From patchwork Mon Oct 22 20:35:17 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 149400 Delivered-To: patch@linaro.org Received: by 2002:a2e:29db:0:0:0:0:0 with SMTP id p88-v6csp109384ljp; Mon, 22 Oct 2018 13:35:28 -0700 (PDT) X-Google-Smtp-Source: ACcGV63K87me9hddV0SFrjA+Wr1GdqDyHun2rI5jdvsbvaauUq7knQtO1gmLyR2M78T2SYqetPQs X-Received: by 2002:a1c:838a:: with SMTP id f132-v6mr18326138wmd.51.1540240528371; Mon, 22 Oct 2018 13:35:28 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1540240528; cv=none; d=google.com; s=arc-20160816; b=KGc2h7G+sEAxVZw1VJsjHT4cHQFxAX+1WkXqi1vnE4cS43E7JxbmCiiKj7LrASZBOL Fb+ZgD/f8KKM4H+i21LCtluEyo/tfgtpecHvNyry8HNivDOTulnXickqSb4FNUgew7Hc MdqqGnHplD/SOjGeRixcZHqRUcEWc+WX2WxeR8vLydxcWzHgBP2yVV0Y4HY4hoisBWOO Fmqw2buvl8fWiW7Lol8KewaJaFLp+7dA4IL4lOWWIm5z0RbgJ1IvYlrrQp4tLimmu4OR CJNqtfSw2pkBjbHMlBMuKJhqAbd9+OYEo/cULvBREtpzcU8kdLOCaksoOEuhy5fo5rIc coxQ== 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 :content-transfer-encoding:mime-version:message-id:date:cc:to:from; bh=LcvmS3m7CUWUnvtlVKMHEyNH/zh7ypMK8ZWAWkTVY0Y=; b=jaGUeelogryFw43S4Pk0aijwg4x1SCtM0hziSNpnMx7fbGIrPvMKhjsI8G+FMiwyDc IA8zyBYYCUM/CQKb7xVUKc2/SvaoeBAm78wUIM5nStP8uK+6Ge/du6ZijA0qXppDgQml vXx8DAO4rRPbWQ8xAfz7HiGBF2ix0Al2vCK4Wbeg+v22BxsldgyXGIHF8JcBJNbWOdQc zA3j3C0ZIOo32BmzR3reVqRCDUDRGmO5Irg3ESNLHNnF8h3sTTqvqjZWodzGCNCaCRK2 1dJ+RguQdAskwstug46AnhzNDs7cQLFqtAWfKpn5a1ouzhqEQSNP3H207qSFwP39P0oJ GW1A== 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 a11-v6si221900wmg.143.2018.10.22.13.35.28; Mon, 22 Oct 2018 13:35:28 -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 022C41B472; Mon, 22 Oct 2018 22:35:28 +0200 (CEST) Received: from foss.arm.com (usa-sjc-mx-foss1.foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id C1EDF1B440 for ; Mon, 22 Oct 2018 22:35:26 +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 A16C5341; Mon, 22 Oct 2018 13:35:25 -0700 (PDT) Received: from localhost.localdomain (U202406.usa.Arm.com [10.118.106.64]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 3067F3F71D; Mon, 22 Oct 2018 13:35:25 -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, gavin.hu@arm.com, dharmik.thakkar@arm.com, nd@arm.com Date: Mon, 22 Oct 2018 15:35:17 -0500 Message-Id: <1540240517-4958-1-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 MIME-Version: 1.0 Subject: [dpdk-dev] [PATCH] doc/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 details of enabling lock free read write concurrency. Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu --- doc/guides/prog_guide/hash_lib.rst | 33 ++++++++++++++++++++++++++++----- 1 file changed, 28 insertions(+), 5 deletions(-) -- 2.7.4 diff --git a/doc/guides/prog_guide/hash_lib.rst b/doc/guides/prog_guide/hash_lib.rst index 76a1f32..f5beec1 100644 --- a/doc/guides/prog_guide/hash_lib.rst +++ b/doc/guides/prog_guide/hash_lib.rst @@ -1,5 +1,6 @@ .. SPDX-License-Identifier: BSD-3-Clause Copyright(c) 2010-2015 Intel Corporation. + Copyright(c) 2018 Arm Limited. .. _Hash_Library: @@ -38,7 +39,7 @@ The main methods exported by the hash are: * Lookup for entry with key: The key is provided as input. If an entry with the specified key is found in the hash (lookup hit), then the position of the entry is returned, otherwise (lookup miss) a negative value is returned. -Apart from these method explained above, the API allows the user three more options: +Apart from these methods explained above, the API provides the user with few more options: * Add / lookup / delete with key and precomputed hash: Both the key and its precomputed hash are provided as input. This allows the user to perform these operations faster, as hash is already computed. @@ -48,6 +49,9 @@ Apart from these method explained above, the API allows the user three more opti * Combination of the two options above: User can provide key, precomputed hash and data. +* Ability to not free the position of the entry in the hash upon calling delete. This is useful for multi-threaded scenarios where + readers continue to use the position even after the entry is deleted. + Also, the API contains a method to allow the user to look up entries in bursts, achieving higher performance than looking up individual entries, as the function prefetches next entries at the time it is operating with the first ones, which reduces significantly the impact of the necessary memory accesses. @@ -83,13 +87,20 @@ For concurrent writes, and concurrent reads and writes the following flag values Key add, delete, and table reset are protected from other writer threads. With only this flag set, readers are not protected from ongoing writes. * If the read/write concurrency (RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) is set, multithread read/write operation is safe - (i.e., no need to stop the readers from accessing the hash table until writers finish their updates. Reads and writes can operate table concurrently). + (i.e., application does not need to stop the readers from accessing the hash table until writers finish their updates. Readers and writers can operate on the table concurrently). + The library uses a reader-writer lock to provide the concurrency. * In addition to these two flag values, if the transactional memory flag (RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT) is also set, - hardware transactional memory will be used to guarantee the thread safety as long as it is supported by the hardware (for example the Intel® TSX support). + the reader-writer lock will use hardware transactional memory to guarantee thread safety as long as it is supported by the hardware (for example the Intel® TSX support). + If the platform supports Intel® TSX, it is advised to set the transactional memory flag, as this will speed up concurrent table operations. + Otherwise concurrent operations will be slower because of the overhead associated with the software locking mechanisms. + +* If lock free read/write concurrency (RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) is set, read/write concurrency is provided without using reader-writer lock. + For platforms (ex: current Arm based platforms), that do not support transactional memory, it is advised to set this flag to achieve greater scalability in performance. -If the platform supports Intel® TSX, it is advised to set the transactional memory flag, as this will speed up concurrent table operations. -Otherwise concurrent operations will be slower because of the overhead associated with the software locking mechanisms. +* If, do not free on delete (RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL) flag is set, the position of the entry in the hash is not freed upon calling delete. This flag is enabled + by default when lock free read/write concurrency is set. The application should free the position after all the readers have stopped referencing the position. + Where required, the application can make use of RCU mechanisms to determine when the readers have stopped referencing the position. Implementation Details ---------------------- @@ -148,6 +159,14 @@ key is considered not able to be stored. With random keys, this method allows the user to get around 90% of the table utilization, without having to drop any stored entry (LRU) or allocate more memory (extended buckets). + +Example of deletion: + +Similar to lookup, the key is searched in its primary and secondary buckets. If the key is found, the bucket +entry is marked as an empty slot. If the hash table was configured with 'no free on delete' or 'lock free read/write concurrency', +the position of the key is not freed. It is the responsibility of the user to free the position while making sure that +readers are not referencing the position anymore. + Entry distribution in hash table -------------------------------- @@ -240,6 +259,10 @@ The flow table operations on the application side are described below: * Delete flow: Delete the flow key from the hash. If the returned position is valid, use it to access the flow entry in the flow table to invalidate the information associated with the flow. +* Free flow: Free flow key position. If 'no free on delete' or 'lock-free read/write concurrency' flags are set, + wait till the readers are not referencing the position returned during add/delete flow and then free the position. + RCU mechanisms can be used to find out when the readers are not referencing the position anymore. + * Lookup flow: Lookup for the flow key in the hash. If the returned position is valid (flow lookup hit), use the returned position to access the flow entry in the flow table. Otherwise (flow lookup miss) there is no flow registered for the current packet.