From: simonm <unknown>
Date: Tue, 19 Jan 1999 17:06:05 +0000 (+0000)
Subject: [project @ 1999-01-19 17:06:02 by simonm]
X-Git-Tag: Approx_2487_patches~42
X-Git-Url: http://git.megacz.com/?p=ghc-hetmet.git;a=commitdiff_plain;h=bbab3c15e58912433d5f2b5dcd2344f5a176848c

[project @ 1999-01-19 17:06:02 by simonm]
Support '+RTS -G1'  i.e. a two-space collector.
---

diff --git a/ghc/rts/GC.c b/ghc/rts/GC.c
index efc1a64..a154012 100644
--- a/ghc/rts/GC.c
+++ b/ghc/rts/GC.c
@@ -1,5 +1,5 @@
 /* -----------------------------------------------------------------------------
- * $Id: GC.c,v 1.14 1999/01/19 15:41:56 simonm Exp $
+ * $Id: GC.c,v 1.15 1999/01/19 17:06:02 simonm Exp $
  *
  * Two-space garbage collector
  *
@@ -84,6 +84,10 @@ static rtsBool weak_done;	/* all done for this pass */
  */
 static rtsBool failed_to_evac;
 
+/* Old to-space (used for two-space collector only)
+ */
+bdescr *old_to_space;
+
 /* -----------------------------------------------------------------------------
    Static function declarations
    -------------------------------------------------------------------------- */
@@ -165,6 +169,7 @@ void GarbageCollect(void (*get_roots)(void))
 
   /* Figure out which generation to collect
    */
+  N = 0;
   for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
     if (generations[g].steps[0].n_blocks >= generations[g].max_blocks) {
       N = g;
@@ -188,6 +193,13 @@ void GarbageCollect(void (*get_roots)(void))
     zeroMutableList(generations[RtsFlags.GcFlags.generations-1].mut_list);
   }
 
+  /* Save the old to-space if we're doing a two-space collection
+   */
+  if (RtsFlags.GcFlags.generations == 1) {
+    old_to_space = g0s0->to_space;
+    g0s0->to_space = NULL;
+  }
+
   /* Initialise to-space in all the generations/steps that we're
    * collecting.
    */
@@ -195,8 +207,12 @@ void GarbageCollect(void (*get_roots)(void))
     generations[g].mut_list = END_MUT_LIST;
 
     for (s = 0; s < generations[g].n_steps; s++) {
+
       /* generation 0, step 0 doesn't need to-space */
-      if (g == 0 && s == 0) { continue; }
+      if (g == 0 && s == 0 && RtsFlags.GcFlags.generations > 1) { 
+	continue; 
+      }
+
       /* Get a free block for to-space.  Extra blocks will be chained on
        * as necessary.
        */
@@ -384,20 +400,78 @@ void GarbageCollect(void (*get_roots)(void))
    * twice the amount of live data plus whatever space the other
    * generations need.
    */
-  if (major_gc) {
-    oldest_gen->max_blocks = 
-      stg_max(oldest_gen->steps[0].to_blocks * RtsFlags.GcFlags.oldGenFactor,
-	      RtsFlags.GcFlags.minOldGenSize);
-    if (oldest_gen->max_blocks > RtsFlags.GcFlags.maxHeapSize / 2) {
-      oldest_gen->max_blocks = RtsFlags.GcFlags.maxHeapSize / 2;
-      if (((int)oldest_gen->max_blocks - (int)oldest_gen->steps[0].to_blocks) < 
-	  (RtsFlags.GcFlags.pcFreeHeap *
-	   RtsFlags.GcFlags.maxHeapSize / 200)) {
+  if (RtsFlags.GcFlags.generations > 1) {
+    if (major_gc) {
+      oldest_gen->max_blocks = 
+	stg_max(oldest_gen->steps[0].to_blocks * RtsFlags.GcFlags.oldGenFactor,
+		RtsFlags.GcFlags.minOldGenSize);
+      if (oldest_gen->max_blocks > RtsFlags.GcFlags.maxHeapSize / 2) {
+	oldest_gen->max_blocks = RtsFlags.GcFlags.maxHeapSize / 2;
+	if (((int)oldest_gen->max_blocks - 
+	     (int)oldest_gen->steps[0].to_blocks) < 
+	    (RtsFlags.GcFlags.pcFreeHeap *
+	     RtsFlags.GcFlags.maxHeapSize / 200)) {
+	}
+      }
+    }
+  } else {
+    /* For a two-space collector, we need to resize the nursery. */
+
+    /* set up a new nursery.  Allocate a nursery size based on a
+     * function of the amount of live data (currently a factor of 2,
+     * should be configurable (ToDo)).  Use the blocks from the old
+     * nursery if possible, freeing up any left over blocks.
+     *
+     * If we get near the maximum heap size, then adjust our nursery
+     * size accordingly.  If the nursery is the same size as the live
+     * data (L), then we need 3L bytes.  We can reduce the size of the
+     * nursery to bring the required memory down near 2L bytes.
+     * 
+     * A normal 2-space collector would need 4L bytes to give the same
+     * performance we get from 3L bytes, reducing to the same
+     * performance at 2L bytes.  
+     */
+    nat blocks = g0s0->to_blocks;
+
+    if ( blocks * 4 > RtsFlags.GcFlags.maxHeapSize ) {
+      int adjusted_blocks;  /* signed on purpose */
+      int pc_free; 
+      
+      adjusted_blocks = (RtsFlags.GcFlags.maxHeapSize - 2 * blocks);
+      IF_DEBUG(gc, fprintf(stderr, "Near maximum heap size of 0x%x blocks, blocks = %d, adjusted to %d\n", RtsFlags.GcFlags.maxHeapSize, blocks, adjusted_blocks));
+      pc_free = adjusted_blocks * 100 / RtsFlags.GcFlags.maxHeapSize;
+      if (pc_free < RtsFlags.GcFlags.pcFreeHeap) /* might even be < 0 */ {
 	heapOverflow();
       }
+      blocks = adjusted_blocks;
+      
+    } else {
+      blocks *= 2;
+      if (blocks < RtsFlags.GcFlags.minAllocAreaSize) {
+	blocks = RtsFlags.GcFlags.minAllocAreaSize;
+      }
+    }
+    
+    if (nursery_blocks < blocks) {
+      IF_DEBUG(gc, fprintf(stderr, "Increasing size of nursery to %d blocks\n", 
+			   blocks));
+      g0s0->blocks = allocNursery(g0s0->blocks, blocks-nursery_blocks);
+    } else {
+      bdescr *next_bd;
+      
+      IF_DEBUG(gc, fprintf(stderr, "Decreasing size of nursery to %d blocks\n", 
+			   blocks));
+      for (bd = g0s0->blocks; nursery_blocks > blocks; nursery_blocks--) {
+	next_bd = bd->link;
+	freeGroup(bd);
+	bd = next_bd;
+      }
+      g0s0->blocks = bd;
     }
+
+    g0s0->n_blocks = nursery_blocks = blocks;
   }
-  
+
   /* run through all the generations/steps and tidy up 
    */
   for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
@@ -410,7 +484,7 @@ void GarbageCollect(void (*get_roots)(void))
       bdescr *next;
       step = &generations[g].steps[s];
 
-      if (!(g == 0 && s == 0)) {
+      if (!(g == 0 && s == 0 && RtsFlags.GcFlags.generations > 1)) {
 	/* Tidy the end of the to-space chains */
 	step->hp_bd->free = step->hp;
 	step->hp_bd->link = NULL;
@@ -455,15 +529,16 @@ void GarbageCollect(void (*get_roots)(void))
 	 * between the maximum size of the oldest and youngest
 	 * generations.
 	 *
-	 * max_blocks =    oldgen_max_blocks  * G
-	 *                 -----------------------
-	 *                       oldest_gen
+	 * max_blocks = alloc_area_size +  
+	 *                 (oldgen_max_blocks - alloc_area_size) * G
+	 *                 -----------------------------------------
+	 *                              oldest_gen
 	 */
 	if (g != 0) {
 	  generations[g].max_blocks = 
-	    stg_max(RtsFlags.GcFlags.minOldGenSize,
-		    (oldest_gen->max_blocks * g) / 
-		    (RtsFlags.GcFlags.generations-1));
+	    RtsFlags.GcFlags.minAllocAreaSize +
+	     (((oldest_gen->max_blocks - RtsFlags.GcFlags.minAllocAreaSize) * g)
+	       / (RtsFlags.GcFlags.generations-1));
 	}
 
       /* for older generations... */
@@ -485,6 +560,34 @@ void GarbageCollect(void (*get_roots)(void))
     }
   }
   
+  /* Two-space collector:
+   * Free the old to-space, and estimate the amount of live data.
+   */
+  if (RtsFlags.GcFlags.generations == 1) {
+    if (old_to_space != NULL) {
+      freeChain(old_to_space);
+    }
+    live = g0s0->to_blocks * BLOCK_SIZE_W + 
+      ((lnat)g0s0->hp_bd->free - (lnat)g0s0->hp_bd->start) / sizeof(W_);
+
+  /* Generational collector:
+   * estimate the amount of live data.
+   */
+  } else {
+    live = 0;
+    for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
+      for (s = 0; s < generations[g].n_steps; s++) {
+	/* approximate amount of live data (doesn't take into account slop
+	 * at end of each block).  ToDo: this more accurately.
+	 */
+	if (g == 0 && s == 0) { continue; }
+	step = &generations[g].steps[s];
+	live += step->n_blocks * BLOCK_SIZE_W + 
+	  ((lnat)step->hp_bd->free -(lnat)step->hp_bd->start) / sizeof(W_);
+      }
+    }
+  }
+
   /* revert dead CAFs and update enteredCAFs list */
   revertDeadCAFs();
   
@@ -507,19 +610,6 @@ void GarbageCollect(void (*get_roots)(void))
   }
   current_nursery = g0s0->blocks;
 
-  live = 0;
-  for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
-    for (s = 0; s < generations[g].n_steps; s++) {
-      /* approximate amount of live data (doesn't take into account slop
-       * at end of each block).  ToDo: this more accurately.
-       */
-      if (g == 0 && s == 0) { continue; }
-      step = &generations[g].steps[s];
-      live += step->n_blocks * BLOCK_SIZE_W + 
-	((lnat)step->hp_bd->free -(lnat)step->hp_bd->start) / sizeof(W_);
-    }
-  }
-
   /* Free the small objects allocated via allocate(), since this will
    * all have been copied into G0S1 now.  
    */
@@ -535,21 +625,26 @@ void GarbageCollect(void (*get_roots)(void))
   
   /* check sanity after GC */
 #ifdef DEBUG
-  for (g = 0; g <= N; g++) {
-    for (s = 0; s < generations[g].n_steps; s++) {
-      if (g == 0 && s == 0) { continue; }
-      IF_DEBUG(sanity, checkHeap(generations[g].steps[s].blocks, NULL));
-      IF_DEBUG(sanity, checkChain(generations[g].steps[s].large_objects));
+  if (RtsFlags.GcFlags.generations == 1) {
+    IF_DEBUG(sanity, checkHeap(g0s0->to_space, NULL));
+    IF_DEBUG(sanity, checkChain(g0s0->large_objects));
+  } else {
+
+    for (g = 0; g <= N; g++) {
+      for (s = 0; s < generations[g].n_steps; s++) {
+	if (g == 0 && s == 0) { continue; }
+	IF_DEBUG(sanity, checkHeap(generations[g].steps[s].blocks, NULL));
+      }
     }
-  }
-  for (g = N+1; g < RtsFlags.GcFlags.generations; g++) {
-    for (s = 0; s < generations[g].n_steps; s++) {
-      IF_DEBUG(sanity, checkHeap(generations[g].steps[s].blocks,
-				 generations[g].steps[s].blocks->start));
-      IF_DEBUG(sanity, checkChain(generations[g].steps[s].large_objects));
+    for (g = N+1; g < RtsFlags.GcFlags.generations; g++) {
+      for (s = 0; s < generations[g].n_steps; s++) {
+	IF_DEBUG(sanity, checkHeap(generations[g].steps[s].blocks,
+				   generations[g].steps[s].blocks->start));
+	IF_DEBUG(sanity, checkChain(generations[g].steps[s].large_objects));
+      }
     }
+    IF_DEBUG(sanity, checkFreeListSanity());
   }
-  IF_DEBUG(sanity, checkFreeListSanity());
 #endif
 
   IF_DEBUG(gc, stat_describe_gens());
diff --git a/ghc/rts/RtsFlags.c b/ghc/rts/RtsFlags.c
index 2d378b5..3d0d866 100644
--- a/ghc/rts/RtsFlags.c
+++ b/ghc/rts/RtsFlags.c
@@ -1,5 +1,5 @@
 /* -----------------------------------------------------------------------------
- * $Id: RtsFlags.c,v 1.4 1999/01/19 15:07:55 simonm Exp $
+ * $Id: RtsFlags.c,v 1.5 1999/01/19 17:06:04 simonm Exp $
  *
  * Functions for parsing the argument list.
  *
@@ -481,7 +481,7 @@ error = rtsTrue;
 
 	      case 'G':
 		RtsFlags.GcFlags.generations = decode(rts_argv[arg]+2);
-		if (RtsFlags.GcFlags.generations <= 1) {
+		if (RtsFlags.GcFlags.generations < 1) {
 		  bad_option(rts_argv[arg]);
 		}
 		break;
diff --git a/ghc/rts/Storage.c b/ghc/rts/Storage.c
index 0403f44..e093888 100644
--- a/ghc/rts/Storage.c
+++ b/ghc/rts/Storage.c
@@ -1,5 +1,5 @@
 /* -----------------------------------------------------------------------------
- * $Id: Storage.c,v 1.4 1999/01/19 15:07:56 simonm Exp $
+ * $Id: Storage.c,v 1.5 1999/01/19 17:06:05 simonm Exp $
  *
  * Storage manager front end
  *
@@ -39,7 +39,6 @@ step *g0s0;			/* generation 0, step 0, for convenience */
 /*
  * Forward references
  */
-static bdescr *allocNursery   (nat blocks);
 static void *stgAllocForGMP   (size_t size_in_bytes);
 static void *stgReallocForGMP (void *ptr, size_t old_size, size_t new_size);
 static void  stgDeallocForGMP (void *ptr, size_t size);
@@ -49,6 +48,7 @@ initStorage (void)
 {
   nat g, s;
   step *step;
+  generation *gen;
 
   initBlockAllocator();
   
@@ -57,50 +57,50 @@ initStorage (void)
 					     * sizeof(struct _generation),
 					     "initStorage: gens");
 
-  /* set up all generations */
+  /* Initialise all generations */
   for(g = 0; g < RtsFlags.GcFlags.generations; g++) {
-    generations[g].no = g;
-    generations[g].mut_list = END_MUT_LIST;
-    generations[g].collections = 0;
-    generations[g].failed_promotions = 0;
+    gen = &generations[g];
+    gen->no = g;
+    gen->mut_list = END_MUT_LIST;
+    gen->collections = 0;
+    gen->failed_promotions = 0;
+    gen->max_blocks = RtsFlags.GcFlags.minOldGenSize;
   }
 
-  /* Oldest generation: one step */
-  g = RtsFlags.GcFlags.generations-1;
-  generations[g].n_steps = 1;
-  generations[g].steps = 
-    stgMallocBytes(1 * sizeof(struct _step), "initStorage: last step");
-  generations[g].max_blocks = RtsFlags.GcFlags.minOldGenSize;
-  step = &generations[g].steps[0];
-  step->no = 0;
-  step->gen = &generations[g];
-  step->blocks = NULL;
-  step->n_blocks = 0;
-  step->to = step;		/* destination is this step */
-  step->hp = NULL;
-  step->hpLim = NULL;
-  step->hp_bd = NULL;
-  
-  /* set up all except the oldest generation with 2 steps */
-  for(g = 0; g < RtsFlags.GcFlags.generations-1; g++) {
-    generations[g].n_steps = 2;
-    generations[g].steps  = stgMallocBytes (2 * sizeof(struct _step),
-					    "initStorage: steps");
-    generations[g].max_blocks = RtsFlags.GcFlags.minOldGenSize;
+  /* A couple of convenience pointers */
+  g0 = &generations[0];
+  oldest_gen = &generations[RtsFlags.GcFlags.generations-1];
+
+  /* Allocate step structures in each generation */
+  if (RtsFlags.GcFlags.generations > 1) {
+    /* Only for multiple-generations */
+
+    /* Oldest generation: one step */
+    oldest_gen->n_steps = 1;
+    oldest_gen->steps = 
+      stgMallocBytes(1 * sizeof(struct _step), "initStorage: last step");
+
+    /* set up all except the oldest generation with 2 steps */
+    for(g = 0; g < RtsFlags.GcFlags.generations-1; g++) {
+      generations[g].n_steps = 2;
+      generations[g].steps  = stgMallocBytes (2 * sizeof(struct _step),
+					      "initStorage: steps");
+    }
+    
+  } else {
+    /* single generation, i.e. a two-space collector */
+    g0->n_steps = 1;
+    g0->steps = stgMallocBytes (sizeof(struct _step), "initStorage: steps");
   }
 
-  for (g = 0; g < RtsFlags.GcFlags.generations-1; g++) {
+  /* Initialise all steps */
+  for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
     for (s = 0; s < generations[g].n_steps; s++) {
       step = &generations[g].steps[s];
       step->no = s;
       step->blocks = NULL;
       step->n_blocks = 0;
       step->gen = &generations[g];
-      if ( s == 1 ) {
-	step->to = &generations[g+1].steps[0];
-      } else {
-	step->to = &generations[g].steps[s+1];
-      }
       step->hp = NULL;
       step->hpLim = NULL;
       step->hp_bd = NULL;
@@ -110,16 +110,29 @@ initStorage (void)
     }
   }
   
-  oldest_gen = &generations[RtsFlags.GcFlags.generations-1];
+  /* Set up the destination pointers in each younger gen. step */
+  for (g = 0; g < RtsFlags.GcFlags.generations-1; g++) {
+    for (s = 0; s < generations[g].n_steps; s++) {
+      step = &generations[g].steps[s];
+      if ( s == 1 ) {
+	step->to = &generations[g+1].steps[0];
+      } else {
+	step->to = &generations[g].steps[s+1];
+      }
+    }
+  }
+  
+  /* The oldest generation has one step and its destination is the
+   * same step. */
+  oldest_gen->steps[0].to = &oldest_gen->steps[0];
 
   /* generation 0 is special: that's the nursery */
-  g0 = &generations[0];
   generations[0].max_blocks = 0;
 
   /* G0S0: the allocation area */
   step = &generations[0].steps[0];
   g0s0 = step;
-  step->blocks   = allocNursery(RtsFlags.GcFlags.minAllocAreaSize);
+  step->blocks   = allocNursery(NULL, RtsFlags.GcFlags.minAllocAreaSize);
   step->n_blocks = RtsFlags.GcFlags.minAllocAreaSize;
   nursery_blocks = RtsFlags.GcFlags.minAllocAreaSize;
   current_nursery = step->blocks;
@@ -142,13 +155,12 @@ initStorage (void)
   IF_DEBUG(gc, stat_describe_gens());
 }
 
-static bdescr *
-allocNursery (nat blocks)
+extern bdescr *
+allocNursery (bdescr *last_bd, nat blocks)
 {
-  bdescr *last_bd, *bd;
+  bdescr *bd;
   nat i;
 
-  last_bd = NULL;
   /* Allocate a nursery */
   for (i=0; i < blocks; i++) {
     bd = allocBlock();
@@ -200,8 +212,6 @@ recordMutable(StgMutClosure *p)
 void
 newCAF(StgClosure* caf)
 {
-  const StgInfoTable *info;
-
   /* Put this CAF on the mutable list for the old generation.
    * This is a HACK - the IND_STATIC closure doesn't really have
    * a mut_link field, but we pretend it has - in fact we re-use
@@ -213,10 +223,14 @@ newCAF(StgClosure* caf)
   oldest_gen->mut_list = (StgMutClosure *)caf;
 
 #ifdef DEBUG
-  info = get_itbl(caf);
-  ASSERT(info->type == IND_STATIC);
-  STATIC_LINK2(info,caf) = caf_list;
-  caf_list = caf;
+  { 
+    const StgInfoTable *info;
+    
+    info = get_itbl(caf);
+    ASSERT(info->type == IND_STATIC);
+    STATIC_LINK2(info,caf) = caf_list;
+    caf_list = caf;
+  }
 #endif
 }
 
@@ -352,10 +366,15 @@ memInventory(void)
   lnat total_blocks = 0, free_blocks = 0;
 
   /* count the blocks we current have */
+
   for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
     for (s = 0; s < generations[g].n_steps; s++) {
       step = &generations[g].steps[s];
       total_blocks += step->n_blocks;
+      if (RtsFlags.GcFlags.generations == 1) {
+	/* two-space collector has a to-space too :-) */
+	total_blocks += g0s0->to_blocks;
+      }
       for (bd = step->large_objects; bd; bd = bd->link) {
 	total_blocks += bd->blocks;
 	/* hack for megablock groups: they have an extra block or two in
diff --git a/ghc/rts/StoragePriv.h b/ghc/rts/StoragePriv.h
index 24b7a84..defe142 100644
--- a/ghc/rts/StoragePriv.h
+++ b/ghc/rts/StoragePriv.h
@@ -1,5 +1,5 @@
 /* -----------------------------------------------------------------------------
- * $Id: StoragePriv.h,v 1.4 1999/01/18 15:21:40 simonm Exp $
+ * $Id: StoragePriv.h,v 1.5 1999/01/19 17:06:05 simonm Exp $
  *
  * Internal Storage Manger Interface
  *
@@ -106,6 +106,8 @@ extern nat nursery_blocks;
 extern nat alloc_blocks;
 extern nat alloc_blocks_lim;
 
+extern bdescr *allocNursery (bdescr *last_bd, nat blocks);
+
 static inline void
 dbl_link_onto(bdescr *bd, bdescr **list)
 {