Commit | Line | Data |
---|---|---|
d4de4869 | 1 | /* |
575c1e87 MD |
2 | * futex.spin: Promela code to validate n wakers to 1 waiter selective |
3 | * futex wakeup algorithm. | |
4 | * | |
5 | * In this model, waker threads are told whether they are still being | |
fda9aff0 MD |
6 | * waited on, and skip the futex wakeup if not. The waiter progresses |
7 | * each time it sees data in both queues. | |
8 | ||
d4de4869 MD |
9 | * Algorithm verified : |
10 | * | |
fda9aff0 MD |
11 | * queue[n] = 0; |
12 | * futex = 0; | |
13 | * futex_wake = 0; | |
d4de4869 | 14 | * |
fda9aff0 MD |
15 | * n wakers (2 loops) |
16 | * | |
17 | * queue[pid] = 1; | |
18 | * if (futex == -1) { | |
19 | * if (waker[pid].waiting == 1) { | |
20 | * waker[pid].waiting = 0; | |
21 | * futex = 0; | |
22 | * futex_wake = 1; | |
d4de4869 | 23 | * } |
2a8044f3 | 24 | * } |
d4de4869 | 25 | * |
fda9aff0 MD |
26 | * 1 waiter |
27 | * | |
d4de4869 | 28 | * while (1) { |
fda9aff0 MD |
29 | * futex = -1; |
30 | * waker[0].waiting = 1; | |
31 | * waker[1].waiting = 1; | |
32 | * while (!(queue[0] == 1 && queue[1] == 1)) { | |
33 | * if (futex == -1) { | |
34 | * futex_wake = (futex == -1 ? 0 : 1); (atomic) | |
35 | * while (futex_wake == 0) { }; | |
36 | * } | |
37 | * } | |
d4de4869 | 38 | * } |
fda9aff0 MD |
39 | * futex = 0; |
40 | * waker[0].waiting = 0; | |
41 | * waker[1].waiting = 0; | |
42 | * progress: | |
43 | * queue[0] = 0; | |
44 | * queue[1] = 0; | |
d4de4869 MD |
45 | * } |
46 | * | |
fda9aff0 MD |
47 | * if queue = 1, then !_np |
48 | * | |
49 | * By testing progress, i.e. [] <> ((!np_) || (!queue_has_entry)), we | |
50 | * check that we can never block forever if there is an entry in the | |
51 | * any of the queues. | |
52 | * | |
53 | * The waker performs only 2 loops (and NOT an infinite number of loops) | |
54 | * because we really want to see what happens when the waker stops | |
55 | * enqueuing. | |
d4de4869 MD |
56 | * |
57 | * This program is free software; you can redistribute it and/or modify | |
58 | * it under the terms of the GNU General Public License as published by | |
59 | * the Free Software Foundation; either version 2 of the License, or | |
60 | * (at your option) any later version. | |
61 | * | |
62 | * This program is distributed in the hope that it will be useful, | |
63 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
64 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
65 | * GNU General Public License for more details. | |
66 | * | |
67 | * You should have received a copy of the GNU General Public License | |
68 | * along with this program; if not, write to the Free Software | |
69 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | |
70 | * | |
575c1e87 | 71 | * Copyright (c) 2009-2011 Mathieu Desnoyers |
d4de4869 MD |
72 | */ |
73 | ||
29f38067 MD |
74 | #define get_pid() (_pid) |
75 | ||
76 | int queue[2] = 0; | |
bc8ef93e | 77 | int waiting[2] = 0; |
fda9aff0 | 78 | int futex = 0; |
2a8044f3 | 79 | int futex_wake = 0; |
d4de4869 | 80 | |
29f38067 | 81 | active [2] proctype waker() |
d4de4869 | 82 | { |
29f38067 MD |
83 | assert(get_pid() < 2); |
84 | ||
fda9aff0 MD |
85 | /* loop 1 */ |
86 | queue[get_pid()] = 1; | |
87 | ||
88 | if | |
89 | :: (futex == -1) -> | |
2a8044f3 | 90 | if |
fda9aff0 | 91 | :: (waiting[get_pid() == 1]) -> |
bc8ef93e | 92 | waiting[get_pid()] = 0; |
fda9aff0 MD |
93 | futex = 0; |
94 | futex_wake = 1; | |
95 | :: else -> skip; | |
2a8044f3 | 96 | fi; |
fda9aff0 MD |
97 | :: else -> |
98 | skip; | |
99 | fi; | |
100 | ||
101 | /* loop 2 */ | |
102 | queue[get_pid()] = 1; | |
103 | ||
104 | if | |
105 | :: (futex == -1) -> | |
106 | if | |
107 | :: (waiting[get_pid() == 1]) -> | |
108 | waiting[get_pid()] = 0; | |
109 | futex = 0; | |
110 | futex_wake = 1; | |
111 | :: else -> skip; | |
112 | fi; | |
113 | :: else -> | |
114 | skip; | |
115 | fi; | |
116 | ||
117 | #ifdef INJ_QUEUE_NO_WAKE | |
118 | /* loop 3 */ | |
119 | queue[get_pid()] = 1; | |
120 | #endif | |
d4de4869 MD |
121 | } |
122 | ||
123 | ||
124 | active proctype waiter() | |
125 | { | |
126 | do | |
127 | :: 1 -> | |
fda9aff0 | 128 | #ifndef INJ_LATE_DEC |
3646de2f | 129 | #ifndef INJ_MISORDER |
fda9aff0 MD |
130 | futex = -1; |
131 | waiting[0] = 1; | |
3646de2f MD |
132 | #else |
133 | waiting[0] = 1; | |
134 | futex = -1; | |
135 | #endif | |
fda9aff0 | 136 | waiting[1] = 1; |
d4de4869 | 137 | #endif |
fda9aff0 MD |
138 | |
139 | do | |
140 | :: 1 -> | |
141 | if | |
142 | :: (queue[0] == 1 || queue[1] == 1) -> | |
143 | break; | |
144 | :: else -> | |
145 | skip; | |
146 | fi; | |
147 | #ifdef INJ_LATE_DEC | |
148 | futex = -1; | |
bc8ef93e | 149 | waiting[0] = 1; |
bc8ef93e | 150 | waiting[1] = 1; |
37acf64d | 151 | #endif |
fda9aff0 MD |
152 | if |
153 | :: (futex == -1) -> | |
154 | atomic { | |
155 | if | |
156 | :: (futex == -1) -> | |
157 | futex_wake = 0; | |
158 | :: else -> | |
159 | futex_wake = 1; | |
160 | fi; | |
161 | } | |
162 | /* block */ | |
163 | do | |
164 | :: 1 -> | |
165 | if | |
166 | :: (futex_wake == 0) -> | |
167 | skip; | |
168 | :: else -> | |
169 | break; | |
170 | fi; | |
171 | od; | |
172 | :: else -> | |
173 | skip; | |
174 | fi; | |
175 | od; | |
bc8ef93e | 176 | |
fda9aff0 MD |
177 | futex = 0; |
178 | waiting[0] = 0; | |
179 | waiting[1] = 0; | |
180 | progress: /* progress on dequeue */ | |
181 | queue[0] = 0; | |
182 | queue[1] = 0; | |
d4de4869 | 183 | od; |
fda9aff0 | 184 | |
d4de4869 | 185 | } |