1 // Copyright 2019 The Dawn Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://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,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include <gtest/gtest.h>
16 #include "dawn_native/BuddyAllocator.h"
17
18 using namespace dawn_native;
19
20 constexpr uint64_t BuddyAllocator::kInvalidOffset;
21
22 // Verify the buddy allocator with a basic test.
TEST(BuddyAllocatorTests,SingleBlock)23 TEST(BuddyAllocatorTests, SingleBlock) {
24 // After one 32 byte allocation:
25 //
26 // Level --------------------------------
27 // 0 32 | A |
28 // --------------------------------
29 //
30 constexpr uint64_t maxBlockSize = 32;
31 BuddyAllocator allocator(maxBlockSize);
32
33 // Check that we cannot allocate a oversized block.
34 ASSERT_EQ(allocator.Allocate(maxBlockSize * 2), BuddyAllocator::kInvalidOffset);
35
36 // Check that we cannot allocate a zero sized block.
37 ASSERT_EQ(allocator.Allocate(0u), BuddyAllocator::kInvalidOffset);
38
39 // Allocate the block.
40 uint64_t blockOffset = allocator.Allocate(maxBlockSize);
41 ASSERT_EQ(blockOffset, 0u);
42
43 // Check that we are full.
44 ASSERT_EQ(allocator.Allocate(maxBlockSize), BuddyAllocator::kInvalidOffset);
45 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 0u);
46
47 // Deallocate the block.
48 allocator.Deallocate(blockOffset);
49 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
50 }
51
52 // Verify multiple allocations succeeds using a buddy allocator.
TEST(BuddyAllocatorTests,MultipleBlocks)53 TEST(BuddyAllocatorTests, MultipleBlocks) {
54 // Fill every level in the allocator (order-n = 2^n)
55 const uint64_t maxBlockSize = (1ull << 16);
56 for (uint64_t order = 1; (1ull << order) <= maxBlockSize; order++) {
57 BuddyAllocator allocator(maxBlockSize);
58
59 uint64_t blockSize = (1ull << order);
60 for (uint32_t blocki = 0; blocki < (maxBlockSize / blockSize); blocki++) {
61 ASSERT_EQ(allocator.Allocate(blockSize), blockSize * blocki);
62 }
63 }
64 }
65
66 // Verify that a single allocation succeeds using a buddy allocator.
TEST(BuddyAllocatorTests,SingleSplitBlock)67 TEST(BuddyAllocatorTests, SingleSplitBlock) {
68 // After one 8 byte allocation:
69 //
70 // Level --------------------------------
71 // 0 32 | S |
72 // --------------------------------
73 // 1 16 | S | F | S - split
74 // -------------------------------- F - free
75 // 2 8 | A | F | | | A - allocated
76 // --------------------------------
77 //
78 constexpr uint64_t maxBlockSize = 32;
79 BuddyAllocator allocator(maxBlockSize);
80
81 // Allocate block (splits two blocks).
82 uint64_t blockOffset = allocator.Allocate(8);
83 ASSERT_EQ(blockOffset, 0u);
84 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u);
85
86 // Deallocate block (merges two blocks).
87 allocator.Deallocate(blockOffset);
88 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
89
90 // Check that we cannot allocate a block that is oversized.
91 ASSERT_EQ(allocator.Allocate(maxBlockSize * 2), BuddyAllocator::kInvalidOffset);
92
93 // Re-allocate the largest block allowed after merging.
94 blockOffset = allocator.Allocate(maxBlockSize);
95 ASSERT_EQ(blockOffset, 0u);
96
97 allocator.Deallocate(blockOffset);
98 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
99 }
100
101 // Verify that a multiple allocated blocks can be removed in the free-list.
TEST(BuddyAllocatorTests,MultipleSplitBlocks)102 TEST(BuddyAllocatorTests, MultipleSplitBlocks) {
103 // After four 16 byte allocations:
104 //
105 // Level --------------------------------
106 // 0 32 | S |
107 // --------------------------------
108 // 1 16 | S | S | S - split
109 // -------------------------------- F - free
110 // 2 8 | Aa | Ab | Ac | Ad | A - allocated
111 // --------------------------------
112 //
113 constexpr uint64_t maxBlockSize = 32;
114 BuddyAllocator allocator(maxBlockSize);
115
116 // Populates the free-list with four blocks at Level2.
117
118 // Allocate "a" block (two splits).
119 constexpr uint64_t blockSizeInBytes = 8;
120 uint64_t blockOffsetA = allocator.Allocate(blockSizeInBytes);
121 ASSERT_EQ(blockOffsetA, 0u);
122 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u);
123
124 // Allocate "b" block.
125 uint64_t blockOffsetB = allocator.Allocate(blockSizeInBytes);
126 ASSERT_EQ(blockOffsetB, blockSizeInBytes);
127 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
128
129 // Allocate "c" block (three splits).
130 uint64_t blockOffsetC = allocator.Allocate(blockSizeInBytes);
131 ASSERT_EQ(blockOffsetC, blockOffsetB + blockSizeInBytes);
132 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
133
134 // Allocate "d" block.
135 uint64_t blockOffsetD = allocator.Allocate(blockSizeInBytes);
136 ASSERT_EQ(blockOffsetD, blockOffsetC + blockSizeInBytes);
137 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 0u);
138
139 // Deallocate "d" block.
140 // FreeList[Level2] = [BlockD] -> x
141 allocator.Deallocate(blockOffsetD);
142 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
143
144 // Deallocate "b" block.
145 // FreeList[Level2] = [BlockB] -> [BlockD] -> x
146 allocator.Deallocate(blockOffsetB);
147 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u);
148
149 // Deallocate "c" block (one merges).
150 // FreeList[Level1] = [BlockCD] -> x
151 // FreeList[Level2] = [BlockB] -> x
152 allocator.Deallocate(blockOffsetC);
153 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u);
154
155 // Deallocate "a" block (two merges).
156 // FreeList[Level0] = [BlockABCD] -> x
157 allocator.Deallocate(blockOffsetA);
158 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
159 }
160
161 // Verify the buddy allocator can handle allocations of various sizes.
TEST(BuddyAllocatorTests,MultipleSplitBlockIncreasingSize)162 TEST(BuddyAllocatorTests, MultipleSplitBlockIncreasingSize) {
163 // After four Level4-to-Level1 byte then one L4 block allocations:
164 //
165 // Level -----------------------------------------------------------------
166 // 0 512 | S |
167 // -----------------------------------------------------------------
168 // 1 256 | S | A |
169 // -----------------------------------------------------------------
170 // 2 128 | S | A | | |
171 // -----------------------------------------------------------------
172 // 3 64 | S | A | | | | | | |
173 // -----------------------------------------------------------------
174 // 4 32 | A | F | | | | | | | | | | | | | | |
175 // -----------------------------------------------------------------
176 //
177 constexpr uint64_t maxBlockSize = 512;
178 BuddyAllocator allocator(maxBlockSize);
179
180 ASSERT_EQ(allocator.Allocate(32), 0ull);
181 ASSERT_EQ(allocator.Allocate(64), 64ull);
182 ASSERT_EQ(allocator.Allocate(128), 128ull);
183 ASSERT_EQ(allocator.Allocate(256), 256ull);
184
185 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
186
187 // Fill in the last free block.
188 ASSERT_EQ(allocator.Allocate(32), 32ull);
189
190 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 0u);
191
192 // Check if we're full.
193 ASSERT_EQ(allocator.Allocate(32), BuddyAllocator::kInvalidOffset);
194 }
195
196 // Verify very small allocations using a larger allocator works correctly.
TEST(BuddyAllocatorTests,MultipleSplitBlocksVariableSizes)197 TEST(BuddyAllocatorTests, MultipleSplitBlocksVariableSizes) {
198 // After allocating four pairs of one 64 byte block and one 32 byte block.
199 //
200 // Level -----------------------------------------------------------------
201 // 0 512 | S |
202 // -----------------------------------------------------------------
203 // 1 256 | S | S |
204 // -----------------------------------------------------------------
205 // 2 128 | S | S | S | F |
206 // -----------------------------------------------------------------
207 // 3 64 | A | S | A | A | S | A | | |
208 // -----------------------------------------------------------------
209 // 4 32 | | | A | A | | | | | A | A | | | | | | |
210 // -----------------------------------------------------------------
211 //
212 constexpr uint64_t maxBlockSize = 512;
213 BuddyAllocator allocator(maxBlockSize);
214
215 ASSERT_EQ(allocator.Allocate(64), 0ull);
216 ASSERT_EQ(allocator.Allocate(32), 64ull);
217
218 ASSERT_EQ(allocator.Allocate(64), 128ull);
219 ASSERT_EQ(allocator.Allocate(32), 96ull);
220
221 ASSERT_EQ(allocator.Allocate(64), 192ull);
222 ASSERT_EQ(allocator.Allocate(32), 256ull);
223
224 ASSERT_EQ(allocator.Allocate(64), 320ull);
225 ASSERT_EQ(allocator.Allocate(32), 288ull);
226
227 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
228 }
229
230 // Verify the buddy allocator can deal with bad fragmentation.
TEST(BuddyAllocatorTests,MultipleSplitBlocksInterleaved)231 TEST(BuddyAllocatorTests, MultipleSplitBlocksInterleaved) {
232 // Allocate every leaf then de-allocate every other of those allocations.
233 //
234 // Level -----------------------------------------------------------------
235 // 0 512 | S |
236 // -----------------------------------------------------------------
237 // 1 256 | S | S |
238 // -----------------------------------------------------------------
239 // 2 128 | S | S | S | S |
240 // -----------------------------------------------------------------
241 // 3 64 | S | S | S | S | S | S | S | S |
242 // -----------------------------------------------------------------
243 // 4 32 | A | F | A | F | A | F | A | F | A | F | A | F | A | F | A | F |
244 // -----------------------------------------------------------------
245 //
246 constexpr uint64_t maxBlockSize = 512;
247 BuddyAllocator allocator(maxBlockSize);
248
249 // Allocate leaf blocks
250 constexpr uint64_t minBlockSizeInBytes = 32;
251 std::vector<uint64_t> blockOffsets;
252 for (uint64_t i = 0; i < maxBlockSize / minBlockSizeInBytes; i++) {
253 blockOffsets.push_back(allocator.Allocate(minBlockSizeInBytes));
254 }
255
256 // Free every other leaf block.
257 for (size_t count = 1; count < blockOffsets.size(); count += 2) {
258 allocator.Deallocate(blockOffsets[count]);
259 }
260
261 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 8u);
262 }
263
264 // Verify the buddy allocator can deal with multiple allocations with mixed alignments.
TEST(BuddyAllocatorTests,SameSizeVariousAlignment)265 TEST(BuddyAllocatorTests, SameSizeVariousAlignment) {
266 // After two 8 byte allocations with 16 byte alignment then one 8 byte allocation with 8 byte
267 // alignment.
268 //
269 // Level --------------------------------
270 // 0 32 | S |
271 // --------------------------------
272 // 1 16 | S | S | S - split
273 // -------------------------------- F - free
274 // 2 8 | Aa | F | Ab | Ac | A - allocated
275 // --------------------------------
276 //
277 BuddyAllocator allocator(32);
278
279 // Allocate Aa (two splits).
280 ASSERT_EQ(allocator.Allocate(8, 16), 0u);
281 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u);
282
283 // Allocate Ab (skip Aa buddy due to alignment and perform another split).
284 ASSERT_EQ(allocator.Allocate(8, 16), 16u);
285
286 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u);
287
288 // Check that we cannot fit another.
289 ASSERT_EQ(allocator.Allocate(8, 16), BuddyAllocator::kInvalidOffset);
290
291 // Allocate Ac (zero splits and Ab's buddy is now the first free block).
292 ASSERT_EQ(allocator.Allocate(8, 8), 24u);
293
294 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
295 }
296
297 // Verify the buddy allocator can deal with multiple allocations with equal alignments.
TEST(BuddyAllocatorTests,VariousSizeSameAlignment)298 TEST(BuddyAllocatorTests, VariousSizeSameAlignment) {
299 // After two 8 byte allocations with 4 byte alignment then one 16 byte allocation with 4 byte
300 // alignment.
301 //
302 // Level --------------------------------
303 // 0 32 | S |
304 // --------------------------------
305 // 1 16 | S | Ac | S - split
306 // -------------------------------- F - free
307 // 2 8 | Aa | Ab | | A - allocated
308 // --------------------------------
309 //
310 constexpr uint64_t maxBlockSize = 32;
311 constexpr uint64_t alignment = 4;
312 BuddyAllocator allocator(maxBlockSize);
313
314 // Allocate block Aa (two splits)
315 ASSERT_EQ(allocator.Allocate(8, alignment), 0u);
316 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u);
317
318 // Allocate block Ab (Aa's buddy)
319 ASSERT_EQ(allocator.Allocate(8, alignment), 8u);
320
321 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u);
322
323 // Check that we can still allocate Ac.
324 ASSERT_EQ(allocator.Allocate(16, alignment), 16ull);
325
326 ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 0u);
327 }
328