[glib] Allow hash table destroy notifiers to remove other entries

[Ryan Lortie <desrt src gnome org>]

commit 18745ff674896c931379d097b18d74678044668e
Author: Benjamin Berg <benjamin sipsolutions net>
Date:   Fri Oct 17 14:16:22 2014 +0200

    Allow hash table destroy notifiers to remove other entries
    
    With this patch it is fine to call g_hash_table_lookup and
    g_hash_table_remove from destroy notification functions. Before
    this could lead to an infinitie loop if g_hash_table_remove_all
    was used.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=695082

 glib/ghash.c      |   91 ++++++++++++++++++++++++++++++++++++++++++----------
 glib/tests/hash.c |   55 ++++++++++++++++++++++++++++++--
 2 files changed, 125 insertions(+), 21 deletions(-)
---
diff --git a/glib/ghash.c b/glib/ghash.c
index f597958..7058808 100644
--- a/glib/ghash.c
+++ b/glib/ghash.c
@@ -365,6 +365,13 @@ g_hash_table_lookup_node (GHashTable    *hash_table,
   gboolean have_tombstone = FALSE;
   guint step = 0;
 
+  /* If this happens, then the application is probably doing too much work
+   * from a destroy notifier. The alternative would be to crash any second
+   * (as keys, etc. will be NULL).
+   * Applications need to either use g_hash_table_destroy, or ensure the hash
+   * table is empty prior to removing the last reference using g_object_unref. */
+  g_assert (hash_table->ref_count > 0);
+
   hash_value = hash_table->hash_func (key);
   if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
     hash_value = 2;
@@ -465,11 +472,20 @@ g_hash_table_remove_node (GHashTable   *hash_table,
  */
 static void
 g_hash_table_remove_all_nodes (GHashTable *hash_table,
-                               gboolean    notify)
+                               gboolean    notify,
+                               gboolean    destruction)
 {
   int i;
   gpointer key;
   gpointer value;
+  gint old_size;
+  gpointer *old_keys;
+  gpointer *old_values;
+  guint    *old_hashes;
+
+  /* If the hash table is already empty, there is nothing to be done. */
+  if (hash_table->nnodes == 0)
+    return;
 
   hash_table->nnodes = 0;
   hash_table->noccupied = 0;
@@ -478,23 +494,52 @@ g_hash_table_remove_all_nodes (GHashTable *hash_table,
       (hash_table->key_destroy_func == NULL &&
        hash_table->value_destroy_func == NULL))
     {
-      memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
-      memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
-      memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
+      if (!destruction)
+        {
+          memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
+          memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
+          memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
+        }
 
       return;
     }
 
-  for (i = 0; i < hash_table->size; i++)
+  /* Keep the old storage space around to iterate over it. */
+  old_size = hash_table->size;
+  old_keys   = hash_table->keys;
+  old_values = hash_table->values;
+  old_hashes = hash_table->hashes;
+
+  /* Now create a new storage space; If the table is destroyed we can use the
+   * shortcut of not creating a new storage. This saves the allocation at the
+   * cost of not allowing any recursive access.
+   * However, the application doesn't own any reference anymore, so access
+   * is not allowed. If accesses are done, then either an assert or crash
+   * *will* happen. */
+  g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
+  if (!destruction)
     {
-      if (HASH_IS_REAL (hash_table->hashes[i]))
+      hash_table->keys   = g_new0 (gpointer, hash_table->size);
+      hash_table->values = hash_table->keys;
+      hash_table->hashes = g_new0 (guint, hash_table->size);
+    }
+  else
+    {
+      hash_table->keys   = NULL;
+      hash_table->values = NULL;
+      hash_table->hashes = NULL;
+    }
+
+  for (i = 0; i < old_size; i++)
+    {
+      if (HASH_IS_REAL (old_hashes[i]))
         {
-          key = hash_table->keys[i];
-          value = hash_table->values[i];
+          key = old_keys[i];
+          value = old_values[i];
 
-          hash_table->hashes[i] = UNUSED_HASH_VALUE;
-          hash_table->keys[i] = NULL;
-          hash_table->values[i] = NULL;
+          old_hashes[i] = UNUSED_HASH_VALUE;
+          old_keys[i] = NULL;
+          old_values[i] = NULL;
 
           if (hash_table->key_destroy_func != NULL)
             hash_table->key_destroy_func (key);
@@ -502,11 +547,14 @@ g_hash_table_remove_all_nodes (GHashTable *hash_table,
           if (hash_table->value_destroy_func != NULL)
             hash_table->value_destroy_func (value);
         }
-      else if (HASH_IS_TOMBSTONE (hash_table->hashes[i]))
-        {
-          hash_table->hashes[i] = UNUSED_HASH_VALUE;
-        }
     }
+
+  /* Destroy old storage space. */
+  if (old_keys != old_values)
+    g_free (old_values);
+
+  g_free (old_keys);
+  g_free (old_hashes);
 }
 
 /*
@@ -643,6 +691,13 @@ g_hash_table_new (GHashFunc  hash_func,
  * allocated for the key and value that get called when removing the
  * entry from the #GHashTable.
  *
+ * Since version 2.42 it is permissible for destroy notify functions to
+ * recursively remove further items from the hash table. This is only
+ * permissible if the application still holds a reference to the hash table.
+ * This means that you may need to ensure that the hash table is empty by
+ * calling g_hash_table_remove_all before releasing the last reference using
+ * g_object_unref.
+ *
  * Returns: a new #GHashTable
  */
 GHashTable *
@@ -1039,7 +1094,7 @@ g_hash_table_unref (GHashTable *hash_table)
 
   if (g_atomic_int_dec_and_test (&hash_table->ref_count))
     {
-      g_hash_table_remove_all_nodes (hash_table, TRUE);
+      g_hash_table_remove_all_nodes (hash_table, TRUE, TRUE);
       if (hash_table->keys != hash_table->values)
         g_free (hash_table->values);
       g_free (hash_table->keys);
@@ -1368,7 +1423,7 @@ g_hash_table_remove_all (GHashTable *hash_table)
     hash_table->version++;
 #endif
 
-  g_hash_table_remove_all_nodes (hash_table, TRUE);
+  g_hash_table_remove_all_nodes (hash_table, TRUE, FALSE);
   g_hash_table_maybe_resize (hash_table);
 }
 
@@ -1391,7 +1446,7 @@ g_hash_table_steal_all (GHashTable *hash_table)
     hash_table->version++;
 #endif
 
-  g_hash_table_remove_all_nodes (hash_table, FALSE);
+  g_hash_table_remove_all_nodes (hash_table, FALSE, FALSE);
   g_hash_table_maybe_resize (hash_table);
 }
 
diff --git a/glib/tests/hash.c b/glib/tests/hash.c
index 332f821..c1c8539 100644
--- a/glib/tests/hash.c
+++ b/glib/tests/hash.c
@@ -793,9 +793,10 @@ test_remove_all (void)
   gboolean res;
 
   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
-  g_hash_table_insert (h, "abc", "ABC");
-  g_hash_table_insert (h, "cde", "CDE");
-  g_hash_table_insert (h, "xyz", "XYZ");
+
+  g_hash_table_insert (h, "abc", "cde");
+  g_hash_table_insert (h, "cde", "xyz");
+  g_hash_table_insert (h, "xyz", "abc");
 
   destroy_counter = 0;
   destroy_key_counter = 0;
@@ -825,6 +826,52 @@ test_remove_all (void)
   g_hash_table_unref (h);
 }
 
+GHashTable *recursive_destruction_table = NULL;
+static void
+recursive_value_destroy (gpointer value)
+{
+  destroy_counter++;
+
+  if (recursive_destruction_table)
+    g_hash_table_remove (recursive_destruction_table, value);
+}
+
+static void
+test_recursive_remove_all_subprocess (void)
+{
+  GHashTable *h;
+
+  h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, recursive_value_destroy);
+  recursive_destruction_table = h;
+
+  /* Add more items compared to test_remove_all, as it would not fail otherwise. */
+  g_hash_table_insert (h, "abc", "cde");
+  g_hash_table_insert (h, "cde", "fgh");
+  g_hash_table_insert (h, "fgh", "ijk");
+  g_hash_table_insert (h, "ijk", "lmn");
+  g_hash_table_insert (h, "lmn", "opq");
+  g_hash_table_insert (h, "opq", "rst");
+  g_hash_table_insert (h, "rst", "uvw");
+  g_hash_table_insert (h, "uvw", "xyz");
+  g_hash_table_insert (h, "xyz", "abc");
+
+  destroy_counter = 0;
+  destroy_key_counter = 0;
+
+  g_hash_table_remove_all (h);
+  g_assert_cmpint (destroy_counter, ==, 9);
+  g_assert_cmpint (destroy_key_counter, ==, 9);
+
+  g_hash_table_unref (h);
+}
+
+static void
+test_recursive_remove_all (void)
+{
+  g_test_trap_subprocess ("/hash/recursive-remove-all/subprocess", 1000000, 0);
+  g_test_trap_assert_passed ();
+}
+
 typedef struct {
   gint ref_count;
   const gchar *key;
@@ -1459,6 +1506,8 @@ main (int argc, char *argv[])
   g_test_add_func ("/hash/set-ref", set_ref_hash_test);
   g_test_add_func ("/hash/ref", test_hash_ref);
   g_test_add_func ("/hash/remove-all", test_remove_all);
+  g_test_add_func ("/hash/recursive-remove-all", test_recursive_remove_all);
+  g_test_add_func ("/hash/recursive-remove-all/subprocess", test_recursive_remove_all_subprocess);
   g_test_add_func ("/hash/find", test_find);
   g_test_add_func ("/hash/foreach", test_foreach);
   g_test_add_func ("/hash/foreach-steal", test_foreach_steal);