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