bug#28590: Weak tables in 2.2.2 grow indefinitely

bug#28590: Weak tables in 2.2.2 grow indefinitely

[Ludovic Courtès]

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’.

bug#28590: Weak tables in 2.2.2 grow indefinitely

[Ludovic Courtès]

ludo@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’.

bug#28590: Weak tables in 2.2.2 grow indefinitely

[Ludovic Courtès]

ludo@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’.

bug#28590: [PATCH 0/7] Attempt to reduce memory growth

[Ludovic Courtès]

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

bug#28590: [PATCH 1/7] weak-table: Fix unbounded growth of the disappearing link table.

[Ludovic Courtès]

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

bug#28590: [PATCH 2/7] weak-table: Stress the GC a little less when resizing.

[Ludovic Courtès]

* 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

bug#28590: [PATCH 3/7] weak-table: Make sure 'move_disappearing_links' actually moves links.

[Ludovic Courtès]

* 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

bug#28590: [PATCH 4/7] weak-table: Always unregister previous links when inserting an entry.

[Ludovic Courtès]

* 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

bug#28590: [PATCH 5/7] weak-table: 'move_weak_entry' reports disappeared links.

[Ludovic Courtès]

* 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

bug#28590: [PATCH 6/7] weak-table: 'rob_from_rich' accounts for disappeared entries.

[Ludovic Courtès]

* 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

bug#28590: [PATCH 7/7] weak-table: Resize less frequently.

[Ludovic Courtès]

* 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

bug#28590: [PATCH 0/7] Attempt to reduce memory growth

[Ludovic Courtès]

[-- Attachment #1: Type: text/plain, Size: 708 bytes --]

Ludovic Courtès <ludo@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’.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: text/x-patch, Size: 7594 bytes --]

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;

bug#28590: [PATCH 0/7] Attempt to reduce memory growth

[Ludovic Courtès]

ludo@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’.

bug#28590: Weak tables in 2.2.2 grow indefinitely

[Ludovic Courtès]

ludo@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’.