This document explains a high-level design of PartitionAlloc. If you're interested in its in-depth implementation, see comments in PartitionAlloc.h.
[TOC]
PartitionAlloc is a memory allocator optimized for performance and security in Blink. All objects in Blink are expected to be allocated with PartitionAlloc or Oilpan (but not yet done).
PartitionAlloc has four partitions. A partition is a heap that contains certain types of objects. Specifically, PartitionAlloc allocates objects on either of the following four partitions depending on their types.
Node partition: A partition to allocate Nodes.
LayoutObject partition: A partition to allocate LayoutObjects.
Buffer partition: A partition to allocate objects that have a strong risk that the length and/or the contents are exploited by user scripts. Specifically, Vectors, HashTables, ArrayBufferContents and Strings are allocated on the Buffer partition.
FastMalloc partition: A partition to allocate all other objects. Objects marked with USING_FAST_MALLOC are allocated on the FastMalloc partition.
Each partition holds multiple buckets. A bucket is a region in a partition that contains similar-sized objects. Each object allocation must be aligned with the closest bucket size. For example, if a partition has three buckets for 64 bytes, 256 bytes and 1024 bytes, then an object of 128 bytes is rounded up to 256 bytes and allocated on the second bucket.
The Node partition and the LayoutObject partition have buckets for all N sizeof(void) (N = 1, 2, ..., N_max). This means that no extra padding is needed to allocate a Node object. Different sizes of Node objects are allocated on different buckets.
The Buffer partition and the FastMalloc partition have many buckets. They support any arbitrary size of allocations but padding may be added to align the allocation with the closest bucket size. The bucket sizes are chosen to keep the worst-case memory overhead less than 10%.
Large allocations (> 1 MB) are realized by direct memory mmapping.
PartitionAlloc doesn't acquire a lock when allocating on the Node partition and the LayoutObject partition, because it's guaranteed that Nodes and LayoutObjects are allocated only by the main thread.
PartitionAlloc acquires a lock when allocating on the Buffer partition and the FastMalloc partition. PartitionAlloc uses a spin lock because thread contention would be rare in Blink.
PartitionAlloc is designed to be extremely fast in fast paths. Just two (reasonably predictable) branches are required for the fast paths of an allocation and deallocation. The number of operations in the fast paths is minimized, leading to the possibility of inlining.
Having the dedicated partitions for Nodes and LayoutObjects is helpful to improve cache locality and thus improve performance.
Security is one of the most important goals of PartitionAlloc.
Different partitions are guaranteed to exist in separate address spaces. When objects contained in a page in a partition are all freed, the physical memory is returned to the system but the address space remains reserved. The address space may be reused later only for the partition. Remember that PartitionAlloc puts Nodes into a dedicated partition. This is because Nodes are likely to be a source of use-after-free. Simiarly, PartitionAlloc puts Strings, Vectors etc into the Buffer partition because the length and/or contents may be exploited by user scripts. This means that PartitionAlloc greedily uses virtual address spaces in favor of security hardening.
Also the following security properties are provided:
Linear overflows cannot corrupt into the partition.
Linear overflows cannot corrupt out of the partition.
Metadata is recorded in a dedicated region (not next to each object). Linear overflow or underflow cannot corrupt the metadata.
Buckets are helpful to allocate different-sized objects on different addresses. One page can contain only similar-sized objects.
Dereference of a freelist pointer should fault.
Partial pointer overwrite of freelist pointer should fault.
Large allocations are guard-paged at the beginning and end.