[ovs-dev] [PATCH v2] lib/ovs-thread: Add Transactional Memory (TM) support.

William Tu u9012063 at gmail.com
Mon Feb 22 17:10:45 UTC 2016


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 <program>
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 <u9012063 at gmail.com>
---
 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])])
-- 
2.5.0




More information about the dev mailing list