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