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 allocated heap comes from a subset of the memory in the range [start, used),
17 // where start == mheap_.arena_start and used == mheap_.arena_used.
18 // The heap bitmap comprises 2 bits for each pointer-sized word in that range,
19 // stored in bytes indexed backward in memory from start.
20 // That is, the byte at address start-1 holds the 2-bit entries for the four words
21 // start through start+3*ptrSize, the byte at start-2 holds the entries for
22 // start+4*ptrSize through start+7*ptrSize, and so on.
24 // In each 2-bit entry, the lower bit holds the same information as in the 1-bit
25 // bitmaps: 0 means uninteresting and 1 means live pointer to be visited during GC.
26 // The meaning of the high bit depends on the position of the word being described
27 // in its allocated object. In the first word, the high bit is unused.
28 // In the second word, the high bit is the GC ``checkmarked'' bit (see below).
29 // In the third and later words, the high bit indicates that the object is still
30 // being described. In these words, if a bit pair with a high bit 0 is encountered,
31 // the low bit can also be assumed to be 0, and the object description is over.
32 // This 00 is called the ``dead'' encoding: it signals that the rest of the words
33 // in the object are uninteresting to the garbage collector.
35 // The 2-bit entries are split when written into the byte, so that the top half
36 // of the byte contains 4 high bits and the bottom half contains 4 low (pointer)
38 // This form allows a copy from the 1-bit to the 4-bit form to keep the
39 // pointer bits contiguous, instead of having to space them out.
41 // The code makes use of the fact that the zero value for a heap bitmap
42 // has no live pointer bit set and is (depending on position), not used,
43 // not checkmarked, and is the dead encoding.
44 // These properties must be preserved when modifying the encoding.
48 // In a concurrent garbage collector, one worries about failing to mark
49 // a live object due to mutations without write barriers or bugs in the
50 // collector implementation. As a sanity check, the GC has a 'checkmark'
51 // mode that retraverses the object graph with the world stopped, to make
52 // sure that everything that should be marked is marked.
53 // In checkmark mode, in the heap bitmap, the high bit of the 2-bit entry
54 // for the second word of the object holds the checkmark bit.
55 // When not in checkmark mode, this bit is set to 1.
57 // The smallest possible allocation is 8 bytes. On a 32-bit machine, that
58 // means every allocated object has two words, so there is room for the
59 // checkmark bit. On a 64-bit machine, however, the 8-byte allocation is
60 // just one word, so the second bit pair is not available for encoding the
61 // checkmark. However, because non-pointer allocations are combined
62 // into larger 16-byte (maxTinySize) allocations, a plain 8-byte allocation
63 // must be a pointer, so the type bit in the first word is not actually needed.
64 // It is still used in general, except in checkmark the type bit is repurposed
65 // as the checkmark bit and then reinitialized (to 1) as the type bit when
72 "runtime/internal/atomic"
73 "runtime/internal/sys"
81 heapBitsShift = 1 // shift offset between successive bitPointer or bitMarked entries
82 heapBitmapScale = sys.PtrSize * (8 / 2) // number of data bytes described by one heap bitmap byte
84 // all mark/pointer bits in a byte
85 bitMarkedAll = bitMarked | bitMarked<<heapBitsShift | bitMarked<<(2*heapBitsShift) | bitMarked<<(3*heapBitsShift)
86 bitPointerAll = bitPointer | bitPointer<<heapBitsShift | bitPointer<<(2*heapBitsShift) | bitPointer<<(3*heapBitsShift)
89 // addb returns the byte pointer p+n.
92 func addb(p *byte, n uintptr) *byte {
93 // Note: wrote out full expression instead of calling add(p, n)
94 // to reduce the number of temporaries generated by the
95 // compiler for this trivial expression during inlining.
96 return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) + n))
99 // subtractb returns the byte pointer p-n.
100 // subtractb is typically used when traversing the pointer tables referred to by hbits
101 // which are arranged in reverse order.
104 func subtractb(p *byte, n uintptr) *byte {
105 // Note: wrote out full expression instead of calling add(p, -n)
106 // to reduce the number of temporaries generated by the
107 // compiler for this trivial expression during inlining.
108 return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) - n))
111 // add1 returns the byte pointer p+1.
114 func add1(p *byte) *byte {
115 // Note: wrote out full expression instead of calling addb(p, 1)
116 // to reduce the number of temporaries generated by the
117 // compiler for this trivial expression during inlining.
118 return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) + 1))
121 // subtract1 returns the byte pointer p-1.
122 // subtract1 is typically used when traversing the pointer tables referred to by hbits
123 // which are arranged in reverse order.
126 // nosplit because it is used during write barriers and must not be preempted.
128 func subtract1(p *byte) *byte {
129 // Note: wrote out full expression instead of calling subtractb(p, 1)
130 // to reduce the number of temporaries generated by the
131 // compiler for this trivial expression during inlining.
132 return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) - 1))
135 // mHeap_MapBits is called each time arena_used is extended.
136 // It maps any additional bitmap memory needed for the new arena memory.
137 // It must be called with the expected new value of arena_used,
138 // *before* h.arena_used has been updated.
139 // Waiting to update arena_used until after the memory has been mapped
140 // avoids faults when other threads try access the bitmap immediately
141 // after observing the change to arena_used.
144 func (h *mheap) mapBits(arena_used uintptr) {
145 // Caller has added extra mappings to the arena.
146 // Add extra mappings of bitmap words as needed.
147 // We allocate extra bitmap pieces in chunks of bitmapChunk.
148 const bitmapChunk = 8192
150 n := (arena_used - mheap_.arena_start) / heapBitmapScale
151 n = round(n, bitmapChunk)
152 n = round(n, sys.PhysPageSize)
153 if h.bitmap_mapped >= n {
157 sysMap(unsafe.Pointer(h.arena_start-n), n-h.bitmap_mapped, h.arena_reserved, &memstats.gc_sys)
161 // heapBits provides access to the bitmap bits for a single heap word.
162 // The methods on heapBits take value receivers so that the compiler
163 // can more easily inline calls to those methods and registerize the
164 // struct fields independently.
165 type heapBits struct {
170 // markBits provides access to the mark bit for an object in the heap.
171 // bytep points to the byte holding the mark bit.
172 // mask is a byte with a single bit set that can be &ed with *bytep
173 // to see if the bit has been set.
174 // *m.byte&m.mask != 0 indicates the mark bit is set.
175 // index can be used along with span information to generate
176 // the address of the object in the heap.
177 // We maintain one set of mark bits for allocation and one for
179 type markBits struct {
186 func (s *mspan) allocBitsForIndex(allocBitIndex uintptr) markBits {
187 whichByte := allocBitIndex / 8
188 whichBit := allocBitIndex % 8
189 return markBits{&s.allocBits[whichByte], uint8(1 << whichBit), allocBitIndex}
192 // ctzVals contains the count of trailing zeros for the
193 // index. 0 returns 8 indicating 8 zeros.
194 var ctzVals = [256]int8{
195 8, 0, 1, 0, 2, 0, 1, 0,
196 3, 0, 1, 0, 2, 0, 1, 0,
197 4, 0, 1, 0, 2, 0, 1, 0,
198 3, 0, 1, 0, 2, 0, 1, 0,
199 5, 0, 1, 0, 2, 0, 1, 0,
200 3, 0, 1, 0, 2, 0, 1, 0,
201 4, 0, 1, 0, 2, 0, 1, 0,
202 3, 0, 1, 0, 2, 0, 1, 0,
203 6, 0, 1, 0, 2, 0, 1, 0,
204 3, 0, 1, 0, 2, 0, 1, 0,
205 4, 0, 1, 0, 2, 0, 1, 0,
206 3, 0, 1, 0, 2, 0, 1, 0,
207 5, 0, 1, 0, 2, 0, 1, 0,
208 3, 0, 1, 0, 2, 0, 1, 0,
209 4, 0, 1, 0, 2, 0, 1, 0,
210 3, 0, 1, 0, 2, 0, 1, 0,
211 7, 0, 1, 0, 2, 0, 1, 0,
212 3, 0, 1, 0, 2, 0, 1, 0,
213 4, 0, 1, 0, 2, 0, 1, 0,
214 3, 0, 1, 0, 2, 0, 1, 0,
215 5, 0, 1, 0, 2, 0, 1, 0,
216 3, 0, 1, 0, 2, 0, 1, 0,
217 4, 0, 1, 0, 2, 0, 1, 0,
218 3, 0, 1, 0, 2, 0, 1, 0,
219 6, 0, 1, 0, 2, 0, 1, 0,
220 3, 0, 1, 0, 2, 0, 1, 0,
221 4, 0, 1, 0, 2, 0, 1, 0,
222 3, 0, 1, 0, 2, 0, 1, 0,
223 5, 0, 1, 0, 2, 0, 1, 0,
224 3, 0, 1, 0, 2, 0, 1, 0,
225 4, 0, 1, 0, 2, 0, 1, 0,
226 3, 0, 1, 0, 2, 0, 1, 0}
228 // A temporary stand in for the count trailing zero ctz instruction.
229 // IA bsf works on 64 bit non-zero word.
230 func ctz64(markBits uint64) uint64 {
231 ctz8 := ctzVals[markBits&0xff]
234 } else if markBits == 0 { // low byte is zero check fill word.
235 return 64 // bits in 64 bit word, ensures loop terminates
239 for ctz8 = ctzVals[markBits&0xff]; ctz8 == 8; ctz8 = ctzVals[markBits&0xff] {
243 result += uint64(ctz8)
247 // refillAllocCache takes 8 bytes s.allocBits starting at whichByte
248 // and negates them so that ctz (count trailing zeros) instructions
249 // can be used. It then places these 8 bytes into the cached 64 bit
251 func (s *mspan) refillAllocCache(whichByte uintptr) {
252 bytes := s.allocBits[whichByte : whichByte+8]
254 aCache |= uint64(bytes[0])
255 aCache |= uint64(bytes[1]) << (1 * 8)
256 aCache |= uint64(bytes[2]) << (2 * 8)
257 aCache |= uint64(bytes[3]) << (3 * 8)
258 aCache |= uint64(bytes[4]) << (4 * 8)
259 aCache |= uint64(bytes[5]) << (5 * 8)
260 aCache |= uint64(bytes[6]) << (6 * 8)
261 aCache |= uint64(bytes[7]) << (7 * 8)
262 s.allocCache = ^aCache
265 // nextFreeIndex returns the index of the next free object in s at
266 // or after s.freeindex.
267 // There are hardware instructions that can be used to make this
268 // faster if profiling warrants it.
269 func (s *mspan) nextFreeIndex() uintptr {
270 sfreeindex := s.freeindex
272 if sfreeindex == snelems {
275 if sfreeindex > snelems {
276 throw("s.freeindex > s.nelems")
279 aCache := s.allocCache
280 bitIndex := ctz64(aCache)
282 // Move index to start of next cached bits.
283 sfreeindex = (sfreeindex + 64) &^ (64 - 1)
284 if sfreeindex >= snelems {
285 s.freeindex = snelems
288 whichByte := sfreeindex / 8
289 // Refill s.allocCache with the next 64 alloc bits.
290 s.refillAllocCache(whichByte)
291 aCache = s.allocCache
292 bitIndex = ctz64(aCache)
293 // Nothing was available try again now allocCache has been refilled.
295 result := sfreeindex + uintptr(bitIndex)
296 if result >= snelems {
297 s.freeindex = snelems
301 s.allocCache >>= (bitIndex + 1)
302 sfreeindex = result + 1
304 if sfreeindex%64 == 0 && sfreeindex != snelems {
305 // We just incremented s.freeindex so it isn't 0.
306 // As each 1 in s.allocCache was encountered and used for allocation
307 // it was shifted away. At this point s.allocCache contains all 0s.
308 // Refill s.allocCache so that it corresponds
309 // to the bits at s.allocBits starting at s.freeindex.
310 whichByte := sfreeindex / 8
311 s.refillAllocCache(whichByte)
313 s.freeindex = sfreeindex
317 func (s *mspan) isFree(index uintptr) bool {
318 whichByte := index / 8
319 whichBit := index % 8
320 return s.allocBits[whichByte]&uint8(1<<whichBit) == 0
323 func markBitsForAddr(p uintptr) markBits {
325 return s.markBitsForAddr(p)
328 func (s *mspan) markBitsForAddr(p uintptr) markBits {
329 byteOffset := p - s.base()
330 markBitIndex := uintptr(0)
332 // markBitIndex := (p - s.base()) / s.elemsize, using division by multiplication
333 markBitIndex = uintptr(uint64(byteOffset) >> s.divShift * uint64(s.divMul) >> s.divShift2)
335 whichByte := markBitIndex / 8
336 whichBit := markBitIndex % 8
337 return markBits{&s.gcmarkBits[whichByte], uint8(1 << whichBit), markBitIndex}
340 func (s *mspan) markBitsForBase() markBits {
341 return markBits{&s.gcmarkBits[0], uint8(1), 0}
344 // isMarked reports whether mark bit m is set.
345 func (m markBits) isMarked() bool {
346 return *m.bytep&m.mask != 0
349 // setMarked sets the marked bit in the markbits, atomically.
350 func (m markBits) setMarked() {
351 // Might be racing with other updates, so use atomic update always.
352 // We used to be clever here and use a non-atomic update in certain
353 // cases, but it's not worth the risk.
354 atomic.Or8(m.bytep, m.mask)
357 // setMarkedNonAtomic sets the marked bit in the markbits, non-atomically.
358 func (m markBits) setMarkedNonAtomic() {
362 // clearMarked clears the marked bit in the markbits, atomically.
363 func (m markBits) clearMarked() {
364 // Might be racing with other updates, so use atomic update always.
365 // We used to be clever here and use a non-atomic update in certain
366 // cases, but it's not worth the risk.
367 atomic.And8(m.bytep, ^m.mask)
370 // clearMarkedNonAtomic clears the marked bit non-atomically.
371 func (m markBits) clearMarkedNonAtomic() {
375 // markBitsForSpan returns the markBits for the span base address base.
376 func markBitsForSpan(base uintptr) (mbits markBits) {
377 if base < mheap_.arena_start || base >= mheap_.arena_used {
378 throw("heapBitsForSpan: base out of range")
380 mbits = markBitsForAddr(base)
382 throw("markBitsForSpan: unaligned start")
387 // advance advances the markBits to the next object in the span.
388 func (m *markBits) advance() {
390 m.bytep = (*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(m.bytep)) + 1))
398 // heapBitsForAddr returns the heapBits for the address addr.
399 // The caller must have already checked that addr is in the range [mheap_.arena_start, mheap_.arena_used).
401 // nosplit because it is used during write barriers and must not be preempted.
403 func heapBitsForAddr(addr uintptr) heapBits {
404 // 2 bits per work, 4 pairs per byte, and a mask is hard coded.
405 off := (addr - mheap_.arena_start) / sys.PtrSize
406 return heapBits{(*uint8)(unsafe.Pointer(mheap_.arena_start - off/4 - 1)), uint32(off & 3)}
409 // heapBitsForSpan returns the heapBits for the span base address base.
410 func heapBitsForSpan(base uintptr) (hbits heapBits) {
411 if base < mheap_.arena_start || base >= mheap_.arena_used {
412 throw("heapBitsForSpan: base out of range")
414 return heapBitsForAddr(base)
417 // heapBitsForObject returns the base address for the heap object
418 // containing the address p, along with the heapBits for base.
419 // If p does not point into a heap object,
421 // otherwise return the base of the object.
423 // refBase and refOff optionally give the base address of the object
424 // in which the pointer p was found and the byte offset at which it
425 // was found. These are used for error reporting.
426 func heapBitsForObject(p, refBase, refOff uintptr) (base uintptr, hbits heapBits, s *mspan) {
427 arenaStart := mheap_.arena_start
428 if p < arenaStart || p >= mheap_.arena_used {
431 off := p - arenaStart
432 idx := off >> _PageShift
433 // p points into the heap, but possibly to the middle of an object.
434 // Consult the span table to find the block beginning.
437 if s == nil || pageID(k) < s.start || p >= s.limit || s.state != mSpanInUse {
438 if s == nil || s.state == _MSpanStack {
439 // If s is nil, the virtual address has never been part of the heap.
440 // This pointer may be to some mmap'd region, so we allow it.
441 // Pointers into stacks are also ok, the runtime manages these explicitly.
445 // The following ensures that we are rigorous about what data
446 // structures hold valid pointers.
447 if debug.invalidptr != 0 {
448 // Typically this indicates an incorrect use
449 // of unsafe or cgo to store a bad pointer in
450 // the Go heap. It may also indicate a runtime
453 // TODO(austin): We could be more aggressive
454 // and detect pointers to unallocated objects
455 // in allocated spans.
457 print("runtime: pointer ", hex(p))
458 if s.state != mSpanInUse {
459 print(" to unallocated span")
461 print(" to unused region of span")
463 print("idx=", hex(idx), " span.base()=", hex(s.base()), " span.limit=", hex(s.limit), " span.state=", s.state, "\n")
465 print("runtime: found in object at *(", hex(refBase), "+", hex(refOff), ")\n")
466 gcDumpObject("object", refBase, refOff)
468 throw("found bad pointer in Go heap (incorrect use of unsafe or cgo?)")
472 // If this span holds object of a power of 2 size, just mask off the bits to
473 // the interior of the object. Otherwise use the size to get the base.
475 // optimize for power of 2 sized objects.
477 base = base + (p-base)&s.baseMask
478 // base = p & s.baseMask is faster for small spans,
479 // but doesn't work for large spans.
480 // Overall, it's faster to use the more general computation above.
483 if p-base >= s.elemsize {
484 // n := (p - base) / s.elemsize, using division by multiplication
485 n := uintptr(uint64(p-base) >> s.divShift * uint64(s.divMul) >> s.divShift2)
486 base += n * s.elemsize
489 // Now that we know the actual base, compute heapBits to return to caller.
490 hbits = heapBitsForAddr(base)
494 // prefetch the bits.
495 func (h heapBits) prefetch() {
496 prefetchnta(uintptr(unsafe.Pointer((h.bitp))))
499 // next returns the heapBits describing the next pointer-sized word in memory.
500 // That is, if h describes address p, h.next() describes p+ptrSize.
501 // Note that next does not modify h. The caller must record the result.
503 // nosplit because it is used during write barriers and must not be preempted.
505 func (h heapBits) next() heapBits {
506 if h.shift < 3*heapBitsShift {
507 return heapBits{h.bitp, h.shift + heapBitsShift}
509 return heapBits{subtract1(h.bitp), 0}
512 // forward returns the heapBits describing n pointer-sized words ahead of h in memory.
513 // That is, if h describes address p, h.forward(n) describes p+n*ptrSize.
514 // h.forward(1) is equivalent to h.next(), just slower.
515 // Note that forward does not modify h. The caller must record the result.
516 // bits returns the heap bits for the current word.
517 func (h heapBits) forward(n uintptr) heapBits {
518 n += uintptr(h.shift) / heapBitsShift
519 return heapBits{subtractb(h.bitp, n/4), uint32(n%4) * heapBitsShift}
522 // The caller can test isMarked and isPointer by &-ing with bitMarked and bitPointer.
523 // The result includes in its higher bits the bits for subsequent words
524 // described by the same bitmap byte.
525 func (h heapBits) bits() uint32 {
526 // The (shift & 31) eliminates a test and conditional branch
527 // from the generated code.
528 return uint32(*h.bitp) >> (h.shift & 31)
531 // morePointers returns true if this word and all remaining words in this object
533 // h must not describe the first or second word of the object.
534 func (h heapBits) morePointers() bool {
535 return *h.bitp&(bitMarked<<h.shift) != 0
538 // isPointer reports whether the heap bits describe a pointer word.
539 // h must describe the initial word of the object.
541 // nosplit because it is used during write barriers and must not be preempted.
543 func (h heapBits) isPointer() bool {
544 return (*h.bitp>>h.shift)&bitPointer != 0
547 // hasPointers reports whether the given object has any pointers.
548 // It must be told how large the object at h is, so that it does not read too
549 // far into the bitmap.
550 // h must describe the initial word of the object.
551 func (h heapBits) hasPointers(size uintptr) bool {
552 if size == sys.PtrSize { // 1-word objects are always pointers
555 // Otherwise, at least a 2-word object, and at least 2-word aligned,
556 // so h.shift is either 0 or 2, so we know we can get the bits for the
557 // first two words out of *h.bitp.
558 // If either of the first two words is a pointer, not pointer free.
559 b := uint32(*h.bitp >> h.shift)
560 if b&(bitPointer|bitPointer<<heapBitsShift) != 0 {
563 if size == 2*sys.PtrSize {
566 // At least a 4-word object. Check scan bit (aka marked bit) in third word.
568 return b&(bitMarked<<(2*heapBitsShift)) != 0
570 return uint32(*subtract1(h.bitp))&bitMarked != 0
573 // isCheckmarked reports whether the heap bits have the checkmarked bit set.
574 // It must be told how large the object at h is, because the encoding of the
575 // checkmark bit varies by size.
576 // h must describe the initial word of the object.
577 func (h heapBits) isCheckmarked(size uintptr) bool {
578 if size == sys.PtrSize {
579 return (*h.bitp>>h.shift)&bitPointer != 0
581 // All multiword objects are 2-word aligned,
582 // so we know that the initial word's 2-bit pair
583 // and the second word's 2-bit pair are in the
584 // same heap bitmap byte, *h.bitp.
585 return (*h.bitp>>(heapBitsShift+h.shift))&bitMarked != 0
588 // setCheckmarked sets the checkmarked bit.
589 // It must be told how large the object at h is, because the encoding of the
590 // checkmark bit varies by size.
591 // h must describe the initial word of the object.
592 func (h heapBits) setCheckmarked(size uintptr) {
593 if size == sys.PtrSize {
594 atomic.Or8(h.bitp, bitPointer<<h.shift)
597 atomic.Or8(h.bitp, bitMarked<<(heapBitsShift+h.shift))
600 // heapBitsBulkBarrier executes writebarrierptr_nostore
601 // for every pointer slot in the memory range [p, p+size),
602 // using the heap, data, or BSS bitmap to locate those pointer slots.
603 // This executes the write barriers necessary after a memmove.
604 // Both p and size must be pointer-aligned.
605 // The range [p, p+size) must lie within a single object.
607 // Callers should call heapBitsBulkBarrier immediately after
608 // calling memmove(p, src, size). This function is marked nosplit
609 // to avoid being preempted; the GC must not stop the goroutine
610 // between the memmove and the execution of the barriers.
612 // The heap bitmap is not maintained for allocations containing
613 // no pointers at all; any caller of heapBitsBulkBarrier must first
614 // make sure the underlying allocation contains pointers, usually
615 // by checking typ.kind&kindNoPointers.
618 func heapBitsBulkBarrier(p, size uintptr) {
619 if (p|size)&(sys.PtrSize-1) != 0 {
620 throw("heapBitsBulkBarrier: unaligned arguments")
622 if !writeBarrier.needed {
626 // If p is on the stack and in a higher frame than the
627 // caller, we either need to execute write barriers on
628 // it (which is what happens for normal stack writes
629 // through pointers to higher frames), or we need to
630 // force the mark termination stack scan to scan the
631 // frame containing p.
633 // Executing write barriers on p is complicated in the
634 // general case because we either need to unwind the
635 // stack to get the stack map, or we need the type's
636 // bitmap, which may be a GC program.
638 // Hence, we opt for forcing the re-scan to scan the
639 // frame containing p, which we can do by simply
640 // unwinding the stack barriers between the current SP
643 if gp != nil && gp.stack.lo <= p && p < gp.stack.hi {
644 // Run on the system stack to give it more
647 gcUnwindBarriers(gp, p)
652 // If p is a global, use the data or BSS bitmaps to
653 // execute write barriers.
654 for datap := &firstmoduledata; datap != nil; datap = datap.next {
655 if datap.data <= p && p < datap.edata {
656 bulkBarrierBitmap(p, size, p-datap.data, datap.gcdatamask.bytedata)
660 for datap := &firstmoduledata; datap != nil; datap = datap.next {
661 if datap.bss <= p && p < datap.ebss {
662 bulkBarrierBitmap(p, size, p-datap.bss, datap.gcbssmask.bytedata)
669 h := heapBitsForAddr(p)
670 for i := uintptr(0); i < size; i += sys.PtrSize {
672 x := (*uintptr)(unsafe.Pointer(p + i))
673 writebarrierptr_nostore(x, *x)
679 // bulkBarrierBitmap executes write barriers for [p, p+size) using a
680 // 1-bit pointer bitmap. p is assumed to start maskOffset bytes into
681 // the data covered by the bitmap in bits.
683 // This is used by heapBitsBulkBarrier for writes to data and BSS.
686 func bulkBarrierBitmap(p, size, maskOffset uintptr, bits *uint8) {
687 word := maskOffset / sys.PtrSize
688 bits = addb(bits, word/8)
689 mask := uint8(1) << (word % 8)
691 for i := uintptr(0); i < size; i += sys.PtrSize {
702 x := (*uintptr)(unsafe.Pointer(p + i))
703 writebarrierptr_nostore(x, *x)
709 // typeBitsBulkBarrier executes writebarrierptr_nostore
710 // for every pointer slot in the memory range [p, p+size),
711 // using the type bitmap to locate those pointer slots.
712 // The type typ must correspond exactly to [p, p+size).
713 // This executes the write barriers necessary after a copy.
714 // Both p and size must be pointer-aligned.
715 // The type typ must have a plain bitmap, not a GC program.
716 // The only use of this function is in channel sends, and the
717 // 64 kB channel element limit takes care of this for us.
719 // Must not be preempted because it typically runs right after memmove,
720 // and the GC must not complete between those two.
723 func typeBitsBulkBarrier(typ *_type, p, size uintptr) {
725 throw("runtime: typeBitsBulkBarrier without type")
727 if typ.size != size {
728 println("runtime: typeBitsBulkBarrier with type ", typ.string(), " of size ", typ.size, " but memory size", size)
729 throw("runtime: invalid typeBitsBulkBarrier")
731 if typ.kind&kindGCProg != 0 {
732 println("runtime: typeBitsBulkBarrier with type ", typ.string(), " with GC prog")
733 throw("runtime: invalid typeBitsBulkBarrier")
735 if !writeBarrier.needed {
738 ptrmask := typ.gcdata
740 for i := uintptr(0); i < typ.ptrdata; i += sys.PtrSize {
741 if i&(sys.PtrSize*8-1) == 0 {
742 bits = uint32(*ptrmask)
743 ptrmask = addb(ptrmask, 1)
748 x := (*uintptr)(unsafe.Pointer(p + i))
749 writebarrierptr_nostore(x, *x)
754 func (s *mspan) clearGCMarkBits() {
755 bytesInMarkBits := (s.nelems + 7) / 8
756 bits := s.gcmarkBits[:bytesInMarkBits]
757 for i := range bits {
762 func (s *mspan) clearAllocBits() {
763 bytesInMarkBits := (s.nelems + 7) / 8
764 bits := s.allocBits[:bytesInMarkBits]
765 for i := range bits {
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 mark and checkmark bits.
780 // If this is a span of pointer-sized objects, it initializes all
781 // words to pointer (and there are no dead bits).
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
787 s.allocBits = &s.markbits1
788 s.gcmarkBits = &s.markbits2
790 s.allocCache = ^uint64(0) // all 1s indicating all free.
795 // Clear bits corresponding to objects.
796 if total%heapBitmapScale != 0 {
797 throw("initSpan: unaligned length")
799 nbyte := total / heapBitmapScale
800 if sys.PtrSize == 8 && size == sys.PtrSize {
802 bitp := subtractb(end, nbyte-1)
804 *bitp = bitPointerAll
812 memclr(unsafe.Pointer(subtractb(h.bitp, nbyte-1)), nbyte)
815 // initCheckmarkSpan initializes a span for being checkmarked.
816 // It clears the checkmark bits, which are set to 1 in normal operation.
817 func (h heapBits) initCheckmarkSpan(size, n, total uintptr) {
818 // The ptrSize == 8 is a compile-time constant false on 32-bit and eliminates this code entirely.
819 if sys.PtrSize == 8 && size == sys.PtrSize {
820 // Checkmark bit is type bit, bottom bit of every 2-bit entry.
821 // Only possible on 64-bit system, since minimum size is 8.
822 // Must clear type bit (checkmark bit) of every word.
823 // The type bit is the lower of every two-bit pair.
825 for i := uintptr(0); i < n; i += 4 {
826 *bitp &^= bitPointerAll
827 bitp = subtract1(bitp)
831 for i := uintptr(0); i < n; i++ {
832 *h.bitp &^= bitMarked << (heapBitsShift + h.shift)
833 h = h.forward(size / sys.PtrSize)
837 // clearCheckmarkSpan undoes all the checkmarking in a span.
838 // The actual checkmark bits are ignored, so the only work to do
839 // is to fix the pointer bits. (Pointer bits are ignored by scanobject
840 // but consulted by typedmemmove.)
841 func (h heapBits) clearCheckmarkSpan(size, n, total uintptr) {
842 // The ptrSize == 8 is a compile-time constant false on 32-bit and eliminates this code entirely.
843 if sys.PtrSize == 8 && size == sys.PtrSize {
844 // Checkmark bit is type bit, bottom bit of every 2-bit entry.
845 // Only possible on 64-bit system, since minimum size is 8.
846 // Must clear type bit (checkmark bit) of every word.
847 // The type bit is the lower of every two-bit pair.
849 for i := uintptr(0); i < n; i += 4 {
850 *bitp |= bitPointerAll
851 bitp = subtract1(bitp)
856 // oneBitCount is indexed by byte and produces the
857 // number of 1 bits in that byte. For example 128 has 1 bit set
858 // and oneBitCount[128] will holds 1.
859 var oneBitCount = [256]uint8{
860 0, 1, 1, 2, 1, 2, 2, 3,
861 1, 2, 2, 3, 2, 3, 3, 4,
862 1, 2, 2, 3, 2, 3, 3, 4,
863 2, 3, 3, 4, 3, 4, 4, 5,
864 1, 2, 2, 3, 2, 3, 3, 4,
865 2, 3, 3, 4, 3, 4, 4, 5,
866 2, 3, 3, 4, 3, 4, 4, 5,
867 3, 4, 4, 5, 4, 5, 5, 6,
868 1, 2, 2, 3, 2, 3, 3, 4,
869 2, 3, 3, 4, 3, 4, 4, 5,
870 2, 3, 3, 4, 3, 4, 4, 5,
871 3, 4, 4, 5, 4, 5, 5, 6,
872 2, 3, 3, 4, 3, 4, 4, 5,
873 3, 4, 4, 5, 4, 5, 5, 6,
874 3, 4, 4, 5, 4, 5, 5, 6,
875 4, 5, 5, 6, 5, 6, 6, 7,
876 1, 2, 2, 3, 2, 3, 3, 4,
877 2, 3, 3, 4, 3, 4, 4, 5,
878 2, 3, 3, 4, 3, 4, 4, 5,
879 3, 4, 4, 5, 4, 5, 5, 6,
880 2, 3, 3, 4, 3, 4, 4, 5,
881 3, 4, 4, 5, 4, 5, 5, 6,
882 3, 4, 4, 5, 4, 5, 5, 6,
883 4, 5, 5, 6, 5, 6, 6, 7,
884 2, 3, 3, 4, 3, 4, 4, 5,
885 3, 4, 4, 5, 4, 5, 5, 6,
886 3, 4, 4, 5, 4, 5, 5, 6,
887 4, 5, 5, 6, 5, 6, 6, 7,
888 3, 4, 4, 5, 4, 5, 5, 6,
889 4, 5, 5, 6, 5, 6, 6, 7,
890 4, 5, 5, 6, 5, 6, 6, 7,
891 5, 6, 6, 7, 6, 7, 7, 8}
893 // countFree runs through the mark bits in a span and counts the number of free objects
895 // TODO:(rlh) Use popcount intrinsic.
896 func (s *mspan) countFree() int {
898 maxIndex := s.nelems / 8
899 for i := uintptr(0); i < maxIndex; i++ {
900 count += int(oneBitCount[s.gcmarkBits[i]])
903 if bitsInLastByte := s.nelems % 8; bitsInLastByte != 0 {
904 markBits := uint8(s.gcmarkBits[maxIndex])
905 mask := uint8((1 << bitsInLastByte) - 1)
906 bits := markBits & mask
907 count += int(oneBitCount[bits])
909 return int(s.nelems) - count
912 // heapBitsSetType records that the new allocation [x, x+size)
913 // holds in [x, x+dataSize) one or more values of type typ.
914 // (The number of values is given by dataSize / typ.size.)
915 // If dataSize < size, the fragment [x+dataSize, x+size) is
916 // recorded as non-pointer data.
917 // It is known that the type has pointers somewhere;
918 // malloc does not call heapBitsSetType when there are no pointers,
919 // because all free objects are marked as noscan during
920 // heapBitsSweepSpan.
921 // There can only be one allocation from a given span active at a time,
922 // so this code is not racing with other instances of itself,
923 // and we don't allocate from a span until it has been swept,
924 // so this code is not racing with heapBitsSweepSpan.
925 // It is, however, racing with the concurrent GC mark phase,
926 // which can be setting the mark bit in the leading 2-bit entry
927 // of an allocated block. The block we are modifying is not quite
928 // allocated yet, so the GC marker is not racing with updates to x's bits,
929 // but if the start or end of x shares a bitmap byte with an adjacent
930 // object, the GC marker is racing with updates to those object's mark bits.
931 func heapBitsSetType(x, size, dataSize uintptr, typ *_type) {
932 const doubleCheck = false // slow but helpful; enable to test modifications to this code
934 // dataSize is always size rounded up to the next malloc size class,
935 // except in the case of allocating a defer block, in which case
936 // size is sizeof(_defer{}) (at least 6 words) and dataSize may be
937 // arbitrarily larger.
939 // The checks for size == sys.PtrSize and size == 2*sys.PtrSize can therefore
940 // assume that dataSize == size without checking it explicitly.
942 if sys.PtrSize == 8 && size == sys.PtrSize {
943 // It's one word and it has pointers, it must be a pointer.
944 // In general we'd need an atomic update here if the
945 // concurrent GC were marking objects in this span,
946 // because each bitmap byte describes 3 other objects
947 // in addition to the one being allocated.
948 // However, since all allocated one-word objects are pointers
949 // (non-pointers are aggregated into tinySize allocations),
950 // initSpan sets the pointer bits for us. Nothing to do here.
952 h := heapBitsForAddr(x)
954 throw("heapBitsSetType: pointer bit missing")
960 h := heapBitsForAddr(x)
961 ptrmask := typ.gcdata // start of 1-bit pointer mask (or GC program, handled below)
963 // Heap bitmap bits for 2-word object are only 4 bits,
964 // so also shared with objects next to it; use atomic updates.
965 // This is called out as a special case primarily for 32-bit systems,
966 // so that on 32-bit systems the code below can assume all objects
967 // are 4-word aligned (because they're all 16-byte aligned).
968 if size == 2*sys.PtrSize {
969 if typ.size == sys.PtrSize {
970 // We're allocating a block big enough to hold two pointers.
971 // On 64-bit, that means the actual object must be two pointers,
972 // or else we'd have used the one-pointer-sized block.
973 // On 32-bit, however, this is the 8-byte block, the smallest one.
974 // So it could be that we're allocating one pointer and this was
975 // just the smallest block available. Distinguish by checking dataSize.
976 // (In general the number of instances of typ being allocated is
977 // dataSize/typ.size.)
978 if sys.PtrSize == 4 && dataSize == sys.PtrSize {
979 // 1 pointer object. On 32-bit machines clear the bit for the
980 // unused second word.
981 if gcphase == _GCoff {
982 *h.bitp &^= (bitPointer | bitMarked | ((bitPointer | bitMarked) << heapBitsShift)) << h.shift
983 *h.bitp |= bitPointer << h.shift
985 atomic.And8(h.bitp, ^uint8((bitPointer|bitMarked|((bitPointer|bitMarked)<<heapBitsShift))<<h.shift))
986 atomic.Or8(h.bitp, bitPointer<<h.shift)
989 // 2-element slice of pointer.
990 if gcphase == _GCoff {
991 *h.bitp |= (bitPointer | bitPointer<<heapBitsShift) << h.shift
993 atomic.Or8(h.bitp, (bitPointer|bitPointer<<heapBitsShift)<<h.shift)
998 // Otherwise typ.size must be 2*sys.PtrSize,
999 // and typ.kind&kindGCProg == 0.
1001 if typ.size != 2*sys.PtrSize || typ.kind&kindGCProg != 0 {
1002 print("runtime: heapBitsSetType size=", size, " but typ.size=", typ.size, " gcprog=", typ.kind&kindGCProg != 0, "\n")
1003 throw("heapBitsSetType")
1006 b := uint32(*ptrmask)
1008 if gcphase == _GCoff {
1009 // bitPointer == 1, bitMarked is 1 << 4, heapBitsShift is 1.
1010 // 110011 is shifted h.shift and complemented.
1011 // This clears out the bits that are about to be
1012 // ored into *h.hbitp in the next instructions.
1013 *h.bitp &^= (bitPointer | bitMarked | ((bitPointer | bitMarked) << heapBitsShift)) << h.shift
1014 *h.bitp |= uint8(hb << h.shift)
1016 // TODO:(rlh) since the GC is not concurrently setting the
1017 // mark bits in the heap map anymore and malloc
1018 // owns the span we are allocating in why does this have
1021 atomic.And8(h.bitp, ^uint8((bitPointer|bitMarked|((bitPointer|bitMarked)<<heapBitsShift))<<h.shift))
1022 atomic.Or8(h.bitp, uint8(hb<<h.shift))
1027 // Copy from 1-bit ptrmask into 2-bit bitmap.
1028 // The basic approach is to use a single uintptr as a bit buffer,
1029 // alternating between reloading the buffer and writing bitmap bytes.
1030 // In general, one load can supply two bitmap byte writes.
1031 // This is a lot of lines of code, but it compiles into relatively few
1032 // machine instructions.
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)
1077 // Note about sizes:
1079 // typ.size is the number of words in the object,
1080 // and typ.ptrdata is the number of words in the prefix
1081 // of the object that contains pointers. That is, the final
1082 // typ.size - typ.ptrdata words contain no pointers.
1083 // This allows optimization of a common pattern where
1084 // an object has a small header followed by a large scalar
1085 // buffer. If we know the pointers are over, we don't have
1086 // to scan the buffer's heap bitmap at all.
1087 // The 1-bit ptrmasks are sized to contain only bits for
1088 // the typ.ptrdata prefix, zero padded out to a full byte
1089 // of bitmap. This code sets nw (below) so that heap bitmap
1090 // bits are only written for the typ.ptrdata prefix; if there is
1091 // more room in the allocated object, the next heap bitmap
1092 // entry is a 00, indicating that there are no more pointers
1093 // to scan. So only the ptrmask for the ptrdata bytes is needed.
1095 // Replicated copies are not as nice: if there is an array of
1096 // objects with scalar tails, all but the last tail does have to
1097 // be initialized, because there is no way to say "skip forward".
1098 // However, because of the possibility of a repeated type with
1099 // size not a multiple of 4 pointers (one heap bitmap byte),
1100 // the code already must handle the last ptrmask byte specially
1101 // by treating it as containing only the bits for endnb pointers,
1102 // where endnb <= 4. We represent large scalar tails that must
1103 // be expanded in the replication by setting endnb larger than 4.
1104 // This will have the effect of reading many bits out of b,
1105 // but once the real bits are shifted out, b will supply as many
1106 // zero bits as we try to read, which is exactly what we need.
1109 if typ.size < dataSize {
1110 // Filling in bits for an array of typ.
1111 // Set up for repetition of ptrmask during main loop.
1112 // Note that ptrmask describes only a prefix of
1113 const maxBits = sys.PtrSize*8 - 7
1114 if typ.ptrdata/sys.PtrSize <= maxBits {
1115 // Entire ptrmask fits in uintptr with room for a byte fragment.
1116 // Load into pbits and never read from ptrmask again.
1117 // This is especially important when the ptrmask has
1118 // fewer than 8 bits in it; otherwise the reload in the middle
1119 // of the Phase 2 loop would itself need to loop to gather
1122 // Accumulate ptrmask into b.
1123 // ptrmask is sized to describe only typ.ptrdata, but we record
1124 // it as describing typ.size bytes, since all the high bits are zero.
1125 nb = typ.ptrdata / sys.PtrSize
1126 for i := uintptr(0); i < nb; i += 8 {
1127 b |= uintptr(*p) << i
1130 nb = typ.size / sys.PtrSize
1132 // Replicate ptrmask to fill entire pbits uintptr.
1133 // Doubling and truncating is fewer steps than
1134 // iterating by nb each time. (nb could be 1.)
1135 // Since we loaded typ.ptrdata/sys.PtrSize bits
1136 // but are pretending to have typ.size/sys.PtrSize,
1137 // there might be no replication necessary/possible.
1140 if nb+nb <= maxBits {
1141 for endnb <= sys.PtrSize*8 {
1142 pbits |= pbits << endnb
1145 // Truncate to a multiple of original ptrmask.
1146 endnb = maxBits / nb * nb
1147 pbits &= 1<<endnb - 1
1152 // Clear p and endp as sentinel for using pbits.
1153 // Checked during Phase 2 loop.
1157 // Ptrmask is larger. Read it multiple times.
1158 n := (typ.ptrdata/sys.PtrSize+7)/8 - 1
1159 endp = addb(ptrmask, n)
1160 endnb = typ.size/sys.PtrSize - n*8
1169 if typ.size == dataSize {
1170 // Single entry: can stop once we reach the non-pointer data.
1171 nw = typ.ptrdata / sys.PtrSize
1173 // Repeated instances of typ in an array.
1174 // Have to process first N-1 entries in full, but can stop
1175 // once we reach the non-pointer data in the final entry.
1176 nw = ((dataSize/typ.size-1)*typ.size + typ.ptrdata) / sys.PtrSize
1179 // No pointers! Caller was supposed to check.
1180 println("runtime: invalid type ", typ.string())
1181 throw("heapBitsSetType: called with non-pointer type")
1185 // Must write at least 2 words, because the "no scan"
1186 // encoding doesn't take effect until the third word.
1190 // Phase 1: Special case for leading byte (shift==0) or half-byte (shift==4).
1191 // The leading byte is special because it contains the bits for words 0 and 1,
1192 // which do not have the marked bits set.
1193 // The leading half-byte is special because it's a half a byte and must be
1194 // manipulated atomically.
1197 throw("heapBitsSetType: unexpected shift")
1200 // Ptrmask and heap bitmap are aligned.
1201 // Handle first byte of bitmap specially.
1202 // The first byte we write out contains the first two words of the object.
1203 // In those words, the mark bits are mark and checkmark, respectively,
1204 // and must not be set. In all following words, we want to set the mark bit
1205 // as a signal that the object continues to the next 2-bit entry in the bitmap.
1206 hb = b & bitPointerAll
1207 hb |= bitMarked<<(2*heapBitsShift) | bitMarked<<(3*heapBitsShift)
1208 if w += 4; w >= nw {
1212 hbitp = subtract1(hbitp)
1216 case sys.PtrSize == 8 && h.shift == 2:
1217 // Ptrmask and heap bitmap are misaligned.
1218 // The bits for the first two words are in a byte shared with another object
1219 // and must be updated atomically.
1220 // NOTE(rsc): The atomic here may not be necessary.
1221 // We took care of 1-word and 2-word objects above,
1222 // so this is at least a 6-word object, so our start bits
1223 // are shared only with the type bits of another object,
1224 // not with its mark bit. Since there is only one allocation
1225 // from a given span at a time, we should be able to set
1226 // these bits non-atomically. Not worth the risk right now.
1227 hb = (b & (bitPointer | bitPointer<<heapBitsShift)) << (2 * heapBitsShift)
1230 // Note: no bitMarker in hb because the first two words don't get markers from us.
1231 if gcphase == _GCoff {
1232 *hbitp &^= uint8((bitPointer | (bitPointer << heapBitsShift)) << (2 * heapBitsShift))
1235 atomic.And8(hbitp, ^(uint8(bitPointer|bitPointer<<heapBitsShift) << (2 * heapBitsShift)))
1236 atomic.Or8(hbitp, uint8(hb))
1238 hbitp = subtract1(hbitp)
1239 if w += 2; w >= nw {
1240 // We know that there is more data, because we handled 2-word objects above.
1241 // This must be at least a 6-word object. If we're out of pointer words,
1242 // mark no scan in next bitmap byte and finish.
1249 // Phase 2: Full bytes in bitmap, up to but not including write to last byte (full or partial) in bitmap.
1250 // The loop computes the bits for that last write but does not execute the write;
1251 // it leaves the bits in hb for processing by phase 3.
1252 // To avoid repeated adjustment of nb, we subtract out the 4 bits we're going to
1253 // use in the first half of the loop right now, and then we only adjust nb explicitly
1254 // if the 8 bits used by each iteration isn't balanced by 8 bits loaded mid-loop.
1257 // Emit bitmap byte.
1258 // b has at least nb+4 bits, with one exception:
1259 // if w+4 >= nw, then b has only nw-w bits,
1260 // but we'll stop at the break and then truncate
1261 // appropriately in Phase 3.
1262 hb = b & bitPointerAll
1264 if w += 4; w >= nw {
1268 hbitp = subtract1(hbitp)
1271 // Load more bits. b has nb right now.
1273 // Fast path: keep reading from ptrmask.
1274 // nb unmodified: we just loaded 8 bits,
1275 // and the next iteration will consume 8 bits,
1276 // leaving us with the same nb the next time we're here.
1278 b |= uintptr(*p) << nb
1281 // Reduce the number of bits in b.
1282 // This is important if we skipped
1283 // over a scalar tail, since nb could
1284 // be larger than the bit width of b.
1287 } else if p == nil {
1288 // Almost as fast path: track bit count and refill from pbits.
1289 // For short repetitions.
1294 nb -= 8 // for next iteration
1296 // Slow path: reached end of ptrmask.
1297 // Process final partial byte and rewind to start.
1298 b |= uintptr(*p) << nb
1301 b |= uintptr(*ptrmask) << nb
1309 // Emit bitmap byte.
1310 hb = b & bitPointerAll
1312 if w += 4; w >= nw {
1316 hbitp = subtract1(hbitp)
1321 // Phase 3: Write last byte or partial byte and zero the rest of the bitmap entries.
1323 // Counting the 4 entries in hb not yet written to memory,
1324 // there are more entries than possible pointer slots.
1325 // Discard the excess entries (can't be more than 3).
1326 mask := uintptr(1)<<(4-(w-nw)) - 1
1327 hb &= mask | mask<<4 // apply mask to both pointer bits and mark bits
1330 // Change nw from counting possibly-pointer words to total words in allocation.
1331 nw = size / sys.PtrSize
1333 // Write whole bitmap bytes.
1334 // The first is hb, the rest are zero.
1337 hbitp = subtract1(hbitp)
1338 hb = 0 // for possible final half-byte below
1339 for w += 4; w <= nw; w += 4 {
1341 hbitp = subtract1(hbitp)
1345 // Write final partial bitmap byte if any.
1346 // We know w > nw, or else we'd still be in the loop above.
1347 // It can be bigger only due to the 4 entries in hb that it counts.
1348 // If w == nw+4 then there's nothing left to do: we wrote all nw entries
1349 // and can discard the 4 sitting in hb.
1350 // But if w == nw+2, we need to write first two in hb.
1351 // The byte is shared with the next object so we may need an atomic.
1353 if gcphase == _GCoff {
1354 *hbitp = *hbitp&^(bitPointer|bitMarked|(bitPointer|bitMarked)<<heapBitsShift) | uint8(hb)
1356 atomic.And8(hbitp, ^uint8(bitPointer|bitMarked|(bitPointer|bitMarked)<<heapBitsShift))
1357 atomic.Or8(hbitp, uint8(hb))
1362 // Phase 4: all done, but perhaps double check.
1364 end := heapBitsForAddr(x + size)
1365 if typ.kind&kindGCProg == 0 && (hbitp != end.bitp || (w == nw+2) != (end.shift == 2)) {
1366 println("ended at wrong bitmap byte for", typ.string(), "x", dataSize/typ.size)
1367 print("typ.size=", typ.size, " typ.ptrdata=", typ.ptrdata, " dataSize=", dataSize, " size=", size, "\n")
1368 print("w=", w, " nw=", nw, " b=", hex(b), " nb=", nb, " hb=", hex(hb), "\n")
1369 h0 := heapBitsForAddr(x)
1370 print("initial bits h0.bitp=", h0.bitp, " h0.shift=", h0.shift, "\n")
1371 print("ended at hbitp=", hbitp, " but next starts at bitp=", end.bitp, " shift=", end.shift, "\n")
1372 throw("bad heapBitsSetType")
1375 // Double-check that bits to be written were written correctly.
1376 // Does not check that other bits were not written, unfortunately.
1377 h := heapBitsForAddr(x)
1378 nptr := typ.ptrdata / sys.PtrSize
1379 ndata := typ.size / sys.PtrSize
1380 count := dataSize / typ.size
1381 totalptr := ((count-1)*typ.size + typ.ptrdata) / sys.PtrSize
1382 for i := uintptr(0); i < size/sys.PtrSize; i++ {
1384 var have, want uint8
1385 have = (*h.bitp >> h.shift) & (bitPointer | bitMarked)
1387 want = 0 // deadmarker
1388 if typ.kind&kindGCProg != 0 && i < (totalptr+3)/4*4 {
1392 if j < nptr && (*addb(ptrmask, j/8)>>(j%8))&1 != 0 {
1402 println("mismatch writing bits for", typ.string(), "x", dataSize/typ.size)
1403 print("typ.size=", typ.size, " typ.ptrdata=", typ.ptrdata, " dataSize=", dataSize, " size=", size, "\n")
1404 print("kindGCProg=", typ.kind&kindGCProg != 0, "\n")
1405 print("w=", w, " nw=", nw, " b=", hex(b), " nb=", nb, " hb=", hex(hb), "\n")
1406 h0 := heapBitsForAddr(x)
1407 print("initial bits h0.bitp=", h0.bitp, " h0.shift=", h0.shift, "\n")
1408 print("current bits h.bitp=", h.bitp, " h.shift=", h.shift, " *h.bitp=", hex(*h.bitp), "\n")
1409 print("ptrmask=", ptrmask, " p=", p, " endp=", endp, " endnb=", endnb, " pbits=", hex(pbits), " b=", hex(b), " nb=", nb, "\n")
1410 println("at word", i, "offset", i*sys.PtrSize, "have", have, "want", want)
1411 if typ.kind&kindGCProg != 0 {
1412 println("GC program:")
1413 dumpGCProg(addb(typ.gcdata, 4))
1415 throw("bad heapBitsSetType")
1419 if ptrmask == debugPtrmask.data {
1420 unlock(&debugPtrmask.lock)
1425 // heapBitsSetTypeNoScan marks x as noscan. For objects with 1 or 2
1426 // words set their bitPointers to off (0).
1427 // All other objects have the first 3 bitPointers set to
1428 // off (0) and the scan word in the third word
1429 // also set to off (0).
1430 func heapBitsSetTypeNoScan(x, size uintptr) {
1431 h := heapBitsForAddr(uintptr(x))
1434 if sys.PtrSize == 8 && size == sys.PtrSize {
1435 // If this is truely noScan the tinyAlloc logic should have noticed
1436 // and combined such objects.
1437 throw("noscan object is too small")
1438 } else if size%(4*sys.PtrSize) == 0 {
1439 *bitp &^= bitPointer | bitPointer<<heapBitsShift | (bitMarked|bitPointer)<<(2*heapBitsShift)
1440 } else if size%(4*sys.PtrSize) == 2*sys.PtrSize {
1442 *bitp &^= (bitPointer | bitPointer<<heapBitsShift)
1443 if size > 2*sys.PtrSize {
1444 *bitp &^= (bitPointer | bitMarked) << (2 * heapBitsShift)
1446 } else if h.shift == 2 {
1447 *bitp &^= bitPointer<<(2*heapBitsShift) | bitPointer<<(3*heapBitsShift)
1448 if size > 2*sys.PtrSize {
1449 bitp = subtract1(bitp)
1450 *bitp &^= bitPointer | bitMarked
1453 throw("Type has unrecognized size")
1456 throw("Type has unrecognized size")
1460 var debugPtrmask struct {
1465 // heapBitsSetTypeGCProg implements heapBitsSetType using a GC program.
1466 // progSize is the size of the memory described by the program.
1467 // elemSize is the size of the element that the GC program describes (a prefix of).
1468 // dataSize is the total size of the intended data, a multiple of elemSize.
1469 // allocSize is the total size of the allocated memory.
1471 // GC programs are only used for large allocations.
1472 // heapBitsSetType requires that allocSize is a multiple of 4 words,
1473 // so that the relevant bitmap bytes are not shared with surrounding
1474 // objects and need not be accessed with atomic instructions.
1475 func heapBitsSetTypeGCProg(h heapBits, progSize, elemSize, dataSize, allocSize uintptr, prog *byte) {
1476 if sys.PtrSize == 8 && allocSize%(4*sys.PtrSize) != 0 {
1477 // Alignment will be wrong.
1478 throw("heapBitsSetTypeGCProg: small allocation")
1480 var totalBits uintptr
1481 if elemSize == dataSize {
1482 totalBits = runGCProg(prog, nil, h.bitp, 2)
1483 if totalBits*sys.PtrSize != progSize {
1484 println("runtime: heapBitsSetTypeGCProg: total bits", totalBits, "but progSize", progSize)
1485 throw("heapBitsSetTypeGCProg: unexpected bit count")
1488 count := dataSize / elemSize
1490 // Piece together program trailer to run after prog that does:
1492 // repeat(1, elemSize-progSize-1) // zeros to fill element size
1493 // repeat(elemSize, count-1) // repeat that element for count
1494 // This zero-pads the data remaining in the first element and then
1495 // repeats that first element to fill the array.
1496 var trailer [40]byte // 3 varints (max 10 each) + some bytes
1498 if n := elemSize/sys.PtrSize - progSize/sys.PtrSize; n > 0 {
1509 for ; n >= 0x80; n >>= 7 {
1510 trailer[i] = byte(n | 0x80)
1513 trailer[i] = byte(n)
1517 // repeat(elemSize/ptrSize, count-1)
1520 n := elemSize / sys.PtrSize
1521 for ; n >= 0x80; n >>= 7 {
1522 trailer[i] = byte(n | 0x80)
1525 trailer[i] = byte(n)
1528 for ; n >= 0x80; n >>= 7 {
1529 trailer[i] = byte(n | 0x80)
1532 trailer[i] = byte(n)
1537 runGCProg(prog, &trailer[0], h.bitp, 2)
1539 // Even though we filled in the full array just now,
1540 // record that we only filled in up to the ptrdata of the
1541 // last element. This will cause the code below to
1542 // memclr the dead section of the final array element,
1543 // so that scanobject can stop early in the final element.
1544 totalBits = (elemSize*(count-1) + progSize) / sys.PtrSize
1546 endProg := unsafe.Pointer(subtractb(h.bitp, (totalBits+3)/4))
1547 endAlloc := unsafe.Pointer(subtractb(h.bitp, allocSize/heapBitmapScale))
1548 memclr(add(endAlloc, 1), uintptr(endProg)-uintptr(endAlloc))
1551 // progToPointerMask returns the 1-bit pointer mask output by the GC program prog.
1552 // size the size of the region described by prog, in bytes.
1553 // The resulting bitvector will have no more than size/sys.PtrSize bits.
1554 func progToPointerMask(prog *byte, size uintptr) bitvector {
1555 n := (size/sys.PtrSize + 7) / 8
1556 x := (*[1 << 30]byte)(persistentalloc(n+1, 1, &memstats.buckhash_sys))[:n+1]
1557 x[len(x)-1] = 0xa1 // overflow check sentinel
1558 n = runGCProg(prog, nil, &x[0], 1)
1559 if x[len(x)-1] != 0xa1 {
1560 throw("progToPointerMask: overflow")
1562 return bitvector{int32(n), &x[0]}
1565 // Packed GC pointer bitmaps, aka GC programs.
1567 // For large types containing arrays, the type information has a
1568 // natural repetition that can be encoded to save space in the
1569 // binary and in the memory representation of the type information.
1571 // The encoding is a simple Lempel-Ziv style bytecode machine
1572 // with the following instructions:
1575 // 0nnnnnnn: emit n bits copied from the next (n+7)/8 bytes
1576 // 10000000 n c: repeat the previous n bits c times; n, c are varints
1577 // 1nnnnnnn c: repeat the previous n bits c times; c is a varint
1579 // runGCProg executes the GC program prog, and then trailer if non-nil,
1580 // writing to dst with entries of the given size.
1581 // If size == 1, dst is a 1-bit pointer mask laid out moving forward from dst.
1582 // If size == 2, dst is the 2-bit heap bitmap, and writes move backward
1583 // starting at dst (because the heap bitmap does). In this case, the caller guarantees
1584 // that only whole bytes in dst need to be written.
1586 // runGCProg returns the number of 1- or 2-bit entries written to memory.
1587 func runGCProg(prog, trailer, dst *byte, size int) uintptr {
1590 // Bits waiting to be written to memory.
1597 // Flush accumulated full bytes.
1598 // The rest of the loop assumes that nbits <= 7.
1599 for ; nbits >= 8; nbits -= 8 {
1605 v := bits&bitPointerAll | bitMarkedAll
1607 dst = subtract1(dst)
1609 v = bits&bitPointerAll | bitMarkedAll
1611 dst = subtract1(dst)
1616 // Process one instruction.
1621 // Literal bits; n == 0 means end of program.
1623 // Program is over; continue in trailer if present.
1625 //println("trailer")
1633 //println("lit", n, dst)
1635 for i := uintptr(0); i < nbyte; i++ {
1636 bits |= uintptr(*p) << nbits
1643 v := bits&0xf | bitMarkedAll
1645 dst = subtract1(dst)
1647 v = bits&0xf | bitMarkedAll
1649 dst = subtract1(dst)
1654 bits |= uintptr(*p) << nbits
1661 // Repeat. If n == 0, it is encoded in a varint in the next bytes.
1663 for off := uint(0); ; off += 7 {
1666 n |= (x & 0x7F) << off
1673 // Count is encoded in a varint in the next bytes.
1675 for off := uint(0); ; off += 7 {
1678 c |= (x & 0x7F) << off
1683 c *= n // now total number of bits to copy
1685 // If the number of bits being repeated is small, load them
1686 // into a register and use that register for the entire loop
1687 // instead of repeatedly reading from memory.
1688 // Handling fewer than 8 bits here makes the general loop simpler.
1689 // The cutoff is sys.PtrSize*8 - 7 to guarantee that when we add
1690 // the pattern to a bit buffer holding at most 7 bits (a partial byte)
1691 // it will not overflow.
1693 const maxBits = sys.PtrSize*8 - 7
1695 // Start with bits in output buffer.
1699 // If we need more bits, fetch them from memory.
1701 src = subtract1(src)
1704 pattern |= uintptr(*src)
1705 src = subtract1(src)
1712 pattern |= uintptr(*src) & 0xf
1718 // We started with the whole bit output buffer,
1719 // and then we loaded bits from whole bytes.
1720 // Either way, we might now have too many instead of too few.
1721 // Discard the extra.
1723 pattern >>= npattern - n
1727 // Replicate pattern to at most maxBits.
1729 // One bit being repeated.
1730 // If the bit is 1, make the pattern all 1s.
1731 // If the bit is 0, the pattern is already all 0s,
1732 // but we can claim that the number of bits
1733 // in the word is equal to the number we need (c),
1734 // because right shift of bits will zero fill.
1736 pattern = 1<<maxBits - 1
1744 if nb+nb <= maxBits {
1745 // Double pattern until the whole uintptr is filled.
1746 for nb <= sys.PtrSize*8 {
1750 // Trim away incomplete copy of original pattern in high bits.
1751 // TODO(rsc): Replace with table lookup or loop on systems without divide?
1752 nb = maxBits / npattern * npattern
1759 // Add pattern to bit buffer and flush bit buffer, c/npattern times.
1760 // Since pattern contains >8 bits, there will be full bytes to flush
1761 // on each iteration.
1762 for ; c >= npattern; c -= npattern {
1763 bits |= pattern << nbits
1774 *dst = uint8(bits&0xf | bitMarkedAll)
1775 dst = subtract1(dst)
1782 // Add final fragment to bit buffer.
1785 bits |= pattern << nbits
1791 // Repeat; n too large to fit in a register.
1792 // Since nbits <= 7, we know the first few bytes of repeated data
1793 // are already written to memory.
1794 off := n - nbits // n > nbits because n > maxBits and nbits <= 7
1796 // Leading src fragment.
1797 src = subtractb(src, (off+7)/8)
1798 if frag := off & 7; frag != 0 {
1799 bits |= uintptr(*src) >> (8 - frag) << nbits
1804 // Main loop: load one byte, write another.
1805 // The bits are rotating through the bit buffer.
1806 for i := c / 8; i > 0; i-- {
1807 bits |= uintptr(*src) << nbits
1813 // Final src fragment.
1815 bits |= (uintptr(*src) & (1<<c - 1)) << nbits
1819 // Leading src fragment.
1820 src = addb(src, (off+3)/4)
1821 if frag := off & 3; frag != 0 {
1822 bits |= (uintptr(*src) & 0xf) >> (4 - frag) << nbits
1823 src = subtract1(src)
1827 // Main loop: load one byte, write another.
1828 // The bits are rotating through the bit buffer.
1829 for i := c / 4; i > 0; i-- {
1830 bits |= (uintptr(*src) & 0xf) << nbits
1831 src = subtract1(src)
1832 *dst = uint8(bits&0xf | bitMarkedAll)
1833 dst = subtract1(dst)
1836 // Final src fragment.
1838 bits |= (uintptr(*src) & (1<<c - 1)) << nbits
1844 // Write any final bits out, using full-byte writes, even for the final byte.
1845 var totalBits uintptr
1847 totalBits = (uintptr(unsafe.Pointer(dst))-uintptr(unsafe.Pointer(dstStart)))*8 + nbits
1849 for ; nbits > 0; nbits -= 8 {
1855 totalBits = (uintptr(unsafe.Pointer(dstStart))-uintptr(unsafe.Pointer(dst)))*4 + nbits
1857 for ; nbits > 0; nbits -= 4 {
1858 v := bits&0xf | bitMarkedAll
1860 dst = subtract1(dst)
1863 // Clear the mark bits in the first two entries.
1864 // They are the actual mark and checkmark bits,
1865 // not non-dead markers. It simplified the code
1866 // above to set the marker in every bit written and
1867 // then clear these two as a special case at the end.
1868 *dstStart &^= bitMarked | bitMarked<<heapBitsShift
1873 func dumpGCProg(p *byte) {
1879 print("\t", nptr, " end\n")
1883 print("\t", nptr, " lit ", x, ":")
1885 for i := 0; i < n; i++ {
1892 nbit := int(x &^ 0x80)
1894 for nb := uint(0); ; nb += 7 {
1897 nbit |= int(x&0x7f) << nb
1904 for nb := uint(0); ; nb += 7 {
1907 count |= int(x&0x7f) << nb
1912 print("\t", nptr, " repeat ", nbit, " × ", count, "\n")
1913 nptr += nbit * count
1920 func getgcmaskcb(frame *stkframe, ctxt unsafe.Pointer) bool {
1921 target := (*stkframe)(ctxt)
1922 if frame.sp <= target.sp && target.sp < frame.varp {
1929 // gcbits returns the GC type info for x, for testing.
1930 // The result is the bitmap entries (0 or 1), one entry per byte.
1931 //go:linkname reflect_gcbits reflect.gcbits
1932 func reflect_gcbits(x interface{}) []byte {
1934 typ := (*ptrtype)(unsafe.Pointer(efaceOf(&x)._type)).elem
1935 nptr := typ.ptrdata / sys.PtrSize
1936 for uintptr(len(ret)) > nptr && ret[len(ret)-1] == 0 {
1937 ret = ret[:len(ret)-1]
1942 // Returns GC type info for object p for testing.
1943 func getgcmask(ep interface{}) (mask []byte) {
1948 for datap := &firstmoduledata; datap != nil; datap = datap.next {
1950 if datap.data <= uintptr(p) && uintptr(p) < datap.edata {
1951 bitmap := datap.gcdatamask.bytedata
1952 n := (*ptrtype)(unsafe.Pointer(t)).elem.size
1953 mask = make([]byte, n/sys.PtrSize)
1954 for i := uintptr(0); i < n; i += sys.PtrSize {
1955 off := (uintptr(p) + i - datap.data) / sys.PtrSize
1956 mask[i/sys.PtrSize] = (*addb(bitmap, off/8) >> (off % 8)) & 1
1962 if datap.bss <= uintptr(p) && uintptr(p) < datap.ebss {
1963 bitmap := datap.gcbssmask.bytedata
1964 n := (*ptrtype)(unsafe.Pointer(t)).elem.size
1965 mask = make([]byte, n/sys.PtrSize)
1966 for i := uintptr(0); i < n; i += sys.PtrSize {
1967 off := (uintptr(p) + i - datap.bss) / sys.PtrSize
1968 mask[i/sys.PtrSize] = (*addb(bitmap, off/8) >> (off % 8)) & 1
1977 if mlookup(uintptr(p), &base, &n, nil) != 0 {
1978 mask = make([]byte, n/sys.PtrSize)
1979 for i := uintptr(0); i < n; i += sys.PtrSize {
1980 hbits := heapBitsForAddr(base + i)
1981 if hbits.isPointer() {
1982 mask[i/sys.PtrSize] = 1
1984 if i >= 2*sys.PtrSize && !hbits.morePointers() {
1985 mask = mask[:i/sys.PtrSize]
1993 if _g_ := getg(); _g_.m.curg.stack.lo <= uintptr(p) && uintptr(p) < _g_.m.curg.stack.hi {
1995 frame.sp = uintptr(p)
1997 gentraceback(_g_.m.curg.sched.pc, _g_.m.curg.sched.sp, 0, _g_.m.curg, 0, nil, 1000, getgcmaskcb, noescape(unsafe.Pointer(&frame)), 0)
1998 if frame.fn != nil {
2000 targetpc := frame.continpc
2004 if targetpc != f.entry {
2007 pcdata := pcdatavalue(f, _PCDATA_StackMapIndex, targetpc, nil)
2011 stkmap := (*stackmap)(funcdata(f, _FUNCDATA_LocalsPointerMaps))
2012 if stkmap == nil || stkmap.n <= 0 {
2015 bv := stackmapdata(stkmap, pcdata)
2016 size := uintptr(bv.n) * sys.PtrSize
2017 n := (*ptrtype)(unsafe.Pointer(t)).elem.size
2018 mask = make([]byte, n/sys.PtrSize)
2019 for i := uintptr(0); i < n; i += sys.PtrSize {
2020 bitmap := bv.bytedata
2021 off := (uintptr(p) + i - frame.varp + size) / sys.PtrSize
2022 mask[i/sys.PtrSize] = (*addb(bitmap, off/8) >> (off % 8)) & 1
2028 // otherwise, not something the GC knows about.
2029 // possibly read-only data, like malloc(0).
2030 // must not have pointers