* tree-cfg.c (verify_gimple_in_cfg): Call verify_location on the
[official-gcc.git] / libsanitizer / asan / asan_fake_stack.h
blob6ac61ddd24e9ff7f4fb58498a332b8b1a005d946
1 //===-- asan_fake_stack.h ---------------------------------------*- C++ -*-===//
2 //
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
5 //
6 //===----------------------------------------------------------------------===//
7 //
8 // This file is a part of AddressSanitizer, an address sanity checker.
9 //
10 // ASan-private header for asan_fake_stack.cc, implements FakeStack.
11 //===----------------------------------------------------------------------===//
13 #ifndef ASAN_FAKE_STACK_H
14 #define ASAN_FAKE_STACK_H
16 #include "sanitizer_common/sanitizer_common.h"
18 namespace __asan {
20 // Fake stack frame contains local variables of one function.
21 struct FakeFrame {
22 uptr magic; // Modified by the instrumented code.
23 uptr descr; // Modified by the instrumented code.
24 uptr pc; // Modified by the instrumented code.
25 uptr real_stack;
28 // For each thread we create a fake stack and place stack objects on this fake
29 // stack instead of the real stack. The fake stack is not really a stack but
30 // a fast malloc-like allocator so that when a function exits the fake stack
31 // is not popped but remains there for quite some time until gets used again.
32 // So, we poison the objects on the fake stack when function returns.
33 // It helps us find use-after-return bugs.
35 // The FakeStack objects is allocated by a single mmap call and has no other
36 // pointers. The size of the fake stack depends on the actual thread stack size
37 // and thus can not be a constant.
38 // stack_size is a power of two greater or equal to the thread's stack size;
39 // we store it as its logarithm (stack_size_log).
40 // FakeStack has kNumberOfSizeClasses (11) size classes, each size class
41 // is a power of two, starting from 64 bytes. Each size class occupies
42 // stack_size bytes and thus can allocate
43 // NumberOfFrames=(stack_size/BytesInSizeClass) fake frames (also a power of 2).
44 // For each size class we have NumberOfFrames allocation flags,
45 // each flag indicates whether the given frame is currently allocated.
46 // All flags for size classes 0 .. 10 are stored in a single contiguous region
47 // followed by another contiguous region which contains the actual memory for
48 // size classes. The addresses are computed by GetFlags and GetFrame without
49 // any memory accesses solely based on 'this' and stack_size_log.
50 // Allocate() flips the appropriate allocation flag atomically, thus achieving
51 // async-signal safety.
52 // This allocator does not have quarantine per se, but it tries to allocate the
53 // frames in round robin fashion to maximize the delay between a deallocation
54 // and the next allocation.
55 class FakeStack {
56 static const uptr kMinStackFrameSizeLog = 6; // Min frame is 64B.
57 static const uptr kMaxStackFrameSizeLog = 16; // Max stack frame is 64K.
59 public:
60 static const uptr kNumberOfSizeClasses =
61 kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1;
63 // CTOR: create the FakeStack as a single mmap-ed object.
64 static FakeStack *Create(uptr stack_size_log);
66 void Destroy(int tid);
68 // stack_size_log is at least 15 (stack_size >= 32K).
69 static uptr SizeRequiredForFlags(uptr stack_size_log) {
70 return ((uptr)1) << (stack_size_log + 1 - kMinStackFrameSizeLog);
73 // Each size class occupies stack_size bytes.
74 static uptr SizeRequiredForFrames(uptr stack_size_log) {
75 return (((uptr)1) << stack_size_log) * kNumberOfSizeClasses;
78 // Number of bytes requires for the whole object.
79 static uptr RequiredSize(uptr stack_size_log) {
80 return kFlagsOffset + SizeRequiredForFlags(stack_size_log) +
81 SizeRequiredForFrames(stack_size_log);
84 // Offset of the given flag from the first flag.
85 // The flags for class 0 begin at offset 000000000
86 // The flags for class 1 begin at offset 100000000
87 // ....................2................ 110000000
88 // ....................3................ 111000000
89 // and so on.
90 static uptr FlagsOffset(uptr stack_size_log, uptr class_id) {
91 uptr t = kNumberOfSizeClasses - 1 - class_id;
92 const uptr all_ones = (((uptr)1) << (kNumberOfSizeClasses - 1)) - 1;
93 return ((all_ones >> t) << t) << (stack_size_log - 15);
96 static uptr NumberOfFrames(uptr stack_size_log, uptr class_id) {
97 return ((uptr)1) << (stack_size_log - kMinStackFrameSizeLog - class_id);
100 // Divide n by the number of frames in size class.
101 static uptr ModuloNumberOfFrames(uptr stack_size_log, uptr class_id, uptr n) {
102 return n & (NumberOfFrames(stack_size_log, class_id) - 1);
105 // The pointer to the flags of the given class_id.
106 u8 *GetFlags(uptr stack_size_log, uptr class_id) {
107 return reinterpret_cast<u8 *>(this) + kFlagsOffset +
108 FlagsOffset(stack_size_log, class_id);
111 // Get frame by class_id and pos.
112 u8 *GetFrame(uptr stack_size_log, uptr class_id, uptr pos) {
113 return reinterpret_cast<u8 *>(this) + kFlagsOffset +
114 SizeRequiredForFlags(stack_size_log) +
115 (((uptr)1) << stack_size_log) * class_id +
116 BytesInSizeClass(class_id) * pos;
119 // Allocate the fake frame.
120 FakeFrame *Allocate(uptr stack_size_log, uptr class_id, uptr real_stack);
122 // Deallocate the fake frame: read the saved flag address and write 0 there.
123 static void Deallocate(uptr x, uptr class_id) {
124 **SavedFlagPtr(x, class_id) = 0;
127 // Poison the entire FakeStack's shadow with the magic value.
128 void PoisonAll(u8 magic);
130 // Return the beginning of the FakeFrame or 0 if the address is not ours.
131 uptr AddrIsInFakeStack(uptr addr, uptr *frame_beg, uptr *frame_end);
132 USED uptr AddrIsInFakeStack(uptr addr) {
133 uptr t1, t2;
134 return AddrIsInFakeStack(addr, &t1, &t2);
137 // Number of bytes in a fake frame of this size class.
138 static uptr BytesInSizeClass(uptr class_id) {
139 return ((uptr)1) << (class_id + kMinStackFrameSizeLog);
142 // The fake frame is guaranteed to have a right redzone.
143 // We use the last word of that redzone to store the address of the flag
144 // that corresponds to the current frame to make faster deallocation.
145 static u8 **SavedFlagPtr(uptr x, uptr class_id) {
146 return reinterpret_cast<u8 **>(x + BytesInSizeClass(class_id) - sizeof(x));
149 uptr stack_size_log() const { return stack_size_log_; }
151 void HandleNoReturn();
152 void GC(uptr real_stack);
154 void ForEachFakeFrame(RangeIteratorCallback callback, void *arg);
156 private:
157 FakeStack() { }
158 static const uptr kFlagsOffset = 4096; // This is were the flags begin.
159 // Must match the number of uses of DEFINE_STACK_MALLOC_FREE_WITH_CLASS_ID
160 COMPILER_CHECK(kNumberOfSizeClasses == 11);
161 static const uptr kMaxStackMallocSize = ((uptr)1) << kMaxStackFrameSizeLog;
163 uptr hint_position_[kNumberOfSizeClasses];
164 uptr stack_size_log_;
165 // a bit is set if something was allocated from the corresponding size class.
166 bool needs_gc_;
169 FakeStack *GetTLSFakeStack();
170 void SetTLSFakeStack(FakeStack *fs);
172 } // namespace __asan
174 #endif // ASAN_FAKE_STACK_H