Justus Winter, le Thu 29 May 2014 18:41:04 +0200, a écrit :
> 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.
Ack.
> * 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
>
--
Samuel
We are Pentium of Borg. Division is futile. You will be approximated.
(seen in someone's .signature)
