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_BUCKET_H_ 6 #define THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_BUCKET_H_ 7 8 #include <stddef.h> 9 #include <stdint.h> 10 11 #include "third_party/base/allocator/partition_allocator/partition_alloc_constants.h" 12 #include "third_party/base/base_export.h" 13 #include "third_party/base/compiler_specific.h" 14 15 namespace pdfium { 16 namespace base { 17 namespace internal { 18 19 struct PartitionPage; 20 struct PartitionRootBase; 21 22 struct PartitionBucket { 23 // Accessed most in hot path => goes first. 24 PartitionPage* active_pages_head; 25 26 PartitionPage* empty_pages_head; 27 PartitionPage* decommitted_pages_head; 28 uint32_t slot_size; 29 uint32_t num_system_pages_per_slot_span : 8; 30 uint32_t num_full_pages : 24; 31 32 // Public API. 33 void Init(uint32_t new_slot_size); 34 35 // Sets |is_already_zeroed| to true if the allocation was satisfied by 36 // requesting (a) new page(s) from the operating system, or false otherwise. 37 // This enables an optimization for when callers use |PartitionAllocZeroFill|: 38 // there is no need to call memset on fresh pages; the OS has already zeroed 39 // them. (See |PartitionRootBase::AllocFromBucket|.) 40 // 41 // Note the matching Free() functions are in PartitionPage. 42 BASE_EXPORT NOINLINE void* SlowPathAlloc(PartitionRootBase* root, 43 int flags, 44 size_t size, 45 bool* is_already_zeroed); 46 is_direct_mappedPartitionBucket47 ALWAYS_INLINE bool is_direct_mapped() const { 48 return !num_system_pages_per_slot_span; 49 } get_bytes_per_spanPartitionBucket50 ALWAYS_INLINE size_t get_bytes_per_span() const { 51 // TODO(ajwong): Change to CheckedMul. https://crbug.com/787153 52 // https://crbug.com/680657 53 return num_system_pages_per_slot_span * kSystemPageSize; 54 } get_slots_per_spanPartitionBucket55 ALWAYS_INLINE uint16_t get_slots_per_span() const { 56 // TODO(ajwong): Change to CheckedMul. https://crbug.com/787153 57 // https://crbug.com/680657 58 return static_cast<uint16_t>(get_bytes_per_span() / slot_size); 59 } 60 get_direct_map_sizePartitionBucket61 static ALWAYS_INLINE size_t get_direct_map_size(size_t size) { 62 // Caller must check that the size is not above the kGenericMaxDirectMapped 63 // limit before calling. This also guards against integer overflow in the 64 // calculation here. 65 DCHECK(size <= kGenericMaxDirectMapped); 66 return (size + kSystemPageOffsetMask) & kSystemPageBaseMask; 67 } 68 69 // TODO(ajwong): Can this be made private? https://crbug.com/787153 70 static PartitionBucket* get_sentinel_bucket(); 71 72 // This helper function scans a bucket's active page list for a suitable new 73 // active page. When it finds a suitable new active page (one that has 74 // free slots and is not empty), it is set as the new active page. If there 75 // is no suitable new active page, the current active page is set to 76 // PartitionPage::get_sentinel_page(). As potential pages are scanned, they 77 // are tidied up according to their state. Empty pages are swept on to the 78 // empty page list, decommitted pages on to the decommitted page list and full 79 // pages are unlinked from any list. 80 // 81 // This is where the guts of the bucket maintenance is done! 82 bool SetNewActivePage(); 83 84 private: 85 static void OutOfMemory(const PartitionRootBase* root); 86 static void OutOfMemoryWithLotsOfUncommitedPages(); 87 88 static NOINLINE void OnFull(); 89 90 // Returns a natural number of PartitionPages (calculated by 91 // get_system_pages_per_slot_span()) to allocate from the current 92 // SuperPage when the bucket runs out of slots. 93 ALWAYS_INLINE uint16_t get_pages_per_slot_span(); 94 95 // Returns the number of system pages in a slot span. 96 // 97 // The calculation attemps to find the best number of System Pages to 98 // allocate for the given slot_size to minimize wasted space. It uses a 99 // heuristic that looks at number of bytes wasted after the last slot and 100 // attempts to account for the PTE usage of each System Page. 101 uint8_t get_system_pages_per_slot_span(); 102 103 // Allocates a new slot span with size |num_partition_pages| from the 104 // current extent. Metadata within this slot span will be uninitialized. 105 // Returns nullptr on error. 106 ALWAYS_INLINE void* AllocNewSlotSpan(PartitionRootBase* root, 107 int flags, 108 uint16_t num_partition_pages); 109 110 // Each bucket allocates a slot span when it runs out of slots. 111 // A slot span's size is equal to get_pages_per_slot_span() number of 112 // PartitionPages. This function initializes all PartitionPage within the 113 // span to point to the first PartitionPage which holds all the metadata 114 // for the span and registers this bucket as the owner of the span. It does 115 // NOT put the slots into the bucket's freelist. 116 ALWAYS_INLINE void InitializeSlotSpan(PartitionPage* page); 117 118 // Allocates one slot from the given |page| and then adds the remainder to 119 // the current bucket. If the |page| was freshly allocated, it must have been 120 // passed through InitializeSlotSpan() first. 121 ALWAYS_INLINE char* AllocAndFillFreelist(PartitionPage* page); 122 123 static PartitionBucket sentinel_bucket_; 124 }; 125 126 } // namespace internal 127 } // namespace base 128 } // namespace pdfium 129 130 #endif // THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_BUCKET_H_ 131