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.header, GetPageSize()));
145 E : EXPECT_TRUE(IsAligned(block.trailer + 1, GetPageSize()));
146 :
147 E : size_t right_redzone_size = block.TotalTrailerSize();
148 :
149 E : EXPECT_EQ(2 * GetPageSize(), block.block_size);
150 E : EXPECT_LE(GetPageSize(), right_redzone_size);
151 :
152 : size_t body_offset = AlignUp(block.RawTrailerPadding(), GetPageSize()) -
153 E : block.RawTrailerPadding();
154 :
155 : // The body must be as close as possible to the page.
156 E : EXPECT_GT(kShadowRatio, body_offset);
157 :
158 E : EXPECT_TRUE(h.FreeBlock(block));
159 E : }
160 E : }
161 E : }
162 E : }
163 :
164 E : TEST(ZebraBlockHeapTest, AllocateSizeLimits) {
165 E : TestZebraBlockHeap h;
166 :
167 : // Test all possible allocation sizes.
168 E : for (size_t i = 1; i <= GetPageSize(); ++i) {
169 E : uint8* alloc = reinterpret_cast<uint8*>(h.Allocate(i));
170 E : EXPECT_NE(reinterpret_cast<uint8*>(NULL), alloc);
171 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
172 E : EXPECT_TRUE(h.Free(alloc));
173 E : }
174 :
175 : // Impossible allocation sizes.
176 E : for (size_t delta = 1; delta < 10000; delta += 7)
177 E : EXPECT_EQ(reinterpret_cast<void*>(NULL), h.Allocate(GetPageSize() + delta));
178 E : }
179 :
180 :
181 E : TEST(ZebraBlockHeapTest, AllocateBlockSizeLimits) {
182 E : TestZebraBlockHeap h;
183 E : BlockLayout layout = {};
184 E : BlockInfo block = {};
185 :
186 E : const size_t kMaxAllowedBlockSize = GetPageSize() - sizeof(BlockHeader);
187 :
188 : // Allocate all possible block sizes.
189 E : for (size_t i = 0; i <= kMaxAllowedBlockSize; ++i) {
190 : uint8* alloc = reinterpret_cast<uint8*>(
191 E : h.AllocateBlock(i, sizeof(BlockHeader), sizeof(BlockTrailer), &layout));
192 :
193 E : EXPECT_NE(reinterpret_cast<void*>(NULL), alloc);
194 E : BlockInitialize(layout, alloc, false, &block);
195 E : EXPECT_TRUE(h.FreeBlock(block));
196 E : }
197 :
198 : // Impossible block sizes.
199 E : for (size_t delta = 1; delta < 10000; delta += 7)
200 : EXPECT_EQ(reinterpret_cast<uint8*>(NULL),
201 : h.AllocateBlock(kMaxAllowedBlockSize + delta,
202 : sizeof(BlockHeader), sizeof(BlockTrailer),
203 E : &layout));
204 E : }
205 :
206 E : TEST(ZebraBlockHeapTest, AllocateTwoEmptyBlocks) {
207 E : TestZebraBlockHeap h;
208 E : BlockLayout layout1 = {};
209 E : BlockLayout layout2 = {};
210 E : BlockInfo block1 = {};
211 E : BlockInfo block2 = {};
212 :
213 : void* mem1 = h.AllocateBlock(0, sizeof(BlockHeader), sizeof(BlockTrailer),
214 E : &layout1);
215 E : EXPECT_NE(reinterpret_cast<void*>(NULL), mem1);
216 E : EXPECT_TRUE(IsAligned(mem1, kShadowRatio));
217 :
218 : void* mem2 = h.AllocateBlock(0, sizeof(BlockHeader), sizeof(BlockTrailer),
219 E : &layout2);
220 E : EXPECT_NE(reinterpret_cast<void*>(NULL), mem2);
221 E : EXPECT_TRUE(IsAligned(mem2, kShadowRatio));
222 :
223 : // Empty blocks cannot have the same address.
224 E : EXPECT_NE(mem1, mem2);
225 :
226 E : BlockInitialize(layout1, mem1, false, &block1);
227 E : BlockInitialize(layout2, mem2, false, &block2);
228 :
229 E : EXPECT_TRUE(h.FreeBlock(block1));
230 E : EXPECT_TRUE(h.FreeBlock(block2));
231 E : }
232 :
233 :
234 E : TEST(ZebraBlockHeapTest, AllocateUntilFull) {
235 E : TestZebraBlockHeap h;
236 : // Test maximum number of allocations.
237 E : std::vector<uint8*> buffers;
238 E : for (size_t i = 0; i < h.slab_count_; ++i) {
239 E : uint8* alloc = reinterpret_cast<uint8*>(h.Allocate(0xFF));
240 E : EXPECT_NE(reinterpret_cast<uint8*>(NULL), alloc);
241 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
242 E : buffers.push_back(alloc);
243 E : }
244 :
245 : // The number of allocations should match the number of even pages.
246 E : EXPECT_EQ(h.slab_count_, buffers.size());
247 :
248 : // Impossible to allocate memory on a full heap.
249 E : EXPECT_EQ(reinterpret_cast<void*>(NULL), h.Allocate(0xFF));
250 :
251 : // Check that all buffers are at least page_size bytes apart.
252 E : std::sort(buffers.begin(), buffers.end());
253 E : for (size_t i = 1; i < buffers.size(); ++i)
254 E : EXPECT_LE(GetPageSize(), static_cast<size_t>(buffers[i] - buffers[i - 1]));
255 :
256 : // Cleanup.
257 E : for (size_t i = 0; i < buffers.size(); ++i)
258 E : EXPECT_TRUE(h.Free(buffers[i]));
259 E : }
260 :
261 E : TEST(ZebraBlockHeapTest, StressAllocateFree) {
262 E : TestZebraBlockHeap h;
263 :
264 : // Test maximum number of allocations.
265 E : std::vector<uint8*> buffers;
266 :
267 : // Fill the heap.
268 E : for (size_t i = 0; i < h.slab_count_; ++i) {
269 E : uint8* alloc = reinterpret_cast<uint8*>(h.Allocate(0xFF));
270 E : EXPECT_NE(reinterpret_cast<uint8*>(NULL), alloc);
271 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
272 E : buffers.push_back(alloc);
273 E : }
274 :
275 : // The number of allocations must match the number of even pages.
276 E : EXPECT_EQ(h.slab_count_, buffers.size());
277 : // Impossible to allocate memory on a full heap.
278 E : EXPECT_EQ(reinterpret_cast<void*>(NULL), h.Allocate(0xFF));
279 :
280 : // Shuffle the allocation order deterministically.
281 E : for (size_t i = 0; i < buffers.size(); ++i)
282 E : std::swap(buffers[i], buffers[(3 * i) % buffers.size()]);
283 :
284 : // Stress Allocate/Free (the heap starts full).
285 E : for (size_t i = 1; i < buffers.size() / 2; ++i) {
286 : // Free i blocks.
287 E : for (size_t j = 0; j < i; ++j) {
288 E : EXPECT_TRUE(h.Free(buffers.back()));
289 E : buffers.pop_back();
290 E : }
291 :
292 : // Allocates i blocks, so the heap is full again.
293 E : for (size_t j = 0; j < i; ++j) {
294 E : uint8* alloc = reinterpret_cast<uint8*>(h.Allocate(0xFF));
295 E : EXPECT_NE(reinterpret_cast<uint8*>(NULL), alloc);
296 E : buffers.push_back(alloc);
297 E : }
298 :
299 : // The number of allocations must match the number of even pages.
300 E : EXPECT_EQ(h.slab_count_, buffers.size());
301 : // Impossible to allocate memory on a full heap.
302 E : EXPECT_EQ(reinterpret_cast<void*>(NULL), h.Allocate(0xFF));
303 E : }
304 :
305 : // Cleanup.
306 E : for (size_t i = 0; i < buffers.size(); ++i)
307 E : EXPECT_TRUE(h.Free(buffers[i]));
308 E : }
309 :
310 E : TEST(ZebraBlockHeapTest, AllocateBlockCornerCases) {
311 E : TestZebraBlockHeap h;
312 E : BlockLayout layout = {};
313 E : BlockInfo block = {};
314 :
315 E : size_t block_header_size = sizeof(BlockHeader);
316 E : size_t block_trailer_size = sizeof(BlockTrailer);
317 :
318 : // Edge-case sizes for testing corner cases.
319 : const size_t kSizes[] = { 0, 1, 2, 3, 4, 5, 7, 8, 9, 15, 17, 1023, 1024, 1025,
320 : 1235, 1365, 2014, 2047, 2048, 2049, 3000, 7000, 12345,
321 : GetPageSize() - 1,
322 : GetPageSize(),
323 : GetPageSize() + 1,
324 : kShadowRatio - 1,
325 : kShadowRatio,
326 : kShadowRatio + 1,
327 : block_header_size - 1,
328 : block_header_size,
329 : block_header_size + 1,
330 : block_trailer_size - 1,
331 : block_trailer_size,
332 : block_trailer_size + 1,
333 : GetPageSize() - block_header_size - 1,
334 : GetPageSize() - block_header_size,
335 : GetPageSize() - block_header_size + 1,
336 : GetPageSize() - block_trailer_size - 1,
337 : GetPageSize() - block_trailer_size,
338 E : GetPageSize() - block_trailer_size + 1 };
339 :
340 E : for (size_t i = 0; i < arraysize(kSizes); ++i) {
341 E : for (size_t j = 0; j < arraysize(kSizes); ++j) {
342 E : for (size_t k = 0; k < arraysize(kSizes); ++k) {
343 E : size_t header_size = kSizes[i];
344 E : size_t body_size = kSizes[j];
345 E : size_t trailer_size = kSizes[k];
346 :
347 : // Check if there is capacity to do the allocation.
348 E : EXPECT_FALSE(h.IsHeapFull());
349 :
350 : void* alloc = h.AllocateBlock(body_size,
351 : header_size,
352 : trailer_size,
353 E : &layout);
354 :
355 E : if (alloc != NULL) {
356 : // Check that the block is well formed.
357 E : EXPECT_TRUE(header_size + body_size <= GetPageSize());
358 E : EXPECT_TRUE(trailer_size <= GetPageSize());
359 :
360 : size_t body_end_offset = layout.header_size +
361 E : layout.header_padding_size + layout.body_size;
362 :
363 : EXPECT_EQ(GetPageSize(),
364 E : ::common::AlignUp(body_end_offset, kShadowRatio));
365 E : BlockInitialize(layout, alloc, false, &block);
366 E : EXPECT_TRUE(h.FreeBlock(block));
367 E : } else {
368 : size_t body_end_offset = layout.header_size +
369 E : layout.header_padding_size + layout.body_size;
370 :
371 : // Check the cause of the unsuccessful allocation.
372 : EXPECT_TRUE(
373 : // Even page overflow.
374 : (header_size + body_size > GetPageSize()) ||
375 : // Odd page overflow.
376 : (trailer_size > GetPageSize()) ||
377 : // Incorrect body alignment.
378 : (GetPageSize() !=
379 E : ::common::AlignUp(body_end_offset, kShadowRatio)));
380 : }
381 E : }
382 E : }
383 E : }
384 E : }
385 :
386 E : TEST(ZebraBlockHeapTest, IsAllocated) {
387 E : TestZebraBlockHeap h;
388 :
389 E : EXPECT_FALSE(h.IsAllocated(NULL));
390 :
391 E : void* a = h.Allocate(100);
392 E : EXPECT_TRUE(h.IsAllocated(a));
393 E : EXPECT_FALSE(h.IsAllocated(reinterpret_cast<uint8*>(a) - 1));
394 E : EXPECT_FALSE(h.IsAllocated(reinterpret_cast<uint8*>(a) + 1));
395 :
396 E : h.Free(a);
397 E : EXPECT_FALSE(h.IsAllocated(a));
398 E : }
399 :
400 E : TEST(ZebraBlockHeapTest, GetAllocationSize) {
401 E : TestZebraBlockHeap h;
402 :
403 E : void* alloc = h.Allocate(67);
404 E : ASSERT_TRUE(alloc != NULL);
405 E : EXPECT_EQ(67u, h.GetAllocationSize(alloc));
406 E : }
407 :
408 E : TEST(ZebraBlockHeapTest, PushPopInvariant) {
409 E : TestZebraBlockHeap h;
410 E : BlockLayout layout = {};
411 E : BlockInfo block = {};
412 :
413 : // Fill the heap.
414 E : std::vector<BlockInfo> blocks;
415 E : for (size_t i = 0; i < h.slab_count_; i++) {
416 E : void* alloc = h.AllocateBlock(0xFF, 0, 0, &layout);
417 E : EXPECT_NE(reinterpret_cast<void*>(NULL), alloc);
418 E : EXPECT_TRUE(IsAligned(alloc, kShadowRatio));
419 E : BlockInitialize(layout, alloc, false, &block);
420 E : blocks.push_back(block);
421 E : CompactBlockInfo compact = {};
422 E : ConvertBlockInfo(block, &compact);
423 E : EXPECT_TRUE(h.Push(compact));
424 E : }
425 :
426 E : for (size_t i = 0; i < h.slab_count_; i++) {
427 E : CompactBlockInfo dummy = {};
428 E : bool old_invariant = h.QuarantineInvariantIsSatisfied();
429 E : if (h.Pop(&dummy)) {
430 E : EXPECT_FALSE(old_invariant);
431 E : } else {
432 E : EXPECT_TRUE(old_invariant);
433 E : EXPECT_TRUE(h.QuarantineInvariantIsSatisfied());
434 E : break;
435 : }
436 E : }
437 :
438 : // Clear the quarantine.
439 E : std::vector<CompactBlockInfo> objects;
440 E : h.Empty(&objects);
441 :
442 : // Blocks can be freed now.
443 E : for (size_t i = 0; i < blocks.size(); i++)
444 E : EXPECT_TRUE(h.FreeBlock(blocks[i]));
445 E : }
446 :
447 E : TEST(ZebraBlockHeapTest, MemoryNotifierIsCalled) {
448 E : testing::MockMemoryNotifier mock_notifier;
449 :
450 : // Should be called exactly once when reserving the initial memory.
451 : EXPECT_CALL(mock_notifier,
452 : NotifyFutureHeapUse(NotNull(), Gt(0u)))
453 E : .Times(1);
454 :
455 : // Should be called in the ZebraBlockHeap destructor.
456 : EXPECT_CALL(mock_notifier,
457 : NotifyReturnedToOS(NotNull(), Gt(0u)))
458 E : .Times(1);
459 :
460 E : TestZebraBlockHeap h(&mock_notifier);
461 E : h.Allocate(10);
462 E : }
463 :
464 E : TEST(ZebraBlockHeapTest, Lock) {
465 E : TestZebraBlockHeap h;
466 :
467 E : h.Lock();
468 E : EXPECT_TRUE(h.TryLock());
469 E : h.Unlock();
470 E : h.Unlock();
471 E : }
472 :
473 : } // namespace heaps
474 : } // namespace asan
475 : } // namespace agent
|