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