From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 288EBA0487 for ; Fri, 5 Jul 2019 11:56:33 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id ED1691BE16; Fri, 5 Jul 2019 11:56:32 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by dpdk.org (Postfix) with ESMTP id A11EC1BE09 for ; Fri, 5 Jul 2019 11:56:31 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 014F81477; Fri, 5 Jul 2019 02:56:31 -0700 (PDT) Received: from phil-VirtualBox.shanghai.arm.com (unknown [10.169.109.155]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id D12DE3F246; Fri, 5 Jul 2019 02:56:28 -0700 (PDT) From: Phil Yang To: dev@dpdk.org Cc: thomas@monjalon.net, david.marchand@redhat.com, konstantin.ananyev@intel.com, jerinj@marvell.com, hemant.agrawal@nxp.com, Honnappa.Nagarahalli@arm.com, gavin.hu@arm.com, nd@arm.com, phil.yang@arm.com Date: Fri, 5 Jul 2019 17:56:02 +0800 Message-Id: <1562320565-17339-1-git-send-email-phil.yang@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1559750328-22377-2-git-send-email-phil.yang@arm.com> References: <1559750328-22377-2-git-send-email-phil.yang@arm.com> Subject: [dpdk-dev] [PATCH v2 0/3] MCS queued lock implementation 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" This patch set added MCS lock library and its unit test. The MCS lock (proposed by John M. Mellor-Crummey and Michael L. Scott) provides scalability by spinning on a CPU/thread local variable which avoids expensive cache bouncings. It provides fairness by maintaining a list of acquirers and passing the lock to each CPU/thread in the order they acquired the lock. References: 1. http://web.mit.edu/6.173/www/currentsemester/readings/R06-scalable-synchronization-1991.pdf 2. https://lwn.net/Articles/590243/ Micro benchmark (1M iterations): --------------------------------------------------------------------------------------------------------- MCS lock | spinlock | ticket lock --------------------------------------------------------------------------------------------------------- Test with lock on 20 cores... | Test with lock on 20 cores... | Test with lock on 20 cores... Core [0] Cost Time = 4221256 us | Core [0] Cost Time = 1948341 us | Core [0] cost time = 25388253 us Core [14] Cost Time = 4221260 us | Core [14] Cost Time = 5136122 us | Core [14] cost time = 25389593 us Core [28] Cost Time = 4221239 us | Core [28] Cost Time = 4849188 us | Core [28] cost time = 25387857 us Core [29] Cost Time = 4221190 us | Core [29] Cost Time = 3424137 us | Core [29] cost time = 25387625 us Core [30] Cost Time = 4221249 us | Core [30] Cost Time = 3455813 us | Core [30] cost time = 25387662 us Core [31] Cost Time = 4221090 us | Core [31] Cost Time = 4742221 us | Core [31] cost time = 25387968 us Core [32] Cost Time = 4221169 us | Core [32] Cost Time = 4955011 us | Core [32] cost time = 25387991 us Core [33] Cost Time = 4221192 us | Core [33] Cost Time = 3807345 us | Core [33] cost time = 25387679 us Core [34] Cost Time = 4221209 us | Core [34] Cost Time = 5011178 us | Core [34] cost time = 25389370 us Core [35] Cost Time = 4221232 us | Core [35] Cost Time = 4983119 us | Core [35] cost time = 25387899 us Core [36] Cost Time = 4221260 us | Core [36] Cost Time = 5178121 us | Core [36] cost time = 25389593 us Core [37] Cost Time = 4221203 us | Core [37] Cost Time = 5148525 us | Core [37] cost time = 25389347 us Core [38] Cost Time = 4221229 us | Core [38] Cost Time = 5186183 us | Core [38] cost time = 25389363 us Core [39] Cost Time = 4221253 us | Core [39] Cost Time = 4650058 us | Core [39] cost time = 25387948 us Core [40] Cost Time = 4221121 us | Core [40] Cost Time = 4682572 us | Core [40] cost time = 25387857 us Core [41] Cost Time = 4221238 us | Core [41] Cost Time = 4327049 us | Core [41] cost time = 25389261 us Core [42] Cost Time = 4221234 us | Core [42] Cost Time = 5141807 us | Core [42] cost time = 25389284 us Core [43] Cost Time = 4221218 us | Core [43] Cost Time = 3346939 us | Core [43] cost time = 25387967 us Core [44] Cost Time = 4221220 us | Core [44] Cost Time = 2768786 us | Core [44] cost time = 25387771 us Core [45] Cost Time = 4221221 us | Core [45] Cost Time = 3525078 us | Core [45] cost time = 25389044 us --------------------------------------------------------------------------------------------------------- Total Cost Time = 84424283 us | Total Cost Time = 86267593 us | Total cost time = 507769332 us --------------------------------------------------------------------------------------------------------- Summary: 1. In the lock contention scenario, MCS lock and ticket lock can grantee the fairness for each lock acquirers. MCS lock has better performance than ticket lock. 2. Spinlock is fast, however spinlock has the unfairness issue in the lock contention case. This will make some lock acquirers got starved. MCS lock is fast and fair comparing with spinlock. v2 1. Lowercase the algrithom author's name; (David Marchand) 2. Add the load test on master core to align with other locks test; (David Marchand) 3. Enlarge the test iterations from 10K to 1M; (Ananyev Konstantin) 4. Fixed potential deadlock issues. v1 Initial version. Phil Yang (3): eal/mcslock: add mcs queued lock implementation eal/mcslock: use generic msc queued lock on all arch test/mcslock: add mcs queued lock unit test MAINTAINERS | 5 + app/test/Makefile | 1 + app/test/autotest_data.py | 6 + app/test/autotest_test_funcs.py | 32 +++ app/test/meson.build | 2 + app/test/test_mcslock.c | 251 +++++++++++++++++++++ doc/api/doxy-api-index.md | 1 + doc/guides/rel_notes/release_19_08.rst | 6 + lib/librte_eal/common/Makefile | 2 +- .../common/include/arch/arm/rte_mcslock.h | 23 ++ .../common/include/arch/ppc_64/rte_mcslock.h | 19 ++ .../common/include/arch/x86/rte_mcslock.h | 19 ++ .../common/include/generic/rte_mcslock.h | 175 ++++++++++++++ lib/librte_eal/common/meson.build | 1 + 14 files changed, 542 insertions(+), 1 deletion(-) create mode 100644 app/test/test_mcslock.c create mode 100644 lib/librte_eal/common/include/arch/arm/rte_mcslock.h create mode 100644 lib/librte_eal/common/include/arch/ppc_64/rte_mcslock.h create mode 100644 lib/librte_eal/common/include/arch/x86/rte_mcslock.h create mode 100644 lib/librte_eal/common/include/generic/rte_mcslock.h -- 2.7.4