From patchwork Fri Oct 26 05:37:29 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 149577 Delivered-To: patch@linaro.org Received: by 2002:a2e:299d:0:0:0:0:0 with SMTP id p29-v6csp341422ljp; Thu, 25 Oct 2018 22:37:52 -0700 (PDT) X-Google-Smtp-Source: AJdET5c6fCBwX3alhxq9slCQ25qdiBMDPsM96i5CbzD6u/Y94/RF62Et+o+vRqzfzfDL2yFDDvbA X-Received: by 2002:a1c:ee05:: with SMTP id m5-v6mr4148693wmh.138.1540532272485; Thu, 25 Oct 2018 22:37:52 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1540532272; cv=none; d=google.com; s=arc-20160816; b=avjLL0Ke1RcnT8GXouM7yw4wh6+3ON5rvkYTv3ggarvKs1b45mROZ1f+Do9bZnbpZW dVlt9gjLpZT9k1Isdm0NVHlCmB0Q8z5zG/PhP/cOFKosSxBNHOBBj7F5NcYv0S8zMR9x RiSZc4/5S+zF8NOsxi8k9iTUUF16EfzEagSakuEuTULlSX9IaSk4GsLYcjGO+6Z3T/Ug YoJXVvevUXDOb73p+1rmCZou5G0KjN3VWEsxdH17iHjnupRlz8UhqXQqtvkNoz/uGsFJ 3UaccTC6L2zUUxG81GcYIkXoKjBJeeXIOI9f7SToeu382u3NrQ0aJIF0cLVC09S2U0ia g+tA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:references:in-reply-to :message-id:date:cc:to:from; bh=c3WhzB9gzyYm8/0hkTy1Fbe8WU1QuKtwPKlKY9q+Qr0=; b=vJqOX+Eo4AtO/sOuap7fK/vOiIvcx5rCg396UKv377tiTBb4nLo9e900GggFRFWTaa LBz1+zzt5n4LShbNNQFm4bIrNxTAy08bqGys4tDs9GAyfnjvJRiuAImkktOe/W6FRIaV 5fcRyuf9uVfAFOV4q5UqfGm9KkHwYAmoLfF5mIH6BHjDuxrbXtTaQdblvE6FpJ5CUVHj 2ncOtNq/2tvL59gKX5PBTJ9Vx0FX4tlBq6Kr4npAnyINw1WZUPVeQ1pnccHP8txo/AMO /7nKIMb01dbvnXCg4APBcQzW+x5oOM8luwt7PD52J34pEtm2JEBtU6+auSLzhO5qhyhh pzkg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Return-Path: Received: from dpdk.org (dpdk.org. [92.243.14.124]) by mx.google.com with ESMTP id o8-v6si6020597wrp.299.2018.10.25.22.37.52; Thu, 25 Oct 2018 22:37:52 -0700 (PDT) Received-SPF: pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) client-ip=92.243.14.124; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 4B93F5F17; Fri, 26 Oct 2018 07:37:49 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 5EB8958EC; Fri, 26 Oct 2018 07:37:44 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 9301EEBD; Thu, 25 Oct 2018 22:37:43 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.14.139]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 248913F71D; Thu, 25 Oct 2018 22:37:43 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, yipeng1.wang@intel.com, honnappa.nagarahalli@arm.com, dharmik.thakkar@arm.com, gavin.hu@arm.com, nd@arm.com, stable@dpdk.org Date: Fri, 26 Oct 2018 00:37:29 -0500 Message-Id: <1540532253-112591-2-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1540532253-112591-1-git-send-email-honnappa.nagarahalli@arm.com> References: <1540532253-112591-1-git-send-email-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH v7 1/5] hash: separate multi-writer from rw-concurrency 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" RW concurrency is required with single writer and multiple reader usecase as well. Hence, multi-writer should not be enabled by default when RW concurrency is enabled. Fixes: f2e3001b53ec ("hash: support read/write concurrency") Cc: stable@dpdk.org Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Yipeng Wang Acked-by: Bruce Richardson --- lib/librte_hash/rte_cuckoo_hash.c | 49 +++++++++++++++++++++------------------ lib/librte_hash/rte_cuckoo_hash.h | 8 +++++-- test/test/test_hash_readwrite.c | 6 +++-- 3 files changed, 37 insertions(+), 26 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 9a48934..3539a10 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -136,9 +136,10 @@ rte_hash_create(const struct rte_hash_parameters *params) char ext_ring_name[RTE_RING_NAMESIZE]; unsigned num_key_slots; unsigned i; - unsigned int hw_trans_mem_support = 0, multi_writer_support = 0; + unsigned int hw_trans_mem_support = 0, use_local_cache = 0; unsigned int ext_table_support = 0; unsigned int readwrite_concur_support = 0; + unsigned int writer_takes_lock = 0; rte_hash_function default_hash_func = (rte_hash_function)rte_jhash; @@ -162,19 +163,21 @@ rte_hash_create(const struct rte_hash_parameters *params) if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT) hw_trans_mem_support = 1; - if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD) - multi_writer_support = 1; + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD) { + use_local_cache = 1; + writer_takes_lock = 1; + } if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) { readwrite_concur_support = 1; - multi_writer_support = 1; + writer_takes_lock = 1; } if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE) ext_table_support = 1; /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ - if (multi_writer_support) + if (use_local_cache) /* * Increase number of slots by total number of indices * that can be stored in the lcore caches @@ -322,7 +325,7 @@ rte_hash_create(const struct rte_hash_parameters *params) h->cmp_jump_table_idx = KEY_OTHER_BYTES; #endif - if (multi_writer_support) { + if (use_local_cache) { h->local_free_slots = rte_zmalloc_socket(NULL, sizeof(struct lcore_cache) * RTE_MAX_LCORE, RTE_CACHE_LINE_SIZE, params->socket_id); @@ -352,9 +355,10 @@ rte_hash_create(const struct rte_hash_parameters *params) h->key_store = k; h->free_slots = r; h->hw_trans_mem_support = hw_trans_mem_support; - h->multi_writer_support = multi_writer_support; + h->use_local_cache = use_local_cache; h->readwrite_concur_support = readwrite_concur_support; h->ext_table_support = ext_table_support; + h->writer_takes_lock = writer_takes_lock; #if defined(RTE_ARCH_X86) if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2)) @@ -363,10 +367,11 @@ rte_hash_create(const struct rte_hash_parameters *params) #endif h->sig_cmp_fn = RTE_HASH_COMPARE_SCALAR; - /* Turn on multi-writer only with explicit flag from user and TM - * support. + /* Writer threads need to take the lock when: + * 1) RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY is enabled OR + * 2) RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD is enabled */ - if (h->multi_writer_support) { + if (h->writer_takes_lock) { h->readwrite_lock = rte_malloc(NULL, sizeof(rte_rwlock_t), RTE_CACHE_LINE_SIZE); if (h->readwrite_lock == NULL) @@ -425,10 +430,10 @@ rte_hash_free(struct rte_hash *h) rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); - if (h->multi_writer_support) { + if (h->use_local_cache) rte_free(h->local_free_slots); + if (h->writer_takes_lock) rte_free(h->readwrite_lock); - } rte_ring_free(h->free_slots); rte_ring_free(h->free_ext_bkts); rte_free(h->key_store); @@ -454,7 +459,7 @@ rte_hash_count(const struct rte_hash *h) if (h == NULL) return -EINVAL; - if (h->multi_writer_support) { + if (h->use_local_cache) { tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1); for (i = 0; i < RTE_MAX_LCORE; i++) @@ -473,9 +478,9 @@ rte_hash_count(const struct rte_hash *h) static inline void __hash_rw_writer_lock(const struct rte_hash *h) { - if (h->multi_writer_support && h->hw_trans_mem_support) + if (h->writer_takes_lock && h->hw_trans_mem_support) rte_rwlock_write_lock_tm(h->readwrite_lock); - else if (h->multi_writer_support) + else if (h->writer_takes_lock) rte_rwlock_write_lock(h->readwrite_lock); } @@ -491,9 +496,9 @@ __hash_rw_reader_lock(const struct rte_hash *h) static inline void __hash_rw_writer_unlock(const struct rte_hash *h) { - if (h->multi_writer_support && h->hw_trans_mem_support) + if (h->writer_takes_lock && h->hw_trans_mem_support) rte_rwlock_write_unlock_tm(h->readwrite_lock); - else if (h->multi_writer_support) + else if (h->writer_takes_lock) rte_rwlock_write_unlock(h->readwrite_lock); } @@ -532,7 +537,7 @@ rte_hash_reset(struct rte_hash *h) } /* Repopulate the free slots ring. Entry zero is reserved for key misses */ - if (h->multi_writer_support) + if (h->use_local_cache) tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) * (LCORE_CACHE_SIZE - 1); else @@ -548,7 +553,7 @@ rte_hash_reset(struct rte_hash *h) (void *)((uintptr_t) i)); } - if (h->multi_writer_support) { + if (h->use_local_cache) { /* Reset local caches per lcore */ for (i = 0; i < RTE_MAX_LCORE; i++) h->local_free_slots[i].len = 0; @@ -566,7 +571,7 @@ enqueue_slot_back(const struct rte_hash *h, struct lcore_cache *cached_free_slots, void *slot_id) { - if (h->multi_writer_support) { + if (h->use_local_cache) { cached_free_slots->objs[cached_free_slots->len] = slot_id; cached_free_slots->len++; } else @@ -848,7 +853,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, __hash_rw_writer_unlock(h); /* Did not find a match, so get a new slot for storing the new key */ - if (h->multi_writer_support) { + if (h->use_local_cache) { lcore_id = rte_lcore_id(); cached_free_slots = &h->local_free_slots[lcore_id]; /* Try to get a free slot from the local cache */ @@ -1117,7 +1122,7 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) struct lcore_cache *cached_free_slots; bkt->sig_current[i] = NULL_SIGNATURE; - if (h->multi_writer_support) { + if (h->use_local_cache) { lcore_id = rte_lcore_id(); cached_free_slots = &h->local_free_slots[lcore_id]; /* Cache full, need to free it. */ diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index 7753cd8..8c522ac 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -161,11 +161,15 @@ struct rte_hash { /**< Length of hash key. */ uint8_t hw_trans_mem_support; /**< If hardware transactional memory is used. */ - uint8_t multi_writer_support; - /**< If multi-writer support is enabled. */ + uint8_t use_local_cache; + /**< If multi-writer support is enabled, use local cache + * to allocate key-store slots. + */ uint8_t readwrite_concur_support; /**< If read-write concurrency support is enabled */ uint8_t ext_table_support; /**< Enable extendable bucket table */ + uint8_t writer_takes_lock; + /**< Indicates if the writer threads need to take lock */ rte_hash_function hash_func; /**< Function used to calculate hash. */ uint32_t hash_func_init_val; /**< Init value used by hash_func. */ rte_hash_cmp_eq_t rte_hash_custom_cmp_eq; diff --git a/test/test/test_hash_readwrite.c b/test/test/test_hash_readwrite.c index 2a4f7b9..a8fadd0 100644 --- a/test/test/test_hash_readwrite.c +++ b/test/test/test_hash_readwrite.c @@ -122,10 +122,12 @@ init_params(int use_htm, int use_jhash) if (use_htm) hash_params.extra_flag = RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT | - RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY; + RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY | + RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD; else hash_params.extra_flag = - RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY; + RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY | + RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD; hash_params.name = "tests"; From patchwork Fri Oct 26 05:37:30 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 149578 Delivered-To: patch@linaro.org Received: by 2002:a2e:299d:0:0:0:0:0 with SMTP id p29-v6csp341518ljp; Thu, 25 Oct 2018 22:38:00 -0700 (PDT) X-Google-Smtp-Source: AJdET5d6xROdvviRvN/tdiQ1eMq0cKtr72xJIc/0ZtRyY2/YygwoXE9KQeeLaJW+auBRPVdLHrd4 X-Received: by 2002:a5d:46ce:: with SMTP id g14-v6mr4282657wrs.263.1540532280319; Thu, 25 Oct 2018 22:38:00 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1540532280; cv=none; d=google.com; s=arc-20160816; b=eBV6pgMeJ6NTCau/mNPFhhlQ0udAULIi5Oe11ny96Sc7z0QMMJUl0Z3Q66NxjY1BpK AGAUfP0yHSSD7nAPNbg4JFUfBFqb2NmWkWidmBShzc9BFy0Ni0qr+EW69Sq9CPK29mSm GCfPHySj/kcYKKbX1MX6fjJrvCqpuFJ6LA+x1gRl1qpxE/MdvC2UmZjJ7bO+vT9uaiBb 9mLtqBYJ/4EEJ/CO/OzOrOZgi72tdaLROhsjp6nW8x5yb+DvKoS4y9HhBJUSvfFClro6 rKu7y+Of6dNlm4AlSSDFSOHXsx1nE5XFwXkOhEISho5sz4WI1+cQVVHO8toDe6WT/miE U8pA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:references:in-reply-to :message-id:date:cc:to:from; bh=6DBaeAeigVzCX+cTrY2xF+TVfbD5eXkfAEBi7jUcFA4=; b=PMKptQdFmKnKkg4kVWfQhCjyLTOShcTayjHbMxqRP8EbJI63Po2qlxIb1YBdwndm0o KUJklcc2cGjQea1RiHqfOE5pCwAy61PKfQNgvmBM8meYsuMqTuiqhhRezqGZOMYpo3x0 QjU2qkRXu7als1Xv0fic/qgeK6CtoXbCtkeanDE8hmBSZ95KSZA9XcpygitJQ5+weLo7 X6jhH9vuWZMn9rdeA5QndexA48CUURmC5ZNfSOT9BRlPGDeVU42rkHXEQiX9f2QIq+CW c5eeU/cfYV8zxoomc7520RekTdprbDzxIhGs29115sS3SixRVN7QM6bQ35IMy6KDGfTz +nzw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Return-Path: Received: from dpdk.org (dpdk.org. [92.243.14.124]) by mx.google.com with ESMTP id y16-v6si7928218wrr.124.2018.10.25.22.38.00; Thu, 25 Oct 2018 22:38:00 -0700 (PDT) Received-SPF: pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) client-ip=92.243.14.124; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 6468D6833; Fri, 26 Oct 2018 07:37:51 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id A41945F12 for ; Fri, 26 Oct 2018 07:37:44 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 16BBF15BF; Thu, 25 Oct 2018 22:37:44 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.14.139]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 9C6483F71D; Thu, 25 Oct 2018 22:37:43 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, yipeng1.wang@intel.com, honnappa.nagarahalli@arm.com, dharmik.thakkar@arm.com, gavin.hu@arm.com, nd@arm.com Date: Fri, 26 Oct 2018 00:37:30 -0500 Message-Id: <1540532253-112591-3-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1540532253-112591-1-git-send-email-honnappa.nagarahalli@arm.com> References: <1540532253-112591-1-git-send-email-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH v7 2/5] hash: support do not free on delete 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" rte_hash_lookup_xxx APIs return the index of slot in the key store. Application(reader) can use that index to reference other data structures in its scope. Because of this, the index should not be freed till the application completes using the index. RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is introduced to support this. When this flag is enabled rte_hash_del_xxx APIs do not free the key-store index/internal memory associated with the deleted entry. The new API rte_hash_free_key_with_position should be called to free the key-store index/internal memory after calling rte_hash_del_xxx APIs. Suggested-by: Yipeng Wang Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Yipeng Wang Acked-by: Bruce Richardson --- lib/librte_hash/rte_cuckoo_hash.c | 50 ++++++++++++- lib/librte_hash/rte_cuckoo_hash.h | 6 ++ lib/librte_hash/rte_hash.h | 40 ++++++++++ lib/librte_hash/rte_hash_version.map | 7 ++ test/test/test_hash.c | 140 ++++++++++++++++++++++++++++++++++- 5 files changed, 239 insertions(+), 4 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 3539a10..e087393 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -140,6 +140,7 @@ rte_hash_create(const struct rte_hash_parameters *params) unsigned int ext_table_support = 0; unsigned int readwrite_concur_support = 0; unsigned int writer_takes_lock = 0; + unsigned int no_free_on_del = 0; rte_hash_function default_hash_func = (rte_hash_function)rte_jhash; @@ -176,6 +177,9 @@ rte_hash_create(const struct rte_hash_parameters *params) if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE) ext_table_support = 1; + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL) + no_free_on_del = 1; + /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ if (use_local_cache) /* @@ -359,6 +363,7 @@ rte_hash_create(const struct rte_hash_parameters *params) h->readwrite_concur_support = readwrite_concur_support; h->ext_table_support = ext_table_support; h->writer_takes_lock = writer_takes_lock; + h->no_free_on_del = no_free_on_del; #if defined(RTE_ARCH_X86) if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2)) @@ -1121,7 +1126,6 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) unsigned lcore_id, n_slots; struct lcore_cache *cached_free_slots; - bkt->sig_current[i] = NULL_SIGNATURE; if (h->use_local_cache) { lcore_id = rte_lcore_id(); cached_free_slots = &h->local_free_slots[lcore_id]; @@ -1183,7 +1187,12 @@ search_and_remove(const struct rte_hash *h, const void *key, k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { - remove_entry(h, bkt, i); + bkt->sig_current[i] = NULL_SIGNATURE; + /* Free the key store index if + * no_free_on_del is disabled. + */ + if (!h->no_free_on_del) + remove_entry(h, bkt, i); /* Return index where key is stored, * subtracting the first dummy index @@ -1301,6 +1310,43 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, return 0; } +int __rte_experimental +rte_hash_free_key_with_position(const struct rte_hash *h, + const int32_t position) +{ + RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL); + + unsigned int lcore_id, n_slots; + struct lcore_cache *cached_free_slots; + const int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES; + + /* Out of bounds */ + if (position >= total_entries) + return -EINVAL; + + if (h->use_local_cache) { + lcore_id = rte_lcore_id(); + cached_free_slots = &h->local_free_slots[lcore_id]; + /* Cache full, need to free it. */ + if (cached_free_slots->len == LCORE_CACHE_SIZE) { + /* Need to enqueue the free slots in global ring. */ + n_slots = rte_ring_mp_enqueue_burst(h->free_slots, + cached_free_slots->objs, + LCORE_CACHE_SIZE, NULL); + cached_free_slots->len -= n_slots; + } + /* Put index of new free slot in cache. */ + cached_free_slots->objs[cached_free_slots->len] = + (void *)((uintptr_t)position); + cached_free_slots->len++; + } else { + rte_ring_sp_enqueue(h->free_slots, + (void *)((uintptr_t)position)); + } + + return 0; +} + static inline void compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches, const struct rte_hash_bucket *prim_bkt, diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index 8c522ac..ff95181 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -168,6 +168,12 @@ struct rte_hash { uint8_t readwrite_concur_support; /**< If read-write concurrency support is enabled */ uint8_t ext_table_support; /**< Enable extendable bucket table */ + uint8_t no_free_on_del; + /**< If key index should be freed on calling rte_hash_del_xxx APIs. + * If this is set, rte_hash_free_key_with_position must be called to + * free the key index associated with the deleted entry. + * This flag is enabled by default. + */ uint8_t writer_takes_lock; /**< Indicates if the writer threads need to take lock */ rte_hash_function hash_func; /**< Function used to calculate hash. */ diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index 6ace64e..dfa542b 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -14,6 +14,8 @@ #include #include +#include + #ifdef __cplusplus extern "C" { #endif @@ -40,6 +42,11 @@ extern "C" { /** Flag to indicate the extendabe bucket table feature should be used */ #define RTE_HASH_EXTRA_FLAGS_EXT_TABLE 0x08 +/** Flag to disable freeing of key index on hash delete. + * Refer to rte_hash_del_xxx APIs for more details. + */ +#define RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL 0x10 + /** * The type of hash value of a key. * It should be a value of at least 32bit with fully random pattern. @@ -236,6 +243,10 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is enabled, + * the key index returned by rte_hash_add_key_xxx APIs will not be + * freed by this API. rte_hash_free_key_with_position API must be called + * additionally to free the index associated with the key. * * @param h * Hash table to remove the key from. @@ -257,6 +268,10 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is enabled, + * the key index returned by rte_hash_add_key_xxx APIs will not be + * freed by this API. rte_hash_free_key_with_position API must be called + * additionally to free the index associated with the key. * * @param h * Hash table to remove the key from. @@ -296,6 +311,31 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, void **key); /** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Free a hash key in the hash table given the position + * of the key. This operation is not multi-thread safe and should + * only be called from one thread by default. Thread safety + * can be enabled by setting flag during table creation. + * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is enabled, + * this API must be called, with the key index returned by rte_hash_add_key_xxx + * APIs, after the key is deleted using rte_hash_del_key_xxx APIs. + * This API does not validate if the key is already freed. + * + * @param h + * Hash table to free the key from. + * @param position + * Position returned when the key was deleted. + * @return + * - 0 if freed successfully + * - -EINVAL if the parameters are invalid. + */ +int __rte_experimental +rte_hash_free_key_with_position(const struct rte_hash *h, + const int32_t position); + +/** * Find a key-value pair in the hash table. * This operation is multi-thread safe with regarding to other lookup threads. * Read-write concurrency can be enabled by setting flag during diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index e216ac8..734ae28 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -53,3 +53,10 @@ DPDK_18.08 { rte_hash_count; } DPDK_16.07; + +EXPERIMENTAL { + global: + + rte_hash_free_key_with_position; + +}; diff --git a/test/test/test_hash.c b/test/test/test_hash.c index 815c734..6d06eb2 100644 --- a/test/test/test_hash.c +++ b/test/test/test_hash.c @@ -260,6 +260,13 @@ static void run_hash_func_tests(void) * - lookup (hit) * - delete * - lookup (miss) + * + * Repeat the test case when 'free on delete' is disabled. + * - add + * - lookup (hit) + * - delete + * - lookup (miss) + * - free */ static int test_add_delete(void) { @@ -295,10 +302,12 @@ static int test_add_delete(void) /* repeat test with precomputed hash functions */ hash_sig_t hash_value; - int pos1, expectedPos1; + int pos1, expectedPos1, delPos1; + ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL; handle = rte_hash_create(&ut_params); RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + ut_params.extra_flag = 0; hash_value = rte_hash_hash(handle, &keys[0]); pos1 = rte_hash_add_key_with_hash(handle, &keys[0], hash_value); @@ -315,12 +324,18 @@ static int test_add_delete(void) print_key_info("Del", &keys[0], pos1); RETURN_IF_ERROR(pos1 != expectedPos1, "failed to delete key (pos1=%d)", pos1); + delPos1 = pos1; pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value); print_key_info("Lkp", &keys[0], pos1); RETURN_IF_ERROR(pos1 != -ENOENT, "fail: found key after deleting! (pos1=%d)", pos1); + pos1 = rte_hash_free_key_with_position(handle, delPos1); + print_key_info("Free", &keys[0], delPos1); + RETURN_IF_ERROR(pos1 != 0, + "failed to free key (pos1=%d)", delPos1); + rte_hash_free(handle); return 0; @@ -391,6 +406,84 @@ static int test_add_update_delete(void) } /* + * Sequence of operations for a single key with 'disable free on del' set: + * - delete: miss + * - add + * - lookup: hit + * - add: update + * - lookup: hit (updated data) + * - delete: hit + * - delete: miss + * - lookup: miss + * - free: hit + * - lookup: miss + */ +static int test_add_update_delete_free(void) +{ + struct rte_hash *handle; + int pos0, expectedPos0, delPos0, result; + + ut_params.name = "test2"; + ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL; + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + ut_params.extra_flag = 0; + + pos0 = rte_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found non-existent key (pos0=%d)", pos0); + + pos0 = rte_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos0); + RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0); + expectedPos0 = pos0; + + pos0 = rte_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to find key (pos0=%d)", pos0); + + pos0 = rte_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to re-add key (pos0=%d)", pos0); + + pos0 = rte_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to find key (pos0=%d)", pos0); + + delPos0 = rte_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], delPos0); + RETURN_IF_ERROR(delPos0 != expectedPos0, + "failed to delete key (pos0=%d)", delPos0); + + pos0 = rte_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: deleted already deleted key (pos0=%d)", pos0); + + pos0 = rte_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found key after deleting! (pos0=%d)", pos0); + + result = rte_hash_free_key_with_position(handle, delPos0); + print_key_info("Free", &keys[0], delPos0); + RETURN_IF_ERROR(result != 0, + "failed to free key (pos1=%d)", delPos0); + + pos0 = rte_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found key after deleting! (pos0=%d)", pos0); + + rte_hash_free(handle); + return 0; +} + +/* * Sequence of operations for retrieving a key with its position * * - create table @@ -399,11 +492,20 @@ static int test_add_update_delete(void) * - delete key * - try to get the deleted key: miss * + * Repeat the test case when 'free on delete' is disabled. + * - create table + * - add key + * - get the key with its position: hit + * - delete key + * - try to get the deleted key: hit + * - free key + * - try to get the deleted key: miss + * */ static int test_hash_get_key_with_position(void) { struct rte_hash *handle = NULL; - int pos, expectedPos, result; + int pos, expectedPos, delPos, result; void *key; ut_params.name = "hash_get_key_w_pos"; @@ -427,6 +529,38 @@ static int test_hash_get_key_with_position(void) RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved"); rte_hash_free(handle); + + ut_params.name = "hash_get_key_w_pos"; + ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL; + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + ut_params.extra_flag = 0; + + pos = rte_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos); + RETURN_IF_ERROR(pos < 0, "failed to add key (pos0=%d)", pos); + expectedPos = pos; + + result = rte_hash_get_key_with_position(handle, pos, &key); + RETURN_IF_ERROR(result != 0, "error retrieving a key"); + + delPos = rte_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], delPos); + RETURN_IF_ERROR(delPos != expectedPos, + "failed to delete key (pos0=%d)", delPos); + + result = rte_hash_get_key_with_position(handle, delPos, &key); + RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved"); + + result = rte_hash_free_key_with_position(handle, delPos); + print_key_info("Free", &keys[0], delPos); + RETURN_IF_ERROR(result != 0, + "failed to free key (pos1=%d)", delPos); + + result = rte_hash_get_key_with_position(handle, delPos, &key); + RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved"); + + rte_hash_free(handle); return 0; } @@ -1609,6 +1743,8 @@ test_hash(void) return -1; if (test_add_update_delete() < 0) return -1; + if (test_add_update_delete_free() < 0) + return -1; if (test_five_keys() < 0) return -1; if (test_full_bucket() < 0) From patchwork Fri Oct 26 05:37:31 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 149579 Delivered-To: patch@linaro.org Received: by 2002:a2e:299d:0:0:0:0:0 with SMTP id p29-v6csp341633ljp; Thu, 25 Oct 2018 22:38:07 -0700 (PDT) X-Google-Smtp-Source: AJdET5ehOymJJXL1z9qSj6FZcgUvjuZ56PDbbfcaSJ4GfNvJaFUBZsrCwOVwwDBHiVhTv/8RjIzc X-Received: by 2002:a1c:5e07:: with SMTP id s7-v6mr4048879wmb.91.1540532287898; Thu, 25 Oct 2018 22:38:07 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1540532287; cv=none; d=google.com; s=arc-20160816; b=bir4zPYR2QZk+QshUDm91Bnvjw0Gfy60FickiUHcw2R5aIR2XDVNcrv0cDUF6HgsiH pd73/sW5nix1t7NU5uGuyn9h/zd0I7e8gEteHg5UtLu+9JJmS+plzbb9cUpxytPjB++m 2x6HDiyjYDbJHDerF7I6772MXeic1UTpUOiEXOgks87ptUF4C12O+Vwv4/5hNKVtiM6E Q8P4zTQGbCzGvVUu1ILz05xnNjpiCT1VxhZMCwtmiQQTvDVyVfJafLp2pjvftMXd8QJ/ TV387mq83nX/jP5Sc5w/czK7YRMeL3JtZ4pDQt/Utm6PxWPVGEWUaBOECf59PP3Y57EX S3+A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:references:in-reply-to :message-id:date:cc:to:from; bh=BiteWHIZHdPmLavF0MhHZEISfdoAcQOmJORoPLXTkeU=; b=EJXim+wsnIUzRLv39kCATLeFGLnmA6ogNJtaLxwt2e1/bZ3DdLzRACxpXmc4htL5VN +feoJR+LoIrK6vaq+w2WxNDCp4odawJDMUd6kQZ0/dF2RGDe4sEFyrcDeRxayKpW3j1g uMSLb5A+RHiKhKuQt4YoDdZ/IkilgcX8CT4NBD8rw0QiuaD6Osta1RINm6+vn6ZHyioR mxJP5N0WCAzFYI2nl2no7vR+CfJWFtvHuHrEenaEFE56+sJSWU/50H7ttCogIeU/NwtK AAXa3/gUzgSX5+FwK9e/eJnUag2ajq+p9dvdjCOe0C3KjMueN5G/fT8ongZsxJsSaIBo iGnQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Return-Path: Received: from dpdk.org (dpdk.org. [92.243.14.124]) by mx.google.com with ESMTP id t9-v6si7559047wrq.111.2018.10.25.22.38.07; Thu, 25 Oct 2018 22:38:07 -0700 (PDT) Received-SPF: pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) client-ip=92.243.14.124; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id B7A417D4A; Fri, 26 Oct 2018 07:37:53 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 3A93B58EC; Fri, 26 Oct 2018 07:37:45 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 8EA91165C; Thu, 25 Oct 2018 22:37:44 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.14.139]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 205C03F71D; Thu, 25 Oct 2018 22:37:44 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, yipeng1.wang@intel.com, honnappa.nagarahalli@arm.com, dharmik.thakkar@arm.com, gavin.hu@arm.com, nd@arm.com, stable@dpdk.org Date: Fri, 26 Oct 2018 00:37:31 -0500 Message-Id: <1540532253-112591-4-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1540532253-112591-1-git-send-email-honnappa.nagarahalli@arm.com> References: <1540532253-112591-1-git-send-email-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH v7 3/5] hash: fix key store element alignment 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Fix the key store array element alignment such that every array element is aligned on KEY_ALIGNMENT boundary. This is required to make 'pdata' in 'struct rte_hash_key' align on its natural boundary for atomic load/store. Fixes: 473d1bebce43 ("hash: allow to store data in hash table") Cc: stable@dpdk.org Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Ola Liljedahl Reviewed-by: Steve Capper Reviewed-by: Yipeng Wang Acked-by: Bruce Richardson --- lib/librte_hash/rte_cuckoo_hash.c | 4 +++- lib/librte_hash/rte_cuckoo_hash.h | 2 +- 2 files changed, 4 insertions(+), 2 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index e087393..d79ba68 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -279,7 +279,9 @@ rte_hash_create(const struct rte_hash_parameters *params) rte_ring_sp_enqueue(r_ext, (void *)((uintptr_t) i)); } - const uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len; + const uint32_t key_entry_size = + RTE_ALIGN(sizeof(struct rte_hash_key) + params->key_len, + KEY_ALIGNMENT); const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots; k = rte_zmalloc_socket(NULL, key_tbl_size, diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index ff95181..601b2ce 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -123,7 +123,7 @@ struct rte_hash_key { }; /* Variable key size */ char key[0]; -} __attribute__((aligned(KEY_ALIGNMENT))); +}; /* All different signature compare functions */ enum rte_hash_sig_compare_function { From patchwork Fri Oct 26 05:37:32 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 149581 Delivered-To: patch@linaro.org Received: by 2002:a2e:299d:0:0:0:0:0 with SMTP id p29-v6csp341873ljp; Thu, 25 Oct 2018 22:38:27 -0700 (PDT) X-Google-Smtp-Source: AJdET5eGxZl3sX/zZuKsfb/bQgW3RsRThKHFsZa+eCAifnHr5F3phFkFdSqg86UER7yCtkR6Ic9e X-Received: by 2002:adf:f090:: with SMTP id n16-v6mr4137914wro.15.1540532307240; Thu, 25 Oct 2018 22:38:27 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1540532307; cv=none; d=google.com; s=arc-20160816; b=Cn7WTVR8WubmmZj5dwexanQ1Rf0pkOiltQW/iOce/7evWG3E1hFyOlkMsUcd64gbiD KTthGR5pJYuwDDzgzaQCgTvKVNuORDwetZy0iVUfRYWCIkGhbv6+WnQ5hPSzqZ4uw7OC zG8uDd9xnCFXDYeVxGiN/Fjsptqm6/nENPxBUpk3X35cDf0Kxfr5gZvJd82V2zBwNBCC GI2vJjImkQXCxjjQj7rkSNCfzixiQ2BuDq5ZiRqLiYJ5UytWMmBfZWlh9OpTn0cHwTue ZMaFBu2H9Asq4CnYz+ic0YZsYOwQ6nLVO4d6aRnB1NEORmeQfk87MLv/3aGY5vwjweg7 eEmQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:references:in-reply-to :message-id:date:cc:to:from; bh=VymttvFxp7LCQQNkz8CwINRHd0beaPox917S+b1yBns=; b=Wy3+CjylaUBLEq+2aFoMygKaD/tEhCwSD/OFNLHeVwnd0TDalWxspFeLIi8MBuYLl6 jCHp8V1fwP9DKwydmtFArCigrtV4P9xePU3t7Q5dsuM3OFwMThMXMjWYC4Kqjp3fjWQI mdZeqROK8QlqhEOMZFJPXTjAZhsd3En7Ghpv2HXxX8ASRKXCn9kJv4sV6QVlvqO6SnXG FvfP+jAkQFDO/nStdjkdIjoyZ9IjI588DnlwEq5+hnqxT808sVeRXMNozudLdRaII8Ns 7zASrMYjuayrZzjQ+mbjz+auL2b6R8pWpYAFyOPFH0uv2nJgR4BVjnh4vkjriOof1W8H hQQA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Return-Path: Received: from dpdk.org (dpdk.org. [92.243.14.124]) by mx.google.com with ESMTP id 88-v6si9954505wrd.441.2018.10.25.22.38.27; Thu, 25 Oct 2018 22:38:27 -0700 (PDT) Received-SPF: pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) client-ip=92.243.14.124; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 498671B113; Fri, 26 Oct 2018 07:37:59 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id ACF055F12 for ; Fri, 26 Oct 2018 07:37:45 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 0A8631682; Thu, 25 Oct 2018 22:37:45 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.14.139]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 982DD3F71D; Thu, 25 Oct 2018 22:37:44 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, yipeng1.wang@intel.com, honnappa.nagarahalli@arm.com, dharmik.thakkar@arm.com, gavin.hu@arm.com, nd@arm.com Date: Fri, 26 Oct 2018 00:37:32 -0500 Message-Id: <1540532253-112591-5-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1540532253-112591-1-git-send-email-honnappa.nagarahalli@arm.com> References: <1540532253-112591-1-git-send-email-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH v7 4/5] hash: add lock-free read-write concurrency 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Add lock-free read-write concurrency. This is achieved by the following changes. 1) Add memory ordering to avoid race conditions. The only race condition that can occur is - using the key store element before the key write is completed. Hence, while inserting the element the release memory order is used. Any other race condition is caught by the key comparison. Memory orderings are added only where needed. For ex: reads in the writer's context do not need memory ordering as there is a single writer. key_idx in the bucket entry and pdata in the key store element are used for synchronisation. key_idx is used to release an inserted entry in the bucket to the reader. Use of pdata for synchronisation is required due to updation of an existing entry where-in only the pdata is updated without updating key_idx. 2) Reader-writer concurrency issue, caused by moving the keys to their alternative locations during key insert, is solved by introducing a global counter(tbl_chng_cnt) indicating a change in table. 3) Add the flag to enable reader-writer concurrency during run time. Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Ola Liljedahl Reviewed-by: Steve Capper Reviewed-by: Yipeng Wang Acked-by: Bruce Richardson --- lib/librte_hash/rte_cuckoo_hash.c | 417 ++++++++++++++++++++++++++++---------- lib/librte_hash/rte_cuckoo_hash.h | 5 + lib/librte_hash/rte_hash.h | 47 ++++- 3 files changed, 351 insertions(+), 118 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index d79ba68..0648a22 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -1,5 +1,6 @@ /* SPDX-License-Identifier: BSD-3-Clause * Copyright(c) 2010-2016 Intel Corporation + * Copyright(c) 2018 Arm Limited */ #include @@ -141,6 +142,8 @@ rte_hash_create(const struct rte_hash_parameters *params) unsigned int readwrite_concur_support = 0; unsigned int writer_takes_lock = 0; unsigned int no_free_on_del = 0; + uint32_t *tbl_chng_cnt = NULL; + unsigned int readwrite_concur_lf_support = 0; rte_hash_function default_hash_func = (rte_hash_function)rte_jhash; @@ -160,6 +163,24 @@ rte_hash_create(const struct rte_hash_parameters *params) return NULL; } + /* Validate correct usage of extra options */ + if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) && + (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF)) { + rte_errno = EINVAL; + RTE_LOG(ERR, HASH, "rte_hash_create: choose rw concurrency or " + "rw concurrency lock free\n"); + return NULL; + } + + if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) && + (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)) { + rte_errno = EINVAL; + RTE_LOG(ERR, HASH, "rte_hash_create: extendable bucket " + "feature not supported with rw concurrency " + "lock free\n"); + return NULL; + } + /* Check extra flags field to check extra options. */ if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT) hw_trans_mem_support = 1; @@ -180,6 +201,12 @@ rte_hash_create(const struct rte_hash_parameters *params) if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL) no_free_on_del = 1; + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) { + readwrite_concur_lf_support = 1; + /* Enable not freeing internal memory/index on delete */ + no_free_on_del = 1; + } + /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ if (use_local_cache) /* @@ -292,6 +319,14 @@ rte_hash_create(const struct rte_hash_parameters *params) goto err_unlock; } + tbl_chng_cnt = rte_zmalloc_socket(NULL, sizeof(uint32_t), + RTE_CACHE_LINE_SIZE, params->socket_id); + + if (tbl_chng_cnt == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + goto err_unlock; + } + /* * If x86 architecture is used, select appropriate compare function, * which may use x86 intrinsics, otherwise use memcmp @@ -360,12 +395,15 @@ rte_hash_create(const struct rte_hash_parameters *params) default_hash_func : params->hash_func; h->key_store = k; h->free_slots = r; + h->tbl_chng_cnt = tbl_chng_cnt; + *h->tbl_chng_cnt = 0; h->hw_trans_mem_support = hw_trans_mem_support; h->use_local_cache = use_local_cache; h->readwrite_concur_support = readwrite_concur_support; h->ext_table_support = ext_table_support; h->writer_takes_lock = writer_takes_lock; h->no_free_on_del = no_free_on_del; + h->readwrite_concur_lf_support = readwrite_concur_lf_support; #if defined(RTE_ARCH_X86) if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2)) @@ -406,6 +444,7 @@ rte_hash_create(const struct rte_hash_parameters *params) rte_free(buckets); rte_free(buckets_ext); rte_free(k); + rte_free(tbl_chng_cnt); return NULL; } @@ -446,6 +485,7 @@ rte_hash_free(struct rte_hash *h) rte_free(h->key_store); rte_free(h->buckets); rte_free(h->buckets_ext); + rte_free(h->tbl_chng_cnt); rte_free(h); rte_free(te); } @@ -530,6 +570,7 @@ rte_hash_reset(struct rte_hash *h) __hash_rw_writer_lock(h); memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket)); memset(h->key_store, 0, h->key_entry_size * (h->entries + 1)); + *h->tbl_chng_cnt = 0; /* clear the free ring */ while (rte_ring_dequeue(h->free_slots, &ptr) == 0) @@ -585,7 +626,9 @@ enqueue_slot_back(const struct rte_hash *h, rte_ring_sp_enqueue(h->free_slots, slot_id); } -/* Search a key from bucket and update its data */ +/* Search a key from bucket and update its data. + * Writer holds the lock before calling this. + */ static inline int32_t search_and_update(const struct rte_hash *h, void *data, const void *key, struct rte_hash_bucket *bkt, uint16_t sig) @@ -598,8 +641,13 @@ search_and_update(const struct rte_hash *h, void *data, const void *key, k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { - /* Update data */ - k->pdata = data; + /* 'pdata' acts as the synchronization point + * when an existing hash entry is updated. + * Key is not updated in this case. + */ + __atomic_store_n(&k->pdata, + data, + __ATOMIC_RELEASE); /* * Return index where key is stored, * subtracting the first dummy index @@ -655,7 +703,15 @@ rte_hash_cuckoo_insert_mw(const struct rte_hash *h, /* Check if slot is available */ if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) { prim_bkt->sig_current[i] = sig; - prim_bkt->key_idx[i] = new_idx; + /* Key can be of arbitrary length, so it is + * not possible to store it atomically. + * Hence the new key element's memory stores + * (key as well as data) should be complete + * before it is referenced. + */ + __atomic_store_n(&prim_bkt->key_idx[i], + new_idx, + __ATOMIC_RELEASE); break; } } @@ -728,27 +784,66 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h, if (unlikely(&h->buckets[prev_alt_bkt_idx] != curr_bkt)) { /* revert it to empty, otherwise duplicated keys */ - curr_bkt->key_idx[curr_slot] = EMPTY_SLOT; + __atomic_store_n(&curr_bkt->key_idx[curr_slot], + EMPTY_SLOT, + __ATOMIC_RELEASE); __hash_rw_writer_unlock(h); return -1; } + if (h->readwrite_concur_lf_support) { + /* Inform the previous move. The current move need + * not be informed now as the current bucket entry + * is present in both primary and secondary. + * Since there is one writer, load acquires on + * tbl_chng_cnt are not required. + */ + __atomic_store_n(h->tbl_chng_cnt, + *h->tbl_chng_cnt + 1, + __ATOMIC_RELEASE); + /* The stores to sig_alt and sig_current should not + * move above the store to tbl_chng_cnt. + */ + __atomic_thread_fence(__ATOMIC_RELEASE); + } + /* Need to swap current/alt sig to allow later * Cuckoo insert to move elements back to its * primary bucket if available */ curr_bkt->sig_current[curr_slot] = prev_bkt->sig_current[prev_slot]; - curr_bkt->key_idx[curr_slot] = - prev_bkt->key_idx[prev_slot]; + /* Release the updated bucket entry */ + __atomic_store_n(&curr_bkt->key_idx[curr_slot], + prev_bkt->key_idx[prev_slot], + __ATOMIC_RELEASE); curr_slot = prev_slot; curr_node = prev_node; curr_bkt = curr_node->bkt; } + if (h->readwrite_concur_lf_support) { + /* Inform the previous move. The current move need + * not be informed now as the current bucket entry + * is present in both primary and secondary. + * Since there is one writer, load acquires on + * tbl_chng_cnt are not required. + */ + __atomic_store_n(h->tbl_chng_cnt, + *h->tbl_chng_cnt + 1, + __ATOMIC_RELEASE); + /* The stores to sig_alt and sig_current should not + * move above the store to tbl_chng_cnt. + */ + __atomic_thread_fence(__ATOMIC_RELEASE); + } + curr_bkt->sig_current[curr_slot] = sig; - curr_bkt->key_idx[curr_slot] = new_idx; + /* Release the new bucket entry */ + __atomic_store_n(&curr_bkt->key_idx[curr_slot], + new_idx, + __ATOMIC_RELEASE); __hash_rw_writer_unlock(h); @@ -889,8 +984,15 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, new_idx = (uint32_t)((uintptr_t) slot_id); /* Copy key */ rte_memcpy(new_k->key, key, h->key_len); - new_k->pdata = data; - + /* Key can be of arbitrary length, so it is not possible to store + * it atomically. Hence the new key element's memory stores + * (key as well as data) should be complete before it is referenced. + * 'pdata' acts as the synchronization point when an existing hash + * entry is updated. + */ + __atomic_store_n(&new_k->pdata, + data, + __ATOMIC_RELEASE); /* Find an empty slot and insert */ ret = rte_hash_cuckoo_insert_mw(h, prim_bkt, sec_bkt, key, data, @@ -1034,21 +1136,27 @@ search_one_bucket(const struct rte_hash *h, const void *key, uint16_t sig, void **data, const struct rte_hash_bucket *bkt) { int i; + uint32_t key_idx; + void *pdata; struct rte_hash_key *k, *keys = h->key_store; for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - if (bkt->sig_current[i] == sig && - bkt->key_idx[i] != EMPTY_SLOT) { + key_idx = __atomic_load_n(&bkt->key_idx[i], + __ATOMIC_ACQUIRE); + if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + - bkt->key_idx[i] * h->key_entry_size); + key_idx * h->key_entry_size); + pdata = __atomic_load_n(&k->pdata, + __ATOMIC_ACQUIRE); + if (rte_hash_cmp_eq(key, k->key, h) == 0) { if (data != NULL) - *data = k->pdata; + *data = pdata; /* * Return index where key is stored, * subtracting the first dummy index */ - return bkt->key_idx[i] - 1; + return key_idx - 1; } } } @@ -1061,34 +1169,62 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, { uint32_t prim_bucket_idx, sec_bucket_idx; struct rte_hash_bucket *bkt, *cur_bkt; + uint32_t cnt_b, cnt_a; int ret; uint16_t short_sig; short_sig = get_short_sig(sig); prim_bucket_idx = get_prim_bucket_index(h, sig); sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig); - bkt = &h->buckets[prim_bucket_idx]; __hash_rw_reader_lock(h); - /* Check if key is in primary location */ - ret = search_one_bucket(h, key, short_sig, data, bkt); - if (ret != -1) { - __hash_rw_reader_unlock(h); - return ret; - } - /* Calculate secondary hash */ - bkt = &h->buckets[sec_bucket_idx]; + do { + /* Load the table change counter before the lookup + * starts. Acquire semantics will make sure that + * loads in search_one_bucket are not hoisted. + */ + cnt_b = __atomic_load_n(h->tbl_chng_cnt, + __ATOMIC_ACQUIRE); - /* Check if key is in secondary location */ - FOR_EACH_BUCKET(cur_bkt, bkt) { - ret = search_one_bucket(h, key, short_sig, data, cur_bkt); + /* Check if key is in primary location */ + bkt = &h->buckets[prim_bucket_idx]; + ret = search_one_bucket(h, key, short_sig, data, bkt); if (ret != -1) { __hash_rw_reader_unlock(h); return ret; } - } + /* Calculate secondary hash */ + bkt = &h->buckets[sec_bucket_idx]; + + /* Check if key is in secondary location */ + FOR_EACH_BUCKET(cur_bkt, bkt) { + ret = search_one_bucket(h, key, short_sig, + data, cur_bkt); + if (ret != -1) { + __hash_rw_reader_unlock(h); + return ret; + } + } + + /* The loads of sig_current in search_one_bucket + * should not move below the load from tbl_chng_cnt. + */ + __atomic_thread_fence(__ATOMIC_ACQUIRE); + /* Re-read the table change counter to check if the + * table has changed during search. If yes, re-do + * the search. + * This load should not get hoisted. The load + * acquires on cnt_b, key index in primary bucket + * and key index in secondary bucket will make sure + * that it does not get hoisted. + */ + cnt_a = __atomic_load_n(h->tbl_chng_cnt, + __ATOMIC_ACQUIRE); + } while (cnt_b != cnt_a); + __hash_rw_reader_unlock(h); + return -ENOENT; } @@ -1173,21 +1309,25 @@ __rte_hash_compact_ll(struct rte_hash_bucket *cur_bkt, int pos) { } } -/* Search one bucket and remove the matched key */ +/* Search one bucket and remove the matched key. + * Writer is expected to hold the lock while calling this + * function. + */ static inline int32_t search_and_remove(const struct rte_hash *h, const void *key, struct rte_hash_bucket *bkt, uint16_t sig, int *pos) { struct rte_hash_key *k, *keys = h->key_store; unsigned int i; - int32_t ret; + uint32_t key_idx; /* Check if key is in bucket */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - if (bkt->sig_current[i] == sig && - bkt->key_idx[i] != EMPTY_SLOT) { + key_idx = __atomic_load_n(&bkt->key_idx[i], + __ATOMIC_ACQUIRE); + if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + - bkt->key_idx[i] * h->key_entry_size); + key_idx * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { bkt->sig_current[i] = NULL_SIGNATURE; /* Free the key store index if @@ -1196,13 +1336,16 @@ search_and_remove(const struct rte_hash *h, const void *key, if (!h->no_free_on_del) remove_entry(h, bkt, i); - /* Return index where key is stored, + __atomic_store_n(&bkt->key_idx[i], + EMPTY_SLOT, + __ATOMIC_RELEASE); + + *pos = i; + /* + * Return index where key is stored, * subtracting the first dummy index */ - ret = bkt->key_idx[i] - 1; - bkt->key_idx[i] = EMPTY_SLOT; - *pos = i; - return ret; + return key_idx - 1; } } } @@ -1402,6 +1545,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0}; uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0}; struct rte_hash_bucket *cur_bkt, *next_bkt; + void *pdata[RTE_HASH_LOOKUP_BULK_MAX]; + uint32_t cnt_b, cnt_a; /* Prefetch first keys */ for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++) @@ -1443,91 +1588,138 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, } __hash_rw_reader_lock(h); - /* Compare signatures and prefetch key slot of first hit */ - for (i = 0; i < num_keys; i++) { - compare_signatures(&prim_hitmask[i], &sec_hitmask[i], + do { + /* Load the table change counter before the lookup + * starts. Acquire semantics will make sure that + * loads in compare_signatures are not hoisted. + */ + cnt_b = __atomic_load_n(h->tbl_chng_cnt, + __ATOMIC_ACQUIRE); + + /* Compare signatures and prefetch key slot of first hit */ + for (i = 0; i < num_keys; i++) { + compare_signatures(&prim_hitmask[i], &sec_hitmask[i], primary_bkt[i], secondary_bkt[i], sig[i], h->sig_cmp_fn); - if (prim_hitmask[i]) { - uint32_t first_hit = - __builtin_ctzl(prim_hitmask[i]) >> 1; - uint32_t key_idx = primary_bkt[i]->key_idx[first_hit]; - const struct rte_hash_key *key_slot = - (const struct rte_hash_key *)( - (const char *)h->key_store + - key_idx * h->key_entry_size); - rte_prefetch0(key_slot); - continue; - } - - if (sec_hitmask[i]) { - uint32_t first_hit = - __builtin_ctzl(sec_hitmask[i]) >> 1; - uint32_t key_idx = secondary_bkt[i]->key_idx[first_hit]; - const struct rte_hash_key *key_slot = - (const struct rte_hash_key *)( - (const char *)h->key_store + - key_idx * h->key_entry_size); - rte_prefetch0(key_slot); - } - } - - /* Compare keys, first hits in primary first */ - for (i = 0; i < num_keys; i++) { - positions[i] = -ENOENT; - while (prim_hitmask[i]) { - uint32_t hit_index = - __builtin_ctzl(prim_hitmask[i]) >> 1; - - uint32_t key_idx = primary_bkt[i]->key_idx[hit_index]; - const struct rte_hash_key *key_slot = - (const struct rte_hash_key *)( - (const char *)h->key_store + - key_idx * h->key_entry_size); - /* - * If key index is 0, do not compare key, - * as it is checking the dummy slot - */ - if (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) { - if (data != NULL) - data[i] = key_slot->pdata; + if (prim_hitmask[i]) { + uint32_t first_hit = + __builtin_ctzl(prim_hitmask[i]) + >> 1; + uint32_t key_idx = + primary_bkt[i]->key_idx[first_hit]; + const struct rte_hash_key *key_slot = + (const struct rte_hash_key *)( + (const char *)h->key_store + + key_idx * h->key_entry_size); + rte_prefetch0(key_slot); + continue; + } - hits |= 1ULL << i; - positions[i] = key_idx - 1; - goto next_key; + if (sec_hitmask[i]) { + uint32_t first_hit = + __builtin_ctzl(sec_hitmask[i]) + >> 1; + uint32_t key_idx = + secondary_bkt[i]->key_idx[first_hit]; + const struct rte_hash_key *key_slot = + (const struct rte_hash_key *)( + (const char *)h->key_store + + key_idx * h->key_entry_size); + rte_prefetch0(key_slot); } - prim_hitmask[i] &= ~(3ULL << (hit_index << 1)); } - while (sec_hitmask[i]) { - uint32_t hit_index = - __builtin_ctzl(sec_hitmask[i]) >> 1; - - uint32_t key_idx = secondary_bkt[i]->key_idx[hit_index]; - const struct rte_hash_key *key_slot = - (const struct rte_hash_key *)( - (const char *)h->key_store + - key_idx * h->key_entry_size); - /* - * If key index is 0, do not compare key, - * as it is checking the dummy slot - */ + /* Compare keys, first hits in primary first */ + for (i = 0; i < num_keys; i++) { + positions[i] = -ENOENT; + while (prim_hitmask[i]) { + uint32_t hit_index = + __builtin_ctzl(prim_hitmask[i]) + >> 1; + uint32_t key_idx = + __atomic_load_n( + &primary_bkt[i]->key_idx[hit_index], + __ATOMIC_ACQUIRE); + const struct rte_hash_key *key_slot = + (const struct rte_hash_key *)( + (const char *)h->key_store + + key_idx * h->key_entry_size); + + if (key_idx != EMPTY_SLOT) + pdata[i] = __atomic_load_n( + &key_slot->pdata, + __ATOMIC_ACQUIRE); + /* + * If key index is 0, do not compare key, + * as it is checking the dummy slot + */ + if (!!key_idx & + !rte_hash_cmp_eq( + key_slot->key, keys[i], h)) { + if (data != NULL) + data[i] = pdata[i]; + + hits |= 1ULL << i; + positions[i] = key_idx - 1; + goto next_key; + } + prim_hitmask[i] &= ~(3ULL << (hit_index << 1)); + } - if (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) { - if (data != NULL) - data[i] = key_slot->pdata; + while (sec_hitmask[i]) { + uint32_t hit_index = + __builtin_ctzl(sec_hitmask[i]) + >> 1; + uint32_t key_idx = + __atomic_load_n( + &secondary_bkt[i]->key_idx[hit_index], + __ATOMIC_ACQUIRE); + const struct rte_hash_key *key_slot = + (const struct rte_hash_key *)( + (const char *)h->key_store + + key_idx * h->key_entry_size); + + if (key_idx != EMPTY_SLOT) + pdata[i] = __atomic_load_n( + &key_slot->pdata, + __ATOMIC_ACQUIRE); + /* + * If key index is 0, do not compare key, + * as it is checking the dummy slot + */ - hits |= 1ULL << i; - positions[i] = key_idx - 1; - goto next_key; + if (!!key_idx & + !rte_hash_cmp_eq( + key_slot->key, keys[i], h)) { + if (data != NULL) + data[i] = pdata[i]; + + hits |= 1ULL << i; + positions[i] = key_idx - 1; + goto next_key; + } + sec_hitmask[i] &= ~(3ULL << (hit_index << 1)); } - sec_hitmask[i] &= ~(3ULL << (hit_index << 1)); +next_key: + continue; } -next_key: - continue; - } + /* The loads of sig_current in compare_signatures + * should not move below the load from tbl_chng_cnt. + */ + __atomic_thread_fence(__ATOMIC_ACQUIRE); + /* Re-read the table change counter to check if the + * table has changed during search. If yes, re-do + * the search. + * This load should not get hoisted. The load + * acquires on cnt_b, primary key index and secondary + * key index will make sure that it does not get + * hoisted. + */ + cnt_a = __atomic_load_n(h->tbl_chng_cnt, + __ATOMIC_ACQUIRE); + } while (cnt_b != cnt_a); /* all found, do not need to go through ext bkt */ if ((hits == ((1ULL << num_keys) - 1)) || !h->ext_table_support) { @@ -1612,7 +1804,8 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32 idx = *next % RTE_HASH_BUCKET_ENTRIES; /* If current position is empty, go to the next one */ - while ((position = h->buckets[bucket_idx].key_idx[idx]) == EMPTY_SLOT) { + while ((position = __atomic_load_n(&h->buckets[bucket_idx].key_idx[idx], + __ATOMIC_ACQUIRE)) == EMPTY_SLOT) { (*next)++; /* End of table */ if (*next == total_entries_main) diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index 601b2ce..5dfbbc4 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -1,5 +1,6 @@ /* SPDX-License-Identifier: BSD-3-Clause * Copyright(c) 2016 Intel Corporation + * Copyright(c) 2018 Arm Limited */ /* rte_cuckoo_hash.h @@ -174,6 +175,8 @@ struct rte_hash { * free the key index associated with the deleted entry. * This flag is enabled by default. */ + uint8_t readwrite_concur_lf_support; + /**< If read-write concurrency lock free support is enabled */ uint8_t writer_takes_lock; /**< Indicates if the writer threads need to take lock */ rte_hash_function hash_func; /**< Function used to calculate hash. */ @@ -196,6 +199,8 @@ struct rte_hash { rte_rwlock_t *readwrite_lock; /**< Read-write lock thread-safety. */ struct rte_hash_bucket *buckets_ext; /**< Extra buckets array */ struct rte_ring *free_ext_bkts; /**< Ring of indexes of free buckets */ + uint32_t *tbl_chng_cnt; + /**< Indicates if the hash table changed from last read. */ } __rte_cache_aligned; struct queue_node { diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index dfa542b..c93d1a1 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -44,9 +44,18 @@ extern "C" { /** Flag to disable freeing of key index on hash delete. * Refer to rte_hash_del_xxx APIs for more details. + * This is enabled by default when RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF + * is enabled. */ #define RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL 0x10 +/** Flag to support lock free reader writer concurrency. Both single writer + * and multi writer use cases are supported. + * Currently, extendable bucket table feature is not supported with + * this feature. + */ +#define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x20 + /** * The type of hash value of a key. * It should be a value of at least 32bit with fully random pattern. @@ -132,7 +141,12 @@ void rte_hash_free(struct rte_hash *h); /** - * Reset all hash structure, by zeroing all entries + * Reset all hash structure, by zeroing all entries. + * When RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * it is application's responsibility to make sure that + * none of the readers are referencing the hash table + * while calling this API. + * * @param h * Hash table to reset */ @@ -156,6 +170,11 @@ rte_hash_count(const struct rte_hash *h); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * If the key exists already in the table, this API updates its value + * with 'data' passed in this API. It is the responsibility of + * the application to manage any memory associated with the old value. + * The readers might still be using the old value even after this API + * has returned. * * @param h * Hash table to add the key to. @@ -178,6 +197,11 @@ rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * If the key exists already in the table, this API updates its value + * with 'data' passed in this API. It is the responsibility of + * the application to manage any memory associated with the old value. + * The readers might still be using the old value even after this API + * has returned. * * @param h * Hash table to add the key to. @@ -243,10 +267,14 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. - * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is enabled, + * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or + * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, * the key index returned by rte_hash_add_key_xxx APIs will not be * freed by this API. rte_hash_free_key_with_position API must be called * additionally to free the index associated with the key. + * rte_hash_free_key_with_position API should be called after all + * the readers have stopped referencing the entry corresponding to + * this key. RCU mechanisms could be used to determine such a state. * * @param h * Hash table to remove the key from. @@ -268,10 +296,14 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. - * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is enabled, + * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or + * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, * the key index returned by rte_hash_add_key_xxx APIs will not be * freed by this API. rte_hash_free_key_with_position API must be called * additionally to free the index associated with the key. + * rte_hash_free_key_with_position API should be called after all + * the readers have stopped referencing the entry corresponding to + * this key. RCU mechanisms could be used to determine such a state. * * @param h * Hash table to remove the key from. @@ -318,9 +350,12 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, * of the key. This operation is not multi-thread safe and should * only be called from one thread by default. Thread safety * can be enabled by setting flag during table creation. - * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is enabled, - * this API must be called, with the key index returned by rte_hash_add_key_xxx - * APIs, after the key is deleted using rte_hash_del_key_xxx APIs. + * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL or + * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * the key index returned by rte_hash_del_key_xxx APIs must be freed + * using this API. This API should be called after all the readers + * have stopped referencing the entry corresponding to this key. + * RCU mechanisms could be used to determine such a state. * This API does not validate if the key is already freed. * * @param h From patchwork Fri Oct 26 05:37:33 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 149580 Delivered-To: patch@linaro.org Received: by 2002:a2e:299d:0:0:0:0:0 with SMTP id p29-v6csp341729ljp; Thu, 25 Oct 2018 22:38:15 -0700 (PDT) X-Google-Smtp-Source: AJdET5fNdyUM4ogHTDyk1vKgZFmeoxaCgq+0FZfVvH8irIw3SNPMchk/2NNVgZjFexyDz18HfRU8 X-Received: by 2002:adf:9403:: with SMTP id 3-v6mr4349301wrq.54.1540532295916; Thu, 25 Oct 2018 22:38:15 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1540532295; cv=none; d=google.com; s=arc-20160816; b=rmClobWyco5dXQCBIzoiK3sL205bYHP0t9Szon3jMho7b+9t7Lu6CJzHu76QVicWEu C/oB8I96DGJmbMQJHfR/3LwwWcYmPOZDvC9quIufWCnUV5vO41tC/L0GlGLhSClwpexv b/Pfbpg2zWTX/dRxiPL84XvfwZt1u9wLAGyoUknJwHJGz6APeHCG7A3M6a+lH3W4E3zA FIK+oAdYOQueNzXVgIvOySor3+N8UWTzV/u4nRv43hicP+Ywq7r9fid5lFvIiobtd0Pk hidg7sqt1WzSr1AAvbS8bQoVBJkRX1C0zka+KUAcGTierFvaqw1SSqJL5LsDuw29fVtS 4VFQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:references:in-reply-to :message-id:date:cc:to:from; bh=NaP2Edp6DG3e0YchSE6kvCXeJ0aVn91U89CH7/cyqos=; b=fcUprcvB8gZ/zff6zsoVzlLw0D7DvwHh+iuHTgCSMgyyi0JIrx4eeaSM4qxy99IzBP r2jrX31feLgLAtcFaYYutwLudGR+NYjVXnVEvHY0HkF0q0ug0+8CA9yW7/PWqcLPYFOk 0FicX/o+EtWCLEubhDAOkU5uYhD9Rwe9KqJo0doDGd2ssd0rxHu7VprY6pCWnz2KiG58 TtYlQRmHeo5TPKnNc3QNgAaMlg1NxhzExU9pbX8G2U8rQHxcxuyEEOlfQzftsKiPXIlT giPU6cNJfxBin3/FTGeq3Vl1RpJZ5xfsT9iVcqK0p+r4P9al9iOpK3IvMDV99UEKPjYC h3WQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Return-Path: Received: from dpdk.org (dpdk.org. [92.243.14.124]) by mx.google.com with ESMTP id f2-v6si3388327wrc.28.2018.10.25.22.38.15; Thu, 25 Oct 2018 22:38:15 -0700 (PDT) Received-SPF: pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) client-ip=92.243.14.124; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id E23321B105; Fri, 26 Oct 2018 07:37:55 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id DA1815F13 for ; Fri, 26 Oct 2018 07:37:45 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 82951A78; Thu, 25 Oct 2018 22:37:45 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.14.139]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 140503F71D; Thu, 25 Oct 2018 22:37:45 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, yipeng1.wang@intel.com, honnappa.nagarahalli@arm.com, dharmik.thakkar@arm.com, gavin.hu@arm.com, nd@arm.com Date: Fri, 26 Oct 2018 00:37:33 -0500 Message-Id: <1540532253-112591-6-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1540532253-112591-1-git-send-email-honnappa.nagarahalli@arm.com> References: <1540532253-112591-1-git-send-email-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH v7 5/5] test/hash: read-write lock-free concurrency test 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" From: Dharmik Thakkar Unit tests to check for hash lookup and bulk-lookup perf with lock-free enabled and with lock-free disabled. Unit tests performed with readers running in parallel with writers. Tests include: - hash lookup on existing keys with: - hash add causing NO key-shifts of existing keys in the table - hash lookup on existing keys likely to be on shift-path with: - hash add causing key-shifts of existing keys in the table - hash lookup on existing keys NOT likely to be on shift-path with: - hash add causing key-shifts of existing keys in the table - hash lookup on non-existing keys with: - hash add causing NO key-shifts of existing keys in the table - hash add causing key-shifts of existing keys in the table - hash lookup on keys likely to be on shift-path with: - multiple writers causing key-shifts of existing keys in the table Signed-off-by: Dharmik Thakkar Reviewed-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Yipeng Wang Acked-by: Bruce Richardson --- test/test/Makefile | 1 + test/test/autotest_data.py | 6 + test/test/meson.build | 2 + test/test/test_hash_readwrite_lf.c | 1220 ++++++++++++++++++++++++++++++++++++ 4 files changed, 1229 insertions(+) create mode 100644 test/test/test_hash_readwrite_lf.c -- 2.7.4 diff --git a/test/test/Makefile b/test/test/Makefile index 8c347e4..1b5c070 100644 --- a/test/test/Makefile +++ b/test/test/Makefile @@ -116,6 +116,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_functions.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_scaling.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_multiwriter.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite.c +SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c diff --git a/test/test/autotest_data.py b/test/test/autotest_data.py index 51f8e16..4eae588 100644 --- a/test/test/autotest_data.py +++ b/test/test/autotest_data.py @@ -580,6 +580,12 @@ "Report": None, }, { + "Name": "Hash read-write lock-free concurrency autotest", + "Command": "hash_readwrite_lf_autotest", + "Func": default_autotest, + "Report": None, + }, + { "Name": "Power autotest", "Command": "power_autotest", "Func": default_autotest, diff --git a/test/test/meson.build b/test/test/meson.build index 90d6607..faef5a4 100644 --- a/test/test/meson.build +++ b/test/test/meson.build @@ -46,6 +46,7 @@ test_sources = files('commands.c', 'test_hash_multiwriter.c', 'test_hash_readwrite.c', 'test_hash_perf.c', + 'test_hash_readwrite_lf.c', 'test_hash_scaling.c', 'test_interrupts.c', 'test_kni.c', @@ -174,6 +175,7 @@ test_names = [ 'hash_functions_autotest', 'hash_multiwriter_autotest', 'hash_perf_autotest', + 'hash_readwrite_lf_autotest', 'interrupt_autotest', 'kni_autotest', 'kvargs_autotest', diff --git a/test/test/test_hash_readwrite_lf.c b/test/test/test_hash_readwrite_lf.c new file mode 100644 index 0000000..cbfd932 --- /dev/null +++ b/test/test/test_hash_readwrite_lf.c @@ -0,0 +1,1220 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Arm Limited + */ + +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "test.h" + +#ifndef RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF +#define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0 +#endif + +#define BULK_LOOKUP_SIZE 32 + +#define RUN_WITH_HTM_DISABLED 0 + +#if (RUN_WITH_HTM_DISABLED) + +#define TOTAL_ENTRY (5*1024) +#define TOTAL_INSERT (5*1024) + +#else + +#define TOTAL_ENTRY (4*1024*1024) +#define TOTAL_INSERT (4*1024*1024) + +#endif + +#define READ_FAIL 1 +#define READ_PASS_NO_KEY_SHIFTS 2 +#define READ_PASS_SHIFT_PATH 4 +#define READ_PASS_NON_SHIFT_PATH 8 +#define BULK_LOOKUP 16 +#define NUM_TEST 3 +unsigned int rwc_core_cnt[NUM_TEST] = {1, 2, 4}; + +struct rwc_perf { + uint32_t w_no_ks_r_hit[2][NUM_TEST]; + uint32_t w_no_ks_r_miss[2][NUM_TEST]; + uint32_t w_ks_r_hit_nsp[2][NUM_TEST]; + uint32_t w_ks_r_hit_sp[2][NUM_TEST]; + uint32_t w_ks_r_miss[2][NUM_TEST]; + uint32_t multi_rw[NUM_TEST - 1][2][NUM_TEST]; +}; + +static struct rwc_perf rwc_lf_results, rwc_non_lf_results; + +struct { + uint32_t *keys; + uint32_t *keys_no_ks; + uint32_t *keys_ks; + uint32_t *keys_absent; + uint32_t *keys_shift_path; + uint32_t *keys_non_shift_path; + uint32_t count_keys_no_ks; + uint32_t count_keys_ks; + uint32_t count_keys_absent; + uint32_t count_keys_shift_path; + uint32_t count_keys_non_shift_path; + uint32_t single_insert; + struct rte_hash *h; +} tbl_rwc_test_param; + +static rte_atomic64_t gread_cycles; +static rte_atomic64_t greads; + +static volatile uint8_t writer_done; +static volatile uint8_t multi_writer_done[4]; + +uint16_t enabled_core_ids[RTE_MAX_LCORE]; + +uint8_t *scanned_bkts; + +static inline int +get_enabled_cores_list(void) +{ + uint32_t i = 0; + uint16_t core_id; + uint32_t max_cores = rte_lcore_count(); + for (core_id = 0; core_id < RTE_MAX_LCORE && i < max_cores; core_id++) { + if (rte_lcore_is_enabled(core_id)) { + enabled_core_ids[i] = core_id; + i++; + } + } + + if (i != max_cores) { + printf("Number of enabled cores in list is different from " + "number given by rte_lcore_count()\n"); + return -1; + } + return 0; +} + +static inline int +check_bucket(uint32_t bkt_idx, uint32_t key) +{ + uint32_t iter; + uint32_t prev_iter; + uint32_t diff; + uint32_t count = 0; + const void *next_key; + void *next_data; + + /* Temporary bucket to hold the keys */ + uint32_t keys_in_bkt[8]; + + iter = bkt_idx * 8; + prev_iter = iter; + while (rte_hash_iterate(tbl_rwc_test_param.h, + &next_key, &next_data, &iter) >= 0) { + + /* Check for duplicate entries */ + if (*(const uint32_t *)next_key == key) + return 1; + + /* Identify if there is any free entry in the bucket */ + diff = iter - prev_iter; + if (diff > 1) + break; + + prev_iter = iter; + keys_in_bkt[count] = *(const uint32_t *)next_key; + count++; + + /* All entries in the bucket are occupied */ + if (count == 8) { + + /* + * Check if bucket was not scanned before, to avoid + * duplicate keys. + */ + if (scanned_bkts[bkt_idx] == 0) { + /* + * Since this bucket (pointed to by bkt_idx) is + * full, it is likely that key(s) in this + * bucket will be on the shift path, when + * collision occurs. Thus, add it to + * keys_shift_path. + */ + memcpy(tbl_rwc_test_param.keys_shift_path + + tbl_rwc_test_param.count_keys_shift_path + , keys_in_bkt, 32); + tbl_rwc_test_param.count_keys_shift_path += 8; + scanned_bkts[bkt_idx] = 1; + } + return -1; + } + } + return 0; +} + +static int +generate_keys(void) +{ + uint32_t *keys = NULL; + uint32_t *keys_no_ks = NULL; + uint32_t *keys_ks = NULL; + uint32_t *keys_absent = NULL; + uint32_t *keys_non_shift_path = NULL; + uint32_t *found = NULL; + uint32_t count_keys_no_ks = 0; + uint32_t count_keys_ks = 0; + uint32_t i; + + /* + * keys will consist of a) keys whose addition to the hash table + * will result in shifting of the existing keys to their alternate + * locations b) keys whose addition to the hash table will not result + * in shifting of the existing keys. + */ + keys = rte_malloc(NULL, sizeof(uint32_t) * TOTAL_INSERT, 0); + if (keys == NULL) { + printf("RTE_MALLOC failed\n"); + goto err; + } + + /* + * keys_no_ks (no key-shifts): Subset of 'keys' - consists of keys that + * will NOT result in shifting of the existing keys to their alternate + * locations. Roughly around 900K keys. + */ + keys_no_ks = rte_malloc(NULL, sizeof(uint32_t) * TOTAL_INSERT, 0); + if (keys_no_ks == NULL) { + printf("RTE_MALLOC failed\n"); + goto err; + } + + /* + * keys_ks (key-shifts): Subset of 'keys' - consists of keys that will + * result in shifting of the existing keys to their alternate locations. + * Roughly around 146K keys. There might be repeating keys. More code is + * required to filter out these keys which will complicate the test case + */ + keys_ks = rte_malloc(NULL, sizeof(uint32_t) * TOTAL_INSERT, 0); + if (keys_ks == NULL) { + printf("RTE_MALLOC failed\n"); + goto err; + } + + /* Used to identify keys not inserted in the hash table */ + found = rte_zmalloc(NULL, sizeof(uint32_t) * TOTAL_INSERT, 0); + if (found == NULL) { + printf("RTE_MALLOC failed\n"); + goto err; + } + + /* + * This consist of keys not inserted to the hash table. + * Used to test perf of lookup on keys that do not exist in the table. + */ + keys_absent = rte_malloc(NULL, sizeof(uint32_t) * TOTAL_INSERT, 0); + if (keys_absent == NULL) { + printf("RTE_MALLOC failed\n"); + goto err; + } + + /* + * This consist of keys which are likely to be on the shift + * path (i.e. being moved to alternate location), when collision occurs + * on addition of a key to an already full primary bucket. + * Used to test perf of lookup on keys that are on the shift path. + */ + tbl_rwc_test_param.keys_shift_path = rte_malloc(NULL, sizeof(uint32_t) * + TOTAL_INSERT, 0); + if (tbl_rwc_test_param.keys_shift_path == NULL) { + printf("RTE_MALLOC failed\n"); + goto err; + } + + /* + * This consist of keys which are never on the shift + * path (i.e. being moved to alternate location), when collision occurs + * on addition of a key to an already full primary bucket. + * Used to test perf of lookup on keys that are not on the shift path. + */ + keys_non_shift_path = rte_malloc(NULL, sizeof(uint32_t) * TOTAL_INSERT, + 0); + if (keys_non_shift_path == NULL) { + printf("RTE_MALLOC failed\n"); + goto err; + } + + + hash_sig_t sig; + uint32_t prim_bucket_idx; + int ret; + uint32_t num_buckets; + uint32_t bucket_bitmask; + num_buckets = rte_align32pow2(TOTAL_ENTRY) / 8; + bucket_bitmask = num_buckets - 1; + + /* + * Used to mark bkts in which at least one key was shifted to its + * alternate location + */ + scanned_bkts = rte_malloc(NULL, sizeof(uint8_t) * num_buckets, 0); + if (scanned_bkts == NULL) { + printf("RTE_MALLOC failed\n"); + goto err; + } + + tbl_rwc_test_param.keys = keys; + tbl_rwc_test_param.keys_no_ks = keys_no_ks; + tbl_rwc_test_param.keys_ks = keys_ks; + tbl_rwc_test_param.keys_absent = keys_absent; + tbl_rwc_test_param.keys_non_shift_path = keys_non_shift_path; + /* Generate keys by adding previous two keys, neglect overflow */ + printf("Generating keys...\n"); + keys[0] = 0; + keys[1] = 1; + for (i = 2; i < TOTAL_INSERT; i++) + keys[i] = keys[i-1] + keys[i-2]; + + /* Segregate keys into keys_no_ks and keys_ks */ + for (i = 0; i < TOTAL_INSERT; i++) { + /* Check if primary bucket has space.*/ + sig = rte_hash_hash(tbl_rwc_test_param.h, + tbl_rwc_test_param.keys+i); + prim_bucket_idx = sig & bucket_bitmask; + ret = check_bucket(prim_bucket_idx, keys[i]); + if (ret < 0) { + /* + * Primary bucket is full, this key will result in + * shifting of the keys to their alternate locations. + */ + keys_ks[count_keys_ks] = keys[i]; + count_keys_ks++; + } else if (ret == 0) { + /* + * Primary bucket has space, this key will not result in + * shifting of the keys. Hence, add key to the table. + */ + ret = rte_hash_add_key_data(tbl_rwc_test_param.h, + keys+i, + (void *)((uintptr_t)i)); + if (ret < 0) { + printf("writer failed %"PRIu32"\n", i); + break; + } + keys_no_ks[count_keys_no_ks] = keys[i]; + count_keys_no_ks++; + } + } + + for (i = 0; i < count_keys_no_ks; i++) { + /* + * Identify keys in keys_no_ks with value less than + * 4M (HTM enabled) OR 5K (HTM disabled) + */ + if (keys_no_ks[i] < TOTAL_INSERT) + found[keys_no_ks[i]]++; + } + + for (i = 0; i < count_keys_ks; i++) { + /* + * Identify keys in keys_ks with value less than + * 4M (HTM enabled) OR 5K (HTM disabled) + */ + if (keys_ks[i] < TOTAL_INSERT) + found[keys_ks[i]]++; + } + + uint32_t count_keys_absent = 0; + for (i = 0; i < TOTAL_INSERT; i++) { + /* + * Identify missing keys between 0 and + * 4M (HTM enabled) OR 5K (HTM disabled) + */ + if (found[i] == 0) + keys_absent[count_keys_absent++] = i; + } + + /* Find keys that will not be on the shift path */ + uint32_t iter; + const void *next_key; + void *next_data; + uint32_t count = 0; + for (i = 0; i < num_buckets; i++) { + /* Check bucket for no keys shifted to alternate locations */ + if (scanned_bkts[i] == 0) { + iter = i * 8; + while (rte_hash_iterate(tbl_rwc_test_param.h, + &next_key, &next_data, &iter) >= 0) { + + /* Check if key belongs to the current bucket */ + if (i >= (iter-1)/8) + keys_non_shift_path[count++] + = *(const uint32_t *)next_key; + else + break; + } + } + } + + tbl_rwc_test_param.count_keys_no_ks = count_keys_no_ks; + tbl_rwc_test_param.count_keys_ks = count_keys_ks; + tbl_rwc_test_param.count_keys_absent = count_keys_absent; + tbl_rwc_test_param.count_keys_non_shift_path = count; + + printf("\nCount of keys NOT causing shifting of existing keys to " + "alternate location: %d\n", tbl_rwc_test_param.count_keys_no_ks); + printf("\nCount of keys causing shifting of existing keys to alternate " + "locations: %d\n\n", tbl_rwc_test_param.count_keys_ks); + printf("Count of absent keys that will never be added to the hash " + "table: %d\n\n", tbl_rwc_test_param.count_keys_absent); + printf("Count of keys likely to be on the shift path: %d\n\n", + tbl_rwc_test_param.count_keys_shift_path); + printf("Count of keys not likely to be on the shift path: %d\n\n", + tbl_rwc_test_param.count_keys_non_shift_path); + + rte_free(found); + rte_hash_free(tbl_rwc_test_param.h); + return 0; + +err: + rte_free(keys); + rte_free(keys_no_ks); + rte_free(keys_ks); + rte_free(keys_absent); + rte_free(found); + rte_free(tbl_rwc_test_param.keys_shift_path); + rte_free(scanned_bkts); + return -1; +} + +static int +init_params(int rwc_lf, int use_jhash, int htm) +{ + struct rte_hash *handle; + + struct rte_hash_parameters hash_params = { + .entries = TOTAL_ENTRY, + .key_len = sizeof(uint32_t), + .hash_func_init_val = 0, + .socket_id = rte_socket_id(), + }; + + if (use_jhash) + hash_params.hash_func = rte_jhash; + else + hash_params.hash_func = rte_hash_crc; + + if (rwc_lf) + hash_params.extra_flag = + RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF | + RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD; + else if (htm) + hash_params.extra_flag = + RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT | + RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY | + RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD; + else + hash_params.extra_flag = + RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY | + RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD; + + hash_params.name = "tests"; + + handle = rte_hash_create(&hash_params); + if (handle == NULL) { + printf("hash creation failed"); + return -1; + } + + tbl_rwc_test_param.h = handle; + return 0; +} + +static int +test_rwc_reader(__attribute__((unused)) void *arg) +{ + uint32_t i, j; + int ret; + uint64_t begin, cycles; + uint32_t loop_cnt = 0; + uint8_t read_type = (uint8_t)((uintptr_t)arg); + uint32_t read_cnt; + uint32_t *keys; + uint32_t extra_keys; + int32_t *pos; + void *temp_a[BULK_LOOKUP_SIZE]; + + /* Used to identify keys not inserted in the hash table */ + pos = rte_zmalloc(NULL, sizeof(uint32_t) * BULK_LOOKUP_SIZE, 0); + if (pos == NULL) { + printf("RTE_MALLOC failed\n"); + return -1; + } + + if (read_type & READ_FAIL) { + keys = tbl_rwc_test_param.keys_absent; + read_cnt = tbl_rwc_test_param.count_keys_absent; + } else if (read_type & READ_PASS_NO_KEY_SHIFTS) { + keys = tbl_rwc_test_param.keys_no_ks; + read_cnt = tbl_rwc_test_param.count_keys_no_ks; + } else if (read_type & READ_PASS_SHIFT_PATH) { + keys = tbl_rwc_test_param.keys_shift_path; + read_cnt = tbl_rwc_test_param.count_keys_shift_path; + } else { + keys = tbl_rwc_test_param.keys_non_shift_path; + read_cnt = tbl_rwc_test_param.count_keys_non_shift_path; + } + + extra_keys = read_cnt & (BULK_LOOKUP_SIZE - 1); + + begin = rte_rdtsc_precise(); + do { + if (read_type & BULK_LOOKUP) { + for (i = 0; i < (read_cnt - extra_keys); + i += BULK_LOOKUP_SIZE) { + /* Array of pointer to the list of keys */ + for (j = 0; j < BULK_LOOKUP_SIZE; j++) + temp_a[j] = keys + i + j; + + rte_hash_lookup_bulk(tbl_rwc_test_param.h, + (const void **) + ((uintptr_t)temp_a), + BULK_LOOKUP_SIZE, pos); + /* Validate lookup result */ + for (j = 0; j < BULK_LOOKUP_SIZE; j++) + if ((read_type & READ_FAIL && + pos[j] != -ENOENT) || + (!(read_type & READ_FAIL) && + pos[j] == -ENOENT)) { + printf("lookup failed!" + "%"PRIu32"\n", + keys[i + j]); + return -1; + } + } + for (j = 0; j < extra_keys; j++) + temp_a[j] = keys + i + j; + + rte_hash_lookup_bulk(tbl_rwc_test_param.h, + (const void **) + ((uintptr_t)temp_a), + extra_keys, pos); + for (j = 0; j < extra_keys; j++) + if ((read_type & READ_FAIL && + pos[j] != -ENOENT) || + (!(read_type & READ_FAIL) && + pos[j] == -ENOENT)) { + printf("lookup failed! %"PRIu32"\n", + keys[i + j]); + return -1; + } + } else { + for (i = 0; i < read_cnt; i++) { + ret = rte_hash_lookup + (tbl_rwc_test_param.h, keys + i); + if (((read_type & READ_FAIL) && + (ret != -ENOENT)) || + (!(read_type & READ_FAIL) && + ret == -ENOENT)) { + printf("lookup failed! %"PRIu32"\n", + keys[i]); + return -1; + } + } + } + loop_cnt++; + } while (!writer_done); + + cycles = rte_rdtsc_precise() - begin; + rte_atomic64_add(&gread_cycles, cycles); + rte_atomic64_add(&greads, read_cnt*loop_cnt); + return 0; +} + +static int +write_keys(uint8_t key_shift) +{ + uint32_t i; + int ret; + uint32_t key_cnt; + uint32_t *keys; + if (key_shift) { + key_cnt = tbl_rwc_test_param.count_keys_ks; + keys = tbl_rwc_test_param.keys_ks; + } else { + key_cnt = tbl_rwc_test_param.count_keys_no_ks; + keys = tbl_rwc_test_param.keys_no_ks; + } + for (i = 0; i < key_cnt; i++) { + ret = rte_hash_add_key(tbl_rwc_test_param.h, keys + i); + if (!key_shift && ret < 0) { + printf("writer failed %"PRIu32"\n", i); + return -1; + } + } + return 0; +} + +static int +test_rwc_multi_writer(__attribute__((unused)) void *arg) +{ + uint32_t i, offset; + uint32_t pos_core = (uint32_t)((uintptr_t)arg); + offset = pos_core * tbl_rwc_test_param.single_insert; + for (i = offset; i < offset + tbl_rwc_test_param.single_insert; i++) + rte_hash_add_key(tbl_rwc_test_param.h, + tbl_rwc_test_param.keys_ks + i); + multi_writer_done[pos_core] = 1; + return 0; +} + +/* + * Test lookup perf: + * Reader(s) lookup keys present in the table. + */ +static int +test_hash_add_no_ks_lookup_hit(struct rwc_perf *rwc_perf_results, int rwc_lf, + int htm) +{ + unsigned int n, m; + uint64_t i; + int use_jhash = 0; + uint8_t key_shift = 0; + uint8_t read_type = READ_PASS_NO_KEY_SHIFTS; + + rte_atomic64_init(&greads); + rte_atomic64_init(&gread_cycles); + + if (init_params(rwc_lf, use_jhash, htm) != 0) + goto err; + printf("\nTest: Hash add - no key-shifts, read - hit\n"); + for (m = 0; m < 2; m++) { + if (m == 1) { + printf("\n** With bulk-lookup **\n"); + read_type |= BULK_LOOKUP; + } + for (n = 0; n < NUM_TEST; n++) { + unsigned int tot_lcore = rte_lcore_count(); + if (tot_lcore < rwc_core_cnt[n] + 1) + goto finish; + + printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); + + rte_atomic64_clear(&greads); + rte_atomic64_clear(&gread_cycles); + + rte_hash_reset(tbl_rwc_test_param.h); + writer_done = 0; + if (write_keys(key_shift) < 0) + goto err; + writer_done = 1; + for (i = 1; i <= rwc_core_cnt[n]; i++) + rte_eal_remote_launch(test_rwc_reader, + (void *)(uintptr_t)read_type, + enabled_core_ids[i]); + rte_eal_mp_wait_lcore(); + + for (i = 1; i <= rwc_core_cnt[n]; i++) + if (lcore_config[i].ret < 0) + goto err; + + unsigned long long cycles_per_lookup = + rte_atomic64_read(&gread_cycles) / + rte_atomic64_read(&greads); + rwc_perf_results->w_no_ks_r_hit[m][n] + = cycles_per_lookup; + printf("Cycles per lookup: %llu\n", cycles_per_lookup); + } + } + +finish: + rte_hash_free(tbl_rwc_test_param.h); + return 0; + +err: + rte_hash_free(tbl_rwc_test_param.h); + return -1; +} + +/* + * Test lookup perf: + * Reader(s) lookup keys absent in the table while + * 'Main' thread adds with no key-shifts. + */ +static int +test_hash_add_no_ks_lookup_miss(struct rwc_perf *rwc_perf_results, int rwc_lf, + int htm) +{ + unsigned int n, m; + uint64_t i; + int use_jhash = 0; + uint8_t key_shift = 0; + uint8_t read_type = READ_FAIL; + int ret; + + rte_atomic64_init(&greads); + rte_atomic64_init(&gread_cycles); + + if (init_params(rwc_lf, use_jhash, htm) != 0) + goto err; + printf("\nTest: Hash add - no key-shifts, Hash lookup - miss\n"); + for (m = 0; m < 2; m++) { + if (m == 1) { + printf("\n** With bulk-lookup **\n"); + read_type |= BULK_LOOKUP; + } + for (n = 0; n < NUM_TEST; n++) { + unsigned int tot_lcore = rte_lcore_count(); + if (tot_lcore < rwc_core_cnt[n] + 1) + goto finish; + + printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); + + rte_atomic64_clear(&greads); + rte_atomic64_clear(&gread_cycles); + + rte_hash_reset(tbl_rwc_test_param.h); + writer_done = 0; + + for (i = 1; i <= rwc_core_cnt[n]; i++) + rte_eal_remote_launch(test_rwc_reader, + (void *)(uintptr_t)read_type, + enabled_core_ids[i]); + ret = write_keys(key_shift); + writer_done = 1; + rte_eal_mp_wait_lcore(); + + if (ret < 0) + goto err; + for (i = 1; i <= rwc_core_cnt[n]; i++) + if (lcore_config[i].ret < 0) + goto err; + + unsigned long long cycles_per_lookup = + rte_atomic64_read(&gread_cycles) / + rte_atomic64_read(&greads); + rwc_perf_results->w_no_ks_r_miss[m][n] + = cycles_per_lookup; + printf("Cycles per lookup: %llu\n", cycles_per_lookup); + } + } + +finish: + rte_hash_free(tbl_rwc_test_param.h); + return 0; + +err: + rte_hash_free(tbl_rwc_test_param.h); + return -1; +} + +/* + * Test lookup perf: + * Reader(s) lookup keys present in the table and not likely to be on the + * shift path while 'Main' thread adds keys causing key-shifts. + */ +static int +test_hash_add_ks_lookup_hit_non_sp(struct rwc_perf *rwc_perf_results, + int rwc_lf, int htm) +{ + unsigned int n, m; + uint64_t i; + int use_jhash = 0; + int ret; + uint8_t key_shift; + uint8_t read_type = READ_PASS_NON_SHIFT_PATH; + + rte_atomic64_init(&greads); + rte_atomic64_init(&gread_cycles); + + if (init_params(rwc_lf, use_jhash, htm) != 0) + goto err; + printf("\nTest: Hash add - key shift, Hash lookup - hit" + " (non-shift-path)\n"); + for (m = 0; m < 2; m++) { + if (m == 1) { + printf("\n** With bulk-lookup **\n"); + read_type |= BULK_LOOKUP; + } + for (n = 0; n < NUM_TEST; n++) { + unsigned int tot_lcore = rte_lcore_count(); + if (tot_lcore < rwc_core_cnt[n] + 1) + goto finish; + + printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); + + rte_atomic64_clear(&greads); + rte_atomic64_clear(&gread_cycles); + + rte_hash_reset(tbl_rwc_test_param.h); + writer_done = 0; + key_shift = 0; + if (write_keys(key_shift) < 0) + goto err; + for (i = 1; i <= rwc_core_cnt[n]; i++) + rte_eal_remote_launch(test_rwc_reader, + (void *)(uintptr_t)read_type, + enabled_core_ids[i]); + key_shift = 1; + ret = write_keys(key_shift); + writer_done = 1; + rte_eal_mp_wait_lcore(); + + if (ret < 0) + goto err; + for (i = 1; i <= rwc_core_cnt[n]; i++) + if (lcore_config[i].ret < 0) + goto err; + + unsigned long long cycles_per_lookup = + rte_atomic64_read(&gread_cycles) / + rte_atomic64_read(&greads); + rwc_perf_results->w_ks_r_hit_nsp[m][n] + = cycles_per_lookup; + printf("Cycles per lookup: %llu\n", cycles_per_lookup); + } + } + +finish: + rte_hash_free(tbl_rwc_test_param.h); + return 0; + +err: + rte_hash_free(tbl_rwc_test_param.h); + return -1; +} + +/* + * Test lookup perf: + * Reader(s) lookup keys present in the table and likely on the shift-path while + * 'Main' thread adds keys causing key-shifts. + */ +static int +test_hash_add_ks_lookup_hit_sp(struct rwc_perf *rwc_perf_results, int rwc_lf, + int htm) +{ + unsigned int n, m; + uint64_t i; + int use_jhash = 0; + int ret; + uint8_t key_shift; + uint8_t read_type = READ_PASS_SHIFT_PATH; + + rte_atomic64_init(&greads); + rte_atomic64_init(&gread_cycles); + + if (init_params(rwc_lf, use_jhash, htm) != 0) + goto err; + printf("\nTest: Hash add - key shift, Hash lookup - hit (shift-path)" + "\n"); + + for (m = 0; m < 2; m++) { + if (m == 1) { + printf("\n** With bulk-lookup **\n"); + read_type |= BULK_LOOKUP; + } + for (n = 0; n < NUM_TEST; n++) { + unsigned int tot_lcore = rte_lcore_count(); + if (tot_lcore < rwc_core_cnt[n]) + goto finish; + + printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); + rte_atomic64_clear(&greads); + rte_atomic64_clear(&gread_cycles); + + rte_hash_reset(tbl_rwc_test_param.h); + writer_done = 0; + key_shift = 0; + if (write_keys(key_shift) < 0) + goto err; + for (i = 1; i <= rwc_core_cnt[n]; i++) + rte_eal_remote_launch(test_rwc_reader, + (void *)(uintptr_t)read_type, + enabled_core_ids[i]); + key_shift = 1; + ret = write_keys(key_shift); + writer_done = 1; + rte_eal_mp_wait_lcore(); + + if (ret < 0) + goto err; + for (i = 1; i <= rwc_core_cnt[n]; i++) + if (lcore_config[i].ret < 0) + goto err; + + unsigned long long cycles_per_lookup = + rte_atomic64_read(&gread_cycles) / + rte_atomic64_read(&greads); + rwc_perf_results->w_ks_r_hit_sp[m][n] + = cycles_per_lookup; + printf("Cycles per lookup: %llu\n", cycles_per_lookup); + } + } + +finish: + rte_hash_free(tbl_rwc_test_param.h); + return 0; + +err: + rte_hash_free(tbl_rwc_test_param.h); + return -1; +} + +/* + * Test lookup perf: + * Reader(s) lookup keys absent in the table while + * 'Main' thread adds keys causing key-shifts. + */ +static int +test_hash_add_ks_lookup_miss(struct rwc_perf *rwc_perf_results, int rwc_lf, int + htm) +{ + unsigned int n, m; + uint64_t i; + int use_jhash = 0; + int ret; + uint8_t key_shift; + uint8_t read_type = READ_FAIL; + + rte_atomic64_init(&greads); + rte_atomic64_init(&gread_cycles); + + if (init_params(rwc_lf, use_jhash, htm) != 0) + goto err; + printf("\nTest: Hash add - key shift, Hash lookup - miss\n"); + for (m = 0; m < 2; m++) { + if (m == 1) { + printf("\n** With bulk-lookup **\n"); + read_type |= BULK_LOOKUP; + } + for (n = 0; n < NUM_TEST; n++) { + unsigned int tot_lcore = rte_lcore_count(); + if (tot_lcore < rwc_core_cnt[n] + 1) + goto finish; + + printf("\nNumber of readers: %u\n", rwc_core_cnt[n]); + + rte_atomic64_clear(&greads); + rte_atomic64_clear(&gread_cycles); + + rte_hash_reset(tbl_rwc_test_param.h); + writer_done = 0; + key_shift = 0; + if (write_keys(key_shift) < 0) + goto err; + for (i = 1; i <= rwc_core_cnt[n]; i++) + rte_eal_remote_launch(test_rwc_reader, + (void *)(uintptr_t)read_type, + enabled_core_ids[i]); + key_shift = 1; + ret = write_keys(key_shift); + writer_done = 1; + rte_eal_mp_wait_lcore(); + + if (ret < 0) + goto err; + for (i = 1; i <= rwc_core_cnt[n]; i++) + if (lcore_config[i].ret < 0) + goto err; + + unsigned long long cycles_per_lookup = + rte_atomic64_read(&gread_cycles) / + rte_atomic64_read(&greads); + rwc_perf_results->w_ks_r_miss[m][n] = cycles_per_lookup; + printf("Cycles per lookup: %llu\n", cycles_per_lookup); + } + } + +finish: + rte_hash_free(tbl_rwc_test_param.h); + return 0; + +err: + rte_hash_free(tbl_rwc_test_param.h); + return -1; +} + +/* + * Test lookup perf for multi-writer: + * Reader(s) lookup keys present in the table and likely on the shift-path while + * Writers add keys causing key-shiftsi. + * Writers are running in parallel, on different data plane cores. + */ +static int +test_hash_multi_add_lookup(struct rwc_perf *rwc_perf_results, int rwc_lf, + int htm) +{ + unsigned int n, m, k; + uint64_t i; + int use_jhash = 0; + uint8_t key_shift; + uint8_t read_type = READ_PASS_SHIFT_PATH; + + rte_atomic64_init(&greads); + rte_atomic64_init(&gread_cycles); + + if (init_params(rwc_lf, use_jhash, htm) != 0) + goto err; + printf("\nTest: Multi-add-lookup\n"); + uint8_t pos_core; + for (m = 1; m < NUM_TEST; m++) { + /* Calculate keys added by each writer */ + tbl_rwc_test_param.single_insert = + tbl_rwc_test_param.count_keys_ks / rwc_core_cnt[m]; + for (k = 0; k < 2; k++) { + if (k == 1) { + printf("\n** With bulk-lookup **\n"); + read_type |= BULK_LOOKUP; + } + for (n = 0; n < NUM_TEST; n++) { + unsigned int tot_lcore = rte_lcore_count(); + if (tot_lcore < (rwc_core_cnt[n] + + rwc_core_cnt[m] + 1)) + goto finish; + + printf("\nNumber of writers: %u", + rwc_core_cnt[m]); + printf("\nNumber of readers: %u\n", + rwc_core_cnt[n]); + + rte_atomic64_clear(&greads); + rte_atomic64_clear(&gread_cycles); + + rte_hash_reset(tbl_rwc_test_param.h); + writer_done = 0; + for (i = 0; i < 4; i++) + multi_writer_done[i] = 0; + key_shift = 0; + if (write_keys(key_shift) < 0) + goto err; + + /* Launch reader(s) */ + for (i = 1; i <= rwc_core_cnt[n]; i++) + rte_eal_remote_launch(test_rwc_reader, + (void *)(uintptr_t)read_type, + enabled_core_ids[i]); + key_shift = 1; + pos_core = 0; + + /* Launch writers */ + for (; i <= rwc_core_cnt[m] + + rwc_core_cnt[n]; i++) { + rte_eal_remote_launch + (test_rwc_multi_writer, + (void *)(uintptr_t)pos_core, + enabled_core_ids[i]); + pos_core++; + } + + /* Wait for writers to complete */ + for (i = 0; i < rwc_core_cnt[m]; i++) + while + (multi_writer_done[i] == 0); + writer_done = 1; + + rte_eal_mp_wait_lcore(); + + for (i = 1; i <= rwc_core_cnt[n]; i++) + if (lcore_config[i].ret < 0) + goto err; + + unsigned long long cycles_per_lookup = + rte_atomic64_read(&gread_cycles) + / rte_atomic64_read(&greads); + rwc_perf_results->multi_rw[m][k][n] + = cycles_per_lookup; + printf("Cycles per lookup: %llu\n", + cycles_per_lookup); + } + } + } + +finish: + rte_hash_free(tbl_rwc_test_param.h); + return 0; + +err: + rte_hash_free(tbl_rwc_test_param.h); + return -1; +} + +static int +test_hash_readwrite_lf_main(void) +{ + /* + * Variables used to choose different tests. + * rwc_lf indicates if read-write concurrency lock-free support is + * enabled. + * htm indicates if Hardware transactional memory support is enabled. + */ + int rwc_lf = 0; + int htm; + int use_jhash = 0; + if (rte_lcore_count() == 1) { + printf("More than one lcore is required " + "to do read write lock-free concurrency test\n"); + return -1; + } + + setlocale(LC_NUMERIC, ""); + + if (rte_tm_supported()) + htm = 1; + else + htm = 0; + + if (init_params(rwc_lf, use_jhash, htm) != 0) + return -1; + if (generate_keys() != 0) + return -1; + if (get_enabled_cores_list() != 0) + return -1; + + if (RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) { + rwc_lf = 1; + printf("Test lookup with read-write concurrency lock free support" + " enabled\n"); + if (test_hash_add_no_ks_lookup_hit(&rwc_lf_results, rwc_lf, + htm) < 0) + return -1; + if (test_hash_add_no_ks_lookup_miss(&rwc_lf_results, rwc_lf, + htm) < 0) + return -1; + if (test_hash_add_ks_lookup_hit_non_sp(&rwc_lf_results, rwc_lf, + htm) < 0) + return -1; + if (test_hash_add_ks_lookup_hit_sp(&rwc_lf_results, rwc_lf, + htm) < 0) + return -1; + if (test_hash_add_ks_lookup_miss(&rwc_lf_results, rwc_lf, htm) + < 0) + return -1; + if (test_hash_multi_add_lookup(&rwc_lf_results, rwc_lf, htm) + < 0) + return -1; + } + printf("\nTest lookup with read-write concurrency lock free support" + " disabled\n"); + rwc_lf = 0; + if (!htm) { + printf("With HTM Disabled\n"); + if (!RUN_WITH_HTM_DISABLED) { + printf("Enable RUN_WITH_HTM_DISABLED to test with" + " lock-free disabled"); + goto results; + } + } else + printf("With HTM Enabled\n"); + if (test_hash_add_no_ks_lookup_hit(&rwc_non_lf_results, rwc_lf, htm) + < 0) + return -1; + if (test_hash_add_no_ks_lookup_miss(&rwc_non_lf_results, rwc_lf, htm) + < 0) + return -1; + if (test_hash_add_ks_lookup_hit_non_sp(&rwc_non_lf_results, rwc_lf, + htm) < 0) + return -1; + if (test_hash_add_ks_lookup_hit_sp(&rwc_non_lf_results, rwc_lf, htm) + < 0) + return -1; + if (test_hash_add_ks_lookup_miss(&rwc_non_lf_results, rwc_lf, htm) < 0) + return -1; + if (test_hash_multi_add_lookup(&rwc_non_lf_results, rwc_lf, htm) < 0) + return -1; +results: + printf("\n\t\t\t\t\t\t********** Results summary **********\n\n"); + int i, j, k; + for (j = 0; j < 2; j++) { + if (j == 1) + printf("\n\t\t\t\t\t#######********** Bulk Lookup " + "**********#######\n\n"); + printf("_______\t\t_______\t\t_________\t___\t\t_________\t\t" + "\t\t\t\t_________________\n"); + printf("Writers\t\tReaders\t\tLock-free\tHTM\t\tTest-case\t\t\t" + "\t\t\tCycles per lookup\n"); + printf("_______\t\t_______\t\t_________\t___\t\t_________\t\t\t" + "\t\t\t_________________\n"); + for (i = 0; i < NUM_TEST; i++) { + printf("%u\t\t%u\t\t", 1, rwc_core_cnt[i]); + printf("Enabled\t\t"); + printf("N/A\t\t"); + printf("Hash add - no key-shifts, lookup - hit\t\t\t\t" + "%u\n\t\t\t\t\t\t\t\t", + rwc_lf_results.w_no_ks_r_hit[j][i]); + printf("Hash add - no key-shifts, lookup - miss\t\t\t\t" + "%u\n\t\t\t\t\t\t\t\t", + rwc_lf_results.w_no_ks_r_miss[j][i]); + printf("Hash add - key-shifts, lookup - hit" + "(non-shift-path)\t\t%u\n\t\t\t\t\t\t\t\t", + rwc_lf_results.w_ks_r_hit_nsp[j][i]); + printf("Hash add - key-shifts, lookup - hit " + "(shift-path)\t\t%u\n\t\t\t\t\t\t\t\t", + rwc_lf_results.w_ks_r_hit_sp[j][i]); + printf("Hash add - key-shifts, Hash lookup miss\t\t\t\t" + "%u\n\n\t\t\t\t", + rwc_lf_results.w_ks_r_miss[j][i]); + + printf("Disabled\t"); + if (htm) + printf("Enabled\t\t"); + else + printf("Disabled\t"); + printf("Hash add - no key-shifts, lookup - hit\t\t\t\t" + "%u\n\t\t\t\t\t\t\t\t", + rwc_non_lf_results.w_no_ks_r_hit[j][i]); + printf("Hash add - no key-shifts, lookup - miss\t\t\t\t" + "%u\n\t\t\t\t\t\t\t\t", + rwc_non_lf_results.w_no_ks_r_miss[j][i]); + printf("Hash add - key-shifts, lookup - hit " + "(non-shift-path)\t\t%u\n\t\t\t\t\t\t\t\t", + rwc_non_lf_results.w_ks_r_hit_nsp[j][i]); + printf("Hash add - key-shifts, lookup - hit " + "(shift-path)\t\t%u\n\t\t\t\t\t\t\t\t", + rwc_non_lf_results.w_ks_r_hit_sp[j][i]); + printf("Hash add - key-shifts, Hash lookup miss\t\t\t\t" + "%u\n", rwc_non_lf_results.w_ks_r_miss[j][i]); + + printf("_______\t\t_______\t\t_________\t___\t\t" + "_________\t\t\t\t\t\t_________________\n"); + } + + for (i = 1; i < NUM_TEST; i++) { + for (k = 0; k < NUM_TEST; k++) { + printf("%u", rwc_core_cnt[i]); + printf("\t\t%u\t\t", rwc_core_cnt[k]); + printf("Enabled\t\t"); + printf("N/A\t\t"); + printf("Multi-add-lookup\t\t\t\t\t\t%u\n\n\t\t" + "\t\t", + rwc_lf_results.multi_rw[i][j][k]); + printf("Disabled\t"); + if (htm) + printf("Enabled\t\t"); + else + printf("Disabled\t"); + printf("Multi-add-lookup\t\t\t\t\t\t%u\n", + rwc_non_lf_results.multi_rw[i][j][k]); + + printf("_______\t\t_______\t\t_________\t___" + "\t\t_________\t\t\t\t\t\t" + "_________________\n"); + } + } + } + rte_free(tbl_rwc_test_param.keys); + rte_free(tbl_rwc_test_param.keys_no_ks); + rte_free(tbl_rwc_test_param.keys_ks); + rte_free(tbl_rwc_test_param.keys_absent); + rte_free(tbl_rwc_test_param.keys_shift_path); + rte_free(scanned_bkts); + return 0; +} + +REGISTER_TEST_COMMAND(hash_readwrite_lf_autotest, test_hash_readwrite_lf_main);