From c17ee649b04ecdbe973d13f4b6ef087947ba80ea Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Wed, 1 Oct 2014 17:38:09 -0400 Subject: [dev.garbage] cmd/gc: never generate BitsMultiWord LGTM=rlh R=rlh, minux CC=golang-codereviews https://codereview.appspot.com/151940043 --- src/cmd/gc/reflect.c | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/cmd/gc/reflect.c b/src/cmd/gc/reflect.c index 4892ab757..e229b3075 100644 --- a/src/cmd/gc/reflect.c +++ b/src/cmd/gc/reflect.c @@ -1506,11 +1506,9 @@ gengcprog1(ProgGen *g, Type *t, vlong *xoffset) *xoffset += t->width; break; case TINTER: - proggendata(g, BitsMultiWord); - if(isnilinter(t)) - proggendata(g, BitsEface); - else - proggendata(g, BitsIface); + // Assuming IfacePointerOnly=1. + proggendata(g, BitsPointer); + proggendata(g, BitsPointer); *xoffset += t->width; break; case TARRAY: -- cgit v1.2.1 From 59a42ca068d7cbe0b92f2f68768129599a6c42f8 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Thu, 2 Oct 2014 14:26:04 -0400 Subject: [dev.garbage] runtime: remove another BitsMultiWord Not found because it was not used by name. Add name in comments for what's left behind. LGTM=rlh R=rlh CC=golang-codereviews https://codereview.appspot.com/148430043 --- src/cmd/gc/plive.c | 19 ++++++------------- src/runtime/gcinfo_test.go | 4 ++-- 2 files changed, 8 insertions(+), 15 deletions(-) (limited to 'src') diff --git a/src/cmd/gc/plive.c b/src/cmd/gc/plive.c index 0feb2c710..3bfa69b1f 100644 --- a/src/cmd/gc/plive.c +++ b/src/cmd/gc/plive.c @@ -1092,7 +1092,7 @@ twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv) case TCOMPLEX64: case TCOMPLEX128: for(i = 0; i < t->width; i++) { - bvset(bv, ((*xoffset + i) / widthptr) * BitsPerPointer); // 1 = live scalar + bvset(bv, ((*xoffset + i) / widthptr) * BitsPerPointer); // 1 = live scalar (BitsScalar) } *xoffset += t->width; break; @@ -1105,7 +1105,7 @@ twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv) case TMAP: if((*xoffset & (widthptr-1)) != 0) fatal("twobitwalktype1: invalid alignment, %T", t); - bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 1); // 2 = live ptr + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 1); // 2 = live ptr (BitsPointer) *xoffset += t->width; break; @@ -1113,7 +1113,7 @@ twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv) // struct { byte *str; intgo len; } if((*xoffset & (widthptr-1)) != 0) fatal("twobitwalktype1: invalid alignment, %T", t); - bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 1); // 2 = live ptr in first slot + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 1); // 2 = live ptr in first slot (BitsPointer) *xoffset += t->width; break; @@ -1123,15 +1123,8 @@ twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv) // struct { Type *type; union { void *ptr, uintptr val } data; } if((*xoffset & (widthptr-1)) != 0) fatal("twobitwalktype1: invalid alignment, %T", t); - bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 0); - bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 1); // 3 = multiword - // next word contains 2 = Iface, 3 = Eface - if(isnilinter(t)) { - bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 2); - bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 3); - } else { - bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 3); - } + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 1); // 2 = live ptr in first slot (BitsPointer) + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 3); // 2 = live ptr in second slot (BitsPointer) *xoffset += t->width; break; @@ -1144,7 +1137,7 @@ twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv) // struct { byte *array; uintgo len; uintgo cap; } if((*xoffset & (widthptr-1)) != 0) fatal("twobitwalktype1: invalid TARRAY alignment, %T", t); - bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 1); // 2 = live ptr in first slot + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 1); // 2 = live ptr in first slot (BitsPointer) *xoffset += t->width; } else for(i = 0; i < t->bound; i++) diff --git a/src/runtime/gcinfo_test.go b/src/runtime/gcinfo_test.go index 88f6703f9..e74d8c2c0 100644 --- a/src/runtime/gcinfo_test.go +++ b/src/runtime/gcinfo_test.go @@ -188,6 +188,6 @@ var ( infoString = []byte{BitsPointer, BitsDead} infoSlice = []byte{BitsPointer, BitsDead, BitsDead} - infoEface = []byte{BitsMultiWord, BitsEface} - infoIface = []byte{BitsMultiWord, BitsIface} + infoEface = []byte{BitsPointer, BitsPointer} + infoIface = []byte{BitsPointer, BitsPointer} ) -- cgit v1.2.1 From 5fc8be8db6a4e7a0e43718e6b21d2b78e5aacf5f Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Thu, 2 Oct 2014 16:49:11 -0400 Subject: [dev.garbage] runtime: make sure G.param and SudoG.elem do not hold stale pointers In old conservative Go, this could cause memory leaks. A new pickier collector might reasonably crash when it saw one of these. LGTM=rlh R=rlh CC=golang-codereviews https://codereview.appspot.com/147480043 --- src/runtime/chan.go | 11 +++++++++-- src/runtime/proc.go | 13 +++++++++++++ src/runtime/select.go | 7 +++++++ src/runtime/sema.go | 1 + 4 files changed, 30 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/runtime/chan.go b/src/runtime/chan.go index 48925b2e3..10503f4e1 100644 --- a/src/runtime/chan.go +++ b/src/runtime/chan.go @@ -140,10 +140,11 @@ func chansend(t *chantype, c *hchan, ep unsafe.Pointer, block bool, callerpc uin unlock(&c.lock) recvg := sg.g - recvg.param = unsafe.Pointer(sg) if sg.elem != nil { memmove(unsafe.Pointer(sg.elem), ep, uintptr(c.elemsize)) + sg.elem = nil } + recvg.param = unsafe.Pointer(sg) if sg.releasetime != 0 { sg.releasetime = cputicks() } @@ -179,6 +180,7 @@ func chansend(t *chantype, c *hchan, ep unsafe.Pointer, block bool, callerpc uin } panic("send on closed channel") } + gp.param = nil if mysg.releasetime > 0 { blockevent(int64(mysg.releasetime)-t0, 2) } @@ -278,6 +280,7 @@ func closechan(c *hchan) { break } gp := sg.g + sg.elem = nil gp.param = nil if sg.releasetime != 0 { sg.releasetime = cputicks() @@ -292,6 +295,7 @@ func closechan(c *hchan) { break } gp := sg.g + sg.elem = nil gp.param = nil if sg.releasetime != 0 { sg.releasetime = cputicks() @@ -372,6 +376,7 @@ func chanrecv(t *chantype, c *hchan, ep unsafe.Pointer, block bool) (selected, r if ep != nil { memmove(ep, sg.elem, uintptr(c.elemsize)) } + sg.elem = nil gp := sg.g gp.param = unsafe.Pointer(sg) if sg.releasetime != 0 { @@ -409,9 +414,11 @@ func chanrecv(t *chantype, c *hchan, ep unsafe.Pointer, block bool) (selected, r if mysg.releasetime > 0 { blockevent(mysg.releasetime-t0, 2) } + haveData := gp.param != nil + gp.param = nil releaseSudog(mysg) - if gp.param != nil { + if haveData { // a sender sent us some data. It already wrote to ep. selected = true received = true diff --git a/src/runtime/proc.go b/src/runtime/proc.go index 9b9586859..eefe8239f 100644 --- a/src/runtime/proc.go +++ b/src/runtime/proc.go @@ -148,6 +148,9 @@ func acquireSudog() *sudog { c := gomcache() s := c.sudogcache if s != nil { + if s.elem != nil { + gothrow("acquireSudog: found s.elem != nil in cache") + } c.sudogcache = s.next return s } @@ -162,12 +165,22 @@ func acquireSudog() *sudog { // which keeps the garbage collector from being invoked. mp := acquirem() p := new(sudog) + if p.elem != nil { + gothrow("acquireSudog: found p.elem != nil after new") + } releasem(mp) return p } //go:nosplit func releaseSudog(s *sudog) { + if s.elem != nil { + gothrow("runtime: sudog with non-nil elem") + } + gp := getg() + if gp.param != nil { + gothrow("runtime: releaseSudog with non-nil gp.param") + } c := gomcache() s.next = c.sudogcache c.sudogcache = s diff --git a/src/runtime/select.go b/src/runtime/select.go index 7716d2d4b..1bcea8c4b 100644 --- a/src/runtime/select.go +++ b/src/runtime/select.go @@ -368,6 +368,7 @@ loop: // someone woke us up sellock(sel) sg = (*sudog)(gp.param) + gp.param = nil // pass 3 - dequeue from unsuccessful chans // otherwise they stack up on quiet channels @@ -376,6 +377,10 @@ loop: // iterating through the linked list they are in reverse order. cas = nil sglist = gp.waiting + // Clear all elem before unlinking from gp.waiting. + for sg1 := gp.waiting; sg1 != nil; sg1 = sg1.waitlink { + sg1.elem = nil + } gp.waiting = nil for i := int(sel.ncase) - 1; i >= 0; i-- { k = &scases[pollorder[i]] @@ -506,6 +511,7 @@ syncrecv: if cas.elem != nil { memmove(cas.elem, sg.elem, uintptr(c.elemsize)) } + sg.elem = nil gp = sg.g gp.param = unsafe.Pointer(sg) if sg.releasetime != 0 { @@ -541,6 +547,7 @@ syncsend: if sg.elem != nil { memmove(sg.elem, cas.elem, uintptr(c.elemsize)) } + sg.elem = nil gp = sg.g gp.param = unsafe.Pointer(sg) if sg.releasetime != 0 { diff --git a/src/runtime/sema.go b/src/runtime/sema.go index beacd6716..142d3082c 100644 --- a/src/runtime/sema.go +++ b/src/runtime/sema.go @@ -168,6 +168,7 @@ func (root *semaRoot) dequeue(s *sudog) { } else { root.head = s.next } + s.elem = nil s.next = nil s.prev = nil } -- cgit v1.2.1 From 4eb6792aa572c7e6d3448d4cf22223b61b65724f Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Fri, 3 Oct 2014 11:33:57 -0400 Subject: [dev.garbage] runtime: scan and mark phase refactoring Refactoring of the scan and mark phase so that concurrent GC, in particular the write barrier, can share a common infrastructure. Now that the scan and mark phases have been separated we will be able to scan stacks without blackening any objects. This in turn will allow us to delay installing expensive write barrier code. LGTM=rsc R=rsc, khr, dvyukov CC=golang-codereviews https://codereview.appspot.com/145640044 Committer: Russ Cox --- src/runtime/malloc.h | 10 +- src/runtime/mgc0.c | 627 ++++++++++++++++++++++++++++++-------------------- src/runtime/proc.c | 3 +- src/runtime/runtime.h | 27 ++- 4 files changed, 404 insertions(+), 263 deletions(-) (limited to 'src') diff --git a/src/runtime/malloc.h b/src/runtime/malloc.h index 3f1981f70..413870c9f 100644 --- a/src/runtime/malloc.h +++ b/src/runtime/malloc.h @@ -86,6 +86,7 @@ typedef struct MSpan MSpan; typedef struct MStats MStats; typedef struct MLink MLink; typedef struct GCStats GCStats; +typedef struct Workbuf Workbuf; enum { @@ -337,8 +338,11 @@ struct MCache StackFreeList stackcache[NumStackOrders]; SudoG* sudogcache; - - void* gcworkbuf; + // Cached P local buffer holding grey objects (marked by not yet scanned) + // Used by mutator for write barrier work. + // GC uses the mcache of the P it is running on for stack and global scanning + // work as well marking. + Workbuf* gcworkbuf; // Local allocator stats, flushed during GC. uintptr local_nlookup; // number of pointer lookups @@ -350,7 +354,7 @@ struct MCache MSpan* runtime·MCache_Refill(MCache *c, int32 sizeclass); void runtime·MCache_ReleaseAll(MCache *c); void runtime·stackcache_clear(MCache *c); -void runtime·gcworkbuffree(void *b); +void runtime·gcworkbuffree(Workbuf *b); enum { diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index 7a3498ae1..b4cd3474d 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -66,7 +66,6 @@ enum { Debug = 0, ConcurrentSweep = 1, - WorkbufSize = 4*1024, FinBlockSize = 4*1024, RootData = 0, RootBss = 1, @@ -97,12 +96,12 @@ extern int32 runtime·gcpercent; // uint32 runtime·worldsema = 1; -typedef struct Workbuf Workbuf; -struct Workbuf -{ - LFNode node; // must be first - uintptr nobj; - byte* obj[(WorkbufSize-sizeof(LFNode)-sizeof(uintptr))/PtrSize]; +typedef struct Markbits Markbits; +struct Markbits { + byte *bitp; // pointer to the byte holding xbits + byte shift; // bits xbits needs to be shifted to get bits + byte xbits; // byte holding all the bits from *bitp + byte bits; // bits relevant to corresponding slot. }; extern byte runtime·data[]; @@ -127,15 +126,22 @@ BitVector runtime·gcbssmask; Mutex runtime·gclock; +static Workbuf* getpartial(void); +static void putpartial(Workbuf*); static Workbuf* getempty(Workbuf*); static Workbuf* getfull(Workbuf*); static void putempty(Workbuf*); static Workbuf* handoff(Workbuf*); static void gchelperstart(void); static void flushallmcaches(void); -static bool scanframe(Stkframe *frame, void *unused); -static void scanstack(G *gp); -static BitVector unrollglobgcprog(byte *prog, uintptr size); +static bool scanframe(Stkframe*, void*); +static void scanstack(G*); +static BitVector unrollglobgcprog(byte*, uintptr); +static void scanblock(byte*, uintptr, byte*); +static byte* objectstart(byte*, Markbits*); +static Workbuf* greyobject(byte*, Markbits*, Workbuf*); +static bool inheap(byte*); +static void slottombits(byte*, Markbits*); void runtime·bgsweep(void); static FuncVal bgsweepv = {runtime·bgsweep}; @@ -156,258 +162,279 @@ static struct { uint32 nspan; } work; -// scanblock scans a block of n bytes starting at pointer b for references -// to other objects, scanning any it finds recursively until there are no -// unscanned objects left. Instead of using an explicit recursion, it keeps -// a work list in the Workbuf* structures and loops in the main function -// body. Keeping an explicit work list is easier on the stack allocator and -// more efficient. +// Is address b in the known heap. If it doesn't have a valid gcmap +// returns false. For example pointers into stacks will return false. +static bool +inheap(byte *b) +{ + MSpan *s; + pageID k; + uintptr x; + + if(b == nil || b < runtime·mheap.arena_start || b >= runtime·mheap.arena_used) + return false; + // Not a beginning of a block, consult span table to find the block beginning. + k = (uintptr)b>>PageShift; + x = k; + x -= (uintptr)runtime·mheap.arena_start>>PageShift; + s = runtime·mheap.spans[x]; + if(s == nil || k < s->start || b >= s->limit || s->state != MSpanInUse) + return false; + return true; +} + +// Given an address in the heap return the relevant byte from the gcmap. This routine +// can be used on addresses to the start of an object or to the interior of the an object. static void -scanblock(byte *b, uintptr n, byte *ptrmask) +slottombits(byte *obj, Markbits *mbits) { - byte *obj, *p, *arena_start, *arena_used, **wp, *scanbuf[8], *ptrbitp, *bitp, bits, xbits, shift, cached; - uintptr i, nobj, size, idx, x, off, scanbufpos; - intptr ncached; - Workbuf *wbuf; - Iface *iface; - Eface *eface; - Type *typ; + uintptr off; + + off = (uintptr*)((uintptr)obj&~(PtrSize-1)) - (uintptr*)runtime·mheap.arena_start; + mbits->bitp = runtime·mheap.arena_start - off/wordsPerBitmapByte - 1; + mbits->shift = (off % wordsPerBitmapByte) * gcBits; + mbits->xbits = *mbits->bitp; + mbits->bits = (mbits->xbits >> mbits->shift) & bitMask; +} + +// b is a pointer into the heap. +// Find the start of the object refered to by b. +// Set mbits to the associated bits from the bit map. +static byte* +objectstart(byte *b, Markbits *mbits) +{ + byte *obj, *p; MSpan *s; pageID k; - bool keepworking; + uintptr x, size, idx; - // Cache memory arena parameters in local vars. - arena_start = runtime·mheap.arena_start; - arena_used = runtime·mheap.arena_used; + obj = (byte*)((uintptr)b&~(PtrSize-1)); + for(;;) { + slottombits(obj, mbits); + if(mbits->bits&bitBoundary == bitBoundary) + break; + + // Not a beginning of a block, consult span table to find the block beginning. + k = (uintptr)obj>>PageShift; + x = k; + x -= (uintptr)runtime·mheap.arena_start>>PageShift; + s = runtime·mheap.spans[x]; + if(s == nil || k < s->start || obj >= s->limit || s->state != MSpanInUse){ + if(s->state == MSpanStack) + break; // This is legit. + + // The following is catching some bugs left over from + // us not being rigerous about what data structures are + // hold valid pointers and different parts of the system + // considering different structures as roots. For example + // if there is a pointer into a stack that is left in + // a global data structure but that part of the runtime knows that + // those structures will be reinitialized before they are + // reused. Unfortunately the GC believes these roots are valid. + // Typically a stack gets moved and only the structures that part of + // the system knows are alive are updated. The span is freed + // after the stack copy and the pointer is still alive. This + // check is catching that bug but for now we will not throw, + // instead we will simply break out of this routine and depend + // on the caller to recognize that this pointer is not a valid + // heap pointer. I leave the code that catches the bug so that once + // resolved we can turn this check back on and throw. + + //runtime·printf("Runtime: Span weird: obj=%p, k=%p", obj, k); + //if (s == nil) + // runtime·printf(" s=nil\n"); + //else + // runtime·printf(" s->start=%p s->limit=%p, s->state=%d\n", s->start*PageSize, s->limit, s->state); + //runtime·throw("Blowup on weird span"); + break; // We are not in a real block throw?? + } + p = (byte*)((uintptr)s->start<sizeclass != 0) { + size = s->elemsize; + idx = ((byte*)obj - p)/size; + p = p+idx*size; + } + if(p == obj) { + runtime·printf("runtime: failed to find block beginning for %p s=%p s->limit=%p\n", + p, s->start*PageSize, s->limit); + runtime·throw("failed to find block beginning"); + } + obj = p; + } + // if size(obj.firstfield) < PtrSize, the &obj.secondfield could map to the boundary bit + // Clear any low bits to get to the start of the object. + // greyobject depends on this. + return obj; +} - wbuf = getempty(nil); - nobj = wbuf->nobj; - wp = &wbuf->obj[nobj]; - keepworking = b == nil; - scanbufpos = 0; - for(i = 0; i < nelem(scanbuf); i++) - scanbuf[i] = nil; +// obj is the start of an object with mark mbits. +// If it isn't already marked, mark it and enqueue into workbuf. +// Return possibly new workbuf to use. +static Workbuf* +greyobject(byte *obj, Markbits *mbits, Workbuf *wbuf) +{ + // obj should be start of allocation, and so must be at least pointer-aligned. + if(((uintptr)obj & (PtrSize-1)) != 0) + runtime·throw("greyobject: obj not pointer-aligned"); + + // If marked we have nothing to do. + if((mbits->bits&bitMarked) != 0) + return wbuf; + + // Each byte of GC bitmap holds info for two words. + // If the current object is larger than two words, or if the object is one word + // but the object it shares the byte with is already marked, + // then all the possible concurrent updates are trying to set the same bit, + // so we can use a non-atomic update. + if((mbits->xbits&(bitMask|(bitMask<bitp = mbits->xbits | (bitMarked<shift); + else + runtime·atomicor8(mbits->bitp, bitMarked<shift); + + if(((mbits->xbits>>(mbits->shift+2))&BitsMask) == BitsDead) + return wbuf; // noscan object + + // Queue the obj for scanning. The PREFETCH(obj) logic has been removed but + // seems like a nice optimization that can be added back in. + // There needs to be time between the PREFETCH and the use. + // Previously we put the obj in an 8 element buffer that is drained at a rate + // to give the PREFETCH time to do its work. + // Use of PREFETCHNTA might be more appropriate than PREFETCH + + // If workbuf is full, obtain an empty one. + if(wbuf->nobj >= nelem(wbuf->obj)) { + wbuf = getempty(wbuf); + } + + wbuf->obj[wbuf->nobj] = obj; + wbuf->nobj++; + return wbuf; +} +// Scan the object b of size n, adding pointers to wbuf. +// Return possibly new wbuf to use. +// If ptrmask != nil, it specifies where pointers are in b. +// If ptrmask == nil, the GC bitmap should be consulted. +// In this case, n may be an overestimate of the size; the GC bitmap +// must also be used to make sure the scan stops at the end of b. +static Workbuf* +scanobject(byte *b, uintptr n, byte *ptrmask, Workbuf *wbuf) +{ + byte *obj, *arena_start, *arena_used, *ptrbitp, bits, cshift, cached; + uintptr i; + intptr ncached; + Markbits mbits; + + arena_start = (byte*)runtime·mheap.arena_start; + arena_used = runtime·mheap.arena_used; ptrbitp = nil; cached = 0; ncached = 0; + // Find bits of the beginning of the object. + if(ptrmask == nil) { + b = objectstart(b, &mbits); + ptrbitp = mbits.bitp; //arena_start - off/wordsPerBitmapByte - 1; + cshift = mbits.shift; //(off % wordsPerBitmapByte) * gcBits; + cached = *ptrbitp >> cshift; + cached &= ~bitBoundary; + ncached = (8 - cshift)/gcBits; + } + for(i = 0; i < n; i += PtrSize) { + // Find bits for this word. + if(ptrmask != nil) { + // dense mask (stack or data) + bits = (ptrmask[(i/PtrSize)/4]>>(((i/PtrSize)%4)*BitsPerPointer))&BitsMask; + } else { + // Check if we have reached end of span. + if((((uintptr)b+i)%PageSize) == 0 && + runtime·mheap.spans[(b-arena_start)>>PageShift] != runtime·mheap.spans[(b+i-arena_start)>>PageShift]) + break; + // Consult GC bitmap. + if(ncached <= 0) { + // Refill cache. + cached = *--ptrbitp; + ncached = 2; + } + bits = cached; + cached >>= gcBits; + ncached--; + + if((bits&bitBoundary) != 0) + break; // reached beginning of the next object + bits = (bits>>2)&BitsMask; + if(bits == BitsDead) + break; // reached no-scan part of the object + } + + if(bits == BitsScalar || bits == BitsDead) + continue; + if(bits != BitsPointer) + runtime·throw("unexpected garbage collection bits"); + + obj = *(byte**)(b+i); + // At this point we have extracted the next potential pointer. + // Check if it points into heap. + if(obj == nil || obj < arena_start || obj >= arena_used) + continue; + // Mark the object. return some important bits. + // We we combine the following two rotines we don't have to pass mbits or obj around. + obj = objectstart(obj, &mbits); + wbuf = greyobject(obj, &mbits, wbuf); + } + return wbuf; +} + +// scanblock starts by scanning b as scanobject would. +// If the gcphase is GCscan, that's all scanblock does. +// Otherwise it traverses some fraction of the pointers it found in b, recursively. +// As a special case, scanblock(nil, 0, nil) means to scan previously queued work, +// stopping only when no work is left in the system. +static void +scanblock(byte *b, uintptr n, byte *ptrmask) +{ + Workbuf *wbuf; + bool keepworking; + + wbuf = getpartial(); + if(b != nil) { + wbuf = scanobject(b, n, ptrmask, wbuf); + if(runtime·gcphase == GCscan) { + putpartial(wbuf); + return; + } + } + + keepworking = b == nil; + // ptrmask can have 2 possible values: // 1. nil - obtain pointer mask from GC bitmap. // 2. pointer to a compact mask (for stacks and data). - if(b != nil) - goto scanobj; for(;;) { - if(nobj == 0) { - // Out of work in workbuf. - // First, see is there is any work in scanbuf. - for(i = 0; i < nelem(scanbuf); i++) { - b = scanbuf[scanbufpos]; - scanbuf[scanbufpos++] = nil; - if(scanbufpos == nelem(scanbuf)) - scanbufpos = 0; - if(b != nil) { - n = arena_used - b; // scan until bitBoundary or BitsDead - ptrmask = nil; // use GC bitmap for pointer info - goto scanobj; - } - } + if(wbuf->nobj == 0) { if(!keepworking) { putempty(wbuf); return; } // Refill workbuf from global queue. wbuf = getfull(wbuf); - if(wbuf == nil) + if(wbuf == nil) // nil means out of work barrier reached return; - nobj = wbuf->nobj; - wp = &wbuf->obj[nobj]; } // If another proc wants a pointer, give it some. - if(work.nwait > 0 && nobj > 4 && work.full == 0) { - wbuf->nobj = nobj; + if(work.nwait > 0 && wbuf->nobj > 4 && work.full == 0) { wbuf = handoff(wbuf); - nobj = wbuf->nobj; - wp = &wbuf->obj[nobj]; - } - - wp--; - nobj--; - b = *wp; - n = arena_used - b; // scan until next bitBoundary or BitsDead - ptrmask = nil; // use GC bitmap for pointer info - - scanobj: - // Find bits of the beginning of the object. - if(ptrmask == nil) { - off = (uintptr*)b - (uintptr*)arena_start; - ptrbitp = arena_start - off/wordsPerBitmapByte - 1; - shift = (off % wordsPerBitmapByte) * gcBits; - cached = *ptrbitp >> shift; - cached &= ~bitBoundary; - ncached = (8 - shift)/gcBits; - } - for(i = 0; i < n; i += PtrSize) { - obj = nil; - // Find bits for this word. - if(ptrmask == nil) { - // Check is we have reached end of span. - if((((uintptr)b+i)%PageSize) == 0 && - runtime·mheap.spans[(b-arena_start)>>PageShift] != runtime·mheap.spans[(b+i-arena_start)>>PageShift]) - break; - // Consult GC bitmap. - if(ncached <= 0) { - // Refill cache. - cached = *--ptrbitp; - ncached = 2; - } - bits = cached; - cached >>= gcBits; - ncached--; - if((bits&bitBoundary) != 0) - break; // reached beginning of the next object - bits = (bits>>2)&BitsMask; - if(bits == BitsDead) - break; // reached no-scan part of the object - } else // dense mask (stack or data) - bits = (ptrmask[(i/PtrSize)/4]>>(((i/PtrSize)%4)*BitsPerPointer))&BitsMask; - - if(bits == BitsScalar || bits == BitsDead) - continue; - if(bits == BitsPointer) { - obj = *(byte**)(b+i); - goto markobj; - } - - // With those three out of the way, must be multi-word. - if(bits != BitsMultiWord) - runtime·throw("unexpected garbage collection bits"); - // Find the next pair of bits. - if(ptrmask == nil) { - if(ncached <= 0) { - // Refill cache. - cached = *--ptrbitp; - ncached = 2; - } - bits = (cached>>2)&BitsMask; - } else - bits = (ptrmask[((i+PtrSize)/PtrSize)/4]>>((((i+PtrSize)/PtrSize)%4)*BitsPerPointer))&BitsMask; - - switch(bits) { - default: - runtime·throw("unexpected garbage collection bits"); - case BitsIface: - iface = (Iface*)(b+i); - if(iface->tab != nil) { - typ = iface->tab->type; - if(!(typ->kind&KindDirectIface) || !(typ->kind&KindNoPointers)) - obj = iface->data; - } - break; - case BitsEface: - eface = (Eface*)(b+i); - typ = eface->type; - if(typ != nil) { - if(!(typ->kind&KindDirectIface) || !(typ->kind&KindNoPointers)) - obj = eface->data; - } - break; - } - - i += PtrSize; - cached >>= gcBits; - ncached--; - - markobj: - // At this point we have extracted the next potential pointer. - // Check if it points into heap. - if(obj == nil || obj < arena_start || obj >= arena_used) - continue; - // Mark the object. - off = (uintptr*)obj - (uintptr*)arena_start; - bitp = arena_start - off/wordsPerBitmapByte - 1; - shift = (off % wordsPerBitmapByte) * gcBits; - xbits = *bitp; - bits = (xbits >> shift) & bitMask; - if((bits&bitBoundary) == 0) { - // Not a beginning of a block, consult span table to find the block beginning. - k = (uintptr)obj>>PageShift; - x = k; - x -= (uintptr)arena_start>>PageShift; - s = runtime·mheap.spans[x]; - if(s == nil || k < s->start || obj >= s->limit || s->state != MSpanInUse) - continue; - p = (byte*)((uintptr)s->start<sizeclass != 0) { - size = s->elemsize; - idx = ((byte*)obj - p)/size; - p = p+idx*size; - } - if(p == obj) { - runtime·printf("runtime: failed to find block beginning for %p s=%p s->limit=%p\n", - p, s->start*PageSize, s->limit); - runtime·throw("failed to find block beginning"); - } - obj = p; - goto markobj; - } - - // Now we have bits, bitp, and shift correct for - // obj pointing at the base of the object. - // Only care about not marked objects. - if((bits&bitMarked) != 0) - continue; - // If obj size is greater than 8, then each byte of GC bitmap - // contains info for at most one object. In such case we use - // non-atomic byte store to mark the object. This can lead - // to double enqueue of the object for scanning, but scanning - // is an idempotent operation, so it is OK. This cannot lead - // to bitmap corruption because the single marked bit is the - // only thing that can change in the byte. - // For 8-byte objects we use non-atomic store, if the other - // quadruple is already marked. Otherwise we resort to CAS - // loop for marking. - if((xbits&(bitMask|(bitMask<>(shift+2))&BitsMask) == BitsDead) - continue; // noscan object - - // Queue the obj for scanning. - PREFETCH(obj); - obj = (byte*)((uintptr)obj & ~(PtrSize-1)); - p = scanbuf[scanbufpos]; - scanbuf[scanbufpos++] = obj; - if(scanbufpos == nelem(scanbuf)) - scanbufpos = 0; - if(p == nil) - continue; - - // If workbuf is full, obtain an empty one. - if(nobj >= nelem(wbuf->obj)) { - wbuf->nobj = nobj; - wbuf = getempty(wbuf); - nobj = wbuf->nobj; - wp = &wbuf->obj[nobj]; - } - *wp = p; - wp++; - nobj++; } - if(Debug && ptrmask == nil) { - // For heap objects ensure that we did not overscan. - n = 0; - p = nil; - if(!runtime·mlookup(b, &p, &n, nil) || b != p || i > n) { - runtime·printf("runtime: scanned (%p,%p), heap object (%p,%p)\n", b, i, p, n); - runtime·throw("scanblock: scanned invalid object"); - } - } + // This might be a good place to add prefetch code... + // if(wbuf->nobj > 4) { + // PREFETCH(wbuf->obj[wbuf->nobj - 3]; + // } + --wbuf->nobj; + b = wbuf->obj[wbuf->nobj]; + wbuf = scanobject(b, runtime·mheap.arena_used - b, nil, wbuf); } } @@ -460,7 +487,8 @@ markroot(ParFor *desc, uint32 i) spf = (SpecialFinalizer*)sp; // A finalizer can be set for an inner byte of an object, find object beginning. p = (void*)((s->start << PageShift) + spf->special.offset/s->elemsize*s->elemsize); - scanblock(p, s->elemsize, nil); + if(runtime·gcphase != GCscan) + scanblock(p, s->elemsize, nil); // Scanned during mark phase scanblock((void*)&spf->fn, PtrSize, oneptr); } } @@ -477,7 +505,7 @@ markroot(ParFor *desc, uint32 i) gp = runtime·allg[i - RootCount]; // remember when we've first observed the G blocked // needed only to output in traceback - status = runtime·readgstatus(gp); + status = runtime·readgstatus(gp); // We are not in a scan state if((status == Gwaiting || status == Gsyscall) && gp->waitsince == 0) gp->waitsince = work.tstart; // Shrink a stack if not much of it is being used. @@ -487,7 +515,31 @@ markroot(ParFor *desc, uint32 i) else gp->gcworkdone = false; restart = runtime·stopg(gp); - scanstack(gp); + + // goroutine will scan its own stack when it stops running. + // Wait until it has. + while((status = runtime·readgstatus(gp)) == Grunning && !gp->gcworkdone) { + if(status == Gdead) { + // TBD you need to explain why Gdead without gp->gcworkdone + // being true. If there is a race then it needs to be + // explained here. + gp->gcworkdone = true; // scan is a noop + break; + //do nothing, scan not needed. + } + // try again + } + + // scanstack(gp); now done as part of gcphasework + // But to make sure we finished we need to make sure that + // the stack traps have all responded so drop into + // this while loop until they respond. + if(!gp->gcworkdone) + // For some reason a G has not completed its work. This is a bug that + // needs to be investigated. For now I'll just print this message in + // case the bug is benign. + runtime·printf("runtime:markroot: post stack scan work not done gp=%p has status %x\n", gp, status); + if(restart) runtime·restartg(gp); break; @@ -511,8 +563,12 @@ getempty(Workbuf *b) } if(b == nil) b = (Workbuf*)runtime·lfstackpop(&work.empty); - if(b == nil) + if(b == nil) { b = runtime·persistentalloc(sizeof(*b), CacheLineSize, &mstats.gc_sys); + b->nobj = 0; + } + if(b->nobj != 0) + runtime·throw("getempty: b->nobj not 0/n"); b->nobj = 0; return b; } @@ -522,6 +578,8 @@ putempty(Workbuf *b) { MCache *c; + if(b->nobj != 0) + runtime·throw("putempty: b->nobj=%D not 0\n"); c = g->m->mcache; if(c->gcworkbuf == nil) { c->gcworkbuf = b; @@ -530,21 +588,70 @@ putempty(Workbuf *b) runtime·lfstackpush(&work.empty, &b->node); } +// Get an partially empty work buffer from the mcache structure +// and if non is available get an empty one. +static Workbuf* +getpartial(void) +{ + MCache *c; + Workbuf *b; + + c = g->m->mcache; + if(c->gcworkbuf != nil) { + b = c->gcworkbuf; + c->gcworkbuf = nil; + } else { + b = getempty(nil); + } + return b; +} + +static void +putpartial(Workbuf *b) +{ + MCache *c; + + c = g->m->mcache; + if(c->gcworkbuf == nil) { + c->gcworkbuf = b; + return; + } + + runtime·throw("putpartial: c->gcworkbuf is not nil\n"); + + runtime·lfstackpush(&work.full, &b->node); +} + void -runtime·gcworkbuffree(void *b) +runtime·gcworkbuffree(Workbuf *b) { - if(b != nil) + if(b != nil) { + if(b->nobj != 0) + runtime·throw("gcworkbufferfree: b->nobj not 0\n"); putempty(b); + } } + // Get a full work buffer off the work.full list, or return nil. +// getfull acts as a barrier for work.nproc helpers. As long as one +// gchelper is actively marking objects it +// may create a workbuffer that the other helpers can work on. +// The for loop either exits when a work buffer is found +// or when _all_ of the work.nproc gc helpers are in the loop +// looking for work and thus not capable of creating new work. +// This is in fact the termination condition for the STW mark +// phase. static Workbuf* getfull(Workbuf *b) { int32 i; - if(b != nil) + if(b != nil) { + if(b->nobj != 0) + runtime·printf("runtime:getfull: b->nobj=%D not 0.", b->nobj); runtime·lfstackpush(&work.empty, &b->node); + } b = (Workbuf*)runtime·lfstackpop(&work.full); if(b != nil || work.nproc == 1) return b; @@ -674,7 +781,7 @@ scanframe(Stkframe *frame, void *unused) } bv = runtime·stackmapdata(stackmap, pcdata); } - scanblock((byte*)frame->argp, bv.n/BitsPerPointer*PtrSize, bv.bytedata); + scanblock((byte*)frame->argp, bv.n/BitsPerPointer*PtrSize, bv.bytedata); } return true; } @@ -727,12 +834,23 @@ runtime·gcphasework(G *gp) case GCquiesce: case GCstw: case GCsweep: - // No work for now. + // No work. + break; + case GCscan: + // scan the stack, mark the objects, put pointers in work buffers + // hanging off the P where this is being run. + scanstack(gp); break; case GCmark: + case GCmarktermination: + // // Disabled until concurrent GC is implemented // but indicate the scan has been done. - // scanstack(gp); + scanstack(gp); + // scanstack will call shade which will populate + // the Workbuf. + // emptywbuf(gp) will empty it before returning + // break; } gp->gcworkdone = true; @@ -1108,6 +1226,7 @@ runtime·gosweepdone(void) return runtime·mheap.sweepdone; } + void runtime·gchelper(void) { @@ -1118,10 +1237,8 @@ runtime·gchelper(void) // parallel mark for over gc roots runtime·parfordo(work.markfor); - - // help other threads scan secondary blocks - scanblock(nil, 0, nil); - + if(runtime·gcphase != GCscan) + scanblock(nil, 0, nil); // blocks in getfull nproc = work.nproc; // work.nproc can change right after we increment work.ndone if(runtime·xadd(&work.ndone, +1) == nproc-1) runtime·notewakeup(&work.alldone); @@ -1288,6 +1405,7 @@ runtime·gcinit(void) runtime·gcbssmask = unrollglobgcprog(runtime·gcbss, runtime·ebss - runtime·bss); } +// Called from malloc.go using onM, stopping and starting the world handled in caller. void runtime·gc_m(void) { @@ -1311,7 +1429,8 @@ gc(struct gc_args *args) int64 t0, t1, t2, t3, t4; uint64 heap0, heap1, obj; GCStats stats; - + uint32 oldphase; + if(runtime·debug.allocfreetrace) runtime·tracegc(); @@ -1327,7 +1446,7 @@ gc(struct gc_args *args) while(runtime·sweepone() != -1) runtime·sweep.npausesweep++; - // Cache runtime.mheap.allspans in work.spans to avoid conflicts with + // Cache runtime·mheap.allspans in work.spans to avoid conflicts with // resizing/freeing allspans. // New spans can be created while GC progresses, but they are not garbage for // this round: @@ -1344,10 +1463,13 @@ gc(struct gc_args *args) work.spans = runtime·mheap.allspans; work.nspan = runtime·mheap.nspan; runtime·unlock(&runtime·mheap.lock); + oldphase = runtime·gcphase; work.nwait = 0; work.ndone = 0; - work.nproc = runtime·gcprocs(); + work.nproc = runtime·gcprocs(); + runtime·gcphase = GCmark; //^^ vv + runtime·parforsetup(work.markfor, work.nproc, RootCount + runtime·allglen, nil, false, markroot); if(work.nproc > 1) { runtime·noteclear(&work.alldone); @@ -1360,8 +1482,9 @@ gc(struct gc_args *args) gchelperstart(); runtime·parfordo(work.markfor); - scanblock(nil, 0, nil); + scanblock(nil, 0, nil); + runtime·gcphase = oldphase; //^^ vv t3 = 0; if(runtime·debug.gctrace) t3 = runtime·nanotime(); diff --git a/src/runtime/proc.c b/src/runtime/proc.c index 25f916640..1f1044d1d 100644 --- a/src/runtime/proc.c +++ b/src/runtime/proc.c @@ -623,9 +623,10 @@ mquiesce(G *gpmaster) uint32 status; uint32 activeglen; - activeglen = runtime·allglen; // enqueue the calling goroutine. runtime·restartg(gpmaster); + + activeglen = runtime·allglen; for(i = 0; i < activeglen; i++) { gp = runtime·allg[i]; if(runtime·readgstatus(gp) == Gdead) diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index adc74cf41..74d7ba4f5 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -93,6 +93,7 @@ typedef struct PollDesc PollDesc; typedef struct DebugVars DebugVars; typedef struct ForceGCState ForceGCState; typedef struct Stack Stack; +typedef struct Workbuf Workbuf; /* * Per-CPU declaration. @@ -303,7 +304,7 @@ struct G bool paniconfault; // panic (instead of crash) on unexpected fault address bool preemptscan; // preempted g does scan for GC bool gcworkdone; // debug: cleared at begining of gc work phase cycle, set by gcphasework, tested at end of cycle - bool throwsplit; // must not split stack + bool throwsplit; // must not split stack int8 raceignore; // ignore race detection events M* m; // for debuggers, but offset not hard-coded M* lockedm; @@ -561,6 +562,16 @@ struct ParFor uint64 nsleep; }; +enum { + WorkbufSize = 4*1024, +}; +struct Workbuf +{ + LFNode node; // must be first + uintptr nobj; + byte* obj[(WorkbufSize-sizeof(LFNode)-sizeof(uintptr))/PtrSize]; +}; + // Track memory allocated by code not written in Go during a cgo call, // so that the garbage collector can see them. struct CgoMal @@ -583,12 +594,14 @@ struct DebugVars // Indicates to write barrier and sychronization task to preform. enum -{ // Synchronization Write barrier - GCoff, // stop and start nop - GCquiesce, // stop and start nop - GCstw, // stop the ps nop - GCmark, // scan the stacks and start no white to black - GCsweep, // stop and start nop +{ // Action WB installation + GCoff = 0, // stop and start no wb + GCquiesce, // stop and start no wb + GCstw, // stop the ps nop + GCscan, // scan the stacks prior to marking + GCmark, // mark use wbufs from GCscan and globals, scan the stacks, then go to GCtermination + GCmarktermination, // mark termination detection. Allocate black, Ps help out GC + GCsweep, // stop and start nop }; struct ForceGCState -- cgit v1.2.1