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