// Copyright 2009 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 runtimeimport ()// addb returns the byte pointer p+n.////go:nowritebarrier//go:nosplitfunc addb( *byte, uintptr) *byte {// Note: wrote out full expression instead of calling add(p, n) // to reduce the number of temporaries generated by the // compiler for this trivial expression during inlining.return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer()) + ))}// subtractb returns the byte pointer p-n.////go:nowritebarrier//go:nosplitfunc subtractb( *byte, uintptr) *byte {// Note: wrote out full expression instead of calling add(p, -n) // to reduce the number of temporaries generated by the // compiler for this trivial expression during inlining.return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer()) - ))}// add1 returns the byte pointer p+1.////go:nowritebarrier//go:nosplitfunc add1( *byte) *byte {// Note: wrote out full expression instead of calling addb(p, 1) // to reduce the number of temporaries generated by the // compiler for this trivial expression during inlining.return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer()) + 1))}// subtract1 returns the byte pointer p-1.//// nosplit because it is used during write barriers and must not be preempted.////go:nowritebarrier//go:nosplitfunc subtract1( *byte) *byte {// Note: wrote out full expression instead of calling subtractb(p, 1) // to reduce the number of temporaries generated by the // compiler for this trivial expression during inlining.return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer()) - 1))}// markBits provides access to the mark bit for an object in the heap.// bytep points to the byte holding the mark bit.// mask is a byte with a single bit set that can be &ed with *bytep// to see if the bit has been set.// *m.byte&m.mask != 0 indicates the mark bit is set.// index can be used along with span information to generate// the address of the object in the heap.// We maintain one set of mark bits for allocation and one for// marking purposes.type markBits struct { bytep *uint8 mask uint8 index uintptr}//go:nosplitfunc ( *mspan) ( uintptr) markBits { , := .allocBits.bitp()returnmarkBits{, , }}// refillAllocCache takes 8 bytes s.allocBits starting at whichByte// and negates them so that ctz (count trailing zeros) instructions// can be used. It then places these 8 bytes into the cached 64 bit// s.allocCache.func ( *mspan) ( uint16) { := (*[8]uint8)(unsafe.Pointer(.allocBits.bytep(uintptr()))) := uint64(0) |= uint64([0]) |= uint64([1]) << (1 * 8) |= uint64([2]) << (2 * 8) |= uint64([3]) << (3 * 8) |= uint64([4]) << (4 * 8) |= uint64([5]) << (5 * 8) |= uint64([6]) << (6 * 8) |= uint64([7]) << (7 * 8) .allocCache = ^}// nextFreeIndex returns the index of the next free object in s at// or after s.freeindex.// There are hardware instructions that can be used to make this// faster if profiling warrants it.func ( *mspan) () uint16 { := .freeindex := .nelemsif == {return }if > {throw("s.freeindex > s.nelems") } := .allocCache := sys.TrailingZeros64()for == 64 {// Move index to start of next cached bits. = ( + 64) &^ (64 - 1)if >= { .freeindex = return } := / 8// Refill s.allocCache with the next 64 alloc bits. .refillAllocCache() = .allocCache = sys.TrailingZeros64()// nothing available in cached bits // grab the next 8 bytes and try again. } := + uint16()if >= { .freeindex = return } .allocCache >>= uint( + 1) = + 1if %64 == 0 && != {// We just incremented s.freeindex so it isn't 0. // As each 1 in s.allocCache was encountered and used for allocation // it was shifted away. At this point s.allocCache contains all 0s. // Refill s.allocCache so that it corresponds // to the bits at s.allocBits starting at s.freeindex. := / 8 .refillAllocCache() } .freeindex = return}// isFree reports whether the index'th object in s is unallocated.//// The caller must ensure s.state is mSpanInUse, and there must have// been no preemption points since ensuring this (which could allow a// GC transition, which would allow the state to change).func ( *mspan) ( uintptr) bool {if < uintptr(.freeIndexForScan) {returnfalse } , := .allocBits.bitp()return *& == 0}// divideByElemSize returns n/s.elemsize.// n must be within [0, s.npages*_PageSize),// or may be exactly s.npages*_PageSize// if s.elemsize is from sizeclasses.go.//// nosplit, because it is called by objIndex, which is nosplit////go:nosplitfunc ( *mspan) ( uintptr) uintptr {const = false// See explanation in mksizeclasses.go's computeDivMagic. := uintptr((uint64() * uint64(.divMul)) >> 32)if && != /.elemsize {println(, "/", .elemsize, "should be", /.elemsize, "but got", )throw("bad magic division") }return}// nosplit, because it is called by other nosplit code like findObject////go:nosplitfunc ( *mspan) ( uintptr) uintptr {return .divideByElemSize( - .base())}func markBitsForAddr( uintptr) markBits { := spanOf() := .objIndex()return .markBitsForIndex()}func ( *mspan) ( uintptr) markBits { , := .gcmarkBits.bitp()returnmarkBits{, , }}func ( *mspan) () markBits {returnmarkBits{&.gcmarkBits.x, uint8(1), 0}}// isMarked reports whether mark bit m is set.func ( markBits) () bool {return *.bytep&.mask != 0}// setMarked sets the marked bit in the markbits, atomically.func ( markBits) () {// Might be racing with other updates, so use atomic update always. // We used to be clever here and use a non-atomic update in certain // cases, but it's not worth the risk.atomic.Or8(.bytep, .mask)}// setMarkedNonAtomic sets the marked bit in the markbits, non-atomically.func ( markBits) () { *.bytep |= .mask}// clearMarked clears the marked bit in the markbits, atomically.func ( markBits) () {// Might be racing with other updates, so use atomic update always. // We used to be clever here and use a non-atomic update in certain // cases, but it's not worth the risk.atomic.And8(.bytep, ^.mask)}// markBitsForSpan returns the markBits for the span base address base.func markBitsForSpan( uintptr) ( markBits) { = markBitsForAddr()if .mask != 1 {throw("markBitsForSpan: unaligned start") }return}// advance advances the markBits to the next object in the span.func ( *markBits) () {if .mask == 1<<7 { .bytep = (*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(.bytep)) + 1)) .mask = 1 } else { .mask = .mask << 1 } .index++}// clobberdeadPtr is a special value that is used by the compiler to// clobber dead stack slots, when -clobberdead flag is set.const clobberdeadPtr = uintptr(0xdeaddead | 0xdeaddead<<((^uintptr(0)>>63)*32))// badPointer throws bad pointer in heap panic.func badPointer( *mspan, , , uintptr) {// Typically this indicates an incorrect use // of unsafe or cgo to store a bad pointer in // the Go heap. It may also indicate a runtime // bug. // // TODO(austin): We could be more aggressive // and detect pointers to unallocated objects // in allocated spans.printlock()print("runtime: pointer ", hex())if != nil { := .state.get()if != mSpanInUse {print(" to unallocated span") } else {print(" to unused region of span") }print(" span.base()=", hex(.base()), " span.limit=", hex(.limit), " span.state=", ) }print("\n")if != 0 {print("runtime: found in object at *(", hex(), "+", hex(), ")\n")gcDumpObject("object", , ) }getg().m.traceback = 2throw("found bad pointer in Go heap (incorrect use of unsafe or cgo?)")}// findObject returns the base address for the heap object containing// the address p, the object's span, and the index of the object in s.// If p does not point into a heap object, it returns base == 0.//// If p points is an invalid heap pointer and debug.invalidptr != 0,// findObject panics.//// refBase and refOff optionally give the base address of the object// in which the pointer p was found and the byte offset at which it// was found. These are used for error reporting.//// It is nosplit so it is safe for p to be a pointer to the current goroutine's stack.// Since p is a uintptr, it would not be adjusted if the stack were to move.////go:nosplitfunc findObject(, , uintptr) ( uintptr, *mspan, uintptr) { = spanOf()// If s is nil, the virtual address has never been part of the heap. // This pointer may be to some mmap'd region, so we allow it.if == nil {if (GOARCH == "amd64" || GOARCH == "arm64") && == clobberdeadPtr && debug.invalidptr != 0 {// Crash if clobberdeadPtr is seen. Only on AMD64 and ARM64 for now, // as they are the only platform where compiler's clobberdead mode is // implemented. On these platforms clobberdeadPtr cannot be a valid address.badPointer(, , , ) }return }// If p is a bad pointer, it may not be in s's bounds. // // Check s.state to synchronize with span initialization // before checking other fields. See also spanOfHeap.if := .state.get(); != mSpanInUse || < .base() || >= .limit {// Pointers into stacks are also ok, the runtime manages these explicitly.if == mSpanManual {return }// The following ensures that we are rigorous about what data // structures hold valid pointers.ifdebug.invalidptr != 0 {badPointer(, , , ) }return } = .objIndex() = .base() + *.elemsizereturn}// reflect_verifyNotInHeapPtr reports whether converting the not-in-heap pointer into a unsafe.Pointer is ok.////go:linkname reflect_verifyNotInHeapPtr reflect.verifyNotInHeapPtrfunc reflect_verifyNotInHeapPtr( uintptr) bool {// Conversion to a pointer is ok as long as findObject above does not call badPointer. // Since we're already promised that p doesn't point into the heap, just disallow heap // pointers and the special clobbered pointer.returnspanOf() == nil && != clobberdeadPtr}const ptrBits = 8 * goarch.PtrSize// bulkBarrierBitmap executes write barriers for copying from [src,// src+size) to [dst, dst+size) using a 1-bit pointer bitmap. src is// assumed to start maskOffset bytes into the data covered by the// bitmap in bits (which may not be a multiple of 8).//// This is used by bulkBarrierPreWrite for writes to data and BSS.////go:nosplitfunc bulkBarrierBitmap(, , , uintptr, *uint8) { := / goarch.PtrSize = addb(, /8) := uint8(1) << ( % 8) := &getg().m.p.ptr().wbBuffor := uintptr(0); < ; += goarch.PtrSize {if == 0 { = addb(, 1)if * == 0 {// Skip 8 words. += 7 * goarch.PtrSizecontinue } = 1 }if *& != 0 { := (*uintptr)(unsafe.Pointer( + ))if == 0 { := .get1() [0] = * } else { := (*uintptr)(unsafe.Pointer( + )) := .get2() [0] = * [1] = * } } <<= 1 }}// typeBitsBulkBarrier executes a write barrier for every// pointer that would be copied from [src, src+size) to [dst,// dst+size) by a memmove using the type bitmap to locate those// pointer slots.//// The type typ must correspond exactly to [src, src+size) and [dst, dst+size).// dst, src, and size must be pointer-aligned.// The type typ must have a plain bitmap, not a GC program.// The only use of this function is in channel sends, and the// 64 kB channel element limit takes care of this for us.//// Must not be preempted because it typically runs right before memmove,// and the GC must observe them as an atomic action.//// Callers must perform cgo checks if goexperiment.CgoCheck2.////go:nosplitfunc typeBitsBulkBarrier( *_type, , , uintptr) {if == nil {throw("runtime: typeBitsBulkBarrier without type") }if .Size_ != {println("runtime: typeBitsBulkBarrier with type ", toRType().string(), " of size ", .Size_, " but memory size", )throw("runtime: invalid typeBitsBulkBarrier") }if .Kind_&kindGCProg != 0 {println("runtime: typeBitsBulkBarrier with type ", toRType().string(), " with GC prog")throw("runtime: invalid typeBitsBulkBarrier") }if !writeBarrier.enabled {return } := .GCData := &getg().m.p.ptr().wbBufvaruint32for := uintptr(0); < .PtrBytes; += goarch.PtrSize {if &(goarch.PtrSize*8-1) == 0 { = uint32(*) = addb(, 1) } else { = >> 1 }if &1 != 0 { := (*uintptr)(unsafe.Pointer( + )) := (*uintptr)(unsafe.Pointer( + )) := .get2() [0] = * [1] = * } }}// countAlloc returns the number of objects allocated in span s by// scanning the mark bitmap.func ( *mspan) () int { := 0 := divRoundUp(uintptr(.nelems), 8)// Iterate over each 8-byte chunk and count allocations // with an intrinsic. Note that newMarkBits guarantees that // gcmarkBits will be 8-byte aligned, so we don't have to // worry about edge cases, irrelevant bits will simply be zero.for := uintptr(0); < ; += 8 {// Extract 64 bits from the byte pointer and get a OnesCount. // Note that the unsafe cast here doesn't preserve endianness, // but that's OK. We only care about how many bits are 1, not // about the order we discover them in. := *(*uint64)(unsafe.Pointer(.gcmarkBits.bytep())) += sys.OnesCount64() }return}// Read the bytes starting at the aligned pointer p into a uintptr.// Read is little-endian.func readUintptr( *byte) uintptr { := *(*uintptr)(unsafe.Pointer())ifgoarch.BigEndian {ifgoarch.PtrSize == 8 {returnuintptr(sys.Bswap64(uint64())) }returnuintptr(sys.Bswap32(uint32())) }return}var debugPtrmask struct { lock mutex data *byte}// progToPointerMask returns the 1-bit pointer mask output by the GC program prog.// size the size of the region described by prog, in bytes.// The resulting bitvector will have no more than size/goarch.PtrSize bits.func progToPointerMask( *byte, uintptr) bitvector { := (/goarch.PtrSize + 7) / 8 := (*[1 << 30]byte)(persistentalloc(+1, 1, &memstats.buckhash_sys))[:+1] [len()-1] = 0xa1// overflow check sentinel = runGCProg(, &[0])if [len()-1] != 0xa1 {throw("progToPointerMask: overflow") }returnbitvector{int32(), &[0]}}// Packed GC pointer bitmaps, aka GC programs.//// For large types containing arrays, the type information has a// natural repetition that can be encoded to save space in the// binary and in the memory representation of the type information.//// The encoding is a simple Lempel-Ziv style bytecode machine// with the following instructions://// 00000000: stop// 0nnnnnnn: emit n bits copied from the next (n+7)/8 bytes// 10000000 n c: repeat the previous n bits c times; n, c are varints// 1nnnnnnn c: repeat the previous n bits c times; c is a varint// runGCProg returns the number of 1-bit entries written to memory.func runGCProg(, *byte) uintptr { := // Bits waiting to be written to memory.varuintptrvaruintptr := :for {// Flush accumulated full bytes. // The rest of the loop assumes that nbits <= 7.for ; >= 8; -= 8 { * = uint8() = add1() >>= 8 }// Process one instruction. := uintptr(*) = add1() := & 0x7Fif &0x80 == 0 {// Literal bits; n == 0 means end of program.if == 0 {// Program is over.break } := / 8for := uintptr(0); < ; ++ { |= uintptr(*) << = add1() * = uint8() = add1() >>= 8 }if %= 8; > 0 { |= uintptr(*) << = add1() += }continue }// Repeat. If n == 0, it is encoded in a varint in the next bytes.if == 0 {for := uint(0); ; += 7 { := uintptr(*) = add1() |= ( & 0x7F) << if &0x80 == 0 {break } } }// Count is encoded in a varint in the next bytes. := uintptr(0)for := uint(0); ; += 7 { := uintptr(*) = add1() |= ( & 0x7F) << if &0x80 == 0 {break } } *= // now total number of bits to copy// If the number of bits being repeated is small, load them // into a register and use that register for the entire loop // instead of repeatedly reading from memory. // Handling fewer than 8 bits here makes the general loop simpler. // The cutoff is goarch.PtrSize*8 - 7 to guarantee that when we add // the pattern to a bit buffer holding at most 7 bits (a partial byte) // it will not overflow. := const = goarch.PtrSize*8 - 7if <= {// Start with bits in output buffer. := := // If we need more bits, fetch them from memory. = subtract1()for < { <<= 8 |= uintptr(*) = subtract1() += 8 }// We started with the whole bit output buffer, // and then we loaded bits from whole bytes. // Either way, we might now have too many instead of too few. // Discard the extra.if > { >>= - = }// Replicate pattern to at most maxBits.if == 1 {// One bit being repeated. // If the bit is 1, make the pattern all 1s. // If the bit is 0, the pattern is already all 0s, // but we can claim that the number of bits // in the word is equal to the number we need (c), // because right shift of bits will zero fill.if == 1 { = 1<< - 1 = } else { = } } else { := := if + <= {// Double pattern until the whole uintptr is filled.for <= goarch.PtrSize*8 { |= << += }// Trim away incomplete copy of original pattern in high bits. // TODO(rsc): Replace with table lookup or loop on systems without divide? = / * &= 1<< - 1 = = } }// Add pattern to bit buffer and flush bit buffer, c/npattern times. // Since pattern contains >8 bits, there will be full bytes to flush // on each iteration.for ; >= ; -= { |= << += for >= 8 { * = uint8() = add1() >>= 8 -= 8 } }// Add final fragment to bit buffer.if > 0 { &= 1<< - 1 |= << += }continue }// Repeat; n too large to fit in a register. // Since nbits <= 7, we know the first few bytes of repeated data // are already written to memory. := - // n > nbits because n > maxBits and nbits <= 7// Leading src fragment. = subtractb(, (+7)/8)if := & 7; != 0 { |= uintptr(*) >> (8 - ) << = add1() += -= }// Main loop: load one byte, write another. // The bits are rotating through the bit buffer.for := / 8; > 0; -- { |= uintptr(*) << = add1() * = uint8() = add1() >>= 8 }// Final src fragment.if %= 8; > 0 { |= (uintptr(*) & (1<< - 1)) << += } }// Write any final bits out, using full-byte writes, even for the final byte. := (uintptr(unsafe.Pointer())-uintptr(unsafe.Pointer()))*8 + += - & 7for ; > 0; -= 8 { * = uint8() = add1() >>= 8 }return}// materializeGCProg allocates space for the (1-bit) pointer bitmask// for an object of size ptrdata. Then it fills that space with the// pointer bitmask specified by the program prog.// The bitmask starts at s.startAddr.// The result must be deallocated with dematerializeGCProg.func materializeGCProg( uintptr, *byte) *mspan {// Each word of ptrdata needs one bit in the bitmap. := divRoundUp(, 8*goarch.PtrSize)// Compute the number of pages needed for bitmapBytes. := divRoundUp(, pageSize) := mheap_.allocManual(, spanAllocPtrScalarBits)runGCProg(addb(, 4), (*byte)(unsafe.Pointer(.startAddr)))return}func dematerializeGCProg( *mspan) {mheap_.freeManual(, spanAllocPtrScalarBits)}func dumpGCProg( *byte) { := 0for { := * = add1()if == 0 {print("\t", , " end\n")break }if &0x80 == 0 {print("\t", , " lit ", , ":") := int(+7) / 8for := 0; < ; ++ {print(" ", hex(*)) = add1() }print("\n") += int() } else { := int( &^ 0x80)if == 0 {for := uint(0); ; += 7 { := * = add1() |= int(&0x7f) << if &0x80 == 0 {break } } } := 0for := uint(0); ; += 7 { := * = add1() |= int(&0x7f) << if &0x80 == 0 {break } }print("\t", , " repeat ", , " × ", , "\n") += * } }}// Testing.// reflect_gcbits returns the GC type info for x, for testing.// The result is the bitmap entries (0 or 1), one entry per byte.////go:linkname reflect_gcbits reflect.gcbitsfunc reflect_gcbits( any) []byte {returngetgcmask()}
The pages are generated with Goldsv0.6.9-preview. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds.