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