path: root/src/gc/gen3.c

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

/**
 * 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);
}