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

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

Add interfaces for partial enforcement of locking protocols in userspace:

  • fibril_mutex_is_locked()
  • fibril_rwlock_is_read_locked()
  • fibril_rwlock_is_write_locked()
  • Property mode set to 100644
File size: 10.0 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
345void fibril_condvar_initialize(fibril_condvar_t *fcv)
346{
347 list_initialize(&fcv->waiters);
348}
349
350int
351fibril_condvar_wait_timeout(fibril_condvar_t *fcv, fibril_mutex_t *fm,
352 suseconds_t timeout)
353{
354 awaiter_t wdata;
355
356 assert(fibril_mutex_is_locked(fm));
357
358 if (timeout < 0)
359 return ETIMEOUT;
360
361 wdata.fid = fibril_get_id();
362 wdata.active = false;
363
364 wdata.to_event.inlist = timeout > 0;
365 wdata.to_event.occurred = false;
366 link_initialize(&wdata.to_event.link);
367
368 wdata.wu_event.inlist = true;
369 link_initialize(&wdata.wu_event.link);
370
371 futex_down(&async_futex);
372 if (timeout) {
373 gettimeofday(&wdata.to_event.expires, NULL);
374 tv_add(&wdata.to_event.expires, timeout);
375 async_insert_timeout(&wdata);
376 }
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);
381
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);
389
390 return wdata.to_event.occurred ? ETIMEOUT : EOK;
391}
392
393void fibril_condvar_wait(fibril_condvar_t *fcv, fibril_mutex_t *fm)
394{
395 int rc;
396
397 rc = fibril_condvar_wait_timeout(fcv, fm, 0);
398 assert(rc == EOK);
399}
400
401static void _fibril_condvar_wakeup_common(fibril_condvar_t *fcv, bool once)
402{
403 link_t *tmp;
404 awaiter_t *wdp;
405
406 futex_down(&async_futex);
407 while (!list_empty(&fcv->waiters)) {
408 tmp = fcv->waiters.next;
409 wdp = list_get_instance(tmp, awaiter_t, wu_event.link);
410 list_remove(&wdp->wu_event.link);
411 wdp->wu_event.inlist = false;
412 if (!wdp->active) {
413 wdp->active = true;
414 fibril_add_ready(wdp->fid);
415 optimize_execution_power();
416 if (once)
417 break;
418 }
419 }
420 futex_up(&async_futex);
421}
422
423void fibril_condvar_signal(fibril_condvar_t *fcv)
424{
425 _fibril_condvar_wakeup_common(fcv, true);
426}
427
428void fibril_condvar_broadcast(fibril_condvar_t *fcv)
429{
430 _fibril_condvar_wakeup_common(fcv, false);
431}
432
433/** @}
434 */
Note: See TracBrowser for help on using the repository browser.