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) { | |
e922fbe4 MD |
27 | * futex = -1; |
28 | * if (queue == 1) { | |
29 | * futex = 0; | |
30 | * } else { | |
31 | * if (futex == -1) { | |
32 | * futex_wake = (futex == -1 ? 0 : 1); (atomic) | |
33 | * while (futex_wake == 0) { }; | |
7f12dad2 | 34 | * } |
e922fbe4 | 35 | * } |
7f12dad2 | 36 | * progress: |
e922fbe4 MD |
37 | * queue = 0; |
38 | * } | |
39 | * | |
40 | * if queue = 1, then !_np | |
41 | * | |
42 | * By testing progress, i.e. [] <> ((!np_) || (!queue_has_entry)), we | |
43 | * check that we can never block forever if there is an entry in the | |
44 | * queue. | |
45 | * | |
46 | * The waker performs only 2 loops (and NOT an infinite number of loops) | |
47 | * because we really want to see what happens when the waker stops | |
48 | * enqueuing. | |
49 | * | |
50 | * This program is free software; you can redistribute it and/or modify | |
51 | * it under the terms of the GNU General Public License as published by | |
52 | * the Free Software Foundation; either version 2 of the License, or | |
53 | * (at your option) any later version. | |
54 | * | |
55 | * This program is distributed in the hope that it will be useful, | |
56 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
57 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
58 | * GNU General Public License for more details. | |
59 | * | |
60 | * You should have received a copy of the GNU General Public License | |
61 | * along with this program; if not, write to the Free Software | |
62 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | |
63 | * | |
64 | * Copyright (c) 2009 Mathieu Desnoyers | |
65 | */ | |
66 | ||
67 | #define get_pid() (_pid) | |
68 | ||
69 | int queue[2] = 0; | |
70 | int futex = 0; | |
71 | int futex_wake = 0; | |
72 | ||
73 | active [2] proctype waker() | |
74 | { | |
75 | assert(get_pid() < 2); | |
76 | ||
77 | /* loop 1 */ | |
78 | queue[get_pid()] = 1; | |
79 | ||
80 | if | |
81 | :: (futex == -1) -> | |
82 | futex = 0; | |
83 | futex_wake = 1; | |
84 | :: else -> | |
85 | skip; | |
86 | fi; | |
87 | ||
88 | /* loop 2 */ | |
89 | queue[get_pid()] = 1; | |
90 | ||
91 | if | |
92 | :: (futex == -1) -> | |
93 | futex = 0; | |
94 | futex_wake = 1; | |
95 | :: else -> | |
96 | skip; | |
97 | fi; | |
98 | ||
99 | #ifdef INJ_QUEUE_NO_WAKE | |
100 | /* loop 3 */ | |
101 | queue[get_pid()] = 1; | |
102 | #endif | |
103 | } | |
104 | ||
105 | ||
106 | active proctype waiter() | |
107 | { | |
108 | do | |
109 | :: 1 -> | |
110 | #ifndef INJ_LATE_DEC | |
111 | futex = -1; | |
112 | #endif | |
113 | ||
114 | if | |
115 | :: (queue[0] == 1 || queue[1] == 1) -> | |
116 | #ifndef INJ_LATE_DEC | |
117 | futex = 0; | |
118 | #endif | |
119 | skip; | |
120 | :: else -> | |
121 | #ifdef INJ_LATE_DEC | |
122 | futex = -1; | |
123 | #endif | |
124 | if | |
125 | :: (futex == -1) -> | |
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 | fi; | |
148 | progress: /* Progress on dequeue */ | |
149 | queue[0] = 0; | |
150 | queue[1] = 0; | |
151 | od; | |
152 | ||
153 | } |