diff options
Diffstat (limited to 'src/gc.c')
| -rw-r--r-- | src/gc.c | 1364 |
1 files changed, 694 insertions, 670 deletions
@@ -5,18 +5,27 @@ */ #include <string.h> +#ifdef MRB_USE_MALLOC_TRIM +#include <malloc.h> +#endif +#include <mruby.h> +#include <mruby/array.h> +#include <mruby/class.h> +#include <mruby/data.h> +#include <mruby/istruct.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> +#include <mruby/throw.h> +#include <mruby/presym.h> + +#ifdef MRB_GC_STRESS #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" +#endif /* = Tri-color Incremental Garbage Collection @@ -33,9 +42,14 @@ * Gray - Marked, But the child objects are unmarked. * Black - Marked, the child objects are also marked. + Extra color + + * Red - Static (ROM object) no need to be collected. + - All child objects should be Red as well. + == Two White Types - There're two white color types in a flip-flop fashion: White-A and White-B, + There are 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). @@ -63,12 +77,13 @@ == Write Barrier - mruby implementer and C extension library writer must write a write - barrier when writing a pointer to an object on object's field. - Two different write barrier are available: + 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 - * mrb_write_barrier + * mrb_field_write_barrier - target B object for a mark. + * mrb_write_barrier - target A object for a mark. == Generational Mode @@ -96,8 +111,14 @@ struct free_obj { struct RBasic *next; }; +struct RVALUE_initializer { + MRB_OBJECT_HEADER; + char padding[sizeof(void*) * 4 - sizeof(uint32_t)]; +}; + typedef struct { union { + struct RVALUE_initializer init; /* must be first member to ensure initialization */ struct free_obj free; struct RBasic basic; struct RObject object; @@ -107,12 +128,12 @@ typedef struct { struct RHash hash; struct RRange range; struct RData data; + struct RIStruct istruct; struct RProc proc; + struct REnv env; + struct RFiber fiber; struct RException exc; -#ifdef MRB_WORD_BOXING - struct RFloat floatv; - struct RCptr cptr; -#endif + struct RBreak brk; } as; } RVALUE; @@ -135,8 +156,8 @@ gettimeofday_time(void) #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));\ + fprintf(stderr, "is_generational: %d\n", is_generational(gc));\ + fprintf(stderr, "is_major_gc: %d\n", is_major_gc(gc));\ } while(0) #define GC_TIME_START do {\ @@ -146,10 +167,10 @@ gettimeofday_time(void) #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_state: %d\n", gc->state);\ + fprintf(stderr, "live: %zu\n", gc->live);\ + fprintf(stderr, "majorgc_old_threshold: %zu\n", gc->majorgc_old_threshold);\ + fprintf(stderr, "gc_threshold: %zu\n", 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) @@ -165,16 +186,45 @@ gettimeofday_time(void) #define DEBUG(x) #endif -#define GC_STEP_SIZE 1024 +#ifndef MRB_HEAP_PAGE_SIZE +#define MRB_HEAP_PAGE_SIZE 1024 +#endif +#define GC_STEP_SIZE 1024 -void* +/* white: 001 or 010, black: 100, gray: 000 */ +#define GC_GRAY 0 +#define GC_WHITE_A 1 +#define GC_WHITE_B (1 << 1) +#define GC_BLACK (1 << 2) +#define GC_RED MRB_GC_RED +#define GC_WHITES (GC_WHITE_A | GC_WHITE_B) +#define GC_COLOR_MASK 7 +mrb_static_assert1(MRB_GC_RED <= GC_COLOR_MASK); + +#define paint_gray(o) ((o)->color = GC_GRAY) +#define paint_black(o) ((o)->color = GC_BLACK) +#define paint_white(o) ((o)->color = GC_WHITES) +#define paint_partial_white(s, o) ((o)->color = (s)->current_white_part) +#define is_gray(o) ((o)->color == GC_GRAY) +#define is_white(o) ((o)->color & GC_WHITES) +#define is_black(o) ((o)->color == GC_BLACK) +#define is_red(o) ((o)->color == GC_RED) +#define flip_white_part(s) ((s)->current_white_part = other_white_part(s)) +#define other_white_part(s) ((s)->current_white_part ^ GC_WHITES) +#define is_dead(s, o) (((o)->color & other_white_part(s) & GC_WHITES) || (o)->tt == MRB_TT_FREE) + +#define objects(p) ((RVALUE *)p->objects) + +mrb_noreturn void mrb_raise_nomemory(mrb_state *mrb); + +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) { + if (!p2 && len > 0 && mrb->gc.heaps) { mrb_full_gc(mrb); p2 = (mrb->allocf)(mrb, p, len, mrb->allocf_ud); } @@ -182,42 +232,37 @@ mrb_realloc_simple(mrb_state *mrb, void *p, size_t len) return p2; } - -void* +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)); - } + if (len == 0) return p2; + if (p2 == NULL) { + mrb->gc.out_of_memory = TRUE; + mrb_raise_nomemory(mrb); } else { - mrb->out_of_memory = FALSE; + mrb->gc.out_of_memory = FALSE; } return p2; } -void* +MRB_API void* mrb_malloc(mrb_state *mrb, size_t len) { return mrb_realloc(mrb, 0, len); } -void* +MRB_API void* mrb_malloc_simple(mrb_state *mrb, size_t len) { return mrb_realloc_simple(mrb, 0, len); } -void* +MRB_API void* mrb_calloc(mrb_state *mrb, size_t nelem, size_t len) { void *p; @@ -226,11 +271,9 @@ mrb_calloc(mrb_state *mrb, size_t nelem, size_t len) nelem <= SIZE_MAX / len) { size_t size; size = nelem * len; - p = mrb_realloc(mrb, 0, size); + p = mrb_malloc(mrb, size); - if (p) { - memset(p, 0, size); - } + memset(p, 0, size); } else { p = NULL; @@ -239,107 +282,133 @@ mrb_calloc(mrb_state *mrb, size_t nelem, size_t len) return p; } -void +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 +MRB_API void* +mrb_alloca(mrb_state *mrb, size_t size) +{ + struct RString *s; + s = MRB_OBJ_ALLOC(mrb, MRB_TT_STRING, mrb->string_class); + return s->as.heap.ptr = (char*)mrb_malloc(mrb, size); +} -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 mrb_bool +heap_p(mrb_gc *gc, struct RBasic *object) +{ + mrb_heap_page* page; + + page = gc->heaps; + while (page) { + RVALUE *p; + + p = objects(page); + if (&p[0].as.basic <= object && object <= &p[MRB_HEAP_PAGE_SIZE].as.basic) { + return TRUE; + } + page = page->next; + } + return FALSE; +} + +MRB_API mrb_bool +mrb_object_dead_p(mrb_state *mrb, struct RBasic *object) { + mrb_gc *gc = &mrb->gc; + if (!heap_p(gc, object)) return TRUE; + return is_dead(gc, object); +} static void -link_heap_page(mrb_state *mrb, struct heap_page *page) +link_heap_page(mrb_gc *gc, mrb_heap_page *page) { - page->next = mrb->heaps; - if (mrb->heaps) - mrb->heaps->prev = page; - mrb->heaps = page; + page->next = gc->heaps; + if (gc->heaps) + gc->heaps->prev = page; + gc->heaps = page; } static void -unlink_heap_page(mrb_state *mrb, struct heap_page *page) +unlink_heap_page(mrb_gc *gc, mrb_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; + if (gc->heaps == page) + gc->heaps = page->next; page->prev = NULL; page->next = NULL; } static void -link_free_heap_page(mrb_state *mrb, struct heap_page *page) +link_free_heap_page(mrb_gc *gc, mrb_heap_page *page) { - page->free_next = mrb->free_heaps; - if (mrb->free_heaps) { - mrb->free_heaps->free_prev = page; + page->free_next = gc->free_heaps; + if (gc->free_heaps) { + gc->free_heaps->free_prev = page; } - mrb->free_heaps = page; + gc->free_heaps = page; } static void -unlink_free_heap_page(mrb_state *mrb, struct heap_page *page) +unlink_free_heap_page(mrb_gc *gc, mrb_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; + if (gc->free_heaps == page) + gc->free_heaps = page->free_next; page->free_prev = NULL; page->free_next = NULL; } static void -add_heap(mrb_state *mrb) +add_heap(mrb_state *mrb, mrb_gc *gc) { - struct heap_page *page = (struct heap_page *)mrb_calloc(mrb, 1, sizeof(struct heap_page)); + mrb_heap_page *page = (mrb_heap_page *)mrb_calloc(mrb, 1, sizeof(mrb_heap_page) + MRB_HEAP_PAGE_SIZE * sizeof(RVALUE)); RVALUE *p, *e; struct RBasic *prev = NULL; - for (p = page->objects, e=p+MRB_HEAP_PAGE_SIZE; p<e; p++) { + for (p = objects(page), 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); + link_heap_page(gc, page); + link_free_heap_page(gc, 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) +#define MAJOR_GC_INC_RATIO 120 +#define MAJOR_GC_TOOMANY 10000 +#define is_generational(gc) ((gc)->generational) +#define is_major_gc(gc) (is_generational(gc) && (gc)->full) +#define is_minor_gc(gc) (is_generational(gc) && !(gc)->full) void -mrb_init_heap(mrb_state *mrb) +mrb_gc_init(mrb_state *mrb, mrb_gc *gc) { - 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_FIXED_ARENA + gc->arena = (struct RBasic**)mrb_malloc(mrb, sizeof(struct RBasic*)*MRB_GC_ARENA_SIZE); + gc->arena_capa = MRB_GC_ARENA_SIZE; +#endif + + gc->current_white_part = GC_WHITE_A; + gc->heaps = NULL; + gc->free_heaps = NULL; + add_heap(mrb, gc); + gc->interval_ratio = DEFAULT_GC_INTERVAL_RATIO; + gc->step_ratio = DEFAULT_GC_STEP_RATIO; #ifndef MRB_GC_TURN_OFF_GENERATIONAL - mrb->is_generational_gc_mode = TRUE; - mrb->gc_full = TRUE; + gc->generational = TRUE; + gc->full = TRUE; #endif #ifdef GC_PROFILE @@ -347,85 +416,178 @@ mrb_init_heap(mrb_state *mrb) #endif } -static void obj_free(mrb_state *mrb, struct RBasic *obj); +static void obj_free(mrb_state *mrb, struct RBasic *obj, int end); -void -mrb_free_heap(mrb_state *mrb) +static void +free_heap(mrb_state *mrb, mrb_gc *gc) { - struct heap_page *page = mrb->heaps; - struct heap_page *tmp; + mrb_heap_page *page = gc->heaps; + mrb_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++) { + for (p = objects(tmp), e=p+MRB_HEAP_PAGE_SIZE; p<e; p++) { if (p->as.free.tt != MRB_TT_FREE) - obj_free(mrb, &p->as.basic); + obj_free(mrb, &p->as.basic, TRUE); } mrb_free(mrb, tmp); } } +void +mrb_gc_destroy(mrb_state *mrb, mrb_gc *gc) +{ + free_heap(mrb, gc); +#ifndef MRB_GC_FIXED_ARENA + mrb_free(mrb, gc->arena); +#endif +} + static void -gc_protect(mrb_state *mrb, struct RBasic *p) +gc_protect(mrb_state *mrb, mrb_gc *gc, struct RBasic *p) { #ifdef MRB_GC_FIXED_ARENA - if (mrb->arena_idx >= MRB_GC_ARENA_SIZE) { + if (gc->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"); + gc->arena_idx = MRB_GC_ARENA_SIZE - 4; /* force room in arena */ + mrb_exc_raise(mrb, mrb_obj_value(mrb->arena_err)); } #else - if (mrb->arena_idx >= mrb->arena_capa) { + if (gc->arena_idx >= gc->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); + gc->arena_capa = (int)(gc->arena_capa * 3 / 2); + gc->arena = (struct RBasic**)mrb_realloc(mrb, gc->arena, sizeof(struct RBasic*)*gc->arena_capa); } #endif - mrb->arena[mrb->arena_idx++] = p; + gc->arena[gc->arena_idx++] = p; } -void +/* mrb_gc_protect() leaves the object in the arena */ +MRB_API void mrb_gc_protect(mrb_state *mrb, mrb_value obj) { - if (mrb_special_const_p(obj)) return; - gc_protect(mrb, mrb_basic_ptr(obj)); + if (mrb_immediate_p(obj)) return; + gc_protect(mrb, &mrb->gc, mrb_basic_ptr(obj)); +} + +#define GC_ROOT_SYM MRB_SYM(_gc_root_) + +/* mrb_gc_register() keeps the object from GC. + + Register your object when it's exported to C world, + without reference from Ruby world, e.g. callback + arguments. Don't forget to remove the object using + mrb_gc_unregister, otherwise your object will leak. +*/ + +MRB_API void +mrb_gc_register(mrb_state *mrb, mrb_value obj) +{ + mrb_sym root; + mrb_value table; + + if (mrb_immediate_p(obj)) return; + root = GC_ROOT_SYM; + table = mrb_gv_get(mrb, root); + if (mrb_nil_p(table) || !mrb_array_p(table)) { + table = mrb_ary_new(mrb); + mrb_gv_set(mrb, root, table); + } + mrb_ary_push(mrb, table, obj); +} + +/* mrb_gc_unregister() removes the object from GC root. */ +MRB_API void +mrb_gc_unregister(mrb_state *mrb, mrb_value obj) +{ + mrb_sym root; + mrb_value table; + struct RArray *a; + mrb_int i; + + if (mrb_immediate_p(obj)) return; + root = GC_ROOT_SYM; + table = mrb_gv_get(mrb, root); + if (mrb_nil_p(table)) return; + if (!mrb_array_p(table)) { + mrb_gv_set(mrb, root, mrb_nil_value()); + return; + } + a = mrb_ary_ptr(table); + mrb_ary_modify(mrb, a); + for (i = 0; i < ARY_LEN(a); i++) { + if (mrb_ptr(ARY_PTR(a)[i]) == mrb_ptr(obj)) { + mrb_int len = ARY_LEN(a)-1; + mrb_value *ptr = ARY_PTR(a); + + ARY_SET_LEN(a, len); + memmove(&ptr[i], &ptr[i + 1], (len - i) * sizeof(mrb_value)); + break; + } + } } -struct RBasic* +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 } } }; + static const RVALUE RVALUE_zero = { { { NULL, NULL, MRB_TT_FALSE } } }; + mrb_gc *gc = &mrb->gc; + + if (cls) { + enum mrb_vtype tt; + + switch (cls->tt) { + case MRB_TT_CLASS: + case MRB_TT_SCLASS: + case MRB_TT_MODULE: + case MRB_TT_ENV: + break; + default: + mrb_raise(mrb, E_TYPE_ERROR, "allocation failure"); + } + tt = MRB_INSTANCE_TT(cls); + if (tt != MRB_TT_FALSE && + ttype != MRB_TT_SCLASS && + ttype != MRB_TT_ICLASS && + ttype != MRB_TT_ENV && + ttype != tt) { + mrb_raisef(mrb, E_TYPE_ERROR, "allocation failure of %C", cls); + } + } + if (ttype <= MRB_TT_FREE) { + mrb_raisef(mrb, E_TYPE_ERROR, "allocation failure of %C (type %d)", cls, (int)ttype); + } #ifdef MRB_GC_STRESS mrb_full_gc(mrb); #endif - if (mrb->gc_threshold < mrb->live) { + if (gc->threshold < gc->live) { mrb_incremental_gc(mrb); } - if (mrb->free_heaps == NULL) { - add_heap(mrb); + if (gc->free_heaps == NULL) { + add_heap(mrb, gc); } - 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); + p = gc->free_heaps->freelist; + gc->free_heaps->freelist = ((struct free_obj*)p)->next; + if (gc->free_heaps->freelist == NULL) { + unlink_free_heap_page(gc, gc->free_heaps); } - mrb->live++; - gc_protect(mrb, p); + gc->live++; + gc_protect(mrb, gc, p); *(RVALUE *)p = RVALUE_zero; p->tt = ttype; p->c = cls; - paint_partial_white(mrb, p); + paint_partial_white(gc, p); return p; } static inline void -add_gray_list(mrb_state *mrb, struct RBasic *obj) +add_gray_list(mrb_state *mrb, mrb_gc *gc, struct RBasic *obj) { #ifdef MRB_GC_STRESS if (obj->tt > MRB_TT_MAXDEFINE) { @@ -433,73 +595,82 @@ add_gray_list(mrb_state *mrb, struct RBasic *obj) } #endif paint_gray(obj); - obj->gcnext = mrb->gray_list; - mrb->gray_list = obj; + obj->gcnext = gc->gray_list; + gc->gray_list = obj; } +mrb_int mrb_ci_nregs(mrb_callinfo *ci); + static void mark_context_stack(mrb_state *mrb, struct mrb_context *c) { size_t i; size_t e; + mrb_value nil; - e = c->stack - c->stbase; - if (c->ci) e += c->ci->nregs; + if (c->stbase == NULL) return; + if (c->ci) { + e = (c->ci->stack ? c->ci->stack - c->stbase : 0); + e += mrb_ci_nregs(c->ci); + } + else { + e = 0; + } 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)); - } + mrb_gc_mark(mrb, mrb_basic_ptr(v)); } } + e = c->stend - c->stbase; + nil = mrb_nil_value(); + for (; i<e; i++) { + c->stbase[i] = nil; + } } 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); + start: + if (c->status == MRB_FIBER_TERMINATED) return; /* mark VM stack */ + mark_context_stack(mrb, c); + + /* mark call 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); + mrb_gc_mark(mrb, (struct RBasic*)ci->u.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); + mrb_gc_mark(mrb, (struct RBasic*)c->fib); + if (c->prev) { + c = c->prev; + goto start; } } static void -gc_mark_children(mrb_state *mrb, struct RBasic *obj) +gc_mark_children(mrb_state *mrb, mrb_gc *gc, 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); + { + struct RClass *c = (struct RClass*)obj; + if (MRB_FLAG_TEST(c, MRB_FL_CLASS_IS_ORIGIN)) + mrb_gc_mark_mt(mrb, c); + mrb_gc_mark(mrb, (struct RBasic*)((struct RClass*)obj)->super); + } break; case MRB_TT_CLASS: @@ -522,22 +693,22 @@ gc_mark_children(mrb_state *mrb, struct RBasic *obj) { struct RProc *p = (struct RProc*)obj; - mrb_gc_mark(mrb, (struct RBasic*)p->env); - mrb_gc_mark(mrb, (struct RBasic*)p->target_class); + mrb_gc_mark(mrb, (struct RBasic*)p->upper); + mrb_gc_mark(mrb, (struct RBasic*)p->e.env); } break; case MRB_TT_ENV: { struct REnv *e = (struct REnv*)obj; + mrb_int i, len; - 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]); - } + if (MRB_ENV_ONSTACK_P(e) && e->cxt && e->cxt->fib) { + mrb_gc_mark(mrb, (struct RBasic*)e->cxt->fib); + } + len = MRB_ENV_LEN(e); + for (i=0; i<len; i++) { + mrb_gc_mark_value(mrb, e->stack[i]); } } break; @@ -550,13 +721,15 @@ gc_mark_children(mrb_state *mrb, struct RBasic *obj) } break; + case MRB_TT_STRUCT: case MRB_TT_ARRAY: { struct RArray *a = (struct RArray*)obj; - size_t i, e; + size_t i, e=ARY_LEN(a); + mrb_value *p = ARY_PTR(a); - for (i=0,e=a->len; i<e; i++) { - mrb_gc_mark_value(mrb, a->ptr[i]); + for (i=0; i<e; i++) { + mrb_gc_mark_value(mrb, p[i]); } } break; @@ -567,16 +740,21 @@ gc_mark_children(mrb_state *mrb, struct RBasic *obj) break; case MRB_TT_STRING: + if (RSTR_FSHARED_P(obj)) { + struct RString *s = (struct RString*)obj; + mrb_gc_mark(mrb, (struct RBasic*)s->as.heap.aux.fshared); + } break; case MRB_TT_RANGE: - { - struct RRange *r = (struct RRange*)obj; + mrb_gc_mark_range(mrb, (struct RRange*)obj); + break; - if (r->edges) { - mrb_gc_mark_value(mrb, r->edges->beg); - mrb_gc_mark_value(mrb, r->edges->end); - } + case MRB_TT_BREAK: + { + struct RBreak *brk = (struct RBreak*)obj; + mrb_gc_mark(mrb, (struct RBasic*)mrb_break_proc_get(brk)); + mrb_gc_mark_value(mrb, mrb_break_value_get(brk)); } break; @@ -592,35 +770,25 @@ gc_mark_children(mrb_state *mrb, struct RBasic *obj) } } -void +MRB_API void mrb_gc_mark(mrb_state *mrb, struct RBasic *obj) { if (obj == 0) return; if (!is_white(obj)) return; + if (is_red(obj)) return; mrb_assert((obj)->tt != MRB_TT_FREE); - add_gray_list(mrb, obj); + add_gray_list(mrb, &mrb->gc, obj); } static void -obj_free(mrb_state *mrb, struct RBasic *obj) +obj_free(mrb_state *mrb, struct RBasic *obj, int end) { - DEBUG(printf("obj_free(%p,tt=%d)\n",obj,obj->tt)); + DEBUG(fprintf(stderr, "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 + case MRB_TT_OBJECT: + mrb_gc_free_iv(mrb, (struct RObject*)obj); break; -#else - return; -#endif - case MRB_TT_OBJECT: case MRB_TT_EXCEPTION: mrb_gc_free_iv(mrb, (struct RObject*)obj); break; @@ -630,16 +798,26 @@ obj_free(mrb_state *mrb, struct RBasic *obj) case MRB_TT_SCLASS: mrb_gc_free_mt(mrb, (struct RClass*)obj); mrb_gc_free_iv(mrb, (struct RObject*)obj); + if (!end) + mrb_mc_clear_by_class(mrb, (struct RClass*)obj); + break; + case MRB_TT_ICLASS: + if (MRB_FLAG_TEST(obj, MRB_FL_CLASS_IS_ORIGIN)) + mrb_gc_free_mt(mrb, (struct RClass*)obj); + if (!end) + mrb_mc_clear_by_class(mrb, (struct RClass*)obj); break; - case MRB_TT_ENV: { struct REnv *e = (struct REnv*)obj; - if (!MRB_ENV_STACK_SHARED_P(e)) { - mrb_free(mrb, e->stack); + if (MRB_ENV_ONSTACK_P(e)) { + /* cannot be freed */ e->stack = NULL; + break; } + mrb_free(mrb, e->stack); + e->stack = NULL; } break; @@ -647,16 +825,31 @@ obj_free(mrb_state *mrb, struct RBasic *obj) { struct mrb_context *c = ((struct RFiber*)obj)->cxt; - if (c != mrb->root_c) + if (c && c != mrb->root_c) { + if (!end && c->status != MRB_FIBER_TERMINATED) { + mrb_callinfo *ci = c->ci; + mrb_callinfo *ce = c->cibase; + + while (ce <= ci) { + struct REnv *e = ci->u.env; + if (e && !mrb_object_dead_p(mrb, (struct RBasic*)e) && + e->tt == MRB_TT_ENV && MRB_ENV_ONSTACK_P(e)) { + mrb_env_unshare(mrb, e); + } + ci--; + } + } mrb_free_context(mrb, c); + } } break; + case MRB_TT_STRUCT: case MRB_TT_ARRAY: - if (obj->flags & MRB_ARY_SHARED) - mrb_ary_decref(mrb, ((struct RArray*)obj)->aux.shared); - else - mrb_free(mrb, ((struct RArray*)obj)->ptr); + if (ARY_SHARED_P(obj)) + mrb_ary_decref(mrb, ((struct RArray*)obj)->as.heap.aux.shared); + else if (!ARY_EMBED_P(obj)) + mrb_free(mrb, ((struct RArray*)obj)->as.heap.ptr); break; case MRB_TT_HASH: @@ -673,13 +866,17 @@ obj_free(mrb_state *mrb, struct RBasic *obj) struct RProc *p = (struct RProc*)obj; if (!MRB_PROC_CFUNC_P(p) && p->body.irep) { - mrb_irep_decref(mrb, p->body.irep); + mrb_irep *irep = (mrb_irep*)p->body.irep; + if (end) { + mrb_irep_cutref(mrb, irep); + } + mrb_irep_decref(mrb, irep); } } break; case MRB_TT_RANGE: - mrb_free(mrb, ((struct RRange*)obj)->edges); + mrb_gc_free_range(mrb, ((struct RRange*)obj)); break; case MRB_TT_DATA: @@ -692,6 +889,24 @@ obj_free(mrb_state *mrb, struct RBasic *obj) } break; +#if defined(MRB_USE_RATIONAL) && defined(MRB_INT64) && defined(MRB_32BIT) + case MRB_TT_RATIONAL: + { + struct RData *o = (struct RData*)obj; + mrb_free(mrb, o->iv); + } + break; +#endif + +#if defined(MRB_USE_COMPLEX) && defined(MRB_32BIT) && !defined(MRB_USE_FLOAT32) + case MRB_TT_COMPLEX: + { + struct RData *o = (struct RData*)obj; + mrb_free(mrb, o->iv); + } + break; +#endif + default: break; } @@ -699,45 +914,68 @@ obj_free(mrb_state *mrb, struct RBasic *obj) } static void -root_scan_phase(mrb_state *mrb) +root_scan_phase(mrb_state *mrb, mrb_gc *gc) { - size_t i, e; + int i, e; - if (!is_minor_gc(mrb)) { - mrb->gray_list = NULL; - mrb->atomic_gray_list = NULL; + if (!is_minor_gc(gc)) { + gc->gray_list = NULL; + gc->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]); + for (i=0,e=gc->arena_idx; i<e; i++) { + mrb_gc_mark(mrb, gc->arena[i]); } /* mark class hierarchy */ mrb_gc_mark(mrb, (struct RBasic*)mrb->object_class); + + /* mark built-in classes */ + mrb_gc_mark(mrb, (struct RBasic*)mrb->class_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->module_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->proc_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->string_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->array_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->hash_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->range_class); + +#ifndef MRB_NO_FLOAT + mrb_gc_mark(mrb, (struct RBasic*)mrb->float_class); +#endif + mrb_gc_mark(mrb, (struct RBasic*)mrb->integer_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->true_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->false_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->nil_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->symbol_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->kernel_module); + + mrb_gc_mark(mrb, (struct RBasic*)mrb->eException_class); + mrb_gc_mark(mrb, (struct RBasic*)mrb->eStandardError_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); + mrb_gc_mark(mrb, (struct RBasic*)mrb->stack_err); +#ifdef MRB_GC_FIXED_ARENA + mrb_gc_mark(mrb, (struct RBasic*)mrb->arena_err); +#endif - mark_context(mrb, mrb->root_c); - if (mrb->root_c->fib) { - mrb_gc_mark(mrb, (struct RBasic*)mrb->root_c->fib); - } + mark_context(mrb, mrb->c); if (mrb->root_c != mrb->c) { - mark_context(mrb, mrb->c); + mark_context(mrb, mrb->root_c); } } +/* rough estimation of number of GC marks (non recursive) */ static size_t -gc_gray_mark(mrb_state *mrb, struct RBasic *obj) +gc_gray_counts(mrb_state *mrb, mrb_gc *gc, struct RBasic *obj) { size_t children = 0; - gc_mark_children(mrb, obj); - switch (obj->tt) { case MRB_TT_ICLASS: children++; @@ -761,7 +999,7 @@ gc_gray_mark(mrb_state *mrb, struct RBasic *obj) break; case MRB_TT_ENV: - children += (int)obj->flags; + children += MRB_ENV_LEN(obj); break; case MRB_TT_FIBER: @@ -770,16 +1008,17 @@ gc_gray_mark(mrb_state *mrb, struct RBasic *obj) size_t i; mrb_callinfo *ci; - if (!c) break; + if (!c || c->status == MRB_FIBER_TERMINATED) break; + /* mark stack */ - i = c->stack - c->stbase; - if (c->ci) i += c->ci->nregs; + i = c->ci->stack - c->stbase; + + if (c->ci) { + i += mrb_ci_nregs(c->ci); + } 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++) @@ -789,10 +1028,11 @@ gc_gray_mark(mrb_state *mrb, struct RBasic *obj) } break; + case MRB_TT_STRUCT: case MRB_TT_ARRAY: { struct RArray *a = (struct RArray*)obj; - children += a->len; + children += ARY_LEN(a); } break; @@ -803,6 +1043,7 @@ gc_gray_mark(mrb_state *mrb, struct RBasic *obj) case MRB_TT_PROC: case MRB_TT_RANGE: + case MRB_TT_BREAK: children+=2; break; @@ -821,133 +1062,151 @@ gc_gray_mark(mrb_state *mrb, struct RBasic *obj) 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; +gc_mark_gray_list(mrb_state *mrb, mrb_gc *gc) { + while (gc->gray_list) { + struct RBasic *obj = gc->gray_list; + gc->gray_list = obj->gcnext; + gc_mark_children(mrb, gc, obj); } } static size_t -incremental_marking_phase(mrb_state *mrb, size_t limit) +incremental_marking_phase(mrb_state *mrb, mrb_gc *gc, size_t limit) { size_t tried_marks = 0; - while (mrb->gray_list && tried_marks < limit) { - tried_marks += gc_gray_mark(mrb, mrb->gray_list); + while (gc->gray_list && tried_marks < limit) { + struct RBasic *obj = gc->gray_list; + gc->gray_list = obj->gcnext; + gc_mark_children(mrb, gc, obj); + tried_marks += gc_gray_counts(mrb, gc, obj); } return tried_marks; } static void -final_marking_phase(mrb_state *mrb) +final_marking_phase(mrb_state *mrb, mrb_gc *gc) { - 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); + int i, e; + + /* mark arena */ + for (i=0,e=gc->arena_idx; i<e; i++) { + mrb_gc_mark(mrb, gc->arena[i]); + } + mrb_gc_mark_gv(mrb); + mark_context(mrb, mrb->c); + if (mrb->c != mrb->root_c) { + mark_context(mrb, mrb->root_c); + } + mrb_gc_mark(mrb, (struct RBasic*)mrb->exc); + gc_mark_gray_list(mrb, gc); + mrb_assert(gc->gray_list == NULL); + gc->gray_list = gc->atomic_gray_list; + gc->atomic_gray_list = NULL; + gc_mark_gray_list(mrb, gc); + mrb_assert(gc->gray_list == NULL); } static void -prepare_incremental_sweep(mrb_state *mrb) +prepare_incremental_sweep(mrb_state *mrb, mrb_gc *gc) { - mrb->gc_state = GC_STATE_SWEEP; - mrb->sweeps = mrb->heaps; - mrb->gc_live_after_mark = mrb->live; + gc->state = MRB_GC_STATE_SWEEP; + gc->sweeps = gc->heaps; + gc->live_after_mark = gc->live; } static size_t -incremental_sweep_phase(mrb_state *mrb, size_t limit) +incremental_sweep_phase(mrb_state *mrb, mrb_gc *gc, size_t limit) { - struct heap_page *page = mrb->sweeps; + mrb_heap_page *page = gc->sweeps; size_t tried_sweep = 0; while (page && (tried_sweep < limit)) { - RVALUE *p = page->objects; + RVALUE *p = objects(page); RVALUE *e = p + MRB_HEAP_PAGE_SIZE; size_t freed = 0; mrb_bool dead_slot = TRUE; - int full = (page->freelist == NULL); + mrb_bool full = (page->freelist == NULL); - if (is_minor_gc(mrb) && page->old) { + if (is_minor_gc(gc) && 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 (is_dead(gc, &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++; + obj_free(mrb, &p->as.basic, FALSE); + if (p->as.basic.tt == MRB_TT_FREE) { + p->as.free.next = page->freelist; + page->freelist = (struct RBasic*)p; + freed++; + } + else { + dead_slot = FALSE; + } } } else { - if (!is_generational(mrb)) - paint_partial_white(mrb, &p->as.basic); /* next gc target */ - dead_slot = 0; + if (!is_generational(gc)) + paint_partial_white(gc, &p->as.basic); /* next gc target */ + dead_slot = FALSE; } p++; } /* free dead slot */ if (dead_slot && freed < MRB_HEAP_PAGE_SIZE) { - struct heap_page *next = page->next; + mrb_heap_page *next = page->next; - unlink_heap_page(mrb, page); - unlink_free_heap_page(mrb, page); + unlink_heap_page(gc, page); + unlink_free_heap_page(gc, page); mrb_free(mrb, page); page = next; } else { if (full && freed > 0) { - link_free_heap_page(mrb, page); + link_free_heap_page(gc, page); } - if (page->freelist == NULL && is_minor_gc(mrb)) + if (page->freelist == NULL && is_minor_gc(gc)) 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; + gc->live -= freed; + gc->live_after_mark -= freed; } - mrb->sweeps = page; + gc->sweeps = page; return tried_sweep; } static size_t -incremental_gc(mrb_state *mrb, size_t limit) +incremental_gc(mrb_state *mrb, mrb_gc *gc, size_t limit) { - switch (mrb->gc_state) { - case GC_STATE_NONE: - root_scan_phase(mrb); - mrb->gc_state = GC_STATE_MARK; - flip_white_part(mrb); + switch (gc->state) { + case MRB_GC_STATE_ROOT: + root_scan_phase(mrb, gc); + gc->state = MRB_GC_STATE_MARK; + flip_white_part(gc); return 0; - case GC_STATE_MARK: - if (mrb->gray_list) { - return incremental_marking_phase(mrb, limit); + case MRB_GC_STATE_MARK: + if (gc->gray_list) { + return incremental_marking_phase(mrb, gc, limit); } else { - final_marking_phase(mrb); - prepare_incremental_sweep(mrb); + final_marking_phase(mrb, gc); + prepare_incremental_sweep(mrb, gc); return 0; } - case GC_STATE_SWEEP: { + case MRB_GC_STATE_SWEEP: { size_t tried_sweep = 0; - tried_sweep = incremental_sweep_phase(mrb, limit); + tried_sweep = incremental_sweep_phase(mrb, gc, limit); if (tried_sweep == 0) - mrb->gc_state = GC_STATE_NONE; + gc->state = MRB_GC_STATE_ROOT; return tried_sweep; } default: @@ -958,79 +1217,90 @@ incremental_gc(mrb_state *mrb, size_t limit) } static void -incremental_gc_until(mrb_state *mrb, enum gc_state to_state) +incremental_gc_until(mrb_state *mrb, mrb_gc *gc, mrb_gc_state to_state) { do { - incremental_gc(mrb, ~0); - } while (mrb->gc_state != to_state); + incremental_gc(mrb, gc, SIZE_MAX); + } while (gc->state != to_state); } static void -incremental_gc_step(mrb_state *mrb) +incremental_gc_step(mrb_state *mrb, mrb_gc *gc) { size_t limit = 0, result = 0; - limit = (GC_STEP_SIZE/100) * mrb->gc_step_ratio; + limit = (GC_STEP_SIZE/100) * gc->step_ratio; while (result < limit) { - result += incremental_gc(mrb, limit); - if (mrb->gc_state == GC_STATE_NONE) + result += incremental_gc(mrb, gc, limit); + if (gc->state == MRB_GC_STATE_ROOT) break; } - mrb->gc_threshold = mrb->live + GC_STEP_SIZE; + gc->threshold = gc->live + GC_STEP_SIZE; } static void -clear_all_old(mrb_state *mrb) +clear_all_old(mrb_state *mrb, mrb_gc *gc) { - mrb_bool origin_mode = mrb->is_generational_gc_mode; + mrb_bool origin_mode = gc->generational; - mrb_assert(is_generational(mrb)); - if (is_major_gc(mrb)) { + mrb_assert(is_generational(gc)); + if (is_major_gc(gc)) { /* finish the half baked GC */ - incremental_gc_until(mrb, GC_STATE_NONE); + incremental_gc_until(mrb, gc, 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_NONE); - mrb->is_generational_gc_mode = origin_mode; + gc->generational = FALSE; + prepare_incremental_sweep(mrb, gc); + incremental_gc_until(mrb, gc, MRB_GC_STATE_ROOT); + gc->generational = origin_mode; - /* The gray objects has already been painted as white */ - mrb->atomic_gray_list = mrb->gray_list = NULL; + /* The gray objects have already been painted as white */ + gc->atomic_gray_list = gc->gray_list = NULL; } -void +MRB_API void mrb_incremental_gc(mrb_state *mrb) { - if (mrb->gc_disabled) return; + mrb_gc *gc = &mrb->gc; + + if (gc->disabled || gc->iterating) return; GC_INVOKE_TIME_REPORT("mrb_incremental_gc()"); GC_TIME_START; - if (is_minor_gc(mrb)) { - incremental_gc_until(mrb, GC_STATE_NONE); + if (is_minor_gc(gc)) { + incremental_gc_until(mrb, gc, MRB_GC_STATE_ROOT); } else { - incremental_gc_step(mrb); + incremental_gc_step(mrb, gc); } - if (mrb->gc_state == GC_STATE_NONE) { - 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 (gc->state == MRB_GC_STATE_ROOT) { + mrb_assert(gc->live >= gc->live_after_mark); + gc->threshold = (gc->live_after_mark/100) * gc->interval_ratio; + if (gc->threshold < GC_STEP_SIZE) { + 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; + if (is_major_gc(gc)) { + size_t threshold = gc->live_after_mark/100 * MAJOR_GC_INC_RATIO; + + gc->full = FALSE; + if (threshold < MAJOR_GC_TOOMANY) { + gc->majorgc_old_threshold = threshold; + } + else { + /* too many objects allocated during incremental GC, */ + /* instead of increasing threshold, invoke full GC. */ + mrb_full_gc(mrb); + } } - else if (is_minor_gc(mrb)) { - if (mrb->live > mrb->majorgc_old_threshold) { - clear_all_old(mrb); - mrb->gc_full = TRUE; + else if (is_minor_gc(gc)) { + if (gc->live > gc->majorgc_old_threshold) { + clear_all_old(mrb, gc); + gc->full = TRUE; } } } @@ -1039,86 +1309,69 @@ mrb_incremental_gc(mrb_state *mrb) } /* Perform a full gc cycle */ -void +MRB_API void mrb_full_gc(mrb_state *mrb) { - if (mrb->gc_disabled) return; + mrb_gc *gc = &mrb->gc; + + if (!mrb->c) return; + if (gc->disabled || gc->iterating) return; + GC_INVOKE_TIME_REPORT("mrb_full_gc()"); GC_TIME_START; - if (is_generational(mrb)) { + if (is_generational(gc)) { /* clear all the old objects back to young */ - clear_all_old(mrb); - mrb->gc_full = TRUE; + clear_all_old(mrb, gc); + gc->full = TRUE; } - else if (mrb->gc_state != GC_STATE_NONE) { + else if (gc->state != MRB_GC_STATE_ROOT) { /* finish half baked GC cycle */ - incremental_gc_until(mrb, GC_STATE_NONE); + incremental_gc_until(mrb, gc, MRB_GC_STATE_ROOT); } - incremental_gc_until(mrb, GC_STATE_NONE); - mrb->gc_threshold = (mrb->gc_live_after_mark/100) * mrb->gc_interval_ratio; + incremental_gc_until(mrb, gc, MRB_GC_STATE_ROOT); + gc->threshold = (gc->live_after_mark/100) * 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; + if (is_generational(gc)) { + gc->majorgc_old_threshold = gc->live_after_mark/100 * MAJOR_GC_INC_RATIO; + gc->full = FALSE; } +#ifdef MRB_USE_MALLOC_TRIM + malloc_trim(0); +#endif GC_TIME_STOP_AND_REPORT; } -void +MRB_API void mrb_garbage_collect(mrb_state *mrb) { mrb_full_gc(mrb); } -int -mrb_gc_arena_save(mrb_state *mrb) -{ - return mrb->arena_idx; -} - -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). */ -void +MRB_API void mrb_field_write_barrier(mrb_state *mrb, struct RBasic *obj, struct RBasic *value) { + mrb_gc *gc = &mrb->gc; + 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_NONE); + mrb_assert(gc->state == MRB_GC_STATE_MARK || (!is_dead(gc, value) && !is_dead(gc, obj))); + mrb_assert(is_generational(gc) || gc->state != MRB_GC_STATE_ROOT); - if (is_generational(mrb) || mrb->gc_state == GC_STATE_MARK) { - add_gray_list(mrb, value); + if (is_generational(gc) || gc->state == MRB_GC_STATE_MARK) { + add_gray_list(mrb, gc, value); } else { - mrb_assert(mrb->gc_state == GC_STATE_SWEEP); - paint_partial_white(mrb, obj); /* for never write barriers */ + mrb_assert(gc->state == MRB_GC_STATE_SWEEP); + paint_partial_white(gc, obj); /* for never write barriers */ } } @@ -1131,16 +1384,18 @@ mrb_field_write_barrier(mrb_state *mrb, struct RBasic *obj, struct RBasic *value * e.g. Set element on Array. */ -void +MRB_API void mrb_write_barrier(mrb_state *mrb, struct RBasic *obj) { + mrb_gc *gc = &mrb->gc; + if (!is_black(obj)) return; - mrb_assert(!is_dead(mrb, obj)); - mrb_assert(is_generational(mrb) || mrb->gc_state != GC_STATE_NONE); + mrb_assert(!is_dead(gc, obj)); + mrb_assert(is_generational(gc) || gc->state != MRB_GC_STATE_ROOT); paint_gray(obj); - obj->gcnext = mrb->atomic_gray_list; - mrb->atomic_gray_list = obj; + obj->gcnext = gc->atomic_gray_list; + gc->atomic_gray_list = obj; } /* @@ -1174,9 +1429,9 @@ gc_start(mrb_state *mrb, mrb_value obj) static mrb_value gc_enable(mrb_state *mrb, mrb_value obj) { - int old = mrb->gc_disabled; + mrb_bool old = mrb->gc.disabled; - mrb->gc_disabled = FALSE; + mrb->gc.disabled = FALSE; return mrb_bool_value(old); } @@ -1196,16 +1451,16 @@ gc_enable(mrb_state *mrb, mrb_value obj) static mrb_value gc_disable(mrb_state *mrb, mrb_value obj) { - int old = mrb->gc_disabled; + mrb_bool old = mrb->gc.disabled; - mrb->gc_disabled = TRUE; + mrb->gc.disabled = TRUE; return mrb_bool_value(old); } /* * call-seq: - * GC.interval_ratio -> fixnum + * GC.interval_ratio -> int * * Returns ratio of GC interval. Default value is 200(%). * @@ -1214,12 +1469,12 @@ gc_disable(mrb_state *mrb, mrb_value obj) static mrb_value gc_interval_ratio_get(mrb_state *mrb, mrb_value obj) { - return mrb_fixnum_value(mrb->gc_interval_ratio); + return mrb_int_value(mrb, mrb->gc.interval_ratio); } /* * call-seq: - * GC.interval_ratio = fixnum -> nil + * GC.interval_ratio = int -> 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(%). @@ -1232,13 +1487,13 @@ gc_interval_ratio_set(mrb_state *mrb, mrb_value obj) mrb_int ratio; mrb_get_args(mrb, "i", &ratio); - mrb->gc_interval_ratio = ratio; + mrb->gc.interval_ratio = (int)ratio; return mrb_nil_value(); } /* * call-seq: - * GC.step_ratio -> fixnum + * GC.step_ratio -> int * * Returns step span ratio of Incremental GC. Default value is 200(%). * @@ -1247,12 +1502,12 @@ gc_interval_ratio_set(mrb_state *mrb, mrb_value obj) static mrb_value gc_step_ratio_get(mrb_state *mrb, mrb_value obj) { - return mrb_fixnum_value(mrb->gc_step_ratio); + return mrb_int_value(mrb, mrb->gc.step_ratio); } /* * call-seq: - * GC.step_ratio = fixnum -> nil + * GC.step_ratio = int -> nil * * Updates step span ratio of Incremental GC. Default value is 200(%). * 1 step of incrementalGC becomes long if a rate is big. @@ -1265,24 +1520,28 @@ gc_step_ratio_set(mrb_state *mrb, mrb_value obj) mrb_int ratio; mrb_get_args(mrb, "i", &ratio); - mrb->gc_step_ratio = ratio; + mrb->gc.step_ratio = (int)ratio; return mrb_nil_value(); } static void -change_gen_gc_mode(mrb_state *mrb, mrb_int enable) +change_gen_gc_mode(mrb_state *mrb, mrb_gc *gc, mrb_bool enable) { - if (is_generational(mrb) && !enable) { - clear_all_old(mrb); - mrb_assert(mrb->gc_state == GC_STATE_NONE); - mrb->gc_full = FALSE; + if (gc->disabled || gc->iterating) { + mrb_raise(mrb, E_RUNTIME_ERROR, "generational mode changed when GC disabled"); + return; + } + if (is_generational(gc) && !enable) { + clear_all_old(mrb, gc); + mrb_assert(gc->state == MRB_GC_STATE_ROOT); + gc->full = FALSE; } - else if (!is_generational(mrb) && enable) { - incremental_gc_until(mrb, GC_STATE_NONE); - mrb->majorgc_old_threshold = mrb->gc_live_after_mark/100 * DEFAULT_MAJOR_GC_INC_RATIO; - mrb->gc_full = FALSE; + else if (!is_generational(gc) && enable) { + incremental_gc_until(mrb, gc, MRB_GC_STATE_ROOT); + gc->majorgc_old_threshold = gc->live_after_mark/100 * MAJOR_GC_INC_RATIO; + gc->full = FALSE; } - mrb->is_generational_gc_mode = enable; + gc->generational = enable; } /* @@ -1296,7 +1555,7 @@ change_gen_gc_mode(mrb_state *mrb, mrb_int enable) static mrb_value gc_generational_mode_get(mrb_state *mrb, mrb_value self) { - return mrb_bool_value(mrb->is_generational_gc_mode); + return mrb_bool_value(mrb->gc.generational); } /* @@ -1313,41 +1572,74 @@ 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); + if (mrb->gc.generational != enable) + change_gen_gc_mode(mrb, &mrb->gc, enable); return mrb_bool_value(enable); } -void -mrb_objspace_each_objects(mrb_state *mrb, mrb_each_object_callback *callback, void *data) + +static void +gc_each_objects(mrb_state *mrb, mrb_gc *gc, mrb_each_object_callback *callback, void *data) { - struct heap_page* page = mrb->heaps; + mrb_heap_page* page; + page = gc->heaps; while (page != NULL) { - RVALUE *p, *pend; + RVALUE *p; + int i; - p = page->objects; - pend = p + MRB_HEAP_PAGE_SIZE; - for (;p < pend; p++) { - (*callback)(mrb, &p->as.basic, data); + p = objects(page); + for (i=0; i < MRB_HEAP_PAGE_SIZE; i++) { + if ((*callback)(mrb, &p[i].as.basic, data) == MRB_EACH_OBJ_BREAK) + return; } - page = page->next; } } -#ifdef GC_TEST -#ifdef GC_DEBUG -static mrb_value gc_test(mrb_state *, mrb_value); -#endif -#endif +void +mrb_objspace_each_objects(mrb_state *mrb, mrb_each_object_callback *callback, void *data) +{ + mrb_bool iterating = mrb->gc.iterating; + + mrb_full_gc(mrb); + mrb->gc.iterating = TRUE; + if (iterating) { + gc_each_objects(mrb, &mrb->gc, callback, data); + } + else { + struct mrb_jmpbuf *prev_jmp = mrb->jmp; + struct mrb_jmpbuf c_jmp; + + MRB_TRY(&c_jmp) { + mrb->jmp = &c_jmp; + gc_each_objects(mrb, &mrb->gc, callback, data); + mrb->jmp = prev_jmp; + mrb->gc.iterating = iterating; + } MRB_CATCH(&c_jmp) { + mrb->gc.iterating = iterating; + mrb->jmp = prev_jmp; + MRB_THROW(prev_jmp); + } MRB_END_EXC(&c_jmp); + } +} + +size_t +mrb_objspace_page_slot_size(void) +{ + return sizeof(RVALUE); +} + void mrb_init_gc(mrb_state *mrb) { struct RClass *gc; + mrb_static_assert(sizeof(RVALUE) <= sizeof(void*) * 6, + "RVALUE size must be within 6 words"); + gc = mrb_define_module(mrb, "GC"); mrb_define_class_method(mrb, gc, "start", gc_start, MRB_ARGS_NONE()); @@ -1359,272 +1651,4 @@ mrb_init_gc(mrb_state *mrb) 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_NONE); - puts(" in GC_STATE_NONE"); - 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_NONE); - - 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_NONE); - - 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_NONE); - - puts(" in major"); - mrb_assert(is_major_gc(mrb)); - do { - mrb_incremental_gc(mrb); - } while (mrb->gc_state != GC_STATE_NONE); - 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 */ |