Why TLB Matters: Unlocking Linux Kernel Performance

Virtual Address Translation Basics

Virtual vs Physical Addresses

Physical addresses refer to actual RAM locations. Virtual addresses are an OS‑provided abstraction that gives each process a contiguous address space starting at zero. The MMU translates a virtual address to a physical address using page tables.

Page Table Structure

In a 32‑bit system with 4 KB pages the high 20 bits form the Virtual Page Number (VPN) and the low 12 bits are the page offset. The VPN indexes the page table to obtain a Physical Frame Number (PFN); the PFN combined with the offset yields the final physical address.

Modern 64‑bit systems use a multi‑level hierarchy (PGD → PUD → PMD → PTE) to keep the page‑table footprint small.

Performance Impact of Page‑Table Walks

Each translation normally requires a memory access to the page table, which is orders of magnitude slower than CPU arithmetic. Frequent walks become a bottleneck for memory‑intensive workloads.

Translation Lookaside Buffer (TLB)

What is the TLB?

The TLB is a small, fast cache inside the MMU that stores a subset of recent page‑table entries. By caching virtual‑to‑physical mappings it eliminates most page‑table walks.

Operation

When the CPU issues a memory request the MMU first probes the TLB:

TLB hit : the physical address is obtained in a few clock cycles.

TLB miss : hardware (x86) or the OS (RISC) walks the page tables, fills the TLB with the new translation, and then proceeds with the access.

TLB Entry Fields

Virtual Page Number (VPN)

Physical Frame Number (PFN)

Valid bit

Tag bits (optional for finer matching)

Accessed bit (used by the OS for replacement heuristics)

Dirty bit (indicates modified data)

TLB Management Mechanisms

Flush Triggers

TLB entries must be invalidated whenever the underlying page table changes – e.g., memory allocation, deallocation, protection changes, context switches, or process termination. Stale entries would cause incorrect physical accesses.

Linux TLB Flush APIs

flush_tlb_all()

– flushes every TLB entry on all CPUs (global page‑table changes). flush_tlb_mm(struct mm_struct *mm) – flushes entries belonging to a specific address space (used during fork/exec).

flush_tlb_range(struct vm_area_struct *vma, unsigned long start, unsigned long end)

– flushes a contiguous virtual‑address range (used for munmap).

flush_tlb_page(struct vm_area_struct *vma, unsigned long addr)

– flushes a single page, typically from a page‑fault handler.

Synchronization Across Cores and Devices

Each core has its own TLB. When one core updates a page‑table entry, other cores must either be notified via inter‑processor interrupts or rely on hardware coherence protocols (e.g., bus sniffing, MESI) to invalidate outdated entries. The same issue appears in CPU‑GPU shared virtual memory; inconsistent TLB entries cause rendering errors.

Hardware‑Managed vs Software‑Managed TLB

x86 (hardware‑managed)

On x86 the hardware automatically walks the page tables on a miss and fills the TLB. The OS can explicitly invalidate entries with the INVLPG instruction or by reloading the CR3 register, which flushes all non‑global entries.

RISC (software‑managed, e.g., MIPS, Alpha, LoongArch)

These architectures raise an exception on a miss. The OS handler walks the page tables in software and inserts the translation into the TLB, providing greater flexibility for real‑time or embedded workloads.

Case Study: Sequential vs Random Memory Access

The following program allocates a 256 MiB buffer (4 KB pages) and measures the time for two access patterns. Sequential access walks the buffer page‑by‑page, exhibiting high spatial locality; random access picks a page index with rand() for each iteration.

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define MEM_SIZE (256*1024*1024)
#define PAGE_SIZE 4096
static inline long get_current_time(void) {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec * 1000000L + tv.tv_usec;
}
void test_sequential(void) {
    char *mem = malloc(MEM_SIZE);
    long start = get_current_time();
    for (int i = 0; i < MEM_SIZE; i += PAGE_SIZE) {
        mem[i] = 1;
    }
    long end = get_current_time();
    printf("Sequential access time: %ld µs
", end - start);
    free(mem);
}
void test_random(void) {
    char *mem = malloc(MEM_SIZE);
    long start = get_current_time();
    for (int i = 0; i < MEM_SIZE; i += PAGE_SIZE) {
        int idx = rand() % MEM_SIZE;
        mem[idx] = 1;
    }
    long end = get_current_time();
    printf("Random access time: %ld µs
", end - start);
    free(mem);
}
int main(void) {
    printf("======= TLB Performance Comparison: Sequential vs Random =======
");
    test_sequential();
    test_random();
    return 0;
}

Running the program with gcc -O0 and measuring perf stat -e dTLB-loads,dTLB-load-misses shows a near‑perfect hit rate (95‑99 %) for the sequential run and a dramatically higher miss count for the random run. Execution time for the random pattern is typically 3‑10× larger because each miss forces a multi‑level page‑table walk.

Optimization Guidelines

Maximize spatial locality (e.g., process data sequentially) to keep TLB hit rates high.

Use large pages (2 MB or 1 GB) to reduce the number of required TLB entries.

Minimize unnecessary context switches; on CPUs with PCID, a context switch can be handled by changing the PCID instead of flushing the entire TLB.

On RISC systems, tailor the software TLB‑miss handler to prioritize latency‑critical mappings.