Black Lives Matter. Support the Equal Justice Initiative.

Source file src/runtime/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  // consec8tab is a table containing the number of consecutive
   124  // zero bits for any uint8 value.
   125  //
   126  // The table is generated by calling consec8(i) for each
   127  // possible uint8 value, which is defined as:
   128  //
   129  // // consec8 counts the maximum number of consecutive 0 bits
   130  // // in a uint8.
   131  // func consec8(n uint8) int {
   132  // 	n = ^n
   133  // 	i := 0
   134  // 	for n != 0 {
   135  // 		n &= (n << 1)
   136  // 		i++
   137  // 	}
   138  // 	return i
   139  // }
   140  var consec8tab = [256]uint{
   141  	8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
   142  	4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
   143  	5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2,
   144  	4, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2,
   145  	6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2,
   146  	4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1,
   147  	5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1,
   148  	4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1,
   149  	7, 6, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3,
   150  	4, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2,
   151  	5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1,
   152  	4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1,
   153  	6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2,
   154  	4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1,
   155  	5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1,
   156  	4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0,
   157  }
   158  
   159  // summarize returns a packed summary of the bitmap in pallocBits.
   160  func (b *pallocBits) summarize() pallocSum {
   161  	// TODO(mknyszek): There may be something more clever to be done
   162  	// here to make the summarize operation more efficient. For example,
   163  	// we can compute start and end with 64-bit wide operations easily,
   164  	// but max is a bit more complex. Perhaps there exists some way to
   165  	// leverage the 64-bit start and end to our advantage?
   166  	var start, max, end uint
   167  	for i := 0; i < len(b); i++ {
   168  		a := b[i]
   169  		for j := 0; j < 64; j += 8 {
   170  			k := uint8(a >> j)
   171  
   172  			// Compute start.
   173  			si := uint(sys.TrailingZeros8(k))
   174  			if start == uint(i*64+j) {
   175  				start += si
   176  			}
   177  
   178  			// Compute max.
   179  			if end+si > max {
   180  				max = end + si
   181  			}
   182  			if mi := consec8tab[k]; mi > max {
   183  				max = mi
   184  			}
   185  
   186  			// Compute end.
   187  			if k == 0 {
   188  				end += 8
   189  			} else {
   190  				end = uint(sys.LeadingZeros8(k))
   191  			}
   192  		}
   193  	}
   194  	return packPallocSum(start, max, end)
   195  }
   196  
   197  // find searches for npages contiguous free pages in pallocBits and returns
   198  // the index where that run starts, as well as the index of the first free page
   199  // it found in the search. searchIdx represents the first known free page and
   200  // where to begin the search from.
   201  //
   202  // If find fails to find any free space, it returns an index of ^uint(0) and
   203  // the new searchIdx should be ignored.
   204  //
   205  // Note that if npages == 1, the two returned values will always be identical.
   206  func (b *pallocBits) find(npages uintptr, searchIdx uint) (uint, uint) {
   207  	if npages == 1 {
   208  		addr := b.find1(searchIdx)
   209  		return addr, addr
   210  	} else if npages <= 64 {
   211  		return b.findSmallN(npages, searchIdx)
   212  	}
   213  	return b.findLargeN(npages, searchIdx)
   214  }
   215  
   216  // find1 is a helper for find which searches for a single free page
   217  // in the pallocBits and returns the index.
   218  //
   219  // See find for an explanation of the searchIdx parameter.
   220  func (b *pallocBits) find1(searchIdx uint) uint {
   221  	for i := searchIdx / 64; i < uint(len(b)); i++ {
   222  		x := b[i]
   223  		if x == ^uint64(0) {
   224  			continue
   225  		}
   226  		return i*64 + uint(sys.TrailingZeros64(^x))
   227  	}
   228  	return ^uint(0)
   229  }
   230  
   231  // findSmallN is a helper for find which searches for npages contiguous free pages
   232  // in this pallocBits and returns the index where that run of contiguous pages
   233  // starts as well as the index of the first free page it finds in its search.
   234  //
   235  // See find for an explanation of the searchIdx parameter.
   236  //
   237  // Returns a ^uint(0) index on failure and the new searchIdx should be ignored.
   238  //
   239  // findSmallN assumes npages <= 64, where any such contiguous run of pages
   240  // crosses at most one aligned 64-bit boundary in the bits.
   241  func (b *pallocBits) findSmallN(npages uintptr, searchIdx uint) (uint, uint) {
   242  	end, newSearchIdx := uint(0), ^uint(0)
   243  	for i := searchIdx / 64; i < uint(len(b)); i++ {
   244  		bi := b[i]
   245  		if bi == ^uint64(0) {
   246  			end = 0
   247  			continue
   248  		}
   249  		// First see if we can pack our allocation in the trailing
   250  		// zeros plus the end of the last 64 bits.
   251  		start := uint(sys.TrailingZeros64(bi))
   252  		if newSearchIdx == ^uint(0) {
   253  			// The new searchIdx is going to be at these 64 bits after any
   254  			// 1s we file, so count trailing 1s.
   255  			newSearchIdx = i*64 + uint(sys.TrailingZeros64(^bi))
   256  		}
   257  		if end+start >= uint(npages) {
   258  			return i*64 - end, newSearchIdx
   259  		}
   260  		// Next, check the interior of the 64-bit chunk.
   261  		j := findBitRange64(^bi, uint(npages))
   262  		if j < 64 {
   263  			return i*64 + j, newSearchIdx
   264  		}
   265  		end = uint(sys.LeadingZeros64(bi))
   266  	}
   267  	return ^uint(0), newSearchIdx
   268  }
   269  
   270  // findLargeN is a helper for find which searches for npages contiguous free pages
   271  // in this pallocBits and returns the index where that run starts, as well as the
   272  // index of the first free page it found it its search.
   273  //
   274  // See alloc for an explanation of the searchIdx parameter.
   275  //
   276  // Returns a ^uint(0) index on failure and the new searchIdx should be ignored.
   277  //
   278  // findLargeN assumes npages > 64, where any such run of free pages
   279  // crosses at least one aligned 64-bit boundary in the bits.
   280  func (b *pallocBits) findLargeN(npages uintptr, searchIdx uint) (uint, uint) {
   281  	start, size, newSearchIdx := ^uint(0), uint(0), ^uint(0)
   282  	for i := searchIdx / 64; i < uint(len(b)); i++ {
   283  		x := b[i]
   284  		if x == ^uint64(0) {
   285  			size = 0
   286  			continue
   287  		}
   288  		if newSearchIdx == ^uint(0) {
   289  			// The new searchIdx is going to be at these 64 bits after any
   290  			// 1s we file, so count trailing 1s.
   291  			newSearchIdx = i*64 + uint(sys.TrailingZeros64(^x))
   292  		}
   293  		if size == 0 {
   294  			size = uint(sys.LeadingZeros64(x))
   295  			start = i*64 + 64 - size
   296  			continue
   297  		}
   298  		s := uint(sys.TrailingZeros64(x))
   299  		if s+size >= uint(npages) {
   300  			size += s
   301  			return start, newSearchIdx
   302  		}
   303  		if s < 64 {
   304  			size = uint(sys.LeadingZeros64(x))
   305  			start = i*64 + 64 - size
   306  			continue
   307  		}
   308  		size += 64
   309  	}
   310  	if size < uint(npages) {
   311  		return ^uint(0), newSearchIdx
   312  	}
   313  	return start, newSearchIdx
   314  }
   315  
   316  // allocRange allocates the range [i, i+n).
   317  func (b *pallocBits) allocRange(i, n uint) {
   318  	(*pageBits)(b).setRange(i, n)
   319  }
   320  
   321  // allocAll allocates all the bits of b.
   322  func (b *pallocBits) allocAll() {
   323  	(*pageBits)(b).setAll()
   324  }
   325  
   326  // free1 frees a single page in the pallocBits at i.
   327  func (b *pallocBits) free1(i uint) {
   328  	(*pageBits)(b).clear(i)
   329  }
   330  
   331  // free frees the range [i, i+n) of pages in the pallocBits.
   332  func (b *pallocBits) free(i, n uint) {
   333  	(*pageBits)(b).clearRange(i, n)
   334  }
   335  
   336  // freeAll frees all the bits of b.
   337  func (b *pallocBits) freeAll() {
   338  	(*pageBits)(b).clearAll()
   339  }
   340  
   341  // pages64 returns a 64-bit bitmap representing a block of 64 pages aligned
   342  // to 64 pages. The returned block of pages is the one containing the i'th
   343  // page in this pallocBits. Each bit represents whether the page is in-use.
   344  func (b *pallocBits) pages64(i uint) uint64 {
   345  	return (*pageBits)(b).block64(i)
   346  }
   347  
   348  // findBitRange64 returns the bit index of the first set of
   349  // n consecutive 1 bits. If no consecutive set of 1 bits of
   350  // size n may be found in c, then it returns an integer >= 64.
   351  func findBitRange64(c uint64, n uint) uint {
   352  	i := uint(0)
   353  	cont := uint(sys.TrailingZeros64(^c))
   354  	for cont < n && i < 64 {
   355  		i += cont
   356  		i += uint(sys.TrailingZeros64(c >> i))
   357  		cont = uint(sys.TrailingZeros64(^(c >> i)))
   358  	}
   359  	return i
   360  }
   361  
   362  // pallocData encapsulates pallocBits and a bitmap for
   363  // whether or not a given page is scavenged in a single
   364  // structure. It's effectively a pallocBits with
   365  // additional functionality.
   366  //
   367  // Update the comment on (*pageAlloc).chunks should this
   368  // structure change.
   369  type pallocData struct {
   370  	pallocBits
   371  	scavenged pageBits
   372  }
   373  
   374  // allocRange sets bits [i, i+n) in the bitmap to 1 and
   375  // updates the scavenged bits appropriately.
   376  func (m *pallocData) allocRange(i, n uint) {
   377  	// Clear the scavenged bits when we alloc the range.
   378  	m.pallocBits.allocRange(i, n)
   379  	m.scavenged.clearRange(i, n)
   380  }
   381  
   382  // allocAll sets every bit in the bitmap to 1 and updates
   383  // the scavenged bits appropriately.
   384  func (m *pallocData) allocAll() {
   385  	// Clear the scavenged bits when we alloc the range.
   386  	m.pallocBits.allocAll()
   387  	m.scavenged.clearAll()
   388  }
   389  

View as plain text