root/maint/gnulib/tests/test-asyncsafe-linked_list-weak.c

/* */

DEFINITIONS

1. init_bag_empty
2. add_to_bag
3. bag_from_list
4. bag_is_empty
5. bag_is_subset
6. bag_equals
7. bag_or
8. bag_xor
9. bag_and_not
10. store_change
11. block_sigint
12. idle_thread
13. sigint_handler
14. send_signal
15. signal_sending_thread
16. mutator_thread
17. main
18. main
19. main

   1 /* Test of async-safe sequential list data type implementation.
   2    Copyright (C) 2021 Free Software Foundation, Inc.
   3 
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 3 of the License, or
   7    (at your option) any later version.
   8 
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13 
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16 
  17 /* Written by Bruno Haible <bruno@clisp.org>, 2021.  */
  18 
  19 /* There are two notions of async-safe for a list:
  20      * A list is "strongly async-safe" if it can be iterated in any signal
  21        handler, and the signal handler will see
  22          - in the single-threaded case: either the value after or the value
  23            before the current in-progress change that was interrupted,
  24          - in the multi-threaded case: one of the most recent values for the
  25            *entire list*.
  26      * A list is "weakly async-safe" if it can be iterated in any signal
  27        handler, and
  28          - in the single-threaded case: the signal handler will see either
  29            the value after or the value before the current in-progress change
  30            that was interrupted,
  31          - in the multi-threaded case:
  32            - elements which were present in the list throughout the iteration
  33              will be seen by the iterator,
  34            - elements which were absent in the list throughout the iteration
  35              will be unseen by the iterator,
  36            - no statement regarding the elements which are being added or
  37              removed during the iteration.
  38 
  39    This unit test attempts to verify that the 'linked-list' implementation of
  40    lists is weakly async-safe.
  41 
  42    It fails the test in the multi-threaded cases (test == 2 or 3).  */
  43 
  44 #include <config.h>
  45 
  46 /* Work around GCC bug 44511.  */
  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 /* || USE_WINDOWS_THREADS */
  56 /* This test works only with POSIX compatible threads.
  57    With Windows threads, send_signal() has to be implemented as
  58      raise (MY_SIGNAL);
  59    hence only test == 3 tests anything, and in fact only 5 signals arrive.
  60    This small test is not able to detect a buggy implementation.  Therefore
  61    mark the test as skipped in this case.  */
  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 /* The signal we use for testing.
  75    For portability, it should be one of SIGINT, SIGFPE, SIGTERM.
  76    If we use SIGINT, it prevents debugging with gdb.
  77    If we use SIGFPE, it does not work right with valgrind.
  78    If we use SIGTERM, it could interfere with a system shutdown.
  79    Oh well.  */
  80 #  define MY_SIGNAL SIGTERM
  81 
  82 /* The number of different objects we can store in a bag.
  83    Must be a multiple of 32.  */
  84 #  define BAG_SIZE 512
  85 
  86 #  define RANDOM(n) (rand () % (n))
  87 #  define RANDOM_OBJECT() ((void *) (uintptr_t) RANDOM (BAG_SIZE))
  88 
  89 /* Representation of a bag as a bit set.  */
  90 typedef struct { uint32_t bits[BAG_SIZE / 32]; } bag_t;
  91 
  92 /* Initializes a bag to empty.  */
  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 /* Adds an element to a bag.  */
 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 /* Returns a bag that contains the elements of the given list.  */
 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 /* Returns true if and only if the given bag is empty.  */
 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 /* Returns true if and only if BAG1 is a subset of BAG2.  */
 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 /* Returns true if and only if the two given bags have the same elements.  */
 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 /* Returns a bag that contains the elements of BAG1 and the elements of
 167    BAG2.  */
 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 /* Returns a bag that contains the elements of BAG1 that are not in BAG2
 181    and the elements of BAG2 that are not in BAG1.  */
 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 /* Returns a bag that contains the elements of BAG1 that are not in BAG2.  */
 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 /* test == 1: signals are executed in the mutator thread.
 208    test == 2: signals are executed in an idle thread.
 209    test == 3: signals are executed in the signal-sending thread.  */
 210 static int volatile test;
 211 
 212 /* Store the newest list's bag representation, the previous list's bag
 213    representation, and so on in a circular buffer.  Store also the
 214    changes in a circular buffer.  */
 215 # define NUM_RECENT_BAGS 1024 /* can be up to (BAG_SIZE * BAG_SIZE) */
 216 static bag_t volatile recent_bags[NUM_RECENT_BAGS];
 217 static uintptr_t volatile recent_changes[NUM_RECENT_BAGS];
 218 /* 0 <= recent_oldest_index <= recent_newest_index
 219    and recent_newest_index - recent_oldest_index < NUM_RECENT_BAGS.
 220    For each i with  recent_oldest_index <= i <= recent_newest_index, the bag
 221    representation of the list[i] is stored at recent_bags[i % NUM_RECENT_BAGS].
 222    For each i with  recent_oldest_index <= i < recent_newest_index, the object
 223    of the change between list[i] and list[i+1] is stored at
 224    recent_changes[i % NUM_RECENT_BAGS].  */
 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 /* Statistics.  */
 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 /* Blocks the MY_SIGNAL signal in the current thread.  */
 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); /* equivalent to pthread_sigmask */
 256 }
 257 
 258 /* This thread is idle.  */
 259 static void *
 260 idle_thread (void *arg)
     /*  */
 261 {
 262   for (;;)
 263     gl_thread_yield ();
 264 
 265   /*NOTREACHED*/
 266 }
 267 
 268 /* The signal handler iterates through the list and verifies that the sum of
 269    all elements in the list is one of the allowed values.  */
 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       /* The signal handler executes in a different thread than the mutator
 290          thread.  By the time we get here, the mutator thread can have done
 291          any number of mutations; it is reasonable to assume that this number
 292          of mutations is small.  */
 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       /* The signal handler executes in the mutator thread.  Its execution
 316          interrupts a single mutation.  The allowed bag is either the newest
 317          or the previous one.  */
 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       /* POSIX does not allow uses of stdio from within a signal handler, but
 327          it should work here, because the rest of the program does not use
 328          stdio.  */
 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 /* Sends a MY_SIGNAL signal to the current process.  */
 337 static void
 338 send_signal (void)
     /*  */
 339 {
 340 #if 0
 341   /* This does not work for test != 3, because raise() sends the signal to the
 342      current thread always, and if test != 3 the signal is eternally blocked
 343      in the current thread; thus it will never get delivered.  */
 344   raise (MY_SIGNAL);
 345 #else
 346   /* This works: Either
 347        kill (getpid (), MY_SIGNAL);
 348      or
 349        pthread_kill (signal_target, MY_SIGNAL);
 350      The difference is that for kill(), the OS determines the (only) thread that
 351      has not blocked the signal, whereas for pthread_kill() we have manually
 352      determined this thread.  */
 353   kill (getpid (), MY_SIGNAL);
 354 #endif
 355 }
 356 
 357 /* This thread permanently sends MY_SIGNAL signals.  */
 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   /*NOTREACHED*/
 387 }
 388 
 389 /* This thread repeatedly adds and removes objects from the list.  */
 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: /* Add an element.  */
 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: /* Remove an element.  */
 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   /*NOTREACHED*/
 425 }
 426 
 427 int
 428 main (int argc, char *argv[])
     /*  */
 429 {
 430   test = atoi (argv[1]);
 431 
 432   /* Allow the user to provide a non-default random seed on the command line.  */
 433   if (argc > 2)
 434     srand (atoi (argv[2]));
 435 
 436   gl_list_t list2;
 437   /* Initialize list1 and list2.  */
 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   /* Install the signal handler.
 463      It needs to be done with sigaction(), not signal(), otherwise on Solaris
 464      and AIX the program crashes at the second incoming MY_SIGNAL.  */
 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   /* Launch the threads.  */
 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

/* */