On 08/29, George Spelvin wrote: > > Oleg Nesterov wrote: > > On 08/29, Ingo Molnar wrote: > >> So I'm wondering, is there any strong reason why we couldn't use a double > >> linked list and still do FIFO and remove that silly linear list walking > >> hack? > > > > This will obviously enlarge callback_head, and it is often embedded. > > But this is minor. > > > > If we use a double linked list we can't do task_work_add() lockless. > > So we will need another spinlock_t in task_struct. We can't use pi_lock. > > You only need a singly linked list for FIFO, but indeed lockless > access is a pain. > > For a LIFO stack, you just do a single compare-and-swap on the head. > Once an entry is in the list, it's immutable. > > For FIFO, you only need one pointer in the nodes, but two in the list > head: a head pointer and a tail pointer.
Actually you need a single tail pointer, See 158e1645e07f3e9f7e49. But this doesn't matter. > The problem for lockless access is that you have to update both the next > pointer and the tail pointer, and without very specialized instructions > like 680x0's CAS2, there's no way to do them both atomically. > > So the procedure to append (write) to the list is: > ... > - But also, there's a sort of priority inversion problem. If a writer > stalls here, no following writer is visible to the reader. And this also means that the next writer which does task_work_add() + task_work_cancel() will be suprised. Worse, this means that work->func() doesn't own its callback_head/container_of. The previous tail is visible to task_work_run(). Perhaps I missed something. But to me this all looks too clever ;) Personally I'd prefer to just add another spinlock_t. But so far I hope we can keep this stupid but simple "reverse the list" loop. Oleg. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
