2 * Copyright (c) 2009 Jakub Jermar
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
35 #include <fibril_synch.h>
43 #include <stacktrace.h>
46 #include "private/async.h"
47 #include "private/fibril.h"
49 static void optimize_execution_power(void)
52 * When waking up a worker fibril previously blocked in fibril
53 * synchronization, chances are that there is an idle manager fibril
54 * waiting for IPC, that could start executing the awakened worker
55 * fibril right away. We try to detect this and bring the manager
56 * fibril back to fruitful work.
61 static void print_deadlock(fibril_owner_info_t
*oi
)
63 fibril_t
*f
= (fibril_t
*) fibril_get_id();
65 printf("Deadlock detected.\n");
68 printf("Fibril %p waits for primitive %p.\n", f
, oi
);
70 while (oi
&& oi
->owned_by
) {
71 printf("Primitive %p is owned by fibril %p.\n",
73 if (oi
->owned_by
== f
)
75 stacktrace_print_fp_pc(
76 context_get_fp(&oi
->owned_by
->ctx
),
77 context_get_pc(&oi
->owned_by
->ctx
));
78 printf("Fibril %p waits for primitive %p.\n",
79 oi
->owned_by
, oi
->owned_by
->waits_for
);
80 oi
= oi
->owned_by
->waits_for
;
85 static void check_for_deadlock(fibril_owner_info_t
*oi
)
87 while (oi
&& oi
->owned_by
) {
88 if (oi
->owned_by
== (fibril_t
*) fibril_get_id()) {
92 oi
= oi
->owned_by
->waits_for
;
97 void fibril_mutex_initialize(fibril_mutex_t
*fm
)
99 fm
->oi
.owned_by
= NULL
;
101 list_initialize(&fm
->waiters
);
104 void fibril_mutex_lock(fibril_mutex_t
*fm
)
106 fibril_t
*f
= (fibril_t
*) fibril_get_id();
108 futex_down(&async_futex
);
109 if (fm
->counter
-- <= 0) {
112 awaiter_initialize(&wdata
);
113 wdata
.fid
= fibril_get_id();
114 wdata
.wu_event
.inlist
= true;
115 list_append(&wdata
.wu_event
.link
, &fm
->waiters
);
116 check_for_deadlock(&fm
->oi
);
117 f
->waits_for
= &fm
->oi
;
118 fibril_switch(FIBRIL_TO_MANAGER
);
121 futex_up(&async_futex
);
125 bool fibril_mutex_trylock(fibril_mutex_t
*fm
)
129 futex_down(&async_futex
);
130 if (fm
->counter
> 0) {
132 fm
->oi
.owned_by
= (fibril_t
*) fibril_get_id();
135 futex_up(&async_futex
);
140 static void _fibril_mutex_unlock_unsafe(fibril_mutex_t
*fm
)
142 if (fm
->counter
++ < 0) {
147 tmp
= list_first(&fm
->waiters
);
149 wdp
= list_get_instance(tmp
, awaiter_t
, wu_event
.link
);
151 wdp
->wu_event
.inlist
= false;
153 f
= (fibril_t
*) wdp
->fid
;
157 list_remove(&wdp
->wu_event
.link
);
158 fibril_add_ready(wdp
->fid
);
159 optimize_execution_power();
161 fm
->oi
.owned_by
= NULL
;
165 void fibril_mutex_unlock(fibril_mutex_t
*fm
)
167 assert(fibril_mutex_is_locked(fm
));
168 futex_down(&async_futex
);
169 _fibril_mutex_unlock_unsafe(fm
);
170 futex_up(&async_futex
);
173 bool fibril_mutex_is_locked(fibril_mutex_t
*fm
)
177 futex_down(&async_futex
);
178 if (fm
->counter
<= 0)
180 futex_up(&async_futex
);
185 void fibril_rwlock_initialize(fibril_rwlock_t
*frw
)
187 frw
->oi
.owned_by
= NULL
;
190 list_initialize(&frw
->waiters
);
193 void fibril_rwlock_read_lock(fibril_rwlock_t
*frw
)
195 fibril_t
*f
= (fibril_t
*) fibril_get_id();
197 futex_down(&async_futex
);
201 awaiter_initialize(&wdata
);
202 wdata
.fid
= (fid_t
) f
;
203 wdata
.wu_event
.inlist
= true;
204 f
->is_writer
= false;
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
);
210 /* Consider the first reader the owner. */
211 if (frw
->readers
++ == 0)
212 frw
->oi
.owned_by
= f
;
213 futex_up(&async_futex
);
217 void fibril_rwlock_write_lock(fibril_rwlock_t
*frw
)
219 fibril_t
*f
= (fibril_t
*) fibril_get_id();
221 futex_down(&async_futex
);
222 if (frw
->writers
|| frw
->readers
) {
225 awaiter_initialize(&wdata
);
226 wdata
.fid
= (fid_t
) f
;
227 wdata
.wu_event
.inlist
= true;
229 list_append(&wdata
.wu_event
.link
, &frw
->waiters
);
230 check_for_deadlock(&frw
->oi
);
231 f
->waits_for
= &frw
->oi
;
232 fibril_switch(FIBRIL_TO_MANAGER
);
234 frw
->oi
.owned_by
= f
;
236 futex_up(&async_futex
);
240 static void _fibril_rwlock_common_unlock(fibril_rwlock_t
*frw
)
242 futex_down(&async_futex
);
244 if (--frw
->readers
) {
245 if (frw
->oi
.owned_by
== (fibril_t
*) fibril_get_id()) {
247 * If this reader firbril was considered the
248 * owner of this rwlock, clear the ownership
249 * information even if there are still more
252 * This is the limitation of the detection
253 * mechanism rooted in the fact that tracking
254 * all readers would require dynamically
255 * allocated memory for keeping linkage info.
257 frw
->oi
.owned_by
= NULL
;
265 assert(!frw
->readers
&& !frw
->writers
);
267 frw
->oi
.owned_by
= NULL
;
269 while (!list_empty(&frw
->waiters
)) {
270 link_t
*tmp
= list_first(&frw
->waiters
);
274 wdp
= list_get_instance(tmp
, awaiter_t
, wu_event
.link
);
275 f
= (fibril_t
*) wdp
->fid
;
283 wdp
->wu_event
.inlist
= false;
284 list_remove(&wdp
->wu_event
.link
);
285 fibril_add_ready(wdp
->fid
);
287 frw
->oi
.owned_by
= f
;
288 optimize_execution_power();
292 wdp
->wu_event
.inlist
= false;
293 list_remove(&wdp
->wu_event
.link
);
294 fibril_add_ready(wdp
->fid
);
295 if (frw
->readers
++ == 0) {
296 /* Consider the first reader the owner. */
297 frw
->oi
.owned_by
= f
;
299 optimize_execution_power();
303 futex_up(&async_futex
);
306 void fibril_rwlock_read_unlock(fibril_rwlock_t
*frw
)
308 assert(fibril_rwlock_is_read_locked(frw
));
309 _fibril_rwlock_common_unlock(frw
);
312 void fibril_rwlock_write_unlock(fibril_rwlock_t
*frw
)
314 assert(fibril_rwlock_is_write_locked(frw
));
315 _fibril_rwlock_common_unlock(frw
);
318 bool fibril_rwlock_is_read_locked(fibril_rwlock_t
*frw
)
322 futex_down(&async_futex
);
325 futex_up(&async_futex
);
330 bool fibril_rwlock_is_write_locked(fibril_rwlock_t
*frw
)
334 futex_down(&async_futex
);
336 assert(frw
->writers
== 1);
339 futex_up(&async_futex
);
344 bool fibril_rwlock_is_locked(fibril_rwlock_t
*frw
)
346 return fibril_rwlock_is_read_locked(frw
) ||
347 fibril_rwlock_is_write_locked(frw
);
350 void fibril_condvar_initialize(fibril_condvar_t
*fcv
)
352 list_initialize(&fcv
->waiters
);
356 fibril_condvar_wait_timeout(fibril_condvar_t
*fcv
, fibril_mutex_t
*fm
,
361 assert(fibril_mutex_is_locked(fm
));
366 awaiter_initialize(&wdata
);
367 wdata
.fid
= fibril_get_id();
368 wdata
.to_event
.inlist
= timeout
> 0;
369 wdata
.wu_event
.inlist
= true;
371 futex_down(&async_futex
);
373 getuptime(&wdata
.to_event
.expires
);
374 tv_add_diff(&wdata
.to_event
.expires
, timeout
);
375 async_insert_timeout(&wdata
);
377 list_append(&wdata
.wu_event
.link
, &fcv
->waiters
);
378 _fibril_mutex_unlock_unsafe(fm
);
379 fibril_switch(FIBRIL_TO_MANAGER
);
380 fibril_mutex_lock(fm
);
382 /* async_futex not held after fibril_switch() */
383 futex_down(&async_futex
);
384 if (wdata
.to_event
.inlist
)
385 list_remove(&wdata
.to_event
.link
);
386 if (wdata
.wu_event
.inlist
)
387 list_remove(&wdata
.wu_event
.link
);
388 futex_up(&async_futex
);
390 return wdata
.to_event
.occurred
? ETIMEOUT
: EOK
;
393 void fibril_condvar_wait(fibril_condvar_t
*fcv
, fibril_mutex_t
*fm
)
397 rc
= fibril_condvar_wait_timeout(fcv
, fm
, 0);
401 static void _fibril_condvar_wakeup_common(fibril_condvar_t
*fcv
, bool once
)
406 futex_down(&async_futex
);
407 while (!list_empty(&fcv
->waiters
)) {
408 tmp
= list_first(&fcv
->waiters
);
409 wdp
= list_get_instance(tmp
, awaiter_t
, wu_event
.link
);
410 list_remove(&wdp
->wu_event
.link
);
411 wdp
->wu_event
.inlist
= false;
414 fibril_add_ready(wdp
->fid
);
415 optimize_execution_power();
420 futex_up(&async_futex
);
423 void fibril_condvar_signal(fibril_condvar_t
*fcv
)
425 _fibril_condvar_wakeup_common(fcv
, true);
428 void fibril_condvar_broadcast(fibril_condvar_t
*fcv
)
430 _fibril_condvar_wakeup_common(fcv
, false);
437 static errno_t
fibril_timer_func(void *arg
)
439 fibril_timer_t
*timer
= (fibril_timer_t
*) arg
;
442 fibril_mutex_lock(timer
->lockp
);
444 while (timer
->state
!= fts_cleanup
) {
445 switch (timer
->state
) {
448 fibril_condvar_wait(&timer
->cv
, timer
->lockp
);
451 rc
= fibril_condvar_wait_timeout(&timer
->cv
,
452 timer
->lockp
, timer
->delay
);
453 if (rc
== ETIMEOUT
&& timer
->state
== fts_active
) {
454 timer
->state
= fts_fired
;
455 timer
->handler_fid
= fibril_get_id();
456 fibril_mutex_unlock(timer
->lockp
);
457 timer
->fun(timer
->arg
);
458 fibril_mutex_lock(timer
->lockp
);
459 timer
->handler_fid
= 0;
469 /* Acknowledge timer fibril has finished cleanup. */
470 timer
->state
= fts_clean
;
471 fibril_condvar_broadcast(&timer
->cv
);
472 fibril_mutex_unlock(timer
->lockp
);
477 /** Create new timer.
479 * @return New timer on success, @c NULL if out of memory.
481 fibril_timer_t
*fibril_timer_create(fibril_mutex_t
*lock
)
484 fibril_timer_t
*timer
;
486 timer
= calloc(1, sizeof(fibril_timer_t
));
490 fid
= fibril_create(fibril_timer_func
, (void *) timer
);
496 fibril_mutex_initialize(&timer
->lock
);
497 fibril_condvar_initialize(&timer
->cv
);
500 timer
->state
= fts_not_set
;
501 timer
->lockp
= (lock
!= NULL
) ? lock
: &timer
->lock
;
503 fibril_add_ready(fid
);
509 * @param timer Timer, must not be active or accessed by other threads.
511 void fibril_timer_destroy(fibril_timer_t
*timer
)
513 fibril_mutex_lock(timer
->lockp
);
514 assert(timer
->state
== fts_not_set
|| timer
->state
== fts_fired
);
516 /* Request timer fibril to terminate. */
517 timer
->state
= fts_cleanup
;
518 fibril_condvar_broadcast(&timer
->cv
);
520 /* Wait for timer fibril to terminate */
521 while (timer
->state
!= fts_clean
)
522 fibril_condvar_wait(&timer
->cv
, timer
->lockp
);
523 fibril_mutex_unlock(timer
->lockp
);
530 * Set timer to execute a callback function after the specified
534 * @param delay Delay in microseconds
535 * @param fun Callback function
536 * @param arg Argument for @a fun
538 void fibril_timer_set(fibril_timer_t
*timer
, suseconds_t delay
,
539 fibril_timer_fun_t fun
, void *arg
)
541 fibril_mutex_lock(timer
->lockp
);
542 fibril_timer_set_locked(timer
, delay
, fun
, arg
);
543 fibril_mutex_unlock(timer
->lockp
);
546 /** Set locked timer.
548 * Set timer to execute a callback function after the specified
549 * interval. Must be called when the timer is locked.
552 * @param delay Delay in microseconds
553 * @param fun Callback function
554 * @param arg Argument for @a fun
556 void fibril_timer_set_locked(fibril_timer_t
*timer
, suseconds_t delay
,
557 fibril_timer_fun_t fun
, void *arg
)
559 assert(fibril_mutex_is_locked(timer
->lockp
));
560 assert(timer
->state
== fts_not_set
|| timer
->state
== fts_fired
);
561 timer
->state
= fts_active
;
562 timer
->delay
= delay
;
565 fibril_condvar_broadcast(&timer
->cv
);
570 * Clears (cancels) timer and returns last state of the timer.
571 * This can be one of:
572 * - fts_not_set If the timer has not been set or has been cleared
573 * - fts_active Timer was set but did not fire
574 * - fts_fired Timer fired
577 * @return Last timer state
579 fibril_timer_state_t
fibril_timer_clear(fibril_timer_t
*timer
)
581 fibril_timer_state_t old_state
;
583 fibril_mutex_lock(timer
->lockp
);
584 old_state
= fibril_timer_clear_locked(timer
);
585 fibril_mutex_unlock(timer
->lockp
);
590 /** Clear locked timer.
592 * Clears (cancels) timer and returns last state of the timer.
593 * This can be one of:
594 * - fts_not_set If the timer has not been set or has been cleared
595 * - fts_active Timer was set but did not fire
596 * - fts_fired Timer fired
597 * Must be called when the timer is locked.
600 * @return Last timer state
602 fibril_timer_state_t
fibril_timer_clear_locked(fibril_timer_t
*timer
)
604 fibril_timer_state_t old_state
;
606 assert(fibril_mutex_is_locked(timer
->lockp
));
608 while (timer
->handler_fid
!= 0) {
609 if (timer
->handler_fid
== fibril_get_id()) {
610 printf("Deadlock detected.\n");
612 printf("Fibril %zx is trying to clear timer %p from "
613 "inside its handler %p.\n",
614 fibril_get_id(), timer
, timer
->fun
);
618 fibril_condvar_wait(&timer
->cv
, timer
->lockp
);
621 old_state
= timer
->state
;
622 timer
->state
= fts_not_set
;
627 fibril_condvar_broadcast(&timer
->cv
);
633 * Initialize a semaphore with initial count set to the provided value.
635 * @param sem Semaphore to initialize.
636 * @param count Initial count. Must not be negative.
638 void fibril_semaphore_initialize(fibril_semaphore_t
*sem
, long count
)
641 * Negative count denotes the length of waitlist,
642 * so it makes no sense as an initial value.
646 list_initialize(&sem
->waiters
);
651 * If there are fibrils waiting for tokens, this operation satisfies
652 * exactly one waiting `fibril_semaphore_down()`.
653 * This operation never blocks the fibril.
655 * @param sem Semaphore to use.
657 void fibril_semaphore_up(fibril_semaphore_t
*sem
)
659 futex_down(&async_futex
);
662 if (sem
->count
> 0) {
663 futex_up(&async_futex
);
667 link_t
*tmp
= list_first(&sem
->waiters
);
671 futex_up(&async_futex
);
673 awaiter_t
*wdp
= list_get_instance(tmp
, awaiter_t
, wu_event
.link
);
674 fibril_add_ready(wdp
->fid
);
675 optimize_execution_power();
680 * If there are no available tokens (count <= 0), this operation blocks until
681 * another fibril produces a token using `fibril_semaphore_up()`.
683 * @param sem Semaphore to use.
685 void fibril_semaphore_down(fibril_semaphore_t
*sem
)
687 futex_down(&async_futex
);
690 if (sem
->count
>= 0) {
691 futex_up(&async_futex
);
696 awaiter_initialize(&wdata
);
698 wdata
.fid
= fibril_get_id();
699 list_append(&wdata
.wu_event
.link
, &sem
->waiters
);
700 fibril_switch(FIBRIL_TO_MANAGER
);
702 /* async_futex not held after fibril_switch() */