1 //===-- sanitizer_allocator_primary32.h -------------------------*- C++ -*-===//
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
6 //===----------------------------------------------------------------------===//
8 // Part of the Sanitizer Allocator.
10 //===----------------------------------------------------------------------===//
11 #ifndef SANITIZER_ALLOCATOR_H
12 #error This file must be included inside sanitizer_allocator.h
15 template<class SizeClassAllocator
> struct SizeClassAllocator32LocalCache
;
17 // SizeClassAllocator32 -- allocator for 32-bit address space.
18 // This allocator can theoretically be used on 64-bit arch, but there it is less
19 // efficient than SizeClassAllocator64.
21 // [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can
22 // be returned by MmapOrDie().
25 // a result of a single call to MmapAlignedOrDieOnFatalError(kRegionSize,
27 // Since the regions are aligned by kRegionSize, there are exactly
28 // kNumPossibleRegions possible regions in the address space and so we keep
29 // a ByteMap possible_regions to store the size classes of each Region.
30 // 0 size class means the region is not used by the allocator.
32 // One Region is used to allocate chunks of a single size class.
33 // A Region looks like this:
34 // UserChunk1 .. UserChunkN <gap> MetaChunkN .. MetaChunk1
36 // In order to avoid false sharing the objects of this class should be
37 // chache-line aligned.
39 struct SizeClassAllocator32FlagMasks
{ // Bit masks.
41 kRandomShuffleChunks
= 1,
42 kUseSeparateSizeClassForBatch
= 2,
46 template <class Params
>
47 class SizeClassAllocator32
{
49 static const uptr kSpaceBeg
= Params::kSpaceBeg
;
50 static const u64 kSpaceSize
= Params::kSpaceSize
;
51 static const uptr kMetadataSize
= Params::kMetadataSize
;
52 typedef typename
Params::SizeClassMap SizeClassMap
;
53 static const uptr kRegionSizeLog
= Params::kRegionSizeLog
;
54 typedef typename
Params::ByteMap ByteMap
;
55 typedef typename
Params::MapUnmapCallback MapUnmapCallback
;
57 static const bool kRandomShuffleChunks
= Params::kFlags
&
58 SizeClassAllocator32FlagMasks::kRandomShuffleChunks
;
59 static const bool kUseSeparateSizeClassForBatch
= Params::kFlags
&
60 SizeClassAllocator32FlagMasks::kUseSeparateSizeClassForBatch
;
62 struct TransferBatch
{
63 static const uptr kMaxNumCached
= SizeClassMap::kMaxNumCachedHint
- 2;
64 void SetFromArray(void *batch
[], uptr count
) {
65 DCHECK_LE(count
, kMaxNumCached
);
67 for (uptr i
= 0; i
< count
; i
++)
70 uptr
Count() const { return count_
; }
71 void Clear() { count_
= 0; }
73 batch_
[count_
++] = ptr
;
74 DCHECK_LE(count_
, kMaxNumCached
);
76 void CopyToArray(void *to_batch
[]) const {
77 for (uptr i
= 0, n
= Count(); i
< n
; i
++)
78 to_batch
[i
] = batch_
[i
];
81 // How much memory do we need for a batch containing n elements.
82 static uptr
AllocationSizeRequiredForNElements(uptr n
) {
83 return sizeof(uptr
) * 2 + sizeof(void *) * n
;
85 static uptr
MaxCached(uptr size
) {
86 return Min(kMaxNumCached
, SizeClassMap::MaxCachedHint(size
));
93 void *batch_
[kMaxNumCached
];
96 static const uptr kBatchSize
= sizeof(TransferBatch
);
97 COMPILER_CHECK((kBatchSize
& (kBatchSize
- 1)) == 0);
98 COMPILER_CHECK(kBatchSize
== SizeClassMap::kMaxNumCachedHint
* sizeof(uptr
));
100 static uptr
ClassIdToSize(uptr class_id
) {
101 return (class_id
== SizeClassMap::kBatchClassID
) ?
102 kBatchSize
: SizeClassMap::Size(class_id
);
105 typedef SizeClassAllocator32
<Params
> ThisT
;
106 typedef SizeClassAllocator32LocalCache
<ThisT
> AllocatorCache
;
108 void Init(s32 release_to_os_interval_ms
) {
109 possible_regions
.Init();
110 internal_memset(size_class_info_array
, 0, sizeof(size_class_info_array
));
113 s32
ReleaseToOSIntervalMs() const {
114 return kReleaseToOSIntervalNever
;
117 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms
) {
118 // This is empty here. Currently only implemented in 64-bit allocator.
121 void ForceReleaseToOS() {
122 // Currently implemented in 64-bit allocator only.
125 void *MapWithCallback(uptr size
) {
126 void *res
= MmapOrDie(size
, PrimaryAllocatorName
);
127 MapUnmapCallback().OnMap((uptr
)res
, size
);
131 void UnmapWithCallback(uptr beg
, uptr size
) {
132 MapUnmapCallback().OnUnmap(beg
, size
);
133 UnmapOrDie(reinterpret_cast<void *>(beg
), size
);
136 static bool CanAllocate(uptr size
, uptr alignment
) {
137 return size
<= SizeClassMap::kMaxSize
&&
138 alignment
<= SizeClassMap::kMaxSize
;
141 void *GetMetaData(const void *p
) {
142 CHECK(PointerIsMine(p
));
143 uptr mem
= reinterpret_cast<uptr
>(p
);
144 uptr beg
= ComputeRegionBeg(mem
);
145 uptr size
= ClassIdToSize(GetSizeClass(p
));
146 u32 offset
= mem
- beg
;
147 uptr n
= offset
/ (u32
)size
; // 32-bit division
148 uptr meta
= (beg
+ kRegionSize
) - (n
+ 1) * kMetadataSize
;
149 return reinterpret_cast<void*>(meta
);
152 NOINLINE TransferBatch
*AllocateBatch(AllocatorStats
*stat
, AllocatorCache
*c
,
154 DCHECK_LT(class_id
, kNumClasses
);
155 SizeClassInfo
*sci
= GetSizeClassInfo(class_id
);
156 SpinMutexLock
l(&sci
->mutex
);
157 if (sci
->free_list
.empty()) {
158 if (UNLIKELY(!PopulateFreeList(stat
, c
, sci
, class_id
)))
160 DCHECK(!sci
->free_list
.empty());
162 TransferBatch
*b
= sci
->free_list
.front();
163 sci
->free_list
.pop_front();
167 NOINLINE
void DeallocateBatch(AllocatorStats
*stat
, uptr class_id
,
169 DCHECK_LT(class_id
, kNumClasses
);
170 CHECK_GT(b
->Count(), 0);
171 SizeClassInfo
*sci
= GetSizeClassInfo(class_id
);
172 SpinMutexLock
l(&sci
->mutex
);
173 sci
->free_list
.push_front(b
);
176 bool PointerIsMine(const void *p
) {
177 uptr mem
= reinterpret_cast<uptr
>(p
);
178 if (mem
< kSpaceBeg
|| mem
>= kSpaceBeg
+ kSpaceSize
)
180 return GetSizeClass(p
) != 0;
183 uptr
GetSizeClass(const void *p
) {
184 return possible_regions
[ComputeRegionId(reinterpret_cast<uptr
>(p
))];
187 void *GetBlockBegin(const void *p
) {
188 CHECK(PointerIsMine(p
));
189 uptr mem
= reinterpret_cast<uptr
>(p
);
190 uptr beg
= ComputeRegionBeg(mem
);
191 uptr size
= ClassIdToSize(GetSizeClass(p
));
192 u32 offset
= mem
- beg
;
193 u32 n
= offset
/ (u32
)size
; // 32-bit division
194 uptr res
= beg
+ (n
* (u32
)size
);
195 return reinterpret_cast<void*>(res
);
198 uptr
GetActuallyAllocatedSize(void *p
) {
199 CHECK(PointerIsMine(p
));
200 return ClassIdToSize(GetSizeClass(p
));
203 uptr
ClassID(uptr size
) { return SizeClassMap::ClassID(size
); }
205 uptr
TotalMemoryUsed() {
206 // No need to lock here.
208 for (uptr i
= 0; i
< kNumPossibleRegions
; i
++)
209 if (possible_regions
[i
])
214 void TestOnlyUnmap() {
215 for (uptr i
= 0; i
< kNumPossibleRegions
; i
++)
216 if (possible_regions
[i
])
217 UnmapWithCallback((i
* kRegionSize
), kRegionSize
);
220 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
221 // introspection API.
223 for (uptr i
= 0; i
< kNumClasses
; i
++) {
224 GetSizeClassInfo(i
)->mutex
.Lock();
229 for (int i
= kNumClasses
- 1; i
>= 0; i
--) {
230 GetSizeClassInfo(i
)->mutex
.Unlock();
234 // Iterate over all existing chunks.
235 // The allocator must be locked when calling this function.
236 void ForEachChunk(ForEachChunkCallback callback
, void *arg
) {
237 for (uptr region
= 0; region
< kNumPossibleRegions
; region
++)
238 if (possible_regions
[region
]) {
239 uptr chunk_size
= ClassIdToSize(possible_regions
[region
]);
240 uptr max_chunks_in_region
= kRegionSize
/ (chunk_size
+ kMetadataSize
);
241 uptr region_beg
= region
* kRegionSize
;
242 for (uptr chunk
= region_beg
;
243 chunk
< region_beg
+ max_chunks_in_region
* chunk_size
;
244 chunk
+= chunk_size
) {
245 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
246 callback(chunk
, arg
);
253 static uptr
AdditionalSize() { return 0; }
255 typedef SizeClassMap SizeClassMapT
;
256 static const uptr kNumClasses
= SizeClassMap::kNumClasses
;
259 static const uptr kRegionSize
= 1 << kRegionSizeLog
;
260 static const uptr kNumPossibleRegions
= kSpaceSize
/ kRegionSize
;
262 struct ALIGNED(SANITIZER_CACHE_LINE_SIZE
) SizeClassInfo
{
263 StaticSpinMutex mutex
;
264 IntrusiveList
<TransferBatch
> free_list
;
267 COMPILER_CHECK(sizeof(SizeClassInfo
) % kCacheLineSize
== 0);
269 uptr
ComputeRegionId(uptr mem
) {
270 const uptr res
= mem
>> kRegionSizeLog
;
271 CHECK_LT(res
, kNumPossibleRegions
);
275 uptr
ComputeRegionBeg(uptr mem
) {
276 return mem
& ~(kRegionSize
- 1);
279 uptr
AllocateRegion(AllocatorStats
*stat
, uptr class_id
) {
280 DCHECK_LT(class_id
, kNumClasses
);
281 const uptr res
= reinterpret_cast<uptr
>(MmapAlignedOrDieOnFatalError(
282 kRegionSize
, kRegionSize
, PrimaryAllocatorName
));
285 MapUnmapCallback().OnMap(res
, kRegionSize
);
286 stat
->Add(AllocatorStatMapped
, kRegionSize
);
287 CHECK(IsAligned(res
, kRegionSize
));
288 possible_regions
.set(ComputeRegionId(res
), static_cast<u8
>(class_id
));
292 SizeClassInfo
*GetSizeClassInfo(uptr class_id
) {
293 DCHECK_LT(class_id
, kNumClasses
);
294 return &size_class_info_array
[class_id
];
297 bool PopulateBatches(AllocatorCache
*c
, SizeClassInfo
*sci
, uptr class_id
,
298 TransferBatch
**current_batch
, uptr max_count
,
299 uptr
*pointers_array
, uptr count
) {
300 // If using a separate class for batches, we do not need to shuffle it.
301 if (kRandomShuffleChunks
&& (!kUseSeparateSizeClassForBatch
||
302 class_id
!= SizeClassMap::kBatchClassID
))
303 RandomShuffle(pointers_array
, count
, &sci
->rand_state
);
304 TransferBatch
*b
= *current_batch
;
305 for (uptr i
= 0; i
< count
; i
++) {
307 b
= c
->CreateBatch(class_id
, this, (TransferBatch
*)pointers_array
[i
]);
312 b
->Add((void*)pointers_array
[i
]);
313 if (b
->Count() == max_count
) {
314 sci
->free_list
.push_back(b
);
322 bool PopulateFreeList(AllocatorStats
*stat
, AllocatorCache
*c
,
323 SizeClassInfo
*sci
, uptr class_id
) {
324 const uptr region
= AllocateRegion(stat
, class_id
);
325 if (UNLIKELY(!region
))
327 if (kRandomShuffleChunks
)
328 if (UNLIKELY(sci
->rand_state
== 0))
329 // The random state is initialized from ASLR (PIE) and time.
330 sci
->rand_state
= reinterpret_cast<uptr
>(sci
) ^ NanoTime();
331 const uptr size
= ClassIdToSize(class_id
);
332 const uptr n_chunks
= kRegionSize
/ (size
+ kMetadataSize
);
333 const uptr max_count
= TransferBatch::MaxCached(size
);
334 DCHECK_GT(max_count
, 0);
335 TransferBatch
*b
= nullptr;
336 constexpr uptr kShuffleArraySize
= 48;
337 uptr shuffle_array
[kShuffleArraySize
];
339 for (uptr i
= region
; i
< region
+ n_chunks
* size
; i
+= size
) {
340 shuffle_array
[count
++] = i
;
341 if (count
== kShuffleArraySize
) {
342 if (UNLIKELY(!PopulateBatches(c
, sci
, class_id
, &b
, max_count
,
343 shuffle_array
, count
)))
349 if (UNLIKELY(!PopulateBatches(c
, sci
, class_id
, &b
, max_count
,
350 shuffle_array
, count
)))
354 CHECK_GT(b
->Count(), 0);
355 sci
->free_list
.push_back(b
);
360 ByteMap possible_regions
;
361 SizeClassInfo size_class_info_array
[kNumClasses
];