Skip to contentSkip to conversation

/dev/epoll update ...

PATCH Dan Kegel 4 participants 12 messages Sep 24, 2001 – Sep 25, 2001

lore
Share & tools
lore

Dan Kegel

author
#0 lore raw
Quoted 3 lines · Gordon Oliver

But you missed the obvious optimization of doing an f_ops->poll when the file is _added_. This means that you'll get an initial event when there is data ready. ...

Note that you can do that in userspace by calling poll(), btw. That gets you down to a single extra system call initially.

Quoted 3 lines

Note that it has the additional advantage of making the dispatch code in the user application easier. You no longer have to do special code to handle the speculative read after adding the fd.

As Davide points out in his reply, /dev/epoll is an exact clone of the O_SETSIG/O_SETOWN/O_ASYNC realtime signal way of getting readiness change events, but using a memory-mapped buffer instead of signal delivery (and obeying an interest mask). Unlike /dev/poll, it only provides information about *changes* in readiness.

Everyone who has successfully written code using the O_SETSIG/O_SETOWN/O_ASYNC code knows that it does not send an initial state event. This has not gotten in the way, as a rule.

If it does turn out to be Very Important for these single-shot readiness notification schemes to generate synthetic initial readiness events, it should be added both to /dev/epoll and to O_SETSIG/O_SETOWN/O_ASYNC.

I think there is still some confusion out there because of the name Davide chose; /dev/epoll is so close to /dev/poll that it lulls many people (myself included) into thinking it's a very similar thing. It ain't. (I really have to fix my c10k page to reflect that correctly...)
- Dan

#1 lore raw
Quoted 5 lines · Dan Kegel

As Davide points out in his reply, /dev/epoll is an exact clone of the O_SETSIG/O_SETOWN/O_ASYNC realtime signal way of getting readiness change events, but using a memory-mapped buffer instead of signal delivery (and obeying an interest mask). Unlike /dev/poll, it only provides information about *changes* in readiness.

Right. But it does one additional thing that the rtsig method doesn't it collapses multiple readiness *changes* into a single readiness change. This allows the kernel to keep a fixed size buffer so you never need to fallback to poll as you need to with the rtsig approach.

Quoted 4 lines

I think there is still some confusion out there because of the name Davide chose; /dev/epoll is so close to /dev/poll that it lulls many people (myself included) into thinking it's a very similar thing. It ain't. (I really have to fix my c10k page to reflect that correctly...)

Hmm. /dev/epoll could and possibly should remove the readiness event if the fd becomes unready before someone gets to reading the /dev/epoll buffer. This is a natural extension of collapsing events.

But even with that it would still only give you the state as of the last state change. And it you have the state already it expects user space to remember the state and not the kernel. Which is both different from /dev/poll and more efficient.

If the goal is to minimize system calls letting user space assume the state is initially not ready. And forcing a state query when
the fd is added should help. I cannot think of a case where having
the kernel do the query would be necessary though.

If the goal is simply to provide a highly scalable event interface. The current /dev/epoll sounds very good. Though I'm not at all thrilled with the user space interface. As far as I can tell the case of a fd becoming not ready is unlikely enough that it probably doesn't need to be handled.

Eric

#2 lore raw
In reply to Dan Kegel
Quoted 10 lines · Eric W. Biederman
Quoted 5 lines

As Davide points out in his reply, /dev/epoll is an exact clone of the O_SETSIG/O_SETOWN/O_ASYNC realtime signal way of getting readiness change events, but using a memory-mapped buffer instead of signal delivery (and obeying an interest mask). Unlike /dev/poll, it only provides information about *changes* in readiness.

Right. But it does one additional thing that the rtsig method doesn't it collapses multiple readiness *changes* into a single readiness change. This allows the kernel to keep a fixed size buffer so you never need to fallback to poll as you need to with the rtsig approach.

That could be added to rtsigs, with the same result: no need to fallback to poll. You could even keep the memory for the queued signal / event inside the file structure.

-- Jamie

#3 lore raw
Quoted 7 lines · On 24-Sep-2001 Jamie Lokier wrote:
Quoted 6 lines · Eric W. Biederman
Quoted 5 lines

As Davide points out in his reply, /dev/epoll is an exact clone of the O_SETSIG/O_SETOWN/O_ASYNC realtime signal way of getting readiness change events, but using a memory-mapped buffer instead of signal delivery (and obeying an interest mask). Unlike /dev/poll, it only provides information about *changes* in readiness.

Quoted 7 lines
Quoted 4 lines

Right. But it does one additional thing that the rtsig method doesn't it collapses multiple readiness *changes* into a single readiness change. This allows the kernel to keep a fixed size buffer so you never need to fallback to poll as you need to with the rtsig approach.

That could be added to rtsigs, with the same result: no need to fallback to poll.

There's already a patch that implement this.

Quoted 1 line

You could even keep the memory for the queued signal / event inside the file structure.

By keeping the event structure inside the file* require you to collect these events ( read memory moves ) at peek time.
With /dev/epoll the event is directly dropped inside the mmaped area.

- Davide

#4 lore raw
In reply to Jamie Lokier
Quoted 1 line · Davide Libenzi
Quoted 1 line

You could even keep the memory for the queued signal / event inside

the file structure.

Quoted 4 lines

By keeping the event structure inside the file* require you to collect these events ( read memory moves ) at peek time.
With /dev/epoll the event is directly dropped inside the mmaped area.

Well, memory move consists of 2 words: (a) file descriptor; (b) poll state/edge flags.

That will be completely swamped by the system calls and so on needed to processes each of the file descriptors. I.e. no scalability problem here.

-- Jamie

#5 lore raw
Quoted 10 lines · On 24-Sep-2001 Jamie Lokier wrote:
Quoted 1 line · Davide Libenzi
Quoted 1 line

You could even keep the memory for the queued signal / event inside

the file structure.

Quoted 4 lines

By keeping the event structure inside the file* require you to collect these events ( read memory moves ) at peek time.
With /dev/epoll the event is directly dropped inside the mmaped area.

Well, memory move consists of 2 words: (a) file descriptor; (b) poll state/edge flags.

2-words * number-of-ready-fds == pretty-high-cache-drain

Quoted 2 lines

That will be completely swamped by the system calls and so on needed to processes each of the file descriptors. I.e. no scalability problem here.

The other issue is that by keeping infos in file* you'll have to scan each fd to report the ready ones, that will make the method to fall back in O(n). Anyway there's a pretty good patch ( http://www.luban.org/GPL/gpl.html ), that has been tested here :

http://www.xmailserver.org/linux-patches/nio-improve.html

that implement the signal-per-fd mechanism and it achieves a very good scalability too.

- Davide

#6 lore raw
In reply to Jamie Lokier
Quoted 4 lines · Davide Libenzi
Quoted 2 lines

Well, memory move consists of 2 words: (a) file descriptor; (b) poll state/edge flags.

2-words * number-of-ready-fds == pretty-high-cache-drain

Perhaps there is a cache issue, but note it is the number of _new_ ready fds (since the last sample), not the number currently ready.

Quoted 5 lines
Quoted 2 lines

That will be completely swamped by the system calls and so on needed to processes each of the file descriptors. I.e. no scalability problem here.

The other issue is that by keeping infos in file* you'll have to scan each fd to report the ready ones, that will make the method to fall back in O(n).

No, that would be silly. You would queue signals exactly as they are queued now (but collapsing multiple signals per fd into one).

Quoted 7 lines

Anyway there's a pretty good patch ( http://www.luban.org/GPL/gpl.html ), that has been tested here :

http://www.xmailserver.org/linux-patches/nio-improve.html

that implement the signal-per-fd mechanism and it achieves a very good scalability too.

It has the bonus of requiring no userspace changes too. Lovely!

-- Jamie

#7 lore raw
Quoted 21 lines · On 24-Sep-2001 Jamie Lokier wrote:
Quoted 4 lines · Davide Libenzi
Quoted 2 lines

Well, memory move consists of 2 words: (a) file descriptor; (b) poll state/edge flags.

2-words * number-of-ready-fds == pretty-high-cache-drain

Perhaps there is a cache issue, but note it is the number of _new_ ready fds (since the last sample), not the number currently ready.

Quoted 5 lines
Quoted 2 lines

That will be completely swamped by the system calls and so on needed to processes each of the file descriptors. I.e. no scalability problem here.

The other issue is that by keeping infos in file* you'll have to scan each fd to report the ready ones, that will make the method to fall back in O(n).

No, that would be silly. You would queue signals exactly as they are queued now (but collapsing multiple signals per fd into one).

Quoted 3 lines

Anyway there's a pretty good patch ( http://www.luban.org/GPL/gpl.html ), that has been tested here :

Quoted 6 lines
Quoted 4 lines

http://www.xmailserver.org/linux-patches/nio-improve.html

that implement the signal-per-fd mechanism and it achieves a very good scalability too.

It has the bonus of requiring no userspace changes too. Lovely!

Sure you can avoid the scan, if you pick up one event at a time. To be compared to /dev/epoll you need the signal-per-fd patch plus a method to collect the whole event-set in a single system call ( see perfs ).

- Davide

#8 lore raw
In reply to Jamie Lokier
Quoted 4 lines · Davide Libenzi

Sure you can avoid the scan, if you pick up one event at a time. To be compared to /dev/epoll you need the signal-per-fd patch plus a method to collect the whole event-set in a single system call ( see perfs ).

Yes, I agree. A variant of sigwaitinfo that will return multiple queued signals was mentioned ages ago, but because the siginfo structure is much larger than is needed, that isn't a very effective use of cache.

Something specialised for fd events is more appropriate IMO. Large numbers of queued RT signals aren't used for anything else AFAIK anyway, not even timers.

-- Jamie

#9 lore raw
Quoted 6 lines · On 24-Sep-2001 Jamie Lokier wrote:
Quoted 4 lines · Davide Libenzi

Sure you can avoid the scan, if you pick up one event at a time. To be compared to /dev/epoll you need the signal-per-fd patch plus a method to collect the whole event-set in a single system call ( see perfs ).

Quoted 7 lines

Yes, I agree. A variant of sigwaitinfo that will return multiple queued signals was mentioned ages ago, but because the siginfo structure is much larger than is needed, that isn't a very effective use of cache.

Something specialised for fd events is more appropriate IMO. Large numbers of queued RT signals aren't used for anything else AFAIK anyway, not even timers.

The bottom line is, for what i saw in my tests, that both /dev/epoll and RT signals ( with signal-per-fd ) offers good performance and scalability.

- Davide

author
#11 lore raw
In reply to Dan Kegel
Quoted 8 lines · Christopher K. St. John

Ok, just to confirm. Using the language of BSD's
kqueue[1]. you've got:

a) report the event only once when it occurs aka
"edge triggered" (EV_CLEAR, not EV_ONESHOT)

b) continuously report the event as long as the
state is valid, aka "level triggered"

Right, and kqueue() can't even represent the 'level triggered' style -- or at least it isn't clear from the paper that it can! True "level triggered" would require that the kernel track readiness of the affected file descriptors.

Quoted 8 lines

The Banga99 paper certainly appears to describe an
"edge triggered" interface:

"Our new API follows the event-based approach. In
this model the kernel simply reports a stream of events to the application. ... The kernel does not track the readiness of any descriptor ... "

Quoted 5 lines

Libenzi-/dev/epoll, being a partical implementation
of the Banga99 mechanism, is also edge-triggered.

OTOH, the Provos/Lever Linux /dev/poll paper describes
what appears to be a "level triggered" interface.

Agreed.

Quoted 8 lines

Now for a question: My initial impression was that
Solaris-/dev/poll, in contrast to Linux /dev/poll, was edge-triggered. That would explain why it might be more efficient that Linux-/dev/poll.

But I don't have a copy of Solaris, handy, so I
can't confirm. Do you know for sure? (Or is part of my analysis wrong?)

Solaris /dev/poll is definitely level-triggered; see Poller_test.cc in
http://www.kegel.com/dkftpbench/dkftpbench-0.33.tar.gz, which verifies this. Poller_devpoll.cc is a thin wrapper around /dev/poll, and it definitely exhibits level-triggered behavior with both Solaris and Linux /dev/poll.

(I later extended Poller to support edge-triggered notifications from the OS, and translate them to level-triggered notification for the user app. Poller_sigio.cc and Poller_sigfd.cc are somewhat fatter wrappers around O_ASYNC, and achieve level-triggered behavior only with cooperation from the application, which has to call clearReadiness(fd) when the OS returns EWOULDBLOCK! Surely the OS could do that internally, eh?)

Java's Selector in JDK 1.4 will have level-triggered behavior, not edge-triggered behavior, btw.
- Dan

author
#10 lore raw
In reply to Jamie Lokier
Quoted 9 lines · Jamie Lokier
Quoted 7 lines

Anyway there's a pretty good patch ( http://www.luban.org/GPL/gpl.html ), that has been tested here :

http://www.xmailserver.org/linux-patches/nio-improve.html

that implement the signal-per-fd mechanism and it achieves a very good scalability too.

It has the bonus of requiring no userspace changes too. Lovely!

Well, not quite *no* userspace changes, but not many. You have to use si_band rather than si_code (and with Luban's version, you also need to set a new flag).

It has some locking problems that only show up under very heavy use, so caveat emptor. I put together a stress test
(http://www.kegel.com/dkftpbench/ with the -sf option);
run that against betaftpd, and around 4500 ftp sessions, you might see it crash because a signal comes in while the file table is expanding...

(By the way, I finally updated http://www.kegel.com/c10k.html to distinguish properly between edge-triggered readiness notification methods and level-triggered ones. Hope that helps dispel some confusion in the future.)
- Dan