Re: [RFC PATCH 2/3 v0.2] sched/umcg: RFC: add userspace atomic helpers

On Fri, Jul 9, 2021 at 9:57 AM Peter Oskolkov [off-list ref] wrote:

On Fri, Jul 9, 2021 at 1:02 AM Peter Zijlstra [off-list ref] wrote:

quoted

[...]

quoted

What's wrong with the trivial lockless single
linked list approach?.

I'm not sure how to get around the ABA problem with a lockless single
linked list: https://en.wikipedia.org/wiki/ABA_problem

Our semantics can probably be relied on to prevent ABA from happening
with idle workers (popped/removed by the userspace), but idle servers
can trivially have it:

(initial state): head => Server A => Server B => NULL

task1 :
- read head (get A), read A (get B), {/* delayed */}

tasks 2-3-4:
- pop A, pop B, push A

task 1:
- cmp_xchg(head, A /* old */, B /* new */) - succeeds, now B is in the
list erroneously

I think the kernel can just mark "popped" servers as such (by setting
the lowest bit of its "next" pointer to one) without actually removing
them from the list, and letting the userspace do the cleanup/GC. With
hard-limiting the max length of idle servers at 2*NUM_CPUs or similar,
this may work out OK. I'll work on this approach. Please have a look
at patch 3. :)

quoted

On top of that, you really want to avoid all that endless stac/clac
nonsense and only have that once, at the outer edges of things.

Something like the *completely* untested below (except it needs lots of
extra gunk to support compilers without asm-goto-output, and more widths
and ...

I'll try the approach you suggest below once it is clear how to deal
with the ABA issue (and the wake server issue raised in patch 3).

[...]