1 //===-- guarded_pool_allocator.h --------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 #ifndef GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_
10 #define GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_
12 #include "gwp_asan/definitions.h"
13 #include "gwp_asan/mutex.h"
14 #include "gwp_asan/options.h"
15 #include "gwp_asan/random.h"
16 #include "gwp_asan/stack_trace_compressor.h"
22 // This class is the primary implementation of the allocator portion of GWP-
23 // ASan. It is the sole owner of the pool of sequentially allocated guarded
24 // slots. It should always be treated as a singleton.
26 // Functions in the public interface of this class are thread-compatible until
27 // init() is called, at which point they become thread-safe (unless specified
29 class GuardedPoolAllocator {
31 static constexpr uint64_t kInvalidThreadID = UINT64_MAX;
42 struct AllocationMetadata {
43 // The number of bytes used to store a compressed stack frame. On 64-bit
44 // platforms, assuming a compression ratio of 50%, this should allow us to
45 // store ~64 frames per trace.
46 static constexpr size_t kStackFrameStorageBytes = 256;
48 // Maximum number of stack frames to collect on allocation/deallocation. The
49 // actual number of collected frames may be less than this as the stack
50 // frames are compressed into a fixed memory range.
51 static constexpr size_t kMaxTraceLengthToCollect = 128;
53 // Records the given allocation metadata into this struct.
54 void RecordAllocation(uintptr_t Addr, size_t Size,
55 options::Backtrace_t Backtrace);
57 // Record that this allocation is now deallocated.
58 void RecordDeallocation(options::Backtrace_t Backtrace);
61 // The compressed backtrace to the allocation/deallocation.
62 uint8_t CompressedTrace[kStackFrameStorageBytes];
63 // The thread ID for this trace, or kInvalidThreadID if not available.
64 uint64_t ThreadID = kInvalidThreadID;
65 // The size of the compressed trace (in bytes). Zero indicates that no
66 // trace was collected.
70 // The address of this allocation.
72 // Represents the actual size of the allocation.
75 CallSiteInfo AllocationTrace;
76 CallSiteInfo DeallocationTrace;
78 // Whether this allocation has been deallocated yet.
79 bool IsDeallocated = false;
82 // During program startup, we must ensure that memory allocations do not land
83 // in this allocation pool if the allocator decides to runtime-disable
84 // GWP-ASan. The constructor value-initialises the class such that if no
85 // further initialisation takes place, calls to shouldSample() and
86 // pointerIsMine() will return false.
87 constexpr GuardedPoolAllocator(){};
88 GuardedPoolAllocator(const GuardedPoolAllocator &) = delete;
89 GuardedPoolAllocator &operator=(const GuardedPoolAllocator &) = delete;
91 // Note: This class is expected to be a singleton for the lifetime of the
92 // program. If this object is initialised, it will leak the guarded page pool
93 // and metadata allocations during destruction. We can't clean up these areas
94 // as this may cause a use-after-free on shutdown.
95 ~GuardedPoolAllocator() = default;
97 // Initialise the rest of the members of this class. Create the allocation
98 // pool using the provided options. See options.inc for runtime configuration
100 void init(const options::Options &Opts);
102 // Return whether the allocation should be randomly chosen for sampling.
103 GWP_ASAN_ALWAYS_INLINE bool shouldSample() {
104 // NextSampleCounter == 0 means we "should regenerate the counter".
105 // == 1 means we "should sample this allocation".
106 if (GWP_ASAN_UNLIKELY(ThreadLocals.NextSampleCounter == 0))
107 ThreadLocals.NextSampleCounter =
108 (getRandomUnsigned32() % AdjustedSampleRate) + 1;
110 return GWP_ASAN_UNLIKELY(--ThreadLocals.NextSampleCounter == 0);
113 // Returns whether the provided pointer is a current sampled allocation that
114 // is owned by this pool.
115 GWP_ASAN_ALWAYS_INLINE bool pointerIsMine(const void *Ptr) const {
116 uintptr_t P = reinterpret_cast<uintptr_t>(Ptr);
117 return GuardedPagePool <= P && P < GuardedPagePoolEnd;
120 // Allocate memory in a guarded slot, and return a pointer to the new
121 // allocation. Returns nullptr if the pool is empty, the requested size is too
122 // large for this pool to handle, or the requested size is zero.
123 void *allocate(size_t Size);
125 // Deallocate memory in a guarded slot. The provided pointer must have been
126 // allocated using this pool. This will set the guarded slot as inaccessible.
127 void deallocate(void *Ptr);
129 // Returns the size of the allocation at Ptr.
130 size_t getSize(const void *Ptr);
132 // Returns the largest allocation that is supported by this pool. Any
133 // allocations larger than this should go to the regular system allocator.
134 size_t maximumAllocationSize() const;
136 // Dumps an error report (including allocation and deallocation stack traces).
137 // An optional error may be provided if the caller knows what the error is
138 // ahead of time. This is primarily a helper function to locate the static
139 // singleton pointer and call the internal version of this function. This
140 // method is never thread safe, and should only be called when fatal errors
142 static void reportError(uintptr_t AccessPtr, Error E = Error::UNKNOWN);
144 // Get the current thread ID, or kInvalidThreadID if failure. Note: This
145 // implementation is platform-specific.
146 static uint64_t getThreadID();
149 static constexpr size_t kInvalidSlotID = SIZE_MAX;
151 // These functions anonymously map memory or change the permissions of mapped
152 // memory into this process in a platform-specific way. Pointer and size
153 // arguments are expected to be page-aligned. These functions will never
154 // return on error, instead electing to kill the calling process on failure.
155 // Note that memory is initially mapped inaccessible. In order for RW
156 // mappings, call mapMemory() followed by markReadWrite() on the returned
158 void *mapMemory(size_t Size) const;
159 void markReadWrite(void *Ptr, size_t Size) const;
160 void markInaccessible(void *Ptr, size_t Size) const;
162 // Get the page size from the platform-specific implementation. Only needs to
163 // be called once, and the result should be cached in PageSize in this class.
164 static size_t getPlatformPageSize();
166 // Install the SIGSEGV crash handler for printing use-after-free and heap-
167 // buffer-{under|over}flow exceptions. This is platform specific as even
168 // though POSIX and Windows both support registering handlers through
169 // signal(), we have to use platform-specific signal handlers to obtain the
170 // address that caused the SIGSEGV exception.
171 static void installSignalHandlers();
173 // Returns the index of the slot that this pointer resides in. If the pointer
174 // is not owned by this pool, the result is undefined.
175 size_t addrToSlot(uintptr_t Ptr) const;
177 // Returns the address of the N-th guarded slot.
178 uintptr_t slotToAddr(size_t N) const;
180 // Returns a pointer to the metadata for the owned pointer. If the pointer is
181 // not owned by this pool, the result is undefined.
182 AllocationMetadata *addrToMetadata(uintptr_t Ptr) const;
184 // Returns the address of the page that this pointer resides in.
185 uintptr_t getPageAddr(uintptr_t Ptr) const;
187 // Gets the nearest slot to the provided address.
188 size_t getNearestSlot(uintptr_t Ptr) const;
190 // Returns whether the provided pointer is a guard page or not. The pointer
191 // must be within memory owned by this pool, else the result is undefined.
192 bool isGuardPage(uintptr_t Ptr) const;
194 // Reserve a slot for a new guarded allocation. Returns kInvalidSlotID if no
195 // slot is available to be reserved.
196 size_t reserveSlot();
198 // Unreserve the guarded slot.
199 void freeSlot(size_t SlotIndex);
201 // Returns the offset (in bytes) between the start of a guarded slot and where
202 // the start of the allocation should take place. Determined using the size of
203 // the allocation and the options provided at init-time.
204 uintptr_t allocationSlotOffset(size_t AllocationSize) const;
206 // Returns the diagnosis for an unknown error. If the diagnosis is not
207 // Error::INVALID_FREE or Error::UNKNOWN, the metadata for the slot
208 // responsible for the error is placed in *Meta.
209 Error diagnoseUnknownError(uintptr_t AccessPtr, AllocationMetadata **Meta);
211 void reportErrorInternal(uintptr_t AccessPtr, Error E);
213 // Cached page size for this system in bytes.
216 // A mutex to protect the guarded slot and metadata pool for this class.
218 // The number of guarded slots that this pool holds.
219 size_t MaxSimultaneousAllocations = 0;
220 // Record the number allocations that we've sampled. We store this amount so
221 // that we don't randomly choose to recycle a slot that previously had an
222 // allocation before all the slots have been utilised.
223 size_t NumSampledAllocations = 0;
224 // Pointer to the pool of guarded slots. Note that this points to the start of
225 // the pool (which is a guard page), not a pointer to the first guarded page.
226 uintptr_t GuardedPagePool = UINTPTR_MAX;
227 uintptr_t GuardedPagePoolEnd = 0;
228 // Pointer to the allocation metadata (allocation/deallocation stack traces),
230 AllocationMetadata *Metadata = nullptr;
232 // Pointer to an array of free slot indexes.
233 size_t *FreeSlots = nullptr;
234 // The current length of the list of free slots.
235 size_t FreeSlotsLength = 0;
237 // See options.{h, inc} for more information.
238 bool PerfectlyRightAlign = false;
240 // Printf function supplied by the implementing allocator. We can't (in
241 // general) use printf() from the cstdlib as it may malloc(), causing infinite
243 options::Printf_t Printf = nullptr;
244 options::Backtrace_t Backtrace = nullptr;
245 options::PrintBacktrace_t PrintBacktrace = nullptr;
247 // The adjusted sample rate for allocation sampling. Default *must* be
248 // nonzero, as dynamic initialisation may call malloc (e.g. from libstdc++)
249 // before GPA::init() is called. This would cause an error in shouldSample(),
250 // where we would calculate modulo zero. This value is set UINT32_MAX, as when
251 // GWP-ASan is disabled, we wish to never spend wasted cycles recalculating
253 uint32_t AdjustedSampleRate = UINT32_MAX;
255 // Pack the thread local variables into a struct to ensure that they're in
256 // the same cache line for performance reasons. These are the most touched
257 // variables in GWP-ASan.
258 struct alignas(8) ThreadLocalPackedVariables {
259 constexpr ThreadLocalPackedVariables() {}
260 // Thread-local decrementing counter that indicates that a given allocation
261 // should be sampled when it reaches zero.
262 uint32_t NextSampleCounter = 0;
263 // Guard against recursivity. Unwinders often contain complex behaviour that
264 // may not be safe for the allocator (i.e. the unwinder calls dlopen(),
265 // which calls malloc()). When recursive behaviour is detected, we will
266 // automatically fall back to the supporting allocator to supply the
268 bool RecursiveGuard = false;
270 static GWP_ASAN_TLS_INITIAL_EXEC ThreadLocalPackedVariables ThreadLocals;
272 } // namespace gwp_asan
274 #endif // GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_