1 // Copyright 2009 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 // Garbage collector: sweeping
7 // The sweeper consists of two different algorithms:
9 // * The object reclaimer finds and frees unmarked slots in spans. It
10 // can free a whole span if none of the objects are marked, but that
11 // isn't its goal. This can be driven either synchronously by
12 // mcentral.cacheSpan for mcentral spans, or asynchronously by
13 // sweepone from the list of all in-use spans in mheap_.sweepSpans.
15 // * The span reclaimer looks for spans that contain no marked objects
16 // and frees whole spans. This is a separate algorithm because
17 // freeing whole spans is the hardest task for the object reclaimer,
18 // but is critical when allocating new spans. The entry point for
19 // this is mheap_.reclaim and it's driven by a sequential scan of
20 // the page marks bitmap in the heap arenas.
22 // Both algorithms ultimately call mspan.sweep, which sweeps a single
28 "runtime/internal/atomic"
34 // State of background sweep.
35 type sweepdata struct {
45 // finishsweep_m ensures that all spans are swept.
47 // The world must be stopped. This ensures there are no sweeps in
51 func finishsweep_m() {
52 // Sweeping must be complete before marking commences, so
53 // sweep any unswept spans. If this is a concurrent GC, there
54 // shouldn't be any spans left to sweep, so this should finish
55 // instantly. If GC was forced before the concurrent sweep
56 // finished, there may be spans to sweep.
57 for sweepone() != ^uintptr(0) {
61 nextMarkBitArenaEpoch()
64 func bgsweep(c chan int) {
70 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1)
73 for sweepone() != ^uintptr(0) {
77 for freeSomeWbufs(true) {
82 // This can happen if a GC runs between
83 // gosweepone returning ^0 above
84 // and the lock being acquired.
89 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1)
93 // sweepone sweeps some unswept heap span and returns the number of pages returned
94 // to the heap, or ^uintptr(0) if there was nothing to sweep.
95 func sweepone() uintptr {
97 sweepRatio := mheap_.sweepPagesPerByte // For debugging
99 // increment locks to ensure that the goroutine is not preempted
100 // in the middle of sweep thus leaving the span in an inconsistent state for next GC
102 if atomic.Load(&mheap_.sweepdone) != 0 {
106 atomic.Xadd(&mheap_.sweepers, +1)
108 // Find a span to sweep.
110 sg := mheap_.sweepgen
112 s = mheap_.sweepSpans[1-sg/2%2].pop()
114 atomic.Store(&mheap_.sweepdone, 1)
117 if state := s.state.get(); state != mSpanInUse {
118 // This can happen if direct sweeping already
119 // swept this span, but in that case the sweep
120 // generation should always be up-to-date.
121 if !(s.sweepgen == sg || s.sweepgen == sg+3) {
122 print("runtime: bad span s.state=", state, " s.sweepgen=", s.sweepgen, " sweepgen=", sg, "\n")
123 throw("non in-use span in unswept list")
127 if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
132 // Sweep the span we found.
133 npages := ^uintptr(0)
137 // Whole span was freed. Count it toward the
138 // page reclaimer credit since these pages can
139 // now be used for span allocation.
140 atomic.Xadduintptr(&mheap_.reclaimCredit, npages)
142 // Span is still in-use, so this returned no
143 // pages to the heap and the span needs to
144 // move to the swept in-use list.
149 // Decrement the number of active sweepers and if this is the
150 // last one print trace information.
151 if atomic.Xadd(&mheap_.sweepers, -1) == 0 && atomic.Load(&mheap_.sweepdone) != 0 {
152 if debug.gcpacertrace > 0 {
153 print("pacer: sweep done at heap size ", memstats.heap_live>>20, "MB; allocated ", (memstats.heap_live-mheap_.sweepHeapLiveBasis)>>20, "MB during sweep; swept ", mheap_.pagesSwept, " pages at ", sweepRatio, " pages/byte\n")
160 // isSweepDone reports whether all spans are swept or currently being swept.
162 // Note that this condition may transition from false to true at any
163 // time as the sweeper runs. It may transition from true to false if a
164 // GC runs; to prevent that the caller must be non-preemptible or must
165 // somehow block GC progress.
166 func isSweepDone() bool {
167 return mheap_.sweepdone != 0
170 // Returns only when span s has been swept.
172 func (s *mspan) ensureSwept() {
173 // Caller must disable preemption.
174 // Otherwise when this function returns the span can become unswept again
175 // (if GC is triggered on another goroutine).
177 if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
178 throw("mspan.ensureSwept: m is not locked")
181 sg := mheap_.sweepgen
182 spangen := atomic.Load(&s.sweepgen)
183 if spangen == sg || spangen == sg+3 {
186 // The caller must be sure that the span is a mSpanInUse span.
187 if atomic.Cas(&s.sweepgen, sg-2, sg-1) {
191 // unfortunate condition, and we don't have efficient means to wait
193 spangen := atomic.Load(&s.sweepgen)
194 if spangen == sg || spangen == sg+3 {
201 // Sweep frees or collects finalizers for blocks not marked in the mark phase.
202 // It clears the mark bits in preparation for the next GC round.
203 // Returns true if the span was returned to heap.
204 // If preserve=true, don't return it to heap nor relink in mcentral lists;
205 // caller takes care of it.
206 func (s *mspan) sweep(preserve bool) bool {
207 // It's critical that we enter this function with preemption disabled,
208 // GC must not start while we are in the middle of this function.
210 if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
211 throw("mspan.sweep: m is not locked")
213 sweepgen := mheap_.sweepgen
214 if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
215 print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
216 throw("mspan.sweep: bad span state")
220 traceGCSweepSpan(s.npages * _PageSize)
223 atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages))
232 // The allocBits indicate which unmarked objects don't need to be
233 // processed since they were free at the end of the last GC cycle
234 // and were not allocated since then.
235 // If the allocBits index is >= s.freeindex and the bit
236 // is not marked then the object remains unallocated
237 // since the last GC.
238 // This situation is analogous to being on a freelist.
240 // Unlink & free special records for any objects we're about to free.
241 // Two complications here:
242 // 1. An object can have both finalizer and profile special records.
243 // In such case we need to queue finalizer for execution,
244 // mark the object as live and preserve the profile special.
245 // 2. A tiny object can have several finalizers setup for different offsets.
246 // If such object is not marked, we need to queue all finalizers at once.
247 // Both 1 and 2 are possible at the same time.
248 specialp := &s.specials
251 // A finalizer can be set for an inner byte of an object, find object beginning.
252 objIndex := uintptr(special.offset) / size
253 p := s.base() + objIndex*size
254 mbits := s.markBitsForIndex(objIndex)
255 if !mbits.isMarked() {
256 // This object is not marked and has at least one special record.
257 // Pass 1: see if it has at least one finalizer.
259 endOffset := p - s.base() + size
260 for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next {
261 if tmp.kind == _KindSpecialFinalizer {
262 // Stop freeing of object if it has a finalizer.
263 mbits.setMarkedNonAtomic()
268 // Pass 2: queue all finalizers _or_ handle profile record.
269 for special != nil && uintptr(special.offset) < endOffset {
270 // Find the exact byte for which the special was setup
271 // (as opposed to object beginning).
272 p := s.base() + uintptr(special.offset)
273 if special.kind == _KindSpecialFinalizer || !hasFin {
274 // Splice out special record.
276 special = special.next
278 freespecial(y, unsafe.Pointer(p), size)
280 // This is profile record, but the object has finalizers (so kept alive).
281 // Keep special record.
282 specialp = &special.next
287 // object is still live: keep special record
288 specialp = &special.next
293 if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled {
294 // Find all newly freed objects. This doesn't have to
295 // efficient; allocfreetrace has massive overhead.
296 mbits := s.markBitsForBase()
297 abits := s.allocBitsForIndex(0)
298 for i := uintptr(0); i < s.nelems; i++ {
299 if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) {
300 x := s.base() + i*s.elemsize
301 if debug.allocfreetrace != 0 {
302 tracefree(unsafe.Pointer(x), size)
304 if debug.clobberfree != 0 {
305 clobberfree(unsafe.Pointer(x), size)
308 racefree(unsafe.Pointer(x), size)
311 msanfree(unsafe.Pointer(x), size)
319 // Count the number of free objects in this span.
320 nalloc := uint16(s.countAlloc())
321 if spc.sizeclass() == 0 && nalloc == 0 {
325 nfreed := s.allocCount - nalloc
326 if nalloc > s.allocCount {
327 print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
328 throw("sweep increased allocation count")
331 s.allocCount = nalloc
332 wasempty := s.nextFreeIndex() == s.nelems
333 s.freeindex = 0 // reset allocation index to start of span.
335 getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
338 // gcmarkBits becomes the allocBits.
339 // get a fresh cleared gcmarkBits in preparation for next GC
340 s.allocBits = s.gcmarkBits
341 s.gcmarkBits = newMarkBits(s.nelems)
343 // Initialize alloc bits cache.
344 s.refillAllocCache(0)
346 // We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
347 // because of the potential for a concurrent free/SetFinalizer.
348 // But we need to set it before we make the span available for allocation
349 // (return it to heap or mcentral), because allocation code assumes that a
350 // span is already swept if available for allocation.
351 if freeToHeap || nfreed == 0 {
352 // The span must be in our exclusive ownership until we update sweepgen,
353 // check for potential races.
354 if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
355 print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
356 throw("mspan.sweep: bad span state after sweep")
358 // Serialization point.
359 // At this point the mark bits are cleared and allocation ready
360 // to go so release the span.
361 atomic.Store(&s.sweepgen, sweepgen)
364 if nfreed > 0 && spc.sizeclass() != 0 {
365 c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
366 res = mheap_.central[spc].mcentral.freeSpan(s, preserve, wasempty)
367 // mcentral.freeSpan updates sweepgen
368 } else if freeToHeap {
369 // Free large span to heap
371 // NOTE(rsc,dvyukov): The original implementation of efence
372 // in CL 22060046 used sysFree instead of sysFault, so that
373 // the operating system would eventually give the memory
374 // back to us again, so that an efence program could run
375 // longer without running out of memory. Unfortunately,
376 // calling sysFree here without any kind of adjustment of the
377 // heap data structures means that when the memory does
378 // come back to us, we have the wrong metadata for it, either in
379 // the mspan structures or in the garbage collection bitmap.
380 // Using sysFault here means that the program will run out of
381 // memory fairly quickly in efence mode, but at least it won't
382 // have mysterious crashes due to confused memory reuse.
383 // It should be possible to switch back to sysFree if we also
384 // implement and then call some kind of mheap.deleteSpan.
385 if debug.efence > 0 {
386 s.limit = 0 // prevent mlookup from finding this span
387 sysFault(unsafe.Pointer(s.base()), size)
392 c.local_largefree += size
396 // The span has been swept and is still in-use, so put
397 // it on the swept in-use list.
398 mheap_.sweepSpans[sweepgen/2%2].push(s)
403 // deductSweepCredit deducts sweep credit for allocating a span of
404 // size spanBytes. This must be performed *before* the span is
405 // allocated to ensure the system has enough credit. If necessary, it
406 // performs sweeping to prevent going in to debt. If the caller will
407 // also sweep pages (e.g., for a large allocation), it can pass a
408 // non-zero callerSweepPages to leave that many pages unswept.
410 // deductSweepCredit makes a worst-case assumption that all spanBytes
411 // bytes of the ultimately allocated span will be available for object
414 // deductSweepCredit is the core of the "proportional sweep" system.
415 // It uses statistics gathered by the garbage collector to perform
416 // enough sweeping so that all pages are swept during the concurrent
417 // sweep phase between GC cycles.
419 // mheap_ must NOT be locked.
420 func deductSweepCredit(spanBytes uintptr, callerSweepPages uintptr) {
421 if mheap_.sweepPagesPerByte == 0 {
422 // Proportional sweep is done or disabled.
431 sweptBasis := atomic.Load64(&mheap_.pagesSweptBasis)
433 // Fix debt if necessary.
434 newHeapLive := uintptr(atomic.Load64(&memstats.heap_live)-mheap_.sweepHeapLiveBasis) + spanBytes
435 pagesTarget := int64(mheap_.sweepPagesPerByte*float64(newHeapLive)) - int64(callerSweepPages)
436 for pagesTarget > int64(atomic.Load64(&mheap_.pagesSwept)-sweptBasis) {
437 if sweepone() == ^uintptr(0) {
438 mheap_.sweepPagesPerByte = 0
441 if atomic.Load64(&mheap_.pagesSweptBasis) != sweptBasis {
442 // Sweep pacing changed. Recompute debt.
452 // clobberfree sets the memory content at x to bad content, for debugging
454 func clobberfree(x unsafe.Pointer, size uintptr) {
455 // size (span.elemsize) is always a multiple of 4.
456 for i := uintptr(0); i < size; i += 4 {
457 *(*uint32)(add(x, i)) = 0xdeadbeef