On Dec 5 13:46, Takashi Yano wrote: > On Wed, 4 Dec 2024 13:53:14 +0100 > Corinna Vinschen wrote: > > On Dec 4 20:41, Takashi Yano wrote: > > > Currently, the signal queue is touched by the thread sig as well as > > > other threads that call sigaction_worker(). This potentially has > > > a possibility to destroy the signal queue chain. A possible worst > > > result may be a self-loop chain which causes infinite loop. With > > > this patch, lock()/unlock() are introduce to avoid such a situation. > > > > I was hoping for a lockfree solution, but never mind that for now. > > I cannot imagine how the lockfree can be realized. > Consider the queue chain: > A->B->C->D > A<-B<-C<-D > where "->" shows next link and "<-" shows prev link. > Assume a thread tries to clear B, and another thread tries to clear C. > Two processes, i.e. > clear(B) > B->prev->next = B->next > B->next->prev = B->prev > and > clear(C) > C->prev->next = C->next > C->next->prev = C->prev > are running at the same time. Even if each line is executed atomically, > the next case is not avoidable. > > clear(B) clear(C) > B->prev->next = B->next A->next > = C > C->prev->next = C->next B->next = D > B->next->prev = B->prev D->prev > = A > C->next->prev = C->prev D->prev = B > > Then, the result is broken as: > A->C->D > A<-B<-D > B->D > B<-C > while expected result is: > A->D > A<-D > > Is there any way to execute atomically two lines: > B->prev->next = B->next > B->next->prev = B->prev > using Interlocked* functions?
It is possible, apparently. There's a university presentation with a nice overview how to do this with a CAS primitive (e. g. InterlockedCompareExchange): https://www.cse.chalmers.se/~tsigas/papers/SLIDES/Lock-Free%20Doubly%20Linked%20Lists%20and%20Deques.pdf Admittedly, I never tried it myself. So, never mind that for now. It might be a fun side-project, though. Corinna
