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 25 package runtime 26 27 import ( 28 "runtime/internal/atomic" 29 "unsafe" 30 ) 31 32 var sweep sweepdata 33 34 // State of background sweep. 35 type 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 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) { 58 sweep.npausesweep++ 59 } 60 61 nextMarkBitArenaEpoch() 62 } 63 64 func bgsweep(c chan int) { 65 sweep.g = getg() 66 67 lock(&sweep.lock) 68 sweep.parked = true 69 c <- 1 70 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1) 71 72 for { 73 for sweepone() != ^uintptr(0) { 74 sweep.nbgsweep++ 75 Gosched() 76 } 77 for freeSomeWbufs(true) { 78 Gosched() 79 } 80 lock(&sweep.lock) 81 if !isSweepDone() { 82 // This can happen if a GC runs between 83 // gosweepone returning ^0 above 84 // and the lock being acquired. 85 unlock(&sweep.lock) 86 continue 87 } 88 sweep.parked = true 89 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1) 90 } 91 } 92 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 { 96 _g_ := getg() 97 sweepRatio := mheap_.sweepPagesPerByte // For debugging 98 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 101 _g_.m.locks++ 102 if atomic.Load(&mheap_.sweepdone) != 0 { 103 _g_.m.locks-- 104 return ^uintptr(0) 105 } 106 atomic.Xadd(&mheap_.sweepers, +1) 107 108 // Find a span to sweep. 109 var s *mspan 110 sg := mheap_.sweepgen 111 for { 112 s = mheap_.sweepSpans[1-sg/2%2].pop() 113 if s == nil { 114 atomic.Store(&mheap_.sweepdone, 1) 115 break 116 } 117 if s.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=", s.state, " s.sweepgen=", s.sweepgen, " sweepgen=", sg, "\n") 123 throw("non in-use span in unswept list") 124 } 125 continue 126 } 127 if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) { 128 break 129 } 130 } 131 132 // Sweep the span we found. 133 npages := ^uintptr(0) 134 if s != nil { 135 npages = s.npages 136 if s.sweep(false) { 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) 141 } else { 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. 145 npages = 0 146 } 147 } 148 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") 154 } 155 } 156 _g_.m.locks-- 157 return npages 158 } 159 160 // isSweepDone reports whether all spans are swept or currently being swept. 161 // 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 168 } 169 170 // Returns only when span s has been swept. 171 //go:nowritebarrier 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). 176 _g_ := getg() 177 if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 { 178 throw("mspan.ensureSwept: m is not locked") 179 } 180 181 sg := mheap_.sweepgen 182 spangen := atomic.Load(&s.sweepgen) 183 if spangen == sg || spangen == sg+3 { 184 return 185 } 186 // The caller must be sure that the span is a mSpanInUse span. 187 if atomic.Cas(&s.sweepgen, sg-2, sg-1) { 188 s.sweep(false) 189 return 190 } 191 // unfortunate condition, and we don't have efficient means to wait 192 for { 193 spangen := atomic.Load(&s.sweepgen) 194 if spangen == sg || spangen == sg+3 { 195 break 196 } 197 osyield() 198 } 199 } 200 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. 209 _g_ := getg() 210 if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 { 211 throw("mspan.sweep: m is not locked") 212 } 213 sweepgen := mheap_.sweepgen 214 if s.state != mSpanInUse || s.sweepgen != sweepgen-1 { 215 print("mspan.sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n") 216 throw("mspan.sweep: bad span state") 217 } 218 219 if trace.enabled { 220 traceGCSweepSpan(s.npages * _PageSize) 221 } 222 223 atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages)) 224 225 spc := s.spanclass 226 size := s.elemsize 227 res := false 228 229 c := _g_.m.mcache 230 freeToHeap := false 231 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. 239 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 249 special := *specialp 250 for special != nil { 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. 258 hasFin := false 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() 264 hasFin = true 265 break 266 } 267 } 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. 275 y := special 276 special = special.next 277 *specialp = special 278 freespecial(y, unsafe.Pointer(p), size) 279 } else { 280 // This is profile record, but the object has finalizers (so kept alive). 281 // Keep special record. 282 specialp = &special.next 283 special = *specialp 284 } 285 } 286 } else { 287 // object is still live: keep special record 288 specialp = &special.next 289 special = *specialp 290 } 291 } 292 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) 303 } 304 if debug.clobberfree != 0 { 305 clobberfree(unsafe.Pointer(x), size) 306 } 307 if raceenabled { 308 racefree(unsafe.Pointer(x), size) 309 } 310 if msanenabled { 311 msanfree(unsafe.Pointer(x), size) 312 } 313 } 314 mbits.advance() 315 abits.advance() 316 } 317 } 318 319 // Count the number of free objects in this span. 320 nalloc := uint16(s.countAlloc()) 321 if spc.sizeclass() == 0 && nalloc == 0 { 322 s.needzero = 1 323 freeToHeap = true 324 } 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") 329 } 330 331 s.allocCount = nalloc 332 wasempty := s.nextFreeIndex() == s.nelems 333 s.freeindex = 0 // reset allocation index to start of span. 334 if trace.enabled { 335 getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize 336 } 337 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) 342 343 // Initialize alloc bits cache. 344 s.refillAllocCache(0) 345 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 s.state != mSpanInUse || s.sweepgen != sweepgen-1 { 355 print("mspan.sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n") 356 throw("mspan.sweep: bad span state after sweep") 357 } 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) 362 } 363 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 370 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) 388 } else { 389 mheap_.freeSpan(s, true) 390 } 391 c.local_nlargefree++ 392 c.local_largefree += size 393 res = true 394 } 395 if !res { 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) 399 } 400 return res 401 } 402 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. 409 // 410 // deductSweepCredit makes a worst-case assumption that all spanBytes 411 // bytes of the ultimately allocated span will be available for object 412 // allocation. 413 // 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. 418 // 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. 423 return 424 } 425 426 if trace.enabled { 427 traceGCSweepStart() 428 } 429 430 retry: 431 sweptBasis := atomic.Load64(&mheap_.pagesSweptBasis) 432 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 439 break 440 } 441 if atomic.Load64(&mheap_.pagesSweptBasis) != sweptBasis { 442 // Sweep pacing changed. Recompute debt. 443 goto retry 444 } 445 } 446 447 if trace.enabled { 448 traceGCSweepDone() 449 } 450 } 451 452 // clobberfree sets the memory content at x to bad content, for debugging 453 // purposes. 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 458 } 459 } 460
View as plain text