* gc.c: revert. before lazy sweep.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@17887 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

2 files changed, 129 insertions, 246 deletions

diff --git a/ChangeLog b/ChangeLog
index 442161f070..39de35d9d7 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,7 @@
+Sat Jul  5 16:12:54 2008  Narihiro Nakamura  <authorNari@gmail.com>
+
+	* gc.c: revert. before lazy sweep.
+
 Sat Jul  5 09:55:44 2008  Masaki Suketa  <masaki.suketa@nifty.ne.jp>
 
 	* ext/win32ole/win32ole.c: add WIN32OLE#ole_respond_to?
@@ -56,7 +60,7 @@ Fri Jul  4 14:17:22 2008  Nobuyoshi Nakada  <nobu@ruby-lang.org>
 
 	* lib/net/ftp.rb (Net::FTP#sendport): use divmod.  [ruby-core:17557]
 
-Fri Jul  4 11:08:37 2008  nari  <authorNari@gmail.com>
+Fri Jul  4 11:08:37 2008  Narihiro Nakamura  <authorNari@gmail.com>
 
 	* gc.c (garbage_collect_force): sweep is completely ended.
 
diff --git a/gc.c b/gc.c
index fc1767de47..eccd164801 100644
--- a/gc.c
+++ b/gc.c
@@ -129,17 +129,10 @@ typedef struct RVALUE {
 #pragma pack(pop)
 #endif
 
-enum slot_color {
-    WHITE = 0x00,  /* garbage */
-    BLACK = 0x01,  /* used */
-    GRAY  = 0x02,  /* not sweep */
-};
-
 struct heaps_slot {
     void *membase;
     RVALUE *slot;
     int limit;
-    enum slot_color color;
 };
 
 #define HEAP_MIN_SLOTS 10000
@@ -169,11 +162,6 @@ typedef struct rb_objspace {
 	RVALUE *freelist;
 	RVALUE *range[2];
 	RVALUE *freed;
-	size_t live;
-	size_t dead;
-	size_t do_heap_free;
-	size_t sweep_index;
-	size_t sweep_increment;
     } heap;
     struct {
 	int dont_gc;
@@ -191,7 +179,6 @@ typedef struct rb_objspace {
     struct gc_list *global_list;
     unsigned int count;
     int gc_stress;
-    int gc_not_lazy_sweep;
 } rb_objspace_t;
 
 #if defined(ENABLE_VM_OBJSPACE) && ENABLE_VM_OBJSPACE
@@ -213,11 +200,6 @@ int *ruby_initial_gc_stress_ptr = &rb_objspace.gc_stress;
 #define himem			objspace->heap.range[1]
 #define heaps_inc		objspace->heap.increment
 #define heaps_freed		objspace->heap.freed
-#define live			objspace->heap.live
-#define dead			objspace->heap.dead
-#define do_heap_free		objspace->heap.do_heap_free
-#define heaps_sweep_index	objspace->heap.sweep_index
-#define heaps_sweep_inc 	objspace->heap.sweep_increment
 #define dont_gc 		objspace->flags.dont_gc
 #define during_gc		objspace->flags.during_gc
 #define finalizer_table 	objspace->final.table
@@ -227,7 +209,6 @@ int *ruby_initial_gc_stress_ptr = &rb_objspace.gc_stress;
 #define mark_stack_overflow	objspace->markstack.overflow
 #define global_List		objspace->global_list
 #define ruby_gc_stress		objspace->gc_stress
-#define ruby_gc_not_lazy_sweep	objspace->gc_not_lazy_sweep
 
 #define need_call_final 	(finalizer_table && finalizer_table->num_entries)
 
@@ -268,7 +249,6 @@ int ruby_disable_gc_stress = 0;
 
 static void run_final(rb_objspace_t *objspace, VALUE obj);
 static int garbage_collect(rb_objspace_t *objspace);
-static int garbage_collect_force(rb_objspace_t *objspace);
 
 void
 rb_global_variable(VALUE *var)
@@ -345,11 +325,11 @@ vm_xmalloc(rb_objspace_t *objspace, size_t size)
 
     if ((ruby_gc_stress && !ruby_disable_gc_stress) ||
 	(malloc_increase+size) > malloc_limit) {
-	garbage_collect_force(objspace);
+	garbage_collect(objspace);
     }
     RUBY_CRITICAL(mem = malloc(size));
     if (!mem) {
-	if (garbage_collect_force(objspace)) {
+	if (garbage_collect(objspace)) {
 	    RUBY_CRITICAL(mem = malloc(size));
 	}
 	if (!mem) {
@@ -385,9 +365,10 @@ vm_xrealloc(rb_objspace_t *objspace, void *ptr, size_t size)
     objspace->malloc_params.allocated_size -= size;
     ptr = (size_t *)ptr - 1;
 #endif
+
     RUBY_CRITICAL(mem = realloc(ptr, size));
     if (!mem) {
-	if (garbage_collect_force(objspace)) {
+	if (garbage_collect(objspace)) {
 	    RUBY_CRITICAL(mem = realloc(ptr, size));
 	}
 	if (!mem) {
@@ -578,8 +559,6 @@ allocate_heaps(rb_objspace_t *objspace, size_t next_heaps_length)
     heaps_length = next_heaps_length;
 }
 
-#define RANY(o) ((RVALUE*)(o))
-
 static void
 assign_heap_slot(rb_objspace_t *objspace)
 {
@@ -623,7 +602,6 @@ assign_heap_slot(rb_objspace_t *objspace)
     heaps[hi].membase = membase;
     heaps[hi].slot = p;
     heaps[hi].limit = objs;
-    heaps[hi].color = BLACK;
     pend = p + objs;
     if (lomem == 0 || lomem > p) lomem = p;
     if (himem < pend) himem = pend;
@@ -635,9 +613,6 @@ assign_heap_slot(rb_objspace_t *objspace)
 	freelist = p;
 	p++;
     }
-    if (hi < heaps_sweep_index) {
-	heaps_sweep_index++;
-    }
 }
 
 static void
@@ -680,13 +655,15 @@ heaps_increment(rb_objspace_t *objspace)
     return Qfalse;
 }
 
+#define RANY(o) ((RVALUE*)(o))
+
 static VALUE
 rb_newobj_from_heap(rb_objspace_t *objspace)
 {
     VALUE obj;
 	
     if ((ruby_gc_stress && !ruby_disable_gc_stress) || !freelist) {
-   	if (!garbage_collect(objspace)) {
+    	if (!heaps_increment(objspace) && !garbage_collect(objspace)) {
 	    rb_memerror();
 	}
     }
@@ -1063,7 +1040,6 @@ gc_mark(rb_objspace_t *objspace, VALUE ptr, int lev)
     if (obj->as.basic.flags == 0) return;       /* free cell */
     if (obj->as.basic.flags & FL_MARK) return;  /* already marked */
     obj->as.basic.flags |= FL_MARK;
-    live++;
 
     if (lev > GC_LEVEL_MAX || (lev == 0 && ruby_stack_check())) {
 	if (!mark_stack_overflow) {
@@ -1099,7 +1075,6 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
     if (obj->as.basic.flags == 0) return;       /* free cell */
     if (obj->as.basic.flags & FL_MARK) return;  /* already marked */
     obj->as.basic.flags |= FL_MARK;
-    live++;
 
   marking:
     if (FL_TEST(obj, FL_EXIVAR)) {
@@ -1359,131 +1334,139 @@ finalize_list(rb_objspace_t *objspace, RVALUE *p)
 	if (!FL_TEST(p, FL_SINGLETON)) { /* not freeing page */
             VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
 	    p->as.free.flags = 0;
+	    p->as.free.next = freelist;
+	    freelist = p;
 	}
 	p = tmp;
     }
 }
 
-void rb_gc_abort_threads(void);
-
-static int
-slot_sweep(rb_objspace_t *objspace, struct heaps_slot *target)
+static void
+free_unused_heaps(rb_objspace_t *objspace)
 {
-    RVALUE *p, *pend, *free;
-    RVALUE *final;
-    int freed = 0;
-
-    if (target->color == BLACK || target->color == WHITE) {
-	return Qfalse;
-    }
+    size_t i, j;
+    RVALUE *last = 0;
 
-    final = deferred_final_list;
-    free = freelist;
-    p = target->slot; pend = p + target->limit;
-    while (p < pend) {
-	if (!(p->as.basic.flags & FL_MARK)) {
-	    if (p->as.basic.flags) {
-		obj_free(objspace, (VALUE)p);
-	    }
-	    if (need_call_final && FL_TEST(p, FL_FINALIZE)) {
-		p->as.free.flags = FL_MARK; /* remain marked */
-		p->as.free.next = deferred_final_list;
-		deferred_final_list = p;
+    for (i = j = 1; j < heaps_used; i++) {
+	if (heaps[i].limit == 0) {
+	    if (!last) {
+		last = heaps[i].membase;
 	    }
 	    else {
-		VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
-		p->as.free.flags = 0;
-		p->as.free.next = freelist;
-		freelist = p;
+		free(heaps[i].membase);
 	    }
-	    freed++;
-	}
-	else if (RBASIC(p)->flags == FL_MARK) {
-	    /* objects to be finalized */
-	    /* do nothing remain marked */
+	    heaps_used--;
 	}
 	else {
-	    p->as.basic.flags &= ~FL_MARK;
+	    if (i != j) {
+		heaps[j] = heaps[i];
+	    }
+	    j++;
 	}
-	p++;
     }
-    dead += freed;
-    if (freed == target->limit && dead > do_heap_free) {
-	RVALUE *pp;
-
-	target->limit = 0;
-	target->color = WHITE;
-	for (pp = deferred_final_list; pp != final; pp = pp->as.free.next) {
-	    pp->as.free.flags |= FL_SINGLETON; /* freeing page mark */
+    if (last) {
+	if (last < heaps_freed) {
+	    free(heaps_freed);
+	    heaps_freed = last;
 	}
-	freelist = free;	/* cancel this page from freelist */
-    }
-    else {
-	target->color = BLACK;
-    }
-    return Qtrue;
-}
-
-static void
-heap_sweep_increment(rb_objspace_t *objspace)
-{
-    int i = 0;
-
-    while (i < heaps_sweep_inc && heaps_sweep_index < heaps_used) {
-	if (slot_sweep(objspace, &heaps[heaps_sweep_index])) {
-	    i++;
+	else {
+	    free(last);
 	}
-	heaps_sweep_index++;
     }
 }
 
 static void
-heap_sweep(rb_objspace_t *objspace)
+gc_sweep(rb_objspace_t *objspace)
 {
-    while (!freelist && heaps_sweep_index < heaps_used) {
-	slot_sweep(objspace, &heaps[heaps_sweep_index]);
-	heaps_sweep_index++;
-    }
-}
-
-#define GC_NOT_LAZY_SWEEP 0
+    RVALUE *p, *pend, *final_list;
+    size_t freed = 0;
+    size_t i;
+    size_t live = 0, free_min = 0, do_heap_free = 0;
 
-static void
-heap_all_sweep(rb_objspace_t *objspace)
-{
-    while (heaps_sweep_index < heaps_used) {
-	slot_sweep(objspace, &heaps[heaps_sweep_index]);
-	heaps_sweep_index++;
+    do_heap_free = (heaps_used * HEAP_OBJ_LIMIT) * 0.65;
+    free_min = (heaps_used * HEAP_OBJ_LIMIT)  * 0.2;
+    if (free_min < FREE_MIN) {
+	do_heap_free = heaps_used * HEAP_OBJ_LIMIT;
+        free_min = FREE_MIN;
     }
-}
 
-static int
-gc_lazy_sweep(rb_objspace_t *objspace, rb_thread_t *th)
-{
+    freelist = 0;
+    final_list = deferred_final_list;
+    deferred_final_list = 0;
+    for (i = 0; i < heaps_used; i++) {
+	int n = 0;
+	RVALUE *free = freelist;
+	RVALUE *final = final_list;
+
+	p = heaps[i].slot; pend = p + heaps[i].limit;
+	while (p < pend) {
+	    if (!(p->as.basic.flags & FL_MARK)) {
+		if (p->as.basic.flags) {
+		    obj_free(objspace, (VALUE)p);
+		}
+		if (need_call_final && FL_TEST(p, FL_FINALIZE)) {
+		    p->as.free.flags = FL_MARK; /* remain marked */
+		    p->as.free.next = final_list;
+		    final_list = p;
+		}
+		else {
+                    VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
+		    p->as.free.flags = 0;
+		    p->as.free.next = freelist;
+		    freelist = p;
+		}
+		n++;
+	    }
+	    else if (RBASIC(p)->flags == FL_MARK) {
+		/* objects to be finalized */
+		/* do nothing remain marked */
+	    }
+	    else {
+		RBASIC(p)->flags &= ~FL_MARK;
+		live++;
+	    }
+	    p++;
+	}
+	if (n == heaps[i].limit && freed > do_heap_free) {
+	    RVALUE *pp;
 
-    if (heaps_increment(objspace)) {
-	heap_sweep_increment(objspace);
+	    heaps[i].limit = 0;
+	    for (pp = final_list; pp != final; pp = pp->as.free.next) {
+		p->as.free.flags |= FL_SINGLETON; /* freeing page mark */
+	    }
+	    freelist = free;	/* cancel this page from freelist */
+	}
+	else {
+	    freed += n;
+	}
     }
-    else {
-	heap_sweep(objspace);
+    if (malloc_increase > malloc_limit) {
+	malloc_limit += (malloc_increase - malloc_limit) * (double)live / (live + freed);
+	if (malloc_limit < GC_MALLOC_LIMIT) malloc_limit = GC_MALLOC_LIMIT;
     }
-
-    if (ruby_gc_not_lazy_sweep || GC_NOT_LAZY_SWEEP) {
-        heap_all_sweep(objspace);
+    malloc_increase = 0;
+    if (freed < free_min) {
+    	set_heaps_increment(objspace);
+	heaps_increment(objspace);
     }
+    during_gc = 0;
 
-    if (!freelist) {
-	return Qfalse;
+    /* clear finalization list */
+    if (final_list) {
+	deferred_final_list = final_list;
+	return;
     }
-
-    return Qtrue;
+    free_unused_heaps(objspace);
 }
 
 void
 rb_gc_force_recycle(VALUE p)
 {
+    rb_objspace_t *objspace = &rb_objspace;
     VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
     RANY(p)->as.free.flags = 0;
+    RANY(p)->as.free.next = freelist;
+    freelist = RANY(p);
 }
 
 static void
@@ -1684,86 +1667,29 @@ mark_current_machine_context(rb_objspace_t *objspace, rb_thread_t *th)
 
 void rb_gc_mark_encodings(void);
 
-static void
-gc_mark_all_clear(rb_objspace_t *objspace)
+static int
+garbage_collect(rb_objspace_t *objspace)
 {
-    RVALUE *last = 0;
-    size_t i, j;
-    
-    for (i = j = 0; j < heaps_used; i++) {
-	if (heaps[i].color == WHITE && !deferred_final_list) {
-	    if (!last) {
-		last = heaps[i].membase;
-	    }
-	    else {
-		free(heaps[i].membase);
-	    }
-	    heaps_used--;
-	}
-	else {
-	    if (heaps[i].color == GRAY) {
-		RVALUE *p, *pend;
-		p = heaps[i].slot; pend = p + heaps[i].limit;
-		while (p < pend) {
-		    if (!(RBASIC(p)->flags & FL_MARK)) {
-			if (p->as.basic.flags && !FL_TEST(p, FL_FINALIZE)) {
-			    obj_free(objspace, (VALUE)p);
-			    VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
-			    p->as.free.flags = 0;
-			}
-		    }
-		    else if (RBASIC(p)->flags != FL_MARK) {
-			p->as.basic.flags &= ~FL_MARK;
-		    }
-		    p++;
-		}
-	    }
-	    else {
-		heaps[i].color = GRAY;
-	    }
-	    if (i != j) {
-		heaps[j] = heaps[i];
-	    }
-	    j++;
-	}
-    }
-    if (last) {
-	if (last < heaps_freed) {
-	    free(heaps_freed);
-	    heaps_freed = last;
-	}
-	else {
-	    free(last);
-	}
-    }
-}
+    struct gc_list *list;
+    rb_thread_t *th = GET_THREAD();
 
-static void
-set_lazy_sweep_params(rb_objspace_t *objspace)
-{
-    size_t free_min = 0;
+    if (GC_NOTIFY) printf("start garbage_collect()\n");
 
-    dead = 0;
-    heaps_sweep_index = 0;
-    heaps_sweep_inc = (heaps_used / 10) + 1;
-    do_heap_free = (heaps_used * HEAP_OBJ_LIMIT) * 0.65;
-    free_min = (heaps_used * HEAP_OBJ_LIMIT)  * 0.2;
-    if (free_min < FREE_MIN) free_min = FREE_MIN;
-    if (free_min > (heaps_used * HEAP_OBJ_LIMIT - live)) {
-	set_heaps_increment(objspace);
-	heaps_sweep_inc = (heaps_used + heaps_sweep_inc) / heaps_sweep_inc + 1;
+    if (!heaps) {
+	return Qfalse;
     }
-}
-
-static void
-gc_marks(rb_objspace_t *objspace, rb_thread_t *th)
-{
-    struct gc_list *list;
-
-    live = 0;
-    freelist = 0;
 
-    gc_mark_all_clear(objspace);
+    if (dont_gc || during_gc) {
+	if (!freelist) {
+            if (!heaps_increment(objspace)) {
+                set_heaps_increment(objspace);
+                heaps_increment(objspace);
+            }
+	}
+	return Qtrue;
+    }
+    during_gc++;
+    objspace->count++;
 
     SET_STACK_END;
 
@@ -1781,7 +1707,6 @@ gc_marks(rb_objspace_t *objspace, rb_thread_t *th)
     rb_gc_mark_symbols();
     rb_gc_mark_encodings();
 
-
     /* mark protected global variables */
     for (list = global_List; list; list = list->next) {
 	rb_gc_mark_maybe(*list->varptr);
@@ -1807,55 +1732,9 @@ gc_marks(rb_objspace_t *objspace, rb_thread_t *th)
 	}
     }
 
-    set_lazy_sweep_params(objspace);
-}
-
-static int
-garbage_collect_force(rb_objspace_t *objspace)
-{
-    int is_gc_success;
-
-    if (malloc_increase > malloc_limit) {
-	malloc_limit += (malloc_increase - malloc_limit) * (double)live / (heaps_used * HEAP_OBJ_LIMIT);
-	if (malloc_limit < GC_MALLOC_LIMIT) malloc_limit = GC_MALLOC_LIMIT;
-    }
-    malloc_increase = 0;
-    ruby_gc_not_lazy_sweep = Qtrue;
-    is_gc_success = garbage_collect(objspace);
-    ruby_gc_not_lazy_sweep = Qfalse;
-    return is_gc_success;
-}
-
-static int
-garbage_collect(rb_objspace_t *objspace)
-{
-    rb_thread_t *th = GET_THREAD();
-
-    if (GC_NOTIFY) printf("start garbage_collect()\n");
-
-    if (!heaps) {
-	return Qfalse;
-    }
-
-    if (dont_gc || during_gc) {
-	if (!freelist) {
-            if (!heaps_increment(objspace)) {
-                set_heaps_increment(objspace);
-                heaps_increment(objspace);
-            }
-	}
-	return Qtrue;
-    }
-    during_gc++;
-    objspace->count++;
-
-    while (!gc_lazy_sweep(objspace, th)) {
-        gc_marks(objspace, th);
-    }
+    gc_sweep(objspace);
 
     if (GC_NOTIFY) printf("end garbage_collect()\n");
-    during_gc = 0;
-
     return Qtrue;
 }
 
@@ -1970,7 +1849,6 @@ os_obj_of(rb_objspace_t *objspace, VALUE of)
 
 	p = heaps[i].slot; pend = p + heaps[i].limit;
 	for (;p < pend; p++) {
-	    if (!freelist) garbage_collect_force(objspace);
 	    if (p->as.basic.flags) {
 		switch (BUILTIN_TYPE(p)) {
 		  case T_NONE:
@@ -2156,6 +2034,7 @@ gc_finalize_deferred(rb_objspace_t *objspace)
     if (p) {
 	finalize_list(objspace, p);
     }
+    free_unused_heaps(objspace);
 }
 
 void
@@ -2227,8 +2106,8 @@ void
 rb_gc(void)
 {
     rb_objspace_t *objspace = &rb_objspace;
-    gc_finalize_deferred(objspace);
     garbage_collect(objspace);
+    gc_finalize_deferred(objspace);
 }
 
 /*