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).
         wordsPerBitmapWord = sizeof(void*)*8/4,
         bitShift = sizeof(void*)*8/4,
 };
 
 // Bits in per-word bitmap.
 // #defines because enum might not be able to hold the values.
 //
 // Each word in the bitmap describes wordsPerBitmapWord words
@@ skipping 19 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-2];
+        byte *obj[512-3];
 };
 
 typedef struct Finalizer Finalizer;
 struct Finalizer
 {
         void (*fn)(void*);
         void *arg;
         int32 nret;
 };
 
 typedef struct FinBlock FinBlock;
 struct FinBlock
 {
         FinBlock *alllink;
         FinBlock *next;
         int32 cnt;
         int32 cap;
         Finalizer fin[1];
 };
 
 extern byte data[];
 extern byte etext[];
-extern byte end[];
+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*);
 static Workbuf* getfull(Workbuf*);
 static void     putempty(Workbuf*);
 static Workbuf* handoff(Workbuf*);
 
-static struct {
-        Lock fmu;
-        Workbuf *full;
-        Lock emu;
-        Workbuf *empty;
+// parallel for descriptor
+typedef struct Parfor Parfor;
+struct Parfor
+{
+        // executed for each element
+        void (*body)(Parfor*, uint32);
+        // number of idle threads
+        uint32 done;
+        // total number of threads
+        uint32 nthr;
+        // thread id sequencer
+        uint32 thrseq;
+        // iteration space [0, cnt)
+        uint32 cnt;
+        // arbitrary user context
+        void *ctx;
+        // if true, wait while all threads finish processing,
+        // otherwise parfor may return while other threads still working
+        bool wait;
+        byte pad[CacheLineSize];
+        struct
+        {
+                // the thread's iteration space [32lsb, 32msb)
+                uint64 pos;
+                byte pad[CacheLineSize-sizeof(uint64)];
+        } thr[MaxGcproc];
+};
+
+typedef struct GcRoot GcRoot;
+struct GcRoot
+{
+        byte *p;
+        uintptr n;
+};
+
+static struct
+{
+        uint64  full; // Workbuf* + ABA counter in 17msb
+        uint64  empty; // Workbuf* + ABA counter in 17msb
         uint32  nproc;
+        byte pad0[CacheLineSize];
         volatile uint32 nwait;
-        volatile uint32 ndone;
-        volatile uint32 markdone;
+        byte pad1[CacheLineSize];
+        volatile uint32 ndone;
+        volatile uint32 debugmarkdone;
         Note    alldone;
-        MSpan   *spans;
+        Parfor  sweepfor;
+        Parfor  markfor;
 
         Lock;
         byte    *chunk;
         uintptr nchunk;
+
+        GcRoot  *roots;
+        uint32  nroot;
+        uint32  rootcap;
 } work;
+
+// lock-free stack
+// used to manage empty and free Workbuf's during mark phase
+static void     lifopush(uint64 *a, Workbuf *b);
+static Workbuf* lifopop(uint64 *a);
+
+// parallel for over [0, n).
+// body() is executed for each iteration.
+// nthr - total number of worker threads.
+// ctx - arbitrary user context.
+// if wait=true, threads return from parfor() when all work is done;
+// otherwise, threads can return while other threads still finishing processing.········
+static void     parforsetup(Parfor *desc, void (*body)(Parfor*, uint32),
+                            uint32 nthr, uint32 n, void *ctx, bool wait);
+static void     parfor(Parfor *desc);
 
 // 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.
 static void
 scanblock(byte *b, int64 n)
 {
@@ skipping 14 matching lines @@
         // Memory arena parameters.
         arena_start = runtime·mheap.arena_start;
         arena_used = runtime·mheap.arena_used;
         nproc = work.nproc;
 
         wbuf = nil;  // current work buffer
         wp = nil;  // storage for next queued pointer (write pointer)
         nobj = 0;  // number of queued objects
 
         // Scanblock helpers pass b==nil.
-        // The main proc needs to return to make more
+        // Procs need to return to make more
         // calls to scanblock.  But if work.nproc==1 then
         // might as well process blocks as soon as we
         // have them.
         keepworking = b == nil || work.nproc == 1;
 
         // Align b to a word boundary.
         off = (uintptr)b & (PtrSize-1);
         if(off != 0) {
                 b += PtrSize - off;
                 n -= PtrSize - off;
@@ skipping 37 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.nlookup++;
-                        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;
                         } else {
                                 if((byte*)obj >= (byte*)s->limit)
                                         continue;
                                 size = runtime·class_to_size[s->sizeclass];
                                 int32 i = ((byte*)obj - p)/size;
                                 obj = p+i*size;
                         }
 
                         // Now that we know the object header, reload bits.
                         off = (uintptr*)obj - (uintptr*)arena_start;
                         bitp = (uintptr*)arena_start - off/wordsPerBitmapWord - 1;
                         shift = off % wordsPerBitmapWord;
                         xbits = *bitp;
                         bits = xbits >> shift;
 
                 found:
+                        // If another proc wants a pointer, give it some.
+                        if(work.nwait > 0 && nobj > 4 && work.full == 0) {
+                                wbuf->nobj = nobj;
+                                wbuf = handoff(wbuf);
+                                nobj = wbuf->nobj;
+                                wp = wbuf->obj + nobj;
+                        }
+
                         // Now we have bits, bitp, and shift correct for
                         // obj pointing at the base of the object.
                         // Only care about allocated and not marked.
                         if((bits & (bitAllocated|bitMarked)) != bitAllocated)
                                 continue;
                         if(nproc == 1)
                                 *bitp |= bitMarked<<shift;
                         else {
                                 for(;;) {
                                         x = *bitp;
                                         if(x & (bitMarked<<shift))
                                                 goto continue_obj;
                                         if(runtime·casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift))))
                                                 break;
                                 }
                         }
 
                         // If object has no pointers, don't need to scan further.
                         if((bits & bitNoPointers) != 0)
                                 continue;
 
-                        // If another proc wants a pointer, give it some.
-                        if(nobj > 4 && work.nwait > 0 && work.full == nil) {
-                                wbuf->nobj = nobj;
-                                wbuf = handoff(wbuf);
-                                nobj = wbuf->nobj;
-                                wp = wbuf->obj + nobj;
-                        }
+                        PREFETCH(obj);
 
                         // If buffer is full, get a new one.
                         if(wbuf == nil || nobj >= nelem(wbuf->obj)) {
                                 if(wbuf != nil)
                                         wbuf->nobj = nobj;
                                 wbuf = getempty(wbuf);
                                 wp = wbuf->obj;
                                 nobj = 0;
                         }
                         *wp++ = obj;
                         nobj++;
                 continue_obj:;
                 }
 
                 // Done scanning [b, b+n).  Prepare for the next iteration of
                 // the loop by setting b and n to the parameters for the next block.
 
                 // Fetch b from the work buffer.
                 if(nobj == 0) {
                         if(!keepworking) {
-                                putempty(wbuf);
+                                if(wbuf != nil)
+                                        putempty(wbuf);
                                 return;
                         }
                         // 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.nlookup++;
-                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 25 matching lines @@
                 if((byte*)obj < runtime·mheap.arena_start || (byte*)obj >= runtime·mheap.arena_used)
                         continue;
 
                 // Round down to word boundary.
                 obj = (void*)((uintptr)obj & ~((uintptr)PtrSize-1));
 
                 // Consult span table to find beginning.
                 s = runtime·MHeap_LookupMaybe(&runtime·mheap, obj);
                 if(s == nil)
                         continue;
-
 
                 p =  (byte*)((uintptr)s->start<<PageShift);
                 if(s->sizeclass == 0) {
                         obj = p;
                         size = (uintptr)s->npages<<PageShift;
                 } else {
                         if((byte*)obj >= (byte*)s->limit)
                                 continue;
                         size = runtime·class_to_size[s->sizeclass];
                         int32 i = ((byte*)obj - p)/size;
@@ skipping 17 matching lines @@
                         runtime·printf("found unmarked block %p in %p\n", obj, vp+i);
 
                 // If object has no pointers, don't need to scan further.
                 if((bits & bitNoPointers) != 0)
                         continue;
 
                 debug_scanblock(obj, size);
         }
 }
 
+static void
+markroot(Parfor *desc, uint32 i)
+{
+        USED(desc);
+        scanblock(work.roots[i].p, work.roots[i].n);
+}
+
 // Get an empty work buffer off the work.empty list,
 // allocating new buffers as needed.
 static Workbuf*
 getempty(Workbuf *b)
 {
-        if(work.nproc == 1) {
-                // Put b on full list.
-                if(b != nil) {
-                        b->next = work.full;
-                        work.full = b;
-                }
-                // Grab from empty list if possible.
-                b = work.empty;
-                if(b != nil) {
-                        work.empty = b->next;
-                        goto haveb;
-                }
-        } else {
-                // Put b on full list.
-                if(b != nil) {
-                        runtime·lock(&work.fmu);
-                        b->next = work.full;
-                        work.full = b;
-                        runtime·unlock(&work.fmu);
-                }
-                // Grab from empty list if possible.
-                runtime·lock(&work.emu);
-                b = work.empty;
-                if(b != nil)
-                        work.empty = b->next;
-                runtime·unlock(&work.emu);
-                if(b != nil)
-                        goto haveb;
-        }
-
-        // Need to allocate.
-        runtime·lock(&work);
-        if(work.nchunk < sizeof *b) {
-                work.nchunk = 1<<20;
-                work.chunk = runtime·SysAlloc(work.nchunk);
-        }
-        b = (Workbuf*)work.chunk;
-        work.chunk += sizeof *b;
-        work.nchunk -= sizeof *b;
-        runtime·unlock(&work);
-
-haveb:
+        if(b != nil)
+                lifopush(&work.full, b);
+        b = lifopop(&work.empty);
+        if(b == nil) {
+                // Need to allocate.
+                runtime·lock(&work);
+                if(work.nchunk < sizeof *b) {
+                        work.nchunk = 1<<20;
+                        work.chunk = runtime·SysAlloc(work.nchunk);
+                }
+                b = (Workbuf*)work.chunk;
+                work.chunk += sizeof *b;
+                work.nchunk -= sizeof *b;
+                runtime·unlock(&work);
+        }
         b->nobj = 0;
         return b;
 }
 
 static void
 putempty(Workbuf *b)
 {
-        if(b == nil)
-                return;
-
-        if(work.nproc == 1) {
-                b->next = work.empty;
-                work.empty = b;
-                return;
-        }
-
-        runtime·lock(&work.emu);
-        b->next = work.empty;
-        work.empty = b;
-        runtime·unlock(&work.emu);
+        lifopush(&work.empty, b);
 }
 
 // Get a full work buffer off the work.full list, or return nil.
 static Workbuf*
 getfull(Workbuf *b)
 {
         int32 i;
-        Workbuf *b1;
-
-        if(work.nproc == 1) {
-                // Put b on empty list.
-                if(b != nil) {
-                        b->next = work.empty;
-                        work.empty = b;
-                }
-                // Grab from full list if possible.
-                // Since work.nproc==1, no one else is
-                // going to give us work.
-                b = work.full;
-                if(b != nil)
-                        work.full = b->next;
+
+        if(b != nil)
+                lifopush(&work.empty, b);
+        b = lifopop(&work.full);
+        if(b != nil || work.nproc == 1)
                 return b;
-        }
-
-        putempty(b);
-
-        // Grab buffer from full list if possible.
-        for(;;) {
-                b1 = work.full;
-                if(b1 == nil)
-                        break;
-                runtime·lock(&work.fmu);
-                if(work.full != nil) {
-                        b1 = work.full;
-                        work.full = b1->next;
-                        runtime·unlock(&work.fmu);
-                        return b1;
-                }
-                runtime·unlock(&work.fmu);
-        }
 
         runtime·xadd(&work.nwait, +1);
         for(i=0;; i++) {
-                b1 = work.full;
-                if(b1 != nil) {
-                        runtime·lock(&work.fmu);
-                        if(work.full != nil) {
-                                runtime·xadd(&work.nwait, -1);
-                                b1 = work.full;
-                                work.full = b1->next;
-                                runtime·unlock(&work.fmu);
-                                return b1;
-                        }
-                        runtime·unlock(&work.fmu);
-                        continue;
+                if(work.full != 0) {
+                        runtime·xadd(&work.nwait, -1);
+                        b = lifopop(&work.full);
+                        if(b != nil)
+                                return b;
+                        runtime·xadd(&work.nwait, +1);
                 }
                 if(work.nwait == work.nproc)
                         return nil;
-                if(i < 10)
+                if(i < 10) {
+                        m->gcstats.nprocyield++;
                         runtime·procyield(20);
-                else if(i < 20)
+                } else if(i < 20) {
+                        m->gcstats.nosyield++;
                         runtime·osyield();
-                else
+                } else {
+                        m->gcstats.nsleep++;
                         runtime·usleep(100);
+                }
         }
 }
 
 static Workbuf*
 handoff(Workbuf *b)
 {
         int32 n;
         Workbuf *b1;
 
         // Make new buffer with half of b's pointers.
         b1 = getempty(nil);
         n = b->nobj/2;
         b->nobj -= n;
         b1->nobj = n;
         runtime·memmove(b1->obj, b->obj+b->nobj, n*sizeof b1->obj[0]);
-        m->gcstats.nhandoff += n;
+        m->gcstats.nhandoff += 1;
+        m->gcstats.nhandoffcnt += n;
 
         // Put b on full list - let first half of b get stolen.
-        runtime·lock(&work.fmu);
-        b->next = work.full;
-        work.full = b;
-        runtime·unlock(&work.fmu);
-
+        lifopush(&work.full, b);
         return b1;
 }
 
-// Scanstack calls scanblock on each of gp's stack segments.
 static void
-scanstack(void (*scanblock)(byte*, int64), G *gp)
+addroot(byte *p, uintptr n)
+{
+        uint32 cap;
+        GcRoot *new;
+
+        if(work.nroot >= work.rootcap) {
+                cap = PageSize/sizeof(GcRoot);
+                if(cap < 2*work.rootcap)
+                        cap = 2*work.rootcap;
+                new = (GcRoot*)runtime·SysAlloc(cap*sizeof(GcRoot));
+                if(work.roots != nil) {
+                        runtime·memmove(new, work.roots, work.rootcap*sizeof(GcRoot));
+                        runtime·SysFree(work.roots, work.rootcap*sizeof(GcRoot));
+                }
+                work.roots = new;
+                work.rootcap = cap;
+        }
+        work.roots[work.nroot].p = p;
+        work.roots[work.nroot].n = n;
+        work.nroot++;
+}
+
+static void
+addstackroots(G *gp)
 {
         M *mp;
         int32 n;
         Stktop *stk;
         byte *sp, *guard;
 
         stk = (Stktop*)gp->stackbase;
         guard = gp->stackguard;
 
         if(gp == g) {
@@ skipping 12 matching lines @@
                 // as schedlock and may have needed to start a new stack segment.
                 // Use the stack segment and stack pointer at the time of
                 // the system call instead, since that won't change underfoot.
                 if(gp->gcstack != nil) {
                         stk = (Stktop*)gp->gcstack;
                         sp = gp->gcsp;
                         guard = gp->gcguard;
                 }
         }
 
-        if(Debug > 1)
-                runtime·printf("scanstack %d %p\n", gp->goid, sp);
         n = 0;
         while(stk) {
                 if(sp < guard-StackGuard || (byte*)stk < sp) {
                         runtime·printf("scanstack inconsistent: g%d#%d sp=%p not in [%p,%p]\n", gp->goid, n, sp, guard-StackGuard, stk);
                         runtime·throw("scanstack");
                 }
-                scanblock(sp, (byte*)stk - sp);
+                addroot(sp, (byte*)stk - sp);
                 sp = stk->gobuf.sp;
                 guard = stk->stackguard;
                 stk = (Stktop*)stk->stackbase;
                 n++;
         }
 }
 
-// Markfin calls scanblock on the blocks that have finalizers:
-// the things pointed at cannot be freed until the finalizers have run.
 static void
-markfin(void *v)
+addfinroots(void *v)
 {
         uintptr size;
 
         size = 0;
         if(!runtime·mlookup(v, &v, &size, nil) || !runtime·blockspecial(v))
                 runtime·throw("mark - finalizer inconsistency");
 
         // do not mark the finalizer block itself.  just mark the things it points at.
-        scanblock(v, size);
+        addroot(v, size);
 }
 
 static void
-debug_markfin(void *v)
-{
-        uintptr size;
-
-        if(!runtime·mlookup(v, &v, &size, nil))
-                runtime·throw("debug_mark - finalizer inconsistency");
-        debug_scanblock(v, size);
-}
-
-// Mark
-static void
-mark(void (*scan)(byte*, int64))
+addroots(void)
 {
         G *gp;
         FinBlock *fb;
+        byte *p;
+
+        work.nroot = 0;
 
         // mark data+bss.
-        // skip runtime·mheap itself, which has no interesting pointers
-        // and is mostly zeroed and would not otherwise be paged in.
-        scan(data, (byte*)&runtime·mheap - data);
-        scan((byte*)(&runtime·mheap+1), end - (byte*)(&runtime·mheap+1));
-
-        // mark stacks
+        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);
-                        runtime·throw("mark - bad status");
-                case Gdead:
-                        break;
-                case Grunning:
-                        if(gp != g)
-                                runtime·throw("mark - world not stopped");
-                        scanstack(scan, gp);
-                        break;
-                case Grunnable:
-                case Gsyscall:
-                case Gwaiting:
-                        scanstack(scan, gp);
-                        break;
-                }
-        }
-
-        // mark things pointed at by objects with finalizers
-        if(scan == debug_scanblock)
-                runtime·walkfintab(debug_markfin);
-        else
-                runtime·walkfintab(markfin);
-
-        for(fb=allfin; fb; fb=fb->alllink)
-                scanblock((byte*)fb->fin, fb->cnt*sizeof(fb->fin[0]));
-
-        // in multiproc mode, join in the queued work.
-        scan(nil, 0);
+                        default:
+                                runtime·printf("unexpected G.status %d\n", gp->status);
+                                runtime·throw("mark - bad status");
+                        case Gdead:
+                                break;
+                        case Grunning:
+                                if(gp != g)
+                                        runtime·throw("mark - world not stopped");
+                                addstackroots(gp);
+                                break;
+                        case Grunnable:
+                        case Gsyscall:
+                        case Gwaiting:
+                                addstackroots(gp);
+                                break;
+                }
+        }
 }
 
 static bool
 handlespecial(byte *p, uintptr size)
 {
         void (*fn)(void*);
         int32 nret;
         FinBlock *block;
         Finalizer *f;
-        
+
         if(!runtime·getfinalizer(p, true, &fn, &nret)) {
                 runtime·setblockspecial(p, false);
                 runtime·MProf_Free(p, size);
                 return false;
         }
 
         runtime·lock(&finlock);
         if(finq == nil || finq->cnt == finq->cap) {
                 if(finc == nil) {
                         finc = runtime·SysAlloc(PageSize);
                         finc->cap = (PageSize - sizeof(FinBlock)) / sizeof(Finalizer) + 1;
                         finc->alllink = allfin;
                         allfin = finc;
                 }
                 block = finc;
                 finc = block->next;
                 block->next = finq;
                 finq = block;
         }
         f = &finq->fin[finq->cnt];
         finq->cnt++;
         f->fn = fn;
         f->nret = nret;
         f->arg = p;
-        runtime·unlock(&finlock); 
+        runtime·unlock(&finlock);
         return true;
 }
 
 // Sweep frees or collects finalizers for blocks not marked in the mark phase.
 // It clears the mark bits in preparation for the next GC round.
 static void
-sweep(void)
+sweepspan(Parfor *desc, uint32 spanidx)
 {
         MSpan *s;
         int32 cl, n, npages;
         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;
 
-        for(;;) {
-                s = work.spans;
-                if(s == nil)
-                        break;
-                if(!runtime·casp(&work.spans, s, s->allnext))
+        p = (byte*)(s->start << PageShift);
+        cl = s->sizeclass;
+        if(cl == 0) {
+                size = s->npages<<PageShift;
+                n = 1;
+        } else {
+                // Chunk full of small blocks.
+                size = runtime·class_to_size[cl];
+                npages = runtime·class_to_allocnpages[cl];
+                n = (npages << PageShift) / size;
+        }
+        c = m->mcache;
+        nfree = 0;
+        start = end = nil;
+
+        // 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.
+        for(; n > 0; n--, p += size) {
+                uintptr off, *bitp, shift, bits;
+
+                off = (uintptr*)p - (uintptr*)arena_start;
+                bitp = (uintptr*)arena_start - off/wordsPerBitmapWord - 1;
+                PREFETCH((byte*)bitp - size);
+                shift = off % wordsPerBitmapWord;
+                bits = *bitp>>shift;
+
+                if((bits & bitAllocated) == 0)
                         continue;
 
-                if(s->state != MSpanInUse)
+                if((bits & bitMarked) != 0) {
+                        if(DebugMark) {
+                                if(!(bits & bitSpecial))
+                                        runtime·printf("found spurious mark on %p\n", p);
+                                *bitp &= ~(bitSpecial<<shift);
+                        }
+                        *bitp &= ~(bitMarked<<shift);
                         continue;
-
-                p = (byte*)(s->start << PageShift);
-                cl = s->sizeclass;
+                }
+
+                // Special means it has a finalizer or is being profiled.
+                // In DebugMark mode, the bit has been coopted so
+                // we have to assume all blocks are special.
+                if(DebugMark || (bits & bitSpecial) != 0) {
+                        if(handlespecial(p, size))
+                                continue;
+                }
+
+                // Mark freed; restore block boundary bit.
+                *bitp = (*bitp & ~(bitMask<<shift)) | (bitBlockBoundary<<shift);
+
                 if(cl == 0) {
-                        size = s->npages<<PageShift;
-                        n = 1;
-                } else {
-                        // Chunk full of small blocks.
-                        size = runtime·class_to_size[cl];
-                        npages = runtime·class_to_allocnpages[cl];
-                        n = (npages << PageShift) / size;
-                }
-
-                // 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.
-                for(; n > 0; n--, p += size) {
-                        uintptr off, *bitp, shift, bits;
-
-                        off = (uintptr*)p - (uintptr*)arena_start;
-                        bitp = (uintptr*)arena_start - off/wordsPerBitmapWord - 1;
-                        shift = off % wordsPerBitmapWord;
-                        bits = *bitp>>shift;
-
-                        if((bits & bitAllocated) == 0)
-                                continue;
-
-                        if((bits & bitMarked) != 0) {
-                                if(DebugMark) {
-                                        if(!(bits & bitSpecial))
-                                                runtime·printf("found spurious mark on %p\n", p);
-                                        *bitp &= ~(bitSpecial<<shift);
-                                }
-                                *bitp &= ~(bitMarked<<shift);
-                                continue;
-                        }
-
-                        // Special means it has a finalizer or is being profiled.
-                        // In DebugMark mode, the bit has been coopted so
-                        // we have to assume all blocks are special.
-                        if(DebugMark || (bits & bitSpecial) != 0) {
-                                if(handlespecial(p, size))
-                                        continue;
-                        }
-
-                        // Mark freed; restore block boundary bit.
-                        *bitp = (*bitp & ~(bitMask<<shift)) | (bitBlockBoundary<<shift);
-
-                        c = m->mcache;
-                        if(s->sizeclass == 0) {
-                                // Free large span.
-                                runtime·unmarkspan(p, 1<<PageShift);
-                                *(uintptr*)p = 1;       // needs zeroing
-                                runtime·MHeap_Free(&runtime·mheap, s, 1);
-                        } else {
-                                // Free small object.
-                                if(size > sizeof(uintptr))
-                                        ((uintptr*)p)[1] = 1;   // mark as "needs to be zeroed"
-                                c->local_by_size[s->sizeclass].nfree++;
-                                runtime·MCache_Free(c, p, s->sizeclass, size);
-                        }
+                        // Free large span.
+                        runtime·unmarkspan(p, 1<<PageShift);
+                        *(uintptr*)p = 1;       // needs zeroing
+                        runtime·MHeap_Free(&runtime·mheap, s, 1);
                         c->local_alloc -= size;
                         c->local_nfree++;
-                }
+                } else {
+                        // Free small object.
+                        if(nfree) {
+                                PREFETCH(p);
+                                if(size > sizeof(uintptr))
+                                        ((uintptr*)end)[1] = 1;   // mark as "needs to be zeroed"
+                                end->next = (MLink*)p;
+                                end = (MLink*)p;
+                        } else {
+                                start = (MLink*)p;
+                                end = (MLink*)p;
+                        }
+                        nfree++;
+                }
+        }
+
+        if(nfree) {
+                if(size > sizeof(uintptr))
+                        ((uintptr*)end)[1] = 1;   // mark as "needs to be zeroed"
+                c->local_by_size[s->sizeclass].nfree += nfree;
+                c->local_alloc -= size * nfree;
+                c->local_nfree += nfree;
+                c->local_cachealloc -= nfree * size;
+                c->local_objects -= nfree;
+                runtime·MCentral_FreeSpan(&runtime·mheap.central[cl],
+                                          s, nfree, start, end);
         }
 }
 
 void
 runtime·gchelper(void)
 {
+        // parallel mark for over gc roots
+        parfor(&work.markfor);
+        // help other threads scan secondary blocks
         scanblock(nil, 0);
+
         if(DebugMark) {
-                while(runtime·atomicload(&work.markdone) == 0)
+                // wait while the main thread executes mark(debug_scanblock)
+                while(runtime·atomicload(&work.debugmarkdone) == 0)
                         runtime·usleep(10);
         }
- ·······
-        sweep();
+
+        // 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;
 
 static void
 stealcache(void)
 {
         M *m;
 
         for(m=runtime·allm; m; m=m->alllink)
                 runtime·MCache_ReleaseAll(m->mcache);
 }
 
 static void
 cachestats(GCStats *stats)
 {
         M *m;
         MCache *c;
         int32 i;
         uint64 stacks_inuse;
         uint64 stacks_sys;
+        uint64 *src, *dst;
 
         if(stats)
                 runtime·memclr((byte*)stats, sizeof(*stats));
         stacks_inuse = 0;
         stacks_sys = 0;
         for(m=runtime·allm; m; m=m->alllink) {
                 runtime·purgecachedstats(m);
                 stacks_inuse += m->stackalloc->inuse;
                 stacks_sys += m->stackalloc->sys;
                 if(stats) {
-                        stats->nlookup += m->gcstats.nlookup;
-                        stats->nsizelookup += m->gcstats.nsizelookup;
-                        stats->naddrlookup += m->gcstats.naddrlookup;
-                        stats->nhandoff += m->gcstats.nhandoff;
+                        src = (uint64*)&m->gcstats;
+                        dst = (uint64*)stats;
+                        for(i=0; i<sizeof(*stats)/sizeof(uint64); i++)
+                                dst[i] += src[i];
                         runtime·memclr((byte*)&m->gcstats, sizeof(m->gcstats));
                 }
                 c = m->mcache;
                 for(i=0; i<nelem(c->local_by_size); i++) {
                         mstats.by_size[i].nmalloc += c->local_by_size[i].nmalloc;
                         c->local_by_size[i].nmalloc = 0;
                         mstats.by_size[i].nfree += c->local_by_size[i].nfree;
                         c->local_by_size[i].nfree = 0;
                 }
         }
         mstats.stacks_inuse = stacks_inuse;
         mstats.stacks_sys = stacks_sys;
 }
 
 void
 runtime·gc(int32 force)
 {
         int64 t0, t1, t2, t3;
         uint64 heap0, heap1, obj0, obj1;
+        GCStats stats;
+        uint32 i;
         byte *p;
-        bool extra;
-        GCStats stats;
 
         // The gc is turned off (via enablegc) until
         // the bootstrap has completed.
         // Also, malloc gets called in the guts
         // of a number of libraries that might be
         // holding locks.  To avoid priority inversion
         // problems, don't bother trying to run gc
         // while holding a lock.  The next mallocgc
         // without a lock will do the gc instead.
         if(!mstats.enablegc || m->locks > 0 || runtime·panicking)
                 return;
 
         if(gcpercent == -2) {   // first time through
                 p = runtime·getenv("GOGC");
                 if(p == nil || p[0] == '\0')
                         gcpercent = 100;
                 else if(runtime·strcmp(p, (byte*)"off") == 0)
                         gcpercent = -1;
                 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();
 
-        cachestats(0);
-        heap0 = mstats.heap_alloc;
-        obj0 = mstats.nmalloc - mstats.nfree;
-
-        work.nproc = MaxGcproc+1;
+        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.spans = runtime·mheap.allspans;
-        work.markdone = 0;
-        extra = false;
-        if(runtime·gomaxprocs > 1 && runtime·ncpu > 1) {
+        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);
-                work.nproc += runtime·helpgc(&extra);
-        }
-        work.nproc -= MaxGcproc;
-
-        mark(scanblock);
+                runtime·helpgc(work.nproc);
+        }
+
+        parfor(&work.markfor);
+        scanblock(nil, 0);
+
         if(DebugMark) {
-                mark(debug_scanblock);
-                runtime·xchg(&work.markdone, 1);
+                for(i=0; i<work.nroot; i++)
+                        debug_scanblock(work.roots[i].p, work.roots[i].n);
+                runtime·xchg(&work.debugmarkdone, 1);
         }
         t1 = runtime·nanotime();
-
-        sweep();
-        if(work.nproc > 1)
-                runtime·notesleep(&work.alldone);
+        // parallel sweep for over all spans
+        parfor(&work.sweepfor);
         t2 = runtime·nanotime();
 
         stealcache();
         cachestats(&stats);
 
         mstats.next_gc = mstats.heap_alloc+mstats.heap_alloc*gcpercent/100;
         m->gcing = 0;
 
-        m->locks++;     // disable gc during the mallocs in newproc
         if(finq != nil) {
+                m->locks++;     // disable gc during the mallocs in newproc
                 // kick off or wake up goroutine to run queued finalizers
                 if(fing == nil)
                         fing = runtime·newproc1((byte*)runfinq, nil, 0, 0, runtime·gc);
                 else if(fingwait) {
                         fingwait = 0;
                         runtime·ready(fing);
                 }
-        }
-        m->locks--;
+                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 handoff\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.nlookup, stats.nsizelookup, stats.naddrlookup, stats.nhandoff);
-        }
-
-        runtime·semrelease(&gcsema);
-
-        // If we could have used another helper proc, start one now,
-        // in the hope that it will be available next time.
-        // It would have been even better to start it before the collection,
-        // but doing so requires allocating memory, so it's tricky to
-        // coordinate.  This lazy approach works out in practice:
-        // we don't mind if the first couple gc rounds don't have quite
-        // the maximum number of procs.
-        runtime·starttheworld(extra);
-
-        // give the queued finalizers, if any, a chance to run ·
-        if(finq != nil) 
+                        stats.nsteal, stats.nstealcnt,
+                        stats.nhandoff, stats.nhandoffcnt,
+                        stats.nprocyield, stats.nosyield, stats.nsleep);
+        }
+ ·······
+        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·starttheworld(false);
+        runtime·semrelease(&runtime·worldsema);
+        runtime·starttheworld();
 }
 
 static void
 runfinq(void)
 {
         Finalizer *f;
         FinBlock *fb, *next;
         byte *frame;
         uint32 framesz, framecap, i;
 
@@ skipping 234 matching lines @@
         uintptr n;
 
         n = (h->arena_used - h->arena_start) / wordsPerBitmapWord;
         n = (n+bitmapChunk-1) & ~(bitmapChunk-1);
         if(h->bitmap_mapped >= n)
                 return;
 
         runtime·SysMap(h->arena_start - n, n - h->bitmap_mapped);
         h->bitmap_mapped = n;
 }
+
+#ifdef _64BIT
+// Amd64 uses 48-bit virtual addresses, 47-th bit is used as kernel/user flag.
+// So we use 17msb of pointers as ABA counter.
+# define PTR_BITS 47
+#else
+# define PTR_BITS 32
+#endif
+#define PTR_MASK ((1ull<<PTR_BITS)-1)
+
+static void
+lifopush(uint64 *a, Workbuf *b)
+{
+        uint64 old, new;
+
+        if((uint64)b != ((uint64)b&PTR_MASK)) {
+                runtime·printf("p=%p\n", b);
+                runtime·throw("lifopush: invalid pointer");
+        }
+
+        if(work.nproc == 1) {
+                b->next = (Workbuf*)(*a&PTR_MASK);
+                *a = (uint64)b;
+                return;
+        }
+
+        b->pushcnt++;
+        new = (uint64)b|(((uint64)b->pushcnt)<<PTR_BITS);
+        old = runtime·atomicload64(a);
+        for(;;) {
+                b->next = (Workbuf*)(old&PTR_MASK);
+                if(runtime·cas64(a, &old, new))
+                        break;
+        }
+}
+
+static Workbuf*
+lifopop(uint64 *a)
+{
+        Workbuf *b, *b2;
+        uint64 old, new;
+
+        if(work.nproc == 1) {
+                b = (Workbuf*)(*a&PTR_MASK);
+                if(b == nil)
+                        return nil;
+                *a = (uint64)b->next;
+                return b;
+        }
+
+        old = runtime·atomicload64(a);
+        for(;;) {
+                if(old == 0)
+                        return nil;
+                b = (Workbuf*)(old&PTR_MASK);
+                b2 = runtime·atomicloadp(&b->next);
+                new = 0;
+                if(b2 != nil)
+                        new = (uint64)b2|(((uint64)b2->pushcnt)<<PTR_BITS);
+                if(runtime·cas64(a, &old, new))
+                        return b;
+        }
+}
+
+void
+runtime·CTestLockFreeStack(bool isShort)
+{
+        uint64 stack;
+        Workbuf *b;
+
+        USED(isShort);
+
+        for(work.nproc=1; work.nproc<=2; work.nproc++) {
+                // check the stack is initially empty
+                stack = 0;
+                if(lifopop(&stack) != nil)
+                        runtime·panicstring("stack is not empty");
+
+                // push one element
+                b = (Workbuf*)runtime·mallocgc(sizeof(Workbuf), FlagNoGC, 0, 0);
+                b->nobj = 42;
+                lifopush(&stack, b);
+
+                // push another
+                b = (Workbuf*)runtime·mallocgc(sizeof(Workbuf), FlagNoGC, 0, 0);
+                b->nobj = 43;
+                lifopush(&stack, b);
+
+                // pop one element
+                b = lifopop(&stack);
+                if(b == nil)
+                        runtime·panicstring("stack is empty");
+                if(b->nobj != 43)
+                        runtime·panicstring("no lifo");
+                runtime·free(b);
+
+                // pop another
+                b = lifopop(&stack);
+                if(b == nil)
+                        runtime·panicstring("stack is empty");
+                if(b->nobj != 42)
+                        runtime·panicstring("no lifo");
+                runtime·free(b);
+
+                // check the stack is empty again
+                if(stack != 0)
+                        runtime·panicstring("stack is not empty");
+                if(lifopop(&stack) != nil)
+                        runtime·panicstring("stack is not empty");
+        }
+}
+
+typedef struct StackTestCtx StackTestCtx;
+struct StackTestCtx
+{
+        uint32 niter;
+        uint32 waitsema;
+        uint64 stack[2];
+};
+
+static void
+stackTestProc(StackTestCtx *ctx)
+{
+        int32 i, n;
+        Workbuf *b;
+
+        for(i=0; i<ctx->niter; i++) {
+                n = runtime·fastrand1()%2;
+                b = lifopop(&ctx->stack[n]);
+                if(b==nil)
+                        continue;
+                n = runtime·fastrand1()%2;
+                lifopush(&ctx->stack[n], b);
+        }
+        runtime·semrelease(&ctx->waitsema);
+}
+
+void
+runtime·CTestLockFreeStackStress(bool isShort)
+{
+        StackTestCtx ctx, *arg;
+        Workbuf *b;
+        int32 i, sum, sum2, cnt, procs;
+        const int32 N = 100;
+        const int32 P = 8;
+        const int32 G = 16;
+
+        procs = runtime·gomaxprocsfunc(P);
+        work.nproc = P;
+        ctx.niter = isShort ? 10000 : 100000;
+        ctx.waitsema = 0;
+        ctx.stack[0] = 0;
+        ctx.stack[1] = 0;
+        arg = &ctx;
+        sum = 0;
+        for(i=0; i<N; i++) {
+                b = (Workbuf*)runtime·mallocgc(sizeof(Workbuf), FlagNoGC, 0, 0);
+                b->nobj = i;
+                sum += i;
+                lifopush(&ctx.stack[i%2], b);
+        }
+        m->locks++; // disable gc during the mallocs (gc resets work.nproc)
+        for(i=0; i<G; i++)
+                runtime·newproc1((byte*)stackTestProc, (byte*)&arg, sizeof(arg), 0, runtime·CTestLockFreeStackStress);
+        m->locks--;
+        for(i=0; i<G; i++)
+                runtime·semacquire(&ctx.waitsema);
+        sum2 = 0;
+        cnt = 0;
+        for(i=0; i<2; i++) {
+                while((b=lifopop(&ctx.stack[i])) != nil) {
+                        cnt++;
+                        sum2 += b->nobj;
+                        b->next = (Workbuf*)123;
+                        runtime·free(b);
+                }
+        }
+        if(cnt != N || sum2 != sum)
+                runtime·panicstring("stack corruption");
+        runtime·gomaxprocsfunc(procs);
+}
+
+static void
+parforsetup(Parfor *desc, void (*body)(Parfor*, uint32), uint32 nthr, uint32 n, void *ctx, bool wait)
+{
+        uint32 i, d, begin, end;
+
+        if(nthr == 0 || nthr > MaxGcproc || body == nil) {
+                runtime·printf("nthr=%d count=%d body=%p\n",
+                               nthr, n, body);
+                runtime·throw("parallel for: invalid args");
+        }
+
+        desc->body = body;
+        desc->done = 0;
+        desc->nthr = nthr;
+        desc->thrseq = 0;
+        desc->cnt = n;
+        desc->ctx = ctx;
+        desc->wait = wait;
+        for(i=0; i<nthr; i++) {
+                begin = n / nthr * i;
+                end = n / nthr * (i+1);
+                d = n % nthr;
+                if(i < d) {
+                        begin += i;
+                        end += (i+1);
+                } else {
+                        begin += d;
+                        end += d;
+                }
+                desc->thr[i].pos = (uint64)begin | (((uint64)end)<<32);
+        }
+}
+
+static void
+parfor(Parfor *desc)
+{
+        uint32 tid, begin, end, begin2, try, victim, i;
+        uint64 *mypos, pos;
+        bool idle;
+
+        // obtain 0-based thread index
+        tid = runtime·xadd(&desc->thrseq, 1) - 1;
+        if(tid >= desc->nthr) {
+                runtime·throw("parallel for: invalid tid");
+        }
+
+        // if single-threaded, just execute the for serially
+        if(desc->nthr==1) {
+                for(i=0; i<desc->cnt; i++)
+                        desc->body(desc, i);
+                return;
+        }
+
+        mypos = &desc->thr[tid].pos;
+        for(;;) {
+                for(;;) {
+                        // while have work, bump low index and execute the iteration
+                        pos = runtime·xadd64(mypos, 1);
+                        begin = (uint32)pos-1;
+                        end = (uint32)(pos>>32);
+                        if(begin>=end)
+                                break;
+                        desc->body(desc, begin);
+                }
+
+                // out of work, need to steal something
+                idle = false;
+                for(try=0;; try++) {
+                        // if we don't see any work for long enough,
+                        // increment the done counter...
+                        if(try > desc->nthr*4 && !idle) {
+                                idle = true;
+                                runtime·xadd(&desc->done, 1);
+                        }
+                        // ...if all threads have incremented the counter,
+                        // we are done
+                        if(desc->done + !idle == desc->nthr) {
+                                if(!idle)
+                                        runtime·xadd(&desc->done, 1);
+                                return;
+                        }
+                        // choose a random victim for stealing
+                        victim = runtime·fastrand1() % (desc->nthr-1);
+                        if(victim >= tid)
+                                victim++;
+                        pos = runtime·atomicload64(&desc->thr[victim].pos);
+                        for(;;) {
+                                // see if it has any work
+                                begin = (uint32)pos;
+                                end = (uint32)(pos>>32);
+                                if(begin >= end-1) {
+                                        begin = end = 0;
+                                        break;
+                                }
+                                if(idle) {
+                                        runtime·xadd(&desc->done, -1);
+                                        idle = false;
+                                }
+                                begin2 = begin + (end-begin)/2;
+                                if(runtime·cas64(&desc->thr[victim].pos, &pos, (uint64)begin | (((uint64)begin2)<<32))) {
+                                        begin = begin2;
+                                        break;
+                                }
+                        }
+                        if(begin < end) {
+                                // has successfully stolen some work
+                                if(idle)
+                                        runtime·throw("parfor: should not be idle");
+                                runtime·atomicstore64(mypos, (uint64)begin | ((uint64)end)<<32);
+                                m->gcstats.nsteal += 1;
+                                m->gcstats.nstealcnt += end-begin;
+                                break;
+                        }
+                        // backoff
+                        if(try < desc->nthr) {
+                        } else if (try < desc->nthr*4) {
+                                m->gcstats.nprocyield++;
+                                runtime·procyield(20);
+                        // if a user asked to not wait for others, exit now
+                        // (assume that most work is already done)
+                        } else if (!desc->wait) {
+                                if(!idle)
+                                        runtime·xadd(&desc->done, 1);
+                                return;
+                        } else if (try < desc->nthr*6) {
+                                m->gcstats.nosyield++;
+                                runtime·osyield();
+                        } else {
+                                m->gcstats.nsleep++;
+                                runtime·usleep(1);
+                        }
+                }
+        }
+}
+
+static void
+testParforBody(Parfor *desc, uint32 i)
+{
+        uint64 *data;
+
+        data = (uint64*)desc->ctx;
+        data[i] *= data[i];
+}
+
+static void
+testParforProc(Parfor *desc)
+{
+        parfor(desc);
+}
+
+// Simple serial sanity test for parallelfor.
+void
+runtime·CTestParfor(bool isShort)
+{
+        Parfor desc;
+        uint64 *data;
+        uint32 i, N;
+
+        USED(isShort);
+
+        N = 1000;
+        data = (uint64*)runtime·mal(N*sizeof(uint64));
+        for(i=0; i<N; i++)
+                data[i] = i;
+        parforsetup(&desc, testParforBody, 1, N, data, true);
+        parfor(&desc);
+        for(i=0; i<N; i++) {
+                if(data[i] != i*i)
+                        runtime·panicstring("incorrect result");
+        }
+        runtime·free(data);
+}
+
+// Test that iterations are properly distributed.
+void
+runtime·CTestParforSetup(bool isShort)
+{
+        Parfor desc;
+        uint32 n, t, i, begin, end, size, end0, size0, sum;
+
+        USED(isShort);
+
+        for(n=0; n<100; n++) {
+                for(t=1; t<=MaxGcproc; t++) {
+                        parforsetup(&desc, testParforBody, t, n, 0, true);
+                        sum = 0;
+                        size0 = 0;
+                        end0 = 0;
+                        for(i=0; i<t; i++) {
+                                begin = (uint32)desc.thr[i].pos;
+                                end = (uint32)(desc.thr[i].pos>>32);
+                                size = end - begin;
+                                sum += size;
+                                if(i==0) {
+                                        size0 = size;
+                                        if(begin != 0)
+                                                runtime·panicstring("incorrect begin");
+                                } else {
+                                        if(size != size0 && size != size0-1)
+                                                runtime·panicstring("incorrect size");
+                                        if(begin != end0)
+                                                runtime·panicstring("incorrect begin/end");
+                                }
+                                end0 = end;
+                        }
+                        if(sum != n)
+                                runtime·panicstring("incorrect sum");
+                }
+        }
+}
+
+// Test that nonblocking parallelfor does not block.
+void
+runtime·CTestParforNonblock(bool isShort)
+{
+        Parfor desc;
+        uint64 *data;
+        uint32 i, N;
+
+        USED(isShort);
+
+        N = 1000;
+        data = (uint64*)runtime·mal(N*sizeof(uint64));
+        for(i=0; i<N; i++)
+                data[i] = i;
+        parforsetup(&desc, testParforBody, MaxGcproc, N, data, false);
+        for(i=0; i<MaxGcproc; i++)
+                parfor(&desc);
+        for(i=0; i<N; i++) {
+                if(data[i] != i*i)
+                        runtime·panicstring("incorrect result");
+        }
+        runtime·free(data);
+}
+
+// Test parallel parallelfor.
+void
+runtime·CTestParforParallel(bool isShort)
+{
+        Parfor desc, *arg;
+        uint64 *data;
+        uint32 i, N;
+        int32 procs;
+
+        procs = runtime·gomaxprocsfunc(MaxGcproc+1);
+        N = 10000;
+        if(isShort)
+                N /= 10;
+        data = (uint64*)runtime·mal(N*sizeof(uint64));
+        for(i=0; i<N; i++)
+                data[i] = i;
+        parforsetup(&desc, testParforBody, MaxGcproc, N, data, true);
+        arg = &desc;
+        m->locks++; // disable gc during the mallocs in newproc
+        for(i=1; i<MaxGcproc; i++)
+                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);
+}