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