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  	"runtime/internal/atomic"
    13  	"runtime/internal/sys"
    14  	"unsafe"
    15  )
    16  
    17  // minPhysPageSize is a lower-bound on the physical page size. The
    18  // true physical page size may be larger than this. In contrast,
    19  // sys.PhysPageSize is an upper-bound on the physical page size.
    20  const minPhysPageSize = 4096
    21  
    22  // Main malloc heap.
    23  // The heap itself is the "free[]" and "large" arrays,
    24  // but all the other global data is here too.
    25  //
    26  // mheap must not be heap-allocated because it contains mSpanLists,
    27  // which must not be heap-allocated.
    28  //
    29  //go:notinheap
    30  type mheap struct {
    31  	lock      mutex
    32  	free      [_MaxMHeapList]mSpanList // free lists of given length up to _MaxMHeapList
    33  	freelarge mTreap                   // free treap of length >= _MaxMHeapList
    34  	busy      [_MaxMHeapList]mSpanList // busy lists of large spans of given length
    35  	busylarge mSpanList                // busy lists of large spans length >= _MaxMHeapList
    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  	// spans is a lookup table to map virtual address page IDs to *mspan.
    54  	// For allocated spans, their pages map to the span itself.
    55  	// For free spans, only the lowest and highest pages map to the span itself.
    56  	// Internal pages map to an arbitrary span.
    57  	// For pages that have never been allocated, spans entries are nil.
    58  	//
    59  	// Modifications are protected by mheap.lock. Reads can be
    60  	// performed without locking, but ONLY from indexes that are
    61  	// known to contain in-use or stack spans. This means there
    62  	// must not be a safe-point between establishing that an
    63  	// address is live and looking it up in the spans array.
    64  	//
    65  	// This is backed by a reserved region of the address space so
    66  	// it can grow without moving. The memory up to len(spans) is
    67  	// mapped. cap(spans) indicates the total reserved memory.
    68  	spans []*mspan
    69  
    70  	// sweepSpans contains two mspan stacks: one of swept in-use
    71  	// spans, and one of unswept in-use spans. These two trade
    72  	// roles on each GC cycle. Since the sweepgen increases by 2
    73  	// on each cycle, this means the swept spans are in
    74  	// sweepSpans[sweepgen/2%2] and the unswept spans are in
    75  	// sweepSpans[1-sweepgen/2%2]. Sweeping pops spans from the
    76  	// unswept stack and pushes spans that are still in-use on the
    77  	// swept stack. Likewise, allocating an in-use span pushes it
    78  	// on the swept stack.
    79  	sweepSpans [2]gcSweepBuf
    80  
    81  	_ uint32 // align uint64 fields on 32-bit for atomics
    82  
    83  	// Proportional sweep
    84  	//
    85  	// These parameters represent a linear function from heap_live
    86  	// to page sweep count. The proportional sweep system works to
    87  	// stay in the black by keeping the current page sweep count
    88  	// above this line at the current heap_live.
    89  	//
    90  	// The line has slope sweepPagesPerByte and passes through a
    91  	// basis point at (sweepHeapLiveBasis, pagesSweptBasis). At
    92  	// any given time, the system is at (memstats.heap_live,
    93  	// pagesSwept) in this space.
    94  	//
    95  	// It's important that the line pass through a point we
    96  	// control rather than simply starting at a (0,0) origin
    97  	// because that lets us adjust sweep pacing at any time while
    98  	// accounting for current progress. If we could only adjust
    99  	// the slope, it would create a discontinuity in debt if any
   100  	// progress has already been made.
   101  	pagesInUse         uint64  // pages of spans in stats _MSpanInUse; R/W with mheap.lock
   102  	pagesSwept         uint64  // pages swept this cycle; updated atomically
   103  	pagesSweptBasis    uint64  // pagesSwept to use as the origin of the sweep ratio; updated atomically
   104  	sweepHeapLiveBasis uint64  // value of heap_live to use as the origin of sweep ratio; written with lock, read without
   105  	sweepPagesPerByte  float64 // proportional sweep ratio; written with lock, read without
   106  	// TODO(austin): pagesInUse should be a uintptr, but the 386
   107  	// compiler can't 8-byte align fields.
   108  
   109  	// Malloc stats.
   110  	largealloc  uint64                  // bytes allocated for large objects
   111  	nlargealloc uint64                  // number of large object allocations
   112  	largefree   uint64                  // bytes freed for large objects (>maxsmallsize)
   113  	nlargefree  uint64                  // number of frees for large objects (>maxsmallsize)
   114  	nsmallfree  [_NumSizeClasses]uint64 // number of frees for small objects (<=maxsmallsize)
   115  
   116  	// range of addresses we might see in the heap
   117  	bitmap        uintptr // Points to one byte past the end of the bitmap
   118  	bitmap_mapped uintptr
   119  
   120  	// The arena_* fields indicate the addresses of the Go heap.
   121  	//
   122  	// The maximum range of the Go heap is
   123  	// [arena_start, arena_start+_MaxMem+1).
   124  	//
   125  	// The range of the current Go heap is
   126  	// [arena_start, arena_used). Parts of this range may not be
   127  	// mapped, but the metadata structures are always mapped for
   128  	// the full range.
   129  	arena_start uintptr
   130  	arena_used  uintptr // Set with setArenaUsed.
   131  
   132  	// The heap is grown using a linear allocator that allocates
   133  	// from the block [arena_alloc, arena_end). arena_alloc is
   134  	// often, but *not always* equal to arena_used.
   135  	arena_alloc uintptr
   136  	arena_end   uintptr
   137  
   138  	// arena_reserved indicates that the memory [arena_alloc,
   139  	// arena_end) is reserved (e.g., mapped PROT_NONE). If this is
   140  	// false, we have to be careful not to clobber existing
   141  	// mappings here. If this is true, then we own the mapping
   142  	// here and *must* clobber it to use it.
   143  	arena_reserved bool
   144  
   145  	_ uint32 // ensure 64-bit alignment
   146  
   147  	// central free lists for small size classes.
   148  	// the padding makes sure that the MCentrals are
   149  	// spaced CacheLineSize bytes apart, so that each MCentral.lock
   150  	// gets its own cache line.
   151  	// central is indexed by spanClass.
   152  	central [numSpanClasses]struct {
   153  		mcentral mcentral
   154  		pad      [sys.CacheLineSize - unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
   155  	}
   156  
   157  	spanalloc             fixalloc // allocator for span*
   158  	cachealloc            fixalloc // allocator for mcache*
   159  	treapalloc            fixalloc // allocator for treapNodes* used by large objects
   160  	specialfinalizeralloc fixalloc // allocator for specialfinalizer*
   161  	specialprofilealloc   fixalloc // allocator for specialprofile*
   162  	speciallock           mutex    // lock for special record allocators.
   163  
   164  	unused *specialfinalizer // never set, just here to force the specialfinalizer type into DWARF
   165  }
   166  
   167  var mheap_ mheap
   168  
   169  // An MSpan is a run of pages.
   170  //
   171  // When a MSpan is in the heap free list, state == MSpanFree
   172  // and heapmap(s->start) == span, heapmap(s->start+s->npages-1) == span.
   173  //
   174  // When a MSpan is allocated, state == MSpanInUse or MSpanManual
   175  // and heapmap(i) == span for all s->start <= i < s->start+s->npages.
   176  
   177  // Every MSpan is in one doubly-linked list,
   178  // either one of the MHeap's free lists or one of the
   179  // MCentral's span lists.
   180  
   181  // An MSpan representing actual memory has state _MSpanInUse,
   182  // _MSpanManual, or _MSpanFree. Transitions between these states are
   183  // constrained as follows:
   184  //
   185  // * A span may transition from free to in-use or manual during any GC
   186  //   phase.
   187  //
   188  // * During sweeping (gcphase == _GCoff), a span may transition from
   189  //   in-use to free (as a result of sweeping) or manual to free (as a
   190  //   result of stacks being freed).
   191  //
   192  // * During GC (gcphase != _GCoff), a span *must not* transition from
   193  //   manual or in-use to free. Because concurrent GC may read a pointer
   194  //   and then look up its span, the span state must be monotonic.
   195  type mSpanState uint8
   196  
   197  const (
   198  	_MSpanDead   mSpanState = iota
   199  	_MSpanInUse             // allocated for garbage collected heap
   200  	_MSpanManual            // allocated for manual management (e.g., stack allocator)
   201  	_MSpanFree
   202  )
   203  
   204  // mSpanStateNames are the names of the span states, indexed by
   205  // mSpanState.
   206  var mSpanStateNames = []string{
   207  	"_MSpanDead",
   208  	"_MSpanInUse",
   209  	"_MSpanManual",
   210  	"_MSpanFree",
   211  }
   212  
   213  // mSpanList heads a linked list of spans.
   214  //
   215  //go:notinheap
   216  type mSpanList struct {
   217  	first *mspan // first span in list, or nil if none
   218  	last  *mspan // last span in list, or nil if none
   219  }
   220  
   221  //go:notinheap
   222  type mspan struct {
   223  	next *mspan     // next span in list, or nil if none
   224  	prev *mspan     // previous span in list, or nil if none
   225  	list *mSpanList // For debugging. TODO: Remove.
   226  
   227  	startAddr uintptr // address of first byte of span aka s.base()
   228  	npages    uintptr // number of pages in span
   229  
   230  	manualFreeList gclinkptr // list of free objects in _MSpanManual spans
   231  
   232  	// freeindex is the slot index between 0 and nelems at which to begin scanning
   233  	// for the next free object in this span.
   234  	// Each allocation scans allocBits starting at freeindex until it encounters a 0
   235  	// indicating a free object. freeindex is then adjusted so that subsequent scans begin
   236  	// just past the newly discovered free object.
   237  	//
   238  	// If freeindex == nelem, this span has no free objects.
   239  	//
   240  	// allocBits is a bitmap of objects in this span.
   241  	// If n >= freeindex and allocBits[n/8] & (1<<(n%8)) is 0
   242  	// then object n is free;
   243  	// otherwise, object n is allocated. Bits starting at nelem are
   244  	// undefined and should never be referenced.
   245  	//
   246  	// Object n starts at address n*elemsize + (start << pageShift).
   247  	freeindex uintptr
   248  	// TODO: Look up nelems from sizeclass and remove this field if it
   249  	// helps performance.
   250  	nelems uintptr // number of object in the span.
   251  
   252  	// Cache of the allocBits at freeindex. allocCache is shifted
   253  	// such that the lowest bit corresponds to the bit freeindex.
   254  	// allocCache holds the complement of allocBits, thus allowing
   255  	// ctz (count trailing zero) to use it directly.
   256  	// allocCache may contain bits beyond s.nelems; the caller must ignore
   257  	// these.
   258  	allocCache uint64
   259  
   260  	// allocBits and gcmarkBits hold pointers to a span's mark and
   261  	// allocation bits. The pointers are 8 byte aligned.
   262  	// There are three arenas where this data is held.
   263  	// free: Dirty arenas that are no longer accessed
   264  	//       and can be reused.
   265  	// next: Holds information to be used in the next GC cycle.
   266  	// current: Information being used during this GC cycle.
   267  	// previous: Information being used during the last GC cycle.
   268  	// A new GC cycle starts with the call to finishsweep_m.
   269  	// finishsweep_m moves the previous arena to the free arena,
   270  	// the current arena to the previous arena, and
   271  	// the next arena to the current arena.
   272  	// The next arena is populated as the spans request
   273  	// memory to hold gcmarkBits for the next GC cycle as well
   274  	// as allocBits for newly allocated spans.
   275  	//
   276  	// The pointer arithmetic is done "by hand" instead of using
   277  	// arrays to avoid bounds checks along critical performance
   278  	// paths.
   279  	// The sweep will free the old allocBits and set allocBits to the
   280  	// gcmarkBits. The gcmarkBits are replaced with a fresh zeroed
   281  	// out memory.
   282  	allocBits  *gcBits
   283  	gcmarkBits *gcBits
   284  
   285  	// sweep generation:
   286  	// if sweepgen == h->sweepgen - 2, the span needs sweeping
   287  	// if sweepgen == h->sweepgen - 1, the span is currently being swept
   288  	// if sweepgen == h->sweepgen, the span is swept and ready to use
   289  	// h->sweepgen is incremented by 2 after every GC
   290  
   291  	sweepgen    uint32
   292  	divMul      uint16     // for divide by elemsize - divMagic.mul
   293  	baseMask    uint16     // if non-0, elemsize is a power of 2, & this will get object allocation base
   294  	allocCount  uint16     // number of allocated objects
   295  	spanclass   spanClass  // size class and noscan (uint8)
   296  	incache     bool       // being used by an mcache
   297  	state       mSpanState // mspaninuse etc
   298  	needzero    uint8      // needs to be zeroed before allocation
   299  	divShift    uint8      // for divide by elemsize - divMagic.shift
   300  	divShift2   uint8      // for divide by elemsize - divMagic.shift2
   301  	elemsize    uintptr    // computed from sizeclass or from npages
   302  	unusedsince int64      // first time spotted by gc in mspanfree state
   303  	npreleased  uintptr    // number of pages released to the os
   304  	limit       uintptr    // end of data in span
   305  	speciallock mutex      // guards specials list
   306  	specials    *special   // linked list of special records sorted by offset.
   307  }
   308  
   309  func (s *mspan) base() uintptr {
   310  	return s.startAddr
   311  }
   312  
   313  func (s *mspan) layout() (size, n, total uintptr) {
   314  	total = s.npages << _PageShift
   315  	size = s.elemsize
   316  	if size > 0 {
   317  		n = total / size
   318  	}
   319  	return
   320  }
   321  
   322  // recordspan adds a newly allocated span to h.allspans.
   323  //
   324  // This only happens the first time a span is allocated from
   325  // mheap.spanalloc (it is not called when a span is reused).
   326  //
   327  // Write barriers are disallowed here because it can be called from
   328  // gcWork when allocating new workbufs. However, because it's an
   329  // indirect call from the fixalloc initializer, the compiler can't see
   330  // this.
   331  //
   332  //go:nowritebarrierrec
   333  func recordspan(vh unsafe.Pointer, p unsafe.Pointer) {
   334  	h := (*mheap)(vh)
   335  	s := (*mspan)(p)
   336  	if len(h.allspans) >= cap(h.allspans) {
   337  		n := 64 * 1024 / sys.PtrSize
   338  		if n < cap(h.allspans)*3/2 {
   339  			n = cap(h.allspans) * 3 / 2
   340  		}
   341  		var new []*mspan
   342  		sp := (*slice)(unsafe.Pointer(&new))
   343  		sp.array = sysAlloc(uintptr(n)*sys.PtrSize, &memstats.other_sys)
   344  		if sp.array == nil {
   345  			throw("runtime: cannot allocate memory")
   346  		}
   347  		sp.len = len(h.allspans)
   348  		sp.cap = n
   349  		if len(h.allspans) > 0 {
   350  			copy(new, h.allspans)
   351  		}
   352  		oldAllspans := h.allspans
   353  		*(*notInHeapSlice)(unsafe.Pointer(&h.allspans)) = *(*notInHeapSlice)(unsafe.Pointer(&new))
   354  		if len(oldAllspans) != 0 {
   355  			sysFree(unsafe.Pointer(&oldAllspans[0]), uintptr(cap(oldAllspans))*unsafe.Sizeof(oldAllspans[0]), &memstats.other_sys)
   356  		}
   357  	}
   358  	h.allspans = h.allspans[:len(h.allspans)+1]
   359  	h.allspans[len(h.allspans)-1] = s
   360  }
   361  
   362  // A spanClass represents the size class and noscan-ness of a span.
   363  //
   364  // Each size class has a noscan spanClass and a scan spanClass. The
   365  // noscan spanClass contains only noscan objects, which do not contain
   366  // pointers and thus do not need to be scanned by the garbage
   367  // collector.
   368  type spanClass uint8
   369  
   370  const (
   371  	numSpanClasses = _NumSizeClasses << 1
   372  	tinySpanClass  = spanClass(tinySizeClass<<1 | 1)
   373  )
   374  
   375  func makeSpanClass(sizeclass uint8, noscan bool) spanClass {
   376  	return spanClass(sizeclass<<1) | spanClass(bool2int(noscan))
   377  }
   378  
   379  func (sc spanClass) sizeclass() int8 {
   380  	return int8(sc >> 1)
   381  }
   382  
   383  func (sc spanClass) noscan() bool {
   384  	return sc&1 != 0
   385  }
   386  
   387  // inheap reports whether b is a pointer into a (potentially dead) heap object.
   388  // It returns false for pointers into _MSpanManual spans.
   389  // Non-preemptible because it is used by write barriers.
   390  //go:nowritebarrier
   391  //go:nosplit
   392  func inheap(b uintptr) bool {
   393  	if b == 0 || b < mheap_.arena_start || b >= mheap_.arena_used {
   394  		return false
   395  	}
   396  	// Not a beginning of a block, consult span table to find the block beginning.
   397  	s := mheap_.spans[(b-mheap_.arena_start)>>_PageShift]
   398  	if s == nil || b < s.base() || b >= s.limit || s.state != mSpanInUse {
   399  		return false
   400  	}
   401  	return true
   402  }
   403  
   404  // inHeapOrStack is a variant of inheap that returns true for pointers
   405  // into any allocated heap span.
   406  //
   407  //go:nowritebarrier
   408  //go:nosplit
   409  func inHeapOrStack(b uintptr) bool {
   410  	if b == 0 || b < mheap_.arena_start || b >= mheap_.arena_used {
   411  		return false
   412  	}
   413  	// Not a beginning of a block, consult span table to find the block beginning.
   414  	s := mheap_.spans[(b-mheap_.arena_start)>>_PageShift]
   415  	if s == nil || b < s.base() {
   416  		return false
   417  	}
   418  	switch s.state {
   419  	case mSpanInUse, _MSpanManual:
   420  		return b < s.limit
   421  	default:
   422  		return false
   423  	}
   424  }
   425  
   426  // TODO: spanOf and spanOfUnchecked are open-coded in a lot of places.
   427  // Use the functions instead.
   428  
   429  // spanOf returns the span of p. If p does not point into the heap or
   430  // no span contains p, spanOf returns nil.
   431  func spanOf(p uintptr) *mspan {
   432  	if p == 0 || p < mheap_.arena_start || p >= mheap_.arena_used {
   433  		return nil
   434  	}
   435  	return spanOfUnchecked(p)
   436  }
   437  
   438  // spanOfUnchecked is equivalent to spanOf, but the caller must ensure
   439  // that p points into the heap (that is, mheap_.arena_start <= p <
   440  // mheap_.arena_used).
   441  func spanOfUnchecked(p uintptr) *mspan {
   442  	return mheap_.spans[(p-mheap_.arena_start)>>_PageShift]
   443  }
   444  
   445  func mlookup(v uintptr, base *uintptr, size *uintptr, sp **mspan) int32 {
   446  	_g_ := getg()
   447  
   448  	_g_.m.mcache.local_nlookup++
   449  	if sys.PtrSize == 4 && _g_.m.mcache.local_nlookup >= 1<<30 {
   450  		// purge cache stats to prevent overflow
   451  		lock(&mheap_.lock)
   452  		purgecachedstats(_g_.m.mcache)
   453  		unlock(&mheap_.lock)
   454  	}
   455  
   456  	s := mheap_.lookupMaybe(unsafe.Pointer(v))
   457  	if sp != nil {
   458  		*sp = s
   459  	}
   460  	if s == nil {
   461  		if base != nil {
   462  			*base = 0
   463  		}
   464  		if size != nil {
   465  			*size = 0
   466  		}
   467  		return 0
   468  	}
   469  
   470  	p := s.base()
   471  	if s.spanclass.sizeclass() == 0 {
   472  		// Large object.
   473  		if base != nil {
   474  			*base = p
   475  		}
   476  		if size != nil {
   477  			*size = s.npages << _PageShift
   478  		}
   479  		return 1
   480  	}
   481  
   482  	n := s.elemsize
   483  	if base != nil {
   484  		i := (v - p) / n
   485  		*base = p + i*n
   486  	}
   487  	if size != nil {
   488  		*size = n
   489  	}
   490  
   491  	return 1
   492  }
   493  
   494  // Initialize the heap.
   495  func (h *mheap) init(spansStart, spansBytes uintptr) {
   496  	h.treapalloc.init(unsafe.Sizeof(treapNode{}), nil, nil, &memstats.other_sys)
   497  	h.spanalloc.init(unsafe.Sizeof(mspan{}), recordspan, unsafe.Pointer(h), &memstats.mspan_sys)
   498  	h.cachealloc.init(unsafe.Sizeof(mcache{}), nil, nil, &memstats.mcache_sys)
   499  	h.specialfinalizeralloc.init(unsafe.Sizeof(specialfinalizer{}), nil, nil, &memstats.other_sys)
   500  	h.specialprofilealloc.init(unsafe.Sizeof(specialprofile{}), nil, nil, &memstats.other_sys)
   501  
   502  	// Don't zero mspan allocations. Background sweeping can
   503  	// inspect a span concurrently with allocating it, so it's
   504  	// important that the span's sweepgen survive across freeing
   505  	// and re-allocating a span to prevent background sweeping
   506  	// from improperly cas'ing it from 0.
   507  	//
   508  	// This is safe because mspan contains no heap pointers.
   509  	h.spanalloc.zero = false
   510  
   511  	// h->mapcache needs no init
   512  	for i := range h.free {
   513  		h.free[i].init()
   514  		h.busy[i].init()
   515  	}
   516  
   517  	h.busylarge.init()
   518  	for i := range h.central {
   519  		h.central[i].mcentral.init(spanClass(i))
   520  	}
   521  
   522  	sp := (*slice)(unsafe.Pointer(&h.spans))
   523  	sp.array = unsafe.Pointer(spansStart)
   524  	sp.len = 0
   525  	sp.cap = int(spansBytes / sys.PtrSize)
   526  
   527  	// Map metadata structures. But don't map race detector memory
   528  	// since we're not actually growing the arena here (and TSAN
   529  	// gets mad if you map 0 bytes).
   530  	h.setArenaUsed(h.arena_used, false)
   531  }
   532  
   533  // setArenaUsed extends the usable arena to address arena_used and
   534  // maps auxiliary VM regions for any newly usable arena space.
   535  //
   536  // racemap indicates that this memory should be managed by the race
   537  // detector. racemap should be true unless this is covering a VM hole.
   538  func (h *mheap) setArenaUsed(arena_used uintptr, racemap bool) {
   539  	// Map auxiliary structures *before* h.arena_used is updated.
   540  	// Waiting to update arena_used until after the memory has been mapped
   541  	// avoids faults when other threads try access these regions immediately
   542  	// after observing the change to arena_used.
   543  
   544  	// Map the bitmap.
   545  	h.mapBits(arena_used)
   546  
   547  	// Map spans array.
   548  	h.mapSpans(arena_used)
   549  
   550  	// Tell the race detector about the new heap memory.
   551  	if racemap && raceenabled {
   552  		racemapshadow(unsafe.Pointer(h.arena_used), arena_used-h.arena_used)
   553  	}
   554  
   555  	h.arena_used = arena_used
   556  }
   557  
   558  // mapSpans makes sure that the spans are mapped
   559  // up to the new value of arena_used.
   560  //
   561  // Don't call this directly. Call mheap.setArenaUsed.
   562  func (h *mheap) mapSpans(arena_used uintptr) {
   563  	// Map spans array, PageSize at a time.
   564  	n := arena_used
   565  	n -= h.arena_start
   566  	n = n / _PageSize * sys.PtrSize
   567  	n = round(n, physPageSize)
   568  	need := n / unsafe.Sizeof(h.spans[0])
   569  	have := uintptr(len(h.spans))
   570  	if have >= need {
   571  		return
   572  	}
   573  	h.spans = h.spans[:need]
   574  	sysMap(unsafe.Pointer(&h.spans[have]), (need-have)*unsafe.Sizeof(h.spans[0]), h.arena_reserved, &memstats.other_sys)
   575  }
   576  
   577  // Sweeps spans in list until reclaims at least npages into heap.
   578  // Returns the actual number of pages reclaimed.
   579  func (h *mheap) reclaimList(list *mSpanList, npages uintptr) uintptr {
   580  	n := uintptr(0)
   581  	sg := mheap_.sweepgen
   582  retry:
   583  	for s := list.first; s != nil; s = s.next {
   584  		if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
   585  			list.remove(s)
   586  			// swept spans are at the end of the list
   587  			list.insertBack(s) // Puts it back on a busy list. s is not in the treap at this point.
   588  			unlock(&h.lock)
   589  			snpages := s.npages
   590  			if s.sweep(false) {
   591  				n += snpages
   592  			}
   593  			lock(&h.lock)
   594  			if n >= npages {
   595  				return n
   596  			}
   597  			// the span could have been moved elsewhere
   598  			goto retry
   599  		}
   600  		if s.sweepgen == sg-1 {
   601  			// the span is being sweept by background sweeper, skip
   602  			continue
   603  		}
   604  		// already swept empty span,
   605  		// all subsequent ones must also be either swept or in process of sweeping
   606  		break
   607  	}
   608  	return n
   609  }
   610  
   611  // Sweeps and reclaims at least npage pages into heap.
   612  // Called before allocating npage pages.
   613  func (h *mheap) reclaim(npage uintptr) {
   614  	// First try to sweep busy spans with large objects of size >= npage,
   615  	// this has good chances of reclaiming the necessary space.
   616  	for i := int(npage); i < len(h.busy); i++ {
   617  		if h.reclaimList(&h.busy[i], npage) != 0 {
   618  			return // Bingo!
   619  		}
   620  	}
   621  
   622  	// Then -- even larger objects.
   623  	if h.reclaimList(&h.busylarge, npage) != 0 {
   624  		return // Bingo!
   625  	}
   626  
   627  	// Now try smaller objects.
   628  	// One such object is not enough, so we need to reclaim several of them.
   629  	reclaimed := uintptr(0)
   630  	for i := 0; i < int(npage) && i < len(h.busy); i++ {
   631  		reclaimed += h.reclaimList(&h.busy[i], npage-reclaimed)
   632  		if reclaimed >= npage {
   633  			return
   634  		}
   635  	}
   636  
   637  	// Now sweep everything that is not yet swept.
   638  	unlock(&h.lock)
   639  	for {
   640  		n := sweepone()
   641  		if n == ^uintptr(0) { // all spans are swept
   642  			break
   643  		}
   644  		reclaimed += n
   645  		if reclaimed >= npage {
   646  			break
   647  		}
   648  	}
   649  	lock(&h.lock)
   650  }
   651  
   652  // Allocate a new span of npage pages from the heap for GC'd memory
   653  // and record its size class in the HeapMap and HeapMapCache.
   654  func (h *mheap) alloc_m(npage uintptr, spanclass spanClass, large bool) *mspan {
   655  	_g_ := getg()
   656  	if _g_ != _g_.m.g0 {
   657  		throw("_mheap_alloc not on g0 stack")
   658  	}
   659  	lock(&h.lock)
   660  
   661  	// To prevent excessive heap growth, before allocating n pages
   662  	// we need to sweep and reclaim at least n pages.
   663  	if h.sweepdone == 0 {
   664  		// TODO(austin): This tends to sweep a large number of
   665  		// spans in order to find a few completely free spans
   666  		// (for example, in the garbage benchmark, this sweeps
   667  		// ~30x the number of pages its trying to allocate).
   668  		// If GC kept a bit for whether there were any marks
   669  		// in a span, we could release these free spans
   670  		// at the end of GC and eliminate this entirely.
   671  		if trace.enabled {
   672  			traceGCSweepStart()
   673  		}
   674  		h.reclaim(npage)
   675  		if trace.enabled {
   676  			traceGCSweepDone()
   677  		}
   678  	}
   679  
   680  	// transfer stats from cache to global
   681  	memstats.heap_scan += uint64(_g_.m.mcache.local_scan)
   682  	_g_.m.mcache.local_scan = 0
   683  	memstats.tinyallocs += uint64(_g_.m.mcache.local_tinyallocs)
   684  	_g_.m.mcache.local_tinyallocs = 0
   685  
   686  	s := h.allocSpanLocked(npage, &memstats.heap_inuse)
   687  	if s != nil {
   688  		// Record span info, because gc needs to be
   689  		// able to map interior pointer to containing span.
   690  		atomic.Store(&s.sweepgen, h.sweepgen)
   691  		h.sweepSpans[h.sweepgen/2%2].push(s) // Add to swept in-use list.
   692  		s.state = _MSpanInUse
   693  		s.allocCount = 0
   694  		s.spanclass = spanclass
   695  		if sizeclass := spanclass.sizeclass(); sizeclass == 0 {
   696  			s.elemsize = s.npages << _PageShift
   697  			s.divShift = 0
   698  			s.divMul = 0
   699  			s.divShift2 = 0
   700  			s.baseMask = 0
   701  		} else {
   702  			s.elemsize = uintptr(class_to_size[sizeclass])
   703  			m := &class_to_divmagic[sizeclass]
   704  			s.divShift = m.shift
   705  			s.divMul = m.mul
   706  			s.divShift2 = m.shift2
   707  			s.baseMask = m.baseMask
   708  		}
   709  
   710  		// update stats, sweep lists
   711  		h.pagesInUse += uint64(npage)
   712  		if large {
   713  			memstats.heap_objects++
   714  			mheap_.largealloc += uint64(s.elemsize)
   715  			mheap_.nlargealloc++
   716  			atomic.Xadd64(&memstats.heap_live, int64(npage<<_PageShift))
   717  			// Swept spans are at the end of lists.
   718  			if s.npages < uintptr(len(h.busy)) {
   719  				h.busy[s.npages].insertBack(s)
   720  			} else {
   721  				h.busylarge.insertBack(s)
   722  			}
   723  		}
   724  	}
   725  	// heap_scan and heap_live were updated.
   726  	if gcBlackenEnabled != 0 {
   727  		gcController.revise()
   728  	}
   729  
   730  	if trace.enabled {
   731  		traceHeapAlloc()
   732  	}
   733  
   734  	// h.spans is accessed concurrently without synchronization
   735  	// from other threads. Hence, there must be a store/store
   736  	// barrier here to ensure the writes to h.spans above happen
   737  	// before the caller can publish a pointer p to an object
   738  	// allocated from s. As soon as this happens, the garbage
   739  	// collector running on another processor could read p and
   740  	// look up s in h.spans. The unlock acts as the barrier to
   741  	// order these writes. On the read side, the data dependency
   742  	// between p and the index in h.spans orders the reads.
   743  	unlock(&h.lock)
   744  	return s
   745  }
   746  
   747  func (h *mheap) alloc(npage uintptr, spanclass spanClass, large bool, needzero bool) *mspan {
   748  	// Don't do any operations that lock the heap on the G stack.
   749  	// It might trigger stack growth, and the stack growth code needs
   750  	// to be able to allocate heap.
   751  	var s *mspan
   752  	systemstack(func() {
   753  		s = h.alloc_m(npage, spanclass, large)
   754  	})
   755  
   756  	if s != nil {
   757  		if needzero && s.needzero != 0 {
   758  			memclrNoHeapPointers(unsafe.Pointer(s.base()), s.npages<<_PageShift)
   759  		}
   760  		s.needzero = 0
   761  	}
   762  	return s
   763  }
   764  
   765  // allocManual allocates a manually-managed span of npage pages.
   766  // allocManual returns nil if allocation fails.
   767  //
   768  // allocManual adds the bytes used to *stat, which should be a
   769  // memstats in-use field. Unlike allocations in the GC'd heap, the
   770  // allocation does *not* count toward heap_inuse or heap_sys.
   771  //
   772  // The memory backing the returned span may not be zeroed if
   773  // span.needzero is set.
   774  //
   775  // allocManual must be called on the system stack to prevent stack
   776  // growth. Since this is used by the stack allocator, stack growth
   777  // during allocManual would self-deadlock.
   778  //
   779  //go:systemstack
   780  func (h *mheap) allocManual(npage uintptr, stat *uint64) *mspan {
   781  	lock(&h.lock)
   782  	s := h.allocSpanLocked(npage, stat)
   783  	if s != nil {
   784  		s.state = _MSpanManual
   785  		s.manualFreeList = 0
   786  		s.allocCount = 0
   787  		s.spanclass = 0
   788  		s.nelems = 0
   789  		s.elemsize = 0
   790  		s.limit = s.base() + s.npages<<_PageShift
   791  		// Manually manged memory doesn't count toward heap_sys.
   792  		memstats.heap_sys -= uint64(s.npages << _PageShift)
   793  	}
   794  
   795  	// This unlock acts as a release barrier. See mheap.alloc_m.
   796  	unlock(&h.lock)
   797  
   798  	return s
   799  }
   800  
   801  // Allocates a span of the given size.  h must be locked.
   802  // The returned span has been removed from the
   803  // free list, but its state is still MSpanFree.
   804  func (h *mheap) allocSpanLocked(npage uintptr, stat *uint64) *mspan {
   805  	var list *mSpanList
   806  	var s *mspan
   807  
   808  	// Try in fixed-size lists up to max.
   809  	for i := int(npage); i < len(h.free); i++ {
   810  		list = &h.free[i]
   811  		if !list.isEmpty() {
   812  			s = list.first
   813  			list.remove(s)
   814  			goto HaveSpan
   815  		}
   816  	}
   817  	// Best fit in list of large spans.
   818  	s = h.allocLarge(npage) // allocLarge removed s from h.freelarge for us
   819  	if s == nil {
   820  		if !h.grow(npage) {
   821  			return nil
   822  		}
   823  		s = h.allocLarge(npage)
   824  		if s == nil {
   825  			return nil
   826  		}
   827  	}
   828  
   829  HaveSpan:
   830  	// Mark span in use.
   831  	if s.state != _MSpanFree {
   832  		throw("MHeap_AllocLocked - MSpan not free")
   833  	}
   834  	if s.npages < npage {
   835  		throw("MHeap_AllocLocked - bad npages")
   836  	}
   837  	if s.npreleased > 0 {
   838  		sysUsed(unsafe.Pointer(s.base()), s.npages<<_PageShift)
   839  		memstats.heap_released -= uint64(s.npreleased << _PageShift)
   840  		s.npreleased = 0
   841  	}
   842  
   843  	if s.npages > npage {
   844  		// Trim extra and put it back in the heap.
   845  		t := (*mspan)(h.spanalloc.alloc())
   846  		t.init(s.base()+npage<<_PageShift, s.npages-npage)
   847  		s.npages = npage
   848  		p := (t.base() - h.arena_start) >> _PageShift
   849  		if p > 0 {
   850  			h.spans[p-1] = s
   851  		}
   852  		h.spans[p] = t
   853  		h.spans[p+t.npages-1] = t
   854  		t.needzero = s.needzero
   855  		s.state = _MSpanManual // prevent coalescing with s
   856  		t.state = _MSpanManual
   857  		h.freeSpanLocked(t, false, false, s.unusedsince)
   858  		s.state = _MSpanFree
   859  	}
   860  	s.unusedsince = 0
   861  
   862  	p := (s.base() - h.arena_start) >> _PageShift
   863  	for n := uintptr(0); n < npage; n++ {
   864  		h.spans[p+n] = s
   865  	}
   866  
   867  	*stat += uint64(npage << _PageShift)
   868  	memstats.heap_idle -= uint64(npage << _PageShift)
   869  
   870  	//println("spanalloc", hex(s.start<<_PageShift))
   871  	if s.inList() {
   872  		throw("still in list")
   873  	}
   874  	return s
   875  }
   876  
   877  // Large spans have a minimum size of 1MByte. The maximum number of large spans to support
   878  // 1TBytes is 1 million, experimentation using random sizes indicates that the depth of
   879  // the tree is less that 2x that of a perfectly balanced tree. For 1TByte can be referenced
   880  // by a perfectly balanced tree with a depth of 20. Twice that is an acceptable 40.
   881  func (h *mheap) isLargeSpan(npages uintptr) bool {
   882  	return npages >= uintptr(len(h.free))
   883  }
   884  
   885  // allocLarge allocates a span of at least npage pages from the treap of large spans.
   886  // Returns nil if no such span currently exists.
   887  func (h *mheap) allocLarge(npage uintptr) *mspan {
   888  	// Search treap for smallest span with >= npage pages.
   889  	return h.freelarge.remove(npage)
   890  }
   891  
   892  // Try to add at least npage pages of memory to the heap,
   893  // returning whether it worked.
   894  //
   895  // h must be locked.
   896  func (h *mheap) grow(npage uintptr) bool {
   897  	// Ask for a big chunk, to reduce the number of mappings
   898  	// the operating system needs to track; also amortizes
   899  	// the overhead of an operating system mapping.
   900  	// Allocate a multiple of 64kB.
   901  	npage = round(npage, (64<<10)/_PageSize)
   902  	ask := npage << _PageShift
   903  	if ask < _HeapAllocChunk {
   904  		ask = _HeapAllocChunk
   905  	}
   906  
   907  	v := h.sysAlloc(ask)
   908  	if v == nil {
   909  		if ask > npage<<_PageShift {
   910  			ask = npage << _PageShift
   911  			v = h.sysAlloc(ask)
   912  		}
   913  		if v == nil {
   914  			print("runtime: out of memory: cannot allocate ", ask, "-byte block (", memstats.heap_sys, " in use)\n")
   915  			return false
   916  		}
   917  	}
   918  
   919  	// Create a fake "in use" span and free it, so that the
   920  	// right coalescing happens.
   921  	s := (*mspan)(h.spanalloc.alloc())
   922  	s.init(uintptr(v), ask>>_PageShift)
   923  	p := (s.base() - h.arena_start) >> _PageShift
   924  	for i := p; i < p+s.npages; i++ {
   925  		h.spans[i] = s
   926  	}
   927  	atomic.Store(&s.sweepgen, h.sweepgen)
   928  	s.state = _MSpanInUse
   929  	h.pagesInUse += uint64(s.npages)
   930  	h.freeSpanLocked(s, false, true, 0)
   931  	return true
   932  }
   933  
   934  // Look up the span at the given address.
   935  // Address is guaranteed to be in map
   936  // and is guaranteed to be start or end of span.
   937  func (h *mheap) lookup(v unsafe.Pointer) *mspan {
   938  	p := uintptr(v)
   939  	p -= h.arena_start
   940  	return h.spans[p>>_PageShift]
   941  }
   942  
   943  // Look up the span at the given address.
   944  // Address is *not* guaranteed to be in map
   945  // and may be anywhere in the span.
   946  // Map entries for the middle of a span are only
   947  // valid for allocated spans. Free spans may have
   948  // other garbage in their middles, so we have to
   949  // check for that.
   950  func (h *mheap) lookupMaybe(v unsafe.Pointer) *mspan {
   951  	if uintptr(v) < h.arena_start || uintptr(v) >= h.arena_used {
   952  		return nil
   953  	}
   954  	s := h.spans[(uintptr(v)-h.arena_start)>>_PageShift]
   955  	if s == nil || uintptr(v) < s.base() || uintptr(v) >= uintptr(unsafe.Pointer(s.limit)) || s.state != _MSpanInUse {
   956  		return nil
   957  	}
   958  	return s
   959  }
   960  
   961  // Free the span back into the heap.
   962  func (h *mheap) freeSpan(s *mspan, acct int32) {
   963  	systemstack(func() {
   964  		mp := getg().m
   965  		lock(&h.lock)
   966  		memstats.heap_scan += uint64(mp.mcache.local_scan)
   967  		mp.mcache.local_scan = 0
   968  		memstats.tinyallocs += uint64(mp.mcache.local_tinyallocs)
   969  		mp.mcache.local_tinyallocs = 0
   970  		if msanenabled {
   971  			// Tell msan that this entire span is no longer in use.
   972  			base := unsafe.Pointer(s.base())
   973  			bytes := s.npages << _PageShift
   974  			msanfree(base, bytes)
   975  		}
   976  		if acct != 0 {
   977  			memstats.heap_objects--
   978  		}
   979  		if gcBlackenEnabled != 0 {
   980  			// heap_scan changed.
   981  			gcController.revise()
   982  		}
   983  		h.freeSpanLocked(s, true, true, 0)
   984  		unlock(&h.lock)
   985  	})
   986  }
   987  
   988  // freeManual frees a manually-managed span returned by allocManual.
   989  // stat must be the same as the stat passed to the allocManual that
   990  // allocated s.
   991  //
   992  // This must only be called when gcphase == _GCoff. See mSpanState for
   993  // an explanation.
   994  //
   995  // freeManual must be called on the system stack to prevent stack
   996  // growth, just like allocManual.
   997  //
   998  //go:systemstack
   999  func (h *mheap) freeManual(s *mspan, stat *uint64) {
  1000  	s.needzero = 1
  1001  	lock(&h.lock)
  1002  	*stat -= uint64(s.npages << _PageShift)
  1003  	memstats.heap_sys += uint64(s.npages << _PageShift)
  1004  	h.freeSpanLocked(s, false, true, 0)
  1005  	unlock(&h.lock)
  1006  }
  1007  
  1008  // s must be on a busy list (h.busy or h.busylarge) or unlinked.
  1009  func (h *mheap) freeSpanLocked(s *mspan, acctinuse, acctidle bool, unusedsince int64) {
  1010  	switch s.state {
  1011  	case _MSpanManual:
  1012  		if s.allocCount != 0 {
  1013  			throw("MHeap_FreeSpanLocked - invalid stack free")
  1014  		}
  1015  	case _MSpanInUse:
  1016  		if s.allocCount != 0 || s.sweepgen != h.sweepgen {
  1017  			print("MHeap_FreeSpanLocked - span ", s, " ptr ", hex(s.base()), " allocCount ", s.allocCount, " sweepgen ", s.sweepgen, "/", h.sweepgen, "\n")
  1018  			throw("MHeap_FreeSpanLocked - invalid free")
  1019  		}
  1020  		h.pagesInUse -= uint64(s.npages)
  1021  	default:
  1022  		throw("MHeap_FreeSpanLocked - invalid span state")
  1023  	}
  1024  
  1025  	if acctinuse {
  1026  		memstats.heap_inuse -= uint64(s.npages << _PageShift)
  1027  	}
  1028  	if acctidle {
  1029  		memstats.heap_idle += uint64(s.npages << _PageShift)
  1030  	}
  1031  	s.state = _MSpanFree
  1032  	if s.inList() {
  1033  		h.busyList(s.npages).remove(s)
  1034  	}
  1035  
  1036  	// Stamp newly unused spans. The scavenger will use that
  1037  	// info to potentially give back some pages to the OS.
  1038  	s.unusedsince = unusedsince
  1039  	if unusedsince == 0 {
  1040  		s.unusedsince = nanotime()
  1041  	}
  1042  	s.npreleased = 0
  1043  
  1044  	// Coalesce with earlier, later spans.
  1045  	p := (s.base() - h.arena_start) >> _PageShift
  1046  	if p > 0 {
  1047  		before := h.spans[p-1]
  1048  		if before != nil && before.state == _MSpanFree {
  1049  			// Now adjust s.
  1050  			s.startAddr = before.startAddr
  1051  			s.npages += before.npages
  1052  			s.npreleased = before.npreleased // absorb released pages
  1053  			s.needzero |= before.needzero
  1054  			p -= before.npages
  1055  			h.spans[p] = s
  1056  			// The size is potentially changing so the treap needs to delete adjacent nodes and
  1057  			// insert back as a combined node.
  1058  			if h.isLargeSpan(before.npages) {
  1059  				// We have a t, it is large so it has to be in the treap so we can remove it.
  1060  				h.freelarge.removeSpan(before)
  1061  			} else {
  1062  				h.freeList(before.npages).remove(before)
  1063  			}
  1064  			before.state = _MSpanDead
  1065  			h.spanalloc.free(unsafe.Pointer(before))
  1066  		}
  1067  	}
  1068  
  1069  	// Now check to see if next (greater addresses) span is free and can be coalesced.
  1070  	if (p + s.npages) < uintptr(len(h.spans)) {
  1071  		after := h.spans[p+s.npages]
  1072  		if after != nil && after.state == _MSpanFree {
  1073  			s.npages += after.npages
  1074  			s.npreleased += after.npreleased
  1075  			s.needzero |= after.needzero
  1076  			h.spans[p+s.npages-1] = s
  1077  			if h.isLargeSpan(after.npages) {
  1078  				h.freelarge.removeSpan(after)
  1079  			} else {
  1080  				h.freeList(after.npages).remove(after)
  1081  			}
  1082  			after.state = _MSpanDead
  1083  			h.spanalloc.free(unsafe.Pointer(after))
  1084  		}
  1085  	}
  1086  
  1087  	// Insert s into appropriate list or treap.
  1088  	if h.isLargeSpan(s.npages) {
  1089  		h.freelarge.insert(s)
  1090  	} else {
  1091  		h.freeList(s.npages).insert(s)
  1092  	}
  1093  }
  1094  
  1095  func (h *mheap) freeList(npages uintptr) *mSpanList {
  1096  	return &h.free[npages]
  1097  }
  1098  
  1099  func (h *mheap) busyList(npages uintptr) *mSpanList {
  1100  	if npages < uintptr(len(h.busy)) {
  1101  		return &h.busy[npages]
  1102  	}
  1103  	return &h.busylarge
  1104  }
  1105  
  1106  func scavengeTreapNode(t *treapNode, now, limit uint64) uintptr {
  1107  	s := t.spanKey
  1108  	var sumreleased uintptr
  1109  	if (now-uint64(s.unusedsince)) > limit && s.npreleased != s.npages {
  1110  		start := s.base()
  1111  		end := start + s.npages<<_PageShift
  1112  		if physPageSize > _PageSize {
  1113  			// We can only release pages in
  1114  			// physPageSize blocks, so round start
  1115  			// and end in. (Otherwise, madvise
  1116  			// will round them *out* and release
  1117  			// more memory than we want.)
  1118  			start = (start + physPageSize - 1) &^ (physPageSize - 1)
  1119  			end &^= physPageSize - 1
  1120  			if end <= start {
  1121  				// start and end don't span a
  1122  				// whole physical page.
  1123  				return sumreleased
  1124  			}
  1125  		}
  1126  		len := end - start
  1127  		released := len - (s.npreleased << _PageShift)
  1128  		if physPageSize > _PageSize && released == 0 {
  1129  			return sumreleased
  1130  		}
  1131  		memstats.heap_released += uint64(released)
  1132  		sumreleased += released
  1133  		s.npreleased = len >> _PageShift
  1134  		sysUnused(unsafe.Pointer(start), len)
  1135  	}
  1136  	return sumreleased
  1137  }
  1138  
  1139  func scavengelist(list *mSpanList, now, limit uint64) uintptr {
  1140  	if list.isEmpty() {
  1141  		return 0
  1142  	}
  1143  
  1144  	var sumreleased uintptr
  1145  	for s := list.first; s != nil; s = s.next {
  1146  		if (now-uint64(s.unusedsince)) <= limit || s.npreleased == s.npages {
  1147  			continue
  1148  		}
  1149  		start := s.base()
  1150  		end := start + s.npages<<_PageShift
  1151  		if physPageSize > _PageSize {
  1152  			// We can only release pages in
  1153  			// physPageSize blocks, so round start
  1154  			// and end in. (Otherwise, madvise
  1155  			// will round them *out* and release
  1156  			// more memory than we want.)
  1157  			start = (start + physPageSize - 1) &^ (physPageSize - 1)
  1158  			end &^= physPageSize - 1
  1159  			if end <= start {
  1160  				// start and end don't span a
  1161  				// whole physical page.
  1162  				continue
  1163  			}
  1164  		}
  1165  		len := end - start
  1166  
  1167  		released := len - (s.npreleased << _PageShift)
  1168  		if physPageSize > _PageSize && released == 0 {
  1169  			continue
  1170  		}
  1171  		memstats.heap_released += uint64(released)
  1172  		sumreleased += released
  1173  		s.npreleased = len >> _PageShift
  1174  		sysUnused(unsafe.Pointer(start), len)
  1175  	}
  1176  	return sumreleased
  1177  }
  1178  
  1179  func (h *mheap) scavenge(k int32, now, limit uint64) {
  1180  	// Disallow malloc or panic while holding the heap lock. We do
  1181  	// this here because this is an non-mallocgc entry-point to
  1182  	// the mheap API.
  1183  	gp := getg()
  1184  	gp.m.mallocing++
  1185  	lock(&h.lock)
  1186  	var sumreleased uintptr
  1187  	for i := 0; i < len(h.free); i++ {
  1188  		sumreleased += scavengelist(&h.free[i], now, limit)
  1189  	}
  1190  	sumreleased += scavengetreap(h.freelarge.treap, now, limit)
  1191  	unlock(&h.lock)
  1192  	gp.m.mallocing--
  1193  
  1194  	if debug.gctrace > 0 {
  1195  		if sumreleased > 0 {
  1196  			print("scvg", k, ": ", sumreleased>>20, " MB released\n")
  1197  		}
  1198  		print("scvg", k, ": 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")
  1199  	}
  1200  }
  1201  
  1202  //go:linkname runtime_debug_freeOSMemory runtime/debug.freeOSMemory
  1203  func runtime_debug_freeOSMemory() {
  1204  	GC()
  1205  	systemstack(func() { mheap_.scavenge(-1, ^uint64(0), 0) })
  1206  }
  1207  
  1208  // Initialize a new span with the given start and npages.
  1209  func (span *mspan) init(base uintptr, npages uintptr) {
  1210  	// span is *not* zeroed.
  1211  	span.next = nil
  1212  	span.prev = nil
  1213  	span.list = nil
  1214  	span.startAddr = base
  1215  	span.npages = npages
  1216  	span.allocCount = 0
  1217  	span.spanclass = 0
  1218  	span.incache = false
  1219  	span.elemsize = 0
  1220  	span.state = _MSpanDead
  1221  	span.unusedsince = 0
  1222  	span.npreleased = 0
  1223  	span.speciallock.key = 0
  1224  	span.specials = nil
  1225  	span.needzero = 0
  1226  	span.freeindex = 0
  1227  	span.allocBits = nil
  1228  	span.gcmarkBits = nil
  1229  }
  1230  
  1231  func (span *mspan) inList() bool {
  1232  	return span.list != nil
  1233  }
  1234  
  1235  // Initialize an empty doubly-linked list.
  1236  func (list *mSpanList) init() {
  1237  	list.first = nil
  1238  	list.last = nil
  1239  }
  1240  
  1241  func (list *mSpanList) remove(span *mspan) {
  1242  	if span.list != list {
  1243  		print("runtime: failed MSpanList_Remove span.npages=", span.npages,
  1244  			" span=", span, " prev=", span.prev, " span.list=", span.list, " list=", list, "\n")
  1245  		throw("MSpanList_Remove")
  1246  	}
  1247  	if list.first == span {
  1248  		list.first = span.next
  1249  	} else {
  1250  		span.prev.next = span.next
  1251  	}
  1252  	if list.last == span {
  1253  		list.last = span.prev
  1254  	} else {
  1255  		span.next.prev = span.prev
  1256  	}
  1257  	span.next = nil
  1258  	span.prev = nil
  1259  	span.list = nil
  1260  }
  1261  
  1262  func (list *mSpanList) isEmpty() bool {
  1263  	return list.first == nil
  1264  }
  1265  
  1266  func (list *mSpanList) insert(span *mspan) {
  1267  	if span.next != nil || span.prev != nil || span.list != nil {
  1268  		println("runtime: failed MSpanList_Insert", span, span.next, span.prev, span.list)
  1269  		throw("MSpanList_Insert")
  1270  	}
  1271  	span.next = list.first
  1272  	if list.first != nil {
  1273  		// The list contains at least one span; link it in.
  1274  		// The last span in the list doesn't change.
  1275  		list.first.prev = span
  1276  	} else {
  1277  		// The list contains no spans, so this is also the last span.
  1278  		list.last = span
  1279  	}
  1280  	list.first = span
  1281  	span.list = list
  1282  }
  1283  
  1284  func (list *mSpanList) insertBack(span *mspan) {
  1285  	if span.next != nil || span.prev != nil || span.list != nil {
  1286  		println("runtime: failed MSpanList_InsertBack", span, span.next, span.prev, span.list)
  1287  		throw("MSpanList_InsertBack")
  1288  	}
  1289  	span.prev = list.last
  1290  	if list.last != nil {
  1291  		// The list contains at least one span.
  1292  		list.last.next = span
  1293  	} else {
  1294  		// The list contains no spans, so this is also the first span.
  1295  		list.first = span
  1296  	}
  1297  	list.last = span
  1298  	span.list = list
  1299  }
  1300  
  1301  // takeAll removes all spans from other and inserts them at the front
  1302  // of list.
  1303  func (list *mSpanList) takeAll(other *mSpanList) {
  1304  	if other.isEmpty() {
  1305  		return
  1306  	}
  1307  
  1308  	// Reparent everything in other to list.
  1309  	for s := other.first; s != nil; s = s.next {
  1310  		s.list = list
  1311  	}
  1312  
  1313  	// Concatenate the lists.
  1314  	if list.isEmpty() {
  1315  		*list = *other
  1316  	} else {
  1317  		// Neither list is empty. Put other before list.
  1318  		other.last.next = list.first
  1319  		list.first.prev = other.last
  1320  		list.first = other.first
  1321  	}
  1322  
  1323  	other.first, other.last = nil, nil
  1324  }
  1325  
  1326  const (
  1327  	_KindSpecialFinalizer = 1
  1328  	_KindSpecialProfile   = 2
  1329  	// Note: The finalizer special must be first because if we're freeing
  1330  	// an object, a finalizer special will cause the freeing operation
  1331  	// to abort, and we want to keep the other special records around
  1332  	// if that happens.
  1333  )
  1334  
  1335  //go:notinheap
  1336  type special struct {
  1337  	next   *special // linked list in span
  1338  	offset uint16   // span offset of object
  1339  	kind   byte     // kind of special
  1340  }
  1341  
  1342  // Adds the special record s to the list of special records for
  1343  // the object p. All fields of s should be filled in except for
  1344  // offset & next, which this routine will fill in.
  1345  // Returns true if the special was successfully added, false otherwise.
  1346  // (The add will fail only if a record with the same p and s->kind
  1347  //  already exists.)
  1348  func addspecial(p unsafe.Pointer, s *special) bool {
  1349  	span := mheap_.lookupMaybe(p)
  1350  	if span == nil {
  1351  		throw("addspecial on invalid pointer")
  1352  	}
  1353  
  1354  	// Ensure that the span is swept.
  1355  	// Sweeping accesses the specials list w/o locks, so we have
  1356  	// to synchronize with it. And it's just much safer.
  1357  	mp := acquirem()
  1358  	span.ensureSwept()
  1359  
  1360  	offset := uintptr(p) - span.base()
  1361  	kind := s.kind
  1362  
  1363  	lock(&span.speciallock)
  1364  
  1365  	// Find splice point, check for existing record.
  1366  	t := &span.specials
  1367  	for {
  1368  		x := *t
  1369  		if x == nil {
  1370  			break
  1371  		}
  1372  		if offset == uintptr(x.offset) && kind == x.kind {
  1373  			unlock(&span.speciallock)
  1374  			releasem(mp)
  1375  			return false // already exists
  1376  		}
  1377  		if offset < uintptr(x.offset) || (offset == uintptr(x.offset) && kind < x.kind) {
  1378  			break
  1379  		}
  1380  		t = &x.next
  1381  	}
  1382  
  1383  	// Splice in record, fill in offset.
  1384  	s.offset = uint16(offset)
  1385  	s.next = *t
  1386  	*t = s
  1387  	unlock(&span.speciallock)
  1388  	releasem(mp)
  1389  
  1390  	return true
  1391  }
  1392  
  1393  // Removes the Special record of the given kind for the object p.
  1394  // Returns the record if the record existed, nil otherwise.
  1395  // The caller must FixAlloc_Free the result.
  1396  func removespecial(p unsafe.Pointer, kind uint8) *special {
  1397  	span := mheap_.lookupMaybe(p)
  1398  	if span == nil {
  1399  		throw("removespecial on invalid pointer")
  1400  	}
  1401  
  1402  	// Ensure that the span is swept.
  1403  	// Sweeping accesses the specials list w/o locks, so we have
  1404  	// to synchronize with it. And it's just much safer.
  1405  	mp := acquirem()
  1406  	span.ensureSwept()
  1407  
  1408  	offset := uintptr(p) - span.base()
  1409  
  1410  	lock(&span.speciallock)
  1411  	t := &span.specials
  1412  	for {
  1413  		s := *t
  1414  		if s == nil {
  1415  			break
  1416  		}
  1417  		// This function is used for finalizers only, so we don't check for
  1418  		// "interior" specials (p must be exactly equal to s->offset).
  1419  		if offset == uintptr(s.offset) && kind == s.kind {
  1420  			*t = s.next
  1421  			unlock(&span.speciallock)
  1422  			releasem(mp)
  1423  			return s
  1424  		}
  1425  		t = &s.next
  1426  	}
  1427  	unlock(&span.speciallock)
  1428  	releasem(mp)
  1429  	return nil
  1430  }
  1431  
  1432  // The described object has a finalizer set for it.
  1433  //
  1434  // specialfinalizer is allocated from non-GC'd memory, so any heap
  1435  // pointers must be specially handled.
  1436  //
  1437  //go:notinheap
  1438  type specialfinalizer struct {
  1439  	special special
  1440  	fn      *funcval // May be a heap pointer.
  1441  	nret    uintptr
  1442  	fint    *_type   // May be a heap pointer, but always live.
  1443  	ot      *ptrtype // May be a heap pointer, but always live.
  1444  }
  1445  
  1446  // Adds a finalizer to the object p. Returns true if it succeeded.
  1447  func addfinalizer(p unsafe.Pointer, f *funcval, nret uintptr, fint *_type, ot *ptrtype) bool {
  1448  	lock(&mheap_.speciallock)
  1449  	s := (*specialfinalizer)(mheap_.specialfinalizeralloc.alloc())
  1450  	unlock(&mheap_.speciallock)
  1451  	s.special.kind = _KindSpecialFinalizer
  1452  	s.fn = f
  1453  	s.nret = nret
  1454  	s.fint = fint
  1455  	s.ot = ot
  1456  	if addspecial(p, &s.special) {
  1457  		// This is responsible for maintaining the same
  1458  		// GC-related invariants as markrootSpans in any
  1459  		// situation where it's possible that markrootSpans
  1460  		// has already run but mark termination hasn't yet.
  1461  		if gcphase != _GCoff {
  1462  			_, base, _ := findObject(p)
  1463  			mp := acquirem()
  1464  			gcw := &mp.p.ptr().gcw
  1465  			// Mark everything reachable from the object
  1466  			// so it's retained for the finalizer.
  1467  			scanobject(uintptr(base), gcw)
  1468  			// Mark the finalizer itself, since the
  1469  			// special isn't part of the GC'd heap.
  1470  			scanblock(uintptr(unsafe.Pointer(&s.fn)), sys.PtrSize, &oneptrmask[0], gcw)
  1471  			if gcBlackenPromptly {
  1472  				gcw.dispose()
  1473  			}
  1474  			releasem(mp)
  1475  		}
  1476  		return true
  1477  	}
  1478  
  1479  	// There was an old finalizer
  1480  	lock(&mheap_.speciallock)
  1481  	mheap_.specialfinalizeralloc.free(unsafe.Pointer(s))
  1482  	unlock(&mheap_.speciallock)
  1483  	return false
  1484  }
  1485  
  1486  // Removes the finalizer (if any) from the object p.
  1487  func removefinalizer(p unsafe.Pointer) {
  1488  	s := (*specialfinalizer)(unsafe.Pointer(removespecial(p, _KindSpecialFinalizer)))
  1489  	if s == nil {
  1490  		return // there wasn't a finalizer to remove
  1491  	}
  1492  	lock(&mheap_.speciallock)
  1493  	mheap_.specialfinalizeralloc.free(unsafe.Pointer(s))
  1494  	unlock(&mheap_.speciallock)
  1495  }
  1496  
  1497  // The described object is being heap profiled.
  1498  //
  1499  //go:notinheap
  1500  type specialprofile struct {
  1501  	special special
  1502  	b       *bucket
  1503  }
  1504  
  1505  // Set the heap profile bucket associated with addr to b.
  1506  func setprofilebucket(p unsafe.Pointer, b *bucket) {
  1507  	lock(&mheap_.speciallock)
  1508  	s := (*specialprofile)(mheap_.specialprofilealloc.alloc())
  1509  	unlock(&mheap_.speciallock)
  1510  	s.special.kind = _KindSpecialProfile
  1511  	s.b = b
  1512  	if !addspecial(p, &s.special) {
  1513  		throw("setprofilebucket: profile already set")
  1514  	}
  1515  }
  1516  
  1517  // Do whatever cleanup needs to be done to deallocate s. It has
  1518  // already been unlinked from the MSpan specials list.
  1519  func freespecial(s *special, p unsafe.Pointer, size uintptr) {
  1520  	switch s.kind {
  1521  	case _KindSpecialFinalizer:
  1522  		sf := (*specialfinalizer)(unsafe.Pointer(s))
  1523  		queuefinalizer(p, sf.fn, sf.nret, sf.fint, sf.ot)
  1524  		lock(&mheap_.speciallock)
  1525  		mheap_.specialfinalizeralloc.free(unsafe.Pointer(sf))
  1526  		unlock(&mheap_.speciallock)
  1527  	case _KindSpecialProfile:
  1528  		sp := (*specialprofile)(unsafe.Pointer(s))
  1529  		mProf_Free(sp.b, size)
  1530  		lock(&mheap_.speciallock)
  1531  		mheap_.specialprofilealloc.free(unsafe.Pointer(sp))
  1532  		unlock(&mheap_.speciallock)
  1533  	default:
  1534  		throw("bad special kind")
  1535  		panic("not reached")
  1536  	}
  1537  }
  1538  
  1539  // gcBits is an alloc/mark bitmap. This is always used as *gcBits.
  1540  //
  1541  //go:notinheap
  1542  type gcBits uint8
  1543  
  1544  // bytep returns a pointer to the n'th byte of b.
  1545  func (b *gcBits) bytep(n uintptr) *uint8 {
  1546  	return addb((*uint8)(b), n)
  1547  }
  1548  
  1549  // bitp returns a pointer to the byte containing bit n and a mask for
  1550  // selecting that bit from *bytep.
  1551  func (b *gcBits) bitp(n uintptr) (bytep *uint8, mask uint8) {
  1552  	return b.bytep(n / 8), 1 << (n % 8)
  1553  }
  1554  
  1555  const gcBitsChunkBytes = uintptr(64 << 10)
  1556  const gcBitsHeaderBytes = unsafe.Sizeof(gcBitsHeader{})
  1557  
  1558  type gcBitsHeader struct {
  1559  	free uintptr // free is the index into bits of the next free byte.
  1560  	next uintptr // *gcBits triggers recursive type bug. (issue 14620)
  1561  }
  1562  
  1563  //go:notinheap
  1564  type gcBitsArena struct {
  1565  	// gcBitsHeader // side step recursive type bug (issue 14620) by including fields by hand.
  1566  	free uintptr // free is the index into bits of the next free byte; read/write atomically
  1567  	next *gcBitsArena
  1568  	bits [gcBitsChunkBytes - gcBitsHeaderBytes]gcBits
  1569  }
  1570  
  1571  var gcBitsArenas struct {
  1572  	lock     mutex
  1573  	free     *gcBitsArena
  1574  	next     *gcBitsArena // Read atomically. Write atomically under lock.
  1575  	current  *gcBitsArena
  1576  	previous *gcBitsArena
  1577  }
  1578  
  1579  // tryAlloc allocates from b or returns nil if b does not have enough room.
  1580  // This is safe to call concurrently.
  1581  func (b *gcBitsArena) tryAlloc(bytes uintptr) *gcBits {
  1582  	if b == nil || atomic.Loaduintptr(&b.free)+bytes > uintptr(len(b.bits)) {
  1583  		return nil
  1584  	}
  1585  	// Try to allocate from this block.
  1586  	end := atomic.Xadduintptr(&b.free, bytes)
  1587  	if end > uintptr(len(b.bits)) {
  1588  		return nil
  1589  	}
  1590  	// There was enough room.
  1591  	start := end - bytes
  1592  	return &b.bits[start]
  1593  }
  1594  
  1595  // newMarkBits returns a pointer to 8 byte aligned bytes
  1596  // to be used for a span's mark bits.
  1597  func newMarkBits(nelems uintptr) *gcBits {
  1598  	blocksNeeded := uintptr((nelems + 63) / 64)
  1599  	bytesNeeded := blocksNeeded * 8
  1600  
  1601  	// Try directly allocating from the current head arena.
  1602  	head := (*gcBitsArena)(atomic.Loadp(unsafe.Pointer(&gcBitsArenas.next)))
  1603  	if p := head.tryAlloc(bytesNeeded); p != nil {
  1604  		return p
  1605  	}
  1606  
  1607  	// There's not enough room in the head arena. We may need to
  1608  	// allocate a new arena.
  1609  	lock(&gcBitsArenas.lock)
  1610  	// Try the head arena again, since it may have changed. Now
  1611  	// that we hold the lock, the list head can't change, but its
  1612  	// free position still can.
  1613  	if p := gcBitsArenas.next.tryAlloc(bytesNeeded); p != nil {
  1614  		unlock(&gcBitsArenas.lock)
  1615  		return p
  1616  	}
  1617  
  1618  	// Allocate a new arena. This may temporarily drop the lock.
  1619  	fresh := newArenaMayUnlock()
  1620  	// If newArenaMayUnlock dropped the lock, another thread may
  1621  	// have put a fresh arena on the "next" list. Try allocating
  1622  	// from next again.
  1623  	if p := gcBitsArenas.next.tryAlloc(bytesNeeded); p != nil {
  1624  		// Put fresh back on the free list.
  1625  		// TODO: Mark it "already zeroed"
  1626  		fresh.next = gcBitsArenas.free
  1627  		gcBitsArenas.free = fresh
  1628  		unlock(&gcBitsArenas.lock)
  1629  		return p
  1630  	}
  1631  
  1632  	// Allocate from the fresh arena. We haven't linked it in yet, so
  1633  	// this cannot race and is guaranteed to succeed.
  1634  	p := fresh.tryAlloc(bytesNeeded)
  1635  	if p == nil {
  1636  		throw("markBits overflow")
  1637  	}
  1638  
  1639  	// Add the fresh arena to the "next" list.
  1640  	fresh.next = gcBitsArenas.next
  1641  	atomic.StorepNoWB(unsafe.Pointer(&gcBitsArenas.next), unsafe.Pointer(fresh))
  1642  
  1643  	unlock(&gcBitsArenas.lock)
  1644  	return p
  1645  }
  1646  
  1647  // newAllocBits returns a pointer to 8 byte aligned bytes
  1648  // to be used for this span's alloc bits.
  1649  // newAllocBits is used to provide newly initialized spans
  1650  // allocation bits. For spans not being initialized the
  1651  // the mark bits are repurposed as allocation bits when
  1652  // the span is swept.
  1653  func newAllocBits(nelems uintptr) *gcBits {
  1654  	return newMarkBits(nelems)
  1655  }
  1656  
  1657  // nextMarkBitArenaEpoch establishes a new epoch for the arenas
  1658  // holding the mark bits. The arenas are named relative to the
  1659  // current GC cycle which is demarcated by the call to finishweep_m.
  1660  //
  1661  // All current spans have been swept.
  1662  // During that sweep each span allocated room for its gcmarkBits in
  1663  // gcBitsArenas.next block. gcBitsArenas.next becomes the gcBitsArenas.current
  1664  // where the GC will mark objects and after each span is swept these bits
  1665  // will be used to allocate objects.
  1666  // gcBitsArenas.current becomes gcBitsArenas.previous where the span's
  1667  // gcAllocBits live until all the spans have been swept during this GC cycle.
  1668  // The span's sweep extinguishes all the references to gcBitsArenas.previous
  1669  // by pointing gcAllocBits into the gcBitsArenas.current.
  1670  // The gcBitsArenas.previous is released to the gcBitsArenas.free list.
  1671  func nextMarkBitArenaEpoch() {
  1672  	lock(&gcBitsArenas.lock)
  1673  	if gcBitsArenas.previous != nil {
  1674  		if gcBitsArenas.free == nil {
  1675  			gcBitsArenas.free = gcBitsArenas.previous
  1676  		} else {
  1677  			// Find end of previous arenas.
  1678  			last := gcBitsArenas.previous
  1679  			for last = gcBitsArenas.previous; last.next != nil; last = last.next {
  1680  			}
  1681  			last.next = gcBitsArenas.free
  1682  			gcBitsArenas.free = gcBitsArenas.previous
  1683  		}
  1684  	}
  1685  	gcBitsArenas.previous = gcBitsArenas.current
  1686  	gcBitsArenas.current = gcBitsArenas.next
  1687  	atomic.StorepNoWB(unsafe.Pointer(&gcBitsArenas.next), nil) // newMarkBits calls newArena when needed
  1688  	unlock(&gcBitsArenas.lock)
  1689  }
  1690  
  1691  // newArenaMayUnlock allocates and zeroes a gcBits arena.
  1692  // The caller must hold gcBitsArena.lock. This may temporarily release it.
  1693  func newArenaMayUnlock() *gcBitsArena {
  1694  	var result *gcBitsArena
  1695  	if gcBitsArenas.free == nil {
  1696  		unlock(&gcBitsArenas.lock)
  1697  		result = (*gcBitsArena)(sysAlloc(gcBitsChunkBytes, &memstats.gc_sys))
  1698  		if result == nil {
  1699  			throw("runtime: cannot allocate memory")
  1700  		}
  1701  		lock(&gcBitsArenas.lock)
  1702  	} else {
  1703  		result = gcBitsArenas.free
  1704  		gcBitsArenas.free = gcBitsArenas.free.next
  1705  		memclrNoHeapPointers(unsafe.Pointer(result), gcBitsChunkBytes)
  1706  	}
  1707  	result.next = nil
  1708  	// If result.bits is not 8 byte aligned adjust index so
  1709  	// that &result.bits[result.free] is 8 byte aligned.
  1710  	if uintptr(unsafe.Offsetof(gcBitsArena{}.bits))&7 == 0 {
  1711  		result.free = 0
  1712  	} else {
  1713  		result.free = 8 - (uintptr(unsafe.Pointer(&result.bits[0])) & 7)
  1714  	}
  1715  	return result
  1716  }
  1717  

View as plain text