Line data Source code
1 : // Copyright 2018 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include "src/base/region-allocator.h"
6 : #include "test/unittests/test-utils.h"
7 :
8 : #include "testing/gtest/include/gtest/gtest.h"
9 :
10 : namespace v8 {
11 : namespace base {
12 :
13 : using Address = RegionAllocator::Address;
14 : using v8::internal::KB;
15 : using v8::internal::MB;
16 :
17 0 : class RegionAllocatorTest : public ::testing::TestWithParam<int> {};
18 :
19 15373 : TEST(RegionAllocatorTest, SimpleAllocateRegionAt) {
20 : const size_t kPageSize = 4 * KB;
21 : const size_t kPageCount = 16;
22 : const size_t kSize = kPageSize * kPageCount;
23 : const Address kBegin = static_cast<Address>(kPageSize * 153);
24 : const Address kEnd = kBegin + kSize;
25 :
26 2 : RegionAllocator ra(kBegin, kSize, kPageSize);
27 :
28 : // Allocate the whole region.
29 33 : for (Address address = kBegin; address < kEnd; address += kPageSize) {
30 16 : CHECK_EQ(ra.free_size(), kEnd - address);
31 16 : CHECK(ra.AllocateRegionAt(address, kPageSize));
32 : }
33 :
34 : // No free regions left, the allocation should fail.
35 1 : CHECK_EQ(ra.free_size(), 0);
36 1 : CHECK_EQ(ra.AllocateRegion(kPageSize), RegionAllocator::kAllocationFailure);
37 :
38 : // Free one region and then the allocation should succeed.
39 1 : CHECK_EQ(ra.FreeRegion(kBegin), kPageSize);
40 1 : CHECK_EQ(ra.free_size(), kPageSize);
41 1 : CHECK(ra.AllocateRegionAt(kBegin, kPageSize));
42 :
43 : // Free all the pages.
44 33 : for (Address address = kBegin; address < kEnd; address += kPageSize) {
45 16 : CHECK_EQ(ra.FreeRegion(address), kPageSize);
46 : }
47 :
48 : // Check that the whole region is free and can be fully allocated.
49 1 : CHECK_EQ(ra.free_size(), kSize);
50 1 : CHECK_EQ(ra.AllocateRegion(kSize), kBegin);
51 1 : }
52 :
53 15373 : TEST(RegionAllocatorTest, SimpleAllocateRegion) {
54 : const size_t kPageSize = 4 * KB;
55 : const size_t kPageCount = 16;
56 : const size_t kSize = kPageSize * kPageCount;
57 : const Address kBegin = static_cast<Address>(kPageSize * 153);
58 : const Address kEnd = kBegin + kSize;
59 :
60 2 : RegionAllocator ra(kBegin, kSize, kPageSize);
61 :
62 : // Allocate the whole region.
63 33 : for (size_t i = 0; i < kPageCount; i++) {
64 16 : CHECK_EQ(ra.free_size(), kSize - kPageSize * i);
65 16 : Address address = ra.AllocateRegion(kPageSize);
66 16 : CHECK_NE(address, RegionAllocator::kAllocationFailure);
67 16 : CHECK_EQ(address, kBegin + kPageSize * i);
68 : }
69 :
70 : // No free regions left, the allocation should fail.
71 1 : CHECK_EQ(ra.free_size(), 0);
72 1 : CHECK_EQ(ra.AllocateRegion(kPageSize), RegionAllocator::kAllocationFailure);
73 :
74 : // Try to free one page and ensure that we are able to allocate it again.
75 33 : for (Address address = kBegin; address < kEnd; address += kPageSize) {
76 16 : CHECK_EQ(ra.FreeRegion(address), kPageSize);
77 16 : CHECK_EQ(ra.AllocateRegion(kPageSize), address);
78 : }
79 1 : CHECK_EQ(ra.free_size(), 0);
80 1 : }
81 :
82 18444 : TEST_P(RegionAllocatorTest, AllocateRegionRandom) {
83 : const size_t kPageSize = 8 * KB;
84 : const size_t kPageCountLog = 16;
85 : const size_t kPageCount = (size_t{1} << kPageCountLog);
86 : const size_t kSize = kPageSize * kPageCount;
87 : const Address kBegin = static_cast<Address>(153 * MB);
88 : const Address kEnd = kBegin + kSize;
89 :
90 0 : base::RandomNumberGenerator rng(GetParam());
91 0 : RegionAllocator ra(kBegin, kSize, kPageSize);
92 :
93 : std::set<Address> allocated_pages;
94 : // The page addresses must be randomized this number of allocated pages.
95 0 : const size_t kRandomizationLimit = ra.max_load_for_randomization_ / kPageSize;
96 0 : CHECK_LT(kRandomizationLimit, kPageCount);
97 :
98 : Address last_address = kBegin;
99 : bool saw_randomized_pages = false;
100 :
101 0 : for (size_t i = 0; i < kPageCount; i++) {
102 0 : Address address = ra.AllocateRegion(&rng, kPageSize);
103 0 : CHECK_NE(address, RegionAllocator::kAllocationFailure);
104 0 : CHECK(IsAligned(address, kPageSize));
105 0 : CHECK_LE(kBegin, address);
106 0 : CHECK_LT(address, kEnd);
107 0 : CHECK_EQ(allocated_pages.find(address), allocated_pages.end());
108 : allocated_pages.insert(address);
109 :
110 0 : saw_randomized_pages |= (address < last_address);
111 : last_address = address;
112 :
113 0 : if (i == kRandomizationLimit) {
114 : // We must evidence allocation randomization till this point.
115 : // The rest of the allocations may still be randomized depending on
116 : // the free ranges distribution, however it is not guaranteed.
117 0 : CHECK(saw_randomized_pages);
118 : }
119 : }
120 :
121 : // No free regions left, the allocation should fail.
122 0 : CHECK_EQ(ra.free_size(), 0);
123 0 : CHECK_EQ(ra.AllocateRegion(kPageSize), RegionAllocator::kAllocationFailure);
124 0 : }
125 :
126 15373 : TEST(RegionAllocatorTest, AllocateBigRegions) {
127 : const size_t kPageSize = 4 * KB;
128 : const size_t kPageCountLog = 10;
129 : const size_t kPageCount = (size_t{1} << kPageCountLog) - 1;
130 : const size_t kSize = kPageSize * kPageCount;
131 : const Address kBegin = static_cast<Address>(kPageSize * 153);
132 :
133 2 : RegionAllocator ra(kBegin, kSize, kPageSize);
134 :
135 : // Allocate the whole region.
136 21 : for (size_t i = 0; i < kPageCountLog; i++) {
137 10 : Address address = ra.AllocateRegion(kPageSize * (size_t{1} << i));
138 10 : CHECK_NE(address, RegionAllocator::kAllocationFailure);
139 10 : CHECK_EQ(address, kBegin + kPageSize * ((size_t{1} << i) - 1));
140 : }
141 :
142 : // No free regions left, the allocation should fail.
143 1 : CHECK_EQ(ra.free_size(), 0);
144 1 : CHECK_EQ(ra.AllocateRegion(kPageSize), RegionAllocator::kAllocationFailure);
145 :
146 : // Try to free one page and ensure that we are able to allocate it again.
147 21 : for (size_t i = 0; i < kPageCountLog; i++) {
148 10 : const size_t size = kPageSize * (size_t{1} << i);
149 10 : Address address = kBegin + kPageSize * ((size_t{1} << i) - 1);
150 10 : CHECK_EQ(ra.FreeRegion(address), size);
151 10 : CHECK_EQ(ra.AllocateRegion(size), address);
152 : }
153 1 : CHECK_EQ(ra.free_size(), 0);
154 1 : }
155 :
156 15373 : TEST(RegionAllocatorTest, MergeLeftToRightCoalecsingRegions) {
157 : const size_t kPageSize = 4 * KB;
158 : const size_t kPageCountLog = 10;
159 : const size_t kPageCount = (size_t{1} << kPageCountLog);
160 : const size_t kSize = kPageSize * kPageCount;
161 : const Address kBegin = static_cast<Address>(kPageSize * 153);
162 :
163 2 : RegionAllocator ra(kBegin, kSize, kPageSize);
164 :
165 : // Allocate the whole region using the following page size pattern:
166 : // |0|1|22|3333|...
167 1 : CHECK_EQ(ra.AllocateRegion(kPageSize), kBegin);
168 21 : for (size_t i = 0; i < kPageCountLog; i++) {
169 10 : Address address = ra.AllocateRegion(kPageSize * (size_t{1} << i));
170 10 : CHECK_NE(address, RegionAllocator::kAllocationFailure);
171 10 : CHECK_EQ(address, kBegin + kPageSize * (size_t{1} << i));
172 : }
173 :
174 : // No free regions left, the allocation should fail.
175 1 : CHECK_EQ(ra.free_size(), 0);
176 1 : CHECK_EQ(ra.AllocateRegion(kPageSize), RegionAllocator::kAllocationFailure);
177 :
178 : // Try to free two coalescing regions and ensure the new page of bigger size
179 : // can be allocated.
180 : size_t current_size = kPageSize;
181 21 : for (size_t i = 0; i < kPageCountLog; i++) {
182 10 : CHECK_EQ(ra.FreeRegion(kBegin), current_size);
183 20 : CHECK_EQ(ra.FreeRegion(kBegin + current_size), current_size);
184 10 : current_size += current_size;
185 10 : CHECK_EQ(ra.AllocateRegion(current_size), kBegin);
186 : }
187 1 : CHECK_EQ(ra.free_size(), 0);
188 1 : }
189 :
190 18444 : TEST_P(RegionAllocatorTest, MergeRightToLeftCoalecsingRegions) {
191 0 : base::RandomNumberGenerator rng(GetParam());
192 : const size_t kPageSize = 4 * KB;
193 : const size_t kPageCountLog = 10;
194 : const size_t kPageCount = (size_t{1} << kPageCountLog);
195 : const size_t kSize = kPageSize * kPageCount;
196 : const Address kBegin = static_cast<Address>(kPageSize * 153);
197 :
198 0 : RegionAllocator ra(kBegin, kSize, kPageSize);
199 :
200 : // Allocate the whole region.
201 0 : for (size_t i = 0; i < kPageCount; i++) {
202 0 : Address address = ra.AllocateRegion(kPageSize);
203 0 : CHECK_NE(address, RegionAllocator::kAllocationFailure);
204 0 : CHECK_EQ(address, kBegin + kPageSize * i);
205 : }
206 :
207 : // No free regions left, the allocation should fail.
208 0 : CHECK_EQ(ra.free_size(), 0);
209 0 : CHECK_EQ(ra.AllocateRegion(kPageSize), RegionAllocator::kAllocationFailure);
210 :
211 : // Free pages with even indices left-to-right.
212 0 : for (size_t i = 0; i < kPageCount; i += 2) {
213 0 : Address address = kBegin + kPageSize * i;
214 0 : CHECK_EQ(ra.FreeRegion(address), kPageSize);
215 : }
216 :
217 : // Free pages with odd indices right-to-left.
218 0 : for (size_t i = 1; i < kPageCount; i += 2) {
219 0 : Address address = kBegin + kPageSize * (kPageCount - i);
220 0 : CHECK_EQ(ra.FreeRegion(address), kPageSize);
221 : // Now we should be able to allocate a double-sized page.
222 0 : CHECK_EQ(ra.AllocateRegion(kPageSize * 2), address - kPageSize);
223 : // .. but there's a window for only one such page.
224 0 : CHECK_EQ(ra.AllocateRegion(kPageSize * 2),
225 : RegionAllocator::kAllocationFailure);
226 : }
227 :
228 : // Free all the double-sized pages.
229 0 : for (size_t i = 0; i < kPageCount; i += 2) {
230 0 : Address address = kBegin + kPageSize * i;
231 0 : CHECK_EQ(ra.FreeRegion(address), kPageSize * 2);
232 : }
233 :
234 : // Check that the whole region is free and can be fully allocated.
235 0 : CHECK_EQ(ra.free_size(), kSize);
236 0 : CHECK_EQ(ra.AllocateRegion(kSize), kBegin);
237 0 : }
238 :
239 15373 : TEST(RegionAllocatorTest, Fragmentation) {
240 : const size_t kPageSize = 64 * KB;
241 : const size_t kPageCount = 9;
242 : const size_t kSize = kPageSize * kPageCount;
243 : const Address kBegin = static_cast<Address>(kPageSize * 153);
244 :
245 2 : RegionAllocator ra(kBegin, kSize, kPageSize);
246 :
247 : // Allocate the whole region.
248 19 : for (size_t i = 0; i < kPageCount; i++) {
249 9 : Address address = ra.AllocateRegion(kPageSize);
250 9 : CHECK_NE(address, RegionAllocator::kAllocationFailure);
251 9 : CHECK_EQ(address, kBegin + kPageSize * i);
252 : }
253 :
254 : // No free regions left, the allocation should fail.
255 1 : CHECK_EQ(ra.free_size(), 0);
256 1 : CHECK_EQ(ra.AllocateRegion(kPageSize), RegionAllocator::kAllocationFailure);
257 :
258 : // Free pages in the following order and check the freed size.
259 : struct {
260 : size_t page_index_to_free;
261 : size_t expected_page_count;
262 : } testcase[] = { // .........
263 : {0, 9}, // x........
264 : {2, 9}, // x.x......
265 : {4, 9}, // x.x.x....
266 : {6, 9}, // x.x.x.x..
267 : {8, 9}, // x.x.x.x.x
268 : {1, 7}, // xxx.x.x.x
269 : {7, 5}, // xxx.x.xxx
270 : {3, 3}, // xxxxx.xxx
271 1 : {5, 1}}; // xxxxxxxxx
272 : CHECK_EQ(kPageCount, arraysize(testcase));
273 :
274 1 : CHECK_EQ(ra.all_regions_.size(), kPageCount);
275 19 : for (size_t i = 0; i < kPageCount; i++) {
276 9 : Address address = kBegin + kPageSize * testcase[i].page_index_to_free;
277 9 : CHECK_EQ(ra.FreeRegion(address), kPageSize);
278 9 : CHECK_EQ(ra.all_regions_.size(), testcase[i].expected_page_count);
279 : }
280 :
281 : // Check that the whole region is free and can be fully allocated.
282 1 : CHECK_EQ(ra.free_size(), kSize);
283 1 : CHECK_EQ(ra.AllocateRegion(kSize), kBegin);
284 1 : }
285 :
286 15373 : TEST(RegionAllocatorTest, FindRegion) {
287 : const size_t kPageSize = 4 * KB;
288 : const size_t kPageCount = 16;
289 : const size_t kSize = kPageSize * kPageCount;
290 : const Address kBegin = static_cast<Address>(kPageSize * 153);
291 : const Address kEnd = kBegin + kSize;
292 :
293 2 : RegionAllocator ra(kBegin, kSize, kPageSize);
294 :
295 : // Allocate the whole region.
296 33 : for (Address address = kBegin; address < kEnd; address += kPageSize) {
297 16 : CHECK_EQ(ra.free_size(), kEnd - address);
298 16 : CHECK(ra.AllocateRegionAt(address, kPageSize));
299 : }
300 :
301 : // No free regions left, the allocation should fail.
302 1 : CHECK_EQ(ra.free_size(), 0);
303 1 : CHECK_EQ(ra.AllocateRegion(kPageSize), RegionAllocator::kAllocationFailure);
304 :
305 : // The out-of region requests must return end iterator.
306 2 : CHECK_EQ(ra.FindRegion(kBegin - 1), ra.all_regions_.end());
307 2 : CHECK_EQ(ra.FindRegion(kBegin - kPageSize), ra.all_regions_.end());
308 2 : CHECK_EQ(ra.FindRegion(kBegin / 2), ra.all_regions_.end());
309 2 : CHECK_EQ(ra.FindRegion(kEnd), ra.all_regions_.end());
310 2 : CHECK_EQ(ra.FindRegion(kEnd + kPageSize), ra.all_regions_.end());
311 2 : CHECK_EQ(ra.FindRegion(kEnd * 2), ra.all_regions_.end());
312 :
313 129 : for (Address address = kBegin; address < kEnd; address += kPageSize / 4) {
314 : RegionAllocator::AllRegionsSet::iterator region_iter =
315 64 : ra.FindRegion(address);
316 64 : CHECK_NE(region_iter, ra.all_regions_.end());
317 64 : RegionAllocator::Region* region = *region_iter;
318 : Address region_start = RoundDown(address, kPageSize);
319 64 : CHECK_EQ(region->begin(), region_start);
320 64 : CHECK_LE(region->begin(), address);
321 64 : CHECK_LT(address, region->end());
322 : }
323 1 : }
324 :
325 15373 : TEST(RegionAllocatorTest, TrimRegion) {
326 : const size_t kPageSize = 4 * KB;
327 : const size_t kPageCount = 64;
328 : const size_t kSize = kPageSize * kPageCount;
329 : const Address kBegin = static_cast<Address>(kPageSize * 153);
330 :
331 2 : RegionAllocator ra(kBegin, kSize, kPageSize);
332 :
333 : Address address = kBegin + 13 * kPageSize;
334 1 : size_t size = 37 * kPageSize;
335 : size_t free_size = kSize - size;
336 1 : CHECK(ra.AllocateRegionAt(address, size));
337 :
338 1 : size_t trim_size = kPageSize;
339 : do {
340 6 : CHECK_EQ(ra.CheckRegion(address), size);
341 6 : CHECK_EQ(ra.free_size(), free_size);
342 :
343 6 : trim_size = std::min(size, trim_size);
344 6 : size -= trim_size;
345 6 : free_size += trim_size;
346 6 : CHECK_EQ(ra.TrimRegion(address, size), trim_size);
347 6 : trim_size *= 2;
348 6 : } while (size != 0);
349 :
350 : // Check that the whole region is free and can be fully allocated.
351 1 : CHECK_EQ(ra.free_size(), kSize);
352 1 : CHECK_EQ(ra.AllocateRegion(kSize), kBegin);
353 1 : }
354 :
355 : } // namespace base
356 9222 : } // namespace v8
|
