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