add 0014-ext2fs-use-libihash-for-the-nodehash.patch

2 files changed, 240 insertions, 0 deletions

diff --git a/debian/patches/0014-ext2fs-use-libihash-for-the-nodehash.patch b/debian/patches/0014-ext2fs-use-libihash-for-the-nodehash.patch
new file mode 100644
index 00000000..a16f1a04
--- /dev/null
+++ b/debian/patches/0014-ext2fs-use-libihash-for-the-nodehash.patch
@@ -0,0 +1,239 @@
+From 92c63891ec976a3b3bdc4dcabf44751111f734f0 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Wed, 14 May 2014 15:30:19 +0200
+Subject: [PATCH 14/14] ext2fs: use libihash for the nodehash
+
+Previously, a lookup of a node through nodehash took O(N / INOHSZ).
+With INOHSZ being a constant (512) this is linear in N.  Use libihash
+instead, which will provide a better lookup performance.
+
+* ext2fs/inode.c (INOHSZ, INOHASH, nodehash_nr_items): Remove.
+(nodehash): Make it a struct hurd_ihash and initialize.
+(inode_init): Remove.
+(diskfs_cached_lookup): Adjust accordingly.
+(ifind, diskfs_try_dropping_softrefs, diskfs_node_iterate): Likewise.
+* ext2fs/ext2fs.h (struct disknode): Remove list pointers, add locp field.
+* ext2fs/ext2fs.c (main): Drop inode_init.
+---
+ ext2fs/ext2fs.c |  2 --
+ ext2fs/ext2fs.h |  4 +--
+ ext2fs/inode.c  | 96 ++++++++++++++++++++++++++-------------------------------
+ 3 files changed, 46 insertions(+), 56 deletions(-)
+
+diff --git a/ext2fs/ext2fs.c b/ext2fs/ext2fs.c
+index 128b6ed..0409dfb 100644
+--- a/ext2fs/ext2fs.c
++++ b/ext2fs/ext2fs.c
+@@ -185,8 +185,6 @@ main (int argc, char **argv)
+ 
+   map_hypermetadata ();
+ 
+-  inode_init ();
+-
+   /* Set diskfs_root_node to the root inode. */
+   err = diskfs_cached_lookup (EXT2_ROOT_INO, &diskfs_root_node);
+   if (err)
+diff --git a/ext2fs/ext2fs.h b/ext2fs/ext2fs.h
+index 3422af2..3de7d50 100644
+--- a/ext2fs/ext2fs.h
++++ b/ext2fs/ext2fs.h
+@@ -159,8 +159,8 @@ struct disknode
+      each DIRBLKSIZE piece of the directory. */
+   int *dirents;
+ 
+-  /* Links on hash list. */
+-  struct node *hnext, **hprevp;
++  /* Quick-removal pointer for libihash. */
++  hurd_ihash_locp_t nodehash_locp;
+ 
+   /* Lock to lock while fiddling with this inode's block allocation info.  */
+   pthread_rwlock_t alloc_lock;
+diff --git a/ext2fs/inode.c b/ext2fs/inode.c
+index 7ec343f..d39f0ac 100644
+--- a/ext2fs/inode.c
++++ b/ext2fs/inode.c
+@@ -20,6 +20,7 @@
+    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
+ 
+ #include "ext2fs.h"
++#include <stddef.h>
+ #include <string.h>
+ #include <unistd.h>
+ #include <stdio.h>
+@@ -39,13 +40,6 @@
+ #define UF_IMMUTABLE 0
+ #endif
+ 
+-#define	INOHSZ	512
+-#if	((INOHSZ&(INOHSZ-1)) == 0)
+-#define	INOHASH(ino)	((ino)&(INOHSZ-1))
+-#else
+-#define	INOHASH(ino)	(((unsigned)(ino))%INOHSZ)
+-#endif
+-
+ /* The nodehash is a cache of nodes.
+ 
+    Access to nodehash and nodehash_nr_items is protected by
+@@ -55,23 +49,19 @@
+    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 struct hurd_ihash nodehash =
++#if notyet
++  HURD_IHASH_INITIALIZER_XXX (offsetof (struct disknode, nodehash_locp));
++#else
++  HURD_IHASH_INITIALIZER (HURD_IHASH_NO_LOCP);
++#endif
++
+ static pthread_mutex_t nodehash_lock = PTHREAD_MUTEX_INITIALIZER;
+ 
+ static error_t read_node (struct node *np);
+ 
+ pthread_spinlock_t generation_lock = PTHREAD_SPINLOCK_INITIALIZER;
+ 
+-/* Initialize the inode hash table. */
+-void
+-inode_init ()
+-{
+-  int n;
+-  for (n = 0; n < INOHSZ; n++)
+-    nodehash[n] = 0;
+-}
+-
+ /* Fetch inode INUM, set *NPP to the node structure;
+    gain one user reference and lock the node.  */
+ error_t
+@@ -82,15 +72,15 @@ diskfs_cached_lookup (ino_t inum, struct node **npp)
+   struct disknode *dn;
+ 
+   pthread_mutex_lock (&nodehash_lock);
+-  for (np = nodehash[INOHASH(inum)]; np; np = np->dn->hnext)
+-    if (np->cache_id == inum)
+-      {
+-	diskfs_nref (np);
+-	pthread_mutex_unlock (&nodehash_lock);
+-	pthread_mutex_lock (&np->lock);
+-	*npp = np;
+-	return 0;
+-      }
++  np = hurd_ihash_find (&nodehash, inum);
++  if (np != NULL)
++    {
++      diskfs_nref (np);
++      pthread_mutex_unlock (&nodehash_lock);
++      pthread_mutex_lock (&np->lock);
++      *npp = np;
++      return 0;
++    }
+ 
+   /* Format specific data for the new node.  */
+   dn = malloc (sizeof (struct disknode));
+@@ -112,15 +102,19 @@ diskfs_cached_lookup (ino_t inum, struct node **npp)
+   pthread_mutex_lock (&np->lock);
+ 
+   /* Put NP in NODEHASH.  */
+-  dn->hnext = nodehash[INOHASH(inum)];
+-  if (dn->hnext)
+-    dn->hnext->dn->hprevp = &dn->hnext;
+-  dn->hprevp = &nodehash[INOHASH(inum)];
+-  nodehash[INOHASH(inum)] = np;
+   diskfs_nref_light (np);
+-  nodehash_nr_items += 1;
+-
++  err = hurd_ihash_add (&nodehash, inum, np);
++#ifndef notyet
++  /* Fake locp.  */
++  dn->nodehash_locp = 1;
++#endif
+   pthread_mutex_unlock (&nodehash_lock);
++  if (err)
++    {
++      diskfs_drop_node (np);
++      free (dn);
++      return err;
++    }
+ 
+   /* Get the contents of NP off disk.  */
+   err = read_node (np);
+@@ -152,11 +146,9 @@ ifind (ino_t inum)
+   struct node *np;
+ 
+   pthread_mutex_lock (&nodehash_lock);
+-  for (np = nodehash[INOHASH(inum)]; np; np = np->dn->hnext)
++  np = hurd_ihash_find (&nodehash, inum);
++  if (np != NULL)
+     {
+-      if (np->cache_id != inum)
+-	continue;
+-
+       pthread_mutex_unlock (&nodehash_lock);
+       return np;
+     }
+@@ -186,7 +178,7 @@ void
+ diskfs_try_dropping_softrefs (struct node *np)
+ {
+   pthread_mutex_lock (&nodehash_lock);
+-  if (np->dn->hnext != NULL)
++  if (np->dn->nodehash_locp != NULL)
+     {
+       /* Check if someone reacquired a reference through the
+          nodehash.  */
+@@ -200,11 +192,12 @@ diskfs_try_dropping_softrefs (struct node *np)
+           return;
+         }
+ 
+-      *np->dn->hprevp = np->dn->hnext;
+-      if (np->dn->hnext)
+-        np->dn->hnext->dn->hprevp = np->dn->hprevp;
+-      np->dn->hnext = NULL;
+-      nodehash_nr_items -= 1;
++#if notyet
++      hurd_ihash_locp_remove (&nodehash, np->dn->nodehash_locp);
++#else
++      hurd_ihash_locp_remove (&nodehash, np->cache_id);
++#endif
++      np->dn->nodehash_locp = NULL;
+       diskfs_nrele_light (np);
+     }
+   pthread_mutex_unlock (&nodehash_lock);
+@@ -581,7 +574,6 @@ error_t
+ diskfs_node_iterate (error_t (*fun)(struct node *))
+ {
+   error_t err = 0;
+-  int n;
+   size_t num_nodes;
+   struct node *node, **node_list, **p;
+ 
+@@ -592,7 +584,7 @@ diskfs_node_iterate (error_t (*fun)(struct node *))
+      during processing (normally we delegate access to hash-table with
+      nodehash_lock, but we can't hold this while locking the
+      individual node locks).  */
+-  num_nodes = nodehash_nr_items;
++  num_nodes = nodehash.nr_items;
+ 
+   /* TODO This method doesn't scale beyond a few dozen nodes and should be
+      replaced.  */
+@@ -605,12 +597,12 @@ diskfs_node_iterate (error_t (*fun)(struct node *))
+     }
+ 
+   p = node_list;
+-  for (n = 0; n < INOHSZ; n++)
+-    for (node = nodehash[n]; node; node = node->dn->hnext)
+-      {
+-	*p++ = node;
+-	diskfs_nref (node);
+-      }
++  HURD_IHASH_ITERATE (&nodehash, value)
++    {
++      node = (struct node *) value;
++      *p++ = node;
++      diskfs_nref (node);
++    }
+ 
+   pthread_mutex_unlock (&nodehash_lock);
+ 
+-- 
+2.0.0.rc0
+
diff --git a/debian/patches/series b/debian/patches/series
index 179d45da..dc554e94 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -53,3 +53,4 @@ mach-defpager-protected-payload.patch
 0011-isofs-use-a-seperate-lock-to-protect-node_cache.patch
 0012-tmpfs-use-a-seperate-lock-to-protect-all_nodes.patch
 0013-libdiskfs-lock-less-reference-counting-of-nodes.patch
+0014-ext2fs-use-libihash-for-the-nodehash.patch