more patches, most notably cuckoo hashing

4 files changed, 469 insertions, 0 deletions

diff --git a/debian/patches/0009-ext2fs-improve-enable-disable-_caching.patch b/debian/patches/0009-ext2fs-improve-enable-disable-_caching.patch
new file mode 100644
index 00000000..f7752a36
--- /dev/null
+++ b/debian/patches/0009-ext2fs-improve-enable-disable-_caching.patch
@@ -0,0 +1,38 @@
+From afa09fc5d380d0a6fd5f6ddd37eb32c9f359de26 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Fri, 9 May 2014 10:07:28 +0200
+Subject: [PATCH 09/11] ext2fs: improve {enable,disable}_caching
+
+* ext2fs/pager.c (enable_caching, disable_caching): Iterate over the
+pager class instead of over both pager buckets.
+---
+ ext2fs/pager.c | 6 ++----
+ 1 file changed, 2 insertions(+), 4 deletions(-)
+
+diff --git a/ext2fs/pager.c b/ext2fs/pager.c
+index 017efcc..6328f3b 100644
+--- a/ext2fs/pager.c
++++ b/ext2fs/pager.c
+@@ -1409,8 +1409,7 @@ disable_caching ()
+ 
+   /* Loop through the pagers and turn off caching one by one,
+      synchronously.  That should cause termination of each pager. */
+-  ports_bucket_iterate (disk_pager_bucket, block_cache);
+-  ports_bucket_iterate (file_pager_bucket, block_cache);
++  ports_class_iterate (_pager_class, block_cache);
+ }
+ 
+ static void
+@@ -1438,8 +1437,7 @@ enable_caching ()
+       return 0;
+     }
+ 
+-  ports_bucket_iterate (disk_pager_bucket, enable_cache);
+-  ports_bucket_iterate (file_pager_bucket, enable_cache);
++  ports_class_iterate (_pager_class, enable_cache);
+ }
+ 
+ /* Tell diskfs if there are pagers exported, and if none, then
+-- 
+2.0.0.rc0
+
diff --git a/debian/patches/0010-fatfs-improve-enable-disable-_caching.patch b/debian/patches/0010-fatfs-improve-enable-disable-_caching.patch
new file mode 100644
index 00000000..e39bdfd8
--- /dev/null
+++ b/debian/patches/0010-fatfs-improve-enable-disable-_caching.patch
@@ -0,0 +1,48 @@
+From 8071bad9edfaf6990a17fcdd68f88afa01456566 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Fri, 9 May 2014 10:11:45 +0200
+Subject: [PATCH 10/11] fatfs: improve {enable,disable}_caching
+
+* fatfs/pager.c (enable_caching, disable_caching): Iterate over the
+pager class instead of over both pager buckets.
+---
+ fatfs/pager.c | 9 +++++----
+ 1 file changed, 5 insertions(+), 4 deletions(-)
+
+diff --git a/fatfs/pager.c b/fatfs/pager.c
+index f855ecf..7aa5c5e 100644
+--- a/fatfs/pager.c
++++ b/fatfs/pager.c
+@@ -23,6 +23,9 @@
+ #include <hurd/store.h>
+ #include "fatfs.h"
+ 
++/* XXX */
++#include "../libpager/priv.h"
++
+ /* A ports bucket to hold disk pager ports.  */
+ struct port_bucket *disk_pager_bucket;
+ 
+@@ -963,8 +966,7 @@ disable_caching ()
+ 
+   /* Loop through the pagers and turn off caching one by one,
+      synchronously.  That should cause termination of each pager.  */
+-  ports_bucket_iterate (disk_pager_bucket, block_cache);
+-  ports_bucket_iterate (file_pager_bucket, block_cache);
++  ports_class_iterate (_pager_class, block_cache);
+ }
+ 	  
+ static void
+@@ -992,8 +994,7 @@ enable_caching ()
+       return 0;
+     }
+ 
+-  ports_bucket_iterate (disk_pager_bucket, enable_cache);
+-  ports_bucket_iterate (file_pager_bucket, enable_cache);
++  ports_class_iterate (_pager_class, enable_cache);
+ }
+ 	    
+ /* Tell diskfs if there are pagers exported, and if none, then
+-- 
+2.0.0.rc0
+
diff --git a/debian/patches/0011-XXX-libports-cuckoo-hashing.patch b/debian/patches/0011-XXX-libports-cuckoo-hashing.patch
new file mode 100644
index 00000000..8095584f
--- /dev/null
+++ b/debian/patches/0011-XXX-libports-cuckoo-hashing.patch
@@ -0,0 +1,380 @@
+From e444428e279c8b1b47c5c19abc093d6fd59c106d Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Sat, 10 May 2014 10:05:07 +0200
+Subject: [PATCH 11/11] XXX libports: cuckoo hashing
+
+---
+ libihash/ihash.c | 200 ++++++++++++++++++++++++++++++-------------------------
+ libihash/ihash.h |  38 +++--------
+ 2 files changed, 119 insertions(+), 119 deletions(-)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index e74a2c5..4a0ff07 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -69,6 +69,18 @@ index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key)
+   return !index_empty (ht, idx) && ht->items[idx].key == key;
+ }
+ 
++static inline unsigned int
++hash0 (hurd_ihash_t ht, hurd_ihash_key_t key)
++{
++  return hash_int32 (key ^ ht->salt0, ht->size - 1);
++}
++
++static inline unsigned int
++hash1 (hurd_ihash_t ht, hurd_ihash_key_t key)
++{
++  return hash_int32 (key ^ ht->salt1, ht->size - 1)
++    | (1U << (ht->size - 2));	/* add offset */
++}
+ 
+ /* Given a hash table HT, and a key KEY, find the index in the table
+    of that key.  You must subsequently check with index_valid() if the
+@@ -76,29 +88,13 @@ index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key)
+ static inline int
+ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
+ {
+-  unsigned int idx;
+-  unsigned int up_idx;
+-  unsigned int mask = ht->size - 1;
+-
+-  idx = hash_int32 (key, 32) & mask;
+-
+-  if (ht->items[idx].value == _HURD_IHASH_EMPTY || 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
+-	  || ht->items[up_idx].key == key)
+-	return up_idx;
+-    }
+-  while (up_idx != idx);
++  unsigned int idx0, idx1;
++  idx0 = hash0 (ht, key);
++  idx1 = hash1 (ht, key);
+ 
+-  /* If we end up here, the item could not be found.  Return any
+-     invalid index.  */
+-  return idx;
++  if (ht->items[idx0].key == key)
++    return idx0;
++  return idx1;
+ }
+ 
+ 
+@@ -124,8 +120,9 @@ hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs)
+   ht->nr_items = 0;
+   ht->size = 0;
+   ht->locp_offset = locp_offs;
+-  ht->max_load = HURD_IHASH_MAX_LOAD_DEFAULT;
+   ht->cleanup = 0;
++  ht->salt0 = 0;
++  ht->salt1 = ~0;
+ }
+ 
+ 
+@@ -184,27 +181,47 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
+   ht->cleanup = cleanup;
+   ht->cleanup_data = cleanup_data;
+ }
++
++/* XXX */
++static inline int
++add_item (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
++{
++  struct _hurd_ihash_item item, old;
++  unsigned int idx0, idx1;
+ 
++  item = (struct _hurd_ihash_item){ .key = key, .value = value};
+ 
+-/* Set the maximum load factor in percent to MAX_LOAD, which should be
+-   between 1 and 100.  The default is HURD_IHASH_MAX_LOAD_DEFAULT.
+-   New elements are only added to the hash table while the number of
+-   hashed elements is that much percent of the total size of the hash
+-   table.  If more elements are added, the hash table is first
+-   expanded and reorganized.  A MAX_LOAD of 100 will always fill the
+-   whole table before enlarging it, but note that this will increase
+-   the cost of operations significantly when the table is almost full.
++  /* xxx max_loop = round_up (3 * log_{1+epsilon}(n)) */
++  unsigned int i;
++  for (i = 0; i < 3 * ht->size; i++)
++    {
++      idx0 = hash0 (ht, item.key);
++      if (index_empty (ht, idx0))
++        {
++          ht->items[idx0] = item;
++          return 1;
++        }
++
++      old = ht->items[idx0];
++      ht->items[idx0] = item;
++      item = old;
++
++      idx1 = hash1 (ht, item.key);
++      if (index_empty (ht, idx1))
++        {
++          ht->items[idx1] = item;
++          return 1;
++        }
++
++      old = ht->items[idx0];
++      ht->items[idx0] = item;
++      item = old;
++    }
+ 
+-   If the value is set to a smaller value than the current load
+-   factor, the next reorganization will happen when a new item is
+-   added to the hash table.  */
+-void
+-hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load)
+-{
+-  ht->max_load = max_load;
++  return 0;
+ }
+ 
+-
++
+ /* Helper function for hurd_ihash_add.  Return 1 if the item was
+    added, and 0 if it could not be added because no empty slot was
+    found.  The arguments are identical to hurd_ihash_add.
+@@ -215,53 +232,55 @@ hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load)
+ 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_int32 (key, 32) & mask;
+-  first_free = idx;
+-
+-  if (ht->items[idx].value != _HURD_IHASH_EMPTY && 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
+-	      || ht->items[up_idx].key == key)
+-	    {
+-	      idx = up_idx;
+-	      break;
+-	    }
+-	}
+-      while (up_idx != idx);
+-    }
+-
+-  /* Remove the old entry for this key if necessary.  */
++  unsigned int idx = find_index (ht, key);
+   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))
+     {
+-      ht->nr_items++;
+-      ht->items[first_free].value = value;
+-      ht->items[first_free].key = key;
+-
+-      if (ht->locp_offset != HURD_IHASH_NO_LOCP)
+-	*((hurd_ihash_locp_t *) (((char *) value) + ht->locp_offset))
+-	  = &ht->items[first_free].value;
+-
++      /* Update the entry.  */
++      locp_remove (ht, &ht->items[idx].value);
++      ht->items[idx].value = value;
+       return 1;
+     }
+ 
+-  return 0;
++  int added = add_item (ht, key, value);
++  if (added)
++    return 1;
++
++  /* We failed.  */
++
++  /* The item that needs to be added.  Also, if we remove an item from
++     the table, we store it here.  If we fail to insert it again, we
++     start over.  */
++  struct _hurd_ihash_item item =
++    (struct _hurd_ihash_item){ .key = key, .value = value};
++
++ retry:
++  /* Pick different hash functions.  */
++  ht->salt0 = hash_int32 (ht->salt0, 32);
++  ht->salt1 = hash_int32 (ht->salt1, 32);
++
++  /* Try to insert the new or stashed item.  */
++  added = add_item (ht, item.key, item.value);
++  if (! added)
++    goto retry;
++
++  /* Rehash the table.  */
++  for (idx = 0; idx < (1U << ht->size); idx++)
++    if (! index_empty (ht, idx)
++        /* For each non-empty slot, check if the item there is not at
++           the correct (new) index.  */
++        && (idx < (1U << (ht->size - 1)) /* select the appropriate
++                                            hash function */
++            ? hash0 (ht, ht->items[idx].key) != idx
++            : hash1 (ht, ht->items[idx].key) != idx))
++      {
++        item = ht->items[idx];
++        ht->items[idx].value = _HURD_IHASH_EMPTY;
++        added = add_item (ht, item.key, item.value);
++        if (! added)
++          goto retry;
++      }
++
++  return 1;
+ }
+ 
+   
+@@ -278,8 +297,8 @@ 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 (ht->nr_items * 100 / ht->size <= ht->max_load)
++      /* Keep the load below 0.5.  */
++      if (ht->nr_items < (1U << (ht->size - 1)))
+ 	if (add_one (ht, key, item))
+ 	  return 0;
+     }
+@@ -289,10 +308,10 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
+   if (ht->size == 0)
+       ht->size = HURD_IHASH_MIN_SIZE;
+   else
+-      ht->size <<= 1;
++      ht->size += 1;	/* double the size */
+ 
+   /* calloc() will initialize all values to _HURD_IHASH_EMPTY implicitely.  */
+-  ht->items = calloc (ht->size, sizeof (struct _hurd_ihash_item));
++  ht->items = calloc (1U << ht->size, sizeof (struct _hurd_ihash_item));
+ 
+   if (ht->items == NULL)
+     {
+@@ -301,12 +320,11 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
+     }
+ 
+   /* We have to rehash the old entries.  */
+-  for (i = 0; i < old_ht.size; i++)
+-    if (!index_empty (&old_ht, i))
+-      {
+-	was_added = add_one (ht, old_ht.items[i].key, old_ht.items[i].value);
+-	assert (was_added);
+-      }
++  HURD_IHASH_ITERATE_ITEMS (&old_ht, item)
++    {
++      was_added = add_one (ht, item->key, item->value);
++      assert (was_added);
++    }
+ 
+   /* Finally add the new element!  */
+   was_added = add_one (ht, key, item);
+diff --git a/libihash/ihash.h b/libihash/ihash.h
+index 057babc..27045cb 100644
+--- a/libihash/ihash.h
++++ b/libihash/ihash.h
+@@ -73,32 +73,29 @@ struct hurd_ihash
+   /* An array of (key, value) pairs.  */
+   _hurd_ihash_item_t items;
+ 
+-  /* The length of the array ITEMS.  */
++  /* Log2 of the length of the array ITEMS, or 0 indicating that ITEMS
++     has not been allocated.  */
+   size_t size;
+ 
+   /* The offset of the location pointer from the hash value.  */
+   intptr_t locp_offset;
+ 
+-  /* The maximum load factor in percent.  */
+-  int max_load;
+-
+   /* When freeing or overwriting an element, this function is called
+      with the value as the first argument, and CLEANUP_DATA as the
+      second argument.  This does not happen if CLEANUP is NULL.  */
+   hurd_ihash_cleanup_t cleanup;
+   void *cleanup_data;
++
++  /* Salts for the hash function.  */
++  uint32_t salt0, salt1;
+ };
+ typedef struct hurd_ihash *hurd_ihash_t;
+ 
+ 
+ /* Construction and destruction of hash tables.  */
+ 
+-/* The size of the initial allocation in number of items.  This must
+-   be a power of two.  */
+-#define HURD_IHASH_MIN_SIZE	32
+-
+-/* The default value for the maximum load factor in percent.  */
+-#define HURD_IHASH_MAX_LOAD_DEFAULT 75
++/* The size of the initial allocation in log2(number of items).  */
++#define HURD_IHASH_MIN_SIZE	5
+ 
+ /* The LOCP_OFFS to use if no location pointer is available.  */
+ #define HURD_IHASH_NO_LOCP	INTPTR_MIN
+@@ -106,8 +103,7 @@ typedef struct hurd_ihash *hurd_ihash_t;
+ /* The static initializer for a struct hurd_ihash.  */
+ #define HURD_IHASH_INITIALIZER(locp_offs)				\
+   { .nr_items = 0, .size = 0, .cleanup = (hurd_ihash_cleanup_t) 0,	\
+-    .max_load = HURD_IHASH_MAX_LOAD_DEFAULT,				\
+-    .locp_offset = (locp_offs)}
++    .locp_offset = (locp_offs), .salt0 = 0, .salt1 = ~0 }
+ 
+ /* 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
+@@ -143,20 +139,6 @@ 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);
+ 
+-/* Set the maximum load factor in percent to MAX_LOAD, which should be
+-   between 50 and 100.  The default is HURD_IHASH_MAX_LOAD_DEFAULT.
+-   New elements are only added to the hash table while the number of
+-   hashed elements is that much percent of the total size of the hash
+-   table.  If more elements are added, the hash table is first
+-   expanded and reorganized.  A MAX_LOAD of 100 will always fill the
+-   whole table before enlarging it, but note that this will increase
+-   the cost of operations significantly when the table is almost full.
+-
+-   If the value is set to a smaller value than the current load
+-   factor, the next reorganization will happen when a new item is
+-   added to the hash table.  */
+-void hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load);
+-
+ 
+ /* 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
+@@ -216,7 +198,7 @@ hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key);
+          *_hurd_ihash_valuep = (ht)->size ? &(ht)->items[0].value : 0;	\
+        (ht)->size							\
+          && ((_hurd_ihash_item_t) _hurd_ihash_valuep) - &(ht)->items[0]	\
+-            < (ht)->size						\
++         < (1U << (ht)->size)                                           \
+          && (val = *_hurd_ihash_valuep, 1);				\
+        _hurd_ihash_valuep = (hurd_ihash_value_t *)			\
+ 	 (((_hurd_ihash_item_t) _hurd_ihash_valuep) + 1))		\
+@@ -234,7 +216,7 @@ hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key);
+    ITEM->value.  */
+ #define HURD_IHASH_ITERATE_ITEMS(ht, item)                              \
+   for (_hurd_ihash_item_t item = (ht)->size? &(ht)->items[0]: 0;	\
+-       (ht)->size && item - &(ht)->items[0] < (ht)->size;               \
++       (ht)->size && item - &(ht)->items[0] < (1U << (ht)->size);       \
+        item++)                                                          \
+     if (item->value != _HURD_IHASH_EMPTY &&                             \
+         item->value != _HURD_IHASH_DELETED)
+-- 
+2.0.0.rc0
+
diff --git a/debian/patches/series b/debian/patches/series
index a9c38fe3..b55ee129 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -49,3 +49,6 @@ ext2fs-cache-superblock.patch
 0006-libihash-use-an-integer-hash-function-on-the-keys.patch
 0007-libihash-reduce-the-default-maximum-load-factor-to-7.patch
 0008-libihash-use-linear-probing-and-fast-modulo-operatio.patch
+0009-ext2fs-improve-enable-disable-_caching.patch
+0010-fatfs-improve-enable-disable-_caching.patch
+0011-XXX-libports-cuckoo-hashing.patch