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