linux-kernel - futex: wakeup race and futex

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-next>] [day] [month] [year] [list]

Message-ID: <4AB17A08.50008@us.ibm.com>
Date:	Wed, 16 Sep 2009 16:51:36 -0700
From:	Darren Hart <dvhltc@...ibm.com>
To:	"lkml, " <linux-kernel@...r.kernel.org>
CC:	Thomas Gleixner <tglx@...utronix.de>,
	Peter Zijlstra <peterz@...radead.org>,
	Steven Rostedt <rostedt@...dmis.org>,
	Ingo Molnar <mingo@...e.hu>,
	Eric Dumazet <eric.dumazet@...il.com>,
	Dinakar Guniguntala <dino@...ibm.com>,
	John Stultz <johnstul@...ibm.com>
Subject: futex: wakeup race and futex_q woken state definition

I'm working on futex commentary cleanup patch series.  While reading
through all the remaining comments, I've come across a couple I'd your
thoughts on:

The futex woken state is defined as:

 * A futex_q has a woken state, just like tasks have TASK_RUNNING.
 * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0.
 * The order of wakup is always to make the first condition true, then
 * wake up q->waiter, then make the second condition true.

1) wake_futex() actually wakes the task (q->task not q->waiter) after
   the lock_ptr has been set to NULL. I believe this is fine and can
   correct the comments accordingly.

2) futex_wait_queue_me() (recently refactored from futex_wait())
   performs the following test:

	/*
	 * !plist_node_empty() is safe here without any lock.
	 * q.lock_ptr != 0 is not safe, because of ordering against wakeup.
	 */
	if (likely(!plist_node_empty(&q->list))) {
		/*
		 * If the timer has already expired, current will already be
		 * flagged for rescheduling. Only call schedule if there
		 * is no timeout, or if it has yet to expire.
		 */
		if (!timeout || timeout->task)
			schedule();
	}

As I understand it, this is to avoid a missed wakeup when a FUTEX_WAKE
call occurs after the queue_me() but before the futex_wait() call has
had a chance to call schedule() (via futex_wait_queue_me()).  However,
as no locks are taken, I don't see what prevents the futex_q from being
removed from the hash list after the plist_node_empty() test and before
the call to schedule().  In this scenario, the futex_q will not be found
on the hash list by subsequent wakers, and it will remain in schedule()
until a timeout or signal occurs.

This leads me to the question on the comment: "!plist_node_empty() is
safe here without any lock." - Why is that safe?

Secondly, why is the q.lock_ptr test not safe? "q.lock_ptr != 0 is not
safe, because of ordering against wakeup."

I understand the definition of the woken state to be
"plist_node_empty(&q->list) || q->lock_ptr == 0".  So testing the plist
will detect a woken futex sooner than testing for a null lock_ptr, but I
don't see how one is more "safe" than the other when no locks are held
to prevent the futex_q from vanishing off the list before the call to
schedule().

Thanks,

-- 
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team
--
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/