From patchwork Mon Feb 22 17:10:45 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: William Tu X-Patchwork-Id: 586409 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from archives.nicira.com (archives.nicira.com [96.126.127.54]) by ozlabs.org (Postfix) with ESMTP id 75947140BEB for ; Tue, 23 Feb 2016 04:10:53 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b=a7YzRMK6; dkim-atps=neutral Received: from archives.nicira.com (localhost [127.0.0.1]) by archives.nicira.com (Postfix) with ESMTP id 3D4221061F; Mon, 22 Feb 2016 09:10:52 -0800 (PST) X-Original-To: dev@openvswitch.org Delivered-To: dev@openvswitch.org Received: from mx3v3.cudamail.com (mx3.cudamail.com [64.34.241.5]) by archives.nicira.com (Postfix) with ESMTPS id 6A97910325 for ; Mon, 22 Feb 2016 09:10:51 -0800 (PST) Received: from bar6.cudamail.com (localhost [127.0.0.1]) by mx3v3.cudamail.com (Postfix) with ESMTPS id 7AF0B162990 for ; Mon, 22 Feb 2016 10:10:50 -0700 (MST) X-ASG-Debug-ID: 1456161049-0b32373712008e0001-byXFYA Received: from mx1-pf2.cudamail.com ([192.168.24.2]) by bar6.cudamail.com with ESMTP id WDerBgST1plwR20c (version=TLSv1 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Mon, 22 Feb 2016 10:10:49 -0700 (MST) X-Barracuda-Envelope-From: u9012063@gmail.com X-Barracuda-RBL-Trusted-Forwarder: 192.168.24.2 Received: from unknown (HELO mail-pf0-f181.google.com) (209.85.192.181) by mx1-pf2.cudamail.com with ESMTPS (RC4-SHA encrypted); 22 Feb 2016 17:10:48 -0000 Received-SPF: pass (mx1-pf2.cudamail.com: SPF record at _netblocks.google.com designates 209.85.192.181 as permitted sender) X-Barracuda-RBL-Trusted-Forwarder: 209.85.192.181 Received: by mail-pf0-f181.google.com with SMTP id e127so95855215pfe.3 for ; Mon, 22 Feb 2016 09:10:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:subject:date:message-id:mime-version:content-type :content-transfer-encoding; bh=PvQ9xtuG2MJnnidbtOsz8QvtcTR5D+DWhEaycBY3caY=; b=a7YzRMK6DB0ERA3R8zTtqKdiZHv6YewTk2XWdGRrSkTFNIEWoRD/5HEpqueywqTMSP tD/liOQPVAv/PwUw4oNx4rJFoxKufIwXJrx4eCjpttn/hNVhXasYBJuu4NO2nDq8cTwt 5Tz8/kwXQ+mTs6wipZasdfhSuMKHOT7l4jYwqCOCYGqachdSxfHcqOYqkCg8y3vVR5L1 aplSDWsQMZCNP0C3Lmz8DQpaz2aLJnNA4HxPMwounU2xdkdz1Go6M1jODPB7a5CY8bAi hPP5GsP1SJTOnj05NoHRcHoBKwAgUsDKfWJrFDBG8wts2+kcN1iHDHo1cFvsBeD2XvD8 Rd8Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:subject:date:message-id:mime-version :content-type:content-transfer-encoding; bh=PvQ9xtuG2MJnnidbtOsz8QvtcTR5D+DWhEaycBY3caY=; b=TF3FvPli0i62h/ly9RP7GXMXpm+YYwuhfbsjRguQLbfRMFyWwVHyUAfhVGxjwpA6K+ eaZ7FfTfxdj1ru/f24z5cnfYe4M1j0vS5Q/81IZbqyefxjrporHENTuqR1xcsHYTuWkO VTveejJ31iQZfr6Db9lxHkUexhk2merkUgbeScZ1OGTsM8e3dTFt8mthAv3NjV8/9XSs IrMTViMyb2ssjvEJZwE5hZrgLXa1CMX7WGylFP/xZPmq0WmyhsZFg2I71kO5ds0aqL2o FE0ZtPQScNbAfE95t1AlCvQAxxLRJYGEXrU1kcrp7ddcQdXHmy50ckxAVRFzQFu8i6f5 ovBg== X-Gm-Message-State: AG10YOSigCVF2cc+rNTY1W6utWLdBY1A0Ziu5SYBnty2CGS07jvy5wWGicOXw3HlkPDaGA== X-Received: by 10.98.12.221 with SMTP id 90mr39518872pfm.95.1456161048123; Mon, 22 Feb 2016 09:10:48 -0800 (PST) Received: from vm-dev.localdomain ([208.91.1.34]) by smtp.gmail.com with ESMTPSA id wh9sm38445492pab.8.2016.02.22.09.10.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 22 Feb 2016 09:10:47 -0800 (PST) X-CudaMail-Envelope-Sender: u9012063@gmail.com X-Barracuda-Apparent-Source-IP: 208.91.1.34 From: William Tu To: u9012063@gmail.com, dev@openvswitch.org X-CudaMail-MID: CM-E2-221045786 X-CudaMail-DTE: 022216 X-CudaMail-Originating-IP: 209.85.192.181 Date: Mon, 22 Feb 2016 09:10:45 -0800 X-ASG-Orig-Subj: [##CM-E2-221045786##][PATCH v2] lib/ovs-thread: Add Transactional Memory (TM) support. Message-Id: <1456161045-69043-1-git-send-email-u9012063@gmail.com> X-Mailer: git-send-email 2.5.0 MIME-Version: 1.0 X-GBUdb-Analysis: 0, 209.85.192.181, Ugly c=0.444918 p=-0.253333 Source Normal X-MessageSniffer-Rules: 0-0-0-21716-c X-Barracuda-Connect: UNKNOWN[192.168.24.2] X-Barracuda-Start-Time: 1456161049 X-Barracuda-Encrypted: DHE-RSA-AES256-SHA X-Barracuda-URL: https://web.cudamail.com:443/cgi-mod/mark.cgi X-Virus-Scanned: by bsmtpd at cudamail.com X-Barracuda-BRTS-Status: 1 X-Barracuda-Spam-Score: 1.60 X-Barracuda-Spam-Status: No, SCORE=1.60 using per-user scores of TAG_LEVEL=3.5 QUARANTINE_LEVEL=1000.0 KILL_LEVEL=4.0 tests=BSF_RULE7568M, BSF_SC0_MISMATCH_TO, BSF_SC0_SA_TO_FROM_ADDR_MATCH, BSF_SC5_MJ1963, DKIM_SIGNED, MAILTO_TO_SPAM_ADDR, RDNS_NONE X-Barracuda-Spam-Report: Code version 3.2, rules version 3.2.3.27241 Rule breakdown below pts rule name description ---- ---------------------- -------------------------------------------------- 0.00 BSF_SC0_MISMATCH_TO Envelope rcpt doesn't match header 0.00 DKIM_SIGNED Domain Keys Identified Mail: message has a signature 0.00 MAILTO_TO_SPAM_ADDR URI: Includes a link to a likely spammer email 0.50 BSF_RULE7568M Custom Rule 7568M 0.10 RDNS_NONE Delivered to trusted network by a host with no rDNS 0.50 BSF_SC0_SA_TO_FROM_ADDR_MATCH Sender Address Matches Recipient Address 0.50 BSF_SC5_MJ1963 Custom Rule MJ1963 Subject: [ovs-dev] [PATCH v2] lib/ovs-thread: Add Transactional Memory (TM) support. X-BeenThere: dev@openvswitch.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@openvswitch.org Sender: "dev" v1->v2 - Fix a bug at UNLOCK_ELISION - Add checking if glibc version >= 2.21 (OVS_CHECK_GLIBC_TSX) - Add checking of whether cpu has TSX support (OVS_CHECK_RTM) - Enable LOCK_ELISION only when CPU has TSX and glibc doesn't (if glibc version >= 2.21, then using phtread_mutex has lock elision) - Add 20% mutation test-cmap testcase - List failed testcases below The patch (for references, not fully passed check yet) shows the preliminary results of enabling RTM (Restricted Transactional Memory). A successful transactional execution elides the lock, i.e., the lock is by-passed, and exposes concurrency. However, transactions might abort due to several reasons such as data conflicts, I/O operations, syscall, etc. When transaction aborts, it falls back to the original locking mechanisms. Thus, the performance improvement depends on the abort rate, and the overhead of speculative execution and rollback. The patch adds OVS_LOCK_ELISION, OVS_TRYLOCK_ELISION, and OVS_UNLOCK_ELISION. Experiments show that for cmap, the TM does not seem to have observable improvements at 2% mutations. For cmap search over 5% mutation, the cmap search time of TM shows better numbers. The most significant improvement is at hmap search, where with TM, there is around x2 or x3 speedup. Results are shown by using test-cmap benchmark. $ tests/ovstest test-cmap benchmark 20000000 4 2 1 Benchmarking with n=2000000, 4 threads, 2.00% mutations, batch size 1: < baseline > < TM > cmap insert     293 ms     293 ms cmap iterate 37 ms     37 ms batch search 197 ms    186 ms cmap destroy 177 ms    166 ms cmap insert     284 ms     283 ms cmap iterate    38 ms     38 ms cmap search     121 ms     120 ms * cmap destroy    168 ms   245 ms hmap insert     141 ms     164 ms hmap iterate    138 ms   134 ms hmap search     780 ms     414 ms * hmap destroy    126 ms   122 ms Benchmarking with n=2000000, 4 threads, 5.00% mutations, batch size 1: cmap insert     296 ms     298 ms cmap iterate 38 ms     38 ms batch search 239 ms    332 ms cmap destroy 162 ms    159 ms cmap insert     285 ms     284 ms cmap iterate 37 ms 37 ms cmap search     143 ms     126 ms * cmap destroy 163 ms   159 ms hmap insert     130 ms     128 ms hmap iterate 140 ms   134 ms hmap search    1577 ms    489 ms * hmap destroy 117 ms   108 ms Benchmarking with n=2000000, 4 threads, 10.00% mutations, batch size 1: cmap insert     301 ms     295 ms cmap iterate 37 ms     37 ms batch search 355 ms   380 ms cmap destroy 148 ms   145 ms cmap insert     286 ms     288 ms cmap iterate 37 ms     37 ms cmap search     240 ms     133 ms * cmap destroy 146 ms   148 ms hmap insert     133 ms     145 ms hmap iterate 139 ms   134 ms hmap search    2087 ms    575 ms * hmap destroy 94 ms     87 ms Benchmarking with n=2000000, 4 threads, 20.00% mutations, batch size 1: cmap insert 295 ms    297 ms cmap iterate 37 ms    38 ms batch search 834 ms   568 ms cmap destroy 126 ms   124 ms cmap insert 328 ms 283 ms cmap iterate    37 ms 37 ms cmap search     518 ms   164 ms * cmap destroy   146 ms   124 ms hmap insert     148 ms 128 ms hmap iterate   134 ms  135 ms hmap search   3034 ms    904 ms * hmap destroy   60 ms     58 ms === Analysis of Abort rate === Linux Perf shows PMU counters for transactional memory as below. $ perf record -e tx-start,tx-abort,tx-commit,tx-conflict The results from 'perf report' of the three TM experiments show: 2% 5% 10% tx-start 10K 14K 16K (count start transaction) tx-abort 7K 13K 14K (count all aborts) tx-commit 10K 14K 16K (count commit of transactions) tx-conflict 7K 13K 14K (count aborts due to conflict with other CPUs) Note: While test-cmap benchmark works fine, the patch fails a few cases when doing "make check". Failed cases: 717 ofproto - del group (OpenFlow 1.5), and the following 3 816 ofproto-dpif - active-backup bonding, and 817, 818 939 ofproto-dpif megaflow - normal, active-backup bonding, and 940, 955 Signed-off-by: William Tu --- configure.ac | 2 + lib/ovs-thread.c | 107 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ m4/openvswitch.m4 | 21 +++++++++++ 3 files changed, 130 insertions(+) diff --git a/configure.ac b/configure.ac index 49aa182..5c3bd15 100644 --- a/configure.ac +++ b/configure.ac @@ -113,6 +113,8 @@ OVS_CHECK_PKIDIR OVS_CHECK_RUNDIR OVS_CHECK_DBDIR OVS_CHECK_BACKTRACE +OVS_CHECK_RTM +OVS_CHECK_GLIBC_TSX OVS_CHECK_PERF_EVENT OVS_CHECK_VALGRIND OVS_CHECK_SOCKET_LIBS diff --git a/lib/ovs-thread.c b/lib/ovs-thread.c index b0e10ee..6fde904 100644 --- a/lib/ovs-thread.c +++ b/lib/ovs-thread.c @@ -52,6 +52,110 @@ static const char *must_not_fork; /* True if we created any threads beyond the main initial thread. */ static bool multithreaded; +#if defined(HAVE_RTM) && !defined(HAVE_GLIBC_TSX) +/* Intel Transactional Memory (TSX) support */ +#define _XBEGIN_STARTED (~0u) +#define _ABORT_EXPLICIT (1 << 0) +#define _ABORT_RETRY (1 << 1) +#define _ABORT_CONFLICT (1 << 2) +#define _ABORT_CAPACITY (1 << 3) +#define _ABORT_DEBUG (1 << 4) +#define _ABORT_NESTED (1 << 5) +#define _XABORT_CODE(x) (((x) >> 24) & 0xff) +#define _ABORT_LOCK_BUSY 0xff + +#define MAX_RETRY_XBEGIN 10 +#define MAX_ABORT_RETRY 5 + +#define __force_inline __attribute__((__always_inline__)) inline + +/* See: Intel 64 and IA-32 Architectures Software Developer's Manual + * Instruction Set Reference. */ + +static __force_inline int _xbegin(void) +{ + int ret = _XBEGIN_STARTED; + __asm__ volatile (".byte 0xc7,0xf8 ; .long 0" : "+a" (ret) :: "memory"); + return ret; +} + +static __force_inline void _xend(void) +{ + __asm__ volatile (".byte 0x0f,0x01,0xd5" ::: "memory"); +} + +static __force_inline void _xabort(const unsigned int status) +{ + __asm__ volatile (".byte 0xc6,0xf8,%P0" :: "i" (status) : "memory"); +} + +static __force_inline int _xtest(void) +{ + unsigned char out; + /* return 1 if RTM_ACTIVE = 1 */ + __asm__ volatile (".byte 0x0f,0x01,0xd6 ; setnz %0" : "=r" (out) :: "memory"); + return out; +} + +#define OVS_LOCK_ELISION(mutex) \ +{\ + unsigned status; \ + int i; \ + int abort_retry = 0; \ + for(i = 0; i < MAX_RETRY_XBEGIN; i++) { \ + if ((status = _xbegin()) == _XBEGIN_STARTED) { \ + if ((mutex)->__data.__lock == 0) {\ + return; \ + }\ + _xabort(_ABORT_LOCK_BUSY);\ + } \ + if (!(status & _ABORT_RETRY)) { \ + if (abort_retry >= MAX_ABORT_RETRY) {\ + break; \ + }\ + abort_retry++; \ + } \ + } \ +} + +/* Same as OVS_LOCK_ELISION, but has return value */ +#define OVS_TRYLOCK_ELISION(mutex) \ +{\ + unsigned status; \ + int i; \ + int abort_retry = 0; \ + for(i = 0; i < MAX_RETRY_XBEGIN; i++) { \ + if ((status = _xbegin()) == _XBEGIN_STARTED) { \ + if ((mutex)->__data.__lock == 0) {\ + return 0; \ + }\ + _xabort(_ABORT_LOCK_BUSY);\ + } \ + if (!(status & _ABORT_RETRY)) { \ + if (abort_retry >= MAX_ABORT_RETRY) {\ + break; \ + }\ + abort_retry++; \ + } \ + } \ +} + +#define OVS_UNLOCK_ELISION(mutex) \ +{\ + if (((mutex)->__data.__lock == 0)) { \ + if (_xtest() == 1) {\ + _xend();\ + }\ + return;\ + }\ +} + +#else /* HAVE_RTM disable below */ +#define OVS_LOCK_ELISION(mutex) +#define OVS_TRYLOCK_ELISION(mutex) +#define OVS_UNLOCK_ELISION(mutex) +#endif + #define LOCK_FUNCTION(TYPE, FUN) \ void \ ovs_##TYPE##_##FUN##_at(const struct ovs_##TYPE *l_, \ @@ -60,6 +164,7 @@ static bool multithreaded; { \ struct ovs_##TYPE *l = CONST_CAST(struct ovs_##TYPE *, l_); \ int error; \ + OVS_LOCK_ELISION(&l->lock); \ \ /* Verify that 'l' was initialized. */ \ if (OVS_UNLIKELY(!l->where)) { \ @@ -85,6 +190,7 @@ LOCK_FUNCTION(rwlock, wrlock); { \ struct ovs_##TYPE *l = CONST_CAST(struct ovs_##TYPE *, l_); \ int error; \ + OVS_TRYLOCK_ELISION(&l->lock); \ \ /* Verify that 'l' was initialized. */ \ if (OVS_UNLIKELY(!l->where)) { \ @@ -112,6 +218,7 @@ TRY_LOCK_FUNCTION(rwlock, trywrlock); { \ struct ovs_##TYPE *l = CONST_CAST(struct ovs_##TYPE *, l_); \ int error; \ + OVS_UNLOCK_ELISION(&l->lock); \ \ /* Verify that 'l' was initialized. */ \ ovs_assert(l->where); \ diff --git a/m4/openvswitch.m4 b/m4/openvswitch.m4 index 0149c30..8245da9 100644 --- a/m4/openvswitch.m4 +++ b/m4/openvswitch.m4 @@ -309,6 +309,27 @@ AC_DEFUN([OVS_CHECK_BACKTRACE], [AC_DEFINE([HAVE_BACKTRACE], [1], [Define to 1 if you have backtrace(3).])])]) +dnl Defines HAVE_RTM if CPU supports TSX +AC_DEFUN([OVS_CHECK_RTM], + [ if (test -e /proc/cpuinfo && cat /proc/cpuinfo | grep rtm > /dev/null); then + AC_DEFINE([HAVE_RTM], [1], [Define to 1 if CPU has Transactional Memory.]) + fi]) + +dnl Defines HAVE_GLIBC_TSX if glibc supports TSX +AC_DEFUN([OVS_CHECK_GLIBC_TSX], + [AC_RUN_IFELSE( + [AC_LANG_PROGRAM([], + [[ + #if __GLIBC__ >= 2 && __GLIBC_MINOR__ >= 21 + return 0; + #else + return 1; + #endif + ]])], + [AC_DEFINE([HAVE_GLIBC_TSX], [1], [Defines HAVE_GLIBC_TSX if glibc supports TSX])], + [], []) + ]) + dnl Defines HAVE_PERF_EVENT if linux/perf_event.h is found. AC_DEFUN([OVS_CHECK_PERF_EVENT], [AC_CHECK_HEADERS([linux/perf_event.h])])