Commit | Line | Data |
---|---|---|
ef781656 MD |
1 | /* |
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. | |
4 | * | |
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 | |
10 | * progress. | |
11 | * | |
12 | * Algorithm verified : | |
13 | * | |
14 | * active = 0; (waker daemon is active) | |
15 | * futex = 0; | |
16 | * futex_wake = 0; | |
17 | * | |
18 | * 1 waker (2 loops) | |
19 | * | |
20 | * futex = 0; | |
21 | * active = 1; (e.g. listen()) | |
22 | * futex_wake = 1; | |
23 | * active = 0; (e.g. close()) | |
24 | * futex = -1; | |
25 | * | |
26 | * n waiters (read-only) | |
27 | * | |
28 | * while (1) { | |
29 | * if (active == 0) { | |
30 | * if (futex == -1) { | |
31 | * futex_wake = (futex == -1 ? 0 : 1); (atomic) | |
32 | * while (futex_wake == 0) { }; | |
33 | * } | |
34 | * } | |
35 | * progress: | |
36 | * } | |
37 | * | |
38 | * if active = 1, then !_np | |
39 | * | |
40 | * By testing progress, i.e. [] <> ((!np_) || (!isactive)), we | |
41 | * check that waiters we can never block forever if the waker is active. | |
42 | * | |
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 | |
45 | * running. | |
46 | * | |
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. | |
51 | * | |
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. | |
56 | * | |
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. | |
60 | * | |
61 | * Copyright (c) 2009 Mathieu Desnoyers | |
62 | */ | |
63 | ||
64 | #define get_pid() (_pid) | |
65 | ||
66 | int _active = 0; | |
67 | int futex = 0; | |
68 | int futex_wake = 0; | |
69 | ||
70 | active proctype waker() | |
71 | { | |
72 | /* loop 1 */ | |
73 | futex = 0; | |
74 | _active = 1; | |
75 | futex_wake = 1; | |
76 | _active = 0; | |
77 | futex = -1; | |
78 | ||
79 | /* loop 2 */ | |
80 | #ifndef INJ_MISORDER_WAKE | |
81 | futex = 0; | |
82 | _active = 1; | |
83 | futex_wake = 1; | |
84 | #else | |
85 | futex_wake = 1; | |
86 | futex = 0; | |
87 | _active = 1; | |
88 | #endif | |
89 | ||
90 | #ifdef INJ_QUEUE_NO_WAKE | |
91 | _active = 0; | |
92 | futex = -1; | |
93 | ||
94 | /* loop 3 */ | |
95 | futex = 0; | |
96 | _active = 1; | |
97 | #endif | |
98 | } | |
99 | ||
100 | /* | |
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. | |
105 | * | |
106 | * However, the order in which wakeup sets the futex value vs sending | |
107 | * the wakeup DOES matter, as shows the INJ_MISORDER_WAKE | |
108 | * error-injection. | |
109 | */ | |
110 | active [2] proctype waiter() | |
111 | { | |
112 | do | |
113 | :: 1 -> | |
114 | if | |
115 | #ifndef INJ_MISORDER | |
116 | :: (_active == 0) -> | |
117 | #else | |
118 | :: (futex == -1) -> | |
119 | #endif | |
120 | if | |
121 | #ifndef INJ_MISORDER | |
122 | :: (futex == -1) -> | |
123 | #else | |
124 | :: (_active == 0) -> | |
125 | #endif | |
126 | atomic { | |
127 | if | |
128 | :: (futex == -1) -> | |
129 | futex_wake = 0; | |
130 | :: else -> | |
131 | futex_wake = 1; | |
132 | fi; | |
133 | } | |
134 | /* block */ | |
135 | do | |
136 | :: 1 -> | |
137 | if | |
138 | :: (futex_wake == 0) -> | |
139 | skip; | |
140 | :: else -> | |
141 | break; | |
142 | fi; | |
143 | od; | |
144 | :: else -> | |
145 | skip; | |
146 | fi; | |
147 | :: else -> | |
148 | skip; | |
149 | fi; | |
150 | progress: | |
151 | skip; | |
152 | od; | |
153 | } |