Kernel Traffic #93 For 13 Nov 2000

I ran a benchmark to see how long a call to poll() takes as you increase the number of idle fd's it has to wade through. I used socketpair() to generate the fd's.

Under Solaris 7, when the number of idle sockets was increased from 100 to 10000, the time to check for active sockets with poll() increased by a factor of only 6.5. That's a sublinear increase in time, pretty spiffy.

Under Linux 2.2.14 [or 2.4.0-test1-pre4], when the number of idle sockets was increased from 100 to 10000, the time to check for active sockets with poll() increased by a factor of 493 [or 300, respectively]. This is terribly, horribly bad scaling behavior, since the time required appears to increase three times faster than the number of sockets.

Detailed measurements and the source code used to make them are available at http://www.kegel.com/dkftpbench/Poller_bench.html

Yeah. It's pretty spiffy.

Basically, poll() is _fundamentally_ a O(n) interface. There is no way to avoid it - you have an array, and there simply is _no_ known algorithm to scan an array in faster than O(n) time. Sorry.

(Yeah, you could parallellize it. I know, I know. Put one CPU on each entry, and you can get it down to O(1). Somehow I doubt Solaris does that. In fact, I'll bet you a dollar that it doesn't).

So what does this mean?

Either

1. Solaris has solved the faster-than-light problem, and Sun engineers should get a Nobel price in physics or something.
2. Solaris "scales" by being optimized for 10000 entries, and not speeding up sufficiently for a small number of entries.

You make the call.

Basically, for poll(), perfect scalability is that poll() scales by a factor of 100 when you go from 100 to 10000 entries. Anybody who does NOT scale by a factor of 100 is not scaling right - and claiming that 6.5 is a "good" scale factor only shows that you've bought into marketing hype.

In short, a 6.5 scale factor STINKS. The only thing it means is that Solaris is slow as hell on the 100 descriptor case.

what you're showing is that Linux actually is _closer_ to the perfect scaling (Linux is off by a factor of 5, while Solaris is off by a factor of 15 from the perfect scaling line, and scales down really badly).

Now, that factor of 5 (or 3, for 2.4.0) is still bad. I'd love to see Linux scale perfectly (which in this case means that 10000 fd's should take exactly 100 times as long to poll() as 100 entries take). But I suspect that there are a few things going on, one of the main ones probably being that the kernel data working set for 100 entries fits in the cache or something like that.

I suspect we could improve Linux in this area, but I hope that I pointed out the most fundamental mistake you did, which was thinking that "scalability" equals "speed". It doesn't.

Scalability really means that the effort to handle a problem grows reasonably with the hardness of the problem. And _deviations_ from that are indications of something being wrong.

Some people think that super-linear improvements in scalability are signs of "goodness". They aren't. For example, the classical reason for super-linear SMP improvement (with number of CPU's) that people get so excited about really means that something is wrong on the low end. Often the "wrongness" is lack of cache - some problems will scale better than perfectly simply because with multiple CPU's you have more cache.

The "wrongess" is often also selecting the wrong algorithm: something that "scales well" by just being horribly slow for the small case, and being "less bad" for the big cases.

In the end, the notion of "scalability" is meaningless. The only meaningful thing is how quickly something happens for the load you have. That's something called "performance", and unlike "scalability", it actually has real-life meaning.

Under Linux, I'm personally more worried about the performance of X etc, and small poll()'s are actually common. So I would argue that the Solaris scalability is going the wrong way. But as performance really depends on the load, and maybe that 10000 entry load is what you consider "real life", you are of course free to disagree (and you'd be equally right ;)

I hope nobody took my rant against "scalability" to mean that I consider the Solaris case to necessarily be bad engineering. My rant was more about people often thinking that "scalability == performance", which it isn't. It may be that Solaris simply wants to do 10000 entries really fast and that they actually do really well, but it is clear that if so they have a huge performance hit for the small cases, and people should realize that.

It's basically a matter of making the proper trade-offs. I think that the "few file descriptors" case is actually arguably a very important one. Sun (who has long since given up on the desktop) probably have a different tradeoff, and maybe their big constant setup-time is worth it.

I suspect a good interface that can easily be done efficiently would basically be something where the user _does_ do the equivalent of a read-only mmap() of poll entries - and explicit and controlled "add_entry()" and "remove_entry()" controls, so that the kernel can maintain the cache without playing tricks.

Basically, something like a user interface to something that looks like the linux poll_table_page structures, with the difference being that it doesn't have to be created and torn down all the time because the user would explicitly ask for "add this fd" and "remove this fd" from the table.

Th eproblem with poll() as-is is that the user doesn't really tell the kernel explictly when it is changing the table..

Actually, forget the mmap, it's not needed.

Here's a suggested "good" interface that would certainly be easy to implement, and very easy to use, with none of the scalability issues that many interfaces have.

First, let's see what is so nice about "select()" and "poll()". They do have one _huge_ advantage, which is why you want to fall back on poll() once the RT signal interface stops working. What is that?

Basically, RT signals or any kind of event queue has a major fundamental queuing theory problem: if you have events happening really quickly, the events pile up, and queuing theory tells you that as you start having queueing problems, your latency increases, which in turn tends to mean that later events are even more likely to queue up, and you end up in a nasty meltdown schenario where your queues get longer and longer.

This is why RT signals suck so badly as a generic interface - clearly we cannot keep sending RT signals forever, because we'd run out of memory just keeping the signal queue information around.

Neither poll() nor select() have this problem: they don't get more expensive as you have more and more events - their expense is the number of file descriptors, not the number of events per se. In fact, both poll() and select() tend to perform _better_ when you have pending events, as they are both amenable to optimizations when there is no need for waiting, and scanning the arrays can use early-out semantics.

So sticky arrays of events are good, while queues are bad. Let's take that as one of the fundamentals.

So why do people still like RT signals? They do have one advantage, which is that you do NOT have that silly array traversal when there is nothing to do. Basically, the RT signals kind of approach is really good for the cases where select() and poll() suck: no need to traverse mostly empty and non-changing arrays all the time.

It boils down to one very simple rule: dense arrays of sticky status information is good. So let's design a good interface for a dense array.

Basically, the perfect interface for events would be

struct event {

unsigned long id; /* file descriptor ID the event is on */
unsigned long event; /* bitmask of active events */

};
 
int get_events(struct event * event_array, int maxnr, struct timeval *tmout);

where you say "I want an array of pending events, and I have an array you can fill with up to 'maxnr' events - and if you have no events for me, please sleep until you get one, or until 'tmout'".

The above looks like a _really_ simple interface to me. Much simpler than either select() or poll(). Agreed?

Now, we still need to inform the kernel of what kind of events we want, ie the "binding" of events. The most straightforward way to do that is to just do a simple "bind_event()" system call:

int bind_event(int fd, struct event *event);

which basically says: I'm interested in the events in "event" on the file descriptor "fd". The way to stop being interested in events is to just set the event bitmask to zero.

Now, the perfect interface would be the above. Nothing more. Nothing fancy, nothing complicated. Only really simple stuff. Remember the old rule: "keep it simple, stupid".

The really nice part of the above is that it's trivial to implement. It's about 50 lines of code, plus some simple logic to various drivers etc to actually inform about the events. The way to do this simply is to limit it in very clear ways, the most notable one being simply that there is only one event queue per process (or rather, per "struct files_struct" - so threads would automatically share the event queue). This keeps the implementation simple, but it's also what keeps the interfaces simple: no queue ID's to pass around etc.

Implementation is straightforward: the event queue basically consists of

• a queue head in "struct files_struct", initially empty.
• doing a "bind_event()" basically adds a fasync entry to the file structure, but rather than cause a signal, it just looks at whether the fasync entry is already linked into the event queue, and if it isn't (and the event is one of the ones in the event bitmask), it adds itself to the event queue.
• get_event() just traverses the event queue and fills in the array, removing them from the event queue. End of story. If the event queue is empty, it trivially sees that in a single line of code (+ timeout handling)

Advantage: everything is O(1), except for "get_event()" which is O(n) where 'n' is the number of active events that it fills in.

Basically, I can't see that it can be done much simpler, and I don't see that you can have much better performance.

I think this is a lot cleaner than your approach:

• it doesn't add extra syscalls
• it handles multiple event queues, and does so without ugliness. all the per-queue state is held in the /dev/poll's "struct file" instance
• in your method you have a per-process queue - but under what clone() conditions is it shared among siblings? Here the user has a choice - they can share the open("/dev/poll/index.html") file descriptor or not using any of the existing means. Granted, they also would probably want to arrange to share the fd's being polled in order to make this useful.
• No new fields in task_struct

A few simple improvements can be made to the Sun model, though:

• The fact that the fd of /dev/poll can't be used for poll(2) or select(2) is ugly. Sure, you probably don't want an open instance of /dev/poll being added to another /dev/poll, but being able to call "select" on them would be really useful:

  1. Imagine a server that has to process connections from both high-priority and low-priority clients - and that requests from the high-priority ones always take precedence. With this interface you could easily have two open instances of /dev/poll and then call select(2) on them. This ability just falls out naturally from the interface.
  2. Some libraries are internally driven by select(2) loops (I think Xlib is like this, IIRC) If you have a lot of fd's you want to watch, this means you must take the hit of calling select(2) on all of them. If you could just pass in a fd for /dev/poll, problem solved.

• I think the fact that you add events via write(2) but retrieve them via ioctl(2) is an ugly asymmetry. From what I can see, the entire motivation for using ioctl as opposed to read(2) is to allow the user to specify a timeout. If you could use poll(2)/select(2) on /dev/poll this issue would be moot (see above)
• It would be nice if the interface were flexible enough to report items _other_ than "activity on fd" in the future. Maybe SYSV IPC? itimers? directory update notification? It seems that every time UNIX adds a mechanism of waiting for events, we spoil it by not making it flexible enough to wait on everything you might want. Lets not repeat the mistake with a new interface.
• The "struct pollfd" and "struct dvpoll" should also include a 64-bit opaque quantity supplied by userland which is returned with each event on that fd. This would save the program from having to look up which connection context goes with each fd - the kernel could just give you the pointer to the structure. Not having this capability isn't a burden for programs dealing with a small number of fd's (since they can just have a lookup table) but if you potentially have 10000's of connections it may be undesirable to allocate an array for them all.

The linux patch of /dev/poll implements mmap'ing of the in-kenrel poll table... I don't think this is a good idea. First, the user just wants to be able to add events and dequeue them - both linear operations. Second, why should the kernel be forced to maintain a fixed-size linear list of events we're looking for... this seems mindlessly inefficient. Why not just pull a "struct pollfd" out of slab each time a new event is listened for?

My unresolved concerns:

• Is this substantially better than the already existing rtsig+poll solution? Enough to make implementing it worth while?
• How do we quickly do the "struct file" -> "struct pollfd" conversion each time an event happens? Especially if there are multiple /dev/poll instances open in the current process. Probably each "struct file" would need a pointer to the instance of /dev/poll which would have some b-tree variant (or maybe a hash table). The limitation would be that a single fd couldn't be polled for events by two different /dev/poll instances, even for different events. This is probably good for sanity's sake anyway.

Sure it does.

What do you think ioctl's are? Every single ioctl number is an extra system call. It's just indirected inside the device driver instead of at the normal system call entry point. The advantage? It's noticeably slower than a real system call.

I've actually read the BSD kevent stuff, and I think it's classic over-design. It's not easy to see what it's all about, and the whole <kq, ident, filter> tuple crap is just silly. Looks much too complicated.

I don't believe in the "library" argument at all, and I think multiple event queues completely detract from the whole point of being simple to use and implement.

It seems that gcc-2.7.2.3 is terminally ill. I'd rather change Documentation/Changes, and just document the fact.

These kinds of subtle work-arounds for gcc bugs are not really acceptable, nor is it worthwhile complaining when somebody does development with a gcc that is _not_ broken, and doesn't notice that some random gcc bug breaks the kernel for others.

• 2.91.66 aka egcs 1.1.2. It has been officially blessed for 2.4 and has been given an informal thumbs-up by Alan for 2.2. (It does NOT work for 2.0, if you still care about that.)
• 2.7.2.3 works for 2.2 (and 2.0) but NOT for 2.4.
• 2.95.2 seems to work with both 2.2 and 2.4 (no known bugs, AFAIK) and many of us use it, but it is a little riskier than egcs.
• Red Hat "2.96" or CVS 2.97 will probably break any known kernel.

Something like the following at the end of your initrd /linuxrc script should mount your ramfs, copy the existing root fs files to it, pivot and unmount your old root. YMMV

mkdir -p /ramfs /ram1
mount -t ramfs /ramfs /ramfs
find / | sed '/^\/ramfs/d;/^\/proc\/.*/d/index.html' | cpio -pdmV /ramfs
cd /ramfs
pivot_root . ram1
exec chroot . sh -c 'umount /ram1; exit' < dev/console >dev/console

Ouch. This was it. I simply overlooked this option and used the one that worked with 2.2...

But it would be nice if the kernel could detect the wrong CPU type and print a message before it stops. Perhaps compile the init section without CPU specific optimization?

The OSS API (http://www.opensound.com/pguide/oss.pdf, page 102ff) specifies that a select _with the sounddriver's filedescriptor set in the read mask_ should start the recording.

Implementing this is currently not possible, as the driver does not get to know whether the application had the filedescriptor set in the select call. Similarily for poll, the driver does not get the caller's events.

Different drivers do it differently. The ISA SB driver just unconditionally starts recording on select, whether the bit in the read mask is set or not. es137* unconditionally does not start recording. Both drivers violate the API.

I don't think this is all that important though, because it's that way for more than a year and the first complaint reached me yesterday.

Considering that about 100% of the sound drivers do not follow that particular API damage anyway (they can't, as has been pointed out: the driver doesn't even receive enough information to be _able_ to follow the documented API), I doubt that there are all that many programs that depend on it.

Yes, some drivers apparently _try_ to follow the spec to some degree, but we should just change the documentation asap.

Looks like all @wanadoo.fr addresses have been kicked out.

That ISP has a habit of returning 500-series reponse codes with supplementary text of style: "System is too busy, please come back latter"

Which of course generates error bounce (like all 500 series codes are supposed to by the RFC 821) leading to removal of erroring address from the list.

Had we fully automated the removal process, both WANADOO.FR and GMX.NET/GMX.DE/GMX.AT users would get kicked out every day around 18-24 CET (UTC+1h). Now it is matter of manual oversight, and while I have been lenient letting those users be, listowners have different minds.

After a stranger than usual late-night #kernelnewbies session on Thursday, I was inspired to come up with Kernel Hangman. This is the traditional game of hangman, except that the words you have to guess are kernel symbols.

So, test your knowledge of kernel trivia and play it at http://user-mode-linux.sourceforge.net/cgi-bin/hangman