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/options.h" 12 13 // RHEL creates the PRIu64 format macro (for printing uint64_t's) only when this 14 // macro is defined before including <inttypes.h>. 15 #ifndef __STDC_FORMAT_MACROS 16 #define __STDC_FORMAT_MACROS 1 17 #endif 18 19 #include <assert.h> 20 #include <inttypes.h> 21 #include <stdio.h> 22 #include <stdlib.h> 23 #include <string.h> 24 #include <time.h> 25 26 using AllocationMetadata = gwp_asan::GuardedPoolAllocator::AllocationMetadata; 27 using Error = gwp_asan::GuardedPoolAllocator::Error; 28 29 namespace gwp_asan { 30 namespace { 31 // Forward declare the pointer to the singleton version of this class. 32 // Instantiated during initialisation, this allows the signal handler 33 // to find this class in order to deduce the root cause of failures. Must not be 34 // referenced by users outside this translation unit, in order to avoid 35 // init-order-fiasco. 36 GuardedPoolAllocator *SingletonPtr = nullptr; 37 38 class ScopedBoolean { 39 public: 40 ScopedBoolean(bool &B) : Bool(B) { Bool = true; } 41 ~ScopedBoolean() { Bool = false; } 42 43 private: 44 bool &Bool; 45 }; 46 47 void defaultPrintStackTrace(uintptr_t *Trace, size_t TraceLength, 48 options::Printf_t Printf) { 49 if (TraceLength == 0) 50 Printf(" <unknown (does your allocator support backtracing?)>\n"); 51 52 for (size_t i = 0; i < TraceLength; ++i) { 53 Printf(" #%zu 0x%zx in <unknown>\n", i, Trace[i]); 54 } 55 Printf("\n"); 56 } 57 } // anonymous namespace 58 59 // Gets the singleton implementation of this class. Thread-compatible until 60 // init() is called, thread-safe afterwards. 61 GuardedPoolAllocator *getSingleton() { return SingletonPtr; } 62 63 void GuardedPoolAllocator::AllocationMetadata::RecordAllocation( 64 uintptr_t AllocAddr, size_t AllocSize, options::Backtrace_t Backtrace) { 65 Addr = AllocAddr; 66 Size = AllocSize; 67 IsDeallocated = false; 68 69 // TODO(hctim): Ask the caller to provide the thread ID, so we don't waste 70 // other thread's time getting the thread ID under lock. 71 AllocationTrace.ThreadID = getThreadID(); 72 AllocationTrace.TraceSize = 0; 73 DeallocationTrace.TraceSize = 0; 74 DeallocationTrace.ThreadID = kInvalidThreadID; 75 76 if (Backtrace) { 77 uintptr_t UncompressedBuffer[kMaxTraceLengthToCollect]; 78 size_t BacktraceLength = 79 Backtrace(UncompressedBuffer, kMaxTraceLengthToCollect); 80 AllocationTrace.TraceSize = compression::pack( 81 UncompressedBuffer, BacktraceLength, AllocationTrace.CompressedTrace, 82 kStackFrameStorageBytes); 83 } 84 } 85 86 void GuardedPoolAllocator::AllocationMetadata::RecordDeallocation( 87 options::Backtrace_t Backtrace) { 88 IsDeallocated = true; 89 // Ensure that the unwinder is not called if the recursive flag is set, 90 // otherwise non-reentrant unwinders may deadlock. 91 DeallocationTrace.TraceSize = 0; 92 if (Backtrace && !ThreadLocals.RecursiveGuard) { 93 ScopedBoolean B(ThreadLocals.RecursiveGuard); 94 95 uintptr_t UncompressedBuffer[kMaxTraceLengthToCollect]; 96 size_t BacktraceLength = 97 Backtrace(UncompressedBuffer, kMaxTraceLengthToCollect); 98 DeallocationTrace.TraceSize = compression::pack( 99 UncompressedBuffer, BacktraceLength, DeallocationTrace.CompressedTrace, 100 kStackFrameStorageBytes); 101 } 102 DeallocationTrace.ThreadID = getThreadID(); 103 } 104 105 void GuardedPoolAllocator::init(const options::Options &Opts) { 106 // Note: We return from the constructor here if GWP-ASan is not available. 107 // This will stop heap-allocation of class members, as well as mmap() of the 108 // guarded slots. 109 if (!Opts.Enabled || Opts.SampleRate == 0 || 110 Opts.MaxSimultaneousAllocations == 0) 111 return; 112 113 if (Opts.SampleRate < 0) { 114 Opts.Printf("GWP-ASan Error: SampleRate is < 0.\n"); 115 exit(EXIT_FAILURE); 116 } 117 118 if (Opts.SampleRate > INT32_MAX) { 119 Opts.Printf("GWP-ASan Error: SampleRate is > 2^31.\n"); 120 exit(EXIT_FAILURE); 121 } 122 123 if (Opts.MaxSimultaneousAllocations < 0) { 124 Opts.Printf("GWP-ASan Error: MaxSimultaneousAllocations is < 0.\n"); 125 exit(EXIT_FAILURE); 126 } 127 128 SingletonPtr = this; 129 130 MaxSimultaneousAllocations = Opts.MaxSimultaneousAllocations; 131 132 PageSize = getPlatformPageSize(); 133 134 PerfectlyRightAlign = Opts.PerfectlyRightAlign; 135 Printf = Opts.Printf; 136 Backtrace = Opts.Backtrace; 137 if (Opts.PrintBacktrace) 138 PrintBacktrace = Opts.PrintBacktrace; 139 else 140 PrintBacktrace = defaultPrintStackTrace; 141 142 size_t PoolBytesRequired = 143 PageSize * (1 + MaxSimultaneousAllocations) + 144 MaxSimultaneousAllocations * maximumAllocationSize(); 145 void *GuardedPoolMemory = mapMemory(PoolBytesRequired); 146 147 size_t BytesRequired = MaxSimultaneousAllocations * sizeof(*Metadata); 148 Metadata = reinterpret_cast<AllocationMetadata *>(mapMemory(BytesRequired)); 149 markReadWrite(Metadata, BytesRequired); 150 151 // Allocate memory and set up the free pages queue. 152 BytesRequired = MaxSimultaneousAllocations * sizeof(*FreeSlots); 153 FreeSlots = reinterpret_cast<size_t *>(mapMemory(BytesRequired)); 154 markReadWrite(FreeSlots, BytesRequired); 155 156 // Multiply the sample rate by 2 to give a good, fast approximation for (1 / 157 // SampleRate) chance of sampling. 158 if (Opts.SampleRate != 1) 159 AdjustedSampleRate = static_cast<uint32_t>(Opts.SampleRate) * 2; 160 else 161 AdjustedSampleRate = 1; 162 163 GuardedPagePool = reinterpret_cast<uintptr_t>(GuardedPoolMemory); 164 GuardedPagePoolEnd = 165 reinterpret_cast<uintptr_t>(GuardedPoolMemory) + PoolBytesRequired; 166 167 // Ensure that signal handlers are installed as late as possible, as the class 168 // is not thread-safe until init() is finished, and thus a SIGSEGV may cause a 169 // race to members if received during init(). 170 if (Opts.InstallSignalHandlers) 171 installSignalHandlers(); 172 } 173 174 void *GuardedPoolAllocator::allocate(size_t Size) { 175 // GuardedPagePoolEnd == 0 when GWP-ASan is disabled. If we are disabled, fall 176 // back to the supporting allocator. 177 if (GuardedPagePoolEnd == 0) 178 return nullptr; 179 180 // Protect against recursivity. 181 if (ThreadLocals.RecursiveGuard) 182 return nullptr; 183 ScopedBoolean SB(ThreadLocals.RecursiveGuard); 184 185 if (Size == 0 || Size > maximumAllocationSize()) 186 return nullptr; 187 188 size_t Index; 189 { 190 ScopedLock L(PoolMutex); 191 Index = reserveSlot(); 192 } 193 194 if (Index == kInvalidSlotID) 195 return nullptr; 196 197 uintptr_t Ptr = slotToAddr(Index); 198 Ptr += allocationSlotOffset(Size); 199 AllocationMetadata *Meta = addrToMetadata(Ptr); 200 201 // If a slot is multiple pages in size, and the allocation takes up a single 202 // page, we can improve overflow detection by leaving the unused pages as 203 // unmapped. 204 markReadWrite(reinterpret_cast<void *>(getPageAddr(Ptr)), Size); 205 206 Meta->RecordAllocation(Ptr, Size, Backtrace); 207 208 return reinterpret_cast<void *>(Ptr); 209 } 210 211 void GuardedPoolAllocator::deallocate(void *Ptr) { 212 assert(pointerIsMine(Ptr) && "Pointer is not mine!"); 213 uintptr_t UPtr = reinterpret_cast<uintptr_t>(Ptr); 214 uintptr_t SlotStart = slotToAddr(addrToSlot(UPtr)); 215 AllocationMetadata *Meta = addrToMetadata(UPtr); 216 if (Meta->Addr != UPtr) { 217 reportError(UPtr, Error::INVALID_FREE); 218 exit(EXIT_FAILURE); 219 } 220 221 // Intentionally scope the mutex here, so that other threads can access the 222 // pool during the expensive markInaccessible() call. 223 { 224 ScopedLock L(PoolMutex); 225 if (Meta->IsDeallocated) { 226 reportError(UPtr, Error::DOUBLE_FREE); 227 exit(EXIT_FAILURE); 228 } 229 230 // Ensure that the deallocation is recorded before marking the page as 231 // inaccessible. Otherwise, a racy use-after-free will have inconsistent 232 // metadata. 233 Meta->RecordDeallocation(Backtrace); 234 } 235 236 markInaccessible(reinterpret_cast<void *>(SlotStart), 237 maximumAllocationSize()); 238 239 // And finally, lock again to release the slot back into the pool. 240 ScopedLock L(PoolMutex); 241 freeSlot(addrToSlot(UPtr)); 242 } 243 244 size_t GuardedPoolAllocator::getSize(const void *Ptr) { 245 assert(pointerIsMine(Ptr)); 246 ScopedLock L(PoolMutex); 247 AllocationMetadata *Meta = addrToMetadata(reinterpret_cast<uintptr_t>(Ptr)); 248 assert(Meta->Addr == reinterpret_cast<uintptr_t>(Ptr)); 249 return Meta->Size; 250 } 251 252 size_t GuardedPoolAllocator::maximumAllocationSize() const { return PageSize; } 253 254 AllocationMetadata *GuardedPoolAllocator::addrToMetadata(uintptr_t Ptr) const { 255 return &Metadata[addrToSlot(Ptr)]; 256 } 257 258 size_t GuardedPoolAllocator::addrToSlot(uintptr_t Ptr) const { 259 assert(pointerIsMine(reinterpret_cast<void *>(Ptr))); 260 size_t ByteOffsetFromPoolStart = Ptr - GuardedPagePool; 261 return ByteOffsetFromPoolStart / (maximumAllocationSize() + PageSize); 262 } 263 264 uintptr_t GuardedPoolAllocator::slotToAddr(size_t N) const { 265 return GuardedPagePool + (PageSize * (1 + N)) + (maximumAllocationSize() * N); 266 } 267 268 uintptr_t GuardedPoolAllocator::getPageAddr(uintptr_t Ptr) const { 269 assert(pointerIsMine(reinterpret_cast<void *>(Ptr))); 270 return Ptr & ~(static_cast<uintptr_t>(PageSize) - 1); 271 } 272 273 bool GuardedPoolAllocator::isGuardPage(uintptr_t Ptr) const { 274 assert(pointerIsMine(reinterpret_cast<void *>(Ptr))); 275 size_t PageOffsetFromPoolStart = (Ptr - GuardedPagePool) / PageSize; 276 size_t PagesPerSlot = maximumAllocationSize() / PageSize; 277 return (PageOffsetFromPoolStart % (PagesPerSlot + 1)) == 0; 278 } 279 280 size_t GuardedPoolAllocator::reserveSlot() { 281 // Avoid potential reuse of a slot before we have made at least a single 282 // allocation in each slot. Helps with our use-after-free detection. 283 if (NumSampledAllocations < MaxSimultaneousAllocations) 284 return NumSampledAllocations++; 285 286 if (FreeSlotsLength == 0) 287 return kInvalidSlotID; 288 289 size_t ReservedIndex = getRandomUnsigned32() % FreeSlotsLength; 290 size_t SlotIndex = FreeSlots[ReservedIndex]; 291 FreeSlots[ReservedIndex] = FreeSlots[--FreeSlotsLength]; 292 return SlotIndex; 293 } 294 295 void GuardedPoolAllocator::freeSlot(size_t SlotIndex) { 296 assert(FreeSlotsLength < MaxSimultaneousAllocations); 297 FreeSlots[FreeSlotsLength++] = SlotIndex; 298 } 299 300 uintptr_t GuardedPoolAllocator::allocationSlotOffset(size_t Size) const { 301 assert(Size > 0); 302 303 bool ShouldRightAlign = getRandomUnsigned32() % 2 == 0; 304 if (!ShouldRightAlign) 305 return 0; 306 307 uintptr_t Offset = maximumAllocationSize(); 308 if (!PerfectlyRightAlign) { 309 if (Size == 3) 310 Size = 4; 311 else if (Size > 4 && Size <= 8) 312 Size = 8; 313 else if (Size > 8 && (Size % 16) != 0) 314 Size += 16 - (Size % 16); 315 } 316 Offset -= Size; 317 return Offset; 318 } 319 320 void GuardedPoolAllocator::reportError(uintptr_t AccessPtr, Error E) { 321 if (SingletonPtr) 322 SingletonPtr->reportErrorInternal(AccessPtr, E); 323 } 324 325 size_t GuardedPoolAllocator::getNearestSlot(uintptr_t Ptr) const { 326 if (Ptr <= GuardedPagePool + PageSize) 327 return 0; 328 if (Ptr > GuardedPagePoolEnd - PageSize) 329 return MaxSimultaneousAllocations - 1; 330 331 if (!isGuardPage(Ptr)) 332 return addrToSlot(Ptr); 333 334 if (Ptr % PageSize <= PageSize / 2) 335 return addrToSlot(Ptr - PageSize); // Round down. 336 return addrToSlot(Ptr + PageSize); // Round up. 337 } 338 339 Error GuardedPoolAllocator::diagnoseUnknownError(uintptr_t AccessPtr, 340 AllocationMetadata **Meta) { 341 // Let's try and figure out what the source of this error is. 342 if (isGuardPage(AccessPtr)) { 343 size_t Slot = getNearestSlot(AccessPtr); 344 AllocationMetadata *SlotMeta = addrToMetadata(slotToAddr(Slot)); 345 346 // Ensure that this slot was allocated once upon a time. 347 if (!SlotMeta->Addr) 348 return Error::UNKNOWN; 349 *Meta = SlotMeta; 350 351 if (SlotMeta->Addr < AccessPtr) 352 return Error::BUFFER_OVERFLOW; 353 return Error::BUFFER_UNDERFLOW; 354 } 355 356 // Access wasn't a guard page, check for use-after-free. 357 AllocationMetadata *SlotMeta = addrToMetadata(AccessPtr); 358 if (SlotMeta->IsDeallocated) { 359 *Meta = SlotMeta; 360 return Error::USE_AFTER_FREE; 361 } 362 363 // If we have reached here, the error is still unknown. There is no metadata 364 // available. 365 *Meta = nullptr; 366 return Error::UNKNOWN; 367 } 368 369 namespace { 370 // Prints the provided error and metadata information. 371 void printErrorType(Error E, uintptr_t AccessPtr, AllocationMetadata *Meta, 372 options::Printf_t Printf, uint64_t ThreadID) { 373 // Print using intermediate strings. Platforms like Android don't like when 374 // you print multiple times to the same line, as there may be a newline 375 // appended to a log file automatically per Printf() call. 376 const char *ErrorString; 377 switch (E) { 378 case Error::UNKNOWN: 379 ErrorString = "GWP-ASan couldn't automatically determine the source of " 380 "the memory error. It was likely caused by a wild memory " 381 "access into the GWP-ASan pool. The error occurred"; 382 break; 383 case Error::USE_AFTER_FREE: 384 ErrorString = "Use after free"; 385 break; 386 case Error::DOUBLE_FREE: 387 ErrorString = "Double free"; 388 break; 389 case Error::INVALID_FREE: 390 ErrorString = "Invalid (wild) free"; 391 break; 392 case Error::BUFFER_OVERFLOW: 393 ErrorString = "Buffer overflow"; 394 break; 395 case Error::BUFFER_UNDERFLOW: 396 ErrorString = "Buffer underflow"; 397 break; 398 } 399 400 constexpr size_t kDescriptionBufferLen = 128; 401 char DescriptionBuffer[kDescriptionBufferLen]; 402 if (Meta) { 403 if (E == Error::USE_AFTER_FREE) { 404 snprintf(DescriptionBuffer, kDescriptionBufferLen, 405 "(%zu byte%s into a %zu-byte allocation at 0x%zx)", 406 AccessPtr - Meta->Addr, (AccessPtr - Meta->Addr == 1) ? "" : "s", 407 Meta->Size, Meta->Addr); 408 } else if (AccessPtr < Meta->Addr) { 409 snprintf(DescriptionBuffer, kDescriptionBufferLen, 410 "(%zu byte%s to the left of a %zu-byte allocation at 0x%zx)", 411 Meta->Addr - AccessPtr, (Meta->Addr - AccessPtr == 1) ? "" : "s", 412 Meta->Size, Meta->Addr); 413 } else if (AccessPtr > Meta->Addr) { 414 snprintf(DescriptionBuffer, kDescriptionBufferLen, 415 "(%zu byte%s to the right of a %zu-byte allocation at 0x%zx)", 416 AccessPtr - Meta->Addr, (AccessPtr - Meta->Addr == 1) ? "" : "s", 417 Meta->Size, Meta->Addr); 418 } else { 419 snprintf(DescriptionBuffer, kDescriptionBufferLen, 420 "(a %zu-byte allocation)", Meta->Size); 421 } 422 } 423 424 // Possible number of digits of a 64-bit number: ceil(log10(2^64)) == 20. Add 425 // a null terminator, and round to the nearest 8-byte boundary. 426 constexpr size_t kThreadBufferLen = 24; 427 char ThreadBuffer[kThreadBufferLen]; 428 if (ThreadID == GuardedPoolAllocator::kInvalidThreadID) 429 snprintf(ThreadBuffer, kThreadBufferLen, "<unknown>"); 430 else 431 snprintf(ThreadBuffer, kThreadBufferLen, "%" PRIu64, ThreadID); 432 433 Printf("%s at 0x%zx %s by thread %s here:\n", ErrorString, AccessPtr, 434 DescriptionBuffer, ThreadBuffer); 435 } 436 437 void printAllocDeallocTraces(uintptr_t AccessPtr, AllocationMetadata *Meta, 438 options::Printf_t Printf, 439 options::PrintBacktrace_t PrintBacktrace) { 440 assert(Meta != nullptr && "Metadata is non-null for printAllocDeallocTraces"); 441 442 if (Meta->IsDeallocated) { 443 if (Meta->DeallocationTrace.ThreadID == 444 GuardedPoolAllocator::kInvalidThreadID) 445 Printf("0x%zx was deallocated by thread <unknown> here:\n", AccessPtr); 446 else 447 Printf("0x%zx was deallocated by thread %zu here:\n", AccessPtr, 448 Meta->DeallocationTrace.ThreadID); 449 450 uintptr_t UncompressedTrace[AllocationMetadata::kMaxTraceLengthToCollect]; 451 size_t UncompressedLength = compression::unpack( 452 Meta->DeallocationTrace.CompressedTrace, 453 Meta->DeallocationTrace.TraceSize, UncompressedTrace, 454 AllocationMetadata::kMaxTraceLengthToCollect); 455 456 PrintBacktrace(UncompressedTrace, UncompressedLength, Printf); 457 } 458 459 if (Meta->AllocationTrace.ThreadID == GuardedPoolAllocator::kInvalidThreadID) 460 Printf("0x%zx was allocated by thread <unknown> here:\n", Meta->Addr); 461 else 462 Printf("0x%zx was allocated by thread %zu here:\n", Meta->Addr, 463 Meta->AllocationTrace.ThreadID); 464 465 uintptr_t UncompressedTrace[AllocationMetadata::kMaxTraceLengthToCollect]; 466 size_t UncompressedLength = compression::unpack( 467 Meta->AllocationTrace.CompressedTrace, Meta->AllocationTrace.TraceSize, 468 UncompressedTrace, AllocationMetadata::kMaxTraceLengthToCollect); 469 470 PrintBacktrace(UncompressedTrace, UncompressedLength, Printf); 471 } 472 473 struct ScopedEndOfReportDecorator { 474 ScopedEndOfReportDecorator(options::Printf_t Printf) : Printf(Printf) {} 475 ~ScopedEndOfReportDecorator() { Printf("*** End GWP-ASan report ***\n"); } 476 options::Printf_t Printf; 477 }; 478 } // anonymous namespace 479 480 void GuardedPoolAllocator::reportErrorInternal(uintptr_t AccessPtr, Error E) { 481 if (!pointerIsMine(reinterpret_cast<void *>(AccessPtr))) { 482 return; 483 } 484 485 // Attempt to prevent races to re-use the same slot that triggered this error. 486 // This does not guarantee that there are no races, because another thread can 487 // take the locks during the time that the signal handler is being called. 488 PoolMutex.tryLock(); 489 ThreadLocals.RecursiveGuard = true; 490 491 Printf("*** GWP-ASan detected a memory error ***\n"); 492 ScopedEndOfReportDecorator Decorator(Printf); 493 494 AllocationMetadata *Meta = nullptr; 495 496 if (E == Error::UNKNOWN) { 497 E = diagnoseUnknownError(AccessPtr, &Meta); 498 } else { 499 size_t Slot = getNearestSlot(AccessPtr); 500 Meta = addrToMetadata(slotToAddr(Slot)); 501 // Ensure that this slot has been previously allocated. 502 if (!Meta->Addr) 503 Meta = nullptr; 504 } 505 506 // Print the error information. 507 uint64_t ThreadID = getThreadID(); 508 printErrorType(E, AccessPtr, Meta, Printf, ThreadID); 509 if (Backtrace) { 510 static constexpr unsigned kMaximumStackFramesForCrashTrace = 512; 511 uintptr_t Trace[kMaximumStackFramesForCrashTrace]; 512 size_t TraceLength = Backtrace(Trace, kMaximumStackFramesForCrashTrace); 513 514 PrintBacktrace(Trace, TraceLength, Printf); 515 } else { 516 Printf(" <unknown (does your allocator support backtracing?)>\n\n"); 517 } 518 519 if (Meta) 520 printAllocDeallocTraces(AccessPtr, Meta, Printf, PrintBacktrace); 521 } 522 523 GWP_ASAN_TLS_INITIAL_EXEC 524 GuardedPoolAllocator::ThreadLocalPackedVariables 525 GuardedPoolAllocator::ThreadLocals; 526 } // namespace gwp_asan 527