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.
5 // Garbage collector: type and heap bitmaps.
7 // Stack, data, and bss bitmaps
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.
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.
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
34 // In the second word, the high bit is the GC ``checkmarked'' bit (see below).
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)
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.
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.
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.
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.
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
78 "runtime/internal/atomic"
79 "runtime/internal/sys"
87 heapBitsShift = 1 // shift offset between successive bitPointer or bitScan entries
88 wordsPerBitmapByte = 8 / 2 // heap words described by one bitmap byte
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)
95 // addb returns the byte pointer p+n.
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))
105 // subtractb returns the byte pointer p-n.
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))
115 // add1 returns the byte pointer p+1.
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))
125 // subtract1 returns the byte pointer p-1.
128 // nosplit because it is used during write barriers and must not be preempted.
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))
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 {
144 arena uint32 // Index of heap arena containing bitp
145 last *uint8 // Last byte arena's bitmap
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}
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
161 type markBits struct {
168 func (s *mspan) allocBitsForIndex(allocBitIndex uintptr) markBits {
169 bytep, mask := s.allocBits.bitp(allocBitIndex)
170 return markBits{bytep, mask, allocBitIndex}
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
177 func (s *mspan) refillAllocCache(whichByte uintptr) {
178 bytes := (*[8]uint8)(unsafe.Pointer(s.allocBits.bytep(whichByte)))
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
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
198 if sfreeindex == snelems {
201 if sfreeindex > snelems {
202 throw("s.freeindex > s.nelems")
205 aCache := s.allocCache
207 bitIndex := sys.Ctz64(aCache)
209 // Move index to start of next cached bits.
210 sfreeindex = (sfreeindex + 64) &^ (64 - 1)
211 if sfreeindex >= snelems {
212 s.freeindex = snelems
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.
223 result := sfreeindex + uintptr(bitIndex)
224 if result >= snelems {
225 s.freeindex = snelems
229 s.allocCache >>= uint(bitIndex + 1)
230 sfreeindex = result + 1
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)
241 s.freeindex = sfreeindex
245 // isFree returns whether the index'th object in s is unallocated.
246 func (s *mspan) isFree(index uintptr) bool {
247 if index < s.freeindex {
250 bytep, mask := s.allocBits.bitp(index)
251 return *bytep&mask == 0
254 func (s *mspan) objIndex(p uintptr) uintptr {
255 byteOffset := p - s.base()
260 // s.baseMask is non-0, elemsize is a power of two, so shift by s.divShift
261 return byteOffset >> s.divShift
263 return uintptr(((uint64(byteOffset) >> s.divShift) * uint64(s.divMul)) >> s.divShift2)
266 func markBitsForAddr(p uintptr) markBits {
268 objIndex := s.objIndex(p)
269 return s.markBitsForIndex(objIndex)
272 func (s *mspan) markBitsForIndex(objIndex uintptr) markBits {
273 bytep, mask := s.gcmarkBits.bitp(objIndex)
274 return markBits{bytep, mask, objIndex}
277 func (s *mspan) markBitsForBase() markBits {
278 return markBits{(*uint8)(s.gcmarkBits), uint8(1), 0}
281 // isMarked reports whether mark bit m is set.
282 func (m markBits) isMarked() bool {
283 return *m.bytep&m.mask != 0
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)
294 // setMarkedNonAtomic sets the marked bit in the markbits, non-atomically.
295 func (m markBits) setMarkedNonAtomic() {
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)
307 // markBitsForSpan returns the markBits for the span base address base.
308 func markBitsForSpan(base uintptr) (mbits markBits) {
309 mbits = markBitsForAddr(base)
311 throw("markBitsForSpan: unaligned start")
316 // advance advances the markBits to the next object in the span.
317 func (m *markBits) advance() {
319 m.bytep = (*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(m.bytep)) + 1))
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.
331 // nosplit because it is used during write barriers and must not be preempted.
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.
341 // addr is not in the heap. Return nil heapBits, which
342 // we expect to crash in the caller.
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]
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.
356 // If p points is an invalid heap pointer and debug.invalidptr != 0,
357 // findObject panics.
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) {
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.
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
381 // TODO(austin): We could be more aggressive
382 // and detect pointers to unallocated objects
383 // in allocated spans.
385 print("runtime: pointer ", hex(p))
386 if s.state != mSpanInUse {
387 print(" to unallocated span")
389 print(" to unused region of span")
391 print(" span.base()=", hex(s.base()), " span.limit=", hex(s.limit), " span.state=", s.state, "\n")
393 print("runtime: found in object at *(", hex(refBase), "+", hex(refOff), ")\n")
394 gcDumpObject("object", refBase, refOff)
396 getg().m.traceback = 2
397 throw("found bad pointer in Go heap (incorrect use of unsafe or cgo?)")
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.
404 // optimize for power of 2 sized objects.
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.
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
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.
426 // nosplit because it is used during write barriers and must not be preempted.
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
434 // Move to the next arena.
440 // nextArena advances h to the beginning of the next heap arena.
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.
449 func (h heapBits) nextArena() heapBits {
451 ai := arenaIdx(h.arena)
452 l2 := mheap_.arenas[ai.l1()]
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.
463 h.bitp, h.shift = &ha.bitmap[0], 0
464 h.last = &ha.bitmap[len(ha.bitmap)-1]
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.
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))
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 {
489 h.bitp = &a.bitmap[past%heapArenaBitmapBytes]
490 h.last = &a.bitmap[len(a.bitmap)-1]
492 h.bitp, h.last = nil, nil
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)))
505 return h.forward(n), n
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.
512 // nosplit because it is used during write barriers and must not be preempted.
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)
520 // morePointers returns true if this word and all remaining words in this object
522 // h must not describe the second word of the object.
523 func (h heapBits) morePointers() bool {
524 return h.bits()&bitScan != 0
527 // isPointer reports whether the heap bits describe a pointer word.
529 // nosplit because it is used during write barriers and must not be preempted.
531 func (h heapBits) isPointer() bool {
532 return h.bits()&bitPointer != 0
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
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
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)
559 atomic.Or8(h.bitp, bitScan<<(heapBitsShift+h.shift))
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.
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
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.
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.
586 // Callers must perform cgo checks if writeBarrier.cgo.
589 func bulkBarrierPreWrite(dst, src, size uintptr) {
590 if (dst|src|size)&(sys.PtrSize-1) != 0 {
591 throw("bulkBarrierPreWrite: unaligned arguments")
593 if !writeBarrier.needed {
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)
605 for _, datap := range activeModules() {
606 if datap.bss <= dst && dst < datap.ebss {
607 bulkBarrierBitmap(dst, src, size, dst-datap.bss, datap.gcbssmask.bytedata)
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.
622 buf := &getg().m.p.ptr().wbBuf
623 h := heapBitsForAddr(dst)
625 for i := uintptr(0); i < size; i += sys.PtrSize {
627 dstx := (*uintptr)(unsafe.Pointer(dst + i))
628 if !buf.putFast(*dstx, 0) {
635 for i := uintptr(0); i < size; i += sys.PtrSize {
637 dstx := (*uintptr)(unsafe.Pointer(dst + i))
638 srcx := (*uintptr)(unsafe.Pointer(src + i))
639 if !buf.putFast(*dstx, *srcx) {
648 // bulkBarrierPreWriteSrcOnly is like bulkBarrierPreWrite but
649 // does not execute write barriers for [dst, dst+size).
651 // In addition to the requirements of bulkBarrierPreWrite
652 // callers need to ensure [dst, dst+size) is zeroed.
654 // This is used for special cases where e.g. dst was just
655 // created and zeroed with malloc.
657 func bulkBarrierPreWriteSrcOnly(dst, src, size uintptr) {
658 if (dst|src|size)&(sys.PtrSize-1) != 0 {
659 throw("bulkBarrierPreWrite: unaligned arguments")
661 if !writeBarrier.needed {
664 buf := &getg().m.p.ptr().wbBuf
665 h := heapBitsForAddr(dst)
666 for i := uintptr(0); i < size; i += sys.PtrSize {
668 srcx := (*uintptr)(unsafe.Pointer(src + i))
669 if !buf.putFast(0, *srcx) {
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).
682 // This is used by bulkBarrierPreWrite for writes to data and BSS.
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)
690 buf := &getg().m.p.ptr().wbBuf
691 for i := uintptr(0); i < size; i += sys.PtrSize {
702 dstx := (*uintptr)(unsafe.Pointer(dst + i))
704 if !buf.putFast(*dstx, 0) {
708 srcx := (*uintptr)(unsafe.Pointer(src + i))
709 if !buf.putFast(*dstx, *srcx) {
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
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.
729 // Must not be preempted because it typically runs right before memmove,
730 // and the GC must observe them as an atomic action.
732 // Callers must perform cgo checks if writeBarrier.cgo.
735 func typeBitsBulkBarrier(typ *_type, dst, src, size uintptr) {
737 throw("runtime: typeBitsBulkBarrier without type")
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")
743 if typ.kind&kindGCProg != 0 {
744 println("runtime: typeBitsBulkBarrier with type ", typ.string(), " with GC prog")
745 throw("runtime: invalid typeBitsBulkBarrier")
747 if !writeBarrier.needed {
750 ptrmask := typ.gcdata
751 buf := &getg().m.p.ptr().wbBuf
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)
761 dstx := (*uintptr)(unsafe.Pointer(dst + i))
762 srcx := (*uintptr)(unsafe.Pointer(src + i))
763 if !buf.putFast(*dstx, *srcx) {
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.
776 // TODO(rsc): Perhaps introduce a different heapBitsSpan type.
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()
786 // Init the markbit structures
788 s.allocCache = ^uint64(0) // all 1s indicating all free.
792 s.gcmarkBits = newMarkBits(s.nelems)
793 s.allocBits = newAllocBits(s.nelems)
795 // Clear bits corresponding to objects.
796 nw := total / sys.PtrSize
797 if nw%wordsPerBitmapByte != 0 {
798 throw("initSpan: unaligned length")
801 throw("initSpan: unaligned base")
804 hNext, anw := h.forwardOrBoundary(nw)
805 nbyte := anw / wordsPerBitmapByte
806 if sys.PtrSize == 8 && size == sys.PtrSize {
808 for i := uintptr(0); i < nbyte; i++ {
809 *bitp = bitPointerAll | bitScanAll
813 memclrNoHeapPointers(unsafe.Pointer(h.bitp), nbyte)
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)
835 for i := uintptr(0); i < n; i++ {
836 *h.bitp &^= bitScan << (heapBitsShift + h.shift)
837 h = h.forward(size / sys.PtrSize)
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)
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}
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 {
901 maxIndex := s.nelems / 8
902 for i := uintptr(0); i < maxIndex; i++ {
903 mrkBits := *s.gcmarkBits.bytep(i)
904 count += int(oneBitCount[mrkBits])
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])
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.
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.
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
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.
946 // The checks for size == sys.PtrSize and size == 2*sys.PtrSize can therefore
947 // assume that dataSize == size without checking it explicitly.
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.
955 h := heapBitsForAddr(x)
957 throw("heapBitsSetType: pointer bit missing")
959 if !h.morePointers() {
960 throw("heapBitsSetType: scan bit missing")
966 h := heapBitsForAddr(x)
967 ptrmask := typ.gcdata // start of 1-bit pointer mask (or GC program, handled below)
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
990 // 2-element slice of pointer.
991 *h.bitp |= (bitPointer | bitScan | bitPointer<<heapBitsShift) << h.shift
995 // Otherwise typ.size must be 2*sys.PtrSize,
996 // and typ.kind&kindGCProg == 0.
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")
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)
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.
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.
1027 // In doubleCheck mode, we randomly do this anyway to
1028 // stress test the bitmap copying path.
1030 h.bitp = (*uint8)(unsafe.Pointer(x))
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
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
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))
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))
1070 ptrmask = debugPtrmask.data
1071 runGCProg(addb(typ.gcdata, 4), nil, ptrmask, 1)
1076 // Note about sizes:
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.
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.
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
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
1129 nb = typ.size / sys.PtrSize
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.
1139 if nb+nb <= maxBits {
1140 for endnb <= sys.PtrSize*8 {
1141 pbits |= pbits << endnb
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
1153 // Clear p and endp as sentinel for using pbits.
1154 // Checked during Phase 2 loop.
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
1170 if typ.size == dataSize {
1171 // Single entry: can stop once we reach the non-pointer data.
1172 nw = typ.ptrdata / sys.PtrSize
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
1180 // No pointers! Caller was supposed to check.
1181 println("runtime: invalid type ", typ.string())
1182 throw("heapBitsSetType: called with non-pointer type")
1186 // Must write at least 2 words, because the "no scan"
1187 // encoding doesn't take effect until the third word.
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.
1198 throw("heapBitsSetType: unexpected shift")
1201 // Ptrmask and heap bitmap are aligned.
1202 // Handle first byte of bitmap specially.
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.
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 {
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
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
1235 hb |= bitScan << (2 * heapBitsShift)
1238 // Note: no bitScan for second word because that's
1240 *hbitp &^= uint8((bitPointer | bitScan | (bitPointer << heapBitsShift)) << (2 * heapBitsShift))
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.
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.
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
1268 if w += 4; w >= nw {
1275 // Load more bits. b has nb right now.
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.
1282 b |= uintptr(*p) << nb
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.
1291 } else if p == nil {
1292 // Almost as fast path: track bit count and refill from pbits.
1293 // For short repetitions.
1298 nb -= 8 // for next iteration
1300 // Slow path: reached end of ptrmask.
1301 // Process final partial byte and rewind to start.
1302 b |= uintptr(*p) << nb
1305 b |= uintptr(*ptrmask) << nb
1313 // Emit bitmap byte.
1314 hb = b & bitPointerAll
1316 if w += 4; w >= nw {
1325 // Phase 3: Write last byte or partial byte and zero the rest of the bitmap entries.
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
1334 // Change nw from counting possibly-pointer words to total words in allocation.
1335 nw = size / sys.PtrSize
1337 // Write whole bitmap bytes.
1338 // The first is hb, the rest are zero.
1342 hb = 0 // for possible final half-byte below
1343 for w += 4; w <= nw; w += 4 {
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
1358 *hbitp = *hbitp&^(bitPointer|bitScan|(bitPointer|bitScan)<<heapBitsShift) | uint8(hb)
1362 // Phase 4: Copy unrolled bitmap to per-arena bitmaps, if necessary.
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.
1376 // Handle the first byte specially if it's shared. See
1377 // Phase 1 for why this is the only special case we need.
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")
1384 if sys.PtrSize == 8 && h.shift == 2 {
1385 *h.bitp = *h.bitp&^((bitPointer|bitScan|(bitPointer|bitScan)<<heapBitsShift)<<(2*heapBitsShift)) | *src
1390 // We're now byte aligned. Copy out to per-arena
1391 // bitmaps until the last byte (which may again be
1394 // This loop processes four words at a time,
1395 // so round cnw down accordingly.
1396 hNext, words := h.forwardOrBoundary(cnw / 4 * 4)
1398 // n is the number of bitmap bytes to copy.
1400 memmove(unsafe.Pointer(h.bitp), unsafe.Pointer(src), n)
1405 if doubleCheck && h.shift != 0 {
1406 print("cnw=", cnw, " h.shift=", h.shift, "\n")
1407 throw("bad shift after block copy")
1409 // Handle the last byte if it's shared.
1411 *h.bitp = *h.bitp&^(bitPointer|bitScan|(bitPointer|bitScan)<<heapBitsShift) | *src
1416 if uintptr(unsafe.Pointer(src)) > x+size {
1417 throw("copy exceeded object size")
1419 if !(cnw == 0 || cnw == 2) {
1420 print("x=", x, " size=", size, " cnw=", cnw, "\n")
1421 throw("bad number of remaining words")
1423 // Set up hbitp so doubleCheck code below can check it.
1426 // Zero the object where we wrote the bitmap.
1427 memclrNoHeapPointers(unsafe.Pointer(x), uintptr(unsafe.Pointer(src))-x)
1430 // Double check the whole bitmap.
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.
1441 endAI = arenaIdx(end.arena)
1442 end.bitp = addb(&mheap_.arenas[endAI.l1()][endAI.l2()].bitmap[0], heapArenaBitmapBytes)
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")
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++ {
1464 var have, want uint8
1465 have = (*h.bitp >> h.shift) & (bitPointer | bitScan)
1467 want = 0 // deadmarker
1468 if typ.kind&kindGCProg != 0 && i < (totalptr+3)/4*4 {
1472 if j < nptr && (*addb(ptrmask, j/8)>>(j%8))&1 != 0 {
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))
1495 throw("bad heapBitsSetType")
1499 if ptrmask == debugPtrmask.data {
1500 unlock(&debugPtrmask.lock)
1505 var debugPtrmask struct {
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.
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
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")
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")
1533 count := dataSize / elemSize
1535 // Piece together program trailer to run after prog that does:
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
1543 if n := elemSize/sys.PtrSize - progSize/sys.PtrSize; n > 0 {
1554 for ; n >= 0x80; n >>= 7 {
1555 trailer[i] = byte(n | 0x80)
1558 trailer[i] = byte(n)
1562 // repeat(elemSize/ptrSize, count-1)
1565 n := elemSize / sys.PtrSize
1566 for ; n >= 0x80; n >>= 7 {
1567 trailer[i] = byte(n | 0x80)
1570 trailer[i] = byte(n)
1573 for ; n >= 0x80; n >>= 7 {
1574 trailer[i] = byte(n | 0x80)
1577 trailer[i] = byte(n)
1582 runGCProg(prog, &trailer[0], h.bitp, 2)
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
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))
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")
1607 return bitvector{int32(n), &x[0]}
1610 // Packed GC pointer bitmaps, aka GC programs.
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.
1616 // The encoding is a simple Lempel-Ziv style bytecode machine
1617 // with the following instructions:
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
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.
1631 // runGCProg returns the number of 1- or 2-bit entries written to memory.
1632 func runGCProg(prog, trailer, dst *byte, size int) uintptr {
1635 // Bits waiting to be written to memory.
1642 // Flush accumulated full bytes.
1643 // The rest of the loop assumes that nbits <= 7.
1644 for ; nbits >= 8; nbits -= 8 {
1650 v := bits&bitPointerAll | bitScanAll
1654 v = bits&bitPointerAll | bitScanAll
1661 // Process one instruction.
1666 // Literal bits; n == 0 means end of program.
1668 // Program is over; continue in trailer if present.
1670 //println("trailer")
1678 //println("lit", n, dst)
1680 for i := uintptr(0); i < nbyte; i++ {
1681 bits |= uintptr(*p) << nbits
1688 v := bits&0xf | bitScanAll
1692 v = bits&0xf | bitScanAll
1699 bits |= uintptr(*p) << nbits
1706 // Repeat. If n == 0, it is encoded in a varint in the next bytes.
1708 for off := uint(0); ; off += 7 {
1711 n |= (x & 0x7F) << off
1718 // Count is encoded in a varint in the next bytes.
1720 for off := uint(0); ; off += 7 {
1723 c |= (x & 0x7F) << off
1728 c *= n // now total number of bits to copy
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.
1738 const maxBits = sys.PtrSize*8 - 7
1740 // Start with bits in output buffer.
1744 // If we need more bits, fetch them from memory.
1746 src = subtract1(src)
1749 pattern |= uintptr(*src)
1750 src = subtract1(src)
1754 src = subtract1(src)
1757 pattern |= uintptr(*src) & 0xf
1758 src = subtract1(src)
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.
1768 pattern >>= npattern - n
1772 // Replicate pattern to at most maxBits.
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.
1781 pattern = 1<<maxBits - 1
1789 if nb+nb <= maxBits {
1790 // Double pattern until the whole uintptr is filled.
1791 for nb <= sys.PtrSize*8 {
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
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
1819 *dst = uint8(bits&0xf | bitScanAll)
1827 // Add final fragment to bit buffer.
1830 bits |= pattern << nbits
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
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
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
1858 // Final src fragment.
1860 bits |= (uintptr(*src) & (1<<c - 1)) << nbits
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
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
1877 *dst = uint8(bits&0xf | bitScanAll)
1881 // Final src fragment.
1883 bits |= (uintptr(*src) & (1<<c - 1)) << nbits
1889 // Write any final bits out, using full-byte writes, even for the final byte.
1890 var totalBits uintptr
1892 totalBits = (uintptr(unsafe.Pointer(dst))-uintptr(unsafe.Pointer(dstStart)))*8 + nbits
1894 for ; nbits > 0; nbits -= 8 {
1900 totalBits = (uintptr(unsafe.Pointer(dst))-uintptr(unsafe.Pointer(dstStart)))*4 + nbits
1902 for ; nbits > 0; nbits -= 4 {
1903 v := bits&0xf | bitScanAll
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)
1922 func dematerializeGCProg(s *mspan) {
1923 mheap_.freeManual(s, &memstats.gc_sys)
1926 func dumpGCProg(p *byte) {
1932 print("\t", nptr, " end\n")
1936 print("\t", nptr, " lit ", x, ":")
1938 for i := 0; i < n; i++ {
1945 nbit := int(x &^ 0x80)
1947 for nb := uint(0); ; nb += 7 {
1950 nbit |= int(x&0x7f) << nb
1957 for nb := uint(0); ; nb += 7 {
1960 count |= int(x&0x7f) << nb
1965 print("\t", nptr, " repeat ", nbit, " × ", count, "\n")
1966 nptr += nbit * count
1973 func getgcmaskcb(frame *stkframe, ctxt unsafe.Pointer) bool {
1974 target := (*stkframe)(ctxt)
1975 if frame.sp <= target.sp && target.sp < frame.varp {
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 {
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]
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) {
2003 for _, datap := range activeModules() {
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
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
2030 if base, s, _ := findObject(uintptr(p), 0, 0); base != 0 {
2031 hbits := heapBitsForAddr(base)
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
2038 if i != 1*sys.PtrSize && !hbits.morePointers() {
2039 mask = mask[:i/sys.PtrSize]
2042 hbits = hbits.next()
2048 if _g_ := getg(); _g_.m.curg.stack.lo <= uintptr(p) && uintptr(p) < _g_.m.curg.stack.hi {
2050 frame.sp = uintptr(p)
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)
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)
2069 // otherwise, not something the GC knows about.
2070 // possibly read-only data, like malloc(0).
2071 // must not have pointers