1 //===-- sanitizer_allocator.h -----------------------------------*- C++ -*-===//
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
6 //===----------------------------------------------------------------------===//
8 // Specialized memory allocator for ThreadSanitizer, MemorySanitizer, etc.
10 //===----------------------------------------------------------------------===//
12 #ifndef SANITIZER_ALLOCATOR_H
13 #define SANITIZER_ALLOCATOR_H
15 #include "sanitizer_internal_defs.h"
16 #include "sanitizer_common.h"
17 #include "sanitizer_libc.h"
18 #include "sanitizer_list.h"
19 #include "sanitizer_mutex.h"
20 #include "sanitizer_lfstack.h"
22 namespace __sanitizer
{
24 // Depending on allocator_may_return_null either return 0 or crash.
25 void *AllocatorReturnNull();
27 // SizeClassMap maps allocation sizes into size classes and back.
28 // Class 0 corresponds to size 0.
29 // Classes 1 - 16 correspond to sizes 16 to 256 (size = class_id * 16).
30 // Next 4 classes: 256 + i * 64 (i = 1 to 4).
31 // Next 4 classes: 512 + i * 128 (i = 1 to 4).
33 // Next 4 classes: 2^k + i * 2^(k-2) (i = 1 to 4).
34 // Last class corresponds to kMaxSize = 1 << kMaxSizeLog.
36 // This structure of the size class map gives us:
37 // - Efficient table-free class-to-size and size-to-class functions.
38 // - Difference between two consequent size classes is betweed 14% and 25%
40 // This class also gives a hint to a thread-caching allocator about the amount
41 // of chunks that need to be cached per-thread:
42 // - kMaxNumCached is the maximal number of chunks per size class.
43 // - (1 << kMaxBytesCachedLog) is the maximal number of bytes per size class.
45 // Part of output of SizeClassMap::Print():
46 // c00 => s: 0 diff: +0 00% l 0 cached: 0 0; id 0
47 // c01 => s: 16 diff: +16 00% l 4 cached: 256 4096; id 1
48 // c02 => s: 32 diff: +16 100% l 5 cached: 256 8192; id 2
49 // c03 => s: 48 diff: +16 50% l 5 cached: 256 12288; id 3
50 // c04 => s: 64 diff: +16 33% l 6 cached: 256 16384; id 4
51 // c05 => s: 80 diff: +16 25% l 6 cached: 256 20480; id 5
52 // c06 => s: 96 diff: +16 20% l 6 cached: 256 24576; id 6
53 // c07 => s: 112 diff: +16 16% l 6 cached: 256 28672; id 7
55 // c08 => s: 128 diff: +16 14% l 7 cached: 256 32768; id 8
56 // c09 => s: 144 diff: +16 12% l 7 cached: 256 36864; id 9
57 // c10 => s: 160 diff: +16 11% l 7 cached: 256 40960; id 10
58 // c11 => s: 176 diff: +16 10% l 7 cached: 256 45056; id 11
59 // c12 => s: 192 diff: +16 09% l 7 cached: 256 49152; id 12
60 // c13 => s: 208 diff: +16 08% l 7 cached: 256 53248; id 13
61 // c14 => s: 224 diff: +16 07% l 7 cached: 256 57344; id 14
62 // c15 => s: 240 diff: +16 07% l 7 cached: 256 61440; id 15
64 // c16 => s: 256 diff: +16 06% l 8 cached: 256 65536; id 16
65 // c17 => s: 320 diff: +64 25% l 8 cached: 204 65280; id 17
66 // c18 => s: 384 diff: +64 20% l 8 cached: 170 65280; id 18
67 // c19 => s: 448 diff: +64 16% l 8 cached: 146 65408; id 19
69 // c20 => s: 512 diff: +64 14% l 9 cached: 128 65536; id 20
70 // c21 => s: 640 diff: +128 25% l 9 cached: 102 65280; id 21
71 // c22 => s: 768 diff: +128 20% l 9 cached: 85 65280; id 22
72 // c23 => s: 896 diff: +128 16% l 9 cached: 73 65408; id 23
74 // c24 => s: 1024 diff: +128 14% l 10 cached: 64 65536; id 24
75 // c25 => s: 1280 diff: +256 25% l 10 cached: 51 65280; id 25
76 // c26 => s: 1536 diff: +256 20% l 10 cached: 42 64512; id 26
77 // c27 => s: 1792 diff: +256 16% l 10 cached: 36 64512; id 27
81 // c48 => s: 65536 diff: +8192 14% l 16 cached: 1 65536; id 48
82 // c49 => s: 81920 diff: +16384 25% l 16 cached: 1 81920; id 49
83 // c50 => s: 98304 diff: +16384 20% l 16 cached: 1 98304; id 50
84 // c51 => s: 114688 diff: +16384 16% l 16 cached: 1 114688; id 51
86 // c52 => s: 131072 diff: +16384 14% l 17 cached: 1 131072; id 52
88 template <uptr kMaxSizeLog
, uptr kMaxNumCachedT
, uptr kMaxBytesCachedLog
>
90 static const uptr kMinSizeLog
= 4;
91 static const uptr kMidSizeLog
= kMinSizeLog
+ 4;
92 static const uptr kMinSize
= 1 << kMinSizeLog
;
93 static const uptr kMidSize
= 1 << kMidSizeLog
;
94 static const uptr kMidClass
= kMidSize
/ kMinSize
;
95 static const uptr S
= 2;
96 static const uptr M
= (1 << S
) - 1;
99 static const uptr kMaxNumCached
= kMaxNumCachedT
;
100 // We transfer chunks between central and thread-local free lists in batches.
101 // For small size classes we allocate batches separately.
102 // For large size classes we use one of the chunks to store the batch.
103 struct TransferBatch
{
106 void *batch
[kMaxNumCached
];
109 static const uptr kMaxSize
= 1UL << kMaxSizeLog
;
110 static const uptr kNumClasses
=
111 kMidClass
+ ((kMaxSizeLog
- kMidSizeLog
) << S
) + 1;
112 COMPILER_CHECK(kNumClasses
>= 32 && kNumClasses
<= 256);
113 static const uptr kNumClassesRounded
=
114 kNumClasses
== 32 ? 32 :
115 kNumClasses
<= 64 ? 64 :
116 kNumClasses
<= 128 ? 128 : 256;
118 static uptr
Size(uptr class_id
) {
119 if (class_id
<= kMidClass
)
120 return kMinSize
* class_id
;
121 class_id
-= kMidClass
;
122 uptr t
= kMidSize
<< (class_id
>> S
);
123 return t
+ (t
>> S
) * (class_id
& M
);
126 static uptr
ClassID(uptr size
) {
127 if (size
<= kMidSize
)
128 return (size
+ kMinSize
- 1) >> kMinSizeLog
;
129 if (size
> kMaxSize
) return 0;
130 uptr l
= MostSignificantSetBitIndex(size
);
131 uptr hbits
= (size
>> (l
- S
)) & M
;
132 uptr lbits
= size
& ((1 << (l
- S
)) - 1);
133 uptr l1
= l
- kMidSizeLog
;
134 return kMidClass
+ (l1
<< S
) + hbits
+ (lbits
> 0);
137 static uptr
MaxCached(uptr class_id
) {
138 if (class_id
== 0) return 0;
139 uptr n
= (1UL << kMaxBytesCachedLog
) / Size(class_id
);
140 return Max
<uptr
>(1, Min(kMaxNumCached
, n
));
143 static void Print() {
145 uptr total_cached
= 0;
146 for (uptr i
= 0; i
< kNumClasses
; i
++) {
148 if (s
>= kMidSize
/ 2 && (s
& (s
- 1)) == 0)
151 uptr p
= prev_s
? (d
* 100 / prev_s
) : 0;
152 uptr l
= s
? MostSignificantSetBitIndex(s
) : 0;
153 uptr cached
= MaxCached(i
) * s
;
154 Printf("c%02zd => s: %zd diff: +%zd %02zd%% l %zd "
155 "cached: %zd %zd; id %zd\n",
156 i
, Size(i
), d
, p
, l
, MaxCached(i
), cached
, ClassID(s
));
157 total_cached
+= cached
;
160 Printf("Total cached: %zd\n", total_cached
);
163 static bool SizeClassRequiresSeparateTransferBatch(uptr class_id
) {
164 return Size(class_id
) < sizeof(TransferBatch
) -
165 sizeof(uptr
) * (kMaxNumCached
- MaxCached(class_id
));
168 static void Validate() {
169 for (uptr c
= 1; c
< kNumClasses
; c
++) {
170 // Printf("Validate: c%zd\n", c);
173 CHECK_EQ(ClassID(s
), c
);
174 if (c
!= kNumClasses
- 1)
175 CHECK_EQ(ClassID(s
+ 1), c
+ 1);
176 CHECK_EQ(ClassID(s
- 1), c
);
178 CHECK_GT(Size(c
), Size(c
-1));
180 CHECK_EQ(ClassID(kMaxSize
+ 1), 0);
182 for (uptr s
= 1; s
<= kMaxSize
; s
++) {
184 // Printf("s%zd => c%zd\n", s, c);
185 CHECK_LT(c
, kNumClasses
);
186 CHECK_GE(Size(c
), s
);
188 CHECK_LT(Size(c
-1), s
);
193 typedef SizeClassMap
<17, 128, 16> DefaultSizeClassMap
;
194 typedef SizeClassMap
<17, 64, 14> CompactSizeClassMap
;
195 template<class SizeClassAllocator
> struct SizeClassAllocatorLocalCache
;
197 // Memory allocator statistics
199 AllocatorStatMalloced
,
201 AllocatorStatMmapped
,
202 AllocatorStatUnmapped
,
206 typedef u64 AllocatorStatCounters
[AllocatorStatCount
];
208 // Per-thread stats, live in per-thread cache.
209 class AllocatorStats
{
212 internal_memset(this, 0, sizeof(*this));
215 void Add(AllocatorStat i
, u64 v
) {
216 v
+= atomic_load(&stats_
[i
], memory_order_relaxed
);
217 atomic_store(&stats_
[i
], v
, memory_order_relaxed
);
220 void Set(AllocatorStat i
, u64 v
) {
221 atomic_store(&stats_
[i
], v
, memory_order_relaxed
);
224 u64
Get(AllocatorStat i
) const {
225 return atomic_load(&stats_
[i
], memory_order_relaxed
);
229 friend class AllocatorGlobalStats
;
230 AllocatorStats
*next_
;
231 AllocatorStats
*prev_
;
232 atomic_uint64_t stats_
[AllocatorStatCount
];
235 // Global stats, used for aggregation and querying.
236 class AllocatorGlobalStats
: public AllocatorStats
{
239 internal_memset(this, 0, sizeof(*this));
244 void Register(AllocatorStats
*s
) {
245 SpinMutexLock
l(&mu_
);
252 void Unregister(AllocatorStats
*s
) {
253 SpinMutexLock
l(&mu_
);
254 s
->prev_
->next_
= s
->next_
;
255 s
->next_
->prev_
= s
->prev_
;
256 for (int i
= 0; i
< AllocatorStatCount
; i
++)
257 Add(AllocatorStat(i
), s
->Get(AllocatorStat(i
)));
260 void Get(AllocatorStatCounters s
) const {
261 internal_memset(s
, 0, AllocatorStatCount
* sizeof(u64
));
262 SpinMutexLock
l(&mu_
);
263 const AllocatorStats
*stats
= this;
265 for (int i
= 0; i
< AllocatorStatCount
; i
++)
266 s
[i
] += stats
->Get(AllocatorStat(i
));
267 stats
= stats
->next_
;
274 mutable SpinMutex mu_
;
277 // Allocators call these callbacks on mmap/munmap.
278 struct NoOpMapUnmapCallback
{
279 void OnMap(uptr p
, uptr size
) const { }
280 void OnUnmap(uptr p
, uptr size
) const { }
283 // Callback type for iterating over chunks.
284 typedef void (*ForEachChunkCallback
)(uptr chunk
, void *arg
);
286 // SizeClassAllocator64 -- allocator for 64-bit address space.
288 // Space: a portion of address space of kSpaceSize bytes starting at
289 // a fixed address (kSpaceBeg). Both constants are powers of two and
290 // kSpaceBeg is kSpaceSize-aligned.
291 // At the beginning the entire space is mprotect-ed, then small parts of it
292 // are mapped on demand.
294 // Region: a part of Space dedicated to a single size class.
295 // There are kNumClasses Regions of equal size.
297 // UserChunk: a piece of memory returned to user.
298 // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk.
300 // A Region looks like this:
301 // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1
302 template <const uptr kSpaceBeg
, const uptr kSpaceSize
,
303 const uptr kMetadataSize
, class SizeClassMap
,
304 class MapUnmapCallback
= NoOpMapUnmapCallback
>
305 class SizeClassAllocator64
{
307 typedef typename
SizeClassMap::TransferBatch Batch
;
308 typedef SizeClassAllocator64
<kSpaceBeg
, kSpaceSize
, kMetadataSize
,
309 SizeClassMap
, MapUnmapCallback
> ThisT
;
310 typedef SizeClassAllocatorLocalCache
<ThisT
> AllocatorCache
;
314 reinterpret_cast<uptr
>(Mprotect(kSpaceBeg
, kSpaceSize
)));
315 MapWithCallback(kSpaceEnd
, AdditionalSize());
318 void MapWithCallback(uptr beg
, uptr size
) {
319 CHECK_EQ(beg
, reinterpret_cast<uptr
>(MmapFixedOrDie(beg
, size
)));
320 MapUnmapCallback().OnMap(beg
, size
);
323 void UnmapWithCallback(uptr beg
, uptr size
) {
324 MapUnmapCallback().OnUnmap(beg
, size
);
325 UnmapOrDie(reinterpret_cast<void *>(beg
), size
);
328 static bool CanAllocate(uptr size
, uptr alignment
) {
329 return size
<= SizeClassMap::kMaxSize
&&
330 alignment
<= SizeClassMap::kMaxSize
;
333 NOINLINE Batch
* AllocateBatch(AllocatorStats
*stat
, AllocatorCache
*c
,
335 CHECK_LT(class_id
, kNumClasses
);
336 RegionInfo
*region
= GetRegionInfo(class_id
);
337 Batch
*b
= region
->free_list
.Pop();
339 b
= PopulateFreeList(stat
, c
, class_id
, region
);
340 region
->n_allocated
+= b
->count
;
344 NOINLINE
void DeallocateBatch(AllocatorStats
*stat
, uptr class_id
, Batch
*b
) {
345 RegionInfo
*region
= GetRegionInfo(class_id
);
346 CHECK_GT(b
->count
, 0);
347 region
->free_list
.Push(b
);
348 region
->n_freed
+= b
->count
;
351 static bool PointerIsMine(const void *p
) {
352 return reinterpret_cast<uptr
>(p
) / kSpaceSize
== kSpaceBeg
/ kSpaceSize
;
355 static uptr
GetSizeClass(const void *p
) {
356 return (reinterpret_cast<uptr
>(p
) / kRegionSize
) % kNumClassesRounded
;
359 void *GetBlockBegin(const void *p
) {
360 uptr class_id
= GetSizeClass(p
);
361 uptr size
= SizeClassMap::Size(class_id
);
363 uptr chunk_idx
= GetChunkIdx((uptr
)p
, size
);
364 uptr reg_beg
= (uptr
)p
& ~(kRegionSize
- 1);
365 uptr beg
= chunk_idx
* size
;
366 uptr next_beg
= beg
+ size
;
367 if (class_id
>= kNumClasses
) return 0;
368 RegionInfo
*region
= GetRegionInfo(class_id
);
369 if (region
->mapped_user
>= next_beg
)
370 return reinterpret_cast<void*>(reg_beg
+ beg
);
374 static uptr
GetActuallyAllocatedSize(void *p
) {
375 CHECK(PointerIsMine(p
));
376 return SizeClassMap::Size(GetSizeClass(p
));
379 uptr
ClassID(uptr size
) { return SizeClassMap::ClassID(size
); }
381 void *GetMetaData(const void *p
) {
382 uptr class_id
= GetSizeClass(p
);
383 uptr size
= SizeClassMap::Size(class_id
);
384 uptr chunk_idx
= GetChunkIdx(reinterpret_cast<uptr
>(p
), size
);
385 return reinterpret_cast<void*>(kSpaceBeg
+ (kRegionSize
* (class_id
+ 1)) -
386 (1 + chunk_idx
) * kMetadataSize
);
389 uptr
TotalMemoryUsed() {
391 for (uptr i
= 0; i
< kNumClasses
; i
++)
392 res
+= GetRegionInfo(i
)->allocated_user
;
397 void TestOnlyUnmap() {
398 UnmapWithCallback(kSpaceBeg
, kSpaceSize
+ AdditionalSize());
402 uptr total_mapped
= 0;
403 uptr n_allocated
= 0;
405 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
406 RegionInfo
*region
= GetRegionInfo(class_id
);
407 total_mapped
+= region
->mapped_user
;
408 n_allocated
+= region
->n_allocated
;
409 n_freed
+= region
->n_freed
;
411 Printf("Stats: SizeClassAllocator64: %zdM mapped in %zd allocations; "
413 total_mapped
>> 20, n_allocated
, n_allocated
- n_freed
);
414 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
415 RegionInfo
*region
= GetRegionInfo(class_id
);
416 if (region
->mapped_user
== 0) continue;
417 Printf(" %02zd (%zd): total: %zd K allocs: %zd remains: %zd\n",
419 SizeClassMap::Size(class_id
),
420 region
->mapped_user
>> 10,
422 region
->n_allocated
- region
->n_freed
);
426 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
427 // introspection API.
429 for (uptr i
= 0; i
< kNumClasses
; i
++) {
430 GetRegionInfo(i
)->mutex
.Lock();
435 for (int i
= (int)kNumClasses
- 1; i
>= 0; i
--) {
436 GetRegionInfo(i
)->mutex
.Unlock();
440 // Iterate over all existing chunks.
441 // The allocator must be locked when calling this function.
442 void ForEachChunk(ForEachChunkCallback callback
, void *arg
) {
443 for (uptr class_id
= 1; class_id
< kNumClasses
; class_id
++) {
444 RegionInfo
*region
= GetRegionInfo(class_id
);
445 uptr chunk_size
= SizeClassMap::Size(class_id
);
446 uptr region_beg
= kSpaceBeg
+ class_id
* kRegionSize
;
447 for (uptr chunk
= region_beg
;
448 chunk
< region_beg
+ region
->allocated_user
;
449 chunk
+= chunk_size
) {
450 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
451 callback(chunk
, arg
);
456 typedef SizeClassMap SizeClassMapT
;
457 static const uptr kNumClasses
= SizeClassMap::kNumClasses
;
458 static const uptr kNumClassesRounded
= SizeClassMap::kNumClassesRounded
;
461 static const uptr kRegionSize
= kSpaceSize
/ kNumClassesRounded
;
462 static const uptr kSpaceEnd
= kSpaceBeg
+ kSpaceSize
;
463 COMPILER_CHECK(kSpaceBeg
% kSpaceSize
== 0);
464 // kRegionSize must be >= 2^32.
465 COMPILER_CHECK((kRegionSize
) >= (1ULL << (SANITIZER_WORDSIZE
/ 2)));
466 // Populate the free list with at most this number of bytes at once
467 // or with one element if its size is greater.
468 static const uptr kPopulateSize
= 1 << 14;
469 // Call mmap for user memory with at least this size.
470 static const uptr kUserMapSize
= 1 << 16;
471 // Call mmap for metadata memory with at least this size.
472 static const uptr kMetaMapSize
= 1 << 16;
476 LFStack
<Batch
> free_list
;
477 uptr allocated_user
; // Bytes allocated for user memory.
478 uptr allocated_meta
; // Bytes allocated for metadata.
479 uptr mapped_user
; // Bytes mapped for user memory.
480 uptr mapped_meta
; // Bytes mapped for metadata.
481 uptr n_allocated
, n_freed
; // Just stats.
483 COMPILER_CHECK(sizeof(RegionInfo
) >= kCacheLineSize
);
485 static uptr
AdditionalSize() {
486 return RoundUpTo(sizeof(RegionInfo
) * kNumClassesRounded
,
487 GetPageSizeCached());
490 RegionInfo
*GetRegionInfo(uptr class_id
) {
491 CHECK_LT(class_id
, kNumClasses
);
492 RegionInfo
*regions
= reinterpret_cast<RegionInfo
*>(kSpaceBeg
+ kSpaceSize
);
493 return ®ions
[class_id
];
496 static uptr
GetChunkIdx(uptr chunk
, uptr size
) {
497 uptr offset
= chunk
% kRegionSize
;
498 // Here we divide by a non-constant. This is costly.
499 // size always fits into 32-bits. If the offset fits too, use 32-bit div.
500 if (offset
>> (SANITIZER_WORDSIZE
/ 2))
501 return offset
/ size
;
502 return (u32
)offset
/ (u32
)size
;
505 NOINLINE Batch
* PopulateFreeList(AllocatorStats
*stat
, AllocatorCache
*c
,
506 uptr class_id
, RegionInfo
*region
) {
507 BlockingMutexLock
l(®ion
->mutex
);
508 Batch
*b
= region
->free_list
.Pop();
511 uptr size
= SizeClassMap::Size(class_id
);
512 uptr count
= size
< kPopulateSize
? SizeClassMap::MaxCached(class_id
) : 1;
513 uptr beg_idx
= region
->allocated_user
;
514 uptr end_idx
= beg_idx
+ count
* size
;
515 uptr region_beg
= kSpaceBeg
+ kRegionSize
* class_id
;
516 if (end_idx
+ size
> region
->mapped_user
) {
517 // Do the mmap for the user memory.
518 uptr map_size
= kUserMapSize
;
519 while (end_idx
+ size
> region
->mapped_user
+ map_size
)
520 map_size
+= kUserMapSize
;
521 CHECK_GE(region
->mapped_user
+ map_size
, end_idx
);
522 MapWithCallback(region_beg
+ region
->mapped_user
, map_size
);
523 stat
->Add(AllocatorStatMmapped
, map_size
);
524 region
->mapped_user
+= map_size
;
526 uptr total_count
= (region
->mapped_user
- beg_idx
- size
)
527 / size
/ count
* count
;
528 region
->allocated_meta
+= total_count
* kMetadataSize
;
529 if (region
->allocated_meta
> region
->mapped_meta
) {
530 uptr map_size
= kMetaMapSize
;
531 while (region
->allocated_meta
> region
->mapped_meta
+ map_size
)
532 map_size
+= kMetaMapSize
;
533 // Do the mmap for the metadata.
534 CHECK_GE(region
->mapped_meta
+ map_size
, region
->allocated_meta
);
535 MapWithCallback(region_beg
+ kRegionSize
-
536 region
->mapped_meta
- map_size
, map_size
);
537 region
->mapped_meta
+= map_size
;
539 CHECK_LE(region
->allocated_meta
, region
->mapped_meta
);
540 if (region
->mapped_user
+ region
->mapped_meta
> kRegionSize
) {
541 Printf("%s: Out of memory. Dying. ", SanitizerToolName
);
542 Printf("The process has exhausted %zuMB for size class %zu.\n",
543 kRegionSize
/ 1024 / 1024, size
);
547 if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id
))
548 b
= (Batch
*)c
->Allocate(this, SizeClassMap::ClassID(sizeof(Batch
)));
550 b
= (Batch
*)(region_beg
+ beg_idx
);
552 for (uptr i
= 0; i
< count
; i
++)
553 b
->batch
[i
] = (void*)(region_beg
+ beg_idx
+ i
* size
);
554 region
->allocated_user
+= count
* size
;
555 CHECK_LE(region
->allocated_user
, region
->mapped_user
);
556 beg_idx
+= count
* size
;
557 if (beg_idx
+ count
* size
+ size
> region
->mapped_user
)
559 CHECK_GT(b
->count
, 0);
560 region
->free_list
.Push(b
);
566 // Maps integers in rage [0, kSize) to u8 values.
570 void TestOnlyInit() {
571 internal_memset(map_
, 0, sizeof(map_
));
574 void set(uptr idx
, u8 val
) {
575 CHECK_LT(idx
, kSize
);
576 CHECK_EQ(0U, map_
[idx
]);
579 u8
operator[] (uptr idx
) {
580 CHECK_LT(idx
, kSize
);
581 // FIXME: CHECK may be too expensive here.
588 // TwoLevelByteMap maps integers in range [0, kSize1*kSize2) to u8 values.
589 // It is implemented as a two-dimensional array: array of kSize1 pointers
590 // to kSize2-byte arrays. The secondary arrays are mmaped on demand.
591 // Each value is initially zero and can be set to something else only once.
592 // Setting and getting values from multiple threads is safe w/o extra locking.
593 template <u64 kSize1
, u64 kSize2
, class MapUnmapCallback
= NoOpMapUnmapCallback
>
594 class TwoLevelByteMap
{
596 void TestOnlyInit() {
597 internal_memset(map1_
, 0, sizeof(map1_
));
600 void TestOnlyUnmap() {
601 for (uptr i
= 0; i
< kSize1
; i
++) {
604 MapUnmapCallback().OnUnmap(reinterpret_cast<uptr
>(p
), kSize2
);
605 UnmapOrDie(p
, kSize2
);
609 uptr
size() const { return kSize1
* kSize2
; }
610 uptr
size1() const { return kSize1
; }
611 uptr
size2() const { return kSize2
; }
613 void set(uptr idx
, u8 val
) {
614 CHECK_LT(idx
, kSize1
* kSize2
);
615 u8
*map2
= GetOrCreate(idx
/ kSize2
);
616 CHECK_EQ(0U, map2
[idx
% kSize2
]);
617 map2
[idx
% kSize2
] = val
;
620 u8
operator[] (uptr idx
) const {
621 CHECK_LT(idx
, kSize1
* kSize2
);
622 u8
*map2
= Get(idx
/ kSize2
);
624 return map2
[idx
% kSize2
];
628 u8
*Get(uptr idx
) const {
629 CHECK_LT(idx
, kSize1
);
630 return reinterpret_cast<u8
*>(
631 atomic_load(&map1_
[idx
], memory_order_acquire
));
634 u8
*GetOrCreate(uptr idx
) {
637 SpinMutexLock
l(&mu_
);
638 if (!(res
= Get(idx
))) {
639 res
= (u8
*)MmapOrDie(kSize2
, "TwoLevelByteMap");
640 MapUnmapCallback().OnMap(reinterpret_cast<uptr
>(res
), kSize2
);
641 atomic_store(&map1_
[idx
], reinterpret_cast<uptr
>(res
),
642 memory_order_release
);
648 atomic_uintptr_t map1_
[kSize1
];
652 // SizeClassAllocator32 -- allocator for 32-bit address space.
653 // This allocator can theoretically be used on 64-bit arch, but there it is less
654 // efficient than SizeClassAllocator64.
656 // [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can
657 // be returned by MmapOrDie().
660 // a result of a single call to MmapAlignedOrDie(kRegionSize, kRegionSize).
661 // Since the regions are aligned by kRegionSize, there are exactly
662 // kNumPossibleRegions possible regions in the address space and so we keep
663 // a ByteMap possible_regions to store the size classes of each Region.
664 // 0 size class means the region is not used by the allocator.
666 // One Region is used to allocate chunks of a single size class.
667 // A Region looks like this:
668 // UserChunk1 .. UserChunkN <gap> MetaChunkN .. MetaChunk1
670 // In order to avoid false sharing the objects of this class should be
671 // chache-line aligned.
672 template <const uptr kSpaceBeg
, const u64 kSpaceSize
,
673 const uptr kMetadataSize
, class SizeClassMap
,
674 const uptr kRegionSizeLog
,
676 class MapUnmapCallback
= NoOpMapUnmapCallback
>
677 class SizeClassAllocator32
{
679 typedef typename
SizeClassMap::TransferBatch Batch
;
680 typedef SizeClassAllocator32
<kSpaceBeg
, kSpaceSize
, kMetadataSize
,
681 SizeClassMap
, kRegionSizeLog
, ByteMap
, MapUnmapCallback
> ThisT
;
682 typedef SizeClassAllocatorLocalCache
<ThisT
> AllocatorCache
;
685 possible_regions
.TestOnlyInit();
686 internal_memset(size_class_info_array
, 0, sizeof(size_class_info_array
));
689 void *MapWithCallback(uptr size
) {
690 size
= RoundUpTo(size
, GetPageSizeCached());
691 void *res
= MmapOrDie(size
, "SizeClassAllocator32");
692 MapUnmapCallback().OnMap((uptr
)res
, size
);
696 void UnmapWithCallback(uptr beg
, uptr size
) {
697 MapUnmapCallback().OnUnmap(beg
, size
);
698 UnmapOrDie(reinterpret_cast<void *>(beg
), size
);
701 static bool CanAllocate(uptr size
, uptr alignment
) {
702 return size
<= SizeClassMap::kMaxSize
&&
703 alignment
<= SizeClassMap::kMaxSize
;
706 void *GetMetaData(const void *p
) {
707 CHECK(PointerIsMine(p
));
708 uptr mem
= reinterpret_cast<uptr
>(p
);
709 uptr beg
= ComputeRegionBeg(mem
);
710 uptr size
= SizeClassMap::Size(GetSizeClass(p
));
711 u32 offset
= mem
- beg
;
712 uptr n
= offset
/ (u32
)size
; // 32-bit division
713 uptr meta
= (beg
+ kRegionSize
) - (n
+ 1) * kMetadataSize
;
714 return reinterpret_cast<void*>(meta
);
717 NOINLINE Batch
* AllocateBatch(AllocatorStats
*stat
, AllocatorCache
*c
,
719 CHECK_LT(class_id
, kNumClasses
);
720 SizeClassInfo
*sci
= GetSizeClassInfo(class_id
);
721 SpinMutexLock
l(&sci
->mutex
);
722 if (sci
->free_list
.empty())
723 PopulateFreeList(stat
, c
, sci
, class_id
);
724 CHECK(!sci
->free_list
.empty());
725 Batch
*b
= sci
->free_list
.front();
726 sci
->free_list
.pop_front();
730 NOINLINE
void DeallocateBatch(AllocatorStats
*stat
, uptr class_id
, Batch
*b
) {
731 CHECK_LT(class_id
, kNumClasses
);
732 SizeClassInfo
*sci
= GetSizeClassInfo(class_id
);
733 SpinMutexLock
l(&sci
->mutex
);
734 CHECK_GT(b
->count
, 0);
735 sci
->free_list
.push_front(b
);
738 bool PointerIsMine(const void *p
) {
739 return GetSizeClass(p
) != 0;
742 uptr
GetSizeClass(const void *p
) {
743 return possible_regions
[ComputeRegionId(reinterpret_cast<uptr
>(p
))];
746 void *GetBlockBegin(const void *p
) {
747 CHECK(PointerIsMine(p
));
748 uptr mem
= reinterpret_cast<uptr
>(p
);
749 uptr beg
= ComputeRegionBeg(mem
);
750 uptr size
= SizeClassMap::Size(GetSizeClass(p
));
751 u32 offset
= mem
- beg
;
752 u32 n
= offset
/ (u32
)size
; // 32-bit division
753 uptr res
= beg
+ (n
* (u32
)size
);
754 return reinterpret_cast<void*>(res
);
757 uptr
GetActuallyAllocatedSize(void *p
) {
758 CHECK(PointerIsMine(p
));
759 return SizeClassMap::Size(GetSizeClass(p
));
762 uptr
ClassID(uptr size
) { return SizeClassMap::ClassID(size
); }
764 uptr
TotalMemoryUsed() {
765 // No need to lock here.
767 for (uptr i
= 0; i
< kNumPossibleRegions
; i
++)
768 if (possible_regions
[i
])
773 void TestOnlyUnmap() {
774 for (uptr i
= 0; i
< kNumPossibleRegions
; i
++)
775 if (possible_regions
[i
])
776 UnmapWithCallback((i
* kRegionSize
), kRegionSize
);
779 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
780 // introspection API.
782 for (uptr i
= 0; i
< kNumClasses
; i
++) {
783 GetSizeClassInfo(i
)->mutex
.Lock();
788 for (int i
= kNumClasses
- 1; i
>= 0; i
--) {
789 GetSizeClassInfo(i
)->mutex
.Unlock();
793 // Iterate over all existing chunks.
794 // The allocator must be locked when calling this function.
795 void ForEachChunk(ForEachChunkCallback callback
, void *arg
) {
796 for (uptr region
= 0; region
< kNumPossibleRegions
; region
++)
797 if (possible_regions
[region
]) {
798 uptr chunk_size
= SizeClassMap::Size(possible_regions
[region
]);
799 uptr max_chunks_in_region
= kRegionSize
/ (chunk_size
+ kMetadataSize
);
800 uptr region_beg
= region
* kRegionSize
;
801 for (uptr chunk
= region_beg
;
802 chunk
< region_beg
+ max_chunks_in_region
* chunk_size
;
803 chunk
+= chunk_size
) {
804 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
805 callback(chunk
, arg
);
813 typedef SizeClassMap SizeClassMapT
;
814 static const uptr kNumClasses
= SizeClassMap::kNumClasses
;
817 static const uptr kRegionSize
= 1 << kRegionSizeLog
;
818 static const uptr kNumPossibleRegions
= kSpaceSize
/ kRegionSize
;
820 struct SizeClassInfo
{
822 IntrusiveList
<Batch
> free_list
;
823 char padding
[kCacheLineSize
- sizeof(uptr
) - sizeof(IntrusiveList
<Batch
>)];
825 COMPILER_CHECK(sizeof(SizeClassInfo
) == kCacheLineSize
);
827 uptr
ComputeRegionId(uptr mem
) {
828 uptr res
= mem
>> kRegionSizeLog
;
829 CHECK_LT(res
, kNumPossibleRegions
);
833 uptr
ComputeRegionBeg(uptr mem
) {
834 return mem
& ~(kRegionSize
- 1);
837 uptr
AllocateRegion(AllocatorStats
*stat
, uptr class_id
) {
838 CHECK_LT(class_id
, kNumClasses
);
839 uptr res
= reinterpret_cast<uptr
>(MmapAlignedOrDie(kRegionSize
, kRegionSize
,
840 "SizeClassAllocator32"));
841 MapUnmapCallback().OnMap(res
, kRegionSize
);
842 stat
->Add(AllocatorStatMmapped
, kRegionSize
);
843 CHECK_EQ(0U, (res
& (kRegionSize
- 1)));
844 possible_regions
.set(ComputeRegionId(res
), static_cast<u8
>(class_id
));
848 SizeClassInfo
*GetSizeClassInfo(uptr class_id
) {
849 CHECK_LT(class_id
, kNumClasses
);
850 return &size_class_info_array
[class_id
];
853 void PopulateFreeList(AllocatorStats
*stat
, AllocatorCache
*c
,
854 SizeClassInfo
*sci
, uptr class_id
) {
855 uptr size
= SizeClassMap::Size(class_id
);
856 uptr reg
= AllocateRegion(stat
, class_id
);
857 uptr n_chunks
= kRegionSize
/ (size
+ kMetadataSize
);
858 uptr max_count
= SizeClassMap::MaxCached(class_id
);
860 for (uptr i
= reg
; i
< reg
+ n_chunks
* size
; i
+= size
) {
862 if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id
))
863 b
= (Batch
*)c
->Allocate(this, SizeClassMap::ClassID(sizeof(Batch
)));
868 b
->batch
[b
->count
++] = (void*)i
;
869 if (b
->count
== max_count
) {
870 CHECK_GT(b
->count
, 0);
871 sci
->free_list
.push_back(b
);
876 CHECK_GT(b
->count
, 0);
877 sci
->free_list
.push_back(b
);
881 ByteMap possible_regions
;
882 SizeClassInfo size_class_info_array
[kNumClasses
];
885 // Objects of this type should be used as local caches for SizeClassAllocator64
886 // or SizeClassAllocator32. Since the typical use of this class is to have one
887 // object per thread in TLS, is has to be POD.
888 template<class SizeClassAllocator
>
889 struct SizeClassAllocatorLocalCache
{
890 typedef SizeClassAllocator Allocator
;
891 static const uptr kNumClasses
= SizeClassAllocator::kNumClasses
;
893 void Init(AllocatorGlobalStats
*s
) {
896 s
->Register(&stats_
);
899 void Destroy(SizeClassAllocator
*allocator
, AllocatorGlobalStats
*s
) {
902 s
->Unregister(&stats_
);
905 void *Allocate(SizeClassAllocator
*allocator
, uptr class_id
) {
906 CHECK_NE(class_id
, 0UL);
907 CHECK_LT(class_id
, kNumClasses
);
908 stats_
.Add(AllocatorStatMalloced
, SizeClassMap::Size(class_id
));
909 PerClass
*c
= &per_class_
[class_id
];
910 if (UNLIKELY(c
->count
== 0))
911 Refill(allocator
, class_id
);
912 void *res
= c
->batch
[--c
->count
];
913 PREFETCH(c
->batch
[c
->count
- 1]);
917 void Deallocate(SizeClassAllocator
*allocator
, uptr class_id
, void *p
) {
918 CHECK_NE(class_id
, 0UL);
919 CHECK_LT(class_id
, kNumClasses
);
920 // If the first allocator call on a new thread is a deallocation, then
921 // max_count will be zero, leading to check failure.
923 stats_
.Add(AllocatorStatFreed
, SizeClassMap::Size(class_id
));
924 PerClass
*c
= &per_class_
[class_id
];
925 CHECK_NE(c
->max_count
, 0UL);
926 if (UNLIKELY(c
->count
== c
->max_count
))
927 Drain(allocator
, class_id
);
928 c
->batch
[c
->count
++] = p
;
931 void Drain(SizeClassAllocator
*allocator
) {
932 for (uptr class_id
= 0; class_id
< kNumClasses
; class_id
++) {
933 PerClass
*c
= &per_class_
[class_id
];
935 Drain(allocator
, class_id
);
940 typedef typename
SizeClassAllocator::SizeClassMapT SizeClassMap
;
941 typedef typename
SizeClassMap::TransferBatch Batch
;
945 void *batch
[2 * SizeClassMap::kMaxNumCached
];
947 PerClass per_class_
[kNumClasses
];
948 AllocatorStats stats_
;
951 if (per_class_
[1].max_count
)
953 for (uptr i
= 0; i
< kNumClasses
; i
++) {
954 PerClass
*c
= &per_class_
[i
];
955 c
->max_count
= 2 * SizeClassMap::MaxCached(i
);
959 NOINLINE
void Refill(SizeClassAllocator
*allocator
, uptr class_id
) {
961 PerClass
*c
= &per_class_
[class_id
];
962 Batch
*b
= allocator
->AllocateBatch(&stats_
, this, class_id
);
963 CHECK_GT(b
->count
, 0);
964 for (uptr i
= 0; i
< b
->count
; i
++)
965 c
->batch
[i
] = b
->batch
[i
];
967 if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id
))
968 Deallocate(allocator
, SizeClassMap::ClassID(sizeof(Batch
)), b
);
971 NOINLINE
void Drain(SizeClassAllocator
*allocator
, uptr class_id
) {
973 PerClass
*c
= &per_class_
[class_id
];
975 if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id
))
976 b
= (Batch
*)Allocate(allocator
, SizeClassMap::ClassID(sizeof(Batch
)));
978 b
= (Batch
*)c
->batch
[0];
979 uptr cnt
= Min(c
->max_count
/ 2, c
->count
);
980 for (uptr i
= 0; i
< cnt
; i
++) {
981 b
->batch
[i
] = c
->batch
[i
];
982 c
->batch
[i
] = c
->batch
[i
+ c
->max_count
/ 2];
986 CHECK_GT(b
->count
, 0);
987 allocator
->DeallocateBatch(&stats_
, class_id
, b
);
991 // This class can (de)allocate only large chunks of memory using mmap/unmap.
992 // The main purpose of this allocator is to cover large and rare allocation
993 // sizes not covered by more efficient allocators (e.g. SizeClassAllocator64).
994 template <class MapUnmapCallback
= NoOpMapUnmapCallback
>
995 class LargeMmapAllocator
{
998 internal_memset(this, 0, sizeof(*this));
999 page_size_
= GetPageSizeCached();
1002 void *Allocate(AllocatorStats
*stat
, uptr size
, uptr alignment
) {
1003 CHECK(IsPowerOfTwo(alignment
));
1004 uptr map_size
= RoundUpMapSize(size
);
1005 if (alignment
> page_size_
)
1006 map_size
+= alignment
;
1007 if (map_size
< size
) return AllocatorReturnNull(); // Overflow.
1008 uptr map_beg
= reinterpret_cast<uptr
>(
1009 MmapOrDie(map_size
, "LargeMmapAllocator"));
1010 MapUnmapCallback().OnMap(map_beg
, map_size
);
1011 uptr map_end
= map_beg
+ map_size
;
1012 uptr res
= map_beg
+ page_size_
;
1013 if (res
& (alignment
- 1)) // Align.
1014 res
+= alignment
- (res
& (alignment
- 1));
1015 CHECK_EQ(0, res
& (alignment
- 1));
1016 CHECK_LE(res
+ size
, map_end
);
1017 Header
*h
= GetHeader(res
);
1019 h
->map_beg
= map_beg
;
1020 h
->map_size
= map_size
;
1021 uptr size_log
= MostSignificantSetBitIndex(map_size
);
1022 CHECK_LT(size_log
, ARRAY_SIZE(stats
.by_size_log
));
1024 SpinMutexLock
l(&mutex_
);
1025 uptr idx
= n_chunks_
++;
1026 chunks_sorted_
= false;
1027 CHECK_LT(idx
, kMaxNumChunks
);
1031 stats
.currently_allocated
+= map_size
;
1032 stats
.max_allocated
= Max(stats
.max_allocated
, stats
.currently_allocated
);
1033 stats
.by_size_log
[size_log
]++;
1034 stat
->Add(AllocatorStatMalloced
, map_size
);
1035 stat
->Add(AllocatorStatMmapped
, map_size
);
1037 return reinterpret_cast<void*>(res
);
1040 void Deallocate(AllocatorStats
*stat
, void *p
) {
1041 Header
*h
= GetHeader(p
);
1043 SpinMutexLock
l(&mutex_
);
1044 uptr idx
= h
->chunk_idx
;
1045 CHECK_EQ(chunks_
[idx
], h
);
1046 CHECK_LT(idx
, n_chunks_
);
1047 chunks_
[idx
] = chunks_
[n_chunks_
- 1];
1048 chunks_
[idx
]->chunk_idx
= idx
;
1050 chunks_sorted_
= false;
1052 stats
.currently_allocated
-= h
->map_size
;
1053 stat
->Add(AllocatorStatFreed
, h
->map_size
);
1054 stat
->Add(AllocatorStatUnmapped
, h
->map_size
);
1056 MapUnmapCallback().OnUnmap(h
->map_beg
, h
->map_size
);
1057 UnmapOrDie(reinterpret_cast<void*>(h
->map_beg
), h
->map_size
);
1060 uptr
TotalMemoryUsed() {
1061 SpinMutexLock
l(&mutex_
);
1063 for (uptr i
= 0; i
< n_chunks_
; i
++) {
1064 Header
*h
= chunks_
[i
];
1065 CHECK_EQ(h
->chunk_idx
, i
);
1066 res
+= RoundUpMapSize(h
->size
);
1071 bool PointerIsMine(const void *p
) {
1072 return GetBlockBegin(p
) != 0;
1075 uptr
GetActuallyAllocatedSize(void *p
) {
1076 return RoundUpTo(GetHeader(p
)->size
, page_size_
);
1079 // At least page_size_/2 metadata bytes is available.
1080 void *GetMetaData(const void *p
) {
1081 // Too slow: CHECK_EQ(p, GetBlockBegin(p));
1082 if (!IsAligned(reinterpret_cast<uptr
>(p
), page_size_
)) {
1083 Printf("%s: bad pointer %p\n", SanitizerToolName
, p
);
1084 CHECK(IsAligned(reinterpret_cast<uptr
>(p
), page_size_
));
1086 return GetHeader(p
) + 1;
1089 void *GetBlockBegin(const void *ptr
) {
1090 uptr p
= reinterpret_cast<uptr
>(ptr
);
1091 SpinMutexLock
l(&mutex_
);
1092 uptr nearest_chunk
= 0;
1093 // Cache-friendly linear search.
1094 for (uptr i
= 0; i
< n_chunks_
; i
++) {
1095 uptr ch
= reinterpret_cast<uptr
>(chunks_
[i
]);
1096 if (p
< ch
) continue; // p is at left to this chunk, skip it.
1097 if (p
- ch
< p
- nearest_chunk
)
1102 Header
*h
= reinterpret_cast<Header
*>(nearest_chunk
);
1103 CHECK_GE(nearest_chunk
, h
->map_beg
);
1104 CHECK_LT(nearest_chunk
, h
->map_beg
+ h
->map_size
);
1105 CHECK_LE(nearest_chunk
, p
);
1106 if (h
->map_beg
+ h
->map_size
<= p
)
1111 // This function does the same as GetBlockBegin, but is much faster.
1112 // Must be called with the allocator locked.
1113 void *GetBlockBeginFastLocked(void *ptr
) {
1114 mutex_
.CheckLocked();
1115 uptr p
= reinterpret_cast<uptr
>(ptr
);
1118 if (!chunks_sorted_
) {
1119 // Do one-time sort. chunks_sorted_ is reset in Allocate/Deallocate.
1120 SortArray(reinterpret_cast<uptr
*>(chunks_
), n
);
1121 for (uptr i
= 0; i
< n
; i
++)
1122 chunks_
[i
]->chunk_idx
= i
;
1123 chunks_sorted_
= true;
1124 min_mmap_
= reinterpret_cast<uptr
>(chunks_
[0]);
1125 max_mmap_
= reinterpret_cast<uptr
>(chunks_
[n
- 1]) +
1126 chunks_
[n
- 1]->map_size
;
1128 if (p
< min_mmap_
|| p
>= max_mmap_
)
1130 uptr beg
= 0, end
= n
- 1;
1131 // This loop is a log(n) lower_bound. It does not check for the exact match
1132 // to avoid expensive cache-thrashing loads.
1133 while (end
- beg
>= 2) {
1134 uptr mid
= (beg
+ end
) / 2; // Invariant: mid >= beg + 1
1135 if (p
< reinterpret_cast<uptr
>(chunks_
[mid
]))
1136 end
= mid
- 1; // We are not interested in chunks_[mid].
1138 beg
= mid
; // chunks_[mid] may still be what we want.
1142 CHECK_EQ(beg
+ 1, end
);
1143 // There are 2 chunks left, choose one.
1144 if (p
>= reinterpret_cast<uptr
>(chunks_
[end
]))
1148 Header
*h
= chunks_
[beg
];
1149 if (h
->map_beg
+ h
->map_size
<= p
|| p
< h
->map_beg
)
1155 Printf("Stats: LargeMmapAllocator: allocated %zd times, "
1156 "remains %zd (%zd K) max %zd M; by size logs: ",
1157 stats
.n_allocs
, stats
.n_allocs
- stats
.n_frees
,
1158 stats
.currently_allocated
>> 10, stats
.max_allocated
>> 20);
1159 for (uptr i
= 0; i
< ARRAY_SIZE(stats
.by_size_log
); i
++) {
1160 uptr c
= stats
.by_size_log
[i
];
1162 Printf("%zd:%zd; ", i
, c
);
1167 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
1168 // introspection API.
1173 void ForceUnlock() {
1177 // Iterate over all existing chunks.
1178 // The allocator must be locked when calling this function.
1179 void ForEachChunk(ForEachChunkCallback callback
, void *arg
) {
1180 for (uptr i
= 0; i
< n_chunks_
; i
++)
1181 callback(reinterpret_cast<uptr
>(GetUser(chunks_
[i
])), arg
);
1185 static const int kMaxNumChunks
= 1 << FIRST_32_SECOND_64(15, 18);
1193 Header
*GetHeader(uptr p
) {
1194 CHECK(IsAligned(p
, page_size_
));
1195 return reinterpret_cast<Header
*>(p
- page_size_
);
1197 Header
*GetHeader(const void *p
) {
1198 return GetHeader(reinterpret_cast<uptr
>(p
));
1201 void *GetUser(Header
*h
) {
1202 CHECK(IsAligned((uptr
)h
, page_size_
));
1203 return reinterpret_cast<void*>(reinterpret_cast<uptr
>(h
) + page_size_
);
1206 uptr
RoundUpMapSize(uptr size
) {
1207 return RoundUpTo(size
, page_size_
) + page_size_
;
1211 Header
*chunks_
[kMaxNumChunks
];
1213 uptr min_mmap_
, max_mmap_
;
1214 bool chunks_sorted_
;
1216 uptr n_allocs
, n_frees
, currently_allocated
, max_allocated
, by_size_log
[64];
1221 // This class implements a complete memory allocator by using two
1222 // internal allocators:
1223 // PrimaryAllocator is efficient, but may not allocate some sizes (alignments).
1224 // When allocating 2^x bytes it should return 2^x aligned chunk.
1225 // PrimaryAllocator is used via a local AllocatorCache.
1226 // SecondaryAllocator can allocate anything, but is not efficient.
1227 template <class PrimaryAllocator
, class AllocatorCache
,
1228 class SecondaryAllocator
> // NOLINT
1229 class CombinedAllocator
{
1237 void *Allocate(AllocatorCache
*cache
, uptr size
, uptr alignment
,
1238 bool cleared
= false) {
1239 // Returning 0 on malloc(0) may break a lot of code.
1242 if (size
+ alignment
< size
)
1243 return AllocatorReturnNull();
1245 size
= RoundUpTo(size
, alignment
);
1247 bool from_primary
= primary_
.CanAllocate(size
, alignment
);
1249 res
= cache
->Allocate(&primary_
, primary_
.ClassID(size
));
1251 res
= secondary_
.Allocate(&stats_
, size
, alignment
);
1253 CHECK_EQ(reinterpret_cast<uptr
>(res
) & (alignment
- 1), 0);
1254 if (cleared
&& res
&& from_primary
)
1255 internal_bzero_aligned16(res
, RoundUpTo(size
, 16));
1259 void Deallocate(AllocatorCache
*cache
, void *p
) {
1261 if (primary_
.PointerIsMine(p
))
1262 cache
->Deallocate(&primary_
, primary_
.GetSizeClass(p
), p
);
1264 secondary_
.Deallocate(&stats_
, p
);
1267 void *Reallocate(AllocatorCache
*cache
, void *p
, uptr new_size
,
1270 return Allocate(cache
, new_size
, alignment
);
1272 Deallocate(cache
, p
);
1275 CHECK(PointerIsMine(p
));
1276 uptr old_size
= GetActuallyAllocatedSize(p
);
1277 uptr memcpy_size
= Min(new_size
, old_size
);
1278 void *new_p
= Allocate(cache
, new_size
, alignment
);
1280 internal_memcpy(new_p
, p
, memcpy_size
);
1281 Deallocate(cache
, p
);
1285 bool PointerIsMine(void *p
) {
1286 if (primary_
.PointerIsMine(p
))
1288 return secondary_
.PointerIsMine(p
);
1291 bool FromPrimary(void *p
) {
1292 return primary_
.PointerIsMine(p
);
1295 void *GetMetaData(const void *p
) {
1296 if (primary_
.PointerIsMine(p
))
1297 return primary_
.GetMetaData(p
);
1298 return secondary_
.GetMetaData(p
);
1301 void *GetBlockBegin(const void *p
) {
1302 if (primary_
.PointerIsMine(p
))
1303 return primary_
.GetBlockBegin(p
);
1304 return secondary_
.GetBlockBegin(p
);
1307 // This function does the same as GetBlockBegin, but is much faster.
1308 // Must be called with the allocator locked.
1309 void *GetBlockBeginFastLocked(void *p
) {
1310 if (primary_
.PointerIsMine(p
))
1311 return primary_
.GetBlockBegin(p
);
1312 return secondary_
.GetBlockBeginFastLocked(p
);
1315 uptr
GetActuallyAllocatedSize(void *p
) {
1316 if (primary_
.PointerIsMine(p
))
1317 return primary_
.GetActuallyAllocatedSize(p
);
1318 return secondary_
.GetActuallyAllocatedSize(p
);
1321 uptr
TotalMemoryUsed() {
1322 return primary_
.TotalMemoryUsed() + secondary_
.TotalMemoryUsed();
1325 void TestOnlyUnmap() { primary_
.TestOnlyUnmap(); }
1327 void InitCache(AllocatorCache
*cache
) {
1328 cache
->Init(&stats_
);
1331 void DestroyCache(AllocatorCache
*cache
) {
1332 cache
->Destroy(&primary_
, &stats_
);
1335 void SwallowCache(AllocatorCache
*cache
) {
1336 cache
->Drain(&primary_
);
1339 void GetStats(AllocatorStatCounters s
) const {
1344 primary_
.PrintStats();
1345 secondary_
.PrintStats();
1348 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
1349 // introspection API.
1351 primary_
.ForceLock();
1352 secondary_
.ForceLock();
1355 void ForceUnlock() {
1356 secondary_
.ForceUnlock();
1357 primary_
.ForceUnlock();
1360 // Iterate over all existing chunks.
1361 // The allocator must be locked when calling this function.
1362 void ForEachChunk(ForEachChunkCallback callback
, void *arg
) {
1363 primary_
.ForEachChunk(callback
, arg
);
1364 secondary_
.ForEachChunk(callback
, arg
);
1368 PrimaryAllocator primary_
;
1369 SecondaryAllocator secondary_
;
1370 AllocatorGlobalStats stats_
;
1373 // Returns true if calloc(size, n) should return 0 due to overflow in size*n.
1374 bool CallocShouldReturnNullDueToOverflow(uptr size
, uptr n
);
1376 } // namespace __sanitizer
1378 #endif // SANITIZER_ALLOCATOR_H