Source: mpagealloc.go in package runtime

Page allocator. The page allocator manages mapped pages (defined by pageSize, NOT physPageSize) for allocation and re-use. It is embedded into mheap. Pages are managed using a bitmap that is sharded into chunks. In the bitmap, 1 means in-use, and 0 means free. The bitmap spans the process's address space. Chunks are managed in a sparse-array-style structure similar to mheap.arenas, since the bitmap may be large on some systems. The bitmap is efficiently searched by using a radix tree in combination with fast bit-wise intrinsics. Allocation is performed using an address-ordered first-fit approach. Each entry in the radix tree is a summary that describes three properties of a particular region of the address space: the number of contiguous free pages at the start and end of the region it represents, and the maximum number of contiguous free pages found anywhere in that region. Each level of the radix tree is stored as one contiguous array, which represents a different granularity of subdivision of the processes' address space. Thus, this radix tree is actually implicit in these large arrays, as opposed to having explicit dynamically-allocated pointer-based node structures. Naturally, these arrays may be quite large for system with large address spaces, so in these cases they are mapped into memory as needed. The leaf summaries of the tree correspond to a bitmap chunk. The root level (referred to as L0 and index 0 in pageAlloc.summary) has each summary represent the largest section of address space (16 GiB on 64-bit systems), with each subsequent level representing successively smaller subsections until we reach the finest granularity at the leaves, a chunk. More specifically, each summary in each level (except for leaf summaries) represents some number of entries in the following level. For example, each summary in the root level may represent a 16 GiB region of address space, and in the next level there could be 8 corresponding entries which represent 2 GiB subsections of that 16 GiB region, each of which could correspond to 8 entries in the next level which each represent 256 MiB regions, and so on. Thus, this design only scales to heaps so large, but can always be extended to larger heaps by simply adding levels to the radix tree, which mostly costs additional virtual address space. The choice of managing large arrays also means that a large amount of virtual address space may be reserved by the runtime.


package runtime

import (
	"runtime/internal/atomic"
	"unsafe"
)

The size of a bitmap chunk, i.e. the amount of bits (that is, pages) to consider in the bitmap at once.

	pallocChunkPages    = 1 << logPallocChunkPages
	pallocChunkBytes    = pallocChunkPages * pageSize
	logPallocChunkPages = 9
	logPallocChunkBytes = logPallocChunkPages + pageShift

The number of radix bits for each level. The value of 3 is chosen such that the block of summaries we need to scan at each level fits in 64 bytes (2^3 summaries * 8 bytes per summary), which is close to the L1 cache line width on many systems. Also, a value of 3 fits 4 tree levels perfectly into the 21-bit pallocBits summary field at the root level. The following equation explains how each of the constants relate: summaryL0Bits + (summaryLevels-1)*summaryLevelBits + logPallocChunkBytes = heapAddrBits summaryLevels is an architecture-dependent value defined in mpagealloc_*.go.

	summaryLevelBits = 3
	summaryL0Bits    = heapAddrBits - logPallocChunkBytes - (summaryLevels-1)*summaryLevelBits

pallocChunksL2Bits is the number of bits of the chunk index number covered by the second level of the chunks map. See (*pageAlloc).chunks for more details. Update the documentation there should this change.

	pallocChunksL2Bits  = heapAddrBits - logPallocChunkBytes - pallocChunksL1Bits
	pallocChunksL1Shift = pallocChunksL2Bits
)

Maximum searchAddr value, which indicates that the heap has no free space. We alias maxOffAddr just to make it clear that this is the maximum address for the page allocator's search space. See maxOffAddr for details.

var maxSearchAddr = maxOffAddr

Global chunk index. Represents an index into the leaf level of the radix tree. Similar to arenaIndex, except instead of arenas, it divides the address space into chunks.

type chunkIdx uint

chunkIndex returns the global index of the palloc chunk containing the pointer p.

func chunkIndex(p uintptr) chunkIdx {
	return chunkIdx((p - arenaBaseOffset) / pallocChunkBytes)
}

chunkIndex returns the base address of the palloc chunk at index ci.

func chunkBase(ci chunkIdx) uintptr {
	return uintptr(ci)*pallocChunkBytes + arenaBaseOffset
}

chunkPageIndex computes the index of the page that contains p, relative to the chunk which contains p.

func chunkPageIndex(p uintptr) uint {
	return uint(p % pallocChunkBytes / pageSize)
}

l1 returns the index into the first level of (*pageAlloc).chunks.

func (i chunkIdx) l1() uint {

Let the compiler optimize this away if there's no L1 map.

		return 0
	} else {
		return uint(i) >> pallocChunksL1Shift
	}
}

l2 returns the index into the second level of (*pageAlloc).chunks.

func (i chunkIdx) l2() uint {
	if pallocChunksL1Bits == 0 {
		return uint(i)
	} else {
		return uint(i) & (1<<pallocChunksL2Bits - 1)
	}
}

offAddrToLevelIndex converts an address in the offset address space to the index into summary[level] containing addr.

func offAddrToLevelIndex(level int, addr offAddr) int {
	return int((addr.a - arenaBaseOffset) >> levelShift[level])
}

levelIndexToOffAddr converts an index into summary[level] into the corresponding address in the offset address space.

func levelIndexToOffAddr(level, idx int) offAddr {
	return offAddr{(uintptr(idx) << levelShift[level]) + arenaBaseOffset}
}

addrsToSummaryRange converts base and limit pointers into a range of entries for the given summary level. The returned range is inclusive on the lower bound and exclusive on the upper bound.

This is slightly more nuanced than just a shift for the exclusive upper-bound. Note that the exclusive upper bound may be within a summary at this level, meaning if we just do the obvious computation hi will end up being an inclusive upper bound. Unfortunately, just adding 1 to that is too broad since we might be on the very edge of of a summary's max page count boundary for this level (1 << levelLogPages[level]). So, make limit an inclusive upper bound then shift, then add 1, so we get an exclusive upper bound at the end.

	lo = int((base - arenaBaseOffset) >> levelShift[level])
	hi = int(((limit-1)-arenaBaseOffset)>>levelShift[level]) + 1
	return
}

blockAlignSummaryRange aligns indices into the given level to that level's block width (1 << levelBits[level]). It assumes lo is inclusive and hi is exclusive, and so aligns them down and up respectively.

func blockAlignSummaryRange(level int, lo, hi int) (int, int) {
	e := uintptr(1) << levelBits[level]
	return int(alignDown(uintptr(lo), e)), int(alignUp(uintptr(hi), e))
}

Radix tree of summaries. Each slice's cap represents the whole memory reservation. Each slice's len reflects the allocator's maximum known mapped heap address for that level. The backing store of each summary level is reserved in init and may or may not be committed in grow (small address spaces may commit all the memory in init). The purpose of keeping len <= cap is to enforce bounds checks on the top end of the slice so that instead of an unknown runtime segmentation fault, we get a much friendlier out-of-bounds error. To iterate over a summary level, use inUse to determine which ranges are currently available. Otherwise one might try to access memory which is only Reserved which may result in a hard fault. We may still get segmentation faults < len since some of that memory may not be committed yet.

	summary [summaryLevels][]pallocSum

chunks is a slice of bitmap chunks. The total size of chunks is quite large on most 64-bit platforms (O(GiB) or more) if flattened, so rather than making one large mapping (which has problems on some platforms, even when PROT_NONE) we use a two-level sparse array approach similar to the arena index in mheap. To find the chunk containing a memory address `a`, do: chunkOf(chunkIndex(a)) Below is a table describing the configuration for chunks for various heapAddrBits supported by the runtime. heapAddrBits | L1 Bits | L2 Bits | L2 Entry Size ------------------------------------------------ 32 | 0 | 10 | 128 KiB 33 (iOS) | 0 | 11 | 256 KiB 48 | 13 | 13 | 1 MiB There's no reason to use the L1 part of chunks on 32-bit, the address space is small so the L2 is small. For platforms with a 48-bit address space, we pick the L1 such that the L2 is 1 MiB in size, which is a good balance between low granularity without making the impact on BSS too high (note the L1 is stored directly in pageAlloc). To iterate over the bitmap, use inUse to determine which ranges are currently available. Otherwise one might iterate over unused ranges. TODO(mknyszek): Consider changing the definition of the bitmap such that 1 means free and 0 means in-use so that summaries and the bitmaps align better on zero-values.

	chunks [1 << pallocChunksL1Bits]*[1 << pallocChunksL2Bits]pallocData

The address to start an allocation search with. It must never point to any memory that is not contained in inUse, i.e. inUse.contains(searchAddr.addr()) must always be true. The one exception to this rule is that it may take on the value of maxOffAddr to indicate that the heap is exhausted. We guarantee that all valid heap addresses below this value are allocated and not worth searching.

	searchAddr offAddr

start and end represent the chunk indices which pageAlloc knows about. It assumes chunks in the range [start, end) are currently ready to use.

	start, end chunkIdx

inUse is a slice of ranges of address space which are known by the page allocator to be currently in-use (passed to grow). This field is currently unused on 32-bit architectures but is harmless to track. We care much more about having a contiguous heap in these cases and take additional measures to ensure that, so in nearly all cases this should have just 1 element. All access is protected by the mheapLock.

	inUse addrRanges

scav stores the scavenger state. All fields are protected by mheapLock.

inUse is a slice of ranges of address space which have not yet been looked at by the scavenger.

		inUse addrRanges

gen is the scavenge generation number.

		gen uint32

reservationBytes is how large of a reservation should be made in bytes of address space for each scavenge iteration.

		reservationBytes uintptr

released is the amount of memory released this generation.

		released uintptr

scavLWM is the lowest (offset) address that the scavenger reached this scavenge generation.

		scavLWM offAddr

freeHWM is the highest (offset) address of a page that was freed to the page allocator this scavenge generation.

		freeHWM offAddr
	}

mheap_.lock. This level of indirection makes it possible to test pageAlloc indepedently of the runtime allocator.

	mheapLock *mutex

sysStat is the runtime memstat to update when new system memory is committed by the pageAlloc for allocation metadata.

	sysStat *sysMemStat

Whether or not this struct is being used in tests.

	test bool
}

func (p *pageAlloc) init(mheapLock *mutex, sysStat *sysMemStat) {

We can't represent 1<<levelLogPages[0] pages, the maximum number of pages we need to represent at the root level, in a summary, which is a big problem. Throw.

		print("runtime: root level max pages = ", 1<<levelLogPages[0], "\n")
		print("runtime: summary max pages = ", maxPackedValue, "\n")
		throw("root level max pages doesn't fit in summary")
	}
	p.sysStat = sysStat

Initialize p.inUse.

	p.inUse.init(sysStat)

System-dependent initialization.

	p.sysInit()

Start with the searchAddr in a state indicating there's no free memory.

	p.searchAddr = maxSearchAddr

Set the mheapLock.

	p.mheapLock = mheapLock

Initialize scavenge tracking state.

	p.scav.scavLWM = maxSearchAddr
}

tryChunkOf returns the bitmap data for the given chunk. Returns nil if the chunk data has not been mapped.

func (p *pageAlloc) tryChunkOf(ci chunkIdx) *pallocData {
	l2 := p.chunks[ci.l1()]
	if l2 == nil {
		return nil
	}
	return &l2[ci.l2()]
}

chunkOf returns the chunk at the given chunk index. The chunk index must be valid or this method may throw.

func (p *pageAlloc) chunkOf(ci chunkIdx) *pallocData {
	return &p.chunks[ci.l1()][ci.l2()]
}

grow sets up the metadata for the address range [base, base+size). It may allocate metadata, in which case *p.sysStat will be updated. p.mheapLock must be held.

func (p *pageAlloc) grow(base, size uintptr) {
	assertLockHeld(p.mheapLock)

Round up to chunks, since we can't deal with increments smaller than chunks. Also, sysGrow expects aligned values.

	limit := alignUp(base+size, pallocChunkBytes)
	base = alignDown(base, pallocChunkBytes)

Grow the summary levels in a system-dependent manner. We just update a bunch of additional metadata here.

	p.sysGrow(base, limit)

Update p.start and p.end. If no growth happened yet, start == 0. This is generally safe since the zero page is unmapped.

	firstGrowth := p.start == 0
	start, end := chunkIndex(base), chunkIndex(limit)
	if firstGrowth || start < p.start {
		p.start = start
	}
	if end > p.end {
		p.end = end

Note that [base, limit) will never overlap with any existing range inUse because grow only ever adds never-used memory regions to the page allocator.

	p.inUse.add(makeAddrRange(base, limit))

A grow operation is a lot like a free operation, so if our chunk ends up below p.searchAddr, update p.searchAddr to the new address, just like in free.

	if b := (offAddr{base}); b.lessThan(p.searchAddr) {
		p.searchAddr = b
	}

Add entries into chunks, which is sparse, if needed. Then, initialize the bitmap. Newly-grown memory is always considered scavenged. Set all the bits in the scavenged bitmaps high.

	for c := chunkIndex(base); c < chunkIndex(limit); c++ {

Create the necessary l2 entry. Store it atomically to avoid races with readers which don't acquire the heap lock.

			r := sysAlloc(unsafe.Sizeof(*p.chunks[0]), p.sysStat)
			atomic.StorepNoWB(unsafe.Pointer(&p.chunks[c.l1()]), r)
		}
		p.chunkOf(c).scavenged.setRange(0, pallocChunkPages)
	}

Update summaries accordingly. The grow acts like a free, so we need to ensure this newly-free memory is visible in the summaries.

	p.update(base, size/pageSize, true, false)
}

update updates heap metadata. It must be called each time the bitmap is updated. If contig is true, update does some optimizations assuming that there was a contiguous allocation or free between addr and addr+npages. alloc indicates whether the operation performed was an allocation or a free. p.mheapLock must be held.

func (p *pageAlloc) update(base, npages uintptr, contig, alloc bool) {
	assertLockHeld(p.mheapLock)

base, limit, start, and end are inclusive.

	limit := base + npages*pageSize - 1
	sc, ec := chunkIndex(base), chunkIndex(limit)

Handle updating the lowest level first.

Fast path: the allocation doesn't span more than one chunk, so update this one and if the summary didn't change, return.

		x := p.summary[len(p.summary)-1][sc]
		y := p.chunkOf(sc).summarize()
		if x == y {
			return
		}
		p.summary[len(p.summary)-1][sc] = y

Slow contiguous path: the allocation spans more than one chunk and at least one summary is guaranteed to change.

		summary := p.summary[len(p.summary)-1]

Update the summary for chunk sc.

		summary[sc] = p.chunkOf(sc).summarize()

Update the summaries for chunks in between, which are either totally allocated or freed.

		whole := p.summary[len(p.summary)-1][sc+1 : ec]

Should optimize into a memclr.

			for i := range whole {
				whole[i] = 0
			}
		} else {
			for i := range whole {
				whole[i] = freeChunkSum
			}
		}

Update the summary for chunk ec.

		summary[ec] = p.chunkOf(ec).summarize()

Slow general path: the allocation spans more than one chunk and at least one summary is guaranteed to change. We can't assume a contiguous allocation happened, so walk over every chunk in the range and manually recompute the summary.

		summary := p.summary[len(p.summary)-1]
		for c := sc; c <= ec; c++ {
			summary[c] = p.chunkOf(c).summarize()
		}
	}

Walk up the radix tree and update the summaries appropriately.

	changed := true

Update summaries at level l from summaries at level l+1.

		changed = false

"Constants" for the previous level which we need to compute the summary from that level.

		logEntriesPerBlock := levelBits[l+1]
		logMaxPages := levelLogPages[l+1]

lo and hi describe all the parts of the level we need to look at.

		lo, hi := addrsToSummaryRange(l, base, limit+1)

Iterate over each block, updating the corresponding summary in the less-granular level.

		for i := lo; i < hi; i++ {
			children := p.summary[l+1][i<<logEntriesPerBlock : (i+1)<<logEntriesPerBlock]
			sum := mergeSummaries(children, logMaxPages)
			old := p.summary[l][i]
			if old != sum {
				changed = true
				p.summary[l][i] = sum
			}
		}
	}
}

allocRange marks the range of memory [base, base+npages*pageSize) as allocated. It also updates the summaries to reflect the newly-updated bitmap. Returns the amount of scavenged memory in bytes present in the allocated range. p.mheapLock must be held.

func (p *pageAlloc) allocRange(base, npages uintptr) uintptr {
	assertLockHeld(p.mheapLock)

	limit := base + npages*pageSize - 1
	sc, ec := chunkIndex(base), chunkIndex(limit)
	si, ei := chunkPageIndex(base), chunkPageIndex(limit)

	scav := uint(0)

The range doesn't cross any chunk boundaries.

		chunk := p.chunkOf(sc)
		scav += chunk.scavenged.popcntRange(si, ei+1-si)
		chunk.allocRange(si, ei+1-si)

The range crosses at least one chunk boundary.

		chunk := p.chunkOf(sc)
		scav += chunk.scavenged.popcntRange(si, pallocChunkPages-si)
		chunk.allocRange(si, pallocChunkPages-si)
		for c := sc + 1; c < ec; c++ {
			chunk := p.chunkOf(c)
			scav += chunk.scavenged.popcntRange(0, pallocChunkPages)
			chunk.allocAll()
		}
		chunk = p.chunkOf(ec)
		scav += chunk.scavenged.popcntRange(0, ei+1)
		chunk.allocRange(0, ei+1)
	}
	p.update(base, npages, true, true)
	return uintptr(scav) * pageSize
}

findMappedAddr returns the smallest mapped offAddr that is >= addr. That is, if addr refers to mapped memory, then it is returned. If addr is higher than any mapped region, then it returns maxOffAddr. p.mheapLock must be held.

func (p *pageAlloc) findMappedAddr(addr offAddr) offAddr {
	assertLockHeld(p.mheapLock)

If we're not in a test, validate first by checking mheap_.arenas. This is a fast path which is only safe to use outside of testing.

	ai := arenaIndex(addr.addr())
	if p.test || mheap_.arenas[ai.l1()] == nil || mheap_.arenas[ai.l1()][ai.l2()] == nil {
		vAddr, ok := p.inUse.findAddrGreaterEqual(addr.addr())
		if ok {
			return offAddr{vAddr}

The candidate search address is greater than any known address, which means we definitely have no free memory left.

			return maxOffAddr
		}
	}
	return addr
}

find searches for the first (address-ordered) contiguous free region of npages in size and returns a base address for that region. It uses p.searchAddr to prune its search and assumes that no palloc chunks below chunkIndex(p.searchAddr) contain any free memory at all. find also computes and returns a candidate p.searchAddr, which may or may not prune more of the address space than p.searchAddr already does. This candidate is always a valid p.searchAddr. find represents the slow path and the full radix tree search. Returns a base address of 0 on failure, in which case the candidate searchAddr returned is invalid and must be ignored. p.mheapLock must be held.

func (p *pageAlloc) find(npages uintptr) (uintptr, offAddr) {
	assertLockHeld(p.mheapLock)

Search algorithm. This algorithm walks each level l of the radix tree from the root level to the leaf level. It iterates over at most 1 << levelBits[l] of entries in a given level in the radix tree, and uses the summary information to find either: 1) That a given subtree contains a large enough contiguous region, at which point it continues iterating on the next level, or 2) That there are enough contiguous boundary-crossing bits to satisfy the allocation, at which point it knows exactly where to start allocating from. i tracks the index into the current level l's structure for the contiguous 1 << levelBits[l] entries we're actually interested in. NOTE: Technically this search could allocate a region which crosses the arenaBaseOffset boundary, which when arenaBaseOffset != 0, is a discontinuity. However, the only way this could happen is if the page at the zero address is mapped, and this is impossible on every system we support where arenaBaseOffset != 0. So, the discontinuity is already encoded in the fact that the OS will never map the zero page for us, and this function doesn't try to handle this case in any way.

i is the beginning of the block of entries we're searching at the current level.

	i := 0

firstFree is the region of address space that we are certain to find the first free page in the heap. base and bound are the inclusive bounds of this window, and both are addresses in the linearized, contiguous view of the address space (with arenaBaseOffset pre-added). At each level, this window is narrowed as we find the memory region containing the first free page of memory. To begin with, the range reflects the full process address space. firstFree is updated by calling foundFree each time free space in the heap is discovered. At the end of the search, base.addr() is the best new searchAddr we could deduce in this search.

	firstFree := struct {
		base, bound offAddr
	}{
		base:  minOffAddr,
		bound: maxOffAddr,

foundFree takes the given address range [addr, addr+size) and updates firstFree if it is a narrower range. The input range must either be fully contained within firstFree or not overlap with it at all. This way, we'll record the first summary we find with any free pages on the root level and narrow that down if we descend into that summary. But as soon as we need to iterate beyond that summary in a level to find a large enough range, we'll stop narrowing.

	foundFree := func(addr offAddr, size uintptr) {

This range fits within the current firstFree window, so narrow down the firstFree window to the base and bound of this range.

			firstFree.base = addr
			firstFree.bound = addr.add(size - 1)

This range only partially overlaps with the firstFree range, so throw.

			print("runtime: addr = ", hex(addr.addr()), ", size = ", size, "\n")
			print("runtime: base = ", hex(firstFree.base.addr()), ", bound = ", hex(firstFree.bound.addr()), "\n")
			throw("range partially overlaps")
		}
	}

lastSum is the summary which we saw on the previous level that made us move on to the next level. Used to print additional information in the case of a catastrophic failure. lastSumIdx is that summary's index in the previous level.

	lastSum := packPallocSum(0, 0, 0)
	lastSumIdx := -1

nextLevel:

For the root level, entriesPerBlock is the whole level.

		entriesPerBlock := 1 << levelBits[l]
		logMaxPages := levelLogPages[l]

We've moved into a new level, so let's update i to our new starting index. This is a no-op for level 0.

		i <<= levelBits[l]

Slice out the block of entries we care about.

		entries := p.summary[l][i : i+entriesPerBlock]

Determine j0, the first index we should start iterating from. The searchAddr may help us eliminate iterations if we followed the searchAddr on the previous level or we're on the root leve, in which case the searchAddr should be the same as i after levelShift.

		j0 := 0
		if searchIdx := offAddrToLevelIndex(l, p.searchAddr); searchIdx&^(entriesPerBlock-1) == i {
			j0 = searchIdx & (entriesPerBlock - 1)
		}

Run over the level entries looking for a contiguous run of at least npages either within an entry or across entries. base contains the page index (relative to the first entry's first page) of the currently considered run of consecutive pages. size contains the size of the currently considered run of consecutive pages.

		var base, size uint
		for j := j0; j < len(entries); j++ {
			sum := entries[j]

A full entry means we broke any streak and that we should skip it altogether.

				size = 0
				continue
			}

We've encountered a non-zero summary which means free memory, so update firstFree.

			foundFree(levelIndexToOffAddr(l, i+j), (uintptr(1)<<logMaxPages)*pageSize)

			s := sum.start()

If size == 0 we don't have a run yet, which means base isn't valid. So, set base to the first page in this block.

				if size == 0 {
					base = uint(j) << logMaxPages

We hit npages; we're done!

				size += s
				break
			}

The entry itself contains npages contiguous free pages, so continue on the next level to find that run.

				i += j
				lastSumIdx = i
				lastSum = sum
				continue nextLevel
			}

We either don't have a current run started, or this entry isn't totally free (meaning we can't continue the current one), so try to begin a new run by setting size and base based on sum.end.

				size = sum.end()
				base = uint(j+1)<<logMaxPages - size
				continue

The entry is completely free, so continue the run.

			size += 1 << logMaxPages
		}

We found a sufficiently large run of free pages straddling some boundary, so compute the address and return it.

			addr := levelIndexToOffAddr(l, i).add(uintptr(base) * pageSize).addr()
			return addr, p.findMappedAddr(firstFree.base)
		}

We're at level zero, so that means we've exhausted our search.

			return 0, maxSearchAddr
		}

We're not at level zero, and we exhausted the level we were looking in. This means that either our calculations were wrong or the level above lied to us. In either case, dump some useful state and throw.

		print("runtime: summary[", l-1, "][", lastSumIdx, "] = ", lastSum.start(), ", ", lastSum.max(), ", ", lastSum.end(), "\n")
		print("runtime: level = ", l, ", npages = ", npages, ", j0 = ", j0, "\n")
		print("runtime: p.searchAddr = ", hex(p.searchAddr.addr()), ", i = ", i, "\n")
		print("runtime: levelShift[level] = ", levelShift[l], ", levelBits[level] = ", levelBits[l], "\n")
		for j := 0; j < len(entries); j++ {
			sum := entries[j]
			print("runtime: summary[", l, "][", i+j, "] = (", sum.start(), ", ", sum.max(), ", ", sum.end(), ")\n")
		}
		throw("bad summary data")
	}

Since we've gotten to this point, that means we haven't found a sufficiently-sized free region straddling some boundary (chunk or larger). This means the last summary we inspected must have had a large enough "max" value, so look inside the chunk to find a suitable run. After iterating over all levels, i must contain a chunk index which is what the final level represents.

	ci := chunkIdx(i)
	j, searchIdx := p.chunkOf(ci).find(npages, 0)

We couldn't find any space in this chunk despite the summaries telling us it should be there. There's likely a bug, so dump some state and throw.

		sum := p.summary[len(p.summary)-1][i]
		print("runtime: summary[", len(p.summary)-1, "][", i, "] = (", sum.start(), ", ", sum.max(), ", ", sum.end(), ")\n")
		print("runtime: npages = ", npages, "\n")
		throw("bad summary data")
	}

Compute the address at which the free space starts.

	addr := chunkBase(ci) + uintptr(j)*pageSize

Since we actually searched the chunk, we may have found an even narrower free window.

	searchAddr := chunkBase(ci) + uintptr(searchIdx)*pageSize
	foundFree(offAddr{searchAddr}, chunkBase(ci+1)-searchAddr)
	return addr, p.findMappedAddr(firstFree.base)
}

alloc allocates npages worth of memory from the page heap, returning the base address for the allocation and the amount of scavenged memory in bytes contained in the region [base address, base address + npages*pageSize). Returns a 0 base address on failure, in which case other returned values should be ignored. p.mheapLock must be held. Must run on the system stack because p.mheapLock must be held.go:systemstack

func (p *pageAlloc) alloc(npages uintptr) (addr uintptr, scav uintptr) {
	assertLockHeld(p.mheapLock)

If the searchAddr refers to a region which has a higher address than any known chunk, then we know we're out of memory.

	if chunkIndex(p.searchAddr.addr()) >= p.end {
		return 0, 0
	}

If npages has a chance of fitting in the chunk where the searchAddr is, search it directly.

	searchAddr := minOffAddr

npages is guaranteed to be no greater than pallocChunkPages here.

		i := chunkIndex(p.searchAddr.addr())
		if max := p.summary[len(p.summary)-1][i].max(); max >= uint(npages) {
			j, searchIdx := p.chunkOf(i).find(npages, chunkPageIndex(p.searchAddr.addr()))
			if j == ^uint(0) {
				print("runtime: max = ", max, ", npages = ", npages, "\n")
				print("runtime: searchIdx = ", chunkPageIndex(p.searchAddr.addr()), ", p.searchAddr = ", hex(p.searchAddr.addr()), "\n")
				throw("bad summary data")
			}
			addr = chunkBase(i) + uintptr(j)*pageSize
			searchAddr = offAddr{chunkBase(i) + uintptr(searchIdx)*pageSize}
			goto Found
		}

We failed to use a searchAddr for one reason or another, so try the slow path.

	addr, searchAddr = p.find(npages)
	if addr == 0 {

We failed to find a single free page, the smallest unit of allocation. This means we know the heap is completely exhausted. Otherwise, the heap still might have free space in it, just not enough contiguous space to accommodate npages.

			p.searchAddr = maxSearchAddr
		}
		return 0, 0
	}

Go ahead and actually mark the bits now that we have an address.

	scav = p.allocRange(addr, npages)

If we found a higher searchAddr, we know that all the heap memory before that searchAddr in an offset address space is allocated, so bump p.searchAddr up to the new one.

	if p.searchAddr.lessThan(searchAddr) {
		p.searchAddr = searchAddr
	}
	return addr, scav
}

free returns npages worth of memory starting at base back to the page heap. p.mheapLock must be held. Must run on the system stack because p.mheapLock must be held.go:systemstack

func (p *pageAlloc) free(base, npages uintptr) {
	assertLockHeld(p.mheapLock)

If we're freeing pages below the p.searchAddr, update searchAddr.

	if b := (offAddr{base}); b.lessThan(p.searchAddr) {
		p.searchAddr = b

Update the free high watermark for the scavenger.

	limit := base + npages*pageSize - 1
	if offLimit := (offAddr{limit}); p.scav.freeHWM.lessThan(offLimit) {
		p.scav.freeHWM = offLimit
	}

Fast path: we're clearing a single bit, and we know exactly where it is, so mark it directly.

		i := chunkIndex(base)
		p.chunkOf(i).free1(chunkPageIndex(base))

Slow path: we're clearing more bits so we may need to iterate.

		sc, ec := chunkIndex(base), chunkIndex(limit)
		si, ei := chunkPageIndex(base), chunkPageIndex(limit)

The range doesn't cross any chunk boundaries.

			p.chunkOf(sc).free(si, ei+1-si)

The range crosses at least one chunk boundary.

			p.chunkOf(sc).free(si, pallocChunkPages-si)
			for c := sc + 1; c < ec; c++ {
				p.chunkOf(c).freeAll()
			}
			p.chunkOf(ec).free(0, ei+1)
		}
	}
	p.update(base, npages, true, false)
}

const (
	pallocSumBytes = unsafe.Sizeof(pallocSum(0))

maxPackedValue is the maximum value that any of the three fields in the pallocSum may take on.

	maxPackedValue    = 1 << logMaxPackedValue
	logMaxPackedValue = logPallocChunkPages + (summaryLevels-1)*summaryLevelBits

	freeChunkSum = pallocSum(uint64(pallocChunkPages) |
		uint64(pallocChunkPages<<logMaxPackedValue) |
		uint64(pallocChunkPages<<(2*logMaxPackedValue)))
)

pallocSum is a packed summary type which packs three numbers: start, max, and end into a single 8-byte value. Each of these values are a summary of a bitmap and are thus counts, each of which may have a maximum value of 2^21 - 1, or all three may be equal to 2^21. The latter case is represented by just setting the 64th bit.

type pallocSum uint64

packPallocSum takes a start, max, and end value and produces a pallocSum.

func packPallocSum(start, max, end uint) pallocSum {
	if max == maxPackedValue {
		return pallocSum(uint64(1 << 63))
	}
	return pallocSum((uint64(start) & (maxPackedValue - 1)) |
		((uint64(max) & (maxPackedValue - 1)) << logMaxPackedValue) |
		((uint64(end) & (maxPackedValue - 1)) << (2 * logMaxPackedValue)))
}

start extracts the start value from a packed sum.

func (p pallocSum) start() uint {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue
	}
	return uint(uint64(p) & (maxPackedValue - 1))
}

max extracts the max value from a packed sum.

func (p pallocSum) max() uint {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue
	}
	return uint((uint64(p) >> logMaxPackedValue) & (maxPackedValue - 1))
}

end extracts the end value from a packed sum.

func (p pallocSum) end() uint {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue
	}
	return uint((uint64(p) >> (2 * logMaxPackedValue)) & (maxPackedValue - 1))
}

unpack unpacks all three values from the summary.

func (p pallocSum) unpack() (uint, uint, uint) {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue, maxPackedValue, maxPackedValue
	}
	return uint(uint64(p) & (maxPackedValue - 1)),
		uint((uint64(p) >> logMaxPackedValue) & (maxPackedValue - 1)),
		uint((uint64(p) >> (2 * logMaxPackedValue)) & (maxPackedValue - 1))
}

mergeSummaries merges consecutive summaries which may each represent at most 1 << logMaxPagesPerSum pages each together into one.

Merge the summaries in sums into one. We do this by keeping a running summary representing the merged summaries of sums[:i] in start, max, and end.

	start, max, end := sums[0].unpack()

Merge in sums[i].

		si, mi, ei := sums[i].unpack()

Merge in sums[i].start only if the running summary is completely free, otherwise this summary's start plays no role in the combined sum.

		if start == uint(i)<<logMaxPagesPerSum {
			start += si
		}

Recompute the max value of the running sum by looking across the boundary between the running sum and sums[i] and at the max sums[i], taking the greatest of those two and the max of the running sum.

		if end+si > max {
			max = end + si
		}
		if mi > max {
			max = mi
		}

Merge in end by checking if this new summary is totally free. If it is, then we want to extend the running sum's end by the new summary. If not, then we have some alloc'd pages in there and we just want to take the end value in sums[i].

		if ei == 1<<logMaxPagesPerSum {
			end += 1 << logMaxPagesPerSum
		} else {
			end = ei
		}
	}
	return packPallocSum(start, max, end)