1 // Copyright 2019 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Scavenging free pages.
7 // This file implements scavenging (the release of physical pages backing mapped
8 // memory) of free and unused pages in the heap as a way to deal with page-level
9 // fragmentation and reduce the RSS of Go applications.
11 // Scavenging in Go happens on two fronts: there's the background
12 // (asynchronous) scavenger and the heap-growth (synchronous) scavenger.
14 // The former happens on a goroutine much like the background sweeper which is
15 // soft-capped at using scavengePercent of the mutator's time, based on
16 // order-of-magnitude estimates of the costs of scavenging. The background
17 // scavenger's primary goal is to bring the estimated heap RSS of the
18 // application down to a goal.
20 // That goal is defined as:
21 // (retainExtraPercent+100) / 100 * (heapGoal / lastHeapGoal) * last_heap_inuse
23 // Essentially, we wish to have the application's RSS track the heap goal, but
24 // the heap goal is defined in terms of bytes of objects, rather than pages like
25 // RSS. As a result, we need to take into account for fragmentation internal to
26 // spans. heapGoal / lastHeapGoal defines the ratio between the current heap goal
27 // and the last heap goal, which tells us by how much the heap is growing and
28 // shrinking. We estimate what the heap will grow to in terms of pages by taking
29 // this ratio and multiplying it by heap_inuse at the end of the last GC, which
30 // allows us to account for this additional fragmentation. Note that this
31 // procedure makes the assumption that the degree of fragmentation won't change
32 // dramatically over the next GC cycle. Overestimating the amount of
33 // fragmentation simply results in higher memory use, which will be accounted
34 // for by the next pacing up date. Underestimating the fragmentation however
35 // could lead to performance degradation. Handling this case is not within the
36 // scope of the scavenger. Situations where the amount of fragmentation balloons
37 // over the course of a single GC cycle should be considered pathologies,
38 // flagged as bugs, and fixed appropriately.
40 // An additional factor of retainExtraPercent is added as a buffer to help ensure
41 // that there's more unscavenged memory to allocate out of, since each allocation
42 // out of scavenged memory incurs a potentially expensive page fault.
44 // The goal is updated after each GC and the scavenger's pacing parameters
45 // (which live in mheap_) are updated to match. The pacing parameters work much
46 // like the background sweeping parameters. The parameters define a line whose
47 // horizontal axis is time and vertical axis is estimated heap RSS, and the
48 // scavenger attempts to stay below that line at all times.
50 // The synchronous heap-growth scavenging happens whenever the heap grows in
51 // size, for some definition of heap-growth. The intuition behind this is that
52 // the application had to grow the heap because existing fragments were
53 // not sufficiently large to satisfy a page-level memory allocation, so we
54 // scavenge those fragments eagerly to offset the growth in RSS that results.
60 "runtime/internal/atomic"
61 "runtime/internal/sys"
66 // The background scavenger is paced according to these parameters.
68 // scavengePercent represents the portion of mutator time we're willing
69 // to spend on scavenging in percent.
70 scavengePercent
= 1 // 1%
72 // retainExtraPercent represents the amount of memory over the heap goal
73 // that the scavenger should keep as a buffer space for the allocator.
75 // The purpose of maintaining this overhead is to have a greater pool of
76 // unscavenged memory available for allocation (since using scavenged memory
77 // incurs an additional cost), to account for heap fragmentation and
78 // the ever-changing layout of the heap.
79 retainExtraPercent
= 10
81 // maxPagesPerPhysPage is the maximum number of supported runtime pages per
82 // physical page, based on maxPhysPageSize.
83 maxPagesPerPhysPage
= maxPhysPageSize
/ pageSize
85 // scavengeCostRatio is the approximate ratio between the costs of using previously
86 // scavenged memory and scavenging memory.
88 // For most systems the cost of scavenging greatly outweighs the costs
89 // associated with using scavenged memory, making this constant 0. On other systems
90 // (especially ones where "sysUsed" is not just a no-op) this cost is non-trivial.
92 // This ratio is used as part of multiplicative factor to help the scavenger account
93 // for the additional costs of using scavenged memory in its pacing.
94 scavengeCostRatio
= 0.7 * (goos
.IsDarwin
+ goos
.IsIos
)
96 // scavengeReservationShards determines the amount of memory the scavenger
97 // should reserve for scavenging at a time. Specifically, the amount of
98 // memory reserved is (heap size in bytes) / scavengeReservationShards.
99 scavengeReservationShards
= 64
102 // heapRetained returns an estimate of the current heap RSS.
103 func heapRetained() uint64 {
104 return memstats
.heap_sys
.load() - atomic
.Load64(&memstats
.heap_released
)
107 // gcPaceScavenger updates the scavenger's pacing, particularly
108 // its rate and RSS goal. For this, it requires the current heapGoal,
109 // and the heapGoal for the previous GC cycle.
111 // The RSS goal is based on the current heap goal with a small overhead
112 // to accommodate non-determinism in the allocator.
114 // The pacing is based on scavengePageRate, which applies to both regular and
115 // huge pages. See that constant for more information.
117 // Must be called whenever GC pacing is updated.
119 // mheap_.lock must be held or the world must be stopped.
120 func gcPaceScavenger(heapGoal
, lastHeapGoal
uint64) {
121 assertWorldStoppedOrLockHeld(&mheap_
.lock
)
123 // If we're called before the first GC completed, disable scavenging.
124 // We never scavenge before the 2nd GC cycle anyway (we don't have enough
125 // information about the heap yet) so this is fine, and avoids a fault
126 // or garbage data later.
127 if lastHeapGoal
== 0 {
128 atomic
.Store64(&mheap_
.scavengeGoal
, ^uint64(0))
131 // Compute our scavenging goal.
132 goalRatio
:= float64(heapGoal
) / float64(lastHeapGoal
)
133 retainedGoal
:= uint64(float64(memstats
.last_heap_inuse
) * goalRatio
)
134 // Add retainExtraPercent overhead to retainedGoal. This calculation
135 // looks strange but the purpose is to arrive at an integer division
136 // (e.g. if retainExtraPercent = 12.5, then we get a divisor of 8)
137 // that also avoids the overflow from a multiplication.
138 retainedGoal
+= retainedGoal
/ (1.0 / (retainExtraPercent
/ 100.0))
139 // Align it to a physical page boundary to make the following calculations
141 retainedGoal
= (retainedGoal
+ uint64(physPageSize
) - 1) &^ (uint64(physPageSize
) - 1)
143 // Represents where we are now in the heap's contribution to RSS in bytes.
145 // Guaranteed to always be a multiple of physPageSize on systems where
146 // physPageSize <= pageSize since we map heap_sys at a rate larger than
147 // any physPageSize and released memory in multiples of the physPageSize.
149 // However, certain functions recategorize heap_sys as other stats (e.g.
150 // stack_sys) and this happens in multiples of pageSize, so on systems
151 // where physPageSize > pageSize the calculations below will not be exact.
152 // Generally this is OK since we'll be off by at most one regular
154 retainedNow
:= heapRetained()
156 // If we're already below our goal, or within one page of our goal, then disable
157 // the background scavenger. We disable the background scavenger if there's
158 // less than one physical page of work to do because it's not worth it.
159 if retainedNow
<= retainedGoal || retainedNow
-retainedGoal
< uint64(physPageSize
) {
160 atomic
.Store64(&mheap_
.scavengeGoal
, ^uint64(0))
163 atomic
.Store64(&mheap_
.scavengeGoal
, retainedGoal
)
166 // Sleep/wait state of the background scavenger.
167 var scavenge
struct {
172 sysmonWake
uint32 // Set atomically.
173 printControllerReset
bool // Whether the scavenger is in cooldown.
176 // readyForScavenger signals sysmon to wake the scavenger because
177 // there may be new work to do.
179 // There may be a significant delay between when this function runs
180 // and when the scavenger is kicked awake, but it may be safely invoked
181 // in contexts where wakeScavenger is unsafe to call directly.
182 func readyForScavenger() {
183 atomic
.Store(&scavenge
.sysmonWake
, 1)
186 // wakeScavenger immediately unparks the scavenger if necessary.
188 // May run without a P, but it may allocate, so it must not be called
189 // on any allocation path.
191 // mheap_.lock, scavenge.lock, and sched.lock must not be held.
192 func wakeScavenger() {
195 // Notify sysmon that it shouldn't bother waking up the scavenger.
196 atomic
.Store(&scavenge
.sysmonWake
, 0)
198 // Try to stop the timer but we don't really care if we succeed.
199 // It's possible that either a timer was never started, or that
200 // we're racing with it.
201 // In the case that we're racing with there's the low chance that
202 // we experience a spurious wake-up of the scavenger, but that's
204 stopTimer(scavenge
.timer
)
206 // Unpark the goroutine and tell it that there may have been a pacing
207 // change. Note that we skip the scheduler's runnext slot because we
208 // want to avoid having the scavenger interfere with the fair
209 // scheduling of user goroutines. In effect, this schedules the
210 // scavenger at a "lower priority" but that's OK because it'll
211 // catch up on the work it missed when it does get scheduled.
212 scavenge
.parked
= false
214 // Ready the goroutine by injecting it. We use injectglist instead
215 // of ready or goready in order to allow us to run this function
216 // without a P. injectglist also avoids placing the goroutine in
217 // the current P's runnext slot, which is desirable to prevent
218 // the scavenger from interfering with user goroutine scheduling
221 list
.push(scavenge
.g
)
224 unlock(&scavenge
.lock
)
227 // scavengeSleep attempts to put the scavenger to sleep for ns.
229 // Note that this function should only be called by the scavenger.
231 // The scavenger may be woken up earlier by a pacing change, and it may not go
232 // to sleep at all if there's a pending pacing change.
234 // Returns the amount of time actually slept.
235 func scavengeSleep(ns
int64) int64 {
240 // This must happen here instead of inside gopark
241 // because we can't close over any variables without
242 // failing escape analysis.
244 resetTimer(scavenge
.timer
, start
+ns
)
246 // Mark ourself as asleep and go to sleep.
247 scavenge
.parked
= true
248 goparkunlock(&scavenge
.lock
, waitReasonSleep
, traceEvGoSleep
, 2)
250 // Return how long we actually slept for.
251 return nanotime() - start
254 // Background scavenger.
256 // The background scavenger maintains the RSS of the application below
257 // the line described by the proportional scavenging statistics in
259 func bgscavenge(c
chan int) {
264 lockInit(&scavenge
.lock
, lockRankScavenge
)
266 scavenge
.parked
= true
268 scavenge
.timer
= new(timer
)
269 scavenge
.timer
.f
= func(_ any
, _
uintptr) {
274 goparkunlock(&scavenge
.lock
, waitReasonGCScavengeWait
, traceEvGoBlock
, 1)
276 // idealFraction is the ideal % of overall application CPU time that we
278 idealFraction
:= float64(scavengePercent
) / 100.0
280 // Input: fraction of CPU time used.
281 // Setpoint: idealFraction.
282 // Output: ratio of critical time to sleep time (determines sleep time).
284 // The output of this controller is somewhat indirect to what we actually
285 // want to achieve: how much time to sleep for. The reason for this definition
286 // is to ensure that the controller's outputs have a direct relationship with
287 // its inputs (as opposed to an inverse relationship), making it somewhat
288 // easier to reason about for tuning purposes.
289 critSleepController
:= piController
{
290 // Tuned loosely via Ziegler-Nichols process.
293 tt
: 1e9
, // 1 second reset time.
295 // These ranges seem wide, but we want to give the controller plenty of
296 // room to hunt for the optimal value.
297 min
: 0.001, // 1:1000
298 max
: 1000.0, // 1000:1
300 // It doesn't really matter what value we start at, but we can't be zero, because
301 // that'll cause divide-by-zero issues. Pick something conservative which we'll
302 // also use as a fallback.
303 const startingCritSleepRatio
= 0.001
304 critSleepRatio
:= startingCritSleepRatio
305 // Duration left in nanoseconds during which we avoid using the controller and
306 // we hold critSleepRatio at a conservative value. Used if the controller's
307 // assumptions fail to hold.
308 controllerCooldown
:= int64(0)
310 released
:= uintptr(0)
313 // Spend at least 1 ms scavenging, otherwise the corresponding
314 // sleep time to maintain our desired utilization is too low to
316 const minCritTime
= 1e6
317 for crit
< minCritTime
{
318 // If background scavenging is disabled or if there's no work to do just park.
319 retained
, goal
:= heapRetained(), atomic
.Load64(&mheap_
.scavengeGoal
)
320 if retained
<= goal
{
324 // scavengeQuantum is the amount of memory we try to scavenge
325 // in one go. A smaller value means the scavenger is more responsive
326 // to the scheduler in case of e.g. preemption. A larger value means
327 // that the overheads of scavenging are better amortized, so better
328 // scavenging throughput.
330 // The current value is chosen assuming a cost of ~10µs/physical page
331 // (this is somewhat pessimistic), which implies a worst-case latency of
332 // about 160µs for 4 KiB physical pages. The current value is biased
333 // toward latency over throughput.
334 const scavengeQuantum
= 64 << 10
336 // Accumulate the amount of time spent scavenging.
338 r
:= mheap_
.pages
.scavenge(scavengeQuantum
)
339 atomic
.Xadduintptr(&mheap_
.pages
.scav
.released
, r
)
342 // On some platforms we may see end >= start if the time it takes to scavenge
343 // memory is less than the minimum granularity of its clock (e.g. Windows) or
344 // due to clock bugs.
346 // In this case, just assume scavenging takes 10 µs per regular physical page
347 // (determined empirically), and conservatively ignore the impact of huge pages
349 const approxCritNSPerPhysicalPage
= 10e3
351 crit
+= approxCritNSPerPhysicalPage
* float64(r
/physPageSize
)
353 crit
+= float64(end
- start
)
357 // When using fake time just do one loop.
365 scavenge
.parked
= true
366 goparkunlock(&scavenge
.lock
, waitReasonGCScavengeWait
, traceEvGoBlock
, 1)
370 if released
< physPageSize
{
371 // If this happens, it means that we may have attempted to release part
372 // of a physical page, but the likely effect of that is that it released
373 // the whole physical page, some of which may have still been in-use.
374 // This could lead to memory corruption. Throw.
375 throw("released less than one physical page of memory")
378 if crit
< minCritTime
{
379 // This means there wasn't enough work to actually fill up minCritTime.
380 // That's fine; we shouldn't try to do anything with this information
381 // because it's going result in a short enough sleep request that things
382 // will get messy. Just assume we did at least this much work.
383 // All this means is that we'll sleep longer than we otherwise would have.
387 // Multiply the critical time by 1 + the ratio of the costs of using
388 // scavenged memory vs. scavenging memory. This forces us to pay down
389 // the cost of reusing this memory eagerly by sleeping for a longer period
390 // of time and scavenging less frequently. More concretely, we avoid situations
391 // where we end up scavenging so often that we hurt allocation performance
392 // because of the additional overheads of using scavenged memory.
393 crit
*= 1 + scavengeCostRatio
395 // Go to sleep based on how much time we spent doing work.
396 slept
:= scavengeSleep(int64(crit
/ critSleepRatio
))
398 // Stop here if we're cooling down from the controller.
399 if controllerCooldown
> 0 {
400 // crit and slept aren't exact measures of time, but it's OK to be a bit
401 // sloppy here. We're just hoping we're avoiding some transient bad behavior.
402 t
:= slept
+ int64(crit
)
403 if t
> controllerCooldown
{
404 controllerCooldown
= 0
406 controllerCooldown
-= t
411 // Calculate the CPU time spent.
413 // This may be slightly inaccurate with respect to GOMAXPROCS, but we're
414 // recomputing this often enough relative to GOMAXPROCS changes in general
415 // (it only changes when the world is stopped, and not during a GC) that
416 // that small inaccuracy is in the noise.
417 cpuFraction
:= float64(crit
) / ((float64(slept
) + crit
) * float64(gomaxprocs
))
419 // Update the critSleepRatio, adjusting until we reach our ideal fraction.
421 critSleepRatio
, ok
= critSleepController
.next(cpuFraction
, idealFraction
, float64(slept
)+crit
)
423 // The core assumption of the controller, that we can get a proportional
424 // response, broke down. This may be transient, so temporarily switch to
425 // sleeping a fixed, conservative amount.
426 critSleepRatio
= startingCritSleepRatio
427 controllerCooldown
= 5e9
// 5 seconds.
429 // Signal the scav trace printer to output this.
431 scavenge
.printControllerReset
= true
432 unlock(&scavenge
.lock
)
437 // scavenge scavenges nbytes worth of free pages, starting with the
438 // highest address first. Successive calls continue from where it left
439 // off until the heap is exhausted. Call scavengeStartGen to bring it
440 // back to the top of the heap.
442 // Returns the amount of memory scavenged in bytes.
443 func (p
*pageAlloc
) scavenge(nbytes
uintptr) uintptr {
448 released
:= uintptr(0)
449 for released
< nbytes
{
450 if addrs
.size() == 0 {
451 if addrs
, gen
= p
.scavengeReserve(); addrs
.size() == 0 {
456 r
, a
:= p
.scavengeOne(addrs
, nbytes
-released
)
461 // Only unreserve the space which hasn't been scavenged or searched
462 // to ensure we always make progress.
463 p
.scavengeUnreserve(addrs
, gen
)
467 // printScavTrace prints a scavenge trace line to standard error.
469 // released should be the amount of memory released since the last time this
470 // was called, and forced indicates whether the scavenge was forced by the
473 // scavenge.lock must be held.
474 func printScavTrace(gen
uint32, released
uintptr, forced
bool) {
475 assertLockHeld(&scavenge
.lock
)
478 print("scav ", gen
, " ",
479 released
>>10, " KiB work, ",
480 atomic
.Load64(&memstats
.heap_released
)>>10, " KiB total, ",
481 (atomic
.Load64(&memstats
.heap_inuse
)*100)/heapRetained(), "% util",
485 } else if scavenge
.printControllerReset
{
486 print(" [controller reset]")
487 scavenge
.printControllerReset
= false
493 // scavengeStartGen starts a new scavenge generation, resetting
494 // the scavenger's search space to the full in-use address space.
496 // p.mheapLock must be held.
498 // Must run on the system stack because p.mheapLock must be held.
501 func (p
*pageAlloc
) scavengeStartGen() {
502 assertLockHeld(p
.mheapLock
)
505 if debug
.scavtrace
> 0 {
506 printScavTrace(p
.scav
.gen
, atomic
.Loaduintptr(&p
.scav
.released
), false)
508 p
.inUse
.cloneInto(&p
.scav
.inUse
)
510 // Pick the new starting address for the scavenger cycle.
511 var startAddr offAddr
512 if p
.scav
.scavLWM
.lessThan(p
.scav
.freeHWM
) {
513 // The "free" high watermark exceeds the "scavenged" low watermark,
514 // so there are free scavengable pages in parts of the address space
515 // that the scavenger already searched, the high watermark being the
516 // highest one. Pick that as our new starting point to ensure we
518 startAddr
= p
.scav
.freeHWM
520 // The "free" high watermark does not exceed the "scavenged" low
521 // watermark. This means the allocator didn't free any memory in
522 // the range we scavenged last cycle, so we might as well continue
523 // scavenging from where we were.
524 startAddr
= p
.scav
.scavLWM
526 p
.scav
.inUse
.removeGreaterEqual(startAddr
.addr())
528 // reservationBytes may be zero if p.inUse.totalBytes is small, or if
529 // scavengeReservationShards is large. This case is fine as the scavenger
530 // will simply be turned off, but it does mean that scavengeReservationShards,
531 // in concert with pallocChunkBytes, dictates the minimum heap size at which
532 // the scavenger triggers. In practice this minimum is generally less than an
533 // arena in size, so virtually every heap has the scavenger on.
534 p
.scav
.reservationBytes
= alignUp(p
.inUse
.totalBytes
, pallocChunkBytes
) / scavengeReservationShards
536 atomic
.Storeuintptr(&p
.scav
.released
, 0)
537 p
.scav
.freeHWM
= minOffAddr
538 p
.scav
.scavLWM
= maxOffAddr
542 // scavengeReserve reserves a contiguous range of the address space
543 // for scavenging. The maximum amount of space it reserves is proportional
544 // to the size of the heap. The ranges are reserved from the high addresses
547 // Returns the reserved range and the scavenge generation number for it.
548 func (p
*pageAlloc
) scavengeReserve() (addrRange
, uint32) {
552 // Start by reserving the minimum.
553 r
:= p
.scav
.inUse
.removeLast(p
.scav
.reservationBytes
)
555 // Return early if the size is zero; we don't want to use
556 // the bogus address below.
562 // The scavenger requires that base be aligned to a
563 // palloc chunk because that's the unit of operation for
564 // the scavenger, so align down, potentially extending
566 newBase
:= alignDown(r
.base
.addr(), pallocChunkBytes
)
568 // Remove from inUse however much extra we just pulled out.
569 p
.scav
.inUse
.removeGreaterEqual(newBase
)
572 r
.base
= offAddr
{newBase
}
576 // scavengeUnreserve returns an unscavenged portion of a range that was
577 // previously reserved with scavengeReserve.
578 func (p
*pageAlloc
) scavengeUnreserve(r addrRange
, gen
uint32) {
582 if r
.base
.addr()%pallocChunkBytes
!= 0 {
583 throw("unreserving unaligned region")
586 if gen
== p
.scav
.gen
{
592 // scavengeOne walks over address range work until it finds
593 // a contiguous run of pages to scavenge. It will try to scavenge
594 // at most max bytes at once, but may scavenge more to avoid
595 // breaking huge pages. Once it scavenges some memory it returns
596 // how much it scavenged in bytes.
598 // Returns the number of bytes scavenged and the part of work
599 // which was not yet searched.
601 // work's base address must be aligned to pallocChunkBytes.
603 // Must run on the systemstack because it acquires p.mheapLock.
606 func (p
*pageAlloc
) scavengeOne(work addrRange
, max
uintptr) (uintptr, addrRange
) {
607 // Defensively check if we've received an empty address range.
608 // If so, just return.
609 if work
.size() == 0 {
613 // Check the prerequisites of work.
614 if work
.base
.addr()%pallocChunkBytes
!= 0 {
615 throw("scavengeOne called with unaligned work region")
617 // Calculate the maximum number of pages to scavenge.
619 // This should be alignUp(max, pageSize) / pageSize but max can and will
620 // be ^uintptr(0), so we need to be very careful not to overflow here.
621 // Rather than use alignUp, calculate the number of pages rounded down
622 // first, then add back one if necessary.
623 maxPages
:= max
/ pageSize
624 if max%pageSize
!= 0 {
628 // Calculate the minimum number of pages we can scavenge.
630 // Because we can only scavenge whole physical pages, we must
631 // ensure that we scavenge at least minPages each time, aligned
632 // to minPages*pageSize.
633 minPages
:= physPageSize
/ pageSize
638 // Fast path: check the chunk containing the top-most address in work.
639 if r
, w
:= p
.scavengeOneFast(work
, minPages
, maxPages
); r
!= 0 {
645 // findCandidate finds the next scavenge candidate in work optimistically.
647 // Returns the candidate chunk index and true on success, and false on failure.
649 // The heap need not be locked.
650 findCandidate
:= func(work addrRange
) (chunkIdx
, bool) {
651 // Iterate over this work's chunks.
652 for i
:= chunkIndex(work
.limit
.addr() - 1); i
>= chunkIndex(work
.base
.addr()); i
-- {
653 // If this chunk is totally in-use or has no unscavenged pages, don't bother
654 // doing a more sophisticated check.
656 // Note we're accessing the summary and the chunks without a lock, but
657 // that's fine. We're being optimistic anyway.
659 // Check quickly if there are enough free pages at all.
660 if p
.summary
[len(p
.summary
)-1][i
].max() < uint(minPages
) {
664 // Run over the chunk looking harder for a candidate. Again, we could
665 // race with a lot of different pieces of code, but we're just being
666 // optimistic. Make sure we load the l2 pointer atomically though, to
667 // avoid races with heap growth. It may or may not be possible to also
668 // see a nil pointer in this case if we do race with heap growth, but
669 // just defensively ignore the nils. This operation is optimistic anyway.
670 l2
:= (*[1 << pallocChunksL2Bits
]pallocData
)(atomic
.Loadp(unsafe
.Pointer(&p
.chunks
[i
.l1()])))
671 if l2
!= nil && l2
[i
.l2()].hasScavengeCandidate(minPages
) {
678 // Slow path: iterate optimistically over the in-use address space
679 // looking for any free and unscavenged page. If we think we see something,
680 // lock and verify it!
681 for work
.size() != 0 {
683 // Search for the candidate.
684 candidateChunkIdx
, ok
:= findCandidate(work
)
686 // We didn't find a candidate, so we're done.
687 work
.limit
= work
.base
691 // Lock, so we can verify what we found.
694 // Find, verify, and scavenge if we can.
695 chunk
:= p
.chunkOf(candidateChunkIdx
)
696 base
, npages
:= chunk
.findScavengeCandidate(pallocChunkPages
-1, minPages
, maxPages
)
698 work
.limit
= offAddr
{p
.scavengeRangeLocked(candidateChunkIdx
, base
, npages
)}
700 return uintptr(npages
) * pageSize
, work
704 // We were fooled, so let's continue from where we left off.
705 work
.limit
= offAddr
{chunkBase(candidateChunkIdx
)}
710 // scavengeOneFast is the fast path for scavengeOne, which just checks the top
711 // chunk of work for some pages to scavenge.
713 // Must run on the system stack because it acquires the heap lock.
716 func (p
*pageAlloc
) scavengeOneFast(work addrRange
, minPages
, maxPages
uintptr) (uintptr, addrRange
) {
717 maxAddr
:= work
.limit
.addr() - 1
718 maxChunk
:= chunkIndex(maxAddr
)
721 if p
.summary
[len(p
.summary
)-1][maxChunk
].max() >= uint(minPages
) {
722 // We only bother looking for a candidate if there at least
723 // minPages free pages at all.
724 base
, npages
:= p
.chunkOf(maxChunk
).findScavengeCandidate(chunkPageIndex(maxAddr
), minPages
, maxPages
)
726 // If we found something, scavenge it and return!
728 work
.limit
= offAddr
{p
.scavengeRangeLocked(maxChunk
, base
, npages
)}
730 return uintptr(npages
) * pageSize
, work
735 // Update the limit to reflect the fact that we checked maxChunk already.
736 work
.limit
= offAddr
{chunkBase(maxChunk
)}
740 // scavengeRangeLocked scavenges the given region of memory.
741 // The region of memory is described by its chunk index (ci),
742 // the starting page index of the region relative to that
743 // chunk (base), and the length of the region in pages (npages).
745 // Returns the base address of the scavenged region.
747 // p.mheapLock must be held. Unlocks p.mheapLock but reacquires
748 // it before returning. Must be run on the systemstack as a result.
751 func (p
*pageAlloc
) scavengeRangeLocked(ci chunkIdx
, base
, npages
uint) uintptr {
752 assertLockHeld(p
.mheapLock
)
754 // Compute the full address for the start of the range.
755 addr
:= chunkBase(ci
) + uintptr(base
)*pageSize
757 // Mark the range we're about to scavenge as allocated, because
758 // we don't want any allocating goroutines to grab it while
759 // the scavenging is in progress.
760 if scav
:= p
.allocRange(addr
, uintptr(npages
)); scav
!= 0 {
761 throw("double scavenge")
764 // With that done, it's safe to unlock.
767 // Update the scavenge low watermark.
769 if oAddr
:= (offAddr
{addr
}); oAddr
.lessThan(p
.scav
.scavLWM
) {
770 p
.scav
.scavLWM
= oAddr
775 // Only perform the actual scavenging if we're not in a test.
776 // It's dangerous to do so otherwise.
777 sysUnused(unsafe
.Pointer(addr
), uintptr(npages
)*pageSize
)
779 // Update global accounting only when not in test, otherwise
780 // the runtime's accounting will be wrong.
781 nbytes
:= int64(npages
) * pageSize
782 atomic
.Xadd64(&memstats
.heap_released
, nbytes
)
784 // Update consistent accounting too.
785 stats
:= memstats
.heapStats
.acquire()
786 atomic
.Xaddint64(&stats
.committed
, -nbytes
)
787 atomic
.Xaddint64(&stats
.released
, nbytes
)
788 memstats
.heapStats
.release()
791 // Relock the heap, because now we need to make these pages
792 // available allocation. Free them back to the page allocator.
794 p
.free(addr
, uintptr(npages
), true)
796 // Mark the range as scavenged.
797 p
.chunkOf(ci
).scavenged
.setRange(base
, npages
)
801 // fillAligned returns x but with all zeroes in m-aligned
802 // groups of m bits set to 1 if any bit in the group is non-zero.
804 // For example, fillAligned(0x0100a3, 8) == 0xff00ff.
806 // Note that if m == 1, this is a no-op.
808 // m must be a power of 2 <= maxPagesPerPhysPage.
809 func fillAligned(x
uint64, m
uint) uint64 {
810 apply
:= func(x
uint64, c
uint64) uint64 {
811 // The technique used it here is derived from
812 // https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
813 // and extended for more than just bytes (like nibbles
814 // and uint16s) by using an appropriate constant.
816 // To summarize the technique, quoting from that page:
817 // "[It] works by first zeroing the high bits of the [8]
818 // bytes in the word. Subsequently, it adds a number that
819 // will result in an overflow to the high bit of a byte if
820 // any of the low bits were initially set. Next the high
821 // bits of the original word are ORed with these values;
822 // thus, the high bit of a byte is set iff any bit in the
823 // byte was set. Finally, we determine if any of these high
824 // bits are zero by ORing with ones everywhere except the
825 // high bits and inverting the result."
826 return ^((((x
& c
) + c
) | x
) | c
)
828 // Transform x to contain a 1 bit at the top of each m-aligned
829 // group of m zero bits.
834 x
= apply(x
, 0x5555555555555555)
836 x
= apply(x
, 0x7777777777777777)
838 x
= apply(x
, 0x7f7f7f7f7f7f7f7f)
840 x
= apply(x
, 0x7fff7fff7fff7fff)
842 x
= apply(x
, 0x7fffffff7fffffff)
843 case 64: // == maxPagesPerPhysPage
844 x
= apply(x
, 0x7fffffffffffffff)
848 // Now, the top bit of each m-aligned group in x is set
849 // that group was all zero in the original x.
851 // From each group of m bits subtract 1.
852 // Because we know only the top bits of each
853 // m-aligned group are set, we know this will
854 // set each group to have all the bits set except
855 // the top bit, so just OR with the original
856 // result to set all the bits.
857 return ^((x
- (x
>> (m
- 1))) | x
)
860 // hasScavengeCandidate returns true if there's any min-page-aligned groups of
861 // min pages of free-and-unscavenged memory in the region represented by this
864 // min must be a non-zero power of 2 <= maxPagesPerPhysPage.
865 func (m
*pallocData
) hasScavengeCandidate(min
uintptr) bool {
866 if min
&(min
-1) != 0 || min
== 0 {
867 print("runtime: min = ", min
, "\n")
868 throw("min must be a non-zero power of 2")
869 } else if min
> maxPagesPerPhysPage
{
870 print("runtime: min = ", min
, "\n")
871 throw("min too large")
874 // The goal of this search is to see if the chunk contains any free and unscavenged memory.
875 for i
:= len(m
.scavenged
) - 1; i
>= 0; i
-- {
876 // 1s are scavenged OR non-free => 0s are unscavenged AND free
878 // TODO(mknyszek): Consider splitting up fillAligned into two
879 // functions, since here we technically could get by with just
880 // the first half of its computation. It'll save a few instructions
881 // but adds some additional code complexity.
882 x
:= fillAligned(m
.scavenged
[i
]|m
.pallocBits
[i
], uint(min
))
884 // Quickly skip over chunks of non-free or scavenged pages.
892 // findScavengeCandidate returns a start index and a size for this pallocData
893 // segment which represents a contiguous region of free and unscavenged memory.
895 // searchIdx indicates the page index within this chunk to start the search, but
896 // note that findScavengeCandidate searches backwards through the pallocData. As a
897 // a result, it will return the highest scavenge candidate in address order.
899 // min indicates a hard minimum size and alignment for runs of pages. That is,
900 // findScavengeCandidate will not return a region smaller than min pages in size,
901 // or that is min pages or greater in size but not aligned to min. min must be
902 // a non-zero power of 2 <= maxPagesPerPhysPage.
904 // max is a hint for how big of a region is desired. If max >= pallocChunkPages, then
905 // findScavengeCandidate effectively returns entire free and unscavenged regions.
906 // If max < pallocChunkPages, it may truncate the returned region such that size is
907 // max. However, findScavengeCandidate may still return a larger region if, for
908 // example, it chooses to preserve huge pages, or if max is not aligned to min (it
909 // will round up). That is, even if max is small, the returned size is not guaranteed
910 // to be equal to max. max is allowed to be less than min, in which case it is as if
912 func (m
*pallocData
) findScavengeCandidate(searchIdx
uint, min
, max
uintptr) (uint, uint) {
913 if min
&(min
-1) != 0 || min
== 0 {
914 print("runtime: min = ", min
, "\n")
915 throw("min must be a non-zero power of 2")
916 } else if min
> maxPagesPerPhysPage
{
917 print("runtime: min = ", min
, "\n")
918 throw("min too large")
920 // max may not be min-aligned, so we might accidentally truncate to
921 // a max value which causes us to return a non-min-aligned value.
922 // To prevent this, align max up to a multiple of min (which is always
923 // a power of 2). This also prevents max from ever being less than
924 // min, unless it's zero, so handle that explicitly.
928 max
= alignUp(max
, min
)
931 i
:= int(searchIdx
/ 64)
932 // Start by quickly skipping over blocks of non-free or scavenged pages.
934 // 1s are scavenged OR non-free => 0s are unscavenged AND free
935 x
:= fillAligned(m
.scavenged
[i
]|m
.pallocBits
[i
], uint(min
))
941 // Failed to find any free/unscavenged pages.
944 // We have something in the 64-bit chunk at i, but it could
945 // extend further. Loop until we find the extent of it.
947 // 1s are scavenged OR non-free => 0s are unscavenged AND free
948 x
:= fillAligned(m
.scavenged
[i
]|m
.pallocBits
[i
], uint(min
))
949 z1
:= uint(sys
.LeadingZeros64(^x
))
950 run
, end
:= uint(0), uint(i
)*64+(64-z1
)
952 // After shifting out z1 bits, we still have 1s,
953 // so the run ends inside this word.
954 run
= uint(sys
.LeadingZeros64(x
<< z1
))
956 // After shifting out z1 bits, we have no more 1s.
957 // This means the run extends to the bottom of the
958 // word so it may extend into further words.
960 for j
:= i
- 1; j
>= 0; j
-- {
961 x
:= fillAligned(m
.scavenged
[j
]|m
.pallocBits
[j
], uint(min
))
962 run
+= uint(sys
.LeadingZeros64(x
))
964 // The run stopped in this word.
970 // Split the run we found if it's larger than max but hold on to
971 // our original length, since we may need it later.
973 if size
> uint(max
) {
978 // Each huge page is guaranteed to fit in a single palloc chunk.
980 // TODO(mknyszek): Support larger huge page sizes.
981 // TODO(mknyszek): Consider taking pages-per-huge-page as a parameter
982 // so we can write tests for this.
983 if physHugePageSize
> pageSize
&& physHugePageSize
> physPageSize
{
984 // We have huge pages, so let's ensure we don't break one by scavenging
985 // over a huge page boundary. If the range [start, start+size) overlaps with
986 // a free-and-unscavenged huge page, we want to grow the region we scavenge
987 // to include that huge page.
989 // Compute the huge page boundary above our candidate.
990 pagesPerHugePage
:= uintptr(physHugePageSize
/ pageSize
)
991 hugePageAbove
:= uint(alignUp(uintptr(start
), pagesPerHugePage
))
993 // If that boundary is within our current candidate, then we may be breaking
995 if hugePageAbove
<= end
{
996 // Compute the huge page boundary below our candidate.
997 hugePageBelow
:= uint(alignDown(uintptr(start
), pagesPerHugePage
))
999 if hugePageBelow
>= end
-run
{
1000 // We're in danger of breaking apart a huge page since start+size crosses
1001 // a huge page boundary and rounding down start to the nearest huge
1002 // page boundary is included in the full run we found. Include the entire
1003 // huge page in the bound by rounding down to the huge page size.
1004 size
= size
+ (start
- hugePageBelow
)
1005 start
= hugePageBelow