1//===-- asan_fake_stack.h ---------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file is a part of AddressSanitizer, an address sanity checker.
10//
11// ASan-private header for asan_fake_stack.cpp, implements FakeStack.
12//===----------------------------------------------------------------------===//
13
14#ifndef ASAN_FAKE_STACK_H
15#define ASAN_FAKE_STACK_H
16
17#include "sanitizer_common/sanitizer_common.h"
18
19namespace __asan {
20
21// Fake stack frame contains local variables of one function.
22struct FakeFrame {
23 uptr magic; // Modified by the instrumented code.
24 uptr descr; // Modified by the instrumented code.
25 uptr pc; // Modified by the instrumented code.
26 uptr real_stack;
27};
28
29// For each thread we create a fake stack and place stack objects on this fake
30// stack instead of the real stack. The fake stack is not really a stack but
31// a fast malloc-like allocator so that when a function exits the fake stack
32// is not popped but remains there for quite some time until gets used again.
33// So, we poison the objects on the fake stack when function returns.
34// It helps us find use-after-return bugs.
35//
36// The FakeStack objects is allocated by a single mmap call and has no other
37// pointers. The size of the fake stack depends on the actual thread stack size
38// and thus can not be a constant.
39// stack_size is a power of two greater or equal to the thread's stack size;
40// we store it as its logarithm (stack_size_log).
41// FakeStack has kNumberOfSizeClasses (11) size classes, each size class
42// is a power of two, starting from 64 bytes. Each size class occupies
43// stack_size bytes and thus can allocate
44// NumberOfFrames=(stack_size/BytesInSizeClass) fake frames (also a power of 2).
45// For each size class we have NumberOfFrames allocation flags,
46// each flag indicates whether the given frame is currently allocated.
47// All flags for size classes 0 .. 10 are stored in a single contiguous region
48// followed by another contiguous region which contains the actual memory for
49// size classes. The addresses are computed by GetFlags and GetFrame without
50// any memory accesses solely based on 'this' and stack_size_log.
51// Allocate() flips the appropriate allocation flag atomically, thus achieving
52// async-signal safety.
53// This allocator does not have quarantine per se, but it tries to allocate the
54// frames in round robin fashion to maximize the delay between a deallocation
55// and the next allocation.
56class FakeStack {
57 static const uptr kMinStackFrameSizeLog = 6; // Min frame is 64B.
58 static const uptr kMaxStackFrameSizeLog = 16; // Max stack frame is 64K.
59
60 public:
61 static const uptr kNumberOfSizeClasses =
62 kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1;
63
64 // CTOR: create the FakeStack as a single mmap-ed object.
65 static FakeStack *Create(uptr stack_size_log);
66
67 void Destroy(int tid);
68
69 // stack_size_log is at least 15 (stack_size >= 32K).
70 static uptr SizeRequiredForFlags(uptr stack_size_log) {
71 return ((uptr)1) << (stack_size_log + 1 - kMinStackFrameSizeLog);
72 }
73
74 // Each size class occupies stack_size bytes.
75 static uptr SizeRequiredForFrames(uptr stack_size_log) {
76 return (((uptr)1) << stack_size_log) * kNumberOfSizeClasses;
77 }
78
79 // Number of bytes requires for the whole object.
80 static uptr RequiredSize(uptr stack_size_log) {
81 return kFlagsOffset + SizeRequiredForFlags(stack_size_log) +
82 SizeRequiredForFrames(stack_size_log);
83 }
84
85 // Offset of the given flag from the first flag.
86 // The flags for class 0 begin at offset 000000000
87 // The flags for class 1 begin at offset 100000000
88 // ....................2................ 110000000
89 // ....................3................ 111000000
90 // and so on.
91 static uptr FlagsOffset(uptr stack_size_log, uptr class_id) {
92 uptr t = kNumberOfSizeClasses - 1 - class_id;
93 const uptr all_ones = (((uptr)1) << (kNumberOfSizeClasses - 1)) - 1;
94 return ((all_ones >> t) << t) << (stack_size_log - 15);
95 }
96
97 static uptr NumberOfFrames(uptr stack_size_log, uptr class_id) {
98 return ((uptr)1) << (stack_size_log - kMinStackFrameSizeLog - class_id);
99 }
100
101 // Divide n by the number of frames in size class.
102 static uptr ModuloNumberOfFrames(uptr stack_size_log, uptr class_id, uptr n) {
103 return n & (NumberOfFrames(stack_size_log, class_id) - 1);
104 }
105
106 // The pointer to the flags of the given class_id.
107 u8 *GetFlags(uptr stack_size_log, uptr class_id) {
108 return reinterpret_cast<u8 *>(this) + kFlagsOffset +
109 FlagsOffset(stack_size_log, class_id);
110 }
111
112 // Get frame by class_id and pos.
113 u8 *GetFrame(uptr stack_size_log, uptr class_id, uptr pos) {
114 return reinterpret_cast<u8 *>(this) + kFlagsOffset +
115 SizeRequiredForFlags(stack_size_log) +
116 (((uptr)1) << stack_size_log) * class_id +
117 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.
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);
133 USED uptr AddrIsInFakeStack(uptr addr) {
134 uptr t1, t2;
135 return AddrIsInFakeStack(addr, frame_beg: &t1, frame_end: &t2);
136 }
137
138 // Number of bytes in a fake frame of this size class.
139 static uptr BytesInSizeClass(uptr class_id) {
140 return ((uptr)1) << (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.
146 static u8 **SavedFlagPtr(uptr x, uptr class_id) {
147 return reinterpret_cast<u8 **>(x + BytesInSizeClass(class_id) - sizeof(x));
148 }
149
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:
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 = ((uptr)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
170FakeStack *GetTLSFakeStack();
171void SetTLSFakeStack(FakeStack *fs);
172
173} // namespace __asan
174
175#endif // ASAN_FAKE_STACK_H
176