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 <cstddef>
17 #include <cstdint>
18
19 #include "lib/stdcompat/bit.h"
20 #include "pw_allocator/block/allocatable.h"
21 #include "pw_allocator/block/result.h"
22 #include "pw_allocator/layout.h"
23 #include "pw_assert/assert.h"
24 #include "pw_bytes/alignment.h"
25 #include "pw_status/status.h"
26
27 namespace pw::allocator {
28 namespace internal {
29
30 // Trivial base class for trait support.
31 struct AlignableBase {};
32
33 } // namespace internal
34
35 /// Mix-in for blocks that can be split on alignment boundaries.
36 ///
37 /// Block mix-ins are stateless and trivially constructible. See `BasicBlock`
38 /// for details on how mix-ins can be combined to implement blocks.
39 ///
40 /// This mix-in requires its derived type also derive from `AllocatableBlock`.
41 template <typename Derived>
42 class AlignableBlock : public internal::AlignableBase {
43 protected:
AlignableBlock()44 constexpr explicit AlignableBlock() {
45 // Assert within a function, since `Derived` is not complete when this type
46 // is defined.
47 static_assert(is_allocatable_v<Derived>,
48 "Types derived from AlignableBlock must also derive from "
49 "AllocatableBlock");
50 }
51
52 /// @copydoc AllocatableBlock::CanAlloc
53 StatusWithSize DoCanAlloc(Layout layout) const;
54
55 /// @copydoc AllocatableBlock::AllocFirst
56 static BlockResult<Derived> DoAllocFirst(Derived*&& block, Layout layout);
57
58 /// @copydoc AllocatableBlock::AllocLast
59 static BlockResult<Derived> DoAllocLast(Derived*&& block, Layout layout);
60
61 private:
derived()62 constexpr const Derived* derived() const {
63 return static_cast<const Derived*>(this);
64 }
65
66 /// Allocates a block of `new_inner_size` that starts after `leading` bytes.
67 static BlockResult<Derived> DoAllocAligned(Derived*&& block,
68 size_t leading,
69 size_t new_inner_size);
70
71 // BlockWithLayout calls DoAllocFirst
72 template <typename>
73 friend class BlockWithLayout;
74 };
75
76 /// Trait type that allows interrogating a block as to whether it is alignable.
77 template <typename BlockType>
78 struct is_alignable : std::is_base_of<internal::AlignableBase, BlockType> {};
79
80 /// Helper variable template for `is_alignable<BlockType>::value`.
81 template <typename BlockType>
82 inline constexpr bool is_alignable_v = is_alignable<BlockType>::value;
83
84 // Template method implementations.
85
86 template <typename Derived>
DoCanAlloc(Layout layout)87 StatusWithSize AlignableBlock<Derived>::DoCanAlloc(Layout layout) const {
88 // How much extra space is available?
89 auto result = derived()->AllocatableBlock<Derived>::DoCanAlloc(layout);
90 if (!result.ok()) {
91 return result;
92 }
93 size_t extra = result.size();
94
95 // Is the default alignment sufficient?
96 if (layout.alignment() <= Derived::kAlignment) {
97 return StatusWithSize(extra);
98 }
99
100 // What is the last aligned address within the leading extra space?
101 auto addr = cpp20::bit_cast<uintptr_t>(derived()->UsableSpace());
102 uintptr_t aligned_addr;
103 PW_ASSERT(!PW_ADD_OVERFLOW(addr, extra, &aligned_addr));
104 aligned_addr = AlignDown(aligned_addr, layout.alignment());
105
106 // Is there an aligned address within the extra space?
107 if (aligned_addr < addr) {
108 return StatusWithSize::ResourceExhausted();
109 }
110
111 // If splitting the first block, is there enough extra for a valid block?
112 size_t leading_outer_size = aligned_addr - addr;
113 if (leading_outer_size != 0 && leading_outer_size < Derived::kMinOuterSize &&
114 derived()->Prev() == nullptr) {
115 return StatusWithSize::ResourceExhausted();
116 }
117
118 return StatusWithSize(leading_outer_size);
119 }
120
121 template <typename Derived>
DoAllocFirst(Derived * && block,Layout layout)122 BlockResult<Derived> AlignableBlock<Derived>::DoAllocFirst(Derived*&& block,
123 Layout layout) {
124 // Is the default alignment sufficient?
125 if (layout.alignment() <= Derived::kAlignment) {
126 return AllocatableBlock<Derived>::DoAllocFirst(std::move(block), layout);
127 }
128
129 // What is the first aligned address within the leading extra space?
130 size_t size = AlignUp(layout.size(), Derived::kAlignment);
131 layout = Layout(size, layout.alignment());
132 StatusWithSize can_alloc = block->DoCanAlloc(layout);
133 if (!can_alloc.ok()) {
134 return BlockResult(block, can_alloc.status());
135 }
136 size_t extra = can_alloc.size();
137 size_t leading_outer_size = extra - AlignDown(extra, layout.alignment());
138
139 // If splitting the first block, there must be enough for a valid block.
140 if (leading_outer_size != 0 && leading_outer_size <= Derived::kMinOuterSize &&
141 block->Prev() == nullptr) {
142 leading_outer_size += AlignUp(Derived::kMinOuterSize - leading_outer_size,
143 layout.alignment());
144 }
145 if (leading_outer_size > extra) {
146 return BlockResult(block, Status::ResourceExhausted());
147 }
148
149 // Allocate the aligned block.
150 return DoAllocAligned(std::move(block), leading_outer_size, layout.size());
151 }
152
153 template <typename Derived>
DoAllocLast(Derived * && block,Layout layout)154 BlockResult<Derived> AlignableBlock<Derived>::DoAllocLast(Derived*&& block,
155 Layout layout) {
156 // Is the default alignment sufficient?
157 if (layout.alignment() <= Derived::kAlignment) {
158 return AllocatableBlock<Derived>::DoAllocLast(std::move(block), layout);
159 }
160
161 // What is the last aligned address within the leading extra space?
162 size_t size = AlignUp(layout.size(), Derived::kAlignment);
163 layout = Layout(size, layout.alignment());
164 StatusWithSize can_alloc = block->DoCanAlloc(layout);
165 if (!can_alloc.ok()) {
166 return BlockResult(block, can_alloc.status());
167 }
168 size_t leading_outer_size = can_alloc.size();
169
170 // Allocate the aligned block.
171 return DoAllocAligned(std::move(block), leading_outer_size, layout.size());
172 }
173
174 template <typename Derived>
DoAllocAligned(Derived * && block,size_t leading_outer_size,size_t new_inner_size)175 BlockResult<Derived> AlignableBlock<Derived>::DoAllocAligned(
176 Derived*&& block, size_t leading_outer_size, size_t new_inner_size) {
177 // Allocate everything after aligned address.
178 Layout layout(block->InnerSize() - leading_outer_size, Derived::kAlignment);
179 auto alloc_result =
180 AllocatableBlock<Derived>::DoAllocLast(std::move(block), layout);
181 if (!alloc_result.ok()) {
182 return alloc_result;
183 }
184 block = alloc_result.block();
185
186 // Resize the allocation to the requested size.
187 auto resize_result = block->DoResize(new_inner_size);
188 if (!resize_result.ok()) {
189 return resize_result;
190 }
191
192 return BlockResult(
193 block, alloc_result.prev(), resize_result.next(), alloc_result.size());
194 }
195
196 } // namespace pw::allocator
197