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, reset the scavenger's pointer
 250                 // into the heap and wake it if necessary.
 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.resetScavengeAddr()
 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         // Count the number of free objects in this span.
 443         nalloc := uint16(s.countAlloc())
 444         nfreed := s.allocCount - nalloc
 445         if nalloc > s.allocCount {
 446                 print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
 447                 throw("sweep increased allocation count")
 448         }
 449
 450         s.allocCount = nalloc
 451         s.freeindex = 0 // reset allocation index to start of span.
 452         if trace.enabled {
 453                 getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
 454         }
 455
 456         // gcmarkBits becomes the allocBits.
 457         // get a fresh cleared gcmarkBits in preparation for next GC
 458         s.allocBits = s.gcmarkBits
 459         s.gcmarkBits = newMarkBits(s.nelems)
 460
 461         // Initialize alloc bits cache.
 462         s.refillAllocCache(0)
 463
 464         // The span must be in our exclusive ownership until we update sweepgen,
 465         // check for potential races.
 466         if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
 467                 print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
 468                 throw("mspan.sweep: bad span state after sweep")
 469         }
 470         if s.sweepgen == sweepgen+1 || s.sweepgen == sweepgen+3 {
 471                 throw("swept cached span")
 472         }
 473
 474         // We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
 475         // because of the potential for a concurrent free/SetFinalizer.
 476         //
 477         // But we need to set it before we make the span available for allocation
 478         // (return it to heap or mcentral), because allocation code assumes that a
 479         // span is already swept if available for allocation.
 480         //
 481         // Serialization point.
 482         // At this point the mark bits are cleared and allocation ready
 483         // to go so release the span.
 484         atomic.Store(&s.sweepgen, sweepgen)
 485
 486         if spc.sizeclass() != 0 {
 487                 // Handle spans for small objects.
 488                 if nfreed > 0 {
 489                         // Only mark the span as needing zeroing if we've freed any
 490                         // objects, because a fresh span that had been allocated into,
 491                         // wasn't totally filled, but then swept, still has all of its
 492                         // free slots zeroed.
 493                         s.needzero = 1
 494                         c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
 495                 }
 496                 if !preserve {
 497                         // The caller may not have removed this span from whatever
 498                         // unswept set its on but taken ownership of the span for
 499                         // sweeping by updating sweepgen. If this span still is in
 500                         // an unswept set, then the mcentral will pop it off the
 501                         // set, check its sweepgen, and ignore it.
 502                         if nalloc == 0 {
 503                                 // Free totally free span directly back to the heap.
 504                                 mheap_.freeSpan(s)
 505                                 return true
 506                         }
 507                         // Return span back to the right mcentral list.
 508                         if uintptr(nalloc) == s.nelems {
 509                                 mheap_.central[spc].mcentral.fullSwept(sweepgen).push(s)
 510                         } else {
 511                                 mheap_.central[spc].mcentral.partialSwept(sweepgen).push(s)
 512                         }
 513                 }
 514         } else if !preserve {
 515                 // Handle spans for large objects.
 516                 if nfreed != 0 {
 517                         // Free large object span to heap.
 518
 519                         // NOTE(rsc,dvyukov): The original implementation of efence
 520                         // in CL 22060046 used sysFree instead of sysFault, so that
 521                         // the operating system would eventually give the memory
 522                         // back to us again, so that an efence program could run
 523                         // longer without running out of memory. Unfortunately,
 524                         // calling sysFree here without any kind of adjustment of the
 525                         // heap data structures means that when the memory does
 526                         // come back to us, we have the wrong metadata for it, either in
 527                         // the mspan structures or in the garbage collection bitmap.
 528                         // Using sysFault here means that the program will run out of
 529                         // memory fairly quickly in efence mode, but at least it won't
 530                         // have mysterious crashes due to confused memory reuse.
 531                         // It should be possible to switch back to sysFree if we also
 532                         // implement and then call some kind of mheap.deleteSpan.
 533                         if debug.efence > 0 {
 534                                 s.limit = 0 // prevent mlookup from finding this span
 535                                 sysFault(unsafe.Pointer(s.base()), size)
 536                         } else {
 537                                 mheap_.freeSpan(s)
 538                         }
 539                         c.local_nlargefree++
 540                         c.local_largefree += size
 541                         return true
 542                 }
 543
 544                 // Add a large span directly onto the full+swept list.
 545                 mheap_.central[spc].mcentral.fullSwept(sweepgen).push(s)
 546         }
 547         return false
 548 }
 549
 550 // Sweep frees or collects finalizers for blocks not marked in the mark phase.
 551 // It clears the mark bits in preparation for the next GC round.
 552 // Returns true if the span was returned to heap.
 553 // If preserve=true, don't return it to heap nor relink in mcentral lists;
 554 // caller takes care of it.
 555 //
 556 // For !go115NewMCentralImpl.
 557 func (s *mspan) oldSweep(preserve bool) bool {
 558         // It's critical that we enter this function with preemption disabled,
 559         // GC must not start while we are in the middle of this function.
 560         _g_ := getg()
 561         if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
 562                 throw("mspan.sweep: m is not locked")
 563         }
 564         sweepgen := mheap_.sweepgen
 565         if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
 566                 print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
 567                 throw("mspan.sweep: bad span state")
 568         }
 569
 570         if trace.enabled {
 571                 traceGCSweepSpan(s.npages * _PageSize)
 572         }
 573
 574         atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages))
 575
 576         spc := s.spanclass
 577         size := s.elemsize
 578         res := false
 579
 580         c := _g_.m.p.ptr().mcache
 581         freeToHeap := false
 582
 583         // The allocBits indicate which unmarked objects don't need to be
 584         // processed since they were free at the end of the last GC cycle
 585         // and were not allocated since then.
 586         // If the allocBits index is >= s.freeindex and the bit
 587         // is not marked then the object remains unallocated
 588         // since the last GC.
 589         // This situation is analogous to being on a freelist.
 590
 591         // Unlink & free special records for any objects we're about to free.
 592         // Two complications here:
 593         // 1. An object can have both finalizer and profile special records.
 594         //    In such case we need to queue finalizer for execution,
 595         //    mark the object as live and preserve the profile special.
 596         // 2. A tiny object can have several finalizers setup for different offsets.
 597         //    If such object is not marked, we need to queue all finalizers at once.
 598         // Both 1 and 2 are possible at the same time.
 599         hadSpecials := s.specials != nil
 600         specialp := &s.specials
 601         special := *specialp
 602         for special != nil {
 603                 // A finalizer can be set for an inner byte of an object, find object beginning.
 604                 objIndex := uintptr(special.offset) / size
 605                 p := s.base() + objIndex*size
 606                 mbits := s.markBitsForIndex(objIndex)
 607                 if !mbits.isMarked() {
 608                         // This object is not marked and has at least one special record.
 609                         // Pass 1: see if it has at least one finalizer.
 610                         hasFin := false
 611                         endOffset := p - s.base() + size
 612                         for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next {
 613                                 if tmp.kind == _KindSpecialFinalizer {
 614                                         // Stop freeing of object if it has a finalizer.
 615                                         mbits.setMarkedNonAtomic()
 616                                         hasFin = true
 617                                         break
 618                                 }
 619                         }
 620                         // Pass 2: queue all finalizers _or_ handle profile record.
 621                         for special != nil && uintptr(special.offset) < endOffset {
 622                                 // Find the exact byte for which the special was setup
 623                                 // (as opposed to object beginning).
 624                                 p := s.base() + uintptr(special.offset)
 625                                 if special.kind == _KindSpecialFinalizer || !hasFin {
 626                                         // Splice out special record.
 627                                         y := special
 628                                         special = special.next
 629                                         *specialp = special
 630                                         freespecial(y, unsafe.Pointer(p), size)
 631                                 } else {
 632                                         // This is profile record, but the object has finalizers (so kept alive).
 633                                         // Keep special record.
 634                                         specialp = &special.next
 635                                         special = *specialp
 636                                 }
 637                         }
 638                 } else {
 639                         // object is still live: keep special record
 640                         specialp = &special.next
 641                         special = *specialp
 642                 }
 643         }
 644         if go115NewMarkrootSpans && hadSpecials && s.specials == nil {
 645                 spanHasNoSpecials(s)
 646         }
 647
 648         if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled {
 649                 // Find all newly freed objects. This doesn't have to
 650                 // efficient; allocfreetrace has massive overhead.
 651                 mbits := s.markBitsForBase()
 652                 abits := s.allocBitsForIndex(0)
 653                 for i := uintptr(0); i < s.nelems; i++ {
 654                         if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) {
 655                                 x := s.base() + i*s.elemsize
 656                                 if debug.allocfreetrace != 0 {
 657                                         tracefree(unsafe.Pointer(x), size)
 658                                 }
 659                                 if debug.clobberfree != 0 {
 660                                         clobberfree(unsafe.Pointer(x), size)
 661                                 }
 662                                 if raceenabled {
 663                                         racefree(unsafe.Pointer(x), size)
 664                                 }
 665                                 if msanenabled {
 666                                         msanfree(unsafe.Pointer(x), size)
 667                                 }
 668                         }
 669                         mbits.advance()
 670                         abits.advance()
 671                 }
 672         }
 673
 674         // Count the number of free objects in this span.
 675         nalloc := uint16(s.countAlloc())
 676         if spc.sizeclass() == 0 && nalloc == 0 {
 677                 s.needzero = 1
 678                 freeToHeap = true
 679         }
 680         nfreed := s.allocCount - nalloc
 681         if nalloc > s.allocCount {
 682                 print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
 683                 throw("sweep increased allocation count")
 684         }
 685
 686         s.allocCount = nalloc
 687         wasempty := s.nextFreeIndex() == s.nelems
 688         s.freeindex = 0 // reset allocation index to start of span.
 689         if trace.enabled {
 690                 getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
 691         }
 692
 693         // gcmarkBits becomes the allocBits.
 694         // get a fresh cleared gcmarkBits in preparation for next GC
 695         s.allocBits = s.gcmarkBits
 696         s.gcmarkBits = newMarkBits(s.nelems)
 697
 698         // Initialize alloc bits cache.
 699         s.refillAllocCache(0)
 700
 701         // We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
 702         // because of the potential for a concurrent free/SetFinalizer.
 703         // But we need to set it before we make the span available for allocation
 704         // (return it to heap or mcentral), because allocation code assumes that a
 705         // span is already swept if available for allocation.
 706         if freeToHeap || nfreed == 0 {
 707                 // The span must be in our exclusive ownership until we update sweepgen,
 708                 // check for potential races.
 709                 if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
 710                         print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
 711                         throw("mspan.sweep: bad span state after sweep")
 712                 }
 713                 // Serialization point.
 714                 // At this point the mark bits are cleared and allocation ready
 715                 // to go so release the span.
 716                 atomic.Store(&s.sweepgen, sweepgen)
 717         }
 718
 719         if nfreed > 0 && spc.sizeclass() != 0 {
 720                 c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
 721                 res = mheap_.central[spc].mcentral.freeSpan(s, preserve, wasempty)
 722                 // mcentral.freeSpan updates sweepgen
 723         } else if freeToHeap {
 724                 // Free large span to heap
 725
 726                 // NOTE(rsc,dvyukov): The original implementation of efence
 727                 // in CL 22060046 used sysFree instead of sysFault, so that
 728                 // the operating system would eventually give the memory
 729                 // back to us again, so that an efence program could run
 730                 // longer without running out of memory. Unfortunately,
 731                 // calling sysFree here without any kind of adjustment of the
 732                 // heap data structures means that when the memory does
 733                 // come back to us, we have the wrong metadata for it, either in
 734                 // the mspan structures or in the garbage collection bitmap.
 735                 // Using sysFault here means that the program will run out of
 736                 // memory fairly quickly in efence mode, but at least it won't
 737                 // have mysterious crashes due to confused memory reuse.
 738                 // It should be possible to switch back to sysFree if we also
 739                 // implement and then call some kind of mheap.deleteSpan.
 740                 if debug.efence > 0 {
 741                         s.limit = 0 // prevent mlookup from finding this span
 742                         sysFault(unsafe.Pointer(s.base()), size)
 743                 } else {
 744                         mheap_.freeSpan(s)
 745                 }
 746                 c.local_nlargefree++
 747                 c.local_largefree += size
 748                 res = true
 749         }
 750         if !res {
 751                 // The span has been swept and is still in-use, so put
 752                 // it on the swept in-use list.
 753                 mheap_.sweepSpans[sweepgen/2%2].push(s)
 754         }
 755         return res
 756 }
 757
 758 // deductSweepCredit deducts sweep credit for allocating a span of
 759 // size spanBytes. This must be performed *before* the span is
 760 // allocated to ensure the system has enough credit. If necessary, it
 761 // performs sweeping to prevent going in to debt. If the caller will
 762 // also sweep pages (e.g., for a large allocation), it can pass a
 763 // non-zero callerSweepPages to leave that many pages unswept.
 764 //
 765 // deductSweepCredit makes a worst-case assumption that all spanBytes
 766 // bytes of the ultimately allocated span will be available for object
 767 // allocation.
 768 //
 769 // deductSweepCredit is the core of the "proportional sweep" system.
 770 // It uses statistics gathered by the garbage collector to perform
 771 // enough sweeping so that all pages are swept during the concurrent
 772 // sweep phase between GC cycles.
 773 //
 774 // mheap_ must NOT be locked.
 775 func deductSweepCredit(spanBytes uintptr, callerSweepPages uintptr) {
 776         if mheap_.sweepPagesPerByte == 0 {
 777                 // Proportional sweep is done or disabled.
 778                 return
 779         }
 780
 781         if trace.enabled {
 782                 traceGCSweepStart()
 783         }
 784
 785 retry:
 786         sweptBasis := atomic.Load64(&mheap_.pagesSweptBasis)
 787
 788         // Fix debt if necessary.
 789         newHeapLive := uintptr(atomic.Load64(&memstats.heap_live)-mheap_.sweepHeapLiveBasis) + spanBytes
 790         pagesTarget := int64(mheap_.sweepPagesPerByte*float64(newHeapLive)) - int64(callerSweepPages)
 791         for pagesTarget > int64(atomic.Load64(&mheap_.pagesSwept)-sweptBasis) {
 792                 if sweepone() == ^uintptr(0) {
 793                         mheap_.sweepPagesPerByte = 0
 794                         break
 795                 }
 796                 if atomic.Load64(&mheap_.pagesSweptBasis) != sweptBasis {
 797                         // Sweep pacing changed. Recompute debt.
 798                         goto retry
 799                 }
 800         }
 801
 802         if trace.enabled {
 803                 traceGCSweepDone()
 804         }
 805 }
 806
 807 // clobberfree sets the memory content at x to bad content, for debugging
 808 // purposes.
 809 func clobberfree(x unsafe.Pointer, size uintptr) {
 810         // size (span.elemsize) is always a multiple of 4.
 811         for i := uintptr(0); i < size; i += 4 {
 812                 *(*uint32)(add(x, i)) = 0xdeadbeef
 813         }
 814 }