# Re: \[PATCH v3 0/3\] epoll: introduce round robin wakeup mode - List: linux-api - 6 messages, 4 authors - Page: https://ratatoskr.run/linux-api/2015/02/92930/t ## Re: \[PATCH v3 0/3\] epoll: introduce round robin wakeup mode - From: Andrew Morton \ - Date: 2015-02-27 21:10:34 - Message: https://ratatoskr.run/linux-api/2015/02/92930.md ```text On Wed, 25 Feb 2015 11:27:04 -0500 Jason Baron [ref] wrote: > > Libenzi inactive eventpoll appears to be without a > > dedicated maintainer since 2011 or so. Is there anyone who > > knows the code and its usages in detail and does final ABI > > decisions on eventpoll - Andrew, Al or Linus? > > > Generally, Andrew and Al do more 'final' reviews here, > and a lot of others on lkml are always very helpful in > looking at this code. However, its not always clear, at > least to me, who I should pester. Yes, it's a difficult situation. The 3/3 changelog refers to "EPOLLROUNDROBIN" which I assume is a leftover from some earlier revision? I don't really understand the need for rotation/round-robin. We can solve the thundering herd via exclusive wakeups, but what is the point in choosing to wake the task which has been sleeping for the longest time? Why is that better than waking the task which has been sleeping for the *least* time? That's probably faster as that task's data is more likely to still be in cache. The changelogs talks about "starvation" but they don't really say what this term means in this context, nor why it is a bad thing. ``` ## Re: \[PATCH v3 0/3\] epoll: introduce round robin wakeup mode - From: Jason Baron \ - Date: 2015-02-27 22:01:33 - Message: https://ratatoskr.run/linux-api/2015/02/92932.md ```text On 02/27/2015 04:10 PM, Andrew Morton wrote: > On Wed, 25 Feb 2015 11:27:04 -0500 Jason Baron [ref] wrote: > >>> Libenzi inactive eventpoll appears to be without a >>> dedicated maintainer since 2011 or so. Is there anyone who >>> knows the code and its usages in detail and does final ABI >>> decisions on eventpoll - Andrew, Al or Linus? >>> >> Generally, Andrew and Al do more 'final' reviews here, >> and a lot of others on lkml are always very helpful in >> looking at this code. However, its not always clear, at >> least to me, who I should pester. > Yes, it's a difficult situation. > > The 3/3 changelog refers to "EPOLLROUNDROBIN" which I assume is > a leftover from some earlier revision? Yes, that's a typo there. It should read 'EPOLL_ROTATE'. > > I don't really understand the need for rotation/round-robin. We can > solve the thundering herd via exclusive wakeups, but what is the point > in choosing to wake the task which has been sleeping for the longest > time? Why is that better than waking the task which has been sleeping > for the *least* time? That's probably faster as that task's data is > more likely to still be in cache. > > The changelogs talks about "starvation" but they don't really say what > this term means in this context, nor why it is a bad thing. > So the idea with the 'rotation' is to try and distribute the workload more evenly across the worker threads. We currently tend to wake up the 'head' of the queue over and over and thus the workload for us is not evenly distributed. In fact, we have a workload where we have to remove all the epoll sets and then re-add them in a different order to improve the situation. We are trying to avoid this workaround and in addition avoid thundering wakeups when possible (using exclusive as you mention). I agree that waking up the task that may have been sleeping longer may not be the best for all workloads. So what I am proposing here is an optional flag to meet a certain workload. It might not be right for all workloads, but we have found it quite useful. The 'starvation' mention was in regards to the fact that with this new behavior of not waking up all threads (and rotating them), an adversarial thread might insert itself into our wakeup queue and 'starve' us out. This concern was raised by Andy Lutomirkski, and this current series is not subject to this issue, b/c it works by creating a new epoll fd and then adding that epoll fd to the wakeup queue. Thus, this 'new' epoll fd is local to the thread and the wakeup queue continues to wake all threads. Only the 'new' epoll fd which we then attach ourselves to, implements the exclusive/rotate behavior. Thanks, -Jason ``` ## Re: \[PATCH v3 0/3\] epoll: introduce round robin wakeup mode - From: Andrew Morton \ - Date: 2015-02-27 22:31:58 - Message: https://ratatoskr.run/linux-api/2015/02/92934.md ```text On Fri, 27 Feb 2015 17:01:32 -0500 Jason Baron [ref] wrote: > > > > > I don't really understand the need for rotation/round-robin. We can > > solve the thundering herd via exclusive wakeups, but what is the point > > in choosing to wake the task which has been sleeping for the longest > > time? Why is that better than waking the task which has been sleeping > > for the *least* time? That's probably faster as that task's data is > > more likely to still be in cache. > > > > The changelogs talks about "starvation" but they don't really say what > > this term means in this context, nor why it is a bad thing. > > I'm still not getting it. > So the idea with the 'rotation' is to try and distribute the > workload more evenly across the worker threads. Why? > We currently > tend to wake up the 'head' of the queue over and over and > thus the workload for us is not evenly distributed. What's wrong with that? > In fact, we > have a workload where we have to remove all the epoll sets > and then re-add them in a different order to improve the situation. Why? > We are trying to avoid this workaround and in addition avoid > thundering wakeups when possible (using exclusive as you > mention). A better way to describe a patchset like this is to start out describing what the user sees: what is wrong with the current kernel behaviour and how will it be improved? Once that is understood then start getting into kernel internal details. Jon's explanation was much more useful. Was it accurate? ``` ## Re: \[PATCH v3 0/3\] epoll: introduce round robin wakeup mode - From: Ingo Molnar \ - Date: 2015-03-05 00:02:25 - Message: https://ratatoskr.run/linux-api/2015/03/93101.md ```text * Andrew Morton [ref] wrote: > On Fri, 27 Feb 2015 17:01:32 -0500 Jason Baron [ref] wrote: > > > > > > > > > I don't really understand the need for rotation/round-robin. We can > > > solve the thundering herd via exclusive wakeups, but what is the point > > > in choosing to wake the task which has been sleeping for the longest > > > time? Why is that better than waking the task which has been sleeping > > > for the *least* time? That's probably faster as that task's data is > > > more likely to still be in cache. > > > > > > The changelogs talks about "starvation" but they don't really say what > > > this term means in this context, nor why it is a bad thing. > > > > > I'm still not getting it. > > > So the idea with the 'rotation' is to try and distribute the > > workload more evenly across the worker threads. > > Why? > > > We currently > > tend to wake up the 'head' of the queue over and over and > > thus the workload for us is not evenly distributed. > > What's wrong with that? > > > In fact, we > > have a workload where we have to remove all the epoll sets > > and then re-add them in a different order to improve the situation. > > Why? So my guess would be (but Jason would know this more precisely) that spreading the workload to more tasks in a FIFO manner, the individual tasks can move between CPUs better, and fill in available CPU bandwidth better, increasing concurrency. With the current LIFO distribution of wakeups, the 'busiest' threads will get many wakeups (potentially from different CPUs), making them cache-hot, which may interfere with them easily migrating across CPUs. So while technically both approaches have similar concurrency, the more 'spread out' task hierarchy schedules in a more consistent manner. But ... this is just a wild guess and even if my description is accurate then it should still be backed by robust measurements and observations, before we extend the ABI. This hypothesis could be tested by the patch below: with the patch applied if the performance difference between FIFO and LIFO epoll wakeups disappears, then the root cause is the cache-hotness code in the scheduler. Thanks, Ingo --- diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index ee595ef30470..89af04e946d2 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5354,7 +5354,7 @@ static int task_hot(struct task_struct *p, struct lb_env *env) lockdep_assert_held(&env->src_rq->lock); - if (p->sched_class != &fair_sched_class) + if (1 || p->sched_class != &fair_sched_class) return 0; if (unlikely(p->policy == SCHED_IDLE)) ``` ## Re: \[PATCH v3 0/3\] epoll: introduce round robin wakeup mode - From: Jason Baron \ - Date: 2015-03-05 03:53:39 - Message: https://ratatoskr.run/linux-api/2015/03/93105.md ```text On 03/04/2015 07:02 PM, Ingo Molnar wrote: > * Andrew Morton [ref] wrote: > >> On Fri, 27 Feb 2015 17:01:32 -0500 Jason Baron [ref] wrote: >> >>>> I don't really understand the need for rotation/round-robin. We can >>>> solve the thundering herd via exclusive wakeups, but what is the point >>>> in choosing to wake the task which has been sleeping for the longest >>>> time? Why is that better than waking the task which has been sleeping >>>> for the *least* time? That's probably faster as that task's data is >>>> more likely to still be in cache. >>>> >>>> The changelogs talks about "starvation" but they don't really say what >>>> this term means in this context, nor why it is a bad thing. >>>> >> I'm still not getting it. >> >>> So the idea with the 'rotation' is to try and distribute the >>> workload more evenly across the worker threads. >> Why? >> >>> We currently >>> tend to wake up the 'head' of the queue over and over and >>> thus the workload for us is not evenly distributed. >> What's wrong with that? >> >>> In fact, we >>> have a workload where we have to remove all the epoll sets >>> and then re-add them in a different order to improve the situation. >> Why? > So my guess would be (but Jason would know this more precisely) that > spreading the workload to more tasks in a FIFO manner, the individual > tasks can move between CPUs better, and fill in available CPU > bandwidth better, increasing concurrency. > > With the current LIFO distribution of wakeups, the 'busiest' threads > will get many wakeups (potentially from different CPUs), making them > cache-hot, which may interfere with them easily migrating across CPUs. > > So while technically both approaches have similar concurrency, the > more 'spread out' task hierarchy schedules in a more consistent > manner. > > But ... this is just a wild guess and even if my description is > accurate then it should still be backed by robust measurements and > observations, before we extend the ABI. > > This hypothesis could be tested by the patch below: with the patch > applied if the performance difference between FIFO and LIFO epoll > wakeups disappears, then the root cause is the cache-hotness code in > the scheduler. > > So what I think you are describing here fits the model where you have single epoll fd (returned by epoll_create()), which is then attached to wakeup fds. So that can be thought of as having a single 'event' queue (the single epoll fd), where multiple threads are competing to grab events via epoll_wait() and things are currently LIFO there as you describe. However, the use-case I was trying to get at is where you have multiple epoll fds (or event queues), and really just one thread doing epoll_wait() against a single epoll fd. So instead of having all threads competing for all events, we have divided up the events into separate queues. Now, the 'problematic' case is where there may be an event source that is shared among all these epoll fds - such as a listen socket or a pipe. Now there are two distinct issues in this case that this series is trying to address. 1) All epoll fds will receive a wakeup (and hence the threads that are potentially blocking there, although they may not return to user-space if the event has already been consumed). I think the test case I posted shows this pretty clearly - http://lwn.net/Articles/632590/. The number of context switches without adding the to the wait queue is 50x the case where they are added exclusively. That's a lot of extra cpu usage. 2) We are using the wakeup in this case to 'assign' work more permanently to the thread. That is, in the case of a listen socket we then add the connected socket to the woken up threads local set of epoll events. So the load persists past the wake up. And in this case, doing the round robin wakeups, simply allows us to access more cpu bandwidth. (I'm also looking into potentially using cpu affinity to do the wakeups as well as you suggested.) Thanks, -Jason ``` ## Re: \[PATCH v3 0/3\] epoll: introduce round robin wakeup mode - From: Ingo Molnar \ - Date: 2015-03-05 09:15:17 - Message: https://ratatoskr.run/linux-api/2015/03/93118.md ```text * Jason Baron [ref] wrote: > 2) We are using the wakeup in this case to 'assign' work more > permanently to the thread. That is, in the case of a listen socket > we then add the connected socket to the woken up threads local set > of epoll events. So the load persists past the wake up. And in this > case, doing the round robin wakeups, simply allows us to access more > cpu bandwidth. (I'm also looking into potentially using cpu affinity > to do the wakeups as well as you suggested.) So this is the part that I still don't understand. What difference does LIFO versus FIFO wakeups make to CPU utilization: a thread waiting for work is idle, no matter whether it ran most recently or least recently. Once an idle worker thread is woken it will compute its own work, for whatever time it needs to, and won't be bothered by epoll again until it finished its work and starts waiting again. So regardless the wakeup order it's the same principal bandwidth utilization, modulo caching artifacts [*] and modulo scheduling artifacts [**]: [*] Caching artifacts: in that sense Andrew's point stands: given multiple equivalent choices it's more beneficial to pick a thread that was most recently used (and is thus most cache-hot - i.e. the current wakeup behavior), versus a thread that was least recently used (and is thus the most cache-cold - i.e. the round-robin wakeup you introduce). [**] The hack patch I posted in my previous reply. Thanks, Ingo ```