Bruno Haible <br...@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?