Source file src/runtime/mheap.go

Documentation: runtime

     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  // Page heap.
     6  //
     7  // See malloc.go for overview.
     8  
     9  package runtime
    10  
    11  import (
    12  	"internal/cpu"
    13  	"runtime/internal/atomic"
    14  	"runtime/internal/sys"
    15  	"unsafe"
    16  )
    17  
    18  // minPhysPageSize is a lower-bound on the physical page size. The
    19  // true physical page size may be larger than this. In contrast,
    20  // sys.PhysPageSize is an upper-bound on the physical page size.
    21  const minPhysPageSize = 4096
    22  
    23  // Main malloc heap.
    24  // The heap itself is the "free" and "scav" treaps,
    25  // but all the other global data is here too.
    26  //
    27  // mheap must not be heap-allocated because it contains mSpanLists,
    28  // which must not be heap-allocated.
    29  //
    30  //go:notinheap
    31  type mheap struct {
    32  	// lock must only be acquired on the system stack, otherwise a g
    33  	// could self-deadlock if its stack grows with the lock held.
    34  	lock      mutex
    35  	free      mTreap // free spans
    36  	sweepgen  uint32 // sweep generation, see comment in mspan
    37  	sweepdone uint32 // all spans are swept
    38  	sweepers  uint32 // number of active sweepone calls
    39  
    40  	// allspans is a slice of all mspans ever created. Each mspan
    41  	// appears exactly once.
    42  	//
    43  	// The memory for allspans is manually managed and can be
    44  	// reallocated and move as the heap grows.
    45  	//
    46  	// In general, allspans is protected by mheap_.lock, which
    47  	// prevents concurrent access as well as freeing the backing
    48  	// store. Accesses during STW might not hold the lock, but
    49  	// must ensure that allocation cannot happen around the
    50  	// access (since that may free the backing store).
    51  	allspans []*mspan // all spans out there
    52  
    53  	// sweepSpans contains two mspan stacks: one of swept in-use
    54  	// spans, and one of unswept in-use spans. These two trade
    55  	// roles on each GC cycle. Since the sweepgen increases by 2
    56  	// on each cycle, this means the swept spans are in
    57  	// sweepSpans[sweepgen/2%2] and the unswept spans are in
    58  	// sweepSpans[1-sweepgen/2%2]. Sweeping pops spans from the
    59  	// unswept stack and pushes spans that are still in-use on the
    60  	// swept stack. Likewise, allocating an in-use span pushes it
    61  	// on the swept stack.
    62  	sweepSpans [2]gcSweepBuf
    63  
    64  	_ uint32 // align uint64 fields on 32-bit for atomics
    65  
    66  	// Proportional sweep
    67  	//
    68  	// These parameters represent a linear function from heap_live
    69  	// to page sweep count. The proportional sweep system works to
    70  	// stay in the black by keeping the current page sweep count
    71  	// above this line at the current heap_live.
    72  	//
    73  	// The line has slope sweepPagesPerByte and passes through a
    74  	// basis point at (sweepHeapLiveBasis, pagesSweptBasis). At
    75  	// any given time, the system is at (memstats.heap_live,
    76  	// pagesSwept) in this space.
    77  	//
    78  	// It's important that the line pass through a point we
    79  	// control rather than simply starting at a (0,0) origin
    80  	// because that lets us adjust sweep pacing at any time while
    81  	// accounting for current progress. If we could only adjust
    82  	// the slope, it would create a discontinuity in debt if any
    83  	// progress has already been made.
    84  	pagesInUse         uint64  // pages of spans in stats mSpanInUse; R/W with mheap.lock
    85  	pagesSwept         uint64  // pages swept this cycle; updated atomically
    86  	pagesSweptBasis    uint64  // pagesSwept to use as the origin of the sweep ratio; updated atomically
    87  	sweepHeapLiveBasis uint64  // value of heap_live to use as the origin of sweep ratio; written with lock, read without
    88  	sweepPagesPerByte  float64 // proportional sweep ratio; written with lock, read without
    89  	// TODO(austin): pagesInUse should be a uintptr, but the 386
    90  	// compiler can't 8-byte align fields.
    91  
    92  	// Scavenger pacing parameters
    93  	//
    94  	// The two basis parameters and the scavenge ratio parallel the proportional
    95  	// sweeping implementation, the primary differences being that:
    96  	//  * Scavenging concerns itself with RSS, estimated as heapRetained()
    97  	//  * Rather than pacing the scavenger to the GC, it is paced to a
    98  	//    time-based rate computed in gcPaceScavenger.
    99  	//
   100  	// scavengeRetainedGoal represents our goal RSS.
   101  	//
   102  	// All fields must be accessed with lock.
   103  	//
   104  	// TODO(mknyszek): Consider abstracting the basis fields and the scavenge ratio
   105  	// into its own type so that this logic may be shared with proportional sweeping.
   106  	scavengeTimeBasis     int64
   107  	scavengeRetainedBasis uint64
   108  	scavengeBytesPerNS    float64
   109  	scavengeRetainedGoal  uint64
   110  
   111  	// Page reclaimer state
   112  
   113  	// reclaimIndex is the page index in allArenas of next page to
   114  	// reclaim. Specifically, it refers to page (i %
   115  	// pagesPerArena) of arena allArenas[i / pagesPerArena].
   116  	//
   117  	// If this is >= 1<<63, the page reclaimer is done scanning
   118  	// the page marks.
   119  	//
   120  	// This is accessed atomically.
   121  	reclaimIndex uint64
   122  	// reclaimCredit is spare credit for extra pages swept. Since
   123  	// the page reclaimer works in large chunks, it may reclaim
   124  	// more than requested. Any spare pages released go to this
   125  	// credit pool.
   126  	//
   127  	// This is accessed atomically.
   128  	reclaimCredit uintptr
   129  
   130  	// Malloc stats.
   131  	largealloc  uint64                  // bytes allocated for large objects
   132  	nlargealloc uint64                  // number of large object allocations
   133  	largefree   uint64                  // bytes freed for large objects (>maxsmallsize)
   134  	nlargefree  uint64                  // number of frees for large objects (>maxsmallsize)
   135  	nsmallfree  [_NumSizeClasses]uint64 // number of frees for small objects (<=maxsmallsize)
   136  
   137  	// arenas is the heap arena map. It points to the metadata for
   138  	// the heap for every arena frame of the entire usable virtual
   139  	// address space.
   140  	//
   141  	// Use arenaIndex to compute indexes into this array.
   142  	//
   143  	// For regions of the address space that are not backed by the
   144  	// Go heap, the arena map contains nil.
   145  	//
   146  	// Modifications are protected by mheap_.lock. Reads can be
   147  	// performed without locking; however, a given entry can
   148  	// transition from nil to non-nil at any time when the lock
   149  	// isn't held. (Entries never transitions back to nil.)
   150  	//
   151  	// In general, this is a two-level mapping consisting of an L1
   152  	// map and possibly many L2 maps. This saves space when there
   153  	// are a huge number of arena frames. However, on many
   154  	// platforms (even 64-bit), arenaL1Bits is 0, making this
   155  	// effectively a single-level map. In this case, arenas[0]
   156  	// will never be nil.
   157  	arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena
   158  
   159  	// heapArenaAlloc is pre-reserved space for allocating heapArena
   160  	// objects. This is only used on 32-bit, where we pre-reserve
   161  	// this space to avoid interleaving it with the heap itself.
   162  	heapArenaAlloc linearAlloc
   163  
   164  	// arenaHints is a list of addresses at which to attempt to
   165  	// add more heap arenas. This is initially populated with a
   166  	// set of general hint addresses, and grown with the bounds of
   167  	// actual heap arena ranges.
   168  	arenaHints *arenaHint
   169  
   170  	// arena is a pre-reserved space for allocating heap arenas
   171  	// (the actual arenas). This is only used on 32-bit.
   172  	arena linearAlloc
   173  
   174  	// allArenas is the arenaIndex of every mapped arena. This can
   175  	// be used to iterate through the address space.
   176  	//
   177  	// Access is protected by mheap_.lock. However, since this is
   178  	// append-only and old backing arrays are never freed, it is
   179  	// safe to acquire mheap_.lock, copy the slice header, and
   180  	// then release mheap_.lock.
   181  	allArenas []arenaIdx
   182  
   183  	// sweepArenas is a snapshot of allArenas taken at the
   184  	// beginning of the sweep cycle. This can be read safely by
   185  	// simply blocking GC (by disabling preemption).
   186  	sweepArenas []arenaIdx
   187  
   188  	_ uint32 // ensure 64-bit alignment of central
   189  
   190  	// central free lists for small size classes.
   191  	// the padding makes sure that the mcentrals are
   192  	// spaced CacheLinePadSize bytes apart, so that each mcentral.lock
   193  	// gets its own cache line.
   194  	// central is indexed by spanClass.
   195  	central [numSpanClasses]struct {
   196  		mcentral mcentral
   197  		pad      [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte
   198  	}
   199  
   200  	spanalloc             fixalloc // allocator for span*
   201  	cachealloc            fixalloc // allocator for mcache*
   202  	treapalloc            fixalloc // allocator for treapNodes*
   203  	specialfinalizeralloc fixalloc // allocator for specialfinalizer*
   204  	specialprofilealloc   fixalloc // allocator for specialprofile*
   205  	speciallock           mutex    // lock for special record allocators.
   206  	arenaHintAlloc        fixalloc // allocator for arenaHints
   207  
   208  	unused *specialfinalizer // never set, just here to force the specialfinalizer type into DWARF
   209  }
   210  
   211  var mheap_ mheap
   212  
   213  // A heapArena stores metadata for a heap arena. heapArenas are stored
   214  // outside of the Go heap and accessed via the mheap_.arenas index.
   215  //
   216  // This gets allocated directly from the OS, so ideally it should be a
   217  // multiple of the system page size. For example, avoid adding small
   218  // fields.
   219  //
   220  //go:notinheap
   221  type heapArena struct {
   222  	// bitmap stores the pointer/scalar bitmap for the words in
   223  	// this arena. See mbitmap.go for a description. Use the
   224  	// heapBits type to access this.
   225  	bitmap [heapArenaBitmapBytes]byte
   226  
   227  	// spans maps from virtual address page ID within this arena to *mspan.
   228  	// For allocated spans, their pages map to the span itself.
   229  	// For free spans, only the lowest and highest pages map to the span itself.
   230  	// Internal pages map to an arbitrary span.
   231  	// For pages that have never been allocated, spans entries are nil.
   232  	//
   233  	// Modifications are protected by mheap.lock. Reads can be
   234  	// performed without locking, but ONLY from indexes that are
   235  	// known to contain in-use or stack spans. This means there
   236  	// must not be a safe-point between establishing that an
   237  	// address is live and looking it up in the spans array.
   238  	spans [pagesPerArena]*mspan
   239  
   240  	// pageInUse is a bitmap that indicates which spans are in
   241  	// state mSpanInUse. This bitmap is indexed by page number,
   242  	// but only the bit corresponding to the first page in each
   243  	// span is used.
   244  	//
   245  	// Writes are protected by mheap_.lock.
   246  	pageInUse [pagesPerArena / 8]uint8
   247  
   248  	// pageMarks is a bitmap that indicates which spans have any
   249  	// marked objects on them. Like pageInUse, only the bit
   250  	// corresponding to the first page in each span is used.
   251  	//
   252  	// Writes are done atomically during marking. Reads are
   253  	// non-atomic and lock-free since they only occur during
   254  	// sweeping (and hence never race with writes).
   255  	//
   256  	// This is used to quickly find whole spans that can be freed.
   257  	//
   258  	// TODO(austin): It would be nice if this was uint64 for
   259  	// faster scanning, but we don't have 64-bit atomic bit
   260  	// operations.
   261  	pageMarks [pagesPerArena / 8]uint8
   262  }
   263  
   264  // arenaHint is a hint for where to grow the heap arenas. See
   265  // mheap_.arenaHints.
   266  //
   267  //go:notinheap
   268  type arenaHint struct {
   269  	addr uintptr
   270  	down bool
   271  	next *arenaHint
   272  }
   273  
   274  // An mspan is a run of pages.
   275  //
   276  // When a mspan is in the heap free treap, state == mSpanFree
   277  // and heapmap(s->start) == span, heapmap(s->start+s->npages-1) == span.
   278  // If the mspan is in the heap scav treap, then in addition to the
   279  // above scavenged == true. scavenged == false in all other cases.
   280  //
   281  // When a mspan is allocated, state == mSpanInUse or mSpanManual
   282  // and heapmap(i) == span for all s->start <= i < s->start+s->npages.
   283  
   284  // Every mspan is in one doubly-linked list, either in the mheap's
   285  // busy list or one of the mcentral's span lists.
   286  
   287  // An mspan representing actual memory has state mSpanInUse,
   288  // mSpanManual, or mSpanFree. Transitions between these states are
   289  // constrained as follows:
   290  //
   291  // * A span may transition from free to in-use or manual during any GC
   292  //   phase.
   293  //
   294  // * During sweeping (gcphase == _GCoff), a span may transition from
   295  //   in-use to free (as a result of sweeping) or manual to free (as a
   296  //   result of stacks being freed).
   297  //
   298  // * During GC (gcphase != _GCoff), a span *must not* transition from
   299  //   manual or in-use to free. Because concurrent GC may read a pointer
   300  //   and then look up its span, the span state must be monotonic.
   301  type mSpanState uint8
   302  
   303  const (
   304  	mSpanDead   mSpanState = iota
   305  	mSpanInUse             // allocated for garbage collected heap
   306  	mSpanManual            // allocated for manual management (e.g., stack allocator)
   307  	mSpanFree
   308  )
   309  
   310  // mSpanStateNames are the names of the span states, indexed by
   311  // mSpanState.
   312  var mSpanStateNames = []string{
   313  	"mSpanDead",
   314  	"mSpanInUse",
   315  	"mSpanManual",
   316  	"mSpanFree",
   317  }
   318  
   319  // mSpanList heads a linked list of spans.
   320  //
   321  //go:notinheap
   322  type mSpanList struct {
   323  	first *mspan // first span in list, or nil if none
   324  	last  *mspan // last span in list, or nil if none
   325  }
   326  
   327  //go:notinheap
   328  type mspan struct {
   329  	next *mspan     // next span in list, or nil if none
   330  	prev *mspan     // previous span in list, or nil if none
   331  	list *mSpanList // For debugging. TODO: Remove.
   332  
   333  	startAddr uintptr // address of first byte of span aka s.base()
   334  	npages    uintptr // number of pages in span
   335  
   336  	manualFreeList gclinkptr // list of free objects in mSpanManual spans
   337  
   338  	// freeindex is the slot index between 0 and nelems at which to begin scanning
   339  	// for the next free object in this span.
   340  	// Each allocation scans allocBits starting at freeindex until it encounters a 0
   341  	// indicating a free object. freeindex is then adjusted so that subsequent scans begin
   342  	// just past the newly discovered free object.
   343  	//
   344  	// If freeindex == nelem, this span has no free objects.
   345  	//
   346  	// allocBits is a bitmap of objects in this span.
   347  	// If n >= freeindex and allocBits[n/8] & (1<<(n%8)) is 0
   348  	// then object n is free;
   349  	// otherwise, object n is allocated. Bits starting at nelem are
   350  	// undefined and should never be referenced.
   351  	//
   352  	// Object n starts at address n*elemsize + (start << pageShift).
   353  	freeindex uintptr
   354  	// TODO: Look up nelems from sizeclass and remove this field if it
   355  	// helps performance.
   356  	nelems uintptr // number of object in the span.
   357  
   358  	// Cache of the allocBits at freeindex. allocCache is shifted
   359  	// such that the lowest bit corresponds to the bit freeindex.
   360  	// allocCache holds the complement of allocBits, thus allowing
   361  	// ctz (count trailing zero) to use it directly.
   362  	// allocCache may contain bits beyond s.nelems; the caller must ignore
   363  	// these.
   364  	allocCache uint64
   365  
   366  	// allocBits and gcmarkBits hold pointers to a span's mark and
   367  	// allocation bits. The pointers are 8 byte aligned.
   368  	// There are three arenas where this data is held.
   369  	// free: Dirty arenas that are no longer accessed
   370  	//       and can be reused.
   371  	// next: Holds information to be used in the next GC cycle.
   372  	// current: Information being used during this GC cycle.
   373  	// previous: Information being used during the last GC cycle.
   374  	// A new GC cycle starts with the call to finishsweep_m.
   375  	// finishsweep_m moves the previous arena to the free arena,
   376  	// the current arena to the previous arena, and
   377  	// the next arena to the current arena.
   378  	// The next arena is populated as the spans request
   379  	// memory to hold gcmarkBits for the next GC cycle as well
   380  	// as allocBits for newly allocated spans.
   381  	//
   382  	// The pointer arithmetic is done "by hand" instead of using
   383  	// arrays to avoid bounds checks along critical performance
   384  	// paths.
   385  	// The sweep will free the old allocBits and set allocBits to the
   386  	// gcmarkBits. The gcmarkBits are replaced with a fresh zeroed
   387  	// out memory.
   388  	allocBits  *gcBits
   389  	gcmarkBits *gcBits
   390  
   391  	// sweep generation:
   392  	// if sweepgen == h->sweepgen - 2, the span needs sweeping
   393  	// if sweepgen == h->sweepgen - 1, the span is currently being swept
   394  	// if sweepgen == h->sweepgen, the span is swept and ready to use
   395  	// if sweepgen == h->sweepgen + 1, the span was cached before sweep began and is still cached, and needs sweeping
   396  	// if sweepgen == h->sweepgen + 3, the span was swept and then cached and is still cached
   397  	// h->sweepgen is incremented by 2 after every GC
   398  
   399  	sweepgen    uint32
   400  	divMul      uint16     // for divide by elemsize - divMagic.mul
   401  	baseMask    uint16     // if non-0, elemsize is a power of 2, & this will get object allocation base
   402  	allocCount  uint16     // number of allocated objects
   403  	spanclass   spanClass  // size class and noscan (uint8)
   404  	state       mSpanState // mspaninuse etc
   405  	needzero    uint8      // needs to be zeroed before allocation
   406  	divShift    uint8      // for divide by elemsize - divMagic.shift
   407  	divShift2   uint8      // for divide by elemsize - divMagic.shift2
   408  	scavenged   bool       // whether this span has had its pages released to the OS
   409  	elemsize    uintptr    // computed from sizeclass or from npages
   410  	limit       uintptr    // end of data in span
   411  	speciallock mutex      // guards specials list
   412  	specials    *special   // linked list of special records sorted by offset.
   413  }
   414  
   415  func (s *mspan) base() uintptr {
   416  	return s.startAddr
   417  }
   418  
   419  func (s *mspan) layout() (size, n, total uintptr) {
   420  	total = s.npages << _PageShift
   421  	size = s.elemsize
   422  	if size > 0 {
   423  		n = total / size
   424  	}
   425  	return
   426  }
   427  
   428  // physPageBounds returns the start and end of the span
   429  // rounded in to the physical page size.
   430  func (s *mspan) physPageBounds() (uintptr, uintptr) {
   431  	start := s.base()
   432  	end := start + s.npages<<_PageShift
   433  	if physPageSize > _PageSize {
   434  		// Round start and end in.
   435  		start = (start + physPageSize - 1) &^ (physPageSize - 1)
   436  		end &^= physPageSize - 1
   437  	}
   438  	return start, end
   439  }
   440  
   441  func (h *mheap) coalesce(s *mspan) {
   442  	// merge is a helper which merges other into s, deletes references to other
   443  	// in heap metadata, and then discards it. other must be adjacent to s.
   444  	merge := func(a, b, other *mspan) {
   445  		// Caller must ensure a.startAddr < b.startAddr and that either a or
   446  		// b is s. a and b must be adjacent. other is whichever of the two is
   447  		// not s.
   448  
   449  		if pageSize < physPageSize && a.scavenged && b.scavenged {
   450  			// If we're merging two scavenged spans on systems where
   451  			// pageSize < physPageSize, then their boundary should always be on
   452  			// a physical page boundary, due to the realignment that happens
   453  			// during coalescing. Throw if this case is no longer true, which
   454  			// means the implementation should probably be changed to scavenge
   455  			// along the boundary.
   456  			_, start := a.physPageBounds()
   457  			end, _ := b.physPageBounds()
   458  			if start != end {
   459  				println("runtime: a.base=", hex(a.base()), "a.npages=", a.npages)
   460  				println("runtime: b.base=", hex(b.base()), "b.npages=", b.npages)
   461  				println("runtime: physPageSize=", physPageSize, "pageSize=", pageSize)
   462  				throw("neighboring scavenged spans boundary is not a physical page boundary")
   463  			}
   464  		}
   465  
   466  		// Adjust s via base and npages and also in heap metadata.
   467  		s.npages += other.npages
   468  		s.needzero |= other.needzero
   469  		if a == s {
   470  			h.setSpan(s.base()+s.npages*pageSize-1, s)
   471  		} else {
   472  			s.startAddr = other.startAddr
   473  			h.setSpan(s.base(), s)
   474  		}
   475  
   476  		// The size is potentially changing so the treap needs to delete adjacent nodes and
   477  		// insert back as a combined node.
   478  		h.free.removeSpan(other)
   479  		other.state = mSpanDead
   480  		h.spanalloc.free(unsafe.Pointer(other))
   481  	}
   482  
   483  	// realign is a helper which shrinks other and grows s such that their
   484  	// boundary is on a physical page boundary.
   485  	realign := func(a, b, other *mspan) {
   486  		// Caller must ensure a.startAddr < b.startAddr and that either a or
   487  		// b is s. a and b must be adjacent. other is whichever of the two is
   488  		// not s.
   489  
   490  		// If pageSize >= physPageSize then spans are always aligned
   491  		// to physical page boundaries, so just exit.
   492  		if pageSize >= physPageSize {
   493  			return
   494  		}
   495  		// Since we're resizing other, we must remove it from the treap.
   496  		h.free.removeSpan(other)
   497  
   498  		// Round boundary to the nearest physical page size, toward the
   499  		// scavenged span.
   500  		boundary := b.startAddr
   501  		if a.scavenged {
   502  			boundary &^= (physPageSize - 1)
   503  		} else {
   504  			boundary = (boundary + physPageSize - 1) &^ (physPageSize - 1)
   505  		}
   506  		a.npages = (boundary - a.startAddr) / pageSize
   507  		b.npages = (b.startAddr + b.npages*pageSize - boundary) / pageSize
   508  		b.startAddr = boundary
   509  
   510  		h.setSpan(boundary-1, a)
   511  		h.setSpan(boundary, b)
   512  
   513  		// Re-insert other now that it has a new size.
   514  		h.free.insert(other)
   515  	}
   516  
   517  	hpMiddle := s.hugePages()
   518  
   519  	// Coalesce with earlier, later spans.
   520  	var hpBefore uintptr
   521  	if before := spanOf(s.base() - 1); before != nil && before.state == mSpanFree {
   522  		if s.scavenged == before.scavenged {
   523  			hpBefore = before.hugePages()
   524  			merge(before, s, before)
   525  		} else {
   526  			realign(before, s, before)
   527  		}
   528  	}
   529  
   530  	// Now check to see if next (greater addresses) span is free and can be coalesced.
   531  	var hpAfter uintptr
   532  	if after := spanOf(s.base() + s.npages*pageSize); after != nil && after.state == mSpanFree {
   533  		if s.scavenged == after.scavenged {
   534  			hpAfter = after.hugePages()
   535  			merge(s, after, after)
   536  		} else {
   537  			realign(s, after, after)
   538  		}
   539  	}
   540  	if !s.scavenged && s.hugePages() > hpBefore+hpMiddle+hpAfter {
   541  		// If s has grown such that it now may contain more huge pages than it
   542  		// and its now-coalesced neighbors did before, then mark the whole region
   543  		// as huge-page-backable.
   544  		//
   545  		// Otherwise, on systems where we break up huge pages (like Linux)
   546  		// s may not be backed by huge pages because it could be made up of
   547  		// pieces which are broken up in the underlying VMA. The primary issue
   548  		// with this is that it can lead to a poor estimate of the amount of
   549  		// free memory backed by huge pages for determining the scavenging rate.
   550  		//
   551  		// TODO(mknyszek): Measure the performance characteristics of sysHugePage
   552  		// and determine whether it makes sense to only sysHugePage on the pages
   553  		// that matter, or if it's better to just mark the whole region.
   554  		sysHugePage(unsafe.Pointer(s.base()), s.npages*pageSize)
   555  	}
   556  }
   557  
   558  // hugePages returns the number of aligned physical huge pages in the memory
   559  // regioned owned by this mspan.
   560  func (s *mspan) hugePages() uintptr {
   561  	if physHugePageSize == 0 || s.npages < physHugePageSize/pageSize {
   562  		return 0
   563  	}
   564  	start := s.base()
   565  	end := start + s.npages*pageSize
   566  	if physHugePageSize > pageSize {
   567  		// Round start and end in.
   568  		start = (start + physHugePageSize - 1) &^ (physHugePageSize - 1)
   569  		end &^= physHugePageSize - 1
   570  	}
   571  	if start < end {
   572  		return (end - start) >> physHugePageShift
   573  	}
   574  	return 0
   575  }
   576  
   577  func (s *mspan) scavenge() uintptr {
   578  	// start and end must be rounded in, otherwise madvise
   579  	// will round them *out* and release more memory
   580  	// than we want.
   581  	start, end := s.physPageBounds()
   582  	if end <= start {
   583  		// start and end don't span a whole physical page.
   584  		return 0
   585  	}
   586  	released := end - start
   587  	memstats.heap_released += uint64(released)
   588  	s.scavenged = true
   589  	sysUnused(unsafe.Pointer(start), released)
   590  	return released
   591  }
   592  
   593  // released returns the number of bytes in this span
   594  // which were returned back to the OS.
   595  func (s *mspan) released() uintptr {
   596  	if !s.scavenged {
   597  		return 0
   598  	}
   599  	start, end := s.physPageBounds()
   600  	return end - start
   601  }
   602  
   603  // recordspan adds a newly allocated span to h.allspans.
   604  //
   605  // This only happens the first time a span is allocated from
   606  // mheap.spanalloc (it is not called when a span is reused).
   607  //
   608  // Write barriers are disallowed here because it can be called from
   609  // gcWork when allocating new workbufs. However, because it's an
   610  // indirect call from the fixalloc initializer, the compiler can't see
   611  // this.
   612  //
   613  //go:nowritebarrierrec
   614  func recordspan(vh unsafe.Pointer, p unsafe.Pointer) {
   615  	h := (*mheap)(vh)
   616  	s := (*mspan)(p)
   617  	if len(h.allspans) >= cap(h.allspans) {
   618  		n := 64 * 1024 / sys.PtrSize
   619  		if n < cap(h.allspans)*3/2 {
   620  			n = cap(h.allspans) * 3 / 2
   621  		}
   622  		var new []*mspan
   623  		sp := (*slice)(unsafe.Pointer(&new))
   624  		sp.array = sysAlloc(uintptr(n)*sys.PtrSize, &memstats.other_sys)
   625  		if sp.array == nil {
   626  			throw("runtime: cannot allocate memory")
   627  		}
   628  		sp.len = len(h.allspans)
   629  		sp.cap = n
   630  		if len(h.allspans) > 0 {
   631  			copy(new, h.allspans)
   632  		}
   633  		oldAllspans := h.allspans
   634  		*(*notInHeapSlice)(unsafe.Pointer(&h.allspans)) = *(*notInHeapSlice)(unsafe.Pointer(&new))
   635  		if len(oldAllspans) != 0 {
   636  			sysFree(unsafe.Pointer(&oldAllspans[0]), uintptr(cap(oldAllspans))*unsafe.Sizeof(oldAllspans[0]), &memstats.other_sys)
   637  		}
   638  	}
   639  	h.allspans = h.allspans[:len(h.allspans)+1]
   640  	h.allspans[len(h.allspans)-1] = s
   641  }
   642  
   643  // A spanClass represents the size class and noscan-ness of a span.
   644  //
   645  // Each size class has a noscan spanClass and a scan spanClass. The
   646  // noscan spanClass contains only noscan objects, which do not contain
   647  // pointers and thus do not need to be scanned by the garbage
   648  // collector.
   649  type spanClass uint8
   650  
   651  const (
   652  	numSpanClasses = _NumSizeClasses << 1
   653  	tinySpanClass  = spanClass(tinySizeClass<<1 | 1)
   654  )
   655  
   656  func makeSpanClass(sizeclass uint8, noscan bool) spanClass {
   657  	return spanClass(sizeclass<<1) | spanClass(bool2int(noscan))
   658  }
   659  
   660  func (sc spanClass) sizeclass() int8 {
   661  	return int8(sc >> 1)
   662  }
   663  
   664  func (sc spanClass) noscan() bool {
   665  	return sc&1 != 0
   666  }
   667  
   668  // arenaIndex returns the index into mheap_.arenas of the arena
   669  // containing metadata for p. This index combines of an index into the
   670  // L1 map and an index into the L2 map and should be used as
   671  // mheap_.arenas[ai.l1()][ai.l2()].
   672  //
   673  // If p is outside the range of valid heap addresses, either l1() or
   674  // l2() will be out of bounds.
   675  //
   676  // It is nosplit because it's called by spanOf and several other
   677  // nosplit functions.
   678  //
   679  //go:nosplit
   680  func arenaIndex(p uintptr) arenaIdx {
   681  	return arenaIdx((p + arenaBaseOffset) / heapArenaBytes)
   682  }
   683  
   684  // arenaBase returns the low address of the region covered by heap
   685  // arena i.
   686  func arenaBase(i arenaIdx) uintptr {
   687  	return uintptr(i)*heapArenaBytes - arenaBaseOffset
   688  }
   689  
   690  type arenaIdx uint
   691  
   692  func (i arenaIdx) l1() uint {
   693  	if arenaL1Bits == 0 {
   694  		// Let the compiler optimize this away if there's no
   695  		// L1 map.
   696  		return 0
   697  	} else {
   698  		return uint(i) >> arenaL1Shift
   699  	}
   700  }
   701  
   702  func (i arenaIdx) l2() uint {
   703  	if arenaL1Bits == 0 {
   704  		return uint(i)
   705  	} else {
   706  		return uint(i) & (1<<arenaL2Bits - 1)
   707  	}
   708  }
   709  
   710  // inheap reports whether b is a pointer into a (potentially dead) heap object.
   711  // It returns false for pointers into mSpanManual spans.
   712  // Non-preemptible because it is used by write barriers.
   713  //go:nowritebarrier
   714  //go:nosplit
   715  func inheap(b uintptr) bool {
   716  	return spanOfHeap(b) != nil
   717  }
   718  
   719  // inHeapOrStack is a variant of inheap that returns true for pointers
   720  // into any allocated heap span.
   721  //
   722  //go:nowritebarrier
   723  //go:nosplit
   724  func inHeapOrStack(b uintptr) bool {
   725  	s := spanOf(b)
   726  	if s == nil || b < s.base() {
   727  		return false
   728  	}
   729  	switch s.state {
   730  	case mSpanInUse, mSpanManual:
   731  		return b < s.limit
   732  	default:
   733  		return false
   734  	}
   735  }
   736  
   737  // spanOf returns the span of p. If p does not point into the heap
   738  // arena or no span has ever contained p, spanOf returns nil.
   739  //
   740  // If p does not point to allocated memory, this may return a non-nil
   741  // span that does *not* contain p. If this is a possibility, the
   742  // caller should either call spanOfHeap or check the span bounds
   743  // explicitly.
   744  //
   745  // Must be nosplit because it has callers that are nosplit.
   746  //
   747  //go:nosplit
   748  func spanOf(p uintptr) *mspan {
   749  	// This function looks big, but we use a lot of constant
   750  	// folding around arenaL1Bits to get it under the inlining
   751  	// budget. Also, many of the checks here are safety checks
   752  	// that Go needs to do anyway, so the generated code is quite
   753  	// short.
   754  	ri := arenaIndex(p)
   755  	if arenaL1Bits == 0 {
   756  		// If there's no L1, then ri.l1() can't be out of bounds but ri.l2() can.
   757  		if ri.l2() >= uint(len(mheap_.arenas[0])) {
   758  			return nil
   759  		}
   760  	} else {
   761  		// If there's an L1, then ri.l1() can be out of bounds but ri.l2() can't.
   762  		if ri.l1() >= uint(len(mheap_.arenas)) {
   763  			return nil
   764  		}
   765  	}
   766  	l2 := mheap_.arenas[ri.l1()]
   767  	if arenaL1Bits != 0 && l2 == nil { // Should never happen if there's no L1.
   768  		return nil
   769  	}
   770  	ha := l2[ri.l2()]
   771  	if ha == nil {
   772  		return nil
   773  	}
   774  	return ha.spans[(p/pageSize)%pagesPerArena]
   775  }
   776  
   777  // spanOfUnchecked is equivalent to spanOf, but the caller must ensure
   778  // that p points into an allocated heap arena.
   779  //
   780  // Must be nosplit because it has callers that are nosplit.
   781  //
   782  //go:nosplit
   783  func spanOfUnchecked(p uintptr) *mspan {
   784  	ai := arenaIndex(p)
   785  	return mheap_.arenas[ai.l1()][ai.l2()].spans[(p/pageSize)%pagesPerArena]
   786  }
   787  
   788  // spanOfHeap is like spanOf, but returns nil if p does not point to a
   789  // heap object.
   790  //
   791  // Must be nosplit because it has callers that are nosplit.
   792  //
   793  //go:nosplit
   794  func spanOfHeap(p uintptr) *mspan {
   795  	s := spanOf(p)
   796  	// If p is not allocated, it may point to a stale span, so we
   797  	// have to check the span's bounds and state.
   798  	if s == nil || p < s.base() || p >= s.limit || s.state != mSpanInUse {
   799  		return nil
   800  	}
   801  	return s
   802  }
   803  
   804  // pageIndexOf returns the arena, page index, and page mask for pointer p.
   805  // The caller must ensure p is in the heap.
   806  func pageIndexOf(p uintptr) (arena *heapArena, pageIdx uintptr, pageMask uint8) {
   807  	ai := arenaIndex(p)
   808  	arena = mheap_.arenas[ai.l1()][ai.l2()]
   809  	pageIdx = ((p / pageSize) / 8) % uintptr(len(arena.pageInUse))
   810  	pageMask = byte(1 << ((p / pageSize) % 8))
   811  	return
   812  }
   813  
   814  // Initialize the heap.
   815  func (h *mheap) init() {
   816  	h.treapalloc.init(unsafe.Sizeof(treapNode{}), nil, nil, &memstats.other_sys)
   817  	h.spanalloc.init(unsafe.Sizeof(mspan{}), recordspan, unsafe.Pointer(h), &memstats.mspan_sys)
   818  	h.cachealloc.init(unsafe.Sizeof(mcache{}), nil, nil, &memstats.mcache_sys)
   819  	h.specialfinalizeralloc.init(unsafe.Sizeof(specialfinalizer{}), nil, nil, &memstats.other_sys)
   820  	h.specialprofilealloc.init(unsafe.Sizeof(specialprofile{}), nil, nil, &memstats.other_sys)
   821  	h.arenaHintAlloc.init(unsafe.Sizeof(arenaHint{}), nil, nil, &memstats.other_sys)
   822  
   823  	// Don't zero mspan allocations. Background sweeping can
   824  	// inspect a span concurrently with allocating it, so it's
   825  	// important that the span's sweepgen survive across freeing
   826  	// and re-allocating a span to prevent background sweeping
   827  	// from improperly cas'ing it from 0.
   828  	//
   829  	// This is safe because mspan contains no heap pointers.
   830  	h.spanalloc.zero = false
   831  
   832  	// h->mapcache needs no init
   833  
   834  	for i := range h.central {
   835  		h.central[i].mcentral.init(spanClass(i))
   836  	}
   837  }
   838  
   839  // reclaim sweeps and reclaims at least npage pages into the heap.
   840  // It is called before allocating npage pages to keep growth in check.
   841  //
   842  // reclaim implements the page-reclaimer half of the sweeper.
   843  //
   844  // h must NOT be locked.
   845  func (h *mheap) reclaim(npage uintptr) {
   846  	// This scans pagesPerChunk at a time. Higher values reduce
   847  	// contention on h.reclaimPos, but increase the minimum
   848  	// latency of performing a reclaim.
   849  	//
   850  	// Must be a multiple of the pageInUse bitmap element size.
   851  	//
   852  	// The time required by this can vary a lot depending on how
   853  	// many spans are actually freed. Experimentally, it can scan
   854  	// for pages at ~300 GB/ms on a 2.6GHz Core i7, but can only
   855  	// free spans at ~32 MB/ms. Using 512 pages bounds this at
   856  	// roughly 100┬Ás.
   857  	//
   858  	// TODO(austin): Half of the time spent freeing spans is in
   859  	// locking/unlocking the heap (even with low contention). We
   860  	// could make the slow path here several times faster by
   861  	// batching heap frees.
   862  	const pagesPerChunk = 512
   863  
   864  	// Bail early if there's no more reclaim work.
   865  	if atomic.Load64(&h.reclaimIndex) >= 1<<63 {
   866  		return
   867  	}
   868  
   869  	// Disable preemption so the GC can't start while we're
   870  	// sweeping, so we can read h.sweepArenas, and so
   871  	// traceGCSweepStart/Done pair on the P.
   872  	mp := acquirem()
   873  
   874  	if trace.enabled {
   875  		traceGCSweepStart()
   876  	}
   877  
   878  	arenas := h.sweepArenas
   879  	locked := false
   880  	for npage > 0 {
   881  		// Pull from accumulated credit first.
   882  		if credit := atomic.Loaduintptr(&h.reclaimCredit); credit > 0 {
   883  			take := credit
   884  			if take > npage {
   885  				// Take only what we need.
   886  				take = npage
   887  			}
   888  			if atomic.Casuintptr(&h.reclaimCredit, credit, credit-take) {
   889  				npage -= take
   890  			}
   891  			continue
   892  		}
   893  
   894  		// Claim a chunk of work.
   895  		idx := uintptr(atomic.Xadd64(&h.reclaimIndex, pagesPerChunk) - pagesPerChunk)
   896  		if idx/pagesPerArena >= uintptr(len(arenas)) {
   897  			// Page reclaiming is done.
   898  			atomic.Store64(&h.reclaimIndex, 1<<63)
   899  			break
   900  		}
   901  
   902  		if !locked {
   903  			// Lock the heap for reclaimChunk.
   904  			lock(&h.lock)
   905  			locked = true
   906  		}
   907  
   908  		// Scan this chunk.
   909  		nfound := h.reclaimChunk(arenas, idx, pagesPerChunk)
   910  		if nfound <= npage {
   911  			npage -= nfound
   912  		} else {
   913  			// Put spare pages toward global credit.
   914  			atomic.Xadduintptr(&h.reclaimCredit, nfound-npage)
   915  			npage = 0
   916  		}
   917  	}
   918  	if locked {
   919  		unlock(&h.lock)
   920  	}
   921  
   922  	if trace.enabled {
   923  		traceGCSweepDone()
   924  	}
   925  	releasem(mp)
   926  }
   927  
   928  // reclaimChunk sweeps unmarked spans that start at page indexes [pageIdx, pageIdx+n).
   929  // It returns the number of pages returned to the heap.
   930  //
   931  // h.lock must be held and the caller must be non-preemptible.
   932  func (h *mheap) reclaimChunk(arenas []arenaIdx, pageIdx, n uintptr) uintptr {
   933  	// The heap lock must be held because this accesses the
   934  	// heapArena.spans arrays using potentially non-live pointers.
   935  	// In particular, if a span were freed and merged concurrently
   936  	// with this probing heapArena.spans, it would be possible to
   937  	// observe arbitrary, stale span pointers.
   938  	n0 := n
   939  	var nFreed uintptr
   940  	sg := h.sweepgen
   941  	for n > 0 {
   942  		ai := arenas[pageIdx/pagesPerArena]
   943  		ha := h.arenas[ai.l1()][ai.l2()]
   944  
   945  		// Get a chunk of the bitmap to work on.
   946  		arenaPage := uint(pageIdx % pagesPerArena)
   947  		inUse := ha.pageInUse[arenaPage/8:]
   948  		marked := ha.pageMarks[arenaPage/8:]
   949  		if uintptr(len(inUse)) > n/8 {
   950  			inUse = inUse[:n/8]
   951  			marked = marked[:n/8]
   952  		}
   953  
   954  		// Scan this bitmap chunk for spans that are in-use
   955  		// but have no marked objects on them.
   956  		for i := range inUse {
   957  			inUseUnmarked := inUse[i] &^ marked[i]
   958  			if inUseUnmarked == 0 {
   959  				continue
   960  			}
   961  
   962  			for j := uint(0); j < 8; j++ {
   963  				if inUseUnmarked&(1<<j) != 0 {
   964  					s := ha.spans[arenaPage+uint(i)*8+j]
   965  					if atomic.Load(&s.sweepgen) == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
   966  						npages := s.npages
   967  						unlock(&h.lock)
   968  						if s.sweep(false) {
   969  							nFreed += npages
   970  						}
   971  						lock(&h.lock)
   972  						// Reload inUse. It's possible nearby
   973  						// spans were freed when we dropped the
   974  						// lock and we don't want to get stale
   975  						// pointers from the spans array.
   976  						inUseUnmarked = inUse[i] &^ marked[i]
   977  					}
   978  				}
   979  			}
   980  		}
   981  
   982  		// Advance.
   983  		pageIdx += uintptr(len(inUse) * 8)
   984  		n -= uintptr(len(inUse) * 8)
   985  	}
   986  	if trace.enabled {
   987  		// Account for pages scanned but not reclaimed.
   988  		traceGCSweepSpan((n0 - nFreed) * pageSize)
   989  	}
   990  	return nFreed
   991  }
   992  
   993  // alloc_m is the internal implementation of mheap.alloc.
   994  //
   995  // alloc_m must run on the system stack because it locks the heap, so
   996  // any stack growth during alloc_m would self-deadlock.
   997  //
   998  //go:systemstack
   999  func (h *mheap) alloc_m(npage uintptr, spanclass spanClass, large bool) *mspan {
  1000  	_g_ := getg()
  1001  
  1002  	// To prevent excessive heap growth, before allocating n pages
  1003  	// we need to sweep and reclaim at least n pages.
  1004  	if h.sweepdone == 0 {
  1005  		h.reclaim(npage)
  1006  	}
  1007  
  1008  	lock(&h.lock)
  1009  	// transfer stats from cache to global
  1010  	memstats.heap_scan += uint64(_g_.m.mcache.local_scan)
  1011  	_g_.m.mcache.local_scan = 0
  1012  	memstats.tinyallocs += uint64(_g_.m.mcache.local_tinyallocs)
  1013  	_g_.m.mcache.local_tinyallocs = 0
  1014  
  1015  	s := h.allocSpanLocked(npage, &memstats.heap_inuse)
  1016  	if s != nil {
  1017  		// Record span info, because gc needs to be
  1018  		// able to map interior pointer to containing span.
  1019  		atomic.Store(&s.sweepgen, h.sweepgen)
  1020  		h.sweepSpans[h.sweepgen/2%2].push(s) // Add to swept in-use list.
  1021  		s.state = mSpanInUse
  1022  		s.allocCount = 0
  1023  		s.spanclass = spanclass
  1024  		if sizeclass := spanclass.sizeclass(); sizeclass == 0 {
  1025  			s.elemsize = s.npages << _PageShift
  1026  			s.divShift = 0
  1027  			s.divMul = 0
  1028  			s.divShift2 = 0
  1029  			s.baseMask = 0
  1030  		} else {
  1031  			s.elemsize = uintptr(class_to_size[sizeclass])
  1032  			m := &class_to_divmagic[sizeclass]
  1033  			s.divShift = m.shift
  1034  			s.divMul = m.mul
  1035  			s.divShift2 = m.shift2
  1036  			s.baseMask = m.baseMask
  1037  		}
  1038  
  1039  		// Mark in-use span in arena page bitmap.
  1040  		arena, pageIdx, pageMask := pageIndexOf(s.base())
  1041  		arena.pageInUse[pageIdx] |= pageMask
  1042  
  1043  		// update stats, sweep lists
  1044  		h.pagesInUse += uint64(npage)
  1045  		if large {
  1046  			memstats.heap_objects++
  1047  			mheap_.largealloc += uint64(s.elemsize)
  1048  			mheap_.nlargealloc++
  1049  			atomic.Xadd64(&memstats.heap_live, int64(npage<<_PageShift))
  1050  		}
  1051  	}
  1052  	// heap_scan and heap_live were updated.
  1053  	if gcBlackenEnabled != 0 {
  1054  		gcController.revise()
  1055  	}
  1056  
  1057  	if trace.enabled {
  1058  		traceHeapAlloc()
  1059  	}
  1060  
  1061  	// h.spans is accessed concurrently without synchronization
  1062  	// from other threads. Hence, there must be a store/store
  1063  	// barrier here to ensure the writes to h.spans above happen
  1064  	// before the caller can publish a pointer p to an object
  1065  	// allocated from s. As soon as this happens, the garbage
  1066  	// collector running on another processor could read p and
  1067  	// look up s in h.spans. The unlock acts as the barrier to
  1068  	// order these writes. On the read side, the data dependency
  1069  	// between p and the index in h.spans orders the reads.
  1070  	unlock(&h.lock)
  1071  	return s
  1072  }
  1073  
  1074  // alloc allocates a new span of npage pages from the GC'd heap.
  1075  //
  1076  // Either large must be true or spanclass must indicates the span's
  1077  // size class and scannability.
  1078  //
  1079  // If needzero is true, the memory for the returned span will be zeroed.
  1080  func (h *mheap) alloc(npage uintptr, spanclass spanClass, large bool, needzero bool) *mspan {
  1081  	// Don't do any operations that lock the heap on the G stack.
  1082  	// It might trigger stack growth, and the stack growth code needs
  1083  	// to be able to allocate heap.
  1084  	var s *mspan
  1085  	systemstack(func() {
  1086  		s = h.alloc_m(npage, spanclass, large)
  1087  	})
  1088  
  1089  	if s != nil {
  1090  		if needzero && s.needzero != 0 {
  1091  			memclrNoHeapPointers(unsafe.Pointer(s.base()), s.npages<<_PageShift)
  1092  		}
  1093  		s.needzero = 0
  1094  	}
  1095  	return s
  1096  }
  1097  
  1098  // allocManual allocates a manually-managed span of npage pages.
  1099  // allocManual returns nil if allocation fails.
  1100  //
  1101  // allocManual adds the bytes used to *stat, which should be a
  1102  // memstats in-use field. Unlike allocations in the GC'd heap, the
  1103  // allocation does *not* count toward heap_inuse or heap_sys.
  1104  //
  1105  // The memory backing the returned span may not be zeroed if
  1106  // span.needzero is set.
  1107  //
  1108  // allocManual must be called on the system stack because it acquires
  1109  // the heap lock. See mheap for details.
  1110  //
  1111  //go:systemstack
  1112  func (h *mheap) allocManual(npage uintptr, stat *uint64) *mspan {
  1113  	lock(&h.lock)
  1114  	s := h.allocSpanLocked(npage, stat)
  1115  	if s != nil {
  1116  		s.state = mSpanManual
  1117  		s.manualFreeList = 0
  1118  		s.allocCount = 0
  1119  		s.spanclass = 0
  1120  		s.nelems = 0
  1121  		s.elemsize = 0
  1122  		s.limit = s.base() + s.npages<<_PageShift
  1123  		// Manually managed memory doesn't count toward heap_sys.
  1124  		memstats.heap_sys -= uint64(s.npages << _PageShift)
  1125  	}
  1126  
  1127  	// This unlock acts as a release barrier. See mheap.alloc_m.
  1128  	unlock(&h.lock)
  1129  
  1130  	return s
  1131  }
  1132  
  1133  // setSpan modifies the span map so spanOf(base) is s.
  1134  func (h *mheap) setSpan(base uintptr, s *mspan) {
  1135  	ai := arenaIndex(base)
  1136  	h.arenas[ai.l1()][ai.l2()].spans[(base/pageSize)%pagesPerArena] = s
  1137  }
  1138  
  1139  // setSpans modifies the span map so [spanOf(base), spanOf(base+npage*pageSize))
  1140  // is s.
  1141  func (h *mheap) setSpans(base, npage uintptr, s *mspan) {
  1142  	p := base / pageSize
  1143  	ai := arenaIndex(base)
  1144  	ha := h.arenas[ai.l1()][ai.l2()]
  1145  	for n := uintptr(0); n < npage; n++ {
  1146  		i := (p + n) % pagesPerArena
  1147  		if i == 0 {
  1148  			ai = arenaIndex(base + n*pageSize)
  1149  			ha = h.arenas[ai.l1()][ai.l2()]
  1150  		}
  1151  		ha.spans[i] = s
  1152  	}
  1153  }
  1154  
  1155  // Allocates a span of the given size.  h must be locked.
  1156  // The returned span has been removed from the
  1157  // free structures, but its state is still mSpanFree.
  1158  func (h *mheap) allocSpanLocked(npage uintptr, stat *uint64) *mspan {
  1159  	t := h.free.find(npage)
  1160  	if t.valid() {
  1161  		goto HaveSpan
  1162  	}
  1163  	if !h.grow(npage) {
  1164  		return nil
  1165  	}
  1166  	t = h.free.find(npage)
  1167  	if t.valid() {
  1168  		goto HaveSpan
  1169  	}
  1170  	throw("grew heap, but no adequate free span found")
  1171  
  1172  HaveSpan:
  1173  	s := t.span()
  1174  	if s.state != mSpanFree {
  1175  		throw("candidate mspan for allocation is not free")
  1176  	}
  1177  
  1178  	// First, subtract any memory that was released back to
  1179  	// the OS from s. We will add back what's left if necessary.
  1180  	memstats.heap_released -= uint64(s.released())
  1181  
  1182  	if s.npages == npage {
  1183  		h.free.erase(t)
  1184  	} else if s.npages > npage {
  1185  		// Trim off the lower bits and make that our new span.
  1186  		// Do this in-place since this operation does not
  1187  		// affect the original span's location in the treap.
  1188  		n := (*mspan)(h.spanalloc.alloc())
  1189  		h.free.mutate(t, func(s *mspan) {
  1190  			n.init(s.base(), npage)
  1191  			s.npages -= npage
  1192  			s.startAddr = s.base() + npage*pageSize
  1193  			h.setSpan(s.base()-1, n)
  1194  			h.setSpan(s.base(), s)
  1195  			h.setSpan(n.base(), n)
  1196  			n.needzero = s.needzero
  1197  			// n may not be big enough to actually be scavenged, but that's fine.
  1198  			// We still want it to appear to be scavenged so that we can do the
  1199  			// right bookkeeping later on in this function (i.e. sysUsed).
  1200  			n.scavenged = s.scavenged
  1201  			// Check if s is still scavenged.
  1202  			if s.scavenged {
  1203  				start, end := s.physPageBounds()
  1204  				if start < end {
  1205  					memstats.heap_released += uint64(end - start)
  1206  				} else {
  1207  					s.scavenged = false
  1208  				}
  1209  			}
  1210  		})
  1211  		s = n
  1212  	} else {
  1213  		throw("candidate mspan for allocation is too small")
  1214  	}
  1215  	// "Unscavenge" s only AFTER splitting so that
  1216  	// we only sysUsed whatever we actually need.
  1217  	if s.scavenged {
  1218  		// sysUsed all the pages that are actually available
  1219  		// in the span. Note that we don't need to decrement
  1220  		// heap_released since we already did so earlier.
  1221  		sysUsed(unsafe.Pointer(s.base()), s.npages<<_PageShift)
  1222  		s.scavenged = false
  1223  
  1224  		// Since we allocated out of a scavenged span, we just
  1225  		// grew the RSS. Mitigate this by scavenging enough free
  1226  		// space to make up for it but only if we need to.
  1227  		//
  1228  		// scavengeLocked may cause coalescing, so prevent
  1229  		// coalescing with s by temporarily changing its state.
  1230  		s.state = mSpanManual
  1231  		h.scavengeIfNeededLocked(s.npages * pageSize)
  1232  		s.state = mSpanFree
  1233  	}
  1234  
  1235  	h.setSpans(s.base(), npage, s)
  1236  
  1237  	*stat += uint64(npage << _PageShift)
  1238  	memstats.heap_idle -= uint64(npage << _PageShift)
  1239  
  1240  	if s.inList() {
  1241  		throw("still in list")
  1242  	}
  1243  	return s
  1244  }
  1245  
  1246  // Try to add at least npage pages of memory to the heap,
  1247  // returning whether it worked.
  1248  //
  1249  // h must be locked.
  1250  func (h *mheap) grow(npage uintptr) bool {
  1251  	ask := npage << _PageShift
  1252  	v, size := h.sysAlloc(ask)
  1253  	if v == nil {
  1254  		print("runtime: out of memory: cannot allocate ", ask, "-byte block (", memstats.heap_sys, " in use)\n")
  1255  		return false
  1256  	}
  1257  
  1258  	// Create a fake "in use" span and free it, so that the
  1259  	// right accounting and coalescing happens.
  1260  	s := (*mspan)(h.spanalloc.alloc())
  1261  	s.init(uintptr(v), size/pageSize)
  1262  	h.setSpans(s.base(), s.npages, s)
  1263  	s.state = mSpanFree
  1264  	memstats.heap_idle += uint64(size)
  1265  	// (*mheap).sysAlloc returns untouched/uncommitted memory.
  1266  	s.scavenged = true
  1267  	// s is always aligned to the heap arena size which is always > physPageSize,
  1268  	// so its totally safe to just add directly to heap_released. Coalescing,
  1269  	// if possible, will also always be correct in terms of accounting, because
  1270  	// s.base() must be a physical page boundary.
  1271  	memstats.heap_released += uint64(size)
  1272  	h.coalesce(s)
  1273  	h.free.insert(s)
  1274  	return true
  1275  }
  1276  
  1277  // Free the span back into the heap.
  1278  //
  1279  // large must match the value of large passed to mheap.alloc. This is
  1280  // used for accounting.
  1281  func (h *mheap) freeSpan(s *mspan, large bool) {
  1282  	systemstack(func() {
  1283  		mp := getg().m
  1284  		lock(&h.lock)
  1285  		memstats.heap_scan += uint64(mp.mcache.local_scan)
  1286  		mp.mcache.local_scan = 0
  1287  		memstats.tinyallocs += uint64(mp.mcache.local_tinyallocs)
  1288  		mp.mcache.local_tinyallocs = 0
  1289  		if msanenabled {
  1290  			// Tell msan that this entire span is no longer in use.
  1291  			base := unsafe.Pointer(s.base())
  1292  			bytes := s.npages << _PageShift
  1293  			msanfree(base, bytes)
  1294  		}
  1295  		if large {
  1296  			// Match accounting done in mheap.alloc.
  1297  			memstats.heap_objects--
  1298  		}
  1299  		if gcBlackenEnabled != 0 {
  1300  			// heap_scan changed.
  1301  			gcController.revise()
  1302  		}
  1303  		h.freeSpanLocked(s, true, true)
  1304  		unlock(&h.lock)
  1305  	})
  1306  }
  1307  
  1308  // freeManual frees a manually-managed span returned by allocManual.
  1309  // stat must be the same as the stat passed to the allocManual that
  1310  // allocated s.
  1311  //
  1312  // This must only be called when gcphase == _GCoff. See mSpanState for
  1313  // an explanation.
  1314  //
  1315  // freeManual must be called on the system stack because it acquires
  1316  // the heap lock. See mheap for details.
  1317  //
  1318  //go:systemstack
  1319  func (h *mheap) freeManual(s *mspan, stat *uint64) {
  1320  	s.needzero = 1
  1321  	lock(&h.lock)
  1322  	*stat -= uint64(s.npages << _PageShift)
  1323  	memstats.heap_sys += uint64(s.npages << _PageShift)
  1324  	h.freeSpanLocked(s, false, true)
  1325  	unlock(&h.lock)
  1326  }
  1327  
  1328  func (h *mheap) freeSpanLocked(s *mspan, acctinuse, acctidle bool) {
  1329  	switch s.state {
  1330  	case mSpanManual:
  1331  		if s.allocCount != 0 {
  1332  			throw("mheap.freeSpanLocked - invalid stack free")
  1333  		}
  1334  	case mSpanInUse:
  1335  		if s.allocCount != 0 || s.sweepgen != h.sweepgen {
  1336  			print("mheap.freeSpanLocked - span ", s, " ptr ", hex(s.base()), " allocCount ", s.allocCount, " sweepgen ", s.sweepgen, "/", h.sweepgen, "\n")
  1337  			throw("mheap.freeSpanLocked - invalid free")
  1338  		}
  1339  		h.pagesInUse -= uint64(s.npages)
  1340  
  1341  		// Clear in-use bit in arena page bitmap.
  1342  		arena, pageIdx, pageMask := pageIndexOf(s.base())
  1343  		arena.pageInUse[pageIdx] &^= pageMask
  1344  	default:
  1345  		throw("mheap.freeSpanLocked - invalid span state")
  1346  	}
  1347  
  1348  	if acctinuse {
  1349  		memstats.heap_inuse -= uint64(s.npages << _PageShift)
  1350  	}
  1351  	if acctidle {
  1352  		memstats.heap_idle += uint64(s.npages << _PageShift)
  1353  	}
  1354  	s.state = mSpanFree
  1355  
  1356  	// Coalesce span with neighbors.
  1357  	h.coalesce(s)
  1358  
  1359  	// Insert s into the treap.
  1360  	h.free.insert(s)
  1361  }
  1362  
  1363  // scavengeSplit takes t.span() and attempts to split off a span containing size
  1364  // (in bytes) worth of physical pages from the back.
  1365  //
  1366  // The split point is only approximately defined by size since the split point
  1367  // is aligned to physPageSize and pageSize every time. If physHugePageSize is
  1368  // non-zero and the split point would break apart a huge page in the span, then
  1369  // the split point is also aligned to physHugePageSize.
  1370  //
  1371  // If the desired split point ends up at the base of s, or if size is obviously
  1372  // much larger than s, then a split is not possible and this method returns nil.
  1373  // Otherwise if a split occurred it returns the newly-created span.
  1374  func (h *mheap) scavengeSplit(t treapIter, size uintptr) *mspan {
  1375  	s := t.span()
  1376  	start, end := s.physPageBounds()
  1377  	if end <= start || end-start <= size {
  1378  		// Size covers the whole span.
  1379  		return nil
  1380  	}
  1381  	// The span is bigger than what we need, so compute the base for the new
  1382  	// span if we decide to split.
  1383  	base := end - size
  1384  	// Round down to the next physical or logical page, whichever is bigger.
  1385  	base &^= (physPageSize - 1) | (pageSize - 1)
  1386  	if base <= start {
  1387  		return nil
  1388  	}
  1389  	if physHugePageSize > pageSize && base&^(physHugePageSize-1) >= start {
  1390  		// We're in danger of breaking apart a huge page, so include the entire
  1391  		// huge page in the bound by rounding down to the huge page size.
  1392  		// base should still be aligned to pageSize.
  1393  		base &^= physHugePageSize - 1
  1394  	}
  1395  	if base == start {
  1396  		// After all that we rounded base down to s.base(), so no need to split.
  1397  		return nil
  1398  	}
  1399  	if base < start {
  1400  		print("runtime: base=", base, ", s.npages=", s.npages, ", s.base()=", s.base(), ", size=", size, "\n")
  1401  		print("runtime: physPageSize=", physPageSize, ", physHugePageSize=", physHugePageSize, "\n")
  1402  		throw("bad span split base")
  1403  	}
  1404  
  1405  	// Split s in-place, removing from the back.
  1406  	n := (*mspan)(h.spanalloc.alloc())
  1407  	nbytes := s.base() + s.npages*pageSize - base
  1408  	h.free.mutate(t, func(s *mspan) {
  1409  		n.init(base, nbytes/pageSize)
  1410  		s.npages -= nbytes / pageSize
  1411  		h.setSpan(n.base()-1, s)
  1412  		h.setSpan(n.base(), n)
  1413  		h.setSpan(n.base()+nbytes-1, n)
  1414  		n.needzero = s.needzero
  1415  		n.state = s.state
  1416  	})
  1417  	return n
  1418  }
  1419  
  1420  // scavengeLocked scavenges nbytes worth of spans in the free treap by
  1421  // starting from the span with the highest base address and working down.
  1422  // It then takes those spans and places them in scav.
  1423  //
  1424  // Returns the amount of memory scavenged in bytes. h must be locked.
  1425  func (h *mheap) scavengeLocked(nbytes uintptr) uintptr {
  1426  	released := uintptr(0)
  1427  	// Iterate over spans with huge pages first, then spans without.
  1428  	const mask = treapIterScav | treapIterHuge
  1429  	for _, match := range []treapIterType{treapIterHuge, 0} {
  1430  		// Iterate over the treap backwards (from highest address to lowest address)
  1431  		// scavenging spans until we've reached our quota of nbytes.
  1432  		for t := h.free.end(mask, match); released < nbytes && t.valid(); {
  1433  			s := t.span()
  1434  			start, end := s.physPageBounds()
  1435  			if start >= end {
  1436  				// This span doesn't cover at least one physical page, so skip it.
  1437  				t = t.prev()
  1438  				continue
  1439  			}
  1440  			n := t.prev()
  1441  			if span := h.scavengeSplit(t, nbytes-released); span != nil {
  1442  				s = span
  1443  			} else {
  1444  				h.free.erase(t)
  1445  			}
  1446  			released += s.scavenge()
  1447  			// Now that s is scavenged, we must eagerly coalesce it
  1448  			// with its neighbors to prevent having two spans with
  1449  			// the same scavenged state adjacent to each other.
  1450  			h.coalesce(s)
  1451  			t = n
  1452  			h.free.insert(s)
  1453  		}
  1454  	}
  1455  	return released
  1456  }
  1457  
  1458  // scavengeIfNeededLocked calls scavengeLocked if we're currently above the
  1459  // scavenge goal in order to prevent the mutator from out-running the
  1460  // the scavenger.
  1461  //
  1462  // h must be locked.
  1463  func (h *mheap) scavengeIfNeededLocked(size uintptr) {
  1464  	if r := heapRetained(); r+uint64(size) > h.scavengeRetainedGoal {
  1465  		todo := uint64(size)
  1466  		// If we're only going to go a little bit over, just request what
  1467  		// we actually need done.
  1468  		if overage := r + uint64(size) - h.scavengeRetainedGoal; overage < todo {
  1469  			todo = overage
  1470  		}
  1471  		h.scavengeLocked(uintptr(todo))
  1472  	}
  1473  }
  1474  
  1475  // scavengeAll visits each node in the free treap and scavenges the
  1476  // treapNode's span. It then removes the scavenged span from
  1477  // unscav and adds it into scav before continuing.
  1478  func (h *mheap) scavengeAll() {
  1479  	// Disallow malloc or panic while holding the heap lock. We do
  1480  	// this here because this is an non-mallocgc entry-point to
  1481  	// the mheap API.
  1482  	gp := getg()
  1483  	gp.m.mallocing++
  1484  	lock(&h.lock)
  1485  	released := h.scavengeLocked(^uintptr(0))
  1486  	unlock(&h.lock)
  1487  	gp.m.mallocing--
  1488  
  1489  	if debug.gctrace > 0 {
  1490  		if released > 0 {
  1491  			print("forced scvg: ", released>>20, " MB released\n")
  1492  		}
  1493  		print("forced scvg: inuse: ", memstats.heap_inuse>>20, ", idle: ", memstats.heap_idle>>20, ", sys: ", memstats.heap_sys>>20, ", released: ", memstats.heap_released>>20, ", consumed: ", (memstats.heap_sys-memstats.heap_released)>>20, " (MB)\n")
  1494  	}
  1495  }
  1496  
  1497  //go:linkname runtime_debug_freeOSMemory runtime/debug.freeOSMemory
  1498  func runtime_debug_freeOSMemory() {
  1499  	GC()
  1500  	systemstack(func() { mheap_.scavengeAll() })
  1501  }
  1502  
  1503  // Initialize a new span with the given start and npages.
  1504  func (span *mspan) init(base uintptr, npages uintptr) {
  1505  	// span is *not* zeroed.
  1506  	span.next = nil
  1507  	span.prev = nil
  1508  	span.list = nil
  1509  	span.startAddr = base
  1510  	span.npages = npages
  1511  	span.allocCount = 0
  1512  	span.spanclass = 0
  1513  	span.elemsize = 0
  1514  	span.state = mSpanDead
  1515  	span.scavenged = false
  1516  	span.speciallock.key = 0
  1517  	span.specials = nil
  1518  	span.needzero = 0
  1519  	span.freeindex = 0
  1520  	span.allocBits = nil
  1521  	span.gcmarkBits = nil
  1522  }
  1523  
  1524  func (span *mspan) inList() bool {
  1525  	return span.list != nil
  1526  }
  1527  
  1528  // Initialize an empty doubly-linked list.
  1529  func (list *mSpanList) init() {
  1530  	list.first = nil
  1531  	list.last = nil
  1532  }
  1533  
  1534  func (list *mSpanList) remove(span *mspan) {
  1535  	if span.list != list {
  1536  		print("runtime: failed mSpanList.remove span.npages=", span.npages,
  1537  			" span=", span, " prev=", span.prev, " span.list=", span.list, " list=", list, "\n")
  1538  		throw("mSpanList.remove")
  1539  	}
  1540  	if list.first == span {
  1541  		list.first = span.next
  1542  	} else {
  1543  		span.prev.next = span.next
  1544  	}
  1545  	if list.last == span {
  1546  		list.last = span.prev
  1547  	} else {
  1548  		span.next.prev = span.prev
  1549  	}
  1550  	span.next = nil
  1551  	span.prev = nil
  1552  	span.list = nil
  1553  }
  1554  
  1555  func (list *mSpanList) isEmpty() bool {
  1556  	return list.first == nil
  1557  }
  1558  
  1559  func (list *mSpanList) insert(span *mspan) {
  1560  	if span.next != nil || span.prev != nil || span.list != nil {
  1561  		println("runtime: failed mSpanList.insert", span, span.next, span.prev, span.list)
  1562  		throw("mSpanList.insert")
  1563  	}
  1564  	span.next = list.first
  1565  	if list.first != nil {
  1566  		// The list contains at least one span; link it in.
  1567  		// The last span in the list doesn't change.
  1568  		list.first.prev = span
  1569  	} else {
  1570  		// The list contains no spans, so this is also the last span.
  1571  		list.last = span
  1572  	}
  1573  	list.first = span
  1574  	span.list = list
  1575  }
  1576  
  1577  func (list *mSpanList) insertBack(span *mspan) {
  1578  	if span.next != nil || span.prev != nil || span.list != nil {
  1579  		println("runtime: failed mSpanList.insertBack", span, span.next, span.prev, span.list)
  1580  		throw("mSpanList.insertBack")
  1581  	}
  1582  	span.prev = list.last
  1583  	if list.last != nil {
  1584  		// The list contains at least one span.
  1585  		list.last.next = span
  1586  	} else {
  1587  		// The list contains no spans, so this is also the first span.
  1588  		list.first = span
  1589  	}
  1590  	list.last = span
  1591  	span.list = list
  1592  }
  1593  
  1594  // takeAll removes all spans from other and inserts them at the front
  1595  // of list.
  1596  func (list *mSpanList) takeAll(other *mSpanList) {
  1597  	if other.isEmpty() {
  1598  		return
  1599  	}
  1600  
  1601  	// Reparent everything in other to list.
  1602  	for s := other.first; s != nil; s = s.next {
  1603  		s.list = list
  1604  	}
  1605  
  1606  	// Concatenate the lists.
  1607  	if list.isEmpty() {
  1608  		*list = *other
  1609  	} else {
  1610  		// Neither list is empty. Put other before list.
  1611  		other.last.next = list.first
  1612  		list.first.prev = other.last
  1613  		list.first = other.first
  1614  	}
  1615  
  1616  	other.first, other.last = nil, nil
  1617  }
  1618  
  1619  const (
  1620  	_KindSpecialFinalizer = 1
  1621  	_KindSpecialProfile   = 2
  1622  	// Note: The finalizer special must be first because if we're freeing
  1623  	// an object, a finalizer special will cause the freeing operation
  1624  	// to abort, and we want to keep the other special records around
  1625  	// if that happens.
  1626  )
  1627  
  1628  //go:notinheap
  1629  type special struct {
  1630  	next   *special // linked list in span
  1631  	offset uint16   // span offset of object
  1632  	kind   byte     // kind of special
  1633  }
  1634  
  1635  // Adds the special record s to the list of special records for
  1636  // the object p. All fields of s should be filled in except for
  1637  // offset & next, which this routine will fill in.
  1638  // Returns true if the special was successfully added, false otherwise.
  1639  // (The add will fail only if a record with the same p and s->kind
  1640  //  already exists.)
  1641  func addspecial(p unsafe.Pointer, s *special) bool {
  1642  	span := spanOfHeap(uintptr(p))
  1643  	if span == nil {
  1644  		throw("addspecial on invalid pointer")
  1645  	}
  1646  
  1647  	// Ensure that the span is swept.
  1648  	// Sweeping accesses the specials list w/o locks, so we have
  1649  	// to synchronize with it. And it's just much safer.
  1650  	mp := acquirem()
  1651  	span.ensureSwept()
  1652  
  1653  	offset := uintptr(p) - span.base()
  1654  	kind := s.kind
  1655  
  1656  	lock(&span.speciallock)
  1657  
  1658  	// Find splice point, check for existing record.
  1659  	t := &span.specials
  1660  	for {
  1661  		x := *t
  1662  		if x == nil {
  1663  			break
  1664  		}
  1665  		if offset == uintptr(x.offset) && kind == x.kind {
  1666  			unlock(&span.speciallock)
  1667  			releasem(mp)
  1668  			return false // already exists
  1669  		}
  1670  		if offset < uintptr(x.offset) || (offset == uintptr(x.offset) && kind < x.kind) {
  1671  			break
  1672  		}
  1673  		t = &x.next
  1674  	}
  1675  
  1676  	// Splice in record, fill in offset.
  1677  	s.offset = uint16(offset)
  1678  	s.next = *t
  1679  	*t = s
  1680  	unlock(&span.speciallock)
  1681  	releasem(mp)
  1682  
  1683  	return true
  1684  }
  1685  
  1686  // Removes the Special record of the given kind for the object p.
  1687  // Returns the record if the record existed, nil otherwise.
  1688  // The caller must FixAlloc_Free the result.
  1689  func removespecial(p unsafe.Pointer, kind uint8) *special {
  1690  	span := spanOfHeap(uintptr(p))
  1691  	if span == nil {
  1692  		throw("removespecial on invalid pointer")
  1693  	}
  1694  
  1695  	// Ensure that the span is swept.
  1696  	// Sweeping accesses the specials list w/o locks, so we have
  1697  	// to synchronize with it. And it's just much safer.
  1698  	mp := acquirem()
  1699  	span.ensureSwept()
  1700  
  1701  	offset := uintptr(p) - span.base()
  1702  
  1703  	lock(&span.speciallock)
  1704  	t := &span.specials
  1705  	for {
  1706  		s := *t
  1707  		if s == nil {
  1708  			break
  1709  		}
  1710  		// This function is used for finalizers only, so we don't check for
  1711  		// "interior" specials (p must be exactly equal to s->offset).
  1712  		if offset == uintptr(s.offset) && kind == s.kind {
  1713  			*t = s.next
  1714  			unlock(&span.speciallock)
  1715  			releasem(mp)
  1716  			return s
  1717  		}
  1718  		t = &s.next
  1719  	}
  1720  	unlock(&span.speciallock)
  1721  	releasem(mp)
  1722  	return nil
  1723  }
  1724  
  1725  // The described object has a finalizer set for it.
  1726  //
  1727  // specialfinalizer is allocated from non-GC'd memory, so any heap
  1728  // pointers must be specially handled.
  1729  //
  1730  //go:notinheap
  1731  type specialfinalizer struct {
  1732  	special special
  1733  	fn      *funcval // May be a heap pointer.
  1734  	nret    uintptr
  1735  	fint    *_type   // May be a heap pointer, but always live.
  1736  	ot      *ptrtype // May be a heap pointer, but always live.
  1737  }
  1738  
  1739  // Adds a finalizer to the object p. Returns true if it succeeded.
  1740  func addfinalizer(p unsafe.Pointer, f *funcval, nret uintptr, fint *_type, ot *ptrtype) bool {
  1741  	lock(&mheap_.speciallock)
  1742  	s := (*specialfinalizer)(mheap_.specialfinalizeralloc.alloc())
  1743  	unlock(&mheap_.speciallock)
  1744  	s.special.kind = _KindSpecialFinalizer
  1745  	s.fn = f
  1746  	s.nret = nret
  1747  	s.fint = fint
  1748  	s.ot = ot
  1749  	if addspecial(p, &s.special) {
  1750  		// This is responsible for maintaining the same
  1751  		// GC-related invariants as markrootSpans in any
  1752  		// situation where it's possible that markrootSpans
  1753  		// has already run but mark termination hasn't yet.
  1754  		if gcphase != _GCoff {
  1755  			base, _, _ := findObject(uintptr(p), 0, 0)
  1756  			mp := acquirem()
  1757  			gcw := &mp.p.ptr().gcw
  1758  			// Mark everything reachable from the object
  1759  			// so it's retained for the finalizer.
  1760  			scanobject(base, gcw)
  1761  			// Mark the finalizer itself, since the
  1762  			// special isn't part of the GC'd heap.
  1763  			scanblock(uintptr(unsafe.Pointer(&s.fn)), sys.PtrSize, &oneptrmask[0], gcw, nil)
  1764  			releasem(mp)
  1765  		}
  1766  		return true
  1767  	}
  1768  
  1769  	// There was an old finalizer
  1770  	lock(&mheap_.speciallock)
  1771  	mheap_.specialfinalizeralloc.free(unsafe.Pointer(s))
  1772  	unlock(&mheap_.speciallock)
  1773  	return false
  1774  }
  1775  
  1776  // Removes the finalizer (if any) from the object p.
  1777  func removefinalizer(p unsafe.Pointer) {
  1778  	s := (*specialfinalizer)(unsafe.Pointer(removespecial(p, _KindSpecialFinalizer)))
  1779  	if s == nil {
  1780  		return // there wasn't a finalizer to remove
  1781  	}
  1782  	lock(&mheap_.speciallock)
  1783  	mheap_.specialfinalizeralloc.free(unsafe.Pointer(s))
  1784  	unlock(&mheap_.speciallock)
  1785  }
  1786  
  1787  // The described object is being heap profiled.
  1788  //
  1789  //go:notinheap
  1790  type specialprofile struct {
  1791  	special special
  1792  	b       *bucket
  1793  }
  1794  
  1795  // Set the heap profile bucket associated with addr to b.
  1796  func setprofilebucket(p unsafe.Pointer, b *bucket) {
  1797  	lock(&mheap_.speciallock)
  1798  	s := (*specialprofile)(mheap_.specialprofilealloc.alloc())
  1799  	unlock(&mheap_.speciallock)
  1800  	s.special.kind = _KindSpecialProfile
  1801  	s.b = b
  1802  	if !addspecial(p, &s.special) {
  1803  		throw("setprofilebucket: profile already set")
  1804  	}
  1805  }
  1806  
  1807  // Do whatever cleanup needs to be done to deallocate s. It has
  1808  // already been unlinked from the mspan specials list.
  1809  func freespecial(s *special, p unsafe.Pointer, size uintptr) {
  1810  	switch s.kind {
  1811  	case _KindSpecialFinalizer:
  1812  		sf := (*specialfinalizer)(unsafe.Pointer(s))
  1813  		queuefinalizer(p, sf.fn, sf.nret, sf.fint, sf.ot)
  1814  		lock(&mheap_.speciallock)
  1815  		mheap_.specialfinalizeralloc.free(unsafe.Pointer(sf))
  1816  		unlock(&mheap_.speciallock)
  1817  	case _KindSpecialProfile:
  1818  		sp := (*specialprofile)(unsafe.Pointer(s))
  1819  		mProf_Free(sp.b, size)
  1820  		lock(&mheap_.speciallock)
  1821  		mheap_.specialprofilealloc.free(unsafe.Pointer(sp))
  1822  		unlock(&mheap_.speciallock)
  1823  	default:
  1824  		throw("bad special kind")
  1825  		panic("not reached")
  1826  	}
  1827  }
  1828  
  1829  // gcBits is an alloc/mark bitmap. This is always used as *gcBits.
  1830  //
  1831  //go:notinheap
  1832  type gcBits uint8
  1833  
  1834  // bytep returns a pointer to the n'th byte of b.
  1835  func (b *gcBits) bytep(n uintptr) *uint8 {
  1836  	return addb((*uint8)(b), n)
  1837  }
  1838  
  1839  // bitp returns a pointer to the byte containing bit n and a mask for
  1840  // selecting that bit from *bytep.
  1841  func (b *gcBits) bitp(n uintptr) (bytep *uint8, mask uint8) {
  1842  	return b.bytep(n / 8), 1 << (n % 8)
  1843  }
  1844  
  1845  const gcBitsChunkBytes = uintptr(64 << 10)
  1846  const gcBitsHeaderBytes = unsafe.Sizeof(gcBitsHeader{})
  1847  
  1848  type gcBitsHeader struct {
  1849  	free uintptr // free is the index into bits of the next free byte.
  1850  	next uintptr // *gcBits triggers recursive type bug. (issue 14620)
  1851  }
  1852  
  1853  //go:notinheap
  1854  type gcBitsArena struct {
  1855  	// gcBitsHeader // side step recursive type bug (issue 14620) by including fields by hand.
  1856  	free uintptr // free is the index into bits of the next free byte; read/write atomically
  1857  	next *gcBitsArena
  1858  	bits [gcBitsChunkBytes - gcBitsHeaderBytes]gcBits
  1859  }
  1860  
  1861  var gcBitsArenas struct {
  1862  	lock     mutex
  1863  	free     *gcBitsArena
  1864  	next     *gcBitsArena // Read atomically. Write atomically under lock.
  1865  	current  *gcBitsArena
  1866  	previous *gcBitsArena
  1867  }
  1868  
  1869  // tryAlloc allocates from b or returns nil if b does not have enough room.
  1870  // This is safe to call concurrently.
  1871  func (b *gcBitsArena) tryAlloc(bytes uintptr) *gcBits {
  1872  	if b == nil || atomic.Loaduintptr(&b.free)+bytes > uintptr(len(b.bits)) {
  1873  		return nil
  1874  	}
  1875  	// Try to allocate from this block.
  1876  	end := atomic.Xadduintptr(&b.free, bytes)
  1877  	if end > uintptr(len(b.bits)) {
  1878  		return nil
  1879  	}
  1880  	// There was enough room.
  1881  	start := end - bytes
  1882  	return &b.bits[start]
  1883  }
  1884  
  1885  // newMarkBits returns a pointer to 8 byte aligned bytes
  1886  // to be used for a span's mark bits.
  1887  func newMarkBits(nelems uintptr) *gcBits {
  1888  	blocksNeeded := uintptr((nelems + 63) / 64)
  1889  	bytesNeeded := blocksNeeded * 8
  1890  
  1891  	// Try directly allocating from the current head arena.
  1892  	head := (*gcBitsArena)(atomic.Loadp(unsafe.Pointer(&gcBitsArenas.next)))
  1893  	if p := head.tryAlloc(bytesNeeded); p != nil {
  1894  		return p
  1895  	}
  1896  
  1897  	// There's not enough room in the head arena. We may need to
  1898  	// allocate a new arena.
  1899  	lock(&gcBitsArenas.lock)
  1900  	// Try the head arena again, since it may have changed. Now
  1901  	// that we hold the lock, the list head can't change, but its
  1902  	// free position still can.
  1903  	if p := gcBitsArenas.next.tryAlloc(bytesNeeded); p != nil {
  1904  		unlock(&gcBitsArenas.lock)
  1905  		return p
  1906  	}
  1907  
  1908  	// Allocate a new arena. This may temporarily drop the lock.
  1909  	fresh := newArenaMayUnlock()
  1910  	// If newArenaMayUnlock dropped the lock, another thread may
  1911  	// have put a fresh arena on the "next" list. Try allocating
  1912  	// from next again.
  1913  	if p := gcBitsArenas.next.tryAlloc(bytesNeeded); p != nil {
  1914  		// Put fresh back on the free list.
  1915  		// TODO: Mark it "already zeroed"
  1916  		fresh.next = gcBitsArenas.free
  1917  		gcBitsArenas.free = fresh
  1918  		unlock(&gcBitsArenas.lock)
  1919  		return p
  1920  	}
  1921  
  1922  	// Allocate from the fresh arena. We haven't linked it in yet, so
  1923  	// this cannot race and is guaranteed to succeed.
  1924  	p := fresh.tryAlloc(bytesNeeded)
  1925  	if p == nil {
  1926  		throw("markBits overflow")
  1927  	}
  1928  
  1929  	// Add the fresh arena to the "next" list.
  1930  	fresh.next = gcBitsArenas.next
  1931  	atomic.StorepNoWB(unsafe.Pointer(&gcBitsArenas.next), unsafe.Pointer(fresh))
  1932  
  1933  	unlock(&gcBitsArenas.lock)
  1934  	return p
  1935  }
  1936  
  1937  // newAllocBits returns a pointer to 8 byte aligned bytes
  1938  // to be used for this span's alloc bits.
  1939  // newAllocBits is used to provide newly initialized spans
  1940  // allocation bits. For spans not being initialized the
  1941  // mark bits are repurposed as allocation bits when
  1942  // the span is swept.
  1943  func newAllocBits(nelems uintptr) *gcBits {
  1944  	return newMarkBits(nelems)
  1945  }
  1946  
  1947  // nextMarkBitArenaEpoch establishes a new epoch for the arenas
  1948  // holding the mark bits. The arenas are named relative to the
  1949  // current GC cycle which is demarcated by the call to finishweep_m.
  1950  //
  1951  // All current spans have been swept.
  1952  // During that sweep each span allocated room for its gcmarkBits in
  1953  // gcBitsArenas.next block. gcBitsArenas.next becomes the gcBitsArenas.current
  1954  // where the GC will mark objects and after each span is swept these bits
  1955  // will be used to allocate objects.
  1956  // gcBitsArenas.current becomes gcBitsArenas.previous where the span's
  1957  // gcAllocBits live until all the spans have been swept during this GC cycle.
  1958  // The span's sweep extinguishes all the references to gcBitsArenas.previous
  1959  // by pointing gcAllocBits into the gcBitsArenas.current.
  1960  // The gcBitsArenas.previous is released to the gcBitsArenas.free list.
  1961  func nextMarkBitArenaEpoch() {
  1962  	lock(&gcBitsArenas.lock)
  1963  	if gcBitsArenas.previous != nil {
  1964  		if gcBitsArenas.free == nil {
  1965  			gcBitsArenas.free = gcBitsArenas.previous
  1966  		} else {
  1967  			// Find end of previous arenas.
  1968  			last := gcBitsArenas.previous
  1969  			for last = gcBitsArenas.previous; last.next != nil; last = last.next {
  1970  			}
  1971  			last.next = gcBitsArenas.free
  1972  			gcBitsArenas.free = gcBitsArenas.previous
  1973  		}
  1974  	}
  1975  	gcBitsArenas.previous = gcBitsArenas.current
  1976  	gcBitsArenas.current = gcBitsArenas.next
  1977  	atomic.StorepNoWB(unsafe.Pointer(&gcBitsArenas.next), nil) // newMarkBits calls newArena when needed
  1978  	unlock(&gcBitsArenas.lock)
  1979  }
  1980  
  1981  // newArenaMayUnlock allocates and zeroes a gcBits arena.
  1982  // The caller must hold gcBitsArena.lock. This may temporarily release it.
  1983  func newArenaMayUnlock() *gcBitsArena {
  1984  	var result *gcBitsArena
  1985  	if gcBitsArenas.free == nil {
  1986  		unlock(&gcBitsArenas.lock)
  1987  		result = (*gcBitsArena)(sysAlloc(gcBitsChunkBytes, &memstats.gc_sys))
  1988  		if result == nil {
  1989  			throw("runtime: cannot allocate memory")
  1990  		}
  1991  		lock(&gcBitsArenas.lock)
  1992  	} else {
  1993  		result = gcBitsArenas.free
  1994  		gcBitsArenas.free = gcBitsArenas.free.next
  1995  		memclrNoHeapPointers(unsafe.Pointer(result), gcBitsChunkBytes)
  1996  	}
  1997  	result.next = nil
  1998  	// If result.bits is not 8 byte aligned adjust index so
  1999  	// that &result.bits[result.free] is 8 byte aligned.
  2000  	if uintptr(unsafe.Offsetof(gcBitsArena{}.bits))&7 == 0 {
  2001  		result.free = 0
  2002  	} else {
  2003  		result.free = 8 - (uintptr(unsafe.Pointer(&result.bits[0])) & 7)
  2004  	}
  2005  	return result
  2006  }
  2007  

View as plain text