xref: /aosp_15_r20/external/pigweed/pw_allocator/public/pw_allocator/bucket_allocator.h (revision 61c4878ac05f98d0ceed94b57d316916de578985)
1 // Copyright 2024 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 //     https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14 #pragma once
15 
16 #include <array>
17 #include <cstdint>
18 #include <utility>
19 
20 #include "pw_allocator/block/detailed_block.h"
21 #include "pw_allocator/block_allocator.h"
22 #include "pw_allocator/bucket/unordered.h"
23 #include "pw_assert/check.h"
24 #include "pw_status/try.h"
25 
26 namespace pw::allocator {
27 
28 /// Alias for a default block type that is compatible with
29 /// `BucketAllocator`.
30 template <typename OffsetType = uintptr_t>
31 using BucketBlock = DetailedBlock<OffsetType, UnorderedItem>;
32 
33 /// Block allocator that uses sized buckets of free blocks.
34 ///
35 /// In this strategy, the allocator handles an allocation request by starting
36 /// with the bucket with the smallest size that is larger than the requested
37 /// size. It tries to allocate using the blocks in that block, if any, before
38 /// trying the bucket with the next largest size.
39 ///
40 /// On deallocation, blocks are placed in the bucket of the smallest size that
41 /// is larger than usable space of the block being freed.
42 ///
43 /// The last bucket always has an unbounded size.
44 ///
45 /// As an example, assume that the allocator is configured with a minimum block
46 /// inner size of 64 and 5 buckets. The internal state may look like the
47 /// following:
48 ///
49 /// @code{.unparsed}
50 /// bucket[0] (64B) --> block[12B] --> block[42B] --> block[64B] --> NULL
51 /// bucket[1] (128B) --> block[65B] --> block[72B] --> NULL
52 /// bucket[2] (256B) --> NULL
53 /// bucket[3] (512B) --> block[312B] --> block[512B] --> block[416B] --> NULL
54 /// bucket[4] (implicit) --> block[1024B] --> block[513B] --> NULL
55 /// @endcode
56 template <typename BlockType = BucketBlock<>,
57           size_t kMinInnerSize = 32,
58           size_t kNumBuckets = 5>
59 class BucketAllocator : public BlockAllocator<BlockType> {
60  private:
61   using Base = BlockAllocator<BlockType>;
62 
63  public:
64   /// Constexpr constructor. Callers must explicitly call `Init`.
BucketAllocator()65   constexpr BucketAllocator() {
66     size_t max_inner_size = kMinInnerSize;
67     for (auto& bucket : span(buckets_.data(), kNumBuckets - 1)) {
68       bucket.set_max_inner_size(max_inner_size);
69       max_inner_size <<= 1;
70     }
71   }
72 
73   /// Non-constexpr constructor that automatically calls `Init`.
74   ///
75   /// @param[in]  region  Region of memory to use when satisfying allocation
76   ///                     requests. The region MUST be large enough to fit an
77   ///                     aligned block with overhead. It MUST NOT be larger
78   ///                     than what is addressable by `OffsetType`.
BucketAllocator(ByteSpan region)79   explicit BucketAllocator(ByteSpan region) : BucketAllocator() {
80     Base::Init(region);
81   }
82 
~BucketAllocator()83   ~BucketAllocator() override {
84     for (auto& bucket : buckets_) {
85       bucket.Clear();
86     }
87   }
88 
89  private:
90   /// @copydoc BlockAllocator::ChooseBlock
ChooseBlock(Layout layout)91   BlockResult<BlockType> ChooseBlock(Layout layout) override {
92     for (auto& bucket : buckets_) {
93       if (layout.size() <= bucket.max_inner_size()) {
94         BlockType* block = bucket.RemoveCompatible(layout);
95         if (block != nullptr) {
96           return BlockType::AllocFirst(std::move(block), layout);
97         }
98       }
99     }
100     return BlockResult<BlockType>(nullptr, Status::NotFound());
101   }
102 
103   /// @copydoc BlockAllocator::ReserveBlock
ReserveBlock(BlockType & block)104   void ReserveBlock(BlockType& block) override {
105     for (auto& bucket : buckets_) {
106       if (block.InnerSize() <= bucket.max_inner_size()) {
107         std::ignore = bucket.Remove(block);
108         break;
109       }
110     }
111   }
112 
113   /// @copydoc BlockAllocator::RecycleBlock
RecycleBlock(BlockType & block)114   void RecycleBlock(BlockType& block) override {
115     for (auto& bucket : buckets_) {
116       if (block.InnerSize() <= bucket.max_inner_size()) {
117         std::ignore = bucket.Add(block);
118         break;
119       }
120     }
121   }
122 
123   std::array<UnorderedBucket<BlockType>, kNumBuckets> buckets_;
124 };
125 
126 }  // namespace pw::allocator
127