partition_bucket.h 9.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205
  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. #ifndef BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_BUCKET_H_
  5. #define BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_BUCKET_H_
  6. #include <cstddef>
  7. #include <cstdint>
  8. #include "base/allocator/partition_allocator/partition_alloc_base/compiler_specific.h"
  9. #include "base/allocator/partition_allocator/partition_alloc_base/component_export.h"
  10. #include "base/allocator/partition_allocator/partition_alloc_base/thread_annotations.h"
  11. #include "base/allocator/partition_allocator/partition_alloc_check.h"
  12. #include "base/allocator/partition_allocator/partition_alloc_constants.h"
  13. #include "base/allocator/partition_allocator/partition_alloc_forward.h"
  14. namespace partition_alloc::internal {
  15. constexpr inline int kPartitionNumSystemPagesPerSlotSpanBits = 8;
  16. // Visible for testing.
  17. PA_COMPONENT_EXPORT(PARTITION_ALLOC)
  18. uint8_t ComputeSystemPagesPerSlotSpan(size_t slot_size,
  19. bool prefer_smaller_slot_spans);
  20. // Visible for testing.
  21. PA_COMPONENT_EXPORT(PARTITION_ALLOC)
  22. bool CompareSlotSpans(SlotSpanMetadata<ThreadSafe>* a,
  23. SlotSpanMetadata<ThreadSafe>* b);
  24. template <bool thread_safe>
  25. struct PartitionBucket {
  26. // Accessed most in hot path => goes first. Only nullptr for invalid buckets,
  27. // may be pointing to the sentinel.
  28. SlotSpanMetadata<thread_safe>* active_slot_spans_head;
  29. SlotSpanMetadata<thread_safe>* empty_slot_spans_head;
  30. SlotSpanMetadata<thread_safe>* decommitted_slot_spans_head;
  31. uint32_t slot_size;
  32. uint32_t num_system_pages_per_slot_span
  33. : kPartitionNumSystemPagesPerSlotSpanBits;
  34. uint32_t num_full_slot_spans : 24;
  35. // `slot_size_reciprocal` is used to improve the performance of
  36. // `GetSlotOffset`. It is computed as `(1 / size) * (2 ** M)` where M is
  37. // chosen to provide the desired accuracy. As a result, we can replace a slow
  38. // integer division (or modulo) operation with a pair of multiplication and a
  39. // bit shift, i.e. `value / size` becomes `(value * size_reciprocal) >> M`.
  40. uint64_t slot_size_reciprocal;
  41. // This is `M` from the formula above. For accurate results, both `value` and
  42. // `size`, which are bound by `kMaxBucketed` for our purposes, must be less
  43. // than `2 ** (M / 2)`. On the other hand, the result of the expression
  44. // `3 * M / 2` must be less than 64, otherwise integer overflow can occur.
  45. static constexpr uint64_t kReciprocalShift = 42;
  46. static constexpr uint64_t kReciprocalMask = (1ull << kReciprocalShift) - 1;
  47. static_assert(
  48. kMaxBucketed < (1 << (kReciprocalShift / 2)),
  49. "GetSlotOffset may produce an incorrect result when kMaxBucketed is too "
  50. "large.");
  51. static constexpr size_t kMaxSlotSpansToSort = 200;
  52. // Public API.
  53. PA_COMPONENT_EXPORT(PARTITION_ALLOC) void Init(uint32_t new_slot_size);
  54. // Sets |is_already_zeroed| to true if the allocation was satisfied by
  55. // requesting (a) new page(s) from the operating system, or false otherwise.
  56. // This enables an optimization for when callers use
  57. // |AllocFlags::kZeroFill|: there is no need to call memset on fresh
  58. // pages; the OS has already zeroed them. (See
  59. // |PartitionRoot::AllocFromBucket|.)
  60. //
  61. // Note the matching Free() functions are in SlotSpanMetadata.
  62. PA_COMPONENT_EXPORT(PARTITION_ALLOC)
  63. PA_NOINLINE uintptr_t SlowPathAlloc(PartitionRoot<thread_safe>* root,
  64. unsigned int flags,
  65. size_t raw_size,
  66. size_t slot_span_alignment,
  67. bool* is_already_zeroed)
  68. PA_EXCLUSIVE_LOCKS_REQUIRED(root->lock_);
  69. PA_ALWAYS_INLINE bool CanStoreRawSize() const {
  70. // For direct-map as well as single-slot slot spans (recognized by checking
  71. // against |MaxRegularSlotSpanSize()|), we have some spare metadata space in
  72. // subsequent PartitionPage to store the raw size. It isn't only metadata
  73. // space though, slot spans that have more than one slot can't have raw size
  74. // stored, because we wouldn't know which slot it applies to.
  75. if (PA_LIKELY(slot_size <= MaxRegularSlotSpanSize()))
  76. return false;
  77. PA_DCHECK((slot_size % SystemPageSize()) == 0);
  78. PA_DCHECK(is_direct_mapped() || get_slots_per_span() == 1);
  79. return true;
  80. }
  81. // Some buckets are pseudo-buckets, which are disabled because they would
  82. // otherwise not fulfill alignment constraints.
  83. PA_ALWAYS_INLINE bool is_valid() const {
  84. return active_slot_spans_head != nullptr;
  85. }
  86. PA_ALWAYS_INLINE bool is_direct_mapped() const {
  87. return !num_system_pages_per_slot_span;
  88. }
  89. PA_ALWAYS_INLINE size_t get_bytes_per_span() const {
  90. // Cannot overflow, num_system_pages_per_slot_span is a bitfield, and 255
  91. // pages fit in a size_t.
  92. static_assert(kPartitionNumSystemPagesPerSlotSpanBits <= 8, "");
  93. return num_system_pages_per_slot_span << SystemPageShift();
  94. }
  95. PA_ALWAYS_INLINE size_t get_slots_per_span() const {
  96. size_t ret = GetSlotNumber(get_bytes_per_span());
  97. PA_DCHECK(ret <= SlotSpanMetadata<thread_safe>::kMaxSlotsPerSlotSpan);
  98. return ret;
  99. }
  100. // Returns a natural number of partition pages (calculated by
  101. // ComputeSystemPagesPerSlotSpan()) to allocate from the current super page
  102. // when the bucket runs out of slots.
  103. PA_ALWAYS_INLINE size_t get_pages_per_slot_span() const {
  104. // Rounds up to nearest multiple of NumSystemPagesPerPartitionPage().
  105. return (num_system_pages_per_slot_span +
  106. (NumSystemPagesPerPartitionPage() - 1)) /
  107. NumSystemPagesPerPartitionPage();
  108. }
  109. // This helper function scans a bucket's active slot span list for a suitable
  110. // new active slot span. When it finds a suitable new active slot span (one
  111. // that has free slots and is not empty), it is set as the new active slot
  112. // span. If there is no suitable new active slot span, the current active slot
  113. // span is set to SlotSpanMetadata::get_sentinel_slot_span(). As potential
  114. // slot spans are scanned, they are tidied up according to their state. Empty
  115. // slot spans are swept on to the empty list, decommitted slot spans on to the
  116. // decommitted list and full slot spans are unlinked from any list.
  117. //
  118. // This is where the guts of the bucket maintenance is done!
  119. bool SetNewActiveSlotSpan();
  120. // Walks the entire active slot span list, and perform regular maintenance,
  121. // where empty, decommitted and full slot spans are moved to their
  122. // steady-state place.
  123. PA_COMPONENT_EXPORT(PARTITION_ALLOC) void MaintainActiveList();
  124. // Returns a slot number starting from the beginning of the slot span.
  125. PA_ALWAYS_INLINE size_t GetSlotNumber(size_t offset_in_slot_span) const {
  126. // See the static assertion for `kReciprocalShift` above.
  127. PA_DCHECK(offset_in_slot_span <= kMaxBucketed);
  128. PA_DCHECK(slot_size <= kMaxBucketed);
  129. const size_t offset_in_slot =
  130. ((offset_in_slot_span * slot_size_reciprocal) >> kReciprocalShift);
  131. PA_DCHECK(offset_in_slot_span / slot_size == offset_in_slot);
  132. return offset_in_slot;
  133. }
  134. // Sort the freelists of all slot spans.
  135. void SortSlotSpanFreelists();
  136. // Sort the active slot span list in ascending freelist length.
  137. PA_COMPONENT_EXPORT(PARTITION_ALLOC) void SortActiveSlotSpans();
  138. private:
  139. // Allocates a new slot span with size |num_partition_pages| from the
  140. // current extent. Metadata within this slot span will be initialized.
  141. // Returns nullptr on error.
  142. PA_ALWAYS_INLINE SlotSpanMetadata<thread_safe>* AllocNewSlotSpan(
  143. PartitionRoot<thread_safe>* root,
  144. unsigned int flags,
  145. size_t slot_span_alignment) PA_EXCLUSIVE_LOCKS_REQUIRED(root->lock_);
  146. // Allocates a new super page from the current extent, if possible. All
  147. // slot-spans will be in the decommitted state. Returns the address of the
  148. // super page's payload, or 0 on error.
  149. PA_ALWAYS_INLINE uintptr_t AllocNewSuperPage(PartitionRoot<thread_safe>* root,
  150. unsigned int flags)
  151. PA_EXCLUSIVE_LOCKS_REQUIRED(root->lock_);
  152. // Each bucket allocates a slot span when it runs out of slots.
  153. // A slot span's size is equal to get_pages_per_slot_span() number of
  154. // partition pages. This function initializes all PartitionPage within the
  155. // span to point to the first PartitionPage which holds all the metadata
  156. // for the span (in PartitionPage::SlotSpanMetadata) and registers this bucket
  157. // as the owner of the span. It does NOT put the slots into the bucket's
  158. // freelist.
  159. PA_ALWAYS_INLINE void InitializeSlotSpan(
  160. SlotSpanMetadata<thread_safe>* slot_span);
  161. // Commit 1 or more pages in |slot_span|, enough to get the next slot, which
  162. // is returned by this function. If more slots fit into the committed pages,
  163. // they'll be added to the free list of the slot span (note that next pointers
  164. // are stored inside the slots).
  165. // The free list must be empty when calling this function.
  166. //
  167. // If |slot_span| was freshly allocated, it must have been passed through
  168. // InitializeSlotSpan() first.
  169. PA_ALWAYS_INLINE uintptr_t
  170. ProvisionMoreSlotsAndAllocOne(PartitionRoot<thread_safe>* root,
  171. SlotSpanMetadata<thread_safe>* slot_span)
  172. PA_EXCLUSIVE_LOCKS_REQUIRED(root->lock_);
  173. };
  174. } // namespace partition_alloc::internal
  175. #endif // BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_BUCKET_H_