kevent: core files.

kernel/kevent/kevent.c new file +5 -0

+       if (kevent_cache)
+               kmem_cache_free(kevent_cache, k);
+       else
+               kfree(k);
+}

kernel/kevent/kevent.c line 236

Quoted 11 lines · Evgeniy Polyakov

kernel/kevent/kevent.c new file +11 -0

+struct kevent *kevent_alloc(gfp_t mask)
+{
+       struct kevent *k;
+
+       if (kevent_cache)
+               k = kmem_cache_alloc(kevent_cache, mask);
+       else
+               k = kzalloc(sizeof(struct kevent), mask);
+
+       return k;
+}

What's this for? Why would kevent_cache be NULL? Note that you can use kmem_cache_zalloc() for fixed size allocations that need to be zeroed.

kernel/kevent/kevent.c line 240

Quoted 4 lines

kernel/kevent/kevent.c new file +4 -0

+
+void kevent_free(struct kevent *k)
+{
+       memset(k, 0xab, sizeof(struct kevent));

Why is slab poisoning not sufficient?

This patch includes core kevent files:
- userspace controlling
- kernelspace interfaces
- initialisation
- notification state machines

It might also inlclude parts from other subsystem (like network related syscalls so it is possible that it will not compile without other patches applied).

Signed-off-by Evgeniy Polyakov <[email protected]>

kernel/kevent/kevent.c new file +4 -0

+	if (kevent_cache)
+		k = kmem_cache_alloc(kevent_cache, mask);
+	else
+		k = kzalloc(sizeof(struct kevent), mask);

From: Evgeniy Polyakov <[email protected]>
Date: Sun, 9 Jul 2006 17:24:46 +0400

Quoted 10 lines

This patch includes core kevent files:
- userspace controlling
- kernelspace interfaces
- initialisation
- notification state machines

It might also inlclude parts from other subsystem (like network related syscalls so it is possible that it will not compile without other patches applied).

Quoted 1 line

Signed-off-by Evgeniy Polyakov <[email protected]>

I like this work a lot, as I've stated before. The data structures look like they will scale well and it takes care of all the limitations that networking in particular seems to have in this area.

I have to say that the user API is not the nicest in the world. Yet, at the same time, I cannot think of a better one :)

Please, remove some grot such as this:

Quoted 4 lines

kernel/kevent/kevent.c new file +4 -0

+	if (kevent_cache)
+		k = kmem_cache_alloc(kevent_cache, mask);
+	else
+		k = kzalloc(sizeof(struct kevent), mask);

...

kernel/kevent/kevent.c line 245

Quoted 4 lines

kernel/kevent/kevent.c new file +4 -0

+	if (kevent_cache)
+		kmem_cache_free(kevent_cache, k);
+	else
+		kfree(k);

Instead, make this:

kernel/kevent/kevent.c line 255

Quoted 4 lines

kernel/kevent/kevent.c new file +4 -0

+	kevent_cache = kmem_cache_create("kevent_cache", 
+			sizeof(struct kevent), 0, 0, NULL, NULL);
+	if (!kevent_cache)
+		err = -ENOMEM;

panic(). This is consistent with how other core subsystems handle SLAB cache creation failures.

I also think that if we accept this work, it should be first class citizen with no config options and no ifdefs scattered all over. Either this is how we do network AIO or it is not.

I've looked only briefly at Ulrich Drepper's AIO proposal in his OLS slides, although the DMA bits do not initially strike me as such a hot idea. I haven't wrapped my brain much around this new stuff, so I'm not going to touch on it much more just yet.

The practical advantage kevent has over any new proposal is that 1) implementation exists :) and 2) several types of test applications and performance measurements have been made against it which usually flushes out the worst design issues.

I like this work a lot, as I've stated before.

The data structures
look like they will scale well and it takes care of all the limitations that networking in particular seems to have in this area.

I have to say that the user API is not the nicest in the world. Yet, at the same time, I cannot think of a better one :)

Quoted 2 lines

I have to say that the user API is not the nicest in the world. Yet, at the same time, I cannot think of a better one :)

I want to first focus on the event collection side of the API because I think we can definitely do better there :). I hope we all agree that there is huge value in having one place where an application can wait for notification from many different sources. If we get the collection side right we can later worry about generating events down the pipe from subsystems in a way that works best for them.

I'll sort of ramble about my thoughts here.

The easy part is fixing up the somewhat obfuscated collection call. Instead of coming in through a multiplexer that magically treats a void
* as a struct kevent_user_control followed by N ukevents (as specified in the kevent_user_control!) we'd turn it into a more explicit collection syscall:

int kevent_getevents(int event_fd, struct ukevent *events,
int min_events, int max_events,
struct timeval *timeout);

This would look a lot less nutty in strace. It lets apps specify if there is some minimum number of events they'd like the opportunity to process rather than waiting for the timeout to expire before the max number arrives. (the latter is what kevent_user_wait() does today). We can have the usual argument about whether *timeout is updated on a partial wake-up :).

That'd be a fine syscall collection interface, but we should try hard to explore being able to collect events without hitting the kernel.

Say we have a ring of event structs. AIO has this today, but it sort of gets it wrong because each event element doesn't specify whether it is owned by the kernel or userspace. (It really gets it wrong because it doesn't flush_dcache_page() after updating the ring via kmap(), but never mind that! No one actually uses this mmap() AIO ring.) In AIO today there is also a control struct mapped along with the ring that has head and tail pointers. We don't want to bounce that cacheline around.
net/socket/af_packet.c gets this right with it's tp_status member of
tpacket_hdr.

So as the kernel generates events in the ring it only produces an event if the ownership field says that userspace has consumed it and in doing so it sets the ownership field to tell userspace that an event is waiting. userspace and the kernel now each follow their index around the ring as the ownership field lets them produce or consume the event at their index. Can someone tell me if the cache coherence costs of this are extreme? I'm hoping they're not.

So, great, glibc can now find pending events very quickly if they're waiting in the ring and can fall back to the collection syscall if it wants to wait and the ring is empty. If it consumes events via the syscall it increases its ring index by the number the syscall returned.

There's two things we should address: level events and the notion of only submitting as much as fits in the ring.

epoll and kevent both have the notion of an event type that always creates an event at the time of the collection syscall while the event source is on a ready list. Think of epoll calling ->poll(POLLOUT) for an empty socket buffer at every sys_epoll_wait() call. We can't have some source constantly spewing into the ring :/. We could fix this by the API requiring that level events can *only* be collected through the syscall interface. userspace could call into the collection syscall every N events collected through the ring, say. N would be tuned to amortize the syscall cost and still provide fairness or latency for the level sources. I'd be fine with that, especially when it's hidden off in glibc.

Today AIO only allows submission of as many events as there are space in the ring. It mostly does this so its completion can drop an event in the ring from any context. If we back away from this so that we can have long-lived source registration generate multiple edge events (and I think we want to!), we have to be kind of careful. A source could generate an event while the ring is full. The event could go in a list but if userspace is collecting events in userspace the kernel won't be told when there's space. We'd first have to check this ready list when later events are generated so that pending events on the list aren't overlooked. Userspace would also want to use the collection syscall as the ring empties. Neither seem hard.

So how does this sound? It wouldn't take me long to build this off of the current kevent patches. We could see how it looks..

- z

Quoted 4 lines

int kevent_getevents(int event_fd, struct ukevent *events,
int min_events, int max_events,
struct timeval *timeout);

I used only one syscall for all operations, above syscall is essentially what kevent_user_wait() does.

Hmm, it looks like I'm lost here...

I especially like idea about world happinness in a week or so :)

Quoted 5 lines

Quoted 4 lines

int kevent_getevents(int event_fd, struct ukevent *events,
int min_events, int max_events,
struct timeval *timeout);

Quoted 2 lines

I used only one syscall for all operations, above syscall is essentially what kevent_user_wait() does.

Essentially, yes, but the differences are important. It's important to have a clear syscall interface instead of nesting through multiplexers.
And we should get the batching/latency inputs right. (I'm for both
min/max elements and arguably timeouts, but I could understand not wanting to go *that* far.)

Quoted 1 line

Hmm, it looks like I'm lost here...

Yeah, it seems my description might not have sunk in :). We're giving userspace a way to collect events without performing a system call.

Quoted 1 line

I especially like idea about world happinness in a week or so :)

A few weeks! :)

- z

I completely agree that existing kevent interface is not the best, so I'm opened for any suggestions.
Should kevent creation/removing/modification be separated too?

Quoted 3 lines

Quoted 1 line

Hmm, it looks like I'm lost here...

Yeah, it seems my description might not have sunk in :). We're giving userspace a way to collect events without performing a system call.

And why do we want this?

How glibc is supposed to determine, that some events already fired and such requests will return immediately, or for example how timer events will be managed?

Quoted 4 lines

I completely agree that existing kevent interface is not the best, so I'm opened for any suggestions.
Should kevent creation/removing/modification be separated too?

Yeah, I think so.

Quoted 5 lines

Quoted 3 lines

Quoted 1 line

Hmm, it looks like I'm lost here...

Yeah, it seems my description might not have sunk in :). We're giving userspace a way to collect events without performing a system call.

And why do we want this?

So that event collection can be very efficient.

Quoted 3 lines

How glibc is supposed to determine, that some events already fired and such requests will return immediately, or for example how timer events will be managed?

...

That was what my previous mail was all about!

- z

So, I'm going to create kevent_create/destroy/control and kevent_get_events() Or any better names?

Some events are impossible to create in userspace (like timer notification, which requires timer start and check when timer completed).

and get ready), and I do not see how, for exmple, glibc can avoid them when user requested POLLIN or similar event for network dataflow?

According to syscall speed on Linux, last time I checked empty syscall took about 100ns on AMD Athlon 3500+.

Ulrich, would you be satisfied if we didn't
have the userspace mapped ring on the first pass and only had a collection syscall?

Quoted 3 lines · Zach Brown

Ulrich, would you be satisfied if we didn't
have the userspace mapped ring on the first pass and only had a collection syscall?

I'm not the one to make a call but why rush things? Let's do it right from the start. Later changes can only lead to problems with users of the earlier interface.

Speaking of API design choices, I saw your OLS paper and was wondering if you were familiar with the Solaris port APIs* and, if so, you could please comment on how your proposed event channels are different/better.

Signature · 1 line

Nicholas Miell <[email protected]>

Quoted 3 lines · Nicholas Miell

Speaking of API design choices, I saw your OLS paper and was wondering if you were familiar with the Solaris port APIs* and, if so, you could please comment on how your proposed event channels are different/better.

As far as it concerns kevents - userspace "ports" are just usual users of kevents, like timer notifications. Add another syscall to "complete" requested kevents and you get exactly Solaris ports.
It is fairly simple to implement on top of kevents, I just do not see immediate benefits from that.

[...] and was wondering
if you were familiar with the Solaris port APIs* and,

if so, you could
please comment on how your proposed event channels are different/better.

Quoted 3 lines · Zach Brown

Ulrich, would you be satisfied if we didn't
have the userspace mapped ring on the first pass and only had a collection syscall?

I'm not the one to make a call but why rush things? Let's do it right from the start. Later changes can only lead to problems with users of the earlier interface.

Signature · 1 line

??? Ulrich Drepper ??? Red Hat, Inc. ??? 444 Castro St ??? Mountain View, CA ???

Btw, why do we want mapped ring of ready events?
If user requestd some event, he definitely wants to get them back when they are ready, and not to check and then get them?
Could you please explain more on this issue?

Quoted 4 lines · Evgeniy Polyakov

Btw, why do we want mapped ring of ready events?
If user requestd some event, he definitely wants to get them back when they are ready, and not to check and then get them?
Could you please explain more on this issue?

If of course makes no sense to enter the kernel to actually get the event. This should be done by storing the event in the ring buffer. I.e., there are two ways to get an event:

- with a syscall. This can report as many events at once as the caller provides space for. And no event which is reported in the run buffer should be reported this way

- if there is space, report it in the ring buffer. Yes, the buffer can be optional, then all events are reported by the system call.

So the use case would be like this:

wait_and_get_event:

is buffer empty ?

    yes -> make syscall

    no -> get event from buffer

To avoid races, the syscall needs to take a parameter indicating the last event checked out from the buffer. If in the meantime the kernel put another event in the buffer the syscall immediately returns. Similar to what we do in the futex syscall.

Quoted 4 lines · Evgeniy Polyakov

Btw, why do we want mapped ring of ready events?
If user requestd some event, he definitely wants to get them back when they are ready, and not to check and then get them?
Could you please explain more on this issue?

If of course makes no sense to enter the kernel to actually get the event. This should be done by storing the event in the ring buffer. I.e., there are two ways to get an event:

- with a syscall. This can report as many events at once as the caller provides space for. And no event which is reported in the run buffer should be reported this way

- if there is space, report it in the ring buffer. Yes, the buffer can be optional, then all events are reported by the system call.

So the use case would be like this:

wait_and_get_event:

is buffer empty ?

    yes -> make syscall

    no -> get event from buffer

To avoid races, the syscall needs to take a parameter indicating the last event checked out from the buffer. If in the meantime the kernel put another event in the buffer the syscall immediately returns. Similar to what we do in the futex syscall.

The question is how to best represent the ring buffer. Zach and some others had some ready responses in Ottawa. The important thing is to avoid cache line ping pong when possible.

Is the ring buffer absolutely necessary? Probably not. But it has the potential to help quite a bit. Don't look at the problem to solve in the context of heavy I/O operations when another syscall here and there doesn't matter. With this single event mechanism for every possible event the kernel can generate programming can look quite different. E.g., every read() call can implicitly we changed into an async read call followed by a user-level reschedule. This rescheduling allows another thread of execution to run while the read request is processed.
I.e., it's basically a setjmp() followed by a goto into the inner loop
to get the next event. And now suddenly the event notification mechanism really should be as fast as possible. If we submit basically every request asynchronously and are not creating dedicated threads for specific tasks anymore we

a) have a lot more event notifications

b) the probability of an event being reported when we want the receive the next one if higher (i.e., the case where no syscall vs syscall makes a difference)

Yes, all this will require changes in the way programs a written but we shouldn't limit the way we can write programs unnecessarily. I think that given increasing discrepancies in relative speed/latency of the peripherals and the CPU this is one possible solution to keep the CPUs busy without resorting to a gazillion separate threads in each program.

Signature · 1 line

➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖

Quoted 3 lines

- if there is space, report it in the ring buffer. Yes, the buffer can be optional, then all events are reported by the system call.

That requires a copy, which can neglect syscall overhead. Do we really want it to be done?

Quoted 6 lines · Evgeniy Polyakov

Quoted 3 lines

- if there is space, report it in the ring buffer. Yes, the buffer can be optional, then all events are reported by the system call.

That requires a copy, which can neglect syscall overhead. Do we really want it to be done?

Please note that we're talking about events here, not actual data. So only the event is being copied, which is presumably rather small compared to the data.

In syscall time kevents copy 40bytes for each event + 12 bytes of header (number of events, timeout and command number). That's likely two cache lines if only one event is reported.

So I would say for up to 4 or 5 events, system call overhead alone touches as many cache lines as the events themselves.

The other to consider is that events don't come from the hardware. Events are written by the kernel. So if user-space is just reading the events that we've written, then there are no cache misses at all.

This is the case to keep in mind here. I thought Zach and the other involved in the discussions in Ottawa said this has been shown to be a problem and that a ring buffer implementation with something other than simple front and back pointers is preferable.

Ok, let's do it in the following way:
I present new version of kevent with new syscalls and fixed issues mentioned before, while people look at it we can end up with mapped buffer design. Is it ok?

Since kevents are never generated by kernel, but only marked as ready, length of the main queue performs as flow control, so we can create a mapped buffer which will have space equal to the main queue length multiplied by size of the copied to userspace structure plus 16 bits for the start index of the kernel writing side, i.e. it will store offset where the oldest event was placed.

Since queue length is a limited factor and thus no new events can be added when queue is full, that means that buffer is full too and userspace must read events. When syscall is called to add new kevent and provided there offset differs from what kernel stored, that means that all events from kernel to provided index have been read and new events can be added. Thus we can even allow read-only mapping. Kernel's index is incremented modulo queue length. If kevent was removed after it was marked as ready, it's copy stays in the mapped buffer, but special flag can be assigned to show that kevent is no longer valid.

So we'd have cases like this, assume we start with a full event queue:

thread A thread B

dequeue event
aha, new connection
accept()
register new kevent queue is now full again
add kevent on new
connection

At this point thread A doesn't have very many options when the kevent add fails. You cannot force this thread to read more events, since he may not be in a state where he is easily able to do so.

There has to be some thread that is responsible for reading events. Perhaps a reasonable thing for a blocked thread that cannot process events to do is to yield to one that can?

From: Evgeniy Polyakov <[email protected]>
Date: Mon, 31 Jul 2006 23:41:43 +0400

Quoted 7 lines

Since kevents are never generated by kernel, but only marked as ready, length of the main queue performs as flow control, so we can create a mapped buffer which will have space equal to the main queue length multiplied by size of the copied to userspace structure plus 16 bits for the start index of the kernel writing side, i.e. it will store offset where the oldest event was placed.

Quoted 9 lines

Since queue length is a limited factor and thus no new events can be added when queue is full, that means that buffer is full too and userspace must read events. When syscall is called to add new kevent and provided there offset differs from what kernel stored, that means that all events from kernel to provided index have been read and new events can be added. Thus we can even allow read-only mapping. Kernel's index is incremented modulo queue length. If kevent was removed after it was marked as ready, it's copy stays in the mapped buffer, but special flag can be assigned to show that kevent is no longer valid.

This sounds reasonable.

However we must be mindful that the thread of control trying to add a new event might not be in a position to drain the queue of pending events when the queue is full. Usually he will be trying to add an event in response to handling another event.

So we'd have cases like this, assume we start with a full event queue:

thread A thread B

dequeue event
aha, new connection
accept()
register new kevent queue is now full again
add kevent on new
connection

At this point thread A doesn't have very many options when the kevent add fails. You cannot force this thread to read more events, since he may not be in a state where he is easily able to do so.

Ok, let's do it in the following way:
I present new version of kevent with new syscalls and fixed issues mentioned before, while people look at it we can end up with mapped buffer design. Is it ok?

kernel/kevent/kevent_user.c line 94

Quoted 4 lines · Evgeniy Polyakov

kernel/kevent/kevent_user.c new file +4 -0

+	u->ready_num = 0;
+#ifdef CONFIG_KEVENT_USER_STAT
+	u->wait_num = u->im_num = u->total = 0;
+#endif

Generally, #ifdefs in the body of the kernel code are discouraged. Can you abstract these out as static inlines?

- James

Signature · 2 lines

James Morris
<[email protected]>

Quoted 9 lines · James Morris

kernel/kevent/kevent_user.c line 94

Quoted 4 lines · Evgeniy Polyakov

kernel/kevent/kevent_user.c new file +4 -0

+	u->ready_num = 0;
+#ifdef CONFIG_KEVENT_USER_STAT
+	u->wait_num = u->im_num = u->total = 0;
+#endif

Generally, #ifdefs in the body of the kernel code are discouraged. Can you abstract these out as static inlines?

Yes, it is possible.
I would ask is it needed at all?

It contains number of immediately fired
events (i.e. those which were ready when event was added and thus syscall returned immediately showing that it is ready), total number of events, which were inserted in the given queue and number of events which were marked as ready after they were inserted. Currently it is compilation option which ends up in printk with above info when kevent queue is removed.

Quoted 8 lines

Quoted 7 lines

kernel/kevent/kevent_user.c line 94

Quoted 4 lines

kernel/kevent/kevent_user.c new file +4 -0

+	u->ready_num = 0;
+#ifdef CONFIG_KEVENT_USER_STAT
+	u->wait_num = u->im_num = u->total = 0;
+#endif

Generally, #ifdefs in the body of the kernel code are discouraged. Can you abstract these out as static inlines?

Quoted 2 lines

Yes, it is possible.
I would ask is it needed at all?

Yes, please, it is standard kernel development practice.

Signature · 2 lines

James Morris
<[email protected]>

include/linux/kevent.h new file +6 -0

+/*
+ * Poll events.
+ */
+#define	KEVENT_POLL_POLLIN	0x0001
+#define	KEVENT_POLL_POLLPRI	0x0002
+#define	KEVENT_POLL_POLLOUT	0x0004

+#define KEVENT_MAX_REQUESTS PAGE_SIZE/sizeof(struct kevent)

+#define sock_async(__sk) 0

kernel/kevent/kevent_user.c new file +4 -0

+static struct kevent *__kqueue_dequeue_one_ready(struct list_head *q, 
+		unsigned int *qlen)
+{
+	struct kevent *k = NULL;

+/*
+ * In nonblocking mode it returns as many events as possible, but not more than @max_nr.
+ * In blocking mode it waits until timeout or if at least @min_nr events are ready,
+ * if timeout is zero, than it waits no more than 1 second or if at least one event
+ * is ready.

Even if we only have one syscall with a cmd multiplexer (which I'm not thrilled with), we should at least make these arguments explicit in the system call. It's weird to hide them in a struct. We could also think about making them u32 or u64 so that we don't need compat wrappers, but maybe that's overkill.

It'd be great if these struct members could get a prefix (ala: inode -> i_, socket -> sk_) so that it's less painful getting tags helpers to look up instances for us. Asking for 'lock' is hilarious.

Hmm. I think the current preference is not to have a lock per bucket.

Quoted 1 line

+#define KEVENT_MAX_REQUESTS PAGE_SIZE/sizeof(struct kevent)

This is unused?

From: Zach Brown <[email protected]>
Date: Tue, 01 Aug 2006 16:56:59 -0700

Quoted 5 lines

Even if we only have one syscall with a cmd multiplexer (which I'm not thrilled with), we should at least make these arguments explicit in the system call. It's weird to hide them in a struct. We could also think about making them u32 or u64 so that we don't need compat wrappers, but maybe that's overkill.

I think making the userspace data structure not require any compat handling is a must, thanks for pointing this out Zach.

Quoted 3 lines

It'd be great if these struct members could get a prefix (ala: inode -> i_, socket -> sk_) so that it's less painful getting tags helpers to look up instances for us. Asking for 'lock' is hilarious.

Agreed.

Quoted 1 line

Hmm. I think the current preference is not to have a lock per bucket.

Yes, it loses badly, that's why we undid this in the routing cache and just have a fixed sized array of locks which is hashed into.

For kevents, I think a single spinlock initially is fine and if we hit performance problems on SMP we can fix it. We should not implement complexity we have no proof of needing yet :)

Quoted 3 lines

Quoted 1 line

+#define KEVENT_MAX_REQUESTS PAGE_SIZE/sizeof(struct kevent)

This is unused?

It is probably groundwork for the mmap() ring buffer... :)

OK, here's some of my reactions to the core part.

include/linux/kevent.h line 45

Quoted 6 lines

include/linux/kevent.h new file +6 -0

+#define KEVENT_SOCKET 		0
+#define KEVENT_INODE		1
+#define KEVENT_TIMER		2
+#define KEVENT_POLL		3
+#define KEVENT_NAIO		4
+#define KEVENT_AIO		5

I guess we can't really avoid some form of centralized list of the constants in the API if we're going for a flat constant namespace. It'll be irritating to manage this list over time, just like it's irritating to manage syscall numbers now.

include/linux/kevent.h line 63

Quoted 6 lines

include/linux/kevent.h new file +6 -0

+/*
+ * Socket/network asynchronous IO events.
+ */
+#define	KEVENT_SOCKET_RECV	0x1
+#define	KEVENT_SOCKET_ACCEPT	0x2
+#define	KEVENT_SOCKET_SEND	0x4

I wonder if these shouldn't live in the subsystems instead of in kevent.h.

Quoted 10 lines

include/linux/kevent.h new file +10 -0

+/*
+ * Poll events.
+ */
+#define	KEVENT_POLL_POLLIN	0x0001
+#define	KEVENT_POLL_POLLPRI	0x0002
+#define	KEVENT_POLL_POLLOUT	0x0004
+#define	KEVENT_POLL_POLLERR	0x0008
+#define	KEVENT_POLL_POLLHUP	0x0010
+#define	KEVENT_POLL_POLLNVAL	0x0020
+

include/linux/kevent.h line 86

Quoted 6 lines

include/linux/kevent.h new file +6 -0

+#define	KEVENT_POLL_POLLRDNORM	0x0040
+#define	KEVENT_POLL_POLLRDBAND	0x0080
+#define	KEVENT_POLL_POLLWRNORM	0x0100
+#define	KEVENT_POLL_POLLWRBAND	0x0200
+#define	KEVENT_POLL_POLLMSG	0x0400
+#define	KEVENT_POLL_POLLREMOVE	0x1000

And couldn't we just use the existing poll bit definitions for this?

include/linux/kevent.h line 99

Quoted 4 lines

include/linux/kevent.h new file +4 -0

+struct kevent_id
+{
+	__u32		raw[2];
+};

Why not a simple u64? Users can play games with packing it into other types if they want.

include/linux/kevent.h line 112

Quoted 3 lines

include/linux/kevent.h new file +3 -0

+		__u32		user[2];		/* User's data. It is not used, just copied to/from user. */
+		void		*ptr;
+	};

Again just a u64 seems like it would be simpler. userspace library wrappers can help massage it, but the kernel is just treating it as an opaque data blob.

Quoted 11 lines

include/linux/kevent.h new file +11 -0

+};
+
+#define	KEVENT_CTL_ADD 		0
+#define	KEVENT_CTL_REMOVE	1
+#define	KEVENT_CTL_MODIFY	2
+#define	KEVENT_CTL_INIT		3
+
+struct kevent_user_control
+{
+	unsigned int		cmd;			/* Control command, e.g. KEVENT_ADD, KEVENT_REMOVE... */
+	unsigned int		num;			/* Number of ukevents this strucutre controls. */

Review

Quoted 2 lines

(quoted diff) +2 -0

+	unsigned int		timeout;		/* Timeout in milliseconds waiting for "num" events to become ready. */
+};

Even if we only have one syscall with a cmd multiplexer (which I'm not thrilled with), we should at least make these arguments explicit in the system call. It's weird to hide them in a struct. We could also think about making them u32 or u64 so that we don't need compat wrappers, but maybe that's overkill.

Also, can we please use a struct timespec for the timeout? Then the kernel will have the luxury of using whatever mechanism it wants to satisfy the user's precision desires. Just like sys_nanosleep() uses timespec and so can be implemented with hrtimers.

Review

Quoted 2 lines

(quoted diff) +2 -0

+struct kevent
+{

(trivial nit, "struct kevent {" is the preferred form.)

include/linux/kevent.h line 147

Quoted 2 lines

include/linux/kevent.h new file +2 -0

+	struct ukevent		event;
+	spinlock_t		lock;			/* This lock protects ukevent manipulations, e.g. ret_flags changes. */

It'd be great if these struct members could get a prefix (ala: inode -> i_, socket -> sk_) so that it's less painful getting tags helpers to look up instances for us. Asking for 'lock' is hilarious.

include/linux/kevent.h line 176

Quoted 9 lines

include/linux/kevent.h new file +9 -0

+struct kevent_list
+{
+	struct list_head	kevent_list;		/* List of all kevents. */
+	spinlock_t 		kevent_lock;		/* Protects all manipulations with queue of kevents. */
+};
+
+struct kevent_user
+{
+	struct kevent_list	kqueue[KEVENT_HASH_MASK+1];

Hmm. I think the current preference is not to have a lock per bucket. It doesn't scale nearly as well as it seems like it should as the cache footprint is higher and as cacheline contention hits as there are multiple buckets per cacheline. For now I'd simplify the hash into a single lock and an array of struct hlist_head. In the future it could be another user of some kind of relatively-generic hash implementation based on rcu that has been talked about for a while.

Quoted 1 line

+#define KEVENT_MAX_REQUESTS PAGE_SIZE/sizeof(struct kevent)

This is unused?

include/linux/kevent.h line 210

Quoted 5 lines

include/linux/kevent.h new file +5 -0

+#define list_for_each_entry_reverse_safe(pos, n, head, member)		\
+	for (pos = list_entry((head)->prev, typeof(*pos), member),	\
+		n = list_entry(pos->member.prev, typeof(*pos), member);	\
+	     prefetch(pos->member.prev), &pos->member != (head); 	\
+	     pos = n, n = list_entry(pos->member.prev, typeof(*pos), member))

If anyone was calling this they could use list_for_each_entry_safe_reverse() in list.h but nothing is calling it?
Either way, it should be removed :).

Quoted 1 line

+#define sock_async(__sk) 0

It's a minor complaint, but these kinds of ifdefs that drop arguments can cause unused argument warnings if they're the only user of the given argument. It'd be nicer to do something like ({ (void)_sk; 0; }) .

include/linux/kevent_storage.h line 6

Quoted 3 lines

include/linux/kevent_storage.h new file +3 -0

+struct kevent_storage
+{
+	void			*origin;		/* Originator's pointer, e.g. struct sock or struct file. Can be NULL. */

Do we really need this pointer? When the kevent_storage is embedded in the origin, like struct inode in your patch sets, you can use container_of() to get back to the inode. For sources that aren't built like that, like the timer_list, you could introduce a parent structure that has the timer_list and the _storage embedded in it.

kernel/kevent/Makefile line 7

Quoted 6 lines

kernel/kevent/Makefile new file +6 -0

+obj-$(CONFIG_KEVENT_SOCKET) += kevent_socket.o
+obj-$(CONFIG_KEVENT_INODE) += kevent_inode.o
+obj-$(CONFIG_KEVENT_TIMER) += kevent_timer.o
+obj-$(CONFIG_KEVENT_POLL) += kevent_poll.o
+obj-$(CONFIG_KEVENT_NAIO) += kevent_naio.o
+obj-$(CONFIG_KEVENT_AIO) += kevent_aio.o

I suspect that we won't want this configurable if it gets merged, but I could be wrong and don't feel strongly about it.

kernel/kevent/kevent.c line 95

Quoted 7 lines

kernel/kevent/kevent.c new file +7 -0

+	switch (k->event.type) {
+		case KEVENT_NAIO:
+			err = kevent_init_naio(k);
+			break;
+		case KEVENT_SOCKET:
+			err = kevent_init_socket(k);
+			break;

I wonder if it wouldn't be less noisy to have something like

struct kevent_callbacks {
	kevent_callback_t	callback, enqueue, dequeue;
} kev_callbacks[] = {

[ KEVENT_NAIO ] = &kevent_naio_callbacks,
};

	k->callbacks = kev_callbacks[k->event.type];

Then you'd also have one pointer per kevent instead of three.

Quoted 4 lines

kernel/kevent/kevent.c new file +4 -0

+void kevent_storage_dequeue(struct kevent_storage *st, struct kevent *k)
+{
+	unsigned long flags;
+

kernel/kevent/kevent.c line 145

Quoted 5 lines

kernel/kevent/kevent.c new file +5 -0

+	spin_lock_irqsave(&st->lock, flags);
+	if (k->storage_entry.next != LIST_POISON1) {
+		list_del(&k->storage_entry);
+		st->qlen--;
+	}

Is this relying on list_del() having set LIST_POISON1? If so, please use list_del_init() and list_empty() instead.

Review

Quoted 2 lines

(quoted diff) +2 -0

+static void __kevent_requeue(struct kevent *k, u32 event)
+{

A few things here. First, the event argument isn't used?

kernel/kevent/kevent.c line 154

Quoted 1 line

kernel/kevent/kevent.c new file +1 -0

+	err = k->callback(k);

This is being called while holding both the kevent_list->kevent_lock and the k->st->lock. So ->callback is being called with locks held and interrupts blocked which is going to greatly restrict what can be done there. If that's what we want to do we should document the heck out of it.

kernel/kevent/kevent.c line 174

Quoted 3 lines

kernel/kevent/kevent.c new file +2 -0

+	spin_lock_irqsave(&k->lock, flags);
 
+		spin_lock_irqsave(&k->user->ready_lock, flags);

It also now creates lock nesting three deep, which starts to feel uncomfortable. Have you run this under lockdep? It might be fine, but this kind of depth means those of us auditing have to stare very very closely at the locks that paths acquire. The fewer locks that are held at a time, the better.

kernel/kevent/kevent.c line 197

Quoted 2 lines

kernel/kevent/kevent.c new file +2 -0

+void kevent_storage_ready(struct kevent_storage *st, 
+		kevent_callback_t ready_callback, u32 event)

Hmm, the only caller that provides a callback is using it to call kevent_break() on each event. Could that not be done by the helper itself if the caller provides the right event? Is there some more complicated use of the callback on the horizon? Not a big deal, but there are those who prefer to avoid code paths that nest lots of callbacks in sequence.

Review

Quoted 1 line

(quoted diff) +1 -0

+	struct kevent *k, *n;

In general, it's nicer to user longer names please. You'll notice throughout the kernel that we use things like dentry, inode, page, sock, etc, instead of d, i, p, and s.

Quoted 4 lines

kernel/kevent/kevent.c new file +4 -0

+struct kevent *kevent_alloc(gfp_t mask)
+{
+	return kmem_cache_alloc(kevent_cache, mask);
+}

kernel/kevent/kevent.c line 234

Quoted 5 lines

kernel/kevent/kevent.c new file +5 -0

+
+void kevent_free(struct kevent *k)
+{
+	kmem_cache_free(kevent_cache, k);
+}

We probably don't need these wrappers, just call the kmem_cache_* functions directly.

Quoted 4 lines

kernel/kevent/kevent_user.c new file +4 -0

+static unsigned int kevent_user_poll(struct file *file, struct poll_table_struct *wait)
+{
+	struct kevent_user *u = file->private_data;
+	unsigned int mask;

kernel/kevent/kevent_user.c line 75

Quoted 6 lines

kernel/kevent/kevent_user.c new file +6 -0

+	
+	poll_wait(file, &u->wait, wait);
+	mask = 0;
+
+	if (u->ready_num)
+		mask |= POLLIN | POLLRDNORM;

Shouldn't this be testing ready_num while holding the ready_lock?

kernel/kevent/kevent_user.c line 98

Quoted 4 lines

kernel/kevent/kevent_user.c new file +4 -0

+	for (i=0; i<KEVENT_HASH_MASK+1; ++i) {
+		INIT_LIST_HEAD(&u->kqueue[i].kevent_list);
+		spin_lock_init(&u->kqueue[i].kevent_lock);
+	}

ARRAY_SIZE(u->kqueue) should probably be used instead of trying to keep (KEVENT_HASH_MASK + 1) in sync with the kqueue definition.

kernel/kevent/kevent_user.c line 134

Quoted 7 lines

kernel/kevent/kevent_user.c new file +7 -0

+static inline void kevent_user_put(struct kevent_user *u)
+{
+	if (atomic_dec_and_test(&u->refcnt)) {
+#ifdef CONFIG_KEVENT_USER_STAT
+		printk("%s: u=%p, wait=%lu, immediately=%lu, total=%lu.\n", 
+				__func__, u, u->wait_num, u->im_num, u->total);
+#endif

printk() seems like a poor choice if this is meant to be a more formal functionality. If it's just a debugging aid then pr_debug() and DEBUG might be nicer.

kernel/kevent/kevent_user.c line 161

Quoted 6 lines

kernel/kevent/kevent_user.c new file +6 -0

+/*
+ * Remove kevent from user's list of all events, 
+ * dequeue it from storage and decrease user's reference counter,
+ * since this kevent does not exist anymore. That is why it is freed here.
+ */
+static void kevent_finish_user(struct kevent *k, int lock, int deq)

How about providing locked and unlocked prototypes instead of an argument that says whether to lock or not? You know, the usual:

void __thingy() {
	doit();
}

void thingy() {
	lock();
	__thingy();
	unlock();
}

Review

Quoted 2 lines

(quoted diff) +2 -0

+		list_del(&k->kevent_entry);
+		u->kevent_num--;

I wonder if these shouldn't get micro helpers that then have BUG_ON()s to test bad conditions. like BUG_ON(list_empty() && kevent_num), that sort of thing.

Quoted 10 lines

kernel/kevent/kevent_user.c new file +10 -0

+static struct kevent *__kqueue_dequeue_one_ready(struct list_head *q, 
+		unsigned int *qlen)
+{
+	struct kevent *k = NULL;
+	unsigned int len = *qlen;
+	
+	if (len && !list_empty(q)) {
+		k = list_entry(q->next, struct kevent, ready_entry);
+		list_del(&k->ready_entry);
+		*qlen = len - 1;

kernel/kevent/kevent_user.c line 209

Quoted 4 lines

kernel/kevent/kevent_user.c new file +4 -0

+	}
+	
+	return k;
+}

Hmm, this is only called in one place? I'd either make the list_head and lock into one struct (like struct sk_buff_head) or hoist the code into the caller.

kernel/kevent/kevent_user.c line 235

Quoted 7 lines

kernel/kevent/kevent_user.c new file +7 -0

+	list_for_each_entry(k, &l->kevent_list, kevent_entry) {
+		spin_lock(&k->lock);
+		if (k->event.user[0] == uk->user[0] && k->event.user[1] == uk->user[1] &&
+				k->event.id.raw[0] == uk->id.raw[0] && 
+				k->event.id.raw[1] == uk->id.raw[1]) {
+			found = 1;
+			spin_unlock(&k->lock);

Ahhh, it's fs/aio.c:lookup_kiocb() all over again :) :). I guess we'll get this in a hash, or something, before merging.

Quoted 8 lines

kernel/kevent/kevent_user.c new file +8 -0

+	mutex_lock(&u->ctl_mutex);
+
+	for (i=0; i<ctl->num; ++i) {
+		if (copy_from_user(&uk, arg, sizeof(struct ukevent))) {
+			err = -EINVAL;
+			break;
+		}
+

kernel/kevent/kevent_user.c line 324

Quoted 1 line

kernel/kevent/kevent_user.c new file +1 -0

+		if (kevent_modify(&uk, u))

So there are a bunch of these. The internal list and kevents and such have their own locks. What are the mutexes serializing? Why can't we rely on the finger-grained object locking to make sure that concurrent operations behave resonably? One can imagine wanting to modify two kevents in a context that have nothing to do with each other and not wanting to serialize them at the context.

Quoted 8 lines

kernel/kevent/kevent_user.c new file +8 -0

+int kevent_user_add_ukevent(struct ukevent *uk, struct kevent_user *u)
+{
+	struct kevent *k;
+	int err;
+
+	k = kevent_alloc(GFP_KERNEL);
+	if (!k) {
+		err = -ENOMEM;

kernel/kevent/kevent_user.c line 384

Quoted 4 lines

kernel/kevent/kevent_user.c new file +4 -0

+		goto err_out_exit;
+	}
+
+	memcpy(&k->event, uk, sizeof(struct ukevent));

This path is copying the ukevents twice. First from userspace back up in kevent_user_ctl_add() and then here into the kevent. We should rework things a bit so that we only copy it once.

kernel/kevent/kevent_user.c line 396

Quoted 3 lines

kernel/kevent/kevent_user.c new file +3 -0

+#ifdef CONFIG_KEVENT_USER_STAT
+	u->total++;
+#endif

FWIW, this could hide behind some kevent_user_stat_inc(u) that could be ifdefed away in the header.

Quoted 6 lines

kernel/kevent/kevent_user.c new file +6 -0

+	{
+		unsigned long flags;
+		unsigned int hash = kevent_user_hash(&k->event);
+		struct kevent_list *l = &u->kqueue[hash];
+		
+		spin_lock_irqsave(&l->kevent_lock, flags);

kernel/kevent/kevent_user.c line 407

Quoted 5 lines

kernel/kevent/kevent_user.c new file +5 -0

+		list_add_tail(&k->kevent_entry, &l->kevent_list);
+		u->kevent_num++;
+		kevent_user_get(u);
+		spin_unlock_irqrestore(&l->kevent_lock, flags);
+	}

Hmm, please don't indent things like this. Add a little helper function or hoist the locals up into the main function and lose the braces.

kernel/kevent/kevent_user.c line 444

Quoted 6 lines

kernel/kevent/kevent_user.c new file +5 -0

+static int kevent_user_ctl_add(struct kevent_user *u, 
+		struct kevent_user_control *ctl, void __user *arg)
+{
 
+	orig = arg;
+	ctl_addr = arg - sizeof(struct kevent_user_control);

Ugh. This is more awkwardness that comes from packing the system call arguments in neighbouring structs behind a void *. We should really have explicit typed args.

Quoted 6 lines

kernel/kevent/kevent_user.c new file +6 -0

+	for (i=0; i<ctl->num; ++i) {
+		if (copy_from_user(&uk, arg, sizeof(struct ukevent))) {
+			cerr = -EINVAL;
+			break;
+		}
+		arg += sizeof(struct ukevent);

kernel/kevent/kevent_user.c line 457

Quoted 2 lines

kernel/kevent/kevent_user.c new file +2 -0

+
+		err = kevent_user_add_ukevent(&uk, u);

There are some users that will want to add thousands of events at a time. (Like, say, a certain database writing back lots of cached dirtied database blocks.) I wonder if we should arrange this so that we can get some batching done and reduce the amount of lock traffic per event added.

Quoted 5 lines

+/*
+ * In nonblocking mode it returns as many events as possible, but not more than @max_nr.
+ * In blocking mode it waits until timeout or if at least @min_nr events are ready,
+ * if timeout is zero, than it waits no more than 1 second or if at least one event
+ * is ready.

That's odd. Why not have a timeout of 0 mean a timeout of 0? Where did 1 second come from? :) It seems pretty crazy to require programmers to check that their timer math didn't just end up at 0 and magically tell the kernel to wait a second.

kernel/kevent/kevent_user.c line 516

Quoted 7 lines

kernel/kevent/kevent_user.c new file +7 -0

+	mutex_lock(&u->ctl_mutex);
+	while (num < max_nr && ((k = kqueue_dequeue_ready(u)) != NULL)) {
+		if (copy_to_user(buf + num*sizeof(struct ukevent), 
+					&k->event, sizeof(struct ukevent))) {
+			cerr = -EINVAL;
+			break;
+		}

Again, this a great opportunity to copy more than one at a time with some refactoring.

Quoted 7 lines

kernel/kevent/kevent_user.c new file +7 -0

+asmlinkage long sys_kevent_ctl(int fd, void __user *arg)
+{
+	int err = -EINVAL, fput_needed;
+	struct kevent_user_control ctl;
+	struct file *file;
+
+	if (copy_from_user(&ctl, arg, sizeof(struct kevent_user_control)))

kernel/kevent/kevent_user.c line 636

Quoted 4 lines

kernel/kevent/kevent_user.c new file +4 -0

+		return -EINVAL;
+
+	if (ctl.cmd == KEVENT_CTL_INIT)
+		return kevent_ctl_init();

Hmm. So we can get one of these fds both by opening the device file or by calling _CTL_INIT (which then magically ignores the fd argument?). That seems confusing.

Anyway, that's enough for now. I hope this helps.

- z

u64 is not aligned, so I prefer to use u32 as much as possible.

From: Evgeniy Polyakov <[email protected]>
Date: Wed, 2 Aug 2006 10:39:18 +0400

Quoted 1 line

u64 is not aligned, so I prefer to use u32 as much as possible.

We have aligned_u64 exactly for this purpose, netfilter makes use of it to avoid the x86_64 vs. x86 u64 alignment discrepency.