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