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