1# Glossary 2 3This page describes some core terminology used in PartitionAlloc. 4A weak attempt is made to present terms "in conceptual order" s.t. 5each term depends mainly upon previously defined ones. 6 7* **Partition**: A heap that is separated and protected both from other 8 partitions and from non-PartitionAlloc memory. Each partition holds 9 multiple buckets. 10 11*** promo 12**NOTE**: In code (and comments), "partition," "root," and even 13"allocator" are all conceptually the same thing. 14*** 15 16## Pages 17 18* **System Page**: A memory page defined by the CPU/OS. Commonly 19 referred to as a "virtual page" in other contexts. This is typically 20 4KiB, but it can be larger. PartitionAlloc supports up to 64KiB, 21 though this constant isn't always known at compile time (depending 22 on the OS). 23* **Partition Page**: The most common granularity used by 24 PartitionAlloc. Consists of exactly 4 system pages. 25* **Super Page**: A 2MiB region, aligned on a 2MiB boundary. Not to 26 be confused with OS-level terms like "large page" or "huge page", 27 which are also commonly 2MiB. These have to be fully committed / 28 uncommitted in memory, whereas super pages can be partially committed 29 with system page granularity. 30* **Extent**: An extent is a run of consecutive super pages (belonging 31 to a single partition). Extents are to super pages what slot spans are 32 to slots (see below). 33 34## Slots and Spans 35 36* **Slot**: An indivisible allocation unit. Slot sizes are tied to 37 buckets. For example, each allocation that falls into the bucket 38 (224, 256] would be satisfied with a slot of size 256. This 39 applies only to normal buckets, not to direct map. 40* **Slot Span**: A run of same-sized slots that are contiguous in 41 memory. Slot span size is a multiple of partition page size, but it 42 isn't always a multiple of slot size, although we try hard for this 43 to be the case. 44 * **Small Bucket**: Allocations up to 4 partition pages. In these 45 cases, slot spans are always between 1 and 4 partition pages in 46 size. For each slot span size, the slot span is chosen to minimize 47 number of pages used while keeping the rounding waste under a 48 reasonable limit. 49 * For example, for a slot size 96, 64B waste is deemed acceptable 50 when using a single partition page, but for slot size 51 384, the potential waste of 256B wouldn't be, so 3 partition pages 52 are used to achieve 0B waste. 53 * PartitionAlloc may avoid waste by lowering the number of committed 54 system pages compared to the number of reserved pages. For 55 example, for the slot size of 896B we'd use a slot span of 2 56 partition pages of 16KiB, i.e. 8 system pages of 4KiB, but commit 57 only up to 7, thus resulting in perfect packing. 58 * **Single-Slot Span**: Allocations above 4 partition pages (but 59 ≤`kMaxBucketed`). This is because each slot span is guaranteed to 60 hold exactly one slot. 61 * Fun fact: there are sizes ≤4 partition pages that result in a 62 slot span having exactly 1 slot, but nonetheless they're still 63 classified as small buckets. The reason is that single-slot spans 64 are often handled by a different code path, and that distinction 65 is made purely based on slot size, for simplicity and efficiency. 66 67## Buckets 68 69* **Bucket**: A collection of regions in a partition that contains 70 similar-sized objects. For example, one bucket may hold objects of 71 size (224, 256], another (256, 320], etc. Bucket size 72 brackets are geometrically spaced, 73 [going up to `kMaxBucketed`][max-bucket-comment]. 74 * Plainly put, all slots (ergo the resulting spans) of a given size 75 class are logically chained into one bucket. 76 77 79 80* **Normal Bucket**: Any bucket whose size ceiling does not exceed 81 `kMaxBucketed`. This is the common case in PartitionAlloc, and 82 the "normal" modifier is often dropped in casual reference. 83* **Direct Map (Bucket)**: Any allocation whose size exceeds `kMaxBucketed`. 84 85## Other Terms 86 87* **Object**: A chunk of memory returned to the allocating invoker 88 of the size requested. It doesn't have to span the entire slot, 89 nor does it have to begin at the slot start. This term is commonly 90 used as a parameter name in PartitionAlloc code, as opposed to 91 `slot_start`. 92* **Thread Cache**: A [thread-local structure][pa-thread-cache] that 93 holds some not-too-large memory chunks, ready to be allocated. This 94 speeds up in-thread allocation by reducing a lock hold to a 95 thread-local storage lookup, improving cache locality. 96* **Pool**: A large (and contiguous on 64-bit) virtual address region, housing 97 super pages, etc. from which PartitionAlloc services allocations. The 98 primary purpose of the pools is to provide a fast answer to the 99 question, "Did PartitionAlloc allocate the memory for this pointer 100 from this pool?" with a single bit-masking operation. 101 * The regular pool is a general purpose pool that contains allocations that 102 aren't protected by BackupRefPtr. 103 * The BRP pool contains all allocations protected by BackupRefPtr. 104 * [64-bit only] The configurable pool is named generically, because its 105 primary user (the [V8 Sandbox][v8-sandbox]) can configure it at runtime, 106 providing a pre-existing mapping. Its allocations aren't protected by 107 BackupRefPtr. 108 * [64-bit only] The thread isolated pool is returning memory protected with 109 per-thread permissions. At the moment, this is implemented for pkeys on x64. 110 It's primary user is [V8 CFI][v8-cfi]. 111 112 114 115*** promo 116Pools are downgraded into a logical concept in 32-bit environments, 117tracking a non-contiguous set of allocations using a bitmap. 118*** 119 120* **Payload**: The usable area of a super page in which slot spans 121 reside. While generally this means "everything between the first 122 and last guard partition pages in a super page," the presence of 123 other metadata (e.g. StarScan bitmaps) can bump the starting offset 124 forward. While this term is entrenched in the code, the team 125 considers it suboptimal and is actively looking for a replacement. 126* **Allocation Fast Path**: A path taken during an allocation that is 127 considered fast. Usually means that an allocation request can be 128 immediately satisfied by grabbing a slot from the freelist of the 129 first active slot span in the bucket. 130* **Allocation Slow Path**: Anything which is not fast (see above). 131 Can involve 132 * finding another active slot span in the list, 133 * provisioning more slots in a slot span, 134 * bringing back a free (or decommitted) slot span, 135 * allocating a new slot span, or even 136 * allocating a new super page. 137 138*** aside 139By "slow" we may mean something as simple as extra logic (`if` 140statements etc.), or something as costly as system calls. 141*** 142 143## Legacy Terms 144 145These terms are (mostly) deprecated and should not be used. They are 146surfaced here to provide a ready reference for readers coming from 147older design documents or documentation. 148 149* **GigaCage**: A memory region several gigabytes wide, reserved by 150 PartitionAlloc upon initialization, from which nearly all allocations 151 are taken. _Pools_ have overtaken GigaCage in conceptual importance, 152 and so and so there is less need today to refer to "GigaCage" or the 153 "cage." This is especially true given the V8 Sandbox and the 154 configurable pool (see above). 155 156## PartitionAlloc-Everywhere 157 158Originally, PartitionAlloc was used only in Blink (Chromium's rendering engine). 159It was invoked explicitly, by calling PartitionAlloc APIs directly. 160 161PartitionAlloc-Everywhere is the name of the project that brought PartitionAlloc 162to the entire-ish codebase (exclusions apply). This was done by intercepting 163`malloc()`, `free()`, `realloc()`, aforementioned `posix_memalign()`, etc. and 164routing them into PartitionAlloc. The shim located in 165`base/allocator/partition_allocator/src/partition_alloc/shim/allocator_shim_default_dispatch_to_partition_alloc.h` is 166responsible for intercepting. For more details, see 167[base/allocator/README.md](../../../base/allocator/README.md). 168 169A special, catch-it-all *Malloc* partition has been created for the intercepted 170`malloc()` et al. This is to isolate from already existing Blink partitions. 171The only exception from that is Blink's *FastMalloc* partition, which was also 172catch-it-all in nature, so it's perfectly fine to merge these together, to 173minimize fragmentation. 174 175As of 2022, PartitionAlloc-Everywhere is supported on 176 177* Windows 32- and 64-bit 178* Linux 179* Android 32- and 64-bit 180* macOS 181* Fuchsia 182 183[max-bucket-comment]: https://source.chromium.org/chromium/chromium/src/+/main:base/allocator/partition_allocator/src/partition_alloc/partition_alloc_constants.h;l=345;drc=667e6b001f438521e1c1a1bc3eabeead7aaa1f37 184[pa-thread-cache]: https://source.chromium.org/chromium/chromium/src/+/main:base/allocator/partition_allocator/src/partition_alloc/thread_cache.h 185[v8-sandbox]: https://docs.google.com/document/d/1FM4fQmIhEqPG8uGp5o9A-mnPB5BOeScZYpkHjo0KKA8/preview# 186[v8-cfi]: https://docs.google.com/document/d/1O2jwK4dxI3nRcOJuPYkonhTkNQfbmwdvxQMyXgeaRHo/preview# 187
