xfs
[Top] [All Lists]

Re: [PATCH 4/5] libxfs: buffer cache hashing is suboptimal

To: Dave Chinner <david@xxxxxxxxxxxxx>, xfs@xxxxxxxxxxx
Subject: Re: [PATCH 4/5] libxfs: buffer cache hashing is suboptimal
From: Brian Foster <bfoster@xxxxxxxxxx>
Date: Thu, 12 Dec 2013 13:59:26 -0500
Delivered-to: xfs@xxxxxxxxxxx
In-reply-to: <1386832945-19763-5-git-send-email-david@xxxxxxxxxxxxx>
References: <1386832945-19763-1-git-send-email-david@xxxxxxxxxxxxx> <1386832945-19763-5-git-send-email-david@xxxxxxxxxxxxx>
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.1.0
On 12/12/2013 02:22 AM, Dave Chinner wrote:
> From: Dave Chinner <dchinner@xxxxxxxxxx>
> 
> The hashkey calculation is very simplistic,and throws away an amount
> of entropy that should be folded into the hash. The result is
> sub-optimal distribution across the hash tables. For example, with a
> default 512 entry table, phase 2 results in this:
> 
...
> Modify the hash to be something more workable - steal the linux
> kernel inode hash calculation and try that:
> 
...
> 
> Kinda says it all, really...
> 
> Signed-off-by: Dave Chinner <dchinner@xxxxxxxxxx>
> ---

Results look nice and the algorithm seems to match the kernel variant,
but what about the 32-bit alternate prime/cache line values? Safe to
leave out..?

Brian

>  include/cache.h |  4 +++-
>  libxfs/cache.c  |  7 +++++--
>  libxfs/rdwr.c   | 12 ++++++++++--
>  3 files changed, 18 insertions(+), 5 deletions(-)
> 
> diff --git a/include/cache.h b/include/cache.h
> index 76cb234..0a84c69 100644
> --- a/include/cache.h
> +++ b/include/cache.h
> @@ -66,7 +66,8 @@ typedef void (*cache_walk_t)(struct cache_node *);
>  typedef struct cache_node * (*cache_node_alloc_t)(cache_key_t);
>  typedef void (*cache_node_flush_t)(struct cache_node *);
>  typedef void (*cache_node_relse_t)(struct cache_node *);
> -typedef unsigned int (*cache_node_hash_t)(cache_key_t, unsigned int);
> +typedef unsigned int (*cache_node_hash_t)(cache_key_t, unsigned int,
> +                                       unsigned int);
>  typedef int (*cache_node_compare_t)(struct cache_node *, cache_key_t);
>  typedef unsigned int (*cache_bulk_relse_t)(struct cache *, struct list_head 
> *);
>  
> @@ -112,6 +113,7 @@ struct cache {
>       cache_node_compare_t    compare;        /* comparison routine */
>       cache_bulk_relse_t      bulkrelse;      /* bulk release routine */
>       unsigned int            c_hashsize;     /* hash bucket count */
> +     unsigned int            c_hashshift;    /* hash key shift */
>       struct cache_hash       *c_hash;        /* hash table buckets */
>       struct cache_mru        c_mrus[CACHE_MAX_PRIORITY + 1];
>       unsigned long long      c_misses;       /* cache misses */
> diff --git a/libxfs/cache.c b/libxfs/cache.c
> index 84d2860..dc69689 100644
> --- a/libxfs/cache.c
> +++ b/libxfs/cache.c
> @@ -25,6 +25,7 @@
>  #include <xfs/platform_defs.h>
>  #include <xfs/list.h>
>  #include <xfs/cache.h>
> +#include <xfs/libxfs.h>
>  
>  #define CACHE_DEBUG 1
>  #undef CACHE_DEBUG
> @@ -61,6 +62,7 @@ cache_init(
>       cache->c_misses = 0;
>       cache->c_maxcount = maxcount;
>       cache->c_hashsize = hashsize;
> +     cache->c_hashshift = libxfs_highbit32(hashsize);
>       cache->hash = cache_operations->hash;
>       cache->alloc = cache_operations->alloc;
>       cache->flush = cache_operations->flush;
> @@ -343,7 +345,7 @@ cache_node_get(
>       int                     priority = 0;
>       int                     purged = 0;
>  
> -     hashidx = cache->hash(key, cache->c_hashsize);
> +     hashidx = cache->hash(key, cache->c_hashsize, cache->c_hashshift);
>       hash = cache->c_hash + hashidx;
>       head = &hash->ch_list;
>  
> @@ -515,7 +517,8 @@ cache_node_purge(
>       struct cache_hash *     hash;
>       int                     count = -1;
>  
> -     hash = cache->c_hash + cache->hash(key, cache->c_hashsize);
> +     hash = cache->c_hash + cache->hash(key, cache->c_hashsize,
> +                                        cache->c_hashshift);
>       head = &hash->ch_list;
>       pthread_mutex_lock(&hash->ch_mutex);
>       for (pos = head->next, n = pos->next; pos != head;
> diff --git a/libxfs/rdwr.c b/libxfs/rdwr.c
> index 0219a08..0effb9a 100644
> --- a/libxfs/rdwr.c
> +++ b/libxfs/rdwr.c
> @@ -311,10 +311,18 @@ struct xfs_bufkey {
>       int                     nmaps;
>  };
>  
> +/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
> +#define GOLDEN_RATIO_PRIME   0x9e37fffffffc0001UL
> +#define CACHE_LINE_SIZE              64
>  static unsigned int
> -libxfs_bhash(cache_key_t key, unsigned int hashsize)
> +libxfs_bhash(cache_key_t key, unsigned int hashsize, unsigned int hashshift)
>  {
> -     return (((unsigned int)((struct xfs_bufkey *)key)->blkno) >> 5) % 
> hashsize;
> +     uint64_t        hashval = ((struct xfs_bufkey *)key)->blkno;
> +     uint64_t        tmp;
> +
> +     tmp = hashval ^ (GOLDEN_RATIO_PRIME + hashval) / CACHE_LINE_SIZE;
> +     tmp = tmp ^ ((tmp ^ GOLDEN_RATIO_PRIME) >> hashshift);
> +     return tmp % hashsize;
>  }
>  
>  static int
> 

<Prev in Thread] Current Thread [Next in Thread>