• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright (c) 2018 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_CONSTANTS_H_
6 #define THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_CONSTANTS_H_
7 
8 #include <limits.h>
9 
10 #include "build/build_config.h"
11 #include "third_party/base/allocator/partition_allocator/page_allocator_constants.h"
12 #include "third_party/base/logging.h"
13 
14 namespace pdfium {
15 namespace base {
16 
17 // Allocation granularity of sizeof(void*) bytes.
18 static const size_t kAllocationGranularity = sizeof(void*);
19 static const size_t kAllocationGranularityMask = kAllocationGranularity - 1;
20 static const size_t kBucketShift = (kAllocationGranularity == 8) ? 3 : 2;
21 
22 // Underlying partition storage pages (`PartitionPage`s) are a power-of-2 size.
23 // It is typical for a `PartitionPage` to be based on multiple system pages.
24 // Most references to "page" refer to `PartitionPage`s.
25 //
26 // *Super pages* are the underlying system allocations we make. Super pages
27 // contain multiple partition pages and include space for a small amount of
28 // metadata per partition page.
29 //
30 // Inside super pages, we store *slot spans*. A slot span is a continguous range
31 // of one or more `PartitionPage`s that stores allocations of the same size.
32 // Slot span sizes are adjusted depending on the allocation size, to make sure
33 // the packing does not lead to unused (wasted) space at the end of the last
34 // system page of the span. For our current maximum slot span size of 64 KiB and
35 // other constant values, we pack _all_ `PartitionRootGeneric::Alloc` sizes
36 // perfectly up against the end of a system page.
37 
38 #if defined(_MIPS_ARCH_LOONGSON)
39 static const size_t kPartitionPageShift = 16;  // 64 KiB
40 #elif defined(ARCH_CPU_PPC64)
41 static const size_t kPartitionPageShift = 18;  // 256 KiB
42 #else
43 static const size_t kPartitionPageShift = 14;  // 16 KiB
44 #endif
45 static const size_t kPartitionPageSize = 1 << kPartitionPageShift;
46 static const size_t kPartitionPageOffsetMask = kPartitionPageSize - 1;
47 static const size_t kPartitionPageBaseMask = ~kPartitionPageOffsetMask;
48 // TODO: Should this be 1 if defined(_MIPS_ARCH_LOONGSON)?
49 static const size_t kMaxPartitionPagesPerSlotSpan = 4;
50 
51 // To avoid fragmentation via never-used freelist entries, we hand out partition
52 // freelist sections gradually, in units of the dominant system page size. What
53 // we're actually doing is avoiding filling the full `PartitionPage` (16 KiB)
54 // with freelist pointers right away. Writing freelist pointers will fault and
55 // dirty a private page, which is very wasteful if we never actually store
56 // objects there.
57 
58 static const size_t kNumSystemPagesPerPartitionPage =
59     kPartitionPageSize / kSystemPageSize;
60 static const size_t kMaxSystemPagesPerSlotSpan =
61     kNumSystemPagesPerPartitionPage * kMaxPartitionPagesPerSlotSpan;
62 
63 // We reserve virtual address space in 2 MiB chunks (aligned to 2 MiB as well).
64 // These chunks are called *super pages*. We do this so that we can store
65 // metadata in the first few pages of each 2 MiB-aligned section. This makes
66 // freeing memory very fast. We specifically choose 2 MiB because this virtual
67 // address block represents a full but single PTE allocation on ARM, ia32 and
68 // x64.
69 //
70 // The layout of the super page is as follows. The sizes below are the same for
71 // 32- and 64-bit platforms.
72 //
73 //     +-----------------------+
74 //     | Guard page (4 KiB)    |
75 //     | Metadata page (4 KiB) |
76 //     | Guard pages (8 KiB)   |
77 //     | Slot span             |
78 //     | Slot span             |
79 //     | ...                   |
80 //     | Slot span             |
81 //     | Guard page (4 KiB)    |
82 //     +-----------------------+
83 //
84 // Each slot span is a contiguous range of one or more `PartitionPage`s.
85 //
86 // The metadata page has the following format. Note that the `PartitionPage`
87 // that is not at the head of a slot span is "unused". In other words, the
88 // metadata for the slot span is stored only in the first `PartitionPage` of the
89 // slot span. Metadata accesses to other `PartitionPage`s are redirected to the
90 // first `PartitionPage`.
91 //
92 //     +---------------------------------------------+
93 //     | SuperPageExtentEntry (32 B)                 |
94 //     | PartitionPage of slot span 1 (32 B, used)   |
95 //     | PartitionPage of slot span 1 (32 B, unused) |
96 //     | PartitionPage of slot span 1 (32 B, unused) |
97 //     | PartitionPage of slot span 2 (32 B, used)   |
98 //     | PartitionPage of slot span 3 (32 B, used)   |
99 //     | ...                                         |
100 //     | PartitionPage of slot span N (32 B, unused) |
101 //     +---------------------------------------------+
102 //
103 // A direct-mapped page has a similar layout to fake it looking like a super
104 // page:
105 //
106 //     +-----------------------+
107 //     | Guard page (4 KiB)    |
108 //     | Metadata page (4 KiB) |
109 //     | Guard pages (8 KiB)   |
110 //     | Direct mapped object  |
111 //     | Guard page (4 KiB)    |
112 //     +-----------------------+
113 //
114 // A direct-mapped page's metadata page has the following layout:
115 //
116 //     +--------------------------------+
117 //     | SuperPageExtentEntry (32 B)    |
118 //     | PartitionPage (32 B)           |
119 //     | PartitionBucket (32 B)         |
120 //     | PartitionDirectMapExtent (8 B) |
121 //     +--------------------------------+
122 
123 static const size_t kSuperPageShift = 21;  // 2 MiB
124 static const size_t kSuperPageSize = 1 << kSuperPageShift;
125 static const size_t kSuperPageOffsetMask = kSuperPageSize - 1;
126 static const size_t kSuperPageBaseMask = ~kSuperPageOffsetMask;
127 static const size_t kNumPartitionPagesPerSuperPage =
128     kSuperPageSize / kPartitionPageSize;
129 
130 // The following kGeneric* constants apply to the generic variants of the API.
131 // The "order" of an allocation is closely related to the power-of-1 size of the
132 // allocation. More precisely, the order is the bit index of the
133 // most-significant-bit in the allocation size, where the bit numbers starts at
134 // index 1 for the least-significant-bit.
135 //
136 // In terms of allocation sizes, order 0 covers 0, order 1 covers 1, order 2
137 // covers 2->3, order 3 covers 4->7, order 4 covers 8->15.
138 
139 static const size_t kGenericMinBucketedOrder = 4;  // 8 bytes.
140 // The largest bucketed order is 1 << (20 - 1), storing [512 KiB, 1 MiB):
141 static const size_t kGenericMaxBucketedOrder = 20;
142 static const size_t kGenericNumBucketedOrders =
143     (kGenericMaxBucketedOrder - kGenericMinBucketedOrder) + 1;
144 // Eight buckets per order (for the higher orders), e.g. order 8 is 128, 144,
145 // 160, ..., 240:
146 static const size_t kGenericNumBucketsPerOrderBits = 3;
147 static const size_t kGenericNumBucketsPerOrder =
148     1 << kGenericNumBucketsPerOrderBits;
149 static const size_t kGenericNumBuckets =
150     kGenericNumBucketedOrders * kGenericNumBucketsPerOrder;
151 static const size_t kGenericSmallestBucket = 1
152                                              << (kGenericMinBucketedOrder - 1);
153 static const size_t kGenericMaxBucketSpacing =
154     1 << ((kGenericMaxBucketedOrder - 1) - kGenericNumBucketsPerOrderBits);
155 static const size_t kGenericMaxBucketed =
156     (1 << (kGenericMaxBucketedOrder - 1)) +
157     ((kGenericNumBucketsPerOrder - 1) * kGenericMaxBucketSpacing);
158 // Limit when downsizing a direct mapping using `realloc`:
159 static const size_t kGenericMinDirectMappedDownsize = kGenericMaxBucketed + 1;
160 static const size_t kGenericMaxDirectMapped =
161     (1UL << 31) + kPageAllocationGranularity;  // 2 GiB plus 1 more page.
162 static const size_t kBitsPerSizeT = sizeof(void*) * CHAR_BIT;
163 
164 // Constant for the memory reclaim logic.
165 static const size_t kMaxFreeableSpans = 16;
166 
167 // If the total size in bytes of allocated but not committed pages exceeds this
168 // value (probably it is a "out of virtual address space" crash), a special
169 // crash stack trace is generated at
170 // `PartitionOutOfMemoryWithLotsOfUncommitedPages`. This is to distinguish "out
171 // of virtual address space" from "out of physical memory" in crash reports.
172 static const size_t kReasonableSizeOfUnusedPages = 1024 * 1024 * 1024;  // 1 GiB
173 
174 // These byte values match tcmalloc.
175 static const unsigned char kUninitializedByte = 0xAB;
176 static const unsigned char kFreedByte = 0xCD;
177 
178 // Flags for `PartitionAllocGenericFlags`.
179 enum PartitionAllocFlags {
180   PartitionAllocReturnNull = 1 << 0,
181   PartitionAllocZeroFill = 1 << 1,
182 
183   PartitionAllocLastFlag = PartitionAllocZeroFill
184 };
185 
186 }  // namespace base
187 }  // namespace pdfium
188 
189 #endif  // THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_CONSTANTS_H_
190