compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp

   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