[hurd] 33/75: libdiskfs: use ihash for the node cache

[Samuel Thibault]

This is an automated email from the git hooks/post-receive script.

sthibault pushed a commit to branch dde
in repository hurd.

commit 52b5c7e8db6e6742dd6d7bf1548c6d33e149f59a
Author: Justus Winter <address@hidden>
Date:   Wed Jun 24 02:30:01 2015 +0200

    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;

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-hurd/hurd.git