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 5package runtime 6 7import ( 8 "runtime/internal/sys" 9) 10 11// pageBits is a bitmap representing one bit per page in a palloc chunk. 12type pageBits [pallocChunkPages / 64]uint64 13 14// get returns the value of the i'th bit in the bitmap. 15func (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. 20func (b *pageBits) block64(i uint) uint64 { 21 return b[i/64] 22} 23 24// set sets bit i of pageBits. 25func (b *pageBits) set(i uint) { 26 b[i/64] |= 1 << (i % 64) 27} 28 29// setRange sets bits in the range [i, i+n). 30func (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. 54func (b *pageBits) setAll() { 55 for i := range b { 56 b[i] = ^uint64(0) 57 } 58} 59 60// clear clears bit i of pageBits. 61func (b *pageBits) clear(i uint) { 62 b[i/64] &^= 1 << (i % 64) 63} 64 65// clearRange clears bits in the range [i, i+n). 66func (b *pageBits) clearRange(i, n uint) { 67 _ = b[i/64] 68 if n == 1 { 69 // Fast path for the n == 1 case. 70 b.clear(i) 71 return 72 } 73 // Clear bits [i, j]. 74 j := i + n - 1 75 if i/64 == j/64 { 76 b[i/64] &^= ((uint64(1) << n) - 1) << (i % 64) 77 return 78 } 79 _ = b[j/64] 80 // Clear leading bits. 81 b[i/64] &^= ^uint64(0) << (i % 64) 82 for k := i/64 + 1; k < j/64; k++ { 83 b[k] = 0 84 } 85 // Clear trailing bits. 86 b[j/64] &^= (uint64(1) << (j%64 + 1)) - 1 87} 88 89// clearAll frees all the bits of b. 90func (b *pageBits) clearAll() { 91 for i := range b { 92 b[i] = 0 93 } 94} 95 96// popcntRange counts the number of set bits in the 97// range [i, i+n). 98func (b *pageBits) popcntRange(i, n uint) (s uint) { 99 if n == 1 { 100 return uint((b[i/64] >> (i % 64)) & 1) 101 } 102 _ = b[i/64] 103 j := i + n - 1 104 if i/64 == j/64 { 105 return uint(sys.OnesCount64((b[i/64] >> (i % 64)) & ((1 << n) - 1))) 106 } 107 _ = b[j/64] 108 s += uint(sys.OnesCount64(b[i/64] >> (i % 64))) 109 for k := i/64 + 1; k < j/64; k++ { 110 s += uint(sys.OnesCount64(b[k])) 111 } 112 s += uint(sys.OnesCount64(b[j/64] & ((1 << (j%64 + 1)) - 1))) 113 return 114} 115 116// pallocBits is a bitmap that tracks page allocations for at most one 117// palloc chunk. 118// 119// The precise representation is an implementation detail, but for the 120// sake of documentation, 0s are free pages and 1s are allocated pages. 121type pallocBits pageBits 122 123// consec8tab is a table containing the number of consecutive 124// zero bits for any uint8 value. 125// 126// The table is generated by calling consec8(i) for each 127// possible uint8 value, which is defined as: 128// 129// // consec8 counts the maximum number of consecutive 0 bits 130// // in a uint8. 131// func consec8(n uint8) int { 132// n = ^n 133// i := 0 134// for n != 0 { 135// n &= (n << 1) 136// i++ 137// } 138// return i 139// } 140var consec8tab = [256]uint{ 141 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 142 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 143 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 144 4, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 145 6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 146 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 147 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 148 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 149 7, 6, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 150 4, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 151 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 152 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 153 6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 154 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 155 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 156 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0, 157} 158 159// summarize returns a packed summary of the bitmap in pallocBits. 160func (b *pallocBits) summarize() pallocSum { 161 // TODO(mknyszek): There may be something more clever to be done 162 // here to make the summarize operation more efficient. For example, 163 // we can compute start and end with 64-bit wide operations easily, 164 // but max is a bit more complex. Perhaps there exists some way to 165 // leverage the 64-bit start and end to our advantage? 166 var start, max, end uint 167 for i := 0; i < len(b); i++ { 168 a := b[i] 169 for j := 0; j < 64; j += 8 { 170 k := uint8(a >> j) 171 172 // Compute start. 173 si := uint(sys.TrailingZeros8(k)) 174 if start == uint(i*64+j) { 175 start += si 176 } 177 178 // Compute max. 179 if end+si > max { 180 max = end + si 181 } 182 if mi := consec8tab[k]; mi > max { 183 max = mi 184 } 185 186 // Compute end. 187 if k == 0 { 188 end += 8 189 } else { 190 end = uint(sys.LeadingZeros8(k)) 191 } 192 } 193 } 194 return packPallocSum(start, max, end) 195} 196 197// find searches for npages contiguous free pages in pallocBits and returns 198// the index where that run starts, as well as the index of the first free page 199// it found in the search. searchIdx represents the first known free page and 200// where to begin the search from. 201// 202// If find fails to find any free space, it returns an index of ^uint(0) and 203// the new searchIdx should be ignored. 204// 205// Note that if npages == 1, the two returned values will always be identical. 206func (b *pallocBits) find(npages uintptr, searchIdx uint) (uint, uint) { 207 if npages == 1 { 208 addr := b.find1(searchIdx) 209 return addr, addr 210 } else if npages <= 64 { 211 return b.findSmallN(npages, searchIdx) 212 } 213 return b.findLargeN(npages, searchIdx) 214} 215 216// find1 is a helper for find which searches for a single free page 217// in the pallocBits and returns the index. 218// 219// See find for an explanation of the searchIdx parameter. 220func (b *pallocBits) find1(searchIdx uint) uint { 221 for i := searchIdx / 64; i < uint(len(b)); i++ { 222 x := b[i] 223 if x == ^uint64(0) { 224 continue 225 } 226 return i*64 + uint(sys.TrailingZeros64(^x)) 227 } 228 return ^uint(0) 229} 230 231// findSmallN is a helper for find which searches for npages contiguous free pages 232// in this pallocBits and returns the index where that run of contiguous pages 233// starts as well as the index of the first free page it finds in its search. 234// 235// See find for an explanation of the searchIdx parameter. 236// 237// Returns a ^uint(0) index on failure and the new searchIdx should be ignored. 238// 239// findSmallN assumes npages <= 64, where any such contiguous run of pages 240// crosses at most one aligned 64-bit boundary in the bits. 241func (b *pallocBits) findSmallN(npages uintptr, searchIdx uint) (uint, uint) { 242 end, newSearchIdx := uint(0), ^uint(0) 243 for i := searchIdx / 64; i < uint(len(b)); i++ { 244 bi := b[i] 245 if bi == ^uint64(0) { 246 end = 0 247 continue 248 } 249 // First see if we can pack our allocation in the trailing 250 // zeros plus the end of the last 64 bits. 251 start := uint(sys.TrailingZeros64(bi)) 252 if newSearchIdx == ^uint(0) { 253 // The new searchIdx is going to be at these 64 bits after any 254 // 1s we file, so count trailing 1s. 255 newSearchIdx = i*64 + uint(sys.TrailingZeros64(^bi)) 256 } 257 if end+start >= uint(npages) { 258 return i*64 - end, newSearchIdx 259 } 260 // Next, check the interior of the 64-bit chunk. 261 j := findBitRange64(^bi, uint(npages)) 262 if j < 64 { 263 return i*64 + j, newSearchIdx 264 } 265 end = uint(sys.LeadingZeros64(bi)) 266 } 267 return ^uint(0), newSearchIdx 268} 269 270// findLargeN is a helper for find which searches for npages contiguous free pages 271// in this pallocBits and returns the index where that run starts, as well as the 272// index of the first free page it found it its search. 273// 274// See alloc for an explanation of the searchIdx parameter. 275// 276// Returns a ^uint(0) index on failure and the new searchIdx should be ignored. 277// 278// findLargeN assumes npages > 64, where any such run of free pages 279// crosses at least one aligned 64-bit boundary in the bits. 280func (b *pallocBits) findLargeN(npages uintptr, searchIdx uint) (uint, uint) { 281 start, size, newSearchIdx := ^uint(0), uint(0), ^uint(0) 282 for i := searchIdx / 64; i < uint(len(b)); i++ { 283 x := b[i] 284 if x == ^uint64(0) { 285 size = 0 286 continue 287 } 288 if newSearchIdx == ^uint(0) { 289 // The new searchIdx is going to be at these 64 bits after any 290 // 1s we file, so count trailing 1s. 291 newSearchIdx = i*64 + uint(sys.TrailingZeros64(^x)) 292 } 293 if size == 0 { 294 size = uint(sys.LeadingZeros64(x)) 295 start = i*64 + 64 - size 296 continue 297 } 298 s := uint(sys.TrailingZeros64(x)) 299 if s+size >= uint(npages) { 300 size += s 301 return start, newSearchIdx 302 } 303 if s < 64 { 304 size = uint(sys.LeadingZeros64(x)) 305 start = i*64 + 64 - size 306 continue 307 } 308 size += 64 309 } 310 if size < uint(npages) { 311 return ^uint(0), newSearchIdx 312 } 313 return start, newSearchIdx 314} 315 316// allocRange allocates the range [i, i+n). 317func (b *pallocBits) allocRange(i, n uint) { 318 (*pageBits)(b).setRange(i, n) 319} 320 321// allocAll allocates all the bits of b. 322func (b *pallocBits) allocAll() { 323 (*pageBits)(b).setAll() 324} 325 326// free1 frees a single page in the pallocBits at i. 327func (b *pallocBits) free1(i uint) { 328 (*pageBits)(b).clear(i) 329} 330 331// free frees the range [i, i+n) of pages in the pallocBits. 332func (b *pallocBits) free(i, n uint) { 333 (*pageBits)(b).clearRange(i, n) 334} 335 336// freeAll frees all the bits of b. 337func (b *pallocBits) freeAll() { 338 (*pageBits)(b).clearAll() 339} 340 341// pages64 returns a 64-bit bitmap representing a block of 64 pages aligned 342// to 64 pages. The returned block of pages is the one containing the i'th 343// page in this pallocBits. Each bit represents whether the page is in-use. 344func (b *pallocBits) pages64(i uint) uint64 { 345 return (*pageBits)(b).block64(i) 346} 347 348// findBitRange64 returns the bit index of the first set of 349// n consecutive 1 bits. If no consecutive set of 1 bits of 350// size n may be found in c, then it returns an integer >= 64. 351func findBitRange64(c uint64, n uint) uint { 352 i := uint(0) 353 cont := uint(sys.TrailingZeros64(^c)) 354 for cont < n && i < 64 { 355 i += cont 356 i += uint(sys.TrailingZeros64(c >> i)) 357 cont = uint(sys.TrailingZeros64(^(c >> i))) 358 } 359 return i 360} 361 362// pallocData encapsulates pallocBits and a bitmap for 363// whether or not a given page is scavenged in a single 364// structure. It's effectively a pallocBits with 365// additional functionality. 366// 367// Update the comment on (*pageAlloc).chunks should this 368// structure change. 369type pallocData struct { 370 pallocBits 371 scavenged pageBits 372} 373 374// allocRange sets bits [i, i+n) in the bitmap to 1 and 375// updates the scavenged bits appropriately. 376func (m *pallocData) allocRange(i, n uint) { 377 // Clear the scavenged bits when we alloc the range. 378 m.pallocBits.allocRange(i, n) 379 m.scavenged.clearRange(i, n) 380} 381 382// allocAll sets every bit in the bitmap to 1 and updates 383// the scavenged bits appropriately. 384func (m *pallocData) allocAll() { 385 // Clear the scavenged bits when we alloc the range. 386 m.pallocBits.allocAll() 387 m.scavenged.clearAll() 388} 389