1 | //===-- sanitizer_allocator_primary64.h -------------------------*- C++ -*-===// |
---|---|
2 | // |
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 |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // Part of the Sanitizer Allocator. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | #ifndef SANITIZER_ALLOCATOR_H |
13 | #error This file must be included inside sanitizer_allocator.h |
14 | #endif |
15 | |
16 | template<class SizeClassAllocator> struct SizeClassAllocator64LocalCache; |
17 | |
18 | // SizeClassAllocator64 -- allocator for 64-bit address space. |
19 | // The template parameter Params is a class containing the actual parameters. |
20 | // |
21 | // Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg. |
22 | // If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically by 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. |
27 | // |
28 | // Region: a part of Space dedicated to a single size class. |
29 | // There are kNumClasses Regions of equal size. |
30 | // |
31 | // UserChunk: a piece of memory returned to user. |
32 | // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk. |
33 | |
34 | // FreeArray is an array free-d chunks (stored as 4-byte offsets) |
35 | // |
36 | // A Region looks like this: |
37 | // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray |
38 | |
39 | struct SizeClassAllocator64FlagMasks { // Bit masks. |
40 | enum { |
41 | kRandomShuffleChunks = 1, |
42 | }; |
43 | }; |
44 | |
45 | template <typename Allocator> |
46 | class MemoryMapper { |
47 | public: |
48 | typedef typename Allocator::CompactPtrT CompactPtrT; |
49 | |
50 | explicit MemoryMapper(const Allocator &allocator) : allocator_(allocator) {} |
51 | |
52 | bool GetAndResetStats(uptr &ranges, uptr &bytes) { |
53 | ranges = released_ranges_count_; |
54 | released_ranges_count_ = 0; |
55 | bytes = released_bytes_; |
56 | released_bytes_ = 0; |
57 | return ranges != 0; |
58 | } |
59 | |
60 | u64 *MapPackedCounterArrayBuffer(uptr count) { |
61 | buffer_.clear(); |
62 | buffer_.resize(new_size: count); |
63 | return buffer_.data(); |
64 | } |
65 | |
66 | // Releases [from, to) range of pages back to OS. |
67 | void ReleasePageRangeToOS(uptr class_id, CompactPtrT from, CompactPtrT to) { |
68 | const uptr region_base = allocator_.GetRegionBeginBySizeClass(class_id); |
69 | const uptr from_page = allocator_.CompactPtrToPointer(region_base, from); |
70 | const uptr to_page = allocator_.CompactPtrToPointer(region_base, to); |
71 | ReleaseMemoryPagesToOS(beg: from_page, end: to_page); |
72 | released_ranges_count_++; |
73 | released_bytes_ += to_page - from_page; |
74 | } |
75 | |
76 | private: |
77 | const Allocator &allocator_; |
78 | uptr released_ranges_count_ = 0; |
79 | uptr released_bytes_ = 0; |
80 | InternalMmapVector<u64> buffer_; |
81 | }; |
82 | |
83 | template <class Params> |
84 | class SizeClassAllocator64 { |
85 | public: |
86 | using AddressSpaceView = typename Params::AddressSpaceView; |
87 | static const uptr kSpaceBeg = Params::kSpaceBeg; |
88 | static const uptr kSpaceSize = Params::kSpaceSize; |
89 | static const uptr kMetadataSize = Params::kMetadataSize; |
90 | typedef typename Params::SizeClassMap SizeClassMap; |
91 | typedef typename Params::MapUnmapCallback MapUnmapCallback; |
92 | |
93 | static const bool kRandomShuffleChunks = |
94 | Params::kFlags & SizeClassAllocator64FlagMasks::kRandomShuffleChunks; |
95 | |
96 | typedef SizeClassAllocator64<Params> ThisT; |
97 | typedef SizeClassAllocator64LocalCache<ThisT> AllocatorCache; |
98 | typedef MemoryMapper<ThisT> MemoryMapperT; |
99 | |
100 | // When we know the size class (the region base) we can represent a pointer |
101 | // as a 4-byte integer (offset from the region start shifted right by 4). |
102 | typedef u32 CompactPtrT; |
103 | static const uptr kCompactPtrScale = 4; |
104 | CompactPtrT PointerToCompactPtr(uptr base, uptr ptr) const { |
105 | return static_cast<CompactPtrT>((ptr - base) >> kCompactPtrScale); |
106 | } |
107 | uptr CompactPtrToPointer(uptr base, CompactPtrT ptr32) const { |
108 | return base + (static_cast<uptr>(ptr32) << kCompactPtrScale); |
109 | } |
110 | |
111 | // If heap_start is nonzero, assumes kSpaceSize bytes are already mapped R/W |
112 | // at heap_start and places the heap there. This mode requires kSpaceBeg == |
113 | // ~(uptr)0. |
114 | void Init(s32 release_to_os_interval_ms, uptr heap_start = 0) { |
115 | uptr TotalSpaceSize = kSpaceSize + AdditionalSize(); |
116 | PremappedHeap = heap_start != 0; |
117 | if (PremappedHeap) { |
118 | CHECK(!kUsingConstantSpaceBeg); |
119 | NonConstSpaceBeg = heap_start; |
120 | uptr RegionInfoSize = AdditionalSize(); |
121 | RegionInfoSpace = |
122 | address_range.Init(size: RegionInfoSize, name: PrimaryAllocatorName); |
123 | CHECK_NE(RegionInfoSpace, ~(uptr)0); |
124 | CHECK_EQ(RegionInfoSpace, |
125 | address_range.MapOrDie(RegionInfoSpace, RegionInfoSize, |
126 | "SizeClassAllocator: region info")); |
127 | MapUnmapCallback().OnMap(RegionInfoSpace, RegionInfoSize); |
128 | } else { |
129 | if (kUsingConstantSpaceBeg) { |
130 | CHECK(IsAligned(kSpaceBeg, SizeClassMap::kMaxSize)); |
131 | CHECK_EQ(kSpaceBeg, |
132 | address_range.Init(TotalSpaceSize, PrimaryAllocatorName, |
133 | kSpaceBeg)); |
134 | } else { |
135 | // Combined allocator expects that an 2^N allocation is always aligned |
136 | // to 2^N. For this to work, the start of the space needs to be aligned |
137 | // as high as the largest size class (which also needs to be a power of |
138 | // 2). |
139 | NonConstSpaceBeg = address_range.InitAligned( |
140 | size: TotalSpaceSize, align: SizeClassMap::kMaxSize, name: PrimaryAllocatorName); |
141 | CHECK_NE(NonConstSpaceBeg, ~(uptr)0); |
142 | } |
143 | RegionInfoSpace = SpaceEnd(); |
144 | MapWithCallbackOrDie(beg: RegionInfoSpace, size: AdditionalSize(), |
145 | name: "SizeClassAllocator: region info"); |
146 | } |
147 | SetReleaseToOSIntervalMs(release_to_os_interval_ms); |
148 | // Check that the RegionInfo array is aligned on the CacheLine size. |
149 | DCHECK_EQ(RegionInfoSpace % kCacheLineSize, 0); |
150 | } |
151 | |
152 | s32 ReleaseToOSIntervalMs() const { |
153 | return atomic_load(a: &release_to_os_interval_ms_, mo: memory_order_relaxed); |
154 | } |
155 | |
156 | void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) { |
157 | atomic_store(a: &release_to_os_interval_ms_, v: release_to_os_interval_ms, |
158 | mo: memory_order_relaxed); |
159 | } |
160 | |
161 | void ForceReleaseToOS() { |
162 | MemoryMapperT memory_mapper(*this); |
163 | for (uptr class_id = 1; class_id < kNumClasses; class_id++) { |
164 | Lock l(&GetRegionInfo(class_id)->mutex); |
165 | MaybeReleaseToOS(memory_mapper: &memory_mapper, class_id, force: true /*force*/); |
166 | } |
167 | } |
168 | |
169 | static bool CanAllocate(uptr size, uptr alignment) { |
170 | return size <= SizeClassMap::kMaxSize && |
171 | alignment <= SizeClassMap::kMaxSize; |
172 | } |
173 | |
174 | NOINLINE void ReturnToAllocator(MemoryMapperT *memory_mapper, |
175 | AllocatorStats *stat, uptr class_id, |
176 | const CompactPtrT *chunks, uptr n_chunks) { |
177 | RegionInfo *region = GetRegionInfo(class_id); |
178 | uptr region_beg = GetRegionBeginBySizeClass(class_id); |
179 | CompactPtrT *free_array = GetFreeArray(region_beg); |
180 | |
181 | Lock l(®ion->mutex); |
182 | uptr old_num_chunks = region->num_freed_chunks; |
183 | uptr new_num_freed_chunks = old_num_chunks + n_chunks; |
184 | // Failure to allocate free array space while releasing memory is non |
185 | // recoverable. |
186 | if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, |
187 | new_num_freed_chunks))) { |
188 | Report( |
189 | format: "FATAL: Internal error: %s's allocator exhausted the free list " |
190 | "space for size class %zu (%zu bytes).\n", |
191 | SanitizerToolName, class_id, ClassIdToSize(class_id)); |
192 | Die(); |
193 | } |
194 | for (uptr i = 0; i < n_chunks; i++) |
195 | free_array[old_num_chunks + i] = chunks[i]; |
196 | region->num_freed_chunks = new_num_freed_chunks; |
197 | region->stats.n_freed += n_chunks; |
198 | |
199 | MaybeReleaseToOS(memory_mapper, class_id, force: false /*force*/); |
200 | } |
201 | |
202 | NOINLINE bool GetFromAllocator(AllocatorStats *stat, uptr class_id, |
203 | CompactPtrT *chunks, uptr n_chunks) { |
204 | RegionInfo *region = GetRegionInfo(class_id); |
205 | uptr region_beg = GetRegionBeginBySizeClass(class_id); |
206 | CompactPtrT *free_array = GetFreeArray(region_beg); |
207 | |
208 | Lock l(®ion->mutex); |
209 | #if SANITIZER_WINDOWS |
210 | /* On Windows unmapping of memory during __sanitizer_purge_allocator is |
211 | explicit and immediate, so unmapped regions must be explicitly mapped back |
212 | in when they are accessed again. */ |
213 | if (region->rtoi.last_released_bytes > 0) { |
214 | MmapFixedOrDie(region_beg, region->mapped_user, |
215 | "SizeClassAllocator: region data"); |
216 | region->rtoi.n_freed_at_last_release = 0; |
217 | region->rtoi.last_released_bytes = 0; |
218 | } |
219 | #endif |
220 | if (UNLIKELY(region->num_freed_chunks < n_chunks)) { |
221 | if (UNLIKELY(!PopulateFreeArray(stat, class_id, region, |
222 | n_chunks - region->num_freed_chunks))) |
223 | return false; |
224 | CHECK_GE(region->num_freed_chunks, n_chunks); |
225 | } |
226 | region->num_freed_chunks -= n_chunks; |
227 | uptr base_idx = region->num_freed_chunks; |
228 | for (uptr i = 0; i < n_chunks; i++) |
229 | chunks[i] = free_array[base_idx + i]; |
230 | region->stats.n_allocated += n_chunks; |
231 | return true; |
232 | } |
233 | |
234 | bool PointerIsMine(const void *p) const { |
235 | uptr P = reinterpret_cast<uptr>(p); |
236 | if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0) |
237 | return P / kSpaceSize == kSpaceBeg / kSpaceSize; |
238 | return P >= SpaceBeg() && P < SpaceEnd(); |
239 | } |
240 | |
241 | uptr GetRegionBegin(const void *p) { |
242 | if (kUsingConstantSpaceBeg) |
243 | return reinterpret_cast<uptr>(p) & ~(kRegionSize - 1); |
244 | uptr space_beg = SpaceBeg(); |
245 | return ((reinterpret_cast<uptr>(p) - space_beg) & ~(kRegionSize - 1)) + |
246 | space_beg; |
247 | } |
248 | |
249 | uptr GetRegionBeginBySizeClass(uptr class_id) const { |
250 | return SpaceBeg() + kRegionSize * class_id; |
251 | } |
252 | |
253 | uptr GetSizeClass(const void *p) { |
254 | if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0) |
255 | return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded; |
256 | return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) % |
257 | kNumClassesRounded; |
258 | } |
259 | |
260 | void *GetBlockBegin(const void *p) { |
261 | uptr class_id = GetSizeClass(p); |
262 | if (class_id >= kNumClasses) return nullptr; |
263 | uptr size = ClassIdToSize(class_id); |
264 | if (!size) return nullptr; |
265 | uptr chunk_idx = GetChunkIdx(chunk: (uptr)p, size); |
266 | uptr reg_beg = GetRegionBegin(p); |
267 | uptr beg = chunk_idx * size; |
268 | uptr next_beg = beg + size; |
269 | const RegionInfo *region = AddressSpaceView::Load(GetRegionInfo(class_id)); |
270 | if (region->mapped_user >= next_beg) |
271 | return reinterpret_cast<void*>(reg_beg + beg); |
272 | return nullptr; |
273 | } |
274 | |
275 | uptr GetActuallyAllocatedSize(void *p) { |
276 | CHECK(PointerIsMine(p)); |
277 | return ClassIdToSize(class_id: GetSizeClass(p)); |
278 | } |
279 | |
280 | static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } |
281 | |
282 | void *GetMetaData(const void *p) { |
283 | CHECK(kMetadataSize); |
284 | uptr class_id = GetSizeClass(p); |
285 | uptr size = ClassIdToSize(class_id); |
286 | if (!size) |
287 | return nullptr; |
288 | uptr chunk_idx = GetChunkIdx(chunk: reinterpret_cast<uptr>(p), size); |
289 | uptr region_beg = GetRegionBeginBySizeClass(class_id); |
290 | return reinterpret_cast<void *>(GetMetadataEnd(region_beg) - |
291 | (1 + chunk_idx) * kMetadataSize); |
292 | } |
293 | |
294 | uptr TotalMemoryUsed() { |
295 | uptr res = 0; |
296 | for (uptr i = 0; i < kNumClasses; i++) |
297 | res += GetRegionInfo(class_id: i)->allocated_user; |
298 | return res; |
299 | } |
300 | |
301 | // Test-only. |
302 | void TestOnlyUnmap() { |
303 | UnmapWithCallbackOrDie(beg: (uptr)address_range.base(), size: address_range.size()); |
304 | } |
305 | |
306 | static void FillMemoryProfile(uptr start, uptr rss, bool file, uptr *stats) { |
307 | for (uptr class_id = 0; class_id < kNumClasses; class_id++) |
308 | if (stats[class_id] == start) |
309 | stats[class_id] = rss; |
310 | } |
311 | |
312 | void PrintStats(uptr class_id, uptr rss) { |
313 | RegionInfo *region = GetRegionInfo(class_id); |
314 | if (region->mapped_user == 0) return; |
315 | uptr in_use = region->stats.n_allocated - region->stats.n_freed; |
316 | uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id); |
317 | Printf( |
318 | "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd " |
319 | "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd " |
320 | "last released: %6lldK region: %p\n", |
321 | region->exhausted ? "F": " ", class_id, ClassIdToSize(class_id), |
322 | region->mapped_user >> 10, region->stats.n_allocated, |
323 | region->stats.n_freed, in_use, region->num_freed_chunks, avail_chunks, |
324 | rss >> 10, region->rtoi.num_releases, |
325 | region->rtoi.last_released_bytes >> 10, |
326 | (void *)(SpaceBeg() + kRegionSize * class_id)); |
327 | } |
328 | |
329 | void PrintStats() { |
330 | uptr rss_stats[kNumClasses]; |
331 | for (uptr class_id = 0; class_id < kNumClasses; class_id++) |
332 | rss_stats[class_id] = SpaceBeg() + kRegionSize * class_id; |
333 | GetMemoryProfile(FillMemoryProfile, rss_stats); |
334 | |
335 | uptr total_mapped = 0; |
336 | uptr total_rss = 0; |
337 | uptr n_allocated = 0; |
338 | uptr n_freed = 0; |
339 | for (uptr class_id = 1; class_id < kNumClasses; class_id++) { |
340 | RegionInfo *region = GetRegionInfo(class_id); |
341 | if (region->mapped_user != 0) { |
342 | total_mapped += region->mapped_user; |
343 | total_rss += rss_stats[class_id]; |
344 | } |
345 | n_allocated += region->stats.n_allocated; |
346 | n_freed += region->stats.n_freed; |
347 | } |
348 | |
349 | Printf(format: "Stats: SizeClassAllocator64: %zdM mapped (%zdM rss) in " |
350 | "%zd allocations; remains %zd\n", total_mapped >> 20, |
351 | total_rss >> 20, n_allocated, n_allocated - n_freed); |
352 | for (uptr class_id = 1; class_id < kNumClasses; class_id++) |
353 | PrintStats(class_id, rss_stats[class_id]); |
354 | } |
355 | |
356 | // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone |
357 | // introspection API. |
358 | void ForceLock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS { |
359 | for (uptr i = 0; i < kNumClasses; i++) { |
360 | GetRegionInfo(class_id: i)->mutex.Lock(); |
361 | } |
362 | } |
363 | |
364 | void ForceUnlock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS { |
365 | for (int i = (int)kNumClasses - 1; i >= 0; i--) { |
366 | GetRegionInfo(class_id: i)->mutex.Unlock(); |
367 | } |
368 | } |
369 | |
370 | // Iterate over all existing chunks. |
371 | // The allocator must be locked when calling this function. |
372 | void ForEachChunk(ForEachChunkCallback callback, void *arg) { |
373 | for (uptr class_id = 1; class_id < kNumClasses; class_id++) { |
374 | RegionInfo *region = GetRegionInfo(class_id); |
375 | uptr chunk_size = ClassIdToSize(class_id); |
376 | uptr region_beg = SpaceBeg() + class_id * kRegionSize; |
377 | uptr region_allocated_user_size = |
378 | AddressSpaceView::Load(region)->allocated_user; |
379 | for (uptr chunk = region_beg; |
380 | chunk < region_beg + region_allocated_user_size; |
381 | chunk += chunk_size) { |
382 | // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk)); |
383 | callback(chunk, arg); |
384 | } |
385 | } |
386 | } |
387 | |
388 | static uptr ClassIdToSize(uptr class_id) { |
389 | return SizeClassMap::Size(class_id); |
390 | } |
391 | |
392 | static uptr AdditionalSize() { |
393 | return RoundUpTo(size: sizeof(RegionInfo) * kNumClassesRounded, |
394 | boundary: GetPageSizeCached()); |
395 | } |
396 | |
397 | typedef SizeClassMap SizeClassMapT; |
398 | static const uptr kNumClasses = SizeClassMap::kNumClasses; |
399 | static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded; |
400 | |
401 | // A packed array of counters. Each counter occupies 2^n bits, enough to store |
402 | // counter's max_value. Ctor will try to allocate the required buffer via |
403 | // mapper->MapPackedCounterArrayBuffer and the caller is expected to check |
404 | // whether the initialization was successful by checking IsAllocated() result. |
405 | // For the performance sake, none of the accessors check the validity of the |
406 | // arguments, it is assumed that index is always in [0, n) range and the value |
407 | // is not incremented past max_value. |
408 | class PackedCounterArray { |
409 | public: |
410 | template <typename MemoryMapper> |
411 | PackedCounterArray(u64 num_counters, u64 max_value, MemoryMapper *mapper) |
412 | : n(num_counters) { |
413 | CHECK_GT(num_counters, 0); |
414 | CHECK_GT(max_value, 0); |
415 | constexpr u64 kMaxCounterBits = sizeof(*buffer) * 8ULL; |
416 | // Rounding counter storage size up to the power of two allows for using |
417 | // bit shifts calculating particular counter's index and offset. |
418 | uptr counter_size_bits = |
419 | RoundUpToPowerOfTwo(size: MostSignificantSetBitIndex(x: max_value) + 1); |
420 | CHECK_LE(counter_size_bits, kMaxCounterBits); |
421 | counter_size_bits_log = Log2(x: counter_size_bits); |
422 | counter_mask = ~0ULL >> (kMaxCounterBits - counter_size_bits); |
423 | |
424 | uptr packing_ratio = kMaxCounterBits >> counter_size_bits_log; |
425 | CHECK_GT(packing_ratio, 0); |
426 | packing_ratio_log = Log2(x: packing_ratio); |
427 | bit_offset_mask = packing_ratio - 1; |
428 | |
429 | buffer = mapper->MapPackedCounterArrayBuffer( |
430 | RoundUpTo(size: n, boundary: 1ULL << packing_ratio_log) >> packing_ratio_log); |
431 | } |
432 | |
433 | bool IsAllocated() const { |
434 | return !!buffer; |
435 | } |
436 | |
437 | u64 GetCount() const { |
438 | return n; |
439 | } |
440 | |
441 | uptr Get(uptr i) const { |
442 | DCHECK_LT(i, n); |
443 | uptr index = i >> packing_ratio_log; |
444 | uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log; |
445 | return (buffer[index] >> bit_offset) & counter_mask; |
446 | } |
447 | |
448 | void Inc(uptr i) const { |
449 | DCHECK_LT(Get(i), counter_mask); |
450 | uptr index = i >> packing_ratio_log; |
451 | uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log; |
452 | buffer[index] += 1ULL << bit_offset; |
453 | } |
454 | |
455 | void IncRange(uptr from, uptr to) const { |
456 | DCHECK_LE(from, to); |
457 | for (uptr i = from; i <= to; i++) |
458 | Inc(i); |
459 | } |
460 | |
461 | private: |
462 | const u64 n; |
463 | u64 counter_size_bits_log; |
464 | u64 counter_mask; |
465 | u64 packing_ratio_log; |
466 | u64 bit_offset_mask; |
467 | u64* buffer; |
468 | }; |
469 | |
470 | template <class MemoryMapperT> |
471 | class FreePagesRangeTracker { |
472 | public: |
473 | FreePagesRangeTracker(MemoryMapperT *mapper, uptr class_id) |
474 | : memory_mapper(mapper), |
475 | class_id(class_id), |
476 | page_size_scaled_log(Log2(x: GetPageSizeCached() >> kCompactPtrScale)) {} |
477 | |
478 | void NextPage(bool freed) { |
479 | if (freed) { |
480 | if (!in_the_range) { |
481 | current_range_start_page = current_page; |
482 | in_the_range = true; |
483 | } |
484 | } else { |
485 | CloseOpenedRange(); |
486 | } |
487 | current_page++; |
488 | } |
489 | |
490 | void Done() { |
491 | CloseOpenedRange(); |
492 | } |
493 | |
494 | private: |
495 | void CloseOpenedRange() { |
496 | if (in_the_range) { |
497 | memory_mapper->ReleasePageRangeToOS( |
498 | class_id, current_range_start_page << page_size_scaled_log, |
499 | current_page << page_size_scaled_log); |
500 | in_the_range = false; |
501 | } |
502 | } |
503 | |
504 | MemoryMapperT *const memory_mapper = nullptr; |
505 | const uptr class_id = 0; |
506 | const uptr page_size_scaled_log = 0; |
507 | bool in_the_range = false; |
508 | uptr current_page = 0; |
509 | uptr current_range_start_page = 0; |
510 | }; |
511 | |
512 | // Iterates over the free_array to identify memory pages containing freed |
513 | // chunks only and returns these pages back to OS. |
514 | // allocated_pages_count is the total number of pages allocated for the |
515 | // current bucket. |
516 | template <typename MemoryMapper> |
517 | static void ReleaseFreeMemoryToOS(CompactPtrT *free_array, |
518 | uptr free_array_count, uptr chunk_size, |
519 | uptr allocated_pages_count, |
520 | MemoryMapper *memory_mapper, |
521 | uptr class_id) { |
522 | const uptr page_size = GetPageSizeCached(); |
523 | |
524 | // Figure out the number of chunks per page and whether we can take a fast |
525 | // path (the number of chunks per page is the same for all pages). |
526 | uptr full_pages_chunk_count_max; |
527 | bool same_chunk_count_per_page; |
528 | if (chunk_size <= page_size && page_size % chunk_size == 0) { |
529 | // Same number of chunks per page, no cross overs. |
530 | full_pages_chunk_count_max = page_size / chunk_size; |
531 | same_chunk_count_per_page = true; |
532 | } else if (chunk_size <= page_size && page_size % chunk_size != 0 && |
533 | chunk_size % (page_size % chunk_size) == 0) { |
534 | // Some chunks are crossing page boundaries, which means that the page |
535 | // contains one or two partial chunks, but all pages contain the same |
536 | // number of chunks. |
537 | full_pages_chunk_count_max = page_size / chunk_size + 1; |
538 | same_chunk_count_per_page = true; |
539 | } else if (chunk_size <= page_size) { |
540 | // Some chunks are crossing page boundaries, which means that the page |
541 | // contains one or two partial chunks. |
542 | full_pages_chunk_count_max = page_size / chunk_size + 2; |
543 | same_chunk_count_per_page = false; |
544 | } else if (chunk_size > page_size && chunk_size % page_size == 0) { |
545 | // One chunk covers multiple pages, no cross overs. |
546 | full_pages_chunk_count_max = 1; |
547 | same_chunk_count_per_page = true; |
548 | } else if (chunk_size > page_size) { |
549 | // One chunk covers multiple pages, Some chunks are crossing page |
550 | // boundaries. Some pages contain one chunk, some contain two. |
551 | full_pages_chunk_count_max = 2; |
552 | same_chunk_count_per_page = false; |
553 | } else { |
554 | UNREACHABLE("All chunk_size/page_size ratios must be handled."); |
555 | } |
556 | |
557 | PackedCounterArray counters(allocated_pages_count, |
558 | full_pages_chunk_count_max, memory_mapper); |
559 | if (!counters.IsAllocated()) |
560 | return; |
561 | |
562 | const uptr chunk_size_scaled = chunk_size >> kCompactPtrScale; |
563 | const uptr page_size_scaled = page_size >> kCompactPtrScale; |
564 | const uptr page_size_scaled_log = Log2(x: page_size_scaled); |
565 | |
566 | // Iterate over free chunks and count how many free chunks affect each |
567 | // allocated page. |
568 | if (chunk_size <= page_size && page_size % chunk_size == 0) { |
569 | // Each chunk affects one page only. |
570 | for (uptr i = 0; i < free_array_count; i++) |
571 | counters.Inc(free_array[i] >> page_size_scaled_log); |
572 | } else { |
573 | // In all other cases chunks might affect more than one page. |
574 | for (uptr i = 0; i < free_array_count; i++) { |
575 | counters.IncRange( |
576 | free_array[i] >> page_size_scaled_log, |
577 | (free_array[i] + chunk_size_scaled - 1) >> page_size_scaled_log); |
578 | } |
579 | } |
580 | |
581 | // Iterate over pages detecting ranges of pages with chunk counters equal |
582 | // to the expected number of chunks for the particular page. |
583 | FreePagesRangeTracker<MemoryMapper> range_tracker(memory_mapper, class_id); |
584 | if (same_chunk_count_per_page) { |
585 | // Fast path, every page has the same number of chunks affecting it. |
586 | for (uptr i = 0; i < counters.GetCount(); i++) |
587 | range_tracker.NextPage(counters.Get(i) == full_pages_chunk_count_max); |
588 | } else { |
589 | // Show path, go through the pages keeping count how many chunks affect |
590 | // each page. |
591 | const uptr pn = |
592 | chunk_size < page_size ? page_size_scaled / chunk_size_scaled : 1; |
593 | const uptr pnc = pn * chunk_size_scaled; |
594 | // The idea is to increment the current page pointer by the first chunk |
595 | // size, middle portion size (the portion of the page covered by chunks |
596 | // except the first and the last one) and then the last chunk size, adding |
597 | // up the number of chunks on the current page and checking on every step |
598 | // whether the page boundary was crossed. |
599 | uptr prev_page_boundary = 0; |
600 | uptr current_boundary = 0; |
601 | for (uptr i = 0; i < counters.GetCount(); i++) { |
602 | uptr page_boundary = prev_page_boundary + page_size_scaled; |
603 | uptr chunks_per_page = pn; |
604 | if (current_boundary < page_boundary) { |
605 | if (current_boundary > prev_page_boundary) |
606 | chunks_per_page++; |
607 | current_boundary += pnc; |
608 | if (current_boundary < page_boundary) { |
609 | chunks_per_page++; |
610 | current_boundary += chunk_size_scaled; |
611 | } |
612 | } |
613 | prev_page_boundary = page_boundary; |
614 | |
615 | range_tracker.NextPage(counters.Get(i) == chunks_per_page); |
616 | } |
617 | } |
618 | range_tracker.Done(); |
619 | } |
620 | |
621 | private: |
622 | friend class MemoryMapper<ThisT>; |
623 | |
624 | ReservedAddressRange address_range; |
625 | |
626 | static const uptr kRegionSize = kSpaceSize / kNumClassesRounded; |
627 | // FreeArray is the array of free-d chunks (stored as 4-byte offsets). |
628 | // In the worst case it may require kRegionSize/SizeClassMap::kMinSize |
629 | // elements, but in reality this will not happen. For simplicity we |
630 | // dedicate 1/8 of the region's virtual space to FreeArray. |
631 | static const uptr kFreeArraySize = kRegionSize / 8; |
632 | |
633 | static const bool kUsingConstantSpaceBeg = kSpaceBeg != ~(uptr)0; |
634 | uptr NonConstSpaceBeg; |
635 | uptr SpaceBeg() const { |
636 | return kUsingConstantSpaceBeg ? kSpaceBeg : NonConstSpaceBeg; |
637 | } |
638 | uptr SpaceEnd() const { return SpaceBeg() + kSpaceSize; } |
639 | // kRegionSize should be able to satisfy the largest size class. |
640 | static_assert(kRegionSize >= SizeClassMap::kMaxSize, |
641 | "Region size exceed largest size"); |
642 | // kRegionSize must be <= 2^36, see CompactPtrT. |
643 | COMPILER_CHECK((kRegionSize) <= |
644 | (1ULL << (sizeof(CompactPtrT) * 8 + kCompactPtrScale))); |
645 | // Call mmap for user memory with at least this size. |
646 | static const uptr kUserMapSize = 1 << 18; |
647 | // Call mmap for metadata memory with at least this size. |
648 | static const uptr kMetaMapSize = 1 << 16; |
649 | // Call mmap for free array memory with at least this size. |
650 | static const uptr kFreeArrayMapSize = 1 << 18; |
651 | |
652 | atomic_sint32_t release_to_os_interval_ms_; |
653 | |
654 | uptr RegionInfoSpace; |
655 | |
656 | // True if the user has already mapped the entire heap R/W. |
657 | bool PremappedHeap; |
658 | |
659 | struct Stats { |
660 | uptr n_allocated; |
661 | uptr n_freed; |
662 | }; |
663 | |
664 | struct ReleaseToOsInfo { |
665 | uptr n_freed_at_last_release; |
666 | uptr num_releases; |
667 | u64 last_release_at_ns; |
668 | u64 last_released_bytes; |
669 | }; |
670 | |
671 | struct alignas(SANITIZER_CACHE_LINE_SIZE) RegionInfo { |
672 | Mutex mutex; |
673 | uptr num_freed_chunks; // Number of elements in the freearray. |
674 | uptr mapped_free_array; // Bytes mapped for freearray. |
675 | uptr allocated_user; // Bytes allocated for user memory. |
676 | uptr allocated_meta; // Bytes allocated for metadata. |
677 | uptr mapped_user; // Bytes mapped for user memory. |
678 | uptr mapped_meta; // Bytes mapped for metadata. |
679 | u32 rand_state; // Seed for random shuffle, used if kRandomShuffleChunks. |
680 | bool exhausted; // Whether region is out of space for new chunks. |
681 | Stats stats; |
682 | ReleaseToOsInfo rtoi; |
683 | }; |
684 | COMPILER_CHECK(sizeof(RegionInfo) % kCacheLineSize == 0); |
685 | |
686 | RegionInfo *GetRegionInfo(uptr class_id) const { |
687 | DCHECK_LT(class_id, kNumClasses); |
688 | RegionInfo *regions = reinterpret_cast<RegionInfo *>(RegionInfoSpace); |
689 | return ®ions[class_id]; |
690 | } |
691 | |
692 | uptr GetMetadataEnd(uptr region_beg) const { |
693 | return region_beg + kRegionSize - kFreeArraySize; |
694 | } |
695 | |
696 | uptr GetChunkIdx(uptr chunk, uptr size) const { |
697 | if (!kUsingConstantSpaceBeg) |
698 | chunk -= SpaceBeg(); |
699 | |
700 | uptr offset = chunk % kRegionSize; |
701 | // Here we divide by a non-constant. This is costly. |
702 | // size always fits into 32-bits. If the offset fits too, use 32-bit div. |
703 | if (offset >> (SANITIZER_WORDSIZE / 2)) |
704 | return offset / size; |
705 | return (u32)offset / (u32)size; |
706 | } |
707 | |
708 | CompactPtrT *GetFreeArray(uptr region_beg) const { |
709 | return reinterpret_cast<CompactPtrT *>(GetMetadataEnd(region_beg)); |
710 | } |
711 | |
712 | bool MapWithCallback(uptr beg, uptr size, const char *name) { |
713 | if (PremappedHeap) |
714 | return beg >= NonConstSpaceBeg && |
715 | beg + size <= NonConstSpaceBeg + kSpaceSize; |
716 | uptr mapped = address_range.Map(fixed_addr: beg, size, name); |
717 | if (UNLIKELY(!mapped)) |
718 | return false; |
719 | CHECK_EQ(beg, mapped); |
720 | MapUnmapCallback().OnMap(beg, size); |
721 | return true; |
722 | } |
723 | |
724 | void MapWithCallbackOrDie(uptr beg, uptr size, const char *name) { |
725 | if (PremappedHeap) { |
726 | CHECK_GE(beg, NonConstSpaceBeg); |
727 | CHECK_LE(beg + size, NonConstSpaceBeg + kSpaceSize); |
728 | return; |
729 | } |
730 | CHECK_EQ(beg, address_range.MapOrDie(beg, size, name)); |
731 | MapUnmapCallback().OnMap(beg, size); |
732 | } |
733 | |
734 | void UnmapWithCallbackOrDie(uptr beg, uptr size) { |
735 | if (PremappedHeap) |
736 | return; |
737 | MapUnmapCallback().OnUnmap(beg, size); |
738 | address_range.Unmap(addr: beg, size); |
739 | } |
740 | |
741 | bool EnsureFreeArraySpace(RegionInfo *region, uptr region_beg, |
742 | uptr num_freed_chunks) { |
743 | uptr needed_space = num_freed_chunks * sizeof(CompactPtrT); |
744 | if (region->mapped_free_array < needed_space) { |
745 | uptr new_mapped_free_array = RoundUpTo(size: needed_space, boundary: kFreeArrayMapSize); |
746 | CHECK_LE(new_mapped_free_array, kFreeArraySize); |
747 | uptr current_map_end = reinterpret_cast<uptr>(GetFreeArray(region_beg)) + |
748 | region->mapped_free_array; |
749 | uptr new_map_size = new_mapped_free_array - region->mapped_free_array; |
750 | if (UNLIKELY(!MapWithCallback(current_map_end, new_map_size, |
751 | "SizeClassAllocator: freearray"))) |
752 | return false; |
753 | region->mapped_free_array = new_mapped_free_array; |
754 | } |
755 | return true; |
756 | } |
757 | |
758 | // Check whether this size class is exhausted. |
759 | bool IsRegionExhausted(RegionInfo *region, uptr class_id, |
760 | uptr additional_map_size) { |
761 | if (LIKELY(region->mapped_user + region->mapped_meta + |
762 | additional_map_size <= kRegionSize - kFreeArraySize)) |
763 | return false; |
764 | if (!region->exhausted) { |
765 | region->exhausted = true; |
766 | Printf(format: "%s: Out of memory. ", SanitizerToolName); |
767 | Printf( |
768 | format: "The process has exhausted %zu MB for size class %zu (%zu bytes).\n", |
769 | kRegionSize >> 20, class_id, ClassIdToSize(class_id)); |
770 | } |
771 | return true; |
772 | } |
773 | |
774 | NOINLINE bool PopulateFreeArray(AllocatorStats *stat, uptr class_id, |
775 | RegionInfo *region, uptr requested_count) { |
776 | // region->mutex is held. |
777 | const uptr region_beg = GetRegionBeginBySizeClass(class_id); |
778 | const uptr size = ClassIdToSize(class_id); |
779 | |
780 | const uptr total_user_bytes = |
781 | region->allocated_user + requested_count * size; |
782 | // Map more space for chunks, if necessary. |
783 | if (LIKELY(total_user_bytes > region->mapped_user)) { |
784 | if (UNLIKELY(region->mapped_user == 0)) { |
785 | if (!kUsingConstantSpaceBeg && kRandomShuffleChunks) |
786 | // The random state is initialized from ASLR. |
787 | region->rand_state = static_cast<u32>(region_beg >> 12); |
788 | // Postpone the first release to OS attempt for ReleaseToOSIntervalMs, |
789 | // preventing just allocated memory from being released sooner than |
790 | // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls |
791 | // for short lived processes. |
792 | // Do it only when the feature is turned on, to avoid a potentially |
793 | // extraneous syscall. |
794 | if (ReleaseToOSIntervalMs() >= 0) |
795 | region->rtoi.last_release_at_ns = MonotonicNanoTime(); |
796 | } |
797 | // Do the mmap for the user memory. |
798 | const uptr user_map_size = |
799 | RoundUpTo(total_user_bytes - region->mapped_user, kUserMapSize); |
800 | if (UNLIKELY(IsRegionExhausted(region, class_id, user_map_size))) |
801 | return false; |
802 | if (UNLIKELY(!MapWithCallback(region_beg + region->mapped_user, |
803 | user_map_size, |
804 | "SizeClassAllocator: region data"))) |
805 | return false; |
806 | stat->Add(i: AllocatorStatMapped, v: user_map_size); |
807 | region->mapped_user += user_map_size; |
808 | } |
809 | const uptr new_chunks_count = |
810 | (region->mapped_user - region->allocated_user) / size; |
811 | |
812 | if (kMetadataSize) { |
813 | // Calculate the required space for metadata. |
814 | const uptr total_meta_bytes = |
815 | region->allocated_meta + new_chunks_count * kMetadataSize; |
816 | const uptr meta_map_size = (total_meta_bytes > region->mapped_meta) ? |
817 | RoundUpTo(total_meta_bytes - region->mapped_meta, kMetaMapSize) : 0; |
818 | // Map more space for metadata, if necessary. |
819 | if (meta_map_size) { |
820 | if (UNLIKELY(IsRegionExhausted(region, class_id, meta_map_size))) |
821 | return false; |
822 | if (UNLIKELY(!MapWithCallback( |
823 | GetMetadataEnd(region_beg) - region->mapped_meta - meta_map_size, |
824 | meta_map_size, "SizeClassAllocator: region metadata"))) |
825 | return false; |
826 | region->mapped_meta += meta_map_size; |
827 | } |
828 | } |
829 | |
830 | // If necessary, allocate more space for the free array and populate it with |
831 | // newly allocated chunks. |
832 | const uptr total_freed_chunks = region->num_freed_chunks + new_chunks_count; |
833 | if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, total_freed_chunks))) |
834 | return false; |
835 | CompactPtrT *free_array = GetFreeArray(region_beg); |
836 | for (uptr i = 0, chunk = region->allocated_user; i < new_chunks_count; |
837 | i++, chunk += size) |
838 | free_array[total_freed_chunks - 1 - i] = PointerToCompactPtr(base: 0, ptr: chunk); |
839 | if (kRandomShuffleChunks) |
840 | RandomShuffle(&free_array[region->num_freed_chunks], new_chunks_count, |
841 | ®ion->rand_state); |
842 | |
843 | // All necessary memory is mapped and now it is safe to advance all |
844 | // 'allocated_*' counters. |
845 | region->num_freed_chunks += new_chunks_count; |
846 | region->allocated_user += new_chunks_count * size; |
847 | CHECK_LE(region->allocated_user, region->mapped_user); |
848 | region->allocated_meta += new_chunks_count * kMetadataSize; |
849 | CHECK_LE(region->allocated_meta, region->mapped_meta); |
850 | region->exhausted = false; |
851 | |
852 | // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent |
853 | // MaybeReleaseToOS from releasing just allocated pages or protect these |
854 | // not yet used chunks some other way. |
855 | |
856 | return true; |
857 | } |
858 | |
859 | // Attempts to release RAM occupied by freed chunks back to OS. The region is |
860 | // expected to be locked. |
861 | // |
862 | // TODO(morehouse): Support a callback on memory release so HWASan can release |
863 | // aliases as well. |
864 | void MaybeReleaseToOS(MemoryMapperT *memory_mapper, uptr class_id, |
865 | bool force) { |
866 | RegionInfo *region = GetRegionInfo(class_id); |
867 | const uptr chunk_size = ClassIdToSize(class_id); |
868 | const uptr page_size = GetPageSizeCached(); |
869 | |
870 | uptr n = region->num_freed_chunks; |
871 | if (n * chunk_size < page_size) |
872 | return; // No chance to release anything. |
873 | if ((region->stats.n_freed - |
874 | region->rtoi.n_freed_at_last_release) * chunk_size < page_size) { |
875 | return; // Nothing new to release. |
876 | } |
877 | |
878 | if (!force) { |
879 | s32 interval_ms = ReleaseToOSIntervalMs(); |
880 | if (interval_ms < 0) |
881 | return; |
882 | |
883 | if (region->rtoi.last_release_at_ns + interval_ms * 1000000ULL > |
884 | MonotonicNanoTime()) { |
885 | return; // Memory was returned recently. |
886 | } |
887 | } |
888 | |
889 | ReleaseFreeMemoryToOS( |
890 | GetFreeArray(region_beg: GetRegionBeginBySizeClass(class_id)), n, chunk_size, |
891 | RoundUpTo(region->allocated_user, page_size) / page_size, memory_mapper, |
892 | class_id); |
893 | |
894 | uptr ranges, bytes; |
895 | if (memory_mapper->GetAndResetStats(ranges, bytes)) { |
896 | region->rtoi.n_freed_at_last_release = region->stats.n_freed; |
897 | region->rtoi.num_releases += ranges; |
898 | region->rtoi.last_released_bytes = bytes; |
899 | } |
900 | region->rtoi.last_release_at_ns = MonotonicNanoTime(); |
901 | } |
902 | }; |
903 |
Definitions
- SizeClassAllocator64FlagMasks
- MemoryMapper
- MemoryMapper
- GetAndResetStats
- MapPackedCounterArrayBuffer
- ReleasePageRangeToOS
- SizeClassAllocator64
- PointerToCompactPtr
- CompactPtrToPointer
- Init
- ReleaseToOSIntervalMs
- SetReleaseToOSIntervalMs
- ForceReleaseToOS
- CanAllocate
- ReturnToAllocator
- GetFromAllocator
- PointerIsMine
- GetRegionBegin
- GetRegionBeginBySizeClass
- GetSizeClass
- GetBlockBegin
- GetActuallyAllocatedSize
- ClassID
- GetMetaData
- TotalMemoryUsed
- TestOnlyUnmap
- FillMemoryProfile
- PrintStats
- PrintStats
- ForceLock
- ForceUnlock
- ForEachChunk
- ClassIdToSize
- AdditionalSize
- PackedCounterArray
- PackedCounterArray
- IsAllocated
- GetCount
- Get
- Inc
- IncRange
- FreePagesRangeTracker
- FreePagesRangeTracker
- NextPage
- Done
- CloseOpenedRange
- ReleaseFreeMemoryToOS
- SpaceBeg
- SpaceEnd
- Stats
- ReleaseToOsInfo
- RegionInfo
- GetRegionInfo
- GetMetadataEnd
- GetChunkIdx
- GetFreeArray
- MapWithCallback
- MapWithCallbackOrDie
- UnmapWithCallbackOrDie
- EnsureFreeArraySpace
- IsRegionExhausted
- PopulateFreeArray
Learn to use CMake with our Intro Training
Find out more