rosella/gc.h

#ifndef GC_H_6b8a27c99f2eb5eb5437e045fa4af1c3
#define GC_H_6b8a27c99f2eb5eb5437e045fa4af1c3

#include <assert.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdio.h>
#include <time.h>

/*
** Macro Definitions
*/

/*
** nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn1   fixnum
**
** sssssssssssssssssssssssssss00000   special
** xxxxxxxxxxyyyyyyyyyyyyyyyyy00010   object_blocks[x].objects[y].box
** xxxxxxxxxxyyyyyyyyyyyyyyyyy00100   object_blocks[x].objects[y].weak_box
** xxxxxxxxxxyyyyyyyyyyyyyyyyy00110   object_blocks[x].objects[y].pair
** xxxxxxxxxxyyyyyyyyyyyyyyyyy01000   object_blocks[x].objects[y].fpnum
** xxxxxxxxxxyyyyyyyyyyyyyyyyy01010   object_blocks[x].objects[y].builtin_fn
** xxxxxxxxxxyyyyyyyyyyyyyyyyy01100   reserved
** xxxxxxxxxxyyyyyyyyyyyyyyyyy01110   reserved
**
** xxxxxxxxxxyyyyyyyyyyyyyyyyy10000   object_blocks[x].objects[y].vector
** xxxxxxxxxxyyyyyyyyyyyyyyyyy10010   object_blocks[x].objects[y].byte_string
** xxxxxxxxxxyyyyyyyyyyyyyyyyy10100   object_blocks[x].objects[y].structure
** xxxxxxxxxxyyyyyyyyyyyyyyyyy10110   object_blocks[x].objects[y].will
** xxxxxxxxxxyyyyyyyyyyyyyyyyy11000   reserved
** xxxxxxxxxxyyyyyyyyyyyyyyyyy11010   reserved
** xxxxxxxxxxyyyyyyyyyyyyyyyyy11100   reserved
** xxxxxxxxxxyyyyyyyyyyyyyyyyy11110   reserved
*/

#define FIXNUM_MIN   (INT32_MIN/2)
#define FIXNUM_MAX   (INT32_MAX/2)

#define OBJECT_BLOCK_MAX     0x3ff
#define OBJECT_INDEX_MAX   0x1ffff
#define OBJECT_TAG_MAX         0xf

#define OBJECT_TAG_FIXNUM       -1
#define OBJECT_TAG_SPECIAL       0
#define OBJECT_TAG_BOX           1
#define OBJECT_TAG_WEAK_BOX      2
#define OBJECT_TAG_PAIR          3
#define OBJECT_TAG_FPNUM         4
#define OBJECT_TAG_BUILTIN_FN    5
/* 6 & 7 are reserved */
#define OBJECT_TAG_VECTOR        8
#define OBJECT_TAG_BYTE_STRING   9
#define OBJECT_TAG_STRUCT       10
#define OBJECT_TAG_WILL         11
/* 12-15 are reserved */

#define OBJECT(blk, idx, tag) \
  ((((value_t)(blk) &   0x3ff) << 22) | \
   (((value_t)(idx) & 0x1ffff) <<  5) | \
   (((value_t)(tag) &     0xf) <<  1))

#define OBJECT_BLOCK(value) ((int)(((value) >> 22) &   0x3ff))
#define OBJECT_INDEX(value) ((int)(((value) >>  5) & 0x1ffff))
#define OBJECT_TAG(value)   ((int)(((value) >>  1) &     0xf))

#define SPECIAL_VALUE(n)    ((value_t)(n)  << 5)
#define SPECIAL_MAX         ((value_t)(-1) << 5)

#define UNDEFINED        SPECIAL_VALUE(0)
#define NIL              SPECIAL_VALUE(1)
#define FALSE_VALUE      SPECIAL_VALUE(2)
#define TRUE_VALUE       SPECIAL_VALUE(3)
#define END_PROGRAM      SPECIAL_VALUE(4)

#define CAR(x)           (get_pair(x)->car)
#define CDR(x)           (get_pair(x)->cdr)
#define CADR(x)          CAR(CDR(x))
#define CDDR(x)          CDR(CDR(x))

/* Ex: SLOT_VALUE(STRUCTURE, v, NAME) */
#define SLOT_VALUE(t,v,s)   (get_struct(v)->slots[t ## _SLOT_ ## s])
#define _SLOT_VALUE(t,v,s)  SLOT_VALUE(t,v,s)

#define STRUCTURE_SLOT_SUPER     0
#define STRUCTURE_SLOT_NSLOTS    1
#define STRUCTURE_SLOT_CALLABLE  2
#define STRUCTURE_SLOTS          3

/* Invoke this macro after updating any object with a new object reference. */
/* Write barriers are required for generational and incremental collectors. */
/* If unsure, invoke the macro; at most there will be a slight cost in performance. */
/* Failing to invoke the macro before the next GC pass can lead to incorrect behavior. */
#define WRITE_BARRIER(value) ((void)0)

/* Like assert(), but for things we want to check even in release builds. */
/* More informative than a simple "if (!x) abort();" statement. */
#define release_assert(expr) \
  ((expr) ? (void)0 : (void)_release_assert(#expr, __FILE__, __LINE__))

/* Evaluates to false, but with an expression that conveys what went wrong. */
#define NOTREACHED(msg) 0

/*
** Type Definitions
*/

/* Primitive types */
typedef uint32_t value_t;
typedef int32_t  fixnum_t;
typedef double   fpnum_t;

/* Builtins replace the normal run_byte_code() and perform_tail_call() steps.
 * The argv, k, and ctx inputs can be found in the state fields, and should be
 * updated as necessary (particularly argv) before the builtin returns. The
 * 'lambda' field will refer to the builtin itself, and in1-in3 are all free. */
struct interp_state;
typedef void builtin_fn_t(struct interp_state *state);

typedef struct box
{
  value_t value;
} box_t;

typedef struct weak_box
{
  value_t value;
  value_t next;
} weak_box_t;

typedef struct pair
{
  value_t car;
  value_t cdr;
} pair_t;

typedef struct vector
{
  bool    immutable;
  size_t  nelements;
  value_t elements[0];
} vector_t;

typedef struct byte_string
{
  bool    immutable;
  size_t  nbytes;
  uint8_t bytes[0];
} byte_string_t;

typedef struct structure
{
  bool    immutable;
  size_t  nslots;
  value_t type;
  value_t slots[0];
} struct_t;

typedef struct will
{
  value_t value;
  value_t finalizer;
  value_t next;
} will_t;

typedef union object
{
  /* free list */
  value_t        next;

  /* direct values */
  box_t          box;
  weak_box_t     weak_box;
  pair_t         pair;
  fpnum_t        fpnum;
  builtin_fn_t  *builtin_fn;

  /* indirect values */
  vector_t      *vector;
  byte_string_t *byte_string;
  struct_t      *structure;
  will_t        *will;
} object_t;

typedef struct object_block
{
  object_t *objects;
  uint32_t *flag_bits;
} object_block_t;

typedef struct gc_root
{
  value_t value;
  struct gc_root *prev;
  struct gc_root *next;
} gc_root_t;

/* uint64_t isn't present everywhere  */
typedef unsigned long long nsec_t;
typedef unsigned long long llsize_t;

typedef struct gc_stats
{
  int      passes;
  nsec_t   total_ns;
  nsec_t   peak_ns;
  llsize_t total_freed;
  llsize_t peak_allocated;
} gc_stats_t;

/*
** Object Declarations
*/

extern object_block_t  object_blocks[OBJECT_BLOCK_MAX + 1];
extern gc_stats_t      gc_stats;

/*
** Function Declarations
*/

static inline bool           get_boolean(value_t v);
static inline fixnum_t       get_fixnum(value_t v);
static inline fpnum_t        get_float(value_t v);
static inline builtin_fn_t  *get_builtin_fn(value_t v);

static inline box_t         *get_box(value_t v);
static inline weak_box_t    *get_weak_box(value_t v);
static inline pair_t        *get_pair(value_t v);
static inline vector_t      *get_vector(value_t v);
static inline byte_string_t *get_byte_string(value_t v); 
static inline struct_t      *get_struct(value_t v); 
/* wills are deliberately omitted from the public interface */

static inline value_t make_boolean(bool value);
static inline value_t make_fixnum(fixnum_t value);

value_t make_float(fpnum_t value);
value_t make_builtin_fn(builtin_fn_t *fn);
value_t make_box(value_t initial_value);
value_t make_weak_box(value_t value);
value_t make_pair(value_t car, value_t cdr);
value_t make_vector(size_t nelements, value_t init);
value_t make_byte_string(size_t nbytes, int init);
value_t make_struct(value_t type);
/* wills are deliberately omitted from the public interface */

/* Returns a byte string w/ bytes from 's' (excl. terminating NUL). */
value_t string_to_value(const char *s);

/* Returns a new C string which must be free()'d by caller. */
char *value_to_string(value_t v);

/* Like strcmp(), but for byte strings. */
int byte_strcmp(value_t s1, value_t s2);

/* Return the structure instance at the root of the structure type hierarchy. */
value_t get_structure_type(void);

/* Instantiates a structure type. Result is immutable. */
value_t make_struct_type(value_t super, fixnum_t nslots, value_t callable);

/* True if 'value' is (1) a structure, and (2) an instance of 'type'. */
bool struct_is_a(value_t value, value_t type);

/* Finalizers are register-and-forget; there should be no external references to wills. */
void register_finalizer(value_t value, value_t finalizer);
bool are_finalizers_pending(void);

/* If *value == #f on return there are no more finalizers. */
void get_next_finalizer(value_t *value, value_t *finalizer);

void register_gc_root(gc_root_t *root, value_t v);
void unregister_gc_root(gc_root_t *root);

void gc_init(void);
void clear_gc_stats(void);
void collect_garbage(void);
bool set_gc_enabled(bool enable);

void fprint_value(FILE *f, value_t v);
void fprint_gc_stats(FILE *f);

/* Implements the release_assert() macro */
void _release_assert(const char *str, const char *file, int line) __attribute__((noreturn));

/* Provides a more informative message for type check failures */
void type_mismatch(value_t value, int expected_tag) __attribute__((noreturn));

/* To be provided by the main application */
void out_of_memory(void);

/*
** Static Function Definitions
*/

static inline bool is_valid_fixnum(fixnum_t n)
{
  return (FIXNUM_MIN <= n) && (n <= FIXNUM_MAX);
}

static inline bool is_nil(value_t v)
{
  return v == NIL;
}

static inline bool is_undefined(value_t v)
{
  return v == UNDEFINED;
}

static inline bool is_boolean(value_t v)
{
  return (v == FALSE_VALUE) || (v == TRUE_VALUE);
}

static inline bool is_fixnum(value_t value)
{
  return (value & 1) != 0;
}

static inline bool is_object_type(value_t value, int tag)
{
  if (tag == OBJECT_TAG_FIXNUM)
    return is_fixnum(value);
  else if ((tag < 0) || (tag > OBJECT_TAG_MAX))
    return false;
  else
    return ((value & 0x1f) == ((value_t)tag << 1));
}

static inline bool is_special(value_t value)
{
  return is_object_type(value, OBJECT_TAG_SPECIAL);
}

static inline bool is_object(value_t value)
{
  return !is_fixnum(value) && !is_special(value);
}

static inline bool is_box(value_t value)
{
  return is_object_type(value, OBJECT_TAG_BOX);
}

static inline bool is_weak_box(value_t value)
{
  return is_object_type(value, OBJECT_TAG_WEAK_BOX);
}

static inline bool is_pair(value_t value)
{
  return is_object_type(value, OBJECT_TAG_PAIR);
}

static inline bool is_list(value_t value)
{
  return is_nil(value) || is_pair(value);
}

static inline bool is_float(value_t value)
{
  return is_object_type(value, OBJECT_TAG_FPNUM);
}

static inline bool is_builtin_fn(value_t value)
{
  return is_object_type(value, OBJECT_TAG_BUILTIN_FN);
}

static inline bool is_vector(value_t value)
{
  return is_object_type(value, OBJECT_TAG_VECTOR);
}

static inline bool is_byte_string(value_t value)
{
  return is_object_type(value, OBJECT_TAG_BYTE_STRING);
}

static inline bool is_struct(value_t value)
{
  return is_object_type(value, OBJECT_TAG_STRUCT);
}

static inline int get_object_type(value_t value)
{
  if (is_fixnum(value))
    return OBJECT_TAG_FIXNUM;
  else
    return OBJECT_TAG(value);
}

static inline bool get_boolean(value_t v)
{
  return v != FALSE_VALUE;
}

static inline int32_t get_fixnum(value_t value)
{
  return (int32_t)value >> 1;
}

static inline object_t *_get_object(value_t value)
{
  release_assert(is_object(value));
  return &object_blocks[OBJECT_BLOCK(value)].objects[OBJECT_INDEX(value)];
}

static inline object_t *_get_typed_object(value_t value, int tag)
{
  if (!is_object_type(value, tag))
  {
    type_mismatch(value, tag);
  }
  return &object_blocks[OBJECT_BLOCK(value)].objects[OBJECT_INDEX(value)];
}

static inline box_t *get_box(value_t value)
{
  return &_get_typed_object(value, OBJECT_TAG_BOX)->box;
}

static inline weak_box_t *get_weak_box(value_t value)
{
  return &_get_typed_object(value, OBJECT_TAG_WEAK_BOX)->weak_box;
}

static inline pair_t *get_pair(value_t value)
{
  return &_get_typed_object(value, OBJECT_TAG_PAIR)->pair;
}

static inline fpnum_t get_float(value_t value)
{
  return _get_typed_object(value, OBJECT_TAG_FPNUM)->fpnum;
}

static inline builtin_fn_t *get_builtin_fn(value_t value)
{
  return _get_typed_object(value, OBJECT_TAG_BUILTIN_FN)->builtin_fn;
}

static inline vector_t *get_vector(value_t value)
{
  return _get_typed_object(value, OBJECT_TAG_VECTOR)->vector;
}

static inline byte_string_t *get_byte_string(value_t value)
{
  return _get_typed_object(value, OBJECT_TAG_BYTE_STRING)->byte_string;
}

static inline struct_t *get_struct(value_t value)
{
  return _get_typed_object(value, OBJECT_TAG_STRUCT)->structure;
}

static inline value_t make_boolean(bool b)
{
  return b ? TRUE_VALUE : FALSE_VALUE;
}

static inline value_t make_fixnum(int32_t n)
{
  //release_assert(is_valid_fixnum(n));
  return (value_t)((n << 1) | 1);
}

static inline void print_value(value_t v)
{
  fprint_value(stdout, v);
}

static inline void print_gc_stats(void)
{
  fprint_gc_stats(stderr);
}

#endif
/* vim:set sw=2 expandtab: */