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 // TODO(rsc): The code having to do with the heap bitmap needs very serious cleanup.
6 // It has gotten completely out of control.
8 // Garbage collector (GC).
12 // - mostly precise (with the exception of some C-allocated objects, assembly frames/arguments, etc)
13 // - parallel (up to MaxGcproc threads)
14 // - partially concurrent (mark is stop-the-world, while sweep is concurrent)
15 // - non-moving/non-compacting
16 // - full (non-partial)
19 // Next GC is after we've allocated an extra amount of memory proportional to
20 // the amount already in use. The proportion is controlled by GOGC environment variable
21 // (100 by default). If GOGC=100 and we're using 4M, we'll GC again when we get to 8M
22 // (this mark is tracked in next_gc variable). This keeps the GC cost in linear
23 // proportion to the allocation cost. Adjusting GOGC just changes the linear constant
24 // (and also the amount of extra memory used).
27 // The sweep phase proceeds concurrently with normal program execution.
28 // The heap is swept span-by-span both lazily (when a goroutine needs another span)
29 // and concurrently in a background goroutine (this helps programs that are not CPU bound).
30 // However, at the end of the stop-the-world GC phase we don't know the size of the live heap,
31 // and so next_gc calculation is tricky and happens as follows.
32 // At the end of the stop-the-world phase next_gc is conservatively set based on total
33 // heap size; all spans are marked as "needs sweeping".
34 // Whenever a span is swept, next_gc is decremented by GOGC*newly_freed_memory.
35 // The background sweeper goroutine simply sweeps spans one-by-one bringing next_gc
36 // closer to the target value. However, this is not enough to avoid over-allocating memory.
37 // Consider that a goroutine wants to allocate a new span for a large object and
38 // there are no free swept spans, but there are small-object unswept spans.
39 // If the goroutine naively allocates a new span, it can surpass the yet-unknown
40 // target next_gc value. In order to prevent such cases (1) when a goroutine needs
41 // to allocate a new small-object span, it sweeps small-object spans for the same
42 // object size until it frees at least one object; (2) when a goroutine needs to
43 // allocate large-object span from heap, it sweeps spans until it frees at least
44 // that many pages into heap. Together these two measures ensure that we don't surpass
45 // target next_gc value by a large margin. There is an exception: if a goroutine sweeps
46 // and frees two nonadjacent one-page spans to the heap, it will allocate a new two-page span,
47 // but there can still be other one-page unswept spans which could be combined into a two-page span.
48 // It's critical to ensure that no operations proceed on unswept spans (that would corrupt
49 // mark bits in GC bitmap). During GC all mcaches are flushed into the central cache,
50 // so they are empty. When a goroutine grabs a new span into mcache, it sweeps it.
51 // When a goroutine explicitly frees an object or sets a finalizer, it ensures that
52 // the span is swept (either by sweeping it, or by waiting for the concurrent sweep to finish).
53 // The finalizer goroutine is kicked off only when all spans are swept.
54 // When the next GC starts, it sweeps all not-yet-swept spans (if any).
62 _DebugGCPtrs = false // if true, print trace of every pointer load during GC
63 _ConcurrentSweep = true
65 _WorkbufSize = 4 * 1024
66 _FinBlockSize = 4 * 1024
75 // ptrmask for an allocation containing a single pointer.
76 var oneptr = [...]uint8{bitsPointer}
78 // Initialized from $GOGC. GOGC=off means no gc.
81 // Holding worldsema grants an M the right to try to stop the world.
84 // semacquire(&worldsema);
91 // semrelease(&worldsema);
94 var worldsema uint32 = 1
97 node lfnode // must be first
99 obj [(_WorkbufSize - unsafe.Sizeof(lfnode{}) - ptrSize) / ptrSize]uintptr
102 var data, edata, bss, ebss, gcdata, gcbss struct{}
104 var finlock mutex // protects the following variables
105 var fing *g // goroutine that runs finalizers
106 var finq *finblock // list of finalizers that are to be executed
107 var finc *finblock // cache of free blocks
108 var finptrmask [_FinBlockSize / ptrSize / pointersPerByte]byte
111 var allfin *finblock // list of all blocks
113 var gcdatamask bitvector
114 var gcbssmask bitvector
118 var badblock [1024]uintptr
121 type workdata struct {
122 full uint64 // lock-free list of full blocks
123 empty uint64 // lock-free list of empty blocks
124 pad0 [_CacheLineSize]uint8 // prevents false-sharing between full/empty and nproc/nwait
132 // Copy of mheap.allspans for marker or sweeper.
138 //go:linkname weak_cgo_allocate go.weak.runtime._cgo_allocate_internal
139 var weak_cgo_allocate byte
141 // Is _cgo_allocate linked into the binary?
142 func have_cgo_allocate() bool {
143 return &weak_cgo_allocate != nil
146 // scanblock scans a block of n bytes starting at pointer b for references
147 // to other objects, scanning any it finds recursively until there are no
148 // unscanned objects left. Instead of using an explicit recursion, it keeps
149 // a work list in the Workbuf* structures and loops in the main function
150 // body. Keeping an explicit work list is easier on the stack allocator and
152 func scanblock(b, n uintptr, ptrmask *uint8) {
153 // Cache memory arena parameters in local vars.
154 arena_start := mheap_.arena_start
155 arena_used := mheap_.arena_used
157 wbuf := getempty(nil)
159 wp := &wbuf.obj[nobj]
160 keepworking := b == 0
162 var ptrbitp unsafe.Pointer
164 // ptrmask can have 2 possible values:
165 // 1. nil - obtain pointer mask from GC bitmap.
166 // 2. pointer to a compact mask (for stacks and data).
167 goto_scanobj := b != 0
174 // Out of work in workbuf.
180 // Refill workbuf from global queue.
186 if nobj < uintptr(len(wbuf.obj)) {
193 // If another proc wants a pointer, give it some.
194 if work.nwait > 0 && nobj > 4 && work.full == 0 {
198 if nobj < uintptr(len(wbuf.obj)) {
208 n = arena_used - uintptr(b)
209 ptrmask = nil // use GC bitmap for pointer info
213 print("scanblock ", b, " +", hex(n), " ", ptrmask, "\n")
216 // Find bits of the beginning of the object.
218 off := (uintptr(b) - arena_start) / ptrSize
219 ptrbitp = unsafe.Pointer(arena_start - off/wordsPerBitmapByte - 1)
223 for i = 0; i < n; i += ptrSize {
224 // Find bits for this word.
227 // Check if we have reached end of span.
228 if (uintptr(b)+i)%_PageSize == 0 &&
229 h_spans[(uintptr(b)-arena_start)>>_PageShift] != h_spans[(uintptr(b)+i-arena_start)>>_PageShift] {
233 // Consult GC bitmap.
234 bits = uintptr(*(*byte)(ptrbitp))
236 if wordsPerBitmapByte != 2 {
237 gothrow("alg doesn't work for wordsPerBitmapByte != 2")
239 j := (uintptr(b) + i) / ptrSize & 1
240 ptrbitp = add(ptrbitp, -j)
243 if bits&bitBoundary != 0 && i != 0 {
244 break // reached beginning of the next object
246 bits = (bits >> 2) & bitsMask
247 if bits == bitsDead {
248 break // reached no-scan part of the object
251 // dense mask (stack or data)
252 bits = (uintptr(*(*byte)(add(unsafe.Pointer(ptrmask), (i/ptrSize)/4))) >> (((i / ptrSize) % 4) * bitsPerPointer)) & bitsMask
255 if bits <= _BitsScalar { // BitsScalar || BitsDead
259 if bits != _BitsPointer {
260 gothrow("unexpected garbage collection bits")
263 obj := *(*uintptr)(unsafe.Pointer(b + i))
268 var off, bitp, shift, xbits uintptr
270 // At this point we have extracted the next potential pointer.
271 // Check if it points into heap.
275 if obj < arena_start || arena_used <= obj {
276 if uintptr(obj) < _PhysPageSize && invalidptr != 0 {
285 off = (obj - arena_start) / ptrSize
286 bitp = arena_start - off/wordsPerBitmapByte - 1
287 shift = (off % wordsPerBitmapByte) * gcBits
288 xbits = uintptr(*(*byte)(unsafe.Pointer(bitp)))
289 bits = (xbits >> shift) & bitMask
290 if (bits & bitBoundary) == 0 {
291 // Not a beginning of a block, consult span table to find the block beginning.
292 k := pageID(obj >> _PageShift)
294 x -= pageID(arena_start >> _PageShift)
296 if s == nil || k < s.start || s.limit <= obj || s.state != mSpanInUse {
297 // Stack pointers lie within the arena bounds but are not part of the GC heap.
299 if s != nil && s.state == _MSpanStack {
304 p := uintptr(s.start) << _PageShift
305 if s.sizeclass != 0 {
307 idx := (obj - p) / size
311 print("runtime: failed to find block beginning for ", hex(p), " s=", hex(s.start*_PageSize), " s.limit=", hex(s.limit), "\n")
312 gothrow("failed to find block beginning")
319 print("scan *", hex(b+i), " = ", hex(obj0), " => base ", hex(obj), "\n")
322 if nbadblock > 0 && obj == badblock[nbadblock-1] {
323 // Running garbage collection again because
324 // we want to find the path from a root to a bad pointer.
325 // Found possible next step; extend or finish path.
326 for j := int32(0); j < nbadblock; j++ {
327 if badblock[j] == b {
331 print("runtime: found *(", hex(b), "+", hex(i), ") = ", hex(obj0), "+", hex(obj-obj0), "\n")
333 gothrow("bad pointer")
335 if nbadblock >= int32(len(badblock)) {
336 gothrow("badblock trace too long")
338 badblock[nbadblock] = uintptr(b)
343 // Now we have bits, bitp, and shift correct for
344 // obj pointing at the base of the object.
345 // Only care about not marked objects.
346 if bits&bitMarked != 0 {
350 // If obj size is greater than 8, then each byte of GC bitmap
351 // contains info for at most one object. In such case we use
352 // non-atomic byte store to mark the object. This can lead
353 // to double enqueue of the object for scanning, but scanning
354 // is an idempotent operation, so it is OK. This cannot lead
355 // to bitmap corruption because the single marked bit is the
356 // only thing that can change in the byte.
357 // For 8-byte objects we use non-atomic store, if the other
358 // quadruple is already marked. Otherwise we resort to CAS
360 if xbits&(bitMask|bitMask<<gcBits) != bitBoundary|bitBoundary<<gcBits || work.nproc == 1 {
361 *(*byte)(unsafe.Pointer(bitp)) = uint8(xbits | bitMarked<<shift)
363 atomicor8((*byte)(unsafe.Pointer(bitp)), bitMarked<<shift)
366 if (xbits>>(shift+2))&bitsMask == bitsDead {
367 continue // noscan object
370 // Queue the obj for scanning.
371 // TODO: PREFETCH here.
373 // If workbuf is full, obtain an empty one.
374 if nobj >= uintptr(len(wbuf.obj)) {
376 wbuf = getempty(wbuf)
382 if nobj < uintptr(len(wbuf.obj)) {
390 // If cgo_allocate is linked into the binary, it can allocate
391 // memory as []unsafe.Pointer that may not contain actual
392 // pointers and must be scanned conservatively.
393 // In this case alone, allow the bad pointer.
394 if have_cgo_allocate() && ptrmask == nil {
398 // Anything else indicates a bug somewhere.
399 // If we're in the middle of chasing down a different bad pointer,
400 // don't confuse the trace by printing about this one.
405 print("runtime: garbage collector found invalid heap pointer *(", hex(b), "+", hex(i), ")=", hex(obj))
409 print(" span=", uintptr(s.start)<<_PageShift, "-", s.limit, "-", (uintptr(s.start)+s.npages)<<_PageShift, " state=", s.state, "\n")
412 gothrow("invalid heap pointer")
414 // Add to badblock list, which will cause the garbage collection
415 // to keep repeating until it has traced the chain of pointers
416 // leading to obj all the way back to a root.
418 badblock[nbadblock] = uintptr(b)
423 print("end scanblock ", hex(b), " +", hex(n), " ", ptrmask, "\n")
425 if _DebugGC > 0 && ptrmask == nil {
426 // For heap objects ensure that we did not overscan.
428 if mlookup(b, &p, &n, nil) == 0 || b != p || i > n {
429 print("runtime: scanned (", hex(b), "+", hex(i), "), heap object (", hex(p), "+", hex(n), ")\n")
430 gothrow("scanblock: scanned invalid object")
436 func markroot(desc *parfor, i uint32) {
437 // Note: if you add a case here, please also update heapdump.c:dumproots.
440 scanblock(uintptr(unsafe.Pointer(&data)), uintptr(unsafe.Pointer(&edata))-uintptr(unsafe.Pointer(&data)), gcdatamask.bytedata)
443 scanblock(uintptr(unsafe.Pointer(&bss)), uintptr(unsafe.Pointer(&ebss))-uintptr(unsafe.Pointer(&bss)), gcbssmask.bytedata)
445 case _RootFinalizers:
446 for fb := allfin; fb != nil; fb = fb.alllink {
447 scanblock(uintptr(unsafe.Pointer(&fb.fin[0])), uintptr(fb.cnt)*unsafe.Sizeof(fb.fin[0]), &finptrmask[0])
451 // mark MSpan.specials
452 sg := mheap_.sweepgen
453 for spanidx := uint32(0); spanidx < uint32(len(work.spans)); spanidx++ {
454 s := work.spans[spanidx]
455 if s.state != mSpanInUse {
458 if s.sweepgen != sg {
459 print("sweep ", s.sweepgen, " ", sg, "\n")
460 gothrow("gc: unswept span")
462 for sp := s.specials; sp != nil; sp = sp.next {
463 if sp.kind != _KindSpecialFinalizer {
466 // don't mark finalized object, but scan it so we
467 // retain everything it points to.
468 spf := (*specialfinalizer)(unsafe.Pointer(sp))
469 // A finalizer can be set for an inner byte of an object, find object beginning.
470 p := uintptr(s.start<<_PageShift) + uintptr(spf.special.offset)/s.elemsize*s.elemsize
471 scanblock(p, s.elemsize, nil)
472 scanblock(uintptr(unsafe.Pointer(&spf.fn)), ptrSize, &oneptr[0])
476 case _RootFlushCaches:
480 // the rest is scanning goroutine stacks
481 if uintptr(i-_RootCount) >= allglen {
482 gothrow("markroot: bad index")
484 gp := allgs[i-_RootCount]
485 // remember when we've first observed the G blocked
486 // needed only to output in traceback
487 status := readgstatus(gp)
488 if (status == _Gwaiting || status == _Gsyscall) && gp.waitsince == 0 {
489 gp.waitsince = work.tstart
491 // Shrink a stack if not much of it is being used.
493 if readgstatus(gp) == _Gdead {
496 gp.gcworkdone = false
506 // Get an empty work buffer off the work.empty list,
507 // allocating new buffers as needed.
508 func getempty(b *workbuf) *workbuf {
511 lfstackpush(&work.full, &b.node)
515 if c.gcworkbuf != nil {
516 b = (*workbuf)(c.gcworkbuf)
520 b = (*workbuf)(lfstackpop(&work.empty))
523 b = (*workbuf)(persistentalloc(unsafe.Sizeof(*b), _CacheLineSize, &memstats.gc_sys))
529 func putempty(b *workbuf) {
532 if c.gcworkbuf == nil {
533 c.gcworkbuf = (unsafe.Pointer)(b)
536 lfstackpush(&work.empty, &b.node)
539 func gcworkbuffree(b unsafe.Pointer) {
541 putempty((*workbuf)(b))
545 // Get a full work buffer off the work.full list, or return nil.
546 func getfull(b *workbuf) *workbuf {
548 lfstackpush(&work.empty, &b.node)
550 b = (*workbuf)(lfstackpop(&work.full))
551 if b != nil || work.nproc == 1 {
555 xadd(&work.nwait, +1)
558 xadd(&work.nwait, -1)
559 b = (*workbuf)(lfstackpop(&work.full))
563 xadd(&work.nwait, +1)
565 if work.nwait == work.nproc {
570 _g_.m.gcstats.nprocyield++
573 _g_.m.gcstats.nosyield++
576 _g_.m.gcstats.nsleep++
582 func handoff(b *workbuf) *workbuf {
583 // Make new buffer with half of b's pointers.
588 memmove(unsafe.Pointer(&b1.obj[0]), unsafe.Pointer(&b.obj[b.nobj]), n*unsafe.Sizeof(b1.obj[0]))
590 _g_.m.gcstats.nhandoff++
591 _g_.m.gcstats.nhandoffcnt += uint64(n)
593 // Put b on full list - let first half of b get stolen.
594 lfstackpush(&work.full, &b.node)
598 func stackmapdata(stkmap *stackmap, n int32) bitvector {
599 if n < 0 || n >= stkmap.n {
600 gothrow("stackmapdata: index out of range")
602 return bitvector{stkmap.nbit, (*byte)(add(unsafe.Pointer(&stkmap.bytedata), uintptr(n*((stkmap.nbit+31)/32*4))))}
605 // Scan a stack frame: local variables and function arguments/results.
606 func scanframe(frame *stkframe, unused unsafe.Pointer) bool {
609 targetpc := frame.continpc
615 print("scanframe ", gofuncname(f), "\n")
617 if targetpc != f.entry {
620 pcdata := pcdatavalue(f, _PCDATA_StackMapIndex, targetpc)
622 // We do not have a valid pcdata value but there might be a
623 // stackmap for this function. It is likely that we are looking
624 // at the function prologue, assume so and hope for the best.
628 // Scan local variables if stack frame has been allocated.
629 size := frame.varp - frame.sp
631 if thechar != '6' && thechar != '8' {
637 stkmap := (*stackmap)(funcdata(f, _FUNCDATA_LocalsPointerMaps))
638 if stkmap == nil || stkmap.n <= 0 {
639 print("runtime: frame ", gofuncname(f), " untyped locals ", hex(frame.varp-size), "+", hex(size), "\n")
640 gothrow("missing stackmap")
643 // Locals bitmap information, scan just the pointers in locals.
644 if pcdata < 0 || pcdata >= stkmap.n {
645 // don't know where we are
646 print("runtime: pcdata is ", pcdata, " and ", stkmap.n, " locals stack map entries for ", gofuncname(f), " (targetpc=", targetpc, ")\n")
647 gothrow("scanframe: bad symbol table")
649 bv := stackmapdata(stkmap, pcdata)
650 size = (uintptr(bv.n) * ptrSize) / bitsPerPointer
651 scanblock(frame.varp-size, uintptr(bv.n)/bitsPerPointer*ptrSize, bv.bytedata)
655 if frame.arglen > 0 {
657 if frame.argmap != nil {
660 stkmap := (*stackmap)(funcdata(f, _FUNCDATA_ArgsPointerMaps))
661 if stkmap == nil || stkmap.n <= 0 {
662 print("runtime: frame ", gofuncname(f), " untyped args ", hex(frame.argp), "+", hex(frame.arglen), "\n")
663 gothrow("missing stackmap")
665 if pcdata < 0 || pcdata >= stkmap.n {
666 // don't know where we are
667 print("runtime: pcdata is ", pcdata, " and ", stkmap.n, " args stack map entries for ", gofuncname(f), " (targetpc=", targetpc, ")\n")
668 gothrow("scanframe: bad symbol table")
670 bv = stackmapdata(stkmap, pcdata)
672 scanblock(frame.argp, uintptr(bv.n)/bitsPerPointer*ptrSize, bv.bytedata)
677 func scanstack(gp *g) {
678 // TODO(rsc): Due to a precedence error, this was never checked in the original C version.
679 // If you enable the check, the gothrow happens.
681 if readgstatus(gp)&_Gscan == 0 {
682 print("runtime: gp=", gp, ", goid=", gp.goid, ", gp->atomicstatus=", readgstatus(gp), "\n")
683 gothrow("mark - bad status")
687 switch readgstatus(gp) &^ _Gscan {
689 print("runtime: gp=", gp, ", goid=", gp.goid, ", gp->atomicstatus=", readgstatus(gp), "\n")
690 gothrow("mark - bad status")
694 print("runtime: gp=", gp, ", goid=", gp.goid, ", gp->atomicstatus=", readgstatus(gp), "\n")
695 gothrow("mark - world not stopped")
696 case _Grunnable, _Gsyscall, _Gwaiting:
701 gothrow("can't scan our own stack")
704 if mp != nil && mp.helpgc != 0 {
705 gothrow("can't scan gchelper stack")
708 gentraceback(^uintptr(0), ^uintptr(0), 0, gp, 0, nil, 0x7fffffff, scanframe, nil, 0)
709 tracebackdefers(gp, scanframe, nil)
712 // The gp has been moved to a gc safepoint. If there is gcphase specific
713 // work it is done here.
714 func gcphasework(gp *g) {
717 gothrow("gcphasework in bad gcphase")
718 case _GCoff, _GCquiesce, _GCstw, _GCsweep:
721 // Disabled until concurrent GC is implemented
722 // but indicate the scan has been done.
728 var finalizer1 = [...]byte{
729 // Each Finalizer is 5 words, ptr ptr uintptr ptr ptr.
730 // Each byte describes 4 words.
731 // Need 4 Finalizers described by 5 bytes before pattern repeats:
732 // ptr ptr uintptr ptr ptr
733 // ptr ptr uintptr ptr ptr
734 // ptr ptr uintptr ptr ptr
735 // ptr ptr uintptr ptr ptr
737 // ptr ptr uintptr ptr
738 // ptr ptr ptr uintptr
740 // uintptr ptr ptr ptr
741 // ptr uintptr ptr ptr
742 // Assumptions about Finalizer layout checked below.
743 bitsPointer | bitsPointer<<2 | bitsScalar<<4 | bitsPointer<<6,
744 bitsPointer | bitsPointer<<2 | bitsPointer<<4 | bitsScalar<<6,
745 bitsPointer | bitsPointer<<2 | bitsPointer<<4 | bitsPointer<<6,
746 bitsScalar | bitsPointer<<2 | bitsPointer<<4 | bitsPointer<<6,
747 bitsPointer | bitsScalar<<2 | bitsPointer<<4 | bitsPointer<<6,
750 func queuefinalizer(p unsafe.Pointer, fn *funcval, nret uintptr, fint *_type, ot *ptrtype) {
752 if finq == nil || finq.cnt == finq.cap {
754 finc = (*finblock)(persistentalloc(_FinBlockSize, 0, &memstats.gc_sys))
755 finc.cap = int32((_FinBlockSize-unsafe.Sizeof(finblock{}))/unsafe.Sizeof(finalizer{}) + 1)
756 finc.alllink = allfin
758 if finptrmask[0] == 0 {
759 // Build pointer mask for Finalizer array in block.
760 // Check assumptions made in finalizer1 array above.
761 if (unsafe.Sizeof(finalizer{}) != 5*ptrSize ||
762 unsafe.Offsetof(finalizer{}.fn) != 0 ||
763 unsafe.Offsetof(finalizer{}.arg) != ptrSize ||
764 unsafe.Offsetof(finalizer{}.nret) != 2*ptrSize ||
765 unsafe.Offsetof(finalizer{}.fint) != 3*ptrSize ||
766 unsafe.Offsetof(finalizer{}.ot) != 4*ptrSize ||
767 bitsPerPointer != 2) {
768 gothrow("finalizer out of sync")
770 for i := range finptrmask {
771 finptrmask[i] = finalizer1[i%len(finalizer1)]
780 f := (*finalizer)(add(unsafe.Pointer(&finq.fin[0]), uintptr(finq.cnt)*unsafe.Sizeof(finq.fin[0])))
791 func iterate_finq(callback func(*funcval, unsafe.Pointer, uintptr, *_type, *ptrtype)) {
792 for fb := allfin; fb != nil; fb = fb.alllink {
793 for i := int32(0); i < fb.cnt; i++ {
795 callback(f.fn, f.arg, f.nret, f.fint, f.ot)
800 func mSpan_EnsureSwept(s *mspan) {
801 // Caller must disable preemption.
802 // Otherwise when this function returns the span can become unswept again
803 // (if GC is triggered on another goroutine).
805 if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
806 gothrow("MSpan_EnsureSwept: m is not locked")
809 sg := mheap_.sweepgen
810 if atomicload(&s.sweepgen) == sg {
813 if cas(&s.sweepgen, sg-2, sg-1) {
814 mSpan_Sweep(s, false)
817 // unfortunate condition, and we don't have efficient means to wait
818 for atomicload(&s.sweepgen) != sg {
823 // Sweep frees or collects finalizers for blocks not marked in the mark phase.
824 // It clears the mark bits in preparation for the next GC round.
825 // Returns true if the span was returned to heap.
826 // If preserve=true, don't return it to heap nor relink in MCentral lists;
827 // caller takes care of it.
828 func mSpan_Sweep(s *mspan, preserve bool) bool {
829 // It's critical that we enter this function with preemption disabled,
830 // GC must not start while we are in the middle of this function.
832 if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
833 gothrow("MSpan_Sweep: m is not locked")
835 sweepgen := mheap_.sweepgen
836 if s.state != mSpanInUse || s.sweepgen != sweepgen-1 {
837 print("MSpan_Sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
838 gothrow("MSpan_Sweep: bad span state")
840 arena_start := mheap_.arena_start
848 // Chunk full of small blocks.
849 npages = class_to_allocnpages[cl]
850 n = (npages << _PageShift) / int32(size)
859 // Mark any free objects in this span so we don't collect them.
860 for link := s.freelist; link != nil; link = link.next {
861 off := (uintptr(unsafe.Pointer(link)) - arena_start) / ptrSize
862 bitp := arena_start - off/wordsPerBitmapByte - 1
863 shift := (off % wordsPerBitmapByte) * gcBits
864 *(*byte)(unsafe.Pointer(bitp)) |= bitMarked << shift
867 // Unlink & free special records for any objects we're about to free.
868 specialp := &s.specials
871 // A finalizer can be set for an inner byte of an object, find object beginning.
872 p := uintptr(s.start<<_PageShift) + uintptr(special.offset)/size*size
873 off := (p - arena_start) / ptrSize
874 bitp := arena_start - off/wordsPerBitmapByte - 1
875 shift := (off % wordsPerBitmapByte) * gcBits
876 bits := (*(*byte)(unsafe.Pointer(bitp)) >> shift) & bitMask
877 if bits&bitMarked == 0 {
878 // Find the exact byte for which the special was setup
879 // (as opposed to object beginning).
880 p := uintptr(s.start<<_PageShift) + uintptr(special.offset)
881 // about to free object: splice out special record
883 special = special.next
885 if !freespecial(y, unsafe.Pointer(p), size, false) {
886 // stop freeing of object if it has a finalizer
887 *(*byte)(unsafe.Pointer(bitp)) |= bitMarked << shift
890 // object is still live: keep special record
891 specialp = &special.next
896 // Sweep through n objects of given size starting at p.
897 // This thread owns the span now, so it can manipulate
898 // the block bitmap without atomic operations.
899 p := uintptr(s.start << _PageShift)
900 off := (p - arena_start) / ptrSize
901 bitp := arena_start - off/wordsPerBitmapByte - 1
903 step := size / (ptrSize * wordsPerBitmapByte)
904 // Rewind to the previous quadruple as we move to the next
905 // in the beginning of the loop.
912 for ; n > 0; n, p = n-1, p+size {
918 shift = gcBits - shift
921 xbits := *(*byte)(unsafe.Pointer(bitp))
922 bits := (xbits >> shift) & bitMask
924 // Allocated and marked object, reset bits to allocated.
925 if bits&bitMarked != 0 {
926 *(*byte)(unsafe.Pointer(bitp)) &^= bitMarked << shift
930 // At this point we know that we are looking at garbage object
931 // that needs to be collected.
932 if debug.allocfreetrace != 0 {
933 tracefree(unsafe.Pointer(p), size)
936 // Reset to allocated+noscan.
937 *(*byte)(unsafe.Pointer(bitp)) = uint8(uintptr(xbits&^((bitMarked|bitsMask<<2)<<shift)) | uintptr(bitsDead)<<(shift+2))
941 gothrow("can't preserve large span")
943 unmarkspan(p, s.npages<<_PageShift)
946 // important to set sweepgen before returning it to heap
947 atomicstore(&s.sweepgen, sweepgen)
950 // NOTE(rsc,dvyukov): The original implementation of efence
951 // in CL 22060046 used SysFree instead of SysFault, so that
952 // the operating system would eventually give the memory
953 // back to us again, so that an efence program could run
954 // longer without running out of memory. Unfortunately,
955 // calling SysFree here without any kind of adjustment of the
956 // heap data structures means that when the memory does
957 // come back to us, we have the wrong metadata for it, either in
958 // the MSpan structures or in the garbage collection bitmap.
959 // Using SysFault here means that the program will run out of
960 // memory fairly quickly in efence mode, but at least it won't
961 // have mysterious crashes due to confused memory reuse.
962 // It should be possible to switch back to SysFree if we also
963 // implement and then call some kind of MHeap_DeleteSpan.
964 if debug.efence > 0 {
965 s.limit = 0 // prevent mlookup from finding this span
966 sysFault(unsafe.Pointer(p), size)
968 mHeap_Free(&mheap_, s, 1)
971 c.local_largefree += size
972 xadd64(&memstats.next_gc, -int64(size)*int64(gcpercent+100)/100)
975 // Free small object.
976 if size > 2*ptrSize {
977 *(*uintptr)(unsafe.Pointer(p + ptrSize)) = uintptrMask & 0xdeaddeaddeaddead // mark as "needs to be zeroed"
978 } else if size > ptrSize {
979 *(*uintptr)(unsafe.Pointer(p + ptrSize)) = 0
981 end.next = (*mlink)(unsafe.Pointer(p))
987 // We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
988 // because of the potential for a concurrent free/SetFinalizer.
989 // But we need to set it before we make the span available for allocation
990 // (return it to heap or mcentral), because allocation code assumes that a
991 // span is already swept if available for allocation.
992 if !sweepgenset && nfree == 0 {
993 // The span must be in our exclusive ownership until we update sweepgen,
994 // check for potential races.
995 if s.state != mSpanInUse || s.sweepgen != sweepgen-1 {
996 print("MSpan_Sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
997 gothrow("MSpan_Sweep: bad span state after sweep")
999 atomicstore(&s.sweepgen, sweepgen)
1002 c.local_nsmallfree[cl] += uintptr(nfree)
1003 c.local_cachealloc -= intptr(uintptr(nfree) * size)
1004 xadd64(&memstats.next_gc, -int64(nfree)*int64(size)*int64(gcpercent+100)/100)
1005 res = mCentral_FreeSpan(&mheap_.central[cl].mcentral, s, int32(nfree), head.next, end, preserve)
1006 // MCentral_FreeSpan updates sweepgen
1011 // State of background sweep.
1012 // Protected by gclock.
1013 type sweepdata struct {
1018 spanidx uint32 // background sweeper position
1027 // returns number of pages returned to heap, or ^uintptr(0) if there is nothing to sweep
1028 func sweepone() uintptr {
1031 // increment locks to ensure that the goroutine is not preempted
1032 // in the middle of sweep thus leaving the span in an inconsistent state for next GC
1034 sg := mheap_.sweepgen
1036 idx := xadd(&sweep.spanidx, 1) - 1
1037 if idx >= uint32(len(work.spans)) {
1038 mheap_.sweepdone = 1
1042 s := work.spans[idx]
1043 if s.state != mSpanInUse {
1047 if s.sweepgen != sg-2 || !cas(&s.sweepgen, sg-2, sg-1) {
1051 if !mSpan_Sweep(s, false) {
1059 func gosweepone() uintptr {
1061 systemstack(func() {
1067 func gosweepdone() bool {
1068 return mheap_.sweepdone != 0
1076 // parallel mark for over gc roots
1077 parfordo(work.markfor)
1079 // help other threads scan secondary blocks
1080 scanblock(0, 0, nil)
1082 nproc := work.nproc // work.nproc can change right after we increment work.ndone
1083 if xadd(&work.ndone, +1) == nproc-1 {
1084 notewakeup(&work.alldone)
1103 func flushallmcaches() {
1113 mCache_ReleaseAll(c)
1118 func updatememstats(stats *gcstats) {
1122 for mp := allm; mp != nil; mp = mp.alllink {
1124 src := (*[unsafe.Sizeof(gcstats{}) / 8]uint64)(unsafe.Pointer(&mp.gcstats))
1125 dst := (*[unsafe.Sizeof(gcstats{}) / 8]uint64)(unsafe.Pointer(stats))
1126 for i, v := range src {
1129 mp.gcstats = gcstats{}
1133 memstats.mcache_inuse = uint64(mheap_.cachealloc.inuse)
1134 memstats.mspan_inuse = uint64(mheap_.spanalloc.inuse)
1135 memstats.sys = memstats.heap_sys + memstats.stacks_sys + memstats.mspan_sys +
1136 memstats.mcache_sys + memstats.buckhash_sys + memstats.gc_sys + memstats.other_sys
1138 // Calculate memory allocator stats.
1139 // During program execution we only count number of frees and amount of freed memory.
1140 // Current number of alive object in the heap and amount of alive heap memory
1141 // are calculated by scanning all spans.
1142 // Total number of mallocs is calculated as number of frees plus number of alive objects.
1143 // Similarly, total amount of allocated memory is calculated as amount of freed memory
1144 // plus amount of alive heap memory.
1146 memstats.total_alloc = 0
1147 memstats.nmalloc = 0
1149 for i := 0; i < len(memstats.by_size); i++ {
1150 memstats.by_size[i].nmalloc = 0
1151 memstats.by_size[i].nfree = 0
1154 // Flush MCache's to MCentral.
1155 systemstack(flushallmcaches)
1157 // Aggregate local stats.
1160 // Scan all spans and count number of alive objects.
1162 for i := uint32(0); i < mheap_.nspan; i++ {
1164 if s.state != mSpanInUse {
1167 if s.sizeclass == 0 {
1169 memstats.alloc += uint64(s.elemsize)
1171 memstats.nmalloc += uint64(s.ref)
1172 memstats.by_size[s.sizeclass].nmalloc += uint64(s.ref)
1173 memstats.alloc += uint64(s.ref) * uint64(s.elemsize)
1176 unlock(&mheap_.lock)
1178 // Aggregate by size class.
1179 smallfree := uint64(0)
1180 memstats.nfree = mheap_.nlargefree
1181 for i := 0; i < len(memstats.by_size); i++ {
1182 memstats.nfree += mheap_.nsmallfree[i]
1183 memstats.by_size[i].nfree = mheap_.nsmallfree[i]
1184 memstats.by_size[i].nmalloc += mheap_.nsmallfree[i]
1185 smallfree += uint64(mheap_.nsmallfree[i]) * uint64(class_to_size[i])
1187 memstats.nfree += memstats.tinyallocs
1188 memstats.nmalloc += memstats.nfree
1190 // Calculate derived stats.
1191 memstats.total_alloc = uint64(memstats.alloc) + uint64(mheap_.largefree) + smallfree
1192 memstats.heap_alloc = memstats.alloc
1193 memstats.heap_objects = memstats.nmalloc - memstats.nfree
1197 if unsafe.Sizeof(workbuf{}) != _WorkbufSize {
1198 gothrow("runtime: size of Workbuf is suboptimal")
1201 work.markfor = parforalloc(_MaxGcproc)
1202 gcpercent = readgogc()
1203 gcdatamask = unrollglobgcprog((*byte)(unsafe.Pointer(&gcdata)), uintptr(unsafe.Pointer(&edata))-uintptr(unsafe.Pointer(&data)))
1204 gcbssmask = unrollglobgcprog((*byte)(unsafe.Pointer(&gcbss)), uintptr(unsafe.Pointer(&ebss))-uintptr(unsafe.Pointer(&bss)))
1207 func gc_m(start_time int64, eagersweep bool) {
1210 casgstatus(gp, _Grunning, _Gwaiting)
1211 gp.waitreason = "garbage collection"
1213 gc(start_time, eagersweep)
1216 // Work out path from root to bad block.
1218 gc(start_time, eagersweep)
1219 if nbadblock >= int32(len(badblock)) {
1220 gothrow("cannot find path to bad pointer")
1225 casgstatus(gp, _Gwaiting, _Grunning)
1228 func gc(start_time int64, eagersweep bool) {
1233 if debug.allocfreetrace > 0 {
1240 work.tstart = start_time
1243 if debug.gctrace > 0 {
1247 // Sweep what is not sweeped by bgsweep.
1248 for sweepone() != ^uintptr(0) {
1252 // Cache runtime.mheap_.allspans in work.spans to avoid conflicts with
1253 // resizing/freeing allspans.
1254 // New spans can be created while GC progresses, but they are not garbage for
1256 // - new stack spans can be created even while the world is stopped.
1257 // - new malloc spans can be created during the concurrent sweep
1259 // Even if this is stop-the-world, a concurrent exitsyscall can allocate a stack from heap.
1261 // Free the old cached sweep array if necessary.
1262 if work.spans != nil && &work.spans[0] != &h_allspans[0] {
1263 sysFree(unsafe.Pointer(&work.spans[0]), uintptr(len(work.spans))*unsafe.Sizeof(work.spans[0]), &memstats.other_sys)
1265 // Cache the current array for marking.
1266 mheap_.gcspans = mheap_.allspans
1267 work.spans = h_allspans
1268 unlock(&mheap_.lock)
1272 work.nproc = uint32(gcprocs())
1273 parforsetup(work.markfor, work.nproc, uint32(_RootCount+allglen), nil, false, markroot)
1275 noteclear(&work.alldone)
1276 helpgc(int32(work.nproc))
1280 if debug.gctrace > 0 {
1285 parfordo(work.markfor)
1286 scanblock(0, 0, nil)
1289 if debug.gctrace > 0 {
1294 notesleep(&work.alldone)
1300 // next_gc calculation is tricky with concurrent sweep since we don't know size of live heap
1301 // estimate what was live heap size after previous GC (for printing only)
1302 heap0 := memstats.next_gc * 100 / (uint64(gcpercent) + 100)
1303 // conservatively set next_gc to high value assuming that everything is live
1304 // concurrent/lazy sweep will reduce this number while discovering new garbage
1305 memstats.next_gc = memstats.heap_alloc + memstats.heap_alloc*uint64(gcpercent)/100
1308 atomicstore64(&memstats.last_gc, uint64(unixnanotime())) // must be Unix time to make sense to user
1309 memstats.pause_ns[memstats.numgc%uint32(len(memstats.pause_ns))] = uint64(t4 - t0)
1310 memstats.pause_end[memstats.numgc%uint32(len(memstats.pause_end))] = uint64(t4)
1311 memstats.pause_total_ns += uint64(t4 - t0)
1313 if memstats.debuggc {
1314 print("pause ", t4-t0, "\n")
1317 if debug.gctrace > 0 {
1318 heap1 := memstats.heap_alloc
1320 updatememstats(&stats)
1321 if heap1 != memstats.heap_alloc {
1322 print("runtime: mstats skew: heap=", heap1, "/", memstats.heap_alloc, "\n")
1323 gothrow("mstats skew")
1325 obj := memstats.nmalloc - memstats.nfree
1327 stats.nprocyield += work.markfor.nprocyield
1328 stats.nosyield += work.markfor.nosyield
1329 stats.nsleep += work.markfor.nsleep
1331 print("gc", memstats.numgc, "(", work.nproc, "): ",
1332 (t1-t0)/1000, "+", (t2-t1)/1000, "+", (t3-t2)/1000, "+", (t4-t3)/1000, " us, ",
1333 heap0>>20, " -> ", heap1>>20, " MB, ",
1334 obj, " (", memstats.nmalloc, "-", memstats.nfree, ") objects, ",
1335 gcount(), " goroutines, ",
1336 len(work.spans), "/", sweep.nbgsweep, "/", sweep.npausesweep, " sweeps, ",
1337 stats.nhandoff, "(", stats.nhandoffcnt, ") handoff, ",
1338 work.markfor.nsteal, "(", work.markfor.nstealcnt, ") steal, ",
1339 stats.nprocyield, "/", stats.nosyield, "/", stats.nsleep, " yields\n")
1341 sweep.npausesweep = 0
1344 // See the comment in the beginning of this function as to why we need the following.
1345 // Even if this is still stop-the-world, a concurrent exitsyscall can allocate a stack from heap.
1347 // Free the old cached mark array if necessary.
1348 if work.spans != nil && &work.spans[0] != &h_allspans[0] {
1349 sysFree(unsafe.Pointer(&work.spans[0]), uintptr(len(work.spans))*unsafe.Sizeof(work.spans[0]), &memstats.other_sys)
1352 // Cache the current array for sweeping.
1353 mheap_.gcspans = mheap_.allspans
1354 mheap_.sweepgen += 2
1355 mheap_.sweepdone = 0
1356 work.spans = h_allspans
1358 unlock(&mheap_.lock)
1360 if _ConcurrentSweep && !eagersweep {
1364 sweep.started = true
1365 } else if sweep.parked {
1366 sweep.parked = false
1371 // Sweep all spans eagerly.
1372 for sweepone() != ^uintptr(0) {
1375 // Do an additional mProf_GC, because all 'free' events are now real as well.
1387 func readmemstats_m(stats *MemStats) {
1390 // Size of the trailing by_size array differs between Go and C,
1391 // NumSizeClasses was changed, but we can not change Go struct because of backward compatibility.
1392 memmove(unsafe.Pointer(stats), unsafe.Pointer(&memstats), sizeof_C_MStats)
1394 // Stack numbers are part of the heap numbers, separate those out for user consumption
1395 stats.StackSys = stats.StackInuse
1396 stats.HeapInuse -= stats.StackInuse
1397 stats.HeapSys -= stats.StackInuse
1400 //go:linkname readGCStats runtime/debug.readGCStats
1401 func readGCStats(pauses *[]uint64) {
1402 systemstack(func() {
1403 readGCStats_m(pauses)
1407 func readGCStats_m(pauses *[]uint64) {
1409 // Calling code in runtime/debug should make the slice large enough.
1410 if cap(p) < len(memstats.pause_ns)+3 {
1411 gothrow("runtime: short slice passed to readGCStats")
1414 // Pass back: pauses, pause ends, last gc (absolute time), number of gc, total pause ns.
1418 if n > uint32(len(memstats.pause_ns)) {
1419 n = uint32(len(memstats.pause_ns))
1422 // The pause buffer is circular. The most recent pause is at
1423 // pause_ns[(numgc-1)%len(pause_ns)], and then backward
1424 // from there to go back farther in time. We deliver the times
1425 // most recent first (in p[0]).
1427 for i := uint32(0); i < n; i++ {
1428 j := (memstats.numgc - 1 - i) % uint32(len(memstats.pause_ns))
1429 p[i] = memstats.pause_ns[j]
1430 p[n+i] = memstats.pause_end[j]
1433 p[n+n] = memstats.last_gc
1434 p[n+n+1] = uint64(memstats.numgc)
1435 p[n+n+2] = memstats.pause_total_ns
1436 unlock(&mheap_.lock)
1440 func setGCPercent(in int32) (out int32) {
1447 unlock(&mheap_.lock)
1451 func gchelperstart() {
1454 if _g_.m.helpgc < 0 || _g_.m.helpgc >= _MaxGcproc {
1455 gothrow("gchelperstart: bad m->helpgc")
1457 if _g_ != _g_.m.g0 {
1458 gothrow("gchelper not running on g0 stack")
1462 func wakefing() *g {
1465 if fingwait && fingwake {
1474 func addb(p *byte, n uintptr) *byte {
1475 return (*byte)(add(unsafe.Pointer(p), n))
1478 // Recursively unrolls GC program in prog.
1479 // mask is where to store the result.
1480 // ppos is a pointer to position in mask, in bits.
1481 // sparse says to generate 4-bits per word mask for heap (2-bits for data/bss otherwise).
1482 func unrollgcprog1(maskp *byte, prog *byte, ppos *uintptr, inplace, sparse bool) *byte {
1483 arena_start := mheap_.arena_start
1485 mask := (*[1 << 30]byte)(unsafe.Pointer(maskp))
1489 gothrow("unrollgcprog: unknown instruction")
1492 prog = addb(prog, 1)
1494 prog = addb(prog, 1)
1495 p := (*[1 << 30]byte)(unsafe.Pointer(prog))
1496 for i := 0; i < siz; i++ {
1497 v := p[i/_PointersPerByte]
1498 v >>= (uint(i) % _PointersPerByte) * _BitsPerPointer
1501 // Store directly into GC bitmap.
1502 off := (uintptr(unsafe.Pointer(&mask[pos])) - arena_start) / ptrSize
1503 bitp := (*byte)(unsafe.Pointer(arena_start - off/wordsPerBitmapByte - 1))
1504 shift := (off % wordsPerBitmapByte) * gcBits
1508 *bitp |= v << (shift + 2)
1519 pos += _BitsPerPointer
1522 prog = addb(prog, round(uintptr(siz)*_BitsPerPointer, 8)/8)
1525 prog = (*byte)(add(unsafe.Pointer(prog), 1))
1527 for i := uintptr(0); i < ptrSize; i++ {
1528 siz = (siz << 8) + uintptr(*(*byte)(add(unsafe.Pointer(prog), ptrSize-i-1)))
1530 prog = (*byte)(add(unsafe.Pointer(prog), ptrSize))
1532 for i := uintptr(0); i < siz; i++ {
1533 prog1 = unrollgcprog1(&mask[0], prog, &pos, inplace, sparse)
1535 if *prog1 != insArrayEnd {
1536 gothrow("unrollgcprog: array does not end with insArrayEnd")
1538 prog = (*byte)(add(unsafe.Pointer(prog1), 1))
1540 case insArrayEnd, insEnd:
1547 // Unrolls GC program prog for data/bss, returns dense GC mask.
1548 func unrollglobgcprog(prog *byte, size uintptr) bitvector {
1549 masksize := round(round(size, ptrSize)/ptrSize*bitsPerPointer, 8) / 8
1550 mask := (*[1 << 30]byte)(persistentalloc(masksize+1, 0, &memstats.gc_sys))
1551 mask[masksize] = 0xa1
1553 prog = unrollgcprog1(&mask[0], prog, &pos, false, false)
1554 if pos != size/ptrSize*bitsPerPointer {
1555 print("unrollglobgcprog: bad program size, got ", pos, ", expect ", size/ptrSize*bitsPerPointer, "\n")
1556 gothrow("unrollglobgcprog: bad program size")
1558 if *prog != insEnd {
1559 gothrow("unrollglobgcprog: program does not end with insEnd")
1561 if mask[masksize] != 0xa1 {
1562 gothrow("unrollglobgcprog: overflow")
1564 return bitvector{int32(masksize * 8), &mask[0]}
1567 func unrollgcproginplace_m(v unsafe.Pointer, typ *_type, size, size0 uintptr) {
1569 prog := (*byte)(unsafe.Pointer(uintptr(typ.gc[1])))
1571 unrollgcprog1((*byte)(v), prog, &pos, true, true)
1574 // Mark first word as bitAllocated.
1575 arena_start := mheap_.arena_start
1576 off := (uintptr(v) - arena_start) / ptrSize
1577 bitp := (*byte)(unsafe.Pointer(arena_start - off/wordsPerBitmapByte - 1))
1578 shift := (off % wordsPerBitmapByte) * gcBits
1579 *bitp |= bitBoundary << shift
1581 // Mark word after last as BitsDead.
1583 off := (uintptr(v) + size0 - arena_start) / ptrSize
1584 bitp := (*byte)(unsafe.Pointer(arena_start - off/wordsPerBitmapByte - 1))
1585 shift := (off % wordsPerBitmapByte) * gcBits
1586 *bitp &= uint8(^(bitPtrMask << shift) | uintptr(bitsDead)<<(shift+2))
1592 // Unrolls GC program in typ.gc[1] into typ.gc[0]
1593 func unrollgcprog_m(typ *_type) {
1595 mask := (*byte)(unsafe.Pointer(uintptr(typ.gc[0])))
1597 pos := uintptr(8) // skip the unroll flag
1598 prog := (*byte)(unsafe.Pointer(uintptr(typ.gc[1])))
1599 prog = unrollgcprog1(mask, prog, &pos, false, true)
1600 if *prog != insEnd {
1601 gothrow("unrollgcprog: program does not end with insEnd")
1603 if typ.size/ptrSize%2 != 0 {
1604 // repeat the program
1605 prog := (*byte)(unsafe.Pointer(uintptr(typ.gc[1])))
1606 unrollgcprog1(mask, prog, &pos, false, true)
1609 // atomic way to say mask[0] = 1
1615 // mark the span of memory at v as having n blocks of the given size.
1616 // if leftover is true, there is left over space at the end of the span.
1617 func markspan(v unsafe.Pointer, size uintptr, n uintptr, leftover bool) {
1618 if uintptr(v)+size*n > mheap_.arena_used || uintptr(v) < mheap_.arena_start {
1619 gothrow("markspan: bad pointer")
1622 // Find bits of the beginning of the span.
1623 off := (uintptr(v) - uintptr(mheap_.arena_start)) / ptrSize
1624 if off%wordsPerBitmapByte != 0 {
1625 gothrow("markspan: unaligned length")
1627 b := mheap_.arena_start - off/wordsPerBitmapByte - 1
1629 // Okay to use non-atomic ops here, because we control
1630 // the entire span, and each bitmap byte has bits for only
1631 // one span, so no other goroutines are changing these bitmap words.
1633 if size == ptrSize {
1634 // Possible only on 64-bits (minimal size class is 8 bytes).
1635 // Set memory to 0x11.
1636 if (bitBoundary|bitsDead)<<gcBits|bitBoundary|bitsDead != 0x11 {
1637 gothrow("markspan: bad bits")
1639 if n%(wordsPerBitmapByte*ptrSize) != 0 {
1640 gothrow("markspan: unaligned length")
1642 b = b - n/wordsPerBitmapByte + 1 // find first byte
1644 gothrow("markspan: unaligned pointer")
1646 for i := uintptr(0); i < n; i, b = i+wordsPerBitmapByte*ptrSize, b+ptrSize {
1647 *(*uintptr)(unsafe.Pointer(b)) = uintptrMask & 0x1111111111111111 // bitBoundary | bitsDead, repeated
1653 n++ // mark a boundary just past end of last block too
1655 step := size / (ptrSize * wordsPerBitmapByte)
1656 for i := uintptr(0); i < n; i, b = i+1, b-step {
1657 *(*byte)(unsafe.Pointer(b)) = bitBoundary | bitsDead<<2
1661 // unmark the span of memory at v of length n bytes.
1662 func unmarkspan(v, n uintptr) {
1663 if v+n > mheap_.arena_used || v < mheap_.arena_start {
1664 gothrow("markspan: bad pointer")
1667 off := (v - mheap_.arena_start) / ptrSize // word offset
1668 if off%(ptrSize*wordsPerBitmapByte) != 0 {
1669 gothrow("markspan: unaligned pointer")
1672 b := mheap_.arena_start - off/wordsPerBitmapByte - 1
1674 if n%(ptrSize*wordsPerBitmapByte) != 0 {
1675 gothrow("unmarkspan: unaligned length")
1678 // Okay to use non-atomic ops here, because we control
1679 // the entire span, and each bitmap word has bits for only
1680 // one span, so no other goroutines are changing these
1682 n /= wordsPerBitmapByte
1683 memclr(unsafe.Pointer(b-n+1), n)
1686 func mHeap_MapBits(h *mheap) {
1687 // Caller has added extra mappings to the arena.
1688 // Add extra mappings of bitmap words as needed.
1689 // We allocate extra bitmap pieces in chunks of bitmapChunk.
1690 const bitmapChunk = 8192
1692 n := (h.arena_used - h.arena_start) / (ptrSize * wordsPerBitmapByte)
1693 n = round(n, bitmapChunk)
1694 n = round(n, _PhysPageSize)
1695 if h.bitmap_mapped >= n {
1699 sysMap(unsafe.Pointer(h.arena_start-n), n-h.bitmap_mapped, h.arena_reserved, &memstats.gc_sys)
1703 func getgcmaskcb(frame *stkframe, ctxt unsafe.Pointer) bool {
1704 target := (*stkframe)(ctxt)
1705 if frame.sp <= target.sp && target.sp < frame.varp {
1712 // Returns GC type info for object p for testing.
1713 func getgcmask(p unsafe.Pointer, t *_type, mask **byte, len *uintptr) {
1718 if uintptr(unsafe.Pointer(&data)) <= uintptr(p) && uintptr(p) < uintptr(unsafe.Pointer(&edata)) {
1719 n := (*ptrtype)(unsafe.Pointer(t)).elem.size
1721 *mask = &make([]byte, *len)[0]
1722 for i := uintptr(0); i < n; i += ptrSize {
1723 off := (uintptr(p) + i - uintptr(unsafe.Pointer(&data))) / ptrSize
1724 bits := (*(*byte)(add(unsafe.Pointer(gcdatamask.bytedata), off/pointersPerByte)) >> ((off % pointersPerByte) * bitsPerPointer)) & bitsMask
1725 *(*byte)(add(unsafe.Pointer(*mask), i/ptrSize)) = bits
1731 if uintptr(unsafe.Pointer(&bss)) <= uintptr(p) && uintptr(p) < uintptr(unsafe.Pointer(&ebss)) {
1732 n := (*ptrtype)(unsafe.Pointer(t)).elem.size
1734 *mask = &make([]byte, *len)[0]
1735 for i := uintptr(0); i < n; i += ptrSize {
1736 off := (uintptr(p) + i - uintptr(unsafe.Pointer(&bss))) / ptrSize
1737 bits := (*(*byte)(add(unsafe.Pointer(gcbssmask.bytedata), off/pointersPerByte)) >> ((off % pointersPerByte) * bitsPerPointer)) & bitsMask
1738 *(*byte)(add(unsafe.Pointer(*mask), i/ptrSize)) = bits
1746 if mlookup(uintptr(p), &base, &n, nil) != 0 {
1748 *mask = &make([]byte, *len)[0]
1749 for i := uintptr(0); i < n; i += ptrSize {
1750 off := (uintptr(base) + i - mheap_.arena_start) / ptrSize
1751 b := mheap_.arena_start - off/wordsPerBitmapByte - 1
1752 shift := (off % wordsPerBitmapByte) * gcBits
1753 bits := (*(*byte)(unsafe.Pointer(b)) >> (shift + 2)) & bitsMask
1754 *(*byte)(add(unsafe.Pointer(*mask), i/ptrSize)) = bits
1761 frame.sp = uintptr(p)
1763 gentraceback(_g_.m.curg.sched.pc, _g_.m.curg.sched.sp, 0, _g_.m.curg, 0, nil, 1000, getgcmaskcb, noescape(unsafe.Pointer(&frame)), 0)
1764 if frame.fn != nil {
1766 targetpc := frame.continpc
1770 if targetpc != f.entry {
1773 pcdata := pcdatavalue(f, _PCDATA_StackMapIndex, targetpc)
1777 stkmap := (*stackmap)(funcdata(f, _FUNCDATA_LocalsPointerMaps))
1778 if stkmap == nil || stkmap.n <= 0 {
1781 bv := stackmapdata(stkmap, pcdata)
1782 size := uintptr(bv.n) / bitsPerPointer * ptrSize
1783 n := (*ptrtype)(unsafe.Pointer(t)).elem.size
1785 *mask = &make([]byte, *len)[0]
1786 for i := uintptr(0); i < n; i += ptrSize {
1787 off := (uintptr(p) + i - frame.varp + size) / ptrSize
1788 bits := ((*(*byte)(add(unsafe.Pointer(bv.bytedata), off*bitsPerPointer/8))) >> ((off * bitsPerPointer) % 8)) & bitsMask
1789 *(*byte)(add(unsafe.Pointer(*mask), i/ptrSize)) = bits
1794 func unixnanotime() int64 {
1796 gc_unixnanotime(&now)