sched: introduce add_wait_queue_exclusive_head

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.

Quoted 12 lines · Peng Tao

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.

Quoted 2 lines

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.

Quoted 1 line

Firstly I think the _head postfix for LIFO is a bad name,

Do you have any preference on the name? add_wait_queue_exclusive_lifo()?

Quoted 4 lines

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.

Yes, Lustre takes care not to mix exclusive and !exclusive tasks in this case.

Quoted 5 lines

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

Quoted 3 lines

element and insert exclusive LIFO tasks there -- thereby keeping !exclusive tasks at the front.

Thank you for the suggestions. Personally I am in favor of the second one but I'll wait others to comment first.

Quoted 2 lines · Peng Tao

Quoted 1 line

Firstly I think the _head postfix for LIFO is a bad name,

Do you have any preference on the name? add_wait_queue_exclusive_lifo()?

I think we can avoid the entire function if we add WQ_FLAG_LIFO and make prepare_to_wait_event() DTRT.

Then we only need to teach ___wait() about this; and I suppose we could make .exclusive=-1 be the LIFO flag.

Unless you cannot use ___wait() and really need to open-code the wait_event() stuff.

Quoted 5 lines

Quoted 4 lines

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.

Yes, Lustre takes care not to mix exclusive and !exclusive tasks in this case.

Right; I saw you had a comment to that effect after I wrote this email.

Quoted 5 lines

Quoted 5 lines

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

s/!//

Quoted 5 lines

Quoted 3 lines

element and insert exclusive LIFO tasks there -- thereby keeping !exclusive tasks at the front.

Thank you for the suggestions. Personally I am in favor of the second one but I'll wait others to comment first.

Oleg, Ingo, any preferences?

Quoted 4 lines · Peter Zijlstra

Unless you cannot use ___wait() and really need to open-code the wait_event() stuff.

Lustre's private l_wait_event() stuff takes care to (un)mask LUSTRE_FATAL_SIGS

and always wait in TASK_INTERRUPTIBLE state.

It looks to me that we can at least wrap l_wait_event() on top of wait_event_interruptible/wait_event_timeout_interruptible.

Quoted 6 lines · Peng Tao

Quoted 4 lines · Peter Zijlstra

Unless you cannot use ___wait() and really need to open-code the wait_event() stuff.

Quoted 2 lines

Lustre's private l_wait_event() stuff takes care to (un)mask LUSTRE_FATAL_SIGS

Hmm. This is off-topic but after the quick grep LUSTRE_FATAL_SIGS/etc looks suspicious.

Firtsly, cfs_block_sigs/cfs_block_sigsinv/etc are not exactly right, they need set_current_blocked(). And you can read "old" lockless.

And note that cfs_block_sigsinv(0) (which should block all signals) can't actually protect from SIGKILL (or in fact from another fatal signal) or SIGSTOP if the caller is multithreaded. Or ptrace, or freezer.

Quoted 1 line

and always wait in TASK_INTERRUPTIBLE state.

and it seems that __wstate passed to waitq_wait/waitq_timedwait is simply ignored.

Quoted 2 lines

It looks to me that we can at least wrap l_wait_event() on top of wait_event_interruptible/wait_event_timeout_interruptible.

l_wait_event looks really complicated ;) but perhaps you can rewrite it on top of ___wait_event(), note that condition/cmd can do anything you want.

Quoted 4 lines · Oleg Nesterov

Firtsly, cfs_block_sigs/cfs_block_sigsinv/etc are not exactly right, they need set_current_blocked(). And you can read "old" lockless.

It seems that set_current_blocked() is not exported. Can we ask to export it?

And looking at other similar places like coda_block_signals(),

Quoted 8 lines · Peng Tao

Quoted 4 lines · Oleg Nesterov

Firtsly, cfs_block_sigs/cfs_block_sigsinv/etc are not exactly right, they need set_current_blocked(). And you can read "old" lockless.

It seems that set_current_blocked() is not exported. Can we ask to export it?

Why not. If you are going to change this code to use set_current_blocked(), I'd suggest you to send the "export set_current_blocked" patch in series. Otherwise, if it is sent separately, your change will depend on another tree.

Or you can use sigprocmask(). Actually it should die, but this won't happen soon and it is already exported.

Quoted 1 line

And looking at other similar places like coda_block_signals(),

Yes, it can have much more users.

But note that set_current_blocked() can't help you to really block SIGKILL anyway.

Could you explain why __l_wait_event() can't use TASK_UNINTERRUPTIBLE instead of cfs_block_sigsinv(0) ?

The original reason for l_wait_event() not using TASK_UNINTERRUPTIBLE is to avoid the load on the server continually being "num_service_threads" regardless of whether they are actually doing something or not. We added various cases for periodic wakeups and such afterward.

Quoted 5 lines · Andreas

The original reason for l_wait_event() not using TASK_UNINTERRUPTIBLE is to avoid the load on the server continually being "num_service_threads"
regardless of whether they are actually doing something or not. We added various cases for periodic wakeups and such afterward.

Hmm, maybe we should finally do the TASK_IDLE thing;

https://lkml.org/lkml/2013/11/12/710

Quoted 4 lines · Andreas

The original reason for l_wait_event() not using TASK_UNINTERRUPTIBLE is to avoid the load on the server continually being "num_service_threads" regardless of whether they are actually doing something or not. We added various cases for periodic wakeups and such afterward.

Hmm, maybe we should finally do the TASK_IDLE thing;

https://lkml.org/lkml/2013/11/12/710

I think we can avoid the entire function if we add WQ_FLAG_LIFO and make prepare_to_wait_event() DTRT.

Then we only need to teach ___wait() about this; and I suppose we could make .exclusive=-1 be the LIFO flag.

Quoted 3 lines · Peter Zijlstra

I think we can avoid the entire function if we add WQ_FLAG_LIFO and make prepare_to_wait_event() DTRT.

Agreed, this looks very natural.

prepare_to_wait_event(WQ_FLAG_LIFO) should probably skip all "flags == 0" entries before list_add(). Given that it is supposed that the users won't mix exclusive and !exclusive, perhaps the additional list_for_each() won't hurt?

Quoted 2 lines

Then we only need to teach ___wait() about this; and I suppose we could make .exclusive=-1 be the LIFO flag.

Or we can change ___wait_event()

        -       if (exclusive)                                                  \
        -               __wait.flags = WQ_FLAG_EXCLUSIVE;                       \
        -       else                                                            \
        -               __wait.flags = 0;                                       \
        +       __wait.flags = exclusive;                                       \

and obviously change the callers. Perhaps this argument should be renamed then.

But I am fine either way, just I like the idea to extend the current interface.

Oleg.

Review

Quoted 12 lines · Oleg Nesterov

(quoted diff) +12 -0

+static void add_wait_queue_flag(wait_queue_head_t *q, wait_queue_t *wait)
+{
+	struct list_head *head = &q->task_list;
+	wait_queue_t *excl;
+
+	if (wait->flags & WQ_FLAG_EXCLUSIVE) {
+		if (wait->flags & WQ_FLAG_EXCLUSIVE_HEAD) {
+			list_for_each_entry(excl, head, task_list)
+				if (excl->flags & WQ_FLAG_EXCLUSIVE) {
+					head = &excl->task_list;
+					break;
+				}

I prefer an extra pair of { } here,

but the main concern would be the
cost of that iteration.

Other than that, yes something like that would do I suppose.

OK, I'll try to test/cleanup/resend tomorrow.

Quoted 2 lines · Oleg Nesterov

OK, I'll try to test/cleanup/resend tomorrow.

Cough. Still un-tested, sorry. I will test it somehow and report, but I'd like to send this for review right now.

Because I simply can't decide what the new flag should actually do, so please ack/nack the semantics/naming at least.

Changes:

1. I decided it would be better to change __wait_event() to accept wait.flags right now. This looks better in any case to me, and otherwise we need to introduce the __wait_exclusive_enum.

The change looks trivial (both actually), please tell me if you think it doesn't deserve a separate patch.

2. I won't insist, but WQ_FLAG_EXCLUSIVE_HEAD can be used without WQ_FLAG_EXCLUSIVE.

Unlikely this can be useful, but it looks more natural this way. Otherwise we need to add another check to ensure that WQ_FLAG_EXCLUSIVE_HEAD can't come alone.

However, perhaps this means the new flag needs another name. I agree in advance with any.

Quoted 27 lines · Oleg Nesterov

Quoted 2 lines · Oleg Nesterov

OK, I'll try to test/cleanup/resend tomorrow.

Cough. Still un-tested, sorry. I will test it somehow and report, but I'd like to send this for review right now.

Because I simply can't decide what the new flag should actually do, so please ack/nack the semantics/naming at least.

Changes:

1. I decided it would be better to change __wait_event() to accept wait.flags right now. This looks better in any case to me, and otherwise we need to introduce the __wait_exclusive_enum.

The change looks trivial (both actually), please tell me if you think it doesn't deserve a separate patch.

2. I won't insist, but WQ_FLAG_EXCLUSIVE_HEAD can be used without WQ_FLAG_EXCLUSIVE.

Unlikely this can be useful, but it looks more natural this way. Otherwise we need to add another check to ensure that WQ_FLAG_EXCLUSIVE_HEAD can't come alone.

Quoted 2 lines

However, perhaps this means the new flag needs another name. I agree in advance with any.

What about:

#define WQ_FLAG_HEAD 0x02

#define WQ_FLAG_EXCLUSIVE_HEAD (WQ_FLAG_HEAD | WQ_FLAG_EXCLUSIVE)

That avoids having WQ_FLAG_EXCLUSIVE_HEAD not actually meaning "exclusive"?

Patches look reasonable at first glance. The second patch would need to be changed to handle that WQ_FLAG_EXCLUSIVE_HEAD has both bits set (probably just replace uses of WQ_FLAG_EXCLUSIVE_HEAD with WQ_FLAG_HEAD).