blob: a8011341bce06a114b68c21643c609276ef72930 [file] [log] [blame]
 // Copyright 2019 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package runtime import ( "runtime/internal/sys" ) // pageBits is a bitmap representing one bit per page in a palloc chunk. type pageBits [pallocChunkPages / 64]uint64 // get returns the value of the i'th bit in the bitmap. func (b *pageBits) get(i uint) uint { return uint((b[i/64] >> (i % 64)) & 1) } // block64 returns the 64-bit aligned block of bits containing the i'th bit. func (b *pageBits) block64(i uint) uint64 { return b[i/64] } // set sets bit i of pageBits. func (b *pageBits) set(i uint) { b[i/64] |= 1 << (i % 64) } // setRange sets bits in the range [i, i+n). func (b *pageBits) setRange(i, n uint) { _ = b[i/64] if n == 1 { // Fast path for the n == 1 case. b.set(i) return } // Set bits [i, j]. j := i + n - 1 if i/64 == j/64 { b[i/64] |= ((uint64(1) << n) - 1) << (i % 64) return } _ = b[j/64] // Set leading bits. b[i/64] |= ^uint64(0) << (i % 64) for k := i/64 + 1; k < j/64; k++ { b[k] = ^uint64(0) } // Set trailing bits. b[j/64] |= (uint64(1) << (j%64 + 1)) - 1 } // setAll sets all the bits of b. func (b *pageBits) setAll() { for i := range b { b[i] = ^uint64(0) } } // clear clears bit i of pageBits. func (b *pageBits) clear(i uint) { b[i/64] &^= 1 << (i % 64) } // clearRange clears bits in the range [i, i+n). func (b *pageBits) clearRange(i, n uint) { _ = b[i/64] if n == 1 { // Fast path for the n == 1 case. b.clear(i) return } // Clear bits [i, j]. j := i + n - 1 if i/64 == j/64 { b[i/64] &^= ((uint64(1) << n) - 1) << (i % 64) return } _ = b[j/64] // Clear leading bits. b[i/64] &^= ^uint64(0) << (i % 64) for k := i/64 + 1; k < j/64; k++ { b[k] = 0 } // Clear trailing bits. b[j/64] &^= (uint64(1) << (j%64 + 1)) - 1 } // clearAll frees all the bits of b. func (b *pageBits) clearAll() { for i := range b { b[i] = 0 } } // popcntRange counts the number of set bits in the // range [i, i+n). func (b *pageBits) popcntRange(i, n uint) (s uint) { if n == 1 { return uint((b[i/64] >> (i % 64)) & 1) } _ = b[i/64] j := i + n - 1 if i/64 == j/64 { return uint(sys.OnesCount64((b[i/64] >> (i % 64)) & ((1 << n) - 1))) } _ = b[j/64] s += uint(sys.OnesCount64(b[i/64] >> (i % 64))) for k := i/64 + 1; k < j/64; k++ { s += uint(sys.OnesCount64(b[k])) } s += uint(sys.OnesCount64(b[j/64] & ((1 << (j%64 + 1)) - 1))) return } // pallocBits is a bitmap that tracks page allocations for at most one // palloc chunk. // // The precise representation is an implementation detail, but for the // sake of documentation, 0s are free pages and 1s are allocated pages. type pallocBits pageBits // consec8tab is a table containing the number of consecutive // zero bits for any uint8 value. // // The table is generated by calling consec8(i) for each // possible uint8 value, which is defined as: // // // consec8 counts the maximum number of consecutive 0 bits // // in a uint8. // func consec8(n uint8) int { // n = ^n // i := 0 // for n != 0 { // n &= (n << 1) // i++ // } // return i // } var consec8tab = [256]uint{ 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 7, 6, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0, } // summarize returns a packed summary of the bitmap in pallocBits. func (b *pallocBits) summarize() pallocSum { // TODO(mknyszek): There may be something more clever to be done // here to make the summarize operation more efficient. For example, // we can compute start and end with 64-bit wide operations easily, // but max is a bit more complex. Perhaps there exists some way to // leverage the 64-bit start and end to our advantage? var start, max, end uint for i := 0; i < len(b); i++ { a := b[i] for j := 0; j < 64; j += 8 { k := uint8(a >> j) // Compute start. si := uint(sys.TrailingZeros8(k)) if start == uint(i*64+j) { start += si } // Compute max. if end+si > max { max = end + si } if mi := consec8tab[k]; mi > max { max = mi } // Compute end. if k == 0 { end += 8 } else { end = uint(sys.LeadingZeros8(k)) } } } return packPallocSum(start, max, end) } // find searches for npages contiguous free pages in pallocBits and returns // the index where that run starts, as well as the index of the first free page // it found in the search. searchIdx represents the first known free page and // where to begin the search from. // // If find fails to find any free space, it returns an index of ^uint(0) and // the new searchIdx should be ignored. // // Note that if npages == 1, the two returned values will always be identical. func (b *pallocBits) find(npages uintptr, searchIdx uint) (uint, uint) { if npages == 1 { addr := b.find1(searchIdx) return addr, addr } else if npages <= 64 { return b.findSmallN(npages, searchIdx) } return b.findLargeN(npages, searchIdx) } // find1 is a helper for find which searches for a single free page // in the pallocBits and returns the index. // // See find for an explanation of the searchIdx parameter. func (b *pallocBits) find1(searchIdx uint) uint { for i := searchIdx / 64; i < uint(len(b)); i++ { x := b[i] if x == ^uint64(0) { continue } return i*64 + uint(sys.TrailingZeros64(^x)) } return ^uint(0) } // findSmallN is a helper for find which searches for npages contiguous free pages // in this pallocBits and returns the index where that run of contiguous pages // starts as well as the index of the first free page it finds in its search. // // See find for an explanation of the searchIdx parameter. // // Returns a ^uint(0) index on failure and the new searchIdx should be ignored. // // findSmallN assumes npages <= 64, where any such contiguous run of pages // crosses at most one aligned 64-bit boundary in the bits. func (b *pallocBits) findSmallN(npages uintptr, searchIdx uint) (uint, uint) { end, newSearchIdx := uint(0), ^uint(0) for i := searchIdx / 64; i < uint(len(b)); i++ { bi := b[i] if bi == ^uint64(0) { end = 0 continue } // First see if we can pack our allocation in the trailing // zeros plus the end of the last 64 bits. start := uint(sys.TrailingZeros64(bi)) if newSearchIdx == ^uint(0) { // The new searchIdx is going to be at these 64 bits after any // 1s we file, so count trailing 1s. newSearchIdx = i*64 + uint(sys.TrailingZeros64(^bi)) } if end+start >= uint(npages) { return i*64 - end, newSearchIdx } // Next, check the interior of the 64-bit chunk. j := findBitRange64(^bi, uint(npages)) if j < 64 { return i*64 + j, newSearchIdx } end = uint(sys.LeadingZeros64(bi)) } return ^uint(0), newSearchIdx } // findLargeN is a helper for find which searches for npages contiguous free pages // in this pallocBits and returns the index where that run starts, as well as the // index of the first free page it found it its search. // // See alloc for an explanation of the searchIdx parameter. // // Returns a ^uint(0) index on failure and the new searchIdx should be ignored. // // findLargeN assumes npages > 64, where any such run of free pages // crosses at least one aligned 64-bit boundary in the bits. func (b *pallocBits) findLargeN(npages uintptr, searchIdx uint) (uint, uint) { start, size, newSearchIdx := ^uint(0), uint(0), ^uint(0) for i := searchIdx / 64; i < uint(len(b)); i++ { x := b[i] if x == ^uint64(0) { size = 0 continue } if newSearchIdx == ^uint(0) { // The new searchIdx is going to be at these 64 bits after any // 1s we file, so count trailing 1s. newSearchIdx = i*64 + uint(sys.TrailingZeros64(^x)) } if size == 0 { size = uint(sys.LeadingZeros64(x)) start = i*64 + 64 - size continue } s := uint(sys.TrailingZeros64(x)) if s+size >= uint(npages) { size += s return start, newSearchIdx } if s < 64 { size = uint(sys.LeadingZeros64(x)) start = i*64 + 64 - size continue } size += 64 } if size < uint(npages) { return ^uint(0), newSearchIdx } return start, newSearchIdx } // allocRange allocates the range [i, i+n). func (b *pallocBits) allocRange(i, n uint) { (*pageBits)(b).setRange(i, n) } // allocAll allocates all the bits of b. func (b *pallocBits) allocAll() { (*pageBits)(b).setAll() } // free1 frees a single page in the pallocBits at i. func (b *pallocBits) free1(i uint) { (*pageBits)(b).clear(i) } // free frees the range [i, i+n) of pages in the pallocBits. func (b *pallocBits) free(i, n uint) { (*pageBits)(b).clearRange(i, n) } // freeAll frees all the bits of b. func (b *pallocBits) freeAll() { (*pageBits)(b).clearAll() } // pages64 returns a 64-bit bitmap representing a block of 64 pages aligned // to 64 pages. The returned block of pages is the one containing the i'th // page in this pallocBits. Each bit represents whether the page is in-use. func (b *pallocBits) pages64(i uint) uint64 { return (*pageBits)(b).block64(i) } // findBitRange64 returns the bit index of the first set of // n consecutive 1 bits. If no consecutive set of 1 bits of // size n may be found in c, then it returns an integer >= 64. func findBitRange64(c uint64, n uint) uint { i := uint(0) cont := uint(sys.TrailingZeros64(^c)) for cont < n && i < 64 { i += cont i += uint(sys.TrailingZeros64(c >> i)) cont = uint(sys.TrailingZeros64(^(c >> i))) } return i } // pallocData encapsulates pallocBits and a bitmap for // whether or not a given page is scavenged in a single // structure. It's effectively a pallocBits with // additional functionality. // // Update the comment on (*pageAlloc).chunks should this // structure change. type pallocData struct { pallocBits scavenged pageBits } // allocRange sets bits [i, i+n) in the bitmap to 1 and // updates the scavenged bits appropriately. func (m *pallocData) allocRange(i, n uint) { // Clear the scavenged bits when we alloc the range. m.pallocBits.allocRange(i, n) m.scavenged.clearRange(i, n) } // allocAll sets every bit in the bitmap to 1 and updates // the scavenged bits appropriately. func (m *pallocData) allocAll() { // Clear the scavenged bits when we alloc the range. m.pallocBits.allocAll() m.scavenged.clearAll() }