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 BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_CONSTANTS_H_ 6 #define BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_CONSTANTS_H_ 7 8 #include <limits.h> 9 10 #include "base/allocator/partition_allocator/page_allocator_constants.h" 11 #include "base/logging.h" 12 13 #include "build/build_config.h" 14 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 188 #endif // BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_CONSTANTS_H_ 189