Multicore, SMP, NUMA & Memory Models

Symmetric Multi-Processing (SMP) means multiple CPU cores share a single physical address space and have equal, symmetric access to all of main memory. Every core can reach every byte of RAM in the same number of bus cycles. There is one operating-system instance managing all cores — contrast this with older systems where multiple CPUs each ran their own OS copy.

The word symmetric is key. No core is privileged. The scheduler can run any thread on any core. Memory latency from any core to any RAM bank is (approximately) the same.

In SMP, all cores typically sit on a shared system bus or a crossbar interconnect that connects them to a unified memory controller. The interconnect arbitrates who gets to talk to memory when, introduces a small amount of contention, but keeps the programming model simple: memory address X means the same thing to Core 0 and Core 7.

Why does this matter for the kernel? The kernel's per-CPU variables, this_cpu_read(), get_cpu(), and the entire concept of CPU-local data exist specifically because putting data on a single shared bus creates a bottleneck. When every core hammers the same cache line, the bus saturates. Per-CPU design is the answer: each core has its own copy of hot data, accessed without coordination.

Real topology exploration:

# See how many CPUs and how they're laid out
nproc                          # total logical CPUs
lscpu                          # topology: sockets, cores/socket, threads/core
cat /sys/devices/system/cpu/cpu0/topology/core_id
cat /sys/devices/system/cpu/cpu0/topology/physical_package_id

# On Linux, the kernel exposes per-CPU variables via /sys
ls /sys/devices/system/cpu/

As core counts grew into the hundreds, the single shared bus became a fatal bottleneck. The solution is NUMA (Non-Uniform Memory Access): partition the machine into nodes, each containing a subset of CPU cores and a local bank of RAM. Cores in a node access their local RAM fast. Accessing another node's RAM requires traversing an inter-node interconnect (Intel's QPI/UPI, AMD's Infinity Fabric, etc.) — this is slower, sometimes 2–4× slower.

The memory is still a unified address space. Any core can still read or write any address — it just costs more if that address lives in a remote node. The OS sees one big address space; the hardware (and the OS scheduler) are aware of the topology.

A concrete picture: A 4-socket server with 16 cores per socket and 64 GB RAM per socket has 4 NUMA nodes. Core 0 (node 0) can access the 64 GB on node 0 in ~60 ns, but accessing node 3's memory takes ~200 ns. If the scheduler places a thread on node 0 but its data is on node 3, you're paying that penalty on every cache miss.

NUMA in the Linux kernel: The kernel has a full NUMA-aware memory allocator (NUMA_BALANCING, cpuset, numactl). alloc_pages_node(nid, ...) explicitly allocates from a specific node. The scheduler tries to keep threads near their memory. migrate_pages() can move pages to a better node.

Exploring NUMA topology:

# Show NUMA topology
numactl --hardware
# Output example:
# available: 2 nodes (0-1)
# node 0 cpus: 0 1 2 3 4 5 6 7
# node 0 size: 32105 MB
# node 0 free: 28000 MB
# node distances:
# node   0   1
#   0:  10  21
#   1:  21  10

# Allocate memory on a specific NUMA node
numactl --membind=0 ./my_program

# See NUMA statistics
cat /proc/zoneinfo | grep -A5 'Node 0'

Modern CPUs have a hierarchy of caches between the core and main memory: L1 (fastest, smallest, ~32 KB, ~4 cycles), L2 (~256 KB, ~12 cycles), L3 (shared among cores on same socket, ~8–32 MB, ~40 cycles), and then main memory (~100+ cycles). Without caches, a 3 GHz CPU would stall waiting for RAM on nearly every instruction.

Here's where the fun begins: if two cores each have a cached copy of the same memory address, and one of them modifies it, what does the other see?

Without any mechanism: stale data. Core 1 reads x = 5 into its L1 cache. Core 2 writes x = 42. Core 1 still reads 5 from its L1 cache — a silent correctness bug.

Cache coherence is the hardware guarantee that all cores agree on the current value of any memory location. It does NOT mean they agree on the order of operations (that's the memory model, covered next) — just that no core is permanently stuck reading a stale value.

Coherence is implemented by a cache coherence protocol that runs in hardware, typically as a finite state machine on each cache line (64 bytes on x86). The most common family of protocols is MESI.

// This program is SAFE on any coherent architecture.
// Core A and Core B will never disagree about x indefinitely.
// (Whether B sees the write immediately is a memory MODEL question, not coherence.)

// Core A (thread A):
int x = 0;       // shared
void writer() {
    x = 42;      // hardware will eventually invalidate other caches
}

// Core B (thread B):
void reader() {
    while (x == 0) ; // spin until we see the write
    // On a coherent CPU, this loop WILL terminate.
    // How quickly depends on the memory model + barriers.
    printf("%d\n", x); // prints 42
}

MESI is the dominant cache coherence protocol. Each cache line is in exactly one of four states on each core's cache:

• M (Modified): This cache has the only valid copy, and it differs from main memory. Only one core can hold M at a time.
• E (Exclusive): This cache has the only copy, and it matches main memory. One core holds it clean.
• S (Shared): Multiple caches may hold valid copies, all matching main memory. Any core can read; none can write without upgrading.
• I (Invalid): This cache line is stale or absent. Must fetch before use.

The protocol in action:

1. Core A reads address X → cache miss → fetches from memory → enters state E (only one has it).
2. Core B reads address X → Core A's E downgrades to S, Core B enters S. Now both have valid copies.
3. Core A wants to write → sends Invalidate message on the bus → Core B's line transitions to I → Core A upgrades to M → writes locally. Core B's cache is now stale.
4. Core B reads X again → cache miss (line is I) → Core A must write-back its M line to memory (or forward directly) → Core B fetches the new value → both enter S.

This bus-snoop mechanism ensures coherence. On large NUMA machines, a directory-based protocol is used instead of broadcasting invalidates (too much traffic), but the state machine logic is similar.

Cache line false sharing is a famous performance pathology: two unrelated variables sitting in the same 64-byte cache line. Core A writes a, Core B writes b. Even though they're logically independent, every write by A invalidates B's line and vice versa — the protocol treats the entire 64-byte unit as the coherence granule. The fix: align hot per-CPU data to cache line boundaries (__cacheline_aligned in kernel code).

// Demonstrating false sharing vs. padding
// Compile: gcc -O2 -pthread false_sharing.c -o false_sharing

#include <pthread.h>
#include <stdint.h>
#include <stdio.h>

#define ITERS 100000000

// BAD: a and b share a cache line
struct bad {
    volatile long a;
    volatile long b;
} shared_bad;

// GOOD: padded to separate cache lines (64 bytes each)
struct good {
    volatile long a;
    char pad[56];   // pad to 64 bytes total
    volatile long b;
} shared_good;

void *inc_a_bad(void *_)  { for(long i=0;i<ITERS;i++) shared_bad.a++;  return NULL; }
void *inc_b_bad(void *_)  { for(long i=0;i<ITERS;i++) shared_bad.b++;  return NULL; }
void *inc_a_good(void *_) { for(long i=0;i<ITERS;i++) shared_good.a++; return NULL; }
void *inc_b_good(void *_) { for(long i=0;i<ITERS;i++) shared_good.b++; return NULL; }

// Time the bad and good versions — good is typically 3-6x faster
// because cores A and B never fight over a shared cache line.

Cache coherence answers: "Will I ever see a stale value forever?" Answer: no.

Memory consistency answers a harder question: "In what order do memory operations performed by different cores become visible to each other?"

This turns out to be deeply non-obvious, because CPUs and compilers both reorder operations for performance — and they're allowed to, within the rules of the memory model.

Sequential Consistency (SC) is the ideal: the result of any execution is as if all operations from all cores were interleaved in some total global order, with each core's operations appearing in program order within that interleaving. This is what most programmers intuitively assume. It's also expensive — enforcing it requires significant hardware coordination on every memory operation.

Total Store Order (TSO) is what x86 implements. Cores have a store buffer: when a core writes, the write goes into the buffer first and drains to the cache later. Reads bypass the store buffer (a core can read its own not-yet-drained writes). The effect: stores can appear delayed to other cores, but loads cannot be reordered past loads, and stores cannot be reordered past stores (within a single core). Other cores may see your writes in a slightly delayed but consistent order. TSO is stronger than fully relaxed but weaker than SC.

Relaxed / Weak models (ARM, RISC-V, POWER) allow almost any reordering: loads can pass loads, stores can pass stores, loads can pass stores. The hardware extracts maximum parallelism but places the burden on the programmer to insert explicit memory barriers wherever ordering matters.

Why does this matter in practice? A classic example: the dekker/peterson mutual exclusion algorithm works correctly under SC but is broken under TSO without barriers. The Linux kernel targets all these architectures — so every synchronization primitive must explicitly specify the ordering it requires, using portable barrier macros.

// Memory model illustration: Dekker's test
// Two cores, two flags.
// Under SC: the assertion never fires.
// Under TSO (x86 without fences): the assertion CAN fire!

// Core 0:              Core 1:
flag0 = 1;             flag1 = 1;
if (flag1 == 0)        if (flag0 == 0)
    critical_section();    critical_section(); // BOTH enter!

// WHY: x86 TSO allows stores to sit in the store buffer.
// Core 0 writes flag0=1 (in buffer), reads flag1=0 (not yet visible).
// Core 1 writes flag1=1 (in buffer), reads flag0=0 (not yet visible).
// Both see the other's flag as 0, both enter. Race condition!

// Fix with x86 MFENCE (full memory fence):
// flag0 = 1;
// asm volatile("mfence" ::: "memory");  // drain store buffer
// if (flag1 == 0) ...   // now sees flag1=1 if Core 1 already set it

A memory barrier (also called a fence) is an instruction that constrains the reordering of memory operations across it. They are the programmer's knob for controlling ordering in a relaxed memory model.

There are three fundamental kinds:

• Store barrier (wmb / sfence): All stores before the barrier are visible to other cores before any store after the barrier. Use when: writing a data structure, then setting a flag that signals "data is ready."
• Load barrier (rmb / lfence): All loads before the barrier complete before any load after it. Use when: reading a flag that signals data is ready, then reading the data itself.
• Full barrier (mb / mfence): Combines both. All prior loads and stores complete before any subsequent loads or stores. Most conservative, most expensive.

Linux kernel barrier macros (architecture-portable):

• smp_mb() — full barrier (on SMP; nop on UP)
• smp_rmb() — read barrier
• smp_wmb() — write barrier
• smp_store_release(ptr, val) — store + implicit release barrier
• smp_load_acquire(ptr) — load + implicit acquire barrier

Acquire/Release semantics (C11, C++11, Linux): A release store ensures all prior operations are visible before the store. An acquire load ensures the load completes before subsequent operations. Pairing a release store with an acquire load creates a happens-before relationship — exactly what a mutex unlock/lock needs.

On x86 TSO, smp_rmb() and smp_wmb() compile to nothing (x86 already provides these orderings for free from TSO); only smp_mb() requires an MFENCE. On ARM/RISC-V, all three emit real instructions (DMB, FENCE). This is why kernel code must use the portable macros — never raw asm("mfence").

// Correct producer/consumer with barriers (kernel style)
// Producer writes data, then publishes flag.
// Consumer reads flag, then reads data.

// Without barriers on ARM/RISC-V: consumer can read data
// BEFORE seeing the flag update — data is garbage.

// Producer (Core A):
void publish(struct item *item, volatile int *ready) {
    item->data = 42;        // write data
    item->more = 99;
    smp_wmb();              // store barrier: data writes drain before flag
    *ready = 1;             // publish flag
}

// Consumer (Core B):
void consume(struct item *item, volatile int *ready) {
    while (!READ_ONCE(*ready)) cpu_relax(); // spin on flag
    smp_rmb();              // load barrier: flag load complete before data loads
    int d = item->data;     // guaranteed to see 42
    int m = item->more;     // guaranteed to see 99
}

// Modern equivalent using acquire/release (preferred in new kernel code):
void publish_v2(struct item *item, volatile int *ready) {
    item->data = 42;
    smp_store_release(ready, 1); // release: all prior stores visible first
}
void consume_v2(struct item *item, volatile int *ready) {
    while (!smp_load_acquire(ready)) cpu_relax(); // acquire: subsequent loads ordered after
    int d = item->data; // safe: happens-after the release store
}

A read-modify-write operation like x++ looks like one statement but is actually three micro-operations: load x, add 1, store x. On a multi-core machine, another core can interleave between the load and the store — this is a data race, and the result is unpredictable.

Atomic instructions make the entire read-modify-write indivisible (atomic) at the hardware level.

x86 mechanisms:

• The LOCK prefix on instructions like LOCK XADD, LOCK CMPXCHG, LOCK INC makes them atomic. It causes the CPU to assert its bus lock (or lock the cache line) for the duration, preventing any other core from accessing that cache line between the read and the write.
• XCHG is implicitly locked on x86 (always atomic).
• CMPXCHG (Compare-and-Exchange) is the primitive for lock-free algorithms: "if the value is X, atomically set it to Y, else tell me the current value." This is the foundation of CAS loops.

ARM mechanisms: LDREX/STREX (ARMv7) and LDXR/STXR (ARMv8/AArch64) implement Load-Link/Store-Conditional (LL/SC). LDXR loads a value and marks the cache line as "reserved." STXR attempts to store; it succeeds only if nothing has modified the cache line since the LDXR. If it fails (another core modified it), you retry the loop. LL/SC avoids the ABA problem that CAS can suffer from.

RISC-V: Also uses LL/SC via LR.W/SC.W. Additionally defines AMO (Atomic Memory Operation) instructions like AMOADD.W, AMOSWAP.W with ordering suffixes (.aq, .rl) baked in.

In the Linux kernel: atomic_t wraps these. atomic_add(), atomic_cmpxchg(), atomic_fetch_add() expand to the appropriate locked instructions on x86 or LL/SC loops on ARM/RISC-V. The kernel also has atomic64_t, atomic_long_t, and the newer atomic_*_relaxed() / atomic_*_acquire() / atomic_*_release() variants that control ordering explicitly.

// x86-64 assembly: atomic increment via LOCK XADD
// Equivalent to atomic_add(1, &counter)

// In AT&T syntax:
// lock xaddl %eax, (%rdi)   ; atomically: tmp=*rdi; *rdi+=eax; eax=tmp

// C with inline asm (educational — use atomic_t in real kernel code):
static inline int atomic_inc_and_return(volatile int *p) {
    int old = 1;
    asm volatile("lock; xaddl %0, %1"
                 : "+r"(old), "+m"(*p)
                 : : "memory");
    return old; // returns value BEFORE increment
}

// ARM64: LL/SC loop for atomic add
// ldxr  w1, [x0]      ; load-exclusive: w1 = *x0, mark reservation
// add   w1, w1, #1    ; w1 = w1 + 1
// stxr  w2, w1, [x0]  ; store-exclusive: *x0 = w1 IF still reserved
//                     ; w2 = 0 on success, 1 on failure
// cbnz  w2, <retry>   ; retry if failed

// ARM64 LSE (Large System Extension, ARMv8.1+): single instruction
// ldadd x1, x2, [x0]  ; atomically: x2 = *x0; *x0 += x1  (with acquire)

// Linux kernel usage:
#include <linux/atomic.h>
atomic_t counter = ATOMIC_INIT(0);
atomic_inc(&counter);                    // atomic, ordered
int v = atomic_inc_return(&counter);     // atomic add+read
if (atomic_cmpxchg(&counter, 5, 10)==5) // CAS: if ==5, set to 10
    pr_info("swapped!");

To understand why barriers are not free, you need to see the microarchitectural structures they flush or drain.

Store buffer: When a core executes a store, it doesn't immediately push it to the cache (that would require winning a bus arbitration, sending invalidate messages, waiting for acknowledgments). Instead, it queues the store in a small FIFO buffer local to the core. Later, when the bus is free, stores drain from the buffer into the cache. Reads from the same core can "bypass" the store buffer (forwarding), so the core sees its own writes immediately. Other cores cannot see buffered stores — they see them only after the store drains.

Invalidate queue: When a core receives an invalidate request for a cache line, it might not be able to process it immediately (the cache pipeline is busy). It queues the invalidate. The sender's protocol acknowledgment goes back immediately (to keep the protocol moving), but the cache line isn't actually invalidated until the queue is drained. This means a core might read a not-yet-invalidated line even though the protocol has acknowledged the invalidate.

What a write barrier (wmb) does: It stalls the core until the store buffer is drained. Every pending store is committed to the cache before the barrier returns. This is cheap on x86 TSO (the store buffer drains in order naturally for stores-to-stores), expensive on weak-order CPUs that batch stores aggressively.

What a read barrier (rmb) does: It stalls until the invalidate queue is drained. Every pending invalidate is applied before the barrier returns. Now subsequent loads will see the correct (invalidated, fresh) values.

The cost: A full mfence on x86 Skylake takes ~80–150 cycles. An sfence is cheaper. This is why kernel developers agonize over barrier placement: too few and you have bugs; too many and you've destroyed your throughput. The READ_ONCE() / WRITE_ONCE() macros (which just prevent compiler reordering via volatile-cast, without hardware barriers) exist for cases where you need to prevent compiler optimization but the hardware ordering is already sufficient.

// READ_ONCE / WRITE_ONCE: compiler barriers only, zero hardware cost
// Use when: preventing compiler from caching a value in a register
// (e.g., polling a flag in a loop)

#include <linux/compiler.h>

// BAD: compiler may hoist this load out of the loop entirely
void bad_poll(volatile int *flag) {
    while (*flag == 0) ; // 'volatile' forces re-read here, but...
}

// CORRECT kernel idiom:
void good_poll(int *flag) {
    while (READ_ONCE(*flag) == 0)
        cpu_relax(); // hints the CPU this is a spin-wait (saves power, helps HT)
}

// READ_ONCE definition (simplified from include/linux/compiler.h):
// #define READ_ONCE(x)  (*(const volatile typeof(x) *)&(x))

// This is NOT a memory barrier. It prevents:
// 1. Compiler from hoisting the load out of the loop
// 2. Compiler from reading x twice and tearing a word
// It does NOT prevent hardware reordering. For that, use smp_load_acquire().

Compare-and-Swap (CAS) is the atomic primitive behind most lock-free data structures. The operation is: "Atomically: if *ptr == expected, then set *ptr = desired and return true; otherwise return false and load the current value into expected."

CAS enables the classic CAS loop pattern for lock-free update:

do {
    old = load(ptr);
    new = compute(old);
} while (!CAS(ptr, old, new));

If another thread modifies ptr between our load and CAS, the CAS fails and we retry. No lock is ever held.

The ABA Problem: A subtle CAS pitfall. Thread A reads ptr = A. Thread B changes it A → B → A. Thread A's CAS succeeds (sees A as expected), but the state of the world has changed in a way A didn't notice. Solution: use a versioned/tagged pointer where the version number is incremented on every write. LL/SC avoids ABA naturally because it tracks the access to the cache line, not just the value.

Load-Link / Store-Conditional (LL/SC) on ARM/RISC-V: The load-exclusive marks the cache line. Any write to that line (by any core) clears the reservation. The store-conditional checks the reservation and fails if cleared. This is not CAS — the SC can fail spuriously (e.g., a context switch, or cache pressure evicting the line) even if nobody wrote to it. Correct LL/SC code must handle spurious failures by retrying.

In the Linux kernel: cmpxchg() on x86, cmpxchg_relaxed() / cmpxchg_acquire() / cmpxchg_release() for ordered variants. The RCU (Read-Copy-Update) mechanism, which is one of Linux's most important scalability innovations, is built on cmpxchg and careful barrier placement rather than locks.

// Lock-free stack using CAS (illustrative, not production-ready)
// This is the pattern behind linux/llist.h (lock-less linked list)

#include <stdatomic.h>   // C11 atomics (userspace illustration)

struct node {
    int val;
    struct node *next;
};

_Atomic(struct node *) stack_top = NULL;

void push(struct node *n) {
    struct node *top;
    do {
        top = atomic_load_explicit(&stack_top, memory_order_relaxed);
        n->next = top;
    } while (!atomic_compare_exchange_weak_explicit(
        &stack_top, &top, n,
        memory_order_release,   // success: release (new node visible before pointer)
        memory_order_relaxed)); // failure: no ordering needed, just retry
}

struct node *pop(void) {
    struct node *top, *next;
    do {
        top = atomic_load_explicit(&stack_top, memory_order_acquire);
        if (!top) return NULL;
        next = top->next;
    } while (!atomic_compare_exchange_weak_explicit(
        &stack_top, &top, next,
        memory_order_acquire,
        memory_order_relaxed));
    return top;
    // NOTE: This has ABA if nodes are reused. Production code needs versioned pointers
    //       or hazard pointers. Linux llist.h uses a simpler push-only lock-free list.
}

NUMA isn't just a topology curiosity — it fundamentally changes how you should write and tune concurrent code on modern servers. The 2–4× latency penalty for remote memory access can devastate performance for memory-intensive workloads.

The Linux kernel's NUMA strategies:

1. First-touch allocation policy: By default, Linux allocates a physical page from the NUMA node of the thread that first touches (writes to) it. This means: the thread that initializes a data structure determines where it physically lives. If you later access it from a different node, you pay the remote tax.

2. Per-CPU data (DEFINE_PER_CPU): For hot kernel data structures, Linux keeps a copy per logical CPU. No sharing, no coherence traffic, no false sharing. The this_cpu_ptr() / per_cpu() API gives you the local copy. The scheduler statistics, memory allocator state, and RCU grace-period tracking are all per-CPU.

3. Per-node allocation: alloc_pages_node(nid, gfp, order) explicitly allocates from node nid. The SLUB allocator has per-node magazines. Network buffers allocated on the node where the NIC lives avoid expensive cross-node copies.

4. NUMA balancing (AutoNUMA): Linux 3.8+ has automatic NUMA balancing. It periodically unmaps pages, causes faults on access, detects which node the accessing thread is on, and migrates pages toward the accessing thread if beneficial. numastat, numactl --show, and /proc/sys/kernel/numa_balancing expose this.

5. CPU affinity and cpusets: taskset (userspace) and cpuset cgroups pin threads to specific CPU sets, which implicitly keeps them on specific NUMA nodes. Kernel threads use kthread_bind(). HPC and real-time workloads routinely pin critical threads to cores and memory on the same node.

/* Kernel-style per-CPU counter (from kernel source patterns) */
#include <linux/percpu.h>
#include <linux/cpumask.h>

/* Declare a per-CPU variable */
DEFINE_PER_CPU(long, my_counter);

void increment_counter(void) {
    /* this_cpu_inc is lockless: we only touch OUR cpu's copy */
    this_cpu_inc(my_counter);
}

long sum_all_counters(void) {
    long total = 0;
    int cpu;
    for_each_possible_cpu(cpu)
        total += per_cpu(my_counter, cpu);
    return total;
}

/* 
 * Userspace NUMA allocation (via numaif.h / libnuma):
 * void *p = numa_alloc_onnode(size, node_id);
 *
 * Check which node a page is on:
 * move_pages(0, 1, &ptr, NULL, &node_out, 0);
 */