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 arm64be alpha sparc64 ia64 6 7// See mpagealloc_32bit.go for why darwin/arm64 is excluded here. 8 9package runtime 10 11import "unsafe" 12 13const ( 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. 33var 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] 47var 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. 59var 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. 70func (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. 99func (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