wingo pushed a commit to branch wip-whippet
in repository guile.
commit d2828975a5f9505beba3c11822fc56dc1ff72ce4
Author: Andy Wingo <wi...@igalia.com>
AuthorDate: Thu Mar 10 10:48:42 2022 +0100
Switch mark-sweep collector to mark stack
Slows down performance though! Have to think here.
---
Makefile | 2 +-
assert.h | 15 +++++++
debug.h | 10 +++++
mark-sweep.h | 45 +++++++++----------
serial-marker.h | 136 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 183 insertions(+), 25 deletions(-)
diff --git a/Makefile b/Makefile
index 0067cec1a..6e20a089e 100644
--- a/Makefile
+++ b/Makefile
@@ -14,7 +14,7 @@ bdw-%: bdw.h conservative-roots.h %.c
semi-%: semi.h precise-roots.h %.c
$(CC) $(CFLAGS) -I. -DGC_SEMI -o $@ $*.c
-mark-sweep-%: mark-sweep.h precise-roots.h %.c
+mark-sweep-%: mark-sweep.h precise-roots.h serial-marker.h assert.h debug.h %.c
$(CC) $(CFLAGS) -I. -DGC_MARK_SWEEP -o $@ $*.c
check: $(addprefix test-$(TARGET),$(TARGETS))
diff --git a/assert.h b/assert.h
new file mode 100644
index 000000000..3133f105c
--- /dev/null
+++ b/assert.h
@@ -0,0 +1,15 @@
+#ifndef ASSERT_H
+#define ASSERT_H
+
+#define STATIC_ASSERT_EQ(a, b) _Static_assert((a) == (b), "eq")
+
+#define UNLIKELY(e) __builtin_expect(e, 0)
+
+#ifndef NDEBUG
+#define ASSERT(x) do { if (UNLIKELY(!(x))) __builtin_trap(); } while (0)
+#else
+#define ASSERT(x) do { } while (0)
+#endif
+#define ASSERT_EQ(a,b) ASSERT((a) == (b))
+
+#endif // ASSERT_H
diff --git a/debug.h b/debug.h
new file mode 100644
index 000000000..7b161c556
--- /dev/null
+++ b/debug.h
@@ -0,0 +1,10 @@
+#ifndef DEBUG_H
+#define DEBUG_H
+
+#ifndef NDEBUG
+#define DEBUG(...) fprintf (stderr, "DEBUG: " __VA_ARGS__)
+#else
+#define DEBUG(...) do { } while (0)
+#endif
+
+#endif // DEBUG_H
diff --git a/mark-sweep.h b/mark-sweep.h
index 8c15da53b..747c46c72 100644
--- a/mark-sweep.h
+++ b/mark-sweep.h
@@ -4,16 +4,9 @@
#include <sys/mman.h>
#include <unistd.h>
+#include "assert.h"
#include "precise-roots.h"
-
-#define STATIC_ASSERT_EQ(a, b) _Static_assert((a) == (b), "eq")
-
-#ifndef NDEBUG
-#define ASSERT(x) do { if (!(x)) __builtin_trap(); } while (0)
-#else
-#define ASSERT(x) do { } while (0)
-#endif
-#define ASSERT_EQ(a,b) ASSERT((a) == (b))
+#include "serial-marker.h"
#define GRANULE_SIZE 8
#define GRANULE_SIZE_LOG_2 3
@@ -163,8 +156,13 @@ struct context {
uintptr_t sweep;
struct handle *roots;
long count;
+ struct marker marker;
};
+static inline struct marker* context_marker(struct context *cx) {
+ return &cx->marker;
+}
+
static inline struct gcobj_free**
get_small_object_freelist(struct context *cx, enum small_object_size kind) {
ASSERT(kind < SMALL_OBJECT_SIZES);
@@ -187,27 +185,21 @@ static inline void clear_memory(uintptr_t addr, size_t
size) {
}
static void collect(struct context *cx) __attribute__((noinline));
-static void mark(struct context *cx, void *p);
-
-static inline void visit(struct context *cx, void **loc) {
- mark(cx, *loc);
-}
-static void mark(struct context *cx, void *p) {
- // A production mark implementation would use a worklist, to avoid
- // stack overflow. This implementation just uses the call stack.
- struct gcobj *obj = p;
- if (obj == NULL)
- return;
+static inline int mark_object(struct gcobj *obj) {
if (tag_marked(obj->tag))
- return;
+ return 0;
tag_set_marked(&obj->tag);
+ return 1;
+}
+
+static void process(struct context *cx, struct gcobj *obj) {
switch (tag_live_alloc_kind(obj->tag)) {
case NODE:
- visit_node_fields(cx, obj, visit);
+ visit_node_fields(cx, obj, marker_visit);
break;
case DOUBLE_ARRAY:
- visit_double_array_fields(cx, obj, visit);
+ visit_double_array_fields(cx, obj, marker_visit);
break;
default:
abort ();
@@ -223,8 +215,11 @@ static void clear_freelists(struct context *cx) {
static void collect(struct context *cx) {
// fprintf(stderr, "start collect #%ld:\n", cx->count);
+ marker_prepare(cx);
for (struct handle *h = cx->roots; h; h = h->next)
- mark(cx, h->v);
+ marker_visit_root(cx, &h->v);
+ marker_trace(cx, process);
+ marker_release(cx);
// fprintf(stderr, "done marking\n");
cx->sweep = cx->base;
clear_freelists(cx);
@@ -513,6 +508,8 @@ static inline void initialize_gc(struct context *cx, size_t
size) {
cx->sweep = cx->base + cx->size;
cx->roots = NULL;
cx->count = 0;
+ if (!marker_init(cx))
+ abort();
reclaim(cx, mem, size_to_granules(size));
}
diff --git a/serial-marker.h b/serial-marker.h
new file mode 100644
index 000000000..432080a02
--- /dev/null
+++ b/serial-marker.h
@@ -0,0 +1,136 @@
+#ifndef SERIAL_TRACE_H
+#define SERIAL_TRACE_H
+
+#include <sys/mman.h>
+#include <unistd.h>
+
+#include "assert.h"
+#include "debug.h"
+
+struct mark_stack {
+ size_t size;
+ size_t next;
+ uintptr_t *buf;
+};
+
+static const size_t mark_stack_max_size =
+ (1ULL << (sizeof(uintptr_t) * 8 - 1)) / sizeof(uintptr_t);
+static const size_t mark_stack_release_byte_threshold = 1 * 1024 * 1024;
+
+static void*
+mark_stack_alloc(size_t size) {
+ void *mem = mmap(NULL, size, PROT_READ|PROT_WRITE,
+ MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
+ if (mem == MAP_FAILED) {
+ perror("Failed to grow mark stack");
+ DEBUG("Failed to allocate %zu bytes", size);
+ return NULL;
+ }
+ return mem;
+}
+
+static int
+mark_stack_init(struct mark_stack *stack) {
+ stack->size = getpagesize();
+ stack->next = 0;
+ stack->buf = mark_stack_alloc(stack->size);
+ return !!stack->buf;
+}
+
+static int
+mark_stack_grow(struct mark_stack *stack) {
+ uintptr_t size = stack->size;
+ if (size >= mark_stack_max_size) {
+ DEBUG("mark stack already at max size of %zu bytes", size);
+ return 0;
+ }
+ size *= 2;
+ uintptr_t *buf = mark_stack_alloc(size);
+ if (!buf)
+ return 0;
+ memcpy(buf, stack->buf, stack->next * sizeof(uintptr_t));
+ munmap(stack->buf, stack->size * sizeof(uintptr_t));
+ stack->size = size;
+ stack->buf = buf;
+ return 1;
+}
+
+static inline void
+mark_stack_push(struct mark_stack *stack, void *p) {
+ size_t next = stack->next;
+ if (UNLIKELY(next == stack->size)) {
+ if (!mark_stack_grow(stack))
+ abort();
+ }
+ stack->buf[next] = (uintptr_t)p;
+ stack->next = next + 1;
+}
+
+static inline void*
+mark_stack_pop(struct mark_stack *stack) {
+ size_t next = stack->next;
+ if (UNLIKELY(next == 0))
+ return NULL;
+ uintptr_t ret = stack->buf[next - 1];
+ stack->next = next - 1;
+ return (void*)ret;
+}
+
+static void
+mark_stack_release(struct mark_stack *stack) {
+ size_t byte_size = stack->size * sizeof(uintptr_t);
+ if (byte_size >= mark_stack_release_byte_threshold)
+ madvise(stack->buf, byte_size, MADV_DONTNEED);
+}
+
+static void
+mark_stack_destroy(struct mark_stack *stack) {
+ size_t byte_size = stack->size * sizeof(uintptr_t);
+ munmap(stack->buf, byte_size);
+}
+
+struct marker {
+ struct mark_stack stack;
+};
+
+struct context;
+static inline struct marker* context_marker(struct context *cx);
+
+static int
+marker_init(struct context *cx) {
+ return mark_stack_init(&context_marker(cx)->stack);
+}
+static void marker_prepare(struct context *cx) {}
+static void marker_release(struct context *cx) {
+ mark_stack_release(&context_marker(cx)->stack);
+}
+
+struct gcobj;
+static inline void marker_visit(struct context *cx, void **loc)
__attribute__((always_inline));
+static inline void marker_trace(struct context *cx,
+ void (*)(struct context *, struct gcobj *))
+ __attribute__((always_inline));
+static inline int mark_object(struct gcobj *obj)
__attribute__((always_inline));
+
+static inline void
+marker_visit(struct context *cx, void **loc) {
+ struct gcobj *obj = *loc;
+ if (obj) {
+ __builtin_prefetch(obj);
+ mark_stack_push(&context_marker(cx)->stack, obj);
+ }
+}
+static inline void
+marker_visit_root(struct context *cx, void **loc) {
+ marker_visit(cx, loc);
+}
+static inline void
+marker_trace(struct context *cx,
+ void (*process)(struct context *, struct gcobj *)) {
+ struct gcobj *obj;
+ while ((obj = mark_stack_pop(&context_marker(cx)->stack)))
+ if (mark_object(obj))
+ process(cx, obj);
+}
+
+#endif // SERIAL_MARK_H
