1 //===-- guarded_pool_allocator.cpp ------------------------------*- 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 #include "gwp_asan/guarded_pool_allocator.h" 10 11 #include "gwp_asan/crash_handler.h" 12 #include "gwp_asan/options.h" 13 #include "gwp_asan/utilities.h" 14 15 #include <assert.h> 16 #include <stddef.h> 17 18 using AllocationMetadata = gwp_asan::AllocationMetadata; 19 using Error = gwp_asan::Error; 20 21 namespace gwp_asan { 22 namespace { 23 // Forward declare the pointer to the singleton version of this class. 24 // Instantiated during initialisation, this allows the signal handler 25 // to find this class in order to deduce the root cause of failures. Must not be 26 // referenced by users outside this translation unit, in order to avoid 27 // init-order-fiasco. 28 GuardedPoolAllocator *SingletonPtr = nullptr; 29 30 size_t roundUpTo(size_t Size, size_t Boundary) { 31 return (Size + Boundary - 1) & ~(Boundary - 1); 32 } 33 34 uintptr_t getPageAddr(uintptr_t Ptr, uintptr_t PageSize) { 35 return Ptr & ~(PageSize - 1); 36 } 37 38 bool isPowerOfTwo(uintptr_t X) { return (X & (X - 1)) == 0; } 39 } // anonymous namespace 40 41 // Gets the singleton implementation of this class. Thread-compatible until 42 // init() is called, thread-safe afterwards. 43 GuardedPoolAllocator *GuardedPoolAllocator::getSingleton() { 44 return SingletonPtr; 45 } 46 47 void GuardedPoolAllocator::init(const options::Options &Opts) { 48 // Note: We return from the constructor here if GWP-ASan is not available. 49 // This will stop heap-allocation of class members, as well as mmap() of the 50 // guarded slots. 51 if (!Opts.Enabled || Opts.SampleRate == 0 || 52 Opts.MaxSimultaneousAllocations == 0) 53 return; 54 55 Check(Opts.SampleRate >= 0, "GWP-ASan Error: SampleRate is < 0."); 56 Check(Opts.SampleRate < (1 << 30), "GWP-ASan Error: SampleRate is >= 2^30."); 57 Check(Opts.MaxSimultaneousAllocations >= 0, 58 "GWP-ASan Error: MaxSimultaneousAllocations is < 0."); 59 60 SingletonPtr = this; 61 Backtrace = Opts.Backtrace; 62 63 State.VersionMagic = {{AllocatorVersionMagic::kAllocatorVersionMagic[0], 64 AllocatorVersionMagic::kAllocatorVersionMagic[1], 65 AllocatorVersionMagic::kAllocatorVersionMagic[2], 66 AllocatorVersionMagic::kAllocatorVersionMagic[3]}, 67 AllocatorVersionMagic::kAllocatorVersion, 68 0}; 69 70 State.MaxSimultaneousAllocations = Opts.MaxSimultaneousAllocations; 71 72 const size_t PageSize = getPlatformPageSize(); 73 // getPageAddr() and roundUpTo() assume the page size to be a power of 2. 74 assert((PageSize & (PageSize - 1)) == 0); 75 State.PageSize = PageSize; 76 77 // Number of pages required = 78 // + MaxSimultaneousAllocations * maximumAllocationSize (N pages per slot) 79 // + MaxSimultaneousAllocations (one guard on the left side of each slot) 80 // + 1 (an extra guard page at the end of the pool, on the right side) 81 // + 1 (an extra page that's used for reporting internally-detected crashes, 82 // like double free and invalid free, to the signal handler; see 83 // raiseInternallyDetectedError() for more info) 84 size_t PoolBytesRequired = 85 PageSize * (2 + State.MaxSimultaneousAllocations) + 86 State.MaxSimultaneousAllocations * State.maximumAllocationSize(); 87 assert(PoolBytesRequired % PageSize == 0); 88 void *GuardedPoolMemory = reserveGuardedPool(PoolBytesRequired); 89 90 size_t BytesRequired = 91 roundUpTo(State.MaxSimultaneousAllocations * sizeof(*Metadata), PageSize); 92 Metadata = reinterpret_cast<AllocationMetadata *>( 93 map(BytesRequired, kGwpAsanMetadataName)); 94 95 // Allocate memory and set up the free pages queue. 96 BytesRequired = roundUpTo( 97 State.MaxSimultaneousAllocations * sizeof(*FreeSlots), PageSize); 98 FreeSlots = 99 reinterpret_cast<size_t *>(map(BytesRequired, kGwpAsanFreeSlotsName)); 100 101 // Multiply the sample rate by 2 to give a good, fast approximation for (1 / 102 // SampleRate) chance of sampling. 103 if (Opts.SampleRate != 1) 104 AdjustedSampleRatePlusOne = static_cast<uint32_t>(Opts.SampleRate) * 2 + 1; 105 else 106 AdjustedSampleRatePlusOne = 2; 107 108 initPRNG(); 109 getThreadLocals()->NextSampleCounter = 110 ((getRandomUnsigned32() % (AdjustedSampleRatePlusOne - 1)) + 1) & 111 ThreadLocalPackedVariables::NextSampleCounterMask; 112 113 State.GuardedPagePool = reinterpret_cast<uintptr_t>(GuardedPoolMemory); 114 State.GuardedPagePoolEnd = 115 reinterpret_cast<uintptr_t>(GuardedPoolMemory) + PoolBytesRequired; 116 117 if (Opts.InstallForkHandlers) 118 installAtFork(); 119 } 120 121 void GuardedPoolAllocator::disable() { 122 PoolMutex.lock(); 123 BacktraceMutex.lock(); 124 } 125 126 void GuardedPoolAllocator::enable() { 127 PoolMutex.unlock(); 128 BacktraceMutex.unlock(); 129 } 130 131 void GuardedPoolAllocator::iterate(void *Base, size_t Size, iterate_callback Cb, 132 void *Arg) { 133 uintptr_t Start = reinterpret_cast<uintptr_t>(Base); 134 for (size_t i = 0; i < State.MaxSimultaneousAllocations; ++i) { 135 const AllocationMetadata &Meta = Metadata[i]; 136 if (Meta.Addr && !Meta.IsDeallocated && Meta.Addr >= Start && 137 Meta.Addr < Start + Size) 138 Cb(Meta.Addr, Meta.RequestedSize, Arg); 139 } 140 } 141 142 void GuardedPoolAllocator::uninitTestOnly() { 143 if (State.GuardedPagePool) { 144 unreserveGuardedPool(); 145 State.GuardedPagePool = 0; 146 State.GuardedPagePoolEnd = 0; 147 } 148 if (Metadata) { 149 unmap(Metadata, 150 roundUpTo(State.MaxSimultaneousAllocations * sizeof(*Metadata), 151 State.PageSize)); 152 Metadata = nullptr; 153 } 154 if (FreeSlots) { 155 unmap(FreeSlots, 156 roundUpTo(State.MaxSimultaneousAllocations * sizeof(*FreeSlots), 157 State.PageSize)); 158 FreeSlots = nullptr; 159 } 160 *getThreadLocals() = ThreadLocalPackedVariables(); 161 } 162 163 // Note, minimum backing allocation size in GWP-ASan is always one page, and 164 // each slot could potentially be multiple pages (but always in 165 // page-increments). Thus, for anything that requires less than page size 166 // alignment, we don't need to allocate extra padding to ensure the alignment 167 // can be met. 168 size_t GuardedPoolAllocator::getRequiredBackingSize(size_t Size, 169 size_t Alignment, 170 size_t PageSize) { 171 assert(isPowerOfTwo(Alignment) && "Alignment must be a power of two!"); 172 assert(Alignment != 0 && "Alignment should be non-zero"); 173 assert(Size != 0 && "Size should be non-zero"); 174 175 if (Alignment <= PageSize) 176 return Size; 177 178 return Size + Alignment - PageSize; 179 } 180 181 uintptr_t GuardedPoolAllocator::alignUp(uintptr_t Ptr, size_t Alignment) { 182 assert(isPowerOfTwo(Alignment) && "Alignment must be a power of two!"); 183 assert(Alignment != 0 && "Alignment should be non-zero"); 184 if ((Ptr & (Alignment - 1)) == 0) 185 return Ptr; 186 187 Ptr += Alignment - (Ptr & (Alignment - 1)); 188 return Ptr; 189 } 190 191 uintptr_t GuardedPoolAllocator::alignDown(uintptr_t Ptr, size_t Alignment) { 192 assert(isPowerOfTwo(Alignment) && "Alignment must be a power of two!"); 193 assert(Alignment != 0 && "Alignment should be non-zero"); 194 if ((Ptr & (Alignment - 1)) == 0) 195 return Ptr; 196 197 Ptr -= Ptr & (Alignment - 1); 198 return Ptr; 199 } 200 201 void *GuardedPoolAllocator::allocate(size_t Size, size_t Alignment) { 202 // GuardedPagePoolEnd == 0 when GWP-ASan is disabled. If we are disabled, fall 203 // back to the supporting allocator. 204 if (State.GuardedPagePoolEnd == 0) { 205 getThreadLocals()->NextSampleCounter = 206 (AdjustedSampleRatePlusOne - 1) & 207 ThreadLocalPackedVariables::NextSampleCounterMask; 208 return nullptr; 209 } 210 211 if (Size == 0) 212 Size = 1; 213 if (Alignment == 0) 214 Alignment = alignof(max_align_t); 215 216 if (!isPowerOfTwo(Alignment) || Alignment > State.maximumAllocationSize() || 217 Size > State.maximumAllocationSize()) 218 return nullptr; 219 220 size_t BackingSize = getRequiredBackingSize(Size, Alignment, State.PageSize); 221 if (BackingSize > State.maximumAllocationSize()) 222 return nullptr; 223 224 // Protect against recursivity. 225 if (getThreadLocals()->RecursiveGuard) 226 return nullptr; 227 ScopedRecursiveGuard SRG; 228 229 size_t Index; 230 { 231 ScopedLock L(PoolMutex); 232 Index = reserveSlot(); 233 } 234 235 if (Index == kInvalidSlotID) 236 return nullptr; 237 238 uintptr_t SlotStart = State.slotToAddr(Index); 239 AllocationMetadata *Meta = addrToMetadata(SlotStart); 240 uintptr_t SlotEnd = State.slotToAddr(Index) + State.maximumAllocationSize(); 241 uintptr_t UserPtr; 242 // Randomly choose whether to left-align or right-align the allocation, and 243 // then apply the necessary adjustments to get an aligned pointer. 244 if (getRandomUnsigned32() % 2 == 0) 245 UserPtr = alignUp(SlotStart, Alignment); 246 else 247 UserPtr = alignDown(SlotEnd - Size, Alignment); 248 249 assert(UserPtr >= SlotStart); 250 assert(UserPtr + Size <= SlotEnd); 251 252 // If a slot is multiple pages in size, and the allocation takes up a single 253 // page, we can improve overflow detection by leaving the unused pages as 254 // unmapped. 255 const size_t PageSize = State.PageSize; 256 allocateInGuardedPool( 257 reinterpret_cast<void *>(getPageAddr(UserPtr, PageSize)), 258 roundUpTo(Size, PageSize)); 259 260 Meta->RecordAllocation(UserPtr, Size); 261 { 262 ScopedLock UL(BacktraceMutex); 263 Meta->AllocationTrace.RecordBacktrace(Backtrace); 264 } 265 266 return reinterpret_cast<void *>(UserPtr); 267 } 268 269 void GuardedPoolAllocator::raiseInternallyDetectedError(uintptr_t Address, 270 Error E) { 271 // Disable the allocator before setting the internal failure state. In 272 // non-recoverable mode, the allocator will be permanently disabled, and so 273 // things will be accessed without locks. 274 disable(); 275 276 // Races between internally- and externally-raised faults can happen. Right 277 // now, in this thread we've locked the allocator in order to raise an 278 // internally-detected fault, and another thread could SIGSEGV to raise an 279 // externally-detected fault. What will happen is that the other thread will 280 // wait in the signal handler, as we hold the allocator's locks from the 281 // disable() above. We'll trigger the signal handler by touching the 282 // internal-signal-raising address below, and the signal handler from our 283 // thread will get to run first as we will continue to hold the allocator 284 // locks until the enable() at the end of this function. Be careful though, if 285 // this thread receives another SIGSEGV after the disable() above, but before 286 // touching the internal-signal-raising address below, then this thread will 287 // get an "externally-raised" SIGSEGV while *also* holding the allocator 288 // locks, which means this thread's signal handler will deadlock. This could 289 // be resolved with a re-entrant lock, but asking platforms to implement this 290 // seems unnecessary given the only way to get a SIGSEGV in this critical 291 // section is either a memory safety bug in the couple lines of code below (be 292 // careful!), or someone outside uses `kill(this_thread, SIGSEGV)`, which 293 // really shouldn't happen. 294 295 State.FailureType = E; 296 State.FailureAddress = Address; 297 298 // Raise a SEGV by touching a specific address that identifies to the crash 299 // handler that this is an internally-raised fault. Changing this address? 300 // Don't forget to update __gwp_asan_get_internal_crash_address. 301 volatile char *p = 302 reinterpret_cast<char *>(State.internallyDetectedErrorFaultAddress()); 303 *p = 0; 304 305 // This should never be reached in non-recoverable mode. Ensure that the 306 // signal handler called handleRecoverablePostCrashReport(), which was 307 // responsible for re-setting these fields. 308 assert(State.FailureType == Error::UNKNOWN); 309 assert(State.FailureAddress == 0u); 310 311 // In recoverable mode, the signal handler (after dumping the crash) marked 312 // the page containing the InternalFaultSegvAddress as read/writeable, to 313 // allow the second touch to succeed after returning from the signal handler. 314 // Now, we need to mark the page as non-read/write-able again, so future 315 // internal faults can be raised. 316 deallocateInGuardedPool( 317 reinterpret_cast<void *>(getPageAddr( 318 State.internallyDetectedErrorFaultAddress(), State.PageSize)), 319 State.PageSize); 320 321 // And now we're done with patching ourselves back up, enable the allocator. 322 enable(); 323 } 324 325 void GuardedPoolAllocator::deallocate(void *Ptr) { 326 assert(pointerIsMine(Ptr) && "Pointer is not mine!"); 327 uintptr_t UPtr = reinterpret_cast<uintptr_t>(Ptr); 328 size_t Slot = State.getNearestSlot(UPtr); 329 uintptr_t SlotStart = State.slotToAddr(Slot); 330 AllocationMetadata *Meta = addrToMetadata(UPtr); 331 332 // If this allocation is responsible for crash, never recycle it. Turn the 333 // deallocate() call into a no-op. 334 if (Meta->HasCrashed) 335 return; 336 337 if (Meta->Addr != UPtr) { 338 raiseInternallyDetectedError(UPtr, Error::INVALID_FREE); 339 return; 340 } 341 if (Meta->IsDeallocated) { 342 raiseInternallyDetectedError(UPtr, Error::DOUBLE_FREE); 343 return; 344 } 345 346 // Intentionally scope the mutex here, so that other threads can access the 347 // pool during the expensive markInaccessible() call. 348 { 349 ScopedLock L(PoolMutex); 350 351 // Ensure that the deallocation is recorded before marking the page as 352 // inaccessible. Otherwise, a racy use-after-free will have inconsistent 353 // metadata. 354 Meta->RecordDeallocation(); 355 356 // Ensure that the unwinder is not called if the recursive flag is set, 357 // otherwise non-reentrant unwinders may deadlock. 358 if (!getThreadLocals()->RecursiveGuard) { 359 ScopedRecursiveGuard SRG; 360 ScopedLock UL(BacktraceMutex); 361 Meta->DeallocationTrace.RecordBacktrace(Backtrace); 362 } 363 } 364 365 deallocateInGuardedPool(reinterpret_cast<void *>(SlotStart), 366 State.maximumAllocationSize()); 367 368 // And finally, lock again to release the slot back into the pool. 369 ScopedLock L(PoolMutex); 370 freeSlot(Slot); 371 } 372 373 // Thread-compatible, protected by PoolMutex. 374 static bool PreviousRecursiveGuard; 375 376 void GuardedPoolAllocator::preCrashReport(void *Ptr) { 377 assert(pointerIsMine(Ptr) && "Pointer is not mine!"); 378 uintptr_t InternalCrashAddr = __gwp_asan_get_internal_crash_address( 379 &State, reinterpret_cast<uintptr_t>(Ptr)); 380 if (!InternalCrashAddr) 381 disable(); 382 383 // If something in the signal handler calls malloc() while dumping the 384 // GWP-ASan report (e.g. backtrace_symbols()), make sure that GWP-ASan doesn't 385 // service that allocation. `PreviousRecursiveGuard` is protected by the 386 // allocator locks taken in disable(), either explicitly above for 387 // externally-raised errors, or implicitly in raiseInternallyDetectedError() 388 // for internally-detected errors. 389 PreviousRecursiveGuard = getThreadLocals()->RecursiveGuard; 390 getThreadLocals()->RecursiveGuard = true; 391 } 392 393 void GuardedPoolAllocator::postCrashReportRecoverableOnly(void *SignalPtr) { 394 uintptr_t SignalUPtr = reinterpret_cast<uintptr_t>(SignalPtr); 395 uintptr_t InternalCrashAddr = 396 __gwp_asan_get_internal_crash_address(&State, SignalUPtr); 397 uintptr_t ErrorUptr = InternalCrashAddr ?: SignalUPtr; 398 399 AllocationMetadata *Metadata = addrToMetadata(ErrorUptr); 400 Metadata->HasCrashed = true; 401 402 allocateInGuardedPool( 403 reinterpret_cast<void *>(getPageAddr(SignalUPtr, State.PageSize)), 404 State.PageSize); 405 406 // Clear the internal state in order to not confuse the crash handler if a 407 // use-after-free or buffer-overflow comes from a different allocation in the 408 // future. 409 if (InternalCrashAddr) { 410 State.FailureType = Error::UNKNOWN; 411 State.FailureAddress = 0; 412 } 413 414 size_t Slot = State.getNearestSlot(ErrorUptr); 415 // If the slot is available, remove it permanently. 416 for (size_t i = 0; i < FreeSlotsLength; ++i) { 417 if (FreeSlots[i] == Slot) { 418 FreeSlots[i] = FreeSlots[FreeSlotsLength - 1]; 419 FreeSlotsLength -= 1; 420 break; 421 } 422 } 423 424 getThreadLocals()->RecursiveGuard = PreviousRecursiveGuard; 425 if (!InternalCrashAddr) 426 enable(); 427 } 428 429 size_t GuardedPoolAllocator::getSize(const void *Ptr) { 430 assert(pointerIsMine(Ptr)); 431 ScopedLock L(PoolMutex); 432 AllocationMetadata *Meta = addrToMetadata(reinterpret_cast<uintptr_t>(Ptr)); 433 assert(Meta->Addr == reinterpret_cast<uintptr_t>(Ptr)); 434 return Meta->RequestedSize; 435 } 436 437 AllocationMetadata *GuardedPoolAllocator::addrToMetadata(uintptr_t Ptr) const { 438 return &Metadata[State.getNearestSlot(Ptr)]; 439 } 440 441 size_t GuardedPoolAllocator::reserveSlot() { 442 // Avoid potential reuse of a slot before we have made at least a single 443 // allocation in each slot. Helps with our use-after-free detection. 444 if (NumSampledAllocations < State.MaxSimultaneousAllocations) 445 return NumSampledAllocations++; 446 447 if (FreeSlotsLength == 0) 448 return kInvalidSlotID; 449 450 size_t ReservedIndex = getRandomUnsigned32() % FreeSlotsLength; 451 size_t SlotIndex = FreeSlots[ReservedIndex]; 452 FreeSlots[ReservedIndex] = FreeSlots[--FreeSlotsLength]; 453 return SlotIndex; 454 } 455 456 void GuardedPoolAllocator::freeSlot(size_t SlotIndex) { 457 assert(FreeSlotsLength < State.MaxSimultaneousAllocations); 458 FreeSlots[FreeSlotsLength++] = SlotIndex; 459 } 460 461 uint32_t GuardedPoolAllocator::getRandomUnsigned32() { 462 uint32_t RandomState = getThreadLocals()->RandomState; 463 RandomState ^= RandomState << 13; 464 RandomState ^= RandomState >> 17; 465 RandomState ^= RandomState << 5; 466 getThreadLocals()->RandomState = RandomState; 467 return RandomState; 468 } 469 } // namespace gwp_asan 470