add patch series

4 files changed, 188 insertions, 0 deletions

diff --git a/debian/patches/ihash0001-libihash-fix-index-computation.patch b/debian/patches/ihash0001-libihash-fix-index-computation.patch
new file mode 100644
index 00000000..3e6c99fc
--- /dev/null
+++ b/debian/patches/ihash0001-libihash-fix-index-computation.patch
@@ -0,0 +1,44 @@
+From 74d373342f799a45e9193c2f56189843b7b42c04 Mon Sep 17 00:00:00 2001
+From: Justus Winter <justus@gnupg.org>
+Date: Thu, 28 Apr 2016 23:59:26 +0200
+Subject: [PATCH hurd 1/3] libihash: fix index computation
+
+Previously, find_index would return a suboptimal slot if a tombstone
+was in the optimal slot.
+
+* libihash/ihash.c (find_index): Fix index computation.
+---
+ libihash/ihash.c | 7 +------
+ 1 file changed, 1 insertion(+), 6 deletions(-)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index 4bc54fd..01ba23b 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -81,15 +81,9 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
+ 
+   idx = hash (ht, key) & mask;
+ 
+-  if (ht->items[idx].value == _HURD_IHASH_EMPTY
+-      || compare (ht, ht->items[idx].key, key))
+-    return idx;
+-
+   up_idx = idx;
+-
+   do
+     {
+-      up_idx = (up_idx + 1) & mask;
+       if (ht->items[up_idx].value == _HURD_IHASH_EMPTY)
+         return first_deleted_set ? first_deleted : up_idx;
+       if (compare (ht, ht->items[up_idx].key, key))
+@@ -97,6 +91,7 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
+       if (! first_deleted_set
+           && ht->items[up_idx].value == _HURD_IHASH_DELETED)
+         first_deleted = up_idx, first_deleted_set = 1;
++      up_idx = (up_idx + 1) & mask;
+     }
+   while (up_idx != idx);
+ 
+-- 
+2.1.4
+
diff --git a/debian/patches/ihash0002-libihash-keep-track-of-free-slots.patch b/debian/patches/ihash0002-libihash-keep-track-of-free-slots.patch
new file mode 100644
index 00000000..052b4905
--- /dev/null
+++ b/debian/patches/ihash0002-libihash-keep-track-of-free-slots.patch
@@ -0,0 +1,89 @@
+From 39031d37fd82c119b4b16af256a8ceae5d8c6ea8 Mon Sep 17 00:00:00 2001
+From: Justus Winter <justus@gnupg.org>
+Date: Thu, 28 Apr 2016 20:11:27 +0200
+Subject: [PATCH hurd 2/3] libihash: keep track of free slots
+
+* libihash/ihash.c (hurd_ihash_init): Init new field 'nr_free'.
+(add_one): Decrement counter if a free slot is used.
+(hurd_ihash_locp_add): Likewise.
+(hurd_ihash_add): Reset counter on reallocation.
+* libihash/ihash.h (struct hurd_ihash): New field 'nr_free'.
+(hurd_ihash_get_effective_load): New function.
+---
+ libihash/ihash.c |  9 +++++++++
+ libihash/ihash.h | 11 +++++++++++
+ 2 files changed, 20 insertions(+)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index 01ba23b..800f492 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -131,6 +131,7 @@ hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs)
+   ht->cleanup = 0;
+   ht->fct_hash = NULL;
+   ht->fct_cmp = NULL;
++  ht->nr_free = 0;
+ }
+ 
+ 
+@@ -246,6 +247,11 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
+   if (index_empty (ht, idx))
+     {
+       ht->nr_items++;
++      if (ht->items[idx].value == _HURD_IHASH_EMPTY)
++        {
++          assert (ht->nr_free > 0);
++          ht->nr_free--;
++        }
+       ht->items[idx].value = value;
+       ht->items[idx].key = key;
+ 
+@@ -290,6 +296,8 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp,
+     {
+       item->key = key;
+       ht->nr_items += 1;
++      assert (ht->nr_free > 0);
++      ht->nr_free -= 1;
+     }
+   else
+     {
+@@ -335,6 +343,7 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
+       ht->size = HURD_IHASH_MIN_SIZE;
+   else
+       ht->size <<= 1;
++  ht->nr_free = ht->size;
+ 
+   /* calloc() will initialize all values to _HURD_IHASH_EMPTY implicitly.  */
+   ht->items = calloc (ht->size, sizeof (struct _hurd_ihash_item));
+diff --git a/libihash/ihash.h b/libihash/ihash.h
+index 356f647..80679f1 100644
+--- a/libihash/ihash.h
++++ b/libihash/ihash.h
+@@ -113,6 +113,9 @@ struct hurd_ihash
+   /* User-supplied functions for the generalized key interface.  */
+   hurd_ihash_fct_hash_t fct_hash;
+   hurd_ihash_fct_cmp_t fct_cmp;
++
++  /* Number of free slots.  */
++  size_t nr_free;
+ };
+ typedef struct hurd_ihash *hurd_ihash_t;
+ 
+@@ -225,6 +228,14 @@ hurd_ihash_get_load (hurd_ihash_t ht)
+   return d >= 0 ? ht->nr_items >> d : ht->nr_items << -d;
+ }
+ 
++/* Similar, but counts tombstones as well.  */
++static inline unsigned int
++hurd_ihash_get_effective_load (hurd_ihash_t ht)
++{
++  int d = __builtin_ctzl (ht->size) - 7;
++  return
++    d >= 0 ? (ht->size - ht->nr_free) >> d : (ht->size - ht->nr_free) << -d;
++}
+ 
+ /* Add ITEM to the hash table HT under the key KEY.  If there already
+    is an item under this key, call the cleanup function (if any) for
+-- 
+2.1.4
+
diff --git a/debian/patches/ihash0003-libihash-rehash-if-effective-load-exceeds-the-thresh.patch b/debian/patches/ihash0003-libihash-rehash-if-effective-load-exceeds-the-thresh.patch
new file mode 100644
index 00000000..245bc7ae
--- /dev/null
+++ b/debian/patches/ihash0003-libihash-rehash-if-effective-load-exceeds-the-thresh.patch
@@ -0,0 +1,52 @@
+From 04d9d15f531017be5a01b5d8e046d9426dc971a5 Mon Sep 17 00:00:00 2001
+From: Justus Winter <justus@gnupg.org>
+Date: Thu, 28 Apr 2016 21:12:58 +0200
+Subject: [PATCH hurd 3/3] libihash: rehash if effective load exceeds the
+ threshold
+
+* libihash/ihash.c (hurd_ihash_locp_add): Use the effective load.
+(hurd_ihash_add): Likewise.  Use the load to decide whether we want to
+enlarge the table, otherwise we merely rehash.
+---
+ libihash/ihash.c | 10 ++++++----
+ 1 file changed, 6 insertions(+), 4 deletions(-)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index 800f492..ae1cf12 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -289,7 +289,7 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp,
+       || item == NULL
+       || item->value == _HURD_IHASH_DELETED
+       || ! compare (ht, item->key, key)
+-      || hurd_ihash_get_load (ht) > ht->max_load)
++      || hurd_ihash_get_effective_load (ht) > ht->max_load)
+     return hurd_ihash_add (ht, key, value);
+ 
+   if (item->value == _HURD_IHASH_EMPTY)
+@@ -331,17 +331,19 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
+   if (ht->size)
+     {
+       /* Only fill the hash table up to its maximum load factor.  */
+-      if (hurd_ihash_get_load (ht) <= ht->max_load)
++      if (hurd_ihash_get_effective_load (ht) <= ht->max_load)
+       add_one:
+ 	if (add_one (ht, key, item))
+ 	  return 0;
+     }
+ 
+-  /* The hash table is too small, and we have to increase it.  */
++  /* If the load exceeds the configured maximal load, then the hash
++     table is too small, and we have to increase it.  Otherwise we
++     merely rehash the table to get rid of the tombstones.  */
+   ht->nr_items = 0;
+   if (ht->size == 0)
+       ht->size = HURD_IHASH_MIN_SIZE;
+-  else
++  else if (hurd_ihash_get_load (&old_ht) > ht->max_load)
+       ht->size <<= 1;
+   ht->nr_free = ht->size;
+ 
+-- 
+2.1.4
+
diff --git a/debian/patches/series b/debian/patches/series
index a1aad4fd..94bfe26d 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -45,3 +45,6 @@ crash0001-xxx-crash-logging-works.patch
 fixes0001-utils-settrans-implement-active-translator-stacking.patch
 fixes0002-Avoid-superfluous-locking-of-node.patch
 fixes0003-fstests-new-micro-benchmark.patch
+ihash0001-libihash-fix-index-computation.patch
+ihash0002-libihash-keep-track-of-free-slots.patch
+ihash0003-libihash-rehash-if-effective-load-exceeds-the-thresh.patch