linux-kernel - Re: [RFC][PATCH 6/7] freelist: Lock less freelist

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]

Date:   Fri, 28 Aug 2020 23:05:20 -0400
From:   Cameron <cameron@...dycamel.com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     Oleg Nesterov <oleg@...hat.com>, linux-kernel@...r.kernel.org,
        Masami Hiramatsu <mhiramat@...nel.org>, Eddy_Wu@...ndmicro.com,
        x86@...nel.org, davem@...emloft.net, rostedt@...dmis.org,
        naveen.n.rao@...ux.ibm.com, anil.s.keshavamurthy@...el.com,
        linux-arch@...r.kernel.org, will@...nel.org, paulmck@...nel.org
Subject: Re: [RFC][PATCH 6/7] freelist: Lock less freelist

> I'm curious whether it is correct to just set the prev->refs to zero and return
> @prev? So that it can remove an unneeded "add()&get()" pair (although in
> an unlikely branch) and __freelist_add() can be folded into freelist_add()
> for tidier code.

That is a very good question. I believe it would be correct, yes, and
would certainly simplify the code. The reference count is zero, so
nobody can increment it again, and REFS_ON_FREELIST is set (the
should-be-on-freelist flag), so instead of adding it to the freelist
to be removed later, it can be returned directly.

> On Fri, Aug 28, 2020 at 04:46:52PM +0200, Oleg Nesterov wrote:
> > 129 lines! And I spent more than 2 hours trying to understand these
> > 129 lines ;) looks correct...

Hahaha. Sorry about that. Some of the most mind-bending code I've ever
written. :-)

> > +                     /*
> > +                      * Hmm, the add failed, but we can only try again when
> > +                      * the refcount goes back to zero.
> > +                      */
> > +                     if (atomic_fetch_add_release(REFS_ON_FREELIST - 1, &node->refs) == 1)
> > +                             continue;
> Do we really need _release ? Why can't atomic_fetch_add_relaxed() work?

The release is to synchronize with the acquire in the compare-exchange
of try_get. However, I think you're right, between the previous
release-write to the refs and that point, there are no memory effects
that need to be synchronized, and so it could be safely replaced with
a relaxed operation.

> Cosmetic, but why not atomic_fetch_dec() ?

This is just one of my idiosyncrasies. I prefer exclusively using
atomic add, I find it easier to read. Feel free to change them all to
subs!

Cameron


> >
> > Do we the barriers implied by _fetch_? Why can't atomic_sub(2, refs) work?
>
> I think we can, the original has std::memory_order_relaxed here. So I
> should've used atomic_fetch_add_relaxed() but since we don't use the
> return value, atomic_sub() would work just fine too.
>
> > > +           /*
> > > +            * OK, the head must have changed on us, but we still need to decrement
> > > +            * the refcount we increased.
> > > +            */
> > > +           refs = atomic_fetch_add(-1, &prev->refs);
> >
> > Cosmetic, but why not atomic_fetch_dec() ?
>
> The original had that, I didn't want to risk more bugs by 'improving'
> things. But yes, that can definitely become dec().