Hi Wei,
> -----Original Message-----
> From: Shen, Wei1
> Sent: Friday, May 06, 2016 9:05 PM
> To: dev at 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 at intel.com>
> Signed-off-by: Sameh Gobriel <sameh.gobriel at 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 */
