1//===-- guarded_pool_allocator.h --------------------------------*- 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#ifndef GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_
10#define GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_
11
12#include "gwp_asan/common.h"
13#include "gwp_asan/definitions.h"
14#include "gwp_asan/mutex.h"
15#include "gwp_asan/options.h"
16#include "gwp_asan/platform_specific/guarded_pool_allocator_fuchsia.h" // IWYU pragma: keep
17#include "gwp_asan/platform_specific/guarded_pool_allocator_posix.h" // IWYU pragma: keep
18#include "gwp_asan/platform_specific/guarded_pool_allocator_tls.h"
19
20#include <stddef.h>
21#include <stdint.h>
22// IWYU pragma: no_include <__stddef_max_align_t.h>
23// IWYU pragma: no_include <__stddef_null.h>
24// IWYU pragma: no_include <__stddef_nullptr_t.h>
25// IWYU pragma: no_include <__stddef_offsetof.h>
26// IWYU pragma: no_include <__stddef_ptrdiff_t.h>
27// IWYU pragma: no_include <__stddef_rsize_t.h>
28// IWYU pragma: no_include <__stddef_size_t.h>
29// IWYU pragma: no_include <__stddef_unreachable.h>
30// IWYU pragma: no_include <__stddef_wchar_t.h>
31// IWYU pragma: no_include <__stddef_wint_t.h>
32
33namespace gwp_asan {
34// This class is the primary implementation of the allocator portion of GWP-
35// ASan. It is the sole owner of the pool of sequentially allocated guarded
36// slots. It should always be treated as a singleton.
37
38// Functions in the public interface of this class are thread-compatible until
39// init() is called, at which point they become thread-safe (unless specified
40// otherwise).
41class GuardedPoolAllocator {
42public:
43 // Name of the GWP-ASan mapping that for `Metadata`.
44 static constexpr const char *kGwpAsanMetadataName = "GWP-ASan Metadata";
45
46 // During program startup, we must ensure that memory allocations do not land
47 // in this allocation pool if the allocator decides to runtime-disable
48 // GWP-ASan. The constructor value-initialises the class such that if no
49 // further initialisation takes place, calls to shouldSample() and
50 // pointerIsMine() will return false.
51 constexpr GuardedPoolAllocator() {}
52 GuardedPoolAllocator(const GuardedPoolAllocator &) = delete;
53 GuardedPoolAllocator &operator=(const GuardedPoolAllocator &) = delete;
54
55 // Note: This class is expected to be a singleton for the lifetime of the
56 // program. If this object is initialised, it will leak the guarded page pool
57 // and metadata allocations during destruction. We can't clean up these areas
58 // as this may cause a use-after-free on shutdown.
59 ~GuardedPoolAllocator() = default;
60
61 // Initialise the rest of the members of this class. Create the allocation
62 // pool using the provided options. See options.inc for runtime configuration
63 // options.
64 void init(const options::Options &Opts);
65 void uninitTestOnly();
66
67 // Functions exported for libmemunreachable's use on Android. disable()
68 // installs a lock in the allocator that prevents any thread from being able
69 // to allocate memory, until enable() is called.
70 void disable();
71 void enable();
72
73 typedef void (*iterate_callback)(uintptr_t base, size_t size, void *arg);
74 // Execute the callback Cb for every allocation the lies in [Base, Base +
75 // Size). Must be called while the allocator is disabled. The callback can not
76 // allocate.
77 void iterate(void *Base, size_t Size, iterate_callback Cb, void *Arg);
78
79 // Return whether the allocation should be randomly chosen for sampling.
80 GWP_ASAN_ALWAYS_INLINE bool shouldSample() {
81 // NextSampleCounter == 0 means we "should regenerate the counter".
82 // == 1 means we "should sample this allocation".
83 // AdjustedSampleRatePlusOne is designed to intentionally underflow. This
84 // class must be valid when zero-initialised, and we wish to sample as
85 // infrequently as possible when this is the case, hence we underflow to
86 // UINT32_MAX.
87 if (GWP_ASAN_UNLIKELY(getThreadLocals()->NextSampleCounter == 0))
88 getThreadLocals()->NextSampleCounter =
89 ((getRandomUnsigned32() % (AdjustedSampleRatePlusOne - 1)) + 1) &
90 ThreadLocalPackedVariables::NextSampleCounterMask;
91
92 return GWP_ASAN_UNLIKELY(--getThreadLocals()->NextSampleCounter == 0);
93 }
94
95 // Returns whether the provided pointer is a current sampled allocation that
96 // is owned by this pool.
97 GWP_ASAN_ALWAYS_INLINE bool pointerIsMine(const void *Ptr) const {
98 return State.pointerIsMine(Ptr);
99 }
100
101 // Allocate memory in a guarded slot, with the specified `Alignment`. Returns
102 // nullptr if the pool is empty, if the alignnment is not a power of two, or
103 // if the size/alignment makes the allocation too large for this pool to
104 // handle. By default, uses strong alignment (i.e. `max_align_t`), see
105 // http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2293.htm for discussion of
106 // alignment issues in the standard.
107 void *allocate(size_t Size, size_t Alignment = alignof(max_align_t));
108
109 // Deallocate memory in a guarded slot. The provided pointer must have been
110 // allocated using this pool. This will set the guarded slot as inaccessible.
111 void deallocate(void *Ptr);
112
113 // Returns the size of the allocation at Ptr.
114 size_t getSize(const void *Ptr);
115
116 // Returns a pointer to the Metadata region, or nullptr if it doesn't exist.
117 const AllocationMetadata *getMetadataRegion() const { return Metadata; }
118
119 // Returns a pointer to the AllocatorState region.
120 const AllocatorState *getAllocatorState() const { return &State; }
121
122 // Functions that the signal handler is responsible for calling, while
123 // providing the SEGV pointer, prior to dumping the crash, and after dumping
124 // the crash (in recoverable mode only).
125 void preCrashReport(void *Ptr);
126 void postCrashReportRecoverableOnly(void *Ptr);
127
128 // Exposed as protected for testing.
129protected:
130 // Returns the actual allocation size required to service an allocation with
131 // the provided Size and Alignment.
132 static size_t getRequiredBackingSize(size_t Size, size_t Alignment,
133 size_t PageSize);
134
135 // Returns the provided pointer that meets the specified alignment, depending
136 // on whether it's left or right aligned.
137 static uintptr_t alignUp(uintptr_t Ptr, size_t Alignment);
138 static uintptr_t alignDown(uintptr_t Ptr, size_t Alignment);
139
140private:
141 // Name of actively-occupied slot mappings.
142 static constexpr const char *kGwpAsanAliveSlotName = "GWP-ASan Alive Slot";
143 // Name of the guard pages. This includes all slots that are not actively in
144 // use (i.e. were never used, or have been free()'d).)
145 static constexpr const char *kGwpAsanGuardPageName = "GWP-ASan Guard Page";
146 // Name of the mapping for `FreeSlots`.
147 static constexpr const char *kGwpAsanFreeSlotsName = "GWP-ASan Metadata";
148
149 static constexpr size_t kInvalidSlotID = SIZE_MAX;
150
151 // These functions anonymously map memory or change the permissions of mapped
152 // memory into this process in a platform-specific way. Pointer and size
153 // arguments are expected to be page-aligned. These functions will never
154 // return on error, instead electing to kill the calling process on failure.
155 // The pool memory is initially reserved and inaccessible, and RW mappings are
156 // subsequently created and destroyed via allocateInGuardedPool() and
157 // deallocateInGuardedPool(). Each mapping is named on platforms that support
158 // it, primarily Android. This name must be a statically allocated string, as
159 // the Android kernel uses the string pointer directly.
160 void *map(size_t Size, const char *Name) const;
161 void unmap(void *Ptr, size_t Size) const;
162
163 // The pool is managed separately, as some platforms (particularly Fuchsia)
164 // manage virtual memory regions as a chunk where individual pages can still
165 // have separate permissions. These platforms maintain metadata about the
166 // region in order to perform operations. The pool is unique as it's the only
167 // thing in GWP-ASan that treats pages in a single VM region on an individual
168 // basis for page protection.
169 // The pointer returned by reserveGuardedPool() is the reserved address range
170 // of (at least) Size bytes.
171 void *reserveGuardedPool(size_t Size);
172 // allocateInGuardedPool() Ptr and Size must be a subrange of the previously
173 // reserved pool range.
174 void allocateInGuardedPool(void *Ptr, size_t Size) const;
175 // deallocateInGuardedPool() Ptr and Size must be an exact pair previously
176 // passed to allocateInGuardedPool().
177 void deallocateInGuardedPool(void *Ptr, size_t Size) const;
178 void unreserveGuardedPool();
179
180 // Get the page size from the platform-specific implementation. Only needs to
181 // be called once, and the result should be cached in PageSize in this class.
182 static size_t getPlatformPageSize();
183
184 // Returns a pointer to the metadata for the owned pointer. If the pointer is
185 // not owned by this pool, the result is undefined.
186 AllocationMetadata *addrToMetadata(uintptr_t Ptr) const;
187
188 // Reserve a slot for a new guarded allocation. Returns kInvalidSlotID if no
189 // slot is available to be reserved.
190 size_t reserveSlot();
191
192 // Unreserve the guarded slot.
193 void freeSlot(size_t SlotIndex);
194
195 // Raise a SEGV and set the corresponding fields in the Allocator's State in
196 // order to tell the crash handler what happened. Used when errors are
197 // detected internally (Double Free, Invalid Free).
198 void raiseInternallyDetectedError(uintptr_t Address, Error E);
199
200 static GuardedPoolAllocator *getSingleton();
201
202 // Install a pthread_atfork handler.
203 void installAtFork();
204
205 gwp_asan::AllocatorState State;
206
207 // A mutex to protect the guarded slot and metadata pool for this class.
208 Mutex PoolMutex;
209 // Some unwinders can grab the libdl lock. In order to provide atfork
210 // protection, we need to ensure that we allow an unwinding thread to release
211 // the libdl lock before forking.
212 Mutex BacktraceMutex;
213 // Record the number allocations that we've sampled. We store this amount so
214 // that we don't randomly choose to recycle a slot that previously had an
215 // allocation before all the slots have been utilised.
216 size_t NumSampledAllocations = 0;
217 // Pointer to the allocation metadata (allocation/deallocation stack traces),
218 // if any.
219 AllocationMetadata *Metadata = nullptr;
220
221 // Pointer to an array of free slot indexes.
222 size_t *FreeSlots = nullptr;
223 // The current length of the list of free slots.
224 size_t FreeSlotsLength = 0;
225
226 // See options.{h, inc} for more information.
227 bool PerfectlyRightAlign = false;
228
229 // Backtrace function provided by the supporting allocator. See `options.h`
230 // for more information.
231 options::Backtrace_t Backtrace = nullptr;
232
233 // The adjusted sample rate for allocation sampling. Default *must* be
234 // nonzero, as dynamic initialisation may call malloc (e.g. from libstdc++)
235 // before GPA::init() is called. This would cause an error in shouldSample(),
236 // where we would calculate modulo zero. This value is set UINT32_MAX, as when
237 // GWP-ASan is disabled, we wish to never spend wasted cycles recalculating
238 // the sample rate.
239 uint32_t AdjustedSampleRatePlusOne = 0;
240
241 // Additional platform specific data structure for the guarded pool mapping.
242 PlatformSpecificMapData GuardedPagePoolPlatformData = {};
243
244 class ScopedRecursiveGuard {
245 public:
246 ScopedRecursiveGuard() { getThreadLocals()->RecursiveGuard = true; }
247 ~ScopedRecursiveGuard() { getThreadLocals()->RecursiveGuard = false; }
248 };
249
250 // Initialise the PRNG, platform-specific.
251 void initPRNG();
252
253 // xorshift (32-bit output), extremely fast PRNG that uses arithmetic
254 // operations only. Seeded using platform-specific mechanisms by initPRNG().
255 uint32_t getRandomUnsigned32();
256};
257} // namespace gwp_asan
258
259#endif // GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_
260