1 : /*
2 : * Copyright (c) 2013 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can be
4 : * found in the LICENSE file.
5 : */
6 :
7 : #include "native_client/src/trusted/service_runtime/sys_futex.h"
8 :
9 : #include "native_client/src/trusted/service_runtime/include/sys/errno.h"
10 : #include "native_client/src/trusted/service_runtime/nacl_app_thread.h"
11 : #include "native_client/src/trusted/service_runtime/nacl_copy.h"
12 : #include "native_client/src/trusted/service_runtime/sel_ldr.h"
13 :
14 : /*
15 : * This is a simple futex implementation that is based on the
16 : * untrusted-code futex implementation from the NaCl IRT
17 : * (irt_futex.c), which in turn was based on futex_emulation.c from
18 : * nacl-glibc.
19 : *
20 : * There are some ways the performance of this implementation could be
21 : * improved:
22 : *
23 : * * On Linux, use the kernel's futex() syscall with
24 : * FUTEX_PRIVATE_FLAG.
25 : *
26 : * * The current futex_wake() implementation does a linear search
27 : * while holding a global lock, which could perform poorly if there
28 : * are large numbers of waiting threads.
29 : *
30 : * We could use a hash table rather than a single linked list for
31 : * looking up wait addresses. Furthermore, to reduce lock
32 : * contention, we could use one lock per hash bucket rather than a
33 : * single lock.
34 : */
35 :
36 :
37 51046 : static void ListAddNodeAtEnd(struct NaClListNode *new_node,
38 : struct NaClListNode *head) {
39 51046 : head->prev->next = new_node;
40 51046 : new_node->prev = head->prev;
41 51046 : new_node->next = head;
42 51046 : head->prev = new_node;
43 51046 : }
44 :
45 51042 : static void ListRemoveNode(struct NaClListNode *node) {
46 51042 : node->next->prev = node->prev;
47 51042 : node->prev->next = node->next;
48 51042 : }
49 :
50 : /*
51 : * Given a pointer to a NaClAppThread's futex_wait_list_node, this
52 : * returns a pointer to the NaClAppThread.
53 : */
54 51526 : static struct NaClAppThread *GetNaClAppThreadFromListNode(
55 : struct NaClListNode *node) {
56 51526 : return (struct NaClAppThread *)
57 51526 : ((uintptr_t) node -
58 : offsetof(struct NaClAppThread, futex_wait_list_node));
59 : }
60 :
61 51101 : int32_t NaClSysFutexWaitAbs(struct NaClAppThread *natp, uint32_t addr,
62 : uint32_t value, uint32_t abstime_ptr) {
63 51101 : struct NaClApp *nap = natp->nap;
64 : struct nacl_abi_timespec abstime;
65 : uint32_t read_value;
66 : int32_t result;
67 : NaClSyncStatus sync_status;
68 :
69 51101 : if (abstime_ptr != 0) {
70 9 : if (!NaClCopyInFromUser(nap, &abstime, abstime_ptr, sizeof(abstime))) {
71 1 : return -NACL_ABI_EFAULT;
72 : }
73 : }
74 :
75 51100 : NaClXMutexLock(&nap->futex_wait_list_mu);
76 :
77 : /*
78 : * Note about lock ordering: NaClCopyInFromUser() can claim the
79 : * mutex nap->mu. nap->mu may be claimed after
80 : * nap->futex_wait_list_mu but never before it.
81 : */
82 51100 : if (!NaClCopyInFromUser(nap, &read_value, addr, sizeof(uint32_t))) {
83 1 : result = -NACL_ABI_EFAULT;
84 1 : goto cleanup;
85 : }
86 51099 : if (read_value != value) {
87 53 : result = -NACL_ABI_EWOULDBLOCK;
88 53 : goto cleanup;
89 : }
90 :
91 : /* Add the current thread onto the futex wait list. */
92 51046 : natp->futex_wait_addr = addr;
93 51046 : ListAddNodeAtEnd(&natp->futex_wait_list_node, &nap->futex_wait_list_head);
94 :
95 51046 : if (abstime_ptr == 0) {
96 51038 : sync_status = NaClCondVarWait(
97 : &natp->futex_condvar, &nap->futex_wait_list_mu);
98 : } else {
99 8 : sync_status = NaClCondVarTimedWaitAbsolute(
100 : &natp->futex_condvar, &nap->futex_wait_list_mu, &abstime);
101 : }
102 51042 : result = -NaClXlateNaClSyncStatus(sync_status);
103 :
104 : /*
105 : * In case a timeout or spurious wakeup occurs, remove this thread
106 : * from the wait queue.
107 : */
108 51042 : if (natp->futex_wait_list_node.next != NULL) {
109 8 : ListRemoveNode(&natp->futex_wait_list_node);
110 : }
111 : /* Clear these fields to prevent their accidental use. */
112 51042 : natp->futex_wait_list_node.next = NULL;
113 51042 : natp->futex_wait_list_node.prev = NULL;
114 51042 : natp->futex_wait_addr = 0;
115 :
116 : cleanup:
117 51096 : NaClXMutexUnlock(&nap->futex_wait_list_mu);
118 51096 : return result;
119 : }
120 :
121 807903 : int32_t NaClSysFutexWake(struct NaClAppThread *natp, uint32_t addr,
122 : uint32_t nwake) {
123 807903 : struct NaClApp *nap = natp->nap;
124 : struct NaClListNode *entry;
125 807903 : uint32_t woken_count = 0;
126 :
127 807903 : NaClXMutexLock(&nap->futex_wait_list_mu);
128 :
129 : /* We process waiting threads in FIFO order. */
130 807903 : entry = nap->futex_wait_list_head.next;
131 1667332 : while (nwake > 0 && entry != &nap->futex_wait_list_head) {
132 51526 : struct NaClListNode *next = entry->next;
133 51526 : struct NaClAppThread *waiting_thread = GetNaClAppThreadFromListNode(entry);
134 :
135 51526 : if (waiting_thread->futex_wait_addr == addr) {
136 51034 : ListRemoveNode(entry);
137 : /*
138 : * Mark the thread as having been removed from the wait queue:
139 : * tell it not to try to remove itself from the queue.
140 : */
141 51034 : entry->next = NULL;
142 :
143 : /* Also clear these fields to prevent their accidental use. */
144 51034 : entry->prev = NULL;
145 51034 : waiting_thread->futex_wait_addr = 0;
146 :
147 51034 : NaClXCondVarSignal(&waiting_thread->futex_condvar);
148 51034 : woken_count++;
149 51034 : nwake--;
150 : }
151 51526 : entry = next;
152 : }
153 :
154 807903 : NaClXMutexUnlock(&nap->futex_wait_list_mu);
155 :
156 807903 : return woken_count;
157 : }
|
