data structures for use in signal handlers

[Bruno Haible]

Hi Marc, Ben,

I need your expertise regarding data structures.

Assume a program has a signal handler, which needs to share some data
structure with the rest of the program.

There are two cases:

(A) Assume that the program is single-threaded.
    Then it is sufficient to use 'volatile' variables for communication
    between the handler and the rest of the program.

(B) Assume that the program is multi-threaded.
    Then 'volatile' is not sufficient, because the signal handler and some
    other threads may be running at the same time.

    As far as I can see, there are three possibilities to write such a
    signal handler:

    (1) Use the 'asyncsafe-spin' lock module from gnulib, and block the
        relevant signals while manipulating the data structures in the
        other code. (Blocking the signals is needed, because otherwise
        the thread might, while manipulating said data structures, be
        interrupted by the signal *in the same thread*, and then no
        spin lock and no waiting can help.)

        This is the approach taken in gnulib/lib/clean-temp.c.

    (2) Let the signal handler work only on immutable copies of the data
        structure. Whenever the other code manipulates the data structure,
        it creates an immutable copy of it, for the signal handler to use.
        Use an 'asyncsafe-spin' lock through which the signal handler tells
        the other threads to not free that immutable copy while it running.

        This is tricky; can it actually be made to work?

        Btw, there is an obvious requirement: the technique should use malloc/
        free for memory management, and should not have memory leaks.
        Algorithms that assume a garbage collected memory management are not
        suitable here.

    (3) Use lock-free algorithms. What lock-free algorithms can you propose?
        What I want is
          (a) a list,
          (b) a balanced binary tree,
        and the other code can malloc/free/add/insert in the data structure,
        whereas the signal handler should only be allowed to iterate and
        search an element within the data structure.

        What algorithms can you recommend for this purpose?

This would be useful for gnulib in general. The balanced binary tree would
also help making GNU libsigsegv multithread-safe.

Bruno