[PATCH-tip v5 19/21] perf bench: Extend mutex/rwlock futex suite to test TP futexes

[Waiman Long <longman@redhat.com>]

This patch extends the futex-mutex and futex-rwlock microbenchmarks to
test userspace mutexes and rwlocks built on top of the TP futexes. We
can then compare the relative performance of those userspace locks
based on different type of futexes.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 tools/perf/bench/futex-locks.c | 258 +++++++++++++++++++++++++++++++++++++++--
 tools/perf/bench/futex.h       |  43 +++++++
 tools/perf/check-headers.sh    |   4 +
 3 files changed, 298 insertions(+), 7 deletions(-)

diff --git a/tools/perf/bench/futex-locks.c b/tools/perf/bench/futex-locks.c
index 18dc71d..42be894 100644
--- a/tools/perf/bench/futex-locks.c
+++ b/tools/perf/bench/futex-locks.c
@@ -8,12 +8,14 @@
  * indication of actual throughput of the mutex code as it may not really
  * need to call into the kernel. Therefore, 3 sets of simple mutex lock and
  * unlock functions are written to implenment a mutex lock using the
- * wait-wake (2 versions) and PI futexes respectively. These functions serve
- * as the basis for measuring the locking throughput.
+ * wait-wake, PI and TP futexes respectively. These functions serve as the
+ * basis for measuring the locking throughput.
  *
- * Two sets of simple reader/writer lock and unlock functions are also
- * implemented using the wait-wake futexes as well as the Glibc rwlock
- * respectively for performance measurement purpose.
+ * Three sets of simple reader/writer lock and unlock functions are also
+ * implemented using the wait-wake and TP futexes as well as the Glibc
+ * rwlock respectively for performance measurement purpose. The TP futex
+ * writer lock/unlock functions are the same as that of the mutex functions.
+ * That is not the case for the wait-wake futexes.
  */
 
 #include <pthread.h>
@@ -57,6 +59,12 @@ enum {
 	STAT_SSLEEPS,	/* # of shared lock sleeps		*/
 	STAT_EAGAINS,	/* # of EAGAIN errors			*/
 	STAT_WAKEUPS,	/* # of wakeups (unlock return)		*/
+	STAT_HANDOFFS,	/* # of lock handoff (TP only)		*/
+	STAT_STEALS,	/* # of lock steals (TP only)		*/
+	STAT_SLRETRIES,	/* # of shared lock retries		*/
+	STAT_SURETRIES,	/* # of shared unlock retries		*/
+	STAT_SALONES,	/* # of shared locking alone ops	*/
+	STAT_SGROUPS,	/* # of shared locking group ops	*/
 	STAT_LOCKERRS,	/* # of exclusive lock errors		*/
 	STAT_UNLKERRS,	/* # of exclusive unlock errors		*/
 	STAT_SLOCKERRS,	/* # of shared lock errors		*/
@@ -192,7 +200,7 @@ static inline void stat_inc(int tid __maybe_unused, int item __maybe_unused)
  */
 static const struct option mutex_options[] = {
 	OPT_INTEGER ('d', "locklat",	&locklat,  "Specify inter-locking latency (default = 1)"),
-	OPT_STRING  ('f', "ftype",	&ftype,    "type", "Specify futex type: WW, PI, all (default)"),
+	OPT_STRING  ('f', "ftype",	&ftype,    "type", "Specify futex type: WW, PI, TP, all (default)"),
 	OPT_INTEGER ('L', "loadlat",	&loadlat,  "Specify load latency (default = 1)"),
 	OPT_UINTEGER('r', "runtime",	&nsecs,    "Specify runtime (in seconds, default = 10s)"),
 	OPT_BOOLEAN ('S', "shared",	&fshared,  "Use shared futexes instead of private ones"),
@@ -210,7 +218,7 @@ static inline void stat_inc(int tid __maybe_unused, int item __maybe_unused)
 
 static const struct option rwlock_options[] = {
 	OPT_INTEGER ('d', "locklat",	&locklat,  "Specify inter-locking latency (default = 1)"),
-	OPT_STRING  ('f', "ftype",	&ftype,    "type", "Specify futex type: WW, GC, all (default)"),
+	OPT_STRING  ('f', "ftype",	&ftype,    "type", "Specify futex type: WW, TP, GC, all (default)"),
 	OPT_INTEGER ('L', "loadlat",	&loadlat,  "Specify load latency (default = 1)"),
 	OPT_UINTEGER('R', "read-%",	&rpercent, "Specify reader percentage (default 50%)"),
 	OPT_UINTEGER('r', "runtime",	&nsecs,    "Specify runtime (in seconds, default = 10s)"),
@@ -504,6 +512,72 @@ static void pi_mutex_unlock(futex_t *futex, int tid)
 	stat_inc(tid, STAT_UNLOCKS);
 }
 
+/*
+ * TP futex lock/unlock functions
+ */
+static void tp_mutex_lock(futex_t *futex, int tid)
+{
+	struct timespec stime, etime;
+	futex_t val;
+	int ret;
+
+	val = futex_cmpxchg(futex, 0, thread_id);
+	if (val == 0)
+		return;
+
+	/*
+	 * Retry if an error happens
+	 */
+	for (;;) {
+		if (timestat) {
+			clock_gettime(CLOCK_REALTIME, &stime);
+			ret = futex_lock(futex, NULL, flags);
+			clock_gettime(CLOCK_REALTIME, &etime);
+			systime_add(tid, TIME_LOCK, &stime, &etime);
+		} else {
+			ret = futex_lock(futex, NULL, flags);
+		}
+		stat_inc(tid, STAT_LOCKS);
+		if (ret >= 0)
+			break;
+		stat_inc(tid, STAT_LOCKERRS);
+	}
+	/*
+	 * Get # of sleeps & locking method
+	 */
+	stat_add(tid, STAT_SLEEPS, ret >> 16);
+	ret &= 0xff;
+	if (!ret)
+		stat_inc(tid, STAT_STEALS);
+	else if (ret == 2)
+		stat_inc(tid, STAT_HANDOFFS);
+}
+
+static void tp_mutex_unlock(futex_t *futex, int tid)
+{
+	struct timespec stime, etime;
+	futex_t val;
+	int ret;
+
+	val = futex_cmpxchg(futex, thread_id, 0);
+	if (val == thread_id)
+		return;
+
+	if (timestat) {
+		clock_gettime(CLOCK_REALTIME, &stime);
+		ret = futex_unlock(futex, flags);
+		clock_gettime(CLOCK_REALTIME, &etime);
+		systime_add(tid, TIME_UNLK, &stime, &etime);
+	} else {
+		ret = futex_unlock(futex, flags);
+	}
+	stat_inc(tid, STAT_UNLOCKS);
+	if (ret < 0)
+		stat_inc(tid, STAT_UNLKERRS);
+	else
+		stat_add(tid, STAT_WAKEUPS, ret);
+}
+
 /**********************[ RWLOCK lock/unlock functions ]********************/
 
 /*
@@ -838,6 +912,138 @@ static void ww2_read_lock(futex_t *futex __maybe_unused, int tid)
 }
 
 /*
+ * TP futex reader/writer lock/unlock functions
+ */
+#define tp_write_lock		tp_mutex_lock
+#define tp_write_unlock		tp_mutex_unlock
+#define FUTEX_FLAGS_MASK	(3UL << 30)
+
+static void tp_read_lock(futex_t *futex, int tid)
+{
+	struct timespec stime, etime;
+	futex_t val;
+	int ret, retry = 0;
+
+	val = futex_cmpxchg(futex, 0, FUTEX_SHARED + 1);
+	if (!val)
+		return;
+
+	for (;;) {
+		futex_t old = val, new;
+
+		/*
+		 * Try to increment the reader count only if
+		 * 1) the FUTEX_SHARED bit is set; and
+		 * 2) none of the flags bits or FUTEX_SHARED_UNLOCK is set.
+		 */
+		if (!old)
+			new = FUTEX_SHARED + 1;
+		else if ((old & FUTEX_SHARED) &&
+			!(old & (FUTEX_FLAGS_MASK|FUTEX_SHARED_UNLOCK)))
+			new = old + 1;
+		else
+			break;
+		val = futex_cmpxchg(futex, old, new);
+		if (val == old)
+			goto out;
+		retry++;
+	}
+
+	for (;;) {
+		if (timestat) {
+			clock_gettime(CLOCK_REALTIME, &stime);
+			ret = futex_lock_shared(futex, NULL, flags);
+			clock_gettime(CLOCK_REALTIME, &etime);
+			systime_add(tid, TIME_SLOCK, &stime, &etime);
+		} else {
+			ret = futex_lock_shared(futex, NULL, flags);
+		}
+		stat_inc(tid, STAT_SLOCKS);
+		if (ret >= 0)
+			break;
+		stat_inc(tid, STAT_SLOCKERRS);
+	}
+	/*
+	 * Get # of sleeps & locking method
+	 */
+	stat_add(tid, STAT_SSLEEPS, ret >> 16);
+	if (ret & 0x100)
+		 stat_inc(tid, STAT_SALONES);	/* In alone mode */
+	if (ret & 0x200)
+		 stat_inc(tid, STAT_SGROUPS);	/* In group mode */
+
+	ret &= 0xff;
+	if (!ret)
+		stat_inc(tid, STAT_STEALS);
+	else if (ret == 2)
+		stat_inc(tid, STAT_HANDOFFS);
+out:
+	if (unlikely(retry))
+		stat_add(tid, STAT_SLRETRIES, retry);
+}
+
+static void tp_read_unlock(futex_t *futex, int tid)
+{
+	struct timespec stime, etime;
+	futex_t old, val;
+	int ret, retry = 0;
+
+	val = atomic_dec_return(futex);
+	if (!(val & FUTEX_SHARED)) {
+		fprintf(stderr,
+			"tp_read_unlock: Incorrect futex value = 0x%x\n", val);
+		exit(1);
+	}
+
+	for (;;) {
+		/*
+		 * Return if not the last reader, not in shared locking
+		 * mode or the unlock bit has been set.
+		 */
+		if ((val & (FUTEX_SCNT_MASK|FUTEX_SHARED_UNLOCK)) ||
+		   !(val & FUTEX_SHARED))
+			return;
+
+		if (val & ~FUTEX_SHARED_TID_MASK) {
+			/*
+			 * Only one task that can set the FUTEX_SHARED_UNLOCK
+			 * bit will do the unlock.
+			 */
+			old = futex_cmpxchg(futex, val,
+					    val|FUTEX_SHARED_UNLOCK);
+			if (old == val)
+				break;
+		} else {
+			/*
+			 * Try to clear the futex.
+			 */
+			old = futex_cmpxchg(futex, val, 0);
+			if (old == val)
+				goto out;
+		}
+		val = old;
+		retry++;
+	}
+
+	if (timestat) {
+		clock_gettime(CLOCK_REALTIME, &stime);
+		ret = futex_unlock_shared(futex, flags);
+		clock_gettime(CLOCK_REALTIME, &etime);
+		systime_add(tid, TIME_SUNLK, &stime, &etime);
+	} else {
+		ret = futex_unlock_shared(futex, flags);
+	}
+	stat_inc(tid, STAT_SUNLOCKS);
+	if (ret < 0)
+		stat_inc(tid, STAT_SUNLKERRS);
+	else
+		stat_add(tid, STAT_WAKEUPS, ret);
+out:
+	if (unlikely(retry))
+		stat_add(tid, STAT_SURETRIES, retry);
+}
+
+/*
  * Glibc read/write lock
  */
 static void gc_write_lock(futex_t *futex __maybe_unused,
@@ -1044,6 +1250,20 @@ static int futex_mutex_type(const char **ptype)
 		*ptype = "PI";
 		mutex_lock_fn = pi_mutex_lock;
 		mutex_unlock_fn = pi_mutex_unlock;
+	} else if (!strcasecmp(type, "TP")) {
+		*ptype = "TP";
+		mutex_lock_fn = tp_mutex_lock;
+		mutex_unlock_fn = tp_mutex_unlock;
+
+		/*
+		 * Check if TP futex is supported.
+		 */
+		futex_unlock(&global_futex, 0);
+		if (errno == ENOSYS) {
+			fprintf(stderr,
+			    "\nTP futexes are not supported by the kernel!\n");
+			return -1;
+		}
 	} else {
 		return -1;
 	}
@@ -1068,6 +1288,22 @@ static int futex_rwlock_type(const char **ptype)
 			write_lock_fn = ww_write_lock;
 			write_unlock_fn = ww_write_unlock;
 		}
+	} else if (!strcasecmp(type, "TP")) {
+		*ptype = "TP";
+		read_lock_fn = tp_read_lock;
+		read_unlock_fn = tp_read_unlock;
+		write_lock_fn = tp_write_lock;
+		write_unlock_fn = tp_write_unlock;
+
+		/*
+		 * Check if TP futex is supported.
+		 */
+		futex_unlock(&global_futex, 0);
+		if (errno == ENOSYS) {
+			fprintf(stderr,
+			    "\nTP futexes are not supported by the kernel!\n");
+			return -1;
+		}
 	} else if (!strcasecmp(type, "GC")) {
 		pthread_rwlockattr_t *attr = NULL;
 
@@ -1119,6 +1355,12 @@ static void futex_test_driver(const char *futex_type,
 		[STAT_SSLEEPS]	 = "Shared lock sleeps",
 		[STAT_WAKEUPS]	 = "Process wakeups",
 		[STAT_EAGAINS]	 = "EAGAIN lock errors",
+		[STAT_HANDOFFS]  = "Lock handoffs",
+		[STAT_STEALS]	 = "Lock stealings",
+		[STAT_SLRETRIES] = "Shared lock retries",
+		[STAT_SURETRIES] = "Shared unlock retries",
+		[STAT_SALONES]	 = "Shared lock ops (alone mode)",
+		[STAT_SGROUPS]	 = "Shared lock ops (group mode)",
 		[STAT_LOCKERRS]  = "\nExclusive lock errors",
 		[STAT_UNLKERRS]  = "\nExclusive unlock errors",
 		[STAT_SLOCKERRS] = "\nShared lock errors",
@@ -1372,6 +1614,7 @@ int bench_futex_mutex(int argc, const char **argv,
 	if (!ftype || !strcmp(ftype, "all")) {
 		futex_test_driver("WW", futex_mutex_type, mutex_workerfn);
 		futex_test_driver("PI", futex_mutex_type, mutex_workerfn);
+		futex_test_driver("TP", futex_mutex_type, mutex_workerfn);
 	} else {
 		futex_test_driver(ftype, futex_mutex_type, mutex_workerfn);
 	}
@@ -1398,6 +1641,7 @@ int bench_futex_rwlock(int argc, const char **argv,
 
 	if (!ftype || !strcmp(ftype, "all")) {
 		futex_test_driver("WW", futex_rwlock_type, rwlock_workerfn);
+		futex_test_driver("TP", futex_rwlock_type, rwlock_workerfn);
 		futex_test_driver("GC", futex_rwlock_type, rwlock_workerfn);
 	} else {
 		futex_test_driver(ftype, futex_rwlock_type, rwlock_workerfn);
diff --git a/tools/perf/bench/futex.h b/tools/perf/bench/futex.h
index ba7c735..199cc77 100644
--- a/tools/perf/bench/futex.h
+++ b/tools/perf/bench/futex.h
@@ -87,6 +87,49 @@
 		 val, opflags);
 }
 
+#ifndef FUTEX_LOCK
+#define FUTEX_LOCK		0xff	/* Disable the use of TP futexes */
+#define FUTEX_UNLOCK		0xff
+#define FUTEX_LOCK_SHARED	0xff
+#define FUTEX_UNLOCK_SHARED	0xff
+#endif /* FUTEX_LOCK */
+
+/**
+ * futex_lock() - lock the TP futex
+ */
+static inline int
+futex_lock(u_int32_t *uaddr, struct timespec *timeout, int opflags)
+{
+	return futex(uaddr, FUTEX_LOCK, 0, timeout, NULL, 0, opflags);
+}
+
+/**
+ * futex_unlock() - unlock the TP futex
+ */
+static inline int
+futex_unlock(u_int32_t *uaddr, int opflags)
+{
+	return futex(uaddr, FUTEX_UNLOCK, 0, NULL, NULL, 0, opflags);
+}
+
+/**
+ * futex_lock_shared() - shared locking of TP futex
+ */
+static inline int
+futex_lock_shared(u_int32_t *uaddr, struct timespec *timeout, int opflags)
+{
+	return futex(uaddr, FUTEX_LOCK_SHARED, 0, timeout, NULL, 0, opflags);
+}
+
+/**
+ * futex_unlock_shared() - shared unlocking of TP futex
+ */
+static inline int
+futex_unlock_shared(u_int32_t *uaddr, int opflags)
+{
+	return futex(uaddr, FUTEX_UNLOCK_SHARED, 0, NULL, NULL, 0, opflags);
+}
+
 #ifndef HAVE_PTHREAD_ATTR_SETAFFINITY_NP
 #include <pthread.h>
 static inline int pthread_attr_setaffinity_np(pthread_attr_t *attr,
diff --git a/tools/perf/check-headers.sh b/tools/perf/check-headers.sh
index c747bfd..6ec5f2d 100755
--- a/tools/perf/check-headers.sh
+++ b/tools/perf/check-headers.sh
@@ -57,3 +57,7 @@ check arch/x86/lib/memcpy_64.S        -B -I "^EXPORT_SYMBOL" -I "^#include <asm/
 check arch/x86/lib/memset_64.S        -B -I "^EXPORT_SYMBOL" -I "^#include <asm/export.h>"
 check include/uapi/asm-generic/mman.h -B -I "^#include <\(uapi/\)*asm-generic/mman-common.h>"
 check include/uapi/linux/mman.h       -B -I "^#include <\(uapi/\)*asm/mman.h>"
+
+# need to link to the latest futex.h header
+[[ -f ../../include/uapi/linux/futex.h ]] &&
+	ln -sf  ../../../../../include/uapi/linux/futex.h util/include/linux
-- 
1.8.3.1