mpagealloc_64bit.go

Documentation: runtime

     1  // Copyright 2019 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  //go:build amd64 || arm64 || loong64 || mips64 || mips64le || ppc64 || ppc64le || riscv64 || s390x
     6  
     7  package runtime
     8  
     9  import (
    10  	"runtime/internal/atomic"
    11  	"unsafe"
    12  )
    13  
    14  const (
    15  	// The number of levels in the radix tree.
    16  	summaryLevels = 5
    17  
    18  	// Constants for testing.
    19  	pageAlloc32Bit = 0
    20  	pageAlloc64Bit = 1
    21  
    22  	// Number of bits needed to represent all indices into the L1 of the
    23  	// chunks map.
    24  	//
    25  	// See (*pageAlloc).chunks for more details. Update the documentation
    26  	// there should this number change.
    27  	pallocChunksL1Bits = 13
    28  )
    29  
    30  // levelBits is the number of bits in the radix for a given level in the super summary
    31  // structure.
    32  //
    33  // The sum of all the entries of levelBits should equal heapAddrBits.
    34  var levelBits = [summaryLevels]uint{
    35  	summaryL0Bits,
    36  	summaryLevelBits,
    37  	summaryLevelBits,
    38  	summaryLevelBits,
    39  	summaryLevelBits,
    40  }
    41  
    42  // levelShift is the number of bits to shift to acquire the radix for a given level
    43  // in the super summary structure.
    44  //
    45  // With levelShift, one can compute the index of the summary at level l related to a
    46  // pointer p by doing:
    47  //
    48  //	p >> levelShift[l]
    49  var levelShift = [summaryLevels]uint{
    50  	heapAddrBits - summaryL0Bits,
    51  	heapAddrBits - summaryL0Bits - 1*summaryLevelBits,
    52  	heapAddrBits - summaryL0Bits - 2*summaryLevelBits,
    53  	heapAddrBits - summaryL0Bits - 3*summaryLevelBits,
    54  	heapAddrBits - summaryL0Bits - 4*summaryLevelBits,
    55  }
    56  
    57  // levelLogPages is log2 the maximum number of runtime pages in the address space
    58  // a summary in the given level represents.
    59  //
    60  // The leaf level always represents exactly log2 of 1 chunk's worth of pages.
    61  var levelLogPages = [summaryLevels]uint{
    62  	logPallocChunkPages + 4*summaryLevelBits,
    63  	logPallocChunkPages + 3*summaryLevelBits,
    64  	logPallocChunkPages + 2*summaryLevelBits,
    65  	logPallocChunkPages + 1*summaryLevelBits,
    66  	logPallocChunkPages,
    67  }
    68  
    69  // sysInit performs architecture-dependent initialization of fields
    70  // in pageAlloc. pageAlloc should be uninitialized except for sysStat
    71  // if any runtime statistic should be updated.
    72  func (p *pageAlloc) sysInit() {
    73  	// Reserve memory for each level. This will get mapped in
    74  	// as R/W by setArenas.
    75  	for l, shift := range levelShift {
    76  		entries := 1 << (heapAddrBits - shift)
    77  
    78  		// Reserve b bytes of memory anywhere in the address space.
    79  		b := alignUp(uintptr(entries)*pallocSumBytes, physPageSize)
    80  		r := sysReserve(nil, b)
    81  		if r == nil {
    82  			throw("failed to reserve page summary memory")
    83  		}
    84  
    85  		// Put this reservation into a slice.
    86  		sl := notInHeapSlice{(*notInHeap)(r), 0, entries}
    87  		p.summary[l] = *(*[]pallocSum)(unsafe.Pointer(&sl))
    88  	}
    89  
    90  	// Set up the scavenge index.
    91  	nbytes := uintptr(1<<heapAddrBits) / pallocChunkBytes / 8
    92  	r := sysReserve(nil, nbytes)
    93  	sl := notInHeapSlice{(*notInHeap)(r), int(nbytes), int(nbytes)}
    94  	p.scav.index.chunks = *(*[]atomic.Uint8)(unsafe.Pointer(&sl))
    95  }
    96  
    97  // sysGrow performs architecture-dependent operations on heap
    98  // growth for the page allocator, such as mapping in new memory
    99  // for summaries. It also updates the length of the slices in
   100  // [.summary.
   101  //
   102  // base is the base of the newly-added heap memory and limit is
   103  // the first address past the end of the newly-added heap memory.
   104  // Both must be aligned to pallocChunkBytes.
   105  //
   106  // The caller must update p.start and p.end after calling sysGrow.
   107  func (p *pageAlloc) sysGrow(base, limit uintptr) {
   108  	if base%pallocChunkBytes != 0 || limit%pallocChunkBytes != 0 {
   109  		print("runtime: base = ", hex(base), ", limit = ", hex(limit), "\n")
   110  		throw("sysGrow bounds not aligned to pallocChunkBytes")
   111  	}
   112  
   113  	// addrRangeToSummaryRange converts a range of addresses into a range
   114  	// of summary indices which must be mapped to support those addresses
   115  	// in the summary range.
   116  	addrRangeToSummaryRange := func(level int, r addrRange) (int, int) {
   117  		sumIdxBase, sumIdxLimit := addrsToSummaryRange(level, r.base.addr(), r.limit.addr())
   118  		return blockAlignSummaryRange(level, sumIdxBase, sumIdxLimit)
   119  	}
   120  
   121  	// summaryRangeToSumAddrRange converts a range of indices in any
   122  	// level of p.summary into page-aligned addresses which cover that
   123  	// range of indices.
   124  	summaryRangeToSumAddrRange := func(level, sumIdxBase, sumIdxLimit int) addrRange {
   125  		baseOffset := alignDown(uintptr(sumIdxBase)*pallocSumBytes, physPageSize)
   126  		limitOffset := alignUp(uintptr(sumIdxLimit)*pallocSumBytes, physPageSize)
   127  		base := unsafe.Pointer(&p.summary[level][0])
   128  		return addrRange{
   129  			offAddr{uintptr(add(base, baseOffset))},
   130  			offAddr{uintptr(add(base, limitOffset))},
   131  		}
   132  	}
   133  
   134  	// addrRangeToSumAddrRange is a convienience function that converts
   135  	// an address range r to the address range of the given summary level
   136  	// that stores the summaries for r.
   137  	addrRangeToSumAddrRange := func(level int, r addrRange) addrRange {
   138  		sumIdxBase, sumIdxLimit := addrRangeToSummaryRange(level, r)
   139  		return summaryRangeToSumAddrRange(level, sumIdxBase, sumIdxLimit)
   140  	}
   141  
   142  	// Find the first inUse index which is strictly greater than base.
   143  	//
   144  	// Because this function will never be asked remap the same memory
   145  	// twice, this index is effectively the index at which we would insert
   146  	// this new growth, and base will never overlap/be contained within
   147  	// any existing range.
   148  	//
   149  	// This will be used to look at what memory in the summary array is already
   150  	// mapped before and after this new range.
   151  	inUseIndex := p.inUse.findSucc(base)
   152  
   153  	// Walk up the radix tree and map summaries in as needed.
   154  	for l := range p.summary {
   155  		// Figure out what part of the summary array this new address space needs.
   156  		needIdxBase, needIdxLimit := addrRangeToSummaryRange(l, makeAddrRange(base, limit))
   157  
   158  		// Update the summary slices with a new upper-bound. This ensures
   159  		// we get tight bounds checks on at least the top bound.
   160  		//
   161  		// We must do this regardless of whether we map new memory.
   162  		if needIdxLimit > len(p.summary[l]) {
   163  			p.summary[l] = p.summary[l][:needIdxLimit]
   164  		}
   165  
   166  		// Compute the needed address range in the summary array for level l.
   167  		need := summaryRangeToSumAddrRange(l, needIdxBase, needIdxLimit)
   168  
   169  		// Prune need down to what needs to be newly mapped. Some parts of it may
   170  		// already be mapped by what inUse describes due to page alignment requirements
   171  		// for mapping. prune's invariants are guaranteed by the fact that this
   172  		// function will never be asked to remap the same memory twice.
   173  		if inUseIndex > 0 {
   174  			need = need.subtract(addrRangeToSumAddrRange(l, p.inUse.ranges[inUseIndex-1]))
   175  		}
   176  		if inUseIndex < len(p.inUse.ranges) {
   177  			need = need.subtract(addrRangeToSumAddrRange(l, p.inUse.ranges[inUseIndex]))
   178  		}
   179  		// It's possible that after our pruning above, there's nothing new to map.
   180  		if need.size() == 0 {
   181  			continue
   182  		}
   183  
   184  		// Map and commit need.
   185  		sysMap(unsafe.Pointer(need.base.addr()), need.size(), p.sysStat)
   186  		sysUsed(unsafe.Pointer(need.base.addr()), need.size(), need.size())
   187  		p.summaryMappedReady += need.size()
   188  	}
   189  
   190  	// Update the scavenge index.
   191  	p.summaryMappedReady += p.scav.index.grow(base, limit, p.sysStat)
   192  }
   193  
   194  // grow increases the index's backing store in response to a heap growth.
   195  //
   196  // Returns the amount of memory added to sysStat.
   197  func (s *scavengeIndex) grow(base, limit uintptr, sysStat *sysMemStat) uintptr {
   198  	if base%pallocChunkBytes != 0 || limit%pallocChunkBytes != 0 {
   199  		print("runtime: base = ", hex(base), ", limit = ", hex(limit), "\n")
   200  		throw("sysGrow bounds not aligned to pallocChunkBytes")
   201  	}
   202  	// Map and commit the pieces of chunks that we need.
   203  	//
   204  	// We always map the full range of the minimum heap address to the
   205  	// maximum heap address. We don't do this for the summary structure
   206  	// because it's quite large and a discontiguous heap could cause a
   207  	// lot of memory to be used. In this situation, the worst case overhead
   208  	// is in the single-digit MiB if we map the whole thing.
   209  	//
   210  	// The base address of the backing store is always page-aligned,
   211  	// because it comes from the OS, so it's sufficient to align the
   212  	// index.
   213  	haveMin := s.min.Load()
   214  	haveMax := s.max.Load()
   215  	needMin := int32(alignDown(uintptr(chunkIndex(base)/8), physPageSize))
   216  	needMax := int32(alignUp(uintptr((chunkIndex(limit)+7)/8), physPageSize))
   217  	// Extend the range down to what we have, if there's no overlap.
   218  	if needMax < haveMin {
   219  		needMax = haveMin
   220  	}
   221  	if needMin > haveMax {
   222  		needMin = haveMax
   223  	}
   224  	have := makeAddrRange(
   225  		// Avoid a panic from indexing one past the last element.
   226  		uintptr(unsafe.Pointer(&s.chunks[0]))+uintptr(haveMin),
   227  		uintptr(unsafe.Pointer(&s.chunks[0]))+uintptr(haveMax),
   228  	)
   229  	need := makeAddrRange(
   230  		// Avoid a panic from indexing one past the last element.
   231  		uintptr(unsafe.Pointer(&s.chunks[0]))+uintptr(needMin),
   232  		uintptr(unsafe.Pointer(&s.chunks[0]))+uintptr(needMax),
   233  	)
   234  	// Subtract any overlap from rounding. We can't re-map memory because
   235  	// it'll be zeroed.
   236  	need = need.subtract(have)
   237  
   238  	// If we've got something to map, map it, and update the slice bounds.
   239  	if need.size() != 0 {
   240  		sysMap(unsafe.Pointer(need.base.addr()), need.size(), sysStat)
   241  		sysUsed(unsafe.Pointer(need.base.addr()), need.size(), need.size())
   242  		// Update the indices only after the new memory is valid.
   243  		if haveMin == 0 || needMin < haveMin {
   244  			s.min.Store(needMin)
   245  		}
   246  		if haveMax == 0 || needMax > haveMax {
   247  			s.max.Store(needMax)
   248  		}
   249  	}
   250  	// Update minHeapIdx. Note that even if there's no mapping work to do,
   251  	// we may still have a new, lower minimum heap address.
   252  	minHeapIdx := s.minHeapIdx.Load()
   253  	if baseIdx := int32(chunkIndex(base) / 8); minHeapIdx == 0 || baseIdx < minHeapIdx {
   254  		s.minHeapIdx.Store(baseIdx)
   255  	}
   256  	return need.size()
   257  }
   258
View as plain text