1 // Copyright 2020 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 
15 #include "pw_allocator/block.h"
16 
17 #include <cstring>
18 #include <span>
19 
20 #include "gtest/gtest.h"
21 
22 using std::byte;
23 
24 namespace pw::allocator {
25 
TEST(Block,CanCreateSingleBlock)26 TEST(Block, CanCreateSingleBlock) {
27   constexpr size_t kN = 200;
28   alignas(Block*) byte bytes[kN];
29 
30   Block* block = nullptr;
31   auto status = Block::Init(std::span(bytes, kN), &block);
32 
33   ASSERT_EQ(status, OkStatus());
34   EXPECT_EQ(block->OuterSize(), kN);
35   EXPECT_EQ(block->InnerSize(),
36             kN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
37   EXPECT_EQ(block->Prev(), nullptr);
38   EXPECT_EQ(block->Next(), (Block*)((uintptr_t)block + kN));
39   EXPECT_EQ(block->Used(), false);
40   EXPECT_EQ(block->Last(), true);
41 }
42 
TEST(Block,CannotCreateUnalignedSingleBlock)43 TEST(Block, CannotCreateUnalignedSingleBlock) {
44   constexpr size_t kN = 1024;
45 
46   // Force alignment, so we can un-force it below
47   alignas(Block*) byte bytes[kN];
48   byte* byte_ptr = bytes;
49 
50   Block* block = nullptr;
51   auto status = Block::Init(std::span(byte_ptr + 1, kN - 1), &block);
52 
53   EXPECT_EQ(status, Status::InvalidArgument());
54 }
55 
TEST(Block,CannotCreateTooSmallBlock)56 TEST(Block, CannotCreateTooSmallBlock) {
57   constexpr size_t kN = 2;
58   alignas(Block*) byte bytes[kN];
59   Block* block = nullptr;
60   auto status = Block::Init(std::span(bytes, kN), &block);
61 
62   EXPECT_EQ(status, Status::InvalidArgument());
63 }
64 
TEST(Block,CanSplitBlock)65 TEST(Block, CanSplitBlock) {
66   constexpr size_t kN = 1024;
67   constexpr size_t kSplitN = 512;
68   alignas(Block*) byte bytes[kN];
69 
70   Block* block = nullptr;
71   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
72 
73   Block* next_block = nullptr;
74   auto status = block->Split(kSplitN, &next_block);
75 
76   ASSERT_EQ(status, OkStatus());
77   EXPECT_EQ(block->InnerSize(), kSplitN);
78   EXPECT_EQ(block->OuterSize(),
79             kSplitN + sizeof(Block) + 2 * PW_ALLOCATOR_POISON_OFFSET);
80   EXPECT_EQ(block->Last(), false);
81 
82   EXPECT_EQ(next_block->OuterSize(),
83             kN - kSplitN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
84   EXPECT_EQ(next_block->Used(), false);
85   EXPECT_EQ(next_block->Last(), true);
86 
87   EXPECT_EQ(block->Next(), next_block);
88   EXPECT_EQ(next_block->Prev(), block);
89 }
90 
TEST(Block,CanSplitBlockUnaligned)91 TEST(Block, CanSplitBlockUnaligned) {
92   constexpr size_t kN = 1024;
93   constexpr size_t kSplitN = 513;
94 
95   alignas(Block*) byte bytes[kN];
96 
97   // We should split at sizeof(Block) + kSplitN bytes. Then
98   // we need to round that up to an alignof(Block*) boundary.
99   uintptr_t split_addr = ((uintptr_t)&bytes) + kSplitN;
100   split_addr += alignof(Block*) - (split_addr % alignof(Block*));
101   uintptr_t split_len = split_addr - (uintptr_t)&bytes;
102 
103   Block* block = nullptr;
104   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
105 
106   Block* next_block = nullptr;
107   auto status = block->Split(kSplitN, &next_block);
108 
109   ASSERT_EQ(status, OkStatus());
110   EXPECT_EQ(block->InnerSize(), split_len);
111   EXPECT_EQ(block->OuterSize(),
112             split_len + sizeof(Block) + 2 * PW_ALLOCATOR_POISON_OFFSET);
113   EXPECT_EQ(next_block->OuterSize(),
114             kN - split_len - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
115   EXPECT_EQ(next_block->Used(), false);
116   EXPECT_EQ(block->Next(), next_block);
117   EXPECT_EQ(next_block->Prev(), block);
118 }
119 
TEST(Block,CanSplitMidBlock)120 TEST(Block, CanSplitMidBlock) {
121   // Split once, then split the original block again to ensure that the
122   // pointers get rewired properly.
123   // I.e.
124   // [[             BLOCK 1            ]]
125   // block1->Split()
126   // [[       BLOCK1       ]][[ BLOCK2 ]]
127   // block1->Split()
128   // [[ BLOCK1 ]][[ BLOCK3 ]][[ BLOCK2 ]]
129 
130   constexpr size_t kN = 1024;
131   constexpr size_t kSplit1 = 512;
132   constexpr size_t kSplit2 = 256;
133   alignas(Block*) byte bytes[kN];
134 
135   Block* block = nullptr;
136   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
137 
138   Block* block2 = nullptr;
139   block->Split(kSplit1, &block2);
140 
141   Block* block3 = nullptr;
142   block->Split(kSplit2, &block3);
143 
144   EXPECT_EQ(block->Next(), block3);
145   EXPECT_EQ(block3->Next(), block2);
146   EXPECT_EQ(block2->Prev(), block3);
147   EXPECT_EQ(block3->Prev(), block);
148 }
149 
TEST(Block,CannotSplitBlockWithoutHeaderSpace)150 TEST(Block, CannotSplitBlockWithoutHeaderSpace) {
151   constexpr size_t kN = 1024;
152   constexpr size_t kSplitN =
153       kN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET - 1;
154   alignas(Block*) byte bytes[kN];
155 
156   Block* block = nullptr;
157   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
158 
159   Block* next_block = nullptr;
160   auto status = block->Split(kSplitN, &next_block);
161 
162   EXPECT_EQ(status, Status::ResourceExhausted());
163   EXPECT_EQ(next_block, nullptr);
164 }
165 
TEST(Block,MustProvideNextBlockPointer)166 TEST(Block, MustProvideNextBlockPointer) {
167   constexpr size_t kN = 1024;
168   constexpr size_t kSplitN = kN - sizeof(Block) - 1;
169   alignas(Block*) byte bytes[kN];
170 
171   Block* block = nullptr;
172   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
173 
174   auto status = block->Split(kSplitN, nullptr);
175   EXPECT_EQ(status, Status::InvalidArgument());
176 }
177 
TEST(Block,CannotMakeBlockLargerInSplit)178 TEST(Block, CannotMakeBlockLargerInSplit) {
179   // Ensure that we can't ask for more space than the block actually has...
180   constexpr size_t kN = 1024;
181   alignas(Block*) byte bytes[kN];
182 
183   Block* block = nullptr;
184   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
185 
186   Block* next_block = nullptr;
187   auto status = block->Split(block->InnerSize() + 1, &next_block);
188 
189   EXPECT_EQ(status, Status::OutOfRange());
190 }
191 
TEST(Block,CannotMakeSecondBlockLargerInSplit)192 TEST(Block, CannotMakeSecondBlockLargerInSplit) {
193   // Ensure that the second block in split is at least of the size of header.
194   constexpr size_t kN = 1024;
195   alignas(Block*) byte bytes[kN];
196 
197   Block* block = nullptr;
198   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
199 
200   Block* next_block = nullptr;
201   auto status = block->Split(
202       block->InnerSize() - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET + 1,
203       &next_block);
204 
205   ASSERT_EQ(status, Status::ResourceExhausted());
206   EXPECT_EQ(next_block, nullptr);
207 }
208 
TEST(Block,CanMakeZeroSizeFirstBlock)209 TEST(Block, CanMakeZeroSizeFirstBlock) {
210   // This block does support splitting with zero payload size.
211   constexpr size_t kN = 1024;
212   alignas(Block*) byte bytes[kN];
213 
214   Block* block = nullptr;
215   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
216 
217   Block* next_block = nullptr;
218   auto status = block->Split(0, &next_block);
219 
220   ASSERT_EQ(status, OkStatus());
221   EXPECT_EQ(block->InnerSize(), static_cast<size_t>(0));
222 }
223 
TEST(Block,CanMakeZeroSizeSecondBlock)224 TEST(Block, CanMakeZeroSizeSecondBlock) {
225   // Likewise, the split block can be zero-width.
226   constexpr size_t kN = 1024;
227   alignas(Block*) byte bytes[kN];
228 
229   Block* block = nullptr;
230   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
231 
232   Block* next_block = nullptr;
233   auto status = block->Split(
234       block->InnerSize() - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET,
235       &next_block);
236 
237   ASSERT_EQ(status, OkStatus());
238   EXPECT_EQ(next_block->InnerSize(), static_cast<size_t>(0));
239 }
240 
TEST(Block,CanMarkBlockUsed)241 TEST(Block, CanMarkBlockUsed) {
242   constexpr size_t kN = 1024;
243   alignas(Block*) byte bytes[kN];
244 
245   Block* block = nullptr;
246   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
247 
248   block->MarkUsed();
249   EXPECT_EQ(block->Used(), true);
250 
251   // Mark used packs that data into the next pointer. Check that it's still
252   // valid
253   EXPECT_EQ(block->Next(), (Block*)((uintptr_t)block + kN));
254 
255   block->MarkFree();
256   EXPECT_EQ(block->Used(), false);
257 }
258 
TEST(Block,CannotSplitUsedBlock)259 TEST(Block, CannotSplitUsedBlock) {
260   constexpr size_t kN = 1024;
261   alignas(Block*) byte bytes[kN];
262 
263   Block* block = nullptr;
264   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
265 
266   block->MarkUsed();
267 
268   Block* next_block = nullptr;
269   auto status = block->Split(512, &next_block);
270   EXPECT_EQ(status, Status::FailedPrecondition());
271 }
272 
TEST(Block,CanMergeWithNextBlock)273 TEST(Block, CanMergeWithNextBlock) {
274   // Do the three way merge from "CanSplitMidBlock", and let's
275   // merge block 3 and 2
276   constexpr size_t kN = 1024;
277   constexpr size_t kSplit1 = 512;
278   constexpr size_t kSplit2 = 256;
279   alignas(Block*) byte bytes[kN];
280 
281   Block* block = nullptr;
282   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
283 
284   Block* block2 = nullptr;
285   block->Split(kSplit1, &block2);
286 
287   Block* block3 = nullptr;
288   block->Split(kSplit2, &block3);
289 
290   EXPECT_EQ(block3->MergeNext(), OkStatus());
291 
292   EXPECT_EQ(block->Next(), block3);
293   EXPECT_EQ(block3->Prev(), block);
294   EXPECT_EQ(block->InnerSize(), kSplit2);
295 
296   // The resulting "right hand" block should have an outer size of 1024 - 256 -
297   // sizeof(Block) - 2*PW_ALLOCATOR_POISON_OFFSET, which accounts for the first
298   // block.
299   EXPECT_EQ(block3->OuterSize(),
300             kN - kSplit2 - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
301 }
302 
TEST(Block,CannotMergeWithFirstOrLastBlock)303 TEST(Block, CannotMergeWithFirstOrLastBlock) {
304   constexpr size_t kN = 1024;
305   alignas(Block*) byte bytes[kN];
306 
307   // Do a split, just to sanity check that the checks on Next/Prev are
308   // different...
309   Block* block = nullptr;
310   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
311 
312   Block* next_block = nullptr;
313   block->Split(512, &next_block);
314 
315   EXPECT_EQ(next_block->MergeNext(), Status::OutOfRange());
316   EXPECT_EQ(block->MergePrev(), Status::OutOfRange());
317 }
318 
TEST(Block,CannotMergeUsedBlock)319 TEST(Block, CannotMergeUsedBlock) {
320   constexpr size_t kN = 1024;
321   alignas(Block*) byte bytes[kN];
322 
323   // Do a split, just to sanity check that the checks on Next/Prev are
324   // different...
325   Block* block = nullptr;
326   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
327 
328   Block* next_block = nullptr;
329   block->Split(512, &next_block);
330 
331   block->MarkUsed();
332   EXPECT_EQ(block->MergeNext(), Status::FailedPrecondition());
333   EXPECT_EQ(next_block->MergePrev(), Status::FailedPrecondition());
334 }
335 
TEST(Block,CanCheckValidBlock)336 TEST(Block, CanCheckValidBlock) {
337   constexpr size_t kN = 1024;
338   alignas(Block*) byte bytes[kN];
339 
340   Block* first_block = nullptr;
341   EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus());
342 
343   Block* second_block = nullptr;
344   first_block->Split(512, &second_block);
345 
346   Block* third_block = nullptr;
347   second_block->Split(256, &third_block);
348 
349   EXPECT_EQ(first_block->IsValid(), true);
350   EXPECT_EQ(second_block->IsValid(), true);
351   EXPECT_EQ(third_block->IsValid(), true);
352 }
353 
TEST(Block,CanCheckInalidBlock)354 TEST(Block, CanCheckInalidBlock) {
355   constexpr size_t kN = 1024;
356   alignas(Block*) byte bytes[kN];
357 
358   Block* first_block = nullptr;
359   EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus());
360 
361   Block* second_block = nullptr;
362   first_block->Split(512, &second_block);
363 
364   Block* third_block = nullptr;
365   second_block->Split(256, &third_block);
366 
367   Block* fourth_block = nullptr;
368   third_block->Split(128, &fourth_block);
369 
370   std::byte* next_ptr = reinterpret_cast<std::byte*>(first_block);
371   memcpy(next_ptr, second_block, sizeof(void*));
372   EXPECT_EQ(first_block->IsValid(), false);
373   EXPECT_EQ(second_block->IsValid(), false);
374   EXPECT_EQ(third_block->IsValid(), true);
375   EXPECT_EQ(fourth_block->IsValid(), true);
376 
377 #if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
378   std::byte fault_poison[PW_ALLOCATOR_POISON_OFFSET] = {std::byte(0)};
379   std::byte* front_poison =
380       reinterpret_cast<std::byte*>(third_block) + sizeof(*third_block);
381   memcpy(front_poison, fault_poison, PW_ALLOCATOR_POISON_OFFSET);
382   EXPECT_EQ(third_block->IsValid(), false);
383 
384   std::byte* end_poison =
385       reinterpret_cast<std::byte*>(fourth_block) + sizeof(*fourth_block);
386   memcpy(end_poison, fault_poison, PW_ALLOCATOR_POISON_OFFSET);
387   EXPECT_EQ(fourth_block->IsValid(), false);
388 #endif  // PW_ALLOCATOR_POISON_ENABLE
389 }
390 
TEST(Block,CanPoisonBlock)391 TEST(Block, CanPoisonBlock) {
392 #if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
393   constexpr size_t kN = 1024;
394   alignas(Block*) byte bytes[kN];
395 
396   Block* first_block = nullptr;
397   EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus());
398 
399   Block* second_block = nullptr;
400   first_block->Split(512, &second_block);
401 
402   Block* third_block = nullptr;
403   second_block->Split(256, &third_block);
404 
405   EXPECT_EQ(first_block->IsValid(), true);
406   EXPECT_EQ(second_block->IsValid(), true);
407   EXPECT_EQ(third_block->IsValid(), true);
408 #endif  // PW_ALLOCATOR_POISON_ENABLE
409 }
410 
411 }  // namespace pw::allocator
412