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 -- step 0.
   6 //
   7 // Stop the world, mark and sweep garbage collector.
   8 // NOT INTENDED FOR PRODUCTION USE.
   9 //
  10 // A mark and sweep collector provides a way to exercise
  11 // and test the memory allocator and the stack walking machinery
  12 // without also needing to get reference counting
  13 // exactly right.
  14
  15 #include "runtime.h"
  16 #include "malloc.h"
  17
  18 enum {
  19         Debug = 0
  20 };
  21
  22 typedef struct BlockList BlockList;
  23 struct BlockList
  24 {
  25         byte *obj;
  26         uintptr size;
  27 };
  28
  29 static bool finstarted;
  30 static pthread_mutex_t finqlock = PTHREAD_MUTEX_INITIALIZER;
  31 static pthread_cond_t finqcond = PTHREAD_COND_INITIALIZER;
  32 static Finalizer *finq;
  33 static int32 fingwait;
  34 static BlockList *bl, *ebl;
  35
  36 static void runfinq(void*);
  37
  38 enum {
  39         PtrSize = sizeof(void*)
  40 };
  41
  42 static void
  43 scanblock(byte *b, int64 n)
  44 {
  45         int32 off;
  46         void *obj;
  47         uintptr size;
  48         uint32 *refp, ref;
  49         void **vp;
  50         int64 i;
  51         BlockList *w;
  52
  53         w = bl;
  54         w->obj = b;
  55         w->size = n;
  56         w++;
  57
  58         while(w > bl) {
  59                 w--;
  60                 b = w->obj;
  61                 n = w->size;
  62
  63                 if(Debug > 1)
  64                         runtime_printf("scanblock %p %lld\n", b, (long long) n);
  65                 off = (uint32)(uintptr)b & (PtrSize-1);
  66                 if(off) {
  67                         b += PtrSize - off;
  68                         n -= PtrSize - off;
  69                 }
  70
  71                 vp = (void**)b;
  72                 n /= PtrSize;
  73                 for(i=0; i<n; i++) {
  74                         obj = vp[i];
  75                         if(obj == nil)
  76                                 continue;
  77                         if(runtime_mheap.min <= (byte*)obj && (byte*)obj < runtime_mheap.max) {
  78                                 if(runtime_mlookup(obj, (byte**)&obj, &size, nil, &refp)) {
  79                                         ref = *refp;
  80                                         switch(ref & ~RefFlags) {
  81                                         case RefNone:
  82                                                 if(Debug > 1)
  83                                                         runtime_printf("found at %p: ", &vp[i]);
  84                                                 *refp = RefSome | (ref & RefFlags);
  85                                                 if(!(ref & RefNoPointers)) {
  86                                                         if(w >= ebl)
  87                                                                 runtime_throw("scanblock: garbage collection stack overflow");
  88                                                         w->obj = obj;
  89                                                         w->size = size;
  90                                                         w++;
  91                                                 }
  92                                                 break;
  93                                         }
  94                                 }
  95                         }
  96                 }
  97         }
  98 }
  99
 100 static void
 101 markfin(void *v)
 102 {
 103         uintptr size;
 104         uint32 *refp;
 105
 106         size = 0;
 107         refp = nil;
 108         if(!runtime_mlookup(v, (byte**)&v, &size, nil, &refp) || !(*refp & RefHasFinalizer))
 109                 runtime_throw("mark - finalizer inconsistency");
 110
 111         // do not mark the finalizer block itself.  just mark the things it points at.
 112         scanblock(v, size);
 113 }
 114
 115 struct root_list {
 116         struct root_list *next;
 117         struct root {
 118                 void *decl;
 119                 size_t size;
 120         } roots[];
 121 };
 122
 123 static struct root_list* roots;
 124
 125 void
 126 __go_register_gc_roots (struct root_list* r)
 127 {
 128         // FIXME: This needs locking if multiple goroutines can call
 129         // dlopen simultaneously.
 130         r->next = roots;
 131         roots = r;
 132 }
 133
 134 static void
 135 mark(void)
 136 {
 137         uintptr blsize, nobj;
 138         struct root_list *pl;
 139
 140         // Figure out how big an object stack we need.
 141         // Get a new one if we need more than we have
 142         // or we need significantly less than we have.
 143         nobj = mstats.heap_objects;
 144         if(nobj > (uintptr)(ebl - bl) || nobj < (uintptr)(ebl-bl)/4) {
 145                 if(bl != nil)
 146                         runtime_SysFree(bl, (byte*)ebl - (byte*)bl);
 147
 148                 // While we're allocated a new object stack,
 149                 // add 20% headroom and also round up to
 150                 // the nearest page boundary, since mmap
 151                 // will anyway.
 152                 nobj = nobj * 12/10;
 153                 blsize = nobj * sizeof *bl;
 154                 blsize = (blsize + 4095) & ~4095;
 155                 nobj = blsize / sizeof *bl;
 156                 bl = runtime_SysAlloc(blsize);
 157                 ebl = bl + nobj;
 158         }
 159
 160         for(pl = roots; pl != nil; pl = pl->next) {
 161                 struct root* pr = &pl->roots[0];
 162                 while(1) {
 163                         void *decl = pr->decl;
 164                         if(decl == nil)
 165                                 break;
 166                         scanblock(decl, pr->size);
 167                         pr++;
 168                 }
 169         }
 170
 171         scanblock((byte*)&m0, sizeof m0);
 172         scanblock((byte*)&finq, sizeof finq);
 173         runtime_MProf_Mark(scanblock);
 174
 175         // mark stacks
 176         __go_scanstacks(scanblock);
 177
 178         // mark things pointed at by objects with finalizers
 179         runtime_walkfintab(markfin, scanblock);
 180 }
 181
 182 // free RefNone, free & queue finalizers for RefNone|RefHasFinalizer, reset RefSome
 183 static void
 184 sweepspan(MSpan *s)
 185 {
 186         int32 n, npages, size;
 187         byte *p;
 188         uint32 ref, *gcrefp, *gcrefep;
 189         MCache *c;
 190         Finalizer *f;
 191
 192         p = (byte*)(s->start << PageShift);
 193         if(s->sizeclass == 0) {
 194                 // Large block.
 195                 ref = s->gcref0;
 196                 switch(ref & ~(RefFlags^RefHasFinalizer)) {
 197                 case RefNone:
 198                         // Free large object.
 199                         mstats.alloc -= s->npages<<PageShift;
 200                         mstats.nfree++;
 201                         runtime_memclr(p, s->npages<<PageShift);
 202                         if(ref & RefProfiled)
 203                                 runtime_MProf_Free(p, s->npages<<PageShift);
 204                         s->gcref0 = RefFree;
 205                         runtime_MHeap_Free(&runtime_mheap, s, 1);
 206                         break;
 207                 case RefNone|RefHasFinalizer:
 208                         f = runtime_getfinalizer(p, 1);
 209                         if(f == nil)
 210                                 runtime_throw("finalizer inconsistency");
 211                         f->arg = p;
 212                         f->next = finq;
 213                         finq = f;
 214                         ref &= ~RefHasFinalizer;
 215                         // fall through
 216                 case RefSome:
 217                 case RefSome|RefHasFinalizer:
 218                         s->gcref0 = RefNone | (ref&RefFlags);
 219                         break;
 220                 }
 221                 return;
 222         }
 223
 224         // Chunk full of small blocks.
 225         runtime_MGetSizeClassInfo(s->sizeclass, &size, &npages, &n);
 226         gcrefp = s->gcref;
 227         gcrefep = s->gcref + n;
 228         for(; gcrefp < gcrefep; gcrefp++, p += size) {
 229                 ref = *gcrefp;
 230                 if(ref < RefNone)       // RefFree or RefStack
 231                         continue;
 232                 switch(ref & ~(RefFlags^RefHasFinalizer)) {
 233                 case RefNone:
 234                         // Free small object.
 235                         if(ref & RefProfiled)
 236                                 runtime_MProf_Free(p, size);
 237                         *gcrefp = RefFree;
 238                         c = m->mcache;
 239                         if(size > (int32)sizeof(uintptr))
 240                                 ((uintptr*)p)[1] = 1;   // mark as "needs to be zeroed"
 241                         mstats.alloc -= size;
 242                         mstats.nfree++;
 243                         mstats.by_size[s->sizeclass].nfree++;
 244                         runtime_MCache_Free(c, p, s->sizeclass, size);
 245                         break;
 246                 case RefNone|RefHasFinalizer:
 247                         f = runtime_getfinalizer(p, 1);
 248                         if(f == nil)
 249                                 runtime_throw("finalizer inconsistency");
 250                         f->arg = p;
 251                         f->next = finq;
 252                         finq = f;
 253                         ref &= ~RefHasFinalizer;
 254                         // fall through
 255                 case RefSome:
 256                 case RefSome|RefHasFinalizer:
 257                         *gcrefp = RefNone | (ref&RefFlags);
 258                         break;
 259                 }
 260         }
 261 }
 262
 263 static void
 264 sweep(void)
 265 {
 266         MSpan *s;
 267
 268         for(s = runtime_mheap.allspans; s != nil; s = s->allnext)
 269                 if(s->state == MSpanInUse)
 270                         sweepspan(s);
 271 }
 272
 273 static pthread_mutex_t gcsema = PTHREAD_MUTEX_INITIALIZER;
 274
 275 // Initialized from $GOGC.  GOGC=off means no gc.
 276 //
 277 // Next gc is after we've allocated an extra amount of
 278 // memory proportional to the amount already in use.
 279 // If gcpercent=100 and we're using 4M, we'll gc again
 280 // when we get to 8M.  This keeps the gc cost in linear
 281 // proportion to the allocation cost.  Adjusting gcpercent
 282 // just changes the linear constant (and also the amount of
 283 // extra memory used).
 284 static int32 gcpercent = -2;
 285
 286 void
 287 runtime_gc(int32 force __attribute__ ((unused)))
 288 {
 289         int64 t0, t1;
 290         char *p;
 291         Finalizer *fp;
 292
 293         // The gc is turned off (via enablegc) until
 294         // the bootstrap has completed.
 295         // Also, malloc gets called in the guts
 296         // of a number of libraries that might be
 297         // holding locks.  To avoid priority inversion
 298         // problems, don't bother trying to run gc
 299         // while holding a lock.  The next mallocgc
 300         // without a lock will do the gc instead.
 301         if(!mstats.enablegc || m->locks > 0 /* || runtime_panicking */)
 302                 return;
 303
 304         if(gcpercent == -2) {   // first time through
 305                 p = runtime_getenv("GOGC");
 306                 if(p == nil || p[0] == '\0')
 307                         gcpercent = 100;
 308                 else if(runtime_strcmp(p, "off") == 0)
 309                         gcpercent = -1;
 310                 else
 311                         gcpercent = runtime_atoi(p);
 312         }
 313         if(gcpercent < 0)
 314                 return;
 315
 316         pthread_mutex_lock(&finqlock);
 317         pthread_mutex_lock(&gcsema);
 318         m->locks++;     // disable gc during the mallocs in newproc
 319         t0 = runtime_nanotime();
 320         runtime_stoptheworld();
 321         if(force || mstats.heap_alloc >= mstats.next_gc) {
 322                 __go_cachestats();
 323                 mark();
 324                 sweep();
 325                 __go_stealcache();
 326                 mstats.next_gc = mstats.heap_alloc+mstats.heap_alloc*gcpercent/100;
 327         }
 328
 329         t1 = runtime_nanotime();
 330         mstats.numgc++;
 331         mstats.pause_ns[mstats.numgc%nelem(mstats.pause_ns)] = t1 - t0;
 332         mstats.pause_total_ns += t1 - t0;
 333         if(mstats.debuggc)
 334                 runtime_printf("pause %llu\n", (unsigned long long)t1-t0);
 335         pthread_mutex_unlock(&gcsema);
 336         runtime_starttheworld();
 337
 338         // finqlock is still held.
 339         fp = finq;
 340         if(fp != nil) {
 341                 // kick off or wake up goroutine to run queued finalizers
 342                 if(!finstarted) {
 343                         __go_go(runfinq, nil);
 344                         finstarted = 1;
 345                 }
 346                 else if(fingwait) {
 347                         fingwait = 0;
 348                         pthread_cond_signal(&finqcond);
 349                 }
 350         }
 351         m->locks--;
 352         pthread_mutex_unlock(&finqlock);
 353 }
 354
 355 static void
 356 runfinq(void* dummy)
 357 {
 358         Finalizer *f, *next;
 359
 360         USED(dummy);
 361
 362         for(;;) {
 363                 pthread_mutex_lock(&finqlock);
 364                 f = finq;
 365                 finq = nil;
 366                 if(f == nil) {
 367                         fingwait = 1;
 368                         pthread_cond_wait(&finqcond, &finqlock);
 369                         pthread_mutex_unlock(&finqlock);
 370                         continue;
 371                 }
 372                 pthread_mutex_unlock(&finqlock);
 373                 for(; f; f=next) {
 374                         void *params[1];
 375
 376                         next = f->next;
 377                         params[0] = &f->arg;
 378                         reflect_call(f->ft, (void*)f->fn, 0, params, nil);
 379                         f->fn = nil;
 380                         f->arg = nil;
 381                         f->next = nil;
 382                         runtime_free(f);
 383                 }
 384                 runtime_gc(1);  // trigger another gc to clean up the finalized objects, if possible
 385         }
 386 }
 387
 388 void
 389 __go_enable_gc()
 390 {
 391   mstats.enablegc = 1;
 392 }