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

[Brian Foster <bfoster@redhat.com>]

On 12/12/2013 02:22 AM, Dave Chinner wrote:
> From: Dave Chinner <dchinner@redhat.com>
> 
> 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@redhat.com>
> ---

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
> 

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs