summaryrefslogtreecommitdiff
path: root/src/pkg/runtime/mgc0.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/runtime/mgc0.c')
-rw-r--r--src/pkg/runtime/mgc0.c234
1 files changed, 135 insertions, 99 deletions
diff --git a/src/pkg/runtime/mgc0.c b/src/pkg/runtime/mgc0.c
index 010f9cd96..aa499f476 100644
--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -140,6 +140,7 @@ static Workbuf* getempty(Workbuf*);
static Workbuf* getfull(Workbuf*);
static void putempty(Workbuf*);
static Workbuf* handoff(Workbuf*);
+static void gchelperstart(void);
static struct {
uint64 full; // lock-free list of full blocks
@@ -191,7 +192,7 @@ static struct {
// markonly marks an object. It returns true if the object
// has been marked by this function, false otherwise.
-// This function isn't thread-safe and doesn't append the object to any buffer.
+// This function doesn't append the object to any buffer.
static bool
markonly(void *obj)
{
@@ -254,13 +255,23 @@ found:
// Only care about allocated and not marked.
if((bits & (bitAllocated|bitMarked)) != bitAllocated)
return false;
- *bitp |= bitMarked<<shift;
+ if(work.nproc == 1)
+ *bitp |= bitMarked<<shift;
+ else {
+ for(;;) {
+ x = *bitp;
+ if(x & (bitMarked<<shift))
+ return false;
+ if(runtime·casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift))))
+ break;
+ }
+ }
// The object is now marked
return true;
}
-// PtrTarget and BitTarget are structures used by intermediate buffers.
+// PtrTarget is a structure used by intermediate buffers.
// The intermediate buffers hold GC data before it
// is moved/flushed to the work buffer (Workbuf).
// The size of an intermediate buffer is very small,
@@ -272,25 +283,17 @@ struct PtrTarget
uintptr ti;
};
-typedef struct BitTarget BitTarget;
-struct BitTarget
-{
- void *p;
- uintptr ti;
- uintptr *bitp, shift;
-};
-
typedef struct BufferList BufferList;
struct BufferList
{
PtrTarget ptrtarget[IntermediateBufferCapacity];
- BitTarget bittarget[IntermediateBufferCapacity];
Obj obj[IntermediateBufferCapacity];
- BufferList *next;
+ uint32 busy;
+ byte pad[CacheLineSize];
};
-static BufferList *bufferList;
+#pragma dataflag 16 // no pointers
+static BufferList bufferList[MaxGcproc];
-static Lock lock;
static Type *itabtype;
static void enqueue(Obj obj, Workbuf **_wbuf, Obj **_wp, uintptr *_nobj);
@@ -301,7 +304,6 @@ static void enqueue(Obj obj, Workbuf **_wbuf, Obj **_wp, uintptr *_nobj);
// and are prepared to be scanned by the garbage collector.
//
// _wp, _wbuf, _nobj are input/output parameters and are specifying the work buffer.
-// bitbuf holds temporary data generated by this function.
//
// A simplified drawing explaining how the todo-list moves from a structure to another:
//
@@ -309,14 +311,12 @@ static void enqueue(Obj obj, Workbuf **_wbuf, Obj **_wp, uintptr *_nobj);
// (find pointers)
// Obj ------> PtrTarget (pointer targets)
// ↑ |
-// | | flushptrbuf (1st part,
-// | | find block start)
-// | ↓
-// `--------- BitTarget (pointer targets and the corresponding locations in bitmap)
-// flushptrbuf
-// (2nd part, mark and enqueue)
+// | |
+// `----------'
+// flushptrbuf
+// (find block start, mark and enqueue)
static void
-flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf, uintptr *_nobj, BitTarget *bitbuf)
+flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf, uintptr *_nobj)
{
byte *p, *arena_start, *obj;
uintptr size, *bitp, bits, shift, j, x, xbits, off, nobj, ti, n;
@@ -325,7 +325,6 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
Obj *wp;
Workbuf *wbuf;
PtrTarget *ptrbuf_end;
- BitTarget *bitbufpos, *bt;
arena_start = runtime·mheap->arena_start;
@@ -359,8 +358,6 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
{
// Multi-threaded version.
- bitbufpos = bitbuf;
-
while(ptrbuf < ptrbuf_end) {
obj = ptrbuf->p;
ti = ptrbuf->ti;
@@ -438,26 +435,22 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
// Only care about allocated and not marked.
if((bits & (bitAllocated|bitMarked)) != bitAllocated)
continue;
-
- *bitbufpos++ = (BitTarget){obj, ti, bitp, shift};
- }
-
- runtime·lock(&lock);
- for(bt=bitbuf; bt<bitbufpos; bt++){
- xbits = *bt->bitp;
- bits = xbits >> bt->shift;
- if((bits & bitMarked) != 0)
- continue;
-
- // Mark the block
- *bt->bitp = xbits | (bitMarked << bt->shift);
+ if(work.nproc == 1)
+ *bitp |= bitMarked<<shift;
+ else {
+ for(;;) {
+ x = *bitp;
+ if(x & (bitMarked<<shift))
+ goto continue_obj;
+ if(runtime·casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift))))
+ break;
+ }
+ }
// If object has no pointers, don't need to scan further.
if((bits & bitNoPointers) != 0)
continue;
- obj = bt->p;
-
// Ask span about size class.
// (Manually inlined copy of MHeap_Lookup.)
x = (uintptr)obj >> PageShift;
@@ -467,11 +460,11 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
PREFETCH(obj);
- *wp = (Obj){obj, s->elemsize, bt->ti};
+ *wp = (Obj){obj, s->elemsize, ti};
wp++;
nobj++;
+ continue_obj:;
}
- runtime·unlock(&lock);
// If another proc wants a pointer, give it some.
if(work.nwait > 0 && nobj > handoffThreshold && work.full == 0) {
@@ -575,20 +568,19 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
byte *b, *arena_start, *arena_used;
uintptr n, i, end_b, elemsize, size, ti, objti, count, type;
uintptr *pc, precise_type, nominal_size;
- uintptr *map_ret, mapkey_size, mapval_size, mapkey_ti, mapval_ti;
+ uintptr *map_ret, mapkey_size, mapval_size, mapkey_ti, mapval_ti, *chan_ret;
void *obj;
Type *t;
Slice *sliceptr;
Frame *stack_ptr, stack_top, stack[GC_STACK_CAPACITY+4];
BufferList *scanbuffers;
PtrTarget *ptrbuf, *ptrbuf_end, *ptrbufpos;
- BitTarget *bitbuf;
Obj *objbuf, *objbuf_end, *objbufpos;
Eface *eface;
Iface *iface;
Hmap *hmap;
MapType *maptype;
- bool didmark, mapkey_kind, mapval_kind;
+ bool mapkey_kind, mapval_kind;
struct hash_gciter map_iter;
struct hash_gciter_data d;
Hchan *chan;
@@ -606,26 +598,13 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
precise_type = false;
nominal_size = 0;
- // Allocate ptrbuf, bitbuf
+ // Allocate ptrbuf
{
- runtime·lock(&lock);
-
- if(bufferList == nil) {
- bufferList = runtime·SysAlloc(sizeof(*bufferList));
- if(bufferList == nil)
- runtime·throw("runtime: cannot allocate memory");
- bufferList->next = nil;
- }
- scanbuffers = bufferList;
- bufferList = bufferList->next;
-
+ scanbuffers = &bufferList[m->helpgc];
ptrbuf = &scanbuffers->ptrtarget[0];
ptrbuf_end = &scanbuffers->ptrtarget[0] + nelem(scanbuffers->ptrtarget);
- bitbuf = &scanbuffers->bittarget[0];
objbuf = &scanbuffers->obj[0];
objbuf_end = &scanbuffers->obj[0] + nelem(scanbuffers->obj);
-
- runtime·unlock(&lock);
}
ptrbufpos = ptrbuf;
@@ -638,6 +617,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
mapkey_ti = mapval_ti = 0;
chan = nil;
chantype = nil;
+ chan_ret = nil;
goto next_block;
@@ -703,7 +683,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
mapval_kind = maptype->elem->kind;
mapval_ti = (uintptr)maptype->elem->gc | PRECISE;
- map_ret = 0;
+ map_ret = nil;
pc = mapProg;
} else {
goto next_block;
@@ -712,6 +692,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
case TypeInfo_Chan:
chan = (Hchan*)b;
chantype = (ChanType*)t;
+ chan_ret = nil;
pc = chanProg;
break;
default:
@@ -759,17 +740,29 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
case GC_STRING:
obj = *(void**)(stack_top.b + pc[1]);
+ markonly(obj);
pc += 2;
- break;
+ continue;
case GC_EFACE:
eface = (Eface*)(stack_top.b + pc[1]);
pc += 2;
- if(eface->type != nil && (eface->data >= arena_start && eface->data < arena_used)) {
- t = eface->type;
+ if(eface->type == nil)
+ continue;
+
+ // eface->type
+ t = eface->type;
+ if((void*)t >= arena_start && (void*)t < arena_used) {
+ *ptrbufpos++ = (PtrTarget){t, 0};
+ if(ptrbufpos == ptrbuf_end)
+ flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);
+ }
+
+ // eface->data
+ if(eface->data >= arena_start && eface->data < arena_used) {
if(t->size <= sizeof(void*)) {
if((t->kind & KindNoPointers))
- break;
+ continue;
obj = eface->data;
if((t->kind & ~KindNoPointers) == KindPtr)
@@ -785,13 +778,13 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
iface = (Iface*)(stack_top.b + pc[1]);
pc += 2;
if(iface->tab == nil)
- break;
+ continue;
// iface->tab
if((void*)iface->tab >= arena_start && (void*)iface->tab < arena_used) {
*ptrbufpos++ = (PtrTarget){iface->tab, (uintptr)itabtype->gc};
if(ptrbufpos == ptrbuf_end)
- flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj, bitbuf);
+ flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);
}
// iface->data
@@ -799,7 +792,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
t = iface->tab->type;
if(t->size <= sizeof(void*)) {
if((t->kind & KindNoPointers))
- break;
+ continue;
obj = iface->data;
if((t->kind & ~KindNoPointers) == KindPtr)
@@ -812,13 +805,13 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
break;
case GC_DEFAULT_PTR:
- while((i = stack_top.b) <= end_b) {
+ while(stack_top.b <= end_b) {
+ obj = *(byte**)stack_top.b;
stack_top.b += PtrSize;
- obj = *(byte**)i;
if(obj >= arena_start && obj < arena_used) {
*ptrbufpos++ = (PtrTarget){obj, 0};
if(ptrbufpos == ptrbuf_end)
- flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj, bitbuf);
+ flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);
}
}
goto next_block;
@@ -826,9 +819,8 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
case GC_END:
if(--stack_top.count != 0) {
// Next iteration of a loop if possible.
- elemsize = stack_top.elemsize;
- stack_top.b += elemsize;
- if(stack_top.b + elemsize <= end_b+PtrSize) {
+ stack_top.b += stack_top.elemsize;
+ if(stack_top.b + stack_top.elemsize <= end_b+PtrSize) {
pc = stack_top.loop_or_ret;
continue;
}
@@ -894,10 +886,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
pc += 3;
continue;
}
- runtime·lock(&lock);
- didmark = markonly(hmap);
- runtime·unlock(&lock);
- if(didmark) {
+ if(markonly(hmap)) {
maptype = (MapType*)pc[2];
if(hash_gciter_init(hmap, &map_iter)) {
mapkey_size = maptype->key->size;
@@ -923,31 +912,41 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
while(hash_gciter_next(&map_iter, &d)) {
// buffers: reserve space for 2 objects.
if(ptrbufpos+2 >= ptrbuf_end)
- flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj, bitbuf);
+ flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);
if(objbufpos+2 >= objbuf_end)
flushobjbuf(objbuf, &objbufpos, &wp, &wbuf, &nobj);
- if(d.st != nil) {
- runtime·lock(&lock);
+ if(d.st != nil)
markonly(d.st);
- runtime·unlock(&lock);
- }
+
if(d.key_data != nil) {
if(!(mapkey_kind & KindNoPointers) || d.indirectkey) {
if(!d.indirectkey)
*objbufpos++ = (Obj){d.key_data, mapkey_size, mapkey_ti};
- else
+ else {
+ if(Debug) {
+ obj = *(void**)d.key_data;
+ if(!(arena_start <= obj && obj < arena_used))
+ runtime·throw("scanblock: inconsistent hashmap");
+ }
*ptrbufpos++ = (PtrTarget){*(void**)d.key_data, mapkey_ti};
+ }
}
if(!(mapval_kind & KindNoPointers) || d.indirectval) {
if(!d.indirectval)
*objbufpos++ = (Obj){d.val_data, mapval_size, mapval_ti};
- else
+ else {
+ if(Debug) {
+ obj = *(void**)d.val_data;
+ if(!(arena_start <= obj && obj < arena_used))
+ runtime·throw("scanblock: inconsistent hashmap");
+ }
*ptrbufpos++ = (PtrTarget){*(void**)d.val_data, mapval_ti};
+ }
}
}
}
- if(map_ret == 0)
+ if(map_ret == nil)
goto next_block;
pc = map_ret;
continue;
@@ -961,7 +960,26 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
*objbufpos++ = (Obj){obj, size, objti};
if(objbufpos == objbuf_end)
flushobjbuf(objbuf, &objbufpos, &wp, &wbuf, &nobj);
- break;
+ continue;
+
+ case GC_CHAN_PTR:
+ // Similar to GC_MAP_PTR
+ chan = *(Hchan**)(stack_top.b + pc[1]);
+ if(chan == nil) {
+ pc += 3;
+ continue;
+ }
+ if(markonly(chan)) {
+ chantype = (ChanType*)pc[2];
+ if(!(chantype->elem->kind & KindNoPointers)) {
+ // Start chanProg.
+ chan_ret = pc+3;
+ pc = chanProg+1;
+ continue;
+ }
+ }
+ pc += 3;
+ continue;
case GC_CHAN:
// There are no heap pointers in struct Hchan,
@@ -981,7 +999,10 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
flushobjbuf(objbuf, &objbufpos, &wp, &wbuf, &nobj);
}
}
- goto next_block;
+ if(chan_ret == nil)
+ goto next_block;
+ pc = chan_ret;
+ continue;
default:
runtime·throw("scanblock: invalid GC instruction");
@@ -991,7 +1012,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
if(obj >= arena_start && obj < arena_used) {
*ptrbufpos++ = (PtrTarget){obj, objti};
if(ptrbufpos == ptrbuf_end)
- flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj, bitbuf);
+ flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);
}
}
@@ -1000,7 +1021,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
// the loop by setting b, n, ti to the parameters for the next block.
if(nobj == 0) {
- flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj, bitbuf);
+ flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);
flushobjbuf(objbuf, &objbufpos, &wp, &wbuf, &nobj);
if(nobj == 0) {
@@ -1026,11 +1047,7 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
nobj--;
}
-endscan:
- runtime·lock(&lock);
- scanbuffers->next = bufferList;
- bufferList = scanbuffers;
- runtime·unlock(&lock);
+endscan:;
}
// debug_scanblock is the debug copy of scanblock.
@@ -1339,7 +1356,7 @@ addstackroots(G *gp)
runtime·printf("scanstack inconsistent: g%D#%d sp=%p not in [%p,%p]\n", gp->goid, n, sp, guard-StackGuard, stk);
runtime·throw("scanstack");
}
- addroot((Obj){sp, (byte*)stk - sp, 0});
+ addroot((Obj){sp, (byte*)stk - sp, (uintptr)defaultProg | PRECISE | LOOP});
sp = (byte*)stk->gobuf.sp;
guard = stk->stackguard;
stk = (Stktop*)stk->stackbase;
@@ -1381,14 +1398,17 @@ addroots(void)
for(spanidx=0; spanidx<runtime·mheap->nspan; spanidx++) {
s = allspans[spanidx];
if(s->state == MSpanInUse) {
+ // The garbage collector ignores type pointers stored in MSpan.types:
+ // - Compiler-generated types are stored outside of heap.
+ // - The reflect package has runtime-generated types cached in its data structures.
+ // The garbage collector relies on finding the references via that cache.
switch(s->types.compression) {
case MTypes_Empty:
case MTypes_Single:
break;
case MTypes_Words:
case MTypes_Bytes:
- // TODO(atom): consider using defaultProg instead of 0
- addroot((Obj){(byte*)&s->types.data, sizeof(void*), 0});
+ markonly((byte*)s->types.data);
break;
}
}
@@ -1655,6 +1675,8 @@ runtime·memorydump(void)
void
runtime·gchelper(void)
{
+ gchelperstart();
+
// parallel mark for over gc roots
runtime·parfordo(work.markfor);
@@ -1668,6 +1690,7 @@ runtime·gchelper(void)
}
runtime·parfordo(work.sweepfor);
+ bufferList[m->helpgc].busy = 0;
if(runtime·xadd(&work.ndone, +1) == work.nproc-1)
runtime·notewakeup(&work.alldone);
}
@@ -1757,6 +1780,8 @@ runtime·gc(int32 force)
// a problem in the past.
if((((uintptr)&work.empty) & 7) != 0)
runtime·throw("runtime: gc work buffer is misaligned");
+ if((((uintptr)&work.full) & 7) != 0)
+ runtime·throw("runtime: gc work buffer is misaligned");
// The gc is turned off (via enablegc) until
// the bootstrap has completed.
@@ -1857,6 +1882,7 @@ gc(struct gc_args *args)
t1 = runtime·nanotime();
+ gchelperstart();
runtime·parfordo(work.markfor);
scanblock(nil, nil, 0, true);
@@ -1868,6 +1894,7 @@ gc(struct gc_args *args)
t2 = runtime·nanotime();
runtime·parfordo(work.sweepfor);
+ bufferList[m->helpgc].busy = 0;
t3 = runtime·nanotime();
if(work.nproc > 1)
@@ -2009,6 +2036,15 @@ runtime∕debug·setGCPercent(intgo in, intgo out)
}
static void
+gchelperstart(void)
+{
+ if(m->helpgc < 0 || m->helpgc >= MaxGcproc)
+ runtime·throw("gchelperstart: bad m->helpgc");
+ if(runtime·xchg(&bufferList[m->helpgc].busy, 1))
+ runtime·throw("gchelperstart: already busy");
+}
+
+static void
runfinq(void)
{
Finalizer *f;
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-29 17:03:36 +0000