blob: 8b3c62c375e76f2efbd1f08a566af86b86954eaf [file] [log] [blame]
// Copyright 2019 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 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 (
const (
// 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 {
if pallocChunksL1Bits == 0 {
// 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.
func addrsToSummaryRange(level int, base, limit uintptr) (lo int, hi int) {
// 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
// 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))
type pageAlloc struct {
// 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.
scav struct {
// 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 *uint64
// Whether or not this struct is being used in tests.
test bool
func (s *pageAlloc) init(mheapLock *mutex, sysStat *uint64) {
if levelLogPages[0] > logMaxPackedValue {
// 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")
s.sysStat = sysStat
// Initialize s.inUse.
// System-dependent initialization.
// Start with the searchAddr in a state indicating there's no free memory.
s.searchAddr = maxSearchAddr
// Set the mheapLock.
s.mheapLock = mheapLock
// Initialize scavenge tracking state.
s.scav.scavLWM = maxSearchAddr
// chunkOf returns the chunk at the given chunk index.
func (s *pageAlloc) chunkOf(ci chunkIdx) *pallocData {
return &s.chunks[ci.l1()][ci.l2()]
// grow sets up the metadata for the address range [base, base+size).
// It may allocate metadata, in which case *s.sysStat will be updated.
// s.mheapLock must be held.
func (s *pageAlloc) grow(base, size uintptr) {
// 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.
s.sysGrow(base, limit)
// Update s.start and s.end.
// If no growth happened yet, start == 0. This is generally
// safe since the zero page is unmapped.
firstGrowth := s.start == 0
start, end := chunkIndex(base), chunkIndex(limit)
if firstGrowth || start < s.start {
s.start = start
if end > s.end {
s.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.
s.inUse.add(makeAddrRange(base, limit))
// A grow operation is a lot like a free operation, so if our
// chunk ends up below s.searchAddr, update s.searchAddr to the
// new address, just like in free.
if b := (offAddr{base}); b.lessThan(s.searchAddr) {
s.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++ {
if s.chunks[c.l1()] == nil {
// Create the necessary l2 entry.
// Store it atomically to avoid races with readers which
// don't acquire the heap lock.
r := sysAlloc(unsafe.Sizeof(*s.chunks[0]), s.sysStat)
atomic.StorepNoWB(unsafe.Pointer(&s.chunks[c.l1()]), r)
s.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.
s.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.
// s.mheapLock must be held.
func (s *pageAlloc) update(base, npages uintptr, contig, alloc bool) {
// base, limit, start, and end are inclusive.
limit := base + npages*pageSize - 1
sc, ec := chunkIndex(base), chunkIndex(limit)
// Handle updating the lowest level first.
if sc == ec {
// Fast path: the allocation doesn't span more than one chunk,
// so update this one and if the summary didn't change, return.
x := s.summary[len(s.summary)-1][sc]
y := s.chunkOf(sc).summarize()
if x == y {
s.summary[len(s.summary)-1][sc] = y
} else if contig {
// Slow contiguous path: the allocation spans more than one chunk
// and at least one summary is guaranteed to change.
summary := s.summary[len(s.summary)-1]
// Update the summary for chunk sc.
summary[sc] = s.chunkOf(sc).summarize()
// Update the summaries for chunks in between, which are
// either totally allocated or freed.
whole := s.summary[len(s.summary)-1][sc+1 : ec]
if alloc {
// 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] = s.chunkOf(ec).summarize()
} else {
// 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 := s.summary[len(s.summary)-1]
for c := sc; c <= ec; c++ {
summary[c] = s.chunkOf(c).summarize()
// Walk up the radix tree and update the summaries appropriately.
changed := true
for l := len(s.summary) - 2; l >= 0 && changed; l-- {
// 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 := s.summary[l+1][i<<logEntriesPerBlock : (i+1)<<logEntriesPerBlock]
sum := mergeSummaries(children, logMaxPages)
old := s.summary[l][i]
if old != sum {
changed = true
s.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.
// s.mheapLock must be held.
func (s *pageAlloc) allocRange(base, npages uintptr) uintptr {
limit := base + npages*pageSize - 1
sc, ec := chunkIndex(base), chunkIndex(limit)
si, ei := chunkPageIndex(base), chunkPageIndex(limit)
scav := uint(0)
if sc == ec {
// The range doesn't cross any chunk boundaries.
chunk := s.chunkOf(sc)
scav += chunk.scavenged.popcntRange(si, ei+1-si)
chunk.allocRange(si, ei+1-si)
} else {
// The range crosses at least one chunk boundary.
chunk := s.chunkOf(sc)
scav += chunk.scavenged.popcntRange(si, pallocChunkPages-si)
chunk.allocRange(si, pallocChunkPages-si)
for c := sc + 1; c < ec; c++ {
chunk := s.chunkOf(c)
scav += chunk.scavenged.popcntRange(0, pallocChunkPages)
chunk = s.chunkOf(ec)
scav += chunk.scavenged.popcntRange(0, ei+1)
chunk.allocRange(0, ei+1)
s.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.
// s.mheapLock must be held.
func (s *pageAlloc) findMappedAddr(addr offAddr) offAddr {
// 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 s.test || mheap_.arenas[ai.l1()] == nil || mheap_.arenas[ai.l1()][ai.l2()] == nil {
vAddr, ok := s.inUse.findAddrGreaterEqual(addr.addr())
if ok {
return offAddr{vAddr}
} else {
// 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 s.searchAddr to prune its search and assumes that no palloc chunks
// below chunkIndex(s.searchAddr) contain any free memory at all.
// find also computes and returns a candidate s.searchAddr, which may or
// may not prune more of the address space than s.searchAddr already does.
// This candidate is always a valid s.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.
// s.mheapLock must be held.
func (s *pageAlloc) find(npages uintptr) (uintptr, offAddr) {
// 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) {
if firstFree.base.lessEqual(addr) && addr.add(size-1).lessEqual(firstFree.bound) {
// 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)
} else if !(addr.add(size-1).lessThan(firstFree.base) || firstFree.bound.lessThan(addr)) {
// 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
for l := 0; l < len(s.summary); l++ {
// 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 := s.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, s.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]
if sum == 0 {
// A full entry means we broke any streak and
// that we should skip it altogether.
size = 0
// 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+s >= uint(npages) {
// 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
if sum.max() >= uint(npages) {
// 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
if size == 0 || s < 1<<logMaxPages {
// 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
// The entry is completely free, so continue the run.
size += 1 << logMaxPages
if size >= uint(npages) {
// 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, s.findMappedAddr(firstFree.base)
if l == 0 {
// 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: s.searchAddr = ", hex(s.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 := s.chunkOf(ci).find(npages, 0)
if j == ^uint(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 := s.summary[len(s.summary)-1][i]
print("runtime: summary[", len(s.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, s.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.
// s.mheapLock must be held.
func (s *pageAlloc) alloc(npages uintptr) (addr uintptr, scav uintptr) {
// 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(s.searchAddr.addr()) >= s.end {
return 0, 0
// If npages has a chance of fitting in the chunk where the searchAddr is,
// search it directly.
searchAddr := minOffAddr
if pallocChunkPages-chunkPageIndex(s.searchAddr.addr()) >= uint(npages) {
// npages is guaranteed to be no greater than pallocChunkPages here.
i := chunkIndex(s.searchAddr.addr())
if max := s.summary[len(s.summary)-1][i].max(); max >= uint(npages) {
j, searchIdx := s.chunkOf(i).find(npages, chunkPageIndex(s.searchAddr.addr()))
if j == ^uint(0) {
print("runtime: max = ", max, ", npages = ", npages, "\n")
print("runtime: searchIdx = ", chunkPageIndex(s.searchAddr.addr()), ", s.searchAddr = ", hex(s.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 = s.find(npages)
if addr == 0 {
if npages == 1 {
// 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.
s.searchAddr = maxSearchAddr
return 0, 0
// Go ahead and actually mark the bits now that we have an address.
scav = s.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 s.searchAddr up to the new one.
if s.searchAddr.lessThan(searchAddr) {
s.searchAddr = searchAddr
return addr, scav
// free returns npages worth of memory starting at base back to the page heap.
// s.mheapLock must be held.
func (s *pageAlloc) free(base, npages uintptr) {
// If we're freeing pages below the s.searchAddr, update searchAddr.
if b := (offAddr{base}); b.lessThan(s.searchAddr) {
s.searchAddr = b
// Update the free high watermark for the scavenger.
limit := base + npages*pageSize - 1
if offLimit := (offAddr{limit}); s.scav.freeHWM.lessThan(offLimit) {
s.scav.freeHWM = offLimit
if npages == 1 {
// Fast path: we're clearing a single bit, and we know exactly
// where it is, so mark it directly.
i := chunkIndex(base)
} else {
// 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)
if sc == ec {
// The range doesn't cross any chunk boundaries.
s.chunkOf(sc).free(si, ei+1-si)
} else {
// The range crosses at least one chunk boundary.
s.chunkOf(sc).free(si, pallocChunkPages-si)
for c := sc + 1; c < ec; c++ {
s.chunkOf(ec).free(0, ei+1)
s.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) |
// 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.
func mergeSummaries(sums []pallocSum, logMaxPagesPerSum uint) pallocSum {
// 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()
for i := 1; i < len(sums); i++ {
// 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)