1// Copyright 2016 The Fuchsia Authors 2// 3// Use of this source code is governed by a MIT-style 4// license that can be found in the LICENSE file or at 5// https://opensource.org/licenses/MIT 6 7#include <object/futex_context.h> 8 9#include <assert.h> 10#include <lib/user_copy/user_ptr.h> 11#include <object/thread_dispatcher.h> 12#include <trace.h> 13#include <zircon/types.h> 14 15#define LOCAL_TRACE 0 16 17FutexContext::FutexContext() { 18 LTRACE_ENTRY; 19} 20 21FutexContext::~FutexContext() { 22 LTRACE_ENTRY; 23 24 // All of the threads should have removed themselves from wait queues 25 // by the time the process has exited. 26 DEBUG_ASSERT(futex_table_.is_empty()); 27} 28 29zx_status_t FutexContext::FutexWait(user_in_ptr<const int> value_ptr, int current_value, zx_time_t deadline) { 30 LTRACE_ENTRY; 31 32 uintptr_t futex_key = reinterpret_cast<uintptr_t>(value_ptr.get()); 33 if (futex_key % sizeof(int)) 34 return ZX_ERR_INVALID_ARGS; 35 36 // FutexWait() checks that the address value_ptr still contains 37 // current_value, and if so it sleeps awaiting a FutexWake() on value_ptr. 38 // Those two steps must together be atomic with respect to FutexWake(). 39 // If a FutexWake() operation could occur between them, a userland mutex 40 // operation built on top of futexes would have a race condition that 41 // could miss wakeups. 42 Guard<fbl::Mutex> guard{&lock_}; 43 44 int value; 45 zx_status_t result = value_ptr.copy_from_user(&value); 46 if (result != ZX_OK) { 47 return result; 48 } 49 if (value != current_value) { 50 return ZX_ERR_BAD_STATE; 51 } 52 53 FutexNode node; 54 node.set_hash_key(futex_key); 55 node.SetAsSingletonList(); 56 57 QueueNodesLocked(&node); 58 59 // Block current thread. This releases lock_ and does not reacquire it. 60 result = node.BlockThread(guard.take(), deadline); 61 if (result == ZX_OK) { 62 DEBUG_ASSERT(!node.IsInQueue()); 63 // All the work necessary for removing us from the hash table was done by FutexWake() 64 return ZX_OK; 65 } 66 67 // The following happens if we hit the deadline (ZX_ERR_TIMED_OUT) or if 68 // the thread was killed (ZX_ERR_INTERNAL_INTR_KILLED) or suspended 69 // (ZX_ERR_INTERNAL_INTR_RETRY). 70 // 71 // We need to ensure that the thread's node is removed from the wait 72 // queue, because FutexWake() probably didn't do that. 73 Guard<fbl::Mutex> guard2{&lock_}; 74 if (UnqueueNodeLocked(&node)) { 75 return result; 76 } 77 // The current thread was not found on the wait queue. This means 78 // that, although we hit the deadline (or were suspended/killed), we 79 // were *also* woken by FutexWake() (which removed the thread from the 80 // wait queue) -- the two raced together. 81 // 82 // In this case, we want to return a success status. This preserves 83 // the property that if FutexWake() is called with wake_count=1 and 84 // there are waiting threads, then at least one FutexWait() call 85 // returns success. 86 // 87 // If that property is broken, it can lead to missed wakeups in 88 // concurrency constructs that are built on top of futexes. For 89 // example, suppose a FutexWake() call from pthread_mutex_unlock() 90 // races with a FutexWait() deadline from pthread_mutex_timedlock(). A 91 // typical implementation of pthread_mutex_timedlock() will return 92 // immediately without trying again to claim the mutex if this 93 // FutexWait() call returns a timeout status. If that happens, and if 94 // another thread is waiting on the mutex, then that thread won't get 95 // woken -- the wakeup from the FutexWake() call would have got lost. 96 return ZX_OK; 97} 98 99zx_status_t FutexContext::FutexWake(user_in_ptr<const int> value_ptr, 100 uint32_t count) { 101 LTRACE_ENTRY; 102 103 if (count == 0) return ZX_OK; 104 105 uintptr_t futex_key = reinterpret_cast<uintptr_t>(value_ptr.get()); 106 if (futex_key % sizeof(int)) 107 return ZX_ERR_INVALID_ARGS; 108 109 AutoReschedDisable resched_disable; // Must come before the Guard. 110 resched_disable.Disable(); 111 Guard<fbl::Mutex> guard{&lock_}; 112 113 FutexNode* node = futex_table_.erase(futex_key); 114 if (!node) { 115 // nothing blocked on this futex if we can't find it 116 return ZX_OK; 117 } 118 DEBUG_ASSERT(node->GetKey() == futex_key); 119 120 FutexNode* remaining_waiters = 121 FutexNode::WakeThreads(node, count, futex_key); 122 123 if (remaining_waiters) { 124 DEBUG_ASSERT(remaining_waiters->GetKey() == futex_key); 125 futex_table_.insert(remaining_waiters); 126 } 127 128 return ZX_OK; 129} 130 131zx_status_t FutexContext::FutexRequeue(user_in_ptr<const int> wake_ptr, uint32_t wake_count, int current_value, 132 user_in_ptr<const int> requeue_ptr, uint32_t requeue_count) { 133 LTRACE_ENTRY; 134 135 if ((requeue_ptr.get() == nullptr) && requeue_count) 136 return ZX_ERR_INVALID_ARGS; 137 138 AutoReschedDisable resched_disable; // Must come before the Guard. 139 Guard<fbl::Mutex> guard{&lock_}; 140 141 int value; 142 zx_status_t result = wake_ptr.copy_from_user(&value); 143 if (result != ZX_OK) return result; 144 if (value != current_value) return ZX_ERR_BAD_STATE; 145 146 uintptr_t wake_key = reinterpret_cast<uintptr_t>(wake_ptr.get()); 147 uintptr_t requeue_key = reinterpret_cast<uintptr_t>(requeue_ptr.get()); 148 if (wake_key == requeue_key) return ZX_ERR_INVALID_ARGS; 149 if (wake_key % sizeof(int) || requeue_key % sizeof(int)) 150 return ZX_ERR_INVALID_ARGS; 151 152 // This must happen before RemoveFromHead() calls set_hash_key() on 153 // nodes below, because operations on futex_table_ look at the GetKey 154 // field of the list head nodes for wake_key and requeue_key. 155 FutexNode* node = futex_table_.erase(wake_key); 156 if (!node) { 157 // nothing blocked on this futex if we can't find it 158 return ZX_OK; 159 } 160 161 // This must come before WakeThreads() to be useful, but we want to 162 // avoid doing it before copy_from_user() in case that faults. 163 resched_disable.Disable(); 164 165 if (wake_count > 0) { 166 node = FutexNode::WakeThreads(node, wake_count, wake_key); 167 } 168 169 // node is now the head of wake_ptr futex after possibly removing some threads to wake 170 if (node != nullptr) { 171 if (requeue_count > 0) { 172 // head and tail of list of nodes to requeue 173 FutexNode* requeue_head = node; 174 node = FutexNode::RemoveFromHead(node, requeue_count, 175 wake_key, requeue_key); 176 177 // now requeue our nodes to requeue_ptr mutex 178 DEBUG_ASSERT(requeue_head->GetKey() == requeue_key); 179 QueueNodesLocked(requeue_head); 180 } 181 } 182 183 // add any remaining nodes back to wake_key futex 184 if (node != nullptr) { 185 DEBUG_ASSERT(node->GetKey() == wake_key); 186 futex_table_.insert(node); 187 } 188 189 return ZX_OK; 190} 191 192void FutexContext::QueueNodesLocked(FutexNode* head) { 193 DEBUG_ASSERT(lock_.lock().IsHeld()); 194 195 FutexNode::HashTable::iterator iter; 196 197 // Attempt to insert this FutexNode into the hash table. If the insert 198 // succeeds, then the current thread is first to block on this futex and we 199 // are finished. If the insert fails, then there is already a thread 200 // waiting on this futex. Add ourselves to that thread's list. 201 if (!futex_table_.insert_or_find(head, &iter)) 202 iter->AppendList(head); 203} 204 205// This attempts to unqueue a thread (which may or may not be waiting on a 206// futex), given its FutexNode. This returns whether the FutexNode was 207// found and removed from a futex wait queue. 208bool FutexContext::UnqueueNodeLocked(FutexNode* node) { 209 DEBUG_ASSERT(lock_.lock().IsHeld()); 210 211 if (!node->IsInQueue()) 212 return false; 213 214 // Note: When UnqueueNode() is called from FutexWait(), it might be 215 // tempting to reuse the futex key that was passed to FutexWait(). 216 // However, that could be out of date if the thread was requeued by 217 // FutexRequeue(), so we need to re-get the hash table key here. 218 uintptr_t futex_key = node->GetKey(); 219 220 FutexNode* old_head = futex_table_.erase(futex_key); 221 DEBUG_ASSERT(old_head); 222 FutexNode* new_head = FutexNode::RemoveNodeFromList(old_head, node); 223 if (new_head) 224 futex_table_.insert(new_head); 225 return true; 226} 227