| OLD | NEW |
| 1 # PartitionAlloc Design | 1 # PartitionAlloc Design |
| 2 | 2 |
| 3 This document explains a high-level design of PartitionAlloc. | 3 This document explains a high-level design of PartitionAlloc. |
| 4 If you're interested in its in-depth implementation, see comments | 4 If you're interested in its in-depth implementation, see comments |
| 5 in PartitionAlloc.h. | 5 in PartitionAlloc.h. |
| 6 | 6 |
| 7 [TOC] | 7 [TOC] |
| 8 | 8 |
| 9 ## Overview | 9 ## Overview |
| 10 | 10 |
| 11 PartitionAlloc is a memory allocator optimized for performance and security | 11 PartitionAlloc is a memory allocator optimized for performance and security |
| 12 in Blink. All objects in Blink are expected to be allocated with | 12 in Blink. All objects in Blink are expected to be allocated with |
| 13 PartitionAlloc or Oilpan (but not yet done). | 13 PartitionAlloc or Oilpan (but not yet done). |
| 14 | 14 |
| 15 ## Partitions and buckets | 15 ## Partitions and buckets |
| 16 | 16 |
| 17 PartitionAlloc has four partitions. A partition is a heap that contains | 17 PartitionAlloc has three partitions. A partition is a heap that contains |
| 18 certain types of objects. Specifically, PartitionAlloc allocates objects | 18 certain types of objects. Specifically, PartitionAlloc allocates objects |
| 19 on either of the following four partitions depending on their types. | 19 on either of the following three partitions depending on their types: |
| 20 | |
| 21 * Node partition: A partition to allocate Nodes. | |
| 22 | 20 |
| 23 * LayoutObject partition: A partition to allocate LayoutObjects. | 21 * LayoutObject partition: A partition to allocate LayoutObjects. |
| 24 | 22 |
| 25 * Buffer partition: A partition to allocate objects that have a strong risk | 23 * Buffer partition: A partition to allocate objects that have a strong risk |
| 26 that the length and/or the contents are exploited by user scripts. | 24 that the length and/or the contents are exploited by user scripts. |
| 27 Specifically, Vectors, HashTables, ArrayBufferContents and Strings are | 25 Specifically, Vectors, HashTables, ArrayBufferContents and Strings are |
| 28 allocated on the Buffer partition. | 26 allocated on the Buffer partition. |
| 29 | 27 |
| 30 * FastMalloc partition: A partition to allocate all other objects. | 28 * FastMalloc partition: A partition to allocate all other objects. |
| 31 Objects marked with USING_FAST_MALLOC are allocated on the FastMalloc partition. | 29 Objects marked with USING_FAST_MALLOC are allocated on the FastMalloc partition. |
| 32 | 30 |
| 33 Each partition holds multiple buckets. A bucket is a region in a partition | 31 Each partition holds multiple buckets. A bucket is a region in a partition |
| 34 that contains similar-sized objects. Each object allocation must be aligned | 32 that contains similar-sized objects. Each object allocation must be aligned |
| 35 with the closest bucket size. For example, if a partition has three buckets | 33 with the closest bucket size. For example, if a partition has three buckets |
| 36 for 64 bytes, 256 bytes and 1024 bytes, then an object of 128 bytes is | 34 for 64 bytes, 256 bytes and 1024 bytes, then an object of 128 bytes is |
| 37 rounded up to 256 bytes and allocated on the second bucket. | 35 rounded up to 256 bytes and allocated on the second bucket. |
| 38 | 36 |
| 39 The Node partition and the LayoutObject partition have buckets for all | 37 The LayoutObject partition has buckets for all N * sizeof(void*) (N = 1, 2, ...,
N_max). |
| 40 N * sizeof(void*) (N = 1, 2, ..., N_max). This means that no extra padding | 38 This means that no extra padding is needed to allocate a LayoutObject object. |
| 41 is needed to allocate a Node object. Different sizes of Node objects are | 39 Different sizes of LayoutObjects are allocated in different buckets. |
| 42 allocated on different buckets. | |
| 43 | 40 |
| 44 The Buffer partition and the FastMalloc partition have many buckets. | 41 The Buffer partition and the FastMalloc partition have many buckets. |
| 45 They support any arbitrary size of allocations but padding may be added | 42 They support any arbitrary size of allocations but padding may be added |
| 46 to align the allocation with the closest bucket size. The bucket sizes are | 43 to align the allocation with the closest bucket size. The bucket sizes are |
| 47 chosen to keep the worst-case memory overhead less than 10%. | 44 chosen to keep the worst-case memory overhead less than 10%. |
| 48 | 45 |
| 49 Large allocations (> 1 MB) are realized by direct memory mmapping. | 46 Large allocations (> 1 MB) are realized by direct memory mmapping. |
| 50 | 47 |
| 51 ## Performance | 48 ## Performance |
| 52 | 49 |
| 53 PartitionAlloc doesn't acquire a lock when allocating on the Node partition and | 50 PartitionAlloc doesn't acquire a lock when allocating on the LayoutObject |
| 54 the LayoutObject partition, because it's guaranteed that Nodes and LayoutObjects | 51 partition, because it's guaranteed that LayoutObjects are allocated |
| 55 are allocated only by the main thread. | 52 only by the main thread. |
| 56 | 53 |
| 57 PartitionAlloc acquires a lock when allocating on the Buffer partition and | 54 PartitionAlloc acquires a lock when allocating on the Buffer partition and |
| 58 the FastMalloc partition. PartitionAlloc uses a spin lock because thread content
ion | 55 the FastMalloc partition. PartitionAlloc uses a spin lock because thread content
ion |
| 59 would be rare in Blink. | 56 would be rare in Blink. |
| 60 | 57 |
| 61 PartitionAlloc is designed to be extremely fast in fast paths. Just two | 58 PartitionAlloc is designed to be extremely fast in fast paths. Just two |
| 62 (reasonably predictable) branches are required for the fast paths of an | 59 (reasonably predictable) branches are required for the fast paths of an |
| 63 allocation and deallocation. The number of operations in the fast paths | 60 allocation and deallocation. The number of operations in the fast paths |
| 64 is minimized, leading to the possibility of inlining. | 61 is minimized, leading to the possibility of inlining. |
| 65 | 62 |
| 66 Having the dedicated partitions for Nodes and LayoutObjects is helpful | 63 Having a dedicated partition for LayoutObjects is helpful to improve cache |
| 67 to improve cache locality and thus improve performance. | 64 locality and thus help improve performance. |
| 68 | 65 |
| 69 ## Security | 66 ## Security |
| 70 | 67 |
| 71 Security is one of the most important goals of PartitionAlloc. | 68 Security is one of the most important goals of PartitionAlloc. |
| 72 | 69 |
| 73 Different partitions are guaranteed to exist in separate address spaces. | 70 Different partitions are guaranteed to exist in separate address spaces. |
| 74 When objects contained in a page in a partition are all freed, | 71 When objects contained in a page in a partition are all freed, |
| 75 the physical memory is returned to the system but the address space | 72 the physical memory is returned to the system but the address space |
| 76 remains reserved. The address space may be reused later only for the partition. | 73 remains reserved. The address space may be reused later only for the partition. |
| 77 Remember that PartitionAlloc puts Nodes into a dedicated partition. | 74 Remember that PartitionAlloc puts LayoutObjects into a dedicated partition. |
| 78 This is because Nodes are likely to be a source of use-after-free. | 75 This is because LayoutObjects are likely to be a source of use-after-free. |
| 79 Simiarly, PartitionAlloc puts Strings, Vectors etc into the Buffer partition | 76 Simiarly, PartitionAlloc puts Strings, Vectors etc into the Buffer partition |
| 80 because the length and/or contents may be exploited by user scripts. | 77 because the length and/or contents may be exploited by user scripts. |
| 81 This means that PartitionAlloc greedily uses virtual address spaces in favor of | 78 This means that PartitionAlloc greedily uses virtual address spaces in favor of |
| 82 security hardening. | 79 security hardening. |
| 83 | 80 |
| 84 Also the following security properties are provided: | 81 Also the following security properties are provided: |
| 85 | 82 |
| 86 * Linear overflows cannot corrupt into the partition. | 83 * Linear overflows cannot corrupt into the partition. |
| 87 | 84 |
| 88 * Linear overflows cannot corrupt out of the partition. | 85 * Linear overflows cannot corrupt out of the partition. |
| 89 | 86 |
| 90 * Metadata is recorded in a dedicated region (not next to each object). | 87 * Metadata is recorded in a dedicated region (not next to each object). |
| 91 Linear overflow or underflow cannot corrupt the metadata. | 88 Linear overflow or underflow cannot corrupt the metadata. |
| 92 | 89 |
| 93 * Buckets are helpful to allocate different-sized objects on different addresses
. | 90 * Buckets are helpful to allocate different-sized objects on different addresses
. |
| 94 One page can contain only similar-sized objects. | 91 One page can contain only similar-sized objects. |
| 95 | 92 |
| 96 * Dereference of a freelist pointer should fault. | 93 * Dereference of a freelist pointer should fault. |
| 97 | 94 |
| 98 * Partial pointer overwrite of freelist pointer should fault. | 95 * Partial pointer overwrite of freelist pointer should fault. |
| 99 | 96 |
| 100 * Large allocations are guard-paged at the beginning and end. | 97 * Large allocations are guard-paged at the beginning and end. |
| OLD | NEW |