Black Lives Matter. Support the Equal Justice Initiative.

Source file src/runtime/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  // +build amd64 !darwin,arm64 mips64 mips64le ppc64 ppc64le riscv64 s390x
     6  
     7  // See mpagealloc_32bit.go for why darwin/arm64 is excluded here.
     8  
     9  package runtime
    10  
    11  import "unsafe"
    12  
    13  const (
    14  	// The number of levels in the radix tree.
    15  	summaryLevels = 5
    16  
    17  	// Constants for testing.
    18  	pageAlloc32Bit = 0
    19  	pageAlloc64Bit = 1
    20  
    21  	// Number of bits needed to represent all indices into the L1 of the
    22  	// chunks map.
    23  	//
    24  	// See (*pageAlloc).chunks for more details. Update the documentation
    25  	// there should this number change.
    26  	pallocChunksL1Bits = 13
    27  )
    28  
    29  // levelBits is the number of bits in the radix for a given level in the super summary
    30  // structure.
    31  //
    32  // The sum of all the entries of levelBits should equal heapAddrBits.
    33  var levelBits = [summaryLevels]uint{
    34  	summaryL0Bits,
    35  	summaryLevelBits,
    36  	summaryLevelBits,
    37  	summaryLevelBits,
    38  	summaryLevelBits,
    39  }
    40  
    41  // levelShift is the number of bits to shift to acquire the radix for a given level
    42  // in the super summary structure.
    43  //
    44  // With levelShift, one can compute the index of the summary at level l related to a
    45  // pointer p by doing:
    46  //   p >> levelShift[l]
    47  var levelShift = [summaryLevels]uint{
    48  	heapAddrBits - summaryL0Bits,
    49  	heapAddrBits - summaryL0Bits - 1*summaryLevelBits,
    50  	heapAddrBits - summaryL0Bits - 2*summaryLevelBits,
    51  	heapAddrBits - summaryL0Bits - 3*summaryLevelBits,
    52  	heapAddrBits - summaryL0Bits - 4*summaryLevelBits,
    53  }
    54  
    55  // levelLogPages is log2 the maximum number of runtime pages in the address space
    56  // a summary in the given level represents.
    57  //
    58  // The leaf level always represents exactly log2 of 1 chunk's worth of pages.
    59  var levelLogPages = [summaryLevels]uint{
    60  	logPallocChunkPages + 4*summaryLevelBits,
    61  	logPallocChunkPages + 3*summaryLevelBits,
    62  	logPallocChunkPages + 2*summaryLevelBits,
    63  	logPallocChunkPages + 1*summaryLevelBits,
    64  	logPallocChunkPages,
    65  }
    66  
    67  // sysInit performs architecture-dependent initialization of fields
    68  // in pageAlloc. pageAlloc should be uninitialized except for sysStat
    69  // if any runtime statistic should be updated.
    70  func (s *pageAlloc) sysInit() {
    71  	// Reserve memory for each level. This will get mapped in
    72  	// as R/W by setArenas.
    73  	for l, shift := range levelShift {
    74  		entries := 1 << (heapAddrBits - shift)
    75  
    76  		// Reserve b bytes of memory anywhere in the address space.
    77  		b := alignUp(uintptr(entries)*pallocSumBytes, physPageSize)
    78  		r := sysReserve(nil, b)
    79  		if r == nil {
    80  			throw("failed to reserve page summary memory")
    81  		}
    82  
    83  		// Put this reservation into a slice.
    84  		sl := notInHeapSlice{(*notInHeap)(r), 0, entries}
    85  		s.summary[l] = *(*[]pallocSum)(unsafe.Pointer(&sl))
    86  	}
    87  }
    88  
    89  // sysGrow performs architecture-dependent operations on heap
    90  // growth for the page allocator, such as mapping in new memory
    91  // for summaries. It also updates the length of the slices in
    92  // s.summary.
    93  //
    94  // base is the base of the newly-added heap memory and limit is
    95  // the first address past the end of the newly-added heap memory.
    96  // Both must be aligned to pallocChunkBytes.
    97  //
    98  // The caller must update s.start and s.end after calling sysGrow.
    99  func (s *pageAlloc) sysGrow(base, limit uintptr) {
   100  	if base%pallocChunkBytes != 0 || limit%pallocChunkBytes != 0 {
   101  		print("runtime: base = ", hex(base), ", limit = ", hex(limit), "\n")
   102  		throw("sysGrow bounds not aligned to pallocChunkBytes")
   103  	}
   104  
   105  	// addrRangeToSummaryRange converts a range of addresses into a range
   106  	// of summary indices which must be mapped to support those addresses
   107  	// in the summary range.
   108  	addrRangeToSummaryRange := func(level int, r addrRange) (int, int) {
   109  		sumIdxBase, sumIdxLimit := addrsToSummaryRange(level, r.base, r.limit)
   110  		return blockAlignSummaryRange(level, sumIdxBase, sumIdxLimit)
   111  	}
   112  
   113  	// summaryRangeToSumAddrRange converts a range of indices in any
   114  	// level of s.summary into page-aligned addresses which cover that
   115  	// range of indices.
   116  	summaryRangeToSumAddrRange := func(level, sumIdxBase, sumIdxLimit int) addrRange {
   117  		baseOffset := alignDown(uintptr(sumIdxBase)*pallocSumBytes, physPageSize)
   118  		limitOffset := alignUp(uintptr(sumIdxLimit)*pallocSumBytes, physPageSize)
   119  		base := unsafe.Pointer(&s.summary[level][0])
   120  		return addrRange{
   121  			uintptr(add(base, baseOffset)),
   122  			uintptr(add(base, limitOffset)),
   123  		}
   124  	}
   125  
   126  	// addrRangeToSumAddrRange is a convienience function that converts
   127  	// an address range r to the address range of the given summary level
   128  	// that stores the summaries for r.
   129  	addrRangeToSumAddrRange := func(level int, r addrRange) addrRange {
   130  		sumIdxBase, sumIdxLimit := addrRangeToSummaryRange(level, r)
   131  		return summaryRangeToSumAddrRange(level, sumIdxBase, sumIdxLimit)
   132  	}
   133  
   134  	// Find the first inUse index which is strictly greater than base.
   135  	//
   136  	// Because this function will never be asked remap the same memory
   137  	// twice, this index is effectively the index at which we would insert
   138  	// this new growth, and base will never overlap/be contained within
   139  	// any existing range.
   140  	//
   141  	// This will be used to look at what memory in the summary array is already
   142  	// mapped before and after this new range.
   143  	inUseIndex := s.inUse.findSucc(base)
   144  
   145  	// Walk up the radix tree and map summaries in as needed.
   146  	for l := range s.summary {
   147  		// Figure out what part of the summary array this new address space needs.
   148  		needIdxBase, needIdxLimit := addrRangeToSummaryRange(l, addrRange{base, limit})
   149  
   150  		// Update the summary slices with a new upper-bound. This ensures
   151  		// we get tight bounds checks on at least the top bound.
   152  		//
   153  		// We must do this regardless of whether we map new memory.
   154  		if needIdxLimit > len(s.summary[l]) {
   155  			s.summary[l] = s.summary[l][:needIdxLimit]
   156  		}
   157  
   158  		// Compute the needed address range in the summary array for level l.
   159  		need := summaryRangeToSumAddrRange(l, needIdxBase, needIdxLimit)
   160  
   161  		// Prune need down to what needs to be newly mapped. Some parts of it may
   162  		// already be mapped by what inUse describes due to page alignment requirements
   163  		// for mapping. prune's invariants are guaranteed by the fact that this
   164  		// function will never be asked to remap the same memory twice.
   165  		if inUseIndex > 0 {
   166  			need = need.subtract(addrRangeToSumAddrRange(l, s.inUse.ranges[inUseIndex-1]))
   167  		}
   168  		if inUseIndex < len(s.inUse.ranges) {
   169  			need = need.subtract(addrRangeToSumAddrRange(l, s.inUse.ranges[inUseIndex]))
   170  		}
   171  		// It's possible that after our pruning above, there's nothing new to map.
   172  		if need.size() == 0 {
   173  			continue
   174  		}
   175  
   176  		// Map and commit need.
   177  		sysMap(unsafe.Pointer(need.base), need.size(), s.sysStat)
   178  		sysUsed(unsafe.Pointer(need.base), need.size())
   179  	}
   180  }
   181  

View as plain text