[PATCH] GC code cleanup

[Ludovic Courtès]

Hi,

The patch below is an attempt to clean up the GC by limiting the use of
global variables for statistics.  IMO it makes it easier to read the
code.  Furthermore, it's also easier to track the exact number of cells
swept/collected at each stage.

It also fixes (unless I'm mistaken!) the computation of the number of
cells swept/collected in `scm_i_sweep_some_cards ()'.

Thanks,
Ludovic.


2005-12-20  Ludovic Courtès  <address@hidden>

        * libguile/gc-segment.c (scm_i_sweep_some_cards): Take two more
        arguments.  Don't refer to SCM_GC_CELLS_COLLECTED and
        SCM_CELLS_ALLOCATED.  If SEG->FIRST_TIME, let CELLS_COLLECTED as zero.
        Take into account SEG->SPAN when computing CELLS_SWEPT.
        (scm_i_sweep_segment): Take two more arguments, similarly.
        (scm_i_sweep_all_segments): Likewise.
        (scm_i_sweep_some_segments): Likewise.
        (scm_i_adjust_min_yield): Change the way MIN_CELLS is computed: do not
        refer to SCM_GC_CELLS_COLLECTED.

        * libguile/gc-freelist.c (scm_i_adjust_min_yield): Take two more
        arguments: CELLS_COLLECTED and CELLS_SWEPT.
        Change the way DELTA is collected: don't take into account
        SCM_GC_CELLS_COLLECTED_1, only CELLS_COLLECTED.
    
        * libguile/gc-malloc.c (scm_realloc): Pass extra arguments, namely
        CELLS_COLLECTED and CELLS_SWEPT, to `scm_i_sweep_all_segments ()'.
    
        * libguile/gc.c (gc_start_stats): Updated accordingly.
        (gc_end_stats): Take two additional arguments: CELLS_COLLECTED and
        CELLS_SWEPT.  Decrement SCM_CELLS_ALLOCATED after calls to
        `scm_i_sweep_* ()'.
        (scm_gc_for_newcell): Updated callers of `scm_i_sweep_*'.
        Decrement SCM_CELLS_ALLOCATED.
        (scm_i_gc): Likewise.
    
        * libguile/private-gc.h: Updated function prototypes accordingly.
 


--- orig/libguile/gc-freelist.c
+++ mod/libguile/gc-freelist.c
@@ -78,7 +78,9 @@
  */
 
 void
-scm_i_adjust_min_yield (scm_t_cell_type_statistics *freelist)
+scm_i_adjust_min_yield (scm_t_cell_type_statistics *freelist,
+                       unsigned cells_collected,
+                       unsigned cells_swept)
 {
   /* min yield is adjusted upwards so that next predicted total yield
    * (allocated cells actually freed by GC) becomes
@@ -98,7 +100,7 @@
     {
       /* Pick largest of last two yields. */
       long delta = ((SCM_HEAP_SIZE * freelist->min_yield_fraction / 100)
-                  - (long) SCM_MAX (scm_gc_cells_collected_1, 
scm_gc_cells_collected));
+                  - (long) cells_collected);
 #ifdef DEBUGINFO
       fprintf (stderr, " after GC = %lu, delta = %ld\n",
               (unsigned long) scm_cells_allocated,


--- orig/libguile/gc-malloc.c
+++ mod/libguile/gc-malloc.c
@@ -105,6 +105,7 @@
 scm_realloc (void *mem, size_t size)
 {
   void *ptr;
+  unsigned cells_collected, cells_swept;
 
   SCM_SYSCALL (ptr = realloc (mem, size));
   if (ptr)
@@ -113,7 +114,7 @@
   scm_i_scm_pthread_mutex_lock (&scm_i_sweep_mutex);
   scm_gc_running_p = 1;
 
-  scm_i_sweep_all_segments ("realloc");
+  scm_i_sweep_all_segments ("realloc", &cells_collected, &cells_swept);
   
   SCM_SYSCALL (ptr = realloc (mem, size));
   if (ptr)
@@ -124,7 +125,7 @@
     }
 
   scm_i_gc ("realloc");
-  scm_i_sweep_all_segments ("realloc");
+  scm_i_sweep_all_segments ("realloc", &cells_collected, &cells_swept);
   
   scm_gc_running_p = 0;
   scm_i_pthread_mutex_unlock (&scm_i_sweep_mutex);
@@ -220,13 +221,14 @@
     {
       unsigned long prev_alloced;
       float yield;
-      
+      unsigned cells_collected, cells_swept;
+
       scm_i_scm_pthread_mutex_lock (&scm_i_sweep_mutex);
       scm_gc_running_p = 1;
       
       prev_alloced  = mallocated;
       scm_i_gc (what);
-      scm_i_sweep_all_segments ("mtrigger");
+      scm_i_sweep_all_segments ("mtrigger", &cells_collected, &cells_swept);
 
       yield = (((float) prev_alloced - (float) scm_mallocated)
               / (float) prev_alloced);


--- orig/libguile/gc-segment.c
+++ mod/libguile/gc-segment.c
@@ -140,15 +140,13 @@
          scm_i_segment_card_count (seg) *  SCM_GC_CARD_BVEC_SIZE_IN_LONGS * 
SCM_SIZEOF_LONG);
 }
 
-/*
-  Sweep cards from SEG until we've gathered THRESHOLD cells
-  
-  RETURN:
-
-  Freelist. 
-*/
+/* Sweep cards from SEG until we've gathered THRESHOLD cells.  On return,
+   *CELLS_SWEPT contains the number of cells that have been visited and
+   *CELLS_COLLECTED contains the number of cells actually collected.  A
+   freelist is returned, potentially empty.  */
 SCM
-scm_i_sweep_some_cards (scm_t_heap_segment *seg)
+scm_i_sweep_some_cards (scm_t_heap_segment *seg,
+                       unsigned *cells_collected, unsigned *cells_swept)
 {
   SCM cells = SCM_EOL;
   int threshold = 512;
@@ -158,7 +156,7 @@
 
   scm_t_cell * next_free = seg->next_free_card;
   int cards_swept = 0;
-  
+
   while (collected < threshold && next_free < seg->bounds[1])
     {
       collected += (*sweeper) (next_free, &cells, seg);
@@ -166,14 +164,18 @@
       cards_swept ++;
     }
 
-  scm_gc_cells_swept +=  cards_swept * (SCM_GC_CARD_N_CELLS - 
SCM_GC_CARD_N_HEADER_CELLS);
-  scm_gc_cells_collected += collected * seg->span;
+  *cells_swept = cards_swept * seg->span
+    * (SCM_GC_CARD_N_CELLS - SCM_GC_CARD_N_HEADER_CELLS);
 
   if (!seg->first_time)
-    scm_cells_allocated -= collected * seg->span;
-  
-  seg->freelist->collected += collected  * seg->span;
-  
+    {
+      /* scm_cells_allocated -= collected * seg->span; */
+      *cells_collected = collected * seg->span;
+    }
+  else
+    *cells_collected = 0;
+
+  seg->freelist->collected += collected * seg->span;
 
   if(next_free == seg->bounds[1])
     {
@@ -196,31 +198,37 @@
   segment again, the statistics are off.
  */
 void
-scm_i_sweep_segment (scm_t_heap_segment * seg)
+scm_i_sweep_segment (scm_t_heap_segment *seg,
+                    unsigned *cells_collected, unsigned *cells_swept)
 {
+  unsigned c, s;
   scm_t_cell * p = seg->next_free_card;
-  int yield = scm_gc_cells_collected;
-  int coll = seg->freelist->collected;
-  unsigned long alloc = scm_cells_allocated ;
-  
-  while (scm_i_sweep_some_cards (seg) != SCM_EOL)
-    ;
 
-  scm_gc_cells_collected = yield;
-  scm_cells_allocated = alloc;
-  seg->freelist->collected = coll; 
-  
+  *cells_collected = *cells_swept = 0;
+
+  while (scm_i_sweep_some_cards (seg, &c, &s) != SCM_EOL)
+    {
+      *cells_collected += c;
+      *cells_swept += s;
+    }
+
   seg->next_free_card =p;
 }
 
 void
-scm_i_sweep_all_segments (char const  *reason)
+scm_i_sweep_all_segments (char const *reason,
+                         unsigned *cells_collected, unsigned *cells_swept)
 {
-  int i= 0; 
+  unsigned i= 0;
 
+  *cells_collected = *cells_swept = 0;
   for (i = 0; i < scm_i_heap_segment_table_size; i++)
     {
-      scm_i_sweep_segment (scm_i_heap_segment_table[i]);
+      unsigned c, s;
+
+      scm_i_sweep_segment (scm_i_heap_segment_table[i], &c, &s);
+      *cells_collected += c;
+      *cells_swept += s;
     }
 }
 
@@ -317,29 +325,37 @@
 }
 
 SCM
-scm_i_sweep_some_segments (scm_t_cell_type_statistics * fl)
+scm_i_sweep_some_segments (scm_t_cell_type_statistics *fl,
+                          unsigned *cells_collected,
+                          unsigned *cells_swept)
 {
   int i = fl->heap_segment_idx;
   SCM collected = SCM_EOL;
-  
+
+  *cells_collected = *cells_swept = 0;
   if (i == -1)
     i++;
-  
+
   for (;
        i < scm_i_heap_segment_table_size; i++)
     {
+      unsigned c, s;
+
       if (scm_i_heap_segment_table[i]->freelist != fl)
        continue;
-      
-      collected = scm_i_sweep_some_cards (scm_i_heap_segment_table[i]);
 
+      collected = scm_i_sweep_some_cards (scm_i_heap_segment_table[i],
+                                         &c, &s);
+
+      *cells_collected += c;
+      *cells_swept += s;
 
       if (collected != SCM_EOL)       /* Don't increment i */
        break;
     }
 
   fl->heap_segment_idx = i;
-  
+
   return collected;
 }
 
@@ -479,8 +495,7 @@
      */
     float f = freelist->min_yield_fraction / 100.0;
     float h = SCM_HEAP_SIZE;
-    float min_cells
-      = (f * h - scm_gc_cells_collected) / (1.0 - f);
+    float min_cells = (f * h - scm_gc_cells_collected) / (1.0 - f);
 
     /* Make heap grow with factor 1.5 */
     len =  freelist->heap_size / 2;


--- orig/libguile/gc.c
+++ mod/libguile/gc.c
@@ -403,31 +403,32 @@
 {
   t_before_gc = scm_c_get_internal_run_time ();
 
-  scm_gc_cells_marked_acc += (double) scm_gc_cells_swept
-    - (double) scm_gc_cells_collected;
-  scm_gc_cells_swept_acc += (double) scm_gc_cells_swept;
-
-  scm_gc_cell_yield_percentage = ( scm_gc_cells_collected * 100 ) / 
SCM_HEAP_SIZE; 
-  
-  scm_gc_cells_swept = 0;
-  scm_gc_cells_collected_1 = scm_gc_cells_collected;
-
-  /*
-    CELLS SWEPT is another word for the number of cells that were
-    examined during GC. YIELD is the number that we cleaned
-    out. MARKED is the number that weren't cleaned. 
-   */
-  scm_gc_cells_collected = 0;
   scm_gc_malloc_collected = 0;
   scm_gc_ports_collected = 0;
 }
 
 static void
-gc_end_stats ()
+gc_end_stats (unsigned cells_collected, unsigned cells_swept)
 {
   unsigned long t = scm_c_get_internal_run_time ();
   scm_gc_time_taken += (t - t_before_gc);
 
+  /*
+    CELLS SWEPT is another word for the number of cells that were
+    examined during GC. YIELD is the number that we cleaned
+    out. MARKED is the number that weren't cleaned.
+   */
+  scm_gc_cells_marked_acc += (double) cells_swept
+    - (double) scm_gc_cells_collected;
+  scm_gc_cells_swept_acc += (double) cells_swept;
+
+  scm_gc_cell_yield_percentage = (cells_collected * 100) / SCM_HEAP_SIZE;
+
+  scm_gc_cells_swept = cells_swept;
+  scm_gc_cells_collected_1 = scm_gc_cells_collected;
+  scm_gc_cells_collected = cells_collected;
+  scm_cells_allocated -= cells_collected;
+
   ++scm_gc_times;
 }
 
@@ -478,15 +479,21 @@
 {
   SCM cell;
   int did_gc = 0;
- 
+  unsigned cells_collected, cells_swept;
+
   scm_i_scm_pthread_mutex_lock (&scm_i_sweep_mutex);
   scm_gc_running_p = 1;
 
-  *free_cells = scm_i_sweep_some_segments (freelist);
+  *free_cells = scm_i_sweep_some_segments (freelist,
+                                          &cells_collected, &cells_swept);
+  scm_cells_allocated -= cells_collected;
+
   if (*free_cells == SCM_EOL && scm_i_gc_grow_heap_p (freelist))
     {
       freelist->heap_segment_idx = scm_i_get_new_heap_segment (freelist, 
abort_on_error);
-      *free_cells = scm_i_sweep_some_segments (freelist);
+      *free_cells = scm_i_sweep_some_segments (freelist,
+                                              &cells_collected, &cells_swept);
+      scm_cells_allocated -= cells_collected;
     }
 
   if (*free_cells == SCM_EOL)
@@ -495,7 +502,7 @@
        with the advent of lazy sweep, GC yield is only known just
        before doing the GC.
       */
-      scm_i_adjust_min_yield (freelist);
+      scm_i_adjust_min_yield (freelist, cells_collected, cells_swept);
 
       /*
        out of fresh cells. Try to get some new ones.
@@ -504,7 +511,9 @@
       did_gc = 1;
       scm_i_gc ("cells");
 
-      *free_cells = scm_i_sweep_some_segments (freelist);
+      *free_cells = scm_i_sweep_some_segments (freelist,
+                                              &cells_collected, &cells_swept);
+      scm_cells_allocated -= cells_collected;
     }
   
   if (*free_cells == SCM_EOL)
@@ -513,7 +522,9 @@
        failed getting new cells. Get new juice or die.
        */
       freelist->heap_segment_idx = scm_i_get_new_heap_segment (freelist, 
abort_on_error);
-      *free_cells = scm_i_sweep_some_segments (freelist);
+      *free_cells = scm_i_sweep_some_segments (freelist,
+                                              &cells_collected, &cells_swept);
+      scm_cells_allocated -= cells_collected;
     }
   
   if (*free_cells == SCM_EOL)
@@ -545,6 +556,8 @@
 void
 scm_i_gc (const char *what)
 {
+  unsigned cells_collected, cells_swept;
+
   scm_i_thread_put_to_sleep ();
 
   scm_c_hook_run (&scm_before_gc_c_hook, 0);
@@ -571,7 +584,12 @@
     Let's finish the sweep. The conservative GC might point into the
     garbage, and marking that would create a mess.
    */
-  scm_i_sweep_all_segments("GC");
+  scm_i_sweep_all_segments ("GC", &cells_collected, &cells_swept);
+
+  /* The number of cells collected (i.e., freed) must always be lower than or
+     equal to the number of cells "swept" (i.e., visited).  */
+  assert (cells_collected <= cells_swept);
+
   if (scm_mallocated < scm_i_deprecated_memory_return)
     {
       /* The byte count of allocated objects has underflowed.  This is
@@ -624,7 +642,7 @@
   scm_gc_sweep ();
   scm_c_hook_run (&scm_after_sweep_c_hook, 0);
 
-  gc_end_stats ();
+  gc_end_stats (cells_collected, cells_swept);
 
   scm_i_thread_wake_up ();
 
@@ -635,6 +653,7 @@
    */
 }
 
+
 
 /* {GC Protection Helper Functions}
  */


--- orig/libguile/private-gc.h
+++ mod/libguile/private-gc.h
@@ -122,7 +122,9 @@
 extern scm_t_cell_type_statistics scm_i_master_freelist2;
 extern unsigned long scm_gc_cells_collected_1;
 
-void scm_i_adjust_min_yield (scm_t_cell_type_statistics *freelist);
+void scm_i_adjust_min_yield (scm_t_cell_type_statistics *freelist,
+                            unsigned cells_collected,
+                            unsigned cells_swept);
 void scm_i_gc_sweep_freelist_reset (scm_t_cell_type_statistics *freelist);
 int scm_i_gc_grow_heap_p (scm_t_cell_type_statistics * freelist);
 
@@ -221,8 +223,10 @@
 
 void scm_i_clear_segment_mark_space (scm_t_heap_segment *seg);
 scm_t_heap_segment * scm_i_make_empty_heap_segment 
(scm_t_cell_type_statistics*);
-SCM scm_i_sweep_some_cards (scm_t_heap_segment *seg);
-void scm_i_sweep_segment (scm_t_heap_segment * seg);
+SCM scm_i_sweep_some_cards (scm_t_heap_segment *seg,
+                           unsigned *cells_collected, unsigned *cells_swept);
+void scm_i_sweep_segment (scm_t_heap_segment *seg,
+                         unsigned *cells_collected, unsigned *cells_swept);
 
 void scm_i_heap_segment_statistics (scm_t_heap_segment *seg, SCM tab);
 
@@ -232,9 +236,13 @@
 int scm_i_get_new_heap_segment (scm_t_cell_type_statistics *, policy_on_error);
 void scm_i_clear_mark_space (void);
 void scm_i_sweep_segments (void);
-SCM scm_i_sweep_some_segments (scm_t_cell_type_statistics * fl);
+SCM scm_i_sweep_some_segments (scm_t_cell_type_statistics *fl,
+                              unsigned *cells_collected,
+                              unsigned *cells_swept);
 void scm_i_reset_segments (void);
-void scm_i_sweep_all_segments (char const *reason);
+void scm_i_sweep_all_segments (char const *reason,
+                              unsigned *cells_collected,
+                              unsigned *cells_swept);
 SCM scm_i_all_segments_statistics (SCM hashtab);
 void scm_i_make_initial_segment (int init_heap_size, 
scm_t_cell_type_statistics *freelist);