code review 5279048: runtime: faster and more scalable GC

src/pkg/runtime/mgc0.c

 // Copyright 2009 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.
 
 // Garbage collector.
 
 #include "runtime.h"
-#include "arch.h"
+#include "arch_GOARCH.h"
 #include "malloc.h"
 #include "stack.h"
 
 enum {
         Debug = 0,
         PtrSize = sizeof(void*),
         DebugMark = 0,  // run second pass to check mark
         DataBlock = 8*1024,
 
         // Four bits per word (see #defines below).
@@ skipping 27 matching lines @@
 //      /* then test bits & bitAllocated, bits & bitMarked, etc. */
 //
 #define bitAllocated            ((uintptr)1<<(bitShift*0))
 #define bitNoPointers           ((uintptr)1<<(bitShift*1))      /* when bitAllocated is set */
 #define bitMarked               ((uintptr)1<<(bitShift*2))      /* when bitAllocated is set */
 #define bitSpecial              ((uintptr)1<<(bitShift*3))      /* when bitAllocated is set - has finalizer or being profiled */
 #define bitBlockBoundary        ((uintptr)1<<(bitShift*1))      /* when bitAllocated is NOT set */
 
 #define bitMask (bitBlockBoundary | bitAllocated | bitMarked | bitSpecial)
 
+// Holding worldsema grants an M the right to try to stop the world.
+// The procedure is:
+//
+//      runtime·semacquire(&runtime·worldsema);
+//      m->gcing = 1;
+//      runtime·stoptheworld();
+//
+//      ... do stuff ...
+//
+//      m->gcing = 0;
+//      runtime·semrelease(&runtime·worldsema);
+//      runtime·starttheworld();
+//
+uint32 runtime·worldsema = 1;
 static int32 gctrace;
 
 typedef struct Workbuf Workbuf;
 struct Workbuf
 {
         Workbuf *next;
         uintptr pushcnt;
         uintptr nobj;
         byte *obj[512-3];
 };
@@ skipping 10 matching lines @@
 struct FinBlock
 {
         FinBlock *alllink;
         FinBlock *next;
         int32 cnt;
         int32 cap;
         Finalizer fin[1];
 };
 
 extern byte data[];
-extern byte end[];
+extern byte etext[];
+extern byte ebss[];
 
 static G *fing;
 static FinBlock *finq; // list of finalizers that are to be executed
 static FinBlock *finc; // cache of free blocks
 static FinBlock *allfin; // list of all blocks
 static Lock finlock;
 static int32 fingwait;
 
 static void runfinq(void);
 static Workbuf* getempty(Workbuf*);
@@ skipping 158 matching lines @@
                                 if(((xbits>>j) & (bitAllocated|bitBlockBoundary)) != 0) {
                                         obj = (byte*)obj - (shift-j)*PtrSize;
                                         shift = j;
                                         bits = xbits>>shift;
                                         goto found;
                                 }
                         }
 
                         // Otherwise consult span table to find beginning.
                         // (Manually inlined copy of MHeap_LookupMaybe.)
-                        m->gcstats.naddrlookup++;
                         k = (uintptr)obj>>PageShift;
                         x = k;
                         if(sizeof(void*) == 8)
                                 x -= (uintptr)arena_start>>PageShift;
                         s = runtime·mheap.map[x];
                         if(s == nil || k < s->start || k - s->start >= s->npages || s->state != MSpanInUse)
                                 continue;
                         p =  (byte*)((uintptr)s->start<<PageShift);
                         if(s->sizeclass == 0) {
                                 obj = p;
@@ skipping 70 matching lines @@
                         // Emptied our buffer: refill.
                         wbuf = getfull(wbuf);
                         if(wbuf == nil)
                                 return;
                         nobj = wbuf->nobj;
                         wp = wbuf->obj + wbuf->nobj;
                 }
                 b = *--wp;
                 nobj--;
 
-                // Figure out n = size of b.  Start by loading bits for b.
-                off = (uintptr*)b - (uintptr*)arena_start;
-                bitp = (uintptr*)arena_start - off/wordsPerBitmapWord - 1;
-                shift = off % wordsPerBitmapWord;
-                xbits = *bitp;
-                bits = xbits >> shift;
-
-                // Might be small; look for nearby block boundary.
-                // A block boundary is marked by either bitBlockBoundary
-                // or bitAllocated being set (see notes near their definition).
-                enum {
-                        boundary = bitBlockBoundary|bitAllocated
-                };
-                // Look for a block boundary both after and before b
-                // in the same bitmap word.
-                //
-                // A block boundary j words after b is indicated by
-                //      bits>>j & boundary
-                // assuming shift+j < bitShift.  (If shift+j >= bitShift then
-                // we'll be bleeding other bit types like bitMarked into our test.)
-                // Instead of inserting the conditional shift+j < bitShift into the loop,
-                // we can let j range from 1 to bitShift as long as we first
-                // apply a mask to keep only the bits corresponding
-                // to shift+j < bitShift aka j < bitShift-shift.
-                bits &= (boundary<<(bitShift-shift)) - boundary;
-
-                // A block boundary j words before b is indicated by
-                //      xbits>>(shift-j) & boundary
-                // (assuming shift >= j).  There is no cleverness here
-                // avoid the test, because when j gets too large the shift
-                // turns negative, which is undefined in C.
-
-                for(j=1; j<bitShift; j++) {
-                        if(((bits>>j)&boundary) != 0 || shift>=j && ((xbits>>(shift-j))&boundary) != 0) {
-                                n = j*PtrSize;
-                                goto scan;
-                        }
-                }
-
-                // Fall back to asking span about size class.
+                // Ask span about size class.
                 // (Manually inlined copy of MHeap_Lookup.)
-                m->gcstats.nsizelookup++;
                 x = (uintptr)b>>PageShift;
                 if(sizeof(void*) == 8)
                         x -= (uintptr)arena_start>>PageShift;
                 s = runtime·mheap.map[x];
                 if(s->sizeclass == 0)
                         n = s->npages<<PageShift;
                 else
                         n = runtime·class_to_size[s->sizeclass];
-        scan:;
         }
 }
 
 // debug_scanblock is the debug copy of scanblock.
 // it is simpler, slower, single-threaded, recursive,
 // and uses bitSpecial as the mark bit.
 static void
 debug_scanblock(byte *b, int64 n)
 {
         byte *obj, *p;
@@ skipping 244 matching lines @@
 
         // do not mark the finalizer block itself.  just mark the things it points at.
         addroot(v, size);
 }
 
 static void
 addroots(void)
 {
         G *gp;
         FinBlock *fb;
-        byte *p, *e;
+        byte *p;
 
         work.nroot = 0;
 
-        e = (byte*)&runtime·mheap;
-        for(p=data; p<e; p+=DataBlock)
-                addroot(p, p+DataBlock<e?DataBlock:e-p);
-
-        e = end;
-        for(p=(byte*)(&runtime·mheap+1); p<e; p+=DataBlock)
-                addroot(p, p+DataBlock<e?DataBlock:e-p);
+        // mark data+bss.
+        for(p=data; p<ebss; p+=DataBlock)
+                addroot(p, p+DataBlock<ebss?DataBlock:ebss-p);
 
         runtime·walkfintab(addfinroots);
 
         for(fb=allfin; fb; fb=fb->alllink)
                 addroot((byte*)fb->fin, fb->cnt*sizeof(fb->fin[0]));
 
         for(gp=runtime·allg; gp!=nil; gp=gp->alllink) {
                 switch(gp->status){
                         default:
                                 runtime·printf("unexpected G.status %d\n", gp->status);
@@ skipping 60 matching lines @@
         uintptr size;
         byte *p;
         MCache *c;
         byte *arena_start;
         MLink *start, *end;
         int32 nfree;
 
         USED(desc);
 
         s = runtime·mheap.allspans[spanidx];
+        // Stamp newly unused spans. The scavenger will use that
+        // info to potentially give back some pages to the OS.
+        if(s->state == MSpanFree && s->unusedsince == 0)
+                s->unusedsince = runtime·nanotime();
         if(s->state != MSpanInUse)
                 return;
 
         arena_start = runtime·mheap.arena_start;
 
         p = (byte*)(s->start << PageShift);
         cl = s->sizeclass;
         if(cl == 0) {
                 size = s->npages<<PageShift;
                 n = 1;
@@ skipping 93 matching lines @@
                         runtime·usleep(10);
         }
 
         // parallel sweep for over all spans
         parfor(&work.sweepfor);
 
         if(runtime·xadd(&work.ndone, +1) == work.nproc-1)
                 runtime·notewakeup(&work.alldone);
 }
 
-// Semaphore, not Lock, so that the goroutine
-// reschedules when there is contention rather
-// than spinning.
-static uint32 gcsema = 1;
-
 // Initialized from $GOGC.  GOGC=off means no gc.
 //
 // Next gc is after we've allocated an extra amount of
 // memory proportional to the amount already in use.
 // If gcpercent=100 and we're using 4M, we'll gc again
 // when we get to 8M.  This keeps the gc cost in linear
 // proportion to the allocation cost.  Adjusting gcpercent
 // just changes the linear constant (and also the amount of
 // extra memory used).
 static int32 gcpercent = -2;
@@ skipping 73 matching lines @@
                 else
                         gcpercent = runtime·atoi(p);
 
                 p = runtime·getenv("GOGCTRACE");
                 if(p != nil)
                         gctrace = runtime·atoi(p);
         }
         if(gcpercent < 0)
                 return;
 
-        runtime·semacquire(&gcsema);
+        runtime·semacquire(&runtime·worldsema);
         if(!force && mstats.heap_alloc < mstats.next_gc) {
-                runtime·semrelease(&gcsema);
+                runtime·semrelease(&runtime·worldsema);
                 return;
         }
 
         t0 = runtime·nanotime();
 
         m->gcing = 1;
         runtime·stoptheworld();
 
         heap0 = 0;
         obj0 = 0;
         if(gctrace) {
                 cachestats(0);
                 heap0 = mstats.heap_alloc;
                 obj0 = mstats.nmalloc - mstats.nfree;
         }
 
         work.nproc = runtime·gcprocs();
         work.nwait = 0;
         work.ndone = 0;
         work.debugmarkdone = 0;
         addroots();
         parforsetup(&work.markfor, markroot, work.nproc, work.nroot, nil, false);
         parforsetup(&work.sweepfor, sweepspan, work.nproc, runtime·mheap.nspan, nil, true);
         if(work.nproc > 1) {
                 runtime·noteclear(&work.alldone);
-                runtime·helpgc();
+                runtime·helpgc(work.nproc);
         }
 
         parfor(&work.markfor);
         scanblock(nil, 0);
 
         if(DebugMark) {
                 for(i=0; i<work.nroot; i++)
                         debug_scanblock(work.roots[i].p, work.roots[i].n);
                 runtime·xchg(&work.debugmarkdone, 1);
         }
@@ skipping 20 matching lines @@
                 m->locks--;
         }
 ········
         if(work.nproc > 1)
                 runtime·notesleep(&work.alldone);
 
         heap1 = mstats.heap_alloc;
         obj1 = mstats.nmalloc - mstats.nfree;
 
         t3 = runtime·nanotime();
+        mstats.last_gc = t3;
         mstats.pause_ns[mstats.numgc%nelem(mstats.pause_ns)] = t3 - t0;
         mstats.pause_total_ns += t3 - t0;
         mstats.numgc++;
         if(mstats.debuggc)
                 runtime·printf("pause %D\n", t3-t0);
 
         if(gctrace) {
-                runtime·printf("gc%d(%d): %D+%D+%D ms %D -> %D MB %D -> %D (%D-%D) objects %D pointer lookups (%D size, %D addr), %D(%D) steals, %D(%D) handoffs, %D/%D/%D yields\n",
+                runtime·printf("gc%d(%d): %D+%D+%D ms %D -> %D MB %D -> %D (%D-%D) objects, %D(%D) steals, %D(%D) handoffs, %D/%D/%D yields\n",
                         mstats.numgc, work.nproc, (t1-t0)/1000000, (t2-t1)/1000000, (t3-t2)/1000000,
                         heap0>>20, heap1>>20, obj0, obj1,
                         mstats.nmalloc, mstats.nfree,
-                        stats.nsizelookup+stats.naddrlookup, stats.nsizelookup, stats.naddrlookup,
                         stats.nsteal, stats.nstealcnt,
                         stats.nhandoff, stats.nhandoffcnt,
                         stats.nprocyield, stats.nosyield, stats.nsleep);
         }
-
-        runtime·semrelease(&gcsema);
+ ·······
+        runtime·MProf_GC();
+        runtime·semrelease(&runtime·worldsema);
         runtime·starttheworld();
 
         // give the queued finalizers, if any, a chance to run
         if(finq != nil)
                 runtime·gosched();
 
         if(gctrace > 1 && !force)
                 runtime·gc(1);
 }
 
 void
-runtime·UpdateMemStats(void)
-{
-        // Have to acquire gcsema to stop the world,
+runtime·ReadMemStats(MStats *stats)
+{
+        // Have to acquire worldsema to stop the world,
         // because stoptheworld can only be used by
         // one goroutine at a time, and there might be
         // a pending garbage collection already calling it.
-        runtime·semacquire(&gcsema);
+        runtime·semacquire(&runtime·worldsema);
         m->gcing = 1;
         runtime·stoptheworld();
         cachestats(0);
+        *stats = mstats;
         m->gcing = 0;
-        runtime·semrelease(&gcsema);
+        runtime·semrelease(&runtime·worldsema);
         runtime·starttheworld();
 }
 
 static void
 runfinq(void)
 {
         Finalizer *f;
         FinBlock *fb, *next;
         byte *frame;
         uint32 framesz, framecap, i;
@@ skipping 682 matching lines @@
                 runtime·newproc1((byte*)testParforProc, (byte*)&arg, sizeof(arg), 0, runtime·CTestParforParallel);
         m->locks--;
         parfor(&desc);
         for(i=0; i<N; i++) {
                 if(data[i] != i*i)
                         runtime·panicstring("incorrect result");
         }
         runtime·free(data);
         runtime·gomaxprocsfunc(procs);
 }