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

Question

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

Answer 1

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.