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 if (class_id
>= kNumClasses
) return nullptr;
190 uptr size
= ClassIdToSize(class_id
);
191 if (!size
) return nullptr;
192 uptr chunk_idx
= GetChunkIdx((uptr
)p
, size
);
193 uptr reg_beg
= GetRegionBegin(p
);
194 uptr beg
= chunk_idx
* size
;
195 uptr next_beg
= beg
+ size
;
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 CHECK(kMetadataSize
);
211 uptr class_id
= GetSizeClass(p
);
212 uptr size
= ClassIdToSize(class_id
);
213 uptr chunk_idx
= GetChunkIdx(reinterpret_cast<uptr
>(p
), size
);
214 uptr region_beg
= GetRegionBeginBySizeClass(class_id
);
215 return reinterpret_cast<void *>(GetMetadataEnd(region_beg
) -
216 (1 + chunk_idx
) * kMetadataSize
);
219 uptr
TotalMemoryUsed() {
221 for (uptr i
= 0; i
< kNumClasses
; i
++)
222 res
+= GetRegionInfo(i
)->allocated_user
;
227 void TestOnlyUnmap() {
228 UnmapWithCallbackOrDie((uptr
)address_range
.base(), address_range
.size());
231 static void FillMemoryProfile(uptr start
, uptr rss
, bool file
, uptr
*stats
,
233 for (uptr class_id
= 0; class_id
< stats_size
; class_id
++)
234 if (stats
[class_id
] == start
)
235 stats
[class_id
] = rss
;
238 void PrintStats(uptr class_id
, uptr rss
) {
239 RegionInfo
*region
= GetRegionInfo(class_id
);
240 if (region
->mapped_user
== 0) return;
241 uptr in_use
= region
->stats
.n_allocated
- region
->stats
.n_freed
;
242 uptr avail_chunks
= region
->allocated_user
/ ClassIdToSize(class_id
);
244 "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd "
245 "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd "
246 "last released: %6zdK region: 0x%zx\n",
247 region
->exhausted
? "F" : " ", class_id
, ClassIdToSize(class_id
),
248 region
->mapped_user
>> 10, region
->stats
.n_allocated
,
249 region
->stats
.n_freed
, in_use
, region
->num_freed_chunks
, avail_chunks
,
250 rss
>> 10, region
->rtoi
.num_releases
,
251 region
->rtoi
.last_released_bytes
>> 10,
252 SpaceBeg() + kRegionSize
* class_id
);
256 uptr rss_stats
[kNumClasses
];
257 for (uptr class_id
= 0; class_id
< kNumClasses
; class_id
++)
258 rss_stats
[class_id
] = SpaceBeg() + kRegionSize
* class_id
;
259 GetMemoryProfile(FillMemoryProfile
, rss_stats
, kNumClasses
);
261 uptr total_mapped
= 0;
263 uptr n_allocated
= 0;
265 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
266 RegionInfo
*region
= GetRegionInfo(class_id
);
267 if (region
->mapped_user
!= 0) {
268 total_mapped
+= region
->mapped_user
;
269 total_rss
+= rss_stats
[class_id
];
271 n_allocated
+= region
->stats
.n_allocated
;
272 n_freed
+= region
->stats
.n_freed
;
275 Printf("Stats: SizeClassAllocator64: %zdM mapped (%zdM rss) in "
276 "%zd allocations; remains %zd\n", total_mapped
>> 20,
277 total_rss
>> 20, n_allocated
, n_allocated
- n_freed
);
278 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++)
279 PrintStats(class_id
, rss_stats
[class_id
]);
282 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
283 // introspection API.
285 for (uptr i
= 0; i
< kNumClasses
; i
++) {
286 GetRegionInfo(i
)->mutex
.Lock();
291 for (int i
= (int)kNumClasses
- 1; i
>= 0; i
--) {
292 GetRegionInfo(i
)->mutex
.Unlock();
296 // Iterate over all existing chunks.
297 // The allocator must be locked when calling this function.
298 void ForEachChunk(ForEachChunkCallback callback
, void *arg
) {
299 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
300 RegionInfo
*region
= GetRegionInfo(class_id
);
301 uptr chunk_size
= ClassIdToSize(class_id
);
302 uptr region_beg
= SpaceBeg() + class_id
* kRegionSize
;
303 uptr region_allocated_user_size
=
304 AddressSpaceView::Load(region
)->allocated_user
;
305 for (uptr chunk
= region_beg
;
306 chunk
< region_beg
+ region_allocated_user_size
;
307 chunk
+= chunk_size
) {
308 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
309 callback(chunk
, arg
);
314 static uptr
ClassIdToSize(uptr class_id
) {
315 return SizeClassMap::Size(class_id
);
318 static uptr
AdditionalSize() {
319 return RoundUpTo(sizeof(RegionInfo
) * kNumClassesRounded
,
320 GetPageSizeCached());
323 typedef SizeClassMap SizeClassMapT
;
324 static const uptr kNumClasses
= SizeClassMap::kNumClasses
;
325 static const uptr kNumClassesRounded
= SizeClassMap::kNumClassesRounded
;
327 // A packed array of counters. Each counter occupies 2^n bits, enough to store
328 // counter's max_value. Ctor will try to allocate the required buffer via
329 // mapper->MapPackedCounterArrayBuffer and the caller is expected to check
330 // whether the initialization was successful by checking IsAllocated() result.
331 // For the performance sake, none of the accessors check the validity of the
332 // arguments, it is assumed that index is always in [0, n) range and the value
333 // is not incremented past max_value.
334 template<class MemoryMapperT
>
335 class PackedCounterArray
{
337 PackedCounterArray(u64 num_counters
, u64 max_value
, MemoryMapperT
*mapper
)
338 : n(num_counters
), memory_mapper(mapper
) {
339 CHECK_GT(num_counters
, 0);
340 CHECK_GT(max_value
, 0);
341 constexpr u64 kMaxCounterBits
= sizeof(*buffer
) * 8ULL;
342 // Rounding counter storage size up to the power of two allows for using
343 // bit shifts calculating particular counter's index and offset.
344 uptr counter_size_bits
=
345 RoundUpToPowerOfTwo(MostSignificantSetBitIndex(max_value
) + 1);
346 CHECK_LE(counter_size_bits
, kMaxCounterBits
);
347 counter_size_bits_log
= Log2(counter_size_bits
);
348 counter_mask
= ~0ULL >> (kMaxCounterBits
- counter_size_bits
);
350 uptr packing_ratio
= kMaxCounterBits
>> counter_size_bits_log
;
351 CHECK_GT(packing_ratio
, 0);
352 packing_ratio_log
= Log2(packing_ratio
);
353 bit_offset_mask
= packing_ratio
- 1;
356 (RoundUpTo(n
, 1ULL << packing_ratio_log
) >> packing_ratio_log
) *
358 buffer
= reinterpret_cast<u64
*>(
359 memory_mapper
->MapPackedCounterArrayBuffer(buffer_size
));
361 ~PackedCounterArray() {
363 memory_mapper
->UnmapPackedCounterArrayBuffer(
364 reinterpret_cast<uptr
>(buffer
), buffer_size
);
368 bool IsAllocated() const {
372 u64
GetCount() const {
376 uptr
Get(uptr i
) const {
378 uptr index
= i
>> packing_ratio_log
;
379 uptr bit_offset
= (i
& bit_offset_mask
) << counter_size_bits_log
;
380 return (buffer
[index
] >> bit_offset
) & counter_mask
;
383 void Inc(uptr i
) const {
384 DCHECK_LT(Get(i
), counter_mask
);
385 uptr index
= i
>> packing_ratio_log
;
386 uptr bit_offset
= (i
& bit_offset_mask
) << counter_size_bits_log
;
387 buffer
[index
] += 1ULL << bit_offset
;
390 void IncRange(uptr from
, uptr to
) const {
392 for (uptr i
= from
; i
<= to
; i
++)
398 u64 counter_size_bits_log
;
400 u64 packing_ratio_log
;
403 MemoryMapperT
* const memory_mapper
;
408 template<class MemoryMapperT
>
409 class FreePagesRangeTracker
{
411 explicit FreePagesRangeTracker(MemoryMapperT
* mapper
)
412 : memory_mapper(mapper
),
413 page_size_scaled_log(Log2(GetPageSizeCached() >> kCompactPtrScale
)),
414 in_the_range(false), current_page(0), current_range_start_page(0) {}
416 void NextPage(bool freed
) {
419 current_range_start_page
= current_page
;
433 void CloseOpenedRange() {
435 memory_mapper
->ReleasePageRangeToOS(
436 current_range_start_page
<< page_size_scaled_log
,
437 current_page
<< page_size_scaled_log
);
438 in_the_range
= false;
442 MemoryMapperT
* const memory_mapper
;
443 const uptr page_size_scaled_log
;
446 uptr current_range_start_page
;
449 // Iterates over the free_array to identify memory pages containing freed
450 // chunks only and returns these pages back to OS.
451 // allocated_pages_count is the total number of pages allocated for the
453 template<class MemoryMapperT
>
454 static void ReleaseFreeMemoryToOS(CompactPtrT
*free_array
,
455 uptr free_array_count
, uptr chunk_size
,
456 uptr allocated_pages_count
,
457 MemoryMapperT
*memory_mapper
) {
458 const uptr page_size
= GetPageSizeCached();
460 // Figure out the number of chunks per page and whether we can take a fast
461 // path (the number of chunks per page is the same for all pages).
462 uptr full_pages_chunk_count_max
;
463 bool same_chunk_count_per_page
;
464 if (chunk_size
<= page_size
&& page_size
% chunk_size
== 0) {
465 // Same number of chunks per page, no cross overs.
466 full_pages_chunk_count_max
= page_size
/ chunk_size
;
467 same_chunk_count_per_page
= true;
468 } else if (chunk_size
<= page_size
&& page_size
% chunk_size
!= 0 &&
469 chunk_size
% (page_size
% chunk_size
) == 0) {
470 // Some chunks are crossing page boundaries, which means that the page
471 // contains one or two partial chunks, but all pages contain the same
473 full_pages_chunk_count_max
= page_size
/ chunk_size
+ 1;
474 same_chunk_count_per_page
= true;
475 } else if (chunk_size
<= page_size
) {
476 // Some chunks are crossing page boundaries, which means that the page
477 // contains one or two partial chunks.
478 full_pages_chunk_count_max
= page_size
/ chunk_size
+ 2;
479 same_chunk_count_per_page
= false;
480 } else if (chunk_size
> page_size
&& chunk_size
% page_size
== 0) {
481 // One chunk covers multiple pages, no cross overs.
482 full_pages_chunk_count_max
= 1;
483 same_chunk_count_per_page
= true;
484 } else if (chunk_size
> page_size
) {
485 // One chunk covers multiple pages, Some chunks are crossing page
486 // boundaries. Some pages contain one chunk, some contain two.
487 full_pages_chunk_count_max
= 2;
488 same_chunk_count_per_page
= false;
490 UNREACHABLE("All chunk_size/page_size ratios must be handled.");
493 PackedCounterArray
<MemoryMapperT
> counters(allocated_pages_count
,
494 full_pages_chunk_count_max
,
496 if (!counters
.IsAllocated())
499 const uptr chunk_size_scaled
= chunk_size
>> kCompactPtrScale
;
500 const uptr page_size_scaled
= page_size
>> kCompactPtrScale
;
501 const uptr page_size_scaled_log
= Log2(page_size_scaled
);
503 // Iterate over free chunks and count how many free chunks affect each
505 if (chunk_size
<= page_size
&& page_size
% chunk_size
== 0) {
506 // Each chunk affects one page only.
507 for (uptr i
= 0; i
< free_array_count
; i
++)
508 counters
.Inc(free_array
[i
] >> page_size_scaled_log
);
510 // In all other cases chunks might affect more than one page.
511 for (uptr i
= 0; i
< free_array_count
; i
++) {
513 free_array
[i
] >> page_size_scaled_log
,
514 (free_array
[i
] + chunk_size_scaled
- 1) >> page_size_scaled_log
);
518 // Iterate over pages detecting ranges of pages with chunk counters equal
519 // to the expected number of chunks for the particular page.
520 FreePagesRangeTracker
<MemoryMapperT
> range_tracker(memory_mapper
);
521 if (same_chunk_count_per_page
) {
522 // Fast path, every page has the same number of chunks affecting it.
523 for (uptr i
= 0; i
< counters
.GetCount(); i
++)
524 range_tracker
.NextPage(counters
.Get(i
) == full_pages_chunk_count_max
);
526 // Show path, go through the pages keeping count how many chunks affect
529 chunk_size
< page_size
? page_size_scaled
/ chunk_size_scaled
: 1;
530 const uptr pnc
= pn
* chunk_size_scaled
;
531 // The idea is to increment the current page pointer by the first chunk
532 // size, middle portion size (the portion of the page covered by chunks
533 // except the first and the last one) and then the last chunk size, adding
534 // up the number of chunks on the current page and checking on every step
535 // whether the page boundary was crossed.
536 uptr prev_page_boundary
= 0;
537 uptr current_boundary
= 0;
538 for (uptr i
= 0; i
< counters
.GetCount(); i
++) {
539 uptr page_boundary
= prev_page_boundary
+ page_size_scaled
;
540 uptr chunks_per_page
= pn
;
541 if (current_boundary
< page_boundary
) {
542 if (current_boundary
> prev_page_boundary
)
544 current_boundary
+= pnc
;
545 if (current_boundary
< page_boundary
) {
547 current_boundary
+= chunk_size_scaled
;
550 prev_page_boundary
= page_boundary
;
552 range_tracker
.NextPage(counters
.Get(i
) == chunks_per_page
);
555 range_tracker
.Done();
559 friend class MemoryMapper
;
561 ReservedAddressRange address_range
;
563 static const uptr kRegionSize
= kSpaceSize
/ kNumClassesRounded
;
564 // FreeArray is the array of free-d chunks (stored as 4-byte offsets).
565 // In the worst case it may reguire kRegionSize/SizeClassMap::kMinSize
566 // elements, but in reality this will not happen. For simplicity we
567 // dedicate 1/8 of the region's virtual space to FreeArray.
568 static const uptr kFreeArraySize
= kRegionSize
/ 8;
570 static const bool kUsingConstantSpaceBeg
= kSpaceBeg
!= ~(uptr
)0;
571 uptr NonConstSpaceBeg
;
572 uptr
SpaceBeg() const {
573 return kUsingConstantSpaceBeg
? kSpaceBeg
: NonConstSpaceBeg
;
575 uptr
SpaceEnd() const { return SpaceBeg() + kSpaceSize
; }
576 // kRegionSize must be >= 2^32.
577 COMPILER_CHECK((kRegionSize
) >= (1ULL << (SANITIZER_WORDSIZE
/ 2)));
578 // kRegionSize must be <= 2^36, see CompactPtrT.
579 COMPILER_CHECK((kRegionSize
) <= (1ULL << (SANITIZER_WORDSIZE
/ 2 + 4)));
580 // Call mmap for user memory with at least this size.
581 static const uptr kUserMapSize
= 1 << 16;
582 // Call mmap for metadata memory with at least this size.
583 static const uptr kMetaMapSize
= 1 << 16;
584 // Call mmap for free array memory with at least this size.
585 static const uptr kFreeArrayMapSize
= 1 << 16;
587 atomic_sint32_t release_to_os_interval_ms_
;
594 struct ReleaseToOsInfo
{
595 uptr n_freed_at_last_release
;
597 u64 last_release_at_ns
;
598 u64 last_released_bytes
;
601 struct ALIGNED(SANITIZER_CACHE_LINE_SIZE
) RegionInfo
{
603 uptr num_freed_chunks
; // Number of elements in the freearray.
604 uptr mapped_free_array
; // Bytes mapped for freearray.
605 uptr allocated_user
; // Bytes allocated for user memory.
606 uptr allocated_meta
; // Bytes allocated for metadata.
607 uptr mapped_user
; // Bytes mapped for user memory.
608 uptr mapped_meta
; // Bytes mapped for metadata.
609 u32 rand_state
; // Seed for random shuffle, used if kRandomShuffleChunks.
610 bool exhausted
; // Whether region is out of space for new chunks.
612 ReleaseToOsInfo rtoi
;
614 COMPILER_CHECK(sizeof(RegionInfo
) % kCacheLineSize
== 0);
616 RegionInfo
*GetRegionInfo(uptr class_id
) const {
617 DCHECK_LT(class_id
, kNumClasses
);
618 RegionInfo
*regions
= reinterpret_cast<RegionInfo
*>(SpaceEnd());
619 return ®ions
[class_id
];
622 uptr
GetMetadataEnd(uptr region_beg
) const {
623 return region_beg
+ kRegionSize
- kFreeArraySize
;
626 uptr
GetChunkIdx(uptr chunk
, uptr size
) const {
627 if (!kUsingConstantSpaceBeg
)
630 uptr offset
= chunk
% kRegionSize
;
631 // Here we divide by a non-constant. This is costly.
632 // size always fits into 32-bits. If the offset fits too, use 32-bit div.
633 if (offset
>> (SANITIZER_WORDSIZE
/ 2))
634 return offset
/ size
;
635 return (u32
)offset
/ (u32
)size
;
638 CompactPtrT
*GetFreeArray(uptr region_beg
) const {
639 return reinterpret_cast<CompactPtrT
*>(GetMetadataEnd(region_beg
));
642 bool MapWithCallback(uptr beg
, uptr size
, const char *name
) {
643 uptr mapped
= address_range
.Map(beg
, size
, name
);
644 if (UNLIKELY(!mapped
))
646 CHECK_EQ(beg
, mapped
);
647 MapUnmapCallback().OnMap(beg
, size
);
651 void MapWithCallbackOrDie(uptr beg
, uptr size
, const char *name
) {
652 CHECK_EQ(beg
, address_range
.MapOrDie(beg
, size
, name
));
653 MapUnmapCallback().OnMap(beg
, size
);
656 void UnmapWithCallbackOrDie(uptr beg
, uptr size
) {
657 MapUnmapCallback().OnUnmap(beg
, size
);
658 address_range
.Unmap(beg
, size
);
661 bool EnsureFreeArraySpace(RegionInfo
*region
, uptr region_beg
,
662 uptr num_freed_chunks
) {
663 uptr needed_space
= num_freed_chunks
* sizeof(CompactPtrT
);
664 if (region
->mapped_free_array
< needed_space
) {
665 uptr new_mapped_free_array
= RoundUpTo(needed_space
, kFreeArrayMapSize
);
666 CHECK_LE(new_mapped_free_array
, kFreeArraySize
);
667 uptr current_map_end
= reinterpret_cast<uptr
>(GetFreeArray(region_beg
)) +
668 region
->mapped_free_array
;
669 uptr new_map_size
= new_mapped_free_array
- region
->mapped_free_array
;
670 if (UNLIKELY(!MapWithCallback(current_map_end
, new_map_size
,
671 "SizeClassAllocator: freearray")))
673 region
->mapped_free_array
= new_mapped_free_array
;
678 // Check whether this size class is exhausted.
679 bool IsRegionExhausted(RegionInfo
*region
, uptr class_id
,
680 uptr additional_map_size
) {
681 if (LIKELY(region
->mapped_user
+ region
->mapped_meta
+
682 additional_map_size
<= kRegionSize
- kFreeArraySize
))
684 if (!region
->exhausted
) {
685 region
->exhausted
= true;
686 Printf("%s: Out of memory. ", SanitizerToolName
);
687 Printf("The process has exhausted %zuMB for size class %zu.\n",
688 kRegionSize
>> 20, ClassIdToSize(class_id
));
693 NOINLINE
bool PopulateFreeArray(AllocatorStats
*stat
, uptr class_id
,
694 RegionInfo
*region
, uptr requested_count
) {
695 // region->mutex is held.
696 const uptr region_beg
= GetRegionBeginBySizeClass(class_id
);
697 const uptr size
= ClassIdToSize(class_id
);
699 const uptr total_user_bytes
=
700 region
->allocated_user
+ requested_count
* size
;
701 // Map more space for chunks, if necessary.
702 if (LIKELY(total_user_bytes
> region
->mapped_user
)) {
703 if (UNLIKELY(region
->mapped_user
== 0)) {
704 if (!kUsingConstantSpaceBeg
&& kRandomShuffleChunks
)
705 // The random state is initialized from ASLR.
706 region
->rand_state
= static_cast<u32
>(region_beg
>> 12);
707 // Postpone the first release to OS attempt for ReleaseToOSIntervalMs,
708 // preventing just allocated memory from being released sooner than
709 // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls
710 // for short lived processes.
711 // Do it only when the feature is turned on, to avoid a potentially
712 // extraneous syscall.
713 if (ReleaseToOSIntervalMs() >= 0)
714 region
->rtoi
.last_release_at_ns
= MonotonicNanoTime();
716 // Do the mmap for the user memory.
717 const uptr user_map_size
=
718 RoundUpTo(total_user_bytes
- region
->mapped_user
, kUserMapSize
);
719 if (UNLIKELY(IsRegionExhausted(region
, class_id
, user_map_size
)))
721 if (UNLIKELY(!MapWithCallback(region_beg
+ region
->mapped_user
,
723 "SizeClassAllocator: region data")))
725 stat
->Add(AllocatorStatMapped
, user_map_size
);
726 region
->mapped_user
+= user_map_size
;
728 const uptr new_chunks_count
=
729 (region
->mapped_user
- region
->allocated_user
) / size
;
732 // Calculate the required space for metadata.
733 const uptr total_meta_bytes
=
734 region
->allocated_meta
+ new_chunks_count
* kMetadataSize
;
735 const uptr meta_map_size
= (total_meta_bytes
> region
->mapped_meta
) ?
736 RoundUpTo(total_meta_bytes
- region
->mapped_meta
, kMetaMapSize
) : 0;
737 // Map more space for metadata, if necessary.
739 if (UNLIKELY(IsRegionExhausted(region
, class_id
, meta_map_size
)))
741 if (UNLIKELY(!MapWithCallback(
742 GetMetadataEnd(region_beg
) - region
->mapped_meta
- meta_map_size
,
743 meta_map_size
, "SizeClassAllocator: region metadata")))
745 region
->mapped_meta
+= meta_map_size
;
749 // If necessary, allocate more space for the free array and populate it with
750 // newly allocated chunks.
751 const uptr total_freed_chunks
= region
->num_freed_chunks
+ new_chunks_count
;
752 if (UNLIKELY(!EnsureFreeArraySpace(region
, region_beg
, total_freed_chunks
)))
754 CompactPtrT
*free_array
= GetFreeArray(region_beg
);
755 for (uptr i
= 0, chunk
= region
->allocated_user
; i
< new_chunks_count
;
757 free_array
[total_freed_chunks
- 1 - i
] = PointerToCompactPtr(0, chunk
);
758 if (kRandomShuffleChunks
)
759 RandomShuffle(&free_array
[region
->num_freed_chunks
], new_chunks_count
,
760 ®ion
->rand_state
);
762 // All necessary memory is mapped and now it is safe to advance all
763 // 'allocated_*' counters.
764 region
->num_freed_chunks
+= new_chunks_count
;
765 region
->allocated_user
+= new_chunks_count
* size
;
766 CHECK_LE(region
->allocated_user
, region
->mapped_user
);
767 region
->allocated_meta
+= new_chunks_count
* kMetadataSize
;
768 CHECK_LE(region
->allocated_meta
, region
->mapped_meta
);
769 region
->exhausted
= false;
771 // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent
772 // MaybeReleaseToOS from releasing just allocated pages or protect these
773 // not yet used chunks some other way.
780 MemoryMapper(const ThisT
& base_allocator
, uptr class_id
)
781 : allocator(base_allocator
),
782 region_base(base_allocator
.GetRegionBeginBySizeClass(class_id
)),
783 released_ranges_count(0),
787 uptr
GetReleasedRangesCount() const {
788 return released_ranges_count
;
791 uptr
GetReleasedBytes() const {
792 return released_bytes
;
795 uptr
MapPackedCounterArrayBuffer(uptr buffer_size
) {
796 // TODO(alekseyshl): The idea to explore is to check if we have enough
797 // space between num_freed_chunks*sizeof(CompactPtrT) and
798 // mapped_free_array to fit buffer_size bytes and use that space instead
799 // of mapping a temporary one.
800 return reinterpret_cast<uptr
>(
801 MmapOrDieOnFatalError(buffer_size
, "ReleaseToOSPageCounters"));
804 void UnmapPackedCounterArrayBuffer(uptr buffer
, uptr buffer_size
) {
805 UnmapOrDie(reinterpret_cast<void *>(buffer
), buffer_size
);
808 // Releases [from, to) range of pages back to OS.
809 void ReleasePageRangeToOS(CompactPtrT from
, CompactPtrT to
) {
810 const uptr from_page
= allocator
.CompactPtrToPointer(region_base
, from
);
811 const uptr to_page
= allocator
.CompactPtrToPointer(region_base
, to
);
812 ReleaseMemoryPagesToOS(from_page
, to_page
);
813 released_ranges_count
++;
814 released_bytes
+= to_page
- from_page
;
818 const ThisT
& allocator
;
819 const uptr region_base
;
820 uptr released_ranges_count
;
824 // Attempts to release RAM occupied by freed chunks back to OS. The region is
825 // expected to be locked.
826 void MaybeReleaseToOS(uptr class_id
, bool force
) {
827 RegionInfo
*region
= GetRegionInfo(class_id
);
828 const uptr chunk_size
= ClassIdToSize(class_id
);
829 const uptr page_size
= GetPageSizeCached();
831 uptr n
= region
->num_freed_chunks
;
832 if (n
* chunk_size
< page_size
)
833 return; // No chance to release anything.
834 if ((region
->stats
.n_freed
-
835 region
->rtoi
.n_freed_at_last_release
) * chunk_size
< page_size
) {
836 return; // Nothing new to release.
840 s32 interval_ms
= ReleaseToOSIntervalMs();
844 if (region
->rtoi
.last_release_at_ns
+ interval_ms
* 1000000ULL >
845 MonotonicNanoTime()) {
846 return; // Memory was returned recently.
850 MemoryMapper
memory_mapper(*this, class_id
);
852 ReleaseFreeMemoryToOS
<MemoryMapper
>(
853 GetFreeArray(GetRegionBeginBySizeClass(class_id
)), n
, chunk_size
,
854 RoundUpTo(region
->allocated_user
, page_size
) / page_size
,
857 if (memory_mapper
.GetReleasedRangesCount() > 0) {
858 region
->rtoi
.n_freed_at_last_release
= region
->stats
.n_freed
;
859 region
->rtoi
.num_releases
+= memory_mapper
.GetReleasedRangesCount();
860 region
->rtoi
.last_released_bytes
= memory_mapper
.GetReleasedBytes();
862 region
->rtoi
.last_release_at_ns
= MonotonicNanoTime();