diff options
Diffstat (limited to 'src/runtime/mpagealloc.go')
| -rw-r--r-- | src/runtime/mpagealloc.go | 1007 |
1 files changed, 1007 insertions, 0 deletions
diff --git a/src/runtime/mpagealloc.go b/src/runtime/mpagealloc.go new file mode 100644 index 0000000..dac1f39 --- /dev/null +++ b/src/runtime/mpagealloc.go @@ -0,0 +1,1007 @@ +// 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 ( + "runtime/internal/atomic" + "unsafe" +) + +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 + 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)) +} + +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 *sysMemStat + + // Whether or not this struct is being used in tests. + test bool +} + +func (p *pageAlloc) init(mheapLock *mutex, sysStat *sysMemStat) { + 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") + } + 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++ { + if p.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(*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. + 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 := p.summary[len(p.summary)-1][sc] + y := p.chunkOf(sc).summarize() + if x == y { + return + } + p.summary[len(p.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 := 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] + 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] = p.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 := 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 + for l := len(p.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 := 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) + if sc == ec { + // 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) + } else { + // 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} + } 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 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) { + 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 + +nextLevel: + for l := 0; l < len(p.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 := 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] + if sum == 0 { + // 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+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 + break + } + 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 + continue + } + // 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, p.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: 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) + 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 := 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 + if pallocChunkPages-chunkPageIndex(p.searchAddr.addr()) >= uint(npages) { + // 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 { + 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. + p.searchAddr = maxSearchAddr + } + return 0, 0 + } +Found: + // 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 + } + 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) + p.chunkOf(i).free1(chunkPageIndex(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. + p.chunkOf(sc).free(si, ei+1-si) + } else { + // 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. +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) +} |