bdw.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define GC_IMPL 1

#include "gc-api.h"
#include "gc-ephemeron.h"
#include "gc-tracepoint.h"

#include "gc-internal.h"

#include "bdw-attrs.h"

#if GC_PRECISE_ROOTS
#error bdw-gc is a conservative collector
#endif

#if !GC_CONSERVATIVE_ROOTS
#error bdw-gc is a conservative collector
#endif

#if !GC_CONSERVATIVE_TRACE
#error bdw-gc is a conservative collector
#endif

// When pthreads are used, let `libgc' know about it and redirect
// allocation calls such as `GC_MALLOC ()' to (contention-free, faster)
// thread-local allocation.

#define GC_THREADS 1
#define GC_REDIRECT_TO_LOCAL 1

// Don't #define pthread routines to their GC_pthread counterparts.
// Instead we will be careful inside the benchmarks to use API to
// register threads with libgc.
#define GC_NO_THREAD_REDIRECTS 1

#include <gc/gc.h>
#include <gc/gc_inline.h> /* GC_generic_malloc_many */
#include <gc/gc_mark.h> /* GC_generic_malloc */

#define GC_INLINE_GRANULE_WORDS 2
#define GC_INLINE_GRANULE_BYTES (sizeof(void *) * GC_INLINE_GRANULE_WORDS)

/* A freelist set contains GC_INLINE_FREELIST_COUNT pointers to singly
   linked lists of objects of different sizes, the ith one containing
   objects i + 1 granules in size.  This setting of
   GC_INLINE_FREELIST_COUNT will hold freelists for allocations of
   up to 256 bytes.  */
#define GC_INLINE_FREELIST_COUNT (256U / GC_INLINE_GRANULE_BYTES)

struct gc_heap {
  struct gc_heap *freelist; // see mark_heap
  pthread_mutex_t lock;
  struct gc_heap_roots *roots;
  struct gc_mutator *mutators;
  struct gc_event_listener event_listener;
  struct gc_finalizer_state *finalizer_state;
  gc_finalizer_callback have_finalizers;
  void *event_listener_data;
  void* (*allocation_failure)(struct gc_heap *, size_t);
};

struct gc_mutator {
  void *freelists[GC_INLINE_FREELIST_COUNT];
  struct gc_heap *heap;
  struct gc_mutator_roots *roots;
  struct gc_mutator *next; // with heap lock
  struct gc_mutator **prev; // with heap lock
  void *event_listener_data;
};

struct gc_heap *__the_bdw_gc_heap;
#define HEAP_EVENT(event, ...) do {                                     \
    __the_bdw_gc_heap->event_listener.event(__the_bdw_gc_heap->event_listener_data, \
                                            ##__VA_ARGS__);             \
    GC_TRACEPOINT(event, ##__VA_ARGS__);                                \
  } while (0)
#define MUTATOR_EVENT(mut, event, ...) do {                             \
    __the_bdw_gc_heap->event_listener.event(mut->event_listener_data,   \
                                            ##__VA_ARGS__);             \
    GC_TRACEPOINT(event, ##__VA_ARGS__);                                \
  } while (0)
static inline size_t gc_inline_bytes_to_freelist_index(size_t bytes) {
  return (bytes - 1U) / GC_INLINE_GRANULE_BYTES;
}
static inline size_t gc_inline_freelist_object_size(size_t idx) {
  return (idx + 1U) * GC_INLINE_GRANULE_BYTES;
}

struct gc_heap* gc_mutator_heap(struct gc_mutator *mutator) {
  return __the_bdw_gc_heap;
}
uintptr_t gc_small_object_nursery_low_address(struct gc_heap *heap) {
  GC_CRASH();
}
uintptr_t gc_small_object_nursery_high_address(struct gc_heap *heap) {
  GC_CRASH();
}

// The values of these must match the internal POINTERLESS and NORMAL
// definitions in libgc, for which unfortunately there are no external
// definitions.  Alack.
enum gc_inline_kind {
  GC_INLINE_KIND_POINTERLESS,
  GC_INLINE_KIND_NORMAL
};

static inline void *
allocate_small(void **freelist, size_t idx, enum gc_inline_kind kind) {
  void *head = *freelist;

  if (!head) {
    size_t bytes = gc_inline_freelist_object_size(idx);
    GC_generic_malloc_many(bytes, kind, freelist);
    head = *freelist;
    if (GC_UNLIKELY (!head))
      return __the_bdw_gc_heap->allocation_failure(__the_bdw_gc_heap, bytes);
  }

  *freelist = *(void **)(head);
  *(void**)head = NULL;

  return head;
}

void* gc_allocate_slow(struct gc_mutator *mut, size_t size,
                       enum gc_allocation_kind kind) {
  GC_ASSERT(size != 0);
  if (size <= gc_allocator_large_threshold()) {
    switch (kind) {
      case GC_ALLOCATION_TAGGED:
      case GC_ALLOCATION_UNTAGGED_CONSERVATIVE: {
        size_t idx = gc_inline_bytes_to_freelist_index(size);
        return allocate_small(&mut->freelists[idx], idx, GC_INLINE_KIND_NORMAL);
      }
      case GC_ALLOCATION_TAGGED_POINTERLESS:
      case GC_ALLOCATION_UNTAGGED_POINTERLESS:
        break;
      default:
        GC_CRASH();
    }
  }
  switch (kind) {
    case GC_ALLOCATION_TAGGED:
    case GC_ALLOCATION_UNTAGGED_CONSERVATIVE: {
      void *ret = GC_malloc(size);
      if (GC_LIKELY (ret != NULL))
        return ret;
      return __the_bdw_gc_heap->allocation_failure(__the_bdw_gc_heap, size);
    }
    case GC_ALLOCATION_TAGGED_POINTERLESS:
    case GC_ALLOCATION_UNTAGGED_POINTERLESS: {
      void *ret = GC_malloc_atomic(size);
      if (GC_LIKELY (ret != NULL)) {
        memset(ret, 0, size);
        return ret;
      }
      return __the_bdw_gc_heap->allocation_failure(__the_bdw_gc_heap, size);
    }
    default:
      GC_CRASH();
  }
}

void gc_pin_object(struct gc_mutator *mut, struct gc_ref ref) {
  // Nothing to do.
}

void gc_collect(struct gc_mutator *mut,
                enum gc_collection_kind requested_kind) {
  switch (requested_kind) {
  case GC_COLLECTION_MINOR:
    GC_collect_a_little();
    break;
  case GC_COLLECTION_ANY:
  case GC_COLLECTION_MAJOR:
    GC_gcollect();
    break;
  case GC_COLLECTION_COMPACTING:
    GC_gcollect_and_unmap();
    break;
  default:
    GC_CRASH();
  }
}

int gc_object_is_old_generation_slow(struct gc_mutator *mut,
                                     struct gc_ref obj) {
  return 0;
}

void gc_write_barrier_slow(struct gc_mutator *mut, struct gc_ref obj,
                           size_t obj_size, struct gc_edge edge,
                           struct gc_ref new_val) {
}

int* gc_safepoint_flag_loc(struct gc_mutator *mut) { GC_CRASH(); }
void gc_safepoint_slow(struct gc_mutator *mut) { GC_CRASH(); }

struct bdw_mark_state {
  struct GC_ms_entry *mark_stack_ptr;
  struct GC_ms_entry *mark_stack_limit;
};

static void bdw_mark_edge(struct gc_edge edge, struct gc_heap *heap,
                          void *visit_data) {
  struct bdw_mark_state *state = visit_data;
  uintptr_t addr = gc_ref_value(gc_edge_ref(edge));
  state->mark_stack_ptr = GC_MARK_AND_PUSH ((void *) addr,
                                            state->mark_stack_ptr,
                                            state->mark_stack_limit,
                                            NULL);
}

static int heap_gc_kind;
static int mutator_gc_kind;
static int ephemeron_gc_kind;
static int finalizer_gc_kind;

// In BDW-GC, we can't hook into the mark phase to call
// gc_trace_ephemerons_for_object, so the advertised ephemeron strategy
// doesn't really work.  The primitives that we have are mark functions,
// which run during GC and can't allocate; finalizers, which run after
// GC and can allocate but can't add to the connectivity graph; and
// disappearing links, which are cleared at the end of marking, in the
// stop-the-world phase.  It does not appear to be possible to implement
// ephemerons using these primitives.  Instead fall back to weak-key
// tables.

struct gc_ephemeron* gc_allocate_ephemeron(struct gc_mutator *mut) {
  return GC_generic_malloc(gc_ephemeron_size(), ephemeron_gc_kind);
}

unsigned gc_heap_ephemeron_trace_epoch(struct gc_heap *heap) {
  return GC_get_gc_no();
}

void gc_ephemeron_init(struct gc_mutator *mut, struct gc_ephemeron *ephemeron,
                       struct gc_ref key, struct gc_ref value) {
  gc_ephemeron_init_internal(mut->heap, ephemeron, key, value);
  if (GC_base((void*)gc_ref_value(key))) {
    struct gc_ref *loc = gc_edge_loc(gc_ephemeron_key_edge(ephemeron));
    GC_register_disappearing_link((void**)loc);
  }
}

int gc_visit_ephemeron_key(struct gc_edge edge, struct gc_heap *heap) {
  // Pretend the key is traced, to avoid adding this ephemeron to the
  // global table.
  return 1;
}

struct gc_finalizer* gc_allocate_finalizer(struct gc_mutator *mut) {
  return GC_generic_malloc(gc_finalizer_size(), finalizer_gc_kind);
}

static void finalize_object(void *obj, void *data) {
  struct gc_finalizer *f = data;
  gc_finalizer_externally_fired(__the_bdw_gc_heap->finalizer_state, f);
}

void gc_finalizer_attach(struct gc_mutator *mut, struct gc_finalizer *finalizer,
                         unsigned priority, struct gc_ref object,
                         struct gc_ref closure) {
  // Don't bother much about the actual finalizer; just delegate to BDW-GC.
  GC_finalization_proc prev = NULL;
  void *prev_data = NULL;
  gc_finalizer_init_internal(finalizer, object, closure);
  gc_finalizer_externally_activated(finalizer);
  GC_register_finalizer_no_order(gc_ref_heap_object(object), finalize_object,
                                 finalizer, &prev, &prev_data);
  // FIXME: Allow multiple finalizers per object.
  GC_ASSERT(prev == NULL);
  GC_ASSERT(prev_data == NULL);
}

struct gc_finalizer* gc_pop_finalizable(struct gc_mutator *mut) {
  GC_invoke_finalizers();
  return gc_finalizer_state_pop(mut->heap->finalizer_state);
}

void gc_set_finalizer_callback(struct gc_heap *heap,
                               gc_finalizer_callback callback) {
  heap->have_finalizers = callback;
}

static void have_finalizers(void) {
  struct gc_heap *heap = __the_bdw_gc_heap;
  if (heap->have_finalizers)
    heap->have_finalizers(heap, 1);
}

static struct GC_ms_entry *
mark_ephemeron(GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
               struct GC_ms_entry *mark_stack_limit, GC_word env) {

  struct bdw_mark_state state = {
    mark_stack_ptr,
    mark_stack_limit,
  };
  
  struct gc_ephemeron *ephemeron = (struct gc_ephemeron*) addr;

  // If this ephemeron is on a freelist, its first word will be a
  // freelist link and everything else will be NULL.
  if (!gc_ref_value(gc_edge_ref(gc_ephemeron_value_edge(ephemeron)))) {
    bdw_mark_edge(gc_edge(addr), NULL, &state);
    return state.mark_stack_ptr;
  }

  if (!gc_ref_value(gc_edge_ref(gc_ephemeron_key_edge(ephemeron)))) {
    // If the key died in a previous collection, the disappearing link
    // will have been cleared.  Mark the ephemeron as dead.
    gc_ephemeron_mark_dead(ephemeron);
  }

  gc_trace_ephemeron(ephemeron, bdw_mark_edge, NULL, &state);

  return state.mark_stack_ptr;
}

static struct GC_ms_entry *
mark_finalizer(GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
               struct GC_ms_entry *mark_stack_limit, GC_word env) {

  struct bdw_mark_state state = {
    mark_stack_ptr,
    mark_stack_limit,
  };
  
  struct gc_finalizer *finalizer = (struct gc_finalizer*) addr;

  // If this ephemeron is on a freelist, its first word will be a
  // freelist link and everything else will be NULL.
  if (!gc_ref_value(gc_finalizer_object(finalizer))) {
    bdw_mark_edge(gc_edge(addr), NULL, &state);
    return state.mark_stack_ptr;
  }

  gc_trace_finalizer(finalizer, bdw_mark_edge, NULL, &state);

  return state.mark_stack_ptr;
}

static struct GC_ms_entry *
mark_heap(GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
          struct GC_ms_entry *mark_stack_limit, GC_word env) {
  struct bdw_mark_state state = {
    mark_stack_ptr,
    mark_stack_limit,
  };
  
  struct gc_heap *heap = (struct gc_heap*) addr;

  // If this heap is on a freelist... well probably we are screwed, BDW
  // isn't really made to do multiple heaps in a process.  But still, in
  // this case, the first word is the freelist and the rest are null.
  if (heap->freelist) {
    bdw_mark_edge(gc_edge(addr), NULL, &state);
    return state.mark_stack_ptr;
  }

  if (heap->roots)
    gc_trace_heap_roots(heap->roots, bdw_mark_edge, heap, &state);

  gc_visit_finalizer_roots(heap->finalizer_state, bdw_mark_edge, heap, &state);

  state.mark_stack_ptr = GC_MARK_AND_PUSH (heap->mutators,
                                           state.mark_stack_ptr,
                                           state.mark_stack_limit,
                                           NULL);

  return state.mark_stack_ptr;
}

static struct GC_ms_entry *
mark_mutator(GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
             struct GC_ms_entry *mark_stack_limit, GC_word env) {
  struct bdw_mark_state state = {
    mark_stack_ptr,
    mark_stack_limit,
  };
  
  struct gc_mutator *mut = (struct gc_mutator*) addr;

  // If this mutator is on a freelist, its first word will be a
  // freelist link and everything else will be NULL.
  if (!mut->heap) {
    bdw_mark_edge(gc_edge(addr), NULL, &state);
    return state.mark_stack_ptr;
  }

  memset(mut->freelists, 0, sizeof(void*) * GC_INLINE_FREELIST_COUNT);

  if (mut->roots)
    gc_trace_mutator_roots(mut->roots, bdw_mark_edge, mut->heap, &state);

  state.mark_stack_ptr = GC_MARK_AND_PUSH (mut->next,
                                           state.mark_stack_ptr,
                                           state.mark_stack_limit,
                                           NULL);

  return state.mark_stack_ptr;
}

static inline struct gc_mutator *add_mutator(struct gc_heap *heap) {
  struct gc_mutator *ret =
    GC_generic_malloc(sizeof(struct gc_mutator), mutator_gc_kind);
  ret->heap = heap;
  ret->event_listener_data =
    heap->event_listener.mutator_added(heap->event_listener_data);

  pthread_mutex_lock(&heap->lock);
  ret->next = heap->mutators;
  ret->prev = &heap->mutators;
  if (ret->next)
    ret->next->prev = &ret->next;
  heap->mutators = ret;
  pthread_mutex_unlock(&heap->lock);

  return ret;
}

struct gc_options {
  struct gc_common_options common;
};
int gc_option_from_string(const char *str) {
  return gc_common_option_from_string(str);
}
struct gc_options* gc_allocate_options(void) {
  struct gc_options *ret = malloc(sizeof(struct gc_options));
  gc_init_common_options(&ret->common);
  return ret;
}
int gc_options_set_int(struct gc_options *options, int option, int value) {
  return gc_common_options_set_int(&options->common, option, value);
}
int gc_options_set_size(struct gc_options *options, int option,
                        size_t value) {
  return gc_common_options_set_size(&options->common, option, value);
}
int gc_options_set_double(struct gc_options *options, int option,
                          double value) {
  return gc_common_options_set_double(&options->common, option, value);
}
int gc_options_parse_and_set(struct gc_options *options, int option,
                             const char *value) {
  return gc_common_options_parse_and_set(&options->common, option, value);
}

struct gc_pending_ephemerons *
gc_heap_pending_ephemerons(struct gc_heap *heap) {
  GC_CRASH();
  return NULL;
}

static void on_collection_event(GC_EventType event) {
  switch (event) {
  case GC_EVENT_START: {
    HEAP_EVENT(requesting_stop);
    HEAP_EVENT(waiting_for_stop);
    break;
  }
  case GC_EVENT_MARK_START:
    HEAP_EVENT(mutators_stopped);
    HEAP_EVENT(prepare_gc, GC_COLLECTION_MAJOR);
    break;
  case GC_EVENT_MARK_END:
    HEAP_EVENT(roots_traced);
    HEAP_EVENT(heap_traced);
    break;
  case GC_EVENT_RECLAIM_START:
    break;
  case GC_EVENT_RECLAIM_END:
    // Sloppily attribute finalizers and eager reclamation to
    // ephemerons.
    HEAP_EVENT(ephemerons_traced);
    // FIXME: This overestimates the live data size, as blocks that have at
    // least one live object will be lazily swept, and free space discovered in
    // those objects will be added to GC_bytes_found, which would need to be
    // subtracted from this value.
    HEAP_EVENT(live_data_size, GC_get_heap_size() - GC_get_free_bytes());
    break;
  case GC_EVENT_END:
    HEAP_EVENT(restarting_mutators);
    break;
  case GC_EVENT_PRE_START_WORLD:
  case GC_EVENT_POST_STOP_WORLD:
    // Can't rely on these, as they are only fired when threads are
    // enabled.
    break;
  case GC_EVENT_THREAD_SUSPENDED:
  case GC_EVENT_THREAD_UNSUSPENDED:
    // No nice way to map back to the mutator.
    break;
  default:
    break;
  }
}

static void on_heap_resize(GC_word size) {
  HEAP_EVENT(heap_resized, size);
}

uint64_t gc_allocation_counter(struct gc_heap *heap) {
  return GC_get_total_bytes();
}

static void* allocation_failure(struct gc_heap *heap, size_t size) {
  fprintf(stderr, "ran out of space, heap size %zu\n", GC_get_heap_size());
  GC_CRASH();
  return NULL;
}

static void* oom_fn(size_t nbytes) {
  return NULL;
}

void gc_heap_set_allocation_failure_handler(struct gc_heap *heap,
                                            void* (*handler)(struct gc_heap*,
                                                             size_t)) {
  heap->allocation_failure = handler;
}

int gc_init(const struct gc_options *options, struct gc_stack_addr stack_base,
            struct gc_heap **heap, struct gc_mutator **mutator,
            struct gc_event_listener event_listener,
            void *event_listener_data) {
  // Root the heap, which will also cause all mutators to be marked.
  GC_ASSERT_EQ(gc_allocator_small_granule_size(), GC_INLINE_GRANULE_BYTES);
  GC_ASSERT_EQ(gc_allocator_large_threshold(),
               GC_INLINE_FREELIST_COUNT * GC_INLINE_GRANULE_BYTES);

  GC_ASSERT_EQ(__the_bdw_gc_heap, NULL);

  if (!options) options = gc_allocate_options();

  // Ignore stack base for main thread.

  switch (options->common.heap_size_policy) {
    case GC_HEAP_SIZE_FIXED:
      GC_set_max_heap_size(options->common.heap_size);
      break;
    case GC_HEAP_SIZE_GROWABLE: {
      if (options->common.maximum_heap_size)
        GC_set_max_heap_size(options->common.maximum_heap_size);
      // BDW uses a pretty weird heap-sizing heuristic:
      //
      // heap-size = live-data * (1 + (2 / GC_free_space_divisor))
      // heap-size-multiplier = heap-size/live-data = 1 + 2/GC_free_space_divisor
      // GC_free_space_divisor = 2/(heap-size-multiplier-1)
      //
      // (Assumption: your heap is mostly "composite", i.e. not
      // "atomic".  See bdw's alloc.c:min_bytes_allocd.)
      double fsd = 2.0/(options->common.heap_size_multiplier - 1);
      // But, the divisor is an integer.  WTF.  This caps the effective
      // maximum heap multiplier at 3.  Oh well.
      GC_set_free_space_divisor(fsd + 0.51);
      break;
    }
    case GC_HEAP_SIZE_ADAPTIVE:
    default:
      fprintf(stderr, "adaptive heap sizing unsupported by bdw-gc\n");
      return 0;
  }

  GC_set_all_interior_pointers (0);
  GC_set_finalize_on_demand (1);
  GC_set_finalizer_notifier(have_finalizers);

  // Not part of 7.3, sigh.  Have to set an env var.
  // GC_set_markers_count(options->common.parallelism);
  char markers[21] = {0,}; // 21 bytes enough for 2**64 in decimal + NUL.
  snprintf(markers, sizeof(markers), "%d", options->common.parallelism);
  setenv("GC_MARKERS", markers, 1);
  GC_init();
  size_t current_heap_size = GC_get_heap_size();
  if (options->common.heap_size > current_heap_size)
    GC_expand_hp(options->common.heap_size - current_heap_size);
  GC_allow_register_threads();

  {
    int add_size_to_descriptor = 0;
    int clear_memory = 1;

    heap_gc_kind = GC_new_kind(GC_new_free_list(),
                               GC_MAKE_PROC(GC_new_proc(mark_heap), 0),
                               add_size_to_descriptor, clear_memory);
    mutator_gc_kind = GC_new_kind(GC_new_free_list(),
                                  GC_MAKE_PROC(GC_new_proc(mark_mutator), 0),
                                  add_size_to_descriptor, clear_memory);
    ephemeron_gc_kind = GC_new_kind(GC_new_free_list(),
                                    GC_MAKE_PROC(GC_new_proc(mark_ephemeron), 0),
                                    add_size_to_descriptor, clear_memory);
    finalizer_gc_kind = GC_new_kind(GC_new_free_list(),
                                    GC_MAKE_PROC(GC_new_proc(mark_finalizer), 0),
                                    add_size_to_descriptor, clear_memory);
  }

  *heap = GC_generic_malloc(sizeof(struct gc_heap), heap_gc_kind);
  pthread_mutex_init(&(*heap)->lock, NULL);

  (*heap)->event_listener = event_listener;
  (*heap)->event_listener_data = event_listener_data;
  (*heap)->finalizer_state = gc_make_finalizer_state();

  __the_bdw_gc_heap = *heap;
  HEAP_EVENT(init, GC_get_heap_size());
  GC_set_on_collection_event(on_collection_event);
  GC_set_on_heap_resize(on_heap_resize);
  GC_set_oom_fn (oom_fn);
  (*heap)->allocation_failure = allocation_failure;

  *mutator = add_mutator(*heap);

  // Sanity check.
  if (!GC_is_visible (&__the_bdw_gc_heap))
    abort ();

  return 1;
}

struct gc_mutator* gc_init_for_thread(struct gc_stack_addr stack_base,
                                      struct gc_heap *heap) {
  struct GC_stack_base base = { gc_stack_addr_as_pointer (stack_base) };
  GC_register_my_thread(&base);
  return add_mutator(heap);
}
void gc_finish_for_thread(struct gc_mutator *mut) {
  pthread_mutex_lock(&mut->heap->lock);
  MUTATOR_EVENT(mut, mutator_removed);
  *mut->prev = mut->next;
  if (mut->next)
    mut->next->prev = mut->prev;
  pthread_mutex_unlock(&mut->heap->lock);

  GC_unregister_my_thread();
}

void* gc_call_without_gc(struct gc_mutator *mut,
                         void* (*f)(void*),
                         void *data) {
  return GC_do_blocking(f, data);
}

void gc_mutator_set_roots(struct gc_mutator *mut,
                          struct gc_mutator_roots *roots) {
  mut->roots = roots;
}
void gc_heap_set_roots(struct gc_heap *heap, struct gc_heap_roots *roots) {
  heap->roots = roots;
}
void gc_heap_set_extern_space(struct gc_heap *heap,
                              struct gc_extern_space *space) {
}