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/freelist.h"
16
17 #include <span>
18
19 #include "gtest/gtest.h"
20 #include "pw_status/status.h"
21
22 using std::byte;
23
24 namespace pw::allocator {
25
26 static const size_t SIZE = 8;
27 static const std::array<size_t, SIZE> example_sizes = {
28 64, 128, 256, 512, 1024, 2048, 4096, 8192};
29
TEST(FreeList,EmptyListHasNoMembers)30 TEST(FreeList, EmptyListHasNoMembers) {
31 FreeListBuffer<SIZE> list(example_sizes);
32
33 auto item = list.FindChunk(4);
34 EXPECT_EQ(item.size(), static_cast<size_t>(0));
35 item = list.FindChunk(128);
36 EXPECT_EQ(item.size(), static_cast<size_t>(0));
37 }
38
TEST(FreeList,CanRetrieveAddedMember)39 TEST(FreeList, CanRetrieveAddedMember) {
40 FreeListBuffer<SIZE> list(example_sizes);
41 constexpr size_t kN = 512;
42
43 byte data[kN] = {std::byte(0)};
44
45 auto status = list.AddChunk(std::span(data, kN));
46 EXPECT_EQ(status, OkStatus());
47
48 auto item = list.FindChunk(kN);
49 EXPECT_EQ(item.size(), kN);
50 EXPECT_EQ(item.data(), data);
51 }
52
TEST(FreeList,CanRetrieveAddedMemberForSmallerSize)53 TEST(FreeList, CanRetrieveAddedMemberForSmallerSize) {
54 FreeListBuffer<SIZE> list(example_sizes);
55 constexpr size_t kN = 512;
56
57 byte data[kN] = {std::byte(0)};
58
59 list.AddChunk(std::span(data, kN));
60 auto item = list.FindChunk(kN / 2);
61 EXPECT_EQ(item.size(), kN);
62 EXPECT_EQ(item.data(), data);
63 }
64
TEST(FreeList,CanRemoveItem)65 TEST(FreeList, CanRemoveItem) {
66 FreeListBuffer<SIZE> list(example_sizes);
67 constexpr size_t kN = 512;
68
69 byte data[kN] = {std::byte(0)};
70
71 list.AddChunk(std::span(data, kN));
72 auto status = list.RemoveChunk(std::span(data, kN));
73 EXPECT_EQ(status, OkStatus());
74
75 auto item = list.FindChunk(kN);
76 EXPECT_EQ(item.size(), static_cast<size_t>(0));
77 }
78
TEST(FreeList,FindReturnsSmallestChunk)79 TEST(FreeList, FindReturnsSmallestChunk) {
80 FreeListBuffer<SIZE> list(example_sizes);
81 constexpr size_t kN1 = 512;
82 constexpr size_t kN2 = 1024;
83
84 byte data1[kN1] = {std::byte(0)};
85 byte data2[kN2] = {std::byte(0)};
86
87 list.AddChunk(std::span(data1, kN1));
88 list.AddChunk(std::span(data2, kN2));
89
90 auto chunk = list.FindChunk(kN1 / 2);
91 EXPECT_EQ(chunk.size(), kN1);
92 EXPECT_EQ(chunk.data(), data1);
93
94 chunk = list.FindChunk(kN1);
95 EXPECT_EQ(chunk.size(), kN1);
96 EXPECT_EQ(chunk.data(), data1);
97
98 chunk = list.FindChunk(kN1 + 1);
99 EXPECT_EQ(chunk.size(), kN2);
100 EXPECT_EQ(chunk.data(), data2);
101 }
102
TEST(FreeList,FindReturnsCorrectChunkInSameBucket)103 TEST(FreeList, FindReturnsCorrectChunkInSameBucket) {
104 // If we have two values in the same bucket, ensure that the allocation will
105 // pick an appropriately sized one.
106 FreeListBuffer<SIZE> list(example_sizes);
107 constexpr size_t kN1 = 512;
108 constexpr size_t kN2 = 257;
109
110 byte data1[kN1] = {std::byte(0)};
111 byte data2[kN2] = {std::byte(0)};
112
113 // List should now be 257 -> 512 -> NULL
114 list.AddChunk(std::span(data1, kN1));
115 list.AddChunk(std::span(data2, kN2));
116
117 auto chunk = list.FindChunk(kN2 + 1);
118 EXPECT_EQ(chunk.size(), kN1);
119 }
120
TEST(FreeList,FindCanMoveUpThroughBuckets)121 TEST(FreeList, FindCanMoveUpThroughBuckets) {
122 // Ensure that finding a chunk will move up through buckets if no appropriate
123 // chunks were found in a given bucket
124 FreeListBuffer<SIZE> list(example_sizes);
125 constexpr size_t kN1 = 257;
126 constexpr size_t kN2 = 513;
127
128 byte data1[kN1] = {std::byte(0)};
129 byte data2[kN2] = {std::byte(0)};
130
131 // List should now be:
132 // bkt[3] (257 bytes up to 512 bytes) -> 257 -> NULL
133 // bkt[4] (513 bytes up to 1024 bytes) -> 513 -> NULL
134 list.AddChunk(std::span(data1, kN1));
135 list.AddChunk(std::span(data2, kN2));
136
137 // Request a 300 byte chunk. This should return the 513 byte one
138 auto chunk = list.FindChunk(kN1 + 1);
139 EXPECT_EQ(chunk.size(), kN2);
140 }
141
TEST(FreeList,RemoveUnknownChunkReturnsNotFound)142 TEST(FreeList, RemoveUnknownChunkReturnsNotFound) {
143 FreeListBuffer<SIZE> list(example_sizes);
144 constexpr size_t kN = 512;
145
146 byte data[kN] = {std::byte(0)};
147 byte data2[kN] = {std::byte(0)};
148
149 list.AddChunk(std::span(data, kN));
150 auto status = list.RemoveChunk(std::span(data2, kN));
151 EXPECT_EQ(status, Status::NotFound());
152 }
153
TEST(FreeList,CanStoreMultipleChunksPerBucket)154 TEST(FreeList, CanStoreMultipleChunksPerBucket) {
155 FreeListBuffer<SIZE> list(example_sizes);
156 constexpr size_t kN = 512;
157
158 byte data1[kN] = {std::byte(0)};
159 byte data2[kN] = {std::byte(0)};
160
161 list.AddChunk(std::span(data1, kN));
162 list.AddChunk(std::span(data2, kN));
163
164 auto chunk1 = list.FindChunk(kN);
165 list.RemoveChunk(chunk1);
166 auto chunk2 = list.FindChunk(kN);
167 list.RemoveChunk(chunk2);
168
169 // Ordering of the chunks doesn't matter
170 EXPECT_TRUE(chunk1.data() != chunk2.data());
171 EXPECT_TRUE(chunk1.data() == data1 || chunk1.data() == data2);
172 EXPECT_TRUE(chunk2.data() == data1 || chunk2.data() == data2);
173 }
174
175 } // namespace pw::allocator
176