mpallocbits.go

Documentation: runtime

     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  }
   444
View as plain text