Re: data structures for use in signal handlers

[Eric Wong]

Bruno Haible <bruno@clisp.org> wrote:
> 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:

>     (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?

Maybe, it sounds like RCU as Ben mentioned.  I've never used RCU
inside signal handlers, though.

>         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.

liburcu uses intrusive data structures (via container_of) like
the Linux kernel does, so memory can be pre-allocated at startup
before a signal handler runs.

>     (3) Use lock-free algorithms. What lock-free algorithms can you propose?
>         What I want is
>           (a) a list,

I haven't used it for signal handlers, but wfcqueue from liburcu
might be a possibility, here.

>           (b) a balanced binary tree,

That seems way tricky.  I've never gone beyond atomic ops (xchg,
cmpxchg, add/sub/or, etc...) and the usual pipe/eventfd/socket
stuff.

>         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.

I would've recommended just using a pipe, socket or eventfd;
but I guess that's not an option for your particular structure
or libsigsegv?