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

// 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 ( *pageBits) ( uint) uint {
	return uint(([/64] >> ( % 64)) & 1)
}

// block64 returns the 64-bit aligned block of bits containing the i'th bit.
func ( *pageBits) ( uint) uint64 {
	return [/64]
}

// set sets bit i of pageBits.
func ( *pageBits) ( uint) {
	[/64] |= 1 << ( % 64)
}

// setRange sets bits in the range [i, i+n).
func ( *pageBits) (,  uint) {
	_ = [/64]
	if  == 1 {
		// Fast path for the n == 1 case.
		.set()
		return
	}
	// Set bits [i, j].
	 :=  +  - 1
	if /64 == /64 {
		[/64] |= ((uint64(1) << ) - 1) << ( % 64)
		return
	}
	_ = [/64]
	// Set leading bits.
	[/64] |= ^uint64(0) << ( % 64)
	for  := /64 + 1;  < /64; ++ {
		[] = ^uint64(0)
	}
	// Set trailing bits.
	[/64] |= (uint64(1) << (%64 + 1)) - 1
}

// setAll sets all the bits of b.
func ( *pageBits) () {
	for  := range  {
		[] = ^uint64(0)
	}
}

// setBlock64 sets the 64-bit aligned block of bits containing the i'th bit that
// are set in v.
func ( *pageBits) ( uint,  uint64) {
	[/64] |= 
}

// clear clears bit i of pageBits.
func ( *pageBits) ( uint) {
	[/64] &^= 1 << ( % 64)
}

// clearRange clears bits in the range [i, i+n).
func ( *pageBits) (,  uint) {
	_ = [/64]
	if  == 1 {
		// Fast path for the n == 1 case.
		.clear()
		return
	}
	// Clear bits [i, j].
	 :=  +  - 1
	if /64 == /64 {
		[/64] &^= ((uint64(1) << ) - 1) << ( % 64)
		return
	}
	_ = [/64]
	// Clear leading bits.
	[/64] &^= ^uint64(0) << ( % 64)
	for  := /64 + 1;  < /64; ++ {
		[] = 0
	}
	// Clear trailing bits.
	[/64] &^= (uint64(1) << (%64 + 1)) - 1
}

// clearAll frees all the bits of b.
func ( *pageBits) () {
	for  := range  {
		[] = 0
	}
}

// clearBlock64 clears the 64-bit aligned block of bits containing the i'th bit that
// are set in v.
func ( *pageBits) ( uint,  uint64) {
	[/64] &^= 
}

// popcntRange counts the number of set bits in the
// range [i, i+n).
func ( *pageBits) (,  uint) ( uint) {
	if  == 1 {
		return uint(([/64] >> ( % 64)) & 1)
	}
	_ = [/64]
	 :=  +  - 1
	if /64 == /64 {
		return uint(sys.OnesCount64(([/64] >> ( % 64)) & ((1 << ) - 1)))
	}
	_ = [/64]
	 += uint(sys.OnesCount64([/64] >> ( % 64)))
	for  := /64 + 1;  < /64; ++ {
		 += uint(sys.OnesCount64([]))
	}
	 += uint(sys.OnesCount64([/64] & ((1 << (%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

// summarize returns a packed summary of the bitmap in pallocBits.
func ( *pallocBits) () pallocSum {
	var , ,  uint
	const  = ^uint(0) // sentinel for start value
	 = 
	for  := 0;  < len(); ++ {
		 := []
		if  == 0 {
			 += 64
			continue
		}
		 := uint(sys.TrailingZeros64())
		 := uint(sys.LeadingZeros64())

		// Finish any region spanning the uint64s
		 += 
		if  ==  {
			 = 
		}
		if  >  {
			 = 
		}
		// Final region that might span to next uint64
		 = 
	}
	if  ==  {
		// Made it all the way through without finding a single 1 bit.
		const  = uint(64 * len())
		return packPallocSum(, , )
	}
	if  >  {
		 = 
	}
	if  >= 64-2 {
		// There is no way an internal run of zeros could beat max.
		return packPallocSum(, , )
	}
	// Now look inside each uint64 for runs of zeros.
	// All uint64s must be nonzero, or we would have aborted above.
:
	for  := 0;  < len(); ++ {
		 := []

		// Look inside this uint64. We have a pattern like
		// 000000 1xxxxx1 000000
		// We need to look inside the 1xxxxx1 for any contiguous
		// region of zeros.

		// We already know the trailing zeros are no larger than max. Remove them.
		 >>= sys.TrailingZeros64() & 63
		if &(+1) == 0 { // no more zeros (except at the top).
			continue
		}

		// Strategy: shrink all runs of zeros by max. If any runs of zero
		// remain, then we've identified a larger maxiumum zero run.
		 :=      // number of zeros we still need to shrink by.
		 := uint(1) // current minimum length of runs of ones in x.
		for {
			// Shrink all runs of zeros by p places (except the top zeros).
			for  > 0 {
				if  <=  {
					// Shift p ones down into the top of each run of zeros.
					 |=  >> ( & 63)
					if &(+1) == 0 { // no more zeros (except at the top).
						continue 
					}
					break
				}
				// Shift k ones down into the top of each run of zeros.
				 |=  >> ( & 63)
				if &(+1) == 0 { // no more zeros (except at the top).
					continue 
				}
				 -= 
				// We've just doubled the minimum length of 1-runs.
				// This allows us to shift farther in the next iteration.
				 *= 2
			}

			// The length of the lowest-order zero run is an increment to our maximum.
			 := uint(sys.TrailingZeros64(^)) // count contiguous trailing ones
			 >>=  & 63                       // remove trailing ones
			 = uint(sys.TrailingZeros64())   // count contiguous trailing zeros
			 >>=  & 63                       // remove zeros
			 +=                            // we have a new maximum!
			if &(+1) == 0 {                  // no more zeros (except at the top).
				continue 
			}
			 =  // remove j more zeros from each zero run.
		}
	}
	return packPallocSum(, , )
}

// 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 next 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 ( *pallocBits) ( uintptr,  uint) (uint, uint) {
	if  == 1 {
		 := .find1()
		return , 
	} else if  <= 64 {
		return .findSmallN(, )
	}
	return .findLargeN(, )
}

// 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 ( *pallocBits) ( uint) uint {
	_ = [0] // lift nil check out of loop
	for  :=  / 64;  < uint(len()); ++ {
		 := []
		if ^ == 0 {
			continue
		}
		return *64 + uint(sys.TrailingZeros64(^))
	}
	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 ( *pallocBits) ( uintptr,  uint) (uint, uint) {
	,  := uint(0), ^uint(0)
	for  :=  / 64;  < uint(len()); ++ {
		 := []
		if ^ == 0 {
			 = 0
			continue
		}
		// First see if we can pack our allocation in the trailing
		// zeros plus the end of the last 64 bits.
		if  == ^uint(0) {
			// The new searchIdx is going to be at these 64 bits after any
			// 1s we file, so count trailing 1s.
			 = *64 + uint(sys.TrailingZeros64(^))
		}
		 := uint(sys.TrailingZeros64())
		if + >= uint() {
			return *64 - , 
		}
		// Next, check the interior of the 64-bit chunk.
		 := findBitRange64(^, uint())
		if  < 64 {
			return *64 + , 
		}
		 = uint(sys.LeadingZeros64())
	}
	return ^uint(0), 
}

// 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 ( *pallocBits) ( uintptr,  uint) (uint, uint) {
	, ,  := ^uint(0), uint(0), ^uint(0)
	for  :=  / 64;  < uint(len()); ++ {
		 := []
		if  == ^uint64(0) {
			 = 0
			continue
		}
		if  == ^uint(0) {
			// The new searchIdx is going to be at these 64 bits after any
			// 1s we file, so count trailing 1s.
			 = *64 + uint(sys.TrailingZeros64(^))
		}
		if  == 0 {
			 = uint(sys.LeadingZeros64())
			 = *64 + 64 - 
			continue
		}
		 := uint(sys.TrailingZeros64())
		if + >= uint() {
			 += 
			return , 
		}
		if  < 64 {
			 = uint(sys.LeadingZeros64())
			 = *64 + 64 - 
			continue
		}
		 += 64
	}
	if  < uint() {
		return ^uint(0), 
	}
	return , 
}

// allocRange allocates the range [i, i+n).
func ( *pallocBits) (,  uint) {
	(*pageBits)().setRange(, )
}

// allocAll allocates all the bits of b.
func ( *pallocBits) () {
	(*pageBits)().setAll()
}

// free1 frees a single page in the pallocBits at i.
func ( *pallocBits) ( uint) {
	(*pageBits)().clear()
}

// free frees the range [i, i+n) of pages in the pallocBits.
func ( *pallocBits) (,  uint) {
	(*pageBits)().clearRange(, )
}

// freeAll frees all the bits of b.
func ( *pallocBits) () {
	(*pageBits)().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 ( *pallocBits) ( uint) uint64 {
	return (*pageBits)().block64()
}

// allocPages64 allocates a 64-bit block of 64 pages aligned to 64 pages according
// to the bits set in alloc. The block set is the one containing the i'th page.
func ( *pallocBits) ( uint,  uint64) {
	(*pageBits)().setBlock64(, )
}

// 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.
// n must be > 0.
func findBitRange64( uint64,  uint) uint {
	// This implementation is based on shrinking the length of
	// runs of contiguous 1 bits. We remove the top n-1 1 bits
	// from each run of 1s, then look for the first remaining 1 bit.
	 :=  - 1   // number of 1s we want to remove.
	 := uint(1) // current minimum width of runs of 0 in c.
	for  > 0 {
		if  <=  {
			// Shift p 0s down into the top of each run of 1s.
			 &=  >> ( & 63)
			break
		}
		// Shift k 0s down into the top of each run of 1s.
		 &=  >> ( & 63)
		if  == 0 {
			return 64
		}
		 -= 
		// We've just doubled the minimum length of 0-runs.
		// This allows us to shift farther in the next iteration.
		 *= 2
	}
	// Find first remaining 1.
	// Since we shrunk from the top down, the first 1 is in
	// its correct original position.
	return uint(sys.TrailingZeros64())
}

// 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 ( *pallocData) (,  uint) {
	// Clear the scavenged bits when we alloc the range.
	.pallocBits.allocRange(, )
	.scavenged.clearRange(, )
}

// allocAll sets every bit in the bitmap to 1 and updates
// the scavenged bits appropriately.
func ( *pallocData) () {
	// Clear the scavenged bits when we alloc the range.
	.pallocBits.allocAll()
	.scavenged.clearAll()
}