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