code review 46970043: runtime: allocate goroutine ids in batches

src/pkg/runtime/proc.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.
 
 #include "runtime.h"
 #include "arch_GOARCH.h"
 #include "zaexperiment.h"
 #include "malloc.h"
 #include "stack.h"
 #include "race.h"
@@ skipping 56 matching lines @@
         // Number of goroutine ids to grab from runtime·sched.goidgen to local per-P cache at once.
         // 16 seems to provide enough amortization, but other than that it's mostly arbitrary number.
         GoidCacheBatch = 16,
 };
 
 Sched   runtime·sched;
 int32   runtime·gomaxprocs;
 uint32  runtime·needextram;
 bool    runtime·iscgo;
 M       runtime·m0;
-G       runtime·g0;      // idle goroutine for m0
-G*      runtime·allg;
+G       runtime·g0;     // idle goroutine for m0
 G*      runtime·lastg;
 M*      runtime·allm;
 M*      runtime·extram;
 int8*   runtime·goos;
 int32   runtime·ncpu;
 static int32    newprocs;
 
+static  Lock allglock;  // the following vars are protected by this lock or by stoptheworld
+G**     runtime·allg;
+uintptr runtime·allglen;
+static  uintptr allgcap;
+
 void runtime·mstart(void);
 static void runqput(P*, G*);
 static G* runqget(P*);
-static void runqgrow(P*);
+static bool runqputslow(P*, G*, uint32, uint32);
 static G* runqsteal(P*, P*);
 static void mput(M*);
 static M* mget(void);
 static void mcommoninit(M*);
 static void schedule(void);
 static void procresize(int32);
 static void acquirep(P*);
 static P* releasep(void);
 static void newm(void(*)(void), P*);
 static void stopm(void);
 static void startm(P*, bool);
 static void handoffp(P*);
 static void wakep(void);
 static void stoplockedm(void);
 static void startlockedm(G*);
 static void sysmon(void);
 static uint32 retake(int64);
 static void incidlelocked(int32);
 static void checkdead(void);
 static void exitsyscall0(G*);
 static void park0(G*);
 static void goexit0(G*);
 static void gfput(P*, G*);
 static G* gfget(P*);
 static void gfpurge(P*);
 static void globrunqput(G*);
+static void globrunqputbatch(G*, G*, int32);
 static G* globrunqget(P*, int32);
 static P* pidleget(void);
 static void pidleput(P*);
 static void injectglist(G*);
 static bool preemptall(void);
 static bool preemptone(P*);
 static bool exitsyscallfast(void);
 static bool haveexperiment(int8*);
+static void allgadd(G*);
 
 // The bootstrap sequence is:
 //
 //      call osinit
 //      call schedinit
 //      make & queue new G
 //      call runtime·mstart
 //
 // The new G calls runtime·main.
 void
 runtime·schedinit(void)
 {
         int32 n, procs;
         byte *p;
         Eface i;
 
         runtime·sched.maxmcount = 10000;
         runtime·precisestack = haveexperiment("precisestack");
 
-        runtime·mprofinit();
         runtime·mallocinit();
         mcommoninit(m);
 ········
         // Initialize the itable value for newErrorCString,
         // so that the next time it gets called, possibly
         // in a fault during a garbage collection, it will not
         // need to allocated memory.
         runtime·newErrorCString(0, &i);
 
         runtime·goargs();
@@ skipping 50 matching lines @@
         // by calling runtime.LockOSThread during initialization
         // to preserve the lock.
         runtime·lockOSThread();
 ········
         // Defer unlock so that runtime.Goexit during init does the unlock too.
         d.fn = &initDone;
         d.siz = 0;
         d.link = g->defer;
         d.argp = (void*)-1;
         d.special = true;
-        d.free = false;
         g->defer = &d;
 
         if(m != &runtime·m0)
                 runtime·throw("runtime·main not on m0");
         runtime·newproc1(&scavenger, nil, 0, 0, runtime·main);
         main·init();
 
         if(g->defer != &d || d.fn != &initDone)
                 runtime·throw("runtime: bad defer entry after init");
         g->defer = d.link;
@@ skipping 12 matching lines @@
 
         runtime·exit(0);
         for(;;)
                 *(int32*)runtime·main = 0;
 }
 
 void
 runtime·goroutineheader(G *gp)
 {
         int8 *status;
+        int64 waitfor;
 
         switch(gp->status) {
         case Gidle:
                 status = "idle";
                 break;
         case Grunnable:
                 status = "runnable";
                 break;
         case Grunning:
                 status = "running";
                 break;
         case Gsyscall:
                 status = "syscall";
                 break;
         case Gwaiting:
                 if(gp->waitreason)
                         status = gp->waitreason;
                 else
                         status = "waiting";
                 break;
         default:
                 status = "???";
                 break;
         }
-        runtime·printf("goroutine %D [%s]:\n", gp->goid, status);
+
+        // approx time the G is blocked, in minutes
+        waitfor = 0;
+        if((gp->status == Gwaiting || gp->status == Gsyscall) && gp->waitsince != 0)
+                waitfor = (runtime·nanotime() - gp->waitsince) / (60LL*1000*1000*1000);
+
+        if(waitfor < 1)
+                runtime·printf("goroutine %D [%s]:\n", gp->goid, status);
+        else
+                runtime·printf("goroutine %D [%s, %D minutes]:\n", gp->goid, status, waitfor);
 }
 
 void
 runtime·tracebackothers(G *me)
 {
         G *gp;
         int32 traceback;
+        uintptr i;
 
         traceback = runtime·gotraceback(nil);
 ········
         // Show the current goroutine first, if we haven't already.
         if((gp = m->curg) != nil && gp != me) {
                 runtime·printf("\n");
                 runtime·goroutineheader(gp);
                 runtime·traceback(~(uintptr)0, ~(uintptr)0, 0, gp);
         }
 
-        for(gp = runtime·allg; gp != nil; gp = gp->alllink) {
+        runtime·lock(&allglock);
+        for(i = 0; i < runtime·allglen; i++) {
+                gp = runtime·allg[i];
                 if(gp == me || gp == m->curg || gp->status == Gdead)
                         continue;
                 if(gp->issystem && traceback < 2)
                         continue;
                 runtime·printf("\n");
                 runtime·goroutineheader(gp);
                 if(gp->status == Grunning) {
                         runtime·printf("\tgoroutine running on other thread; stack unavailable\n");
                         runtime·printcreatedby(gp);
                 } else
                         runtime·traceback(~(uintptr)0, ~(uintptr)0, 0, gp);
         }
+        runtime·unlock(&allglock);
 }
 
 static void
 checkmcount(void)
 {
         // sched lock is held
         if(runtime·sched.mcount > runtime·sched.maxmcount) {
                 runtime·printf("runtime: program exceeds %d-thread limit\n", runtime·sched.maxmcount);
                 runtime·throw("thread exhaustion");
         }
@@ skipping 308 matching lines @@
 // When running with cgo, we call _cgo_thread_start
 // to start threads for us so that we can play nicely with
 // foreign code.
 void (*_cgo_thread_start)(void*);
 
 typedef struct CgoThreadStart CgoThreadStart;
 struct CgoThreadStart
 {
         M *m;
         G *g;
+        uintptr *tls;
         void (*fn)(void);
 };
 
 // Allocate a new m unassociated with any thread.
 // Can use p for allocation context if needed.
 M*
 runtime·allocm(P *p)
 {
         M *mp;
         static Type *mtype;  // The Go type M
 
         m->locks++;  // disable GC because it can be called from sysmon
         if(m->p == nil)
                 acquirep(p);  // temporarily borrow p for mallocs in this function
         if(mtype == nil) {
                 Eface e;
                 runtime·gc_m_ptr(&e);
                 mtype = ((PtrType*)e.type)->elem;
         }
 
         mp = runtime·cnew(mtype);
         mcommoninit(mp);
 
-        // In case of cgo, pthread_create will make us a stack.
+        // In case of cgo or Solaris, pthread_create will make us a stack.
         // Windows will layout sched stack on OS stack.
-        if(runtime·iscgo || Windows)
+        if(runtime·iscgo || Solaris || Windows)
                 mp->g0 = runtime·malg(-1);
         else
                 mp->g0 = runtime·malg(8192);
 
         if(p == m->p)
                 releasep();
         m->locks--;
         if(m->locks == 0 && g->preempt)  // restore the preemption request in case we've cleared it in newstack
                 g->stackguard0 = StackPreempt;
 
@@ skipping 117 matching lines @@
         gp->syscallguard = gp->stackguard;
         gp->status = Gsyscall;
         mp->curg = gp;
         mp->locked = LockInternal;
         mp->lockedg = gp;
         gp->lockedm = mp;
         gp->goid = runtime·xadd64(&runtime·sched.goidgen, 1);
         if(raceenabled)
                 gp->racectx = runtime·racegostart(runtime·newextram);
         // put on allg for garbage collector
-        runtime·lock(&runtime·sched);
-        if(runtime·lastg == nil)
-                runtime·allg = gp;
-        else
-                runtime·lastg->alllink = gp;
-        runtime·lastg = gp;
-        runtime·unlock(&runtime·sched);
+        allgadd(gp);
 
         // Add m to the extra list.
         mnext = lockextra(true);
         mp->schedlink = mnext;
         unlockextra(mp);
 }
 
 // dropm is called when a cgo callback has called needm but is now
 // done with the callback and returning back into the non-Go thread.
 // It puts the current m back onto the extra list.
@@ skipping 94 matching lines @@
         mp->nextp = p;
         mp->mstartfn = fn;
 
         if(runtime·iscgo) {
                 CgoThreadStart ts;
 
                 if(_cgo_thread_start == nil)
                         runtime·throw("_cgo_thread_start missing");
                 ts.m = mp;
                 ts.g = mp->g0;
+                ts.tls = mp->tls;
                 ts.fn = runtime·mstart;
                 runtime·asmcgocall(_cgo_thread_start, &ts);
                 return;
         }
         runtime·newosproc(mp, (byte*)mp->g0->stackbase);
 }
 
 // Stops execution of the current m until new work is available.
 // Returns with acquired P.
 static void
@@ skipping 24 matching lines @@
         m->nextp = nil;
 }
 
 static void
 mspinning(void)
 {
         m->spinning = true;
 }
 
 // Schedules some M to run the p (creates an M if necessary).
-// If p==nil, tries to get an idle P, if no idle P's returns false.
+// If p==nil, tries to get an idle P, if no idle P's does nothing.
 static void
 startm(P *p, bool spinning)
 {
         M *mp;
         void (*fn)(void);
 
         runtime·lock(&runtime·sched);
         if(p == nil) {
                 p = pidleget();
                 if(p == nil) {
@@ skipping 143 matching lines @@
 static void
 execute(G *gp)
 {
         int32 hz;
 
         if(gp->status != Grunnable) {
                 runtime·printf("execute: bad g status %d\n", gp->status);
                 runtime·throw("execute: bad g status");
         }
         gp->status = Grunning;
+        gp->waitsince = 0;
         gp->preempt = false;
         gp->stackguard0 = gp->stackguard;
         m->p->schedtick++;
         m->curg = gp;
         gp->m = m;
 
         // Check whether the profiler needs to be turned on or off.
         hz = runtime·sched.profilehz;
         if(m->profilehz != hz)
                 runtime·resetcpuprofiler(hz);
@@ skipping 403 matching lines @@
 // from the low-level system calls used by the runtime.
 #pragma textflag NOSPLIT
 void
 runtime·exitsyscall(void)
 {
         m->locks++;  // see comment in entersyscall
 
         if(g->isbackground)  // do not consider blocked scavenger for deadlock detection
                 incidlelocked(-1);
 
+        g->waitsince = 0;
         if(exitsyscallfast()) {
                 // There's a cpu for us, so we can run.
                 m->p->syscalltick++;
                 g->status = Grunning;
                 // Garbage collector isn't running (since we are),
                 // so okay to clear gcstack and gcsp.
                 g->syscallstack = (uintptr)nil;
                 g->syscallsp = (uintptr)nil;
                 m->locks--;
                 if(g->preempt) {
@@ skipping 202 matching lines @@
         // Not worth it: this is almost always an error.
         if(siz > StackMin - 1024)
                 runtime·throw("runtime.newproc: function arguments too large for new goroutine");
 
         p = m->p;
         if((newg = gfget(p)) != nil) {
                 if(newg->stackguard - StackGuard != newg->stack0)
                         runtime·throw("invalid stack in newg");
         } else {
                 newg = runtime·malg(StackMin);
-                runtime·lock(&runtime·sched);
-                if(runtime·lastg == nil)
-                        runtime·allg = newg;
-                else
-                        runtime·lastg->alllink = newg;
-                runtime·lastg = newg;
-                runtime·unlock(&runtime·sched);
+                allgadd(newg);
         }
 
         sp = (byte*)newg->stackbase;
         sp -= siz;
         runtime·memmove(sp, argp, narg);
         if(thechar == '5') {
                 // caller's LR
                 sp -= sizeof(void*);
                 *(void**)sp = nil;
         }
@@ skipping 14 matching lines @@
         if(raceenabled)
                 newg->racectx = runtime·racegostart((void*)callerpc);
         runqput(p, newg);
 
         if(runtime·atomicload(&runtime·sched.npidle) != 0 && runtime·atomicload(&runtime·sched.nmspinning) == 0 && fn->fn != runtime·main)  // TODO: fast atomic
                 wakep();
         m->locks--;
         if(m->locks == 0 && g->preempt)  // restore the preemption request in case we've cleared it in newstack
                 g->stackguard0 = StackPreempt;
         return newg;
+}
+
+static void
+allgadd(G *gp)
+{
+        G **new;
+        uintptr cap;
+
+        runtime·lock(&allglock);
+        if(runtime·allglen >= allgcap) {
+                cap = 4096/sizeof(new[0]);
+                if(cap < 2*allgcap)
+                        cap = 2*allgcap;
+                new = runtime·malloc(cap*sizeof(new[0]));
+                if(new == nil)
+                        runtime·throw("runtime: cannot allocate memory");
+                if(runtime·allg != nil) {
+                        runtime·memmove(new, runtime·allg, runtime·allglen*sizeof(new[0]));
+                        runtime·free(runtime·allg);
+                }
+                runtime·allg = new;
+                allgcap = cap;
+        }
+        runtime·allg[runtime·allglen++] = gp;
+        runtime·unlock(&allglock);
 }
 
 // Put on gfree list.
 // If local list is too long, transfer a batch to the global list.
 static void
 gfput(P *p, G *gp)
 {
         if(gp->stackguard - StackGuard != gp->stack0)
                 runtime·throw("invalid stack in gfput");
         gp->schedlink = p->gfree;
@@ skipping 171 matching lines @@
 {
         ret = runtime·gcount();
         FLUSH(&ret);
 }
 
 int32
 runtime·gcount(void)
 {
         G *gp;
         int32 n, s;
+        uintptr i;
 
         n = 0;
-        runtime·lock(&runtime·sched);
+        runtime·lock(&allglock);
         // TODO(dvyukov): runtime.NumGoroutine() is O(N).
         // We do not want to increment/decrement centralized counter in newproc/goexit,
         // just to make runtime.NumGoroutine() faster.
         // Compromise solution is to introduce per-P counters of active goroutines.
-        for(gp = runtime·allg; gp; gp = gp->alllink) {
+        for(i = 0; i < runtime·allglen; i++) {
+                gp = runtime·allg[i];
                 s = gp->status;
                 if(s == Grunnable || s == Grunning || s == Gsyscall || s == Gwaiting)
                         n++;
         }
-        runtime·unlock(&runtime·sched);
+        runtime·unlock(&allglock);
         return n;
 }
 
 int32
 runtime·mcount(void)
 {
         return runtime·sched.mcount;
 }
 
 void
@@ skipping 23 matching lines @@
         uintptr pcbuf[100];
 } prof;
 
 static void
 System(void)
 {
 }
 
 // Called if we receive a SIGPROF signal.
 void
-runtime·sigprof(uint8 *pc, uint8 *sp, uint8 *lr, G *gp)
+runtime·sigprof(uint8 *pc, uint8 *sp, uint8 *lr, G *gp, M *mp)
 {
         int32 n;
         bool traceback;
+        MCache *mcache;
+        // Do not use global m in this function, use mp instead.
+        // On windows one m is sending reports about all the g's, so m means a wrong thing.
+        byte m;
+
+        m = 0;
+        USED(m);
 
         if(prof.fn == nil || prof.hz == 0)
                 return;
-        traceback = true;
-        // Windows does profiling in a dedicated thread w/o m.
-        if(!Windows && (m == nil || m->mcache == nil))
-                traceback = false;
- ·······
+
+        // Profiling runs concurrently with GC, so it must not allocate.
+        mcache = mp->mcache;
+        mp->mcache = nil;
+
         // Define that a "user g" is a user-created goroutine, and a "system g"
         // is one that is m->g0 or m->gsignal. We've only made sure that we
         // can unwind user g's, so exclude the system g's.
         //
         // It is not quite as easy as testing gp == m->curg (the current user g)
         // because we might be interrupted for profiling halfway through a
         // goroutine switch. The switch involves updating three (or four) values:
         // g, PC, SP, and (on arm) LR. The PC must be the last to be updated,
         // because once it gets updated the new g is running.
         //
@@ skipping 52 matching lines @@
         // The biggest drawback to this solution is that it requires that we can tell
         // whether it's safe to read from the memory pointed at by PC.
         // In a correct program, we can test PC == nil and otherwise read,
         // but if a profiling signal happens at the instant that a program executes
         // a bad jump (before the program manages to handle the resulting fault)
         // the profiling handler could fault trying to read nonexistent memory.
         //
         // To recap, there are no constraints on the assembly being used for the
         // transition. We simply require that g and SP match and that the PC is not
         // in runtime.gogo.
-        //
-        // On Windows, one m is sending reports about all the g's, so gp == m->curg
-        // is not a useful comparison. The profilem function in os_windows.c has
-        // already checked that gp is a user g.
-        if(gp == nil ||
-           (!Windows && gp != m->curg) ||
+        traceback = true;
+        if(gp == nil || gp != mp->curg ||
            (uintptr)sp < gp->stackguard - StackGuard || gp->stackbase < (uintptr)sp ||
            ((uint8*)runtime·gogo <= pc && pc < (uint8*)runtime·gogo + RuntimeGogoBytes))
                 traceback = false;
 
         // Race detector calls asmcgocall w/o entersyscall/exitsyscall,
         // we can not currently unwind through asmcgocall.
-        if(m != nil && m->racecall)
+        if(mp != nil && mp->racecall)
                 traceback = false;
 
         runtime·lock(&prof);
         if(prof.fn == nil) {
                 runtime·unlock(&prof);
+                mp->mcache = mcache;
                 return;
         }
         n = 0;
         if(traceback)
                 n = runtime·gentraceback((uintptr)pc, (uintptr)sp, (uintptr)lr, gp, 0, prof.pcbuf, nelem(prof.pcbuf), nil, nil, false);
         if(!traceback || n <= 0) {
                 n = 2;
                 prof.pcbuf[0] = (uintptr)pc;
                 prof.pcbuf[1] = (uintptr)System + 1;
         }
         prof.fn(prof.pcbuf, n);
         runtime·unlock(&prof);
+        mp->mcache = mcache;
 }
 
 // Arrange to call fn with a traceback hz times a second.
 void
 runtime·setcpuprofilerate(void (*fn)(uintptr*, int32), int32 hz)
 {
         // Force sane arguments.
         if(hz < 0)
                 hz = 0;
         if(hz == 0)
@@ skipping 22 matching lines @@
                 runtime·resetcpuprofiler(hz);
 
         m->locks--;
 }
 
 // Change number of processors.  The world is stopped, sched is locked.
 static void
 procresize(int32 new)
 {
         int32 i, old;
+        bool empty;
         G *gp;
         P *p;
 
         old = runtime·gomaxprocs;
         if(old < 0 || old > MaxGomaxprocs || new <= 0 || new >MaxGomaxprocs)
                 runtime·throw("procresize: invalid arg");
         // initialize new P's
         for(i = 0; i < new; i++) {
                 p = runtime·allp[i];
                 if(p == nil) {
                         p = (P*)runtime·mallocgc(sizeof(*p), 0, FlagNoInvokeGC);
                         p->id = i;
                         p->status = Pgcstop;
                         runtime·atomicstorep(&runtime·allp[i], p);
                 }
                 if(p->mcache == nil) {
                         if(old==0 && i==0)
                                 p->mcache = m->mcache;  // bootstrap
                         else
                                 p->mcache = runtime·allocmcache();
                 }
-                if(p->runq == nil) {
-                        p->runqsize = 128;
-                        p->runq = (G**)runtime·mallocgc(p->runqsize*sizeof(G*), 0, FlagNoInvokeGC);
-                }
         }
 
         // redistribute runnable G's evenly
-        for(i = 0; i < old; i++) {
-                p = runtime·allp[i];
-                while(gp = runqget(p))
-                        globrunqput(gp);
-        }
+        // collect all runnable goroutines in global queue preserving FIFO order
+        // FIFO order is required to ensure fairness even during frequent GCs
+        // see http://golang.org/issue/7126
+        empty = false;
+        while(!empty) {
+                empty = true;
+                for(i = 0; i < old; i++) {
+                        p = runtime·allp[i];
+                        if(p->runqhead == p->runqtail)
+                                continue;
+                        empty = false;
+                        // pop from tail of local queue
+                        p->runqtail--;
+                        gp = p->runq[p->runqtail%nelem(p->runq)];
+                        // push onto head of global queue
+                        gp->schedlink = runtime·sched.runqhead;
+                        runtime·sched.runqhead = gp;
+                        if(runtime·sched.runqtail == nil)
+                                runtime·sched.runqtail = gp;
+                        runtime·sched.runqsize++;
+                }
+        }
+        // fill local queues with at most nelem(p->runq)/2 goroutines
         // start at 1 because current M already executes some G and will acquire allp[0] below,
         // so if we have a spare G we want to put it into allp[1].
-        for(i = 1; runtime·sched.runqhead; i++) {
+        for(i = 1; i < new * nelem(p->runq)/2 && runtime·sched.runqsize > 0; i++) {
                 gp = runtime·sched.runqhead;
                 runtime·sched.runqhead = gp->schedlink;
+                if(runtime·sched.runqhead == nil)
+                        runtime·sched.runqtail = nil;
+                runtime·sched.runqsize--;
                 runqput(runtime·allp[i%new], gp);
         }
-        runtime·sched.runqtail = nil;
-        runtime·sched.runqsize = 0;
 
         // free unused P's
         for(i = new; i < old; i++) {
                 p = runtime·allp[i];
                 runtime·freemcache(p->mcache);
                 p->mcache = nil;
                 gfpurge(p);
                 p->status = Pdead;
                 // can't free P itself because it can be referenced by an M in syscall
         }
@@ skipping 61 matching lines @@
         runtime·unlock(&runtime·sched);
 }
 
 // Check for deadlock situation.
 // The check is based on number of running M's, if 0 -> deadlock.
 static void
 checkdead(void)
 {
         G *gp;
         int32 run, grunning, s;
+        uintptr i;
 
         // -1 for sysmon
         run = runtime·sched.mcount - runtime·sched.nmidle - runtime·sched.nmidlelocked - 1;
         if(run > 0)
                 return;
         if(run < 0) {
                 runtime·printf("checkdead: nmidle=%d nmidlelocked=%d mcount=%d\n",
                         runtime·sched.nmidle, runtime·sched.nmidlelocked, runtime·sched.mcount);
                 runtime·throw("checkdead: inconsistent counts");
         }
         grunning = 0;
-        for(gp = runtime·allg; gp; gp = gp->alllink) {
+        runtime·lock(&allglock);
+        for(i = 0; i < runtime·allglen; i++) {
+                gp = runtime·allg[i];
                 if(gp->isbackground)
                         continue;
                 s = gp->status;
                 if(s == Gwaiting)
                         grunning++;
                 else if(s == Grunnable || s == Grunning || s == Gsyscall) {
+                        runtime·unlock(&allglock);
                         runtime·printf("checkdead: find g %D in status %d\n", gp->goid, s);
                         runtime·throw("checkdead: runnable g");
                 }
         }
+        runtime·unlock(&allglock);
         if(grunning == 0)  // possible if main goroutine calls runtime·Goexit()
                 runtime·exit(0);
         m->throwing = -1;  // do not dump full stacks
         runtime·throw("all goroutines are asleep - deadlock!");
 }
 
 static void
 sysmon(void)
 {
         uint32 idle, delay;
@@ skipping 165 matching lines @@
         gp->stackguard0 = StackPreempt;
         return true;
 }
 
 void
 runtime·schedtrace(bool detailed)
 {
         static int64 starttime;
         int64 now;
         int64 id1, id2, id3;
-        int32 i, q, t, h, s;
+        int32 i, t, h;
+        uintptr gi;
         int8 *fmt;
         M *mp, *lockedm;
         G *gp, *lockedg;
         P *p;
 
         now = runtime·nanotime();
         if(starttime == 0)
                 starttime = now;
 
         runtime·lock(&runtime·sched);
         runtime·printf("SCHED %Dms: gomaxprocs=%d idleprocs=%d threads=%d idlethreads=%d runqueue=%d",
                 (now-starttime)/1000000, runtime·gomaxprocs, runtime·sched.npidle, runtime·sched.mcount,
                 runtime·sched.nmidle, runtime·sched.runqsize);
         if(detailed) {
                 runtime·printf(" gcwaiting=%d nmidlelocked=%d nmspinning=%d stopwait=%d sysmonwait=%d\n",
                         runtime·sched.gcwaiting, runtime·sched.nmidlelocked, runtime·sched.nmspinning,
                         runtime·sched.stopwait, runtime·sched.sysmonwait);
         }
         // We must be careful while reading data from P's, M's and G's.
         // Even if we hold schedlock, most data can be changed concurrently.
         // E.g. (p->m ? p->m->id : -1) can crash if p->m changes from non-nil to nil.
         for(i = 0; i < runtime·gomaxprocs; i++) {
                 p = runtime·allp[i];
                 if(p == nil)
                         continue;
                 mp = p->m;
-                t = p->runqtail;
-                h = p->runqhead;
-                s = p->runqsize;
-                q = t - h;
-                if(q < 0)
-                        q += s;
+                h = runtime·atomicload(&p->runqhead);
+                t = runtime·atomicload(&p->runqtail);
                 if(detailed)
-                        runtime·printf("  P%d: status=%d schedtick=%d syscalltick=%d m=%d runqsize=%d/%d gfreecnt=%d\n",
-                                i, p->status, p->schedtick, p->syscalltick, mp ? mp->id : -1, q, s, p->gfreecnt);
+                        runtime·printf("  P%d: status=%d schedtick=%d syscalltick=%d m=%d runqsize=%d gfreecnt=%d\n",
+                                i, p->status, p->schedtick, p->syscalltick, mp ? mp->id : -1, t-h, p->gfreecnt);
                 else {
                         // In non-detailed mode format lengths of per-P run queues as:
                         // [len1 len2 len3 len4]
                         fmt = " %d";
                         if(runtime·gomaxprocs == 1)
                                 fmt = " [%d]\n";
                         else if(i == 0)
                                 fmt = " [%d";
                         else if(i == runtime·gomaxprocs-1)
                                 fmt = " %d]\n";
-                        runtime·printf(fmt, q);
+                        runtime·printf(fmt, t-h);
                 }
         }
         if(!detailed) {
                 runtime·unlock(&runtime·sched);
                 return;
         }
         for(mp = runtime·allm; mp; mp = mp->alllink) {
                 p = mp->p;
                 gp = mp->curg;
                 lockedg = mp->lockedg;
                 id1 = -1;
                 if(p)
                         id1 = p->id;
                 id2 = -1;
                 if(gp)
                         id2 = gp->goid;
                 id3 = -1;
                 if(lockedg)
                         id3 = lockedg->goid;
                 runtime·printf("  M%d: p=%D curg=%D mallocing=%d throwing=%d gcing=%d"
                         " locks=%d dying=%d helpgc=%d spinning=%d lockedg=%D\n",
                         mp->id, id1, id2,
                         mp->mallocing, mp->throwing, mp->gcing, mp->locks, mp->dying, mp->helpgc,
                         mp->spinning, id3);
         }
-        for(gp = runtime·allg; gp; gp = gp->alllink) {
+        runtime·lock(&allglock);
+        for(gi = 0; gi < runtime·allglen; gi++) {
+                gp = runtime·allg[gi];
                 mp = gp->m;
                 lockedm = gp->lockedm;
                 runtime·printf("  G%D: status=%d(%s) m=%d lockedm=%d\n",
                         gp->goid, gp->status, gp->waitreason, mp ? mp->id : -1,
                         lockedm ? lockedm->id : -1);
         }
+        runtime·unlock(&allglock);
         runtime·unlock(&runtime·sched);
 }
 
 // Put mp on midle list.
 // Sched must be locked.
 static void
 mput(M *mp)
 {
         mp->schedlink = runtime·sched.midle;
         runtime·sched.midle = mp;
@@ skipping 22 matching lines @@
 {
         gp->schedlink = nil;
         if(runtime·sched.runqtail)
                 runtime·sched.runqtail->schedlink = gp;
         else
                 runtime·sched.runqhead = gp;
         runtime·sched.runqtail = gp;
         runtime·sched.runqsize++;
 }
 
+// Put a batch of runnable goroutines on the global runnable queue.
+// Sched must be locked.
+static void
+globrunqputbatch(G *ghead, G *gtail, int32 n)
+{
+        gtail->schedlink = nil;
+        if(runtime·sched.runqtail)
+                runtime·sched.runqtail->schedlink = ghead;
+        else
+                runtime·sched.runqhead = ghead;
+        runtime·sched.runqtail = gtail;
+        runtime·sched.runqsize += n;
+}
+
 // Try get a batch of G's from the global runnable queue.
 // Sched must be locked.
 static G*
 globrunqget(P *p, int32 max)
 {
         G *gp, *gp1;
         int32 n;
 
         if(runtime·sched.runqsize == 0)
                 return nil;
         n = runtime·sched.runqsize/runtime·gomaxprocs+1;
         if(n > runtime·sched.runqsize)
                 n = runtime·sched.runqsize;
         if(max > 0 && n > max)
                 n = max;
+        if(n > nelem(p->runq)/2)
+                n = nelem(p->runq)/2;
         runtime·sched.runqsize -= n;
         if(runtime·sched.runqsize == 0)
                 runtime·sched.runqtail = nil;
         gp = runtime·sched.runqhead;
         runtime·sched.runqhead = gp->schedlink;
         n--;
         while(n--) {
                 gp1 = runtime·sched.runqhead;
                 runtime·sched.runqhead = gp1->schedlink;
                 runqput(p, gp1);
@@ skipping 19 matching lines @@
         P *p;
 
         p = runtime·sched.pidle;
         if(p) {
                 runtime·sched.pidle = p->link;
                 runtime·xadd(&runtime·sched.npidle, -1);  // TODO: fast atomic
         }
         return p;
 }
 
-// Put g on local runnable queue.
-// TODO(dvyukov): consider using lock-free queue.
+// Try to put g on local runnable queue.
+// If it's full, put onto global queue.
+// Executed only by the owner P.
 static void
 runqput(P *p, G *gp)
 {
-        int32 h, t, s;
-
-        runtime·lock(p);
+        uint32 h, t;
+
 retry:
-        h = p->runqhead;
+        h = runtime·atomicload(&p->runqhead);  // load-acquire, synchronize with consumers
         t = p->runqtail;
-        s = p->runqsize;
-        if(t == h-1 || (h == 0 && t == s-1)) {
-                runqgrow(p);
-                goto retry;
-        }
-        p->runq[t++] = gp;
-        if(t == s)
-                t = 0;
-        p->runqtail = t;
-        runtime·unlock(p);
+        if(t - h < nelem(p->runq)) {
+                p->runq[t%nelem(p->runq)] = gp;
+                runtime·atomicstore(&p->runqtail, t+1);  // store-release, makes the item available for consumption
+                return;
+        }
+        if(runqputslow(p, gp, h, t))
+                return;
+        // the queue is not full, now the put above must suceed
+        goto retry;
+}
+
+// Put g and a batch of work from local runnable queue on global queue.
+// Executed only by the owner P.
+static bool
+runqputslow(P *p, G *gp, uint32 h, uint32 t)
+{
+        G *batch[nelem(p->runq)/2+1];
+        uint32 n, i;
+
+        // First, grab a batch from local queue.
+        n = t-h;
+        n = n/2;
+        if(n != nelem(p->runq)/2)
+                runtime·throw("runqputslow: queue is not full");
+        for(i=0; i<n; i++)
+                batch[i] = p->runq[(h+i)%nelem(p->runq)];
+        if(!runtime·cas(&p->runqhead, h, h+n))  // cas-release, commits consume
+                return false;
+        batch[n] = gp;
+        // Link the goroutines.
+        for(i=0; i<n; i++)
+                batch[i]->schedlink = batch[i+1];
+        // Now put the batch on global queue.
+        runtime·lock(&runtime·sched);
+        globrunqputbatch(batch[0], batch[n], n+1);
+        runtime·unlock(&runtime·sched);
+        return true;
 }
 
 // Get g from local runnable queue.
+// Executed only by the owner P.
 static G*
 runqget(P *p)
 {
         G *gp;
-        int32 t, h, s;
-
-        if(p->runqhead == p->runqtail)
-                return nil;
-        runtime·lock(p);
-        h = p->runqhead;
-        t = p->runqtail;
-        s = p->runqsize;
-        if(t == h) {
-                runtime·unlock(p);
-                return nil;
-        }
-        gp = p->runq[h++];
-        if(h == s)
-                h = 0;
-        p->runqhead = h;
-        runtime·unlock(p);
-        return gp;
-}
-
-// Grow local runnable queue.
-// TODO(dvyukov): consider using fixed-size array
-// and transfer excess to the global list (local queue can grow way too big).
-static void
-runqgrow(P *p)
-{
-        G **q;
-        int32 s, t, h, t2;
-
-        h = p->runqhead;
-        t = p->runqtail;
-        s = p->runqsize;
-        t2 = 0;
-        q = runtime·malloc(2*s*sizeof(*q));
-        while(t != h) {
-                q[t2++] = p->runq[h++];
-                if(h == s)
-                        h = 0;
-        }
-        runtime·free(p->runq);
-        p->runq = q;
-        p->runqhead = 0;
-        p->runqtail = t2;
-        p->runqsize = 2*s;
+        uint32 t, h;
+
+        for(;;) {
+                h = runtime·atomicload(&p->runqhead);  // load-acquire, synchronize with other consumers
+                t = p->runqtail;
+                if(t == h)
+                        return nil;
+                gp = p->runq[h%nelem(p->runq)];
+                if(runtime·cas(&p->runqhead, h, h+1))  // cas-release, commits consume
+                        return gp;
+        }
+}
+
+// Grabs a batch of goroutines from local runnable queue.
+// batch array must be of size nelem(p->runq)/2. Returns number of grabbed goroutines.
+// Can be executed by any P.
+static uint32
+runqgrab(P *p, G **batch)
+{
+        uint32 t, h, n, i;
+
+        for(;;) {
+                h = runtime·atomicload(&p->runqhead);  // load-acquire, synchronize with other consumers
+                t = runtime·atomicload(&p->runqtail);  // load-acquire, synchronize with the producer
+                n = t-h;
+                n = n - n/2;
+                if(n == 0)
+                        break;
+                if(n > nelem(p->runq)/2)  // read inconsistent h and t
+                        continue;
+                for(i=0; i<n; i++)
+                        batch[i] = p->runq[(h+i)%nelem(p->runq)];
+                if(runtime·cas(&p->runqhead, h, h+n))  // cas-release, commits consume
+                        break;
+        }
+        return n;
 }
 
 // Steal half of elements from local runnable queue of p2
 // and put onto local runnable queue of p.
 // Returns one of the stolen elements (or nil if failed).
 static G*
 runqsteal(P *p, P *p2)
 {
-        G *gp, *gp1;
-        int32 t, h, s, t2, h2, s2, c, i;
-
-        if(p2->runqhead == p2->runqtail)
+        G *gp;
+        G *batch[nelem(p->runq)/2];
+        uint32 t, h, n, i;
+
+        n = runqgrab(p2, batch);
+        if(n == 0)
                 return nil;
-        // sort locks to prevent deadlocks
-        if(p < p2)
-                runtime·lock(p);
-        runtime·lock(p2);
-        if(p2->runqhead == p2->runqtail) {
-                runtime·unlock(p2);
-                if(p < p2)
-                        runtime·unlock(p);
-                return nil;
-        }
-        if(p >= p2)
-                runtime·lock(p);
-        // now we've locked both queues and know the victim is not empty
-        h = p->runqhead;
+        n--;
+        gp = batch[n];
+        if(n == 0)
+                return gp;
+        h = runtime·atomicload(&p->runqhead);  // load-acquire, synchronize with consumers
         t = p->runqtail;
-        s = p->runqsize;
-        h2 = p2->runqhead;
-        t2 = p2->runqtail;
-        s2 = p2->runqsize;
-        gp = p2->runq[h2++];  // return value
-        if(h2 == s2)
-                h2 = 0;
-        // steal roughly half
-        if(t2 > h2)
-                c = (t2 - h2) / 2;
-        else
-                c = (s2 - h2 + t2) / 2;
-        // copy
-        for(i = 0; i != c; i++) {
-                // the target queue is full?
-                if(t == h-1 || (h == 0 && t == s-1))
-                        break;
-                // the victim queue is empty?
-                if(t2 == h2)
-                        break;
-                gp1 = p2->runq[h2++];
-                if(h2 == s2)
-                        h2 = 0;
-                p->runq[t++] = gp1;
-                if(t == s)
-                        t = 0;
-        }
-        p->runqtail = t;
-        p2->runqhead = h2;
-        runtime·unlock(p2);
-        runtime·unlock(p);
+        if(t - h + n >= nelem(p->runq))
+                runtime·throw("runqsteal: runq overflow");
+        for(i=0; i<n; i++, t++)
+                p->runq[t%nelem(p->runq)] = batch[i];
+        runtime·atomicstore(&p->runqtail, t);  // store-release, makes the item available for consumption
         return gp;
 }
 
 void
 runtime·testSchedLocalQueue(void)
 {
         P p;
-        G gs[1000];
+        G gs[nelem(p.runq)];
         int32 i, j;
 
         runtime·memclr((byte*)&p, sizeof(p));
-        p.runqsize = 1;
-        p.runqhead = 0;
-        p.runqtail = 0;
-        p.runq = runtime·malloc(p.runqsize*sizeof(*p.runq));
 
         for(i = 0; i < nelem(gs); i++) {
                 if(runqget(&p) != nil)
                         runtime·throw("runq is not empty initially");
                 for(j = 0; j < i; j++)
                         runqput(&p, &gs[i]);
                 for(j = 0; j < i; j++) {
                         if(runqget(&p) != &gs[i]) {
                                 runtime·printf("bad element at iter %d/%d\n", i, j);
                                 runtime·throw("bad element");
                         }
                 }
                 if(runqget(&p) != nil)
                         runtime·throw("runq is not empty afterwards");
         }
 }
 
 void
 runtime·testSchedLocalQueueSteal(void)
 {
         P p1, p2;
-        G gs[1000], *gp;
+        G gs[nelem(p1.runq)], *gp;
         int32 i, j, s;
 
         runtime·memclr((byte*)&p1, sizeof(p1));
-        p1.runqsize = 1;
-        p1.runqhead = 0;
-        p1.runqtail = 0;
-        p1.runq = runtime·malloc(p1.runqsize*sizeof(*p1.runq));
-
         runtime·memclr((byte*)&p2, sizeof(p2));
-        p2.runqsize = nelem(gs);
-        p2.runqhead = 0;
-        p2.runqtail = 0;
-        p2.runq = runtime·malloc(p2.runqsize*sizeof(*p2.runq));
 
         for(i = 0; i < nelem(gs); i++) {
                 for(j = 0; j < i; j++) {
                         gs[j].sig = 0;
                         runqput(&p1, &gs[j]);
                 }
                 gp = runqsteal(&p2, &p1);
                 s = 0;
                 if(gp) {
                         s++;
@@ skipping 57 matching lines @@
                                 if(experiment[i+j] != name[j])
                                         goto nomatch;
                         if(experiment[i+j] != '\0' && experiment[i+j] != ',')
                                 goto nomatch;
                         return 1;
                 }
         nomatch:;
         }
         return 0;
 }