DPDK patches and discussions
 help / color / mirror / Atom feed
From: "De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com>
To: "Shen, Wei1" <wei1.shen@intel.com>, "dev@dpdk.org" <dev@dpdk.org>
Cc: "Maciocco, Christian" <christian.maciocco@intel.com>,
	"Gobriel, Sameh" <sameh.gobriel@intel.com>
Subject: Re: [dpdk-dev] [PATCH v1] hash: add tsx support for cuckoo hash
Date: Wed, 15 Jun 2016 23:45:35 +0000	[thread overview]
Message-ID: <E115CCD9D858EF4F90C690B0DCB4D8973C962891@IRSMSX108.ger.corp.intel.com> (raw)
In-Reply-To: <1462565102-15312-1-git-send-email-wei1.shen@intel.com>

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 */

  parent reply	other threads:[~2016-06-15 23:45 UTC|newest]

Thread overview: 12+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-05-06 20:05 Shen Wei
2016-05-07  4:56 ` Stephen Hemminger
2016-05-09 16:51   ` Shen, Wei1
2016-06-10 11:09     ` De Lara Guarch, Pablo
2016-06-15 23:45 ` De Lara Guarch, Pablo [this message]
2016-06-16  4:58   ` Shen, Wei1
2016-06-16  4:52 ` [dpdk-dev] [PATCH v2] rte_hash: add scalable multi-writer insertion w/ Intel TSX Wei Shen
2016-06-16 12:14   ` Ananyev, Konstantin
2016-06-16 22:14   ` [dpdk-dev] [PATCH v3] " Wei Shen
2016-06-16 22:14     ` Wei Shen
2016-06-16 22:22       ` De Lara Guarch, Pablo
2016-06-24 14:09         ` Thomas Monjalon

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=E115CCD9D858EF4F90C690B0DCB4D8973C962891@IRSMSX108.ger.corp.intel.com \
    --to=pablo.de.lara.guarch@intel.com \
    --cc=christian.maciocco@intel.com \
    --cc=dev@dpdk.org \
    --cc=sameh.gobriel@intel.com \
    --cc=wei1.shen@intel.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).