source: mainline/uspace/lib/c/generic/fibril_synch.c@ e26a4633

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since e26a4633 was e26a4633, checked in by Martin Decky <martin@…>, 14 years ago

introduce private libc.h header containing items which should not be visible from outside
  • Property mode set to 100644
File size: 10.3 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 <adt/list.h>
39#include <futex.h>
40#include <sys/time.h>
41#include <errno.h>
42#include <assert.h>
43#include <stacktrace.h>
44#include <stdlib.h>
45#include "private/async.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 if (fibril_get_sercount() != 0)
107 core();
108
109 futex_down(&async_futex);
110 if (fm->counter-- <= 0) {
111 awaiter_t wdata;
112
113 wdata.fid = fibril_get_id();
114 wdata.active = false;
115 wdata.wu_event.inlist = true;
116 link_initialize(&wdata.wu_event.link);
117 list_append(&wdata.wu_event.link, &fm->waiters);
118 check_for_deadlock(&fm->oi);
119 f->waits_for = &fm->oi;
120 fibril_switch(FIBRIL_TO_MANAGER);
121 } else {
122 fm->oi.owned_by = f;
123 futex_up(&async_futex);
124 }
125}
126
127bool fibril_mutex_trylock(fibril_mutex_t *fm)
128{
129 bool locked = false;
130
131 futex_down(&async_futex);
132 if (fm->counter > 0) {
133 fm->counter--;
134 fm->oi.owned_by = (fibril_t *) fibril_get_id();
135 locked = true;
136 }
137 futex_up(&async_futex);
138
139 return locked;
140}
141
142static void _fibril_mutex_unlock_unsafe(fibril_mutex_t *fm)
143{
144 if (fm->counter++ < 0) {
145 link_t *tmp;
146 awaiter_t *wdp;
147 fibril_t *f;
148
149 assert(!list_empty(&fm->waiters));
150 tmp = fm->waiters.next;
151 wdp = list_get_instance(tmp, awaiter_t, wu_event.link);
152 wdp->active = true;
153 wdp->wu_event.inlist = false;
154
155 f = (fibril_t *) wdp->fid;
156 fm->oi.owned_by = f;
157 f->waits_for = NULL;
158
159 list_remove(&wdp->wu_event.link);
160 fibril_add_ready(wdp->fid);
161 optimize_execution_power();
162 } else {
163 fm->oi.owned_by = NULL;
164 }
165}
166
167void fibril_mutex_unlock(fibril_mutex_t *fm)
168{
169 assert(fibril_mutex_is_locked(fm));
170 futex_down(&async_futex);
171 _fibril_mutex_unlock_unsafe(fm);
172 futex_up(&async_futex);
173}
174
175bool fibril_mutex_is_locked(fibril_mutex_t *fm)
176{
177 bool locked = false;
178
179 futex_down(&async_futex);
180 if (fm->counter <= 0)
181 locked = true;
182 futex_up(&async_futex);
183
184 return locked;
185}
186
187void fibril_rwlock_initialize(fibril_rwlock_t *frw)
188{
189 frw->oi.owned_by = NULL;
190 frw->writers = 0;
191 frw->readers = 0;
192 list_initialize(&frw->waiters);
193}
194
195void fibril_rwlock_read_lock(fibril_rwlock_t *frw)
196{
197 fibril_t *f = (fibril_t *) fibril_get_id();
198
199 if (fibril_get_sercount() != 0)
200 core();
201
202 futex_down(&async_futex);
203 if (frw->writers) {
204 awaiter_t wdata;
205
206 wdata.fid = (fid_t) f;
207 wdata.active = false;
208 wdata.wu_event.inlist = true;
209 link_initialize(&wdata.wu_event.link);
210 f->flags &= ~FIBRIL_WRITER;
211 list_append(&wdata.wu_event.link, &frw->waiters);
212 check_for_deadlock(&frw->oi);
213 f->waits_for = &frw->oi;
214 fibril_switch(FIBRIL_TO_MANAGER);
215 } else {
216 /* Consider the first reader the owner. */
217 if (frw->readers++ == 0)
218 frw->oi.owned_by = f;
219 futex_up(&async_futex);
220 }
221}
222
223void fibril_rwlock_write_lock(fibril_rwlock_t *frw)
224{
225 fibril_t *f = (fibril_t *) fibril_get_id();
226
227 if (fibril_get_sercount() != 0)
228 core();
229
230 futex_down(&async_futex);
231 if (frw->writers || frw->readers) {
232 awaiter_t wdata;
233
234 wdata.fid = (fid_t) f;
235 wdata.active = false;
236 wdata.wu_event.inlist = true;
237 link_initialize(&wdata.wu_event.link);
238 f->flags |= FIBRIL_WRITER;
239 list_append(&wdata.wu_event.link, &frw->waiters);
240 check_for_deadlock(&frw->oi);
241 f->waits_for = &frw->oi;
242 fibril_switch(FIBRIL_TO_MANAGER);
243 } else {
244 frw->oi.owned_by = f;
245 frw->writers++;
246 futex_up(&async_futex);
247 }
248}
249
250static void _fibril_rwlock_common_unlock(fibril_rwlock_t *frw)
251{
252 futex_down(&async_futex);
253 if (frw->readers) {
254 if (--frw->readers) {
255 if (frw->oi.owned_by == (fibril_t *) fibril_get_id()) {
256 /*
257 * If this reader firbril was considered the
258 * owner of this rwlock, clear the ownership
259 * information even if there are still more
260 * readers.
261 *
262 * This is the limitation of the detection
263 * mechanism rooted in the fact that tracking
264 * all readers would require dynamically
265 * allocated memory for keeping linkage info.
266 */
267 frw->oi.owned_by = NULL;
268 }
269 goto out;
270 }
271 } else {
272 frw->writers--;
273 }
274
275 assert(!frw->readers && !frw->writers);
276
277 frw->oi.owned_by = NULL;
278
279 while (!list_empty(&frw->waiters)) {
280 link_t *tmp = frw->waiters.next;
281 awaiter_t *wdp;
282 fibril_t *f;
283
284 wdp = list_get_instance(tmp, awaiter_t, wu_event.link);
285 f = (fibril_t *) wdp->fid;
286
287 f->waits_for = NULL;
288
289 if (f->flags & FIBRIL_WRITER) {
290 if (frw->readers)
291 break;
292 wdp->active = true;
293 wdp->wu_event.inlist = false;
294 list_remove(&wdp->wu_event.link);
295 fibril_add_ready(wdp->fid);
296 frw->writers++;
297 frw->oi.owned_by = f;
298 optimize_execution_power();
299 break;
300 } else {
301 wdp->active = true;
302 wdp->wu_event.inlist = false;
303 list_remove(&wdp->wu_event.link);
304 fibril_add_ready(wdp->fid);
305 if (frw->readers++ == 0) {
306 /* Consider the first reader the owner. */
307 frw->oi.owned_by = f;
308 }
309 optimize_execution_power();
310 }
311 }
312out:
313 futex_up(&async_futex);
314}
315
316void fibril_rwlock_read_unlock(fibril_rwlock_t *frw)
317{
318 assert(fibril_rwlock_is_read_locked(frw));
319 _fibril_rwlock_common_unlock(frw);
320}
321
322void fibril_rwlock_write_unlock(fibril_rwlock_t *frw)
323{
324 assert(fibril_rwlock_is_write_locked(frw));
325 _fibril_rwlock_common_unlock(frw);
326}
327
328bool fibril_rwlock_is_read_locked(fibril_rwlock_t *frw)
329{
330 bool locked = false;
331
332 futex_down(&async_futex);
333 if (frw->readers)
334 locked = true;
335 futex_up(&async_futex);
336
337 return locked;
338}
339
340bool fibril_rwlock_is_write_locked(fibril_rwlock_t *frw)
341{
342 bool locked = false;
343
344 futex_down(&async_futex);
345 if (frw->writers) {
346 assert(frw->writers == 1);
347 locked = true;
348 }
349 futex_up(&async_futex);
350
351 return locked;
352}
353
354bool fibril_rwlock_is_locked(fibril_rwlock_t *frw)
355{
356 return fibril_rwlock_is_read_locked(frw) ||
357 fibril_rwlock_is_write_locked(frw);
358}
359
360void fibril_condvar_initialize(fibril_condvar_t *fcv)
361{
362 list_initialize(&fcv->waiters);
363}
364
365int
366fibril_condvar_wait_timeout(fibril_condvar_t *fcv, fibril_mutex_t *fm,
367 suseconds_t timeout)
368{
369 awaiter_t wdata;
370
371 assert(fibril_mutex_is_locked(fm));
372
373 if (timeout < 0)
374 return ETIMEOUT;
375
376 wdata.fid = fibril_get_id();
377 wdata.active = false;
378
379 wdata.to_event.inlist = timeout > 0;
380 wdata.to_event.occurred = false;
381 link_initialize(&wdata.to_event.link);
382
383 wdata.wu_event.inlist = true;
384 link_initialize(&wdata.wu_event.link);
385
386 futex_down(&async_futex);
387 if (timeout) {
388 gettimeofday(&wdata.to_event.expires, NULL);
389 tv_add(&wdata.to_event.expires, timeout);
390 async_insert_timeout(&wdata);
391 }
392 list_append(&wdata.wu_event.link, &fcv->waiters);
393 _fibril_mutex_unlock_unsafe(fm);
394 fibril_switch(FIBRIL_TO_MANAGER);
395 fibril_mutex_lock(fm);
396
397 /* async_futex not held after fibril_switch() */
398 futex_down(&async_futex);
399 if (wdata.to_event.inlist)
400 list_remove(&wdata.to_event.link);
401 if (wdata.wu_event.inlist)
402 list_remove(&wdata.wu_event.link);
403 futex_up(&async_futex);
404
405 return wdata.to_event.occurred ? ETIMEOUT : EOK;
406}
407
408void fibril_condvar_wait(fibril_condvar_t *fcv, fibril_mutex_t *fm)
409{
410 int rc;
411
412 rc = fibril_condvar_wait_timeout(fcv, fm, 0);
413 assert(rc == EOK);
414}
415
416static void _fibril_condvar_wakeup_common(fibril_condvar_t *fcv, bool once)
417{
418 link_t *tmp;
419 awaiter_t *wdp;
420
421 futex_down(&async_futex);
422 while (!list_empty(&fcv->waiters)) {
423 tmp = fcv->waiters.next;
424 wdp = list_get_instance(tmp, awaiter_t, wu_event.link);
425 list_remove(&wdp->wu_event.link);
426 wdp->wu_event.inlist = false;
427 if (!wdp->active) {
428 wdp->active = true;
429 fibril_add_ready(wdp->fid);
430 optimize_execution_power();
431 if (once)
432 break;
433 }
434 }
435 futex_up(&async_futex);
436}
437
438void fibril_condvar_signal(fibril_condvar_t *fcv)
439{
440 _fibril_condvar_wakeup_common(fcv, true);
441}
442
443void fibril_condvar_broadcast(fibril_condvar_t *fcv)
444{
445 _fibril_condvar_wakeup_common(fcv, false);
446}
447
448/** @}
449 */
Note: See TracBrowser for help on using the repository browser.