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 |