libctf, hash: save per-item space when no key/item freeing function

The libctf dynhash hashtab abstraction supports per-hashtab arbitrary
key/item freeing functions -- but it also has a constant slot type that
holds both key and value requested by the user, so it needs to use its
own freeing function to free that -- and it has nowhere to store the
freeing functions the caller requested.

So it copies them into every hash item, bloating every slot, even though
all items in a given hash table must have the same key and value freeing
functions.

So point back to the owner using a back-pointer, but don't even spend
space in the item or the hashtab allocating those freeing functions
unless necessary: if none are needed, we can simply arrange to not pass
in ctf_dynhash_item_free as a del_f to hashtab_create_alloc, and none of
those fields will ever be accessed.

The only downside is that this makes the code sensitive to the order of
fields in the ctf_helem_t and ctf_hashtab_t: but the deduplicator
allocates so many hash tables that doing this alone cuts memory usage
during deduplication by about 10%.  (libiberty hashtab itself has a lot
of per-hashtab bloat: in the future we might trim that down, or make a
trimmer version.)

libctf/
	* ctf-hash.c (ctf_helem_t) <key_free>: Remove.
	<value_free>: Likewise.
	<owner>: New.
	(ctf_dynhash_item_free): Indirect through the owner.
	(ctf_dynhash_create): Only pass in ctf_dynhash_item_free and
	allocate space for the key_free and value_free fields fields
	if necessary.
	(ctf_hashtab_insert): Likewise.  Fix OOM errno value.
	(ctf_dynhash_insert): Only access ctf_hashtab's key_free and
	value_free if they will exist.  Set the slot's owner, but only
	if it exists.
	(ctf_dynhash_remove): Adjust.

2 files changed, 62 insertions, 21 deletions

diff --git a/libctf/ChangeLog b/libctf/ChangeLog
index 9e8129a..27987f2 100644
--- a/libctf/ChangeLog
+++ b/libctf/ChangeLog
@@ -1,5 +1,20 @@
 2020-07-22  Nick Alcock  <nick.alcock@oracle.com>
 
+	* ctf-hash.c (ctf_helem_t) <key_free>: Remove.
+	<value_free>: Likewise.
+	<owner>: New.
+	(ctf_dynhash_item_free): Indirect through the owner.
+	(ctf_dynhash_create): Only pass in ctf_dynhash_item_free and
+	allocate space for the key_free and value_free fields fields
+	if necessary.
+	(ctf_hashtab_insert): Likewise.  Fix OOM errno value.
+	(ctf_dynhash_insert): Only access ctf_hashtab's key_free and
+	value_free if they will exist.  Set the slot's owner, but only
+	if it exists.
+	(ctf_dynhash_remove): Adjust.
+
+2020-07-22  Nick Alcock  <nick.alcock@oracle.com>
+
 	* ctf-hash.c (ctf_hashtab_insert): Free the key passed in if
 	there is a key-freeing function and the key already exists.
 
diff --git a/libctf/ctf-hash.c b/libctf/ctf-hash.c
index 1c37d75..caefd99 100644
--- a/libctf/ctf-hash.c
+++ b/libctf/ctf-hash.c
@@ -31,14 +31,19 @@
    not support removal.  These can be implemented by the same underlying hashmap
    if you wish.  */
 
+/* The helem is used for general key/value mappings in both the ctf_hash and
+   ctf_dynhash: the owner may not have space allocated for it, and will be
+   garbage (not NULL!) in that case.  */
+
 typedef struct ctf_helem
 {
   void *key;			 /* Either a pointer, or a coerced ctf_id_t.  */
   void *value;			 /* The value (possibly a coerced int).  */
-  ctf_hash_free_fun key_free;
-  ctf_hash_free_fun value_free;
+  ctf_dynhash_t *owner;          /* The hash that owns us.  */
 } ctf_helem_t;
 
+/* Equally, the key_free and value_free may not exist.  */
+
 struct ctf_dynhash
 {
   struct htab *htab;
@@ -106,17 +111,17 @@ ctf_hash_eq_type_mapping_key (const void *a, const void *b)
 
 /* The dynhash, used for hashes whose size is not known at creation time. */
 
-/* Free a single ctf_helem.  */
+/* Free a single ctf_helem with arbitrary key/value functions.  */
 
 static void
 ctf_dynhash_item_free (void *item)
 {
   ctf_helem_t *helem = item;
 
-  if (helem->key_free && helem->key)
-    helem->key_free (helem->key);
-  if (helem->value_free && helem->value)
-    helem->value_free (helem->value);
+  if (helem->owner->key_free && helem->key)
+    helem->owner->key_free (helem->key);
+  if (helem->owner->value_free && helem->value)
+    helem->owner->value_free (helem->value);
   free (helem);
 }
 
@@ -125,21 +130,31 @@ ctf_dynhash_create (ctf_hash_fun hash_fun, ctf_hash_eq_fun eq_fun,
                     ctf_hash_free_fun key_free, ctf_hash_free_fun value_free)
 {
   ctf_dynhash_t *dynhash;
+  htab_del del = ctf_dynhash_item_free;
 
-  dynhash = malloc (sizeof (ctf_dynhash_t));
+  if (key_free || value_free)
+    dynhash = malloc (sizeof (ctf_dynhash_t));
+  else
+    dynhash = malloc (offsetof (ctf_dynhash_t, key_free));
   if (!dynhash)
     return NULL;
 
-  /* 7 is arbitrary and untested for now..  */
+  if (key_free == NULL && value_free == NULL)
+    del = free;
+
+  /* 7 is arbitrary and untested for now.  */
   if ((dynhash->htab = htab_create_alloc (7, (htab_hash) hash_fun, eq_fun,
-                                          ctf_dynhash_item_free, xcalloc, free)) == NULL)
+					  del, xcalloc, free)) == NULL)
     {
       free (dynhash);
       return NULL;
     }
 
-  dynhash->key_free = key_free;
-  dynhash->value_free = value_free;
+  if (key_free || value_free)
+    {
+      dynhash->key_free = key_free;
+      dynhash->value_free = value_free;
+    }
 
   return dynhash;
 }
@@ -162,13 +177,18 @@ ctf_hashtab_insert (struct htab *htab, void *key, void *value,
 
   if (!slot)
     {
-      errno = -ENOMEM;
+      errno = ENOMEM;
       return NULL;
     }
 
   if (!*slot)
     {
-      *slot = malloc (sizeof (ctf_helem_t));
+      /* Only spend space on the owner if we're going to use it: if there is a
+	 key or value freeing function.  */
+      if (key_free || value_free)
+	*slot = malloc (sizeof (ctf_helem_t));
+      else
+	*slot = malloc (offsetof (ctf_helem_t, owner));
       if (!*slot)
 	return NULL;
       (*slot)->key = key;
@@ -188,19 +208,25 @@ int
 ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value)
 {
   ctf_helem_t *slot;
+  ctf_hash_free_fun key_free = NULL, value_free = NULL;
 
+  if (hp->htab->del_f == ctf_dynhash_item_free)
+    {
+      key_free = hp->key_free;
+      value_free = hp->value_free;
+    }
   slot = ctf_hashtab_insert (hp->htab, key, value,
-			     hp->key_free, hp->value_free);
+			     key_free, value_free);
 
   if (!slot)
     return errno;
 
-  /* We need to keep the key_free and value_free around in each item because the
-     del function has no visibility into the hash as a whole, only into the
-     individual items.  */
+  /* Keep track of the owner, so that the del function can get at the key_free
+     and value_free functions.  Only do this if one of those functions is set:
+     if not, the owner is not even present in the helem.  */
 
-  slot->key_free = hp->key_free;
-  slot->value_free = hp->value_free;
+  if (key_free || value_free)
+    slot->owner = hp;
 
   return 0;
 }
@@ -208,7 +234,7 @@ ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value)
 void
 ctf_dynhash_remove (ctf_dynhash_t *hp, const void *key)
 {
-  ctf_helem_t hep = { (void *) key, NULL, NULL, NULL };
+  ctf_helem_t hep = { (void *) key, NULL, NULL };
   htab_remove_elt (hp->htab, &hep);
 }