summaryrefslogtreecommitdiff
path: root/libguile/whippet/src/large-object-space.h
diff options
context:
space:
mode:
Diffstat (limited to 'libguile/whippet/src/large-object-space.h')
-rw-r--r--libguile/whippet/src/large-object-space.h525
1 files changed, 525 insertions, 0 deletions
diff --git a/libguile/whippet/src/large-object-space.h b/libguile/whippet/src/large-object-space.h
new file mode 100644
index 000000000..cdd798343
--- /dev/null
+++ b/libguile/whippet/src/large-object-space.h
@@ -0,0 +1,525 @@
+#ifndef LARGE_OBJECT_SPACE_H
+#define LARGE_OBJECT_SPACE_H
+
+#include <pthread.h>
+#include <malloc.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "gc-assert.h"
+#include "gc-ref.h"
+#include "gc-conservative-ref.h"
+#include "gc-trace.h"
+#include "address-map.h"
+#include "address-set.h"
+#include "background-thread.h"
+#include "freelist.h"
+
+// A mark-sweep space with generational support.
+
+struct gc_heap;
+
+enum large_object_state {
+ LARGE_OBJECT_NURSERY = 0,
+ LARGE_OBJECT_MARKED_BIT = 1,
+ LARGE_OBJECT_MARK_TOGGLE_BIT = 2,
+ LARGE_OBJECT_MARK_0 = LARGE_OBJECT_MARKED_BIT,
+ LARGE_OBJECT_MARK_1 = LARGE_OBJECT_MARKED_BIT | LARGE_OBJECT_MARK_TOGGLE_BIT
+};
+
+struct large_object {
+ uintptr_t addr;
+ size_t size;
+};
+struct large_object_node;
+struct large_object_live_data {
+ uint8_t mark;
+ enum gc_trace_kind trace;
+};
+struct large_object_dead_data {
+ uint8_t age;
+ struct large_object_node **prev;
+ struct large_object_node *next;
+};
+struct large_object_data {
+ uint8_t is_live;
+ union {
+ struct large_object_live_data live;
+ struct large_object_dead_data dead;
+ };
+};
+
+#define SPLAY_TREE_PREFIX large_object_
+typedef struct large_object large_object_key_span;
+typedef uintptr_t large_object_key;
+typedef struct large_object_data large_object_value;
+static inline int
+large_object_compare(uintptr_t addr, struct large_object obj) {
+ if (addr < obj.addr) return -1;
+ if (addr - obj.addr < obj.size) return 0;
+ return 1;
+}
+static inline uintptr_t
+large_object_span_start(struct large_object obj) {
+ return obj.addr;
+}
+#include "splay-tree.h"
+
+DEFINE_FREELIST(large_object_freelist, sizeof(uintptr_t) * 8 - 1, 2,
+ struct large_object_node*);
+
+struct large_object_space {
+ // Lock for object_map, quarantine, nursery, and marked.
+ pthread_mutex_t lock;
+ // Lock for object_tree.
+ pthread_mutex_t object_tree_lock;
+ // Lock for remembered_edges.
+ pthread_mutex_t remembered_edges_lock;
+ // Locking order: You must hold the space lock when taking
+ // object_tree_lock. Take no other lock while holding
+ // object_tree_lock. remembered_edges_lock is a leaf; take no locks
+ // when holding it.
+
+ // The value for a large_object_node's "mark" field indicating a
+ // marked object; always nonzero, and alternating between two values
+ // at every major GC.
+ uint8_t marked;
+
+ // Splay tree of objects, keyed by <addr, size> tuple. Useful when
+ // looking up object-for-address.
+ struct large_object_tree object_tree;
+
+ // Hash table of objects, where values are pointers to splay tree
+ // nodes. Useful when you have the object address and just want to
+ // check something about it (for example its size).
+ struct address_map object_map;
+
+ // In generational configurations, we collect all allocations in the
+ // last cycle into the nursery.
+ struct address_map nursery;
+
+ // Size-segregated freelist of dead objects. Allocations are first
+ // served from the quarantine freelist before falling back to the OS
+ // if needed. Collected objects spend a second or two in quarantine
+ // before being returned to the OS. This is an optimization to avoid
+ // mucking about too much with the TLB and so on.
+ struct large_object_freelist quarantine;
+
+ // Set of edges from lospace that may reference young objects,
+ // possibly in other spaces.
+ struct address_set remembered_edges;
+
+ size_t page_size;
+ size_t page_size_log2;
+ size_t total_pages;
+ size_t free_pages;
+ size_t live_pages_at_last_collection;
+ size_t pages_freed_by_last_collection;
+ int synchronous_release;
+};
+
+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 size_t
+large_object_space_size_at_last_collection(struct large_object_space *space) {
+ return space->live_pages_at_last_collection << space->page_size_log2;
+}
+
+static inline int
+large_object_space_contains_with_lock(struct large_object_space *space,
+ struct gc_ref ref) {
+ return address_map_contains(&space->object_map, gc_ref_value(ref));
+}
+
+static inline int
+large_object_space_contains(struct large_object_space *space,
+ struct gc_ref ref) {
+ pthread_mutex_lock(&space->lock);
+ int ret = large_object_space_contains_with_lock(space, ref);
+ pthread_mutex_unlock(&space->lock);
+ return ret;
+}
+
+static inline struct gc_ref
+large_object_space_object_containing_edge(struct large_object_space *space,
+ struct gc_edge edge) {
+ pthread_mutex_lock(&space->object_tree_lock);
+ struct large_object_node *node =
+ large_object_tree_lookup(&space->object_tree, gc_edge_address(edge));
+ uintptr_t addr = (node && node->value.is_live) ? node->key.addr : 0;
+ pthread_mutex_unlock(&space->object_tree_lock);
+ return gc_ref(addr);
+}
+
+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 (!is_minor_gc) {
+ space->marked ^= LARGE_OBJECT_MARK_TOGGLE_BIT;
+ space->live_pages_at_last_collection = 0;
+ }
+}
+
+static inline struct gc_trace_plan
+large_object_space_object_trace_plan(struct large_object_space *space,
+ struct gc_ref ref) {
+ uintptr_t node_bits =
+ address_map_lookup(&space->object_map, gc_ref_value(ref), 0);
+ GC_ASSERT(node_bits);
+ struct large_object_node *node = (struct large_object_node*) node_bits;
+ switch (node->value.live.trace) {
+ case GC_TRACE_PRECISELY:
+ return (struct gc_trace_plan){ GC_TRACE_PRECISELY, };
+ case GC_TRACE_NONE:
+ return (struct gc_trace_plan){ GC_TRACE_NONE, };
+#if GC_CONSERVATIVE_TRACE
+ case GC_TRACE_CONSERVATIVELY: {
+ return (struct gc_trace_plan){ GC_TRACE_CONSERVATIVELY, node->key.size };
+ }
+ // No large ephemerons.
+#endif
+ default:
+ GC_CRASH();
+ }
+}
+
+static uint8_t*
+large_object_node_mark_loc(struct large_object_node *node) {
+ GC_ASSERT(node->value.is_live);
+ return &node->value.live.mark;
+}
+
+static uint8_t
+large_object_node_get_mark(struct large_object_node *node) {
+ return atomic_load_explicit(large_object_node_mark_loc(node),
+ memory_order_acquire);
+}
+
+static struct large_object_node*
+large_object_space_lookup(struct large_object_space *space, struct gc_ref ref) {
+ return (struct large_object_node*) address_map_lookup(&space->object_map,
+ gc_ref_value(ref),
+ 0);
+}
+
+static int
+large_object_space_mark(struct large_object_space *space, struct gc_ref ref) {
+ struct large_object_node *node = large_object_space_lookup(space, ref);
+ if (!node)
+ return 0;
+ GC_ASSERT(node->value.is_live);
+
+ uint8_t *loc = large_object_node_mark_loc(node);
+ uint8_t mark = atomic_load_explicit(loc, memory_order_relaxed);
+ do {
+ if (mark == space->marked)
+ return 0;
+ } while (!atomic_compare_exchange_weak_explicit(loc, &mark, space->marked,
+ memory_order_acq_rel,
+ memory_order_acquire));
+
+ size_t pages = node->key.size >> space->page_size_log2;
+ atomic_fetch_add(&space->live_pages_at_last_collection, pages);
+
+ return 1;
+}
+
+static int
+large_object_space_is_marked(struct large_object_space *space,
+ struct gc_ref ref) {
+ struct large_object_node *node = large_object_space_lookup(space, ref);
+ if (!node)
+ return 0;
+ GC_ASSERT(node->value.is_live);
+
+ return atomic_load_explicit(large_object_node_mark_loc(node),
+ memory_order_acquire) == space->marked;
+}
+
+static int
+large_object_space_is_survivor(struct large_object_space *space,
+ struct gc_ref ref) {
+ GC_ASSERT(large_object_space_contains(space, ref));
+ pthread_mutex_lock(&space->lock);
+ int old = large_object_space_is_marked(space, ref);
+ pthread_mutex_unlock(&space->lock);
+ return old;
+}
+
+static int
+large_object_space_remember_edge(struct large_object_space *space,
+ struct gc_ref obj,
+ struct gc_edge edge) {
+ GC_ASSERT(large_object_space_contains(space, obj));
+ if (!large_object_space_is_survivor(space, obj))
+ return 0;
+
+ uintptr_t edge_addr = gc_edge_address(edge);
+ int remembered = 0;
+ pthread_mutex_lock(&space->remembered_edges_lock);
+ if (!address_set_contains(&space->remembered_edges, edge_addr)) {
+ address_set_add(&space->remembered_edges, edge_addr);
+ remembered = 1;
+ }
+ pthread_mutex_unlock(&space->remembered_edges_lock);
+ return remembered;
+}
+
+static void
+large_object_space_forget_edge(struct large_object_space *space,
+ struct gc_edge edge) {
+ uintptr_t edge_addr = gc_edge_address(edge);
+ pthread_mutex_lock(&space->remembered_edges_lock);
+ GC_ASSERT(address_set_contains(&space->remembered_edges, edge_addr));
+ address_set_remove(&space->remembered_edges, edge_addr);
+ pthread_mutex_unlock(&space->remembered_edges_lock);
+}
+
+static void
+large_object_space_clear_remembered_edges(struct large_object_space *space) {
+ address_set_clear(&space->remembered_edges);
+}
+
+static void
+large_object_space_add_to_freelist(struct large_object_space *space,
+ struct large_object_node *node) {
+ node->value.is_live = 0;
+ struct large_object_dead_data *data = &node->value.dead;
+ memset(data, 0, sizeof(*data));
+ data->age = 0;
+ struct large_object_node **bucket =
+ large_object_freelist_bucket(&space->quarantine, node->key.size);
+ data->next = *bucket;
+ if (data->next)
+ data->next->value.dead.prev = &data->next;
+ data->prev = bucket;
+ *bucket = node;
+}
+
+static void
+large_object_space_remove_from_freelist(struct large_object_space *space,
+ struct large_object_node *node) {
+ GC_ASSERT(!node->value.is_live);
+ struct large_object_dead_data *dead = &node->value.dead;
+ GC_ASSERT(dead->prev);
+ if (dead->next)
+ dead->next->value.dead.prev = dead->prev;
+ *dead->prev = dead->next;
+ dead->prev = NULL;
+ dead->next = NULL;
+}
+
+static void
+large_object_space_sweep_one(uintptr_t addr, uintptr_t node_bits,
+ void *data) {
+ struct large_object_space *space = data;
+ struct large_object_node *node = (struct large_object_node*) node_bits;
+ if (!node->value.is_live)
+ return;
+ GC_ASSERT(node->value.is_live);
+ uint8_t mark = atomic_load_explicit(large_object_node_mark_loc(node),
+ memory_order_acquire);
+ if (mark != space->marked)
+ large_object_space_add_to_freelist(space, node);
+}
+
+static void
+large_object_space_process_quarantine(void *data) {
+ struct large_object_space *space = data;
+ pthread_mutex_lock(&space->lock);
+ pthread_mutex_lock(&space->object_tree_lock);
+ for (size_t idx = 0; idx < large_object_freelist_num_size_classes(); idx++) {
+ struct large_object_node **link = &space->quarantine.buckets[idx];
+ for (struct large_object_node *node = *link; node; node = *link) {
+ GC_ASSERT(!node->value.is_live);
+ if (++node->value.dead.age < 2) {
+ link = &node->value.dead.next;
+ } else {
+ struct large_object obj = node->key;
+ large_object_space_remove_from_freelist(space, node);
+ address_map_remove(&space->object_map, obj.addr);
+ large_object_tree_remove(&space->object_tree, obj.addr);
+ gc_platform_release_memory((void*)obj.addr, obj.size);
+ }
+ }
+ }
+ pthread_mutex_unlock(&space->object_tree_lock);
+ pthread_mutex_unlock(&space->lock);
+}
+
+static void
+large_object_space_finish_gc(struct large_object_space *space,
+ int is_minor_gc) {
+ if (GC_GENERATIONAL) {
+ address_map_for_each(is_minor_gc ? &space->nursery : &space->object_map,
+ large_object_space_sweep_one,
+ space);
+ address_map_clear(&space->nursery);
+ } else {
+ address_map_for_each(&space->object_map,
+ large_object_space_sweep_one,
+ space);
+ }
+ size_t free_pages =
+ space->total_pages - space->live_pages_at_last_collection;
+ space->pages_freed_by_last_collection = free_pages - space->free_pages;
+ space->free_pages = free_pages;
+ pthread_mutex_unlock(&space->lock);
+ if (space->synchronous_release)
+ large_object_space_process_quarantine(space);
+}
+
+static void
+large_object_space_add_to_allocation_counter(struct large_object_space *space,
+ uint64_t *counter) {
+ size_t pages = space->total_pages - space->free_pages;
+ pages -= space->live_pages_at_last_collection;
+ *counter += pages << space->page_size_log2;
+}
+
+static inline struct gc_ref
+large_object_space_mark_conservative_ref(struct large_object_space *space,
+ struct gc_conservative_ref ref,
+ int possibly_interior) {
+ uintptr_t addr = gc_conservative_ref_value(ref);
+
+ if (!possibly_interior) {
+ // Addr not aligned on page boundary? Not a large object.
+ // Otherwise strip the displacement to obtain the true base address.
+ uintptr_t displacement = addr & (space->page_size - 1);
+ if (!gc_is_valid_conservative_ref_displacement(displacement))
+ return gc_ref_null();
+ addr -= displacement;
+ }
+
+ struct large_object_node *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));
+ }
+
+ if (node && node->value.is_live &&
+ large_object_space_mark(space, gc_ref(node->key.addr)))
+ return gc_ref(node->key.addr);
+
+ return gc_ref_null();
+}
+
+static void*
+large_object_space_alloc(struct large_object_space *space, size_t npages,
+ enum gc_trace_kind trace) {
+ void *ret = NULL;
+ pthread_mutex_lock(&space->lock);
+
+ size_t size = npages << space->page_size_log2;
+ for (size_t idx = large_object_freelist_size_class(size);
+ idx < large_object_freelist_num_size_classes();
+ idx++) {
+ struct large_object_node *node = space->quarantine.buckets[idx];
+ while (node && node->key.size < size)
+ node = node->value.dead.next;
+ if (node) {
+ // We found a suitable hole in quarantine. Unlink it from the
+ // freelist.
+ large_object_space_remove_from_freelist(space, node);
+
+ // Mark the hole as live.
+ node->value.is_live = 1;
+ memset(&node->value.live, 0, sizeof(node->value.live));
+ node->value.live.mark = LARGE_OBJECT_NURSERY;
+ node->value.live.trace = trace;
+
+ // If the hole is actually too big, trim its tail.
+ if (node->key.size > size) {
+ struct large_object tail = {node->key.addr + size, node->key.size - size};
+ struct large_object_data tail_value = {0,};
+ node->key.size = size;
+ pthread_mutex_lock(&space->object_tree_lock);
+ struct large_object_node *tail_node =
+ large_object_tree_insert(&space->object_tree, tail, tail_value);
+ pthread_mutex_unlock(&space->object_tree_lock);
+ uintptr_t tail_node_bits = (uintptr_t)tail_node;
+ address_map_add(&space->object_map, tail_node->key.addr,
+ tail_node_bits);
+ large_object_space_add_to_freelist(space, tail_node);
+ }
+
+ // Add the object to the nursery.
+ if (GC_GENERATIONAL)
+ address_map_add(&space->nursery, node->key.addr, (uintptr_t)node);
+
+ space->free_pages -= npages;
+ ret = (void*)node->key.addr;
+ memset(ret, 0, size);
+ break;
+ }
+ }
+
+ // If we didn't find anything in the quarantine, get fresh pages from the OS.
+ if (!ret) {
+ ret = gc_platform_acquire_memory(size, 0);
+ if (ret) {
+ uintptr_t addr = (uintptr_t)ret;
+ struct large_object k = { addr, size };
+ struct large_object_data v = {0,};
+ v.is_live = 1;
+ v.live.mark = LARGE_OBJECT_NURSERY;
+ v.live.trace = trace;
+
+ pthread_mutex_lock(&space->object_tree_lock);
+ struct large_object_node *node =
+ large_object_tree_insert(&space->object_tree, k, v);
+ uintptr_t node_bits = (uintptr_t)node;
+ address_map_add(&space->object_map, addr, node_bits);
+ space->total_pages += npages;
+ pthread_mutex_unlock(&space->object_tree_lock);
+ }
+ }
+
+ pthread_mutex_unlock(&space->lock);
+ return ret;
+}
+
+static int
+large_object_space_init(struct large_object_space *space,
+ struct gc_heap *heap,
+ struct gc_background_thread *thread) {
+ memset(space, 0, sizeof(*space));
+ pthread_mutex_init(&space->lock, NULL);
+ pthread_mutex_init(&space->object_tree_lock, NULL);
+ pthread_mutex_init(&space->remembered_edges_lock, NULL);
+
+ space->page_size = getpagesize();
+ space->page_size_log2 = __builtin_ctz(space->page_size);
+
+ space->marked = LARGE_OBJECT_MARK_0;
+
+ large_object_tree_init(&space->object_tree);
+ address_map_init(&space->object_map);
+ address_map_init(&space->nursery);
+ large_object_freelist_init(&space->quarantine);
+
+ address_set_init(&space->remembered_edges);
+
+ if (thread)
+ gc_background_thread_add_task(thread, GC_BACKGROUND_TASK_START,
+ large_object_space_process_quarantine,
+ space);
+ else
+ space->synchronous_release = 1;
+
+ return 1;
+}
+
+#endif // LARGE_OBJECT_SPACE_H