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

/* */

DEFINITIONS

1. store_newest_sum
2. block_sigint
3. idle_thread
4. sigint_handler
5. send_signal
6. signal_sending_thread
7. mutator_thread
8. main
9. main
10. 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 strongly 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 #  define RANDOM(n) (rand () % (n))
  83 #  define RANDOM_OBJECT() ((void *) (uintptr_t) RANDOM (10000))
  84 
  85 /* test == 1: signals are executed in the mutator thread.
  86    test == 2: signals are executed in an idle thread.
  87    test == 3: signals are executed in the signal-sending thread.  */
  88 static int volatile test;
  89 
  90 /* Store the newest sum, the previous sum, the sum before the previous sum,
  91    and so on in a circular buffer.  */
  92 #  define NUM_RECENT_SUMS (4*1024*1024)
  93 static uintptr_t volatile recent_sums[NUM_RECENT_SUMS];
  94 /* 0 <= recent_sums_oldest_index < recent_sums_newest_index
  95    and recent_sums_newest_index - recent_sums_oldest_index <= NUM_RECENT_SUMS.
  96    For each i with  recent_sums_oldest_index <= i < recent_sums_newest_index,
  97    the sum is actually stored at recent_sums[i % NUM_RECENT_SUMS].  */
  98 static size_t volatile recent_sums_newest_index;
  99 static size_t volatile recent_sums_oldest_index;
 100 
 101 static void
 102 store_newest_sum (uintptr_t sum)
     /*  */
 103 {
 104   recent_sums_oldest_index +=
 105     (recent_sums_newest_index - recent_sums_oldest_index) == NUM_RECENT_SUMS;
 106   recent_sums[recent_sums_newest_index % NUM_RECENT_SUMS] = sum;
 107   recent_sums_newest_index++;
 108 }
 109 
 110 static gl_list_t volatile list1;
 111 
 112 static gl_thread_t volatile signal_target;
 113 
 114 /* Statistics.  */
 115 static unsigned int volatile num_mutations;
 116 static unsigned int volatile num_signals_sent;
 117 static unsigned int volatile num_signals_arrived;
 118 
 119 /* Blocks the MY_SIGNAL signal in the current thread.  */
 120 static void
 121 block_sigint (void)
     /*  */
 122 {
 123   sigset_t mask;
 124 
 125   sigemptyset (&mask);
 126   sigaddset (&mask, MY_SIGNAL);
 127   sigprocmask (SIG_BLOCK, &mask, NULL); /* equivalent to pthread_sigmask */
 128 }
 129 
 130 /* This thread is idle.  */
 131 static void *
 132 idle_thread (void *arg)
     /*  */
 133 {
 134   for (;;)
 135     gl_thread_yield ();
 136 
 137   /*NOTREACHED*/
 138 }
 139 
 140 /* The signal handler iterates through the list and verifies that the sum of
 141    all elements in the list is one of the allowed values.  */
 142 static _GL_ASYNC_SAFE void
 143 sigint_handler (int signo)
     /*  */
 144 {
 145   num_signals_arrived++;
 146 
 147   uintptr_t sum = 0;
 148   {
 149     gl_list_iterator_t iter = gl_list_iterator (list1);
 150     const void *elt;
 151 
 152     while (gl_list_iterator_next (&iter, &elt, NULL))
 153       sum += (uintptr_t) elt;
 154     gl_list_iterator_free (&iter);
 155   }
 156 
 157   bool found = false;
 158   if (test != 1)
 159     {
 160       /* The signal handler executes in a different thread than the mutator
 161          thread.  By the time we get here, the mutator thread can have done
 162          any number of mutations; it is reasonable to assume that this number
 163          of mutations is small.  */
 164       size_t i;
 165       for (i = recent_sums_newest_index - 1;;)
 166         {
 167           if (sum == recent_sums[i % NUM_RECENT_SUMS]
 168               && i >= recent_sums_oldest_index)
 169             {
 170               found = true;
 171               break;
 172             }
 173           if (i <= recent_sums_oldest_index)
 174             break;
 175           i--;
 176         }
 177     }
 178   else
 179     {
 180       /* The signal handler executes in the mutator thread.  Its execution
 181          interrupts a single mutation.  The allowed sum is either the newest
 182          or the previous one.  */
 183       size_t i = recent_sums_newest_index - 1;
 184       found = (sum == recent_sums[i % NUM_RECENT_SUMS]
 185                || (i > recent_sums_oldest_index
 186                    && sum == recent_sums[(i - 1) % NUM_RECENT_SUMS]));
 187     }
 188   if (!found)
 189     {
 190       /* POSIX does not allow uses of stdio from within a signal handler, but
 191          it should work here, because the rest of the program does not use
 192          stdio.  */
 193       size_t i = recent_sums_newest_index - 1;
 194       fprintf (stderr, "sum = %lu, expected %lu or older (after %u mutations and %u signals)\n",
 195                (unsigned long) sum,
 196                (unsigned long) recent_sums[i % NUM_RECENT_SUMS],
 197                num_mutations, num_signals_arrived);
 198       fflush (stderr);
 199       abort ();
 200     }
 201 }
 202 
 203 /* Sends a MY_SIGNAL signal to the current process.  */
 204 static void
 205 send_signal (void)
     /*  */
 206 {
 207 #if 0
 208   /* This does not work for test != 3, because raise() sends the signal to the
 209      current thread always, and if test != 3 the signal is eternally blocked
 210      in the current thread; thus it will never get delivered.  */
 211   raise (MY_SIGNAL);
 212 #else
 213   /* This works: Either
 214        kill (getpid (), MY_SIGNAL);
 215      or
 216        pthread_kill (signal_target, MY_SIGNAL);
 217      The difference is that for kill(), the OS determines the (only) thread that
 218      has not blocked the signal, whereas for pthread_kill() we have manually
 219      determined this thread.  */
 220   kill (getpid (), MY_SIGNAL);
 221 #endif
 222 }
 223 
 224 /* This thread permanently sends MY_SIGNAL signals.  */
 225 static void *
 226 signal_sending_thread (void *arg)
     /*  */
 227 {
 228   if (test != 3)
 229     block_sigint ();
 230 
 231   int repeat;
 232 
 233   for (repeat = 1000; repeat > 0; repeat--)
 234     {
 235       num_signals_sent++; send_signal ();
 236       num_signals_sent++; send_signal ();
 237       num_signals_sent++; send_signal ();
 238       num_signals_sent++; send_signal ();
 239       num_signals_sent++; send_signal ();
 240       {
 241         struct timespec ts;
 242         ts.tv_sec = 0; ts.tv_nsec = 1000000;
 243         nanosleep (&ts, NULL);
 244       }
 245       gl_thread_yield ();
 246     }
 247 
 248   printf ("Sent %u signals. Received %u signals. Done after %u mutations.\n",
 249           num_signals_sent, num_signals_arrived, num_mutations);
 250 
 251   exit (0);
 252 
 253   /*NOTREACHED*/
 254 }
 255 
 256 /* This thread repeatedly adds and removes objects from the list.  */
 257 static void *
 258 mutator_thread (void *arg)
     /*  */
 259 {
 260   if (test != 1)
 261     block_sigint ();
 262 
 263   gl_list_t list2 = (gl_list_t) arg;
 264 
 265   for (num_mutations = 0; ; num_mutations++)
 266     {
 267       unsigned int operation = RANDOM (2);
 268       switch (operation)
 269         {
 270         case 0: /* Add an element.  */
 271           {
 272             const void *obj = RANDOM_OBJECT ();
 273             ASSERT (gl_list_nx_add_first (list2, obj) != NULL);
 274             uintptr_t sum_before_current_operation =
 275               recent_sums[(recent_sums_newest_index - 1) % NUM_RECENT_SUMS];
 276             uintptr_t sum_after_current_operation =
 277               sum_before_current_operation + (uintptr_t) obj;
 278             store_newest_sum (sum_after_current_operation);
 279             ASSERT (gl_list_nx_add_first (list1, obj) != NULL);
 280           }
 281           break;
 282         case 1: /* Remove an element.  */
 283           if (gl_list_size (list2) > 0)
 284             {
 285               size_t index = RANDOM (gl_list_size (list2));
 286               const void *obj = gl_list_get_at (list2, index);
 287               ASSERT (gl_list_remove (list2, obj));
 288               uintptr_t sum_before_current_operation =
 289                 recent_sums[(recent_sums_newest_index - 1) % NUM_RECENT_SUMS];
 290               uintptr_t sum_after_current_operation =
 291                 sum_before_current_operation - (uintptr_t) obj;
 292               store_newest_sum (sum_after_current_operation);
 293               ASSERT (gl_list_remove (list1, obj));
 294             }
 295           break;
 296         }
 297     }
 298 
 299   /*NOTREACHED*/
 300 }
 301 
 302 int
 303 main (int argc, char *argv[])
     /*  */
 304 {
 305   test = atoi (argv[1]);
 306 
 307   /* Allow the user to provide a non-default random seed on the command line.  */
 308   if (argc > 2)
 309     srand (atoi (argv[2]));
 310 
 311   gl_list_t list2;
 312   /* Initialize list1 and list2.  */
 313   {
 314     size_t initial_size = RANDOM (50);
 315     const void **contents =
 316       (const void **) malloc (initial_size * sizeof (const void *));
 317     size_t i;
 318 
 319     for (i = 0; i < initial_size; i++)
 320       contents[i] = RANDOM_OBJECT ();
 321 
 322     list1 = gl_list_nx_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
 323     ASSERT (list1 != NULL);
 324     for (i = 0; i < initial_size; i++)
 325       ASSERT (gl_list_nx_add_first (list1, contents[i]) != NULL);
 326 
 327     list2 = gl_list_nx_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
 328     ASSERT (list2 != NULL);
 329     for (i = 0; i < initial_size; i++)
 330       ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
 331 
 332     uintptr_t initial_sum = 0;
 333     for (i = 0; i < initial_size; i++)
 334       initial_sum += (uintptr_t) contents[i];
 335     recent_sums_oldest_index = 0;
 336     recent_sums[0] = initial_sum;
 337     recent_sums_newest_index = 1;
 338   }
 339 
 340   /* Install the signal handler.
 341      It needs to be done with sigaction(), not signal(), otherwise on Solaris
 342      and AIX the program crashes at the second incoming MY_SIGNAL.  */
 343   #if 0
 344   signal (MY_SIGNAL, sigint_handler);
 345   #else
 346   {
 347     struct sigaction action;
 348     action.sa_handler = sigint_handler;
 349     action.sa_flags = SA_RESTART | SA_NODEFER;
 350     sigemptyset (&action.sa_mask);
 351     ASSERT (sigaction (MY_SIGNAL, &action, NULL) == 0);
 352   }
 353   #endif
 354 
 355   /* Launch the threads.  */
 356   switch (test)
 357     {
 358     case 1:
 359       {
 360         signal_target = gl_thread_create (mutator_thread, list2);
 361         signal_sending_thread (NULL);
 362         abort ();
 363       }
 364 
 365     case 2:
 366       {
 367         signal_target = gl_thread_create (idle_thread, NULL);
 368         gl_thread_create (mutator_thread, list2);
 369         signal_sending_thread (NULL);
 370         abort ();
 371       }
 372 
 373     case 3:
 374       {
 375         gl_thread_create (mutator_thread, list2);
 376         signal_target = gl_thread_self (); signal_sending_thread (NULL);
 377         abort ();
 378       }
 379 
 380     default:
 381       ASSERT (false);
 382     }
 383 }
 384 
 385 # else
 386 
 387 #  include <stdio.h>
 388 
 389 int
 390 main ()
     /*  */
 391 {
 392   fputs ("Skipping test: POSIX compatible multithreading not enabled\n", stderr);
 393   return 77;
 394 }
 395 
 396 # endif
 397 
 398 #else
 399 
 400 # include <stdio.h>
 401 
 402 int
 403 main ()
     /*  */
 404 {
 405   fputs ("Skipping test: signal-safety of linked lists is not enabled\n", stderr);
 406   return 77;
 407 }
 408 
 409 #endif

/* */