linux-kernel - Re: [PATCH RFC] sched: introduce add_wait_queue_exclusive

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: <20140318133331.GA23193@laptop.programming.kicks-ass.net>
Date:	Tue, 18 Mar 2014 14:33:31 +0100
From:	Peter Zijlstra <peterz@...radead.org>
To:	Peng Tao <bergwolf@...il.com>
Cc:	linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...hat.com>,
	Oleg Drokin <oleg.drokin@...el.com>,
	Andreas Dilger <andreas.dilger@...el.com>,
	Oleg Nesterov <oleg@...hat.com>
Subject: Re: [PATCH RFC] sched: introduce add_wait_queue_exclusive_head

On Tue, Mar 18, 2014 at 09:10:08PM +0800, Peng Tao wrote:
> Normally wait_queue_t is a FIFO list for exclusive waiting tasks.
> As a side effect, if there are many threads waiting on the same
> condition (which is common for data servers like Lustre), all
> threads will be waken up again and again, causing unnecessary cache
> line polution. Instead of FIFO lists, we can use LIFO lists to always
> wake up the most recent active threads.
> 
> Lustre implements this add_wait_queue_exclusive_head() privately but we
> think it might be useful as a generic function. With it being moved to
> generic layer, the rest of Lustre private wrappers for wait queue can be
> all removed.
> 
> Of course there is an alternative approach to just open code it but we'd
> like to ask first to see if there is objection to making it generic.

OK, so I don't particularly mind LIFO, but there are a few problems with
the patch.

Firstly I think the _head postfix for LIFO is a bad name, and secondly,
and most important, this breaks __wake_up_common().

So waitqueue wakeups are specified as waking all !exclusive tasks and @n
exclusive tasks. The way this works is that !exclusive tasks are added
to the head (LIFO) and exclusive tasks are added to the tail
(FIFO).

We can then iterate the list until @n exclusive tasks have been
observed.

However if you start adding exclusive tasks to the head this all comes
apart.

If you don't mix exclusive and !exclusive tasks on the same waitqueue
this isn't a problem, but I'm sure people will eventually do this and
get a nasty surprise.

I'm not sure what the best way around this would be; but I can see two
options:

 - add enough debugging bits to detect this fail case.
 - extend wait_queue_head_t to keep a pointer to the first !exclusive
   element and insert exclusive LIFO tasks there -- thereby keeping
   !exclusive tasks at the front.

Anybody?
--
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/