Messages in this thread | | | Date | Sun, 28 Nov 2004 09:34:32 -0800 | From | Howard Chu <> | Subject | [Fwd: Re: >1024 connections in slapd / select->poll] |
| |
Hi there, I read your kqueue paper with great interest. Some other mechanisms were also suggested to me but kqueue is by far the most powerful/flexible I've seen so far. I would like to extend it a bit further though and wanted to get your feedback on the idea.
In adding support for Linux epoll() to OpenLDAP slapd one of the difficulties was that there is no direct way to ask "did descriptor N trigger" without walking through the entire list of returned events. This has to do with supporting prioritized events, certain descriptors must be processed before others. This is a key benefit of using select(), all the events are in a fixed array and any one can be accessed directly. kqueue also behaves the same way epoll does in this respect, and the documentation suggests that using multiple nested kqueues will allow prioritization. Certainly true, but that's somewhat clumsy, and requires a lot more work for the application developer.
My idea here is to use mapped/shared memory to store the event list. When returning a list of triggered events, the return list is simply a list of indices into the original event list. The actual event is flagged in the original event list. So apps that don't care about priority can still process events in the returned order, but with one additional dereference. Apps that do care about priority can find their events directly in the original list.
Let's call this approach "equeue" for the purposes of this discussion. There will be two system calls, analogous to kqueue/kevent. The first creates the queue. Like linux epoll() it takes an argument, the maximum size of its event list. Unlike epoll, this is a hard limit, because it maps a memory region for this size and the region is never grown after that. It takes another argument, a pointer to where to store the address of the allocated shared memory. int equeue( int size, struct equeue **addr );
The struct equeue describes the event list:
struct equeue { short maxevents; short nchanges; short *ievents; struct eevent events[]; };
This is just a header for the mapped region. Since we're using shorts for array indices there is a limit of 65535 events in an equeue. The actual layout of the mapped region is thus the header, followed by (maxevents) eevent structs, followed by the array of indices. The eevent structure is basically a kevent structure with an additional field containing the result flags for the event. The equeue struct is initialized by the equeue() system call before being returned to the user.
struct eevent { uintpt_t ident; /* identifier for event */ short filter; /* filter for event */ u_short flags; /* action flags */ u_int inflags; /* filter flags of interest */ u_int outflags; /* resulting flags */ intptr_t data; /* filter data value */ void *udata; /* opaque identifier */ };
A call to eevent() just needs two arguments - the fd returned from equeue(), and a timeout. The address of the mapped region is stored internally by the equeue() syscall, and is used implicitly by eevent().
On input, equeue.nchanges tells how many event structures are being controlled/modified and the ievents array gives the indices of each modified structure. On return from eevent() the equeue.nchanges tells how many events were triggered and the ievents array gives the indices of each triggered structure. A triggered event is reported by setting the outflags of the corresponding eevent struct.
This approach completely eliminates any copying of event records/descriptor lists between user/kernel space, so constructing event lists and modifying them is essentially zero-cost. Also, since the array of events remains in place, the application can inspect higher priority events of interest by direct reference.
As a further refinement, an event that is already registered can be masked and unmasked arbitrarily, by toggling a flag in the action flags. Masking an event leaves all the polling callbacks in place, but the callback will not wakeup the waiter. This saves any overhead of "adding" and "deleting" an event from the event list, when the app just wants to ignore it temporarily. (like sigprocmask, really.)
Toggling interest in descriptors is also something that slapd does frequently, and the epoll_ctl method really slows us down. With 2048 active connections slapd with epoll() is noticably slower than slapd with select() on a 2.6 Linux kernel, mainly because of this epoll_ctl overhead. Since kqueue combines event modification with event wait the overhead is probably lower, but I haven't tried it yet. Still, the lack of direct access to "event for descriptor X" makes it less usable.
I plan to implement this in the next month or two but wanted to get some feedback from you first, thanks. -- -- Howard Chu Chief Architect, Symas Corp. Director, Highland Sun http://www.symas.com http://highlandsun.com/hyc Symas: Premier OpenSource Development and Support
-------- Original Message -------- Date: Thu, 18 Nov 2004 22:15:40 -0800 From: Howard Chu <hyc@symas.com> To: Yusuf Goolamabbas <yusufg@outblaze.com> Cc: Volker.Lendecke@SerNet.DE, openldap-devel@OpenLDAP.org Subject: Re: >1024 connections in slapd / select->poll Comment: openldap-devel mailing list <http://www.OpenLDAP.org/lists/> List-Archive: <http://www.OpenLDAP.org/lists/openldap-devel/>
Yusuf Goolamabbas wrote:
>>Well if you're feeling brave, I've just completed a patch in CVS HEAD >>supporting epoll. I haven't tried testing it with a massive number of >>connections yet, but the code now passes the regular test suite. It >>should be simple enough to add kqueue support as well now (I would have >>begun that but I don't have BSD installed anywhere at the moment). >>Regular poll can easily be added if you want, but there's really no >>reason to. Solaris /dev/poll is a bit more awkward. >> >> > >Solaris 10 supports event ports which is supposedly thread friendly > >http://blogs.sun.com/roller/page/barts/20040720 >http://developers.sun.com/solaris/articles/event_completion.html > > Thanks for the links, good references. Of course they seem to confirm that there's no compelling reason to migrate away from select() in slapd...poll() blocks the entire process, /dev/poll has strict mutex requirements and performs poorly when the descriptor list changes frequently... epoll has some of that characteristic as well - modifying the descriptor set requires a system call, a trip across the user/kernel barrier. With select you just flip a bit in userspace and you're done. The Solaris event ports sound interesting, but I think anybody who develops a "new event handler" on Unix and forgets to support signal() at the outset has overlooked something important...
Anyway, it's too bad that everyone is just copying each other's ideas and not actually learning from the obvious limitations of all of these schemes. A real solution needs to not only perform well on large sets of monitored items, but it needs to be extremely cheap to create and manage these sets in the first place. Only select wins on that score, and the obvious solution to avoid the argument passing overhead that everyone seems so foolishly focused on is to use explicitly mapped memory for the event sets. I.e., mmap a region that is directly accessible in both user and kernel space so that no byte copying needs to be done.
Another point where select (and poll) wins is that there is a fast mapping from the input set to the result set - i.e., if you want to know "did event #5 occur?" you can find out in constant time, because it's just a fixed bitfield lookup. For all the other mechanisms that either return events one at a time or in a flat list, you have to iterate thru the list to look for "event #5". They have thus taken the linear search that the kernel does for select and kicked it out into userland, thus perceiving a great savings in kernel CPU time but not really improving life for the application developer. There is an obvious way to solve both of these problems with no additional cost - do both.
Define the input event set as an array of structures, as most of these mechanisms do. The array resides in a shared memory region. We can use a modified struct kevent as a typical structure: struct kevent { uintpt_t ident; /* identifier for event */ short filter; /* filter for event */ u_short flags; /* action flags */ u_int inflags; /* filter flags of interest */ u_int outflags; /* resulting flags */ intptr_t data; /* filter data value */ void *udata; /* opaque identifier */ }
kqueue is pretty darn good, but it still misses on the argument copying problem, its result set is an array of struct kevent's describing the results, and it doesn't give you direct access for priority management.The bulk of the struct is redundant information, all we want to know are the resulting flags and any data accompanying it.
What a really good, efficient mechanism would do is leave the input event array in place, set the result flags and data there, and return a list of *offsets* to all the entries in the array that got signaled. That way you can navigate the result list in priority order and in event order, all without expensive linear search time. (If your argument list is a mmap'd region, using offsets means you don't have to guarantee the region gets mapped to any particular address, but you can still remember the location of the relevant structure for a monitored object and access it in constant time.)
Maybe I'll write a patch for this for Linux over the holidays. Starting from either of poll or kqueue it would be pretty easy to fix this up right.
-- -- Howard Chu Chief Architect, Symas Corp. Director, Highland Sun http://www.symas.com http://highlandsun.com/hyc Symas: Premier OpenSource Development and Support
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |