async poll for 2.5

As of today, there is no scalable alternative to poll/select in the 2.5 kernel even though the topic has been discussed a number of times before. The case for a scalable poll has been made often so I won't get into that.

Attached is a port of the 2.4 async poll code to 2.5.41, written by David Stevens with assistance from Jay Vosburgh and Mingming Cao (a port for 2.5.42 is in progress and will be posted shortly). The patch is a clean port of the 2.4 design and eliminates the use of worktodos, just as Ben had done through the do_hack() function. The patch has been tested on 2.5.41 using simple poll tests. A performance evaluation and further testing is underway.

Even though Ben has indicated, on linux-aio and in OLS, that the 2.4 design doesn't scale well enough, it is a lot better than normal poll. With the absence of alternatives and the impending feature freeze, this patch would be one way to ensure that users have at least one alternative to regular poll.

Ben, are you working on a different async poll implementation that is likely to be ready by the feature freeze ?

Regards,
Shailabh

diff -ruN linux-2.5.41/fs/aio.c linux-2.5.41AIO/fs/aio.c
@@ -59,6 +59,8 @@
 static spinlock_t	fput_lock = SPIN_LOCK_UNLOCKED;
 LIST_HEAD(fput_head);
 
+int async_poll(struct kiocb *iocb, int events);
+
 /* aio_setup
  *	Creates the slab caches used by the aio routines, panic on
  *	failure as this is done early during the boot sequence.

@@ -893,6 +895,19 @@
 	return -EINVAL;
 }
 
+ssize_t generic_aio_poll(struct file *file, struct kiocb *req, struct iocb *iocb)
+{
+	unsigned events = iocb->aio_buf;
+
+	/* Did the user set any bits they weren't supposed to? (The 
+	 * above is actually a cast.
+	 */
+	if (unlikely(events != iocb->aio_buf))
+		return -EINVAL;
+	
+	return async_poll(req, events);
+}
+
 static int FASTCALL(io_submit_one(struct kioctx *ctx, struct iocb *user_iocb,
 				  struct iocb *iocb));
 static int io_submit_one(struct kioctx *ctx, struct iocb *user_iocb,

@@ -978,12 +993,15 @@
 		if (file->f_op->aio_fsync)
 			ret = file->f_op->aio_fsync(req, 0);
 		break;
+	case IOCB_CMD_POLL:
+		ret = generic_aio_poll(file, req, iocb);
+		break;
 	default:
 		dprintk("EINVAL: io_submit: no operation provided\n");
 		ret = -EINVAL;
 	}
 
-	if (likely(EIOCBQUEUED == ret))
+	if (likely(-EIOCBQUEUED == ret))
 		return 0;
 	if (ret >= 0) {
 		aio_complete(req, ret, 0);

diff -ruN linux-2.5.41/include/linux/aio_abi.h linux-2.5.41AIO/include/linux/aio_abi.h
@@ -40,6 +40,7 @@
 	 * IOCB_CMD_PREADX = 4,
 	 * IOCB_CMD_POLL = 5,
 	 */
+	IOCB_CMD_POLL = 5,
 	IOCB_CMD_NOOP = 6,
 };
 

diff -ruN linux-2.5.41/include/linux/poll.h linux-2.5.41AIO/include/linux/poll.h
@@ -9,12 +9,14 @@
 #include <linux/string.h>
 #include <linux/mm.h>
 #include <asm/uaccess.h>
+#include <linux/workqueue.h>
 
 struct poll_table_page;
 
 typedef struct poll_table_struct {
-	int error;
-	struct poll_table_page * table;
+	int			error;
+	struct poll_table_page	*table;
+	struct kiocb		*iocb;		/* iocb for async poll */
 } poll_table;
 
 extern void __pollwait(struct file * filp, wait_queue_head_t * wait_address, poll_table *p);

@@ -29,6 +31,7 @@
 {
 	pt->error = 0;
 	pt->table = NULL;
+	pt->iocb = NULL;
 }
 extern void poll_freewait(poll_table* pt);
 

Your patch has numerous races, a kiocb leak, and incorrectly calls aio_complete() upon cancellation. Please see the patch I sent to [email protected] on September 29.

Have you bothered addressing the fact that async poll scales worse than /dev/epoll? That was the original reason for dropping it.

-ben

Doesn't the F_SETSIG/F_SETOWN/SIGIO stuff qualify as a scalable alternative?
It's in 2.5 as far as I know. It does suffer from using the signal
queue,
but it's in production use on servers that handle many thousands of concurrent connections, so it's pretty scalable.

- Dan

No.

-ben

What's the worst part about it? The use of the signal queue?
- Dan

there are four things that really suck about sigio.
in order of most-significant-suckage to least-significant-suckage, i see them as:

[1] signals are very heavy.
thousands of signals/second does not scale on SMP due to the serialization of them in the kernel.
(just look at the code path for delivering a signal)

signals also resulted in 128 u32's being transferred from kernel to userspace for every signal. thats a lot of memory i/o bandwidth consumed at 1000's of concurrent sockets and tens-of-thousands of events/sec happening.

[2] SIGIO only exposes half of the POLL_OUT semantics. with poll(), you can use POLL_OUT to indicate if there is free buffer space to write into or not.
with SIGIO, for most applications, you can only find out by issuing a write() and get back a -EWOULDBLOCK. to indicate !POLL_OUT.
(perhaps that has been addressed in the last 12 months or so; but i doubt it)

[3] SIGIO had no easy recovery path if you hit the maximum- queue-limit for number of signals queued to userspace. (ok, you *could* do a poll() and start again, but it couldn't be done in a 100% race-free manner)

[4] you couldn't enable SIGIO on a incoming socket accept()ed without there being a race window where something happened to that socket between accept() and enable-SIGIO. [sort-of related to (3); you could work-around it by doing a poll() on the socket after enable-SIGIO, but it makes a clean interface a horrible interface]

other miscellaneous things that makes SIGIO less usable in the real-world:
- you can only get one event at a time -- that means tens-of-thousands to hundreds-of-thousands of system calls / second just to get event status, when it'd probably make more sense to poll for multiple signals at the same time
- SIGIO only addressed "event notification". it did nothing to address the other large scalability that you typically hit when writing
high-performance i/o
systems: overhead of memory-copy from userspace<->kernelspace. various zerocopy mechanisms help address that side of thing, but if you're comparing aio to SIGIO, aio *is* addressing a much larger problem than just SIGIO on its own

cheers,

lincoln.

Dan,

Are there any performance numbers for F_SETSIG/F_SETOWN/SIGIO on 2.5 ? Does it scale with the number of active connections too ?

Signal-per-fd seems to be a decent alternative (from the measurements on Davide's /dev/epoll page) but Vitaly Luban's patch for that isn't available for 2.5 so I'm not sure what other issues it might have.

-- Shailabh

I don't recall any. (I suppose I should get off my butt and start running 2.5.)

The overhead is probably mostly linear with activity, I don't know.

Seems like the thing to do is to move /dev/epoll over to use Ben's event system rather than worry about the old /dev/epoll interface. But like signal-per-fd, we will want to collapse readiness events, which is something Ben's event system might not do naturally. (I wouldn't know -- I haven't actually looked at Ben's code.)

- Dan

If you look at how /dev/epoll does it, the collapsing of readiness events is very elegant: a given fd is only allowed to report a change in its state once per run through the event loop. The ioctl that swaps event buffers acts as a barrier between the two possible reports.

As to how this would interact with the aio event loops, I thought the "barrier" syscall could be the point at which aio event slots are reserved and freed. Interest registration would be the other syscall (which would naturally have to reserve an event for the descriptor in the current set of readiness notifications). Anyways, just a few thoughts...

-ben

"Do you seek knowledge in time travel?"

And the way /dev/epoll does it has a key flaw: it only works with single threaded callers. If you have multiple threads simultaneously trying to get events, then race conditions abound.

Which assumes there are only single threaded callers. To work correctly with multithreaded callers, there needs to be a more explicit mechanism for a caller to indicate it has completed handling an event and wants to rearm its interest.

There are also additional interactions with cancellation. How does the cancellation interface report and handle the case where an associated event is being delivered or handled by another thread? What happens when that thread then tries to rearm the canceled interest?

I certainly hope /dev/epoll itself doesn't get accepted into the kernel, the interface is error prone. Registering interest in a condition when the condition is already true should immediately generate an event, the epoll interface did not do that last time I saw it discussed. This deficiency in the interface requires callers to include more complex workaround code and is likely to result in subtle, hard to diagnose bugs.

Delaying the "get next batch of readiness events" call as long as possible
increases the amount of event collapsing possible, which is important because
the network stack seems to generate lots of spurious events. Thus I suspect
you don't want multiple threads all calling the "get next batch of events"
entry point frequently.
The most effective way to use something like /dev/epoll in a multithreaded
program might be to have one thread call "get next batch of events", then divvy up the events across multiple threads.
Thus I disagree that the way /dev/epoll does it is flawed.

With queued readiness notification schemes like SIGIO and /dev/epoll, it's safest to allow readiness notifications from the kernel to be wrong sometimes; this happens at least in the case of accept readiness,
and possibly other places. Once you allow that, it's easy to handle the condition you're worried about by generating a spurious readiness indication when registering a fd. That's what I do in my wrapper library.

Also, because /dev/epoll and friends are single-shot notifications of *changes* in readiness, there is little reason to register interest in this or that event, and change that interest over time; instead, apps should simply register interest in any event they might ever be interested in. The number of extra events they then have to ignore is very
small, since if you take no action on a 'read ready' event, no more of those events will occur.

So I pretty much disagree all around :-) but I do understand where you're
coming from. I used to feel similarly until I figured out the 'right' way to use one-shot readiness notification systems (sometime last week :-)

- Dan

That is a tautology. As /dev/epoll is inherently a single threaded interface, of course the most effective way for a multithreaded program to use it is to have one thread call it then divvy up the events. That's the *only* way a multithreaded program can deal with a single threaded interface.

The cost to divvy up the events can be substantial, not the mention the cost of funneling them all through a single CPU. This cost can easily be greater than what one saves by combining events. io_getevents() is a great model for divvying events across multiple threads, the poll facility should work with that model.

The solution for optimizing the amount of event collapsing is to implement concurrency control.

This is a workaround. You are adding additional code and complexity to the caller in order to deal with a deficiency in the interface. This has several problems:

Someone writing to the /dev/epoll interface needs to know that they need to write such workaround code. If they don't know to write the code or if they make an error in the workaround code, it is still likely that the program will pass testing. What will result are intermittent, hard to diagnose failures in production.

User space does not have the information to address this as well as the kernel can. As a result, the workaround requires more processing in the common, non racy case.

The kernel can clearly handle this situation better than user space. It can do the necessary checks while it is still holding the necessary locks. It is less error prone to handle the situation in the kernel. The logic clearly belongs in the kernel.

You're making assumptions about the structure and flow of an application. Sometimes when an application stops having interest in this or that event, it needs to free/invalidate the context associated with that event.

So that's fine as a strategy for amortizing the cost of registration/deregistration, but it isn't universally applicable.

There're many ways to have /dev/epoll working in a threaded environment if you think about it, and no you don't need to have a single thread fetching events. You can have, if you really like threads, N fetching threads ( working on N private /dev/epoll fds ), feeding M queues, polled by P service threads. If you like it ...

- Davide

In such models, you still have to pay the cost of divvying up the events after you receive them. You also have to worry about keeping load distributed evenly enough.

That's exactly the reason why you don't want to use many threads. Typical applications that uses multiplex interfaces uses only one task ( eventually for each CPU ) that handles many connections. And again, you can also use threads, if you design your application correctly. It is not that expensive having service threads popping from an array. Yes, you have a lock to be acquired but this is a price you have to pay as soon as you choose threads.

- Davide

As I mentioned before, this only works if you have the luxury of being able to write your application and its supporting libraries from scratch. If you don't have that luxury, you need additional threads in order to isolate the latency caused by blocking operations.

You have to pay for the lock needed to receive the events. What I am objecting to is having to pay again for a second lock (and condition variable) to redistribute those events from the thread they were received on to the thread they will be processed on. An interface that supports multithreading well will permit events to be delivered directly to the threads that need to process them.

io_getevents() is an example of an interface that support multithreaded callers well. Since the divvying up is done in the kernel, the information exists for its implementation to be later refined to be more intelligent about when to deliver which events to which threads. For example, the interface can later implement CPU affinity of events and concurrency control.

Why would you need to use threads with a multiplex-like interface like /dev/epoll ? The reason of these ( poll()/select()//dev/epoll//dev/poll ) interfaces is to be able to handle more file descriptors inside a _single_ task.

It works exactly like rt-signals and all you have to do is to change your code from :

int myread(...) {

	if (wait(POLLIN))
		read();

}

to :

int myread(...) {

	while (read() == EGAIN)
		wait(POLLIN);

}

- Davide

Because in some applications processing an event can cause the thread to block, potentially for a long time. Multiple threads are needed to isolate that block to the context associated with the event.

Assuming registration of interest is inside wait(), this has a race. If the file becomes readable between the time that read() returns and the time that wait() can register interest, the connection will hang.

I don't want this to become the latest pro/against threads but if your processing thread block for a long time you should consider handling the blocking condition asynchronously. If your procesing thread blocks, your application model should very likely be redesigned, or you just go with threads ( and you do not need any multiplex interface ).

Your assumption is wrong, the registration is done as soon as the fd "born" ( socket() or accept() for example ) and is typically removed when it dies.

- Davide

Rewriting the code to handle the blocking condition asynchronously can be inordinately expensive and time consuming. This is particularly true when using third party code (such as the system DNS resolver) which only has blocking interfaces.

A much more cost effective and timely methodology is to only asynchronously code the most important conditions, leaving threads to handle the rest.

Nonetheless, the requirement for user space to test the condition after the registration, not before, is subtle. A program which does these in the wrong order is still likely to pass QA and will fail in production in a way that will be difficult to diagnose. There is no rational reason for the kernel to not test the condition upon registration.

I suppose one way of getting the async poll code up to snuff would be to cache the poll registration in the file descriptor. Alternatively, the iocb could simply persist until it is cancelled or a refire is permitted (so that the event queue does not get overrun). Would you care to try crunching the numbers with polltest on 2.5?

-ben

"Do you seek knowledge in time travel?"

First, can you confirm that your only problem with the async poll code is the fact that it doesn't amortize the registration/deregistration cost across multiple events?

I would say that the fact that the async poll code doesn't do this amortization is not sufficient reason to hold up the patch. A non-amortizing async poll is sufficiently useful to warrant inclusion. It is conceivable that some applications will not want to amortize some of their poll requests. The non-amortizing interface can later be extended to an amortizing one by defining an "amortize me" bit to the events request mask.

I don't think caching the registration in the file descriptor is a good idea--there can be multiple registrations against a given fd. The registration should be cached close to the iocb--either in the iocb or in some structure that directly references the iocb.

The model for multiple-events-per-iocb I was thinking of is as follows:

Add a concept of a "partial completion". Unlike a normal completion, when a partial completion event fires the iocb is not freed. Instead the iocb goes into a "fired" state.

When an iocb is in the fired state, it will not generate any more completion events until it is "rearmed" by user space. The method by which user space rearms an iocb is to be determined. Upon rearming, the iocb is once again able to generate either a partial or normal completion. As with submission, rearming can generate this completion immediately if the situation warrants.

Canceling an iocb in the rearmed state is the same as canceling an iocb that has never generated a completion event. Canceling an iocb in the fired state returns a normal completion through the cancellation interface and returns a distinct error code (not 0 or -EAGAIN) to inform the caller that there is an outstanding event to be synchronized with.

Attempting to rearm a canceled iocb returns an error, probably -EAGAIN to be consistent with cancellation.

All APIs have their own specifications and if you do not follow them, or you're using a different interfacing just because the name looks similar to other APIs, you're going to have problems. The problem it's not inside the API but inside the user ...

- Davide

The epoll API is deficient--it is subtly error prone and it forces work on user space that is better done in the kernel. That the API is specified in a deficient way does not make it any less deficient.

Again, there is no rational justification for the kernel to not test the condition upon registration. There is ample justification for it to do so.

Just a simple question : Have you ever used RT-Signal API ? Is it the API "deficent" or is it the one that does not understand it ? Do you know the difference between level triggered ( poll() - select() - /dev/poll ) and edge triggered ( /dev/epoll - RT-Signal ) interfaces ?

- Davide

No. Yes. The (fixed) size of the signal queue is far too small. One either gets catastrophic failure on overload or one has to pay to do redundant accounting of interest.

Yes. The registration of interest can itself be considered an edge condition.

I knew you were going there, aka you do not understand how edge triggered API have to be used. Even if the API will drop an event at registration time you still cannot use this code scheme :

int my_io(...) {

	if (event_wait(...))
		do_io(...);

}

You CAN NOT. And look, it is not an API problem, it's your problem that you want to use the API like a poll()-like API. The code scheme for an edge triggered API is :

int my_io(...) {

	while (do_io(...) == EAGAIN)
		event_wait(...);

}

This because you have to consume the I/O space to push the level to 0 so that a transaction 0->1 can happen and you can happily receive your events.

- Davide

Nonsense.

You have insufficient basis upon which to claim I would write code as broken as above.

Of course you have to consume the I/O space to push the level to 0. What do you think I am, stupid?

This is done with something like:

for (;;) {
    fd = event_wait(...);
    while (do_io(fd) != EAGAIN);
}

Trying to do at once as much work as one can on a given fd helps keep that fd's context information in cache. If one needs to have the fd yield the CPU in order to reduce system latency, one generates a user-mode event.

Yes I have, look down 15 lines ...

I told you did not understand the API, this code won't work for edge triggered APIs. Please consider investigating a little bit more before shooting to perfectly working APIs.

- Davide

Nonsense. If you wish to make such a claim, you need to provide an example of a situation in which it won't work.

Your welcome. This is your code :

for (;;) {
     fd = event_wait(...);
     while (do_io(fd) != EAGAIN);
}

If the I/O space is not exhausted when you call event_wait(...); you'll never receive the event because you'll be waiting a 0->1 transaction without bringing the signal to 0 ( I/O space exhausted ). That one is a typical use of poll() - select() - /dev/poll and you showed pretty clearly that you do not seem to understand edge triggered event APIs. If you code your I/O function like :

int my_io(...) {

	if (event_wait(...))
		do_io(...);

}

and you consume only part of the I/O space with the first call to my_io(), the second call will block _infinitely_.

- Davide

My code above does exhaust the I/O space.

This is not how my example is coded.

while (do_io(...) != EAGAIN);

is not equivalent to:

do_io(...);

The former is guaranteed to exhaust the I/O space, the latter is not.

You're spouting nonsense.

Look, I'm usually very polite but you're really wasting my time. You should know that an instruction at line N is usually executed before an instruction at line N+1. Now this IS your code :

[N-1] for (;;) {
[N ] fd = event_wait(...);
[N+1] while (do_io(fd) != EAGAIN);
[N+2} }

I will leave you as an exercise to understand what happens when you call the first event_wait(...); and there is still data to be read/write on the file descriptor. The reason you're asking /dev/epoll to drop an event at fd insertion time shows very clearly that you're going to use the API is the WRONG way and that you do not understand how such APIs works. And the fact that there're users currently using the rt-sig and epoll APIs means that either those guys are genius or you're missing something.

- Davide

Your claim was that even if the API will drop an event at registration time, my code scheme would not work. Thus, we can take "the API will drop an event at registration time" as postulated. That being postulated, if there is still data to be read/written on the file descriptor then the first event_wait will return immediately.

In fact, given that postulate and the appropriate axioms about the behavior of event_wait() and do_io(), one can prove that my code scheme is equivalent to yours. The logical conclusion from that and your claim would be that you don't understand how edge triggered APIs have to be used.

The wrong way as defined by what? Having /dev/epoll drop appropriate events at registration time permits a useful simplification/optimization and makes the system significantly less prone to subtle progamming errors.

I do understand how such APIs work, to the extent that I am pointing out a flaw in their current models.

Nonsense. People are able to use flawed APIs all of the time.

No, the concept of edge triggered APIs is that you have to use the fd until EAGAIN. It's a very simple concept. That means that after a connect()/accept() you have to start using the fd because I/O space might be available for read()/write(). Dropping an event is an attempt of using the API like poll() & Co., where after an fd born, it is put inside the set to be later wake up. You're basically saying "the kernel should drop an event at creation time" and I'm saying that, to keep the API usage consistent to "use the fd until EAGAIN", you have to use the fd as soon as it'll become available.

I'm sorry but why do you want to sell your mistakes for API flaws ?

- Davide

Which my code does, given the postulate.

Here's where your argument is inconsistent with the Linux philosophy.

Linux has a strong philosophy of practicality. The goal of Linux is to do useful things, including provide applications with the semantics they need to do useful things. The criteria for deciding what goes into Linux is heavily weighted towards what works best in practice.

Whether or not some API matches someone's Platonic ideal of of an OS interface is not a criterion. In Linux, APIs are judged by their practical merits. This is why Linux does not have such things as message passing and separate address spaces for drivers.

So whether or not a proposed set of epoll semantics is consistent with your Platonic ideal of "use the fd until EAGAIN" is simply not an issue. What matters is what works best in practice.

Luckily enough, being the only one that wasted my time in those couple of days arguing against the API semantic, you pretty much down in the list of people that are able to decide what "works best in practice".

- Davide

flawed. If I wanted a method of monopolizing the event loop with real time priorities, I would implement real time priorities within the event loop.

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

You don't need to "use the fd until EAGAIN", you can consume even only byte out of 10000 and stop using the fd. As long as you keep such fd in your ready-list. As soon as you receive an EAGAIN from that fd, you remove it from your ready-list and the next time you'll go to fish for events it will reemerge as soon as it'll have something for you. The concept is very simple, "you don't have to go waiting for events for a given fd before having consumed its I/O space".

- Davide

The choice I see is between:
1. re-arming the one-shot notification when the user gets EAGAIN
2. re-arming the one-shot notification when the user reads all the data that was waiting (such that the very next read would return EGAIN).

#1 is what Davide wants; I think John and Mark are arguing for #2.

I suspect that Davide would be happy with #2, but advises programmers to read until EGAIN anyway just to make things clear.

If the programmer is smart enough to figure out how to do that without hitting EAGAIN, that's fine. Essentially, if he tries to get away without getting an EAGAIN, and his program stalls because he didn't read all the data that's available and thereby doesn't reset the one-shot readiness event, it's his own damn fault, and he should go back to using level-triggered techniques like classical poll() or blocking i/o.

- Dan

I thought the debate was over how the initial arming of the one-shot was done.

The choice above is a different issue.

Neither of 1 or 2 above accurately reflects what the code in the kernel actually does.

Hitting EAGAIN does not "re-arm" the one-shot notification.

Consider TCP.

The tcp write code issues a POLLOUT edge when the socket-buffer fill level drops below a hi-water mark (tcp_min_write_space()).

For reads, AFAIK, tcp issues POLLIN for every new TCP segment that arrives, which get coalesced automatically by virtue of the getevents barrier.

A short count means the appliation has hit an extreme end of the buffer (completely full or empty). EAGAIN means the buffer was already at the extreme. Either way you know just as well that new activity will trigger a new edge event.

In summary, a short count is every bit as reliable as EAGAIN to know that it is safe to wait on epoll_getevents.

Davide?

-- Buck

It's a minor point, but based on the logic above, I think this advise is overkill.

-- Buck

Whoops. I just realized a flaw in my own argument.

With read, a short count might precede EOF. Indeed, in that case, calling epoll_getevents would cause the connection to get stuck.

Never mind my earlier message then.

-- Buck

Maybe epoll should be extended with a specific EOF event. Then short reads would be fine.
- Dan

No, this is not what I'm arguing. Once an event arrives for a fd, my proposed semantics are no different than Mr. Libenzi's. The only difference is what happens upon registration of interest for a fd. With my semantics, the kernel guarantees that if the fd is ready then at least one event has been generated. With Mr Libenzi's semantics, there is no such guarantee and the application is required to behave as if an event had been generated upon registration.

sed s/Mr. Libenzi/Davide/g ... I'm not that old :)
There're a couple of reason's why the drop of the initial event is a waste of time :

1) The I/O write space is completely available at fd creation
2) For sockets it's very likely that the first packet brought something

	more than the SYN == The I/O read space might have something for you

I strongly believe that the concept "use the fd until EAGAIN" should be applied even at creation time, w/out making exceptions to what is the API's rule to follow.

- Davide

There is a third way, described in the original Banga/Mogul/Druschel paper, available via Dan Kegel's web site: extend the accept() call to return whether an event has already happened on that FD. That way you can service a ready FD without reading /dev/epoll or calling sigtimedwait, and you don't have to waste a read() call on the socket only to find out you got EAGAIN.

Of course, this changes the accept API, which is another matter. But if we're talking a new API then there's no problem.

-Erich

That would be the fastest way of finding out, maybe.
But I'd rather use a uniform way of notifying about readiness events. Rather than using a new API (acceptEx :-) or a rule ("always ready initially"), when not just deliver the initial readiness event via the usual channel? And for ease of coding for the moment, David can just deliver
a 'ready for everything' event initially unconditionally.

No API changes, just a simple, uniform way of tickling the user's "I gotta do I/O" code.
- Dan

Why differentiate between connect and accept. At that point you should also handle connect as a particular case, that's the point. And that's why I like the API's rule to be consistent and I would not like to put inside the kernel source code explicit event dispatch inside accept/connect.

- Davide

I'm getting confused over what minute details are being disputed here.

This debate might get clearer, to me anyway, if the example code fragments were more concrete.

So if anybody still cares at this point, here is my stab at clarifying some things.

PART I: THE RACE

Suppose we have the following:

1 for(;;) {
2 fd = event_wait(...);
3 if(fd == my_listen_fd) {
4 /* new connections */
5 while((new_fd = my_accept(my_listen_fd, ...) != EAGAIN))
6 epoll_addf(new_fd, ...);
7 } else {
8 /* established connections */
9 while(do_io(fd) != EAGAIN)
10 }
11 }

With the current epoll/rtsig semantics, there is a race condition above. I think this essentially the same race condition as the snippet at the top of this message.

Just to be clear, I walk completely through the steps in the race scenario, as follows.

We start with our application blocked in line 2.

A new connection is initiated by the application on other side.

The kernels exchange SYNs, causing the connection to be established.

The kernel on our side queues the new connection, waiting for the application on this side to call accept(). In the process it fires an edge POLLIN on the listen_fd, which wakes up the kernel side of line
2. However, some time may pass before we actually wake up.

Meanwhile, the other side immediately sends some application level data. The other side is going to wait for us to read the application level data and respond. So it is now blocked.

All of this happens before our application runs line 5 to pick up the new connection from the kernel.

Here comes the race:

Before we reach line 6, new_fd is not in epoll mode, so packet arrivals do not trigger a POLLIN edge notfication on new_fd.

After line 6, there will be no data from the other side, so there will still be no POLLIN edge notification for new_fd.

Therefore, line 2 will never yield a POLLIN event for new_fd, and the new connection is now deadlocked.

Is this the kind of race we're talking about?

If so, we proceed as follows.

PART 2: SOLUTIONS

A race free alternative to write the code above is as follows. Only one new line (marked with *) is added.

1 for(;;) {
2 fd = event_wait(...);
3 if(fd == my_listen_fd) {
4 /* new connections */
5 while((new_fd = my_accept(my_listen_fd, ...) != EAGAIN)) {
6 epoll_addf(new_fd, ...);
7* while(do_io(new_fd) != EAGAIN);
8 }
9 } else {
10 /* established connections */
11 while(do_io(fd) != EAGAIN)
12 }
13 }

The example above works with current epoll and rtsig semantics. This is just rephrasing what Davide has been saying: "Never call event_wait without first ensuring that IO space is definitively exhausted".

Or we could have (to make John happier?):

1 for(;;) {
2 fd = event_wait(...);
3 if(fd == my_listen_fd) {
4 /* new connections */
5 while((new_fd = my_accept(my_listen_fd, ...) != EAGAIN)) {
6* epoll_addf(new_fd, &pfd, ...);
7* if(pfd.revents & POLLIN) {
7* while(do_io(new_fd) != EAGAIN);
8* }
8 }
9 } else {
10 /* established connections */
11 while(do_io(fd) != EAGAIN)
12 }
13 }

Here, epoll_addf primitive has been modified to return the initial status. Presumably so we avoid the first call to do_io if there is nothing to do yet.

If it's easy to do (change add primitive that is), why not?

The first solution works either way.

-- Buck

Exactly, you're going to wait for an event w/out having consumed the possibly available I/O space.

Exactly, this is the sketchy solution ( but event_wait() return more than one fd though ).

- Davide

Close. What we would have is a modification of the epoll_addf() semantics such that it would have an additional postcondition that if the new_fd is in the ready state (has data available) then at least one notification has been generated. In the code above, the three lines comprising the if statement labeled "7*" would be removed.

I am just joining your discussion today for the fist time. I come from a Windows implementation of async I/O, so please don't hold it against me. I can't say that I am following 100% percent, but I think you guys are talking about what the user API will look like, correct?

Assuming the answer is yes. Here are my two cents. The code you have below seems a bit awkward -- the line while(do_io(fd) != EAGAIN) appears twice. I think the reason for that is that you're trying to do too many things at once, namely, you're trying to handle both the initial accept/setup of the socket and its steady state servicing. I don't see any benefit to that -- it definitely doesn't make for cleaner code. Why not do things separately.

1. Have a setup phase which more or less does:

*  listen()
*  accept()
*  add the new fd/socket to an "event" which all the worker threads are

waiting on.

2. Have the worker tread/steady state operation be:

* event_wait() which returns the fd, some descriptor of what exactly happened (read/write), the number of bytes transferred.
* based upon the return from event wait the user updates his state, and posts the next operation (read/write).

Thanks,

Tervel Atanassov

-----Original Message-----
From: [email protected] [mailto:[email protected]] On Behalf Of John Myers
Sent: Friday, October 18, 2002 6:05 PM
To: Charles 'Buck' Krasic
Cc: Davide Libenzi; Benjamin LaHaise; Dan Kegel; Shailabh Nagar; linux-kernel; linux-aio; Andrew Morton; David Miller; Linus Torvalds; Stephen Tweedie
Subject: Re: epoll (was Re: [PATCH] async poll for 2.5)

Close. What we would have is a modification of the epoll_addf() semantics such that it would have an additional postcondition that if the new_fd is in the ready state (has data available) then at least one notification has been generated. In the code above, the three lines comprising the if statement labeled "7*" would be removed.

--
To unsubscribe, send a message with 'unsubscribe linux-aio' in the body to [email protected]. For more info on Linux AIO,
see: http://www.kvack.org/aio/

If you carefully reread the message you replied to, you will see that this is exactly what I am proposing. The redundant copy of the line you consider awkward would be removed.

I see.

I assume the kernel implementation is no big deal: epoll_addf() has to call the kernel internal equivalent to poll() with a zero timeout.

This wouldn't break the first "solution" in my earlier post, but it would cause every new connection to experience one extra EAGAIN.

I see three possibilities:

1) keep the current epoll_addf()
2) modify it as John suggests, posting the initial ready state in the next epoll_getevents()
3) both: add an option to epoll_addf() that says which of 1 or 2 is desired.

-- Buck

How hard would it be to modify the current epoll code to work that way? I'd assume it's just a matter having epoll_addf call the legacy poll() code to check the condition (with a zero timeout).

-- Buck

Not to enter into any of the other discussions on this issue, I wouldn't usually do what you suggest above. Sure, for operations like accept() that are inherently inefficient, I would loop until EAGAIN, but if I did I a recv() or read() of 2K, and I only received 1K, there is no reason why another system call should be invoked on the resource that likely will not have any data ready.

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

You're into the minutiae here. Sure, you can optimize the read() in some cases, but Mr. Libenzi's example of a correct code scheme is no better than mine when it comes to this.

In some situations, I've found that optimizing in the other direction is useful. When a peer is feeding you data slowly you can increase throughput by having the thread block on read for a couple of milliseconds before going back to the pool. A large part of that was that the particular event delivery subsystem was expensive.

The poll()-like code :

int my_io(...) {

	if (poll(...))
		do_io(...);

}

The epoll-like code :

int my_io(...) {

	while (do_io(...) == EAGAIN)
		event_wait(...);

}

I would say that the epoll-like code generates less system calls because if you call my_io() by processing small chunks of the I/O space, the epoll-like code will generate only one system call while the poll()-like code two. In case of I/O that ends up in wait the poll()-like code generate two system calls while epoll-like code three. Globally the number of system calls are about the same and from a performance point of view /dev/epoll looks "pretty good" ( see /dev/epoll page ).

- Davide

This is not my example of a correct code scheme. You're made a strawman argument, which proves nothing.

You can argue that any API is subtly error prone. The whole sockets API is that way. That's why the W. Richard Stevens network programming books are such gems. That's why having access to kernel source is invaluable. You have to pay attention to details to avoid errors.

With /dev/epoll, it is perfectly feasible to write user level wrapper libraries that help avoid the potential pitfalls.

I think it was Dan Kegel who has already mentioned one.

I've written one myself, and I'm very confident in it. I've written a traffic generator application on top of my library that stresses the Linux kernel protocol stack to the extreme. It generates the proverbial 10k cps, saturates gigabit networks, etc.

It has no problem running over /dev/epoll.

IMHO, the code inside my wrapper library for the epoll case is significantly easier to understand than the code for the case that uses the legacy poll() interface.

If /dev/epoll were so error prone as you say it is, I think I would have noticed it.

-- Buck

ps If anybody cares. I can give them a pointer to my code.

The /dev/epoll usage is IMHO very simple. Once the I/O fd is created you register it with POLLIN|POLLOUT and you leave it inside the monitor set until it is needed ( mainly until you close() it ). It is not necessary to continuosly switch the event mask from POLLIN and POLLOUT. An hypothetical syscall API should look like :

int sys_epoll_create(int maxfds);
void sys_epoll_close(int epd);
int sys_epoll_addfd(int epd, int fd, int evtmask);
int sys_epoll_wait(int epd, struct pollfd **pevts, int timeout);

with the option ( if benchmarks will give positive results ) like Ben suggested, of using the AIO event collector instead of sys_epoll_wait().

- Davide

Hi Davide,

On thinking about this a bit, I wonder if the evtmask isn't superflous in sys_epoll_addf? (And in the existing epoll interface where the application writes to /dev/epoll).

As you say, the normal usage will be to register for all events anyway. My wrapper library does exactly that. As you say, not having to continously switch the mask is the simpler way to go. If registering for all events is the only sensible approach, the argument isn't needed at all.

What do you think? It's a minor detail, I know.

Taking the idea further, I would prefer that ALL non-blocking sockets are automatically added to the epoll interest set if the application has already called epoll_create(). Maybe that behaviour could be an option to epoll_create().

BTW, I'm not clear on another aspect of the API below, is there still an mmap() for the pollfd buffers?

-- Buck

Even if it is the fastest way to use the API, iI would still prefer such behaviour to be encoded in wrapper libraries instead of inside the API itself. Having a choice is usually better that not having it, if the cost for having a choice is not too much ( and in this particular case is not ).

Same thing, I would leave this task to your my_socket() and my_accept(). I think what is really missing about /dev/epoll is an easy-to-use interface library to avoid users confused by the presence of "poll" inside its name, to use it like select()/poll().

Yes, it creates a mapping shared between the kernel and the user space.

- Davide

I agree... but we might eventually have events that apps aren't interested in. No harm in letting app specify an interest mask once.

That would prevent apps from having more than one i/o readiness notification event source. This is a problem for modular software, where you try to combine libraries in a multithreaded program.

- Dan

You can also argue that the earth is flat. It's just that some arguments have more basis than others.

In other words, you don't deny the problem. Instead, you work around it in user space.

Better to fix the API. The kernel has more information than user space and can do a better job. In the kernel, the problem can be fixed once and for all, not over and over again in each different wrapper library. It's not even as if the change would break programs correctly written to the old API, not that we particularly care about programs written to the old API.

Not exactly. I'm saying that the context in which /dev/epoll is used (at least originally), is non-blocking socket IO. Anybody who has worked with that API can tell you there are subtleties, and that if they're ignored, will certainly lead to pitfalls. These are not the fault of the /dev/epoll interface.

I think we're talking across purposes.

I know this is the AIO list, but I think epoll has value independent of AIO. They're complementary, not mutually exclusive.

I agree if you are talking about AIO as a whole. But epoll is more limited in its scope, it really relates only to poll()/select not the whole IO api.

-- Buck

The particular subtlety I am pointing out is the fault of the currently defined /dev/epoll interface and can be fixed by making a minor change to the /dev/epoll interface.

My objection to the current /dev/epoll API does apply to said "limited scope," it is not dependent on the scope that is "AIO as a whole."

I think a chunk of the poll scaling problem is better addressed by futexes. If I can say "this futex list for this fd for events X Y and Z" I can construct almost all the efficient stuff I need out of the futex interfaces, much like doing it with SIGIO setting flags but a lot less clocks

Alan

I've structured the aio userland structure so that this is possible, just not implemented yet. There are fields for compatible and incompatible features, as well as the length of the header. This way, the library can implement a faster getevents call when futex support is added, but it always has the option of falling back to the syscall should it not understand any changes we make to the data structure.

-ben

"Do you seek knowledge in time travel?"

As long as we agree that the kernel may provide spurious readiness notifications on occasion, I agree. Then /dev/epoll can easily fulfill this by signaling readiness on everything at registration; more accurate notifications could be added later as an optimization.

- Dan

Shouldn't the should be rearmed inside read() when it returns EAGAIN? That's how I do it in my wrapper library these days.
No reason to have a race.

- Dan

Great! We agree! Progress!

The key phrase is "assuming registration of interest is inside wait()." The code fragment didn't cover when registration of interest occurs. If registration of interest occurs before the read() or if registration of interest while the fd is ready generates an event, there is no race. If registration of interest occurs after the read() and registration of interest while the fd is ready does not generate an event, there is a race.

I find myself still not understanding this thread. Lots of examples of code that should or should not be used, but I would always choose:

   ... ensure file descriptor is blocking ...
   for (;;) {
       int nread = read(...);
       ...
   }

Over the above, or any derivative of the above.

What would be the point of using an event notification mechanism for synchronous reads with no other multiplexed options?

A 'proper' event loop is significantly more complicated. Since everybody here knows this... I'm still confused...

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

I was afraid someone would be confused by the examples. Davide loves coroutines (check out http://www.xmailserver.org/linux-patches/nio-improve.html ) and I think his examples are written in that style. He really means what you think he should be meaning :-)
which is something like

    while (1) {
        grab next bunch of events from epoll
        for each event
            while (do_io(event->fd) != EAGAIN);
    }

I'm pretty sure.

- Dan

Yes, I like coroutines :) even if sometimes you have to be carefull with the stack usage ( at least if you do not want to waste all your memory ). Since there're N coroutines/stacks for N connections even 4Kb does mean something when N is about 100000. The other solution is a state machine, cheaper about memory, a little bit more complex about coding. Coroutines though helps a graceful migration from a thread based application to a multiplexed one. If you take a thread application and you code your connect()/accept()/recv()/send() like the ones coded in the example http server linked inside the epoll page, you can easily migrate a threaded app by simply adding a distribution loop like :

for (;;) {
	get_events();
	for_each_fd
		call_coroutines_associated_with_ready_fd();
}

- Davide

If each of these co-routines does "while (read() != EAGAIN) wait", your implementation is seriously flawed unless you do not mind certain file descriptors that may have lower numbers to have a real time priority higher than file descriptors with a higher number.

If efficiency is the true goal - the event loop itself needs to be abstracted - not just the query and dispatch routines. Using /dev/epoll in a way that it is compatible with other applications is an excercise in abuse, that will only show positive results because the alternatives to /dev/epoll are ineffective, not because /dev/epoll is a better model.

I like the idea of /dev/epoll - which means that if I used it, I would implement an efficient model with it, not a traditional model that through hackery will function transparently using /dev/epoll.

But that might just be me...

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

No, once a file descriptor is ready the associated coroutine is called with a co_call() and, for example, the read function is :

int dph_read(struct dph_conn *conn, char *buf, int nbyte)

{
    int n;

    while ((n = read(conn->sfd, buf, nbyte)) < 0) {
        if (errno == EINTR)
            continue;
        if (errno != EAGAIN && errno != EWOULDBLOCK)
            return -1;
        conn->events = POLLIN | POLLERR | POLLHUP;
        co_resume(conn);
    }
    return n;
}

where co_resume() preempt the current coroutine and run another one ( that is the scheduler coroutine ). The scheduler coroutine looks like :

static int dph_scheduler(int loop, unsigned int timeout)

{
    int ii;
    static int nfds = 0;
    struct dph_conn *conn;
    static struct pollfd *pfds = NULL;

    do {
        if (!nfds) {
            struct evpoll evp;

            evp.ep_timeout = timeout;
            evp.ep_resoff = 0;

            nfds = ioctl(kdpfd, EP_POLL, &evp);
            pfds = (struct pollfd *) (map + evp.ep_resoff);
        }
        for (ii = 0; ii < EPLIMTEVENTS && nfds > 0; ii++, nfds--, pfds++) {
            if ((conn = dph_find(pfds->fd))) {
                conn->revents = pfds->revents;

                if (conn->revents & conn->events)
                    co_call(conn->co, conn);
            }
        }
    } while (loop);
    return 0;
}

These functions are taken from the really simple example http server used to test/compare /dev/epoll with poll()/select()/rt-sig//dev/poll :

http://www.xmailserver.org/linux-patches/dphttpd_last.tar.gz

- Davide

They still represent an excessive complicated model that attempts to implement /dev/epoll the same way that one would implement poll()/select().

Sometimes the answer isn't emulation, or comparability.

Sometimes the answer is innovation.

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

epoll is about fixing one aspect of an otherwise well established api. That is, fixing the scalability of poll()/select() for applications based on non-blocking sockets.

Yes, programming non-blocking sockets has its complexity. Most people probably end up writing their own API to simplify things, building wrapper libraries above. However, a wrapper library can not fix the performance problems of poll()/select().

epoll() is a relatively modest kernel modification that delivers impressive performance benefits. It isn't exactly a drop in replacement for poll()/select(), especially because of the difference between level and edge semantics. That's why wrapper libraries make sense.

Yes, building a better API into the kernel makes sense. Not only to eliminate wrappers, but to generalize beyond sockets. I went to local user group meeting this week where a guy gave an overview of what's new in kernel 2.5. When AIO was presented, the first question was "why not use nonblocking IO?". I bet more than half the programmers in the room had no idea that nonblocking flags have absolutely no effect for files.

It seems to me that most people pushing on AIO so far have been using it for files, e.g. Oracle. They have no choice. It's either that or use clumsy worker thread arrangements. Network code on the other hand, has had non-blocking IO available for years. That's why there are all kinds of examples of web servers that use threads only for the disk side of things.

But let's not mix them up. AIO is a new model (for linux anyway), whose implementation is necessitating fairly major architectural changes to the kernel.

epoll is a nice well contained fix, that fits neatly into the existing architecture.

As it happens, epoll will probably have a place in AIO too. But there is no mutual dependency between them. They are both important on their own.

-- Buck

epoll is not a poll()/select() enhancement (unless it is used in conjuction with poll()/select()). It is a poll()/select() replacement.

Meaning... purposefully creating an API that is designed the way one would design a poll()/select() loop is purposefully limiting the benefits of /dev/epoll.

It's like inventing a power drill to replace the common screw driver, but rather than plugging the power drill in, manually turning the drill as if it was a socket wrench for the drill bit.

I find it an excercise in self defeat... except that /dev/epoll used the same way one would use poll()/select() happens to perform better even when it is crippled.

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

Agreed.
- Dan

Since the sys_epoll ( and /dev/epoll ) fd support standard polling, you can mix sys_epoll handling with other methods like poll() and the AIO's POLL function when it'll be ready. For example, for devices that sys_epoll intentionally does not support, you can use a method like :

	put_sys_epoll_fd_inside_XXX();
	...
	wait_for_XXX_events();
	...
	if (XXX_event_fd() == sys_epoll_fd) {
		sys_epoll_wait();
		for_each_sys_epoll_event {
			handle_fd_event();
		}
	}

- Davide

The more important question is why do you need epoll. asynchronous I/O completions setting a list of futexes can already be made to do the job and is much more flexible.

Alan, could you provide a code snipped to show how easy it is and how well it fits a 1:N ( one task/thread , N connections ) architecture ? And looking at Ben's presentation about benchmarks ( and for pipe's ), you'll discover that both poll() and AIO are "a little bit slower" than sys_epoll. Anyway I do not want anything superflous added to the kernel w/out reason, that's why, beside the Ben's presentation, there're curretly people benchmarking existing solutions.

- Davide

That's why I was hoping async poll would get fixed to have the same performance characteristics as /dev/epoll. But.... :-/

-ben

"Do you seek knowledge in time travel?"

Yep, like I wrote you yesterday ( and you did not answer ) is that I was trying to add supprt for AIO into the test HTTP server I use to do benchmark tests ( http://www.xmailserver.org/linux-patches/ephttpd-0.1.tar.gz ) but since there's no support for AIO POLL, it is impossible ( at least to my knowledge ) to compare sys_epoll and AIO on a "real HTTP load" networking test.

- Davide

If you would like this to happen, it would help if you would respond to questions asked and proposals made on the linux-aio mailing list. It's a little difficult trying to read your mind.

*Which* proposals? There was enough of a discussion that I don't know what people had decided on.

-ben

"Do you seek knowledge in time travel?"

Primarily the ones in my message of Tue, 15 Oct 2002 16:26:59 -0700. In that I repeat a question I posed in my message of Tue, 01 Oct 2002 14:16:23 -0700.

There's also the IOCB_CMD_NOOP strawman of Fri, 18 Oct 2002 17:16:41 -0700.

How does it perform?

That's going in unless there are any other objections to it from folks. Part of it was that I had problems with 2.4.43-bk not working on my test machines last week that delayed a few things.

-ben

"Do you seek knowledge in time travel?"

Ben,

Is there a patch against 2.5.44 with all the latest fixes that we can sync up with ?

Regards
Suparna

That was one of the questions, since you claimed it didn't "scale" without being specific as to which axes that was with respect to.

If the problem is the cost of reregistration (which seems likely) then fixing that requires extending the model upon which the aio framework is based. If the proposed extended model is not acceptable, it would be best to fix that before spending the time to implement it.

I don't think the big picture is that complicated.

epoll is useful for programs that use the old nonblocking socket API. It improves performance significantly for a case where poll() and select() are deficient (large numbers of slow or idle connections).

There are a number of people, including myself, who already use epoll. At least some of us don't think it is too complicated. I claim most of the complication is in the nonblocking socket API, in which case the complexity falls under the category of "the devil you know...".

The old nonblocking socket API (and hence epoll) does nothing for file IO, and it just doesn't make sense relative to file IO. (EAGAIN, POLLIN, POLLOUT, etc. aren't terribly useful signals from a disk device).

So, its a great thing that the new AIO API is forthcoming.

So maybe epoll's moment of utility is only transient. It should have been in the kernel a long time ago. Is it too late now that AIO is imminent?

-- Buck

This is not my call actually. But beside comparing actual performance between AIO and sys_epoll, one of the advantages that the patch had is this :

arch/i386/kernel/entry.S  |    4
drivers/char/Makefile     |    4
fs/Makefile               |    4
fs/file_table.c           |    4
fs/pipe.c                 |   36 +
include/asm-i386/poll.h   |    1
include/asm-i386/unistd.h |    3
include/linux/fs.h        |    4
include/linux/list.h      |    5
include/linux/pipe_fs_i.h |    4
include/linux/sys.h       |    2
include/net/sock.h        |   10
net/ipv4/tcp.c            |    4

That is, it has a very little "intrusion" in the original code by plugging in the existing architecture.

- Davide

epoll has another benefit: it works with read() and write(). That makes it easier to use with existing libraries like OpenSSL without having to recode them to use aio_read() and aio_write().

Furthermore, epoll is nice because it delivers one-shot readiness change notification (I used to think that was a drawback, but coding nonblocking OpenSSL apps has convinced me otherwise).
I may be confused, but I suspect the async poll being proposed by Ben only delivers absolute readiness, not changes in readiness.

I think epoll is worth having, even if Ben's AIO already handled networking properly.
- Dan

That depends on how it compares to async read/write, which hasn't been looked into yet. The way the pipe code worked involved walking the page tables, which is still quite expensive for small data sizes. With the new code, the CPU's tlb will be used, which will make a big difference, especially for the case where only a single address space is in use on the system.

-ben

"Do you seek knowledge in time travel?"

Ben, does it work at all currently read/write requests on sockets ? I would like to test AIO on networking using my test http server, and I was thinking about using poll() for async accept and AIO for read/write. The poll() should be pretty fast because there's only one fd in the set and the remaining code will use AIO for read/write. Might this work currently ?

- Davide

The socket async read/write code is not yet in the kernel.

-ben

"Do you seek knowledge in time travel?"

Ok, this pretty much stops every attempt to test/compare AIO with sys_epoll ... ETA ?

- Davide

It would be useful to compare async poll (the patch that started this thread) with sys_epoll. sys_epoll is expected to perform better since it ignores multithreading issues and amortizes registration across multiple events, but it would be interesting to know by how much.

I think this can be done, David Stevens ( IBM ) already proposed me the patch to test.

- Davide

Can someone remind me why poll is needed in the AIO api at all?

How would it be used?

-- Buck

Maybe my understanding of AIO on Linux is limited but how would you do async accept/connect ? Will you be using std poll/select for that, and then you'll switch to AIO for read/write requests ?

- Davide

I see. Adding async accept/connect would seem to make more sense to me.

-- Buck

If a connection is likely to be idle, one would want to use an async read poll instead of an async read in order to avoid having to allocate input buffers to idle connections. (What one really wants is a variant of async read that allocates an input buffer to an fd at completion time, not submission time).

Sometimes one wants to use a library which only has a nonblocking interface, so when the library says WOULDBLOCK you have to do an async write poll.

Sometimes one wants to use a kernel interface (e.g. sendfile) that does not yet have an async equivalent. Accept/connect are in this class--there should be nothing to prevent us from creating async versions of accept/connect.

In that situation, why not just add the fd to an epoll, and have the epoll deliver events through Ben's interface? That way you'd get notified of changes in readability, and wouldn't have to issue the read poll call over and over.

- Dan

Right. This does make sense for a server with thousands of idle
connections. You could have lots of unused memory in that case.

Right. I can see this too. This might be thorny for epoll though, since it's entirely conceivable that such libraries would be expecting level style poll semantics.

Right. However in this case, I think using poll is a stop gap solution.

It would be better to give accept, connect, and sendfile (and sendfile64) native status in AIO. Even if the implementations are not going to be ready for a while, I think their spots in the API should be reserved now.

That said, the first two points above convince me that there are valid reasons why poll is also needed in AIO.

-- Buck

Because you might need to use the aio_data facility of the iocb interface. Because you might want to keep the kernel from simultaneously delivering two events for the same fd to two different threads.

Why would you want to have a single fd simultaneously handled by two different threads with all the locking issues that would arise ? I can understand loving threads but this seems to be too much :)

- Davide

We in fact tried to do this and for good reason. Our nameserver sofware gets great benefit when two processes listen to the same socket on an SMP system. In some cases, this means 70% more packets/second, which is close to the theoretical maximum beneft.

We would heavily prefer to have two *threads* listening to the same socket instead of to processes. The two processes do not share caching information now because that expects to live in the same memory.

Right now, we can't do that because of very weird locking behaviour, which is documented here: http://www.mysql.com/doc/en/Linux.html and leads to 250.000 context switches/second and dysmal peformance.

I expect NPTL to fix this situation and I would just love to be able to call select() or poll() or recvfrom() on the same fd(s) from different threads.

Regards,

bert hubert

http://www.PowerDNS.com          Versatile DNS Software & Services
http://lartc.org           Linux Advanced Routing & Traffic Control HOWTO

I feel this topic is going somewhere else ;) ... but if you need your processes to share memory, and hence you would like them to be threads, you're very likely going to have some form of syncronization mechanism to access the shared area, don't you? So, isn't it better to have two separate tasks, that can freely access the memory w/out locks instead of N threads?

- Davide

You would not want this to happen. Thus you would want the poll facility to somehow prevent returning event N+1 until after the thread that got event N has somehow indicated that it has finished handling the event.

We're again looping talking about threads and fd being bounced between threads. It seems that we've very different opinions about the use of threads and how server applications should be designed. IMHO if you're thinking of bouncing fds among threads for their handling you're doing something somehow wrong, but this is just my opinion ...

- Davide

Again, it comes down to whether or not one has the luxury of being able to (re)write one's application and supporting libraries from scratch. If one can ensure that the code for handling an event will never block for any significant amount of time, then single-threaded process-per-CPU will most likely perform best. If, on the other hand, the code for handling an event can occasionally block, then one needs a thread pool in order to have reasonable latency.

A thread pool based server that is released will trivially outperform a single threaded server that needs a few more years development to convert all the blocking calls to use the event subsystem.

I beg you pardon but where an application is possibly waiting for ? Couldn't it be waiting to something somehow identifiable as a file ? So, supposing that an interface like sys_epoll ( or AIO, or whatever ) delivers you events for all your file descriptors your application is waiting for, why would you need threads ? In fact, I personally find that coroutines make threaded->single-task transaction very easy. Your virtual threads shares everything by default w/out having a single lock inside your application.

- Davide

The only uses of threads in a full aio application is task independence (or interactivity) and process context separation

Example from GUI side:
Suppose your web (http) client is fully ported to aio (thus only one thread), if you have two windows and one window receives a big complicated html page that needs much CPU time to render, this window can block the other one. If you have a thread for each window, once the html parser has elapsed its timeslice, the other window can continue parsing or displaying its (tiny html) page.
(In fact you should use two (or more) threads per window, as html parsing shouldn't block widget redrawing (like menus and toolbars))

It's not strictly necessary to use threads here. At least not with gtk+. I don't know whether other toolkits are the same.

Anyway with gtk+, you can install "idle callbacks". These are functions to be called whenever the GUI code has nothing to do. If you can transform your html parser(s) into idle function(s), then it won't necessarily disrupt the GUI. You just have to make sure that the parser yields periodically (returns to gtk+). Since parsers are loop oriented, this shouldn't be too hard, you just make each call to the function do 1 iteration of the top level loop.

My traffic generator, mxtraf, works this way. It has a software oscilliscope (gscope) that graphically displays signals in real time. At the same time it does lots of IO work to generate synthetic network traffic. mxtraf is single threaded.

-- Buck

--

Presumably epoll_add could be enhanced to let user specify a user data word.

You might want to use aio_write() for writes, and read() for reads, in which case you could tell epoll you're not interested in write readiness events. Then there'd be no double notification for reads or writes on same fd.
It's a bit contrived, but I can imagine it being useful.

- Dan

It'll take 2 minutes to do such a thing. Actually the pollfd struct contains the "events" field that is wasted when returning events and it could be used for something more useful.

- Davide

Also, I was just wondering if this might be usefull :

asmlinkage int sys_epoll_wait(int epfd, int minevents, struct pollfd **events, int timeout);

Where "minevents" rapresent the minimum number of events returned by sys_epoll ...

- Davide

Hem ... they're about 100 lines of code and they rapresent a complete I/O dispatching engine. And yes, like you could guess from the source code, the same skeleton was used, with different event retrieval methods, to test poll() , rt-sig , /dev/poll and /dev/epoll. And, as I said in the previous email, you could have implemented an I/O driven state machine. I personally like a little bit more coroutines, that the reason of such implementation.

- Davide

The main point here is determining which of many open connections need servicing.

select() and poll() do not scale well, so this is where stuff like /dev/epoll comes in--to tell you which of those file descriptors need to be serviced.

Chris

Chris Friesen                    | MailStop: 043/33/F10
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: [email protected]

I know what the point is, and I know the concept behind /dev/epoll.

I'm speaking more about the snippets of code that fail to show the real benefits of /dev/epoll, and the following discussion about which snippet is better than which other snippet.

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

Hi Ben,

I didn't address async poll's scalability vs. /dev/epoll because /dev/epoll isn't in the kernel either. I wasn't sure whether you had a better async poll in the making.

Either solution (/dev/epoll or async poll) would be a considerable improvement over what we have today.

So I guess the question would now be: whats keeping /dev/epoll from being included in the kernel given the time left before the feature freeze ?

-- Shailabh

We don't need yet another event reporting mechanism as /dev/epoll presents. I was thinking it should just be its own syscall but report its events in the same way as aio.

-ben

"Do you seek knowledge in time travel?"

Yes, Linus ( like myself ) hates magic inodes inside /dev. At that time it was the fastest way to have a kernel interface exposed w/out having to beg for a syscall. I'm all for a new syscall obviously, and IMHO /dev/epoll might be a nice complement to AIO for specific applications.

- Davide

So what would the syscall look like ? Could you give a few more details on the interface ?

- Shailabh

Something like this might work :

int sys_epoll_create(int maxfds);
void sys_epoll_close(int epd);
int sys_epoll_wait(int epd, struct pollfd **pevts, int timeout);

where sys_epoll_wait() return the number of events available, 0 for timeout, -1 for error.

- Davide

There's no reason to make epoll_wait a new syscall -- poll events can easily be returned via the aio_complete mechanism (with the existing aio_poll experiment as a possible means for doing so).

-ben

Ben, one of the reasons of the /dev/epoll speed is how it returns events and how it collapses them. A memory mapped array is divided by two and while the user consumes events in one set, the kernel fill the other one. The next wait() will switch the pointers. There is no copy from kernel to user space. Doing :

int sys_epoll_wait(int epd, struct pollfd **pevts, int timeout);

the only data the kernel has to copy to userspace is the 4(8) bytes for the "pevts" pointer.

- Davide

Erm, the aio interface has support for the event ringbuffer being accessed by userspace (it lives in user memory and the kernel acts as a writer, with userspace as a reader), that's one of its advantages -- completion events are directly accessible from userspace after being written to by an interrupt. Ideally this is to be wrapped in a vsyscall, but we don't have support for that yet on x86, although much of the code written for x86-64 should be reusable.

-ben

In general I would like to have a "common" interface to retrieve IO events, but IMHO the two solutions should be benchmarked before adopting the one or the other.

- Davide

Seems like /dev/epoll uses a double-buffering scheme rather than a ring buffer, and this is not just a trivial difference; it's related to how redundant events are collapsed, right?
- Dan

It's just a matter of implementation. With a double buffer you have clearly two distinct working zones, one is the user zone and the other is the kernel zone. With a ring buffer you have to mark what is the area that is currently returned as event set to the user and avoid the kernel to overflow on such area. The double buffer is probably faster and easy to implement ( for event collapsing ).

- Davide

Making the event ringbuffer visible to userspace conflicts with being able to support event priorities. To support event priorities, the ringbuffer would need to be replaced with some other data structure.

No it does not. Event priorities are easily accomplished via separate event queues for events of different priorities. Most hardware implements event priorities in this fashion.

-ben

"Do you seek knowledge in time travel?"

So a user would setup an ioctx and use io_getevents to retrieve events on an interest set of fds created and manipulated through the new system calls ?

-- Shailabh

Since i guess that w/out having the bility to add fds to the monitores set would make the API useless ...

int sys_epoll_addfd(int epd, int fd);

- Davide