wingo pushed a commit to branch wip-whippet
in repository guile.
commit 3315fc7477068377458fc61c772e903487e38620
Author: Andy Wingo <wi...@igalia.com>
AuthorDate: Thu Apr 14 22:20:27 2022 +0200
Add large object space to semi-space collector
---
large-object-space.h | 32 ++++++++++++++--
semi.h | 101 +++++++++++++++++++++++++++++++++++++++++++++------
2 files changed, 117 insertions(+), 16 deletions(-)
diff --git a/large-object-space.h b/large-object-space.h
index bcd36e9e9..29d733a9e 100644
--- a/large-object-space.h
+++ b/large-object-space.h
@@ -43,7 +43,7 @@ static int large_object_space_init(struct large_object_space
*space,
struct heap *heap) {
pthread_mutex_init(&space->lock, NULL);
space->page_size = getpagesize();
- space->page_size_log2 = __builtin_clz(space->page_size);
+ space->page_size_log2 = __builtin_ctz(space->page_size);
address_set_init(&space->from_space);
address_set_init(&space->to_space);
address_set_init(&space->free_space);
@@ -52,6 +52,11 @@ static int large_object_space_init(struct large_object_space
*space,
return 1;
}
+static size_t large_object_space_npages(struct large_object_space *space,
+ size_t bytes) {
+ return (bytes + space->page_size - 1) >> space->page_size_log2;
+}
+
static void large_object_space_start_gc(struct large_object_space *space) {
// Flip. Note that when we flip, fromspace is empty, but it might have
// allocated storage, so we do need to do a proper swap.
@@ -156,12 +161,11 @@ static int large_object_space_best_fit(uintptr_t addr,
void *data) {
return found->min_npages == npages;
}
-static inline void* large_object_space_alloc(struct large_object_space *space,
- size_t size) {
+static void* large_object_space_alloc(struct large_object_space *space,
+ size_t npages) {
void *ret;
pthread_mutex_lock(&space->lock);
ret = NULL;
- size_t npages = (size + space->page_size - 1) >> space->page_size_log2;
struct large_object_space_candidate found = { space, npages, 0, -1 };
address_set_find(&space->free_space, large_object_space_best_fit, &found);
if (found.addr) {
@@ -185,4 +189,24 @@ static inline void* large_object_space_alloc(struct
large_object_space *space,
return ret;
}
+static void*
+large_object_space_obtain_and_alloc(struct large_object_space *space,
+ size_t npages) {
+ size_t bytes = npages * space->page_size;
+ void *ret = mmap(NULL, bytes, PROT_READ|PROT_WRITE,
+ MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
+ if (ret == MAP_FAILED)
+ return NULL;
+
+ uintptr_t addr = (uintptr_t)ret;
+ pthread_mutex_lock(&space->lock);
+ address_map_add(&space->object_pages, addr, npages);
+ address_map_add(&space->predecessors, addr + bytes, addr);
+ address_set_add(&space->to_space, addr);
+ space->total_pages += npages;
+ pthread_mutex_unlock(&space->lock);
+
+ return ret;
+}
+
#endif // LARGE_OBJECT_SPACE_H
diff --git a/semi.h b/semi.h
index 3661c7ace..0757ee6b0 100644
--- a/semi.h
+++ b/semi.h
@@ -55,6 +55,23 @@ static void collect_for_alloc(struct mutator *mut, size_t
bytes) NEVER_INLINE;
static void visit(void **loc, void *visit_data);
+static int semi_space_steal_pages(struct semi_space *space, size_t npages) {
+ size_t page_size = getpagesize();
+
+ if (npages & 1) npages++;
+ size_t half_size = (npages * page_size) >> 1;
+ if (space->limit - space->hp < half_size)
+ return 0;
+
+ space->limit -= half_size;
+ size_t tospace_offset = space->limit - space->base;
+ madvise((void*)(space->base + tospace_offset), half_size, MADV_DONTNEED);
+ size_t fromspace_offset =
+ (tospace_offset + (space->size >> 1)) & (space->size - 1);
+ madvise((void*)(space->base + fromspace_offset), half_size, MADV_DONTNEED);
+ return 1;
+}
+
static void flip(struct semi_space *space) {
uintptr_t split = space->base + (space->size >> 1);
if (space->hp <= split) {
@@ -86,13 +103,13 @@ static void* copy(struct semi_space *space, uintptr_t
kind, void *obj) {
return new_obj;
}
-static uintptr_t scan(struct semi_space *space, uintptr_t grey) {
+static uintptr_t scan(struct heap *heap, uintptr_t grey) {
void *obj = (void*)grey;
uintptr_t kind = *(uintptr_t*) obj;
switch (kind) {
#define SCAN_OBJECT(name, Name, NAME) \
case ALLOC_KIND_##NAME: \
- visit_##name##_fields((Name*)obj, visit, space); \
+ visit_##name##_fields((Name*)obj, visit, heap); \
return grey + align_up(name##_size((Name*)obj), ALIGNMENT);
FOR_EACH_HEAP_OBJECT_KIND(SCAN_OBJECT)
#undef SCAN_OBJECT
@@ -114,25 +131,53 @@ static void* forward(struct semi_space *space, void *obj)
{
}
}
+static void visit_semi_space(struct heap *heap, struct semi_space *space,
+ void **loc, void *obj) {
+ *loc = forward(space, obj);
+}
+
+static void visit_large_object_space(struct heap *heap,
+ struct large_object_space *space,
+ void **loc, void *obj) {
+ if (large_object_space_copy(space, (uintptr_t)obj))
+ scan(heap, (uintptr_t)obj);
+}
+
+static int semi_space_contains(struct semi_space *space, void *obj) {
+ return (((uintptr_t)obj) - space->base) < space->size;
+}
+
static void visit(void **loc, void *visit_data) {
- struct semi_space *space = visit_data;
+ struct heap *heap = visit_data;
void *obj = *loc;
- if (obj != NULL)
- *loc = forward(space, obj);
+ if (obj == NULL)
+ return;
+ if (semi_space_contains(heap_semi_space(heap), obj))
+ visit_semi_space(heap, heap_semi_space(heap), loc, obj);
+ else if (large_object_space_contains(heap_large_object_space(heap), obj))
+ visit_large_object_space(heap, heap_large_object_space(heap), loc, obj);
+ else
+ abort();
}
+
static void collect(struct mutator *mut) {
- struct semi_space *space = mutator_semi_space(mut);
+ struct heap *heap = mutator_heap(mut);
+ struct semi_space *semi = heap_semi_space(heap);
+ struct large_object_space *large = heap_large_object_space(heap);
// fprintf(stderr, "start collect #%ld:\n", space->count);
- flip(space);
- uintptr_t grey = space->hp;
+ large_object_space_start_gc(large);
+ flip(semi);
+ uintptr_t grey = semi->hp;
for (struct handle *h = mut->roots; h; h = h->next)
- visit(&h->v, space);
+ visit(&h->v, heap);
// fprintf(stderr, "pushed %zd bytes in roots\n", space->hp - grey);
- while(grey < space->hp)
- grey = scan(space, grey);
+ while(grey < semi->hp)
+ grey = scan(heap, grey);
+ large_object_space_finish_gc(large);
+ semi_space_steal_pages(semi, large->live_pages_at_last_collection);
// fprintf(stderr, "%zd bytes copied\n",
(space->size>>1)-(space->limit-space->hp));
-
}
+
static void collect_for_alloc(struct mutator *mut, size_t bytes) {
collect(mut);
struct semi_space *space = mutator_semi_space(mut);
@@ -142,8 +187,40 @@ static void collect_for_alloc(struct mutator *mut, size_t
bytes) {
}
}
+static const size_t LARGE_OBJECT_THRESHOLD = 8192;
+static void* allocate_large(struct mutator *mut, enum alloc_kind kind,
+ size_t size) {
+ struct heap *heap = mutator_heap(mut);
+ struct large_object_space *space = heap_large_object_space(heap);
+ struct semi_space *semi_space = heap_semi_space(heap);
+
+ size_t npages = large_object_space_npages(space, size);
+ if (!semi_space_steal_pages(semi_space, npages)) {
+ collect(mut);
+ if (!semi_space_steal_pages(semi_space, npages)) {
+ fprintf(stderr, "ran out of space, heap size %zu\n", semi_space->size);
+ abort();
+ }
+ }
+
+ void *ret = large_object_space_alloc(space, npages);
+ if (!ret)
+ ret = large_object_space_obtain_and_alloc(space, npages);
+
+ if (!ret) {
+ perror("weird: we have the space but mmap didn't work");
+ abort();
+ }
+
+ *(uintptr_t*)ret = kind;
+ return ret;
+}
+
static inline void* allocate(struct mutator *mut, enum alloc_kind kind,
size_t size) {
+ if (size >= LARGE_OBJECT_THRESHOLD)
+ return allocate_large(mut, kind, size);
+
struct semi_space *space = mutator_semi_space(mut);
while (1) {
uintptr_t addr = space->hp;
