diff options
Diffstat (limited to 'libguile/whippet/src/field-set.h')
-rw-r--r-- | libguile/whippet/src/field-set.h | 229 |
1 files changed, 229 insertions, 0 deletions
diff --git a/libguile/whippet/src/field-set.h b/libguile/whippet/src/field-set.h new file mode 100644 index 000000000..ff9a68e83 --- /dev/null +++ b/libguile/whippet/src/field-set.h @@ -0,0 +1,229 @@ +#ifndef FIELD_SET_H +#define FIELD_SET_H + +#include <pthread.h> +#include <stdatomic.h> +#include <stdlib.h> + +#include "assert.h" +#include "gc-edge.h" +#include "gc-lock.h" +#include "tracer.h" + +#define GC_EDGE_BUFFER_CAPACITY 510 + +struct gc_edge_buffer { + struct gc_edge_buffer *next; + size_t size; + struct gc_edge edges[GC_EDGE_BUFFER_CAPACITY]; +}; + +// Lock-free. +struct gc_edge_buffer_list { + struct gc_edge_buffer *head; +}; + +// With a lock. +struct gc_edge_buffer_stack { + struct gc_edge_buffer_list list; +}; + +struct gc_field_set { + struct gc_edge_buffer_list full; + struct gc_edge_buffer_stack partly_full; + struct gc_edge_buffer_list empty; + size_t count; + pthread_mutex_t lock; +}; + +struct gc_field_set_writer { + struct gc_edge_buffer *buf; + struct gc_field_set *set; +}; + +static void +gc_edge_buffer_list_push(struct gc_edge_buffer_list *list, + struct gc_edge_buffer *buf) { + GC_ASSERT(!buf->next); + struct gc_edge_buffer *next = + atomic_load_explicit(&list->head, memory_order_relaxed); + do { + buf->next = next; + } while (!atomic_compare_exchange_weak_explicit(&list->head, &next, buf, + memory_order_acq_rel, + memory_order_acquire)); +} + +static struct gc_edge_buffer* +gc_edge_buffer_list_pop(struct gc_edge_buffer_list *list) { + struct gc_edge_buffer *head = + atomic_load_explicit(&list->head, memory_order_acquire); + struct gc_edge_buffer *next; + do { + if (!head) return NULL; + next = head->next; + } while (!atomic_compare_exchange_weak_explicit(&list->head, &head, next, + memory_order_acq_rel, + memory_order_acquire)); + head->next = NULL; + return head; +} + +static void +gc_edge_buffer_stack_push(struct gc_edge_buffer_stack *stack, + struct gc_edge_buffer *buf, + const struct gc_lock *lock) { + GC_ASSERT(!buf->next); + buf->next = stack->list.head; + stack->list.head = buf; +} + +static struct gc_edge_buffer* +gc_edge_buffer_stack_pop(struct gc_edge_buffer_stack *stack, + const struct gc_lock *lock) { + struct gc_edge_buffer *head = stack->list.head; + if (head) { + stack->list.head = head->next; + head->next = NULL; + } + return head; +} + +static void +gc_field_set_init(struct gc_field_set *set) { + memset(set, 0, sizeof(*set)); + pthread_mutex_init(&set->lock, NULL); +} + +static struct gc_edge_buffer* +gc_field_set_acquire_buffer(struct gc_field_set *set) { + struct gc_edge_buffer *ret; + + ret = gc_edge_buffer_list_pop(&set->empty); + if (ret) return ret; + + struct gc_lock lock = gc_lock_acquire(&set->lock); + ret = gc_edge_buffer_stack_pop(&set->partly_full, &lock); + gc_lock_release(&lock); + if (ret) return ret; + + // atomic inc count + ret = malloc(sizeof(*ret)); + if (!ret) { + perror("Failed to allocate remembered set"); + GC_CRASH(); + } + memset(ret, 0, sizeof(*ret)); + return ret; +} + +static void +gc_field_set_release_buffer(struct gc_field_set *set, + struct gc_edge_buffer *buf) { + if (buf->size == GC_EDGE_BUFFER_CAPACITY) { + gc_edge_buffer_list_push(&set->full, buf); + } else { + struct gc_lock lock = gc_lock_acquire(&set->lock); + gc_edge_buffer_stack_push(&set->partly_full, buf, &lock); + gc_lock_release(&lock); + } +} + +static void +gc_field_set_add_roots(struct gc_field_set *set, struct gc_tracer *tracer) { + struct gc_edge_buffer *buf; + struct gc_lock lock = gc_lock_acquire(&set->lock); + while ((buf = gc_edge_buffer_stack_pop(&set->partly_full, &lock))) + gc_tracer_add_root(tracer, gc_root_edge_buffer(buf)); + while ((buf = gc_edge_buffer_list_pop(&set->full))) + gc_tracer_add_root(tracer, gc_root_edge_buffer(buf)); + gc_lock_release(&lock); +} + +static void +gc_field_set_clear(struct gc_field_set *set, + void (*forget_edge)(struct gc_edge, struct gc_heap*), + struct gc_heap *heap) { + struct gc_edge_buffer *partly_full = set->partly_full.list.head; + struct gc_edge_buffer *full = set->full.head; + // Clear the full and partly full sets now so that if a collector + // wanted to it could re-add an edge to the remembered set. + set->partly_full.list.head = NULL; + set->full.head = NULL; + struct gc_edge_buffer *buf, *next; + for (buf = partly_full; buf; buf = next) { + next = buf->next; + buf->next = NULL; + if (forget_edge) + for (size_t i = 0; i < buf->size; i++) + forget_edge(buf->edges[i], heap); + buf->size = 0; + gc_edge_buffer_list_push(&set->empty, buf); + } + for (buf = full; buf; buf = next) { + next = buf->next; + buf->next = NULL; + if (forget_edge) + for (size_t i = 0; i < buf->size; i++) + forget_edge(buf->edges[i], heap); + buf->size = 0; + gc_edge_buffer_list_push(&set->empty, buf); + } +} + +static inline void +gc_field_set_visit_edge_buffer(struct gc_field_set *set, + struct gc_edge_buffer *buf, + int (*visit)(struct gc_edge, + struct gc_heap*, + void *data), + struct gc_heap *heap, + void *data) GC_ALWAYS_INLINE; +static inline void +gc_field_set_visit_edge_buffer(struct gc_field_set *set, + struct gc_edge_buffer *buf, + int (*visit)(struct gc_edge, + struct gc_heap*, + void *data), + struct gc_heap *heap, + void *data) { + size_t i = 0; + while (i < buf->size) { + if (visit(buf->edges[i], heap, data)) + i++; + else + buf->edges[i] = buf->edges[--buf->size]; + } + gc_field_set_release_buffer(set, buf); +} + +static void +gc_field_set_writer_release_buffer(struct gc_field_set_writer *writer) { + if (writer->buf) { + gc_field_set_release_buffer(writer->set, writer->buf); + writer->buf = NULL; + } +} + +static void +gc_field_set_writer_init(struct gc_field_set_writer *writer, + struct gc_field_set *set) { + writer->set = set; + writer->buf = NULL; +} + +static void +gc_field_set_writer_add_edge(struct gc_field_set_writer *writer, + struct gc_edge edge) { + struct gc_edge_buffer *buf = writer->buf; + if (GC_UNLIKELY(!buf)) + writer->buf = buf = gc_field_set_acquire_buffer(writer->set); + GC_ASSERT(buf->size < GC_EDGE_BUFFER_CAPACITY); + buf->edges[buf->size++] = edge; + if (GC_UNLIKELY(buf->size == GC_EDGE_BUFFER_CAPACITY)) { + gc_edge_buffer_list_push(&writer->set->full, buf); + writer->buf = NULL; + } +} + +#endif // FIELD_SET_H |