Source file src/runtime/mbitmap.go

Documentation: runtime

     1  // Copyright 2009 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  // Garbage collector: type and heap bitmaps.
     6  //
     7  // Stack, data, and bss bitmaps
     8  //
     9  // Stack frames and global variables in the data and bss sections are described
    10  // by 1-bit bitmaps in which 0 means uninteresting and 1 means live pointer
    11  // to be visited during GC. The bits in each byte are consumed starting with
    12  // the low bit: 1<<0, 1<<1, and so on.
    13  //
    14  // Heap bitmap
    15  //
    16  // The heap bitmap comprises 2 bits for each pointer-sized word in the heap,
    17  // stored in the heapArena metadata backing each heap arena.
    18  // That is, if ha is the heapArena for the arena starting a start,
    19  // then ha.bitmap[0] holds the 2-bit entries for the four words start
    20  // through start+3*ptrSize, ha.bitmap[1] holds the entries for
    21  // start+4*ptrSize through start+7*ptrSize, and so on.
    22  //
    23  // In each 2-bit entry, the lower bit holds the same information as in the 1-bit
    24  // bitmaps: 0 means uninteresting and 1 means live pointer to be visited during GC.
    25  // The meaning of the high bit depends on the position of the word being described
    26  // in its allocated object. In all words *except* the second word, the
    27  // high bit indicates that the object is still being described. In
    28  // these words, if a bit pair with a high bit 0 is encountered, the
    29  // low bit can also be assumed to be 0, and the object description is
    30  // over. This 00 is called the ``dead'' encoding: it signals that the
    31  // rest of the words in the object are uninteresting to the garbage
    32  // collector.
    33  //
    34  // In the second word, the high bit is the GC ``checkmarked'' bit (see below).
    35  //
    36  // The 2-bit entries are split when written into the byte, so that the top half
    37  // of the byte contains 4 high bits and the bottom half contains 4 low (pointer)
    38  // bits.
    39  // This form allows a copy from the 1-bit to the 4-bit form to keep the
    40  // pointer bits contiguous, instead of having to space them out.
    41  //
    42  // The code makes use of the fact that the zero value for a heap bitmap
    43  // has no live pointer bit set and is (depending on position), not used,
    44  // not checkmarked, and is the dead encoding.
    45  // These properties must be preserved when modifying the encoding.
    46  //
    47  // The bitmap for noscan spans is not maintained. Code must ensure
    48  // that an object is scannable before consulting its bitmap by
    49  // checking either the noscan bit in the span or by consulting its
    50  // type's information.
    51  //
    52  // Checkmarks
    53  //
    54  // In a concurrent garbage collector, one worries about failing to mark
    55  // a live object due to mutations without write barriers or bugs in the
    56  // collector implementation. As a sanity check, the GC has a 'checkmark'
    57  // mode that retraverses the object graph with the world stopped, to make
    58  // sure that everything that should be marked is marked.
    59  // In checkmark mode, in the heap bitmap, the high bit of the 2-bit entry
    60  // for the second word of the object holds the checkmark bit.
    61  // When not in checkmark mode, this bit is set to 1.
    62  //
    63  // The smallest possible allocation is 8 bytes. On a 32-bit machine, that
    64  // means every allocated object has two words, so there is room for the
    65  // checkmark bit. On a 64-bit machine, however, the 8-byte allocation is
    66  // just one word, so the second bit pair is not available for encoding the
    67  // checkmark. However, because non-pointer allocations are combined
    68  // into larger 16-byte (maxTinySize) allocations, a plain 8-byte allocation
    69  // must be a pointer, so the type bit in the first word is not actually needed.
    70  // It is still used in general, except in checkmark the type bit is repurposed
    71  // as the checkmark bit and then reinitialized (to 1) as the type bit when
    72  // finished.
    73  //
    74  
    75  package runtime
    76  
    77  import (
    78  	"runtime/internal/atomic"
    79  	"runtime/internal/sys"
    80  	"unsafe"
    81  )
    82  
    83  const (
    84  	bitPointer = 1 << 0
    85  	bitScan    = 1 << 4
    86  
    87  	heapBitsShift      = 1     // shift offset between successive bitPointer or bitScan entries
    88  	wordsPerBitmapByte = 8 / 2 // heap words described by one bitmap byte
    89  
    90  	// all scan/pointer bits in a byte
    91  	bitScanAll    = bitScan | bitScan<<heapBitsShift | bitScan<<(2*heapBitsShift) | bitScan<<(3*heapBitsShift)
    92  	bitPointerAll = bitPointer | bitPointer<<heapBitsShift | bitPointer<<(2*heapBitsShift) | bitPointer<<(3*heapBitsShift)
    93  )
    94  
    95  // addb returns the byte pointer p+n.
    96  //go:nowritebarrier
    97  //go:nosplit
    98  func addb(p *byte, n uintptr) *byte {
    99  	// Note: wrote out full expression instead of calling add(p, n)
   100  	// to reduce the number of temporaries generated by the
   101  	// compiler for this trivial expression during inlining.
   102  	return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) + n))
   103  }
   104  
   105  // subtractb returns the byte pointer p-n.
   106  //go:nowritebarrier
   107  //go:nosplit
   108  func subtractb(p *byte, n uintptr) *byte {
   109  	// Note: wrote out full expression instead of calling add(p, -n)
   110  	// to reduce the number of temporaries generated by the
   111  	// compiler for this trivial expression during inlining.
   112  	return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) - n))
   113  }
   114  
   115  // add1 returns the byte pointer p+1.
   116  //go:nowritebarrier
   117  //go:nosplit
   118  func add1(p *byte) *byte {
   119  	// Note: wrote out full expression instead of calling addb(p, 1)
   120  	// to reduce the number of temporaries generated by the
   121  	// compiler for this trivial expression during inlining.
   122  	return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) + 1))
   123  }
   124  
   125  // subtract1 returns the byte pointer p-1.
   126  //go:nowritebarrier
   127  //
   128  // nosplit because it is used during write barriers and must not be preempted.
   129  //go:nosplit
   130  func subtract1(p *byte) *byte {
   131  	// Note: wrote out full expression instead of calling subtractb(p, 1)
   132  	// to reduce the number of temporaries generated by the
   133  	// compiler for this trivial expression during inlining.
   134  	return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) - 1))
   135  }
   136  
   137  // heapBits provides access to the bitmap bits for a single heap word.
   138  // The methods on heapBits take value receivers so that the compiler
   139  // can more easily inline calls to those methods and registerize the
   140  // struct fields independently.
   141  type heapBits struct {
   142  	bitp  *uint8
   143  	shift uint32
   144  	arena uint32 // Index of heap arena containing bitp
   145  	last  *uint8 // Last byte arena's bitmap
   146  }
   147  
   148  // Make the compiler check that heapBits.arena is large enough to hold
   149  // the maximum arena frame number.
   150  var _ = heapBits{arena: (1<<heapAddrBits)/heapArenaBytes - 1}
   151  
   152  // markBits provides access to the mark bit for an object in the heap.
   153  // bytep points to the byte holding the mark bit.
   154  // mask is a byte with a single bit set that can be &ed with *bytep
   155  // to see if the bit has been set.
   156  // *m.byte&m.mask != 0 indicates the mark bit is set.
   157  // index can be used along with span information to generate
   158  // the address of the object in the heap.
   159  // We maintain one set of mark bits for allocation and one for
   160  // marking purposes.
   161  type markBits struct {
   162  	bytep *uint8
   163  	mask  uint8
   164  	index uintptr
   165  }
   166  
   167  //go:nosplit
   168  func (s *mspan) allocBitsForIndex(allocBitIndex uintptr) markBits {
   169  	bytep, mask := s.allocBits.bitp(allocBitIndex)
   170  	return markBits{bytep, mask, allocBitIndex}
   171  }
   172  
   173  // refillAllocCache takes 8 bytes s.allocBits starting at whichByte
   174  // and negates them so that ctz (count trailing zeros) instructions
   175  // can be used. It then places these 8 bytes into the cached 64 bit
   176  // s.allocCache.
   177  func (s *mspan) refillAllocCache(whichByte uintptr) {
   178  	bytes := (*[8]uint8)(unsafe.Pointer(s.allocBits.bytep(whichByte)))
   179  	aCache := uint64(0)
   180  	aCache |= uint64(bytes[0])
   181  	aCache |= uint64(bytes[1]) << (1 * 8)
   182  	aCache |= uint64(bytes[2]) << (2 * 8)
   183  	aCache |= uint64(bytes[3]) << (3 * 8)
   184  	aCache |= uint64(bytes[4]) << (4 * 8)
   185  	aCache |= uint64(bytes[5]) << (5 * 8)
   186  	aCache |= uint64(bytes[6]) << (6 * 8)
   187  	aCache |= uint64(bytes[7]) << (7 * 8)
   188  	s.allocCache = ^aCache
   189  }
   190  
   191  // nextFreeIndex returns the index of the next free object in s at
   192  // or after s.freeindex.
   193  // There are hardware instructions that can be used to make this
   194  // faster if profiling warrants it.
   195  func (s *mspan) nextFreeIndex() uintptr {
   196  	sfreeindex := s.freeindex
   197  	snelems := s.nelems
   198  	if sfreeindex == snelems {
   199  		return sfreeindex
   200  	}
   201  	if sfreeindex > snelems {
   202  		throw("s.freeindex > s.nelems")
   203  	}
   204  
   205  	aCache := s.allocCache
   206  
   207  	bitIndex := sys.Ctz64(aCache)
   208  	for bitIndex == 64 {
   209  		// Move index to start of next cached bits.
   210  		sfreeindex = (sfreeindex + 64) &^ (64 - 1)
   211  		if sfreeindex >= snelems {
   212  			s.freeindex = snelems
   213  			return snelems
   214  		}
   215  		whichByte := sfreeindex / 8
   216  		// Refill s.allocCache with the next 64 alloc bits.
   217  		s.refillAllocCache(whichByte)
   218  		aCache = s.allocCache
   219  		bitIndex = sys.Ctz64(aCache)
   220  		// nothing available in cached bits
   221  		// grab the next 8 bytes and try again.
   222  	}
   223  	result := sfreeindex + uintptr(bitIndex)
   224  	if result >= snelems {
   225  		s.freeindex = snelems
   226  		return snelems
   227  	}
   228  
   229  	s.allocCache >>= uint(bitIndex + 1)
   230  	sfreeindex = result + 1
   231  
   232  	if sfreeindex%64 == 0 && sfreeindex != snelems {
   233  		// We just incremented s.freeindex so it isn't 0.
   234  		// As each 1 in s.allocCache was encountered and used for allocation
   235  		// it was shifted away. At this point s.allocCache contains all 0s.
   236  		// Refill s.allocCache so that it corresponds
   237  		// to the bits at s.allocBits starting at s.freeindex.
   238  		whichByte := sfreeindex / 8
   239  		s.refillAllocCache(whichByte)
   240  	}
   241  	s.freeindex = sfreeindex
   242  	return result
   243  }
   244  
   245  // isFree reports whether the index'th object in s is unallocated.
   246  func (s *mspan) isFree(index uintptr) bool {
   247  	if index < s.freeindex {
   248  		return false
   249  	}
   250  	bytep, mask := s.allocBits.bitp(index)
   251  	return *bytep&mask == 0
   252  }
   253  
   254  func (s *mspan) objIndex(p uintptr) uintptr {
   255  	byteOffset := p - s.base()
   256  	if byteOffset == 0 {
   257  		return 0
   258  	}
   259  	if s.baseMask != 0 {
   260  		// s.baseMask is non-0, elemsize is a power of two, so shift by s.divShift
   261  		return byteOffset >> s.divShift
   262  	}
   263  	return uintptr(((uint64(byteOffset) >> s.divShift) * uint64(s.divMul)) >> s.divShift2)
   264  }
   265  
   266  func markBitsForAddr(p uintptr) markBits {
   267  	s := spanOf(p)
   268  	objIndex := s.objIndex(p)
   269  	return s.markBitsForIndex(objIndex)
   270  }
   271  
   272  func (s *mspan) markBitsForIndex(objIndex uintptr) markBits {
   273  	bytep, mask := s.gcmarkBits.bitp(objIndex)
   274  	return markBits{bytep, mask, objIndex}
   275  }
   276  
   277  func (s *mspan) markBitsForBase() markBits {
   278  	return markBits{(*uint8)(s.gcmarkBits), uint8(1), 0}
   279  }
   280  
   281  // isMarked reports whether mark bit m is set.
   282  func (m markBits) isMarked() bool {
   283  	return *m.bytep&m.mask != 0
   284  }
   285  
   286  // setMarked sets the marked bit in the markbits, atomically.
   287  func (m markBits) setMarked() {
   288  	// Might be racing with other updates, so use atomic update always.
   289  	// We used to be clever here and use a non-atomic update in certain
   290  	// cases, but it's not worth the risk.
   291  	atomic.Or8(m.bytep, m.mask)
   292  }
   293  
   294  // setMarkedNonAtomic sets the marked bit in the markbits, non-atomically.
   295  func (m markBits) setMarkedNonAtomic() {
   296  	*m.bytep |= m.mask
   297  }
   298  
   299  // clearMarked clears the marked bit in the markbits, atomically.
   300  func (m markBits) clearMarked() {
   301  	// Might be racing with other updates, so use atomic update always.
   302  	// We used to be clever here and use a non-atomic update in certain
   303  	// cases, but it's not worth the risk.
   304  	atomic.And8(m.bytep, ^m.mask)
   305  }
   306  
   307  // markBitsForSpan returns the markBits for the span base address base.
   308  func markBitsForSpan(base uintptr) (mbits markBits) {
   309  	mbits = markBitsForAddr(base)
   310  	if mbits.mask != 1 {
   311  		throw("markBitsForSpan: unaligned start")
   312  	}
   313  	return mbits
   314  }
   315  
   316  // advance advances the markBits to the next object in the span.
   317  func (m *markBits) advance() {
   318  	if m.mask == 1<<7 {
   319  		m.bytep = (*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(m.bytep)) + 1))
   320  		m.mask = 1
   321  	} else {
   322  		m.mask = m.mask << 1
   323  	}
   324  	m.index++
   325  }
   326  
   327  // heapBitsForAddr returns the heapBits for the address addr.
   328  // The caller must ensure addr is in an allocated span.
   329  // In particular, be careful not to point past the end of an object.
   330  //
   331  // nosplit because it is used during write barriers and must not be preempted.
   332  //go:nosplit
   333  func heapBitsForAddr(addr uintptr) (h heapBits) {
   334  	// 2 bits per word, 4 pairs per byte, and a mask is hard coded.
   335  	arena := arenaIndex(addr)
   336  	ha := mheap_.arenas[arena.l1()][arena.l2()]
   337  	// The compiler uses a load for nil checking ha, but in this
   338  	// case we'll almost never hit that cache line again, so it
   339  	// makes more sense to do a value check.
   340  	if ha == nil {
   341  		// addr is not in the heap. Return nil heapBits, which
   342  		// we expect to crash in the caller.
   343  		return
   344  	}
   345  	h.bitp = &ha.bitmap[(addr/(sys.PtrSize*4))%heapArenaBitmapBytes]
   346  	h.shift = uint32((addr / sys.PtrSize) & 3)
   347  	h.arena = uint32(arena)
   348  	h.last = &ha.bitmap[len(ha.bitmap)-1]
   349  	return
   350  }
   351  
   352  // findObject returns the base address for the heap object containing
   353  // the address p, the object's span, and the index of the object in s.
   354  // If p does not point into a heap object, it returns base == 0.
   355  //
   356  // If p points is an invalid heap pointer and debug.invalidptr != 0,
   357  // findObject panics.
   358  //
   359  // refBase and refOff optionally give the base address of the object
   360  // in which the pointer p was found and the byte offset at which it
   361  // was found. These are used for error reporting.
   362  func findObject(p, refBase, refOff uintptr) (base uintptr, s *mspan, objIndex uintptr) {
   363  	s = spanOf(p)
   364  	// If p is a bad pointer, it may not be in s's bounds.
   365  	if s == nil || p < s.base() || p >= s.limit || s.state != mSpanInUse {
   366  		if s == nil || s.state == mSpanManual {
   367  			// If s is nil, the virtual address has never been part of the heap.
   368  			// This pointer may be to some mmap'd region, so we allow it.
   369  			// Pointers into stacks are also ok, the runtime manages these explicitly.
   370  			return
   371  		}
   372  
   373  		// The following ensures that we are rigorous about what data
   374  		// structures hold valid pointers.
   375  		if debug.invalidptr != 0 {
   376  			// Typically this indicates an incorrect use
   377  			// of unsafe or cgo to store a bad pointer in
   378  			// the Go heap. It may also indicate a runtime
   379  			// bug.
   380  			//
   381  			// TODO(austin): We could be more aggressive
   382  			// and detect pointers to unallocated objects
   383  			// in allocated spans.
   384  			printlock()
   385  			print("runtime: pointer ", hex(p))
   386  			if s.state != mSpanInUse {
   387  				print(" to unallocated span")
   388  			} else {
   389  				print(" to unused region of span")
   390  			}
   391  			print(" span.base()=", hex(s.base()), " span.limit=", hex(s.limit), " span.state=", s.state, "\n")
   392  			if refBase != 0 {
   393  				print("runtime: found in object at *(", hex(refBase), "+", hex(refOff), ")\n")
   394  				gcDumpObject("object", refBase, refOff)
   395  			}
   396  			getg().m.traceback = 2
   397  			throw("found bad pointer in Go heap (incorrect use of unsafe or cgo?)")
   398  		}
   399  		return
   400  	}
   401  	// If this span holds object of a power of 2 size, just mask off the bits to
   402  	// the interior of the object. Otherwise use the size to get the base.
   403  	if s.baseMask != 0 {
   404  		// optimize for power of 2 sized objects.
   405  		base = s.base()
   406  		base = base + (p-base)&uintptr(s.baseMask)
   407  		objIndex = (base - s.base()) >> s.divShift
   408  		// base = p & s.baseMask is faster for small spans,
   409  		// but doesn't work for large spans.
   410  		// Overall, it's faster to use the more general computation above.
   411  	} else {
   412  		base = s.base()
   413  		if p-base >= s.elemsize {
   414  			// n := (p - base) / s.elemsize, using division by multiplication
   415  			objIndex = uintptr(p-base) >> s.divShift * uintptr(s.divMul) >> s.divShift2
   416  			base += objIndex * s.elemsize
   417  		}
   418  	}
   419  	return
   420  }
   421  
   422  // next returns the heapBits describing the next pointer-sized word in memory.
   423  // That is, if h describes address p, h.next() describes p+ptrSize.
   424  // Note that next does not modify h. The caller must record the result.
   425  //
   426  // nosplit because it is used during write barriers and must not be preempted.
   427  //go:nosplit
   428  func (h heapBits) next() heapBits {
   429  	if h.shift < 3*heapBitsShift {
   430  		h.shift += heapBitsShift
   431  	} else if h.bitp != h.last {
   432  		h.bitp, h.shift = add1(h.bitp), 0
   433  	} else {
   434  		// Move to the next arena.
   435  		return h.nextArena()
   436  	}
   437  	return h
   438  }
   439  
   440  // nextArena advances h to the beginning of the next heap arena.
   441  //
   442  // This is a slow-path helper to next. gc's inliner knows that
   443  // heapBits.next can be inlined even though it calls this. This is
   444  // marked noinline so it doesn't get inlined into next and cause next
   445  // to be too big to inline.
   446  //
   447  //go:nosplit
   448  //go:noinline
   449  func (h heapBits) nextArena() heapBits {
   450  	h.arena++
   451  	ai := arenaIdx(h.arena)
   452  	l2 := mheap_.arenas[ai.l1()]
   453  	if l2 == nil {
   454  		// We just passed the end of the object, which
   455  		// was also the end of the heap. Poison h. It
   456  		// should never be dereferenced at this point.
   457  		return heapBits{}
   458  	}
   459  	ha := l2[ai.l2()]
   460  	if ha == nil {
   461  		return heapBits{}
   462  	}
   463  	h.bitp, h.shift = &ha.bitmap[0], 0
   464  	h.last = &ha.bitmap[len(ha.bitmap)-1]
   465  	return h
   466  }
   467  
   468  // forward returns the heapBits describing n pointer-sized words ahead of h in memory.
   469  // That is, if h describes address p, h.forward(n) describes p+n*ptrSize.
   470  // h.forward(1) is equivalent to h.next(), just slower.
   471  // Note that forward does not modify h. The caller must record the result.
   472  // bits returns the heap bits for the current word.
   473  //go:nosplit
   474  func (h heapBits) forward(n uintptr) heapBits {
   475  	n += uintptr(h.shift) / heapBitsShift
   476  	nbitp := uintptr(unsafe.Pointer(h.bitp)) + n/4
   477  	h.shift = uint32(n%4) * heapBitsShift
   478  	if nbitp <= uintptr(unsafe.Pointer(h.last)) {
   479  		h.bitp = (*uint8)(unsafe.Pointer(nbitp))
   480  		return h
   481  	}
   482  
   483  	// We're in a new heap arena.
   484  	past := nbitp - (uintptr(unsafe.Pointer(h.last)) + 1)
   485  	h.arena += 1 + uint32(past/heapArenaBitmapBytes)
   486  	ai := arenaIdx(h.arena)
   487  	if l2 := mheap_.arenas[ai.l1()]; l2 != nil && l2[ai.l2()] != nil {
   488  		a := l2[ai.l2()]
   489  		h.bitp = &a.bitmap[past%heapArenaBitmapBytes]
   490  		h.last = &a.bitmap[len(a.bitmap)-1]
   491  	} else {
   492  		h.bitp, h.last = nil, nil
   493  	}
   494  	return h
   495  }
   496  
   497  // forwardOrBoundary is like forward, but stops at boundaries between
   498  // contiguous sections of the bitmap. It returns the number of words
   499  // advanced over, which will be <= n.
   500  func (h heapBits) forwardOrBoundary(n uintptr) (heapBits, uintptr) {
   501  	maxn := 4 * ((uintptr(unsafe.Pointer(h.last)) + 1) - uintptr(unsafe.Pointer(h.bitp)))
   502  	if n > maxn {
   503  		n = maxn
   504  	}
   505  	return h.forward(n), n
   506  }
   507  
   508  // The caller can test morePointers and isPointer by &-ing with bitScan and bitPointer.
   509  // The result includes in its higher bits the bits for subsequent words
   510  // described by the same bitmap byte.
   511  //
   512  // nosplit because it is used during write barriers and must not be preempted.
   513  //go:nosplit
   514  func (h heapBits) bits() uint32 {
   515  	// The (shift & 31) eliminates a test and conditional branch
   516  	// from the generated code.
   517  	return uint32(*h.bitp) >> (h.shift & 31)
   518  }
   519  
   520  // morePointers reports whether this word and all remaining words in this object
   521  // are scalars.
   522  // h must not describe the second word of the object.
   523  func (h heapBits) morePointers() bool {
   524  	return h.bits()&bitScan != 0
   525  }
   526  
   527  // isPointer reports whether the heap bits describe a pointer word.
   528  //
   529  // nosplit because it is used during write barriers and must not be preempted.
   530  //go:nosplit
   531  func (h heapBits) isPointer() bool {
   532  	return h.bits()&bitPointer != 0
   533  }
   534  
   535  // isCheckmarked reports whether the heap bits have the checkmarked bit set.
   536  // It must be told how large the object at h is, because the encoding of the
   537  // checkmark bit varies by size.
   538  // h must describe the initial word of the object.
   539  func (h heapBits) isCheckmarked(size uintptr) bool {
   540  	if size == sys.PtrSize {
   541  		return (*h.bitp>>h.shift)&bitPointer != 0
   542  	}
   543  	// All multiword objects are 2-word aligned,
   544  	// so we know that the initial word's 2-bit pair
   545  	// and the second word's 2-bit pair are in the
   546  	// same heap bitmap byte, *h.bitp.
   547  	return (*h.bitp>>(heapBitsShift+h.shift))&bitScan != 0
   548  }
   549  
   550  // setCheckmarked sets the checkmarked bit.
   551  // It must be told how large the object at h is, because the encoding of the
   552  // checkmark bit varies by size.
   553  // h must describe the initial word of the object.
   554  func (h heapBits) setCheckmarked(size uintptr) {
   555  	if size == sys.PtrSize {
   556  		atomic.Or8(h.bitp, bitPointer<<h.shift)
   557  		return
   558  	}
   559  	atomic.Or8(h.bitp, bitScan<<(heapBitsShift+h.shift))
   560  }
   561  
   562  // bulkBarrierPreWrite executes a write barrier
   563  // for every pointer slot in the memory range [src, src+size),
   564  // using pointer/scalar information from [dst, dst+size).
   565  // This executes the write barriers necessary before a memmove.
   566  // src, dst, and size must be pointer-aligned.
   567  // The range [dst, dst+size) must lie within a single object.
   568  // It does not perform the actual writes.
   569  //
   570  // As a special case, src == 0 indicates that this is being used for a
   571  // memclr. bulkBarrierPreWrite will pass 0 for the src of each write
   572  // barrier.
   573  //
   574  // Callers should call bulkBarrierPreWrite immediately before
   575  // calling memmove(dst, src, size). This function is marked nosplit
   576  // to avoid being preempted; the GC must not stop the goroutine
   577  // between the memmove and the execution of the barriers.
   578  // The caller is also responsible for cgo pointer checks if this
   579  // may be writing Go pointers into non-Go memory.
   580  //
   581  // The pointer bitmap is not maintained for allocations containing
   582  // no pointers at all; any caller of bulkBarrierPreWrite must first
   583  // make sure the underlying allocation contains pointers, usually
   584  // by checking typ.kind&kindNoPointers.
   585  //
   586  // Callers must perform cgo checks if writeBarrier.cgo.
   587  //
   588  //go:nosplit
   589  func bulkBarrierPreWrite(dst, src, size uintptr) {
   590  	if (dst|src|size)&(sys.PtrSize-1) != 0 {
   591  		throw("bulkBarrierPreWrite: unaligned arguments")
   592  	}
   593  	if !writeBarrier.needed {
   594  		return
   595  	}
   596  	if s := spanOf(dst); s == nil {
   597  		// If dst is a global, use the data or BSS bitmaps to
   598  		// execute write barriers.
   599  		for _, datap := range activeModules() {
   600  			if datap.data <= dst && dst < datap.edata {
   601  				bulkBarrierBitmap(dst, src, size, dst-datap.data, datap.gcdatamask.bytedata)
   602  				return
   603  			}
   604  		}
   605  		for _, datap := range activeModules() {
   606  			if datap.bss <= dst && dst < datap.ebss {
   607  				bulkBarrierBitmap(dst, src, size, dst-datap.bss, datap.gcbssmask.bytedata)
   608  				return
   609  			}
   610  		}
   611  		return
   612  	} else if s.state != mSpanInUse || dst < s.base() || s.limit <= dst {
   613  		// dst was heap memory at some point, but isn't now.
   614  		// It can't be a global. It must be either our stack,
   615  		// or in the case of direct channel sends, it could be
   616  		// another stack. Either way, no need for barriers.
   617  		// This will also catch if dst is in a freed span,
   618  		// though that should never have.
   619  		return
   620  	}
   621  
   622  	buf := &getg().m.p.ptr().wbBuf
   623  	h := heapBitsForAddr(dst)
   624  	if src == 0 {
   625  		for i := uintptr(0); i < size; i += sys.PtrSize {
   626  			if h.isPointer() {
   627  				dstx := (*uintptr)(unsafe.Pointer(dst + i))
   628  				if !buf.putFast(*dstx, 0) {
   629  					wbBufFlush(nil, 0)
   630  				}
   631  			}
   632  			h = h.next()
   633  		}
   634  	} else {
   635  		for i := uintptr(0); i < size; i += sys.PtrSize {
   636  			if h.isPointer() {
   637  				dstx := (*uintptr)(unsafe.Pointer(dst + i))
   638  				srcx := (*uintptr)(unsafe.Pointer(src + i))
   639  				if !buf.putFast(*dstx, *srcx) {
   640  					wbBufFlush(nil, 0)
   641  				}
   642  			}
   643  			h = h.next()
   644  		}
   645  	}
   646  }
   647  
   648  // bulkBarrierPreWriteSrcOnly is like bulkBarrierPreWrite but
   649  // does not execute write barriers for [dst, dst+size).
   650  //
   651  // In addition to the requirements of bulkBarrierPreWrite
   652  // callers need to ensure [dst, dst+size) is zeroed.
   653  //
   654  // This is used for special cases where e.g. dst was just
   655  // created and zeroed with malloc.
   656  //go:nosplit
   657  func bulkBarrierPreWriteSrcOnly(dst, src, size uintptr) {
   658  	if (dst|src|size)&(sys.PtrSize-1) != 0 {
   659  		throw("bulkBarrierPreWrite: unaligned arguments")
   660  	}
   661  	if !writeBarrier.needed {
   662  		return
   663  	}
   664  	buf := &getg().m.p.ptr().wbBuf
   665  	h := heapBitsForAddr(dst)
   666  	for i := uintptr(0); i < size; i += sys.PtrSize {
   667  		if h.isPointer() {
   668  			srcx := (*uintptr)(unsafe.Pointer(src + i))
   669  			if !buf.putFast(0, *srcx) {
   670  				wbBufFlush(nil, 0)
   671  			}
   672  		}
   673  		h = h.next()
   674  	}
   675  }
   676  
   677  // bulkBarrierBitmap executes write barriers for copying from [src,
   678  // src+size) to [dst, dst+size) using a 1-bit pointer bitmap. src is
   679  // assumed to start maskOffset bytes into the data covered by the
   680  // bitmap in bits (which may not be a multiple of 8).
   681  //
   682  // This is used by bulkBarrierPreWrite for writes to data and BSS.
   683  //
   684  //go:nosplit
   685  func bulkBarrierBitmap(dst, src, size, maskOffset uintptr, bits *uint8) {
   686  	word := maskOffset / sys.PtrSize
   687  	bits = addb(bits, word/8)
   688  	mask := uint8(1) << (word % 8)
   689  
   690  	buf := &getg().m.p.ptr().wbBuf
   691  	for i := uintptr(0); i < size; i += sys.PtrSize {
   692  		if mask == 0 {
   693  			bits = addb(bits, 1)
   694  			if *bits == 0 {
   695  				// Skip 8 words.
   696  				i += 7 * sys.PtrSize
   697  				continue
   698  			}
   699  			mask = 1
   700  		}
   701  		if *bits&mask != 0 {
   702  			dstx := (*uintptr)(unsafe.Pointer(dst + i))
   703  			if src == 0 {
   704  				if !buf.putFast(*dstx, 0) {
   705  					wbBufFlush(nil, 0)
   706  				}
   707  			} else {
   708  				srcx := (*uintptr)(unsafe.Pointer(src + i))
   709  				if !buf.putFast(*dstx, *srcx) {
   710  					wbBufFlush(nil, 0)
   711  				}
   712  			}
   713  		}
   714  		mask <<= 1
   715  	}
   716  }
   717  
   718  // typeBitsBulkBarrier executes a write barrier for every
   719  // pointer that would be copied from [src, src+size) to [dst,
   720  // dst+size) by a memmove using the type bitmap to locate those
   721  // pointer slots.
   722  //
   723  // The type typ must correspond exactly to [src, src+size) and [dst, dst+size).
   724  // dst, src, and size must be pointer-aligned.
   725  // The type typ must have a plain bitmap, not a GC program.
   726  // The only use of this function is in channel sends, and the
   727  // 64 kB channel element limit takes care of this for us.
   728  //
   729  // Must not be preempted because it typically runs right before memmove,
   730  // and the GC must observe them as an atomic action.
   731  //
   732  // Callers must perform cgo checks if writeBarrier.cgo.
   733  //
   734  //go:nosplit
   735  func typeBitsBulkBarrier(typ *_type, dst, src, size uintptr) {
   736  	if typ == nil {
   737  		throw("runtime: typeBitsBulkBarrier without type")
   738  	}
   739  	if typ.size != size {
   740  		println("runtime: typeBitsBulkBarrier with type ", typ.string(), " of size ", typ.size, " but memory size", size)
   741  		throw("runtime: invalid typeBitsBulkBarrier")
   742  	}
   743  	if typ.kind&kindGCProg != 0 {
   744  		println("runtime: typeBitsBulkBarrier with type ", typ.string(), " with GC prog")
   745  		throw("runtime: invalid typeBitsBulkBarrier")
   746  	}
   747  	if !writeBarrier.needed {
   748  		return
   749  	}
   750  	ptrmask := typ.gcdata
   751  	buf := &getg().m.p.ptr().wbBuf
   752  	var bits uint32
   753  	for i := uintptr(0); i < typ.ptrdata; i += sys.PtrSize {
   754  		if i&(sys.PtrSize*8-1) == 0 {
   755  			bits = uint32(*ptrmask)
   756  			ptrmask = addb(ptrmask, 1)
   757  		} else {
   758  			bits = bits >> 1
   759  		}
   760  		if bits&1 != 0 {
   761  			dstx := (*uintptr)(unsafe.Pointer(dst + i))
   762  			srcx := (*uintptr)(unsafe.Pointer(src + i))
   763  			if !buf.putFast(*dstx, *srcx) {
   764  				wbBufFlush(nil, 0)
   765  			}
   766  		}
   767  	}
   768  }
   769  
   770  // The methods operating on spans all require that h has been returned
   771  // by heapBitsForSpan and that size, n, total are the span layout description
   772  // returned by the mspan's layout method.
   773  // If total > size*n, it means that there is extra leftover memory in the span,
   774  // usually due to rounding.
   775  //
   776  // TODO(rsc): Perhaps introduce a different heapBitsSpan type.
   777  
   778  // initSpan initializes the heap bitmap for a span.
   779  // It clears all checkmark bits.
   780  // If this is a span of pointer-sized objects, it initializes all
   781  // words to pointer/scan.
   782  // Otherwise, it initializes all words to scalar/dead.
   783  func (h heapBits) initSpan(s *mspan) {
   784  	size, n, total := s.layout()
   785  
   786  	// Init the markbit structures
   787  	s.freeindex = 0
   788  	s.allocCache = ^uint64(0) // all 1s indicating all free.
   789  	s.nelems = n
   790  	s.allocBits = nil
   791  	s.gcmarkBits = nil
   792  	s.gcmarkBits = newMarkBits(s.nelems)
   793  	s.allocBits = newAllocBits(s.nelems)
   794  
   795  	// Clear bits corresponding to objects.
   796  	nw := total / sys.PtrSize
   797  	if nw%wordsPerBitmapByte != 0 {
   798  		throw("initSpan: unaligned length")
   799  	}
   800  	if h.shift != 0 {
   801  		throw("initSpan: unaligned base")
   802  	}
   803  	for nw > 0 {
   804  		hNext, anw := h.forwardOrBoundary(nw)
   805  		nbyte := anw / wordsPerBitmapByte
   806  		if sys.PtrSize == 8 && size == sys.PtrSize {
   807  			bitp := h.bitp
   808  			for i := uintptr(0); i < nbyte; i++ {
   809  				*bitp = bitPointerAll | bitScanAll
   810  				bitp = add1(bitp)
   811  			}
   812  		} else {
   813  			memclrNoHeapPointers(unsafe.Pointer(h.bitp), nbyte)
   814  		}
   815  		h = hNext
   816  		nw -= anw
   817  	}
   818  }
   819  
   820  // initCheckmarkSpan initializes a span for being checkmarked.
   821  // It clears the checkmark bits, which are set to 1 in normal operation.
   822  func (h heapBits) initCheckmarkSpan(size, n, total uintptr) {
   823  	// The ptrSize == 8 is a compile-time constant false on 32-bit and eliminates this code entirely.
   824  	if sys.PtrSize == 8 && size == sys.PtrSize {
   825  		// Checkmark bit is type bit, bottom bit of every 2-bit entry.
   826  		// Only possible on 64-bit system, since minimum size is 8.
   827  		// Must clear type bit (checkmark bit) of every word.
   828  		// The type bit is the lower of every two-bit pair.
   829  		for i := uintptr(0); i < n; i += wordsPerBitmapByte {
   830  			*h.bitp &^= bitPointerAll
   831  			h = h.forward(wordsPerBitmapByte)
   832  		}
   833  		return
   834  	}
   835  	for i := uintptr(0); i < n; i++ {
   836  		*h.bitp &^= bitScan << (heapBitsShift + h.shift)
   837  		h = h.forward(size / sys.PtrSize)
   838  	}
   839  }
   840  
   841  // clearCheckmarkSpan undoes all the checkmarking in a span.
   842  // The actual checkmark bits are ignored, so the only work to do
   843  // is to fix the pointer bits. (Pointer bits are ignored by scanobject
   844  // but consulted by typedmemmove.)
   845  func (h heapBits) clearCheckmarkSpan(size, n, total uintptr) {
   846  	// The ptrSize == 8 is a compile-time constant false on 32-bit and eliminates this code entirely.
   847  	if sys.PtrSize == 8 && size == sys.PtrSize {
   848  		// Checkmark bit is type bit, bottom bit of every 2-bit entry.
   849  		// Only possible on 64-bit system, since minimum size is 8.
   850  		// Must clear type bit (checkmark bit) of every word.
   851  		// The type bit is the lower of every two-bit pair.
   852  		for i := uintptr(0); i < n; i += wordsPerBitmapByte {
   853  			*h.bitp |= bitPointerAll
   854  			h = h.forward(wordsPerBitmapByte)
   855  		}
   856  	}
   857  }
   858  
   859  // oneBitCount is indexed by byte and produces the
   860  // number of 1 bits in that byte. For example 128 has 1 bit set
   861  // and oneBitCount[128] will holds 1.
   862  var oneBitCount = [256]uint8{
   863  	0, 1, 1, 2, 1, 2, 2, 3,
   864  	1, 2, 2, 3, 2, 3, 3, 4,
   865  	1, 2, 2, 3, 2, 3, 3, 4,
   866  	2, 3, 3, 4, 3, 4, 4, 5,
   867  	1, 2, 2, 3, 2, 3, 3, 4,
   868  	2, 3, 3, 4, 3, 4, 4, 5,
   869  	2, 3, 3, 4, 3, 4, 4, 5,
   870  	3, 4, 4, 5, 4, 5, 5, 6,
   871  	1, 2, 2, 3, 2, 3, 3, 4,
   872  	2, 3, 3, 4, 3, 4, 4, 5,
   873  	2, 3, 3, 4, 3, 4, 4, 5,
   874  	3, 4, 4, 5, 4, 5, 5, 6,
   875  	2, 3, 3, 4, 3, 4, 4, 5,
   876  	3, 4, 4, 5, 4, 5, 5, 6,
   877  	3, 4, 4, 5, 4, 5, 5, 6,
   878  	4, 5, 5, 6, 5, 6, 6, 7,
   879  	1, 2, 2, 3, 2, 3, 3, 4,
   880  	2, 3, 3, 4, 3, 4, 4, 5,
   881  	2, 3, 3, 4, 3, 4, 4, 5,
   882  	3, 4, 4, 5, 4, 5, 5, 6,
   883  	2, 3, 3, 4, 3, 4, 4, 5,
   884  	3, 4, 4, 5, 4, 5, 5, 6,
   885  	3, 4, 4, 5, 4, 5, 5, 6,
   886  	4, 5, 5, 6, 5, 6, 6, 7,
   887  	2, 3, 3, 4, 3, 4, 4, 5,
   888  	3, 4, 4, 5, 4, 5, 5, 6,
   889  	3, 4, 4, 5, 4, 5, 5, 6,
   890  	4, 5, 5, 6, 5, 6, 6, 7,
   891  	3, 4, 4, 5, 4, 5, 5, 6,
   892  	4, 5, 5, 6, 5, 6, 6, 7,
   893  	4, 5, 5, 6, 5, 6, 6, 7,
   894  	5, 6, 6, 7, 6, 7, 7, 8}
   895  
   896  // countAlloc returns the number of objects allocated in span s by
   897  // scanning the allocation bitmap.
   898  // TODO:(rlh) Use popcount intrinsic.
   899  func (s *mspan) countAlloc() int {
   900  	count := 0
   901  	maxIndex := s.nelems / 8
   902  	for i := uintptr(0); i < maxIndex; i++ {
   903  		mrkBits := *s.gcmarkBits.bytep(i)
   904  		count += int(oneBitCount[mrkBits])
   905  	}
   906  	if bitsInLastByte := s.nelems % 8; bitsInLastByte != 0 {
   907  		mrkBits := *s.gcmarkBits.bytep(maxIndex)
   908  		mask := uint8((1 << bitsInLastByte) - 1)
   909  		bits := mrkBits & mask
   910  		count += int(oneBitCount[bits])
   911  	}
   912  	return count
   913  }
   914  
   915  // heapBitsSetType records that the new allocation [x, x+size)
   916  // holds in [x, x+dataSize) one or more values of type typ.
   917  // (The number of values is given by dataSize / typ.size.)
   918  // If dataSize < size, the fragment [x+dataSize, x+size) is
   919  // recorded as non-pointer data.
   920  // It is known that the type has pointers somewhere;
   921  // malloc does not call heapBitsSetType when there are no pointers,
   922  // because all free objects are marked as noscan during
   923  // heapBitsSweepSpan.
   924  //
   925  // There can only be one allocation from a given span active at a time,
   926  // and the bitmap for a span always falls on byte boundaries,
   927  // so there are no write-write races for access to the heap bitmap.
   928  // Hence, heapBitsSetType can access the bitmap without atomics.
   929  //
   930  // There can be read-write races between heapBitsSetType and things
   931  // that read the heap bitmap like scanobject. However, since
   932  // heapBitsSetType is only used for objects that have not yet been
   933  // made reachable, readers will ignore bits being modified by this
   934  // function. This does mean this function cannot transiently modify
   935  // bits that belong to neighboring objects. Also, on weakly-ordered
   936  // machines, callers must execute a store/store (publication) barrier
   937  // between calling this function and making the object reachable.
   938  func heapBitsSetType(x, size, dataSize uintptr, typ *_type) {
   939  	const doubleCheck = false // slow but helpful; enable to test modifications to this code
   940  
   941  	// dataSize is always size rounded up to the next malloc size class,
   942  	// except in the case of allocating a defer block, in which case
   943  	// size is sizeof(_defer{}) (at least 6 words) and dataSize may be
   944  	// arbitrarily larger.
   945  	//
   946  	// The checks for size == sys.PtrSize and size == 2*sys.PtrSize can therefore
   947  	// assume that dataSize == size without checking it explicitly.
   948  
   949  	if sys.PtrSize == 8 && size == sys.PtrSize {
   950  		// It's one word and it has pointers, it must be a pointer.
   951  		// Since all allocated one-word objects are pointers
   952  		// (non-pointers are aggregated into tinySize allocations),
   953  		// initSpan sets the pointer bits for us. Nothing to do here.
   954  		if doubleCheck {
   955  			h := heapBitsForAddr(x)
   956  			if !h.isPointer() {
   957  				throw("heapBitsSetType: pointer bit missing")
   958  			}
   959  			if !h.morePointers() {
   960  				throw("heapBitsSetType: scan bit missing")
   961  			}
   962  		}
   963  		return
   964  	}
   965  
   966  	h := heapBitsForAddr(x)
   967  	ptrmask := typ.gcdata // start of 1-bit pointer mask (or GC program, handled below)
   968  
   969  	// Heap bitmap bits for 2-word object are only 4 bits,
   970  	// so also shared with objects next to it.
   971  	// This is called out as a special case primarily for 32-bit systems,
   972  	// so that on 32-bit systems the code below can assume all objects
   973  	// are 4-word aligned (because they're all 16-byte aligned).
   974  	if size == 2*sys.PtrSize {
   975  		if typ.size == sys.PtrSize {
   976  			// We're allocating a block big enough to hold two pointers.
   977  			// On 64-bit, that means the actual object must be two pointers,
   978  			// or else we'd have used the one-pointer-sized block.
   979  			// On 32-bit, however, this is the 8-byte block, the smallest one.
   980  			// So it could be that we're allocating one pointer and this was
   981  			// just the smallest block available. Distinguish by checking dataSize.
   982  			// (In general the number of instances of typ being allocated is
   983  			// dataSize/typ.size.)
   984  			if sys.PtrSize == 4 && dataSize == sys.PtrSize {
   985  				// 1 pointer object. On 32-bit machines clear the bit for the
   986  				// unused second word.
   987  				*h.bitp &^= (bitPointer | bitScan | ((bitPointer | bitScan) << heapBitsShift)) << h.shift
   988  				*h.bitp |= (bitPointer | bitScan) << h.shift
   989  			} else {
   990  				// 2-element slice of pointer.
   991  				*h.bitp |= (bitPointer | bitScan | bitPointer<<heapBitsShift) << h.shift
   992  			}
   993  			return
   994  		}
   995  		// Otherwise typ.size must be 2*sys.PtrSize,
   996  		// and typ.kind&kindGCProg == 0.
   997  		if doubleCheck {
   998  			if typ.size != 2*sys.PtrSize || typ.kind&kindGCProg != 0 {
   999  				print("runtime: heapBitsSetType size=", size, " but typ.size=", typ.size, " gcprog=", typ.kind&kindGCProg != 0, "\n")
  1000  				throw("heapBitsSetType")
  1001  			}
  1002  		}
  1003  		b := uint32(*ptrmask)
  1004  		hb := (b & 3) | bitScan
  1005  		// bitPointer == 1, bitScan is 1 << 4, heapBitsShift is 1.
  1006  		// 110011 is shifted h.shift and complemented.
  1007  		// This clears out the bits that are about to be
  1008  		// ored into *h.hbitp in the next instructions.
  1009  		*h.bitp &^= (bitPointer | bitScan | ((bitPointer | bitScan) << heapBitsShift)) << h.shift
  1010  		*h.bitp |= uint8(hb << h.shift)
  1011  		return
  1012  	}
  1013  
  1014  	// Copy from 1-bit ptrmask into 2-bit bitmap.
  1015  	// The basic approach is to use a single uintptr as a bit buffer,
  1016  	// alternating between reloading the buffer and writing bitmap bytes.
  1017  	// In general, one load can supply two bitmap byte writes.
  1018  	// This is a lot of lines of code, but it compiles into relatively few
  1019  	// machine instructions.
  1020  
  1021  	outOfPlace := false
  1022  	if arenaIndex(x+size-1) != arenaIdx(h.arena) || (doubleCheck && fastrand()%2 == 0) {
  1023  		// This object spans heap arenas, so the bitmap may be
  1024  		// discontiguous. Unroll it into the object instead
  1025  		// and then copy it out.
  1026  		//
  1027  		// In doubleCheck mode, we randomly do this anyway to
  1028  		// stress test the bitmap copying path.
  1029  		outOfPlace = true
  1030  		h.bitp = (*uint8)(unsafe.Pointer(x))
  1031  		h.last = nil
  1032  	}
  1033  
  1034  	var (
  1035  		// Ptrmask input.
  1036  		p     *byte   // last ptrmask byte read
  1037  		b     uintptr // ptrmask bits already loaded
  1038  		nb    uintptr // number of bits in b at next read
  1039  		endp  *byte   // final ptrmask byte to read (then repeat)
  1040  		endnb uintptr // number of valid bits in *endp
  1041  		pbits uintptr // alternate source of bits
  1042  
  1043  		// Heap bitmap output.
  1044  		w     uintptr // words processed
  1045  		nw    uintptr // number of words to process
  1046  		hbitp *byte   // next heap bitmap byte to write
  1047  		hb    uintptr // bits being prepared for *hbitp
  1048  	)
  1049  
  1050  	hbitp = h.bitp
  1051  
  1052  	// Handle GC program. Delayed until this part of the code
  1053  	// so that we can use the same double-checking mechanism
  1054  	// as the 1-bit case. Nothing above could have encountered
  1055  	// GC programs: the cases were all too small.
  1056  	if typ.kind&kindGCProg != 0 {
  1057  		heapBitsSetTypeGCProg(h, typ.ptrdata, typ.size, dataSize, size, addb(typ.gcdata, 4))
  1058  		if doubleCheck {
  1059  			// Double-check the heap bits written by GC program
  1060  			// by running the GC program to create a 1-bit pointer mask
  1061  			// and then jumping to the double-check code below.
  1062  			// This doesn't catch bugs shared between the 1-bit and 4-bit
  1063  			// GC program execution, but it does catch mistakes specific
  1064  			// to just one of those and bugs in heapBitsSetTypeGCProg's
  1065  			// implementation of arrays.
  1066  			lock(&debugPtrmask.lock)
  1067  			if debugPtrmask.data == nil {
  1068  				debugPtrmask.data = (*byte)(persistentalloc(1<<20, 1, &memstats.other_sys))
  1069  			}
  1070  			ptrmask = debugPtrmask.data
  1071  			runGCProg(addb(typ.gcdata, 4), nil, ptrmask, 1)
  1072  		}
  1073  		goto Phase4
  1074  	}
  1075  
  1076  	// Note about sizes:
  1077  	//
  1078  	// typ.size is the number of words in the object,
  1079  	// and typ.ptrdata is the number of words in the prefix
  1080  	// of the object that contains pointers. That is, the final
  1081  	// typ.size - typ.ptrdata words contain no pointers.
  1082  	// This allows optimization of a common pattern where
  1083  	// an object has a small header followed by a large scalar
  1084  	// buffer. If we know the pointers are over, we don't have
  1085  	// to scan the buffer's heap bitmap at all.
  1086  	// The 1-bit ptrmasks are sized to contain only bits for
  1087  	// the typ.ptrdata prefix, zero padded out to a full byte
  1088  	// of bitmap. This code sets nw (below) so that heap bitmap
  1089  	// bits are only written for the typ.ptrdata prefix; if there is
  1090  	// more room in the allocated object, the next heap bitmap
  1091  	// entry is a 00, indicating that there are no more pointers
  1092  	// to scan. So only the ptrmask for the ptrdata bytes is needed.
  1093  	//
  1094  	// Replicated copies are not as nice: if there is an array of
  1095  	// objects with scalar tails, all but the last tail does have to
  1096  	// be initialized, because there is no way to say "skip forward".
  1097  	// However, because of the possibility of a repeated type with
  1098  	// size not a multiple of 4 pointers (one heap bitmap byte),
  1099  	// the code already must handle the last ptrmask byte specially
  1100  	// by treating it as containing only the bits for endnb pointers,
  1101  	// where endnb <= 4. We represent large scalar tails that must
  1102  	// be expanded in the replication by setting endnb larger than 4.
  1103  	// This will have the effect of reading many bits out of b,
  1104  	// but once the real bits are shifted out, b will supply as many
  1105  	// zero bits as we try to read, which is exactly what we need.
  1106  
  1107  	p = ptrmask
  1108  	if typ.size < dataSize {
  1109  		// Filling in bits for an array of typ.
  1110  		// Set up for repetition of ptrmask during main loop.
  1111  		// Note that ptrmask describes only a prefix of
  1112  		const maxBits = sys.PtrSize*8 - 7
  1113  		if typ.ptrdata/sys.PtrSize <= maxBits {
  1114  			// Entire ptrmask fits in uintptr with room for a byte fragment.
  1115  			// Load into pbits and never read from ptrmask again.
  1116  			// This is especially important when the ptrmask has
  1117  			// fewer than 8 bits in it; otherwise the reload in the middle
  1118  			// of the Phase 2 loop would itself need to loop to gather
  1119  			// at least 8 bits.
  1120  
  1121  			// Accumulate ptrmask into b.
  1122  			// ptrmask is sized to describe only typ.ptrdata, but we record
  1123  			// it as describing typ.size bytes, since all the high bits are zero.
  1124  			nb = typ.ptrdata / sys.PtrSize
  1125  			for i := uintptr(0); i < nb; i += 8 {
  1126  				b |= uintptr(*p) << i
  1127  				p = add1(p)
  1128  			}
  1129  			nb = typ.size / sys.PtrSize
  1130  
  1131  			// Replicate ptrmask to fill entire pbits uintptr.
  1132  			// Doubling and truncating is fewer steps than
  1133  			// iterating by nb each time. (nb could be 1.)
  1134  			// Since we loaded typ.ptrdata/sys.PtrSize bits
  1135  			// but are pretending to have typ.size/sys.PtrSize,
  1136  			// there might be no replication necessary/possible.
  1137  			pbits = b
  1138  			endnb = nb
  1139  			if nb+nb <= maxBits {
  1140  				for endnb <= sys.PtrSize*8 {
  1141  					pbits |= pbits << endnb
  1142  					endnb += endnb
  1143  				}
  1144  				// Truncate to a multiple of original ptrmask.
  1145  				// Because nb+nb <= maxBits, nb fits in a byte.
  1146  				// Byte division is cheaper than uintptr division.
  1147  				endnb = uintptr(maxBits/byte(nb)) * nb
  1148  				pbits &= 1<<endnb - 1
  1149  				b = pbits
  1150  				nb = endnb
  1151  			}
  1152  
  1153  			// Clear p and endp as sentinel for using pbits.
  1154  			// Checked during Phase 2 loop.
  1155  			p = nil
  1156  			endp = nil
  1157  		} else {
  1158  			// Ptrmask is larger. Read it multiple times.
  1159  			n := (typ.ptrdata/sys.PtrSize+7)/8 - 1
  1160  			endp = addb(ptrmask, n)
  1161  			endnb = typ.size/sys.PtrSize - n*8
  1162  		}
  1163  	}
  1164  	if p != nil {
  1165  		b = uintptr(*p)
  1166  		p = add1(p)
  1167  		nb = 8
  1168  	}
  1169  
  1170  	if typ.size == dataSize {
  1171  		// Single entry: can stop once we reach the non-pointer data.
  1172  		nw = typ.ptrdata / sys.PtrSize
  1173  	} else {
  1174  		// Repeated instances of typ in an array.
  1175  		// Have to process first N-1 entries in full, but can stop
  1176  		// once we reach the non-pointer data in the final entry.
  1177  		nw = ((dataSize/typ.size-1)*typ.size + typ.ptrdata) / sys.PtrSize
  1178  	}
  1179  	if nw == 0 {
  1180  		// No pointers! Caller was supposed to check.
  1181  		println("runtime: invalid type ", typ.string())
  1182  		throw("heapBitsSetType: called with non-pointer type")
  1183  		return
  1184  	}
  1185  	if nw < 2 {
  1186  		// Must write at least 2 words, because the "no scan"
  1187  		// encoding doesn't take effect until the third word.
  1188  		nw = 2
  1189  	}
  1190  
  1191  	// Phase 1: Special case for leading byte (shift==0) or half-byte (shift==2).
  1192  	// The leading byte is special because it contains the bits for word 1,
  1193  	// which does not have the scan bit set.
  1194  	// The leading half-byte is special because it's a half a byte,
  1195  	// so we have to be careful with the bits already there.
  1196  	switch {
  1197  	default:
  1198  		throw("heapBitsSetType: unexpected shift")
  1199  
  1200  	case h.shift == 0:
  1201  		// Ptrmask and heap bitmap are aligned.
  1202  		// Handle first byte of bitmap specially.
  1203  		//
  1204  		// The first byte we write out covers the first four
  1205  		// words of the object. The scan/dead bit on the first
  1206  		// word must be set to scan since there are pointers
  1207  		// somewhere in the object. The scan/dead bit on the
  1208  		// second word is the checkmark, so we don't set it.
  1209  		// In all following words, we set the scan/dead
  1210  		// appropriately to indicate that the object contains
  1211  		// to the next 2-bit entry in the bitmap.
  1212  		//
  1213  		// TODO: It doesn't matter if we set the checkmark, so
  1214  		// maybe this case isn't needed any more.
  1215  		hb = b & bitPointerAll
  1216  		hb |= bitScan | bitScan<<(2*heapBitsShift) | bitScan<<(3*heapBitsShift)
  1217  		if w += 4; w >= nw {
  1218  			goto Phase3
  1219  		}
  1220  		*hbitp = uint8(hb)
  1221  		hbitp = add1(hbitp)
  1222  		b >>= 4
  1223  		nb -= 4
  1224  
  1225  	case sys.PtrSize == 8 && h.shift == 2:
  1226  		// Ptrmask and heap bitmap are misaligned.
  1227  		// The bits for the first two words are in a byte shared
  1228  		// with another object, so we must be careful with the bits
  1229  		// already there.
  1230  		// We took care of 1-word and 2-word objects above,
  1231  		// so this is at least a 6-word object.
  1232  		hb = (b & (bitPointer | bitPointer<<heapBitsShift)) << (2 * heapBitsShift)
  1233  		// This is not noscan, so set the scan bit in the
  1234  		// first word.
  1235  		hb |= bitScan << (2 * heapBitsShift)
  1236  		b >>= 2
  1237  		nb -= 2
  1238  		// Note: no bitScan for second word because that's
  1239  		// the checkmark.
  1240  		*hbitp &^= uint8((bitPointer | bitScan | (bitPointer << heapBitsShift)) << (2 * heapBitsShift))
  1241  		*hbitp |= uint8(hb)
  1242  		hbitp = add1(hbitp)
  1243  		if w += 2; w >= nw {
  1244  			// We know that there is more data, because we handled 2-word objects above.
  1245  			// This must be at least a 6-word object. If we're out of pointer words,
  1246  			// mark no scan in next bitmap byte and finish.
  1247  			hb = 0
  1248  			w += 4
  1249  			goto Phase3
  1250  		}
  1251  	}
  1252  
  1253  	// Phase 2: Full bytes in bitmap, up to but not including write to last byte (full or partial) in bitmap.
  1254  	// The loop computes the bits for that last write but does not execute the write;
  1255  	// it leaves the bits in hb for processing by phase 3.
  1256  	// To avoid repeated adjustment of nb, we subtract out the 4 bits we're going to
  1257  	// use in the first half of the loop right now, and then we only adjust nb explicitly
  1258  	// if the 8 bits used by each iteration isn't balanced by 8 bits loaded mid-loop.
  1259  	nb -= 4
  1260  	for {
  1261  		// Emit bitmap byte.
  1262  		// b has at least nb+4 bits, with one exception:
  1263  		// if w+4 >= nw, then b has only nw-w bits,
  1264  		// but we'll stop at the break and then truncate
  1265  		// appropriately in Phase 3.
  1266  		hb = b & bitPointerAll
  1267  		hb |= bitScanAll
  1268  		if w += 4; w >= nw {
  1269  			break
  1270  		}
  1271  		*hbitp = uint8(hb)
  1272  		hbitp = add1(hbitp)
  1273  		b >>= 4
  1274  
  1275  		// Load more bits. b has nb right now.
  1276  		if p != endp {
  1277  			// Fast path: keep reading from ptrmask.
  1278  			// nb unmodified: we just loaded 8 bits,
  1279  			// and the next iteration will consume 8 bits,
  1280  			// leaving us with the same nb the next time we're here.
  1281  			if nb < 8 {
  1282  				b |= uintptr(*p) << nb
  1283  				p = add1(p)
  1284  			} else {
  1285  				// Reduce the number of bits in b.
  1286  				// This is important if we skipped
  1287  				// over a scalar tail, since nb could
  1288  				// be larger than the bit width of b.
  1289  				nb -= 8
  1290  			}
  1291  		} else if p == nil {
  1292  			// Almost as fast path: track bit count and refill from pbits.
  1293  			// For short repetitions.
  1294  			if nb < 8 {
  1295  				b |= pbits << nb
  1296  				nb += endnb
  1297  			}
  1298  			nb -= 8 // for next iteration
  1299  		} else {
  1300  			// Slow path: reached end of ptrmask.
  1301  			// Process final partial byte and rewind to start.
  1302  			b |= uintptr(*p) << nb
  1303  			nb += endnb
  1304  			if nb < 8 {
  1305  				b |= uintptr(*ptrmask) << nb
  1306  				p = add1(ptrmask)
  1307  			} else {
  1308  				nb -= 8
  1309  				p = ptrmask
  1310  			}
  1311  		}
  1312  
  1313  		// Emit bitmap byte.
  1314  		hb = b & bitPointerAll
  1315  		hb |= bitScanAll
  1316  		if w += 4; w >= nw {
  1317  			break
  1318  		}
  1319  		*hbitp = uint8(hb)
  1320  		hbitp = add1(hbitp)
  1321  		b >>= 4
  1322  	}
  1323  
  1324  Phase3:
  1325  	// Phase 3: Write last byte or partial byte and zero the rest of the bitmap entries.
  1326  	if w > nw {
  1327  		// Counting the 4 entries in hb not yet written to memory,
  1328  		// there are more entries than possible pointer slots.
  1329  		// Discard the excess entries (can't be more than 3).
  1330  		mask := uintptr(1)<<(4-(w-nw)) - 1
  1331  		hb &= mask | mask<<4 // apply mask to both pointer bits and scan bits
  1332  	}
  1333  
  1334  	// Change nw from counting possibly-pointer words to total words in allocation.
  1335  	nw = size / sys.PtrSize
  1336  
  1337  	// Write whole bitmap bytes.
  1338  	// The first is hb, the rest are zero.
  1339  	if w <= nw {
  1340  		*hbitp = uint8(hb)
  1341  		hbitp = add1(hbitp)
  1342  		hb = 0 // for possible final half-byte below
  1343  		for w += 4; w <= nw; w += 4 {
  1344  			*hbitp = 0
  1345  			hbitp = add1(hbitp)
  1346  		}
  1347  	}
  1348  
  1349  	// Write final partial bitmap byte if any.
  1350  	// We know w > nw, or else we'd still be in the loop above.
  1351  	// It can be bigger only due to the 4 entries in hb that it counts.
  1352  	// If w == nw+4 then there's nothing left to do: we wrote all nw entries
  1353  	// and can discard the 4 sitting in hb.
  1354  	// But if w == nw+2, we need to write first two in hb.
  1355  	// The byte is shared with the next object, so be careful with
  1356  	// existing bits.
  1357  	if w == nw+2 {
  1358  		*hbitp = *hbitp&^(bitPointer|bitScan|(bitPointer|bitScan)<<heapBitsShift) | uint8(hb)
  1359  	}
  1360  
  1361  Phase4:
  1362  	// Phase 4: Copy unrolled bitmap to per-arena bitmaps, if necessary.
  1363  	if outOfPlace {
  1364  		// TODO: We could probably make this faster by
  1365  		// handling [x+dataSize, x+size) specially.
  1366  		h := heapBitsForAddr(x)
  1367  		// cnw is the number of heap words, or bit pairs
  1368  		// remaining (like nw above).
  1369  		cnw := size / sys.PtrSize
  1370  		src := (*uint8)(unsafe.Pointer(x))
  1371  		// We know the first and last byte of the bitmap are
  1372  		// not the same, but it's still possible for small
  1373  		// objects span arenas, so it may share bitmap bytes
  1374  		// with neighboring objects.
  1375  		//
  1376  		// Handle the first byte specially if it's shared. See
  1377  		// Phase 1 for why this is the only special case we need.
  1378  		if doubleCheck {
  1379  			if !(h.shift == 0 || (sys.PtrSize == 8 && h.shift == 2)) {
  1380  				print("x=", x, " size=", size, " cnw=", h.shift, "\n")
  1381  				throw("bad start shift")
  1382  			}
  1383  		}
  1384  		if sys.PtrSize == 8 && h.shift == 2 {
  1385  			*h.bitp = *h.bitp&^((bitPointer|bitScan|(bitPointer|bitScan)<<heapBitsShift)<<(2*heapBitsShift)) | *src
  1386  			h = h.next().next()
  1387  			cnw -= 2
  1388  			src = addb(src, 1)
  1389  		}
  1390  		// We're now byte aligned. Copy out to per-arena
  1391  		// bitmaps until the last byte (which may again be
  1392  		// partial).
  1393  		for cnw >= 4 {
  1394  			// This loop processes four words at a time,
  1395  			// so round cnw down accordingly.
  1396  			hNext, words := h.forwardOrBoundary(cnw / 4 * 4)
  1397  
  1398  			// n is the number of bitmap bytes to copy.
  1399  			n := words / 4
  1400  			memmove(unsafe.Pointer(h.bitp), unsafe.Pointer(src), n)
  1401  			cnw -= words
  1402  			h = hNext
  1403  			src = addb(src, n)
  1404  		}
  1405  		if doubleCheck && h.shift != 0 {
  1406  			print("cnw=", cnw, " h.shift=", h.shift, "\n")
  1407  			throw("bad shift after block copy")
  1408  		}
  1409  		// Handle the last byte if it's shared.
  1410  		if cnw == 2 {
  1411  			*h.bitp = *h.bitp&^(bitPointer|bitScan|(bitPointer|bitScan)<<heapBitsShift) | *src
  1412  			src = addb(src, 1)
  1413  			h = h.next().next()
  1414  		}
  1415  		if doubleCheck {
  1416  			if uintptr(unsafe.Pointer(src)) > x+size {
  1417  				throw("copy exceeded object size")
  1418  			}
  1419  			if !(cnw == 0 || cnw == 2) {
  1420  				print("x=", x, " size=", size, " cnw=", cnw, "\n")
  1421  				throw("bad number of remaining words")
  1422  			}
  1423  			// Set up hbitp so doubleCheck code below can check it.
  1424  			hbitp = h.bitp
  1425  		}
  1426  		// Zero the object where we wrote the bitmap.
  1427  		memclrNoHeapPointers(unsafe.Pointer(x), uintptr(unsafe.Pointer(src))-x)
  1428  	}
  1429  
  1430  	// Double check the whole bitmap.
  1431  	if doubleCheck {
  1432  		// x+size may not point to the heap, so back up one
  1433  		// word and then call next().
  1434  		end := heapBitsForAddr(x + size - sys.PtrSize).next()
  1435  		endAI := arenaIdx(end.arena)
  1436  		if !outOfPlace && (end.bitp == nil || (end.shift == 0 && end.bitp == &mheap_.arenas[endAI.l1()][endAI.l2()].bitmap[0])) {
  1437  			// The unrolling code above walks hbitp just
  1438  			// past the bitmap without moving to the next
  1439  			// arena. Synthesize this for end.bitp.
  1440  			end.arena--
  1441  			endAI = arenaIdx(end.arena)
  1442  			end.bitp = addb(&mheap_.arenas[endAI.l1()][endAI.l2()].bitmap[0], heapArenaBitmapBytes)
  1443  			end.last = nil
  1444  		}
  1445  		if typ.kind&kindGCProg == 0 && (hbitp != end.bitp || (w == nw+2) != (end.shift == 2)) {
  1446  			println("ended at wrong bitmap byte for", typ.string(), "x", dataSize/typ.size)
  1447  			print("typ.size=", typ.size, " typ.ptrdata=", typ.ptrdata, " dataSize=", dataSize, " size=", size, "\n")
  1448  			print("w=", w, " nw=", nw, " b=", hex(b), " nb=", nb, " hb=", hex(hb), "\n")
  1449  			h0 := heapBitsForAddr(x)
  1450  			print("initial bits h0.bitp=", h0.bitp, " h0.shift=", h0.shift, "\n")
  1451  			print("ended at hbitp=", hbitp, " but next starts at bitp=", end.bitp, " shift=", end.shift, "\n")
  1452  			throw("bad heapBitsSetType")
  1453  		}
  1454  
  1455  		// Double-check that bits to be written were written correctly.
  1456  		// Does not check that other bits were not written, unfortunately.
  1457  		h := heapBitsForAddr(x)
  1458  		nptr := typ.ptrdata / sys.PtrSize
  1459  		ndata := typ.size / sys.PtrSize
  1460  		count := dataSize / typ.size
  1461  		totalptr := ((count-1)*typ.size + typ.ptrdata) / sys.PtrSize
  1462  		for i := uintptr(0); i < size/sys.PtrSize; i++ {
  1463  			j := i % ndata
  1464  			var have, want uint8
  1465  			have = (*h.bitp >> h.shift) & (bitPointer | bitScan)
  1466  			if i >= totalptr {
  1467  				want = 0 // deadmarker
  1468  				if typ.kind&kindGCProg != 0 && i < (totalptr+3)/4*4 {
  1469  					want = bitScan
  1470  				}
  1471  			} else {
  1472  				if j < nptr && (*addb(ptrmask, j/8)>>(j%8))&1 != 0 {
  1473  					want |= bitPointer
  1474  				}
  1475  				if i != 1 {
  1476  					want |= bitScan
  1477  				} else {
  1478  					have &^= bitScan
  1479  				}
  1480  			}
  1481  			if have != want {
  1482  				println("mismatch writing bits for", typ.string(), "x", dataSize/typ.size)
  1483  				print("typ.size=", typ.size, " typ.ptrdata=", typ.ptrdata, " dataSize=", dataSize, " size=", size, "\n")
  1484  				print("kindGCProg=", typ.kind&kindGCProg != 0, " outOfPlace=", outOfPlace, "\n")
  1485  				print("w=", w, " nw=", nw, " b=", hex(b), " nb=", nb, " hb=", hex(hb), "\n")
  1486  				h0 := heapBitsForAddr(x)
  1487  				print("initial bits h0.bitp=", h0.bitp, " h0.shift=", h0.shift, "\n")
  1488  				print("current bits h.bitp=", h.bitp, " h.shift=", h.shift, " *h.bitp=", hex(*h.bitp), "\n")
  1489  				print("ptrmask=", ptrmask, " p=", p, " endp=", endp, " endnb=", endnb, " pbits=", hex(pbits), " b=", hex(b), " nb=", nb, "\n")
  1490  				println("at word", i, "offset", i*sys.PtrSize, "have", hex(have), "want", hex(want))
  1491  				if typ.kind&kindGCProg != 0 {
  1492  					println("GC program:")
  1493  					dumpGCProg(addb(typ.gcdata, 4))
  1494  				}
  1495  				throw("bad heapBitsSetType")
  1496  			}
  1497  			h = h.next()
  1498  		}
  1499  		if ptrmask == debugPtrmask.data {
  1500  			unlock(&debugPtrmask.lock)
  1501  		}
  1502  	}
  1503  }
  1504  
  1505  var debugPtrmask struct {
  1506  	lock mutex
  1507  	data *byte
  1508  }
  1509  
  1510  // heapBitsSetTypeGCProg implements heapBitsSetType using a GC program.
  1511  // progSize is the size of the memory described by the program.
  1512  // elemSize is the size of the element that the GC program describes (a prefix of).
  1513  // dataSize is the total size of the intended data, a multiple of elemSize.
  1514  // allocSize is the total size of the allocated memory.
  1515  //
  1516  // GC programs are only used for large allocations.
  1517  // heapBitsSetType requires that allocSize is a multiple of 4 words,
  1518  // so that the relevant bitmap bytes are not shared with surrounding
  1519  // objects.
  1520  func heapBitsSetTypeGCProg(h heapBits, progSize, elemSize, dataSize, allocSize uintptr, prog *byte) {
  1521  	if sys.PtrSize == 8 && allocSize%(4*sys.PtrSize) != 0 {
  1522  		// Alignment will be wrong.
  1523  		throw("heapBitsSetTypeGCProg: small allocation")
  1524  	}
  1525  	var totalBits uintptr
  1526  	if elemSize == dataSize {
  1527  		totalBits = runGCProg(prog, nil, h.bitp, 2)
  1528  		if totalBits*sys.PtrSize != progSize {
  1529  			println("runtime: heapBitsSetTypeGCProg: total bits", totalBits, "but progSize", progSize)
  1530  			throw("heapBitsSetTypeGCProg: unexpected bit count")
  1531  		}
  1532  	} else {
  1533  		count := dataSize / elemSize
  1534  
  1535  		// Piece together program trailer to run after prog that does:
  1536  		//	literal(0)
  1537  		//	repeat(1, elemSize-progSize-1) // zeros to fill element size
  1538  		//	repeat(elemSize, count-1) // repeat that element for count
  1539  		// This zero-pads the data remaining in the first element and then
  1540  		// repeats that first element to fill the array.
  1541  		var trailer [40]byte // 3 varints (max 10 each) + some bytes
  1542  		i := 0
  1543  		if n := elemSize/sys.PtrSize - progSize/sys.PtrSize; n > 0 {
  1544  			// literal(0)
  1545  			trailer[i] = 0x01
  1546  			i++
  1547  			trailer[i] = 0
  1548  			i++
  1549  			if n > 1 {
  1550  				// repeat(1, n-1)
  1551  				trailer[i] = 0x81
  1552  				i++
  1553  				n--
  1554  				for ; n >= 0x80; n >>= 7 {
  1555  					trailer[i] = byte(n | 0x80)
  1556  					i++
  1557  				}
  1558  				trailer[i] = byte(n)
  1559  				i++
  1560  			}
  1561  		}
  1562  		// repeat(elemSize/ptrSize, count-1)
  1563  		trailer[i] = 0x80
  1564  		i++
  1565  		n := elemSize / sys.PtrSize
  1566  		for ; n >= 0x80; n >>= 7 {
  1567  			trailer[i] = byte(n | 0x80)
  1568  			i++
  1569  		}
  1570  		trailer[i] = byte(n)
  1571  		i++
  1572  		n = count - 1
  1573  		for ; n >= 0x80; n >>= 7 {
  1574  			trailer[i] = byte(n | 0x80)
  1575  			i++
  1576  		}
  1577  		trailer[i] = byte(n)
  1578  		i++
  1579  		trailer[i] = 0
  1580  		i++
  1581  
  1582  		runGCProg(prog, &trailer[0], h.bitp, 2)
  1583  
  1584  		// Even though we filled in the full array just now,
  1585  		// record that we only filled in up to the ptrdata of the
  1586  		// last element. This will cause the code below to
  1587  		// memclr the dead section of the final array element,
  1588  		// so that scanobject can stop early in the final element.
  1589  		totalBits = (elemSize*(count-1) + progSize) / sys.PtrSize
  1590  	}
  1591  	endProg := unsafe.Pointer(addb(h.bitp, (totalBits+3)/4))
  1592  	endAlloc := unsafe.Pointer(addb(h.bitp, allocSize/sys.PtrSize/wordsPerBitmapByte))
  1593  	memclrNoHeapPointers(endProg, uintptr(endAlloc)-uintptr(endProg))
  1594  }
  1595  
  1596  // progToPointerMask returns the 1-bit pointer mask output by the GC program prog.
  1597  // size the size of the region described by prog, in bytes.
  1598  // The resulting bitvector will have no more than size/sys.PtrSize bits.
  1599  func progToPointerMask(prog *byte, size uintptr) bitvector {
  1600  	n := (size/sys.PtrSize + 7) / 8
  1601  	x := (*[1 << 30]byte)(persistentalloc(n+1, 1, &memstats.buckhash_sys))[:n+1]
  1602  	x[len(x)-1] = 0xa1 // overflow check sentinel
  1603  	n = runGCProg(prog, nil, &x[0], 1)
  1604  	if x[len(x)-1] != 0xa1 {
  1605  		throw("progToPointerMask: overflow")
  1606  	}
  1607  	return bitvector{int32(n), &x[0]}
  1608  }
  1609  
  1610  // Packed GC pointer bitmaps, aka GC programs.
  1611  //
  1612  // For large types containing arrays, the type information has a
  1613  // natural repetition that can be encoded to save space in the
  1614  // binary and in the memory representation of the type information.
  1615  //
  1616  // The encoding is a simple Lempel-Ziv style bytecode machine
  1617  // with the following instructions:
  1618  //
  1619  //	00000000: stop
  1620  //	0nnnnnnn: emit n bits copied from the next (n+7)/8 bytes
  1621  //	10000000 n c: repeat the previous n bits c times; n, c are varints
  1622  //	1nnnnnnn c: repeat the previous n bits c times; c is a varint
  1623  
  1624  // runGCProg executes the GC program prog, and then trailer if non-nil,
  1625  // writing to dst with entries of the given size.
  1626  // If size == 1, dst is a 1-bit pointer mask laid out moving forward from dst.
  1627  // If size == 2, dst is the 2-bit heap bitmap, and writes move backward
  1628  // starting at dst (because the heap bitmap does). In this case, the caller guarantees
  1629  // that only whole bytes in dst need to be written.
  1630  //
  1631  // runGCProg returns the number of 1- or 2-bit entries written to memory.
  1632  func runGCProg(prog, trailer, dst *byte, size int) uintptr {
  1633  	dstStart := dst
  1634  
  1635  	// Bits waiting to be written to memory.
  1636  	var bits uintptr
  1637  	var nbits uintptr
  1638  
  1639  	p := prog
  1640  Run:
  1641  	for {
  1642  		// Flush accumulated full bytes.
  1643  		// The rest of the loop assumes that nbits <= 7.
  1644  		for ; nbits >= 8; nbits -= 8 {
  1645  			if size == 1 {
  1646  				*dst = uint8(bits)
  1647  				dst = add1(dst)
  1648  				bits >>= 8
  1649  			} else {
  1650  				v := bits&bitPointerAll | bitScanAll
  1651  				*dst = uint8(v)
  1652  				dst = add1(dst)
  1653  				bits >>= 4
  1654  				v = bits&bitPointerAll | bitScanAll
  1655  				*dst = uint8(v)
  1656  				dst = add1(dst)
  1657  				bits >>= 4
  1658  			}
  1659  		}
  1660  
  1661  		// Process one instruction.
  1662  		inst := uintptr(*p)
  1663  		p = add1(p)
  1664  		n := inst & 0x7F
  1665  		if inst&0x80 == 0 {
  1666  			// Literal bits; n == 0 means end of program.
  1667  			if n == 0 {
  1668  				// Program is over; continue in trailer if present.
  1669  				if trailer != nil {
  1670  					//println("trailer")
  1671  					p = trailer
  1672  					trailer = nil
  1673  					continue
  1674  				}
  1675  				//println("done")
  1676  				break Run
  1677  			}
  1678  			//println("lit", n, dst)
  1679  			nbyte := n / 8
  1680  			for i := uintptr(0); i < nbyte; i++ {
  1681  				bits |= uintptr(*p) << nbits
  1682  				p = add1(p)
  1683  				if size == 1 {
  1684  					*dst = uint8(bits)
  1685  					dst = add1(dst)
  1686  					bits >>= 8
  1687  				} else {
  1688  					v := bits&0xf | bitScanAll
  1689  					*dst = uint8(v)
  1690  					dst = add1(dst)
  1691  					bits >>= 4
  1692  					v = bits&0xf | bitScanAll
  1693  					*dst = uint8(v)
  1694  					dst = add1(dst)
  1695  					bits >>= 4
  1696  				}
  1697  			}
  1698  			if n %= 8; n > 0 {
  1699  				bits |= uintptr(*p) << nbits
  1700  				p = add1(p)
  1701  				nbits += n
  1702  			}
  1703  			continue Run
  1704  		}
  1705  
  1706  		// Repeat. If n == 0, it is encoded in a varint in the next bytes.
  1707  		if n == 0 {
  1708  			for off := uint(0); ; off += 7 {
  1709  				x := uintptr(*p)
  1710  				p = add1(p)
  1711  				n |= (x & 0x7F) << off
  1712  				if x&0x80 == 0 {
  1713  					break
  1714  				}
  1715  			}
  1716  		}
  1717  
  1718  		// Count is encoded in a varint in the next bytes.
  1719  		c := uintptr(0)
  1720  		for off := uint(0); ; off += 7 {
  1721  			x := uintptr(*p)
  1722  			p = add1(p)
  1723  			c |= (x & 0x7F) << off
  1724  			if x&0x80 == 0 {
  1725  				break
  1726  			}
  1727  		}
  1728  		c *= n // now total number of bits to copy
  1729  
  1730  		// If the number of bits being repeated is small, load them
  1731  		// into a register and use that register for the entire loop
  1732  		// instead of repeatedly reading from memory.
  1733  		// Handling fewer than 8 bits here makes the general loop simpler.
  1734  		// The cutoff is sys.PtrSize*8 - 7 to guarantee that when we add
  1735  		// the pattern to a bit buffer holding at most 7 bits (a partial byte)
  1736  		// it will not overflow.
  1737  		src := dst
  1738  		const maxBits = sys.PtrSize*8 - 7
  1739  		if n <= maxBits {
  1740  			// Start with bits in output buffer.
  1741  			pattern := bits
  1742  			npattern := nbits
  1743  
  1744  			// If we need more bits, fetch them from memory.
  1745  			if size == 1 {
  1746  				src = subtract1(src)
  1747  				for npattern < n {
  1748  					pattern <<= 8
  1749  					pattern |= uintptr(*src)
  1750  					src = subtract1(src)
  1751  					npattern += 8
  1752  				}
  1753  			} else {
  1754  				src = subtract1(src)
  1755  				for npattern < n {
  1756  					pattern <<= 4
  1757  					pattern |= uintptr(*src) & 0xf
  1758  					src = subtract1(src)
  1759  					npattern += 4
  1760  				}
  1761  			}
  1762  
  1763  			// We started with the whole bit output buffer,
  1764  			// and then we loaded bits from whole bytes.
  1765  			// Either way, we might now have too many instead of too few.
  1766  			// Discard the extra.
  1767  			if npattern > n {
  1768  				pattern >>= npattern - n
  1769  				npattern = n
  1770  			}
  1771  
  1772  			// Replicate pattern to at most maxBits.
  1773  			if npattern == 1 {
  1774  				// One bit being repeated.
  1775  				// If the bit is 1, make the pattern all 1s.
  1776  				// If the bit is 0, the pattern is already all 0s,
  1777  				// but we can claim that the number of bits
  1778  				// in the word is equal to the number we need (c),
  1779  				// because right shift of bits will zero fill.
  1780  				if pattern == 1 {
  1781  					pattern = 1<<maxBits - 1
  1782  					npattern = maxBits
  1783  				} else {
  1784  					npattern = c
  1785  				}
  1786  			} else {
  1787  				b := pattern
  1788  				nb := npattern
  1789  				if nb+nb <= maxBits {
  1790  					// Double pattern until the whole uintptr is filled.
  1791  					for nb <= sys.PtrSize*8 {
  1792  						b |= b << nb
  1793  						nb += nb
  1794  					}
  1795  					// Trim away incomplete copy of original pattern in high bits.
  1796  					// TODO(rsc): Replace with table lookup or loop on systems without divide?
  1797  					nb = maxBits / npattern * npattern
  1798  					b &= 1<<nb - 1
  1799  					pattern = b
  1800  					npattern = nb
  1801  				}
  1802  			}
  1803  
  1804  			// Add pattern to bit buffer and flush bit buffer, c/npattern times.
  1805  			// Since pattern contains >8 bits, there will be full bytes to flush
  1806  			// on each iteration.
  1807  			for ; c >= npattern; c -= npattern {
  1808  				bits |= pattern << nbits
  1809  				nbits += npattern
  1810  				if size == 1 {
  1811  					for nbits >= 8 {
  1812  						*dst = uint8(bits)
  1813  						dst = add1(dst)
  1814  						bits >>= 8
  1815  						nbits -= 8
  1816  					}
  1817  				} else {
  1818  					for nbits >= 4 {
  1819  						*dst = uint8(bits&0xf | bitScanAll)
  1820  						dst = add1(dst)
  1821  						bits >>= 4
  1822  						nbits -= 4
  1823  					}
  1824  				}
  1825  			}
  1826  
  1827  			// Add final fragment to bit buffer.
  1828  			if c > 0 {
  1829  				pattern &= 1<<c - 1
  1830  				bits |= pattern << nbits
  1831  				nbits += c
  1832  			}
  1833  			continue Run
  1834  		}
  1835  
  1836  		// Repeat; n too large to fit in a register.
  1837  		// Since nbits <= 7, we know the first few bytes of repeated data
  1838  		// are already written to memory.
  1839  		off := n - nbits // n > nbits because n > maxBits and nbits <= 7
  1840  		if size == 1 {
  1841  			// Leading src fragment.
  1842  			src = subtractb(src, (off+7)/8)
  1843  			if frag := off & 7; frag != 0 {
  1844  				bits |= uintptr(*src) >> (8 - frag) << nbits
  1845  				src = add1(src)
  1846  				nbits += frag
  1847  				c -= frag
  1848  			}
  1849  			// Main loop: load one byte, write another.
  1850  			// The bits are rotating through the bit buffer.
  1851  			for i := c / 8; i > 0; i-- {
  1852  				bits |= uintptr(*src) << nbits
  1853  				src = add1(src)
  1854  				*dst = uint8(bits)
  1855  				dst = add1(dst)
  1856  				bits >>= 8
  1857  			}
  1858  			// Final src fragment.
  1859  			if c %= 8; c > 0 {
  1860  				bits |= (uintptr(*src) & (1<<c - 1)) << nbits
  1861  				nbits += c
  1862  			}
  1863  		} else {
  1864  			// Leading src fragment.
  1865  			src = subtractb(src, (off+3)/4)
  1866  			if frag := off & 3; frag != 0 {
  1867  				bits |= (uintptr(*src) & 0xf) >> (4 - frag) << nbits
  1868  				src = add1(src)
  1869  				nbits += frag
  1870  				c -= frag
  1871  			}
  1872  			// Main loop: load one byte, write another.
  1873  			// The bits are rotating through the bit buffer.
  1874  			for i := c / 4; i > 0; i-- {
  1875  				bits |= (uintptr(*src) & 0xf) << nbits
  1876  				src = add1(src)
  1877  				*dst = uint8(bits&0xf | bitScanAll)
  1878  				dst = add1(dst)
  1879  				bits >>= 4
  1880  			}
  1881  			// Final src fragment.
  1882  			if c %= 4; c > 0 {
  1883  				bits |= (uintptr(*src) & (1<<c - 1)) << nbits
  1884  				nbits += c
  1885  			}
  1886  		}
  1887  	}
  1888  
  1889  	// Write any final bits out, using full-byte writes, even for the final byte.
  1890  	var totalBits uintptr
  1891  	if size == 1 {
  1892  		totalBits = (uintptr(unsafe.Pointer(dst))-uintptr(unsafe.Pointer(dstStart)))*8 + nbits
  1893  		nbits += -nbits & 7
  1894  		for ; nbits > 0; nbits -= 8 {
  1895  			*dst = uint8(bits)
  1896  			dst = add1(dst)
  1897  			bits >>= 8
  1898  		}
  1899  	} else {
  1900  		totalBits = (uintptr(unsafe.Pointer(dst))-uintptr(unsafe.Pointer(dstStart)))*4 + nbits
  1901  		nbits += -nbits & 3
  1902  		for ; nbits > 0; nbits -= 4 {
  1903  			v := bits&0xf | bitScanAll
  1904  			*dst = uint8(v)
  1905  			dst = add1(dst)
  1906  			bits >>= 4
  1907  		}
  1908  	}
  1909  	return totalBits
  1910  }
  1911  
  1912  // materializeGCProg allocates space for the (1-bit) pointer bitmask
  1913  // for an object of size ptrdata.  Then it fills that space with the
  1914  // pointer bitmask specified by the program prog.
  1915  // The bitmask starts at s.startAddr.
  1916  // The result must be deallocated with dematerializeGCProg.
  1917  func materializeGCProg(ptrdata uintptr, prog *byte) *mspan {
  1918  	s := mheap_.allocManual((ptrdata/(8*sys.PtrSize)+pageSize-1)/pageSize, &memstats.gc_sys)
  1919  	runGCProg(addb(prog, 4), nil, (*byte)(unsafe.Pointer(s.startAddr)), 1)
  1920  	return s
  1921  }
  1922  func dematerializeGCProg(s *mspan) {
  1923  	mheap_.freeManual(s, &memstats.gc_sys)
  1924  }
  1925  
  1926  func dumpGCProg(p *byte) {
  1927  	nptr := 0
  1928  	for {
  1929  		x := *p
  1930  		p = add1(p)
  1931  		if x == 0 {
  1932  			print("\t", nptr, " end\n")
  1933  			break
  1934  		}
  1935  		if x&0x80 == 0 {
  1936  			print("\t", nptr, " lit ", x, ":")
  1937  			n := int(x+7) / 8
  1938  			for i := 0; i < n; i++ {
  1939  				print(" ", hex(*p))
  1940  				p = add1(p)
  1941  			}
  1942  			print("\n")
  1943  			nptr += int(x)
  1944  		} else {
  1945  			nbit := int(x &^ 0x80)
  1946  			if nbit == 0 {
  1947  				for nb := uint(0); ; nb += 7 {
  1948  					x := *p
  1949  					p = add1(p)
  1950  					nbit |= int(x&0x7f) << nb
  1951  					if x&0x80 == 0 {
  1952  						break
  1953  					}
  1954  				}
  1955  			}
  1956  			count := 0
  1957  			for nb := uint(0); ; nb += 7 {
  1958  				x := *p
  1959  				p = add1(p)
  1960  				count |= int(x&0x7f) << nb
  1961  				if x&0x80 == 0 {
  1962  					break
  1963  				}
  1964  			}
  1965  			print("\t", nptr, " repeat ", nbit, " × ", count, "\n")
  1966  			nptr += nbit * count
  1967  		}
  1968  	}
  1969  }
  1970  
  1971  // Testing.
  1972  
  1973  func getgcmaskcb(frame *stkframe, ctxt unsafe.Pointer) bool {
  1974  	target := (*stkframe)(ctxt)
  1975  	if frame.sp <= target.sp && target.sp < frame.varp {
  1976  		*target = *frame
  1977  		return false
  1978  	}
  1979  	return true
  1980  }
  1981  
  1982  // gcbits returns the GC type info for x, for testing.
  1983  // The result is the bitmap entries (0 or 1), one entry per byte.
  1984  //go:linkname reflect_gcbits reflect.gcbits
  1985  func reflect_gcbits(x interface{}) []byte {
  1986  	ret := getgcmask(x)
  1987  	typ := (*ptrtype)(unsafe.Pointer(efaceOf(&x)._type)).elem
  1988  	nptr := typ.ptrdata / sys.PtrSize
  1989  	for uintptr(len(ret)) > nptr && ret[len(ret)-1] == 0 {
  1990  		ret = ret[:len(ret)-1]
  1991  	}
  1992  	return ret
  1993  }
  1994  
  1995  // Returns GC type info for the pointer stored in ep for testing.
  1996  // If ep points to the stack, only static live information will be returned
  1997  // (i.e. not for objects which are only dynamically live stack objects).
  1998  func getgcmask(ep interface{}) (mask []byte) {
  1999  	e := *efaceOf(&ep)
  2000  	p := e.data
  2001  	t := e._type
  2002  	// data or bss
  2003  	for _, datap := range activeModules() {
  2004  		// data
  2005  		if datap.data <= uintptr(p) && uintptr(p) < datap.edata {
  2006  			bitmap := datap.gcdatamask.bytedata
  2007  			n := (*ptrtype)(unsafe.Pointer(t)).elem.size
  2008  			mask = make([]byte, n/sys.PtrSize)
  2009  			for i := uintptr(0); i < n; i += sys.PtrSize {
  2010  				off := (uintptr(p) + i - datap.data) / sys.PtrSize
  2011  				mask[i/sys.PtrSize] = (*addb(bitmap, off/8) >> (off % 8)) & 1
  2012  			}
  2013  			return
  2014  		}
  2015  
  2016  		// bss
  2017  		if datap.bss <= uintptr(p) && uintptr(p) < datap.ebss {
  2018  			bitmap := datap.gcbssmask.bytedata
  2019  			n := (*ptrtype)(unsafe.Pointer(t)).elem.size
  2020  			mask = make([]byte, n/sys.PtrSize)
  2021  			for i := uintptr(0); i < n; i += sys.PtrSize {
  2022  				off := (uintptr(p) + i - datap.bss) / sys.PtrSize
  2023  				mask[i/sys.PtrSize] = (*addb(bitmap, off/8) >> (off % 8)) & 1
  2024  			}
  2025  			return
  2026  		}
  2027  	}
  2028  
  2029  	// heap
  2030  	if base, s, _ := findObject(uintptr(p), 0, 0); base != 0 {
  2031  		hbits := heapBitsForAddr(base)
  2032  		n := s.elemsize
  2033  		mask = make([]byte, n/sys.PtrSize)
  2034  		for i := uintptr(0); i < n; i += sys.PtrSize {
  2035  			if hbits.isPointer() {
  2036  				mask[i/sys.PtrSize] = 1
  2037  			}
  2038  			if i != 1*sys.PtrSize && !hbits.morePointers() {
  2039  				mask = mask[:i/sys.PtrSize]
  2040  				break
  2041  			}
  2042  			hbits = hbits.next()
  2043  		}
  2044  		return
  2045  	}
  2046  
  2047  	// stack
  2048  	if _g_ := getg(); _g_.m.curg.stack.lo <= uintptr(p) && uintptr(p) < _g_.m.curg.stack.hi {
  2049  		var frame stkframe
  2050  		frame.sp = uintptr(p)
  2051  		_g_ := getg()
  2052  		gentraceback(_g_.m.curg.sched.pc, _g_.m.curg.sched.sp, 0, _g_.m.curg, 0, nil, 1000, getgcmaskcb, noescape(unsafe.Pointer(&frame)), 0)
  2053  		if frame.fn.valid() {
  2054  			locals, _, _ := getStackMap(&frame, nil, false)
  2055  			if locals.n == 0 {
  2056  				return
  2057  			}
  2058  			size := uintptr(locals.n) * sys.PtrSize
  2059  			n := (*ptrtype)(unsafe.Pointer(t)).elem.size
  2060  			mask = make([]byte, n/sys.PtrSize)
  2061  			for i := uintptr(0); i < n; i += sys.PtrSize {
  2062  				off := (uintptr(p) + i - frame.varp + size) / sys.PtrSize
  2063  				mask[i/sys.PtrSize] = locals.ptrbit(off)
  2064  			}
  2065  		}
  2066  		return
  2067  	}
  2068  
  2069  	// otherwise, not something the GC knows about.
  2070  	// possibly read-only data, like malloc(0).
  2071  	// must not have pointers
  2072  	return
  2073  }
  2074  

View as plain text