[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: asyncsafe-linked_list failure on Fedora, Ubuntu
|
From: |
Bruno Haible |
|
Subject: |
Re: asyncsafe-linked_list failure on Fedora, Ubuntu |
|
Date: |
Sun, 28 Mar 2021 20:19:17 +0200 |
|
User-agent: |
KMail/5.1.3 (Linux/4.4.0-203-generic; KDE/5.18.0; x86_64; ; ) |
> Meanwhile I know that the unit test is partially wrong. Still need to
> determine whether the SIGNAL_SAFE_LIST is buggy as well or not.
In fact, there are two possiblities to define "async-safe list", and each
leads to a different unit test.
The SIGNAL_SAFE_LIST is OK in both respects, but only in single-threaded
applications. In multi-threaded applications, the tests fail, and valgrind
shows why: the iteration over the list may reference list nodes that have
just been freed by a simultaneously running thread:
Invalid read of size 8
at 0x40180A: gl_linked_iterator_next (gl_anylinked_list2.h:1015)
by 0x40119B: gl_list_iterator_next (gl_list.h:820)
by 0x40119B: sigint_handler (test-asyncsafe-linked_list-strong.c:152)
by 0x4E4B38F: ??? (in /lib/x86_64-linux-gnu/libpthread-2.23.so)
by 0x508C776: kill (syscall-template.S:84)
by 0x4015BF: send_signal (test-asyncsafe-linked_list-strong.c:220)
by 0x4015BF: signal_sending_thread.isra.0
(test-asyncsafe-linked_list-strong.c:237)
by 0x400F8C: main (test-asyncsafe-linked_list-strong.c:376)
Address 0x68c72f0 is 16 bytes inside a block of size 24 free'd
at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
by 0x401F2D: gl_linked_remove_node (gl_anylinked_list2.h:834)
by 0x4014F4: gl_list_remove (gl_list.h:792)
by 0x4014F4: mutator_thread (test-asyncsafe-linked_list-strong.c:293)
by 0x4E416B9: start_thread (pthread_create.c:333)
Block was alloc'd at
at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
by 0x402205: gl_linked_nx_add_first (gl_anylinked_list2.h:600)
by 0x4013E4: gl_list_nx_add_first (gl_list.h:723)
by 0x4013E4: mutator_thread (test-asyncsafe-linked_list-strong.c:279)
by 0x4E416B9: start_thread (pthread_create.c:333)
2021-03-28 Bruno Haible <bruno@clisp.org>
linked-list tests: Add another test for SIGNAL_SAFE_LIST.
* tests/test-asyncsafe-linked_list-strong.c: Renamed from
tests/test-asyncsafe-linked_list.c.
* tests/test-asyncsafe-linked_list-strong.sh: Renamed from
tests/test-asyncsafe-linked_list.sh.
* tests/test-asyncsafe-linked_list-weak.c: New file, based on
tests/test-asyncsafe-linked_list.c.
* tests/test-asyncsafe-linked_list-weak.sh: New file, based on
tests/test-asyncsafe-linked_list.sh.
* modules/linked-list-tests (Files): Add
tests/test-asyncsafe-linked_list-weak.*,
tests/test-asyncsafe-linked_list-strong.*.
(Makefile.am): Arrange to test also
tests/test-asyncsafe-linked_list-weak.sh. Mark
test-asyncsafe-linked_list-weak.sh and
test-asyncsafe-linked_list-strong.sh as expected failures.
diff --git a/modules/linked-list-tests b/modules/linked-list-tests
index bf21bee..c45f02b 100644
--- a/modules/linked-list-tests
+++ b/modules/linked-list-tests
@@ -1,7 +1,9 @@
Files:
tests/test-linked_list.c
-tests/test-asyncsafe-linked_list.sh
-tests/test-asyncsafe-linked_list.c
+tests/test-asyncsafe-linked_list-weak.sh
+tests/test-asyncsafe-linked_list-weak.c
+tests/test-asyncsafe-linked_list-strong.sh
+tests/test-asyncsafe-linked_list-strong.c
tests/macros.h
Depends-on:
@@ -15,6 +17,16 @@ sigprocmask
configure.ac:
Makefile.am:
-TESTS += test-linked_list test-asyncsafe-linked_list.sh
-check_PROGRAMS += test-linked_list test-asyncsafe-linked_list
-test_asyncsafe_linked_list_LDADD = $(LDADD) @LIBMULTITHREAD@ @YIELD_LIB@
+TESTS += \
+ test-linked_list \
+ test-asyncsafe-linked_list-weak.sh \
+ test-asyncsafe-linked_list-strong.sh
+XFAIL_TESTS += \
+ test-asyncsafe-linked_list-weak.sh \
+ test-asyncsafe-linked_list-strong.sh
+check_PROGRAMS += \
+ test-linked_list \
+ test-asyncsafe-linked_list-weak \
+ test-asyncsafe-linked_list-strong
+test_asyncsafe_linked_list_weak_LDADD = $(LDADD) @LIBMULTITHREAD@ @YIELD_LIB@
+test_asyncsafe_linked_list_strong_LDADD = $(LDADD) @LIBMULTITHREAD@ @YIELD_LIB@
diff --git a/tests/test-asyncsafe-linked_list.c
b/tests/test-asyncsafe-linked_list-strong.c
similarity index 57%
rename from tests/test-asyncsafe-linked_list.c
rename to tests/test-asyncsafe-linked_list-strong.c
index 56e76bb..36b1a1a 100644
--- a/tests/test-asyncsafe-linked_list.c
+++ b/tests/test-asyncsafe-linked_list-strong.c
@@ -16,6 +16,31 @@
/* Written by Bruno Haible <bruno@clisp.org>, 2021. */
+/* There are two notions of async-safe for a list:
+ * A list is "strongly async-safe" if it can be iterated in any signal
+ handler, and the signal handler will see
+ - in the single-threaded case: either the value after or the value
+ before the current in-progress change that was interrupted,
+ - in the multi-threaded case: one of the most recent values for the
+ *entire list*.
+ * A list is "weakly async-safe" if it can be iterated in any signal
+ handler, and
+ - in the single-threaded case: the signal handler will see either
+ the value after or the value before the current in-progress change
+ that was interrupted,
+ - in the multi-threaded case:
+ - elements which were present in the list throughout the iteration
+ will be seen by the iterator,
+ - elements which were absent in the list throughout the iteration
+ will be unseen by the iterator,
+ - no statement regarding the elements which are being added or
+ removed during the iteration.
+
+ This unit test attempts to verify that the 'linked-list' implementation of
+ lists is strongly async-safe.
+
+ It fails the test in the multi-threaded cases (test == 2 or 3). */
+
#include <config.h>
/* Work around GCC bug 44511. */
@@ -30,8 +55,8 @@
# if USE_ISOC_THREADS || USE_POSIX_THREADS || USE_ISOC_AND_POSIX_THREADS /* ||
USE_WINDOWS_THREADS */
/* This test works only with POSIX compatible threads.
With Windows threads, send_signal() has to be implemented as
- raise (SIGINT);
- hence only test == 2 tests anything, and in fact only 5 signals arrive.
+ raise (MY_SIGNAL);
+ hence only test == 3 tests anything, and in fact only 5 signals arrive.
This small test is not able to detect a buggy implementation. Therefore
mark the test as skipped in this case. */
@@ -46,16 +71,41 @@
# include "macros.h"
+/* The signal we use for testing.
+ For portability, it should be one of SIGINT, SIGFPE, SIGTERM.
+ If we use SIGINT, it prevents debugging with gdb.
+ If we use SIGFPE, it does not work right with valgrind.
+ If we use SIGTERM, it could interfere with a system shutdown.
+ Oh well. */
+# define MY_SIGNAL SIGTERM
+
# define RANDOM(n) (rand () % (n))
# define RANDOM_OBJECT() ((void *) (uintptr_t) RANDOM (10000))
-/* test == 1: signals are executed in an idle thread.
- test == 2: signals are executed in the signal-sending thread.
- test == 3: signals are executed in the mutator thread. */
+/* test == 1: signals are executed in the mutator thread.
+ test == 2: signals are executed in an idle thread.
+ test == 3: signals are executed in the signal-sending thread. */
static int volatile test;
-static uintptr_t volatile sum_before_current_operation;
-static uintptr_t volatile sum_after_current_operation;
+/* Store the newest sum, the previous sum, the sum before the previous sum,
+ and so on in a circular buffer. */
+# define NUM_RECENT_SUMS (4*1024*1024)
+static uintptr_t volatile recent_sums[NUM_RECENT_SUMS];
+/* 0 <= recent_sums_oldest_index < recent_sums_newest_index
+ and recent_sums_newest_index - recent_sums_oldest_index <= NUM_RECENT_SUMS.
+ For each i with recent_sums_oldest_index <= i < recent_sums_newest_index,
+ the sum is actually stored at recent_sums[i % NUM_RECENT_SUMS]. */
+static size_t volatile recent_sums_newest_index;
+static size_t volatile recent_sums_oldest_index;
+
+static void
+store_newest_sum (uintptr_t sum)
+{
+ recent_sums_oldest_index +=
+ (recent_sums_newest_index - recent_sums_oldest_index) == NUM_RECENT_SUMS;
+ recent_sums[recent_sums_newest_index % NUM_RECENT_SUMS] = sum;
+ recent_sums_newest_index++;
+}
static gl_list_t volatile list1;
@@ -66,14 +116,14 @@ static unsigned int volatile num_mutations;
static unsigned int volatile num_signals_sent;
static unsigned int volatile num_signals_arrived;
-/* Blocks the SIGINT signal in the current thread. */
+/* Blocks the MY_SIGNAL signal in the current thread. */
static void
block_sigint (void)
{
sigset_t mask;
sigemptyset (&mask);
- sigaddset (&mask, SIGINT);
+ sigaddset (&mask, MY_SIGNAL);
sigprocmask (SIG_BLOCK, &mask, NULL); /* equivalent to pthread_sigmask */
}
@@ -88,7 +138,7 @@ idle_thread (void *arg)
}
/* The signal handler iterates through the list and verifies that the sum of
- all elements in the list is one of the two allowed values. */
+ all elements in the list is one of the allowed values. */
static _GL_ASYNC_SAFE void
sigint_handler (int signo)
{
@@ -103,47 +153,79 @@ sigint_handler (int signo)
sum += (uintptr_t) elt;
gl_list_iterator_free (&iter);
}
- if (!(sum == sum_before_current_operation
- || sum == sum_after_current_operation))
+
+ bool found = false;
+ if (test != 1)
+ {
+ /* The signal handler executes in a different thread than the mutator
+ thread. By the time we get here, the mutator thread can have done
+ any number of mutations; it is reasonable to assume that this number
+ of mutations is small. */
+ size_t i;
+ for (i = recent_sums_newest_index - 1;;)
+ {
+ if (sum == recent_sums[i % NUM_RECENT_SUMS]
+ && i >= recent_sums_oldest_index)
+ {
+ found = true;
+ break;
+ }
+ if (i <= recent_sums_oldest_index)
+ break;
+ i--;
+ }
+ }
+ else
+ {
+ /* The signal handler executes in the mutator thread. Its execution
+ interrupts a single mutation. The allowed sum is either the newest
+ or the previous one. */
+ size_t i = recent_sums_newest_index - 1;
+ found = (sum == recent_sums[i % NUM_RECENT_SUMS]
+ || (i > recent_sums_oldest_index
+ && sum == recent_sums[(i - 1) % NUM_RECENT_SUMS]));
+ }
+ if (!found)
{
/* POSIX does not allow uses of stdio from within a signal handler, but
it should work here, because the rest of the program does not use
stdio. */
- fprintf (stderr, "sum = %lu, expected %lu or %lu\n",
+ size_t i = recent_sums_newest_index - 1;
+ fprintf (stderr, "sum = %lu, expected %lu or older (after %u mutations
and %u signals)\n",
(unsigned long) sum,
- (unsigned long) sum_before_current_operation,
- (unsigned long) sum_after_current_operation);
+ (unsigned long) recent_sums[i % NUM_RECENT_SUMS],
+ num_mutations, num_signals_arrived);
fflush (stderr);
abort ();
}
}
-/* Sends a SIGINT signal to the current process. */
+/* Sends a MY_SIGNAL signal to the current process. */
static void
send_signal (void)
{
#if 0
- /* This does not work for test != 2, because raise() sends the signal to the
- current thread always, and if test != 2 the signal is eternally blocked
+ /* This does not work for test != 3, because raise() sends the signal to the
+ current thread always, and if test != 3 the signal is eternally blocked
in the current thread; thus it will never get delivered. */
- raise (SIGINT);
+ raise (MY_SIGNAL);
#else
/* This works: Either
- kill (getpid (), SIGINT);
+ kill (getpid (), MY_SIGNAL);
or
- pthread_kill (signal_target, SIGINT);
+ pthread_kill (signal_target, MY_SIGNAL);
The difference is that for kill(), the OS determines the (only) thread
that
has not blocked the signal, whereas for pthread_kill() we have manually
determined this thread. */
- kill (getpid (), SIGINT);
+ kill (getpid (), MY_SIGNAL);
#endif
}
-/* This thread permanently sends SIGINT signals. */
+/* This thread permanently sends MY_SIGNAL signals. */
static void *
signal_sending_thread (void *arg)
{
- if (test != 2)
+ if (test != 3)
block_sigint ();
int repeat;
@@ -175,7 +257,7 @@ signal_sending_thread (void *arg)
static void *
mutator_thread (void *arg)
{
- if (test != 3)
+ if (test != 1)
block_sigint ();
gl_list_t list2 = (gl_list_t) arg;
@@ -189,10 +271,12 @@ mutator_thread (void *arg)
{
const void *obj = RANDOM_OBJECT ();
ASSERT (gl_list_nx_add_first (list2, obj) != NULL);
- sum_after_current_operation =
+ uintptr_t sum_before_current_operation =
+ recent_sums[(recent_sums_newest_index - 1) % NUM_RECENT_SUMS];
+ uintptr_t sum_after_current_operation =
sum_before_current_operation + (uintptr_t) obj;
+ store_newest_sum (sum_after_current_operation);
ASSERT (gl_list_nx_add_first (list1, obj) != NULL);
- sum_before_current_operation = sum_after_current_operation;
}
break;
case 1: /* Remove an element. */
@@ -201,10 +285,12 @@ mutator_thread (void *arg)
size_t index = RANDOM (gl_list_size (list2));
const void *obj = gl_list_get_at (list2, index);
ASSERT (gl_list_remove (list2, obj));
- sum_after_current_operation =
+ uintptr_t sum_before_current_operation =
+ recent_sums[(recent_sums_newest_index - 1) % NUM_RECENT_SUMS];
+ uintptr_t sum_after_current_operation =
sum_before_current_operation - (uintptr_t) obj;
+ store_newest_sum (sum_after_current_operation);
ASSERT (gl_list_remove (list1, obj));
- sum_before_current_operation = sum_after_current_operation;
}
break;
}
@@ -246,22 +332,23 @@ main (int argc, char *argv[])
uintptr_t initial_sum = 0;
for (i = 0; i < initial_size; i++)
initial_sum += (uintptr_t) contents[i];
- sum_before_current_operation = initial_sum;
- sum_after_current_operation = initial_sum;
+ recent_sums_oldest_index = 0;
+ recent_sums[0] = initial_sum;
+ recent_sums_newest_index = 1;
}
/* Install the signal handler.
It needs to be done with sigaction(), not signal(), otherwise on Solaris
- and AIX the program crashes at the second incoming SIGINT. */
+ and AIX the program crashes at the second incoming MY_SIGNAL. */
#if 0
- signal (SIGINT, sigint_handler);
+ signal (MY_SIGNAL, sigint_handler);
#else
{
struct sigaction action;
action.sa_handler = sigint_handler;
action.sa_flags = SA_RESTART | SA_NODEFER;
sigemptyset (&action.sa_mask);
- ASSERT (sigaction (SIGINT, &action, NULL) == 0);
+ ASSERT (sigaction (MY_SIGNAL, &action, NULL) == 0);
}
#endif
@@ -270,23 +357,23 @@ main (int argc, char *argv[])
{
case 1:
{
- signal_target = gl_thread_create (idle_thread, NULL);
- gl_thread_create (mutator_thread, list2);
+ signal_target = gl_thread_create (mutator_thread, list2);
signal_sending_thread (NULL);
abort ();
}
case 2:
{
+ signal_target = gl_thread_create (idle_thread, NULL);
gl_thread_create (mutator_thread, list2);
- signal_target = gl_thread_self (); signal_sending_thread (NULL);
+ signal_sending_thread (NULL);
abort ();
}
case 3:
{
- signal_target = gl_thread_create (mutator_thread, list2);
- signal_sending_thread (NULL);
+ gl_thread_create (mutator_thread, list2);
+ signal_target = gl_thread_self (); signal_sending_thread (NULL);
abort ();
}
diff --git a/tests/test-asyncsafe-linked_list.sh
b/tests/test-asyncsafe-linked_list-strong.sh
similarity index 54%
copy from tests/test-asyncsafe-linked_list.sh
copy to tests/test-asyncsafe-linked_list-strong.sh
index c2ad176..226b0a5 100755
--- a/tests/test-asyncsafe-linked_list.sh
+++ b/tests/test-asyncsafe-linked_list-strong.sh
@@ -2,14 +2,14 @@
st=0
for i in 1 2 3 ; do
- ${CHECKER} ./test-asyncsafe-linked_list${EXEEXT} $i
+ ${CHECKER} ./test-asyncsafe-linked_list-strong${EXEEXT} $i
result=$?
if test $result = 77; then
st=77
break
fi
if test $result != 0; then
- echo test-asyncsafe-linked_list.sh: test case $i failed >&2
+ echo "test-asyncsafe-linked_list-strong.sh: test case $i failed" >&2
st=1
fi
done
diff --git a/tests/test-asyncsafe-linked_list-weak.c
b/tests/test-asyncsafe-linked_list-weak.c
new file mode 100644
index 0000000..f2b0d61
--- /dev/null
+++ b/tests/test-asyncsafe-linked_list-weak.c
@@ -0,0 +1,531 @@
+/* Test of async-safe sequential list data type implementation.
+ Copyright (C) 2021 Free Software Foundation, Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+/* Written by Bruno Haible <bruno@clisp.org>, 2021. */
+
+/* There are two notions of async-safe for a list:
+ * A list is "strongly async-safe" if it can be iterated in any signal
+ handler, and the signal handler will see
+ - in the single-threaded case: either the value after or the value
+ before the current in-progress change that was interrupted,
+ - in the multi-threaded case: one of the most recent values for the
+ *entire list*.
+ * A list is "weakly async-safe" if it can be iterated in any signal
+ handler, and
+ - in the single-threaded case: the signal handler will see either
+ the value after or the value before the current in-progress change
+ that was interrupted,
+ - in the multi-threaded case:
+ - elements which were present in the list throughout the iteration
+ will be seen by the iterator,
+ - elements which were absent in the list throughout the iteration
+ will be unseen by the iterator,
+ - no statement regarding the elements which are being added or
+ removed during the iteration.
+
+ This unit test attempts to verify that the 'linked-list' implementation of
+ lists is weakly async-safe.
+
+ It fails the test in the multi-threaded cases (test == 2 or 3). */
+
+#include <config.h>
+
+/* Work around GCC bug 44511. */
+#if 4 < __GNUC__ + (3 <= __GNUC_MINOR__)
+# pragma GCC diagnostic ignored "-Wreturn-type"
+#endif
+
+#include "gl_linked_list.h"
+
+#if SIGNAL_SAFE_LIST
+
+# if USE_ISOC_THREADS || USE_POSIX_THREADS || USE_ISOC_AND_POSIX_THREADS /* ||
USE_WINDOWS_THREADS */
+/* This test works only with POSIX compatible threads.
+ With Windows threads, send_signal() has to be implemented as
+ raise (MY_SIGNAL);
+ hence only test == 3 tests anything, and in fact only 5 signals arrive.
+ This small test is not able to detect a buggy implementation. Therefore
+ mark the test as skipped in this case. */
+
+# include <signal.h>
+# include <stdint.h>
+# include <stdlib.h>
+# include <unistd.h>
+# include <time.h>
+
+# include "glthread/thread.h"
+# include "glthread/yield.h"
+
+# include "macros.h"
+
+/* The signal we use for testing.
+ For portability, it should be one of SIGINT, SIGFPE, SIGTERM.
+ If we use SIGINT, it prevents debugging with gdb.
+ If we use SIGFPE, it does not work right with valgrind.
+ If we use SIGTERM, it could interfere with a system shutdown.
+ Oh well. */
+# define MY_SIGNAL SIGTERM
+
+/* The number of different objects we can store in a bag.
+ Must be a multiple of 32. */
+# define BAG_SIZE 512
+
+# define RANDOM(n) (rand () % (n))
+# define RANDOM_OBJECT() ((void *) (uintptr_t) RANDOM (BAG_SIZE))
+
+/* Representation of a bag as a bit set. */
+typedef struct { uint32_t bits[BAG_SIZE / 32]; } bag_t;
+
+/* Initializes a bag to empty. */
+static void
+init_bag_empty (bag_t *bagp)
+{
+ size_t i;
+
+ for (i = 0; i < BAG_SIZE / 32; i++)
+ bagp->bits[i] = 0;
+}
+
+/* Adds an element to a bag. */
+static void
+add_to_bag (uintptr_t x, bag_t *bagp)
+{
+ if (!(x < BAG_SIZE))
+ abort ();
+ bagp->bits[x / 32] |= (1U << (x % 32));
+}
+
+/* Returns a bag that contains the elements of the given list. */
+static bag_t
+bag_from_list (gl_list_t list)
+{
+ bag_t bag;
+
+ init_bag_empty (&bag);
+ {
+ gl_list_iterator_t iter = gl_list_iterator (list);
+ const void *elt;
+
+ while (gl_list_iterator_next (&iter, &elt, NULL))
+ add_to_bag ((uintptr_t) elt, &bag);
+ gl_list_iterator_free (&iter);
+ }
+
+ return bag;
+}
+
+/* Returns true if and only if the given bag is empty. */
+static bool _GL_ATTRIBUTE_MAYBE_UNUSED
+bag_is_empty (bag_t bag)
+{
+ size_t i;
+
+ for (i = 0; i < BAG_SIZE / 32; i++)
+ if (bag.bits[i] != 0)
+ return false;
+ return true;
+}
+
+/* Returns true if and only if BAG1 is a subset of BAG2. */
+static bool
+bag_is_subset (bag_t bag1, bag_t bag2)
+{
+ size_t i;
+
+ for (i = 0; i < BAG_SIZE / 32; i++)
+ if ((bag1.bits[i] & ~bag2.bits[i]) != 0)
+ return false;
+ return true;
+}
+
+/* Returns true if and only if the two given bags have the same elements. */
+static bool
+bag_equals (bag_t bag1, bag_t bag2)
+{
+ size_t i;
+
+ for (i = 0; i < BAG_SIZE / 32; i++)
+ if (bag1.bits[i] != bag2.bits[i])
+ return false;
+ return true;
+}
+
+/* Returns a bag that contains the elements of BAG1 and the elements of
+ BAG2. */
+static bag_t _GL_ATTRIBUTE_MAYBE_UNUSED
+bag_or (bag_t bag1, bag_t bag2)
+{
+ bag_t bag;
+ size_t i;
+
+ for (i = 0; i < BAG_SIZE / 32; i++)
+ bag.bits[i] = bag1.bits[i] | bag2.bits[i];
+
+ return bag;
+}
+
+/* Returns a bag that contains the elements of BAG1 that are not in BAG2
+ and the elements of BAG2 that are not in BAG1. */
+static bag_t
+bag_xor (bag_t bag1, bag_t bag2)
+{
+ bag_t bag;
+ size_t i;
+
+ for (i = 0; i < BAG_SIZE / 32; i++)
+ bag.bits[i] = bag1.bits[i] ^ bag2.bits[i];
+
+ return bag;
+}
+
+/* Returns a bag that contains the elements of BAG1 that are not in BAG2. */
+static bag_t _GL_ATTRIBUTE_MAYBE_UNUSED
+bag_and_not (bag_t bag1, bag_t bag2)
+{
+ bag_t bag;
+ size_t i;
+
+ for (i = 0; i < BAG_SIZE / 32; i++)
+ bag.bits[i] = bag1.bits[i] & ~bag2.bits[i];
+
+ return bag;
+}
+
+/* test == 1: signals are executed in the mutator thread.
+ test == 2: signals are executed in an idle thread.
+ test == 3: signals are executed in the signal-sending thread. */
+static int volatile test;
+
+/* Store the newest list's bag representation, the previous list's bag
+ representation, and so on in a circular buffer. Store also the
+ changes in a circular buffer. */
+# define NUM_RECENT_BAGS 1024 /* can be up to (BAG_SIZE * BAG_SIZE) */
+static bag_t volatile recent_bags[NUM_RECENT_BAGS];
+static uintptr_t volatile recent_changes[NUM_RECENT_BAGS];
+/* 0 <= recent_oldest_index <= recent_newest_index
+ and recent_newest_index - recent_oldest_index < NUM_RECENT_BAGS.
+ For each i with recent_oldest_index <= i <= recent_newest_index, the bag
+ representation of the list[i] is stored at recent_bags[i % NUM_RECENT_BAGS].
+ For each i with recent_oldest_index <= i < recent_newest_index, the object
+ of the change between list[i] and list[i+1] is stored at
+ recent_changes[i % NUM_RECENT_BAGS]. */
+static size_t volatile recent_newest_index;
+static size_t volatile recent_oldest_index;
+
+static void
+store_change (uintptr_t x, gl_list_t list)
+{
+ recent_oldest_index +=
+ (recent_newest_index - recent_oldest_index) == NUM_RECENT_BAGS - 1;
+ recent_changes[recent_newest_index % NUM_RECENT_BAGS] = x;
+ recent_bags[(recent_newest_index + 1) % NUM_RECENT_BAGS] = bag_from_list
(list);
+ recent_newest_index++;
+}
+
+static gl_list_t volatile list1;
+
+static gl_thread_t volatile signal_target;
+
+/* Statistics. */
+static unsigned int volatile num_mutations;
+static unsigned int volatile num_signals_sent;
+static unsigned int volatile num_signals_arrived;
+
+/* Blocks the MY_SIGNAL signal in the current thread. */
+static void
+block_sigint (void)
+{
+ sigset_t mask;
+
+ sigemptyset (&mask);
+ sigaddset (&mask, MY_SIGNAL);
+ sigprocmask (SIG_BLOCK, &mask, NULL); /* equivalent to pthread_sigmask */
+}
+
+/* This thread is idle. */
+static void *
+idle_thread (void *arg)
+{
+ for (;;)
+ gl_thread_yield ();
+
+ /*NOTREACHED*/
+}
+
+/* The signal handler iterates through the list and verifies that the sum of
+ all elements in the list is one of the allowed values. */
+static _GL_ASYNC_SAFE void
+sigint_handler (int signo)
+{
+ num_signals_arrived++;
+
+ bag_t bag;
+ init_bag_empty (&bag);
+ {
+ gl_list_iterator_t iter = gl_list_iterator (list1);
+ const void *elt;
+
+ while (gl_list_iterator_next (&iter, &elt, NULL))
+ add_to_bag ((uintptr_t) elt, &bag);
+ gl_list_iterator_free (&iter);
+ }
+
+ bool found = false;
+ if (test != 1)
+ {
+ /* The signal handler executes in a different thread than the mutator
+ thread. By the time we get here, the mutator thread can have done
+ any number of mutations; it is reasonable to assume that this number
+ of mutations is small. */
+ size_t i;
+ bag_t changes_from_i_to_newest;
+ init_bag_empty (&changes_from_i_to_newest);
+
+ for (i = recent_newest_index;;)
+ {
+ if (bag_is_subset (bag_xor (bag, recent_bags[i % NUM_RECENT_BAGS]),
+ changes_from_i_to_newest)
+ && i >= recent_oldest_index)
+ {
+ found = true;
+ break;
+ }
+ if (i <= recent_oldest_index)
+ break;
+ i--;
+ add_to_bag (recent_changes[i % NUM_RECENT_BAGS],
+ &changes_from_i_to_newest);
+ }
+ }
+ else
+ {
+ /* The signal handler executes in the mutator thread. Its execution
+ interrupts a single mutation. The allowed bag is either the newest
+ or the previous one. */
+ size_t i = recent_newest_index;
+ found = (bag_equals (bag, recent_bags[i % NUM_RECENT_BAGS])
+ || (i > recent_oldest_index
+ && bag_equals (bag, recent_bags[(i - 1) % NUM_RECENT_BAGS])
+ && i > recent_oldest_index));
+ }
+ if (!found)
+ {
+ /* POSIX does not allow uses of stdio from within a signal handler, but
+ it should work here, because the rest of the program does not use
+ stdio. */
+ fprintf (stderr, "unexpected bag (after %u mutations and %u signals)\n",
+ num_mutations, num_signals_arrived);
+ fflush (stderr);
+ abort ();
+ }
+}
+
+/* Sends a MY_SIGNAL signal to the current process. */
+static void
+send_signal (void)
+{
+#if 0
+ /* This does not work for test != 3, because raise() sends the signal to the
+ current thread always, and if test != 3 the signal is eternally blocked
+ in the current thread; thus it will never get delivered. */
+ raise (MY_SIGNAL);
+#else
+ /* This works: Either
+ kill (getpid (), MY_SIGNAL);
+ or
+ pthread_kill (signal_target, MY_SIGNAL);
+ The difference is that for kill(), the OS determines the (only) thread
that
+ has not blocked the signal, whereas for pthread_kill() we have manually
+ determined this thread. */
+ kill (getpid (), MY_SIGNAL);
+#endif
+}
+
+/* This thread permanently sends MY_SIGNAL signals. */
+static void *
+signal_sending_thread (void *arg)
+{
+ if (test != 3)
+ block_sigint ();
+
+ int repeat;
+
+ for (repeat = 1000; repeat > 0; repeat--)
+ {
+ num_signals_sent++; send_signal ();
+ num_signals_sent++; send_signal ();
+ num_signals_sent++; send_signal ();
+ num_signals_sent++; send_signal ();
+ num_signals_sent++; send_signal ();
+ {
+ struct timespec ts;
+ ts.tv_sec = 0; ts.tv_nsec = 1000000;
+ nanosleep (&ts, NULL);
+ }
+ gl_thread_yield ();
+ }
+
+ printf ("Sent %u signals. Received %u signals. Done after %u mutations.\n",
+ num_signals_sent, num_signals_arrived, num_mutations);
+
+ exit (0);
+
+ /*NOTREACHED*/
+}
+
+/* This thread repeatedly adds and removes objects from the list. */
+static void *
+mutator_thread (void *arg)
+{
+ if (test != 1)
+ block_sigint ();
+
+ gl_list_t list2 = (gl_list_t) arg;
+
+ for (num_mutations = 0; ; num_mutations++)
+ {
+ unsigned int operation = RANDOM (2);
+ switch (operation)
+ {
+ case 0: /* Add an element. */
+ {
+ const void *obj = RANDOM_OBJECT ();
+ ASSERT (gl_list_nx_add_first (list2, obj) != NULL);
+ store_change ((uintptr_t) obj, list2);
+ ASSERT (gl_list_nx_add_first (list1, obj) != NULL);
+ }
+ break;
+ case 1: /* Remove an element. */
+ if (gl_list_size (list2) > 0)
+ {
+ size_t index = RANDOM (gl_list_size (list2));
+ const void *obj = gl_list_get_at (list2, index);
+ ASSERT (gl_list_remove (list2, obj));
+ store_change ((uintptr_t) obj, list2);
+ ASSERT (gl_list_remove (list1, obj));
+ }
+ break;
+ }
+ }
+
+ /*NOTREACHED*/
+}
+
+int
+main (int argc, char *argv[])
+{
+ test = atoi (argv[1]);
+
+ /* Allow the user to provide a non-default random seed on the command line.
*/
+ if (argc > 2)
+ srand (atoi (argv[2]));
+
+ gl_list_t list2;
+ /* Initialize list1 and list2. */
+ {
+ size_t initial_size = RANDOM (50);
+ const void **contents =
+ (const void **) malloc (initial_size * sizeof (const void *));
+ size_t i;
+
+ for (i = 0; i < initial_size; i++)
+ contents[i] = RANDOM_OBJECT ();
+
+ list1 = gl_list_nx_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
+ ASSERT (list1 != NULL);
+ for (i = 0; i < initial_size; i++)
+ ASSERT (gl_list_nx_add_first (list1, contents[i]) != NULL);
+
+ list2 = gl_list_nx_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
+ ASSERT (list2 != NULL);
+ for (i = 0; i < initial_size; i++)
+ ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
+
+ recent_oldest_index = 0;
+ recent_bags[0] = bag_from_list (list2);
+ recent_newest_index = 0;
+ }
+
+ /* Install the signal handler.
+ It needs to be done with sigaction(), not signal(), otherwise on Solaris
+ and AIX the program crashes at the second incoming MY_SIGNAL. */
+ #if 0
+ signal (MY_SIGNAL, sigint_handler);
+ #else
+ {
+ struct sigaction action;
+ action.sa_handler = sigint_handler;
+ action.sa_flags = SA_RESTART | SA_NODEFER;
+ sigemptyset (&action.sa_mask);
+ ASSERT (sigaction (MY_SIGNAL, &action, NULL) == 0);
+ }
+ #endif
+
+ /* Launch the threads. */
+ switch (test)
+ {
+ case 1:
+ {
+ signal_target = gl_thread_create (mutator_thread, list2);
+ signal_sending_thread (NULL);
+ abort ();
+ }
+
+ case 2:
+ {
+ signal_target = gl_thread_create (idle_thread, NULL);
+ gl_thread_create (mutator_thread, list2);
+ signal_sending_thread (NULL);
+ abort ();
+ }
+
+ case 3:
+ {
+ gl_thread_create (mutator_thread, list2);
+ signal_target = gl_thread_self (); signal_sending_thread (NULL);
+ abort ();
+ }
+
+ default:
+ ASSERT (false);
+ }
+}
+
+# else
+
+# include <stdio.h>
+
+int
+main ()
+{
+ fputs ("Skipping test: POSIX compatible multithreading not enabled\n",
stderr);
+ return 77;
+}
+
+# endif
+
+#else
+
+# include <stdio.h>
+
+int
+main ()
+{
+ fputs ("Skipping test: signal-safety of linked lists is not enabled\n",
stderr);
+ return 77;
+}
+
+#endif
diff --git a/tests/test-asyncsafe-linked_list.sh
b/tests/test-asyncsafe-linked_list-weak.sh
similarity index 55%
rename from tests/test-asyncsafe-linked_list.sh
rename to tests/test-asyncsafe-linked_list-weak.sh
index c2ad176..73f15eb 100755
--- a/tests/test-asyncsafe-linked_list.sh
+++ b/tests/test-asyncsafe-linked_list-weak.sh
@@ -2,14 +2,14 @@
st=0
for i in 1 2 3 ; do
- ${CHECKER} ./test-asyncsafe-linked_list${EXEEXT} $i
+ ${CHECKER} ./test-asyncsafe-linked_list-weak${EXEEXT} $i
result=$?
if test $result = 77; then
st=77
break
fi
if test $result != 0; then
- echo test-asyncsafe-linked_list.sh: test case $i failed >&2
+ echo "test-asyncsafe-linked_list-weak.sh: test case $i failed" >&2
st=1
fi
done