From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga04.intel.com (mga04.intel.com [192.55.52.120]) by dpdk.org (Postfix) with ESMTP id B9AED1BE0C for ; Sat, 7 Jul 2018 04:53:56 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga104.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 06 Jul 2018 19:53:55 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,319,1526367600"; d="scan'208";a="62888529" Received: from skx-yipeng.jf.intel.com ([10.54.81.175]) by FMSMGA003.fm.intel.com with ESMTP; 06 Jul 2018 19:53:44 -0700 From: Yipeng Wang To: pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, yipeng1.wang@intel.com, bruce.richardson@intel.com, honnappa.nagarahalli@arm.com, vguvva@caviumnetworks.com, brijesh.s.singh@gmail.com Date: Fri, 6 Jul 2018 12:46:38 -0700 Message-Id: <1530906406-289697-1-git-send-email-yipeng1.wang@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1528455078-328182-1-git-send-email-yipeng1.wang@intel.com> References: <1528455078-328182-1-git-send-email-yipeng1.wang@intel.com> Subject: [dpdk-dev] [PATCH v3 0/8] Add read-write concurrency to rte_hash library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 07 Jul 2018 02:53:57 -0000 This patch set adds the read-write concurrency support in rte_hash. A new flag value is added to indicate if read-write concurrency is needed during creation time. Test cases are implemented to do functional and performance tests. The new concurrency model is based on rte_rwlock. When Intel TSX is available and the users indicate to use it, the TM version of the rte_rwlock will be called. Both multi-writer and read-write concurrency are protected by the rte_rwlock instead of the x86 specific RTM instructions, so the x86 specific header rte_cuckoo_hash_x86.h is removed and the code is infused into the main .c file. A new rte_hash_count API is proposed to count how many keys are inserted into the hash table. v2->v3: 1. hash: Concurrency bug fix: after beginning cuckoo path moving, the last empty slot needs to be verified again in case other writers raced into this slot and occupy it. A new commit is added to do this bug fix since it applies to master head as well. 2. hash: Concurrency bug fix: if cuckoo path is detected to be invalid, the current slot needs to be emptied since it is duplicated to its target bucket. 3. hash: "const" is used for types in multiple locations. (Pablo) 4. hash: rte_malloc used for readwriter lock used wrong align argument. Similar fix applies to master head so a new commit is created. (Pablo) 5. hash: ring size calculation fix is moved to front. (Pablo) 6. hash: search-and-remove function is refactored to be more aligned with other search function. (Pablo) 7. test: using jhash in functional test for read-write concurrency. It is because jhash with sequential keys incur more cuckoo path. 8. Multiple coding style, typo, commit message fixes. (Pablo) v1->v2: 1. Split each commit into two commits for easier review (Pablo). 2. Add more comments in various places (Pablo). 3. hash: In key insertion function, move duplicated key checking to earlier location and protect it using locks. Checking duplicated key should happen first and data updates should be protected. 4. hash: In lookup bulk function, put signature comparison in lock, since writers could happen between signature match on two buckets. 5. hash: Add write locks to reset function as well to protect resets. 5. test: Fix 32-bit compilation error in read-write test (Pablo). 6. test: Check total physical core count in read-write test. Don't test with thread count that larger than physical core count. 7. Other minor fixes such as typos (Pablo). Yipeng Wang (8): hash: fix multiwriter lock memory allocation hash: fix a multi-writer bug hash: fix to have more accurate key slot size hash: make duplicated code into functions hash: add read and write concurrency support test: add tests in hash table perf test test: add test case for read write concurrency hash: add new API function to query the key count lib/librte_hash/meson.build | 1 - lib/librte_hash/rte_cuckoo_hash.c | 705 +++++++++++++++++++++------------- lib/librte_hash/rte_cuckoo_hash.h | 18 +- lib/librte_hash/rte_cuckoo_hash_x86.h | 164 -------- lib/librte_hash/rte_hash.h | 14 + lib/librte_hash/rte_hash_version.map | 8 + test/test/Makefile | 1 + test/test/test_hash.c | 12 + test/test/test_hash_multiwriter.c | 9 + test/test/test_hash_perf.c | 36 +- test/test/test_hash_readwrite.c | 646 +++++++++++++++++++++++++++++++ 11 files changed, 1167 insertions(+), 447 deletions(-) delete mode 100644 lib/librte_hash/rte_cuckoo_hash_x86.h create mode 100644 test/test/test_hash_readwrite.c -- 2.7.4