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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAPNVh5fH49Ehh2xNqcEVgK46KTWV6xz9BMw40BW-rzj=-Y2YLA@mail.gmail.com>
Date:   Fri, 9 Jul 2021 10:33:51 -0700
From:   Peter Oskolkov <posk@...gle.com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     Peter Oskolkov <posk@...k.io>, Ingo Molnar <mingo@...hat.com>,
        Thomas Gleixner <tglx@...utronix.de>,
        linux-kernel@...r.kernel.org, linux-api@...r.kernel.org,
        Paul Turner <pjt@...gle.com>, Ben Segall <bsegall@...gle.com>,
        Joel Fernandes <joel@...lfernandes.org>,
        Andrei Vagin <avagin@...gle.com>,
        Jim Newsome <jnewsome@...project.org>,
        Jann Horn <jannh@...gle.com>
Subject: 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 <posk@...gle.com> wrote:
>
> On Fri, Jul 9, 2021 at 1:02 AM Peter Zijlstra <peterz@...radead.org> wrote:
> >
[...]

> > 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. :)

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

[...]