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

View as plain text