Re: [RFC] NUMA futex hashing

[Eric Dumazet <dada1@cosmosbay.com>]

On Tuesday 08 August 2006 09:07, Ravikiran G Thirumalai wrote:
> Current futex hash scheme is not the best for NUMA.   The futex hash table
> is an array of struct futex_hash_bucket, which is just a spinlock and a
> list_head -- this means multiple spinlocks on the same cacheline and on
> NUMA machines, on the same internode cacheline.  If futexes of two
> unrelated threads running on two different nodes happen to hash onto
> adjacent hash buckets, or buckets on the same internode cacheline, then we
> have the internode cacheline bouncing between nodes.
>
> Here is a simple scheme which maintains per-node hash tables for futexes.
>
> In this scheme, a private futex is assigned to the node id of the futex's
> KVA. The reasoning is, the futex KVA is allocated from the node as
> indicated by memory policy set by the process, and that should be a good
> 'home node' for that futex.  Of course this helps workloads where all the
> threads of a process are bound to the same node, but it seems reasonable to
> run all threads of a process on the same node.
>
> A shared futex is assigned a home node based on jhash2 itself.  Since inode
> and offset are used as the key, the same inode offset is used to arrive at
> the home node of a shared futex.  This distributes private futexes across
> all nodes.
>
> Comments? Suggestions? Particularly regarding shared futexes.  Any policy
> suggestions?
>

Your patch seems fine, but I have one comment.

For non NUMA machine, we would have one useless indirection to get the 
futex_queues pointer.

static struct futex_hash_bucket *futex_queues[1];

I think it is worth to redesign your patch so that this extra-indirection is 
needed only for NUMA machines.

#if defined(CONFIG_NUMA)
static struct futex_hash_bucket *futex_queues[MAX_NUMNODES];
#define FUTEX_QUEUES(nodeid, hash) \
	&futex_queues[nodeid][hash & ((1 << FUTEX_HASHBITS)-1)];
#else
static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
# define FUTEX_QUEUES(nodeid, hash) \
     &futex_queues[hash & ((1 << FUTEX_HASHBITS)-1)];
#endif

Thank you

> Thanks,
> Kiran
>
> Note: This patch needs to have kvaddr_to_nid() reintroduced.  This was
> taken out in git commit 9f3fd602aef96c2a490e3bfd669d06475aeba8d8
>
> Index: linux-2.6.18-rc3/kernel/futex.c
> ===================================================================
> --- linux-2.6.18-rc3.orig/kernel/futex.c	2006-08-02 12:11:34.000000000
> -0700 +++ linux-2.6.18-rc3/kernel/futex.c	2006-08-02 16:48:47.000000000
> -0700 @@ -137,20 +137,35 @@ struct futex_hash_bucket {
>         struct list_head       chain;
>  };
>
> -static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
> +static struct futex_hash_bucket *futex_queues[MAX_NUMNODES] __read_mostly;
>
>  /* Futex-fs vfsmount entry: */
>  static struct vfsmount *futex_mnt;
>
>  /*
>   * We hash on the keys returned from get_futex_key (see below).
> + * With NUMA aware futex hashing, we have per-node hash tables.
> + * We determine the home node of a futex based on the KVA -- if the futex
> + * is a private futex.  For shared futexes, we use  jhash2 itself on the
> + * futex_key to arrive at a home node.
>   */
>  static struct futex_hash_bucket *hash_futex(union futex_key *key)
>  {
> +	int nodeid;
>  	u32 hash = jhash2((u32*)&key->both.word,
>  			  (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
>  			  key->both.offset);
> -	return &futex_queues[hash & ((1 << FUTEX_HASHBITS)-1)];
> +	if (key->both.offset & 0x1) {
> +		/*
> +		 * Shared futex: Use any of the 'possible' nodes as home node.
> +		 */
> +		nodeid = hash & (MAX_NUMNODES -1);
> +		BUG_ON(!node_possible(nodeid));
> +	} else
> +		/* Private futex */
> +		nodeid = kvaddr_to_nid(key->both.ptr);
> +
> +	return &futex_queues[nodeid][hash & ((1 << FUTEX_HASHBITS)-1)];
>  }
>
>  /*
> @@ -1909,13 +1924,25 @@ static int __init init(void)
>  {
>  	unsigned int i;
>
> +	int nid;
> +
> +	for_each_node(nid)
> +	{
> +		futex_queues[nid] = kmalloc_node(
> +					(sizeof(struct futex_hash_bucket) *
> +					(1 << FUTEX_HASHBITS)),
> +					GFP_KERNEL, nid);
> +		if (!futex_queues[nid])
> +			panic("futex_init: Allocation of multi-node futex_queues failed");
> +		for (i = 0; i < (1 << FUTEX_HASHBITS); i++) {
> +			INIT_LIST_HEAD(&futex_queues[nid][i].chain);
> +			spin_lock_init(&futex_queues[nid][i].lock);
> +		}
> +	}
> +
>  	register_filesystem(&futex_fs_type);
>  	futex_mnt = kern_mount(&futex_fs_type);
>
> -	for (i = 0; i < ARRAY_SIZE(futex_queues); i++) {
> -		INIT_LIST_HEAD(&futex_queues[i].chain);
> -		spin_lock_init(&futex_queues[i].lock);
> -	}
>  	return 0;
>  }
>  __initcall(init);
>
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/