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. 4 5// Garbage collector: sweeping 6 7// The sweeper consists of two different algorithms: 8// 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. 14// 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. 21// 22// Both algorithms ultimately call mspan.sweep, which sweeps a single 23// heap span. 24 25package runtime 26 27import ( 28 "runtime/internal/atomic" 29 "unsafe" 30) 31 32var sweep sweepdata 33 34// State of background sweep. 35type sweepdata struct { 36 lock mutex 37 g *g 38 parked bool 39 started bool 40 41 nbgsweep uint32 42 npausesweep uint32 43} 44 45// finishsweep_m ensures that all spans are swept. 46// 47// The world must be stopped. This ensures there are no sweeps in 48// progress. 49// 50//go:nowritebarrier 51func 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) { 58 sweep.npausesweep++ 59 } 60 61 nextMarkBitArenaEpoch() 62} 63 64func bgsweep(c chan int) { 65 setSystemGoroutine() 66 67 sweep.g = getg() 68 69 lock(&sweep.lock) 70 sweep.parked = true 71 c <- 1 72 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1) 73 74 for { 75 for sweepone() != ^uintptr(0) { 76 sweep.nbgsweep++ 77 Gosched() 78 } 79 for freeSomeWbufs(true) { 80 Gosched() 81 } 82 lock(&sweep.lock) 83 if !isSweepDone() { 84 // This can happen if a GC runs between 85 // gosweepone returning ^0 above 86 // and the lock being acquired. 87 unlock(&sweep.lock) 88 continue 89 } 90 sweep.parked = true 91 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1) 92 } 93} 94 95// sweepone sweeps some unswept heap span and returns the number of pages returned 96// to the heap, or ^uintptr(0) if there was nothing to sweep. 97func sweepone() uintptr { 98 _g_ := getg() 99 sweepRatio := mheap_.sweepPagesPerByte // For debugging 100 101 // increment locks to ensure that the goroutine is not preempted 102 // in the middle of sweep thus leaving the span in an inconsistent state for next GC 103 _g_.m.locks++ 104 if atomic.Load(&mheap_.sweepdone) != 0 { 105 _g_.m.locks-- 106 return ^uintptr(0) 107 } 108 atomic.Xadd(&mheap_.sweepers, +1) 109 110 // Find a span to sweep. 111 var s *mspan 112 sg := mheap_.sweepgen 113 for { 114 s = mheap_.sweepSpans[1-sg/2%2].pop() 115 if s == nil { 116 atomic.Store(&mheap_.sweepdone, 1) 117 break 118 } 119 if s.state != mSpanInUse { 120 // This can happen if direct sweeping already 121 // swept this span, but in that case the sweep 122 // generation should always be up-to-date. 123 if !(s.sweepgen == sg || s.sweepgen == sg+3) { 124 print("runtime: bad span s.state=", s.state, " s.sweepgen=", s.sweepgen, " sweepgen=", sg, "\n") 125 throw("non in-use span in unswept list") 126 } 127 continue 128 } 129 if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) { 130 break 131 } 132 } 133 134 // Sweep the span we found. 135 npages := ^uintptr(0) 136 if s != nil { 137 npages = s.npages 138 if s.sweep(false) { 139 // Whole span was freed. Count it toward the 140 // page reclaimer credit since these pages can 141 // now be used for span allocation. 142 atomic.Xadduintptr(&mheap_.reclaimCredit, npages) 143 } else { 144 // Span is still in-use, so this returned no 145 // pages to the heap and the span needs to 146 // move to the swept in-use list. 147 npages = 0 148 } 149 } 150 151 // Decrement the number of active sweepers and if this is the 152 // last one print trace information. 153 if atomic.Xadd(&mheap_.sweepers, -1) == 0 && atomic.Load(&mheap_.sweepdone) != 0 { 154 if debug.gcpacertrace > 0 { 155 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") 156 } 157 } 158 _g_.m.locks-- 159 return npages 160} 161 162// isSweepDone reports whether all spans are swept or currently being swept. 163// 164// Note that this condition may transition from false to true at any 165// time as the sweeper runs. It may transition from true to false if a 166// GC runs; to prevent that the caller must be non-preemptible or must 167// somehow block GC progress. 168func isSweepDone() bool { 169 return mheap_.sweepdone != 0 170} 171 172// Returns only when span s has been swept. 173//go:nowritebarrier 174func (s *mspan) ensureSwept() { 175 // Caller must disable preemption. 176 // Otherwise when this function returns the span can become unswept again 177 // (if GC is triggered on another goroutine). 178 _g_ := getg() 179 if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 { 180 throw("mspan.ensureSwept: m is not locked") 181 } 182 183 sg := mheap_.sweepgen 184 spangen := atomic.Load(&s.sweepgen) 185 if spangen == sg || spangen == sg+3 { 186 return 187 } 188 // The caller must be sure that the span is a mSpanInUse span. 189 if atomic.Cas(&s.sweepgen, sg-2, sg-1) { 190 s.sweep(false) 191 return 192 } 193 // unfortunate condition, and we don't have efficient means to wait 194 for { 195 spangen := atomic.Load(&s.sweepgen) 196 if spangen == sg || spangen == sg+3 { 197 break 198 } 199 osyield() 200 } 201} 202 203// Sweep frees or collects finalizers for blocks not marked in the mark phase. 204// It clears the mark bits in preparation for the next GC round. 205// Returns true if the span was returned to heap. 206// If preserve=true, don't return it to heap nor relink in mcentral lists; 207// caller takes care of it. 208//TODO go:nowritebarrier 209func (s *mspan) sweep(preserve bool) bool { 210 // It's critical that we enter this function with preemption disabled, 211 // GC must not start while we are in the middle of this function. 212 _g_ := getg() 213 if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 { 214 throw("mspan.sweep: m is not locked") 215 } 216 sweepgen := mheap_.sweepgen 217 if s.state != mSpanInUse || s.sweepgen != sweepgen-1 { 218 print("mspan.sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n") 219 throw("mspan.sweep: bad span state") 220 } 221 222 if trace.enabled { 223 traceGCSweepSpan(s.npages * _PageSize) 224 } 225 226 atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages)) 227 228 spc := s.spanclass 229 size := s.elemsize 230 res := false 231 232 c := _g_.m.mcache 233 freeToHeap := false 234 235 // The allocBits indicate which unmarked objects don't need to be 236 // processed since they were free at the end of the last GC cycle 237 // and were not allocated since then. 238 // If the allocBits index is >= s.freeindex and the bit 239 // is not marked then the object remains unallocated 240 // since the last GC. 241 // This situation is analogous to being on a freelist. 242 243 // Unlink & free special records for any objects we're about to free. 244 // Two complications here: 245 // 1. An object can have both finalizer and profile special records. 246 // In such case we need to queue finalizer for execution, 247 // mark the object as live and preserve the profile special. 248 // 2. A tiny object can have several finalizers setup for different offsets. 249 // If such object is not marked, we need to queue all finalizers at once. 250 // Both 1 and 2 are possible at the same time. 251 specialp := &s.specials 252 special := *specialp 253 for special != nil { 254 // A finalizer can be set for an inner byte of an object, find object beginning. 255 objIndex := uintptr(special.offset) / size 256 p := s.base() + objIndex*size 257 mbits := s.markBitsForIndex(objIndex) 258 if !mbits.isMarked() { 259 // This object is not marked and has at least one special record. 260 // Pass 1: see if it has at least one finalizer. 261 hasFin := false 262 endOffset := p - s.base() + size 263 for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next { 264 if tmp.kind == _KindSpecialFinalizer { 265 // Stop freeing of object if it has a finalizer. 266 mbits.setMarkedNonAtomic() 267 hasFin = true 268 break 269 } 270 } 271 // Pass 2: queue all finalizers _or_ handle profile record. 272 for special != nil && uintptr(special.offset) < endOffset { 273 // Find the exact byte for which the special was setup 274 // (as opposed to object beginning). 275 p := s.base() + uintptr(special.offset) 276 if special.kind == _KindSpecialFinalizer || !hasFin { 277 // Splice out special record. 278 y := special 279 special = special.next 280 *specialp = special 281 freespecial(y, unsafe.Pointer(p), size) 282 } else { 283 // This is profile record, but the object has finalizers (so kept alive). 284 // Keep special record. 285 specialp = &special.next 286 special = *specialp 287 } 288 } 289 } else { 290 // object is still live: keep special record 291 specialp = &special.next 292 special = *specialp 293 } 294 } 295 296 if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled { 297 // Find all newly freed objects. This doesn't have to 298 // efficient; allocfreetrace has massive overhead. 299 mbits := s.markBitsForBase() 300 abits := s.allocBitsForIndex(0) 301 for i := uintptr(0); i < s.nelems; i++ { 302 if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) { 303 x := s.base() + i*s.elemsize 304 if debug.allocfreetrace != 0 { 305 tracefree(unsafe.Pointer(x), size) 306 } 307 if debug.clobberfree != 0 { 308 clobberfree(unsafe.Pointer(x), size) 309 } 310 if raceenabled { 311 racefree(unsafe.Pointer(x), size) 312 } 313 if msanenabled { 314 msanfree(unsafe.Pointer(x), size) 315 } 316 } 317 mbits.advance() 318 abits.advance() 319 } 320 } 321 322 // Count the number of free objects in this span. 323 nalloc := uint16(s.countAlloc()) 324 if spc.sizeclass() == 0 && nalloc == 0 { 325 s.needzero = 1 326 freeToHeap = true 327 } 328 nfreed := s.allocCount - nalloc 329 330 // This check is not reliable with gccgo, because of 331 // conservative stack scanning. The test boils down to 332 // checking that no new bits have been set in gcmarkBits since 333 // the span was added to the sweep count. New bits are set by 334 // greyobject. Seeing a new bit means that a live pointer has 335 // appeared that was not found during the mark phase. That can 336 // not happen when pointers are followed strictly. However, 337 // with conservative checking, it is possible for a pointer 338 // that will never be used to appear live and to cause a mark 339 // to be added. That is unfortunate in that it causes this 340 // check to be inaccurate, and it will keep an object live 341 // unnecessarily, but provided the pointer is not really live 342 // it is not otherwise a problem. So we disable the test for gccgo. 343 nfreedSigned := int(nfreed) 344 if nalloc > s.allocCount { 345 if usestackmaps { 346 print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n") 347 throw("sweep increased allocation count") 348 } 349 350 // For gccgo, adjust the freed count as a signed number. 351 nfreedSigned = int(s.allocCount) - int(nalloc) 352 if uintptr(nalloc) == s.nelems { 353 s.freeindex = s.nelems 354 } 355 } 356 357 s.allocCount = nalloc 358 wasempty := s.nextFreeIndex() == s.nelems 359 s.freeindex = 0 // reset allocation index to start of span. 360 if trace.enabled { 361 getg().m.p.ptr().traceReclaimed += uintptr(nfreedSigned) * s.elemsize 362 } 363 364 // gcmarkBits becomes the allocBits. 365 // get a fresh cleared gcmarkBits in preparation for next GC 366 s.allocBits = s.gcmarkBits 367 s.gcmarkBits = newMarkBits(s.nelems) 368 369 // Initialize alloc bits cache. 370 s.refillAllocCache(0) 371 372 // We need to set s.sweepgen = h.sweepgen only when all blocks are swept, 373 // because of the potential for a concurrent free/SetFinalizer. 374 // But we need to set it before we make the span available for allocation 375 // (return it to heap or mcentral), because allocation code assumes that a 376 // span is already swept if available for allocation. 377 if freeToHeap || nfreedSigned <= 0 { 378 // The span must be in our exclusive ownership until we update sweepgen, 379 // check for potential races. 380 if s.state != mSpanInUse || s.sweepgen != sweepgen-1 { 381 print("mspan.sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n") 382 throw("mspan.sweep: bad span state after sweep") 383 } 384 // Serialization point. 385 // At this point the mark bits are cleared and allocation ready 386 // to go so release the span. 387 atomic.Store(&s.sweepgen, sweepgen) 388 } 389 390 if spc.sizeclass() != 0 { 391 c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreedSigned) 392 } 393 394 if nfreedSigned > 0 && spc.sizeclass() != 0 { 395 res = mheap_.central[spc].mcentral.freeSpan(s, preserve, wasempty) 396 // mcentral.freeSpan updates sweepgen 397 } else if freeToHeap { 398 // Free large span to heap 399 400 // NOTE(rsc,dvyukov): The original implementation of efence 401 // in CL 22060046 used sysFree instead of sysFault, so that 402 // the operating system would eventually give the memory 403 // back to us again, so that an efence program could run 404 // longer without running out of memory. Unfortunately, 405 // calling sysFree here without any kind of adjustment of the 406 // heap data structures means that when the memory does 407 // come back to us, we have the wrong metadata for it, either in 408 // the mspan structures or in the garbage collection bitmap. 409 // Using sysFault here means that the program will run out of 410 // memory fairly quickly in efence mode, but at least it won't 411 // have mysterious crashes due to confused memory reuse. 412 // It should be possible to switch back to sysFree if we also 413 // implement and then call some kind of mheap.deleteSpan. 414 if debug.efence > 0 { 415 s.limit = 0 // prevent mlookup from finding this span 416 sysFault(unsafe.Pointer(s.base()), size) 417 } else { 418 mheap_.freeSpan(s, true) 419 } 420 c.local_nlargefree++ 421 c.local_largefree += size 422 res = true 423 } 424 if !res { 425 // The span has been swept and is still in-use, so put 426 // it on the swept in-use list. 427 mheap_.sweepSpans[sweepgen/2%2].push(s) 428 } 429 return res 430} 431 432// deductSweepCredit deducts sweep credit for allocating a span of 433// size spanBytes. This must be performed *before* the span is 434// allocated to ensure the system has enough credit. If necessary, it 435// performs sweeping to prevent going in to debt. If the caller will 436// also sweep pages (e.g., for a large allocation), it can pass a 437// non-zero callerSweepPages to leave that many pages unswept. 438// 439// deductSweepCredit makes a worst-case assumption that all spanBytes 440// bytes of the ultimately allocated span will be available for object 441// allocation. 442// 443// deductSweepCredit is the core of the "proportional sweep" system. 444// It uses statistics gathered by the garbage collector to perform 445// enough sweeping so that all pages are swept during the concurrent 446// sweep phase between GC cycles. 447// 448// mheap_ must NOT be locked. 449func deductSweepCredit(spanBytes uintptr, callerSweepPages uintptr) { 450 if mheap_.sweepPagesPerByte == 0 { 451 // Proportional sweep is done or disabled. 452 return 453 } 454 455 if trace.enabled { 456 traceGCSweepStart() 457 } 458 459retry: 460 sweptBasis := atomic.Load64(&mheap_.pagesSweptBasis) 461 462 // Fix debt if necessary. 463 newHeapLive := uintptr(atomic.Load64(&memstats.heap_live)-mheap_.sweepHeapLiveBasis) + spanBytes 464 pagesTarget := int64(mheap_.sweepPagesPerByte*float64(newHeapLive)) - int64(callerSweepPages) 465 for pagesTarget > int64(atomic.Load64(&mheap_.pagesSwept)-sweptBasis) { 466 if sweepone() == ^uintptr(0) { 467 mheap_.sweepPagesPerByte = 0 468 break 469 } 470 if atomic.Load64(&mheap_.pagesSweptBasis) != sweptBasis { 471 // Sweep pacing changed. Recompute debt. 472 goto retry 473 } 474 } 475 476 if trace.enabled { 477 traceGCSweepDone() 478 } 479} 480 481// clobberfree sets the memory content at x to bad content, for debugging 482// purposes. 483func clobberfree(x unsafe.Pointer, size uintptr) { 484 // size (span.elemsize) is always a multiple of 4. 485 for i := uintptr(0); i < size; i += 4 { 486 *(*uint32)(add(x, i)) = 0xdeadbeef 487 } 488} 489