Source file src/runtime/mheap.go

     1  // Copyright 2009 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Page heap.
     6  //
     7  // See malloc.go for overview.
     8  
     9  package runtime
    10  
    11  import (
    12  	"internal/cpu"
    13  	"internal/goarch"
    14  	"internal/goexperiment"
    15  	"runtime/internal/atomic"
    16  	"runtime/internal/sys"
    17  	"unsafe"
    18  )
    19  
    20  const (
    21  	// minPhysPageSize is a lower-bound on the physical page size. The
    22  	// true physical page size may be larger than this. In contrast,
    23  	// sys.PhysPageSize is an upper-bound on the physical page size.
    24  	minPhysPageSize = 4096
    25  
    26  	// maxPhysPageSize is the maximum page size the runtime supports.
    27  	maxPhysPageSize = 512 << 10
    28  
    29  	// maxPhysHugePageSize sets an upper-bound on the maximum huge page size
    30  	// that the runtime supports.
    31  	maxPhysHugePageSize = pallocChunkBytes
    32  
    33  	// pagesPerReclaimerChunk indicates how many pages to scan from the
    34  	// pageInUse bitmap at a time. Used by the page reclaimer.
    35  	//
    36  	// Higher values reduce contention on scanning indexes (such as
    37  	// h.reclaimIndex), but increase the minimum latency of the
    38  	// operation.
    39  	//
    40  	// The time required to scan this many pages can vary a lot depending
    41  	// on how many spans are actually freed. Experimentally, it can
    42  	// scan for pages at ~300 GB/ms on a 2.6GHz Core i7, but can only
    43  	// free spans at ~32 MB/ms. Using 512 pages bounds this at
    44  	// roughly 100µs.
    45  	//
    46  	// Must be a multiple of the pageInUse bitmap element size and
    47  	// must also evenly divide pagesPerArena.
    48  	pagesPerReclaimerChunk = 512
    49  
    50  	// physPageAlignedStacks indicates whether stack allocations must be
    51  	// physical page aligned. This is a requirement for MAP_STACK on
    52  	// OpenBSD.
    53  	physPageAlignedStacks = GOOS == "openbsd"
    54  )
    55  
    56  // Main malloc heap.
    57  // The heap itself is the "free" and "scav" treaps,
    58  // but all the other global data is here too.
    59  //
    60  // mheap must not be heap-allocated because it contains mSpanLists,
    61  // which must not be heap-allocated.
    62  type mheap struct {
    63  	_ sys.NotInHeap
    64  
    65  	// lock must only be acquired on the system stack, otherwise a g
    66  	// could self-deadlock if its stack grows with the lock held.
    67  	lock mutex
    68  
    69  	pages pageAlloc // page allocation data structure
    70  
    71  	sweepgen uint32 // sweep generation, see comment in mspan; written during STW
    72  
    73  	// allspans is a slice of all mspans ever created. Each mspan
    74  	// appears exactly once.
    75  	//
    76  	// The memory for allspans is manually managed and can be
    77  	// reallocated and move as the heap grows.
    78  	//
    79  	// In general, allspans is protected by mheap_.lock, which
    80  	// prevents concurrent access as well as freeing the backing
    81  	// store. Accesses during STW might not hold the lock, but
    82  	// must ensure that allocation cannot happen around the
    83  	// access (since that may free the backing store).
    84  	allspans []*mspan // all spans out there
    85  
    86  	// Proportional sweep
    87  	//
    88  	// These parameters represent a linear function from gcController.heapLive
    89  	// to page sweep count. The proportional sweep system works to
    90  	// stay in the black by keeping the current page sweep count
    91  	// above this line at the current gcController.heapLive.
    92  	//
    93  	// The line has slope sweepPagesPerByte and passes through a
    94  	// basis point at (sweepHeapLiveBasis, pagesSweptBasis). At
    95  	// any given time, the system is at (gcController.heapLive,
    96  	// pagesSwept) in this space.
    97  	//
    98  	// It is important that the line pass through a point we
    99  	// control rather than simply starting at a 0,0 origin
   100  	// because that lets us adjust sweep pacing at any time while
   101  	// accounting for current progress. If we could only adjust
   102  	// the slope, it would create a discontinuity in debt if any
   103  	// progress has already been made.
   104  	pagesInUse         atomic.Uintptr // pages of spans in stats mSpanInUse
   105  	pagesSwept         atomic.Uint64  // pages swept this cycle
   106  	pagesSweptBasis    atomic.Uint64  // pagesSwept to use as the origin of the sweep ratio
   107  	sweepHeapLiveBasis uint64         // value of gcController.heapLive to use as the origin of sweep ratio; written with lock, read without
   108  	sweepPagesPerByte  float64        // proportional sweep ratio; written with lock, read without
   109  
   110  	// Page reclaimer state
   111  
   112  	// reclaimIndex is the page index in allArenas of next page to
   113  	// reclaim. Specifically, it refers to page (i %
   114  	// pagesPerArena) of arena allArenas[i / pagesPerArena].
   115  	//
   116  	// If this is >= 1<<63, the page reclaimer is done scanning
   117  	// the page marks.
   118  	reclaimIndex atomic.Uint64
   119  
   120  	// reclaimCredit is spare credit for extra pages swept. Since
   121  	// the page reclaimer works in large chunks, it may reclaim
   122  	// more than requested. Any spare pages released go to this
   123  	// credit pool.
   124  	reclaimCredit atomic.Uintptr
   125  
   126  	_ cpu.CacheLinePad // prevents false-sharing between arenas and preceding variables
   127  
   128  	// arenas is the heap arena map. It points to the metadata for
   129  	// the heap for every arena frame of the entire usable virtual
   130  	// address space.
   131  	//
   132  	// Use arenaIndex to compute indexes into this array.
   133  	//
   134  	// For regions of the address space that are not backed by the
   135  	// Go heap, the arena map contains nil.
   136  	//
   137  	// Modifications are protected by mheap_.lock. Reads can be
   138  	// performed without locking; however, a given entry can
   139  	// transition from nil to non-nil at any time when the lock
   140  	// isn't held. (Entries never transitions back to nil.)
   141  	//
   142  	// In general, this is a two-level mapping consisting of an L1
   143  	// map and possibly many L2 maps. This saves space when there
   144  	// are a huge number of arena frames. However, on many
   145  	// platforms (even 64-bit), arenaL1Bits is 0, making this
   146  	// effectively a single-level map. In this case, arenas[0]
   147  	// will never be nil.
   148  	arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena
   149  
   150  	// arenasHugePages indicates whether arenas' L2 entries are eligible
   151  	// to be backed by huge pages.
   152  	arenasHugePages bool
   153  
   154  	// heapArenaAlloc is pre-reserved space for allocating heapArena
   155  	// objects. This is only used on 32-bit, where we pre-reserve
   156  	// this space to avoid interleaving it with the heap itself.
   157  	heapArenaAlloc linearAlloc
   158  
   159  	// arenaHints is a list of addresses at which to attempt to
   160  	// add more heap arenas. This is initially populated with a
   161  	// set of general hint addresses, and grown with the bounds of
   162  	// actual heap arena ranges.
   163  	arenaHints *arenaHint
   164  
   165  	// arena is a pre-reserved space for allocating heap arenas
   166  	// (the actual arenas). This is only used on 32-bit.
   167  	arena linearAlloc
   168  
   169  	// allArenas is the arenaIndex of every mapped arena. This can
   170  	// be used to iterate through the address space.
   171  	//
   172  	// Access is protected by mheap_.lock. However, since this is
   173  	// append-only and old backing arrays are never freed, it is
   174  	// safe to acquire mheap_.lock, copy the slice header, and
   175  	// then release mheap_.lock.
   176  	allArenas []arenaIdx
   177  
   178  	// sweepArenas is a snapshot of allArenas taken at the
   179  	// beginning of the sweep cycle. This can be read safely by
   180  	// simply blocking GC (by disabling preemption).
   181  	sweepArenas []arenaIdx
   182  
   183  	// markArenas is a snapshot of allArenas taken at the beginning
   184  	// of the mark cycle. Because allArenas is append-only, neither
   185  	// this slice nor its contents will change during the mark, so
   186  	// it can be read safely.
   187  	markArenas []arenaIdx
   188  
   189  	// curArena is the arena that the heap is currently growing
   190  	// into. This should always be physPageSize-aligned.
   191  	curArena struct {
   192  		base, end uintptr
   193  	}
   194  
   195  	// central free lists for small size classes.
   196  	// the padding makes sure that the mcentrals are
   197  	// spaced CacheLinePadSize bytes apart, so that each mcentral.lock
   198  	// gets its own cache line.
   199  	// central is indexed by spanClass.
   200  	central [numSpanClasses]struct {
   201  		mcentral mcentral
   202  		pad      [(cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize) % cpu.CacheLinePadSize]byte
   203  	}
   204  
   205  	spanalloc              fixalloc // allocator for span*
   206  	cachealloc             fixalloc // allocator for mcache*
   207  	specialfinalizeralloc  fixalloc // allocator for specialfinalizer*
   208  	specialprofilealloc    fixalloc // allocator for specialprofile*
   209  	specialReachableAlloc  fixalloc // allocator for specialReachable
   210  	specialPinCounterAlloc fixalloc // allocator for specialPinCounter
   211  	speciallock            mutex    // lock for special record allocators.
   212  	arenaHintAlloc         fixalloc // allocator for arenaHints
   213  
   214  	// User arena state.
   215  	//
   216  	// Protected by mheap_.lock.
   217  	userArena struct {
   218  		// arenaHints is a list of addresses at which to attempt to
   219  		// add more heap arenas for user arena chunks. This is initially
   220  		// populated with a set of general hint addresses, and grown with
   221  		// the bounds of actual heap arena ranges.
   222  		arenaHints *arenaHint
   223  
   224  		// quarantineList is a list of user arena spans that have been set to fault, but
   225  		// are waiting for all pointers into them to go away. Sweeping handles
   226  		// identifying when this is true, and moves the span to the ready list.
   227  		quarantineList mSpanList
   228  
   229  		// readyList is a list of empty user arena spans that are ready for reuse.
   230  		readyList mSpanList
   231  	}
   232  
   233  	unused *specialfinalizer // never set, just here to force the specialfinalizer type into DWARF
   234  }
   235  
   236  var mheap_ mheap
   237  
   238  // A heapArena stores metadata for a heap arena. heapArenas are stored
   239  // outside of the Go heap and accessed via the mheap_.arenas index.
   240  type heapArena struct {
   241  	_ sys.NotInHeap
   242  
   243  	// heapArenaPtrScalar contains pointer/scalar data about the heap for this heap arena.
   244  	heapArenaPtrScalar
   245  
   246  	// spans maps from virtual address page ID within this arena to *mspan.
   247  	// For allocated spans, their pages map to the span itself.
   248  	// For free spans, only the lowest and highest pages map to the span itself.
   249  	// Internal pages map to an arbitrary span.
   250  	// For pages that have never been allocated, spans entries are nil.
   251  	//
   252  	// Modifications are protected by mheap.lock. Reads can be
   253  	// performed without locking, but ONLY from indexes that are
   254  	// known to contain in-use or stack spans. This means there
   255  	// must not be a safe-point between establishing that an
   256  	// address is live and looking it up in the spans array.
   257  	spans [pagesPerArena]*mspan
   258  
   259  	// pageInUse is a bitmap that indicates which spans are in
   260  	// state mSpanInUse. This bitmap is indexed by page number,
   261  	// but only the bit corresponding to the first page in each
   262  	// span is used.
   263  	//
   264  	// Reads and writes are atomic.
   265  	pageInUse [pagesPerArena / 8]uint8
   266  
   267  	// pageMarks is a bitmap that indicates which spans have any
   268  	// marked objects on them. Like pageInUse, only the bit
   269  	// corresponding to the first page in each span is used.
   270  	//
   271  	// Writes are done atomically during marking. Reads are
   272  	// non-atomic and lock-free since they only occur during
   273  	// sweeping (and hence never race with writes).
   274  	//
   275  	// This is used to quickly find whole spans that can be freed.
   276  	//
   277  	// TODO(austin): It would be nice if this was uint64 for
   278  	// faster scanning, but we don't have 64-bit atomic bit
   279  	// operations.
   280  	pageMarks [pagesPerArena / 8]uint8
   281  
   282  	// pageSpecials is a bitmap that indicates which spans have
   283  	// specials (finalizers or other). Like pageInUse, only the bit
   284  	// corresponding to the first page in each span is used.
   285  	//
   286  	// Writes are done atomically whenever a special is added to
   287  	// a span and whenever the last special is removed from a span.
   288  	// Reads are done atomically to find spans containing specials
   289  	// during marking.
   290  	pageSpecials [pagesPerArena / 8]uint8
   291  
   292  	// checkmarks stores the debug.gccheckmark state. It is only
   293  	// used if debug.gccheckmark > 0.
   294  	checkmarks *checkmarksMap
   295  
   296  	// zeroedBase marks the first byte of the first page in this
   297  	// arena which hasn't been used yet and is therefore already
   298  	// zero. zeroedBase is relative to the arena base.
   299  	// Increases monotonically until it hits heapArenaBytes.
   300  	//
   301  	// This field is sufficient to determine if an allocation
   302  	// needs to be zeroed because the page allocator follows an
   303  	// address-ordered first-fit policy.
   304  	//
   305  	// Read atomically and written with an atomic CAS.
   306  	zeroedBase uintptr
   307  }
   308  
   309  // arenaHint is a hint for where to grow the heap arenas. See
   310  // mheap_.arenaHints.
   311  type arenaHint struct {
   312  	_    sys.NotInHeap
   313  	addr uintptr
   314  	down bool
   315  	next *arenaHint
   316  }
   317  
   318  // An mspan is a run of pages.
   319  //
   320  // When a mspan is in the heap free treap, state == mSpanFree
   321  // and heapmap(s->start) == span, heapmap(s->start+s->npages-1) == span.
   322  // If the mspan is in the heap scav treap, then in addition to the
   323  // above scavenged == true. scavenged == false in all other cases.
   324  //
   325  // When a mspan is allocated, state == mSpanInUse or mSpanManual
   326  // and heapmap(i) == span for all s->start <= i < s->start+s->npages.
   327  
   328  // Every mspan is in one doubly-linked list, either in the mheap's
   329  // busy list or one of the mcentral's span lists.
   330  
   331  // An mspan representing actual memory has state mSpanInUse,
   332  // mSpanManual, or mSpanFree. Transitions between these states are
   333  // constrained as follows:
   334  //
   335  //   - A span may transition from free to in-use or manual during any GC
   336  //     phase.
   337  //
   338  //   - During sweeping (gcphase == _GCoff), a span may transition from
   339  //     in-use to free (as a result of sweeping) or manual to free (as a
   340  //     result of stacks being freed).
   341  //
   342  //   - During GC (gcphase != _GCoff), a span *must not* transition from
   343  //     manual or in-use to free. Because concurrent GC may read a pointer
   344  //     and then look up its span, the span state must be monotonic.
   345  //
   346  // Setting mspan.state to mSpanInUse or mSpanManual must be done
   347  // atomically and only after all other span fields are valid.
   348  // Likewise, if inspecting a span is contingent on it being
   349  // mSpanInUse, the state should be loaded atomically and checked
   350  // before depending on other fields. This allows the garbage collector
   351  // to safely deal with potentially invalid pointers, since resolving
   352  // such pointers may race with a span being allocated.
   353  type mSpanState uint8
   354  
   355  const (
   356  	mSpanDead   mSpanState = iota
   357  	mSpanInUse             // allocated for garbage collected heap
   358  	mSpanManual            // allocated for manual management (e.g., stack allocator)
   359  )
   360  
   361  // mSpanStateNames are the names of the span states, indexed by
   362  // mSpanState.
   363  var mSpanStateNames = []string{
   364  	"mSpanDead",
   365  	"mSpanInUse",
   366  	"mSpanManual",
   367  }
   368  
   369  // mSpanStateBox holds an atomic.Uint8 to provide atomic operations on
   370  // an mSpanState. This is a separate type to disallow accidental comparison
   371  // or assignment with mSpanState.
   372  type mSpanStateBox struct {
   373  	s atomic.Uint8
   374  }
   375  
   376  // It is nosplit to match get, below.
   377  
   378  //go:nosplit
   379  func (b *mSpanStateBox) set(s mSpanState) {
   380  	b.s.Store(uint8(s))
   381  }
   382  
   383  // It is nosplit because it's called indirectly by typedmemclr,
   384  // which must not be preempted.
   385  
   386  //go:nosplit
   387  func (b *mSpanStateBox) get() mSpanState {
   388  	return mSpanState(b.s.Load())
   389  }
   390  
   391  // mSpanList heads a linked list of spans.
   392  type mSpanList struct {
   393  	_     sys.NotInHeap
   394  	first *mspan // first span in list, or nil if none
   395  	last  *mspan // last span in list, or nil if none
   396  }
   397  
   398  type mspan struct {
   399  	_    sys.NotInHeap
   400  	next *mspan     // next span in list, or nil if none
   401  	prev *mspan     // previous span in list, or nil if none
   402  	list *mSpanList // For debugging.
   403  
   404  	startAddr uintptr // address of first byte of span aka s.base()
   405  	npages    uintptr // number of pages in span
   406  
   407  	manualFreeList gclinkptr // list of free objects in mSpanManual spans
   408  
   409  	// freeindex is the slot index between 0 and nelems at which to begin scanning
   410  	// for the next free object in this span.
   411  	// Each allocation scans allocBits starting at freeindex until it encounters a 0
   412  	// indicating a free object. freeindex is then adjusted so that subsequent scans begin
   413  	// just past the newly discovered free object.
   414  	//
   415  	// If freeindex == nelem, this span has no free objects.
   416  	//
   417  	// allocBits is a bitmap of objects in this span.
   418  	// If n >= freeindex and allocBits[n/8] & (1<<(n%8)) is 0
   419  	// then object n is free;
   420  	// otherwise, object n is allocated. Bits starting at nelem are
   421  	// undefined and should never be referenced.
   422  	//
   423  	// Object n starts at address n*elemsize + (start << pageShift).
   424  	freeindex uint16
   425  	// TODO: Look up nelems from sizeclass and remove this field if it
   426  	// helps performance.
   427  	nelems uint16 // number of object in the span.
   428  	// freeIndexForScan is like freeindex, except that freeindex is
   429  	// used by the allocator whereas freeIndexForScan is used by the
   430  	// GC scanner. They are two fields so that the GC sees the object
   431  	// is allocated only when the object and the heap bits are
   432  	// initialized (see also the assignment of freeIndexForScan in
   433  	// mallocgc, and issue 54596).
   434  	freeIndexForScan uint16
   435  
   436  	// Cache of the allocBits at freeindex. allocCache is shifted
   437  	// such that the lowest bit corresponds to the bit freeindex.
   438  	// allocCache holds the complement of allocBits, thus allowing
   439  	// ctz (count trailing zero) to use it directly.
   440  	// allocCache may contain bits beyond s.nelems; the caller must ignore
   441  	// these.
   442  	allocCache uint64
   443  
   444  	// allocBits and gcmarkBits hold pointers to a span's mark and
   445  	// allocation bits. The pointers are 8 byte aligned.
   446  	// There are three arenas where this data is held.
   447  	// free: Dirty arenas that are no longer accessed
   448  	//       and can be reused.
   449  	// next: Holds information to be used in the next GC cycle.
   450  	// current: Information being used during this GC cycle.
   451  	// previous: Information being used during the last GC cycle.
   452  	// A new GC cycle starts with the call to finishsweep_m.
   453  	// finishsweep_m moves the previous arena to the free arena,
   454  	// the current arena to the previous arena, and
   455  	// the next arena to the current arena.
   456  	// The next arena is populated as the spans request
   457  	// memory to hold gcmarkBits for the next GC cycle as well
   458  	// as allocBits for newly allocated spans.
   459  	//
   460  	// The pointer arithmetic is done "by hand" instead of using
   461  	// arrays to avoid bounds checks along critical performance
   462  	// paths.
   463  	// The sweep will free the old allocBits and set allocBits to the
   464  	// gcmarkBits. The gcmarkBits are replaced with a fresh zeroed
   465  	// out memory.
   466  	allocBits  *gcBits
   467  	gcmarkBits *gcBits
   468  	pinnerBits *gcBits // bitmap for pinned objects; accessed atomically
   469  
   470  	// sweep generation:
   471  	// if sweepgen == h->sweepgen - 2, the span needs sweeping
   472  	// if sweepgen == h->sweepgen - 1, the span is currently being swept
   473  	// if sweepgen == h->sweepgen, the span is swept and ready to use
   474  	// if sweepgen == h->sweepgen + 1, the span was cached before sweep began and is still cached, and needs sweeping
   475  	// if sweepgen == h->sweepgen + 3, the span was swept and then cached and is still cached
   476  	// h->sweepgen is incremented by 2 after every GC
   477  
   478  	sweepgen              uint32
   479  	divMul                uint32        // for divide by elemsize
   480  	allocCount            uint16        // number of allocated objects
   481  	spanclass             spanClass     // size class and noscan (uint8)
   482  	state                 mSpanStateBox // mSpanInUse etc; accessed atomically (get/set methods)
   483  	needzero              uint8         // needs to be zeroed before allocation
   484  	isUserArenaChunk      bool          // whether or not this span represents a user arena
   485  	allocCountBeforeCache uint16        // a copy of allocCount that is stored just before this span is cached
   486  	elemsize              uintptr       // computed from sizeclass or from npages
   487  	limit                 uintptr       // end of data in span
   488  	speciallock           mutex         // guards specials list and changes to pinnerBits
   489  	specials              *special      // linked list of special records sorted by offset.
   490  	userArenaChunkFree    addrRange     // interval for managing chunk allocation
   491  	largeType             *_type        // malloc header for large objects.
   492  }
   493  
   494  func (s *mspan) base() uintptr {
   495  	return s.startAddr
   496  }
   497  
   498  func (s *mspan) layout() (size, n, total uintptr) {
   499  	total = s.npages << _PageShift
   500  	size = s.elemsize
   501  	if size > 0 {
   502  		n = total / size
   503  	}
   504  	return
   505  }
   506  
   507  // recordspan adds a newly allocated span to h.allspans.
   508  //
   509  // This only happens the first time a span is allocated from
   510  // mheap.spanalloc (it is not called when a span is reused).
   511  //
   512  // Write barriers are disallowed here because it can be called from
   513  // gcWork when allocating new workbufs. However, because it's an
   514  // indirect call from the fixalloc initializer, the compiler can't see
   515  // this.
   516  //
   517  // The heap lock must be held.
   518  //
   519  //go:nowritebarrierrec
   520  func recordspan(vh unsafe.Pointer, p unsafe.Pointer) {
   521  	h := (*mheap)(vh)
   522  	s := (*mspan)(p)
   523  
   524  	assertLockHeld(&h.lock)
   525  
   526  	if len(h.allspans) >= cap(h.allspans) {
   527  		n := 64 * 1024 / goarch.PtrSize
   528  		if n < cap(h.allspans)*3/2 {
   529  			n = cap(h.allspans) * 3 / 2
   530  		}
   531  		var new []*mspan
   532  		sp := (*slice)(unsafe.Pointer(&new))
   533  		sp.array = sysAlloc(uintptr(n)*goarch.PtrSize, &memstats.other_sys)
   534  		if sp.array == nil {
   535  			throw("runtime: cannot allocate memory")
   536  		}
   537  		sp.len = len(h.allspans)
   538  		sp.cap = n
   539  		if len(h.allspans) > 0 {
   540  			copy(new, h.allspans)
   541  		}
   542  		oldAllspans := h.allspans
   543  		*(*notInHeapSlice)(unsafe.Pointer(&h.allspans)) = *(*notInHeapSlice)(unsafe.Pointer(&new))
   544  		if len(oldAllspans) != 0 {
   545  			sysFree(unsafe.Pointer(&oldAllspans[0]), uintptr(cap(oldAllspans))*unsafe.Sizeof(oldAllspans[0]), &memstats.other_sys)
   546  		}
   547  	}
   548  	h.allspans = h.allspans[:len(h.allspans)+1]
   549  	h.allspans[len(h.allspans)-1] = s
   550  }
   551  
   552  // A spanClass represents the size class and noscan-ness of a span.
   553  //
   554  // Each size class has a noscan spanClass and a scan spanClass. The
   555  // noscan spanClass contains only noscan objects, which do not contain
   556  // pointers and thus do not need to be scanned by the garbage
   557  // collector.
   558  type spanClass uint8
   559  
   560  const (
   561  	numSpanClasses = _NumSizeClasses << 1
   562  	tinySpanClass  = spanClass(tinySizeClass<<1 | 1)
   563  )
   564  
   565  func makeSpanClass(sizeclass uint8, noscan bool) spanClass {
   566  	return spanClass(sizeclass<<1) | spanClass(bool2int(noscan))
   567  }
   568  
   569  //go:nosplit
   570  func (sc spanClass) sizeclass() int8 {
   571  	return int8(sc >> 1)
   572  }
   573  
   574  //go:nosplit
   575  func (sc spanClass) noscan() bool {
   576  	return sc&1 != 0
   577  }
   578  
   579  // arenaIndex returns the index into mheap_.arenas of the arena
   580  // containing metadata for p. This index combines of an index into the
   581  // L1 map and an index into the L2 map and should be used as
   582  // mheap_.arenas[ai.l1()][ai.l2()].
   583  //
   584  // If p is outside the range of valid heap addresses, either l1() or
   585  // l2() will be out of bounds.
   586  //
   587  // It is nosplit because it's called by spanOf and several other
   588  // nosplit functions.
   589  //
   590  //go:nosplit
   591  func arenaIndex(p uintptr) arenaIdx {
   592  	return arenaIdx((p - arenaBaseOffset) / heapArenaBytes)
   593  }
   594  
   595  // arenaBase returns the low address of the region covered by heap
   596  // arena i.
   597  func arenaBase(i arenaIdx) uintptr {
   598  	return uintptr(i)*heapArenaBytes + arenaBaseOffset
   599  }
   600  
   601  type arenaIdx uint
   602  
   603  // l1 returns the "l1" portion of an arenaIdx.
   604  //
   605  // Marked nosplit because it's called by spanOf and other nosplit
   606  // functions.
   607  //
   608  //go:nosplit
   609  func (i arenaIdx) l1() uint {
   610  	if arenaL1Bits == 0 {
   611  		// Let the compiler optimize this away if there's no
   612  		// L1 map.
   613  		return 0
   614  	} else {
   615  		return uint(i) >> arenaL1Shift
   616  	}
   617  }
   618  
   619  // l2 returns the "l2" portion of an arenaIdx.
   620  //
   621  // Marked nosplit because it's called by spanOf and other nosplit funcs.
   622  // functions.
   623  //
   624  //go:nosplit
   625  func (i arenaIdx) l2() uint {
   626  	if arenaL1Bits == 0 {
   627  		return uint(i)
   628  	} else {
   629  		return uint(i) & (1<<arenaL2Bits - 1)
   630  	}
   631  }
   632  
   633  // inheap reports whether b is a pointer into a (potentially dead) heap object.
   634  // It returns false for pointers into mSpanManual spans.
   635  // Non-preemptible because it is used by write barriers.
   636  //
   637  //go:nowritebarrier
   638  //go:nosplit
   639  func inheap(b uintptr) bool {
   640  	return spanOfHeap(b) != nil
   641  }
   642  
   643  // inHeapOrStack is a variant of inheap that returns true for pointers
   644  // into any allocated heap span.
   645  //
   646  //go:nowritebarrier
   647  //go:nosplit
   648  func inHeapOrStack(b uintptr) bool {
   649  	s := spanOf(b)
   650  	if s == nil || b < s.base() {
   651  		return false
   652  	}
   653  	switch s.state.get() {
   654  	case mSpanInUse, mSpanManual:
   655  		return b < s.limit
   656  	default:
   657  		return false
   658  	}
   659  }
   660  
   661  // spanOf returns the span of p. If p does not point into the heap
   662  // arena or no span has ever contained p, spanOf returns nil.
   663  //
   664  // If p does not point to allocated memory, this may return a non-nil
   665  // span that does *not* contain p. If this is a possibility, the
   666  // caller should either call spanOfHeap or check the span bounds
   667  // explicitly.
   668  //
   669  // Must be nosplit because it has callers that are nosplit.
   670  //
   671  //go:nosplit
   672  func spanOf(p uintptr) *mspan {
   673  	// This function looks big, but we use a lot of constant
   674  	// folding around arenaL1Bits to get it under the inlining
   675  	// budget. Also, many of the checks here are safety checks
   676  	// that Go needs to do anyway, so the generated code is quite
   677  	// short.
   678  	ri := arenaIndex(p)
   679  	if arenaL1Bits == 0 {
   680  		// If there's no L1, then ri.l1() can't be out of bounds but ri.l2() can.
   681  		if ri.l2() >= uint(len(mheap_.arenas[0])) {
   682  			return nil
   683  		}
   684  	} else {
   685  		// If there's an L1, then ri.l1() can be out of bounds but ri.l2() can't.
   686  		if ri.l1() >= uint(len(mheap_.arenas)) {
   687  			return nil
   688  		}
   689  	}
   690  	l2 := mheap_.arenas[ri.l1()]
   691  	if arenaL1Bits != 0 && l2 == nil { // Should never happen if there's no L1.
   692  		return nil
   693  	}
   694  	ha := l2[ri.l2()]
   695  	if ha == nil {
   696  		return nil
   697  	}
   698  	return ha.spans[(p/pageSize)%pagesPerArena]
   699  }
   700  
   701  // spanOfUnchecked is equivalent to spanOf, but the caller must ensure
   702  // that p points into an allocated heap arena.
   703  //
   704  // Must be nosplit because it has callers that are nosplit.
   705  //
   706  //go:nosplit
   707  func spanOfUnchecked(p uintptr) *mspan {
   708  	ai := arenaIndex(p)
   709  	return mheap_.arenas[ai.l1()][ai.l2()].spans[(p/pageSize)%pagesPerArena]
   710  }
   711  
   712  // spanOfHeap is like spanOf, but returns nil if p does not point to a
   713  // heap object.
   714  //
   715  // Must be nosplit because it has callers that are nosplit.
   716  //
   717  //go:nosplit
   718  func spanOfHeap(p uintptr) *mspan {
   719  	s := spanOf(p)
   720  	// s is nil if it's never been allocated. Otherwise, we check
   721  	// its state first because we don't trust this pointer, so we
   722  	// have to synchronize with span initialization. Then, it's
   723  	// still possible we picked up a stale span pointer, so we
   724  	// have to check the span's bounds.
   725  	if s == nil || s.state.get() != mSpanInUse || p < s.base() || p >= s.limit {
   726  		return nil
   727  	}
   728  	return s
   729  }
   730  
   731  // pageIndexOf returns the arena, page index, and page mask for pointer p.
   732  // The caller must ensure p is in the heap.
   733  func pageIndexOf(p uintptr) (arena *heapArena, pageIdx uintptr, pageMask uint8) {
   734  	ai := arenaIndex(p)
   735  	arena = mheap_.arenas[ai.l1()][ai.l2()]
   736  	pageIdx = ((p / pageSize) / 8) % uintptr(len(arena.pageInUse))
   737  	pageMask = byte(1 << ((p / pageSize) % 8))
   738  	return
   739  }
   740  
   741  // Initialize the heap.
   742  func (h *mheap) init() {
   743  	lockInit(&h.lock, lockRankMheap)
   744  	lockInit(&h.speciallock, lockRankMheapSpecial)
   745  
   746  	h.spanalloc.init(unsafe.Sizeof(mspan{}), recordspan, unsafe.Pointer(h), &memstats.mspan_sys)
   747  	h.cachealloc.init(unsafe.Sizeof(mcache{}), nil, nil, &memstats.mcache_sys)
   748  	h.specialfinalizeralloc.init(unsafe.Sizeof(specialfinalizer{}), nil, nil, &memstats.other_sys)
   749  	h.specialprofilealloc.init(unsafe.Sizeof(specialprofile{}), nil, nil, &memstats.other_sys)
   750  	h.specialReachableAlloc.init(unsafe.Sizeof(specialReachable{}), nil, nil, &memstats.other_sys)
   751  	h.specialPinCounterAlloc.init(unsafe.Sizeof(specialPinCounter{}), nil, nil, &memstats.other_sys)
   752  	h.arenaHintAlloc.init(unsafe.Sizeof(arenaHint{}), nil, nil, &memstats.other_sys)
   753  
   754  	// Don't zero mspan allocations. Background sweeping can
   755  	// inspect a span concurrently with allocating it, so it's
   756  	// important that the span's sweepgen survive across freeing
   757  	// and re-allocating a span to prevent background sweeping
   758  	// from improperly cas'ing it from 0.
   759  	//
   760  	// This is safe because mspan contains no heap pointers.
   761  	h.spanalloc.zero = false
   762  
   763  	// h->mapcache needs no init
   764  
   765  	for i := range h.central {
   766  		h.central[i].mcentral.init(spanClass(i))
   767  	}
   768  
   769  	h.pages.init(&h.lock, &memstats.gcMiscSys, false)
   770  }
   771  
   772  // reclaim sweeps and reclaims at least npage pages into the heap.
   773  // It is called before allocating npage pages to keep growth in check.
   774  //
   775  // reclaim implements the page-reclaimer half of the sweeper.
   776  //
   777  // h.lock must NOT be held.
   778  func (h *mheap) reclaim(npage uintptr) {
   779  	// TODO(austin): Half of the time spent freeing spans is in
   780  	// locking/unlocking the heap (even with low contention). We
   781  	// could make the slow path here several times faster by
   782  	// batching heap frees.
   783  
   784  	// Bail early if there's no more reclaim work.
   785  	if h.reclaimIndex.Load() >= 1<<63 {
   786  		return
   787  	}
   788  
   789  	// Disable preemption so the GC can't start while we're
   790  	// sweeping, so we can read h.sweepArenas, and so
   791  	// traceGCSweepStart/Done pair on the P.
   792  	mp := acquirem()
   793  
   794  	trace := traceAcquire()
   795  	if trace.ok() {
   796  		trace.GCSweepStart()
   797  		traceRelease(trace)
   798  	}
   799  
   800  	arenas := h.sweepArenas
   801  	locked := false
   802  	for npage > 0 {
   803  		// Pull from accumulated credit first.
   804  		if credit := h.reclaimCredit.Load(); credit > 0 {
   805  			take := credit
   806  			if take > npage {
   807  				// Take only what we need.
   808  				take = npage
   809  			}
   810  			if h.reclaimCredit.CompareAndSwap(credit, credit-take) {
   811  				npage -= take
   812  			}
   813  			continue
   814  		}
   815  
   816  		// Claim a chunk of work.
   817  		idx := uintptr(h.reclaimIndex.Add(pagesPerReclaimerChunk) - pagesPerReclaimerChunk)
   818  		if idx/pagesPerArena >= uintptr(len(arenas)) {
   819  			// Page reclaiming is done.
   820  			h.reclaimIndex.Store(1 << 63)
   821  			break
   822  		}
   823  
   824  		if !locked {
   825  			// Lock the heap for reclaimChunk.
   826  			lock(&h.lock)
   827  			locked = true
   828  		}
   829  
   830  		// Scan this chunk.
   831  		nfound := h.reclaimChunk(arenas, idx, pagesPerReclaimerChunk)
   832  		if nfound <= npage {
   833  			npage -= nfound
   834  		} else {
   835  			// Put spare pages toward global credit.
   836  			h.reclaimCredit.Add(nfound - npage)
   837  			npage = 0
   838  		}
   839  	}
   840  	if locked {
   841  		unlock(&h.lock)
   842  	}
   843  
   844  	trace = traceAcquire()
   845  	if trace.ok() {
   846  		trace.GCSweepDone()
   847  		traceRelease(trace)
   848  	}
   849  	releasem(mp)
   850  }
   851  
   852  // reclaimChunk sweeps unmarked spans that start at page indexes [pageIdx, pageIdx+n).
   853  // It returns the number of pages returned to the heap.
   854  //
   855  // h.lock must be held and the caller must be non-preemptible. Note: h.lock may be
   856  // temporarily unlocked and re-locked in order to do sweeping or if tracing is
   857  // enabled.
   858  func (h *mheap) reclaimChunk(arenas []arenaIdx, pageIdx, n uintptr) uintptr {
   859  	// The heap lock must be held because this accesses the
   860  	// heapArena.spans arrays using potentially non-live pointers.
   861  	// In particular, if a span were freed and merged concurrently
   862  	// with this probing heapArena.spans, it would be possible to
   863  	// observe arbitrary, stale span pointers.
   864  	assertLockHeld(&h.lock)
   865  
   866  	n0 := n
   867  	var nFreed uintptr
   868  	sl := sweep.active.begin()
   869  	if !sl.valid {
   870  		return 0
   871  	}
   872  	for n > 0 {
   873  		ai := arenas[pageIdx/pagesPerArena]
   874  		ha := h.arenas[ai.l1()][ai.l2()]
   875  
   876  		// Get a chunk of the bitmap to work on.
   877  		arenaPage := uint(pageIdx % pagesPerArena)
   878  		inUse := ha.pageInUse[arenaPage/8:]
   879  		marked := ha.pageMarks[arenaPage/8:]
   880  		if uintptr(len(inUse)) > n/8 {
   881  			inUse = inUse[:n/8]
   882  			marked = marked[:n/8]
   883  		}
   884  
   885  		// Scan this bitmap chunk for spans that are in-use
   886  		// but have no marked objects on them.
   887  		for i := range inUse {
   888  			inUseUnmarked := atomic.Load8(&inUse[i]) &^ marked[i]
   889  			if inUseUnmarked == 0 {
   890  				continue
   891  			}
   892  
   893  			for j := uint(0); j < 8; j++ {
   894  				if inUseUnmarked&(1<<j) != 0 {
   895  					s := ha.spans[arenaPage+uint(i)*8+j]
   896  					if s, ok := sl.tryAcquire(s); ok {
   897  						npages := s.npages
   898  						unlock(&h.lock)
   899  						if s.sweep(false) {
   900  							nFreed += npages
   901  						}
   902  						lock(&h.lock)
   903  						// Reload inUse. It's possible nearby
   904  						// spans were freed when we dropped the
   905  						// lock and we don't want to get stale
   906  						// pointers from the spans array.
   907  						inUseUnmarked = atomic.Load8(&inUse[i]) &^ marked[i]
   908  					}
   909  				}
   910  			}
   911  		}
   912  
   913  		// Advance.
   914  		pageIdx += uintptr(len(inUse) * 8)
   915  		n -= uintptr(len(inUse) * 8)
   916  	}
   917  	sweep.active.end(sl)
   918  	trace := traceAcquire()
   919  	if trace.ok() {
   920  		unlock(&h.lock)
   921  		// Account for pages scanned but not reclaimed.
   922  		trace.GCSweepSpan((n0 - nFreed) * pageSize)
   923  		traceRelease(trace)
   924  		lock(&h.lock)
   925  	}
   926  
   927  	assertLockHeld(&h.lock) // Must be locked on return.
   928  	return nFreed
   929  }
   930  
   931  // spanAllocType represents the type of allocation to make, or
   932  // the type of allocation to be freed.
   933  type spanAllocType uint8
   934  
   935  const (
   936  	spanAllocHeap          spanAllocType = iota // heap span
   937  	spanAllocStack                              // stack span
   938  	spanAllocPtrScalarBits                      // unrolled GC prog bitmap span
   939  	spanAllocWorkBuf                            // work buf span
   940  )
   941  
   942  // manual returns true if the span allocation is manually managed.
   943  func (s spanAllocType) manual() bool {
   944  	return s != spanAllocHeap
   945  }
   946  
   947  // alloc allocates a new span of npage pages from the GC'd heap.
   948  //
   949  // spanclass indicates the span's size class and scannability.
   950  //
   951  // Returns a span that has been fully initialized. span.needzero indicates
   952  // whether the span has been zeroed. Note that it may not be.
   953  func (h *mheap) alloc(npages uintptr, spanclass spanClass) *mspan {
   954  	// Don't do any operations that lock the heap on the G stack.
   955  	// It might trigger stack growth, and the stack growth code needs
   956  	// to be able to allocate heap.
   957  	var s *mspan
   958  	systemstack(func() {
   959  		// To prevent excessive heap growth, before allocating n pages
   960  		// we need to sweep and reclaim at least n pages.
   961  		if !isSweepDone() {
   962  			h.reclaim(npages)
   963  		}
   964  		s = h.allocSpan(npages, spanAllocHeap, spanclass)
   965  	})
   966  	return s
   967  }
   968  
   969  // allocManual allocates a manually-managed span of npage pages.
   970  // allocManual returns nil if allocation fails.
   971  //
   972  // allocManual adds the bytes used to *stat, which should be a
   973  // memstats in-use field. Unlike allocations in the GC'd heap, the
   974  // allocation does *not* count toward heapInUse.
   975  //
   976  // The memory backing the returned span may not be zeroed if
   977  // span.needzero is set.
   978  //
   979  // allocManual must be called on the system stack because it may
   980  // acquire the heap lock via allocSpan. See mheap for details.
   981  //
   982  // If new code is written to call allocManual, do NOT use an
   983  // existing spanAllocType value and instead declare a new one.
   984  //
   985  //go:systemstack
   986  func (h *mheap) allocManual(npages uintptr, typ spanAllocType) *mspan {
   987  	if !typ.manual() {
   988  		throw("manual span allocation called with non-manually-managed type")
   989  	}
   990  	return h.allocSpan(npages, typ, 0)
   991  }
   992  
   993  // setSpans modifies the span map so [spanOf(base), spanOf(base+npage*pageSize))
   994  // is s.
   995  func (h *mheap) setSpans(base, npage uintptr, s *mspan) {
   996  	p := base / pageSize
   997  	ai := arenaIndex(base)
   998  	ha := h.arenas[ai.l1()][ai.l2()]
   999  	for n := uintptr(0); n < npage; n++ {
  1000  		i := (p + n) % pagesPerArena
  1001  		if i == 0 {
  1002  			ai = arenaIndex(base + n*pageSize)
  1003  			ha = h.arenas[ai.l1()][ai.l2()]
  1004  		}
  1005  		ha.spans[i] = s
  1006  	}
  1007  }
  1008  
  1009  // allocNeedsZero checks if the region of address space [base, base+npage*pageSize),
  1010  // assumed to be allocated, needs to be zeroed, updating heap arena metadata for
  1011  // future allocations.
  1012  //
  1013  // This must be called each time pages are allocated from the heap, even if the page
  1014  // allocator can otherwise prove the memory it's allocating is already zero because
  1015  // they're fresh from the operating system. It updates heapArena metadata that is
  1016  // critical for future page allocations.
  1017  //
  1018  // There are no locking constraints on this method.
  1019  func (h *mheap) allocNeedsZero(base, npage uintptr) (needZero bool) {
  1020  	for npage > 0 {
  1021  		ai := arenaIndex(base)
  1022  		ha := h.arenas[ai.l1()][ai.l2()]
  1023  
  1024  		zeroedBase := atomic.Loaduintptr(&ha.zeroedBase)
  1025  		arenaBase := base % heapArenaBytes
  1026  		if arenaBase < zeroedBase {
  1027  			// We extended into the non-zeroed part of the
  1028  			// arena, so this region needs to be zeroed before use.
  1029  			//
  1030  			// zeroedBase is monotonically increasing, so if we see this now then
  1031  			// we can be sure we need to zero this memory region.
  1032  			//
  1033  			// We still need to update zeroedBase for this arena, and
  1034  			// potentially more arenas.
  1035  			needZero = true
  1036  		}
  1037  		// We may observe arenaBase > zeroedBase if we're racing with one or more
  1038  		// allocations which are acquiring memory directly before us in the address
  1039  		// space. But, because we know no one else is acquiring *this* memory, it's
  1040  		// still safe to not zero.
  1041  
  1042  		// Compute how far into the arena we extend into, capped
  1043  		// at heapArenaBytes.
  1044  		arenaLimit := arenaBase + npage*pageSize
  1045  		if arenaLimit > heapArenaBytes {
  1046  			arenaLimit = heapArenaBytes
  1047  		}
  1048  		// Increase ha.zeroedBase so it's >= arenaLimit.
  1049  		// We may be racing with other updates.
  1050  		for arenaLimit > zeroedBase {
  1051  			if atomic.Casuintptr(&ha.zeroedBase, zeroedBase, arenaLimit) {
  1052  				break
  1053  			}
  1054  			zeroedBase = atomic.Loaduintptr(&ha.zeroedBase)
  1055  			// Double check basic conditions of zeroedBase.
  1056  			if zeroedBase <= arenaLimit && zeroedBase > arenaBase {
  1057  				// The zeroedBase moved into the space we were trying to
  1058  				// claim. That's very bad, and indicates someone allocated
  1059  				// the same region we did.
  1060  				throw("potentially overlapping in-use allocations detected")
  1061  			}
  1062  		}
  1063  
  1064  		// Move base forward and subtract from npage to move into
  1065  		// the next arena, or finish.
  1066  		base += arenaLimit - arenaBase
  1067  		npage -= (arenaLimit - arenaBase) / pageSize
  1068  	}
  1069  	return
  1070  }
  1071  
  1072  // tryAllocMSpan attempts to allocate an mspan object from
  1073  // the P-local cache, but may fail.
  1074  //
  1075  // h.lock need not be held.
  1076  //
  1077  // This caller must ensure that its P won't change underneath
  1078  // it during this function. Currently to ensure that we enforce
  1079  // that the function is run on the system stack, because that's
  1080  // the only place it is used now. In the future, this requirement
  1081  // may be relaxed if its use is necessary elsewhere.
  1082  //
  1083  //go:systemstack
  1084  func (h *mheap) tryAllocMSpan() *mspan {
  1085  	pp := getg().m.p.ptr()
  1086  	// If we don't have a p or the cache is empty, we can't do
  1087  	// anything here.
  1088  	if pp == nil || pp.mspancache.len == 0 {
  1089  		return nil
  1090  	}
  1091  	// Pull off the last entry in the cache.
  1092  	s := pp.mspancache.buf[pp.mspancache.len-1]
  1093  	pp.mspancache.len--
  1094  	return s
  1095  }
  1096  
  1097  // allocMSpanLocked allocates an mspan object.
  1098  //
  1099  // h.lock must be held.
  1100  //
  1101  // allocMSpanLocked must be called on the system stack because
  1102  // its caller holds the heap lock. See mheap for details.
  1103  // Running on the system stack also ensures that we won't
  1104  // switch Ps during this function. See tryAllocMSpan for details.
  1105  //
  1106  //go:systemstack
  1107  func (h *mheap) allocMSpanLocked() *mspan {
  1108  	assertLockHeld(&h.lock)
  1109  
  1110  	pp := getg().m.p.ptr()
  1111  	if pp == nil {
  1112  		// We don't have a p so just do the normal thing.
  1113  		return (*mspan)(h.spanalloc.alloc())
  1114  	}
  1115  	// Refill the cache if necessary.
  1116  	if pp.mspancache.len == 0 {
  1117  		const refillCount = len(pp.mspancache.buf) / 2
  1118  		for i := 0; i < refillCount; i++ {
  1119  			pp.mspancache.buf[i] = (*mspan)(h.spanalloc.alloc())
  1120  		}
  1121  		pp.mspancache.len = refillCount
  1122  	}
  1123  	// Pull off the last entry in the cache.
  1124  	s := pp.mspancache.buf[pp.mspancache.len-1]
  1125  	pp.mspancache.len--
  1126  	return s
  1127  }
  1128  
  1129  // freeMSpanLocked free an mspan object.
  1130  //
  1131  // h.lock must be held.
  1132  //
  1133  // freeMSpanLocked must be called on the system stack because
  1134  // its caller holds the heap lock. See mheap for details.
  1135  // Running on the system stack also ensures that we won't
  1136  // switch Ps during this function. See tryAllocMSpan for details.
  1137  //
  1138  //go:systemstack
  1139  func (h *mheap) freeMSpanLocked(s *mspan) {
  1140  	assertLockHeld(&h.lock)
  1141  
  1142  	pp := getg().m.p.ptr()
  1143  	// First try to free the mspan directly to the cache.
  1144  	if pp != nil && pp.mspancache.len < len(pp.mspancache.buf) {
  1145  		pp.mspancache.buf[pp.mspancache.len] = s
  1146  		pp.mspancache.len++
  1147  		return
  1148  	}
  1149  	// Failing that (or if we don't have a p), just free it to
  1150  	// the heap.
  1151  	h.spanalloc.free(unsafe.Pointer(s))
  1152  }
  1153  
  1154  // allocSpan allocates an mspan which owns npages worth of memory.
  1155  //
  1156  // If typ.manual() == false, allocSpan allocates a heap span of class spanclass
  1157  // and updates heap accounting. If manual == true, allocSpan allocates a
  1158  // manually-managed span (spanclass is ignored), and the caller is
  1159  // responsible for any accounting related to its use of the span. Either
  1160  // way, allocSpan will atomically add the bytes in the newly allocated
  1161  // span to *sysStat.
  1162  //
  1163  // The returned span is fully initialized.
  1164  //
  1165  // h.lock must not be held.
  1166  //
  1167  // allocSpan must be called on the system stack both because it acquires
  1168  // the heap lock and because it must block GC transitions.
  1169  //
  1170  //go:systemstack
  1171  func (h *mheap) allocSpan(npages uintptr, typ spanAllocType, spanclass spanClass) (s *mspan) {
  1172  	// Function-global state.
  1173  	gp := getg()
  1174  	base, scav := uintptr(0), uintptr(0)
  1175  	growth := uintptr(0)
  1176  
  1177  	// On some platforms we need to provide physical page aligned stack
  1178  	// allocations. Where the page size is less than the physical page
  1179  	// size, we already manage to do this by default.
  1180  	needPhysPageAlign := physPageAlignedStacks && typ == spanAllocStack && pageSize < physPageSize
  1181  
  1182  	// If the allocation is small enough, try the page cache!
  1183  	// The page cache does not support aligned allocations, so we cannot use
  1184  	// it if we need to provide a physical page aligned stack allocation.
  1185  	pp := gp.m.p.ptr()
  1186  	if !needPhysPageAlign && pp != nil && npages < pageCachePages/4 {
  1187  		c := &pp.pcache
  1188  
  1189  		// If the cache is empty, refill it.
  1190  		if c.empty() {
  1191  			lock(&h.lock)
  1192  			*c = h.pages.allocToCache()
  1193  			unlock(&h.lock)
  1194  		}
  1195  
  1196  		// Try to allocate from the cache.
  1197  		base, scav = c.alloc(npages)
  1198  		if base != 0 {
  1199  			s = h.tryAllocMSpan()
  1200  			if s != nil {
  1201  				goto HaveSpan
  1202  			}
  1203  			// We have a base but no mspan, so we need
  1204  			// to lock the heap.
  1205  		}
  1206  	}
  1207  
  1208  	// For one reason or another, we couldn't get the
  1209  	// whole job done without the heap lock.
  1210  	lock(&h.lock)
  1211  
  1212  	if needPhysPageAlign {
  1213  		// Overallocate by a physical page to allow for later alignment.
  1214  		extraPages := physPageSize / pageSize
  1215  
  1216  		// Find a big enough region first, but then only allocate the
  1217  		// aligned portion. We can't just allocate and then free the
  1218  		// edges because we need to account for scavenged memory, and
  1219  		// that's difficult with alloc.
  1220  		//
  1221  		// Note that we skip updates to searchAddr here. It's OK if
  1222  		// it's stale and higher than normal; it'll operate correctly,
  1223  		// just come with a performance cost.
  1224  		base, _ = h.pages.find(npages + extraPages)
  1225  		if base == 0 {
  1226  			var ok bool
  1227  			growth, ok = h.grow(npages + extraPages)
  1228  			if !ok {
  1229  				unlock(&h.lock)
  1230  				return nil
  1231  			}
  1232  			base, _ = h.pages.find(npages + extraPages)
  1233  			if base == 0 {
  1234  				throw("grew heap, but no adequate free space found")
  1235  			}
  1236  		}
  1237  		base = alignUp(base, physPageSize)
  1238  		scav = h.pages.allocRange(base, npages)
  1239  	}
  1240  
  1241  	if base == 0 {
  1242  		// Try to acquire a base address.
  1243  		base, scav = h.pages.alloc(npages)
  1244  		if base == 0 {
  1245  			var ok bool
  1246  			growth, ok = h.grow(npages)
  1247  			if !ok {
  1248  				unlock(&h.lock)
  1249  				return nil
  1250  			}
  1251  			base, scav = h.pages.alloc(npages)
  1252  			if base == 0 {
  1253  				throw("grew heap, but no adequate free space found")
  1254  			}
  1255  		}
  1256  	}
  1257  	if s == nil {
  1258  		// We failed to get an mspan earlier, so grab
  1259  		// one now that we have the heap lock.
  1260  		s = h.allocMSpanLocked()
  1261  	}
  1262  	unlock(&h.lock)
  1263  
  1264  HaveSpan:
  1265  	// Decide if we need to scavenge in response to what we just allocated.
  1266  	// Specifically, we track the maximum amount of memory to scavenge of all
  1267  	// the alternatives below, assuming that the maximum satisfies *all*
  1268  	// conditions we check (e.g. if we need to scavenge X to satisfy the
  1269  	// memory limit and Y to satisfy heap-growth scavenging, and Y > X, then
  1270  	// it's fine to pick Y, because the memory limit is still satisfied).
  1271  	//
  1272  	// It's fine to do this after allocating because we expect any scavenged
  1273  	// pages not to get touched until we return. Simultaneously, it's important
  1274  	// to do this before calling sysUsed because that may commit address space.
  1275  	bytesToScavenge := uintptr(0)
  1276  	forceScavenge := false
  1277  	if limit := gcController.memoryLimit.Load(); !gcCPULimiter.limiting() {
  1278  		// Assist with scavenging to maintain the memory limit by the amount
  1279  		// that we expect to page in.
  1280  		inuse := gcController.mappedReady.Load()
  1281  		// Be careful about overflow, especially with uintptrs. Even on 32-bit platforms
  1282  		// someone can set a really big memory limit that isn't maxInt64.
  1283  		if uint64(scav)+inuse > uint64(limit) {
  1284  			bytesToScavenge = uintptr(uint64(scav) + inuse - uint64(limit))
  1285  			forceScavenge = true
  1286  		}
  1287  	}
  1288  	if goal := scavenge.gcPercentGoal.Load(); goal != ^uint64(0) && growth > 0 {
  1289  		// We just caused a heap growth, so scavenge down what will soon be used.
  1290  		// By scavenging inline we deal with the failure to allocate out of
  1291  		// memory fragments by scavenging the memory fragments that are least
  1292  		// likely to be re-used.
  1293  		//
  1294  		// Only bother with this because we're not using a memory limit. We don't
  1295  		// care about heap growths as long as we're under the memory limit, and the
  1296  		// previous check for scaving already handles that.
  1297  		if retained := heapRetained(); retained+uint64(growth) > goal {
  1298  			// The scavenging algorithm requires the heap lock to be dropped so it
  1299  			// can acquire it only sparingly. This is a potentially expensive operation
  1300  			// so it frees up other goroutines to allocate in the meanwhile. In fact,
  1301  			// they can make use of the growth we just created.
  1302  			todo := growth
  1303  			if overage := uintptr(retained + uint64(growth) - goal); todo > overage {
  1304  				todo = overage
  1305  			}
  1306  			if todo > bytesToScavenge {
  1307  				bytesToScavenge = todo
  1308  			}
  1309  		}
  1310  	}
  1311  	// There are a few very limited circumstances where we won't have a P here.
  1312  	// It's OK to simply skip scavenging in these cases. Something else will notice
  1313  	// and pick up the tab.
  1314  	var now int64
  1315  	if pp != nil && bytesToScavenge > 0 {
  1316  		// Measure how long we spent scavenging and add that measurement to the assist
  1317  		// time so we can track it for the GC CPU limiter.
  1318  		//
  1319  		// Limiter event tracking might be disabled if we end up here
  1320  		// while on a mark worker.
  1321  		start := nanotime()
  1322  		track := pp.limiterEvent.start(limiterEventScavengeAssist, start)
  1323  
  1324  		// Scavenge, but back out if the limiter turns on.
  1325  		released := h.pages.scavenge(bytesToScavenge, func() bool {
  1326  			return gcCPULimiter.limiting()
  1327  		}, forceScavenge)
  1328  
  1329  		mheap_.pages.scav.releasedEager.Add(released)
  1330  
  1331  		// Finish up accounting.
  1332  		now = nanotime()
  1333  		if track {
  1334  			pp.limiterEvent.stop(limiterEventScavengeAssist, now)
  1335  		}
  1336  		scavenge.assistTime.Add(now - start)
  1337  	}
  1338  
  1339  	// Initialize the span.
  1340  	h.initSpan(s, typ, spanclass, base, npages)
  1341  
  1342  	// Commit and account for any scavenged memory that the span now owns.
  1343  	nbytes := npages * pageSize
  1344  	if scav != 0 {
  1345  		// sysUsed all the pages that are actually available
  1346  		// in the span since some of them might be scavenged.
  1347  		sysUsed(unsafe.Pointer(base), nbytes, scav)
  1348  		gcController.heapReleased.add(-int64(scav))
  1349  	}
  1350  	// Update stats.
  1351  	gcController.heapFree.add(-int64(nbytes - scav))
  1352  	if typ == spanAllocHeap {
  1353  		gcController.heapInUse.add(int64(nbytes))
  1354  	}
  1355  	// Update consistent stats.
  1356  	stats := memstats.heapStats.acquire()
  1357  	atomic.Xaddint64(&stats.committed, int64(scav))
  1358  	atomic.Xaddint64(&stats.released, -int64(scav))
  1359  	switch typ {
  1360  	case spanAllocHeap:
  1361  		atomic.Xaddint64(&stats.inHeap, int64(nbytes))
  1362  	case spanAllocStack:
  1363  		atomic.Xaddint64(&stats.inStacks, int64(nbytes))
  1364  	case spanAllocPtrScalarBits:
  1365  		atomic.Xaddint64(&stats.inPtrScalarBits, int64(nbytes))
  1366  	case spanAllocWorkBuf:
  1367  		atomic.Xaddint64(&stats.inWorkBufs, int64(nbytes))
  1368  	}
  1369  	memstats.heapStats.release()
  1370  
  1371  	pageTraceAlloc(pp, now, base, npages)
  1372  	return s
  1373  }
  1374  
  1375  // initSpan initializes a blank span s which will represent the range
  1376  // [base, base+npages*pageSize). typ is the type of span being allocated.
  1377  func (h *mheap) initSpan(s *mspan, typ spanAllocType, spanclass spanClass, base, npages uintptr) {
  1378  	// At this point, both s != nil and base != 0, and the heap
  1379  	// lock is no longer held. Initialize the span.
  1380  	s.init(base, npages)
  1381  	if h.allocNeedsZero(base, npages) {
  1382  		s.needzero = 1
  1383  	}
  1384  	nbytes := npages * pageSize
  1385  	if typ.manual() {
  1386  		s.manualFreeList = 0
  1387  		s.nelems = 0
  1388  		s.limit = s.base() + s.npages*pageSize
  1389  		s.state.set(mSpanManual)
  1390  	} else {
  1391  		// We must set span properties before the span is published anywhere
  1392  		// since we're not holding the heap lock.
  1393  		s.spanclass = spanclass
  1394  		if sizeclass := spanclass.sizeclass(); sizeclass == 0 {
  1395  			s.elemsize = nbytes
  1396  			s.nelems = 1
  1397  			s.divMul = 0
  1398  		} else {
  1399  			s.elemsize = uintptr(class_to_size[sizeclass])
  1400  			if goexperiment.AllocHeaders && !s.spanclass.noscan() && heapBitsInSpan(s.elemsize) {
  1401  				// In the allocheaders experiment, reserve space for the pointer/scan bitmap at the end.
  1402  				s.nelems = uint16((nbytes - (nbytes / goarch.PtrSize / 8)) / s.elemsize)
  1403  			} else {
  1404  				s.nelems = uint16(nbytes / s.elemsize)
  1405  			}
  1406  			s.divMul = class_to_divmagic[sizeclass]
  1407  		}
  1408  
  1409  		// Initialize mark and allocation structures.
  1410  		s.freeindex = 0
  1411  		s.freeIndexForScan = 0
  1412  		s.allocCache = ^uint64(0) // all 1s indicating all free.
  1413  		s.gcmarkBits = newMarkBits(uintptr(s.nelems))
  1414  		s.allocBits = newAllocBits(uintptr(s.nelems))
  1415  
  1416  		// It's safe to access h.sweepgen without the heap lock because it's
  1417  		// only ever updated with the world stopped and we run on the
  1418  		// systemstack which blocks a STW transition.
  1419  		atomic.Store(&s.sweepgen, h.sweepgen)
  1420  
  1421  		// Now that the span is filled in, set its state. This
  1422  		// is a publication barrier for the other fields in
  1423  		// the span. While valid pointers into this span
  1424  		// should never be visible until the span is returned,
  1425  		// if the garbage collector finds an invalid pointer,
  1426  		// access to the span may race with initialization of
  1427  		// the span. We resolve this race by atomically
  1428  		// setting the state after the span is fully
  1429  		// initialized, and atomically checking the state in
  1430  		// any situation where a pointer is suspect.
  1431  		s.state.set(mSpanInUse)
  1432  	}
  1433  
  1434  	// Publish the span in various locations.
  1435  
  1436  	// This is safe to call without the lock held because the slots
  1437  	// related to this span will only ever be read or modified by
  1438  	// this thread until pointers into the span are published (and
  1439  	// we execute a publication barrier at the end of this function
  1440  	// before that happens) or pageInUse is updated.
  1441  	h.setSpans(s.base(), npages, s)
  1442  
  1443  	if !typ.manual() {
  1444  		// Mark in-use span in arena page bitmap.
  1445  		//
  1446  		// This publishes the span to the page sweeper, so
  1447  		// it's imperative that the span be completely initialized
  1448  		// prior to this line.
  1449  		arena, pageIdx, pageMask := pageIndexOf(s.base())
  1450  		atomic.Or8(&arena.pageInUse[pageIdx], pageMask)
  1451  
  1452  		// Update related page sweeper stats.
  1453  		h.pagesInUse.Add(npages)
  1454  	}
  1455  
  1456  	// Make sure the newly allocated span will be observed
  1457  	// by the GC before pointers into the span are published.
  1458  	publicationBarrier()
  1459  }
  1460  
  1461  // Try to add at least npage pages of memory to the heap,
  1462  // returning how much the heap grew by and whether it worked.
  1463  //
  1464  // h.lock must be held.
  1465  func (h *mheap) grow(npage uintptr) (uintptr, bool) {
  1466  	assertLockHeld(&h.lock)
  1467  
  1468  	// We must grow the heap in whole palloc chunks.
  1469  	// We call sysMap below but note that because we
  1470  	// round up to pallocChunkPages which is on the order
  1471  	// of MiB (generally >= to the huge page size) we
  1472  	// won't be calling it too much.
  1473  	ask := alignUp(npage, pallocChunkPages) * pageSize
  1474  
  1475  	totalGrowth := uintptr(0)
  1476  	// This may overflow because ask could be very large
  1477  	// and is otherwise unrelated to h.curArena.base.
  1478  	end := h.curArena.base + ask
  1479  	nBase := alignUp(end, physPageSize)
  1480  	if nBase > h.curArena.end || /* overflow */ end < h.curArena.base {
  1481  		// Not enough room in the current arena. Allocate more
  1482  		// arena space. This may not be contiguous with the
  1483  		// current arena, so we have to request the full ask.
  1484  		av, asize := h.sysAlloc(ask, &h.arenaHints, true)
  1485  		if av == nil {
  1486  			inUse := gcController.heapFree.load() + gcController.heapReleased.load() + gcController.heapInUse.load()
  1487  			print("runtime: out of memory: cannot allocate ", ask, "-byte block (", inUse, " in use)\n")
  1488  			return 0, false
  1489  		}
  1490  
  1491  		if uintptr(av) == h.curArena.end {
  1492  			// The new space is contiguous with the old
  1493  			// space, so just extend the current space.
  1494  			h.curArena.end = uintptr(av) + asize
  1495  		} else {
  1496  			// The new space is discontiguous. Track what
  1497  			// remains of the current space and switch to
  1498  			// the new space. This should be rare.
  1499  			if size := h.curArena.end - h.curArena.base; size != 0 {
  1500  				// Transition this space from Reserved to Prepared and mark it
  1501  				// as released since we'll be able to start using it after updating
  1502  				// the page allocator and releasing the lock at any time.
  1503  				sysMap(unsafe.Pointer(h.curArena.base), size, &gcController.heapReleased)
  1504  				// Update stats.
  1505  				stats := memstats.heapStats.acquire()
  1506  				atomic.Xaddint64(&stats.released, int64(size))
  1507  				memstats.heapStats.release()
  1508  				// Update the page allocator's structures to make this
  1509  				// space ready for allocation.
  1510  				h.pages.grow(h.curArena.base, size)
  1511  				totalGrowth += size
  1512  			}
  1513  			// Switch to the new space.
  1514  			h.curArena.base = uintptr(av)
  1515  			h.curArena.end = uintptr(av) + asize
  1516  		}
  1517  
  1518  		// Recalculate nBase.
  1519  		// We know this won't overflow, because sysAlloc returned
  1520  		// a valid region starting at h.curArena.base which is at
  1521  		// least ask bytes in size.
  1522  		nBase = alignUp(h.curArena.base+ask, physPageSize)
  1523  	}
  1524  
  1525  	// Grow into the current arena.
  1526  	v := h.curArena.base
  1527  	h.curArena.base = nBase
  1528  
  1529  	// Transition the space we're going to use from Reserved to Prepared.
  1530  	//
  1531  	// The allocation is always aligned to the heap arena
  1532  	// size which is always > physPageSize, so its safe to
  1533  	// just add directly to heapReleased.
  1534  	sysMap(unsafe.Pointer(v), nBase-v, &gcController.heapReleased)
  1535  
  1536  	// The memory just allocated counts as both released
  1537  	// and idle, even though it's not yet backed by spans.
  1538  	stats := memstats.heapStats.acquire()
  1539  	atomic.Xaddint64(&stats.released, int64(nBase-v))
  1540  	memstats.heapStats.release()
  1541  
  1542  	// Update the page allocator's structures to make this
  1543  	// space ready for allocation.
  1544  	h.pages.grow(v, nBase-v)
  1545  	totalGrowth += nBase - v
  1546  	return totalGrowth, true
  1547  }
  1548  
  1549  // Free the span back into the heap.
  1550  func (h *mheap) freeSpan(s *mspan) {
  1551  	systemstack(func() {
  1552  		pageTraceFree(getg().m.p.ptr(), 0, s.base(), s.npages)
  1553  
  1554  		lock(&h.lock)
  1555  		if msanenabled {
  1556  			// Tell msan that this entire span is no longer in use.
  1557  			base := unsafe.Pointer(s.base())
  1558  			bytes := s.npages << _PageShift
  1559  			msanfree(base, bytes)
  1560  		}
  1561  		if asanenabled {
  1562  			// Tell asan that this entire span is no longer in use.
  1563  			base := unsafe.Pointer(s.base())
  1564  			bytes := s.npages << _PageShift
  1565  			asanpoison(base, bytes)
  1566  		}
  1567  		h.freeSpanLocked(s, spanAllocHeap)
  1568  		unlock(&h.lock)
  1569  	})
  1570  }
  1571  
  1572  // freeManual frees a manually-managed span returned by allocManual.
  1573  // typ must be the same as the spanAllocType passed to the allocManual that
  1574  // allocated s.
  1575  //
  1576  // This must only be called when gcphase == _GCoff. See mSpanState for
  1577  // an explanation.
  1578  //
  1579  // freeManual must be called on the system stack because it acquires
  1580  // the heap lock. See mheap for details.
  1581  //
  1582  //go:systemstack
  1583  func (h *mheap) freeManual(s *mspan, typ spanAllocType) {
  1584  	pageTraceFree(getg().m.p.ptr(), 0, s.base(), s.npages)
  1585  
  1586  	s.needzero = 1
  1587  	lock(&h.lock)
  1588  	h.freeSpanLocked(s, typ)
  1589  	unlock(&h.lock)
  1590  }
  1591  
  1592  func (h *mheap) freeSpanLocked(s *mspan, typ spanAllocType) {
  1593  	assertLockHeld(&h.lock)
  1594  
  1595  	switch s.state.get() {
  1596  	case mSpanManual:
  1597  		if s.allocCount != 0 {
  1598  			throw("mheap.freeSpanLocked - invalid stack free")
  1599  		}
  1600  	case mSpanInUse:
  1601  		if s.isUserArenaChunk {
  1602  			throw("mheap.freeSpanLocked - invalid free of user arena chunk")
  1603  		}
  1604  		if s.allocCount != 0 || s.sweepgen != h.sweepgen {
  1605  			print("mheap.freeSpanLocked - span ", s, " ptr ", hex(s.base()), " allocCount ", s.allocCount, " sweepgen ", s.sweepgen, "/", h.sweepgen, "\n")
  1606  			throw("mheap.freeSpanLocked - invalid free")
  1607  		}
  1608  		h.pagesInUse.Add(-s.npages)
  1609  
  1610  		// Clear in-use bit in arena page bitmap.
  1611  		arena, pageIdx, pageMask := pageIndexOf(s.base())
  1612  		atomic.And8(&arena.pageInUse[pageIdx], ^pageMask)
  1613  	default:
  1614  		throw("mheap.freeSpanLocked - invalid span state")
  1615  	}
  1616  
  1617  	// Update stats.
  1618  	//
  1619  	// Mirrors the code in allocSpan.
  1620  	nbytes := s.npages * pageSize
  1621  	gcController.heapFree.add(int64(nbytes))
  1622  	if typ == spanAllocHeap {
  1623  		gcController.heapInUse.add(-int64(nbytes))
  1624  	}
  1625  	// Update consistent stats.
  1626  	stats := memstats.heapStats.acquire()
  1627  	switch typ {
  1628  	case spanAllocHeap:
  1629  		atomic.Xaddint64(&stats.inHeap, -int64(nbytes))
  1630  	case spanAllocStack:
  1631  		atomic.Xaddint64(&stats.inStacks, -int64(nbytes))
  1632  	case spanAllocPtrScalarBits:
  1633  		atomic.Xaddint64(&stats.inPtrScalarBits, -int64(nbytes))
  1634  	case spanAllocWorkBuf:
  1635  		atomic.Xaddint64(&stats.inWorkBufs, -int64(nbytes))
  1636  	}
  1637  	memstats.heapStats.release()
  1638  
  1639  	// Mark the space as free.
  1640  	h.pages.free(s.base(), s.npages)
  1641  
  1642  	// Free the span structure. We no longer have a use for it.
  1643  	s.state.set(mSpanDead)
  1644  	h.freeMSpanLocked(s)
  1645  }
  1646  
  1647  // scavengeAll acquires the heap lock (blocking any additional
  1648  // manipulation of the page allocator) and iterates over the whole
  1649  // heap, scavenging every free page available.
  1650  //
  1651  // Must run on the system stack because it acquires the heap lock.
  1652  //
  1653  //go:systemstack
  1654  func (h *mheap) scavengeAll() {
  1655  	// Disallow malloc or panic while holding the heap lock. We do
  1656  	// this here because this is a non-mallocgc entry-point to
  1657  	// the mheap API.
  1658  	gp := getg()
  1659  	gp.m.mallocing++
  1660  
  1661  	// Force scavenge everything.
  1662  	released := h.pages.scavenge(^uintptr(0), nil, true)
  1663  
  1664  	gp.m.mallocing--
  1665  
  1666  	if debug.scavtrace > 0 {
  1667  		printScavTrace(0, released, true)
  1668  	}
  1669  }
  1670  
  1671  //go:linkname runtime_debug_freeOSMemory runtime/debug.freeOSMemory
  1672  func runtime_debug_freeOSMemory() {
  1673  	GC()
  1674  	systemstack(func() { mheap_.scavengeAll() })
  1675  }
  1676  
  1677  // Initialize a new span with the given start and npages.
  1678  func (span *mspan) init(base uintptr, npages uintptr) {
  1679  	// span is *not* zeroed.
  1680  	span.next = nil
  1681  	span.prev = nil
  1682  	span.list = nil
  1683  	span.startAddr = base
  1684  	span.npages = npages
  1685  	span.allocCount = 0
  1686  	span.spanclass = 0
  1687  	span.elemsize = 0
  1688  	span.speciallock.key = 0
  1689  	span.specials = nil
  1690  	span.needzero = 0
  1691  	span.freeindex = 0
  1692  	span.freeIndexForScan = 0
  1693  	span.allocBits = nil
  1694  	span.gcmarkBits = nil
  1695  	span.pinnerBits = nil
  1696  	span.state.set(mSpanDead)
  1697  	lockInit(&span.speciallock, lockRankMspanSpecial)
  1698  }
  1699  
  1700  func (span *mspan) inList() bool {
  1701  	return span.list != nil
  1702  }
  1703  
  1704  // Initialize an empty doubly-linked list.
  1705  func (list *mSpanList) init() {
  1706  	list.first = nil
  1707  	list.last = nil
  1708  }
  1709  
  1710  func (list *mSpanList) remove(span *mspan) {
  1711  	if span.list != list {
  1712  		print("runtime: failed mSpanList.remove span.npages=", span.npages,
  1713  			" span=", span, " prev=", span.prev, " span.list=", span.list, " list=", list, "\n")
  1714  		throw("mSpanList.remove")
  1715  	}
  1716  	if list.first == span {
  1717  		list.first = span.next
  1718  	} else {
  1719  		span.prev.next = span.next
  1720  	}
  1721  	if list.last == span {
  1722  		list.last = span.prev
  1723  	} else {
  1724  		span.next.prev = span.prev
  1725  	}
  1726  	span.next = nil
  1727  	span.prev = nil
  1728  	span.list = nil
  1729  }
  1730  
  1731  func (list *mSpanList) isEmpty() bool {
  1732  	return list.first == nil
  1733  }
  1734  
  1735  func (list *mSpanList) insert(span *mspan) {
  1736  	if span.next != nil || span.prev != nil || span.list != nil {
  1737  		println("runtime: failed mSpanList.insert", span, span.next, span.prev, span.list)
  1738  		throw("mSpanList.insert")
  1739  	}
  1740  	span.next = list.first
  1741  	if list.first != nil {
  1742  		// The list contains at least one span; link it in.
  1743  		// The last span in the list doesn't change.
  1744  		list.first.prev = span
  1745  	} else {
  1746  		// The list contains no spans, so this is also the last span.
  1747  		list.last = span
  1748  	}
  1749  	list.first = span
  1750  	span.list = list
  1751  }
  1752  
  1753  func (list *mSpanList) insertBack(span *mspan) {
  1754  	if span.next != nil || span.prev != nil || span.list != nil {
  1755  		println("runtime: failed mSpanList.insertBack", span, span.next, span.prev, span.list)
  1756  		throw("mSpanList.insertBack")
  1757  	}
  1758  	span.prev = list.last
  1759  	if list.last != nil {
  1760  		// The list contains at least one span.
  1761  		list.last.next = span
  1762  	} else {
  1763  		// The list contains no spans, so this is also the first span.
  1764  		list.first = span
  1765  	}
  1766  	list.last = span
  1767  	span.list = list
  1768  }
  1769  
  1770  // takeAll removes all spans from other and inserts them at the front
  1771  // of list.
  1772  func (list *mSpanList) takeAll(other *mSpanList) {
  1773  	if other.isEmpty() {
  1774  		return
  1775  	}
  1776  
  1777  	// Reparent everything in other to list.
  1778  	for s := other.first; s != nil; s = s.next {
  1779  		s.list = list
  1780  	}
  1781  
  1782  	// Concatenate the lists.
  1783  	if list.isEmpty() {
  1784  		*list = *other
  1785  	} else {
  1786  		// Neither list is empty. Put other before list.
  1787  		other.last.next = list.first
  1788  		list.first.prev = other.last
  1789  		list.first = other.first
  1790  	}
  1791  
  1792  	other.first, other.last = nil, nil
  1793  }
  1794  
  1795  const (
  1796  	_KindSpecialFinalizer = 1
  1797  	_KindSpecialProfile   = 2
  1798  	// _KindSpecialReachable is a special used for tracking
  1799  	// reachability during testing.
  1800  	_KindSpecialReachable = 3
  1801  	// _KindSpecialPinCounter is a special used for objects that are pinned
  1802  	// multiple times
  1803  	_KindSpecialPinCounter = 4
  1804  	// Note: The finalizer special must be first because if we're freeing
  1805  	// an object, a finalizer special will cause the freeing operation
  1806  	// to abort, and we want to keep the other special records around
  1807  	// if that happens.
  1808  )
  1809  
  1810  type special struct {
  1811  	_      sys.NotInHeap
  1812  	next   *special // linked list in span
  1813  	offset uint16   // span offset of object
  1814  	kind   byte     // kind of special
  1815  }
  1816  
  1817  // spanHasSpecials marks a span as having specials in the arena bitmap.
  1818  func spanHasSpecials(s *mspan) {
  1819  	arenaPage := (s.base() / pageSize) % pagesPerArena
  1820  	ai := arenaIndex(s.base())
  1821  	ha := mheap_.arenas[ai.l1()][ai.l2()]
  1822  	atomic.Or8(&ha.pageSpecials[arenaPage/8], uint8(1)<<(arenaPage%8))
  1823  }
  1824  
  1825  // spanHasNoSpecials marks a span as having no specials in the arena bitmap.
  1826  func spanHasNoSpecials(s *mspan) {
  1827  	arenaPage := (s.base() / pageSize) % pagesPerArena
  1828  	ai := arenaIndex(s.base())
  1829  	ha := mheap_.arenas[ai.l1()][ai.l2()]
  1830  	atomic.And8(&ha.pageSpecials[arenaPage/8], ^(uint8(1) << (arenaPage % 8)))
  1831  }
  1832  
  1833  // Adds the special record s to the list of special records for
  1834  // the object p. All fields of s should be filled in except for
  1835  // offset & next, which this routine will fill in.
  1836  // Returns true if the special was successfully added, false otherwise.
  1837  // (The add will fail only if a record with the same p and s->kind
  1838  // already exists.)
  1839  func addspecial(p unsafe.Pointer, s *special) bool {
  1840  	span := spanOfHeap(uintptr(p))
  1841  	if span == nil {
  1842  		throw("addspecial on invalid pointer")
  1843  	}
  1844  
  1845  	// Ensure that the span is swept.
  1846  	// Sweeping accesses the specials list w/o locks, so we have
  1847  	// to synchronize with it. And it's just much safer.
  1848  	mp := acquirem()
  1849  	span.ensureSwept()
  1850  
  1851  	offset := uintptr(p) - span.base()
  1852  	kind := s.kind
  1853  
  1854  	lock(&span.speciallock)
  1855  
  1856  	// Find splice point, check for existing record.
  1857  	iter, exists := span.specialFindSplicePoint(offset, kind)
  1858  	if !exists {
  1859  		// Splice in record, fill in offset.
  1860  		s.offset = uint16(offset)
  1861  		s.next = *iter
  1862  		*iter = s
  1863  		spanHasSpecials(span)
  1864  	}
  1865  
  1866  	unlock(&span.speciallock)
  1867  	releasem(mp)
  1868  	return !exists // already exists
  1869  }
  1870  
  1871  // Removes the Special record of the given kind for the object p.
  1872  // Returns the record if the record existed, nil otherwise.
  1873  // The caller must FixAlloc_Free the result.
  1874  func removespecial(p unsafe.Pointer, kind uint8) *special {
  1875  	span := spanOfHeap(uintptr(p))
  1876  	if span == nil {
  1877  		throw("removespecial on invalid pointer")
  1878  	}
  1879  
  1880  	// Ensure that the span is swept.
  1881  	// Sweeping accesses the specials list w/o locks, so we have
  1882  	// to synchronize with it. And it's just much safer.
  1883  	mp := acquirem()
  1884  	span.ensureSwept()
  1885  
  1886  	offset := uintptr(p) - span.base()
  1887  
  1888  	var result *special
  1889  	lock(&span.speciallock)
  1890  
  1891  	iter, exists := span.specialFindSplicePoint(offset, kind)
  1892  	if exists {
  1893  		s := *iter
  1894  		*iter = s.next
  1895  		result = s
  1896  	}
  1897  	if span.specials == nil {
  1898  		spanHasNoSpecials(span)
  1899  	}
  1900  	unlock(&span.speciallock)
  1901  	releasem(mp)
  1902  	return result
  1903  }
  1904  
  1905  // Find a splice point in the sorted list and check for an already existing
  1906  // record. Returns a pointer to the next-reference in the list predecessor.
  1907  // Returns true, if the referenced item is an exact match.
  1908  func (span *mspan) specialFindSplicePoint(offset uintptr, kind byte) (**special, bool) {
  1909  	// Find splice point, check for existing record.
  1910  	iter := &span.specials
  1911  	found := false
  1912  	for {
  1913  		s := *iter
  1914  		if s == nil {
  1915  			break
  1916  		}
  1917  		if offset == uintptr(s.offset) && kind == s.kind {
  1918  			found = true
  1919  			break
  1920  		}
  1921  		if offset < uintptr(s.offset) || (offset == uintptr(s.offset) && kind < s.kind) {
  1922  			break
  1923  		}
  1924  		iter = &s.next
  1925  	}
  1926  	return iter, found
  1927  }
  1928  
  1929  // The described object has a finalizer set for it.
  1930  //
  1931  // specialfinalizer is allocated from non-GC'd memory, so any heap
  1932  // pointers must be specially handled.
  1933  type specialfinalizer struct {
  1934  	_       sys.NotInHeap
  1935  	special special
  1936  	fn      *funcval // May be a heap pointer.
  1937  	nret    uintptr
  1938  	fint    *_type   // May be a heap pointer, but always live.
  1939  	ot      *ptrtype // May be a heap pointer, but always live.
  1940  }
  1941  
  1942  // Adds a finalizer to the object p. Returns true if it succeeded.
  1943  func addfinalizer(p unsafe.Pointer, f *funcval, nret uintptr, fint *_type, ot *ptrtype) bool {
  1944  	lock(&mheap_.speciallock)
  1945  	s := (*specialfinalizer)(mheap_.specialfinalizeralloc.alloc())
  1946  	unlock(&mheap_.speciallock)
  1947  	s.special.kind = _KindSpecialFinalizer
  1948  	s.fn = f
  1949  	s.nret = nret
  1950  	s.fint = fint
  1951  	s.ot = ot
  1952  	if addspecial(p, &s.special) {
  1953  		// This is responsible for maintaining the same
  1954  		// GC-related invariants as markrootSpans in any
  1955  		// situation where it's possible that markrootSpans
  1956  		// has already run but mark termination hasn't yet.
  1957  		if gcphase != _GCoff {
  1958  			base, span, _ := findObject(uintptr(p), 0, 0)
  1959  			mp := acquirem()
  1960  			gcw := &mp.p.ptr().gcw
  1961  			// Mark everything reachable from the object
  1962  			// so it's retained for the finalizer.
  1963  			if !span.spanclass.noscan() {
  1964  				scanobject(base, gcw)
  1965  			}
  1966  			// Mark the finalizer itself, since the
  1967  			// special isn't part of the GC'd heap.
  1968  			scanblock(uintptr(unsafe.Pointer(&s.fn)), goarch.PtrSize, &oneptrmask[0], gcw, nil)
  1969  			releasem(mp)
  1970  		}
  1971  		return true
  1972  	}
  1973  
  1974  	// There was an old finalizer
  1975  	lock(&mheap_.speciallock)
  1976  	mheap_.specialfinalizeralloc.free(unsafe.Pointer(s))
  1977  	unlock(&mheap_.speciallock)
  1978  	return false
  1979  }
  1980  
  1981  // Removes the finalizer (if any) from the object p.
  1982  func removefinalizer(p unsafe.Pointer) {
  1983  	s := (*specialfinalizer)(unsafe.Pointer(removespecial(p, _KindSpecialFinalizer)))
  1984  	if s == nil {
  1985  		return // there wasn't a finalizer to remove
  1986  	}
  1987  	lock(&mheap_.speciallock)
  1988  	mheap_.specialfinalizeralloc.free(unsafe.Pointer(s))
  1989  	unlock(&mheap_.speciallock)
  1990  }
  1991  
  1992  // The described object is being heap profiled.
  1993  type specialprofile struct {
  1994  	_       sys.NotInHeap
  1995  	special special
  1996  	b       *bucket
  1997  }
  1998  
  1999  // Set the heap profile bucket associated with addr to b.
  2000  func setprofilebucket(p unsafe.Pointer, b *bucket) {
  2001  	lock(&mheap_.speciallock)
  2002  	s := (*specialprofile)(mheap_.specialprofilealloc.alloc())
  2003  	unlock(&mheap_.speciallock)
  2004  	s.special.kind = _KindSpecialProfile
  2005  	s.b = b
  2006  	if !addspecial(p, &s.special) {
  2007  		throw("setprofilebucket: profile already set")
  2008  	}
  2009  }
  2010  
  2011  // specialReachable tracks whether an object is reachable on the next
  2012  // GC cycle. This is used by testing.
  2013  type specialReachable struct {
  2014  	special   special
  2015  	done      bool
  2016  	reachable bool
  2017  }
  2018  
  2019  // specialPinCounter tracks whether an object is pinned multiple times.
  2020  type specialPinCounter struct {
  2021  	special special
  2022  	counter uintptr
  2023  }
  2024  
  2025  // specialsIter helps iterate over specials lists.
  2026  type specialsIter struct {
  2027  	pprev **special
  2028  	s     *special
  2029  }
  2030  
  2031  func newSpecialsIter(span *mspan) specialsIter {
  2032  	return specialsIter{&span.specials, span.specials}
  2033  }
  2034  
  2035  func (i *specialsIter) valid() bool {
  2036  	return i.s != nil
  2037  }
  2038  
  2039  func (i *specialsIter) next() {
  2040  	i.pprev = &i.s.next
  2041  	i.s = *i.pprev
  2042  }
  2043  
  2044  // unlinkAndNext removes the current special from the list and moves
  2045  // the iterator to the next special. It returns the unlinked special.
  2046  func (i *specialsIter) unlinkAndNext() *special {
  2047  	cur := i.s
  2048  	i.s = cur.next
  2049  	*i.pprev = i.s
  2050  	return cur
  2051  }
  2052  
  2053  // freeSpecial performs any cleanup on special s and deallocates it.
  2054  // s must already be unlinked from the specials list.
  2055  func freeSpecial(s *special, p unsafe.Pointer, size uintptr) {
  2056  	switch s.kind {
  2057  	case _KindSpecialFinalizer:
  2058  		sf := (*specialfinalizer)(unsafe.Pointer(s))
  2059  		queuefinalizer(p, sf.fn, sf.nret, sf.fint, sf.ot)
  2060  		lock(&mheap_.speciallock)
  2061  		mheap_.specialfinalizeralloc.free(unsafe.Pointer(sf))
  2062  		unlock(&mheap_.speciallock)
  2063  	case _KindSpecialProfile:
  2064  		sp := (*specialprofile)(unsafe.Pointer(s))
  2065  		mProf_Free(sp.b, size)
  2066  		lock(&mheap_.speciallock)
  2067  		mheap_.specialprofilealloc.free(unsafe.Pointer(sp))
  2068  		unlock(&mheap_.speciallock)
  2069  	case _KindSpecialReachable:
  2070  		sp := (*specialReachable)(unsafe.Pointer(s))
  2071  		sp.done = true
  2072  		// The creator frees these.
  2073  	case _KindSpecialPinCounter:
  2074  		lock(&mheap_.speciallock)
  2075  		mheap_.specialPinCounterAlloc.free(unsafe.Pointer(s))
  2076  		unlock(&mheap_.speciallock)
  2077  	default:
  2078  		throw("bad special kind")
  2079  		panic("not reached")
  2080  	}
  2081  }
  2082  
  2083  // gcBits is an alloc/mark bitmap. This is always used as gcBits.x.
  2084  type gcBits struct {
  2085  	_ sys.NotInHeap
  2086  	x uint8
  2087  }
  2088  
  2089  // bytep returns a pointer to the n'th byte of b.
  2090  func (b *gcBits) bytep(n uintptr) *uint8 {
  2091  	return addb(&b.x, n)
  2092  }
  2093  
  2094  // bitp returns a pointer to the byte containing bit n and a mask for
  2095  // selecting that bit from *bytep.
  2096  func (b *gcBits) bitp(n uintptr) (bytep *uint8, mask uint8) {
  2097  	return b.bytep(n / 8), 1 << (n % 8)
  2098  }
  2099  
  2100  const gcBitsChunkBytes = uintptr(64 << 10)
  2101  const gcBitsHeaderBytes = unsafe.Sizeof(gcBitsHeader{})
  2102  
  2103  type gcBitsHeader struct {
  2104  	free uintptr // free is the index into bits of the next free byte.
  2105  	next uintptr // *gcBits triggers recursive type bug. (issue 14620)
  2106  }
  2107  
  2108  type gcBitsArena struct {
  2109  	_ sys.NotInHeap
  2110  	// gcBitsHeader // side step recursive type bug (issue 14620) by including fields by hand.
  2111  	free uintptr // free is the index into bits of the next free byte; read/write atomically
  2112  	next *gcBitsArena
  2113  	bits [gcBitsChunkBytes - gcBitsHeaderBytes]gcBits
  2114  }
  2115  
  2116  var gcBitsArenas struct {
  2117  	lock     mutex
  2118  	free     *gcBitsArena
  2119  	next     *gcBitsArena // Read atomically. Write atomically under lock.
  2120  	current  *gcBitsArena
  2121  	previous *gcBitsArena
  2122  }
  2123  
  2124  // tryAlloc allocates from b or returns nil if b does not have enough room.
  2125  // This is safe to call concurrently.
  2126  func (b *gcBitsArena) tryAlloc(bytes uintptr) *gcBits {
  2127  	if b == nil || atomic.Loaduintptr(&b.free)+bytes > uintptr(len(b.bits)) {
  2128  		return nil
  2129  	}
  2130  	// Try to allocate from this block.
  2131  	end := atomic.Xadduintptr(&b.free, bytes)
  2132  	if end > uintptr(len(b.bits)) {
  2133  		return nil
  2134  	}
  2135  	// There was enough room.
  2136  	start := end - bytes
  2137  	return &b.bits[start]
  2138  }
  2139  
  2140  // newMarkBits returns a pointer to 8 byte aligned bytes
  2141  // to be used for a span's mark bits.
  2142  func newMarkBits(nelems uintptr) *gcBits {
  2143  	blocksNeeded := (nelems + 63) / 64
  2144  	bytesNeeded := blocksNeeded * 8
  2145  
  2146  	// Try directly allocating from the current head arena.
  2147  	head := (*gcBitsArena)(atomic.Loadp(unsafe.Pointer(&gcBitsArenas.next)))
  2148  	if p := head.tryAlloc(bytesNeeded); p != nil {
  2149  		return p
  2150  	}
  2151  
  2152  	// There's not enough room in the head arena. We may need to
  2153  	// allocate a new arena.
  2154  	lock(&gcBitsArenas.lock)
  2155  	// Try the head arena again, since it may have changed. Now
  2156  	// that we hold the lock, the list head can't change, but its
  2157  	// free position still can.
  2158  	if p := gcBitsArenas.next.tryAlloc(bytesNeeded); p != nil {
  2159  		unlock(&gcBitsArenas.lock)
  2160  		return p
  2161  	}
  2162  
  2163  	// Allocate a new arena. This may temporarily drop the lock.
  2164  	fresh := newArenaMayUnlock()
  2165  	// If newArenaMayUnlock dropped the lock, another thread may
  2166  	// have put a fresh arena on the "next" list. Try allocating
  2167  	// from next again.
  2168  	if p := gcBitsArenas.next.tryAlloc(bytesNeeded); p != nil {
  2169  		// Put fresh back on the free list.
  2170  		// TODO: Mark it "already zeroed"
  2171  		fresh.next = gcBitsArenas.free
  2172  		gcBitsArenas.free = fresh
  2173  		unlock(&gcBitsArenas.lock)
  2174  		return p
  2175  	}
  2176  
  2177  	// Allocate from the fresh arena. We haven't linked it in yet, so
  2178  	// this cannot race and is guaranteed to succeed.
  2179  	p := fresh.tryAlloc(bytesNeeded)
  2180  	if p == nil {
  2181  		throw("markBits overflow")
  2182  	}
  2183  
  2184  	// Add the fresh arena to the "next" list.
  2185  	fresh.next = gcBitsArenas.next
  2186  	atomic.StorepNoWB(unsafe.Pointer(&gcBitsArenas.next), unsafe.Pointer(fresh))
  2187  
  2188  	unlock(&gcBitsArenas.lock)
  2189  	return p
  2190  }
  2191  
  2192  // newAllocBits returns a pointer to 8 byte aligned bytes
  2193  // to be used for this span's alloc bits.
  2194  // newAllocBits is used to provide newly initialized spans
  2195  // allocation bits. For spans not being initialized the
  2196  // mark bits are repurposed as allocation bits when
  2197  // the span is swept.
  2198  func newAllocBits(nelems uintptr) *gcBits {
  2199  	return newMarkBits(nelems)
  2200  }
  2201  
  2202  // nextMarkBitArenaEpoch establishes a new epoch for the arenas
  2203  // holding the mark bits. The arenas are named relative to the
  2204  // current GC cycle which is demarcated by the call to finishweep_m.
  2205  //
  2206  // All current spans have been swept.
  2207  // During that sweep each span allocated room for its gcmarkBits in
  2208  // gcBitsArenas.next block. gcBitsArenas.next becomes the gcBitsArenas.current
  2209  // where the GC will mark objects and after each span is swept these bits
  2210  // will be used to allocate objects.
  2211  // gcBitsArenas.current becomes gcBitsArenas.previous where the span's
  2212  // gcAllocBits live until all the spans have been swept during this GC cycle.
  2213  // The span's sweep extinguishes all the references to gcBitsArenas.previous
  2214  // by pointing gcAllocBits into the gcBitsArenas.current.
  2215  // The gcBitsArenas.previous is released to the gcBitsArenas.free list.
  2216  func nextMarkBitArenaEpoch() {
  2217  	lock(&gcBitsArenas.lock)
  2218  	if gcBitsArenas.previous != nil {
  2219  		if gcBitsArenas.free == nil {
  2220  			gcBitsArenas.free = gcBitsArenas.previous
  2221  		} else {
  2222  			// Find end of previous arenas.
  2223  			last := gcBitsArenas.previous
  2224  			for last = gcBitsArenas.previous; last.next != nil; last = last.next {
  2225  			}
  2226  			last.next = gcBitsArenas.free
  2227  			gcBitsArenas.free = gcBitsArenas.previous
  2228  		}
  2229  	}
  2230  	gcBitsArenas.previous = gcBitsArenas.current
  2231  	gcBitsArenas.current = gcBitsArenas.next
  2232  	atomic.StorepNoWB(unsafe.Pointer(&gcBitsArenas.next), nil) // newMarkBits calls newArena when needed
  2233  	unlock(&gcBitsArenas.lock)
  2234  }
  2235  
  2236  // newArenaMayUnlock allocates and zeroes a gcBits arena.
  2237  // The caller must hold gcBitsArena.lock. This may temporarily release it.
  2238  func newArenaMayUnlock() *gcBitsArena {
  2239  	var result *gcBitsArena
  2240  	if gcBitsArenas.free == nil {
  2241  		unlock(&gcBitsArenas.lock)
  2242  		result = (*gcBitsArena)(sysAlloc(gcBitsChunkBytes, &memstats.gcMiscSys))
  2243  		if result == nil {
  2244  			throw("runtime: cannot allocate memory")
  2245  		}
  2246  		lock(&gcBitsArenas.lock)
  2247  	} else {
  2248  		result = gcBitsArenas.free
  2249  		gcBitsArenas.free = gcBitsArenas.free.next
  2250  		memclrNoHeapPointers(unsafe.Pointer(result), gcBitsChunkBytes)
  2251  	}
  2252  	result.next = nil
  2253  	// If result.bits is not 8 byte aligned adjust index so
  2254  	// that &result.bits[result.free] is 8 byte aligned.
  2255  	if unsafe.Offsetof(gcBitsArena{}.bits)&7 == 0 {
  2256  		result.free = 0
  2257  	} else {
  2258  		result.free = 8 - (uintptr(unsafe.Pointer(&result.bits[0])) & 7)
  2259  	}
  2260  	return result
  2261  }
  2262  

View as plain text