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  // 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