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 From af64ab79c0ad72decf083d78cf54257d009741b5 Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Tue, 14 Oct 2014 09:51:46 -0400 Subject: [dev.garbage] runtime: Write barrier code. Comments lay out the concurrent GC algorithms. This CL implements parts of the algorithm. The acknowledgement code has been removed from this CL LGTM=rsc, dvyukov R=dvyukov, rsc CC=golang-codereviews https://codereview.appspot.com/151540043 --- src/runtime/mgc0.c | 145 +++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 129 insertions(+), 16 deletions(-) (limited to 'src') diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index 39fae9bbe..dabd38a60 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -4,22 +4,73 @@ // Garbage collector (GC). // -// GC is: -// - mark&sweep -// - mostly precise (with the exception of some C-allocated objects, assembly frames/arguments, etc) -// - parallel (up to MaxGcproc threads) -// - partially concurrent (mark is stop-the-world, while sweep is concurrent) -// - non-moving/non-compacting -// - full (non-partial) +// The GC runs concurrently with mutator threads, is type accurate (aka precise), allows multiple GC +// thread to run in parallel. It is a concurrent mark and sweep that uses a write barrier. It is +// non-generational and non-compacting. Allocation is done using size segregated per P allocation +// areas to minimize fragmentation while eliminating locks in the common case. // -// GC rate. -// Next GC is after we've allocated an extra amount of memory proportional to -// the amount already in use. The proportion is controlled by GOGC environment variable -// (100 by default). If GOGC=100 and we're using 4M, we'll GC again when we get to 8M -// (this mark is tracked in next_gc variable). This keeps the GC cost in linear -// proportion to the allocation cost. Adjusting GOGC just changes the linear constant -// (and also the amount of extra memory used). +// The algorithm decomposes into several steps. +// This is a high level description of the algorithm being used. For an overview of GC a good +// place to start is Richard Jones' gchandbook.org. +// +// The algorithm's intellectual heritage includes Dijkstra's on-the-fly algorithm, see +// Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. 1978. +// On-the-fly garbage collection: an exercise in cooperation. Commun. ACM 21, 11 (November 1978), 966-975. +// For journal quality proofs that these steps are complete, correct, and terminate see +// Hudson, R., and Moss, J.E.B. Copying Garbage Collection without stopping the world. +// Concurrency and Computation: Practice and Experience 15(3-5), 2003. // +// 0. Set phase = GCscan from GCoff. +// 1. Wait for all P's to acknowledge phase change. +// At this point all goroutines have passed through a GC safepoint and +// know we are in the GCscan phase. +// 2. GC scans all goroutine stacks, mark and enqueues all encountered pointers +// (marking avoids most duplicate enqueuing but races may produce duplication which is benign). +// Preempted goroutines are scanned before P schedules next goroutine. +// 3. Set phase = GCmark. +// 4. Wait for all P's to acknowledge phase change. +// 5. Now write barrier marks and enqueues black or grey to white pointers. If a pointer is +// stored into a white slot, such pointer is not marked. +// Malloc still allocates white (non-marked) objects. +// 6. Meanwhile GC transitively walks the heap marking reachable objects. +// 7. When GC finishes marking heap, it preempts P's one-by-one and +// retakes partial wbufs (filled by write barrier or during a stack scan of the goroutine +// currently scheduled on the P). +// 8. Once the GC has exhausted all available marking work it sets phase = marktermination. +// 9. Wait for all P's to acknowledge phase change. +// 10. Malloc now allocates black objects, so number of unmarked reachable objects +// monotonically decreases. +// 11. GC preempts P's one-by-one taking partial wbufs and marks all unmarked yet reachable objects. +// 12. When GC completes a full cycle over P's and discovers no new grey +// objects, (which means all reachable objects are marked) set phase = GCsweep. +// 13. Wait for all P's to acknowledge phase change. +// 14. Now malloc allocates white (but sweeps spans before use). +// Write barrier becomes nop. +// 15. GC does background sweeping, see description below. +// 16. When sweeping is complete set phase to GCoff. +// 17. When sufficient allocation has taken place replay the sequence starting at 0 above, +// see discussion of GC rate below. + +// Changing phases. +// Phases are changed by setting the gcphase to the next phase and call ackgcphase. +// All phase action must be benign in the presence of a change. +// Starting with GCoff +// GCoff to GCscan +// GSscan scans stacks and globals greying them and never marks an object black. +// Once all the P's are aware of the new phase they will scan gs on preemption. +// This means that the scanning of preempted gs can't start until all the Ps +// have acknowledged. +// GCscan to GCmark +// GCMark turns on the write barrier which also only greys objects. No scanning +// of objects (making them black) can happen until all the Ps have acknowledged +// the phase change. +// GCmark to GCmarktermination +// The only change here is that we start allocating black so the Ps must acknowledge +// the change before we begin the termination algorithm +// GCmarktermination to GSsweep +// Object currently on the freelist must be marked black for this to work. +// Are things on the free lists black or white? How does the sweep phase work? + // Concurrent sweep. // The sweep phase proceeds concurrently with normal program execution. // The heap is swept span-by-span both lazily (when a goroutine needs another span) @@ -50,6 +101,14 @@ // The finalizer goroutine is kicked off only when all spans are swept. // When the next GC starts, it sweeps all not-yet-swept spans (if any). +// GC rate. +// Next GC is after we've allocated an extra amount of memory proportional to +// the amount already in use. The proportion is controlled by GOGC environment variable +// (100 by default). If GOGC=100 and we're using 4M, we'll GC again when we get to 8M +// (this mark is tracked in next_gc variable). This keeps the GC cost in linear +// proportion to the allocation cost. Adjusting GOGC just changes the linear constant +// (and also the amount of extra memory used). + #include "runtime.h" #include "arch_GOARCH.h" #include "malloc.h" @@ -141,6 +200,8 @@ static void scanblock(byte*, uintptr, byte*); static byte* objectstart(byte*, Markbits*); static Workbuf* greyobject(byte*, Markbits*, Workbuf*); static bool inheap(byte*); +static bool shaded(byte*); +static void shade(byte*); static void slottombits(byte*, Markbits*); void runtime·bgsweep(void); @@ -633,13 +694,12 @@ runtime·gcworkbuffree(Workbuf *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 +// 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. @@ -823,6 +883,59 @@ scanstack(G *gp) runtime·tracebackdefers(gp, &fn, nil); } +// If the slot is grey or black return true, if white return false. +// If the slot is not in the known heap and thus does not have a valid GC bitmap then +// it is considered grey. Globals and stacks can hold such slots. +// The slot is grey if its mark bit is set and it is enqueued to be scanned. +// The slot is black if it has already been scanned. +// It is white if it has a valid mark bit and the bit is not set. +static bool +shaded(byte *slot) +{ + Markbits mbits; + + if(!inheap(slot)) // non-heap slots considered grey + return true; + + objectstart(slot, &mbits); + return (mbits.bits&bitMarked) != 0; +} + +// Shade the object if it isn't already. +// The object is not nil and known to be in the heap. +static void +shade(byte *b) +{ + byte *obj; + Workbuf *wbuf; + Markbits mbits; + + if(!inheap(b)) + runtime·throw("shade: passed an address not in the heap"); + + wbuf = getpartial(); + // Mark the object, return some important bits. + // If we combine the following two rotines we don't have to pass mbits or obj around. + obj = objectstart(b, &mbits); + wbuf = greyobject(obj, &mbits, wbuf); // augments the wbuf + putpartial(wbuf); + return; +} + +// This is the Dijkstra barrier coarsened to shade grey to white whereas +// the original Dijkstra barrier only shaded black to white. +// +// Shade indicates that it has seen a white pointer by adding the referent +// to wbuf. +void +runtime·markwb(void **slot, void *ptr) +{ + // initial nil check avoids some needlesss loads + if(ptr != nil && inheap(ptr) && shaded((void*)slot)) + shade(ptr); + *slot = ptr; +} + // The gp has been moved to a gc safepoint. If there is gcphase specific // work it is done here. void -- cgit v1.2.1 From 978c971bacf92ee97b8e24ce45b485afa1c31fad Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Thu, 23 Oct 2014 15:51:17 -0400 Subject: [dev.garbage] runtime: simplifiy lfstack.c due to undiagnosed buffer corruption. The changes got rid of the problems we were seeing. We suspect the pushcnt field has a race. LGTM=rsc R=dvyukov, rsc CC=golang-codereviews https://codereview.appspot.com/159330043 Committer: Russ Cox --- src/runtime/lfstack.c | 14 ++++++-------- src/runtime/runtime.h | 2 +- 2 files changed, 7 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/runtime/lfstack.c b/src/runtime/lfstack.c index 57e0af282..0ced839c2 100644 --- a/src/runtime/lfstack.c +++ b/src/runtime/lfstack.c @@ -46,7 +46,7 @@ runtime·lfstackpush(uint64 *head, LFNode *node) new = (uint64)(uintptr)node|(((uint64)node->pushcnt&CNT_MASK)<next = (LFNode*)(uintptr)(old&PTR_MASK); + node->next = old; if(runtime·cas64(head, old, new)) break; } @@ -55,19 +55,17 @@ runtime·lfstackpush(uint64 *head, LFNode *node) LFNode* runtime·lfstackpop(uint64 *head) { - LFNode *node, *node2; - uint64 old, new; + LFNode *node; + uint64 old, next; for(;;) { old = runtime·atomicload64(head); if(old == 0) return nil; node = (LFNode*)(uintptr)(old&PTR_MASK); - node2 = runtime·atomicloadp(&node->next); - new = 0; - if(node2 != nil) - new = (uint64)(uintptr)node2|(((uint64)node2->pushcnt&CNT_MASK)<next); + + if(runtime·cas64(head, old, next)) return node; } } diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index bea773799..37929c59c 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -573,7 +573,7 @@ enum { // Lock-free stack node. struct LFNode { - LFNode *next; + uint64 next; uintptr pushcnt; }; -- cgit v1.2.1 From 2c987a9ddefd9d256bf9e7e21396e2485a7d6514 Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Fri, 24 Oct 2014 11:07:16 -0400 Subject: [dev.garbage] runtime: Concurrent scan code Routines and logic to preform a concurrent stack scan of go-routines. This CL excersizes most of the functionality needed. The major exception being that it does not scan running goroutines. After doing the scans it relies on a STW to finish the GC, including rescanning the stacks. It is intended to achieve correctness, performance will follow. LGTM=rsc R=golang-codereviews, rsc CC=dvyukov, golang-codereviews https://codereview.appspot.com/156580043 --- src/runtime/malloc.go | 8 ++ src/runtime/malloc.h | 5 - src/runtime/mcache.c | 2 +- src/runtime/mgc0.c | 308 ++++++++++++++++++++++++++++++++++---------------- src/runtime/proc.c | 19 ++-- src/runtime/runtime.h | 2 + src/runtime/stack.c | 35 +++--- src/runtime/stubs.go | 2 + 8 files changed, 254 insertions(+), 127 deletions(-) (limited to 'src') diff --git a/src/runtime/malloc.go b/src/runtime/malloc.go index 9b4264f2b..c56e03886 100644 --- a/src/runtime/malloc.go +++ b/src/runtime/malloc.go @@ -438,7 +438,15 @@ func gogc(force int32) { mp = acquirem() mp.gcing = 1 releasem(mp) + onM(stoptheworld) + onM(finishsweep_m) // finish sweep before we start concurrent scan. + onM(starttheworld) + + // Do a concurrent heap scan before we stop the world. + onM(gcscan_m) + onM(stoptheworld) + if mp != acquirem() { gothrow("gogc: rescheduled") } diff --git a/src/runtime/malloc.h b/src/runtime/malloc.h index edcd0be77..e606b0c7a 100644 --- a/src/runtime/malloc.h +++ b/src/runtime/malloc.h @@ -343,11 +343,6 @@ struct MCache StackFreeList stackcache[NumStackOrders]; SudoG* sudogcache; - // 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 diff --git a/src/runtime/mcache.c b/src/runtime/mcache.c index 5fdbe3266..95ddced3e 100644 --- a/src/runtime/mcache.c +++ b/src/runtime/mcache.c @@ -39,12 +39,12 @@ runtime·allocmcache(void) return c; } +// mheap.lock needs to be held to release the gcworkbuf. static void freemcache(MCache *c) { runtime·MCache_ReleaseAll(c); runtime·stackcache_clear(c); - runtime·gcworkbuffree(c->gcworkbuf); runtime·lock(&runtime·mheap.lock); runtime·purgecachedstats(c); runtime·FixAlloc_Free(&runtime·mheap.cachealloc, c); diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index 8620f47af..c385d51cf 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -52,7 +52,7 @@ // see discussion of GC rate below. // Changing phases. -// Phases are changed by setting the gcphase to the next phase and call ackgcphase. +// Phases are changed by setting the gcphase to the next phase and possibly calling ackgcphase. // All phase action must be benign in the presence of a change. // Starting with GCoff // GCoff to GCscan @@ -137,7 +137,7 @@ enum { // ptrmask for an allocation containing a single pointer. static byte oneptr[] = {BitsPointer}; -// Initialized from $GOGC. GOGC=off means no gc. +// Initialized from $GOGC. GOGC=off means no GC. extern int32 runtime·gcpercent; // Holding worldsema grants an M the right to try to stop the world. @@ -185,11 +185,12 @@ BitVector runtime·gcbssmask; Mutex runtime·gclock; -static Workbuf* getpartial(void); +static Workbuf* getpartialorempty(void); static void putpartial(Workbuf*); static Workbuf* getempty(Workbuf*); static Workbuf* getfull(Workbuf*); static void putempty(Workbuf*); +static void putfull(Workbuf*); static Workbuf* handoff(Workbuf*); static void gchelperstart(void); static void flushallmcaches(void); @@ -205,12 +206,14 @@ static void shade(byte*); static void slottombits(byte*, Markbits*); void runtime·bgsweep(void); +void runtime·finishsweep_m(void); static FuncVal bgsweepv = {runtime·bgsweep}; typedef struct WorkData WorkData; struct WorkData { - uint64 full; // lock-free list of full blocks - uint64 empty; // lock-free list of empty blocks + uint64 full; // lock-free list of full blocks + uint64 empty; // lock-free list of empty blocks + uint64 partial; // lock-free list of partially filled blocks byte pad0[CacheLineSize]; // prevents false-sharing between full/empty and nproc/nwait uint32 nproc; int64 tstart; @@ -455,15 +458,22 @@ scanblock(byte *b, uintptr n, byte *ptrmask) Workbuf *wbuf; bool keepworking; - wbuf = getpartial(); + wbuf = getpartialorempty(); if(b != nil) { wbuf = scanobject(b, n, ptrmask, wbuf); if(runtime·gcphase == GCscan) { + if(inheap(b) && !ptrmask) + // b is in heap, we are in GCscan so there should be a ptrmask. + runtime·throw("scanblock: In GCscan phase and inheap is true."); + // GCscan only goes one level deep since mark wb not turned on. putpartial(wbuf); return; } } - + if(runtime·gcphase == GCscan) { + runtime·throw("scanblock: In GCscan phase but no b passed in."); + } + keepworking = b == nil; // ptrmask can have 2 possible values: @@ -479,6 +489,11 @@ scanblock(byte *b, uintptr n, byte *ptrmask) wbuf = getfull(wbuf); if(wbuf == nil) // nil means out of work barrier reached return; + + if(wbuf->nobj<=0) { + runtime·throw("runtime:scanblock getfull returns empty buffer"); + } + } // If another proc wants a pointer, give it some. @@ -506,7 +521,7 @@ markroot(ParFor *desc, uint32 i) void *p; uint32 status; bool restart; - + USED(&desc); // Note: if you add a case here, please also update heapdump.c:dumproots. switch(i) { @@ -553,7 +568,8 @@ markroot(ParFor *desc, uint32 i) break; case RootFlushCaches: - flushallmcaches(); + if (runtime·gcphase != GCscan) // Do not flush mcaches during GCscan phase. + flushallmcaches(); break; default: @@ -566,9 +582,10 @@ markroot(ParFor *desc, uint32 i) status = runtime·readgstatus(gp); // We are not in a scan state if((status == Gwaiting || status == Gsyscall) && gp->waitsince == 0) gp->waitsince = runtime·work.tstart; - // Shrink a stack if not much of it is being used. - runtime·shrinkstack(gp); - if(runtime·readgstatus(gp) == Gdead) + // Shrink a stack if not much of it is being used but not in the scan phase. + if (runtime·gcphase != GCscan) // Do not shrink during GCscan phase. + runtime·shrinkstack(gp); + if(runtime·readgstatus(gp) == Gdead) gp->gcworkdone = true; else gp->gcworkdone = false; @@ -576,121 +593,120 @@ markroot(ParFor *desc, uint32 i) // goroutine will scan its own stack when it stops running. // Wait until it has. - while((status = runtime·readgstatus(gp)) == Grunning && !gp->gcworkdone) { + while(runtime·readgstatus(gp) == Grunning && !gp->gcworkdone) { + } + + // scanstack(gp) is 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. + while(!gp->gcworkdone){ + status = runtime·readgstatus(gp); 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 + if(status == Gwaiting || status == Grunnable) + restart = runtime·stopg(gp); } - - // 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; } } +// wblock is used for creating new empty work buffer blocks. +static Mutex wblock; + // Get an empty work buffer off the work.empty list, // allocating new buffers as needed. static Workbuf* getempty(Workbuf *b) { - MCache *c; - - if(b != nil) - runtime·lfstackpush(&runtime·work.full, &b->node); - b = nil; - c = g->m->mcache; - if(c->gcworkbuf != nil) { - b = c->gcworkbuf; - c->gcworkbuf = nil; + if(b != nil) { + putfull(b); + b = nil; } - if(b == nil) + if(runtime·work.empty) b = (Workbuf*)runtime·lfstackpop(&runtime·work.empty); + + if(b && b->nobj != 0) { + runtime·printf("m%d: getempty: popped b=%p with non-zero b->nobj=%D\n", g->m->id, b, b->nobj); + runtime·throw("getempty: workbuffer not empty, b->nobj not 0"); + } if(b == nil) { + runtime·lock(&wblock); b = runtime·persistentalloc(sizeof(*b), CacheLineSize, &mstats.gc_sys); b->nobj = 0; + runtime·unlock(&wblock); } - if(b->nobj != 0) - runtime·throw("getempty: b->nobj not 0/n"); - b->nobj = 0; return b; } static void 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; - return; + if(b->nobj != 0) { + runtime·throw("putempty: b->nobj not 0\n"); } runtime·lfstackpush(&runtime·work.empty, &b->node); } -// Get an partially empty work buffer from the mcache structure -// and if non is available get an empty one. +// Put a full or partially full workbuf on the full list. +static void +putfull(Workbuf *b) +{ + if(b->nobj <= 0) { + runtime·throw("putfull: b->nobj <= 0\n"); + } + runtime·lfstackpush(&runtime·work.full, &b->node); +} + +// Get an partially empty work buffer +// if none are available get an empty one. static Workbuf* -getpartial(void) +getpartialorempty(void) { - MCache *c; Workbuf *b; - c = g->m->mcache; - if(c->gcworkbuf != nil) { - b = c->gcworkbuf; - c->gcworkbuf = nil; - } else { + b = (Workbuf*)runtime·lfstackpop(&runtime·work.partial); + if(b == nil) b = getempty(nil); - } return b; } static void putpartial(Workbuf *b) { - MCache *c; - c = g->m->mcache; - if(c->gcworkbuf == nil) { - c->gcworkbuf = b; - return; + if(b->nobj == 0) + runtime·lfstackpush(&runtime·work.empty, &b->node); + else if (b->nobj < nelem(b->obj)) + runtime·lfstackpush(&runtime·work.partial, &b->node); + else if (b->nobj == nelem(b->obj)) + runtime·lfstackpush(&runtime·work.full, &b->node); + else { + runtime·printf("b=%p, b->nobj=%D, nelem(b->obj)=%d\n", b, b->nobj, nelem(b->obj)); + runtime·throw("putpartial: bad Workbuf b->nobj"); } - - runtime·throw("putpartial: c->gcworkbuf is not nil\n"); - - runtime·lfstackpush(&runtime·work.full, &b->node); } void runtime·gcworkbuffree(Workbuf *b) { - if(b != nil) { - if(b->nobj != 0) - runtime·throw("gcworkbufferfree: b->nobj not 0\n"); + if(b == nil) + return; + if(b->nobj == 0) putempty(b); - } + else + putfull(b); } -// Get a full work buffer off the work.full list, or return nil. +// Get a full work buffer off the work.full or a partially +// filled one off the work.partial list. If nothing is available +// wait until all the other gc helpers have finished and then +// 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. @@ -704,12 +720,12 @@ getfull(Workbuf *b) { int32 i; - if(b != nil) { - if(b->nobj != 0) - runtime·printf("runtime:getfull: b->nobj=%D not 0.", b->nobj); - runtime·lfstackpush(&runtime·work.empty, &b->node); - } + if(b != nil) + putempty(b); + b = (Workbuf*)runtime·lfstackpop(&runtime·work.full); + if(b==nil) + b = (Workbuf*)runtime·lfstackpop(&runtime·work.partial); if(b != nil || runtime·work.nproc == 1) return b; @@ -718,7 +734,9 @@ getfull(Workbuf *b) if(runtime·work.full != 0) { runtime·xadd(&runtime·work.nwait, -1); b = (Workbuf*)runtime·lfstackpop(&runtime·work.full); - if(b != nil) + if(b==nil) + b = (Workbuf*)runtime·lfstackpop(&runtime·work.partial); + if(b != nil) return b; runtime·xadd(&runtime·work.nwait, +1); } @@ -861,8 +879,7 @@ scanstack(G *gp) case Gdead: return; case Grunning: - runtime·printf("runtime: gp=%p, goid=%D, gp->atomicstatus=%d\n", gp, gp->goid, runtime·readgstatus(gp)); - runtime·throw("mark - world not stopped"); + runtime·throw("scanstack: - goroutine not stopped"); case Grunnable: case Gsyscall: case Gwaiting: @@ -909,7 +926,7 @@ shade(byte *b) if(!inheap(b)) runtime·throw("shade: passed an address not in the heap"); - wbuf = getpartial(); + wbuf = getpartialorempty(); // Mark the object, return some important bits. // If we combine the following two rotines we don't have to pass mbits or obj around. obj = objectstart(b, &mbits); @@ -932,8 +949,8 @@ runtime·markwb(void **slot, void *ptr) *slot = ptr; } -// The gp has been moved to a gc safepoint. If there is gcphase specific -// work it is done here. +// The gp has been moved to a GC safepoint. GC phase specific +// work is done here. void runtime·gcphasework(G *gp) { @@ -953,14 +970,8 @@ runtime·gcphasework(G *gp) break; case GCmark: case GCmarktermination: - // - // Disabled until concurrent GC is implemented - // but indicate the scan has been done. scanstack(gp); - // scanstack will call shade which will populate - // the Workbuf. - // emptywbuf(gp) will empty it before returning - // + // All available mark work will be emptied before returning. break; } gp->gcworkdone = true; @@ -1050,6 +1061,7 @@ runtime·iterate_finq(void (*callback)(FuncVal*, byte*, uintptr, Type*, PtrType* } } +// Returns only when span s has been swept. void runtime·MSpan_EnsureSwept(MSpan *s) { @@ -1064,6 +1076,7 @@ runtime·MSpan_EnsureSwept(MSpan *s) sg = runtime·mheap.sweepgen; if(runtime·atomicload(&s->sweepgen) == sg) return; + // The caller must be sure that the span is a MSpanInUse span. if(runtime·cas(&s->sweepgen, sg-2, sg-1)) { runtime·MSpan_Sweep(s, false); return; @@ -1347,7 +1360,7 @@ runtime·gchelper(void) g->m->traceback = 2; gchelperstart(); - // parallel mark for over gc roots + // parallel mark for over GC roots runtime·parfordo(runtime·work.markfor); if(runtime·gcphase != GCscan) scanblock(nil, 0, nil); // blocks in getfull @@ -1531,10 +1544,93 @@ runtime·gc_m(void) a.start_time = (uint64)(g->m->scalararg[0]) | ((uint64)(g->m->scalararg[1]) << 32); a.eagersweep = g->m->scalararg[2]; gc(&a); - runtime·casgstatus(gp, Gwaiting, Grunning); } +void +runtime·finishsweep_m(void) +{ + uint32 i, sg; + MSpan *s; + + // The world is stopped so we should be able to complete the sweeps + // quickly. + while(runtime·sweepone() != -1) + runtime·sweep.npausesweep++; + + // There may be some other spans being swept concurrently that + // we need to wait for. If finishsweep_m is done with the world stopped + // this code is not required. + sg = runtime·mheap.sweepgen; + for(i=0; isweepgen == sg) { + continue; + } + if(s->state != MSpanInUse) // Span is not part of the GCed heap so no need to ensure it is swept. + continue; + runtime·MSpan_EnsureSwept(s); + } +} + +// Scan all of the stacks, greying (or graying if in America) the referents +// but not blackening them since the mark write barrier isn't installed. +void +runtime·gcscan_m(void) +{ + uint32 i, allglen, oldphase; + G *gp, *mastergp, **allg; + + // Grab the g that called us and potentially allow rescheduling. + // This allows it to be scanned like other goroutines. + mastergp = g->m->curg; + + runtime·casgstatus(mastergp, Grunning, Gwaiting); + mastergp->waitreason = runtime·gostringnocopy((byte*)"garbage collection scan"); + + // Span sweeping has been done by finishsweep_m. + // Long term we will want to make this goroutine runnable + // by placing it onto a scanenqueue state and then calling + // runtime·restartg(mastergp) to make it Grunnable. + // At the bottom we will want to return this p back to the scheduler. + + oldphase = runtime·gcphase; + + runtime·lock(&runtime·allglock); + allglen = runtime·allglen; + allg = runtime·allg; + // Prepare flag indicating that the scan has not been completed. + for(i = 0; i < allglen; i++) { + gp = allg[i]; + gp->gcworkdone = false; // set to true in gcphasework + } + runtime·unlock(&runtime·allglock); + + runtime·work.nwait = 0; + runtime·work.ndone = 0; + runtime·work.nproc = 1; // For now do not do this in parallel. + runtime·gcphase = GCscan; + // ackgcphase is not needed since we are not scanning running goroutines. + runtime·parforsetup(runtime·work.markfor, runtime·work.nproc, RootCount + allglen, nil, false, markroot); + runtime·parfordo(runtime·work.markfor); + + runtime·lock(&runtime·allglock); + + allg = runtime·allg; + // Check that gc work is done. + for(i = 0; i < allglen; i++) { + gp = allg[i]; + if(!gp->gcworkdone) { + runtime·throw("scan missed a g"); + } + } + runtime·unlock(&runtime·allglock); + + runtime·gcphase = oldphase; + runtime·casgstatus(mastergp, Gwaiting, Grunning); + // Let the g that called us continue to run. +} + static void gc(struct gc_args *args) { @@ -1542,7 +1638,9 @@ gc(struct gc_args *args) uint64 heap0, heap1, obj; GCStats stats; uint32 oldphase; - + uint32 i; + G *gp; + if(runtime·debug.allocfreetrace) runtime·tracegc(); @@ -1554,9 +1652,7 @@ gc(struct gc_args *args) if(runtime·debug.gctrace) t1 = runtime·nanotime(); - // Sweep what is not sweeped by bgsweep. - while(runtime·sweepone() != -1) - runtime·sweep.npausesweep++; + runtime·finishsweep_m(); // Cache runtime·mheap.allspans in work.spans to avoid conflicts with // resizing/freeing allspans. @@ -1580,7 +1676,13 @@ gc(struct gc_args *args) runtime·work.nwait = 0; runtime·work.ndone = 0; runtime·work.nproc = runtime·gcprocs(); - runtime·gcphase = GCmark; //^^ vv + runtime·gcphase = GCmark; + + // World is stopped so allglen will not change. + for(i = 0; i < runtime·allglen; i++) { + gp = runtime·allg[i]; + gp->gcworkdone = false; // set to true in gcphasework + } runtime·parforsetup(runtime·work.markfor, runtime·work.nproc, RootCount + runtime·allglen, nil, false, markroot); if(runtime·work.nproc > 1) { @@ -1596,7 +1698,13 @@ gc(struct gc_args *args) runtime·parfordo(runtime·work.markfor); scanblock(nil, 0, nil); - runtime·gcphase = oldphase; //^^ vv + + if(runtime·work.full) + runtime·throw("runtime·work.full != nil"); + if(runtime·work.partial) + runtime·throw("runtime·work.partial != nil"); + + runtime·gcphase = oldphase; t3 = 0; if(runtime·debug.gctrace) t3 = runtime·nanotime(); @@ -1735,7 +1843,7 @@ readgcstats_m(void) if(pauses->cap < nelem(mstats.pause_ns)+3) runtime·throw("runtime: short slice passed to readGCStats"); - // Pass back: pauses, last gc (absolute time), number of gc, total pause ns. + // Pass back: pauses, last GC (absolute time), number of GC, total pause ns. p = (uint64*)pauses->array; runtime·lock(&runtime·mheap.lock); n = mstats.numgc; diff --git a/src/runtime/proc.c b/src/runtime/proc.c index 9643abcc6..b824f574d 100644 --- a/src/runtime/proc.c +++ b/src/runtime/proc.c @@ -423,13 +423,7 @@ runtime·casgstatus(G *gp, uint32 oldval, uint32 newval) // loop if gp->atomicstatus is in a scan state giving // GC time to finish and change the state to oldval. while(!runtime·cas(&gp->atomicstatus, oldval, newval)) { - // Help GC if needed. - if(gp->preemptscan && !gp->gcworkdone && (oldval == Grunning || oldval == Gsyscall)) { - gp->preemptscan = false; - g->m->ptrarg[0] = gp; - fn = helpcasgstatus; - runtime·onM(&fn); - } + } } @@ -504,6 +498,13 @@ runtime·stopg(G *gp) return false; case Grunning: + if(runtime·gcphase == GCscan) { + gp->gcworkdone = true; + return false; + // Running routines not scanned during + // GCscan phase, we only scan non-running routines. + } + // Claim goroutine, so we aren't racing with a status // transition away from Grunning. if(!runtime·castogscanstatus(gp, Grunning, Gscanrunning)) @@ -1918,6 +1919,7 @@ exitsyscallfast(void) // Freezetheworld sets stopwait but does not retake P's. if(runtime·sched.stopwait) { + g->m->mcache = nil; g->m->p = nil; return false; } @@ -1930,6 +1932,7 @@ exitsyscallfast(void) return true; } // Try to get any other idle P. + g->m->mcache = nil; g->m->p = nil; if(runtime·sched.pidle) { fn = exitsyscallfast_pidle; @@ -2617,6 +2620,8 @@ runtime·setcpuprofilerate_m(void) P *runtime·newP(void); // Change number of processors. The world is stopped, sched is locked. +// gcworkbufs are not being modified by either the GC or +// the write barrier code. static void procresize(int32 new) { diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index 37929c59c..cbbf6b3fc 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -649,6 +649,7 @@ struct ForceGCState }; extern uint32 runtime·gcphase; +extern Mutex runtime·allglock; /* * defined macros @@ -677,6 +678,7 @@ enum { uint32 runtime·readgstatus(G*); void runtime·casgstatus(G*, uint32, uint32); +bool runtime·castogscanstatus(G*, uint32, uint32); void runtime·quiesce(G*); bool runtime·stopg(G*); void runtime·restartg(G*); diff --git a/src/runtime/stack.c b/src/runtime/stack.c index e402691f4..e06e48a93 100644 --- a/src/runtime/stack.c +++ b/src/runtime/stack.c @@ -587,13 +587,13 @@ adjustsudogs(G *gp, AdjustInfo *adjinfo) } // Copies gp's stack to a new stack of a different size. +// Caller must have changed gp status to Gcopystack. static void copystack(G *gp, uintptr newsize) { Stack old, new; uintptr used; AdjustInfo adjinfo; - uint32 oldstatus; bool (*cb)(Stkframe*, void*); byte *p, *ep; @@ -637,20 +637,11 @@ copystack(G *gp, uintptr newsize) } runtime·memmove((byte*)new.hi - used, (byte*)old.hi - used, used); - oldstatus = runtime·readgstatus(gp); - oldstatus &= ~Gscan; - if(oldstatus == Gwaiting || oldstatus == Grunnable) - runtime·casgstatus(gp, oldstatus, Gcopystack); // oldstatus is Gwaiting or Grunnable - else - runtime·throw("copystack: bad status, not Gwaiting or Grunnable"); - // Swap out old stack for new one gp->stack = new; gp->stackguard0 = new.lo + StackGuard; // NOTE: might clobber a preempt request gp->sched.sp = new.hi - used; - runtime·casgstatus(gp, Gcopystack, oldstatus); // oldstatus is Gwaiting or Grunnable - // free old stack if(StackPoisonCopy) { p = (byte*)old.lo; @@ -700,6 +691,7 @@ void runtime·newstack(void) { int32 oldsize, newsize; + uint32 oldstatus; uintptr sp; G *gp; Gobuf morebuf; @@ -789,12 +781,15 @@ runtime·newstack(void) runtime·throw("stack overflow"); } - // Note that the concurrent GC might be scanning the stack as we try to replace it. - // copystack takes care of the appropriate coordination with the stack scanner. + oldstatus = runtime·readgstatus(gp); + oldstatus &= ~Gscan; + runtime·casgstatus(gp, oldstatus, Gcopystack); // oldstatus is Gwaiting or Grunnable + // The concurrent GC will not scan the stack while we are doing the copy since + // the gp is in a Gcopystack status. copystack(gp, newsize); if(StackDebug >= 1) runtime·printf("stack grow done\n"); - runtime·casgstatus(gp, Gwaiting, Grunning); + runtime·casgstatus(gp, Gcopystack, Grunning); runtime·gogo(&gp->sched); } @@ -825,6 +820,7 @@ void runtime·shrinkstack(G *gp) { uintptr used, oldsize, newsize; + uint32 oldstatus; if(runtime·readgstatus(gp) == Gdead) { if(gp->stack.lo != 0) { @@ -858,8 +854,19 @@ runtime·shrinkstack(G *gp) #endif if(StackDebug > 0) runtime·printf("shrinking stack %D->%D\n", (uint64)oldsize, (uint64)newsize); + // This is being done in a Gscan state and was initiated by the GC so no need to move to + // the Gcopystate. + // The world is stopped, so the goroutine must be Gwaiting or Grunnable, + // and what it is is not changing underfoot. + + oldstatus = runtime·readgstatus(gp); + oldstatus &= ~Gscan; + if(oldstatus != Gwaiting && oldstatus != Grunnable) + runtime·throw("status is not Gwaiting or Grunnable"); + runtime·casgstatus(gp, oldstatus, Gcopystack); copystack(gp, newsize); -} + runtime·casgstatus(gp, Gcopystack, oldstatus); + } // Do any delayed stack freeing that was queued up during GC. void diff --git a/src/runtime/stubs.go b/src/runtime/stubs.go index 6561094ff..32dfed7d3 100644 --- a/src/runtime/stubs.go +++ b/src/runtime/stubs.go @@ -106,6 +106,8 @@ func recovery_m(*g) func mcacheRefill_m() func largeAlloc_m() func gc_m() +func gcscan_m() +func finishsweep_m() func scavenge_m() func setFinalizer_m() func removeFinalizer_m() -- cgit v1.2.1 From 297ae6e1545a6982878a82114d5d2d40da373ca6 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Mon, 27 Oct 2014 15:57:07 -0400 Subject: [dev.garbage] runtime: fix TestLFStack on 386 LGTM=rlh R=rlh, dvyukov CC=golang-codereviews https://codereview.appspot.com/157430044 --- src/runtime/export_test.go | 2 +- src/runtime/lfstack_test.go | 2 +- src/runtime/runtime.h | 1 + 3 files changed, 3 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/runtime/export_test.go b/src/runtime/export_test.go index be352557f..65e918e84 100644 --- a/src/runtime/export_test.go +++ b/src/runtime/export_test.go @@ -26,7 +26,7 @@ var Exitsyscall = exitsyscall var LockedOSThread = lockedOSThread type LFNode struct { - Next *LFNode + Next uint64 Pushcnt uintptr } diff --git a/src/runtime/lfstack_test.go b/src/runtime/lfstack_test.go index e51877704..68f221d6e 100644 --- a/src/runtime/lfstack_test.go +++ b/src/runtime/lfstack_test.go @@ -121,7 +121,7 @@ func TestLFStackStress(t *testing.T) { } cnt++ sum2 += node.data - node.Next = nil + node.Next = 0 } } if cnt != K { diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index cbbf6b3fc..c1bba423a 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -571,6 +571,7 @@ enum { #endif // Lock-free stack node. +// Also known to export_test.go. struct LFNode { uint64 next; -- cgit v1.2.1 From 9232cbb6a6aaa8a4197b22819406128ff0f99265 Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Mon, 27 Oct 2014 17:07:53 -0400 Subject: [dev.garbage] runtime: Fix 386 compiler warnings. LGTM=rsc R=rsc CC=golang-codereviews https://codereview.appspot.com/163390043 --- src/runtime/mgc0.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index c385d51cf..cc1f81123 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -632,7 +632,7 @@ getempty(Workbuf *b) b = (Workbuf*)runtime·lfstackpop(&runtime·work.empty); if(b && b->nobj != 0) { - runtime·printf("m%d: getempty: popped b=%p with non-zero b->nobj=%D\n", g->m->id, b, b->nobj); + runtime·printf("m%d: getempty: popped b=%p with non-zero b->nobj=%d\n", g->m->id, b, (uint32)b->nobj); runtime·throw("getempty: workbuffer not empty, b->nobj not 0"); } if(b == nil) { @@ -687,7 +687,7 @@ putpartial(Workbuf *b) else if (b->nobj == nelem(b->obj)) runtime·lfstackpush(&runtime·work.full, &b->node); else { - runtime·printf("b=%p, b->nobj=%D, nelem(b->obj)=%d\n", b, b->nobj, nelem(b->obj)); + runtime·printf("b=%p, b->nobj=%d, nelem(b->obj)=%d\n", b, b->nobj, (uint32)nelem(b->obj)); runtime·throw("putpartial: bad Workbuf b->nobj"); } } -- cgit v1.2.1 From f65bb028c5ceb4fb213b103f24a85f17cf67ac39 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Thu, 30 Oct 2014 10:16:03 -0400 Subject: [dev.garbage] cmd/gc, runtime: implement write barriers in terms of writebarrierptr This CL implements the many multiword write barriers by calling writebarrierptr, so that only writebarrierptr needs the actual barrier. In lieu of an actual barrier, writebarrierptr checks that the value being copied is not a small non-zero integer. This is enough to shake out bugs where the barrier is being called when it should not (for non-pointer values). It also found a few tests in sync/atomic that were being too clever. This CL adds a write barrier for the memory moved during the builtin copy function, which I forgot when inserting barriers for Go 1.4. This CL re-enables some write barriers that were disabled for Go 1.4. Those were disabled because it is possible to change the generated code so that they are unnecessary most of the time, but we have not changed the generated code yet. For safety they must be enabled. None of this is terribly efficient. We are aiming for correct first. LGTM=rlh R=rlh CC=golang-codereviews https://codereview.appspot.com/168770043 --- src/cmd/api/goapi.go | 1 + src/cmd/gc/builtin.c | 29 ++++++- src/cmd/gc/runtime.go | 31 ++++++- src/cmd/gc/typecheck.c | 6 +- src/cmd/gc/walk.c | 46 +++++++--- src/run.bash | 3 +- src/runtime/malloc.go | 33 +++++++ src/runtime/mgc0.go | 104 +++++++++++++++++----- src/runtime/mgc0.h | 2 +- src/runtime/wbfat.go | 190 +++++++++++++++++++++++++++++++++++++++++ src/runtime/wbfat_gen.go | 41 +++++++++ src/sync/atomic/atomic_test.go | 8 +- 12 files changed, 447 insertions(+), 47 deletions(-) create mode 100644 src/runtime/wbfat.go create mode 100644 src/runtime/wbfat_gen.go (limited to 'src') diff --git a/src/cmd/api/goapi.go b/src/cmd/api/goapi.go index 5a8c87603..e49ba33bb 100644 --- a/src/cmd/api/goapi.go +++ b/src/cmd/api/goapi.go @@ -405,6 +405,7 @@ func (w *Walker) parseFile(dir, file string) (*ast.File, error) { " note struct{};" + " p struct{};" + " parfor struct{};" + + " slice struct{};" + " slicetype struct{};" + " stkframe struct{};" + " sudog struct{};" + diff --git a/src/cmd/gc/builtin.c b/src/cmd/gc/builtin.c index fbca4ee5f..bd3fca167 100644 --- a/src/cmd/gc/builtin.c +++ b/src/cmd/gc/builtin.c @@ -86,10 +86,33 @@ char *runtimeimport = "func @\"\".writebarrierstring (@\"\".dst·1 *any, @\"\".src·2 any)\n" "func @\"\".writebarrierslice (@\"\".dst·1 *any, @\"\".src·2 any)\n" "func @\"\".writebarrieriface (@\"\".dst·1 *any, @\"\".src·2 any)\n" - "func @\"\".writebarrierfat2 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" - "func @\"\".writebarrierfat3 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" - "func @\"\".writebarrierfat4 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat01 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat10 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat11 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat001 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat010 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat011 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat100 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat101 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat110 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat111 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat0001 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat0010 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat0011 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat0100 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat0101 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat0110 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat0111 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat1000 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat1001 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat1010 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat1011 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat1100 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat1101 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat1110 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat1111 (@\"\".dst·1 *any, _ *byte, @\"\".src·3 any)\n" "func @\"\".writebarrierfat (@\"\".typ·1 *byte, @\"\".dst·2 *any, @\"\".src·3 *any)\n" + "func @\"\".writebarriercopy (@\"\".typ·2 *byte, @\"\".dst·3 any, @\"\".src·4 any) (? int)\n" "func @\"\".selectnbsend (@\"\".chanType·2 *byte, @\"\".hchan·3 chan<- any, @\"\".elem·4 *any) (? bool)\n" "func @\"\".selectnbrecv (@\"\".chanType·2 *byte, @\"\".elem·3 *any, @\"\".hchan·4 <-chan any) (? bool)\n" "func @\"\".selectnbrecv2 (@\"\".chanType·2 *byte, @\"\".elem·3 *any, @\"\".received·4 *bool, @\"\".hchan·5 <-chan any) (? bool)\n" diff --git a/src/cmd/gc/runtime.go b/src/cmd/gc/runtime.go index 0fb15c265..38bf6abb6 100644 --- a/src/cmd/gc/runtime.go +++ b/src/cmd/gc/runtime.go @@ -115,10 +115,35 @@ func writebarrieriface(dst *any, src any) // The unused *byte argument makes sure that src is 2-pointer-aligned, // which is the maximum alignment on NaCl amd64p32 // (and possibly on 32-bit systems if we start 64-bit aligning uint64s). -func writebarrierfat2(dst *any, _ *byte, src any) -func writebarrierfat3(dst *any, _ *byte, src any) -func writebarrierfat4(dst *any, _ *byte, src any) +// The bitmap in the name tells which words being copied are pointers. +func writebarrierfat01(dst *any, _ *byte, src any) +func writebarrierfat10(dst *any, _ *byte, src any) +func writebarrierfat11(dst *any, _ *byte, src any) +func writebarrierfat001(dst *any, _ *byte, src any) +func writebarrierfat010(dst *any, _ *byte, src any) +func writebarrierfat011(dst *any, _ *byte, src any) +func writebarrierfat100(dst *any, _ *byte, src any) +func writebarrierfat101(dst *any, _ *byte, src any) +func writebarrierfat110(dst *any, _ *byte, src any) +func writebarrierfat111(dst *any, _ *byte, src any) +func writebarrierfat0001(dst *any, _ *byte, src any) +func writebarrierfat0010(dst *any, _ *byte, src any) +func writebarrierfat0011(dst *any, _ *byte, src any) +func writebarrierfat0100(dst *any, _ *byte, src any) +func writebarrierfat0101(dst *any, _ *byte, src any) +func writebarrierfat0110(dst *any, _ *byte, src any) +func writebarrierfat0111(dst *any, _ *byte, src any) +func writebarrierfat1000(dst *any, _ *byte, src any) +func writebarrierfat1001(dst *any, _ *byte, src any) +func writebarrierfat1010(dst *any, _ *byte, src any) +func writebarrierfat1011(dst *any, _ *byte, src any) +func writebarrierfat1100(dst *any, _ *byte, src any) +func writebarrierfat1101(dst *any, _ *byte, src any) +func writebarrierfat1110(dst *any, _ *byte, src any) +func writebarrierfat1111(dst *any, _ *byte, src any) + func writebarrierfat(typ *byte, dst *any, src *any) +func writebarriercopy(typ *byte, dst any, src any) int func selectnbsend(chanType *byte, hchan chan<- any, elem *any) bool func selectnbrecv(chanType *byte, elem *any, hchan <-chan any) bool diff --git a/src/cmd/gc/typecheck.c b/src/cmd/gc/typecheck.c index 714c66268..f05d8022d 100644 --- a/src/cmd/gc/typecheck.c +++ b/src/cmd/gc/typecheck.c @@ -2891,7 +2891,8 @@ typecheckas(Node *n) case OSLICE3: case OSLICESTR: // For x = x[0:y], x can be updated in place, without touching pointer. - if(samesafeexpr(n->left, n->right->left) && (n->right->right->left == N || iszero(n->right->right->left))) + // TODO(rsc): Reenable once it is actually updated in place without touching the pointer. + if(0 && samesafeexpr(n->left, n->right->left) && (n->right->right->left == N || iszero(n->right->right->left))) n->right->reslice = 1; break; @@ -2899,7 +2900,8 @@ typecheckas(Node *n) // For x = append(x, ...), x can be updated in place when there is capacity, // without touching the pointer; otherwise the emitted code to growslice // can take care of updating the pointer, and only in that case. - if(n->right->list != nil && samesafeexpr(n->left, n->right->list->n)) + // TODO(rsc): Reenable once the emitted code does update the pointer. + if(0 && n->right->list != nil && samesafeexpr(n->left, n->right->list->n)) n->right->reslice = 1; break; } diff --git a/src/cmd/gc/walk.c b/src/cmd/gc/walk.c index d4d0f449c..7b502eb60 100644 --- a/src/cmd/gc/walk.c +++ b/src/cmd/gc/walk.c @@ -6,6 +6,7 @@ #include #include "go.h" #include "../ld/textflag.h" +#include "../../runtime/mgc0.h" static Node* walkprint(Node*, NodeList**); static Node* writebarrierfn(char*, Type*, Type*); @@ -1988,14 +1989,15 @@ applywritebarrier(Node *n, NodeList **init) { Node *l, *r; Type *t; + vlong x; + static Bvec *bv; + char name[32]; if(n->left && n->right && needwritebarrier(n->left, n->right)) { t = n->left->type; l = nod(OADDR, n->left, N); l->etype = 1; // addr does not escape if(t->width == widthptr) { - n = mkcall1(writebarrierfn("writebarrierptr", t, n->right->type), T, init, - l, n->right); } else if(t->etype == TSTRING) { n = mkcall1(writebarrierfn("writebarrierstring", t, n->right->type), T, init, l, n->right); @@ -2005,14 +2007,33 @@ applywritebarrier(Node *n, NodeList **init) } else if(isinter(t)) { n = mkcall1(writebarrierfn("writebarrieriface", t, n->right->type), T, init, l, n->right); - } else if(t->width == 2*widthptr) { - n = mkcall1(writebarrierfn("writebarrierfat2", t, n->right->type), T, init, - l, nodnil(), n->right); - } else if(t->width == 3*widthptr) { - n = mkcall1(writebarrierfn("writebarrierfat3", t, n->right->type), T, init, - l, nodnil(), n->right); - } else if(t->width == 4*widthptr) { - n = mkcall1(writebarrierfn("writebarrierfat4", t, n->right->type), T, init, + } else if(t->width <= 4*widthptr) { + x = 0; + if(bv == nil) + bv = bvalloc(BitsPerPointer*4); + bvresetall(bv); + twobitwalktype1(t, &x, bv); + // The bvgets are looking for BitsPointer in successive slots. + enum { + PtrBit = 1, + }; + if(BitsPointer != (1<width/widthptr) { + case 2: + snprint(name, sizeof name, "writebarrierfat%d%d", + bvget(bv, PtrBit), bvget(bv, BitsPerPointer+PtrBit)); + break; + case 3: + snprint(name, sizeof name, "writebarrierfat%d%d%d", + bvget(bv, PtrBit), bvget(bv, BitsPerPointer+PtrBit), bvget(bv, 2*BitsPerPointer+PtrBit)); + break; + case 4: + snprint(name, sizeof name, "writebarrierfat%d%d%d%d", + bvget(bv, PtrBit), bvget(bv, BitsPerPointer+PtrBit), bvget(bv, 2*BitsPerPointer+PtrBit), bvget(bv, 3*BitsPerPointer+PtrBit)); + break; + } + n = mkcall1(writebarrierfn(name, t, n->right->type), T, init, l, nodnil(), n->right); } else { r = n->right; @@ -2874,6 +2895,11 @@ copyany(Node *n, NodeList **init, int runtimecall) { Node *nl, *nr, *nfrm, *nto, *nif, *nlen, *nwid, *fn; NodeList *l; + + if(haspointers(n->left->type->type)) { + fn = writebarrierfn("writebarriercopy", n->left->type, n->right->type); + return mkcall1(fn, n->type, init, typename(n->left->type->type), n->left, n->right); + } if(runtimecall) { if(n->right->type->etype == TSTRING) diff --git a/src/run.bash b/src/run.bash index 3c9430c87..91f12a174 100755 --- a/src/run.bash +++ b/src/run.bash @@ -66,7 +66,8 @@ go test sync -short -timeout=$(expr 120 \* $timeout_scale)s -cpu=10 # Race detector only supported on Linux, FreeBSD and OS X, # and only on amd64, and only when cgo is enabled. -case "$GOHOSTOS-$GOOS-$GOARCH-$CGO_ENABLED" in +# DISABLED until we get garbage collection working. +case "$GOHOSTOS-$GOOS-$GOARCH-$CGO_ENABLED-XXX-DISABLED" in linux-linux-amd64-1 | freebsd-freebsd-amd64-1 | darwin-darwin-amd64-1) echo echo '# Testing race detector.' diff --git a/src/runtime/malloc.go b/src/runtime/malloc.go index 020f87a7a..56f4f7cd7 100644 --- a/src/runtime/malloc.go +++ b/src/runtime/malloc.go @@ -245,6 +245,8 @@ func mallocgc(size uintptr, typ *_type, flags int) unsafe.Pointer { masksize = masksize * pointersPerByte / 8 // 4 bits per word masksize++ // unroll flag in the beginning if masksize > maxGCMask && typ.gc[1] != 0 { + // write barriers have not been updated to deal with this case yet. + gothrow("maxGCMask too small for now") // If the mask is too large, unroll the program directly // into the GC bitmap. It's 7 times slower than copying // from the pre-unrolled mask, but saves 1/16 of type size @@ -344,6 +346,37 @@ marked: return x } +func loadPtrMask(typ *_type) []uint8 { + var ptrmask *uint8 + nptr := (uintptr(typ.size) + ptrSize - 1) / ptrSize + if typ.kind&kindGCProg != 0 { + masksize := nptr + if masksize%2 != 0 { + masksize *= 2 // repeated + } + masksize = masksize * pointersPerByte / 8 // 4 bits per word + masksize++ // unroll flag in the beginning + if masksize > maxGCMask && typ.gc[1] != 0 { + // write barriers have not been updated to deal with this case yet. + gothrow("maxGCMask too small for now") + } + ptrmask = (*uint8)(unsafe.Pointer(uintptr(typ.gc[0]))) + // Check whether the program is already unrolled + // by checking if the unroll flag byte is set + maskword := uintptr(atomicloadp(unsafe.Pointer(ptrmask))) + if *(*uint8)(unsafe.Pointer(&maskword)) == 0 { + mp := acquirem() + mp.ptrarg[0] = unsafe.Pointer(typ) + onM(unrollgcprog_m) + releasem(mp) + } + ptrmask = (*uint8)(add(unsafe.Pointer(ptrmask), 1)) // skip the unroll flag byte + } else { + ptrmask = (*uint8)(unsafe.Pointer(typ.gc[0])) // pointer to unrolled mask + } + return (*[1 << 30]byte)(unsafe.Pointer(ptrmask))[:(nptr+1)/2] +} + // implementation of new builtin func newobject(typ *_type) unsafe.Pointer { flags := 0 diff --git a/src/runtime/mgc0.go b/src/runtime/mgc0.go index 3a7204b54..75678c522 100644 --- a/src/runtime/mgc0.go +++ b/src/runtime/mgc0.go @@ -83,54 +83,112 @@ func bgsweep() { } } +const ( + _PoisonGC = 0xf969696969696969 & ^uintptr(0) + _PoisonStack = 0x6868686868686868 & ^uintptr(0) +) + // NOTE: Really dst *unsafe.Pointer, src unsafe.Pointer, // but if we do that, Go inserts a write barrier on *dst = src. //go:nosplit func writebarrierptr(dst *uintptr, src uintptr) { + if src != 0 && (src < _PageSize || src == _PoisonGC || src == _PoisonStack) { + onM(func() { gothrow("bad pointer in write barrier") }) + } *dst = src } //go:nosplit func writebarrierstring(dst *[2]uintptr, src [2]uintptr) { - dst[0] = src[0] + writebarrierptr(&dst[0], src[0]) dst[1] = src[1] } //go:nosplit func writebarrierslice(dst *[3]uintptr, src [3]uintptr) { - dst[0] = src[0] + writebarrierptr(&dst[0], src[0]) dst[1] = src[1] dst[2] = src[2] } //go:nosplit func writebarrieriface(dst *[2]uintptr, src [2]uintptr) { - dst[0] = src[0] - dst[1] = src[1] + writebarrierptr(&dst[0], src[0]) + writebarrierptr(&dst[1], src[1]) } -//go:nosplit -func writebarrierfat2(dst *[2]uintptr, _ *byte, src [2]uintptr) { - dst[0] = src[0] - dst[1] = src[1] -} +//go:generate go run wbfat_gen.go -- wbfat.go +// +// The above line generates multiword write barriers for +// all the combinations of ptr+scalar up to four words. +// The implementations are written to wbfat.go. //go:nosplit -func writebarrierfat3(dst *[3]uintptr, _ *byte, src [3]uintptr) { - dst[0] = src[0] - dst[1] = src[1] - dst[2] = src[2] -} - -//go:nosplit -func writebarrierfat4(dst *[4]uintptr, _ *byte, src [4]uintptr) { - dst[0] = src[0] - dst[1] = src[1] - dst[2] = src[2] - dst[3] = src[3] +func writebarrierfat(typ *_type, dst, src unsafe.Pointer) { + mask := loadPtrMask(typ) + nptr := typ.size / ptrSize + for i := uintptr(0); i < nptr; i += 2 { + bits := mask[i/2] + if (bits>>2)&_BitsMask == _BitsPointer { + writebarrierptr((*uintptr)(dst), *(*uintptr)(src)) + } else { + *(*uintptr)(dst) = *(*uintptr)(src) + } + dst = add(dst, ptrSize) + src = add(src, ptrSize) + if i+1 == nptr { + break + } + bits >>= 4 + if (bits>>2)&_BitsMask == _BitsPointer { + writebarrierptr((*uintptr)(dst), *(*uintptr)(src)) + } else { + *(*uintptr)(dst) = *(*uintptr)(src) + } + dst = add(dst, ptrSize) + src = add(src, ptrSize) + } } //go:nosplit -func writebarrierfat(typ *_type, dst, src unsafe.Pointer) { - memmove(dst, src, typ.size) +func writebarriercopy(typ *_type, dst, src slice) int { + n := dst.len + if n > src.len { + n = src.len + } + if n == 0 { + return 0 + } + dstp := unsafe.Pointer(dst.array) + srcp := unsafe.Pointer(src.array) + + if uintptr(srcp) < uintptr(dstp) && uintptr(srcp)+uintptr(n)*typ.size > uintptr(dstp) { + // Overlap with src before dst. + // Copy backward, being careful not to move dstp/srcp + // out of the array they point into. + dstp = add(dstp, uintptr(n-1)*typ.size) + srcp = add(srcp, uintptr(n-1)*typ.size) + i := uint(0) + for { + writebarrierfat(typ, dstp, srcp) + if i++; i >= n { + break + } + dstp = add(dstp, -typ.size) + srcp = add(srcp, -typ.size) + } + } else { + // Copy forward, being careful not to move dstp/srcp + // out of the array they point into. + i := uint(0) + for { + writebarrierfat(typ, dstp, srcp) + if i++; i >= n { + break + } + dstp = add(dstp, typ.size) + srcp = add(srcp, typ.size) + } + } + return int(n) } diff --git a/src/runtime/mgc0.h b/src/runtime/mgc0.h index 64f818914..16fbe4665 100644 --- a/src/runtime/mgc0.h +++ b/src/runtime/mgc0.h @@ -56,7 +56,7 @@ enum { BitsEface = 3, // 64 bytes cover objects of size 1024/512 on 64/32 bits, respectively. - MaxGCMask = 64, + MaxGCMask = 65536, // TODO(rsc): change back to 64 }; // Bits in per-word bitmap. diff --git a/src/runtime/wbfat.go b/src/runtime/wbfat.go new file mode 100644 index 000000000..75c58b26b --- /dev/null +++ b/src/runtime/wbfat.go @@ -0,0 +1,190 @@ +// generated by wbfat_gen.go; use go generate + +package runtime + +//go:nosplit +func writebarrierfat01(dst *[2]uintptr, _ *byte, src [2]uintptr) { + dst[0] = src[0] + writebarrierptr(&dst[1], src[1]) +} + +//go:nosplit +func writebarrierfat10(dst *[2]uintptr, _ *byte, src [2]uintptr) { + writebarrierptr(&dst[0], src[0]) + dst[1] = src[1] +} + +//go:nosplit +func writebarrierfat11(dst *[2]uintptr, _ *byte, src [2]uintptr) { + writebarrierptr(&dst[0], src[0]) + writebarrierptr(&dst[1], src[1]) +} + +//go:nosplit +func writebarrierfat001(dst *[3]uintptr, _ *byte, src [3]uintptr) { + dst[0] = src[0] + dst[1] = src[1] + writebarrierptr(&dst[2], src[2]) +} + +//go:nosplit +func writebarrierfat010(dst *[3]uintptr, _ *byte, src [3]uintptr) { + dst[0] = src[0] + writebarrierptr(&dst[1], src[1]) + dst[2] = src[2] +} + +//go:nosplit +func writebarrierfat011(dst *[3]uintptr, _ *byte, src [3]uintptr) { + dst[0] = src[0] + writebarrierptr(&dst[1], src[1]) + writebarrierptr(&dst[2], src[2]) +} + +//go:nosplit +func writebarrierfat100(dst *[3]uintptr, _ *byte, src [3]uintptr) { + writebarrierptr(&dst[0], src[0]) + dst[1] = src[1] + dst[2] = src[2] +} + +//go:nosplit +func writebarrierfat101(dst *[3]uintptr, _ *byte, src [3]uintptr) { + writebarrierptr(&dst[0], src[0]) + dst[1] = src[1] + writebarrierptr(&dst[2], src[2]) +} + +//go:nosplit +func writebarrierfat110(dst *[3]uintptr, _ *byte, src [3]uintptr) { + writebarrierptr(&dst[0], src[0]) + writebarrierptr(&dst[1], src[1]) + dst[2] = src[2] +} + +//go:nosplit +func writebarrierfat111(dst *[3]uintptr, _ *byte, src [3]uintptr) { + writebarrierptr(&dst[0], src[0]) + writebarrierptr(&dst[1], src[1]) + writebarrierptr(&dst[2], src[2]) +} + +//go:nosplit +func writebarrierfat0001(dst *[4]uintptr, _ *byte, src [4]uintptr) { + dst[0] = src[0] + dst[1] = src[1] + dst[2] = src[2] + writebarrierptr(&dst[3], src[3]) +} + +//go:nosplit +func writebarrierfat0010(dst *[4]uintptr, _ *byte, src [4]uintptr) { + dst[0] = src[0] + dst[1] = src[1] + writebarrierptr(&dst[2], src[2]) + dst[3] = src[3] +} + +//go:nosplit +func writebarrierfat0011(dst *[4]uintptr, _ *byte, src [4]uintptr) { + dst[0] = src[0] + dst[1] = src[1] + writebarrierptr(&dst[2], src[2]) + writebarrierptr(&dst[3], src[3]) +} + +//go:nosplit +func writebarrierfat0100(dst *[4]uintptr, _ *byte, src [4]uintptr) { + dst[0] = src[0] + writebarrierptr(&dst[1], src[1]) + dst[2] = src[2] + dst[3] = src[3] +} + +//go:nosplit +func writebarrierfat0101(dst *[4]uintptr, _ *byte, src [4]uintptr) { + dst[0] = src[0] + writebarrierptr(&dst[1], src[1]) + dst[2] = src[2] + writebarrierptr(&dst[3], src[3]) +} + +//go:nosplit +func writebarrierfat0110(dst *[4]uintptr, _ *byte, src [4]uintptr) { + dst[0] = src[0] + writebarrierptr(&dst[1], src[1]) + writebarrierptr(&dst[2], src[2]) + dst[3] = src[3] +} + +//go:nosplit +func writebarrierfat0111(dst *[4]uintptr, _ *byte, src [4]uintptr) { + dst[0] = src[0] + writebarrierptr(&dst[1], src[1]) + writebarrierptr(&dst[2], src[2]) + writebarrierptr(&dst[3], src[3]) +} + +//go:nosplit +func writebarrierfat1000(dst *[4]uintptr, _ *byte, src [4]uintptr) { + writebarrierptr(&dst[0], src[0]) + dst[1] = src[1] + dst[2] = src[2] + dst[3] = src[3] +} + +//go:nosplit +func writebarrierfat1001(dst *[4]uintptr, _ *byte, src [4]uintptr) { + writebarrierptr(&dst[0], src[0]) + dst[1] = src[1] + dst[2] = src[2] + writebarrierptr(&dst[3], src[3]) +} + +//go:nosplit +func writebarrierfat1010(dst *[4]uintptr, _ *byte, src [4]uintptr) { + writebarrierptr(&dst[0], src[0]) + dst[1] = src[1] + writebarrierptr(&dst[2], src[2]) + dst[3] = src[3] +} + +//go:nosplit +func writebarrierfat1011(dst *[4]uintptr, _ *byte, src [4]uintptr) { + writebarrierptr(&dst[0], src[0]) + dst[1] = src[1] + writebarrierptr(&dst[2], src[2]) + writebarrierptr(&dst[3], src[3]) +} + +//go:nosplit +func writebarrierfat1100(dst *[4]uintptr, _ *byte, src [4]uintptr) { + writebarrierptr(&dst[0], src[0]) + writebarrierptr(&dst[1], src[1]) + dst[2] = src[2] + dst[3] = src[3] +} + +//go:nosplit +func writebarrierfat1101(dst *[4]uintptr, _ *byte, src [4]uintptr) { + writebarrierptr(&dst[0], src[0]) + writebarrierptr(&dst[1], src[1]) + dst[2] = src[2] + writebarrierptr(&dst[3], src[3]) +} + +//go:nosplit +func writebarrierfat1110(dst *[4]uintptr, _ *byte, src [4]uintptr) { + writebarrierptr(&dst[0], src[0]) + writebarrierptr(&dst[1], src[1]) + writebarrierptr(&dst[2], src[2]) + dst[3] = src[3] +} + +//go:nosplit +func writebarrierfat1111(dst *[4]uintptr, _ *byte, src [4]uintptr) { + writebarrierptr(&dst[0], src[0]) + writebarrierptr(&dst[1], src[1]) + writebarrierptr(&dst[2], src[2]) + writebarrierptr(&dst[3], src[3]) +} diff --git a/src/runtime/wbfat_gen.go b/src/runtime/wbfat_gen.go new file mode 100644 index 000000000..78d5b6271 --- /dev/null +++ b/src/runtime/wbfat_gen.go @@ -0,0 +1,41 @@ +// Copyright 2014 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// +build ignore + +package main + +import ( + "flag" + "fmt" + "log" + "os" +) + +func main() { + flag.Parse() + if flag.NArg() > 0 { + f, err := os.Create(flag.Arg(0)) + if err != nil { + log.Fatal(err) + } + os.Stdout = f + } + fmt.Printf("// generated by wbfat_gen.go; use go generate\n\n") + fmt.Printf("package runtime\n") + for i := uint(2); i <= 4; i++ { + for j := 1; j < 1< delta; delta += delta { + for delta := uintptr(1 << 16); delta+delta > delta; delta += delta { k := SwapPointer(&x.i, unsafe.Pointer(delta)) if uintptr(x.i) != delta || uintptr(k) != j { t.Fatalf("delta=%d i=%d j=%d k=%d", delta, x.i, j, k) @@ -456,7 +456,7 @@ func TestCompareAndSwapPointer(t *testing.T) { magicptr := uintptr(m) x.before = magicptr x.after = magicptr - for val := uintptr(1); val+val > val; val += val { + for val := uintptr(1 << 16); val+val > val; val += val { x.i = unsafe.Pointer(val) if !CompareAndSwapPointer(&x.i, unsafe.Pointer(val), unsafe.Pointer(val+1)) { t.Fatalf("should have swapped %#x %#x", val, val+1) @@ -595,7 +595,7 @@ func TestLoadPointer(t *testing.T) { magicptr := uintptr(m) x.before = magicptr x.after = magicptr - for delta := uintptr(1); delta+delta > delta; delta += delta { + for delta := uintptr(1 << 16); delta+delta > delta; delta += delta { k := LoadPointer(&x.i) if k != x.i { t.Fatalf("delta=%d i=%d k=%d", delta, x.i, k) @@ -731,7 +731,7 @@ func TestStorePointer(t *testing.T) { x.before = magicptr x.after = magicptr v := unsafe.Pointer(uintptr(0)) - for delta := uintptr(1); delta+delta > delta; delta += delta { + for delta := uintptr(1 << 16); delta+delta > delta; delta += delta { StorePointer(&x.i, unsafe.Pointer(v)) if x.i != v { t.Fatalf("delta=%d i=%d v=%d", delta, x.i, v) -- cgit v1.2.1 From 9155768e48e7de0fd0d6297eaa932d4c489e3f38 Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Tue, 4 Nov 2014 13:31:34 -0500 Subject: [dev.garbage] runtime: Add gc mark verification pass. This adds an independent mark phase to the GC that can be used to verify the the default concurrent mark phase has found all reachable objects. It uses the upper 2 bits of the boundary nibble to encode the mark leaving the lower bits to encode the boundary and the normal mark bit. LGTM=rsc R=rsc CC=golang-codereviews https://codereview.appspot.com/167130043 --- src/runtime/heapdump.c | 15 +- src/runtime/malloc.go | 28 +++- src/runtime/mgc0.c | 428 +++++++++++++++++++++++++++++++++++++++---------- src/runtime/mgc0.h | 8 +- src/runtime/stack.c | 40 +---- src/runtime/stubs.go | 6 + 6 files changed, 382 insertions(+), 143 deletions(-) (limited to 'src') diff --git a/src/runtime/heapdump.c b/src/runtime/heapdump.c index 71da419f1..5ac37803b 100644 --- a/src/runtime/heapdump.c +++ b/src/runtime/heapdump.c @@ -259,20 +259,7 @@ dumpbv(BitVector *bv, uintptr offset) dumpint(offset + i / BitsPerPointer * PtrSize); break; case BitsMultiWord: - switch(bv->bytedata[(i+BitsPerPointer)/8] >> (i+BitsPerPointer)%8 & 3) { - default: - runtime·throw("unexpected garbage collection bits"); - case BitsIface: - dumpint(FieldKindIface); - dumpint(offset + i / BitsPerPointer * PtrSize); - i += BitsPerPointer; - break; - case BitsEface: - dumpint(FieldKindEface); - dumpint(offset + i / BitsPerPointer * PtrSize); - i += BitsPerPointer; - break; - } + runtime·throw("bumpbv unexpected garbage collection bits"); } } } diff --git a/src/runtime/malloc.go b/src/runtime/malloc.go index 56f4f7cd7..274bae9a3 100644 --- a/src/runtime/malloc.go +++ b/src/runtime/malloc.go @@ -306,6 +306,18 @@ func mallocgc(size uintptr, typ *_type, flags int) unsafe.Pointer { } } marked: + + // GCmarkterminate allocates black + // All slots hold nil so no scanning is needed. + // This may be racing with GC so do it atomically if there can be + // a race marking the bit. + if gcphase == _GCmarktermination { + mp := acquirem() + mp.ptrarg[0] = x + onM(gcmarknewobject_m) + releasem(mp) + } + if raceenabled { racemalloc(x, size) } @@ -478,8 +490,12 @@ func gogc(force int32) { // Do a concurrent heap scan before we stop the world. onM(gcscan_m) + onM(gcinstallmarkwb_m) onM(stoptheworld) - + // onM(starttheworld) + // mark from roots scanned in gcscan_m. startthework when write barrier works + onM(gcmark_m) + // onM(stoptheworld) if mp != acquirem() { gothrow("gogc: rescheduled") } @@ -510,6 +526,8 @@ func gogc(force int32) { onM(gc_m) } + onM(gccheckmark_m) + // all done mp.gcing = 0 semrelease(&worldsema) @@ -524,6 +542,14 @@ func gogc(force int32) { } } +func GCcheckmarkenable() { + onM(gccheckmarkenable_m) +} + +func GCcheckmarkdisable() { + onM(gccheckmarkdisable_m) +} + // GC runs a garbage collection. func GC() { gogc(2) diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index f76d7c05c..e283f6ee8 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -155,12 +155,16 @@ extern int32 runtime·gcpercent; // uint32 runtime·worldsema = 1; +// It is a bug if bits does not have bitBoundary set but +// there are still some cases where this happens related +// to stack spans. 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. + byte bits; // mark and boundary bits relevant to corresponding slot. + byte tbits; // pointer||scalar bits relevant to corresponding slot. }; extern byte runtime·data[]; @@ -204,6 +208,11 @@ static bool inheap(byte*); static bool shaded(byte*); static void shade(byte*); static void slottombits(byte*, Markbits*); +static void atomicxor8(byte*, byte); +static bool ischeckmarked(Markbits*); +static bool ismarked(Markbits*); +static void clearcheckmarkbits(void); +static void clearcheckmarkbitsspan(MSpan*); void runtime·bgsweep(void); void runtime·finishsweep_m(void); @@ -228,6 +237,28 @@ struct WorkData { }; WorkData runtime·work; +// To help debug the concurrent GC we remark with the world +// stopped ensuring that any object encountered has their normal +// mark bit set. To do this we use an orthogonal bit +// pattern to indicate the object is marked. The following pattern +// uses the upper two bits in the object's bounday nibble. +// 01: scalar not marked +// 10: pointer not marked +// 11: pointer marked +// 00: scalar marked +// Xoring with 01 will flip the pattern from marked to unmarked and vica versa. +// The higher bit is 1 for pointers and 0 for scalars, whether the object +// is marked or not. +// The first nibble no longer holds the bitsDead pattern indicating that the +// there are no more pointers in the object. This information is held +// in the second nibble. + +// When marking an object if the bool checkmark is true one uses the above +// encoding, otherwise one uses the bitMarked bit in the lower two bits +// of the nibble. +static bool checkmark = false; +static bool gccheckmarkenable = false; + // 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 @@ -261,11 +292,14 @@ slottombits(byte *obj, Markbits *mbits) mbits->shift = (off % wordsPerBitmapByte) * gcBits; mbits->xbits = *mbits->bitp; mbits->bits = (mbits->xbits >> mbits->shift) & bitMask; + mbits->tbits = (mbits->xbits >> mbits->shift) & bitPtrMask; } // 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. +// If b is not a valid heap object return nil and +// undefined values in mbits. static byte* objectstart(byte *b, Markbits *mbits) { @@ -277,42 +311,27 @@ objectstart(byte *b, Markbits *mbits) obj = (byte*)((uintptr)b&~(PtrSize-1)); for(;;) { slottombits(obj, mbits); - if(mbits->bits&bitBoundary == bitBoundary) + 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?? + if(s != nil && s->state == MSpanStack) { + return nil; // This is legit. + } + + // The following ensures that we are rigorous about what data + // structures hold valid pointers + runtime·printf("runtime:objectstart 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("objectstart: bad span"); } p = (byte*)((uintptr)s->start<sizeclass != 0) { @@ -333,6 +352,75 @@ objectstart(byte *b, Markbits *mbits) return obj; } +// Slow for now as we serialize this, since this is on a debug path +// speed is not critical at this point. +static Mutex xorlock; +static void +atomicxor8(byte *src, byte val) +{ + runtime·lock(&xorlock); + *src = *src^val; + runtime·unlock(&xorlock); +} + +// Mark using the checkmark scheme. +void +docheckmark(Markbits *mbits) +{ + // xor 01 moves 01(scalar unmarked) to 00(scalar marked) + // and 10(pointer unmarked) to 11(pointer marked) + atomicxor8(mbits->bitp, BitsCheckMarkXor<shift<<2); + return; +} + +// In the default scheme does mbits refer to a marked object. +static bool +ismarked(Markbits *mbits) +{ + if((mbits->bits&bitBoundary) != bitBoundary) + runtime·throw("ismarked: bits should have boundary bit set"); + return (mbits->bits&bitMarked) == bitMarked; +} + +// In the checkmark scheme does mbits refer to a marked object. +static bool +ischeckmarked(Markbits *mbits) +{ + if((mbits->bits&bitBoundary) != bitBoundary) + runtime·printf("runtime:ischeckmarked: bits should have boundary bit set\n"); + return mbits->tbits==BitsScalarMarked || mbits->tbits==BitsPointerMarked; +} + +// When in GCmarkterminate phase we allocate black. +void +runtime·gcmarknewobject_m(void) +{ + Markbits mbits; + byte *obj; + + if(runtime·gcphase != GCmarktermination) + runtime·throw("marking new object while not in mark termination phase"); + if(checkmark) // The world should be stopped so this should not happen. + runtime·throw("gcmarknewobject called while doing checkmark"); + + obj = g->m->ptrarg[0]; + slottombits((byte*)((uintptr)obj & (PtrSize-1)), &mbits); + + if((mbits.bits&bitMarked) != 0) + return; + + // 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<bits&bitMarked) != 0) - return wbuf; + if(checkmark) { + if(!ismarked(mbits)) { + runtime·printf("runtime:greyobject: checkmarks finds unexpected unmarked object obj=%p, mbits->bits=%x, *mbits->bitp=%x\n", obj, mbits->bits, *mbits->bitp); + } + if(ischeckmarked(mbits)) + return wbuf; + docheckmark(mbits); + } else { + // 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); + } - // 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) + if (!checkmark && (((mbits->xbits>>(mbits->shift+2))&BitsMask) == BitsDead)) return wbuf; // noscan object // Queue the obj for scanning. The PREFETCH(obj) logic has been removed but @@ -398,6 +495,8 @@ scanobject(byte *b, uintptr n, byte *ptrmask, Workbuf *wbuf) // Find bits of the beginning of the object. if(ptrmask == nil) { b = objectstart(b, &mbits); + if(b == nil) + return wbuf; ptrbitp = mbits.bitp; //arena_start - off/wordsPerBitmapByte - 1; } for(i = 0; i < n; i += PtrSize) { @@ -407,6 +506,7 @@ scanobject(byte *b, uintptr n, byte *ptrmask, Workbuf *wbuf) bits = (ptrmask[(i/PtrSize)/4]>>(((i/PtrSize)%4)*BitsPerPointer))&BitsMask; } else { // Check if we have reached end of span. + // n is an overestimate of the size of the object. if((((uintptr)b+i)%PageSize) == 0 && runtime·mheap.spans[(b-arena_start)>>PageShift] != runtime·mheap.spans[(b+i-arena_start)>>PageShift]) break; @@ -414,7 +514,7 @@ scanobject(byte *b, uintptr n, byte *ptrmask, Workbuf *wbuf) bits = *ptrbitp; if(wordsPerBitmapByte != 2) runtime·throw("alg doesn't work for wordsPerBitmapByte != 2"); - j = ((uintptr)b+i)/PtrSize & 1; + j = ((uintptr)b+i)/PtrSize & 1; // j indicates upper nibble or lower nibble bits >>= gcBits*j; if(i == 0) bits &= ~bitBoundary; @@ -422,15 +522,19 @@ scanobject(byte *b, uintptr n, byte *ptrmask, Workbuf *wbuf) if((bits&bitBoundary) != 0 && i != 0) break; // reached beginning of the next object - bits = (bits>>2)&BitsMask; - if(bits == BitsDead) + bits = (bits&bitPtrMask)>>2; // bits refer to the type bits. + + if(i != 0 && bits == BitsDead) // BitsDead in first nibble not valid during checkmark break; // reached no-scan part of the object - } + } - if(bits <= BitsScalar) // Bits Scalar || BitsDead - continue; - if(bits != BitsPointer) { - runtime·printf("gc bits=%x\n", bits); + if(bits <= BitsScalar) // Bits Scalar || + // BitsDead || // default encoding + // BitsScalarMarked // checkmark encoding + continue; + + if((bits&BitsPointer) != BitsPointer) { + runtime·printf("gc checkmark=%d, b=%p ptrmask=%p, mbits.bitp=%p, mbits.xbits=%x, bits=%x\n", checkmark, b, ptrmask, mbits.bitp, mbits.xbits, bits); runtime·throw("unexpected garbage collection bits"); } @@ -442,6 +546,11 @@ scanobject(byte *b, uintptr n, byte *ptrmask, Workbuf *wbuf) // 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); + // In the case of the span being MSpan_Stack mbits is useless and will not have + // the boundary bit set. It does not need to be greyed since it will be + // scanned using the scan stack mechanism. + if(obj == nil) + continue; wbuf = greyobject(obj, &mbits, wbuf); } return wbuf; @@ -548,7 +657,8 @@ markroot(ParFor *desc, uint32 i) s = runtime·work.spans[spanidx]; if(s->state != MSpanInUse) continue; - if(s->sweepgen != sg) { + if(!checkmark && s->sweepgen != sg) { + // sweepgen was updated (+2) during non-checkmark GC pass runtime·printf("sweep %d %d\n", s->sweepgen, sg); runtime·throw("gc: unswept span"); } @@ -616,9 +726,6 @@ markroot(ParFor *desc, uint32 i) } } -// wblock is used for creating new empty work buffer blocks. -static Mutex wblock; - // Get an empty work buffer off the work.empty list, // allocating new buffers as needed. static Workbuf* @@ -636,10 +743,8 @@ getempty(Workbuf *b) runtime·throw("getempty: workbuffer not empty, b->nobj not 0"); } if(b == nil) { - runtime·lock(&wblock); b = runtime·persistentalloc(sizeof(*b), CacheLineSize, &mstats.gc_sys); b->nobj = 0; - runtime·unlock(&wblock); } return b; } @@ -692,17 +797,6 @@ putpartial(Workbuf *b) } } -void -runtime·gcworkbuffree(Workbuf *b) -{ - if(b == nil) - return; - if(b->nobj == 0) - putempty(b); - else - putfull(b); -} - // Get a full work buffer off the work.full or a partially // filled one off the work.partial list. If nothing is available // wait until all the other gc helpers have finished and then @@ -906,11 +1000,18 @@ static bool shaded(byte *slot) { Markbits mbits; + byte *valid; if(!inheap(slot)) // non-heap slots considered grey return true; - objectstart(slot, &mbits); + valid = objectstart(slot, &mbits); + if(valid == nil) + return true; + + if(checkmark) + return ischeckmarked(&mbits); + return (mbits.bits&bitMarked) != 0; } @@ -930,7 +1031,9 @@ shade(byte *b) // Mark the object, return some important bits. // If we combine the following two rotines we don't have to pass mbits or obj around. obj = objectstart(b, &mbits); - wbuf = greyobject(obj, &mbits, wbuf); // augments the wbuf + if(obj != nil) + wbuf = greyobject(obj, &mbits, wbuf); // augments the wbuf + putpartial(wbuf); return; } @@ -969,6 +1072,7 @@ runtime·gcphasework(G *gp) scanstack(gp); break; case GCmark: + break; case GCmarktermination: scanstack(gp); // All available mark work will be emptied before returning. @@ -1104,6 +1208,9 @@ runtime·MSpan_Sweep(MSpan *s, bool preserve) Special *special, **specialp, *y; bool res, sweepgenset; + if(checkmark) + runtime·throw("MSpan_Sweep: checkmark only runs in STW and after the sweep."); + // It's critical that we enter this function with preemption disabled, // GC must not start while we are in the middle of this function. if(g->m->locks == 0 && g->m->mallocing == 0 && g != g->m->g0) @@ -1547,6 +1654,134 @@ runtime·gc_m(void) runtime·casgstatus(gp, Gwaiting, Grunning); } +// Similar to clearcheckmarkbits but works on a single span. +// It preforms two tasks. +// 1. When used before the checkmark phase it converts BitsDead (00) to bitsScalar (01) +// for nibbles with the BoundaryBit set. +// 2. When used after the checkmark phase it converts BitsPointerMark (11) to BitsPointer 10 and +// BitsScalarMark (00) to BitsScalar (01), thus clearing the checkmark mark encoding. +// For the second case it is possible to restore the BitsDead pattern but since +// clearmark is a debug tool performance has a lower priority than simplicity. +// The span is MSpanInUse and the world is stopped. +static void +clearcheckmarkbitsspan(MSpan *s) +{ + int32 cl, n, npages, i; + uintptr size, off, step; + byte *p, *bitp, *arena_start, b; + + if(!checkmark) + runtime·throw("clearcheckmarkbitsspan: checkmark not set."); + + if(s->state != MSpanInUse) { + runtime·printf("runtime:clearcheckmarkbitsspan: state=%d\n", + s->state); + runtime·throw("clearcheckmarkbitsspan: bad span state"); + } + arena_start = runtime·mheap.arena_start; + cl = s->sizeclass; + size = s->elemsize; + if(cl == 0) { + n = 1; + } else { + // Chunk full of small blocks. + npages = runtime·class_to_allocnpages[cl]; + n = (npages << PageShift) / size; + } + + // MSpan_Sweep has similar code but instead of overloading and + // complicating that routine we do a simpler walk here. + // Sweep through n objects of given size starting at p. + // This thread owns the span now, so it can manipulate + // the block bitmap without atomic operations. + p = (byte*)(s->start << PageShift); + // Find bits for the beginning of the span. + off = (uintptr*)p - (uintptr*)arena_start; + bitp = arena_start - off/wordsPerBitmapByte - 1; + step = size/(PtrSize*wordsPerBitmapByte); + + if(step == 0) { + // updating top and bottom nibbles, all boundaries + for(i=0; i>2; + if(b == BitsScalarMarked || b == BitsPointerMarked) + *bitp ^= BitsCheckMarkXor<<2; + + if(((*bitp>>gcBits) & bitBoundary) != bitBoundary) + runtime·throw("missing bitBoundary"); + b = ((*bitp>>gcBits) & bitPtrMask)>>2; + if(b == BitsScalarMarked || b == BitsPointerMarked) + *bitp ^= BitsCheckMarkXor<<(2+gcBits); + } + } else { + // updating bottom nibble for first word of each object + for(i=0; i>2; + if(b == BitsScalarMarked || b == BitsPointerMarked) + *bitp ^= BitsCheckMarkXor<<2; + } + } +} + +// clearcheckmarkbits preforms two tasks. +// 1. When used before the checkmark phase it converts BitsDead (00) to bitsScalar (01) +// for nibbles with the BoundaryBit set. +// 2. When used after the checkmark phase it converts BitsPointerMark (11) to BitsPointer 10 and +// BitsScalarMark (00) to BitsScalar (01), thus clearing the checkmark mark encoding. +// This is a bit expensive but preserves the BitsDead encoding during the normal marking. +// BitsDead remains valid for every nibble except the ones with BitsBoundary set. +static void +clearcheckmarkbits(void) +{ + uint32 idx; + MSpan *s; + for(idx=0; idxstate == MSpanInUse) { + clearcheckmarkbitsspan(s); + } + } +} + +// Called from malloc.go using onM. +// The world is stopped. Rerun the scan and mark phases +// using the bitMarkedCheck bit instead of the +// bitMarked bit. If the marking encounters an +// bitMarked bit that is not set then we throw. +void +runtime·gccheckmark_m(void) +{ + if(!gccheckmarkenable) + return; + + if(checkmark) + runtime·throw("gccheckmark_m, entered with checkmark already true."); + + checkmark = true; + clearcheckmarkbits(); // Converts BitsDead to BitsScalar. + runtime·gc_m(); + // Work done, fixed up the GC bitmap to remove the checkmark bits. + clearcheckmarkbits(); + checkmark = false; +} + +// checkmarkenable is initially false +void +runtime·gccheckmarkenable_m(void) +{ + gccheckmarkenable = true; +} + +void +runtime·gccheckmarkdisable_m(void) +{ + gccheckmarkenable = false; +} + void runtime·finishsweep_m(void) { @@ -1631,6 +1866,21 @@ runtime·gcscan_m(void) // Let the g that called us continue to run. } +// Mark all objects that are known about. +void +runtime·gcmark_m(void) +{ + scanblock(nil, 0, nil); +} + +// For now this must be followed by a stoptheworld and a starttheworld to ensure +// all go routines see the new barrier. +void +runtime·gcinstallmarkwb_m(void) +{ + runtime·gcphase = GCmark; +} + static void gc(struct gc_args *args) { @@ -1652,7 +1902,8 @@ gc(struct gc_args *args) if(runtime·debug.gctrace) t1 = runtime·nanotime(); - runtime·finishsweep_m(); + if(!checkmark) + runtime·finishsweep_m(); // skip during checkmark debug phase. // Cache runtime·mheap.allspans in work.spans to avoid conflicts with // resizing/freeing allspans. @@ -1676,7 +1927,7 @@ gc(struct gc_args *args) runtime·work.nwait = 0; runtime·work.ndone = 0; runtime·work.nproc = runtime·gcprocs(); - runtime·gcphase = GCmark; + runtime·gcphase = GCmarktermination; // World is stopped so allglen will not change. for(i = 0; i < runtime·allglen; i++) { @@ -1774,21 +2025,24 @@ gc(struct gc_args *args) runtime·sweep.spanidx = 0; runtime·unlock(&runtime·mheap.lock); - if(ConcurrentSweep && !args->eagersweep) { - runtime·lock(&runtime·gclock); - if(runtime·sweep.g == nil) - runtime·sweep.g = runtime·newproc1(&bgsweepv, nil, 0, 0, gc); - else if(runtime·sweep.parked) { - runtime·sweep.parked = false; - runtime·ready(runtime·sweep.g); + // Start the sweep after the checkmark phase if there is one. + if(!gccheckmarkenable || checkmark) { + if(ConcurrentSweep && !args->eagersweep) { + runtime·lock(&runtime·gclock); + if(runtime·sweep.g == nil) + runtime·sweep.g = runtime·newproc1(&bgsweepv, nil, 0, 0, gc); + else if(runtime·sweep.parked) { + runtime·sweep.parked = false; + runtime·ready(runtime·sweep.g); + } + runtime·unlock(&runtime·gclock); + } else { + // Sweep all spans eagerly. + while(runtime·sweepone() != -1) + runtime·sweep.npausesweep++; + // Do an additional mProf_GC, because all 'free' events are now real as well. + runtime·mProf_GC(); } - runtime·unlock(&runtime·gclock); - } else { - // Sweep all spans eagerly. - while(runtime·sweepone() != -1) - runtime·sweep.npausesweep++; - // Do an additional mProf_GC, because all 'free' events are now real as well. - runtime·mProf_GC(); } runtime·mProf_GC(); diff --git a/src/runtime/mgc0.h b/src/runtime/mgc0.h index 16fbe4665..519d7206e 100644 --- a/src/runtime/mgc0.h +++ b/src/runtime/mgc0.h @@ -45,8 +45,12 @@ enum { // If you change these, also change scanblock. // scanblock does "if(bits == BitsScalar || bits == BitsDead)" as "if(bits <= BitsScalar)". BitsDead = 0, - BitsScalar = 1, - BitsPointer = 2, + BitsScalar = 1, // 01 + BitsPointer = 2, // 10 + BitsCheckMarkXor = 1, // 10 + BitsScalarMarked = BitsScalar ^ BitsCheckMarkXor, // 00 + BitsPointerMarked = BitsPointer ^ BitsCheckMarkXor, // 11 + BitsMultiWord = 3, // BitsMultiWord will be set for the first word of a multi-word item. // When it is set, one of the following will be set for the second word. diff --git a/src/runtime/stack.c b/src/runtime/stack.c index f18171ea5..fb23cc1c3 100644 --- a/src/runtime/stack.c +++ b/src/runtime/stack.c @@ -382,8 +382,6 @@ adjustpointers(byte **scanp, BitVector *bv, AdjustInfo *adjinfo, Func *f) uintptr delta; int32 num, i; byte *p, *minp, *maxp; - Type *t; - Itab *tab; minp = (byte*)adjinfo->old.lo; maxp = (byte*)adjinfo->old.hi; @@ -415,43 +413,7 @@ adjustpointers(byte **scanp, BitVector *bv, AdjustInfo *adjinfo, Func *f) } break; case BitsMultiWord: - switch(bv->bytedata[(i+1) / (8 / BitsPerPointer)] >> ((i+1) * BitsPerPointer & 7) & 3) { - default: - runtime·throw("unexpected garbage collection bits"); - case BitsEface: - t = (Type*)scanp[i]; - if(t != nil && ((t->kind & KindDirectIface) == 0 || (t->kind & KindNoPointers) == 0)) { - p = scanp[i+1]; - if(minp <= p && p < maxp) { - if(StackDebug >= 3) - runtime·printf("adjust eface %p\n", p); - if(t->size > PtrSize) // currently we always allocate such objects on the heap - runtime·throw("large interface value found on stack"); - scanp[i+1] = p + delta; - } - } - i++; - break; - case BitsIface: - tab = (Itab*)scanp[i]; - if(tab != nil) { - t = tab->type; - //runtime·printf(" type=%p\n", t); - if((t->kind & KindDirectIface) == 0 || (t->kind & KindNoPointers) == 0) { - p = scanp[i+1]; - if(minp <= p && p < maxp) { - if(StackDebug >= 3) - runtime·printf("adjust iface %p\n", p); - if(t->size > PtrSize) // currently we always allocate such objects on the heap - runtime·throw("large interface value found on stack"); - scanp[i+1] = p + delta; - } - } - } - i++; - break; - } - break; + runtime·throw("adjustpointers: unexpected garbage collection bits"); } } } diff --git a/src/runtime/stubs.go b/src/runtime/stubs.go index 2d5e41c1c..68f464f57 100644 --- a/src/runtime/stubs.go +++ b/src/runtime/stubs.go @@ -107,6 +107,12 @@ func mcacheRefill_m() func largeAlloc_m() func gc_m() func gcscan_m() +func gcmark_m() +func gccheckmark_m() +func gccheckmarkenable_m() +func gccheckmarkdisable_m() +func gcinstallmarkwb_m() +func gcmarknewobject_m() func finishsweep_m() func scavenge_m() func setFinalizer_m() -- cgit v1.2.1 From 494d936b2c70f1f8a1fa51efe419619c05f624e5 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Wed, 5 Nov 2014 11:09:08 -0500 Subject: [dev.garbage] runtime: fix 32-bit build TBR=crawshaw R=crawshaw CC=golang-codereviews https://codereview.appspot.com/168860046 --- src/runtime/mgc0.go | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/runtime/mgc0.go b/src/runtime/mgc0.go index 75678c522..22e88494a 100644 --- a/src/runtime/mgc0.go +++ b/src/runtime/mgc0.go @@ -84,8 +84,8 @@ func bgsweep() { } const ( - _PoisonGC = 0xf969696969696969 & ^uintptr(0) - _PoisonStack = 0x6868686868686868 & ^uintptr(0) + _PoisonGC = 0xf969696969696969 & (1<<(8*ptrSize) - 1) + _PoisonStack = 0x6868686868686868 & (1<<(8*ptrSize) - 1) ) // NOTE: Really dst *unsafe.Pointer, src unsafe.Pointer, -- cgit v1.2.1 From c4bde225a28b8ce8e0b2075c912f7726b3756300 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Wed, 5 Nov 2014 13:37:34 -0500 Subject: [dev.garbage] runtime: fix a few checkmark bugs - Some sequencing issues with stopping the first gc_m round at the right place to set up correctly for the second round. - atomicxor8 is not idempotent; avoid xor. - Maintain BitsDead type bits correctly; see long comment added. - Enable checkmark phase by default for now. LGTM=rlh R=rlh CC=golang-codereviews https://codereview.appspot.com/171090043 --- src/runtime/mgc0.c | 146 ++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 111 insertions(+), 35 deletions(-) (limited to 'src') diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index e283f6ee8..77a6c9377 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -257,7 +257,7 @@ WorkData runtime·work; // encoding, otherwise one uses the bitMarked bit in the lower two bits // of the nibble. static bool checkmark = false; -static bool gccheckmarkenable = false; +static bool gccheckmarkenable = true; // 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. @@ -292,7 +292,7 @@ slottombits(byte *obj, Markbits *mbits) mbits->shift = (off % wordsPerBitmapByte) * gcBits; mbits->xbits = *mbits->bitp; mbits->bits = (mbits->xbits >> mbits->shift) & bitMask; - mbits->tbits = (mbits->xbits >> mbits->shift) & bitPtrMask; + mbits->tbits = ((mbits->xbits >> mbits->shift) & bitPtrMask) >> 2; } // b is a pointer into the heap. @@ -354,13 +354,13 @@ objectstart(byte *b, Markbits *mbits) // Slow for now as we serialize this, since this is on a debug path // speed is not critical at this point. -static Mutex xorlock; +static Mutex andlock; static void -atomicxor8(byte *src, byte val) +atomicand8(byte *src, byte val) { - runtime·lock(&xorlock); - *src = *src^val; - runtime·unlock(&xorlock); + runtime·lock(&andlock); + *src = *src&val; + runtime·unlock(&andlock); } // Mark using the checkmark scheme. @@ -369,7 +369,16 @@ docheckmark(Markbits *mbits) { // xor 01 moves 01(scalar unmarked) to 00(scalar marked) // and 10(pointer unmarked) to 11(pointer marked) - atomicxor8(mbits->bitp, BitsCheckMarkXor<shift<<2); + if(mbits->tbits == BitsScalar) + atomicand8(mbits->bitp, ~(byte)(BitsCheckMarkXor<shift<<2)); + else if(mbits->tbits == BitsPointer) + runtime·atomicor8(mbits->bitp, BitsCheckMarkXor<shift<<2); + + // reload bits for ischeckmarked + mbits->xbits = *mbits->bitp; + mbits->bits = (mbits->xbits >> mbits->shift) & bitMask; + mbits->tbits = ((mbits->xbits >> mbits->shift) & bitPtrMask) >> 2; + return; } @@ -434,10 +443,15 @@ greyobject(byte *obj, Markbits *mbits, Workbuf *wbuf) if(checkmark) { if(!ismarked(mbits)) { runtime·printf("runtime:greyobject: checkmarks finds unexpected unmarked object obj=%p, mbits->bits=%x, *mbits->bitp=%x\n", obj, mbits->bits, *mbits->bitp); + runtime·throw("checkmark found unmarked object"); } if(ischeckmarked(mbits)) return wbuf; docheckmark(mbits); + if(!ischeckmarked(mbits)) { + runtime·printf("mbits xbits=%x bits=%x tbits=%x shift=%d\n", mbits->xbits, mbits->bits, mbits->tbits, mbits->shift); + runtime·throw("docheckmark and ischeckmarked disagree"); + } } else { // If marked we have nothing to do. if((mbits->bits&bitMarked) != 0) @@ -1670,9 +1684,6 @@ clearcheckmarkbitsspan(MSpan *s) uintptr size, off, step; byte *p, *bitp, *arena_start, b; - if(!checkmark) - runtime·throw("clearcheckmarkbitsspan: checkmark not set."); - if(s->state != MSpanInUse) { runtime·printf("runtime:clearcheckmarkbitsspan: state=%d\n", s->state); @@ -1700,19 +1711,65 @@ clearcheckmarkbitsspan(MSpan *s) bitp = arena_start - off/wordsPerBitmapByte - 1; step = size/(PtrSize*wordsPerBitmapByte); + // The type bit values are: + // 00 - BitsDead, for us BitsScalarMarked + // 01 - BitsScalar + // 10 - BitsPointer + // 11 - unused, for us BitsPointerMarked + // + // When called to prepare for the checkmark phase (checkmark==1), + // we change BitsDead to BitsScalar, so that there are no BitsScalarMarked + // type bits anywhere. + // + // The checkmark phase marks by changing BitsScalar to BitsScalarMarked + // and BitsPointer to BitsPointerMarked. + // + // When called to clean up after the checkmark phase (checkmark==0), + // we unmark by changing BitsScalarMarked back to BitsScalar and + // BitsPointerMarked back to BitsPointer. + // + // There are two problems with the scheme as just described. + // First, the setup rewrites BitsDead to BitsScalar, but the type bits + // following a BitsDead are uninitialized and must not be used. + // Second, objects that are free are expected to have their type + // bits zeroed (BitsDead), so in the cleanup we need to restore + // any BitsDeads that were there originally. + // + // In a one-word object (8-byte allocation on 64-bit system), + // there is no difference between BitsScalar and BitsDead, because + // neither is a pointer and there are no more words in the object, + // so using BitsScalar during the checkmark is safe and mapping + // both back to BitsDead during cleanup is also safe. + // + // In a larger object, we need to be more careful. During setup, + // if the type of the first word is BitsDead, we change it to BitsScalar + // (as we must) but also initialize the type of the second + // word to BitsDead, so that a scan during the checkmark phase + // will still stop before seeing the uninitialized type bits in the + // rest of the object. The sequence 'BitsScalar BitsDead' never + // happens in real type bitmaps - BitsDead is always as early + // as possible, so immediately after the last BitsPointer. + // During cleanup, if we see a BitsScalar, we can check to see if it + // is followed by BitsDead. If so, it was originally BitsDead and + // we can change it back. + if(step == 0) { // updating top and bottom nibbles, all boundaries for(i=0; i>2; - if(b == BitsScalarMarked || b == BitsPointerMarked) + if(!checkmark && (b == BitsScalar || b == BitsScalarMarked)) + *bitp &= ~0x0c; // convert to BitsDead + else if(b == BitsScalarMarked || b == BitsPointerMarked) *bitp ^= BitsCheckMarkXor<<2; - + if(((*bitp>>gcBits) & bitBoundary) != bitBoundary) runtime·throw("missing bitBoundary"); b = ((*bitp>>gcBits) & bitPtrMask)>>2; - if(b == BitsScalarMarked || b == BitsPointerMarked) + if(!checkmark && (b == BitsScalar || b == BitsScalarMarked)) + *bitp &= ~0xc0; // convert to BitsDead + else if(b == BitsScalarMarked || b == BitsPointerMarked) *bitp ^= BitsCheckMarkXor<<(2+gcBits); } } else { @@ -1721,7 +1778,19 @@ clearcheckmarkbitsspan(MSpan *s) if((*bitp & bitBoundary) != bitBoundary) runtime·throw("missing bitBoundary"); b = (*bitp & bitPtrMask)>>2; - if(b == BitsScalarMarked || b == BitsPointerMarked) + + if(checkmark && b == BitsDead) { + // move BitsDead into second word. + // set bits to BitsScalar in preparation for checkmark phase. + *bitp &= ~0xc0; + *bitp |= BitsScalar<<2; + } else if(!checkmark && (b == BitsScalar || b == BitsScalarMarked) && (*bitp & 0xc0) == 0) { + // Cleaning up after checkmark phase. + // First word is scalar or dead (we forgot) + // and second word is dead. + // First word might as well be dead too. + *bitp &= ~0x0c; + } else if(b == BitsScalarMarked || b == BitsPointerMarked) *bitp ^= BitsCheckMarkXor<<2; } } @@ -1763,10 +1832,9 @@ runtime·gccheckmark_m(void) checkmark = true; clearcheckmarkbits(); // Converts BitsDead to BitsScalar. - runtime·gc_m(); + runtime·gc_m(); // turns off checkmark // Work done, fixed up the GC bitmap to remove the checkmark bits. clearcheckmarkbits(); - checkmark = false; } // checkmarkenable is initially false @@ -2016,6 +2084,16 @@ gc(struct gc_args *args) // Free the old cached mark array if necessary. if(runtime·work.spans != nil && runtime·work.spans != runtime·mheap.allspans) runtime·SysFree(runtime·work.spans, runtime·work.nspan*sizeof(runtime·work.spans[0]), &mstats.other_sys); + + if(gccheckmarkenable) { + if(!checkmark) { + // first half of two-pass; don't set up sweep + runtime·unlock(&runtime·mheap.lock); + return; + } + checkmark = false; // done checking marks + } + // Cache the current array for sweeping. runtime·mheap.gcspans = runtime·mheap.allspans; runtime·mheap.sweepgen += 2; @@ -2025,24 +2103,22 @@ gc(struct gc_args *args) runtime·sweep.spanidx = 0; runtime·unlock(&runtime·mheap.lock); - // Start the sweep after the checkmark phase if there is one. - if(!gccheckmarkenable || checkmark) { - if(ConcurrentSweep && !args->eagersweep) { - runtime·lock(&runtime·gclock); - if(runtime·sweep.g == nil) - runtime·sweep.g = runtime·newproc1(&bgsweepv, nil, 0, 0, gc); - else if(runtime·sweep.parked) { - runtime·sweep.parked = false; - runtime·ready(runtime·sweep.g); - } - runtime·unlock(&runtime·gclock); - } else { - // Sweep all spans eagerly. - while(runtime·sweepone() != -1) - runtime·sweep.npausesweep++; - // Do an additional mProf_GC, because all 'free' events are now real as well. - runtime·mProf_GC(); + + if(ConcurrentSweep && !args->eagersweep) { + runtime·lock(&runtime·gclock); + if(runtime·sweep.g == nil) + runtime·sweep.g = runtime·newproc1(&bgsweepv, nil, 0, 0, gc); + else if(runtime·sweep.parked) { + runtime·sweep.parked = false; + runtime·ready(runtime·sweep.g); } + runtime·unlock(&runtime·gclock); + } else { + // Sweep all spans eagerly. + while(runtime·sweepone() != -1) + runtime·sweep.npausesweep++; + // Do an additional mProf_GC, because all 'free' events are now real as well. + runtime·mProf_GC(); } runtime·mProf_GC(); -- cgit v1.2.1 From 6d5e8c9c938b45ddcc62470a790408642a26218b Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Wed, 5 Nov 2014 14:42:24 -0500 Subject: [dev.garbage] runtime: ignore objects in dead spans We still don't know why this is happening. LGTM=rlh R=rlh CC=golang-codereviews https://codereview.appspot.com/169990043 --- src/runtime/mgc0.c | 16 ++++++++++------ 1 file changed, 10 insertions(+), 6 deletions(-) (limited to 'src') diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index 77a6c9377..3ebaf005f 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -326,12 +326,16 @@ objectstart(byte *b, Markbits *mbits) // The following ensures that we are rigorous about what data // structures hold valid pointers - runtime·printf("runtime:objectstart 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("objectstart: bad span"); + if(0) { + // Still happens sometimes. We don't know why. + runtime·printf("runtime:objectstart 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("objectstart: bad pointer in unexpected span"); + } + return nil; } p = (byte*)((uintptr)s->start<sizeclass != 0) { -- cgit v1.2.1 From aefaeb75f3eff323f212c5309d8ae65768ad9809 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Wed, 5 Nov 2014 14:42:54 -0500 Subject: [dev.garbage] cmd/gc, runtime: add locks around print statements Now each C printf, Go print, or Go println is guaranteed not to be interleaved with other calls of those functions. This should help when debugging concurrent failures. LGTM=rlh R=rlh CC=golang-codereviews https://codereview.appspot.com/169120043 --- src/cmd/gc/builtin.c | 2 ++ src/cmd/gc/go.h | 1 + src/cmd/gc/runtime.go | 2 ++ src/cmd/gc/walk.c | 17 +++++++++++++++++ src/runtime/print1.go | 30 +++++++++++++++++++++++++++--- src/runtime/runtime.h | 1 + 6 files changed, 50 insertions(+), 3 deletions(-) (limited to 'src') diff --git a/src/cmd/gc/builtin.c b/src/cmd/gc/builtin.c index bd3fca167..aeeadedca 100644 --- a/src/cmd/gc/builtin.c +++ b/src/cmd/gc/builtin.c @@ -24,6 +24,8 @@ char *runtimeimport = "func @\"\".printslice (? any)\n" "func @\"\".printnl ()\n" "func @\"\".printsp ()\n" + "func @\"\".printlock ()\n" + "func @\"\".printunlock ()\n" "func @\"\".concatstring2 (? string, ? string) (? string)\n" "func @\"\".concatstring3 (? string, ? string, ? string) (? string)\n" "func @\"\".concatstring4 (? string, ? string, ? string, ? string) (? string)\n" diff --git a/src/cmd/gc/go.h b/src/cmd/gc/go.h index 965a0550d..cc590416b 100644 --- a/src/cmd/gc/go.h +++ b/src/cmd/gc/go.h @@ -1464,6 +1464,7 @@ void walk(Node *fn); void walkexpr(Node **np, NodeList **init); void walkexprlist(NodeList *l, NodeList **init); void walkexprlistsafe(NodeList *l, NodeList **init); +void walkexprlistcheap(NodeList *l, NodeList **init); void walkstmt(Node **np); void walkstmtlist(NodeList *l); Node* conv(Node*, Type*); diff --git a/src/cmd/gc/runtime.go b/src/cmd/gc/runtime.go index 38bf6abb6..c6007714c 100644 --- a/src/cmd/gc/runtime.go +++ b/src/cmd/gc/runtime.go @@ -36,6 +36,8 @@ func printeface(any) func printslice(any) func printnl() func printsp() +func printlock() +func printunlock() func concatstring2(string, string) string func concatstring3(string, string, string) string diff --git a/src/cmd/gc/walk.c b/src/cmd/gc/walk.c index 7b502eb60..38bed1e22 100644 --- a/src/cmd/gc/walk.c +++ b/src/cmd/gc/walk.c @@ -363,6 +363,15 @@ walkexprlistsafe(NodeList *l, NodeList **init) } } +void +walkexprlistcheap(NodeList *l, NodeList **init) +{ + for(; l; l=l->next) { + l->n = cheapexpr(l->n, init); + walkexpr(&l->n, init); + } +} + void walkexpr(Node **np, NodeList **init) { @@ -1773,6 +1782,11 @@ walkprint(Node *nn, NodeList **init) calls = nil; notfirst = 0; + // Hoist all the argument evaluation up before the lock. + walkexprlistcheap(all, init); + + calls = list(calls, mkcall("printlock", T, init)); + for(l=all; l; l=l->next) { if(notfirst) { calls = list(calls, mkcall("printsp", T, init)); @@ -1853,6 +1867,9 @@ walkprint(Node *nn, NodeList **init) if(op == OPRINTN) calls = list(calls, mkcall("printnl", T, nil)); + + calls = list(calls, mkcall("printunlock", T, init)); + typechecklist(calls, Etop); walkexprlist(calls, init); diff --git a/src/runtime/print1.go b/src/runtime/print1.go index 8f8268873..3d812bd04 100644 --- a/src/runtime/print1.go +++ b/src/runtime/print1.go @@ -41,7 +41,31 @@ func snprintf(dst *byte, n int32, s *byte) { gp.writebuf = nil } -//var debuglock mutex +var debuglock mutex + +// The compiler emits calls to printlock and printunlock around +// the multiple calls that implement a single Go print or println +// statement. Some of the print helpers (printsp, for example) +// call print recursively. There is also the problem of a crash +// happening during the print routines and needing to acquire +// the print lock to print information about the crash. +// For both these reasons, let a thread acquire the printlock 'recursively'. + +func printlock() { + mp := getg().m + mp.printlock++ + if mp.printlock == 1 { + lock(&debuglock) + } +} + +func printunlock() { + mp := getg().m + mp.printlock-- + if mp.printlock == 0 { + unlock(&debuglock) + } +} // write to goroutine-local buffer if diverting output, // or else standard error. @@ -80,7 +104,7 @@ func printnl() { // Very simple printf. Only for debugging prints. // Do not add to this without checking with Rob. func vprintf(str string, arg unsafe.Pointer) { - //lock(&debuglock); + printlock() s := bytes(str) start := 0 @@ -160,7 +184,7 @@ func vprintf(str string, arg unsafe.Pointer) { gwrite(s[start:i]) } - //unlock(&debuglock); + printunlock() } func printpc(p unsafe.Pointer) { diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index 6a02ef1d3..ee86f2d17 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -345,6 +345,7 @@ struct M int32 helpgc; bool spinning; // M is out of work and is actively looking for work bool blocked; // M is blocked on a Note + int8 printlock; uint32 fastrand; uint64 ncgocall; // number of cgo calls in total int32 ncgo; // number of cgo calls currently in progress -- cgit v1.2.1 From c3f533c86a28f6990b8d35a7ed9c30a6f620e853 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Wed, 5 Nov 2014 15:43:41 -0500 Subject: [dev.garbage] cmd/gc: emit pointer write barriers This got lost in the change that added the writebarrierfat variants. LGTM=rlh R=rlh CC=golang-codereviews https://codereview.appspot.com/165510043 --- src/cmd/gc/walk.c | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'src') diff --git a/src/cmd/gc/walk.c b/src/cmd/gc/walk.c index 38bed1e22..37bd62dea 100644 --- a/src/cmd/gc/walk.c +++ b/src/cmd/gc/walk.c @@ -2015,6 +2015,8 @@ applywritebarrier(Node *n, NodeList **init) l = nod(OADDR, n->left, N); l->etype = 1; // addr does not escape if(t->width == widthptr) { + n = mkcall1(writebarrierfn("writebarrierptr", t, n->right->type), T, init, + l, n->right); } else if(t->etype == TSTRING) { n = mkcall1(writebarrierfn("writebarrierstring", t, n->right->type), T, init, l, n->right); @@ -2037,6 +2039,8 @@ applywritebarrier(Node *n, NodeList **init) if(BitsPointer != (1<width/widthptr) { + default: + fatal("found writebarrierfat for %d-byte object of type %T", (int)t->width, t); case 2: snprint(name, sizeof name, "writebarrierfat%d%d", bvget(bv, PtrBit), bvget(bv, BitsPerPointer+PtrBit)); -- cgit v1.2.1 From cb223591339d2e03283e21144057b30d5e9667dd Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Mon, 10 Nov 2014 13:42:34 -0500 Subject: [dev.garbage] runtime: Code to implement write barriers To turn concurrent gc on alter the if false in func gogc currently at line 489 in malloc.go LGTM=rsc R=rsc CC=golang-codereviews, rlh https://codereview.appspot.com/172190043 Committer: Russ Cox --- src/runtime/malloc.go | 21 +++++++++++---------- src/runtime/mgc0.c | 39 ++++++++++++++++++++++++++++++++++----- src/runtime/mgc0.go | 19 ++++++++++++++++++- src/runtime/runtime.h | 1 + src/runtime/stubs.go | 2 ++ 5 files changed, 66 insertions(+), 16 deletions(-) (limited to 'src') diff --git a/src/runtime/malloc.go b/src/runtime/malloc.go index 274bae9a3..a18e77421 100644 --- a/src/runtime/malloc.go +++ b/src/runtime/malloc.go @@ -486,16 +486,17 @@ func gogc(force int32) { onM(stoptheworld) onM(finishsweep_m) // finish sweep before we start concurrent scan. - onM(starttheworld) - - // Do a concurrent heap scan before we stop the world. - onM(gcscan_m) - onM(gcinstallmarkwb_m) - onM(stoptheworld) - // onM(starttheworld) - // mark from roots scanned in gcscan_m. startthework when write barrier works - onM(gcmark_m) - // onM(stoptheworld) + if false { // To turn on concurrent scan and mark set to true... + onM(starttheworld) + // Do a concurrent heap scan before we stop the world. + onM(gcscan_m) + onM(stoptheworld) + onM(gcinstallmarkwb_m) + onM(starttheworld) + onM(gcmark_m) + onM(stoptheworld) + onM(gcinstalloffwb_m) + } if mp != acquirem() { gothrow("gogc: rescheduled") } diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index 3ebaf005f..5300f554b 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -1061,13 +1061,34 @@ shade(byte *b) // // Shade indicates that it has seen a white pointer by adding the referent // to wbuf. +// slot is the destination (dst) in go code +// ptr is the value that goes into the slot (src) in the go code void -runtime·markwb(void **slot, void *ptr) +runtime·gcmarkwb_m() { - // initial nil check avoids some needlesss loads - if(ptr != nil && inheap(ptr) && shaded((void*)slot)) - shade(ptr); + byte **slot, *ptr; + slot = (byte**)g->m->scalararg[0]; + ptr = (byte*)g->m->scalararg[1]; + *slot = ptr; + switch(runtime·gcphase) { + default: + runtime·throw("gcphasework in bad gcphase"); + case GCoff: + case GCquiesce: + case GCstw: + case GCsweep: + case GCscan: + break; + case GCmark: + if(ptr != nil && inheap(ptr) && shaded((byte*)slot)) + shade(ptr); + break; + case GCmarktermination: + if(ptr != nil && inheap(ptr) && shaded((byte*)slot)) + shade(ptr); + break; + } } // The gp has been moved to a GC safepoint. GC phase specific @@ -1945,7 +1966,7 @@ runtime·gcmark_m(void) scanblock(nil, 0, nil); } -// For now this must be followed by a stoptheworld and a starttheworld to ensure +// For now this must be bracketed with a stoptheworld and a starttheworld to ensure // all go routines see the new barrier. void runtime·gcinstallmarkwb_m(void) @@ -1953,6 +1974,14 @@ runtime·gcinstallmarkwb_m(void) runtime·gcphase = GCmark; } +// For now this must be bracketed with a stoptheworld and a starttheworld to ensure +// all go routines see the new barrier. +void +runtime·gcinstalloffwb_m(void) +{ + runtime·gcphase = GCoff; +} + static void gc(struct gc_args *args) { diff --git a/src/runtime/mgc0.go b/src/runtime/mgc0.go index 22e88494a..ce5c290ef 100644 --- a/src/runtime/mgc0.go +++ b/src/runtime/mgc0.go @@ -95,7 +95,24 @@ func writebarrierptr(dst *uintptr, src uintptr) { if src != 0 && (src < _PageSize || src == _PoisonGC || src == _PoisonStack) { onM(func() { gothrow("bad pointer in write barrier") }) } - *dst = src + + mp := acquirem() + if mp.inwb { + *dst = src + releasem(mp) + return + } + mp.inwb = true + oldscalar0 := mp.scalararg[0] + oldscalar1 := mp.scalararg[1] + mp.scalararg[0] = uintptr(unsafe.Pointer(dst)) + mp.scalararg[1] = src + onM_signalok(gcmarkwb_m) + mp.scalararg[0] = oldscalar0 + mp.scalararg[1] = oldscalar1 + mp.inwb = false + releasem(mp) + // *dst = src is done inside of the write barrier. } //go:nosplit diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index ee86f2d17..a0f1acc05 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -345,6 +345,7 @@ struct M int32 helpgc; bool spinning; // M is out of work and is actively looking for work bool blocked; // M is blocked on a Note + bool inwb; // M is executing a write barrier int8 printlock; uint32 fastrand; uint64 ncgocall; // number of cgo calls in total diff --git a/src/runtime/stubs.go b/src/runtime/stubs.go index 68f464f57..852f4ddbb 100644 --- a/src/runtime/stubs.go +++ b/src/runtime/stubs.go @@ -112,7 +112,9 @@ func gccheckmark_m() func gccheckmarkenable_m() func gccheckmarkdisable_m() func gcinstallmarkwb_m() +func gcinstalloffwb_m() func gcmarknewobject_m() +func gcmarkwb_m() func finishsweep_m() func scavenge_m() func setFinalizer_m() -- cgit v1.2.1 From 11c9da27d8b3d09835a611edea424885af1ec650 Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Mon, 10 Nov 2014 14:32:02 -0500 Subject: [dev.garbage] runtime: Coarsen the write barrier to always grey the destination. LGTM=rsc R=rsc CC=golang-codereviews https://codereview.appspot.com/174820043 --- src/runtime/mgc0.c | 38 +++++++++++++++++++++++++++++++++----- 1 file changed, 33 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index 5300f554b..3f6cce5c0 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -1056,13 +1056,41 @@ shade(byte *b) return; } -// This is the Dijkstra barrier coarsened to shade grey to white whereas -// the original Dijkstra barrier only shaded black to white. +// This is the Dijkstra barrier coarsened to always shade the ptr (dst) object. +// The original Dijkstra barrier only shaded ptrs being placed in black slots. // // Shade indicates that it has seen a white pointer by adding the referent -// to wbuf. +// to wbuf as well as marking it. +// // slot is the destination (dst) in go code // ptr is the value that goes into the slot (src) in the go code +// +// Dijkstra pointed out that maintaining the no black to white +// pointers means that white to white pointers not need +// to be noted by the write barrier. Furthermore if either +// white object dies before it is reached by the +// GC then the object can be collected during this GC cycle +// instead of waiting for the next cycle. Unfortunately the cost of +// ensure that the object holding the slot doesn't concurrently +// change to black without the mutator noticing seems prohibitive. +// +// Consider the following example where the mutator writes into +// a slot and then loads the slot's mark bit while the GC thread +// writes to the slot's mark bit and then as part of scanning reads +// the slot. +// +// Initially both [slot] and [slotmark] are 0 (nil) +// Mutator thread GC thread +// st [slot], ptr st [slotmark], 1 +// +// ld r1, [slotmark] ld r2, [slot] +// +// This is a classic example of independent reads of independent writes, +// aka IRIW. The question is if r1==r2==0 is allowed and for most HW the +// answer is yes without inserting a memory barriers between the st and the ld. +// These barriers are expensive so we have decided that we will +// always grey the ptr object regardless of the slot's color. +// void runtime·gcmarkwb_m() { @@ -1081,11 +1109,11 @@ runtime·gcmarkwb_m() case GCscan: break; case GCmark: - if(ptr != nil && inheap(ptr) && shaded((byte*)slot)) + if(ptr != nil && inheap(ptr)) shade(ptr); break; case GCmarktermination: - if(ptr != nil && inheap(ptr) && shaded((byte*)slot)) + if(ptr != nil && inheap(ptr)) shade(ptr); break; } -- cgit v1.2.1 From f4d66a3a39bd302d7fd96fc98c086813cfdaf755 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Mon, 10 Nov 2014 14:59:36 -0500 Subject: [dev.garbage] runtime: add write barrier to casp Also rewrite some casp that don't use real pointers to use casuintptr instead. LGTM=rlh R=rlh CC=golang-codereviews https://codereview.appspot.com/166440044 --- src/runtime/asm_386.s | 6 +++--- src/runtime/asm_amd64.s | 6 +++--- src/runtime/asm_amd64p32.s | 6 +++--- src/runtime/asm_power64x.s | 6 +++--- src/runtime/atomic.go | 38 ++++++++++++++++++++++++++++++++++---- src/runtime/mgc0.c | 1 - src/runtime/mgc0.go | 14 ++++++++++++-- src/runtime/proc.c | 14 +++++++------- src/runtime/runtime.h | 1 + src/runtime/string.c | 2 +- src/runtime/stubs.go | 3 --- 11 files changed, 67 insertions(+), 30 deletions(-) (limited to 'src') diff --git a/src/runtime/asm_386.s b/src/runtime/asm_386.s index 2d102b273..d456e6bca 100644 --- a/src/runtime/asm_386.s +++ b/src/runtime/asm_386.s @@ -502,7 +502,7 @@ fail: // return 1; // }else // return 0; -TEXT runtime·casp(SB), NOSPLIT, $0-13 +TEXT runtime·casp1(SB), NOSPLIT, $0-13 MOVL ptr+0(FP), BX MOVL old+4(FP), AX MOVL new+8(FP), CX @@ -537,7 +537,7 @@ TEXT runtime·xchg(SB), NOSPLIT, $0-12 MOVL AX, ret+8(FP) RET -TEXT runtime·xchgp(SB), NOSPLIT, $0-12 +TEXT runtime·xchgp1(SB), NOSPLIT, $0-12 MOVL ptr+0(FP), BX MOVL new+4(FP), AX XCHGL AX, 0(BX) @@ -555,7 +555,7 @@ again: JNZ again RET -TEXT runtime·atomicstorep(SB), NOSPLIT, $0-8 +TEXT runtime·atomicstorep1(SB), NOSPLIT, $0-8 MOVL ptr+0(FP), BX MOVL val+4(FP), AX XCHGL AX, 0(BX) diff --git a/src/runtime/asm_amd64.s b/src/runtime/asm_amd64.s index ac9c58cf3..5d176575c 100644 --- a/src/runtime/asm_amd64.s +++ b/src/runtime/asm_amd64.s @@ -489,7 +489,7 @@ TEXT runtime·atomicstoreuintptr(SB), NOSPLIT, $0-16 // return 1; // } else // return 0; -TEXT runtime·casp(SB), NOSPLIT, $0-25 +TEXT runtime·casp1(SB), NOSPLIT, $0-25 MOVQ ptr+0(FP), BX MOVQ old+8(FP), AX MOVQ new+16(FP), CX @@ -541,7 +541,7 @@ TEXT runtime·xchg64(SB), NOSPLIT, $0-24 MOVQ AX, ret+16(FP) RET -TEXT runtime·xchgp(SB), NOSPLIT, $0-24 +TEXT runtime·xchgp1(SB), NOSPLIT, $0-24 MOVQ ptr+0(FP), BX MOVQ new+8(FP), AX XCHGQ AX, 0(BX) @@ -559,7 +559,7 @@ again: JNZ again RET -TEXT runtime·atomicstorep(SB), NOSPLIT, $0-16 +TEXT runtime·atomicstorep1(SB), NOSPLIT, $0-16 MOVQ ptr+0(FP), BX MOVQ val+8(FP), AX XCHGQ AX, 0(BX) diff --git a/src/runtime/asm_amd64p32.s b/src/runtime/asm_amd64p32.s index de3ef3a23..2b2155753 100644 --- a/src/runtime/asm_amd64p32.s +++ b/src/runtime/asm_amd64p32.s @@ -460,7 +460,7 @@ fail: // return 1; // } else // return 0; -TEXT runtime·casp(SB), NOSPLIT, $0-17 +TEXT runtime·casp1(SB), NOSPLIT, $0-17 MOVL ptr+0(FP), BX MOVL old+4(FP), AX MOVL new+8(FP), CX @@ -512,7 +512,7 @@ TEXT runtime·xchg64(SB), NOSPLIT, $0-24 MOVQ AX, ret+16(FP) RET -TEXT runtime·xchgp(SB), NOSPLIT, $0-12 +TEXT runtime·xchgp1(SB), NOSPLIT, $0-12 MOVL ptr+0(FP), BX MOVL new+4(FP), AX XCHGL AX, 0(BX) @@ -530,7 +530,7 @@ again: JNZ again RET -TEXT runtime·atomicstorep(SB), NOSPLIT, $0-8 +TEXT runtime·atomicstorep1(SB), NOSPLIT, $0-8 MOVL ptr+0(FP), BX MOVL val+4(FP), AX XCHGL AX, 0(BX) diff --git a/src/runtime/asm_power64x.s b/src/runtime/asm_power64x.s index f77658032..fd0c6be16 100644 --- a/src/runtime/asm_power64x.s +++ b/src/runtime/asm_power64x.s @@ -472,7 +472,7 @@ TEXT runtime·atomicstoreuintptr(SB), NOSPLIT, $0-16 // return 1; // } else // return 0; -TEXT runtime·casp(SB), NOSPLIT, $0-25 +TEXT runtime·casp1(SB), NOSPLIT, $0-25 BR runtime·cas64(SB) // uint32 xadd(uint32 volatile *val, int32 delta) @@ -529,7 +529,7 @@ TEXT runtime·xchg64(SB), NOSPLIT, $0-24 MOVD R3, ret+16(FP) RETURN -TEXT runtime·xchgp(SB), NOSPLIT, $0-24 +TEXT runtime·xchgp1(SB), NOSPLIT, $0-24 BR runtime·xchg64(SB) TEXT runtime·xchguintptr(SB), NOSPLIT, $0-24 @@ -538,7 +538,7 @@ TEXT runtime·xchguintptr(SB), NOSPLIT, $0-24 TEXT runtime·procyield(SB),NOSPLIT,$0-0 RETURN -TEXT runtime·atomicstorep(SB), NOSPLIT, $0-16 +TEXT runtime·atomicstorep1(SB), NOSPLIT, $0-16 BR runtime·atomicstore64(SB) TEXT runtime·atomicstore(SB), NOSPLIT, $0-12 diff --git a/src/runtime/atomic.go b/src/runtime/atomic.go index 7e9d9b3aa..a0e4d84e9 100644 --- a/src/runtime/atomic.go +++ b/src/runtime/atomic.go @@ -20,8 +20,16 @@ func xchg(ptr *uint32, new uint32) uint32 //go:noescape func xchg64(ptr *uint64, new uint64) uint64 -//go:noescape -func xchgp(ptr unsafe.Pointer, new unsafe.Pointer) unsafe.Pointer +// Cannot use noescape here: ptr does not but new does escape. +// Instead use noescape(ptr) in wrapper below. +func xchgp1(ptr unsafe.Pointer, new unsafe.Pointer) unsafe.Pointer + +//go:nosplit +func xchgp(ptr unsafe.Pointer, new unsafe.Pointer) unsafe.Pointer { + old := xchgp1(noescape(ptr), new) + writebarrierptr_nostore((*uintptr)(ptr), uintptr(new)) + return old +} //go:noescape func xchguintptr(ptr *uintptr, new uintptr) uintptr @@ -47,5 +55,27 @@ func atomicstore(ptr *uint32, val uint32) //go:noescape func atomicstore64(ptr *uint64, val uint64) -//go:noescape -func atomicstorep(ptr unsafe.Pointer, val unsafe.Pointer) +// Cannot use noescape here: ptr does not but val does escape. +// Instead use noescape(ptr) in wrapper below. +func atomicstorep1(ptr unsafe.Pointer, val unsafe.Pointer) + +//go:nosplit +func atomicstorep(ptr unsafe.Pointer, val unsafe.Pointer) { + atomicstorep1(noescape(ptr), val) + // TODO(rsc): Why does the compiler think writebarrierptr_nostore's dst argument escapes? + writebarrierptr_nostore((*uintptr)(noescape(ptr)), uintptr(val)) +} + +// Cannot use noescape here: ptr does not but new does escape. +// Instead use noescape(ptr) in wrapper below. +func casp1(ptr *unsafe.Pointer, old, new unsafe.Pointer) bool + +//go:nosplit +func casp(ptr *unsafe.Pointer, old, new unsafe.Pointer) bool { + ok := casp1((*unsafe.Pointer)(noescape(unsafe.Pointer(ptr))), old, new) + if !ok { + return false + } + writebarrierptr_nostore((*uintptr)(unsafe.Pointer(ptr)), uintptr(new)) + return true +} diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index 3f6cce5c0..8d87107c7 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -1098,7 +1098,6 @@ runtime·gcmarkwb_m() slot = (byte**)g->m->scalararg[0]; ptr = (byte*)g->m->scalararg[1]; - *slot = ptr; switch(runtime·gcphase) { default: runtime·throw("gcphasework in bad gcphase"); diff --git a/src/runtime/mgc0.go b/src/runtime/mgc0.go index ce5c290ef..760d2a545 100644 --- a/src/runtime/mgc0.go +++ b/src/runtime/mgc0.go @@ -92,13 +92,24 @@ const ( // but if we do that, Go inserts a write barrier on *dst = src. //go:nosplit func writebarrierptr(dst *uintptr, src uintptr) { + *dst = src + writebarrierptr_nostore(dst, src) +} + +// Like writebarrierptr, but the store has already been applied. +// Do not reapply. +//go:nosplit +func writebarrierptr_nostore(dst *uintptr, src uintptr) { + if getg() == nil { // very low-level startup + return + } + if src != 0 && (src < _PageSize || src == _PoisonGC || src == _PoisonStack) { onM(func() { gothrow("bad pointer in write barrier") }) } mp := acquirem() if mp.inwb { - *dst = src releasem(mp) return } @@ -112,7 +123,6 @@ func writebarrierptr(dst *uintptr, src uintptr) { mp.scalararg[1] = oldscalar1 mp.inwb = false releasem(mp) - // *dst = src is done inside of the write barrier. } //go:nosplit diff --git a/src/runtime/proc.c b/src/runtime/proc.c index 9626bd101..e5e2df2e4 100644 --- a/src/runtime/proc.c +++ b/src/runtime/proc.c @@ -1060,7 +1060,7 @@ runtime·dropm(void) unlockextra(mp); } -#define MLOCKED ((M*)1) +#define MLOCKED 1 // lockextra locks the extra list and returns the list head. // The caller must unlock the list by storing a new list head @@ -1071,28 +1071,28 @@ runtime·dropm(void) static M* lockextra(bool nilokay) { - M *mp; + uintptr mpx; void (*yield)(void); for(;;) { - mp = runtime·atomicloadp(&runtime·extram); - if(mp == MLOCKED) { + mpx = runtime·atomicloaduintptr((uintptr*)&runtime·extram); + if(mpx == MLOCKED) { yield = runtime·osyield; yield(); continue; } - if(mp == nil && !nilokay) { + if(mpx == 0 && !nilokay) { runtime·usleep(1); continue; } - if(!runtime·casp(&runtime·extram, mp, MLOCKED)) { + if(!runtime·casuintptr((uintptr*)&runtime·extram, mpx, MLOCKED)) { yield = runtime·osyield; yield(); continue; } break; } - return mp; + return (M*)mpx; } #pragma textflag NOSPLIT diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index a0f1acc05..a4186f450 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -894,6 +894,7 @@ int32 runtime·round2(int32 x); // round x up to a power of 2. bool runtime·cas(uint32*, uint32, uint32); bool runtime·cas64(uint64*, uint64, uint64); bool runtime·casp(void**, void*, void*); +bool runtime·casuintptr(uintptr*, uintptr, uintptr); // Don't confuse with XADD x86 instruction, // this one is actually 'addx', that is, add-and-fetch. uint32 runtime·xadd(uint32 volatile*, int32); diff --git a/src/runtime/string.c b/src/runtime/string.c index ed5debc33..475ea2de6 100644 --- a/src/runtime/string.c +++ b/src/runtime/string.c @@ -48,7 +48,7 @@ runtime·gostringnocopy(byte *str) s.len = runtime·findnull(str); while(true) { ms = runtime·maxstring; - if(s.len <= ms || runtime·casp((void**)&runtime·maxstring, (void*)ms, (void*)s.len)) + if(s.len <= ms || runtime·casuintptr(&runtime·maxstring, ms, s.len)) return s; } } diff --git a/src/runtime/stubs.go b/src/runtime/stubs.go index 852f4ddbb..421ab04e5 100644 --- a/src/runtime/stubs.go +++ b/src/runtime/stubs.go @@ -213,9 +213,6 @@ func write(fd uintptr, p unsafe.Pointer, n int32) int32 //go:noescape func cas(ptr *uint32, old, new uint32) bool -//go:noescape -func casp(ptr *unsafe.Pointer, old, new unsafe.Pointer) bool - //go:noescape func casuintptr(ptr *uintptr, old, new uintptr) bool -- cgit v1.2.1 From fc350a0d75c2df2eea560e66483dbb6f04d00e35 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Tue, 11 Nov 2014 16:54:50 -0500 Subject: [dev.garbage] runtime: concurrent mark fixes Add missing write barrier when initializing state for newly created goroutine. Add write barrier for same slot when preempting a goroutine. Disable write barrier during goroutine death, because dopanic does pointer writes. With concurrent mark enabled (not in this CL), all.bash passed once. The second time, TestGoexitCrash-2 failed. LGTM=rlh R=rlh CC=golang-codereviews https://codereview.appspot.com/167610043 --- src/runtime/mgc0.c | 3 +-- src/runtime/mgc0.go | 2 +- src/runtime/runtime.h | 2 ++ src/runtime/stack.c | 8 ++++++++ src/runtime/sys_x86.c | 1 + 5 files changed, 13 insertions(+), 3 deletions(-) (limited to 'src') diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index 8d87107c7..3c4d1afa5 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -1094,8 +1094,7 @@ shade(byte *b) void runtime·gcmarkwb_m() { - byte **slot, *ptr; - slot = (byte**)g->m->scalararg[0]; + byte *ptr; ptr = (byte*)g->m->scalararg[1]; switch(runtime·gcphase) { diff --git a/src/runtime/mgc0.go b/src/runtime/mgc0.go index 760d2a545..dc4eec519 100644 --- a/src/runtime/mgc0.go +++ b/src/runtime/mgc0.go @@ -109,7 +109,7 @@ func writebarrierptr_nostore(dst *uintptr, src uintptr) { } mp := acquirem() - if mp.inwb { + if mp.inwb || mp.dying > 0 { releasem(mp) return } diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index a4186f450..fec224390 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -1121,6 +1121,8 @@ void runtime·osyield(void); void runtime·lockOSThread(void); void runtime·unlockOSThread(void); +void runtime·writebarrierptr_nostore(void*, void*); + bool runtime·showframe(Func*, G*); void runtime·printcreatedby(G*); diff --git a/src/runtime/stack.c b/src/runtime/stack.c index fb23cc1c3..a4947a53b 100644 --- a/src/runtime/stack.c +++ b/src/runtime/stack.c @@ -706,6 +706,14 @@ runtime·newstack(void) runtime·printf("runtime: split stack overflow: %p < %p\n", sp, gp->stack.lo); runtime·throw("runtime: split stack overflow"); } + + if(gp->sched.ctxt != nil) { + // morestack wrote sched.ctxt on its way in here, + // without a write barrier. Run the write barrier now. + // It is not possible to be preempted between then + // and now, so it's okay. + runtime·writebarrierptr_nostore(&gp->sched.ctxt, gp->sched.ctxt); + } if(gp->stackguard0 == (uintptr)StackPreempt) { if(gp == g->m->g0) diff --git a/src/runtime/sys_x86.c b/src/runtime/sys_x86.c index a450b3e58..edbe47ff4 100644 --- a/src/runtime/sys_x86.c +++ b/src/runtime/sys_x86.c @@ -20,6 +20,7 @@ runtime·gostartcall(Gobuf *gobuf, void (*fn)(void), void *ctxt) gobuf->sp = (uintptr)sp; gobuf->pc = (uintptr)fn; gobuf->ctxt = ctxt; + runtime·writebarrierptr_nostore(&gobuf->ctxt, ctxt); } // Called to rewind context saved during morestack back to beginning of function. -- cgit v1.2.1 From 4664f7441b495d8fa8aa5001755cb5f85e790b19 Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Wed, 12 Nov 2014 14:20:53 -0500 Subject: [dev.garbage] runtime: Add write barriers to c code Also improve missing GC mark diagnostics. LGTM=rsc R=rsc CC=golang-codereviews https://codereview.appspot.com/169450043 --- src/runtime/mgc0.c | 21 +++++++++++++++++++-- src/runtime/os_darwin.c | 3 +++ src/runtime/os_dragonfly.c | 3 +++ src/runtime/os_freebsd.c | 3 +++ src/runtime/os_linux.c | 3 +++ src/runtime/os_nacl.c | 3 +++ src/runtime/os_netbsd.c | 3 +++ src/runtime/os_openbsd.c | 3 +++ src/runtime/os_plan9.c | 6 ++++++ src/runtime/os_solaris.c | 3 +++ src/runtime/proc.c | 2 ++ 11 files changed, 51 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c index 3c4d1afa5..214b9ebc2 100644 --- a/src/runtime/mgc0.c +++ b/src/runtime/mgc0.c @@ -29,8 +29,7 @@ // Preempted goroutines are scanned before P schedules next goroutine. // 3. Set phase = GCmark. // 4. Wait for all P's to acknowledge phase change. -// 5. Now write barrier marks and enqueues black or grey to white pointers. If a pointer is -// stored into a white slot, such pointer is not marked. +// 5. Now write barrier marks and enqueues black, grey, or white to white pointers. // Malloc still allocates white (non-marked) objects. // 6. Meanwhile GC transitively walks the heap marking reachable objects. // 7. When GC finishes marking heap, it preempts P's one-by-one and @@ -446,7 +445,25 @@ greyobject(byte *obj, Markbits *mbits, Workbuf *wbuf) if(checkmark) { if(!ismarked(mbits)) { + MSpan *s; + pageID k; + uintptr x, i; + runtime·printf("runtime:greyobject: checkmarks finds unexpected unmarked object obj=%p, mbits->bits=%x, *mbits->bitp=%x\n", obj, mbits->bits, *mbits->bitp); + + k = (uintptr)obj>>PageShift; + x = k; + x -= (uintptr)runtime·mheap.arena_start>>PageShift; + s = runtime·mheap.spans[x]; + runtime·printf("runtime:greyobject Span: 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, s->sizeclass=%d, s->elemsize=%D \n", s->start*PageSize, s->limit, s->state, s->sizeclass, s->elemsize); + for(i=0; isizeclass; i++) { + runtime·printf(" ((uintptr*)obj)[%D]=%p\n", i, ((uintptr*)obj)[i]); + } + } runtime·throw("checkmark found unmarked object"); } if(ischeckmarked(mbits)) diff --git a/src/runtime/os_darwin.c b/src/runtime/os_darwin.c index bbd29282b..b866863d0 100644 --- a/src/runtime/os_darwin.c +++ b/src/runtime/os_darwin.c @@ -135,7 +135,10 @@ void runtime·mpreinit(M *mp) { mp->gsignal = runtime·malg(32*1024); // OS X wants >=8K, Linux >=2K + runtime·writebarrierptr_nostore(&mp->gsignal, mp->gsignal); + mp->gsignal->m = mp; + runtime·writebarrierptr_nostore(&mp->gsignal->m, mp->gsignal->m); } // Called to initialize a new m (including the bootstrap m). diff --git a/src/runtime/os_dragonfly.c b/src/runtime/os_dragonfly.c index e372205ec..051192ad3 100644 --- a/src/runtime/os_dragonfly.c +++ b/src/runtime/os_dragonfly.c @@ -195,7 +195,10 @@ void runtime·mpreinit(M *mp) { mp->gsignal = runtime·malg(32*1024); + runtime·writebarrierptr_nostore(&mp->gsignal, mp->gsignal); + mp->gsignal->m = mp; + runtime·writebarrierptr_nostore(&mp->gsignal->m, mp->gsignal->m); } // Called to initialize a new m (including the bootstrap m). diff --git a/src/runtime/os_freebsd.c b/src/runtime/os_freebsd.c index a513cb604..1c126547a 100644 --- a/src/runtime/os_freebsd.c +++ b/src/runtime/os_freebsd.c @@ -203,7 +203,10 @@ void runtime·mpreinit(M *mp) { mp->gsignal = runtime·malg(32*1024); + runtime·writebarrierptr_nostore(&mp->gsignal, mp->gsignal); + mp->gsignal->m = mp; + runtime·writebarrierptr_nostore(&mp->gsignal->m, mp->gsignal->m); } // Called to initialize a new m (including the bootstrap m). diff --git a/src/runtime/os_linux.c b/src/runtime/os_linux.c index 9bd123d59..cc23774e3 100644 --- a/src/runtime/os_linux.c +++ b/src/runtime/os_linux.c @@ -233,7 +233,10 @@ void runtime·mpreinit(M *mp) { mp->gsignal = runtime·malg(32*1024); // OS X wants >=8K, Linux >=2K + runtime·writebarrierptr_nostore(&mp->gsignal, mp->gsignal); + mp->gsignal->m = mp; + runtime·writebarrierptr_nostore(&mp->gsignal->m, mp->gsignal->m); } // Called to initialize a new m (including the bootstrap m). diff --git a/src/runtime/os_nacl.c b/src/runtime/os_nacl.c index 14b558303..ad72cc7c6 100644 --- a/src/runtime/os_nacl.c +++ b/src/runtime/os_nacl.c @@ -20,7 +20,10 @@ void runtime·mpreinit(M *mp) { mp->gsignal = runtime·malg(32*1024); // OS X wants >=8K, Linux >=2K + runtime·writebarrierptr_nostore(&mp->gsignal, mp->gsignal); + mp->gsignal->m = mp; + runtime·writebarrierptr_nostore(&mp->gsignal->m, mp->gsignal->m); } // Called to initialize a new m (including the bootstrap m). diff --git a/src/runtime/os_netbsd.c b/src/runtime/os_netbsd.c index 58e5bedf2..28929ea57 100644 --- a/src/runtime/os_netbsd.c +++ b/src/runtime/os_netbsd.c @@ -271,7 +271,10 @@ void runtime·mpreinit(M *mp) { mp->gsignal = runtime·malg(32*1024); + runtime·writebarrierptr_nostore(&mp->gsignal, mp->gsignal); + mp->gsignal->m = mp; + runtime·writebarrierptr_nostore(&mp->gsignal->m, mp->gsignal->m); } // Called to initialize a new m (including the bootstrap m). diff --git a/src/runtime/os_openbsd.c b/src/runtime/os_openbsd.c index eebaa13ee..960aaffff 100644 --- a/src/runtime/os_openbsd.c +++ b/src/runtime/os_openbsd.c @@ -217,7 +217,10 @@ void runtime·mpreinit(M *mp) { mp->gsignal = runtime·malg(32*1024); + runtime·writebarrierptr_nostore(&mp->gsignal, mp->gsignal); + mp->gsignal->m = mp; + runtime·writebarrierptr_nostore(&mp->gsignal->m, mp->gsignal->m); } // Called to initialize a new m (including the bootstrap m). diff --git a/src/runtime/os_plan9.c b/src/runtime/os_plan9.c index f8c543f6f..18460fc12 100644 --- a/src/runtime/os_plan9.c +++ b/src/runtime/os_plan9.c @@ -20,12 +20,18 @@ runtime·mpreinit(M *mp) { // Initialize stack and goroutine for note handling. mp->gsignal = runtime·malg(32*1024); + runtime·writebarrierptr_nostore(&mp->gsignal, mp->gsignal); + mp->gsignal->m = mp; + runtime·writebarrierptr_nostore(&mp->gsignal->m, mp->gsignal->m); + mp->notesig = (int8*)runtime·mallocgc(ERRMAX*sizeof(int8), nil, FlagNoScan); + runtime·writebarrierptr_nostore(&mp->notesig, mp->notesig); // Initialize stack for handling strings from the // errstr system call, as used in package syscall. mp->errstr = (byte*)runtime·mallocgc(ERRMAX*sizeof(byte), nil, FlagNoScan); + runtime·writebarrierptr_nostore(&mp->errstr, mp->errstr); } // Called to initialize a new m (including the bootstrap m). diff --git a/src/runtime/os_solaris.c b/src/runtime/os_solaris.c index e16b8e637..bee91d8e6 100644 --- a/src/runtime/os_solaris.c +++ b/src/runtime/os_solaris.c @@ -176,7 +176,10 @@ void runtime·mpreinit(M *mp) { mp->gsignal = runtime·malg(32*1024); + runtime·writebarrierptr_nostore(&mp->gsignal, mp->gsignal); + mp->gsignal->m = mp; + runtime·writebarrierptr_nostore(&mp->gsignal->m, mp->gsignal->m); } // Called to initialize a new m (including the bootstrap m). diff --git a/src/runtime/proc.c b/src/runtime/proc.c index e5e2df2e4..c1df40d02 100644 --- a/src/runtime/proc.c +++ b/src/runtime/proc.c @@ -876,7 +876,9 @@ runtime·allocm(P *p) mp->g0 = runtime·malg(-1); else mp->g0 = runtime·malg(8192); + runtime·writebarrierptr_nostore(&mp->g0, mp->g0); mp->g0->m = mp; + runtime·writebarrierptr_nostore(&mp->g0->m, mp->g0->m); if(p == g->m->p) releasep(); -- cgit v1.2.1 From 1e210ecf449d3b518aa000891559321ce61a62da Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Thu, 20 Nov 2014 12:08:13 -0500 Subject: [dev.garbage] runtime: Turn concurrent GC on by default. Avoid write barriers for GC internal structures such as free lists. LGTM=rsc R=rsc CC=golang-codereviews, rsc https://codereview.appspot.com/179000043 --- src/runtime/heapdump.go | 4 ++-- src/runtime/malloc.go | 14 +++++++------- src/runtime/malloc2.go | 39 ++++++++++++++++++++++++++++++++------- src/runtime/mcache.go | 4 ++-- src/runtime/mcentral.go | 30 +++++++++++++++++------------- src/runtime/mgc.go | 20 +++++++++++++------- src/runtime/mheap.go | 6 +++--- src/runtime/stack1.go | 44 ++++++++++++++++++++++---------------------- 8 files changed, 98 insertions(+), 63 deletions(-) (limited to 'src') diff --git a/src/runtime/heapdump.go b/src/runtime/heapdump.go index c942e0163..c6f97025f 100644 --- a/src/runtime/heapdump.go +++ b/src/runtime/heapdump.go @@ -464,8 +464,8 @@ func dumpobjs() { if n > uintptr(len(freemark)) { gothrow("freemark array doesn't have enough entries") } - for l := s.freelist; l != nil; l = l.next { - freemark[(uintptr(unsafe.Pointer(l))-p)/size] = true + for l := s.freelist; l.ptr() != nil; l = l.ptr().next { + freemark[(uintptr(l)-p)/size] = true } for j := uintptr(0); j < n; j, p = j+1, p+size { if freemark[j] { diff --git a/src/runtime/malloc.go b/src/runtime/malloc.go index f90a8f84a..86e20b249 100644 --- a/src/runtime/malloc.go +++ b/src/runtime/malloc.go @@ -140,14 +140,14 @@ func mallocgc(size uintptr, typ *_type, flags uint32) unsafe.Pointer { // Allocate a new maxTinySize block. s = c.alloc[tinySizeClass] v := s.freelist - if v == nil { + if v.ptr() == nil { systemstack(func() { mCache_Refill(c, tinySizeClass) }) s = c.alloc[tinySizeClass] v = s.freelist } - s.freelist = v.next + s.freelist = v.ptr().next s.ref++ //TODO: prefetch v.next x = unsafe.Pointer(v) @@ -170,19 +170,19 @@ func mallocgc(size uintptr, typ *_type, flags uint32) unsafe.Pointer { size = uintptr(class_to_size[sizeclass]) s = c.alloc[sizeclass] v := s.freelist - if v == nil { + if v.ptr() == nil { systemstack(func() { mCache_Refill(c, int32(sizeclass)) }) s = c.alloc[sizeclass] v = s.freelist } - s.freelist = v.next + s.freelist = v.ptr().next s.ref++ //TODO: prefetch x = unsafe.Pointer(v) if flags&flagNoZero == 0 { - v.next = nil + v.ptr().next = 0 if size > 2*ptrSize && ((*[2]uintptr)(x))[1] != 0 { memclr(unsafe.Pointer(v), size) } @@ -341,7 +341,7 @@ marked: } } - if memstats.heap_alloc >= memstats.next_gc { + if memstats.heap_alloc >= memstats.next_gc/2 { gogc(0) } @@ -475,7 +475,7 @@ func gogc(force int32) { systemstack(stoptheworld) systemstack(finishsweep_m) // finish sweep before we start concurrent scan. - if false { // To turn on concurrent scan and mark set to true... + if true { // To turn on concurrent scan and mark set to true... systemstack(starttheworld) // Do a concurrent heap scan before we stop the world. systemstack(gcscan_m) diff --git a/src/runtime/malloc2.go b/src/runtime/malloc2.go index 4ac0207b1..511638d3d 100644 --- a/src/runtime/malloc2.go +++ b/src/runtime/malloc2.go @@ -139,10 +139,35 @@ const ( ) // A generic linked list of blocks. (Typically the block is bigger than sizeof(MLink).) +// Since assignments to mlink.next will result in a write barrier being preformed +// this can not be used by some of the internal GC structures. For example when +// the sweeper is placing an unmarked object on the free list it does not want the +// write barrier to be called since that could result in the object being reachable. type mlink struct { next *mlink } +// A gclink is a node in a linked list of blocks, like mlink, +// but it is opaque to the garbage collector. +// The GC does not trace the pointers during collection, +// and the compiler does not emit write barriers for assignments +// of gclinkptr values. Code should store references to gclinks +// as gclinkptr, not as *gclink. +type gclink struct { + next gclinkptr +} + +// A gclinkptr is a pointer to a gclink, but it is opaque +// to the garbage collector. +type gclinkptr uintptr + +// ptr returns the *gclink form of p. +// The result should be used for accessing fields, not stored +// in other data structures. +func (p gclinkptr) ptr() *gclink { + return (*gclink)(unsafe.Pointer(p)) +} + // sysAlloc obtains a large chunk of zeroed memory from the // operating system, typically on the order of a hundred kilobytes // or a megabyte. @@ -275,8 +300,8 @@ type mcachelist struct { } type stackfreelist struct { - list *mlink // linked list of free stacks - size uintptr // total size of stacks in list + list gclinkptr // linked list of free stacks + size uintptr // total size of stacks in list } // Per-thread (in Go, per-P) cache for small objects. @@ -346,11 +371,11 @@ const ( ) type mspan struct { - next *mspan // in a span linked list - prev *mspan // in a span linked list - start pageID // starting page number - npages uintptr // number of pages in span - freelist *mlink // list of free objects + next *mspan // in a span linked list + prev *mspan // in a span linked list + start pageID // starting page number + npages uintptr // number of pages in span + freelist gclinkptr // list of free objects // sweep generation: // if sweepgen == h->sweepgen - 2, the span needs sweeping // if sweepgen == h->sweepgen - 1, the span is currently being swept diff --git a/src/runtime/mcache.go b/src/runtime/mcache.go index 08b1bc359..f8389c5cb 100644 --- a/src/runtime/mcache.go +++ b/src/runtime/mcache.go @@ -59,7 +59,7 @@ func mCache_Refill(c *mcache, sizeclass int32) *mspan { _g_.m.locks++ // Return the current cached span to the central lists. s := c.alloc[sizeclass] - if s.freelist != nil { + if s.freelist.ptr() != nil { gothrow("refill on a nonempty span") } if s != &emptymspan { @@ -71,7 +71,7 @@ func mCache_Refill(c *mcache, sizeclass int32) *mspan { if s == nil { gothrow("out of memory") } - if s.freelist == nil { + if s.freelist.ptr() == nil { println(s.ref, (s.npages<<_PageShift)/s.elemsize) gothrow("empty span") } diff --git a/src/runtime/mcentral.go b/src/runtime/mcentral.go index 0d172a08b..ae5c6f1d5 100644 --- a/src/runtime/mcentral.go +++ b/src/runtime/mcentral.go @@ -55,7 +55,7 @@ retry: mSpanList_InsertBack(&c.empty, s) unlock(&c.lock) mSpan_Sweep(s, true) - if s.freelist != nil { + if s.freelist.ptr() != nil { goto havespan } lock(&c.lock) @@ -90,7 +90,7 @@ havespan: if n == 0 { gothrow("empty span") } - if s.freelist == nil { + if s.freelist.ptr() == nil { gothrow("freelist empty") } s.incache = true @@ -122,14 +122,14 @@ func mCentral_UncacheSpan(c *mcentral, s *mspan) { // the latest generation. // If preserve=true, don't return the span to heap nor relink in MCentral lists; // caller takes care of it. -func mCentral_FreeSpan(c *mcentral, s *mspan, n int32, start *mlink, end *mlink, preserve bool) bool { +func mCentral_FreeSpan(c *mcentral, s *mspan, n int32, start gclinkptr, end gclinkptr, preserve bool) bool { if s.incache { gothrow("freespan into cached span") } // Add the objects back to s's free list. - wasempty := s.freelist == nil - end.next = s.freelist + wasempty := s.freelist.ptr() == nil + end.ptr().next = s.freelist s.freelist = start s.ref -= uint16(n) @@ -165,7 +165,7 @@ func mCentral_FreeSpan(c *mcentral, s *mspan, n int32, start *mlink, end *mlink, // s is completely freed, return it to the heap. mSpanList_Remove(s) s.needzero = 1 - s.freelist = nil + s.freelist = 0 unlock(&c.lock) unmarkspan(uintptr(s.start)<<_PageShift, s.npages<<_PageShift) mHeap_Free(&mheap_, s, 0) @@ -183,17 +183,21 @@ func mCentral_Grow(c *mcentral) *mspan { return nil } - // Carve span into sequence of blocks. - tailp := &s.freelist p := uintptr(s.start << _PageShift) s.limit = p + size*n - for i := uintptr(0); i < n; i++ { - v := (*mlink)(unsafe.Pointer(p)) - *tailp = v - tailp = &v.next + head := gclinkptr(p) + tail := gclinkptr(p) + // i==0 iteration already done + for i := uintptr(1); i < n; i++ { p += size + tail.ptr().next = gclinkptr(p) + tail = gclinkptr(p) } - *tailp = nil + if s.freelist.ptr() != nil { + gothrow("freelist not empty") + } + tail.ptr().next = 0 + s.freelist = head markspan(unsafe.Pointer(uintptr(s.start)<<_PageShift), size, n, size*n < s.npages<<_PageShift) return s } diff --git a/src/runtime/mgc.go b/src/runtime/mgc.go index 57bd8b356..0bf618d06 100644 --- a/src/runtime/mgc.go +++ b/src/runtime/mgc.go @@ -312,7 +312,7 @@ func objectstart(b uintptr, mbits *markbits) uintptr { p = p + idx*size } if p == obj { - print("runtime: failed to find block beginning for ", hex(p), " s=", hex(s.start*_PageSize), " s.limit=", s.limit, "\n") + print("runtime: failed to find block beginning for ", hex(p), " s=", hex(s.start*_PageSize), " s.limit=", hex(s.limit), "\n") gothrow("failed to find block beginning") } obj = p @@ -1201,13 +1201,14 @@ func mSpan_Sweep(s *mspan, preserve bool) bool { } res := false nfree := 0 - var head mlink - end := &head + + var head, end gclinkptr + c := _g_.m.mcache sweepgenset := false // Mark any free objects in this span so we don't collect them. - for link := s.freelist; link != nil; link = link.next { + for link := s.freelist; link.ptr() != nil; link = link.ptr().next { off := (uintptr(unsafe.Pointer(link)) - arena_start) / ptrSize bitp := arena_start - off/wordsPerBitmapByte - 1 shift := (off % wordsPerBitmapByte) * gcBits @@ -1328,8 +1329,13 @@ func mSpan_Sweep(s *mspan, preserve bool) bool { } else if size > ptrSize { *(*uintptr)(unsafe.Pointer(p + ptrSize)) = 0 } - end.next = (*mlink)(unsafe.Pointer(p)) - end = end.next + if head.ptr() == nil { + head = gclinkptr(p) + } else { + end.ptr().next = gclinkptr(p) + } + end = gclinkptr(p) + end.ptr().next = gclinkptr(0xbaddadae5) nfree++ } } @@ -1352,7 +1358,7 @@ func mSpan_Sweep(s *mspan, preserve bool) bool { c.local_nsmallfree[cl] += uintptr(nfree) c.local_cachealloc -= intptr(uintptr(nfree) * size) xadd64(&memstats.next_gc, -int64(nfree)*int64(size)*int64(gcpercent+100)/100) - res = mCentral_FreeSpan(&mheap_.central[cl].mcentral, s, int32(nfree), head.next, end, preserve) + res = mCentral_FreeSpan(&mheap_.central[cl].mcentral, s, int32(nfree), head, end, preserve) // MCentral_FreeSpan updates sweepgen } return res diff --git a/src/runtime/mheap.go b/src/runtime/mheap.go index fedcd69c5..30205d68d 100644 --- a/src/runtime/mheap.go +++ b/src/runtime/mheap.go @@ -196,7 +196,7 @@ func mHeap_Alloc_m(h *mheap, npage uintptr, sizeclass int32, large bool) *mspan // able to map interior pointer to containing span. atomicstore(&s.sweepgen, h.sweepgen) s.state = _MSpanInUse - s.freelist = nil + s.freelist = 0 s.ref = 0 s.sizeclass = uint8(sizeclass) if sizeclass == 0 { @@ -248,7 +248,7 @@ func mHeap_AllocStack(h *mheap, npage uintptr) *mspan { s := mHeap_AllocSpanLocked(h, npage) if s != nil { s.state = _MSpanStack - s.freelist = nil + s.freelist = 0 s.ref = 0 memstats.stacks_inuse += uint64(s.npages << _PageShift) } @@ -571,7 +571,7 @@ func mSpan_Init(span *mspan, start pageID, npages uintptr) { span.prev = nil span.start = start span.npages = npages - span.freelist = nil + span.freelist = 0 span.ref = 0 span.sizeclass = 0 span.incache = false diff --git a/src/runtime/stack1.go b/src/runtime/stack1.go index 963f4fa73..78bcccc41 100644 --- a/src/runtime/stack1.go +++ b/src/runtime/stack1.go @@ -58,7 +58,7 @@ func stackinit() { // Allocates a stack from the free pool. Must be called with // stackpoolmu held. -func stackpoolalloc(order uint8) *mlink { +func stackpoolalloc(order uint8) gclinkptr { list := &stackpool[order] s := list.next if s == list { @@ -70,23 +70,23 @@ func stackpoolalloc(order uint8) *mlink { if s.ref != 0 { gothrow("bad ref") } - if s.freelist != nil { + if s.freelist.ptr() != nil { gothrow("bad freelist") } for i := uintptr(0); i < _StackCacheSize; i += _FixedStack << order { - x := (*mlink)(unsafe.Pointer(uintptr(s.start)<<_PageShift + i)) - x.next = s.freelist + x := gclinkptr(uintptr(s.start)<<_PageShift + i) + x.ptr().next = s.freelist s.freelist = x } mSpanList_Insert(list, s) } x := s.freelist - if x == nil { + if x.ptr() == nil { gothrow("span has no free stacks") } - s.freelist = x.next + s.freelist = x.ptr().next s.ref++ - if s.freelist == nil { + if s.freelist.ptr() == nil { // all stacks in s are allocated. mSpanList_Remove(s) } @@ -94,22 +94,22 @@ func stackpoolalloc(order uint8) *mlink { } // Adds stack x to the free pool. Must be called with stackpoolmu held. -func stackpoolfree(x *mlink, order uint8) { +func stackpoolfree(x gclinkptr, order uint8) { s := mHeap_Lookup(&mheap_, (unsafe.Pointer)(x)) if s.state != _MSpanStack { gothrow("freeing stack not in a stack span") } - if s.freelist == nil { + if s.freelist.ptr() == nil { // s will now have a free stack mSpanList_Insert(&stackpool[order], s) } - x.next = s.freelist + x.ptr().next = s.freelist s.freelist = x s.ref-- if s.ref == 0 { // span is completely free - return to heap mSpanList_Remove(s) - s.freelist = nil + s.freelist = 0 mHeap_FreeStack(&mheap_, s) } } @@ -123,12 +123,12 @@ func stackcacherefill(c *mcache, order uint8) { // Grab some stacks from the global cache. // Grab half of the allowed capacity (to prevent thrashing). - var list *mlink + var list gclinkptr var size uintptr lock(&stackpoolmu) for size < _StackCacheSize/2 { x := stackpoolalloc(order) - x.next = list + x.ptr().next = list list = x size += _FixedStack << order } @@ -145,7 +145,7 @@ func stackcacherelease(c *mcache, order uint8) { size := c.stackcache[order].size lock(&stackpoolmu) for size > _StackCacheSize/2 { - y := x.next + y := x.ptr().next stackpoolfree(x, order) x = y size -= _FixedStack << order @@ -162,12 +162,12 @@ func stackcache_clear(c *mcache) { lock(&stackpoolmu) for order := uint8(0); order < _NumStackOrders; order++ { x := c.stackcache[order].list - for x != nil { - y := x.next + for x.ptr() != nil { + y := x.ptr().next stackpoolfree(x, order) x = y } - c.stackcache[order].list = nil + c.stackcache[order].list = 0 c.stackcache[order].size = 0 } unlock(&stackpoolmu) @@ -207,7 +207,7 @@ func stackalloc(n uint32) stack { order++ n2 >>= 1 } - var x *mlink + var x gclinkptr c := thisg.m.mcache if c == nil || thisg.m.gcing != 0 || thisg.m.helpgc != 0 { // c == nil can happen in the guts of exitsyscall or @@ -219,11 +219,11 @@ func stackalloc(n uint32) stack { unlock(&stackpoolmu) } else { x = c.stackcache[order].list - if x == nil { + if x.ptr() == nil { stackcacherefill(c, order) x = c.stackcache[order].list } - c.stackcache[order].list = x.next + c.stackcache[order].list = x.ptr().next c.stackcache[order].size -= uintptr(n) } v = (unsafe.Pointer)(x) @@ -270,7 +270,7 @@ func stackfree(stk stack) { order++ n2 >>= 1 } - x := (*mlink)(v) + x := gclinkptr(v) c := gp.m.mcache if c == nil || gp.m.gcing != 0 || gp.m.helpgc != 0 { lock(&stackpoolmu) @@ -280,7 +280,7 @@ func stackfree(stk stack) { if c.stackcache[order].size >= _StackCacheSize { stackcacherelease(c, order) } - x.next = c.stackcache[order].list + x.ptr().next = c.stackcache[order].list c.stackcache[order].list = x c.stackcache[order].size += n } -- cgit v1.2.1 From f391841fde69c09b23dc2607904dd2af2425c692 Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Thu, 20 Nov 2014 14:24:01 -0500 Subject: [dev.garbage] runtime: Fix constant overflow on 32 bit machines LGTM=rsc R=golang-codereviews CC=golang-codereviews, rsc https://codereview.appspot.com/180040043 --- src/runtime/mgc.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src') diff --git a/src/runtime/mgc.go b/src/runtime/mgc.go index 0bf618d06..5b0c9b990 100644 --- a/src/runtime/mgc.go +++ b/src/runtime/mgc.go @@ -1335,7 +1335,7 @@ func mSpan_Sweep(s *mspan, preserve bool) bool { end.ptr().next = gclinkptr(p) } end = gclinkptr(p) - end.ptr().next = gclinkptr(0xbaddadae5) + end.ptr().next = gclinkptr(0x0bade5) nfree++ } } -- cgit v1.2.1 From a1d2955f5ee5d3e170b9b784baf46c79e0740320 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Fri, 21 Nov 2014 15:57:10 -0500 Subject: [dev.garbage] runtime: add prefetcht0, prefetcht1, prefetcht2, prefetcht3, prefetchnta for GC We don't know what we need yet, so add them all. Add them even on x86 architectures (as no-ops) so that the GC can refer to them unconditionally. Eventually we'll know what we want and probably have just one 'prefetch' with an appropriate meaning on each architecture. LGTM=rlh R=rlh CC=golang-codereviews https://codereview.appspot.com/179160043 --- src/runtime/asm_386.s | 20 ++++++++++++++++++++ src/runtime/asm_amd64.s | 20 ++++++++++++++++++++ src/runtime/asm_amd64p32.s | 21 +++++++++++++++++++++ src/runtime/asm_arm.s | 12 ++++++++++++ src/runtime/asm_power64x.s | 12 ++++++++++++ src/runtime/runtime1.go | 5 ++++- src/runtime/stubs.go | 5 +++++ 7 files changed, 94 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/runtime/asm_386.s b/src/runtime/asm_386.s index a02bb5556..7cc64a3a4 100644 --- a/src/runtime/asm_386.s +++ b/src/runtime/asm_386.s @@ -2285,3 +2285,23 @@ TEXT runtime·getg(SB),NOSPLIT,$0-4 MOVL AX, ret+0(FP) RET +TEXT runtime·prefetcht0(SB),NOSPLIT,$0-4 + MOVL addr+0(FP), AX + PREFETCHT0 (AX) + RET + +TEXT runtime·prefetcht1(SB),NOSPLIT,$0-4 + MOVL addr+0(FP), AX + PREFETCHT1 (AX) + RET + + +TEXT runtime·prefetcht2(SB),NOSPLIT,$0-4 + MOVL addr+0(FP), AX + PREFETCHT2 (AX) + RET + +TEXT runtime·prefetchnta(SB),NOSPLIT,$0-4 + MOVL addr+0(FP), AX + PREFETCHNTA (AX) + RET diff --git a/src/runtime/asm_amd64.s b/src/runtime/asm_amd64.s index 6e3f5ff6c..14be2fe92 100644 --- a/src/runtime/asm_amd64.s +++ b/src/runtime/asm_amd64.s @@ -2228,3 +2228,23 @@ TEXT runtime·getg(SB),NOSPLIT,$0-8 MOVQ g(CX), AX MOVQ AX, ret+0(FP) RET + +TEXT runtime·prefetcht0(SB),NOSPLIT,$0-8 + MOVQ addr+0(FP), AX + PREFETCHT0 (AX) + RET + +TEXT runtime·prefetcht1(SB),NOSPLIT,$0-8 + MOVQ addr+0(FP), AX + PREFETCHT1 (AX) + RET + +TEXT runtime·prefetcht2(SB),NOSPLIT,$0-8 + MOVQ addr+0(FP), AX + PREFETCHT2 (AX) + RET + +TEXT runtime·prefetchnta(SB),NOSPLIT,$0-8 + MOVQ addr+0(FP), AX + PREFETCHNTA (AX) + RET diff --git a/src/runtime/asm_amd64p32.s b/src/runtime/asm_amd64p32.s index cead3cd07..60c438c1d 100644 --- a/src/runtime/asm_amd64p32.s +++ b/src/runtime/asm_amd64p32.s @@ -1079,3 +1079,24 @@ TEXT runtime·getg(SB),NOSPLIT,$0-4 MOVL g(CX), AX MOVL AX, ret+0(FP) RET + +TEXT runtime·prefetcht0(SB),NOSPLIT,$0-4 + MOVL addr+0(FP), AX + PREFETCHT0 (AX) + RET + +TEXT runtime·prefetcht1(SB),NOSPLIT,$0-4 + MOVL addr+0(FP), AX + PREFETCHT1 (AX) + RET + + +TEXT runtime·prefetcht2(SB),NOSPLIT,$0-4 + MOVL addr+0(FP), AX + PREFETCHT2 (AX) + RET + +TEXT runtime·prefetchnta(SB),NOSPLIT,$0-4 + MOVL addr+0(FP), AX + PREFETCHNTA (AX) + RET diff --git a/src/runtime/asm_arm.s b/src/runtime/asm_arm.s index 583c7ba50..c6c98b443 100644 --- a/src/runtime/asm_arm.s +++ b/src/runtime/asm_arm.s @@ -1320,3 +1320,15 @@ TEXT runtime·goexit(SB),NOSPLIT,$-4-0 TEXT runtime·getg(SB),NOSPLIT,$-4-4 MOVW g, ret+0(FP) RET + +TEXT runtime·prefetcht0(SB),NOSPLIT,$0-4 + RET + +TEXT runtime·prefetcht1(SB),NOSPLIT,$0-4 + RET + +TEXT runtime·prefetcht2(SB),NOSPLIT,$0-4 + RET + +TEXT runtime·prefetchnta(SB),NOSPLIT,$0-4 + RET diff --git a/src/runtime/asm_power64x.s b/src/runtime/asm_power64x.s index ba900c2b3..6169202ea 100644 --- a/src/runtime/asm_power64x.s +++ b/src/runtime/asm_power64x.s @@ -986,3 +986,15 @@ TEXT _cgo_topofstack(SB),NOSPLIT,$0 TEXT runtime·goexit(SB),NOSPLIT,$-8-0 MOVD R0, R0 // NOP BL runtime·goexit1(SB) // does not return + +TEXT runtime·prefetcht0(SB),NOSPLIT,$0-8 + RETURN + +TEXT runtime·prefetcht1(SB),NOSPLIT,$0-8 + RETURN + +TEXT runtime·prefetcht2(SB),NOSPLIT,$0-8 + RETURN + +TEXT runtime·prefetchnta(SB),NOSPLIT,$0-8 + RETURN diff --git a/src/runtime/runtime1.go b/src/runtime/runtime1.go index 15dea01a3..9e19b68be 100644 --- a/src/runtime/runtime1.go +++ b/src/runtime/runtime1.go @@ -97,7 +97,10 @@ func testAtomic64() { z64 = 42 x64 = 0 - // TODO: PREFETCH((unsafe.Pointer)(&z64)) + prefetcht0(uintptr(unsafe.Pointer(&z64))) + prefetcht1(uintptr(unsafe.Pointer(&z64))) + prefetcht2(uintptr(unsafe.Pointer(&z64))) + prefetchnta(uintptr(unsafe.Pointer(&z64))) if cas64(&z64, x64, 1) { gothrow("cas64 failed") } diff --git a/src/runtime/stubs.go b/src/runtime/stubs.go index 217307a1e..4063e5434 100644 --- a/src/runtime/stubs.go +++ b/src/runtime/stubs.go @@ -231,3 +231,8 @@ func call536870912(fn, arg unsafe.Pointer, n, retoffset uint32) func call1073741824(fn, arg unsafe.Pointer, n, retoffset uint32) func systemstack_switch() + +func prefetcht0(addr uintptr) +func prefetcht1(addr uintptr) +func prefetcht2(addr uintptr) +func prefetchnta(addr uintptr) -- cgit v1.2.1 From df7d4576f312e1b646af4f5f1a32412a4221b785 Mon Sep 17 00:00:00 2001 From: Rick Hudson Date: Fri, 21 Nov 2014 16:46:27 -0500 Subject: [dev.garbage] runtime: Stop running gs during the GCscan phase. Ensure that all gs are in a scan state when their stacks are being scanned. LGTM=rsc R=rsc CC=golang-codereviews https://codereview.appspot.com/179160044 --- src/runtime/mgc.go | 13 +++++-------- src/runtime/proc1.go | 11 ++++------- src/runtime/stack1.go | 5 +++++ 3 files changed, 14 insertions(+), 15 deletions(-) (limited to 'src') diff --git a/src/runtime/mgc.go b/src/runtime/mgc.go index 5b0c9b990..a13de0488 100644 --- a/src/runtime/mgc.go +++ b/src/runtime/mgc.go @@ -923,14 +923,11 @@ func scanframe(frame *stkframe, unused unsafe.Pointer) bool { } func scanstack(gp *g) { - // TODO(rsc): Due to a precedence error, this was never checked in the original C version. - // If you enable the check, the gothrow happens. - /* - if readgstatus(gp)&_Gscan == 0 { - print("runtime: gp=", gp, ", goid=", gp.goid, ", gp->atomicstatus=", readgstatus(gp), "\n") - gothrow("mark - bad status") - } - */ + + if readgstatus(gp)&_Gscan == 0 { + print("runtime:scanstack: gp=", gp, ", goid=", gp.goid, ", gp->atomicstatus=", hex(readgstatus(gp)), "\n") + gothrow("scanstack - bad status") + } switch readgstatus(gp) &^ _Gscan { default: diff --git a/src/runtime/proc1.go b/src/runtime/proc1.go index 8c941dd35..be01f2671 100644 --- a/src/runtime/proc1.go +++ b/src/runtime/proc1.go @@ -316,6 +316,10 @@ func casfrom_Gscanstatus(gp *g, oldval, newval uint32) { // Check that transition is valid. switch oldval { + default: + print("runtime: casfrom_Gscanstatus bad oldval gp=", gp, ", oldval=", hex(oldval), ", newval=", hex(newval), "\n") + dumpgstatus(gp) + gothrow("casfrom_Gscanstatus:top gp->status is not in scan state") case _Gscanrunnable, _Gscanwaiting, _Gscanrunning, @@ -417,13 +421,6 @@ func stopg(gp *g) bool { return false case _Grunning: - if gcphase == _GCscan { - // Running routines not scanned during - // GCscan phase, we only scan non-running routines. - gp.gcworkdone = true - return false - } - // Claim goroutine, so we aren't racing with a status // transition away from Grunning. if !castogscanstatus(gp, _Grunning, _Gscanrunning) { diff --git a/src/runtime/stack1.go b/src/runtime/stack1.go index 78bcccc41..57d0f8c65 100644 --- a/src/runtime/stack1.go +++ b/src/runtime/stack1.go @@ -682,7 +682,12 @@ func newstack() { gothrow("runtime: g is running but p is not") } if gp.preemptscan { + for !castogscanstatus(gp, _Gwaiting, _Gscanwaiting) { + // Likely to be racing with the GC as it sees a _Gwaiting and does the stack scan. + // If so this stack will be scanned twice which does not change correctness. + } gcphasework(gp) + casfrom_Gscanstatus(gp, _Gscanwaiting, _Gwaiting) casgstatus(gp, _Gwaiting, _Grunning) gp.stackguard0 = gp.stack.lo + _StackGuard gp.preempt = false -- cgit v1.2.1