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