1 //===-- sanitizer_allocator_primary64.h -------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Part of the Sanitizer Allocator.
12 //===----------------------------------------------------------------------===//
13 #ifndef SANITIZER_ALLOCATOR_H
14 #error This file must be included inside sanitizer_allocator.h
17 template<class SizeClassAllocator> struct SizeClassAllocator64LocalCache;
19 // SizeClassAllocator64 -- allocator for 64-bit address space.
20 // The template parameter Params is a class containing the actual parameters.
22 // Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg.
23 // If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically my mmap.
24 // Otherwise SpaceBeg=kSpaceBeg (fixed address).
25 // kSpaceSize is a power of two.
26 // At the beginning the entire space is mprotect-ed, then small parts of it
27 // are mapped on demand.
29 // Region: a part of Space dedicated to a single size class.
30 // There are kNumClasses Regions of equal size.
32 // UserChunk: a piece of memory returned to user.
33 // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk.
35 // FreeArray is an array free-d chunks (stored as 4-byte offsets)
37 // A Region looks like this:
38 // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray
40 struct SizeClassAllocator64FlagMasks { // Bit masks.
42 kRandomShuffleChunks = 1,
46 template <class Params>
47 class SizeClassAllocator64 {
49 using AddressSpaceView = typename Params::AddressSpaceView;
50 static const uptr kSpaceBeg = Params::kSpaceBeg;
51 static const uptr kSpaceSize = Params::kSpaceSize;
52 static const uptr kMetadataSize = Params::kMetadataSize;
53 typedef typename Params::SizeClassMap SizeClassMap;
54 typedef typename Params::MapUnmapCallback MapUnmapCallback;
56 static const bool kRandomShuffleChunks =
57 Params::kFlags & SizeClassAllocator64FlagMasks::kRandomShuffleChunks;
59 typedef SizeClassAllocator64<Params> ThisT;
60 typedef SizeClassAllocator64LocalCache<ThisT> AllocatorCache;
62 // When we know the size class (the region base) we can represent a pointer
63 // as a 4-byte integer (offset from the region start shifted right by 4).
64 typedef u32 CompactPtrT;
65 static const uptr kCompactPtrScale = 4;
66 CompactPtrT PointerToCompactPtr(uptr base, uptr ptr) const {
67 return static_cast<CompactPtrT>((ptr - base) >> kCompactPtrScale);
69 uptr CompactPtrToPointer(uptr base, CompactPtrT ptr32) const {
70 return base + (static_cast<uptr>(ptr32) << kCompactPtrScale);
73 void Init(s32 release_to_os_interval_ms) {
74 uptr TotalSpaceSize = kSpaceSize + AdditionalSize();
75 if (kUsingConstantSpaceBeg) {
76 CHECK_EQ(kSpaceBeg, address_range.Init(TotalSpaceSize,
77 PrimaryAllocatorName, kSpaceBeg));
79 NonConstSpaceBeg = address_range.Init(TotalSpaceSize,
80 PrimaryAllocatorName);
81 CHECK_NE(NonConstSpaceBeg, ~(uptr)0);
83 SetReleaseToOSIntervalMs(release_to_os_interval_ms);
84 MapWithCallbackOrDie(SpaceEnd(), AdditionalSize());
85 // Check that the RegionInfo array is aligned on the CacheLine size.
86 DCHECK_EQ(SpaceEnd() % kCacheLineSize, 0);
89 s32 ReleaseToOSIntervalMs() const {
90 return atomic_load(&release_to_os_interval_ms_, memory_order_relaxed);
93 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
94 atomic_store(&release_to_os_interval_ms_, release_to_os_interval_ms,
95 memory_order_relaxed);
98 void ForceReleaseToOS() {
99 for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
100 BlockingMutexLock l(&GetRegionInfo(class_id)->mutex);
101 MaybeReleaseToOS(class_id, true /*force*/);
105 static bool CanAllocate(uptr size, uptr alignment) {
106 return size <= SizeClassMap::kMaxSize &&
107 alignment <= SizeClassMap::kMaxSize;
110 NOINLINE void ReturnToAllocator(AllocatorStats *stat, uptr class_id,
111 const CompactPtrT *chunks, uptr n_chunks) {
112 RegionInfo *region = GetRegionInfo(class_id);
113 uptr region_beg = GetRegionBeginBySizeClass(class_id);
114 CompactPtrT *free_array = GetFreeArray(region_beg);
116 BlockingMutexLock l(®ion->mutex);
117 uptr old_num_chunks = region->num_freed_chunks;
118 uptr new_num_freed_chunks = old_num_chunks + n_chunks;
119 // Failure to allocate free array space while releasing memory is non
121 if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg,
122 new_num_freed_chunks))) {
123 Report("FATAL: Internal error: %s's allocator exhausted the free list "
124 "space for size class %zd (%zd bytes).\n", SanitizerToolName,
125 class_id, ClassIdToSize(class_id));
128 for (uptr i = 0; i < n_chunks; i++)
129 free_array[old_num_chunks + i] = chunks[i];
130 region->num_freed_chunks = new_num_freed_chunks;
131 region->stats.n_freed += n_chunks;
133 MaybeReleaseToOS(class_id, false /*force*/);
136 NOINLINE bool GetFromAllocator(AllocatorStats *stat, uptr class_id,
137 CompactPtrT *chunks, uptr n_chunks) {
138 RegionInfo *region = GetRegionInfo(class_id);
139 uptr region_beg = GetRegionBeginBySizeClass(class_id);
140 CompactPtrT *free_array = GetFreeArray(region_beg);
142 BlockingMutexLock l(®ion->mutex);
143 if (UNLIKELY(region->num_freed_chunks < n_chunks)) {
144 if (UNLIKELY(!PopulateFreeArray(stat, class_id, region,
145 n_chunks - region->num_freed_chunks)))
147 CHECK_GE(region->num_freed_chunks, n_chunks);
149 region->num_freed_chunks -= n_chunks;
150 uptr base_idx = region->num_freed_chunks;
151 for (uptr i = 0; i < n_chunks; i++)
152 chunks[i] = free_array[base_idx + i];
153 region->stats.n_allocated += n_chunks;
157 bool PointerIsMine(const void *p) {
158 uptr P = reinterpret_cast<uptr>(p);
159 if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)
160 return P / kSpaceSize == kSpaceBeg / kSpaceSize;
161 return P >= SpaceBeg() && P < SpaceEnd();
164 uptr GetRegionBegin(const void *p) {
165 if (kUsingConstantSpaceBeg)
166 return reinterpret_cast<uptr>(p) & ~(kRegionSize - 1);
167 uptr space_beg = SpaceBeg();
168 return ((reinterpret_cast<uptr>(p) - space_beg) & ~(kRegionSize - 1)) +
172 uptr GetRegionBeginBySizeClass(uptr class_id) const {
173 return SpaceBeg() + kRegionSize * class_id;
176 uptr GetSizeClass(const void *p) {
177 if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)
178 return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded;
179 return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) %
183 void *GetBlockBegin(const void *p) {
184 uptr class_id = GetSizeClass(p);
185 uptr size = ClassIdToSize(class_id);
186 if (!size) return nullptr;
187 uptr chunk_idx = GetChunkIdx((uptr)p, size);
188 uptr reg_beg = GetRegionBegin(p);
189 uptr beg = chunk_idx * size;
190 uptr next_beg = beg + size;
191 if (class_id >= kNumClasses) return nullptr;
192 RegionInfo *region = GetRegionInfo(class_id);
193 if (region->mapped_user >= next_beg)
194 return reinterpret_cast<void*>(reg_beg + beg);
198 uptr GetActuallyAllocatedSize(void *p) {
199 CHECK(PointerIsMine(p));
200 return ClassIdToSize(GetSizeClass(p));
203 uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
205 void *GetMetaData(const void *p) {
206 uptr class_id = GetSizeClass(p);
207 uptr size = ClassIdToSize(class_id);
208 uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size);
209 uptr region_beg = GetRegionBeginBySizeClass(class_id);
210 return reinterpret_cast<void *>(GetMetadataEnd(region_beg) -
211 (1 + chunk_idx) * kMetadataSize);
214 uptr TotalMemoryUsed() {
216 for (uptr i = 0; i < kNumClasses; i++)
217 res += GetRegionInfo(i)->allocated_user;
222 void TestOnlyUnmap() {
223 UnmapWithCallbackOrDie(SpaceBeg(), kSpaceSize + AdditionalSize());
226 static void FillMemoryProfile(uptr start, uptr rss, bool file, uptr *stats,
228 for (uptr class_id = 0; class_id < stats_size; class_id++)
229 if (stats[class_id] == start)
230 stats[class_id] = rss;
233 void PrintStats(uptr class_id, uptr rss) {
234 RegionInfo *region = GetRegionInfo(class_id);
235 if (region->mapped_user == 0) return;
236 uptr in_use = region->stats.n_allocated - region->stats.n_freed;
237 uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id);
239 "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd "
240 "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd "
241 "last released: %6zdK region: 0x%zx\n",
242 region->exhausted ? "F" : " ", class_id, ClassIdToSize(class_id),
243 region->mapped_user >> 10, region->stats.n_allocated,
244 region->stats.n_freed, in_use, region->num_freed_chunks, avail_chunks,
245 rss >> 10, region->rtoi.num_releases,
246 region->rtoi.last_released_bytes >> 10,
247 SpaceBeg() + kRegionSize * class_id);
251 uptr rss_stats[kNumClasses];
252 for (uptr class_id = 0; class_id < kNumClasses; class_id++)
253 rss_stats[class_id] = SpaceBeg() + kRegionSize * class_id;
254 GetMemoryProfile(FillMemoryProfile, rss_stats, kNumClasses);
256 uptr total_mapped = 0;
258 uptr n_allocated = 0;
260 for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
261 RegionInfo *region = GetRegionInfo(class_id);
262 if (region->mapped_user != 0) {
263 total_mapped += region->mapped_user;
264 total_rss += rss_stats[class_id];
266 n_allocated += region->stats.n_allocated;
267 n_freed += region->stats.n_freed;
270 Printf("Stats: SizeClassAllocator64: %zdM mapped (%zdM rss) in "
271 "%zd allocations; remains %zd\n", total_mapped >> 20,
272 total_rss >> 20, n_allocated, n_allocated - n_freed);
273 for (uptr class_id = 1; class_id < kNumClasses; class_id++)
274 PrintStats(class_id, rss_stats[class_id]);
277 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
278 // introspection API.
280 for (uptr i = 0; i < kNumClasses; i++) {
281 GetRegionInfo(i)->mutex.Lock();
286 for (int i = (int)kNumClasses - 1; i >= 0; i--) {
287 GetRegionInfo(i)->mutex.Unlock();
291 // Iterate over all existing chunks.
292 // The allocator must be locked when calling this function.
293 void ForEachChunk(ForEachChunkCallback callback, void *arg) {
294 for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
295 RegionInfo *region = GetRegionInfo(class_id);
296 uptr chunk_size = ClassIdToSize(class_id);
297 uptr region_beg = SpaceBeg() + class_id * kRegionSize;
298 uptr region_allocated_user_size =
299 AddressSpaceView::Load(region)->allocated_user;
300 for (uptr chunk = region_beg;
301 chunk < region_beg + region_allocated_user_size;
302 chunk += chunk_size) {
303 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
304 callback(chunk, arg);
309 static uptr ClassIdToSize(uptr class_id) {
310 return SizeClassMap::Size(class_id);
313 static uptr AdditionalSize() {
314 return RoundUpTo(sizeof(RegionInfo) * kNumClassesRounded,
315 GetPageSizeCached());
318 typedef SizeClassMap SizeClassMapT;
319 static const uptr kNumClasses = SizeClassMap::kNumClasses;
320 static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded;
322 // A packed array of counters. Each counter occupies 2^n bits, enough to store
323 // counter's max_value. Ctor will try to allocate the required buffer via
324 // mapper->MapPackedCounterArrayBuffer and the caller is expected to check
325 // whether the initialization was successful by checking IsAllocated() result.
326 // For the performance sake, none of the accessors check the validity of the
327 // arguments, it is assumed that index is always in [0, n) range and the value
328 // is not incremented past max_value.
329 template<class MemoryMapperT>
330 class PackedCounterArray {
332 PackedCounterArray(u64 num_counters, u64 max_value, MemoryMapperT *mapper)
333 : n(num_counters), memory_mapper(mapper) {
334 CHECK_GT(num_counters, 0);
335 CHECK_GT(max_value, 0);
336 constexpr u64 kMaxCounterBits = sizeof(*buffer) * 8ULL;
337 // Rounding counter storage size up to the power of two allows for using
338 // bit shifts calculating particular counter's index and offset.
339 uptr counter_size_bits =
340 RoundUpToPowerOfTwo(MostSignificantSetBitIndex(max_value) + 1);
341 CHECK_LE(counter_size_bits, kMaxCounterBits);
342 counter_size_bits_log = Log2(counter_size_bits);
343 counter_mask = ~0ULL >> (kMaxCounterBits - counter_size_bits);
345 uptr packing_ratio = kMaxCounterBits >> counter_size_bits_log;
346 CHECK_GT(packing_ratio, 0);
347 packing_ratio_log = Log2(packing_ratio);
348 bit_offset_mask = packing_ratio - 1;
351 (RoundUpTo(n, 1ULL << packing_ratio_log) >> packing_ratio_log) *
353 buffer = reinterpret_cast<u64*>(
354 memory_mapper->MapPackedCounterArrayBuffer(buffer_size));
356 ~PackedCounterArray() {
358 memory_mapper->UnmapPackedCounterArrayBuffer(
359 reinterpret_cast<uptr>(buffer), buffer_size);
363 bool IsAllocated() const {
367 u64 GetCount() const {
371 uptr Get(uptr i) const {
373 uptr index = i >> packing_ratio_log;
374 uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log;
375 return (buffer[index] >> bit_offset) & counter_mask;
378 void Inc(uptr i) const {
379 DCHECK_LT(Get(i), counter_mask);
380 uptr index = i >> packing_ratio_log;
381 uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log;
382 buffer[index] += 1ULL << bit_offset;
385 void IncRange(uptr from, uptr to) const {
387 for (uptr i = from; i <= to; i++)
393 u64 counter_size_bits_log;
395 u64 packing_ratio_log;
398 MemoryMapperT* const memory_mapper;
403 template<class MemoryMapperT>
404 class FreePagesRangeTracker {
406 explicit FreePagesRangeTracker(MemoryMapperT* mapper)
407 : memory_mapper(mapper),
408 page_size_scaled_log(Log2(GetPageSizeCached() >> kCompactPtrScale)),
409 in_the_range(false), current_page(0), current_range_start_page(0) {}
411 void NextPage(bool freed) {
414 current_range_start_page = current_page;
428 void CloseOpenedRange() {
430 memory_mapper->ReleasePageRangeToOS(
431 current_range_start_page << page_size_scaled_log,
432 current_page << page_size_scaled_log);
433 in_the_range = false;
437 MemoryMapperT* const memory_mapper;
438 const uptr page_size_scaled_log;
441 uptr current_range_start_page;
444 // Iterates over the free_array to identify memory pages containing freed
445 // chunks only and returns these pages back to OS.
446 // allocated_pages_count is the total number of pages allocated for the
448 template<class MemoryMapperT>
449 static void ReleaseFreeMemoryToOS(CompactPtrT *free_array,
450 uptr free_array_count, uptr chunk_size,
451 uptr allocated_pages_count,
452 MemoryMapperT *memory_mapper) {
453 const uptr page_size = GetPageSizeCached();
455 // Figure out the number of chunks per page and whether we can take a fast
456 // path (the number of chunks per page is the same for all pages).
457 uptr full_pages_chunk_count_max;
458 bool same_chunk_count_per_page;
459 if (chunk_size <= page_size && page_size % chunk_size == 0) {
460 // Same number of chunks per page, no cross overs.
461 full_pages_chunk_count_max = page_size / chunk_size;
462 same_chunk_count_per_page = true;
463 } else if (chunk_size <= page_size && page_size % chunk_size != 0 &&
464 chunk_size % (page_size % chunk_size) == 0) {
465 // Some chunks are crossing page boundaries, which means that the page
466 // contains one or two partial chunks, but all pages contain the same
468 full_pages_chunk_count_max = page_size / chunk_size + 1;
469 same_chunk_count_per_page = true;
470 } else if (chunk_size <= page_size) {
471 // Some chunks are crossing page boundaries, which means that the page
472 // contains one or two partial chunks.
473 full_pages_chunk_count_max = page_size / chunk_size + 2;
474 same_chunk_count_per_page = false;
475 } else if (chunk_size > page_size && chunk_size % page_size == 0) {
476 // One chunk covers multiple pages, no cross overs.
477 full_pages_chunk_count_max = 1;
478 same_chunk_count_per_page = true;
479 } else if (chunk_size > page_size) {
480 // One chunk covers multiple pages, Some chunks are crossing page
481 // boundaries. Some pages contain one chunk, some contain two.
482 full_pages_chunk_count_max = 2;
483 same_chunk_count_per_page = false;
485 UNREACHABLE("All chunk_size/page_size ratios must be handled.");
488 PackedCounterArray<MemoryMapperT> counters(allocated_pages_count,
489 full_pages_chunk_count_max,
491 if (!counters.IsAllocated())
494 const uptr chunk_size_scaled = chunk_size >> kCompactPtrScale;
495 const uptr page_size_scaled = page_size >> kCompactPtrScale;
496 const uptr page_size_scaled_log = Log2(page_size_scaled);
498 // Iterate over free chunks and count how many free chunks affect each
500 if (chunk_size <= page_size && page_size % chunk_size == 0) {
501 // Each chunk affects one page only.
502 for (uptr i = 0; i < free_array_count; i++)
503 counters.Inc(free_array[i] >> page_size_scaled_log);
505 // In all other cases chunks might affect more than one page.
506 for (uptr i = 0; i < free_array_count; i++) {
508 free_array[i] >> page_size_scaled_log,
509 (free_array[i] + chunk_size_scaled - 1) >> page_size_scaled_log);
513 // Iterate over pages detecting ranges of pages with chunk counters equal
514 // to the expected number of chunks for the particular page.
515 FreePagesRangeTracker<MemoryMapperT> range_tracker(memory_mapper);
516 if (same_chunk_count_per_page) {
517 // Fast path, every page has the same number of chunks affecting it.
518 for (uptr i = 0; i < counters.GetCount(); i++)
519 range_tracker.NextPage(counters.Get(i) == full_pages_chunk_count_max);
521 // Show path, go through the pages keeping count how many chunks affect
524 chunk_size < page_size ? page_size_scaled / chunk_size_scaled : 1;
525 const uptr pnc = pn * chunk_size_scaled;
526 // The idea is to increment the current page pointer by the first chunk
527 // size, middle portion size (the portion of the page covered by chunks
528 // except the first and the last one) and then the last chunk size, adding
529 // up the number of chunks on the current page and checking on every step
530 // whether the page boundary was crossed.
531 uptr prev_page_boundary = 0;
532 uptr current_boundary = 0;
533 for (uptr i = 0; i < counters.GetCount(); i++) {
534 uptr page_boundary = prev_page_boundary + page_size_scaled;
535 uptr chunks_per_page = pn;
536 if (current_boundary < page_boundary) {
537 if (current_boundary > prev_page_boundary)
539 current_boundary += pnc;
540 if (current_boundary < page_boundary) {
542 current_boundary += chunk_size_scaled;
545 prev_page_boundary = page_boundary;
547 range_tracker.NextPage(counters.Get(i) == chunks_per_page);
550 range_tracker.Done();
554 friend class MemoryMapper;
556 ReservedAddressRange address_range;
558 static const uptr kRegionSize = kSpaceSize / kNumClassesRounded;
559 // FreeArray is the array of free-d chunks (stored as 4-byte offsets).
560 // In the worst case it may reguire kRegionSize/SizeClassMap::kMinSize
561 // elements, but in reality this will not happen. For simplicity we
562 // dedicate 1/8 of the region's virtual space to FreeArray.
563 static const uptr kFreeArraySize = kRegionSize / 8;
565 static const bool kUsingConstantSpaceBeg = kSpaceBeg != ~(uptr)0;
566 uptr NonConstSpaceBeg;
567 uptr SpaceBeg() const {
568 return kUsingConstantSpaceBeg ? kSpaceBeg : NonConstSpaceBeg;
570 uptr SpaceEnd() const { return SpaceBeg() + kSpaceSize; }
571 // kRegionSize must be >= 2^32.
572 COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2)));
573 // kRegionSize must be <= 2^36, see CompactPtrT.
574 COMPILER_CHECK((kRegionSize) <= (1ULL << (SANITIZER_WORDSIZE / 2 + 4)));
575 // Call mmap for user memory with at least this size.
576 static const uptr kUserMapSize = 1 << 16;
577 // Call mmap for metadata memory with at least this size.
578 static const uptr kMetaMapSize = 1 << 16;
579 // Call mmap for free array memory with at least this size.
580 static const uptr kFreeArrayMapSize = 1 << 16;
582 atomic_sint32_t release_to_os_interval_ms_;
589 struct ReleaseToOsInfo {
590 uptr n_freed_at_last_release;
592 u64 last_release_at_ns;
593 u64 last_released_bytes;
596 struct ALIGNED(SANITIZER_CACHE_LINE_SIZE) RegionInfo {
598 uptr num_freed_chunks; // Number of elements in the freearray.
599 uptr mapped_free_array; // Bytes mapped for freearray.
600 uptr allocated_user; // Bytes allocated for user memory.
601 uptr allocated_meta; // Bytes allocated for metadata.
602 uptr mapped_user; // Bytes mapped for user memory.
603 uptr mapped_meta; // Bytes mapped for metadata.
604 u32 rand_state; // Seed for random shuffle, used if kRandomShuffleChunks.
605 bool exhausted; // Whether region is out of space for new chunks.
607 ReleaseToOsInfo rtoi;
609 COMPILER_CHECK(sizeof(RegionInfo) % kCacheLineSize == 0);
611 RegionInfo *GetRegionInfo(uptr class_id) const {
612 DCHECK_LT(class_id, kNumClasses);
613 RegionInfo *regions = reinterpret_cast<RegionInfo *>(SpaceEnd());
614 return ®ions[class_id];
617 uptr GetMetadataEnd(uptr region_beg) const {
618 return region_beg + kRegionSize - kFreeArraySize;
621 uptr GetChunkIdx(uptr chunk, uptr size) const {
622 if (!kUsingConstantSpaceBeg)
625 uptr offset = chunk % kRegionSize;
626 // Here we divide by a non-constant. This is costly.
627 // size always fits into 32-bits. If the offset fits too, use 32-bit div.
628 if (offset >> (SANITIZER_WORDSIZE / 2))
629 return offset / size;
630 return (u32)offset / (u32)size;
633 CompactPtrT *GetFreeArray(uptr region_beg) const {
634 return reinterpret_cast<CompactPtrT *>(GetMetadataEnd(region_beg));
637 bool MapWithCallback(uptr beg, uptr size) {
638 uptr mapped = address_range.Map(beg, size);
639 if (UNLIKELY(!mapped))
641 CHECK_EQ(beg, mapped);
642 MapUnmapCallback().OnMap(beg, size);
646 void MapWithCallbackOrDie(uptr beg, uptr size) {
647 CHECK_EQ(beg, address_range.MapOrDie(beg, size));
648 MapUnmapCallback().OnMap(beg, size);
651 void UnmapWithCallbackOrDie(uptr beg, uptr size) {
652 MapUnmapCallback().OnUnmap(beg, size);
653 address_range.Unmap(beg, size);
656 bool EnsureFreeArraySpace(RegionInfo *region, uptr region_beg,
657 uptr num_freed_chunks) {
658 uptr needed_space = num_freed_chunks * sizeof(CompactPtrT);
659 if (region->mapped_free_array < needed_space) {
660 uptr new_mapped_free_array = RoundUpTo(needed_space, kFreeArrayMapSize);
661 CHECK_LE(new_mapped_free_array, kFreeArraySize);
662 uptr current_map_end = reinterpret_cast<uptr>(GetFreeArray(region_beg)) +
663 region->mapped_free_array;
664 uptr new_map_size = new_mapped_free_array - region->mapped_free_array;
665 if (UNLIKELY(!MapWithCallback(current_map_end, new_map_size)))
667 region->mapped_free_array = new_mapped_free_array;
672 // Check whether this size class is exhausted.
673 bool IsRegionExhausted(RegionInfo *region, uptr class_id,
674 uptr additional_map_size) {
675 if (LIKELY(region->mapped_user + region->mapped_meta +
676 additional_map_size <= kRegionSize - kFreeArraySize))
678 if (!region->exhausted) {
679 region->exhausted = true;
680 Printf("%s: Out of memory. ", SanitizerToolName);
681 Printf("The process has exhausted %zuMB for size class %zu.\n",
682 kRegionSize >> 20, ClassIdToSize(class_id));
687 NOINLINE bool PopulateFreeArray(AllocatorStats *stat, uptr class_id,
688 RegionInfo *region, uptr requested_count) {
689 // region->mutex is held.
690 const uptr region_beg = GetRegionBeginBySizeClass(class_id);
691 const uptr size = ClassIdToSize(class_id);
693 const uptr total_user_bytes =
694 region->allocated_user + requested_count * size;
695 // Map more space for chunks, if necessary.
696 if (LIKELY(total_user_bytes > region->mapped_user)) {
697 if (UNLIKELY(region->mapped_user == 0)) {
698 if (!kUsingConstantSpaceBeg && kRandomShuffleChunks)
699 // The random state is initialized from ASLR.
700 region->rand_state = static_cast<u32>(region_beg >> 12);
701 // Postpone the first release to OS attempt for ReleaseToOSIntervalMs,
702 // preventing just allocated memory from being released sooner than
703 // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls
704 // for short lived processes.
705 // Do it only when the feature is turned on, to avoid a potentially
706 // extraneous syscall.
707 if (ReleaseToOSIntervalMs() >= 0)
708 region->rtoi.last_release_at_ns = MonotonicNanoTime();
710 // Do the mmap for the user memory.
711 const uptr user_map_size =
712 RoundUpTo(total_user_bytes - region->mapped_user, kUserMapSize);
713 if (UNLIKELY(IsRegionExhausted(region, class_id, user_map_size)))
715 if (UNLIKELY(!MapWithCallback(region_beg + region->mapped_user,
718 stat->Add(AllocatorStatMapped, user_map_size);
719 region->mapped_user += user_map_size;
721 const uptr new_chunks_count =
722 (region->mapped_user - region->allocated_user) / size;
725 // Calculate the required space for metadata.
726 const uptr total_meta_bytes =
727 region->allocated_meta + new_chunks_count * kMetadataSize;
728 const uptr meta_map_size = (total_meta_bytes > region->mapped_meta) ?
729 RoundUpTo(total_meta_bytes - region->mapped_meta, kMetaMapSize) : 0;
730 // Map more space for metadata, if necessary.
732 if (UNLIKELY(IsRegionExhausted(region, class_id, meta_map_size)))
734 if (UNLIKELY(!MapWithCallback(
735 GetMetadataEnd(region_beg) - region->mapped_meta - meta_map_size,
738 region->mapped_meta += meta_map_size;
742 // If necessary, allocate more space for the free array and populate it with
743 // newly allocated chunks.
744 const uptr total_freed_chunks = region->num_freed_chunks + new_chunks_count;
745 if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, total_freed_chunks)))
747 CompactPtrT *free_array = GetFreeArray(region_beg);
748 for (uptr i = 0, chunk = region->allocated_user; i < new_chunks_count;
750 free_array[total_freed_chunks - 1 - i] = PointerToCompactPtr(0, chunk);
751 if (kRandomShuffleChunks)
752 RandomShuffle(&free_array[region->num_freed_chunks], new_chunks_count,
753 ®ion->rand_state);
755 // All necessary memory is mapped and now it is safe to advance all
756 // 'allocated_*' counters.
757 region->num_freed_chunks += new_chunks_count;
758 region->allocated_user += new_chunks_count * size;
759 CHECK_LE(region->allocated_user, region->mapped_user);
760 region->allocated_meta += new_chunks_count * kMetadataSize;
761 CHECK_LE(region->allocated_meta, region->mapped_meta);
762 region->exhausted = false;
764 // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent
765 // MaybeReleaseToOS from releasing just allocated pages or protect these
766 // not yet used chunks some other way.
773 MemoryMapper(const ThisT& base_allocator, uptr class_id)
774 : allocator(base_allocator),
775 region_base(base_allocator.GetRegionBeginBySizeClass(class_id)),
776 released_ranges_count(0),
780 uptr GetReleasedRangesCount() const {
781 return released_ranges_count;
784 uptr GetReleasedBytes() const {
785 return released_bytes;
788 uptr MapPackedCounterArrayBuffer(uptr buffer_size) {
789 // TODO(alekseyshl): The idea to explore is to check if we have enough
790 // space between num_freed_chunks*sizeof(CompactPtrT) and
791 // mapped_free_array to fit buffer_size bytes and use that space instead
792 // of mapping a temporary one.
793 return reinterpret_cast<uptr>(
794 MmapOrDieOnFatalError(buffer_size, "ReleaseToOSPageCounters"));
797 void UnmapPackedCounterArrayBuffer(uptr buffer, uptr buffer_size) {
798 UnmapOrDie(reinterpret_cast<void *>(buffer), buffer_size);
801 // Releases [from, to) range of pages back to OS.
802 void ReleasePageRangeToOS(CompactPtrT from, CompactPtrT to) {
803 const uptr from_page = allocator.CompactPtrToPointer(region_base, from);
804 const uptr to_page = allocator.CompactPtrToPointer(region_base, to);
805 ReleaseMemoryPagesToOS(from_page, to_page);
806 released_ranges_count++;
807 released_bytes += to_page - from_page;
811 const ThisT& allocator;
812 const uptr region_base;
813 uptr released_ranges_count;
817 // Attempts to release RAM occupied by freed chunks back to OS. The region is
818 // expected to be locked.
819 void MaybeReleaseToOS(uptr class_id, bool force) {
820 RegionInfo *region = GetRegionInfo(class_id);
821 const uptr chunk_size = ClassIdToSize(class_id);
822 const uptr page_size = GetPageSizeCached();
824 uptr n = region->num_freed_chunks;
825 if (n * chunk_size < page_size)
826 return; // No chance to release anything.
827 if ((region->stats.n_freed -
828 region->rtoi.n_freed_at_last_release) * chunk_size < page_size) {
829 return; // Nothing new to release.
833 s32 interval_ms = ReleaseToOSIntervalMs();
837 if (region->rtoi.last_release_at_ns + interval_ms * 1000000ULL >
838 MonotonicNanoTime()) {
839 return; // Memory was returned recently.
843 MemoryMapper memory_mapper(*this, class_id);
845 ReleaseFreeMemoryToOS<MemoryMapper>(
846 GetFreeArray(GetRegionBeginBySizeClass(class_id)), n, chunk_size,
847 RoundUpTo(region->allocated_user, page_size) / page_size,
850 if (memory_mapper.GetReleasedRangesCount() > 0) {
851 region->rtoi.n_freed_at_last_release = region->stats.n_freed;
852 region->rtoi.num_releases += memory_mapper.GetReleasedRangesCount();
853 region->rtoi.last_released_bytes = memory_mapper.GetReleasedBytes();
855 region->rtoi.last_release_at_ns = MonotonicNanoTime();