[PATCH 6/6] libdiskfs: use a hash table for the name cache

[Justus Winter]

Previously, name cache lookup operation completed in O(n) time.  This
means that making the cache too large would decrease the performance.
Therefore it was required to tune the size.

Implement the name cache using a hash table.

We use buckets of a fixed size.  We approximate the least-frequently
used cache algorithm by counting the number of lookups using
saturating arithmetic in the two lowest bits of the pointer to the
name.  Using this strategy we achieve a constant worst-case lookup and
insertion time.

Since we are not bound by the size of the cache anymore, increase its
size from 200 to 1024.

* libdiskfs/name-cache.c: Implement the name cache using a hash table.
(diskfs_enter_lookup_cache): Change accordingly.
(diskfs_purge_lookup_cache): Likewise.
(diskfs_check_lookup_cache): Likewise.  Also, hard code a
cache miss for the parent of the root directory and merge unlocking
and releasing of node references.
---
 libdiskfs/name-cache.c | 374 ++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 274 insertions(+), 100 deletions(-)

diff --git a/libdiskfs/name-cache.c b/libdiskfs/name-cache.c
index 25b5d0d..d8f86b1 100644
--- a/libdiskfs/name-cache.c
+++ b/libdiskfs/name-cache.c
@@ -1,6 +1,6 @@
 /* Directory name lookup caching
 
-   Copyright (C) 1996, 1997, 1998 Free Software Foundation, Inc.
+   Copyright (C) 1996, 1997, 1998, 2014 Free Software Foundation, Inc.
    Written by Michael I. Bushnell, p/BSG, & Miles Bader.
 
    This file is part of the GNU Hurd.
@@ -20,118 +20,290 @@
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA. */
 
 #include "priv.h"
+#include <assert.h>
 #include <string.h>
-#include <cacheq.h>
 
-/* Maximum number of names to cache at once */
-#define MAXCACHE 200
+/* The name cache is implemented using a hash table.
 
-/* Maximum length of file name we bother caching */
-#define CACHE_NAME_LEN 100
+   We use buckets of a fixed size.  We approximate the
+   least-frequently used cache algorithm by counting the number of
+   lookups using saturating arithmetic in the two lowest bits of the
+   pointer to the name.  Using this strategy we achieve a constant
+   worst-case lookup and insertion time.  */
 
-/* Cache entry */
-struct lookup_cache
+/* Number of buckets.  Must be a power of two. */
+#define CACHE_SIZE     256
+
+/* Entries per bucket.  */
+#define BUCKET_SIZE    4
+
+/* A mask for fast binary modulo.  */
+#define CACHE_MASK     (CACHE_SIZE - 1)
+
+/* Cache bucket with BUCKET_SIZE entries.
+
+   The layout of the bucket is chosen so that it will be straight
+   forward to use vector operations in the future.  */
+struct cache_bucket
 {
-  struct cacheq_hdr hdr;
+  /* Name of the node NODE_CACHE_ID in the directory DIR_CACHE_ID.  If
+     NULL, the entry is unused.  */
+  unsigned long name[BUCKET_SIZE];
 
-  /* Used to indentify nodes to the fs dependent code.  0 for NODE_CACHE_ID
-     means a `negative' entry -- recording that there's definitely no node with
-     this name.  */
-  ino64_t dir_cache_id, node_cache_id;
+  /* The key.  */
+  unsigned long key[BUCKET_SIZE];
 
-  /* Name of the node NODE_CACHE_ID in the directory DIR_CACHE_ID.  Entries
-     with names too long to fit in this buffer aren't cached at all.  */
-  char name[CACHE_NAME_LEN];
+  /* Used to indentify nodes to the fs dependent code.  */
+  ino64_t dir_cache_id[BUCKET_SIZE];
 
-  /* Strlen of NAME.  If this is zero, it's an unused entry. */
-  size_t name_len;
+  /* 0 for NODE_CACHE_ID means a `negative' entry -- recording that
+     there's definitely no node with this name.  */
+  ino64_t node_cache_id[BUCKET_SIZE];
 };
 
-/* The contents of the cache in no particular order */
-static struct cacheq lookup_cache = { sizeof (struct lookup_cache) };
+/* The cache.  */
+static struct cache_bucket name_cache[CACHE_SIZE];
 
-static pthread_spinlock_t cache_lock = PTHREAD_SPINLOCK_INITIALIZER;
+/* Protected by this lock.  */
+static pthread_mutex_t cache_lock = PTHREAD_MUTEX_INITIALIZER;
 
-/* If there's an entry for NAME, of length NAME_LEN, in directory DIR in the
-   cache, return its entry, otherwise 0.  CACHE_LOCK must be held.  */
-static struct lookup_cache *
-find_cache (struct node *dir, const char *name, size_t name_len)
+/* Given VALUE, return the char pointer.  */
+static inline char *
+charp (unsigned long value)
 {
-  struct lookup_cache *c;
-  int i;
-
-  /* Search the list.  All unused entries are contiguous at the end of the
-     list, so we can stop searching when we see the first one.  */
-  for (i = 0, c = lookup_cache.mru;
-       c && c->name_len;
-       c = c->hdr.next, i++)
-    if (c->name_len == name_len
-       && c->dir_cache_id == dir->cache_id
-       && c->name[0] == name[0] && strcmp (c->name, name) == 0)
-      return c;
+  return (char *) (value & ~3L);
+}
 
-  return 0;
+/* Given VALUE, return the approximation of use frequency.  */
+static inline unsigned long
+frequ (unsigned long value)
+{
+  return value & 3;
 }
 
-/* Node NP has just been found in DIR with NAME.  If NP is null, that
-   means that this name has been confirmed as absent in the directory. */
-void
-diskfs_enter_lookup_cache (struct node *dir, struct node *np, const char *name)
+/* Add an entry in the Ith slot of the given bucket.  If there is a
+   value there, remove it first.  */
+static inline void
+add_entry (struct cache_bucket *b, int i,
+          const char *name, unsigned long key,
+          ino64_t dir_cache_id, ino64_t node_cache_id)
 {
-  struct lookup_cache *c;
-  size_t name_len = strlen (name);
+  if (b->name[i])
+    free (charp (b->name[i]));
 
-  if (name_len > CACHE_NAME_LEN - 1)
+  b->name[i] = (unsigned long) strdup (name);
+  assert ((b->name[i] & 3) == 0);
+  if (b->name[i] == 0)
     return;
 
-  pthread_spin_lock (&cache_lock);
+  b->key[i] = key;
+  b->dir_cache_id[i] = dir_cache_id;
+  b->node_cache_id[i] = node_cache_id;
+}
 
-  if (lookup_cache.length == 0)
-    /* There should always be an lru_cache; this being zero means that the
-       cache hasn't been initialized yet.  Do so.  */
-    cacheq_set_length (&lookup_cache, MAXCACHE);
+/* Remove the entry in the Ith slot of the given bucket.  */
+static inline void
+remove_entry (struct cache_bucket *b, int i)
+{
+  if (b->name[i])
+    free (charp (b->name[i]));
+  b->name[i] = 0;
+}
 
-  /* See if there's an old entry for NAME in DIR.  If not, replace the least
-     recently used entry.  */
-  c = find_cache (dir, name, name_len) ?: lookup_cache.lru;
+/* Check if the entry in the Ith slot of the given bucket is
+   valid.  */
+static inline int
+valid_entry (struct cache_bucket *b, int i)
+{
+  return b->name[i] != 0;
+}
+
+/* This is the Murmur3 hash algorithm.  */
+
+#define FORCE_INLINE inline __attribute__((always_inline))
+
+inline uint32_t rotl32 ( uint32_t x, int8_t r )
+{
+  return (x << r) | (x >> (32 - r));
+}
 
-  /* Fill C with the new entry.  */
-  c->dir_cache_id = dir->cache_id;
-  c->node_cache_id = np ? np->cache_id : 0;
-  strcpy (c->name, name);
-  c->name_len = name_len;
+#define ROTL32(x,y)     rotl32(x,y)
 
-  /* Now C becomes the MRU entry!  */
-  cacheq_make_mru (&lookup_cache, c);
+/* Block read - if your platform needs to do endian-swapping or can
+   only handle aligned reads, do the conversion here.  */
 
-  pthread_spin_unlock (&cache_lock);
+FORCE_INLINE uint32_t getblock32 ( const uint32_t * p, int i )
+{
+  return p[i];
+}
+
+/* Finalization mix - force all bits of a hash block to avalanche.  */
+
+FORCE_INLINE uint32_t fmix32 ( uint32_t h )
+{
+  h ^= h >> 16;
+  h *= 0x85ebca6b;
+  h ^= h >> 13;
+  h *= 0xc2b2ae35;
+  h ^= h >> 16;
+
+  return h;
+}
+
+/* The Murmur3 hash function.  */
+void MurmurHash3_x86_32 ( const void * key, int len,
+                          uint32_t seed, void * out )
+{
+  const uint8_t * data = (const uint8_t*)key;
+  const int nblocks = len / 4;
+
+  uint32_t h1 = seed;
+
+  const uint32_t c1 = 0xcc9e2d51;
+  const uint32_t c2 = 0x1b873593;
+
+  /* body */
+
+  const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
+
+  for(int i = -nblocks; i; i++)
+  {
+    uint32_t k1 = getblock32(blocks,i);
+
+    k1 *= c1;
+    k1 = ROTL32(k1,15);
+    k1 *= c2;
+
+    h1 ^= k1;
+    h1 = ROTL32(h1,13);
+    h1 = h1*5+0xe6546b64;
+  }
+
+  /* tail */
+
+  const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
+
+  uint32_t k1 = 0;
+
+  switch(len & 3)
+  {
+  case 3: k1 ^= tail[2] << 16;
+  case 2: k1 ^= tail[1] << 8;
+  case 1: k1 ^= tail[0];
+          k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
+  };
+
+  /* finalization */
+
+  h1 ^= len;
+
+  h1 = fmix32(h1);
+
+  *(uint32_t*)out = h1;
 }
 
-/* Purge all references in the cache to NP as a node inside
-   directory DP. */
-void
-diskfs_purge_lookup_cache (struct node *dp, struct node *np)
+/* If there is no best candidate to replace, pick any.  We approximate
+   any by picking the slot depicted by REPLACE, and increment REPLACE
+   then.  */
+static int replace;
+
+/* Lookup (DIR_CACHE_ID, NAME, KEY) in the cache.  If it is found,
+   return 1 and set BUCKET and INDEX to the item.  Otherwise, return 0
+   and set BUCKET and INDEX to the slot where the item should be
+   inserted.  */
+static inline int
+lookup (ino64_t dir_cache_id, const char *name, unsigned long key,
+       struct cache_bucket **bucket, int *index)
 {
-  struct lookup_cache *c, *next;
+  struct cache_bucket *b = *bucket = &name_cache[key & CACHE_MASK];
+  unsigned long best = 3;
+  int i;
 
-  pthread_spin_lock (&cache_lock);
-  for (c = lookup_cache.mru; c; c = next)
+  for (i = 0; i < BUCKET_SIZE; i++)
     {
-      /* Save C->hdr.next, since we may move C from this position. */
-      next = c->hdr.next;
+      unsigned long f = frequ (b->name[i]);
+
+      if (valid_entry (b, i)
+         && b->key[i] == key
+         && b->dir_cache_id[i] == dir_cache_id
+         && strcmp (charp (b->name[i]), name) == 0)
+       {
+         if (f < 3)
+           b->name[i] += 1;
+
+         *index = i;
+         return 1;
+       }
 
-      if (c->name_len
-         && c->dir_cache_id == dp->cache_id
-         && c->node_cache_id == np->cache_id)
+      /* Keep track of the replacement candidate.  */
+      if (f < best)
        {
-         c->name_len = 0;
-         cacheq_make_lru (&lookup_cache, c); /* Use C as the next free
-                                                entry. */
+         best = f;
+         *index = i;
        }
     }
-  pthread_spin_unlock (&cache_lock);
+
+  /* If there was no entry with a lower use frequency, just replace
+     any entry.  */
+  if (best == 3)
+    {
+      *index = replace;
+      replace = (replace + 1) & (BUCKET_SIZE - 1);
+    }
+
+  return 0;
+}
+
+/* Hash the directory cache_id and the name.  */
+static inline unsigned long
+hash (ino64_t dir_cache_id, const char *name)
+{
+  unsigned long h;
+  MurmurHash3_x86_32 (&dir_cache_id, sizeof dir_cache_id, 0, &h);
+  MurmurHash3_x86_32 (name, strlen (name), h, &h);
+  return h;
+}
+
+/* Node NP has just been found in DIR with NAME.  If NP is null, that
+   means that this name has been confirmed as absent in the directory. */
+void
+diskfs_enter_lookup_cache (struct node *dir, struct node *np, const char *name)
+{
+  unsigned long key = hash (dir->cache_id, name);
+  ino64_t value = np ? np->cache_id : 0;
+  struct cache_bucket *bucket;
+  int i = 0, found;
+
+  pthread_mutex_lock (&cache_lock);
+  found = lookup (dir->cache_id, name, key, &bucket, &i);
+  if (! found)
+    add_entry (bucket, i, name, key, dir->cache_id, value);
+  else
+    if (bucket->node_cache_id[i] != value)
+      bucket->node_cache_id[i] = value;
+
+  pthread_mutex_unlock (&cache_lock);
 }
 
+/* Purge all references in the cache to NP as a node inside
+   directory DP. */
+void
+diskfs_purge_lookup_cache (struct node *dp, struct node *np)
+{
+  int i;
+  struct cache_bucket *b;
+
+  pthread_mutex_lock (&cache_lock);
+
+  for (b = &name_cache[0]; b < &name_cache[CACHE_SIZE]; b++)
+    for (i = 0; i < BUCKET_SIZE; i++)
+      if (valid_entry (b, i)
+         && b->dir_cache_id[i] == dp->cache_id
+         && b->node_cache_id[i] == np->cache_id)
+       remove_entry (b, i);
+
+  pthread_mutex_unlock (&cache_lock);
+}
 
 /* Scan the cache looking for NAME inside DIR.  If we don't know
    anything entry at all, then return 0.  If the entry is confirmed to
@@ -140,27 +312,28 @@ diskfs_purge_lookup_cache (struct node *dp, struct node 
*np)
 struct node *
 diskfs_check_lookup_cache (struct node *dir, const char *name)
 {
-  struct lookup_cache *c;
-
-  pthread_spin_lock (&cache_lock);
-
-  c = find_cache (dir, name, strlen (name));
-  if (c)
+  unsigned long key = hash (dir->cache_id, name);
+  int lookup_parent = name[0] == '.' && name[1] == '.' && name[2] == '\0';
+  struct cache_bucket *bucket;
+  int i, found;
+
+  if (lookup_parent && dir == diskfs_root_node)
+    /* This is outside our file system, return cache miss.  */
+    return NULL;
+
+  pthread_mutex_lock (&cache_lock);
+  found = lookup (dir->cache_id, name, key, &bucket, &i);
+  if (found)
     {
-      int id = c->node_cache_id;
-
-      cacheq_make_mru (&lookup_cache, c); /* Record C as recently used.  */
+      ino64_t id = bucket->node_cache_id[i];
+      pthread_mutex_unlock (&cache_lock);
 
       if (id == 0)
        /* A negative cache entry.  */
-       {
-         pthread_spin_unlock (&cache_lock);
-         return (struct node *)-1;
-       }
+       return (struct node *) -1;
       else if (id == dir->cache_id)
        /* The cached node is the same as DIR.  */
        {
-         pthread_spin_unlock (&cache_lock);
          diskfs_nref (dir);
          return dir;
        }
@@ -170,9 +343,7 @@ diskfs_check_lookup_cache (struct node *dir, const char 
*name)
          struct node *np;
          error_t err;
 
-         pthread_spin_unlock (&cache_lock);
-
-         if (name[0] == '.' && name[1] == '.' && name[2] == '\0')
+         if (lookup_parent)
            {
              pthread_mutex_unlock (&dir->lock);
              err = diskfs_cached_lookup (id, &np);
@@ -181,14 +352,18 @@ diskfs_check_lookup_cache (struct node *dir, const char 
*name)
              /* In the window where DP was unlocked, we might
                 have lost.  So check the cache again, and see
                 if it's still there; if so, then we win. */
-             c = find_cache (dir, "..", 2);
-             if (!c || c->node_cache_id != id)
+             pthread_mutex_lock (&cache_lock);
+             found = lookup (dir->cache_id, name, key, &bucket, &i);
+             if (! found
+                 || ! bucket->node_cache_id[i] != id)
                {
+                 pthread_mutex_unlock (&cache_lock);
+
                  /* Lose */
-                 pthread_mutex_unlock (&np->lock);
-                 diskfs_nrele (np);
+                 diskfs_nput (np);
                  return 0;
                }
+             pthread_mutex_unlock (&cache_lock);
            }
          else
            err = diskfs_cached_lookup (id, &np);
@@ -196,7 +371,6 @@ diskfs_check_lookup_cache (struct node *dir, const char 
*name)
        }
     }
 
-  pthread_spin_unlock (&cache_lock);
-
+  pthread_mutex_unlock (&cache_lock);
   return 0;
 }
-- 
2.0.0.rc2