This source file includes following definitions.
- init_bag_empty
- add_to_bag
- bag_from_list
- bag_is_empty
- bag_is_subset
- bag_equals
- bag_or
- bag_xor
- bag_and_not
- store_change
- block_sigint
- idle_thread
- sigint_handler
- send_signal
- signal_sending_thread
- mutator_thread
- main
- main
- main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 #include <config.h>
45
46
47 #if 4 < __GNUC__ + (3 <= __GNUC_MINOR__)
48 # pragma GCC diagnostic ignored "-Wreturn-type"
49 #endif
50
51 #include "gl_linked_list.h"
52
53 #if SIGNAL_SAFE_LIST
54
55 # if USE_ISOC_THREADS || USE_POSIX_THREADS || USE_ISOC_AND_POSIX_THREADS
56
57
58
59
60
61
62
63 # include <signal.h>
64 # include <stdint.h>
65 # include <stdlib.h>
66 # include <unistd.h>
67 # include <time.h>
68
69 # include "glthread/thread.h"
70 # include "glthread/yield.h"
71
72 # include "macros.h"
73
74
75
76
77
78
79
80 # define MY_SIGNAL SIGTERM
81
82
83
84 # define BAG_SIZE 512
85
86 # define RANDOM(n) (rand () % (n))
87 # define RANDOM_OBJECT() ((void *) (uintptr_t) RANDOM (BAG_SIZE))
88
89
90 typedef struct { uint32_t bits[BAG_SIZE / 32]; } bag_t;
91
92
93 static void
94 init_bag_empty (bag_t *bagp)
95 {
96 size_t i;
97
98 for (i = 0; i < BAG_SIZE / 32; i++)
99 bagp->bits[i] = 0;
100 }
101
102
103 static void
104 add_to_bag (uintptr_t x, bag_t *bagp)
105 {
106 if (!(x < BAG_SIZE))
107 abort ();
108 bagp->bits[x / 32] |= (1U << (x % 32));
109 }
110
111
112 static bag_t
113 bag_from_list (gl_list_t list)
114 {
115 bag_t bag;
116
117 init_bag_empty (&bag);
118 {
119 gl_list_iterator_t iter = gl_list_iterator (list);
120 const void *elt;
121
122 while (gl_list_iterator_next (&iter, &elt, NULL))
123 add_to_bag ((uintptr_t) elt, &bag);
124 gl_list_iterator_free (&iter);
125 }
126
127 return bag;
128 }
129
130
131 _GL_ATTRIBUTE_MAYBE_UNUSED static bool
132 bag_is_empty (bag_t bag)
133 {
134 size_t i;
135
136 for (i = 0; i < BAG_SIZE / 32; i++)
137 if (bag.bits[i] != 0)
138 return false;
139 return true;
140 }
141
142
143 static bool
144 bag_is_subset (bag_t bag1, bag_t bag2)
145 {
146 size_t i;
147
148 for (i = 0; i < BAG_SIZE / 32; i++)
149 if ((bag1.bits[i] & ~bag2.bits[i]) != 0)
150 return false;
151 return true;
152 }
153
154
155 static bool
156 bag_equals (bag_t bag1, bag_t bag2)
157 {
158 size_t i;
159
160 for (i = 0; i < BAG_SIZE / 32; i++)
161 if (bag1.bits[i] != bag2.bits[i])
162 return false;
163 return true;
164 }
165
166
167
168 _GL_ATTRIBUTE_MAYBE_UNUSED static bag_t
169 bag_or (bag_t bag1, bag_t bag2)
170 {
171 bag_t bag;
172 size_t i;
173
174 for (i = 0; i < BAG_SIZE / 32; i++)
175 bag.bits[i] = bag1.bits[i] | bag2.bits[i];
176
177 return bag;
178 }
179
180
181
182 static bag_t
183 bag_xor (bag_t bag1, bag_t bag2)
184 {
185 bag_t bag;
186 size_t i;
187
188 for (i = 0; i < BAG_SIZE / 32; i++)
189 bag.bits[i] = bag1.bits[i] ^ bag2.bits[i];
190
191 return bag;
192 }
193
194
195 _GL_ATTRIBUTE_MAYBE_UNUSED static bag_t
196 bag_and_not (bag_t bag1, bag_t bag2)
197 {
198 bag_t bag;
199 size_t i;
200
201 for (i = 0; i < BAG_SIZE / 32; i++)
202 bag.bits[i] = bag1.bits[i] & ~bag2.bits[i];
203
204 return bag;
205 }
206
207
208
209
210 static int volatile test;
211
212
213
214
215 # define NUM_RECENT_BAGS 1024
216 static bag_t volatile recent_bags[NUM_RECENT_BAGS];
217 static uintptr_t volatile recent_changes[NUM_RECENT_BAGS];
218
219
220
221
222
223
224
225 static size_t volatile recent_newest_index;
226 static size_t volatile recent_oldest_index;
227
228 static void
229 store_change (uintptr_t x, gl_list_t list)
230 {
231 recent_oldest_index +=
232 (recent_newest_index - recent_oldest_index) == NUM_RECENT_BAGS - 1;
233 recent_changes[recent_newest_index % NUM_RECENT_BAGS] = x;
234 recent_bags[(recent_newest_index + 1) % NUM_RECENT_BAGS] = bag_from_list (list);
235 recent_newest_index++;
236 }
237
238 static gl_list_t volatile list1;
239
240 static gl_thread_t volatile signal_target;
241
242
243 static unsigned int volatile num_mutations;
244 static unsigned int volatile num_signals_sent;
245 static unsigned int volatile num_signals_arrived;
246
247
248 static void
249 block_sigint (void)
250 {
251 sigset_t mask;
252
253 sigemptyset (&mask);
254 sigaddset (&mask, MY_SIGNAL);
255 sigprocmask (SIG_BLOCK, &mask, NULL);
256 }
257
258
259 static void *
260 idle_thread (void *arg)
261 {
262 for (;;)
263 gl_thread_yield ();
264
265
266 }
267
268
269
270 static _GL_ASYNC_SAFE void
271 sigint_handler (int signo)
272 {
273 num_signals_arrived++;
274
275 bag_t bag;
276 init_bag_empty (&bag);
277 {
278 gl_list_iterator_t iter = gl_list_iterator (list1);
279 const void *elt;
280
281 while (gl_list_iterator_next (&iter, &elt, NULL))
282 add_to_bag ((uintptr_t) elt, &bag);
283 gl_list_iterator_free (&iter);
284 }
285
286 bool found = false;
287 if (test != 1)
288 {
289
290
291
292
293 size_t i;
294 bag_t changes_from_i_to_newest;
295 init_bag_empty (&changes_from_i_to_newest);
296
297 for (i = recent_newest_index;;)
298 {
299 if (bag_is_subset (bag_xor (bag, recent_bags[i % NUM_RECENT_BAGS]),
300 changes_from_i_to_newest)
301 && i >= recent_oldest_index)
302 {
303 found = true;
304 break;
305 }
306 if (i <= recent_oldest_index)
307 break;
308 i--;
309 add_to_bag (recent_changes[i % NUM_RECENT_BAGS],
310 &changes_from_i_to_newest);
311 }
312 }
313 else
314 {
315
316
317
318 size_t i = recent_newest_index;
319 found = (bag_equals (bag, recent_bags[i % NUM_RECENT_BAGS])
320 || (i > recent_oldest_index
321 && bag_equals (bag, recent_bags[(i - 1) % NUM_RECENT_BAGS])
322 && i > recent_oldest_index));
323 }
324 if (!found)
325 {
326
327
328
329 fprintf (stderr, "unexpected bag (after %u mutations and %u signals)\n",
330 num_mutations, num_signals_arrived);
331 fflush (stderr);
332 abort ();
333 }
334 }
335
336
337 static void
338 send_signal (void)
339 {
340 #if 0
341
342
343
344 raise (MY_SIGNAL);
345 #else
346
347
348
349
350
351
352
353 kill (getpid (), MY_SIGNAL);
354 #endif
355 }
356
357
358 static void *
359 signal_sending_thread (void *arg)
360 {
361 if (test != 3)
362 block_sigint ();
363
364 int repeat;
365
366 for (repeat = 1000; repeat > 0; repeat--)
367 {
368 num_signals_sent++; send_signal ();
369 num_signals_sent++; send_signal ();
370 num_signals_sent++; send_signal ();
371 num_signals_sent++; send_signal ();
372 num_signals_sent++; send_signal ();
373 {
374 struct timespec ts;
375 ts.tv_sec = 0; ts.tv_nsec = 1000000;
376 nanosleep (&ts, NULL);
377 }
378 gl_thread_yield ();
379 }
380
381 printf ("Sent %u signals. Received %u signals. Done after %u mutations.\n",
382 num_signals_sent, num_signals_arrived, num_mutations);
383
384 exit (0);
385
386
387 }
388
389
390 static void *
391 mutator_thread (void *arg)
392 {
393 if (test != 1)
394 block_sigint ();
395
396 gl_list_t list2 = (gl_list_t) arg;
397
398 for (num_mutations = 0; ; num_mutations++)
399 {
400 unsigned int operation = RANDOM (2);
401 switch (operation)
402 {
403 case 0:
404 {
405 const void *obj = RANDOM_OBJECT ();
406 ASSERT (gl_list_nx_add_first (list2, obj) != NULL);
407 store_change ((uintptr_t) obj, list2);
408 ASSERT (gl_list_nx_add_first (list1, obj) != NULL);
409 }
410 break;
411 case 1:
412 if (gl_list_size (list2) > 0)
413 {
414 size_t index = RANDOM (gl_list_size (list2));
415 const void *obj = gl_list_get_at (list2, index);
416 ASSERT (gl_list_remove (list2, obj));
417 store_change ((uintptr_t) obj, list2);
418 ASSERT (gl_list_remove (list1, obj));
419 }
420 break;
421 }
422 }
423
424
425 }
426
427 int
428 main (int argc, char *argv[])
429 {
430 test = atoi (argv[1]);
431
432
433 if (argc > 2)
434 srand (atoi (argv[2]));
435
436 gl_list_t list2;
437
438 {
439 size_t initial_size = RANDOM (50);
440 const void **contents =
441 (const void **) malloc (initial_size * sizeof (const void *));
442 size_t i;
443
444 for (i = 0; i < initial_size; i++)
445 contents[i] = RANDOM_OBJECT ();
446
447 list1 = gl_list_nx_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
448 ASSERT (list1 != NULL);
449 for (i = 0; i < initial_size; i++)
450 ASSERT (gl_list_nx_add_first (list1, contents[i]) != NULL);
451
452 list2 = gl_list_nx_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
453 ASSERT (list2 != NULL);
454 for (i = 0; i < initial_size; i++)
455 ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
456
457 recent_oldest_index = 0;
458 recent_bags[0] = bag_from_list (list2);
459 recent_newest_index = 0;
460 }
461
462
463
464
465 #if 0
466 signal (MY_SIGNAL, sigint_handler);
467 #else
468 {
469 struct sigaction action;
470 action.sa_handler = sigint_handler;
471 action.sa_flags = SA_RESTART | SA_NODEFER;
472 sigemptyset (&action.sa_mask);
473 ASSERT (sigaction (MY_SIGNAL, &action, NULL) == 0);
474 }
475 #endif
476
477
478 switch (test)
479 {
480 case 1:
481 {
482 signal_target = gl_thread_create (mutator_thread, list2);
483 signal_sending_thread (NULL);
484 abort ();
485 }
486
487 case 2:
488 {
489 signal_target = gl_thread_create (idle_thread, NULL);
490 gl_thread_create (mutator_thread, list2);
491 signal_sending_thread (NULL);
492 abort ();
493 }
494
495 case 3:
496 {
497 gl_thread_create (mutator_thread, list2);
498 signal_target = gl_thread_self (); signal_sending_thread (NULL);
499 abort ();
500 }
501
502 default:
503 ASSERT (false);
504 }
505 }
506
507 # else
508
509 # include <stdio.h>
510
511 int
512 main ()
513 {
514 fputs ("Skipping test: POSIX compatible multithreading not enabled\n", stderr);
515 return 77;
516 }
517
518 # endif
519
520 #else
521
522 # include <stdio.h>
523
524 int
525 main ()
526 {
527 fputs ("Skipping test: signal-safety of linked lists is not enabled\n", stderr);
528 return 77;
529 }
530
531 #endif