wingo pushed a commit to branch wip-whippet
in repository guile.
commit ce52d8417394e8d05be32ed013c1a0d16b673eb7
Author: Andy Wingo <[email protected]>
AuthorDate: Tue Aug 5 15:31:43 2025 +0200
Avoid synchronization when looking up lospace conservative refs
---
src/address-map.h | 3 +++
src/extents.h | 33 +++++++++++++++++++++++++++++++--
src/large-object-space.h | 48 +++++++++++++++++++++++++++++++++++++++++++++---
3 files changed, 79 insertions(+), 5 deletions(-)
diff --git a/src/address-map.h b/src/address-map.h
index 57c2a0a04..d7356a569 100644
--- a/src/address-map.h
+++ b/src/address-map.h
@@ -177,6 +177,9 @@ static void address_map_destroy(struct address_map *map) {
static void address_map_clear(struct address_map *map) {
hash_map_clear(&map->hash_map);
}
+static size_t address_map_size(struct address_map *map) {
+ return map->hash_map.n_items;
+}
static void address_map_add(struct address_map *map, uintptr_t addr, uintptr_t
v) {
hash_map_insert(&map->hash_map, hash_address(addr), v);
diff --git a/src/extents.h b/src/extents.h
index 62dba92b9..89460ea0d 100644
--- a/src/extents.h
+++ b/src/extents.h
@@ -17,7 +17,7 @@ struct extents {
struct extent_range ranges[];
};
-static inline int
+static inline uintptr_t
extents_contain_addr(struct extents *extents, uintptr_t addr) {
size_t lo = 0;
size_t hi = extents->size;
@@ -27,7 +27,7 @@ extents_contain_addr(struct extents *extents, uintptr_t addr)
{
if (addr < range.lo_addr) {
hi = mid;
} else if (addr < range.hi_addr) {
- return 1;
+ return range.lo_addr;
} else {
lo = mid + 1;
}
@@ -69,6 +69,7 @@ extents_insert(struct extents *old, size_t idx, struct
extent_range range) {
static struct extents*
extents_adjoin(struct extents *extents, void *lo_addr, size_t size) {
+ GC_ASSERT(range.lo_addr);
size_t i;
struct extent_range range = { (uintptr_t)lo_addr, (uintptr_t)lo_addr + size
};
for (i = 0; i < extents->size; i++) {
@@ -85,4 +86,32 @@ extents_adjoin(struct extents *extents, void *lo_addr,
size_t size) {
return extents_insert(extents, i, range);
}
+static inline struct extents*
+extents_clear(struct extents *extents) {
+ extents->size = 0;
+ return extents;
+}
+
+static inline struct extents*
+extents_prepare(struct extents *extents, size_t size)
+{
+ if (size <= extents->size)
+ return extents_clear(extents);
+
+ size_t capacity = extents->size * 2;
+ if (capacity < size)
+ capacity = size;
+ free(extents);
+ return extents_allocate(capacity);
+}
+
+static inline void
+extents_append(struct extents *extents, void *lo_addr, size_t size) {
+ size_t idx = extents->size++;
+ GC_ASSERT(extents->size <= extents->capacity);
+ struct extent_range range = { (uintptr_t)lo_addr, (uintptr_t)lo_addr + size
};
+ GC_ASSERT(idx == 0 || extents->ranges[idx - 1].hi_addr <= range.lo_addr);
+ extents->ranges[idx] = range;
+}
+
#endif // EXTENTS_H
diff --git a/src/large-object-space.h b/src/large-object-space.h
index 59aea8628..9104aa6d7 100644
--- a/src/large-object-space.h
+++ b/src/large-object-space.h
@@ -111,6 +111,10 @@ struct large_object_space {
// possibly in other spaces.
struct address_set remembered_edges;
+ // Sorted array of object extents; used during GC to identify
+ // conservative refs.
+ struct extents *extents;
+
size_t page_size;
size_t page_size_log2;
size_t total_pages;
@@ -156,12 +160,32 @@ large_object_space_object_containing_edge(struct
large_object_space *space,
return gc_ref(addr);
}
+static void
+large_object_append_extent(struct large_object_node *node,
+ struct extents *extents) {
+ if (node->left) large_object_append_extent(node->left, extents);
+ extents_append(extents, (void*)node->key.addr, node->key.size);
+ if (node->right) large_object_append_extent(node->right, extents);
+}
+
+static void
+large_object_space_prepare_extents(struct large_object_space *space) {
+ pthread_mutex_lock(&space->object_tree_lock);
+ space->extents = extents_prepare(space->extents,
+ address_map_size(&space->object_map));
+ if (space->object_tree.root)
+ large_object_append_extent(space->object_tree.root, space->extents);
+ pthread_mutex_unlock(&space->object_tree_lock);
+}
+
static void
large_object_space_start_gc(struct large_object_space *space, int is_minor_gc)
{
// Take the space lock to prevent
// large_object_space_process_quarantine from concurrently mutating
// the object map.
pthread_mutex_lock(&space->lock);
+ if (gc_has_mutator_conservative_roots())
+ large_object_space_prepare_extents(space);
if (!is_minor_gc) {
space->marked ^= LARGE_OBJECT_MARK_TOGGLE_BIT;
space->live_pages_at_last_collection = 0;
@@ -356,6 +380,8 @@ large_object_space_process_quarantine(void *data) {
static void
large_object_space_finish_gc(struct large_object_space *space,
int is_minor_gc) {
+ if (gc_has_mutator_conservative_roots())
+ extents_clear(space->extents);
if (GC_GENERATIONAL) {
address_map_for_each(is_minor_gc ? &space->nursery : &space->object_map,
large_object_space_sweep_one,
@@ -398,13 +424,26 @@ large_object_space_lookup_conservative_ref(struct
large_object_space *space,
addr -= displacement;
}
- struct large_object_node *node;
+ if (space->extents->size) {
+ // We are in a collection; avoid locks.
+ uintptr_t start = extents_contain_addr(space->extents, addr);
+ if (!start)
+ return NULL;
+ if (possibly_interior)
+ addr = start;
+ else if (addr != start)
+ return NULL;
+ }
+
+ struct large_object_node *node =
+ large_object_space_lookup(space, gc_ref(addr));
+ if (node)
+ return node;
+
if (possibly_interior) {
pthread_mutex_lock(&space->object_tree_lock);
node = large_object_tree_lookup(&space->object_tree, addr);
pthread_mutex_unlock(&space->object_tree_lock);
- } else {
- node = large_object_space_lookup(space, gc_ref(addr));
}
return node;
@@ -533,6 +572,9 @@ large_object_space_init(struct large_object_space *space,
address_set_init(&space->remembered_edges);
+ if (gc_has_mutator_conservative_roots())
+ space->extents = extents_allocate(64);
+
if (thread)
gc_background_thread_add_task(thread, GC_BACKGROUND_TASK_START,
large_object_space_process_quarantine,
