annotate Documentation/robust-futex-ABI.txt @ 524:7f8b544237bf

netfront: Allow netfront in domain 0.

This is useful if your physical network device is in a utility domain.

Signed-off-by: Ian Campbell <ian.campbell@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Tue Apr 15 15:18:58 2008 +0100 (2008-04-15)
parents 831230e53067
rev   line source
ian@0 1 Started by Paul Jackson <pj@sgi.com>
ian@0 2
ian@0 3 The robust futex ABI
ian@0 4 --------------------
ian@0 5
ian@0 6 Robust_futexes provide a mechanism that is used in addition to normal
ian@0 7 futexes, for kernel assist of cleanup of held locks on task exit.
ian@0 8
ian@0 9 The interesting data as to what futexes a thread is holding is kept on a
ian@0 10 linked list in user space, where it can be updated efficiently as locks
ian@0 11 are taken and dropped, without kernel intervention. The only additional
ian@0 12 kernel intervention required for robust_futexes above and beyond what is
ian@0 13 required for futexes is:
ian@0 14
ian@0 15 1) a one time call, per thread, to tell the kernel where its list of
ian@0 16 held robust_futexes begins, and
ian@0 17 2) internal kernel code at exit, to handle any listed locks held
ian@0 18 by the exiting thread.
ian@0 19
ian@0 20 The existing normal futexes already provide a "Fast Userspace Locking"
ian@0 21 mechanism, which handles uncontested locking without needing a system
ian@0 22 call, and handles contested locking by maintaining a list of waiting
ian@0 23 threads in the kernel. Options on the sys_futex(2) system call support
ian@0 24 waiting on a particular futex, and waking up the next waiter on a
ian@0 25 particular futex.
ian@0 26
ian@0 27 For robust_futexes to work, the user code (typically in a library such
ian@0 28 as glibc linked with the application) has to manage and place the
ian@0 29 necessary list elements exactly as the kernel expects them. If it fails
ian@0 30 to do so, then improperly listed locks will not be cleaned up on exit,
ian@0 31 probably causing deadlock or other such failure of the other threads
ian@0 32 waiting on the same locks.
ian@0 33
ian@0 34 A thread that anticipates possibly using robust_futexes should first
ian@0 35 issue the system call:
ian@0 36
ian@0 37 asmlinkage long
ian@0 38 sys_set_robust_list(struct robust_list_head __user *head, size_t len);
ian@0 39
ian@0 40 The pointer 'head' points to a structure in the threads address space
ian@0 41 consisting of three words. Each word is 32 bits on 32 bit arch's, or 64
ian@0 42 bits on 64 bit arch's, and local byte order. Each thread should have
ian@0 43 its own thread private 'head'.
ian@0 44
ian@0 45 If a thread is running in 32 bit compatibility mode on a 64 native arch
ian@0 46 kernel, then it can actually have two such structures - one using 32 bit
ian@0 47 words for 32 bit compatibility mode, and one using 64 bit words for 64
ian@0 48 bit native mode. The kernel, if it is a 64 bit kernel supporting 32 bit
ian@0 49 compatibility mode, will attempt to process both lists on each task
ian@0 50 exit, if the corresponding sys_set_robust_list() call has been made to
ian@0 51 setup that list.
ian@0 52
ian@0 53 The first word in the memory structure at 'head' contains a
ian@0 54 pointer to a single linked list of 'lock entries', one per lock,
ian@0 55 as described below. If the list is empty, the pointer will point
ian@0 56 to itself, 'head'. The last 'lock entry' points back to the 'head'.
ian@0 57
ian@0 58 The second word, called 'offset', specifies the offset from the
ian@0 59 address of the associated 'lock entry', plus or minus, of what will
ian@0 60 be called the 'lock word', from that 'lock entry'. The 'lock word'
ian@0 61 is always a 32 bit word, unlike the other words above. The 'lock
ian@0 62 word' holds 3 flag bits in the upper 3 bits, and the thread id (TID)
ian@0 63 of the thread holding the lock in the bottom 29 bits. See further
ian@0 64 below for a description of the flag bits.
ian@0 65
ian@0 66 The third word, called 'list_op_pending', contains transient copy of
ian@0 67 the address of the 'lock entry', during list insertion and removal,
ian@0 68 and is needed to correctly resolve races should a thread exit while
ian@0 69 in the middle of a locking or unlocking operation.
ian@0 70
ian@0 71 Each 'lock entry' on the single linked list starting at 'head' consists
ian@0 72 of just a single word, pointing to the next 'lock entry', or back to
ian@0 73 'head' if there are no more entries. In addition, nearby to each 'lock
ian@0 74 entry', at an offset from the 'lock entry' specified by the 'offset'
ian@0 75 word, is one 'lock word'.
ian@0 76
ian@0 77 The 'lock word' is always 32 bits, and is intended to be the same 32 bit
ian@0 78 lock variable used by the futex mechanism, in conjunction with
ian@0 79 robust_futexes. The kernel will only be able to wakeup the next thread
ian@0 80 waiting for a lock on a threads exit if that next thread used the futex
ian@0 81 mechanism to register the address of that 'lock word' with the kernel.
ian@0 82
ian@0 83 For each futex lock currently held by a thread, if it wants this
ian@0 84 robust_futex support for exit cleanup of that lock, it should have one
ian@0 85 'lock entry' on this list, with its associated 'lock word' at the
ian@0 86 specified 'offset'. Should a thread die while holding any such locks,
ian@0 87 the kernel will walk this list, mark any such locks with a bit
ian@0 88 indicating their holder died, and wakeup the next thread waiting for
ian@0 89 that lock using the futex mechanism.
ian@0 90
ian@0 91 When a thread has invoked the above system call to indicate it
ian@0 92 anticipates using robust_futexes, the kernel stores the passed in 'head'
ian@0 93 pointer for that task. The task may retrieve that value later on by
ian@0 94 using the system call:
ian@0 95
ian@0 96 asmlinkage long
ian@0 97 sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr,
ian@0 98 size_t __user *len_ptr);
ian@0 99
ian@0 100 It is anticipated that threads will use robust_futexes embedded in
ian@0 101 larger, user level locking structures, one per lock. The kernel
ian@0 102 robust_futex mechanism doesn't care what else is in that structure, so
ian@0 103 long as the 'offset' to the 'lock word' is the same for all
ian@0 104 robust_futexes used by that thread. The thread should link those locks
ian@0 105 it currently holds using the 'lock entry' pointers. It may also have
ian@0 106 other links between the locks, such as the reverse side of a double
ian@0 107 linked list, but that doesn't matter to the kernel.
ian@0 108
ian@0 109 By keeping its locks linked this way, on a list starting with a 'head'
ian@0 110 pointer known to the kernel, the kernel can provide to a thread the
ian@0 111 essential service available for robust_futexes, which is to help clean
ian@0 112 up locks held at the time of (a perhaps unexpectedly) exit.
ian@0 113
ian@0 114 Actual locking and unlocking, during normal operations, is handled
ian@0 115 entirely by user level code in the contending threads, and by the
ian@0 116 existing futex mechanism to wait for, and wakeup, locks. The kernels
ian@0 117 only essential involvement in robust_futexes is to remember where the
ian@0 118 list 'head' is, and to walk the list on thread exit, handling locks
ian@0 119 still held by the departing thread, as described below.
ian@0 120
ian@0 121 There may exist thousands of futex lock structures in a threads shared
ian@0 122 memory, on various data structures, at a given point in time. Only those
ian@0 123 lock structures for locks currently held by that thread should be on
ian@0 124 that thread's robust_futex linked lock list a given time.
ian@0 125
ian@0 126 A given futex lock structure in a user shared memory region may be held
ian@0 127 at different times by any of the threads with access to that region. The
ian@0 128 thread currently holding such a lock, if any, is marked with the threads
ian@0 129 TID in the lower 29 bits of the 'lock word'.
ian@0 130
ian@0 131 When adding or removing a lock from its list of held locks, in order for
ian@0 132 the kernel to correctly handle lock cleanup regardless of when the task
ian@0 133 exits (perhaps it gets an unexpected signal 9 in the middle of
ian@0 134 manipulating this list), the user code must observe the following
ian@0 135 protocol on 'lock entry' insertion and removal:
ian@0 136
ian@0 137 On insertion:
ian@0 138 1) set the 'list_op_pending' word to the address of the 'lock word'
ian@0 139 to be inserted,
ian@0 140 2) acquire the futex lock,
ian@0 141 3) add the lock entry, with its thread id (TID) in the bottom 29 bits
ian@0 142 of the 'lock word', to the linked list starting at 'head', and
ian@0 143 4) clear the 'list_op_pending' word.
ian@0 144
ian@0 145 On removal:
ian@0 146 1) set the 'list_op_pending' word to the address of the 'lock word'
ian@0 147 to be removed,
ian@0 148 2) remove the lock entry for this lock from the 'head' list,
ian@0 149 2) release the futex lock, and
ian@0 150 2) clear the 'lock_op_pending' word.
ian@0 151
ian@0 152 On exit, the kernel will consider the address stored in
ian@0 153 'list_op_pending' and the address of each 'lock word' found by walking
ian@0 154 the list starting at 'head'. For each such address, if the bottom 29
ian@0 155 bits of the 'lock word' at offset 'offset' from that address equals the
ian@0 156 exiting threads TID, then the kernel will do two things:
ian@0 157
ian@0 158 1) if bit 31 (0x80000000) is set in that word, then attempt a futex
ian@0 159 wakeup on that address, which will waken the next thread that has
ian@0 160 used to the futex mechanism to wait on that address, and
ian@0 161 2) atomically set bit 30 (0x40000000) in the 'lock word'.
ian@0 162
ian@0 163 In the above, bit 31 was set by futex waiters on that lock to indicate
ian@0 164 they were waiting, and bit 30 is set by the kernel to indicate that the
ian@0 165 lock owner died holding the lock.
ian@0 166
ian@0 167 The kernel exit code will silently stop scanning the list further if at
ian@0 168 any point:
ian@0 169
ian@0 170 1) the 'head' pointer or an subsequent linked list pointer
ian@0 171 is not a valid address of a user space word
ian@0 172 2) the calculated location of the 'lock word' (address plus
ian@0 173 'offset') is not the valud address of a 32 bit user space
ian@0 174 word
ian@0 175 3) if the list contains more than 1 million (subject to
ian@0 176 future kernel configuration changes) elements.
ian@0 177
ian@0 178 When the kernel sees a list entry whose 'lock word' doesn't have the
ian@0 179 current threads TID in the lower 29 bits, it does nothing with that
ian@0 180 entry, and goes on to the next entry.
ian@0 181
ian@0 182 Bit 29 (0x20000000) of the 'lock word' is reserved for future use.