@@ -121,7 +121,7 @@ struct free_obj {
121121122122struct RVALUE_initializer {
123123MRB_OBJECT_HEADER;
124-char padding[sizeof(void*) * 4 - sizeof(uint32_t)];
124+char padding[sizeof(void*) * 3];
125125};
126126127127struct RVALUE {
@@ -531,8 +531,12 @@ add_gray_list(mrb_gc *gc, struct RBasic *obj)
531531 }
532532#endif
533533paint_gray(obj);
534-obj->gcnext = gc->gray_list;
535-gc->gray_list = obj;
534+if (gc->gray_stack_top < MRB_GRAY_STACK_SIZE) {
535+gc->gray_stack[gc->gray_stack_top++] = obj;
536+ }
537+else {
538+gc->gray_overflow = TRUE;
539+ }
536540}
537541538542static void
@@ -914,8 +918,8 @@ root_scan_phase(mrb_state *mrb, mrb_gc *gc)
914918int i, e;
915919916920if (!is_minor_gc(gc)) {
917-gc->gray_list = NULL;
918-gc->atomic_gray_list = NULL;
921+gc->gray_stack_top = 0;
922+gc->gray_overflow = FALSE;
919923 }
920924921925mrb_gc_mark_gv(mrb);
@@ -964,13 +968,37 @@ root_scan_phase(mrb_state *mrb, mrb_gc *gc)
964968#endif
965969}
966970971+static void
972+gc_gray_rescan(mrb_state *mrb, mrb_gc *gc)
973+{
974+mrb_heap_page *page = gc->heaps;
975+976+gc->gray_overflow = FALSE;
977+while (page) {
978+RVALUE *p = page->objects;
979+RVALUE *e = p + MRB_HEAP_PAGE_SIZE;
980+for (; p < e; p++) {
981+if (is_gray(&p->as.basic) && p->as.basic.tt != MRB_TT_FREE) {
982+if (gc->gray_stack_top >= MRB_GRAY_STACK_SIZE) {
983+gc->gray_overflow = TRUE;
984+return;
985+ }
986+gc->gray_stack[gc->gray_stack_top++] = &p->as.basic;
987+ }
988+ }
989+page = page->next;
990+ }
991+}
992+967993static void
968994gc_mark_gray_list(mrb_state *mrb, mrb_gc *gc) {
969-while (gc->gray_list) {
970-struct RBasic *obj = gc->gray_list;
971-gc->gray_list = obj->gcnext;
972-obj->gcnext = NULL;
973-gc_mark_children(mrb, gc, obj);
995+for (;;) {
996+while (gc->gray_stack_top > 0) {
997+struct RBasic *obj = gc->gray_stack[--gc->gray_stack_top];
998+gc_mark_children(mrb, gc, obj);
999+ }
1000+if (!gc->gray_overflow) break;
1001+gc_gray_rescan(mrb, gc);
9741002 }
9751003}
9761004@@ -979,11 +1007,18 @@ incremental_marking_phase(mrb_state *mrb, mrb_gc *gc, size_t limit)
9791007{
9801008size_t tried_marks = 0;
9811009982-while (gc->gray_list && tried_marks < limit) {
983-struct RBasic *obj = gc->gray_list;
984-gc->gray_list = obj->gcnext;
985-obj->gcnext = NULL;
986-tried_marks += gc_mark_children(mrb, gc, obj);
1010+while (tried_marks < limit) {
1011+if (gc->gray_stack_top > 0) {
1012+struct RBasic *obj = gc->gray_stack[--gc->gray_stack_top];
1013+tried_marks += gc_mark_children(mrb, gc, obj);
1014+ }
1015+else if (gc->gray_overflow) {
1016+gc_gray_rescan(mrb, gc);
1017+if (gc->gray_stack_top == 0) break;
1018+ }
1019+else {
1020+break;
1021+ }
9871022 }
98810239891024return tried_marks;
@@ -1027,18 +1062,12 @@ final_marking_phase(mrb_state *mrb, mrb_gc *gc)
10271062#endif
1028106310291064gc_mark_gray_list(mrb, gc);
1030-mrb_assert(gc->gray_list == NULL);
1031-gc->gray_list = gc->atomic_gray_list;
1032-gc->atomic_gray_list = NULL;
1033-gc_mark_gray_list(mrb, gc);
1034-mrb_assert(gc->gray_list == NULL);
10351065}
1036106610371067static void
10381068prepare_incremental_sweep(mrb_state *mrb, mrb_gc *gc)
10391069{
1040-// mrb_assert(gc->atomic_gray_list == NULL);
1041-// mrb_assert(gc->gray_list == NULL);
1070+// mrb_assert(gc->gray_stack_top == 0);
10421071gc->state = MRB_GC_STATE_SWEEP;
10431072gc->sweeps = NULL;
10441073gc->live_after_mark = gc->live;
@@ -1131,7 +1160,7 @@ incremental_gc(mrb_state *mrb, mrb_gc *gc, size_t limit)
11311160flip_white_part(gc);
11321161return 0;
11331162case MRB_GC_STATE_MARK:
1134-if (gc->gray_list) {
1163+if (gc->gray_stack_top > 0 || gc->gray_overflow) {
11351164return incremental_marking_phase(mrb, gc, limit);
11361165 }
11371166else {
@@ -1190,7 +1219,8 @@ clear_all_old(mrb_state *mrb, mrb_gc *gc)
11901219incremental_gc_finish(mrb, gc);
11911220gc->generational = TRUE;
11921221/* The gray objects have already been painted as white */
1193-gc->atomic_gray_list = gc->gray_list = NULL;
1222+gc->gray_stack_top = 0;
1223+gc->gray_overflow = FALSE;
11941224}
1195122511961226MRB_API void
@@ -1318,8 +1348,12 @@ mrb_write_barrier(mrb_state *mrb, struct RBasic *obj)
13181348mrb_assert(!is_dead(gc, obj));
13191349mrb_assert(is_generational(gc) || gc->state != MRB_GC_STATE_ROOT);
13201350paint_gray(obj);
1321-obj->gcnext = gc->atomic_gray_list;
1322-gc->atomic_gray_list = obj;
1351+if (gc->gray_stack_top < MRB_GRAY_STACK_SIZE) {
1352+gc->gray_stack[gc->gray_stack_top++] = obj;
1353+ }
1354+else {
1355+gc->gray_overflow = TRUE;
1356+ }
13231357}
1324135813251359/*