1 : // Copyright 2014 Google Inc. All Rights Reserved.
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 "syzygy/agent/asan/page_allocator.h"
16 :
17 : #include "gtest/gtest.h"
18 :
19 : namespace agent {
20 : namespace asan {
21 :
22 : namespace {
23 :
24 : template<size_t kObjectSize,
25 : size_t kMaxObjectCount,
26 : size_t kPageSize>
27 : class TestPageAllocator
28 : : public PageAllocator<kObjectSize, kMaxObjectCount, kPageSize, true> {
29 : public:
30 : typedef PageAllocator<kObjectSize, kMaxObjectCount, kPageSize, true>
31 : Super;
32 :
33 E : void AllocatePage() {
34 E : base::AutoLock lock(lock_);
35 E : AllocatePageLocked();
36 E : }
37 :
38 : // Counts the number of free objects by iterating over the lists.
39 : // If |count| is 0 then counts all free objects, otherwise only counts
40 : // those in the given size class.
41 E : size_t FreeObjects(size_t count) {
42 E : size_t n_min = 1;
43 E : size_t n_max = kMaxObjectCount;
44 E : if (count != 0) {
45 E : n_min = count;
46 E : n_max = count;
47 : }
48 :
49 E : size_t free_objects = 0;
50 E : for (size_t n = n_min; n <= n_max; ++n) {
51 E : Object* free = free_[n - 1];
52 E : while (free) {
53 E : free_objects += n;
54 E : free = free->next_free;
55 E : }
56 E : }
57 :
58 E : return free_objects;
59 E : }
60 :
61 E : const PageAllocatorStatistics& stats() {
62 E : return stats_.stats;
63 E : }
64 :
65 : using Super::AllocatePageLocked;
66 : using Super::page_;
67 : using Super::object_;
68 : using Super::free_;
69 : };
70 :
71 : template<typename ObjectType,
72 : size_t kMaxObjectCount,
73 : size_t kPageSize>
74 : class TestTypedPageAllocator
75 : : public TypedPageAllocator<ObjectType, kMaxObjectCount, kPageSize, true> {
76 : public:
77 : typedef TypedPageAllocator<ObjectType, kMaxObjectCount, kPageSize, true>
78 : Super;
79 :
80 : const PageAllocatorStatistics& stats() {
81 : return stats_.stats;
82 : }
83 : };
84 :
85 : // There are 256 16-byte objects in a 4KB page, so we should get 255 objects.
86 : typedef TestPageAllocator<16, 1, 4096> TestPageAllocator255;
87 : typedef TestPageAllocator<16, 10, 4096> TestPageAllocatorMulti255;
88 :
89 : } // namespace
90 :
91 E : TEST(PageAllocatorTest, Constructor) {
92 E : TestPageAllocator255 pa;
93 E : EXPECT_EQ(255, TestPageAllocator255::Page::kObjectsPerPage);
94 E : EXPECT_TRUE(pa.page_ == nullptr);
95 E : EXPECT_TRUE(pa.object_ == nullptr);
96 E : EXPECT_TRUE(pa.free_[0] == nullptr);
97 :
98 E : TestPageAllocatorMulti255 mpa;
99 E : EXPECT_EQ(255, TestPageAllocatorMulti255::Page::kObjectsPerPage);
100 E : EXPECT_TRUE(mpa.page_ == nullptr);
101 E : EXPECT_TRUE(mpa.object_ == nullptr);
102 E : for (size_t i = 0; i < arraysize(mpa.free_); ++i)
103 E : EXPECT_TRUE(mpa.free_[i] == nullptr);
104 E : }
105 :
106 E : TEST(PageAllocatorTest, AllocatePage) {
107 E : TestPageAllocator255 pa;
108 E : EXPECT_TRUE(pa.page_ == nullptr);
109 E : EXPECT_TRUE(pa.object_ == nullptr);
110 E : EXPECT_EQ(0u, pa.stats().page_count);
111 :
112 E : pa.AllocatePage();
113 E : EXPECT_FALSE(pa.page_ == nullptr);
114 E : EXPECT_FALSE(pa.object_ == nullptr);
115 E : EXPECT_EQ(pa.page_->objects, pa.object_);
116 E : EXPECT_EQ(1u, pa.stats().page_count);
117 E : }
118 :
119 E : TEST(PageAllocatorTest, Allocated) {
120 E : TestPageAllocator255 pa;
121 E : EXPECT_TRUE(pa.page_ == nullptr);
122 E : EXPECT_TRUE(pa.object_ == nullptr);
123 E : EXPECT_EQ(0u, pa.stats().page_count);
124 :
125 E : std::vector<void*> allocs;
126 E : allocs.reserve(300);
127 E : for (size_t i = 0; i < 300; ++i) {
128 E : void* alloc = pa.Allocate(1);
129 E : EXPECT_TRUE(pa.Allocated(alloc, 1));
130 E : EXPECT_FALSE(pa.Freed(alloc, 1));
131 E : allocs.push_back(alloc);
132 E : }
133 E : EXPECT_EQ(2u, pa.stats().page_count);
134 :
135 E : for (size_t i = 0; i < 300; ++i) {
136 E : size_t index = ::rand() % allocs.size();
137 E : void* alloc = allocs[index];
138 E : allocs[index] = allocs.back();
139 E : allocs.pop_back();
140 E : EXPECT_TRUE(pa.Allocated(alloc, 1));
141 E : EXPECT_FALSE(pa.Freed(alloc, 1));
142 E : }
143 E : }
144 :
145 E : TEST(PageAllocatorTest, SuccessiveSingleAllocations) {
146 E : TestPageAllocator255 pa;
147 E : EXPECT_TRUE(pa.page_ == nullptr);
148 E : EXPECT_TRUE(pa.object_ == nullptr);
149 E : EXPECT_EQ(0u, pa.stats().page_count);
150 :
151 E : pa.AllocatePage();
152 E : for (size_t i = 0; i < 255; ++i) {
153 E : EXPECT_EQ(pa.page_->objects + i, pa.object_);
154 E : void* current_object = pa.object_;
155 E : EXPECT_EQ(current_object, pa.Allocate(1));
156 E : EXPECT_EQ(i + 1, pa.stats().allocated_groups);
157 E : EXPECT_EQ(i + 1, pa.stats().allocated_objects);
158 E : EXPECT_EQ(0u, pa.stats().freed_groups);
159 E : EXPECT_EQ(0u, pa.stats().freed_objects);
160 E : }
161 E : EXPECT_EQ(pa.object_, pa.page_->end());
162 E : EXPECT_EQ(1u, pa.stats().page_count);
163 :
164 E : TestPageAllocator255::Page* current_page = pa.page_;
165 E : pa.Allocate(1);
166 E : EXPECT_NE(current_page, pa.page_);
167 E : EXPECT_EQ(pa.page_->objects + 1, pa.object_);
168 E : EXPECT_EQ(2u, pa.stats().page_count);
169 E : EXPECT_EQ(current_page, pa.page_->prev_page);
170 E : }
171 :
172 E : TEST(PageAllocatorTest, SingleStatsTest) {
173 E : TestPageAllocator255 pa;
174 :
175 E : EXPECT_EQ(0u, pa.stats().page_count);
176 E : EXPECT_EQ(0u, pa.stats().allocated_groups);
177 E : EXPECT_EQ(0u, pa.stats().allocated_objects);
178 E : EXPECT_EQ(0u, pa.stats().freed_groups);
179 E : EXPECT_EQ(0u, pa.stats().freed_objects);
180 :
181 E : void* a1 = pa.Allocate(1);
182 E : EXPECT_EQ(1u, pa.stats().page_count);
183 E : EXPECT_EQ(1u, pa.stats().allocated_groups);
184 E : EXPECT_EQ(1u, pa.stats().allocated_objects);
185 E : EXPECT_EQ(0u, pa.stats().freed_groups);
186 E : EXPECT_EQ(0u, pa.stats().freed_objects);
187 :
188 E : void* a2 = pa.Allocate(1);
189 E : EXPECT_EQ(1u, pa.stats().page_count);
190 E : EXPECT_EQ(2u, pa.stats().allocated_groups);
191 E : EXPECT_EQ(2u, pa.stats().allocated_objects);
192 E : EXPECT_EQ(0u, pa.stats().freed_groups);
193 E : EXPECT_EQ(0u, pa.stats().freed_objects);
194 :
195 E : pa.Free(a1, 1);
196 E : EXPECT_EQ(1u, pa.stats().page_count);
197 E : EXPECT_EQ(1u, pa.stats().allocated_groups);
198 E : EXPECT_EQ(1u, pa.stats().allocated_objects);
199 E : EXPECT_EQ(1u, pa.stats().freed_groups);
200 E : EXPECT_EQ(1u, pa.stats().freed_objects);
201 :
202 E : pa.Free(a2, 1);
203 E : EXPECT_EQ(1u, pa.stats().page_count);
204 E : EXPECT_EQ(0u, pa.stats().allocated_groups);
205 E : EXPECT_EQ(0u, pa.stats().allocated_objects);
206 E : EXPECT_EQ(2u, pa.stats().freed_groups);
207 E : EXPECT_EQ(2u, pa.stats().freed_objects);
208 E : }
209 :
210 E : TEST(PageAllocatorTest, SingleAllocsAndFrees) {
211 E : std::set<void*> allocated, freed;
212 :
213 : // Runs of allocations/frees to perform.
214 : static const size_t kSizes[] = {
215 : 12, 10, // 12 high water, 2 allocated, 10 freed.
216 : 33, 15, // 35 high water, 20 allocated, 15 freed.
217 : 100, 80, // 120 high water, 40 allocated, 80 freed.
218 : 1, 10, // 120 high water, 31 allocated, 89 freed.
219 : 5, 7, // 120 high water, 29 allocated, 91 freed.
220 : 100, 80, // 129 high water, 49 allocated, 80 freed.
221 : 10, 59, // 129 high water, 0 allocated, 129 freed.
222 : };
223 :
224 E : TestPageAllocator255 pa;
225 E : for (size_t i = 0; i < arraysize(kSizes); ++i) {
226 E : if ((i % 2) == 0) {
227 : // Allocating.
228 E : for (size_t j = 0; j < kSizes[i]; ++j) {
229 E : void* alloc = pa.Allocate(1);
230 E : EXPECT_TRUE(pa.Allocated(alloc, 1));
231 E : EXPECT_FALSE(pa.Freed(alloc, 1));
232 E : EXPECT_EQ(0u, allocated.count(alloc));
233 E : allocated.insert(alloc);
234 :
235 E : if (!freed.empty()) {
236 E : EXPECT_EQ(1u, freed.count(alloc));
237 E : freed.erase(alloc);
238 : }
239 E : }
240 : } else {
241 E : EXPECT_LE(kSizes[i], allocated.size());
242 : // Freeing.
243 E : for (size_t j = 0; j < kSizes[i]; ++j) {
244 E : void* alloc = *allocated.begin();
245 E : EXPECT_TRUE(pa.Allocated(alloc, 1));
246 E : EXPECT_FALSE(pa.Freed(alloc, 1));
247 E : allocated.erase(alloc);
248 E : pa.Free(alloc, 1);
249 E : EXPECT_FALSE(pa.Allocated(alloc, 1));
250 E : EXPECT_TRUE(pa.Freed(alloc, 1));
251 E : EXPECT_EQ(0u, freed.count(alloc));
252 E : freed.insert(alloc);
253 E : }
254 : }
255 :
256 E : std::set<void*>::const_iterator it;
257 E : for (it = allocated.begin(); it != allocated.end(); ++it) {
258 E : EXPECT_TRUE(pa.Allocated(*it, 1));
259 E : EXPECT_FALSE(pa.Freed(*it, 1));
260 E : }
261 E : for (it = freed.begin(); it != freed.end(); ++it) {
262 E : EXPECT_FALSE(pa.Allocated(*it, 1));
263 E : EXPECT_TRUE(pa.Freed(*it, 1));
264 E : }
265 E : }
266 :
267 E : EXPECT_EQ(129u, pa.FreeObjects(1));
268 E : }
269 :
270 E : TEST(PageAllocatorTest, MultiAllocsAndFrees) {
271 E : TestPageAllocatorMulti255 pa;
272 E : EXPECT_EQ(0u, pa.stats().page_count);
273 :
274 E : void* a = pa.Allocate(10);
275 E : void* a_orig = a;
276 E : EXPECT_EQ(1u, pa.stats().page_count);
277 E : EXPECT_EQ(0u, pa.FreeObjects(0));
278 :
279 E : pa.Free(a, 10);
280 E : EXPECT_EQ(1u, pa.stats().page_count);
281 E : EXPECT_EQ(10u, pa.FreeObjects(0)); // All size classes.
282 E : EXPECT_EQ(10u, pa.FreeObjects(10)); // Length 10 allocations only.
283 :
284 : // Allocating again should reuse the freed allocation.
285 E : size_t r = 0;
286 E : a = pa.Allocate(8, &r);
287 E : EXPECT_EQ(a_orig, a);
288 E : EXPECT_EQ(10u, r);
289 E : EXPECT_EQ(1u, pa.stats().page_count);
290 E : EXPECT_EQ(0u, pa.FreeObjects(0));
291 :
292 E : pa.Free(a, r);
293 E : EXPECT_EQ(1u, pa.stats().page_count);
294 E : EXPECT_EQ(10u, pa.FreeObjects(0)); // All size classes.
295 E : EXPECT_EQ(10u, pa.FreeObjects(10)); // Length 10 allocations only.
296 :
297 : // Allocated should use the freed allocation, and add the remainder to a
298 : // shorter free list.
299 E : a = pa.Allocate(8);
300 E : EXPECT_EQ(a_orig, a);
301 E : EXPECT_EQ(1u, pa.stats().page_count);
302 E : EXPECT_EQ(2u, pa.FreeObjects(0)); // All size classes.
303 E : EXPECT_EQ(2u, pa.FreeObjects(2)); // Length 2 allocations only.
304 :
305 : // The remainder should now be used.
306 E : a = pa.Allocate(2);
307 E : void* a_expected = reinterpret_cast<uint8*>(a_orig) + 16 * 8;
308 E : EXPECT_EQ(a_expected, a);
309 E : EXPECT_EQ(1u, pa.stats().page_count);
310 E : EXPECT_EQ(0u, pa.FreeObjects(0));
311 E : }
312 :
313 E : TEST(PageAllocatorTest, MultiStatsTest) {
314 E : TestPageAllocatorMulti255 pa;
315 :
316 E : EXPECT_EQ(0u, pa.stats().page_count);
317 E : EXPECT_EQ(0u, pa.stats().allocated_groups);
318 E : EXPECT_EQ(0u, pa.stats().allocated_objects);
319 E : EXPECT_EQ(0u, pa.stats().freed_groups);
320 E : EXPECT_EQ(0u, pa.stats().freed_objects);
321 :
322 E : void* a1 = pa.Allocate(10);
323 E : EXPECT_EQ(1u, pa.stats().page_count);
324 E : EXPECT_EQ(1u, pa.stats().allocated_groups);
325 E : EXPECT_EQ(10u, pa.stats().allocated_objects);
326 E : EXPECT_EQ(0u, pa.stats().freed_groups);
327 E : EXPECT_EQ(0u, pa.stats().freed_objects);
328 :
329 E : void* a2 = pa.Allocate(5);
330 E : EXPECT_EQ(1u, pa.stats().page_count);
331 E : EXPECT_EQ(2u, pa.stats().allocated_groups);
332 E : EXPECT_EQ(15u, pa.stats().allocated_objects);
333 E : EXPECT_EQ(0u, pa.stats().freed_groups);
334 E : EXPECT_EQ(0u, pa.stats().freed_objects);
335 :
336 E : pa.Free(a1, 10);
337 E : EXPECT_EQ(1u, pa.stats().page_count);
338 E : EXPECT_EQ(1u, pa.stats().allocated_groups);
339 E : EXPECT_EQ(5u, pa.stats().allocated_objects);
340 E : EXPECT_EQ(1u, pa.stats().freed_groups);
341 E : EXPECT_EQ(10u, pa.stats().freed_objects);
342 :
343 E : pa.Free(a2, 5);
344 E : EXPECT_EQ(1u, pa.stats().page_count);
345 E : EXPECT_EQ(0u, pa.stats().allocated_groups);
346 E : EXPECT_EQ(0u, pa.stats().allocated_objects);
347 E : EXPECT_EQ(2u, pa.stats().freed_groups);
348 E : EXPECT_EQ(15u, pa.stats().freed_objects);
349 :
350 : // This will take from the allocation of size 10,
351 : // and create a free group of size 3.
352 E : a1 = pa.Allocate(7);
353 E : EXPECT_EQ(1u, pa.stats().page_count);
354 E : EXPECT_EQ(1u, pa.stats().allocated_groups);
355 E : EXPECT_EQ(7u, pa.stats().allocated_objects);
356 E : EXPECT_EQ(2u, pa.stats().freed_groups);
357 E : EXPECT_EQ(8u, pa.stats().freed_objects);
358 :
359 : // This will take from the free group of size 5,
360 : // returning one more element than requested.
361 E : size_t received = 0;
362 E : a2 = pa.Allocate(4, &received);
363 E : EXPECT_EQ(5u, received);
364 E : EXPECT_EQ(1u, pa.stats().page_count);
365 E : EXPECT_EQ(2u, pa.stats().allocated_groups);
366 E : EXPECT_EQ(12u, pa.stats().allocated_objects);
367 E : EXPECT_EQ(1u, pa.stats().freed_groups);
368 E : EXPECT_EQ(3u, pa.stats().freed_objects);
369 E : }
370 :
371 E : TEST(PageAllocatorTest, MultiSlabsPagesSmallerThanAllocGranularity) {
372 : typedef PageAllocator<16, 1, 32 * 1024, false> PA;
373 E : PA pa;
374 :
375 E : EXPECT_EQ(2u, PA::Page::kPagesPerSlab);
376 E : EXPECT_EQ(64 * 1024, PA::Page::kSlabSize);
377 E : EXPECT_EQ(32 * 1024, PA::Page::kPageSize);
378 E : EXPECT_EQ(32 * 1024, sizeof(PA::Page));
379 E : EXPECT_EQ(2 * 1024 - 1, PA::Page::kObjectsPerPage);
380 :
381 : // We can fit 2047 objects per page, and 2 pages per 64KB slab. So we need
382 : // to allocate nearly 10000 objects before we'll be certain that 2 slabs have
383 : // been allocated, each containing 2 pages.
384 E : for (size_t i = 0; i < 10000; ++i)
385 E : pa.Allocate(1);
386 E : }
387 :
388 E : TEST(PageAllocatorTest, MultiSlabsPagesBiggerThanAllGranularity) {
389 : typedef PageAllocator<16, 1, 70 * 1024, false> PA;
390 E : PA pa;
391 :
392 E : EXPECT_EQ(1u, PA::Page::kPagesPerSlab);
393 E : EXPECT_EQ(128 * 1024, PA::Page::kSlabSize);
394 E : EXPECT_EQ(128 * 1024, PA::Page::kPageSize);
395 E : EXPECT_EQ(128 * 1024, sizeof(PA::Page));
396 E : EXPECT_EQ(8 * 1024 - 1, PA::Page::kObjectsPerPage);
397 :
398 : // We can over 16K objects per page/slab so we need to allocate at least 35K
399 : // objects before we're certain that 2 slabs will have been allocated.
400 E : for (size_t i = 0; i < 35000; ++i)
401 E : pa.Allocate(1);
402 E : }
403 :
404 E : TEST(TypedPageAllocatorTest, SingleEndToEnd) {
405 E : TypedPageAllocator<uint32, 1, 1000, true> pa;
406 E : for (size_t i = 0; i < 1600; ++i) {
407 E : uint32* alloc = pa.Allocate(1);
408 E : if ((i % 3) == 0)
409 E : pa.Free(alloc, 1);
410 E : }
411 E : }
412 :
413 E : TEST(TypedPageAllocatorTest, MultiEndToEnd) {
414 E : TypedPageAllocator<uint32, 10, 1000, true> pa;
415 E : for (size_t i = 0; i < 100; ++i) {
416 E : size_t requested = (i % 10) + 1;
417 E : size_t received = 0;
418 E : uint32* alloc = pa.Allocate(requested, &received);
419 E : if ((i % 3) == 0)
420 E : pa.Free(alloc, received);
421 E : }
422 :
423 E : for (size_t i = 0; i < 100; ++i) {
424 E : size_t requested = (i % 10) + 1;
425 E : uint32* alloc = pa.Allocate(requested);
426 E : if ((i % 3) == 0)
427 E : pa.Free(alloc, requested);
428 E : }
429 E : }
430 :
431 : } // namespace asan
432 : } // namespace agent
|