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 : uint8* free = free_[n - 1];
52 E : while (free) {
53 E : free_objects += n;
54 E : free = *reinterpret_cast<uint8**>(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::Allocated;
67 : using Super::Freed;
68 : using Super::page_size_;
69 : using Super::objects_per_page_;
70 : using Super::current_page_;
71 : using Super::current_object_;
72 : using Super::end_object_;
73 : using Super::free_;
74 : };
75 :
76 : template<typename ObjectType,
77 : size_t kMaxObjectCount,
78 : size_t kPageSize>
79 : class TestTypedPageAllocator
80 : : public TypedPageAllocator<ObjectType, kMaxObjectCount, kPageSize, true> {
81 : public:
82 : typedef TypedPageAllocator<ObjectType, kMaxObjectCount, kPageSize, true>
83 : Super;
84 :
85 : const PageAllocatorStatistics& stats() {
86 : return stats_.stats;
87 : }
88 : };
89 :
90 : // There are 256 16-byte objects in a 4KB page, so we should get 255 objects.
91 : typedef TestPageAllocator<16, 1, 4096> TestPageAllocator255;
92 : typedef TestPageAllocator<16, 10, 4096> TestPageAllocatorMulti255;
93 :
94 : } // namespace
95 :
96 :
97 E : TEST(PageAllocatorTest, Constructor) {
98 E : TestPageAllocator255 pa;
99 E : EXPECT_EQ(4096, pa.page_size_);
100 E : EXPECT_EQ(255, pa.objects_per_page_);
101 E : EXPECT_TRUE(pa.current_page_ == NULL);
102 E : EXPECT_TRUE(pa.current_object_ == NULL);
103 E : EXPECT_TRUE(pa.free_[0] == NULL);
104 :
105 E : TestPageAllocatorMulti255 mpa;
106 E : EXPECT_EQ(4096, mpa.page_size_);
107 E : EXPECT_EQ(255, mpa.objects_per_page_);
108 E : EXPECT_TRUE(mpa.current_page_ == NULL);
109 E : EXPECT_TRUE(mpa.current_object_ == NULL);
110 E : for (size_t i = 0; i < 10; ++i)
111 E : EXPECT_TRUE(mpa.free_[i] == NULL);
112 E : }
113 :
114 E : TEST(PageAllocatorTest, AllocatePage) {
115 E : TestPageAllocator255 pa;
116 E : EXPECT_TRUE(pa.current_page_ == NULL);
117 E : EXPECT_TRUE(pa.current_object_ == NULL);
118 E : EXPECT_EQ(0u, pa.stats().page_count);
119 :
120 E : pa.AllocatePage();
121 E : EXPECT_TRUE(pa.current_page_ != NULL);
122 E : EXPECT_TRUE(pa.current_object_ != NULL);
123 : EXPECT_EQ(reinterpret_cast<uint8*>(pa.current_page_),
124 E : reinterpret_cast<uint8*>(pa.current_object_));
125 E : EXPECT_EQ(1u, pa.stats().page_count);
126 E : }
127 :
128 E : TEST(PageAllocatorTest, SuccessiveSingleAllocations) {
129 E : TestPageAllocator255 pa;
130 E : EXPECT_TRUE(pa.current_page_ == NULL);
131 E : EXPECT_TRUE(pa.current_object_ == NULL);
132 E : EXPECT_EQ(0u, pa.stats().page_count);
133 :
134 E : pa.AllocatePage();
135 E : for (size_t i = 0; i < 255; ++i) {
136 : EXPECT_EQ(reinterpret_cast<uint8*>(pa.current_page_) + i * 16,
137 E : reinterpret_cast<uint8*>(pa.current_object_));
138 E : void* current_object = pa.current_object_;
139 E : EXPECT_EQ(current_object, pa.Allocate(1));
140 E : EXPECT_EQ(i + 1, pa.stats().allocated_groups);
141 E : EXPECT_EQ(i + 1, pa.stats().allocated_objects);
142 E : EXPECT_EQ(0u, pa.stats().freed_groups);
143 E : EXPECT_EQ(0u, pa.stats().freed_objects);
144 E : }
145 E : EXPECT_GE(pa.current_object_, pa.end_object_);
146 E : EXPECT_EQ(1u, pa.stats().page_count);
147 :
148 E : void* current_page = pa.current_page_;
149 E : pa.Allocate(1);
150 E : EXPECT_NE(current_page, pa.current_page_);
151 : EXPECT_EQ(reinterpret_cast<uint8*>(pa.current_page_) + 16,
152 E : reinterpret_cast<uint8*>(pa.current_object_));
153 E : EXPECT_EQ(2u, pa.stats().page_count);
154 :
155 : void* prev = reinterpret_cast<uint8*>(pa.current_page_) + pa.page_size_ -
156 E : sizeof(void*);
157 E : EXPECT_EQ(current_page, *reinterpret_cast<void**>(prev));
158 E : }
159 :
160 E : TEST(PageAllocatorTest, SingleStatsTest) {
161 E : TestPageAllocator255 pa;
162 :
163 E : EXPECT_EQ(0u, pa.stats().page_count);
164 E : EXPECT_EQ(0u, pa.stats().allocated_groups);
165 E : EXPECT_EQ(0u, pa.stats().allocated_objects);
166 E : EXPECT_EQ(0u, pa.stats().freed_groups);
167 E : EXPECT_EQ(0u, pa.stats().freed_objects);
168 :
169 E : void* a1 = pa.Allocate(1);
170 E : EXPECT_EQ(1u, pa.stats().page_count);
171 E : EXPECT_EQ(1u, pa.stats().allocated_groups);
172 E : EXPECT_EQ(1u, pa.stats().allocated_objects);
173 E : EXPECT_EQ(0u, pa.stats().freed_groups);
174 E : EXPECT_EQ(0u, pa.stats().freed_objects);
175 :
176 E : void* a2 = pa.Allocate(1);
177 E : EXPECT_EQ(1u, pa.stats().page_count);
178 E : EXPECT_EQ(2u, pa.stats().allocated_groups);
179 E : EXPECT_EQ(2u, pa.stats().allocated_objects);
180 E : EXPECT_EQ(0u, pa.stats().freed_groups);
181 E : EXPECT_EQ(0u, pa.stats().freed_objects);
182 :
183 E : pa.Free(a1, 1);
184 E : EXPECT_EQ(1u, pa.stats().page_count);
185 E : EXPECT_EQ(1u, pa.stats().allocated_groups);
186 E : EXPECT_EQ(1u, pa.stats().allocated_objects);
187 E : EXPECT_EQ(1u, pa.stats().freed_groups);
188 E : EXPECT_EQ(1u, pa.stats().freed_objects);
189 :
190 E : pa.Free(a2, 1);
191 E : EXPECT_EQ(1u, pa.stats().page_count);
192 E : EXPECT_EQ(0u, pa.stats().allocated_groups);
193 E : EXPECT_EQ(0u, pa.stats().allocated_objects);
194 E : EXPECT_EQ(2u, pa.stats().freed_groups);
195 E : EXPECT_EQ(2u, pa.stats().freed_objects);
196 E : }
197 :
198 E : TEST(PageAllocatorTest, SingleAllocsAndFrees) {
199 E : std::set<void*> allocated, freed;
200 :
201 : // Runs of allocations/frees to perform.
202 : static const size_t kSizes[] = {
203 : 12, 10, // 12 high water, 2 allocated, 10 freed.
204 : 33, 15, // 35 high water, 20 allocated, 15 freed.
205 : 100, 80, // 120 high water, 40 allocated, 80 freed.
206 : 1, 10, // 120 high water, 31 allocated, 89 freed.
207 : 5, 7, // 120 high water, 29 allocated, 91 freed.
208 : 100, 80, // 129 high water, 49 allocated, 80 freed.
209 : 10, 59, // 129 high water, 0 allocated, 129 freed.
210 : };
211 :
212 E : TestPageAllocator255 pa;
213 E : for (size_t i = 0; i < arraysize(kSizes); ++i) {
214 E : if ((i % 2) == 0) {
215 : // Allocating.
216 E : for (size_t j = 0; j < kSizes[i]; ++j) {
217 E : void* alloc = pa.Allocate(1);
218 E : EXPECT_EQ(0u, allocated.count(alloc));
219 E : allocated.insert(alloc);
220 :
221 E : if (!freed.empty()) {
222 E : EXPECT_EQ(1u, freed.count(alloc));
223 E : freed.erase(alloc);
224 : }
225 E : }
226 : } else {
227 E : EXPECT_LE(kSizes[i], allocated.size());
228 : // Freeing.
229 E : for (size_t j = 0; j < kSizes[i]; ++j) {
230 E : void* alloc = *allocated.begin();
231 E : allocated.erase(alloc);
232 E : pa.Free(alloc, 1);
233 E : EXPECT_EQ(0u, freed.count(alloc));
234 E : freed.insert(alloc);
235 E : }
236 : }
237 :
238 E : std::set<void*>::const_iterator it;
239 E : for (it = allocated.begin(); it != allocated.end(); ++it)
240 E : EXPECT_TRUE(pa.Allocated(*it, 1));
241 E : for (it = freed.begin(); it != freed.end(); ++it)
242 E : EXPECT_TRUE(pa.Freed(*it, 1));
243 E : }
244 :
245 E : EXPECT_EQ(129u, pa.FreeObjects(1));
246 E : }
247 :
248 E : TEST(PageAllocatorTest, MultiAllocsAndFrees) {
249 E : TestPageAllocatorMulti255 pa;
250 E : EXPECT_EQ(0u, pa.stats().page_count);
251 :
252 E : void* a = pa.Allocate(10);
253 E : void* a_orig = a;
254 E : EXPECT_EQ(1u, pa.stats().page_count);
255 E : EXPECT_EQ(0u, pa.FreeObjects(0));
256 :
257 E : pa.Free(a, 10);
258 E : EXPECT_EQ(1u, pa.stats().page_count);
259 E : EXPECT_EQ(10u, pa.FreeObjects(0)); // All size classes.
260 E : EXPECT_EQ(10u, pa.FreeObjects(10)); // Length 10 allocations only.
261 :
262 : // Allocating again should reuse the freed allocation.
263 E : size_t r = 0;
264 E : a = pa.Allocate(8, &r);
265 E : EXPECT_EQ(a_orig, a);
266 E : EXPECT_EQ(10u, r);
267 E : EXPECT_EQ(1u, pa.stats().page_count);
268 E : EXPECT_EQ(0u, pa.FreeObjects(0));
269 :
270 E : pa.Free(a, r);
271 E : EXPECT_EQ(1u, pa.stats().page_count);
272 E : EXPECT_EQ(10u, pa.FreeObjects(0)); // All size classes.
273 E : EXPECT_EQ(10u, pa.FreeObjects(10)); // Length 10 allocations only.
274 :
275 : // Allocated should use the freed allocation, and add the remainder to a
276 : // shorter free list.
277 E : a = pa.Allocate(8);
278 E : EXPECT_EQ(a_orig, a);
279 E : EXPECT_EQ(1u, pa.stats().page_count);
280 E : EXPECT_EQ(2u, pa.FreeObjects(0)); // All size classes.
281 E : EXPECT_EQ(2u, pa.FreeObjects(2)); // Length 2 allocations only.
282 :
283 : // The remainder should now be used.
284 E : a = pa.Allocate(2);
285 E : void* a_expected = reinterpret_cast<uint8*>(a_orig) + 16 * 8;
286 E : EXPECT_EQ(a_expected, a);
287 E : EXPECT_EQ(1u, pa.stats().page_count);
288 E : EXPECT_EQ(0u, pa.FreeObjects(0));
289 E : }
290 :
291 E : TEST(PageAllocatorTest, MultiStatsTest) {
292 E : TestPageAllocatorMulti255 pa;
293 :
294 E : EXPECT_EQ(0u, pa.stats().page_count);
295 E : EXPECT_EQ(0u, pa.stats().allocated_groups);
296 E : EXPECT_EQ(0u, pa.stats().allocated_objects);
297 E : EXPECT_EQ(0u, pa.stats().freed_groups);
298 E : EXPECT_EQ(0u, pa.stats().freed_objects);
299 :
300 E : void* a1 = pa.Allocate(10);
301 E : EXPECT_EQ(1u, pa.stats().page_count);
302 E : EXPECT_EQ(1u, pa.stats().allocated_groups);
303 E : EXPECT_EQ(10u, pa.stats().allocated_objects);
304 E : EXPECT_EQ(0u, pa.stats().freed_groups);
305 E : EXPECT_EQ(0u, pa.stats().freed_objects);
306 :
307 E : void* a2 = pa.Allocate(5);
308 E : EXPECT_EQ(1u, pa.stats().page_count);
309 E : EXPECT_EQ(2u, pa.stats().allocated_groups);
310 E : EXPECT_EQ(15u, pa.stats().allocated_objects);
311 E : EXPECT_EQ(0u, pa.stats().freed_groups);
312 E : EXPECT_EQ(0u, pa.stats().freed_objects);
313 :
314 E : pa.Free(a1, 10);
315 E : EXPECT_EQ(1u, pa.stats().page_count);
316 E : EXPECT_EQ(1u, pa.stats().allocated_groups);
317 E : EXPECT_EQ(5u, pa.stats().allocated_objects);
318 E : EXPECT_EQ(1u, pa.stats().freed_groups);
319 E : EXPECT_EQ(10u, pa.stats().freed_objects);
320 :
321 E : pa.Free(a2, 5);
322 E : EXPECT_EQ(1u, pa.stats().page_count);
323 E : EXPECT_EQ(0u, pa.stats().allocated_groups);
324 E : EXPECT_EQ(0u, pa.stats().allocated_objects);
325 E : EXPECT_EQ(2u, pa.stats().freed_groups);
326 E : EXPECT_EQ(15u, pa.stats().freed_objects);
327 :
328 : // This will take from the allocation of size 10,
329 : // and create a free group of size 3.
330 E : a1 = pa.Allocate(7);
331 E : EXPECT_EQ(1u, pa.stats().page_count);
332 E : EXPECT_EQ(1u, pa.stats().allocated_groups);
333 E : EXPECT_EQ(7u, pa.stats().allocated_objects);
334 E : EXPECT_EQ(2u, pa.stats().freed_groups);
335 E : EXPECT_EQ(8u, pa.stats().freed_objects);
336 :
337 : // This will take from the free group of size 5,
338 : // returning one more element than requested.
339 E : size_t received = 0;
340 E : a2 = pa.Allocate(4, &received);
341 E : EXPECT_EQ(5u, received);
342 E : EXPECT_EQ(1u, pa.stats().page_count);
343 E : EXPECT_EQ(2u, pa.stats().allocated_groups);
344 E : EXPECT_EQ(12u, pa.stats().allocated_objects);
345 E : EXPECT_EQ(1u, pa.stats().freed_groups);
346 E : EXPECT_EQ(3u, pa.stats().freed_objects);
347 E : }
348 :
349 E : TEST(TypedPageAllocatorTest, SingleEndToEnd) {
350 E : TypedPageAllocator<uint32, 1, 1000, true> pa;
351 E : for (size_t i = 0; i < 1600; ++i) {
352 E : uint32* alloc = pa.Allocate(1);
353 E : if ((i % 3) == 0)
354 E : pa.Free(alloc, 1);
355 E : }
356 E : }
357 :
358 E : TEST(TypedPageAllocatorTest, MultiEndToEnd) {
359 E : TypedPageAllocator<uint32, 10, 1000, true> pa;
360 E : for (size_t i = 0; i < 100; ++i) {
361 E : size_t requested = (i % 10) + 1;
362 E : size_t received = 0;
363 E : uint32* alloc = pa.Allocate(requested, &received);
364 E : if ((i % 3) == 0)
365 E : pa.Free(alloc, received);
366 E : }
367 :
368 E : for (size_t i = 0; i < 100; ++i) {
369 E : size_t requested = (i % 10) + 1;
370 E : uint32* alloc = pa.Allocate(requested);
371 E : if ((i % 3) == 0)
372 E : pa.Free(alloc, requested);
373 E : }
374 E : }
375 :
376 : } // namespace asan
377 : } // namespace agent
|