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

View as plain text