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 <redacted>
@@ -0,0 +1,263 @@+/*+*kevent.h+*+*2006Copyright(c)EvgeniyPolyakov<johnpol@2ka.mipt.ru>+*Allrightsreserved.+*+*Thisprogramisfreesoftware;youcanredistributeitand/ormodify+*itunderthetermsoftheGNUGeneralPublicLicenseaspublishedby+*theFreeSoftwareFoundation;eitherversion2oftheLicense,or+*(atyouroption)anylaterversion.+*+*Thisprogramisdistributedinthehopethatitwillbeuseful,+*butWITHOUTANYWARRANTY;withouteventheimpliedwarrantyof+*MERCHANTABILITYorFITNESSFORAPARTICULARPURPOSE.Seethe+*GNUGeneralPublicLicenseformoredetails.+*+*YoushouldhavereceivedacopyoftheGNUGeneralPublicLicense+*alongwiththisprogram;ifnot,writetotheFreeSoftware+*Foundation,Inc.,59TemplePlace,Suite330,Boston,MA02111-1307USA+*/++#ifndef __KEVENT_H+#define __KEVENT_H++/*+*Keventrequestflags.+*/++#define KEVENT_REQ_ONESHOT 0x1 /* Process this event only once and then dequeue. */++/*+*Keventreturnflags.+*/+#define KEVENT_RET_BROKEN 0x1 /* Kevent is broken. */+#define KEVENT_RET_DONE 0x2 /* Kevent processing was finished successfully. */++/*+*Keventtypeset.+*/+#define KEVENT_SOCKET 0+#define KEVENT_INODE 1+#define KEVENT_TIMER 2+#define KEVENT_POLL 3+#define KEVENT_NAIO 4+#define KEVENT_AIO 5+#define KEVENT_MAX 6++/*+*Per-typeeventsets.+*Numberofper-eventsetsshouldbeexactlyasnumberofkeventtypes.+*/++/*+*Timerevents.+*/+#define KEVENT_TIMER_FIRED 0x1++/*+*Socket/networkasynchronousIOevents.+*/+#define KEVENT_SOCKET_RECV 0x1+#define KEVENT_SOCKET_ACCEPT 0x2+#define KEVENT_SOCKET_SEND 0x4++/*+*Inodeevents.+*/+#define KEVENT_INODE_CREATE 0x1+#define KEVENT_INODE_REMOVE 0x2++/*+*Pollevents.+*/+#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++#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++/*+*AsynchronousIOevents.+*/+#define KEVENT_AIO_BIO 0x1++#define KEVENT_MASK_ALL 0xffffffff /* Mask of all possible event values. */+#define KEVENT_MASK_EMPTY 0x0 /* Empty mask of ready events. */++structkevent_id+{+__u32raw[2];+};++structukevent+{+structkevent_idid;/* Id of this request, e.g. socket number, file descriptor and so on... */+__u32type;/* Event type, e.g. KEVENT_SOCK, KEVENT_INODE, KEVENT_TIMER and so on... */+__u32event;/* Event itself, e.g. SOCK_ACCEPT, INODE_CREATED, TIMER_FIRED... */+__u32req_flags;/* Per-event request flags */+__u32ret_flags;/* Per-event return flags */+__u32ret_data[2];/* Event return data. Event originator fills it with anything it likes. */+union{+__u32user[2];/* User's data. It is not used, just copied to/from user. */+void*ptr;+};+};++#define KEVENT_CTL_ADD 0+#define KEVENT_CTL_REMOVE 1+#define KEVENT_CTL_MODIFY 2+#define KEVENT_CTL_WAIT 3+#define KEVENT_CTL_INIT 4++structkevent_user_control+{+unsignedintcmd;/* Control command, e.g. KEVENT_ADD, KEVENT_REMOVE... */+unsignedintnum;/* Number of ukevents this strucutre controls. */+unsignedinttimeout;/* Timeout in milliseconds waiting for "num" events to become ready. */+};++#define KEVENT_USER_SYMBOL 'K'+#define KEVENT_USER_CTL _IOWR(KEVENT_USER_SYMBOL, 0, struct kevent_user_control)+#define KEVENT_USER_WAIT _IOWR(KEVENT_USER_SYMBOL, 1, struct kevent_user_control)++#ifdef __KERNEL__++#include<linux/types.h>+#include<linux/list.h>+#include<linux/spinlock.h>+#include<linux/kevent_storage.h>+#include<asm/semaphore.h>++structinode;+structdentry;+structsock;++structkevent;+structkevent_storage;+typedefint(*kevent_callback_t)(structkevent*);++structkevent+{+structukeventevent;+spinlock_tlock;/* This lock protects ukevent manipulations, e.g. ret_flags changes. */++structlist_headkevent_entry;/* Entry of user's queue. */+structlist_headstorage_entry;/* Entry of origin's queue. */+structlist_headready_entry;/* Entry of user's ready. */++structkevent_user*user;/* User who requested this kevent. */+structkevent_storage*st;/* Kevent container. */++kevent_callback_tcallback;/* Is called each time new event has been caught. */+kevent_callback_tenqueue;/* Is called each time new event is queued. */+kevent_callback_tdequeue;/* Is called each time event is dequeued. */++void*priv;/* Private data for different storages. +*poll()/selectstoragehasalistofwait_queue_tcontainers+*foreach->poll(){poll_wait()'}here.+*/+};++#define KEVENT_HASH_MASK 0xff++structkevent_list+{+structlist_headkevent_list;/* List of all kevents. */+spinlock_tkevent_lock;/* Protects all manipulations with queue of kevents. */+};++structkevent_user+{+structkevent_listkqueue[KEVENT_HASH_MASK+1];+unsignedintkevent_num;/* Number of queued kevents. */++structlist_headready_list;/* List of ready kevents. */+unsignedintready_num;/* Number of ready kevents. */+spinlock_tready_lock;/* Protects all manipulations with ready queue. */++unsignedintmax_ready_num;/* Requested number of kevents. */++structsemaphorectl_mutex;/* Protects against simultaneous kevent_user control manipulations. */+structsemaphorewait_mutex;/* Protects against simultaneous kevent_user waits. */+wait_queue_head_twait;/* Wait until some events are ready. */++atomic_trefcnt;/* Reference counter, increased for each new kevent. */+#ifdef CONFIG_KEVENT_USER_STAT+unsignedlongim_num;+unsignedlongwait_num;+unsignedlongtotal;+#endif+};++#define KEVENT_MAX_REQUESTS PAGE_SIZE/sizeof(struct kevent)++structkevent*kevent_alloc(gfp_tmask);+voidkevent_free(structkevent*k);+intkevent_enqueue(structkevent*k);+intkevent_dequeue(structkevent*k);+intkevent_init(structkevent*k);+voidkevent_requeue(structkevent*k);++#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))++intkevent_break(structkevent*k);+intkevent_init(structkevent*k);++intkevent_init_socket(structkevent*k);+intkevent_init_inode(structkevent*k);+intkevent_init_timer(structkevent*k);+intkevent_init_poll(structkevent*k);+intkevent_init_naio(structkevent*k);+intkevent_init_aio(structkevent*k);++voidkevent_storage_ready(structkevent_storage*st,+kevent_callback_tready_callback,u32event);+intkevent_storage_init(void*origin,structkevent_storage*st);+voidkevent_storage_fini(structkevent_storage*st);+intkevent_storage_enqueue(structkevent_storage*st,structkevent*k);+voidkevent_storage_dequeue(structkevent_storage*st,structkevent*k);++intkevent_user_add_ukevent(structukevent*uk,structkevent_user*u);++#ifdef CONFIG_KEVENT_INODE+voidkevent_inode_notify(structinode*inode,u32event);+voidkevent_inode_notify_parent(structdentry*dentry,u32event);+voidkevent_inode_remove(structinode*inode);+#else+staticinlinevoidkevent_inode_notify(structinode*inode,u32event)+{+}+staticinlinevoidkevent_inode_notify_parent(structdentry*dentry,u32event)+{+}+staticinlinevoidkevent_inode_remove(structinode*inode)+{+}+#endif /* CONFIG_KEVENT_INODE */+#ifdef CONFIG_KEVENT_SOCKET++voidkevent_socket_notify(structsock*sock,u32event);+intkevent_socket_dequeue(structkevent*k);+intkevent_socket_enqueue(structkevent*k);+#define sock_async(__sk) sock_flag(__sk, SOCK_ASYNC)+#else+staticinlinevoidkevent_socket_notify(structsock*sock,u32event)+{+}+#define sock_async(__sk) 0+#endif+#endif /* __KERNEL__ */+#endif /* __KEVENT_H */
@@ -0,0 +1,12 @@+#ifndef __KEVENT_STORAGE_H+#define __KEVENT_STORAGE_H++structkevent_storage+{+void*origin;/* Originator's pointer, e.g. struct sock or struct file. Can be NULL. */+structlist_headlist;/* List of queued kevents. */+unsignedintqlen;/* Number of queued kevents. */+spinlock_tlock;/* Protects users queue. */+};++#endif /* __KEVENT_STORAGE_H */
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.
On 7/9/06, Evgeniy Polyakov [off-list ref] wrote:
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 <redacted>
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:
+ if (kevent_cache)
+ k = kmem_cache_alloc(kevent_cache, mask);
+ else
+ k = kzalloc(sizeof(struct kevent), mask);
...
+ if (kevent_cache)
+ kmem_cache_free(kevent_cache, k);
+ else
+ kfree(k);
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.
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 <redacted>
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 :)
Hi David. I see you have a day of backlog mails processing :)
Please, remove some grot such as this:
quoted
+ if (kevent_cache)
+ k = kmem_cache_alloc(kevent_cache, mask);
+ else
+ k = kzalloc(sizeof(struct kevent), mask);
...
quoted
+ if (kevent_cache)
+ kmem_cache_free(kevent_cache, k);
+ else
+ kfree(k);
panic(). This is consistent with how other core subsystems handle
SLAB cache creation failures.
Ok.
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.
Yes, his idea of dma alloc is extremely good.
I manage it with quite big overhead in kevent unfortunately.
All other topics are fully covered with kevent (except nice userspace
API of course :) )
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 will clean code up and resubmit today.
Thank you.
--
Evgeniy Polyakov
From: Zach Brown <hidden> Date: 2006-07-27 19:18:51
I like this work a lot, as I've stated before.
Yeah, me too. I think we're very close to having a workable system
here. A few weeks of some restructuring and we all might be very happy.
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 :)
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
On Thu, Jul 27, 2006 at 12:18:42PM -0700, Zach Brown (zach.brown@oracle.com) wrote:
quoted
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);
I used only one syscall for all operations, above syscall is
essentially what kevent_user_wait() does.
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 :).
Sure it can be moved as a different syscall.
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.
When kevent is ready, it is supposed to be "moved" into the userspace,
if it is ready or not is detected through it's list entry for given
list(or just dequeue it).
So there is no need to have a ring of all kevents and select ready from
them (actually kevent has a list of all kevents, and it is possible to
scan it and select for ready ones, but special ready list was created to
speed that process up).
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.
It can get pending event from ready list - no need to scan the whole
ring. If one wants to wait on special kevent, it is possible to get it
from "main" list and check it's state.
But do we really need that functionality? If user created several
kevents, it was not done just for the sake of kevent creation - user
wants them back, so why he will wait only on special one?
I had an idea about priorities for the kevents, and it can be
implemented as several ready lists though.
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.
Hmm, it looks like I'm lost here...
Each kevent can be modified and even reused at any time, no matter if it
is in the ready list or not.
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.
There is no problem with lists lengths - when kevent is added, and
queue length is enough, it is autmatically means that all lists will
accept that kevent, since all kevents live simultaneously in several
rings. There are no event generators - only existing, i.e. requested
kevents are confirmed to be ready or not, so system behaves axactly how
user asked it to work with provided requests.
For example inotify will allocate and add to the ring new events each
time they fire, but kevent works in a different way (it's inode
notification) - it checks if there are events for inode creation/removal
and that events are marked as ready - thus no allocations, no problems
with queues -system scales well and does not eat resources, but it has a
problem, that not very much info can be delivered to user when event is
ready (for example no filenames, only inode number can be transferred).
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..
I especially like idea about world happinness in a week or so :)
From: Benjamin LaHaise <bcrl@kvack.org> Date: 2006-07-27 20:58:57
On Thu, Jul 27, 2006 at 12:18:42PM -0700, Zach Brown wrote:
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);
You've just reinvented io_getevents(). What exactly are we getting from
reinventing this (aside from breaking existing apps and creating more of
an API mess)?
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.
That could be rev'd in the mmap() ring buffer, as there are compat and
incompat bits for changing the structure layout. As for bouncing the
cacheline of head/tail around, I don't think it matters on real machines,
as the multithreaded/SMP case will hit that cacheline bouncing if the
user is sharing the event ring between multiple threads on multiple CPUs.
The only way around that is to use multiple event rings, say one per node,
at which point you have to do load balancing of io requests explicitely
between queues (which might be worth it).
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.
This is exactly why I think level triggered events are nasty. It's
impossible to do cleanly without requiring a syscall.
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.
As soon as you allow queueing events up in kernel space, it becomes
necessary to do another syscall after pulling events out of the queue,
which is a waste of CPU cycles when you're under heavy load (exactly the
point at which you want the system to be its most efficient). Given that
growing the ring buffer is easy enough to do, I'm not sure that the hit
is worth it. At some point there has to be some form of flow control
involved, and it is much better if it is explicitely obvious where this
happens (as opposed to signal queues and our wonderful OOM handling).
-ben
--
"Time is of no importance, Mr. President, only life is important."
Don't Email: [off-list ref].
From: Zach Brown <hidden> Date: 2006-07-27 21:32:12
quoted
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.
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.)
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.
I especially like idea about world happinness in a week or so :)
From: Zach Brown <hidden> Date: 2006-07-27 21:44:55
quoted
int kevent_getevents(int event_fd, struct ukevent *events,
int min_events, int max_events,
struct timeval *timeout);
You've just reinvented io_getevents().
Well, that's certainly one inflammatory way to put it. I would describe
it as suggesting that the kevents collection interface not lose the
nicer properties of io_getevents().
What exactly are we getting from
reinventing this (aside from breaking existing apps and creating more of
an API mess)?
A generic event collection interface that isn't so strongly bound to the
existing semantics of io_setup() and io_submit(). It can be a file
descriptor instead of a mysterious cookie/pointer to the mapped region,
to start.
incompat bits for changing the structure layout. As for bouncing the
cacheline of head/tail around, I don't think it matters on real machines,
as the multithreaded/SMP case will hit that cacheline bouncing if the
user is sharing the event ring between multiple threads on multiple CPUs.
The only way around that is to use multiple event rings, say one per node,
at which point you have to do load balancing of io requests explicitely
between queues (which might be worth it).
Sure, so maybe we experiment with these things in the context of the
kevent patches and maybe merge them back into the AIO paths if in the
end that's the right thing to do. I see no problem with separating
development from the existing code.
quoted
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.
This is exactly why I think level triggered events are nasty. It's
impossible to do cleanly without requiring a syscall.
I'm not convinced that it isn't possible to get a sufficiently clean
interface that involves the mix.
As soon as you allow queueing events up in kernel space, it becomes
necessary to do another syscall after pulling events out of the queue,
which is a waste of CPU cycles when you're under heavy load (exactly the
point at which you want the system to be its most efficient).
If we've just consumed a full ring worth of events, and done real work
with them, I'm not convinced that an empty syscall is going to be that
painful. If we're really under load it might well return some newly
arrived events. It becomes a mix of ring completions and syscall
completions.
- z
From: Benjamin LaHaise <bcrl@kvack.org> Date: 2006-07-27 22:02:53
On Thu, Jul 27, 2006 at 02:44:50PM -0700, Zach Brown wrote:
quoted
quoted
int kevent_getevents(int event_fd, struct ukevent *events,
int min_events, int max_events,
struct timeval *timeout);
You've just reinvented io_getevents().
Well, that's certainly one inflammatory way to put it. I would describe
it as suggesting that the kevents collection interface not lose the
nicer properties of io_getevents().
Perhaps, but there seems to be a lot of talk about introducing new APIs
where it isn't entirely clear that it is needed. Sorry if that sounded
rather acerbic.
quoted
What exactly are we getting from
reinventing this (aside from breaking existing apps and creating more of
an API mess)?
A generic event collection interface that isn't so strongly bound to the
existing semantics of io_setup() and io_submit(). It can be a file
descriptor instead of a mysterious cookie/pointer to the mapped region,
to start.
Things were like that at one point in time, but file descriptors turn out
to introduce a huge gaping security hole with SUID programs. The problem
is that any event context is closely tied to the address space of the
thread issuing the syscalls, and file descriptors do not have this close
binding.
Sure, so maybe we experiment with these things in the context of the
kevent patches and maybe merge them back into the AIO paths if in the
end that's the right thing to do. I see no problem with separating
development from the existing code.
Excellent!
quoted
quoted
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.
This is exactly why I think level triggered events are nasty. It's
impossible to do cleanly without requiring a syscall.
I'm not convinced that it isn't possible to get a sufficiently clean
interface that involves the mix.
My arguement is that this approach introduces a slow path into the heavily
loaded server case. If you can show me how to avoid that, I'd be happy to
see such an implementation. =-)
quoted
As soon as you allow queueing events up in kernel space, it becomes
necessary to do another syscall after pulling events out of the queue,
which is a waste of CPU cycles when you're under heavy load (exactly the
point at which you want the system to be its most efficient).
If we've just consumed a full ring worth of events, and done real work
with them, I'm not convinced that an empty syscall is going to be that
painful. If we're really under load it might well return some newly
arrived events. It becomes a mix of ring completions and syscall
completions.
Except that you're not usually pulling a full ring worth of events at a
time, more often just one. One of the driving forces behind AIO use is
in realtime apps where you don't want to eat occasional spikes in the
latency of request processing, one just wants to eat the highest priority
event then work on the next. By keeping each step small and managable,
the properties of the system are much easier to predict. Yes, batching
can be helpful performance-wise, but it is somewhat opposite to the design
criteria that need to be considered. The right way to cope with that may
be to have two different modes of operation that trade off one way or the
other on the batching question.
-ben
--
"Time is of no importance, Mr. President, only life is important."
Don't Email: [off-list ref].
On Thu, Jul 27, 2006 at 02:32:05PM -0700, Zach Brown (zach.brown@oracle.com) wrote:
quoted
quoted
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.
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.)
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
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
I especially like idea about world happinness in a week or so :)
A few weeks! :)
No matter after couple of millions of years of human evolution :)
On Thu, Jul 27, 2006 at 06:02:38PM -0400, Benjamin LaHaise (bcrl@kvack.org) wrote:
On Thu, Jul 27, 2006 at 02:44:50PM -0700, Zach Brown wrote:
quoted
quoted
quoted
int kevent_getevents(int event_fd, struct ukevent *events,
int min_events, int max_events,
struct timeval *timeout);
You've just reinvented io_getevents().
Well, that's certainly one inflammatory way to put it. I would describe
it as suggesting that the kevents collection interface not lose the
nicer properties of io_getevents().
Perhaps, but there seems to be a lot of talk about introducing new APIs
where it isn't entirely clear that it is needed. Sorry if that sounded
rather acerbic.
Except that kevent has completely different structures and it is
possible to have a lot of more types of event than AIO has and there is
no need to specially have bytes, offsets and so on.
Magic pointer returned from aio syscall is no pollable too.
quoted
quoted
What exactly are we getting from
reinventing this (aside from breaking existing apps and creating more of
an API mess)?
A generic event collection interface that isn't so strongly bound to the
existing semantics of io_setup() and io_submit(). It can be a file
descriptor instead of a mysterious cookie/pointer to the mapped region,
to start.
Things were like that at one point in time, but file descriptors turn out
to introduce a huge gaping security hole with SUID programs. The problem
is that any event context is closely tied to the address space of the
thread issuing the syscalls, and file descriptors do not have this close
binding.
It is true for all shared resources no matter if it is file descriptor or
mapped area.
quoted
Sure, so maybe we experiment with these things in the context of the
kevent patches and maybe merge them back into the AIO paths if in the
end that's the right thing to do. I see no problem with separating
development from the existing code.
Excellent!
quoted
quoted
quoted
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.
This is exactly why I think level triggered events are nasty. It's
impossible to do cleanly without requiring a syscall.
I'm not convinced that it isn't possible to get a sufficiently clean
interface that involves the mix.
My arguement is that this approach introduces a slow path into the heavily
loaded server case. If you can show me how to avoid that, I'd be happy to
see such an implementation. =-)
If I understand you correct you are talking about level triggering
events, which arrive continuously? Such events are handled by only one
kevent, if iti is ready, that means that at least one such event was
fired. One can add a number of fired events as a hints inside kevent.
quoted
quoted
As soon as you allow queueing events up in kernel space, it becomes
necessary to do another syscall after pulling events out of the queue,
which is a waste of CPU cycles when you're under heavy load (exactly the
point at which you want the system to be its most efficient).
If we've just consumed a full ring worth of events, and done real work
with them, I'm not convinced that an empty syscall is going to be that
painful. If we're really under load it might well return some newly
arrived events. It becomes a mix of ring completions and syscall
completions.
Except that you're not usually pulling a full ring worth of events at a
time, more often just one. One of the driving forces behind AIO use is
in realtime apps where you don't want to eat occasional spikes in the
latency of request processing, one just wants to eat the highest priority
event then work on the next. By keeping each step small and managable,
the properties of the system are much easier to predict. Yes, batching
can be helpful performance-wise, but it is somewhat opposite to the design
criteria that need to be considered. The right way to cope with that may
be to have two different modes of operation that trade off one way or the
other on the batching question.
It is user who should decide either he wants one, all or at least one
eventt. kevent supports all types of requests, it's behaviour depends on
parameters.
From: Zach Brown <hidden> Date: 2006-07-28 18:33:18
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
quoted
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.
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
On Fri, Jul 28, 2006 at 11:33:16AM -0700, Zach Brown (zach.brown@oracle.com) wrote:
quoted
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.
So, I'm going to create kevent_create/destroy/control and kevent_get_events()
Or any better names?
quoted
quoted
quoted
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
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!
Some events are impossible to create in userspace (like timer
notification, which requires timer start and check when timer
completed).
Actually all events are part of the kernel, since glibc does not have
any knowledge about in-kernel state machines which are bound to
appropriate kevents, so each kevent takes at least two syscall (create
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+.
From: Zach Brown <hidden> Date: 2006-07-28 19:01:31
Things were like that at one point in time, but file descriptors turn out
to introduce a huge gaping security hole with SUID programs. The problem
is that any event context is closely tied to the address space of the
thread issuing the syscalls, and file descriptors do not have this close
binding.
Can you go into that hole in more detail?
Except that you're not usually pulling a full ring worth of events at a
time, more often just one.
OK, but then to wait for it you were already sleeping in the kernel, right?
Clearly we should port httpd to kevents and take some measurements :)
- z
From: Zach Brown <hidden> Date: 2006-07-28 19:10:58
So, I'm going to create kevent_create/destroy/control and kevent_get_events()
Or any better names?
Yeah, that sounds good.
Some events are impossible to create in userspace (like timer
notification, which requires timer start and check when timer
completed).
We're not talking about *creating* events in userspace, we're talking
about checking for their completion events in the ring.
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?
There are events that can be generated by kernel code paths as the event
completes. Network sockets have the hooks to do this with SIGIO, it's
very natural for the storage completion paths, etc. So that kernel code
would update the ring which userspace could check. AIO does this today.
Userspace would still have to use the syscall to sleep waiting for new
events when the ring is empty.
According to syscall speed on Linux, last time I checked empty syscall
took about 100ns on AMD Athlon 3500+.
Oh, sure, but still nice to avoid.
I'm mostly pursuing this because Ulrich seemed so insistent on it in his
paper and talk. I will be very sad if we don't have aggressive glibc
support for this generic event collection interface and so I want very
much to keep him engaged. Ulrich, would you be satisfied if we didn't
have the userspace mapped ring on the first pass and only had a
collection syscall?
- z
On Fri, Jul 28, 2006 at 12:01:28PM -0700, Zach Brown (zach.brown@oracle.com) wrote:
Clearly we should port httpd to kevents and take some measurements :)
One of my main kevent benchmarks (socket notifications for
accept/receive) is handmade http server.
I compared it with FreeBSD kqueue, epoll and kevent_poll
(this is generic poll/select notifications ported to kevent)
based (it is the same server but with different event functions.
Client was httperf, I ran it with 30k connections in bursts of 3k
connection with 1 second timeout between bursts.
Here are results:
kevent: more than 2600 requests/second
epoll and kevent_poll: about 1600-1800 requests/second
kqueue: enormous number of connection reset errors (only 62% of
successfull connections) (likely misconfiguration, default FreeBSD
6-something does not allow such rates at all).
More info can be found on kevent homepage:
http://tservice.net.ru/~s0mbre/old/?section=projects&item=kevent
From: Zach Brown <hidden> Date: 2006-07-28 19:34:51
Evgeniy Polyakov wrote:
On Fri, Jul 28, 2006 at 12:01:28PM -0700, Zach Brown (zach.brown@oracle.com) wrote:
quoted
Clearly we should port httpd to kevents and take some measurements :)
One of my main kevent benchmarks (socket notifications for
accept/receive) is handmade http server.
Yeah, so I noticed. That's a good starting point but I'm more
interested in seeing the work integrated with servers that have to
survive outside of benchmarking runs.
- z
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.
--
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
From: Nicholas Miell <hidden> Date: 2006-07-29 04:33:05
On Fri, 2006-07-28 at 20:38 -0700, Ulrich Drepper wrote:
Zach Brown wrote:
quoted
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.
* http://docs.sun.com/app/docs/doc/816-5168/6mbb3hrir?a=view
--
Nicholas Miell [off-list ref]
On Fri, Jul 28, 2006 at 08:38:02PM -0700, Ulrich Drepper (drepper@redhat.com) wrote:
Zach Brown wrote:
quoted
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.
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?
--
??? Ulrich Drepper ??? Red Hat, Inc. ??? 444 Castro St ??? Mountain View, CA ???
On Fri, Jul 28, 2006 at 09:32:42PM -0700, Nicholas Miell (nmiell@comcast.net) wrote:
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.
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.
--
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
From: Hans Henrik Happe <hidden> Date: 2006-07-29 16:36:21
On Saturday 29 July 2006 18:18, Ulrich Drepper wrote:
Evgeniy Polyakov wrote:
quoted
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.
Couldn't this be done in a general way: Given a fd that supports streaming
input, map some user-mem as a ring buffer for input. Maybe the kernel should
control the buffer in order to make resizing possible (i.e., TCP zero-copy
and window scaling).
Hans Henrik
From: Nicholas Miell <hidden> Date: 2006-07-29 20:55:25
On Sat, 2006-07-29 at 19:48 +0400, Evgeniy Polyakov wrote:
On Fri, Jul 28, 2006 at 09:32:42PM -0700, Nicholas Miell (nmiell@comcast.net) wrote:
quoted
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.
Sorry, I wasn't talking about kevent, I was talking about the interfaces
described in "The Need for Asynchronous, Zero-Copy Network I/O" by
Ulrich Drepper -- specifically the ec_t type and related functions and
the modifications to struct sigevent.
--
Nicholas Miell [off-list ref]
[...] and was wondering
if you were familiar with the Solaris port APIs* and,
I wasn't.
if so, you could
please comment on how your proposed event channels are different/better.
There indeed is not much difference. The differences are in the
details. The way those ports are specified doesn't allow much room for
further optimizations. E.g., the userlevel ring buffer isn't possible.
But mostly it's the same semantics. The ec_t type in my text is also
better a file descriptor since otherwise it cannot be transported via
Unix stream sockets.
--
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
On Sat, Jul 29, 2006 at 09:18:47AM -0700, Ulrich Drepper (drepper@redhat.com) wrote:
Evgeniy Polyakov wrote:
quoted
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.
That requires a copy, which can neglect syscall overhead.
Do we really want it to be done?
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.
And how "misordering" between queue and buffer is going to be managed?
I.e. when buffer is full and events are placed into queue, so syscall
could get them, and then syscall is called to get events from the queue
but not from the buffer - we can endup taking events from buffer while
old are placed in the queue.
And how waiting will be done without syscalls? Will glibc take care of
it?
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.
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?
--
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
On Mon, Jul 31, 2006 at 08:35:55PM +1000, Herbert Xu (herbert@gondor.apana.org.au) wrote:
Evgeniy Polyakov [off-list ref] wrote:
quoted
quoted
- 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.
--
Evgeniy Polyakov
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.
Do you know how many cachelines are dirtied by system call
entry and exit on typical system?
On sparc64 it is a minimum of 3 64-byte cachelines just to save and
restore the system call time cpu register state. If application is
deep in a call chain, register windows might spill and each such
register window will dirty 2 more cachelines as they are dumped to the
stack.
I am not even talking about the other basic necessities of doing
a system call such as touching various task_struct and thread_info
state to check for pending signals etc.
System call overhead is non-trivial especially when you are using
it to move only a few small objects into and out of the kernel.
So I would say for up to 4 or 5 events, system call overhead alone
touches as many cache lines as the events themselves.
On Mon, Jul 31, 2006 at 02:33:22PM +0400, Evgeniy Polyakov (johnpol@2ka.mipt.ru) wrote:
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.
--
Evgeniy Polyakov
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.
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.
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?
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?
The reason one decentralizes event processing into threads is so that
once they are tasked to process some event they need not be concerned
with event state.
They are designed to process their event through to the end, then
return to the top level and say "any more work for me?"
From: Zach Brown <hidden> Date: 2006-07-31 22:46:26
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?
Yeah, that sounds good. I'm looking forward to seeing the next set of
patches :).
- z
From: David Miller <davem@davemloft.net> Date: 2006-08-01 01:03:12
From: Zach Brown <redacted>
Date: Thu, 27 Jul 2006 12:18:42 -0700
[ I kept this thread around in my inbox because I wanted to give it
some deep thought, so sorry for replying to old bits... ]
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.
No need for an owner field, we can use something like a VJ
netchannel datastructure for this. Kernel only writes to
producer index and user only writes to consumer index.
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.
I do not think if we do a ring buffer that events should be obtainable
via a syscall at all. Rather, I think this system call should be
purely "sleep until ring is not empty".
This is actually reasonably simple stuff to implement as Evgeniy
has tried to explain.
Events in kevent live on a ready list when they have triggered.
Existence on a list determined the state, and I think this design
btw invalidates some of the arguments against using netlink that
Ulrich mentions in his paper. If netlink socket queuing fails,
well then kevent stays on ready list and that is all until the
kevent can be successfully published to the user.
I am not advocating netlink at all for this, as the ring buffer idea
is much better.
The ring buffer size, as Evgeniy also tried to describe, is bounded
purely by the number of registered events. So event loop of
application might look something like this:
struct ukevent cur_event;
struct timeval timeo;
setup_timeout(&timeo);
for (;;) {
int err;
while(!(err = ukevent_dequeue(evt_fd, evt_ring,
&cur_event, &timeo))) {
struct my_event_object *o =
event_to_object(&cur_event);
o->dispatch(o, &cur_event);
setup_timeout(&timeo);
}
if (err == -ETIMEDOUT)
timeout_processing();
else
event_error_processing(err);
}
ukevent_dequeue() is perhaps some GLIBC implemented routine which does
something like:
int err;
for (;;) {
if (!evt_ring_empty(evt_ring)) {
struct ukevent *p = evt_ring_consume(evt_ring);
memcpy(event_p, p, sizeof(struct ukevent));
return 0;
}
err = kevent_wait(evt_fd, timeo_p);
if (err < 0)
break;
}
return err;
It's just some stupid ideas... we could also choose to expose the ring
buffer layout directly to the user event loop and let it perform the
dequeue operation and kevent_wait() calls directly. I don't see why
not to allow that.
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?
I do not think so, object for these 3 operations are the same,
so there are no typing issues.
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.
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.
By default all kevents are not removed from the queue, so accept events
will be in the queue and thread B will fail to register new kevent.
To remove kevent from the queue user should either set one-shot flag or
do it by special command.
So if we are in position when queue is full and all events are not
one-shot, control thread must think about what does it do, and remove
some of them (and next time add them with one-shot flag).
--
Evgeniy Polyakov
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.
Not quite true. The ring buffer can be written to from another
processor. The kernel thread responsible for generating the event
(receiving data from network or disk, expired timer) can run
independently on another CPU.
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.
--
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
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.
This is part of why I suggested VJ style channel data
structure. At worst, the cachelines for the entries get
into shared modified state when the remove userland cpu
reads the slot.
This patch includes generic poll/select and timer notifications.
kevent_poll works simialr to epoll and has the same issues (callback
is invoked not from internal state machine of the caller, but through
process awake).
Timer notifications can be used for fine grained per-process time
management, since iteractive timers are very inconveniently to use,
and they are limited.
Signed-off-by: Evgeniy Polyakov <redacted>
@@ -0,0 +1,223 @@+/*+*kevent_poll.c+*+*2006Copyright(c)EvgeniyPolyakov<johnpol@2ka.mipt.ru>+*Allrightsreserved.+*+*Thisprogramisfreesoftware;youcanredistributeitand/ormodify+*itunderthetermsoftheGNUGeneralPublicLicenseaspublishedby+*theFreeSoftwareFoundation;eitherversion2oftheLicense,or+*(atyouroption)anylaterversion.+*+*Thisprogramisdistributedinthehopethatitwillbeuseful,+*butWITHOUTANYWARRANTY;withouteventheimpliedwarrantyof+*MERCHANTABILITYorFITNESSFORAPARTICULARPURPOSE.Seethe+*GNUGeneralPublicLicenseformoredetails.+*/++#include<linux/kernel.h>+#include<linux/types.h>+#include<linux/list.h>+#include<linux/slab.h>+#include<linux/spinlock.h>+#include<linux/timer.h>+#include<linux/file.h>+#include<linux/kevent.h>+#include<linux/poll.h>+#include<linux/fs.h>++statickmem_cache_t*kevent_poll_container_cache;+statickmem_cache_t*kevent_poll_priv_cache;++structkevent_poll_ctl+{+structpoll_table_structpt;+structkevent*k;+};++structkevent_poll_wait_container+{+structlist_headcontainer_entry;+wait_queue_head_t*whead;+wait_queue_twait;+structkevent*k;+};++structkevent_poll_private+{+structlist_headcontainer_list;+spinlock_tcontainer_lock;+};++staticintkevent_poll_enqueue(structkevent*k);+staticintkevent_poll_dequeue(structkevent*k);+staticintkevent_poll_callback(structkevent*k);++staticintkevent_poll_wait_callback(wait_queue_t*wait,+unsignedmode,intsync,void*key)+{+structkevent_poll_wait_container*cont=+container_of(wait,structkevent_poll_wait_container,wait);+structkevent*k=cont->k;+structfile*file=k->st->origin;+unsignedlongflags;+u32revents,event;++revents=file->f_op->poll(file,NULL);+spin_lock_irqsave(&k->lock,flags);+event=k->event.event;+spin_unlock_irqrestore(&k->lock,flags);++kevent_storage_ready(k->st,NULL,revents);++return0;+}++staticvoidkevent_poll_qproc(structfile*file,wait_queue_head_t*whead,+structpoll_table_struct*poll_table)+{+structkevent*k=+container_of(poll_table,structkevent_poll_ctl,pt)->k;+structkevent_poll_private*priv=k->priv;+structkevent_poll_wait_container*cont;+unsignedlongflags;++cont=kmem_cache_alloc(kevent_poll_container_cache,SLAB_KERNEL);+if(!cont){+kevent_break(k);+return;+}++cont->k=k;+init_waitqueue_func_entry(&cont->wait,kevent_poll_wait_callback);+cont->whead=whead;++spin_lock_irqsave(&priv->container_lock,flags);+list_add_tail(&cont->container_entry,&priv->container_list);+spin_unlock_irqrestore(&priv->container_lock,flags);++add_wait_queue(whead,&cont->wait);+}++staticintkevent_poll_enqueue(structkevent*k)+{+structfile*file;+interr,ready=0;+unsignedintrevents;+structkevent_poll_ctlctl;+structkevent_poll_private*priv;++file=fget(k->event.id.raw[0]);+if(!file)+return-ENODEV;++err=-EINVAL;+if(!file->f_op||!file->f_op->poll)+gotoerr_out_fput;++err=-ENOMEM;+priv=kmem_cache_alloc(kevent_poll_priv_cache,SLAB_KERNEL);+if(!priv)+gotoerr_out_fput;++spin_lock_init(&priv->container_lock);+INIT_LIST_HEAD(&priv->container_list);++k->priv=priv;++ctl.k=k;+init_poll_funcptr(&ctl.pt,&kevent_poll_qproc);++err=kevent_storage_enqueue(&file->st,k);+if(err)+gotoerr_out_free;++revents=file->f_op->poll(file,&ctl.pt);+if(revents&k->event.event){+ready=1;+kevent_poll_dequeue(k);+}++returnready;++err_out_free:+kmem_cache_free(kevent_poll_priv_cache,priv);+err_out_fput:+fput(file);+returnerr;+}++staticintkevent_poll_dequeue(structkevent*k)+{+structfile*file=k->st->origin;+structkevent_poll_private*priv=k->priv;+structkevent_poll_wait_container*w,*n;+unsignedlongflags;++kevent_storage_dequeue(k->st,k);++spin_lock_irqsave(&priv->container_lock,flags);+list_for_each_entry_safe(w,n,&priv->container_list,container_entry){+list_del(&w->container_entry);+remove_wait_queue(w->whead,&w->wait);+kmem_cache_free(kevent_poll_container_cache,w);+}+spin_unlock_irqrestore(&priv->container_lock,flags);++kmem_cache_free(kevent_poll_priv_cache,priv);+k->priv=NULL;++fput(file);++return0;+}++staticintkevent_poll_callback(structkevent*k)+{+structfile*file=k->st->origin;+unsignedintrevents=file->f_op->poll(file,NULL);+return(revents&k->event.event);+}++intkevent_init_poll(structkevent*k)+{+if(!kevent_poll_container_cache||!kevent_poll_priv_cache)+return-ENOMEM;++k->enqueue=&kevent_poll_enqueue;+k->dequeue=&kevent_poll_dequeue;+k->callback=&kevent_poll_callback;+return0;+}+++staticint__initkevent_poll_sys_init(void)+{+kevent_poll_container_cache=kmem_cache_create("kevent_poll_container_cache",+sizeof(structkevent_poll_wait_container),0,0,NULL,NULL);+if(!kevent_poll_container_cache){+printk(KERN_ERR"Failed to create kevent poll container cache.\n");+return-ENOMEM;+}++kevent_poll_priv_cache=kmem_cache_create("kevent_poll_priv_cache",+sizeof(structkevent_poll_private),0,0,NULL,NULL);+if(!kevent_poll_priv_cache){+printk(KERN_ERR"Failed to create kevent poll private data cache.\n");+kmem_cache_destroy(kevent_poll_container_cache);+kevent_poll_container_cache=NULL;+return-ENOMEM;+}++printk(KERN_INFO"Kevent poll()/select() subsystem has been initialized.\n");+return0;+}++staticvoid__exitkevent_poll_sys_fini(void)+{+kmem_cache_destroy(kevent_poll_priv_cache);+kmem_cache_destroy(kevent_poll_container_cache);+}++module_init(kevent_poll_sys_init);+module_exit(kevent_poll_sys_fini);
I send this patchset for comments and review, it still contains AIO and
aio_sendfile() implementation on top of get_block() abstraction, which was
decided to postpone for a while (it is simpler right now to generate patchset as a whole,
when kevent will be ready for merge, I will generate patchset without AIO stuff).
It does not contain mapped buffer implementation, since it's design is not 100%
completed, I will present that implementation in the third patchset.
Changes from previous patchset:
- rebased against 2.6.18-git tree
- removed ioctl controlling
- added new syscall kevent_get_events(int fd, unsigned int min_nr, unsigned int max_nr,
unsigned int timeout, void __user *buf, unsigned flags)
- use old syscall kevent_ctl for creation/removing, modification and initial kevent
initialization
- use mutuxes instead of semaphores
- added file descriptor check and return error if provided descriptor does not match
kevent file operations
- various indent fixes
- removed aio_sendfile() declarations.
Thank you.
Signed-off-by: Evgeniy Polyakov <redacted>
This patch includes core kevent files:
- userspace controlling
- kernelspace interfaces
- initialization
- 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 <redacted>
@@ -0,0 +1,259 @@+/*+*kevent.h+*+*2006Copyright(c)EvgeniyPolyakov<johnpol@2ka.mipt.ru>+*Allrightsreserved.+*+*Thisprogramisfreesoftware;youcanredistributeitand/ormodify+*itunderthetermsoftheGNUGeneralPublicLicenseaspublishedby+*theFreeSoftwareFoundation;eitherversion2oftheLicense,or+*(atyouroption)anylaterversion.+*+*Thisprogramisdistributedinthehopethatitwillbeuseful,+*butWITHOUTANYWARRANTY;withouteventheimpliedwarrantyof+*MERCHANTABILITYorFITNESSFORAPARTICULARPURPOSE.Seethe+*GNUGeneralPublicLicenseformoredetails.+*+*YoushouldhavereceivedacopyoftheGNUGeneralPublicLicense+*alongwiththisprogram;ifnot,writetotheFreeSoftware+*Foundation,Inc.,59TemplePlace,Suite330,Boston,MA02111-1307USA+*/++#ifndef __KEVENT_H+#define __KEVENT_H++/*+*Keventrequestflags.+*/++#define KEVENT_REQ_ONESHOT 0x1 /* Process this event only once and then dequeue. */++/*+*Keventreturnflags.+*/+#define KEVENT_RET_BROKEN 0x1 /* Kevent is broken. */+#define KEVENT_RET_DONE 0x2 /* Kevent processing was finished successfully. */++/*+*Keventtypeset.+*/+#define KEVENT_SOCKET 0+#define KEVENT_INODE 1+#define KEVENT_TIMER 2+#define KEVENT_POLL 3+#define KEVENT_NAIO 4+#define KEVENT_AIO 5+#define KEVENT_MAX 6++/*+*Per-typeeventsets.+*Numberofper-eventsetsshouldbeexactlyasnumberofkeventtypes.+*/++/*+*Timerevents.+*/+#define KEVENT_TIMER_FIRED 0x1++/*+*Socket/networkasynchronousIOevents.+*/+#define KEVENT_SOCKET_RECV 0x1+#define KEVENT_SOCKET_ACCEPT 0x2+#define KEVENT_SOCKET_SEND 0x4++/*+*Inodeevents.+*/+#define KEVENT_INODE_CREATE 0x1+#define KEVENT_INODE_REMOVE 0x2++/*+*Pollevents.+*/+#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++#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++/*+*AsynchronousIOevents.+*/+#define KEVENT_AIO_BIO 0x1++#define KEVENT_MASK_ALL 0xffffffff /* Mask of all possible event values. */+#define KEVENT_MASK_EMPTY 0x0 /* Empty mask of ready events. */++structkevent_id+{+__u32raw[2];+};++structukevent+{+structkevent_idid;/* Id of this request, e.g. socket number, file descriptor and so on... */+__u32type;/* Event type, e.g. KEVENT_SOCK, KEVENT_INODE, KEVENT_TIMER and so on... */+__u32event;/* Event itself, e.g. SOCK_ACCEPT, INODE_CREATED, TIMER_FIRED... */+__u32req_flags;/* Per-event request flags */+__u32ret_flags;/* Per-event return flags */+__u32ret_data[2];/* Event return data. Event originator fills it with anything it likes. */+union{+__u32user[2];/* User's data. It is not used, just copied to/from user. */+void*ptr;+};+};++#define KEVENT_CTL_ADD 0+#define KEVENT_CTL_REMOVE 1+#define KEVENT_CTL_MODIFY 2+#define KEVENT_CTL_INIT 3++structkevent_user_control+{+unsignedintcmd;/* Control command, e.g. KEVENT_ADD, KEVENT_REMOVE... */+unsignedintnum;/* Number of ukevents this strucutre controls. */+unsignedinttimeout;/* Timeout in milliseconds waiting for "num" events to become ready. */+};++#ifdef __KERNEL__++#include<linux/types.h>+#include<linux/list.h>+#include<linux/spinlock.h>+#include<linux/mutex.h>+#include<linux/wait.h>+#include<linux/kevent_storage.h>++structinode;+structdentry;+structsock;++structkevent;+structkevent_storage;+typedefint(*kevent_callback_t)(structkevent*);++structkevent+{+structukeventevent;+spinlock_tlock;/* This lock protects ukevent manipulations, e.g. ret_flags changes. */++structlist_headkevent_entry;/* Entry of user's queue. */+structlist_headstorage_entry;/* Entry of origin's queue. */+structlist_headready_entry;/* Entry of user's ready. */++structkevent_user*user;/* User who requested this kevent. */+structkevent_storage*st;/* Kevent container. */++kevent_callback_tcallback;/* Is called each time new event has been caught. */+kevent_callback_tenqueue;/* Is called each time new event is queued. */+kevent_callback_tdequeue;/* Is called each time event is dequeued. */++void*priv;/* Private data for different storages. +*poll()/selectstoragehasalistofwait_queue_tcontainers+*foreach->poll(){poll_wait()'}here.+*/+};++#define KEVENT_HASH_MASK 0xff++structkevent_list+{+structlist_headkevent_list;/* List of all kevents. */+spinlock_tkevent_lock;/* Protects all manipulations with queue of kevents. */+};++structkevent_user+{+structkevent_listkqueue[KEVENT_HASH_MASK+1];+unsignedintkevent_num;/* Number of queued kevents. */++structlist_headready_list;/* List of ready kevents. */+unsignedintready_num;/* Number of ready kevents. */+spinlock_tready_lock;/* Protects all manipulations with ready queue. */++unsignedintmax_ready_num;/* Requested number of kevents. */++structmutexctl_mutex;/* Protects against simultaneous kevent_user control manipulations. */+structmutexwait_mutex;/* Protects against simultaneous kevent_user waits. */+wait_queue_head_twait;/* Wait until some events are ready. */++atomic_trefcnt;/* Reference counter, increased for each new kevent. */+#ifdef CONFIG_KEVENT_USER_STAT+unsignedlongim_num;+unsignedlongwait_num;+unsignedlongtotal;+#endif+};++#define KEVENT_MAX_REQUESTS PAGE_SIZE/sizeof(struct kevent)++structkevent*kevent_alloc(gfp_tmask);+voidkevent_free(structkevent*k);+intkevent_enqueue(structkevent*k);+intkevent_dequeue(structkevent*k);+intkevent_init(structkevent*k);+voidkevent_requeue(structkevent*k);++#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))++intkevent_break(structkevent*k);+intkevent_init(structkevent*k);++intkevent_init_socket(structkevent*k);+intkevent_init_inode(structkevent*k);+intkevent_init_timer(structkevent*k);+intkevent_init_poll(structkevent*k);+intkevent_init_naio(structkevent*k);+intkevent_init_aio(structkevent*k);++voidkevent_storage_ready(structkevent_storage*st,+kevent_callback_tready_callback,u32event);+intkevent_storage_init(void*origin,structkevent_storage*st);+voidkevent_storage_fini(structkevent_storage*st);+intkevent_storage_enqueue(structkevent_storage*st,structkevent*k);+voidkevent_storage_dequeue(structkevent_storage*st,structkevent*k);++intkevent_user_add_ukevent(structukevent*uk,structkevent_user*u);++#ifdef CONFIG_KEVENT_INODE+voidkevent_inode_notify(structinode*inode,u32event);+voidkevent_inode_notify_parent(structdentry*dentry,u32event);+voidkevent_inode_remove(structinode*inode);+#else+staticinlinevoidkevent_inode_notify(structinode*inode,u32event)+{+}+staticinlinevoidkevent_inode_notify_parent(structdentry*dentry,u32event)+{+}+staticinlinevoidkevent_inode_remove(structinode*inode)+{+}+#endif /* CONFIG_KEVENT_INODE */+#ifdef CONFIG_KEVENT_SOCKET++voidkevent_socket_notify(structsock*sock,u32event);+intkevent_socket_dequeue(structkevent*k);+intkevent_socket_enqueue(structkevent*k);+#define sock_async(__sk) sock_flag(__sk, SOCK_ASYNC)+#else+staticinlinevoidkevent_socket_notify(structsock*sock,u32event)+{+}+#define sock_async(__sk) 0+#endif+#endif /* __KERNEL__ */+#endif /* __KEVENT_H */
@@ -0,0 +1,12 @@+#ifndef __KEVENT_STORAGE_H+#define __KEVENT_STORAGE_H++structkevent_storage+{+void*origin;/* Originator's pointer, e.g. struct sock or struct file. Can be NULL. */+structlist_headlist;/* List of queued kevents. */+unsignedintqlen;/* Number of queued kevents. */+spinlock_tlock;/* Protects users queue. */+};++#endif /* __KEVENT_STORAGE_H */
@@ -0,0 +1,248 @@+/*+*kevent.c+*+*2006Copyright(c)EvgeniyPolyakov<johnpol@2ka.mipt.ru>+*Allrightsreserved.+*+*Thisprogramisfreesoftware;youcanredistributeitand/ormodify+*itunderthetermsoftheGNUGeneralPublicLicenseaspublishedby+*theFreeSoftwareFoundation;eitherversion2oftheLicense,or+*(atyouroption)anylaterversion.+*+*Thisprogramisdistributedinthehopethatitwillbeuseful,+*butWITHOUTANYWARRANTY;withouteventheimpliedwarrantyof+*MERCHANTABILITYorFITNESSFORAPARTICULARPURPOSE.Seethe+*GNUGeneralPublicLicenseformoredetails.+*+*YoushouldhavereceivedacopyoftheGNUGeneralPublicLicense+*alongwiththisprogram;ifnot,writetotheFreeSoftware+*Foundation,Inc.,59TemplePlace,Suite330,Boston,MA02111-1307USA+*/++#include<linux/kernel.h>+#include<linux/types.h>+#include<linux/list.h>+#include<linux/slab.h>+#include<linux/spinlock.h>+#include<linux/mempool.h>+#include<linux/sched.h>+#include<linux/wait.h>+#include<linux/kevent.h>++statickmem_cache_t*kevent_cache;++/*+*Attemptstoaddaneventintoappropriateorigin'squeue.+*Returnspositivevalueifthiseventisreadyimmediately,+*negativevalueincaseoferrorandzeroifeventhasbeenqueued.+*->enqueue()callbackmustincreaseorigin'sreferencecounter.+*/+intkevent_enqueue(structkevent*k)+{+if(k->event.type>=KEVENT_MAX)+return-E2BIG;++if(!k->enqueue){+kevent_break(k);+return-EINVAL;+}++returnk->enqueue(k);+}++/*+*Removeeventfromtheappropriatequeue.+*->dequeue()callbackmustdecreaseorigin'sreferencecounter.+*/+intkevent_dequeue(structkevent*k)+{+if(k->event.type>=KEVENT_MAX)+return-E2BIG;++if(!k->dequeue){+kevent_break(k);+return-EINVAL;+}++returnk->dequeue(k);+}++/*+*Mustbecalledbeforeeventisgoingtobeaddedintosomeorigin'squeue.+*Initializes->enqueue(),->dequeue()and->callback()callbacks.+*Iffailed,keventshouldnotbeusedorkevent_enqueue()willfailtoadd+*thiskeventintoorigin'squeuewithsetting+*KEVENT_RET_BROKENflaginkevent->event.ret_flags.+*/+intkevent_init(structkevent*k)+{+interr;++spin_lock_init(&k->lock);+k->kevent_entry.next=LIST_POISON1;+k->storage_entry.next=LIST_POISON1;+k->ready_entry.next=LIST_POISON1;++if(k->event.type>=KEVENT_MAX)+return-E2BIG;++switch(k->event.type){+caseKEVENT_NAIO:+err=kevent_init_naio(k);+break;+caseKEVENT_SOCKET:+err=kevent_init_socket(k);+break;+caseKEVENT_INODE:+err=kevent_init_inode(k);+break;+caseKEVENT_TIMER:+err=kevent_init_timer(k);+break;+caseKEVENT_POLL:+err=kevent_init_poll(k);+break;+caseKEVENT_AIO:+err=kevent_init_aio(k);+break;+default:+err=-ENODEV;+}++returnerr;+}++/*+*Calledfrom->enqueue()callbackwhenreferencecounterforgiven+*origin(socket,inode...)hasbeenincreased.+*/+intkevent_storage_enqueue(structkevent_storage*st,structkevent*k)+{+unsignedlongflags;++k->st=st;+spin_lock_irqsave(&st->lock,flags);+list_add_tail(&k->storage_entry,&st->list);+st->qlen++;+spin_unlock_irqrestore(&st->lock,flags);+return0;+}++/*+*Dequeuekeventfromorigin'squeue.+*Itdoesnotdecreaseorigin'sreferencecounterinanyway+*andmustbecalledbeforeit,sostorageitselfmustbevalid.+*Itiscalledfrom->dequeue()callback.+*/+voidkevent_storage_dequeue(structkevent_storage*st,structkevent*k)+{+unsignedlongflags;++spin_lock_irqsave(&st->lock,flags);+if(k->storage_entry.next!=LIST_POISON1){+list_del(&k->storage_entry);+st->qlen--;+}+spin_unlock_irqrestore(&st->lock,flags);+}++staticvoid__kevent_requeue(structkevent*k,u32event)+{+interr,rem=0;+unsignedlongflags;++err=k->callback(k);++spin_lock_irqsave(&k->lock,flags);+if(err>0){+k->event.ret_flags|=KEVENT_RET_DONE;+}elseif(err<0){+k->event.ret_flags|=KEVENT_RET_BROKEN;+k->event.ret_flags|=KEVENT_RET_DONE;+}+rem=(k->event.req_flags&KEVENT_REQ_ONESHOT);+if(!err)+err=(k->event.ret_flags&(KEVENT_RET_BROKEN|KEVENT_RET_DONE));+spin_unlock_irqrestore(&k->lock,flags);++if(err){+if(rem){+list_del(&k->storage_entry);+k->st->qlen--;+}++spin_lock_irqsave(&k->user->ready_lock,flags);+if(k->ready_entry.next==LIST_POISON1){+list_add_tail(&k->ready_entry,&k->user->ready_list);+k->user->ready_num++;+}+spin_unlock_irqrestore(&k->user->ready_lock,flags);+wake_up(&k->user->wait);+}+}++voidkevent_requeue(structkevent*k)+{+unsignedlongflags;++spin_lock_irqsave(&k->st->lock,flags);+__kevent_requeue(k,0);+spin_unlock_irqrestore(&k->st->lock,flags);+}++/*+*Calledeachtimesomeactivityinorigin(socket,inode...)isnoticed.+*/+voidkevent_storage_ready(structkevent_storage*st,+kevent_callback_tready_callback,u32event)+{+structkevent*k,*n;++spin_lock(&st->lock);+list_for_each_entry_safe(k,n,&st->list,storage_entry){+if(ready_callback)+ready_callback(k);++if(event&k->event.event)+__kevent_requeue(k,event);+}+spin_unlock(&st->lock);+}++intkevent_storage_init(void*origin,structkevent_storage*st)+{+spin_lock_init(&st->lock);+st->origin=origin;+st->qlen=0;+INIT_LIST_HEAD(&st->list);+return0;+}++voidkevent_storage_fini(structkevent_storage*st)+{+kevent_storage_ready(st,kevent_break,KEVENT_MASK_ALL);+}++structkevent*kevent_alloc(gfp_tmask)+{+returnkmem_cache_alloc(kevent_cache,mask);+}++voidkevent_free(structkevent*k)+{+kmem_cache_free(kevent_cache,k);+}++int__initkevent_sys_init(void)+{+interr=0;++kevent_cache=kmem_cache_create("kevent_cache",+sizeof(structkevent),0,0,NULL,NULL);+if(!kevent_cache)+panic("kevent: Unable to create a cache.\n");++returnerr;+}++late_initcall(kevent_sys_init);
This patchset includes socket notifications and network asynchronous IO.
Network AIO is based on kevent and works as usual kevent storage on top
of inode.
Signed-off-by: Evgeniy Polyakov <redacted>
@@ -548,6 +567,12 @@ struct proto {int(*backlog_rcv)(structsock*sk,structsk_buff*skb);++int(*async_recv)(structsock*sk,+void*dst,size_tsize);+int(*async_send)(structsock*sk,+structpage**pages,unsignedintpoffset,+size_tsize);/* Keeping track of sk's, looking them up, and port selection methods. */void(*hash)(structsock*sk);
@@ -1085,6 +1086,301 @@ int tcp_read_sock(struct sock *sk, read_}/*+*Mustbecalledwithlockedsock.+*/+inttcp_async_send(structsock*sk,structpage**pages,unsignedintpoffset,size_tlen)+{+structtcp_sock*tp=tcp_sk(sk);+intmss_now,size_goal;+interr=-EAGAIN;+ssize_tcopied;++/* Wait for a connection to finish. */+if((1<<sk->sk_state)&~(TCPF_ESTABLISHED|TCPF_CLOSE_WAIT))+gotoout_err;++clear_bit(SOCK_ASYNC_NOSPACE,&sk->sk_socket->flags);++mss_now=tcp_current_mss(sk,1);+size_goal=tp->xmit_size_goal;+copied=0;++err=-EPIPE;+if(sk->sk_err||(sk->sk_shutdown&SEND_SHUTDOWN)||sock_flag(sk,SOCK_DONE)||+(sk->sk_state==TCP_CLOSE)||(atomic_read(&sk->sk_refcnt)==1))+gotodo_error;++while(len>0){+structsk_buff*skb=sk->sk_write_queue.prev;+structpage*page=pages[poffset/PAGE_SIZE];+intcopy,i,can_coalesce;+intoffset=poffset%PAGE_SIZE;+intsize=min_t(size_t,len,PAGE_SIZE-offset);++if(!sk->sk_send_head||(copy=size_goal-skb->len)<=0){+new_segment:+if(!sk_stream_memory_free(sk))+gotowait_for_sndbuf;++skb=sk_stream_alloc_pskb(sk,0,0,+sk->sk_allocation);+if(!skb)+gotowait_for_memory;++skb_entail(sk,tp,skb);+copy=size_goal;+}++if(copy>size)+copy=size;++i=skb_shinfo(skb)->nr_frags;+can_coalesce=skb_can_coalesce(skb,i,page,offset);+if(!can_coalesce&&i>=MAX_SKB_FRAGS){+tcp_mark_push(tp,skb);+gotonew_segment;+}+if(!sk_stream_wmem_schedule(sk,copy))+gotowait_for_memory;++if(can_coalesce){+skb_shinfo(skb)->frags[i-1].size+=copy;+}else{+get_page(page);+skb_fill_page_desc(skb,i,page,offset,copy);+}++skb->len+=copy;+skb->data_len+=copy;+skb->truesize+=copy;+sk->sk_wmem_queued+=copy;+sk->sk_forward_alloc-=copy;+skb->ip_summed=CHECKSUM_HW;+tp->write_seq+=copy;+TCP_SKB_CB(skb)->end_seq+=copy;+skb_shinfo(skb)->gso_segs=0;++if(!copied)+TCP_SKB_CB(skb)->flags&=~TCPCB_FLAG_PSH;++copied+=copy;+poffset+=copy;+if(!(len-=copy))+gotoout;++if(skb->len<mss_now)+continue;++if(forced_push(tp)){+tcp_mark_push(tp,skb);+__tcp_push_pending_frames(sk,tp,mss_now,TCP_NAGLE_PUSH);+}elseif(skb==sk->sk_send_head)+tcp_push_one(sk,mss_now);+continue;++wait_for_sndbuf:+set_bit(SOCK_NOSPACE,&sk->sk_socket->flags);+wait_for_memory:+if(copied)+tcp_push(sk,tp,0,mss_now,TCP_NAGLE_PUSH);++err=-EAGAIN;+gotodo_error;+}++out:+if(copied)+tcp_push(sk,tp,0,mss_now,tp->nonagle);+returncopied;++do_error:+if(copied)+gotoout;+out_err:+returnsk_stream_error(sk,0,err);+}++/*+*Mustbecalledwithlockedsock.+*/+inttcp_async_recv(structsock*sk,void*dst,size_tlen)+{+structtcp_sock*tp=tcp_sk(sk);+intcopied=0;+u32*seq;+unsignedlongused;+interr;+inttarget;/* Read at least this many bytes */+intcopied_early=0;++TCP_CHECK_TIMER(sk);++err=-ENOTCONN;+if(sk->sk_state==TCP_LISTEN)+gotoout;++seq=&tp->copied_seq;++target=sock_rcvlowat(sk,0,len);++do{+structsk_buff*skb;+u32offset;++/* Are we at urgent data? Stop if we have read anything or have SIGURG pending. */+if(tp->urg_data&&tp->urg_seq==*seq){+if(copied)+break;+}++/* Next get a buffer. */++skb=skb_peek(&sk->sk_receive_queue);+do{+if(!skb)+break;++/* Now that we have two receive queues this+*shouldn'thappen.+*/+if(before(*seq,TCP_SKB_CB(skb)->seq)){+printk(KERN_INFO"async_recv bug: copied %X "+"seq %X\n",*seq,TCP_SKB_CB(skb)->seq);+break;+}+offset=*seq-TCP_SKB_CB(skb)->seq;+if(skb->h.th->syn)+offset--;+if(offset<skb->len)+gotofound_ok_skb;+if(skb->h.th->fin)+gotofound_fin_ok;+skb=skb->next;+}while(skb!=(structsk_buff*)&sk->sk_receive_queue);++if(copied)+break;++if(sock_flag(sk,SOCK_DONE))+break;++if(sk->sk_err){+copied=sock_error(sk);+break;+}++if(sk->sk_shutdown&RCV_SHUTDOWN)+break;++if(sk->sk_state==TCP_CLOSE){+if(!sock_flag(sk,SOCK_DONE)){+/* This occurs when user tries to read+*fromneverconnectedsocket.+*/+copied=-ENOTCONN;+break;+}+break;+}++copied=-EAGAIN;+break;++found_ok_skb:+/* Ok so how much can we use? */+used=skb->len-offset;+if(len<used)+used=len;++/* Do we have urgent data here? */+if(tp->urg_data){+u32urg_offset=tp->urg_seq-*seq;+if(urg_offset<used){+if(!urg_offset){+if(!sock_flag(sk,SOCK_URGINLINE)){+++*seq;+offset++;+used--;+if(!used)+gotoskip_copy;+}+}else+used=urg_offset;+}+}+#ifdef CONFIG_NET_DMA+if(!tp->ucopy.dma_chan&&tp->ucopy.pinned_list)+tp->ucopy.dma_chan=get_softnet_dma();++if(tp->ucopy.dma_chan){+tp->ucopy.dma_cookie=dma_skb_copy_datagram_iovec(+tp->ucopy.dma_chan,skb,offset,+msg->msg_iov,used,+tp->ucopy.pinned_list);++if(tp->ucopy.dma_cookie<0){++printk(KERN_ALERT"dma_cookie < 0\n");++/* Exception. Bailout! */+if(!copied)+copied=-EFAULT;+break;+}+if((offset+used)==skb->len)+copied_early=1;++}else+#endif+{+err=skb_copy_datagram(skb,offset,dst,used);+if(err){+/* Exception. Bailout! */+if(!copied)+copied=-EFAULT;+break;+}+}++*seq+=used;+copied+=used;+len-=used;+dst+=used;++tcp_rcv_space_adjust(sk);++skip_copy:+if(tp->urg_data&&after(tp->copied_seq,tp->urg_seq)){+tp->urg_data=0;+tcp_fast_path_check(sk,tp);+}+if(used+offset<skb->len)+continue;++if(skb->h.th->fin)+gotofound_fin_ok;+sk_eat_skb(sk,skb,copied_early);+continue;++found_fin_ok:+/* Process the FIN. */+++*seq;+sk_eat_skb(sk,skb,copied_early);+break;+}while(len>0);++/* Clean up data we have read: This will do ACK frames. */+tcp_cleanup_rbuf(sk,copied);++TCP_CHECK_TIMER(sk);+returncopied;++out:+TCP_CHECK_TIMER(sk);+returnerr;+}++/**Thisroutinecopiesfromasockstructintotheuserbuffer.**Technicalnote:in2.3weworkon_locked_socket,sothat
This patch includes asynchronous propagation of file's data into VFS
cache and aio_sendfile() implementation.
Network aio_sendfile() works lazily - it asynchronously populates pages
into the VFS cache (which can be used for various tricks with adaptive
readahead) and then uses usual ->sendfile() callback.
Signed-off-by: Evgeniy Polyakov <redacted>
@@ -165,12 +166,18 @@ #endif}memset(&inode->u,0,sizeof(inode->u));inode->i_mapping=mapping;+#if defined CONFIG_KEVENT+kevent_storage_init(inode,&inode->st);+#endif}returninode;}voiddestroy_inode(structinode*inode){+#if defined CONFIG_KEVENT_INODE || defined CONFIG_KEVENT_SOCKET+kevent_storage_fini(&inode->st);+#endifBUG_ON(inode_has_buffers(inode));security_inode_free(inode);if(inode->i_sb->s_op->destroy_inode)
@@ -546,6 +551,10 @@ #ifdef CONFIG_INOTIFYstructmutexinotify_mutex;/* protects the watches list */#endif+#ifdef CONFIG_KEVENT_INODE+structkevent_storagest;+#endif+unsignedlongi_state;unsignedlongdirtied_when;/* jiffies of first dirtying */
Generally, #ifdefs in the body of the kernel code are discouraged. Can
you abstract these out as static inlines?
- James
--
James Morris
[off-list ref]
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.
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?
Yes, please, it is standard kernel development practice.
Otherwise, the kernel will turn into an unmaintainable #ifdef jungle.
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.
Fine, make
static inline void kevent_user_stat_reset(u);
etc.
which compile to nothing when it's not confifgured.
--
James Morris
[off-list ref]
From: Zach Brown <hidden> Date: 2006-08-01 17:02:32
I do not think if we do a ring buffer that events should be obtainable
via a syscall at all. Rather, I think this system call should be
purely "sleep until ring is not empty".
Mmm, yeah, of course. That's much simpler. I'm looking forward to
Evgeniy's next patch set.
The ring buffer size, as Evgeniy also tried to describe, is bounded
purely by the number of registered events.
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.
And couldn't we just use the existing poll bit definitions for this?
+struct kevent_id
+{
+ __u32 raw[2];
+};
Why not a simple u64? Users can play games with packing it into other
types if they want.
+ __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.
+};
+
+#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. */
+ 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.
+struct kevent
+{
(trivial nit, "struct kevent {" is the preferred form.)
+ 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.
+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.
+#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 :).
+#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; }) .
+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.
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.
A few things here. First, the event argument isn't used?
+ 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.
+ 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.
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.
+ 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.
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.
+/*
+ * 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();
}
+ 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.
+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;
+ }
+
+ 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.
Ahhh, it's fs/aio.c:lookup_kiocb() all over again :) :). I guess we'll
get this in a hash, or something, before merging.
+ mutex_lock(&u->ctl_mutex);
+
+ for (i=0; i<ctl->num; ++i) {
+ if (copy_from_user(&uk, arg, sizeof(struct ukevent))) {
+ err = -EINVAL;
+ break;
+ }
+
+ 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.
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.
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.
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.
+/*
+ * 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.
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
From: David Miller <davem@davemloft.net> Date: 2006-08-02 00:02:37
From: Zach Brown <redacted>
Date: Tue, 01 Aug 2006 16:56:59 -0700
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.
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.
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 :)
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.
I wonder if these shouldn't live in the subsystems instead of in kevent.h.
Yes it could, but it requires including those files in kevent.h, which
is exported to userspace, and it is not always possible to publish
included file there.
And couldn't we just use the existing poll bit definitions for this?
asm/poll.h I expect.
linux/poll.h is too heavy or not?
quoted
+struct kevent_id
+{
+ __u32 raw[2];
+};
Why not a simple u64? Users can play games with packing it into other
types if they want.
quoted
+ __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.
u64 is not aligned, so I prefer to use u32 as much as possible.
quoted
+};
+
+#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. */
+ 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.
Ok.
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.
It has variable size, I strongly against such things between kernel and
userspace.
quoted
+struct kevent
+{
(trivial nit, "struct kevent {" is the preferred form.)
Ok.
quoted
+ 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.
But it requires much less typing :)
Will update.
quoted
+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.
Well, it scales better than one lock per the whole queue, but we can
see how it looks with one lock.
I used RCU hash table in kevents, but it scales very bad for things like
inode removal, which can not be done (at least when kevent was initially
created) in rcu callback context, so it required sycnhronize)rcu() which
broke latencies to unacceptible level.
As David mentioned, I expect it to be base for mapped ring, although it
should be PAGE_SIZE/sizeof(struct ukevent). I will remove for now.
quoted
+#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 :).
It is from the past life, I will remove it.
quoted
+#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; }) .
Ok.
quoted
+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.
Well, the idea was to be able not only to embed kevent_storage, but to
have a pointer to it, so some users can allocate it as addon.
If we strongly decide, that it will not used that way, this pointer can
be removed.
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.
Is this relying on list_del() having set LIST_POISON1? If so, please
use list_del_init() and list_empty() instead.
Yes, POISON is a flag, that keven is or is not in the appropriate list.
It could be done by wasting some bits, but I decided to not do it since
list poison is always there.
A few things here. First, the event argument isn't used?
Tss, it was used for printk when it was there :)
quoted
+ 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.
No, interrupts and bh a not blocked there, when it is called from
origin's state machine.
locking is following:
storage_lock (interrupts and bh are in the state which was in a origin's
state machine, for example socket code has bh disabled, but block layer
has interrupts disabled here)
check if at aleast one event in storage queue is requested for
that event
call callback
It is possible to mark event as broken or done in callback, so we need
to check event's flags. It does not actually require irqsave lock, since
the same kevent can not live in several storages.
We hold a lock to protect against userspace which can change that flags.
If it is marked as ready we queue that event into ready list under
ready list lock. That requires irq disabling, since that queue can be
accessed from any context.
So there are maximum 2 embedded locks.
When userspace modifies kevent, it must protect against access from the
origin, so it disables interrupt.
quoted
+ spin_lock_irqsave(&k->lock, flags);
quoted
+ 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.
Above sequence is only possible when userspace modifies kevent which was
not fired yet, and that modification ends up in immediat fire.
When it is called from origin's state machine irqs are disabled only
when kevent is moved into the ready queue, since that queue can be
accessed from different CPU or from irq on the same one.
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.
kevent users can call any callback they want here, for example it can
mark all events as ready, not only broken, or all mark as one-shot if
origin is going to be removed and so on.
quoted
+ 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.
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.
Yes, I will wrap it into some nice function.
quoted
+/*
+ * 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();
}
Ok.
quoted
+ 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.
Well, if list is empty that means that kevent_entry has a broken links,
which will will fire on list_del.
And having a lot of BUGs is not a good sign.
But I do not care much actually about it, let's have couple...
quoted
+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;
+ }
+
+ 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.
Ahhh, it's fs/aio.c:lookup_kiocb() all over again :) :). I guess we'll
get this in a hash, or something, before merging.
Please note that it is searching inside hash bucket :)
quoted
+ mutex_lock(&u->ctl_mutex);
+
+ for (i=0; i<ctl->num; ++i) {
+ if (copy_from_user(&uk, arg, sizeof(struct ukevent))) {
+ err = -EINVAL;
+ break;
+ }
+
+ 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.
Each lock is hosted inside a bucket, but kevent itself is protected by
that mutex. lock is being held for relatively small operations, but
mutex protects against the whole sequence of them (select bucket,
search, hash and so on).
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.
struct ukevent here can be allocated in stack and filled by naio or aio.
I would not allow them to allocate and link kevents by itself, so I
created this function.
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.
kevent_user_control will be replaced with explicit syscall parameters,
so it will be removed.
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.
Well, it is possible with additional GPF_KERNEL allocation of the buffer,
do we want that cost?
quoted
+/*
+ * 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.
Zero timeout means that we want as much as we have, but not less than one kevent.
So we sleep one second for them :)
I will use min_nr for that, i.e. if it is zero, than it meanst at least
onee and less than max_nr.
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.
On Tue, Aug 01, 2006 at 05:01:38PM -0700, David Miller (davem@davemloft.net) wrote:
From: Zach Brown <redacted>
Date: Tue, 01 Aug 2006 16:56:59 -0700
quoted
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.
It does not require compat macros, since unsigned int has the same size
on all normal machines where Linux runs, although it can be different.
Anyway, I will replace it with explicit syscall parameters.
quoted
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.
Heh, it was so much less typing...
quoted
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 :)
Network AIO, socket notifications.
This patchset includes socket notifications and network asynchronous IO.
Network AIO is based on kevent and works as usual kevent storage on top
of inode.
Signed-off-by: Evgeniy Polyakov <redacted>
@@ -548,6 +567,12 @@ struct proto {int(*backlog_rcv)(structsock*sk,structsk_buff*skb);++int(*async_recv)(structsock*sk,+void*dst,size_tsize);+int(*async_send)(structsock*sk,+structpage**pages,unsignedintpoffset,+size_tsize);/* Keeping track of sk's, looking them up, and port selection methods. */void(*hash)(structsock*sk);
@@ -1085,6 +1086,301 @@ int tcp_read_sock(struct sock *sk, read_}/*+*Mustbecalledwithlockedsock.+*/+inttcp_async_send(structsock*sk,structpage**pages,unsignedintpoffset,size_tlen)+{+structtcp_sock*tp=tcp_sk(sk);+intmss_now,size_goal;+interr=-EAGAIN;+ssize_tcopied;++/* Wait for a connection to finish. */+if((1<<sk->sk_state)&~(TCPF_ESTABLISHED|TCPF_CLOSE_WAIT))+gotoout_err;++clear_bit(SOCK_ASYNC_NOSPACE,&sk->sk_socket->flags);++mss_now=tcp_current_mss(sk,1);+size_goal=tp->xmit_size_goal;+copied=0;++err=-EPIPE;+if(sk->sk_err||(sk->sk_shutdown&SEND_SHUTDOWN)||sock_flag(sk,SOCK_DONE)||+(sk->sk_state==TCP_CLOSE)||(atomic_read(&sk->sk_refcnt)==1))+gotodo_error;++while(len>0){+structsk_buff*skb=sk->sk_write_queue.prev;+structpage*page=pages[poffset/PAGE_SIZE];+intcopy,i,can_coalesce;+intoffset=poffset%PAGE_SIZE;+intsize=min_t(size_t,len,PAGE_SIZE-offset);++if(!sk->sk_send_head||(copy=size_goal-skb->len)<=0){+new_segment:+if(!sk_stream_memory_free(sk))+gotowait_for_sndbuf;++skb=sk_stream_alloc_pskb(sk,0,0,+sk->sk_allocation);+if(!skb)+gotowait_for_memory;++skb_entail(sk,tp,skb);+copy=size_goal;+}++if(copy>size)+copy=size;++i=skb_shinfo(skb)->nr_frags;+can_coalesce=skb_can_coalesce(skb,i,page,offset);+if(!can_coalesce&&i>=MAX_SKB_FRAGS){+tcp_mark_push(tp,skb);+gotonew_segment;+}+if(!sk_stream_wmem_schedule(sk,copy))+gotowait_for_memory;++if(can_coalesce){+skb_shinfo(skb)->frags[i-1].size+=copy;+}else{+get_page(page);+skb_fill_page_desc(skb,i,page,offset,copy);+}++skb->len+=copy;+skb->data_len+=copy;+skb->truesize+=copy;+sk->sk_wmem_queued+=copy;+sk->sk_forward_alloc-=copy;+skb->ip_summed=CHECKSUM_HW;+tp->write_seq+=copy;+TCP_SKB_CB(skb)->end_seq+=copy;+skb_shinfo(skb)->gso_segs=0;++if(!copied)+TCP_SKB_CB(skb)->flags&=~TCPCB_FLAG_PSH;++copied+=copy;+poffset+=copy;+if(!(len-=copy))+gotoout;++if(skb->len<mss_now)+continue;++if(forced_push(tp)){+tcp_mark_push(tp,skb);+__tcp_push_pending_frames(sk,tp,mss_now,TCP_NAGLE_PUSH);+}elseif(skb==sk->sk_send_head)+tcp_push_one(sk,mss_now);+continue;++wait_for_sndbuf:+set_bit(SOCK_NOSPACE,&sk->sk_socket->flags);+wait_for_memory:+if(copied)+tcp_push(sk,tp,0,mss_now,TCP_NAGLE_PUSH);++err=-EAGAIN;+gotodo_error;+}++out:+if(copied)+tcp_push(sk,tp,0,mss_now,tp->nonagle);+returncopied;++do_error:+if(copied)+gotoout;+out_err:+returnsk_stream_error(sk,0,err);+}++/*+*Mustbecalledwithlockedsock.+*/+inttcp_async_recv(structsock*sk,void*dst,size_tlen)+{+structtcp_sock*tp=tcp_sk(sk);+intcopied=0;+u32*seq;+unsignedlongused;+interr;+inttarget;/* Read at least this many bytes */+intcopied_early=0;++TCP_CHECK_TIMER(sk);++err=-ENOTCONN;+if(sk->sk_state==TCP_LISTEN)+gotoout;++seq=&tp->copied_seq;++target=sock_rcvlowat(sk,0,len);++do{+structsk_buff*skb;+u32offset;++/* Are we at urgent data? Stop if we have read anything or have SIGURG pending. */+if(tp->urg_data&&tp->urg_seq==*seq){+if(copied)+break;+}++/* Next get a buffer. */++skb=skb_peek(&sk->sk_receive_queue);+do{+if(!skb)+break;++/* Now that we have two receive queues this+*shouldn'thappen.+*/+if(before(*seq,TCP_SKB_CB(skb)->seq)){+printk(KERN_INFO"async_recv bug: copied %X "+"seq %X\n",*seq,TCP_SKB_CB(skb)->seq);+break;+}+offset=*seq-TCP_SKB_CB(skb)->seq;+if(skb->h.th->syn)+offset--;+if(offset<skb->len)+gotofound_ok_skb;+if(skb->h.th->fin)+gotofound_fin_ok;+skb=skb->next;+}while(skb!=(structsk_buff*)&sk->sk_receive_queue);++if(copied)+break;++if(sock_flag(sk,SOCK_DONE))+break;++if(sk->sk_err){+copied=sock_error(sk);+break;+}++if(sk->sk_shutdown&RCV_SHUTDOWN)+break;++if(sk->sk_state==TCP_CLOSE){+if(!sock_flag(sk,SOCK_DONE)){+/* This occurs when user tries to read+*fromneverconnectedsocket.+*/+copied=-ENOTCONN;+break;+}+break;+}++copied=-EAGAIN;+break;++found_ok_skb:+/* Ok so how much can we use? */+used=skb->len-offset;+if(len<used)+used=len;++/* Do we have urgent data here? */+if(tp->urg_data){+u32urg_offset=tp->urg_seq-*seq;+if(urg_offset<used){+if(!urg_offset){+if(!sock_flag(sk,SOCK_URGINLINE)){+++*seq;+offset++;+used--;+if(!used)+gotoskip_copy;+}+}else+used=urg_offset;+}+}+#ifdef CONFIG_NET_DMA+if(!tp->ucopy.dma_chan&&tp->ucopy.pinned_list)+tp->ucopy.dma_chan=get_softnet_dma();++if(tp->ucopy.dma_chan){+tp->ucopy.dma_cookie=dma_skb_copy_datagram_iovec(+tp->ucopy.dma_chan,skb,offset,+msg->msg_iov,used,+tp->ucopy.pinned_list);++if(tp->ucopy.dma_cookie<0){++printk(KERN_ALERT"dma_cookie < 0\n");++/* Exception. Bailout! */+if(!copied)+copied=-EFAULT;+break;+}+if((offset+used)==skb->len)+copied_early=1;++}else+#endif+{+err=skb_copy_datagram(skb,offset,dst,used);+if(err){+/* Exception. Bailout! */+if(!copied)+copied=-EFAULT;+break;+}+}++*seq+=used;+copied+=used;+len-=used;+dst+=used;++tcp_rcv_space_adjust(sk);++skip_copy:+if(tp->urg_data&&after(tp->copied_seq,tp->urg_seq)){+tp->urg_data=0;+tcp_fast_path_check(sk,tp);+}+if(used+offset<skb->len)+continue;++if(skb->h.th->fin)+gotofound_fin_ok;+sk_eat_skb(sk,skb,copied_early);+continue;++found_fin_ok:+/* Process the FIN. */+++*seq;+sk_eat_skb(sk,skb,copied_early);+break;+}while(len>0);++/* Clean up data we have read: This will do ACK frames. */+tcp_cleanup_rbuf(sk,copied);++TCP_CHECK_TIMER(sk);+returncopied;++out:+TCP_CHECK_TIMER(sk);+returnerr;+}++/**Thisroutinecopiesfromasockstructintotheuserbuffer.**Technicalnote:in2.3weworkon_locked_socket,sothat
Generic event handling mechanism.
I send this patchset for comments and review, it still contains AIO and
aio_sendfile() implementation on top of get_block() abstraction, which was
decided to postpone for a while (it is simpler right now to generate patchset as a whole,
when kevent will be ready for merge, I will generate patchset without AIO stuff).
It does not contain mapped buffer implementation, since it's design is not 100%
completed, I will present that implementation in the third patchset.
Changes from 'take2' patchset:
* split kevent_finish_user() to locked and unlocked variants
* do not use KEVENT_STAT ifdefs, use inline functions instead
* use array of callbacks of each type instead of each kevent callback initialization
* changed name of ukevent guarding lock
* use only one kevent lock in kevent_user for all hash buckets instead of per-bucket locks
* do not use kevent_user_ctl structure instead provide needed arguments as syscall parameters
* various indent cleanups
* mapped buffer (initial) implementation (no userspace yet)
Changes from 'take1' patchset:
- rebased against 2.6.18-git tree
- removed ioctl controlling
- added new syscall kevent_get_events(int fd, unsigned int min_nr, unsigned int max_nr,
unsigned int timeout, void __user *buf, unsigned flags)
- use old syscall kevent_ctl for creation/removing, modification and initial kevent
initialization
- use mutuxes instead of semaphores
- added file descriptor check and return error if provided descriptor does not match
kevent file operations
- various indent fixes
- removed aio_sendfile() declarations.
Thank you.
Signed-off-by: Evgeniy Polyakov <redacted>
poll/select() notifications. Timer notifications.
This patch includes generic poll/select and timer notifications.
kevent_poll works simialr to epoll and has the same issues (callback
is invoked not from internal state machine of the caller, but through
process awake).
Timer notifications can be used for fine grained per-process time
management, since iteractive timers are very inconveniently to use,
and they are limited.
Signed-off-by: Evgeniy Polyakov <redacted>
@@ -0,0 +1,217 @@+/*+*kevent_poll.c+*+*2006Copyright(c)EvgeniyPolyakov<johnpol@2ka.mipt.ru>+*Allrightsreserved.+*+*Thisprogramisfreesoftware;youcanredistributeitand/ormodify+*itunderthetermsoftheGNUGeneralPublicLicenseaspublishedby+*theFreeSoftwareFoundation;eitherversion2oftheLicense,or+*(atyouroption)anylaterversion.+*+*Thisprogramisdistributedinthehopethatitwillbeuseful,+*butWITHOUTANYWARRANTY;withouteventheimpliedwarrantyof+*MERCHANTABILITYorFITNESSFORAPARTICULARPURPOSE.Seethe+*GNUGeneralPublicLicenseformoredetails.+*/++#include<linux/kernel.h>+#include<linux/types.h>+#include<linux/list.h>+#include<linux/slab.h>+#include<linux/spinlock.h>+#include<linux/timer.h>+#include<linux/file.h>+#include<linux/kevent.h>+#include<linux/poll.h>+#include<linux/fs.h>++statickmem_cache_t*kevent_poll_container_cache;+statickmem_cache_t*kevent_poll_priv_cache;++structkevent_poll_ctl+{+structpoll_table_structpt;+structkevent*k;+};++structkevent_poll_wait_container+{+structlist_headcontainer_entry;+wait_queue_head_t*whead;+wait_queue_twait;+structkevent*k;+};++structkevent_poll_private+{+structlist_headcontainer_list;+spinlock_tcontainer_lock;+};++staticintkevent_poll_enqueue(structkevent*k);+staticintkevent_poll_dequeue(structkevent*k);+staticintkevent_poll_callback(structkevent*k);++staticintkevent_poll_wait_callback(wait_queue_t*wait,+unsignedmode,intsync,void*key)+{+structkevent_poll_wait_container*cont=+container_of(wait,structkevent_poll_wait_container,wait);+structkevent*k=cont->k;+structfile*file=k->st->origin;+unsignedlongflags;+u32revents,event;++revents=file->f_op->poll(file,NULL);+spin_lock_irqsave(&k->ulock,flags);+event=k->event.event;+spin_unlock_irqrestore(&k->ulock,flags);++kevent_storage_ready(k->st,NULL,revents);++return0;+}++staticvoidkevent_poll_qproc(structfile*file,wait_queue_head_t*whead,+structpoll_table_struct*poll_table)+{+structkevent*k=+container_of(poll_table,structkevent_poll_ctl,pt)->k;+structkevent_poll_private*priv=k->priv;+structkevent_poll_wait_container*cont;+unsignedlongflags;++cont=kmem_cache_alloc(kevent_poll_container_cache,SLAB_KERNEL);+if(!cont){+kevent_break(k);+return;+}++cont->k=k;+init_waitqueue_func_entry(&cont->wait,kevent_poll_wait_callback);+cont->whead=whead;++spin_lock_irqsave(&priv->container_lock,flags);+list_add_tail(&cont->container_entry,&priv->container_list);+spin_unlock_irqrestore(&priv->container_lock,flags);++add_wait_queue(whead,&cont->wait);+}++staticintkevent_poll_enqueue(structkevent*k)+{+structfile*file;+interr,ready=0;+unsignedintrevents;+structkevent_poll_ctlctl;+structkevent_poll_private*priv;++file=fget(k->event.id.raw[0]);+if(!file)+return-ENODEV;++err=-EINVAL;+if(!file->f_op||!file->f_op->poll)+gotoerr_out_fput;++err=-ENOMEM;+priv=kmem_cache_alloc(kevent_poll_priv_cache,SLAB_KERNEL);+if(!priv)+gotoerr_out_fput;++spin_lock_init(&priv->container_lock);+INIT_LIST_HEAD(&priv->container_list);++k->priv=priv;++ctl.k=k;+init_poll_funcptr(&ctl.pt,&kevent_poll_qproc);++err=kevent_storage_enqueue(&file->st,k);+if(err)+gotoerr_out_free;++revents=file->f_op->poll(file,&ctl.pt);+if(revents&k->event.event){+ready=1;+kevent_poll_dequeue(k);+}++returnready;++err_out_free:+kmem_cache_free(kevent_poll_priv_cache,priv);+err_out_fput:+fput(file);+returnerr;+}++staticintkevent_poll_dequeue(structkevent*k)+{+structfile*file=k->st->origin;+structkevent_poll_private*priv=k->priv;+structkevent_poll_wait_container*w,*n;+unsignedlongflags;++kevent_storage_dequeue(k->st,k);++spin_lock_irqsave(&priv->container_lock,flags);+list_for_each_entry_safe(w,n,&priv->container_list,container_entry){+list_del(&w->container_entry);+remove_wait_queue(w->whead,&w->wait);+kmem_cache_free(kevent_poll_container_cache,w);+}+spin_unlock_irqrestore(&priv->container_lock,flags);++kmem_cache_free(kevent_poll_priv_cache,priv);+k->priv=NULL;++fput(file);++return0;+}++staticintkevent_poll_callback(structkevent*k)+{+structfile*file=k->st->origin;+unsignedintrevents=file->f_op->poll(file,NULL);+return(revents&k->event.event);+}++staticint__initkevent_poll_sys_init(void)+{+structkevent_callbacks*pc=&kevent_registered_callbacks[KEVENT_POLL];++kevent_poll_container_cache=kmem_cache_create("kevent_poll_container_cache",+sizeof(structkevent_poll_wait_container),0,0,NULL,NULL);+if(!kevent_poll_container_cache){+printk(KERN_ERR"Failed to create kevent poll container cache.\n");+return-ENOMEM;+}++kevent_poll_priv_cache=kmem_cache_create("kevent_poll_priv_cache",+sizeof(structkevent_poll_private),0,0,NULL,NULL);+if(!kevent_poll_priv_cache){+printk(KERN_ERR"Failed to create kevent poll private data cache.\n");+kmem_cache_destroy(kevent_poll_container_cache);+kevent_poll_container_cache=NULL;+return-ENOMEM;+}++pc->enqueue=&kevent_poll_enqueue;+pc->dequeue=&kevent_poll_dequeue;+pc->callback=&kevent_poll_callback;++printk(KERN_INFO"Kevent poll()/select() subsystem has been initialized.\n");+return0;+}++staticvoid__exitkevent_poll_sys_fini(void)+{+kmem_cache_destroy(kevent_poll_priv_cache);+kmem_cache_destroy(kevent_poll_container_cache);+}++module_init(kevent_poll_sys_init);+module_exit(kevent_poll_sys_fini);
AIO, aio_sendfile() implementation.
This patch includes asynchronous propagation of file's data into VFS
cache and aio_sendfile() implementation.
Network aio_sendfile() works lazily - it asynchronously populates pages
into the VFS cache (which can be used for various tricks with adaptive
readahead) and then uses usual ->sendfile() callback.
Signed-off-by: Evgeniy Polyakov <redacted>
@@ -165,12 +166,18 @@ #endif}memset(&inode->u,0,sizeof(inode->u));inode->i_mapping=mapping;+#if defined CONFIG_KEVENT+kevent_storage_init(inode,&inode->st);+#endif}returninode;}voiddestroy_inode(structinode*inode){+#if defined CONFIG_KEVENT_INODE || defined CONFIG_KEVENT_SOCKET+kevent_storage_fini(&inode->st);+#endifBUG_ON(inode_has_buffers(inode));security_inode_free(inode);if(inode->i_sb->s_op->destroy_inode)
@@ -546,6 +551,10 @@ #ifdef CONFIG_INOTIFYstructmutexinotify_mutex;/* protects the watches list */#endif+#ifdef CONFIG_KEVENT_INODE+structkevent_storagest;+#endif+unsignedlongi_state;unsignedlongdirtied_when;/* jiffies of first dirtying */
Core files.
This patch includes core kevent files:
- userspace controlling
- kernelspace interfaces
- initialization
- 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 <redacted>
@@ -0,0 +1,277 @@+/*+*kevent.h+*+*2006Copyright(c)EvgeniyPolyakov<johnpol@2ka.mipt.ru>+*Allrightsreserved.+*+*Thisprogramisfreesoftware;youcanredistributeitand/ormodify+*itunderthetermsoftheGNUGeneralPublicLicenseaspublishedby+*theFreeSoftwareFoundation;eitherversion2oftheLicense,or+*(atyouroption)anylaterversion.+*+*Thisprogramisdistributedinthehopethatitwillbeuseful,+*butWITHOUTANYWARRANTY;withouteventheimpliedwarrantyof+*MERCHANTABILITYorFITNESSFORAPARTICULARPURPOSE.Seethe+*GNUGeneralPublicLicenseformoredetails.+*+*YoushouldhavereceivedacopyoftheGNUGeneralPublicLicense+*alongwiththisprogram;ifnot,writetotheFreeSoftware+*Foundation,Inc.,59TemplePlace,Suite330,Boston,MA02111-1307USA+*/++#ifndef __KEVENT_H+#define __KEVENT_H++/*+*Keventrequestflags.+*/++#define KEVENT_REQ_ONESHOT 0x1 /* Process this event only once and then dequeue. */++/*+*Keventreturnflags.+*/+#define KEVENT_RET_BROKEN 0x1 /* Kevent is broken. */+#define KEVENT_RET_DONE 0x2 /* Kevent processing was finished successfully. */++/*+*Keventtypeset.+*/+#define KEVENT_SOCKET 0+#define KEVENT_INODE 1+#define KEVENT_TIMER 2+#define KEVENT_POLL 3+#define KEVENT_NAIO 4+#define KEVENT_AIO 5+#define KEVENT_MAX 6++/*+*Per-typeeventsets.+*Numberofper-eventsetsshouldbeexactlyasnumberofkeventtypes.+*/++/*+*Timerevents.+*/+#define KEVENT_TIMER_FIRED 0x1++/*+*Socket/networkasynchronousIOevents.+*/+#define KEVENT_SOCKET_RECV 0x1+#define KEVENT_SOCKET_ACCEPT 0x2+#define KEVENT_SOCKET_SEND 0x4++/*+*Inodeevents.+*/+#define KEVENT_INODE_CREATE 0x1+#define KEVENT_INODE_REMOVE 0x2++/*+*Pollevents.+*/+#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++#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++/*+*AsynchronousIOevents.+*/+#define KEVENT_AIO_BIO 0x1++#define KEVENT_MASK_ALL 0xffffffff /* Mask of all possible event values. */+#define KEVENT_MASK_EMPTY 0x0 /* Empty mask of ready events. */++structkevent_id+{+__u32raw[2];+};++structukevent+{+structkevent_idid;/* Id of this request, e.g. socket number, file descriptor and so on... */+__u32type;/* Event type, e.g. KEVENT_SOCK, KEVENT_INODE, KEVENT_TIMER and so on... */+__u32event;/* Event itself, e.g. SOCK_ACCEPT, INODE_CREATED, TIMER_FIRED... */+__u32req_flags;/* Per-event request flags */+__u32ret_flags;/* Per-event return flags */+__u32ret_data[2];/* Event return data. Event originator fills it with anything it likes. */+union{+__u32user[2];/* User's data. It is not used, just copied to/from user. */+void*ptr;+};+};++#define KEVENT_CTL_ADD 0+#define KEVENT_CTL_REMOVE 1+#define KEVENT_CTL_MODIFY 2+#define KEVENT_CTL_INIT 3++#ifdef __KERNEL__++#include<linux/types.h>+#include<linux/list.h>+#include<linux/spinlock.h>+#include<linux/mutex.h>+#include<linux/wait.h>+#include<linux/kevent_storage.h>++#define KEVENT_MAX_EVENTS 4096+#define KEVENT_MIN_BUFFS_ALLOC 3++structinode;+structdentry;+structsock;++structkevent;+structkevent_storage;+typedefint(*kevent_callback_t)(structkevent*);++/* @callback is called each time new event has been caught. */+/* @enqueue is called each time new event is queued. */+/* @dequeue is called each time event is dequeued. */++structkevent_callbacks{+kevent_callback_tcallback,enqueue,dequeue;+};++structkevent+{+structukeventevent;+spinlock_tulock;/* This lock protects ukevent manipulations, e.g. ret_flags changes. */++structlist_headkevent_entry;/* Entry of user's queue. */+structlist_headstorage_entry;/* Entry of origin's queue. */+structlist_headready_entry;/* Entry of user's ready. */++structkevent_user*user;/* User who requested this kevent. */+structkevent_storage*st;/* Kevent container. */++structkevent_callbackscallbacks;++void*priv;/* Private data for different storages. +*poll()/selectstoragehasalistofwait_queue_tcontainers+*foreach->poll(){poll_wait()'}here.+*/+};++externstructkevent_callbackskevent_registered_callbacks[];++#define KEVENT_HASH_MASK 0xff++structkevent_user+{+structlist_headkevent_list[KEVENT_HASH_MASK+1];+spinlock_tkevent_lock;+unsignedintkevent_num;/* Number of queued kevents. */++structlist_headready_list;/* List of ready kevents. */+unsignedintready_num;/* Number of ready kevents. */+spinlock_tready_lock;/* Protects all manipulations with ready queue. */++unsignedintmax_ready_num;/* Requested number of kevents. */++structmutexctl_mutex;/* Protects against simultaneous kevent_user control manipulations. */+structmutexwait_mutex;/* Protects against simultaneous kevent_user waits. */+wait_queue_head_twait;/* Wait until some events are ready. */++atomic_trefcnt;/* Reference counter, increased for each new kevent. */++unsignedlong*pring;/* Array of pages forming mapped ring buffer */++#ifdef CONFIG_KEVENT_USER_STAT+unsignedlongim_num;+unsignedlongwait_num;+unsignedlongtotal;+#endif+};++structkevent*kevent_alloc(gfp_tmask);+voidkevent_free(structkevent*k);+intkevent_enqueue(structkevent*k);+intkevent_dequeue(structkevent*k);+intkevent_init(structkevent*k);+voidkevent_requeue(structkevent*k);+intkevent_break(structkevent*k);++voidkevent_user_ring_add_event(structkevent*k);++voidkevent_storage_ready(structkevent_storage*st,+kevent_callback_tready_callback,u32event);+intkevent_storage_init(void*origin,structkevent_storage*st);+voidkevent_storage_fini(structkevent_storage*st);+intkevent_storage_enqueue(structkevent_storage*st,structkevent*k);+voidkevent_storage_dequeue(structkevent_storage*st,structkevent*k);++intkevent_user_add_ukevent(structukevent*uk,structkevent_user*u);++#ifdef CONFIG_KEVENT_INODE+voidkevent_inode_notify(structinode*inode,u32event);+voidkevent_inode_notify_parent(structdentry*dentry,u32event);+voidkevent_inode_remove(structinode*inode);+#else+staticinlinevoidkevent_inode_notify(structinode*inode,u32event)+{+}+staticinlinevoidkevent_inode_notify_parent(structdentry*dentry,u32event)+{+}+staticinlinevoidkevent_inode_remove(structinode*inode)+{+}+#endif /* CONFIG_KEVENT_INODE */+#ifdef CONFIG_KEVENT_SOCKET++voidkevent_socket_notify(structsock*sock,u32event);+intkevent_socket_dequeue(structkevent*k);+intkevent_socket_enqueue(structkevent*k);+#define sock_async(__sk) sock_flag(__sk, SOCK_ASYNC)+#else+staticinlinevoidkevent_socket_notify(structsock*sock,u32event)+{+}+#define sock_async(__sk) ({ (void)__sk; 0; })+#endif++#ifdef CONFIG_KEVENT_USER_STAT+staticinlinevoidkevent_user_stat_init(structkevent_user*u)+{+u->wait_num=u->im_num=u->total=0;+}+staticinlinevoidkevent_user_stat_print(structkevent_user*u)+{+pr_debug("%s: u=%p, wait=%lu, immediately=%lu, total=%lu.\n",+__func__,u,u->wait_num,u->im_num,u->total);+}+staticinlinevoidkevent_user_stat_increase_im(structkevent_user*u)+{+u->im_num++;+}+staticinlinevoidkevent_user_stat_increase_wait(structkevent_user*u)+{+u->wait_num++;+}+staticinlinevoidkevent_user_stat_increase_total(structkevent_user*u)+{+u->total++;+}+#else+#define kevent_user_stat_print(u) ({ (void) u;})+#define kevent_user_stat_init(u) ({ (void) u;})+#define kevent_user_stat_increase_im(u) ({ (void) u;})+#define kevent_user_stat_increase_wait(u) ({ (void) u;})+#define kevent_user_stat_increase_total(u) ({ (void) u;})+#endif++#endif /* __KERNEL__ */+#endif /* __KEVENT_H */
@@ -0,0 +1,12 @@+#ifndef __KEVENT_STORAGE_H+#define __KEVENT_STORAGE_H++structkevent_storage+{+void*origin;/* Originator's pointer, e.g. struct sock or struct file. Can be NULL. */+structlist_headlist;/* List of queued kevents. */+unsignedintqlen;/* Number of queued kevents. */+spinlock_tlock;/* Protects users queue. */+};++#endif /* __KEVENT_STORAGE_H */
@@ -0,0 +1,248 @@+/*+*kevent.c+*+*2006Copyright(c)EvgeniyPolyakov<johnpol@2ka.mipt.ru>+*Allrightsreserved.+*+*Thisprogramisfreesoftware;youcanredistributeitand/ormodify+*itunderthetermsoftheGNUGeneralPublicLicenseaspublishedby+*theFreeSoftwareFoundation;eitherversion2oftheLicense,or+*(atyouroption)anylaterversion.+*+*Thisprogramisdistributedinthehopethatitwillbeuseful,+*butWITHOUTANYWARRANTY;withouteventheimpliedwarrantyof+*MERCHANTABILITYorFITNESSFORAPARTICULARPURPOSE.Seethe+*GNUGeneralPublicLicenseformoredetails.+*+*YoushouldhavereceivedacopyoftheGNUGeneralPublicLicense+*alongwiththisprogram;ifnot,writetotheFreeSoftware+*Foundation,Inc.,59TemplePlace,Suite330,Boston,MA02111-1307USA+*/++#include<linux/kernel.h>+#include<linux/types.h>+#include<linux/list.h>+#include<linux/slab.h>+#include<linux/spinlock.h>+#include<linux/mempool.h>+#include<linux/sched.h>+#include<linux/wait.h>+#include<linux/kevent.h>++statickmem_cache_t*kevent_cache;++/*+*Attemptstoaddaneventintoappropriateorigin'squeue.+*Returnspositivevalueifthiseventisreadyimmediately,+*negativevalueincaseoferrorandzeroifeventhasbeenqueued.+*->enqueue()callbackmustincreaseorigin'sreferencecounter.+*/+intkevent_enqueue(structkevent*k)+{+if(k->event.type>=KEVENT_MAX)+return-E2BIG;++if(!k->callbacks.enqueue){+kevent_break(k);+return-EINVAL;+}++returnk->callbacks.enqueue(k);+}++/*+*Removeeventfromtheappropriatequeue.+*->dequeue()callbackmustdecreaseorigin'sreferencecounter.+*/+intkevent_dequeue(structkevent*k)+{+if(k->event.type>=KEVENT_MAX)+return-E2BIG;++if(!k->callbacks.dequeue){+kevent_break(k);+return-EINVAL;+}++returnk->callbacks.dequeue(k);+}++intkevent_break(structkevent*k)+{+unsignedlongflags;++spin_lock_irqsave(&k->ulock,flags);+k->event.ret_flags|=KEVENT_RET_BROKEN;+spin_unlock_irqrestore(&k->ulock,flags);+return0;+}++structkevent_callbackskevent_registered_callbacks[KEVENT_MAX];++/*+*Mustbecalledbeforeeventisgoingtobeaddedintosomeorigin'squeue.+*Initializes->enqueue(),->dequeue()and->callback()callbacks.+*Iffailed,keventshouldnotbeusedorkevent_enqueue()willfailtoadd+*thiskeventintoorigin'squeuewithsetting+*KEVENT_RET_BROKENflaginkevent->event.ret_flags.+*/+intkevent_init(structkevent*k)+{+spin_lock_init(&k->ulock);+k->kevent_entry.next=LIST_POISON1;+k->storage_entry.next=LIST_POISON1;+k->ready_entry.next=LIST_POISON1;++if(k->event.type>=KEVENT_MAX)+return-E2BIG;++k->callbacks=kevent_registered_callbacks[k->event.type];+if(!k->callbacks.callback){+kevent_break(k);+return-EINVAL;+}++return0;+}++/*+*Calledfrom->enqueue()callbackwhenreferencecounterforgiven+*origin(socket,inode...)hasbeenincreased.+*/+intkevent_storage_enqueue(structkevent_storage*st,structkevent*k)+{+unsignedlongflags;++k->st=st;+spin_lock_irqsave(&st->lock,flags);+list_add_tail(&k->storage_entry,&st->list);+st->qlen++;+spin_unlock_irqrestore(&st->lock,flags);+return0;+}++/*+*Dequeuekeventfromorigin'squeue.+*Itdoesnotdecreaseorigin'sreferencecounterinanyway+*andmustbecalledbeforeit,sostorageitselfmustbevalid.+*Itiscalledfrom->dequeue()callback.+*/+voidkevent_storage_dequeue(structkevent_storage*st,structkevent*k)+{+unsignedlongflags;++spin_lock_irqsave(&st->lock,flags);+if(k->storage_entry.next!=LIST_POISON1){+list_del(&k->storage_entry);+st->qlen--;+}+spin_unlock_irqrestore(&st->lock,flags);+}++staticvoid__kevent_requeue(structkevent*k,u32event)+{+interr,rem=0;+unsignedlongflags;++err=k->callbacks.callback(k);++spin_lock_irqsave(&k->ulock,flags);+if(err>0){+k->event.ret_flags|=KEVENT_RET_DONE;+}elseif(err<0){+k->event.ret_flags|=KEVENT_RET_BROKEN;+k->event.ret_flags|=KEVENT_RET_DONE;+}+rem=(k->event.req_flags&KEVENT_REQ_ONESHOT);+if(!err)+err=(k->event.ret_flags&(KEVENT_RET_BROKEN|KEVENT_RET_DONE));+spin_unlock_irqrestore(&k->ulock,flags);++if(err){+if(rem){+list_del(&k->storage_entry);+k->st->qlen--;+}++spin_lock_irqsave(&k->user->ready_lock,flags);+if(k->ready_entry.next==LIST_POISON1){+kevent_user_ring_add_event(k);+list_add_tail(&k->ready_entry,&k->user->ready_list);+k->user->ready_num++;+}+spin_unlock_irqrestore(&k->user->ready_lock,flags);+wake_up(&k->user->wait);+}+}++voidkevent_requeue(structkevent*k)+{+unsignedlongflags;++spin_lock_irqsave(&k->st->lock,flags);+__kevent_requeue(k,0);+spin_unlock_irqrestore(&k->st->lock,flags);+}++/*+*Calledeachtimesomeactivityinorigin(socket,inode...)isnoticed.+*/+voidkevent_storage_ready(structkevent_storage*st,+kevent_callback_tready_callback,u32event)+{+structkevent*k,*n;++spin_lock(&st->lock);+list_for_each_entry_safe(k,n,&st->list,storage_entry){+if(ready_callback)+ready_callback(k);++if(event&k->event.event)+__kevent_requeue(k,event);+}+spin_unlock(&st->lock);+}++intkevent_storage_init(void*origin,structkevent_storage*st)+{+spin_lock_init(&st->lock);+st->origin=origin;+st->qlen=0;+INIT_LIST_HEAD(&st->list);+return0;+}++voidkevent_storage_fini(structkevent_storage*st)+{+kevent_storage_ready(st,kevent_break,KEVENT_MASK_ALL);+}++structkevent*kevent_alloc(gfp_tmask)+{+returnkmem_cache_alloc(kevent_cache,mask);+}++voidkevent_free(structkevent*k)+{+kmem_cache_free(kevent_cache,k);+}++staticint__initkevent_sys_init(void)+{+inti;++kevent_cache=kmem_cache_create("kevent_cache",+sizeof(structkevent),0,0,NULL,NULL);+if(!kevent_cache)+panic("kevent: Unable to create a cache.\n");++for(i=0;i<ARRAY_SIZE(kevent_registered_callbacks);++i){+structkevent_callbacks*c=&kevent_registered_callbacks[i];++c->callback=c->enqueue=c->dequeue=NULL;+}++return0;+}++late_initcall(kevent_sys_init);
@@ -0,0 +1,876 @@+/*+*kevent_user.c+*+*2006Copyright(c)EvgeniyPolyakov<johnpol@2ka.mipt.ru>+*Allrightsreserved.+*+*Thisprogramisfreesoftware;youcanredistributeitand/ormodify+*itunderthetermsoftheGNUGeneralPublicLicenseaspublishedby+*theFreeSoftwareFoundation;eitherversion2oftheLicense,or+*(atyouroption)anylaterversion.+*+*Thisprogramisdistributedinthehopethatitwillbeuseful,+*butWITHOUTANYWARRANTY;withouteventheimpliedwarrantyof+*MERCHANTABILITYorFITNESSFORAPARTICULARPURPOSE.Seethe+*GNUGeneralPublicLicenseformoredetails.+*+*YoushouldhavereceivedacopyoftheGNUGeneralPublicLicense+*alongwiththisprogram;ifnot,writetotheFreeSoftware+*Foundation,Inc.,59TemplePlace,Suite330,Boston,MA02111-1307USA+*/++#include<linux/kernel.h>+#include<linux/module.h>+#include<linux/types.h>+#include<linux/list.h>+#include<linux/slab.h>+#include<linux/spinlock.h>+#include<linux/fs.h>+#include<linux/file.h>+#include<linux/mount.h>+#include<linux/device.h>+#include<linux/poll.h>+#include<linux/kevent.h>+#include<linux/jhash.h>+#include<asm/io.h>++staticstructclass*kevent_user_class;+staticcharkevent_name[]="kevent";+staticintkevent_user_major;++staticintkevent_user_open(structinode*,structfile*);+staticintkevent_user_release(structinode*,structfile*);+staticunsignedintkevent_user_poll(structfile*,structpoll_table_struct*);+staticintkevnet_user_mmap(structfile*,structvm_area_struct*);++staticstructfile_operationskevent_user_fops={+.mmap=kevnet_user_mmap,+.open=kevent_user_open,+.release=kevent_user_release,+.poll=kevent_user_poll,+.owner=THIS_MODULE,+};++staticintkevent_get_sb(structfile_system_type*fs_type,+intflags,constchar*dev_name,void*data,structvfsmount*mnt)+{+/* So original magic... */+returnget_sb_pseudo(fs_type,kevent_name,NULL,0xabcdef,mnt);+}++staticstructfile_system_typekevent_fs_type={+.name=kevent_name,+.get_sb=kevent_get_sb,+.kill_sb=kill_anon_super,+};++staticstructvfsmount*kevent_mnt;++staticunsignedintkevent_user_poll(structfile*file,structpoll_table_struct*wait)+{+structkevent_user*u=file->private_data;+unsignedintmask;++poll_wait(file,&u->wait,wait);+mask=0;++if(u->ready_num)+mask|=POLLIN|POLLRDNORM;++returnmask;+}++staticinlinevoidkevent_user_ring_set(structkevent_user*u,unsignedintnum)+{+unsignedint*idx;++idx=(unsignedint*)u->pring[0];+idx[0]=num;+}++/*+*Notethatkeventsdoesnotexactlyfillthepage(eachukeventis40bytes),+*sowereuse4bytesatthebeginingofthefirstpagetostoreindex.+*Takethatintoaccountifyouwanttochangesizeofstructukevent.+*/+#define KEVENTS_ON_PAGE PAGE_SIZE/sizeof(struct ukevent)++/*+*Calledunderkevent_user->ready_lock,soupdatesarealwaysprotected.+*/+voidkevent_user_ring_add_event(structkevent*k)+{+unsignedint*idx_ptr,idx,pidx,off;+structukevent*ukev;++idx_ptr=(unsignedint*)k->user->pring[0];+idx=idx_ptr[0];++pidx=idx/KEVENTS_ON_PAGE;+off=idx%KEVENTS_ON_PAGE;++if(pidx==0)+ukev=(structukevent*)(k->user->pring[pidx]+sizeof(unsignedint));+else+ukev=(structukevent*)(k->user->pring[pidx]);++memcpy(&ukev[off],&k->event,sizeof(structukevent));++idx++;+if(idx>=KEVENT_MAX_EVENTS)+idx=0;++idx_ptr[0]=idx;+}++staticintkevent_user_ring_init(structkevent_user*u)+{+inti,pnum;++pnum=ALIGN(KEVENT_MAX_EVENTS*sizeof(structukevent)+sizeof(unsignedint),PAGE_SIZE)/PAGE_SIZE;++u->pring=kmalloc(pnum*sizeof(unsignedlong),GFP_KERNEL);+if(!u->pring)+return-ENOMEM;++for(i=0;i<pnum;++i){+u->pring[i]=__get_free_page(GFP_KERNEL);+if(!u->pring)+break;+}++if(i!=pnum){+pnum=i;+gotoerr_out_free;+}++kevent_user_ring_set(u,0);++return0;++err_out_free:+for(i=0;i<pnum;++i)+free_page(u->pring[i]);++kfree(u->pring);++return-ENOMEM;+}++staticvoidkevent_user_ring_fini(structkevent_user*u)+{+inti,pnum;++pnum=ALIGN(KEVENT_MAX_EVENTS*sizeof(structukevent)+sizeof(unsignedint),PAGE_SIZE)/PAGE_SIZE;++for(i=0;i<pnum;++i)+free_page(u->pring[i]);++kfree(u->pring);+}++staticstructkevent_user*kevent_user_alloc(void)+{+structkevent_user*u;+inti;++u=kzalloc(sizeof(structkevent_user),GFP_KERNEL);+if(!u)+returnNULL;++INIT_LIST_HEAD(&u->ready_list);+spin_lock_init(&u->ready_lock);+u->ready_num=0;+kevent_user_stat_init(u);+spin_lock_init(&u->kevent_lock);+for(i=0;i<ARRAY_SIZE(u->kevent_list);++i)+INIT_LIST_HEAD(&u->kevent_list[i]);+u->kevent_num=0;++mutex_init(&u->ctl_mutex);+mutex_init(&u->wait_mutex);+init_waitqueue_head(&u->wait);+u->max_ready_num=0;++atomic_set(&u->refcnt,1);++if(kevent_user_ring_init(u)){+kfree(u);+u=NULL;+}++returnu;+}++staticintkevent_user_open(structinode*inode,structfile*file)+{+structkevent_user*u=kevent_user_alloc();++if(!u)+return-ENOMEM;++file->private_data=u;++return0;+}++staticinlinevoidkevent_user_get(structkevent_user*u)+{+atomic_inc(&u->refcnt);+}++staticinlinevoidkevent_user_put(structkevent_user*u)+{+if(atomic_dec_and_test(&u->refcnt)){+kevent_user_stat_print(u);+kevent_user_ring_fini(u);+kfree(u);+}+}++staticintkevnet_user_mmap(structfile*file,structvm_area_struct*vma)+{+size_tsize=vma->vm_end-vma->vm_start,psize;+intpnum=size/PAGE_SIZE,i;+unsignedlongstart=vma->vm_start;+structkevent_user*u=file->private_data;++psize=ALIGN(KEVENT_MAX_EVENTS*sizeof(structukevent)+sizeof(unsignedint),PAGE_SIZE);++if(size+vma->vm_pgoff*PAGE_SIZE!=psize)+return-EINVAL;++if(vma->vm_flags&VM_WRITE)+return-EPERM;++vma->vm_page_prot=pgprot_noncached(vma->vm_page_prot);++for(i=0;i<pnum;++i){+if(remap_pfn_range(vma,start,virt_to_phys((void*)u->pring[i+vma->vm_pgoff]),PAGE_SIZE,+vma->vm_page_prot))+return-EAGAIN;+start+=PAGE_SIZE;+}++return0;+}++#if 0+staticinlineunsignedintkevent_user_hash(structukevent*uk)+{+unsignedinth=(uk->user[0]^uk->user[1])^(uk->id.raw[0]^uk->id.raw[1]);++h=(((h>>16)&0xffff)^(h&0xffff))&0xffff;+h=(((h>>8)&0xff)^(h&0xff))&KEVENT_HASH_MASK;++returnh;+}+#else+staticinlineunsignedintkevent_user_hash(structukevent*uk)+{+returnjhash_1word(uk->id.raw[0],0)&KEVENT_HASH_MASK;+}+#endif++staticvoidkevent_finish_user_complete(structkevent*k,intdeq)+{+structkevent_user*u=k->user;+unsignedlongflags;++if(deq)+kevent_dequeue(k);++spin_lock_irqsave(&u->ready_lock,flags);+if(k->ready_entry.next!=LIST_POISON1){+list_del(&k->ready_entry);+u->ready_num--;+}+spin_unlock_irqrestore(&u->ready_lock,flags);++kevent_user_put(u);+kevent_free(k);+}++staticvoid__kevent_finish_user(structkevent*k,intdeq)+{+structkevent_user*u=k->user;++list_del(&k->kevent_entry);+u->kevent_num--;+kevent_finish_user_complete(k,deq);+}++/*+*Removekeventfromuser'slistofallevents,+*dequeueitfromstorageanddecreaseuser'sreferencecounter,+*sincethiskeventdoesnotexistanymore.Thatiswhyitisfreedhere.+*/+staticvoidkevent_finish_user(structkevent*k,intdeq)+{+structkevent_user*u=k->user;+unsignedlongflags;++spin_lock_irqsave(&u->kevent_lock,flags);+list_del(&k->kevent_entry);+u->kevent_num--;+spin_unlock_irqrestore(&u->kevent_lock,flags);+kevent_finish_user_complete(k,deq);+}++/*+*Dequeueoneentryfromuser'sreadyqueue.+*/++staticstructkevent*kqueue_dequeue_ready(structkevent_user*u)+{+unsignedlongflags;+structkevent*k=NULL;++spin_lock_irqsave(&u->ready_lock,flags);+if(u->ready_num&&!list_empty(&u->ready_list)){+k=list_entry(u->ready_list.next,structkevent,ready_entry);+list_del(&k->ready_entry);+u->ready_num--;+}+spin_unlock_irqrestore(&u->ready_lock,flags);++returnk;+}++staticstructkevent*__kevent_search(structlist_head*head,structukevent*uk,+structkevent_user*u)+{+structkevent*k;+intfound=0;++list_for_each_entry(k,head,kevent_entry){+spin_lock(&k->ulock);+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->ulock);+break;+}+spin_unlock(&k->ulock);+}++return(found)?k:NULL;+}++staticintkevent_modify(structukevent*uk,structkevent_user*u)+{+structkevent*k;+unsignedinthash=kevent_user_hash(uk);+interr=-ENODEV;+unsignedlongflags;++spin_lock_irqsave(&u->kevent_lock,flags);+k=__kevent_search(&u->kevent_list[hash],uk,u);+if(k){+spin_lock(&k->ulock);+k->event.event=uk->event;+k->event.req_flags=uk->req_flags;+k->event.ret_flags=0;+spin_unlock(&k->ulock);+kevent_requeue(k);+err=0;+}+spin_unlock_irqrestore(&u->kevent_lock,flags);++returnerr;+}++staticintkevent_remove(structukevent*uk,structkevent_user*u)+{+interr=-ENODEV;+structkevent*k;+unsignedinthash=kevent_user_hash(uk);+unsignedlongflags;++spin_lock_irqsave(&u->kevent_lock,flags);+k=__kevent_search(&u->kevent_list[hash],uk,u);+if(k){+__kevent_finish_user(k,1);+err=0;+}+spin_unlock_irqrestore(&u->kevent_lock,flags);++returnerr;+}++/*+*Nonewentrycanbeaddedorremovedfromanylistatthispoint.+*Itisnotpermittedtocall->ioctl()and->release()inparallel.+*/+staticintkevent_user_release(structinode*inode,structfile*file)+{+structkevent_user*u=file->private_data;+structkevent*k,*n;+inti;++for(i=0;i<KEVENT_HASH_MASK+1;++i){+list_for_each_entry_safe(k,n,&u->kevent_list[i],kevent_entry)+kevent_finish_user(k,1);+}++kevent_user_put(u);+file->private_data=NULL;++return0;+}++staticstructukevent*kevent_get_user(unsignedintnum,void__user*arg)+{+structukevent*ukev;++ukev=kmalloc(sizeof(structukevent)*num,GFP_KERNEL);+if(!ukev)+returnNULL;++if(copy_from_user(arg,ukev,sizeof(structukevent)*num)){+kfree(ukev);+returnNULL;+}++returnukev;+}++staticintkevent_user_ctl_modify(structkevent_user*u,unsignedintnum,void__user*arg)+{+interr=0,i;+structukeventuk;++mutex_lock(&u->ctl_mutex);++if(num>KEVENT_MIN_BUFFS_ALLOC){+structukevent*ukev;++ukev=kevent_get_user(num,arg);+if(ukev){+for(i=0;i<num;++i){+if(kevent_modify(&ukev[i],u))+ukev[i].ret_flags|=KEVENT_RET_BROKEN;+ukev[i].ret_flags|=KEVENT_RET_DONE;+}+if(copy_to_user(arg,ukev,num*sizeof(structukevent)))+err=-EINVAL;+kfree(ukev);+gotoout;+}+}++for(i=0;i<num;++i){+if(copy_from_user(&uk,arg,sizeof(structukevent))){+err=-EINVAL;+break;+}++if(kevent_modify(&uk,u))+uk.ret_flags|=KEVENT_RET_BROKEN;+uk.ret_flags|=KEVENT_RET_DONE;++if(copy_to_user(arg,&uk,sizeof(structukevent))){+err=-EINVAL;+break;+}++arg+=sizeof(structukevent);+}+out:+mutex_unlock(&u->ctl_mutex);++returnerr;+}++staticintkevent_user_ctl_remove(structkevent_user*u,unsignedintnum,void__user*arg)+{+interr=0,i;+structukeventuk;++mutex_lock(&u->ctl_mutex);++if(num>KEVENT_MIN_BUFFS_ALLOC){+structukevent*ukev;++ukev=kevent_get_user(num,arg);+if(ukev){+for(i=0;i<num;++i){+if(kevent_remove(&ukev[i],u))+ukev[i].ret_flags|=KEVENT_RET_BROKEN;+ukev[i].ret_flags|=KEVENT_RET_DONE;+}+if(copy_to_user(arg,ukev,num*sizeof(structukevent)))+err=-EINVAL;+kfree(ukev);+gotoout;+}+}++for(i=0;i<num;++i){+if(copy_from_user(&uk,arg,sizeof(structukevent))){+err=-EINVAL;+break;+}++if(kevent_remove(&uk,u))+uk.ret_flags|=KEVENT_RET_BROKEN;++uk.ret_flags|=KEVENT_RET_DONE;++if(copy_to_user(arg,&uk,sizeof(structukevent))){+err=-EINVAL;+break;+}++arg+=sizeof(structukevent);+}+out:+mutex_unlock(&u->ctl_mutex);++returnerr;+}++staticvoidkevent_user_enqueue(structkevent_user*u,structkevent*k)+{+unsignedlongflags;+unsignedinthash=kevent_user_hash(&k->event);++spin_lock_irqsave(&u->kevent_lock,flags);+list_add_tail(&k->kevent_entry,&u->kevent_list[hash]);+u->kevent_num++;+kevent_user_get(u);+spin_unlock_irqrestore(&u->kevent_lock,flags);+}++intkevent_user_add_ukevent(structukevent*uk,structkevent_user*u)+{+structkevent*k;+interr;++k=kevent_alloc(GFP_KERNEL);+if(!k){+err=-ENOMEM;+gotoerr_out_exit;+}++memcpy(&k->event,uk,sizeof(structukevent));++k->event.ret_flags=0;++err=kevent_init(k);+if(err){+kevent_free(k);+gotoerr_out_exit;+}+k->user=u;+kevent_user_stat_increase_total(u);+kevent_user_enqueue(u,k);++err=kevent_enqueue(k);+if(err){+memcpy(uk,&k->event,sizeof(structukevent));+if(err<0)+uk->ret_flags|=KEVENT_RET_BROKEN;+uk->ret_flags|=KEVENT_RET_DONE;+kevent_finish_user(k,0);+}++err_out_exit:+returnerr;+}++/*+*Copyallukeventsfromuserspace,allocatekeventforeachone+*andaddthemintoappropriatekevent_storages,+*e.g.sockets,inodesandsoon...+*Ifsomethinggoeswrong,alleventswillbedequeuedand+*negativeerrorwillbereturned.+*Onsuccessnumberoffinishedeventsisreturnedand+*Arrayoffinishedevents(structukevent)willbeplacedbehind+*kevent_user_controlstructure.Usermustrunthroughthatarrayandcheck+*ret_flagsfieldofeachukeventstructuretodetermineifitisfiredorfailedevent.+*/+staticintkevent_user_ctl_add(structkevent_user*u,unsignedintnum,void__user*arg)+{+interr,cerr=0,knum=0,rnum=0,i;+void__user*orig=arg;+structukeventuk;++mutex_lock(&u->ctl_mutex);++err=-ENFILE;+if(u->kevent_num+num>=KEVENT_MAX_EVENTS)+gotoout_remove;++if(num>KEVENT_MIN_BUFFS_ALLOC){+structukevent*ukev;++ukev=kevent_get_user(num,arg);+if(ukev){+for(i=0;i<num;++i){+err=kevent_user_add_ukevent(&ukev[i],u);+if(err){+kevent_user_stat_increase_im(u);+if(i!=rnum)+memcpy(&ukev[rnum],&ukev[i],sizeof(structukevent));+rnum++;+}else+knum++;+}+if(copy_to_user(orig,ukev,rnum*sizeof(structukevent)))+cerr=-EINVAL;+kfree(ukev);+gotoout_setup;+}+}++for(i=0;i<num;++i){+if(copy_from_user(&uk,arg,sizeof(structukevent))){+cerr=-EINVAL;+break;+}+arg+=sizeof(structukevent);++err=kevent_user_add_ukevent(&uk,u);+if(err){+kevent_user_stat_increase_im(u);+if(copy_to_user(orig,&uk,sizeof(structukevent))){+cerr=-EINVAL;+break;+}+orig+=sizeof(structukevent);+rnum++;+}else+knum++;+}++out_setup:+if(cerr<0){+err=cerr;+gotoout_remove;+}++err=rnum;+out_remove:+mutex_unlock(&u->ctl_mutex);++returnerr;+}++/*+*Innonblockingmodeitreturnsasmanyeventsaspossible,butnotmorethan@max_nr.+*Inblockingmodeitwaitsuntiltimeoutorifatleast@min_nreventsareready,+*iftimeoutiszero,thanitwaitsnomorethan1secondorifatleastoneevent+*isready.+*/+staticintkevent_user_wait(structfile*file,structkevent_user*u,+unsignedintmin_nr,unsignedintmax_nr,unsignedinttimeout,+void__user*buf)+{+structkevent*k;+intcerr=0,num=0;++if(!(file->f_flags&O_NONBLOCK)){+if(timeout)+wait_event_interruptible_timeout(u->wait,+u->ready_num>=min_nr,msecs_to_jiffies(timeout));+else+wait_event_interruptible_timeout(u->wait,+u->ready_num>0,msecs_to_jiffies(1000));+}++mutex_lock(&u->ctl_mutex);+while(num<max_nr&&((k=kqueue_dequeue_ready(u))!=NULL)){+if(copy_to_user(buf+num*sizeof(structukevent),+&k->event,sizeof(structukevent))){+cerr=-EINVAL;+break;+}++/*+*Ifitisone-shotkevent,ithasbeenremovedalreadyfrom+*origin'squeue,sowecaneasilyfreeithere.+*/+if(k->event.req_flags&KEVENT_REQ_ONESHOT)+kevent_finish_user(k,1);+++num;+kevent_user_stat_increase_wait(u);+}+mutex_unlock(&u->ctl_mutex);++return(cerr)?cerr:num;+}++staticintkevent_ctl_init(void)+{+structkevent_user*u;+structfile*file;+intfd,ret;++fd=get_unused_fd();+if(fd<0)+returnfd;++file=get_empty_filp();+if(!file){+ret=-ENFILE;+gotoout_put_fd;+}++u=kevent_user_alloc();+if(unlikely(!u)){+ret=-ENOMEM;+gotoout_put_file;+}++file->f_op=&kevent_user_fops;+file->f_vfsmnt=mntget(kevent_mnt);+file->f_dentry=dget(kevent_mnt->mnt_root);+file->f_mapping=file->f_dentry->d_inode->i_mapping;+file->f_mode=FMODE_READ;+file->f_flags=O_RDONLY;+file->private_data=u;++fd_install(fd,file);++returnfd;++out_put_file:+put_filp(file);+out_put_fd:+put_unused_fd(fd);+returnret;+}++staticintkevent_ctl_process(structfile*file,unsignedintcmd,unsignedintnum,void__user*arg)+{+interr;+structkevent_user*u=file->private_data;++if(!u)+return-EINVAL;++switch(cmd){+caseKEVENT_CTL_ADD:+err=kevent_user_ctl_add(u,num,arg);+break;+caseKEVENT_CTL_REMOVE:+err=kevent_user_ctl_remove(u,num,arg);+break;+caseKEVENT_CTL_MODIFY:+err=kevent_user_ctl_modify(u,num,arg);+break;+default:+err=-EINVAL;+break;+}++returnerr;+}++asmlinkagelongsys_kevent_get_events(intctl_fd,unsignedintmin_nr,unsignedintmax_nr,+unsignedinttimeout,void__user*buf,unsignedflags)+{+interr=-EINVAL,fput_needed;+structfile*file;+structkevent_user*u;++file=fget_light(ctl_fd,&fput_needed);+if(!file)+return-ENODEV;++if(file->f_op!=&kevent_user_fops)+gotoout_fput;+u=file->private_data;++err=kevent_user_wait(file,u,min_nr,max_nr,timeout,buf);+out_fput:+fput_light(file,fput_needed);+returnerr;+}++asmlinkagelongsys_kevent_ctl(intfd,unsignedintcmd,unsignedintnum,void__user*arg)+{+interr=-EINVAL,fput_needed;+structfile*file;++if(cmd==KEVENT_CTL_INIT)+returnkevent_ctl_init();++file=fget_light(fd,&fput_needed);+if(!file)+return-ENODEV;++if(file->f_op!=&kevent_user_fops)+gotoout_fput;++err=kevent_ctl_process(file,cmd,num,arg);++out_fput:+fput_light(file,fput_needed);+returnerr;+}++staticint__devinitkevent_user_init(void)+{+structclass_device*dev;+interr=0;++err=register_filesystem(&kevent_fs_type);+if(err)+panic("%s: failed to register filesystem: err=%d.\n",+kevent_name,err);++kevent_mnt=kern_mount(&kevent_fs_type);+if(IS_ERR(kevent_mnt))+panic("%s: failed to mount silesystem: err=%ld.\n",+kevent_name,PTR_ERR(kevent_mnt));++kevent_user_major=register_chrdev(0,kevent_name,&kevent_user_fops);+if(kevent_user_major<0){+printk(KERN_ERR"Failed to register \"%s\" char device: err=%d.\n",+kevent_name,kevent_user_major);+return-ENODEV;+}++kevent_user_class=class_create(THIS_MODULE,"kevent");+if(IS_ERR(kevent_user_class)){+printk(KERN_ERR"Failed to register \"%s\" class: err=%ld.\n",+kevent_name,PTR_ERR(kevent_user_class));+err=PTR_ERR(kevent_user_class);+gotoerr_out_unregister;+}++dev=class_device_create(kevent_user_class,NULL,+MKDEV(kevent_user_major,0),NULL,kevent_name);+if(IS_ERR(dev)){+printk(KERN_ERR"Failed to create %d.%d class device in \"%s\" class: err=%ld.\n",+kevent_user_major,0,kevent_name,PTR_ERR(dev));+err=PTR_ERR(dev);+gotoerr_out_class_destroy;+}++printk("KEVENT subsystem: chardev helper: major=%d.\n",kevent_user_major);++return0;++err_out_class_destroy:+class_destroy(kevent_user_class);+err_out_unregister:+unregister_chrdev(kevent_user_major,kevent_name);++returnerr;+}++staticvoid__devexitkevent_user_fini(void)+{+class_device_destroy(kevent_user_class,MKDEV(kevent_user_major,0));+class_destroy(kevent_user_class);+unregister_chrdev(kevent_user_major,kevent_name);+mntput(kevent_mnt);+unregister_filesystem(&kevent_fs_type);+}++module_init(kevent_user_init);+module_exit(kevent_user_fini);
On Thu, Aug 03, 2006 at 01:45:59PM +0400, Evgeniy Polyakov (johnpol@2ka.mipt.ru) wrote:
Changes from 'take2' patchset:
* split kevent_finish_user() to locked and unlocked variants
* do not use KEVENT_STAT ifdefs, use inline functions instead
* use array of callbacks of each type instead of each kevent callback initialization
* changed name of ukevent guarding lock
* use only one kevent lock in kevent_user for all hash buckets instead of per-bucket locks
* do not use kevent_user_ctl structure instead provide needed arguments as syscall parameters
* various indent cleanups
* mapped buffer (initial) implementation (no userspace yet)
Also added optimisation aimed to help when a lot of kevents are being
copied from userspace in one syscall.
--
Evgeniy Polyakov
From: Eric Dumazet <hidden> Date: 2006-08-03 09:54:31
On Thursday 03 August 2006 11:46, Evgeniy Polyakov wrote:
quoted hunk
Network AIO, socket notifications.
This patchset includes socket notifications and network asynchronous IO.
Network AIO is based on kevent and works as usual kevent storage on top
of inode.
(3 * TCP_RTO_MIN) / 4,
+static int kevent_naio_enqueue(struct kevent *k)
+{
+ int err, i;
+ struct page **page;
+ void *addr;
+ unsigned int size = k->event.id.raw[1];
+ int num = size/PAGE_SIZE;
+ struct file *file;
+ struct sock *sk = NULL;
+ int fput_needed;
+
+ file = fget_light(k->event.id.raw[0], &fput_needed);
+ if (!file)
+ return -ENODEV;
+
+ err = -EINVAL;
+ if (!file->f_dentry || !file->f_dentry->d_inode)
+ goto err_out_fput;
How can you be 100% sure this file is actually a socket here ?
(Another thread could close the fd and this fd can now point to another file)
You should do
if (file->f_op != &socket_file_ops)
goto err_out_fput;
sk = file->private_data; /* set in sock_map_fd */
On Thu, Aug 03, 2006 at 11:54:26AM +0200, Eric Dumazet (dada1@cosmosbay.com) wrote:
On Thursday 03 August 2006 11:46, Evgeniy Polyakov wrote:
quoted
Network AIO, socket notifications.
This patchset includes socket notifications and network asynchronous IO.
Network AIO is based on kevent and works as usual kevent storage on top
of inode.
How can you be 100% sure this file is actually a socket here ?
(Another thread could close the fd and this fd can now point to another file)
You should do
if (file->f_op != &socket_file_ops)
goto err_out_fput;
sk = file->private_data; /* set in sock_map_fd */
That will be socket, not sock, but that check is definitely needed in
both socket and network aio code.
Thanks Eric.
It seems quite wrong to hold ctl_mutex while doing a copy_to_user() (of
possibly a large amount of data) : A thread can sleep on a page fault and
other threads cannot make progress.
Eric
It seems quite wrong to hold ctl_mutex while doing a copy_to_user() (of
possibly a large amount of data) : A thread can sleep on a page fault and
other threads cannot make progress.
I would not call that wrong - system prevents some threads from removing
kevents which are counted to be transfered to the userspace, i.e. when
dequeuing was awakened and it had seen some events it is possible, that
when it will dequeue them part will be removed by other thread, so I
prevent this.
It seems quite wrong to hold ctl_mutex while doing a copy_to_user() (of
possibly a large amount of data) : A thread can sleep on a page fault and
other threads cannot make progress.
I would not call that wrong - system prevents some threads from removing
kevents which are counted to be transfered to the userspace, i.e. when
dequeuing was awakened and it had seen some events it is possible, that
when it will dequeue them part will be removed by other thread, so I
prevent this.
Hum, "wrong" was maybe not the good word.... but kqueue_dequeue_ready() uses a
spinlock (ready_lock) to protect ready_list. One particular struct kevent is
given to one thread, one at a time.
If you look at fs/eventpoll.c, you can see how carefull is ep_send_events() so
that multiple threads can in the same time transfer different items to user
memory.
In a model where several threads are servicing events collected by a single
point (epoll, or kevent), this is important to not block all threads because
of a single thread waiting a swapin (trigered by copy_to_user() )
Eric
It seems quite wrong to hold ctl_mutex while doing a copy_to_user() (of
possibly a large amount of data) : A thread can sleep on a page fault and
other threads cannot make progress.
I would not call that wrong - system prevents some threads from removing
kevents which are counted to be transfered to the userspace, i.e. when
dequeuing was awakened and it had seen some events it is possible, that
when it will dequeue them part will be removed by other thread, so I
prevent this.
Hum, "wrong" was maybe not the good word.... but kqueue_dequeue_ready() uses a
spinlock (ready_lock) to protect ready_list. One particular struct kevent is
given to one thread, one at a time.
I mean that wait_event logic will see that there are requested number of
events, and when it starts to get them, it is possible that there will
be no events at all.
If you look at fs/eventpoll.c, you can see how carefull is ep_send_events() so
that multiple threads can in the same time transfer different items to user
memory.
It is done under the same logic under ep->sem semaphore, which is being
held for del and read operations.
Or do you mean to have rw semahore instead of mutex here?
In a model where several threads are servicing events collected by a single
point (epoll, or kevent), this is important to not block all threads because
of a single thread waiting a swapin (trigered by copy_to_user() )
AIO, aio_sendfile() implementation.
This patch includes asynchronous propagation of file's data into VFS
cache and aio_sendfile() implementation.
Network aio_sendfile() works lazily - it asynchronously populates pages
into the VFS cache (which can be used for various tricks with adaptive
readahead) and then uses usual ->sendfile() callback.
...
--- /dev/null+++ b/kernel/kevent/kevent_aio.c
@@ -0,0 +1,584 @@+/*+*kevent_aio.c+*
Since this is *almost* same as mpage.c code, wondering if its possible
to make common
generic/helper routines in mpage.c and use it here ?
Thanks,
Badari
On Thu, Aug 03, 2006 at 10:04:36AM -0700, Badari Pulavarty (pbadari@us.ibm.com) wrote:
Evgeniy Polyakov wrote:
quoted
AIO, aio_sendfile() implementation.
This patch includes asynchronous propagation of file's data into VFS
cache and aio_sendfile() implementation.
Network aio_sendfile() works lazily - it asynchronously populates pages
into the VFS cache (which can be used for various tricks with adaptive
readahead) and then uses usual ->sendfile() callback.
...
--- /dev/null+++ b/kernel/kevent/kevent_aio.c
@@ -0,0 +1,584 @@+/*+*kevent_aio.c+*
Since this is *almost* same as mpage.c code, wondering if its possible
to make common
generic/helper routines in mpage.c and use it here ?
Yes, as I mentioned in mail to Christoph, I did it just to separate
kevent as much as possible (so I introduced ->get_block() based
approach). It can be safely moved into mpage code and used from more
clear callback like ->readpage().
Since this AIO code was decided to be postponed for a while, I'm not
updating it (just make sure that it compiles with new changes), since
overall design of AIO changes (if any) is not 100% completed.