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()
}