src/runtime/stack.c

   1 // Copyright 2013 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 "runtime.h"
   6 #include "arch_GOARCH.h"
   7 #include "malloc.h"
   8 #include "stack.h"
   9 #include "funcdata.h"
  10 #include "typekind.h"
  11 #include "type.h"
  12 #include "race.h"
  13 #include "mgc0.h"
  14 #include "textflag.h"
  15
  16 enum
  17 {
  18         // StackDebug == 0: no logging
  19         //            == 1: logging of per-stack operations
  20         //            == 2: logging of per-frame operations
  21         //            == 3: logging of per-word updates
  22         //            == 4: logging of per-word reads
  23         StackDebug = 0,
  24         StackFromSystem = 0,    // allocate stacks from system memory instead of the heap
  25         StackFaultOnFree = 0,   // old stacks are mapped noaccess to detect use after free
  26         StackPoisonCopy = 0,    // fill stack that should not be accessed with garbage, to detect bad dereferences during copy
  27
  28         StackCache = 1,
  29 };
  30
  31 // Global pool of spans that have free stacks.
  32 // Stacks are assigned an order according to size.
  33 //     order = log_2(size/FixedStack)
  34 // There is a free list for each order.
  35 MSpan runtime·stackpool[NumStackOrders];
  36 Mutex runtime·stackpoolmu;
  37 // TODO: one lock per order?
  38
  39 static Stack stackfreequeue;
  40
  41 void
  42 runtime·stackinit(void)
  43 {
  44         int32 i;
  45
  46         if((StackCacheSize & PageMask) != 0)
  47                 runtime·throw("cache size must be a multiple of page size");
  48
  49         for(i = 0; i < NumStackOrders; i++)
  50                 runtime·MSpanList_Init(&runtime·stackpool[i]);
  51 }
  52
  53 // Allocates a stack from the free pool.  Must be called with
  54 // stackpoolmu held.
  55 static MLink*
  56 poolalloc(uint8 order)
  57 {
  58         MSpan *list;
  59         MSpan *s;
  60         MLink *x;
  61         uintptr i;
  62
  63         list = &runtime·stackpool[order];
  64         s = list->next;
  65         if(s == list) {
  66                 // no free stacks.  Allocate another span worth.
  67                 s = runtime·MHeap_AllocStack(&runtime·mheap, StackCacheSize >> PageShift);
  68                 if(s == nil)
  69                         runtime·throw("out of memory");
  70                 if(s->ref != 0)
  71                         runtime·throw("bad ref");
  72                 if(s->freelist != nil)
  73                         runtime·throw("bad freelist");
  74                 for(i = 0; i < StackCacheSize; i += FixedStack << order) {
  75                         x = (MLink*)((s->start << PageShift) + i);
  76                         x->next = s->freelist;
  77                         s->freelist = x;
  78                 }
  79                 runtime·MSpanList_Insert(list, s);
  80         }
  81         x = s->freelist;
  82         if(x == nil)
  83                 runtime·throw("span has no free stacks");
  84         s->freelist = x->next;
  85         s->ref++;
  86         if(s->freelist == nil) {
  87                 // all stacks in s are allocated.
  88                 runtime·MSpanList_Remove(s);
  89         }
  90         return x;
  91 }
  92
  93 // Adds stack x to the free pool.  Must be called with stackpoolmu held.
  94 static void
  95 poolfree(MLink *x, uint8 order)
  96 {
  97         MSpan *s;
  98
  99         s = runtime·MHeap_Lookup(&runtime·mheap, x);
 100         if(s->state != MSpanStack)
 101                 runtime·throw("freeing stack not in a stack span");
 102         if(s->freelist == nil) {
 103                 // s will now have a free stack
 104                 runtime·MSpanList_Insert(&runtime·stackpool[order], s);
 105         }
 106         x->next = s->freelist;
 107         s->freelist = x;
 108         s->ref--;
 109         if(s->ref == 0) {
 110                 // span is completely free - return to heap
 111                 runtime·MSpanList_Remove(s);
 112                 s->freelist = nil;
 113                 runtime·MHeap_FreeStack(&runtime·mheap, s);
 114         }
 115 }
 116
 117 // stackcacherefill/stackcacherelease implement a global pool of stack segments.
 118 // The pool is required to prevent unlimited growth of per-thread caches.
 119 static void
 120 stackcacherefill(MCache *c, uint8 order)
 121 {
 122         MLink *x, *list;
 123         uintptr size;
 124
 125         if(StackDebug >= 1)
 126                 runtime·printf("stackcacherefill order=%d\n", order);
 127
 128         // Grab some stacks from the global cache.
 129         // Grab half of the allowed capacity (to prevent thrashing).
 130         list = nil;
 131         size = 0;
 132         runtime·lock(&runtime·stackpoolmu);
 133         while(size < StackCacheSize/2) {
 134                 x = poolalloc(order);
 135                 x->next = list;
 136                 list = x;
 137                 size += FixedStack << order;
 138         }
 139         runtime·unlock(&runtime·stackpoolmu);
 140
 141         c->stackcache[order].list = list;
 142         c->stackcache[order].size = size;
 143 }
 144
 145 static void
 146 stackcacherelease(MCache *c, uint8 order)
 147 {
 148         MLink *x, *y;
 149         uintptr size;
 150
 151         if(StackDebug >= 1)
 152                 runtime·printf("stackcacherelease order=%d\n", order);
 153         x = c->stackcache[order].list;
 154         size = c->stackcache[order].size;
 155         runtime·lock(&runtime·stackpoolmu);
 156         while(size > StackCacheSize/2) {
 157                 y = x->next;
 158                 poolfree(x, order);
 159                 x = y;
 160                 size -= FixedStack << order;
 161         }
 162         runtime·unlock(&runtime·stackpoolmu);
 163         c->stackcache[order].list = x;
 164         c->stackcache[order].size = size;
 165 }
 166
 167 void
 168 runtime·stackcache_clear(MCache *c)
 169 {
 170         uint8 order;
 171         MLink *x, *y;
 172
 173         if(StackDebug >= 1)
 174                 runtime·printf("stackcache clear\n");
 175         runtime·lock(&runtime·stackpoolmu);
 176         for(order = 0; order < NumStackOrders; order++) {
 177                 x = c->stackcache[order].list;
 178                 while(x != nil) {
 179                         y = x->next;
 180                         poolfree(x, order);
 181                         x = y;
 182                 }
 183                 c->stackcache[order].list = nil;
 184                 c->stackcache[order].size = 0;
 185         }
 186         runtime·unlock(&runtime·stackpoolmu);
 187 }
 188
 189 Stack
 190 runtime·stackalloc(uint32 n)
 191 {
 192         uint8 order;
 193         uint32 n2;
 194         void *v;
 195         MLink *x;
 196         MSpan *s;
 197         MCache *c;
 198
 199         // Stackalloc must be called on scheduler stack, so that we
 200         // never try to grow the stack during the code that stackalloc runs.
 201         // Doing so would cause a deadlock (issue 1547).
 202         if(g != g->m->g0)
 203                 runtime·throw("stackalloc not on scheduler stack");
 204         if((n & (n-1)) != 0)
 205                 runtime·throw("stack size not a power of 2");
 206         if(StackDebug >= 1)
 207                 runtime·printf("stackalloc %d\n", n);
 208
 209         if(runtime·debug.efence || StackFromSystem) {
 210                 v = runtime·sysAlloc(ROUND(n, PageSize), &mstats.stacks_sys);
 211                 if(v == nil)
 212                         runtime·throw("out of memory (stackalloc)");
 213                 return (Stack){(uintptr)v, (uintptr)v+n};
 214         }
 215
 216         // Small stacks are allocated with a fixed-size free-list allocator.
 217         // If we need a stack of a bigger size, we fall back on allocating
 218         // a dedicated span.
 219         if(StackCache && n < FixedStack << NumStackOrders && n < StackCacheSize) {
 220                 order = 0;
 221                 n2 = n;
 222                 while(n2 > FixedStack) {
 223                         order++;
 224                         n2 >>= 1;
 225                 }
 226                 c = g->m->mcache;
 227                 if(c == nil || g->m->gcing || g->m->helpgc) {
 228                         // c == nil can happen in the guts of exitsyscall or
 229                         // procresize. Just get a stack from the global pool.
 230                         // Also don't touch stackcache during gc
 231                         // as it's flushed concurrently.
 232                         runtime·lock(&runtime·stackpoolmu);
 233                         x = poolalloc(order);
 234                         runtime·unlock(&runtime·stackpoolmu);
 235                 } else {
 236                         x = c->stackcache[order].list;
 237                         if(x == nil) {
 238                                 stackcacherefill(c, order);
 239                                 x = c->stackcache[order].list;
 240                         }
 241                         c->stackcache[order].list = x->next;
 242                         c->stackcache[order].size -= n;
 243                 }
 244                 v = (byte*)x;
 245         } else {
 246                 s = runtime·MHeap_AllocStack(&runtime·mheap, ROUND(n, PageSize) >> PageShift);
 247                 if(s == nil)
 248                         runtime·throw("out of memory");
 249                 v = (byte*)(s->start<<PageShift);
 250         }
 251
 252         if(raceenabled)
 253                 runtime·racemalloc(v, n);
 254         if(StackDebug >= 1)
 255                 runtime·printf("  allocated %p\n", v);
 256         return (Stack){(uintptr)v, (uintptr)v+n};
 257 }
 258
 259 void
 260 runtime·stackfree(Stack stk)
 261 {
 262         uint8 order;
 263         uintptr n, n2;
 264         MSpan *s;
 265         MLink *x;
 266         MCache *c;
 267         void *v;
 268
 269         n = stk.hi - stk.lo;
 270         v = (void*)stk.lo;
 271         if(n & (n-1))
 272                 runtime·throw("stack not a power of 2");
 273         if(StackDebug >= 1) {
 274                 runtime·printf("stackfree %p %d\n", v, (int32)n);
 275                 runtime·memclr(v, n); // for testing, clobber stack data
 276         }
 277         if(runtime·debug.efence || StackFromSystem) {
 278                 if(runtime·debug.efence || StackFaultOnFree)
 279                         runtime·SysFault(v, n);
 280                 else
 281                         runtime·SysFree(v, n, &mstats.stacks_sys);
 282                 return;
 283         }
 284         if(StackCache && n < FixedStack << NumStackOrders && n < StackCacheSize) {
 285                 order = 0;
 286                 n2 = n;
 287                 while(n2 > FixedStack) {
 288                         order++;
 289                         n2 >>= 1;
 290                 }
 291                 x = (MLink*)v;
 292                 c = g->m->mcache;
 293                 if(c == nil || g->m->gcing || g->m->helpgc) {
 294                         runtime·lock(&runtime·stackpoolmu);
 295                         poolfree(x, order);
 296                         runtime·unlock(&runtime·stackpoolmu);
 297                 } else {
 298                         if(c->stackcache[order].size >= StackCacheSize)
 299                                 stackcacherelease(c, order);
 300                         x->next = c->stackcache[order].list;
 301                         c->stackcache[order].list = x;
 302                         c->stackcache[order].size += n;
 303                 }
 304         } else {
 305                 s = runtime·MHeap_Lookup(&runtime·mheap, v);
 306                 if(s->state != MSpanStack) {
 307                         runtime·printf("%p %p\n", s->start<<PageShift, v);
 308                         runtime·throw("bad span state");
 309                 }
 310                 runtime·MHeap_FreeStack(&runtime·mheap, s);
 311         }
 312 }
 313
 314 uintptr runtime·maxstacksize = 1<<20; // enough until runtime.main sets it for real
 315
 316 static uint8*
 317 mapnames[] = {
 318         (uint8*)"---",
 319         (uint8*)"scalar",
 320         (uint8*)"ptr",
 321         (uint8*)"multi",
 322 };
 323
 324 // Stack frame layout
 325 //
 326 // (x86)
 327 // +------------------+
 328 // | args from caller |
 329 // +------------------+ <- frame->argp
 330 // |  return address  |
 331 // +------------------+ <- frame->varp
 332 // |     locals       |
 333 // +------------------+
 334 // |  args to callee  |
 335 // +------------------+ <- frame->sp
 336 //
 337 // (arm)
 338 // +------------------+
 339 // | args from caller |
 340 // +------------------+ <- frame->argp
 341 // | caller's retaddr |
 342 // +------------------+ <- frame->varp
 343 // |     locals       |
 344 // +------------------+
 345 // |  args to callee  |
 346 // +------------------+
 347 // |  return address  |
 348 // +------------------+ <- frame->sp
 349
 350 void runtime·main(void);
 351 void runtime·switchtoM(void(*)(void));
 352
 353 typedef struct AdjustInfo AdjustInfo;
 354 struct AdjustInfo {
 355         Stack old;
 356         uintptr delta;  // ptr distance from old to new stack (newbase - oldbase)
 357 };
 358
 359 // Adjustpointer checks whether *vpp is in the old stack described by adjinfo.
 360 // If so, it rewrites *vpp to point into the new stack.
 361 static void
 362 adjustpointer(AdjustInfo *adjinfo, void *vpp)
 363 {
 364         byte **pp, *p;
 365
 366         pp = vpp;
 367         p = *pp;
 368         if(StackDebug >= 4)
 369                 runtime·printf("        %p:%p\n", pp, p);
 370         if(adjinfo->old.lo <= (uintptr)p && (uintptr)p < adjinfo->old.hi) {
 371                 *pp = p + adjinfo->delta;
 372                 if(StackDebug >= 3)
 373                         runtime·printf("        adjust ptr %p: %p -> %p\n", pp, p, *pp);
 374         }
 375 }
 376
 377 // bv describes the memory starting at address scanp.
 378 // Adjust any pointers contained therein.
 379 static void
 380 adjustpointers(byte **scanp, BitVector *bv, AdjustInfo *adjinfo, Func *f)
 381 {
 382         uintptr delta;
 383         int32 num, i;
 384         byte *p, *minp, *maxp;
 385
 386         minp = (byte*)adjinfo->old.lo;
 387         maxp = (byte*)adjinfo->old.hi;
 388         delta = adjinfo->delta;
 389         num = bv->n / BitsPerPointer;
 390         for(i = 0; i < num; i++) {
 391                 if(StackDebug >= 4)
 392                         runtime·printf("        %p:%s:%p\n", &scanp[i], mapnames[bv->bytedata[i / (8 / BitsPerPointer)] >> (i * BitsPerPointer & 7) & 3], scanp[i]);
 393                 switch(bv->bytedata[i / (8 / BitsPerPointer)] >> (i * BitsPerPointer & 7) & 3) {
 394                 case BitsDead:
 395                         if(runtime·debug.gcdead)
 396                                 scanp[i] = (byte*)PoisonStack;
 397                         break;
 398                 case BitsScalar:
 399                         break;
 400                 case BitsPointer:
 401                         p = scanp[i];
 402                         if(f != nil && (byte*)0 < p && (p < (byte*)PageSize && runtime·invalidptr || (uintptr)p == PoisonGC || (uintptr)p == PoisonStack)) {
 403                                 // Looks like a junk value in a pointer slot.
 404                                 // Live analysis wrong?
 405                                 g->m->traceback = 2;
 406                                 runtime·printf("runtime: bad pointer in frame %s at %p: %p\n", runtime·funcname(f), &scanp[i], p);
 407                                 runtime·throw("invalid stack pointer");
 408                         }
 409                         if(minp <= p && p < maxp) {
 410                                 if(StackDebug >= 3)
 411                                         runtime·printf("adjust ptr %p %s\n", p, runtime·funcname(f));
 412                                 scanp[i] = p + delta;
 413                         }
 414                         break;
 415                 case BitsMultiWord:
 416                         runtime·throw("adjustpointers: unexpected garbage collection bits");
 417                 }
 418         }
 419 }
 420
 421 // Note: the argument/return area is adjusted by the callee.
 422 static bool
 423 adjustframe(Stkframe *frame, void *arg)
 424 {
 425         AdjustInfo *adjinfo;
 426         Func *f;
 427         StackMap *stackmap;
 428         int32 pcdata;
 429         BitVector bv;
 430         uintptr targetpc, size, minsize;
 431
 432         adjinfo = arg;
 433         targetpc = frame->continpc;
 434         if(targetpc == 0) {
 435                 // Frame is dead.
 436                 return true;
 437         }
 438         f = frame->fn;
 439         if(StackDebug >= 2)
 440                 runtime·printf("    adjusting %s frame=[%p,%p] pc=%p continpc=%p\n", runtime·funcname(f), frame->sp, frame->fp, frame->pc, frame->continpc);
 441         if(f->entry == (uintptr)runtime·switchtoM) {
 442                 // A special routine at the bottom of stack of a goroutine that does an onM call.
 443                 // We will allow it to be copied even though we don't
 444                 // have full GC info for it (because it is written in asm).
 445                 return true;
 446         }
 447         if(targetpc != f->entry)
 448                 targetpc--;
 449         pcdata = runtime·pcdatavalue(f, PCDATA_StackMapIndex, targetpc);
 450         if(pcdata == -1)
 451                 pcdata = 0; // in prologue
 452
 453         // Adjust local variables if stack frame has been allocated.
 454         size = frame->varp - frame->sp;
 455         if(thechar != '6' && thechar != '8')
 456                 minsize = sizeof(uintptr);
 457         else
 458                 minsize = 0;
 459         if(size > minsize) {
 460                 stackmap = runtime·funcdata(f, FUNCDATA_LocalsPointerMaps);
 461                 if(stackmap == nil || stackmap->n <= 0) {
 462                         runtime·printf("runtime: frame %s untyped locals %p+%p\n", runtime·funcname(f), (byte*)(frame->varp-size), size);
 463                         runtime·throw("missing stackmap");
 464                 }
 465                 // Locals bitmap information, scan just the pointers in locals.
 466                 if(pcdata < 0 || pcdata >= stackmap->n) {
 467                         // don't know where we are
 468                         runtime·printf("runtime: pcdata is %d and %d locals stack map entries for %s (targetpc=%p)\n",
 469                                 pcdata, stackmap->n, runtime·funcname(f), targetpc);
 470                         runtime·throw("bad symbol table");
 471                 }
 472                 bv = runtime·stackmapdata(stackmap, pcdata);
 473                 size = (bv.n * PtrSize) / BitsPerPointer;
 474                 if(StackDebug >= 3)
 475                         runtime·printf("      locals\n");
 476                 adjustpointers((byte**)(frame->varp - size), &bv, adjinfo, f);
 477         }
 478
 479         // Adjust arguments.
 480         if(frame->arglen > 0) {
 481                 if(frame->argmap != nil) {
 482                         bv = *frame->argmap;
 483                 } else {
 484                         stackmap = runtime·funcdata(f, FUNCDATA_ArgsPointerMaps);
 485                         if(stackmap == nil || stackmap->n <= 0) {
 486                                 runtime·printf("runtime: frame %s untyped args %p+%p\n", runtime·funcname(f), frame->argp, (uintptr)frame->arglen);
 487                                 runtime·throw("missing stackmap");
 488                         }
 489                         if(pcdata < 0 || pcdata >= stackmap->n) {
 490                                 // don't know where we are
 491                                 runtime·printf("runtime: pcdata is %d and %d args stack map entries for %s (targetpc=%p)\n",
 492                                         pcdata, stackmap->n, runtime·funcname(f), targetpc);
 493                                 runtime·throw("bad symbol table");
 494                         }
 495                         bv = runtime·stackmapdata(stackmap, pcdata);
 496                 }
 497                 if(StackDebug >= 3)
 498                         runtime·printf("      args\n");
 499                 adjustpointers((byte**)frame->argp, &bv, adjinfo, nil);
 500         }
 501
 502         return true;
 503 }
 504
 505 static void
 506 adjustctxt(G *gp, AdjustInfo *adjinfo)
 507 {
 508         adjustpointer(adjinfo, &gp->sched.ctxt);
 509 }
 510
 511 static void
 512 adjustdefers(G *gp, AdjustInfo *adjinfo)
 513 {
 514         Defer *d;
 515         bool (*cb)(Stkframe*, void*);
 516
 517         // Adjust defer argument blocks the same way we adjust active stack frames.
 518         cb = adjustframe;
 519         runtime·tracebackdefers(gp, &cb, adjinfo);
 520
 521         // Adjust pointers in the Defer structs.
 522         // Defer structs themselves are never on the stack.
 523         for(d = gp->defer; d != nil; d = d->link) {
 524                 adjustpointer(adjinfo, &d->fn);
 525                 adjustpointer(adjinfo, &d->argp);
 526                 adjustpointer(adjinfo, &d->panic);
 527         }
 528 }
 529
 530 static void
 531 adjustpanics(G *gp, AdjustInfo *adjinfo)
 532 {
 533         // Panics are on stack and already adjusted.
 534         // Update pointer to head of list in G.
 535         adjustpointer(adjinfo, &gp->panic);
 536 }
 537
 538 static void
 539 adjustsudogs(G *gp, AdjustInfo *adjinfo)
 540 {
 541         SudoG *s;
 542
 543         // the data elements pointed to by a SudoG structure
 544         // might be in the stack.
 545         for(s = gp->waiting; s != nil; s = s->waitlink) {
 546                 adjustpointer(adjinfo, &s->elem);
 547                 adjustpointer(adjinfo, &s->selectdone);
 548         }
 549 }
 550
 551 // Copies gp's stack to a new stack of a different size.
 552 // Caller must have changed gp status to Gcopystack.
 553 static void
 554 copystack(G *gp, uintptr newsize)
 555 {
 556         Stack old, new;
 557         uintptr used;
 558         AdjustInfo adjinfo;
 559         bool (*cb)(Stkframe*, void*);
 560         byte *p, *ep;
 561
 562         if(gp->syscallsp != 0)
 563                 runtime·throw("stack growth not allowed in system call");
 564         old = gp->stack;
 565         if(old.lo == 0)
 566                 runtime·throw("nil stackbase");
 567         used = old.hi - gp->sched.sp;
 568
 569         // allocate new stack
 570         new = runtime·stackalloc(newsize);
 571         if(StackPoisonCopy) {
 572                 p = (byte*)new.lo;
 573                 ep = (byte*)new.hi;
 574                 while(p < ep)
 575                         *p++ = 0xfd;
 576         }
 577
 578         if(StackDebug >= 1)
 579                 runtime·printf("copystack gp=%p [%p %p %p]/%d -> [%p %p %p]/%d\n", gp, old.lo, old.hi-used, old.hi, (int32)(old.hi-old.lo), new.lo, new.hi-used, new.hi, (int32)newsize);
 580
 581         // adjust pointers in the to-be-copied frames
 582         adjinfo.old = old;
 583         adjinfo.delta = new.hi - old.hi;
 584         cb = adjustframe;
 585         runtime·gentraceback(~(uintptr)0, ~(uintptr)0, 0, gp, 0, nil, 0x7fffffff, &cb, &adjinfo, 0);
 586
 587         // adjust other miscellaneous things that have pointers into stacks.
 588         adjustctxt(gp, &adjinfo);
 589         adjustdefers(gp, &adjinfo);
 590         adjustpanics(gp, &adjinfo);
 591         adjustsudogs(gp, &adjinfo);
 592
 593         // copy the stack to the new location
 594         if(StackPoisonCopy) {
 595                 p = (byte*)new.lo;
 596                 ep = (byte*)new.hi;
 597                 while(p < ep)
 598                         *p++ = 0xfb;
 599         }
 600         runtime·memmove((byte*)new.hi - used, (byte*)old.hi - used, used);
 601
 602         // Swap out old stack for new one
 603         gp->stack = new;
 604         gp->stackguard0 = new.lo + StackGuard; // NOTE: might clobber a preempt request
 605         gp->sched.sp = new.hi - used;
 606
 607         // free old stack
 608         if(StackPoisonCopy) {
 609                 p = (byte*)old.lo;
 610                 ep = (byte*)old.hi;
 611                 while(p < ep)
 612                         *p++ = 0xfc;
 613         }
 614         if(newsize > old.hi-old.lo) {
 615                 // growing, free stack immediately
 616                 runtime·stackfree(old);
 617         } else {
 618                 // shrinking, queue up free operation.  We can't actually free the stack
 619                 // just yet because we might run into the following situation:
 620                 // 1) GC starts, scans a SudoG but does not yet mark the SudoG.elem pointer
 621                 // 2) The stack that pointer points to is shrunk
 622                 // 3) The old stack is freed
 623                 // 4) The containing span is marked free
 624                 // 5) GC attempts to mark the SudoG.elem pointer.  The marking fails because
 625                 //    the pointer looks like a pointer into a free span.
 626                 // By not freeing, we prevent step #4 until GC is done.
 627                 runtime·lock(&runtime·stackpoolmu);
 628                 *(Stack*)old.lo = stackfreequeue;
 629                 stackfreequeue = old;
 630                 runtime·unlock(&runtime·stackpoolmu);
 631         }
 632 }
 633
 634 // round x up to a power of 2.
 635 int32
 636 runtime·round2(int32 x)
 637 {
 638         int32 s;
 639
 640         s = 0;
 641         while((1 << s) < x)
 642                 s++;
 643         return 1 << s;
 644 }
 645
 646 // Called from runtime·morestack when more stack is needed.
 647 // Allocate larger stack and relocate to new stack.
 648 // Stack growth is multiplicative, for constant amortized cost.
 649 //
 650 // g->atomicstatus will be Grunning or Gscanrunning upon entry.
 651 // If the GC is trying to stop this g then it will set preemptscan to true.
 652 void
 653 runtime·newstack(void)
 654 {
 655         int32 oldsize, newsize;
 656         uint32 oldstatus;
 657         uintptr sp;
 658         G *gp;
 659         Gobuf morebuf;
 660
 661         if(g->m->morebuf.g->stackguard0 == (uintptr)StackFork)
 662                 runtime·throw("stack growth after fork");
 663         if(g->m->morebuf.g != g->m->curg) {
 664                 runtime·printf("runtime: newstack called from g=%p\n"
 665                         "\tm=%p m->curg=%p m->g0=%p m->gsignal=%p\n",
 666                         g->m->morebuf.g, g->m, g->m->curg, g->m->g0, g->m->gsignal);
 667                 morebuf = g->m->morebuf;
 668                 runtime·traceback(morebuf.pc, morebuf.sp, morebuf.lr, morebuf.g);
 669                 runtime·throw("runtime: wrong goroutine in newstack");
 670         }
 671         if(g->m->curg->throwsplit)
 672                 runtime·throw("runtime: stack split at bad time");
 673
 674         // The goroutine must be executing in order to call newstack,
 675         // so it must be Grunning or Gscanrunning.
 676
 677         gp = g->m->curg;
 678         morebuf = g->m->morebuf;
 679         g->m->morebuf.pc = (uintptr)nil;
 680         g->m->morebuf.lr = (uintptr)nil;
 681         g->m->morebuf.sp = (uintptr)nil;
 682         g->m->morebuf.g = (G*)nil;
 683
 684         runtime·casgstatus(gp, Grunning, Gwaiting);
 685         gp->waitreason = runtime·gostringnocopy((byte*)"stack growth");
 686
 687         runtime·rewindmorestack(&gp->sched);
 688
 689         if(gp->stack.lo == 0)
 690                 runtime·throw("missing stack in newstack");
 691         sp = gp->sched.sp;
 692         if(thechar == '6' || thechar == '8') {
 693                 // The call to morestack cost a word.
 694                 sp -= sizeof(uintreg);
 695         }
 696         if(StackDebug >= 1 || sp < gp->stack.lo) {
 697                 runtime·printf("runtime: newstack sp=%p stack=[%p, %p]\n"
 698                         "\tmorebuf={pc:%p sp:%p lr:%p}\n"
 699                         "\tsched={pc:%p sp:%p lr:%p ctxt:%p}\n",
 700                         sp, gp->stack.lo, gp->stack.hi,
 701                         g->m->morebuf.pc, g->m->morebuf.sp, g->m->morebuf.lr,
 702                         gp->sched.pc, gp->sched.sp, gp->sched.lr, gp->sched.ctxt);
 703         }
 704         if(sp < gp->stack.lo) {
 705                 runtime·printf("runtime: gp=%p, gp->status=%d\n ", (void*)gp, runtime·readgstatus(gp));
 706                 runtime·printf("runtime: split stack overflow: %p < %p\n", sp, gp->stack.lo);
 707                 runtime·throw("runtime: split stack overflow");
 708         }
 709
 710         if(gp->sched.ctxt != nil) {
 711                 // morestack wrote sched.ctxt on its way in here,
 712                 // without a write barrier. Run the write barrier now.
 713                 // It is not possible to be preempted between then
 714                 // and now, so it's okay.
 715                 runtime·writebarrierptr_nostore(&gp->sched.ctxt, gp->sched.ctxt);
 716         }
 717
 718         if(gp->stackguard0 == (uintptr)StackPreempt) {
 719                 if(gp == g->m->g0)
 720                         runtime·throw("runtime: preempt g0");
 721                 if(g->m->p == nil && g->m->locks == 0)
 722                         runtime·throw("runtime: g is running but p is not");
 723                 if(gp->preemptscan) {
 724                         runtime·gcphasework(gp);
 725                         runtime·casgstatus(gp, Gwaiting, Grunning);
 726                         gp->stackguard0 = gp->stack.lo + StackGuard;
 727                         gp->preempt = false;
 728                         gp->preemptscan = false;        // Tells the GC premption was successful.
 729                         runtime·gogo(&gp->sched);      // never return
 730                 }
 731
 732                 // Be conservative about where we preempt.
 733                 // We are interested in preempting user Go code, not runtime code.
 734                 if(g->m->locks || g->m->mallocing || g->m->gcing || g->m->p->status != Prunning) {
 735                         // Let the goroutine keep running for now.
 736                         // gp->preempt is set, so it will be preempted next time.
 737                         gp->stackguard0 = gp->stack.lo + StackGuard;
 738                         runtime·casgstatus(gp, Gwaiting, Grunning);
 739                         runtime·gogo(&gp->sched);      // never return
 740                 }
 741                 // Act like goroutine called runtime.Gosched.
 742                 runtime·casgstatus(gp, Gwaiting, Grunning);
 743                 runtime·gosched_m(gp); // never return
 744         }
 745
 746         // Allocate a bigger segment and move the stack.
 747         oldsize = gp->stack.hi - gp->stack.lo;
 748         newsize = oldsize * 2;
 749         if(newsize > runtime·maxstacksize) {
 750                 runtime·printf("runtime: goroutine stack exceeds %D-byte limit\n", (uint64)runtime·maxstacksize);
 751                 runtime·throw("stack overflow");
 752         }
 753
 754         oldstatus = runtime·readgstatus(gp);
 755         oldstatus &= ~Gscan;
 756         runtime·casgstatus(gp, oldstatus, Gcopystack); // oldstatus is Gwaiting or Grunnable
 757         // The concurrent GC will not scan the stack while we are doing the copy since
 758         // the gp is in a Gcopystack status.
 759         copystack(gp, newsize);
 760         if(StackDebug >= 1)
 761                 runtime·printf("stack grow done\n");
 762         runtime·casgstatus(gp, Gcopystack, Grunning);
 763         runtime·gogo(&gp->sched);
 764 }
 765
 766 #pragma textflag NOSPLIT
 767 void
 768 runtime·nilfunc(void)
 769 {
 770         *(byte*)0 = 0;
 771 }
 772
 773 // adjust Gobuf as if it executed a call to fn
 774 // and then did an immediate gosave.
 775 void
 776 runtime·gostartcallfn(Gobuf *gobuf, FuncVal *fv)
 777 {
 778         void *fn;
 779
 780         if(fv != nil)
 781                 fn = fv->fn;
 782         else
 783                 fn = runtime·nilfunc;
 784         runtime·gostartcall(gobuf, fn, fv);
 785 }
 786
 787 // Maybe shrink the stack being used by gp.
 788 // Called at garbage collection time.
 789 void
 790 runtime·shrinkstack(G *gp)
 791 {
 792         uintptr used, oldsize, newsize;
 793         uint32 oldstatus;
 794
 795         if(runtime·readgstatus(gp) == Gdead) {
 796                 if(gp->stack.lo != 0) {
 797                         // Free whole stack - it will get reallocated
 798                         // if G is used again.
 799                         runtime·stackfree(gp->stack);
 800                         gp->stack.lo = 0;
 801                         gp->stack.hi = 0;
 802                 }
 803                 return;
 804         }
 805         if(gp->stack.lo == 0)
 806                 runtime·throw("missing stack in shrinkstack");
 807
 808         oldsize = gp->stack.hi - gp->stack.lo;
 809         newsize = oldsize / 2;
 810         if(newsize < FixedStack)
 811                 return; // don't shrink below the minimum-sized stack
 812         used = gp->stack.hi - gp->sched.sp;
 813         if(used >= oldsize / 4)
 814                 return; // still using at least 1/4 of the segment.
 815
 816         // We can't copy the stack if we're in a syscall.
 817         // The syscall might have pointers into the stack.
 818         if(gp->syscallsp != 0)
 819                 return;
 820
 821 #ifdef GOOS_windows
 822         if(gp->m != nil && gp->m->libcallsp != 0)
 823                 return;
 824 #endif
 825         if(StackDebug > 0)
 826                 runtime·printf("shrinking stack %D->%D\n", (uint64)oldsize, (uint64)newsize);
 827         // This is being done in a Gscan state and was initiated by the GC so no need to move to
 828         // the Gcopystate.
 829         // The world is stopped, so the goroutine must be Gwaiting or Grunnable,
 830         // and what it is is not changing underfoot.
 831
 832         oldstatus = runtime·readgstatus(gp);
 833         oldstatus &= ~Gscan;
 834         if(oldstatus != Gwaiting && oldstatus != Grunnable)
 835                 runtime·throw("status is not Gwaiting or Grunnable");
 836         runtime·casgstatus(gp, oldstatus, Gcopystack);
 837         copystack(gp, newsize);
 838         runtime·casgstatus(gp, Gcopystack, oldstatus);
 839  }
 840
 841 // Do any delayed stack freeing that was queued up during GC.
 842 void
 843 runtime·shrinkfinish(void)
 844 {
 845         Stack s, t;
 846
 847         runtime·lock(&runtime·stackpoolmu);
 848         s = stackfreequeue;
 849         stackfreequeue = (Stack){0,0};
 850         runtime·unlock(&runtime·stackpoolmu);
 851         while(s.lo != 0) {
 852                 t = *(Stack*)s.lo;
 853                 runtime·stackfree(s);
 854                 s = t;
 855         }
 856 }
 857
 858 static void badc(void);
 859
 860 #pragma textflag NOSPLIT
 861 void
 862 runtime·morestackc(void)
 863 {
 864         void (*fn)(void);
 865
 866         fn = badc;
 867         runtime·onM(&fn);
 868 }
 869
 870 static void
 871 badc(void)
 872 {
 873         runtime·throw("attempt to execute C code on Go stack");
 874 }