> The helpers below can work with userspace single-linked lists
concurrently
> without indefinitely spinning in the kernel. Specifically:
>
> push (add to the head of the list):
>
> step = 0
> while (++step < N)
> old = *head
> *next = old
> cmp_xchng(head, &old, next)
>
> pop (remove the first element from the list):
> mark the node as deleted by flipping its lowest bit without
> actually removing the node from the list:
>
> curr = *head
> step = 0
>
> while (curr && ++step < N)
>
> next = *curr
> if (next & 1)
> curr = next & ~1
> continue
>
> if (cmp_xchng(curr, next, next | 1))
> return curr
> else
> curr = next & ~1
>
> It is the userspace's responsibility to actually remove the
> nodes marked as deleted from the list.
I believe the subsystem called Nemesis introduced a MCS-based queue that
could
be useful here. The original paper is https://doi.org/10.1109/CCGRID.2006.31
You can also look at this repo for an implementation of the queue.
https://git.uwaterloo.ca/mkarsten/libfibre/-/blob/master/src/runtime/LockFreeQueues.h
While it uses 2 pointers, I believe it would fit well for idle_workers_ptr
since the push operation is wait-free, which avoids problems for the kernel.
The pop operation requires a lock in userspace *if* multiple servers can
consume from the same queue, but I don't believe it's a requirement in
general.
