This patch adds a new document file on how to use the TO futexes.
Signed-off-by: Waiman Long <Waiman.Long@xxxxxxx>
---
Documentation/00-INDEX | 2 +
Documentation/to-futex.txt | 124 ++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 126 insertions(+), 0 deletions(-)
create mode 100644 Documentation/to-futex.txt
diff --git a/Documentation/00-INDEX b/Documentation/00-INDEX
index cb9a6c6..a39f020 100644
--- a/Documentation/00-INDEX
+++ b/Documentation/00-INDEX
@@ -439,6 +439,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)
+to-futex.txt
+ - Documentation on lightweight throughput-optimized futexes.
trace/
- directory with info on tracing technologies within linux
unaligned-memory-access.txt
diff --git a/Documentation/to-futex.txt b/Documentation/to-futex.txt
new file mode 100644
index 0000000..58a0637
--- /dev/null
+++ b/Documentation/to-futex.txt
@@ -0,0 +1,124 @@
+Started by: Waiman Long <waiman.long@xxxxxxx>
+
+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.
+
+Throughput-optimized futex is a solution to both the wakeup latency
+and spinlock contention problems by encouraging lock stealing and
+optimistically spinning on a locked futex when the lock owner is
+running within the kernel until the lock is free. 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.
+
+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.
+
+Implementation
+--------------
+
+Like the PI and robust futexes, a 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 new FUTEX_LOCK_TO futex(2) syscall.
+
+ futex(uaddr, FUTEX_LOCK_TO, 0, timeout, NULL, 0);
+
+Only the optional timeout parameter is being used by the new futex
+call.
+
+A kernel mutex is used for serialization. The top lock waiter that is
+the owner of the serialization mutex will try to steal the lock when
+it is available and delay setting the FUTEX_WAITERS bit to encourage
+more lock stealing in the userspace. When it has waited long enough
+or is going to sleep, it then set the FUTEX_WAITERS bit to make sure
+that it is going to get the lock next and is woken up when the lock
+owner releases the lock.
+
+When it is time to unlock, the lock owner has to atomically change the
+futex value from its TID to 0. If that fails, it can optionally clear
+the TID portion of the futex value to encourage faster lock transfer.
+It also has to issue a FUTEX_UNLOCK_TO futex system call to wake up
+the top waiter, if it has slept.
+
+ futex(uaddr, FUTEX_UNLOCK_TO, 0, NULL, NULL, 0);
+
+A return value of 1 from the FUTEX_UNLOCK_TO futex(2) syscall
+indicates a task has been woken up. The syscall returns 0 if no
+sleeping task is woken.
+
+The error number returned by a FUTEX_UNLOCK_TO call on an empty futex
+can be used to decide if the TO futex functionality is implemented in
+the kernel. If it is present, no error will be returned. Otherwise it
+will be ENOSYS.
+
+TO futexes require the kernel to have support for the cmpxchg
+functionality. For architectures that don't support cmpxchg, TO
+futexes will not be supported as well.
+
+The TO futexes are orthogonal to the robust futexes and can be combined
+without problem.
+
+Usage Scenario
+--------------
+
+A TO futex can be used as an exclusive lock to guard a critical
+section which are unlikely to go to sleep. The waiters in a TO 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 benefit when compared with a wait-wake futex in this case.
+
+Sample Code
+-----------
+
+The following are sample code to implement a simple lock and unlock
+function.
+
+__thread int tid; /* Thread ID */
+
+void mutex_lock(int *faddr)
+{
+ if (cmpxchg(faddr, 0, tid) == 0)
+ return;
+ for (;;)
+ if (futex(faddr, FUTEX_LOCK_TO, ...) == 0)
+ break;
+}
+
+void mutex_unlock(int *faddr)
+{
+ int old, fval;
+
+ if ((fval = cmpxchg(faddr, tid, 0)) == tid)
+ return;
+ /* Clear only the TID portion of the futex */
+ for (;;) {
+ old = fval;
+ fval = cmpxchg(faddr, old, old & ~FUTEX_TID_MASK);
+ if (fval == old)
+ break;
+ }
+ if (fval & FUTEX_WAITERS)
+ futex(faddr, FUTEX_UNLOCK_TO, ...);
+}
--
1.7.1
--
To unsubscribe from this list: send the line "unsubscribe linux-doc" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
