epoll_wait misses edge-triggered eventfd events: bug in Linux 5.3 and 5.4

epoll_wait misses edge-triggered eventfd events: bug in Linux 5.3 and 5.4

[Max Neunhoeffer]

Dear All,

I believe I have found a bug in Linux 5.3 and 5.4 in epoll_wait/epoll_ctl
when an eventfd together with edge-triggered or the EPOLLONESHOT policy
is used. If an epoll_ctl call to rearm the eventfd happens approximately
at the same time as the epoll_wait goes to sleep, the event can be lost, 
even though proper protection through a mutex is employed.

The details together with two programs showing the problem can be found
here:

  https://bugzilla.kernel.org/show_bug.cgi?id=205933

Older kernels seem not to have this problem, although I did not test all
versions. I know that 4.15 and 5.0 do not show the problem.

Note that this method of using epoll_wait/eventfd is used by
boost::asio to wake up event loops in case a new completion handler
is posted to an io_service, so this is probably relevant for many
applications.

Any help with this would be appreciated.

Cheers,
  Max.

Re: epoll_wait misses edge-triggered eventfd events: bug in Linux 5.3 and 5.4

[Jakub Kicinski]

On Fri, 31 Jan 2020 14:57:30 +0100, Max Neunhoeffer wrote:
> Dear All,
> 
> I believe I have found a bug in Linux 5.3 and 5.4 in epoll_wait/epoll_ctl
> when an eventfd together with edge-triggered or the EPOLLONESHOT policy
> is used. If an epoll_ctl call to rearm the eventfd happens approximately
> at the same time as the epoll_wait goes to sleep, the event can be lost, 
> even though proper protection through a mutex is employed.
> 
> The details together with two programs showing the problem can be found
> here:
> 
>   https://bugzilla.kernel.org/show_bug.cgi?id=205933
> 
> Older kernels seem not to have this problem, although I did not test all
> versions. I know that 4.15 and 5.0 do not show the problem.
> 
> Note that this method of using epoll_wait/eventfd is used by
> boost::asio to wake up event loops in case a new completion handler
> is posted to an io_service, so this is probably relevant for many
> applications.
> 
> Any help with this would be appreciated.

Could be networking related but let's CC FS folks just in case.

Would you be able to perform bisection to narrow down the search 
for a buggy change?

Re: epoll_wait misses edge-triggered eventfd events: bug in Linux 5.3 and 5.4

[Max Neunhoeffer]

Dear Jakub and all,

I have done a git bisect and found that this commit introduced the epoll
bug:

https://github.com/torvalds/linux/commit/a218cc4914209ac14476cb32769b31a556355b22

I Cc the author of the commit.

This makes sense, since the commit introduces a new rwlock to reduce
contention in ep_poll_callback. I do not fully understand the details
but this sounds all very close to this bug.

I have also verified that the bug is still present in the latest master
branch in Linus' repository.

Furthermore, Chris Kohlhoff has provided yet another reproducing program
which is no longer using edge-triggered but standard level-triggered
events and epoll_wait. This makes the bug all the more urgent, since
potentially more programs could run into this problem and could end up
with sleeping barbers.

I have added all the details to the bugzilla bugreport:

  https://bugzilla.kernel.org/show_bug.cgi?id=205933

Hopefully, we can resolve this now equipped with this amount of information.

Best regards,
  Max.

On 20/02/01 12:16, Jakub Kicinski wrote:
> On Fri, 31 Jan 2020 14:57:30 +0100, Max Neunhoeffer wrote:
> > Dear All,
> > 
> > I believe I have found a bug in Linux 5.3 and 5.4 in epoll_wait/epoll_ctl
> > when an eventfd together with edge-triggered or the EPOLLONESHOT policy
> > is used. If an epoll_ctl call to rearm the eventfd happens approximately
> > at the same time as the epoll_wait goes to sleep, the event can be lost, 
> > even though proper protection through a mutex is employed.
> > 
> > The details together with two programs showing the problem can be found
> > here:
> > 
> >   https://bugzilla.kernel.org/show_bug.cgi?id=205933
> > 
> > Older kernels seem not to have this problem, although I did not test all
> > versions. I know that 4.15 and 5.0 do not show the problem.
> > 
> > Note that this method of using epoll_wait/eventfd is used by
> > boost::asio to wake up event loops in case a new completion handler
> > is posted to an io_service, so this is probably relevant for many
> > applications.
> > 
> > Any help with this would be appreciated.
> 
> Could be networking related but let's CC FS folks just in case.
> 
> Would you be able to perform bisection to narrow down the search 
> for a buggy change?

Re: epoll_wait misses edge-triggered eventfd events: bug in Linux 5.3 and 5.4

[Jakub Kicinski]

On Mon, 3 Feb 2020 16:15:36 +0100, Max Neunhoeffer wrote:
> Dear Jakub and all,
> 
> I have done a git bisect and found that this commit introduced the epoll
> bug:
> 
> https://github.com/torvalds/linux/commit/a218cc4914209ac14476cb32769b31a556355b22
> 
> I Cc the author of the commit.

Awesome, thanks a lot for doing that! Hopefully Roman can take a look
soon. Breaking boost::asio seems like a pretty serious regression.

> This makes sense, since the commit introduces a new rwlock to reduce
> contention in ep_poll_callback. I do not fully understand the details
> but this sounds all very close to this bug.
> 
> I have also verified that the bug is still present in the latest master
> branch in Linus' repository.
> 
> Furthermore, Chris Kohlhoff has provided yet another reproducing program
> which is no longer using edge-triggered but standard level-triggered
> events and epoll_wait. This makes the bug all the more urgent, since
> potentially more programs could run into this problem and could end up
> with sleeping barbers.
> 
> I have added all the details to the bugzilla bugreport:
> 
>   https://bugzilla.kernel.org/show_bug.cgi?id=205933
> 
> Hopefully, we can resolve this now equipped with this amount of information.
> 
> Best regards,
>   Max.
> 
> On 20/02/01 12:16, Jakub Kicinski wrote:
> > On Fri, 31 Jan 2020 14:57:30 +0100, Max Neunhoeffer wrote:  
> > > Dear All,
> > > 
> > > I believe I have found a bug in Linux 5.3 and 5.4 in epoll_wait/epoll_ctl
> > > when an eventfd together with edge-triggered or the EPOLLONESHOT policy
> > > is used. If an epoll_ctl call to rearm the eventfd happens approximately
> > > at the same time as the epoll_wait goes to sleep, the event can be lost, 
> > > even though proper protection through a mutex is employed.
> > > 
> > > The details together with two programs showing the problem can be found
> > > here:
> > > 
> > >   https://bugzilla.kernel.org/show_bug.cgi?id=205933
> > > 
> > > Older kernels seem not to have this problem, although I did not test all
> > > versions. I know that 4.15 and 5.0 do not show the problem.
> > > 
> > > Note that this method of using epoll_wait/eventfd is used by
> > > boost::asio to wake up event loops in case a new completion handler
> > > is posted to an io_service, so this is probably relevant for many
> > > applications.
> > > 
> > > Any help with this would be appreciated.  
> > 
> > Could be networking related but let's CC FS folks just in case.
> > 
> > Would you be able to perform bisection to narrow down the search 
> > for a buggy change?  

Re: epoll_wait misses edge-triggered eventfd events: bug in Linux 5.3 and 5.4

[Roman Penyaev]

Hi Max and all,

I can reproduce the issue.  My epoll optimization which you referenced
did not consider the case of wakeups on epoll_ctl() path, only the fd
update path.

I will send the fix upstream today/tomorrow (already tested on the
epollbug.c), the exemplary patch at the bottom of the current
email.

Also I would like to  submit the epollbug.c as a test case for
the epoll test suite. Does the author of epollbug have any
objections?

Thanks.

--
Roman

diff --git a/fs/eventpoll.c b/fs/eventpoll.c
index c4159bcc05d9..a90f8b8a5def 100644
--- a/fs/eventpoll.c
+++ b/fs/eventpoll.c
@@ -745,7 +745,7 @@ static __poll_t ep_scan_ready_list(struct eventpoll 
*ep,
                  * the ->poll() wait list (delayed after we release the 
lock).
                  */
                 if (waitqueue_active(&ep->wq))
-                       wake_up(&ep->wq);
+                       wake_up_locked(&ep->wq);
                 if (waitqueue_active(&ep->poll_wait))
                         pwake++;
         }
@@ -1200,7 +1200,7 @@ static inline bool chain_epi_lockless(struct 
epitem *epi)
   * Another thing worth to mention is that ep_poll_callback() can be 
called
   * concurrently for the same @epi from different CPUs if poll table was 
inited
   * with several wait queues entries.  Plural wakeup from different CPUs 
of a
- * single wait queue is serialized by wq.lock, but the case when 
multiple wait
+ * single wait queue is serialized by ep->lock, but the case when 
multiple wait
   * queues are used should be detected accordingly.  This is detected 
using
   * cmpxchg() operation.
   */
@@ -1275,6 +1275,13 @@ static int ep_poll_callback(wait_queue_entry_t 
*wait, unsigned mode, int sync, v
                                 break;
                         }
                 }
+               /*
+                * Since here we have the read lock (ep->lock) taken, 
plural
+                * wakeup from different CPUs can occur, thus we call 
wake_up()
+                * variant which implies its own lock on wqueue. All 
other paths
+                * take write lock, thus modifications on ep->wq are 
serialized
+                * by rw lock.
+                */
                 wake_up(&ep->wq);
         }
         if (waitqueue_active(&ep->poll_wait))
@@ -1578,7 +1585,7 @@ static int ep_insert(struct eventpoll *ep, const 
struct epoll_event *event,

                 /* Notify waiting tasks that events are available */
                 if (waitqueue_active(&ep->wq))
-                       wake_up(&ep->wq);
+                       wake_up_locked(&ep->wq);
                 if (waitqueue_active(&ep->poll_wait))
                         pwake++;
         }
@@ -1684,7 +1691,7 @@ static int ep_modify(struct eventpoll *ep, struct 
epitem *epi,

                         /* Notify waiting tasks that events are 
available */
                         if (waitqueue_active(&ep->wq))
-                               wake_up(&ep->wq);
+                               wake_up_locked(&ep->wq);
                         if (waitqueue_active(&ep->poll_wait))
                                 pwake++;
                 }
@@ -1881,9 +1888,9 @@ static int ep_poll(struct eventpoll *ep, struct 
epoll_event __user *events,
                 waiter = true;
                 init_waitqueue_entry(&wait, current);

-               spin_lock_irq(&ep->wq.lock);
+               write_lock_irq(&ep->lock);
                 __add_wait_queue_exclusive(&ep->wq, &wait);
-               spin_unlock_irq(&ep->wq.lock);
+               write_unlock_irq(&ep->lock);
         }

         for (;;) {
@@ -1931,9 +1938,9 @@ static int ep_poll(struct eventpoll *ep, struct 
epoll_event __user *events,
                 goto fetch_events;

         if (waiter) {
-               spin_lock_irq(&ep->wq.lock);
+               write_lock_irq(&ep->lock);
                 __remove_wait_queue(&ep->wq, &wait);
-               spin_unlock_irq(&ep->wq.lock);
+               write_unlock_irq(&ep->lock);
         }

         return res;




On 2020-02-03 16:15, Max Neunhoeffer wrote:
> Dear Jakub and all,
> 
> I have done a git bisect and found that this commit introduced the 
> epoll
> bug:
> 
> https://github.com/torvalds/linux/commit/a218cc4914209ac14476cb32769b31a556355b22
> 
> I Cc the author of the commit.
> 
> This makes sense, since the commit introduces a new rwlock to reduce
> contention in ep_poll_callback. I do not fully understand the details
> but this sounds all very close to this bug.
> 
> I have also verified that the bug is still present in the latest master
> branch in Linus' repository.
> 
> Furthermore, Chris Kohlhoff has provided yet another reproducing 
> program
> which is no longer using edge-triggered but standard level-triggered
> events and epoll_wait. This makes the bug all the more urgent, since
> potentially more programs could run into this problem and could end up
> with sleeping barbers.
> 
> I have added all the details to the bugzilla bugreport:
> 
>   https://bugzilla.kernel.org/show_bug.cgi?id=205933
> 
> Hopefully, we can resolve this now equipped with this amount of 
> information.
> 
> Best regards,
>   Max.
> 
> On 20/02/01 12:16, Jakub Kicinski wrote:
>> On Fri, 31 Jan 2020 14:57:30 +0100, Max Neunhoeffer wrote:
>> > Dear All,
>> >
>> > I believe I have found a bug in Linux 5.3 and 5.4 in epoll_wait/epoll_ctl
>> > when an eventfd together with edge-triggered or the EPOLLONESHOT policy
>> > is used. If an epoll_ctl call to rearm the eventfd happens approximately
>> > at the same time as the epoll_wait goes to sleep, the event can be lost,
>> > even though proper protection through a mutex is employed.
>> >
>> > The details together with two programs showing the problem can be found
>> > here:
>> >
>> >   https://bugzilla.kernel.org/show_bug.cgi?id=205933
>> >
>> > Older kernels seem not to have this problem, although I did not test all
>> > versions. I know that 4.15 and 5.0 do not show the problem.
>> >
>> > Note that this method of using epoll_wait/eventfd is used by
>> > boost::asio to wake up event loops in case a new completion handler
>> > is posted to an io_service, so this is probably relevant for many
>> > applications.
>> >
>> > Any help with this would be appreciated.
>> 
>> Could be networking related but let's CC FS folks just in case.
>> 
>> Would you be able to perform bisection to narrow down the search
>> for a buggy change?

Re: epoll_wait misses edge-triggered eventfd events: bug in Linux 5.3 and 5.4

[Max Neunhöffer]

Hi Roman,

Thanks for your quick response. This sounds fantastic!

The epollbug.c program was originally written by my colleague Lars Maier and then modified by me and subsequently by Chris Kohlhoff. Note that the bugzilla bug report contains altogether three variants which test epoll_wait/epoll_ctl in three different ways. It might be sensible to take all three variants for the test suite.
I cannot imagine that any of the three authors would object to this, I definitely do not, the other two are on Cc in this email and can speak for themselves.

Best regards,
  Max

Am 3. Februar 2020 18:33:27 MEZ schrieb Roman Penyaev <rpenyaev@suse.de>:
>Hi Max and all,
>
>I can reproduce the issue.  My epoll optimization which you referenced
>did not consider the case of wakeups on epoll_ctl() path, only the fd
>update path.
>
>I will send the fix upstream today/tomorrow (already tested on the
>epollbug.c), the exemplary patch at the bottom of the current
>email.
>
>Also I would like to  submit the epollbug.c as a test case for
>the epoll test suite. Does the author of epollbug have any
>objections?
>
>Thanks.
>
>--
>Roman
>
>diff --git a/fs/eventpoll.c b/fs/eventpoll.c
>index c4159bcc05d9..a90f8b8a5def 100644
>--- a/fs/eventpoll.c
>+++ b/fs/eventpoll.c
>@@ -745,7 +745,7 @@ static __poll_t ep_scan_ready_list(struct eventpoll
>
>*ep,
>                * the ->poll() wait list (delayed after we release the 
>lock).
>                  */
>                 if (waitqueue_active(&ep->wq))
>-                       wake_up(&ep->wq);
>+                       wake_up_locked(&ep->wq);
>                 if (waitqueue_active(&ep->poll_wait))
>                         pwake++;
>         }
>@@ -1200,7 +1200,7 @@ static inline bool chain_epi_lockless(struct 
>epitem *epi)
>   * Another thing worth to mention is that ep_poll_callback() can be 
>called
>* concurrently for the same @epi from different CPUs if poll table was 
>inited
>* with several wait queues entries.  Plural wakeup from different CPUs 
>of a
>- * single wait queue is serialized by wq.lock, but the case when 
>multiple wait
>+ * single wait queue is serialized by ep->lock, but the case when 
>multiple wait
>   * queues are used should be detected accordingly.  This is detected 
>using
>   * cmpxchg() operation.
>   */
>@@ -1275,6 +1275,13 @@ static int ep_poll_callback(wait_queue_entry_t 
>*wait, unsigned mode, int sync, v
>                                 break;
>                         }
>                 }
>+               /*
>+                * Since here we have the read lock (ep->lock) taken, 
>plural
>+                * wakeup from different CPUs can occur, thus we call 
>wake_up()
>+                * variant which implies its own lock on wqueue. All 
>other paths
>+                * take write lock, thus modifications on ep->wq are 
>serialized
>+                * by rw lock.
>+                */
>                 wake_up(&ep->wq);
>         }
>         if (waitqueue_active(&ep->poll_wait))
>@@ -1578,7 +1585,7 @@ static int ep_insert(struct eventpoll *ep, const 
>struct epoll_event *event,
>
>                 /* Notify waiting tasks that events are available */
>                 if (waitqueue_active(&ep->wq))
>-                       wake_up(&ep->wq);
>+                       wake_up_locked(&ep->wq);
>                 if (waitqueue_active(&ep->poll_wait))
>                         pwake++;
>         }
>@@ -1684,7 +1691,7 @@ static int ep_modify(struct eventpoll *ep, struct
>
>epitem *epi,
>
>                         /* Notify waiting tasks that events are 
>available */
>                         if (waitqueue_active(&ep->wq))
>-                               wake_up(&ep->wq);
>+                               wake_up_locked(&ep->wq);
>                         if (waitqueue_active(&ep->poll_wait))
>                                 pwake++;
>                 }
>@@ -1881,9 +1888,9 @@ static int ep_poll(struct eventpoll *ep, struct 
>epoll_event __user *events,
>                 waiter = true;
>                 init_waitqueue_entry(&wait, current);
>
>-               spin_lock_irq(&ep->wq.lock);
>+               write_lock_irq(&ep->lock);
>                 __add_wait_queue_exclusive(&ep->wq, &wait);
>-               spin_unlock_irq(&ep->wq.lock);
>+               write_unlock_irq(&ep->lock);
>         }
>
>         for (;;) {
>@@ -1931,9 +1938,9 @@ static int ep_poll(struct eventpoll *ep, struct 
>epoll_event __user *events,
>                 goto fetch_events;
>
>         if (waiter) {
>-               spin_lock_irq(&ep->wq.lock);
>+               write_lock_irq(&ep->lock);
>                 __remove_wait_queue(&ep->wq, &wait);
>-               spin_unlock_irq(&ep->wq.lock);
>+               write_unlock_irq(&ep->lock);
>         }
>
>         return res;
>
>
>
>
>On 2020-02-03 16:15, Max Neunhoeffer wrote:
>> Dear Jakub and all,
>> 
>> I have done a git bisect and found that this commit introduced the 
>> epoll
>> bug:
>> 
>>
>https://github.com/torvalds/linux/commit/a218cc4914209ac14476cb32769b31a556355b22
>> 
>> I Cc the author of the commit.
>> 
>> This makes sense, since the commit introduces a new rwlock to reduce
>> contention in ep_poll_callback. I do not fully understand the details
>> but this sounds all very close to this bug.
>> 
>> I have also verified that the bug is still present in the latest
>master
>> branch in Linus' repository.
>> 
>> Furthermore, Chris Kohlhoff has provided yet another reproducing 
>> program
>> which is no longer using edge-triggered but standard level-triggered
>> events and epoll_wait. This makes the bug all the more urgent, since
>> potentially more programs could run into this problem and could end
>up
>> with sleeping barbers.
>> 
>> I have added all the details to the bugzilla bugreport:
>> 
>>   https://bugzilla.kernel.org/show_bug.cgi?id=205933
>> 
>> Hopefully, we can resolve this now equipped with this amount of 
>> information.
>> 
>> Best regards,
>>   Max.
>> 
>> On 20/02/01 12:16, Jakub Kicinski wrote:
>>> On Fri, 31 Jan 2020 14:57:30 +0100, Max Neunhoeffer wrote:
>>> > Dear All,
>>> >
>>> > I believe I have found a bug in Linux 5.3 and 5.4 in
>epoll_wait/epoll_ctl
>>> > when an eventfd together with edge-triggered or the EPOLLONESHOT
>policy
>>> > is used. If an epoll_ctl call to rearm the eventfd happens
>approximately
>>> > at the same time as the epoll_wait goes to sleep, the event can be
>lost,
>>> > even though proper protection through a mutex is employed.
>>> >
>>> > The details together with two programs showing the problem can be
>found
>>> > here:
>>> >
>>> >   https://bugzilla.kernel.org/show_bug.cgi?id=205933
>>> >
>>> > Older kernels seem not to have this problem, although I did not
>test all
>>> > versions. I know that 4.15 and 5.0 do not show the problem.
>>> >
>>> > Note that this method of using epoll_wait/eventfd is used by
>>> > boost::asio to wake up event loops in case a new completion
>handler
>>> > is posted to an io_service, so this is probably relevant for many
>>> > applications.
>>> >
>>> > Any help with this would be appreciated.
>>> 
>>> Could be networking related but let's CC FS folks just in case.
>>> 
>>> Would you be able to perform bisection to narrow down the search
>>> for a buggy change?

Re: epoll_wait misses edge-triggered eventfd events: bug in Linux 5.3 and 5.4

[Roman Penyaev]

On 2020-02-03 22:03, Max Neunhöffer wrote:
> Hi Roman,
> 
> Thanks for your quick response. This sounds fantastic!
> 
> The epollbug.c program was originally written by my colleague Lars
> Maier and then modified by me and subsequently by Chris Kohlhoff. Note
> that the bugzilla bug report contains altogether three variants which
> test epoll_wait/epoll_ctl in three different ways. It might be
> sensible to take all three variants for the test suite.

I checked 3 variants, they do same things: epoll_ctl() races against
epoll_wait(), and this is exactly the bug reproduction, regardless
actual read() from a file descriptor or EPOLLET flag set.

> I cannot imagine that any of the three authors would object to this, I
> definitely do not, the other two are on Cc in this email and can speak
> for themselves.

I adapted the logic from epollbug.c and included it into 
epoll_wakeup_test.c
test suite, you should have received the email: "[PATCH 3/3] kselftest:
introduce new epoll test case".  Please, take a look or ask your 
colleague
to take a look. If no objections - then fine, leave as is.

Thanks.

--
Roman