1 //===-- sanitizer_allocator_primary64.h -------------------------*- C++ -*-===//
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
6 //===----------------------------------------------------------------------===//
8 // Part of the Sanitizer Allocator.
10 //===----------------------------------------------------------------------===//
11 #ifndef SANITIZER_ALLOCATOR_H
12 #error This file must be included inside sanitizer_allocator.h
15 template<class SizeClassAllocator
> struct SizeClassAllocator64LocalCache
;
17 // SizeClassAllocator64 -- allocator for 64-bit address space.
18 // The template parameter Params is a class containing the actual parameters.
20 // Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg.
21 // If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically my mmap.
22 // Otherwise SpaceBeg=kSpaceBeg (fixed address).
23 // kSpaceSize is a power of two.
24 // At the beginning the entire space is mprotect-ed, then small parts of it
25 // are mapped on demand.
27 // Region: a part of Space dedicated to a single size class.
28 // There are kNumClasses Regions of equal size.
30 // UserChunk: a piece of memory returned to user.
31 // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk.
33 // FreeArray is an array free-d chunks (stored as 4-byte offsets)
35 // A Region looks like this:
36 // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray
38 struct SizeClassAllocator64FlagMasks
{ // Bit masks.
40 kRandomShuffleChunks
= 1,
44 template <class Params
>
45 class SizeClassAllocator64
{
47 static const uptr kSpaceBeg
= Params::kSpaceBeg
;
48 static const uptr kSpaceSize
= Params::kSpaceSize
;
49 static const uptr kMetadataSize
= Params::kMetadataSize
;
50 typedef typename
Params::SizeClassMap SizeClassMap
;
51 typedef typename
Params::MapUnmapCallback MapUnmapCallback
;
53 static const bool kRandomShuffleChunks
=
54 Params::kFlags
& SizeClassAllocator64FlagMasks::kRandomShuffleChunks
;
56 typedef SizeClassAllocator64
<Params
> ThisT
;
57 typedef SizeClassAllocator64LocalCache
<ThisT
> AllocatorCache
;
59 // When we know the size class (the region base) we can represent a pointer
60 // as a 4-byte integer (offset from the region start shifted right by 4).
61 typedef u32 CompactPtrT
;
62 static const uptr kCompactPtrScale
= 4;
63 CompactPtrT
PointerToCompactPtr(uptr base
, uptr ptr
) const {
64 return static_cast<CompactPtrT
>((ptr
- base
) >> kCompactPtrScale
);
66 uptr
CompactPtrToPointer(uptr base
, CompactPtrT ptr32
) const {
67 return base
+ (static_cast<uptr
>(ptr32
) << kCompactPtrScale
);
70 void Init(s32 release_to_os_interval_ms
) {
71 uptr TotalSpaceSize
= kSpaceSize
+ AdditionalSize();
72 if (kUsingConstantSpaceBeg
) {
73 CHECK_EQ(kSpaceBeg
, address_range
.Init(TotalSpaceSize
,
74 PrimaryAllocatorName
, kSpaceBeg
));
76 NonConstSpaceBeg
= address_range
.Init(TotalSpaceSize
,
77 PrimaryAllocatorName
);
78 CHECK_NE(NonConstSpaceBeg
, ~(uptr
)0);
80 SetReleaseToOSIntervalMs(release_to_os_interval_ms
);
81 MapWithCallbackOrDie(SpaceEnd(), AdditionalSize());
82 // Check that the RegionInfo array is aligned on the CacheLine size.
83 DCHECK_EQ(SpaceEnd() % kCacheLineSize
, 0);
86 s32
ReleaseToOSIntervalMs() const {
87 return atomic_load(&release_to_os_interval_ms_
, memory_order_relaxed
);
90 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms
) {
91 atomic_store(&release_to_os_interval_ms_
, release_to_os_interval_ms
,
92 memory_order_relaxed
);
95 void ForceReleaseToOS() {
96 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
97 BlockingMutexLock
l(&GetRegionInfo(class_id
)->mutex
);
98 MaybeReleaseToOS(class_id
, true /*force*/);
102 static bool CanAllocate(uptr size
, uptr alignment
) {
103 return size
<= SizeClassMap::kMaxSize
&&
104 alignment
<= SizeClassMap::kMaxSize
;
107 NOINLINE
void ReturnToAllocator(AllocatorStats
*stat
, uptr class_id
,
108 const CompactPtrT
*chunks
, uptr n_chunks
) {
109 RegionInfo
*region
= GetRegionInfo(class_id
);
110 uptr region_beg
= GetRegionBeginBySizeClass(class_id
);
111 CompactPtrT
*free_array
= GetFreeArray(region_beg
);
113 BlockingMutexLock
l(®ion
->mutex
);
114 uptr old_num_chunks
= region
->num_freed_chunks
;
115 uptr new_num_freed_chunks
= old_num_chunks
+ n_chunks
;
116 // Failure to allocate free array space while releasing memory is non
118 if (UNLIKELY(!EnsureFreeArraySpace(region
, region_beg
,
119 new_num_freed_chunks
))) {
120 Report("FATAL: Internal error: %s's allocator exhausted the free list "
121 "space for size class %zd (%zd bytes).\n", SanitizerToolName
,
122 class_id
, ClassIdToSize(class_id
));
125 for (uptr i
= 0; i
< n_chunks
; i
++)
126 free_array
[old_num_chunks
+ i
] = chunks
[i
];
127 region
->num_freed_chunks
= new_num_freed_chunks
;
128 region
->stats
.n_freed
+= n_chunks
;
130 MaybeReleaseToOS(class_id
, false /*force*/);
133 NOINLINE
bool GetFromAllocator(AllocatorStats
*stat
, uptr class_id
,
134 CompactPtrT
*chunks
, uptr n_chunks
) {
135 RegionInfo
*region
= GetRegionInfo(class_id
);
136 uptr region_beg
= GetRegionBeginBySizeClass(class_id
);
137 CompactPtrT
*free_array
= GetFreeArray(region_beg
);
139 BlockingMutexLock
l(®ion
->mutex
);
140 if (UNLIKELY(region
->num_freed_chunks
< n_chunks
)) {
141 if (UNLIKELY(!PopulateFreeArray(stat
, class_id
, region
,
142 n_chunks
- region
->num_freed_chunks
)))
144 CHECK_GE(region
->num_freed_chunks
, n_chunks
);
146 region
->num_freed_chunks
-= n_chunks
;
147 uptr base_idx
= region
->num_freed_chunks
;
148 for (uptr i
= 0; i
< n_chunks
; i
++)
149 chunks
[i
] = free_array
[base_idx
+ i
];
150 region
->stats
.n_allocated
+= n_chunks
;
154 bool PointerIsMine(const void *p
) {
155 uptr P
= reinterpret_cast<uptr
>(p
);
156 if (kUsingConstantSpaceBeg
&& (kSpaceBeg
% kSpaceSize
) == 0)
157 return P
/ kSpaceSize
== kSpaceBeg
/ kSpaceSize
;
158 return P
>= SpaceBeg() && P
< SpaceEnd();
161 uptr
GetRegionBegin(const void *p
) {
162 if (kUsingConstantSpaceBeg
)
163 return reinterpret_cast<uptr
>(p
) & ~(kRegionSize
- 1);
164 uptr space_beg
= SpaceBeg();
165 return ((reinterpret_cast<uptr
>(p
) - space_beg
) & ~(kRegionSize
- 1)) +
169 uptr
GetRegionBeginBySizeClass(uptr class_id
) const {
170 return SpaceBeg() + kRegionSize
* class_id
;
173 uptr
GetSizeClass(const void *p
) {
174 if (kUsingConstantSpaceBeg
&& (kSpaceBeg
% kSpaceSize
) == 0)
175 return ((reinterpret_cast<uptr
>(p
)) / kRegionSize
) % kNumClassesRounded
;
176 return ((reinterpret_cast<uptr
>(p
) - SpaceBeg()) / kRegionSize
) %
180 void *GetBlockBegin(const void *p
) {
181 uptr class_id
= GetSizeClass(p
);
182 uptr size
= ClassIdToSize(class_id
);
183 if (!size
) return nullptr;
184 uptr chunk_idx
= GetChunkIdx((uptr
)p
, size
);
185 uptr reg_beg
= GetRegionBegin(p
);
186 uptr beg
= chunk_idx
* size
;
187 uptr next_beg
= beg
+ size
;
188 if (class_id
>= kNumClasses
) return nullptr;
189 RegionInfo
*region
= GetRegionInfo(class_id
);
190 if (region
->mapped_user
>= next_beg
)
191 return reinterpret_cast<void*>(reg_beg
+ beg
);
195 uptr
GetActuallyAllocatedSize(void *p
) {
196 CHECK(PointerIsMine(p
));
197 return ClassIdToSize(GetSizeClass(p
));
200 uptr
ClassID(uptr size
) { return SizeClassMap::ClassID(size
); }
202 void *GetMetaData(const void *p
) {
203 uptr class_id
= GetSizeClass(p
);
204 uptr size
= ClassIdToSize(class_id
);
205 uptr chunk_idx
= GetChunkIdx(reinterpret_cast<uptr
>(p
), size
);
206 uptr region_beg
= GetRegionBeginBySizeClass(class_id
);
207 return reinterpret_cast<void *>(GetMetadataEnd(region_beg
) -
208 (1 + chunk_idx
) * kMetadataSize
);
211 uptr
TotalMemoryUsed() {
213 for (uptr i
= 0; i
< kNumClasses
; i
++)
214 res
+= GetRegionInfo(i
)->allocated_user
;
219 void TestOnlyUnmap() {
220 UnmapWithCallbackOrDie(SpaceBeg(), kSpaceSize
+ AdditionalSize());
223 static void FillMemoryProfile(uptr start
, uptr rss
, bool file
, uptr
*stats
,
225 for (uptr class_id
= 0; class_id
< stats_size
; class_id
++)
226 if (stats
[class_id
] == start
)
227 stats
[class_id
] = rss
;
230 void PrintStats(uptr class_id
, uptr rss
) {
231 RegionInfo
*region
= GetRegionInfo(class_id
);
232 if (region
->mapped_user
== 0) return;
233 uptr in_use
= region
->stats
.n_allocated
- region
->stats
.n_freed
;
234 uptr avail_chunks
= region
->allocated_user
/ ClassIdToSize(class_id
);
236 "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd "
237 "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd "
238 "last released: %6zdK region: 0x%zx\n",
239 region
->exhausted
? "F" : " ", class_id
, ClassIdToSize(class_id
),
240 region
->mapped_user
>> 10, region
->stats
.n_allocated
,
241 region
->stats
.n_freed
, in_use
, region
->num_freed_chunks
, avail_chunks
,
242 rss
>> 10, region
->rtoi
.num_releases
,
243 region
->rtoi
.last_released_bytes
>> 10,
244 SpaceBeg() + kRegionSize
* class_id
);
248 uptr rss_stats
[kNumClasses
];
249 for (uptr class_id
= 0; class_id
< kNumClasses
; class_id
++)
250 rss_stats
[class_id
] = SpaceBeg() + kRegionSize
* class_id
;
251 GetMemoryProfile(FillMemoryProfile
, rss_stats
, kNumClasses
);
253 uptr total_mapped
= 0;
255 uptr n_allocated
= 0;
257 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
258 RegionInfo
*region
= GetRegionInfo(class_id
);
259 if (region
->mapped_user
!= 0) {
260 total_mapped
+= region
->mapped_user
;
261 total_rss
+= rss_stats
[class_id
];
263 n_allocated
+= region
->stats
.n_allocated
;
264 n_freed
+= region
->stats
.n_freed
;
267 Printf("Stats: SizeClassAllocator64: %zdM mapped (%zdM rss) in "
268 "%zd allocations; remains %zd\n", total_mapped
>> 20,
269 total_rss
>> 20, n_allocated
, n_allocated
- n_freed
);
270 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++)
271 PrintStats(class_id
, rss_stats
[class_id
]);
274 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
275 // introspection API.
277 for (uptr i
= 0; i
< kNumClasses
; i
++) {
278 GetRegionInfo(i
)->mutex
.Lock();
283 for (int i
= (int)kNumClasses
- 1; i
>= 0; i
--) {
284 GetRegionInfo(i
)->mutex
.Unlock();
288 // Iterate over all existing chunks.
289 // The allocator must be locked when calling this function.
290 void ForEachChunk(ForEachChunkCallback callback
, void *arg
) {
291 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
292 RegionInfo
*region
= GetRegionInfo(class_id
);
293 uptr chunk_size
= ClassIdToSize(class_id
);
294 uptr region_beg
= SpaceBeg() + class_id
* kRegionSize
;
295 for (uptr chunk
= region_beg
;
296 chunk
< region_beg
+ region
->allocated_user
;
297 chunk
+= chunk_size
) {
298 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
299 callback(chunk
, arg
);
304 static uptr
ClassIdToSize(uptr class_id
) {
305 return SizeClassMap::Size(class_id
);
308 static uptr
AdditionalSize() {
309 return RoundUpTo(sizeof(RegionInfo
) * kNumClassesRounded
,
310 GetPageSizeCached());
313 typedef SizeClassMap SizeClassMapT
;
314 static const uptr kNumClasses
= SizeClassMap::kNumClasses
;
315 static const uptr kNumClassesRounded
= SizeClassMap::kNumClassesRounded
;
317 // A packed array of counters. Each counter occupies 2^n bits, enough to store
318 // counter's max_value. Ctor will try to allocate the required buffer via
319 // mapper->MapPackedCounterArrayBuffer and the caller is expected to check
320 // whether the initialization was successful by checking IsAllocated() result.
321 // For the performance sake, none of the accessors check the validity of the
322 // arguments, it is assumed that index is always in [0, n) range and the value
323 // is not incremented past max_value.
324 template<class MemoryMapperT
>
325 class PackedCounterArray
{
327 PackedCounterArray(u64 num_counters
, u64 max_value
, MemoryMapperT
*mapper
)
328 : n(num_counters
), memory_mapper(mapper
) {
329 CHECK_GT(num_counters
, 0);
330 CHECK_GT(max_value
, 0);
331 constexpr u64 kMaxCounterBits
= sizeof(*buffer
) * 8ULL;
332 // Rounding counter storage size up to the power of two allows for using
333 // bit shifts calculating particular counter's index and offset.
334 uptr counter_size_bits
=
335 RoundUpToPowerOfTwo(MostSignificantSetBitIndex(max_value
) + 1);
336 CHECK_LE(counter_size_bits
, kMaxCounterBits
);
337 counter_size_bits_log
= Log2(counter_size_bits
);
338 counter_mask
= ~0ULL >> (kMaxCounterBits
- counter_size_bits
);
340 uptr packing_ratio
= kMaxCounterBits
>> counter_size_bits_log
;
341 CHECK_GT(packing_ratio
, 0);
342 packing_ratio_log
= Log2(packing_ratio
);
343 bit_offset_mask
= packing_ratio
- 1;
346 (RoundUpTo(n
, 1ULL << packing_ratio_log
) >> packing_ratio_log
) *
348 buffer
= reinterpret_cast<u64
*>(
349 memory_mapper
->MapPackedCounterArrayBuffer(buffer_size
));
351 ~PackedCounterArray() {
353 memory_mapper
->UnmapPackedCounterArrayBuffer(
354 reinterpret_cast<uptr
>(buffer
), buffer_size
);
358 bool IsAllocated() const {
362 u64
GetCount() const {
366 uptr
Get(uptr i
) const {
368 uptr index
= i
>> packing_ratio_log
;
369 uptr bit_offset
= (i
& bit_offset_mask
) << counter_size_bits_log
;
370 return (buffer
[index
] >> bit_offset
) & counter_mask
;
373 void Inc(uptr i
) const {
374 DCHECK_LT(Get(i
), counter_mask
);
375 uptr index
= i
>> packing_ratio_log
;
376 uptr bit_offset
= (i
& bit_offset_mask
) << counter_size_bits_log
;
377 buffer
[index
] += 1ULL << bit_offset
;
380 void IncRange(uptr from
, uptr to
) const {
382 for (uptr i
= from
; i
<= to
; i
++)
388 u64 counter_size_bits_log
;
390 u64 packing_ratio_log
;
393 MemoryMapperT
* const memory_mapper
;
398 template<class MemoryMapperT
>
399 class FreePagesRangeTracker
{
401 explicit FreePagesRangeTracker(MemoryMapperT
* mapper
)
402 : memory_mapper(mapper
),
403 page_size_scaled_log(Log2(GetPageSizeCached() >> kCompactPtrScale
)),
404 in_the_range(false), current_page(0), current_range_start_page(0) {}
406 void NextPage(bool freed
) {
409 current_range_start_page
= current_page
;
423 void CloseOpenedRange() {
425 memory_mapper
->ReleasePageRangeToOS(
426 current_range_start_page
<< page_size_scaled_log
,
427 current_page
<< page_size_scaled_log
);
428 in_the_range
= false;
432 MemoryMapperT
* const memory_mapper
;
433 const uptr page_size_scaled_log
;
436 uptr current_range_start_page
;
439 // Iterates over the free_array to identify memory pages containing freed
440 // chunks only and returns these pages back to OS.
441 // allocated_pages_count is the total number of pages allocated for the
443 template<class MemoryMapperT
>
444 static void ReleaseFreeMemoryToOS(CompactPtrT
*free_array
,
445 uptr free_array_count
, uptr chunk_size
,
446 uptr allocated_pages_count
,
447 MemoryMapperT
*memory_mapper
) {
448 const uptr page_size
= GetPageSizeCached();
450 // Figure out the number of chunks per page and whether we can take a fast
451 // path (the number of chunks per page is the same for all pages).
452 uptr full_pages_chunk_count_max
;
453 bool same_chunk_count_per_page
;
454 if (chunk_size
<= page_size
&& page_size
% chunk_size
== 0) {
455 // Same number of chunks per page, no cross overs.
456 full_pages_chunk_count_max
= page_size
/ chunk_size
;
457 same_chunk_count_per_page
= true;
458 } else if (chunk_size
<= page_size
&& page_size
% chunk_size
!= 0 &&
459 chunk_size
% (page_size
% chunk_size
) == 0) {
460 // Some chunks are crossing page boundaries, which means that the page
461 // contains one or two partial chunks, but all pages contain the same
463 full_pages_chunk_count_max
= page_size
/ chunk_size
+ 1;
464 same_chunk_count_per_page
= true;
465 } else if (chunk_size
<= page_size
) {
466 // Some chunks are crossing page boundaries, which means that the page
467 // contains one or two partial chunks.
468 full_pages_chunk_count_max
= page_size
/ chunk_size
+ 2;
469 same_chunk_count_per_page
= false;
470 } else if (chunk_size
> page_size
&& chunk_size
% page_size
== 0) {
471 // One chunk covers multiple pages, no cross overs.
472 full_pages_chunk_count_max
= 1;
473 same_chunk_count_per_page
= true;
474 } else if (chunk_size
> page_size
) {
475 // One chunk covers multiple pages, Some chunks are crossing page
476 // boundaries. Some pages contain one chunk, some contain two.
477 full_pages_chunk_count_max
= 2;
478 same_chunk_count_per_page
= false;
480 UNREACHABLE("All chunk_size/page_size ratios must be handled.");
483 PackedCounterArray
<MemoryMapperT
> counters(allocated_pages_count
,
484 full_pages_chunk_count_max
,
486 if (!counters
.IsAllocated())
489 const uptr chunk_size_scaled
= chunk_size
>> kCompactPtrScale
;
490 const uptr page_size_scaled
= page_size
>> kCompactPtrScale
;
491 const uptr page_size_scaled_log
= Log2(page_size_scaled
);
493 // Iterate over free chunks and count how many free chunks affect each
495 if (chunk_size
<= page_size
&& page_size
% chunk_size
== 0) {
496 // Each chunk affects one page only.
497 for (uptr i
= 0; i
< free_array_count
; i
++)
498 counters
.Inc(free_array
[i
] >> page_size_scaled_log
);
500 // In all other cases chunks might affect more than one page.
501 for (uptr i
= 0; i
< free_array_count
; i
++) {
503 free_array
[i
] >> page_size_scaled_log
,
504 (free_array
[i
] + chunk_size_scaled
- 1) >> page_size_scaled_log
);
508 // Iterate over pages detecting ranges of pages with chunk counters equal
509 // to the expected number of chunks for the particular page.
510 FreePagesRangeTracker
<MemoryMapperT
> range_tracker(memory_mapper
);
511 if (same_chunk_count_per_page
) {
512 // Fast path, every page has the same number of chunks affecting it.
513 for (uptr i
= 0; i
< counters
.GetCount(); i
++)
514 range_tracker
.NextPage(counters
.Get(i
) == full_pages_chunk_count_max
);
516 // Show path, go through the pages keeping count how many chunks affect
519 chunk_size
< page_size
? page_size_scaled
/ chunk_size_scaled
: 1;
520 const uptr pnc
= pn
* chunk_size_scaled
;
521 // The idea is to increment the current page pointer by the first chunk
522 // size, middle portion size (the portion of the page covered by chunks
523 // except the first and the last one) and then the last chunk size, adding
524 // up the number of chunks on the current page and checking on every step
525 // whether the page boundary was crossed.
526 uptr prev_page_boundary
= 0;
527 uptr current_boundary
= 0;
528 for (uptr i
= 0; i
< counters
.GetCount(); i
++) {
529 uptr page_boundary
= prev_page_boundary
+ page_size_scaled
;
530 uptr chunks_per_page
= pn
;
531 if (current_boundary
< page_boundary
) {
532 if (current_boundary
> prev_page_boundary
)
534 current_boundary
+= pnc
;
535 if (current_boundary
< page_boundary
) {
537 current_boundary
+= chunk_size_scaled
;
540 prev_page_boundary
= page_boundary
;
542 range_tracker
.NextPage(counters
.Get(i
) == chunks_per_page
);
545 range_tracker
.Done();
549 friend class MemoryMapper
;
551 ReservedAddressRange address_range
;
553 static const uptr kRegionSize
= kSpaceSize
/ kNumClassesRounded
;
554 // FreeArray is the array of free-d chunks (stored as 4-byte offsets).
555 // In the worst case it may reguire kRegionSize/SizeClassMap::kMinSize
556 // elements, but in reality this will not happen. For simplicity we
557 // dedicate 1/8 of the region's virtual space to FreeArray.
558 static const uptr kFreeArraySize
= kRegionSize
/ 8;
560 static const bool kUsingConstantSpaceBeg
= kSpaceBeg
!= ~(uptr
)0;
561 uptr NonConstSpaceBeg
;
562 uptr
SpaceBeg() const {
563 return kUsingConstantSpaceBeg
? kSpaceBeg
: NonConstSpaceBeg
;
565 uptr
SpaceEnd() const { return SpaceBeg() + kSpaceSize
; }
566 // kRegionSize must be >= 2^32.
567 COMPILER_CHECK((kRegionSize
) >= (1ULL << (SANITIZER_WORDSIZE
/ 2)));
568 // kRegionSize must be <= 2^36, see CompactPtrT.
569 COMPILER_CHECK((kRegionSize
) <= (1ULL << (SANITIZER_WORDSIZE
/ 2 + 4)));
570 // Call mmap for user memory with at least this size.
571 static const uptr kUserMapSize
= 1 << 16;
572 // Call mmap for metadata memory with at least this size.
573 static const uptr kMetaMapSize
= 1 << 16;
574 // Call mmap for free array memory with at least this size.
575 static const uptr kFreeArrayMapSize
= 1 << 16;
577 atomic_sint32_t release_to_os_interval_ms_
;
584 struct ReleaseToOsInfo
{
585 uptr n_freed_at_last_release
;
587 u64 last_release_at_ns
;
588 u64 last_released_bytes
;
591 struct ALIGNED(SANITIZER_CACHE_LINE_SIZE
) RegionInfo
{
593 uptr num_freed_chunks
; // Number of elements in the freearray.
594 uptr mapped_free_array
; // Bytes mapped for freearray.
595 uptr allocated_user
; // Bytes allocated for user memory.
596 uptr allocated_meta
; // Bytes allocated for metadata.
597 uptr mapped_user
; // Bytes mapped for user memory.
598 uptr mapped_meta
; // Bytes mapped for metadata.
599 u32 rand_state
; // Seed for random shuffle, used if kRandomShuffleChunks.
600 bool exhausted
; // Whether region is out of space for new chunks.
602 ReleaseToOsInfo rtoi
;
604 COMPILER_CHECK(sizeof(RegionInfo
) % kCacheLineSize
== 0);
606 RegionInfo
*GetRegionInfo(uptr class_id
) const {
607 DCHECK_LT(class_id
, kNumClasses
);
608 RegionInfo
*regions
= reinterpret_cast<RegionInfo
*>(SpaceEnd());
609 return ®ions
[class_id
];
612 uptr
GetMetadataEnd(uptr region_beg
) const {
613 return region_beg
+ kRegionSize
- kFreeArraySize
;
616 uptr
GetChunkIdx(uptr chunk
, uptr size
) const {
617 if (!kUsingConstantSpaceBeg
)
620 uptr offset
= chunk
% kRegionSize
;
621 // Here we divide by a non-constant. This is costly.
622 // size always fits into 32-bits. If the offset fits too, use 32-bit div.
623 if (offset
>> (SANITIZER_WORDSIZE
/ 2))
624 return offset
/ size
;
625 return (u32
)offset
/ (u32
)size
;
628 CompactPtrT
*GetFreeArray(uptr region_beg
) const {
629 return reinterpret_cast<CompactPtrT
*>(GetMetadataEnd(region_beg
));
632 bool MapWithCallback(uptr beg
, uptr size
) {
633 uptr mapped
= address_range
.Map(beg
, size
);
634 if (UNLIKELY(!mapped
))
636 CHECK_EQ(beg
, mapped
);
637 MapUnmapCallback().OnMap(beg
, size
);
641 void MapWithCallbackOrDie(uptr beg
, uptr size
) {
642 CHECK_EQ(beg
, address_range
.MapOrDie(beg
, size
));
643 MapUnmapCallback().OnMap(beg
, size
);
646 void UnmapWithCallbackOrDie(uptr beg
, uptr size
) {
647 MapUnmapCallback().OnUnmap(beg
, size
);
648 address_range
.Unmap(beg
, size
);
651 bool EnsureFreeArraySpace(RegionInfo
*region
, uptr region_beg
,
652 uptr num_freed_chunks
) {
653 uptr needed_space
= num_freed_chunks
* sizeof(CompactPtrT
);
654 if (region
->mapped_free_array
< needed_space
) {
655 uptr new_mapped_free_array
= RoundUpTo(needed_space
, kFreeArrayMapSize
);
656 CHECK_LE(new_mapped_free_array
, kFreeArraySize
);
657 uptr current_map_end
= reinterpret_cast<uptr
>(GetFreeArray(region_beg
)) +
658 region
->mapped_free_array
;
659 uptr new_map_size
= new_mapped_free_array
- region
->mapped_free_array
;
660 if (UNLIKELY(!MapWithCallback(current_map_end
, new_map_size
)))
662 region
->mapped_free_array
= new_mapped_free_array
;
667 // Check whether this size class is exhausted.
668 bool IsRegionExhausted(RegionInfo
*region
, uptr class_id
,
669 uptr additional_map_size
) {
670 if (LIKELY(region
->mapped_user
+ region
->mapped_meta
+
671 additional_map_size
<= kRegionSize
- kFreeArraySize
))
673 if (!region
->exhausted
) {
674 region
->exhausted
= true;
675 Printf("%s: Out of memory. ", SanitizerToolName
);
676 Printf("The process has exhausted %zuMB for size class %zu.\n",
677 kRegionSize
>> 20, ClassIdToSize(class_id
));
682 NOINLINE
bool PopulateFreeArray(AllocatorStats
*stat
, uptr class_id
,
683 RegionInfo
*region
, uptr requested_count
) {
684 // region->mutex is held.
685 const uptr region_beg
= GetRegionBeginBySizeClass(class_id
);
686 const uptr size
= ClassIdToSize(class_id
);
688 const uptr total_user_bytes
=
689 region
->allocated_user
+ requested_count
* size
;
690 // Map more space for chunks, if necessary.
691 if (LIKELY(total_user_bytes
> region
->mapped_user
)) {
692 if (UNLIKELY(region
->mapped_user
== 0)) {
693 if (!kUsingConstantSpaceBeg
&& kRandomShuffleChunks
)
694 // The random state is initialized from ASLR.
695 region
->rand_state
= static_cast<u32
>(region_beg
>> 12);
696 // Postpone the first release to OS attempt for ReleaseToOSIntervalMs,
697 // preventing just allocated memory from being released sooner than
698 // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls
699 // for short lived processes.
700 // Do it only when the feature is turned on, to avoid a potentially
701 // extraneous syscall.
702 if (ReleaseToOSIntervalMs() >= 0)
703 region
->rtoi
.last_release_at_ns
= MonotonicNanoTime();
705 // Do the mmap for the user memory.
706 const uptr user_map_size
=
707 RoundUpTo(total_user_bytes
- region
->mapped_user
, kUserMapSize
);
708 if (UNLIKELY(IsRegionExhausted(region
, class_id
, user_map_size
)))
710 if (UNLIKELY(!MapWithCallback(region_beg
+ region
->mapped_user
,
713 stat
->Add(AllocatorStatMapped
, user_map_size
);
714 region
->mapped_user
+= user_map_size
;
716 const uptr new_chunks_count
=
717 (region
->mapped_user
- region
->allocated_user
) / size
;
720 // Calculate the required space for metadata.
721 const uptr total_meta_bytes
=
722 region
->allocated_meta
+ new_chunks_count
* kMetadataSize
;
723 const uptr meta_map_size
= (total_meta_bytes
> region
->mapped_meta
) ?
724 RoundUpTo(total_meta_bytes
- region
->mapped_meta
, kMetaMapSize
) : 0;
725 // Map more space for metadata, if necessary.
727 if (UNLIKELY(IsRegionExhausted(region
, class_id
, meta_map_size
)))
729 if (UNLIKELY(!MapWithCallback(
730 GetMetadataEnd(region_beg
) - region
->mapped_meta
- meta_map_size
,
733 region
->mapped_meta
+= meta_map_size
;
737 // If necessary, allocate more space for the free array and populate it with
738 // newly allocated chunks.
739 const uptr total_freed_chunks
= region
->num_freed_chunks
+ new_chunks_count
;
740 if (UNLIKELY(!EnsureFreeArraySpace(region
, region_beg
, total_freed_chunks
)))
742 CompactPtrT
*free_array
= GetFreeArray(region_beg
);
743 for (uptr i
= 0, chunk
= region
->allocated_user
; i
< new_chunks_count
;
745 free_array
[total_freed_chunks
- 1 - i
] = PointerToCompactPtr(0, chunk
);
746 if (kRandomShuffleChunks
)
747 RandomShuffle(&free_array
[region
->num_freed_chunks
], new_chunks_count
,
748 ®ion
->rand_state
);
750 // All necessary memory is mapped and now it is safe to advance all
751 // 'allocated_*' counters.
752 region
->num_freed_chunks
+= new_chunks_count
;
753 region
->allocated_user
+= new_chunks_count
* size
;
754 CHECK_LE(region
->allocated_user
, region
->mapped_user
);
755 region
->allocated_meta
+= new_chunks_count
* kMetadataSize
;
756 CHECK_LE(region
->allocated_meta
, region
->mapped_meta
);
757 region
->exhausted
= false;
759 // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent
760 // MaybeReleaseToOS from releasing just allocated pages or protect these
761 // not yet used chunks some other way.
768 MemoryMapper(const ThisT
& base_allocator
, uptr class_id
)
769 : allocator(base_allocator
),
770 region_base(base_allocator
.GetRegionBeginBySizeClass(class_id
)),
771 released_ranges_count(0),
775 uptr
GetReleasedRangesCount() const {
776 return released_ranges_count
;
779 uptr
GetReleasedBytes() const {
780 return released_bytes
;
783 uptr
MapPackedCounterArrayBuffer(uptr buffer_size
) {
784 // TODO(alekseyshl): The idea to explore is to check if we have enough
785 // space between num_freed_chunks*sizeof(CompactPtrT) and
786 // mapped_free_array to fit buffer_size bytes and use that space instead
787 // of mapping a temporary one.
788 return reinterpret_cast<uptr
>(
789 MmapOrDieOnFatalError(buffer_size
, "ReleaseToOSPageCounters"));
792 void UnmapPackedCounterArrayBuffer(uptr buffer
, uptr buffer_size
) {
793 UnmapOrDie(reinterpret_cast<void *>(buffer
), buffer_size
);
796 // Releases [from, to) range of pages back to OS.
797 void ReleasePageRangeToOS(CompactPtrT from
, CompactPtrT to
) {
798 const uptr from_page
= allocator
.CompactPtrToPointer(region_base
, from
);
799 const uptr to_page
= allocator
.CompactPtrToPointer(region_base
, to
);
800 ReleaseMemoryPagesToOS(from_page
, to_page
);
801 released_ranges_count
++;
802 released_bytes
+= to_page
- from_page
;
806 const ThisT
& allocator
;
807 const uptr region_base
;
808 uptr released_ranges_count
;
812 // Attempts to release RAM occupied by freed chunks back to OS. The region is
813 // expected to be locked.
814 void MaybeReleaseToOS(uptr class_id
, bool force
) {
815 RegionInfo
*region
= GetRegionInfo(class_id
);
816 const uptr chunk_size
= ClassIdToSize(class_id
);
817 const uptr page_size
= GetPageSizeCached();
819 uptr n
= region
->num_freed_chunks
;
820 if (n
* chunk_size
< page_size
)
821 return; // No chance to release anything.
822 if ((region
->stats
.n_freed
-
823 region
->rtoi
.n_freed_at_last_release
) * chunk_size
< page_size
) {
824 return; // Nothing new to release.
828 s32 interval_ms
= ReleaseToOSIntervalMs();
832 if (region
->rtoi
.last_release_at_ns
+ interval_ms
* 1000000ULL >
833 MonotonicNanoTime()) {
834 return; // Memory was returned recently.
838 MemoryMapper
memory_mapper(*this, class_id
);
840 ReleaseFreeMemoryToOS
<MemoryMapper
>(
841 GetFreeArray(GetRegionBeginBySizeClass(class_id
)), n
, chunk_size
,
842 RoundUpTo(region
->allocated_user
, page_size
) / page_size
,
845 if (memory_mapper
.GetReleasedRangesCount() > 0) {
846 region
->rtoi
.n_freed_at_last_release
= region
->stats
.n_freed
;
847 region
->rtoi
.num_releases
+= memory_mapper
.GetReleasedRangesCount();
848 region
->rtoi
.last_released_bytes
= memory_mapper
.GetReleasedBytes();
850 region
->rtoi
.last_release_at_ns
= MonotonicNanoTime();