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 41860 : static void ListAddNodeAtEnd(struct NaClListNode *new_node,
38 41860 : struct NaClListNode *head) {
39 41860 : head->prev->next = new_node;
40 41860 : new_node->prev = head->prev;
41 41860 : new_node->next = head;
42 41860 : head->prev = new_node;
43 41860 : }
44 :
45 41858 : static void ListRemoveNode(struct NaClListNode *node) {
46 41858 : node->next->prev = node->prev;
47 41858 : node->prev->next = node->next;
48 41858 : }
49 :
50 : /*
51 : * Given a pointer to a NaClAppThread's futex_wait_list_node, this
52 : * returns a pointer to the NaClAppThread.
53 : */
54 : static struct NaClAppThread *GetNaClAppThreadFromListNode(
55 43723 : struct NaClListNode *node) {
56 43723 : return (struct NaClAppThread *)
57 : ((uintptr_t) node -
58 : offsetof(struct NaClAppThread, futex_wait_list_node));
59 : }
60 :
61 47427 : int32_t NaClSysFutexWaitAbs(struct NaClAppThread *natp, uint32_t addr,
62 47427 : uint32_t value, uint32_t abstime_ptr) {
63 47427 : struct NaClApp *nap = natp->nap;
64 47427 : struct nacl_abi_timespec abstime;
65 47427 : uint32_t read_value;
66 47427 : int32_t result;
67 47427 : NaClSyncStatus sync_status;
68 :
69 47427 : if (abstime_ptr != 0) {
70 9 : if (!NaClCopyInFromUser(nap, &abstime, abstime_ptr, sizeof(abstime))) {
71 1 : return -NACL_ABI_EFAULT;
72 : }
73 8 : }
74 :
75 47426 : 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 47426 : if (!NaClCopyInFromUser(nap, &read_value, addr, sizeof(uint32_t))) {
83 1 : result = -NACL_ABI_EFAULT;
84 1 : goto cleanup;
85 : }
86 47425 : if (read_value != value) {
87 5565 : result = -NACL_ABI_EWOULDBLOCK;
88 5565 : goto cleanup;
89 : }
90 :
91 : /* Add the current thread onto the futex wait list. */
92 41860 : natp->futex_wait_addr = addr;
93 41860 : ListAddNodeAtEnd(&natp->futex_wait_list_node, &nap->futex_wait_list_head);
94 :
95 41860 : if (abstime_ptr == 0) {
96 41852 : sync_status = NaClCondVarWait(
97 : &natp->futex_condvar, &nap->futex_wait_list_mu);
98 41852 : } else {
99 8 : sync_status = NaClCondVarTimedWaitAbsolute(
100 : &natp->futex_condvar, &nap->futex_wait_list_mu, &abstime);
101 : }
102 41858 : 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 41858 : if (natp->futex_wait_list_node.next != NULL) {
109 8 : ListRemoveNode(&natp->futex_wait_list_node);
110 8 : }
111 : /* Clear these fields to prevent their accidental use. */
112 41858 : natp->futex_wait_list_node.next = NULL;
113 41858 : natp->futex_wait_list_node.prev = NULL;
114 41858 : natp->futex_wait_addr = 0;
115 :
116 : cleanup:
117 47424 : NaClXMutexUnlock(&nap->futex_wait_list_mu);
118 47424 : return result;
119 47425 : }
120 :
121 954728 : int32_t NaClSysFutexWake(struct NaClAppThread *natp, uint32_t addr,
122 954728 : uint32_t nwake) {
123 954728 : struct NaClApp *nap = natp->nap;
124 954728 : struct NaClListNode *entry;
125 954728 : uint32_t woken_count = 0;
126 :
127 954728 : NaClXMutexLock(&nap->futex_wait_list_mu);
128 :
129 : /* We process waiting threads in FIFO order. */
130 954728 : entry = nap->futex_wait_list_head.next;
131 2912779 : while (nwake > 0 && entry != &nap->futex_wait_list_head) {
132 43723 : struct NaClListNode *next = entry->next;
133 43723 : struct NaClAppThread *waiting_thread = GetNaClAppThreadFromListNode(entry);
134 :
135 43723 : if (waiting_thread->futex_wait_addr == addr) {
136 41850 : 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 41850 : entry->next = NULL;
142 :
143 : /* Also clear these fields to prevent their accidental use. */
144 41850 : entry->prev = NULL;
145 41850 : waiting_thread->futex_wait_addr = 0;
146 :
147 41850 : NaClXCondVarSignal(&waiting_thread->futex_condvar);
148 41850 : woken_count++;
149 41850 : nwake--;
150 41850 : }
151 43723 : entry = next;
152 43723 : }
153 :
154 954728 : NaClXMutexUnlock(&nap->futex_wait_list_mu);
155 :
156 954728 : return woken_count;
157 : }
|
