Re: [PATCH v1] hash: add tsx support for cuckoo hash

["Shen, Wei1" <wei1.shen@intel.com>]

Thanks Pablo for reviewing the patch. I just sent out v2 patch. It fixed those problems you found and also removed the RTE_HASH_KEY_FLAG_MOVED flag used in v1, which would cause problem when key deletion happens (current key deletion doesn’t restore keys back to its primary bucket). Now it just swaps current/alt sig when a push happens, as make_space_bucket does.

There is still some line too long checkpatch warning, but fixing those would hurt code readability rather than improving them. So I left as it.

Thanks.
-- 
Best,

Wei Shen.

On 6/15/16, 4:45 PM, "De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com> wrote:

Hi Wei,

> -----Original Message-----
> From: Shen, Wei1
> Sent: Friday, May 06, 2016 9:05 PM
> To: dev@dpdk.org
> Cc: De Lara Guarch, Pablo; Maciocco, Christian; Shen, Wei1; Gobriel, Sameh
> Subject: [PATCH v1] hash: add tsx support for cuckoo hash
> 
> Introduced Intel TSX-enabled scalable multi-writer Cuckoo hash
> insertion.
> 
> This patch introduced scalable multi-writer Cuckoo Hash insertion
> based on a split Cuckoo Search and Move operation using Intel
> TSX. It can do scalable hash insertion with 22 cores with little
> performance loss and negligible TSX abortion rate.
> 
> * Added an extra rte_hash flag definition to switch default
>   single writer Cuckoo Hash behavior to multiwriter.
> 
> * Added a make_space_insert_bfs_mw() function to do split Cuckoo
>   search in BFS order.
> 
> * Added tsx_cuckoo_move_insert() to do Cuckoo move in Intel TSX
>   protected manner.
> 
> * Added test_hash_multiwriter() as test case for multi-writer
>   Cuckoo Hash.
> 
> Signed-off-by: Shen Wei <wei1.shen@intel.com>
> Signed-off-by: Sameh Gobriel <sameh.gobriel@intel.com>
> ---
>  app/test/Makefile                 |   1 +
>  app/test/test_hash_multiwriter.c  | 272
> ++++++++++++++++++++++++++++++++++++++
>  lib/librte_hash/rte_cuckoo_hash.c | 228 ++++++++++++++++++++++++++++--
> --
>  lib/librte_hash/rte_hash.h        |   3 +
>  4 files changed, 480 insertions(+), 24 deletions(-)
>  create mode 100644 app/test/test_hash_multiwriter.c
> 

[...]

> diff --git a/app/test/test_hash_multiwriter.c
> b/app/test/test_hash_multiwriter.c
> new file mode 100644
> index 0000000..bdb9840
> --- /dev/null
> +++ b/app/test/test_hash_multiwriter.c
> @@ -0,0 +1,272 @@

[...]

> +
> +	if (duplicated_keys > 0) {
> +		printf("%d key duplicated\n", duplicated_keys);
> +		goto err3;
> +	}
> +
> +	if (lost_keys > 0) {
> +		printf("%d key lost\n", lost_keys);
> +		goto err3;
> +	}
> +
> +	printf("No key corruped during multiwriter insertion.\n");

Typo: corrupted

> +
> +	unsigned long long int cycles_per_insertion =
> +		rte_atomic64_read(&gcycles)/
> +		rte_atomic64_read(&ginsertions);
> +
> +	printf(" cycles per insertion: %llu\n", cycles_per_insertion);
> +
> +	rte_free(tbl_multiwriter_test_params.found);
> +	rte_free(tbl_multiwriter_test_params.keys);
> +	rte_hash_free(handle);
> +	return 0;
> +
> +err3:
> +	rte_free(tbl_multiwriter_test_params.found);
> +err2:
> +	rte_free(tbl_multiwriter_test_params.keys);
> +err1:
> +	rte_hash_free(handle);
> +	return -1;
> +}
> +
> +static int
> +test_hash_multiwriter_main(void)
> +{
> +	int r = -1;
> +
> +	if (rte_lcore_count() == 1) {
> +		printf(
> +			"More than one lcores are required to do multiwriter
> test\n");

Typo: More than one lcore is required to do multiwriter test.

> +		return r;
> +	}
> +
> +	if (!rte_tm_supported()) {
> +		printf(
> +			"Hardware transactional memory (lock elision) is NOT
> supported\n");
> +		return r;
> +	}
> +
> +	printf("Hardware transactional memory (lock elision) is
> supported\n");
> +
> +	setlocale(LC_NUMERIC, "");
> +
> +	r = test_hash_multiwriter();
> +
> +	return r;
> +}
> +
> +
> +static struct test_command hash_scaling_cmd = {
> +	.command = "hash_multiwriter_autotest",
> +	.callback = test_hash_multiwriter_main,
> +};
> +
> +REGISTER_TEST_COMMAND(hash_scaling_cmd);
> diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> b/lib/librte_hash/rte_cuckoo_hash.c
> index 7b7d1f8..5a01f51 100644
> --- a/lib/librte_hash/rte_cuckoo_hash.c
> +++ b/lib/librte_hash/rte_cuckoo_hash.c

[...]

> +/* Shift buckets along cuckoo_path and fill the path head with new entry */
> +static inline int
> +tsx_cuckoo_move_insert(const struct rte_hash *h, struct queue_node *leaf,
> +		       uint32_t leaf_slot, hash_sig_t sig,
> +		       hash_sig_t alt_hash, uint32_t new_idx, uint8_t flag)
> +{
> +	#define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4

Could you move this up and indent it to the left?

> +	int32_t try = 0;

This variable (try) should not have any negative number, so you can change it to unsigned.

> +	uint32_t prev_alt_bkt_idx;
> +	unsigned status;
> +
> +	struct queue_node *prev_node, *curr_node = leaf;
> +	struct rte_hash_bucket *prev_bkt, *curr_bkt = leaf->bkt;
> +	uint32_t prev_slot, curr_slot = leaf_slot;
> +
> +	int cuckoo_path_len = 0;

This variable is not being used. It gets incremented below,
but is not used in anything useful, as far as I can see.
If you are not using it, then remove it.

> +
> +	while (try < 10) {

Magic number. Define a macro with this number instead.

> +		status = rte_xbegin();
> +		if (likely(status == RTE_XBEGIN_STARTED)) {
> +			while (likely(curr_node->prev != NULL)) {
> +				prev_node = curr_node->prev;
> +				prev_bkt = prev_node->bkt;
> +				prev_slot = curr_node->prev_slot;
> +
> +				prev_alt_bkt_idx
> +					= prev_bkt->signatures[prev_slot].alt
> +					& h->bucket_bitmask;
> +
> +				if (unlikely(&h->buckets[prev_alt_bkt_idx]
> +					     != curr_bkt)) {
> +
> 	rte_xabort(RTE_XABORT_CUCKOO_PATH_INVALIDED);
> +				}
> +
> +				curr_bkt->signatures[curr_slot]
> +					= prev_bkt->signatures[prev_slot];
> +				curr_bkt->key_idx[curr_slot]
> +					= prev_bkt->key_idx[prev_slot];
> +				curr_bkt->flag[curr_slot]
> +					= RTE_HASH_KEY_FLAG_MOVED;
> +
> +				curr_slot = prev_slot;
> +				curr_node = prev_node;
> +				curr_bkt = curr_node->bkt;
> +
> +				cuckoo_path_len++;
> +			}
> +
> +			curr_bkt->signatures[curr_slot].current = sig;
> +			curr_bkt->signatures[curr_slot].alt = alt_hash;
> +			curr_bkt->key_idx[curr_slot] = new_idx;
> +			curr_bkt->flag[curr_slot] = flag;
> +
> +			rte_xend();
> +
> +			return 0;
> +		}
> +
> +		/* If we abort we give up this cuckoo path. */
> +		try++;
> +		rte_pause();
> +		continue;

Is this continue necessary? It is at the end of a while loop, so it does not look it is.

> +	}
> +
> +	return -1;
> +}
> +
> +/* Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
> + * Cuckoo
> + */
> +static inline int
> +make_space_insert_bfs_mw(const struct rte_hash *h, struct
> rte_hash_bucket *bkt,
> +			 hash_sig_t sig, hash_sig_t alt_hash,
> +			 uint32_t new_idx, uint8_t flag)
> +{
> +	int i;

Unsigned i;

> +	struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];
> +	struct queue_node *tail, *head;
> +	struct rte_hash_bucket *curr_bkt, *alt_bkt;
> +
> +	tail = queue;
> +	head = queue + 1;
> +	tail->bkt = bkt;
> +	tail->prev = NULL;
> +	tail->prev_slot = -1;
> +
> +	/* Cuckoo Search */
> +	while (likely(tail != head && head <
> +		      queue + RTE_HASH_BFS_QUEUE_MAX_LEN - 4)) {
> +
> +		curr_bkt = tail->bkt;
> +		for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
> +			if (curr_bkt->signatures[i].sig == NULL_SIGNATURE) {
> +				if (likely(tsx_cuckoo_move_insert(h, tail, i,
> +					sig, alt_hash, new_idx, flag) == 0))

Add extra indentation here, to distinguish between the conditional
and the body (extra indentation to the right in "sig, alt_hash...").

> +					return 0;
> +			}
> +
> +			/* Make sure current key's not already in its
> +			 * secondary bucket.
> +			 */
> +			if (curr_bkt->flag[i] ==
> RTE_HASH_KEY_FLAG_UNMOVED) {
> +				/* Enqueue new node and keep prev node
> info */
> +				alt_bkt =
> +					&(h->buckets[curr_bkt-
> >signatures[i].alt
> +						     & h->bucket_bitmask]);
> +				head->bkt = alt_bkt;
> +				head->prev = tail;
> +				head->prev_slot = i;
> +				head++;
> +			}
> +		}
> +		tail++;
> +	}
> +
> +	return -ENOSPC;
> +}
> +
>  /*
>   * Function called to enqueue back an index in the cache/ring,
>   * as slot has not being used and it can be used in the
> @@ -712,30 +852,70 @@ __rte_hash_add_key_with_hash(const struct
> rte_hash *h, const void *key,
>  	rte_memcpy(new_k->key, key, h->key_len);
>  	new_k->pdata = data;
> 
> -	/* Insert new entry is there is room in the primary bucket */
> -	for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
> -		/* Check if slot is available */
> -		if (likely(prim_bkt->signatures[i].sig == NULL_SIGNATURE)) {
> -			prim_bkt->signatures[i].current = sig;
> -			prim_bkt->signatures[i].alt = alt_hash;
> -			prim_bkt->key_idx[i] = new_idx;
> -			return new_idx - 1;
> +	unsigned status;
> +	int32_t try = 0;
> +
> +	while (try < 10) {


Same comments about "unsigned try" and magic numbers.

> +		status = rte_xbegin();

The following code should only be executed if RTM is supported,
otherwise, there will be an illegal instruction.

> +		if (likely(status == RTE_XBEGIN_STARTED)) {
> +			/* Insert new entry is there is room in the primary
> +			 * bucket.

Typo: Insert new entry if there is room...

> +			 */
> +			for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
> +				/* Check if slot is available */
> +				if (likely(prim_bkt->signatures[i].sig
> +					   == NULL_SIGNATURE)) {

Extra indentation to the right, as said above.

> +					prim_bkt->signatures[i].current = sig;
> +					prim_bkt->signatures[i].alt =
> alt_hash;
> +					prim_bkt->key_idx[i] = new_idx;
> +					prim_bkt->flag[i] =
> +
> 	RTE_HASH_KEY_FLAG_UNMOVED;
> +					break;
> +				}
> +			}
> +			rte_xend();
> +
> +			if (i != RTE_HASH_BUCKET_ENTRIES)
> +				return new_idx - 1;
> +
> +			break;
> +
> +		} else {
> +			/* If we abort we give up this cuckoo path. */
> +			try++;
> +			rte_pause();
> +			continue;

Same as above, unnecessary continue?

>  		}
>  	}
> 
>  	/* Primary bucket is full, so we need to make space for new entry */