mbed I/F binding for mruby
Dependents: mruby_mbed_web mirb_mbed
mbed-mruby
How to use
Class
src/gc.c
- Committer:
- mzta
- Date:
- 2015-04-13
- Revision:
- 1:8ccd1d494a4b
- Parent:
- 0:158c61bb030f
File content as of revision 1:8ccd1d494a4b:
/* ** gc.c - garbage collector for mruby ** ** See Copyright Notice in mruby.h */ #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" /* = Tri-color Incremental Garbage Collection mruby's GC is Tri-color Incremental GC with Mark & Sweep. Algorithm details are omitted. Instead, the implementation part is described below. == Object's Color Each object can be painted in three colors: * White - Unmarked. * Gray - Marked, But the child objects are unmarked. * Black - Marked, the child objects are also marked. == Two White Types There're two white color types in a flip-flop fashion: White-A and White-B, which respectively represent the Current White color (the newly allocated objects in the current GC cycle) and the Sweep Target White color (the dead objects to be swept). A and B will be switched just at the beginning of the next GC cycle. At that time, all the dead objects have been swept, while the newly created objects in the current GC cycle which finally remains White are now regarded as dead objects. Instead of traversing all the White-A objects and painting them as White-B, just switch the meaning of White-A and White-B as this will be much cheaper. As a result, the objects we sweep in the current GC cycle are always left from the previous GC cycle. This allows us to sweep objects incrementally, without the disturbance of the newly created objects. == Execution Timing GC Execution Time and Each step interval are decided by live objects count. List of Adjustment API: * gc_interval_ratio_set * gc_step_ratio_set For details, see the comments for each function. == Write Barrier mruby implementer and C extension library writer must insert a write barrier when updating a reference from a field of an object. When updating a reference from a field of object A to object B, two different types of write barrier are available: * mrb_field_write_barrier - target B object for a mark. * mrb_write_barrier - target A object for a mark. == Generational Mode mruby's GC offers an Generational Mode while re-using the tri-color GC infrastructure. It will treat the Black objects as Old objects after each sweep phase, instead of painting them White. The key ideas are still the same as traditional generational GC: * Minor GC - just traverse the Young objects (Gray objects) in the mark phase, then only sweep the newly created objects, and leave the Old objects live. * Major GC - same as a full regular GC cycle. The difference from "traditional" generational GC is, that the major GC in mruby is triggered incrementally in a tri-color manner. For details, see the comments for each function. */ 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; #endif } 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 {\ gc_time = gettimeofday_time() - gc_time;\ gc_total_time += gc_time;\ fprintf(stderr, "gc_state: %d\n", mrb->gc_state);\ fprintf(stderr, "live: %zu\n", mrb->live);\ fprintf(stderr, "majorgc_old_threshold: %zu\n", mrb->majorgc_old_threshold);\ fprintf(stderr, "gc_threshold: %zu\n", mrb->gc_threshold);\ fprintf(stderr, "gc_time: %30.20f\n", gc_time);\ fprintf(stderr, "gc_total_time: %30.20f\n\n", gc_total_time);\ } while(0) #else #define GC_INVOKE_TIME_REPORT(s) #define GC_TIME_START #define GC_TIME_STOP_AND_REPORT #endif #ifdef GC_DEBUG #define DEBUG(x) (x) #else #define DEBUG(x) #endif #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 #endif struct heap_page { struct RBasic *freelist; struct heap_page *prev; struct heap_page *next; struct heap_page *free_next; struct heap_page *free_prev; mrb_bool old:1; RVALUE objects[MRB_HEAP_PAGE_SIZE]; }; 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) void 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; #endif #ifdef GC_PROFILE program_invoke_time = gettimeofday_time(); #endif } static void obj_free(mrb_state *mrb, struct RBasic *obj); void 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"); } #else 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); } #endif 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); #endif 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(); } #endif 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)) { mrb_int i, len; len = 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; #else return; #endif 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 * (including all the old objects, of course) to white. */ 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); } else { incremental_gc_step(mrb); } if (mrb->gc_state == GC_STATE_ROOT) { mrb_assert(mrb->live >= mrb->gc_live_after_mark); mrb->gc_threshold = (mrb->gc_live_after_mark/100) * mrb->gc_interval_ratio; if (mrb->gc_threshold < GC_STEP_SIZE) { mrb->gc_threshold = GC_STEP_SIZE; } if (is_major_gc(mrb)) { mrb->majorgc_old_threshold = mrb->gc_live_after_mark/100 * DEFAULT_MAJOR_GC_INC_RATIO; mrb->gc_full = FALSE; } else if (is_minor_gc(mrb)) { if (mrb->live > mrb->majorgc_old_threshold) { clear_all_old(mrb); mrb->gc_full = TRUE; } } } GC_TIME_STOP_AND_REPORT; } /* Perform a full gc cycle */ MRB_API void mrb_full_gc(mrb_state *mrb) { if (mrb->gc_disabled) return; GC_INVOKE_TIME_REPORT("mrb_full_gc()"); GC_TIME_START; if (is_generational(mrb)) { /* clear all the old objects back to young */ clear_all_old(mrb); mrb->gc_full = TRUE; } else if (mrb->gc_state != GC_STATE_ROOT) { /* finish half baked GC cycle */ incremental_gc_until(mrb, GC_STATE_ROOT); } incremental_gc_until(mrb, GC_STATE_ROOT); mrb->gc_threshold = (mrb->gc_live_after_mark/100) * mrb->gc_interval_ratio; if (is_generational(mrb)) { mrb->majorgc_old_threshold = mrb->gc_live_after_mark/100 * DEFAULT_MAJOR_GC_INC_RATIO; mrb->gc_full = FALSE; } GC_TIME_STOP_AND_REPORT; } MRB_API void mrb_garbage_collect(mrb_state *mrb) { mrb_full_gc(mrb); } MRB_API int mrb_gc_arena_save(mrb_state *mrb) { return mrb->arena_idx; } MRB_API void mrb_gc_arena_restore(mrb_state *mrb, int idx) { #ifndef MRB_GC_FIXED_ARENA int capa = mrb->arena_capa; if (idx < capa / 2) { capa = (int)(capa * 0.66); if (capa < MRB_GC_ARENA_SIZE) { capa = MRB_GC_ARENA_SIZE; } if (capa != mrb->arena_capa) { mrb->arena = (struct RBasic**)mrb_realloc(mrb, mrb->arena, sizeof(struct RBasic*)*capa); mrb->arena_capa = capa; } } #endif mrb->arena_idx = idx; } /* * Field write barrier * Paint obj(Black) -> value(White) to obj(Black) -> value(Gray). */ MRB_API void mrb_field_write_barrier(mrb_state *mrb, struct RBasic *obj, struct RBasic *value) { if (!is_black(obj)) return; if (!is_white(value)) return; mrb_assert(!is_dead(mrb, value) && !is_dead(mrb, obj)); mrb_assert(is_generational(mrb) || mrb->gc_state != GC_STATE_ROOT); if (is_generational(mrb) || mrb->gc_state == GC_STATE_MARK) { add_gray_list(mrb, value); } else { mrb_assert(mrb->gc_state == GC_STATE_SWEEP); paint_partial_white(mrb, obj); /* for never write barriers */ } } /* * Write barrier * Paint obj(Black) to obj(Gray). * * The object that is painted gray will be traversed atomically in final * mark phase. So you use this write barrier if it's frequency written spot. * e.g. Set element on Array. */ MRB_API void mrb_write_barrier(mrb_state *mrb, struct RBasic *obj) { if (!is_black(obj)) return; mrb_assert(!is_dead(mrb, obj)); mrb_assert(is_generational(mrb) || mrb->gc_state != GC_STATE_ROOT); paint_gray(obj); obj->gcnext = mrb->atomic_gray_list; mrb->atomic_gray_list = obj; } /* * call-seq: * GC.start -> nil * * Initiates full garbage collection. * */ static mrb_value gc_start(mrb_state *mrb, mrb_value obj) { mrb_full_gc(mrb); return mrb_nil_value(); } /* * call-seq: * GC.enable -> true or false * * Enables garbage collection, returning <code>true</code> if garbage * collection was previously disabled. * * GC.disable #=> false * GC.enable #=> true * GC.enable #=> false * */ static mrb_value gc_enable(mrb_state *mrb, mrb_value obj) { mrb_bool old = mrb->gc_disabled; mrb->gc_disabled = FALSE; return mrb_bool_value(old); } /* * call-seq: * GC.disable -> true or false * * Disables garbage collection, returning <code>true</code> if garbage * collection was already disabled. * * GC.disable #=> false * GC.disable #=> true * */ static mrb_value gc_disable(mrb_state *mrb, mrb_value obj) { mrb_bool old = mrb->gc_disabled; mrb->gc_disabled = TRUE; return mrb_bool_value(old); } /* * call-seq: * GC.interval_ratio -> fixnum * * Returns ratio of GC interval. Default value is 200(%). * */ static mrb_value gc_interval_ratio_get(mrb_state *mrb, mrb_value obj) { return mrb_fixnum_value(mrb->gc_interval_ratio); } /* * call-seq: * GC.interval_ratio = fixnum -> nil * * Updates ratio of GC interval. Default value is 200(%). * GC start as soon as after end all step of GC if you set 100(%). * */ static mrb_value gc_interval_ratio_set(mrb_state *mrb, mrb_value obj) { mrb_int ratio; mrb_get_args(mrb, "i", &ratio); mrb->gc_interval_ratio = ratio; return mrb_nil_value(); } /* * call-seq: * GC.step_ratio -> fixnum * * Returns step span ratio of Incremental GC. Default value is 200(%). * */ static mrb_value gc_step_ratio_get(mrb_state *mrb, mrb_value obj) { return mrb_fixnum_value(mrb->gc_step_ratio); } /* * call-seq: * GC.step_ratio = fixnum -> nil * * Updates step span ratio of Incremental GC. Default value is 200(%). * 1 step of incrementalGC becomes long if a rate is big. * */ static mrb_value gc_step_ratio_set(mrb_state *mrb, mrb_value obj) { mrb_int ratio; mrb_get_args(mrb, "i", &ratio); mrb->gc_step_ratio = ratio; return mrb_nil_value(); } static void change_gen_gc_mode(mrb_state *mrb, mrb_bool enable) { if (is_generational(mrb) && !enable) { clear_all_old(mrb); mrb_assert(mrb->gc_state == GC_STATE_ROOT); mrb->gc_full = FALSE; } else if (!is_generational(mrb) && enable) { incremental_gc_until(mrb, GC_STATE_ROOT); mrb->majorgc_old_threshold = mrb->gc_live_after_mark/100 * DEFAULT_MAJOR_GC_INC_RATIO; mrb->gc_full = FALSE; } mrb->is_generational_gc_mode = enable; } /* * call-seq: * GC.generational_mode -> true or false * * Returns generational or normal gc mode. * */ static mrb_value gc_generational_mode_get(mrb_state *mrb, mrb_value self) { return mrb_bool_value(mrb->is_generational_gc_mode); } /* * call-seq: * GC.generational_mode = true or false -> true or false * * Changes to generational or normal gc mode. * */ static mrb_value gc_generational_mode_set(mrb_state *mrb, mrb_value self) { mrb_bool enable; mrb_get_args(mrb, "b", &enable); if (mrb->is_generational_gc_mode != enable) change_gen_gc_mode(mrb, enable); return mrb_bool_value(enable); } void mrb_objspace_each_objects(mrb_state *mrb, mrb_each_object_callback *callback, void *data) { struct heap_page* page = mrb->heaps; while (page != NULL) { RVALUE *p, *pend; p = page->objects; pend = p + MRB_HEAP_PAGE_SIZE; for (;p < pend; p++) { (*callback)(mrb, &p->as.basic, data); } page = page->next; } } #ifdef GC_TEST #ifdef GC_DEBUG static mrb_value gc_test(mrb_state *, mrb_value); #endif #endif void mrb_init_gc(mrb_state *mrb) { struct RClass *gc; gc = mrb_define_module(mrb, "GC"); mrb_define_class_method(mrb, gc, "start", gc_start, MRB_ARGS_NONE()); mrb_define_class_method(mrb, gc, "enable", gc_enable, MRB_ARGS_NONE()); mrb_define_class_method(mrb, gc, "disable", gc_disable, MRB_ARGS_NONE()); mrb_define_class_method(mrb, gc, "interval_ratio", gc_interval_ratio_get, MRB_ARGS_NONE()); mrb_define_class_method(mrb, gc, "interval_ratio=", gc_interval_ratio_set, MRB_ARGS_REQ(1)); mrb_define_class_method(mrb, gc, "step_ratio", gc_step_ratio_get, MRB_ARGS_NONE()); mrb_define_class_method(mrb, gc, "step_ratio=", gc_step_ratio_set, MRB_ARGS_REQ(1)); mrb_define_class_method(mrb, gc, "generational_mode=", gc_generational_mode_set, MRB_ARGS_REQ(1)); mrb_define_class_method(mrb, gc, "generational_mode", gc_generational_mode_get, MRB_ARGS_NONE()); #ifdef GC_TEST #ifdef GC_DEBUG mrb_define_class_method(mrb, gc, "test", gc_test, MRB_ARGS_NONE()); #endif #endif } #ifdef GC_TEST #ifdef GC_DEBUG void test_mrb_field_write_barrier(void) { mrb_state *mrb = mrb_open(); struct RBasic *obj, *value; puts("test_mrb_field_write_barrier"); mrb->is_generational_gc_mode = FALSE; obj = mrb_basic_ptr(mrb_ary_new(mrb)); value = mrb_basic_ptr(mrb_str_new_lit(mrb, "value")); paint_black(obj); paint_partial_white(mrb, value); puts(" in GC_STATE_MARK"); mrb->gc_state = GC_STATE_MARK; mrb_field_write_barrier(mrb, obj, value); mrb_assert(is_gray(value)); puts(" in GC_STATE_SWEEP"); paint_partial_white(mrb, value); mrb->gc_state = GC_STATE_SWEEP; mrb_field_write_barrier(mrb, obj, value); mrb_assert(obj->color & mrb->current_white_part); mrb_assert(value->color & mrb->current_white_part); puts(" fail with black"); mrb->gc_state = GC_STATE_MARK; paint_white(obj); paint_partial_white(mrb, value); mrb_field_write_barrier(mrb, obj, value); mrb_assert(obj->color & mrb->current_white_part); puts(" fail with gray"); mrb->gc_state = GC_STATE_MARK; paint_black(obj); paint_gray(value); mrb_field_write_barrier(mrb, obj, value); mrb_assert(is_gray(value)); { puts("test_mrb_field_write_barrier_value"); obj = mrb_basic_ptr(mrb_ary_new(mrb)); mrb_value value = mrb_str_new_lit(mrb, "value"); paint_black(obj); paint_partial_white(mrb, mrb_basic_ptr(value)); mrb->gc_state = GC_STATE_MARK; mrb_field_write_barrier_value(mrb, obj, value); mrb_assert(is_gray(mrb_basic_ptr(value))); } mrb_close(mrb); } void test_mrb_write_barrier(void) { mrb_state *mrb = mrb_open(); struct RBasic *obj; puts("test_mrb_write_barrier"); obj = mrb_basic_ptr(mrb_ary_new(mrb)); paint_black(obj); puts(" in GC_STATE_MARK"); mrb->gc_state = GC_STATE_MARK; mrb_write_barrier(mrb, obj); mrb_assert(is_gray(obj)); mrb_assert(mrb->atomic_gray_list == obj); puts(" fail with gray"); paint_gray(obj); mrb_write_barrier(mrb, obj); mrb_assert(is_gray(obj)); mrb_close(mrb); } void test_add_gray_list(void) { mrb_state *mrb = mrb_open(); struct RBasic *obj1, *obj2; puts("test_add_gray_list"); change_gen_gc_mode(mrb, FALSE); mrb_assert(mrb->gray_list == NULL); obj1 = mrb_basic_ptr(mrb_str_new_lit(mrb, "test")); add_gray_list(mrb, obj1); mrb_assert(mrb->gray_list == obj1); mrb_assert(is_gray(obj1)); obj2 = mrb_basic_ptr(mrb_str_new_lit(mrb, "test")); add_gray_list(mrb, obj2); mrb_assert(mrb->gray_list == obj2); mrb_assert(mrb->gray_list->gcnext == obj1); mrb_assert(is_gray(obj2)); mrb_close(mrb); } void test_gc_gray_mark(void) { mrb_state *mrb = mrb_open(); mrb_value obj_v, value_v; struct RBasic *obj; size_t gray_num = 0; puts("test_gc_gray_mark"); puts(" in MRB_TT_CLASS"); obj = (struct RBasic*)mrb->object_class; paint_gray(obj); gray_num = gc_gray_mark(mrb, obj); mrb_assert(is_black(obj)); mrb_assert(gray_num > 1); puts(" in MRB_TT_ARRAY"); obj_v = mrb_ary_new(mrb); value_v = mrb_str_new_lit(mrb, "test"); paint_gray(mrb_basic_ptr(obj_v)); paint_partial_white(mrb, mrb_basic_ptr(value_v)); mrb_ary_push(mrb, obj_v, value_v); gray_num = gc_gray_mark(mrb, mrb_basic_ptr(obj_v)); mrb_assert(is_black(mrb_basic_ptr(obj_v))); mrb_assert(is_gray(mrb_basic_ptr(value_v))); mrb_assert(gray_num == 1); mrb_close(mrb); } void test_incremental_gc(void) { mrb_state *mrb = mrb_open(); size_t max = ~0, live = 0, total = 0, freed = 0; RVALUE *free; struct heap_page *page; puts("test_incremental_gc"); change_gen_gc_mode(mrb, FALSE); puts(" in mrb_full_gc"); mrb_full_gc(mrb); mrb_assert(mrb->gc_state == GC_STATE_ROOT); puts(" in GC_STATE_ROOT"); incremental_gc(mrb, max); mrb_assert(mrb->gc_state == GC_STATE_MARK); puts(" in GC_STATE_MARK"); incremental_gc_until(mrb, GC_STATE_SWEEP); mrb_assert(mrb->gc_state == GC_STATE_SWEEP); puts(" in GC_STATE_SWEEP"); page = mrb->heaps; while (page) { RVALUE *p = page->objects; RVALUE *e = p + MRB_HEAP_PAGE_SIZE; while (p<e) { if (is_black(&p->as.basic)) { live++; } if (is_gray(&p->as.basic) && !is_dead(mrb, &p->as.basic)) { printf("%p\n", &p->as.basic); } p++; } page = page->next; total += MRB_HEAP_PAGE_SIZE; } mrb_assert(mrb->gray_list == NULL); incremental_gc(mrb, max); mrb_assert(mrb->gc_state == GC_STATE_SWEEP); incremental_gc(mrb, max); mrb_assert(mrb->gc_state == GC_STATE_ROOT); free = (RVALUE*)mrb->heaps->freelist; while (free) { freed++; free = (RVALUE*)free->as.free.next; } mrb_assert(mrb->live == live); mrb_assert(mrb->live == total-freed); puts("test_incremental_gc(gen)"); incremental_gc_until(mrb, GC_STATE_SWEEP); change_gen_gc_mode(mrb, TRUE); mrb_assert(mrb->gc_full == FALSE); mrb_assert(mrb->gc_state == GC_STATE_ROOT); puts(" in minor"); mrb_assert(is_minor_gc(mrb)); mrb_assert(mrb->majorgc_old_threshold > 0); mrb->majorgc_old_threshold = 0; mrb_incremental_gc(mrb); mrb_assert(mrb->gc_full == TRUE); mrb_assert(mrb->gc_state == GC_STATE_ROOT); puts(" in major"); mrb_assert(is_major_gc(mrb)); do { mrb_incremental_gc(mrb); } while (mrb->gc_state != GC_STATE_ROOT); mrb_assert(mrb->gc_full == FALSE); mrb_close(mrb); } void test_incremental_sweep_phase(void) { mrb_state *mrb = mrb_open(); puts("test_incremental_sweep_phase"); add_heap(mrb); mrb->sweeps = mrb->heaps; mrb_assert(mrb->heaps->next->next == NULL); mrb_assert(mrb->free_heaps->next->next == NULL); incremental_sweep_phase(mrb, MRB_HEAP_PAGE_SIZE*3); mrb_assert(mrb->heaps->next == NULL); mrb_assert(mrb->heaps == mrb->free_heaps); mrb_close(mrb); } static mrb_value gc_test(mrb_state *mrb, mrb_value self) { test_mrb_field_write_barrier(); test_mrb_write_barrier(); test_add_gray_list(); test_gc_gray_mark(); test_incremental_gc(); test_incremental_sweep_phase(); return mrb_nil_value(); } #endif /* GC_DEBUG */ #endif /* GC_TEST */