libgo/runtime/mgc0.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 // Garbage collector.
   6
   7 #include "runtime.h"
   8 #include "arch.h"
   9 #include "malloc.h"
  10
  11 #ifdef USING_SPLIT_STACK
  12
  13 extern void * __splitstack_find (void *, void *, size_t *, void **, void **,
  14                                  void **);
  15
  16 extern void * __splitstack_find_context (void *context[10], size_t *, void **,
  17                                          void **, void **);
  18
  19 #endif
  20
  21 enum {
  22         Debug = 0,
  23         PtrSize = sizeof(void*),
  24         DebugMark = 0,  // run second pass to check mark
  25
  26         // Four bits per word (see #defines below).
  27         wordsPerBitmapWord = sizeof(void*)*8/4,
  28         bitShift = sizeof(void*)*8/4,
  29 };
  30
  31 // Bits in per-word bitmap.
  32 // #defines because enum might not be able to hold the values.
  33 //
  34 // Each word in the bitmap describes wordsPerBitmapWord words
  35 // of heap memory.  There are 4 bitmap bits dedicated to each heap word,
  36 // so on a 64-bit system there is one bitmap word per 16 heap words.
  37 // The bits in the word are packed together by type first, then by
  38 // heap location, so each 64-bit bitmap word consists of, from top to bottom,
  39 // the 16 bitSpecial bits for the corresponding heap words, then the 16 bitMarked bits,
  40 // then the 16 bitNoPointers/bitBlockBoundary bits, then the 16 bitAllocated bits.
  41 // This layout makes it easier to iterate over the bits of a given type.
  42 //
  43 // The bitmap starts at mheap.arena_start and extends *backward* from
  44 // there.  On a 64-bit system the off'th word in the arena is tracked by
  45 // the off/16+1'th word before mheap.arena_start.  (On a 32-bit system,
  46 // the only difference is that the divisor is 8.)
  47 //
  48 // To pull out the bits corresponding to a given pointer p, we use:
  49 //
  50 //      off = p - (uintptr*)mheap.arena_start;  // word offset
  51 //      b = (uintptr*)mheap.arena_start - off/wordsPerBitmapWord - 1;
  52 //      shift = off % wordsPerBitmapWord
  53 //      bits = *b >> shift;
  54 //      /* then test bits & bitAllocated, bits & bitMarked, etc. */
  55 //
  56 #define bitAllocated            ((uintptr)1<<(bitShift*0))
  57 #define bitNoPointers           ((uintptr)1<<(bitShift*1))      /* when bitAllocated is set */
  58 #define bitMarked               ((uintptr)1<<(bitShift*2))      /* when bitAllocated is set */
  59 #define bitSpecial              ((uintptr)1<<(bitShift*3))      /* when bitAllocated is set - has finalizer or being profiled */
  60 #define bitBlockBoundary        ((uintptr)1<<(bitShift*1))      /* when bitAllocated is NOT set */
  61
  62 #define bitMask (bitBlockBoundary | bitAllocated | bitMarked | bitSpecial)
  63
  64 // TODO: Make these per-M.
  65 static uint64 nlookup;
  66 static uint64 nsizelookup;
  67 static uint64 naddrlookup;
  68 static uint64 nhandoff;
  69
  70 static int32 gctrace;
  71
  72 typedef struct Workbuf Workbuf;
  73 struct Workbuf
  74 {
  75         Workbuf *next;
  76         uintptr nobj;
  77         byte *obj[512-2];
  78 };
  79
  80 typedef struct Finalizer Finalizer;
  81 struct Finalizer
  82 {
  83         void (*fn)(void*);
  84         void *arg;
  85         const struct __go_func_type *ft;
  86 };
  87
  88 typedef struct FinBlock FinBlock;
  89 struct FinBlock
  90 {
  91         FinBlock *alllink;
  92         FinBlock *next;
  93         int32 cnt;
  94         int32 cap;
  95         Finalizer fin[1];
  96 };
  97
  98
  99 static G *fing;
 100 static FinBlock *finq; // list of finalizers that are to be executed
 101 static FinBlock *finc; // cache of free blocks
 102 static FinBlock *allfin; // list of all blocks
 103 static Lock finlock;
 104 static int32 fingwait;
 105
 106 static void runfinq(void*);
 107 static Workbuf* getempty(Workbuf*);
 108 static Workbuf* getfull(Workbuf*);
 109 static void     putempty(Workbuf*);
 110 static Workbuf* handoff(Workbuf*);
 111
 112 static struct {
 113         Lock fmu;
 114         Workbuf *full;
 115         Lock emu;
 116         Workbuf *empty;
 117         uint32  nproc;
 118         volatile uint32 nwait;
 119         volatile uint32 ndone;
 120         Note    alldone;
 121         Lock    markgate;
 122         Lock    sweepgate;
 123         MSpan   *spans;
 124
 125         Lock;
 126         byte    *chunk;
 127         uintptr nchunk;
 128 } work;
 129
 130 // scanblock scans a block of n bytes starting at pointer b for references
 131 // to other objects, scanning any it finds recursively until there are no
 132 // unscanned objects left.  Instead of using an explicit recursion, it keeps
 133 // a work list in the Workbuf* structures and loops in the main function
 134 // body.  Keeping an explicit work list is easier on the stack allocator and
 135 // more efficient.
 136 static void
 137 scanblock(byte *b, int64 n)
 138 {
 139         byte *obj, *arena_start, *arena_used, *p;
 140         void **vp;
 141         uintptr size, *bitp, bits, shift, i, j, x, xbits, off, nobj, nproc;
 142         MSpan *s;
 143         PageID k;
 144         void **wp;
 145         Workbuf *wbuf;
 146         bool keepworking;
 147
 148         if((int64)(uintptr)n != n || n < 0) {
 149                 // runtime_printf("scanblock %p %lld\n", b, (long long)n);
 150                 runtime_throw("scanblock");
 151         }
 152
 153         // Memory arena parameters.
 154         arena_start = runtime_mheap.arena_start;
 155         arena_used = runtime_mheap.arena_used;
 156         nproc = work.nproc;
 157
 158         wbuf = nil;  // current work buffer
 159         wp = nil;  // storage for next queued pointer (write pointer)
 160         nobj = 0;  // number of queued objects
 161
 162         // Scanblock helpers pass b==nil.
 163         // The main proc needs to return to make more
 164         // calls to scanblock.  But if work.nproc==1 then
 165         // might as well process blocks as soon as we
 166         // have them.
 167         keepworking = b == nil || work.nproc == 1;
 168
 169         // Align b to a word boundary.
 170         off = (uintptr)b & (PtrSize-1);
 171         if(off != 0) {
 172                 b += PtrSize - off;
 173                 n -= PtrSize - off;
 174         }
 175
 176         for(;;) {
 177                 // Each iteration scans the block b of length n, queueing pointers in
 178                 // the work buffer.
 179                 if(Debug > 1)
 180                         runtime_printf("scanblock %p %lld\n", b, (long long) n);
 181
 182                 vp = (void**)b;
 183                 n >>= (2+PtrSize/8);  /* n /= PtrSize (4 or 8) */
 184                 for(i=0; i<(uintptr)n; i++) {
 185                         obj = (byte*)vp[i];
 186
 187                         // Words outside the arena cannot be pointers.
 188                         if((byte*)obj < arena_start || (byte*)obj >= arena_used)
 189                                 continue;
 190
 191                         // obj may be a pointer to a live object.
 192                         // Try to find the beginning of the object.
 193
 194                         // Round down to word boundary.
 195                         obj = (void*)((uintptr)obj & ~((uintptr)PtrSize-1));
 196
 197                         // Find bits for this word.
 198                         off = (uintptr*)obj - (uintptr*)arena_start;
 199                         bitp = (uintptr*)arena_start - off/wordsPerBitmapWord - 1;
 200                         shift = off % wordsPerBitmapWord;
 201                         xbits = *bitp;
 202                         bits = xbits >> shift;
 203
 204                         // Pointing at the beginning of a block?
 205                         if((bits & (bitAllocated|bitBlockBoundary)) != 0)
 206                                 goto found;
 207
 208                         // Pointing just past the beginning?
 209                         // Scan backward a little to find a block boundary.
 210                         for(j=shift; j-->0; ) {
 211                                 if(((xbits>>j) & (bitAllocated|bitBlockBoundary)) != 0) {
 212                                         obj = (byte*)obj - (shift-j)*PtrSize;
 213                                         shift = j;
 214                                         bits = xbits>>shift;
 215                                         goto found;
 216                                 }
 217                         }
 218
 219                         // Otherwise consult span table to find beginning.
 220                         // (Manually inlined copy of MHeap_LookupMaybe.)
 221                         nlookup++;
 222                         naddrlookup++;
 223                         k = (uintptr)obj>>PageShift;
 224                         x = k;
 225                         if(sizeof(void*) == 8)
 226                                 x -= (uintptr)arena_start>>PageShift;
 227                         s = runtime_mheap.map[x];
 228                         if(s == nil || k < s->start || k - s->start >= s->npages || s->state != MSpanInUse)
 229                                 continue;
 230                         p =  (byte*)((uintptr)s->start<<PageShift);
 231                         if(s->sizeclass == 0) {
 232                                 obj = p;
 233                         } else {
 234                                 if((byte*)obj >= (byte*)s->limit)
 235                                         continue;
 236                                 size = runtime_class_to_size[s->sizeclass];
 237                                 int32 i = ((byte*)obj - p)/size;
 238                                 obj = p+i*size;
 239                         }
 240
 241                         // Now that we know the object header, reload bits.
 242                         off = (uintptr*)obj - (uintptr*)arena_start;
 243                         bitp = (uintptr*)arena_start - off/wordsPerBitmapWord - 1;
 244                         shift = off % wordsPerBitmapWord;
 245                         xbits = *bitp;
 246                         bits = xbits >> shift;
 247
 248                 found:
 249                         // Now we have bits, bitp, and shift correct for
 250                         // obj pointing at the base of the object.
 251                         // Only care about allocated and not marked.
 252                         if((bits & (bitAllocated|bitMarked)) != bitAllocated)
 253                                 continue;
 254                         if(nproc == 1)
 255                                 *bitp |= bitMarked<<shift;
 256                         else {
 257                                 for(;;) {
 258                                         x = *bitp;
 259                                         if(x & (bitMarked<<shift))
 260                                                 goto continue_obj;
 261                                         if(runtime_casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift))))
 262                                                 break;
 263                                 }
 264                         }
 265
 266                         // If object has no pointers, don't need to scan further.
 267                         if((bits & bitNoPointers) != 0)
 268                                 continue;
 269
 270                         // If another proc wants a pointer, give it some.
 271                         if(nobj > 4 && work.nwait > 0 && work.full == nil) {
 272                                 wbuf->nobj = nobj;
 273                                 wbuf = handoff(wbuf);
 274                                 nobj = wbuf->nobj;
 275                                 wp = (void**)(wbuf->obj + nobj);
 276                         }
 277
 278                         // If buffer is full, get a new one.
 279                         if(wbuf == nil || nobj >= nelem(wbuf->obj)) {
 280                                 if(wbuf != nil)
 281                                         wbuf->nobj = nobj;
 282                                 wbuf = getempty(wbuf);
 283                                 wp = (void**)(wbuf->obj);
 284                                 nobj = 0;
 285                         }
 286                         *wp++ = obj;
 287                         nobj++;
 288                 continue_obj:;
 289                 }
 290
 291                 // Done scanning [b, b+n).  Prepare for the next iteration of
 292                 // the loop by setting b and n to the parameters for the next block.
 293
 294                 // Fetch b from the work buffer.
 295                 if(nobj == 0) {
 296                         if(!keepworking) {
 297                                 putempty(wbuf);
 298                                 return;
 299                         }
 300                         // Emptied our buffer: refill.
 301                         wbuf = getfull(wbuf);
 302                         if(wbuf == nil)
 303                                 return;
 304                         nobj = wbuf->nobj;
 305                         wp = (void**)(wbuf->obj + wbuf->nobj);
 306                 }
 307                 b = *--wp;
 308                 nobj--;
 309
 310                 // Figure out n = size of b.  Start by loading bits for b.
 311                 off = (uintptr*)b - (uintptr*)arena_start;
 312                 bitp = (uintptr*)arena_start - off/wordsPerBitmapWord - 1;
 313                 shift = off % wordsPerBitmapWord;
 314                 xbits = *bitp;
 315                 bits = xbits >> shift;
 316
 317                 // Might be small; look for nearby block boundary.
 318                 // A block boundary is marked by either bitBlockBoundary
 319                 // or bitAllocated being set (see notes near their definition).
 320                 enum {
 321                         boundary = bitBlockBoundary|bitAllocated
 322                 };
 323                 // Look for a block boundary both after and before b
 324                 // in the same bitmap word.
 325                 //
 326                 // A block boundary j words after b is indicated by
 327                 //      bits>>j & boundary
 328                 // assuming shift+j < bitShift.  (If shift+j >= bitShift then
 329                 // we'll be bleeding other bit types like bitMarked into our test.)
 330                 // Instead of inserting the conditional shift+j < bitShift into the loop,
 331                 // we can let j range from 1 to bitShift as long as we first
 332                 // apply a mask to keep only the bits corresponding
 333                 // to shift+j < bitShift aka j < bitShift-shift.
 334                 bits &= (boundary<<(bitShift-shift)) - boundary;
 335
 336                 // A block boundary j words before b is indicated by
 337                 //      xbits>>(shift-j) & boundary
 338                 // (assuming shift >= j).  There is no cleverness here
 339                 // avoid the test, because when j gets too large the shift
 340                 // turns negative, which is undefined in C.
 341
 342                 for(j=1; j<bitShift; j++) {
 343                         if(((bits>>j)&boundary) != 0 || (shift>=j && ((xbits>>(shift-j))&boundary) != 0)) {
 344                                 n = j*PtrSize;
 345                                 goto scan;
 346                         }
 347                 }
 348
 349                 // Fall back to asking span about size class.
 350                 // (Manually inlined copy of MHeap_Lookup.)
 351                 nlookup++;
 352                 nsizelookup++;
 353                 x = (uintptr)b>>PageShift;
 354                 if(sizeof(void*) == 8)
 355                         x -= (uintptr)arena_start>>PageShift;
 356                 s = runtime_mheap.map[x];
 357                 if(s->sizeclass == 0)
 358                         n = s->npages<<PageShift;
 359                 else
 360                         n = runtime_class_to_size[s->sizeclass];
 361         scan:;
 362         }
 363 }
 364
 365 // debug_scanblock is the debug copy of scanblock.
 366 // it is simpler, slower, single-threaded, recursive,
 367 // and uses bitSpecial as the mark bit.
 368 static void
 369 debug_scanblock(byte *b, int64 n)
 370 {
 371         byte *obj, *p;
 372         void **vp;
 373         uintptr size, *bitp, bits, shift, i, xbits, off;
 374         MSpan *s;
 375
 376         if(!DebugMark)
 377                 runtime_throw("debug_scanblock without DebugMark");
 378
 379         if((int64)(uintptr)n != n || n < 0) {
 380                 //runtime_printf("debug_scanblock %p %D\n", b, n);
 381                 runtime_throw("debug_scanblock");
 382         }
 383
 384         // Align b to a word boundary.
 385         off = (uintptr)b & (PtrSize-1);
 386         if(off != 0) {
 387                 b += PtrSize - off;
 388                 n -= PtrSize - off;
 389         }
 390
 391         vp = (void**)b;
 392         n /= PtrSize;
 393         for(i=0; i<(uintptr)n; i++) {
 394                 obj = (byte*)vp[i];
 395
 396                 // Words outside the arena cannot be pointers.
 397                 if((byte*)obj < runtime_mheap.arena_start || (byte*)obj >= runtime_mheap.arena_used)
 398                         continue;
 399
 400                 // Round down to word boundary.
 401                 obj = (void*)((uintptr)obj & ~((uintptr)PtrSize-1));
 402
 403                 // Consult span table to find beginning.
 404                 s = runtime_MHeap_LookupMaybe(&runtime_mheap, obj);
 405                 if(s == nil)
 406                         continue;
 407
 408
 409                 p =  (byte*)((uintptr)s->start<<PageShift);
 410                 if(s->sizeclass == 0) {
 411                         obj = p;
 412                         size = (uintptr)s->npages<<PageShift;
 413                 } else {
 414                         if((byte*)obj >= (byte*)s->limit)
 415                                 continue;
 416                         size = runtime_class_to_size[s->sizeclass];
 417                         int32 i = ((byte*)obj - p)/size;
 418                         obj = p+i*size;
 419                 }
 420
 421                 // Now that we know the object header, reload bits.
 422                 off = (uintptr*)obj - (uintptr*)runtime_mheap.arena_start;
 423                 bitp = (uintptr*)runtime_mheap.arena_start - off/wordsPerBitmapWord - 1;
 424                 shift = off % wordsPerBitmapWord;
 425                 xbits = *bitp;
 426                 bits = xbits >> shift;
 427
 428                 // Now we have bits, bitp, and shift correct for
 429                 // obj pointing at the base of the object.
 430                 // If not allocated or already marked, done.
 431                 if((bits & bitAllocated) == 0 || (bits & bitSpecial) != 0)  // NOTE: bitSpecial not bitMarked
 432                         continue;
 433                 *bitp |= bitSpecial<<shift;
 434                 if(!(bits & bitMarked))
 435                         runtime_printf("found unmarked block %p in %p\n", obj, vp+i);
 436
 437                 // If object has no pointers, don't need to scan further.
 438                 if((bits & bitNoPointers) != 0)
 439                         continue;
 440
 441                 debug_scanblock(obj, size);
 442         }
 443 }
 444
 445 // Get an empty work buffer off the work.empty list,
 446 // allocating new buffers as needed.
 447 static Workbuf*
 448 getempty(Workbuf *b)
 449 {
 450         if(work.nproc == 1) {
 451                 // Put b on full list.
 452                 if(b != nil) {
 453                         b->next = work.full;
 454                         work.full = b;
 455                 }
 456                 // Grab from empty list if possible.
 457                 b = work.empty;
 458                 if(b != nil) {
 459                         work.empty = b->next;
 460                         goto haveb;
 461                 }
 462         } else {
 463                 // Put b on full list.
 464                 if(b != nil) {
 465                         runtime_lock(&work.fmu);
 466                         b->next = work.full;
 467                         work.full = b;
 468                         runtime_unlock(&work.fmu);
 469                 }
 470                 // Grab from empty list if possible.
 471                 runtime_lock(&work.emu);
 472                 b = work.empty;
 473                 if(b != nil)
 474                         work.empty = b->next;
 475                 runtime_unlock(&work.emu);
 476                 if(b != nil)
 477                         goto haveb;
 478         }
 479
 480         // Need to allocate.
 481         runtime_lock(&work);
 482         if(work.nchunk < sizeof *b) {
 483                 work.nchunk = 1<<20;
 484                 work.chunk = runtime_SysAlloc(work.nchunk);
 485         }
 486         b = (Workbuf*)work.chunk;
 487         work.chunk += sizeof *b;
 488         work.nchunk -= sizeof *b;
 489         runtime_unlock(&work);
 490
 491 haveb:
 492         b->nobj = 0;
 493         return b;
 494 }
 495
 496 static void
 497 putempty(Workbuf *b)
 498 {
 499         if(b == nil)
 500                 return;
 501
 502         if(work.nproc == 1) {
 503                 b->next = work.empty;
 504                 work.empty = b;
 505                 return;
 506         }
 507
 508         runtime_lock(&work.emu);
 509         b->next = work.empty;
 510         work.empty = b;
 511         runtime_unlock(&work.emu);
 512 }
 513
 514 // Get a full work buffer off the work.full list, or return nil.
 515 static Workbuf*
 516 getfull(Workbuf *b)
 517 {
 518         int32 i;
 519         Workbuf *b1;
 520
 521         if(work.nproc == 1) {
 522                 // Put b on empty list.
 523                 if(b != nil) {
 524                         b->next = work.empty;
 525                         work.empty = b;
 526                 }
 527                 // Grab from full list if possible.
 528                 // Since work.nproc==1, no one else is
 529                 // going to give us work.
 530                 b = work.full;
 531                 if(b != nil)
 532                         work.full = b->next;
 533                 return b;
 534         }
 535
 536         putempty(b);
 537
 538         // Grab buffer from full list if possible.
 539         for(;;) {
 540                 b1 = work.full;
 541                 if(b1 == nil)
 542                         break;
 543                 runtime_lock(&work.fmu);
 544                 if(work.full != nil) {
 545                         b1 = work.full;
 546                         work.full = b1->next;
 547                         runtime_unlock(&work.fmu);
 548                         return b1;
 549                 }
 550                 runtime_unlock(&work.fmu);
 551         }
 552
 553         runtime_xadd(&work.nwait, +1);
 554         for(i=0;; i++) {
 555                 b1 = work.full;
 556                 if(b1 != nil) {
 557                         runtime_lock(&work.fmu);
 558                         if(work.full != nil) {
 559                                 runtime_xadd(&work.nwait, -1);
 560                                 b1 = work.full;
 561                                 work.full = b1->next;
 562                                 runtime_unlock(&work.fmu);
 563                                 return b1;
 564                         }
 565                         runtime_unlock(&work.fmu);
 566                         continue;
 567                 }
 568                 if(work.nwait == work.nproc)
 569                         return nil;
 570                 if(i < 10)
 571                         runtime_procyield(20);
 572                 else if(i < 20)
 573                         runtime_osyield();
 574                 else
 575                         runtime_usleep(100);
 576         }
 577 }
 578
 579 static Workbuf*
 580 handoff(Workbuf *b)
 581 {
 582         int32 n;
 583         Workbuf *b1;
 584
 585         // Make new buffer with half of b's pointers.
 586         b1 = getempty(nil);
 587         n = b->nobj/2;
 588         b->nobj -= n;
 589         b1->nobj = n;
 590         runtime_memmove(b1->obj, b->obj+b->nobj, n*sizeof b1->obj[0]);
 591         nhandoff += n;
 592
 593         // Put b on full list - let first half of b get stolen.
 594         runtime_lock(&work.fmu);
 595         b->next = work.full;
 596         work.full = b;
 597         runtime_unlock(&work.fmu);
 598
 599         return b1;
 600 }
 601
 602 // Scanstack calls scanblock on each of gp's stack segments.
 603 static void
 604 scanstack(void (*scanblock)(byte*, int64), G *gp)
 605 {
 606 #ifdef USING_SPLIT_STACK
 607         M *mp;
 608         void* sp;
 609         size_t spsize;
 610         void* next_segment;
 611         void* next_sp;
 612         void* initial_sp;
 613
 614         if(gp == runtime_g()) {
 615                 // Scanning our own stack.
 616                 sp = __splitstack_find(nil, nil, &spsize, &next_segment,
 617                                        &next_sp, &initial_sp);
 618         } else if((mp = gp->m) != nil && mp->helpgc) {
 619                 // gchelper's stack is in active use and has no interesting pointers.
 620                 return;
 621         } else {
 622                 // Scanning another goroutine's stack.
 623                 // The goroutine is usually asleep (the world is stopped).
 624
 625                 // The exception is that if the goroutine is about to enter or might
 626                 // have just exited a system call, it may be executing code such
 627                 // as schedlock and may have needed to start a new stack segment.
 628                 // Use the stack segment and stack pointer at the time of
 629                 // the system call instead, since that won't change underfoot.
 630                 if(gp->gcstack != nil) {
 631                         sp = gp->gcstack;
 632                         spsize = gp->gcstack_size;
 633                         next_segment = gp->gcnext_segment;
 634                         next_sp = gp->gcnext_sp;
 635                         initial_sp = gp->gcinitial_sp;
 636                 } else {
 637                         sp = __splitstack_find_context(&gp->stack_context[0],
 638                                                        &spsize, &next_segment,
 639                                                        &next_sp, &initial_sp);
 640                 }
 641         }
 642         if(sp != nil) {
 643                 scanblock(sp, spsize);
 644                 while((sp = __splitstack_find(next_segment, next_sp,
 645                                               &spsize, &next_segment,
 646                                               &next_sp, &initial_sp)) != nil)
 647                         scanblock(sp, spsize);
 648         }
 649 #else
 650         M *mp;
 651         byte* bottom;
 652         byte* top;
 653
 654         if(gp == runtime_g()) {
 655                 // Scanning our own stack.
 656                 bottom = (byte*)&gp;
 657         } else if((mp = gp->m) != nil && mp->helpgc) {
 658                 // gchelper's stack is in active use and has no interesting pointers.
 659                 return;
 660         } else {
 661                 // Scanning another goroutine's stack.
 662                 // The goroutine is usually asleep (the world is stopped).
 663                 bottom = (byte*)gp->gcnext_sp;
 664                 if(bottom == nil)
 665                         return;
 666         }
 667         top = (byte*)gp->gcinitial_sp + gp->gcstack_size;
 668         if(top > bottom)
 669                 scanblock(bottom, top - bottom);
 670         else
 671                 scanblock(top, bottom - top);
 672 #endif
 673 }
 674
 675 // Markfin calls scanblock on the blocks that have finalizers:
 676 // the things pointed at cannot be freed until the finalizers have run.
 677 static void
 678 markfin(void *v)
 679 {
 680         uintptr size;
 681
 682         size = 0;
 683         if(!runtime_mlookup(v, (byte**)&v, &size, nil) || !runtime_blockspecial(v))
 684                 runtime_throw("mark - finalizer inconsistency");
 685
 686         // do not mark the finalizer block itself.  just mark the things it points at.
 687         scanblock(v, size);
 688 }
 689
 690 struct root_list {
 691         struct root_list *next;
 692         struct root {
 693                 void *decl;
 694                 size_t size;
 695         } roots[];
 696 };
 697
 698 static struct root_list* roots;
 699
 700 void
 701 __go_register_gc_roots (struct root_list* r)
 702 {
 703         // FIXME: This needs locking if multiple goroutines can call
 704         // dlopen simultaneously.
 705         r->next = roots;
 706         roots = r;
 707 }
 708
 709 static void
 710 debug_markfin(void *v)
 711 {
 712         uintptr size;
 713
 714         if(!runtime_mlookup(v, (byte**)&v, &size, nil))
 715                 runtime_throw("debug_mark - finalizer inconsistency");
 716         debug_scanblock(v, size);
 717 }
 718
 719 // Mark
 720 static void
 721 mark(void (*scan)(byte*, int64))
 722 {
 723         struct root_list *pl;
 724         G *gp;
 725         FinBlock *fb;
 726
 727         // mark data+bss.
 728         for(pl = roots; pl != nil; pl = pl->next) {
 729                 struct root* pr = &pl->roots[0];
 730                 while(1) {
 731                         void *decl = pr->decl;
 732                         if(decl == nil)
 733                                 break;
 734                         scanblock(decl, pr->size);
 735                         pr++;
 736                 }
 737         }
 738
 739         scan((byte*)&runtime_m0, sizeof runtime_m0);
 740         scan((byte*)&runtime_g0, sizeof runtime_g0);
 741         scan((byte*)&runtime_allg, sizeof runtime_allg);
 742         scan((byte*)&runtime_allm, sizeof runtime_allm);
 743         runtime_MProf_Mark(scan);
 744         runtime_time_scan(scan);
 745
 746         // mark stacks
 747         for(gp=runtime_allg; gp!=nil; gp=gp->alllink) {
 748                 switch(gp->status){
 749                 default:
 750                         runtime_printf("unexpected G.status %d\n", gp->status);
 751                         runtime_throw("mark - bad status");
 752                 case Gdead:
 753                         break;
 754                 case Grunning:
 755                         if(gp != runtime_g())
 756                                 runtime_throw("mark - world not stopped");
 757                         scanstack(scan, gp);
 758                         break;
 759                 case Grunnable:
 760                 case Gsyscall:
 761                 case Gwaiting:
 762                         scanstack(scan, gp);
 763                         break;
 764                 }
 765         }
 766
 767         // mark things pointed at by objects with finalizers
 768         if(scan == debug_scanblock)
 769                 runtime_walkfintab(debug_markfin, scan);
 770         else
 771                 runtime_walkfintab(markfin, scan);
 772
 773         for(fb=allfin; fb; fb=fb->alllink)
 774                 scanblock((byte*)fb->fin, fb->cnt*sizeof(fb->fin[0]));
 775
 776         // in multiproc mode, join in the queued work.
 777         scan(nil, 0);
 778 }
 779
 780 static bool
 781 handlespecial(byte *p, uintptr size)
 782 {
 783         void (*fn)(void*);
 784         const struct __go_func_type *ft;
 785         FinBlock *block;
 786         Finalizer *f;
 787
 788         if(!runtime_getfinalizer(p, true, &fn, &ft)) {
 789                 runtime_setblockspecial(p, false);
 790                 runtime_MProf_Free(p, size);
 791                 return false;
 792         }
 793
 794         runtime_lock(&finlock);
 795         if(finq == nil || finq->cnt == finq->cap) {
 796                 if(finc == nil) {
 797                         finc = runtime_SysAlloc(PageSize);
 798                         finc->cap = (PageSize - sizeof(FinBlock)) / sizeof(Finalizer) + 1;
 799                         finc->alllink = allfin;
 800                         allfin = finc;
 801                 }
 802                 block = finc;
 803                 finc = block->next;
 804                 block->next = finq;
 805                 finq = block;
 806         }
 807         f = &finq->fin[finq->cnt];
 808         finq->cnt++;
 809         f->fn = fn;
 810         f->ft = ft;
 811         f->arg = p;
 812         runtime_unlock(&finlock);
 813         return true;
 814 }
 815
 816 // Sweep frees or collects finalizers for blocks not marked in the mark phase.
 817 // It clears the mark bits in preparation for the next GC round.
 818 static void
 819 sweep(void)
 820 {
 821         M *m;
 822         MSpan *s;
 823         int32 cl, n, npages;
 824         uintptr size;
 825         byte *p;
 826         MCache *c;
 827         byte *arena_start;
 828
 829         m = runtime_m();
 830         arena_start = runtime_mheap.arena_start;
 831
 832         for(;;) {
 833                 s = work.spans;
 834                 if(s == nil)
 835                         break;
 836                 if(!runtime_casp(&work.spans, s, s->allnext))
 837                         continue;
 838
 839                 if(s->state != MSpanInUse)
 840                         continue;
 841
 842                 p = (byte*)(s->start << PageShift);
 843                 cl = s->sizeclass;
 844                 if(cl == 0) {
 845                         size = s->npages<<PageShift;
 846                         n = 1;
 847                 } else {
 848                         // Chunk full of small blocks.
 849                         size = runtime_class_to_size[cl];
 850                         npages = runtime_class_to_allocnpages[cl];
 851                         n = (npages << PageShift) / size;
 852                 }
 853
 854                 // Sweep through n objects of given size starting at p.
 855                 // This thread owns the span now, so it can manipulate
 856                 // the block bitmap without atomic operations.
 857                 for(; n > 0; n--, p += size) {
 858                         uintptr off, *bitp, shift, bits;
 859
 860                         off = (uintptr*)p - (uintptr*)arena_start;
 861                         bitp = (uintptr*)arena_start - off/wordsPerBitmapWord - 1;
 862                         shift = off % wordsPerBitmapWord;
 863                         bits = *bitp>>shift;
 864
 865                         if((bits & bitAllocated) == 0)
 866                                 continue;
 867
 868                         if((bits & bitMarked) != 0) {
 869                                 if(DebugMark) {
 870                                         if(!(bits & bitSpecial))
 871                                                 runtime_printf("found spurious mark on %p\n", p);
 872                                         *bitp &= ~(bitSpecial<<shift);
 873                                 }
 874                                 *bitp &= ~(bitMarked<<shift);
 875                                 continue;
 876                         }
 877
 878                         // Special means it has a finalizer or is being profiled.
 879                         // In DebugMark mode, the bit has been coopted so
 880                         // we have to assume all blocks are special.
 881                         if(DebugMark || (bits & bitSpecial) != 0) {
 882                                 if(handlespecial(p, size))
 883                                         continue;
 884                         }
 885
 886                         // Mark freed; restore block boundary bit.
 887                         *bitp = (*bitp & ~(bitMask<<shift)) | (bitBlockBoundary<<shift);
 888
 889                         c = m->mcache;
 890                         if(s->sizeclass == 0) {
 891                                 // Free large span.
 892                                 runtime_unmarkspan(p, 1<<PageShift);
 893                                 *(uintptr*)p = 1;       // needs zeroing
 894                                 runtime_MHeap_Free(&runtime_mheap, s, 1);
 895                         } else {
 896                                 // Free small object.
 897                                 if(size > sizeof(uintptr))
 898                                         ((uintptr*)p)[1] = 1;   // mark as "needs to be zeroed"
 899                                 c->local_by_size[s->sizeclass].nfree++;
 900                                 runtime_MCache_Free(c, p, s->sizeclass, size);
 901                         }
 902                         c->local_alloc -= size;
 903                         c->local_nfree++;
 904                 }
 905         }
 906 }
 907
 908 void
 909 runtime_gchelper(void)
 910 {
 911         // Wait until main proc is ready for mark help.
 912         runtime_lock(&work.markgate);
 913         runtime_unlock(&work.markgate);
 914         scanblock(nil, 0);
 915
 916         // Wait until main proc is ready for sweep help.
 917         runtime_lock(&work.sweepgate);
 918         runtime_unlock(&work.sweepgate);
 919         sweep();
 920
 921         if(runtime_xadd(&work.ndone, +1) == work.nproc-1)
 922                 runtime_notewakeup(&work.alldone);
 923 }
 924
 925 // Semaphore, not Lock, so that the goroutine
 926 // reschedules when there is contention rather
 927 // than spinning.
 928 static uint32 gcsema = 1;
 929
 930 // Initialized from $GOGC.  GOGC=off means no gc.
 931 //
 932 // Next gc is after we've allocated an extra amount of
 933 // memory proportional to the amount already in use.
 934 // If gcpercent=100 and we're using 4M, we'll gc again
 935 // when we get to 8M.  This keeps the gc cost in linear
 936 // proportion to the allocation cost.  Adjusting gcpercent
 937 // just changes the linear constant (and also the amount of
 938 // extra memory used).
 939 static int32 gcpercent = -2;
 940
 941 static void
 942 stealcache(void)
 943 {
 944         M *m;
 945
 946         for(m=runtime_allm; m; m=m->alllink)
 947                 runtime_MCache_ReleaseAll(m->mcache);
 948 }
 949
 950 static void
 951 cachestats(void)
 952 {
 953         M *m;
 954         MCache *c;
 955         uint32 i;
 956         uint64 stacks_inuse;
 957         uint64 stacks_sys;
 958
 959         stacks_inuse = 0;
 960         stacks_sys = 0;
 961         for(m=runtime_allm; m; m=m->alllink) {
 962                 runtime_purgecachedstats(m);
 963                 // stacks_inuse += m->stackalloc->inuse;
 964                 // stacks_sys += m->stackalloc->sys;
 965                 c = m->mcache;
 966                 for(i=0; i<nelem(c->local_by_size); i++) {
 967                         mstats.by_size[i].nmalloc += c->local_by_size[i].nmalloc;
 968                         c->local_by_size[i].nmalloc = 0;
 969                         mstats.by_size[i].nfree += c->local_by_size[i].nfree;
 970                         c->local_by_size[i].nfree = 0;
 971                 }
 972         }
 973         mstats.stacks_inuse = stacks_inuse;
 974         mstats.stacks_sys = stacks_sys;
 975 }
 976
 977 void
 978 runtime_gc(int32 force)
 979 {
 980         M *m;
 981         int64 t0, t1, t2, t3;
 982         uint64 heap0, heap1, obj0, obj1;
 983         const byte *p;
 984         bool extra;
 985
 986         // The gc is turned off (via enablegc) until
 987         // the bootstrap has completed.
 988         // Also, malloc gets called in the guts
 989         // of a number of libraries that might be
 990         // holding locks.  To avoid priority inversion
 991         // problems, don't bother trying to run gc
 992         // while holding a lock.  The next mallocgc
 993         // without a lock will do the gc instead.
 994         m = runtime_m();
 995         if(!mstats.enablegc || m->locks > 0 || runtime_panicking)
 996                 return;
 997
 998         if(gcpercent == -2) {   // first time through
 999                 p = runtime_getenv("GOGC");
1000                 if(p == nil || p[0] == '\0')
1001                         gcpercent = 100;
1002                 else if(runtime_strcmp((const char*)p, "off") == 0)
1003                         gcpercent = -1;
1004                 else
1005                         gcpercent = runtime_atoi(p);
1006
1007                 p = runtime_getenv("GOGCTRACE");
1008                 if(p != nil)
1009                         gctrace = runtime_atoi(p);
1010         }
1011         if(gcpercent < 0)
1012                 return;
1013
1014         runtime_semacquire(&gcsema);
1015         if(!force && mstats.heap_alloc < mstats.next_gc) {
1016                 runtime_semrelease(&gcsema);
1017                 return;
1018         }
1019
1020         t0 = runtime_nanotime();
1021         nlookup = 0;
1022         nsizelookup = 0;
1023         naddrlookup = 0;
1024         nhandoff = 0;
1025
1026         m->gcing = 1;
1027         runtime_stoptheworld();
1028
1029         cachestats();
1030         heap0 = mstats.heap_alloc;
1031         obj0 = mstats.nmalloc - mstats.nfree;
1032
1033         runtime_lock(&work.markgate);
1034         runtime_lock(&work.sweepgate);
1035
1036         extra = false;
1037         work.nproc = 1;
1038         if(runtime_gomaxprocs > 1 && runtime_ncpu > 1) {
1039                 runtime_noteclear(&work.alldone);
1040                 work.nproc += runtime_helpgc(&extra);
1041         }
1042         work.nwait = 0;
1043         work.ndone = 0;
1044
1045         runtime_unlock(&work.markgate);  // let the helpers in
1046         mark(scanblock);
1047         if(DebugMark)
1048                 mark(debug_scanblock);
1049         t1 = runtime_nanotime();
1050
1051         work.spans = runtime_mheap.allspans;
1052         runtime_unlock(&work.sweepgate);  // let the helpers in
1053         sweep();
1054         if(work.nproc > 1)
1055                 runtime_notesleep(&work.alldone);
1056         t2 = runtime_nanotime();
1057
1058         stealcache();
1059         cachestats();
1060
1061         mstats.next_gc = mstats.heap_alloc+mstats.heap_alloc*gcpercent/100;
1062         m->gcing = 0;
1063
1064         m->locks++;     // disable gc during the mallocs in newproc
1065         if(finq != nil) {
1066                 // kick off or wake up goroutine to run queued finalizers
1067                 if(fing == nil)
1068                         fing = __go_go(runfinq, nil);
1069                 else if(fingwait) {
1070                         fingwait = 0;
1071                         runtime_ready(fing);
1072                 }
1073         }
1074         m->locks--;
1075
1076         cachestats();
1077         heap1 = mstats.heap_alloc;
1078         obj1 = mstats.nmalloc - mstats.nfree;
1079
1080         t3 = runtime_nanotime();
1081         mstats.pause_ns[mstats.numgc%nelem(mstats.pause_ns)] = t3 - t0;
1082         mstats.pause_total_ns += t3 - t0;
1083         mstats.numgc++;
1084         if(mstats.debuggc)
1085                 runtime_printf("pause %llu\n", (unsigned long long)t3-t0);
1086
1087         if(gctrace) {
1088                 runtime_printf("gc%d: %llu+%llu+%llu ms %llu -> %llu MB %llu -> %llu (%llu-%llu) objects %llu pointer lookups (%llu size, %llu addr) %llu handoff\n",
1089                         mstats.numgc, (unsigned long long)(t1-t0)/1000000, (unsigned long long)(t2-t1)/1000000, (unsigned long long)(t3-t2)/1000000,
1090                         (unsigned long long)heap0>>20, (unsigned long long)heap1>>20, (unsigned long long)obj0, (unsigned long long)obj1,
1091                         (unsigned long long)mstats.nmalloc, (unsigned long long)mstats.nfree,
1092                         (unsigned long long)nlookup, (unsigned long long)nsizelookup, (unsigned long long)naddrlookup, (unsigned long long) nhandoff);
1093         }
1094
1095         runtime_semrelease(&gcsema);
1096
1097         // If we could have used another helper proc, start one now,
1098         // in the hope that it will be available next time.
1099         // It would have been even better to start it before the collection,
1100         // but doing so requires allocating memory, so it's tricky to
1101         // coordinate.  This lazy approach works out in practice:
1102         // we don't mind if the first couple gc rounds don't have quite
1103         // the maximum number of procs.
1104         runtime_starttheworld(extra);
1105
1106         // give the queued finalizers, if any, a chance to run
1107         if(finq != nil)
1108                 runtime_gosched();
1109
1110         if(gctrace > 1 && !force)
1111                 runtime_gc(1);
1112 }
1113
1114 void runtime_UpdateMemStats(void)
1115   __asm__("libgo_runtime.runtime.UpdateMemStats");
1116
1117 void
1118 runtime_UpdateMemStats(void)
1119 {
1120         M *m;
1121
1122         // Have to acquire gcsema to stop the world,
1123         // because stoptheworld can only be used by
1124         // one goroutine at a time, and there might be
1125         // a pending garbage collection already calling it.
1126         runtime_semacquire(&gcsema);
1127         m = runtime_m();
1128         m->gcing = 1;
1129         runtime_stoptheworld();
1130         cachestats();
1131         m->gcing = 0;
1132         runtime_semrelease(&gcsema);
1133         runtime_starttheworld(false);
1134 }
1135
1136 static void
1137 runfinq(void* dummy __attribute__ ((unused)))
1138 {
1139         G* gp;
1140         Finalizer *f;
1141         FinBlock *fb, *next;
1142         uint32 i;
1143
1144         gp = runtime_g();
1145         for(;;) {
1146                 // There's no need for a lock in this section
1147                 // because it only conflicts with the garbage
1148                 // collector, and the garbage collector only
1149                 // runs when everyone else is stopped, and
1150                 // runfinq only stops at the gosched() or
1151                 // during the calls in the for loop.
1152                 fb = finq;
1153                 finq = nil;
1154                 if(fb == nil) {
1155                         fingwait = 1;
1156                         gp->status = Gwaiting;
1157                         gp->waitreason = "finalizer wait";
1158                         runtime_gosched();
1159                         continue;
1160                 }
1161                 for(; fb; fb=next) {
1162                         next = fb->next;
1163                         for(i=0; i<(uint32)fb->cnt; i++) {
1164                                 void *params[1];
1165
1166                                 f = &fb->fin[i];
1167                                 params[0] = &f->arg;
1168                                 runtime_setblockspecial(f->arg, false);
1169                                 reflect_call(f->ft, (void*)f->fn, 0, 0, params, nil);
1170                                 f->fn = nil;
1171                                 f->arg = nil;
1172                         }
1173                         fb->cnt = 0;
1174                         fb->next = finc;
1175                         finc = fb;
1176                 }
1177                 runtime_gc(1);  // trigger another gc to clean up the finalized objects, if possible
1178         }
1179 }
1180
1181 // mark the block at v of size n as allocated.
1182 // If noptr is true, mark it as having no pointers.
1183 void
1184 runtime_markallocated(void *v, uintptr n, bool noptr)
1185 {
1186         uintptr *b, obits, bits, off, shift;
1187
1188         // if(0)
1189                 // runtime_printf("markallocated %p+%p\n", v, n);
1190
1191         if((byte*)v+n > (byte*)runtime_mheap.arena_used || (byte*)v < runtime_mheap.arena_start)
1192                 runtime_throw("markallocated: bad pointer");
1193
1194         off = (uintptr*)v - (uintptr*)runtime_mheap.arena_start;  // word offset
1195         b = (uintptr*)runtime_mheap.arena_start - off/wordsPerBitmapWord - 1;
1196         shift = off % wordsPerBitmapWord;
1197
1198         for(;;) {
1199                 obits = *b;
1200                 bits = (obits & ~(bitMask<<shift)) | (bitAllocated<<shift);
1201                 if(noptr)
1202                         bits |= bitNoPointers<<shift;
1203                 if(runtime_singleproc) {
1204                         *b = bits;
1205                         break;
1206                 } else {
1207                         // more than one goroutine is potentially running: use atomic op
1208                         if(runtime_casp((void**)b, (void*)obits, (void*)bits))
1209                                 break;
1210                 }
1211         }
1212 }
1213
1214 // mark the block at v of size n as freed.
1215 void
1216 runtime_markfreed(void *v, uintptr n)
1217 {
1218         uintptr *b, obits, bits, off, shift;
1219
1220         // if(0)
1221                 // runtime_printf("markallocated %p+%p\n", v, n);
1222
1223         if((byte*)v+n > (byte*)runtime_mheap.arena_used || (byte*)v < runtime_mheap.arena_start)
1224                 runtime_throw("markallocated: bad pointer");
1225
1226         off = (uintptr*)v - (uintptr*)runtime_mheap.arena_start;  // word offset
1227         b = (uintptr*)runtime_mheap.arena_start - off/wordsPerBitmapWord - 1;
1228         shift = off % wordsPerBitmapWord;
1229
1230         for(;;) {
1231                 obits = *b;
1232                 bits = (obits & ~(bitMask<<shift)) | (bitBlockBoundary<<shift);
1233                 if(runtime_singleproc) {
1234                         *b = bits;
1235                         break;
1236                 } else {
1237                         // more than one goroutine is potentially running: use atomic op
1238                         if(runtime_casp((void**)b, (void*)obits, (void*)bits))
1239                                 break;
1240                 }
1241         }
1242 }
1243
1244 // check that the block at v of size n is marked freed.
1245 void
1246 runtime_checkfreed(void *v, uintptr n)
1247 {
1248         uintptr *b, bits, off, shift;
1249
1250         if(!runtime_checking)
1251                 return;
1252
1253         if((byte*)v+n > (byte*)runtime_mheap.arena_used || (byte*)v < runtime_mheap.arena_start)
1254                 return; // not allocated, so okay
1255
1256         off = (uintptr*)v - (uintptr*)runtime_mheap.arena_start;  // word offset
1257         b = (uintptr*)runtime_mheap.arena_start - off/wordsPerBitmapWord - 1;
1258         shift = off % wordsPerBitmapWord;
1259
1260         bits = *b>>shift;
1261         if((bits & bitAllocated) != 0) {
1262                 runtime_printf("checkfreed %p+%p: off=%p have=%p\n",
1263                         v, (void*)n, (void*)off, (void*)(bits & bitMask));
1264                 runtime_throw("checkfreed: not freed");
1265         }
1266 }
1267
1268 // mark the span of memory at v as having n blocks of the given size.
1269 // if leftover is true, there is left over space at the end of the span.
1270 void
1271 runtime_markspan(void *v, uintptr size, uintptr n, bool leftover)
1272 {
1273         uintptr *b, off, shift;
1274         byte *p;
1275
1276         if((byte*)v+size*n > (byte*)runtime_mheap.arena_used || (byte*)v < runtime_mheap.arena_start)
1277                 runtime_throw("markspan: bad pointer");
1278
1279         p = v;
1280         if(leftover)    // mark a boundary just past end of last block too
1281                 n++;
1282         for(; n-- > 0; p += size) {
1283                 // Okay to use non-atomic ops here, because we control
1284                 // the entire span, and each bitmap word has bits for only
1285                 // one span, so no other goroutines are changing these
1286                 // bitmap words.
1287                 off = (uintptr*)p - (uintptr*)runtime_mheap.arena_start;  // word offset
1288                 b = (uintptr*)runtime_mheap.arena_start - off/wordsPerBitmapWord - 1;
1289                 shift = off % wordsPerBitmapWord;
1290                 *b = (*b & ~(bitMask<<shift)) | (bitBlockBoundary<<shift);
1291         }
1292 }
1293
1294 // unmark the span of memory at v of length n bytes.
1295 void
1296 runtime_unmarkspan(void *v, uintptr n)
1297 {
1298         uintptr *p, *b, off;
1299
1300         if((byte*)v+n > (byte*)runtime_mheap.arena_used || (byte*)v < runtime_mheap.arena_start)
1301                 runtime_throw("markspan: bad pointer");
1302
1303         p = v;
1304         off = p - (uintptr*)runtime_mheap.arena_start;  // word offset
1305         if(off % wordsPerBitmapWord != 0)
1306                 runtime_throw("markspan: unaligned pointer");
1307         b = (uintptr*)runtime_mheap.arena_start - off/wordsPerBitmapWord - 1;
1308         n /= PtrSize;
1309         if(n%wordsPerBitmapWord != 0)
1310                 runtime_throw("unmarkspan: unaligned length");
1311         // Okay to use non-atomic ops here, because we control
1312         // the entire span, and each bitmap word has bits for only
1313         // one span, so no other goroutines are changing these
1314         // bitmap words.
1315         n /= wordsPerBitmapWord;
1316         while(n-- > 0)
1317                 *b-- = 0;
1318 }
1319
1320 bool
1321 runtime_blockspecial(void *v)
1322 {
1323         uintptr *b, off, shift;
1324
1325         if(DebugMark)
1326                 return true;
1327
1328         off = (uintptr*)v - (uintptr*)runtime_mheap.arena_start;
1329         b = (uintptr*)runtime_mheap.arena_start - off/wordsPerBitmapWord - 1;
1330         shift = off % wordsPerBitmapWord;
1331
1332         return (*b & (bitSpecial<<shift)) != 0;
1333 }
1334
1335 void
1336 runtime_setblockspecial(void *v, bool s)
1337 {
1338         uintptr *b, off, shift, bits, obits;
1339
1340         if(DebugMark)
1341                 return;
1342
1343         off = (uintptr*)v - (uintptr*)runtime_mheap.arena_start;
1344         b = (uintptr*)runtime_mheap.arena_start - off/wordsPerBitmapWord - 1;
1345         shift = off % wordsPerBitmapWord;
1346
1347         for(;;) {
1348                 obits = *b;
1349                 if(s)
1350                         bits = obits | (bitSpecial<<shift);
1351                 else
1352                         bits = obits & ~(bitSpecial<<shift);
1353                 if(runtime_singleproc) {
1354                         *b = bits;
1355                         break;
1356                 } else {
1357                         // more than one goroutine is potentially running: use atomic op
1358                         if(runtime_casp((void**)b, (void*)obits, (void*)bits))
1359                                 break;
1360                 }
1361         }
1362 }
1363
1364 void
1365 runtime_MHeap_MapBits(MHeap *h)
1366 {
1367         // Caller has added extra mappings to the arena.
1368         // Add extra mappings of bitmap words as needed.
1369         // We allocate extra bitmap pieces in chunks of bitmapChunk.
1370         enum {
1371                 bitmapChunk = 8192
1372         };
1373         uintptr n;
1374
1375         n = (h->arena_used - h->arena_start) / wordsPerBitmapWord;
1376         n = (n+bitmapChunk-1) & ~(bitmapChunk-1);
1377         if(h->bitmap_mapped >= n)
1378                 return;
1379
1380         runtime_SysMap(h->arena_start - n, n - h->bitmap_mapped);
1381         h->bitmap_mapped = n;
1382 }