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