1351282Sdim//===-- guarded_pool_allocator.h --------------------------------*- C++ -*-===// 2351282Sdim// 3351282Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351282Sdim// See https://llvm.org/LICENSE.txt for license information. 5351282Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351282Sdim// 7351282Sdim//===----------------------------------------------------------------------===// 8351282Sdim 9351282Sdim#ifndef GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_ 10351282Sdim#define GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_ 11351282Sdim 12351282Sdim#include "gwp_asan/definitions.h" 13351282Sdim#include "gwp_asan/mutex.h" 14351282Sdim#include "gwp_asan/options.h" 15351282Sdim#include "gwp_asan/random.h" 16360784Sdim#include "gwp_asan/stack_trace_compressor.h" 17351282Sdim 18351282Sdim#include <stddef.h> 19351282Sdim#include <stdint.h> 20351282Sdim 21351282Sdimnamespace gwp_asan { 22351282Sdim// This class is the primary implementation of the allocator portion of GWP- 23351282Sdim// ASan. It is the sole owner of the pool of sequentially allocated guarded 24351282Sdim// slots. It should always be treated as a singleton. 25351282Sdim 26351282Sdim// Functions in the public interface of this class are thread-compatible until 27351282Sdim// init() is called, at which point they become thread-safe (unless specified 28351282Sdim// otherwise). 29351282Sdimclass GuardedPoolAllocator { 30351282Sdimpublic: 31351282Sdim static constexpr uint64_t kInvalidThreadID = UINT64_MAX; 32351282Sdim 33351282Sdim enum class Error { 34351282Sdim UNKNOWN, 35351282Sdim USE_AFTER_FREE, 36351282Sdim DOUBLE_FREE, 37351282Sdim INVALID_FREE, 38351282Sdim BUFFER_OVERFLOW, 39351282Sdim BUFFER_UNDERFLOW 40351282Sdim }; 41351282Sdim 42351282Sdim struct AllocationMetadata { 43360784Sdim // The number of bytes used to store a compressed stack frame. On 64-bit 44360784Sdim // platforms, assuming a compression ratio of 50%, this should allow us to 45360784Sdim // store ~64 frames per trace. 46360784Sdim static constexpr size_t kStackFrameStorageBytes = 256; 47351282Sdim 48360784Sdim // Maximum number of stack frames to collect on allocation/deallocation. The 49360784Sdim // actual number of collected frames may be less than this as the stack 50360784Sdim // frames are compressed into a fixed memory range. 51360784Sdim static constexpr size_t kMaxTraceLengthToCollect = 128; 52360784Sdim 53351282Sdim // Records the given allocation metadata into this struct. 54351282Sdim void RecordAllocation(uintptr_t Addr, size_t Size, 55351282Sdim options::Backtrace_t Backtrace); 56351282Sdim 57351282Sdim // Record that this allocation is now deallocated. 58351282Sdim void RecordDeallocation(options::Backtrace_t Backtrace); 59351282Sdim 60351282Sdim struct CallSiteInfo { 61360784Sdim // The compressed backtrace to the allocation/deallocation. 62360784Sdim uint8_t CompressedTrace[kStackFrameStorageBytes]; 63351282Sdim // The thread ID for this trace, or kInvalidThreadID if not available. 64351282Sdim uint64_t ThreadID = kInvalidThreadID; 65360784Sdim // The size of the compressed trace (in bytes). Zero indicates that no 66360784Sdim // trace was collected. 67360784Sdim size_t TraceSize = 0; 68351282Sdim }; 69351282Sdim 70351282Sdim // The address of this allocation. 71351282Sdim uintptr_t Addr = 0; 72351282Sdim // Represents the actual size of the allocation. 73351282Sdim size_t Size = 0; 74351282Sdim 75351282Sdim CallSiteInfo AllocationTrace; 76351282Sdim CallSiteInfo DeallocationTrace; 77351282Sdim 78351282Sdim // Whether this allocation has been deallocated yet. 79351282Sdim bool IsDeallocated = false; 80351282Sdim }; 81351282Sdim 82351282Sdim // During program startup, we must ensure that memory allocations do not land 83351282Sdim // in this allocation pool if the allocator decides to runtime-disable 84351282Sdim // GWP-ASan. The constructor value-initialises the class such that if no 85351282Sdim // further initialisation takes place, calls to shouldSample() and 86351282Sdim // pointerIsMine() will return false. 87351282Sdim constexpr GuardedPoolAllocator(){}; 88351282Sdim GuardedPoolAllocator(const GuardedPoolAllocator &) = delete; 89351282Sdim GuardedPoolAllocator &operator=(const GuardedPoolAllocator &) = delete; 90351282Sdim 91351282Sdim // Note: This class is expected to be a singleton for the lifetime of the 92351282Sdim // program. If this object is initialised, it will leak the guarded page pool 93351282Sdim // and metadata allocations during destruction. We can't clean up these areas 94351282Sdim // as this may cause a use-after-free on shutdown. 95351282Sdim ~GuardedPoolAllocator() = default; 96351282Sdim 97351282Sdim // Initialise the rest of the members of this class. Create the allocation 98351282Sdim // pool using the provided options. See options.inc for runtime configuration 99351282Sdim // options. 100351282Sdim void init(const options::Options &Opts); 101351282Sdim 102351282Sdim // Return whether the allocation should be randomly chosen for sampling. 103360784Sdim GWP_ASAN_ALWAYS_INLINE bool shouldSample() { 104351282Sdim // NextSampleCounter == 0 means we "should regenerate the counter". 105351282Sdim // == 1 means we "should sample this allocation". 106360784Sdim if (GWP_ASAN_UNLIKELY(ThreadLocals.NextSampleCounter == 0)) 107351282Sdim ThreadLocals.NextSampleCounter = 108351282Sdim (getRandomUnsigned32() % AdjustedSampleRate) + 1; 109351282Sdim 110360784Sdim return GWP_ASAN_UNLIKELY(--ThreadLocals.NextSampleCounter == 0); 111351282Sdim } 112351282Sdim 113351282Sdim // Returns whether the provided pointer is a current sampled allocation that 114351282Sdim // is owned by this pool. 115360784Sdim GWP_ASAN_ALWAYS_INLINE bool pointerIsMine(const void *Ptr) const { 116351282Sdim uintptr_t P = reinterpret_cast<uintptr_t>(Ptr); 117351282Sdim return GuardedPagePool <= P && P < GuardedPagePoolEnd; 118351282Sdim } 119351282Sdim 120351282Sdim // Allocate memory in a guarded slot, and return a pointer to the new 121351282Sdim // allocation. Returns nullptr if the pool is empty, the requested size is too 122351282Sdim // large for this pool to handle, or the requested size is zero. 123351282Sdim void *allocate(size_t Size); 124351282Sdim 125351282Sdim // Deallocate memory in a guarded slot. The provided pointer must have been 126351282Sdim // allocated using this pool. This will set the guarded slot as inaccessible. 127351282Sdim void deallocate(void *Ptr); 128351282Sdim 129351282Sdim // Returns the size of the allocation at Ptr. 130351282Sdim size_t getSize(const void *Ptr); 131351282Sdim 132351282Sdim // Returns the largest allocation that is supported by this pool. Any 133351282Sdim // allocations larger than this should go to the regular system allocator. 134351282Sdim size_t maximumAllocationSize() const; 135351282Sdim 136351282Sdim // Dumps an error report (including allocation and deallocation stack traces). 137351282Sdim // An optional error may be provided if the caller knows what the error is 138351282Sdim // ahead of time. This is primarily a helper function to locate the static 139351282Sdim // singleton pointer and call the internal version of this function. This 140351282Sdim // method is never thread safe, and should only be called when fatal errors 141351282Sdim // occur. 142351282Sdim static void reportError(uintptr_t AccessPtr, Error E = Error::UNKNOWN); 143351282Sdim 144351282Sdim // Get the current thread ID, or kInvalidThreadID if failure. Note: This 145351282Sdim // implementation is platform-specific. 146351282Sdim static uint64_t getThreadID(); 147351282Sdim 148351282Sdimprivate: 149351282Sdim static constexpr size_t kInvalidSlotID = SIZE_MAX; 150351282Sdim 151351282Sdim // These functions anonymously map memory or change the permissions of mapped 152351282Sdim // memory into this process in a platform-specific way. Pointer and size 153351282Sdim // arguments are expected to be page-aligned. These functions will never 154351282Sdim // return on error, instead electing to kill the calling process on failure. 155351282Sdim // Note that memory is initially mapped inaccessible. In order for RW 156351282Sdim // mappings, call mapMemory() followed by markReadWrite() on the returned 157351282Sdim // pointer. 158351282Sdim void *mapMemory(size_t Size) const; 159351282Sdim void markReadWrite(void *Ptr, size_t Size) const; 160351282Sdim void markInaccessible(void *Ptr, size_t Size) const; 161351282Sdim 162351282Sdim // Get the page size from the platform-specific implementation. Only needs to 163351282Sdim // be called once, and the result should be cached in PageSize in this class. 164351282Sdim static size_t getPlatformPageSize(); 165351282Sdim 166351282Sdim // Install the SIGSEGV crash handler for printing use-after-free and heap- 167351282Sdim // buffer-{under|over}flow exceptions. This is platform specific as even 168351282Sdim // though POSIX and Windows both support registering handlers through 169351282Sdim // signal(), we have to use platform-specific signal handlers to obtain the 170351282Sdim // address that caused the SIGSEGV exception. 171351282Sdim static void installSignalHandlers(); 172351282Sdim 173351282Sdim // Returns the index of the slot that this pointer resides in. If the pointer 174351282Sdim // is not owned by this pool, the result is undefined. 175351282Sdim size_t addrToSlot(uintptr_t Ptr) const; 176351282Sdim 177351282Sdim // Returns the address of the N-th guarded slot. 178351282Sdim uintptr_t slotToAddr(size_t N) const; 179351282Sdim 180351282Sdim // Returns a pointer to the metadata for the owned pointer. If the pointer is 181351282Sdim // not owned by this pool, the result is undefined. 182351282Sdim AllocationMetadata *addrToMetadata(uintptr_t Ptr) const; 183351282Sdim 184351282Sdim // Returns the address of the page that this pointer resides in. 185351282Sdim uintptr_t getPageAddr(uintptr_t Ptr) const; 186351282Sdim 187351282Sdim // Gets the nearest slot to the provided address. 188351282Sdim size_t getNearestSlot(uintptr_t Ptr) const; 189351282Sdim 190351282Sdim // Returns whether the provided pointer is a guard page or not. The pointer 191351282Sdim // must be within memory owned by this pool, else the result is undefined. 192351282Sdim bool isGuardPage(uintptr_t Ptr) const; 193351282Sdim 194351282Sdim // Reserve a slot for a new guarded allocation. Returns kInvalidSlotID if no 195351282Sdim // slot is available to be reserved. 196351282Sdim size_t reserveSlot(); 197351282Sdim 198351282Sdim // Unreserve the guarded slot. 199351282Sdim void freeSlot(size_t SlotIndex); 200351282Sdim 201351282Sdim // Returns the offset (in bytes) between the start of a guarded slot and where 202351282Sdim // the start of the allocation should take place. Determined using the size of 203351282Sdim // the allocation and the options provided at init-time. 204351282Sdim uintptr_t allocationSlotOffset(size_t AllocationSize) const; 205351282Sdim 206351282Sdim // Returns the diagnosis for an unknown error. If the diagnosis is not 207351282Sdim // Error::INVALID_FREE or Error::UNKNOWN, the metadata for the slot 208351282Sdim // responsible for the error is placed in *Meta. 209351282Sdim Error diagnoseUnknownError(uintptr_t AccessPtr, AllocationMetadata **Meta); 210351282Sdim 211351282Sdim void reportErrorInternal(uintptr_t AccessPtr, Error E); 212351282Sdim 213351282Sdim // Cached page size for this system in bytes. 214351282Sdim size_t PageSize = 0; 215351282Sdim 216351282Sdim // A mutex to protect the guarded slot and metadata pool for this class. 217351282Sdim Mutex PoolMutex; 218351282Sdim // The number of guarded slots that this pool holds. 219351282Sdim size_t MaxSimultaneousAllocations = 0; 220351282Sdim // Record the number allocations that we've sampled. We store this amount so 221351282Sdim // that we don't randomly choose to recycle a slot that previously had an 222351282Sdim // allocation before all the slots have been utilised. 223351282Sdim size_t NumSampledAllocations = 0; 224351282Sdim // Pointer to the pool of guarded slots. Note that this points to the start of 225351282Sdim // the pool (which is a guard page), not a pointer to the first guarded page. 226351282Sdim uintptr_t GuardedPagePool = UINTPTR_MAX; 227351282Sdim uintptr_t GuardedPagePoolEnd = 0; 228351282Sdim // Pointer to the allocation metadata (allocation/deallocation stack traces), 229351282Sdim // if any. 230351282Sdim AllocationMetadata *Metadata = nullptr; 231351282Sdim 232351282Sdim // Pointer to an array of free slot indexes. 233351282Sdim size_t *FreeSlots = nullptr; 234351282Sdim // The current length of the list of free slots. 235351282Sdim size_t FreeSlotsLength = 0; 236351282Sdim 237351282Sdim // See options.{h, inc} for more information. 238351282Sdim bool PerfectlyRightAlign = false; 239351282Sdim 240351282Sdim // Printf function supplied by the implementing allocator. We can't (in 241351282Sdim // general) use printf() from the cstdlib as it may malloc(), causing infinite 242351282Sdim // recursion. 243351282Sdim options::Printf_t Printf = nullptr; 244351282Sdim options::Backtrace_t Backtrace = nullptr; 245351282Sdim options::PrintBacktrace_t PrintBacktrace = nullptr; 246351282Sdim 247351282Sdim // The adjusted sample rate for allocation sampling. Default *must* be 248351282Sdim // nonzero, as dynamic initialisation may call malloc (e.g. from libstdc++) 249351282Sdim // before GPA::init() is called. This would cause an error in shouldSample(), 250351282Sdim // where we would calculate modulo zero. This value is set UINT32_MAX, as when 251351282Sdim // GWP-ASan is disabled, we wish to never spend wasted cycles recalculating 252351282Sdim // the sample rate. 253351282Sdim uint32_t AdjustedSampleRate = UINT32_MAX; 254351282Sdim 255351282Sdim // Pack the thread local variables into a struct to ensure that they're in 256351282Sdim // the same cache line for performance reasons. These are the most touched 257351282Sdim // variables in GWP-ASan. 258351282Sdim struct alignas(8) ThreadLocalPackedVariables { 259351282Sdim constexpr ThreadLocalPackedVariables() {} 260351282Sdim // Thread-local decrementing counter that indicates that a given allocation 261351282Sdim // should be sampled when it reaches zero. 262351282Sdim uint32_t NextSampleCounter = 0; 263351282Sdim // Guard against recursivity. Unwinders often contain complex behaviour that 264351282Sdim // may not be safe for the allocator (i.e. the unwinder calls dlopen(), 265351282Sdim // which calls malloc()). When recursive behaviour is detected, we will 266351282Sdim // automatically fall back to the supporting allocator to supply the 267351282Sdim // allocation. 268351282Sdim bool RecursiveGuard = false; 269351282Sdim }; 270360784Sdim static GWP_ASAN_TLS_INITIAL_EXEC ThreadLocalPackedVariables ThreadLocals; 271351282Sdim}; 272351282Sdim} // namespace gwp_asan 273351282Sdim 274351282Sdim#endif // GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_ 275