src/runtime/mgcsweep.go

   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, which looks at all the mcentral lists.
  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         // centralIndex is the current unswept span class.
  45         // It represents an index into the mcentral span
  46         // sets. Accessed and updated via its load and
  47         // update methods. Not protected by a lock.
  48         //
  49         // Reset at mark termination.
  50         // Used by mheap.nextSpanForSweep.
  51         centralIndex sweepClass
  52 }
  53
  54 // sweepClass is a spanClass and one bit to represent whether we're currently
  55 // sweeping partial or full spans.
  56 type sweepClass uint32
  57
  58 const (
  59         numSweepClasses            = numSpanClasses * 2
  60         sweepClassDone  sweepClass = sweepClass(^uint32(0))
  61 )
  62
  63 func (s *sweepClass) load() sweepClass {
  64         return sweepClass(atomic.Load((*uint32)(s)))
  65 }
  66
  67 func (s *sweepClass) update(sNew sweepClass) {
  68         // Only update *s if its current value is less than sNew,
  69         // since *s increases monotonically.
  70         sOld := s.load()
  71         for sOld < sNew && !atomic.Cas((*uint32)(s), uint32(sOld), uint32(sNew)) {
  72                 sOld = s.load()
  73         }
  74         // TODO(mknyszek): This isn't the only place we have
  75         // an atomic monotonically increasing counter. It would
  76         // be nice to have an "atomic max" which is just implemented
  77         // as the above on most architectures. Some architectures
  78         // like RISC-V however have native support for an atomic max.
  79 }
  80
  81 func (s *sweepClass) clear() {
  82         atomic.Store((*uint32)(s), 0)
  83 }
  84
  85 // split returns the underlying span class as well as
  86 // whether we're interested in the full or partial
  87 // unswept lists for that class, indicated as a boolean
  88 // (true means "full").
  89 func (s sweepClass) split() (spc spanClass, full bool) {
  90         return spanClass(s >> 1), s&1 == 0
  91 }
  92
  93 // nextSpanForSweep finds and pops the next span for sweeping from the
  94 // central sweep buffers. It returns ownership of the span to the caller.
  95 // Returns nil if no such span exists.
  96 func (h *mheap) nextSpanForSweep() *mspan {
  97         sg := h.sweepgen
  98         for sc := sweep.centralIndex.load(); sc < numSweepClasses; sc++ {
  99                 spc, full := sc.split()
 100                 c := &h.central[spc].mcentral
 101                 var s *mspan
 102                 if full {
 103                         s = c.fullUnswept(sg).pop()
 104                 } else {
 105                         s = c.partialUnswept(sg).pop()
 106                 }
 107                 if s != nil {
 108                         // Write down that we found something so future sweepers
 109                         // can start from here.
 110                         sweep.centralIndex.update(sc)
 111                         return s
 112                 }
 113         }
 114         // Write down that we found nothing.
 115         sweep.centralIndex.update(sweepClassDone)
 116         return nil
 117 }
 118
 119 // finishsweep_m ensures that all spans are swept.
 120 //
 121 // The world must be stopped. This ensures there are no sweeps in
 122 // progress.
 123 //
 124 //go:nowritebarrier
 125 func finishsweep_m() {
 126         // Sweeping must be complete before marking commences, so
 127         // sweep any unswept spans. If this is a concurrent GC, there
 128         // shouldn't be any spans left to sweep, so this should finish
 129         // instantly. If GC was forced before the concurrent sweep
 130         // finished, there may be spans to sweep.
 131         for sweepone() != ^uintptr(0) {
 132                 sweep.npausesweep++
 133         }
 134
 135         if go115NewMCentralImpl {
 136                 // Reset all the unswept buffers, which should be empty.
 137                 // Do this in sweep termination as opposed to mark termination
 138                 // so that we can catch unswept spans and reclaim blocks as
 139                 // soon as possible.
 140                 sg := mheap_.sweepgen
 141                 for i := range mheap_.central {
 142                         c := &mheap_.central[i].mcentral
 143                         c.partialUnswept(sg).reset()
 144                         c.fullUnswept(sg).reset()
 145                 }
 146         }
 147
 148         // Sweeping is done, so if the scavenger isn't already awake,
 149         // wake it up. There's definitely work for it to do at this
 150         // point.
 151         wakeScavenger()
 152
 153         nextMarkBitArenaEpoch()
 154 }
 155
 156 func bgsweep(c chan int) {
 157         sweep.g = getg()
 158
 159         lockInit(&sweep.lock, lockRankSweep)
 160         lock(&sweep.lock)
 161         sweep.parked = true
 162         c <- 1
 163         goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1)
 164
 165         for {
 166                 for sweepone() != ^uintptr(0) {
 167                         sweep.nbgsweep++
 168                         Gosched()
 169                 }
 170                 for freeSomeWbufs(true) {
 171                         Gosched()
 172                 }
 173                 lock(&sweep.lock)
 174                 if !isSweepDone() {
 175                         // This can happen if a GC runs between
 176                         // gosweepone returning ^0 above
 177                         // and the lock being acquired.
 178                         unlock(&sweep.lock)
 179                         continue
 180                 }
 181                 sweep.parked = true
 182                 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1)
 183         }
 184 }
 185
 186 // sweepone sweeps some unswept heap span and returns the number of pages returned
 187 // to the heap, or ^uintptr(0) if there was nothing to sweep.
 188 func sweepone() uintptr {
 189         _g_ := getg()
 190         sweepRatio := mheap_.sweepPagesPerByte // For debugging
 191
 192         // increment locks to ensure that the goroutine is not preempted
 193         // in the middle of sweep thus leaving the span in an inconsistent state for next GC
 194         _g_.m.locks++
 195         if atomic.Load(&mheap_.sweepdone) != 0 {
 196                 _g_.m.locks--
 197                 return ^uintptr(0)
 198         }
 199         atomic.Xadd(&mheap_.sweepers, +1)
 200
 201         // Find a span to sweep.
 202         var s *mspan
 203         sg := mheap_.sweepgen
 204         for {
 205                 if go115NewMCentralImpl {
 206                         s = mheap_.nextSpanForSweep()
 207                 } else {
 208                         s = mheap_.sweepSpans[1-sg/2%2].pop()
 209                 }
 210                 if s == nil {
 211                         atomic.Store(&mheap_.sweepdone, 1)
 212                         break
 213                 }
 214                 if state := s.state.get(); state != mSpanInUse {
 215                         // This can happen if direct sweeping already
 216                         // swept this span, but in that case the sweep
 217                         // generation should always be up-to-date.
 218                         if !(s.sweepgen == sg || s.sweepgen == sg+3) {
 219                                 print("runtime: bad span s.state=", state, " s.sweepgen=", s.sweepgen, " sweepgen=", sg, "\n")
 220                                 throw("non in-use span in unswept list")
 221                         }
 222                         continue
 223                 }
 224                 if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
 225                         break
 226                 }
 227         }
 228
 229         // Sweep the span we found.
 230         npages := ^uintptr(0)
 231         if s != nil {
 232                 npages = s.npages
 233                 if s.sweep(false) {
 234                         // Whole span was freed. Count it toward the
 235                         // page reclaimer credit since these pages can
 236                         // now be used for span allocation.
 237                         atomic.Xadduintptr(&mheap_.reclaimCredit, npages)
 238                 } else {
 239                         // Span is still in-use, so this returned no
 240                         // pages to the heap and the span needs to
 241                         // move to the swept in-use list.
 242                         npages = 0
 243                 }
 244         }
 245
 246         // Decrement the number of active sweepers and if this is the
 247         // last one print trace information.
 248         if atomic.Xadd(&mheap_.sweepers, -1) == 0 && atomic.Load(&mheap_.sweepdone) != 0 {
 249                 // Since the sweeper is done, move the scavenge gen forward (signalling
 250                 // that there's new work to do) and wake the scavenger.
 251                 //
 252                 // The scavenger is signaled by the last sweeper because once
 253                 // sweeping is done, we will definitely have useful work for
 254                 // the scavenger to do, since the scavenger only runs over the
 255                 // heap once per GC cyle. This update is not done during sweep
 256                 // termination because in some cases there may be a long delay
 257                 // between sweep done and sweep termination (e.g. not enough
 258                 // allocations to trigger a GC) which would be nice to fill in
 259                 // with scavenging work.
 260                 systemstack(func() {
 261                         lock(&mheap_.lock)
 262                         mheap_.pages.scavengeStartGen()
 263                         unlock(&mheap_.lock)
 264                 })
 265                 // Since we might sweep in an allocation path, it's not possible
 266                 // for us to wake the scavenger directly via wakeScavenger, since
 267                 // it could allocate. Ask sysmon to do it for us instead.
 268                 readyForScavenger()
 269
 270                 if debug.gcpacertrace > 0 {
 271                         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")
 272                 }
 273         }
 274         _g_.m.locks--
 275         return npages
 276 }
 277
 278 // isSweepDone reports whether all spans are swept or currently being swept.
 279 //
 280 // Note that this condition may transition from false to true at any
 281 // time as the sweeper runs. It may transition from true to false if a
 282 // GC runs; to prevent that the caller must be non-preemptible or must
 283 // somehow block GC progress.
 284 func isSweepDone() bool {
 285         return mheap_.sweepdone != 0
 286 }
 287
 288 // Returns only when span s has been swept.
 289 //go:nowritebarrier
 290 func (s *mspan) ensureSwept() {
 291         // Caller must disable preemption.
 292         // Otherwise when this function returns the span can become unswept again
 293         // (if GC is triggered on another goroutine).
 294         _g_ := getg()
 295         if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
 296                 throw("mspan.ensureSwept: m is not locked")
 297         }
 298
 299         sg := mheap_.sweepgen
 300         spangen := atomic.Load(&s.sweepgen)
 301         if spangen == sg || spangen == sg+3 {
 302                 return
 303         }
 304         // The caller must be sure that the span is a mSpanInUse span.
 305         if atomic.Cas(&s.sweepgen, sg-2, sg-1) {
 306                 s.sweep(false)
 307                 return
 308         }
 309         // unfortunate condition, and we don't have efficient means to wait
 310         for {
 311                 spangen := atomic.Load(&s.sweepgen)
 312                 if spangen == sg || spangen == sg+3 {
 313                         break
 314                 }
 315                 osyield()
 316         }
 317 }
 318
 319 // Sweep frees or collects finalizers for blocks not marked in the mark phase.
 320 // It clears the mark bits in preparation for the next GC round.
 321 // Returns true if the span was returned to heap.
 322 // If preserve=true, don't return it to heap nor relink in mcentral lists;
 323 // caller takes care of it.
 324 func (s *mspan) sweep(preserve bool) bool {
 325         if !go115NewMCentralImpl {
 326                 return s.oldSweep(preserve)
 327         }
 328         // It's critical that we enter this function with preemption disabled,
 329         // GC must not start while we are in the middle of this function.
 330         _g_ := getg()
 331         if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
 332                 throw("mspan.sweep: m is not locked")
 333         }
 334         sweepgen := mheap_.sweepgen
 335         if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
 336                 print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
 337                 throw("mspan.sweep: bad span state")
 338         }
 339
 340         if trace.enabled {
 341                 traceGCSweepSpan(s.npages * _PageSize)
 342         }
 343
 344         atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages))
 345
 346         spc := s.spanclass
 347         size := s.elemsize
 348
 349         c := _g_.m.p.ptr().mcache
 350
 351         // The allocBits indicate which unmarked objects don't need to be
 352         // processed since they were free at the end of the last GC cycle
 353         // and were not allocated since then.
 354         // If the allocBits index is >= s.freeindex and the bit
 355         // is not marked then the object remains unallocated
 356         // since the last GC.
 357         // This situation is analogous to being on a freelist.
 358
 359         // Unlink & free special records for any objects we're about to free.
 360         // Two complications here:
 361         // 1. An object can have both finalizer and profile special records.
 362         //    In such case we need to queue finalizer for execution,
 363         //    mark the object as live and preserve the profile special.
 364         // 2. A tiny object can have several finalizers setup for different offsets.
 365         //    If such object is not marked, we need to queue all finalizers at once.
 366         // Both 1 and 2 are possible at the same time.
 367         hadSpecials := s.specials != nil
 368         specialp := &s.specials
 369         special := *specialp
 370         for special != nil {
 371                 // A finalizer can be set for an inner byte of an object, find object beginning.
 372                 objIndex := uintptr(special.offset) / size
 373                 p := s.base() + objIndex*size
 374                 mbits := s.markBitsForIndex(objIndex)
 375                 if !mbits.isMarked() {
 376                         // This object is not marked and has at least one special record.
 377                         // Pass 1: see if it has at least one finalizer.
 378                         hasFin := false
 379                         endOffset := p - s.base() + size
 380                         for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next {
 381                                 if tmp.kind == _KindSpecialFinalizer {
 382                                         // Stop freeing of object if it has a finalizer.
 383                                         mbits.setMarkedNonAtomic()
 384                                         hasFin = true
 385                                         break
 386                                 }
 387                         }
 388                         // Pass 2: queue all finalizers _or_ handle profile record.
 389                         for special != nil && uintptr(special.offset) < endOffset {
 390                                 // Find the exact byte for which the special was setup
 391                                 // (as opposed to object beginning).
 392                                 p := s.base() + uintptr(special.offset)
 393                                 if special.kind == _KindSpecialFinalizer || !hasFin {
 394                                         // Splice out special record.
 395                                         y := special
 396                                         special = special.next
 397                                         *specialp = special
 398                                         freespecial(y, unsafe.Pointer(p), size)
 399                                 } else {
 400                                         // This is profile record, but the object has finalizers (so kept alive).
 401                                         // Keep special record.
 402                                         specialp = &special.next
 403                                         special = *specialp
 404                                 }
 405                         }
 406                 } else {
 407                         // object is still live: keep special record
 408                         specialp = &special.next
 409                         special = *specialp
 410                 }
 411         }
 412         if hadSpecials && s.specials == nil {
 413                 spanHasNoSpecials(s)
 414         }
 415
 416         if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled {
 417                 // Find all newly freed objects. This doesn't have to
 418                 // efficient; allocfreetrace has massive overhead.
 419                 mbits := s.markBitsForBase()
 420                 abits := s.allocBitsForIndex(0)
 421                 for i := uintptr(0); i < s.nelems; i++ {
 422                         if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) {
 423                                 x := s.base() + i*s.elemsize
 424                                 if debug.allocfreetrace != 0 {
 425                                         tracefree(unsafe.Pointer(x), size)
 426                                 }
 427                                 if debug.clobberfree != 0 {
 428                                         clobberfree(unsafe.Pointer(x), size)
 429                                 }
 430                                 if raceenabled {
 431                                         racefree(unsafe.Pointer(x), size)
 432                                 }
 433                                 if msanenabled {
 434                                         msanfree(unsafe.Pointer(x), size)
 435                                 }
 436                         }
 437                         mbits.advance()
 438                         abits.advance()
 439                 }
 440         }
 441
 442         // Check for zombie objects.
 443         if s.freeindex < s.nelems {
 444                 // Everything < freeindex is allocated and hence
 445                 // cannot be zombies.
 446                 //
 447                 // Check the first bitmap byte, where we have to be
 448                 // careful with freeindex.
 449                 obj := s.freeindex
 450                 if (*s.gcmarkBits.bytep(obj / 8)&^*s.allocBits.bytep(obj / 8))>>(obj%8) != 0 {
 451                         s.reportZombies()
 452                 }
 453                 // Check remaining bytes.
 454                 for i := obj/8 + 1; i < divRoundUp(s.nelems, 8); i++ {
 455                         if *s.gcmarkBits.bytep(i)&^*s.allocBits.bytep(i) != 0 {
 456                                 s.reportZombies()
 457                         }
 458                 }
 459         }
 460
 461         // Count the number of free objects in this span.
 462         nalloc := uint16(s.countAlloc())
 463         nfreed := s.allocCount - nalloc
 464         if nalloc > s.allocCount {
 465                 // The zombie check above should have caught this in
 466                 // more detail.
 467                 print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
 468                 throw("sweep increased allocation count")
 469         }
 470
 471         s.allocCount = nalloc
 472         s.freeindex = 0 // reset allocation index to start of span.
 473         if trace.enabled {
 474                 getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
 475         }
 476
 477         // gcmarkBits becomes the allocBits.
 478         // get a fresh cleared gcmarkBits in preparation for next GC
 479         s.allocBits = s.gcmarkBits
 480         s.gcmarkBits = newMarkBits(s.nelems)
 481
 482         // Initialize alloc bits cache.
 483         s.refillAllocCache(0)
 484
 485         // The span must be in our exclusive ownership until we update sweepgen,
 486         // check for potential races.
 487         if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
 488                 print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
 489                 throw("mspan.sweep: bad span state after sweep")
 490         }
 491         if s.sweepgen == sweepgen+1 || s.sweepgen == sweepgen+3 {
 492                 throw("swept cached span")
 493         }
 494
 495         // We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
 496         // because of the potential for a concurrent free/SetFinalizer.
 497         //
 498         // But we need to set it before we make the span available for allocation
 499         // (return it to heap or mcentral), because allocation code assumes that a
 500         // span is already swept if available for allocation.
 501         //
 502         // Serialization point.
 503         // At this point the mark bits are cleared and allocation ready
 504         // to go so release the span.
 505         atomic.Store(&s.sweepgen, sweepgen)
 506
 507         if spc.sizeclass() != 0 {
 508                 // Handle spans for small objects.
 509                 if nfreed > 0 {
 510                         // Only mark the span as needing zeroing if we've freed any
 511                         // objects, because a fresh span that had been allocated into,
 512                         // wasn't totally filled, but then swept, still has all of its
 513                         // free slots zeroed.
 514                         s.needzero = 1
 515                         c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
 516                 }
 517                 if !preserve {
 518                         // The caller may not have removed this span from whatever
 519                         // unswept set its on but taken ownership of the span for
 520                         // sweeping by updating sweepgen. If this span still is in
 521                         // an unswept set, then the mcentral will pop it off the
 522                         // set, check its sweepgen, and ignore it.
 523                         if nalloc == 0 {
 524                                 // Free totally free span directly back to the heap.
 525                                 mheap_.freeSpan(s)
 526                                 return true
 527                         }
 528                         // Return span back to the right mcentral list.
 529                         if uintptr(nalloc) == s.nelems {
 530                                 mheap_.central[spc].mcentral.fullSwept(sweepgen).push(s)
 531                         } else {
 532                                 mheap_.central[spc].mcentral.partialSwept(sweepgen).push(s)
 533                         }
 534                 }
 535         } else if !preserve {
 536                 // Handle spans for large objects.
 537                 if nfreed != 0 {
 538                         // Free large object span to heap.
 539
 540                         // NOTE(rsc,dvyukov): The original implementation of efence
 541                         // in CL 22060046 used sysFree instead of sysFault, so that
 542                         // the operating system would eventually give the memory
 543                         // back to us again, so that an efence program could run
 544                         // longer without running out of memory. Unfortunately,
 545                         // calling sysFree here without any kind of adjustment of the
 546                         // heap data structures means that when the memory does
 547                         // come back to us, we have the wrong metadata for it, either in
 548                         // the mspan structures or in the garbage collection bitmap.
 549                         // Using sysFault here means that the program will run out of
 550                         // memory fairly quickly in efence mode, but at least it won't
 551                         // have mysterious crashes due to confused memory reuse.
 552                         // It should be possible to switch back to sysFree if we also
 553                         // implement and then call some kind of mheap.deleteSpan.
 554                         if debug.efence > 0 {
 555                                 s.limit = 0 // prevent mlookup from finding this span
 556                                 sysFault(unsafe.Pointer(s.base()), size)
 557                         } else {
 558                                 mheap_.freeSpan(s)
 559                         }
 560                         c.local_nlargefree++
 561                         c.local_largefree += size
 562                         return true
 563                 }
 564
 565                 // Add a large span directly onto the full+swept list.
 566                 mheap_.central[spc].mcentral.fullSwept(sweepgen).push(s)
 567         }
 568         return false
 569 }
 570
 571 // Sweep frees or collects finalizers for blocks not marked in the mark phase.
 572 // It clears the mark bits in preparation for the next GC round.
 573 // Returns true if the span was returned to heap.
 574 // If preserve=true, don't return it to heap nor relink in mcentral lists;
 575 // caller takes care of it.
 576 //
 577 // For !go115NewMCentralImpl.
 578 func (s *mspan) oldSweep(preserve bool) bool {
 579         // It's critical that we enter this function with preemption disabled,
 580         // GC must not start while we are in the middle of this function.
 581         _g_ := getg()
 582         if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
 583                 throw("mspan.sweep: m is not locked")
 584         }
 585         sweepgen := mheap_.sweepgen
 586         if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
 587                 print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
 588                 throw("mspan.sweep: bad span state")
 589         }
 590
 591         if trace.enabled {
 592                 traceGCSweepSpan(s.npages * _PageSize)
 593         }
 594
 595         atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages))
 596
 597         spc := s.spanclass
 598         size := s.elemsize
 599         res := false
 600
 601         c := _g_.m.p.ptr().mcache
 602         freeToHeap := false
 603
 604         // The allocBits indicate which unmarked objects don't need to be
 605         // processed since they were free at the end of the last GC cycle
 606         // and were not allocated since then.
 607         // If the allocBits index is >= s.freeindex and the bit
 608         // is not marked then the object remains unallocated
 609         // since the last GC.
 610         // This situation is analogous to being on a freelist.
 611
 612         // Unlink & free special records for any objects we're about to free.
 613         // Two complications here:
 614         // 1. An object can have both finalizer and profile special records.
 615         //    In such case we need to queue finalizer for execution,
 616         //    mark the object as live and preserve the profile special.
 617         // 2. A tiny object can have several finalizers setup for different offsets.
 618         //    If such object is not marked, we need to queue all finalizers at once.
 619         // Both 1 and 2 are possible at the same time.
 620         hadSpecials := s.specials != nil
 621         specialp := &s.specials
 622         special := *specialp
 623         for special != nil {
 624                 // A finalizer can be set for an inner byte of an object, find object beginning.
 625                 objIndex := uintptr(special.offset) / size
 626                 p := s.base() + objIndex*size
 627                 mbits := s.markBitsForIndex(objIndex)
 628                 if !mbits.isMarked() {
 629                         // This object is not marked and has at least one special record.
 630                         // Pass 1: see if it has at least one finalizer.
 631                         hasFin := false
 632                         endOffset := p - s.base() + size
 633                         for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next {
 634                                 if tmp.kind == _KindSpecialFinalizer {
 635                                         // Stop freeing of object if it has a finalizer.
 636                                         mbits.setMarkedNonAtomic()
 637                                         hasFin = true
 638                                         break
 639                                 }
 640                         }
 641                         // Pass 2: queue all finalizers _or_ handle profile record.
 642                         for special != nil && uintptr(special.offset) < endOffset {
 643                                 // Find the exact byte for which the special was setup
 644                                 // (as opposed to object beginning).
 645                                 p := s.base() + uintptr(special.offset)
 646                                 if special.kind == _KindSpecialFinalizer || !hasFin {
 647                                         // Splice out special record.
 648                                         y := special
 649                                         special = special.next
 650                                         *specialp = special
 651                                         freespecial(y, unsafe.Pointer(p), size)
 652                                 } else {
 653                                         // This is profile record, but the object has finalizers (so kept alive).
 654                                         // Keep special record.
 655                                         specialp = &special.next
 656                                         special = *specialp
 657                                 }
 658                         }
 659                 } else {
 660                         // object is still live: keep special record
 661                         specialp = &special.next
 662                         special = *specialp
 663                 }
 664         }
 665         if go115NewMarkrootSpans && hadSpecials && s.specials == nil {
 666                 spanHasNoSpecials(s)
 667         }
 668
 669         if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled {
 670                 // Find all newly freed objects. This doesn't have to
 671                 // efficient; allocfreetrace has massive overhead.
 672                 mbits := s.markBitsForBase()
 673                 abits := s.allocBitsForIndex(0)
 674                 for i := uintptr(0); i < s.nelems; i++ {
 675                         if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) {
 676                                 x := s.base() + i*s.elemsize
 677                                 if debug.allocfreetrace != 0 {
 678                                         tracefree(unsafe.Pointer(x), size)
 679                                 }
 680                                 if debug.clobberfree != 0 {
 681                                         clobberfree(unsafe.Pointer(x), size)
 682                                 }
 683                                 if raceenabled {
 684                                         racefree(unsafe.Pointer(x), size)
 685                                 }
 686                                 if msanenabled {
 687                                         msanfree(unsafe.Pointer(x), size)
 688                                 }
 689                         }
 690                         mbits.advance()
 691                         abits.advance()
 692                 }
 693         }
 694
 695         // Count the number of free objects in this span.
 696         nalloc := uint16(s.countAlloc())
 697         if spc.sizeclass() == 0 && nalloc == 0 {
 698                 s.needzero = 1
 699                 freeToHeap = true
 700         }
 701         nfreed := s.allocCount - nalloc
 702         if nalloc > s.allocCount {
 703                 print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
 704                 throw("sweep increased allocation count")
 705         }
 706
 707         s.allocCount = nalloc
 708         wasempty := s.nextFreeIndex() == s.nelems
 709         s.freeindex = 0 // reset allocation index to start of span.
 710         if trace.enabled {
 711                 getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
 712         }
 713
 714         // gcmarkBits becomes the allocBits.
 715         // get a fresh cleared gcmarkBits in preparation for next GC
 716         s.allocBits = s.gcmarkBits
 717         s.gcmarkBits = newMarkBits(s.nelems)
 718
 719         // Initialize alloc bits cache.
 720         s.refillAllocCache(0)
 721
 722         // We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
 723         // because of the potential for a concurrent free/SetFinalizer.
 724         // But we need to set it before we make the span available for allocation
 725         // (return it to heap or mcentral), because allocation code assumes that a
 726         // span is already swept if available for allocation.
 727         if freeToHeap || nfreed == 0 {
 728                 // The span must be in our exclusive ownership until we update sweepgen,
 729                 // check for potential races.
 730                 if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
 731                         print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
 732                         throw("mspan.sweep: bad span state after sweep")
 733                 }
 734                 // Serialization point.
 735                 // At this point the mark bits are cleared and allocation ready
 736                 // to go so release the span.
 737                 atomic.Store(&s.sweepgen, sweepgen)
 738         }
 739
 740         if nfreed > 0 && spc.sizeclass() != 0 {
 741                 c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
 742                 res = mheap_.central[spc].mcentral.freeSpan(s, preserve, wasempty)
 743                 // mcentral.freeSpan updates sweepgen
 744         } else if freeToHeap {
 745                 // Free large span to heap
 746
 747                 // NOTE(rsc,dvyukov): The original implementation of efence
 748                 // in CL 22060046 used sysFree instead of sysFault, so that
 749                 // the operating system would eventually give the memory
 750                 // back to us again, so that an efence program could run
 751                 // longer without running out of memory. Unfortunately,
 752                 // calling sysFree here without any kind of adjustment of the
 753                 // heap data structures means that when the memory does
 754                 // come back to us, we have the wrong metadata for it, either in
 755                 // the mspan structures or in the garbage collection bitmap.
 756                 // Using sysFault here means that the program will run out of
 757                 // memory fairly quickly in efence mode, but at least it won't
 758                 // have mysterious crashes due to confused memory reuse.
 759                 // It should be possible to switch back to sysFree if we also
 760                 // implement and then call some kind of mheap.deleteSpan.
 761                 if debug.efence > 0 {
 762                         s.limit = 0 // prevent mlookup from finding this span
 763                         sysFault(unsafe.Pointer(s.base()), size)
 764                 } else {
 765                         mheap_.freeSpan(s)
 766                 }
 767                 c.local_nlargefree++
 768                 c.local_largefree += size
 769                 res = true
 770         }
 771         if !res {
 772                 // The span has been swept and is still in-use, so put
 773                 // it on the swept in-use list.
 774                 mheap_.sweepSpans[sweepgen/2%2].push(s)
 775         }
 776         return res
 777 }
 778
 779 // reportZombies reports any marked but free objects in s and throws.
 780 //
 781 // This generally means one of the following:
 782 //
 783 // 1. User code converted a pointer to a uintptr and then back
 784 // unsafely, and a GC ran while the uintptr was the only reference to
 785 // an object.
 786 //
 787 // 2. User code (or a compiler bug) constructed a bad pointer that
 788 // points to a free slot, often a past-the-end pointer.
 789 //
 790 // 3. The GC two cycles ago missed a pointer and freed a live object,
 791 // but it was still live in the last cycle, so this GC cycle found a
 792 // pointer to that object and marked it.
 793 func (s *mspan) reportZombies() {
 794         printlock()
 795         print("runtime: marked free object in span ", s, ", elemsize=", s.elemsize, " freeindex=", s.freeindex, " (bad use of unsafe.Pointer? try -d=checkptr)\n")
 796         mbits := s.markBitsForBase()
 797         abits := s.allocBitsForIndex(0)
 798         for i := uintptr(0); i < s.nelems; i++ {
 799                 addr := s.base() + i*s.elemsize
 800                 print(hex(addr))
 801                 alloc := i < s.freeindex || abits.isMarked()
 802                 if alloc {
 803                         print(" alloc")
 804                 } else {
 805                         print(" free ")
 806                 }
 807                 if mbits.isMarked() {
 808                         print(" marked  ")
 809                 } else {
 810                         print(" unmarked")
 811                 }
 812                 zombie := mbits.isMarked() && !alloc
 813                 if zombie {
 814                         print(" zombie")
 815                 }
 816                 print("\n")
 817                 if zombie {
 818                         length := s.elemsize
 819                         if length > 1024 {
 820                                 length = 1024
 821                         }
 822                         hexdumpWords(addr, addr+length, nil)
 823                 }
 824                 mbits.advance()
 825                 abits.advance()
 826         }
 827         throw("found pointer to free object")
 828 }
 829
 830 // deductSweepCredit deducts sweep credit for allocating a span of
 831 // size spanBytes. This must be performed *before* the span is
 832 // allocated to ensure the system has enough credit. If necessary, it
 833 // performs sweeping to prevent going in to debt. If the caller will
 834 // also sweep pages (e.g., for a large allocation), it can pass a
 835 // non-zero callerSweepPages to leave that many pages unswept.
 836 //
 837 // deductSweepCredit makes a worst-case assumption that all spanBytes
 838 // bytes of the ultimately allocated span will be available for object
 839 // allocation.
 840 //
 841 // deductSweepCredit is the core of the "proportional sweep" system.
 842 // It uses statistics gathered by the garbage collector to perform
 843 // enough sweeping so that all pages are swept during the concurrent
 844 // sweep phase between GC cycles.
 845 //
 846 // mheap_ must NOT be locked.
 847 func deductSweepCredit(spanBytes uintptr, callerSweepPages uintptr) {
 848         if mheap_.sweepPagesPerByte == 0 {
 849                 // Proportional sweep is done or disabled.
 850                 return
 851         }
 852
 853         if trace.enabled {
 854                 traceGCSweepStart()
 855         }
 856
 857 retry:
 858         sweptBasis := atomic.Load64(&mheap_.pagesSweptBasis)
 859
 860         // Fix debt if necessary.
 861         newHeapLive := uintptr(atomic.Load64(&memstats.heap_live)-mheap_.sweepHeapLiveBasis) + spanBytes
 862         pagesTarget := int64(mheap_.sweepPagesPerByte*float64(newHeapLive)) - int64(callerSweepPages)
 863         for pagesTarget > int64(atomic.Load64(&mheap_.pagesSwept)-sweptBasis) {
 864                 if sweepone() == ^uintptr(0) {
 865                         mheap_.sweepPagesPerByte = 0
 866                         break
 867                 }
 868                 if atomic.Load64(&mheap_.pagesSweptBasis) != sweptBasis {
 869                         // Sweep pacing changed. Recompute debt.
 870                         goto retry
 871                 }
 872         }
 873
 874         if trace.enabled {
 875                 traceGCSweepDone()
 876         }
 877 }
 878
 879 // clobberfree sets the memory content at x to bad content, for debugging
 880 // purposes.
 881 func clobberfree(x unsafe.Pointer, size uintptr) {
 882         // size (span.elemsize) is always a multiple of 4.
 883         for i := uintptr(0); i < size; i += 4 {
 884                 *(*uint32)(add(x, i)) = 0xdeadbeef
 885         }
 886 }