linux-kernel - Re: [PATCH v3 4/4] futex: Avoid taking hb lock if nothing to wakeup

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: <CA+55aFyrZmG6rNpY22OK3UQi18e=4UQyh8a3tpxY+QVCbNxXkw@mail.gmail.com>
Date:	Thu, 19 Dec 2013 19:13:09 -0800
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Davidlohr Bueso <davidlohr@...com>
Cc:	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Ingo Molnar <mingo@...hat.com>,
	Darren Hart <dvhart@...ux.intel.com>,
	Peter Zijlstra <peterz@...radead.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Paul McKenney <paulmck@...ux.vnet.ibm.com>,
	Mike Galbraith <efault@....de>, Jeff Mahoney <jeffm@...e.com>,
	Jason Low <jason.low2@...com>,
	Waiman Long <Waiman.Long@...com>, Tom Vaden <tom.vaden@...com>,
	"Norton, Scott J" <scott.norton@...com>,
	"Chandramouleeswaran, Aswin" <aswin@...com>,
	Ingo Molnar <mingo@...nel.org>
Subject: Re: [PATCH v3 4/4] futex: Avoid taking hb lock if nothing to wakeup

On Thu, Dec 19, 2013 at 6:22 PM, Davidlohr Bueso <davidlohr@...com> wrote:
>
> Ok so when I replied I was thinking about the plist really and not the
> hb->lock ticket counter. Yeah, what you propose does make sense for
> waiters. However in wake paths we have to decrement  the counter nwake
> times (per each call to __unqueue_futex()), and if we rely on the
> ticket, then we do it only once, in the unlock, so the counter doesn't
> reflect the actual waitqueue size. Or am I missing something with ticket
> spinlocks (I'm not very familiar with that code)?

So that's why I suggested checking the ticket lock _and_ the state of
the node list.

The ticket lock state gives you the racy window before the entry has
actually been added to the node list, and then after the lock has been
released, the fact that the list isn't empty gives you the rest.

I think we might have to order the two reads with an smp_rmb - making
sure that we check the lock state first - but I think it should be
otherwise pretty solid.

And maybe there is some reason it doesn't work, but I'd really like to
understand it (and I'd like to avoid the extra atomics for the waiters
count if it at all can be avoided)

> Btw, I tried using spin_is_contended + plist_head_empty and we run into
> a whole bunch of nasty issues which I have yet to sit down and look
> into.

Yeah, I said "spin_contended()" myself initially, but it needs to be
"spin_is_locked()". It's hopefully unlikely to ever actually be
contended (which in ticket lock terms is "head is _more_ than one away
from the tail").

            Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/