source: mainline/uspace/lib/c/generic/fibril_synch.c@ 36a6e11

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 36a6e11 was c81b6f2, checked in by Jakub Jermar <jakub@…>, 15 years ago

Add fibril_rwlock_is_locked().
  • Property mode set to 100644
File size: 10.2 KB
Line 
1/*
2 * Copyright (c) 2009 Jakub Jermar
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup libc
30 * @{
31 */
32/** @file
33 */
34
35#include <fibril_synch.h>
36#include <fibril.h>
37#include <async.h>
38#include <async_priv.h>
39#include <adt/list.h>
40#include <futex.h>
41#include <sys/time.h>
42#include <errno.h>
43#include <assert.h>
44#include <stacktrace.h>
45#include <stdlib.h>
46
47static void optimize_execution_power(void)
48{
49 /*
50 * When waking up a worker fibril previously blocked in fibril
51 * synchronization, chances are that there is an idle manager fibril
52 * waiting for IPC, that could start executing the awakened worker
53 * fibril right away. We try to detect this and bring the manager
54 * fibril back to fruitful work.
55 */
56 if (atomic_get(&threads_in_ipc_wait) > 0)
57 ipc_poke();
58}
59
60static void print_deadlock(fibril_owner_info_t *oi)
61{
62 fibril_t *f = (fibril_t *) fibril_get_id();
63
64 printf("Deadlock detected.\n");
65 stacktrace_print();
66
67 printf("Fibril %p waits for primitive %p.\n", f, oi);
68
69 while (oi && oi->owned_by) {
70 printf("Primitive %p is owned by fibril %p.\n",
71 oi, oi->owned_by);
72 if (oi->owned_by == f)
73 break;
74 stacktrace_print_fp_pc(context_get_fp(&oi->owned_by->ctx),
75 oi->owned_by->ctx.pc);
76 printf("Fibril %p waits for primitive %p.\n",
77 oi->owned_by, oi->owned_by->waits_for);
78 oi = oi->owned_by->waits_for;
79 }
80}
81
82
83static void check_for_deadlock(fibril_owner_info_t *oi)
84{
85 while (oi && oi->owned_by) {
86 if (oi->owned_by == (fibril_t *) fibril_get_id()) {
87 print_deadlock(oi);
88 abort();
89 }
90 oi = oi->owned_by->waits_for;
91 }
92}
93
94
95void fibril_mutex_initialize(fibril_mutex_t *fm)
96{
97 fm->oi.owned_by = NULL;
98 fm->counter = 1;
99 list_initialize(&fm->waiters);
100}
101
102void fibril_mutex_lock(fibril_mutex_t *fm)
103{
104 fibril_t *f = (fibril_t *) fibril_get_id();
105
106 futex_down(&async_futex);
107 if (fm->counter-- <= 0) {
108 awaiter_t wdata;
109
110 wdata.fid = fibril_get_id();
111 wdata.active = false;
112 wdata.wu_event.inlist = true;
113 link_initialize(&wdata.wu_event.link);
114 list_append(&wdata.wu_event.link, &fm->waiters);
115 check_for_deadlock(&fm->oi);
116 f->waits_for = &fm->oi;
117 fibril_switch(FIBRIL_TO_MANAGER);
118 } else {
119 fm->oi.owned_by = f;
120 futex_up(&async_futex);
121 }
122}
123
124bool fibril_mutex_trylock(fibril_mutex_t *fm)
125{
126 bool locked = false;
127
128 futex_down(&async_futex);
129 if (fm->counter > 0) {
130 fm->counter--;
131 fm->oi.owned_by = (fibril_t *) fibril_get_id();
132 locked = true;
133 }
134 futex_up(&async_futex);
135
136 return locked;
137}
138
139static void _fibril_mutex_unlock_unsafe(fibril_mutex_t *fm)
140{
141 if (fm->counter++ < 0) {
142 link_t *tmp;
143 awaiter_t *wdp;
144 fibril_t *f;
145
146 assert(!list_empty(&fm->waiters));
147 tmp = fm->waiters.next;
148 wdp = list_get_instance(tmp, awaiter_t, wu_event.link);
149 wdp->active = true;
150 wdp->wu_event.inlist = false;
151
152 f = (fibril_t *) wdp->fid;
153 fm->oi.owned_by = f;
154 f->waits_for = NULL;
155
156 list_remove(&wdp->wu_event.link);
157 fibril_add_ready(wdp->fid);
158 optimize_execution_power();
159 } else {
160 fm->oi.owned_by = NULL;
161 }
162}
163
164void fibril_mutex_unlock(fibril_mutex_t *fm)
165{
166 assert(fibril_mutex_is_locked(fm));
167 futex_down(&async_futex);
168 _fibril_mutex_unlock_unsafe(fm);
169 futex_up(&async_futex);
170}
171
172bool fibril_mutex_is_locked(fibril_mutex_t *fm)
173{
174 bool locked = false;
175
176 futex_down(&async_futex);
177 if (fm->counter <= 0)
178 locked = true;
179 futex_up(&async_futex);
180
181 return locked;
182}
183
184void fibril_rwlock_initialize(fibril_rwlock_t *frw)
185{
186 frw->oi.owned_by = NULL;
187 frw->writers = 0;
188 frw->readers = 0;
189 list_initialize(&frw->waiters);
190}
191
192void fibril_rwlock_read_lock(fibril_rwlock_t *frw)
193{
194 fibril_t *f = (fibril_t *) fibril_get_id();
195
196 futex_down(&async_futex);
197 if (frw->writers) {
198 awaiter_t wdata;
199
200 wdata.fid = (fid_t) f;
201 wdata.active = false;
202 wdata.wu_event.inlist = true;
203 link_initialize(&wdata.wu_event.link);
204 f->flags &= ~FIBRIL_WRITER;
205 list_append(&wdata.wu_event.link, &frw->waiters);
206 check_for_deadlock(&frw->oi);
207 f->waits_for = &frw->oi;
208 fibril_switch(FIBRIL_TO_MANAGER);
209 } else {
210 /* Consider the first reader the owner. */
211 if (frw->readers++ == 0)
212 frw->oi.owned_by = f;
213 futex_up(&async_futex);
214 }
215}
216
217void fibril_rwlock_write_lock(fibril_rwlock_t *frw)
218{
219 fibril_t *f = (fibril_t *) fibril_get_id();
220
221 futex_down(&async_futex);
222 if (frw->writers || frw->readers) {
223 awaiter_t wdata;
224
225 wdata.fid = (fid_t) f;
226 wdata.active = false;
227 wdata.wu_event.inlist = true;
228 link_initialize(&wdata.wu_event.link);
229 f->flags |= FIBRIL_WRITER;
230 list_append(&wdata.wu_event.link, &frw->waiters);
231 check_for_deadlock(&frw->oi);
232 f->waits_for = &frw->oi;
233 fibril_switch(FIBRIL_TO_MANAGER);
234 } else {
235 frw->oi.owned_by = f;
236 frw->writers++;
237 futex_up(&async_futex);
238 }
239}
240
241static void _fibril_rwlock_common_unlock(fibril_rwlock_t *frw)
242{
243 futex_down(&async_futex);
244 if (frw->readers) {
245 if (--frw->readers) {
246 if (frw->oi.owned_by == (fibril_t *) fibril_get_id()) {
247 /*
248 * If this reader firbril was considered the
249 * owner of this rwlock, clear the ownership
250 * information even if there are still more
251 * readers.
252 *
253 * This is the limitation of the detection
254 * mechanism rooted in the fact that tracking
255 * all readers would require dynamically
256 * allocated memory for keeping linkage info.
257 */
258 frw->oi.owned_by = NULL;
259 }
260 goto out;
261 }
262 } else {
263 frw->writers--;
264 }
265
266 assert(!frw->readers && !frw->writers);
267
268 frw->oi.owned_by = NULL;
269
270 while (!list_empty(&frw->waiters)) {
271 link_t *tmp = frw->waiters.next;
272 awaiter_t *wdp;
273 fibril_t *f;
274
275 wdp = list_get_instance(tmp, awaiter_t, wu_event.link);
276 f = (fibril_t *) wdp->fid;
277
278 f->waits_for = NULL;
279
280 if (f->flags & FIBRIL_WRITER) {
281 if (frw->readers)
282 break;
283 wdp->active = true;
284 wdp->wu_event.inlist = false;
285 list_remove(&wdp->wu_event.link);
286 fibril_add_ready(wdp->fid);
287 frw->writers++;
288 frw->oi.owned_by = f;
289 optimize_execution_power();
290 break;
291 } else {
292 wdp->active = true;
293 wdp->wu_event.inlist = false;
294 list_remove(&wdp->wu_event.link);
295 fibril_add_ready(wdp->fid);
296 if (frw->readers++ == 0) {
297 /* Consider the first reader the owner. */
298 frw->oi.owned_by = f;
299 }
300 optimize_execution_power();
301 }
302 }
303out:
304 futex_up(&async_futex);
305}
306
307void fibril_rwlock_read_unlock(fibril_rwlock_t *frw)
308{
309 assert(fibril_rwlock_is_read_locked(frw));
310 _fibril_rwlock_common_unlock(frw);
311}
312
313void fibril_rwlock_write_unlock(fibril_rwlock_t *frw)
314{
315 assert(fibril_rwlock_is_write_locked(frw));
316 _fibril_rwlock_common_unlock(frw);
317}
318
319bool fibril_rwlock_is_read_locked(fibril_rwlock_t *frw)
320{
321 bool locked = false;
322
323 futex_down(&async_futex);
324 if (frw->readers)
325 locked = true;
326 futex_up(&async_futex);
327
328 return locked;
329}
330
331bool fibril_rwlock_is_write_locked(fibril_rwlock_t *frw)
332{
333 bool locked = false;
334
335 futex_down(&async_futex);
336 if (frw->writers) {
337 assert(frw->writers == 1);
338 locked = true;
339 }
340 futex_up(&async_futex);
341
342 return locked;
343}
344
345bool fibril_rwlock_is_locked(fibril_rwlock_t *frw)
346{
347 return fibril_rwlock_is_read_locked(frw) ||
348 fibril_rwlock_is_write_locked(frw);
349}
350
351void fibril_condvar_initialize(fibril_condvar_t *fcv)
352{
353 list_initialize(&fcv->waiters);
354}
355
356int
357fibril_condvar_wait_timeout(fibril_condvar_t *fcv, fibril_mutex_t *fm,
358 suseconds_t timeout)
359{
360 awaiter_t wdata;
361
362 assert(fibril_mutex_is_locked(fm));
363
364 if (timeout < 0)
365 return ETIMEOUT;
366
367 wdata.fid = fibril_get_id();
368 wdata.active = false;
369
370 wdata.to_event.inlist = timeout > 0;
371 wdata.to_event.occurred = false;
372 link_initialize(&wdata.to_event.link);
373
374 wdata.wu_event.inlist = true;
375 link_initialize(&wdata.wu_event.link);
376
377 futex_down(&async_futex);
378 if (timeout) {
379 gettimeofday(&wdata.to_event.expires, NULL);
380 tv_add(&wdata.to_event.expires, timeout);
381 async_insert_timeout(&wdata);
382 }
383 list_append(&wdata.wu_event.link, &fcv->waiters);
384 _fibril_mutex_unlock_unsafe(fm);
385 fibril_switch(FIBRIL_TO_MANAGER);
386 fibril_mutex_lock(fm);
387
388 /* async_futex not held after fibril_switch() */
389 futex_down(&async_futex);
390 if (wdata.to_event.inlist)
391 list_remove(&wdata.to_event.link);
392 if (wdata.wu_event.inlist)
393 list_remove(&wdata.wu_event.link);
394 futex_up(&async_futex);
395
396 return wdata.to_event.occurred ? ETIMEOUT : EOK;
397}
398
399void fibril_condvar_wait(fibril_condvar_t *fcv, fibril_mutex_t *fm)
400{
401 int rc;
402
403 rc = fibril_condvar_wait_timeout(fcv, fm, 0);
404 assert(rc == EOK);
405}
406
407static void _fibril_condvar_wakeup_common(fibril_condvar_t *fcv, bool once)
408{
409 link_t *tmp;
410 awaiter_t *wdp;
411
412 futex_down(&async_futex);
413 while (!list_empty(&fcv->waiters)) {
414 tmp = fcv->waiters.next;
415 wdp = list_get_instance(tmp, awaiter_t, wu_event.link);
416 list_remove(&wdp->wu_event.link);
417 wdp->wu_event.inlist = false;
418 if (!wdp->active) {
419 wdp->active = true;
420 fibril_add_ready(wdp->fid);
421 optimize_execution_power();
422 if (once)
423 break;
424 }
425 }
426 futex_up(&async_futex);
427}
428
429void fibril_condvar_signal(fibril_condvar_t *fcv)
430{
431 _fibril_condvar_wakeup_common(fcv, true);
432}
433
434void fibril_condvar_broadcast(fibril_condvar_t *fcv)
435{
436 _fibril_condvar_wakeup_common(fcv, false);
437}
438
439/** @}
440 */
Note: See TracBrowser for help on using the repository browser.