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