From 57331ba9756df043b5c665aa4952a0a7b38799e5 Mon Sep 17 00:00:00 2001 From: Nathan Ringo Date: Sat, 16 Nov 2024 12:38:37 -0600 Subject: Initial commit --- src/Makefile | 61 ++++++++++++++++ src/gc.h | 18 +++++ src/gc/gc-debug.c | 0 src/gc/gc.c | 213 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/main.c | 65 +++++++++++++++++ src/util.c | 51 +++++++++++++ src/util.h | 31 ++++++++ src/value.c | 1 + src/value.h | 38 ++++++++++ 9 files changed, 478 insertions(+) create mode 100644 src/Makefile create mode 100644 src/gc.h create mode 100644 src/gc/gc-debug.c create mode 100644 src/gc/gc.c create mode 100644 src/main.c create mode 100644 src/util.c create mode 100644 src/util.h create mode 100644 src/value.c create mode 100644 src/value.h (limited to 'src') diff --git a/src/Makefile b/src/Makefile new file mode 100644 index 0000000..432b331 --- /dev/null +++ b/src/Makefile @@ -0,0 +1,61 @@ +ifeq ($(strip $(DEVKITPRO)),) +$(error "Please set DEVKITPRO in your environment. export DEVKITPRO=devkitPRO") +endif + +SRCS = $(sort $(wildcard $(srcdir)/*.c)) +OBJS = $(patsubst $(srcdir)/%.c,obj/%.o,$(SRCS)) +DEPS = $(patsubst $(srcdir)/%.c,obj/%.d,$(SRCS)) + +CFLAGS = +CPPFLAGS = +LDFLAGS = + +CC = $(DEVKITPRO)/devkitARM/bin/arm-none-eabi-gcc + +CFLAGS_AUTO = -D__3DS__ -ffunction-sections -flto -g -march=armv6k -mtune=mpcore -mfloat-abi=hard -mtp=soft -mword-relocations -Og -std=c11 -Wall -Werror=implicit-function-declaration +LDFLAGS_AUTO = -L$(DEVKITPRO)/libctru/lib -specs=3dsx.specs +LDLIBS_AUTO = -lctru -lm + +CFLAGS_ALL = $(CPPFLAGS) $(CFLAGS_AUTO) $(CFLAGS) +LDFLAGS_ALL = $(LDFLAGS_AUTO) $(LDFLAGS) +LDLIBS_ALL = $(LDLIBS_AUTO) $(LDLIBS) + +-include config.mak + +ifeq ($(CONFIGURED),) + +all: + @printf >&2 'Please run mk.sh, not make.\n' + @exit 1 + +else + +all: imb3.3dsx +3dslink: imb3.3dsx + $(DEVKITPRO)/tools/bin/3dslink $< +.PHONY: 3dslink + +imb3.3dsx: imb3.elf + 3dsxtool $< $@ + +imb3.elf: $(OBJS) obj/gc/gc.o + $(CC) $(CFLAGS_ALL) $(LDFLAGS_ALL) -o $@ $^ $(LDLIBS_ALL) +imb3-debug.elf: $(OBJS) obj/gc/gc-debug.o + $(CC) $(CFLAGS_ALL) $(LDFLAGS_ALL) -o $@ $^ $(LDLIBS_ALL) + +obj/%.o: $(srcdir)/%.c + @mkdir -p $(dir $@) + $(CC) $(CFLAGS_ALL) -c -o $@ $< + +# https://www.gnu.org/software/make/manual/html_node/Automatic-Prerequisites.html +obj/%.d: $(srcdir)/%.c + @mkdir -p obj + @set -e; rm -f $@; \ + $(CC) -M $(CPPFLAGS) $< > $@.$$$$; \ + sed 's,\($*\)\.o[ :]*,obj/\1.o $@ : ,g' < $@.$$$$ > $@; \ + rm -f $@.$$$$ +include $(DEPS) + +endif + +.PHONY: all diff --git a/src/gc.h b/src/gc.h new file mode 100644 index 0000000..dff3b79 --- /dev/null +++ b/src/gc.h @@ -0,0 +1,18 @@ +#ifndef IMB3_GC_H +#define IMB3_GC_H + +#include "value.h" +#include + +void gc_init(void); +void gc_collect(void); + +struct object; +struct value gc_read_value_slot(struct object *, size_t); +uintptr_t gc_read_untraced_slot(struct object *, size_t); +uint8_t gc_read_untraced_byte(struct object *, size_t); +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); + +#endif // IMB3_GC_H diff --git a/src/gc/gc-debug.c b/src/gc/gc-debug.c new file mode 100644 index 0000000..e69de29 diff --git a/src/gc/gc.c b/src/gc/gc.c new file mode 100644 index 0000000..f53fd79 --- /dev/null +++ b/src/gc/gc.c @@ -0,0 +1,213 @@ +#include "../util.h" +#include +#include +#include +#include + +/** + * These cache-size details are from + * https://www.copetti.org/writings/consoles/nintendo-3ds/. We call the second + * level of cache (only available on N3DS) L3, since this GC design only cares + * about L1D and L3. + */ +static const size_t L1D_SIZE = 16 * 1024, L3_SIZE = 2 * 1024 * 1024; + +/** + * 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 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_EQ_HASHTABLE, + + /** + * 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 `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_value_slots(struct object_size size) { + switch (size.kind) { + case OBJECT_NORMAL: + case OBJECT_EQ_HASHTABLE: + case OBJECT_COMPILED_FUNCTION: + 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_untraced_slots(struct object_size size) { + switch (size.kind) { + case OBJECT_NORMAL: + case OBJECT_EQ_HASHTABLE: + case OBJECT_COMPILED_FUNCTION: + 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[]; +}; + +/** + * 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 { + struct object_size size; + size_t fwd; + 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(L1D_SIZE * NURSERY_L1D_SIZE_FACTOR); + assume(nursery_bottom); + young_heap_bottom = young_heap_next = + (uintptr_t)malloc(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]; + } +} diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..c8a1115 --- /dev/null +++ b/src/main.c @@ -0,0 +1,65 @@ +#include "gc.h" +#include "util.h" +#include <3ds.h> +#include +#include + +int main(int argc, char **argv) { + gfxInit(GSP_BGR8_OES, GSP_BGR8_OES, false); + + // Initialize console on top screen. Using NULL as the second argument tells + // the console library to use the internal console structure as current one + consoleInit(GFX_TOP, NULL); + + // Move the cursor to row 15 and column 19 and then prints "Hello World!" + // To move the cursor you have to print "\x1b[r;cH", where r and c are + // respectively the row and column where you want your cursor to move The top + // screen has 30 rows and 50 columns The bottom screen has 30 rows and 40 + // columns + printf("\x1b[16;20HHello World!"); + + printf("\x1b[29;16HPress Start to exit.\n"); + + gc_init(); + + // Main loop + while (aptMainLoop()) { + // Scan all the inputs. This should be done once for each frame + hidScanInput(); + + // hidKeysDown returns information about which buttons have been just + // pressed (and they weren't in the previous frame) + u32 kDown = hidKeysDown(); + + if (kDown & KEY_START) + break; // break in order to return to hbmenu + if (kDown & KEY_A) + todo("GM"); + + circlePosition pos; + hidCircleRead(&pos); + printf("\x1b[0;0H\x1b[K(%" PRId16 ", %" PRId16 ")\n", pos.dx, pos.dy); + + // Get the bottom screen's frame buffer + u16 w, h; + u8 *fb = gfxGetFramebuffer(GFX_BOTTOM, GFX_LEFT, &w, &h); + + for (u16 j = 0; j < h; j++) { + for (u16 i = 0; i < w; i++) { + *fb++ = (u8)(((float)i / (float)w) * 255.0); + *fb++ = (u8)(((float)j / (float)h) * 255.0); + *fb++ = 0x00; + } + } + + // Flush and swap framebuffers + gfxFlushBuffers(); + gfxSwapBuffers(); + + // Wait for VBlank + gspWaitForVBlank(); + } + + gfxExit(); + return 0; +} diff --git a/src/util.c b/src/util.c new file mode 100644 index 0000000..c219831 --- /dev/null +++ b/src/util.c @@ -0,0 +1,51 @@ +#include "util.h" +#include +#include +#include + +#ifdef __3DS__ + +#include <3ds.h> + +static void panic_begin(void) { consoleInit(GFX_TOP, NULL); } + +static noreturn void panic(void) { + printf("\nPress Start to exit.\n"); + + while (aptMainLoop()) { + hidScanInput(); + u32 keys = hidKeysDown(); + if (keys & KEY_START) + break; + gfxFlushBuffers(); + gfxSwapBuffers(); + gspWaitForVBlank(); + } + + gfxExit(); + exit(1); +} + +#else + +static void panic_begin(void) {} + +static noreturn void panic(void) { abort(); } + +#endif + +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); + panic(); +} + +noreturn void todo__impl(const char *file, int line, const char *fmt, ...) { + panic_begin(); + printf("%s:%d: TODO: ", file, line); + va_list ap; + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + panic(); +} diff --git a/src/util.h b/src/util.h new file mode 100644 index 0000000..569054b --- /dev/null +++ b/src/util.h @@ -0,0 +1,31 @@ +#ifndef IMB3_UTIL_H +#define IMB3_UTIL_H + +#include +#include + +static inline bool likely(bool cond) { return __builtin_expect(cond, true); } +static inline bool unlikely(bool cond) { return __builtin_expect(cond, false); } + +#ifndef NDEBUG +noreturn void assume__failed(const char *file, int line, const char *expr); +#endif // NDEBUG + +static inline void assume__impl(bool cond, const char *file, int line, + const char *expr) { +#ifndef NDEBUG + if (unlikely(!cond)) + assume__failed(file, line, expr); +#endif // NDEBUG + if (unlikely(!cond)) + __builtin_unreachable(); +} + +#define assume(COND) assume__impl(COND, __FILE__, __LINE__, #COND) + +__attribute__((format(printf, 3, 4))) noreturn void +todo__impl(const char *file, int line, const char *fmt, ...); + +#define todo(...) todo__impl(__FILE__, __LINE__, __VA_ARGS__) + +#endif // IMB3_UTIL_H diff --git a/src/value.c b/src/value.c new file mode 100644 index 0000000..66d388c --- /dev/null +++ b/src/value.c @@ -0,0 +1 @@ +#include "value.h" diff --git a/src/value.h b/src/value.h new file mode 100644 index 0000000..a932514 --- /dev/null +++ b/src/value.h @@ -0,0 +1,38 @@ +#ifndef IMB3_VALUE_H +#define IMB3_VALUE_H + +#include + +struct value { + uintptr_t bits; +}; + +enum value_tag { + /** + * A big integer or the nil constant. + */ + TAG_BIGINT_OR_NIL = 0b000, + + /** + * 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, + + /** + * A builtin-object. + */ + TAG_BUILTIN_OBJECT = 0b010, + + /** + * A simple-array, i.e. an array of values without a fill-pointer. + */ + TAG_SIMPLE_ARRAY = 0b100, + + /** + * A standard-object, effectively a pair of a class and a slot array. + */ + TAG_STANDARD_OBJECT = 0b110, +}; + +#endif // IMB3_VALUE_H -- cgit v1.2.3