add patch series

3 files changed, 380 insertions, 0 deletions

diff --git a/debian/patches/nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch b/debian/patches/nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch
new file mode 100644
index 00000000..da6f1c09
--- /dev/null
+++ b/debian/patches/nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch
@@ -0,0 +1,260 @@
+From 8ca7a316d0096eb2df8935f12533c1b8f66998c8 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Wed, 24 Jun 2015 02:30:01 +0200
+Subject: [PATCH hurd 1/2] libdiskfs: use ihash for the node cache
+
+Replace the hand-written hash table in the node cache with libihash.
+Libihash is a self-tuning hash table, whereas the previous code used a
+fixed number of buckets.
+
+* libdiskfs/Makefile (HURDLIBS): Link to `ihash'.
+* libdiskfs/diskfs.h (struct node): Remove bucket list, add slot pointer.
+* libdiskfs/node-cache.c (nodecache): New ihash table replacing the
+old `nodehash'.
+(lookup): Drop function.
+(diskfs_cached_lookup_context): Adapt accordingly.
+(diskfs_cached_ifind): Likewise.
+(diskfs_try_dropping_softrefs): Likewise.
+(diskfs_node_iterate): Likewise.
+---
+ libdiskfs/Makefile     |   2 +-
+ libdiskfs/diskfs.h     |   5 ++-
+ libdiskfs/node-cache.c | 107 +++++++++++++++++++++++--------------------------
+ 3 files changed, 55 insertions(+), 59 deletions(-)
+
+diff --git a/libdiskfs/Makefile b/libdiskfs/Makefile
+index 47b9339..803761d 100644
+--- a/libdiskfs/Makefile
++++ b/libdiskfs/Makefile
+@@ -61,7 +61,7 @@ MIGSTUBS = fsServer.o ioServer.o fsysServer.o exec_startupServer.o \
+ 	startup_notifyServer.o
+ OBJS = $(sort $(SRCS:.c=.o) $(MIGSTUBS))
+ 
+-HURDLIBS = fshelp iohelp store ports shouldbeinlibc pager
++HURDLIBS = fshelp iohelp store ports shouldbeinlibc pager ihash
+ LDLIBS += -lpthread
+ 
+ fsys-MIGSFLAGS = -imacros $(srcdir)/fsmutations.h -DREPLY_PORTS
+diff --git a/libdiskfs/diskfs.h b/libdiskfs/diskfs.h
+index 11fb0ad..106aeb0 100644
+--- a/libdiskfs/diskfs.h
++++ b/libdiskfs/diskfs.h
+@@ -25,6 +25,7 @@
+ #include <pthread.h>
+ #include <hurd/ports.h>
+ #include <hurd/fshelp.h>
++#include <hurd/ihash.h>
+ #include <hurd/iohelp.h>
+ #include <idvec.h>
+ #include <features.h>
+@@ -80,8 +81,8 @@ struct peropen
+    filesystem.  */
+ struct node
+ {
+-  /* Links on hash list. */
+-  struct node *hnext, **hprevp;
++  /* The slot we occupy in the node cache.  */
++  hurd_ihash_locp_t slot;
+ 
+   struct disknode *dn;
+ 
+diff --git a/libdiskfs/node-cache.c b/libdiskfs/node-cache.c
+index a76474a..ee7e6fd 100644
+--- a/libdiskfs/node-cache.c
++++ b/libdiskfs/node-cache.c
+@@ -17,46 +17,49 @@
+    You should have received a copy of the GNU General Public License
+    along with the GNU Hurd.  If not, see <http://www.gnu.org/licenses/>.  */
+ 
+-#include "priv.h"
+-
+-#define	INOHSZ	8192
+-#if	((INOHSZ&(INOHSZ-1)) == 0)
+-#define	INOHASH(ino)	((ino)&(INOHSZ-1))
+-#else
+-#define	INOHASH(ino)	(((unsigned)(ino))%INOHSZ)
+-#endif
++#include <hurd/ihash.h>
+ 
+-/* The nodehash is a cache of nodes.
++#include "priv.h"
+ 
+-   Access to nodehash and nodehash_nr_items is protected by
+-   nodecache_lock.
++/* The node cache is implemented using a hash table.  Access to the
++   cache is protected by nodecache_lock.
+ 
+-   Every node in the nodehash carries a light reference.  When we are
++   Every node in the cache carries a light reference.  When we are
+    asked to give up that light reference, we reacquire our lock
+    momentarily to check whether someone else reacquired a reference
+-   through the nodehash.  */
+-static struct node *nodehash[INOHSZ];
+-static size_t nodehash_nr_items;
+-static pthread_rwlock_t nodecache_lock = PTHREAD_RWLOCK_INITIALIZER;
++   through the cache.  */
++
++/* The size of ino_t is larger than hurd_ihash_key_t on 32 bit
++   platforms.  We therefore have to use libihashs generalized key
++   interface.  */
++
++/* This is the mix function of fasthash, see
++   https://code.google.com/p/fast-hash/ for reference.  */
++#define mix_fasthash(h) ({              \
++        (h) ^= (h) >> 23;               \
++        (h) *= 0x2127599bf4325c37ULL;   \
++        (h) ^= (h) >> 47; })
+ 
+-/* Initialize the inode hash table. */
+-static void __attribute__ ((constructor))
+-nodecache_init ()
++static hurd_ihash_key_t
++hash (const void *key)
+ {
++  ino_t i;
++  i = *(ino_t *) key;
++  mix_fasthash (i);
++  return (hurd_ihash_key_t) i;
+ }
+ 
+-/* Lookup node with inode number INUM.  Returns NULL if the node is
+-   not found in the node cache.  */
+-static struct node *
+-lookup (ino_t inum)
++static int
++compare (const void *a, const void *b)
+ {
+-  struct node *np;
+-  for (np = nodehash[INOHASH(inum)]; np; np = np->hnext)
+-    if (np->cache_id == inum)
+-      return np;
+-  return NULL;
++  return *(ino_t *) a == *(ino_t *) b;
+ }
+ 
++static struct hurd_ihash nodecache =
++  HURD_IHASH_INITIALIZER_GKI (offsetof (struct node, slot), NULL, NULL,
++                              hash, compare);
++static pthread_rwlock_t nodecache_lock = PTHREAD_RWLOCK_INITIALIZER;
++
+ /* Fetch inode INUM, set *NPP to the node structure;
+    gain one user reference and lock the node.  */
+ error_t __attribute__ ((weak))
+@@ -73,9 +76,10 @@ diskfs_cached_lookup_context (ino_t inum, struct node **npp,
+ {
+   error_t err;
+   struct node *np, *tmp;
++  hurd_ihash_locp_t slot;
+ 
+   pthread_rwlock_rdlock (&nodecache_lock);
+-  np = lookup (inum);
++  np = hurd_ihash_locp_find (&nodecache, (hurd_ihash_key_t) &inum, &slot);
+   if (np)
+     goto gotit;
+   pthread_rwlock_unlock (&nodecache_lock);
+@@ -89,7 +93,8 @@ diskfs_cached_lookup_context (ino_t inum, struct node **npp,
+ 
+   /* Put NP in NODEHASH.  */
+   pthread_rwlock_wrlock (&nodecache_lock);
+-  tmp = lookup (inum);
++  tmp = hurd_ihash_locp_find (&nodecache, (hurd_ihash_key_t) &np->cache_id,
++			      &slot);
+   if (tmp)
+     {
+       /* We lost a race.  */
+@@ -98,13 +103,10 @@ diskfs_cached_lookup_context (ino_t inum, struct node **npp,
+       goto gotit;
+     }
+ 
+-  np->hnext = nodehash[INOHASH(inum)];
+-  if (np->hnext)
+-    np->hnext->hprevp = &np->hnext;
+-  np->hprevp = &nodehash[INOHASH(inum)];
+-  nodehash[INOHASH(inum)] = np;
++  err = hurd_ihash_locp_add (&nodecache, slot,
++			     (hurd_ihash_key_t) &np->cache_id, np);
++  assert_perror (err);
+   diskfs_nref_light (np);
+-  nodehash_nr_items += 1;
+   pthread_rwlock_unlock (&nodecache_lock);
+ 
+   /* Get the contents of NP off disk.  */
+@@ -133,7 +135,7 @@ diskfs_cached_ifind (ino_t inum)
+   struct node *np;
+ 
+   pthread_rwlock_rdlock (&nodecache_lock);
+-  np = lookup (inum);
++  np = hurd_ihash_find (&nodecache, (hurd_ihash_key_t) &inum);
+   pthread_rwlock_unlock (&nodecache_lock);
+ 
+   assert (np);
+@@ -144,7 +146,7 @@ void __attribute__ ((weak))
+ diskfs_try_dropping_softrefs (struct node *np)
+ {
+   pthread_rwlock_wrlock (&nodecache_lock);
+-  if (np->hprevp != NULL)
++  if (np->slot != NULL)
+     {
+       /* Check if someone reacquired a reference through the
+ 	 nodehash.  */
+@@ -159,12 +161,8 @@ diskfs_try_dropping_softrefs (struct node *np)
+ 	  return;
+ 	}
+ 
+-      *np->hprevp = np->hnext;
+-      if (np->hnext)
+-	np->hnext->hprevp = np->hprevp;
+-      np->hnext = NULL;
+-      np->hprevp = NULL;
+-      nodehash_nr_items -= 1;
++      hurd_ihash_locp_remove (&nodecache, np->slot);
++      np->slot = NULL;
+       diskfs_nrele_light (np);
+     }
+   pthread_rwlock_unlock (&nodecache_lock);
+@@ -179,7 +177,6 @@ error_t __attribute__ ((weak))
+ diskfs_node_iterate (error_t (*fun)(struct node *))
+ {
+   error_t err = 0;
+-  int n;
+   size_t num_nodes;
+   struct node *node, **node_list, **p;
+ 
+@@ -191,7 +188,7 @@ diskfs_node_iterate (error_t (*fun)(struct node *))
+      nodecache_lock, but we can't hold this while locking the
+      individual node locks).  */
+   /* XXX: Can we?  */
+-  num_nodes = nodehash_nr_items;
++  num_nodes = nodecache.nr_items;
+ 
+   /* TODO This method doesn't scale beyond a few dozen nodes and should be
+      replaced.  */
+@@ -203,17 +200,15 @@ diskfs_node_iterate (error_t (*fun)(struct node *))
+     }
+ 
+   p = node_list;
+-  for (n = 0; n < INOHSZ; n++)
+-    for (node = nodehash[n]; node; node = node->hnext)
+-      {
+-	*p++ = node;
+-
+-	/* We acquire a hard reference for node, but without using
+-	   diskfs_nref.	 We do this so that diskfs_new_hardrefs will not
+-	   get called.	*/
+-	refcounts_ref (&node->refcounts, NULL);
+-      }
++  HURD_IHASH_ITERATE (&nodecache, i)
++    {
++      *p++ = node = i;
+ 
++      /* We acquire a hard reference for node, but without using
++	 diskfs_nref.  We do this so that diskfs_new_hardrefs will not
++	 get called.  */
++      refcounts_ref (&node->refcounts, NULL);
++    }
+   pthread_rwlock_unlock (&nodecache_lock);
+ 
+   p = node_list;
+-- 
+2.1.4
+
diff --git a/debian/patches/nodeihash0002-xxx-fix-node-iteration.patch b/debian/patches/nodeihash0002-xxx-fix-node-iteration.patch
new file mode 100644
index 00000000..67f768ff
--- /dev/null
+++ b/debian/patches/nodeihash0002-xxx-fix-node-iteration.patch
@@ -0,0 +1,118 @@
+From f465c6d344375bd889282972137e91bcfe317cc7 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Fri, 20 Nov 2015 12:45:28 +0100
+Subject: [PATCH hurd 2/2] xxx fix node iteration
+
+---
+ libdiskfs/diskfs.h     |  8 +++----
+ libdiskfs/node-cache.c | 63 ++++++++++++++++----------------------------------
+ 2 files changed, 24 insertions(+), 47 deletions(-)
+
+diff --git a/libdiskfs/diskfs.h b/libdiskfs/diskfs.h
+index 106aeb0..51bb79f 100644
+--- a/libdiskfs/diskfs.h
++++ b/libdiskfs/diskfs.h
+@@ -521,10 +521,10 @@ void diskfs_write_disknode (struct node *np, int wait);
+ void diskfs_file_update (struct node *np, int wait);
+ 
+ /* The user must define this function unless she wants to use the node
+-   cache.  See the section `Node cache' below.  For each active node, call
+-   FUN.  The node is to be locked around the call to FUN.  If FUN
+-   returns non-zero for any node, then immediately stop, and return
+-   that value. */
++   cache.  See the section `Node cache' below.  For each active node,
++   call FUN.  The node is to be locked around the call to FUN.  FUN
++   must be idempotent.  If FUN returns non-zero for any node, then
++   immediately stop, and return that value. */
+ error_t diskfs_node_iterate (error_t (*fun)(struct node *));
+ 
+ /* The user must define this function.  Sync all the pagers and any
+diff --git a/libdiskfs/node-cache.c b/libdiskfs/node-cache.c
+index ee7e6fd..4016779 100644
+--- a/libdiskfs/node-cache.c
++++ b/libdiskfs/node-cache.c
+@@ -170,61 +170,38 @@ diskfs_try_dropping_softrefs (struct node *np)
+   diskfs_user_try_dropping_softrefs (np);
+ }
+ 
+-/* For each active node, call FUN.  The node is to be locked around the call
+-   to FUN.  If FUN returns non-zero for any node, then immediately stop, and
+-   return that value.  */
++/* For each active node, call FUN.  FUN must be idempotent.  The node
++   is to be locked around the call to FUN.  If FUN returns non-zero
++   for any node, then immediately stop, and return that value.  */
+ error_t __attribute__ ((weak))
+ diskfs_node_iterate (error_t (*fun)(struct node *))
+ {
+   error_t err = 0;
+-  size_t num_nodes;
+-  struct node *node, **node_list, **p;
++  struct node *node;
+ 
++  /* XXX */
++ restart:
+   pthread_rwlock_rdlock (&nodecache_lock);
+ 
+-  /* We must copy everything from the hash table into another data structure
+-     to avoid running into any problems with the hash-table being modified
+-     during processing (normally we delegate access to hash-table with
+-     nodecache_lock, but we can't hold this while locking the
+-     individual node locks).  */
+-  /* XXX: Can we?  */
+-  num_nodes = nodecache.nr_items;
+-
+-  /* TODO This method doesn't scale beyond a few dozen nodes and should be
+-     replaced.  */
+-  node_list = malloc (num_nodes * sizeof (struct node *));
+-  if (node_list == NULL)
+-    {
+-      pthread_rwlock_unlock (&nodecache_lock);
+-      return ENOMEM;
+-    }
+-
+-  p = node_list;
+   HURD_IHASH_ITERATE (&nodecache, i)
+     {
+-      *p++ = node = i;
+-
+-      /* We acquire a hard reference for node, but without using
+-	 diskfs_nref.  We do this so that diskfs_new_hardrefs will not
+-	 get called.  */
+-      refcounts_ref (&node->refcounts, NULL);
++      node = i;
++
++      if (pthread_mutex_trylock (&node->lock))
++        {
++          /* Failed to acquire the lock.  Release the cache lock and
++             restart iteration.  */
++          pthread_rwlock_unlock (&nodecache_lock);
++          goto restart;
++        }
++      err = (*fun)(node);
++      pthread_mutex_unlock (&node->lock);
++      if (err)
++        break;
+     }
+-  pthread_rwlock_unlock (&nodecache_lock);
+ 
+-  p = node_list;
+-  while (num_nodes-- > 0)
+-    {
+-      node = *p++;
+-      if (!err)
+-	{
+-	  pthread_mutex_lock (&node->lock);
+-	  err = (*fun)(node);
+-	  pthread_mutex_unlock (&node->lock);
+-	}
+-      diskfs_nrele (node);
+-    }
++  pthread_rwlock_unlock (&nodecache_lock);
+ 
+-  free (node_list);
+   return err;
+ }
+ 
+-- 
+2.1.4
+
diff --git a/debian/patches/series b/debian/patches/series
index 33142212..c4bc7c96 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -54,3 +54,5 @@ 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
+nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch
+nodeihash0002-xxx-fix-node-iteration.patch