TCMalloc Documentation

TCMalloc manages the heap using the following concepts:

• Pages: The heap is divided into pages of a compile-time determined size (e.g., 4KiB, 8KiB, 32KiB, or 256KiB).
• Spans: A Span is a contiguous run of one or more pages. A span can either manage a single large object or a sequence of small objects of a specific size-class.
• Pagemap: A 2-level or 3-level radix tree used to map memory addresses to the Span they belong to, allowing the allocator to identify the size-class or span for any given object address.

For small objects, spans use an unrolled linked list with two-byte indexes to reduce cache misses and improve memory efficiency.

Temeraire is a hugepage-aware page heap for TCMalloc designed to better handle memory backed by hugepages. Its statistics provide a detailed breakdown of how memory is distributed across various caches to avoid breaking up hugepages.

Summary Statistics

The summary shows the number of different sizes of ranges, total MiB available, and total MiB of unmapped ranges.

Each line for a specific number of contiguous pages includes:

• The number of contiguous pages.
• The number of spans of that number of pages.
• The total MiB of that span size that are mapped.
• The cumulative total of the mapped pages.
• The total MiB of that span size that are unmapped.
• The cumulative total of the unmapped pages.

Temeraire is a hugepage-aware allocator designed to optimize memory usage by packing allocations into the smallest possible set of hugepages. It uses a tiered allocation strategy based on request size:

1. Small allocations: Packed into existing, partially empty hugepages using the HugePageFiller.
2. Medium allocations (too large for a single hugepage but not a multiple of one): Best-fit into large HugeRegion slabs (currently 1 GiB) that can cross hugepage boundaries.
3. Large allocations: Rounded up to the nearest hugepage and managed via HugeAllocator or HugeRegion.

Deallocation identifies which tier the object belonged to and marks it as free.

The middle-end acts as the intermediary between the front-end (per-thread/per-CPU caches) and the back-end (pageheap). It consists of two main components:

1. Transfer Cache: A fast array of pointers used to move objects between different CPUs or threads. If the transfer cache cannot satisfy a request or is full, it communicates with the central free list.
2. Central Free List: Manages memory in Spans. It satisfies requests by extracting objects from spans or requesting new spans from the back-end if existing ones are insufficient.

Note: Both the transfer cache and central free list use mutex locks, which introduces serialization costs when accessing them.

There are two distinct projects based on Google's internal TCMalloc:

1. This repository (google/tcmalloc): This is Google's current implementation used in production. It focuses strictly on the memory allocator implementation itself and includes modern optimizations like per-CPU caches, sized delete, and a hugepage-aware backend.

2. gperftools: A community-adopted version that includes the memory allocator plus additional tools like a CPU profiler and a heap checker.

Use this repository if you want the latest implementation used by Google's C++ programs, which is optimized for modern platforms and based on Abseil.

In Per-Thread mode, TCMalloc assigns a thread-local cache to each thread.

• Allocation: Objects are removed from the appropriate size-class linked list in the thread-local cache.
• Deallocation: Objects are prepended to the appropriate size-class linked list.
• Underflow/Overflow: If the cache is empty (underflow) or too full (overflow), TCMalloc interacts with the middle-end to fetch or return batches of objects.
• Thread Exit: When a thread exits, its cached memory is returned to the middle-end.

In Temeraire-enabled TCMalloc, HugeRegion (and HugeRegionSet) is a core component used to manage large allocations that exceed a single hugepage size. It solves the 'trilemma' of supporting arbitrary allocation sizes, backing the heap with hugepages, and minimizing global space overhead.

HugeRegion allows the allocator to use the unused tail of a hugepage from one large allocation as the beginning of another contiguous large allocation. This prevents significant space overhead (up to 100%) that would occur if every allocation larger than a hugepage were forced to round up to a full hugepage boundary.

TCMalloc manages memory using one of two caching modes to avoid lock contention during allocation and deallocation:

• Per-CPU caching (Default): Maintains memory caches local to individual logical cores. This mode is automatically enabled on Linux kernels that support restartable sequences (RSEQ) (Linux kernel 4.18 or newer).
• Per-thread caching: Maintains memory caches local to each application thread. TCMalloc reverts to this mode if RSEQ is unavailable on the host system.

The back-end manages large unused memory chunks, fetches memory from the OS, and returns unused memory to the OS. There are two types:

1. Legacy Pageheap: Manages memory in chunks of TCMalloc page sizes. It uses an array of free lists where the $k$-th entry holds runs of $k$ pages (up to 256 pages). For runs $\ge 256$ pages, a single free list is used.
2. Hugepage Aware Allocator (HPAA): Designed to hold memory in hugepage-sized chunks (e.g., 2MiB on x86) to reduce TLB misses. It uses three caches:
   • Filler Cache: Holds hugepages with some memory already allocated; handles requests smaller than a hugepage.
   • Region Cache: Handles allocations larger than a hugepage by allowing them to straddle multiple hugepages.
   • Hugepage Cache: Handles large allocations of at least a hugepage size.

TCMalloc implements per-CPU caches using the Linux kernel's restartable sequences (rseq(2)) mechanism. This allows TCMalloc to execute code regions atomically with respect to other threads on the same CPU by avoiding expensive atomic operations in the common case.

If a thread is preempted, interrupted by a signal, or migrated to a different core while executing an rseq sequence, the kernel aborts the sequence and restarts it. To support this, TCMalloc code paths are designed so that the entire sequence—except for the final 'commit' store to memory—can be safely restarted. This design optimizes performance by staying on the same core and avoiding atomics, accepting the rare cost of a restart when preemption occurs.