Poll : add poll_wait_set_exclusive (fixing thundering herd problem in LTTng)

static struct poll_table_entry *poll_get_entry(poll_table *_p) {

fs/select.c +4 -2

 	struct poll_wqueues *p = container_of(_p, struct poll_wqueues, pt);

@@ -117,8 +135,10 @@ static struct poll_table_entry *poll_get
 }
 
 /* Add a new entry */
-static void __pollwait(struct file *filp, wait_queue_head_t *wait_address,
-				poll_table *p)
+static void __pollwait_common(struct file *filp,
+			      wait_queue_head_t *wait_address,
+			      poll_table *p,
+			      int exclusive)
 {
 	struct poll_table_entry *entry = poll_get_entry(p);
 	if (!entry)

Hi

Quoted 17 lines

static struct poll_table_entry *poll_get_entry(poll_table *_p) {

fs/select.c +4 -2

 	struct poll_wqueues *p = container_of(_p, struct poll_wqueues, pt);

@@ -117,8 +135,10 @@ static struct poll_table_entry *poll_get
 }
 
 /* Add a new entry */
-static void __pollwait(struct file *filp, wait_queue_head_t *wait_address,
-				poll_table *p)
+static void __pollwait_common(struct file *filp,
+			      wait_queue_head_t *wait_address,
+			      poll_table *p,
+			      int exclusive)
 {
 	struct poll_table_entry *entry = poll_get_entry(p);
 	if (!entry)

fs/select.c static void __pollwait(struct file *filp · line 154

Quoted 9 lines

fs/select.c +5 -1

@@ -127,7 +147,23 @@ static void __pollwait(struct file *filp
 	entry->filp = filp;
 	entry->wait_address = wait_address;
 	init_waitqueue_entry(&entry->wait, current);
-	add_wait_queue(wait_address, &entry->wait);
+	if (!exclusive)
+		add_wait_queue(wait_address, &entry->wait);
+	else
+		add_wait_queue_exclusive(wait_address, &entry->wait);
+}

I fully agreed this feature is needed. Actually, I've made similar patch at one years ago.

http://marc.info/?l=linux-kernel&m=120257050719087&w=2

but, I have one question.
My version have epoll support, but yours donesn't have. Is it intensionally?

this is just dumb question, it doesn't mean any objection.

Quoted 10 lines

I fully agreed this feature is needed. Actually, I've made similar patch at one years ago.

http://marc.info/?l=linux-kernel&m=120257050719087&w=2

but, I have one question.
My version have epoll support, but yours donesn't have. Is it intensionally?

Quoted 1 line

this is just dumb question, it doesn't mean any objection.

Hrm, actually, your patch seems cleaner than mine, but it adds a branch in the standard hotpath, which mine does not do (but I am not sure it is such an important optimization...).

Is there any reason why your patch
did not get merged ?

The only reason I did not make a epoll version is simply because LTTng currently does not support it. :)

Quoted 10 lines

Quoted 10 lines

I fully agreed this feature is needed. Actually, I've made similar patch at one years ago.

http://marc.info/?l=linux-kernel&m=120257050719087&w=2

but, I have one question.
My version have epoll support, but yours donesn't have. Is it intensionally?

Quoted 5 lines

Quoted 1 line

this is just dumb question, it doesn't mean any objection.

Hrm, actually, your patch seems cleaner than mine, but it adds a branch in the standard hotpath, which mine does not do (but I am not sure it is such an important optimization...).

Why do you think poll_wait() is hotpath?
I think sysm_poll() isn't hotpath because it often cause task sleeping.

Quoted 2 lines

Is there any reason why your patch
did not get merged ?

my patch was developed for a part of mem_notify patch series. but the mem_notify was naked by akpm.
therefore it lost merging motivation ;-)

Ingo, I'll rebase and post my patch for -tip tommorow. Could you please review it?

Quoted 2 lines

The only reason I did not make a epoll version is simply because LTTng currently does not support it. :)

thanks.
I understand your original intension.

patch againt: tip/tracing/marker

==========
Currently, wake_up() function behavior depend on the way of wait queue adding function.

wake_up() wake_up_all()
---------------------------------------------------------------

add_wait_queue()              wake up all        wake up all
add_wait_queue_exclusive()    wake up one task   wake up all

Unforunately, poll_wait() always use add_wait_queue().
it means there is no way that wake up only one process in polled processes. wake_up() also wake up all sleeping processes, not 1 process.

Mathieu Desnoyers explained it cause following problem to LTTng.

In LTTng, all lttd readers are polling all the available debugfs files for data. This is principally because the number of reader threads is user-defined and there are typical workloads where a single CPU is producing most of the tracing data and all other CPUs are idle, available to consume data. It therefore makes sense not to tie those threads to specific buffers. However, when the number of threads grows, we face a "thundering herd" problem where many threads can be woken up and put back to sleep, leaving only a single thread doing useful work.

Quoted 10 lines

Mathieu Desnoyers explained it cause following problem to LTTng.

In LTTng, all lttd readers are polling all the available debugfs files for data. This is principally because the number of reader threads is user-defined and there are typical workloads where a single CPU is producing most of the tracing data and all other CPUs are idle, available to consume data. It therefore makes sense not to tie those threads to specific buffers. However, when the number of threads grows, we face a "thundering herd" problem where many threads can be woken up and put back to sleep, leaving only a single thread doing useful work.

Why do you need to have so many threads banging a single device/file? Have one (or any other very little number) puller thread(s), that activates with chucks of pulled data the other processing threads. That way there's no need for a new wakeup abstraction.

Quoted 21 lines · KOSAKI Motohiro

patch againt: tip/tracing/marker

==========
Currently, wake_up() function behavior depend on the way of wait queue adding function.

wake_up() wake_up_all()
---------------------------------------------------------------

add_wait_queue()              wake up all        wake up all
add_wait_queue_exclusive()    wake up one task   wake up all

Unforunately, poll_wait() always use add_wait_queue().
it means there is no way that wake up only one process in polled processes. wake_up() also wake up all sleeping processes, not 1 process.

Mathieu Desnoyers explained it cause following problem to LTTng.

Quoted 8 lines

In LTTng, all lttd readers are polling all the available debugfs files for data. This is principally because the number of reader threads is user-defined and there are typical workloads where a single CPU is producing most of the tracing data and all other CPUs are idle, available to consume data. It therefore makes sense not to tie those threads to specific buffers. However, when the number of threads grows, we face a "thundering herd" problem where many threads can be woken up and put back to sleep, leaving only a single thread doing useful work.

Why do you need to have so many threads banging a single device/file? Have one (or any other very little number) puller thread(s), that activates with chucks of pulled data the other processing threads. That way there's no need for a new wakeup abstraction.

- Davide

Quoted 11 lines

Quoted 10 lines

Mathieu Desnoyers explained it cause following problem to LTTng.

In LTTng, all lttd readers are polling all the available debugfs files for data. This is principally because the number of reader threads is user-defined and there are typical workloads where a single CPU is producing most of the tracing data and all other CPUs are idle, available to consume data. It therefore makes sense not to tie those threads to specific buffers. However, when the number of threads grows, we face a "thundering herd" problem where many threads can be woken up and put back to sleep, leaving only a single thread doing useful work.

Quoted 8 lines

Why do you need to have so many threads banging a single device/file? Have one (or any other very little number) puller thread(s), that activates with chucks of pulled data the other processing threads. That way there's no need for a new wakeup abstraction.

- Davide

One of the key design rule of LTTng is to do not depend on such system-wide data structures, or entity (e.g. single manager thread). Everything is per-cpu, and it does scale very well.

I wonder how badly the approach you propose can scale on large NUMA systems, where having to synchronize everything through a single thread might become an important point of contention, just due to the cacheline bouncing and extra scheduler activity involved.

Mathieu Desnoyers <[email protected]> writes:

[...]

Quoted 24 lines

Quoted 11 lines

Quoted 10 lines

Mathieu Desnoyers explained it cause following problem to LTTng.

In LTTng, all lttd readers are polling all the available debugfs files for data. This is principally because the number of reader threads is user-defined and there are typical workloads where a single CPU is producing most of the tracing data and all other CPUs are idle, available to consume data. It therefore makes sense not to tie those threads to specific buffers. However, when the number of threads grows, we face a "thundering herd" problem where many threads can be woken up and put back to sleep, leaving only a single thread doing useful work.

Quoted 8 lines

Why do you need to have so many threads banging a single device/file? Have one (or any other very little number) puller thread(s), that activates with chucks of pulled data the other processing threads. That way there's no need for a new wakeup abstraction.

- Davide

One of the key design rule of LTTng is to do not depend on such system-wide data structures, or entity (e.g. single manager thread). Everything is per-cpu, and it does scale very well.

Quoted 4 lines

I wonder how badly the approach you propose can scale on large NUMA systems, where having to synchronize everything through a single thread might become an important point of contention, just due to the cacheline bouncing and extra scheduler activity involved.

But at the end of the day these threads end up writing to the (possibly) single spindle. Isn't that the biggest bottlneck here?

One of the key design rule of LTTng is to do not depend on such system-wide data structures, or entity (e.g. single manager thread). Everything is per-cpu, and it does scale very well.

I wonder how badly the approach you propose can scale on large NUMA systems, where having to synchronize everything through a single thread might become an important point of contention, just due to the cacheline bouncing and extra scheduler activity involved.

Quoted 8 lines

One of the key design rule of LTTng is to do not depend on such system-wide data structures, or entity (e.g. single manager thread). Everything is per-cpu, and it does scale very well.

I wonder how badly the approach you propose can scale on large NUMA systems, where having to synchronize everything through a single thread might become an important point of contention, just due to the cacheline bouncing and extra scheduler activity involved.

I dunno the LTT architecture, so I'm staying out of that discussion. But, if the patch you're trying to push is to avoid thundering herd of so many threads waiting on the single file*, you've got the same problem right there. You've got at least the spinlock protecting the queue where these threads are focusing, whose cacheline is bounced gets bounced all over the CPUs.
Do you have any measure of the improvements that such poll_wait_exclusive() will eventually lead to?

Quoted 8 lines · Mathieu Desnoyers

One of the key design rule of LTTng is to do not depend on such system-wide data structures, or entity (e.g. single manager thread). Everything is per-cpu, and it does scale very well.

I wonder how badly the approach you propose can scale on large NUMA systems, where having to synchronize everything through a single thread might become an important point of contention, just due to the cacheline bouncing and extra scheduler activity involved.

I dunno the LTT architecture, so I'm staying out of that discussion. But, if the patch you're trying to push is to avoid thundering herd of so many threads waiting on the single file*, you've got the same problem right there. You've got at least the spinlock protecting the queue where these threads are focusing, whose cacheline is bounced gets bounced all over the CPUs.
Do you have any measure of the improvements that such poll_wait_exclusive() will eventually lead to?

- Davide

Nope, sorry, I don't own any machine with such huge amount of CPUs, therefore I can't afford to test that scalability level.

You say that "You've got at least the spinlock protecting the queue where these threads are focusing", you assume we stay limited to the current implementation inability to scale correctly. We could think of a scheme with :

- Per cpu waiters. Waiters are added to their own CPU waiting list.
- Per cpu wakeups, where the wakeup will try to wake up a waiter on the local CPU first.

If there happens to be no waiters for a local CPU wakeup, the wakeup would then be broadcasted to other CPUs, which involves proper locking which I think could be done pretty efficiently so we don't hurt the "add waiter" fastpath.

By doing this, we could end up not even taking a global spinlock in the add waiter/wakeup fastpaths. So then we would have fixed both the thundering herd problem _and_ the global spinlock issue altogether.

Any thought ?

Quoted 1 line

Any thought ?

That looks fine, but before waving the Thundering Herd flag some performance numbers should be given IMO, considerng also that this is a rather particular use of the poll subsystem.
Eventually, isn't something like the patch below better than adding custom case names to poll_wait() ALA poll_wait_LONGNAMESFOLLOW()? That way you can pass your own queueing function:

	poll_wait_qfunc(file, head, pt, add_wait_queue_exclusive);