1 //===-- sanitizer_allocator_primary64.h -------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // Part of the Sanitizer Allocator.
11 //===----------------------------------------------------------------------===//
12 #ifndef SANITIZER_ALLOCATOR_H
13 #error This file must be included inside sanitizer_allocator.h
16 template<class SizeClassAllocator
> struct SizeClassAllocator64LocalCache
;
18 // SizeClassAllocator64 -- allocator for 64-bit address space.
19 // The template parameter Params is a class containing the actual parameters.
21 // Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg.
22 // If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically my 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.
28 // Region: a part of Space dedicated to a single size class.
29 // There are kNumClasses Regions of equal size.
31 // UserChunk: a piece of memory returned to user.
32 // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk.
34 // FreeArray is an array free-d chunks (stored as 4-byte offsets)
36 // A Region looks like this:
37 // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray
39 struct SizeClassAllocator64FlagMasks
{ // Bit masks.
41 kRandomShuffleChunks
= 1,
45 template <class Params
>
46 class SizeClassAllocator64
{
48 using AddressSpaceView
= typename
Params::AddressSpaceView
;
49 static const uptr kSpaceBeg
= Params::kSpaceBeg
;
50 static const uptr kSpaceSize
= Params::kSpaceSize
;
51 static const uptr kMetadataSize
= Params::kMetadataSize
;
52 typedef typename
Params::SizeClassMap SizeClassMap
;
53 typedef typename
Params::MapUnmapCallback MapUnmapCallback
;
55 static const bool kRandomShuffleChunks
=
56 Params::kFlags
& SizeClassAllocator64FlagMasks::kRandomShuffleChunks
;
58 typedef SizeClassAllocator64
<Params
> ThisT
;
59 typedef SizeClassAllocator64LocalCache
<ThisT
> AllocatorCache
;
61 // When we know the size class (the region base) we can represent a pointer
62 // as a 4-byte integer (offset from the region start shifted right by 4).
63 typedef u32 CompactPtrT
;
64 static const uptr kCompactPtrScale
= 4;
65 CompactPtrT
PointerToCompactPtr(uptr base
, uptr ptr
) const {
66 return static_cast<CompactPtrT
>((ptr
- base
) >> kCompactPtrScale
);
68 uptr
CompactPtrToPointer(uptr base
, CompactPtrT ptr32
) const {
69 return base
+ (static_cast<uptr
>(ptr32
) << kCompactPtrScale
);
72 void Init(s32 release_to_os_interval_ms
) {
73 uptr TotalSpaceSize
= kSpaceSize
+ AdditionalSize();
74 if (kUsingConstantSpaceBeg
) {
75 CHECK(IsAligned(kSpaceBeg
, SizeClassMap::kMaxSize
));
76 CHECK_EQ(kSpaceBeg
, address_range
.Init(TotalSpaceSize
,
77 PrimaryAllocatorName
, kSpaceBeg
));
79 // Combined allocator expects that an 2^N allocation is always aligned to
80 // 2^N. For this to work, the start of the space needs to be aligned as
81 // high as the largest size class (which also needs to be a power of 2).
82 NonConstSpaceBeg
= address_range
.InitAligned(
83 TotalSpaceSize
, SizeClassMap::kMaxSize
, PrimaryAllocatorName
);
84 CHECK_NE(NonConstSpaceBeg
, ~(uptr
)0);
86 SetReleaseToOSIntervalMs(release_to_os_interval_ms
);
87 MapWithCallbackOrDie(SpaceEnd(), AdditionalSize(),
88 "SizeClassAllocator: region info");
89 // Check that the RegionInfo array is aligned on the CacheLine size.
90 DCHECK_EQ(SpaceEnd() % kCacheLineSize
, 0);
93 s32
ReleaseToOSIntervalMs() const {
94 return atomic_load(&release_to_os_interval_ms_
, memory_order_relaxed
);
97 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms
) {
98 atomic_store(&release_to_os_interval_ms_
, release_to_os_interval_ms
,
99 memory_order_relaxed
);
102 void ForceReleaseToOS() {
103 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
104 BlockingMutexLock
l(&GetRegionInfo(class_id
)->mutex
);
105 MaybeReleaseToOS(class_id
, true /*force*/);
109 static bool CanAllocate(uptr size
, uptr alignment
) {
110 return size
<= SizeClassMap::kMaxSize
&&
111 alignment
<= SizeClassMap::kMaxSize
;
114 NOINLINE
void ReturnToAllocator(AllocatorStats
*stat
, uptr class_id
,
115 const CompactPtrT
*chunks
, uptr n_chunks
) {
116 RegionInfo
*region
= GetRegionInfo(class_id
);
117 uptr region_beg
= GetRegionBeginBySizeClass(class_id
);
118 CompactPtrT
*free_array
= GetFreeArray(region_beg
);
120 BlockingMutexLock
l(®ion
->mutex
);
121 uptr old_num_chunks
= region
->num_freed_chunks
;
122 uptr new_num_freed_chunks
= old_num_chunks
+ n_chunks
;
123 // Failure to allocate free array space while releasing memory is non
125 if (UNLIKELY(!EnsureFreeArraySpace(region
, region_beg
,
126 new_num_freed_chunks
))) {
127 Report("FATAL: Internal error: %s's allocator exhausted the free list "
128 "space for size class %zd (%zd bytes).\n", SanitizerToolName
,
129 class_id
, ClassIdToSize(class_id
));
132 for (uptr i
= 0; i
< n_chunks
; i
++)
133 free_array
[old_num_chunks
+ i
] = chunks
[i
];
134 region
->num_freed_chunks
= new_num_freed_chunks
;
135 region
->stats
.n_freed
+= n_chunks
;
137 MaybeReleaseToOS(class_id
, false /*force*/);
140 NOINLINE
bool GetFromAllocator(AllocatorStats
*stat
, uptr class_id
,
141 CompactPtrT
*chunks
, uptr n_chunks
) {
142 RegionInfo
*region
= GetRegionInfo(class_id
);
143 uptr region_beg
= GetRegionBeginBySizeClass(class_id
);
144 CompactPtrT
*free_array
= GetFreeArray(region_beg
);
146 BlockingMutexLock
l(®ion
->mutex
);
147 if (UNLIKELY(region
->num_freed_chunks
< n_chunks
)) {
148 if (UNLIKELY(!PopulateFreeArray(stat
, class_id
, region
,
149 n_chunks
- region
->num_freed_chunks
)))
151 CHECK_GE(region
->num_freed_chunks
, n_chunks
);
153 region
->num_freed_chunks
-= n_chunks
;
154 uptr base_idx
= region
->num_freed_chunks
;
155 for (uptr i
= 0; i
< n_chunks
; i
++)
156 chunks
[i
] = free_array
[base_idx
+ i
];
157 region
->stats
.n_allocated
+= n_chunks
;
161 bool PointerIsMine(const void *p
) const {
162 uptr P
= reinterpret_cast<uptr
>(p
);
163 if (kUsingConstantSpaceBeg
&& (kSpaceBeg
% kSpaceSize
) == 0)
164 return P
/ kSpaceSize
== kSpaceBeg
/ kSpaceSize
;
165 return P
>= SpaceBeg() && P
< SpaceEnd();
168 uptr
GetRegionBegin(const void *p
) {
169 if (kUsingConstantSpaceBeg
)
170 return reinterpret_cast<uptr
>(p
) & ~(kRegionSize
- 1);
171 uptr space_beg
= SpaceBeg();
172 return ((reinterpret_cast<uptr
>(p
) - space_beg
) & ~(kRegionSize
- 1)) +
176 uptr
GetRegionBeginBySizeClass(uptr class_id
) const {
177 return SpaceBeg() + kRegionSize
* class_id
;
180 uptr
GetSizeClass(const void *p
) {
181 if (kUsingConstantSpaceBeg
&& (kSpaceBeg
% kSpaceSize
) == 0)
182 return ((reinterpret_cast<uptr
>(p
)) / kRegionSize
) % kNumClassesRounded
;
183 return ((reinterpret_cast<uptr
>(p
) - SpaceBeg()) / kRegionSize
) %
187 void *GetBlockBegin(const void *p
) {
188 uptr class_id
= GetSizeClass(p
);
189 uptr size
= ClassIdToSize(class_id
);
190 if (!size
) return nullptr;
191 uptr chunk_idx
= GetChunkIdx((uptr
)p
, size
);
192 uptr reg_beg
= GetRegionBegin(p
);
193 uptr beg
= chunk_idx
* size
;
194 uptr next_beg
= beg
+ size
;
195 if (class_id
>= kNumClasses
) return nullptr;
196 const RegionInfo
*region
= AddressSpaceView::Load(GetRegionInfo(class_id
));
197 if (region
->mapped_user
>= next_beg
)
198 return reinterpret_cast<void*>(reg_beg
+ beg
);
202 uptr
GetActuallyAllocatedSize(void *p
) {
203 CHECK(PointerIsMine(p
));
204 return ClassIdToSize(GetSizeClass(p
));
207 static uptr
ClassID(uptr size
) { return SizeClassMap::ClassID(size
); }
209 void *GetMetaData(const void *p
) {
210 uptr class_id
= GetSizeClass(p
);
211 uptr size
= ClassIdToSize(class_id
);
212 uptr chunk_idx
= GetChunkIdx(reinterpret_cast<uptr
>(p
), size
);
213 uptr region_beg
= GetRegionBeginBySizeClass(class_id
);
214 return reinterpret_cast<void *>(GetMetadataEnd(region_beg
) -
215 (1 + chunk_idx
) * kMetadataSize
);
218 uptr
TotalMemoryUsed() {
220 for (uptr i
= 0; i
< kNumClasses
; i
++)
221 res
+= GetRegionInfo(i
)->allocated_user
;
226 void TestOnlyUnmap() {
227 UnmapWithCallbackOrDie((uptr
)address_range
.base(), address_range
.size());
230 static void FillMemoryProfile(uptr start
, uptr rss
, bool file
, uptr
*stats
,
232 for (uptr class_id
= 0; class_id
< stats_size
; class_id
++)
233 if (stats
[class_id
] == start
)
234 stats
[class_id
] = rss
;
237 void PrintStats(uptr class_id
, uptr rss
) {
238 RegionInfo
*region
= GetRegionInfo(class_id
);
239 if (region
->mapped_user
== 0) return;
240 uptr in_use
= region
->stats
.n_allocated
- region
->stats
.n_freed
;
241 uptr avail_chunks
= region
->allocated_user
/ ClassIdToSize(class_id
);
243 "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd "
244 "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd "
245 "last released: %6zdK region: 0x%zx\n",
246 region
->exhausted
? "F" : " ", class_id
, ClassIdToSize(class_id
),
247 region
->mapped_user
>> 10, region
->stats
.n_allocated
,
248 region
->stats
.n_freed
, in_use
, region
->num_freed_chunks
, avail_chunks
,
249 rss
>> 10, region
->rtoi
.num_releases
,
250 region
->rtoi
.last_released_bytes
>> 10,
251 SpaceBeg() + kRegionSize
* class_id
);
255 uptr rss_stats
[kNumClasses
];
256 for (uptr class_id
= 0; class_id
< kNumClasses
; class_id
++)
257 rss_stats
[class_id
] = SpaceBeg() + kRegionSize
* class_id
;
258 GetMemoryProfile(FillMemoryProfile
, rss_stats
, kNumClasses
);
260 uptr total_mapped
= 0;
262 uptr n_allocated
= 0;
264 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
265 RegionInfo
*region
= GetRegionInfo(class_id
);
266 if (region
->mapped_user
!= 0) {
267 total_mapped
+= region
->mapped_user
;
268 total_rss
+= rss_stats
[class_id
];
270 n_allocated
+= region
->stats
.n_allocated
;
271 n_freed
+= region
->stats
.n_freed
;
274 Printf("Stats: SizeClassAllocator64: %zdM mapped (%zdM rss) in "
275 "%zd allocations; remains %zd\n", total_mapped
>> 20,
276 total_rss
>> 20, n_allocated
, n_allocated
- n_freed
);
277 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++)
278 PrintStats(class_id
, rss_stats
[class_id
]);
281 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
282 // introspection API.
284 for (uptr i
= 0; i
< kNumClasses
; i
++) {
285 GetRegionInfo(i
)->mutex
.Lock();
290 for (int i
= (int)kNumClasses
- 1; i
>= 0; i
--) {
291 GetRegionInfo(i
)->mutex
.Unlock();
295 // Iterate over all existing chunks.
296 // The allocator must be locked when calling this function.
297 void ForEachChunk(ForEachChunkCallback callback
, void *arg
) {
298 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
299 RegionInfo
*region
= GetRegionInfo(class_id
);
300 uptr chunk_size
= ClassIdToSize(class_id
);
301 uptr region_beg
= SpaceBeg() + class_id
* kRegionSize
;
302 uptr region_allocated_user_size
=
303 AddressSpaceView::Load(region
)->allocated_user
;
304 for (uptr chunk
= region_beg
;
305 chunk
< region_beg
+ region_allocated_user_size
;
306 chunk
+= chunk_size
) {
307 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
308 callback(chunk
, arg
);
313 static uptr
ClassIdToSize(uptr class_id
) {
314 return SizeClassMap::Size(class_id
);
317 static uptr
AdditionalSize() {
318 return RoundUpTo(sizeof(RegionInfo
) * kNumClassesRounded
,
319 GetPageSizeCached());
322 typedef SizeClassMap SizeClassMapT
;
323 static const uptr kNumClasses
= SizeClassMap::kNumClasses
;
324 static const uptr kNumClassesRounded
= SizeClassMap::kNumClassesRounded
;
326 // A packed array of counters. Each counter occupies 2^n bits, enough to store
327 // counter's max_value. Ctor will try to allocate the required buffer via
328 // mapper->MapPackedCounterArrayBuffer and the caller is expected to check
329 // whether the initialization was successful by checking IsAllocated() result.
330 // For the performance sake, none of the accessors check the validity of the
331 // arguments, it is assumed that index is always in [0, n) range and the value
332 // is not incremented past max_value.
333 template<class MemoryMapperT
>
334 class PackedCounterArray
{
336 PackedCounterArray(u64 num_counters
, u64 max_value
, MemoryMapperT
*mapper
)
337 : n(num_counters
), memory_mapper(mapper
) {
338 CHECK_GT(num_counters
, 0);
339 CHECK_GT(max_value
, 0);
340 constexpr u64 kMaxCounterBits
= sizeof(*buffer
) * 8ULL;
341 // Rounding counter storage size up to the power of two allows for using
342 // bit shifts calculating particular counter's index and offset.
343 uptr counter_size_bits
=
344 RoundUpToPowerOfTwo(MostSignificantSetBitIndex(max_value
) + 1);
345 CHECK_LE(counter_size_bits
, kMaxCounterBits
);
346 counter_size_bits_log
= Log2(counter_size_bits
);
347 counter_mask
= ~0ULL >> (kMaxCounterBits
- counter_size_bits
);
349 uptr packing_ratio
= kMaxCounterBits
>> counter_size_bits_log
;
350 CHECK_GT(packing_ratio
, 0);
351 packing_ratio_log
= Log2(packing_ratio
);
352 bit_offset_mask
= packing_ratio
- 1;
355 (RoundUpTo(n
, 1ULL << packing_ratio_log
) >> packing_ratio_log
) *
357 buffer
= reinterpret_cast<u64
*>(
358 memory_mapper
->MapPackedCounterArrayBuffer(buffer_size
));
360 ~PackedCounterArray() {
362 memory_mapper
->UnmapPackedCounterArrayBuffer(
363 reinterpret_cast<uptr
>(buffer
), buffer_size
);
367 bool IsAllocated() const {
371 u64
GetCount() const {
375 uptr
Get(uptr i
) const {
377 uptr index
= i
>> packing_ratio_log
;
378 uptr bit_offset
= (i
& bit_offset_mask
) << counter_size_bits_log
;
379 return (buffer
[index
] >> bit_offset
) & counter_mask
;
382 void Inc(uptr i
) const {
383 DCHECK_LT(Get(i
), counter_mask
);
384 uptr index
= i
>> packing_ratio_log
;
385 uptr bit_offset
= (i
& bit_offset_mask
) << counter_size_bits_log
;
386 buffer
[index
] += 1ULL << bit_offset
;
389 void IncRange(uptr from
, uptr to
) const {
391 for (uptr i
= from
; i
<= to
; i
++)
397 u64 counter_size_bits_log
;
399 u64 packing_ratio_log
;
402 MemoryMapperT
* const memory_mapper
;
407 template<class MemoryMapperT
>
408 class FreePagesRangeTracker
{
410 explicit FreePagesRangeTracker(MemoryMapperT
* mapper
)
411 : memory_mapper(mapper
),
412 page_size_scaled_log(Log2(GetPageSizeCached() >> kCompactPtrScale
)),
413 in_the_range(false), current_page(0), current_range_start_page(0) {}
415 void NextPage(bool freed
) {
418 current_range_start_page
= current_page
;
432 void CloseOpenedRange() {
434 memory_mapper
->ReleasePageRangeToOS(
435 current_range_start_page
<< page_size_scaled_log
,
436 current_page
<< page_size_scaled_log
);
437 in_the_range
= false;
441 MemoryMapperT
* const memory_mapper
;
442 const uptr page_size_scaled_log
;
445 uptr current_range_start_page
;
448 // Iterates over the free_array to identify memory pages containing freed
449 // chunks only and returns these pages back to OS.
450 // allocated_pages_count is the total number of pages allocated for the
452 template<class MemoryMapperT
>
453 static void ReleaseFreeMemoryToOS(CompactPtrT
*free_array
,
454 uptr free_array_count
, uptr chunk_size
,
455 uptr allocated_pages_count
,
456 MemoryMapperT
*memory_mapper
) {
457 const uptr page_size
= GetPageSizeCached();
459 // Figure out the number of chunks per page and whether we can take a fast
460 // path (the number of chunks per page is the same for all pages).
461 uptr full_pages_chunk_count_max
;
462 bool same_chunk_count_per_page
;
463 if (chunk_size
<= page_size
&& page_size
% chunk_size
== 0) {
464 // Same number of chunks per page, no cross overs.
465 full_pages_chunk_count_max
= page_size
/ chunk_size
;
466 same_chunk_count_per_page
= true;
467 } else if (chunk_size
<= page_size
&& page_size
% chunk_size
!= 0 &&
468 chunk_size
% (page_size
% chunk_size
) == 0) {
469 // Some chunks are crossing page boundaries, which means that the page
470 // contains one or two partial chunks, but all pages contain the same
472 full_pages_chunk_count_max
= page_size
/ chunk_size
+ 1;
473 same_chunk_count_per_page
= true;
474 } else if (chunk_size
<= page_size
) {
475 // Some chunks are crossing page boundaries, which means that the page
476 // contains one or two partial chunks.
477 full_pages_chunk_count_max
= page_size
/ chunk_size
+ 2;
478 same_chunk_count_per_page
= false;
479 } else if (chunk_size
> page_size
&& chunk_size
% page_size
== 0) {
480 // One chunk covers multiple pages, no cross overs.
481 full_pages_chunk_count_max
= 1;
482 same_chunk_count_per_page
= true;
483 } else if (chunk_size
> page_size
) {
484 // One chunk covers multiple pages, Some chunks are crossing page
485 // boundaries. Some pages contain one chunk, some contain two.
486 full_pages_chunk_count_max
= 2;
487 same_chunk_count_per_page
= false;
489 UNREACHABLE("All chunk_size/page_size ratios must be handled.");
492 PackedCounterArray
<MemoryMapperT
> counters(allocated_pages_count
,
493 full_pages_chunk_count_max
,
495 if (!counters
.IsAllocated())
498 const uptr chunk_size_scaled
= chunk_size
>> kCompactPtrScale
;
499 const uptr page_size_scaled
= page_size
>> kCompactPtrScale
;
500 const uptr page_size_scaled_log
= Log2(page_size_scaled
);
502 // Iterate over free chunks and count how many free chunks affect each
504 if (chunk_size
<= page_size
&& page_size
% chunk_size
== 0) {
505 // Each chunk affects one page only.
506 for (uptr i
= 0; i
< free_array_count
; i
++)
507 counters
.Inc(free_array
[i
] >> page_size_scaled_log
);
509 // In all other cases chunks might affect more than one page.
510 for (uptr i
= 0; i
< free_array_count
; i
++) {
512 free_array
[i
] >> page_size_scaled_log
,
513 (free_array
[i
] + chunk_size_scaled
- 1) >> page_size_scaled_log
);
517 // Iterate over pages detecting ranges of pages with chunk counters equal
518 // to the expected number of chunks for the particular page.
519 FreePagesRangeTracker
<MemoryMapperT
> range_tracker(memory_mapper
);
520 if (same_chunk_count_per_page
) {
521 // Fast path, every page has the same number of chunks affecting it.
522 for (uptr i
= 0; i
< counters
.GetCount(); i
++)
523 range_tracker
.NextPage(counters
.Get(i
) == full_pages_chunk_count_max
);
525 // Show path, go through the pages keeping count how many chunks affect
528 chunk_size
< page_size
? page_size_scaled
/ chunk_size_scaled
: 1;
529 const uptr pnc
= pn
* chunk_size_scaled
;
530 // The idea is to increment the current page pointer by the first chunk
531 // size, middle portion size (the portion of the page covered by chunks
532 // except the first and the last one) and then the last chunk size, adding
533 // up the number of chunks on the current page and checking on every step
534 // whether the page boundary was crossed.
535 uptr prev_page_boundary
= 0;
536 uptr current_boundary
= 0;
537 for (uptr i
= 0; i
< counters
.GetCount(); i
++) {
538 uptr page_boundary
= prev_page_boundary
+ page_size_scaled
;
539 uptr chunks_per_page
= pn
;
540 if (current_boundary
< page_boundary
) {
541 if (current_boundary
> prev_page_boundary
)
543 current_boundary
+= pnc
;
544 if (current_boundary
< page_boundary
) {
546 current_boundary
+= chunk_size_scaled
;
549 prev_page_boundary
= page_boundary
;
551 range_tracker
.NextPage(counters
.Get(i
) == chunks_per_page
);
554 range_tracker
.Done();
558 friend class MemoryMapper
;
560 ReservedAddressRange address_range
;
562 static const uptr kRegionSize
= kSpaceSize
/ kNumClassesRounded
;
563 // FreeArray is the array of free-d chunks (stored as 4-byte offsets).
564 // In the worst case it may reguire kRegionSize/SizeClassMap::kMinSize
565 // elements, but in reality this will not happen. For simplicity we
566 // dedicate 1/8 of the region's virtual space to FreeArray.
567 static const uptr kFreeArraySize
= kRegionSize
/ 8;
569 static const bool kUsingConstantSpaceBeg
= kSpaceBeg
!= ~(uptr
)0;
570 uptr NonConstSpaceBeg
;
571 uptr
SpaceBeg() const {
572 return kUsingConstantSpaceBeg
? kSpaceBeg
: NonConstSpaceBeg
;
574 uptr
SpaceEnd() const { return SpaceBeg() + kSpaceSize
; }
575 // kRegionSize must be >= 2^32.
576 COMPILER_CHECK((kRegionSize
) >= (1ULL << (SANITIZER_WORDSIZE
/ 2)));
577 // kRegionSize must be <= 2^36, see CompactPtrT.
578 COMPILER_CHECK((kRegionSize
) <= (1ULL << (SANITIZER_WORDSIZE
/ 2 + 4)));
579 // Call mmap for user memory with at least this size.
580 static const uptr kUserMapSize
= 1 << 16;
581 // Call mmap for metadata memory with at least this size.
582 static const uptr kMetaMapSize
= 1 << 16;
583 // Call mmap for free array memory with at least this size.
584 static const uptr kFreeArrayMapSize
= 1 << 16;
586 atomic_sint32_t release_to_os_interval_ms_
;
593 struct ReleaseToOsInfo
{
594 uptr n_freed_at_last_release
;
596 u64 last_release_at_ns
;
597 u64 last_released_bytes
;
600 struct ALIGNED(SANITIZER_CACHE_LINE_SIZE
) RegionInfo
{
602 uptr num_freed_chunks
; // Number of elements in the freearray.
603 uptr mapped_free_array
; // Bytes mapped for freearray.
604 uptr allocated_user
; // Bytes allocated for user memory.
605 uptr allocated_meta
; // Bytes allocated for metadata.
606 uptr mapped_user
; // Bytes mapped for user memory.
607 uptr mapped_meta
; // Bytes mapped for metadata.
608 u32 rand_state
; // Seed for random shuffle, used if kRandomShuffleChunks.
609 bool exhausted
; // Whether region is out of space for new chunks.
611 ReleaseToOsInfo rtoi
;
613 COMPILER_CHECK(sizeof(RegionInfo
) % kCacheLineSize
== 0);
615 RegionInfo
*GetRegionInfo(uptr class_id
) const {
616 DCHECK_LT(class_id
, kNumClasses
);
617 RegionInfo
*regions
= reinterpret_cast<RegionInfo
*>(SpaceEnd());
618 return ®ions
[class_id
];
621 uptr
GetMetadataEnd(uptr region_beg
) const {
622 return region_beg
+ kRegionSize
- kFreeArraySize
;
625 uptr
GetChunkIdx(uptr chunk
, uptr size
) const {
626 if (!kUsingConstantSpaceBeg
)
629 uptr offset
= chunk
% kRegionSize
;
630 // Here we divide by a non-constant. This is costly.
631 // size always fits into 32-bits. If the offset fits too, use 32-bit div.
632 if (offset
>> (SANITIZER_WORDSIZE
/ 2))
633 return offset
/ size
;
634 return (u32
)offset
/ (u32
)size
;
637 CompactPtrT
*GetFreeArray(uptr region_beg
) const {
638 return reinterpret_cast<CompactPtrT
*>(GetMetadataEnd(region_beg
));
641 bool MapWithCallback(uptr beg
, uptr size
, const char *name
) {
642 uptr mapped
= address_range
.Map(beg
, size
, name
);
643 if (UNLIKELY(!mapped
))
645 CHECK_EQ(beg
, mapped
);
646 MapUnmapCallback().OnMap(beg
, size
);
650 void MapWithCallbackOrDie(uptr beg
, uptr size
, const char *name
) {
651 CHECK_EQ(beg
, address_range
.MapOrDie(beg
, size
, name
));
652 MapUnmapCallback().OnMap(beg
, size
);
655 void UnmapWithCallbackOrDie(uptr beg
, uptr size
) {
656 MapUnmapCallback().OnUnmap(beg
, size
);
657 address_range
.Unmap(beg
, size
);
660 bool EnsureFreeArraySpace(RegionInfo
*region
, uptr region_beg
,
661 uptr num_freed_chunks
) {
662 uptr needed_space
= num_freed_chunks
* sizeof(CompactPtrT
);
663 if (region
->mapped_free_array
< needed_space
) {
664 uptr new_mapped_free_array
= RoundUpTo(needed_space
, kFreeArrayMapSize
);
665 CHECK_LE(new_mapped_free_array
, kFreeArraySize
);
666 uptr current_map_end
= reinterpret_cast<uptr
>(GetFreeArray(region_beg
)) +
667 region
->mapped_free_array
;
668 uptr new_map_size
= new_mapped_free_array
- region
->mapped_free_array
;
669 if (UNLIKELY(!MapWithCallback(current_map_end
, new_map_size
,
670 "SizeClassAllocator: freearray")))
672 region
->mapped_free_array
= new_mapped_free_array
;
677 // Check whether this size class is exhausted.
678 bool IsRegionExhausted(RegionInfo
*region
, uptr class_id
,
679 uptr additional_map_size
) {
680 if (LIKELY(region
->mapped_user
+ region
->mapped_meta
+
681 additional_map_size
<= kRegionSize
- kFreeArraySize
))
683 if (!region
->exhausted
) {
684 region
->exhausted
= true;
685 Printf("%s: Out of memory. ", SanitizerToolName
);
686 Printf("The process has exhausted %zuMB for size class %zu.\n",
687 kRegionSize
>> 20, ClassIdToSize(class_id
));
692 NOINLINE
bool PopulateFreeArray(AllocatorStats
*stat
, uptr class_id
,
693 RegionInfo
*region
, uptr requested_count
) {
694 // region->mutex is held.
695 const uptr region_beg
= GetRegionBeginBySizeClass(class_id
);
696 const uptr size
= ClassIdToSize(class_id
);
698 const uptr total_user_bytes
=
699 region
->allocated_user
+ requested_count
* size
;
700 // Map more space for chunks, if necessary.
701 if (LIKELY(total_user_bytes
> region
->mapped_user
)) {
702 if (UNLIKELY(region
->mapped_user
== 0)) {
703 if (!kUsingConstantSpaceBeg
&& kRandomShuffleChunks
)
704 // The random state is initialized from ASLR.
705 region
->rand_state
= static_cast<u32
>(region_beg
>> 12);
706 // Postpone the first release to OS attempt for ReleaseToOSIntervalMs,
707 // preventing just allocated memory from being released sooner than
708 // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls
709 // for short lived processes.
710 // Do it only when the feature is turned on, to avoid a potentially
711 // extraneous syscall.
712 if (ReleaseToOSIntervalMs() >= 0)
713 region
->rtoi
.last_release_at_ns
= MonotonicNanoTime();
715 // Do the mmap for the user memory.
716 const uptr user_map_size
=
717 RoundUpTo(total_user_bytes
- region
->mapped_user
, kUserMapSize
);
718 if (UNLIKELY(IsRegionExhausted(region
, class_id
, user_map_size
)))
720 if (UNLIKELY(!MapWithCallback(region_beg
+ region
->mapped_user
,
722 "SizeClassAllocator: region data")))
724 stat
->Add(AllocatorStatMapped
, user_map_size
);
725 region
->mapped_user
+= user_map_size
;
727 const uptr new_chunks_count
=
728 (region
->mapped_user
- region
->allocated_user
) / size
;
731 // Calculate the required space for metadata.
732 const uptr total_meta_bytes
=
733 region
->allocated_meta
+ new_chunks_count
* kMetadataSize
;
734 const uptr meta_map_size
= (total_meta_bytes
> region
->mapped_meta
) ?
735 RoundUpTo(total_meta_bytes
- region
->mapped_meta
, kMetaMapSize
) : 0;
736 // Map more space for metadata, if necessary.
738 if (UNLIKELY(IsRegionExhausted(region
, class_id
, meta_map_size
)))
740 if (UNLIKELY(!MapWithCallback(
741 GetMetadataEnd(region_beg
) - region
->mapped_meta
- meta_map_size
,
742 meta_map_size
, "SizeClassAllocator: region metadata")))
744 region
->mapped_meta
+= meta_map_size
;
748 // If necessary, allocate more space for the free array and populate it with
749 // newly allocated chunks.
750 const uptr total_freed_chunks
= region
->num_freed_chunks
+ new_chunks_count
;
751 if (UNLIKELY(!EnsureFreeArraySpace(region
, region_beg
, total_freed_chunks
)))
753 CompactPtrT
*free_array
= GetFreeArray(region_beg
);
754 for (uptr i
= 0, chunk
= region
->allocated_user
; i
< new_chunks_count
;
756 free_array
[total_freed_chunks
- 1 - i
] = PointerToCompactPtr(0, chunk
);
757 if (kRandomShuffleChunks
)
758 RandomShuffle(&free_array
[region
->num_freed_chunks
], new_chunks_count
,
759 ®ion
->rand_state
);
761 // All necessary memory is mapped and now it is safe to advance all
762 // 'allocated_*' counters.
763 region
->num_freed_chunks
+= new_chunks_count
;
764 region
->allocated_user
+= new_chunks_count
* size
;
765 CHECK_LE(region
->allocated_user
, region
->mapped_user
);
766 region
->allocated_meta
+= new_chunks_count
* kMetadataSize
;
767 CHECK_LE(region
->allocated_meta
, region
->mapped_meta
);
768 region
->exhausted
= false;
770 // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent
771 // MaybeReleaseToOS from releasing just allocated pages or protect these
772 // not yet used chunks some other way.
779 MemoryMapper(const ThisT
& base_allocator
, uptr class_id
)
780 : allocator(base_allocator
),
781 region_base(base_allocator
.GetRegionBeginBySizeClass(class_id
)),
782 released_ranges_count(0),
786 uptr
GetReleasedRangesCount() const {
787 return released_ranges_count
;
790 uptr
GetReleasedBytes() const {
791 return released_bytes
;
794 uptr
MapPackedCounterArrayBuffer(uptr buffer_size
) {
795 // TODO(alekseyshl): The idea to explore is to check if we have enough
796 // space between num_freed_chunks*sizeof(CompactPtrT) and
797 // mapped_free_array to fit buffer_size bytes and use that space instead
798 // of mapping a temporary one.
799 return reinterpret_cast<uptr
>(
800 MmapOrDieOnFatalError(buffer_size
, "ReleaseToOSPageCounters"));
803 void UnmapPackedCounterArrayBuffer(uptr buffer
, uptr buffer_size
) {
804 UnmapOrDie(reinterpret_cast<void *>(buffer
), buffer_size
);
807 // Releases [from, to) range of pages back to OS.
808 void ReleasePageRangeToOS(CompactPtrT from
, CompactPtrT to
) {
809 const uptr from_page
= allocator
.CompactPtrToPointer(region_base
, from
);
810 const uptr to_page
= allocator
.CompactPtrToPointer(region_base
, to
);
811 ReleaseMemoryPagesToOS(from_page
, to_page
);
812 released_ranges_count
++;
813 released_bytes
+= to_page
- from_page
;
817 const ThisT
& allocator
;
818 const uptr region_base
;
819 uptr released_ranges_count
;
823 // Attempts to release RAM occupied by freed chunks back to OS. The region is
824 // expected to be locked.
825 void MaybeReleaseToOS(uptr class_id
, bool force
) {
826 RegionInfo
*region
= GetRegionInfo(class_id
);
827 const uptr chunk_size
= ClassIdToSize(class_id
);
828 const uptr page_size
= GetPageSizeCached();
830 uptr n
= region
->num_freed_chunks
;
831 if (n
* chunk_size
< page_size
)
832 return; // No chance to release anything.
833 if ((region
->stats
.n_freed
-
834 region
->rtoi
.n_freed_at_last_release
) * chunk_size
< page_size
) {
835 return; // Nothing new to release.
839 s32 interval_ms
= ReleaseToOSIntervalMs();
843 if (region
->rtoi
.last_release_at_ns
+ interval_ms
* 1000000ULL >
844 MonotonicNanoTime()) {
845 return; // Memory was returned recently.
849 MemoryMapper
memory_mapper(*this, class_id
);
851 ReleaseFreeMemoryToOS
<MemoryMapper
>(
852 GetFreeArray(GetRegionBeginBySizeClass(class_id
)), n
, chunk_size
,
853 RoundUpTo(region
->allocated_user
, page_size
) / page_size
,
856 if (memory_mapper
.GetReleasedRangesCount() > 0) {
857 region
->rtoi
.n_freed_at_last_release
= region
->stats
.n_freed
;
858 region
->rtoi
.num_releases
+= memory_mapper
.GetReleasedRangesCount();
859 region
->rtoi
.last_released_bytes
= memory_mapper
.GetReleasedBytes();
861 region
->rtoi
.last_release_at_ns
= MonotonicNanoTime();