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/heaps/zebra_block_heap.h"
16 :
17 : #include <algorithm>
18 : #include <set>
19 : #include <utility>
20 : #include <vector>
21 :
22 : #include "gmock/gmock.h"
23 : #include "gtest/gtest.h"
24 : #include "syzygy/agent/asan/unittest_util.h"
25 : #include "syzygy/common/align.h"
26 :
27 :
28 : namespace agent {
29 : namespace asan {
30 : namespace heaps {
31 :
32 : namespace {
33 :
34 : using ::common::IsAligned;
35 : using ::common::AlignDown;
36 : using ::common::AlignUp;
37 :
38 : using ::testing::_;
39 : using ::testing::Gt;
40 : using ::testing::NotNull;
41 : using ::testing::AtLeast;
42 :
43 E : testing::NullMemoryNotifier null_notifier;
44 E : testing::DummyHeap dummy_heap;
45 :
46 : class TestZebraBlockHeap : public ZebraBlockHeap {
47 : public:
48 : using ZebraBlockHeap::QuarantineInvariantIsSatisfied;
49 : using ZebraBlockHeap::heap_address_;
50 : using ZebraBlockHeap::slab_count_;
51 :
52 : static const size_t kInitialHeapSize = 8 * (1 << 20);
53 :
54 : // Creates a test heap with 8 MB initial (and maximum) memory using the
55 : // default memory notifier.
56 : TestZebraBlockHeap() : ZebraBlockHeap(kInitialHeapSize,
57 : &null_notifier,
58 E : &dummy_heap) { }
59 :
60 : // Creates a test heap with 8 MB initial (and maximum) memory using a custom
61 : // memory notifier.
62 E : explicit TestZebraBlockHeap(MemoryNotifierInterface* memory_notifier)
63 : : ZebraBlockHeap(kInitialHeapSize, memory_notifier, &dummy_heap) { }
64 :
65 : // Allows to know if the heap can handle more allocations.
66 : // @returns true if the heap is full (no more allocations allowed),
67 : // false otherwise.
68 E : bool IsHeapFull() {
69 : // No free slabs.
70 E : return free_slabs_.empty();
71 E : }
72 : };
73 :
74 : } // namespace
75 :
76 E : TEST(ZebraBlockHeapTest, GetHeapTypeIsValid) {
77 E : TestZebraBlockHeap h;
78 E : EXPECT_EQ(kZebraBlockHeap, h.GetHeapType());
79 E : }
80 :
81 E : TEST(ZebraBlockHeapTest, FeaturesAreValid) {
82 E : TestZebraBlockHeap h;
83 : EXPECT_EQ(HeapInterface::kHeapSupportsIsAllocated |
84 : HeapInterface::kHeapReportsReservations |
85 : HeapInterface::kHeapSupportsGetAllocationSize,
86 E : h.GetHeapFeatures());
87 E : }
88 :
89 E : TEST(ZebraBlockHeapTest, AllocateEmptyBlock) {
90 E : TestZebraBlockHeap h;
91 E : BlockLayout layout = {};
92 E : BlockInfo block = {};
93 :
94 : // Allocate and free a zero-sized allocation. This should succeed
95 : // by definition.
96 E : void* alloc = h.AllocateBlock(0, 0, 0, &layout);
97 E : EXPECT_NE(reinterpret_cast<void*>(NULL), alloc);
98 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
99 E : BlockInitialize(layout, alloc, false, &block);
100 E : EXPECT_TRUE(h.FreeBlock(block));
101 E : }
102 :
103 E : TEST(ZebraBlockHeapTest, EndToEnd) {
104 E : TestZebraBlockHeap h;
105 E : BlockLayout layout = {};
106 E : BlockInfo block = {};
107 :
108 : // Make a bunch of different sized allocations.
109 E : std::vector<BlockInfo> blocks;
110 E : for (size_t i = 1; i < 100; i++) {
111 E : void* alloc = h.AllocateBlock(i, 0, 0, &layout);
112 E : EXPECT_NE(reinterpret_cast<void*>(NULL), alloc);
113 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
114 E : BlockInitialize(layout, alloc, false, &block);
115 E : blocks.push_back(block);
116 E : }
117 :
118 : // Now free them.
119 E : for (size_t i = 0; i < blocks.size(); ++i)
120 E : EXPECT_TRUE(h.FreeBlock(blocks[i]));
121 E : }
122 :
123 E : TEST(ZebraBlockHeapTest, BlocksHaveCorrectAlignment) {
124 E : TestZebraBlockHeap h;
125 E : BlockLayout layout = {};
126 E : BlockInfo block = {};
127 :
128 : // Allocate blocks with different header, body and trailer sizes .
129 E : for (size_t header_size = 0; header_size < 100; header_size += 3) {
130 E : for (size_t trailer_size = 0; trailer_size < 100; trailer_size += 3) {
131 E : for (size_t body_size = 0; body_size < 100; body_size += 3) {
132 : void* alloc = h.AllocateBlock(body_size, header_size,
133 E : trailer_size, &layout);
134 :
135 E : EXPECT_NE(reinterpret_cast<void*>(NULL), alloc);
136 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
137 :
138 E : BlockInitialize(layout, alloc, false, &block);
139 :
140 : // The header (== block), body and the end of the trailer must be
141 : // kShadowRatio aligned.
142 E : EXPECT_TRUE(IsAligned(block.body, kShadowRatio));
143 E : EXPECT_TRUE(IsAligned(block.header, kShadowRatio));
144 E : EXPECT_TRUE(IsAligned(block.block, GetPageSize()));
145 E : EXPECT_TRUE(IsAligned(block.block + block.block_size, GetPageSize()));
146 :
147 : size_t right_redzone_size = (block.block + block.block_size) -
148 E : reinterpret_cast<uint8*>(block.trailer_padding);
149 :
150 E : EXPECT_EQ(2 * GetPageSize(), block.block_size);
151 E : EXPECT_LE(GetPageSize(), right_redzone_size);
152 :
153 : size_t body_offset = AlignUp(block.trailer_padding, GetPageSize()) -
154 E : block.trailer_padding;
155 :
156 : // The body must be as close as possible to the page.
157 E : EXPECT_GT(kShadowRatio, body_offset);
158 :
159 E : EXPECT_TRUE(h.FreeBlock(block));
160 E : }
161 E : }
162 E : }
163 E : }
164 :
165 E : TEST(ZebraBlockHeapTest, AllocateSizeLimits) {
166 E : TestZebraBlockHeap h;
167 :
168 : // Test all possible allocation sizes.
169 E : for (size_t i = 1; i <= GetPageSize(); ++i) {
170 E : uint8* alloc = reinterpret_cast<uint8*>(h.Allocate(i));
171 E : EXPECT_NE(reinterpret_cast<uint8*>(NULL), alloc);
172 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
173 E : EXPECT_TRUE(h.Free(alloc));
174 E : }
175 :
176 : // Impossible allocation sizes.
177 E : for (size_t delta = 1; delta < 10000; delta += 7)
178 E : EXPECT_EQ(reinterpret_cast<void*>(NULL), h.Allocate(GetPageSize() + delta));
179 E : }
180 :
181 :
182 E : TEST(ZebraBlockHeapTest, AllocateBlockSizeLimits) {
183 E : TestZebraBlockHeap h;
184 E : BlockLayout layout = {};
185 E : BlockInfo block = {};
186 :
187 E : const size_t kMaxAllowedBlockSize = GetPageSize() - sizeof(BlockHeader);
188 :
189 : // Allocate all possible block sizes.
190 E : for (size_t i = 0; i <= kMaxAllowedBlockSize; ++i) {
191 : uint8* alloc = reinterpret_cast<uint8*>(
192 E : h.AllocateBlock(i, sizeof(BlockHeader), sizeof(BlockTrailer), &layout));
193 :
194 E : EXPECT_NE(reinterpret_cast<void*>(NULL), alloc);
195 E : BlockInitialize(layout, alloc, false, &block);
196 E : EXPECT_TRUE(h.FreeBlock(block));
197 E : }
198 :
199 : // Impossible block sizes.
200 E : for (size_t delta = 1; delta < 10000; delta += 7)
201 : EXPECT_EQ(reinterpret_cast<uint8*>(NULL),
202 : h.AllocateBlock(kMaxAllowedBlockSize + delta,
203 : sizeof(BlockHeader), sizeof(BlockTrailer),
204 E : &layout));
205 E : }
206 :
207 E : TEST(ZebraBlockHeapTest, AllocateTwoEmptyBlocks) {
208 E : TestZebraBlockHeap h;
209 E : BlockLayout layout1 = {};
210 E : BlockLayout layout2 = {};
211 E : BlockInfo block1 = {};
212 E : BlockInfo block2 = {};
213 :
214 : void* mem1 = h.AllocateBlock(0, sizeof(BlockHeader), sizeof(BlockTrailer),
215 E : &layout1);
216 E : EXPECT_NE(reinterpret_cast<void*>(NULL), mem1);
217 E : EXPECT_TRUE(IsAligned(mem1, kShadowRatio));
218 :
219 : void* mem2 = h.AllocateBlock(0, sizeof(BlockHeader), sizeof(BlockTrailer),
220 E : &layout2);
221 E : EXPECT_NE(reinterpret_cast<void*>(NULL), mem2);
222 E : EXPECT_TRUE(IsAligned(mem2, kShadowRatio));
223 :
224 : // Empty blocks cannot have the same address.
225 E : EXPECT_NE(mem1, mem2);
226 :
227 E : BlockInitialize(layout1, mem1, false, &block1);
228 E : BlockInitialize(layout2, mem2, false, &block2);
229 :
230 E : EXPECT_TRUE(h.FreeBlock(block1));
231 E : EXPECT_TRUE(h.FreeBlock(block2));
232 E : }
233 :
234 :
235 E : TEST(ZebraBlockHeapTest, AllocateUntilFull) {
236 E : TestZebraBlockHeap h;
237 : // Test maximum number of allocations.
238 E : std::vector<uint8*> buffers;
239 E : for (size_t i = 0; i < h.slab_count_; ++i) {
240 E : uint8* alloc = reinterpret_cast<uint8*>(h.Allocate(0xFF));
241 E : EXPECT_NE(reinterpret_cast<uint8*>(NULL), alloc);
242 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
243 E : buffers.push_back(alloc);
244 E : }
245 :
246 : // The number of allocations should match the number of even pages.
247 E : EXPECT_EQ(h.slab_count_, buffers.size());
248 :
249 : // Impossible to allocate memory on a full heap.
250 E : EXPECT_EQ(reinterpret_cast<void*>(NULL), h.Allocate(0xFF));
251 :
252 : // Check that all buffers are at least page_size bytes apart.
253 E : std::sort(buffers.begin(), buffers.end());
254 E : for (size_t i = 1; i < buffers.size(); ++i)
255 E : EXPECT_LE(GetPageSize(), static_cast<size_t>(buffers[i] - buffers[i - 1]));
256 :
257 : // Cleanup.
258 E : for (size_t i = 0; i < buffers.size(); ++i)
259 E : EXPECT_TRUE(h.Free(buffers[i]));
260 E : }
261 :
262 E : TEST(ZebraBlockHeapTest, StressAllocateFree) {
263 E : TestZebraBlockHeap h;
264 :
265 : // Test maximum number of allocations.
266 E : std::vector<uint8*> buffers;
267 :
268 : // Fill the heap.
269 E : for (size_t i = 0; i < h.slab_count_; ++i) {
270 E : uint8* alloc = reinterpret_cast<uint8*>(h.Allocate(0xFF));
271 E : EXPECT_NE(reinterpret_cast<uint8*>(NULL), alloc);
272 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
273 E : buffers.push_back(alloc);
274 E : }
275 :
276 : // The number of allocations must match the number of even pages.
277 E : EXPECT_EQ(h.slab_count_, buffers.size());
278 : // Impossible to allocate memory on a full heap.
279 E : EXPECT_EQ(reinterpret_cast<void*>(NULL), h.Allocate(0xFF));
280 :
281 : // Shuffle the allocation order deterministically.
282 E : for (size_t i = 0; i < buffers.size(); ++i)
283 E : std::swap(buffers[i], buffers[(3 * i) % buffers.size()]);
284 :
285 : // Stress Allocate/Free (the heap starts full).
286 E : for (size_t i = 1; i < buffers.size() / 2; ++i) {
287 : // Free i blocks.
288 E : for (size_t j = 0; j < i; ++j) {
289 E : EXPECT_TRUE(h.Free(buffers.back()));
290 E : buffers.pop_back();
291 E : }
292 :
293 : // Allocates i blocks, so the heap is full again.
294 E : for (size_t j = 0; j < i; ++j) {
295 E : uint8* alloc = reinterpret_cast<uint8*>(h.Allocate(0xFF));
296 E : EXPECT_NE(reinterpret_cast<uint8*>(NULL), alloc);
297 E : buffers.push_back(alloc);
298 E : }
299 :
300 : // The number of allocations must match the number of even pages.
301 E : EXPECT_EQ(h.slab_count_, buffers.size());
302 : // Impossible to allocate memory on a full heap.
303 E : EXPECT_EQ(reinterpret_cast<void*>(NULL), h.Allocate(0xFF));
304 E : }
305 :
306 : // Cleanup.
307 E : for (size_t i = 0; i < buffers.size(); ++i)
308 E : EXPECT_TRUE(h.Free(buffers[i]));
309 E : }
310 :
311 E : TEST(ZebraBlockHeapTest, AllocateBlockCornerCases) {
312 E : TestZebraBlockHeap h;
313 E : BlockLayout layout = {};
314 E : BlockInfo block = {};
315 :
316 E : size_t block_header_size = sizeof(BlockHeader);
317 E : size_t block_trailer_size = sizeof(BlockTrailer);
318 :
319 : // Edge-case sizes for testing corner cases.
320 : const size_t kSizes[] = { 0, 1, 2, 3, 4, 5, 7, 8, 9, 15, 17, 1023, 1024, 1025,
321 : 1235, 1365, 2014, 2047, 2048, 2049, 3000, 7000, 12345,
322 : GetPageSize() - 1,
323 : GetPageSize(),
324 : GetPageSize() + 1,
325 : kShadowRatio - 1,
326 : kShadowRatio,
327 : kShadowRatio + 1,
328 : block_header_size - 1,
329 : block_header_size,
330 : block_header_size + 1,
331 : block_trailer_size - 1,
332 : block_trailer_size,
333 : block_trailer_size + 1,
334 : GetPageSize() - block_header_size - 1,
335 : GetPageSize() - block_header_size,
336 : GetPageSize() - block_header_size + 1,
337 : GetPageSize() - block_trailer_size - 1,
338 : GetPageSize() - block_trailer_size,
339 E : GetPageSize() - block_trailer_size + 1 };
340 :
341 E : for (size_t i = 0; i < arraysize(kSizes); ++i) {
342 E : for (size_t j = 0; j < arraysize(kSizes); ++j) {
343 E : for (size_t k = 0; k < arraysize(kSizes); ++k) {
344 E : size_t header_size = kSizes[i];
345 E : size_t body_size = kSizes[j];
346 E : size_t trailer_size = kSizes[k];
347 :
348 : // Check if there is capacity to do the allocation.
349 E : EXPECT_FALSE(h.IsHeapFull());
350 :
351 : void* alloc = h.AllocateBlock(body_size,
352 : header_size,
353 : trailer_size,
354 E : &layout);
355 :
356 E : if (alloc != NULL) {
357 : // Check that the block is well formed.
358 E : EXPECT_TRUE(header_size + body_size <= GetPageSize());
359 E : EXPECT_TRUE(trailer_size <= GetPageSize());
360 :
361 : size_t body_end_offset = layout.header_size +
362 E : layout.header_padding_size + layout.body_size;
363 :
364 : EXPECT_EQ(GetPageSize(),
365 E : ::common::AlignUp(body_end_offset, kShadowRatio));
366 E : BlockInitialize(layout, alloc, false, &block);
367 E : EXPECT_TRUE(h.FreeBlock(block));
368 E : } else {
369 : size_t body_end_offset = layout.header_size +
370 E : layout.header_padding_size + layout.body_size;
371 :
372 : // Check the cause of the unsuccessful allocation.
373 : EXPECT_TRUE(
374 : // Even page overflow.
375 : (header_size + body_size > GetPageSize()) ||
376 : // Odd page overflow.
377 : (trailer_size > GetPageSize()) ||
378 : // Incorrect body alignment.
379 : (GetPageSize() !=
380 E : ::common::AlignUp(body_end_offset, kShadowRatio)));
381 : }
382 E : }
383 E : }
384 E : }
385 E : }
386 :
387 E : TEST(ZebraBlockHeapTest, IsAllocated) {
388 E : TestZebraBlockHeap h;
389 :
390 E : EXPECT_FALSE(h.IsAllocated(NULL));
391 :
392 E : void* a = h.Allocate(100);
393 E : EXPECT_TRUE(h.IsAllocated(a));
394 E : EXPECT_FALSE(h.IsAllocated(reinterpret_cast<uint8*>(a) - 1));
395 E : EXPECT_FALSE(h.IsAllocated(reinterpret_cast<uint8*>(a) + 1));
396 :
397 E : h.Free(a);
398 E : EXPECT_FALSE(h.IsAllocated(a));
399 E : }
400 :
401 E : TEST(ZebraBlockHeapTest, GetAllocationSize) {
402 E : TestZebraBlockHeap h;
403 :
404 E : void* alloc = h.Allocate(67);
405 E : ASSERT_TRUE(alloc != NULL);
406 E : EXPECT_EQ(67u, h.GetAllocationSize(alloc));
407 E : }
408 :
409 E : TEST(ZebraBlockHeapTest, PushPopInvariant) {
410 E : TestZebraBlockHeap h;
411 E : BlockLayout layout = {};
412 E : BlockInfo block = {};
413 :
414 : // Fill the heap.
415 E : std::vector<BlockInfo> blocks;
416 E : for (size_t i = 0; i < h.slab_count_; i++) {
417 E : void* alloc = h.AllocateBlock(0xFF, 0, 0, &layout);
418 E : EXPECT_NE(reinterpret_cast<void*>(NULL), alloc);
419 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
420 E : BlockInitialize(layout, alloc, false, &block);
421 E : blocks.push_back(block);
422 E : CompactBlockInfo compact = {};
423 E : ConvertBlockInfo(block, &compact);
424 E : EXPECT_TRUE(h.Push(compact));
425 E : }
426 :
427 E : for (size_t i = 0; i < h.slab_count_; i++) {
428 E : CompactBlockInfo dummy = {};
429 E : bool old_invariant = h.QuarantineInvariantIsSatisfied();
430 E : if (h.Pop(&dummy)) {
431 E : EXPECT_FALSE(old_invariant);
432 E : } else {
433 E : EXPECT_TRUE(old_invariant);
434 E : EXPECT_TRUE(h.QuarantineInvariantIsSatisfied());
435 E : break;
436 : }
437 E : }
438 :
439 : // Clear the quarantine.
440 E : std::vector<CompactBlockInfo> objects;
441 E : h.Empty(&objects);
442 :
443 : // Blocks can be freed now.
444 E : for (size_t i = 0; i < blocks.size(); i++)
445 E : EXPECT_TRUE(h.FreeBlock(blocks[i]));
446 E : }
447 :
448 E : TEST(ZebraBlockHeapTest, MemoryNotifierIsCalled) {
449 E : testing::MockMemoryNotifier mock_notifier;
450 :
451 : // Should be called exactly once when reserving the initial memory.
452 : EXPECT_CALL(mock_notifier,
453 : NotifyFutureHeapUse(NotNull(), Gt(0u)))
454 E : .Times(1);
455 :
456 : // Should be called in the ZebraBlockHeap destructor.
457 : EXPECT_CALL(mock_notifier,
458 : NotifyReturnedToOS(NotNull(), Gt(0u)))
459 E : .Times(1);
460 :
461 E : TestZebraBlockHeap h(&mock_notifier);
462 E : h.Allocate(10);
463 E : }
464 :
465 E : TEST(ZebraBlockHeapTest, Lock) {
466 E : TestZebraBlockHeap h;
467 :
468 E : h.Lock();
469 E : EXPECT_TRUE(h.TryLock());
470 E : h.Unlock();
471 E : h.Unlock();
472 E : }
473 :
474 : } // namespace heaps
475 : } // namespace asan
476 : } // namespace agent
|