2 * futex.spin: Promela code to validate 1 waker to n waiters futex
3 * wakeup algorithm, where waiters have read-only access to the futex.
5 * In this model, the waker thread unconditionally wakes all waiters if
6 * they need to be awakened. We guarantee that all waiters will never
7 * wait forever if they need to be awakened, even if the waker is
8 * inactive after requiring the wakeup. When "active" is set (e.g. a
9 * daemon is available to service waiter requests), the waiter should
12 * Algorithm verified :
14 * active = 0; (waker daemon is active)
21 * active = 1; (e.g. listen())
23 * active = 0; (e.g. close())
26 * n waiters (read-only)
31 * futex_wake = (futex == -1 ? 0 : 1); (atomic)
32 * while (futex_wake == 0) { };
38 * if active = 1, then !_np
40 * By testing progress, i.e. [] <> ((!np_) || (!isactive)), we
41 * check that waiters we can never block forever if the waker is active.
43 * The waker performs only 2 loops (and NOT an infinite number of loops)
44 * because we really want to see what happens when the waker stops
47 * This program is free software; you can redistribute it and/or modify
48 * it under the terms of the GNU General Public License as published by
49 * the Free Software Foundation; either version 2 of the License, or
50 * (at your option) any later version.
52 * This program is distributed in the hope that it will be useful,
53 * but WITHOUT ANY WARRANTY; without even the implied warranty of
54 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
55 * GNU General Public License for more details.
57 * You should have received a copy of the GNU General Public License
58 * along with this program; if not, write to the Free Software
59 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
61 * Copyright (c) 2009 Mathieu Desnoyers
64 #define get_pid() (_pid)
70 active proctype waker()
80 #ifndef INJ_MISORDER_WAKE
90 #ifdef INJ_QUEUE_NO_WAKE
101 * The INJ_MISORDER error-injection test case succeeds, which means
102 * order of active vs futex value read does not matter. It is
103 * understandable because every time the active value is enabled by the
104 * waker, a wake is performed.
106 * However, the order in which wakeup sets the futex value vs sending
107 * the wakeup DOES matter, as shows the INJ_MISORDER_WAKE
110 active [2] proctype waiter()
138 :: (futex_wake == 0) ->