Importing kqueue's from FreeBSD...
Simon J. Gerraty
>implementation of kqueue in FreeBSD, a few NetBSD developers
>present decided that it's definately worth a look for NetBSD.
Yes I'd like to see this in netbsd. It would be nice if the enhancements
Jason mentioned could be done while maintaining API compatability.
But even as is I think it worth having.
--sjg
Luke Mewburn
implementation of kqueue in FreeBSD, a few NetBSD developers
present decided that it's definately worth a look for NetBSD.
kqueue (aka `kevent') is a generic and scalable event
notification facility, developed by Jonathan Lemon of FreeBSD.
It's generic: you can monitor socket events, filesystem events
such as `file ready to read', vnode operations such as `file has been
deleted', `directory has been modified', signals delivered to a
process, process creation/exit, etc.
It's scalable: time to process increases linearly with respect to
number of outstanding events (such as `socket waiting to be read'),
unlike select & poll where the time increases with respect to the
number of sockets listened to.
It supports multiple listeners for the same event. FreeBSD has had it
in a couple of releases, and I believe third party vendors such as
Apache are already using the API. Other API's such as Solaris'
/dev/poll and Irix's /dev/imon provide a subset of what kqueue offers.
Jonathan has more information, both the original paper and the slides
he presented at BSDCon 2000, up at:
http://people.freebsd.org/~jlemon/
It's also referenced in a great paper on server scalability:
http://www.kegel.com/c10k.html
I think we need this in NetBSD; it would be of great benefit to
various applications that need scalability. If we do import this,
I feel that it's imperative that we maintain the same API as FreeBSD,
or if we feel it needs enhancing, at least work with Jonathan to
maintain compatibility with FreeBSD. There's no point in doing an API
like this for third-party application vendors that is gratuitiously
incompatible with FreeBSD where the API originated from.
I have ported his original diffs to FreeBSD into NetBSD, and
incorporated most of the patches and fixes made in FreeBSD after the
original import into FreeBSD; everything except the recent rework to
move the filesystem kqueue code lower down to make it more generic - I
wanted to get it working first.
I have this almost working, modulo a couple of panics in certain
conditions that I'm debugging. (These only occur if I create a kqueue
and try to trigger a certain event.)
I'd like to bring these into -current, #ifdef-ed appropriatly, to
allow others to `bang' on the code as well.
Thoughts/comments?
--
Luke Mewburn <lu...@wasabisystems.com> http://www.wasabisystems.com
Luke Mewburn <lu...@netbsd.org> http://www.netbsd.org
Wasabi Systems - providing NetBSD sales, support and service.
Jason R Thorpe
> I'd like to bring these into -current, #ifdef-ed appropriatly, to
> allow others to `bang' on the code as well.
>
> Thoughts/comments?
Why #ifdef'd?
If we do get this, we should make select(2) and poll(2) use the same
underlying "event" notification mechanism, instead of the current
selinfo stuff. It's pretty silly to have both.
kqueue, while being "generic", has no way to add filters, etc. without
modifying the API -- to add a constant representing the filter, event,
etc. This is seriously broken and must be addressed if we're going to
call it "generic".
--
-- Jason R. Thorpe <tho...@zembu.com>
Jarommr Dolecek
> kqueue (aka `kevent') is a generic and scalable event
> notification facility, developed by Jonathan Lemon of FreeBSD.
>
> It's generic: you can monitor socket events, filesystem events
> such as `file ready to read', vnode operations such as `file has been
> deleted', `directory has been modified', signals delivered to a
> process, process creation/exit, etc.
This facility seems like fit for the kernel event mechanism we
were occasionally muttering about on lists :) Definitely, it'll
be a good thing to bring it into NetBSD. Thanks for the
integration work, Luke!
> I'd like to bring these into -current, #ifdef-ed appropriatly, to
> allow others to `bang' on the code as well.
#ifdef-ed for now; I think it makes sence to make this non-optional
eventually.
Jaromir
--
Jaromir Dolecek <jdol...@NetBSD.org> http://www.ics.muni.cz/~dolecek/
*** Wanna a real operating system ? Go and get NetBSD, dammit! ***
e...@netbsd.org
After I saw a presentation at BSDCon 2000 last year about the
implementation of kqueue in FreeBSD, a few NetBSD developers
present decided that it's definately worth a look for NetBSD.
kqueue (aka `kevent') is a generic and scalable event
notification facility, developed by Jonathan Lemon of FreeBSD.
It's generic: you can monitor socket events, filesystem events
such as `file ready to read', vnode operations such as `file has been
deleted', `directory has been modified', signals delivered to a
process, process creation/exit, etc.
If you want to claim it is a generic event mechanism it also
needs to support device events: insertion, removal, errors,
etc.
Eduardo
Jarommr Dolecek
> If you want to claim it is a generic event mechanism it also
> needs to support device events: insertion, removal, errors,
> etc.
That is just SMOP :)
'Generic' means that the API is not bound to any particular
event type. It doesn't mean that it has to support all possible
events the day it's brought in ;-)
Luke Mewburn
We could add a new event type (EVFILT_DEVICE (?)) and add support into
various device layers to raise this event. I have no objection to
doing this; it makes perfect sense to me.
I think the reason why jlemon classified it as generic was that:
a) it already supports a bunch of different type of events, and
b) it's fairly simple to add new event types, even if currently it
requires adding new types to <sys/event.h>. I have thoughts
about how to make this easier for dynamic event addition
(e.g., for lkm's); they need to be fleshed out a bit more first.
I don't think it would be appropriate to hold back incorporation
of this work because it does have every event time that anyone can
think of right now.
Jonathan Stone
>On Thu, Mar 15, 2001 at 04:59:25PM -0000, e...@netbsd.org wrote:
>
>I don't think it would be appropriate to hold back incorporation
>of this work because it does have every event time that anyone can
>think of right now.
"type"?
What's the userlevel api? Can it easily support explicit
event-notification mechanism like the one (iirc) Gaurav Banga and Jeff
Mogul proposed as a replacement for poll()/select(), for
single-threaded apps with thousands of "interesting" objects?
(I'd UTSL if i wasnt writing my thesis...)
Jonathan Lemon
>On Thu, Mar 15, 2001 at 04:59:25PM -0000, e...@netbsd.org wrote:
>>
>> implementation of kqueue in FreeBSD, a few NetBSD developers
>> present decided that it's definately worth a look for NetBSD.
>>
>> kqueue (aka `kevent') is a generic and scalable event
>> notification facility, developed by Jonathan Lemon of FreeBSD.
>>
>> It's generic: you can monitor socket events, filesystem events
>> such as `file ready to read', vnode operations such as `file has been
>> deleted', `directory has been modified', signals delivered to a
>> process, process creation/exit, etc.
>>
>> If you want to claim it is a generic event mechanism it also
>> needs to support device events: insertion, removal, errors,
>> etc.
>
>We could add a new event type (EVFILT_DEVICE (?)) and add support into
>various device layers to raise this event. I have no objection to
>doing this; it makes perfect sense to me.
Yup, this is something that should be done eventually; I'd like to
try and keep all 3 *BSD's in sync if possible. (OpenBSD has already
brought over the code).
I also didn't want to try and write every possible filter type ahead
of time, but wanted to wait until there was actually a need for them.
In any case, I'm glad to see kqueue go into NetBSD, and would be
happy to provide any assistance if needed.
--
Jonathan
Nathan J. Williams
The kqueue system seems like a reasonable way to avoid the overhead
seen by applications that want notification of events, but how much
overhead is incurred on the rest of the system by the knote() calls,
compared to the current infrastructure?
The performance numbers referred to by the paper don't address this at
all.
- Nathan
Jonathan Lemon
>On Thu, Mar 15, 2001 at 03:33:37PM +1100, Luke Mewburn wrote:
>
> > allow others to `bang' on the code as well.
> >
>
>Why #ifdef'd?
>
>If we do get this, we should make select(2) and poll(2) use the same
>underlying "event" notification mechanism, instead of the current
>selinfo stuff. It's pretty silly to have both.
I'd like to do that, but its not quite that simple. I've been trying
to think of a clean way to accomplish this and haven't found one yet.
>kqueue, while being "generic", has no way to add filters, etc. without
>modifying the API -- to add a constant representing the filter, event,
>etc. This is seriously broken and must be addressed if we're going to
>call it "generic".
Actually, the API was designed with a third syscall in mind: kfilter().
The idea here was to allow new filters to be dynamically loaded/registered
by the system, while keeping a small number of "standard" filters
available (read/write). However, I never got around to doing this.
--
Jonathan
e...@netbsd.org
We could add a new event type (EVFILT_DEVICE (?)) and add support into
various device layers to raise this event. I have no objection to
doing this; it makes perfect sense to me.
I think the reason why jlemon classified it as generic was that:
a) it already supports a bunch of different type of events, and
b) it's fairly simple to add new event types, even if currently it
requires adding new types to <sys/event.h>. I have thoughts
about how to make this easier for dynamic event addition
(e.g., for lkm's); they need to be fleshed out a bit more first.
I don't think it would be appropriate to hold back incorporation
of this work because it does have every event time that anyone can
think of right now.
I think that needing to add new event types to <sys/event.h> is
a problem. The issue is not being able to handle every event that
anyone can think of but being able to add events without fears of
conflicts. Since the interface is exported to userland, we shouldn't
need to recompile the universe because someone added a new event type.
I'm afraid that this limitation will eventually require the interface
be replaced by something more flexible, so I really would like to
have that issue addressed first.
Eduardo
Luke Mewburn
> In message <2001031607...@wasabisystems.com>Luke Mewburn writes
> >
> >I don't think it would be appropriate to hold back incorporation
> >of this work because it does have every event time that anyone can
> >think of right now.
>
> "type"?
yup. `oops'.
> What's the userlevel api? Can it easily support explicit
> event-notification mechanism like the one (iirc) Gaurav Banga and Jeff
> Mogul proposed as a replacement for poll()/select(), for
> single-threaded apps with thousands of "interesting" objects?
yup. kqueue is designed explicitly for this. e.g, watching 10000's of
fd's where only a few actually have outstanding interesting events.
the following code fragment will print the number of times SIGCHLD
is delivered to the process:
int kq;
struct kevent event[1];
/* create kqueue */
kq = kqueue();
if (kq < 1)
err(1, "kqueue");
/* setup event to watch for */
event[0].ident = SIGCHLD;
event[0].filter = EVFILT_SIGNAL;
event[0].flags = EV_ADD | EV_ENABLE;
n = kevent(kq, event, 1, NULL, 0, NULL);
if (n < 0)
err(1, "kevent(1)");
/* ... do stuff ... */
sleep(10);
/* look for events outstanding */
for (;;) {
n = kevent(kq, NULL, 0, event, 1, NULL);
if (n < 0)
err(1, "kevent(2)");
printf("kevent flags: 0x%x, data: %ld (times signal posted)\n",
event[0].flags, event[0].data);
}
read jlemon's paper and skim through jlemon's slides. it does a good job
of explaining this.
Charles M. Hannum
On Thu, Mar 15, 2001 at 03:40:49PM -0600, Jonathan Lemon wrote:
>
> If there is no knote attached to the structure being monitored, then
> the overhead is just a single if() statement. Otherwise, the overhead
> is roughly O(N), where N is the number of knotes attached to the structure.
One of the interesting things about the Solaris and /dev/poll is that
the SVR4 poll(2) lended itself to reusing the structures for both
interfaces without introducing overhead in the `nobody listening' case.
Jonathan Lemon
I'll admit the performance section of the paper is sadly lacking; I'm
working on that at the moment.
If there is no knote attached to the structure being monitored, then
the overhead is just a single if() statement. Otherwise, the overhead
is roughly O(N), where N is the number of knotes attached to the structure.
The actual time required varies, as it depends on what the filter
routine does; for this reason, it's a good idea to keep the filters
short and sweet.
--
Jonathan
Bill Sommerfeld
> the SVR4 poll(2) lended itself to reusing the structures for both
> interfaces without introducing overhead in the `nobody listening' case.
Indeed.
It seems that it should be possible to migrate towards a common
in-kernel event interface which handles the following cases..
- process waiting in select() or poll()
- process sleeping for event in blocking read() or what have you
- process has SIGIO established on descriptor.
- in-kernel subsystem wants callback ..
- process has kevent established
.. with a single hook which just walks down a list of callbacks/"filters".
Look at sowakeup() in uipc_socket2.c for instance (it currently
handles the 4 of the 5 above which are included in NetBSD). That's
gotta hurt since in most cases only one of the notifications will be
in use for any given socket.
- Bill
Jason R Thorpe
> I'll admit the performance section of the paper is sadly lacking; I'm
> working on that at the moment.
>
> If there is no knote attached to the structure being monitored, then
> the overhead is just a single if() statement. Otherwise, the overhead
> is roughly O(N), where N is the number of knotes attached to the structure.
Yah, seems to me roughly like the overhead of selwakeup(), except not
nearly as pathological when multiple things are looking at a particular
e.g. socket.
I have no beef with kqueue other than the lack of really really really
generic event type stuff.
For example, luke said EVFILT_DEVICE -- ok, so, the problem is that you
get notified that an EVFILT_DEVICE event occurred... was it an insert or
a removal? How do you tell? Unless I missed something, there doesn't
seem to be any way of passing down ancillary data with the event.
Jonathan Lemon
Each filter has a private flag word and a data word that they can
define for their own use. An EVFILT_DEVICE filter may define some of
the bits in them to mean inserted/removed/suspended, "current status",
or whatever the filter wants to return.
--
Jonathan
Jason R Thorpe
> What's the userlevel api? Can it easily support explicit
> event-notification mechanism like the one (iirc) Gaurav Banga and Jeff
> Mogul proposed as a replacement for poll()/select(), for
> single-threaded apps with thousands of "interesting" objects?
Uh, read jlemon's paper -- he wrote it after reading Mogul's paper,
and it does indeed perform that function (with a much nicer interface
than Mogul's, I might add...)
Bill Sommerfeld
> to pass back a lot of data. I have a filter that does this, for example,
> by using copyout() to pass out multiple socket fd's, peer/local addresses,
> and so forth.
this suggests to me that the "filter" callback should really be in 3
parts..
- one invoked when a process first asks for the event (invoked in
that process).
- one invoked when the event happens (which could be in any context
-- interrupt level, process context of some other process, ...)
- one invoked when the event actually gets posted to the process
(again invoked in that process)
- Bill
Jason R Thorpe
> Each filter has a private flag word and a data word that they can
> define for their own use. An EVFILT_DEVICE filter may define some of
> the bits in them to mean inserted/removed/suspended, "current status",
> or whatever the filter wants to return.
Hm -- might be nice if there was a way to get a bigger blob of data
than just a single word...
Jonathan Lemon
Hah. I had that discussion in the early days of the design of kqueue
with matt dillon. The problem is always, how many words is enough?
There is always an application that just wants one more word than
provided. So I provided u_int flag, an intptr_t data, which should be
enough to either pass back data in-band or provide information where
to find things out-of band. This doesn't count the void *udata field
either.
The answer I came up with was to use a backchannel if you really want
to pass back a lot of data. I have a filter that does this, for example,
by using copyout() to pass out multiple socket fd's, peer/local addresses,
and so forth.
--
Jonathan
Bill Sommerfeld
>
> > - one invoked when a process first asks for the event (invoked in
> > that process).
>
> the kernel?
nope, for preallocating any additional space needed so that code
called at interrupt level won't "lose" an event because of a temporary
resource shortage.
- Bill
Jason R Thorpe
> this suggests to me that the "filter" callback should really be in 3
> parts..
I agree with you except for:
> - one invoked when a process first asks for the event (invoked in
> that process).
I don't understand what this one would be for -- for copyting data into
the kernel? IIRC, the current "user provided data" is simply a pointer
into the user's address space that is passed as-is when the event occurs.
The example provided in the paper was to use it to dispatch the handler
function (i.e. the pointer was just a pointer to a function, and you simply
jump through it).
> - one invoked when the event happens (which could be in any context
> -- interrupt level, process context of some other process, ...)
> - one invoked when the event actually gets posted to the process
> (again invoked in that process)
>
> - Bill
>
>
--
Luke Mewburn
> implementation of kqueue in FreeBSD, a few NetBSD developers
> present decided that it's definately worth a look for NetBSD.
i've put a diff up at:
ftp://ftp.netbsd.org/pub/NetBSD/misc/lukem/kqueue-010319.diffs
there's also a simple test suite and a todo list.
this is a work in progress; i haven't had a chance to look at this
seriously for a couple of weeks.
Erik E. Fair
>I think that needing to add new event types to <sys/event.h> is
>a problem. The issue is not being able to handle every event that
>anyone can think of but being able to add events without fears of
>conflicts. Since the interface is exported to userland, we shouldn't
>need to recompile the universe because someone added a new event type.
>I'm afraid that this limitation will eventually require the interface
>be replaced by something more flexible, so I really would like to
>have that issue addressed first.
I'd like to amplify Eduardo's point, and add that since we work hard
on binary compatability with Linux and UNIX-like OS's, we will need
to coordinate event identifier assignment with everyone else who
wants to use this API, or resign ourselves to maintaining event
translation tables in the emulation layers.
We might want to consider establishing a common registry for stuff
like this (system call numbers, event identifiers, device major
numbers, etc) among the *BSD's...
Erik <fa...@clock.org>
e...@netbsd.org
Actually, that was not exactly what I was looking for. Registries
always have problems since generating a consensus about who
controls the registry is difficult, and experimental code is
usually built before registering with the authority.
I would prefer something that uses strings to identify events
to userland so new event types could be created without
much fear that they would conflict. By qualifying the
event by a subsystem type, the probablility of conflict
between two different events would be minimal.
In the kernel, the strings could be hashed and manipulated
by the hash values to speed processing.
Eduardo
Charles M. Hannum
On Mon, Mar 19, 2001 at 04:21:45PM -0000, e...@netbsd.org wrote:
>
> I would prefer something that uses strings to identify events
> to userland so new event types could be created without
> much fear that they would conflict. By qualifying the
> event by a subsystem type, the probablility of conflict
> between two different events would be minimal.
As I've already pointed out elsewhere, copying strings in and out of
the kernel for poll(2)/select(2)-like functionality would be a
significant CPU hit, which partly defeats the point of doing this in
the first place.
Luke Mewburn
> On Mon, Mar 19, 2001 at 04:21:45PM -0000, e...@netbsd.org wrote:
> > to userland so new event types could be created without
> > much fear that they would conflict. By qualifying the
> > event by a subsystem type, the probablility of conflict
> > between two different events would be minimal.
>
> the kernel for poll(2)/select(2)-like functionality would be a
> significant CPU hit, which partly defeats the point of doing this in
> the first place.
In order to solve eeh's preferences, there was an alternative
solution; support a string->kqueuefilter lookup:
struct kevent event[1];
int fd, type;
kq = kqueue();
if (kq < 0)
err(1, "kqueue");
/* the following is new */
type = kqueue_filtertype("read");
event[0].ident = fd;
event[0].filter = type; /* instead of EVFILT_READ */
event[0].flags = EV_ADD | EV_ENABLE;
if (kevent(kq, event, 1, NULL, 0, NULL) < 0)
err(1, "kevent");
In this case, int kqueue_filtertype(const char *) checks the kernel
for a list of already registered filters and returns an int to be used
as the filter type. When support is added for the functionality to
allow extra filters to be registered, that registration function could
also take the string as the identifier.
It shouldn't matter if the string->id conversion returns different
numbers for the same string across reboots; it only has to be
consistent per reboot.
I think this solve's eeh's (and thorpej's) concerns about allowing
arbitrary filters to be defined, without requiring strings to be used
at all times. There's still a potential for namespace clash (if two
third party lkm vendors choose the same string), but it's far less
likely than two vendors choosing the same int.
PS: excuse me if this isn't coherent; I'm feeling unwell.
Jason R Thorpe
> type = kqueue_filtertype("read");
> I think this solve's eeh's (and thorpej's) concerns about allowing
> arbitrary filters to be defined, without requiring strings to be used
> at all times. There's still a potential for namespace clash (if two
> third party lkm vendors choose the same string), but it's far less
> likely than two vendors choosing the same int.
No, this is a fine solution, and there is a way to deal with the
clash.
Here is a quote from draft-ietf-secsh-architecture-08.txt:
o Names that do not contain an at-sign (@) are reserved to be assigned
by IETF consensus (RFCs). Examples include `3des-cbc', `sha-1',
`hmac-sha1', and `zlib' (the quotes are not part of the name). Names
of this format MUST NOT be used without first registering them.
Registered names MUST NOT contain an at-sign (@) or a comma (,).
o Anyone can define additional algorithms by using names in the format
name@domainname, e.g. "ourcip...@ssh.com". The format of the part
preceding the at sign is not specified; it MUST consist of US-ASCII
characters except at-sign and comma. The part following the at-sign
MUST be a valid fully qualified internet domain name [RFC-1034]
controlled by the person or organization defining the name. It is up
to each domain how it manages its local namespace.
der Mouse
> No, this is a fine solution, and there is a way to deal with the clash.
> Here is a quote from draft-ietf-secsh-architecture-08.txt:
> o Names that do not contain an at-sign (@) are reserved to be
> assigned by [authority].
> o Anyone can define additional [...] names in the format
> name@domainname, [...]. The part following the at-sign MUST be a
> valid fully qualified internet domain name [RFC-1034] controlled
> by the person or organization defining the name.
Which is fine until a domain changes hands. (If this is due to
something like a corporate takeover, it's not a problem. But if the
original holder lets it lapse and some innocent bystander picks it up
later, it may be.)
Still, it's probably as good as you're going to get.
der Mouse
mo...@rodents.montreal.qc.ca
7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
Luke Mewburn
i've put an updated set of diffs for the kqueue work up at:
ftp://ftp.netbsd.org/pub/NetBSD/misc/lukem/kqueue-010428.diffs
along with the updated todo and test suite. the trivial mods to libc
to support the extra syscalls aren't there yet.
some things to still do:
- chase up all the XXXLUKEM comments, and resolve the issues
highlighted.
usually these are just concerns about whether locking is
correctly used or not, but i'm not familiar enough with that
part of the kernel to know what's the right thing to do.
- test EVFILT_WRITE (for sockets & pipes)
comments about other issues brought up previously:
- need a way to register new filters internally to the kernel
(aka `kfilter()' ?. this should support taking a name as the
new filter type (q.v.)
- need a way to look up a filter number from a string from
userland (e.g, "kqfilter_lookup(const char *)", which
returns 0 for not found, or the int otherwise.
- the current filter mechanism supports executing callbacks
when a filter is attached, detached, and triggered by the
kernel.
there isn't a mechanism to execute a callback when the
process actually receives the event (bill sommerfeld asked
for this), but i'm not sure what this would be used for.
we should approach jlemon with our thoughts on this
particular requirement.
i'll continue to do a bit more testing and soliciting feedback,
especially on the merge of the code from freebsd.
comments/hints/help?
luke.