1//===-- sanitizer_allocator_secondary.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// Part of the Sanitizer Allocator.
10//
11//===----------------------------------------------------------------------===//
12#ifndef SANITIZER_ALLOCATOR_H
13#error This file must be included inside sanitizer_allocator.h
14#endif
15
16// Fixed array to store LargeMmapAllocator chunks list, limited to 32K total
17// allocated chunks. To be used in memory constrained or not memory hungry cases
18// (currently, 32 bits and internal allocator).
19class LargeMmapAllocatorPtrArrayStatic {
20 public:
21 inline void *Init() { return &p_[0]; }
22 inline void EnsureSpace(uptr n) { CHECK_LT(n, kMaxNumChunks); }
23 private:
24 static const int kMaxNumChunks = 1 << 15;
25 uptr p_[kMaxNumChunks];
26};
27
28// Much less restricted LargeMmapAllocator chunks list (comparing to
29// PtrArrayStatic). Backed by mmaped memory region and can hold up to 1M chunks.
30// ReservedAddressRange was used instead of just MAP_NORESERVE to achieve the
31// same functionality in Fuchsia case, which does not support MAP_NORESERVE.
32class LargeMmapAllocatorPtrArrayDynamic {
33 public:
34 inline void *Init() {
35 uptr p = address_range_.Init(size: kMaxNumChunks * sizeof(uptr),
36 name: SecondaryAllocatorName);
37 CHECK(p);
38 return reinterpret_cast<void*>(p);
39 }
40
41 inline void EnsureSpace(uptr n) {
42 CHECK_LT(n, kMaxNumChunks);
43 DCHECK(n <= n_reserved_);
44 if (UNLIKELY(n == n_reserved_)) {
45 address_range_.MapOrDie(
46 fixed_addr: reinterpret_cast<uptr>(address_range_.base()) +
47 n_reserved_ * sizeof(uptr),
48 size: kChunksBlockCount * sizeof(uptr));
49 n_reserved_ += kChunksBlockCount;
50 }
51 }
52
53 private:
54 static const int kMaxNumChunks = 1 << 20;
55 static const int kChunksBlockCount = 1 << 14;
56 ReservedAddressRange address_range_;
57 uptr n_reserved_;
58};
59
60#if SANITIZER_WORDSIZE == 32
61typedef LargeMmapAllocatorPtrArrayStatic DefaultLargeMmapAllocatorPtrArray;
62#else
63typedef LargeMmapAllocatorPtrArrayDynamic DefaultLargeMmapAllocatorPtrArray;
64#endif
65
66// This class can (de)allocate only large chunks of memory using mmap/unmap.
67// The main purpose of this allocator is to cover large and rare allocation
68// sizes not covered by more efficient allocators (e.g. SizeClassAllocator64).
69template <class MapUnmapCallback = NoOpMapUnmapCallback,
70 class PtrArrayT = DefaultLargeMmapAllocatorPtrArray,
71 class AddressSpaceViewTy = LocalAddressSpaceView>
72class LargeMmapAllocator {
73 public:
74 using AddressSpaceView = AddressSpaceViewTy;
75 void InitLinkerInitialized() {
76 page_size_ = GetPageSizeCached();
77 chunks_ = reinterpret_cast<Header**>(ptr_array_.Init());
78 }
79
80 void Init() {
81 internal_memset(this, 0, sizeof(*this));
82 InitLinkerInitialized();
83 }
84
85 void *Allocate(AllocatorStats *stat, const uptr size, uptr alignment) {
86 CHECK(IsPowerOfTwo(alignment));
87 uptr map_size = RoundUpMapSize(size);
88 if (alignment > page_size_)
89 map_size += alignment;
90 // Overflow.
91 if (map_size < size) {
92 Report(format: "WARNING: %s: LargeMmapAllocator allocation overflow: "
93 "0x%zx bytes with 0x%zx alignment requested\n",
94 SanitizerToolName, map_size, alignment);
95 return nullptr;
96 }
97 uptr map_beg = reinterpret_cast<uptr>(
98 MmapOrDieOnFatalError(size: map_size, mem_type: SecondaryAllocatorName));
99 if (!map_beg)
100 return nullptr;
101 CHECK(IsAligned(map_beg, page_size_));
102 uptr map_end = map_beg + map_size;
103 uptr res = map_beg + page_size_;
104 if (res & (alignment - 1)) // Align.
105 res += alignment - (res & (alignment - 1));
106 MapUnmapCallback().OnMapSecondary(map_beg, map_size, res, size);
107 CHECK(IsAligned(res, alignment));
108 CHECK(IsAligned(res, page_size_));
109 CHECK_GE(res + size, map_beg);
110 CHECK_LE(res + size, map_end);
111 Header *h = GetHeader(res);
112 h->size = size;
113 h->map_beg = map_beg;
114 h->map_size = map_size;
115 uptr size_log = MostSignificantSetBitIndex(x: map_size);
116 CHECK_LT(size_log, ARRAY_SIZE(stats.by_size_log));
117 {
118 SpinMutexLock l(&mutex_);
119 ptr_array_.EnsureSpace(n_chunks_);
120 uptr idx = n_chunks_++;
121 h->chunk_idx = idx;
122 chunks_[idx] = h;
123 chunks_sorted_ = false;
124 stats.n_allocs++;
125 stats.currently_allocated += map_size;
126 stats.max_allocated = Max(stats.max_allocated, stats.currently_allocated);
127 stats.by_size_log[size_log]++;
128 stat->Add(i: AllocatorStatAllocated, v: map_size);
129 stat->Add(i: AllocatorStatMapped, v: map_size);
130 }
131 return reinterpret_cast<void*>(res);
132 }
133
134 void Deallocate(AllocatorStats *stat, void *p) {
135 Header *h = GetHeader(p);
136 {
137 SpinMutexLock l(&mutex_);
138 uptr idx = h->chunk_idx;
139 CHECK_EQ(chunks_[idx], h);
140 CHECK_LT(idx, n_chunks_);
141 chunks_[idx] = chunks_[--n_chunks_];
142 chunks_[idx]->chunk_idx = idx;
143 chunks_sorted_ = false;
144 stats.n_frees++;
145 stats.currently_allocated -= h->map_size;
146 stat->Sub(i: AllocatorStatAllocated, v: h->map_size);
147 stat->Sub(i: AllocatorStatMapped, v: h->map_size);
148 }
149 MapUnmapCallback().OnUnmap(h->map_beg, h->map_size);
150 UnmapOrDie(reinterpret_cast<void*>(h->map_beg), h->map_size);
151 }
152
153 uptr TotalMemoryUsed() {
154 SpinMutexLock l(&mutex_);
155 uptr res = 0;
156 for (uptr i = 0; i < n_chunks_; i++) {
157 Header *h = chunks_[i];
158 CHECK_EQ(h->chunk_idx, i);
159 res += RoundUpMapSize(size: h->size);
160 }
161 return res;
162 }
163
164 bool PointerIsMine(const void *p) const {
165 return GetBlockBegin(ptr: p) != nullptr;
166 }
167
168 uptr GetActuallyAllocatedSize(void *p) {
169 return RoundUpTo(GetHeader(p)->size, page_size_);
170 }
171
172 // At least page_size_/2 metadata bytes is available.
173 void *GetMetaData(const void *p) {
174 // Too slow: CHECK_EQ(p, GetBlockBegin(p));
175 if (!IsAligned(a: reinterpret_cast<uptr>(p), alignment: page_size_)) {
176 Printf(format: "%s: bad pointer %p\n", SanitizerToolName, p);
177 CHECK(IsAligned(reinterpret_cast<uptr>(p), page_size_));
178 }
179 return GetHeader(p) + 1;
180 }
181
182 void *GetBlockBegin(const void *ptr) const {
183 uptr p = reinterpret_cast<uptr>(ptr);
184 SpinMutexLock l(&mutex_);
185 uptr nearest_chunk = 0;
186 Header *const *chunks = AddressSpaceView::Load(chunks_, n_chunks_);
187 // Cache-friendly linear search.
188 for (uptr i = 0; i < n_chunks_; i++) {
189 uptr ch = reinterpret_cast<uptr>(chunks[i]);
190 if (p < ch) continue; // p is at left to this chunk, skip it.
191 if (p - ch < p - nearest_chunk)
192 nearest_chunk = ch;
193 }
194 if (!nearest_chunk)
195 return nullptr;
196 const Header *h =
197 AddressSpaceView::Load(reinterpret_cast<Header *>(nearest_chunk));
198 Header *h_ptr = reinterpret_cast<Header *>(nearest_chunk);
199 CHECK_GE(nearest_chunk, h->map_beg);
200 CHECK_LT(nearest_chunk, h->map_beg + h->map_size);
201 CHECK_LE(nearest_chunk, p);
202 if (h->map_beg + h->map_size <= p)
203 return nullptr;
204 return GetUser(h: h_ptr);
205 }
206
207 void EnsureSortedChunks() {
208 if (chunks_sorted_) return;
209 Header **chunks = AddressSpaceView::LoadWritable(chunks_, n_chunks_);
210 Sort(v: reinterpret_cast<uptr *>(chunks), size: n_chunks_);
211 for (uptr i = 0; i < n_chunks_; i++)
212 AddressSpaceView::LoadWritable(chunks[i])->chunk_idx = i;
213 chunks_sorted_ = true;
214 }
215
216 // This function does the same as GetBlockBegin, but is much faster.
217 // Must be called with the allocator locked.
218 void *GetBlockBeginFastLocked(const void *ptr) {
219 mutex_.CheckLocked();
220 uptr p = reinterpret_cast<uptr>(ptr);
221 uptr n = n_chunks_;
222 if (!n) return nullptr;
223 EnsureSortedChunks();
224 Header *const *chunks = AddressSpaceView::Load(chunks_, n_chunks_);
225 auto min_mmap_ = reinterpret_cast<uptr>(chunks[0]);
226 auto max_mmap_ = reinterpret_cast<uptr>(chunks[n - 1]) +
227 AddressSpaceView::Load(chunks[n - 1])->map_size;
228 if (p < min_mmap_ || p >= max_mmap_)
229 return nullptr;
230 uptr beg = 0, end = n - 1;
231 // This loop is a log(n) lower_bound. It does not check for the exact match
232 // to avoid expensive cache-thrashing loads.
233 while (end - beg >= 2) {
234 uptr mid = (beg + end) / 2; // Invariant: mid >= beg + 1
235 if (p < reinterpret_cast<uptr>(chunks[mid]))
236 end = mid - 1; // We are not interested in chunks[mid].
237 else
238 beg = mid; // chunks[mid] may still be what we want.
239 }
240
241 if (beg < end) {
242 CHECK_EQ(beg + 1, end);
243 // There are 2 chunks left, choose one.
244 if (p >= reinterpret_cast<uptr>(chunks[end]))
245 beg = end;
246 }
247
248 const Header *h = AddressSpaceView::Load(chunks[beg]);
249 Header *h_ptr = chunks[beg];
250 if (h->map_beg + h->map_size <= p || p < h->map_beg)
251 return nullptr;
252 return GetUser(h: h_ptr);
253 }
254
255 void PrintStats() {
256 Printf("Stats: LargeMmapAllocator: allocated %zd times, "
257 "remains %zd (%zd K) max %zd M; by size logs: ",
258 stats.n_allocs, stats.n_allocs - stats.n_frees,
259 stats.currently_allocated >> 10, stats.max_allocated >> 20);
260 for (uptr i = 0; i < ARRAY_SIZE(stats.by_size_log); i++) {
261 uptr c = stats.by_size_log[i];
262 if (!c) continue;
263 Printf(format: "%zd:%zd; ", i, c);
264 }
265 Printf(format: "\n");
266 }
267
268 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
269 // introspection API.
270 void ForceLock() SANITIZER_ACQUIRE(mutex_) { mutex_.Lock(); }
271
272 void ForceUnlock() SANITIZER_RELEASE(mutex_) { mutex_.Unlock(); }
273
274 // Iterate over all existing chunks.
275 // The allocator must be locked when calling this function.
276 void ForEachChunk(ForEachChunkCallback callback, void *arg) {
277 EnsureSortedChunks(); // Avoid doing the sort while iterating.
278 const Header *const *chunks = AddressSpaceView::Load(chunks_, n_chunks_);
279 for (uptr i = 0; i < n_chunks_; i++) {
280 const Header *t = chunks[i];
281 callback(reinterpret_cast<uptr>(GetUser(h: t)), arg);
282 // Consistency check: verify that the array did not change.
283 CHECK_EQ(chunks[i], t);
284 CHECK_EQ(AddressSpaceView::Load(chunks[i])->chunk_idx, i);
285 }
286 }
287
288 private:
289 struct Header {
290 uptr map_beg;
291 uptr map_size;
292 uptr size;
293 uptr chunk_idx;
294 };
295
296 Header *GetHeader(uptr p) {
297 CHECK(IsAligned(p, page_size_));
298 return reinterpret_cast<Header*>(p - page_size_);
299 }
300 Header *GetHeader(const void *p) {
301 return GetHeader(reinterpret_cast<uptr>(p));
302 }
303
304 void *GetUser(const Header *h) const {
305 CHECK(IsAligned((uptr)h, page_size_));
306 return reinterpret_cast<void*>(reinterpret_cast<uptr>(h) + page_size_);
307 }
308
309 uptr RoundUpMapSize(uptr size) {
310 return RoundUpTo(size, boundary: page_size_) + page_size_;
311 }
312
313 uptr page_size_;
314 Header **chunks_;
315 PtrArrayT ptr_array_;
316 uptr n_chunks_;
317 bool chunks_sorted_;
318 struct Stats {
319 uptr n_allocs, n_frees, currently_allocated, max_allocated, by_size_log[64];
320 } stats;
321 mutable StaticSpinMutex mutex_;
322};
323

source code of compiler-rt/lib/sanitizer_common/sanitizer_allocator_secondary.h