| //===-- guarded_pool_allocator.cpp ------------------------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "gwp_asan/guarded_pool_allocator.h" |
| |
| #include "gwp_asan/options.h" |
| #include "gwp_asan/utilities.h" |
| |
| #include <assert.h> |
| #include <stddef.h> |
| |
| using AllocationMetadata = gwp_asan::AllocationMetadata; |
| using Error = gwp_asan::Error; |
| |
| namespace gwp_asan { |
| namespace { |
| // Forward declare the pointer to the singleton version of this class. |
| // Instantiated during initialisation, this allows the signal handler |
| // to find this class in order to deduce the root cause of failures. Must not be |
| // referenced by users outside this translation unit, in order to avoid |
| // init-order-fiasco. |
| GuardedPoolAllocator *SingletonPtr = nullptr; |
| |
| size_t roundUpTo(size_t Size, size_t Boundary) { |
| return (Size + Boundary - 1) & ~(Boundary - 1); |
| } |
| |
| uintptr_t getPageAddr(uintptr_t Ptr, uintptr_t PageSize) { |
| return Ptr & ~(PageSize - 1); |
| } |
| |
| bool isPowerOfTwo(uintptr_t X) { return (X & (X - 1)) == 0; } |
| } // anonymous namespace |
| |
| // Gets the singleton implementation of this class. Thread-compatible until |
| // init() is called, thread-safe afterwards. |
| GuardedPoolAllocator *GuardedPoolAllocator::getSingleton() { |
| return SingletonPtr; |
| } |
| |
| void GuardedPoolAllocator::init(const options::Options &Opts) { |
| // Note: We return from the constructor here if GWP-ASan is not available. |
| // This will stop heap-allocation of class members, as well as mmap() of the |
| // guarded slots. |
| if (!Opts.Enabled || Opts.SampleRate == 0 || |
| Opts.MaxSimultaneousAllocations == 0) |
| return; |
| |
| Check(Opts.SampleRate >= 0, "GWP-ASan Error: SampleRate is < 0."); |
| Check(Opts.SampleRate < (1 << 30), "GWP-ASan Error: SampleRate is >= 2^30."); |
| Check(Opts.MaxSimultaneousAllocations >= 0, |
| "GWP-ASan Error: MaxSimultaneousAllocations is < 0."); |
| |
| SingletonPtr = this; |
| Backtrace = Opts.Backtrace; |
| |
| State.VersionMagic = {{AllocatorVersionMagic::kAllocatorVersionMagic[0], |
| AllocatorVersionMagic::kAllocatorVersionMagic[1], |
| AllocatorVersionMagic::kAllocatorVersionMagic[2], |
| AllocatorVersionMagic::kAllocatorVersionMagic[3]}, |
| AllocatorVersionMagic::kAllocatorVersion, |
| 0}; |
| |
| State.MaxSimultaneousAllocations = Opts.MaxSimultaneousAllocations; |
| |
| const size_t PageSize = getPlatformPageSize(); |
| // getPageAddr() and roundUpTo() assume the page size to be a power of 2. |
| assert((PageSize & (PageSize - 1)) == 0); |
| State.PageSize = PageSize; |
| |
| size_t PoolBytesRequired = |
| PageSize * (1 + State.MaxSimultaneousAllocations) + |
| State.MaxSimultaneousAllocations * State.maximumAllocationSize(); |
| assert(PoolBytesRequired % PageSize == 0); |
| void *GuardedPoolMemory = reserveGuardedPool(PoolBytesRequired); |
| |
| size_t BytesRequired = |
| roundUpTo(State.MaxSimultaneousAllocations * sizeof(*Metadata), PageSize); |
| Metadata = reinterpret_cast<AllocationMetadata *>( |
| map(BytesRequired, kGwpAsanMetadataName)); |
| |
| // Allocate memory and set up the free pages queue. |
| BytesRequired = roundUpTo( |
| State.MaxSimultaneousAllocations * sizeof(*FreeSlots), PageSize); |
| FreeSlots = |
| reinterpret_cast<size_t *>(map(BytesRequired, kGwpAsanFreeSlotsName)); |
| |
| // Multiply the sample rate by 2 to give a good, fast approximation for (1 / |
| // SampleRate) chance of sampling. |
| if (Opts.SampleRate != 1) |
| AdjustedSampleRatePlusOne = static_cast<uint32_t>(Opts.SampleRate) * 2 + 1; |
| else |
| AdjustedSampleRatePlusOne = 2; |
| |
| initPRNG(); |
| getThreadLocals()->NextSampleCounter = |
| ((getRandomUnsigned32() % (AdjustedSampleRatePlusOne - 1)) + 1) & |
| ThreadLocalPackedVariables::NextSampleCounterMask; |
| |
| State.GuardedPagePool = reinterpret_cast<uintptr_t>(GuardedPoolMemory); |
| State.GuardedPagePoolEnd = |
| reinterpret_cast<uintptr_t>(GuardedPoolMemory) + PoolBytesRequired; |
| |
| if (Opts.InstallForkHandlers) |
| installAtFork(); |
| } |
| |
| void GuardedPoolAllocator::disable() { |
| PoolMutex.lock(); |
| BacktraceMutex.lock(); |
| } |
| |
| void GuardedPoolAllocator::enable() { |
| PoolMutex.unlock(); |
| BacktraceMutex.unlock(); |
| } |
| |
| void GuardedPoolAllocator::iterate(void *Base, size_t Size, iterate_callback Cb, |
| void *Arg) { |
| uintptr_t Start = reinterpret_cast<uintptr_t>(Base); |
| for (size_t i = 0; i < State.MaxSimultaneousAllocations; ++i) { |
| const AllocationMetadata &Meta = Metadata[i]; |
| if (Meta.Addr && !Meta.IsDeallocated && Meta.Addr >= Start && |
| Meta.Addr < Start + Size) |
| Cb(Meta.Addr, Meta.RequestedSize, Arg); |
| } |
| } |
| |
| void GuardedPoolAllocator::uninitTestOnly() { |
| if (State.GuardedPagePool) { |
| unreserveGuardedPool(); |
| State.GuardedPagePool = 0; |
| State.GuardedPagePoolEnd = 0; |
| } |
| if (Metadata) { |
| unmap(Metadata, |
| roundUpTo(State.MaxSimultaneousAllocations * sizeof(*Metadata), |
| State.PageSize)); |
| Metadata = nullptr; |
| } |
| if (FreeSlots) { |
| unmap(FreeSlots, |
| roundUpTo(State.MaxSimultaneousAllocations * sizeof(*FreeSlots), |
| State.PageSize)); |
| FreeSlots = nullptr; |
| } |
| *getThreadLocals() = ThreadLocalPackedVariables(); |
| } |
| |
| // Note, minimum backing allocation size in GWP-ASan is always one page, and |
| // each slot could potentially be multiple pages (but always in |
| // page-increments). Thus, for anything that requires less than page size |
| // alignment, we don't need to allocate extra padding to ensure the alignment |
| // can be met. |
| size_t GuardedPoolAllocator::getRequiredBackingSize(size_t Size, |
| size_t Alignment, |
| size_t PageSize) { |
| assert(isPowerOfTwo(Alignment) && "Alignment must be a power of two!"); |
| assert(Alignment != 0 && "Alignment should be non-zero"); |
| assert(Size != 0 && "Size should be non-zero"); |
| |
| if (Alignment <= PageSize) |
| return Size; |
| |
| return Size + Alignment - PageSize; |
| } |
| |
| uintptr_t GuardedPoolAllocator::alignUp(uintptr_t Ptr, size_t Alignment) { |
| assert(isPowerOfTwo(Alignment) && "Alignment must be a power of two!"); |
| assert(Alignment != 0 && "Alignment should be non-zero"); |
| if ((Ptr & (Alignment - 1)) == 0) |
| return Ptr; |
| |
| Ptr += Alignment - (Ptr & (Alignment - 1)); |
| return Ptr; |
| } |
| |
| uintptr_t GuardedPoolAllocator::alignDown(uintptr_t Ptr, size_t Alignment) { |
| assert(isPowerOfTwo(Alignment) && "Alignment must be a power of two!"); |
| assert(Alignment != 0 && "Alignment should be non-zero"); |
| if ((Ptr & (Alignment - 1)) == 0) |
| return Ptr; |
| |
| Ptr -= Ptr & (Alignment - 1); |
| return Ptr; |
| } |
| |
| void *GuardedPoolAllocator::allocate(size_t Size, size_t Alignment) { |
| // GuardedPagePoolEnd == 0 when GWP-ASan is disabled. If we are disabled, fall |
| // back to the supporting allocator. |
| if (State.GuardedPagePoolEnd == 0) { |
| getThreadLocals()->NextSampleCounter = |
| (AdjustedSampleRatePlusOne - 1) & |
| ThreadLocalPackedVariables::NextSampleCounterMask; |
| return nullptr; |
| } |
| |
| if (Size == 0) |
| Size = 1; |
| if (Alignment == 0) |
| Alignment = alignof(max_align_t); |
| |
| if (!isPowerOfTwo(Alignment) || Alignment > State.maximumAllocationSize() || |
| Size > State.maximumAllocationSize()) |
| return nullptr; |
| |
| size_t BackingSize = getRequiredBackingSize(Size, Alignment, State.PageSize); |
| if (BackingSize > State.maximumAllocationSize()) |
| return nullptr; |
| |
| // Protect against recursivity. |
| if (getThreadLocals()->RecursiveGuard) |
| return nullptr; |
| ScopedRecursiveGuard SRG; |
| |
| size_t Index; |
| { |
| ScopedLock L(PoolMutex); |
| Index = reserveSlot(); |
| } |
| |
| if (Index == kInvalidSlotID) |
| return nullptr; |
| |
| uintptr_t SlotStart = State.slotToAddr(Index); |
| AllocationMetadata *Meta = addrToMetadata(SlotStart); |
| uintptr_t SlotEnd = State.slotToAddr(Index) + State.maximumAllocationSize(); |
| uintptr_t UserPtr; |
| // Randomly choose whether to left-align or right-align the allocation, and |
| // then apply the necessary adjustments to get an aligned pointer. |
| if (getRandomUnsigned32() % 2 == 0) |
| UserPtr = alignUp(SlotStart, Alignment); |
| else |
| UserPtr = alignDown(SlotEnd - Size, Alignment); |
| |
| assert(UserPtr >= SlotStart); |
| assert(UserPtr + Size <= SlotEnd); |
| |
| // If a slot is multiple pages in size, and the allocation takes up a single |
| // page, we can improve overflow detection by leaving the unused pages as |
| // unmapped. |
| const size_t PageSize = State.PageSize; |
| allocateInGuardedPool( |
| reinterpret_cast<void *>(getPageAddr(UserPtr, PageSize)), |
| roundUpTo(Size, PageSize)); |
| |
| Meta->RecordAllocation(UserPtr, Size); |
| { |
| ScopedLock UL(BacktraceMutex); |
| Meta->AllocationTrace.RecordBacktrace(Backtrace); |
| } |
| |
| return reinterpret_cast<void *>(UserPtr); |
| } |
| |
| void GuardedPoolAllocator::trapOnAddress(uintptr_t Address, Error E) { |
| State.FailureType = E; |
| State.FailureAddress = Address; |
| |
| // Raise a SEGV by touching first guard page. |
| volatile char *p = reinterpret_cast<char *>(State.GuardedPagePool); |
| *p = 0; |
| // Normally, would be __builtin_unreachable(), but because of |
| // https://bugs.llvm.org/show_bug.cgi?id=47480, unreachable will DCE the |
| // volatile store above, even though it has side effects. |
| __builtin_trap(); |
| } |
| |
| void GuardedPoolAllocator::stop() { |
| getThreadLocals()->RecursiveGuard = true; |
| PoolMutex.tryLock(); |
| } |
| |
| void GuardedPoolAllocator::deallocate(void *Ptr) { |
| assert(pointerIsMine(Ptr) && "Pointer is not mine!"); |
| uintptr_t UPtr = reinterpret_cast<uintptr_t>(Ptr); |
| size_t Slot = State.getNearestSlot(UPtr); |
| uintptr_t SlotStart = State.slotToAddr(Slot); |
| AllocationMetadata *Meta = addrToMetadata(UPtr); |
| if (Meta->Addr != UPtr) { |
| // If multiple errors occur at the same time, use the first one. |
| ScopedLock L(PoolMutex); |
| trapOnAddress(UPtr, Error::INVALID_FREE); |
| } |
| |
| // Intentionally scope the mutex here, so that other threads can access the |
| // pool during the expensive markInaccessible() call. |
| { |
| ScopedLock L(PoolMutex); |
| if (Meta->IsDeallocated) { |
| trapOnAddress(UPtr, Error::DOUBLE_FREE); |
| } |
| |
| // Ensure that the deallocation is recorded before marking the page as |
| // inaccessible. Otherwise, a racy use-after-free will have inconsistent |
| // metadata. |
| Meta->RecordDeallocation(); |
| |
| // Ensure that the unwinder is not called if the recursive flag is set, |
| // otherwise non-reentrant unwinders may deadlock. |
| if (!getThreadLocals()->RecursiveGuard) { |
| ScopedRecursiveGuard SRG; |
| ScopedLock UL(BacktraceMutex); |
| Meta->DeallocationTrace.RecordBacktrace(Backtrace); |
| } |
| } |
| |
| deallocateInGuardedPool(reinterpret_cast<void *>(SlotStart), |
| State.maximumAllocationSize()); |
| |
| // And finally, lock again to release the slot back into the pool. |
| ScopedLock L(PoolMutex); |
| freeSlot(Slot); |
| } |
| |
| size_t GuardedPoolAllocator::getSize(const void *Ptr) { |
| assert(pointerIsMine(Ptr)); |
| ScopedLock L(PoolMutex); |
| AllocationMetadata *Meta = addrToMetadata(reinterpret_cast<uintptr_t>(Ptr)); |
| assert(Meta->Addr == reinterpret_cast<uintptr_t>(Ptr)); |
| return Meta->RequestedSize; |
| } |
| |
| AllocationMetadata *GuardedPoolAllocator::addrToMetadata(uintptr_t Ptr) const { |
| return &Metadata[State.getNearestSlot(Ptr)]; |
| } |
| |
| size_t GuardedPoolAllocator::reserveSlot() { |
| // Avoid potential reuse of a slot before we have made at least a single |
| // allocation in each slot. Helps with our use-after-free detection. |
| if (NumSampledAllocations < State.MaxSimultaneousAllocations) |
| return NumSampledAllocations++; |
| |
| if (FreeSlotsLength == 0) |
| return kInvalidSlotID; |
| |
| size_t ReservedIndex = getRandomUnsigned32() % FreeSlotsLength; |
| size_t SlotIndex = FreeSlots[ReservedIndex]; |
| FreeSlots[ReservedIndex] = FreeSlots[--FreeSlotsLength]; |
| return SlotIndex; |
| } |
| |
| void GuardedPoolAllocator::freeSlot(size_t SlotIndex) { |
| assert(FreeSlotsLength < State.MaxSimultaneousAllocations); |
| FreeSlots[FreeSlotsLength++] = SlotIndex; |
| } |
| |
| uint32_t GuardedPoolAllocator::getRandomUnsigned32() { |
| uint32_t RandomState = getThreadLocals()->RandomState; |
| RandomState ^= RandomState << 13; |
| RandomState ^= RandomState >> 17; |
| RandomState ^= RandomState << 5; |
| getThreadLocals()->RandomState = RandomState; |
| return RandomState; |
| } |
| } // namespace gwp_asan |