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/optional/segv_handler.h"
12 #include "gwp_asan/options.h"
13 #include "gwp_asan/utilities.h"
14 
15 // RHEL creates the PRIu64 format macro (for printing uint64_t's) only when this
16 // macro is defined before including <inttypes.h>.
17 #ifndef __STDC_FORMAT_MACROS
18 #define __STDC_FORMAT_MACROS 1
19 #endif
20 
21 #include <assert.h>
22 #include <inttypes.h>
23 #include <signal.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <time.h>
28 
29 using AllocationMetadata = gwp_asan::AllocationMetadata;
30 using Error = gwp_asan::Error;
31 
32 namespace gwp_asan {
33 namespace {
34 // Forward declare the pointer to the singleton version of this class.
35 // Instantiated during initialisation, this allows the signal handler
36 // to find this class in order to deduce the root cause of failures. Must not be
37 // referenced by users outside this translation unit, in order to avoid
38 // init-order-fiasco.
39 GuardedPoolAllocator *SingletonPtr = nullptr;
40 } // anonymous namespace
41 
42 // Gets the singleton implementation of this class. Thread-compatible until
43 // init() is called, thread-safe afterwards.
44 GuardedPoolAllocator *GuardedPoolAllocator::getSingleton() {
45   return SingletonPtr;
46 }
47 
48 static size_t roundUpTo(size_t Size, size_t Boundary) {
49   return (Size + Boundary - 1) & ~(Boundary - 1);
50 }
51 
52 void GuardedPoolAllocator::init(const options::Options &Opts) {
53   // Note: We return from the constructor here if GWP-ASan is not available.
54   // This will stop heap-allocation of class members, as well as mmap() of the
55   // guarded slots.
56   if (!Opts.Enabled || Opts.SampleRate == 0 ||
57       Opts.MaxSimultaneousAllocations == 0)
58     return;
59 
60   Check(Opts.SampleRate >= 0, "GWP-ASan Error: SampleRate is < 0.");
61   Check(Opts.SampleRate < (1 << 30), "GWP-ASan Error: SampleRate is >= 2^30.");
62   Check(Opts.MaxSimultaneousAllocations >= 0,
63         "GWP-ASan Error: MaxSimultaneousAllocations is < 0.");
64 
65   SingletonPtr = this;
66   Backtrace = Opts.Backtrace;
67 
68   State.MaxSimultaneousAllocations = Opts.MaxSimultaneousAllocations;
69 
70   const size_t PageSize = getPlatformPageSize();
71   // getPageAddr() and roundUpTo() assume the page size to be a power of 2.
72   assert((PageSize & (PageSize - 1)) == 0);
73   State.PageSize = PageSize;
74 
75   PerfectlyRightAlign = Opts.PerfectlyRightAlign;
76 
77   size_t PoolBytesRequired =
78       PageSize * (1 + State.MaxSimultaneousAllocations) +
79       State.MaxSimultaneousAllocations * State.maximumAllocationSize();
80   assert(PoolBytesRequired % PageSize == 0);
81   void *GuardedPoolMemory = reserveGuardedPool(PoolBytesRequired);
82 
83   size_t BytesRequired =
84       roundUpTo(State.MaxSimultaneousAllocations * sizeof(*Metadata), PageSize);
85   Metadata = reinterpret_cast<AllocationMetadata *>(
86       map(BytesRequired, kGwpAsanMetadataName));
87 
88   // Allocate memory and set up the free pages queue.
89   BytesRequired = roundUpTo(
90       State.MaxSimultaneousAllocations * sizeof(*FreeSlots), PageSize);
91   FreeSlots =
92       reinterpret_cast<size_t *>(map(BytesRequired, kGwpAsanFreeSlotsName));
93 
94   // Multiply the sample rate by 2 to give a good, fast approximation for (1 /
95   // SampleRate) chance of sampling.
96   if (Opts.SampleRate != 1)
97     AdjustedSampleRatePlusOne = static_cast<uint32_t>(Opts.SampleRate) * 2 + 1;
98   else
99     AdjustedSampleRatePlusOne = 2;
100 
101   initPRNG();
102   ThreadLocals.NextSampleCounter =
103       ((getRandomUnsigned32() % (AdjustedSampleRatePlusOne - 1)) + 1) &
104       ThreadLocalPackedVariables::NextSampleCounterMask;
105 
106   State.GuardedPagePool = reinterpret_cast<uintptr_t>(GuardedPoolMemory);
107   State.GuardedPagePoolEnd =
108       reinterpret_cast<uintptr_t>(GuardedPoolMemory) + PoolBytesRequired;
109 
110   if (Opts.InstallForkHandlers)
111     installAtFork();
112 }
113 
114 void GuardedPoolAllocator::disable() { PoolMutex.lock(); }
115 
116 void GuardedPoolAllocator::enable() { PoolMutex.unlock(); }
117 
118 void GuardedPoolAllocator::iterate(void *Base, size_t Size, iterate_callback Cb,
119                                    void *Arg) {
120   uintptr_t Start = reinterpret_cast<uintptr_t>(Base);
121   for (size_t i = 0; i < State.MaxSimultaneousAllocations; ++i) {
122     const AllocationMetadata &Meta = Metadata[i];
123     if (Meta.Addr && !Meta.IsDeallocated && Meta.Addr >= Start &&
124         Meta.Addr < Start + Size)
125       Cb(Meta.Addr, Meta.Size, Arg);
126   }
127 }
128 
129 void GuardedPoolAllocator::uninitTestOnly() {
130   if (State.GuardedPagePool) {
131     unreserveGuardedPool();
132     State.GuardedPagePool = 0;
133     State.GuardedPagePoolEnd = 0;
134   }
135   if (Metadata) {
136     unmap(Metadata,
137           roundUpTo(State.MaxSimultaneousAllocations * sizeof(*Metadata),
138                     State.PageSize));
139     Metadata = nullptr;
140   }
141   if (FreeSlots) {
142     unmap(FreeSlots,
143           roundUpTo(State.MaxSimultaneousAllocations * sizeof(*FreeSlots),
144                     State.PageSize));
145     FreeSlots = nullptr;
146   }
147 }
148 
149 static uintptr_t getPageAddr(uintptr_t Ptr, uintptr_t PageSize) {
150   return Ptr & ~(PageSize - 1);
151 }
152 
153 void *GuardedPoolAllocator::allocate(size_t Size) {
154   // GuardedPagePoolEnd == 0 when GWP-ASan is disabled. If we are disabled, fall
155   // back to the supporting allocator.
156   if (State.GuardedPagePoolEnd == 0) {
157     ThreadLocals.NextSampleCounter =
158         (AdjustedSampleRatePlusOne - 1) &
159         ThreadLocalPackedVariables::NextSampleCounterMask;
160     return nullptr;
161   }
162 
163   // Protect against recursivity.
164   if (ThreadLocals.RecursiveGuard)
165     return nullptr;
166   ScopedRecursiveGuard SRG;
167 
168   if (Size == 0 || Size > State.maximumAllocationSize())
169     return nullptr;
170 
171   size_t Index;
172   {
173     ScopedLock L(PoolMutex);
174     Index = reserveSlot();
175   }
176 
177   if (Index == kInvalidSlotID)
178     return nullptr;
179 
180   uintptr_t Ptr = State.slotToAddr(Index);
181   // Should we right-align this allocation?
182   if (getRandomUnsigned32() % 2 == 0) {
183     AlignmentStrategy Align = AlignmentStrategy::DEFAULT;
184     if (PerfectlyRightAlign)
185       Align = AlignmentStrategy::PERFECT;
186     Ptr +=
187         State.maximumAllocationSize() - rightAlignedAllocationSize(Size, Align);
188   }
189   AllocationMetadata *Meta = addrToMetadata(Ptr);
190 
191   // If a slot is multiple pages in size, and the allocation takes up a single
192   // page, we can improve overflow detection by leaving the unused pages as
193   // unmapped.
194   const size_t PageSize = State.PageSize;
195   allocateInGuardedPool(reinterpret_cast<void *>(getPageAddr(Ptr, PageSize)),
196                         roundUpTo(Size, PageSize));
197 
198   Meta->RecordAllocation(Ptr, Size);
199   Meta->AllocationTrace.RecordBacktrace(Backtrace);
200 
201   return reinterpret_cast<void *>(Ptr);
202 }
203 
204 void GuardedPoolAllocator::trapOnAddress(uintptr_t Address, Error E) {
205   State.FailureType = E;
206   State.FailureAddress = Address;
207 
208   // Raise a SEGV by touching first guard page.
209   volatile char *p = reinterpret_cast<char *>(State.GuardedPagePool);
210   *p = 0;
211   __builtin_unreachable();
212 }
213 
214 void GuardedPoolAllocator::stop() {
215   ThreadLocals.RecursiveGuard = true;
216   PoolMutex.tryLock();
217 }
218 
219 void GuardedPoolAllocator::deallocate(void *Ptr) {
220   assert(pointerIsMine(Ptr) && "Pointer is not mine!");
221   uintptr_t UPtr = reinterpret_cast<uintptr_t>(Ptr);
222   size_t Slot = State.getNearestSlot(UPtr);
223   uintptr_t SlotStart = State.slotToAddr(Slot);
224   AllocationMetadata *Meta = addrToMetadata(UPtr);
225   if (Meta->Addr != UPtr) {
226     // If multiple errors occur at the same time, use the first one.
227     ScopedLock L(PoolMutex);
228     trapOnAddress(UPtr, Error::INVALID_FREE);
229   }
230 
231   // Intentionally scope the mutex here, so that other threads can access the
232   // pool during the expensive markInaccessible() call.
233   {
234     ScopedLock L(PoolMutex);
235     if (Meta->IsDeallocated) {
236       trapOnAddress(UPtr, Error::DOUBLE_FREE);
237     }
238 
239     // Ensure that the deallocation is recorded before marking the page as
240     // inaccessible. Otherwise, a racy use-after-free will have inconsistent
241     // metadata.
242     Meta->RecordDeallocation();
243 
244     // Ensure that the unwinder is not called if the recursive flag is set,
245     // otherwise non-reentrant unwinders may deadlock.
246     if (!ThreadLocals.RecursiveGuard) {
247       ScopedRecursiveGuard SRG;
248       Meta->DeallocationTrace.RecordBacktrace(Backtrace);
249     }
250   }
251 
252   deallocateInGuardedPool(reinterpret_cast<void *>(SlotStart),
253                           State.maximumAllocationSize());
254 
255   // And finally, lock again to release the slot back into the pool.
256   ScopedLock L(PoolMutex);
257   freeSlot(Slot);
258 }
259 
260 size_t GuardedPoolAllocator::getSize(const void *Ptr) {
261   assert(pointerIsMine(Ptr));
262   ScopedLock L(PoolMutex);
263   AllocationMetadata *Meta = addrToMetadata(reinterpret_cast<uintptr_t>(Ptr));
264   assert(Meta->Addr == reinterpret_cast<uintptr_t>(Ptr));
265   return Meta->Size;
266 }
267 
268 AllocationMetadata *GuardedPoolAllocator::addrToMetadata(uintptr_t Ptr) const {
269   return &Metadata[State.getNearestSlot(Ptr)];
270 }
271 
272 size_t GuardedPoolAllocator::reserveSlot() {
273   // Avoid potential reuse of a slot before we have made at least a single
274   // allocation in each slot. Helps with our use-after-free detection.
275   if (NumSampledAllocations < State.MaxSimultaneousAllocations)
276     return NumSampledAllocations++;
277 
278   if (FreeSlotsLength == 0)
279     return kInvalidSlotID;
280 
281   size_t ReservedIndex = getRandomUnsigned32() % FreeSlotsLength;
282   size_t SlotIndex = FreeSlots[ReservedIndex];
283   FreeSlots[ReservedIndex] = FreeSlots[--FreeSlotsLength];
284   return SlotIndex;
285 }
286 
287 void GuardedPoolAllocator::freeSlot(size_t SlotIndex) {
288   assert(FreeSlotsLength < State.MaxSimultaneousAllocations);
289   FreeSlots[FreeSlotsLength++] = SlotIndex;
290 }
291 
292 uint32_t GuardedPoolAllocator::getRandomUnsigned32() {
293   uint32_t RandomState = ThreadLocals.RandomState;
294   RandomState ^= RandomState << 13;
295   RandomState ^= RandomState >> 17;
296   RandomState ^= RandomState << 5;
297   ThreadLocals.RandomState = RandomState;
298   return RandomState;
299 }
300 
301 GWP_ASAN_TLS_INITIAL_EXEC
302 GuardedPoolAllocator::ThreadLocalPackedVariables
303     GuardedPoolAllocator::ThreadLocals;
304 } // namespace gwp_asan
305