Source file
src/runtime/mpallocbits.go
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 package runtime
6
7 import (
8 "internal/runtime/sys"
9 )
10
11 // pageBits is a bitmap representing one bit per page in a palloc chunk.
12 type pageBits [pallocChunkPages / 64]uint64
13
14 // get returns the value of the i'th bit in the bitmap.
15 func (b *pageBits) get(i uint) uint {
16 return uint((b[i/64] >> (i % 64)) & 1)
17 }
18
19 // block64 returns the 64-bit aligned block of bits containing the i'th bit.
20 func (b *pageBits) block64(i uint) uint64 {
21 return b[i/64]
22 }
23
24 // set sets bit i of pageBits.
25 func (b *pageBits) set(i uint) {
26 b[i/64] |= 1 << (i % 64)
27 }
28
29 // setRange sets bits in the range [i, i+n).
30 func (b *pageBits) setRange(i, n uint) {
31 _ = b[i/64]
32 if n == 1 {
33 // Fast path for the n == 1 case.
34 b.set(i)
35 return
36 }
37 // Set bits [i, j].
38 j := i + n - 1
39 if i/64 == j/64 {
40 b[i/64] |= ((uint64(1) << n) - 1) << (i % 64)
41 return
42 }
43 _ = b[j/64]
44 // Set leading bits.
45 b[i/64] |= ^uint64(0) << (i % 64)
46 for k := i/64 + 1; k < j/64; k++ {
47 b[k] = ^uint64(0)
48 }
49 // Set trailing bits.
50 b[j/64] |= (uint64(1) << (j%64 + 1)) - 1
51 }
52
53 // setAll sets all the bits of b.
54 func (b *pageBits) setAll() {
55 for i := range b {
56 b[i] = ^uint64(0)
57 }
58 }
59
60 // setBlock64 sets the 64-bit aligned block of bits containing the i'th bit that
61 // are set in v.
62 func (b *pageBits) setBlock64(i uint, v uint64) {
63 b[i/64] |= v
64 }
65
66 // clear clears bit i of pageBits.
67 func (b *pageBits) clear(i uint) {
68 b[i/64] &^= 1 << (i % 64)
69 }
70
71 // clearRange clears bits in the range [i, i+n).
72 func (b *pageBits) clearRange(i, n uint) {
73 _ = b[i/64]
74 if n == 1 {
75 // Fast path for the n == 1 case.
76 b.clear(i)
77 return
78 }
79 // Clear bits [i, j].
80 j := i + n - 1
81 if i/64 == j/64 {
82 b[i/64] &^= ((uint64(1) << n) - 1) << (i % 64)
83 return
84 }
85 _ = b[j/64]
86 // Clear leading bits.
87 b[i/64] &^= ^uint64(0) << (i % 64)
88 clear(b[i/64+1 : j/64])
89 // Clear trailing bits.
90 b[j/64] &^= (uint64(1) << (j%64 + 1)) - 1
91 }
92
93 // clearAll frees all the bits of b.
94 func (b *pageBits) clearAll() {
95 clear(b[:])
96 }
97
98 // clearBlock64 clears the 64-bit aligned block of bits containing the i'th bit that
99 // are set in v.
100 func (b *pageBits) clearBlock64(i uint, v uint64) {
101 b[i/64] &^= v
102 }
103
104 // popcntRange counts the number of set bits in the
105 // range [i, i+n).
106 func (b *pageBits) popcntRange(i, n uint) (s uint) {
107 if n == 1 {
108 return uint((b[i/64] >> (i % 64)) & 1)
109 }
110 _ = b[i/64]
111 j := i + n - 1
112 if i/64 == j/64 {
113 return uint(sys.OnesCount64((b[i/64] >> (i % 64)) & ((1 << n) - 1)))
114 }
115 _ = b[j/64]
116 s += uint(sys.OnesCount64(b[i/64] >> (i % 64)))
117 for k := i/64 + 1; k < j/64; k++ {
118 s += uint(sys.OnesCount64(b[k]))
119 }
120 s += uint(sys.OnesCount64(b[j/64] & ((1 << (j%64 + 1)) - 1)))
121 return
122 }
123
124 // pallocBits is a bitmap that tracks page allocations for at most one
125 // palloc chunk.
126 //
127 // The precise representation is an implementation detail, but for the
128 // sake of documentation, 0s are free pages and 1s are allocated pages.
129 type pallocBits pageBits
130
131 // summarize returns a packed summary of the bitmap in pallocBits.
132 func (b *pallocBits) summarize() pallocSum {
133 var start, most, cur uint
134 const notSetYet = ^uint(0) // sentinel for start value
135 start = notSetYet
136 for i := 0; i < len(b); i++ {
137 x := b[i]
138 if x == 0 {
139 cur += 64
140 continue
141 }
142 t := uint(sys.TrailingZeros64(x))
143 l := uint(sys.LeadingZeros64(x))
144
145 // Finish any region spanning the uint64s
146 cur += t
147 if start == notSetYet {
148 start = cur
149 }
150 most = max(most, cur)
151 // Final region that might span to next uint64
152 cur = l
153 }
154 if start == notSetYet {
155 // Made it all the way through without finding a single 1 bit.
156 const n = uint(64 * len(b))
157 return packPallocSum(n, n, n)
158 }
159 most = max(most, cur)
160
161 if most >= 64-2 {
162 // There is no way an internal run of zeros could beat max.
163 return packPallocSum(start, most, cur)
164 }
165 // Now look inside each uint64 for runs of zeros.
166 // All uint64s must be nonzero, or we would have aborted above.
167 outer:
168 for i := 0; i < len(b); i++ {
169 x := b[i]
170
171 // Look inside this uint64. We have a pattern like
172 // 000000 1xxxxx1 000000
173 // We need to look inside the 1xxxxx1 for any contiguous
174 // region of zeros.
175
176 // We already know the trailing zeros are no larger than max. Remove them.
177 x >>= sys.TrailingZeros64(x) & 63
178 if x&(x+1) == 0 { // no more zeros (except at the top).
179 continue
180 }
181
182 // Strategy: shrink all runs of zeros by max. If any runs of zero
183 // remain, then we've identified a larger maximum zero run.
184 p := most // number of zeros we still need to shrink by.
185 k := uint(1) // current minimum length of runs of ones in x.
186 for {
187 // Shrink all runs of zeros by p places (except the top zeros).
188 for p > 0 {
189 if p <= k {
190 // Shift p ones down into the top of each run of zeros.
191 x |= x >> (p & 63)
192 if x&(x+1) == 0 { // no more zeros (except at the top).
193 continue outer
194 }
195 break
196 }
197 // Shift k ones down into the top of each run of zeros.
198 x |= x >> (k & 63)
199 if x&(x+1) == 0 { // no more zeros (except at the top).
200 continue outer
201 }
202 p -= k
203 // We've just doubled the minimum length of 1-runs.
204 // This allows us to shift farther in the next iteration.
205 k *= 2
206 }
207
208 // The length of the lowest-order zero run is an increment to our maximum.
209 j := uint(sys.TrailingZeros64(^x)) // count contiguous trailing ones
210 x >>= j & 63 // remove trailing ones
211 j = uint(sys.TrailingZeros64(x)) // count contiguous trailing zeros
212 x >>= j & 63 // remove zeros
213 most += j // we have a new maximum!
214 if x&(x+1) == 0 { // no more zeros (except at the top).
215 continue outer
216 }
217 p = j // remove j more zeros from each zero run.
218 }
219 }
220 return packPallocSum(start, most, cur)
221 }
222
223 // find searches for npages contiguous free pages in pallocBits and returns
224 // the index where that run starts, as well as the index of the first free page
225 // it found in the search. searchIdx represents the first known free page and
226 // where to begin the next search from.
227 //
228 // If find fails to find any free space, it returns an index of ^uint(0) and
229 // the new searchIdx should be ignored.
230 //
231 // Note that if npages == 1, the two returned values will always be identical.
232 func (b *pallocBits) find(npages uintptr, searchIdx uint) (uint, uint) {
233 if npages == 1 {
234 addr := b.find1(searchIdx)
235 return addr, addr
236 } else if npages <= 64 {
237 return b.findSmallN(npages, searchIdx)
238 }
239 return b.findLargeN(npages, searchIdx)
240 }
241
242 // find1 is a helper for find which searches for a single free page
243 // in the pallocBits and returns the index.
244 //
245 // See find for an explanation of the searchIdx parameter.
246 func (b *pallocBits) find1(searchIdx uint) uint {
247 _ = b[0] // lift nil check out of loop
248 for i := searchIdx / 64; i < uint(len(b)); i++ {
249 x := b[i]
250 if ^x == 0 {
251 continue
252 }
253 return i*64 + uint(sys.TrailingZeros64(^x))
254 }
255 return ^uint(0)
256 }
257
258 // findSmallN is a helper for find which searches for npages contiguous free pages
259 // in this pallocBits and returns the index where that run of contiguous pages
260 // starts as well as the index of the first free page it finds in its search.
261 //
262 // See find for an explanation of the searchIdx parameter.
263 //
264 // Returns a ^uint(0) index on failure and the new searchIdx should be ignored.
265 //
266 // findSmallN assumes npages <= 64, where any such contiguous run of pages
267 // crosses at most one aligned 64-bit boundary in the bits.
268 func (b *pallocBits) findSmallN(npages uintptr, searchIdx uint) (uint, uint) {
269 end, newSearchIdx := uint(0), ^uint(0)
270 for i := searchIdx / 64; i < uint(len(b)); i++ {
271 bi := b[i]
272 if ^bi == 0 {
273 end = 0
274 continue
275 }
276 // First see if we can pack our allocation in the trailing
277 // zeros plus the end of the last 64 bits.
278 if newSearchIdx == ^uint(0) {
279 // The new searchIdx is going to be at these 64 bits after any
280 // 1s we file, so count trailing 1s.
281 newSearchIdx = i*64 + uint(sys.TrailingZeros64(^bi))
282 }
283 start := uint(sys.TrailingZeros64(bi))
284 if end+start >= uint(npages) {
285 return i*64 - end, newSearchIdx
286 }
287 // Next, check the interior of the 64-bit chunk.
288 j := findBitRange64(^bi, uint(npages))
289 if j < 64 {
290 return i*64 + j, newSearchIdx
291 }
292 end = uint(sys.LeadingZeros64(bi))
293 }
294 return ^uint(0), newSearchIdx
295 }
296
297 // findLargeN is a helper for find which searches for npages contiguous free pages
298 // in this pallocBits and returns the index where that run starts, as well as the
299 // index of the first free page it found it its search.
300 //
301 // See alloc for an explanation of the searchIdx parameter.
302 //
303 // Returns a ^uint(0) index on failure and the new searchIdx should be ignored.
304 //
305 // findLargeN assumes npages > 64, where any such run of free pages
306 // crosses at least one aligned 64-bit boundary in the bits.
307 func (b *pallocBits) findLargeN(npages uintptr, searchIdx uint) (uint, uint) {
308 start, size, newSearchIdx := ^uint(0), uint(0), ^uint(0)
309 for i := searchIdx / 64; i < uint(len(b)); i++ {
310 x := b[i]
311 if x == ^uint64(0) {
312 size = 0
313 continue
314 }
315 if newSearchIdx == ^uint(0) {
316 // The new searchIdx is going to be at these 64 bits after any
317 // 1s we file, so count trailing 1s.
318 newSearchIdx = i*64 + uint(sys.TrailingZeros64(^x))
319 }
320 if size == 0 {
321 size = uint(sys.LeadingZeros64(x))
322 start = i*64 + 64 - size
323 continue
324 }
325 s := uint(sys.TrailingZeros64(x))
326 if s+size >= uint(npages) {
327 return start, newSearchIdx
328 }
329 if s < 64 {
330 size = uint(sys.LeadingZeros64(x))
331 start = i*64 + 64 - size
332 continue
333 }
334 size += 64
335 }
336 if size < uint(npages) {
337 return ^uint(0), newSearchIdx
338 }
339 return start, newSearchIdx
340 }
341
342 // allocRange allocates the range [i, i+n).
343 func (b *pallocBits) allocRange(i, n uint) {
344 (*pageBits)(b).setRange(i, n)
345 }
346
347 // allocAll allocates all the bits of b.
348 func (b *pallocBits) allocAll() {
349 (*pageBits)(b).setAll()
350 }
351
352 // free1 frees a single page in the pallocBits at i.
353 func (b *pallocBits) free1(i uint) {
354 (*pageBits)(b).clear(i)
355 }
356
357 // free frees the range [i, i+n) of pages in the pallocBits.
358 func (b *pallocBits) free(i, n uint) {
359 (*pageBits)(b).clearRange(i, n)
360 }
361
362 // freeAll frees all the bits of b.
363 func (b *pallocBits) freeAll() {
364 (*pageBits)(b).clearAll()
365 }
366
367 // pages64 returns a 64-bit bitmap representing a block of 64 pages aligned
368 // to 64 pages. The returned block of pages is the one containing the i'th
369 // page in this pallocBits. Each bit represents whether the page is in-use.
370 func (b *pallocBits) pages64(i uint) uint64 {
371 return (*pageBits)(b).block64(i)
372 }
373
374 // allocPages64 allocates a 64-bit block of 64 pages aligned to 64 pages according
375 // to the bits set in alloc. The block set is the one containing the i'th page.
376 func (b *pallocBits) allocPages64(i uint, alloc uint64) {
377 (*pageBits)(b).setBlock64(i, alloc)
378 }
379
380 // findBitRange64 returns the bit index of the first set of
381 // n consecutive 1 bits. If no consecutive set of 1 bits of
382 // size n may be found in c, then it returns an integer >= 64.
383 // n must be > 0.
384 func findBitRange64(c uint64, n uint) uint {
385 // This implementation is based on shrinking the length of
386 // runs of contiguous 1 bits. We remove the top n-1 1 bits
387 // from each run of 1s, then look for the first remaining 1 bit.
388 p := n - 1 // number of 1s we want to remove.
389 k := uint(1) // current minimum width of runs of 0 in c.
390 for p > 0 {
391 if p <= k {
392 // Shift p 0s down into the top of each run of 1s.
393 c &= c >> (p & 63)
394 break
395 }
396 // Shift k 0s down into the top of each run of 1s.
397 c &= c >> (k & 63)
398 if c == 0 {
399 return 64
400 }
401 p -= k
402 // We've just doubled the minimum length of 0-runs.
403 // This allows us to shift farther in the next iteration.
404 k *= 2
405 }
406 // Find first remaining 1.
407 // Since we shrunk from the top down, the first 1 is in
408 // its correct original position.
409 return uint(sys.TrailingZeros64(c))
410 }
411
412 // pallocData encapsulates pallocBits and a bitmap for
413 // whether or not a given page is scavenged in a single
414 // structure. It's effectively a pallocBits with
415 // additional functionality.
416 //
417 // Update the comment on (*pageAlloc).chunks should this
418 // structure change.
419 type pallocData struct {
420 pallocBits
421 scavenged pageBits
422 }
423
424 // allocRange sets bits [i, i+n) in the bitmap to 1 and
425 // updates the scavenged bits appropriately.
426 func (m *pallocData) allocRange(i, n uint) {
427 // Clear the scavenged bits when we alloc the range.
428 m.pallocBits.allocRange(i, n)
429 m.scavenged.clearRange(i, n)
430 }
431
432 // allocAll sets every bit in the bitmap to 1 and updates
433 // the scavenged bits appropriately.
434 func (m *pallocData) allocAll() {
435 // Clear the scavenged bits when we alloc the range.
436 m.pallocBits.allocAll()
437 m.scavenged.clearAll()
438 }
439
View as plain text