1//===-- release.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#ifndef SCUDO_RELEASE_H_
10#define SCUDO_RELEASE_H_
11
12#include "common.h"
13#include "list.h"
14#include "mem_map.h"
15#include "mutex.h"
16#include "string_utils.h"
17#include "thread_annotations.h"
18
19namespace scudo {
20
21template <typename MemMapT> class RegionReleaseRecorder {
22public:
23 RegionReleaseRecorder(MemMapT *RegionMemMap, uptr Base, uptr Offset = 0)
24 : RegionMemMap(RegionMemMap), Base(Base), Offset(Offset) {}
25
26 uptr getReleasedBytes() const { return ReleasedBytes; }
27
28 uptr getBase() const { return Base; }
29
30 // Releases [From, To) range of pages back to OS. Note that `From` and `To`
31 // are offseted from `Base` + Offset.
32 void releasePageRangeToOS(uptr From, uptr To) {
33 const uptr Size = To - From;
34 RegionMemMap->releasePagesToOS(getBase() + Offset + From, Size);
35 ReleasedBytes += Size;
36 }
37
38private:
39 uptr ReleasedBytes = 0;
40 MemMapT *RegionMemMap = nullptr;
41 uptr Base = 0;
42 // The release offset from Base. This is used when we know a given range after
43 // Base will not be released.
44 uptr Offset = 0;
45};
46
47class ReleaseRecorder {
48public:
49 ReleaseRecorder(uptr Base, uptr Offset = 0, MapPlatformData *Data = nullptr)
50 : Base(Base), Offset(Offset), Data(Data) {}
51
52 uptr getReleasedBytes() const { return ReleasedBytes; }
53
54 uptr getBase() const { return Base; }
55
56 // Releases [From, To) range of pages back to OS.
57 void releasePageRangeToOS(uptr From, uptr To) {
58 const uptr Size = To - From;
59 releasePagesToOS(BaseAddress: Base, Offset: From + Offset, Size, Data);
60 ReleasedBytes += Size;
61 }
62
63private:
64 uptr ReleasedBytes = 0;
65 // The starting address to release. Note that we may want to combine (Base +
66 // Offset) as a new Base. However, the Base is retrieved from
67 // `MapPlatformData` on Fuchsia, which means the offset won't be aware.
68 // Therefore, store them separately to make it work on all the platforms.
69 uptr Base = 0;
70 // The release offset from Base. This is used when we know a given range after
71 // Base will not be released.
72 uptr Offset = 0;
73 MapPlatformData *Data = nullptr;
74};
75
76class FragmentationRecorder {
77public:
78 FragmentationRecorder() = default;
79
80 uptr getReleasedPagesCount() const { return ReleasedPagesCount; }
81
82 void releasePageRangeToOS(uptr From, uptr To) {
83 DCHECK_EQ((To - From) % getPageSizeCached(), 0U);
84 ReleasedPagesCount += (To - From) >> getPageSizeLogCached();
85 }
86
87private:
88 uptr ReleasedPagesCount = 0;
89};
90
91template <uptr GroupSize, uptr NumGroups>
92class MemoryGroupFragmentationRecorder {
93public:
94 const uptr NumPagesInOneGroup = GroupSize / getPageSizeCached();
95
96 void releasePageRangeToOS(uptr From, uptr To) {
97 for (uptr I = From / getPageSizeCached(); I < To / getPageSizeCached(); ++I)
98 ++FreePagesCount[I / NumPagesInOneGroup];
99 }
100
101 uptr getNumFreePages(uptr GroupId) { return FreePagesCount[GroupId]; }
102
103private:
104 uptr FreePagesCount[NumGroups] = {};
105};
106
107// A buffer pool which holds a fixed number of static buffers of `uptr` elements
108// for fast buffer allocation. If the request size is greater than
109// `StaticBufferNumElements` or if all the static buffers are in use, it'll
110// delegate the allocation to map().
111template <uptr StaticBufferCount, uptr StaticBufferNumElements>
112class BufferPool {
113public:
114 // Preserve 1 bit in the `Mask` so that we don't need to do zero-check while
115 // extracting the least significant bit from the `Mask`.
116 static_assert(StaticBufferCount < SCUDO_WORDSIZE, "");
117 static_assert(isAligned(X: StaticBufferNumElements * sizeof(uptr),
118 SCUDO_CACHE_LINE_SIZE),
119 "");
120
121 struct Buffer {
122 // Pointer to the buffer's memory, or nullptr if no buffer was allocated.
123 uptr *Data = nullptr;
124
125 // The index of the underlying static buffer, or StaticBufferCount if this
126 // buffer was dynamically allocated. This value is initially set to a poison
127 // value to aid debugging.
128 uptr BufferIndex = ~static_cast<uptr>(0);
129
130 // Only valid if BufferIndex == StaticBufferCount.
131 MemMapT MemMap = {};
132 };
133
134 // Buf must be an empty buffer that will be filled in to contain a zero
135 // initialized buffer which can contain the given number of elements.
136 // On failure, Buf.data is guaranteed to be nullptr, and returns false.
137 bool getBuffer(Buffer &Buf, const uptr NumElements) {
138 DCHECK(Buf.Data == nullptr);
139 if (UNLIKELY(NumElements > StaticBufferNumElements))
140 return getDynamicBuffer(Buf, NumElements);
141
142 uptr Index;
143 {
144 // TODO: In general, we expect this operation should be fast so the
145 // waiting thread won't be put into sleep. The HybridMutex does implement
146 // the busy-waiting but we may want to review the performance and see if
147 // we need an explict spin lock here.
148 ScopedLock L(Mutex);
149 Index = getLeastSignificantSetBitIndex(X: Mask);
150 if (Index < StaticBufferCount)
151 Mask ^= static_cast<uptr>(1) << Index;
152 }
153
154 if (Index >= StaticBufferCount)
155 return getDynamicBuffer(Buf, NumElements);
156
157 Buf.Data = &RawBuffer[Index * StaticBufferNumElements];
158 Buf.BufferIndex = Index;
159 memset(Buf.Data, 0, StaticBufferNumElements * sizeof(uptr));
160 return true;
161 }
162
163 void releaseBuffer(Buffer &Buf) {
164 DCHECK_NE(Buf.Data, nullptr);
165 DCHECK_LE(Buf.BufferIndex, StaticBufferCount);
166 if (Buf.BufferIndex != StaticBufferCount) {
167 ScopedLock L(Mutex);
168 DCHECK_EQ((Mask & (static_cast<uptr>(1) << Buf.BufferIndex)), 0U);
169 Mask |= static_cast<uptr>(1) << Buf.BufferIndex;
170 } else {
171 Buf.MemMap.unmap();
172 }
173 Buf.Data = nullptr;
174 }
175
176 bool isStaticBufferTestOnly(const Buffer &Buf) {
177 DCHECK_NE(Buf.Data, nullptr);
178 DCHECK_LE(Buf.BufferIndex, StaticBufferCount);
179 return Buf.BufferIndex != StaticBufferCount;
180 }
181
182private:
183 bool getDynamicBuffer(Buffer &Buf, const uptr NumElements) {
184 // When using a heap-based buffer, precommit the pages backing the
185 // Vmar by passing |MAP_PRECOMMIT| flag. This allows an optimization
186 // where page fault exceptions are skipped as the allocated memory
187 // is accessed. So far, this is only enabled on Fuchsia. It hasn't proven a
188 // performance benefit on other platforms.
189 const uptr MmapFlags = MAP_ALLOWNOMEM | (SCUDO_FUCHSIA ? MAP_PRECOMMIT : 0);
190 const uptr MappedSize =
191 roundUp(X: NumElements * sizeof(uptr), Boundary: getPageSizeCached());
192 if (!UNLIKELY(Buf.MemMap.map(/*Addr=*/0, MappedSize, "scudo:counters",
193 MmapFlags))) {
194 return false;
195 }
196
197 DCHECK(Buf.Data == nullptr);
198 Buf.Data = reinterpret_cast<uptr *>(Buf.MemMap.getBase());
199 Buf.BufferIndex = StaticBufferCount;
200 return true;
201 }
202
203 HybridMutex Mutex;
204 // '1' means that buffer index is not used. '0' means the buffer is in use.
205 uptr Mask GUARDED_BY(Mutex) = ~static_cast<uptr>(0);
206 uptr RawBuffer[StaticBufferCount * StaticBufferNumElements] GUARDED_BY(Mutex);
207};
208
209// A Region page map is used to record the usage of pages in the regions. It
210// implements a packed array of Counters. Each counter occupies 2^N bits, enough
211// to store counter's MaxValue. Ctor will try to use a static buffer first, and
212// if that fails (the buffer is too small or already locked), will allocate the
213// required Buffer via map(). The caller is expected to check whether the
214// initialization was successful by checking isAllocated() result. For
215// performance sake, none of the accessors check the validity of the arguments,
216// It is assumed that Index is always in [0, N) range and the value is not
217// incremented past MaxValue.
218class RegionPageMap {
219public:
220 RegionPageMap()
221 : Regions(0), NumCounters(0), CounterSizeBitsLog(0), CounterMask(0),
222 PackingRatioLog(0), BitOffsetMask(0), SizePerRegion(0),
223 BufferNumElements(0) {}
224 RegionPageMap(uptr NumberOfRegions, uptr CountersPerRegion, uptr MaxValue) {
225 reset(NumberOfRegions, CountersPerRegion, MaxValue);
226 }
227 ~RegionPageMap() {
228 if (!isAllocated())
229 return;
230 Buffers.releaseBuffer(Buf&: Buffer);
231 }
232
233 // Lock of `StaticBuffer` is acquired conditionally and there's no easy way to
234 // specify the thread-safety attribute properly in current code structure.
235 // Besides, it's the only place we may want to check thread safety. Therefore,
236 // it's fine to bypass the thread-safety analysis now.
237 void reset(uptr NumberOfRegions, uptr CountersPerRegion, uptr MaxValue) {
238 DCHECK_GT(NumberOfRegions, 0);
239 DCHECK_GT(CountersPerRegion, 0);
240 DCHECK_GT(MaxValue, 0);
241
242 Regions = NumberOfRegions;
243 NumCounters = CountersPerRegion;
244
245 constexpr uptr MaxCounterBits = sizeof(*Buffer.Data) * 8UL;
246 // Rounding counter storage size up to the power of two allows for using
247 // bit shifts calculating particular counter's Index and offset.
248 const uptr CounterSizeBits =
249 roundUpPowerOfTwo(Size: getMostSignificantSetBitIndex(X: MaxValue) + 1);
250 DCHECK_LE(CounterSizeBits, MaxCounterBits);
251 CounterSizeBitsLog = getLog2(X: CounterSizeBits);
252 CounterMask = ~(static_cast<uptr>(0)) >> (MaxCounterBits - CounterSizeBits);
253
254 const uptr PackingRatio = MaxCounterBits >> CounterSizeBitsLog;
255 DCHECK_GT(PackingRatio, 0);
256 PackingRatioLog = getLog2(X: PackingRatio);
257 BitOffsetMask = PackingRatio - 1;
258
259 SizePerRegion =
260 roundUp(X: NumCounters, Boundary: static_cast<uptr>(1U) << PackingRatioLog) >>
261 PackingRatioLog;
262 BufferNumElements = SizePerRegion * Regions;
263 if (!Buffers.getBuffer(Buf&: Buffer, NumElements: BufferNumElements)) {
264 DCHECK(Buffer.Data == nullptr);
265 Printf(Format: "Scudo WARNING: unable to allocate buffer for RegionPageMap");
266 }
267 }
268
269 bool isAllocated() const { return Buffer.Data != nullptr; }
270
271 uptr getCount() const { return NumCounters; }
272
273 uptr get(uptr Region, uptr I) const {
274 DCHECK_LT(Region, Regions);
275 DCHECK_LT(I, NumCounters);
276 const uptr Index = I >> PackingRatioLog;
277 const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
278 return (Buffer.Data[Region * SizePerRegion + Index] >> BitOffset) &
279 CounterMask;
280 }
281
282 void inc(uptr Region, uptr I) const {
283 DCHECK_LT(get(Region, I), CounterMask);
284 const uptr Index = I >> PackingRatioLog;
285 const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
286 DCHECK_LT(BitOffset, SCUDO_WORDSIZE);
287 DCHECK_EQ(isAllCounted(Region, I), false);
288 Buffer.Data[Region * SizePerRegion + Index] += static_cast<uptr>(1U)
289 << BitOffset;
290 }
291
292 void incN(uptr Region, uptr I, uptr N) const {
293 DCHECK_GT(N, 0U);
294 DCHECK_LE(N, CounterMask);
295 DCHECK_LE(get(Region, I), CounterMask - N);
296 const uptr Index = I >> PackingRatioLog;
297 const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
298 DCHECK_LT(BitOffset, SCUDO_WORDSIZE);
299 DCHECK_EQ(isAllCounted(Region, I), false);
300 Buffer.Data[Region * SizePerRegion + Index] += N << BitOffset;
301 }
302
303 void incRange(uptr Region, uptr From, uptr To) const {
304 DCHECK_LE(From, To);
305 const uptr Top = Min(A: To + 1, B: NumCounters);
306 for (uptr I = From; I < Top; I++)
307 inc(Region, I);
308 }
309
310 // Set the counter to the max value. Note that the max number of blocks in a
311 // page may vary. To provide an easier way to tell if all the blocks are
312 // counted for different pages, set to the same max value to denote the
313 // all-counted status.
314 void setAsAllCounted(uptr Region, uptr I) const {
315 DCHECK_LE(get(Region, I), CounterMask);
316 const uptr Index = I >> PackingRatioLog;
317 const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
318 DCHECK_LT(BitOffset, SCUDO_WORDSIZE);
319 Buffer.Data[Region * SizePerRegion + Index] |= CounterMask << BitOffset;
320 }
321 void setAsAllCountedRange(uptr Region, uptr From, uptr To) const {
322 DCHECK_LE(From, To);
323 const uptr Top = Min(A: To + 1, B: NumCounters);
324 for (uptr I = From; I < Top; I++)
325 setAsAllCounted(Region, I);
326 }
327
328 bool updateAsAllCountedIf(uptr Region, uptr I, uptr MaxCount) {
329 const uptr Count = get(Region, I);
330 if (Count == CounterMask)
331 return true;
332 if (Count == MaxCount) {
333 setAsAllCounted(Region, I);
334 return true;
335 }
336 return false;
337 }
338 bool isAllCounted(uptr Region, uptr I) const {
339 return get(Region, I) == CounterMask;
340 }
341
342 uptr getBufferNumElements() const { return BufferNumElements; }
343
344private:
345 // We may consider making this configurable if there are cases which may
346 // benefit from this.
347 static const uptr StaticBufferCount = 2U;
348 static const uptr StaticBufferNumElements = 512U;
349 using BufferPoolT = BufferPool<StaticBufferCount, StaticBufferNumElements>;
350 static BufferPoolT Buffers;
351
352 uptr Regions;
353 uptr NumCounters;
354 uptr CounterSizeBitsLog;
355 uptr CounterMask;
356 uptr PackingRatioLog;
357 uptr BitOffsetMask;
358
359 uptr SizePerRegion;
360 uptr BufferNumElements;
361 BufferPoolT::Buffer Buffer;
362};
363
364template <class ReleaseRecorderT> class FreePagesRangeTracker {
365public:
366 explicit FreePagesRangeTracker(ReleaseRecorderT &Recorder)
367 : Recorder(Recorder) {}
368
369 void processNextPage(bool Released) {
370 if (Released) {
371 if (!InRange) {
372 CurrentRangeStatePage = CurrentPage;
373 InRange = true;
374 }
375 } else {
376 closeOpenedRange();
377 }
378 CurrentPage++;
379 }
380
381 void skipPages(uptr N) {
382 closeOpenedRange();
383 CurrentPage += N;
384 }
385
386 void finish() { closeOpenedRange(); }
387
388private:
389 void closeOpenedRange() {
390 if (InRange) {
391 const uptr PageSizeLog = getPageSizeLogCached();
392 Recorder.releasePageRangeToOS((CurrentRangeStatePage << PageSizeLog),
393 (CurrentPage << PageSizeLog));
394 InRange = false;
395 }
396 }
397
398 ReleaseRecorderT &Recorder;
399 bool InRange = false;
400 uptr CurrentPage = 0;
401 uptr CurrentRangeStatePage = 0;
402};
403
404struct PageReleaseContext {
405 PageReleaseContext(uptr BlockSize, uptr NumberOfRegions, uptr ReleaseSize,
406 uptr ReleaseOffset = 0)
407 : BlockSize(BlockSize), NumberOfRegions(NumberOfRegions) {
408 const uptr PageSize = getPageSizeCached();
409 if (BlockSize <= PageSize) {
410 if (PageSize % BlockSize == 0) {
411 // Same number of chunks per page, no cross overs.
412 FullPagesBlockCountMax = PageSize / BlockSize;
413 SameBlockCountPerPage = true;
414 } else if (BlockSize % (PageSize % BlockSize) == 0) {
415 // Some chunks are crossing page boundaries, which means that the page
416 // contains one or two partial chunks, but all pages contain the same
417 // number of chunks.
418 FullPagesBlockCountMax = PageSize / BlockSize + 1;
419 SameBlockCountPerPage = true;
420 } else {
421 // Some chunks are crossing page boundaries, which means that the page
422 // contains one or two partial chunks.
423 FullPagesBlockCountMax = PageSize / BlockSize + 2;
424 SameBlockCountPerPage = false;
425 }
426 } else {
427 if ((BlockSize & (PageSize - 1)) == 0) {
428 // One chunk covers multiple pages, no cross overs.
429 FullPagesBlockCountMax = 1;
430 SameBlockCountPerPage = true;
431 } else {
432 // One chunk covers multiple pages, Some chunks are crossing page
433 // boundaries. Some pages contain one chunk, some contain two.
434 FullPagesBlockCountMax = 2;
435 SameBlockCountPerPage = false;
436 }
437 }
438
439 // TODO: For multiple regions, it's more complicated to support partial
440 // region marking (which includes the complexity of how to handle the last
441 // block in a region). We may consider this after markFreeBlocks() accepts
442 // only free blocks from the same region.
443 if (NumberOfRegions != 1)
444 DCHECK_EQ(ReleaseOffset, 0U);
445
446 const uptr PageSizeLog = getPageSizeLogCached();
447 PagesCount = roundUp(X: ReleaseSize, Boundary: PageSize) >> PageSizeLog;
448 ReleasePageOffset = ReleaseOffset >> PageSizeLog;
449 }
450
451 // PageMap is lazily allocated when markFreeBlocks() is invoked.
452 bool hasBlockMarked() const {
453 return PageMap.isAllocated();
454 }
455
456 bool ensurePageMapAllocated() {
457 if (PageMap.isAllocated())
458 return true;
459 PageMap.reset(NumberOfRegions, CountersPerRegion: PagesCount, MaxValue: FullPagesBlockCountMax);
460 return PageMap.isAllocated();
461 }
462
463 // Mark all the blocks in the given range [From, to). Instead of visiting all
464 // the blocks, we will just mark the page as all counted. Note the `From` and
465 // `To` has to be page aligned but with one exception, if `To` is equal to the
466 // RegionSize, it's not necessary to be aligned with page size.
467 bool markRangeAsAllCounted(uptr From, uptr To, uptr Base,
468 const uptr RegionIndex, const uptr RegionSize) {
469 const uptr PageSize = getPageSizeCached();
470 DCHECK_LT(From, To);
471 DCHECK_LE(To, Base + RegionSize);
472 DCHECK_EQ(From % PageSize, 0U);
473 DCHECK_LE(To - From, RegionSize);
474
475 if (!ensurePageMapAllocated())
476 return false;
477
478 uptr FromInRegion = From - Base;
479 uptr ToInRegion = To - Base;
480 uptr FirstBlockInRange = roundUpSlow(X: FromInRegion, Boundary: BlockSize);
481
482 // The straddling block sits across entire range.
483 if (FirstBlockInRange >= ToInRegion)
484 return true;
485
486 // First block may not sit at the first page in the range, move
487 // `FromInRegion` to the first block page.
488 FromInRegion = roundDown(X: FirstBlockInRange, Boundary: PageSize);
489
490 // When The first block is not aligned to the range boundary, which means
491 // there is a block sitting across `From`, that looks like,
492 //
493 // From To
494 // V V
495 // +-----------------------------------------------+
496 // +-----+-----+-----+-----+
497 // | | | | | ...
498 // +-----+-----+-----+-----+
499 // |- first page -||- second page -||- ...
500 //
501 // Therefore, we can't just mark the first page as all counted. Instead, we
502 // increment the number of blocks in the first page in the page map and
503 // then round up the `From` to the next page.
504 if (FirstBlockInRange != FromInRegion) {
505 DCHECK_GT(FromInRegion + PageSize, FirstBlockInRange);
506 uptr NumBlocksInFirstPage =
507 (FromInRegion + PageSize - FirstBlockInRange + BlockSize - 1) /
508 BlockSize;
509 PageMap.incN(Region: RegionIndex, I: getPageIndex(P: FromInRegion),
510 N: NumBlocksInFirstPage);
511 FromInRegion = roundUp(X: FromInRegion + 1, Boundary: PageSize);
512 }
513
514 uptr LastBlockInRange = roundDownSlow(X: ToInRegion - 1, Boundary: BlockSize);
515
516 // Note that LastBlockInRange may be smaller than `FromInRegion` at this
517 // point because it may contain only one block in the range.
518
519 // When the last block sits across `To`, we can't just mark the pages
520 // occupied by the last block as all counted. Instead, we increment the
521 // counters of those pages by 1. The exception is that if it's the last
522 // block in the region, it's fine to mark those pages as all counted.
523 if (LastBlockInRange + BlockSize != RegionSize) {
524 DCHECK_EQ(ToInRegion % PageSize, 0U);
525 // The case below is like,
526 //
527 // From To
528 // V V
529 // +----------------------------------------+
530 // +-----+-----+-----+-----+
531 // | | | | | ...
532 // +-----+-----+-----+-----+
533 // ... -||- last page -||- next page -|
534 //
535 // The last block is not aligned to `To`, we need to increment the
536 // counter of `next page` by 1.
537 if (LastBlockInRange + BlockSize != ToInRegion) {
538 PageMap.incRange(Region: RegionIndex, From: getPageIndex(P: ToInRegion),
539 To: getPageIndex(P: LastBlockInRange + BlockSize - 1));
540 }
541 } else {
542 ToInRegion = RegionSize;
543 }
544
545 // After handling the first page and the last block, it's safe to mark any
546 // page in between the range [From, To).
547 if (FromInRegion < ToInRegion) {
548 PageMap.setAsAllCountedRange(Region: RegionIndex, From: getPageIndex(P: FromInRegion),
549 To: getPageIndex(P: ToInRegion - 1));
550 }
551
552 return true;
553 }
554
555 template <class TransferBatchT, typename DecompactPtrT>
556 bool markFreeBlocksInRegion(const IntrusiveList<TransferBatchT> &FreeList,
557 DecompactPtrT DecompactPtr, const uptr Base,
558 const uptr RegionIndex, const uptr RegionSize,
559 bool MayContainLastBlockInRegion) {
560 if (!ensurePageMapAllocated())
561 return false;
562
563 const uptr PageSize = getPageSizeCached();
564 if (MayContainLastBlockInRegion) {
565 const uptr LastBlockInRegion =
566 ((RegionSize / BlockSize) - 1U) * BlockSize;
567 // The last block in a region may not use the entire page, we mark the
568 // following "pretend" memory block(s) as free in advance.
569 //
570 // Region Boundary
571 // v
572 // -----+-----------------------+
573 // | Last Page | <- Rounded Region Boundary
574 // -----+-----------------------+
575 // |-----||- trailing blocks -|
576 // ^
577 // last block
578 const uptr RoundedRegionSize = roundUp(X: RegionSize, Boundary: PageSize);
579 const uptr TrailingBlockBase = LastBlockInRegion + BlockSize;
580 // If the difference between `RoundedRegionSize` and
581 // `TrailingBlockBase` is larger than a page, that implies the reported
582 // `RegionSize` may not be accurate.
583 DCHECK_LT(RoundedRegionSize - TrailingBlockBase, PageSize);
584
585 // Only the last page touched by the last block needs to mark the trailing
586 // blocks. Note that if the last "pretend" block straddles the boundary,
587 // we still have to count it in so that the logic of counting the number
588 // of blocks on a page is consistent.
589 uptr NumTrailingBlocks =
590 (roundUpSlow(X: RoundedRegionSize - TrailingBlockBase, Boundary: BlockSize) +
591 BlockSize - 1) /
592 BlockSize;
593 if (NumTrailingBlocks > 0) {
594 PageMap.incN(Region: RegionIndex, I: getPageIndex(P: TrailingBlockBase),
595 N: NumTrailingBlocks);
596 }
597 }
598
599 // Iterate over free chunks and count how many free chunks affect each
600 // allocated page.
601 if (BlockSize <= PageSize && PageSize % BlockSize == 0) {
602 // Each chunk affects one page only.
603 for (const auto &It : FreeList) {
604 for (u16 I = 0; I < It.getCount(); I++) {
605 const uptr PInRegion = DecompactPtr(It.get(I)) - Base;
606 DCHECK_LT(PInRegion, RegionSize);
607 PageMap.inc(Region: RegionIndex, I: getPageIndex(P: PInRegion));
608 }
609 }
610 } else {
611 // In all other cases chunks might affect more than one page.
612 DCHECK_GE(RegionSize, BlockSize);
613 for (const auto &It : FreeList) {
614 for (u16 I = 0; I < It.getCount(); I++) {
615 const uptr PInRegion = DecompactPtr(It.get(I)) - Base;
616 PageMap.incRange(Region: RegionIndex, From: getPageIndex(P: PInRegion),
617 To: getPageIndex(P: PInRegion + BlockSize - 1));
618 }
619 }
620 }
621
622 return true;
623 }
624
625 uptr getPageIndex(uptr P) {
626 return (P >> getPageSizeLogCached()) - ReleasePageOffset;
627 }
628 uptr getReleaseOffset() {
629 return ReleasePageOffset << getPageSizeLogCached();
630 }
631
632 uptr BlockSize;
633 uptr NumberOfRegions;
634 // For partial region marking, some pages in front are not needed to be
635 // counted.
636 uptr ReleasePageOffset;
637 uptr PagesCount;
638 uptr FullPagesBlockCountMax;
639 bool SameBlockCountPerPage;
640 RegionPageMap PageMap;
641};
642
643// Try to release the page which doesn't have any in-used block, i.e., they are
644// all free blocks. The `PageMap` will record the number of free blocks in each
645// page.
646template <class ReleaseRecorderT, typename SkipRegionT>
647NOINLINE void
648releaseFreeMemoryToOS(PageReleaseContext &Context,
649 ReleaseRecorderT &Recorder, SkipRegionT SkipRegion) {
650 const uptr PageSize = getPageSizeCached();
651 const uptr BlockSize = Context.BlockSize;
652 const uptr PagesCount = Context.PagesCount;
653 const uptr NumberOfRegions = Context.NumberOfRegions;
654 const uptr ReleasePageOffset = Context.ReleasePageOffset;
655 const uptr FullPagesBlockCountMax = Context.FullPagesBlockCountMax;
656 const bool SameBlockCountPerPage = Context.SameBlockCountPerPage;
657 RegionPageMap &PageMap = Context.PageMap;
658
659 // Iterate over pages detecting ranges of pages with chunk Counters equal
660 // to the expected number of chunks for the particular page.
661 FreePagesRangeTracker<ReleaseRecorderT> RangeTracker(Recorder);
662 if (SameBlockCountPerPage) {
663 // Fast path, every page has the same number of chunks affecting it.
664 for (uptr I = 0; I < NumberOfRegions; I++) {
665 if (SkipRegion(I)) {
666 RangeTracker.skipPages(PagesCount);
667 continue;
668 }
669 for (uptr J = 0; J < PagesCount; J++) {
670 const bool CanRelease =
671 PageMap.updateAsAllCountedIf(Region: I, I: J, MaxCount: FullPagesBlockCountMax);
672 RangeTracker.processNextPage(CanRelease);
673 }
674 }
675 } else {
676 // Slow path, go through the pages keeping count how many chunks affect
677 // each page.
678 const uptr Pn = BlockSize < PageSize ? PageSize / BlockSize : 1;
679 const uptr Pnc = Pn * BlockSize;
680 // The idea is to increment the current page pointer by the first chunk
681 // size, middle portion size (the portion of the page covered by chunks
682 // except the first and the last one) and then the last chunk size, adding
683 // up the number of chunks on the current page and checking on every step
684 // whether the page boundary was crossed.
685 for (uptr I = 0; I < NumberOfRegions; I++) {
686 if (SkipRegion(I)) {
687 RangeTracker.skipPages(PagesCount);
688 continue;
689 }
690 uptr PrevPageBoundary = 0;
691 uptr CurrentBoundary = 0;
692 if (ReleasePageOffset > 0) {
693 PrevPageBoundary = ReleasePageOffset << getPageSizeLogCached();
694 CurrentBoundary = roundUpSlow(X: PrevPageBoundary, Boundary: BlockSize);
695 }
696 for (uptr J = 0; J < PagesCount; J++) {
697 const uptr PageBoundary = PrevPageBoundary + PageSize;
698 uptr BlocksPerPage = Pn;
699 if (CurrentBoundary < PageBoundary) {
700 if (CurrentBoundary > PrevPageBoundary)
701 BlocksPerPage++;
702 CurrentBoundary += Pnc;
703 if (CurrentBoundary < PageBoundary) {
704 BlocksPerPage++;
705 CurrentBoundary += BlockSize;
706 }
707 }
708 PrevPageBoundary = PageBoundary;
709 const bool CanRelease =
710 PageMap.updateAsAllCountedIf(Region: I, I: J, MaxCount: BlocksPerPage);
711 RangeTracker.processNextPage(CanRelease);
712 }
713 }
714 }
715 RangeTracker.finish();
716}
717
718} // namespace scudo
719
720#endif // SCUDO_RELEASE_H_
721