I'm missing something obvious...

["Zack Weinberg" <zackw at stanford dot edu>]

I'm trying to simplify the code dealing with nested garbage-collection
contexts.  I have implemented something that *should* work, but
doesn't: on the first collection after anything is allocated in a
nested context, live objects get freed, and we crash.  I suspect I'm
missing something obvious.  Would someone please look at the appended
patch and send me a clue?

There's an explanation of the algorithm above ggc_push_context.  It's
possible to make it more memory-efficient but that masks the bug so I
haven't included that change.  There are debugging printouts.  If you
configure with --enable-checking=gc,gcac,misc, you'll get a crash
compiling muldi3:

Starting program: /home/zack/src/b/gcc_vanilla/gcc/./cc1 -lang-c -I. -I. -I../../../gcc_vanilla/gcc -I../../../gcc_vanilla/gcc/. -I../../../gcc_vanilla/gcc/config -I../../../gcc_vanilla/gcc/../include -iprefix ./../lib/gcc-lib/i686-pc-linux-gnu/3.1/ -isystem ./include -isystem /work/inst/i686-pc-linux-gnu/bin/include -D__GNUC__=3 -D__GNUC_MINOR__=1 -D__GNUC_PATCHLEVEL__=0 -D__ELF__ -Dunix -Dlinux -D__ELF__ -D__unix__ -D__linux__ -D__unix -D__linux -Asystem=posix -D__OPTIMIZE__ -D__STDC_HOSTED__=1 -W -Wall -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -Acpu=i386 -Amachine=i386 -Di386 -D__i386 -D__i386__ -D__tune_i686__ -D__tune_pentiumpro__ -D__PIC__ -D__pic__ -DIN_GCC -DHAVE_GTHR_DEFAULT -DIN_LIBGCC2 -D__GCC_FLOAT_NOT_NEEDED -DL_muldi3 -isystem /work/inst/i686-pc-linux-gnu/include -isystem ./include ../../../gcc_vanilla/gcc/libgcc2.c -dumpbase libgcc2.c -g1 -O2 -W -Wall -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -version -fPIC -o /tmp/ccnImlYh.s -quiet
GNU CPP version 3.1 20010521 (experimental) (cpplib) (i386 Linux/ELF)
GNU C version 3.1 20010521 (experimental) (i686-pc-linux-gnu)
        compiled by GNU C version 2.95.4 20010506 (Debian prerelease).
[wait some time...]
{GC context+ 1} {GC context- 0} 
01 0x40321000 on 0x8495760 
01 0x40321010 on 0x8495760 
01 0x40322000 on 0x8416890 
01 0x40322008 on 0x8416890 
{GC lower page 0x8416890} {GC lower page 0x8495760} 
Program received signal SIGSEGV, Segmentation fault.
0x81bde83 in reg_scan_mark_refs (x=0x403043a0, insn=0x403043e0, note_flag=0, 
    min_regno=0) at ../../../gcc_vanilla/gcc/regclass.c:2447
2447                if (fmt[i] == 'e')

The rtx pointed to by 'x' has been freed incorrectly...

TIA,

-- 
zw                I met a traveller from an antique land
                  Who said: 'Your name is Ozymandias,
                  king of kings, and I claim my five pounds!'
                  	-- Del Cotter

===================================================================
Index: ggc-page.c
--- ggc-page.c	2001/02/20 05:49:05	1.39
+++ ggc-page.c	2001/05/22 02:07:42
@@ -74,7 +74,8 @@ Boston, MA 02111-1307, USA.  */
 
    Each page-entry also has a context depth, which is used to track
    pushing and popping of allocation contexts.  Only objects allocated
-   in the current (highest-numbered) context may be collected.  
+   in the current (highest-numbered) context may be collected.  No page
+   contains objects from more than one context.
 
    Page entries are arranged in an array of singly-linked lists.  The
    array is indexed by the allocation size, in bits, of the pages on
@@ -225,10 +226,6 @@ typedef struct page_entry 
   struct page_group *group;
 #endif
 
-  /* Saved in-use bit vector for pages that aren't in the topmost
-     context during collection.  */
-  unsigned long *save_in_use_p;
-
   /* Context depth of this page.  */
   unsigned short context_depth;
 
@@ -316,8 +313,10 @@ static struct globals
   /* Total amount of memory mapped.  */
   size_t bytes_mapped;
 
-  /* The current depth in the context stack.  */
-  unsigned short context_depth;
+  /* The current depth in the context stack.  There are two different
+     markers.  See comments above ggc_push_context for details. */
+  unsigned short collection_depth;
+  unsigned short allocation_depth;
 
   /* A file descriptor open to /dev/zero for reading.  */
 #if defined (HAVE_MMAP_DEV_ZERO)
@@ -372,7 +371,6 @@ static void free_page PARAMS ((struct pa
 static void release_pages PARAMS ((void));
 static void clear_marks PARAMS ((void));
 static void sweep_pages PARAMS ((void));
-static void ggc_recalculate_in_use_p PARAMS ((page_entry *));
 
 #ifdef GGC_POISON
 static void poison_pages PARAMS ((void));
@@ -714,7 +712,7 @@ alloc_page (order)
 
   entry->bytes = entry_size;
   entry->page = page;
-  entry->context_depth = G.context_depth;
+  entry->context_depth = G.allocation_depth;
   entry->order = order;
   entry->num_free_objects = num_objects;
   entry->next_bit_hint = 1;
@@ -860,6 +858,10 @@ ggc_alloc (size)
   struct page_entry *entry;
   void *result;
 
+  /* If the collection depth has been adjusted, start allocating
+     in the new topmost context.  */
+  //  G.allocation_depth = G.collection_depth;
+
   if (size <= 256)
     order = size_lookup[size];
   else
@@ -873,8 +875,16 @@ ggc_alloc (size)
      the head of the list.  */
   entry = G.pages[order];
 
+  /* Find a page with free objects that's at the current allocation
+     depth.  FIXME: Ensure that pages are sorted by allocation depth,
+     then this loop will not be necessary.  */
+  while (entry && entry->num_free_objects
+	 && entry->context_depth != G.allocation_depth)
+    entry = entry->next;
+
   /* If there is no page for this object size, or all pages in this
-     context are full, allocate a new page.  */
+     context are full or not at the current allocation depth, get a
+     new page.  */
   if (entry == NULL || entry->num_free_objects == 0)
     {
       struct page_entry *new_entry;
@@ -958,6 +968,10 @@ ggc_alloc (size)
 	     "Allocating object, requested size=%ld, actual=%ld at %p on %p\n",
 	     (long) size, (long) OBJECT_SIZE (order), result, (PTR) entry);
 
+  if (0 != G.allocation_depth)
+    fprintf (stderr, "\n%d%d %p on %p ", G.collection_depth, G.allocation_depth,
+	     result, (PTR) entry);
+
   return result;
 }
 
@@ -1098,89 +1112,61 @@ init_ggc ()
     }
 }
 
-/* Increment the `GC context'.  Objects allocated in an outer context
-   are never freed, eliminating the need to register their roots.  */
+/* Enter a new 'GC context'.  This tells the garbage collector that
+   the registered GC roots do not necessarily cover all objects
+   allocated at the time ggc_push_context is called.  This continues
+   to be true until ggc_pop_context is called.  If a collection occurs
+   while a context has been pushed, objects allocated between paired
+   calls to ggc_push/pop_context must still be reachable from the
+   known set of roots.  ggc_push_context can be called repeatedly;
+   only objects in the topmost context are collectable.
+
+   Here's how it works:
+
+   No page contains objects in more than one context.  The _context
+   depth_ of a page indicates how far down in the context stack it is.
+   Allocation creates new pages whose context depth is equal to the
+   "allocation depth."
+
+   When ggc_collect is called, the mark phase proceeds as normal, but
+   the sweep phase does not touch any pages whose depth is below the
+   "collection depth."  
+
+   ggc_push_context increments the allocation depth and the collection
+   depth.  ggc_pop_context lowers the collection depth but leaves the
+   allocation depth alone.  The allocation depth is set equal to the
+   collection depth at the end of each collection.  The hysterisis is
+   necessary because, between a call to ggc_pop_context and the next
+   collection, the in-use bit vectors for pages between the old and
+   new context depths are inaccurate, so allocation must not touch them.  */
 
 void
 ggc_push_context ()
 {
-  ++G.context_depth;
+  ++G.collection_depth;
+  ++G.allocation_depth;
 
   /* Die on wrap.  */
-  if (G.context_depth == 0)
+  if (G.collection_depth == 0)
     abort ();
-}
-
-/* Merge the SAVE_IN_USE_P and IN_USE_P arrays in P so that IN_USE_P
-   reflects reality.  Recalculate NUM_FREE_OBJECTS as well.  */
 
-static void
-ggc_recalculate_in_use_p (p)
-     page_entry *p;
-{
-  unsigned int i;
-  size_t num_objects;
-
-  /* Because the past-the-end bit in in_use_p is always set, we 
-     pretend there is one additional object.  */
-  num_objects = OBJECTS_PER_PAGE (p->order) + 1;
-
-  /* Reset the free object count.  */
-  p->num_free_objects = num_objects;
-
-  /* Combine the IN_USE_P and SAVE_IN_USE_P arrays.  */
-  for (i = 0; 
-       i < CEIL (BITMAP_SIZE (num_objects),
-		 sizeof (*p->in_use_p));
-       ++i)
-    {
-      unsigned long j;
-
-      /* Something is in use if it is marked, or if it was in use in a
-	 context further down the context stack.  */
-      p->in_use_p[i] |= p->save_in_use_p[i];
-
-      /* Decrement the free object count for every object allocated.  */
-      for (j = p->in_use_p[i]; j; j >>= 1)
-	p->num_free_objects -= (j & 1);
-    }
-
-  if (p->num_free_objects >= num_objects)
-    abort ();
+  fprintf(stderr, "{GC context+ %d} ", G.collection_depth);
 }
 
-/* Decrement the `GC context'.  All objects allocated since the 
-   previous ggc_push_context are migrated to the outer context.  */
+/* Decrement the `GC context'.  All objects allocated since the
+   previous ggc_push_context will be migrated to the current context
+   in the next collection. */
 
 void
 ggc_pop_context ()
 {
-  unsigned order, depth;
-
-  depth = --G.context_depth;
+  --G.collection_depth;
 
-  /* Any remaining pages in the popped context are lowered to the new
-     current context; i.e. objects allocated in the popped context and
-     left over are imported into the previous context.  */
-  for (order = 2; order < NUM_ORDERS; order++)
-    {
-      page_entry *p;
-
-      for (p = G.pages[order]; p != NULL; p = p->next)
-	{
-	  if (p->context_depth > depth)
-	    p->context_depth = depth;
+  /* Die on wrap.  */
+  if (G.collection_depth > G.allocation_depth)
+    abort ();
 
-	  /* If this page is now in the topmost context, and we'd
-	     saved its allocation state, restore it.  */
-	  else if (p->context_depth == depth && p->save_in_use_p)
-	    {
-	      ggc_recalculate_in_use_p (p);
-	      free (p->save_in_use_p);
-	      p->save_in_use_p = 0;
-	    }
-	}
-    }
+  fprintf(stderr, "{GC context- %d} ", G.collection_depth);
 }
 
 /* Unmark all objects.  */
@@ -1204,18 +1190,8 @@ clear_marks ()
 	    abort ();
 #endif
 
-	  /* Pages that aren't in the topmost context are not collected;
-	     nevertheless, we need their in-use bit vectors to store GC
-	     marks.  So, back them up first.  */
-	  if (p->context_depth < G.context_depth)
-	    {
-	      if (! p->save_in_use_p)
-		p->save_in_use_p = xmalloc (bitmap_size);
-	      memcpy (p->save_in_use_p, p->in_use_p, bitmap_size);
-	    }
-
-	  /* Reset reset the number of free objects and clear the
-             in-use bits.  These will be adjusted by mark_obj.  */
+	  /* Reset the number of free objects and clear the in-use
+             bits.  These will be adjusted by ggc_set_mark.  */
 	  p->num_free_objects = num_objects;
 	  memset (p->in_use_p, 0, bitmap_size);
 
@@ -1263,13 +1239,21 @@ sweep_pages ()
 
 	  G.allocated += OBJECT_SIZE (order) * live_objects;
 
-	  /* Only objects on pages in the topmost context should get
-	     collected.  */
-	  if (p->context_depth < G.context_depth)
-	    ;
+	  /* Pages below the current collection depth are left strictly
+	     alone.  */
+	  if (p->context_depth < G.collection_depth)
+	    continue;
 
+	  /* Pages above the current collection depth are lowered
+	     to that depth, then swept normally.  */
+
+	  if (p->context_depth > G.collection_depth) {
+	    p->context_depth = G.collection_depth;
+	    fprintf(stderr, "{GC lower page %p} ", p);
+	  }
+
 	  /* Remove the page if it's empty.  */
-	  else if (live_objects == 0)
+	  if (live_objects == 0)
 	    {
 	      if (! previous)
 		G.pages[order] = next;
@@ -1324,12 +1308,6 @@ sweep_pages ()
 	  p = next;
 	} 
       while (! done);
-
-      /* Now, restore the in_use_p vectors for any pages from contexts
-         other than the current one.  */
-      for (p = G.pages[order]; p; p = p->next)
-	if (p->context_depth != G.context_depth)
-	  ggc_recalculate_in_use_p (p);
     }
 }
 
@@ -1351,7 +1329,7 @@ poison_pages ()
 	{
 	  size_t i;
 
-	  if (p->context_depth != G.context_depth)
+	  if (p->context_depth < G.collection_depth)
 	    /* Since we don't do any collection for pages in pushed
 	       contexts, there's no need to do any poisoning.  And
 	       besides, the IN_USE_P array isn't valid until we pop
@@ -1404,6 +1382,10 @@ ggc_collect ()
 #endif
 
   sweep_pages ();
+
+  /* Now that all pages above the collection depth have been lowered to
+     that depth, it's safe to lower the allocation depth.  */
+  G.allocation_depth = G.collection_depth;
 
   G.allocated_last_gc = G.allocated;
   if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED)