OSDN Git Service

94c2a51730e944e93f0e976c878057819f8afd67
[pf3gnuchains/gcc-fork.git] / libgo / runtime / proc.c
1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 #include <limits.h>
6 #include <stdlib.h>
7 #include <pthread.h>
8 #include <unistd.h>
9
10 #include "config.h"
11 #include "runtime.h"
12 #include "arch.h"
13 #include "defs.h"
14 #include "malloc.h"
15 #include "go-defer.h"
16
17 #ifdef USING_SPLIT_STACK
18
19 /* FIXME: These are not declared anywhere.  */
20
21 extern void __splitstack_getcontext(void *context[10]);
22
23 extern void __splitstack_setcontext(void *context[10]);
24
25 extern void *__splitstack_makecontext(size_t, void *context[10], size_t *);
26
27 extern void * __splitstack_resetcontext(void *context[10], size_t *);
28
29 extern void *__splitstack_find(void *, void *, size_t *, void **, void **,
30                                void **);
31
32 extern void __splitstack_block_signals (int *, int *);
33
34 extern void __splitstack_block_signals_context (void *context[10], int *,
35                                                 int *);
36
37 #endif
38
39 #if defined(USING_SPLIT_STACK) && defined(LINKER_SUPPORTS_SPLIT_STACK)
40 # ifdef PTHREAD_STACK_MIN
41 #  define StackMin PTHREAD_STACK_MIN
42 # else
43 #  define StackMin 8192
44 # endif
45 #else
46 # define StackMin 2 * 1024 * 1024
47 #endif
48
49 static void schedule(G*);
50
51 typedef struct Sched Sched;
52
53 M       runtime_m0;
54 G       runtime_g0;     // idle goroutine for m0
55
56 #ifdef __rtems__
57 #define __thread
58 #endif
59
60 static __thread G *g;
61 static __thread M *m;
62
63 #ifndef SETCONTEXT_CLOBBERS_TLS
64
65 static inline void
66 initcontext(void)
67 {
68 }
69
70 static inline void
71 fixcontext(ucontext_t *c __attribute__ ((unused)))
72 {
73 }
74
75 # else
76
77 # if defined(__x86_64__) && defined(__sun__)
78
79 // x86_64 Solaris 10 and 11 have a bug: setcontext switches the %fs
80 // register to that of the thread which called getcontext.  The effect
81 // is that the address of all __thread variables changes.  This bug
82 // also affects pthread_self() and pthread_getspecific.  We work
83 // around it by clobbering the context field directly to keep %fs the
84 // same.
85
86 static __thread greg_t fs;
87
88 static inline void
89 initcontext(void)
90 {
91         ucontext_t c;
92
93         getcontext(&c);
94         fs = c.uc_mcontext.gregs[REG_FSBASE];
95 }
96
97 static inline void
98 fixcontext(ucontext_t* c)
99 {
100         c->uc_mcontext.gregs[REG_FSBASE] = fs;
101 }
102
103 # else
104
105 #  error unknown case for SETCONTEXT_CLOBBERS_TLS
106
107 # endif
108
109 #endif
110
111 // We can not always refer to the TLS variables directly.  The
112 // compiler will call tls_get_addr to get the address of the variable,
113 // and it may hold it in a register across a call to schedule.  When
114 // we get back from the call we may be running in a different thread,
115 // in which case the register now points to the TLS variable for a
116 // different thread.  We use non-inlinable functions to avoid this
117 // when necessary.
118
119 G* runtime_g(void) __attribute__ ((noinline, no_split_stack));
120
121 G*
122 runtime_g(void)
123 {
124         return g;
125 }
126
127 M* runtime_m(void) __attribute__ ((noinline, no_split_stack));
128
129 M*
130 runtime_m(void)
131 {
132         return m;
133 }
134
135 int32   runtime_gcwaiting;
136
137 // Go scheduler
138 //
139 // The go scheduler's job is to match ready-to-run goroutines (`g's)
140 // with waiting-for-work schedulers (`m's).  If there are ready g's
141 // and no waiting m's, ready() will start a new m running in a new
142 // OS thread, so that all ready g's can run simultaneously, up to a limit.
143 // For now, m's never go away.
144 //
145 // By default, Go keeps only one kernel thread (m) running user code
146 // at a single time; other threads may be blocked in the operating system.
147 // Setting the environment variable $GOMAXPROCS or calling
148 // runtime.GOMAXPROCS() will change the number of user threads
149 // allowed to execute simultaneously.  $GOMAXPROCS is thus an
150 // approximation of the maximum number of cores to use.
151 //
152 // Even a program that can run without deadlock in a single process
153 // might use more m's if given the chance.  For example, the prime
154 // sieve will use as many m's as there are primes (up to runtime_sched.mmax),
155 // allowing different stages of the pipeline to execute in parallel.
156 // We could revisit this choice, only kicking off new m's for blocking
157 // system calls, but that would limit the amount of parallel computation
158 // that go would try to do.
159 //
160 // In general, one could imagine all sorts of refinements to the
161 // scheduler, but the goal now is just to get something working on
162 // Linux and OS X.
163
164 struct Sched {
165         Lock;
166
167         G *gfree;       // available g's (status == Gdead)
168         int32 goidgen;
169
170         G *ghead;       // g's waiting to run
171         G *gtail;
172         int32 gwait;    // number of g's waiting to run
173         int32 gcount;   // number of g's that are alive
174         int32 grunning; // number of g's running on cpu or in syscall
175
176         M *mhead;       // m's waiting for work
177         int32 mwait;    // number of m's waiting for work
178         int32 mcount;   // number of m's that have been created
179
180         volatile uint32 atomic; // atomic scheduling word (see below)
181
182         int32 profilehz;        // cpu profiling rate
183
184         bool init;  // running initialization
185         bool lockmain;  // init called runtime.LockOSThread
186
187         Note    stopped;        // one g can set waitstop and wait here for m's to stop
188 };
189
190 // The atomic word in sched is an atomic uint32 that
191 // holds these fields.
192 //
193 //      [15 bits] mcpu          number of m's executing on cpu
194 //      [15 bits] mcpumax       max number of m's allowed on cpu
195 //      [1 bit] waitstop        some g is waiting on stopped
196 //      [1 bit] gwaiting        gwait != 0
197 //
198 // These fields are the information needed by entersyscall
199 // and exitsyscall to decide whether to coordinate with the
200 // scheduler.  Packing them into a single machine word lets
201 // them use a fast path with a single atomic read/write and
202 // no lock/unlock.  This greatly reduces contention in
203 // syscall- or cgo-heavy multithreaded programs.
204 //
205 // Except for entersyscall and exitsyscall, the manipulations
206 // to these fields only happen while holding the schedlock,
207 // so the routines holding schedlock only need to worry about
208 // what entersyscall and exitsyscall do, not the other routines
209 // (which also use the schedlock).
210 //
211 // In particular, entersyscall and exitsyscall only read mcpumax,
212 // waitstop, and gwaiting.  They never write them.  Thus, writes to those
213 // fields can be done (holding schedlock) without fear of write conflicts.
214 // There may still be logic conflicts: for example, the set of waitstop must
215 // be conditioned on mcpu >= mcpumax or else the wait may be a
216 // spurious sleep.  The Promela model in proc.p verifies these accesses.
217 enum {
218         mcpuWidth = 15,
219         mcpuMask = (1<<mcpuWidth) - 1,
220         mcpuShift = 0,
221         mcpumaxShift = mcpuShift + mcpuWidth,
222         waitstopShift = mcpumaxShift + mcpuWidth,
223         gwaitingShift = waitstopShift+1,
224
225         // The max value of GOMAXPROCS is constrained
226         // by the max value we can store in the bit fields
227         // of the atomic word.  Reserve a few high values
228         // so that we can detect accidental decrement
229         // beyond zero.
230         maxgomaxprocs = mcpuMask - 10,
231 };
232
233 #define atomic_mcpu(v)          (((v)>>mcpuShift)&mcpuMask)
234 #define atomic_mcpumax(v)       (((v)>>mcpumaxShift)&mcpuMask)
235 #define atomic_waitstop(v)      (((v)>>waitstopShift)&1)
236 #define atomic_gwaiting(v)      (((v)>>gwaitingShift)&1)
237
238 Sched runtime_sched;
239 int32 runtime_gomaxprocs;
240 bool runtime_singleproc;
241
242 static bool canaddmcpu(void);
243
244 // An m that is waiting for notewakeup(&m->havenextg).  This may
245 // only be accessed while the scheduler lock is held.  This is used to
246 // minimize the number of times we call notewakeup while the scheduler
247 // lock is held, since the m will normally move quickly to lock the
248 // scheduler itself, producing lock contention.
249 static M* mwakeup;
250
251 // Scheduling helpers.  Sched must be locked.
252 static void gput(G*);   // put/get on ghead/gtail
253 static G* gget(void);
254 static void mput(M*);   // put/get on mhead
255 static M* mget(G*);
256 static void gfput(G*);  // put/get on gfree
257 static G* gfget(void);
258 static void matchmg(void);      // match m's to g's
259 static void readylocked(G*);    // ready, but sched is locked
260 static void mnextg(M*, G*);
261 static void mcommoninit(M*);
262
263 void
264 setmcpumax(uint32 n)
265 {
266         uint32 v, w;
267
268         for(;;) {
269                 v = runtime_sched.atomic;
270                 w = v;
271                 w &= ~(mcpuMask<<mcpumaxShift);
272                 w |= n<<mcpumaxShift;
273                 if(runtime_cas(&runtime_sched.atomic, v, w))
274                         break;
275         }
276 }
277
278 // First function run by a new goroutine.  This replaces gogocall.
279 static void
280 kickoff(void)
281 {
282         void (*fn)(void*);
283
284         fn = (void (*)(void*))(g->entry);
285         fn(g->param);
286         runtime_goexit();
287 }
288
289 // Switch context to a different goroutine.  This is like longjmp.
290 static void runtime_gogo(G*) __attribute__ ((noinline));
291 static void
292 runtime_gogo(G* newg)
293 {
294 #ifdef USING_SPLIT_STACK
295         __splitstack_setcontext(&newg->stack_context[0]);
296 #endif
297         g = newg;
298         newg->fromgogo = true;
299         fixcontext(&newg->context);
300         setcontext(&newg->context);
301         runtime_throw("gogo setcontext returned");
302 }
303
304 // Save context and call fn passing g as a parameter.  This is like
305 // setjmp.  Because getcontext always returns 0, unlike setjmp, we use
306 // g->fromgogo as a code.  It will be true if we got here via
307 // setcontext.  g == nil the first time this is called in a new m.
308 static void runtime_mcall(void (*)(G*)) __attribute__ ((noinline));
309 static void
310 runtime_mcall(void (*pfn)(G*))
311 {
312 #ifndef USING_SPLIT_STACK
313         int i;
314 #endif
315
316         // Ensure that all registers are on the stack for the garbage
317         // collector.
318         __builtin_unwind_init();
319
320         if(g == m->g0)
321                 runtime_throw("runtime: mcall called on m->g0 stack");
322
323         if(g != nil) {
324
325 #ifdef USING_SPLIT_STACK
326                 __splitstack_getcontext(&g->stack_context[0]);
327 #else
328                 g->gcnext_sp = &i;
329 #endif
330                 g->fromgogo = false;
331                 getcontext(&g->context);
332         }
333         if (g == nil || !g->fromgogo) {
334 #ifdef USING_SPLIT_STACK
335                 __splitstack_setcontext(&m->g0->stack_context[0]);
336 #endif
337                 m->g0->entry = (byte*)pfn;
338                 m->g0->param = g;
339                 g = m->g0;
340                 fixcontext(&m->g0->context);
341                 setcontext(&m->g0->context);
342                 runtime_throw("runtime: mcall function returned");
343         }
344 }
345
346 // The bootstrap sequence is:
347 //
348 //      call osinit
349 //      call schedinit
350 //      make & queue new G
351 //      call runtime_mstart
352 //
353 // The new G calls runtime_main.
354 void
355 runtime_schedinit(void)
356 {
357         int32 n;
358         const byte *p;
359
360         m = &runtime_m0;
361         g = &runtime_g0;
362         m->g0 = g;
363         m->curg = g;
364         g->m = m;
365
366         initcontext();
367
368         m->nomemprof++;
369         runtime_mallocinit();
370         mcommoninit(m);
371
372         runtime_goargs();
373         runtime_goenvs();
374
375         // For debugging:
376         // Allocate internal symbol table representation now,
377         // so that we don't need to call malloc when we crash.
378         // runtime_findfunc(0);
379
380         runtime_gomaxprocs = 1;
381         p = runtime_getenv("GOMAXPROCS");
382         if(p != nil && (n = runtime_atoi(p)) != 0) {
383                 if(n > maxgomaxprocs)
384                         n = maxgomaxprocs;
385                 runtime_gomaxprocs = n;
386         }
387         setmcpumax(runtime_gomaxprocs);
388         runtime_singleproc = runtime_gomaxprocs == 1;
389
390         canaddmcpu();   // mcpu++ to account for bootstrap m
391         m->helpgc = 1;  // flag to tell schedule() to mcpu--
392         runtime_sched.grunning++;
393
394         // Can not enable GC until all roots are registered.
395         // mstats.enablegc = 1;
396         m->nomemprof--;
397 }
398
399 extern void main_init(void) __asm__ ("__go_init_main");
400 extern void main_main(void) __asm__ ("main.main");
401
402 // The main goroutine.
403 void
404 runtime_main(void)
405 {
406         // Lock the main goroutine onto this, the main OS thread,
407         // during initialization.  Most programs won't care, but a few
408         // do require certain calls to be made by the main thread.
409         // Those can arrange for main.main to run in the main thread
410         // by calling runtime.LockOSThread during initialization
411         // to preserve the lock.
412         runtime_LockOSThread();
413         runtime_sched.init = true;
414         main_init();
415         runtime_sched.init = false;
416         if(!runtime_sched.lockmain)
417                 runtime_UnlockOSThread();
418
419         // For gccgo we have to wait until after main is initialized
420         // to enable GC, because initializing main registers the GC
421         // roots.
422         mstats.enablegc = 1;
423
424         main_main();
425         runtime_exit(0);
426         for(;;)
427                 *(int32*)0 = 0;
428 }
429
430 // Lock the scheduler.
431 static void
432 schedlock(void)
433 {
434         runtime_lock(&runtime_sched);
435 }
436
437 // Unlock the scheduler.
438 static void
439 schedunlock(void)
440 {
441         M *m;
442
443         m = mwakeup;
444         mwakeup = nil;
445         runtime_unlock(&runtime_sched);
446         if(m != nil)
447                 runtime_notewakeup(&m->havenextg);
448 }
449
450 void
451 runtime_goexit(void)
452 {
453         g->status = Gmoribund;
454         runtime_gosched();
455 }
456
457 void
458 runtime_goroutineheader(G *g)
459 {
460         const char *status;
461
462         switch(g->status) {
463         case Gidle:
464                 status = "idle";
465                 break;
466         case Grunnable:
467                 status = "runnable";
468                 break;
469         case Grunning:
470                 status = "running";
471                 break;
472         case Gsyscall:
473                 status = "syscall";
474                 break;
475         case Gwaiting:
476                 if(g->waitreason)
477                         status = g->waitreason;
478                 else
479                         status = "waiting";
480                 break;
481         case Gmoribund:
482                 status = "moribund";
483                 break;
484         default:
485                 status = "???";
486                 break;
487         }
488         runtime_printf("goroutine %d [%s]:\n", g->goid, status);
489 }
490
491 void
492 runtime_tracebackothers(G *me)
493 {
494         G *g;
495
496         for(g = runtime_allg; g != nil; g = g->alllink) {
497                 if(g == me || g->status == Gdead)
498                         continue;
499                 runtime_printf("\n");
500                 runtime_goroutineheader(g);
501                 // runtime_traceback(g->sched.pc, g->sched.sp, 0, g);
502         }
503 }
504
505 // Mark this g as m's idle goroutine.
506 // This functionality might be used in environments where programs
507 // are limited to a single thread, to simulate a select-driven
508 // network server.  It is not exposed via the standard runtime API.
509 void
510 runtime_idlegoroutine(void)
511 {
512         if(g->idlem != nil)
513                 runtime_throw("g is already an idle goroutine");
514         g->idlem = m;
515 }
516
517 static void
518 mcommoninit(M *m)
519 {
520         // Add to runtime_allm so garbage collector doesn't free m
521         // when it is just in a register or thread-local storage.
522         m->alllink = runtime_allm;
523         // runtime_Cgocalls() iterates over allm w/o schedlock,
524         // so we need to publish it safely.
525         runtime_atomicstorep((void**)&runtime_allm, m);
526
527         m->id = runtime_sched.mcount++;
528         m->fastrand = 0x49f6428aUL + m->id + runtime_cputicks();
529
530         if(m->mcache == nil)
531                 m->mcache = runtime_allocmcache();
532 }
533
534 // Try to increment mcpu.  Report whether succeeded.
535 static bool
536 canaddmcpu(void)
537 {
538         uint32 v;
539
540         for(;;) {
541                 v = runtime_sched.atomic;
542                 if(atomic_mcpu(v) >= atomic_mcpumax(v))
543                         return 0;
544                 if(runtime_cas(&runtime_sched.atomic, v, v+(1<<mcpuShift)))
545                         return 1;
546         }
547 }
548
549 // Put on `g' queue.  Sched must be locked.
550 static void
551 gput(G *g)
552 {
553         M *m;
554
555         // If g is wired, hand it off directly.
556         if((m = g->lockedm) != nil && canaddmcpu()) {
557                 mnextg(m, g);
558                 return;
559         }
560
561         // If g is the idle goroutine for an m, hand it off.
562         if(g->idlem != nil) {
563                 if(g->idlem->idleg != nil) {
564                         runtime_printf("m%d idle out of sync: g%d g%d\n",
565                                 g->idlem->id,
566                                 g->idlem->idleg->goid, g->goid);
567                         runtime_throw("runtime: double idle");
568                 }
569                 g->idlem->idleg = g;
570                 return;
571         }
572
573         g->schedlink = nil;
574         if(runtime_sched.ghead == nil)
575                 runtime_sched.ghead = g;
576         else
577                 runtime_sched.gtail->schedlink = g;
578         runtime_sched.gtail = g;
579
580         // increment gwait.
581         // if it transitions to nonzero, set atomic gwaiting bit.
582         if(runtime_sched.gwait++ == 0)
583                 runtime_xadd(&runtime_sched.atomic, 1<<gwaitingShift);
584 }
585
586 // Report whether gget would return something.
587 static bool
588 haveg(void)
589 {
590         return runtime_sched.ghead != nil || m->idleg != nil;
591 }
592
593 // Get from `g' queue.  Sched must be locked.
594 static G*
595 gget(void)
596 {
597         G *g;
598
599         g = runtime_sched.ghead;
600         if(g){
601                 runtime_sched.ghead = g->schedlink;
602                 if(runtime_sched.ghead == nil)
603                         runtime_sched.gtail = nil;
604                 // decrement gwait.
605                 // if it transitions to zero, clear atomic gwaiting bit.
606                 if(--runtime_sched.gwait == 0)
607                         runtime_xadd(&runtime_sched.atomic, -1<<gwaitingShift);
608         } else if(m->idleg != nil) {
609                 g = m->idleg;
610                 m->idleg = nil;
611         }
612         return g;
613 }
614
615 // Put on `m' list.  Sched must be locked.
616 static void
617 mput(M *m)
618 {
619         m->schedlink = runtime_sched.mhead;
620         runtime_sched.mhead = m;
621         runtime_sched.mwait++;
622 }
623
624 // Get an `m' to run `g'.  Sched must be locked.
625 static M*
626 mget(G *g)
627 {
628         M *m;
629
630         // if g has its own m, use it.
631         if(g && (m = g->lockedm) != nil)
632                 return m;
633
634         // otherwise use general m pool.
635         if((m = runtime_sched.mhead) != nil){
636                 runtime_sched.mhead = m->schedlink;
637                 runtime_sched.mwait--;
638         }
639         return m;
640 }
641
642 // Mark g ready to run.
643 void
644 runtime_ready(G *g)
645 {
646         schedlock();
647         readylocked(g);
648         schedunlock();
649 }
650
651 // Mark g ready to run.  Sched is already locked.
652 // G might be running already and about to stop.
653 // The sched lock protects g->status from changing underfoot.
654 static void
655 readylocked(G *g)
656 {
657         if(g->m){
658                 // Running on another machine.
659                 // Ready it when it stops.
660                 g->readyonstop = 1;
661                 return;
662         }
663
664         // Mark runnable.
665         if(g->status == Grunnable || g->status == Grunning) {
666                 runtime_printf("goroutine %d has status %d\n", g->goid, g->status);
667                 runtime_throw("bad g->status in ready");
668         }
669         g->status = Grunnable;
670
671         gput(g);
672         matchmg();
673 }
674
675 // Same as readylocked but a different symbol so that
676 // debuggers can set a breakpoint here and catch all
677 // new goroutines.
678 static void
679 newprocreadylocked(G *g)
680 {
681         readylocked(g);
682 }
683
684 // Pass g to m for running.
685 // Caller has already incremented mcpu.
686 static void
687 mnextg(M *m, G *g)
688 {
689         runtime_sched.grunning++;
690         m->nextg = g;
691         if(m->waitnextg) {
692                 m->waitnextg = 0;
693                 if(mwakeup != nil)
694                         runtime_notewakeup(&mwakeup->havenextg);
695                 mwakeup = m;
696         }
697 }
698
699 // Get the next goroutine that m should run.
700 // Sched must be locked on entry, is unlocked on exit.
701 // Makes sure that at most $GOMAXPROCS g's are
702 // running on cpus (not in system calls) at any given time.
703 static G*
704 nextgandunlock(void)
705 {
706         G *gp;
707         uint32 v;
708
709 top:
710         if(atomic_mcpu(runtime_sched.atomic) >= maxgomaxprocs)
711                 runtime_throw("negative mcpu");
712
713         // If there is a g waiting as m->nextg, the mcpu++
714         // happened before it was passed to mnextg.
715         if(m->nextg != nil) {
716                 gp = m->nextg;
717                 m->nextg = nil;
718                 schedunlock();
719                 return gp;
720         }
721
722         if(m->lockedg != nil) {
723                 // We can only run one g, and it's not available.
724                 // Make sure some other cpu is running to handle
725                 // the ordinary run queue.
726                 if(runtime_sched.gwait != 0) {
727                         matchmg();
728                         // m->lockedg might have been on the queue.
729                         if(m->nextg != nil) {
730                                 gp = m->nextg;
731                                 m->nextg = nil;
732                                 schedunlock();
733                                 return gp;
734                         }
735                 }
736         } else {
737                 // Look for work on global queue.
738                 while(haveg() && canaddmcpu()) {
739                         gp = gget();
740                         if(gp == nil)
741                                 runtime_throw("gget inconsistency");
742
743                         if(gp->lockedm) {
744                                 mnextg(gp->lockedm, gp);
745                                 continue;
746                         }
747                         runtime_sched.grunning++;
748                         schedunlock();
749                         return gp;
750                 }
751
752                 // The while loop ended either because the g queue is empty
753                 // or because we have maxed out our m procs running go
754                 // code (mcpu >= mcpumax).  We need to check that
755                 // concurrent actions by entersyscall/exitsyscall cannot
756                 // invalidate the decision to end the loop.
757                 //
758                 // We hold the sched lock, so no one else is manipulating the
759                 // g queue or changing mcpumax.  Entersyscall can decrement
760                 // mcpu, but if does so when there is something on the g queue,
761                 // the gwait bit will be set, so entersyscall will take the slow path
762                 // and use the sched lock.  So it cannot invalidate our decision.
763                 //
764                 // Wait on global m queue.
765                 mput(m);
766         }
767
768         v = runtime_atomicload(&runtime_sched.atomic);
769         if(runtime_sched.grunning == 0)
770                 runtime_throw("all goroutines are asleep - deadlock!");
771         m->nextg = nil;
772         m->waitnextg = 1;
773         runtime_noteclear(&m->havenextg);
774
775         // Stoptheworld is waiting for all but its cpu to go to stop.
776         // Entersyscall might have decremented mcpu too, but if so
777         // it will see the waitstop and take the slow path.
778         // Exitsyscall never increments mcpu beyond mcpumax.
779         if(atomic_waitstop(v) && atomic_mcpu(v) <= atomic_mcpumax(v)) {
780                 // set waitstop = 0 (known to be 1)
781                 runtime_xadd(&runtime_sched.atomic, -1<<waitstopShift);
782                 runtime_notewakeup(&runtime_sched.stopped);
783         }
784         schedunlock();
785
786         runtime_notesleep(&m->havenextg);
787         if(m->helpgc) {
788                 runtime_gchelper();
789                 m->helpgc = 0;
790                 runtime_lock(&runtime_sched);
791                 goto top;
792         }
793         if((gp = m->nextg) == nil)
794                 runtime_throw("bad m->nextg in nextgoroutine");
795         m->nextg = nil;
796         return gp;
797 }
798
799 int32
800 runtime_helpgc(bool *extra)
801 {
802         M *mp;
803         int32 n, max;
804
805         // Figure out how many CPUs to use.
806         // Limited by gomaxprocs, number of actual CPUs, and MaxGcproc.
807         max = runtime_gomaxprocs;
808         if(max > runtime_ncpu)
809                 max = runtime_ncpu > 0 ? runtime_ncpu : 1;
810         if(max > MaxGcproc)
811                 max = MaxGcproc;
812
813         // We're going to use one CPU no matter what.
814         // Figure out the max number of additional CPUs.
815         max--;
816
817         runtime_lock(&runtime_sched);
818         n = 0;
819         while(n < max && (mp = mget(nil)) != nil) {
820                 n++;
821                 mp->helpgc = 1;
822                 mp->waitnextg = 0;
823                 runtime_notewakeup(&mp->havenextg);
824         }
825         runtime_unlock(&runtime_sched);
826         if(extra)
827                 *extra = n != max;
828         return n;
829 }
830
831 void
832 runtime_stoptheworld(void)
833 {
834         uint32 v;
835
836         schedlock();
837         runtime_gcwaiting = 1;
838
839         setmcpumax(1);
840
841         // while mcpu > 1
842         for(;;) {
843                 v = runtime_sched.atomic;
844                 if(atomic_mcpu(v) <= 1)
845                         break;
846
847                 // It would be unsafe for multiple threads to be using
848                 // the stopped note at once, but there is only
849                 // ever one thread doing garbage collection.
850                 runtime_noteclear(&runtime_sched.stopped);
851                 if(atomic_waitstop(v))
852                         runtime_throw("invalid waitstop");
853
854                 // atomic { waitstop = 1 }, predicated on mcpu <= 1 check above
855                 // still being true.
856                 if(!runtime_cas(&runtime_sched.atomic, v, v+(1<<waitstopShift)))
857                         continue;
858
859                 schedunlock();
860                 runtime_notesleep(&runtime_sched.stopped);
861                 schedlock();
862         }
863         runtime_singleproc = runtime_gomaxprocs == 1;
864         schedunlock();
865 }
866
867 void
868 runtime_starttheworld(bool extra)
869 {
870         M *m;
871
872         schedlock();
873         runtime_gcwaiting = 0;
874         setmcpumax(runtime_gomaxprocs);
875         matchmg();
876         if(extra && canaddmcpu()) {
877                 // Start a new m that will (we hope) be idle
878                 // and so available to help when the next
879                 // garbage collection happens.
880                 // canaddmcpu above did mcpu++
881                 // (necessary, because m will be doing various
882                 // initialization work so is definitely running),
883                 // but m is not running a specific goroutine,
884                 // so set the helpgc flag as a signal to m's
885                 // first schedule(nil) to mcpu-- and grunning--.
886                 m = runtime_newm();
887                 m->helpgc = 1;
888                 runtime_sched.grunning++;
889         }
890         schedunlock();
891 }
892
893 // Called to start an M.
894 void*
895 runtime_mstart(void* mp)
896 {
897         m = (M*)mp;
898         g = m->g0;
899
900         initcontext();
901
902         g->entry = nil;
903         g->param = nil;
904
905         // Record top of stack for use by mcall.
906         // Once we call schedule we're never coming back,
907         // so other calls can reuse this stack space.
908 #ifdef USING_SPLIT_STACK
909         __splitstack_getcontext(&g->stack_context[0]);
910 #else
911         g->gcinitial_sp = &mp;
912         // Setting gcstack_size to 0 is a marker meaning that gcinitial_sp
913         // is the top of the stack, not the bottom.
914         g->gcstack_size = 0;
915         g->gcnext_sp = &mp;
916 #endif
917         getcontext(&g->context);
918
919         if(g->entry != nil) {
920                 // Got here from mcall.
921                 void (*pfn)(G*) = (void (*)(G*))g->entry;
922                 G* gp = (G*)g->param;
923                 pfn(gp);
924                 *(int*)0x21 = 0x21;
925         }
926         runtime_minit();
927
928 #ifdef USING_SPLIT_STACK
929         {
930           int dont_block_signals = 0;
931           __splitstack_block_signals(&dont_block_signals, nil);
932         }
933 #endif
934
935         schedule(nil);
936         return nil;
937 }
938
939 typedef struct CgoThreadStart CgoThreadStart;
940 struct CgoThreadStart
941 {
942         M *m;
943         G *g;
944         void (*fn)(void);
945 };
946
947 // Kick off new m's as needed (up to mcpumax).
948 // Sched is locked.
949 static void
950 matchmg(void)
951 {
952         G *gp;
953         M *mp;
954
955         if(m->mallocing || m->gcing)
956                 return;
957
958         while(haveg() && canaddmcpu()) {
959                 gp = gget();
960                 if(gp == nil)
961                         runtime_throw("gget inconsistency");
962
963                 // Find the m that will run gp.
964                 if((mp = mget(gp)) == nil)
965                         mp = runtime_newm();
966                 mnextg(mp, gp);
967         }
968 }
969
970 // Create a new m.  It will start off with a call to runtime_mstart.
971 M*
972 runtime_newm(void)
973 {
974         M *m;
975         pthread_attr_t attr;
976         pthread_t tid;
977
978         m = runtime_malloc(sizeof(M));
979         mcommoninit(m);
980         m->g0 = runtime_malg(-1, nil, nil);
981
982         if(pthread_attr_init(&attr) != 0)
983                 runtime_throw("pthread_attr_init");
984         if(pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED) != 0)
985                 runtime_throw("pthread_attr_setdetachstate");
986
987 #ifndef PTHREAD_STACK_MIN
988 #define PTHREAD_STACK_MIN 8192
989 #endif
990         if(pthread_attr_setstacksize(&attr, PTHREAD_STACK_MIN) != 0)
991                 runtime_throw("pthread_attr_setstacksize");
992
993         if(pthread_create(&tid, &attr, runtime_mstart, m) != 0)
994                 runtime_throw("pthread_create");
995
996         return m;
997 }
998
999 // One round of scheduler: find a goroutine and run it.
1000 // The argument is the goroutine that was running before
1001 // schedule was called, or nil if this is the first call.
1002 // Never returns.
1003 static void
1004 schedule(G *gp)
1005 {
1006         int32 hz;
1007         uint32 v;
1008
1009         schedlock();
1010         if(gp != nil) {
1011                 // Just finished running gp.
1012                 gp->m = nil;
1013                 runtime_sched.grunning--;
1014
1015                 // atomic { mcpu-- }
1016                 v = runtime_xadd(&runtime_sched.atomic, -1<<mcpuShift);
1017                 if(atomic_mcpu(v) > maxgomaxprocs)
1018                         runtime_throw("negative mcpu in scheduler");
1019
1020                 switch(gp->status){
1021                 case Grunnable:
1022                 case Gdead:
1023                         // Shouldn't have been running!
1024                         runtime_throw("bad gp->status in sched");
1025                 case Grunning:
1026                         gp->status = Grunnable;
1027                         gput(gp);
1028                         break;
1029                 case Gmoribund:
1030                         gp->status = Gdead;
1031                         if(gp->lockedm) {
1032                                 gp->lockedm = nil;
1033                                 m->lockedg = nil;
1034                         }
1035                         gp->idlem = nil;
1036                         gfput(gp);
1037                         if(--runtime_sched.gcount == 0)
1038                                 runtime_exit(0);
1039                         break;
1040                 }
1041                 if(gp->readyonstop){
1042                         gp->readyonstop = 0;
1043                         readylocked(gp);
1044                 }
1045         } else if(m->helpgc) {
1046                 // Bootstrap m or new m started by starttheworld.
1047                 // atomic { mcpu-- }
1048                 v = runtime_xadd(&runtime_sched.atomic, -1<<mcpuShift);
1049                 if(atomic_mcpu(v) > maxgomaxprocs)
1050                         runtime_throw("negative mcpu in scheduler");
1051                 // Compensate for increment in starttheworld().
1052                 runtime_sched.grunning--;
1053                 m->helpgc = 0;
1054         } else if(m->nextg != nil) {
1055                 // New m started by matchmg.
1056         } else {
1057                 runtime_throw("invalid m state in scheduler");
1058         }
1059
1060         // Find (or wait for) g to run.  Unlocks runtime_sched.
1061         gp = nextgandunlock();
1062         gp->readyonstop = 0;
1063         gp->status = Grunning;
1064         m->curg = gp;
1065         gp->m = m;
1066
1067         // Check whether the profiler needs to be turned on or off.
1068         hz = runtime_sched.profilehz;
1069         if(m->profilehz != hz)
1070                 runtime_resetcpuprofiler(hz);
1071
1072         runtime_gogo(gp);
1073 }
1074
1075 // Enter scheduler.  If g->status is Grunning,
1076 // re-queues g and runs everyone else who is waiting
1077 // before running g again.  If g->status is Gmoribund,
1078 // kills off g.
1079 void
1080 runtime_gosched(void)
1081 {
1082         if(m->locks != 0)
1083                 runtime_throw("gosched holding locks");
1084         if(g == m->g0)
1085                 runtime_throw("gosched of g0");
1086         runtime_mcall(schedule);
1087 }
1088
1089 // The goroutine g is about to enter a system call.
1090 // Record that it's not using the cpu anymore.
1091 // This is called only from the go syscall library and cgocall,
1092 // not from the low-level system calls used by the runtime.
1093 //
1094 // Entersyscall cannot split the stack: the runtime_gosave must
1095 // make g->sched refer to the caller's stack segment, because
1096 // entersyscall is going to return immediately after.
1097 // It's okay to call matchmg and notewakeup even after
1098 // decrementing mcpu, because we haven't released the
1099 // sched lock yet, so the garbage collector cannot be running.
1100
1101 void runtime_entersyscall(void) __attribute__ ((no_split_stack));
1102
1103 void
1104 runtime_entersyscall(void)
1105 {
1106         uint32 v;
1107
1108         // Leave SP around for gc and traceback.
1109 #ifdef USING_SPLIT_STACK
1110         g->gcstack = __splitstack_find(NULL, NULL, &g->gcstack_size,
1111                                        &g->gcnext_segment, &g->gcnext_sp,
1112                                        &g->gcinitial_sp);
1113 #else
1114         g->gcnext_sp = (byte *) &v;
1115 #endif
1116
1117         // Save the registers in the g structure so that any pointers
1118         // held in registers will be seen by the garbage collector.
1119         // We could use getcontext here, but setjmp is more efficient
1120         // because it doesn't need to save the signal mask.
1121         setjmp(g->gcregs);
1122
1123         g->status = Gsyscall;
1124
1125         // Fast path.
1126         // The slow path inside the schedlock/schedunlock will get
1127         // through without stopping if it does:
1128         //      mcpu--
1129         //      gwait not true
1130         //      waitstop && mcpu <= mcpumax not true
1131         // If we can do the same with a single atomic add,
1132         // then we can skip the locks.
1133         v = runtime_xadd(&runtime_sched.atomic, -1<<mcpuShift);
1134         if(!atomic_gwaiting(v) && (!atomic_waitstop(v) || atomic_mcpu(v) > atomic_mcpumax(v)))
1135                 return;
1136
1137         schedlock();
1138         v = runtime_atomicload(&runtime_sched.atomic);
1139         if(atomic_gwaiting(v)) {
1140                 matchmg();
1141                 v = runtime_atomicload(&runtime_sched.atomic);
1142         }
1143         if(atomic_waitstop(v) && atomic_mcpu(v) <= atomic_mcpumax(v)) {
1144                 runtime_xadd(&runtime_sched.atomic, -1<<waitstopShift);
1145                 runtime_notewakeup(&runtime_sched.stopped);
1146         }
1147
1148         schedunlock();
1149 }
1150
1151 // The goroutine g exited its system call.
1152 // Arrange for it to run on a cpu again.
1153 // This is called only from the go syscall library, not
1154 // from the low-level system calls used by the runtime.
1155 void
1156 runtime_exitsyscall(void)
1157 {
1158         G *gp;
1159         uint32 v;
1160
1161         // Fast path.
1162         // If we can do the mcpu++ bookkeeping and
1163         // find that we still have mcpu <= mcpumax, then we can
1164         // start executing Go code immediately, without having to
1165         // schedlock/schedunlock.
1166         gp = g;
1167         v = runtime_xadd(&runtime_sched.atomic, (1<<mcpuShift));
1168         if(m->profilehz == runtime_sched.profilehz && atomic_mcpu(v) <= atomic_mcpumax(v)) {
1169                 // There's a cpu for us, so we can run.
1170                 gp->status = Grunning;
1171                 // Garbage collector isn't running (since we are),
1172                 // so okay to clear gcstack.
1173 #ifdef USING_SPLIT_STACK
1174                 gp->gcstack = nil;
1175 #endif
1176                 gp->gcnext_sp = nil;
1177                 runtime_memclr(gp->gcregs, sizeof gp->gcregs);
1178                 return;
1179         }
1180
1181         // Tell scheduler to put g back on the run queue:
1182         // mostly equivalent to g->status = Grunning,
1183         // but keeps the garbage collector from thinking
1184         // that g is running right now, which it's not.
1185         gp->readyonstop = 1;
1186
1187         // All the cpus are taken.
1188         // The scheduler will ready g and put this m to sleep.
1189         // When the scheduler takes g away from m,
1190         // it will undo the runtime_sched.mcpu++ above.
1191         runtime_gosched();
1192
1193         // Gosched returned, so we're allowed to run now.
1194         // Delete the gcstack information that we left for
1195         // the garbage collector during the system call.
1196         // Must wait until now because until gosched returns
1197         // we don't know for sure that the garbage collector
1198         // is not running.
1199 #ifdef USING_SPLIT_STACK
1200         gp->gcstack = nil;
1201 #endif
1202         gp->gcnext_sp = nil;
1203         runtime_memclr(gp->gcregs, sizeof gp->gcregs);
1204 }
1205
1206 // Allocate a new g, with a stack big enough for stacksize bytes.
1207 G*
1208 runtime_malg(int32 stacksize, byte** ret_stack, size_t* ret_stacksize)
1209 {
1210         G *newg;
1211
1212         newg = runtime_malloc(sizeof(G));
1213         if(stacksize >= 0) {
1214 #if USING_SPLIT_STACK
1215                 int dont_block_signals = 0;
1216
1217                 *ret_stack = __splitstack_makecontext(stacksize,
1218                                                       &newg->stack_context[0],
1219                                                       ret_stacksize);
1220                 __splitstack_block_signals_context(&newg->stack_context[0],
1221                                                    &dont_block_signals, nil);
1222 #else
1223                 *ret_stack = runtime_mallocgc(stacksize, FlagNoProfiling|FlagNoGC, 0, 0);
1224                 *ret_stacksize = stacksize;
1225                 newg->gcinitial_sp = *ret_stack;
1226                 newg->gcstack_size = stacksize;
1227 #endif
1228         }
1229         return newg;
1230 }
1231
1232 /* For runtime package testing.  */
1233
1234 void runtime_testing_entersyscall(void)
1235   __asm__("libgo_runtime.runtime.entersyscall");
1236
1237 void
1238 runtime_testing_entersyscall()
1239 {
1240         runtime_entersyscall();
1241 }
1242
1243 void runtime_testing_exitsyscall(void)
1244   __asm__("libgo_runtime.runtime.exitsyscall");
1245
1246 void
1247 runtime_testing_exitsyscall()
1248 {
1249         runtime_exitsyscall();
1250 }
1251
1252 G*
1253 __go_go(void (*fn)(void*), void* arg)
1254 {
1255         byte *sp;
1256         size_t spsize;
1257         G * volatile newg;      // volatile to avoid longjmp warning
1258
1259         schedlock();
1260
1261         if((newg = gfget()) != nil){
1262 #ifdef USING_SPLIT_STACK
1263                 int dont_block_signals = 0;
1264
1265                 sp = __splitstack_resetcontext(&newg->stack_context[0],
1266                                                &spsize);
1267                 __splitstack_block_signals_context(&newg->stack_context[0],
1268                                                    &dont_block_signals, nil);
1269 #else
1270                 sp = newg->gcinitial_sp;
1271                 spsize = newg->gcstack_size;
1272                 if(spsize == 0)
1273                         runtime_throw("bad spsize in __go_go");
1274                 newg->gcnext_sp = sp;
1275 #endif
1276         } else {
1277                 newg = runtime_malg(StackMin, &sp, &spsize);
1278                 if(runtime_lastg == nil)
1279                         runtime_allg = newg;
1280                 else
1281                         runtime_lastg->alllink = newg;
1282                 runtime_lastg = newg;
1283         }
1284         newg->status = Gwaiting;
1285         newg->waitreason = "new goroutine";
1286
1287         newg->entry = (byte*)fn;
1288         newg->param = arg;
1289         newg->gopc = (uintptr)__builtin_return_address(0);
1290
1291         runtime_sched.gcount++;
1292         runtime_sched.goidgen++;
1293         newg->goid = runtime_sched.goidgen;
1294
1295         if(sp == nil)
1296                 runtime_throw("nil g->stack0");
1297
1298         getcontext(&newg->context);
1299         newg->context.uc_stack.ss_sp = sp;
1300         newg->context.uc_stack.ss_size = spsize;
1301         makecontext(&newg->context, kickoff, 0);
1302
1303         newprocreadylocked(newg);
1304         schedunlock();
1305
1306         return newg;
1307 //printf(" goid=%d\n", newg->goid);
1308 }
1309
1310 // Put on gfree list.  Sched must be locked.
1311 static void
1312 gfput(G *g)
1313 {
1314         g->schedlink = runtime_sched.gfree;
1315         runtime_sched.gfree = g;
1316 }
1317
1318 // Get from gfree list.  Sched must be locked.
1319 static G*
1320 gfget(void)
1321 {
1322         G *g;
1323
1324         g = runtime_sched.gfree;
1325         if(g)
1326                 runtime_sched.gfree = g->schedlink;
1327         return g;
1328 }
1329
1330 // Run all deferred functions for the current goroutine.
1331 static void
1332 rundefer(void)
1333 {
1334         Defer *d;
1335
1336         while((d = g->defer) != nil) {
1337                 void (*pfn)(void*);
1338
1339                 pfn = d->__pfn;
1340                 d->__pfn = nil;
1341                 if (pfn != nil)
1342                         (*pfn)(d->__arg);
1343                 g->defer = d->__next;
1344                 runtime_free(d);
1345         }
1346 }
1347
1348 void runtime_Goexit (void) asm ("libgo_runtime.runtime.Goexit");
1349
1350 void
1351 runtime_Goexit(void)
1352 {
1353         rundefer();
1354         runtime_goexit();
1355 }
1356
1357 void runtime_Gosched (void) asm ("libgo_runtime.runtime.Gosched");
1358
1359 void
1360 runtime_Gosched(void)
1361 {
1362         runtime_gosched();
1363 }
1364
1365 // Implementation of runtime.GOMAXPROCS.
1366 // delete when scheduler is stronger
1367 int32
1368 runtime_gomaxprocsfunc(int32 n)
1369 {
1370         int32 ret;
1371         uint32 v;
1372
1373         schedlock();
1374         ret = runtime_gomaxprocs;
1375         if(n <= 0)
1376                 n = ret;
1377         if(n > maxgomaxprocs)
1378                 n = maxgomaxprocs;
1379         runtime_gomaxprocs = n;
1380         if(runtime_gomaxprocs > 1)
1381                 runtime_singleproc = false;
1382         if(runtime_gcwaiting != 0) {
1383                 if(atomic_mcpumax(runtime_sched.atomic) != 1)
1384                         runtime_throw("invalid mcpumax during gc");
1385                 schedunlock();
1386                 return ret;
1387         }
1388
1389         setmcpumax(n);
1390
1391         // If there are now fewer allowed procs
1392         // than procs running, stop.
1393         v = runtime_atomicload(&runtime_sched.atomic);
1394         if((int32)atomic_mcpu(v) > n) {
1395                 schedunlock();
1396                 runtime_gosched();
1397                 return ret;
1398         }
1399         // handle more procs
1400         matchmg();
1401         schedunlock();
1402         return ret;
1403 }
1404
1405 void
1406 runtime_LockOSThread(void)
1407 {
1408         if(m == &runtime_m0 && runtime_sched.init) {
1409                 runtime_sched.lockmain = true;
1410                 return;
1411         }
1412         m->lockedg = g;
1413         g->lockedm = m;
1414 }
1415
1416 void
1417 runtime_UnlockOSThread(void)
1418 {
1419         if(m == &runtime_m0 && runtime_sched.init) {
1420                 runtime_sched.lockmain = false;
1421                 return;
1422         }
1423         m->lockedg = nil;
1424         g->lockedm = nil;
1425 }
1426
1427 bool
1428 runtime_lockedOSThread(void)
1429 {
1430         return g->lockedm != nil && m->lockedg != nil;
1431 }
1432
1433 // for testing of callbacks
1434
1435 _Bool runtime_golockedOSThread(void)
1436   asm("libgo_runtime.runtime.golockedOSThread");
1437
1438 _Bool
1439 runtime_golockedOSThread(void)
1440 {
1441         return runtime_lockedOSThread();
1442 }
1443
1444 // for testing of wire, unwire
1445 uint32
1446 runtime_mid()
1447 {
1448         return m->id;
1449 }
1450
1451 int32 runtime_Goroutines (void)
1452   __asm__ ("libgo_runtime.runtime.Goroutines");
1453
1454 int32
1455 runtime_Goroutines()
1456 {
1457         return runtime_sched.gcount;
1458 }
1459
1460 int32
1461 runtime_mcount(void)
1462 {
1463         return runtime_sched.mcount;
1464 }
1465
1466 static struct {
1467         Lock;
1468         void (*fn)(uintptr*, int32);
1469         int32 hz;
1470         uintptr pcbuf[100];
1471 } prof;
1472
1473 // Called if we receive a SIGPROF signal.
1474 void
1475 runtime_sigprof(uint8 *pc __attribute__ ((unused)),
1476                 uint8 *sp __attribute__ ((unused)),
1477                 uint8 *lr __attribute__ ((unused)),
1478                 G *gp __attribute__ ((unused)))
1479 {
1480         // int32 n;
1481
1482         if(prof.fn == nil || prof.hz == 0)
1483                 return;
1484
1485         runtime_lock(&prof);
1486         if(prof.fn == nil) {
1487                 runtime_unlock(&prof);
1488                 return;
1489         }
1490         // n = runtime_gentraceback(pc, sp, lr, gp, 0, prof.pcbuf, nelem(prof.pcbuf));
1491         // if(n > 0)
1492         //      prof.fn(prof.pcbuf, n);
1493         runtime_unlock(&prof);
1494 }
1495
1496 // Arrange to call fn with a traceback hz times a second.
1497 void
1498 runtime_setcpuprofilerate(void (*fn)(uintptr*, int32), int32 hz)
1499 {
1500         // Force sane arguments.
1501         if(hz < 0)
1502                 hz = 0;
1503         if(hz == 0)
1504                 fn = nil;
1505         if(fn == nil)
1506                 hz = 0;
1507
1508         // Stop profiler on this cpu so that it is safe to lock prof.
1509         // if a profiling signal came in while we had prof locked,
1510         // it would deadlock.
1511         runtime_resetcpuprofiler(0);
1512
1513         runtime_lock(&prof);
1514         prof.fn = fn;
1515         prof.hz = hz;
1516         runtime_unlock(&prof);
1517         runtime_lock(&runtime_sched);
1518         runtime_sched.profilehz = hz;
1519         runtime_unlock(&runtime_sched);
1520
1521         if(hz != 0)
1522                 runtime_resetcpuprofiler(hz);
1523 }