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