Skip to contentSkip to conversation

fs/epoll: fix the edge-triggered mode for nested epoll

PATCH RESEND In review hev 3 participants 12 messages Sep 2, 2019 – Sep 12, 2019 VFS

lore
Share & tools
lore

hev

author
#0 lore raw

PATCH RESEND 1/1 fs/epoll: fix the edge-triggered mode for nested epoll

From: Heiher <[email protected]>

The structure of event pools:
efd[1]: { efd[2] (EPOLLIN) } efd[0]: { efd[2] (EPOLLIN | EPOLLET) }

               |                                   |
               +-----------------+-----------------+
                                 |
                                 v
                             efd[2]: { sfd[0] (EPOLLIN) }

When sfd[0] to be readable:
* the epoll_wait(efd[0], ..., 0) should return efd[2]'s events on first call, and returns 0 on next calls, because efd[2] is added in edge-triggered mode.
* the epoll_wait(efd[1], ..., 0) should returns efd[2]'s events on every calls until efd[2] is not readable (epoll_wait(efd[2], ...) => 0), because efd[1] is added in level-triggered mode.
* the epoll_wait(efd[2], ..., 0) should returns sfd[0]'s events on every calls until sfd[0] is not readable (read(sfd[0], ...) => EAGAIN), because sfd[0] is added in level-triggered mode.

Test code:
#include <stdio.h>
#include <unistd.h>
#include <sys/epoll.h>
#include <sys/socket.h>

int main(int argc, char *argv[])
{
int sfd[2];
int efd[3];
int nfds;
struct epoll_event e;

if (socketpair(AF_UNIX, SOCK_STREAM, 0, sfd) < 0)
goto out;

efd[0] = epoll_create(1);
if (efd[0] < 0)
goto out;

efd[1] = epoll_create(1);
if (efd[1] < 0)
goto out;

efd[2] = epoll_create(1);
if (efd[2] < 0)
goto out;

e.events = EPOLLIN;
if (epoll_ctl(efd[2], EPOLL_CTL_ADD, sfd[0], &e) < 0)
goto out;

e.events = EPOLLIN;
if (epoll_ctl(efd[1], EPOLL_CTL_ADD, efd[2], &e) < 0)
goto out;

e.events = EPOLLIN | EPOLLET;
if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[2], &e) < 0)
goto out;

if (write(sfd[1], "w", 1) != 1)
goto out;

nfds = epoll_wait(efd[0], &e, 1, 0);
if (nfds != 1)
goto out;

nfds = epoll_wait(efd[0], &e, 1, 0);
if (nfds != 0)
goto out;

nfds = epoll_wait(efd[1], &e, 1, 0);
if (nfds != 1)
goto out;

nfds = epoll_wait(efd[1], &e, 1, 0);
if (nfds != 1)
goto out;

nfds = epoll_wait(efd[2], &e, 1, 0);
if (nfds != 1)
goto out;

nfds = epoll_wait(efd[2], &e, 1, 0);
if (nfds != 1)
goto out;

close(efd[2]);
close(efd[1]);
close(efd[0]);
close(sfd[0]);
close(sfd[1]);

printf("PASS\n");
return 0;

out:
printf("FAIL\n");
return -1;
}

Cc Al Viro <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Davide Libenzi <[email protected]>
Cc Davidlohr Bueso <[email protected]>
Cc Dominik Brodowski <[email protected]>
Cc Eric Wong <[email protected]>
Cc Jason Baron <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Roman Penyaev <[email protected]>
Cc Sridhar Samudrala <[email protected]>
---
 fs/eventpoll.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
fs/eventpoll.c +5 -1
index d7f1f5011fac..a44cb27c636c 100644
@@ -672,6 +672,7 @@ static __poll_t ep_scan_ready_list(struct eventpoll *ep,
 {
 	__poll_t res;
 	int pwake = 0;
+	int nwake = 0;
 	struct epitem *epi, *nepi;
 	LIST_HEAD(txlist);
 
@@ -685,6 +686,9 @@ static __poll_t ep_scan_ready_list(struct eventpoll *ep,
 	if (!ep_locked)
 		mutex_lock_nested(&ep->mtx, depth);
 
+	if (!depth || list_empty(&ep->rdllist))
+		nwake = 1;
+
 	/*
 	 * Steal the ready list, and re-init the original one to the
 	 * empty list. Also, set ep->ovflist to NULL so that events
@@ -739,7 +743,7 @@ static __poll_t ep_scan_ready_list(struct eventpoll *ep,
 	list_splice(&txlist, &ep->rdllist);
 	__pm_relax(ep->ws);
 
-	if (!list_empty(&ep->rdllist)) {
+	if (nwake && !list_empty(&ep->rdllist)) {
 		/*
 		 * Wake up (if active) both the eventpoll wait list and
 		 * the ->poll() wait list (delayed after we release the lock).
Signature · 1 line
2.23.0
#1 lore raw

Hi,

This is indeed a bug. (quick side note: could you please remove efd[1] from your test, because it is not related to the reproduction of a current bug).

Your patch lacks a good description, what exactly you've fixed. Let me speak out loud and please correct me if I'm wrong, my understanding of epoll internals has become a bit rusty: when epoll fds are nested an attempt to harvest events (ep_scan_ready_list() call) produces a second (repeated) event from an internal fd up to an external fd:

     epoll_wait(efd[0], ...):
       ep_send_events():
          ep_scan_ready_list(depth=0):
            ep_send_events_proc():
                ep_item_poll():
                  ep_scan_ready_list(depth=1):
                    ep_poll_safewake():
                      ep_poll_callback()
                        list_add_tail(&epi, &epi->rdllist);
                        ^^^^^^
                        repeated event

In your patch you forbid wakeup for the cases, where depth != 0, i.e. for all nested cases. That seems clear. But what if we can go further and remove the whole chunk, which seems excessive:

@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct eventpoll *ep,

-
- if (!list_empty(&ep->rdllist)) {
- /*

-                * Wake up (if active) both the eventpoll wait list and
-                * the ->poll() wait list (delayed after we release the lock).
-                */

- if (waitqueue_active(&ep->wq))
- wake_up(&ep->wq);
- if (waitqueue_active(&ep->poll_wait))
- pwake++;
- }

        write_unlock_irq(&ep->lock);

        if (!ep_locked)
                mutex_unlock(&ep->mtx);

- /* We have to call this outside the lock */
- if (pwake)
- ep_poll_safewake(&ep->poll_wait);

I reason like that: by the time we've reached the point of scanning events for readiness all wakeups from ep_poll_callback have been already fired and new events have been already accounted in ready list (ep_poll_callback() calls the same ep_poll_safewake()). Here, frankly, I'm not 100% sure and probably missing some corner cases.

Thoughts?

PS. You call list_empty(&ep->rdllist) without ep->lock taken, that is fine,

     but you should be _careful_, so list_empty_careful(&ep->rdllist) 

call
instead.

--
Roman

Quoted 159 lines · hev

From: Heiher <[email protected]>

The structure of event pools:
efd[1]: { efd[2] (EPOLLIN) } efd[0]: { efd[2] (EPOLLIN |
EPOLLET) }

               |                                   |
               +-----------------+-----------------+
                                 |
                                 v
                             efd[2]: { sfd[0] (EPOLLIN) }

When sfd[0] to be readable:
* the epoll_wait(efd[0], ..., 0) should return efd[2]'s events on
first call,
and returns 0 on next calls, because efd[2] is added in
edge-triggered mode.
* the epoll_wait(efd[1], ..., 0) should returns efd[2]'s events on
every calls
until efd[2] is not readable (epoll_wait(efd[2], ...) => 0), because
efd[1]
is added in level-triggered mode.
* the epoll_wait(efd[2], ..., 0) should returns sfd[0]'s events on
every calls
until sfd[0] is not readable (read(sfd[0], ...) => EAGAIN), because
sfd[0]
is added in level-triggered mode.

Test code:
#include <stdio.h>
#include <unistd.h>
#include <sys/epoll.h>
#include <sys/socket.h>

int main(int argc, char *argv[])
{

(quoted diff) +0 -0
 	int sfd[2];
 	int efd[3];
 	int nfds;
 	struct epoll_event e;
 
 	if (socketpair(AF_UNIX, SOCK_STREAM, 0, sfd) < 0)
 		goto out;
 
 	efd[0] = epoll_create(1);
 	if (efd[0] < 0)
 		goto out;
 
 	efd[1] = epoll_create(1);
 	if (efd[1] < 0)
 		goto out;
 
 	efd[2] = epoll_create(1);
 	if (efd[2] < 0)
 		goto out;
 
 	e.events = EPOLLIN;
 	if (epoll_ctl(efd[2], EPOLL_CTL_ADD, sfd[0], &e) < 0)
 		goto out;
 
 	e.events = EPOLLIN;
 	if (epoll_ctl(efd[1], EPOLL_CTL_ADD, efd[2], &e) < 0)
 		goto out;
 
 	e.events = EPOLLIN | EPOLLET;
 	if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[2], &e) < 0)
 		goto out;
 
 	if (write(sfd[1], "w", 1) != 1)
 		goto out;
 
 	nfds = epoll_wait(efd[0], &e, 1, 0);
 	if (nfds != 1)
 		goto out;
 
 	nfds = epoll_wait(efd[0], &e, 1, 0);
 	if (nfds != 0)
 		goto out;
 
 	nfds = epoll_wait(efd[1], &e, 1, 0);
 	if (nfds != 1)
 		goto out;
 
 	nfds = epoll_wait(efd[1], &e, 1, 0);
 	if (nfds != 1)
 		goto out;
 
 	nfds = epoll_wait(efd[2], &e, 1, 0);
 	if (nfds != 1)
 		goto out;
 
 	nfds = epoll_wait(efd[2], &e, 1, 0);
 	if (nfds != 1)
 		goto out;
 
 	close(efd[2]);
 	close(efd[1]);
 	close(efd[0]);
 	close(sfd[0]);
 	close(sfd[1]);
 
 	printf("PASS\n");
 	return 0;
 
 out:
 	printf("FAIL\n");
 	return -1;
 }
Cc Al Viro <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Davide Libenzi <[email protected]>
Cc Davidlohr Bueso <[email protected]>
Cc Dominik Brodowski <[email protected]>
Cc Eric Wong <[email protected]>
Cc Jason Baron <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Roman Penyaev <[email protected]>
Cc Sridhar Samudrala <[email protected]>
---
 fs/eventpoll.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
fs/eventpoll.c +4 -0
index d7f1f5011fac..a44cb27c636c 100644
@@ -672,6 +672,7 @@ static __poll_t ep_scan_ready_list(struct eventpoll 
 *ep,
 {
 	__poll_t res;
 	int pwake = 0;
+	int nwake = 0;
 	struct epitem *epi, *nepi;
 	LIST_HEAD(txlist);
@@ -685,6 +686,9 @@ static __poll_t ep_scan_ready_list(struct eventpoll 
 *ep,
 	if (!ep_locked)
 		mutex_lock_nested(&ep->mtx, depth);
 
+	if (!depth || list_empty(&ep->rdllist))
+		nwake = 1;
+
 	/*
 	 * Steal the ready list, and re-init the original one to the
fs/eventpoll.c +1 -1
 	 * empty list. Also, set ep->ovflist to NULL so that events
@@ -739,7 +743,7 @@ static __poll_t ep_scan_ready_list(struct eventpoll 
 *ep,
 	list_splice(&txlist, &ep->rdllist);
 	__pm_relax(ep->ws);
 
-	if (!list_empty(&ep->rdllist)) {
+	if (nwake && !list_empty(&ep->rdllist)) {
 		/*
 		 * Wake up (if active) both the eventpoll wait list and

* the ->poll() wait list (delayed after we release the lock).

#2 lore raw
Quoted 54 lines · Roman Penyaev

Hi,

This is indeed a bug. (quick side note: could you please remove efd[1] from your test, because it is not related to the reproduction of a current bug).

Your patch lacks a good description, what exactly you've fixed.  Let me speak out loud and please correct me if I'm wrong, my understanding of epoll internals has become a bit rusty: when epoll fds are nested an attempt to harvest events (ep_scan_ready_list() call) produces a second (repeated) event from an internal fd up to an external fd:

     epoll_wait(efd[0], ...):
       ep_send_events():
          ep_scan_ready_list(depth=0):
            ep_send_events_proc():
                ep_item_poll():
                  ep_scan_ready_list(depth=1):
                    ep_poll_safewake():
                      ep_poll_callback() list_add_tail(&epi, &epi->rdllist); ^^^^^^
                        repeated event

In your patch you forbid wakeup for the cases, where depth != 0, i.e. for all nested cases. That seems clear.  But what if we can go further and remove the whole chunk, which seems excessive:

(quoted diff) +0 -5
@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
 
-
-       if (!list_empty(&ep->rdllist)) {
-               /*
-                * Wake up (if active) both the eventpoll wait list and
-                * the ->poll() wait list (delayed after we release the

lock).
-                */
-               if (waitqueue_active(&ep->wq)) -                       wake_up(&ep->wq);
-               if (waitqueue_active(&ep->poll_wait)) -                       pwake++;
-       }
        write_unlock_irq(&ep->lock);

        if (!ep_locked)
                mutex_unlock(&ep->mtx);

-       /* We have to call this outside the lock */ -       if (pwake)
-               ep_poll_safewake(&ep->poll_wait);

Quoted 8 lines

I reason like that: by the time we've reached the point of scanning events for readiness all wakeups from ep_poll_callback have been already fired and new events have been already accounted in ready list (ep_poll_callback() calls
the same ep_poll_safewake()). Here, frankly, I'm not 100% sure and probably missing some corner cases.

Thoughts?

So the: 'wake_up(&ep->wq);' part, I think is about waking up other threads that may be in waiting in epoll_wait(). For example, there may be multiple threads doing epoll_wait() on the same epoll fd, and the logic above seems to say thread 1 may have processed say N events and now its going to to go off to work those, so let's wake up thread 2 now to handle the next chunk. So I think removing all that even for the depth 0 case is going to change some behavior here. So perhaps, it should be removed for all depths except for 0? And if so, it may be better to make 2 patches here to separate these changes.

For the nested wakeups, I agree that the extra wakeups seem unnecessary and it may make sense to remove them for all depths. I don't think the nested epoll semantics are particularly well spelled out, and afaict, nested epoll() has behaved this way for quite some time. And the current behavior is not bad in the way that a missing wakeup or false negative would be. It woulbe be good to better understand the use-case more here and to try and spell out the nested semantics more clearly?

Thanks,

-Jason

Quoted 172 lines

PS.  You call list_empty(&ep->rdllist) without ep->lock taken, that is fine,
     but you should be _careful_, so list_empty_careful(&ep->rdllist) call instead.

Signature · 1 line
Roman
Quoted 159 lines · hev

From: Heiher <[email protected]>

The structure of event pools:
 efd[1]: { efd[2] (EPOLLIN) }        efd[0]: { efd[2] (EPOLLIN | EPOLLET) }

               |                                   |
               +-----------------+-----------------+
                                 |

                                 v
                             efd[2]: { sfd[0] (EPOLLIN) }

When sfd[0] to be readable:
 * the epoll_wait(efd[0], ..., 0) should return efd[2]'s events on first call,
   and returns 0 on next calls, because efd[2] is added in edge-triggered mode.
 * the epoll_wait(efd[1], ..., 0) should returns efd[2]'s events on every calls
   until efd[2] is not readable (epoll_wait(efd[2], ...) => 0), because efd[1]
   is added in level-triggered mode.
 * the epoll_wait(efd[2], ..., 0) should returns sfd[0]'s events on every calls
   until sfd[0] is not readable (read(sfd[0], ...) => EAGAIN), because sfd[0]
   is added in level-triggered mode.

Test code:
 #include <stdio.h>
 #include <unistd.h>
 #include <sys/epoll.h>
 #include <sys/socket.h>

 int main(int argc, char *argv[])
 {
     int sfd[2];
     int efd[3];
     int nfds;
     struct epoll_event e;

     if (socketpair(AF_UNIX, SOCK_STREAM, 0, sfd) < 0) goto out;

     efd[0] = epoll_create(1);
     if (efd[0] < 0)
         goto out;

     efd[1] = epoll_create(1);
     if (efd[1] < 0)
         goto out;

     efd[2] = epoll_create(1);
     if (efd[2] < 0)
         goto out;

     e.events = EPOLLIN;
     if (epoll_ctl(efd[2], EPOLL_CTL_ADD, sfd[0], &e) < 0) goto out;

     e.events = EPOLLIN;
     if (epoll_ctl(efd[1], EPOLL_CTL_ADD, efd[2], &e) < 0) goto out;

     e.events = EPOLLIN | EPOLLET;
     if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[2], &e) < 0) goto out;

     if (write(sfd[1], "w", 1) != 1)
         goto out;

     nfds = epoll_wait(efd[0], &e, 1, 0);
     if (nfds != 1)
         goto out;

     nfds = epoll_wait(efd[0], &e, 1, 0);
     if (nfds != 0)
         goto out;

     nfds = epoll_wait(efd[1], &e, 1, 0);
     if (nfds != 1)
         goto out;

     nfds = epoll_wait(efd[1], &e, 1, 0);
     if (nfds != 1)
         goto out;

     nfds = epoll_wait(efd[2], &e, 1, 0);
     if (nfds != 1)
         goto out;

     nfds = epoll_wait(efd[2], &e, 1, 0);
     if (nfds != 1)
         goto out;

     close(efd[2]);
     close(efd[1]);
     close(efd[0]);
     close(sfd[0]);
     close(sfd[1]);

     printf("PASS\n");
     return 0;

 out:
     printf("FAIL\n");
     return -1;
 }

Cc Al Viro <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Davide Libenzi <[email protected]>
Cc Davidlohr Bueso <[email protected]>
Cc Dominik Brodowski <[email protected]>
Cc Eric Wong <[email protected]>
Cc Jason Baron <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Roman Penyaev <[email protected]>
Cc Sridhar Samudrala <[email protected]>

---
 fs/eventpoll.c | 6 +++++-

 1 file changed, 5 insertions(+), 1 deletion(-)
fs/eventpoll.c +4 -0
index d7f1f5011fac..a44cb27c636c 100644
@@ -672,6 +672,7 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
  {
      __poll_t res;
      int pwake = 0;
+    int nwake = 0;
      struct epitem *epi, *nepi;
      LIST_HEAD(txlist);
@@ -685,6 +686,9 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
      if (!ep_locked)
          mutex_lock_nested(&ep->mtx, depth);
 
+    if (!depth || list_empty(&ep->rdllist))
+        nwake = 1;
+
      /*
       * Steal the ready list, and re-init the original one to the

      * empty list. Also, set ep->ovflist to NULL so that events

fs/eventpoll.c +1 -1
@@ -739,7 +743,7 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
      list_splice(&txlist, &ep->rdllist);
      __pm_relax(ep->ws);
 
-    if (!list_empty(&ep->rdllist)) {
+    if (nwake && !list_empty(&ep->rdllist)) {
          /*
           * Wake up (if active) both the eventpoll wait list and

          * the ->poll() wait list (delayed after we release the lock).

#3 lore raw
Quoted 64 lines · Jason Baron
Quoted 63 lines · Roman Penyaev

Hi,

This is indeed a bug. (quick side note: could you please remove efd[1] from your test, because it is not related to the reproduction of a current bug).

Your patch lacks a good description, what exactly you've fixed.  Let me speak out loud and please correct me if I'm wrong, my understanding of epoll internals has become a bit rusty: when epoll fds are nested an attempt to harvest events (ep_scan_ready_list() call) produces a second (repeated) event from an internal fd up to an external fd:

     epoll_wait(efd[0], ...):
       ep_send_events():
          ep_scan_ready_list(depth=0):
            ep_send_events_proc():
                ep_item_poll():
                  ep_scan_ready_list(depth=1):
                    ep_poll_safewake():
                      ep_poll_callback() list_add_tail(&epi, &epi->rdllist); ^^^^^^
                        repeated event

In your patch you forbid wakeup for the cases, where depth != 0, i.e. for all nested cases. That seems clear.  But what if we can go further and remove the whole chunk, which seems excessive:

(quoted diff) +0 -4
@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
 
-
-       if (!list_empty(&ep->rdllist)) {
-               /*
-                * Wake up (if active) both the eventpoll wait list 

and
-                * the ->poll() wait list (delayed after we release the
lock).
-                */
-               if (waitqueue_active(&ep->wq))
-                       wake_up(&ep->wq);
-               if (waitqueue_active(&ep->poll_wait))
-                       pwake++;
-       }
        write_unlock_irq(&ep->lock);

        if (!ep_locked)
                mutex_unlock(&ep->mtx);

-       /* We have to call this outside the lock */ -       if (pwake)
-               ep_poll_safewake(&ep->poll_wait);

I reason like that: by the time we've reached the point of scanning events for readiness all wakeups from ep_poll_callback have been already fired and new events have been already accounted in ready list (ep_poll_callback() calls
the same ep_poll_safewake()). Here, frankly, I'm not 100% sure and probably missing some corner cases.

Quoted 8 lines
Quoted 1 line

Thoughts?

So the: 'wake_up(&ep->wq);' part, I think is about waking up other threads that may be in waiting in epoll_wait(). For example, there may be multiple threads doing epoll_wait() on the same epoll fd, and the logic above seems to say thread 1 may have processed say N events and now its going to to go off to work those, so let's wake up thread 2 now to handle the next chunk.

Not quite. Thread which calls ep_scan_ready_list() processes all the events, and while processing those, removes them one by one from the ready list. But if event mask is !0 and event belongs to Level Triggered Mode descriptor (let's say default mode) it tails event again back to the list (because we are in level mode, so event should be there). So at the end of this traversing loop ready list is likely not empty, and if so, wake up again is called for nested epoll fds. But, those nested epoll fds should get already all the notifications from the main event callback ep_poll_callback(), regardless any thread which traverses events.

I suppose this logic exists for decades, when Davide (the author) was reshuffling the code here and there.

But I do not feel confidence to state that this extra wakeup is bogus, I just have a gut feeling that it looks excessive.

Quoted 11 lines

So I think removing all that even for the
depth 0 case is going to change some behavior here. So perhaps, it should be removed for all depths except for 0? And if so, it may be better to make 2 patches here to separate these changes.

For the nested wakeups, I agree that the extra wakeups seem unnecessary and it may make sense to remove them for all depths. I don't think the nested epoll semantics are particularly well spelled out, and afaict, nested epoll() has behaved this way for quite some time. And the current behavior is not bad in the way that a missing wakeup or false negative would be.

That's 100% true! For edge mode extra wake up is not a bug, not optimal for userspace - yes, but that can't lead to any lost wakeups.

--
Roman

#4 lore raw
Quoted 83 lines · Roman Penyaev
Quoted 62 lines · Jason Baron
Quoted 61 lines · Roman Penyaev

Hi,

This is indeed a bug. (quick side note: could you please remove efd[1] from your test, because it is not related to the reproduction of a current bug).

Your patch lacks a good description, what exactly you've fixed.  Let me speak out loud and please correct me if I'm wrong, my understanding of epoll internals has become a bit rusty: when epoll fds are nested an attempt to harvest events (ep_scan_ready_list() call) produces a second (repeated) event from an internal fd up to an external fd:

     epoll_wait(efd[0], ...):
       ep_send_events():
          ep_scan_ready_list(depth=0):
            ep_send_events_proc():
                ep_item_poll():
                  ep_scan_ready_list(depth=1):
                    ep_poll_safewake():
                      ep_poll_callback() list_add_tail(&epi, &epi->rdllist); ^^^^^^
                        repeated event

In your patch you forbid wakeup for the cases, where depth != 0, i.e. for all nested cases. That seems clear.  But what if we can go further and remove the whole chunk, which seems excessive:

(quoted diff) +0 -5
@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
 
-
-       if (!list_empty(&ep->rdllist)) {
-               /*
-                * Wake up (if active) both the eventpoll wait list and
-                * the ->poll() wait list (delayed after we release the

lock).
-                */
-               if (waitqueue_active(&ep->wq)) -                       wake_up(&ep->wq);
-               if (waitqueue_active(&ep->poll_wait)) -                       pwake++;
-       }
        write_unlock_irq(&ep->lock);

        if (!ep_locked)
                mutex_unlock(&ep->mtx);

-       /* We have to call this outside the lock */ -       if (pwake)
-               ep_poll_safewake(&ep->poll_wait);

I reason like that: by the time we've reached the point of scanning events for readiness all wakeups from ep_poll_callback have been already fired and new events have been already accounted in ready list (ep_poll_callback() calls
the same ep_poll_safewake()). Here, frankly, I'm not 100% sure and probably missing some corner cases.

Quoted 8 lines
Quoted 1 line

Thoughts?

So the: 'wake_up(&ep->wq);' part, I think is about waking up other threads that may be in waiting in epoll_wait(). For example, there may be multiple threads doing epoll_wait() on the same epoll fd, and the logic above seems to say thread 1 may have processed say N events and now its going to to go off to work those, so let's wake up thread 2 now to handle the next chunk.

Not quite. Thread which calls ep_scan_ready_list() processes all the events, and while processing those, removes them one by one from the ready list.  But if event mask is !0 and event belongs to Level Triggered Mode descriptor (let's say default mode) it tails event again back to the list (because we are in level mode, so event should be there).  So at the end of this traversing loop ready list is likely not empty, and if so, wake up again is called for nested epoll fds. But, those nested epoll fds should get already all the notifications from the main event callback ep_poll_callback(), regardless any thread which traverses events.

Quoted 5 lines

I suppose this logic exists for decades, when Davide (the author) was reshuffling the code here and there.

But I do not feel confidence to state that this extra wakeup is bogus, I just have a gut feeling that it looks excessive.

Note that I was talking about the wakeup done on ep->wq not ep->poll_wait. The path that I'm concerned about is let's say that there are N events queued on the ready list. A thread that was woken up in epoll_wait may decide to only process say N/2 of then. Then it will call wakeup on ep->wq and this will wakeup another thread to process the remaining N/2. Without the wakeup, the original thread isn't going to process the events until it finishes with the original N/2 and gets back to epoll_wait(). So I'm not sure how important that path is but I wanted to at least note the change here would impact that behavior.

Thanks,

-Jason

Quoted 19 lines
Quoted 6 lines

So I think removing all that even for the
depth 0 case is going to change some behavior here. So perhaps, it should be removed for all depths except for 0? And if so, it may be better to make 2 patches here to separate these changes.

Quoted 6 lines

For the nested wakeups, I agree that the extra wakeups seem unnecessary and it may make sense to remove them for all depths. I don't think the nested epoll semantics are particularly well spelled out, and afaict, nested epoll() has behaved this way for quite some time. And the current behavior is not bad in the way that a missing wakeup or false negative would be.

That's 100% true! For edge mode extra wake up is not a bug, not optimal for userspace - yes, but that can't lead to any lost wakeups.

Signature · 1 line
Roman
author
#5 lore raw

Hi,

Quoted 103 lines · Jason Baron
Quoted 83 lines · Roman Penyaev
Quoted 62 lines · Jason Baron
Quoted 61 lines · Roman Penyaev

Hi,

This is indeed a bug. (quick side note: could you please remove efd[1] from your test, because it is not related to the reproduction of a current bug).

Your patch lacks a good description, what exactly you've fixed. Let me speak out loud and please correct me if I'm wrong, my understanding of epoll internals has become a bit rusty: when epoll fds are nested an attempt to harvest events (ep_scan_ready_list() call) produces a second (repeated) event from an internal fd up to an external fd:

     epoll_wait(efd[0], ...):
       ep_send_events():
          ep_scan_ready_list(depth=0):
            ep_send_events_proc():
                ep_item_poll():
                  ep_scan_ready_list(depth=1):
                    ep_poll_safewake():
                      ep_poll_callback()
                        list_add_tail(&epi, &epi->rdllist);
                        ^^^^^^
                        repeated event

In your patch you forbid wakeup for the cases, where depth != 0, i.e. for all nested cases. That seems clear. But what if we can go further and remove the whole chunk, which seems excessive:

(quoted diff) +0 -5
@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
 
-
-       if (!list_empty(&ep->rdllist)) {
-               /*
-                * Wake up (if active) both the eventpoll wait list and
-                * the ->poll() wait list (delayed after we release the

lock).

(quoted diff) +0 -9
-                */
-               if (waitqueue_active(&ep->wq))
-                       wake_up(&ep->wq);
-               if (waitqueue_active(&ep->poll_wait))
-                       pwake++;
-       }
        write_unlock_irq(&ep->lock);
 
        if (!ep_locked)
                mutex_unlock(&ep->mtx);
 
-       /* We have to call this outside the lock */
-       if (pwake)
-               ep_poll_safewake(&ep->poll_wait);

I reason like that: by the time we've reached the point of scanning events for readiness all wakeups from ep_poll_callback have been already fired and new events have been already accounted in ready list (ep_poll_callback() calls
the same ep_poll_safewake()). Here, frankly, I'm not 100% sure and probably missing some corner cases.

Quoted 8 lines
Quoted 1 line

Thoughts?

So the: 'wake_up(&ep->wq);' part, I think is about waking up other threads that may be in waiting in epoll_wait(). For example, there may be multiple threads doing epoll_wait() on the same epoll fd, and the logic above seems to say thread 1 may have processed say N events and now its going to to go off to work those, so let's wake up thread 2 now to handle the next chunk.

Not quite. Thread which calls ep_scan_ready_list() processes all the events, and while processing those, removes them one by one from the ready list. But if event mask is !0 and event belongs to Level Triggered Mode descriptor (let's say default mode) it tails event again back to the list (because we are in level mode, so event should be there). So at the end of this traversing loop ready list is likely not empty, and if so, wake up again is called for nested epoll fds. But, those nested epoll fds should get already all the notifications from the main event callback ep_poll_callback(), regardless any thread which traverses events.

Quoted 5 lines

I suppose this logic exists for decades, when Davide (the author) was reshuffling the code here and there.

But I do not feel confidence to state that this extra wakeup is bogus, I just have a gut feeling that it looks excessive.

Note that I was talking about the wakeup done on ep->wq not ep->poll_wait. The path that I'm concerned about is let's say that there are N events queued on the ready list. A thread that was woken up in epoll_wait may decide to only process say N/2 of then. Then it will call wakeup on ep->wq and this will wakeup another thread to process the remaining N/2. Without the wakeup, the original thread isn't going to process the events until it finishes with the original N/2 and gets back to epoll_wait(). So I'm not sure how important that path is but I wanted to at least note the change here would impact that behavior.

Quoted 24 lines

Thanks,

-Jason

Quoted 19 lines
Quoted 6 lines

So I think removing all that even for the
depth 0 case is going to change some behavior here. So perhaps, it should be removed for all depths except for 0? And if so, it may be better to make 2 patches here to separate these changes.

Quoted 6 lines

For the nested wakeups, I agree that the extra wakeups seem unnecessary and it may make sense to remove them for all depths. I don't think the nested epoll semantics are particularly well spelled out, and afaict, nested epoll() has behaved this way for quite some time. And the current behavior is not bad in the way that a missing wakeup or false negative would be.

That's 100% true! For edge mode extra wake up is not a bug, not optimal for userspace - yes, but that can't lead to any lost wakeups.

--
Roman

I tried to remove the whole chunk of code that Roman said, and it seems that there
are no obvious problems with the two test programs below:

Test case 1:

           t0
            |
           e0
            |
           e1 (et)
            |
           s0 (lt)

When s0 is readable, the thread 0 can only read once event from e0.

#include <stdio.h>
#include <unistd.h>
#include <sys/epoll.h>
#include <sys/socket.h>

int main(int argc, char *argv[])

{
    int sfd[2];
    int efd[2];
    int nfds;
    struct epoll_event e;

    if (socketpair(AF_UNIX, SOCK_STREAM, 0, sfd) < 0)
        goto out;

    efd[0] = epoll_create(1);
    if (efd[0] < 0)
        goto out;

    efd[1] = epoll_create(1);
    if (efd[1] < 0)
        goto out;

    e.events = EPOLLIN;
    if (epoll_ctl(efd[1], EPOLL_CTL_ADD, sfd[0], &e) < 0)
        goto out;

    e.events = EPOLLIN | EPOLLET;
    if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[1], &e) < 0)
        goto out;

    if (write(sfd[1], "w", 1) != 1)
        goto out;

    nfds = epoll_wait(efd[0], &e, 1, 0);
    if (nfds != 1)
        goto out;

    nfds = epoll_wait(efd[0], &e, 1, 0);
    if (nfds != 0)
        goto out;

    nfds = epoll_wait(efd[1], &e, 1, 0);
    if (nfds != 1)
        goto out;

    nfds = epoll_wait(efd[1], &e, 1, 0);
    if (nfds != 1)
        goto out;

    close(efd[1]);
    close(efd[0]);
    close(sfd[0]);
    close(sfd[1]);

    printf("PASS\n");
    return 0;

out:

    printf("FAIL\n");
    return -1;
}

Test case 2:

           t0  t1
            \   /
             e0
            /   \
    (et) e1   e2 (et)
           |      |
     (lt) s0    s2 (lt)

When s0 and s2 are readable, both thread 0 and thread 1 can read an event from e0.

#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <sys/epoll.h>
#include <sys/socket.h>

static int efd[3];
static int sfd[4];
static int count;

static void *
thread_handler(void *data)

{
    struct epoll_event e;

    if (epoll_wait(efd[0], &e, 1, -1) == 1)
        count++;

    return NULL;
}

static void *
emit_handler(void *data)

{
    usleep (100000);

    write(sfd[1], "w", 1);
    write(sfd[3], "w", 1);

    return NULL;
}

int main(int argc, char *argv[])

{
    struct epoll_event e;
    pthread_t tw, te;

    if (socketpair(AF_UNIX, SOCK_STREAM, 0, &sfd[0]) < 0)
        goto out;

    if (socketpair(AF_UNIX, SOCK_STREAM, 0, &sfd[2]) < 0)
        goto out;

    efd[0] = epoll_create(1);
    if (efd[0] < 0)
        goto out;

    efd[1] = epoll_create(1);
    if (efd[1] < 0)
        goto out;

    efd[2] = epoll_create(1);
    if (efd[2] < 0)
        goto out;

    e.events = EPOLLIN;
    if (epoll_ctl(efd[1], EPOLL_CTL_ADD, sfd[0], &e) < 0)
        goto out;

    e.events = EPOLLIN;
    if (epoll_ctl(efd[2], EPOLL_CTL_ADD, sfd[2], &e) < 0)
        goto out;

    e.events = EPOLLIN | EPOLLET;
    if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[1], &e) < 0)
        goto out;

    e.events = EPOLLIN | EPOLLET;
    if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[2], &e) < 0)
        goto out;

    if (pthread_create(&tw, NULL, thread_handler, NULL) < 0)
        goto out;

    if (pthread_create(&te, NULL, emit_handler, NULL) < 0)
        goto out;

    if (epoll_wait(efd[0], &e, 1, -1) == 1)
        count++;

    if (pthread_join(tw, NULL) < 0)
        goto out;

    if (count != 2)
        goto out;

    close(efd[0]);
    close(efd[1]);
    close(efd[2]);
    close(sfd[0]);
    close(sfd[1]);
    close(sfd[2]);
    close(sfd[3]);

    printf ("PASS\n");
    return 0;

out:

    printf("FAIL\n");
    return -1;
}

t0: thread0
t1: thread1
e0: epoll0 (efd[0])
e1: epoll1 (efd[1])
e2: epoll2 (efd[2])
s0: socket0 (sfd[0])
s2: socket2 (sfd[2])

Is it possible to prove that this modification is correct, or any other corner cases are missing?

Signature · 3 lines
Best regards!
Hev
https://hev.cc
author
#6 lore raw

Hi,

I created an epoll wakeup test project, listed some possible cases, and any other corner cases needs to be added?

https://github.com/heiher/epoll-wakeup/blob/master/README.md

Quoted 339 lines · Heiher

Hi,

Quoted 103 lines · Jason Baron
Quoted 83 lines · Roman Penyaev
Quoted 62 lines · Jason Baron
Quoted 61 lines · Roman Penyaev

Hi,

This is indeed a bug. (quick side note: could you please remove efd[1] from your test, because it is not related to the reproduction of a current bug).

Your patch lacks a good description, what exactly you've fixed. Let me speak out loud and please correct me if I'm wrong, my understanding of epoll internals has become a bit rusty: when epoll fds are nested an attempt to harvest events (ep_scan_ready_list() call) produces a second (repeated) event from an internal fd up to an external fd:

     epoll_wait(efd[0], ...):
       ep_send_events():
          ep_scan_ready_list(depth=0):
            ep_send_events_proc():
                ep_item_poll():
                  ep_scan_ready_list(depth=1):
                    ep_poll_safewake():
                      ep_poll_callback()
                        list_add_tail(&epi, &epi->rdllist);
                        ^^^^^^
                        repeated event

In your patch you forbid wakeup for the cases, where depth != 0, i.e. for all nested cases. That seems clear. But what if we can go further and remove the whole chunk, which seems excessive:

(quoted diff) +0 -5
@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
 
-
-       if (!list_empty(&ep->rdllist)) {
-               /*
-                * Wake up (if active) both the eventpoll wait list and
-                * the ->poll() wait list (delayed after we release the

lock).

(quoted diff) +0 -9
-                */
-               if (waitqueue_active(&ep->wq))
-                       wake_up(&ep->wq);
-               if (waitqueue_active(&ep->poll_wait))
-                       pwake++;
-       }
        write_unlock_irq(&ep->lock);
 
        if (!ep_locked)
                mutex_unlock(&ep->mtx);
 
-       /* We have to call this outside the lock */
-       if (pwake)
-               ep_poll_safewake(&ep->poll_wait);

I reason like that: by the time we've reached the point of scanning events for readiness all wakeups from ep_poll_callback have been already fired and new events have been already accounted in ready list (ep_poll_callback() calls
the same ep_poll_safewake()). Here, frankly, I'm not 100% sure and probably missing some corner cases.

Quoted 8 lines
Quoted 1 line

Thoughts?

So the: 'wake_up(&ep->wq);' part, I think is about waking up other threads that may be in waiting in epoll_wait(). For example, there may be multiple threads doing epoll_wait() on the same epoll fd, and the logic above seems to say thread 1 may have processed say N events and now its going to to go off to work those, so let's wake up thread 2 now to handle the next chunk.

Not quite. Thread which calls ep_scan_ready_list() processes all the events, and while processing those, removes them one by one from the ready list. But if event mask is !0 and event belongs to Level Triggered Mode descriptor (let's say default mode) it tails event again back to the list (because we are in level mode, so event should be there). So at the end of this traversing loop ready list is likely not empty, and if so, wake up again is called for nested epoll fds. But, those nested epoll fds should get already all the notifications from the main event callback ep_poll_callback(), regardless any thread which traverses events.

Quoted 5 lines

I suppose this logic exists for decades, when Davide (the author) was reshuffling the code here and there.

But I do not feel confidence to state that this extra wakeup is bogus, I just have a gut feeling that it looks excessive.

Note that I was talking about the wakeup done on ep->wq not ep->poll_wait. The path that I'm concerned about is let's say that there are N events queued on the ready list. A thread that was woken up in epoll_wait may decide to only process say N/2 of then. Then it will call wakeup on ep->wq and this will wakeup another thread to process the remaining N/2. Without the wakeup, the original thread isn't going to process the events until it finishes with the original N/2 and gets back to epoll_wait(). So I'm not sure how important that path is but I wanted to at least note the change here would impact that behavior.

Quoted 24 lines

Thanks,

-Jason

Quoted 19 lines
Quoted 6 lines

So I think removing all that even for the
depth 0 case is going to change some behavior here. So perhaps, it should be removed for all depths except for 0? And if so, it may be better to make 2 patches here to separate these changes.

Quoted 6 lines

For the nested wakeups, I agree that the extra wakeups seem unnecessary and it may make sense to remove them for all depths. I don't think the nested epoll semantics are particularly well spelled out, and afaict, nested epoll() has behaved this way for quite some time. And the current behavior is not bad in the way that a missing wakeup or false negative would be.

That's 100% true! For edge mode extra wake up is not a bug, not optimal for userspace - yes, but that can't lead to any lost wakeups.

--
Roman

I tried to remove the whole chunk of code that Roman said, and it seems that there
are no obvious problems with the two test programs below:

Test case 1:

           t0
            |
           e0
            |
           e1 (et)
            |
           s0 (lt)

When s0 is readable, the thread 0 can only read once event from e0.

#include <stdio.h>
#include <unistd.h>
#include <sys/epoll.h>
#include <sys/socket.h>

int main(int argc, char *argv[])

{
    int sfd[2];
    int efd[2];
    int nfds;
    struct epoll_event e;

    if (socketpair(AF_UNIX, SOCK_STREAM, 0, sfd) < 0)
        goto out;

    efd[0] = epoll_create(1);
    if (efd[0] < 0)
        goto out;

    efd[1] = epoll_create(1);
    if (efd[1] < 0)
        goto out;

    e.events = EPOLLIN;
    if (epoll_ctl(efd[1], EPOLL_CTL_ADD, sfd[0], &e) < 0)
        goto out;

    e.events = EPOLLIN | EPOLLET;
    if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[1], &e) < 0)
        goto out;

    if (write(sfd[1], "w", 1) != 1)
        goto out;

    nfds = epoll_wait(efd[0], &e, 1, 0);
    if (nfds != 1)
        goto out;

    nfds = epoll_wait(efd[0], &e, 1, 0);
    if (nfds != 0)
        goto out;

    nfds = epoll_wait(efd[1], &e, 1, 0);
    if (nfds != 1)
        goto out;

    nfds = epoll_wait(efd[1], &e, 1, 0);
    if (nfds != 1)
        goto out;

    close(efd[1]);
    close(efd[0]);
    close(sfd[0]);
    close(sfd[1]);

    printf("PASS\n");
    return 0;

out:

    printf("FAIL\n");
    return -1;
}

Test case 2:

           t0  t1
            \   /
             e0
            /   \
    (et) e1   e2 (et)
           |      |
     (lt) s0    s2 (lt)

When s0 and s2 are readable, both thread 0 and thread 1 can read an event from e0.

#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <sys/epoll.h>
#include <sys/socket.h>

static int efd[3];
static int sfd[4];
static int count;

static void *
thread_handler(void *data)

{
    struct epoll_event e;

    if (epoll_wait(efd[0], &e, 1, -1) == 1)
        count++;

    return NULL;
}

static void *
emit_handler(void *data)

{
    usleep (100000);

    write(sfd[1], "w", 1);
    write(sfd[3], "w", 1);

    return NULL;
}

int main(int argc, char *argv[])

{
    struct epoll_event e;
    pthread_t tw, te;

    if (socketpair(AF_UNIX, SOCK_STREAM, 0, &sfd[0]) < 0)
        goto out;

    if (socketpair(AF_UNIX, SOCK_STREAM, 0, &sfd[2]) < 0)
        goto out;

    efd[0] = epoll_create(1);
    if (efd[0] < 0)
        goto out;

    efd[1] = epoll_create(1);
    if (efd[1] < 0)
        goto out;

    efd[2] = epoll_create(1);
    if (efd[2] < 0)
        goto out;

    e.events = EPOLLIN;
    if (epoll_ctl(efd[1], EPOLL_CTL_ADD, sfd[0], &e) < 0)
        goto out;

    e.events = EPOLLIN;
    if (epoll_ctl(efd[2], EPOLL_CTL_ADD, sfd[2], &e) < 0)
        goto out;

    e.events = EPOLLIN | EPOLLET;
    if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[1], &e) < 0)
        goto out;

    e.events = EPOLLIN | EPOLLET;
    if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[2], &e) < 0)
        goto out;

    if (pthread_create(&tw, NULL, thread_handler, NULL) < 0)
        goto out;

    if (pthread_create(&te, NULL, emit_handler, NULL) < 0)
        goto out;

    if (epoll_wait(efd[0], &e, 1, -1) == 1)
        count++;

    if (pthread_join(tw, NULL) < 0)
        goto out;

    if (count != 2)
        goto out;

    close(efd[0]);
    close(efd[1]);
    close(efd[2]);
    close(sfd[0]);
    close(sfd[1]);
    close(sfd[2]);
    close(sfd[3]);

    printf ("PASS\n");
    return 0;

out:

    printf("FAIL\n");
    return -1;
}

t0: thread0
t1: thread1
e0: epoll0 (efd[0])
e1: epoll1 (efd[1])
e2: epoll2 (efd[2])
s0: socket0 (sfd[0])
s2: socket2 (sfd[2])

Is it possible to prove that this modification is correct, or any other corner cases are missing?

--
Best regards!
Hev
https://hev.cc

Signature · 3 lines
Best regards!
Hev
https://hev.cc
author
#7 lore raw

Hi,

Quoted 144 lines · Heiher

Hi,

I created an epoll wakeup test project, listed some possible cases, and any other corner cases needs to be added?

https://github.com/heiher/epoll-wakeup/blob/master/README.md

Quoted 135 lines · Heiher

Hi,

Quoted 103 lines · Jason Baron
Quoted 83 lines · Roman Penyaev
Quoted 62 lines · Jason Baron
Quoted 61 lines · Roman Penyaev

Hi,

This is indeed a bug. (quick side note: could you please remove efd[1] from your test, because it is not related to the reproduction of a current bug).

Your patch lacks a good description, what exactly you've fixed. Let me speak out loud and please correct me if I'm wrong, my understanding of epoll internals has become a bit rusty: when epoll fds are nested an attempt to harvest events (ep_scan_ready_list() call) produces a second (repeated) event from an internal fd up to an external fd:

     epoll_wait(efd[0], ...):
       ep_send_events():
          ep_scan_ready_list(depth=0):
            ep_send_events_proc():
                ep_item_poll():
                  ep_scan_ready_list(depth=1):
                    ep_poll_safewake():
                      ep_poll_callback()
                        list_add_tail(&epi, &epi->rdllist);
                        ^^^^^^
                        repeated event

In your patch you forbid wakeup for the cases, where depth != 0, i.e. for all nested cases. That seems clear. But what if we can go further and remove the whole chunk, which seems excessive:

(quoted diff) +0 -5
@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
 
-
-       if (!list_empty(&ep->rdllist)) {
-               /*
-                * Wake up (if active) both the eventpoll wait list and
-                * the ->poll() wait list (delayed after we release the

lock).

(quoted diff) +0 -9
-                */
-               if (waitqueue_active(&ep->wq))
-                       wake_up(&ep->wq);
-               if (waitqueue_active(&ep->poll_wait))
-                       pwake++;
-       }
        write_unlock_irq(&ep->lock);
 
        if (!ep_locked)
                mutex_unlock(&ep->mtx);
 
-       /* We have to call this outside the lock */
-       if (pwake)
-               ep_poll_safewake(&ep->poll_wait);

I reason like that: by the time we've reached the point of scanning events for readiness all wakeups from ep_poll_callback have been already fired and new events have been already accounted in ready list (ep_poll_callback() calls
the same ep_poll_safewake()). Here, frankly, I'm not 100% sure and probably missing some corner cases.

Quoted 8 lines
Quoted 1 line

Thoughts?

So the: 'wake_up(&ep->wq);' part, I think is about waking up other threads that may be in waiting in epoll_wait(). For example, there may be multiple threads doing epoll_wait() on the same epoll fd, and the logic above seems to say thread 1 may have processed say N events and now its going to to go off to work those, so let's wake up thread 2 now to handle the next chunk.

Not quite. Thread which calls ep_scan_ready_list() processes all the events, and while processing those, removes them one by one from the ready list. But if event mask is !0 and event belongs to Level Triggered Mode descriptor (let's say default mode) it tails event again back to the list (because we are in level mode, so event should be there). So at the end of this traversing loop ready list is likely not empty, and if so, wake up again is called for nested epoll fds. But, those nested epoll fds should get already all the notifications from the main event callback ep_poll_callback(), regardless any thread which traverses events.

Quoted 5 lines

I suppose this logic exists for decades, when Davide (the author) was reshuffling the code here and there.

But I do not feel confidence to state that this extra wakeup is bogus, I just have a gut feeling that it looks excessive.

Note that I was talking about the wakeup done on ep->wq not ep->poll_wait. The path that I'm concerned about is let's say that there are N events queued on the ready list. A thread that was woken up in epoll_wait may decide to only process say N/2 of then. Then it will call wakeup on ep->wq and this will wakeup another thread to process the remaining N/2. Without the wakeup, the original thread isn't going to process the events until it finishes with the original N/2 and gets back to epoll_wait(). So I'm not sure how important that path is but I wanted to at least note the change here would impact that behavior.

Quoted 24 lines

Thanks,

-Jason

Quoted 19 lines
Quoted 6 lines

So I think removing all that even for the
depth 0 case is going to change some behavior here. So perhaps, it should be removed for all depths except for 0? And if so, it may be better to make 2 patches here to separate these changes.

Quoted 6 lines

For the nested wakeups, I agree that the extra wakeups seem unnecessary and it may make sense to remove them for all depths. I don't think the nested epoll semantics are particularly well spelled out, and afaict, nested epoll() has behaved this way for quite some time. And the current behavior is not bad in the way that a missing wakeup or false negative would be.

That's 100% true! For edge mode extra wake up is not a bug, not optimal for userspace - yes, but that can't lead to any lost wakeups.

--
Roman

I tried to remove the whole chunk of code that Roman said, and it seems that there
are no obvious problems with the two test programs below:

I recall this message, the test case 9/25/26 of epoll-wakeup (on github) are failed while
the whole chunk are removed.

Apply the original patch, all tests passed.

Quoted 211 lines
Quoted 197 lines

Test case 1:

           t0
            |
           e0
            |
           e1 (et)
            |
           s0 (lt)

When s0 is readable, the thread 0 can only read once event from e0.

#include <stdio.h>
#include <unistd.h>
#include <sys/epoll.h>
#include <sys/socket.h>

int main(int argc, char *argv[])

{
    int sfd[2];
    int efd[2];
    int nfds;
    struct epoll_event e;

    if (socketpair(AF_UNIX, SOCK_STREAM, 0, sfd) < 0)
        goto out;

    efd[0] = epoll_create(1);
    if (efd[0] < 0)
        goto out;

    efd[1] = epoll_create(1);
    if (efd[1] < 0)
        goto out;

    e.events = EPOLLIN;
    if (epoll_ctl(efd[1], EPOLL_CTL_ADD, sfd[0], &e) < 0)
        goto out;

    e.events = EPOLLIN | EPOLLET;
    if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[1], &e) < 0)
        goto out;

    if (write(sfd[1], "w", 1) != 1)
        goto out;

    nfds = epoll_wait(efd[0], &e, 1, 0);
    if (nfds != 1)
        goto out;

    nfds = epoll_wait(efd[0], &e, 1, 0);
    if (nfds != 0)
        goto out;

    nfds = epoll_wait(efd[1], &e, 1, 0);
    if (nfds != 1)
        goto out;

    nfds = epoll_wait(efd[1], &e, 1, 0);
    if (nfds != 1)
        goto out;

    close(efd[1]);
    close(efd[0]);
    close(sfd[0]);
    close(sfd[1]);

    printf("PASS\n");
    return 0;

out:

    printf("FAIL\n");
    return -1;
}

Test case 2:

           t0  t1
            \   /
             e0
            /   \
    (et) e1   e2 (et)
           |      |
     (lt) s0    s2 (lt)

When s0 and s2 are readable, both thread 0 and thread 1 can read an event from e0.

#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <sys/epoll.h>
#include <sys/socket.h>

static int efd[3];
static int sfd[4];
static int count;

static void *
thread_handler(void *data)

{
    struct epoll_event e;

    if (epoll_wait(efd[0], &e, 1, -1) == 1)
        count++;

    return NULL;
}

static void *
emit_handler(void *data)

{
    usleep (100000);

    write(sfd[1], "w", 1);
    write(sfd[3], "w", 1);

    return NULL;
}

int main(int argc, char *argv[])

{
    struct epoll_event e;
    pthread_t tw, te;

    if (socketpair(AF_UNIX, SOCK_STREAM, 0, &sfd[0]) < 0)
        goto out;

    if (socketpair(AF_UNIX, SOCK_STREAM, 0, &sfd[2]) < 0)
        goto out;

    efd[0] = epoll_create(1);
    if (efd[0] < 0)
        goto out;

    efd[1] = epoll_create(1);
    if (efd[1] < 0)
        goto out;

    efd[2] = epoll_create(1);
    if (efd[2] < 0)
        goto out;

    e.events = EPOLLIN;
    if (epoll_ctl(efd[1], EPOLL_CTL_ADD, sfd[0], &e) < 0)
        goto out;

    e.events = EPOLLIN;
    if (epoll_ctl(efd[2], EPOLL_CTL_ADD, sfd[2], &e) < 0)
        goto out;

    e.events = EPOLLIN | EPOLLET;
    if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[1], &e) < 0)
        goto out;

    e.events = EPOLLIN | EPOLLET;
    if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[2], &e) < 0)
        goto out;

    if (pthread_create(&tw, NULL, thread_handler, NULL) < 0)
        goto out;

    if (pthread_create(&te, NULL, emit_handler, NULL) < 0)
        goto out;

    if (epoll_wait(efd[0], &e, 1, -1) == 1)
        count++;

    if (pthread_join(tw, NULL) < 0)
        goto out;

    if (count != 2)
        goto out;

    close(efd[0]);
    close(efd[1]);
    close(efd[2]);
    close(sfd[0]);
    close(sfd[1]);
    close(sfd[2]);
    close(sfd[3]);

    printf ("PASS\n");
    return 0;

out:

    printf("FAIL\n");
    return -1;
}

t0: thread0
t1: thread1
e0: epoll0 (efd[0])
e1: epoll1 (efd[1])
e2: epoll2 (efd[2])
s0: socket0 (sfd[0])
s2: socket2 (sfd[2])

Quoted 7 lines

Is it possible to prove that this modification is correct, or any other corner cases are missing?

--
Best regards!
Hev
https://hev.cc

--
Best regards!
Hev
https://hev.cc

Signature · 3 lines
Best regards!
Hev
https://hev.cc
#8 lore raw
Quoted 148 lines · Heiher

Hi,

Quoted 144 lines · Heiher

Hi,

I created an epoll wakeup test project, listed some possible cases, and any other corner cases needs to be added?

https://github.com/heiher/epoll-wakeup/blob/master/README.md

Quoted 135 lines · Heiher

Hi,

Quoted 103 lines · Jason Baron
Quoted 83 lines · Roman Penyaev
Quoted 62 lines · Jason Baron
Quoted 61 lines · Roman Penyaev

Hi,

This is indeed a bug. (quick side note: could you please remove efd[1] from your test, because it is not related to the reproduction of a current bug).

Your patch lacks a good description, what exactly you've fixed. Let me speak out loud and please correct me if I'm wrong, my understanding of epoll internals has become a bit rusty: when epoll fds are nested an attempt to harvest events (ep_scan_ready_list() call) produces a second (repeated) event from an internal fd up to an external fd:

     epoll_wait(efd[0], ...):
       ep_send_events():
          ep_scan_ready_list(depth=0):
            ep_send_events_proc():
                ep_item_poll():
                  ep_scan_ready_list(depth=1):
                    ep_poll_safewake():
                      ep_poll_callback()
                        list_add_tail(&epi, &epi->rdllist);
                        ^^^^^^
                        repeated event

In your patch you forbid wakeup for the cases, where depth != 0, i.e. for all nested cases. That seems clear. But what if we can go further and remove the whole chunk, which seems excessive:

(quoted diff) +0 -5
@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
 
-
-       if (!list_empty(&ep->rdllist)) {
-               /*
-                * Wake up (if active) both the eventpoll wait list and
-                * the ->poll() wait list (delayed after we release the

lock).

(quoted diff) +0 -9
-                */
-               if (waitqueue_active(&ep->wq))
-                       wake_up(&ep->wq);
-               if (waitqueue_active(&ep->poll_wait))
-                       pwake++;
-       }
        write_unlock_irq(&ep->lock);
 
        if (!ep_locked)
                mutex_unlock(&ep->mtx);
 
-       /* We have to call this outside the lock */
-       if (pwake)
-               ep_poll_safewake(&ep->poll_wait);

I reason like that: by the time we've reached the point of scanning events for readiness all wakeups from ep_poll_callback have been already fired and new events have been already accounted in ready list (ep_poll_callback() calls
the same ep_poll_safewake()). Here, frankly, I'm not 100% sure and probably missing some corner cases.

Quoted 8 lines
Quoted 1 line

Thoughts?

So the: 'wake_up(&ep->wq);' part, I think is about waking up other threads that may be in waiting in epoll_wait(). For example, there may be multiple threads doing epoll_wait() on the same epoll fd, and the logic above seems to say thread 1 may have processed say N events and now its going to to go off to work those, so let's wake up thread 2 now to handle the next chunk.

Not quite. Thread which calls ep_scan_ready_list() processes all the events, and while processing those, removes them one by one from the ready list. But if event mask is !0 and event belongs to Level Triggered Mode descriptor (let's say default mode) it tails event again back to the list (because we are in level mode, so event should be there). So at the end of this traversing loop ready list is likely not empty, and if so, wake up again is called for nested epoll fds. But, those nested epoll fds should get already all the notifications from the main event callback ep_poll_callback(), regardless any thread which traverses events.

Quoted 5 lines

I suppose this logic exists for decades, when Davide (the author) was reshuffling the code here and there.

But I do not feel confidence to state that this extra wakeup is bogus, I just have a gut feeling that it looks excessive.

Note that I was talking about the wakeup done on ep->wq not ep->poll_wait. The path that I'm concerned about is let's say that there are N events queued on the ready list. A thread that was woken up in epoll_wait may decide to only process say N/2 of then. Then it will call wakeup on ep->wq and this will wakeup another thread to process the remaining N/2. Without the wakeup, the original thread isn't going to process the events until it finishes with the original N/2 and gets back to epoll_wait(). So I'm not sure how important that path is but I wanted to at least note the change here would impact that behavior.

Quoted 24 lines

Thanks,

-Jason

Quoted 19 lines
Quoted 6 lines

So I think removing all that even for the
depth 0 case is going to change some behavior here. So perhaps, it should be removed for all depths except for 0? And if so, it may be better to make 2 patches here to separate these changes.

Quoted 6 lines

For the nested wakeups, I agree that the extra wakeups seem unnecessary and it may make sense to remove them for all depths. I don't think the nested epoll semantics are particularly well spelled out, and afaict, nested epoll() has behaved this way for quite some time. And the current behavior is not bad in the way that a missing wakeup or false negative would be.

That's 100% true! For edge mode extra wake up is not a bug, not optimal for userspace - yes, but that can't lead to any lost wakeups.

--
Roman

I tried to remove the whole chunk of code that Roman said, and it seems that there
are no obvious problems with the two test programs below:

Quoted 5 lines

I recall this message, the test case 9/25/26 of epoll-wakeup (on github) are failed while
the whole chunk are removed.

Apply the original patch, all tests passed.

These are failing on my bare 5.2.0-rc2

TEST  bin/epoll31       FAIL
TEST  bin/epoll46       FAIL
TEST  bin/epoll50       FAIL
TEST  bin/epoll32       FAIL
TEST  bin/epoll19       FAIL
TEST  bin/epoll27       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll20       FAIL
TEST  bin/epoll28       FAIL
TEST  bin/epoll38       FAIL
TEST  bin/epoll52       FAIL
TEST  bin/epoll24       FAIL
TEST  bin/epoll23       FAIL

These are failing if your patch is applied:
(my 5.2.0-rc2 is old? broken?)

TEST  bin/epoll46       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL

These are failing if "ep_poll_safewake(&ep->poll_wait)" is not called, but wakeup(&ep->wq); is still invoked:

TEST  bin/epoll46       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL

So at least 48 has been "fixed".

These are failing if the whole chunk is removed, like your said 9,25,26 are among which do not pass:

TEST  bin/epoll26       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll9        FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll25       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL

This can be a good test suite, probably can be added to kselftests?

--
Roman

#9 lore raw
Quoted 258 lines · Roman Penyaev
Quoted 194 lines · Heiher

Hi,

Quoted 173 lines · Heiher

Hi,

I created an epoll wakeup test project, listed some possible cases, and any other corner cases needs to be added?

https://github.com/heiher/epoll-wakeup/blob/master/README.md

Quoted 13 lines · Heiher

Hi,

Quoted 9 lines · Jason Baron
Quoted 5 lines · Roman Penyaev
Quoted 4 lines · Jason Baron
Quoted 3 lines · Roman Penyaev

Hi,

This is indeed a bug. (quick side note: could you please

remove efd[1]

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

from your test, because it is not related to the reproduction

of a

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

current bug).

Your patch lacks a good description, what exactly you've

fixed.  Let

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

me speak out loud and please correct me if I'm wrong, my

understanding

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

of epoll internals has become a bit rusty: when epoll fds are

nested

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

an attempt to harvest events (ep_scan_ready_list() call)

produces a

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

second (repeated) event from an internal fd up to an external

fd:

Quoted 14 lines
Quoted 14 lines
Quoted 14 lines
Quoted 14 lines
Quoted 14 lines

      epoll_wait(efd[0], ...):
        ep_send_events():
           ep_scan_ready_list(depth=0):
             ep_send_events_proc():
                 ep_item_poll():
                   ep_scan_ready_list(depth=1):
                     ep_poll_safewake():
                       ep_poll_callback() list_add_tail(&epi, &epi->rdllist); ^^^^^^
                         repeated event

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

In your patch you forbid wakeup for the cases, where depth !=

0, i.e.

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

for all nested cases. That seems clear.  But what if we can

go further

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
Quoted 9 lines

Review static __poll_t ep_scan_ready_list(struct · line 890

Quoted 9 lines

and remove the whole chunk, which seems excessive:

(quoted diff) +0 -4
@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
 
-
-       if (!list_empty(&ep->rdllist)) {
-               /*
-                * Wake up (if active) both the eventpoll

wait list and

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Review static __poll_t ep_scan_ready_list(struct · line 891

Quoted 1 line
(quoted diff) +0 -1
-                * the ->poll() wait list (delayed after we

release the

Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
Quoted 12 lines

lock).
-                */
-               if (waitqueue_active(&ep->wq)) -                       wake_up(&ep->wq);
-               if (waitqueue_active(&ep->poll_wait)) -                       pwake++;
-       }
         write_unlock_irq(&ep->lock);

         if (!ep_locked)
                 mutex_unlock(&ep->mtx);

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

-       /* We have to call this outside the lock */ -       if (pwake)
-               ep_poll_safewake(&ep->poll_wait);

I reason like that: by the time we've reached the point of

scanning events

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

for readiness all wakeups from ep_poll_callback have been

already fired and

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

new events have been already accounted in ready list

(ep_poll_callback()

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

calls
the same ep_poll_safewake()). Here, frankly, I'm not 100%

sure and probably

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 3 lines

missing some corner cases.

Thoughts?

So the: 'wake_up(&ep->wq);' part, I think is about waking up

other

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

threads that may be in waiting in epoll_wait(). For example,

there may

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

be multiple threads doing epoll_wait() on the same epoll fd,

and the

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

logic above seems to say thread 1 may have processed say N

events and

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

now its going to to go off to work those, so let's wake up

thread 2 now

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 1 line

to handle the next chunk.

Not quite. Thread which calls ep_scan_ready_list() processes

all the

Quoted 1 line
Quoted 1 line
Quoted 1 line

events, and while processing those, removes them one by one

from the

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

ready list.  But if event mask is !0 and event belongs to Level Triggered Mode descriptor (let's say default mode) it

tails event

Quoted 1 line
Quoted 1 line
Quoted 1 line

again back to the list (because we are in level mode, so event

should

Quoted 1 line
Quoted 1 line
Quoted 1 line

be there).  So at the end of this traversing loop ready list is

likely

Quoted 1 line
Quoted 1 line
Quoted 1 line

not empty, and if so, wake up again is called for nested epoll

fds.

Quoted 1 line
Quoted 1 line
Quoted 1 line

But, those nested epoll fds should get already all the

notifications

Quoted 1 line
Quoted 1 line
Quoted 1 line

from the main event callback ep_poll_callback(), regardless any

thread

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

which traverses events.

I suppose this logic exists for decades, when Davide (the

author) was

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

reshuffling the code here and there.

But I do not feel confidence to state that this extra wakeup is

bogus,

Quoted 3 lines
Quoted 3 lines
Quoted 1 line

I just have a gut feeling that it looks excessive.

Note that I was talking about the wakeup done on ep->wq not

ep->poll_wait.

Quoted 1 line
Quoted 1 line

The path that I'm concerned about is let's say that there are N

events

Quoted 1 line
Quoted 1 line

queued on the ready list. A thread that was woken up in

epoll_wait may

Quoted 1 line
Quoted 1 line

decide to only process say N/2 of then. Then it will call wakeup

on ep->wq

Quoted 1 line
Quoted 1 line

and this will wakeup another thread to process the remaining N/2.

Without

Quoted 1 line
Quoted 1 line

the wakeup, the original thread isn't going to process the events

until

Quoted 1 line
Quoted 1 line

it finishes with the original N/2 and gets back to epoll_wait().

So I'm not

Quoted 1 line
Quoted 1 line

sure how important that path is but I wanted to at least note the

change

Quoted 10 lines
Quoted 10 lines

here would impact that behavior.

Thanks,

-Jason

Quoted 3 lines
Quoted 3 lines

So I think removing all that even for the depth 0 case is going to change some behavior here. So

perhaps, it

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

should be removed for all depths except for 0? And if so, it

may be

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

better to make 2 patches here to separate these changes.

For the nested wakeups, I agree that the extra wakeups seem

unnecessary

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

and it may make sense to remove them for all depths. I don't

think the

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

nested epoll semantics are particularly well spelled out, and

afaict,

Quoted 17 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

nested epoll() has behaved this way for quite some time. And

the current

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

behavior is not bad in the way that a missing wakeup or false

negative

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 1 line

would be.

That's 100% true! For edge mode extra wake up is not a bug, not

optimal

Quoted 9 lines
Quoted 5 lines
Quoted 5 lines

for userspace - yes, but that can't lead to any lost wakeups.

--
Roman

I tried to remove the whole chunk of code that Roman said, and it seems that there
are no obvious problems with the two test programs below:

Quoted 5 lines

I recall this message, the test case 9/25/26 of epoll-wakeup (on github) are failed while
the whole chunk are removed.

Apply the original patch, all tests passed.

These are failing on my bare 5.2.0-rc2

TEST  bin/epoll31       FAIL
TEST  bin/epoll46       FAIL
TEST  bin/epoll50       FAIL
TEST  bin/epoll32       FAIL
TEST  bin/epoll19       FAIL
TEST  bin/epoll27       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll20       FAIL
TEST  bin/epoll28       FAIL
TEST  bin/epoll38       FAIL
TEST  bin/epoll52       FAIL
TEST  bin/epoll24       FAIL
TEST  bin/epoll23       FAIL

These are failing if your patch is applied:
(my 5.2.0-rc2 is old? broken?)

TEST  bin/epoll46       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL

These are failing if "ep_poll_safewake(&ep->poll_wait)" is not called, but wakeup(&ep->wq); is still invoked:

TEST  bin/epoll46       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL

So at least 48 has been "fixed".

These are failing if the whole chunk is removed, like your said 9,25,26 are among which do not pass:

TEST  bin/epoll26       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll9        FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll25       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL

Quoted 5 lines

This can be a good test suite, probably can be added to kselftests?

Signature · 1 line
Roman

Indeed, I just tried the same test suite and I am seeing similar failures - it looks like its a bit timing dependent. It looks like all the failures are caused by a similar issue. For example, take epoll34:

         t0   t1
     (ew) |    | (ew)
         e0    |
      (lt) \  /
             |
            e1
             | (et)
            s0

The test is trying to assert that an epoll_wait() on e1 and and epoll_wait() on e0 both return 1 event for EPOLLIN. However, the epoll_wait on e1 is done in a thread and it can happen before or after the epoll_wait() is called against e0. If the epoll_wait() on e1 happens first then because its attached as 'et', it consumes the event. So that there is no longer an event reported at e0. I think that is reasonable semantics here. However if the wait on e0 happens after the wait on e1 then the test will pass as both waits will see the event. Thus, a patch like this will 'fix' this testcase:

src/epoll34.c +3 -3
@@ -59,15 +59,15 @@ int main(int argc, char *argv[])
        if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[1], &e) < 0)
                goto out;
 
-       if (pthread_create(&tw, NULL, thread_handler, NULL) < 0)
-               goto out;
-
        if (pthread_create(&te, NULL, emit_handler, NULL) < 0)
                goto out;
 
        if (epoll_wait(efd[0], &e, 1, 500) == 1)
                count++;
 
+       if (pthread_create(&tw, NULL, thread_handler, NULL) < 0)
+               goto out;
+
        if (pthread_join(tw, NULL) < 0)
                goto out;
 

I found all the other failures to be of similar origin. I suspect Heiher didn't see failures due to the thread timings here.

I also found that all the testcases pass if we leave the wakeup(&ep->wq) call for the depth 0 case (and remove the pwake part).

Thanks,

-Jason

author
#10 lore raw

Hi,

Quoted 262 lines · Jason Baron
Quoted 258 lines · Roman Penyaev
Quoted 194 lines · Heiher

Hi,

Quoted 173 lines · Heiher

Hi,

I created an epoll wakeup test project, listed some possible cases, and any other corner cases needs to be added?

https://github.com/heiher/epoll-wakeup/blob/master/README.md

Quoted 13 lines · Heiher

Hi,

Quoted 9 lines · Jason Baron
Quoted 5 lines · Roman Penyaev
Quoted 4 lines · Jason Baron
Quoted 3 lines · Roman Penyaev

Hi,

This is indeed a bug. (quick side note: could you please

remove efd[1]

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

from your test, because it is not related to the reproduction

of a

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

current bug).

Your patch lacks a good description, what exactly you've

fixed. Let

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

me speak out loud and please correct me if I'm wrong, my

understanding

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

of epoll internals has become a bit rusty: when epoll fds are

nested

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

an attempt to harvest events (ep_scan_ready_list() call)

produces a

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

second (repeated) event from an internal fd up to an external

fd:

Quoted 14 lines
Quoted 14 lines
Quoted 14 lines
Quoted 14 lines
Quoted 14 lines
     epoll_wait(efd[0], ...):
       ep_send_events():
          ep_scan_ready_list(depth=0):
            ep_send_events_proc():
                ep_item_poll():
                  ep_scan_ready_list(depth=1):
                    ep_poll_safewake():
                      ep_poll_callback()
                        list_add_tail(&epi, &epi->rdllist);
                        ^^^^^^
                        repeated event
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

In your patch you forbid wakeup for the cases, where depth !=

0, i.e.

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

for all nested cases. That seems clear. But what if we can

go further

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
Quoted 9 lines

Review static __poll_t ep_scan_ready_list(struct · line 890

Quoted 9 lines

and remove the whole chunk, which seems excessive:

(quoted diff) +0 -4
@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
 
-
-       if (!list_empty(&ep->rdllist)) {
-               /*
-                * Wake up (if active) both the eventpoll

wait list and

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Review static __poll_t ep_scan_ready_list(struct · line 891

Quoted 1 line
(quoted diff) +0 -1
-                * the ->poll() wait list (delayed after we

release the

Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
Quoted 12 lines

lock).

(quoted diff) +0 -6
-                */
-               if (waitqueue_active(&ep->wq))
-                       wake_up(&ep->wq);
-               if (waitqueue_active(&ep->poll_wait))
-                       pwake++;
-       }
        write_unlock_irq(&ep->lock);
 
        if (!ep_locked)
                mutex_unlock(&ep->mtx);
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
(quoted diff) +0 -3
-       /* We have to call this outside the lock */
-       if (pwake)
-               ep_poll_safewake(&ep->poll_wait);

I reason like that: by the time we've reached the point of

scanning events

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

for readiness all wakeups from ep_poll_callback have been

already fired and

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

new events have been already accounted in ready list

(ep_poll_callback()

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

calls
the same ep_poll_safewake()). Here, frankly, I'm not 100%

sure and probably

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 3 lines

missing some corner cases.

Thoughts?

So the: 'wake_up(&ep->wq);' part, I think is about waking up

other

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

threads that may be in waiting in epoll_wait(). For example,

there may

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

be multiple threads doing epoll_wait() on the same epoll fd,

and the

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

logic above seems to say thread 1 may have processed say N

events and

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

now its going to to go off to work those, so let's wake up

thread 2 now

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 1 line

to handle the next chunk.

Not quite. Thread which calls ep_scan_ready_list() processes

all the

Quoted 1 line
Quoted 1 line
Quoted 1 line

events, and while processing those, removes them one by one

from the

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

ready list. But if event mask is !0 and event belongs to Level Triggered Mode descriptor (let's say default mode) it

tails event

Quoted 1 line
Quoted 1 line
Quoted 1 line

again back to the list (because we are in level mode, so event

should

Quoted 1 line
Quoted 1 line
Quoted 1 line

be there). So at the end of this traversing loop ready list is

likely

Quoted 1 line
Quoted 1 line
Quoted 1 line

not empty, and if so, wake up again is called for nested epoll

fds.

Quoted 1 line
Quoted 1 line
Quoted 1 line

But, those nested epoll fds should get already all the

notifications

Quoted 1 line
Quoted 1 line
Quoted 1 line

from the main event callback ep_poll_callback(), regardless any

thread

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

which traverses events.

I suppose this logic exists for decades, when Davide (the

author) was

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

reshuffling the code here and there.

But I do not feel confidence to state that this extra wakeup is

bogus,

Quoted 3 lines
Quoted 3 lines
Quoted 1 line

I just have a gut feeling that it looks excessive.

Note that I was talking about the wakeup done on ep->wq not

ep->poll_wait.

Quoted 1 line
Quoted 1 line

The path that I'm concerned about is let's say that there are N

events

Quoted 1 line
Quoted 1 line

queued on the ready list. A thread that was woken up in

epoll_wait may

Quoted 1 line
Quoted 1 line

decide to only process say N/2 of then. Then it will call wakeup

on ep->wq

Quoted 1 line
Quoted 1 line

and this will wakeup another thread to process the remaining N/2.

Without

Quoted 1 line
Quoted 1 line

the wakeup, the original thread isn't going to process the events

until

Quoted 1 line
Quoted 1 line

it finishes with the original N/2 and gets back to epoll_wait().

So I'm not

Quoted 1 line
Quoted 1 line

sure how important that path is but I wanted to at least note the

change

Quoted 10 lines
Quoted 10 lines

here would impact that behavior.

Thanks,

-Jason

Quoted 3 lines
Quoted 3 lines

So I think removing all that even for the depth 0 case is going to change some behavior here. So

perhaps, it

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

should be removed for all depths except for 0? And if so, it

may be

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

better to make 2 patches here to separate these changes.

For the nested wakeups, I agree that the extra wakeups seem

unnecessary

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

and it may make sense to remove them for all depths. I don't

think the

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

nested epoll semantics are particularly well spelled out, and

afaict,

Quoted 17 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

nested epoll() has behaved this way for quite some time. And

the current

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

behavior is not bad in the way that a missing wakeup or false

negative

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 1 line

would be.

That's 100% true! For edge mode extra wake up is not a bug, not

optimal

Quoted 9 lines
Quoted 5 lines
Quoted 5 lines

for userspace - yes, but that can't lead to any lost wakeups.

--
Roman

I tried to remove the whole chunk of code that Roman said, and it seems that there
are no obvious problems with the two test programs below:

Quoted 5 lines

I recall this message, the test case 9/25/26 of epoll-wakeup (on github) are failed while
the whole chunk are removed.

Apply the original patch, all tests passed.

These are failing on my bare 5.2.0-rc2

TEST  bin/epoll31       FAIL
TEST  bin/epoll46       FAIL
TEST  bin/epoll50       FAIL
TEST  bin/epoll32       FAIL
TEST  bin/epoll19       FAIL
TEST  bin/epoll27       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll20       FAIL
TEST  bin/epoll28       FAIL
TEST  bin/epoll38       FAIL
TEST  bin/epoll52       FAIL
TEST  bin/epoll24       FAIL
TEST  bin/epoll23       FAIL

These are failing if your patch is applied:
(my 5.2.0-rc2 is old? broken?)

TEST  bin/epoll46       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL

These are failing if "ep_poll_safewake(&ep->poll_wait)" is not called, but wakeup(&ep->wq); is still invoked:

TEST  bin/epoll46       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL

So at least 48 has been "fixed".

These are failing if the whole chunk is removed, like your said 9,25,26 are among which do not pass:

TEST  bin/epoll26       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll9        FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll25       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL
Quoted 1 line
Quoted 1 line

This can be a good test suite, probably can be added to kselftests?

Thank you, I have updated epoll-tests to fix these issues. I think this is good news if we can added to kselftests. ;)

Quoted 52 lines
Quoted 4 lines

--
Roman

Indeed, I just tried the same test suite and I am seeing similar failures - it looks like its a bit timing dependent. It looks like all the failures are caused by a similar issue. For example, take epoll34:

         t0   t1
     (ew) |    | (ew)
         e0    |
      (lt) \  /
             |
            e1
             | (et)
            s0

The test is trying to assert that an epoll_wait() on e1 and and epoll_wait() on e0 both return 1 event for EPOLLIN. However, the epoll_wait on e1 is done in a thread and it can happen before or after the epoll_wait() is called against e0. If the epoll_wait() on e1 happens first then because its attached as 'et', it consumes the event. So that there is no longer an event reported at e0. I think that is reasonable semantics here. However if the wait on e0 happens after the wait on e1 then the test will pass as both waits will see the event. Thus, a patch like this will 'fix' this testcase:

src/epoll34.c +3 -3
@@ -59,15 +59,15 @@ int main(int argc, char *argv[])
        if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[1], &e) < 0)
                goto out;
 
-       if (pthread_create(&tw, NULL, thread_handler, NULL) < 0)
-               goto out;
-
        if (pthread_create(&te, NULL, emit_handler, NULL) < 0)
                goto out;
 
        if (epoll_wait(efd[0], &e, 1, 500) == 1)
                count++;
 
+       if (pthread_create(&tw, NULL, thread_handler, NULL) < 0)
+               goto out;
+
        if (pthread_join(tw, NULL) < 0)
                goto out;
 
Quoted 2 lines

I found all the other failures to be of similar origin. I suspect Heiher didn't see failures due to the thread timings here.

Thank you. I also found a multi-threaded concurrent accumulation problem, and that has been changed to atomic operations. I think we should allow two different behaviors to be passed because they are all correctly.

thread 2:
if (epoll_wait(efd[1], &e, 1, 500) == 1)

    __sync_fetch_and_or(&count, 1);

thread1:
if (epoll_wait(efd[0], &e, 1, 500) == 1)

    __sync_fetch_and_or(&count, 2);

check:
if ((count != 1) && (count != 3))

    goto out;
Quoted 3 lines

I also found that all the testcases pass if we leave the wakeup(&ep->wq) call for the depth 0 case (and remove the pwake part).

So, We need to keep the wakeup(&ep-wq) for all depth, and only wakeup(&ep->poll_wait)
for depth 0 and/or ep->rdlist from empty to be not empty?

Quoted 8 lines

Thanks,

-Jason

Signature · 3 lines
Best regards!
Hev
https://hev.cc
#11 lore raw
Quoted 342 lines · Heiher

Hi,

Quoted 262 lines · Jason Baron
Quoted 258 lines · Roman Penyaev
Quoted 194 lines · Heiher

Hi,

Quoted 173 lines · Heiher

Hi,

I created an epoll wakeup test project, listed some possible cases, and any other corner cases needs to be added?

https://github.com/heiher/epoll-wakeup/blob/master/README.md

Quoted 13 lines · Heiher

Hi,

Quoted 9 lines · Jason Baron
Quoted 5 lines · Roman Penyaev
Quoted 4 lines · Jason Baron
Quoted 3 lines · Roman Penyaev

Hi,

This is indeed a bug. (quick side note: could you please

remove efd[1]

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

from your test, because it is not related to the reproduction

of a

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

current bug).

Your patch lacks a good description, what exactly you've

fixed. Let

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

me speak out loud and please correct me if I'm wrong, my

understanding

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

of epoll internals has become a bit rusty: when epoll fds are

nested

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

an attempt to harvest events (ep_scan_ready_list() call)

produces a

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

second (repeated) event from an internal fd up to an external

fd:

Quoted 14 lines
Quoted 14 lines
Quoted 14 lines
Quoted 14 lines
Quoted 14 lines
     epoll_wait(efd[0], ...):
       ep_send_events():
          ep_scan_ready_list(depth=0):
            ep_send_events_proc():
                ep_item_poll():
                  ep_scan_ready_list(depth=1):
                    ep_poll_safewake():
                      ep_poll_callback()
                        list_add_tail(&epi, &epi->rdllist);
                        ^^^^^^
                        repeated event
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

In your patch you forbid wakeup for the cases, where depth !=

0, i.e.

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

for all nested cases. That seems clear. But what if we can

go further

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
Quoted 9 lines

Review static __poll_t ep_scan_ready_list(struct · line 890

Quoted 9 lines

and remove the whole chunk, which seems excessive:

(quoted diff) +0 -4
@@ -885,26 +886,11 @@ static __poll_t ep_scan_ready_list(struct
 eventpoll *ep,
 
-
-       if (!list_empty(&ep->rdllist)) {
-               /*
-                * Wake up (if active) both the eventpoll

wait list and

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Review static __poll_t ep_scan_ready_list(struct · line 891

Quoted 1 line
(quoted diff) +0 -1
-                * the ->poll() wait list (delayed after we

release the

Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
Quoted 12 lines

lock).

(quoted diff) +0 -6
-                */
-               if (waitqueue_active(&ep->wq))
-                       wake_up(&ep->wq);
-               if (waitqueue_active(&ep->poll_wait))
-                       pwake++;
-       }
        write_unlock_irq(&ep->lock);
 
        if (!ep_locked)
                mutex_unlock(&ep->mtx);
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
(quoted diff) +0 -3
-       /* We have to call this outside the lock */
-       if (pwake)
-               ep_poll_safewake(&ep->poll_wait);

I reason like that: by the time we've reached the point of

scanning events

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

for readiness all wakeups from ep_poll_callback have been

already fired and

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

new events have been already accounted in ready list

(ep_poll_callback()

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

calls
the same ep_poll_safewake()). Here, frankly, I'm not 100%

sure and probably

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 3 lines

missing some corner cases.

Thoughts?

So the: 'wake_up(&ep->wq);' part, I think is about waking up

other

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

threads that may be in waiting in epoll_wait(). For example,

there may

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

be multiple threads doing epoll_wait() on the same epoll fd,

and the

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

logic above seems to say thread 1 may have processed say N

events and

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

now its going to to go off to work those, so let's wake up

thread 2 now

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 1 line

to handle the next chunk.

Not quite. Thread which calls ep_scan_ready_list() processes

all the

Quoted 1 line
Quoted 1 line
Quoted 1 line

events, and while processing those, removes them one by one

from the

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

ready list. But if event mask is !0 and event belongs to Level Triggered Mode descriptor (let's say default mode) it

tails event

Quoted 1 line
Quoted 1 line
Quoted 1 line

again back to the list (because we are in level mode, so event

should

Quoted 1 line
Quoted 1 line
Quoted 1 line

be there). So at the end of this traversing loop ready list is

likely

Quoted 1 line
Quoted 1 line
Quoted 1 line

not empty, and if so, wake up again is called for nested epoll

fds.

Quoted 1 line
Quoted 1 line
Quoted 1 line

But, those nested epoll fds should get already all the

notifications

Quoted 1 line
Quoted 1 line
Quoted 1 line

from the main event callback ep_poll_callback(), regardless any

thread

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

which traverses events.

I suppose this logic exists for decades, when Davide (the

author) was

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

reshuffling the code here and there.

But I do not feel confidence to state that this extra wakeup is

bogus,

Quoted 3 lines
Quoted 3 lines
Quoted 1 line

I just have a gut feeling that it looks excessive.

Note that I was talking about the wakeup done on ep->wq not

ep->poll_wait.

Quoted 1 line
Quoted 1 line

The path that I'm concerned about is let's say that there are N

events

Quoted 1 line
Quoted 1 line

queued on the ready list. A thread that was woken up in

epoll_wait may

Quoted 1 line
Quoted 1 line

decide to only process say N/2 of then. Then it will call wakeup

on ep->wq

Quoted 1 line
Quoted 1 line

and this will wakeup another thread to process the remaining N/2.

Without

Quoted 1 line
Quoted 1 line

the wakeup, the original thread isn't going to process the events

until

Quoted 1 line
Quoted 1 line

it finishes with the original N/2 and gets back to epoll_wait().

So I'm not

Quoted 1 line
Quoted 1 line

sure how important that path is but I wanted to at least note the

change

Quoted 10 lines
Quoted 10 lines

here would impact that behavior.

Thanks,

-Jason

Quoted 3 lines
Quoted 3 lines

So I think removing all that even for the depth 0 case is going to change some behavior here. So

perhaps, it

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

should be removed for all depths except for 0? And if so, it

may be

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

better to make 2 patches here to separate these changes.

For the nested wakeups, I agree that the extra wakeups seem

unnecessary

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

and it may make sense to remove them for all depths. I don't

think the

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

nested epoll semantics are particularly well spelled out, and

afaict,

Quoted 17 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

nested epoll() has behaved this way for quite some time. And

the current

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

behavior is not bad in the way that a missing wakeup or false

negative

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 1 line

would be.

That's 100% true! For edge mode extra wake up is not a bug, not

optimal

Quoted 9 lines
Quoted 5 lines
Quoted 5 lines

for userspace - yes, but that can't lead to any lost wakeups.

--
Roman

I tried to remove the whole chunk of code that Roman said, and it seems that there
are no obvious problems with the two test programs below:

Quoted 5 lines

I recall this message, the test case 9/25/26 of epoll-wakeup (on github) are failed while
the whole chunk are removed.

Apply the original patch, all tests passed.

These are failing on my bare 5.2.0-rc2

TEST  bin/epoll31       FAIL
TEST  bin/epoll46       FAIL
TEST  bin/epoll50       FAIL
TEST  bin/epoll32       FAIL
TEST  bin/epoll19       FAIL
TEST  bin/epoll27       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll20       FAIL
TEST  bin/epoll28       FAIL
TEST  bin/epoll38       FAIL
TEST  bin/epoll52       FAIL
TEST  bin/epoll24       FAIL
TEST  bin/epoll23       FAIL

These are failing if your patch is applied:
(my 5.2.0-rc2 is old? broken?)

TEST  bin/epoll46       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL

These are failing if "ep_poll_safewake(&ep->poll_wait)" is not called, but wakeup(&ep->wq); is still invoked:

TEST  bin/epoll46       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL

So at least 48 has been "fixed".

These are failing if the whole chunk is removed, like your said 9,25,26 are among which do not pass:

TEST  bin/epoll26       FAIL
TEST  bin/epoll42       FAIL
TEST  bin/epoll34       FAIL
TEST  bin/epoll9        FAIL
TEST  bin/epoll48       FAIL
TEST  bin/epoll40       FAIL
TEST  bin/epoll25       FAIL
TEST  bin/epoll44       FAIL
TEST  bin/epoll38       FAIL
Quoted 1 line
Quoted 1 line

This can be a good test suite, probably can be added to kselftests?

Thank you, I have updated epoll-tests to fix these issues. I think this is good news if we can added to kselftests. ;)

Quoted 52 lines
Quoted 4 lines

--
Roman

Indeed, I just tried the same test suite and I am seeing similar failures - it looks like its a bit timing dependent. It looks like all the failures are caused by a similar issue. For example, take epoll34:

         t0   t1
     (ew) |    | (ew)
         e0    |
      (lt) \  /
             |
            e1
             | (et)
            s0

The test is trying to assert that an epoll_wait() on e1 and and epoll_wait() on e0 both return 1 event for EPOLLIN. However, the epoll_wait on e1 is done in a thread and it can happen before or after the epoll_wait() is called against e0. If the epoll_wait() on e1 happens first then because its attached as 'et', it consumes the event. So that there is no longer an event reported at e0. I think that is reasonable semantics here. However if the wait on e0 happens after the wait on e1 then the test will pass as both waits will see the event. Thus, a patch like this will 'fix' this testcase:

src/epoll34.c +3 -3
@@ -59,15 +59,15 @@ int main(int argc, char *argv[])
        if (epoll_ctl(efd[0], EPOLL_CTL_ADD, efd[1], &e) < 0)
                goto out;
 
-       if (pthread_create(&tw, NULL, thread_handler, NULL) < 0)
-               goto out;
-
        if (pthread_create(&te, NULL, emit_handler, NULL) < 0)
                goto out;
 
        if (epoll_wait(efd[0], &e, 1, 500) == 1)
                count++;
 
+       if (pthread_create(&tw, NULL, thread_handler, NULL) < 0)
+               goto out;
+
        if (pthread_join(tw, NULL) < 0)
                goto out;
 
Quoted 2 lines

I found all the other failures to be of similar origin. I suspect Heiher didn't see failures due to the thread timings here.

Thank you. I also found a multi-threaded concurrent accumulation problem, and that has been changed to atomic operations. I think we should allow two different behaviors to be passed because they are all correctly.

thread 2:
if (epoll_wait(efd[1], &e, 1, 500) == 1)

    __sync_fetch_and_or(&count, 1);

thread1:
if (epoll_wait(efd[0], &e, 1, 500) == 1)

    __sync_fetch_and_or(&count, 2);

check:
if ((count != 1) && (count != 3))

    goto out;
Quoted 1 line
Quoted 7 lines
Quoted 2 lines

I also found that all the testcases pass if we leave the wakeup(&ep->wq) call for the depth 0 case (and remove the pwake part).

So, We need to keep the wakeup(&ep-wq) for all depth, and only wakeup(&ep->poll_wait)
for depth 0 and/or ep->rdlist from empty to be not empty?

Yes, so my thinking is yes, leave the wakeup(&ep->wq) for all depths. It may not strictly be necessary for depths > 0 but I do have some concerns about it and doesn't affect this specific case. So I would leave it for all depths and if you want to remove it for depths > 0, its a separate patch.

I'm now not sure its really safe to remove the wakeup(&ep->poll_wait) either. Take the case where we have:

       (et)  (lt)

t0---e0---e1----s0

Let's say there is thread t1 also doing epoll_wait() on e1. Now, let's say s0 fires an event and wakes up t1. While t1 is reaping events from t1 its calling ep_scan_ready_list() and while its processing the events it drops the ep->lock and more events get queued to the overflow list. Now, let's say t0 wakes up from epoll_wait() it will not see any of the events queued to e1 yet (since they are not on the readylist yet). Thus, t0 goes back to sleep and I think can miss an event here. So I think that's what the wakeup(&ep->poll_wait) is about.

What I think we can do to fix the original case, is that perhaps in that case where events get queued to the overflow list we do in fact do the wakeup(&ep->poll_wait). So perhaps, we can just have variable that checks if there is anything in the overflow list, and if so do the wakeup(&ep->poll_wait) conditional on there being things on the overflow list. Although I can't say I tried to see if this would work.

That said, I think ep_modify() might also subtlety be dependent on the current behavior, in that ep_item_poll() uses ep_scan_ready_list() and when an event is modified it may need to wakeup nested epoll fds to inform them of events. Thus, perhaps, we would also need an explicit call to wakeup(&ep->poll_wait) when ep_item_poll() returns events.

Thanks,

-Jason