linux-kernel - Re: [PATCH v2 1/2] sched/wait: Add add_wait_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]

Message-ID: <220a7b090d27ffc8f3d00253c289ddd964a8462b.camel@infradead.org>
Date:   Tue, 27 Oct 2020 19:27:59 +0000
From:   David Woodhouse <dwmw2@...radead.org>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...hat.com>,
        Juri Lelli <juri.lelli@...hat.com>,
        Vincent Guittot <vincent.guittot@...aro.org>,
        Dietmar Eggemann <dietmar.eggemann@....com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Ben Segall <bsegall@...gle.com>, Mel Gorman <mgorman@...e.de>,
        Daniel Bristot de Oliveira <bristot@...hat.com>,
        Paolo Bonzini <pbonzini@...hat.com>, kvm@...r.kernel.org,
        Oleg Nesterov <oleg@...hat.com>
Subject: Re: [PATCH v2 1/2] sched/wait: Add add_wait_queue_priority()

On Tue, 2020-10-27 at 20:09 +0100, Peter Zijlstra wrote:
> On Tue, Oct 27, 2020 at 02:39:43PM +0000, David Woodhouse wrote:
> > From: David Woodhouse <dwmw@...zon.co.uk>
> > 
> > This allows an exclusive wait_queue_entry to be added at the head of the
> > queue, instead of the tail as normal. Thus, it gets to consume events
> > first without allowing non-exclusive waiters to be woken at all.
> > 
> > The (first) intended use is for KVM IRQFD, which currently has
> 
> Do you have more? You could easily special case this inside the KVM
> code.

I don't have more right now. What is the easy special case that you
see?

> I don't _think_ the other users of __add_wait_queue() will mind the
> extra branch, but what do I know.

I suppose we could add an unlikely() in there. It seemed like premature
optimisation.

> >  static inline void __add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
> >  {
> > -	list_add(&wq_entry->entry, &wq_head->head);
> > +	struct list_head *head = &wq_head->head;
> > +	struct wait_queue_entry *wq;
> > +
> > +	list_for_each_entry(wq, &wq_head->head, entry) {
> > +		if (!(wq->flags & WQ_FLAG_PRIORITY))
> > +			break;
> > +		head = &wq->entry;
> > +	}
> > +	list_add(&wq_entry->entry, head);
> >  }
> 
> So you're adding the PRIORITY things to the head of the list and need
> the PRIORITY flag to keep them in FIFO order there, right?

No, I don't care about the order of priority entries; there will
typically be only one of them; that's the point. (I'd have used the
word 'exclusive' if that wasn't already in use for something that...
well... isn't.)

I only case that the priority entries come *before* the bog-standard
non-exclusive entries (like ep_poll_callback).

The priority items end up getting added in FIFO order purely by chance,
because it was simpler to use the same insertion flow for both priority
and normal non-exclusive entries instead of making a new case. So they
all get inserted behind any existing priority entries.

> While looking at this I found that weird __add_wait_queue_exclusive()
> which is used by fs/eventpoll.c and does something similar, except it
> doesn't keep the FIFO order.

It does, doesn't it? Except those so-called "exclusive" entries end up
in FIFO order amongst themselves at the *tail* of the queue, to be
woken up only after all the other entries before them *haven't* been
excluded.

> The Changelog doesn't state how important this property is to you.

Because it isn't :)

The ordering is:

 { PRIORITY }*  { NON-EXCLUSIVE }* { EXCLUSIVE(sic) }*

I care that PRIORITY comes before the others, because I want to
actually exclude the others. Especially the "non-exclusive" ones, which
the 'exclusive' ones don't actually exclude.

I absolutely don't care about ordering *within* the set of PRIORITY
entries, since as I said I expect there to be only one.

Download attachment "smime.p7s" of type "application/x-pkcs7-signature" (5174 bytes)