wingo pushed a commit to branch wip-whippet
in repository guile.
commit d2bde8319f60f7a4b04c1b00c509c6096581db02
Author: Andy Wingo <wi...@igalia.com>
AuthorDate: Fri Sep 16 13:40:55 2022 +0200
Add conservative stack capture
This isn't really wired up yet anywhere, but add a precursor to
conservative stack scanning.
---
Makefile | 7 +++--
bdw.c | 9 ++++--
gc-align.h | 17 ++++++++++++
gc-api.h | 22 +++++++++++----
gc-stack.c | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
gc-stack.h | 29 ++++++++++++++++++++
mt-gcbench.c | 58 ++++++++++++++++-----------------------
quads.c | 3 +-
semi.c | 8 ++++--
whippet.c | 15 ++++------
10 files changed, 200 insertions(+), 58 deletions(-)
diff --git a/Makefile b/Makefile
index f8e2c9ba9..1770f1a3c 100644
--- a/Makefile
+++ b/Makefile
@@ -15,11 +15,14 @@ all: $(ALL_TESTS)
gc-platform.o: gc-platform.h gc-platform-$(PLATFORM).c gc-visibility.h
$(COMPILE) -o $@ -c gc-platform-$(PLATFORM).c
+gc-stack.o: gc-stack.c
+ $(COMPILE) -o $@ -c $<
+
bdw-%-gc.o: semi.c %-embedder.h %.c
$(COMPILE) `pkg-config --cflags bdw-gc` -include $*-embedder.h -o $@ -c
bdw.c
bdw-%.o: semi.c %.c
$(COMPILE) -include bdw-attrs.h -o $@ -c $*.c
-bdw-%: bdw-%.o bdw-%-gc.o
+bdw-%: bdw-%.o bdw-%-gc.o gc-stack.o gc-platform.o
$(CC) $(LDFLAGS) `pkg-config --libs bdw-gc` -o $@ $^
semi-%-gc.o: semi.c %-embedder.h large-object-space.h assert.h debug.h %.c
@@ -47,7 +50,7 @@ parallel-generational-whippet-%-gc.o: whippet.c %-embedder.h
large-object-space.
parallel-generational-whippet-%.o: whippet.c %.c
$(COMPILE) -DGC_PARALLEL=1 -DGC_GENERATIONAL=1 -DGC_PRECISE=1 -include
whippet-attrs.h -o $@ -c $*.c
-%: %.o %-gc.o gc-platform.o
+%: %.o %-gc.o gc-platform.o gc-stack.o
$(CC) $(LDFLAGS) $($*_LDFLAGS) -o $@ $^
check: $(addprefix test-$(TARGET),$(TARGETS))
diff --git a/bdw.c b/bdw.c
index 9325726f5..caf161e0b 100644
--- a/bdw.c
+++ b/bdw.c
@@ -188,7 +188,8 @@ static int parse_options(int argc, struct gc_option argv[],
}
int gc_init(int argc, struct gc_option argv[],
- struct gc_heap **heap, struct gc_mutator **mutator) {
+ struct gc_stack_addr *stack_base, struct gc_heap **heap,
+ struct gc_mutator **mutator) {
GC_ASSERT_EQ(gc_allocator_small_granule_size(), GC_INLINE_GRANULE_BYTES);
GC_ASSERT_EQ(gc_allocator_large_threshold(),
GC_INLINE_FREELIST_COUNT * GC_INLINE_GRANULE_BYTES);
@@ -201,6 +202,8 @@ int gc_init(int argc, struct gc_option argv[],
// GC_free_space_divisor = 16;
// GC_enable_incremental();
+ // Ignore stack base for main thread.
+
GC_set_max_heap_size(options.fixed_heap_size);
// Not part of 7.3, sigh. Have to set an env var.
// GC_set_markers_count(options.parallelism);
@@ -218,8 +221,8 @@ int gc_init(int argc, struct gc_option argv[],
return 1;
}
-struct gc_mutator* gc_init_for_thread(uintptr_t *stack_base,
- struct gc_heap *heap) {
+struct gc_mutator* gc_init_for_thread(struct gc_stack_addr *stack_base,
+ struct gc_heap *heap) {
pthread_mutex_lock(&heap->lock);
if (!heap->multithreaded) {
GC_allow_register_threads();
diff --git a/gc-align.h b/gc-align.h
new file mode 100644
index 000000000..117d1cb47
--- /dev/null
+++ b/gc-align.h
@@ -0,0 +1,17 @@
+#ifndef GC_ALIGN_H
+#define GC_ALIGN_H
+
+#ifndef GC_IMPL
+#error internal header file, not part of API
+#endif
+
+#include <stdint.h>
+
+static inline uintptr_t align_down(uintptr_t addr, size_t align) {
+ return addr & ~(align - 1);
+}
+static inline uintptr_t align_up(uintptr_t addr, size_t align) {
+ return align_down(addr + align - 1, align);
+}
+
+#endif // GC_ALIGN_H
diff --git a/gc-api.h b/gc-api.h
index 2c4a636a1..a33fd7b12 100644
--- a/gc-api.h
+++ b/gc-api.h
@@ -7,6 +7,7 @@
#include "gc-inline.h"
#include "gc-ref.h"
#include "gc-edge.h"
+#include "gc-visibility.h"
#include <stdatomic.h>
#include <stdint.h>
@@ -27,21 +28,30 @@ struct gc_option {
// FIXME: Conflict with bdw-gc GC_API. Switch prefix?
#ifndef GC_API_
-#define GC_API_ __attribute__((visibility("hidden")))
+#define GC_API_ GC_INTERNAL
#endif
GC_API_ int gc_option_from_string(const char *str);
+
+struct gc_stack_addr;
+GC_API_ void* gc_call_with_stack_addr(void* (*f)(struct gc_stack_addr *,
+ void *),
+ void *data) GC_NEVER_INLINE;
+
GC_API_ int gc_init(int argc, struct gc_option argv[],
- struct gc_heap **heap, struct gc_mutator **mutator);
+ struct gc_stack_addr *base, struct gc_heap **heap,
+ struct gc_mutator **mutator);
struct gc_mutator_roots;
-struct gc_heap_roots;
GC_API_ void gc_mutator_set_roots(struct gc_mutator *mut,
struct gc_mutator_roots *roots);
-GC_API_ void gc_heap_set_roots(struct gc_heap *heap, struct gc_heap_roots
*roots);
-GC_API_ struct gc_mutator* gc_init_for_thread(uintptr_t *stack_base,
- struct gc_heap *heap);
+struct gc_heap_roots;
+GC_API_ void gc_heap_set_roots(struct gc_heap *heap,
+ struct gc_heap_roots *roots);
+
+GC_API_ struct gc_mutator* gc_init_for_thread(struct gc_stack_addr *base,
+ struct gc_heap *heap);
GC_API_ void gc_finish_for_thread(struct gc_mutator *mut);
GC_API_ void* gc_call_without_gc(struct gc_mutator *mut, void* (*f)(void*),
void *data) GC_NEVER_INLINE;
diff --git a/gc-stack.c b/gc-stack.c
new file mode 100644
index 000000000..bc8c9e64f
--- /dev/null
+++ b/gc-stack.c
@@ -0,0 +1,90 @@
+// For pthread_getattr_np.
+#define _GNU_SOURCE
+#include <pthread.h>
+#include <setjmp.h>
+#include <stdio.h>
+#include <unistd.h>
+
+#define GC_IMPL 1
+
+#include "debug.h"
+#include "gc-align.h"
+#include "gc-assert.h"
+#include "gc-inline.h"
+#include "gc-platform.h"
+#include "gc-stack.h"
+
+static uintptr_t current_thread_hot_stack_addr(void) {
+#ifdef __GCC__
+ return (uintptr_t)__builtin_frame_address(0);
+#else
+ uintptr_t local;
+ return (uintptr_t)&local;
+#endif
+}
+
+// FIXME: check platform stack growth direction.
+#define HOTTER_THAN <=
+
+static void capture_current_thread_hot_stack_addr(struct gc_stack_addr *addr) {
+ addr->addr = current_thread_hot_stack_addr();
+}
+
+static void capture_current_thread_cold_stack_addr(struct gc_stack_addr *addr)
{
+ addr->addr = gc_platform_current_thread_stack_base();
+}
+
+void gc_stack_init(struct gc_stack *stack, struct gc_stack_addr *base) {
+ if (base)
+ stack->cold = *base;
+ else
+ capture_current_thread_cold_stack_addr(&stack->cold);
+ stack->hot = stack->cold;
+}
+
+void gc_stack_capture_hot(struct gc_stack *stack) {
+ capture_current_thread_hot_stack_addr(&stack->hot);
+ setjmp(stack->registers);
+ GC_ASSERT(stack->hot.addr HOTTER_THAN stack->cold.addr);
+}
+
+static void* call_with_stack(void* (*)(struct gc_stack_addr*, void*),
+ struct gc_stack_addr*, void*) GC_NEVER_INLINE;
+static void* call_with_stack(void* (*f)(struct gc_stack_addr *, void *),
+ struct gc_stack_addr *addr, void *arg) {
+ return f(addr, arg);
+}
+void* gc_call_with_stack_addr(void* (*f)(struct gc_stack_addr *base,
+ void *arg),
+ void *arg) {
+ struct gc_stack_addr base;
+ capture_current_thread_hot_stack_addr(&base);
+ return call_with_stack(f, &base, arg);
+}
+
+void gc_stack_visit(struct gc_stack *stack,
+ void (*visit)(uintptr_t low, uintptr_t high, void *data),
+ void *data) {
+ {
+ uintptr_t low = (uintptr_t)stack->registers;
+ GC_ASSERT(low == align_down(low, sizeof(uintptr_t)));
+ uintptr_t high = low + sizeof(jmp_buf);
+ DEBUG("found mutator register roots for %p: [%p,%p)\n", stack,
+ (void*)low, (void*)high);
+ visit(low, high, data);
+ }
+
+ if (0 HOTTER_THAN 1) {
+ DEBUG("found mutator stack roots for %p: [%p,%p)\n", stack,
+ (void*)stack->hot.addr, (void*)stack->cold.addr);
+ visit(align_up(stack->hot.addr, sizeof(uintptr_t)),
+ align_down(stack->cold.addr, sizeof(uintptr_t)),
+ data);
+ } else {
+ DEBUG("found mutator stack roots for %p: [%p,%p)\n", stack,
+ (void*)stack->cold.addr, (void*)stack->hot.addr);
+ visit(align_up(stack->cold.addr, sizeof(uintptr_t)),
+ align_down(stack->hot.addr, sizeof(uintptr_t)),
+ data);
+ }
+}
diff --git a/gc-stack.h b/gc-stack.h
new file mode 100644
index 000000000..fa228b210
--- /dev/null
+++ b/gc-stack.h
@@ -0,0 +1,29 @@
+#ifndef GC_STACK_H
+#define GC_STACK_H
+
+#ifndef GC_IMPL
+#error internal header file, not part of API
+#endif
+
+#include "gc-inline.h"
+#include <setjmp.h>
+
+struct gc_stack_addr {
+ uintptr_t addr;
+};
+
+struct gc_stack {
+ struct gc_stack_addr cold;
+ struct gc_stack_addr hot;
+ jmp_buf registers;
+};
+
+GC_INTERNAL void gc_stack_init(struct gc_stack *stack,
+ struct gc_stack_addr *base);
+GC_INTERNAL void gc_stack_capture_hot(struct gc_stack *stack);
+GC_INTERNAL void gc_stack_visit(struct gc_stack *stack,
+ void (*visit)(uintptr_t low, uintptr_t high,
+ void *data),
+ void *data);
+
+#endif // GC_STACK_H
diff --git a/mt-gcbench.c b/mt-gcbench.c
index 9c6e6b5d4..4789a4f7d 100644
--- a/mt-gcbench.c
+++ b/mt-gcbench.c
@@ -257,61 +257,49 @@ static void time_construction(struct thread *t, int
depth) {
POP_HANDLE(t);
}
-static void* call_with_stack_base(void* (*)(uintptr_t*, void*), void*)
GC_NEVER_INLINE;
-static void* call_with_stack_base_inner(void* (*)(uintptr_t*, void*),
uintptr_t*, void*) GC_NEVER_INLINE;
-static void* call_with_stack_base_inner(void* (*f)(uintptr_t *stack_base, void
*arg),
- uintptr_t *stack_base, void *arg) {
- return f(stack_base, arg);
-}
-static void* call_with_stack_base(void* (*f)(uintptr_t *stack_base, void *arg),
- void *arg) {
- uintptr_t x;
- return call_with_stack_base_inner(f, &x, arg);
-}
-
struct call_with_gc_data {
- void* (*f)(struct gc_mutator *);
+ void* (*f)(struct thread *);
struct gc_heap *heap;
};
-static void* call_with_gc_inner(uintptr_t *stack_base, void *arg) {
+static void* call_with_gc_inner(struct gc_stack_addr *addr, void *arg) {
struct call_with_gc_data *data = arg;
- struct gc_mutator *mut = gc_init_for_thread(stack_base, data->heap);
- void *ret = data->f(mut);
+ struct gc_mutator *mut = gc_init_for_thread(addr, data->heap);
+ struct thread t = { mut, };
+ gc_mutator_set_roots(mut, &t.roots);
+ void *ret = data->f(&t);
gc_finish_for_thread(mut);
return ret;
}
-static void* call_with_gc(void* (*f)(struct gc_mutator *),
+static void* call_with_gc(void* (*f)(struct thread *),
struct gc_heap *heap) {
struct call_with_gc_data data = { f, heap };
- return call_with_stack_base(call_with_gc_inner, &data);
+ return gc_call_with_stack_addr(call_with_gc_inner, &data);
}
-static void* run_one_test(struct gc_mutator *mut) {
+static void* run_one_test(struct thread *t) {
NodeHandle long_lived_tree = { NULL };
NodeHandle temp_tree = { NULL };
DoubleArrayHandle array = { NULL };
- struct thread t = { mut, };
- gc_mutator_set_roots(mut, &t.roots);
- PUSH_HANDLE(&t, long_lived_tree);
- PUSH_HANDLE(&t, temp_tree);
- PUSH_HANDLE(&t, array);
+ PUSH_HANDLE(t, long_lived_tree);
+ PUSH_HANDLE(t, temp_tree);
+ PUSH_HANDLE(t, array);
// Create a long lived object
printf(" Creating a long-lived binary tree of depth %d\n",
long_lived_tree_depth);
- HANDLE_SET(long_lived_tree, allocate_node(mut));
- populate(&t, long_lived_tree_depth, HANDLE_REF(long_lived_tree));
+ HANDLE_SET(long_lived_tree, allocate_node(t->mut));
+ populate(t, long_lived_tree_depth, HANDLE_REF(long_lived_tree));
// Create long-lived array, filling half of it
printf(" Creating a long-lived array of %d doubles\n", array_size);
- HANDLE_SET(array, allocate_double_array(mut, array_size));
+ HANDLE_SET(array, allocate_double_array(t->mut, array_size));
for (int i = 0; i < array_size/2; ++i) {
HANDLE_REF(array)->values[i] = 1.0/i;
}
for (int d = min_tree_depth; d <= max_tree_depth; d += 2) {
- time_construction(&t, d);
+ time_construction(t, d);
}
validate_tree(HANDLE_REF(long_lived_tree), long_lived_tree_depth);
@@ -322,10 +310,9 @@ static void* run_one_test(struct gc_mutator *mut) {
|| HANDLE_REF(array)->values[1000] != 1.0/1000)
fprintf(stderr, "Failed\n");
- POP_HANDLE(&t);
- POP_HANDLE(&t);
- POP_HANDLE(&t);
- gc_mutator_set_roots(mut, NULL);
+ POP_HANDLE(t);
+ POP_HANDLE(t);
+ POP_HANDLE(t);
return NULL;
}
@@ -377,11 +364,14 @@ int main(int argc, char *argv[]) {
{ GC_OPTION_PARALLELISM, parallelism } };
struct gc_heap *heap;
struct gc_mutator *mut;
- if (!gc_init(sizeof options / sizeof options[0], options, &heap, &mut)) {
+ if (!gc_init(sizeof options / sizeof options[0], options, NULL, &heap,
+ &mut)) {
fprintf(stderr, "Failed to initialize GC with heap size %zu bytes\n",
heap_size);
return 1;
}
+ struct thread main_thread = { mut, };
+ gc_mutator_set_roots(mut, &main_thread.roots);
printf("Garbage Collector Test\n");
printf(" Live storage will peak at %zd bytes.\n\n", heap_max_live);
@@ -398,7 +388,7 @@ int main(int argc, char *argv[]) {
return 1;
}
}
- run_one_test(mut);
+ run_one_test(&main_thread);
for (size_t i = 1; i < nthreads; i++) {
struct join_data data = { 0, threads[i] };
gc_call_without_gc(mut, join_thread, &data);
diff --git a/quads.c b/quads.c
index 6136988b8..1318adf9f 100644
--- a/quads.c
+++ b/quads.c
@@ -136,7 +136,8 @@ int main(int argc, char *argv[]) {
{ GC_OPTION_PARALLELISM, parallelism } };
struct gc_heap *heap;
struct gc_mutator *mut;
- if (!gc_init(sizeof options / sizeof options[0], options, &heap, &mut)) {
+ if (!gc_init(sizeof options / sizeof options[0], options, NULL, &heap,
+ &mut)) {
fprintf(stderr, "Failed to initialize GC with heap size %zu bytes\n",
heap_size);
return 1;
diff --git a/semi.c b/semi.c
index e29e63c26..e771f7f3d 100644
--- a/semi.c
+++ b/semi.c
@@ -311,7 +311,8 @@ static int parse_options(int argc, struct gc_option argv[],
}
int gc_init(int argc, struct gc_option argv[],
- struct gc_heap **heap, struct gc_mutator **mut) {
+ struct gc_stack_addr *stack_base, struct gc_heap **heap,
+ struct gc_mutator **mut) {
GC_ASSERT_EQ(gc_allocator_allocation_pointer_offset(),
offsetof(struct semi_space, hp));
GC_ASSERT_EQ(gc_allocator_allocation_limit_offset(),
@@ -331,6 +332,7 @@ int gc_init(int argc, struct gc_option argv[],
if (!large_object_space_init(heap_large_object_space(*heap), *heap))
return 0;
+ // Ignore stack base, as we are precise.
(*mut)->roots = NULL;
return 1;
@@ -344,8 +346,8 @@ void gc_heap_set_roots(struct gc_heap *heap, struct
gc_heap_roots *roots) {
GC_CRASH();
}
-struct gc_mutator* gc_init_for_thread(uintptr_t *stack_base,
- struct gc_heap *heap) {
+struct gc_mutator* gc_init_for_thread(struct gc_stack_addr *base,
+ struct gc_heap *heap) {
fprintf(stderr,
"Semispace copying collector not appropriate for multithreaded
use.\n");
GC_CRASH();
diff --git a/whippet.c b/whippet.c
index 3e8e52185..dccb2a470 100644
--- a/whippet.c
+++ b/whippet.c
@@ -10,7 +10,10 @@
#define GC_API_
#include "gc-api.h"
+#define GC_IMPL 1
+
#include "debug.h"
+#include "gc-align.h"
#include "gc-inline.h"
#include "large-object-space.h"
#if GC_PARALLEL
@@ -178,13 +181,6 @@ struct slab {
};
STATIC_ASSERT_EQ(sizeof(struct slab), SLAB_SIZE);
-static inline uintptr_t align_down(uintptr_t addr, size_t align) {
- return addr & ~(align - 1);
-}
-static inline uintptr_t align_up(uintptr_t addr, size_t align) {
- return align_down(addr + align - 1, align);
-}
-
static struct slab *object_slab(void *obj) {
uintptr_t addr = (uintptr_t) obj;
uintptr_t base = align_down(addr, SLAB_SIZE);
@@ -1999,7 +1995,8 @@ static int mark_space_init(struct mark_space *space,
struct gc_heap *heap) {
}
int gc_init(int argc, struct gc_option argv[],
- struct gc_heap **heap, struct gc_mutator **mut) {
+ struct gc_stack_addr *stack_base, struct gc_heap **heap,
+ struct gc_mutator **mut) {
GC_ASSERT_EQ(gc_allocator_small_granule_size(), GRANULE_SIZE);
GC_ASSERT_EQ(gc_allocator_large_threshold(), LARGE_OBJECT_THRESHOLD);
GC_ASSERT_EQ(gc_allocator_allocation_pointer_offset(),
@@ -2041,7 +2038,7 @@ int gc_init(int argc, struct gc_option argv[],
return 1;
}
-struct gc_mutator* gc_init_for_thread(uintptr_t *stack_base,
+struct gc_mutator* gc_init_for_thread(struct gc_stack_addr *stack_base,
struct gc_heap *heap) {
struct gc_mutator *ret = calloc(1, sizeof(struct gc_mutator));
if (!ret)
