1#include <threads.h> 2 3#include <errno.h> 4 5#include <runtime/mutex.h> 6 7#include "futex_impl.h" 8#include "libc.h" 9#include "threads_impl.h" 10 11struct waiter { 12 struct waiter *prev, *next; 13 atomic_int state; 14 atomic_int barrier; 15 atomic_int* notify; 16}; 17 18enum { 19 WAITING, 20 LEAVING, 21}; 22 23int cnd_timedwait(cnd_t* restrict c, mtx_t* restrict mutex, 24 const struct timespec* restrict ts) { 25 zxr_mutex_t* m = (zxr_mutex_t*)mutex; 26 int e, clock = c->_c_clock, oldstate; 27 28 if (ts && ts->tv_nsec >= 1000000000UL) 29 return thrd_error; 30 31 lock(&c->_c_lock); 32 33 int seq = 2; 34 struct waiter node = { 35 .barrier = ATOMIC_VAR_INIT(seq), 36 .state = ATOMIC_VAR_INIT(WAITING), 37 }; 38 atomic_int* fut = &node.barrier; 39 /* Add our waiter node onto the condvar's list. We add the node to the 40 * head of the list, but this is logically the end of the queue. */ 41 node.next = c->_c_head; 42 c->_c_head = &node; 43 if (!c->_c_tail) 44 c->_c_tail = &node; 45 else 46 node.next->prev = &node; 47 48 unlock(&c->_c_lock); 49 50 zxr_mutex_unlock(m); 51 52 /* Wait to be signaled. There are multiple ways this loop could exit: 53 * 1) After being woken by __private_cond_signal(). 54 * 2) After being woken by zxr_mutex_unlock(), after we were 55 * requeued from the condvar's futex to the mutex's futex (by 56 * cnd_timedwait() in another thread). 57 * 3) After a timeout. 58 * 4) On Linux, interrupted by an asynchronous signal. This does 59 * not apply on Zircon. */ 60 do 61 e = __timedwait(fut, seq, clock, ts); 62 while (*fut == seq && !e); 63 64 oldstate = a_cas_shim(&node.state, WAITING, LEAVING); 65 66 if (oldstate == WAITING) { 67 /* The wait timed out. So far, this thread was not signaled by 68 * cnd_signal()/cnd_broadcast() -- this thread was able to move 69 * state.node out of the WAITING state before any 70 * __private_cond_signal() call could do that. 71 * 72 * This thread must therefore remove the waiter node from the 73 * list itself. */ 74 75 /* Access to cv object is valid because this waiter was not 76 * yet signaled and a new signal/broadcast cannot return 77 * after seeing a LEAVING waiter without getting notified 78 * via the futex notify below. */ 79 80 lock(&c->_c_lock); 81 82 /* Remove our waiter node from the list. */ 83 if (c->_c_head == &node) 84 c->_c_head = node.next; 85 else if (node.prev) 86 node.prev->next = node.next; 87 if (c->_c_tail == &node) 88 c->_c_tail = node.prev; 89 else if (node.next) 90 node.next->prev = node.prev; 91 92 unlock(&c->_c_lock); 93 94 /* It is possible that __private_cond_signal() saw our waiter node 95 * after we set node.state to LEAVING but before we removed the 96 * node from the list. If so, it will have set node.notify and 97 * will be waiting on it, and we need to wake it up. 98 * 99 * This is rather complex. An alternative would be to eliminate 100 * the node.state field and always claim _c_lock if we could have 101 * got a timeout. However, that presumably has higher overhead 102 * (since it contends _c_lock and involves more atomic ops). */ 103 if (node.notify) { 104 if (atomic_fetch_add(node.notify, -1) == 1) 105 __wake(node.notify, 1); 106 } 107 } else { 108 /* Lock barrier first to control wake order. */ 109 lock(&node.barrier); 110 } 111 112 /* We must leave the mutex in the "locked with waiters" state here. 113 * There are two reasons for that: 114 * 1) If we do the unlock_requeue() below, a condvar waiter will be 115 * requeued to the mutex's futex. We need to ensure that it will 116 * be signaled by zxr_mutex_unlock() in future. 117 * 2) If the current thread was woken via an unlock_requeue() + 118 * zxr_mutex_unlock(), there *might* be another thread waiting for 119 * the mutex after us in the queue. We need to ensure that it 120 * will be signaled by zxr_mutex_unlock() in future. */ 121 zxr_mutex_lock_with_waiter(m); 122 123 /* By this point, our part of the waiter list cannot change further. 124 * It has been unlinked from the condvar by __private_cond_signal(). 125 * It consists only of waiters that were woken explicitly by 126 * cnd_signal()/cnd_broadcast(). Any timed-out waiters would have 127 * removed themselves from the list before __private_cond_signal() 128 * signaled the first node.barrier in our list. 129 * 130 * It is therefore safe now to read node.next and node.prev without 131 * holding _c_lock. */ 132 133 if (oldstate != WAITING && node.prev) { 134 /* Unlock the barrier that's holding back the next waiter, and 135 * requeue it to the mutex so that it will be woken when the 136 * mutex is unlocked. */ 137 unlock_requeue(&node.prev->barrier, &m->futex); 138 } 139 140 switch (e) { 141 case 0: 142 return 0; 143 case EINVAL: 144 return thrd_error; 145 case ETIMEDOUT: 146 return thrd_timedout; 147 default: 148 // No other error values are permissible from __timedwait_cp(); 149 __builtin_trap(); 150 } 151} 152