# PartitionAlloc Design

This document explains a high-level design of PartitionAlloc.
If you're interested in its in-depth implementation, see comments
in PartitionAlloc.h.

[TOC]

## Overview

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).

## Partitions and buckets

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.

## Performance

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

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.
