OSDN Git Service

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