1 //===-- guarded_pool_allocator.cpp ------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 #include "gwp_asan/guarded_pool_allocator.h"
11 #include "gwp_asan/options.h"
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
26 using AllocationMetadata = gwp_asan::GuardedPoolAllocator::AllocationMetadata;
27 using Error = gwp_asan::GuardedPoolAllocator::Error;
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
36 GuardedPoolAllocator *SingletonPtr = nullptr;
40 ScopedBoolean(bool &B) : Bool(B) { Bool = true; }
41 ~ScopedBoolean() { Bool = false; }
47 void defaultPrintStackTrace(uintptr_t *Trace, size_t TraceLength,
48 options::Printf_t Printf) {
50 Printf(" <unknown (does your allocator support backtracing?)>\n");
52 for (size_t i = 0; i < TraceLength; ++i) {
53 Printf(" #%zu 0x%zx in <unknown>\n", i, Trace[i]);
57 } // anonymous namespace
59 // Gets the singleton implementation of this class. Thread-compatible until
60 // init() is called, thread-safe afterwards.
61 GuardedPoolAllocator *getSingleton() { return SingletonPtr; }
63 void GuardedPoolAllocator::AllocationMetadata::RecordAllocation(
64 uintptr_t AllocAddr, size_t AllocSize, options::Backtrace_t Backtrace) {
67 IsDeallocated = false;
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;
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);
86 void GuardedPoolAllocator::AllocationMetadata::RecordDeallocation(
87 options::Backtrace_t Backtrace) {
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);
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);
102 DeallocationTrace.ThreadID = getThreadID();
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
109 if (!Opts.Enabled || Opts.SampleRate == 0 ||
110 Opts.MaxSimultaneousAllocations == 0)
113 if (Opts.SampleRate < 0) {
114 Opts.Printf("GWP-ASan Error: SampleRate is < 0.\n");
118 if (Opts.SampleRate > INT32_MAX) {
119 Opts.Printf("GWP-ASan Error: SampleRate is > 2^31.\n");
123 if (Opts.MaxSimultaneousAllocations < 0) {
124 Opts.Printf("GWP-ASan Error: MaxSimultaneousAllocations is < 0.\n");
130 MaxSimultaneousAllocations = Opts.MaxSimultaneousAllocations;
132 PageSize = getPlatformPageSize();
134 PerfectlyRightAlign = Opts.PerfectlyRightAlign;
135 Printf = Opts.Printf;
136 Backtrace = Opts.Backtrace;
137 if (Opts.PrintBacktrace)
138 PrintBacktrace = Opts.PrintBacktrace;
140 PrintBacktrace = defaultPrintStackTrace;
142 size_t PoolBytesRequired =
143 PageSize * (1 + MaxSimultaneousAllocations) +
144 MaxSimultaneousAllocations * maximumAllocationSize();
145 void *GuardedPoolMemory = mapMemory(PoolBytesRequired);
147 size_t BytesRequired = MaxSimultaneousAllocations * sizeof(*Metadata);
148 Metadata = reinterpret_cast<AllocationMetadata *>(mapMemory(BytesRequired));
149 markReadWrite(Metadata, BytesRequired);
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);
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;
161 AdjustedSampleRate = 1;
163 GuardedPagePool = reinterpret_cast<uintptr_t>(GuardedPoolMemory);
165 reinterpret_cast<uintptr_t>(GuardedPoolMemory) + PoolBytesRequired;
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();
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)
180 // Protect against recursivity.
181 if (ThreadLocals.RecursiveGuard)
183 ScopedBoolean SB(ThreadLocals.RecursiveGuard);
185 if (Size == 0 || Size > maximumAllocationSize())
190 ScopedLock L(PoolMutex);
191 Index = reserveSlot();
194 if (Index == kInvalidSlotID)
197 uintptr_t Ptr = slotToAddr(Index);
198 Ptr += allocationSlotOffset(Size);
199 AllocationMetadata *Meta = addrToMetadata(Ptr);
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
204 markReadWrite(reinterpret_cast<void *>(getPageAddr(Ptr)), Size);
206 Meta->RecordAllocation(Ptr, Size, Backtrace);
208 return reinterpret_cast<void *>(Ptr);
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);
221 // Intentionally scope the mutex here, so that other threads can access the
222 // pool during the expensive markInaccessible() call.
224 ScopedLock L(PoolMutex);
225 if (Meta->IsDeallocated) {
226 reportError(UPtr, Error::DOUBLE_FREE);
230 // Ensure that the deallocation is recorded before marking the page as
231 // inaccessible. Otherwise, a racy use-after-free will have inconsistent
233 Meta->RecordDeallocation(Backtrace);
236 markInaccessible(reinterpret_cast<void *>(SlotStart),
237 maximumAllocationSize());
239 // And finally, lock again to release the slot back into the pool.
240 ScopedLock L(PoolMutex);
241 freeSlot(addrToSlot(UPtr));
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));
252 size_t GuardedPoolAllocator::maximumAllocationSize() const { return PageSize; }
254 AllocationMetadata *GuardedPoolAllocator::addrToMetadata(uintptr_t Ptr) const {
255 return &Metadata[addrToSlot(Ptr)];
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);
264 uintptr_t GuardedPoolAllocator::slotToAddr(size_t N) const {
265 return GuardedPagePool + (PageSize * (1 + N)) + (maximumAllocationSize() * N);
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);
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;
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++;
286 if (FreeSlotsLength == 0)
287 return kInvalidSlotID;
289 size_t ReservedIndex = getRandomUnsigned32() % FreeSlotsLength;
290 size_t SlotIndex = FreeSlots[ReservedIndex];
291 FreeSlots[ReservedIndex] = FreeSlots[--FreeSlotsLength];
295 void GuardedPoolAllocator::freeSlot(size_t SlotIndex) {
296 assert(FreeSlotsLength < MaxSimultaneousAllocations);
297 FreeSlots[FreeSlotsLength++] = SlotIndex;
300 uintptr_t GuardedPoolAllocator::allocationSlotOffset(size_t Size) const {
303 bool ShouldRightAlign = getRandomUnsigned32() % 2 == 0;
304 if (!ShouldRightAlign)
307 uintptr_t Offset = maximumAllocationSize();
308 if (!PerfectlyRightAlign) {
311 else if (Size > 4 && Size <= 8)
313 else if (Size > 8 && (Size % 16) != 0)
314 Size += 16 - (Size % 16);
320 void GuardedPoolAllocator::reportError(uintptr_t AccessPtr, Error E) {
322 SingletonPtr->reportErrorInternal(AccessPtr, E);
325 size_t GuardedPoolAllocator::getNearestSlot(uintptr_t Ptr) const {
326 if (Ptr <= GuardedPagePool + PageSize)
328 if (Ptr > GuardedPagePoolEnd - PageSize)
329 return MaxSimultaneousAllocations - 1;
331 if (!isGuardPage(Ptr))
332 return addrToSlot(Ptr);
334 if (Ptr % PageSize <= PageSize / 2)
335 return addrToSlot(Ptr - PageSize); // Round down.
336 return addrToSlot(Ptr + PageSize); // Round up.
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));
346 // Ensure that this slot was allocated once upon a time.
348 return Error::UNKNOWN;
351 if (SlotMeta->Addr < AccessPtr)
352 return Error::BUFFER_OVERFLOW;
353 return Error::BUFFER_UNDERFLOW;
356 // Access wasn't a guard page, check for use-after-free.
357 AllocationMetadata *SlotMeta = addrToMetadata(AccessPtr);
358 if (SlotMeta->IsDeallocated) {
360 return Error::USE_AFTER_FREE;
363 // If we have reached here, the error is still unknown. There is no metadata
366 return Error::UNKNOWN;
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;
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";
383 case Error::USE_AFTER_FREE:
384 ErrorString = "Use after free";
386 case Error::DOUBLE_FREE:
387 ErrorString = "Double free";
389 case Error::INVALID_FREE:
390 ErrorString = "Invalid (wild) free";
392 case Error::BUFFER_OVERFLOW:
393 ErrorString = "Buffer overflow";
395 case Error::BUFFER_UNDERFLOW:
396 ErrorString = "Buffer underflow";
400 constexpr size_t kDescriptionBufferLen = 128;
401 char DescriptionBuffer[kDescriptionBufferLen];
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);
419 snprintf(DescriptionBuffer, kDescriptionBufferLen,
420 "(a %zu-byte allocation)", Meta->Size);
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>");
431 snprintf(ThreadBuffer, kThreadBufferLen, "%" PRIu64, ThreadID);
433 Printf("%s at 0x%zx %s by thread %s here:\n", ErrorString, AccessPtr,
434 DescriptionBuffer, ThreadBuffer);
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");
442 if (Meta->IsDeallocated) {
443 if (Meta->DeallocationTrace.ThreadID ==
444 GuardedPoolAllocator::kInvalidThreadID)
445 Printf("0x%zx was deallocated by thread <unknown> here:\n", AccessPtr);
447 Printf("0x%zx was deallocated by thread %zu here:\n", AccessPtr,
448 Meta->DeallocationTrace.ThreadID);
450 uintptr_t UncompressedTrace[AllocationMetadata::kMaxTraceLengthToCollect];
451 size_t UncompressedLength = compression::unpack(
452 Meta->DeallocationTrace.CompressedTrace,
453 Meta->DeallocationTrace.TraceSize, UncompressedTrace,
454 AllocationMetadata::kMaxTraceLengthToCollect);
456 PrintBacktrace(UncompressedTrace, UncompressedLength, Printf);
459 if (Meta->AllocationTrace.ThreadID == GuardedPoolAllocator::kInvalidThreadID)
460 Printf("0x%zx was allocated by thread <unknown> here:\n", Meta->Addr);
462 Printf("0x%zx was allocated by thread %zu here:\n", Meta->Addr,
463 Meta->AllocationTrace.ThreadID);
465 uintptr_t UncompressedTrace[AllocationMetadata::kMaxTraceLengthToCollect];
466 size_t UncompressedLength = compression::unpack(
467 Meta->AllocationTrace.CompressedTrace, Meta->AllocationTrace.TraceSize,
468 UncompressedTrace, AllocationMetadata::kMaxTraceLengthToCollect);
470 PrintBacktrace(UncompressedTrace, UncompressedLength, Printf);
473 struct ScopedEndOfReportDecorator {
474 ScopedEndOfReportDecorator(options::Printf_t Printf) : Printf(Printf) {}
475 ~ScopedEndOfReportDecorator() { Printf("*** End GWP-ASan report ***\n"); }
476 options::Printf_t Printf;
478 } // anonymous namespace
480 void GuardedPoolAllocator::reportErrorInternal(uintptr_t AccessPtr, Error E) {
481 if (!pointerIsMine(reinterpret_cast<void *>(AccessPtr))) {
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.
489 ThreadLocals.RecursiveGuard = true;
491 Printf("*** GWP-ASan detected a memory error ***\n");
492 ScopedEndOfReportDecorator Decorator(Printf);
494 AllocationMetadata *Meta = nullptr;
496 if (E == Error::UNKNOWN) {
497 E = diagnoseUnknownError(AccessPtr, &Meta);
499 size_t Slot = getNearestSlot(AccessPtr);
500 Meta = addrToMetadata(slotToAddr(Slot));
501 // Ensure that this slot has been previously allocated.
506 // Print the error information.
507 uint64_t ThreadID = getThreadID();
508 printErrorType(E, AccessPtr, Meta, Printf, ThreadID);
510 static constexpr unsigned kMaximumStackFramesForCrashTrace = 512;
511 uintptr_t Trace[kMaximumStackFramesForCrashTrace];
512 size_t TraceLength = Backtrace(Trace, kMaximumStackFramesForCrashTrace);
514 PrintBacktrace(Trace, TraceLength, Printf);
516 Printf(" <unknown (does your allocator support backtracing?)>\n\n");
520 printAllocDeallocTraces(AccessPtr, Meta, Printf, PrintBacktrace);
523 GWP_ASAN_TLS_INITIAL_EXEC
524 GuardedPoolAllocator::ThreadLocalPackedVariables
525 GuardedPoolAllocator::ThreadLocals;
526 } // namespace gwp_asan