linux-kernel - Re: [RFC] sched: implement the exclusive wait queue as a LIFO queue

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:	Wed, 28 Apr 2010 14:21:35 +0100
From:	Jamie Lokier <jamie@...reable.org>
To:	Changli Gao <xiaosuo@...il.com>
Cc:	David Howells <dhowells@...hat.com>,
	Yong Zhang <yong.zhang@...driver.com>,
	Xiaotian Feng <xtfeng@...il.com>, Ingo Molnar <mingo@...e.hu>,
	Alexander Viro <viro@...iv.linux.org.uk>,
	Andrew Morton <akpm@...ux-foundation.org>,
	"Eric W. Biederman" <ebiederm@...ssion.com>,
	Davide Libenzi <davidel@...ilserver.org>,
	Roland Dreier <rolandd@...co.com>,
	Stefan Richter <stefanr@...6.in-berlin.de>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	"David S. Miller" <davem@...emloft.net>,
	Eric Dumazet <dada1@...mosbay.com>,
	Christoph Lameter <cl@...ux.com>,
	Andreas Herrmann <andreas.herrmann3@....com>,
	Thomas Gleixner <tglx@...utronix.de>,
	Takashi Iwai <tiwai@...e.de>, linux-fsdevel@...r.kernel.org,
	linux-kernel@...r.kernel.org
Subject: Re: [RFC] sched: implement the exclusive wait queue as a LIFO queue

Changli Gao wrote:
> On Wed, Apr 28, 2010 at 5:29 PM, David Howells <dhowells@...hat.com> wrote:
> > Changli Gao <xiaosuo@...il.com> wrote:
> >
> >> If there isn't enough work to be done, we'd better not disrupt them
> >> and  leave them sleeping forever to keep the scheduler happier. Do we
> >> have reason to keep fair to all the workers? Does it have benefit?
> >
> > You've made one important assumption: the processes on the wait queue are
> > sleeping waiting to service things... but what if the wait queue governs
> > access to a resource, and all the processes on that wait queue need access to
> > that resource to do things?  Some of the processes waiting for it may never
> > get a go, and so necessary work may be left undone.
> >
> 
> You are right. I made the wrong assumption. But we indeed need some
> primitive to add wait_queue at the head of the wait_queue_head, and I
> know epoll needs it, at least.
> 
> fs/eventpoll.c: 1443.
>                 wait.flags |= WQ_FLAG_EXCLUSIVE;
>                 __add_wait_queue(&ep->wq, &wait);

The same thing about assumptions applies here.  The userspace process
may be waiting for an epoll condition to get access to a resource,
rather than being a worker thread interchangeable with others.

For example, userspace might be using a pipe as a signal-safe lock, or
signal-safe multi-token semaphore, and epoll to wait for that pipe.

WQ_FLAG_EXCLUSIVE means there is no point waking all tasks, to avoid a
pointless thundering herd.  It doesn't mean unfairness is ok.

The LIFO idea _might_ make sense for interchangeable worker-thread
situations - including userspace.  It would make sense for pipe
waiters, socket waiters (especially accept), etc.

Do you have any measurements which showing the LIFO mode performing
better than FIFO, and by how much?

-- Jamie
--
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/