#include <string.h>

#include <stdlib.h>

#include "mruby.h"

#include "mruby/array.h"

#include "mruby/class.h"

#include "mruby/data.h"

#include "mruby/hash.h"

#include "mruby/proc.h"

#include "mruby/range.h"

#include "mruby/string.h"

#include "mruby/variable.h"

#include "mruby/gc.h"

#include "mruby/error.h"

struct free_obj {

MRB_OBJECT_HEADER;

struct RBasic *next;

};

typedef struct {

union {

struct free_obj free;

struct RBasic basic;

struct RObject object;

struct RClass klass;

struct RString string;

struct RArray array;

struct RHash hash;

struct RRange range;

struct RData data;

struct RProc proc;

struct RException exc;

#ifdef MRB_WORD_BOXING

struct RFloat floatv;

struct RCptr cptr;

} as;

} RVALUE;

#ifdef GC_PROFILE

#include <stdio.h>

#include <sys/time.h>

static double program_invoke_time = 0;

static double gc_time = 0;

static double gc_total_time = 0;

static double

gettimeofday_time(void)

{

struct timeval tv;

gettimeofday(&tv, NULL);

return tv.tv_sec + tv.tv_usec * 1e-6;

}

#define GC_INVOKE_TIME_REPORT(with) do {\

fprintf(stderr, "%s\n", with);\

fprintf(stderr, "gc_invoke: %19.3f\n", gettimeofday_time() - program_invoke_time);\

fprintf(stderr, "is_generational: %d\n", is_generational(mrb));\

fprintf(stderr, "is_major_gc: %d\n", is_major_gc(mrb));\

} while(0)

#define GC_TIME_START do {\

gc_time = gettimeofday_time();\

} while(0)

#define GC_TIME_STOP_AND_REPORT do {\

#define GC_INVOKE_TIME_REPORT(s)

#define GC_TIME_START

#define GC_TIME_STOP_AND_REPORT

#ifdef GC_DEBUG

#define DEBUG(x) (x)

#define DEBUG(x)

#define GC_STEP_SIZE 1024

MRB_API void*

mrb_realloc_simple(mrb_state *mrb, void *p, size_t len)

{

void *p2;

p2 = (mrb->allocf)(mrb, p, len, mrb->allocf_ud);

if (!p2 && len > 0 && mrb->heaps) {

mrb_full_gc(mrb);

p2 = (mrb->allocf)(mrb, p, len, mrb->allocf_ud);

}

return p2;

}

MRB_API void*

mrb_realloc(mrb_state *mrb, void *p, size_t len)

{

void *p2;

p2 = mrb_realloc_simple(mrb, p, len);

if (!p2 && len) {

if (mrb->out_of_memory) {

/* mrb_panic(mrb); */

}

else {

mrb->out_of_memory = TRUE;

mrb_exc_raise(mrb, mrb_obj_value(mrb->nomem_err));

}

}

else {

mrb->out_of_memory = FALSE;

}

return p2;

}

MRB_API void*

mrb_malloc(mrb_state *mrb, size_t len)

{

return mrb_realloc(mrb, 0, len);

}

MRB_API void*

mrb_malloc_simple(mrb_state *mrb, size_t len)

{

return mrb_realloc_simple(mrb, 0, len);

}

MRB_API void*

mrb_calloc(mrb_state *mrb, size_t nelem, size_t len)

{

void *p;

if (nelem > 0 && len > 0 &&

nelem <= SIZE_MAX / len) {

size_t size;

size = nelem * len;

p = mrb_malloc(mrb, size);

memset(p, 0, size);

}

else {

p = NULL;

}

return p;

}

MRB_API void

mrb_free(mrb_state *mrb, void *p)

{

(mrb->allocf)(mrb, p, 0, mrb->allocf_ud);

}

#ifndef MRB_HEAP_PAGE_SIZE

#define MRB_HEAP_PAGE_SIZE 1024

struct heap_page {

};

static void

link_heap_page(mrb_state *mrb, struct heap_page *page)

{

page->next = mrb->heaps;

if (mrb->heaps)

mrb->heaps->prev = page;

mrb->heaps = page;

}

static void

unlink_heap_page(mrb_state *mrb, struct heap_page *page)

{

if (page->prev)

page->prev->next = page->next;

if (page->next)

page->next->prev = page->prev;

if (mrb->heaps == page)

mrb->heaps = page->next;

page->prev = NULL;

page->next = NULL;

}

static void

link_free_heap_page(mrb_state *mrb, struct heap_page *page)

{

page->free_next = mrb->free_heaps;

if (mrb->free_heaps) {

mrb->free_heaps->free_prev = page;

}

mrb->free_heaps = page;

}

static void

unlink_free_heap_page(mrb_state *mrb, struct heap_page *page)

{

if (page->free_prev)

page->free_prev->free_next = page->free_next;

if (page->free_next)

page->free_next->free_prev = page->free_prev;

if (mrb->free_heaps == page)

mrb->free_heaps = page->free_next;

page->free_prev = NULL;

page->free_next = NULL;

}

static void

add_heap(mrb_state *mrb)

{

struct heap_page *page = (struct heap_page *)mrb_calloc(mrb, 1, sizeof(struct heap_page));

RVALUE *p, *e;

struct RBasic *prev = NULL;

for (p = page->objects, e=p+MRB_HEAP_PAGE_SIZE; p<e; p++) {

p->as.free.tt = MRB_TT_FREE;

p->as.free.next = prev;

prev = &p->as.basic;

}

page->freelist = prev;

link_heap_page(mrb, page);

link_free_heap_page(mrb, page);

}

#define DEFAULT_GC_INTERVAL_RATIO 200

#define DEFAULT_GC_STEP_RATIO 200

#define DEFAULT_MAJOR_GC_INC_RATIO 200

#define is_generational(mrb) ((mrb)->is_generational_gc_mode)

#define is_major_gc(mrb) (is_generational(mrb) && (mrb)->gc_full)

#define is_minor_gc(mrb) (is_generational(mrb) && !(mrb)->gc_full)

mrb_init_heap(mrb_state *mrb)

{

mrb->heaps = NULL;

mrb->free_heaps = NULL;

add_heap(mrb);

mrb->gc_interval_ratio = DEFAULT_GC_INTERVAL_RATIO;

mrb->gc_step_ratio = DEFAULT_GC_STEP_RATIO;

#ifndef MRB_GC_TURN_OFF_GENERATIONAL

mrb->is_generational_gc_mode = TRUE;

mrb->gc_full = TRUE;

#ifdef GC_PROFILE

program_invoke_time = gettimeofday_time();

}

static void obj_free(mrb_state *mrb, struct RBasic *obj);

mrb_free_heap(mrb_state *mrb)

{

struct heap_page *page = mrb->heaps;

struct heap_page *tmp;

RVALUE *p, *e;

while (page) {

tmp = page;

page = page->next;

for (p = tmp->objects, e=p+MRB_HEAP_PAGE_SIZE; p<e; p++) {

if (p->as.free.tt != MRB_TT_FREE)

obj_free(mrb, &p->as.basic);

}

mrb_free(mrb, tmp);

}

}

static void

gc_protect(mrb_state *mrb, struct RBasic *p)

{

#ifdef MRB_GC_FIXED_ARENA

if (mrb->arena_idx >= MRB_GC_ARENA_SIZE) {

/* arena overflow error */

mrb->arena_idx = MRB_GC_ARENA_SIZE - 4; /* force room in arena */

mrb_raise(mrb, E_RUNTIME_ERROR, "arena overflow error");

}

if (mrb->arena_idx >= mrb->arena_capa) {

/* extend arena */

mrb->arena_capa = (int)(mrb->arena_capa * 1.5);

mrb->arena = (struct RBasic**)mrb_realloc(mrb, mrb->arena, sizeof(struct RBasic*)*mrb->arena_capa);

}

mrb->arena[mrb->arena_idx++] = p;

}

MRB_API void

mrb_gc_protect(mrb_state *mrb, mrb_value obj)

{

if (mrb_immediate_p(obj)) return;

gc_protect(mrb, mrb_basic_ptr(obj));

}

MRB_API struct RBasic*

mrb_obj_alloc(mrb_state *mrb, enum mrb_vtype ttype, struct RClass *cls)

{

struct RBasic *p;

static const RVALUE RVALUE_zero = { { { MRB_TT_FALSE } } };

#ifdef MRB_GC_STRESS

mrb_full_gc(mrb);

if (mrb->gc_threshold < mrb->live) {

mrb_incremental_gc(mrb);

}

if (mrb->free_heaps == NULL) {

add_heap(mrb);

}

p = mrb->free_heaps->freelist;

mrb->free_heaps->freelist = ((struct free_obj*)p)->next;

if (mrb->free_heaps->freelist == NULL) {

unlink_free_heap_page(mrb, mrb->free_heaps);

}

mrb->live++;

gc_protect(mrb, p);

*(RVALUE *)p = RVALUE_zero;

p->tt = ttype;

p->c = cls;

paint_partial_white(mrb, p);

return p;

}

static inline void

add_gray_list(mrb_state *mrb, struct RBasic *obj)

{

#ifdef MRB_GC_STRESS

if (obj->tt > MRB_TT_MAXDEFINE) {

abort();

}

paint_gray(obj);

obj->gcnext = mrb->gray_list;

mrb->gray_list = obj;

}

static void

mark_context_stack(mrb_state *mrb, struct mrb_context *c)

{

size_t i;

size_t e;

e = c->stack - c->stbase;

if (c->ci) e += c->ci->nregs;

if (c->stbase + e > c->stend) e = c->stend - c->stbase;

for (i=0; i<e; i++) {

mrb_value v = c->stbase[i];

if (!mrb_immediate_p(v)) {

if (mrb_basic_ptr(v)->tt == MRB_TT_FREE) {

c->stbase[i] = mrb_nil_value();

}

else {

mrb_gc_mark(mrb, mrb_basic_ptr(v));

}

}

}

}

static void

mark_context(mrb_state *mrb, struct mrb_context *c)

{

int i, e = 0;

mrb_callinfo *ci;

/* mark stack */

mark_context_stack(mrb, c);

/* mark VM stack */

if (c->cibase) {

for (ci = c->cibase; ci <= c->ci; ci++) {

if (ci->eidx > e) {

e = ci->eidx;

}

mrb_gc_mark(mrb, (struct RBasic*)ci->env);

mrb_gc_mark(mrb, (struct RBasic*)ci->proc);

mrb_gc_mark(mrb, (struct RBasic*)ci->target_class);

}

}

/* mark ensure stack */

for (i=0; i<e; i++) {

mrb_gc_mark(mrb, (struct RBasic*)c->ensure[i]);

}

/* mark fibers */

if (c->prev && c->prev->fib) {

mrb_gc_mark(mrb, (struct RBasic*)c->prev->fib);

}

}

static void

gc_mark_children(mrb_state *mrb, struct RBasic *obj)

{

mrb_assert(is_gray(obj));

paint_black(obj);

mrb->gray_list = obj->gcnext;

mrb_gc_mark(mrb, (struct RBasic*)obj->c);

switch (obj->tt) {

case MRB_TT_ICLASS:

mrb_gc_mark(mrb, (struct RBasic*)((struct RClass*)obj)->super);

break;

case MRB_TT_CLASS:

case MRB_TT_MODULE:

case MRB_TT_SCLASS:

{

struct RClass *c = (struct RClass*)obj;

mrb_gc_mark_mt(mrb, c);

mrb_gc_mark(mrb, (struct RBasic*)c->super);

}

/* fall through */

case MRB_TT_OBJECT:

case MRB_TT_DATA:

case MRB_TT_EXCEPTION:

mrb_gc_mark_iv(mrb, (struct RObject*)obj);

break;

case MRB_TT_PROC:

{

struct RProc *p = (struct RProc*)obj;

mrb_gc_mark(mrb, (struct RBasic*)p->env);

mrb_gc_mark(mrb, (struct RBasic*)p->target_class);

}

break;

case MRB_TT_ENV:

{

struct REnv *e = (struct REnv*)obj;

if (!MRB_ENV_STACK_SHARED_P(e)) {

int i, len;

len = (int)MRB_ENV_STACK_LEN(e);

for (i=0; i<len; i++) {

mrb_gc_mark_value(mrb, e->stack[i]);

}

}

}

break;

case MRB_TT_FIBER:

{

struct mrb_context *c = ((struct RFiber*)obj)->cxt;

if (c) mark_context(mrb, c);

}

break;

case MRB_TT_ARRAY:

{

struct RArray *a = (struct RArray*)obj;

size_t i, e;

for (i=0,e=a->len; i<e; i++) {

mrb_gc_mark_value(mrb, a->ptr[i]);

}

}

break;

case MRB_TT_HASH:

mrb_gc_mark_iv(mrb, (struct RObject*)obj);

mrb_gc_mark_hash(mrb, (struct RHash*)obj);

break;

case MRB_TT_STRING:

break;

case MRB_TT_RANGE:

{

struct RRange *r = (struct RRange*)obj;

if (r->edges) {

mrb_gc_mark_value(mrb, r->edges->beg);

mrb_gc_mark_value(mrb, r->edges->end);

}

}

break;

default:

break;

}

}

MRB_API void

mrb_gc_mark(mrb_state *mrb, struct RBasic *obj)

{

if (obj == 0) return;

if (!is_white(obj)) return;

mrb_assert((obj)->tt != MRB_TT_FREE);

add_gray_list(mrb, obj);

}

static void

obj_free(mrb_state *mrb, struct RBasic *obj)

{

DEBUG(printf("obj_free(%p,tt=%d)\n",obj,obj->tt));

switch (obj->tt) {

/* immediate - no mark */

case MRB_TT_TRUE:

case MRB_TT_FIXNUM:

case MRB_TT_SYMBOL:

/* cannot happen */

return;

case MRB_TT_FLOAT:

#ifdef MRB_WORD_BOXING

break;

return;

case MRB_TT_OBJECT:

case MRB_TT_EXCEPTION:

mrb_gc_free_iv(mrb, (struct RObject*)obj);

break;

case MRB_TT_CLASS:

case MRB_TT_MODULE:

case MRB_TT_SCLASS:

mrb_gc_free_mt(mrb, (struct RClass*)obj);

mrb_gc_free_iv(mrb, (struct RObject*)obj);

break;

case MRB_TT_ENV:

{

struct REnv *e = (struct REnv*)obj;

if (!MRB_ENV_STACK_SHARED_P(e)) {

mrb_free(mrb, e->stack);

e->stack = NULL;

}

}

break;

case MRB_TT_FIBER:

{

struct mrb_context *c = ((struct RFiber*)obj)->cxt;

if (c != mrb->root_c)

mrb_free_context(mrb, c);

}

break;

case MRB_TT_ARRAY:

if (ARY_SHARED_P(obj))

mrb_ary_decref(mrb, ((struct RArray*)obj)->aux.shared);

else

mrb_free(mrb, ((struct RArray*)obj)->ptr);

break;

case MRB_TT_HASH:

mrb_gc_free_iv(mrb, (struct RObject*)obj);

mrb_gc_free_hash(mrb, (struct RHash*)obj);

break;

case MRB_TT_STRING:

mrb_gc_free_str(mrb, (struct RString*)obj);

break;

case MRB_TT_PROC:

{

struct RProc *p = (struct RProc*)obj;

if (!MRB_PROC_CFUNC_P(p) && p->body.irep) {

mrb_irep_decref(mrb, p->body.irep);

}

}

break;

case MRB_TT_RANGE:

mrb_free(mrb, ((struct RRange*)obj)->edges);

break;

case MRB_TT_DATA:

{

struct RData *d = (struct RData*)obj;

if (d->type && d->type->dfree) {

d->type->dfree(mrb, d->data);

}

mrb_gc_free_iv(mrb, (struct RObject*)obj);

}

break;

default:

break;

}

obj->tt = MRB_TT_FREE;

}

static void

root_scan_phase(mrb_state *mrb)

{

size_t i, e;

if (!is_minor_gc(mrb)) {

mrb->gray_list = NULL;

mrb->atomic_gray_list = NULL;

}

mrb_gc_mark_gv(mrb);

/* mark arena */

for (i=0,e=mrb->arena_idx; i<e; i++) {

mrb_gc_mark(mrb, mrb->arena[i]);

}

/* mark class hierarchy */

mrb_gc_mark(mrb, (struct RBasic*)mrb->object_class);

/* mark top_self */

mrb_gc_mark(mrb, (struct RBasic*)mrb->top_self);

/* mark exception */

mrb_gc_mark(mrb, (struct RBasic*)mrb->exc);

/* mark pre-allocated exception */

mrb_gc_mark(mrb, (struct RBasic*)mrb->nomem_err);

mark_context(mrb, mrb->root_c);

if (mrb->root_c->fib) {

mrb_gc_mark(mrb, (struct RBasic*)mrb->root_c->fib);

}

if (mrb->root_c != mrb->c) {

mark_context(mrb, mrb->c);

}

}

static size_t

gc_gray_mark(mrb_state *mrb, struct RBasic *obj)

{

size_t children = 0;

gc_mark_children(mrb, obj);

switch (obj->tt) {

case MRB_TT_ICLASS:

children++;

break;

case MRB_TT_CLASS:

case MRB_TT_SCLASS:

case MRB_TT_MODULE:

{

struct RClass *c = (struct RClass*)obj;

children += mrb_gc_mark_iv_size(mrb, (struct RObject*)obj);

children += mrb_gc_mark_mt_size(mrb, c);

children++;

}

break;

case MRB_TT_OBJECT:

case MRB_TT_DATA:

case MRB_TT_EXCEPTION:

children += mrb_gc_mark_iv_size(mrb, (struct RObject*)obj);

break;

case MRB_TT_ENV:

children += (int)obj->flags;

break;

case MRB_TT_FIBER:

{

struct mrb_context *c = ((struct RFiber*)obj)->cxt;

size_t i;

mrb_callinfo *ci;

if (!c) break;

/* mark stack */

i = c->stack - c->stbase;

if (c->ci) i += c->ci->nregs;

if (c->stbase + i > c->stend) i = c->stend - c->stbase;

children += i;

/* mark ensure stack */

children += (c->ci) ? c->ci->eidx : 0;

/* mark closure */

if (c->cibase) {

for (i=0, ci = c->cibase; ci <= c->ci; i++, ci++)

;

}

children += i;

}

break;

case MRB_TT_ARRAY:

{

struct RArray *a = (struct RArray*)obj;

children += a->len;

}

break;

case MRB_TT_HASH:

children += mrb_gc_mark_iv_size(mrb, (struct RObject*)obj);

children += mrb_gc_mark_hash_size(mrb, (struct RHash*)obj);

break;

case MRB_TT_PROC:

case MRB_TT_RANGE:

children+=2;

break;

default:

break;

}

return children;

}

static void

gc_mark_gray_list(mrb_state *mrb) {

while (mrb->gray_list) {

if (is_gray(mrb->gray_list))

gc_mark_children(mrb, mrb->gray_list);

else

mrb->gray_list = mrb->gray_list->gcnext;

}

}

static size_t

incremental_marking_phase(mrb_state *mrb, size_t limit)

{

size_t tried_marks = 0;

while (mrb->gray_list && tried_marks < limit) {

tried_marks += gc_gray_mark(mrb, mrb->gray_list);

}

return tried_marks;

}

static void

final_marking_phase(mrb_state *mrb)

{

mark_context_stack(mrb, mrb->root_c);

gc_mark_gray_list(mrb);

mrb_assert(mrb->gray_list == NULL);

mrb->gray_list = mrb->atomic_gray_list;

mrb->atomic_gray_list = NULL;

gc_mark_gray_list(mrb);

mrb_assert(mrb->gray_list == NULL);

}

static void

prepare_incremental_sweep(mrb_state *mrb)

{

mrb->gc_state = GC_STATE_SWEEP;

mrb->sweeps = mrb->heaps;

mrb->gc_live_after_mark = mrb->live;

}

static size_t

incremental_sweep_phase(mrb_state *mrb, size_t limit)

{

struct heap_page *page = mrb->sweeps;

size_t tried_sweep = 0;

while (page && (tried_sweep < limit)) {

RVALUE *p = page->objects;

RVALUE *e = p + MRB_HEAP_PAGE_SIZE;

size_t freed = 0;

mrb_bool dead_slot = TRUE;

mrb_bool full = (page->freelist == NULL);

if (is_minor_gc(mrb) && page->old) {

/* skip a slot which doesn't contain any young object */

p = e;

dead_slot = FALSE;

}

while (p<e) {

if (is_dead(mrb, &p->as.basic)) {

if (p->as.basic.tt != MRB_TT_FREE) {

obj_free(mrb, &p->as.basic);

p->as.free.next = page->freelist;

page->freelist = (struct RBasic*)p;

freed++;

}

}

else {

if (!is_generational(mrb))

paint_partial_white(mrb, &p->as.basic); /* next gc target */

dead_slot = 0;

}

p++;

}

/* free dead slot */

if (dead_slot && freed < MRB_HEAP_PAGE_SIZE) {

struct heap_page *next = page->next;

unlink_heap_page(mrb, page);

unlink_free_heap_page(mrb, page);

mrb_free(mrb, page);

page = next;

}

else {

if (full && freed > 0) {

link_free_heap_page(mrb, page);

}

if (page->freelist == NULL && is_minor_gc(mrb))

page->old = TRUE;

else

page->old = FALSE;

page = page->next;

}

tried_sweep += MRB_HEAP_PAGE_SIZE;

mrb->live -= freed;

mrb->gc_live_after_mark -= freed;

}

mrb->sweeps = page;

return tried_sweep;

}

static size_t

incremental_gc(mrb_state *mrb, size_t limit)

{

switch (mrb->gc_state) {

case GC_STATE_ROOT:

root_scan_phase(mrb);

mrb->gc_state = GC_STATE_MARK;

flip_white_part(mrb);

return 0;

case GC_STATE_MARK:

if (mrb->gray_list) {

return incremental_marking_phase(mrb, limit);

}

else {

final_marking_phase(mrb);

prepare_incremental_sweep(mrb);

return 0;

}

case GC_STATE_SWEEP: {

size_t tried_sweep = 0;

tried_sweep = incremental_sweep_phase(mrb, limit);

if (tried_sweep == 0)

mrb->gc_state = GC_STATE_ROOT;

return tried_sweep;

}

default:

/* unknown state */

mrb_assert(0);

return 0;

}

}

static void

incremental_gc_until(mrb_state *mrb, enum gc_state to_state)

{

do {

incremental_gc(mrb, SIZE_MAX);

} while (mrb->gc_state != to_state);

}

static void

incremental_gc_step(mrb_state *mrb)

{

size_t limit = 0, result = 0;

limit = (GC_STEP_SIZE/100) * mrb->gc_step_ratio;

while (result < limit) {

result += incremental_gc(mrb, limit);

if (mrb->gc_state == GC_STATE_ROOT)

break;

}

mrb->gc_threshold = mrb->live + GC_STEP_SIZE;

}

static void

clear_all_old(mrb_state *mrb)

{

mrb_bool origin_mode = mrb->is_generational_gc_mode;

mrb_assert(is_generational(mrb));

if (is_major_gc(mrb)) {

/* finish the half baked GC */

incremental_gc_until(mrb, GC_STATE_ROOT);

}

/* Sweep the dead objects, then reset all the live objects

mrb->is_generational_gc_mode = FALSE;

prepare_incremental_sweep(mrb);

incremental_gc_until(mrb, GC_STATE_ROOT);

mrb->is_generational_gc_mode = origin_mode;

/* The gray objects have already been painted as white */

mrb->atomic_gray_list = mrb->gray_list = NULL;

}

MRB_API void

mrb_incremental_gc(mrb_state *mrb)

{

if (mrb->gc_disabled) return;

GC_INVOKE_TIME_REPORT("mrb_incremental_gc()");

GC_TIME_START;

if (is_minor_gc(mrb)) {

incremental_gc_until(mrb, GC_STATE_ROOT);