Re: Weak tables harmful to GC?

[Andy Wingo]

On Tue 31 Oct 2017 00:13, address@hidden (Ludovic Courtès) writes:

> I built libguile with the patch (I haven’t yet taken the time to rebuild
> all of Guile).  It works, but unfortunately it still shows quick growth
> of the heap on this example (<https://bugs.gnu.org/28590>):

Fixed in attached patches (on top of the other one).  This was a race
between the periodic vacuum process, which should run after GC via a
finalizer, and the mutator.  If the mutator had the weak table lock, the
vacuum would never be run.  Of course in the test below, the mutator
usually has the table lock, so we ended up often skipping the vacuum,
which causes the table size to grow, which causes the active heap size
to grow, which causes the bytes-allocated-before-GC to increase, and
which ultimately is a vicious circle.

In my tests this patch fixes the issue, though the level at which the
heap stabilizes can vary slightly as there's a bit of nondeterministic
concurrency as the mutator and the vacuum process still race a bit.
Right now for me it stabilizes at about 6.2M of heap.

>>    weak_key_gc_kind =
>>      GC_new_kind (GC_new_free_list (),
>> -             GC_MAKE_PROC (GC_new_proc (mark_weak_key_table), 0),
>> +             GC_MAKE_PROC (GC_new_proc (mark_weak_key_entry), 0),
>>               0, 0);
>
> I think we should avoid custom mark procedures and use a bitmap here, as
> recommended in the libgc headers (like ‘wcar_pair_descr’ in weaks.c in
> 2.0.)

Good idea; fixed.

Andy

>From 098c4171ef53791d97b5c675218f302efc7bcf26 Mon Sep 17 00:00:00 2001
From: Andy Wingo <address@hidden>
Date: Tue, 31 Oct 2017 09:10:55 +0100
Subject: [PATCH 2/3] Refactor weak table to use bitmaps for weak entries

---
 libguile/weak-table.c | 107 ++++++++++++--------------------------------------
 1 file changed, 25 insertions(+), 82 deletions(-)

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index ff8a01fb0..fab98149f 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -25,7 +25,7 @@
 #include <assert.h>
 
 #include "libguile/bdw-gc.h"
-#include <gc/gc_mark.h>
+#include <gc/gc_typed.h>
 
 #include "libguile/_scm.h"
 #include "libguile/hash.h"
@@ -152,70 +152,10 @@ typedef struct {
 
 
 
-/* The GC "kinds" for singly-weak tables.  */
-static int weak_key_gc_kind;
-static int weak_value_gc_kind;
-static int doubly_weak_gc_kind;
-
-static struct GC_ms_entry *
-mark_weak_key_entry (GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
-                     struct GC_ms_entry *mark_stack_limit, GC_word env)
-{
-  scm_t_weak_entry *entry = (scm_t_weak_entry*) addr;
-
-  if (entry->next)
-    mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) entry->next,
-                                       mark_stack_ptr, mark_stack_limit,
-                                       NULL);
-
-  if (entry->hash && entry->key)
-    {
-      SCM value = SCM_PACK (entry->value);
-      if (SCM_HEAP_OBJECT_P (value))
-        mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) SCM2PTR (value),
-                                           mark_stack_ptr, mark_stack_limit,
-                                           NULL);
-    }
-
-  return mark_stack_ptr;
-}
-
-static struct GC_ms_entry *
-mark_weak_value_entry (GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
-                       struct GC_ms_entry *mark_stack_limit, GC_word env)
-{
-  scm_t_weak_entry *entry = (scm_t_weak_entry*) addr;
-
-  if (entry->next)
-    mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) entry->next,
-                                       mark_stack_ptr, mark_stack_limit,
-                                       NULL);
-
-  if (entry->hash && entry->value)
-    {
-      SCM key = SCM_PACK (entry->key);
-      if (SCM_HEAP_OBJECT_P (key))
-        mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) SCM2PTR (key),
-                                           mark_stack_ptr, mark_stack_limit,
-                                           NULL);
-    }
-
-  return mark_stack_ptr;
-}
-
-static struct GC_ms_entry *
-mark_doubly_weak_entry (GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
-                        struct GC_ms_entry *mark_stack_limit, GC_word env)
-{
-  scm_t_weak_entry *entry = (scm_t_weak_entry*) addr;
-
-  if (entry->next)
-    mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) entry->next,
-                                       mark_stack_ptr, mark_stack_limit,
-                                       NULL);
-
-  return mark_stack_ptr;
-}
+/* GC descriptors for the various kinds of scm_t_weak_entry.  */
+static GC_descr weak_key_descr;
+static GC_descr weak_value_descr;
+static GC_descr doubly_weak_descr;
 
 static scm_t_weak_entry *
 allocate_entry (scm_t_weak_table_kind kind)
@@ -225,20 +165,18 @@ allocate_entry (scm_t_weak_table_kind kind)
   switch (kind)
     {
     case SCM_WEAK_TABLE_KIND_KEY:
-      ret = GC_generic_malloc (sizeof (*ret), weak_key_gc_kind);
+      ret = GC_malloc_explicitly_typed (sizeof (*ret), weak_key_descr);
       break;
     case SCM_WEAK_TABLE_KIND_VALUE:
-      ret = GC_generic_malloc (sizeof (*ret), weak_value_gc_kind);
+      ret = GC_malloc_explicitly_typed (sizeof (*ret), weak_value_descr);
       break;
     case SCM_WEAK_TABLE_KIND_BOTH:
-      ret = GC_generic_malloc (sizeof (*ret), doubly_weak_gc_kind);
+      ret = GC_malloc_explicitly_typed (sizeof (*ret), doubly_weak_descr);
       break;
     default:
       abort ();
     }
 
-  memset (ret, 0, sizeof (*ret));
-
   return ret;
 }
 
@@ -852,18 +790,23 @@ SCM_DEFINE (scm_doubly_weak_hash_table_p, 
"doubly-weak-hash-table?", 1, 0, 0,
 void
 scm_weak_table_prehistory (void)
 {
-  weak_key_gc_kind =
-    GC_new_kind (GC_new_free_list (),
-                GC_MAKE_PROC (GC_new_proc (mark_weak_key_entry), 0),
-                0, 0);
-  weak_value_gc_kind =
-    GC_new_kind (GC_new_free_list (),
-                GC_MAKE_PROC (GC_new_proc (mark_weak_value_entry), 0),
-                0, 0);
-  doubly_weak_gc_kind =
-    GC_new_kind (GC_new_free_list (),
-                GC_MAKE_PROC (GC_new_proc (mark_doubly_weak_entry), 0),
-                0, 0);
+  GC_word weak_key_bitmap[GC_BITMAP_SIZE (scm_t_weak_entry)] = { 0 };
+  GC_word weak_value_bitmap[GC_BITMAP_SIZE (scm_t_weak_entry)] = { 0 };
+  GC_word doubly_weak_bitmap[GC_BITMAP_SIZE (scm_t_weak_entry)] = { 0 };
+
+  GC_set_bit (weak_key_bitmap, GC_WORD_OFFSET (scm_t_weak_entry, next));
+  GC_set_bit (weak_value_bitmap, GC_WORD_OFFSET (scm_t_weak_entry, next));
+  GC_set_bit (doubly_weak_bitmap, GC_WORD_OFFSET (scm_t_weak_entry, next));
+
+  GC_set_bit (weak_key_bitmap, GC_WORD_OFFSET (scm_t_weak_entry, value));
+  GC_set_bit (weak_value_bitmap, GC_WORD_OFFSET (scm_t_weak_entry, key));
+
+  weak_key_descr = GC_make_descriptor (weak_key_bitmap,
+                                       GC_WORD_LEN (scm_t_weak_entry));
+  weak_value_descr = GC_make_descriptor (weak_value_bitmap,
+                                         GC_WORD_LEN (scm_t_weak_entry));
+  doubly_weak_descr = GC_make_descriptor (doubly_weak_bitmap,
+                                          GC_WORD_LEN (scm_t_weak_entry));
 }
 
 void
-- 
2.14.1

>From 3304f9dc2cf106426570acc8437b4e39fe5edf91 Mon Sep 17 00:00:00 2001
From: Andy Wingo <address@hidden>
Date: Tue, 31 Oct 2017 08:43:09 +0100
Subject: [PATCH 3/3] More robust vacuuming of in-use weak tables

* libguile/weak-table.c (scm_t_weak_table); Add last_gc_no member.
* libguile/weak-table.c (vacuum_weak_table): Only vacuum if we haven't
  done so since the last GC.
  (scm_c_weak_table_ref, scm_c_weak_table_put_x, scm_c_weak_table_remove_x)
  (scm_c_weak_table_fold): Vacuum the weak table if needed.
  (scm_weak_table_clear_x): Update last_gc_no flag, as no more vacuuming
  will be needed.
---
 libguile/weak-table.c | 25 ++++++++++++++++++++++---
 1 file changed, 22 insertions(+), 3 deletions(-)

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index fab98149f..461d4a47c 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -31,7 +31,6 @@
 #include "libguile/hash.h"
 #include "libguile/eval.h"
 #include "libguile/ports.h"
-
 #include "libguile/validate.h"
 #include "libguile/weak-list.h"
 #include "libguile/weak-table.h"
@@ -141,6 +140,7 @@ typedef struct {
   unsigned long upper;         /* when to grow */
   int size_index;              /* index into hashtable_size */
   int min_size_index;          /* minimum size_index */
+  GC_word last_gc_no;
 } scm_t_weak_table;
 
 
@@ -275,8 +275,14 @@ resize_table (scm_t_weak_table *table)
 static void
 vacuum_weak_table (scm_t_weak_table *table)
 {
+  GC_word gc_no = GC_get_gc_no ();
   unsigned long k;
 
+  if (gc_no == table->last_gc_no)
+    return;
+
+  table->last_gc_no = gc_no;
+
   for (k = 0; k < table->n_buckets; k++)
     {
       scm_t_weak_entry **loc = table->buckets + k;
@@ -427,6 +433,7 @@ make_weak_table (unsigned long k, scm_t_weak_table_kind 
kind)
   table->upper = 9 * n / 10;
   table->size_index = i;
   table->min_size_index = i;
+  table->last_gc_no = GC_get_gc_no ();
   scm_i_pthread_mutex_init (&table->lock, NULL);
 
   return scm_cell (scm_tc7_weak_table, (scm_t_bits)table);
@@ -456,8 +463,10 @@ do_vacuum_weak_table (SCM table)
      custom predicate, or via finalizers run explicitly by (gc) or in an
      async (for non-threaded Guile).  We add a restriction that
      prohibits the first case, by convention.  But since we can't
-     prohibit the second case, here we trylock instead of lock.  Not so
-     nice.  */
+     prohibit the second case, here we trylock instead of lock.  In any
+     case, if the mutex is held by another thread, then the table is in
+     active use, so the next user of the table will handle the vacuum
+     for us.  */
   if (scm_i_pthread_mutex_trylock (&t->lock) == 0)
     {
       vacuum_weak_table (t);
@@ -513,6 +522,8 @@ scm_c_weak_table_ref (SCM table, unsigned long raw_hash,
 
   scm_i_pthread_mutex_lock (&t->lock);
 
+  vacuum_weak_table (t);
+
   ret = weak_table_ref (t, raw_hash, pred, closure, dflt);
 
   scm_i_pthread_mutex_unlock (&t->lock);
@@ -535,6 +546,8 @@ scm_c_weak_table_put_x (SCM table, unsigned long raw_hash,
 
   scm_i_pthread_mutex_lock (&t->lock);
 
+  vacuum_weak_table (t);
+
   weak_table_put_x (t, raw_hash, pred, closure, key, value);
 
   scm_i_pthread_mutex_unlock (&t->lock);
@@ -555,6 +568,8 @@ scm_c_weak_table_remove_x (SCM table, unsigned long 
raw_hash,
 
   scm_i_pthread_mutex_lock (&t->lock);
 
+  vacuum_weak_table (t);
+
   weak_table_remove_x (t, raw_hash, pred, closure);
 
   scm_i_pthread_mutex_unlock (&t->lock);
@@ -604,6 +619,8 @@ scm_weak_table_clear_x (SCM table)
 
   scm_i_pthread_mutex_lock (&t->lock);
 
+  t->last_gc_no = GC_get_gc_no ();
+
   for (k = 0; k < t->n_buckets; k++)
     {
       for (entry = t->buckets[k]; entry; entry = entry->next)
@@ -628,6 +645,8 @@ scm_c_weak_table_fold (scm_t_table_fold_fn proc, void 
*closure,
 
   scm_i_pthread_mutex_lock (&t->lock);
 
+  vacuum_weak_table (t);
+
   for (k = 0; k < t->n_buckets; k++)
     {
       scm_t_weak_entry *entry;
-- 
2.14.1