1ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany//===-- asan_fake_stack_test.cc -------------------------------------------===// 2ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// 3ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// The LLVM Compiler Infrastructure 4ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// 5ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// This file is distributed under the University of Illinois Open Source 6ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// License. See LICENSE.TXT for details. 7ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// 8ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany//===----------------------------------------------------------------------===// 9ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// 10ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// This file is a part of AddressSanitizer, an address sanity checker. 11ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// 12ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// Tests for FakeStack. 13ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// This test file should be compiled w/o asan instrumentation. 14ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany//===----------------------------------------------------------------------===// 15ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 16ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany#include "asan_fake_stack.h" 17ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany#include "asan_test_utils.h" 18ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany#include "sanitizer_common/sanitizer_common.h" 19ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 20ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany#include <assert.h> 21ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany#include <stdlib.h> 22ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany#include <stdio.h> 23ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 240f2283742e1d37ebf0c5ac034dab704a7d9af099Kostya Serebryany#include <map> 25ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 26ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryanynamespace __asan { 27ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 28ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya SerebryanyTEST(FakeStack, FlagsSize) { 29b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::SizeRequiredForFlags(10), 1U << 5); 30b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::SizeRequiredForFlags(11), 1U << 6); 31b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::SizeRequiredForFlags(20), 1U << 15); 32ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany} 33ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 34ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya SerebryanyTEST(FakeStack, RequiredSize) { 35ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // for (int i = 15; i < 20; i++) { 36ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // uptr alloc_size = FakeStack::RequiredSize(i); 37ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // printf("%zdK ==> %zd\n", 1 << (i - 10), alloc_size); 38ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // } 39b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::RequiredSize(15), 365568U); 40b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::RequiredSize(16), 727040U); 41b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::RequiredSize(17), 1449984U); 42b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::RequiredSize(18), 2895872U); 43b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::RequiredSize(19), 5787648U); 44ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany} 45ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 46ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya SerebryanyTEST(FakeStack, FlagsOffset) { 47ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany for (uptr stack_size_log = 15; stack_size_log <= 20; stack_size_log++) { 48ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr stack_size = 1UL << stack_size_log; 49ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr offset = 0; 50ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany for (uptr class_id = 0; class_id < FakeStack::kNumberOfSizeClasses; 51ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany class_id++) { 52ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr frame_size = FakeStack::BytesInSizeClass(class_id); 53ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr num_flags = stack_size / frame_size; 54ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany EXPECT_EQ(offset, FakeStack::FlagsOffset(stack_size_log, class_id)); 55ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // printf("%zd: %zd => %zd %zd\n", stack_size_log, class_id, offset, 56ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // FakeStack::FlagsOffset(stack_size_log, class_id)); 57ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany offset += num_flags; 58ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 59ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 60ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany} 61ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#if !defined(_WIN32) // FIXME: Fails due to OOM on Windows. 63ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya SerebryanyTEST(FakeStack, CreateDestroy) { 64ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany for (int i = 0; i < 1000; i++) { 65ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany for (uptr stack_size_log = 20; stack_size_log <= 22; stack_size_log++) { 66ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany FakeStack *fake_stack = FakeStack::Create(stack_size_log); 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines fake_stack->Destroy(0); 68ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 69ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 70ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany} 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif 72ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 73ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya SerebryanyTEST(FakeStack, ModuloNumberOfFrames) { 74b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 0, 0), 0U); 75b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 0, (1<<15)), 0U); 76b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 0, (1<<10)), 0U); 77b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 0, (1<<9)), 0U); 78b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 0, (1<<8)), 1U<<8); 79b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 0, (1<<15) + 1), 1U); 80ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 81b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 1, 0), 0U); 82b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 1, 1<<9), 0U); 83b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 1, 1<<8), 0U); 84b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 1, 1<<7), 1U<<7); 85ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 86b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 5, 0), 0U); 87b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 5, 1), 1U); 88b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 5, 15), 15U); 89b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 5, 16), 0U); 90b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(FakeStack::ModuloNumberOfFrames(15, 5, 17), 1U); 91ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany} 92ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 93ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya SerebryanyTEST(FakeStack, GetFrame) { 94ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany const uptr stack_size_log = 20; 95ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany const uptr stack_size = 1 << stack_size_log; 96ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany FakeStack *fs = FakeStack::Create(stack_size_log); 97ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany u8 *base = fs->GetFrame(stack_size_log, 0, 0); 98ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany EXPECT_EQ(base, reinterpret_cast<u8 *>(fs) + 99ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany fs->SizeRequiredForFlags(stack_size_log) + 4096); 100b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(base + 0*stack_size + 64 * 7, fs->GetFrame(stack_size_log, 0, 7U)); 101b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(base + 1*stack_size + 128 * 3, fs->GetFrame(stack_size_log, 1, 3U)); 102b1173c27c2791aef27304e68911a11648401064dKostya Serebryany EXPECT_EQ(base + 2*stack_size + 256 * 5, fs->GetFrame(stack_size_log, 2, 5U)); 1032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines fs->Destroy(0); 104ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany} 105ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 106ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya SerebryanyTEST(FakeStack, Allocate) { 107ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany const uptr stack_size_log = 19; 108ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany FakeStack *fs = FakeStack::Create(stack_size_log); 1090f2283742e1d37ebf0c5ac034dab704a7d9af099Kostya Serebryany std::map<FakeFrame *, uptr> s; 110ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany for (int iter = 0; iter < 2; iter++) { 111ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany s.clear(); 112ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany for (uptr cid = 0; cid < FakeStack::kNumberOfSizeClasses; cid++) { 113ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr n = FakeStack::NumberOfFrames(stack_size_log, cid); 114ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr bytes_in_class = FakeStack::BytesInSizeClass(cid); 115ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany for (uptr j = 0; j < n; j++) { 116ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany FakeFrame *ff = fs->Allocate(stack_size_log, cid, 0); 117ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr x = reinterpret_cast<uptr>(ff); 1180f2283742e1d37ebf0c5ac034dab704a7d9af099Kostya Serebryany EXPECT_TRUE(s.insert(std::make_pair(ff, cid)).second); 119ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany EXPECT_EQ(x, fs->AddrIsInFakeStack(x)); 120ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany EXPECT_EQ(x, fs->AddrIsInFakeStack(x + 1)); 121ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany EXPECT_EQ(x, fs->AddrIsInFakeStack(x + bytes_in_class - 1)); 122ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany EXPECT_NE(x, fs->AddrIsInFakeStack(x + bytes_in_class)); 123ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 124e1c68c319a0113be832da17a777892353a8b5f23Kostya Serebryany // We are out of fake stack, so Allocate should return 0. 125e1c68c319a0113be832da17a777892353a8b5f23Kostya Serebryany EXPECT_EQ(0UL, fs->Allocate(stack_size_log, cid, 0)); 126ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 1270f2283742e1d37ebf0c5ac034dab704a7d9af099Kostya Serebryany for (std::map<FakeFrame *, uptr>::iterator it = s.begin(); it != s.end(); 1280f2283742e1d37ebf0c5ac034dab704a7d9af099Kostya Serebryany ++it) { 129b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany fs->Deallocate(reinterpret_cast<uptr>(it->first), it->second); 130ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 131ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines fs->Destroy(0); 133ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany} 134ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 135ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryanystatic void RecursiveFunction(FakeStack *fs, int depth) { 136ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr class_id = depth / 3; 137ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany FakeFrame *ff = fs->Allocate(fs->stack_size_log(), class_id, 0); 138ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany if (depth) { 139ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany RecursiveFunction(fs, depth - 1); 140ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany RecursiveFunction(fs, depth - 1); 141ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 142b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany fs->Deallocate(reinterpret_cast<uptr>(ff), class_id); 143ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany} 144ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 145ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya SerebryanyTEST(FakeStack, RecursiveStressTest) { 146ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany const uptr stack_size_log = 16; 147ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany FakeStack *fs = FakeStack::Create(stack_size_log); 148ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany RecursiveFunction(fs, 22); // with 26 runs for 2-3 seconds. 1492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines fs->Destroy(0); 150ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany} 151ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 152ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany} // namespace __asan 153