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