// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Page heap.
//
// See malloc.go for overview.

package runtime

import (
	
	
	
	
	
)

const (
	// minPhysPageSize is a lower-bound on the physical page size. The
	// true physical page size may be larger than this. In contrast,
	// sys.PhysPageSize is an upper-bound on the physical page size.
	minPhysPageSize = 4096

	// maxPhysPageSize is the maximum page size the runtime supports.
	maxPhysPageSize = 512 << 10

	// maxPhysHugePageSize sets an upper-bound on the maximum huge page size
	// that the runtime supports.
	maxPhysHugePageSize = pallocChunkBytes

	// pagesPerReclaimerChunk indicates how many pages to scan from the
	// pageInUse bitmap at a time. Used by the page reclaimer.
	//
	// Higher values reduce contention on scanning indexes (such as
	// h.reclaimIndex), but increase the minimum latency of the
	// operation.
	//
	// The time required to scan this many pages can vary a lot depending
	// on how many spans are actually freed. Experimentally, it can
	// scan for pages at ~300 GB/ms on a 2.6GHz Core i7, but can only
	// free spans at ~32 MB/ms. Using 512 pages bounds this at
	// roughly 100µs.
	//
	// Must be a multiple of the pageInUse bitmap element size and
	// must also evenly divide pagesPerArena.
	pagesPerReclaimerChunk = 512

	// physPageAlignedStacks indicates whether stack allocations must be
	// physical page aligned. This is a requirement for MAP_STACK on
	// OpenBSD.
	physPageAlignedStacks = GOOS == "openbsd"
)

// Main malloc heap.
// The heap itself is the "free" and "scav" treaps,
// but all the other global data is here too.
//
// mheap must not be heap-allocated because it contains mSpanLists,
// which must not be heap-allocated.
type mheap struct {
	_ sys.NotInHeap

	// lock must only be acquired on the system stack, otherwise a g
	// could self-deadlock if its stack grows with the lock held.
	lock mutex

	pages pageAlloc // page allocation data structure

	sweepgen uint32 // sweep generation, see comment in mspan; written during STW

	// allspans is a slice of all mspans ever created. Each mspan
	// appears exactly once.
	//
	// The memory for allspans is manually managed and can be
	// reallocated and move as the heap grows.
	//
	// In general, allspans is protected by mheap_.lock, which
	// prevents concurrent access as well as freeing the backing
	// store. Accesses during STW might not hold the lock, but
	// must ensure that allocation cannot happen around the
	// access (since that may free the backing store).
	allspans []*mspan // all spans out there

	// Proportional sweep
	//
	// These parameters represent a linear function from gcController.heapLive
	// to page sweep count. The proportional sweep system works to
	// stay in the black by keeping the current page sweep count
	// above this line at the current gcController.heapLive.
	//
	// The line has slope sweepPagesPerByte and passes through a
	// basis point at (sweepHeapLiveBasis, pagesSweptBasis). At
	// any given time, the system is at (gcController.heapLive,
	// pagesSwept) in this space.
	//
	// It is important that the line pass through a point we
	// control rather than simply starting at a 0,0 origin
	// because that lets us adjust sweep pacing at any time while
	// accounting for current progress. If we could only adjust
	// the slope, it would create a discontinuity in debt if any
	// progress has already been made.
	pagesInUse         atomic.Uintptr // pages of spans in stats mSpanInUse
	pagesSwept         atomic.Uint64  // pages swept this cycle
	pagesSweptBasis    atomic.Uint64  // pagesSwept to use as the origin of the sweep ratio
	sweepHeapLiveBasis uint64         // value of gcController.heapLive to use as the origin of sweep ratio; written with lock, read without
	sweepPagesPerByte  float64        // proportional sweep ratio; written with lock, read without

	// Page reclaimer state

	// reclaimIndex is the page index in allArenas of next page to
	// reclaim. Specifically, it refers to page (i %
	// pagesPerArena) of arena allArenas[i / pagesPerArena].
	//
	// If this is >= 1<<63, the page reclaimer is done scanning
	// the page marks.
	reclaimIndex atomic.Uint64

	// reclaimCredit is spare credit for extra pages swept. Since
	// the page reclaimer works in large chunks, it may reclaim
	// more than requested. Any spare pages released go to this
	// credit pool.
	reclaimCredit atomic.Uintptr

	// arenas is the heap arena map. It points to the metadata for
	// the heap for every arena frame of the entire usable virtual
	// address space.
	//
	// Use arenaIndex to compute indexes into this array.
	//
	// For regions of the address space that are not backed by the
	// Go heap, the arena map contains nil.
	//
	// Modifications are protected by mheap_.lock. Reads can be
	// performed without locking; however, a given entry can
	// transition from nil to non-nil at any time when the lock
	// isn't held. (Entries never transitions back to nil.)
	//
	// In general, this is a two-level mapping consisting of an L1
	// map and possibly many L2 maps. This saves space when there
	// are a huge number of arena frames. However, on many
	// platforms (even 64-bit), arenaL1Bits is 0, making this
	// effectively a single-level map. In this case, arenas[0]
	// will never be nil.
	arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena

	// arenasHugePages indicates whether arenas' L2 entries are eligible
	// to be backed by huge pages.
	arenasHugePages bool

	// heapArenaAlloc is pre-reserved space for allocating heapArena
	// objects. This is only used on 32-bit, where we pre-reserve
	// this space to avoid interleaving it with the heap itself.
	heapArenaAlloc linearAlloc

	// arenaHints is a list of addresses at which to attempt to
	// add more heap arenas. This is initially populated with a
	// set of general hint addresses, and grown with the bounds of
	// actual heap arena ranges.
	arenaHints *arenaHint

	// arena is a pre-reserved space for allocating heap arenas
	// (the actual arenas). This is only used on 32-bit.
	arena linearAlloc

	// allArenas is the arenaIndex of every mapped arena. This can
	// be used to iterate through the address space.
	//
	// Access is protected by mheap_.lock. However, since this is
	// append-only and old backing arrays are never freed, it is
	// safe to acquire mheap_.lock, copy the slice header, and
	// then release mheap_.lock.
	allArenas []arenaIdx

	// sweepArenas is a snapshot of allArenas taken at the
	// beginning of the sweep cycle. This can be read safely by
	// simply blocking GC (by disabling preemption).
	sweepArenas []arenaIdx

	// markArenas is a snapshot of allArenas taken at the beginning
	// of the mark cycle. Because allArenas is append-only, neither
	// this slice nor its contents will change during the mark, so
	// it can be read safely.
	markArenas []arenaIdx

	// curArena is the arena that the heap is currently growing
	// into. This should always be physPageSize-aligned.
	curArena struct {
		base, end uintptr
	}

	// central free lists for small size classes.
	// the padding makes sure that the mcentrals are
	// spaced CacheLinePadSize bytes apart, so that each mcentral.lock
	// gets its own cache line.
	// central is indexed by spanClass.
	central [numSpanClasses]struct {
		mcentral mcentral
		pad      [(cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize) % cpu.CacheLinePadSize]byte
	}

	spanalloc              fixalloc // allocator for span*
	cachealloc             fixalloc // allocator for mcache*
	specialfinalizeralloc  fixalloc // allocator for specialfinalizer*
	specialprofilealloc    fixalloc // allocator for specialprofile*
	specialReachableAlloc  fixalloc // allocator for specialReachable
	specialPinCounterAlloc fixalloc // allocator for specialPinCounter
	speciallock            mutex    // lock for special record allocators.
	arenaHintAlloc         fixalloc // allocator for arenaHints

	// User arena state.
	//
	// Protected by mheap_.lock.
	userArena struct {
		// arenaHints is a list of addresses at which to attempt to
		// add more heap arenas for user arena chunks. This is initially
		// populated with a set of general hint addresses, and grown with
		// the bounds of actual heap arena ranges.
		arenaHints *arenaHint

		// quarantineList is a list of user arena spans that have been set to fault, but
		// are waiting for all pointers into them to go away. Sweeping handles
		// identifying when this is true, and moves the span to the ready list.
		quarantineList mSpanList

		// readyList is a list of empty user arena spans that are ready for reuse.
		readyList mSpanList
	}

	unused *specialfinalizer // never set, just here to force the specialfinalizer type into DWARF
}

var mheap_ mheap

// A heapArena stores metadata for a heap arena. heapArenas are stored
// outside of the Go heap and accessed via the mheap_.arenas index.
type heapArena struct {
	_ sys.NotInHeap

	// bitmap stores the pointer/scalar bitmap for the words in
	// this arena. See mbitmap.go for a description.
	// This array uses 1 bit per word of heap, or 1.6% of the heap size (for 64-bit).
	bitmap [heapArenaBitmapWords]uintptr

	// If the ith bit of noMorePtrs is true, then there are no more
	// pointers for the object containing the word described by the
	// high bit of bitmap[i].
	// In that case, bitmap[i+1], ... must be zero until the start
	// of the next object.
	// We never operate on these entries using bit-parallel techniques,
	// so it is ok if they are small. Also, they can't be bigger than
	// uint16 because at that size a single noMorePtrs entry
	// represents 8K of memory, the minimum size of a span. Any larger
	// and we'd have to worry about concurrent updates.
	// This array uses 1 bit per word of bitmap, or .024% of the heap size (for 64-bit).
	noMorePtrs [heapArenaBitmapWords / 8]uint8

	// spans maps from virtual address page ID within this arena to *mspan.
	// For allocated spans, their pages map to the span itself.
	// For free spans, only the lowest and highest pages map to the span itself.
	// Internal pages map to an arbitrary span.
	// For pages that have never been allocated, spans entries are nil.
	//
	// Modifications are protected by mheap.lock. Reads can be
	// performed without locking, but ONLY from indexes that are
	// known to contain in-use or stack spans. This means there
	// must not be a safe-point between establishing that an
	// address is live and looking it up in the spans array.
	spans [pagesPerArena]*mspan

	// pageInUse is a bitmap that indicates which spans are in
	// state mSpanInUse. This bitmap is indexed by page number,
	// but only the bit corresponding to the first page in each
	// span is used.
	//
	// Reads and writes are atomic.
	pageInUse [pagesPerArena / 8]uint8

	// pageMarks is a bitmap that indicates which spans have any
	// marked objects on them. Like pageInUse, only the bit
	// corresponding to the first page in each span is used.
	//
	// Writes are done atomically during marking. Reads are
	// non-atomic and lock-free since they only occur during
	// sweeping (and hence never race with writes).
	//
	// This is used to quickly find whole spans that can be freed.
	//
	// TODO(austin): It would be nice if this was uint64 for
	// faster scanning, but we don't have 64-bit atomic bit
	// operations.
	pageMarks [pagesPerArena / 8]uint8

	// pageSpecials is a bitmap that indicates which spans have
	// specials (finalizers or other). Like pageInUse, only the bit
	// corresponding to the first page in each span is used.
	//
	// Writes are done atomically whenever a special is added to
	// a span and whenever the last special is removed from a span.
	// Reads are done atomically to find spans containing specials
	// during marking.
	pageSpecials [pagesPerArena / 8]uint8

	// checkmarks stores the debug.gccheckmark state. It is only
	// used if debug.gccheckmark > 0.
	checkmarks *checkmarksMap

	// zeroedBase marks the first byte of the first page in this
	// arena which hasn't been used yet and is therefore already
	// zero. zeroedBase is relative to the arena base.
	// Increases monotonically until it hits heapArenaBytes.
	//
	// This field is sufficient to determine if an allocation
	// needs to be zeroed because the page allocator follows an
	// address-ordered first-fit policy.
	//
	// Read atomically and written with an atomic CAS.
	zeroedBase uintptr
}

// arenaHint is a hint for where to grow the heap arenas. See
// mheap_.arenaHints.
type arenaHint struct {
	_    sys.NotInHeap
	addr uintptr
	down bool
	next *arenaHint
}

// An mspan is a run of pages.
//
// When a mspan is in the heap free treap, state == mSpanFree
// and heapmap(s->start) == span, heapmap(s->start+s->npages-1) == span.
// If the mspan is in the heap scav treap, then in addition to the
// above scavenged == true. scavenged == false in all other cases.
//
// When a mspan is allocated, state == mSpanInUse or mSpanManual
// and heapmap(i) == span for all s->start <= i < s->start+s->npages.

// Every mspan is in one doubly-linked list, either in the mheap's
// busy list or one of the mcentral's span lists.

// An mspan representing actual memory has state mSpanInUse,
// mSpanManual, or mSpanFree. Transitions between these states are
// constrained as follows:
//
//   - A span may transition from free to in-use or manual during any GC
//     phase.
//
//   - During sweeping (gcphase == _GCoff), a span may transition from
//     in-use to free (as a result of sweeping) or manual to free (as a
//     result of stacks being freed).
//
//   - During GC (gcphase != _GCoff), a span *must not* transition from
//     manual or in-use to free. Because concurrent GC may read a pointer
//     and then look up its span, the span state must be monotonic.
//
// Setting mspan.state to mSpanInUse or mSpanManual must be done
// atomically and only after all other span fields are valid.
// Likewise, if inspecting a span is contingent on it being
// mSpanInUse, the state should be loaded atomically and checked
// before depending on other fields. This allows the garbage collector
// to safely deal with potentially invalid pointers, since resolving
// such pointers may race with a span being allocated.
type mSpanState uint8

const (
	mSpanDead   mSpanState = iota
	mSpanInUse             // allocated for garbage collected heap
	mSpanManual            // allocated for manual management (e.g., stack allocator)
)

// mSpanStateNames are the names of the span states, indexed by
// mSpanState.
var mSpanStateNames = []string{
	"mSpanDead",
	"mSpanInUse",
	"mSpanManual",
}

// mSpanStateBox holds an atomic.Uint8 to provide atomic operations on
// an mSpanState. This is a separate type to disallow accidental comparison
// or assignment with mSpanState.
type mSpanStateBox struct {
	s atomic.Uint8
}

// It is nosplit to match get, below.

//go:nosplit
func ( *mSpanStateBox) ( mSpanState) {
	.s.Store(uint8())
}

// It is nosplit because it's called indirectly by typedmemclr,
// which must not be preempted.

//go:nosplit
func ( *mSpanStateBox) () mSpanState {
	return mSpanState(.s.Load())
}

// mSpanList heads a linked list of spans.
type mSpanList struct {
	_     sys.NotInHeap
	first *mspan // first span in list, or nil if none
	last  *mspan // last span in list, or nil if none
}

type mspan struct {
	_    sys.NotInHeap
	next *mspan     // next span in list, or nil if none
	prev *mspan     // previous span in list, or nil if none
	list *mSpanList // For debugging. TODO: Remove.

	startAddr uintptr // address of first byte of span aka s.base()
	npages    uintptr // number of pages in span

	manualFreeList gclinkptr // list of free objects in mSpanManual spans

	// freeindex is the slot index between 0 and nelems at which to begin scanning
	// for the next free object in this span.
	// Each allocation scans allocBits starting at freeindex until it encounters a 0
	// indicating a free object. freeindex is then adjusted so that subsequent scans begin
	// just past the newly discovered free object.
	//
	// If freeindex == nelem, this span has no free objects.
	//
	// allocBits is a bitmap of objects in this span.
	// If n >= freeindex and allocBits[n/8] & (1<<(n%8)) is 0
	// then object n is free;
	// otherwise, object n is allocated. Bits starting at nelem are
	// undefined and should never be referenced.
	//
	// Object n starts at address n*elemsize + (start << pageShift).
	freeindex uintptr
	// TODO: Look up nelems from sizeclass and remove this field if it
	// helps performance.
	nelems uintptr // number of object in the span.

	// Cache of the allocBits at freeindex. allocCache is shifted
	// such that the lowest bit corresponds to the bit freeindex.
	// allocCache holds the complement of allocBits, thus allowing
	// ctz (count trailing zero) to use it directly.
	// allocCache may contain bits beyond s.nelems; the caller must ignore
	// these.
	allocCache uint64

	// allocBits and gcmarkBits hold pointers to a span's mark and
	// allocation bits. The pointers are 8 byte aligned.
	// There are three arenas where this data is held.
	// free: Dirty arenas that are no longer accessed
	//       and can be reused.
	// next: Holds information to be used in the next GC cycle.
	// current: Information being used during this GC cycle.
	// previous: Information being used during the last GC cycle.
	// A new GC cycle starts with the call to finishsweep_m.
	// finishsweep_m moves the previous arena to the free arena,
	// the current arena to the previous arena, and
	// the next arena to the current arena.
	// The next arena is populated as the spans request
	// memory to hold gcmarkBits for the next GC cycle as well
	// as allocBits for newly allocated spans.
	//
	// The pointer arithmetic is done "by hand" instead of using
	// arrays to avoid bounds checks along critical performance
	// paths.
	// The sweep will free the old allocBits and set allocBits to the
	// gcmarkBits. The gcmarkBits are replaced with a fresh zeroed
	// out memory.
	allocBits  *gcBits
	gcmarkBits *gcBits
	pinnerBits *gcBits // bitmap for pinned objects; accessed atomically

	// sweep generation:
	// if sweepgen == h->sweepgen - 2, the span needs sweeping
	// if sweepgen == h->sweepgen - 1, the span is currently being swept
	// if sweepgen == h->sweepgen, the span is swept and ready to use
	// if sweepgen == h->sweepgen + 1, the span was cached before sweep began and is still cached, and needs sweeping
	// if sweepgen == h->sweepgen + 3, the span was swept and then cached and is still cached
	// h->sweepgen is incremented by 2 after every GC

	sweepgen              uint32
	divMul                uint32        // for divide by elemsize
	allocCount            uint16        // number of allocated objects
	spanclass             spanClass     // size class and noscan (uint8)
	state                 mSpanStateBox // mSpanInUse etc; accessed atomically (get/set methods)
	needzero              uint8         // needs to be zeroed before allocation
	isUserArenaChunk      bool          // whether or not this span represents a user arena
	allocCountBeforeCache uint16        // a copy of allocCount that is stored just before this span is cached
	elemsize              uintptr       // computed from sizeclass or from npages
	limit                 uintptr       // end of data in span
	speciallock           mutex         // guards specials list and changes to pinnerBits
	specials              *special      // linked list of special records sorted by offset.
	userArenaChunkFree    addrRange     // interval for managing chunk allocation

	// freeIndexForScan is like freeindex, except that freeindex is
	// used by the allocator whereas freeIndexForScan is used by the
	// GC scanner. They are two fields so that the GC sees the object
	// is allocated only when the object and the heap bits are
	// initialized (see also the assignment of freeIndexForScan in
	// mallocgc, and issue 54596).
	freeIndexForScan uintptr
}

func ( *mspan) () uintptr {
	return .startAddr
}

func ( *mspan) () (, ,  uintptr) {
	 = .npages << _PageShift
	 = .elemsize
	if  > 0 {
		 =  / 
	}
	return
}

// recordspan adds a newly allocated span to h.allspans.
//
// This only happens the first time a span is allocated from
// mheap.spanalloc (it is not called when a span is reused).
//
// Write barriers are disallowed here because it can be called from
// gcWork when allocating new workbufs. However, because it's an
// indirect call from the fixalloc initializer, the compiler can't see
// this.
//
// The heap lock must be held.
//
//go:nowritebarrierrec
func ( unsafe.Pointer,  unsafe.Pointer) {
	 := (*mheap)()
	 := (*mspan)()

	assertLockHeld(&.lock)

	if len(.allspans) >= cap(.allspans) {
		 := 64 * 1024 / goarch.PtrSize
		if  < cap(.allspans)*3/2 {
			 = cap(.allspans) * 3 / 2
		}
		var  []*mspan
		 := (*slice)(unsafe.Pointer(&))
		.array = sysAlloc(uintptr()*goarch.PtrSize, &memstats.other_sys)
		if .array == nil {
			throw("runtime: cannot allocate memory")
		}
		.len = len(.allspans)
		.cap = 
		if len(.allspans) > 0 {
			copy(, .allspans)
		}
		 := .allspans
		*(*notInHeapSlice)(unsafe.Pointer(&.allspans)) = *(*notInHeapSlice)(unsafe.Pointer(&))
		if len() != 0 {
			sysFree(unsafe.Pointer(&[0]), uintptr(cap())*unsafe.Sizeof([0]), &memstats.other_sys)
		}
	}
	.allspans = .allspans[:len(.allspans)+1]
	.allspans[len(.allspans)-1] = 
}

// A spanClass represents the size class and noscan-ness of a span.
//
// Each size class has a noscan spanClass and a scan spanClass. The
// noscan spanClass contains only noscan objects, which do not contain
// pointers and thus do not need to be scanned by the garbage
// collector.
type spanClass uint8

const (
	numSpanClasses = _NumSizeClasses << 1
	tinySpanClass  = spanClass(tinySizeClass<<1 | 1)
)

func ( uint8,  bool) spanClass {
	return spanClass(<<1) | spanClass(bool2int())
}

func ( spanClass) () int8 {
	return int8( >> 1)
}

func ( spanClass) () bool {
	return &1 != 0
}

// arenaIndex returns the index into mheap_.arenas of the arena
// containing metadata for p. This index combines of an index into the
// L1 map and an index into the L2 map and should be used as
// mheap_.arenas[ai.l1()][ai.l2()].
//
// If p is outside the range of valid heap addresses, either l1() or
// l2() will be out of bounds.
//
// It is nosplit because it's called by spanOf and several other
// nosplit functions.
//
//go:nosplit
func ( uintptr) arenaIdx {
	return arenaIdx(( - arenaBaseOffset) / heapArenaBytes)
}

// arenaBase returns the low address of the region covered by heap
// arena i.
func ( arenaIdx) uintptr {
	return uintptr()*heapArenaBytes + arenaBaseOffset
}

type arenaIdx uint

// l1 returns the "l1" portion of an arenaIdx.
//
// Marked nosplit because it's called by spanOf and other nosplit
// functions.
//
//go:nosplit
func ( arenaIdx) () uint {
	if arenaL1Bits == 0 {
		// Let the compiler optimize this away if there's no
		// L1 map.
		return 0
	} else {
		return uint() >> arenaL1Shift
	}
}

// l2 returns the "l2" portion of an arenaIdx.
//
// Marked nosplit because it's called by spanOf and other nosplit funcs.
// functions.
//
//go:nosplit
func ( arenaIdx) () uint {
	if arenaL1Bits == 0 {
		return uint()
	} else {
		return uint() & (1<<arenaL2Bits - 1)
	}
}

// inheap reports whether b is a pointer into a (potentially dead) heap object.
// It returns false for pointers into mSpanManual spans.
// Non-preemptible because it is used by write barriers.
//
//go:nowritebarrier
//go:nosplit
func ( uintptr) bool {
	return spanOfHeap() != nil
}

// inHeapOrStack is a variant of inheap that returns true for pointers
// into any allocated heap span.
//
//go:nowritebarrier
//go:nosplit
func ( uintptr) bool {
	 := spanOf()
	if  == nil ||  < .base() {
		return false
	}
	switch .state.get() {
	case mSpanInUse, mSpanManual:
		return  < .limit
	default:
		return false
	}
}

// spanOf returns the span of p. If p does not point into the heap
// arena or no span has ever contained p, spanOf returns nil.
//
// If p does not point to allocated memory, this may return a non-nil
// span that does *not* contain p. If this is a possibility, the
// caller should either call spanOfHeap or check the span bounds
// explicitly.
//
// Must be nosplit because it has callers that are nosplit.
//
//go:nosplit
func ( uintptr) *mspan {
	// This function looks big, but we use a lot of constant
	// folding around arenaL1Bits to get it under the inlining
	// budget. Also, many of the checks here are safety checks
	// that Go needs to do anyway, so the generated code is quite
	// short.
	 := arenaIndex()
	if arenaL1Bits == 0 {
		// If there's no L1, then ri.l1() can't be out of bounds but ri.l2() can.
		if .l2() >= uint(len(mheap_.arenas[0])) {
			return nil
		}
	} else {
		// If there's an L1, then ri.l1() can be out of bounds but ri.l2() can't.
		if .l1() >= uint(len(mheap_.arenas)) {
			return nil
		}
	}
	 := mheap_.arenas[.l1()]
	if arenaL1Bits != 0 &&  == nil { // Should never happen if there's no L1.
		return nil
	}
	 := [.l2()]
	if  == nil {
		return nil
	}
	return .spans[(/pageSize)%pagesPerArena]
}

// spanOfUnchecked is equivalent to spanOf, but the caller must ensure
// that p points into an allocated heap arena.
//
// Must be nosplit because it has callers that are nosplit.
//
//go:nosplit
func ( uintptr) *mspan {
	 := arenaIndex()
	return mheap_.arenas[.l1()][.l2()].spans[(/pageSize)%pagesPerArena]
}

// spanOfHeap is like spanOf, but returns nil if p does not point to a
// heap object.
//
// Must be nosplit because it has callers that are nosplit.
//
//go:nosplit
func ( uintptr) *mspan {
	 := spanOf()
	// s is nil if it's never been allocated. Otherwise, we check
	// its state first because we don't trust this pointer, so we
	// have to synchronize with span initialization. Then, it's
	// still possible we picked up a stale span pointer, so we
	// have to check the span's bounds.
	if  == nil || .state.get() != mSpanInUse ||  < .base() ||  >= .limit {
		return nil
	}
	return 
}

// pageIndexOf returns the arena, page index, and page mask for pointer p.
// The caller must ensure p is in the heap.
func ( uintptr) ( *heapArena,  uintptr,  uint8) {
	 := arenaIndex()
	 = mheap_.arenas[.l1()][.l2()]
	 = (( / pageSize) / 8) % uintptr(len(.pageInUse))
	 = byte(1 << (( / pageSize) % 8))
	return
}

// Initialize the heap.
func ( *mheap) () {
	lockInit(&.lock, lockRankMheap)
	lockInit(&.speciallock, lockRankMheapSpecial)

	.spanalloc.init(unsafe.Sizeof(mspan{}), recordspan, unsafe.Pointer(), &memstats.mspan_sys)
	.cachealloc.init(unsafe.Sizeof(mcache{}), nil, nil, &memstats.mcache_sys)
	.specialfinalizeralloc.init(unsafe.Sizeof(specialfinalizer{}), nil, nil, &memstats.other_sys)
	.specialprofilealloc.init(unsafe.Sizeof(specialprofile{}), nil, nil, &memstats.other_sys)
	.specialReachableAlloc.init(unsafe.Sizeof(specialReachable{}), nil, nil, &memstats.other_sys)
	.specialPinCounterAlloc.init(unsafe.Sizeof(specialPinCounter{}), nil, nil, &memstats.other_sys)
	.arenaHintAlloc.init(unsafe.Sizeof(arenaHint{}), nil, nil, &memstats.other_sys)

	// Don't zero mspan allocations. Background sweeping can
	// inspect a span concurrently with allocating it, so it's
	// important that the span's sweepgen survive across freeing
	// and re-allocating a span to prevent background sweeping
	// from improperly cas'ing it from 0.
	//
	// This is safe because mspan contains no heap pointers.
	.spanalloc.zero = false

	// h->mapcache needs no init

	for  := range .central {
		.central[].mcentral.init(spanClass())
	}

	.pages.init(&.lock, &memstats.gcMiscSys, false)
}

// reclaim sweeps and reclaims at least npage pages into the heap.
// It is called before allocating npage pages to keep growth in check.
//
// reclaim implements the page-reclaimer half of the sweeper.
//
// h.lock must NOT be held.
func ( *mheap) ( uintptr) {
	// TODO(austin): Half of the time spent freeing spans is in
	// locking/unlocking the heap (even with low contention). We
	// could make the slow path here several times faster by
	// batching heap frees.

	// Bail early if there's no more reclaim work.
	if .reclaimIndex.Load() >= 1<<63 {
		return
	}

	// Disable preemption so the GC can't start while we're
	// sweeping, so we can read h.sweepArenas, and so
	// traceGCSweepStart/Done pair on the P.
	 := acquirem()

	if traceEnabled() {
		traceGCSweepStart()
	}

	 := .sweepArenas
	 := false
	for  > 0 {
		// Pull from accumulated credit first.
		if  := .reclaimCredit.Load();  > 0 {
			 := 
			if  >  {
				// Take only what we need.
				 = 
			}
			if .reclaimCredit.CompareAndSwap(, -) {
				 -= 
			}
			continue
		}

		// Claim a chunk of work.
		 := uintptr(.reclaimIndex.Add(pagesPerReclaimerChunk) - pagesPerReclaimerChunk)
		if /pagesPerArena >= uintptr(len()) {
			// Page reclaiming is done.
			.reclaimIndex.Store(1 << 63)
			break
		}

		if ! {
			// Lock the heap for reclaimChunk.
			lock(&.lock)
			 = true
		}

		// Scan this chunk.
		 := .reclaimChunk(, , pagesPerReclaimerChunk)
		if  <=  {
			 -= 
		} else {
			// Put spare pages toward global credit.
			.reclaimCredit.Add( - )
			 = 0
		}
	}
	if  {
		unlock(&.lock)
	}

	if traceEnabled() {
		traceGCSweepDone()
	}
	releasem()
}

// reclaimChunk sweeps unmarked spans that start at page indexes [pageIdx, pageIdx+n).
// It returns the number of pages returned to the heap.
//
// h.lock must be held and the caller must be non-preemptible. Note: h.lock may be
// temporarily unlocked and re-locked in order to do sweeping or if tracing is
// enabled.
func ( *mheap) ( []arenaIdx, ,  uintptr) uintptr {
	// The heap lock must be held because this accesses the
	// heapArena.spans arrays using potentially non-live pointers.
	// In particular, if a span were freed and merged concurrently
	// with this probing heapArena.spans, it would be possible to
	// observe arbitrary, stale span pointers.
	assertLockHeld(&.lock)

	 := 
	var  uintptr
	 := sweep.active.begin()
	if !.valid {
		return 0
	}
	for  > 0 {
		 := [/pagesPerArena]
		 := .arenas[.l1()][.l2()]

		// Get a chunk of the bitmap to work on.
		 := uint( % pagesPerArena)
		 := .pageInUse[/8:]
		 := .pageMarks[/8:]
		if uintptr(len()) > /8 {
			 = [:/8]
			 = [:/8]
		}

		// Scan this bitmap chunk for spans that are in-use
		// but have no marked objects on them.
		for  := range  {
			 := atomic.Load8(&[]) &^ []
			if  == 0 {
				continue
			}

			for  := uint(0);  < 8; ++ {
				if &(1<<) != 0 {
					 := .spans[+uint()*8+]
					if ,  := .tryAcquire();  {
						 := .npages
						unlock(&.lock)
						if .sweep(false) {
							 += 
						}
						lock(&.lock)
						// Reload inUse. It's possible nearby
						// spans were freed when we dropped the
						// lock and we don't want to get stale
						// pointers from the spans array.
						 = atomic.Load8(&[]) &^ []
					}
				}
			}
		}

		// Advance.
		 += uintptr(len() * 8)
		 -= uintptr(len() * 8)
	}
	sweep.active.end()
	if traceEnabled() {
		unlock(&.lock)
		// Account for pages scanned but not reclaimed.
		traceGCSweepSpan(( - ) * pageSize)
		lock(&.lock)
	}

	assertLockHeld(&.lock) // Must be locked on return.
	return 
}

// spanAllocType represents the type of allocation to make, or
// the type of allocation to be freed.
type spanAllocType uint8

const (
	spanAllocHeap          spanAllocType = iota // heap span
	spanAllocStack                              // stack span
	spanAllocPtrScalarBits                      // unrolled GC prog bitmap span
	spanAllocWorkBuf                            // work buf span
)

// manual returns true if the span allocation is manually managed.
func ( spanAllocType) () bool {
	return  != spanAllocHeap
}

// alloc allocates a new span of npage pages from the GC'd heap.
//
// spanclass indicates the span's size class and scannability.
//
// Returns a span that has been fully initialized. span.needzero indicates
// whether the span has been zeroed. Note that it may not be.
func ( *mheap) ( uintptr,  spanClass) *mspan {
	// Don't do any operations that lock the heap on the G stack.
	// It might trigger stack growth, and the stack growth code needs
	// to be able to allocate heap.
	var  *mspan
	systemstack(func() {
		// To prevent excessive heap growth, before allocating n pages
		// we need to sweep and reclaim at least n pages.
		if !isSweepDone() {
			.reclaim()
		}
		 = .allocSpan(, spanAllocHeap, )
	})
	return 
}

// allocManual allocates a manually-managed span of npage pages.
// allocManual returns nil if allocation fails.
//
// allocManual adds the bytes used to *stat, which should be a
// memstats in-use field. Unlike allocations in the GC'd heap, the
// allocation does *not* count toward heapInUse.
//
// The memory backing the returned span may not be zeroed if
// span.needzero is set.
//
// allocManual must be called on the system stack because it may
// acquire the heap lock via allocSpan. See mheap for details.
//
// If new code is written to call allocManual, do NOT use an
// existing spanAllocType value and instead declare a new one.
//
//go:systemstack
func ( *mheap) ( uintptr,  spanAllocType) *mspan {
	if !.manual() {
		throw("manual span allocation called with non-manually-managed type")
	}
	return .allocSpan(, , 0)
}

// setSpans modifies the span map so [spanOf(base), spanOf(base+npage*pageSize))
// is s.
func ( *mheap) (,  uintptr,  *mspan) {
	 :=  / pageSize
	 := arenaIndex()
	 := .arenas[.l1()][.l2()]
	for  := uintptr(0);  < ; ++ {
		 := ( + ) % pagesPerArena
		if  == 0 {
			 = arenaIndex( + *pageSize)
			 = .arenas[.l1()][.l2()]
		}
		.spans[] = 
	}
}

// allocNeedsZero checks if the region of address space [base, base+npage*pageSize),
// assumed to be allocated, needs to be zeroed, updating heap arena metadata for
// future allocations.
//
// This must be called each time pages are allocated from the heap, even if the page
// allocator can otherwise prove the memory it's allocating is already zero because
// they're fresh from the operating system. It updates heapArena metadata that is
// critical for future page allocations.
//
// There are no locking constraints on this method.
func ( *mheap) (,  uintptr) ( bool) {
	for  > 0 {
		 := arenaIndex()
		 := .arenas[.l1()][.l2()]

		 := atomic.Loaduintptr(&.zeroedBase)
		 :=  % heapArenaBytes
		if  <  {
			// We extended into the non-zeroed part of the
			// arena, so this region needs to be zeroed before use.
			//
			// zeroedBase is monotonically increasing, so if we see this now then
			// we can be sure we need to zero this memory region.
			//
			// We still need to update zeroedBase for this arena, and
			// potentially more arenas.
			 = true
		}
		// We may observe arenaBase > zeroedBase if we're racing with one or more
		// allocations which are acquiring memory directly before us in the address
		// space. But, because we know no one else is acquiring *this* memory, it's
		// still safe to not zero.

		// Compute how far into the arena we extend into, capped
		// at heapArenaBytes.
		 :=  + *pageSize
		if  > heapArenaBytes {
			 = heapArenaBytes
		}
		// Increase ha.zeroedBase so it's >= arenaLimit.
		// We may be racing with other updates.
		for  >  {
			if atomic.Casuintptr(&.zeroedBase, , ) {
				break
			}
			 = atomic.Loaduintptr(&.zeroedBase)
			// Double check basic conditions of zeroedBase.
			if  <=  &&  >  {
				// The zeroedBase moved into the space we were trying to
				// claim. That's very bad, and indicates someone allocated
				// the same region we did.
				throw("potentially overlapping in-use allocations detected")
			}
		}

		// Move base forward and subtract from npage to move into
		// the next arena, or finish.
		 +=  - 
		 -= ( - ) / pageSize
	}
	return
}

// tryAllocMSpan attempts to allocate an mspan object from
// the P-local cache, but may fail.
//
// h.lock need not be held.
//
// This caller must ensure that its P won't change underneath
// it during this function. Currently to ensure that we enforce
// that the function is run on the system stack, because that's
// the only place it is used now. In the future, this requirement
// may be relaxed if its use is necessary elsewhere.
//
//go:systemstack
func ( *mheap) () *mspan {
	 := getg().m.p.ptr()
	// If we don't have a p or the cache is empty, we can't do
	// anything here.
	if  == nil || .mspancache.len == 0 {
		return nil
	}
	// Pull off the last entry in the cache.
	 := .mspancache.buf[.mspancache.len-1]
	.mspancache.len--
	return 
}

// allocMSpanLocked allocates an mspan object.
//
// h.lock must be held.
//
// allocMSpanLocked must be called on the system stack because
// its caller holds the heap lock. See mheap for details.
// Running on the system stack also ensures that we won't
// switch Ps during this function. See tryAllocMSpan for details.
//
//go:systemstack
func ( *mheap) () *mspan {
	assertLockHeld(&.lock)

	 := getg().m.p.ptr()
	if  == nil {
		// We don't have a p so just do the normal thing.
		return (*mspan)(.spanalloc.alloc())
	}
	// Refill the cache if necessary.
	if .mspancache.len == 0 {
		const  = len(.mspancache.buf) / 2
		for  := 0;  < ; ++ {
			.mspancache.buf[] = (*mspan)(.spanalloc.alloc())
		}
		.mspancache.len = 
	}
	// Pull off the last entry in the cache.
	 := .mspancache.buf[.mspancache.len-1]
	.mspancache.len--
	return 
}

// freeMSpanLocked free an mspan object.
//
// h.lock must be held.
//
// freeMSpanLocked must be called on the system stack because
// its caller holds the heap lock. See mheap for details.
// Running on the system stack also ensures that we won't
// switch Ps during this function. See tryAllocMSpan for details.
//
//go:systemstack
func ( *mheap) ( *mspan) {
	assertLockHeld(&.lock)

	 := getg().m.p.ptr()
	// First try to free the mspan directly to the cache.
	if  != nil && .mspancache.len < len(.mspancache.buf) {
		.mspancache.buf[.mspancache.len] = 
		.mspancache.len++
		return
	}
	// Failing that (or if we don't have a p), just free it to
	// the heap.
	.spanalloc.free(unsafe.Pointer())
}

// allocSpan allocates an mspan which owns npages worth of memory.
//
// If typ.manual() == false, allocSpan allocates a heap span of class spanclass
// and updates heap accounting. If manual == true, allocSpan allocates a
// manually-managed span (spanclass is ignored), and the caller is
// responsible for any accounting related to its use of the span. Either
// way, allocSpan will atomically add the bytes in the newly allocated
// span to *sysStat.
//
// The returned span is fully initialized.
//
// h.lock must not be held.
//
// allocSpan must be called on the system stack both because it acquires
// the heap lock and because it must block GC transitions.
//
//go:systemstack
func ( *mheap) ( uintptr,  spanAllocType,  spanClass) ( *mspan) {
	// Function-global state.
	 := getg()
	,  := uintptr(0), uintptr(0)
	 := uintptr(0)

	// On some platforms we need to provide physical page aligned stack
	// allocations. Where the page size is less than the physical page
	// size, we already manage to do this by default.
	 := physPageAlignedStacks &&  == spanAllocStack && pageSize < physPageSize

	// If the allocation is small enough, try the page cache!
	// The page cache does not support aligned allocations, so we cannot use
	// it if we need to provide a physical page aligned stack allocation.
	 := .m.p.ptr()
	if ! &&  != nil &&  < pageCachePages/4 {
		 := &.pcache

		// If the cache is empty, refill it.
		if .empty() {
			lock(&.lock)
			* = .pages.allocToCache()
			unlock(&.lock)
		}

		// Try to allocate from the cache.
		,  = .alloc()
		if  != 0 {
			 = .tryAllocMSpan()
			if  != nil {
				goto 
			}
			// We have a base but no mspan, so we need
			// to lock the heap.
		}
	}

	// For one reason or another, we couldn't get the
	// whole job done without the heap lock.
	lock(&.lock)

	if  {
		// Overallocate by a physical page to allow for later alignment.
		 := physPageSize / pageSize

		// Find a big enough region first, but then only allocate the
		// aligned portion. We can't just allocate and then free the
		// edges because we need to account for scavenged memory, and
		// that's difficult with alloc.
		//
		// Note that we skip updates to searchAddr here. It's OK if
		// it's stale and higher than normal; it'll operate correctly,
		// just come with a performance cost.
		, _ = .pages.find( + )
		if  == 0 {
			var  bool
			,  = .grow( + )
			if ! {
				unlock(&.lock)
				return nil
			}
			, _ = .pages.find( + )
			if  == 0 {
				throw("grew heap, but no adequate free space found")
			}
		}
		 = alignUp(, physPageSize)
		 = .pages.allocRange(, )
	}

	if  == 0 {
		// Try to acquire a base address.
		,  = .pages.alloc()
		if  == 0 {
			var  bool
			,  = .grow()
			if ! {
				unlock(&.lock)
				return nil
			}
			,  = .pages.alloc()
			if  == 0 {
				throw("grew heap, but no adequate free space found")
			}
		}
	}
	if  == nil {
		// We failed to get an mspan earlier, so grab
		// one now that we have the heap lock.
		 = .allocMSpanLocked()
	}
	unlock(&.lock)

:
	// Decide if we need to scavenge in response to what we just allocated.
	// Specifically, we track the maximum amount of memory to scavenge of all
	// the alternatives below, assuming that the maximum satisfies *all*
	// conditions we check (e.g. if we need to scavenge X to satisfy the
	// memory limit and Y to satisfy heap-growth scavenging, and Y > X, then
	// it's fine to pick Y, because the memory limit is still satisfied).
	//
	// It's fine to do this after allocating because we expect any scavenged
	// pages not to get touched until we return. Simultaneously, it's important
	// to do this before calling sysUsed because that may commit address space.
	 := uintptr(0)
	 := false
	if  := gcController.memoryLimit.Load(); !gcCPULimiter.limiting() {
		// Assist with scavenging to maintain the memory limit by the amount
		// that we expect to page in.
		 := gcController.mappedReady.Load()
		// Be careful about overflow, especially with uintptrs. Even on 32-bit platforms
		// someone can set a really big memory limit that isn't maxInt64.
		if uint64()+ > uint64() {
			 = uintptr(uint64() +  - uint64())
			 = true
		}
	}
	if  := scavenge.gcPercentGoal.Load();  != ^uint64(0) &&  > 0 {
		// We just caused a heap growth, so scavenge down what will soon be used.
		// By scavenging inline we deal with the failure to allocate out of
		// memory fragments by scavenging the memory fragments that are least
		// likely to be re-used.
		//
		// Only bother with this because we're not using a memory limit. We don't
		// care about heap growths as long as we're under the memory limit, and the
		// previous check for scaving already handles that.
		if  := heapRetained(); +uint64() >  {
			// The scavenging algorithm requires the heap lock to be dropped so it
			// can acquire it only sparingly. This is a potentially expensive operation
			// so it frees up other goroutines to allocate in the meanwhile. In fact,
			// they can make use of the growth we just created.
			 := 
			if  := uintptr( + uint64() - );  >  {
				 = 
			}
			if  >  {
				 = 
			}
		}
	}
	// There are a few very limited circumstances where we won't have a P here.
	// It's OK to simply skip scavenging in these cases. Something else will notice
	// and pick up the tab.
	var  int64
	if  != nil &&  > 0 {
		// Measure how long we spent scavenging and add that measurement to the assist
		// time so we can track it for the GC CPU limiter.
		//
		// Limiter event tracking might be disabled if we end up here
		// while on a mark worker.
		 := nanotime()
		 := .limiterEvent.start(limiterEventScavengeAssist, )

		// Scavenge, but back out if the limiter turns on.
		 := .pages.scavenge(, func() bool {
			return gcCPULimiter.limiting()
		}, )

		mheap_.pages.scav.releasedEager.Add()

		// Finish up accounting.
		 = nanotime()
		if  {
			.limiterEvent.stop(limiterEventScavengeAssist, )
		}
		scavenge.assistTime.Add( - )
	}

	// Initialize the span.
	.initSpan(, , , , )

	// Commit and account for any scavenged memory that the span now owns.
	 :=  * pageSize
	if  != 0 {
		// sysUsed all the pages that are actually available
		// in the span since some of them might be scavenged.
		sysUsed(unsafe.Pointer(), , )
		gcController.heapReleased.add(-int64())
	}
	// Update stats.
	gcController.heapFree.add(-int64( - ))
	if  == spanAllocHeap {
		gcController.heapInUse.add(int64())
	}
	// Update consistent stats.
	 := memstats.heapStats.acquire()
	atomic.Xaddint64(&.committed, int64())
	atomic.Xaddint64(&.released, -int64())
	switch  {
	case spanAllocHeap:
		atomic.Xaddint64(&.inHeap, int64())
	case spanAllocStack:
		atomic.Xaddint64(&.inStacks, int64())
	case spanAllocPtrScalarBits:
		atomic.Xaddint64(&.inPtrScalarBits, int64())
	case spanAllocWorkBuf:
		atomic.Xaddint64(&.inWorkBufs, int64())
	}
	memstats.heapStats.release()

	pageTraceAlloc(, , , )
	return 
}

// initSpan initializes a blank span s which will represent the range
// [base, base+npages*pageSize). typ is the type of span being allocated.
func ( *mheap) ( *mspan,  spanAllocType,  spanClass, ,  uintptr) {
	// At this point, both s != nil and base != 0, and the heap
	// lock is no longer held. Initialize the span.
	.init(, )
	if .allocNeedsZero(, ) {
		.needzero = 1
	}
	 :=  * pageSize
	if .manual() {
		.manualFreeList = 0
		.nelems = 0
		.limit = .base() + .npages*pageSize
		.state.set(mSpanManual)
	} else {
		// We must set span properties before the span is published anywhere
		// since we're not holding the heap lock.
		.spanclass = 
		if  := .sizeclass();  == 0 {
			.elemsize = 
			.nelems = 1
			.divMul = 0
		} else {
			.elemsize = uintptr(class_to_size[])
			.nelems =  / .elemsize
			.divMul = class_to_divmagic[]
		}

		// Initialize mark and allocation structures.
		.freeindex = 0
		.freeIndexForScan = 0
		.allocCache = ^uint64(0) // all 1s indicating all free.
		.gcmarkBits = newMarkBits(.nelems)
		.allocBits = newAllocBits(.nelems)

		// It's safe to access h.sweepgen without the heap lock because it's
		// only ever updated with the world stopped and we run on the
		// systemstack which blocks a STW transition.
		atomic.Store(&.sweepgen, .sweepgen)

		// Now that the span is filled in, set its state. This
		// is a publication barrier for the other fields in
		// the span. While valid pointers into this span
		// should never be visible until the span is returned,
		// if the garbage collector finds an invalid pointer,
		// access to the span may race with initialization of
		// the span. We resolve this race by atomically
		// setting the state after the span is fully
		// initialized, and atomically checking the state in
		// any situation where a pointer is suspect.
		.state.set(mSpanInUse)
	}

	// Publish the span in various locations.

	// This is safe to call without the lock held because the slots
	// related to this span will only ever be read or modified by
	// this thread until pointers into the span are published (and
	// we execute a publication barrier at the end of this function
	// before that happens) or pageInUse is updated.
	.setSpans(.base(), , )

	if !.manual() {
		// Mark in-use span in arena page bitmap.
		//
		// This publishes the span to the page sweeper, so
		// it's imperative that the span be completely initialized
		// prior to this line.
		, ,  := pageIndexOf(.base())
		atomic.Or8(&.pageInUse[], )

		// Update related page sweeper stats.
		.pagesInUse.Add()
	}

	// Make sure the newly allocated span will be observed
	// by the GC before pointers into the span are published.
	publicationBarrier()
}

// Try to add at least npage pages of memory to the heap,
// returning how much the heap grew by and whether it worked.
//
// h.lock must be held.
func ( *mheap) ( uintptr) (uintptr, bool) {
	assertLockHeld(&.lock)

	// We must grow the heap in whole palloc chunks.
	// We call sysMap below but note that because we
	// round up to pallocChunkPages which is on the order
	// of MiB (generally >= to the huge page size) we
	// won't be calling it too much.
	 := alignUp(, pallocChunkPages) * pageSize

	 := uintptr(0)
	// This may overflow because ask could be very large
	// and is otherwise unrelated to h.curArena.base.
	 := .curArena.base + 
	 := alignUp(, physPageSize)
	if  > .curArena.end || /* overflow */  < .curArena.base {
		// Not enough room in the current arena. Allocate more
		// arena space. This may not be contiguous with the
		// current arena, so we have to request the full ask.
		,  := .sysAlloc(, &.arenaHints, true)
		if  == nil {
			 := gcController.heapFree.load() + gcController.heapReleased.load() + gcController.heapInUse.load()
			print("runtime: out of memory: cannot allocate ", , "-byte block (", , " in use)\n")
			return 0, false
		}

		if uintptr() == .curArena.end {
			// The new space is contiguous with the old
			// space, so just extend the current space.
			.curArena.end = uintptr() + 
		} else {
			// The new space is discontiguous. Track what
			// remains of the current space and switch to
			// the new space. This should be rare.
			if  := .curArena.end - .curArena.base;  != 0 {
				// Transition this space from Reserved to Prepared and mark it
				// as released since we'll be able to start using it after updating
				// the page allocator and releasing the lock at any time.
				sysMap(unsafe.Pointer(.curArena.base), , &gcController.heapReleased)
				// Update stats.
				 := memstats.heapStats.acquire()
				atomic.Xaddint64(&.released, int64())
				memstats.heapStats.release()
				// Update the page allocator's structures to make this
				// space ready for allocation.
				.pages.grow(.curArena.base, )
				 += 
			}
			// Switch to the new space.
			.curArena.base = uintptr()
			.curArena.end = uintptr() + 
		}

		// Recalculate nBase.
		// We know this won't overflow, because sysAlloc returned
		// a valid region starting at h.curArena.base which is at
		// least ask bytes in size.
		 = alignUp(.curArena.base+, physPageSize)
	}

	// Grow into the current arena.
	 := .curArena.base
	.curArena.base = 

	// Transition the space we're going to use from Reserved to Prepared.
	//
	// The allocation is always aligned to the heap arena
	// size which is always > physPageSize, so its safe to
	// just add directly to heapReleased.
	sysMap(unsafe.Pointer(), -, &gcController.heapReleased)

	// The memory just allocated counts as both released
	// and idle, even though it's not yet backed by spans.
	 := memstats.heapStats.acquire()
	atomic.Xaddint64(&.released, int64(-))
	memstats.heapStats.release()

	// Update the page allocator's structures to make this
	// space ready for allocation.
	.pages.grow(, -)
	 +=  - 
	return , true
}

// Free the span back into the heap.
func ( *mheap) ( *mspan) {
	systemstack(func() {
		pageTraceFree(getg().m.p.ptr(), 0, .base(), .npages)

		lock(&.lock)
		if msanenabled {
			// Tell msan that this entire span is no longer in use.
			 := unsafe.Pointer(.base())
			 := .npages << _PageShift
			msanfree(, )
		}
		if asanenabled {
			// Tell asan that this entire span is no longer in use.
			 := unsafe.Pointer(.base())
			 := .npages << _PageShift
			asanpoison(, )
		}
		.freeSpanLocked(, spanAllocHeap)
		unlock(&.lock)
	})
}

// freeManual frees a manually-managed span returned by allocManual.
// typ must be the same as the spanAllocType passed to the allocManual that
// allocated s.
//
// This must only be called when gcphase == _GCoff. See mSpanState for
// an explanation.
//
// freeManual must be called on the system stack because it acquires
// the heap lock. See mheap for details.
//
//go:systemstack
func ( *mheap) ( *mspan,  spanAllocType) {
	pageTraceFree(getg().m.p.ptr(), 0, .base(), .npages)

	.needzero = 1
	lock(&.lock)
	.freeSpanLocked(, )
	unlock(&.lock)
}

func ( *mheap) ( *mspan,  spanAllocType) {
	assertLockHeld(&.lock)

	switch .state.get() {
	case mSpanManual:
		if .allocCount != 0 {
			throw("mheap.freeSpanLocked - invalid stack free")
		}
	case mSpanInUse:
		if .isUserArenaChunk {
			throw("mheap.freeSpanLocked - invalid free of user arena chunk")
		}
		if .allocCount != 0 || .sweepgen != .sweepgen {
			print("mheap.freeSpanLocked - span ", , " ptr ", hex(.base()), " allocCount ", .allocCount, " sweepgen ", .sweepgen, "/", .sweepgen, "\n")
			throw("mheap.freeSpanLocked - invalid free")
		}
		.pagesInUse.Add(-.npages)

		// Clear in-use bit in arena page bitmap.
		, ,  := pageIndexOf(.base())
		atomic.And8(&.pageInUse[], ^)
	default:
		throw("mheap.freeSpanLocked - invalid span state")
	}

	// Update stats.
	//
	// Mirrors the code in allocSpan.
	 := .npages * pageSize
	gcController.heapFree.add(int64())
	if  == spanAllocHeap {
		gcController.heapInUse.add(-int64())
	}
	// Update consistent stats.
	 := memstats.heapStats.acquire()
	switch  {
	case spanAllocHeap:
		atomic.Xaddint64(&.inHeap, -int64())
	case spanAllocStack:
		atomic.Xaddint64(&.inStacks, -int64())
	case spanAllocPtrScalarBits:
		atomic.Xaddint64(&.inPtrScalarBits, -int64())
	case spanAllocWorkBuf:
		atomic.Xaddint64(&.inWorkBufs, -int64())
	}
	memstats.heapStats.release()

	// Mark the space as free.
	.pages.free(.base(), .npages)

	// Free the span structure. We no longer have a use for it.
	.state.set(mSpanDead)
	.freeMSpanLocked()
}

// scavengeAll acquires the heap lock (blocking any additional
// manipulation of the page allocator) and iterates over the whole
// heap, scavenging every free page available.
//
// Must run on the system stack because it acquires the heap lock.
//
//go:systemstack
func ( *mheap) () {
	// Disallow malloc or panic while holding the heap lock. We do
	// this here because this is a non-mallocgc entry-point to
	// the mheap API.
	 := getg()
	.m.mallocing++

	// Force scavenge everything.
	 := .pages.scavenge(^uintptr(0), nil, true)

	.m.mallocing--

	if debug.scavtrace > 0 {
		printScavTrace(0, , true)
	}
}

//go:linkname runtime_debug_freeOSMemory runtime/debug.freeOSMemory
func () {
	GC()
	systemstack(func() { mheap_.scavengeAll() })
}

// Initialize a new span with the given start and npages.
func ( *mspan) ( uintptr,  uintptr) {
	// span is *not* zeroed.
	.next = nil
	.prev = nil
	.list = nil
	.startAddr = 
	.npages = 
	.allocCount = 0
	.spanclass = 0
	.elemsize = 0
	.speciallock.key = 0
	.specials = nil
	.needzero = 0
	.freeindex = 0
	.freeIndexForScan = 0
	.allocBits = nil
	.gcmarkBits = nil
	.pinnerBits = nil
	.state.set(mSpanDead)
	lockInit(&.speciallock, lockRankMspanSpecial)
}

func ( *mspan) () bool {
	return .list != nil
}

// Initialize an empty doubly-linked list.
func ( *mSpanList) () {
	.first = nil
	.last = nil
}

func ( *mSpanList) ( *mspan) {
	if .list !=  {
		print("runtime: failed mSpanList.remove span.npages=", .npages,
			" span=", , " prev=", .prev, " span.list=", .list, " list=", , "\n")
		throw("mSpanList.remove")
	}
	if .first ==  {
		.first = .next
	} else {
		.prev.next = .next
	}
	if .last ==  {
		.last = .prev
	} else {
		.next.prev = .prev
	}
	.next = nil
	.prev = nil
	.list = nil
}

func ( *mSpanList) () bool {
	return .first == nil
}

func ( *mSpanList) ( *mspan) {
	if .next != nil || .prev != nil || .list != nil {
		println("runtime: failed mSpanList.insert", , .next, .prev, .list)
		throw("mSpanList.insert")
	}
	.next = .first
	if .first != nil {
		// The list contains at least one span; link it in.
		// The last span in the list doesn't change.
		.first.prev = 
	} else {
		// The list contains no spans, so this is also the last span.
		.last = 
	}
	.first = 
	.list = 
}

func ( *mSpanList) ( *mspan) {
	if .next != nil || .prev != nil || .list != nil {
		println("runtime: failed mSpanList.insertBack", , .next, .prev, .list)
		throw("mSpanList.insertBack")
	}
	.prev = .last
	if .last != nil {
		// The list contains at least one span.
		.last.next = 
	} else {
		// The list contains no spans, so this is also the first span.
		.first = 
	}
	.last = 
	.list = 
}

// takeAll removes all spans from other and inserts them at the front
// of list.
func ( *mSpanList) ( *mSpanList) {
	if .isEmpty() {
		return
	}

	// Reparent everything in other to list.
	for  := .first;  != nil;  = .next {
		.list = 
	}

	// Concatenate the lists.
	if .isEmpty() {
		* = *
	} else {
		// Neither list is empty. Put other before list.
		.last.next = .first
		.first.prev = .last
		.first = .first
	}

	.first, .last = nil, nil
}

const (
	_KindSpecialFinalizer = 1
	_KindSpecialProfile   = 2
	// _KindSpecialReachable is a special used for tracking
	// reachability during testing.
	_KindSpecialReachable = 3
	// _KindSpecialPinCounter is a special used for objects that are pinned
	// multiple times
	_KindSpecialPinCounter = 4
	// Note: The finalizer special must be first because if we're freeing
	// an object, a finalizer special will cause the freeing operation
	// to abort, and we want to keep the other special records around
	// if that happens.
)

type special struct {
	_      sys.NotInHeap
	next   *special // linked list in span
	offset uint16   // span offset of object
	kind   byte     // kind of special
}

// spanHasSpecials marks a span as having specials in the arena bitmap.
func ( *mspan) {
	 := (.base() / pageSize) % pagesPerArena
	 := arenaIndex(.base())
	 := mheap_.arenas[.l1()][.l2()]
	atomic.Or8(&.pageSpecials[/8], uint8(1)<<(%8))
}

// spanHasNoSpecials marks a span as having no specials in the arena bitmap.
func ( *mspan) {
	 := (.base() / pageSize) % pagesPerArena
	 := arenaIndex(.base())
	 := mheap_.arenas[.l1()][.l2()]
	atomic.And8(&.pageSpecials[/8], ^(uint8(1) << ( % 8)))
}

// Adds the special record s to the list of special records for
// the object p. All fields of s should be filled in except for
// offset & next, which this routine will fill in.
// Returns true if the special was successfully added, false otherwise.
// (The add will fail only if a record with the same p and s->kind
// already exists.)
func ( unsafe.Pointer,  *special) bool {
	 := spanOfHeap(uintptr())
	if  == nil {
		throw("addspecial on invalid pointer")
	}

	// Ensure that the span is swept.
	// Sweeping accesses the specials list w/o locks, so we have
	// to synchronize with it. And it's just much safer.
	 := acquirem()
	.ensureSwept()

	 := uintptr() - .base()
	 := .kind

	lock(&.speciallock)

	// Find splice point, check for existing record.
	,  := .specialFindSplicePoint(, )
	if ! {
		// Splice in record, fill in offset.
		.offset = uint16()
		.next = *
		* = 
		spanHasSpecials()
	}

	unlock(&.speciallock)
	releasem()
	return ! // already exists
}

// Removes the Special record of the given kind for the object p.
// Returns the record if the record existed, nil otherwise.
// The caller must FixAlloc_Free the result.
func ( unsafe.Pointer,  uint8) *special {
	 := spanOfHeap(uintptr())
	if  == nil {
		throw("removespecial on invalid pointer")
	}

	// Ensure that the span is swept.
	// Sweeping accesses the specials list w/o locks, so we have
	// to synchronize with it. And it's just much safer.
	 := acquirem()
	.ensureSwept()

	 := uintptr() - .base()

	var  *special
	lock(&.speciallock)

	,  := .specialFindSplicePoint(, )
	if  {
		 := *
		* = .next
		 = 
	}
	if .specials == nil {
		spanHasNoSpecials()
	}
	unlock(&.speciallock)
	releasem()
	return 
}

// Find a splice point in the sorted list and check for an already existing
// record. Returns a pointer to the next-reference in the list predecessor.
// Returns true, if the referenced item is an exact match.
func ( *mspan) ( uintptr,  byte) (**special, bool) {
	// Find splice point, check for existing record.
	 := &.specials
	 := false
	for {
		 := *
		if  == nil {
			break
		}
		if  == uintptr(.offset) &&  == .kind {
			 = true
			break
		}
		if  < uintptr(.offset) || ( == uintptr(.offset) &&  < .kind) {
			break
		}
		 = &.next
	}
	return , 
}

// The described object has a finalizer set for it.
//
// specialfinalizer is allocated from non-GC'd memory, so any heap
// pointers must be specially handled.
type specialfinalizer struct {
	_       sys.NotInHeap
	special special
	fn      *funcval // May be a heap pointer.
	nret    uintptr
	fint    *_type   // May be a heap pointer, but always live.
	ot      *ptrtype // May be a heap pointer, but always live.
}

// Adds a finalizer to the object p. Returns true if it succeeded.
func ( unsafe.Pointer,  *funcval,  uintptr,  *_type,  *ptrtype) bool {
	lock(&mheap_.speciallock)
	 := (*specialfinalizer)(mheap_.specialfinalizeralloc.alloc())
	unlock(&mheap_.speciallock)
	.special.kind = _KindSpecialFinalizer
	.fn = 
	.nret = 
	.fint = 
	.ot = 
	if addspecial(, &.special) {
		// This is responsible for maintaining the same
		// GC-related invariants as markrootSpans in any
		// situation where it's possible that markrootSpans
		// has already run but mark termination hasn't yet.
		if gcphase != _GCoff {
			, ,  := findObject(uintptr(), 0, 0)
			 := acquirem()
			 := &.p.ptr().gcw
			// Mark everything reachable from the object
			// so it's retained for the finalizer.
			if !.spanclass.noscan() {
				scanobject(, )
			}
			// Mark the finalizer itself, since the
			// special isn't part of the GC'd heap.
			scanblock(uintptr(unsafe.Pointer(&.fn)), goarch.PtrSize, &oneptrmask[0], , nil)
			releasem()
		}
		return true
	}

	// There was an old finalizer
	lock(&mheap_.speciallock)
	mheap_.specialfinalizeralloc.free(unsafe.Pointer())
	unlock(&mheap_.speciallock)
	return false
}

// Removes the finalizer (if any) from the object p.
func ( unsafe.Pointer) {
	 := (*specialfinalizer)(unsafe.Pointer(removespecial(, _KindSpecialFinalizer)))
	if  == nil {
		return // there wasn't a finalizer to remove
	}
	lock(&mheap_.speciallock)
	mheap_.specialfinalizeralloc.free(unsafe.Pointer())
	unlock(&mheap_.speciallock)
}

// The described object is being heap profiled.
type specialprofile struct {
	_       sys.NotInHeap
	special special
	b       *bucket
}

// Set the heap profile bucket associated with addr to b.
func ( unsafe.Pointer,  *bucket) {
	lock(&mheap_.speciallock)
	 := (*specialprofile)(mheap_.specialprofilealloc.alloc())
	unlock(&mheap_.speciallock)
	.special.kind = _KindSpecialProfile
	.b = 
	if !addspecial(, &.special) {
		throw("setprofilebucket: profile already set")
	}
}

// specialReachable tracks whether an object is reachable on the next
// GC cycle. This is used by testing.
type specialReachable struct {
	special   special
	done      bool
	reachable bool
}

// specialPinCounter tracks whether an object is pinned multiple times.
type specialPinCounter struct {
	special special
	counter uintptr
}

// specialsIter helps iterate over specials lists.
type specialsIter struct {
	pprev **special
	s     *special
}

func ( *mspan) specialsIter {
	return specialsIter{&.specials, .specials}
}

func ( *specialsIter) () bool {
	return .s != nil
}

func ( *specialsIter) () {
	.pprev = &.s.next
	.s = *.pprev
}

// unlinkAndNext removes the current special from the list and moves
// the iterator to the next special. It returns the unlinked special.
func ( *specialsIter) () *special {
	 := .s
	.s = .next
	*.pprev = .s
	return 
}

// freeSpecial performs any cleanup on special s and deallocates it.
// s must already be unlinked from the specials list.
func ( *special,  unsafe.Pointer,  uintptr) {
	switch .kind {
	case _KindSpecialFinalizer:
		 := (*specialfinalizer)(unsafe.Pointer())
		queuefinalizer(, .fn, .nret, .fint, .ot)
		lock(&mheap_.speciallock)
		mheap_.specialfinalizeralloc.free(unsafe.Pointer())
		unlock(&mheap_.speciallock)
	case _KindSpecialProfile:
		 := (*specialprofile)(unsafe.Pointer())
		mProf_Free(.b, )
		lock(&mheap_.speciallock)
		mheap_.specialprofilealloc.free(unsafe.Pointer())
		unlock(&mheap_.speciallock)
	case _KindSpecialReachable:
		 := (*specialReachable)(unsafe.Pointer())
		.done = true
		// The creator frees these.
	case _KindSpecialPinCounter:
		lock(&mheap_.speciallock)
		mheap_.specialPinCounterAlloc.free(unsafe.Pointer())
		unlock(&mheap_.speciallock)
	default:
		throw("bad special kind")
		panic("not reached")
	}
}

// gcBits is an alloc/mark bitmap. This is always used as gcBits.x.
type gcBits struct {
	_ sys.NotInHeap
	x uint8
}

// bytep returns a pointer to the n'th byte of b.
func ( *gcBits) ( uintptr) *uint8 {
	return addb(&.x, )
}

// bitp returns a pointer to the byte containing bit n and a mask for
// selecting that bit from *bytep.
func ( *gcBits) ( uintptr) ( *uint8,  uint8) {
	return .bytep( / 8), 1 << ( % 8)
}

const gcBitsChunkBytes = uintptr(64 << 10)
const gcBitsHeaderBytes = unsafe.Sizeof(gcBitsHeader{})

type gcBitsHeader struct {
	free uintptr // free is the index into bits of the next free byte.
	next uintptr // *gcBits triggers recursive type bug. (issue 14620)
}

type gcBitsArena struct {
	_ sys.NotInHeap
	// gcBitsHeader // side step recursive type bug (issue 14620) by including fields by hand.
	free uintptr // free is the index into bits of the next free byte; read/write atomically
	next *gcBitsArena
	bits [gcBitsChunkBytes - gcBitsHeaderBytes]gcBits
}

var gcBitsArenas struct {
	lock     mutex
	free     *gcBitsArena
	next     *gcBitsArena // Read atomically. Write atomically under lock.
	current  *gcBitsArena
	previous *gcBitsArena
}

// tryAlloc allocates from b or returns nil if b does not have enough room.
// This is safe to call concurrently.
func ( *gcBitsArena) ( uintptr) *gcBits {
	if  == nil || atomic.Loaduintptr(&.free)+ > uintptr(len(.bits)) {
		return nil
	}
	// Try to allocate from this block.
	 := atomic.Xadduintptr(&.free, )
	if  > uintptr(len(.bits)) {
		return nil
	}
	// There was enough room.
	 :=  - 
	return &.bits[]
}

// newMarkBits returns a pointer to 8 byte aligned bytes
// to be used for a span's mark bits.
func ( uintptr) *gcBits {
	 := uintptr(( + 63) / 64)
	 :=  * 8

	// Try directly allocating from the current head arena.
	 := (*gcBitsArena)(atomic.Loadp(unsafe.Pointer(&gcBitsArenas.next)))
	if  := .tryAlloc();  != nil {
		return 
	}

	// There's not enough room in the head arena. We may need to
	// allocate a new arena.
	lock(&gcBitsArenas.lock)
	// Try the head arena again, since it may have changed. Now
	// that we hold the lock, the list head can't change, but its
	// free position still can.
	if  := gcBitsArenas.next.tryAlloc();  != nil {
		unlock(&gcBitsArenas.lock)
		return 
	}

	// Allocate a new arena. This may temporarily drop the lock.
	 := newArenaMayUnlock()
	// If newArenaMayUnlock dropped the lock, another thread may
	// have put a fresh arena on the "next" list. Try allocating
	// from next again.
	if  := gcBitsArenas.next.tryAlloc();  != nil {
		// Put fresh back on the free list.
		// TODO: Mark it "already zeroed"
		.next = gcBitsArenas.free
		gcBitsArenas.free = 
		unlock(&gcBitsArenas.lock)
		return 
	}

	// Allocate from the fresh arena. We haven't linked it in yet, so
	// this cannot race and is guaranteed to succeed.
	 := .tryAlloc()
	if  == nil {
		throw("markBits overflow")
	}

	// Add the fresh arena to the "next" list.
	.next = gcBitsArenas.next
	atomic.StorepNoWB(unsafe.Pointer(&gcBitsArenas.next), unsafe.Pointer())

	unlock(&gcBitsArenas.lock)
	return 
}

// newAllocBits returns a pointer to 8 byte aligned bytes
// to be used for this span's alloc bits.
// newAllocBits is used to provide newly initialized spans
// allocation bits. For spans not being initialized the
// mark bits are repurposed as allocation bits when
// the span is swept.
func ( uintptr) *gcBits {
	return newMarkBits()
}

// nextMarkBitArenaEpoch establishes a new epoch for the arenas
// holding the mark bits. The arenas are named relative to the
// current GC cycle which is demarcated by the call to finishweep_m.
//
// All current spans have been swept.
// During that sweep each span allocated room for its gcmarkBits in
// gcBitsArenas.next block. gcBitsArenas.next becomes the gcBitsArenas.current
// where the GC will mark objects and after each span is swept these bits
// will be used to allocate objects.
// gcBitsArenas.current becomes gcBitsArenas.previous where the span's
// gcAllocBits live until all the spans have been swept during this GC cycle.
// The span's sweep extinguishes all the references to gcBitsArenas.previous
// by pointing gcAllocBits into the gcBitsArenas.current.
// The gcBitsArenas.previous is released to the gcBitsArenas.free list.
func () {
	lock(&gcBitsArenas.lock)
	if gcBitsArenas.previous != nil {
		if gcBitsArenas.free == nil {
			gcBitsArenas.free = gcBitsArenas.previous
		} else {
			// Find end of previous arenas.
			 := gcBitsArenas.previous
			for  = gcBitsArenas.previous; .next != nil;  = .next {
			}
			.next = gcBitsArenas.free
			gcBitsArenas.free = gcBitsArenas.previous
		}
	}
	gcBitsArenas.previous = gcBitsArenas.current
	gcBitsArenas.current = gcBitsArenas.next
	atomic.StorepNoWB(unsafe.Pointer(&gcBitsArenas.next), nil) // newMarkBits calls newArena when needed
	unlock(&gcBitsArenas.lock)
}

// newArenaMayUnlock allocates and zeroes a gcBits arena.
// The caller must hold gcBitsArena.lock. This may temporarily release it.
func () *gcBitsArena {
	var  *gcBitsArena
	if gcBitsArenas.free == nil {
		unlock(&gcBitsArenas.lock)
		 = (*gcBitsArena)(sysAlloc(gcBitsChunkBytes, &memstats.gcMiscSys))
		if  == nil {
			throw("runtime: cannot allocate memory")
		}
		lock(&gcBitsArenas.lock)
	} else {
		 = gcBitsArenas.free
		gcBitsArenas.free = gcBitsArenas.free.next
		memclrNoHeapPointers(unsafe.Pointer(), gcBitsChunkBytes)
	}
	.next = nil
	// If result.bits is not 8 byte aligned adjust index so
	// that &result.bits[result.free] is 8 byte aligned.
	if uintptr(unsafe.Offsetof(gcBitsArena{}.bits))&7 == 0 {
		.free = 0
	} else {
		.free = 8 - (uintptr(unsafe.Pointer(&.bits[0])) & 7)
	}
	return 
}