001 Notes

C Interview Notes

C.1 — Implement `sizeof`

What `sizeof` actually is

sizeof is a compile-time operator, not a function. It returns a size_t and does not evaluate its operand. The single exception is C99 VLAs (variable-length arrays), where the operand is evaluated and the result is computed at runtime:

int n = read_int();
int a[n];                  // VLA
size_t s = sizeof(a);      // runtime: n * sizeof(int)
size_t t = sizeof(int[n]); // runtime

Two surface forms:

sizeof expr      // parens optional
sizeof(type)     // parens required around a type name

sizeof of a function-call expression does not call the function:

int x = 5;
sizeof(x = 10);   // x stays 5; only the type of (x=10) is examined

Naive emulation for an expression

#define SIZEOF(x) ((size_t)((char*)(&(x) + 1) - (char*)&(x)))

How it works: &(x) + 1 advances by one element worth of bytes (pointer arithmetic uses the type’s size). Subtracting two char* gives the difference in bytes. We use char* because pointer subtraction in any other type would divide by that type’s size.

Limitations:

Requires x to be addressable — can’t apply to register variables, bit-fields, or rvalues.
It’s a runtime expression, not a constant expression, so it won’t work in case labels, array sizes, or _Static_assert.

Emulation for a type

#define SIZEOF_TYPE(T) ((size_t)((char*)((T*)0 + 1) - (char*)((T*)0)))

(T*)0 + 1 is the address one element past a null pointer; subtracting from (T*)0 gives the size. Strictly, dereferencing or computing arithmetic on a null pointer of an object type is undefined behavior — but every mainstream compiler does the obvious thing because the addresses are never accessed.

Why you cannot fully replicate `sizeof`

Without compiler help you cannot get:

Constant-expression result (needed for static asserts, array bounds, switch labels).
No evaluation of side effects in sizeof expr.
Incomplete types like sizeof(struct foo) when only the tag is visible.

GCC/Clang provide __builtin_object_size and similar; the real sizeof is hard-baked into the compiler.

Array-decay gotcha

void f(int a[10]) {          // a is actually int*
    sizeof(a);               // sizeof(int*), NOT 10*sizeof(int)
}

int b[10];
sizeof(b);                   // 10*sizeof(int), good
sizeof(b)/sizeof(b[0]);      // common 'array length' macro

The decay-to-pointer happens for function parameters and any time you assign an array to a pointer. This is why ARRAY_SIZE(x) must be defined where the array is in scope as an array.

#define ARRAY_SIZE(a) (sizeof(a)/sizeof((a)[0]))

Linux kernel hardens this:

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]) + __must_be_array(arr))

__must_be_array uses __builtin_types_compatible_p to produce a compile error if arr is a pointer.

Counter-examples to internalize

Expression	Result	Why
`sizeof(char)`	1	by definition
`sizeof('a')` in C	`sizeof(int)`	character constants are `int` in C
`sizeof('a')` in C++	1	`char` in C++
`sizeof("hi")`	3	includes the `'\0'`
`sizeof(struct {})`	0 in C (GCC ext), 1 in C++	empty struct UB-ish in std C; C++ guarantees ≥1
`sizeof(void)`	error in std C, 1 in GCC	extension

C.2 — Implement `memcpy`

Signature: void *memcpy(void *dest, const void *src, size_t n); — returns dest. Undefined behavior if regions overlap (use memmove for that).

Step 0 — naive byte loop

void *memcpy(void *dst, const void *src, size_t n) {
    unsigned char *d = dst;
    const unsigned char *s = src;
    while (n--) *d++ = *s++;
    return dst;
}

Correct, portable, slow. ~1 byte/cycle on modern hardware. Easily 10–50× slower than tuned implementations for large copies.

Step 1 — word-at-a-time when aligned

void *memcpy(void *dst, const void *src, size_t n) {
    unsigned char *d = dst;
    const unsigned char *s = src;

    /* Copy bytes until d is word-aligned */
    while (n && ((uintptr_t)d & (sizeof(long) - 1))) {
        *d++ = *s++; n--;
    }

    /* Copy long-at-a-time if s is also aligned */
    if (!((uintptr_t)s & (sizeof(long) - 1))) {
        long *ld = (long*)d;
        const long *ls = (const long*)s;
        while (n >= sizeof(long)) {
            *ld++ = *ls++;
            n -= sizeof(long);
        }
        d = (unsigned char*)ld;
        s = (const unsigned char*)ls;
    }

    /* Tail */
    while (n--) *d++ = *s++;
    return dst;
}

This is the classic “align then chunk” pattern. ~8× faster on 64-bit machines when both pointers can be aligned together. If src and dst have different alignment relative to a word, you cannot just bit-cast — you’d need to do shift-and-combine on every word, which is rarely worth it; falling back to bytes is fine for unaligned mismatches.

Step 2 — SIMD (SSE/AVX)

#include <immintrin.h>

void *memcpy(void *dst, const void *src, size_t n) {
    unsigned char *d = dst;
    const unsigned char *s = src;

    while (n >= 32) {
        __m256i v = _mm256_loadu_si256((const __m256i*)s);
        _mm256_storeu_si256((__m256i*)d, v);
        s += 32; d += 32; n -= 32;
    }
    while (n--) *d++ = *s++;
    return dst;
}

32 bytes per iteration. With AVX-512, 64 bytes. The loadu/storeu variants handle unaligned input; aligned _mm256_load_si256/_mm256_store_si256 are marginally faster but UB if misaligned.

Step 3 — what glibc actually does

glibc dispatches at startup via IFUNC (indirect function resolver):

Tiny (<16B): handled by branchy code that does overlapping loads.
Small (≤256B): unrolled SSE/AVX with overlapping head+tail trick.
Medium: AVX with cache-line-aligned stores.
Large (≥temp_threshold): non-temporal stores (movnt) to skip the cache and avoid evicting useful data.
Recent Intel: rep movsb — Enhanced REP MOVSB (ERMS) since Ivy Bridge. The CPU implements this as a microcoded fast path that beats software for large sizes.

The overlapping head+tail trick for medium sizes:

if (n <= 32) {
    __m128i a = _mm_loadu_si128((const __m128i*)s);
    __m128i b = _mm_loadu_si128((const __m128i*)(s + n - 16));
    _mm_storeu_si128((__m128i*)d, a);
    _mm_storeu_si128((__m128i*)(d + n - 16), b);
    return dst;
}

For n between 17 and 32, this copies the first 16 bytes and the last 16 bytes. They overlap in the middle — but since both reads are from src before any writes go to overlapping regions of dst, the overlap is fine and you’ve branchlessly handled the entire range size with two loads and two stores.

Step 4 — non-temporal stores for huge copies

while (n >= 64) {
    __m256i a = _mm256_loadu_si256((const __m256i*)s);
    __m256i b = _mm256_loadu_si256((const __m256i*)(s + 32));
    _mm256_stream_si256((__m256i*)d, a);          // bypasses cache
    _mm256_stream_si256((__m256i*)(d + 32), b);
    s += 64; d += 64; n -= 64;
}
_mm_sfence();   // ensure stores visible

movnt/stream bypasses the cache. For a copy larger than L3 you’d otherwise pollute the cache with data you won’t read again. Costs: alignment is required (movntdq needs 16-aligned, vmovntdq 32-aligned), and you must sfence before any code depending on the writes.

Decision tree

Size	Best strategy
< 8 B	inline by-byte or overlapping loads
8 B – L1 size	SIMD or unrolled word loop with cached stores
> L3	non-temporal stores, no cache pollution
Memory-mapped IO	`volatile` loop, no SIMD reordering

Counter-example: when memcpy is the wrong tool

struct S { int a, b; };
struct S x = {1,2}, y;
memcpy(&y, &x, sizeof y);     // ok but bad style
y = x;                        // let compiler choose

Compilers inline memcpy for known-size, known-alignment cases — and y = x lets the compiler track aliasing better.

For overlapping regions:

memmove(dst, src, n);          // handles overlap

memmove checks dst < src vs dst > src and copies in the right direction (forward or backward) so overlap doesn’t corrupt the source.

C.3 — Implement `typeof`

typeof (C23) or __typeof__ (GCC extension since the 1980s) is a compile-time type operator: typeof(expr) becomes the type of expr without evaluating it. Useful for type-safe, type-generic macros.

Idiomatic use — type-safe MAX

Naive (unsafe):

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int x = 5;
int y = MAX(x++, 10);    // x++ evaluated twice — bug

Side effects are double-evaluated and types are not preserved. The fix with GCC’s “statement expression” + __typeof__:

#define MAX(a, b) ({              \
    __typeof__(a) _a = (a);       \
    __typeof__(b) _b = (b);       \
    _a > _b ? _a : _b;            \
})

Each operand evaluated once; both copies are typed. The Linux kernel goes further:

#define max(x, y) ({                                  \
    typeof(x) _max1 = (x);                            \
    typeof(y) _max2 = (y);                            \
    (void) (&_max1 == &_max2);                        \
    _max1 > _max2 ? _max1 : _max2; })

The (void)(&_max1 == &_max2) triggers a compiler warning if the types differ (comparing incompatible pointer types), catching mixed-sign comparisons that silently misbehave.

Without GCC extensions — `_Generic` (C11)

#define abs(x) _Generic((x),                  \
    int:        abs,                          \
    long:       labs,                         \
    long long:  llabs,                        \
    float:      fabsf,                        \
    double:     fabs,                         \
    long double:fabsl)(x)

_Generic dispatches at compile time based on the type of the controlling expression. Different from typeof — _Generic selects an expression, typeof yields a type.

typeof gotchas

int a[10];
typeof(a) b;             // int[10], OK
typeof(a) *p = &a;       // int(*)[10] — array pointer

If the operand is an lvalue expression, typeof preserves arrayness. If it’s a function-parameter-style decay you’ve already converted to pointer.

const int x = 5;
typeof(x) y;             // const int — const propagates

In C23, both typeof (preserves qualifiers) and typeof_unqual (strips them) exist.

When to use vs avoid

Use typeof:

Type-safe macros (MAX, SWAP, min_t)
Hash table macros where the value type is the caller’s choice
Linux kernel container_of, READ_ONCE/WRITE_ONCE

Avoid:

Public API headers when you can’t require GCC/C23 — use _Generic or specialize per type
Cases where an inline function works just as well and gives you a real symbol for debugging

C.4 — Implement `NULL`

What `NULL` is

In <stddef.h> (and several other headers), NULL is a null pointer constant: an integer constant expression with value 0, or such an expression cast to void*.

/* Common C definition */
#define NULL ((void*)0)

/* C++ pre-11 */
#define NULL 0

/* C++11 onward */
#define NULL nullptr

A null pointer constant, when assigned to a pointer of any type, yields a null pointer value — guaranteed by the standard to compare unequal to any pointer to an actual object.

The `(void*)0` vs `0` debate

In C, (void*)0 is preferred because:

It catches misuse in variadic functions: printf("%p", NULL) — NULL = 0 would push an int, breaking calling conventions on platforms where sizeof(int) != sizeof(void*).
execl("/bin/ls", "ls", NULL) requires a pointer-sized null sentinel; 0 would be wrong on LP64.

In C++, (void*)0 is wrong because C++ disallows implicit conversion from void* to other pointer types. So C++ traditionally used 0, and now nullptr.

Why `nullptr` exists (C++)

void f(int);
void f(char*);

f(0);          // calls f(int) — surprising for null-pointer intent
f(NULL);       // calls f(int) when NULL is 0
f(nullptr);    // calls f(char*) — unambiguous

nullptr has type std::nullptr_t, convertible to any pointer type but not to integral types. C23 adopted nullptr too.

Is NULL guaranteed to be all-zero bits?

No. The standard guarantees the null pointer value compares equal to the integer constant 0, but the bit pattern in memory is implementation-defined.

Most platforms: all zeros (memset(ptr, 0, sizeof ptr) produces a null pointer in practice).
Some historical platforms (e.g. some Honeywell, Symbolics) used non-zero bit patterns.

For portable struct zero-init, = {0} or = {} (C23) sets pointer members to null pointer values regardless of bit representation.

Common patterns

if (p)          /* null-pointer check */
if (p != NULL)  /* equivalent, explicit */
if (!p)         /* null-pointer check */

Don’t write if (p == 0) — works, but conflates pointer and integer.

Counter-example: NULL as int

int n = NULL;   /* legal in C (NULL is integer constant), bad style */
                /* legal in C++ pre-11 if NULL=0; rejected if NULL=nullptr */

Tools like -Wzero-as-null-pointer-constant (clang) flag this.

C.5 — Implement `malloc`

This is the deepest C question on the list. Pacing: bump → free list → boundary tags → size classes → arenas → thread cache.

Step 0 — bump allocator (no free)

#include <unistd.h>

void *malloc(size_t n) {
    void *p = sbrk(n);
    return p == (void*)-1 ? NULL : p;
}
void free(void *p) { (void)p; }

Each call extends the program break by n. No free. Used by some kernels’ boot allocators and by tiny embedded runtimes. O(1), zero metadata overhead, but memory is monotonically consumed.

Step 1 — free list with coalescing

Carve heap into blocks with a header recording size and “in-use” bit. On free, walk a free list to find a slot; on alloc, find a fit and split.

typedef struct block {
    size_t size;            /* low bit = in-use */
    struct block *next;     /* free list link, only when free */
} block_t;

#define ALIGN     8
#define HEADER    sizeof(size_t)
#define ALIGN_UP(n) (((n) + ALIGN - 1) & ~(ALIGN - 1))

static block_t *freelist = NULL;
static void *heap_end = NULL;

void *malloc(size_t n) {
    n = ALIGN_UP(n);
    block_t **prev = &freelist, *b;
    for (b = freelist; b; prev = &b->next, b = b->next) {
        if ((b->size & ~1UL) >= n) {
            *prev = b->next;            /* unlink */
            b->size |= 1;               /* mark in-use */
            return (char*)b + HEADER;
        }
    }
    /* grow heap */
    b = sbrk(n + HEADER);
    if (b == (void*)-1) return NULL;
    b->size = n | 1;
    return (char*)b + HEADER;
}

void free(void *p) {
    if (!p) return;
    block_t *b = (block_t*)((char*)p - HEADER);
    b->size &= ~1UL;
    b->next = freelist;
    freelist = b;
}

First-fit, no coalescing, fragmentation gets bad. Adding boundary tags (Knuth) — duplicate the size at the end of each block — lets us coalesce in O(1):

| size_hdr | payload .... | size_ftr |

On free, look at the previous block’s footer and the next block’s header; if either is free, merge.

Step 2 — size classes (slab / segregated lists)

Free list per size class:

class[0]: 16 B
class[1]: 32 B
class[2]: 48 B
...
class[k]: 8*(k+2) B

Small allocations go to the right class instantly (O(1) bucket index). Each class has its own free list; same-size freed blocks go back to the same list. No fragmentation within a class. Wasted space due to over-rounding is bounded.

This is the slab allocator in kernels (kmem_cache_*) and the foundation of jemalloc / tcmalloc.

Step 3 — mmap for large allocations

if (n >= MMAP_THRESHOLD) {            /* ~128 KB in glibc */
    void *p = mmap(NULL, n + page_size, ...);
    /* record n in page header */
    return p + page_size;
}

Why split: brk is per-process linear; large free blocks in the middle can’t be returned to the OS. mmap regions can be munmap’d immediately.

Step 4 — per-thread cache (tcmalloc / jemalloc)

Every malloc call grabbing a global lock is fatal at scale.

Per-thread cache of small free blocks. Cache miss → grab from central free list under lock. Returns go to thread cache first, batched back to central.
Arenas: divide central storage into N arenas (one per CPU or sharded by thread ID) so locks don’t contend.
Size-class round-trips are O(1) into thread-local arrays.

jemalloc has the most refined design:

4-tier hierarchy: tcache → arena bin → arena run → chunk.
Tcache holds dozens of recently-freed blocks per size class.
“Decay-based purging” lazily returns memory to the OS via madvise(MADV_DONTNEED).

tcmalloc (Google) uses a central free list and a thread-local cache. Both designs converge.

Real-world numbers

glibc malloc (ptmalloc2): ~30 ns small alloc/free.
jemalloc: ~15 ns, ~3× lower fragmentation under load.
tcmalloc: ~12 ns, optimized for short-lived allocs.

Gotchas to mention

Double free / use-after-free require quarantine/poison lists. jemalloc’s MALLOC_CONF=junk:true writes a pattern; AddressSanitizer maintains a red zone.
brk is one global break per process — multithreaded growers must lock.
munmap returns memory eagerly, brk shrinks only the tail. Long-lived servers often “leak” memory not because of bugs but because of fragmentation preventing tail shrink.
Alignment: malloc(n) must return at least alignof(max_align_t) aligned. For larger needs use posix_memalign or aligned_alloc(alignment, size) (C11).

Counter-example: arena allocator

For request-scoped work (web request, parser pass), use a bump arena and reset at end:

struct arena { char *buf; size_t off, cap; };

void *arena_alloc(struct arena *a, size_t n) {
    n = ALIGN_UP(n);
    if (a->off + n > a->cap) return NULL;
    void *p = a->buf + a->off;
    a->off += n;
    return p;
}

void arena_reset(struct arena *a) { a->off = 0; }

O(1) alloc, O(1) bulk free, zero metadata per allocation. Orders of magnitude faster than malloc for request-scoped data. Pattern is common in compilers (LLVM BumpPtrAllocator), game engines, kernel code.

C.6 — Memory-saving struct design

Padding mechanics

Every type has a natural alignment (often equal to its size for primitives). The compiler inserts padding so each member is aligned, and the struct is padded so an array of the struct keeps every element aligned.

struct bad {
    char  a;      /* 1 */
    /* 7 bytes pad */
    long  b;      /* 8 */
    char  c;      /* 1 */
    /* 7 bytes pad — tail, so arrays stay aligned */
};
/* sizeof = 24 */

struct good {
    long  b;      /* 8 */
    char  a;      /* 1 */
    char  c;      /* 1 */
    /* 6 bytes pad */
};
/* sizeof = 16 */

Rule of thumb: order members by descending alignment (long → int → short → char).

Bitfields

struct flags {
    unsigned valid:1;
    unsigned dirty:1;
    unsigned mode:3;
    unsigned :0;          /* force alignment of next field */
    unsigned id:24;
};

Bitfields pack flag-style fields into a single word. Caveats:

Order across the underlying storage unit is implementation-defined (MSB-first vs LSB-first).
Taking the address of a bitfield is illegal.
They’re slower to read/write than a full word; the compiler emits shift+mask.

Use bitfields when memory matters more than speed (network packet headers, on-disk structures). For hot fields use plain ints.

`attribute((packed))` — what it does and what it costs

struct __attribute__((packed)) net_hdr {
    uint8_t  ver;
    uint32_t addr;       /* no padding inserted */
};

Padding removed; struct size is sum of member sizes.
All member accesses become potentially unaligned — compiler emits byte-by-byte loads or movbe/unaligned-aware insns.
On ARM (older), unaligned access traps. Even on x86 it costs cycles.
Worst trap: taking &packed.addr produces a pointer whose alignment doesn’t satisfy the type. Subsequent dereferences are UB.

Use packed only for serialization or protocol structs where you control all accesses.

Unions for tagged variants

struct value {
    enum { INT, STR, FLT } tag;
    union {
        int    i;
        char  *s;
        float  f;
    } u;
};

The union occupies the size of its largest member. The tag adds 4 bytes plus 4 padding (likely). A “naive” struct with all three fields would cost sizeof(int)+sizeof(char*)+sizeof(float) ≈ 16 B; the tagged union costs max(4,8,4) + 4 (tag) + 4 pad = 16 B here, but if you had 5 alternatives the union still costs max + tag, the struct grows.

Reducing pointer count

Replace 64-bit pointers with 32-bit indices into a base array. Halves pointer memory on large dense structures (graphs, ECS). Costs an extra dereference and ties lifetimes to the base array.

struct node {
    uint32_t left;     /* index, not pointer */
    uint32_t right;
} nodes[1 << 28];      /* up to 256M nodes — addressable by 32-bit index */

Hot/cold splitting

struct task {
    /* hot: touched every scheduler tick */
    uint64_t runtime;
    int      state;

    /* cold: rarely touched */
    char     name[64];
    struct credential *cred;
};

→ split into struct task_hot and struct task_cold if they’re processed in different loops. Keeps the hot cache line dense.

Empty-base optimization (C++) and zero-size structs

C: an empty struct is non-standard (GCC gives size 0; some compilers reject). C++: empty struct has size ≥ 1 so distinct objects have distinct addresses, but with [[no_unique_address]] (C++20) you can stash an empty class inside another with zero cost.

Counter-example: don’t sacrifice readability for 4 bytes

struct user {
    char name[32];
    int  id;
    bool admin;
    /* 3 bytes pad */
};

If you have a thousand users, you save 3 KB by reordering. If you have a billion, you save 3 GB — worth it. For small N, leave it readable.

Debugging tool

pahole struct_name binary.elf    # shows layout + padding

pahole (from dwarves) reads DWARF debug info and prints the layout with holes. Essential for memory tuning.

C.7 — Implement `offsetof`

offsetof(type, member) from <stddef.h> returns the byte offset of member within type. Compile-time constant.

Classic implementation

#define offsetof(t, m) ((size_t)(&((t*)0)->m))

How: pretend a t lives at address 0, take the address of m, that is the offset.

This is technically undefined behavior by the strict letter of the standard (forming a pointer to a member of a null object), but every compiler defines it because the address is never dereferenced.

Strictly conforming variant

#define offsetof(t, m) ((size_t)((char*)&(((t*)1)->m) - (char*)1))

Use 1 instead of 0; the standard objection vanishes. Still works.

What the compilers actually use

GCC and Clang have __builtin_offsetof:

#define offsetof(t, m) __builtin_offsetof(t, m)

Why a builtin? Two reasons:

C++ inheritance: ((t*)0)->m is UB-prone if t uses virtual base classes — there’s no fixed offset until you have an object.
Strict alias warnings: the builtin doesn’t trip -Werror=null-dereference.

What it’s used for

container_of (see C.8)
Hand-rolled hash tables that embed a link
Serialization layout descriptors
Kernel data structure introspection

Gotcha — bitfields

struct s {
    int a:4;
    int b:4;
};
offsetof(struct s, b);  /* error: cannot take address of bitfield */

offsetof is not defined for bitfield members.

C.8 — Implement `container_of`

The Linux-kernel macro you’ve definitely seen:

#define container_of(ptr, type, member) ({                       \
    const __typeof__(((type*)0)->member) *__mptr = (ptr);        \
    (type *)((char*)__mptr - offsetof(type, member));            \
})

What it does

Given a pointer to a member, get the pointer to the enclosing struct.

struct list_head { struct list_head *next, *prev; };

struct task {
    int pid;
    struct list_head run;
};

/* You have a list_head*, you want the struct task* */
struct task *t = container_of(node, struct task, run);

Why the `typeof` dance

The plain version is:

#define container_of(ptr, type, member) \
    ((type*)((char*)(ptr) - offsetof(type, member)))

Works fine. The kernel version adds a type-checking layer: it copies ptr into a __typeof__(((type*)0)->member) * variable. If ptr has the wrong type, the compiler warns about incompatible pointer types. Otherwise a typo like

container_of(some_unrelated_ptr, struct task, run);

would silently produce garbage.

Why intrusive containers exist

Doubly-linked list nodes embedded in the struct, no separate node-with-pointer allocation:

+--------------------+      +--------------------+
| struct task        |      | struct task        |
|   int pid          |      |   int pid          |
|   list_head run -----+  +---- list_head run    |
+--------------------+ |  | +--------------------+
                       +--+

The list APIs walk list_head nodes; container_of recovers the enclosing object. Zero allocation overhead, perfect for kernel code where allocation can fail.

Generic intrusive list

#define list_for_each_entry(pos, head, member)                                  \
    for (pos = container_of((head)->next, __typeof__(*pos), member);            \
         &pos->member != (head);                                                \
         pos = container_of(pos->member.next, __typeof__(*pos), member))

The macro takes the field name and iterates struct-by-struct, hiding all container_of calls.

Counter-example — when to use ordinary heap nodes

For application code where allocation is cheap, ordinary struct list_node { T* item; struct list_node *next; } is simpler. Intrusive only pays off when:

Memory pressure matters (kernel, embedded).
Each item participates in multiple containers (run queue + hash + LRU) — separate node-with-pointer would multiply alloc cost.
You want O(1) unlinking without a search.

C.9 — Macros vs inline functions

What they are

Macros are text substitution by the preprocessor. No notion of types, scopes, or evaluation order.
Inline functions are real functions the compiler may inline at the call site. Full type checking, normal scoping, single evaluation.

Side-effects bug

#define SQR(x) ((x) * (x))
int n = 3;
int r = SQR(n++);     /* expands to ((n++) * (n++)) — UB */

Two evaluations of n++ in the same sequence point is UB (pre-C11) and produces 9 or 12 unpredictably. Inline function:

static inline int sqr(int x) { return x * x; }
int r = sqr(n++);     /* n incremented once, value 9 used */

Precedence bug

#define SQR(x) (x) * (x)
int y = SQR(1+2);     /* (1+2)*(1+2) = 9 — OK */
int z = SQR(1+2) + 1; /* (1+2)*(1+2) + 1 = 10 — OK */

/* but: */
#define SQR(x) x*x
int w = SQR(1+2);     /* 1+2*1+2 = 5 — wrong */

Always parenthesize macro arguments and the whole expansion. Or use inline.

Multi-statement macro pattern

#define LOG(msg) do {                          \
    fprintf(stderr, "%s\n", msg);              \
    fflush(stderr);                            \
} while (0)

The do { } while (0) makes it a single statement so if (cond) LOG(x); else ... parses correctly. Inline functions don’t have this problem.

When macros are the right tool

Compile-time constants:

#define MAX_USERS 1024
char buf[MAX_USERS];   /* must be a constant expression */

static const int is not a constant expression in C (it is in C++).

Conditional compilation:

#ifdef DEBUG
#define DBG(x) printf("%s\n", x)
#else
#define DBG(x)
#endif

Stringification / token-pasting:
```
#define STR(x) #x
#define CAT(a,b) a##b
```

Type-generic interfaces without templates:

#define MAX(a,b) ({ typeof(a) _a=(a); typeof(b) _b=(b); _a>_b?_a:_b; })

assert-like constructs where you need to capture __FILE__/__LINE__.

X-macros:

#define COLORS X(RED) X(GREEN) X(BLUE)
enum { COLORS };
#define X(c) #c,
const char *names[] = { COLORS };

When inline is the right tool

All numeric/general computation
Anything that should appear in a backtrace as a real function
Anything debugger users need to step into
When you want overload-like behavior in C++, but in C you can use _Generic

Performance — does `inline` actually inline?

inline is a hint. The compiler decides based on optimization level, size, callsite count. With static inline, the compiler is usually willing. With LTO, even non-inline cross-TU calls can be inlined.

GCC: __attribute__((always_inline)) forces; __attribute__((noinline)) forbids.

A macro is guaranteed to be expanded inline by the preprocessor. So for must-inline tiny hot code (like reading hardware registers), macros remove any uncertainty.

Debugging

Macros show their expanded form in errors — sometimes thousands of characters of soup.
Inline functions have names in stack traces, can be stepped into, have proper line numbers.

Counter-example: when inline can hurt

inline void foo(void) { /* huge body */ }

If inlined everywhere, code size explodes, icache misses tank performance. Compiler will usually refuse, but always_inline forces a bad outcome.

C.10 — `extern`, `static`, declaration vs definition, linkage rules

Declaration vs definition

Declaration: announces a name and its type. No storage allocated; can appear many times.
Definition: allocates storage (for objects) or provides a body (for functions). Exactly one per program (for non-static).

extern int x;        /* declaration */
int x = 5;           /* definition (also a declaration) */

int f(int);          /* declaration */
int f(int n) { ... } /* definition */

A tentative definition is the tricky middle case:

int x;               /* tentative definition at file scope */

If no other definition exists in the TU, this becomes a real definition with zero init. Multiple tentative definitions in a single TU collapse to one. In C this works; in C++ it’s a definition immediately and multiple are ODR violations.

Linkage — the three kinds

Linkage	Means	Default for
External	Visible across TUs; one definition program-wide	file-scope objects/functions
Internal	Visible only within this TU	file-scope objects/functions declared `static`
None	Visible only within block scope	block-scope objects

`extern` — three different jobs

Forward declare something defined elsewhere:

/* header.h */ extern int counter;
/* impl.c   */ int counter = 0;

Re-declare a variable to refer to an existing external one (rarely needed).

Function declarations at file scope are implicitly extern:

void f(void);            /* same as: extern void f(void); */

`static` at file scope vs block scope

/* file scope */
static int counter;      /* internal linkage — not visible from other TUs */
static int helper(void); /* internal linkage — TU-private helper */

void f(void) {
    static int n;        /* block scope, static storage duration */
    n++;                 /* persists across calls */
}

These are unrelated meanings of the same keyword. See C.11.

What’s the default?

Where	Default storage	Default linkage
File-scope object	static (entire program lifetime)	external
File-scope function	n/a	external
Block-scope object without `static`	automatic (stack)	none
Block-scope object with `static`	static	none
Function parameter	automatic	none

Multiple-definition errors

The linker rule: exactly one definition of each external symbol across all linked TUs.

/* a.c */ int x = 1;
/* b.c */ int x = 2;        /* link error: multiple definition of 'x' */

Fix with static:

/* a.c */ static int x = 1;
/* b.c */ static int x = 2; /* OK — each is internal */

Or with extern:

/* header.h */ extern int x;
/* a.c     */ int x = 1;
/* b.c     */ #include "header.h"  /* uses a.c's x */

Common subtle bugs

Header with a non-static definition:

/* shared.h */ int counter;     /* tentative definition */

Two TUs including this header get two counters in C (linker may merge) or a hard error in C++. Fix: declare in the header, define in exactly one .c.

Static inline in header:

/* fast.h */ static inline int sqr(int x) { return x*x; }

Safe — each TU gets its own copy, linker doesn’t see it as a global.

extern with initializer:

extern int x = 5;        /* this is a definition, not a declaration */

The extern is ignored. Confusing — avoid.

`inline` and `extern inline`

C99 inline rules are notoriously fiddly. Summary:

static inline — definition per TU, no external symbol. Safe everywhere.
extern inline — must be paired with a non-inline definition somewhere.
inline alone — the compiler may or may not emit an external definition; rules differ from C++.

For most code, write static inline in headers and stop worrying.

C.11 — The `static` keyword

Five distinct meanings:

1. File-scope variable — internal linkage

static int g_count;     /* not visible outside this TU */

2. File-scope function — internal linkage

static void helper(void) { ... }    /* TU-private */

3. Block-scope variable — static storage duration

int next_id(void) {
    static int n = 0;     /* initialized once, persists */
    return ++n;
}

Initialization happens before main if the initializer is a constant expression; for C99 with non-constant initializers (e.g., a function call), behavior is implementation-defined (C++ has “magic statics” guaranteed thread-safe; C does not).

4. Array parameter — minimum size hint (C99)

void f(int a[static 10]) { ... }   /* caller promises a has >= 10 elements */

Lets the compiler assume a[0]..a[9] are valid for prefetch / vectorization. Violation is UB.

5. C++ class static member

struct S {
    static int n;          /* one per class, not per instance */
};
int S::n = 0;              /* definition in exactly one TU */

(Out of scope for plain C.)

Linkage vs storage duration — keep them separate

static confuses people because:

At file scope it changes linkage (external → internal).
At block scope it changes storage duration (automatic → static).

It never changes both at the same time.

Common pitfalls

Static initialization order fiasco (C++ only). Multiple TUs with non-trivial static initializers; order between TUs is undefined. C avoids it by requiring static initializers to be constant expressions.

Thread safety of static locals (C):

int next_id(void) {
    static int n;
    return ++n;          /* race in multithreaded code */
}

Use _Atomic int or a mutex.

static and recursion:

int f(void) {
    static int depth;
    depth++;
    if (depth < 3) f();
    depth--;
    return 0;
}

The variable is shared across recursive invocations — that’s the whole point of static, not a bug.

C.12 — The `restrict` keyword (C99)

Contract

T *restrict p tells the compiler: for the lifetime of p, the object pointed to is accessed only through p (or pointers derived from p). Aliasing through another pointer is undefined.

This is a promise to the compiler, not a check. Violation: UB, optimizer assumes you, silent miscompiles.

Why it exists — autovectorization

void add(int *a, int *b, int *c, size_t n) {
    for (size_t i = 0; i < n; i++) a[i] = b[i] + c[i];
}

Compiler must assume a may alias b or c. If a == b+1, the loop has a true dependency. So it must emit scalar code, or version into aliased/non-aliased branches.

void add(int *restrict a, int *restrict b, int *restrict c, size_t n) {
    for (size_t i = 0; i < n; i++) a[i] = b[i] + c[i];
}

Now the compiler knows no aliasing — full SIMD vectorization, no version split. Often 4–8× faster.

Standard library uses

void *memcpy(void *restrict dest, const void *restrict src, size_t n);

Reflects the actual contract: dest and src must not overlap. memmove does not have restrict because it explicitly handles overlap.

Multiple `restrict` pointers

The contract is that no two restrict pointers access overlapping memory. So:

int x;
int *restrict p = &x;
int *restrict q = &x;     /* UB if both are used to write */

But pointers derived from the same restrict parent are fine:

int *restrict p = arr;
int *q = p + 5;           /* OK — q is derived from p */
*q = 1; *p = 2;           /* both writes go through p's family */

`restrict` on struct fields

C99 permits it; rarely useful. Generally restrict applies to function parameters and locals.

When to use

Hot loops that operate on multiple arrays
Library APIs where overlap doesn’t make sense
Anywhere you’re chasing vectorization

When to avoid

Public APIs where callers might pass overlapping buffers (memmove, not memcpy)
Reference-counted or shared-data structures

Counter-example: subtle UB

void zero(int *restrict a, int *restrict b, size_t n) {
    for (size_t i = 0; i < n; i++) {
        a[i] = 0;
        b[i] = 0;
    }
}

int arr[10];
zero(arr, arr, 10);    /* UB! both restrict pointers point to same object */

The function compiles, runs, and may even produce the right result — but the optimizer is allowed to assume non-aliasing. Sanitizers (UBSan) can catch some cases at runtime.

C.13 — Implement `strcpy`, `strncpy`

`strcpy`

char *strcpy(char *dst, const char *src) {
    char *p = dst;
    while ((*p++ = *src++))
        ;
    return dst;
}

The assignment-in-condition copies the byte and tests it; when '\0' is copied it returns false. Clean idiom, fine performance for small strings.

Word-at-a-time strcpy

Real implementations walk a word at a time, checking each word for a zero byte (Hacker’s Delight trick):

#define HAS_ZERO_BYTE(w) (((w) - 0x0101010101010101ULL) & ~(w) & 0x8080808080808080ULL)

This expression is nonzero iff some byte of w is 0x00. So you read a 64-bit word, test the mask, and if no zero, store the whole word and advance. Only when a zero is found do you fall back to byte-by-byte to find its exact position. Combined with SIMD (pcmpeqb to find the zero), modern strcpy is ~10× faster than naive.

`strncpy` — and why it’s so dangerous

char *strncpy(char *dst, const char *src, size_t n) {
    size_t i;
    for (i = 0; i < n && src[i] != '\0'; i++)
        dst[i] = src[i];
    for (; i < n; i++)
        dst[i] = '\0';    /* pad with zeros */
    return dst;
}

Two surprising behaviors:

If strlen(src) >= n, dst is NOT null-terminated. You can iterate off the end.
If strlen(src) < n, it pads the rest with '\0'. For large n this is wasted work.

strncpy was designed for fixed-width database records where you wanted exactly N bytes with zero padding. Using it as “safe strcpy” is wrong.

The “safe” alternative — `strlcpy` (BSD)

size_t strlcpy(char *dst, const char *src, size_t size) {
    size_t srclen = strlen(src);
    if (size > 0) {
        size_t copy = srclen < size - 1 ? srclen : size - 1;
        memcpy(dst, src, copy);
        dst[copy] = '\0';
    }
    return srclen;    /* returns total length src — lets caller detect truncation */
}

Guaranteed to null-terminate (when size > 0); returns full source length so caller can detect truncation. Glibc finally added it in 2.38 (2023).

`snprintf` as a safe alternative

snprintf(dst, size, "%s", src);

Always null-terminates, returns the length that would have been written. Slower than strlcpy but universally available.

Counter-example — overlap

char buf[] = "hello";
strcpy(buf + 1, buf);    /* UB — overlapping source and dest */

Always undefined. Use memmove-like logic if you need overlap.

Real-world strcpy is hardened

glibc’s strcpy is __strcpy_chk under _FORTIFY_SOURCE=2, which inserts size checks at the call site using compile-time __builtin_object_size. Catches some buffer overflows even before runtime.

C.14 — Implement `itoa`, `atoi`

`atoi` — basic

int atoi(const char *s) {
    while (*s == ' ' || (*s >= '\t' && *s <= '\r')) s++;
    int sign = 1;
    if (*s == '-') { sign = -1; s++; }
    else if (*s == '+') s++;
    int n = 0;
    while (*s >= '0' && *s <= '9')
        n = n * 10 + (*s++ - '0');
    return sign * n;
}

Limitations of atoi:

No error reporting — invalid input returns 0, indistinguishable from "0".
Silent overflow → UB.

`strtol` is the right tool

long strtol(const char *restrict s, char **restrict endptr, int base);

Returns the parsed value, sets *endptr to the first non-digit, sets errno = ERANGE on overflow. Use this in real code.

Skeletal implementation:

long strtol(const char *s, char **endptr, int base) {
    /* skip whitespace */
    while (isspace((unsigned char)*s)) s++;

    int neg = 0;
    if (*s == '-') { neg = 1; s++; }
    else if (*s == '+') s++;

    /* auto-detect base */
    if (base == 0) {
        if (s[0] == '0' && (s[1] == 'x' || s[1] == 'X')) { base = 16; s += 2; }
        else if (s[0] == '0') base = 8;
        else base = 10;
    } else if (base == 16 && s[0] == '0' && (s[1] == 'x' || s[1] == 'X')) {
        s += 2;
    }

    long acc = 0;
    long cutoff = neg ? LONG_MIN : LONG_MAX;
    long cutlim = cutoff % base;
    cutoff /= base;
    if (neg) { cutlim = -cutlim; cutoff = -cutoff; }
    int any = 0, overflow = 0;

    for (;;) {
        int c = (unsigned char)*s;
        int d;
        if (isdigit(c)) d = c - '0';
        else if (isalpha(c)) d = (c | 0x20) - 'a' + 10;
        else break;
        if (d >= base) break;
        if (overflow || acc > cutoff || (acc == cutoff && d > cutlim))
            overflow = 1;
        else { acc = acc * base + d; any = 1; }
        s++;
    }

    if (endptr) *endptr = (char*)(any ? s : s - !!neg);
    if (overflow) { errno = ERANGE; return neg ? LONG_MIN : LONG_MAX; }
    return neg ? -acc : acc;
}

`itoa` — non-standard, here’s the idiom

char *itoa(int value, char *buf, int base) {
    char tmp[36];
    int  i = 0;
    unsigned uval = value < 0 && base == 10 ? -(unsigned)value : (unsigned)value;

    do {
        int d = uval % base;
        tmp[i++] = d < 10 ? '0' + d : 'a' + d - 10;
        uval /= base;
    } while (uval);

    char *p = buf;
    if (value < 0 && base == 10) *p++ = '-';
    while (i--) *p++ = tmp[i];
    *p = '\0';
    return buf;
}

Digit extraction is by modulo, but they come out reversed — we collect into a temp and then reverse-copy. Direct two-pointer reverse on the buffer is equally common.

Optimized integer formatting

snprintf("%d", n) is fine for general use but allocates inside. For hot paths (logging, protocol encoding), prebuilt approaches:

Look-up table for 2-digit pairs (facebook/folly):

static const char digits[201] =
  "0001020304050607080910111213141516171819"
  "2021222324252627282930313233343536373839"
  "...";

Two digits at a time — halves the divisions.

64-bit reciprocal multiplication instead of % 10:
```
uint64_t q = (uint64_t)n * 0xcccccccccccccccdULL >> (64 + 3);    /* n / 10 */
```
Cuts divs to multiplies. Compilers do this automatically when divisor is a constant.

Counter-example: locale-sensitive parsing

atof("3,14") parses to 3.0 in C locale, 3.14 in German locale. strtod_l lets you pin the locale. For data interchange use a locale-independent parser (std::from_chars in C++17).

C.15 — Pointer arithmetic

Rules

T *p + n advances by n * sizeof(T) bytes — it counts elements, not bytes.
p - q (same type) yields a ptrdiff_t count of elements.
Comparisons (<, >, <=, >=) are defined only for pointers into the same array (or one-past-end).
void * arithmetic is not standard but GCC allows it as bytes (p + 1 moves one byte). Cast to char * portably.

Equivalence `a[i] = *(a + i)`

The subscript operator is defined as:

E1[E2] ≡ *((E1) + (E2))

This is symmetric: 5[a] is the same as a[5]. Try it once for amusement, never in real code.

Type of subtraction

int arr[100];
int *p = &arr[20], *q = &arr[5];
ptrdiff_t d = p - q;       /* 15 */

ptrdiff_t is signed. On most 64-bit systems it’s 64-bit. The standard guarantees ptrdiff_t is large enough to hold the difference between any two pointers in the same object.

One-past-the-end

The address arr + N (for arr[N]) is well-defined and may be compared/subtracted, but dereferencing is UB. This is why loops like for (p = arr; p != arr + N; p++) are safe.

Array decay

void f(int *p);

int arr[10];
f(arr);          /* arr decays to &arr[0] */
f(&arr[0]);     /* same thing */

But &arr is a pointer to the whole array with type int (*)[10], not int*. Adding 1 to it moves by 10 * sizeof(int).

int arr[10];
int (*pa)[10] = &arr;
pa + 1;          /* address arr + 40 (10 ints) */
&arr[0] + 1;    /* address arr + 4  (1 int)   */

`void *` arithmetic

void *p = ...;
p++;             /* error in standard C; GCC extension treats as 1 byte */
char *cp = p;
cp += n;         /* portable byte arithmetic */

Negative offsets / underflow

int arr[10];
int *p = &arr[0];
p--;            /* UB — underflows below array */

Even computing p - 1 is UB if it goes below the start. p + (- something) follows the same rule.

Pointer-to-pointer

int **pp = ...;
pp + 1;       /* moves by sizeof(int*) */

Each level of indirection peels one type off.

Implementation note — fat pointers

C pointers are usually one machine word. Some safer dialects (CHERI, Cyclone) use fat pointers carrying base + bound + offset. C’s pointer arithmetic rules are designed to be efficient on flat pointers — that’s why one-past-end is allowed and two-past-end is UB.

Counter-example: pointer to outside the array is UB

int a[10];
int b[10];
int *p = a + 12;        /* UB — even forming the pointer */
ptrdiff_t d = b - a;     /* UB — different arrays */

The arrays might be adjacent in memory but the type system treats them as separate objects.

C.16 — Why arrays start from 0

Three arguments — historical, mathematical, mechanical.

Mechanical: pointer arithmetic

a[i] = *(a + i). The first element is at offset 0 from the base. A 1-based system would need *(a + i - 1) everywhere, costing an extra subtraction (or a base-1 adjustment when computing addresses) at every access.

In assembly, an indexed load is MOV reg, [base + index*scale]. The natural identity is base+0.

Mathematical (Dijkstra EWD831, 1982)

Consider 4 ways to write the range “integers from 2 to 5”:

a)  2 ≤ i <  6
b)  1 <  i ≤  5
c)  2 ≤ i ≤  5
d)  1 <  i <  6

Dijkstra argues (a) is best:

Length = upper − lower. Trivially 6 − 2 = 4.
Empty range is [i, i) — no off-by-one.
Adjacent ranges join cleanly: [a, b) ∪ [b, c) = [a, c).
Natural numbers start at 0, not 1 — so the “no values” range is [0, 0), not [1, 0) or [1, 1).

Given a half-open range [0, N), the indices used are 0, 1, ..., N-1. Hence zero-based.

The downside is the off-by-one stigma — for (i = 0; i < N; i++) — but with practice it’s clearer than for (i = 1; i <= N; i++) because i < N lets you read N as the length directly.

Historical

C inherited from B and BCPL. In BCPL, a[i] was literally *(a + i) — base+offset semantics with 0-based as the natural choice. FORTRAN went 1-based; Pascal let you choose; both required extra arithmetic in the compiled code or were tied to less-flexible runtime layouts.

Languages that buck the trend

Lua, Smalltalk, Julia, R, Matlab — 1-based. Pedagogically nicer for some uses (matrix algebra) but pays a cost everywhere else.
Pascal — index range declared by the programmer: var a: array[10..20] of integer;

The non-obvious cost of 1-based

Modular arithmetic loses its elegance. Hash table buckets use h % N, giving 0..N-1. To map that to 1..N you’d need (h % N) + 1. Wrap-around indexing in ring buffers, hash probing, FFT butterflies — all natural in 0-based, awkward in 1-based.

C.17 — Alignment

What alignment is

Every object has an alignment requirement: an integer (always a power of 2) such that the object’s address must be a multiple of it. Loading a misaligned object may be slower, may crash (older ARM, RISC-V without unaligned support), or may simply work (x86) at a small perf penalty.

Why hardware cares

A 64-bit load from memory pulls one cache line (64 B) into L1. If the target spans two cache lines (because the address isn’t 8-aligned), the CPU pulls two lines and stitches them — extra cycles. SIMD instructions (movdqa) require alignment matching the operand size.

C alignment primitives

C11:

#include <stdalign.h>

alignas(16) char buf[64];        /* buf is 16-aligned */
size_t a = alignof(double);      /* alignment requirement of double */

max_align_t in <stddef.h> — the most-strict primitive alignment. malloc guarantees alignof(max_align_t), typically 16 on x86-64.

Beyond max_align_t:

void *p;
posix_memalign(&p, 4096, size);          /* page-aligned */
p = aligned_alloc(64, size);             /* C11, cache-line-aligned */

For aligned_alloc, size must be a multiple of alignment.

Struct alignment

struct s {
    char  a;
    double b;       /* offsetof(b) = 8 — padding inserted */
};
alignof(struct s);   /* 8 — max of member alignments */
sizeof(struct s);    /* 16 — multiple of alignment, so arrays stay aligned */

You can over-align a struct:

struct alignas(64) cacheline_aligned {
    int x;
};                  /* always 64-aligned, sizeof multiple of 64 */

struct counters {
    long a;
    long b;
} c;

If thread A increments c.a and thread B c.b, both fields live in the same 64-byte cache line. Every write triggers a coherency invalidation on the other core. The line ping-pongs between caches — orders of magnitude slowdown.

Fix:

struct counters {
    alignas(64) long a;
    alignas(64) long b;
};

Now each counter has its own cache line.

Unaligned loads — gotcha

char buf[8] = ...;
uint64_t v = *(uint64_t*)buf;          /* may be UB if buf not 8-aligned */

Strict-aliasing aside, the cast is UB on platforms where uint64_t requires 8-alignment. Portable form:

uint64_t v;
memcpy(&v, buf, 8);                    /* compiler optimizes to a load */

The compiler emits the same instruction as the cast on x86; on ARM it emits the safe sequence.

Page alignment

Page size (4 KB typically; 2 MB hugepages, 1 GB gigantic pages) matters for:

mmap (must be page-aligned)
O_DIRECT IO (often page-aligned buffers)
Memory-protect regions (mprotect only on page boundaries)

Counter-example: over-aligning wastes memory

alignas(64) on every field “for safety” can quadruple your struct size. Only over-align where you can prove it matters — measured false sharing, SIMD requirement, hardware constraint.

C.18 — Condition variable vs mutex vs spinlock vs atomic

A hierarchy of synchronization primitives, from lightest to heaviest. Each exists because the next one up has unacceptable cost in its domain.

Atomic

Hardware-level read-modify-write on a single word. No locks, no syscalls, no scheduler involvement.

#include <stdatomic.h>
_Atomic int counter;
atomic_fetch_add(&counter, 1);

Backed by:

x86: LOCK XADD, LOCK CMPXCHG — locks the cache line during the op.
ARM64: LDXR/STXR (load-exclusive/store-exclusive) loop.
RISC-V: LR/SC.

Cost: ~10–30 ns under contention (cache-line bounce), ~5 ns uncontended.

Use for: counters, single-bit flags, lock-free queues (with CAS). Don’t use for: anything that needs multiple coordinated state changes (use a lock).

Spinlock

Thread spins on a CAS until it acquires.

typedef _Atomic int spinlock_t;

void lock(spinlock_t *l) {
    while (atomic_exchange_explicit(l, 1, memory_order_acquire))
        while (atomic_load_explicit(l, memory_order_relaxed))
            __builtin_ia32_pause();    /* x86 PAUSE */
}
void unlock(spinlock_t *l) {
    atomic_store_explicit(l, 0, memory_order_release);
}

The inner pause (or ARM yield) signals SMT/hyperthreading that we’re spinning; the outer exchange is the test-and-set. The “test, test-and-set” pattern (the inner relaxed load) avoids hammering the cache line with writes — only retry the exchange when the spinlock looks free.

Cost: ~5 ns uncontended, infinite if held by a preempted thread on a single CPU.

Use for:

Kernel code where you can’t sleep (interrupt handlers, scheduler).
Very short critical sections (~100 ns) where syscall overhead would dominate.
Lock-free fallback paths.

Don’t use for:

Long critical sections — wastes a CPU.
User-space code with preemption (use mutex with adaptive spinning).

Mutex

Tries a brief spin (the “adaptive” part), then falls back to a syscall that parks the thread until the holder releases. On Linux this is futex (see C++/Low-level sections).

#include <pthread.h>
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&m);
/* ... */
pthread_mutex_unlock(&m);

Cost: ~25 ns uncontended, ~1–5 μs contended (one syscall in each direction).

Use for: anything that may sleep, anything held longer than a few hundred ns, anything where holder may be preempted.

Condition variable

A mutex protects state; a CV waits for state to satisfy a condition.

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  c = PTHREAD_COND_INITIALIZER;
int             ready = 0;

/* consumer */
pthread_mutex_lock(&m);
while (!ready)
    pthread_cond_wait(&c, &m);    /* atomically unlocks m, sleeps */
/* uses shared state, holds m */
pthread_mutex_unlock(&m);

/* producer */
pthread_mutex_lock(&m);
ready = 1;
pthread_cond_signal(&c);
pthread_mutex_unlock(&m);

cond_wait atomically unlocks and sleeps, then reacquires on wake. The while (!ready) is mandatory — spurious wakeups are allowed by POSIX, and the predicate may have already become false again by the time you reacquire.

Use for: producer/consumer, work queues, “wait until X” patterns. Don’t use for: simple flag waits — atomic_int with futex_wait is leaner.

Choosing — decision table

Need	Use
Counter / flag, no other state	`atomic`
Lock-free data structure	`atomic` with CAS
Critical section <100 ns, can’t sleep	spinlock
Critical section >100 ns or may block	mutex
Wait for predicate / event	mutex + CV (or `eventfd`, `futex_wait`)
Many readers, rare writer	rwlock or RCU

Performance summary (typical x86-64)

Op	Latency uncontended	Contended
Cached load	1 ns	—
Atomic increment	5–10 ns	50–200 ns (cache bounce)
Spinlock	5 ns	depends on hold time
Mutex	25 ns	1–5 μs (with syscall)
Condition variable wake	—	5–10 μs (syscall + wake)

Memory order matters

Atomics aren’t enough by themselves — the memory order you specify dictates which other reads/writes can be reordered around them. See the C++ memory model section. For now: acquire on lock, release on unlock are the bread-and-butter.

Counter-example: spinlock under preemption

spin_lock(&L);          /* user thread acquires */
/* preempted! */
spin_lock(&L);          /* another user thread spins until the kernel reschedules the first */

Spins for a full scheduler quantum (1–10 ms) instead of the intended microsecond. Glibc pthread_mutex_t (PTHREAD_MUTEX_ADAPTIVE_NP) detects high uncontended cost and switches to futex_wait after a short spin — that’s why it’s the default for user-space.