From 52b5c7e8db6e6742dd6d7bf1548c6d33e149f59a 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: 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/node-cache.c | 107 +++++++++++++++++++++++--------------------------
1 file changed, 51 insertions(+), 56 deletions(-)
(limited to 'libdiskfs/node-cache.c')
diff --git a/libdiskfs/node-cache.c b/libdiskfs/node-cache.c
index a76474af..ee7e6fdb 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 . */
-#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
-/* 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;
--
cgit v1.2.3