diff options
| -rw-r--r-- | flake.nix | 14 | ||||
| -rwxr-xr-x | mk.sh | 1 | ||||
| -rw-r--r-- | src/Makefile | 8 | ||||
| -rw-r--r-- | src/gc.h | 5 | ||||
| -rw-r--r-- | src/gc/gc.c | 266 | ||||
| -rw-r--r-- | src/gc/gen3.c | 566 | ||||
| -rw-r--r-- | src/gc/sms.c | 205 | ||||
| -rw-r--r-- | src/main.c | 6 | ||||
| -rw-r--r-- | src/platform.h | 4 | ||||
| -rw-r--r-- | src/platform/3ds.c | 58 | ||||
| -rw-r--r-- | src/platform/3ds.mk | 2 | ||||
| -rw-r--r-- | src/platform/linux.c | 158 | ||||
| -rw-r--r-- | src/util.c | 19 | ||||
| -rw-r--r-- | src/util.h | 5 | ||||
| -rw-r--r-- | src/value.c | 53 | ||||
| -rw-r--r-- | src/value.h | 53 |
16 files changed, 1137 insertions, 286 deletions
@@ -23,17 +23,21 @@ pkgs.bear pkgs.devkitNix.devkitARM ]; - inherit (pkgs.devkitNix.devkitARM) shellHook; }; packages = { - default = packages.imb3; - imb3 = pkgs.stdenv.mkDerivation { + default = packages.imb3-3ds; + imb3-3ds = pkgs.stdenv.mkDerivation { name = "imb3"; - src = ./src; + src = ./.; preBuild = pkgs.devkitNix.devkitARM.shellHook; + buildPhase = '' + runHook preBuild + bash mk.sh 3ds + runHook postBuild + ''; installPhase = '' - cp imb3.3dsx $out + install -Dt $out build/imb3.{3dsx,elf} ''; meta.description = "An interactive programming language sitting somewhere between Common Lisp and Forth."; }; @@ -21,5 +21,4 @@ EOF ln -s "$srcdir/Makefile" n="$(nproc)" -watchexec -w "$srcdir" -- \ make "-j$n" "-l$n" "$@" diff --git a/src/Makefile b/src/Makefile index 0f4841b..e9d49c7 100644 --- a/src/Makefile +++ b/src/Makefile @@ -2,11 +2,15 @@ SRCS = $(sort $(wildcard $(srcdir)/*.c)) OBJS = $(patsubst $(srcdir)/%.c,obj/%.o,$(SRCS)) DEPS = $(patsubst $(srcdir)/%.c,obj/%.d,$(SRCS)) +gc_impl = sms + CFLAGS = CPPFLAGS = LDFLAGS = -CFLAGS_AUTO = -fdata-sections -ffunction-sections -flto -g -O3 -std=c11 -Wall -Werror=implicit-function-declaration +# CFLAGS_AUTO = -fdata-sections -ffunction-sections -flto -g -O3 -std=c11 -Wall -Werror=implicit-function-declaration +# CFLAGS_AUTO = -g -Og -std=c11 -Wall -Werror=implicit-function-declaration +CFLAGS_AUTO = -flto -g -Og -std=c11 -Wall -Werror=implicit-function-declaration LDFLAGS_AUTO = LDLIBS_AUTO = -lm @@ -26,7 +30,7 @@ else include $(srcdir)/platform/$(platform).mk -imb3.elf: $(OBJS) obj/gc/gc.o obj/platform/$(platform).o +imb3.elf: $(OBJS) obj/gc/$(gc_impl).o obj/platform/$(platform).o $(CC) $(CFLAGS_ALL) $(LDFLAGS_ALL) -o $@ $^ $(LDLIBS_ALL) obj/%.o: $(srcdir)/%.c @@ -21,4 +21,9 @@ void gc_write_value_slot(struct object *, size_t, struct value); void gc_write_untraced_slot(struct object *, size_t, uintptr_t); void gc_write_untraced_byte(struct object *, size_t, uint8_t); +void gc_root_push(struct value *); +void gc_root_pop(void); + +void gc_debug(void); + #endif // IMB3_GC_H diff --git a/src/gc/gc.c b/src/gc/gc.c deleted file mode 100644 index 1c0daec..0000000 --- a/src/gc/gc.c +++ /dev/null @@ -1,266 +0,0 @@ -#include "../gc.h" -#include "../platform.h" -#include "../util.h" -#include <stdbool.h> -#include <stddef.h> -#include <stdint.h> -#include <stdlib.h> - -/** - * Constants that should probably be learned. - */ -static const size_t NURSERY_L1D_SIZE_FACTOR = 1; -static const size_t YOUNG_HEAP_L3_SIZE_FACTOR = 2; - -/** - * Objects each have a header, with a slightly different layout depending on - * which heap the object is in. Each header tracks the layout of the object - * itself, as well as some other properties, in a uniform way. via the - * `enum object_kind` and `struct object_size` types. - */ - -/** - * Gives special properties the object might have, as well as the interpretation - * of its size. - */ -enum object_kind { - /** - * A normal object. Has up to 2¹⁶ slots for values, and up to 2¹³ slots for - * untraced `uintptr_t`s (which may simply be used as bytes). - */ - OBJECT_NORMAL, - - /** - * An untraced object. Has up to 2²⁹ slots for untraced `uintptr_t`s (which - * may simply be used as bytes). - */ - OBJECT_UNTRACED, - - /** - * A wrapper for a pointer to a code address. When this object gets collected, - * calls `free_code` on its first untraced slot. - */ - OBJECT_COMPILED_FUNCTION, - - /** - * A hashtable keyed by the addresses. This behaves like a normal object, but - * the first untraced slot gets set to the `uintptr_t` 1 whenever a collection - * traces the hashtable. - * - * The hashtable uses this information to rehash after each collection. - */ - OBJECT_HASHTABLE_EQ, -}; - -/** - * A `size_t`-sized encoding of the object size. Also stores an extra bit used - * to indicate that the object has been moved in nursery collection, and that - * the object has been marked in old-heap collection. - */ -struct object_size { - enum object_kind kind : 2; - bool mark : 1; - size_t bits : (8 * sizeof(size_t)) - 3; -}; - -/** - * Returns the number of slots for values the object has. - */ -static size_t object_size_value_slots(struct object_size size) { - switch (size.kind) { - case OBJECT_NORMAL: - case OBJECT_COMPILED_FUNCTION: - case OBJECT_HASHTABLE_EQ: - return size.bits >> ((4 * sizeof(size_t)) - 3); - case OBJECT_UNTRACED: - return 0; - } -} - -/** - * Returns the number of untraced slots the object has. - */ -static size_t object_size_untraced_slots(struct object_size size) { - switch (size.kind) { - case OBJECT_NORMAL: - case OBJECT_COMPILED_FUNCTION: - case OBJECT_HASHTABLE_EQ: - return size.bits & ((1 << ((4 * sizeof(size_t)) - 3)) - 1); - case OBJECT_UNTRACED: - return size.bits; - } -} - -/** - * This struct is used as an opaque type for the fields of an object. - */ -struct object { - uintptr_t hd; - uintptr_t tl[]; -}; - -/** - * Returns the number of slots for values the object has. - */ -static size_t object_value_slots(const struct object *obj) { - return object_size_value_slots(((struct object_size *)obj)[-1]); -} - -/** - * Returns the number of untraced slots the object has. - */ -static size_t object_untraced_slots(const struct object *obj) { - return object_size_untraced_slots(((struct object_size *)obj)[-1]); -} - -/** - * This is the layout of an object in the nursery. - */ -struct nursery_object { - struct object_size size; - uintptr_t slots[]; -}; - -/** - * This is the layout of an object in the young-heap. Because the young-heap is - * collected with mark-compact, it needs a dedicated forwarding pointer (or in - * our case, a forwarding offset) and can't simply overwrite the object slots - * with one. - */ -struct young_heap_object { - size_t fwd; - struct object_size size; - uintptr_t slots[]; -}; - -/** - * This is the layout of an object in the old-heap. It matches the nursery - * layout at the moment. - */ -struct old_heap_object { - struct object_size size; - uintptr_t slots[]; -}; - -/** - * The nursery and young-heap each have a layout like: - * - * ┌──────────────┐ ←── Top - * │remembered set│ - * ├──────────────┤ ←── Limit - * │ free │ - * │ space │ - * ├──────────────┤ ←── Next - * │ │ - * │ │ - * │ objects │ - * │ │ - * │ │ - * └──────────────┘ ←── Bottom - * - * The layout of both regions are defined by the four labelled pointers, so we - * define them. - */ -uintptr_t nursery_bottom, nursery_next, nursery_limit, nursery_top; -uintptr_t young_heap_bottom, young_heap_next, young_heap_limit, young_heap_top; - -/** - * The old-heap is composed of blocks, each of which are stored in an - * intrusive doubly linked list per size class. Size classes start at 8 bytes - * and go up to 64KiB, with a "large object" size class past that. For size - * classes up to and including 4KiB, blocks are 64KiB in size. Past that, blocks - * are sized to fit one object of the size class. - * - * Each block has a local free-list of objects of the size class. - */ -enum old_heap_size_class { - SIZE_8 = 0, - SIZE_16, - SIZE_32, - SIZE_64, - SIZE_128, - SIZE_256, - SIZE_512, - SIZE_1024, - SIZE_2048, - SIZE_4096, - SIZE_8192, - SIZE_16384, - SIZE_32768, - SIZE_65536, - SIZE_HUGE, - - SIZE_CLASS_COUNT, -}; - -struct old_heap_block { - struct old_heap_block *prev, *next; - struct old_heap_free_object *free_list; -}; - -struct old_heap_free_object { - struct old_heap_free_object *next; -}; - -static struct old_heap_block old_heap_sentinels[SIZE_CLASS_COUNT]; - -void gc_init(void) { - // Allocate the nursery and young-heap. - nursery_bottom = nursery_next = - (uintptr_t)malloc(get_l1d_size() * NURSERY_L1D_SIZE_FACTOR); - assume(nursery_bottom); - young_heap_bottom = young_heap_next = - (uintptr_t)malloc(get_l3_size() * YOUNG_HEAP_L3_SIZE_FACTOR); - assume(young_heap_bottom); - - // Self-link the old-heap. - for (size_t i = 0; i < SIZE_CLASS_COUNT; i++) { - old_heap_sentinels[i].prev = old_heap_sentinels[i].next = - &old_heap_sentinels[i]; - } -} - -struct object *gc_alloc(size_t value_slot_count, size_t untraced_slot_count) { - todo("gc_alloc"); -} - -struct object *gc_alloc_compiled_function(size_t value_slot_count, - size_t untraced_slot_count) { - todo("gc_alloc_compiled_function"); -} - -struct object *gc_alloc_hashtable_eq(size_t value_slot_count, - size_t untraced_slot_count) { - todo("gc_alloc_hashtable_eq"); -} - -struct value gc_read_value_slot(const struct object *obj, size_t slot_index) { - assume(slot_index < object_value_slots(obj)); - todo("gc_read_value_slot"); -} - -uintptr_t gc_read_untraced_slot(const struct object *obj, size_t slot_index) { - assume(slot_index < object_untraced_slots(obj)); - todo("gc_read_untraced_slot"); -} - -uint8_t gc_read_untraced_byte(const struct object *obj, size_t byte_index) { - todo("gc_read_untraced_byte"); -} - -void gc_write_value_slot(struct object *obj, size_t slot_index, - struct value value) { - assume(slot_index < object_value_slots(obj)); - todo("gc_write_value_slot"); -} - -void gc_write_untraced_slot(struct object *obj, size_t slot_index, - uintptr_t value) { - assume(slot_index < object_untraced_slots(obj)); - todo("gc_write_untraced_slot"); -} - -void gc_write_untraced_byte(struct object *obj, size_t byte_index, - uint8_t byte) { - todo("gc_write_untraced_byte"); -} diff --git a/src/gc/gen3.c b/src/gc/gen3.c new file mode 100644 index 0000000..09fa452 --- /dev/null +++ b/src/gc/gen3.c @@ -0,0 +1,566 @@ +#include "../gc.h" +#include "../platform.h" +#include "../util.h" +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/** + * Constants that should probably be learned. + */ +static const size_t NURSERY_L1D_SIZE_FACTOR = 1; +static const size_t YOUNG_HEAP_L3_SIZE_FACTOR = 2; + +/** + * Objects each have a header, with a slightly different layout depending on + * which heap the object is in. Each header tracks the layout of the object + * itself, as well as some other properties, in a uniform way. via the + * `enum object_kind` and `struct object_size` types. + */ + +/** + * Gives special properties the object might have, as well as the interpretation + * of its size. + */ +enum object_kind { + /** + * A normal object. Has up to 2¹⁶ slots for values, and up to 2¹³ slots for + * untraced `uintptr_t`s (which may simply be used as bytes). + */ + OBJECT_NORMAL, + + /** + * An untraced object. Has up to 2²⁹ slots for untraced `uintptr_t`s (which + * may simply be used as bytes). + */ + OBJECT_UNTRACED, + + /** + * A wrapper for a pointer to a code address. When this object gets collected, + * calls `free_code` on its first untraced slot. + */ + OBJECT_COMPILED_FUNCTION, + + /** + * A hashtable keyed by the addresses. This behaves like a normal object, but + * the first untraced slot gets set to the `uintptr_t` 1 whenever a collection + * traces the hashtable. + * + * The hashtable uses this information to rehash after each collection. + */ + OBJECT_HASHTABLE_EQ, +}; + +/** + * A `size_t`-sized encoding of the object size. Also stores an extra bit used + * to indicate that the object has been moved in nursery collection, and that + * the object has been marked in old-heap collection. + */ +struct object_size { + enum object_kind kind : 2; + bool mark : 1; + size_t bits : (8 * sizeof(size_t)) - 3; +}; + +/** + * Returns the number of slots for values the object has. + */ +static size_t object_size_value_slots(const struct object_size size) { + switch (size.kind) { + case OBJECT_NORMAL: + case OBJECT_COMPILED_FUNCTION: + case OBJECT_HASHTABLE_EQ: + return size.bits >> ((4 * sizeof(size_t)) - 3); + case OBJECT_UNTRACED: + return 0; + } +} + +/** + * Returns the number of untraced slots the object has. + */ +static size_t object_size_untraced_slots(const struct object_size size) { + switch (size.kind) { + case OBJECT_NORMAL: + case OBJECT_COMPILED_FUNCTION: + case OBJECT_HASHTABLE_EQ: + return size.bits & ((1 << ((4 * sizeof(size_t)) - 3)) - 1); + case OBJECT_UNTRACED: + return size.bits; + } +} + +/** + * Returns the total number of slots the object has. + */ +static size_t object_size_total_slots(const struct object_size size) { + return object_size_value_slots(size) + object_size_untraced_slots(size); +} + +/** + * This struct is used as an opaque type for the fields of an object. + */ +struct object { + uintptr_t hd; + uintptr_t tl[]; +}; + +/** + * Returns the number of slots for values the object has. + */ +static size_t object_value_slots(const struct object *const obj) { + return object_size_value_slots(((const struct object_size *)obj)[-1]); +} + +/** + * Returns the number of untraced slots the object has. + */ +static size_t object_untraced_slots(const struct object *const obj) { + return object_size_untraced_slots(((const struct object_size *)obj)[-1]); +} + +/** + * Returns the total number of slots the object has. + */ +static size_t object_total_slots(const struct object *const obj) { + return object_value_slots(obj) + object_untraced_slots(obj); +} + +/** + * This is the layout of an object in the nursery. + */ +struct nursery_object { + struct object_size size; + uintptr_t slots[]; +}; + +/** + * This is the layout of an object in the young-heap. Because the young-heap is + * collected with mark-compact, it needs a dedicated forwarding pointer (or in + * our case, a forwarding offset) and can't simply overwrite the object slots + * with one. + */ +struct young_heap_object { + uintptr_t fwd; + struct object_size size; + uintptr_t slots[]; +}; + +/** + * This is the layout of an object in the old-heap. It matches the nursery + * layout at the moment. + */ +struct old_heap_object { + struct object_size size; + uintptr_t slots[]; +}; + +/** + * The nursery and young-heap each have a layout like: + * + * ┌──────────────┐ ←── Top ─┐ + * │remembered set│ │ + * ├──────────────┤ ←── Limit │ + * │ free │ │ + * │ space │ │ + * ├──────────────┤ ←── Next ├─ Size + * │ │ │ + * │ │ │ + * │ objects │ │ + * │ │ │ + * │ │ │ + * └──────────────┘ ←── Bottom ─┘ + * + * The layout of both regions are defined by the four labelled pointers, so we + * define them. + */ +static uintptr_t nursery_bottom, nursery_next, nursery_limit, nursery_top; +static uintptr_t young_heap_bottom, young_heap_next, young_heap_limit, + young_heap_top; +static size_t nursery_size, young_heap_size; +static size_t max_needed_young_heap_size_during_collection; + +/** + * The old-heap is composed of blocks, each of which are stored in an + * intrusive doubly linked list per size class. Size classes start at 8 bytes + * and go up to 64KiB, with a "large object" size class past that. For size + * classes up to and including 4KiB, blocks are 64KiB in size. Past that, blocks + * are sized to fit one object of the size class. + * + * Each block has a local free-list of objects of the size class. + */ +enum old_heap_size_class { + SIZE_8 = 0, + SIZE_16, + SIZE_32, + SIZE_64, + SIZE_128, + SIZE_256, + SIZE_512, + SIZE_1024, + SIZE_2048, + SIZE_4096, + SIZE_8192, + SIZE_16384, + SIZE_32768, + SIZE_65536, + SIZE_HUGE, + + SIZE_CLASS_COUNT, +}; + +struct old_heap_block { + struct old_heap_block *prev, *next; + struct old_heap_free_object *free_list; +}; + +struct old_heap_free_object { + struct old_heap_free_object *next; +}; + +static struct old_heap_block old_heap_sentinels[SIZE_CLASS_COUNT]; + +/** + * The root stack is an arbitrary 4KiB. It shouldn't get anywhere near this + * deep, so this is simply a convenient size. + */ +static struct value *root_stack[4096 / sizeof(uintptr_t)] = {0}; +static size_t root_stack_depth = 0; + +#include <stdarg.h> +static inline __attribute__((format(printf, 1, 2))) void +gc_debugf(const char *fmt, ...) { + va_list ap; + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + va_end(ap); +} + +void gc_init(void) { + // Allocate the nursery and young-heap. + nursery_size = get_l1d_size() * NURSERY_L1D_SIZE_FACTOR; + nursery_bottom = nursery_next = alloc_gc_region(nursery_size); + nursery_limit = nursery_top = nursery_bottom + nursery_size; + assume(nursery_bottom); + + young_heap_size = get_l3_size() * YOUNG_HEAP_L3_SIZE_FACTOR; + young_heap_bottom = young_heap_next = alloc_gc_region(young_heap_size); + young_heap_limit = young_heap_top = young_heap_bottom + young_heap_size; + assume(young_heap_bottom); + + // Compute how much space could be used when migrating the nursery to the + // young-heap, at a maximum. We collect the young-heap if its size gets below + // this. + max_needed_young_heap_size_during_collection = + (nursery_size * (sizeof(struct young_heap_object) + sizeof(uintptr_t))) / + (sizeof(struct nursery_object) + sizeof(uintptr_t)); + + // Self-link the old-heap. + for (size_t i = 0; i < SIZE_CLASS_COUNT; i++) { + old_heap_sentinels[i].prev = old_heap_sentinels[i].next = + &old_heap_sentinels[i]; + } +} + +static struct object *gc_alloc_in_nursery(const struct object_size object_size, + const size_t nursery_object_size) { + // Check if there's enough space in the nursery. + uintptr_t new_next = nursery_next + nursery_object_size; + if (new_next > nursery_limit) { + gc_collect_nursery(); + new_next = nursery_next + nursery_object_size; + assume(new_next <= nursery_limit); + } + + // Reserve the space. + struct nursery_object *obj = (struct nursery_object *)nursery_next; + nursery_next = new_next; + + // Hand the space back. + obj->size = object_size; + return (struct object *)&obj->slots[0]; +} + +static struct object * +gc_alloc_in_young_heap(const struct object_size object_size, + const size_t young_heap_object_size) { + todo("gc_alloc: young heap"); +} + +static struct object *gc_alloc_in_old_heap(const struct object_size object_size, + const size_t old_heap_object_size) { + todo("gc_alloc: old heap"); +} + +struct object *gc_alloc(const size_t value_slot_count, + const size_t untraced_slot_count) { + gc_debugf("gc_alloc(%zu, %zu) = ", value_slot_count, untraced_slot_count); + + // First, decide if this is an untraced object and check the object size. + const bool is_untraced = value_slot_count == 0; + if (is_untraced) { + assume(untraced_slot_count < (1 << 29)); + } else { + assume(value_slot_count < (1 << 16)); + assume(untraced_slot_count < (1 << 13)); + } + + // First, calculate the amount of space we'll need to store the object in the + // various heaps. + const size_t object_size_bytes = (value_slot_count * sizeof(struct value)) + + (untraced_slot_count * sizeof(uintptr_t)); + assume(object_size_bytes > 0); + const size_t nursery_object_size = + sizeof(struct nursery_object) + object_size_bytes, + young_heap_object_size = + sizeof(struct young_heap_object) + object_size_bytes, + old_heap_object_size = + sizeof(struct old_heap_object) + object_size_bytes; + + // Check whether the object is inherently too large, and should get allocated + // directly into another heap. + const bool nursery_fits = nursery_object_size <= nursery_size, + young_heap_fits = young_heap_object_size <= young_heap_size; + + // Construct the object size. This is common to all the headers, so why not. + const struct object_size object_size = { + .kind = is_untraced ? OBJECT_UNTRACED : OBJECT_NORMAL, + .mark = false, + .bits = is_untraced ? untraced_slot_count + : (value_slot_count << ((4 * sizeof(size_t)) - 3)) | + untraced_slot_count, + }; + assume(object_size_value_slots(object_size) == value_slot_count); + assume(object_size_untraced_slots(object_size) == untraced_slot_count); + + // Everything above this line should get inlined and constant-folded. + struct object *obj = + nursery_fits ? gc_alloc_in_nursery(object_size, nursery_object_size) + : young_heap_fits + ? gc_alloc_in_young_heap(object_size, young_heap_object_size) + : gc_alloc_in_old_heap(object_size, old_heap_object_size); + memset(obj, 0, object_value_slots(obj) * sizeof(uintptr_t)); + gc_debugf("%p\n", (void *)obj); + return obj; +} + +struct object *gc_alloc_compiled_function(size_t value_slot_count, + size_t untraced_slot_count) { + todo("gc_alloc_compiled_function"); +} + +struct object *gc_alloc_hashtable_eq(size_t value_slot_count, + size_t untraced_slot_count) { + todo("gc_alloc_hashtable_eq"); +} + +/** + * Relocates the pointer in the slot, if necessary. Returns whether it did + * (i.e., whether the pointer was a nursery pointer). + */ +static bool gc_collect_nursery_relocate(struct value *slot) { + gc_debugf("gc_collect_nursery_relocate(%p): %p -", slot, (void *)slot->bits); + char relocation_type = 'x'; + struct value old_value = *slot; + + // Check if the value was a pointer. If not, we don't need to relocate it. + if (!is_ptr(old_value)) + goto out; + + // Check if the object is in the nursery. If not, we don't need to relocate + // it. + struct object *old_obj = untag_ptr(old_value); + if (!(nursery_bottom <= (uintptr_t)old_obj && + (uintptr_t)old_obj <= nursery_top)) + goto out; + + // Check if the object has already been relocated. + struct nursery_object *old_header = + (struct nursery_object *)((uintptr_t)old_obj - + sizeof(struct nursery_object)); + struct object *new_obj; + if (old_header->size.mark) { + new_obj = (struct object *)old_header->slots[0]; + relocation_type = 'o'; + } else { + // Allocate a new object in the young-heap. + assume(young_heap_next < young_heap_limit); + assume((young_heap_next & 0b111) == 0); + struct young_heap_object *new_header = + (struct young_heap_object *)young_heap_next; + new_obj = (struct object *)&new_header->slots[0]; + size_t total_slots = object_size_total_slots(old_header->size); + assume(total_slots > 0); + uintptr_t new_next = (uintptr_t)&new_header->slots[total_slots]; + assume(new_next < young_heap_limit); + young_heap_next = new_next; + gc_debugf("{%p - %p (%zu)}", &old_header->slots[0], + &old_header->slots[total_slots], total_slots); + + // Copy the object. + new_header->size = old_header->size; + memcpy(new_obj, old_obj, total_slots * sizeof(uintptr_t)); + + // Mark the object as relocated. + old_header->size.mark = true; + old_header->slots[0] = (uintptr_t)new_obj; + + // Update the relocation flag. + relocation_type = '>'; + } + *slot = tag_ptr(new_obj, get_tag(old_value)); + +out: + gc_debugf("%c %p\n", relocation_type, (void *)slot->bits); + return relocation_type != 'x'; +} + +void gc_collect_nursery(void) { + gc_debugf("--- gc ---\n"); + + // Check that there's enough space in the young-heap. + assume(max_needed_young_heap_size_during_collection < + (young_heap_limit - young_heap_next)); + + // Keep a "finger" at the point at which we've started relocating objects. + uintptr_t finger = young_heap_next; + + // Relocate the roots. + for (size_t i = 0; i < root_stack_depth; i++) + gc_collect_nursery_relocate(root_stack[i]); + + // Relocate or promote fields of the remembered set. + while (nursery_limit != nursery_top) { + struct value *slot = *(struct value **)nursery_limit; + nursery_limit += sizeof(struct value *); + + // If the slot was in a nursery object, ignore it. + if (nursery_bottom <= (uintptr_t)slot && (uintptr_t)slot <= nursery_top) + continue; + + // If the slot didn't contain a pointer, ignore it. + if (!is_ptr(*slot)) + continue; + struct object *ptr = untag_ptr(*slot); + + // If the slot pointed to a nursery object, relocate it. + if (nursery_bottom <= (uintptr_t)ptr && (uintptr_t)ptr <= nursery_top) { + gc_collect_nursery_relocate(slot); + continue; + } + + // If the slot was in the young-set but did not point to the nursery set, we + // don't care about it either. + if (young_heap_bottom <= (uintptr_t)slot && + (uintptr_t)slot <= young_heap_top) + continue; + + // TODO: Remembered set + todo("relocate remembered set"); + } + + // Walk the objects we just moved to the young-heap, relocating their fields. + while (finger < young_heap_next) { + // Relocate any fields. + struct young_heap_object *header = (struct young_heap_object *)finger; + size_t value_slot_count = object_size_value_slots(header->size); + for (size_t i = 0; i < value_slot_count; i++) + gc_collect_nursery_relocate((struct value *)&header->slots[i]); + + // Advance the finger. + size_t total_slot_count = object_size_total_slots(header->size); + finger = (uintptr_t)&header->slots[total_slot_count]; + } + + // Reset the nursery's pointers. + nursery_next = nursery_bottom; + assume(nursery_limit == nursery_top); + + // Clear the nursery's memory. + clear_gc_region(nursery_bottom, nursery_size); +} + +void gc_collect_young_heap(void) { todo("gc_collect_young_heap"); } + +void gc_collect_old_heap(void) { todo("gc_collect_old_heap"); } + +struct value gc_read_value_slot(const struct object *obj, size_t slot_index) { + gc_debugf("gc_read_value_slot(%p, %zu) = ", obj, slot_index); + assume(slot_index < object_value_slots(obj)); + struct value *slots = (struct value *)obj; + struct value value = slots[slot_index]; + gc_debugf("%p\n", (void *)value.bits); + return value; +} + +uintptr_t gc_read_untraced_slot(const struct object *obj, size_t slot_index) { + assume(slot_index < object_untraced_slots(obj)); + todo("gc_read_untraced_slot"); +} + +uint8_t gc_read_untraced_byte(const struct object *obj, size_t byte_index) { + todo("gc_read_untraced_byte"); +} + +void gc_write_value_slot(struct object *obj, size_t slot_index, + struct value value) { + gc_debugf("gc_write_value_slot(%p, %zu, %p)\n", obj, slot_index, + (void *)value.bits); + gc_debugf(" object_value_slots = %zu\n", object_value_slots(obj)); + gc_debugf(" object_untraced_slots = %zu\n", object_untraced_slots(obj)); + assume(slot_index < object_value_slots(obj)); + if (nursery_next == nursery_limit) { + gc_root_push(&obj); + if (!(value.bits & 1)) + gc_root_push(&value); + gc_collect_nursery(); + if (!(value.bits & 1)) + gc_root_pop(); + gc_root_pop(); + } + + nursery_limit -= sizeof(uintptr_t); + uintptr_t **remembered_set = (uintptr_t **)nursery_limit; + *remembered_set = (uintptr_t *)obj + slot_index * sizeof(uintptr_t); + + struct value *slots = (struct value *)obj; + slots[slot_index] = value; +} + +void gc_write_untraced_slot(struct object *obj, size_t slot_index, + uintptr_t value) { + assume(slot_index < object_untraced_slots(obj)); + todo("gc_write_untraced_slot"); +} + +void gc_write_untraced_byte(struct object *obj, size_t byte_index, + uint8_t byte) { + todo("gc_write_untraced_byte"); +} + +void gc_root_push(struct value *root) { + assume(root_stack_depth < sizeof(root_stack)); + root_stack[root_stack_depth++] = root; +} + +void gc_root_pop(void) { + assume(root_stack_depth > 0); + root_stack_depth--; +} + +void gc_debug(void) { + fprintf(stderr, "nursery size: %#zx\n", nursery_size); + fprintf(stderr, "nursery top: %p\n", (void *)nursery_top); + fprintf(stderr, "nursery limit: %p\n", (void *)nursery_limit); + fprintf(stderr, "nursery next: %p\n", (void *)nursery_next); + fprintf(stderr, "nursery bottom: %p\n", (void *)nursery_bottom); + fprintf(stderr, "\n"); + fprintf(stderr, "young-heap size: %#zx\n", young_heap_size); + fprintf(stderr, "young-heap top: %p\n", (void *)young_heap_top); + fprintf(stderr, "young-heap limit: %p\n", (void *)young_heap_limit); + fprintf(stderr, "young-heap next: %p\n", (void *)young_heap_next); + fprintf(stderr, "young-heap bottom: %p\n", (void *)young_heap_bottom); +} diff --git a/src/gc/sms.c b/src/gc/sms.c new file mode 100644 index 0000000..dcee0c1 --- /dev/null +++ b/src/gc/sms.c @@ -0,0 +1,205 @@ +#include "../gc.h" +#include "../util.h" +#include <inttypes.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +struct object_header { + bool mark : 1; + bool is_compiled_function : 1; + int rsvd : 1; + uint16_t untraced_slot_count : 13; + uint16_t value_slot_count; + struct object_header *next; + uintptr_t slots[]; +}; + +/** + * A singly-linked list of live objects. + */ +static struct object_header *live_objects = NULL; + +/** + * The number of bytes of live data, including object headers. + */ +static size_t live_bytes = 0; + +/** + * The number of bytes of live data to reach before collecting. + */ +static size_t limit_bytes = 80 * 1024 * 1024; + +/** + * The root stack is an arbitrary 4KiB. It shouldn't get anywhere near this + * deep, so this is simply a convenient size. + */ +static struct value *root_stack[4096 / sizeof(uintptr_t)] = {0}; +static size_t root_stack_depth = 0; + +static struct object_header *hdr(void *ptr) { + return &((struct object_header *)ptr)[-1]; +} + +static const struct object_header *hdrc(const void *ptr) { + return &((const struct object_header *)ptr)[-1]; +} + +void gc_init(void) {} + +static void gc_mark(const struct value initial_value) { + // If the initial value just wasn't a pointer, we don't need to mark it. + if (!is_ptr(initial_value)) + return; + struct object *obj = untag_ptr(initial_value); + if (!obj) + return; + + // Otherwise, we do a traversal starting at the value, doing pointer reversal + // to avoid recursion. + // + // In simple recursive marking, we store where we came from in the call + // stack. Each stack frame effectively stores: + // + // 1. the pointer to the object we came from + // 2. the index of the slot we came from in that object + // + // In pointer reversal, instead of using that space, we store where we came + // from in the previous object itself. This relies on having the + // TAG_GC_INTERNAL tag. + struct object *prev = NULL; + while (obj) { + // Check if the object has already been marked. If so, we don't need to + // traverse it. + struct object_header *header = hdr(obj); + if (!header->mark) { + // Invariant: We've just started traversing this object, so none of its + // fields should have TAG_GC_INTERNAL. + + // Check the object's fields, looking for one that + + todo("gc_mark 1"); + } + todo("gc_mark 2"); + } + + /* + struct object_header *header = hdr(obj); + if (header->mark) + return; + header->mark = true; + struct value *slots = (struct value *)&header->slots[0]; + for (size_t i = 0; i < header->value_slot_count; i++) + gc_mark(slots[i]); + */ +} + +static void gc_sweep(void) { + struct object_header **head = &live_objects, *header; + while ((header = *head)) { + if ((*head)->mark) { + (*head)->mark = false; + head = &header->next; + } else { + *head = header->next; + const size_t total_bytes = + sizeof(struct object_header) + + (header->value_slot_count + header->untraced_slot_count) * + sizeof(uintptr_t); + free(header); + live_bytes -= total_bytes; + } + } +} + +void gc_collect(void) { + fprintf(stderr, "gc_collect()... "); + for (size_t i = 0; i < root_stack_depth; i++) + gc_mark(*root_stack[i]); + const size_t before = live_bytes; + gc_sweep(); + const size_t after = live_bytes; + fprintf(stderr, "collected %zu bytes\n", before - after); + assume(live_bytes < limit_bytes); +} + +struct object *gc_alloc(size_t value_slot_count, size_t untraced_slot_count) { + assume(value_slot_count < (1 << 16)); + assume(untraced_slot_count < (1 << 13)); + + const size_t total_bytes = + sizeof(struct object_header) + + (value_slot_count + untraced_slot_count) * sizeof(uintptr_t); + if ((live_bytes += total_bytes) >= limit_bytes) + gc_collect(); + struct object_header *header = malloc(total_bytes); + if (!header) { + gc_collect(); + header = malloc(total_bytes); + if (!header) + todo("OOM"); + } + memset(header, 0, total_bytes); + header->value_slot_count = value_slot_count; + header->untraced_slot_count = untraced_slot_count; + header->next = live_objects; + live_objects = header; + return (struct object *)&header->slots[0]; +} + +struct object *gc_alloc_compiled_function(size_t value_slot_count, + size_t untraced_slot_count) { + struct object *obj = gc_alloc(value_slot_count, untraced_slot_count); + hdr(obj)->is_compiled_function = true; + return obj; +} + +struct object *gc_alloc_hashtable_eq(size_t value_slot_count, + size_t untraced_slot_count) { + return gc_alloc(value_slot_count, untraced_slot_count); +} + +struct value gc_read_value_slot(const struct object *obj, size_t slot_index) { + assume(slot_index < hdrc(obj)->value_slot_count); + struct value *slots = (struct value *)obj; + struct value value = slots[slot_index]; + return value; +} + +uintptr_t gc_read_untraced_slot(const struct object *obj, size_t slot_index) { + assume(slot_index < hdrc(obj)->untraced_slot_count); + todo("gc_read_untraced_slot"); +} + +uint8_t gc_read_untraced_byte(const struct object *obj, size_t byte_index) { + todo("gc_read_untraced_byte"); +} + +void gc_write_value_slot(struct object *obj, size_t slot_index, + struct value value) { + struct value *slots = (struct value *)obj; + slots[slot_index] = value; +} + +void gc_write_untraced_slot(struct object *obj, size_t slot_index, + uintptr_t value) { + assume(slot_index < hdrc(obj)->untraced_slot_count); + todo("gc_write_untraced_slot"); +} + +void gc_write_untraced_byte(struct object *obj, size_t byte_index, + uint8_t byte) { + todo("gc_write_untraced_byte"); +} + +void gc_root_push(struct value *root) { + assume(root_stack_depth < sizeof(root_stack)); + root_stack[root_stack_depth++] = root; +} + +void gc_root_pop(void) { + assume(root_stack_depth > 0); + root_stack_depth--; +} + +void gc_debug(void) { fprintf(stderr, "live bytes = %zu\n", live_bytes); } diff --git a/src/main.c b/src/main.c deleted file mode 100644 index 2f6fcf2..0000000 --- a/src/main.c +++ /dev/null @@ -1,6 +0,0 @@ -#include "gc.h" -#include "util.h" - -int main(int argc, char **argv) { - return 0; -} diff --git a/src/platform.h b/src/platform.h index 2dbfd26..0bb6bbe 100644 --- a/src/platform.h +++ b/src/platform.h @@ -2,11 +2,15 @@ #define IMB3_PLATFORM_H #include <stddef.h> +#include <stdint.h> #include <stdnoreturn.h> size_t get_l1d_size(void); size_t get_l3_size(void); +uintptr_t alloc_gc_region(size_t); +void clear_gc_region(uintptr_t, size_t); + void panic_begin(void); noreturn void panic_end(void); diff --git a/src/platform/3ds.c b/src/platform/3ds.c index 5683422..5566121 100644 --- a/src/platform/3ds.c +++ b/src/platform/3ds.c @@ -6,6 +6,7 @@ #include <inttypes.h> #include <stdio.h> #include <stdlib.h> +#include <string.h> /** * These cache-size details are from @@ -16,6 +17,16 @@ size_t get_l1d_size(void) { return 16 * 1024; } size_t get_l3_size(void) { return 2 * 1024 * 1024; } +uintptr_t alloc_gc_region(size_t size) { + void *ptr = malloc(size); + assume(ptr != NULL); + return (uintptr_t)ptr; +} + +void clear_gc_region(uintptr_t addr, size_t size) { + memset((void *)addr, 0, size); +} + void panic_begin(void) { consoleInit(GFX_TOP, NULL); } noreturn void panic_end(void) { @@ -35,6 +46,51 @@ noreturn void panic_end(void) { exit(1); } +static void gc_test(void) { + gc_debug(); + + const struct value ZERO = {.bits = (0 << 2) | TAG_FIXNUM}; + + struct object *values = gc_alloc(64, 0); + struct object *value_slot_counts = gc_alloc(64, 0); + gc_root_push(&values); + gc_root_push(&value_slot_counts); + + for (size_t i = 0; i < 10000000; i++) { + if ((rand() & 0b11) == 0) { + size_t value_slot_count = rand() & 63; + if (!value_slot_count) + value_slot_count = 1; + size_t untraced_slot_count = rand() & 63; + struct value value = + alloc_builtin_object(ZERO, value_slot_count, untraced_slot_count); + size_t i = rand() % 63; + gc_write_value_slot(values, i, value); + gc_write_value_slot(value_slot_counts, i, + integer_of_int(value_slot_count)); + } else { + size_t i = rand() & 63; + struct value value = gc_read_value_slot(values, i); + struct value value_slot_count_value = + gc_read_value_slot(value_slot_counts, i); + if (!value.bits) + continue; + assume(get_tag(value) == TAG_BUILTIN_OBJECT); + assume(get_tag(value_slot_count_value) == TAG_FIXNUM); + struct object *obj = untag_ptr(value); + intptr_t value_slot_count = untag_fixnum(value_slot_count_value); + size_t j = rand() % value_slot_count; + size_t k = rand() % 63; + gc_write_value_slot(obj, j, gc_read_value_slot(values, k)); + } + } + + gc_root_pop(); + gc_root_pop(); + + gc_debug(); +} + int main(int argc, char **argv) { gfxInit(GSP_BGR8_OES, GSP_BGR8_OES, false); @@ -66,7 +122,7 @@ int main(int argc, char **argv) { if (kDown & KEY_START) break; // break in order to return to hbmenu if (kDown & KEY_A) - todo("GM"); + gc_test(); circlePosition pos; hidCircleRead(&pos); diff --git a/src/platform/3ds.mk b/src/platform/3ds.mk index cbe7e0b..0b0d2f2 100644 --- a/src/platform/3ds.mk +++ b/src/platform/3ds.mk @@ -15,4 +15,4 @@ all: imb3.3dsx .PHONY: 3dslink imb3.3dsx: imb3.elf - 3dsxtool $< $@ + $(DEVKITPRO)/../../bin/3dsxtool $< $@ diff --git a/src/platform/linux.c b/src/platform/linux.c index e69de29..3305869 100644 --- a/src/platform/linux.c +++ b/src/platform/linux.c @@ -0,0 +1,158 @@ +#define _GNU_SOURCE +#include "../gc.h" +#include "../platform.h" +#include "../util.h" +#include <errno.h> +#include <fcntl.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/mman.h> +#include <unistd.h> + +int main(int argc, char **argv) { + // As a test of the garbage collector, we're doing a bunch of random + // mutations. + gc_init(); + srand(0); + gc_debug(); + + const struct value ZERO = {.bits = (0 << 2) | TAG_FIXNUM}; + + struct object *values = gc_alloc(64, 0); + struct object *value_slot_counts = gc_alloc(64, 0); + gc_root_push(&values); + gc_root_push(&value_slot_counts); + + for (size_t i = 0; i < 1000000; i++) { + if ((rand() & 0b11) == 0) { + size_t value_slot_count = 3; + if (!value_slot_count) + value_slot_count = 1; + size_t untraced_slot_count = rand() & 255; + struct value value = + alloc_builtin_object(ZERO, value_slot_count, untraced_slot_count); + size_t i = rand() % 63; + gc_write_value_slot(values, i, value); + gc_write_value_slot(value_slot_counts, i, + integer_of_int(value_slot_count)); + } else { + size_t i = rand() & 63; + struct value value = gc_read_value_slot(values, i); + struct value value_slot_count_value = + gc_read_value_slot(value_slot_counts, i); + if (!value.bits) + continue; + assume(get_tag(value) == TAG_BUILTIN_OBJECT); + assume(get_tag(value_slot_count_value) == TAG_FIXNUM); + struct object *obj = untag_ptr(value); + intptr_t value_slot_count = untag_fixnum(value_slot_count_value); + size_t j = rand() % value_slot_count; + size_t k = rand() % 63; + gc_write_value_slot(obj, j, gc_read_value_slot(values, k)); + } + } + + gc_debug(); + return 0; +} + +void panic_begin(void) {} +noreturn void panic_end(void) { abort(); } + +static size_t read_cache_size(const char *path) { + int fd = open(path, O_RDONLY | O_CLOEXEC); + if (fd == -1) + fprintf(stderr, "open %s: %s\n", path, strerror(errno)), abort(); + + char buf[4096]; + size_t len = 0; + for (;;) { + ssize_t ret = read(fd, &buf[len], sizeof(buf) - len); + if (ret == 0) + break; + else if (ret < 0 && errno == EINTR) + continue; + else if (ret < 0) + fprintf(stderr, "read %s: %s\n", path, strerror(errno)), abort(); + else + len += ret; + } + + if (close(fd)) + fprintf(stderr, "close %s: %s\n", path, strerror(errno)), abort(); + + size_t i = 0, out = 0; + while (i < len) { + char ch = buf[i]; + if ('0' <= ch && ch <= '9') { + out = 10 * out + (ch - '0'); + i++; + } else { + break; + } + } + if (i < len) { + char ch = buf[i]; + if (ch == 'K') { + out *= 1024; + i++; + } else if (ch == 'M') { + out *= 1024 * 1024; + i++; + } + } + if (i < len && buf[i] == '\n') + i++; + if (i != len) { + fprintf(stderr, "invalid cache size in %s: [", path); + for (size_t j = 0; j < len; j++) { + fprintf(stderr, "%s", i == j ? "|" : j ? " " : ""); + char ch = buf[j]; + if (' ' <= ch && ch <= '~' && ch != '\'' && ch != '\\') + fprintf(stderr, "'%c'", ch); + else if (ch == '\n') + fprintf(stderr, "'\\n'"); + else if (ch == '\'') + fprintf(stderr, "\"'\""); + else if (ch == '\\') + fprintf(stderr, "'\\\\'"); + else + fprintf(stderr, "%02hhx", buf[j]); + } + fprintf(stderr, "]\n"); + abort(); + } + + return out; +} + +size_t get_l1d_size(void) { + return read_cache_size("/sys/devices/system/cpu/cpu0/cache/index0/size"); +} + +size_t get_l3_size(void) { + return read_cache_size("/sys/devices/system/cpu/cpu0/cache/index2/size"); +} + +uintptr_t alloc_gc_region(size_t size) { + static uintptr_t base_ptr = 0x10000; + static size_t page_size = 0; + if (!page_size) + page_size = sysconf(_SC_PAGE_SIZE); + + void *ptr = mmap((void *)base_ptr, size, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); + if (ptr == MAP_FAILED) + perror("alloc_gc_region"), exit(111); + base_ptr = + (((uintptr_t)ptr + size + page_size - 1) & ~(page_size - 1)) + page_size; + return (uintptr_t)ptr; +} + +void clear_gc_region(uintptr_t addr, size_t size) { + void *new_ptr = mmap((void *)addr, size, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, 0); + if (new_ptr == MAP_FAILED) + perror("clear_gc_region"), exit(111); +} @@ -1,11 +1,13 @@ #include "util.h" +#include "gc.h" #include "platform.h" #include <stdarg.h> #include <stdio.h> noreturn void assume__failed(const char *file, int line, const char *expr) { panic_begin(); - fprintf(stderr, "%s:%d: assertion failed: %s\n", file, line, expr); + fprintf(stderr, "%s:%d: assertion failed: %s\n\n", file, line, expr); + gc_debug(); panic_end(); } @@ -16,5 +18,20 @@ noreturn void todo__impl(const char *file, int line, const char *fmt, ...) { va_start(ap, fmt); vprintf(fmt, ap); va_end(ap); + printf("\n"); + gc_debug(); + panic_end(); +} + +noreturn void unreachable__impl(const char *file, int line, const char *fmt, + ...) { + panic_begin(); + printf("%s:%d: unreachable code entered: ", file, line); + va_list ap; + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + printf("\n"); + gc_debug(); panic_end(); } @@ -28,4 +28,9 @@ todo__impl(const char *file, int line, const char *fmt, ...); #define todo(...) todo__impl(__FILE__, __LINE__, __VA_ARGS__) +__attribute__((format(printf, 3, 4))) noreturn void +unreachable__impl(const char *file, int line, const char *fmt, ...); + +#define unreachable(...) unreachable__impl(__FILE__, __LINE__, __VA_ARGS__) + #endif // IMB3_UTIL_H diff --git a/src/value.c b/src/value.c index 07af689..b4e22a9 100644 --- a/src/value.c +++ b/src/value.c @@ -1,5 +1,11 @@ #include "value.h" #include "gc.h" +#include "util.h" +#include <inttypes.h> + +static const intptr_t FIXNUM_MIN = -((intptr_t)1 << (4 * sizeof(void *) - 3)), + FIXNUM_MAX = + ((intptr_t)1 << (4 * sizeof(void *) - 3)) - 1; enum builtin { BUILTIN_BUILTIN_CLASS_BIGNUM, @@ -83,6 +89,8 @@ static struct value pop(void) { return (struct value){.bits = 0}; } struct value alloc_builtin_object(struct value class, size_t value_slot_count, size_t untraced_slot_count) { + assume(value_slot_count != 0); + struct object *obj; if (class.bits == builtins[BUILTIN_BUILTIN_CLASS_COMPILED_FUNCTION].bits) obj = gc_alloc_compiled_function(value_slot_count, untraced_slot_count); @@ -96,6 +104,51 @@ struct value alloc_builtin_object(struct value class, size_t value_slot_count, }; } +struct value integer_of_int(intptr_t n) { + if (FIXNUM_MIN <= n && n <= FIXNUM_MAX) { + struct value value = (struct value){.bits = (n << 2) | TAG_FIXNUM}; + assume(untag_fixnum(value) == n); + return value; + } else { + todo("integer_of_int: bigint %" PRIdPTR, n); + } +} + +enum value_tag get_tag(struct value value) { + uintptr_t low_bits = value.bits & 0b111; + switch (low_bits) { + case 0b000: + case 0b010: + case 0b100: + case 0b110: + return (enum value_tag)low_bits; + case 0b001: + case 0b101: + return TAG_FIXNUM; + default: + unreachable("invalid tag for value %p", (void *)value.bits); + } +} + +bool is_ptr(struct value value) { return !(value.bits & 1); } + +struct value tag_ptr(struct object *obj, enum value_tag tag) { + assume((tag & 0b1) == 0); + assume(((uintptr_t)obj & 0b111) == 0); + return (struct value){.bits = (uintptr_t)obj | tag}; +} + +intptr_t untag_fixnum(struct value value) { + assume(get_tag(value) == TAG_FIXNUM); + intptr_t bits = value.bits; + return bits >> 2; +} + +struct object *untag_ptr(struct value value) { + assume(is_ptr(value)); + return (struct object *)((uintptr_t)value.bits & ~0b111); +} + void bootstrap(void) { // Since it is its own class, standard-class needs to be constructed // manually. diff --git a/src/value.h b/src/value.h index 3795486..1331d9d 100644 --- a/src/value.h +++ b/src/value.h @@ -1,9 +1,15 @@ #ifndef IMB3_VALUE_H #define IMB3_VALUE_H +#include <stdbool.h> #include <stddef.h> #include <stdint.h> +/** + * Declared "for real" in gc.h. + */ +struct object; + struct value { uintptr_t bits; }; @@ -18,7 +24,7 @@ enum value_tag { * Fixnums, i.e. integers that are stored directly in the value rather than * being pointed to. This is a two-bit tag rather than a three-bit tag... */ - VALUE_FIXNUM = 0b01, + TAG_FIXNUM = 0b01, /** * A builtin-object. @@ -34,13 +40,54 @@ enum value_tag { * A standard-object, effectively a pair of a class and a slot array. */ TAG_STANDARD_OBJECT = 0b110, + + /** + * An tag that is _invalid_ for values, but may be used by the internals of + * the garbage collector. + */ + TAG_GC_INTERNAL = 0b111, }; /** + * The nil constant. + */ +static const struct value NIL = {.bits = 0}; + +/** * Allocates a builtin-object with the given class and slot count. */ -struct value make_builtin_object(struct value class, size_t value_slot_count, - size_t untraced_slot_count); +struct value alloc_builtin_object(struct value class, size_t value_slot_count, + size_t untraced_slot_count); + +/** + * Stores an intptr_t as a fixnum or a bignum. + */ +struct value integer_of_int(intptr_t); + +/** + * Returns the tag of a value. + */ +enum value_tag get_tag(struct value); + +/** + * Returns whether a value is a pointer. + */ +bool is_ptr(struct value); + +/** + * Tags a pointer. + */ +struct value tag_ptr(struct object *, enum value_tag); + +/** + * Untags a fixnum. + */ +intptr_t untag_fixnum(struct value); + +/** + * Untags a pointer. + */ +struct object *untag_ptr(struct value); /** * Bootstraps the class heirarchy. This should only be called once. |