GNU bug report logs - #28590
Weak tables in 2.2.2 grow indefinitely

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 28590 in the body.
You can then email your comments to 28590 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: bug-guile <at> gnu.org
Subject: Weak tables in 2.2.2 grow indefinitely
Date: Mon, 25 Sep 2017 10:49:13 +0200

Consider this program:

--8<---------------cut here---------------start------------->8---
(use-modules (ice-9 format))

(define loops 3000000)

(define table
  (make-weak-key-hash-table))

(let loop ((i loops))
  (unless #f ;(zero? i)
    (when (zero? (modulo i 100000))
      (format #t "heap-size: ~,2h MiB  table: ~s~%"
              (/ (assoc-ref (gc-stats) 'heap-size) (expt 2. 20))
              table))

    (hashq-set! table (cons 1 2) #t)
    (loop (1- i))))
--8<---------------cut here---------------end--------------->8---

On 2.0.14, the heap size stays at around 24 MiB, and the table size is
stable at 224,717 buckets (?).

On 2.2.2, the heap grows indefinitely (though logarithmically).  It’s
not deterministic though: sometimes the heap size stabilizes in the
140–300 MiB range, and sometimes it keeps growing endlessly even though
the table size reaches a maxium at 7,190,537 entries.

Ludo’.

Message #10 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: 28590 <at> debbugs.gnu.org
Subject: Re: bug#28590: Weak tables in 2.2.2 grow indefinitely
Date: Tue, 26 Sep 2017 11:57:54 +0200

ludo <at> gnu.org (Ludovic Courtès) skribis:

> Consider this program:
>
> (use-modules (ice-9 format))
>
> (define loops 3000000)
>
> (define table
>   (make-weak-key-hash-table))
>
> (let loop ((i loops))
>   (unless #f ;(zero? i)
>     (when (zero? (modulo i 100000))
>       (format #t "heap-size: ~,2h MiB  table: ~s~%"
>               (/ (assoc-ref (gc-stats) 'heap-size) (expt 2. 20))
>               table))
>
>     (hashq-set! table (cons 1 2) #t)
>     (loop (1- i))))

I’ve changed it to do:

    (hashq-set! table (cons 1 2) (make-vector 10000))

Then if we build Guile with -DGC_DEBUG=1, link it against libgc built
with -DKEEP_BACK_PTRS=1, and run with “GC_BACKTRACES=1”, we see that the
heap is full of those 10,000-element vectors:

  0x54ae9030 (../libguile/gc.h:232, sz=80008, NORMAL)
  Reference could not be found
  0x1bee5030 (../libguile/gc.h:232, sz=80008, NORMAL)
  Reference could not be found
  0x60491030 (../libguile/gc.h:232, sz=80008, NORMAL)
  Reference could not be found

Problem is that “Reference could not be found” corresponds to
GC_UNREFERENCED in <gc_backptr.h>, meaning that there’s no reference
holding this object.  Interesting no?

(Though it could also be a bug in the back-pointer code, or pretty much
anything!)

Ludo’.

Message #13 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: 28590 <at> debbugs.gnu.org
Cc: Andy Wingo <wingo <at> igalia.com>
Subject: Re: bug#28590: Weak tables in 2.2.2 grow indefinitely
Date: Mon, 02 Oct 2017 11:53:09 +0200

ludo <at> gnu.org (Ludovic Courtès) skribis:

> On 2.2.2, the heap grows indefinitely (though logarithmically).  It’s
> not deterministic though: sometimes the heap size stabilizes in the
> 140–300 MiB range, and sometimes it keeps growing endlessly even though
> the table size reaches a maxium at 7,190,537 entries.

Below is a simple reproducer in C that I’ve also reported at
<https://github.com/ivmai/bdwgc/issues/182>:

--8<---------------cut here---------------start------------->8---
#define GC_DEBUG 1
#include <gc.h>
#include <stdlib.h>
#include <stdio.h>

int
main ()
{
  GC_INIT ();

  while (1)
    {
      unsigned int count = 777 * (random () % 1000);
      void **p = GC_MALLOC_ATOMIC (count * sizeof *p);

      for (unsigned int i = 0; i < count; i++)
	{
	  void *key = GC_MALLOC_ATOMIC (10);
	  p[i] = key;
	  GC_GENERAL_REGISTER_DISAPPEARING_LINK (&p[i], key); /* <- !!! */
	}

      static unsigned int loops = 0;
      if (loops++ % 10 == 0)
	printf ("iteration %4u, heap size = %li MiB\n",
		loops, GC_get_heap_size () / (1024 * 1024));
    }
}
--8<---------------cut here---------------end--------------->8---

Ludo’.

Message #16 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: wingo <at> igalia.com
Cc: Ludovic Courtès <ludo <at> gnu.org>, 28590 <at> debbugs.gnu.org
Subject: [PATCH 2/7] weak-table: Stress the GC a little less when resizing.
Date: Tue,  3 Oct 2017 13:43:47 +0200

* libguile/weak-table.c (resize_table): Move 'allocate_entries' call
outside of the loop.
---
 libguile/weak-table.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index a0bebca5e..1aa2a0fcc 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -476,10 +476,11 @@ resize_table (scm_t_weak_table *table)
       if (new_size_index == table->size_index)
         return;
       new_size = hashtable_size[new_size_index];
-      new_entries = allocate_entries (new_size, table->kind);
     }
   while (!is_acceptable_size_index (table, new_size_index));
 
+  new_entries = allocate_entries (new_size, table->kind);
+
   old_entries = table->entries;
   old_size = table->size;
   
-- 
2.14.2

Message #19 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: wingo <at> igalia.com
Cc: Ludovic Courtès <ludo <at> gnu.org>, 28590 <at> debbugs.gnu.org
Subject: [PATCH 1/7] weak-table: Fix unbounded growth of the disappearing link
 table.
Date: Tue,  3 Oct 2017 13:43:46 +0200

Partly fixes <https://bugs.gnu.org/28590>.

* libguile/weak-table.c (resize_table): Remove all disappearing links on
OLD_ENTRIES, and reset all of OLD_ENTRIES.
---
 libguile/weak-table.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index 599c4cf0e..a0bebca5e 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -498,11 +498,19 @@ resize_table (scm_t_weak_table *table)
       scm_t_weak_entry copy;
       unsigned long new_k, distance;
 
+      /* Make sure we don't leave a disappearing link behind us.
+	 See <https://github.com/ivmai/bdwgc/issues/182>.  */
+      unregister_disappearing_links (&old_entries[old_k], table->kind);
+
       if (!old_entries[old_k].hash)
-        continue;
-      
+	{
+	  old_entries[old_k].key = old_entries[old_k].value = 0;
+	  continue;
+	}
+
       copy_weak_entry (&old_entries[old_k], &copy);
-      
+      old_entries[old_k].key = old_entries[old_k].value = 0;
+
       if (!copy.key || !copy.value)
         continue;
       
-- 
2.14.2

Message #22 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: wingo <at> igalia.com
Cc: Ludovic Courtès <ludo <at> gnu.org>, 28590 <at> debbugs.gnu.org
Subject: [PATCH 0/7] Attempt to reduce memory growth
Date: Tue,  3 Oct 2017 13:43:45 +0200

So!  This is an attempt to mitigate memory growth in the use case shown
at <https://debbugs.gnu.org/cgi/bugreport.cgi?bug=28590>.
Unfortunately, it doesn’t that much: on the python.scm compilation
“benchmark”, there’s a bit less than 10% gain both in memory consumption
and CPU time.

I’ll try to combine that with incremental marking of the weak table, but
I’m not very hopeful.

Andy: I need your help!  :-)

Ludo’.

Ludovic Courtès (7):
  weak-table: Fix unbounded growth of the disappearing link table.
  weak-table: Stress the GC a little less when resizing.
  weak-table: Make sure 'move_disappearing_links' actually moves links.
  weak-table: Always unregister previous links when inserting an entry.
  weak-table: 'move_weak_entry' reports disappeared links.
  weak-table: 'rob_from_rich' accounts for disappeared entries.
  weak-table: Resize less frequently.

 libguile/weak-table.c | 144 +++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 114 insertions(+), 30 deletions(-)

-- 
2.14.2

Message #25 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: wingo <at> igalia.com
Cc: Ludovic Courtès <ludo <at> gnu.org>, 28590 <at> debbugs.gnu.org
Subject: [PATCH 7/7] weak-table: Resize less frequently.
Date: Tue,  3 Oct 2017 13:43:52 +0200

* libguile/weak-table.c (do_count_entries, update_entry_count): New
functions.
(resize_table): Use it; check 'n_items' and return if there's nothing to
do.
---
 libguile/weak-table.c | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index 24fff4e73..1a99a130f 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -504,6 +504,32 @@ is_acceptable_size_index (scm_t_weak_table *table, int size_index)
   return 0;
 }
 
+static void *
+do_count_entries (void *data)
+{
+  size_t i, count = 0;
+  scm_t_weak_table *table = data;
+
+  for (i = 0; i < table->size; i++)
+    {
+      if (table->entries[i].hash != 0
+	  && table->entries[i].key != 0
+	  && table->entries[i].value != 0)
+	count++;
+    }
+
+  table->n_items = count;
+
+  return table;
+}
+
+/* Traverse all of TABLE and updates its 'n_items' field.  */
+static void
+update_entry_count (scm_t_weak_table *table)
+{
+  GC_call_with_alloc_lock (do_count_entries, table);
+}
+
 static void
 resize_table (scm_t_weak_table *table)
 {
@@ -511,6 +537,14 @@ resize_table (scm_t_weak_table *table)
   int new_size_index;
   unsigned long old_size, new_size, old_k;
 
+  /* Make sure we have an accurate view of TABLE's load factor before
+     attempting to resize it.  */
+  update_entry_count (table);
+
+  if (table->n_items > table->lower
+      && table->n_items < table->upper)
+    return;
+
   do 
     {
       new_size_index = compute_size_index (table);
-- 
2.14.2

Message #28 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: wingo <at> igalia.com
Cc: Ludovic Courtès <ludo <at> gnu.org>, 28590 <at> debbugs.gnu.org
Subject: [PATCH 5/7] weak-table: 'move_weak_entry' reports disappeared links.
Date: Tue,  3 Oct 2017 13:43:50 +0200

* libguile/weak-table.c (move_weak_entry): Change to return a Boolean.
(give_to_poor): Remove 'copy_weak_entry' call and adjust accordingly.
---
 libguile/weak-table.c | 46 +++++++++++++++++++++++++++++-----------------
 1 file changed, 29 insertions(+), 17 deletions(-)

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index b5db3ef48..5c4b3d30a 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -199,28 +199,45 @@ move_disappearing_links (scm_t_weak_entry *from, scm_t_weak_entry *to,
     }
 }
 
-static void
+/* Move weak entry FROM to TO.  Return non-zero on success, and zero if
+   the entry at FROM disappeared in the meantime.  */
+static int
 move_weak_entry (scm_t_weak_entry *from, scm_t_weak_entry *to,
                  scm_t_weak_table_kind kind)
 {
   if (from->hash)
     {
       scm_t_weak_entry copy;
-      
+
       copy_weak_entry (from, &copy);
-      to->hash = copy.hash;
-      to->key = copy.key;
-      to->value = copy.value;
 
-      move_disappearing_links (from, to,
-                               SCM_PACK (copy.key), SCM_PACK (copy.value),
-                               kind);
+      if (copy.key != 0 && copy.value != 0)
+	{
+	  to->hash = copy.hash;
+	  to->key = copy.key;
+	  to->value = copy.value;
+
+	  move_disappearing_links (from, to,
+				   SCM_PACK (copy.key), SCM_PACK (copy.value),
+				   kind);
+	  return 1;
+	}
+      else
+	{
+	  /* Lost weak reference: make sure all the disappearing links
+	     are registered (in the case of a doubly-weak table, one of
+	     the disappearing links could still be there.)  */
+	  memset (to, '\0', sizeof *to);
+	  unregister_disappearing_links (from, kind);
+	  return 0;
+	}
     }
   else
     {
+      unregister_disappearing_links (from, kind);
       to->hash = 0;
-      to->key = 0;
-      to->value = 0;
+      to->key = to->value = 0;
+      return 0;
     }
 }
 
@@ -301,16 +318,14 @@ give_to_poor (scm_t_weak_table *table, unsigned long k)
     {
       unsigned long next = (k + 1) % size;
       unsigned long hash;
-      scm_t_weak_entry copy;
 
       hash = table->entries[next].hash;
 
       if (!hash || hash_to_index (hash, size) == next)
         break;
 
-      copy_weak_entry (&table->entries[next], &copy);
-
-      if (!copy.key || !copy.value)
+      if (!move_weak_entry (&table->entries[next], &table->entries[k],
+			    table->kind))
         /* Lost weak reference.  */
         {
           give_to_poor (table, next);
@@ -318,9 +333,6 @@ give_to_poor (scm_t_weak_table *table, unsigned long k)
           continue;
         }
 
-      move_weak_entry (&table->entries[next], &table->entries[k],
-                       table->kind);
-
       k = next;
     }
 
-- 
2.14.2

Message #31 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: wingo <at> igalia.com
Cc: Ludovic Courtès <ludo <at> gnu.org>, 28590 <at> debbugs.gnu.org
Subject: [PATCH 6/7] weak-table: 'rob_from_rich' accounts for disappeared
 entries.
Date: Tue,  3 Oct 2017 13:43:51 +0200

* libguile/weak-table.c (rob_from_rich): Leave the loop also if 'key' or
'value' is zero.  Reset 'hash'.
---
 libguile/weak-table.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index 5c4b3d30a..24fff4e73 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -292,7 +292,11 @@ rob_from_rich (scm_t_weak_table *table, unsigned long k)
   empty = k;
   do 
     empty = (empty + 1) % size;
-  while (table->entries[empty].hash);
+  while (table->entries[empty].hash
+	 && table->entries[empty].key
+	 && table->entries[empty].value);
+
+  table->entries[empty].hash = 0;
 
   do
     {
-- 
2.14.2

Message #34 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: wingo <at> igalia.com
Cc: Ludovic Courtès <ludo <at> gnu.org>, 28590 <at> debbugs.gnu.org
Subject: [PATCH 4/7] weak-table: Always unregister previous links when
 inserting an entry.
Date: Tue,  3 Oct 2017 13:43:49 +0200

* libguile/weak-table.c (weak_table_put_x): Always call
'unregister_disappearing_links' before returning.
---
 libguile/weak-table.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index 7d8633165..b5db3ef48 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -731,9 +731,9 @@ weak_table_put_x (scm_t_weak_table *table, unsigned long hash,
       return;
     }
 
-  if (entries[k].hash)
-    unregister_disappearing_links (&entries[k], table->kind);
-  else
+  unregister_disappearing_links (&entries[k], table->kind);
+
+  if (!entries[k].hash)
     table->n_items++;
 
   entries[k].hash = hash;
-- 
2.14.2

Message #37 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: wingo <at> igalia.com
Cc: Ludovic Courtès <ludo <at> gnu.org>, 28590 <at> debbugs.gnu.org
Subject: [PATCH 3/7] weak-table: Make sure 'move_disappearing_links' actually
 moves links.
Date: Tue,  3 Oct 2017 13:43:48 +0200

* libguile/weak-table.c (move_disappearing_links): Check the return
value of 'GC_move_disappearing_link' and call
'register_disappearing_links' upon GC_NOT_FOUND.
(GC_move_disappearing_link) [!HAVE_GC_MOVE_DISAPPEARING_LINK]: Adjust
to return the error code.
---
 libguile/weak-table.c | 35 ++++++++++++++++++++++++++++++-----
 1 file changed, 30 insertions(+), 5 deletions(-)

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index 1aa2a0fcc..7d8633165 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -153,11 +153,16 @@ unregister_disappearing_links (scm_t_weak_entry *entry,
 }
 
 #ifndef HAVE_GC_MOVE_DISAPPEARING_LINK
-static void
+static int
 GC_move_disappearing_link (void **from, void **to)
 {
-  GC_unregister_disappearing_link (from);
-  SCM_I_REGISTER_DISAPPEARING_LINK (to, *to);
+  int err;
+
+  err = GC_unregister_disappearing_link (from);
+  if (err == GC_SUCCESS)
+    err = SCM_I_REGISTER_DISAPPEARING_LINK (to, *to);
+
+  return err;
 }
 #endif
 
@@ -165,13 +170,33 @@ static void
 move_disappearing_links (scm_t_weak_entry *from, scm_t_weak_entry *to,
                          SCM key, SCM value, scm_t_weak_table_kind kind)
 {
+  int err;
+
   if ((kind == SCM_WEAK_TABLE_KIND_KEY || kind == SCM_WEAK_TABLE_KIND_BOTH)
       && SCM_HEAP_OBJECT_P (key))
-    GC_move_disappearing_link ((void **) &from->key, (void **) &to->key);
+    {
+      err = GC_move_disappearing_link ((void **) &from->key,
+				       (void **) &to->key);
+      if (err == GC_NOT_FOUND)
+	/* Link disappeared.  */
+	register_disappearing_links (to, key, value,
+				     SCM_WEAK_TABLE_KIND_KEY);
+      else
+	assert (err == GC_SUCCESS);
+    }
 
   if ((kind == SCM_WEAK_TABLE_KIND_VALUE || kind == SCM_WEAK_TABLE_KIND_BOTH)
       && SCM_HEAP_OBJECT_P (value))
-    GC_move_disappearing_link ((void **) &from->value, (void **) &to->value);
+    {
+      err = GC_move_disappearing_link ((void **) &from->value,
+				       (void **) &to->value);
+      if (err == GC_NOT_FOUND)
+	/* Link disappeared.  */
+	register_disappearing_links (to, key, value,
+				     SCM_WEAK_TABLE_KIND_VALUE);
+      else
+	assert (err == GC_SUCCESS);
+    }
 }
 
 static void
-- 
2.14.2

Message #40 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: wingo <at> igalia.com
Cc: 28590 <at> debbugs.gnu.org
Subject: Re: bug#28590: [PATCH 0/7] Attempt to reduce memory growth
Date: Wed, 04 Oct 2017 15:09:17 +0200

[Message part 1 (text/plain, inline)]

Ludovic Courtès <ludo <at> gnu.org> skribis:

> I’ll try to combine that with incremental marking of the weak table, but
> I’m not very hopeful.

Here’s an attempt to mark tables incrementally.

Unfortunately it misses references sometimes (e.g., values of a weak-key
table do not get marked even though they should.)

I’m unsure whether incremental marking is actually doable: the mark
procedure only knows its own part of the mark state, not the global mark
state.  For instance, it cannot distinguish between different mark
phases.  I tried to fix that by memorizing the ‘GC_mark_no’ value we
were in when we left the mark procedure, but that didn’t help.

Ideas?

Ludo’.

[Message part 2 (text/x-patch, inline)]

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index 1a99a130f..cec9ee8ae 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 2011, 2012, 2013, 2014 Free Software Foundation, Inc.
+/* Copyright (C) 2011, 2012, 2013, 2014, 2017 Free Software Foundation, Inc.
  * 
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public License
@@ -94,6 +94,15 @@ typedef struct {
   scm_t_bits value;
 } scm_t_weak_entry;
 
+#define WEAK_MAGIC  0x9876123450UL
+
+struct weak_mark_state
+{
+  unsigned long magic;		   /* distinguished magic number */
+  unsigned long index;		   /* index where to resume marking */
+  unsigned long count;		   /* number of entries in the array */
+  scm_t_weak_entry *entries;	   /* pointer to the array of entries */
+};
 
 struct weak_entry_data {
   scm_t_weak_entry *in;
@@ -252,6 +261,7 @@ typedef struct {
   unsigned long upper;		/* when to grow */
   int size_index;		/* index into hashtable_size */
   int min_size_index;		/* minimum size_index */
+  struct weak_mark_state *mark_state;
 } scm_t_weak_table;
 
 
@@ -288,7 +298,11 @@ rob_from_rich (scm_t_weak_table *table, unsigned long k)
 
   /* If we are to free up slot K in the table, we need room to do so.  */
   assert (table->n_items < size);
-  
+
+  /* To be on the safe side, have the next mark phase start from the
+     beginning.  */
+  table->mark_state->index = 0;
+
   empty = k;
   do 
     empty = (empty + 1) % size;
@@ -318,6 +332,10 @@ give_to_poor (scm_t_weak_table *table, unsigned long k)
   /* Slot K was just freed up; possibly shuffle others down.  */
   unsigned long size = table->size;
 
+  /* To be on the safe side, have the next mark phase start from the
+     beginning.  */
+  table->mark_state->index = 0;
+
   while (1)
     {
       unsigned long next = (k + 1) % size;
@@ -354,49 +372,96 @@ give_to_poor (scm_t_weak_table *table, unsigned long k)
 static int weak_key_gc_kind;
 static int weak_value_gc_kind;
 
+extern GC_word GC_mark_no;
+
 static struct GC_ms_entry *
 mark_weak_key_table (GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
                      struct GC_ms_entry *mark_stack_limit, GC_word env)
 {
-  scm_t_weak_entry *entries = (scm_t_weak_entry*) addr;
-  unsigned long k, size = GC_size (addr) / sizeof (scm_t_weak_entry);
-
-  for (k = 0; k < size; k++)
+  struct weak_mark_state *state = (struct weak_mark_state *) addr;
+  scm_t_weak_entry *entries = state->entries;
+  unsigned long k, size = state->count;
+  unsigned long credit = GC_PROC_BYTES / sizeof (GC_word);
+
+  if (state->magic != WEAK_MAGIC)
+    /* STATE might point to a freed element.  */
+    return mark_stack_ptr;
+
+  for (k = state->index;
+       credit > 0 && k < size;
+       k++)
     if (entries[k].hash && entries[k].key)
       {
         SCM value = SCM_PACK (entries[k].value);
-        mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) SCM2PTR (value),
+        mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word *) SCM2PTR (value),
                                            mark_stack_ptr, mark_stack_limit,
                                            NULL);
+	credit--;
       }
 
+  if (k == size)
+    /* We marked ENTRIES till the end.  */
+    state->index = 0;
+  else
+    {
+      /* Save the current index and push ADDR back on the mark stack so
+	 we can resume later.  */
+      state->index = k;
+      mark_stack_ptr = GC_MARK_AND_PUSH (addr,
+					 mark_stack_ptr, mark_stack_limit,
+					 NULL);
+    }
+
   return mark_stack_ptr;
 }
 
 static struct GC_ms_entry *
 mark_weak_value_table (GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
-                       struct GC_ms_entry *mark_stack_limit, GC_word env)
+		       struct GC_ms_entry *mark_stack_limit, GC_word env)
 {
-  scm_t_weak_entry *entries = (scm_t_weak_entry*) addr;
-  unsigned long k, size = GC_size (addr) / sizeof (scm_t_weak_entry);
-
-  for (k = 0; k < size; k++)
+  struct weak_mark_state *state = (struct weak_mark_state *) addr;
+  scm_t_weak_entry *entries = state->entries;
+  unsigned long k, size = state->count;
+  unsigned long credit = GC_PROC_BYTES / sizeof (GC_word);
+
+  if (state->magic != WEAK_MAGIC)
+    /* STATE might point to a freed element.  */
+    return mark_stack_ptr;
+
+  for (k = state->index;
+       credit > 0 && k < size;
+       k++)
     if (entries[k].hash && entries[k].value)
       {
         SCM key = SCM_PACK (entries[k].key);
-        mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) SCM2PTR (key),
+        mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word *) SCM2PTR (key),
                                            mark_stack_ptr, mark_stack_limit,
                                            NULL);
+	credit--;
       }
 
+  if (k == size)
+    /* We marked ENTRIES till the end.  */
+    state->index = 0;
+  else
+    {
+      /* Save the current index and push ADDR back on the mark stack so
+	 we can resume later.  */
+      state->index = k;
+      mark_stack_ptr = GC_MARK_AND_PUSH (addr,
+					 mark_stack_ptr, mark_stack_limit,
+					 NULL);
+    }
+
   return mark_stack_ptr;
 }
 
-static scm_t_weak_entry *
+
+static struct weak_mark_state *
 allocate_entries (unsigned long size, scm_t_weak_table_kind kind)
 {
-  scm_t_weak_entry *ret;
-  size_t bytes = size * sizeof (*ret);
+  struct weak_mark_state *ret;
+  size_t bytes = size * sizeof (scm_t_weak_entry) + sizeof *ret;
 
   switch (kind)
     {
@@ -414,6 +479,9 @@ allocate_entries (unsigned long size, scm_t_weak_table_kind kind)
     }
 
   memset (ret, 0, bytes);
+  ret->magic = WEAK_MAGIC;
+  ret->count = size;
+  ret->entries = (scm_t_weak_entry *) ((char *) ret + sizeof (*ret));
 
   return ret;
 }
@@ -533,6 +601,7 @@ update_entry_count (scm_t_weak_table *table)
 static void
 resize_table (scm_t_weak_table *table)
 {
+  struct weak_mark_state *mark_state, *old_state;
   scm_t_weak_entry *old_entries, *new_entries;
   int new_size_index;
   unsigned long old_size, new_size, old_k;
@@ -554,11 +623,13 @@ resize_table (scm_t_weak_table *table)
     }
   while (!is_acceptable_size_index (table, new_size_index));
 
-  new_entries = allocate_entries (new_size, table->kind);
+  mark_state = allocate_entries (new_size, table->kind);
+  new_entries = mark_state->entries;
 
   old_entries = table->entries;
   old_size = table->size;
-  
+
+  table->mark_state = mark_state;
   table->size_index = new_size_index;
   table->size = new_size;
   if (new_size_index <= table->min_size_index)
@@ -618,6 +689,8 @@ resize_table (scm_t_weak_table *table)
                                    SCM_PACK (copy.key), SCM_PACK (copy.value),
                                    table->kind);
     }
+
+  old_state->magic = 0;
 }
 
 /* Run after GC via do_vacuum_weak_table, this function runs over the
@@ -807,6 +880,9 @@ weak_table_remove_x (scm_t_weak_table *table, unsigned long hash,
   hash = (hash << 1) | 0x1;
   k = hash_to_index (hash, size);
 
+  /* To be on the safe side, mark the whole array of entries again.  */
+  table->mark_state->index = 0;
+
   for (distance = 0; distance < size; distance++, k = (k + 1) % size)
     {
       unsigned long other_hash;
@@ -869,7 +945,8 @@ make_weak_table (unsigned long k, scm_t_weak_table_kind kind)
   n = hashtable_size[i];
 
   table = scm_gc_malloc (sizeof (*table), "weak-table");
-  table->entries = allocate_entries (n, kind);
+  table->mark_state = allocate_entries (n, kind);
+  table->entries = table->mark_state->entries;
   table->kind = kind;
   table->n_items = 0;
   table->size = n;

Message #43 received at 28590 <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: wingo <at> igalia.com
Cc: 28590 <at> debbugs.gnu.org
Subject: Re: bug#28590: [PATCH 0/7] Attempt to reduce memory growth
Date: Thu, 05 Oct 2017 16:09:04 +0200

ludo <at> gnu.org (Ludovic Courtès) skribis:

> Here’s an attempt to mark tables incrementally.
>
> Unfortunately it misses references sometimes (e.g., values of a weak-key
> table do not get marked even though they should.)

I’ve thrown a message in a bottle, with a reproducer in C:

  https://github.com/ivmai/bdwgc/issues/183

Ludo’.

Message #48 received at 28590-done <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: 28590-done <at> debbugs.gnu.org
Subject: Re: bug#28590: Weak tables in 2.2.2 grow indefinitely
Date: Tue, 07 Nov 2017 11:58:58 +0100

ludo <at> gnu.org (Ludovic Courtès) skribis:

> Consider this program:
>
> (use-modules (ice-9 format))
>
> (define loops 3000000)
>
> (define table
>   (make-weak-key-hash-table))
>
> (let loop ((i loops))
>   (unless #f ;(zero? i)
>     (when (zero? (modulo i 100000))
>       (format #t "heap-size: ~,2h MiB  table: ~s~%"
>               (/ (assoc-ref (gc-stats) 'heap-size) (expt 2. 20))
>               table))
>
>     (hashq-set! table (cons 1 2) #t)
>     (loop (1- i))))
>
> On 2.0.14, the heap size stays at around 24 MiB, and the table size is
> stable at 224,717 buckets (?).
>
> On 2.2.2, the heap grows indefinitely (though logarithmically).  It’s
> not deterministic though: sometimes the heap size stabilizes in the
> 140–300 MiB range, and sometimes it keeps growing endlessly even though
> the table size reaches a maxium at 7,190,537 entries.

This is fixed with Andy’s rewrite of weak tables to bucket-and-chains as
in 2.0:

  https://git.savannah.gnu.org/cgit/guile.git/commit/?h=stable-2.2&id=a053c0510c4a644f9453166b7b385cf30f6d3a21
  https://git.savannah.gnu.org/cgit/guile.git/commit/?h=stable-2.2&id=d01addeb1feba830ddd703e27f89576864a063ff
  https://git.savannah.gnu.org/cgit/guile.git/commit/?h=stable-2.2&id=dc8dda77e0c937abae42a76ea88c6e7995adbd9a
  https://lists.gnu.org/archive/html/guile-devel/2017-10/msg00051.html

\o/

Ludo’.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.