Control Flow & Functions

In C, any integer expression can be used as a condition. Zero is false; everything else is true. This is not a quirk — it is a deliberate design that maps directly to the CPU's zero flag after an arithmetic or comparison instruction.

The if statement evaluates an expression. If the result is non-zero (true), it executes the first block; otherwise it falls to else if or else clauses checked in order. Only the first matching branch runs.

Why this matters: C has no dedicated boolean type in C89 (though C99 added _Bool and <stdbool.h>). Kernel code uses plain int for boolean results extensively. You will see idioms like if (ptr) to check for NULL (NULL is 0), and if (!err) to check for success (most kernel functions return 0 on success, negative errno on failure).

Compilation: if (a > b) compiles to a CMP instruction followed by a conditional branch (e.g., jle on x86 — jump if less-or-equal — to the else block). The CPU's branch predictor tries to predict which way the branch goes; modern CPUs are right ~95% of the time on typical code. The kernel uses likely() and unlikely() macros (wrapping GCC's __builtin_expect) to give the compiler hints that improve branch layout.

#include <stdio.h>
#include <stdbool.h>

/* Kernel-style: returns 0 on success, -1 on error */
int parse_header(const char *buf, int len)
{
    if (!buf)          /* NULL check — NULL == 0, so !NULL is true */
        return -1;
    if (len < 4)
        return -1;
    if (buf[0] == 'M' && buf[1] == 'Z')
        return 0;      /* DOS/PE magic bytes */
    else if (buf[0] == 0x7f && buf[1] == 'E')
        return 0;      /* ELF magic */
    else
        return -1;
}

int main(void)
{
    const char elf[] = { 0x7f, 'E', 'L', 'F' };
    int rc = parse_header(elf, 4);
    printf("result: %d\n", rc);   /* prints: result: 0 */
    return 0;
}

A switch statement is a multi-way conditional branch. It evaluates an integer expression (char, int, enum, etc.) and jumps directly to the matching case label — or to default if no case matches.

Fallthrough: Execution continues past a matched case until it hits a break, a return, or the end of the switch. This is intentional: it lets multiple cases share code. But forgetting break is a classic bug. Modern compilers warn about implicit fallthrough; the kernel annotates intentional fallthrough with the fallthrough; pseudo-keyword (a macro resolving to __attribute__((fallthrough)) in GCC).

Jump table: The compiler often compiles a dense switch into a jump table — an array of code addresses indexed by the switch value, making the branch O(1) regardless of how many cases there are. This is a real performance advantage over a chain of if/else if. You will see large switch statements in kernel code (e.g., in ioctl handlers) that benefit from exactly this.

Enum + switch: Pairing an enum with a switch and no default (or with a -Wswitch warning) is a powerful pattern: the compiler warns you if you add a new enum value and forget to handle it in the switch.

#include <stdio.h>

typedef enum { OP_ADD, OP_SUB, OP_MUL, OP_DIV } opcode_t;

int compute(int a, int b, opcode_t op)
{
    switch (op) {
    case OP_ADD: return a + b;
    case OP_SUB: return a - b;
    case OP_MUL: return a * b;
    case OP_DIV:
        if (b == 0) return 0;  /* guard */
        return a / b;
    }   /* no default: compiler warns if enum grows */
    return 0;
}

int main(void)
{
    printf("%d\n", compute(10, 3, OP_MUL));  /* 30 */
    printf("%d\n", compute(10, 3, OP_DIV));  /* 3  */
}

C has three loop constructs, all of which compile to essentially the same machine code (a conditional backward branch), but each optimized for a different intent.

for loop is for when you know the loop structure up front: initialization, condition, increment. Idiomatic for array traversal and counted iterations.

while loop is for when the continuation condition is checked at the top — the body may not execute at all.

do-while loop is for when the body must execute at least once — the condition is checked at the bottom. Used in the kernel in macros (the do { ... } while (0) idiom makes a multi-statement macro safe to use with a trailing semicolon).

break and continue: break exits the innermost loop (or switch). continue skips the rest of the current iteration and jumps to the condition check (for while/do-while) or the increment (for for).

Loop variable scope: In C99 and later, you can declare the loop variable in the for initializer (for (int i = 0; ...)) and it is scoped to the loop. The kernel uses C11, so this is available.

Loop unrolling: The compiler (-O2) often unrolls tight loops — copies the body N times to reduce branch overhead. The kernel sometimes uses #pragma GCC unroll N or the __builtin_expect pattern to guide this.

#include <stdio.h>

/* Count set bits (popcount) — Kernighan's algorithm */
int count_bits(unsigned int n)
{
    int count = 0;
    while (n) {          /* loop until all bits cleared */
        n &= (n - 1);    /* clear lowest set bit */
        count++;
    }
    return count;
}

int main(void)
{
    /* for: iterate over array */
    int arr[] = {3, 1, 4, 1, 5, 9};
    int sum = 0;
    for (int i = 0; i < 6; i++)
        sum += arr[i];
    printf("sum=%d\n", sum);           /* 23 */

    /* do-while: read-at-least-once */
    int x = 1;
    do {
        x *= 2;
    } while (x < 100);
    printf("x=%d\n", x);             /* 128 */

    printf("bits in 0b1011=%d\n",
           count_bits(0b1011));        /* 3 */
    return 0;
}

goto is the most misunderstood keyword in C. In general application code it is rightly avoided — it makes control flow hard to follow. But in the Linux kernel, goto is used extensively and purposefully, and for good reason.

The error-cleanup pattern: When a function acquires multiple resources (allocates memory, opens a file, locks a mutex), it must release them in reverse order if an error occurs partway through. Without goto, you end up with deeply nested if blocks or duplicated cleanup code. With goto, you write cleanup at the bottom and jump there from any error point:

    if (alloc A fails) goto err_a;
    if (alloc B fails) goto err_b;
    ...
err_b: free B;
err_a: free A;
    return -ENOMEM;

This is not spaghetti code — it is a disciplined, readable pattern that the kernel community has agreed upon. The labels are always downward jumps (no jumping into a block, no jumping backward), which keeps the flow linear.

The rule: In the kernel, goto jumps are always forward and always to cleanup labels. If you see a backward goto in kernel code, something unusual is happening.

Why not exceptions or RAII? C has neither. goto is the cleanest C idiom for this. When you read drivers/usb/ or fs/ext4/, you will see this pattern in nearly every non-trivial function.

Labels in C are identifiers followed by a colon. They are in function scope. goto label transfers control unconditionally to that label.

/* Kernel-style resource acquisition with goto cleanup */
#include <stdlib.h>
#include <stdio.h>

typedef struct { int fd; }  file_t;
typedef struct { char *buf; } buf_t;

static file_t *open_file(const char *path) { (void)path; return malloc(sizeof(file_t)); }
static buf_t  *alloc_buf(void)             { return malloc(sizeof(buf_t)); }
static void    close_file(file_t *f)       { free(f); puts("file closed"); }
static void    free_buf(buf_t *b)          { free(b); puts("buf freed"); }

int process(const char *path, int fail_at)
{
    int err = 0;
    file_t *f = NULL;
    buf_t  *b = NULL;

    f = open_file(path);
    if (!f) { err = -1; goto err_file; }
    if (fail_at == 1) { err = -2; goto err_file; }

    b = alloc_buf();
    if (!b) { err = -1; goto err_buf; }
    if (fail_at == 2) { err = -2; goto err_buf; }

    puts("success path");
    /* ... do real work ... */

err_buf:  free_buf(b);   /* only runs if b was allocated */
err_file: close_file(f);
    return err;
}

int main(void)
{
    puts("--- success ---"); process("/dev/null", 0);
    puts("--- fail at 1 ---"); process("/dev/null", 1);
    puts("--- fail at 2 ---"); process("/dev/null", 2);
    return 0;
}

A function definition is the full body of a function — the code that runs when it is called. A declaration (also called a prototype) tells the compiler the function's name, return type, and parameter types, without providing the body. A declaration is enough for the compiler to type-check calls to that function.

Why prototypes matter: C is compiled one translation unit (.c file) at a time. If you call a function defined in another file, the compiler needs to know its signature to generate the right call code (how many bytes to push, what type the return value is). You provide this via a prototype, typically in a .h header file.

Return type: Every function has a return type. void means it returns nothing. int is the conventional return type for success/failure codes in C (and universally in the kernel: 0 = success, negative errno = error).

static functions: A function declared static has internal linkage — it is invisible outside its translation unit. This is crucial in the kernel: most helper functions are static to avoid polluting the global symbol namespace. The kernel has tens of thousands of functions; without static, name collisions would be constant.

inline functions: static inline functions in headers are expanded at the call site like macros but with full type checking. The kernel uses them heavily for small, hot-path helpers.

Forward declaration vs. definition ordering: In a single file, you can either define functions in call order (callee before caller) or use a forward declaration. The kernel style is to use static prototypes at the top of the file when needed.

/* --- math_utils.h --- */
#ifndef MATH_UTILS_H
#define MATH_UTILS_H

/* Declaration (prototype): compiler knows the signature */
int gcd(int a, int b);
int lcm(int a, int b);

/* static inline: expanded at call site, no symbol exported */
static inline int square(int x) { return x * x; }

#endif

/* --- math_utils.c --- */
#include "math_utils.h"

/* Definition: the actual code */
int gcd(int a, int b)
{
    while (b) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;   /* divide first to avoid overflow */
}

/* --- main.c --- */
#include <stdio.h>
#include "math_utils.h"

int main(void)
{
    printf("gcd(48,18)=%d\n", gcd(48, 18));   /* 6  */
    printf("lcm(4,6)=%d\n",   lcm(4, 6));     /* 12 */
    printf("square(7)=%d\n",  square(7));     /* 49 */
    return 0;
}

C passes all function arguments by value: the function receives a copy of each argument. Modifying a parameter inside the function does not affect the caller's variable.

This is not a limitation — it is a powerful guarantee. You can always reason locally about a function: it cannot silently modify your variables through named parameters.

Passing large data efficiently: Copying a big struct every call would be slow. Instead, you pass a pointer to the struct. The pointer is still passed by value (a copy of the address), but through the pointer the function can read or modify the original data. This is the dominant pattern in all C programming, and especially in the kernel (almost every kernel function takes a pointer to a struct).

const pointers: const struct foo *p means "I have a pointer to foo, and I promise not to modify what it points to." This is the kernel's way of expressing read-only access and allows the compiler to optimize further.

Arrays decay to pointers: When you pass an array to a function, it decays to a pointer to its first element. The function does not know the array's length — you must pass it separately. This is a famous source of bugs and also the reason C standard library functions like strncpy take an explicit length.

Returning values: A function can return only one value. For multiple outputs, either return a struct or take output-pointer parameters. The kernel often uses the return value for error codes and writes results through pointer parameters.

#include <stdio.h>

/* By value: caller's 'a' is NOT modified */
void double_val(int x)
{
    x *= 2;   /* modifies the local copy */
}

/* By pointer: caller's value IS modified */
void double_ptr(int *x)
{
    *x *= 2;  /* dereference and modify */
}

/* Large struct: pass by pointer, read-only via const */
typedef struct { int x, y, z; } vec3_t;

float dot(const vec3_t *a, const vec3_t *b)
{
    return (float)(a->x*b->x + a->y*b->y + a->z*b->z);
}

int main(void)
{
    int n = 7;
    double_val(n);          /* n is still 7 */
    printf("after double_val: %d\n", n);  /* 7 */

    double_ptr(&n);
    printf("after double_ptr: %d\n", n);  /* 14 */

    vec3_t u = {1,2,3}, v = {4,5,6};
    printf("dot product: %.0f\n", dot(&u, &v));  /* 32 */
    return 0;
}

The call stack is the region of memory that manages function calls. It works like a stack of plates: each function call pushes a new frame (plate) on top; when the function returns, that frame is popped off.

What a stack frame contains:

• The return address: the address in the caller where execution should resume after this function returns.
• The saved frame pointer (on architectures that use one): the base address of the caller's frame, used for debugging and walking the stack.
• Local variables: all variables declared inside the function.
• Saved registers: values of registers the function must preserve (callee-saved registers per the calling convention).
• Passed-by-value arguments (on some architectures/calling conventions; modern ABIs often pass small arguments in registers).

The stack pointer (SP): A dedicated CPU register (RSP on x86-64, SP on ARM) always points to the top of the stack. When a function is called, SP is decremented to make room for the new frame. When the function returns, SP is restored.

The frame pointer (FP/RBP): An optional register that points to a fixed position in the current frame, making it easy to find local variables and the return address regardless of how much SP has moved. The kernel compiles with -fno-omit-frame-pointer so that stack traces (backtraces) are always readable.

Stack overflow: The kernel has a fixed stack size per thread (~8 KB or 16 KB). If functions recurse too deeply or declare too-large locals, the stack grows into adjacent memory, causing corruption. The kernel stack is much smaller than a typical user-space stack (which defaults to 8 MB). This is why kernel code avoids deep recursion and large stack allocations — you will see kmalloc() used for big buffers rather than stack-local arrays.

Analogy: Think of a stack of work orders in a busy kitchen. When the head chef (main) needs a sauce, he hands the task to the sous chef (a called function) and pins a note on the clipboard with 'come back to step 7 when done' (return address). The sous chef's area is their frame. When they're done, they clean their station and hand back control at the noted step.

/* Visualize the call stack with a simple example.
   Compile: gcc -O0 -g stack_demo.c -o stack_demo
   Then: gdb ./stack_demo  →  run  →  backtrace */
#include <stdio.h>

void c_func(int z)
{
    printf("c_func: z=%d  (deepest frame)\n", z);
    /* At this point the stack (top to bottom) is:
       [c_func frame: z, return addr to b_func]
       [b_func frame: y, return addr to a_func]
       [a_func frame: x, return addr to main]
       [main  frame: return addr to libc start] */
}

void b_func(int y)
{
    printf("b_func: y=%d\n", y);
    c_func(y + 1);
}

void a_func(int x)
{
    printf("a_func: x=%d\n", x);
    b_func(x + 1);
}

int main(void)
{
    a_func(1);
    return 0;
}

A recursive function calls itself (directly or indirectly). Every recursive algorithm has two essential parts:

1. Base case(s): The condition under which the function does NOT recurse and returns directly. Without a base case, you get infinite recursion and a stack overflow.
2. Recursive case: The function calls itself with a smaller or simpler version of the problem, making progress toward the base case.

The mental model: Trust the induction. When writing a recursive function, assume that the recursive call correctly solves the smaller subproblem, and use that result to construct the solution to the larger problem. Do not try to trace the full call chain in your head — just verify the base case and the recursive step.

The call stack during recursion: Each recursive call creates a new stack frame. A recursion of depth N uses N frames simultaneously. For factorial(5), the stack looks like: main → factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1). This is why deep recursion is dangerous in the kernel (small stack!) and why the kernel prefers iterative algorithms.

Tail recursion: A function is tail-recursive if the recursive call is the very last operation (its return value is returned directly, not used in further computation). Tail-recursive functions can be optimized by the compiler into a loop with no stack growth (-O2 enables this in GCC). Classic factorial is NOT tail-recursive because of the pending multiplication n * ...; a rewrite with an accumulator makes it tail-recursive.

Real use in systems: The kernel uses recursion in tree traversal (e.g., VFS directory entry cache, red-black trees), expression parsing, and certain lock-free algorithms. But always with bounded depth, or converted to iterative with an explicit stack.

#include <stdio.h>

/* Non-tail-recursive: pending multiply on return */
unsigned long factorial(int n)
{
    if (n <= 1) return 1;          /* base case */
    return n * factorial(n - 1);   /* recursive case */
}

/* Tail-recursive: accumulator carries the result */
unsigned long factorial_tail(int n, unsigned long acc)
{
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  /* last op = call */
}

/* Classic: binary search via recursion */
int bsearch_r(const int *arr, int lo, int hi, int target)
{
    if (lo > hi) return -1;           /* base: not found */
    int mid = lo + (hi - lo) / 2;    /* avoid overflow */
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)
        return bsearch_r(arr, mid+1, hi, target);
    return bsearch_r(arr, lo, mid-1, target);
}

int main(void)
{
    printf("5! = %lu\n", factorial(5));          /* 120 */
    printf("5! = %lu\n", factorial_tail(5, 1));  /* 120 */

    int sorted[] = {2, 5, 8, 12, 16, 23, 38};
    printf("found 23 at index %d\n",
           bsearch_r(sorted, 0, 6, 23));          /* 5 */
    printf("found 99 at index %d\n",
           bsearch_r(sorted, 0, 6, 99));          /* -1 */
    return 0;
}

Every variable in C has two orthogonal properties: scope (where in the code it can be named) and lifetime (how long it exists in memory).

Automatic (local) variables: Variables declared inside a block {} have block scope and automatic lifetime — they are created when the block is entered (typically on the stack frame) and destroyed when it exits. Accessing them after the block ends is undefined behavior — a classic bug when returning a pointer to a local variable.

Static local variables: A local variable declared static has block scope but static lifetime — it is allocated in the data segment (not the stack), initialized once at program start, and persists across calls. It remembers its value between calls. This is how you implement a counter or a one-time-init inside a function without exposing the variable globally.

Global variables: Declared outside any function; they have file scope (or if extern, program scope) and static lifetime. The kernel uses them for things like the global run queue or the process list, but prefers passing state through pointers to avoid tight coupling.

The danger of returning local addresses: A local variable is stored on the stack frame. When the function returns, that frame is logically gone and will be overwritten by the next function call. Returning a pointer to a local variable is one of the most common bugs in C.

#include <stdio.h>

/* static local: remembers value across calls */
int next_id(void)
{
    static int counter = 0;  /* initialized ONCE */
    return ++counter;
}

/* BUG: returns pointer to stack variable — undefined behavior */
/* int *bad(void) { int x = 42; return &x; }  -- DO NOT DO THIS */

/* CORRECT: caller-provided buffer (kernel style) */
void make_name(char *buf, int size, int id)
{
    /* snprintf is safe: respects size limit */
    /* Using a simplified manual version for clarity */
    buf[0] = 'i'; buf[1] = 'd'; buf[2] = '_';
    buf[3] = (char)('0' + id % 10);
    buf[4] = '\0';
    (void)size;
}

int main(void)
{
    printf("%d %d %d\n",
           next_id(), next_id(), next_id());  /* 1 2 3 */

    char name[16];
    make_name(name, sizeof(name), 7);
    printf("%s\n", name);  /* id_7 */
    return 0;
}

Reading compiler output on Godbolt or with gcc -S demystifies everything. Here is what a simple function call looks like at the machine level on x86-64 Linux (System V ABI).

Calling convention (System V AMD64 ABI):

• First six integer/pointer arguments go in registers: RDI, RSI, RDX, RCX, R8, R9.
• Return value: RAX (integer/pointer), XMM0 (float/double).
• Caller saves: RAX, RCX, RDX, RSI, RDI, R8-R11.
• Callee saves: RBX, RBP, R12-R15.

What call does: Pushes the return address (address of the next instruction) onto the stack, then jumps to the callee.

What ret does: Pops the return address off the stack and jumps to it.

The prologue and epilogue: Most functions begin with push %rbp / mov %rsp,%rbp (save old frame pointer, set new one) and end with pop %rbp / ret. With -fomit-frame-pointer (common at -O2 in user space, but NOT in the kernel), the frame pointer is freed up as a general register and the prologue is omitted.

Understanding this lets you read kernel oops messages, which print a stack trace with raw addresses, and it lets you spot when a compiler is doing something unexpected.

/* C source */
int add(int a, int b) { return a + b; }
int main(void) { return add(3, 4); }

/* x86-64 output (gcc -O0, System V ABI)
   Try it live at https://godbolt.org

add:
    pushq   %rbp          ; save caller's frame pointer
    movq    %rsp, %rbp    ; set our frame pointer
    movl    %edi, -4(%rbp) ; spill arg a (was in RDI)
    movl    %esi, -8(%rbp) ; spill arg b (was in RSI)
    movl    -4(%rbp), %edx
    movl    -8(%rbp), %eax
    addl    %edx, %eax    ; result in EAX (return reg)
    popq    %rbp          ; restore caller's frame pointer
    ret                   ; pop return addr, jump to it

main:
    pushq   %rbp
    movq    %rsp, %rbp
    movl    $4, %esi      ; b = 4  (second arg)
    movl    $3, %edi      ; a = 3  (first arg)
    call    add           ; push ret addr, jump to add
    popq    %rbp
    ret
*/