Virtual memory, pages and the TLB

Every address a program uses is virtual. The processor translates it to a physical address through page tables that the kernel maintains for each process. Memory is managed in pages, 4 KB by default on x86-64 Linux. The translation gives each process its own address space, lets the kernel put pages anywhere in physical memory, and enforces permissions.

On x86-64 the page tables have four levels (five on systems that enable larger address spaces). Translating an address from scratch means reading one entry at each level: four dependent memory reads before the actual load can begin.

To avoid that on every access, the core caches recent translations in the translation lookaside buffer. There are small, fast first-level TLBs for data and instructions and a larger second-level TLB, with on the order of a thousand to a few thousand entries in total on current cores.

A TLB hit costs essentially nothing extra. A miss triggers a page walk in hardware. The walk's reads go through the data caches, so for a recently walked region they may hit L1 or L2; for a large, randomly accessed region they miss too, and the walk can cost as much as a memory access, before the access itself.

The amount of memory the TLB can cover is entries times page size. With roughly 1,500 second-level entries and 4 KB pages, that is about 6 MB. A process that touches a 2 GB book randomly is far beyond that: most accesses to cold parts of it need a page walk as well as a cache miss.

That is the problem huge pages solve. With 2 MB pages, the same number of entries covers about 3 GB; with 1 GB pages, more than any process needs. Page walks almost disappear, and the walk that does happen is one level shorter.

• Explicit huge pages (hugetlbfs). Reserve a pool at boot (hugepages= on the kernel command line, or vm.nr_hugepages), then map from it with mmap(MAP_HUGETLB) or files in a hugetlbfs mount. Predictable: the pages are reserved, contiguous and never split. This is what latency-sensitive systems generally use for their big preallocated regions.
• Transparent huge pages (THP). The kernel promotes suitably aligned anonymous memory to 2 MB pages automatically, and a background thread (khugepaged) collapses small pages into huge ones. Convenient, but the work happens at times you do not choose: compaction to find a free 2 MB region can stall an allocation, and collapsing scans memory in the background. Many trading setups set THP to madvise (only regions that ask for it with madvise(MADV_HUGEPAGE)) or never, and use explicit huge pages instead.

• Reservation. Explicit huge pages are taken from memory at boot whether used or not, and allocation fails rather than falling back if the pool is empty.
• Granularity. Memory is allocated, faulted and freed 2 MB at a time. Touching one byte of a huge page faults in all of it.
• Fragmentation. After a machine has been up for a long time, finding contiguous 2 MB regions for new huge pages may be impossible, which is another reason to reserve at boot.
• Not a fix for cache misses. Huge pages remove translation misses, not data misses. If the book is accessed randomly, the data still misses in cache.

When the kernel changes or removes a mapping (munmap, mprotect, page migration, memory being returned by free), every core that might hold the old translation must flush it. The kernel sends an inter-processor interrupt to those cores: a TLB shootdown. Each interrupted core stops what it is doing to handle it. A latency-critical thread on an isolated core can be hit by shootdowns caused by another thread in the same process unmapping memory, which is one more reason to map everything at start-up and never unmap on a live system.