19#include "pw_allocator/block/detailed_block.h"
20#include "pw_allocator/block_allocator.h"
21#include "pw_allocator/bucket/fast_sorted.h"
22#include "pw_allocator/bucket/unordered.h"
23#include "pw_allocator/config.h"
25namespace pw::allocator {
28template <
typename OffsetType>
29using DlBlock = DetailedBlock<OffsetType, GenericFastSortedItem>;
44template <
typename BlockType = DlBlock<u
intptr_t>>
52 static constexpr size_t kMinSize = 8;
55 static constexpr size_t kNumFastBins = 10;
58 static constexpr size_t kNumSmallBins = 64;
59 static_assert((kNumSmallBins & (kNumSmallBins - 1)) == 0);
63 static constexpr size_t kNumLargeBins = kNumSmallBins - 1;
66 static constexpr size_t kBitmapBits = std::numeric_limits<uintptr_t>::digits;
67 static constexpr size_t kNumBitmaps =
68 AlignUp(kNumSmallBins + kNumLargeBins, kBitmapBits) / kBitmapBits;
85 BlockResult<BlockType>
ChooseBlock(Layout layout)
override;
94 void Flush()
override { ReleaseFastBins(); }
105 size_t GetIndex(
size_t size);
114 void ReleaseFastBins();
120 bool FindNextAvailable(
size_t& index);
124 void UpdateBitmaps(
size_t index,
bool empty);
126 std::array<FastBin, kNumFastBins> fast_bins_;
127 std::array<SmallBin, kNumSmallBins> small_bins_;
128 std::array<LargeBin, kNumLargeBins> large_bins_;
129 std::array<uintptr_t, kNumBitmaps> bitmaps_;
134template <
typename BlockType>
138 size_t bin_size = kMinSize;
139 size_t bins_in_round = kNumSmallBins;
140 while (bins_in_round > 1) {
141 for (
size_t i = 0; i < bins_in_round; ++i) {
143 if (index < kNumFastBins) {
144 fast_bins_[index].set_max_inner_size(size);
146 if (index < kNumSmallBins) {
147 small_bins_[index].set_max_inner_size(size);
149 large_bins_[index - kNumSmallBins].set_max_inner_size(size);
159template <
typename BlockType>
161 layout =
Layout(std::max(layout.size(), kMinSize), layout.alignment());
162 size_t index = GetIndex(layout.size());
164 if (index < kNumSmallBins) {
166 if (index < kNumFastBins) {
167 FastBin& fast_bin = fast_bins_[index];
169 if (block !=
nullptr) {
175 if (small_bins_[index].empty()) {
184 for (; FindNextAvailable(index) && index < kNumSmallBins; ++index) {
185 SmallBin& small_bin = small_bins_[index];
187 if (block !=
nullptr) {
188 UpdateBitmaps(index, small_bin.
empty());
189 return BlockType::AllocFirst(std::move(block), layout);
194 for (; FindNextAvailable(index); ++index) {
195 LargeBin& large_bin = large_bins_[index - kNumSmallBins];
197 if (block !=
nullptr) {
198 UpdateBitmaps(index, large_bin.
empty());
199 return BlockType::AllocFirst(std::move(block), layout);
207template <
typename BlockType>
209 size_t index = GetIndex(block.InnerSize());
210 if (index < kNumSmallBins) {
211 SmallBin& small_bin = small_bins_[index];
212 std::ignore = small_bin.
Remove(block);
213 UpdateBitmaps(index, small_bin.
empty());
215 LargeBin& large_bin = large_bins_[index - kNumSmallBins];
216 std::ignore = large_bin.
Remove(block);
217 UpdateBitmaps(index, large_bin.
empty());
221template <
typename BlockType>
223 size_t index = GetIndex(block.InnerSize());
224 if (index < kNumSmallBins) {
225 std::ignore = small_bins_[index].Add(block);
227 std::ignore = large_bins_[index - kNumSmallBins].Add(block);
229 UpdateBitmaps(index,
false);
232template <
typename BlockType>
235 size_t index = block->InnerSize() / kMinSize;
236 if (index < kNumFastBins) {
237 std::ignore = fast_bins_[index].Add(*block);
239 Base::DeallocateBlock(std::move(block));
243template <
typename BlockType>
246 size_t bin_size = kMinSize;
247 size_t bins_in_round = kNumSmallBins;
248 size =
AlignUp(size, kMinSize) - kMinSize;
249 while (bins_in_round > 1) {
250 size_t round_size = bin_size * bins_in_round;
251 if (size < round_size) {
252 return index + (size / bin_size);
255 index += bins_in_round;
262template <
typename BlockType>
263void DlAllocator<BlockType>::ReleaseFastBins() {
264 for (
auto& fast_bin : fast_bins_) {
265 while (!fast_bin.empty()) {
266 BlockType* block = fast_bin.RemoveAny();
267 if constexpr (Hardening::kIncludesDebugChecks) {
268 PW_ASSERT(block !=
nullptr);
270 Base::DeallocateBlock(std::move(block));
275template <
typename BlockType>
276bool DlAllocator<BlockType>::FindNextAvailable(
size_t& index) {
277 size_t bitmap_index = index / kBitmapBits;
278 size_t bitmap_offset = index % kBitmapBits;
279 uintptr_t bitmap = bitmaps_[bitmap_index] & (~uintptr_t(0) << bitmap_offset);
280 while (bitmap == 0) {
282 if (bitmap_index >= kNumBitmaps) {
285 bitmap = bitmaps_[bitmap_index];
287 auto bitmap_log2 = internal::CountRZero(bitmap);
288 index = (bitmap_index * kBitmapBits) + bitmap_log2;
292template <
typename BlockType>
293void DlAllocator<BlockType>::UpdateBitmaps(
size_t index,
bool empty) {
294 size_t bitmap_index = index / kBitmapBits;
295 size_t bitmap_offset = index % kBitmapBits;
296 uintptr_t bitmap = uintptr_t(1) << bitmap_offset;
298 bitmaps_[bitmap_index] &= ~bitmap;
300 bitmaps_[bitmap_index] |= bitmap;
Definition: block_allocator.h:104
void Init(ByteSpan region)
Definition: block_allocator.h:281
Definition: dl_allocator.h:45
void RecycleBlock(BlockType &block) override
Definition: dl_allocator.h:222
void DeallocateBlock(BlockType *&&block) override
Definition: dl_allocator.h:233
BlockResult< BlockType > ChooseBlock(Layout layout) override
Definition: dl_allocator.h:160
void Flush() override
Definition: dl_allocator.h:94
void ReserveBlock(BlockType &block) override
Definition: dl_allocator.h:208
DlAllocator(ByteSpan region)
Definition: dl_allocator.h:79
constexpr DlAllocator()
Constexpr constructor. Callers must explicitly call Init.
Definition: dl_allocator.h:135
Definition: fast_sorted.h:63
Definition: unordered.h:42
bool Remove(BlockType &block)
Definition: base.h:110
constexpr bool empty() const
Returns whether this buckets contains any free blocks.
Definition: base.h:68
BlockType * RemoveCompatible(Layout layout)
Definition: base.h:121
constexpr size_t AlignUp(uintptr_t value, size_t alignment)
Returns the value rounded up to the nearest multiple of alignment.
Definition: alignment.h:52