1//===-- sanitizer_allocator_primary64.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
16template<class SizeClassAllocator> struct SizeClassAllocator64LocalCache;
17
18// SizeClassAllocator64 -- allocator for 64-bit address space.
19// The template parameter Params is a class containing the actual parameters.
20//
21// Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg.
22// If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically by mmap.
23// Otherwise SpaceBeg=kSpaceBeg (fixed address).
24// kSpaceSize is a power of two.
25// At the beginning the entire space is mprotect-ed, then small parts of it
26// are mapped on demand.
27//
28// Region: a part of Space dedicated to a single size class.
29// There are kNumClasses Regions of equal size.
30//
31// UserChunk: a piece of memory returned to user.
32// MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk.
33
34// FreeArray is an array free-d chunks (stored as 4-byte offsets)
35//
36// A Region looks like this:
37// UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray
38
39struct SizeClassAllocator64FlagMasks { // Bit masks.
40 enum {
41 kRandomShuffleChunks = 1,
42 };
43};
44
45template <typename Allocator>
46class MemoryMapper {
47 public:
48 typedef typename Allocator::CompactPtrT CompactPtrT;
49
50 explicit MemoryMapper(const Allocator &allocator) : allocator_(allocator) {}
51
52 bool GetAndResetStats(uptr &ranges, uptr &bytes) {
53 ranges = released_ranges_count_;
54 released_ranges_count_ = 0;
55 bytes = released_bytes_;
56 released_bytes_ = 0;
57 return ranges != 0;
58 }
59
60 u64 *MapPackedCounterArrayBuffer(uptr count) {
61 buffer_.clear();
62 buffer_.resize(new_size: count);
63 return buffer_.data();
64 }
65
66 // Releases [from, to) range of pages back to OS.
67 void ReleasePageRangeToOS(uptr class_id, CompactPtrT from, CompactPtrT to) {
68 const uptr region_base = allocator_.GetRegionBeginBySizeClass(class_id);
69 const uptr from_page = allocator_.CompactPtrToPointer(region_base, from);
70 const uptr to_page = allocator_.CompactPtrToPointer(region_base, to);
71 ReleaseMemoryPagesToOS(beg: from_page, end: to_page);
72 released_ranges_count_++;
73 released_bytes_ += to_page - from_page;
74 }
75
76 private:
77 const Allocator &allocator_;
78 uptr released_ranges_count_ = 0;
79 uptr released_bytes_ = 0;
80 InternalMmapVector<u64> buffer_;
81};
82
83template <class Params>
84class SizeClassAllocator64 {
85 public:
86 using AddressSpaceView = typename Params::AddressSpaceView;
87 static const uptr kSpaceBeg = Params::kSpaceBeg;
88 static const uptr kSpaceSize = Params::kSpaceSize;
89 static const uptr kMetadataSize = Params::kMetadataSize;
90 typedef typename Params::SizeClassMap SizeClassMap;
91 typedef typename Params::MapUnmapCallback MapUnmapCallback;
92
93 static const bool kRandomShuffleChunks =
94 Params::kFlags & SizeClassAllocator64FlagMasks::kRandomShuffleChunks;
95
96 typedef SizeClassAllocator64<Params> ThisT;
97 typedef SizeClassAllocator64LocalCache<ThisT> AllocatorCache;
98 typedef MemoryMapper<ThisT> MemoryMapperT;
99
100 // When we know the size class (the region base) we can represent a pointer
101 // as a 4-byte integer (offset from the region start shifted right by 4).
102 typedef u32 CompactPtrT;
103 static const uptr kCompactPtrScale = 4;
104 CompactPtrT PointerToCompactPtr(uptr base, uptr ptr) const {
105 return static_cast<CompactPtrT>((ptr - base) >> kCompactPtrScale);
106 }
107 uptr CompactPtrToPointer(uptr base, CompactPtrT ptr32) const {
108 return base + (static_cast<uptr>(ptr32) << kCompactPtrScale);
109 }
110
111 // If heap_start is nonzero, assumes kSpaceSize bytes are already mapped R/W
112 // at heap_start and places the heap there. This mode requires kSpaceBeg ==
113 // ~(uptr)0.
114 void Init(s32 release_to_os_interval_ms, uptr heap_start = 0) {
115 uptr TotalSpaceSize = kSpaceSize + AdditionalSize();
116
117 uptr MaxAddr = GetMaxUserVirtualAddress();
118 // VReport does not call the sanitizer allocator.
119 VReport(3, "Max user virtual address: 0x%zx\n", MaxAddr);
120 VReport(3, "Total space size for primary allocator: 0x%zx\n",
121 TotalSpaceSize);
122 // TODO: revise the check if we ever configure sanitizers to deliberately
123 // map beyond the 2**48 barrier (note that Linux pretends the VMA is
124 // limited to 48-bit for backwards compatibility, but allows apps to
125 // explicitly specify an address beyond that).
126 if (heap_start + TotalSpaceSize >= MaxAddr) {
127 // We can't easily adjust the requested heap size, because kSpaceSize is
128 // const (for optimization) and used throughout the code.
129 VReport(0, "Error: heap size %zx exceeds max user virtual address %zx\n",
130 TotalSpaceSize, MaxAddr);
131 VReport(
132 0, "Try using a kernel that allows a larger virtual address space\n");
133 }
134 PremappedHeap = heap_start != 0;
135 if (PremappedHeap) {
136 CHECK(!kUsingConstantSpaceBeg);
137 NonConstSpaceBeg = heap_start;
138 uptr RegionInfoSize = AdditionalSize();
139 RegionInfoSpace =
140 address_range.Init(size: RegionInfoSize, name: PrimaryAllocatorName);
141 CHECK_NE(RegionInfoSpace, ~(uptr)0);
142 CHECK_EQ(RegionInfoSpace,
143 address_range.MapOrDie(RegionInfoSpace, RegionInfoSize,
144 "SizeClassAllocator: region info"));
145 MapUnmapCallback().OnMap(RegionInfoSpace, RegionInfoSize);
146 } else {
147 if (kUsingConstantSpaceBeg) {
148 CHECK(IsAligned(kSpaceBeg, SizeClassMap::kMaxSize));
149 CHECK_EQ(kSpaceBeg,
150 address_range.Init(TotalSpaceSize, PrimaryAllocatorName,
151 kSpaceBeg));
152 } else {
153 // Combined allocator expects that an 2^N allocation is always aligned
154 // to 2^N. For this to work, the start of the space needs to be aligned
155 // as high as the largest size class (which also needs to be a power of
156 // 2).
157 NonConstSpaceBeg = address_range.InitAligned(
158 size: TotalSpaceSize, align: SizeClassMap::kMaxSize, name: PrimaryAllocatorName);
159 CHECK_NE(NonConstSpaceBeg, ~(uptr)0);
160 }
161 RegionInfoSpace = SpaceEnd();
162 MapWithCallbackOrDie(beg: RegionInfoSpace, size: AdditionalSize(),
163 name: "SizeClassAllocator: region info");
164 }
165 SetReleaseToOSIntervalMs(release_to_os_interval_ms);
166 // Check that the RegionInfo array is aligned on the CacheLine size.
167 DCHECK_EQ(RegionInfoSpace % kCacheLineSize, 0);
168 }
169
170 s32 ReleaseToOSIntervalMs() const {
171 return atomic_load(a: &release_to_os_interval_ms_, mo: memory_order_relaxed);
172 }
173
174 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
175 atomic_store(a: &release_to_os_interval_ms_, v: release_to_os_interval_ms,
176 mo: memory_order_relaxed);
177 }
178
179 void ForceReleaseToOS() {
180 MemoryMapperT memory_mapper(*this);
181 for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
182 Lock l(&GetRegionInfo(class_id)->mutex);
183 MaybeReleaseToOS(memory_mapper: &memory_mapper, class_id, force: true /*force*/);
184 }
185 }
186
187 static bool CanAllocate(uptr size, uptr alignment) {
188 return size <= SizeClassMap::kMaxSize &&
189 alignment <= SizeClassMap::kMaxSize;
190 }
191
192 NOINLINE void ReturnToAllocator(MemoryMapperT *memory_mapper,
193 AllocatorStats *stat, uptr class_id,
194 const CompactPtrT *chunks, uptr n_chunks) {
195 RegionInfo *region = GetRegionInfo(class_id);
196 uptr region_beg = GetRegionBeginBySizeClass(class_id);
197 CompactPtrT *free_array = GetFreeArray(region_beg);
198
199 Lock l(&region->mutex);
200 uptr old_num_chunks = region->num_freed_chunks;
201 uptr new_num_freed_chunks = old_num_chunks + n_chunks;
202 // Failure to allocate free array space while releasing memory is non
203 // recoverable.
204 if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg,
205 new_num_freed_chunks))) {
206 Report(
207 format: "FATAL: Internal error: %s's allocator exhausted the free list "
208 "space for size class %zu (%zu bytes).\n",
209 SanitizerToolName, class_id, ClassIdToSize(class_id));
210 Die();
211 }
212 for (uptr i = 0; i < n_chunks; i++)
213 free_array[old_num_chunks + i] = chunks[i];
214 region->num_freed_chunks = new_num_freed_chunks;
215 region->stats.n_freed += n_chunks;
216
217 MaybeReleaseToOS(memory_mapper, class_id, force: false /*force*/);
218 }
219
220 NOINLINE bool GetFromAllocator(AllocatorStats *stat, uptr class_id,
221 CompactPtrT *chunks, uptr n_chunks) {
222 RegionInfo *region = GetRegionInfo(class_id);
223 uptr region_beg = GetRegionBeginBySizeClass(class_id);
224 CompactPtrT *free_array = GetFreeArray(region_beg);
225
226 Lock l(&region->mutex);
227#if SANITIZER_WINDOWS
228 /* On Windows unmapping of memory during __sanitizer_purge_allocator is
229 explicit and immediate, so unmapped regions must be explicitly mapped back
230 in when they are accessed again. */
231 if (region->rtoi.last_released_bytes > 0) {
232 MmapFixedOrDie(region_beg, region->mapped_user,
233 "SizeClassAllocator: region data");
234 region->rtoi.n_freed_at_last_release = 0;
235 region->rtoi.last_released_bytes = 0;
236 }
237#endif
238 if (UNLIKELY(region->num_freed_chunks < n_chunks)) {
239 if (UNLIKELY(!PopulateFreeArray(stat, class_id, region,
240 n_chunks - region->num_freed_chunks)))
241 return false;
242 CHECK_GE(region->num_freed_chunks, n_chunks);
243 }
244 region->num_freed_chunks -= n_chunks;
245 uptr base_idx = region->num_freed_chunks;
246 for (uptr i = 0; i < n_chunks; i++)
247 chunks[i] = free_array[base_idx + i];
248 region->stats.n_allocated += n_chunks;
249 return true;
250 }
251
252 bool PointerIsMine(const void *p) const {
253 uptr P = reinterpret_cast<uptr>(p);
254 if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)
255 return P / kSpaceSize == kSpaceBeg / kSpaceSize;
256 return P >= SpaceBeg() && P < SpaceEnd();
257 }
258
259 uptr GetRegionBegin(const void *p) {
260 if (kUsingConstantSpaceBeg)
261 return reinterpret_cast<uptr>(p) & ~(kRegionSize - 1);
262 uptr space_beg = SpaceBeg();
263 return ((reinterpret_cast<uptr>(p) - space_beg) & ~(kRegionSize - 1)) +
264 space_beg;
265 }
266
267 uptr GetRegionBeginBySizeClass(uptr class_id) const {
268 return SpaceBeg() + kRegionSize * class_id;
269 }
270
271 uptr GetSizeClass(const void *p) {
272 if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)
273 return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded;
274 return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) %
275 kNumClassesRounded;
276 }
277
278 void *GetBlockBegin(const void *p) {
279 uptr class_id = GetSizeClass(p);
280 if (class_id >= kNumClasses) return nullptr;
281 uptr size = ClassIdToSize(class_id);
282 if (!size) return nullptr;
283 uptr chunk_idx = GetChunkIdx(chunk: (uptr)p, size);
284 uptr reg_beg = GetRegionBegin(p);
285 uptr beg = chunk_idx * size;
286 uptr next_beg = beg + size;
287 const RegionInfo *region = AddressSpaceView::Load(GetRegionInfo(class_id));
288 if (region->mapped_user >= next_beg)
289 return reinterpret_cast<void*>(reg_beg + beg);
290 return nullptr;
291 }
292
293 uptr GetActuallyAllocatedSize(void *p) {
294 CHECK(PointerIsMine(p));
295 return ClassIdToSize(class_id: GetSizeClass(p));
296 }
297
298 static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
299
300 void *GetMetaData(const void *p) {
301 CHECK(kMetadataSize);
302 uptr class_id = GetSizeClass(p);
303 uptr size = ClassIdToSize(class_id);
304 if (!size)
305 return nullptr;
306 uptr chunk_idx = GetChunkIdx(chunk: reinterpret_cast<uptr>(p), size);
307 uptr region_beg = GetRegionBeginBySizeClass(class_id);
308 return reinterpret_cast<void *>(GetMetadataEnd(region_beg) -
309 (1 + chunk_idx) * kMetadataSize);
310 }
311
312 uptr TotalMemoryUsed() {
313 uptr res = 0;
314 for (uptr i = 0; i < kNumClasses; i++)
315 res += GetRegionInfo(class_id: i)->allocated_user;
316 return res;
317 }
318
319 // Test-only.
320 void TestOnlyUnmap() {
321 UnmapWithCallbackOrDie(beg: (uptr)address_range.base(), size: address_range.size());
322 }
323
324 static void FillMemoryProfile(uptr start, uptr rss, bool file, uptr *stats) {
325 for (uptr class_id = 0; class_id < kNumClasses; class_id++)
326 if (stats[class_id] == start)
327 stats[class_id] = rss;
328 }
329
330 void PrintStats(uptr class_id, uptr rss) {
331 RegionInfo *region = GetRegionInfo(class_id);
332 if (region->mapped_user == 0) return;
333 uptr in_use = region->stats.n_allocated - region->stats.n_freed;
334 uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id);
335 Printf(
336 "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd "
337 "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd "
338 "last released: %6lldK region: %p\n",
339 region->exhausted ? "F" : " ", class_id, ClassIdToSize(class_id),
340 region->mapped_user >> 10, region->stats.n_allocated,
341 region->stats.n_freed, in_use, region->num_freed_chunks, avail_chunks,
342 rss >> 10, region->rtoi.num_releases,
343 region->rtoi.last_released_bytes >> 10,
344 (void *)(SpaceBeg() + kRegionSize * class_id));
345 }
346
347 void PrintStats() {
348 uptr rss_stats[kNumClasses];
349 for (uptr class_id = 0; class_id < kNumClasses; class_id++)
350 rss_stats[class_id] = SpaceBeg() + kRegionSize * class_id;
351 GetMemoryProfile(FillMemoryProfile, rss_stats);
352
353 uptr total_mapped = 0;
354 uptr total_rss = 0;
355 uptr n_allocated = 0;
356 uptr n_freed = 0;
357 for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
358 RegionInfo *region = GetRegionInfo(class_id);
359 if (region->mapped_user != 0) {
360 total_mapped += region->mapped_user;
361 total_rss += rss_stats[class_id];
362 }
363 n_allocated += region->stats.n_allocated;
364 n_freed += region->stats.n_freed;
365 }
366
367 Printf(format: "Stats: SizeClassAllocator64: %zdM mapped (%zdM rss) in "
368 "%zd allocations; remains %zd\n", total_mapped >> 20,
369 total_rss >> 20, n_allocated, n_allocated - n_freed);
370 for (uptr class_id = 1; class_id < kNumClasses; class_id++)
371 PrintStats(class_id, rss_stats[class_id]);
372 }
373
374 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
375 // introspection API.
376 void ForceLock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS {
377 for (uptr i = 0; i < kNumClasses; i++) {
378 GetRegionInfo(class_id: i)->mutex.Lock();
379 }
380 }
381
382 void ForceUnlock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS {
383 for (int i = (int)kNumClasses - 1; i >= 0; i--) {
384 GetRegionInfo(class_id: i)->mutex.Unlock();
385 }
386 }
387
388 // Iterate over all existing chunks.
389 // The allocator must be locked when calling this function.
390 void ForEachChunk(ForEachChunkCallback callback, void *arg) {
391 for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
392 RegionInfo *region = GetRegionInfo(class_id);
393 uptr chunk_size = ClassIdToSize(class_id);
394 uptr region_beg = SpaceBeg() + class_id * kRegionSize;
395 uptr region_allocated_user_size =
396 AddressSpaceView::Load(region)->allocated_user;
397 for (uptr chunk = region_beg;
398 chunk < region_beg + region_allocated_user_size;
399 chunk += chunk_size) {
400 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
401 callback(chunk, arg);
402 }
403 }
404 }
405
406 static uptr ClassIdToSize(uptr class_id) {
407 return SizeClassMap::Size(class_id);
408 }
409
410 static uptr AdditionalSize() {
411 return RoundUpTo(size: sizeof(RegionInfo) * kNumClassesRounded,
412 boundary: GetPageSizeCached());
413 }
414
415 typedef SizeClassMap SizeClassMapT;
416 static const uptr kNumClasses = SizeClassMap::kNumClasses;
417 static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded;
418
419 // A packed array of counters. Each counter occupies 2^n bits, enough to store
420 // counter's max_value. Ctor will try to allocate the required buffer via
421 // mapper->MapPackedCounterArrayBuffer and the caller is expected to check
422 // whether the initialization was successful by checking IsAllocated() result.
423 // For the performance sake, none of the accessors check the validity of the
424 // arguments, it is assumed that index is always in [0, n) range and the value
425 // is not incremented past max_value.
426 class PackedCounterArray {
427 public:
428 template <typename MemoryMapper>
429 PackedCounterArray(u64 num_counters, u64 max_value, MemoryMapper *mapper)
430 : n(num_counters) {
431 CHECK_GT(num_counters, 0);
432 CHECK_GT(max_value, 0);
433 constexpr u64 kMaxCounterBits = sizeof(*buffer) * 8ULL;
434 // Rounding counter storage size up to the power of two allows for using
435 // bit shifts calculating particular counter's index and offset.
436 uptr counter_size_bits =
437 RoundUpToPowerOfTwo(size: MostSignificantSetBitIndex(x: max_value) + 1);
438 CHECK_LE(counter_size_bits, kMaxCounterBits);
439 counter_size_bits_log = Log2(x: counter_size_bits);
440 counter_mask = ~0ULL >> (kMaxCounterBits - counter_size_bits);
441
442 uptr packing_ratio = kMaxCounterBits >> counter_size_bits_log;
443 CHECK_GT(packing_ratio, 0);
444 packing_ratio_log = Log2(x: packing_ratio);
445 bit_offset_mask = packing_ratio - 1;
446
447 buffer = mapper->MapPackedCounterArrayBuffer(
448 RoundUpTo(size: n, boundary: 1ULL << packing_ratio_log) >> packing_ratio_log);
449 }
450
451 bool IsAllocated() const {
452 return !!buffer;
453 }
454
455 u64 GetCount() const {
456 return n;
457 }
458
459 uptr Get(uptr i) const {
460 DCHECK_LT(i, n);
461 uptr index = i >> packing_ratio_log;
462 uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log;
463 return (buffer[index] >> bit_offset) & counter_mask;
464 }
465
466 void Inc(uptr i) const {
467 DCHECK_LT(Get(i), counter_mask);
468 uptr index = i >> packing_ratio_log;
469 uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log;
470 buffer[index] += 1ULL << bit_offset;
471 }
472
473 void IncRange(uptr from, uptr to) const {
474 DCHECK_LE(from, to);
475 for (uptr i = from; i <= to; i++)
476 Inc(i);
477 }
478
479 private:
480 const u64 n;
481 u64 counter_size_bits_log;
482 u64 counter_mask;
483 u64 packing_ratio_log;
484 u64 bit_offset_mask;
485 u64* buffer;
486 };
487
488 template <class MemoryMapperT>
489 class FreePagesRangeTracker {
490 public:
491 FreePagesRangeTracker(MemoryMapperT *mapper, uptr class_id)
492 : memory_mapper(mapper),
493 class_id(class_id),
494 page_size_scaled_log(Log2(x: GetPageSizeCached() >> kCompactPtrScale)) {}
495
496 void NextPage(bool freed) {
497 if (freed) {
498 if (!in_the_range) {
499 current_range_start_page = current_page;
500 in_the_range = true;
501 }
502 } else {
503 CloseOpenedRange();
504 }
505 current_page++;
506 }
507
508 void Done() {
509 CloseOpenedRange();
510 }
511
512 private:
513 void CloseOpenedRange() {
514 if (in_the_range) {
515 memory_mapper->ReleasePageRangeToOS(
516 class_id, current_range_start_page << page_size_scaled_log,
517 current_page << page_size_scaled_log);
518 in_the_range = false;
519 }
520 }
521
522 MemoryMapperT *const memory_mapper = nullptr;
523 const uptr class_id = 0;
524 const uptr page_size_scaled_log = 0;
525 bool in_the_range = false;
526 uptr current_page = 0;
527 uptr current_range_start_page = 0;
528 };
529
530 // Iterates over the free_array to identify memory pages containing freed
531 // chunks only and returns these pages back to OS.
532 // allocated_pages_count is the total number of pages allocated for the
533 // current bucket.
534 template <typename MemoryMapper>
535 static void ReleaseFreeMemoryToOS(CompactPtrT *free_array,
536 uptr free_array_count, uptr chunk_size,
537 uptr allocated_pages_count,
538 MemoryMapper *memory_mapper,
539 uptr class_id) {
540 const uptr page_size = GetPageSizeCached();
541
542 // Figure out the number of chunks per page and whether we can take a fast
543 // path (the number of chunks per page is the same for all pages).
544 uptr full_pages_chunk_count_max;
545 bool same_chunk_count_per_page;
546 if (chunk_size <= page_size && page_size % chunk_size == 0) {
547 // Same number of chunks per page, no cross overs.
548 full_pages_chunk_count_max = page_size / chunk_size;
549 same_chunk_count_per_page = true;
550 } else if (chunk_size <= page_size && page_size % chunk_size != 0 &&
551 chunk_size % (page_size % chunk_size) == 0) {
552 // Some chunks are crossing page boundaries, which means that the page
553 // contains one or two partial chunks, but all pages contain the same
554 // number of chunks.
555 full_pages_chunk_count_max = page_size / chunk_size + 1;
556 same_chunk_count_per_page = true;
557 } else if (chunk_size <= page_size) {
558 // Some chunks are crossing page boundaries, which means that the page
559 // contains one or two partial chunks.
560 full_pages_chunk_count_max = page_size / chunk_size + 2;
561 same_chunk_count_per_page = false;
562 } else if (chunk_size > page_size && chunk_size % page_size == 0) {
563 // One chunk covers multiple pages, no cross overs.
564 full_pages_chunk_count_max = 1;
565 same_chunk_count_per_page = true;
566 } else if (chunk_size > page_size) {
567 // One chunk covers multiple pages, Some chunks are crossing page
568 // boundaries. Some pages contain one chunk, some contain two.
569 full_pages_chunk_count_max = 2;
570 same_chunk_count_per_page = false;
571 } else {
572 UNREACHABLE("All chunk_size/page_size ratios must be handled.");
573 }
574
575 PackedCounterArray counters(allocated_pages_count,
576 full_pages_chunk_count_max, memory_mapper);
577 if (!counters.IsAllocated())
578 return;
579
580 const uptr chunk_size_scaled = chunk_size >> kCompactPtrScale;
581 const uptr page_size_scaled = page_size >> kCompactPtrScale;
582 const uptr page_size_scaled_log = Log2(x: page_size_scaled);
583
584 // Iterate over free chunks and count how many free chunks affect each
585 // allocated page.
586 if (chunk_size <= page_size && page_size % chunk_size == 0) {
587 // Each chunk affects one page only.
588 for (uptr i = 0; i < free_array_count; i++)
589 counters.Inc(free_array[i] >> page_size_scaled_log);
590 } else {
591 // In all other cases chunks might affect more than one page.
592 for (uptr i = 0; i < free_array_count; i++) {
593 counters.IncRange(
594 free_array[i] >> page_size_scaled_log,
595 (free_array[i] + chunk_size_scaled - 1) >> page_size_scaled_log);
596 }
597 }
598
599 // Iterate over pages detecting ranges of pages with chunk counters equal
600 // to the expected number of chunks for the particular page.
601 FreePagesRangeTracker<MemoryMapper> range_tracker(memory_mapper, class_id);
602 if (same_chunk_count_per_page) {
603 // Fast path, every page has the same number of chunks affecting it.
604 for (uptr i = 0; i < counters.GetCount(); i++)
605 range_tracker.NextPage(counters.Get(i) == full_pages_chunk_count_max);
606 } else {
607 // Show path, go through the pages keeping count how many chunks affect
608 // each page.
609 const uptr pn =
610 chunk_size < page_size ? page_size_scaled / chunk_size_scaled : 1;
611 const uptr pnc = pn * chunk_size_scaled;
612 // The idea is to increment the current page pointer by the first chunk
613 // size, middle portion size (the portion of the page covered by chunks
614 // except the first and the last one) and then the last chunk size, adding
615 // up the number of chunks on the current page and checking on every step
616 // whether the page boundary was crossed.
617 uptr prev_page_boundary = 0;
618 uptr current_boundary = 0;
619 for (uptr i = 0; i < counters.GetCount(); i++) {
620 uptr page_boundary = prev_page_boundary + page_size_scaled;
621 uptr chunks_per_page = pn;
622 if (current_boundary < page_boundary) {
623 if (current_boundary > prev_page_boundary)
624 chunks_per_page++;
625 current_boundary += pnc;
626 if (current_boundary < page_boundary) {
627 chunks_per_page++;
628 current_boundary += chunk_size_scaled;
629 }
630 }
631 prev_page_boundary = page_boundary;
632
633 range_tracker.NextPage(counters.Get(i) == chunks_per_page);
634 }
635 }
636 range_tracker.Done();
637 }
638
639 private:
640 friend class MemoryMapper<ThisT>;
641
642 ReservedAddressRange address_range;
643
644 static const uptr kRegionSize = kSpaceSize / kNumClassesRounded;
645 // FreeArray is the array of free-d chunks (stored as 4-byte offsets).
646 // In the worst case it may require kRegionSize/SizeClassMap::kMinSize
647 // elements, but in reality this will not happen. For simplicity we
648 // dedicate 1/8 of the region's virtual space to FreeArray.
649 static const uptr kFreeArraySize = kRegionSize / 8;
650
651 static const bool kUsingConstantSpaceBeg = kSpaceBeg != ~(uptr)0;
652 uptr NonConstSpaceBeg;
653 uptr SpaceBeg() const {
654 return kUsingConstantSpaceBeg ? kSpaceBeg : NonConstSpaceBeg;
655 }
656 uptr SpaceEnd() const { return SpaceBeg() + kSpaceSize; }
657 // kRegionSize should be able to satisfy the largest size class.
658 static_assert(kRegionSize >= SizeClassMap::kMaxSize,
659 "Region size exceed largest size");
660 // kRegionSize must be <= 2^36, see CompactPtrT.
661 COMPILER_CHECK((kRegionSize) <=
662 (1ULL << (sizeof(CompactPtrT) * 8 + kCompactPtrScale)));
663 // Call mmap for user memory with at least this size.
664 static const uptr kUserMapSize = 1 << 18;
665 // Call mmap for metadata memory with at least this size.
666 static const uptr kMetaMapSize = 1 << 16;
667 // Call mmap for free array memory with at least this size.
668 static const uptr kFreeArrayMapSize = 1 << 18;
669
670 atomic_sint32_t release_to_os_interval_ms_;
671
672 uptr RegionInfoSpace;
673
674 // True if the user has already mapped the entire heap R/W.
675 bool PremappedHeap;
676
677 struct Stats {
678 uptr n_allocated;
679 uptr n_freed;
680 };
681
682 struct ReleaseToOsInfo {
683 uptr n_freed_at_last_release;
684 uptr num_releases;
685 u64 last_release_at_ns;
686 u64 last_released_bytes;
687 };
688
689 struct alignas(SANITIZER_CACHE_LINE_SIZE) RegionInfo {
690 Mutex mutex;
691 uptr num_freed_chunks; // Number of elements in the freearray.
692 uptr mapped_free_array; // Bytes mapped for freearray.
693 uptr allocated_user; // Bytes allocated for user memory.
694 uptr allocated_meta; // Bytes allocated for metadata.
695 uptr mapped_user; // Bytes mapped for user memory.
696 uptr mapped_meta; // Bytes mapped for metadata.
697 u32 rand_state; // Seed for random shuffle, used if kRandomShuffleChunks.
698 bool exhausted; // Whether region is out of space for new chunks.
699 Stats stats;
700 ReleaseToOsInfo rtoi;
701 };
702 COMPILER_CHECK(sizeof(RegionInfo) % kCacheLineSize == 0);
703
704 RegionInfo *GetRegionInfo(uptr class_id) const {
705 DCHECK_LT(class_id, kNumClasses);
706 RegionInfo *regions = reinterpret_cast<RegionInfo *>(RegionInfoSpace);
707 return &regions[class_id];
708 }
709
710 uptr GetMetadataEnd(uptr region_beg) const {
711 return region_beg + kRegionSize - kFreeArraySize;
712 }
713
714 uptr GetChunkIdx(uptr chunk, uptr size) const {
715 if (!kUsingConstantSpaceBeg)
716 chunk -= SpaceBeg();
717
718 uptr offset = chunk % kRegionSize;
719 // Here we divide by a non-constant. This is costly.
720 // size always fits into 32-bits. If the offset fits too, use 32-bit div.
721 if (offset >> (SANITIZER_WORDSIZE / 2))
722 return offset / size;
723 return (u32)offset / (u32)size;
724 }
725
726 CompactPtrT *GetFreeArray(uptr region_beg) const {
727 return reinterpret_cast<CompactPtrT *>(GetMetadataEnd(region_beg));
728 }
729
730 bool MapWithCallback(uptr beg, uptr size, const char *name) {
731 if (PremappedHeap)
732 return beg >= NonConstSpaceBeg &&
733 beg + size <= NonConstSpaceBeg + kSpaceSize;
734 uptr mapped = address_range.Map(fixed_addr: beg, size, name);
735 if (UNLIKELY(!mapped))
736 return false;
737 CHECK_EQ(beg, mapped);
738 MapUnmapCallback().OnMap(beg, size);
739 return true;
740 }
741
742 void MapWithCallbackOrDie(uptr beg, uptr size, const char *name) {
743 if (PremappedHeap) {
744 CHECK_GE(beg, NonConstSpaceBeg);
745 CHECK_LE(beg + size, NonConstSpaceBeg + kSpaceSize);
746 return;
747 }
748 CHECK_EQ(beg, address_range.MapOrDie(beg, size, name));
749 MapUnmapCallback().OnMap(beg, size);
750 }
751
752 void UnmapWithCallbackOrDie(uptr beg, uptr size) {
753 if (PremappedHeap)
754 return;
755 MapUnmapCallback().OnUnmap(beg, size);
756 address_range.Unmap(addr: beg, size);
757 }
758
759 bool EnsureFreeArraySpace(RegionInfo *region, uptr region_beg,
760 uptr num_freed_chunks) {
761 uptr needed_space = num_freed_chunks * sizeof(CompactPtrT);
762 if (region->mapped_free_array < needed_space) {
763 uptr new_mapped_free_array = RoundUpTo(size: needed_space, boundary: kFreeArrayMapSize);
764 CHECK_LE(new_mapped_free_array, kFreeArraySize);
765 uptr current_map_end = reinterpret_cast<uptr>(GetFreeArray(region_beg)) +
766 region->mapped_free_array;
767 uptr new_map_size = new_mapped_free_array - region->mapped_free_array;
768 if (UNLIKELY(!MapWithCallback(current_map_end, new_map_size,
769 "SizeClassAllocator: freearray")))
770 return false;
771 region->mapped_free_array = new_mapped_free_array;
772 }
773 return true;
774 }
775
776 // Check whether this size class is exhausted.
777 bool IsRegionExhausted(RegionInfo *region, uptr class_id,
778 uptr additional_map_size) {
779 if (LIKELY(region->mapped_user + region->mapped_meta +
780 additional_map_size <= kRegionSize - kFreeArraySize))
781 return false;
782 if (!region->exhausted) {
783 region->exhausted = true;
784 Printf(format: "%s: Out of memory. ", SanitizerToolName);
785 Printf(
786 format: "The process has exhausted %zu MB for size class %zu (%zu bytes).\n",
787 kRegionSize >> 20, class_id, ClassIdToSize(class_id));
788 }
789 return true;
790 }
791
792 NOINLINE bool PopulateFreeArray(AllocatorStats *stat, uptr class_id,
793 RegionInfo *region, uptr requested_count) {
794 // region->mutex is held.
795 const uptr region_beg = GetRegionBeginBySizeClass(class_id);
796 const uptr size = ClassIdToSize(class_id);
797
798 const uptr total_user_bytes =
799 region->allocated_user + requested_count * size;
800 // Map more space for chunks, if necessary.
801 if (LIKELY(total_user_bytes > region->mapped_user)) {
802 if (UNLIKELY(region->mapped_user == 0)) {
803 if (!kUsingConstantSpaceBeg && kRandomShuffleChunks)
804 // The random state is initialized from ASLR.
805 region->rand_state = static_cast<u32>(region_beg >> 12);
806 // Postpone the first release to OS attempt for ReleaseToOSIntervalMs,
807 // preventing just allocated memory from being released sooner than
808 // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls
809 // for short lived processes.
810 // Do it only when the feature is turned on, to avoid a potentially
811 // extraneous syscall.
812 if (ReleaseToOSIntervalMs() >= 0)
813 region->rtoi.last_release_at_ns = MonotonicNanoTime();
814 }
815 // Do the mmap for the user memory.
816 const uptr user_map_size =
817 RoundUpTo(total_user_bytes - region->mapped_user, kUserMapSize);
818 if (UNLIKELY(IsRegionExhausted(region, class_id, user_map_size)))
819 return false;
820 if (UNLIKELY(!MapWithCallback(region_beg + region->mapped_user,
821 user_map_size,
822 "SizeClassAllocator: region data")))
823 return false;
824 stat->Add(i: AllocatorStatMapped, v: user_map_size);
825 region->mapped_user += user_map_size;
826 }
827 const uptr new_chunks_count =
828 (region->mapped_user - region->allocated_user) / size;
829
830 if (kMetadataSize) {
831 // Calculate the required space for metadata.
832 const uptr total_meta_bytes =
833 region->allocated_meta + new_chunks_count * kMetadataSize;
834 const uptr meta_map_size = (total_meta_bytes > region->mapped_meta) ?
835 RoundUpTo(total_meta_bytes - region->mapped_meta, kMetaMapSize) : 0;
836 // Map more space for metadata, if necessary.
837 if (meta_map_size) {
838 if (UNLIKELY(IsRegionExhausted(region, class_id, meta_map_size)))
839 return false;
840 if (UNLIKELY(!MapWithCallback(
841 GetMetadataEnd(region_beg) - region->mapped_meta - meta_map_size,
842 meta_map_size, "SizeClassAllocator: region metadata")))
843 return false;
844 region->mapped_meta += meta_map_size;
845 }
846 }
847
848 // If necessary, allocate more space for the free array and populate it with
849 // newly allocated chunks.
850 const uptr total_freed_chunks = region->num_freed_chunks + new_chunks_count;
851 if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, total_freed_chunks)))
852 return false;
853 CompactPtrT *free_array = GetFreeArray(region_beg);
854 for (uptr i = 0, chunk = region->allocated_user; i < new_chunks_count;
855 i++, chunk += size)
856 free_array[total_freed_chunks - 1 - i] = PointerToCompactPtr(base: 0, ptr: chunk);
857 if (kRandomShuffleChunks)
858 RandomShuffle(&free_array[region->num_freed_chunks], new_chunks_count,
859 &region->rand_state);
860
861 // All necessary memory is mapped and now it is safe to advance all
862 // 'allocated_*' counters.
863 region->num_freed_chunks += new_chunks_count;
864 region->allocated_user += new_chunks_count * size;
865 CHECK_LE(region->allocated_user, region->mapped_user);
866 region->allocated_meta += new_chunks_count * kMetadataSize;
867 CHECK_LE(region->allocated_meta, region->mapped_meta);
868 region->exhausted = false;
869
870 // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent
871 // MaybeReleaseToOS from releasing just allocated pages or protect these
872 // not yet used chunks some other way.
873
874 return true;
875 }
876
877 // Attempts to release RAM occupied by freed chunks back to OS. The region is
878 // expected to be locked.
879 //
880 // TODO(morehouse): Support a callback on memory release so HWASan can release
881 // aliases as well.
882 void MaybeReleaseToOS(MemoryMapperT *memory_mapper, uptr class_id,
883 bool force) {
884 RegionInfo *region = GetRegionInfo(class_id);
885 const uptr chunk_size = ClassIdToSize(class_id);
886 const uptr page_size = GetPageSizeCached();
887
888 uptr n = region->num_freed_chunks;
889 if (n * chunk_size < page_size)
890 return; // No chance to release anything.
891 if ((region->stats.n_freed -
892 region->rtoi.n_freed_at_last_release) * chunk_size < page_size) {
893 return; // Nothing new to release.
894 }
895
896 if (!force) {
897 s32 interval_ms = ReleaseToOSIntervalMs();
898 if (interval_ms < 0)
899 return;
900
901 if (region->rtoi.last_release_at_ns + interval_ms * 1000000ULL >
902 MonotonicNanoTime()) {
903 return; // Memory was returned recently.
904 }
905 }
906
907 ReleaseFreeMemoryToOS(
908 GetFreeArray(region_beg: GetRegionBeginBySizeClass(class_id)), n, chunk_size,
909 RoundUpTo(region->allocated_user, page_size) / page_size, memory_mapper,
910 class_id);
911
912 uptr ranges, bytes;
913 if (memory_mapper->GetAndResetStats(ranges, bytes)) {
914 region->rtoi.n_freed_at_last_release = region->stats.n_freed;
915 region->rtoi.num_releases += ranges;
916 region->rtoi.last_released_bytes = bytes;
917 }
918 region->rtoi.last_release_at_ns = MonotonicNanoTime();
919 }
920};
921