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 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
61 auto item = list.FindChunk(kN / 2);
62 EXPECT_EQ(item.size(), kN);
63 EXPECT_EQ(item.data(), data);
64 }
65
TEST(FreeList,CanRemoveItem)66 TEST(FreeList, CanRemoveItem) {
67 FreeListBuffer<SIZE> list(example_sizes);
68 constexpr size_t kN = 512;
69
70 byte data[kN] = {std::byte(0)};
71
72 list.AddChunk(std::span(data, kN))
73 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
74 auto status = list.RemoveChunk(std::span(data, kN));
75 EXPECT_EQ(status, OkStatus());
76
77 auto item = list.FindChunk(kN);
78 EXPECT_EQ(item.size(), static_cast<size_t>(0));
79 }
80
TEST(FreeList,FindReturnsSmallestChunk)81 TEST(FreeList, FindReturnsSmallestChunk) {
82 FreeListBuffer<SIZE> list(example_sizes);
83 constexpr size_t kN1 = 512;
84 constexpr size_t kN2 = 1024;
85
86 byte data1[kN1] = {std::byte(0)};
87 byte data2[kN2] = {std::byte(0)};
88
89 list.AddChunk(std::span(data1, kN1))
90 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
91 list.AddChunk(std::span(data2, kN2))
92 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
93
94 auto chunk = list.FindChunk(kN1 / 2);
95 EXPECT_EQ(chunk.size(), kN1);
96 EXPECT_EQ(chunk.data(), data1);
97
98 chunk = list.FindChunk(kN1);
99 EXPECT_EQ(chunk.size(), kN1);
100 EXPECT_EQ(chunk.data(), data1);
101
102 chunk = list.FindChunk(kN1 + 1);
103 EXPECT_EQ(chunk.size(), kN2);
104 EXPECT_EQ(chunk.data(), data2);
105 }
106
TEST(FreeList,FindReturnsCorrectChunkInSameBucket)107 TEST(FreeList, FindReturnsCorrectChunkInSameBucket) {
108 // If we have two values in the same bucket, ensure that the allocation will
109 // pick an appropriately sized one.
110 FreeListBuffer<SIZE> list(example_sizes);
111 constexpr size_t kN1 = 512;
112 constexpr size_t kN2 = 257;
113
114 byte data1[kN1] = {std::byte(0)};
115 byte data2[kN2] = {std::byte(0)};
116
117 // List should now be 257 -> 512 -> NULL
118 list.AddChunk(std::span(data1, kN1))
119 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
120 list.AddChunk(std::span(data2, kN2))
121 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
122
123 auto chunk = list.FindChunk(kN2 + 1);
124 EXPECT_EQ(chunk.size(), kN1);
125 }
126
TEST(FreeList,FindCanMoveUpThroughBuckets)127 TEST(FreeList, FindCanMoveUpThroughBuckets) {
128 // Ensure that finding a chunk will move up through buckets if no appropriate
129 // chunks were found in a given bucket
130 FreeListBuffer<SIZE> list(example_sizes);
131 constexpr size_t kN1 = 257;
132 constexpr size_t kN2 = 513;
133
134 byte data1[kN1] = {std::byte(0)};
135 byte data2[kN2] = {std::byte(0)};
136
137 // List should now be:
138 // bkt[3] (257 bytes up to 512 bytes) -> 257 -> NULL
139 // bkt[4] (513 bytes up to 1024 bytes) -> 513 -> NULL
140 list.AddChunk(std::span(data1, kN1))
141 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
142 list.AddChunk(std::span(data2, kN2))
143 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
144
145 // Request a 300 byte chunk. This should return the 513 byte one
146 auto chunk = list.FindChunk(kN1 + 1);
147 EXPECT_EQ(chunk.size(), kN2);
148 }
149
TEST(FreeList,RemoveUnknownChunkReturnsNotFound)150 TEST(FreeList, RemoveUnknownChunkReturnsNotFound) {
151 FreeListBuffer<SIZE> list(example_sizes);
152 constexpr size_t kN = 512;
153
154 byte data[kN] = {std::byte(0)};
155 byte data2[kN] = {std::byte(0)};
156
157 list.AddChunk(std::span(data, kN))
158 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
159 auto status = list.RemoveChunk(std::span(data2, kN));
160 EXPECT_EQ(status, Status::NotFound());
161 }
162
TEST(FreeList,CanStoreMultipleChunksPerBucket)163 TEST(FreeList, CanStoreMultipleChunksPerBucket) {
164 FreeListBuffer<SIZE> list(example_sizes);
165 constexpr size_t kN = 512;
166
167 byte data1[kN] = {std::byte(0)};
168 byte data2[kN] = {std::byte(0)};
169
170 list.AddChunk(std::span(data1, kN))
171 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
172 list.AddChunk(std::span(data2, kN))
173 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
174
175 auto chunk1 = list.FindChunk(kN);
176 list.RemoveChunk(chunk1)
177 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
178 auto chunk2 = list.FindChunk(kN);
179 list.RemoveChunk(chunk2)
180 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
181
182 // Ordering of the chunks doesn't matter
183 EXPECT_TRUE(chunk1.data() != chunk2.data());
184 EXPECT_TRUE(chunk1.data() == data1 || chunk1.data() == data2);
185 EXPECT_TRUE(chunk2.data() == data1 || chunk2.data() == data2);
186 }
187
188 } // namespace pw::allocator
189