summaryrefslogtreecommitdiff
path: root/libguile/whippet/src/simple-worklist.h
diff options
context:
space:
mode:
Diffstat (limited to 'libguile/whippet/src/simple-worklist.h')
-rw-r--r--libguile/whippet/src/simple-worklist.h121
1 files changed, 121 insertions, 0 deletions
diff --git a/libguile/whippet/src/simple-worklist.h b/libguile/whippet/src/simple-worklist.h
new file mode 100644
index 000000000..61f92a31d
--- /dev/null
+++ b/libguile/whippet/src/simple-worklist.h
@@ -0,0 +1,121 @@
+#ifndef SIMPLE_WORKLIST_H
+#define SIMPLE_WORKLIST_H
+
+#include "assert.h"
+#include "debug.h"
+#include "gc-inline.h"
+#include "gc-ref.h"
+#include "gc-platform.h"
+
+struct simple_worklist {
+ size_t size;
+ size_t read;
+ size_t write;
+ struct gc_ref *buf;
+};
+
+static const size_t simple_worklist_max_size =
+ (1ULL << (sizeof(struct gc_ref) * 8 - 1)) / sizeof(struct gc_ref);
+static const size_t simple_worklist_release_byte_threshold = 1 * 1024 * 1024;
+
+static struct gc_ref *
+simple_worklist_alloc(size_t size) {
+ void *mem = gc_platform_acquire_memory(size * sizeof(struct gc_ref), 0);
+ if (!mem) {
+ perror("Failed to grow trace queue");
+ DEBUG("Failed to allocate %zu bytes", size);
+ return NULL;
+ }
+ return mem;
+}
+
+static int
+simple_worklist_init(struct simple_worklist *q) {
+ q->size = gc_platform_page_size() / sizeof(struct gc_ref);
+ q->read = 0;
+ q->write = 0;
+ q->buf = simple_worklist_alloc(q->size);
+ return !!q->buf;
+}
+
+static inline struct gc_ref
+simple_worklist_get(struct simple_worklist *q, size_t idx) {
+ return q->buf[idx & (q->size - 1)];
+}
+
+static inline void
+simple_worklist_put(struct simple_worklist *q, size_t idx, struct gc_ref x) {
+ q->buf[idx & (q->size - 1)] = x;
+}
+
+static int simple_worklist_grow(struct simple_worklist *q) GC_NEVER_INLINE;
+
+static int
+simple_worklist_grow(struct simple_worklist *q) {
+ size_t old_size = q->size;
+ struct gc_ref *old_buf = q->buf;
+ if (old_size >= simple_worklist_max_size) {
+ DEBUG("trace queue already at max size of %zu bytes", old_size);
+ return 0;
+ }
+
+ size_t new_size = old_size * 2;
+ struct gc_ref *new_buf = simple_worklist_alloc(new_size);
+ if (!new_buf)
+ return 0;
+
+ size_t old_mask = old_size - 1;
+ size_t new_mask = new_size - 1;
+
+ for (size_t i = q->read; i < q->write; i++)
+ new_buf[i & new_mask] = old_buf[i & old_mask];
+
+ munmap(old_buf, old_size * sizeof(struct gc_ref));
+
+ q->size = new_size;
+ q->buf = new_buf;
+ return 1;
+}
+
+static inline void
+simple_worklist_push(struct simple_worklist *q, struct gc_ref p) {
+ if (UNLIKELY(q->write - q->read == q->size)) {
+ if (!simple_worklist_grow(q))
+ GC_CRASH();
+ }
+ simple_worklist_put(q, q->write++, p);
+}
+
+static inline void
+simple_worklist_push_many(struct simple_worklist *q, struct gc_ref *pv,
+ size_t count) {
+ while (q->size - (q->write - q->read) < count) {
+ if (!simple_worklist_grow(q))
+ GC_CRASH();
+ }
+ for (size_t i = 0; i < count; i++)
+ simple_worklist_put(q, q->write++, pv[i]);
+}
+
+static inline struct gc_ref
+simple_worklist_pop(struct simple_worklist *q) {
+ if (UNLIKELY(q->read == q->write))
+ return gc_ref_null();
+ return simple_worklist_get(q, q->read++);
+}
+
+static void
+simple_worklist_release(struct simple_worklist *q) {
+ size_t byte_size = q->size * sizeof(struct gc_ref);
+ if (byte_size >= simple_worklist_release_byte_threshold)
+ madvise(q->buf, byte_size, MADV_DONTNEED);
+ q->read = q->write = 0;
+}
+
+static void
+simple_worklist_destroy(struct simple_worklist *q) {
+ size_t byte_size = q->size * sizeof(struct gc_ref);
+ munmap(q->buf, byte_size);
+}
+
+#endif // SIMPLE_WORKLIST_H