Re: [PATCH v2] epoll: Support for disabling items, and a self-test app.

[CC += linux-api@]

Hello Paton,

On Thu, Aug 23, 2012 at 11:15 PM, Paton J. Lewis [off-list ref] wrote:

From: "Paton J. Lewis" <redacted>

Enhanced epoll_ctl to support EPOLL_CTL_DISABLE, which disables an epoll item.
If epoll_ctl doesn't return -EBUSY in this case, it is then safe to delete the
epoll item in a multi-threaded environment. Also added a new test_epoll self-
test app to both demonstrate the need for this feature and test it.

(There's a lot of background missing from this version of the patch
that was included in the previous version
[http://thread.gmane.org/gmane.linux.kernel/1311457]. It helps to
include the full rationale with a revised patch--best not to assume
that someone has the context of past mails when reading a revised
patch.)

I've taken a look at this patch as it currently stands in 3.7-rc1, and
done a bit of testing. (By the way, the test program
tools/testing/selftests/epoll/test_epoll.c does not compile...)

There are one or two places where the behavior seems a little strange,
so I have a question or two at the end of this mail. But other than
that, I want to check my understanding so that the interface can be
correctly documented.

Just to go though my understanding, the problem is the following
scenario in a multithreaded application:

1. Multiple threads are performing epoll_wait() operations,
   and maintaining a user-space cache that contains information
   corresponding to each file descriptor being monitored by
   epoll_wait().

2. At some point, a thread wants to delete (EPOLL_CTL_DEL)
   a file descriptor from the epoll interest list, and
   delete the corresponding record from the user-space cache.

3. The problem with (2) is that some other thread may have
   previously done an epoll_wait() that retrieved information
   about the fd in question, and may be in the middle of using
   information in the cache that relates to that fd. Thus,
   there is a potential race.

4. The race can't solved purely in user space, because doing
   so would require applying a mutex across the epoll_wait()
   call, which would of course blow thread concurrency.

Right?

67 more lines

432 more quoted lines

-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Author of "The Linux Programming Interface"; http://man7.org/tlpi/

On Tue, 16 Oct 2012 17:12:57 +0200
"Michael Kerrisk (man-pages)" [off-list ref] wrote:

On Thu, Aug 23, 2012 at 11:15 PM, Paton J. Lewis [off-list ref] wrote:

quoted

From: "Paton J. Lewis" <redacted>

Enhanced epoll_ctl to support EPOLL_CTL_DISABLE, which disables an epoll item.
If epoll_ctl doesn't return -EBUSY in this case, it is then safe to delete the
epoll item in a multi-threaded environment. Also added a new test_epoll self-
test app to both demonstrate the need for this feature and test it.

(There's a lot of background missing from this version of the patch
that was included in the previous version
[http://thread.gmane.org/gmane.linux.kernel/1311457]. It helps to
include the full rationale with a revised patch--best not to assume
that someone has the context of past mails when reading a revised
patch.)

I've taken a look at this patch as it currently stands in 3.7-rc1, and
done a bit of testing. (By the way, the test program
tools/testing/selftests/epoll/test_epoll.c does not compile...)

Thanks for this.  You raise significant issues.  If we can't get these
fully resolved over the next month or so, we should revert the patch so
this new API doesn't get released in 3.7.  I have queued a patch to do
this and shall maintain it while I watch developments...

[cc Paul McKenney, who is probably the leading expert on these things]

On 10/17/2012 04:30 PM, Andrew Morton wrote:

On Tue, 16 Oct 2012 17:12:57 +0200
"Michael Kerrisk (man-pages)" [off-list ref] wrote:

quoted

On Thu, Aug 23, 2012 at 11:15 PM, Paton J. Lewis [off-list ref] wrote:

quoted

From: "Paton J. Lewis" <redacted>

Enhanced epoll_ctl to support EPOLL_CTL_DISABLE, which disables an epoll item.
If epoll_ctl doesn't return -EBUSY in this case, it is then safe to delete the
epoll item in a multi-threaded environment. Also added a new test_epoll self-
test app to both demonstrate the need for this feature and test it.

(There's a lot of background missing from this version of the patch
that was included in the previous version
[http://thread.gmane.org/gmane.linux.kernel/1311457]. It helps to
include the full rationale with a revised patch--best not to assume
that someone has the context of past mails when reading a revised
patch.)

I've taken a look at this patch as it currently stands in 3.7-rc1, and
done a bit of testing. (By the way, the test program
tools/testing/selftests/epoll/test_epoll.c does not compile...)

Thanks for this.  You raise significant issues.  If we can't get these
fully resolved over the next month or so, we should revert the patch so
this new API doesn't get released in 3.7.  I have queued a patch to do
this and shall maintain it while I watch developments...

I can't shake the feeling that EPOLL_CTL_DISABLE is solving a
non-problem, or, more precisely, that there should be a perfectly good
userspace solution with no kernel changes.

Unless something is rather buggy in kernel land (and I don't think it
is), once EPOLL_CTL_DEL has returned, no call to epoll_wait that starts
*after* EPOLL_CTL_DEL finishes will return that object.  This suggests
an RCU-like approach: once EPOLL_CTL_DEL has returned and every thread
has returned from an epoll_wait call that started after the
EPOLL_CTL_DEL returns, then the data structure can be safely freed.

In pseudocode:

delete(fd, pdata) {
  pdata->dead = true;
  EPOLL_CTL_DEL(fd);
  rcu_call(delete pdata);
}

wait() {
  epoll_wait;
  for each event pdata {
    if (pdata->gone) continue;
    process the event;
  }

  rcu_this_is_a_grace_period();
}

Of course, these are not normal grace periods and would need to be
tracked separately.  (The optimal data structure to do this without
killing scalability is not obvious.  urcu presumably implements such a
thing.)

Am I right?


--Andy

Il 18/10/2012 20:05, Andy Lutomirski ha scritto:

Unless something is rather buggy in kernel land (and I don't think it
is), once EPOLL_CTL_DEL has returned, no call to epoll_wait that starts
*after* EPOLL_CTL_DEL finishes will return that object.  This suggests
an RCU-like approach: once EPOLL_CTL_DEL has returned and every thread
has returned from an epoll_wait call that started after the
EPOLL_CTL_DEL returns, then the data structure can be safely freed.

In pseudocode:

delete(fd, pdata) {
  pdata->dead = true;
  EPOLL_CTL_DEL(fd);
  rcu_call(delete pdata);
}

wait() {
  epoll_wait;
  for each event pdata {
    if (pdata->gone) continue;
    process the event;
  }

  rcu_this_is_a_grace_period();
}

Of course, these are not normal grace periods and would need to be
tracked separately.  (The optimal data structure to do this without
killing scalability is not obvious.  urcu presumably implements such a
thing.)

Am I right?

Equip each thread with a) an id or something else that lets each thread
refer to "the next" thread; b) a lists of "items waiting to be deleted".
 Then the deleting thread adds the item being deleted to the first
thread's list.  Before executing epoll_wait, thread K empties its list
and passes the buck, appending the old contents of its list to that of
thread K+1.  This is an O(1) operation no matter how many items are
being deleted; only Thread N, being the last thread, actually has to go
through the list and delete the items.

The lists need to be protected by a mutex, but contention should really
be rare since there are just two writers.  Note that each thread only
needs to hold one mutex at a time, and the deletion loop does not need
to happen with the mutex held at all, so there's no worries of
"cascading" waits on the mutexes.

Compared to http://thread.gmane.org/gmane.linux.kernel/1311457, you get
rid of the per-item mutex and the operations that have to be done with
the (now per-thread) mutex held remain pretty trivial.

Paolo

On 10/19/12 6:03 AM, "Paolo Bonzini" [off-list ref] wrote:

Il 18/10/2012 20:05, Andy Lutomirski ha scritto:

quoted

Unless something is rather buggy in kernel land (and I don't think it
is), once EPOLL_CTL_DEL has returned, no call to epoll_wait that starts
*after* EPOLL_CTL_DEL finishes will return that object.  This suggests
an RCU-like approach: once EPOLL_CTL_DEL has returned and every thread
has returned from an epoll_wait call that started after the
EPOLL_CTL_DEL returns, then the data structure can be safely freed.

In pseudocode:

delete(fd, pdata) {
  pdata->dead = true;
  EPOLL_CTL_DEL(fd);
  rcu_call(delete pdata);
}

wait() {
  epoll_wait;
  for each event pdata {
    if (pdata->gone) continue;
    process the event;
  }

  rcu_this_is_a_grace_period();
}

Of course, these are not normal grace periods and would need to be
tracked separately.  (The optimal data structure to do this without
killing scalability is not obvious.  urcu presumably implements such a
thing.)

Am I right?

Equip each thread with a) an id or something else that lets each thread
refer to "the next" thread; b) a lists of "items waiting to be deleted".
Then the deleting thread adds the item being deleted to the first
thread's list.  Before executing epoll_wait, thread K empties its list
and passes the buck, appending the old contents of its list to that of
thread K+1.  This is an O(1) operation no matter how many items are

14 more quoted lines

A disadvantage of solutions in this direction, which was not preset in
Paton's patch, is that all calls to epoll_wait would need to specify some
timeout value (!= -1) to guarantee that they each come out of epoll_wait
and execute the "pass the buck" or "grace_period" logic.  So you would
then have contention between designs that want highly responsive "delete"
operations (those would require very short timeout values to epoll_wait)
and those that want low execution overhead (those would want larger
timeout values).