docs: move locking-specific documents to locking/

Several files under Documentation/*.txt describe some type of
locking API. Move them to locking/ subdir and add to the
locking/index.rst index file.

Signed-off-by: Mauro Carvalho Chehab <mchehab+huawei@kernel.org>
Link: https://lore.kernel.org/r/dd833a10bbd0b2c1461d78913f5ec28a7e27f00b.1588345503.git.mchehab+huawei@kernel.org
Signed-off-by: Jonathan Corbet <corbet@lwn.net>

1 files changed, 0 insertions, 221 deletions

diff --git a/Documentation/robust-futexes.txt b/Documentation/robust-futexes.txt
deleted file mode 100644
index 6361fb01c9c1..000000000000
--- a/Documentation/robust-futexes.txt
+++ /dev/null
@@ -1,221 +0,0 @@
-========================================
-A description of what robust futexes are
-========================================
-
-:Started by: Ingo Molnar <mingo@redhat.com>
-
-Background
-----------
-
-what are robust futexes? To answer that, we first need to understand
-what futexes are: normal futexes are special types of locks that in the
-noncontended case can be acquired/released from userspace without having
-to enter the kernel.
-
-A futex is in essence a user-space address, e.g. a 32-bit lock variable
-field. If userspace notices contention (the lock is already owned and
-someone else wants to grab it too) then the lock is marked with a value
-that says "there's a waiter pending", and the sys_futex(FUTEX_WAIT)
-syscall is used to wait for the other guy to release it. The kernel
-creates a 'futex queue' internally, so that it can later on match up the
-waiter with the waker - without them having to know about each other.
-When the owner thread releases the futex, it notices (via the variable
-value) that there were waiter(s) pending, and does the
-sys_futex(FUTEX_WAKE) syscall to wake them up.  Once all waiters have
-taken and released the lock, the futex is again back to 'uncontended'
-state, and there's no in-kernel state associated with it. The kernel
-completely forgets that there ever was a futex at that address. This
-method makes futexes very lightweight and scalable.
-
-"Robustness" is about dealing with crashes while holding a lock: if a
-process exits prematurely while holding a pthread_mutex_t lock that is
-also shared with some other process (e.g. yum segfaults while holding a
-pthread_mutex_t, or yum is kill -9-ed), then waiters for that lock need
-to be notified that the last owner of the lock exited in some irregular
-way.
-
-To solve such types of problems, "robust mutex" userspace APIs were
-created: pthread_mutex_lock() returns an error value if the owner exits
-prematurely - and the new owner can decide whether the data protected by
-the lock can be recovered safely.
-
-There is a big conceptual problem with futex based mutexes though: it is
-the kernel that destroys the owner task (e.g. due to a SEGFAULT), but
-the kernel cannot help with the cleanup: if there is no 'futex queue'
-(and in most cases there is none, futexes being fast lightweight locks)
-then the kernel has no information to clean up after the held lock!
-Userspace has no chance to clean up after the lock either - userspace is
-the one that crashes, so it has no opportunity to clean up. Catch-22.
-
-In practice, when e.g. yum is kill -9-ed (or segfaults), a system reboot
-is needed to release that futex based lock. This is one of the leading
-bugreports against yum.
-
-To solve this problem, the traditional approach was to extend the vma
-(virtual memory area descriptor) concept to have a notion of 'pending
-robust futexes attached to this area'. This approach requires 3 new
-syscall variants to sys_futex(): FUTEX_REGISTER, FUTEX_DEREGISTER and
-FUTEX_RECOVER. At do_exit() time, all vmas are searched to see whether
-they have a robust_head set. This approach has two fundamental problems
-left:
-
- - it has quite complex locking and race scenarios. The vma-based
-   approach had been pending for years, but they are still not completely
-   reliable.
-
- - they have to scan _every_ vma at sys_exit() time, per thread!
-
-The second disadvantage is a real killer: pthread_exit() takes around 1
-microsecond on Linux, but with thousands (or tens of thousands) of vmas
-every pthread_exit() takes a millisecond or more, also totally
-destroying the CPU's L1 and L2 caches!
-
-This is very much noticeable even for normal process sys_exit_group()
-calls: the kernel has to do the vma scanning unconditionally! (this is
-because the kernel has no knowledge about how many robust futexes there
-are to be cleaned up, because a robust futex might have been registered
-in another task, and the futex variable might have been simply mmap()-ed
-into this process's address space).
-
-This huge overhead forced the creation of CONFIG_FUTEX_ROBUST so that
-normal kernels can turn it off, but worse than that: the overhead makes
-robust futexes impractical for any type of generic Linux distribution.
-
-So something had to be done.
-
-New approach to robust futexes
-------------------------------
-
-At the heart of this new approach there is a per-thread private list of
-robust locks that userspace is holding (maintained by glibc) - which
-userspace list is registered with the kernel via a new syscall [this
-registration happens at most once per thread lifetime]. At do_exit()
-time, the kernel checks this user-space list: are there any robust futex
-locks to be cleaned up?
-
-In the common case, at do_exit() time, there is no list registered, so
-the cost of robust futexes is just a simple current->robust_list != NULL
-comparison. If the thread has registered a list, then normally the list
-is empty. If the thread/process crashed or terminated in some incorrect
-way then the list might be non-empty: in this case the kernel carefully
-walks the list [not trusting it], and marks all locks that are owned by
-this thread with the FUTEX_OWNER_DIED bit, and wakes up one waiter (if
-any).
-
-The list is guaranteed to be private and per-thread at do_exit() time,
-so it can be accessed by the kernel in a lockless way.
-
-There is one race possible though: since adding to and removing from the
-list is done after the futex is acquired by glibc, there is a few
-instructions window for the thread (or process) to die there, leaving
-the futex hung. To protect against this possibility, userspace (glibc)
-also maintains a simple per-thread 'list_op_pending' field, to allow the
-kernel to clean up if the thread dies after acquiring the lock, but just
-before it could have added itself to the list. Glibc sets this
-list_op_pending field before it tries to acquire the futex, and clears
-it after the list-add (or list-remove) has finished.
-
-That's all that is needed - all the rest of robust-futex cleanup is done
-in userspace [just like with the previous patches].
-
-Ulrich Drepper has implemented the necessary glibc support for this new
-mechanism, which fully enables robust mutexes.
-
-Key differences of this userspace-list based approach, compared to the
-vma based method:
-
- - it's much, much faster: at thread exit time, there's no need to loop
-   over every vma (!), which the VM-based method has to do. Only a very
-   simple 'is the list empty' op is done.
-
- - no VM changes are needed - 'struct address_space' is left alone.
-
- - no registration of individual locks is needed: robust mutexes don't
-   need any extra per-lock syscalls. Robust mutexes thus become a very
-   lightweight primitive - so they don't force the application designer
-   to do a hard choice between performance and robustness - robust
-   mutexes are just as fast.
-
- - no per-lock kernel allocation happens.
-
- - no resource limits are needed.
-
- - no kernel-space recovery call (FUTEX_RECOVER) is needed.
-
- - the implementation and the locking is "obvious", and there are no
-   interactions with the VM.
-
-Performance
------------
-
-I have benchmarked the time needed for the kernel to process a list of 1
-million (!) held locks, using the new method [on a 2GHz CPU]:
-
- - with FUTEX_WAIT set [contended mutex]: 130 msecs
- - without FUTEX_WAIT set [uncontended mutex]: 30 msecs
-
-I have also measured an approach where glibc does the lock notification
-[which it currently does for !pshared robust mutexes], and that took 256
-msecs - clearly slower, due to the 1 million FUTEX_WAKE syscalls
-userspace had to do.
-
-(1 million held locks are unheard of - we expect at most a handful of
-locks to be held at a time. Nevertheless it's nice to know that this
-approach scales nicely.)
-
-Implementation details
-----------------------
-
-The patch adds two new syscalls: one to register the userspace list, and
-one to query the registered list pointer::
-
- asmlinkage long
- sys_set_robust_list(struct robust_list_head __user *head,
-                     size_t len);
-
- asmlinkage long
- sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr,
-                     size_t __user *len_ptr);
-
-List registration is very fast: the pointer is simply stored in
-current->robust_list. [Note that in the future, if robust futexes become
-widespread, we could extend sys_clone() to register a robust-list head
-for new threads, without the need of another syscall.]
-
-So there is virtually zero overhead for tasks not using robust futexes,
-and even for robust futex users, there is only one extra syscall per
-thread lifetime, and the cleanup operation, if it happens, is fast and
-straightforward. The kernel doesn't have any internal distinction between
-robust and normal futexes.
-
-If a futex is found to be held at exit time, the kernel sets the
-following bit of the futex word::
-
-	#define FUTEX_OWNER_DIED        0x40000000
-
-and wakes up the next futex waiter (if any). User-space does the rest of
-the cleanup.
-
-Otherwise, robust futexes are acquired by glibc by putting the TID into
-the futex field atomically. Waiters set the FUTEX_WAITERS bit::
-
-	#define FUTEX_WAITERS           0x80000000
-
-and the remaining bits are for the TID.
-
-Testing, architecture support
------------------------------
-
-I've tested the new syscalls on x86 and x86_64, and have made sure the
-parsing of the userspace list is robust [ ;-) ] even if the list is
-deliberately corrupted.
-
-i386 and x86_64 syscalls are wired up at the moment, and Ulrich has
-tested the new glibc code (on x86_64 and i386), and it works for his
-robust-mutex testcases.
-
-All other architectures should build just fine too - but they won't have
-the new syscalls yet.
-
-Architectures need to implement the new futex_atomic_cmpxchg_inatomic()
-inline function before writing up the syscalls.