add patch series

6 files changed, 747 insertions, 0 deletions

diff --git a/debian/patches/ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch b/debian/patches/ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch
new file mode 100644
index 00000000..bc330973
--- /dev/null
+++ b/debian/patches/ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch
@@ -0,0 +1,109 @@
+From 5aa7e263521b934c2e23e7fb795fd9163999219a Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Sat, 21 Nov 2015 16:12:53 +0100
+Subject: [PATCH hurd 1/5] libihash: fix ill-devised locp lookup interface
+
+* libihash/ihash.c (hurd_ihash_locp_find): Return both the item and the slot.
+* libihash/ihash.h (hurd_ihash_locp_find): Adjust prototype.
+(hurd_ihash_locp_value): Remove function.
+---
+ libihash/ihash.c | 19 +++++++++----------
+ libihash/ihash.h | 31 ++++++-------------------------
+ 2 files changed, 15 insertions(+), 35 deletions(-)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index 87d7abf..8b1ad1f 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -370,13 +370,9 @@ hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key)
+     }
+ }
+ 
+-/* Find the item in the hash table HT with key KEY.  If it is found,
+-   return the location of its slot in the hash table.  If it is not
+-   found, this function may still return a location.
+-
+-   This location pointer can always be safely accessed using
+-   hurd_ihash_locp_value.  If the lookup is successful,
+-   hurd_ihash_locp_value will return the value related to KEY.
++/* Find and return the item in the hash table HT with key KEY, or NULL
++   if it doesn't exist.  If it is not found, this function may still
++   return a location in SLOT.
+ 
+    If the lookup is successful, the returned location can be used with
+    hurd_ihash_locp_add to update the item, and with
+@@ -387,8 +383,10 @@ hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key)
+ 
+    Note that returned location is only valid until the next insertion
+    or deletion.  */
+-hurd_ihash_locp_t
+-hurd_ihash_locp_find (hurd_ihash_t ht, hurd_ihash_key_t key)
++hurd_ihash_value_t
++hurd_ihash_locp_find (hurd_ihash_t ht,
++		      hurd_ihash_key_t key,
++		      hurd_ihash_locp_t *slot)
+ {
+   int idx;
+ 
+@@ -396,7 +394,8 @@ hurd_ihash_locp_find (hurd_ihash_t ht, hurd_ihash_key_t key)
+     return NULL;
+ 
+   idx = find_index (ht, key);
+-  return &ht->items[idx].value;
++  *slot = &ht->items[idx].value;
++  return index_valid (ht, idx, key) ? ht->items[idx].value : NULL;
+ }
+ 
+ 
+diff --git a/libihash/ihash.h b/libihash/ihash.h
+index 1dbc348..fdfc367 100644
+--- a/libihash/ihash.h
++++ b/libihash/ihash.h
+@@ -218,13 +218,9 @@ error_t hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp,
+    if it doesn't exist.  */
+ hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key);
+ 
+-/* Find the item in the hash table HT with key KEY.  If it is found,
+-   return the location of its slot in the hash table.  If it is not
+-   found, this function may still return a location.
+-
+-   This location pointer can always be safely accessed using
+-   hurd_ihash_locp_value.  If the lookup is successful,
+-   hurd_ihash_locp_value will return the value related to KEY.
++/* Find and return the item in the hash table HT with key KEY, or NULL
++   if it doesn't exist.  If it is not found, this function may still
++   return a location in SLOT.
+ 
+    If the lookup is successful, the returned location can be used with
+    hurd_ihash_locp_add to update the item, and with
+@@ -235,24 +231,9 @@ hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key);
+ 
+    Note that returned location is only valid until the next insertion
+    or deletion.  */
+-hurd_ihash_locp_t hurd_ihash_locp_find (hurd_ihash_t ht,
+-                                        hurd_ihash_key_t key);
+-
+-/* Given an hash table bucket location LOCP, return the value stored
+-   there, or NULL if it is empty or LOCP is NULL.  */
+-static inline void *
+-hurd_ihash_locp_value (hurd_ihash_locp_t locp)
+-{
+-  struct _hurd_ihash_item *item = (struct _hurd_ihash_item *) locp;
+-
+-  if (item == NULL)
+-    return NULL;
+-
+-  if (hurd_ihash_value_valid (item->value))
+-    return item->value;
+-
+-  return NULL;
+-}
++hurd_ihash_value_t hurd_ihash_locp_find (hurd_ihash_t ht,
++					 hurd_ihash_key_t key,
++					 hurd_ihash_locp_t *slot);
+ 
+ /* Iterate over all elements in the hash table.  You use this macro
+    with a block, for example like this:
+-- 
+2.1.4
+
diff --git a/debian/patches/ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch b/debian/patches/ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch
new file mode 100644
index 00000000..4bbac576
--- /dev/null
+++ b/debian/patches/ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch
@@ -0,0 +1,26 @@
+From 143ea78cf3e14b9f9f7609e9fbb0a30635a92788 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Sun, 22 Nov 2015 18:13:01 +0100
+Subject: [PATCH hurd 2/5] libihash: fix fast insertion corner case
+
+* libihash/ihash.c (hurd_ihash_locp_add): Fix insertion if the key
+doesn't match.
+---
+ libihash/ihash.c | 1 +
+ 1 file changed, 1 insertion(+)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index 8b1ad1f..598d341 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -267,6 +267,7 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp,
+   if (ht->size == 0
+       || item == NULL
+       || item->value == _HURD_IHASH_DELETED
++      || ! compare (ht, item->key, key)
+       || hurd_ihash_get_load (ht) > ht->max_load)
+     return hurd_ihash_add (ht, key, value);
+ 
+-- 
+2.1.4
+
diff --git a/debian/patches/ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch b/debian/patches/ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch
new file mode 100644
index 00000000..fbadb805
--- /dev/null
+++ b/debian/patches/ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch
@@ -0,0 +1,237 @@
+From 99833334867f052e6ad98ec4b6a72bbabf4362c4 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Sat, 21 Nov 2015 16:27:40 +0100
+Subject: [PATCH hurd 3/5] libihash: generalize the interface to support
+ non-integer keys
+
+* libihash/ihash.c (hash, compare): New functions that are used
+throughout libihash to hash and compare keys.
+(hurd_ihash_set_gki): New function.
+* libihash/ihash.h (hurd_ihash_fct_hash_t): New type for hash functions.
+(hurd_ihash_fct_cmp_t): New type for comparison functions.
+(struct hurd_ihash): New fields for hash and comparison functions.
+(HURD_IHASH_INITIALIZER_GKI): New static initializer.
+(hurd_ihash_set_gki): New prototype.
+---
+ libihash/ihash.c | 59 +++++++++++++++++++++++++++++++++++++++++++++-----------
+ libihash/ihash.h | 36 +++++++++++++++++++++++++++++++++-
+ 2 files changed, 83 insertions(+), 12 deletions(-)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index 598d341..164b84d 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -1,5 +1,5 @@
+ /* ihash.c - Integer-keyed hash table functions.
+-   Copyright (C) 1993-1997, 2001, 2003, 2004, 2006
++   Copyright (C) 1993-1997, 2001, 2003, 2004, 2006, 2014, 2015
+      Free Software Foundation, Inc.
+    Written by Michael I. Bushnell.
+    Revised by Miles Bader <miles@gnu.org>.
+@@ -32,6 +32,22 @@
+ 
+ #include "ihash.h"
+ 
++/* This function is used to hash the key.  */
++static inline hurd_ihash_key_t
++hash (hurd_ihash_t ht, hurd_ihash_key_t k)
++{
++  return ht->fct_hash ? ht->fct_hash ((void *) k) : k;
++}
++
++/* This function is used to compare the key.  Returns true if A is
++   equal to B.  */
++static inline int
++compare (hurd_ihash_t ht, hurd_ihash_key_t a, hurd_ihash_key_t b)
++{
++  return
++    ht->fct_cmp ? (a && ht->fct_cmp ((void *) a, (void *) b)) : a == b;
++}
++
+ /* Return 1 if the slot with the index IDX in the hash table HT is
+    empty, and 0 otherwise.  */
+ static inline int
+@@ -46,7 +62,7 @@ index_empty (hurd_ihash_t ht, unsigned int idx)
+ static inline int
+ index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key)
+ {
+-  return !index_empty (ht, idx) && ht->items[idx].key == key;
++  return !index_empty (ht, idx) && compare (ht, ht->items[idx].key, key);
+ }
+ 
+ 
+@@ -60,9 +76,10 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
+   unsigned int up_idx;
+   unsigned int mask = ht->size - 1;
+ 
+-  idx = key & mask;
++  idx = hash (ht, key) & mask;
+ 
+-  if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
++  if (ht->items[idx].value == _HURD_IHASH_EMPTY
++      || compare (ht, ht->items[idx].key, key))
+     return idx;
+ 
+   up_idx = idx;
+@@ -71,7 +88,7 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
+     {
+       up_idx = (up_idx + 1) & mask;
+       if (ht->items[up_idx].value == _HURD_IHASH_EMPTY
+-	  || ht->items[up_idx].key == key)
++	  || compare (ht, ht->items[up_idx].key, key))
+ 	return up_idx;
+     }
+   while (up_idx != idx);
+@@ -88,9 +105,11 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
+ static inline void
+ locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp)
+ {
++  struct _hurd_ihash_item *item = locp;
+   if (ht->cleanup)
+-    (*ht->cleanup) (*locp, ht->cleanup_data);
+-  *locp = _HURD_IHASH_DELETED;
++    (*ht->cleanup) (item->value, ht->cleanup_data);
++  item->value = _HURD_IHASH_DELETED;
++  item->key = 0;
+   ht->nr_items--;
+ }
+ 
+@@ -106,6 +125,8 @@ hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs)
+   ht->locp_offset = locp_offs;
+   ht->max_load = HURD_IHASH_MAX_LOAD_DEFAULT;
+   ht->cleanup = 0;
++  ht->fct_hash = NULL;
++  ht->fct_cmp = NULL;
+ }
+ 
+ 
+@@ -166,6 +187,21 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
+ }
+ 
+ 
++/* Use the generalized key interface.  Must be called before any item
++   is inserted into the table.  */
++void
++hurd_ihash_set_gki (hurd_ihash_t ht,
++		    hurd_ihash_fct_hash_t fct_hash,
++		    hurd_ihash_fct_cmp_t fct_cmp)
++{
++  assert (ht->size == 0 || !"called after insertion");
++  assert (fct_hash);
++  assert (fct_cmp);
++  ht->fct_hash = fct_hash;
++  ht->fct_cmp = fct_cmp;
++}
++
++
+ /* Set the maximum load factor in binary percent to MAX_LOAD, which
+    should be between 64 and 128.  The default is
+    HURD_IHASH_MAX_LOAD_DEFAULT.  New elements are only added to the
+@@ -199,10 +235,11 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
+   unsigned int first_free;
+   unsigned int mask = ht->size - 1;
+ 
+-  idx = key & mask;
++  idx = hash (ht, key) & mask;
+   first_free = idx;
+ 
+-  if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key)
++  if (ht->items[idx].value != _HURD_IHASH_EMPTY
++      && ! compare (ht, ht->items[idx].key, key))
+     {
+       unsigned int up_idx = idx;
+ 
+@@ -210,7 +247,7 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
+ 	{
+         up_idx = (up_idx + 1) & mask;
+ 	  if (ht->items[up_idx].value == _HURD_IHASH_EMPTY
+-	      || ht->items[up_idx].key == key)
++	      || compare (ht, ht->items[up_idx].key, key))
+ 	    {
+ 	      idx = up_idx;
+ 	      break;
+@@ -278,7 +315,7 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp,
+     }
+   else
+     {
+-      assert (item->key == key);
++      assert (compare (ht, item->key, key));
+       if (ht->cleanup)
+         (*ht->cleanup) (locp, ht->cleanup_data);
+     }
+diff --git a/libihash/ihash.h b/libihash/ihash.h
+index fdfc367..d332479 100644
+--- a/libihash/ihash.h
++++ b/libihash/ihash.h
+@@ -1,5 +1,5 @@
+ /* ihash.h - Integer keyed hash table interface.
+-   Copyright (C) 1995, 2003, 2004 Free Software Foundation, Inc.
++   Copyright (C) 1995, 2003, 2004, 2014, 2015 Free Software Foundation, Inc.
+    Written by Miles Bader <miles@gnu.org>.
+    Revised by Marcus Brinkmann <marcus@gnu.org>.
+ 
+@@ -57,6 +57,20 @@ typedef uintptr_t hurd_ihash_key_t;
+ typedef hurd_ihash_value_t *hurd_ihash_locp_t;
+ 
+ 
++/* We support non-integer keys using the generalized key interface.
++
++   To use it, supply a pair of functions matching the following
++   specification, and use pointers to the key instead of the key
++   itself in all calls to libihash.  */
++
++/* The type of a function computing a hash for the given key.  */
++typedef hurd_ihash_key_t (*hurd_ihash_fct_hash_t) (void *);
++
++/* The type of a function comparing two given keys.  Return true if
++   both keys are equal.  */
++typedef int (*hurd_ihash_fct_cmp_t) (void *, void *);
++
++
+ /* The type of the cleanup function, which is called for every value
+    removed from the hash table.  */
+ typedef void (*hurd_ihash_cleanup_t) (hurd_ihash_value_t value, void *arg);
+@@ -95,6 +109,10 @@ struct hurd_ihash
+      second argument.  This does not happen if CLEANUP is NULL.  */
+   hurd_ihash_cleanup_t cleanup;
+   void *cleanup_data;
++
++  /* User-supplied functions for the generalized key interface.  */
++  hurd_ihash_fct_hash_t fct_hash;
++  hurd_ihash_fct_cmp_t fct_cmp;
+ };
+ typedef struct hurd_ihash *hurd_ihash_t;
+ 
+@@ -118,6 +136,16 @@ typedef struct hurd_ihash *hurd_ihash_t;
+     .max_load = HURD_IHASH_MAX_LOAD_DEFAULT,				\
+     .locp_offset = (locp_offs)}
+ 
++#define HURD_IHASH_INITIALIZER_GKI(locp_offs, f_clean, f_clean_data,	\
++				   f_hash, f_compare)			\
++  { .nr_items = 0, .size = 0,						\
++    .cleanup = (f_clean),						\
++    .cleanup_data = (f_clean_data),					\
++    .max_load = HURD_IHASH_MAX_LOAD_DEFAULT,				\
++    .locp_offset = (locp_offs),						\
++    .fct_hash = (f_hash),						\
++    .fct_cmp = (f_compare)}						\
++
+ /* Initialize the hash table at address HT.  If LOCP_OFFSET is not
+    HURD_IHASH_NO_LOCP, then this is an offset (in bytes) from the
+    address of a hash value where a location pointer can be found.  The
+@@ -152,6 +180,12 @@ void hurd_ihash_free (hurd_ihash_t ht);
+ void hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
+ 			     void *cleanup_data);
+ 
++/* Use the generalized key interface.  Must be called before any item
++   is inserted into the table.	*/
++void hurd_ihash_set_gki (hurd_ihash_t ht,
++			 hurd_ihash_fct_hash_t fct_hash,
++			 hurd_ihash_fct_cmp_t fct_cmp);
++
+ /* Set the maximum load factor in binary percent to MAX_LOAD, which
+    should be between 64 and 128.  The default is
+    HURD_IHASH_MAX_LOAD_DEFAULT.  New elements are only added to the
+-- 
+2.1.4
+
diff --git a/debian/patches/ihash-as-cache0004-libihash-fix-item-insertion.patch b/debian/patches/ihash-as-cache0004-libihash-fix-item-insertion.patch
new file mode 100644
index 00000000..93893aca
--- /dev/null
+++ b/debian/patches/ihash-as-cache0004-libihash-fix-item-insertion.patch
@@ -0,0 +1,109 @@
+From 76a5839125371ffc6960000558d027112ff3b53b Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Sun, 22 Nov 2015 21:04:51 +0100
+Subject: [PATCH hurd 4/5] libihash: fix item insertion
+
+* libihash/ihash.c (find_index): Keep track and return the index where
+we could insert the item.
+(add_one): Use 'find_index'.
+---
+ libihash/ihash.c | 54 ++++++++++++++++++------------------------------------
+ 1 file changed, 18 insertions(+), 36 deletions(-)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index 164b84d..292743b 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -74,6 +74,8 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
+ {
+   unsigned int idx;
+   unsigned int up_idx;
++  unsigned int first_deleted = 0;
++  int first_deleted_set = 0;
+   unsigned int mask = ht->size - 1;
+ 
+   idx = hash (ht, key) & mask;
+@@ -87,15 +89,21 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
+   do
+     {
+       up_idx = (up_idx + 1) & mask;
+-      if (ht->items[up_idx].value == _HURD_IHASH_EMPTY
+-	  || compare (ht, ht->items[up_idx].key, key))
++      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))
+ 	return up_idx;
++      if (! first_deleted_set
++          && ht->items[up_idx].value == _HURD_IHASH_DELETED)
++        first_deleted = up_idx, first_deleted_set = 1;
+     }
+   while (up_idx != idx);
+ 
+-  /* If we end up here, the item could not be found.  Return any
+-     invalid index.  */
+-  return idx;
++  /* If we end up here, the item could not be found.  Return the index
++     of the first deleted item, as this is the position where we can
++     insert an item with the given key once we established that it is
++     not in the table.  */
++  return first_deleted;
+ }
+ 
+ 
+@@ -232,48 +240,22 @@ static inline int
+ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
+ {
+   unsigned int idx;
+-  unsigned int first_free;
+-  unsigned int mask = ht->size - 1;
+-
+-  idx = hash (ht, key) & mask;
+-  first_free = idx;
+-
+-  if (ht->items[idx].value != _HURD_IHASH_EMPTY
+-      && ! compare (ht, ht->items[idx].key, key))
+-    {
+-      unsigned int up_idx = idx;
+ 
+-      do
+-	{
+-        up_idx = (up_idx + 1) & mask;
+-	  if (ht->items[up_idx].value == _HURD_IHASH_EMPTY
+-	      || compare (ht, ht->items[up_idx].key, key))
+-	    {
+-	      idx = up_idx;
+-	      break;
+-	    }
+-	}
+-      while (up_idx != idx);
+-    }
++  idx = find_index (ht, key);
+ 
+   /* Remove the old entry for this key if necessary.  */
+   if (index_valid (ht, idx, key))
+     locp_remove (ht, &ht->items[idx].value);
+ 
+-  /* If we have not found an empty slot, maybe the last one we
+-     looked at was empty (or just got deleted).  */
+-  if (!index_empty (ht, first_free))
+-    first_free = idx;
+- 
+-  if (index_empty (ht, first_free))
++  if (index_empty (ht, idx))
+     {
+       ht->nr_items++;
+-      ht->items[first_free].value = value;
+-      ht->items[first_free].key = key;
++      ht->items[idx].value = value;
++      ht->items[idx].key = key;
+ 
+       if (ht->locp_offset != HURD_IHASH_NO_LOCP)
+ 	*((hurd_ihash_locp_t *) (((char *) value) + ht->locp_offset))
+-	  = &ht->items[first_free].value;
++	  = &ht->items[idx].value;
+ 
+       return 1;
+     }
+-- 
+2.1.4
+
diff --git a/debian/patches/ihash-as-cache0005-libihash-provide-a-general-purpose-hash-algorithm.patch b/debian/patches/ihash-as-cache0005-libihash-provide-a-general-purpose-hash-algorithm.patch
new file mode 100644
index 00000000..f23ef287
--- /dev/null
+++ b/debian/patches/ihash-as-cache0005-libihash-provide-a-general-purpose-hash-algorithm.patch
@@ -0,0 +1,261 @@
+From bc6d77c63547ce4da7e5d49f1a86a84aad42bf69 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Fri, 27 Nov 2015 03:24:24 +0100
+Subject: [PATCH hurd 5/5] libihash: provide a general purpose hash algorithm
+
+* libdiskfs/name-cache.c: Move the Murmur3 algorithm...
+* libihash/murmur3.c: ... here, and properly attribute the code.
+* libihash/ihash.h (hurd_ihash_hash32): New prototype.
+* libihash/Makefile (SRCS): Add new file.
+---
+ libdiskfs/name-cache.c | 89 ++---------------------------------------------
+ libihash/Makefile      |  2 +-
+ libihash/ihash.h       |  5 +++
+ libihash/murmur3.c     | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++
+ 4 files changed, 102 insertions(+), 87 deletions(-)
+ create mode 100644 libihash/murmur3.c
+
+diff --git a/libdiskfs/name-cache.c b/libdiskfs/name-cache.c
+index e9fe27e..53935ab 100644
+--- a/libdiskfs/name-cache.c
++++ b/libdiskfs/name-cache.c
+@@ -21,6 +21,7 @@
+ 
+ #include "priv.h"
+ #include <assert.h>
++#include <hurd/ihash.h>
+ #include <string.h>
+ 
+ /* The name cache is implemented using a hash table.
+@@ -118,90 +119,6 @@ valid_entry (struct cache_bucket *b, int i)
+   return b->name[i] != 0;
+ }
+ 
+-/* This is the Murmur3 hash algorithm.  */
+-
+-#define FORCE_INLINE inline __attribute__((always_inline))
+-
+-inline uint32_t rotl32 ( uint32_t x, int8_t r )
+-{
+-  return (x << r) | (x >> (32 - r));
+-}
+-
+-#define ROTL32(x,y)     rotl32(x,y)
+-
+-/* Block read - if your platform needs to do endian-swapping or can
+-   only handle aligned reads, do the conversion here.  */
+-
+-FORCE_INLINE uint32_t getblock32 ( const uint32_t * p, int i )
+-{
+-  return p[i];
+-}
+-
+-/* Finalization mix - force all bits of a hash block to avalanche.  */
+-
+-FORCE_INLINE uint32_t fmix32 ( uint32_t h )
+-{
+-  h ^= h >> 16;
+-  h *= 0x85ebca6b;
+-  h ^= h >> 13;
+-  h *= 0xc2b2ae35;
+-  h ^= h >> 16;
+-
+-  return h;
+-}
+-
+-/* The Murmur3 hash function.  */
+-void MurmurHash3_x86_32 ( const void * key, int len,
+-                          uint32_t seed, void * out )
+-{
+-  const uint8_t * data = (const uint8_t*)key;
+-  const int nblocks = len / 4;
+-
+-  uint32_t h1 = seed;
+-
+-  const uint32_t c1 = 0xcc9e2d51;
+-  const uint32_t c2 = 0x1b873593;
+-
+-  /* body */
+-
+-  const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
+-
+-  for(int i = -nblocks; i; i++)
+-  {
+-    uint32_t k1 = getblock32(blocks,i);
+-
+-    k1 *= c1;
+-    k1 = ROTL32(k1,15);
+-    k1 *= c2;
+-
+-    h1 ^= k1;
+-    h1 = ROTL32(h1,13);
+-    h1 = h1*5+0xe6546b64;
+-  }
+-
+-  /* tail */
+-
+-  const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
+-
+-  uint32_t k1 = 0;
+-
+-  switch(len & 3)
+-  {
+-  case 3: k1 ^= tail[2] << 16;
+-  case 2: k1 ^= tail[1] << 8;
+-  case 1: k1 ^= tail[0];
+-          k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
+-  };
+-
+-  /* finalization */
+-
+-  h1 ^= len;
+-
+-  h1 = fmix32(h1);
+-
+-  *(uint32_t*)out = h1;
+-}
+-
+ /* If there is no best candidate to replace, pick any.  We approximate
+    any by picking the slot depicted by REPLACE, and increment REPLACE
+    then.  */
+@@ -259,8 +176,8 @@ static inline unsigned long
+ hash (ino64_t dir_cache_id, const char *name)
+ {
+   unsigned long h;
+-  MurmurHash3_x86_32 (&dir_cache_id, sizeof dir_cache_id, 0, &h);
+-  MurmurHash3_x86_32 (name, strlen (name), h, &h);
++  h = hurd_ihash_hash32 (&dir_cache_id, sizeof dir_cache_id, 0);
++  h = hurd_ihash_hash32 (name, strlen (name), h);
+   return h;
+ }
+ 
+diff --git a/libihash/Makefile b/libihash/Makefile
+index 09bb136..3377ef4 100644
+--- a/libihash/Makefile
++++ b/libihash/Makefile
+@@ -20,7 +20,7 @@ dir := libihash
+ makemode := library
+ 
+ libname := libihash
+-SRCS = ihash.c
++SRCS = ihash.c murmur3.c
+ installhdrs = ihash.h
+ 
+ OBJS = $(SRCS:.c=.o)
+diff --git a/libihash/ihash.h b/libihash/ihash.h
+index d332479..9333fc6 100644
+--- a/libihash/ihash.h
++++ b/libihash/ihash.h
+@@ -349,5 +349,10 @@ int hurd_ihash_remove (hurd_ihash_t ht, hurd_ihash_key_t key);
+    was provided to hurd_ihash_add().  This call is faster than
+    hurd_ihash_remove().  */
+ void hurd_ihash_locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp);
++
++/* We provide a general purpose hash function.  This function can be
++   used with the generalized key interface to use arbitrary data as
++   keys using this library.  */
++uint32_t hurd_ihash_hash32 (const char *buf, size_t len, uint32_t seed);
+ 
+ #endif	/* _HURD_IHASH_H */
+diff --git a/libihash/murmur3.c b/libihash/murmur3.c
+new file mode 100644
+index 0000000..0b06037
+--- /dev/null
++++ b/libihash/murmur3.c
+@@ -0,0 +1,93 @@
++/* This is the Murmur3 hash algorithm.
++ *
++ * MurmurHash3 was written by Austin Appleby, and is placed in the public
++ * domain.  The author hereby disclaims copyright to this source code.
++ */
++
++#include <stdint.h>
++#include <stdio.h>
++
++#define FORCE_INLINE static inline __attribute__((always_inline))
++
++static inline uint32_t rotl32 ( uint32_t x, int8_t r )
++{
++  return (x << r) | (x >> (32 - r));
++}
++
++#define ROTL32(x,y)     rotl32(x,y)
++
++/* Block read - if your platform needs to do endian-swapping or can
++   only handle aligned reads, do the conversion here.  */
++
++FORCE_INLINE uint32_t getblock32 ( const uint32_t * p, int i )
++{
++  return p[i];
++}
++
++/* Finalization mix - force all bits of a hash block to avalanche.  */
++
++FORCE_INLINE uint32_t fmix32 ( uint32_t h )
++{
++  h ^= h >> 16;
++  h *= 0x85ebca6b;
++  h ^= h >> 13;
++  h *= 0xc2b2ae35;
++  h ^= h >> 16;
++
++  return h;
++}
++
++/* The Murmur3 hash function.  */
++static uint32_t
++MurmurHash3_x86_32 (const void *key, size_t len, uint32_t seed)
++{
++  const uint8_t * data = (const uint8_t*)key;
++  const int nblocks = (int) (len / 4);
++
++  uint32_t h1 = seed;
++
++  const uint32_t c1 = 0xcc9e2d51;
++  const uint32_t c2 = 0x1b873593;
++
++  /* body */
++
++  const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
++
++  for(int i = -nblocks; i; i++)
++  {
++    uint32_t k1 = getblock32(blocks,i);
++
++    k1 *= c1;
++    k1 = ROTL32(k1,15);
++    k1 *= c2;
++
++    h1 ^= k1;
++    h1 = ROTL32(h1,13);
++    h1 = h1*5+0xe6546b64;
++  }
++
++  /* tail */
++
++  const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
++
++  uint32_t k1 = 0;
++
++  switch(len & 3)
++  {
++  case 3: k1 ^= tail[2] << 16;
++  case 2: k1 ^= tail[1] << 8;
++  case 1: k1 ^= tail[0];
++          k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
++  };
++
++  /* finalization */
++
++  h1 ^= len;
++
++  h1 = fmix32(h1);
++
++  return h1;
++}
++
++uint32_t hurd_ihash_hash32 (const char *, size_t, uint32_t)
++  __attribute__ ((weak, alias ("MurmurHash3_x86_32")));
+-- 
+2.1.4
+
diff --git a/debian/patches/series b/debian/patches/series
index c5e922b4..822f0384 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -63,3 +63,8 @@ translators-list0002-libfshelp-acquire-references-to-control-ports.patch
 translators-list0003-libihash-add-general-purpose-hash-functions.patch
 translators-list0004-libfshelp-improve-translator-list.patch
 translators-list0005-add-iteration.patch
+ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch
+ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch
+ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch
+ihash-as-cache0004-libihash-fix-item-insertion.patch
+ihash-as-cache0005-libihash-provide-a-general-purpose-hash-algorithm.patch