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