add patch series

4 files changed, 307 insertions, 0 deletions

diff --git a/debian/patches/ihash-as-cache0001-libihash-add-hurd_ihash_value_valid.patch b/debian/patches/ihash-as-cache0001-libihash-add-hurd_ihash_value_valid.patch
new file mode 100644
index 00000000..f115220d
--- /dev/null
+++ b/debian/patches/ihash-as-cache0001-libihash-add-hurd_ihash_value_valid.patch
@@ -0,0 +1,47 @@
+From 6c948532d2799bcc172053cac504c4aa5f016bba Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Thu, 15 May 2014 17:55:45 +0200
+Subject: [PATCH hurd 1/3] libihash: add hurd_ihash_value_valid
+
+* libihash/ihash.h (hurd_ihash_value_valid): New function.
+* libihash/ihash.c (index_empty): Use hurd_ihash_value_valid.
+---
+ libihash/ihash.c | 3 +--
+ libihash/ihash.h | 7 +++++++
+ 2 files changed, 8 insertions(+), 2 deletions(-)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index fa29257..74e9edd 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -37,8 +37,7 @@
+ static inline int
+ index_empty (hurd_ihash_t ht, unsigned int idx)
+ {
+-  return ht->items[idx].value == _HURD_IHASH_EMPTY
+-    || ht->items[idx].value == _HURD_IHASH_DELETED;
++  return ! hurd_ihash_value_valid (ht->items[idx].value);
+ }
+ 
+ 
+diff --git a/libihash/ihash.h b/libihash/ihash.h
+index 849a55a..128027a 100644
+--- a/libihash/ihash.h
++++ b/libihash/ihash.h
+@@ -41,6 +41,13 @@ typedef void *hurd_ihash_value_t;
+ #define _HURD_IHASH_EMPTY	((hurd_ihash_value_t) 0)
+ #define _HURD_IHASH_DELETED	((hurd_ihash_value_t) -1)
+ 
++/* Test if VALUE is valid.  */
++static inline int
++hurd_ihash_value_valid (hurd_ihash_value_t value)
++{
++  return value != _HURD_IHASH_EMPTY && value != _HURD_IHASH_DELETED;
++}
++
+ /* The type of integer we want to use for the keys.  */
+ typedef uintptr_t hurd_ihash_key_t;
+ 
+-- 
+2.1.4
+
diff --git a/debian/patches/ihash-as-cache0002-libihash-optimize-lookup-or-insert-operations.patch b/debian/patches/ihash-as-cache0002-libihash-optimize-lookup-or-insert-operations.patch
new file mode 100644
index 00000000..2b5dd1f8
--- /dev/null
+++ b/debian/patches/ihash-as-cache0002-libihash-optimize-lookup-or-insert-operations.patch
@@ -0,0 +1,196 @@
+From c1d5c163a89f53a3c6e4e67f5f4119af96f7a470 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Wed, 14 May 2014 16:24:21 +0200
+Subject: [PATCH hurd 2/3] libihash: optimize lookup-or-insert operations
+
+If libihash is used to implement a cache, a insertion is always
+preceeded by a lookup.  hurd_ihash_add has to do the lookup again.
+
+Provide a new pair of functions, hurd_ihash_locp_add and
+hurd_ihash_locp_find, that can be used in combination to avoid the
+second lookup.
+
+* libihash/ihash.c (hurd_ihash_locp_add): New function using a
+location pointer...
+(hurd_ihash_locp_find): ... that has been returned by this function.
+* libihash/ihash.h (hurd_ihash_locp_add): New declaration.
+(hurd_ihash_locp_find): Likewise.
+(hurd_ihash_locp_value): New function.
+---
+ libihash/ihash.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
+ libihash/ihash.h | 52 +++++++++++++++++++++++++++++++++++++
+ 2 files changed, 129 insertions(+), 1 deletion(-)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index 74e9edd..a97de3e 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -244,7 +244,54 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
+   return 0;
+ }
+ 
+-  
++
++/* Add VALUE to the hash table HT under the key KEY at LOCP.  If there
++   already is an item under this key, call the cleanup function (if
++   any) for it before overriding the value.  This function is faster
++   than hurd_ihash_add.
++
++   If LOCP is NULL, fall back to hurd_ihash_add.  Otherwise, LOCP must
++   be valid and may either be obtained from hurd_ihash_locp_find, or
++   from an item that is currently in the hash table.  If an item is
++   replaced, KEY must match the key of the previous item.
++
++   If a memory allocation error occurs, ENOMEM is returned, otherwise
++   0.  */
++error_t
++hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp,
++                     hurd_ihash_key_t key, hurd_ihash_value_t value)
++{
++  struct _hurd_ihash_item *item = (struct _hurd_ihash_item *) locp;
++
++  /* In case of complications, fall back to hurd_ihash_add.  */
++  if (ht->size == 0
++      || item == NULL
++      || item->value == _HURD_IHASH_DELETED
++      || hurd_ihash_get_load (ht) > ht->max_load)
++    return hurd_ihash_add (ht, key, value);
++
++  if (item->value == _HURD_IHASH_EMPTY)
++    {
++      item->key = key;
++      ht->nr_items += 1;
++    }
++  else
++    {
++      assert (item->key == key);
++      if (ht->cleanup)
++        (*ht->cleanup) (locp, ht->cleanup_data);
++    }
++
++  item->value = value;
++
++  if (ht->locp_offset != HURD_IHASH_NO_LOCP)
++    *((hurd_ihash_locp_t *) (((char *) value) + ht->locp_offset))
++      = locp;
++
++  return 0;
++}
++
++
+ /* 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
+    it before overriding the value.  If a memory allocation error
+@@ -313,6 +360,35 @@ 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.
++
++   If the lookup is successful, the returned location can be used with
++   hurd_ihash_locp_add to update the item, and with
++   hurd_ihash_locp_remove to remove it.
++
++   If the lookup is not successful, the returned location can be used
++   with hurd_ihash_locp_add to add the item.
++
++   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)
++{
++  int idx;
++
++  if (ht->size == 0)
++    return NULL;
++
++  idx = find_index (ht, key);
++  return &ht->items[idx].value;
++}
++
+ 
+ /* Remove the entry with the key KEY from the hash table HT.  If such
+    an entry was found and removed, 1 is returned, otherwise 0.  */
+diff --git a/libihash/ihash.h b/libihash/ihash.h
+index 128027a..1dbc348 100644
+--- a/libihash/ihash.h
++++ b/libihash/ihash.h
+@@ -26,6 +26,7 @@
+ #include <sys/types.h>
+ #include <limits.h>
+ #include <stdint.h>
++#include <stddef.h>
+ 
+ 
+ /* The type of the values corresponding to the keys.  Must be a
+@@ -198,10 +199,61 @@ hurd_ihash_get_load (hurd_ihash_t ht)
+ error_t hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key,
+ 			hurd_ihash_value_t item);
+ 
++/* Add VALUE to the hash table HT under the key KEY at LOCP.  If there
++   already is an item under this key, call the cleanup function (if
++   any) for it before overriding the value.  This function is faster
++   than hurd_ihash_add.
++
++   If LOCP is NULL, fall back to hurd_ihash_add.  Otherwise, LOCP must
++   be valid and may either be obtained from hurd_ihash_locp_find, or
++   from an item that is currently in the hash table.  If an item is
++   replaced, KEY must match the key of the previous item.
++
++   If a memory allocation error occurs, ENOMEM is returned, otherwise
++   0.  */
++error_t hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp,
++                             hurd_ihash_key_t key, hurd_ihash_value_t value);
++
+ /* Find and return the item in the hash table HT with key KEY, or NULL
+    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.
++
++   If the lookup is successful, the returned location can be used with
++   hurd_ihash_locp_add to update the item, and with
++   hurd_ihash_locp_remove to remove it.
++
++   If the lookup is not successful, the returned location can be used
++   with hurd_ihash_locp_add to add the item.
++
++   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;
++}
++
+ /* 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-cache0003-libihash-prefer-performance-degradation-over-failure.patch b/debian/patches/ihash-as-cache0003-libihash-prefer-performance-degradation-over-failure.patch
new file mode 100644
index 00000000..90178650
--- /dev/null
+++ b/debian/patches/ihash-as-cache0003-libihash-prefer-performance-degradation-over-failure.patch
@@ -0,0 +1,61 @@
+From 820fa61ad45099e413acc04674ca645ad758e26b Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Sun, 7 Jun 2015 00:58:36 +0200
+Subject: [PATCH hurd 3/3] libihash: prefer performance degradation over
+ failure
+
+* libihash/ihash.c (hurd_ihash_add): Add the item even though we are
+above the load factor if resizing failed.
+---
+ libihash/ihash.c | 14 ++++++++++++--
+ 1 file changed, 12 insertions(+), 2 deletions(-)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index a97de3e..8133e01 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -301,18 +301,19 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
+ {
+   struct hurd_ihash old_ht = *ht;
+   int was_added;
++  int fatal = 0;	/* bail out on allocation errors */
+   unsigned int i;
+ 
+   if (ht->size)
+     {
+       /* Only fill the hash table up to its maximum load factor.  */
+       if (hurd_ihash_get_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.  */
+-  ht->nr_items = 0;
+   if (ht->size == 0)
+       ht->size = HURD_IHASH_MIN_SIZE;
+   else
+@@ -324,10 +325,19 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
+   if (ht->items == NULL)
+     {
+       *ht = old_ht;
+-      return ENOMEM;
++      if (fatal || ht->size == 0)
++        return ENOMEM;
++
++      /* We prefer performance degradation over failure.  Therefore,
++	 we add the item even though we are above the load factor.  If
++	 the table is full, this will fail.  We set the fatal flag to
++	 avoid looping.	 */
++      fatal = 1;
++      goto add_one;
+     }
+ 
+   /* We have to rehash the old entries.  */
++  ht->nr_items = 0;
+   for (i = 0; i < old_ht.size; i++)
+     if (!index_empty (&old_ht, i))
+       {
+-- 
+2.1.4
+
diff --git a/debian/patches/series b/debian/patches/series
index 1ec2b4a9..5fbb94bd 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -53,3 +53,6 @@ introspection0006-libpager-annotate-objects-managed-by-libports.patch
 introspection0007-ext2fs-annotate-objects-managed-by-libports.patch
 introspection0008-utils-rpctrace-support-attaching-to-servers.patch
 introspection0009-pflocal-annotate-objects-managed-by-libports.patch
+ihash-as-cache0001-libihash-add-hurd_ihash_value_valid.patch
+ihash-as-cache0002-libihash-optimize-lookup-or-insert-operations.patch
+ihash-as-cache0003-libihash-prefer-performance-degradation-over-failure.patch