blob: 6dcb61091dab240a22f19415761f4f8dd5db279b [file] [log] [blame]
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Garbage collector -- step 0.
//
// Stop the world, mark and sweep garbage collector.
// NOT INTENDED FOR PRODUCTION USE.
//
// A mark and sweep collector provides a way to exercise
// and test the memory allocator and the stack walking machinery
// without also needing to get reference counting
// exactly right.
#include "runtime.h"
#include "malloc.h"
enum {
Debug = 0
};
typedef struct BlockList BlockList;
struct BlockList
{
byte *obj;
uintptr size;
};
extern byte data[];
extern byte etext[];
extern byte end[];
static G *fing;
static Finalizer *finq;
static int32 fingwait;
static BlockList *bl, *ebl;
static void runfinq(void);
enum {
PtrSize = sizeof(void*)
};
static void
scanblock(byte *b, int64 n)
{
int32 off;
void *obj;
uintptr size;
uint32 *refp, ref;
void **vp;
int64 i;
BlockList *w;
w = bl;
w->obj = b;
w->size = n;
w++;
while(w > bl) {
w--;
b = w->obj;
n = w->size;
if(Debug > 1)
runtime·printf("scanblock %p %D\n", b, n);
off = (uint32)(uintptr)b & (PtrSize-1);
if(off) {
b += PtrSize - off;
n -= PtrSize - off;
}
vp = (void**)b;
n /= PtrSize;
for(i=0; i<n; i++) {
obj = vp[i];
if(obj == nil)
continue;
if(runtime·mheap.min <= (byte*)obj && (byte*)obj < runtime·mheap.max) {
if(runtime·mlookup(obj, &obj, &size, nil, &refp)) {
ref = *refp;
switch(ref & ~RefFlags) {
case RefNone:
if(Debug > 1)
runtime·printf("found at %p: ", &vp[i]);
*refp = RefSome | (ref & RefFlags);
if(!(ref & RefNoPointers)) {
if(w >= ebl)
runtime·throw("scanblock: garbage collection stack overflow");
w->obj = obj;
w->size = size;
w++;
}
break;
}
}
}
}
}
}
static void
scanstack(G *gp)
{
Stktop *stk;
byte *sp;
if(gp == g)
sp = (byte*)&gp;
else
sp = gp->sched.sp;
if(Debug > 1)
runtime·printf("scanstack %d %p\n", gp->goid, sp);
stk = (Stktop*)gp->stackbase;
while(stk) {
scanblock(sp, (byte*)stk - sp);
sp = stk->gobuf.sp;
stk = (Stktop*)stk->stackbase;
}
}
static void
markfin(void *v)
{
uintptr size;
uint32 *refp;
size = 0;
refp = nil;
if(!runtime·mlookup(v, &v, &size, nil, &refp) || !(*refp & RefHasFinalizer))
runtime·throw("mark - finalizer inconsistency");
// do not mark the finalizer block itself. just mark the things it points at.
scanblock(v, size);
}
static void
mark(void)
{
G *gp;
uintptr blsize, nobj;
// Figure out how big an object stack we need.
// Get a new one if we need more than we have
// or we need significantly less than we have.
nobj = mstats.heap_objects;
if(nobj > ebl - bl || nobj < (ebl-bl)/4) {
if(bl != nil)
runtime·SysFree(bl, (byte*)ebl - (byte*)bl);
// While we're allocated a new object stack,
// add 20% headroom and also round up to
// the nearest page boundary, since mmap
// will anyway.
nobj = nobj * 12/10;
blsize = nobj * sizeof *bl;
blsize = (blsize + 4095) & ~4095;
nobj = blsize / sizeof *bl;
bl = runtime·SysAlloc(blsize);
ebl = bl + nobj;
}
// mark data+bss.
// skip runtime·mheap itself, which has no interesting pointers
// and is mostly zeroed and would not otherwise be paged in.
scanblock(data, (byte*)&runtime·mheap - data);
scanblock((byte*)(&runtime·mheap+1), end - (byte*)(&runtime·mheap+1));
// mark stacks
for(gp=runtime·allg; gp!=nil; gp=gp->alllink) {
switch(gp->status){
default:
runtime·printf("unexpected G.status %d\n", gp->status);
runtime·throw("mark - bad status");
case Gdead:
break;
case Grunning:
case Grecovery:
if(gp != g)
runtime·throw("mark - world not stopped");
scanstack(gp);
break;
case Grunnable:
case Gsyscall:
case Gwaiting:
scanstack(gp);
break;
}
}
// mark things pointed at by objects with finalizers
runtime·walkfintab(markfin);
}
// free RefNone, free & queue finalizers for RefNone|RefHasFinalizer, reset RefSome
static void
sweepspan(MSpan *s)
{
int32 n, npages, size;
byte *p;
uint32 ref, *gcrefp, *gcrefep;
MCache *c;
Finalizer *f;
p = (byte*)(s->start << PageShift);
if(s->sizeclass == 0) {
// Large block.
ref = s->gcref0;
switch(ref & ~(RefFlags^RefHasFinalizer)) {
case RefNone:
// Free large object.
mstats.alloc -= s->npages<<PageShift;
runtime·memclr(p, s->npages<<PageShift);
if(ref & RefProfiled)
runtime·MProf_Free(p, s->npages<<PageShift);
s->gcref0 = RefFree;
runtime·MHeap_Free(&runtime·mheap, s, 1);
break;
case RefNone|RefHasFinalizer:
f = runtime·getfinalizer(p, 1);
if(f == nil)
runtime·throw("finalizer inconsistency");
f->arg = p;
f->next = finq;
finq = f;
ref &= ~RefHasFinalizer;
// fall through
case RefSome:
case RefSome|RefHasFinalizer:
s->gcref0 = RefNone | (ref&RefFlags);
break;
}
return;
}
// Chunk full of small blocks.
runtime·MGetSizeClassInfo(s->sizeclass, &size, &npages, &n);
gcrefp = s->gcref;
gcrefep = s->gcref + n;
for(; gcrefp < gcrefep; gcrefp++, p += size) {
ref = *gcrefp;
if(ref < RefNone) // RefFree or RefStack
continue;
switch(ref & ~(RefFlags^RefHasFinalizer)) {
case RefNone:
// Free small object.
if(ref & RefProfiled)
runtime·MProf_Free(p, size);
*gcrefp = RefFree;
c = m->mcache;
if(size > sizeof(uintptr))
((uintptr*)p)[1] = 1; // mark as "needs to be zeroed"
mstats.alloc -= size;
mstats.by_size[s->sizeclass].nfree++;
runtime·MCache_Free(c, p, s->sizeclass, size);
break;
case RefNone|RefHasFinalizer:
f = runtime·getfinalizer(p, 1);
if(f == nil)
runtime·throw("finalizer inconsistency");
f->arg = p;
f->next = finq;
finq = f;
ref &= ~RefHasFinalizer;
// fall through
case RefSome:
case RefSome|RefHasFinalizer:
*gcrefp = RefNone | (ref&RefFlags);
break;
}
}
}
static void
sweep(void)
{
MSpan *s;
for(s = runtime·mheap.allspans; s != nil; s = s->allnext)
if(s->state == MSpanInUse)
sweepspan(s);
}
// Semaphore, not Lock, so that the goroutine
// reschedules when there is contention rather
// than spinning.
static uint32 gcsema = 1;
// Initialized from $GOGC. GOGC=off means no gc.
//
// Next gc is after we've allocated an extra amount of
// memory proportional to the amount already in use.
// If gcpercent=100 and we're using 4M, we'll gc again
// when we get to 8M. This keeps the gc cost in linear
// proportion to the allocation cost. Adjusting gcpercent
// just changes the linear constant (and also the amount of
// extra memory used).
static int32 gcpercent = -2;
static void
stealcache(void)
{
M *m;
for(m=runtime·allm; m; m=m->alllink)
runtime·MCache_ReleaseAll(m->mcache);
}
static void
cachestats(void)
{
M *m;
MCache *c;
for(m=runtime·allm; m; m=m->alllink) {
c = m->mcache;
mstats.heap_alloc += c->local_alloc;
c->local_alloc = 0;
mstats.heap_objects += c->local_objects;
c->local_objects = 0;
}
}
void
runtime·gc(int32 force)
{
int64 t0, t1;
byte *p;
Finalizer *fp;
// The gc is turned off (via enablegc) until
// the bootstrap has completed.
// Also, malloc gets called in the guts
// of a number of libraries that might be
// holding locks. To avoid priority inversion
// problems, don't bother trying to run gc
// while holding a lock. The next mallocgc
// without a lock will do the gc instead.
if(!mstats.enablegc || m->locks > 0 || runtime·panicking)
return;
if(gcpercent == -2) { // first time through
p = runtime·getenv("GOGC");
if(p == nil || p[0] == '\0')
gcpercent = 100;
else if(runtime·strcmp(p, (byte*)"off") == 0)
gcpercent = -1;
else
gcpercent = runtime·atoi(p);
}
if(gcpercent < 0)
return;
runtime·semacquire(&gcsema);
t0 = runtime·nanotime();
m->gcing = 1;
runtime·stoptheworld();
if(runtime·mheap.Lock.key != 0)
runtime·throw("runtime·mheap locked during gc");
if(force || mstats.heap_alloc >= mstats.next_gc) {
cachestats();
mark();
sweep();
stealcache();
mstats.next_gc = mstats.heap_alloc+mstats.heap_alloc*gcpercent/100;
}
m->gcing = 0;
m->locks++; // disable gc during the mallocs in newproc
fp = finq;
if(fp != nil) {
// kick off or wake up goroutine to run queued finalizers
if(fing == nil)
fing = runtime·newproc1((byte*)runfinq, nil, 0, 0);
else if(fingwait) {
fingwait = 0;
runtime·ready(fing);
}
}
m->locks--;
t1 = runtime·nanotime();
mstats.numgc++;
mstats.pause_ns += t1 - t0;
if(mstats.debuggc)
runtime·printf("pause %D\n", t1-t0);
runtime·semrelease(&gcsema);
runtime·starttheworld();
// give the queued finalizers, if any, a chance to run
if(fp != nil)
runtime·gosched();
}
static void
runfinq(void)
{
Finalizer *f, *next;
byte *frame;
for(;;) {
// There's no need for a lock in this section
// because it only conflicts with the garbage
// collector, and the garbage collector only
// runs when everyone else is stopped, and
// runfinq only stops at the gosched() or
// during the calls in the for loop.
f = finq;
finq = nil;
if(f == nil) {
fingwait = 1;
g->status = Gwaiting;
runtime·gosched();
continue;
}
for(; f; f=next) {
next = f->next;
frame = runtime·mal(sizeof(uintptr) + f->nret);
*(void**)frame = f->arg;
reflect·call((byte*)f->fn, frame, sizeof(uintptr) + f->nret);
runtime·free(frame);
f->fn = nil;
f->arg = nil;
f->next = nil;
runtime·free(f);
}
runtime·gc(1); // trigger another gc to clean up the finalized objects, if possible
}
}