# Does a reentrant list for signal queue in a single-thread environment exist?

I need to handle Unix signals in a single-threaded application with the following goals:

1. Signals doesn't mask on receive (thus, the signal handler must be reentrant).
2. I am not allowed to lose signal data (thus, if a new signal comes before the handler of the previous returned, it also must be handled correctly).

I have the common multi-threaded primitives (spinlocks, semaphores, etc). But they doesn't seem enough, because my higher-level data structures (even a such simple as a list) aren't thread-safe.

My initial idea was the following:

1. I use a list, in which I store the data of the incoming signal fast,
2. and process them (call the possibily much slower running handlers) later, out of the critical section.

The main problem with that, that the list data structure isn't thread safe. If I lock it, I can't store a second signal anywhere. I can't wait until the previous handler exits, because on the second signal it is essentially suspended in a critical section.

Simply I don't have any idea, how to handle the following scenario:

1. signal1 comes, the process suspends, and the handler of signal1 starts
2. signal2 comes, the handler of signal1 suspends, and the handler of signal2 starts
3. Handler of signal2 returns, execution returns to the handler signal1
4. Handler of signal1 returns, execution returns to the main program.

After thinking a lot on it, I have an impression, maybe my problem is unsolvable. Am I right? How do operating systems handle similar problems (for example, possibily bursting interrupts from hardware)?

• @JustAnotherSoul I won't guarantee there aren't more signals delivered at once as many threads I have. And my current app is single-threaded, but it has to handle signals very well (i.e. no signal can be lost). – peterh says reinstate Monica Sep 1 '15 at 20:55
• What I mean is, why not just spin off a thread to add the signal data to the data structure. I.E. Signal 1 comes in, thread to add the data to the list is created. ... Signal n comes in, thread to add the data to the list is created. I'm also assuming you can't simply spin off a thread to handle each signal for some reason. – JustAnotherSoul Sep 1 '15 at 20:56
• Off-topic note: your architecture will lose signal data: if two signals are delivered to your application at almost the same time, they will be conflated, and your process will only receive one. On-topic note: pretty much any synchronization primitive does two things — test-and-set, clear-and-mask-interrupt (a.k.a. start signal handler and mask signal), test-for-input-and-block, ... – Gilles 'SO- stop being evil' Sep 1 '15 at 21:01
• @JustAnotherSoul Good assumption, although your solution looks fine. – peterh says reinstate Monica Sep 1 '15 at 21:01

Finally I found a solution, which handles the whole problem at once. It is relatively easy. They key to the solution: we can use the signal stack as a "to-do stack".

Important to remember, that although this problem is also about race condition eliminiation, its solution differs significantly from the "lock everything what you use, do your task, release everything" solutions. It is because it is not about parallelisation, it is about reentrancy. The common lock-based solutions would lead to deadlock here, because the parent (in the example) signal1 handler will be surely suspended while the whole execution of the handler of signal2.

So, this is a disadvantage, but it is an advantage as well. We can guarantee, that signal1 won't do anything while our signal2 runs. We can't simply lock things, but we also don't need to do them.

So, that blocking locks are closed out, only the nonblocking locks left. What I invented, is the following C code:

#define STORE(a, b) __atomic_store(&(a), &(b), __ATOMIC_SEQ_CST)
#define SWAP(a, b) __atomic_exchange(&(a), &(b), &(b), __ATOMIC_SEQ_CST)

// action handler wrapper
void ss_wrapper(int signum, siginfo_t* siginfo, ucontext_t* ucontext) {
// currently top element on the signal stack
static struct ss_hit *top = NULL;

struct ss_hit *hit = ss_hit_new(signum, siginfo, ucontext);
struct ss_hit *bkp;

again:

bkp = hit;
SWAP(top, hit);
if (!hit) { // we got the lock, we are the master
ss_fire(bkp);
SWAP(top, &bkp->next); // release the lock, find out if there is new element
if (bkp->nxt) { // there IS

hit = bkp;
free(bkp);
goto again;

} else
free(bkp);
} else { // we didn't got the lock, but we got the top in hit
STORE(hit->next, bkp);
}
}


As we can see, it had been very beautiful to have a separated, reentrant stack (and not list) data structure.

The main problem was to understood, that

• adding new element in the stack, AND testing if it is empty, they should be done in a single atomic operation (this is why top serves as both of spinlock and pointer to the top of the stack)
• similarly, removing element from the stack, and to know, if it is now empty, should be done also atomically.

I also learned from this some days of thinking, that * constructing reentrant algorithm is much harder as to contrust a multithread * the most important thing is that reentrant algos should have only very few variables to interact eachother through them, and all operation should be atomic on them.