From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 5DFABC406 for ; Thu, 16 Jun 2016 01:45:38 +0200 (CEST) Received: from fmsmga001.fm.intel.com ([10.253.24.23]) by fmsmga102.fm.intel.com with ESMTP; 15 Jun 2016 16:45:38 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.26,478,1459839600"; d="scan'208";a="988362905" Received: from irsmsx103.ger.corp.intel.com ([163.33.3.157]) by fmsmga001.fm.intel.com with ESMTP; 15 Jun 2016 16:45:36 -0700 Received: from irsmsx108.ger.corp.intel.com ([169.254.11.183]) by IRSMSX103.ger.corp.intel.com ([169.254.3.240]) with mapi id 14.03.0248.002; Thu, 16 Jun 2016 00:45:35 +0100 From: "De Lara Guarch, Pablo" To: "Shen, Wei1" , "dev@dpdk.org" CC: "Maciocco, Christian" , "Gobriel, Sameh" Thread-Topic: [PATCH v1] hash: add tsx support for cuckoo hash Thread-Index: AQHRp9Kfko/XpRYsU0q4V1vttXdit5/raNvQ Date: Wed, 15 Jun 2016 23:45:35 +0000 Message-ID: References: <1462565102-15312-1-git-send-email-wei1.shen@intel.com> In-Reply-To: <1462565102-15312-1-git-send-email-wei1.shen@intel.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiZDU0MWJhYWUtMTU0MS00MGZkLWEwOGEtYTI1MDIyMTA2MzQ5IiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX0lDIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE1LjkuNi42IiwiVHJ1c3RlZExhYmVsSGFzaCI6ImFkRHhmSm9WVWM0TTNiTHNQVXhzdFZ1RW5PZU5BTEFjeUZGREh5QVwvVnJzPSJ9 x-ctpclassification: CTP_IC x-originating-ip: [163.33.239.181] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH v1] hash: add tsx support for cuckoo hash X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 15 Jun 2016 23:45:39 -0000 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, Same= h > Subject: [PATCH v1] hash: add tsx support for cuckoo hash >=20 > Introduced Intel TSX-enabled scalable multi-writer Cuckoo hash > insertion. >=20 > 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. >=20 > * Added an extra rte_hash flag definition to switch default > single writer Cuckoo Hash behavior to multiwriter. >=20 > * Added a make_space_insert_bfs_mw() function to do split Cuckoo > search in BFS order. >=20 > * Added tsx_cuckoo_move_insert() to do Cuckoo move in Intel TSX > protected manner. >=20 > * Added test_hash_multiwriter() as test case for multi-writer > Cuckoo Hash. >=20 > Signed-off-by: Shen Wei > Signed-off-by: Sameh Gobriel > --- > 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 >=20 [...] > 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 =3D > + 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 =3D -1; > + > + if (rte_lcore_count() =3D=3D 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 =3D test_hash_multiwriter(); > + > + return r; > +} > + > + > +static struct test_command hash_scaling_cmd =3D { > + .command =3D "hash_multiwriter_autotest", > + .callback =3D 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 =3D 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 =3D leaf; > + struct rte_hash_bucket *prev_bkt, *curr_bkt =3D leaf->bkt; > + uint32_t prev_slot, curr_slot =3D leaf_slot; > + > + int cuckoo_path_len =3D 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 =3D rte_xbegin(); > + if (likely(status =3D=3D RTE_XBEGIN_STARTED)) { > + while (likely(curr_node->prev !=3D NULL)) { > + prev_node =3D curr_node->prev; > + prev_bkt =3D prev_node->bkt; > + prev_slot =3D curr_node->prev_slot; > + > + prev_alt_bkt_idx > + =3D prev_bkt->signatures[prev_slot].alt > + & h->bucket_bitmask; > + > + if (unlikely(&h->buckets[prev_alt_bkt_idx] > + !=3D curr_bkt)) { > + > rte_xabort(RTE_XABORT_CUCKOO_PATH_INVALIDED); > + } > + > + curr_bkt->signatures[curr_slot] > + =3D prev_bkt->signatures[prev_slot]; > + curr_bkt->key_idx[curr_slot] > + =3D prev_bkt->key_idx[prev_slot]; > + curr_bkt->flag[curr_slot] > + =3D RTE_HASH_KEY_FLAG_MOVED; > + > + curr_slot =3D prev_slot; > + curr_node =3D prev_node; > + curr_bkt =3D curr_node->bkt; > + > + cuckoo_path_len++; > + } > + > + curr_bkt->signatures[curr_slot].current =3D sig; > + curr_bkt->signatures[curr_slot].alt =3D alt_hash; > + curr_bkt->key_idx[curr_slot] =3D new_idx; > + curr_bkt->flag[curr_slot] =3D 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 no= t 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 =3D queue; > + head =3D queue + 1; > + tail->bkt =3D bkt; > + tail->prev =3D NULL; > + tail->prev_slot =3D -1; > + > + /* Cuckoo Search */ > + while (likely(tail !=3D head && head < > + queue + RTE_HASH_BFS_QUEUE_MAX_LEN - 4)) { > + > + curr_bkt =3D tail->bkt; > + for (i =3D 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { > + if (curr_bkt->signatures[i].sig =3D=3D NULL_SIGNATURE) { > + if (likely(tsx_cuckoo_move_insert(h, tail, i, > + sig, alt_hash, new_idx, flag) =3D=3D 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] =3D=3D > RTE_HASH_KEY_FLAG_UNMOVED) { > + /* Enqueue new node and keep prev node > info */ > + alt_bkt =3D > + &(h->buckets[curr_bkt- > >signatures[i].alt > + & h->bucket_bitmask]); > + head->bkt =3D alt_bkt; > + head->prev =3D tail; > + head->prev_slot =3D 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 =3D data; >=20 > - /* Insert new entry is there is room in the primary bucket */ > - for (i =3D 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { > - /* Check if slot is available */ > - if (likely(prim_bkt->signatures[i].sig =3D=3D NULL_SIGNATURE)) { > - prim_bkt->signatures[i].current =3D sig; > - prim_bkt->signatures[i].alt =3D alt_hash; > - prim_bkt->key_idx[i] =3D new_idx; > - return new_idx - 1; > + unsigned status; > + int32_t try =3D 0; > + > + while (try < 10) { Same comments about "unsigned try" and magic numbers. > + status =3D rte_xbegin(); The following code should only be executed if RTM is supported, otherwise, there will be an illegal instruction. > + if (likely(status =3D=3D RTE_XBEGIN_STARTED)) { > + /* Insert new entry is there is room in the primary > + * bucket. Typo: Insert new entry if there is room... > + */ > + for (i =3D 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { > + /* Check if slot is available */ > + if (likely(prim_bkt->signatures[i].sig > + =3D=3D NULL_SIGNATURE)) { Extra indentation to the right, as said above. > + prim_bkt->signatures[i].current =3D sig; > + prim_bkt->signatures[i].alt =3D > alt_hash; > + prim_bkt->key_idx[i] =3D new_idx; > + prim_bkt->flag[i] =3D > + > RTE_HASH_KEY_FLAG_UNMOVED; > + break; > + } > + } > + rte_xend(); > + > + if (i !=3D 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? > } > } >=20 > /* Primary bucket is full, so we need to make space for new entry */