path: root/src/gc/gc.c

#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");
}