1 //===-- asan_fake_stack.h ---------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file is a part of AddressSanitizer, an address sanity checker.
12 // ASan-private header for asan_fake_stack.cc, implements FakeStack.
13 //===----------------------------------------------------------------------===//
15 #ifndef ASAN_FAKE_STACK_H
16 #define ASAN_FAKE_STACK_H
18 #include "sanitizer_common/sanitizer_common.h"
22 // Fake stack frame contains local variables of one function.
24 uptr magic
; // Modified by the instrumented code.
25 uptr descr
; // Modified by the instrumented code.
26 uptr pc
; // Modified by the instrumented code.
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.
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.
58 static const uptr kMinStackFrameSizeLog
= 6; // Min frame is 64B.
59 static const uptr kMaxStackFrameSizeLog
= 16; // Max stack frame is 64K.
62 static const uptr kNumberOfSizeClasses
=
63 kMaxStackFrameSizeLog
- kMinStackFrameSizeLog
+ 1;
65 // CTOR: create the FakeStack as a single mmap-ed object.
66 static FakeStack
*Create(uptr stack_size_log
);
68 void Destroy(int tid
);
70 // stack_size_log is at least 15 (stack_size >= 32K).
71 static uptr
SizeRequiredForFlags(uptr stack_size_log
) {
72 return 1UL << (stack_size_log
+ 1 - kMinStackFrameSizeLog
);
75 // Each size class occupies stack_size bytes.
76 static uptr
SizeRequiredForFrames(uptr stack_size_log
) {
77 return (1ULL << stack_size_log
) * kNumberOfSizeClasses
;
80 // Number of bytes requires for the whole object.
81 static uptr
RequiredSize(uptr stack_size_log
) {
82 return kFlagsOffset
+ SizeRequiredForFlags(stack_size_log
) +
83 SizeRequiredForFrames(stack_size_log
);
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
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);
98 static uptr
NumberOfFrames(uptr stack_size_log
, uptr class_id
) {
99 return 1UL << (stack_size_log
- kMinStackFrameSizeLog
- class_id
);
102 // Divide n by the numbe of frames in size class.
103 static uptr
ModuloNumberOfFrames(uptr stack_size_log
, uptr class_id
, uptr n
) {
104 return n
& (NumberOfFrames(stack_size_log
, class_id
) - 1);
107 // The the pointer to the flags of the given 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
);
113 // Get frame by class_id and 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
;
120 // Allocate the fake frame.
121 FakeFrame
*Allocate(uptr stack_size_log
, uptr class_id
, uptr real_stack
);
123 // Deallocate the fake frame: read the saved flag address and write 0 there.
124 static void Deallocate(uptr x
, uptr class_id
) {
125 **SavedFlagPtr(x
, class_id
) = 0;
128 // Poison the entire FakeStack's shadow with the magic value.
129 void PoisonAll(u8 magic
);
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
);
133 USED uptr
AddrIsInFakeStack(uptr addr
) {
135 return AddrIsInFakeStack(addr
, &t1
, &t2
);
138 // Number of bytes in a fake frame of this size class.
139 static uptr
BytesInSizeClass(uptr class_id
) {
140 return 1UL << (class_id
+ kMinStackFrameSizeLog
);
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.
146 static u8
**SavedFlagPtr(uptr x
, uptr class_id
) {
147 return reinterpret_cast<u8
**>(x
+ BytesInSizeClass(class_id
) - sizeof(x
));
150 uptr
stack_size_log() const { return stack_size_log_
; }
152 void HandleNoReturn();
153 void GC(uptr real_stack
);
155 void ForEachFakeFrame(RangeIteratorCallback callback
, void *arg
);
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
;
164 uptr hint_position_
[kNumberOfSizeClasses
];
165 uptr stack_size_log_
;
166 // a bit is set if something was allocated from the corresponding size class.
170 FakeStack
*GetTLSFakeStack();
171 void SetTLSFakeStack(FakeStack
*fs
);
173 } // namespace __asan
175 #endif // ASAN_FAKE_STACK_H