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

Groups > linux.kernel > #1606812 > unrolled thread

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

Back to article view | Back to linux.kernel

Contents

  [PATCH-tip v6 00/22] futex: Introducing throughput-optimized (TP) futexes Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 12/22] TP-futex: Return status code on FUTEX_LOCK calls Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 11/22] TP-futex: Implement lock handoff to prevent lock starvation Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 20/22] perf bench: Extend mutex/rwlock futex suite to test TP futexes Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 21/22] sched, TP-futex: Make wake_up_q() return wakeup count Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 02/22] perf bench: New microbenchmark for userspace rwlock performance Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 03/22] futex: Consolidate duplicated timer setup code Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 04/22] futex: Rename futex_pi_state to futex_state Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 22/22] futex: Dump internal futex state via debugfs Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 19/22] TP-futex, doc: Update TP futexes document on shared locking Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 08/22] futex: Allow direct attachment of futex_state objects to hash bucket Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 09/22] futex: Introduce throughput-optimized (TP) futexes Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 01/22] perf bench: New microbenchmark for userspace mutex performance Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 18/22] TP-futex: Group readers together in wait queue Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
      Re: [PATCH-tip v6 18/22] TP-futex: Group readers together in wait  queue kbuild test robot <lkp@intel.com> - 2017-03-24 09:30 +0100
      Re: [PATCH-tip v6 18/22] TP-futex: Group readers together in wait  queue kbuild test robot <lkp@intel.com> - 2017-03-24 09:40 +0100
    [PATCH-tip v6 16/22] TP-futex: Support userspace reader/writer locks Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 13/22] TP-futex: Add timeout support Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 17/22] TP-futex: Enable kernel reader lock stealing Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 05/22] futex: Add helpers to get & cmpxchg futex value without lock Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 10/22] TP-futex: Enable robust handling Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 07/22] futex: Add a new futex type field into futex_state Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 15/22] TP-futex, doc: Add TP futexes documentation Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100
    [PATCH-tip v6 14/22] TP-futex: Optionally return EAGAIN for userspace locking Waiman Long <longman@redhat.com> - 2017-03-22 18:50 +0100

Page 2 of 2 — ← Prev page 1 [2]

#1606835 — [PATCH-tip v6 10/22] 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 7270552..af367e8 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);
@@ -3197,8 +3216,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);
@@ -3339,6 +3358,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.
  */
 
 /**
@@ -3537,6 +3562,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;
@@ -3551,13 +3580,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();
@@ -3576,12 +3639,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.
@@ -3617,8 +3685,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]

#1606836 — [PATCH-tip v6 07/22] futex: Add a new futex type field into futex_state

As the futex_state structure will be overloaded in later patches
to be used by non-PI futexes, it is necessary to add a type field to
distinguish among different types of futexes.

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

diff --git a/kernel/futex.c b/kernel/futex.c
index cff711d..fd365b2 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -193,6 +193,10 @@
 #define FLAGS_CLOCKRT		0x02
 #define FLAGS_HAS_TIMEOUT	0x04
 
+enum futex_type {
+	TYPE_PI = 0,
+};
+
 /*
  * Futex state object:
  *  - Priority Inheritance state
@@ -212,6 +216,7 @@ struct futex_state {
 	struct task_struct *owner;
 	atomic_t refcount;
 
+	enum futex_type type;
 	union futex_key key;
 };
 
@@ -905,13 +910,14 @@ static void put_futex_state(struct futex_state *state)
 		return;
 
 	/*
-	 * If state->owner is NULL, the owner is most probably dying
-	 * and has cleaned up the futex state already
+	 * If state->owner is NULL and the type is TYPE_PI, the owner is
+	 * most probably dying and has cleaned up the futex state already.
 	 */
 	if (state->owner) {
 		task_pi_list_del(state, false);
 
-		rt_mutex_proxy_unlock(&state->pi_mutex, state->owner);
+		if (state->type == TYPE_PI)
+			rt_mutex_proxy_unlock(&state->pi_mutex, state->owner);
 	}
 
 	if (current->pi_state_cache)
@@ -1064,7 +1070,7 @@ static int attach_to_pi_state(u32 uval, struct futex_state *pi_state,
 	/*
 	 * Userspace might have messed up non-PI and PI futexes [3]
 	 */
-	if (unlikely(!pi_state))
+	if (unlikely(!pi_state || (pi_state->type != TYPE_PI)))
 		return -EINVAL;
 
 	WARN_ON(!atomic_read(&pi_state->refcount));
@@ -1182,6 +1188,7 @@ static int attach_to_pi_owner(u32 uval, union futex_key *key,
 
 	/* Store the key for possible exit cleanups: */
 	pi_state->key = *key;
+	pi_state->type = TYPE_PI;
 
 	WARN_ON(!list_empty(&pi_state->list));
 	list_add(&pi_state->list, &p->pi_state_list);
-- 
1.8.3.1

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

#1606837 — [PATCH-tip v6 15/22] TP-futex, doc: Add TP futexes documentation

This patch adds a new document file on how to use the TP futexes.

In term of locking performance, a futex locking microbenchmark
was written where separate userspace mutexes are implemented using
wait-wake (WW), PI and TP futexes respectively. This microbenchmark
was intructed to run 10s of locking operations with a load-to-load
latency of 10 on a 2-socket 36-core E5-2699 v3 system (HT off).
The added latency was there to reduce the chance that a given CPU could
monopolize the lock over multiple consecutive locking operations.
The system was running on a 4.11 based kernel.  the results of the
benchmark runs were as follows:

                      WW futex    PI futex   TP futex     Glibc
                      --------    --------   --------     -----
Total locking ops    49,065,154   372,301   57,209,013  39,667,389
Per-thread avg/sec      136,291     1,034      158,897     110,186
Per-thread min/sec      131,597     1,033      139,441     106,397
Per-thread max/sec      140,414     1,051      176,816     117,527
% Stddev                  0.22%     0.05%        1.27%       0.36%
lock slowpaths       10,292,953   372,114   11,864,228       -
unlock slowpaths     14,306,857   372,110           25       -

Besides a 17% performance increase, another major difference between
WW and TP futexes was the dramatic reduction in the number of unlock
slowpaths that were being taken.

By increasing the load latency (amount of time spent in the critical
section) from a default of 1, the performance discrepancies between
WW and TP futexes actually increases in the x86 system as shown in
the tables below.

  Load Latency  WW locking ops  TP locking ops  % change
  ------------  --------------  --------------  --------
      5           40,365,507      54,993,009      +36%
     10           33,193,154      47,696,618      +44%
     20           25,855,039      37,553,477      +45%
     30           21,157,759      31,667,873      +50%
     40           18,216,561      27,408,570      +50%
     50           16,103,078      24,299,436      +51%
    100           10,233,914      14,375,505      +40%
  1us sleep          178,018         174,938       -2%

The performance advantage increased to about 50% and then started
dropping off. The TP futexes, however, are not designed for sleeping
lock holders as there are no performance advantage.

On a 2-socket 10-core and 80-thread Power8 system, the benchmark
results were:
                      WW futex    PI futex   TP futex     Glibc
                      --------    --------   --------     -----
Total locking ops    12,939,135  1,758,607  21,502,680  10,896,395
Per-thread avg/sec       16,172      2,198      26,851      13,619
Per-thread min/sec       13,527      2,197      23,101      11,524
Per-thread max/sec       19,519      2,220      27,629      15,952
% Stddev                  0.93%      0.01%       0.25%       0.87%
lock slowpaths        2,856,730  1,758,403   7,092,852       -
unlock slowpaths      4,279,445  1,758,403          13       -

Signed-off-by: Waiman Long <longman@redhat.com>
---
 Documentation/00-INDEX     |   2 +
 Documentation/tp-futex.txt | 180 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 182 insertions(+)
 create mode 100644 Documentation/tp-futex.txt

diff --git a/Documentation/00-INDEX b/Documentation/00-INDEX
index 793acf9..436d2ed 100644
--- a/Documentation/00-INDEX
+++ b/Documentation/00-INDEX
@@ -416,6 +416,8 @@ this_cpu_ops.txt
 	- List rationale behind and the way to use this_cpu operations.
 thermal/
 	- directory with information on managing thermal issues (CPU/temp)
+tp-futex.txt
+	- Documentation on lightweight throughput-optimized futexes.
 trace/
 	- directory with info on tracing technologies within linux
 translations/
diff --git a/Documentation/tp-futex.txt b/Documentation/tp-futex.txt
new file mode 100644
index 0000000..d040c18
--- /dev/null
+++ b/Documentation/tp-futex.txt
@@ -0,0 +1,180 @@
+Started by: Waiman Long <longman@redhat.com>
+
+Throughput-Optimized Futexes
+----------------------------
+
+There are two main problems for a wait-wake futex (FUTEX_WAIT and
+FUTEX_WAKE) when used for creating user-space locking primitives:
+
+ 1) With a wait-wake futex, tasks waiting for a lock are put to sleep
+    in the futex queue to be woken up by the lock owner when it is done
+    with the lock. Waking up a sleeping task, however, introduces some
+    additional latency which can be large especially if the critical
+    section protected by the lock is relatively short. This may cause
+    a performance bottleneck on large systems with many CPUs running
+    applications that need a lot of inter-thread synchronization.
+
+ 2) The performance of the wait-wake futex is currently
+    spinlock-constrained.  When many threads are contending for a
+    futex in a large system with many CPUs, it is not unusual to have
+    spinlock contention accounting for more than 90% of the total
+    CPU cycles consumed at various points in time.
+
+This two problems can create performance bottlenecks with a
+futex-constrained workload especially on systems with large number
+of CPUs.
+
+The goal of the throughput-optimized (TP) futexes is maximize the
+locking throughput at the expense of fairness and deterministic
+latency. This is done by encouraging lock stealing and optimistic
+spinning on a locked futex when the futex owner is running.  This is
+the same optimistic spinning mechanism used by the kernel mutex and rw
+semaphore implementations to improve performance. Optimistic spinning
+was done without taking any lock.
+
+Lock stealing is known to be a performance enhancement technique as
+long as the safeguards are in place to make sure that there will be no
+lock starvation.  The TP futexes has a built-in lock hand-off mechanism
+to prevent lock starvation from happening as long as the underlying
+kernel mutexes that the TP futexes use have no lock starvation problem.
+
+When the top lock waiter has failed to acquire the lock within a
+certain time threshold, it will initiate the hand-off mechanism by
+forcing the unlocker to transfer the lock to itself instead of freeing
+it for others to grab. This limit the maximum latency a waiter has
+to wait.
+
+Because of optimistic spinning, the lock holders are much less likely
+to go into the kernel to wake up sleeping waiters when performing
+unlock operation. This also helps to increase throughput.
+
+The downside of this improved throughput is the increased variance
+of the actual response times of the locking operations. Some locking
+operations will be very fast, while others may be considerably slower.
+The average response time should be better than the wait-wake futexes.
+
+Performance-wise, TP futexes should be faster than wait-wake futexes
+especially if the futex locker holders do not sleep. For workload
+that does a lot of sleeping within the critical sections, the TP
+futexes may not be faster than the wait-wake futexes.
+
+Implementation
+--------------
+
+Like the PI and robust futexes, an exclusive lock acquirer has to
+atomically put its thread ID (TID) into the lower 30 bits of the
+32-bit futex which should has an original value of 0. If it succeeds,
+it will be the owner of the futex. Otherwise, it has to call into
+the kernel using the FUTEX_LOCK futex(2) syscall.
+
+  futex(uaddr, FUTEX_LOCK, uslock, timeout, NULL, 0);
+
+The two parameters that can be set are:
+ 1) uslock - return EAGAIN to perform userspace locking when set,
+    otherwise locking will be done in the kernel.
+ 2) timeout - specify the timeout value (relative to current time)
+    and ETIMEDOUT will be returned if lock cannot be acquired or
+    available within the timeout period.
+
+Userspace locking can improve throughput by reducing lock hold time,
+but it also has the risk of lock starvation. So kernel locking should
+be used after a number of userspace locking failures.
+
+Inside the kernel, a kernel mutex is used for serialization among
+the futex waiters. Only the top lock waiter which is the owner of
+the serialization mutex is allowed to continuously spin and attempt
+to acquire the lock.  Other lock waiters will have one attempt to
+steal the lock before entering the mutex queues.
+
+When the exclusive futex lock owner is no longer running, the top
+waiter will set the FUTEX_WAITERS bit before going to sleep. This is
+to make sure the futex owner will go into the kernel at unlock time
+to wake up the top waiter.
+
+The return values of the above futex locking syscall, if non-negative,
+are status code that consists of 2 fields - the lock acquisition code
+(bits 0-7) and the number of sleeps (bits 8-30) in the optimistic
+spinning loop before acquiring the futex. A negative returned value
+means an error has happened.
+
+The lock acquisition code can have the following values:
+ a) 0 - lock stolen as non-top waiter
+ b) 1 - lock acquired as the top waiter
+ c) 2 - lock explicitly handed off by the unlocker
+
+When it is time to unlock, the exclusive lock owner has to atomically
+change the futex value from its TID to 0. If that fails, it has to
+issue a FUTEX_UNLOCK futex(2) syscall to wake up the top waiter.
+
+  futex(uaddr, FUTEX_UNLOCK, 0, NULL, NULL, 0);
+
+A return value of 1 from the FUTEX_UNLOCK futex(2) syscall indicates
+a task has been woken up. The syscall returns 0 if no sleeping task
+is woken. A negative value will be returned if an error happens.
+
+The error number returned by a FUTEX_UNLOCK syscall on an empty futex
+can be used to decide if the TP futex functionality is implemented
+in the kernel. If it is present, an EPERFM error will be returned.
+Otherwise it will return ENOSYS.
+
+TP futexes require the kernel to have SMP support as well as support
+for the cmpxchg functionality. For architectures that don't support
+cmpxchg, TP futexes will not be supported as well.
+
+The exclusive locking TP futexes are orthogonal to the robust futexes
+and can be combined without problem. The TP futexes also have code
+to detect the death of an exclusive TP futex owner and handle the
+transfer of futex ownership automatically without the use of the
+robust futexes. The only case that the TP futexes cannot handle alone
+is the PID wrap-around issue where another process with the same PID
+as the real futex owner because of PID wrap-around is mis-identified
+as the owner of a futex.
+
+If a signal comes at the right instance in time, it is possible that a
+lock handoff has happened but the top waiter returns an error instead.
+So the userspace locking code will need to check for this very unlikely
+situation. It is possible for the kernel to handle this internally,
+but it will probably reduce performance. Userspace code can handle
+this more efficiently.
+
+Usage Scenario
+--------------
+
+A TP futex can be used to implement a user-space exclusive lock
+or mutex to guard a critical section which are unlikely to go to
+sleep. The waiters in a TP futex, however, will fall back to sleep in
+a wait queue if the lock owner isn't running. Therefore, it can also be
+used when the critical section is long and prone to sleeping. However,
+it may not have the performance gain when compared with a wait-wake
+futex in this case.
+
+The wait-wake futexes are more versatile as they can also be used to
+implement other locking primitives like semaphores or conditional
+variables.  So the TP futex is not a direct replacement of the
+wait-wake futex. However for userspace mutexes or rwlocks, the TP
+futex is likely a better option than the wait-wake futex.
+
+Sample Code
+-----------
+
+The following are sample code to implement simple mutex lock and
+unlock functions.
+
+__thread int thread_id;
+
+void mutex_lock(int *faddr)
+{
+	if (cmpxchg(faddr, 0, thread_id) == 0)
+		return;
+	while (futex(faddr, FUTEX_LOCK, 0, NULL, NULL, 0) > 0)
+		;
+}
+
+void mutex_unlock(int *faddr)
+{
+	int old, fval;
+
+	if (cmpxchg(faddr, thread_id, 0) == thread_id)
+		return;
+	futex(faddr, FUTEX_UNLOCK, 0, NULL, NULL, 0);
+}
-- 
1.8.3.1

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

#1606839 — [PATCH-tip v6 14/22] TP-futex: Optionally return EAGAIN for userspace locking

A performance disadvantage of TP futexes versus wait-wake futex is
the fact that locking was done in the kernel for TP futexes instead of
in the userspace like the WW futexes. The additional latency between
when the lock was taken in the kernel and when the task returned to
the userspace would be added to the lock hold time. This could make
TP futexes less performant than WW futexes in some circumstances.

To remedy this deficiency, we now allow users to specify where locking
should be done.

  futex(uaddr, FUTEX_LOCK, uslock, timeout, NULL, 0);

If the uslock flag is set, the EAGAIN error will be returned like
the WW futexes to indicate that locking can now be done in the
userspace. If it is not set, locking will be done in the kernel
instead. It is possible that lock handoff can happen even if uslock
flag is set. So the userspace code must check the lock value to see
if this is the case.

Doing locking in the userspace can lead to lock starvation in some
cases unless some precautionary measure is taken. So it is recommended
that kernel locking should be performed after a number of failures
in userspace locking.

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

diff --git a/kernel/futex.c b/kernel/futex.c
index b54f429..7f41999 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -196,6 +196,7 @@
 #endif
 #define FLAGS_CLOCKRT		0x02
 #define FLAGS_HAS_TIMEOUT	0x04
+#define FLAGS_TP_USLOCK		0x08	/* Do the locking in userspace */
 
 enum futex_type {
 	TYPE_PI = 0,
@@ -3465,10 +3466,11 @@ static inline int put_futex_state_unlocked(struct futex_state *state)
 
 /**
  * __futex_trylock - try to lock the userspace futex word (0 => vpid).
- * @uaddr: futex address
- * @vpid:  PID of current task
- * @puval: storage location for current futex value
- * @steal: false for top waiter, true otherwise for lock stealing
+ * @uaddr:   futex address
+ * @vpid:    PID of current task
+ * @puval:   storage location for current futex value
+ * @steal:   false for top waiter, true otherwise for lock stealing
+ * @chkonly: check lock status without actual locking
  *
  * The HB fs_lock should NOT be held while calling this function.
  * The flag bits are ignored in the trylock.
@@ -3485,10 +3487,11 @@ static inline int put_futex_state_unlocked(struct futex_state *state)
  *	   TP_LOCK_HANDOFF if lock was handed off;
  *	   0 if lock acquisition failed;
  *	   -EFAULT if an error happened.
+ *	   -EAGAIN if chkonly and lock is free
  *	   *puval will contain the latest futex value when trylock fails.
  */
 static inline int __futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval,
-				  const bool steal)
+				  const bool steal, bool chkonly)
 {
 	u32 uval, flags = 0;
 
@@ -3500,6 +3503,9 @@ static inline int __futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval,
 	if (!steal && (uval & FUTEX_TID_MASK) == vpid)
 		return TP_LOCK_HANDOFF;
 
+	if (chkonly && !uval)
+		return -EAGAIN;
+
 	if (uval & FUTEX_TID_MASK)
 		return 0;	/* Trylock fails */
 
@@ -3512,21 +3518,23 @@ static inline int __futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval,
 	return (*puval == uval) ? TP_LOCK_ACQUIRED : 0;
 }
 
-static int futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval)
+static int futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval,
+			 bool chkonly)
 {
-	return __futex_trylock(uaddr, vpid, puval, false);
+	return __futex_trylock(uaddr, vpid, puval, false, chkonly);
 }
 
 static int futex_steal_lock(u32 __user *uaddr, const u32 vpid, u32 *puval)
 {
-	return __futex_trylock(uaddr, vpid, puval, true);
+	return __futex_trylock(uaddr, vpid, puval, true, false);
 }
 
 /**
  * futex_trylock_preempt_disabled - futex_trylock with preemption disabled
- * @uaddr: futex address
- * @vpid:  PID of current task
- * @puval: storage location for current futex value
+ * @uaddr:   futex address
+ * @vpid:    PID of current task
+ * @puval:   storage location for current futex value
+ * @chkonly: check lock status without actual locking
  *
  * The preempt_disable() has similar effect as pagefault_disable(). As a
  * result, we will have to disable page fault as well and handle the case
@@ -3537,14 +3545,15 @@ static int futex_steal_lock(u32 __user *uaddr, const u32 vpid, u32 *puval)
  *	   TP_LOCK_HANDOFF if lock was handed off;
  *	   0 if lock acquisition failed;
  *	   -EFAULT if an error happened.
+ *	   -EAGAIN if chkonly and lock is free
  */
 static inline int futex_trylock_preempt_disabled(u32 __user *uaddr,
-						 const u32 vpid, u32 *puval)
+			const u32 vpid, u32 *puval, bool chkonly)
 {
 	int ret;
 
 	pagefault_disable();
-	ret = futex_trylock(uaddr, vpid, puval);
+	ret = futex_trylock(uaddr, vpid, puval, chkonly);
 	pagefault_enable();
 
 	return ret;
@@ -3584,6 +3593,7 @@ static inline int futex_set_waiters_bit(u32 __user *uaddr, u32 *puval)
  * @vpid:    PID of current task
  * @state:   futex state object
  * @timeout: hrtimer_sleeper structure
+ * @chkonly: check lock status without actual locking
  *
  * Spin on the futex word while the futex owner is active. Otherwise, set
  * the FUTEX_WAITERS bit and go to sleep.
@@ -3600,7 +3610,8 @@ 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,
-			       struct hrtimer_sleeper *timeout)
+			       struct hrtimer_sleeper *timeout,
+			       bool chkonly)
 {
 #define OWNER_DEAD_MESSAGE					\
 	"futex: owner pid %d of TP futex 0x%lx was %s.\n"	\
@@ -3618,7 +3629,8 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 	WRITE_ONCE(state->mutex_owner, current);
 retry:
 	for (;;) {
-		ret = futex_trylock_preempt_disabled(uaddr, vpid, &uval);
+		ret = futex_trylock_preempt_disabled(uaddr, vpid, &uval,
+						     chkonly);
 		if (ret)
 			break;
 
@@ -3730,7 +3742,8 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 		 * wakeup		sleep
 		 */
 		set_current_state(TASK_INTERRUPTIBLE);
-		ret = futex_trylock_preempt_disabled(uaddr, vpid, &uval);
+		ret = futex_trylock_preempt_disabled(uaddr, vpid, &uval,
+						     chkonly);
 		if (ret) {
 			__set_current_state(TASK_RUNNING);
 			break;
@@ -3871,9 +3884,11 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 
 	/*
 	 * As the mutex owner, we can now spin on the futex word as well as
-	 * the active-ness of the futex owner.
+	 * the active-ness of the futex owner. The spinner will return EAGAIN
+	 * without taking the lock when the userspace locking flag is set.
 	 */
-	ret = futex_spin_on_owner(uaddr, vpid, state, to);
+	ret = futex_spin_on_owner(uaddr, vpid, state, to,
+				  flags & FLAGS_TP_USLOCK);
 
 	mutex_unlock(&state->mutex);
 
@@ -4047,6 +4062,8 @@ long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
 		return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 1);
 #ifdef CONFIG_SMP
 	case FUTEX_LOCK:
+		if (val)
+			flags |= FLAGS_TP_USLOCK;
 		return futex_lock(uaddr, flags, timeout);
 	case FUTEX_UNLOCK:
 		return futex_unlock(uaddr, flags);
-- 
1.8.3.1

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | linux.kernel

csiph-web