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