Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1573329 > unrolled thread

[PATCH-tip v5 00/21] futex: Introducing throughput-optimized (TP) futexes

Back to article view | Back to linux.kernel

Contents

  [PATCH-tip v5 00/21] futex: Introducing throughput-optimized (TP) futexes Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100
    [PATCH-tip v5 20/21] sched, TP-futex: Make wake_up_q() return wakeup count Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100
    [PATCH-tip v5 21/21] futex: Dump internal futex state via debugfs Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100
    [PATCH-tip v5 17/21] TP-futex: Group readers together in wait queue Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100
      Re: [PATCH-tip v5 17/21] TP-futex: Group readers together in wait queue valdis.kletnieks@vt.edu - 2017-02-03 19:30 +0100
        Re: [PATCH-tip v5 17/21] TP-futex: Group readers together in wait  queue Waiman Long <longman@redhat.com> - 2017-02-03 19:50 +0100
          Re: [PATCH-tip v5 17/21] TP-futex: Group readers together in wait queue valdis.kletnieks@vt.edu - 2017-02-03 20:30 +0100
    [PATCH-tip v5 05/21] futex: Add helpers to get & cmpxchg futex value without lock Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100
    [PATCH-tip v5 04/21] futex: Rename futex_pi_state to futex_state Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100
    [PATCH-tip v5 10/21] TP-futex: Enable robust handling Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100
    [PATCH-tip v5 08/21] futex: Allow direct attachment of futex_state objects to hash bucket Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100
    [PATCH-tip v5 03/21] futex: Consolidate duplicated timer setup code Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100
    [PATCH-tip v5 19/21] perf bench: Extend mutex/rwlock futex suite to test TP futexes Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100
    [PATCH-tip v5 11/21] TP-futex: Implement lock handoff to prevent lock starvation Waiman Long <longman@redhat.com> - 2017-02-03 19:10 +0100

#1573329 — [PATCH-tip v5 00/21] futex: Introducing throughput-optimized (TP) futexes

 v4->v5:
  - Fix 0-day kernel build test compilation warnings.
  - Extract out non-TP futexes futex-mutex and futex-rwlock
    microbenchmarks as separate patches, as suggested by Arnaldo.
  - Rebased to the latest tip tree & use running_clock() instead
    of sched_clock().

 v3->v4:
  - Properly handle EFAULT error due to page fault.
  - Extend the use cases of TP futexes to userspace rwlock.
  - Change the lock handoff trigger from number of spinnings to
    elapsed time (5ms).
  - Various updates to the "perf bench futex mutex" microbenchmark.
  - Add a new "perf bench futex rwlock" microbenchmark for measuring
    rwlock performance.
  - Add mutex_owner to futex_state object to hold the serialization
    mutex owner.
  - Streamline a number of helper functions and other miscellenous
    coding improvements.
  - Rebase the patchset to the 4.10 kernel.

 v2->v3:
  - Use the abbreviation TP for the new futexes instead of TO.
  - Make a number of changes accordingly to review comments from
    ThomasG, PeterZ and MikeG.
  - Breaks the main futex patch into smaller pieces to make them easier
    to review.

 v1->v2:
  - Adds an explicit lock hand-off mechanism.
  - Adds timeout support.
  - Simplifies the required userspace code.
  - Fixes a number of problems in the v1 code.

This patchset introduces a new futex implementation called
throughput-optimized (TP) futexes. It is similar to PI futexes in its
calling convention, but provides better throughput than the wait-wake
(WW) futexes by encouraging lock stealing and optimistic spinning.

The new TP futexes can be used in implementing both userspace mutexes
and rwlocks. They provides better performance while simplifying the
userspace locking implementation at the same time. The WW futexes
are still needed to implement other synchronization primitives like
conditional variables and semaphores that cannot be handled by the
TP futexes.

Another advantage of TP futexes is that it has a built-in lock handoff
mechanism to prevent lock starvation from happenning as long as the
underlying kernel mutex doesn't have lock starvation problem.

Patches 1-2 implements userspace exclusive lock and read/write lock
benchmark in perf bench using futexes.

Patches 3-8 are preparatory patches that pave the way to implement
the TP futexes.

Patch 9 implements the basic TP futex that can support userspace
mutexes.

Patch 10 adds robust handling to TP futex to handle the death of TP
futex exclusive lock owners.

Patch 11 adds a lock hand-off mechanism that can prevent lock starvation
to happen while introducing minimal runtime overhead.

Patch 12 enables the FUTEX_LOCK futex(2) syscall to return status
information, such as how the lock is acquired and how many time
the task needs to sleep in the spinning loop, that can be used by
userspace utilities to monitor how the TP futexes are performing.

Patch 13 enables userspace applications to supply a timeout value to
abort the lock acquisition attempt after the specified time period
has passed.

Patch 14 adds a new document tp-futex.txt in the Documentation
directory to describe the new TP futexes.

Patch 15 extends the TP futexes to support userspace rwlocks.

Patch 16 enables more reader lock stealing of TP futexes in the kernel.

Patch 17 groups readers together as a spin group to enhance reader
throughput.

Patch 18 updates the tp-futex.txt file to add information about
rwlock support.

Patch 19 extends the perf bench futex locking benchmark to include
variants using the new TP futexes.

Patch 20 updates the wake_up_q() function to returns the number
woken tasks.

Patch 21 enables the dumping of internal futex state information
via debugfs.

All the benchmark results shown in the change logs were produced by
the microbenchmarks included in this patchset. So everyone can run
the microbenchmark to see how the TP futexes perform and behave in
their own test systems.

Once this patchset is finalized, an updated manpage patch to document
the new TP futexes will be sent out. The next step will then be to
make Glibc NTPL use the new TP futexes.

Performance highlight in term of average locking rates (ops/sec)
on a 2-socket system are as follows:

                WW futex       TP futex      Glibc
                --------       --------      -----
  mutex         121,129        152,242         -
  rwlock         99,149        162,887       30,362

Patches 9 and 17 contain more detailed information about the
performance characteristics of the TP futexes when implementing
userspace mutex and rwlock respectively when compared with other
possible way of doing so via the wait-wake futexes.

Waiman Long (21):
  perf bench: New microbenchmark for userspace mutex performance
  perf bench: New microbenchmark for userspace rwlock performance
  futex: Consolidate duplicated timer setup code
  futex: Rename futex_pi_state to futex_state
  futex: Add helpers to get & cmpxchg futex value without lock
  futex: Consolidate pure pi_state_list add & delete codes to helpers
  futex: Add a new futex type field into futex_state
  futex: Allow direct attachment of futex_state objects to hash bucket
  futex: Introduce throughput-optimized (TP) futexes
  TP-futex: Enable robust handling
  TP-futex: Implement lock handoff to prevent lock starvation
  TP-futex: Return status code on FUTEX_LOCK calls
  TP-futex: Add timeout support
  TP-futex, doc: Add TP futexes documentation
  TP-futex: Support userspace reader/writer locks
  TP-futex: Enable kernel reader lock stealing
  TP-futex: Group readers together in wait queue
  TP-futex, doc: Update TP futexes document on shared locking
  perf bench: Extend mutex/rwlock futex suite to test TP futexes
  sched, TP-futex: Make wake_up_q() return wakeup count
  futex: Dump internal futex state via debugfs

 Documentation/00-INDEX                  |    2 +
 Documentation/tp-futex.txt              |  284 ++++++
 include/linux/sched.h                   |    4 +-
 include/linux/sched/wake_q.h            |    2 +-
 include/uapi/linux/futex.h              |   32 +-
 kernel/futex.c                          | 1412 +++++++++++++++++++++++---
 kernel/sched/core.c                     |    6 +-
 tools/perf/Documentation/perf-bench.txt |    5 +
 tools/perf/bench/Build                  |    1 +
 tools/perf/bench/bench.h                |    2 +
 tools/perf/bench/futex-locks.c          | 1654 +++++++++++++++++++++++++++++++
 tools/perf/bench/futex.h                |   43 +
 tools/perf/builtin-bench.c              |   11 +
 tools/perf/check-headers.sh             |    4 +
 14 files changed, 3341 insertions(+), 121 deletions(-)
 create mode 100644 Documentation/tp-futex.txt
 create mode 100644 tools/perf/bench/futex-locks.c

-- 
1.8.3.1

[toc] | [next] | [standalone]

#1573330 — [PATCH-tip v5 20/21] sched, TP-futex: Make wake_up_q() return wakeup count

Unlike wake_up_process(), wake_up_q() doesn't tell us how many
tasks have been woken up. This information can sometimes be useful
for tracking purpose. So wake_up_q() is now modified to return that
information.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 include/linux/sched/wake_q.h | 2 +-
 kernel/futex.c               | 8 +++-----
 kernel/sched/core.c          | 6 ++++--
 3 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/include/linux/sched/wake_q.h b/include/linux/sched/wake_q.h
index 9a32f17..2b2bc9d 100644
--- a/include/linux/sched/wake_q.h
+++ b/include/linux/sched/wake_q.h
@@ -49,6 +49,6 @@ static inline void wake_q_init(struct wake_q_head *head)
 
 extern void wake_q_add(struct wake_q_head *head,
 		       struct task_struct *task);
-extern void wake_up_q(struct wake_q_head *head);
+extern int wake_up_q(struct wake_q_head *head);
 
 #endif /* _LINUX_SCHED_WAKE_Q_H */
diff --git a/kernel/futex.c b/kernel/futex.c
index 16c63b8..6bf5304 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -4257,11 +4257,9 @@ static int futex_unlock(u32 __user *uaddr, unsigned int flags,
 out_put_key:
 	put_futex_key(&key);
 	if (owner) {
-		/*
-		 * No error would have happened if owner defined.
-		 */
-		wake_up_q(&wake_q);
-		return ret ? ret : 1;
+		int cnt = wake_up_q(&wake_q);
+
+		return ret ? ret : cnt;
 	}
 
 	return ret;
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 679093d..668a094 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -452,9 +452,10 @@ void wake_q_add(struct wake_q_head *head, struct task_struct *task)
 	head->lastp = &node->next;
 }
 
-void wake_up_q(struct wake_q_head *head)
+int wake_up_q(struct wake_q_head *head)
 {
 	struct wake_q_node *node = head->first;
+	int wakecnt = 0;
 
 	while (node != WAKE_Q_TAIL) {
 		struct task_struct *task;
@@ -469,9 +470,10 @@ void wake_up_q(struct wake_q_head *head)
 		 * wake_up_process() implies a wmb() to pair with the queueing
 		 * in wake_q_add() so as not to miss wakeups.
 		 */
-		wake_up_process(task);
+		wakecnt += wake_up_process(task);
 		put_task_struct(task);
 	}
+	return wakecnt;
 }
 
 /*
-- 
1.8.3.1

[toc] | [prev] | [next] | [standalone]

#1573331 — [PATCH-tip v5 21/21] futex: Dump internal futex state via debugfs

For debugging purpose, it is sometimes useful to dump the internal
states in the futex hash bucket table. This patch adds a file
"futex_hash_table" in debugfs root filesystem to dump the internal
futex states.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/futex.c | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 82 insertions(+)

diff --git a/kernel/futex.c b/kernel/futex.c
index 6bf5304..8b7a591 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -4428,3 +4428,85 @@ static int __init futex_init(void)
 	return 0;
 }
 __initcall(futex_init);
+
+#if defined(CONFIG_DEBUG_FS) && defined(CONFIG_SMP)
+/*
+ * Debug code to dump selected content of in-kernel futex hash bucket table.
+ */
+#include <linux/debugfs.h>
+
+static int futex_dump_show(struct seq_file *m, void *arg)
+{
+	struct futex_hash_bucket *hb = arg;
+	struct futex_state *state;
+	int i;
+
+	if (list_empty(&hb->fs_head))
+		return 0;
+
+	seq_printf(m, "\nHash bucket %d:\n", (int)(hb - futex_queues));
+	spin_lock(&hb->fs_lock);
+	i = 0;
+	list_for_each_entry(state, &hb->fs_head, fs_list) {
+		seq_printf(m, "  Futex state %d\n", i++);
+		if (state->owner)
+			seq_printf(m, "    owner PID = %d\n",
+				   task_pid_vnr(state->owner));
+		if (state->mutex_owner)
+			seq_printf(m, "    mutex owner PID = %d\n",
+				   task_pid_vnr(state->mutex_owner));
+		seq_printf(m, "    reference count = %d\n",
+			   atomic_read(&state->refcount));
+		seq_printf(m, "    handoff PID = %d\n", state->handoff_pid);
+	}
+	spin_unlock(&hb->fs_lock);
+	return 0;
+}
+
+static void *futex_dump_start(struct seq_file *m, loff_t *pos)
+{
+	return (*pos < futex_hashsize) ? &futex_queues[*pos] : NULL;
+}
+
+static void *futex_dump_next(struct seq_file *m, void *arg, loff_t *pos)
+{
+	(*pos)++;
+	return (*pos < futex_hashsize) ? &futex_queues[*pos] : NULL;
+}
+
+static void futex_dump_stop(struct seq_file *m, void *arg)
+{
+}
+
+static const struct seq_operations futex_dump_op = {
+	.start = futex_dump_start,
+	.next  = futex_dump_next,
+	.stop  = futex_dump_stop,
+	.show  = futex_dump_show,
+};
+
+static int futex_dump_open(struct inode *inode, struct file *file)
+{
+	return seq_open(file, &futex_dump_op);
+}
+
+static const struct file_operations fops_futex_dump = {
+	.open	 = futex_dump_open,
+	.read	 = seq_read,
+	.llseek	 = seq_lseek,
+	.release = seq_release,
+};
+
+/*
+ * Initialize debugfs for the futex hash bucket table dump.
+ */
+static int __init init_futex_dump(void)
+{
+	if (!debugfs_create_file("futex_hash_table", 0400, NULL, NULL,
+				 &fops_futex_dump))
+		return -ENOMEM;
+	return 0;
+}
+fs_initcall(init_futex_dump);
+
+#endif /* CONFIG_DEBUG_FS && CONFIG_SMP */
-- 
1.8.3.1

[toc] | [prev] | [next] | [standalone]

#1573332 — [PATCH-tip v5 17/21] TP-futex: Group readers together in wait queue

All the TP futex lock waiters are serialized in the kernel using a
kernel mutex which acts like a wait queue. The order at which the
waiters popped out from the wait queue will affect performance when
exclusive (writer) and shared (reader) lock waiters are mixed in the
queue. The worst case scenarios will be something like RWRWRW... in
term of ordering where no parallelism in term of lock ownership
can happen.

To improve throughput, the readers are now grouped together as a single
entity in the wait queue. The first reader that enters the mutex wait
queue will become the leader of the group. The other readers will
spin on the group leader via an OSQ lock. When the futex is put in
the shared mode, either by the group leader or by an external reader
the spinning readers in the reader group will then acquire the read
lock successively.

The spinning readers in the group will get disbanded when the group
leader goes to sleep. In this case, all those readers will go into the
mutex wait queue alone and wait for their turn to acquire the TP futex.

On a 2-socket 36-core E5-2699 v3 system (HT off) running on a 4.10
based kernel, the performance of TP rwlock with 1:1 reader/writer
ratio versus one based on the wait-wake futexes as well as the Glibc
rwlock with a microbenchmark (1 worker thread per cpu core) running
for 10s were as follows:

                          WW futex       TP futex         Glibc
                          --------       --------         -----
Total locking ops        35,707,234     58,645,434     10,930,422
Per-thread avg/sec           99,149        162,887         30,362
Per-thread min/sec           93,190         38,641         29,872
Per-thread max/sec          104,213        225,983         30,708
Write lock futex calls   11,161,534         14,094          -
Write unlock futex calls  8,696,121            167          -
Read lock futex calls     1,717,863          6,659          -
Read unlock futex calls   4,316,418            323          -

It can be seen that the throughput of the TP futex is close to 2X
the WW futex and almost 6X the Glibc version in this particular case.

The following table shows the CPU cores scaling for the average
per-thread locking rates (ops/sec):

                          WW futex       TP futex       Glibc
                          --------       --------       -----
  9 threads (1 socket)    422,014        647,006       190,236
 18 threads (2 sockets)   197,145        330,353        66,934
 27 threads (2 sockets)   127,947        213,417        43,641
 36 threads (2 sockets)    99,149        162,887        30,362

The following tables shows the average per-thread locking rates
(36 threads) with different reader percentages:

                          WW futex       TP futex       Glibc
                          --------       --------       -----
   90% readers            124,426        159,657        60,208
   95% readers            148,905        152,315        68,666
  100% reader             210,029        191,759        84,316

The rwlocks based on the WW futexes and Glibc prefer readers by
default. So it can be seen that the performance of the WW futex and
Glibc rwlocks increased with higher reader percentages. The TP futex
rwlock, however, prefers writers a bit more than readers. So the
performance didn't increase as the reader percentage rises.

The WW futexes and Glibc rwlocks also have a writer-preferring version.
Their performance with the same tests are as follows:

                          WW futex       TP futex       Glibc
                          --------       --------       -----
   90% readers             87,866        159,657        26,057
   95% readers             93,193        152,315        32,611
  100% reader             193,267        191,759        88,440

With separate 18 reader and 18 writer threads, the the average
per-thread reader and writer locking rates with different load
latencies (L, default = 1) and reader-preferring rwlocks are:

                          WW futex       TP futex       Glibc
                          --------       --------       -----
 Reader rate, L=1         381,411         74,059       164,184
 Writer rate, L=1               0        240,841             0

 Reader rate, L=5         330,732         57,361       150,691
 Writer rate, L=5               0        175,400             0

 Reader rate, L=50        304,505         17,355        97,066
 Writer rate, L=50              0        114,504             0

The corresponding locking rates with writer-preferring rwlocks are:

                          WW futex       TP futex       Glibc
                          --------       --------       -----
 Reader rate, L=1         138,805         74,059            54
 Writer rate, L=1          31,113        240,841        56,424

 Reader rate, L=5         114,414         57,361            24
 Writer rate, L=5          28,062        175,400        52,039

 Reader rate, L=50         88,619         51,483             5
 Writer rate, L=50         21,005         98,005        49,885

With both the WW futex and Glibc rwlocks, lock starvation happened
for the writers with reader-preferring rwlocks. For writer preferring
rwlocks, the WW futex one fared better. The Glibc one, however,
was close to starving the readers.

The TP futex prefers writer in general, but the actual preference
depends on the timing. Lock starvation should not happen on the TP
futexes as long as the underlying kernel mutex is lock starvation
free which is the case for 4.10 and later kernel.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/futex.c | 136 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 133 insertions(+), 3 deletions(-)

diff --git a/kernel/futex.c b/kernel/futex.c
index 90c8c80..16c63b8 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -71,6 +71,7 @@
 #include <linux/freezer.h>
 #include <linux/bootmem.h>
 #include <linux/fault-inject.h>
+#include <linux/osq_lock.h>
 
 #include <asm/futex.h>
 
@@ -241,6 +242,16 @@ struct futex_state {
 	u32 handoff_pid;			/* For TP futexes only */
 	int locksteal_disabled;			/* For TP futexes only */
 
+	/*
+	 * To improve reader throughput in TP futexes, all the readers
+	 * in the mutex queue are grouped together. The first reader in the
+	 * queue will set first_reader, then the rest of the readers will
+	 * spin on the first reader via the OSQ without actually entering
+	 * the mutex queue.
+	 */
+	struct optimistic_spin_queue reader_osq;
+	struct task_struct *first_reader;
+
 	enum futex_type type;
 	union futex_key key;
 };
@@ -3390,14 +3401,21 @@ void exit_robust_list(struct task_struct *curr)
  *		   0 - steals the lock
  *		   1 - top waiter (mutex owner) acquires the lock
  *		   2 - handed off the lock
- * 2) bits 08-15: reserved
- * 3) bits 15-30: how many times the task has slept or yield to scheduler
+ * 2) bit  08:	  1 if reader spins alone		(shared lock only)
+ *    bit  09:	  1 if reader is a spin group leader	(shared lock only)
+ *    bits 10-16: reserved
+ * 3) bits 16-30: how many times the task has slept or yield to scheduler
  *		  in futex_spin_on_owner().
  */
 #define TP_LOCK_STOLEN		0
 #define TP_LOCK_ACQUIRED	1
 #define TP_LOCK_HANDOFF		2
+
+#define TP_READER_ALONE		1
+#define TP_READER_GROUP		2
+
 #define TP_STATUS_SLEEP(val, sleep)	((val)|((sleep) << 16))
+#define TP_STATUS_ALONE(val, alone)	((val)|((alone) << 8))
 
 /**
  * lookup_futex_state - Looking up the futex state structure.
@@ -3440,6 +3458,7 @@ void exit_robust_list(struct task_struct *curr)
 	state->type = TYPE_TP;
 	state->key = *key;
 	state->locksteal_disabled = false;
+	osq_lock_init(&state->reader_osq);
 	list_add(&state->fs_list, &hb->fs_head);
 	WARN_ON(atomic_read(&state->refcount) != 1);
 
@@ -3897,6 +3916,98 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 	return (ret < 0) ? ret : TP_STATUS_SLEEP(ret, nsleep);
 }
 
+/**
+ * futex_spin_on_reader - Optimistically spin on first reader
+ * @uaddr:   futex address
+ * @pfirst:  pointer to first reader
+ * @state:   futex state object
+ * @timeout: hrtimer_sleeper structure
+ *
+ * Reader performance will depend on the placement of readers within the
+ * mutex queue. For a queue of 4 readers and 4 writers, for example, the
+ * optimal placement will be either RRRRWWWW or WWWWRRRR. A worse case will
+ * be RWRWRWRW.
+ *
+ * One way to avoid the worst case scenario is to gather all the readers
+ * together as a single unit and place it into the mutex queue. This is done
+ * by having the first reader puts its task structure into state->first_reader
+ * and the rest of the readers optimistically spin on it instead of entering
+ * the mutex queue.
+ *
+ * On exit from this function, the reader would have
+ *  1) acquired a read lock on the futex;
+ *  2) become the first reader and goes into the mutex queue; or
+ *  3) seen the first reader slept and needs to go into the mutex queue alone.
+ *
+ * Any fault on accessing the futex will cause it to return 0 and goes into
+ * the mutex queue.
+ *
+ * Return:  > 0 - acquired the read lock
+ *	   <= 0 - need to goes into the mutex queue
+ */
+static int futex_spin_on_reader(u32 __user *uaddr, struct task_struct **pfirst,
+				struct futex_state *state,
+				struct hrtimer_sleeper *timeout)
+{
+	struct task_struct *first_reader;
+	int ret = 0;
+
+	preempt_disable();
+
+retry:
+	first_reader = READ_ONCE(state->first_reader);
+	if (!first_reader)
+		first_reader = cmpxchg(&state->first_reader, NULL, current);
+	if (!first_reader)
+		goto out;	/* Became the first reader */
+
+	if (!osq_lock(&state->reader_osq))
+		goto reschedule;
+
+	for (;;) {
+		u32 uval;
+
+		if (!state->locksteal_disabled) {
+			ret = futex_trylock_preempt_disabled(uaddr,
+						FUTEX_SHARED, &uval);
+			/*
+			 * Return if lock acquired or an error happened
+			 */
+			if (ret)
+				break;
+		}
+
+		/*
+		 * Reread the first reader value again.
+		 */
+		first_reader = READ_ONCE(state->first_reader);
+		if (!first_reader)
+			first_reader = cmpxchg(&state->first_reader, NULL,
+						current);
+		if (!first_reader || !first_reader->on_cpu)
+			break;
+
+		if (need_resched()) {
+			osq_unlock(&state->reader_osq);
+			goto reschedule;
+		}
+
+		cpu_relax();
+	}
+	osq_unlock(&state->reader_osq);
+out:
+	*pfirst = first_reader;
+	preempt_enable();
+	return ret;
+
+reschedule:
+	/*
+	 * Yield the CPU and retry later.
+	 */
+	schedule_preempt_disabled();
+	goto retry;
+}
+
 /*
  * Userspace tried a 0 -> TID atomic transition of the futex value
  * and failed. The kernel side here does the whole locking operation.
@@ -3923,9 +4034,11 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags,
 {
 	struct hrtimer_sleeper timeout, *to;
 	struct futex_hash_bucket *hb;
+	struct task_struct *first_reader = NULL;
 	union futex_key key = FUTEX_KEY_INIT;
 	struct futex_state *state;
 	u32 uval, vpid = shared ? FUTEX_SHARED : task_pid_vnr(current);
+	int alone = 0;
 	int ret;
 
 	/*
@@ -3991,6 +4104,17 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags,
 		hrtimer_start_expires(&to->timer, HRTIMER_MODE_ABS);
 
 	/*
+	 * Spin on the first reader and return if we acquired the read lock.
+	 */
+	if (shared) {
+		int rspin_ret = futex_spin_on_reader(uaddr, &first_reader,
+						     state, to);
+		if (rspin_ret > 0)
+			goto out_put_state_key;
+		alone = first_reader ? TP_READER_ALONE : TP_READER_GROUP;
+	}
+
+	/*
 	 * Acquiring the serialization mutex.
 	 *
 	 * If we got a signal or has some other error, we need to abort
@@ -4018,6 +4142,12 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags,
 	mutex_unlock(&state->mutex);
 
 out_put_state_key:
+	/*
+	 * We will be the first reader if (first_reader == NULL).
+	 */
+	if (shared && !first_reader)
+		WRITE_ONCE(state->first_reader, NULL);
+
 	if (!put_futex_state_unlocked(state)) {
 		/*
 		 * May need to free the futex state object and so must be
@@ -4034,7 +4164,7 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags,
 		hrtimer_cancel(&to->timer);
 		destroy_hrtimer_on_stack(&to->timer);
 	}
-	return ret;
+	return (ret < 0) ? ret : TP_STATUS_ALONE(ret, alone);
 }
 
 /*
-- 
1.8.3.1

[toc] | [prev] | [next] | [standalone]

#1573349 — Re: [PATCH-tip v5 17/21] TP-futex: Group readers together in wait queue

[Multipart message — attachments visible in raw view] — view raw

On Fri, 03 Feb 2017 13:03:50 -0500, Waiman Long said:

> On a 2-socket 36-core E5-2699 v3 system (HT off) running on a 4.10

>                           WW futex       TP futex         Glibc
>                           --------       --------         -----
> Total locking ops        35,707,234     58,645,434     10,930,422
> Per-thread avg/sec           99,149        162,887         30,362
> Per-thread min/sec           93,190         38,641         29,872
> Per-thread max/sec          104,213        225,983         30,708

Do we understand where the 38K number came from?  I'm a bit concerned that the
min-to-max has such a large dispersion compared to all the other numbers.  Was
that a worst-case issue, and is the worst-case something likely to happen in
production, or requires special effort to trigger?

[toc] | [prev] | [next] | [standalone]

#1573371 — Re: [PATCH-tip v5 17/21] TP-futex: Group readers together in wait queue

On 02/03/2017 01:23 PM, valdis.kletnieks@vt.edu wrote:
> On Fri, 03 Feb 2017 13:03:50 -0500, Waiman Long said:
>
>> On a 2-socket 36-core E5-2699 v3 system (HT off) running on a 4.10
>>                           WW futex       TP futex         Glibc
>>                           --------       --------         -----
>> Total locking ops        35,707,234     58,645,434     10,930,422
>> Per-thread avg/sec           99,149        162,887         30,362
>> Per-thread min/sec           93,190         38,641         29,872
>> Per-thread max/sec          104,213        225,983         30,708
> Do we understand where the 38K number came from?  I'm a bit concerned that the
> min-to-max has such a large dispersion compared to all the other numbers.  Was
> that a worst-case issue, and is the worst-case something likely to happen in
> production, or requires special effort to trigger?
>
Because the lock isn't fair and depending on the placement of the lock,
you will see some CPUs have higher likelihood of getting the lock than
the others. This is reflected in the different locking rates as reported
by the micro-benchmark.  As the microbenchmark is included in this patch
set, you can play around with it if you want.

This patch set does guarantee some minimum performance level, but it
can't guarantee fairness for all the lock waiters.

Regards,
Longman

[toc] | [prev] | [next] | [standalone]

#1573388 — Re: [PATCH-tip v5 17/21] TP-futex: Group readers together in wait queue

[Multipart message — attachments visible in raw view] — view raw

On Fri, 03 Feb 2017 13:42:46 -0500, Waiman Long said:

> This patch set does guarantee some minimum performance level, but it
> can't guarantee fairness for all the lock waiters.

OK, sounds like it's a situation that's statistically unlikely, but it has
protections against starvation so the system will eventually dig itself out of
the hole, and the scenario is at least known and understood.  The improved
numbers for average-case probably outweigh the worst-case then...

[toc] | [prev] | [next] | [standalone]

#1573334 — [PATCH-tip v5 05/21] futex: Add helpers to get & cmpxchg futex value without lock

Two new helper functions cmpxchg_futex_value() and get_futex_value()
are added to access and change the futex value without the hash
bucket lock.  As a result, page fault is enabled and the page will
be faulted in if not present yet.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/futex.c | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/kernel/futex.c b/kernel/futex.c
index b21c6a0..203a388 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -805,6 +805,21 @@ static int get_futex_value_locked(u32 *dest, u32 __user *from)
 	return ret ? -EFAULT : 0;
 }
 
+/*
+ * The equivalents of the above cmpxchg_futex_value_locked() and
+ * get_futex_value_locked which are called without the hash bucket lock
+ * and so can have page fault enabled.
+ */
+static inline int cmpxchg_futex_value(u32 *curval, u32 __user *uaddr,
+				      u32 uval, u32 newval)
+{
+	return futex_atomic_cmpxchg_inatomic(curval, uaddr, uval, newval);
+}
+
+static inline int get_futex_value(u32 *dest, u32 __user *from)
+{
+	return __get_user(*dest, from);
+}
 
 /*
  * PI code:
-- 
1.8.3.1

[toc] | [prev] | [next] | [standalone]

#1573335 — [PATCH-tip v5 04/21] futex: Rename futex_pi_state to futex_state

The futex_pi_state structure will be overloaded in later patches to
store state information about non-PI futexes. So the structure name
itself is no longer a good description of its purpose. So its name
is changed to futex_state, a more generic name.

Some of the functions that process the futex states are also renamed.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 include/linux/sched.h |   4 +-
 kernel/futex.c        | 107 +++++++++++++++++++++++++-------------------------
 2 files changed, 56 insertions(+), 55 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index e9d5503..27a0b77 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -59,7 +59,7 @@
 struct sched_attr;
 struct sched_param;
 
-struct futex_pi_state;
+struct futex_state;
 struct robust_list_head;
 struct bio_list;
 struct fs_struct;
@@ -1354,7 +1354,7 @@ struct task_struct {
 	struct compat_robust_list_head __user *compat_robust_list;
 #endif
 	struct list_head pi_state_list;
-	struct futex_pi_state *pi_state_cache;
+	struct futex_state *pi_state_cache;
 #endif
 #ifdef CONFIG_PERF_EVENTS
 	struct perf_event_context *perf_event_ctxp[perf_nr_task_contexts];
diff --git a/kernel/futex.c b/kernel/futex.c
index 07886ba..b21c6a0 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -194,11 +194,12 @@
 #define FLAGS_HAS_TIMEOUT	0x04
 
 /*
- * Priority Inheritance state:
+ * Futex state object:
+ *  - Priority Inheritance state
  */
-struct futex_pi_state {
+struct futex_state {
 	/*
-	 * list of 'owned' pi_state instances - these have to be
+	 * list of 'owned' state instances - these have to be
 	 * cleaned up in do_exit() if the task exits prematurely:
 	 */
 	struct list_head list;
@@ -242,7 +243,7 @@ struct futex_q {
 	struct task_struct *task;
 	spinlock_t *lock_ptr;
 	union futex_key key;
-	struct futex_pi_state *pi_state;
+	struct futex_state *pi_state;
 	struct rt_mutex_waiter *rt_waiter;
 	union futex_key *requeue_pi_key;
 	u32 bitset;
@@ -808,76 +809,76 @@ static int get_futex_value_locked(u32 *dest, u32 __user *from)
 /*
  * PI code:
  */
-static int refill_pi_state_cache(void)
+static int refill_futex_state_cache(void)
 {
-	struct futex_pi_state *pi_state;
+	struct futex_state *state;
 
 	if (likely(current->pi_state_cache))
 		return 0;
 
-	pi_state = kzalloc(sizeof(*pi_state), GFP_KERNEL);
+	state = kzalloc(sizeof(*state), GFP_KERNEL);
 
-	if (!pi_state)
+	if (!state)
 		return -ENOMEM;
 
-	INIT_LIST_HEAD(&pi_state->list);
+	INIT_LIST_HEAD(&state->list);
 	/* pi_mutex gets initialized later */
-	pi_state->owner = NULL;
-	atomic_set(&pi_state->refcount, 1);
-	pi_state->key = FUTEX_KEY_INIT;
+	state->owner = NULL;
+	atomic_set(&state->refcount, 1);
+	state->key = FUTEX_KEY_INIT;
 
-	current->pi_state_cache = pi_state;
+	current->pi_state_cache = state;
 
 	return 0;
 }
 
-static struct futex_pi_state * alloc_pi_state(void)
+static struct futex_state *alloc_futex_state(void)
 {
-	struct futex_pi_state *pi_state = current->pi_state_cache;
+	struct futex_state *state = current->pi_state_cache;
 
-	WARN_ON(!pi_state);
+	WARN_ON(!state);
 	current->pi_state_cache = NULL;
 
-	return pi_state;
+	return state;
 }
 
 /*
- * Drops a reference to the pi_state object and frees or caches it
+ * Drops a reference to the futex state object and frees or caches it
  * when the last reference is gone.
  *
  * Must be called with the hb lock held.
  */
-static void put_pi_state(struct futex_pi_state *pi_state)
+static void put_futex_state(struct futex_state *state)
 {
-	if (!pi_state)
+	if (!state)
 		return;
 
-	if (!atomic_dec_and_test(&pi_state->refcount))
+	if (!atomic_dec_and_test(&state->refcount))
 		return;
 
 	/*
-	 * If pi_state->owner is NULL, the owner is most probably dying
-	 * and has cleaned up the pi_state already
+	 * If state->owner is NULL, the owner is most probably dying
+	 * and has cleaned up the futex state already
 	 */
-	if (pi_state->owner) {
-		raw_spin_lock_irq(&pi_state->owner->pi_lock);
-		list_del_init(&pi_state->list);
-		raw_spin_unlock_irq(&pi_state->owner->pi_lock);
+	if (state->owner) {
+		raw_spin_lock_irq(&state->owner->pi_lock);
+		list_del_init(&state->list);
+		raw_spin_unlock_irq(&state->owner->pi_lock);
 
-		rt_mutex_proxy_unlock(&pi_state->pi_mutex, pi_state->owner);
+		rt_mutex_proxy_unlock(&state->pi_mutex, state->owner);
 	}
 
 	if (current->pi_state_cache)
-		kfree(pi_state);
+		kfree(state);
 	else {
 		/*
-		 * pi_state->list is already empty.
-		 * clear pi_state->owner.
+		 * state->list is already empty.
+		 * clear state->owner.
 		 * refcount is at 0 - put it back to 1.
 		 */
-		pi_state->owner = NULL;
-		atomic_set(&pi_state->refcount, 1);
-		current->pi_state_cache = pi_state;
+		state->owner = NULL;
+		atomic_set(&state->refcount, 1);
+		current->pi_state_cache = state;
 	}
 }
 
@@ -907,7 +908,7 @@ static struct task_struct * futex_find_get_task(pid_t pid)
 void exit_pi_state_list(struct task_struct *curr)
 {
 	struct list_head *next, *head = &curr->pi_state_list;
-	struct futex_pi_state *pi_state;
+	struct futex_state *pi_state;
 	struct futex_hash_bucket *hb;
 	union futex_key key = FUTEX_KEY_INIT;
 
@@ -922,7 +923,7 @@ void exit_pi_state_list(struct task_struct *curr)
 	while (!list_empty(head)) {
 
 		next = head->next;
-		pi_state = list_entry(next, struct futex_pi_state, list);
+		pi_state = list_entry(next, struct futex_state, list);
 		key = pi_state->key;
 		hb = hash_futex(&key);
 		raw_spin_unlock_irq(&curr->pi_lock);
@@ -1009,8 +1010,8 @@ void exit_pi_state_list(struct task_struct *curr)
  * the pi_state against the user space value. If correct, attach to
  * it.
  */
-static int attach_to_pi_state(u32 uval, struct futex_pi_state *pi_state,
-			      struct futex_pi_state **ps)
+static int attach_to_pi_state(u32 uval, struct futex_state *pi_state,
+			      struct futex_state **ps)
 {
 	pid_t pid = uval & FUTEX_TID_MASK;
 
@@ -1081,10 +1082,10 @@ static int attach_to_pi_state(u32 uval, struct futex_pi_state *pi_state,
  * it after doing proper sanity checks.
  */
 static int attach_to_pi_owner(u32 uval, union futex_key *key,
-			      struct futex_pi_state **ps)
+			      struct futex_state **ps)
 {
 	pid_t pid = uval & FUTEX_TID_MASK;
-	struct futex_pi_state *pi_state;
+	struct futex_state *pi_state;
 	struct task_struct *p;
 
 	/*
@@ -1125,7 +1126,7 @@ static int attach_to_pi_owner(u32 uval, union futex_key *key,
 	/*
 	 * No existing pi state. First waiter. [2]
 	 */
-	pi_state = alloc_pi_state();
+	pi_state = alloc_futex_state();
 
 	/*
 	 * Initialize the pi_mutex in locked state and make @p
@@ -1149,7 +1150,7 @@ static int attach_to_pi_owner(u32 uval, union futex_key *key,
 }
 
 static int lookup_pi_state(u32 uval, struct futex_hash_bucket *hb,
-			   union futex_key *key, struct futex_pi_state **ps)
+			   union futex_key *key, struct futex_state **ps)
 {
 	struct futex_q *match = futex_top_waiter(hb, key);
 
@@ -1201,7 +1202,7 @@ static int lock_pi_update_atomic(u32 __user *uaddr, u32 uval, u32 newval)
  */
 static int futex_lock_pi_atomic(u32 __user *uaddr, struct futex_hash_bucket *hb,
 				union futex_key *key,
-				struct futex_pi_state **ps,
+				struct futex_state **ps,
 				struct task_struct *task, int set_waiters)
 {
 	u32 uval, newval, vpid = task_pid_vnr(task);
@@ -1327,7 +1328,7 @@ static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this,
 			 struct futex_hash_bucket *hb)
 {
 	struct task_struct *new_owner;
-	struct futex_pi_state *pi_state = this->pi_state;
+	struct futex_state *pi_state = this->pi_state;
 	u32 uninitialized_var(curval), newval;
 	DEFINE_WAKE_Q(wake_q);
 	bool deboost;
@@ -1667,7 +1668,7 @@ static int futex_proxy_trylock_atomic(u32 __user *pifutex,
 				 struct futex_hash_bucket *hb1,
 				 struct futex_hash_bucket *hb2,
 				 union futex_key *key1, union futex_key *key2,
-				 struct futex_pi_state **ps, int set_waiters)
+				 struct futex_state **ps, int set_waiters)
 {
 	struct futex_q *top_waiter = NULL;
 	u32 curval;
@@ -1736,7 +1737,7 @@ static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
 {
 	union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
 	int drop_count = 0, task_count = 0, ret;
-	struct futex_pi_state *pi_state = NULL;
+	struct futex_state *pi_state = NULL;
 	struct futex_hash_bucket *hb1, *hb2;
 	struct futex_q *this, *next;
 	DEFINE_WAKE_Q(wake_q);
@@ -1753,7 +1754,7 @@ static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
 		 * requeue_pi requires a pi_state, try to allocate it now
 		 * without any locks in case it fails.
 		 */
-		if (refill_pi_state_cache())
+		if (refill_futex_state_cache())
 			return -ENOMEM;
 		/*
 		 * requeue_pi must wake as many tasks as it can, up to nr_wake
@@ -1965,7 +1966,7 @@ static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
 				 * object.
 				 */
 				this->pi_state = NULL;
-				put_pi_state(pi_state);
+				put_futex_state(pi_state);
 				/*
 				 * We stop queueing more waiters and let user
 				 * space deal with the mess.
@@ -1982,7 +1983,7 @@ static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
 	 * in futex_proxy_trylock_atomic() or in lookup_pi_state(). We
 	 * need to drop it here again.
 	 */
-	put_pi_state(pi_state);
+	put_futex_state(pi_state);
 
 out_unlock:
 	double_unlock_hb(hb1, hb2);
@@ -2137,7 +2138,7 @@ static void unqueue_me_pi(struct futex_q *q)
 	__unqueue_futex(q);
 
 	BUG_ON(!q->pi_state);
-	put_pi_state(q->pi_state);
+	put_futex_state(q->pi_state);
 	q->pi_state = NULL;
 
 	spin_unlock(q->lock_ptr);
@@ -2153,7 +2154,7 @@ static int fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
 				struct task_struct *newowner)
 {
 	u32 newtid = task_pid_vnr(newowner) | FUTEX_WAITERS;
-	struct futex_pi_state *pi_state = q->pi_state;
+	struct futex_state *pi_state = q->pi_state;
 	struct task_struct *oldowner = pi_state->owner;
 	u32 uval, uninitialized_var(curval), newval;
 	int ret;
@@ -2529,7 +2530,7 @@ static int futex_lock_pi(u32 __user *uaddr, unsigned int flags,
 	struct futex_q q = futex_q_init;
 	int res, ret;
 
-	if (refill_pi_state_cache())
+	if (refill_futex_state_cache())
 		return -ENOMEM;
 
 	to = futex_setup_timer(time, &timeout, FLAGS_CLOCKRT, 0);
@@ -2910,7 +2911,7 @@ static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
 			 * Drop the reference to the pi state which
 			 * the requeue_pi() code acquired for us.
 			 */
-			put_pi_state(q.pi_state);
+			put_futex_state(q.pi_state);
 			spin_unlock(q.lock_ptr);
 		}
 	} else {
-- 
1.8.3.1

[toc] | [prev] | [next] | [standalone]

#1573336 — [PATCH-tip v5 10/21] TP-futex: Enable robust handling

The TP futexes don't have code to handle the death of futex
owners. There are 2 different cases that need to be considered.

As top waiter gets a reference to the task structure of the futex
owner, the task structure will never go away even if the owner dies.
When the futex owner died while the top waiter is spinning, the task
structure will be marked dead or the pid won't have a matching task
structure if the task died before a reference is taken. Alternatively,
if robust futex attribute is enabled, the FUTEX_OWNER_DIED bit of the
futex word may also be set. In all those cases, what the top waiter
need to do is to grab the futex directly. An informational message
will be printed to highlight this event.

If the futex owner died while the top waiter is sleeping, we need to
make the exit processing code to wake up the top waiter. This is done
by chaining the futex state object into the pi_state_list of the futex
owner before the top waiter sleeps so that if exit_pi_state_list()
is called, the wakeup will happen. The top waiter needs to remove
its futex state object from the pi_state_list of the old owner if
the ownership changes hand or when the lock is acquired.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/futex.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 79 insertions(+), 6 deletions(-)

diff --git a/kernel/futex.c b/kernel/futex.c
index 6a59e6d..46a1a4b 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -1006,7 +1006,7 @@ static struct task_struct * futex_find_get_task(pid_t pid)
 }
 
 /*
- * This task is holding PI mutexes at exit time => bad.
+ * This task is holding PI or TP mutexes at exit time => bad.
  * Kernel cleans up PI-state, but userspace is likely hosed.
  * (Robust-futex cleanup is separate and might save the day for userspace.)
  */
@@ -1023,12 +1023,31 @@ void exit_pi_state_list(struct task_struct *curr)
 	 * We are a ZOMBIE and nobody can enqueue itself on
 	 * pi_state_list anymore, but we have to be careful
 	 * versus waiters unqueueing themselves:
+	 *
+	 * For TP futexes, the only purpose of showing up in the
+	 * pi_state_list is for this function to wake up the serialization
+	 * mutex owner (state->mutex_owner). We don't actually need to take
+	 * the HB lock. The futex state and task struct won't go away as long
+	 * as we hold the pi_lock.
 	 */
 	raw_spin_lock_irq(&curr->pi_lock);
 	while (!list_empty(head)) {
 
 		next = head->next;
 		pi_state = list_entry(next, struct futex_state, list);
+
+		if (pi_state->type == TYPE_TP) {
+			struct task_struct *owner;
+
+			owner = READ_ONCE(pi_state->mutex_owner);
+			WARN_ON(list_empty(&pi_state->list));
+			list_del_init(&pi_state->list);
+			pi_state->owner = NULL;
+			if (owner)
+				wake_up_process(owner);
+			continue;
+		}
+
 		key = pi_state->key;
 		hb = hash_futex(&key);
 		raw_spin_unlock_irq(&curr->pi_lock);
@@ -3185,8 +3204,8 @@ int handle_futex_death(u32 __user *uaddr, struct task_struct *curr, int pi)
 			goto retry;
 
 		/*
-		 * Wake robust non-PI futexes here. The wakeup of
-		 * PI futexes happens in exit_pi_state():
+		 * Wake robust wait-wake futexes here. The wakeup of
+		 * PI and TP futexes happens in exit_pi_state():
 		 */
 		if (!pi && (uval & FUTEX_WAITERS))
 			futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
@@ -3327,6 +3346,12 @@ void exit_robust_list(struct task_struct *curr)
  * Unlike the other futexes, the futex_q structures aren't used. Instead,
  * they will queue up in the serialization mutex of the futex state container
  * queued in the hash bucket.
+ *
+ * To handle the exceptional case that the futex owner died, the robust
+ * futexes list mechanism is used to for waking up sleeping top waiter.
+ * Checks are also made in the futex_spin_on_owner() loop for dead task
+ * structure or invalid pid. In both cases, the top waiter will take over
+ * the ownership of the futex.
  */
 
 /**
@@ -3515,6 +3540,10 @@ static inline int futex_set_waiters_bit(u32 __user *uaddr, u32 *puval)
 static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 			       struct futex_state *state)
 {
+#define OWNER_DEAD_MESSAGE					\
+	"futex: owner pid %d of TP futex 0x%lx was %s.\n"	\
+	"\tLock is now acquired by pid %d!\n"
+
 	int ret;
 	u32 uval;
 	u32 owner_pid = 0;
@@ -3529,13 +3558,47 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 			break;
 
 		if ((uval & FUTEX_TID_MASK) != owner_pid) {
-			if (owner_task)
+			if (owner_task) {
+				/*
+				 * task_pi_list_del() should always be
+				 * done before put_task_struct(). The futex
+				 * state may have been dequeued if the task
+				 * is dead.
+				 */
+				if (state->owner) {
+					WARN_ON(state->owner != owner_task);
+					task_pi_list_del(state, true);
+				}
 				put_task_struct(owner_task);
+			}
 
 			owner_pid  = uval & FUTEX_TID_MASK;
 			owner_task = futex_find_get_task(owner_pid);
 		}
 
+		if (unlikely(!owner_task ||
+			    (owner_task->flags & PF_EXITING) ||
+			    (uval & FUTEX_OWNER_DIED))) {
+			/*
+			 * PID invalid or exiting/dead task, we can directly
+			 * grab the lock now.
+			 */
+			u32 curval;
+			char *owner_state;
+
+			ret = cmpxchg_futex_value_locked(&curval, uaddr, uval,
+							 vpid);
+			if (unlikely(ret))
+				break;
+			if (curval != uval)
+				continue;
+			owner_state = (owner_task || (uval & FUTEX_OWNER_DIED))
+				    ? "dead" : "invalid";
+			pr_info(OWNER_DEAD_MESSAGE, owner_pid,
+				(long)uaddr, owner_state, vpid);
+			break;
+		}
+
 		if (need_resched()) {
 			__set_current_state(TASK_RUNNING);
 			schedule_preempt_disabled();
@@ -3554,12 +3617,17 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 
 		/*
 		 * If the owner isn't active, we need to go to sleep after
-		 * making sure that the FUTEX_WAITERS bit is set.
+		 * making sure that the FUTEX_WAITERS bit is set. We also
+		 * need to put the futex state into the futex owner's
+		 * pi_state_list to prevent deadlock when the owner dies.
 		 */
 		ret = futex_set_waiters_bit(uaddr, &uval);
 		if (ret)
 			break;
 
+		if (owner_task && !state->owner)
+			task_pi_list_add(owner_task, state);
+
 		/*
 		 * Do a trylock after setting the task state to make
 		 * sure we won't miss a wakeup.
@@ -3595,8 +3663,13 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 			goto retry;
 	}
 
-	if (owner_task)
+	if (owner_task) {
+		if (state->owner)
+			task_pi_list_del(state, false);
 		put_task_struct(owner_task);
+	} else {
+		WARN_ON(state->owner);
+	}
 
 	/*
 	 * Cleanup futex state.
-- 
1.8.3.1

[toc] | [prev] | [next] | [standalone]

#1573337 — [PATCH-tip v5 08/21] futex: Allow direct attachment of futex_state objects to hash bucket

Currently, the futex state objects can only be located indirectly as

        hash bucket => futex_q => futex state

Actually it can be beneficial in some cases to locate the futex state
object directly from the hash bucket without the futex_q middleman.
Therefore, a new list head to link the futex state objects as well
as a new spinlock to manage them are added to the hash bucket.

To limit size increase for UP systems, these new fields are only for
SMP machines where the cacheline alignment of the hash bucket leaves
it with enough empty space for the new fields.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/futex.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

diff --git a/kernel/futex.c b/kernel/futex.c
index 928212c..2ced6c0 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -209,6 +209,11 @@ struct futex_state {
 	struct list_head list;
 
 	/*
+	 * Can link to fs_head in the owning hash bucket.
+	 */
+	struct list_head fs_list;
+
+	/*
 	 * The PI object:
 	 */
 	struct rt_mutex pi_mutex;
@@ -264,11 +269,24 @@ struct futex_q {
  * Hash buckets are shared by all the futex_keys that hash to the same
  * location.  Each key may have multiple futex_q structures, one for each task
  * waiting on a futex.
+ *
+ * Alternatively (in SMP), a key can be associated with a unique futex_state
+ * object where multiple waiters waiting for that futex can queue up in that
+ * futex_state object without using the futex_q structure. A separate
+ * futex_state lock (fs_lock) is used for processing those futex_state objects.
  */
 struct futex_hash_bucket {
 	atomic_t waiters;
 	spinlock_t lock;
 	struct plist_head chain;
+
+#ifdef CONFIG_SMP
+	/*
+	 * Fields for managing futex_state object list
+	 */
+	spinlock_t fs_lock;
+	struct list_head fs_head;
+#endif
 } ____cacheline_aligned_in_smp;
 
 /*
@@ -875,6 +893,8 @@ static int refill_futex_state_cache(void)
 		return -ENOMEM;
 
 	INIT_LIST_HEAD(&state->list);
+	INIT_LIST_HEAD(&state->fs_list);
+
 	/* pi_mutex gets initialized later */
 	state->owner = NULL;
 	atomic_set(&state->refcount, 1);
@@ -3365,6 +3385,10 @@ static int __init futex_init(void)
 		atomic_set(&futex_queues[i].waiters, 0);
 		plist_head_init(&futex_queues[i].chain);
 		spin_lock_init(&futex_queues[i].lock);
+#ifdef CONFIG_SMP
+		INIT_LIST_HEAD(&futex_queues[i].fs_head);
+		spin_lock_init(&futex_queues[i].fs_lock);
+#endif
 	}
 
 	return 0;
-- 
1.8.3.1

[toc] | [prev] | [next] | [standalone]

#1573338 — [PATCH-tip v5 03/21] futex: Consolidate duplicated timer setup code

A new futex_setup_timer() helper function is added to consolidate all
the hrtimer_sleeper setup code.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/futex.c | 67 ++++++++++++++++++++++++++++++++--------------------------
 1 file changed, 37 insertions(+), 30 deletions(-)

diff --git a/kernel/futex.c b/kernel/futex.c
index a6d6c87..07886ba 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -479,6 +479,35 @@ static void drop_futex_key_refs(union futex_key *key)
 }
 
 /**
+ * futex_setup_timer - set up the sleeping hrtimer.
+ * @time:	ptr to the given timeout value
+ * @timeout:	the hrtimer_sleeper structure to be set up
+ * @flags:	futex flags
+ * @range_ns:	optional range in ns
+ *
+ * Return: Initialized hrtimer_sleeper structure or NULL if no timeout
+ *	   value given
+ */
+static inline struct hrtimer_sleeper *
+futex_setup_timer(ktime_t *time, struct hrtimer_sleeper *timeout,
+		  int flags, u64 range_ns)
+{
+	if (!time)
+		return NULL;
+
+	hrtimer_init_on_stack(&timeout->timer, (flags & FLAGS_CLOCKRT) ?
+			      CLOCK_REALTIME : CLOCK_MONOTONIC,
+			      HRTIMER_MODE_ABS);
+	hrtimer_init_sleeper(timeout, current);
+	if (range_ns)
+		hrtimer_set_expires_range_ns(&timeout->timer, *time, range_ns);
+	else
+		hrtimer_set_expires(&timeout->timer, *time);
+
+	return timeout;
+}
+
+/**
  * get_futex_key() - Get parameters which are the keys for a futex
  * @uaddr:	virtual address of the futex
  * @fshared:	0 for a PROCESS_PRIVATE futex, 1 for PROCESS_SHARED
@@ -2404,7 +2433,7 @@ static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,
 static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
 		      ktime_t *abs_time, u32 bitset)
 {
-	struct hrtimer_sleeper timeout, *to = NULL;
+	struct hrtimer_sleeper timeout, *to;
 	struct restart_block *restart;
 	struct futex_hash_bucket *hb;
 	struct futex_q q = futex_q_init;
@@ -2414,17 +2443,8 @@ static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
 		return -EINVAL;
 	q.bitset = bitset;
 
-	if (abs_time) {
-		to = &timeout;
-
-		hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
-				      CLOCK_REALTIME : CLOCK_MONOTONIC,
-				      HRTIMER_MODE_ABS);
-		hrtimer_init_sleeper(to, current);
-		hrtimer_set_expires_range_ns(&to->timer, *abs_time,
-					     current->timer_slack_ns);
-	}
-
+	to = futex_setup_timer(abs_time, &timeout, flags,
+			       current->timer_slack_ns);
 retry:
 	/*
 	 * Prepare to wait on uaddr. On success, holds hb lock and increments
@@ -2504,7 +2524,7 @@ static long futex_wait_restart(struct restart_block *restart)
 static int futex_lock_pi(u32 __user *uaddr, unsigned int flags,
 			 ktime_t *time, int trylock)
 {
-	struct hrtimer_sleeper timeout, *to = NULL;
+	struct hrtimer_sleeper timeout, *to;
 	struct futex_hash_bucket *hb;
 	struct futex_q q = futex_q_init;
 	int res, ret;
@@ -2512,13 +2532,7 @@ static int futex_lock_pi(u32 __user *uaddr, unsigned int flags,
 	if (refill_pi_state_cache())
 		return -ENOMEM;
 
-	if (time) {
-		to = &timeout;
-		hrtimer_init_on_stack(&to->timer, CLOCK_REALTIME,
-				      HRTIMER_MODE_ABS);
-		hrtimer_init_sleeper(to, current);
-		hrtimer_set_expires(&to->timer, *time);
-	}
+	to = futex_setup_timer(time, &timeout, FLAGS_CLOCKRT, 0);
 
 retry:
 	ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q.key, VERIFY_WRITE);
@@ -2813,7 +2827,7 @@ static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
 				 u32 val, ktime_t *abs_time, u32 bitset,
 				 u32 __user *uaddr2)
 {
-	struct hrtimer_sleeper timeout, *to = NULL;
+	struct hrtimer_sleeper timeout, *to;
 	struct rt_mutex_waiter rt_waiter;
 	struct rt_mutex *pi_mutex = NULL;
 	struct futex_hash_bucket *hb;
@@ -2827,15 +2841,8 @@ static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
 	if (!bitset)
 		return -EINVAL;
 
-	if (abs_time) {
-		to = &timeout;
-		hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
-				      CLOCK_REALTIME : CLOCK_MONOTONIC,
-				      HRTIMER_MODE_ABS);
-		hrtimer_init_sleeper(to, current);
-		hrtimer_set_expires_range_ns(&to->timer, *abs_time,
-					     current->timer_slack_ns);
-	}
+	to = futex_setup_timer(abs_time, &timeout, flags,
+			       current->timer_slack_ns);
 
 	/*
 	 * The waiter is allocated on our stack, manipulated by the requeue
-- 
1.8.3.1

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

#1573340 — [PATCH-tip v5 11/21] TP-futex: Implement lock handoff to prevent lock starvation

The current TP futexes has no guarantee that the top waiter
(serialization mutex owner) can get the lock within a finite time.
As a result, lock starvation can happen.

A lock handoff mechanism is added to the TP futexes to prevent lock
starvation from happening. The idea is that the top waiter can set a
special handoff_pid variable with its own pid. The futex owner will
then check this variable at unlock time to see if it should free the
futex or change its value to the designated pid to transfer the lock
directly to the top waiter.

This change does have the effect of limiting the amount of unfairness
and hence may adversely affect performance depending on the workloads.

Currently the handoff mechanism is triggered when the top waiter fails
to acquire the lock after about 5ms of spinning and sleeping. So the
maximum lock handoff rate is about 200 handoffs per second.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/futex.c | 59 ++++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 53 insertions(+), 6 deletions(-)

diff --git a/kernel/futex.c b/kernel/futex.c
index 46a1a4b..348b44c 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -63,6 +63,7 @@
 #include <linux/pid.h>
 #include <linux/nsproxy.h>
 #include <linux/ptrace.h>
+#include <linux/sched/clock.h>
 #include <linux/sched/rt.h>
 #include <linux/sched/wake_q.h>
 #include <linux/sched/mm.h>
@@ -237,6 +238,8 @@ struct futex_state {
 	struct task_struct *mutex_owner;	/* For TP futexes only */
 	atomic_t refcount;
 
+	u32 handoff_pid;			/* For TP futexes only */
+
 	enum futex_type type;
 	union futex_key key;
 };
@@ -914,6 +917,7 @@ static int refill_futex_state_cache(void)
 	/* pi_mutex gets initialized later */
 	state->owner = NULL;
 	state->mutex_owner = NULL;
+	state->handoff_pid = 0;
 	atomic_set(&state->refcount, 1);
 	state->key = FUTEX_KEY_INIT;
 
@@ -3337,8 +3341,9 @@ void exit_robust_list(struct task_struct *curr)
  * and unlocking.
  *
  * The purpose of this FUTEX_WAITERS bit is to make the unlocker wake up the
- * serialization mutex owner. Not having the FUTEX_WAITERS bit set doesn't
- * mean there is no waiter in the kernel.
+ * serialization mutex owner or to hand off the lock directly to the top
+ * waiter. Not having the FUTEX_WAITERS bit set doesn't mean there is no
+ * waiter in the kernel.
  *
  * Like PI futexes, TP futexes are orthogonal to robust futexes can be
  * used together.
@@ -3354,6 +3359,16 @@ void exit_robust_list(struct task_struct *curr)
  * the ownership of the futex.
  */
 
+/*
+ * Timeout value for enabling lock handoff and prevent lock starvation.
+ *
+ * Currently, lock handoff will be enabled if the top waiter can't get the
+ * futex after about 5ms. To reduce time checking overhead, it is only done
+ * after every 128 spins or right after wakeup. As a result, the actual
+ * elapsed time will be a bit longer than the specified value.
+ */
+#define TP_HANDOFF_TIMEOUT	5000000	/* 5ms	*/
+
 /**
  * lookup_futex_state - Looking up the futex state structure.
  * @hb:		 hash bucket
@@ -3433,6 +3448,7 @@ static inline int put_futex_state_unlocked(struct futex_state *state)
  * If waiter is true
  * then
  *   don't preserve the flag bits;
+ *   check for handoff (futex word == own pid)
  * else
  *   preserve the flag bits
  * endif
@@ -3451,6 +3467,9 @@ static inline int futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval,
 
 	uval = *puval;
 
+	if (waiter && (uval & FUTEX_TID_MASK) == vpid)
+		return 1;
+
 	if (uval & FUTEX_TID_MASK)
 		return 0;	/* Trylock fails */
 
@@ -3544,10 +3563,12 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 	"futex: owner pid %d of TP futex 0x%lx was %s.\n"	\
 	"\tLock is now acquired by pid %d!\n"
 
-	int ret;
+	int ret, loopcnt = 1;
+	bool handoff_set = false;
 	u32 uval;
 	u32 owner_pid = 0;
 	struct task_struct *owner_task = NULL;
+	u64 handoff_time = running_clock() + TP_HANDOFF_TIMEOUT;
 
 	preempt_disable();
 	WRITE_ONCE(state->mutex_owner, current);
@@ -3602,6 +3623,7 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 		if (need_resched()) {
 			__set_current_state(TASK_RUNNING);
 			schedule_preempt_disabled();
+			loopcnt = 0;
 			continue;
 		}
 
@@ -3610,6 +3632,23 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 			break;
 		}
 
+		/*
+		 * Enable lock handoff if the elapsed time exceed the timeout
+		 * value. We also need to set the FUTEX_WAITERS bit to make
+		 * sure that futex lock holder will initiate the handoff at
+		 * unlock time.
+		 */
+		if (!handoff_set && !(loopcnt++ & 0x7f)) {
+			if (running_clock() > handoff_time) {
+				WARN_ON(READ_ONCE(state->handoff_pid));
+				ret = futex_set_waiters_bit(uaddr, &uval);
+				if (ret)
+					break;
+				WRITE_ONCE(state->handoff_pid, vpid);
+				handoff_set = true;
+			}
+		}
+
 		if (owner_task->on_cpu) {
 			cpu_relax();
 			continue;
@@ -3652,8 +3691,10 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 		 * lock stealing happen in between setting the FUTEX_WAITERS
 		 * and setting state to TASK_INTERRUPTIBLE.
 		 */
-		if (!(uval & FUTEX_OWNER_DIED) && (uval & FUTEX_WAITERS))
+		if (!(uval & FUTEX_OWNER_DIED) && (uval & FUTEX_WAITERS)) {
 			schedule_preempt_disabled();
+			loopcnt = 0;
+		}
 		__set_current_state(TASK_RUNNING);
 	}
 
@@ -3675,6 +3716,7 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 	 * Cleanup futex state.
 	 */
 	WRITE_ONCE(state->mutex_owner, NULL);
+	WRITE_ONCE(state->handoff_pid, 0);
 
 	preempt_enable();
 	return ret;
@@ -3789,6 +3831,7 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags)
 static int futex_unlock(u32 __user *uaddr, unsigned int flags)
 {
 	u32 uval, vpid = task_pid_vnr(current);
+	u32 newpid = 0;
 	union futex_key key = FUTEX_KEY_INIT;
 	struct futex_hash_bucket *hb;
 	struct futex_state *state = NULL;
@@ -3822,6 +3865,10 @@ static int futex_unlock(u32 __user *uaddr, unsigned int flags)
 		goto out_put_key;
 	}
 
+	newpid = READ_ONCE(state->handoff_pid);
+	if (newpid)
+		WRITE_ONCE(state->handoff_pid, 0);
+
 	owner = READ_ONCE(state->mutex_owner);
 	if (owner)
 		wake_q_add(&wake_q, owner);
@@ -3829,13 +3876,13 @@ static int futex_unlock(u32 __user *uaddr, unsigned int flags)
 	spin_unlock(&hb->fs_lock);
 
 	/*
-	 * Unlock the futex.
+	 * Unlock the futex or handoff to the next owner.
 	 * The flag bits are not preserved to encourage more lock stealing.
 	 */
 	for (;;) {
 		u32 old = uval;
 
-		if (cmpxchg_futex_value(&uval, uaddr, old, 0)) {
+		if (cmpxchg_futex_value(&uval, uaddr, old, newpid)) {
 			ret = -EFAULT;
 			break;
 		}
-- 
1.8.3.1

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web