kqueue microbenchmark results
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 15 lines · Gideon Glass
Quoted 8 lines · Jonathan Lemon
Also, consider the following scenario for the proposed
get_event():1. packet arrives, queues an event.
2. user retrieves event.
3. second packet arrives, queues event again.
4. userreads()all data.Quoted 5 lines
Now, next time around the loop, we get a notification for an event when there is no data to read. The application now must be prepared to handle this case (meaning no blocking
read()calls can be used).Also, what happens if the user closes the socket after step 4 above?
Quoted 7 lines
Depends on the implementation. If the item in the queue is the struct file (or whatever an fd indexes to), then the implementation can only queue the fd once. This also avoids the problem with closing sockets -
close()would naturally do alist_del()or whatever on the struct file.At least I think it could be implemented this way...
kqueue currently does this; a close() on an fd will remove any pending events from the queues that they are on which correspond to that fd. I was trying to point out that it isn't as simple as it would seem at first glance, as you have to consider an issues like this. Also, if the implementation allows multiple event types per fd, (leading to multiple queued events per fd) there no longer is a 1:1 mapping to something like 'struct file', and performing a list walk doesn't scale very well. --
Jonathan
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/
Quoted 2 lines
kqueue currently does this; a
close()on an fd will remove any pending events from the queues that they are on which correspond to that fd.
This seems an odd thing to do. Surely what you need to do is to post a 'close completed' event to the queue. This also makes more sense when you have a threaded app and another thread may well currently be in say a read at the time it is closed
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/
Quoted 7 lines · Alan Cox
Quoted 2 lines
kqueue currently does this; a
close()on an fd will remove any pending events from the queues that they are on which correspond to that fd.This seems an odd thing to do. Surely what you need to do is to post a 'close completed' event to the queue. This also makes more sense when you have a threaded app and another thread may well currently be in say a read at the time it is closed
Kqueue's flexibility could allow this to be implemented, all you would need to do is make a new filter trigger. You might need a _bit_ of hackery to make sure those aren't removed, or one could just add the event after clearing all pending events.
Adding a filter to be informed when a specific fd is closed is certainly an option, it doesn't make very much sense because that fd could then be reused quickly by something else...
but anyhow:
The point of this interface is to ask kqueue to report only on the things you are interested in, not to generate superfluous that you wouldn't care about. You could make such a flag if Linux adopted this interface and I'm sure we'd be forced to adopt it, but if you make kqueue generate info an application won't care about I don't think that would be taken back.
Signature · 6 lines
-Alfred Perlstein - [[email protected]|[email protected]] "I have the heart of a child; I keep it in a jar on my desk." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] Please read the FAQ at http://www.tux.org/lkml/
Quoted 7 lines · Alan Cox
Quoted 2 lines
kqueue currently does this; a
close()on an fd will remove any pending events from the queues that they are on which correspond to that fd.This seems an odd thing to do. Surely what you need to do is to post a 'close completed' event to the queue. This also makes more sense when you have a threaded app and another thread may well currently be in say a read at the time it is closed
Actually, it makes sense when you think about it. The `fd' is actually a capability that the application uses to refer to the open file in the kernel. If the app does a close() on the fd, it destroys this naming.
The application then has no capability left which refers to the formerly open socket, and conversly, the kernel has no capability (name) to notify the application of a close event. What can I say, "the fd formerly known as X" is now gone? It would be incorrect to say that "fd X was closed", since X no longer refers to anything, and the application may have reused that fd for another file.
As for the multi-thread case, this would be a bug; if one thread closes the descriptor, the other thread is going to get an EBADF when it goes to perform the read.
--
Jonathan
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/
Quoted 4 lines
the application of a close event. What can I say, "the fd formerly known as X" is now gone? It would be incorrect to say that "fd X was closed", since X no longer refers to anything, and the application may have reused that fd for another file.
Which is precisely why you need to know where in the chain of events this happened. Otherwise if I see
'read on fd 5'
'read on fd 5'
How do I know which read is for which fd in the multithreaded case
Quoted 3 lines
As for the multi-thread case, this would be a bug; if one thread closes the descriptor, the other thread is going to get an EBADF when it goes to perform the read.
Another thread may already have reused the fd
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/
Quoted 8 lines · Alan Cox
Quoted 7 lines
Quoted 2 lines
kqueue currently does this; a
close()on an fd will remove any pending events from the queues that they are on which correspond to that fd.the application of a close event. What can I say, "the fd formerly known as X" is now gone? It would be incorrect to say that "fd X was closed", since X no longer refers to anything, and the application may have reused that fd for another file.
Quoted 7 lines
Which is precisely why you need to know where in the chain of events this happened. Otherwise if I see
'read on fd 5'
'read on fd 5'How do I know which read is for which fd in the multithreaded case
That can't happen, can it? Let's say the following happens:
close(5)
accept() = 5
call kevent() and rebind fd 5
The 'close(5)' would remove the old fd 5 events. Therefore, any fd 5 events you see returned from kevent are for the new fd 5.
(I suspect it helps that kevent() is both the only way to bind events and the only way to pick them up; makes it harder for one thread to sneak a new fd into the event list without the thread calling kevent() noticing.)
- Dan
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/
Quoted 12 lines
Quoted 7 lines
Which is precisely why you need to know where in the chain of events this happened. Otherwise if I see
'read on fd 5'
'read on fd 5'How do I know which read is for which fd in the multithreaded case
That can't happen, can it? Let's say the following happens:
close(5) accept() = 5 call kevent() and rebind fd 5
Quoted 7 lines
The 'close(5)' would remove the old fd 5 events. Therefore, any fd 5 events you see returned from kevent are for the new fd 5.
(I suspect it helps that
kevent()is both the only way to bind events and the only way to pick them up; makes it harder for one thread to sneak a new fd into the event list without the thread callingkevent()noticing.)
Strictly speaking, it can happen in two cases:
1) single acceptor thread, multiple worker threads
2) multiple anonymous "work to do" threads
In both these cases, the incoming requests from a client are given to any thread, rather than a particular thread.
In the first case, we can have (id:executer order:event):
1:1:open 5
2:2:read 5
3:4:read 5
2:3:close 5
If thread 2 processes the close event before thread 3 processes the read event, then when thread 3 attempts procssing, it will fail.
Technically, this is a group ordering problem in the design of the software, which should instead queue all events to a dispatch thread, and the threads should use IPC to serialize processing of serial events. This is similar to the problem with async mounted FS recovery in event of a crash: without ordering guarantees, you can only get to a "good" state, not necessarily "the one correct state".
In the second case, we can have:
1:2:read 5
2:1:open 5
3:4:read 5
2:3:close 5
This is just a non-degenerate form of the first case, where we allow thread 1 and all other threads to be identical, and don't serialize open state initialization.
The NetWare for UNIX system uses this model. The benefit is that all user space threads can be identical. This means that I can use either threads or processes, and it won't matter, so my software can run on older systems that lack "perfect" threads models, simply by using processes, and putting client state into shared memory.
In this case, there is no need for inter-thread synchronization; instead, we must insist that events be dispatched sequentially, and that the events be processed serially. This effectively requires event processing completion notigfication from user space to kernel space.
In NetWare for UNIX, this was accomplished using a streams MUX which knew that the NetWare protocol was request-response. This also permitted "busy" responses to be turned around in kernel space, without incurring a kernel-to-user space scheduling penalty. It also permitted "piggyback", where an ioctl to the mux was used to respond, and combined sending a response with the next read. This reduced protection domain crossing and the context switch overhead by 50%. Finally, the MUX sent requests to user space in LIFO order. This approach is called "hot engine scheduling", in that the last reader in from user space is the most likely to have its pages in core, so as to not need swapping to handle the next request.
I was architect of much of the process model discussed above; as you can see, there are some significant performance wins to be had by building the right interfaces, and putting the code on the right side of the user/kernel boundary.
In any case, the answer is that you can not assume that the only correct way to solve a problem like event inversion is serialization of events in user space (or kernel space). This is not strictly a "threaded application implementation" issue, and it is not strictly a kernel serialization of event delivery issue.
Another case, which NetWare did not handle, is that of rejected authentication. Even if you went with the first model, and forced your programmers to use expensive inter-thread synchronization, or worse, bound each client to a single thread in the server, thus rendering the system likely to have skewed thread load, getting worse the longer the connection was up, you would still have the problem of rejected authentication. A client might attempt to send authentication followed by commands in the same packet series, without waiting for an explicit ACK after each one (i.e. it might attempt to implement a sliding window over a virtual circuit), and the system on the other end might dilligently queue the events, only to have the authentication be rejected, but with packets queued already to user space for processing, assuming serialization in user space. You would then need a much more complex mechanism, to allow you to invalidate an already queued event to another thread, which you don't know about in your thread, before you release the interlock. Otherwise the client may get responses without a valid authentication.
You need look no further than LDAPv3 for an example of a protocol where this is possible (assuming X.509 certificate based SASL authentication, where authentication is not challenge-response, but where it consists solely of presenting ones certificate).
When considering this API, you have to consider more than just the programming models you think are "right", you have to consider all of the that are possible.
All in all, this is an interesting discussion. 8-).
Terry Lambert [email protected]
---
Any opinions in this posting are my own and not those of my present or previous employers.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/
Quoted 24 lines · Terry Lambert
Quoted 7 lines
Quoted 6 lines
Which is precisely why you need to know where in the chain of events this happened. Otherwise if I see
'read on fd 5'
'read on fd 5'
How do I know which read is for which fd in the multithreaded caseQuoted 6 lines
That can't happen, can it? Let's say the following happens:
close(5) accept() = 5 call kevent() and rebind fd 5The 'close(5)' would remove the old fd 5 events. Therefore, any fd 5 events you see returned from kevent are for the new fd 5.
Strictly speaking, it can happen in two cases:
1) single acceptor thread, multiple worker threads
2) multiple anonymous "work to do" threadsIn both these cases, the incoming requests from a client are given to any thread, rather than a particular thread.
In the first case, we can have (id:executer order:event):
Quoted 8 lines
1:1:open 5
2:2:read 5
3:4:read 5
2:3:close 5If thread 2 processes the close event before thread 3 processes the read event, then when thread 3 attempts procssing, it will fail.
You're not talking about kqueue() / kevent() here, are you? With that interface, thread 2 would not see a close event; instead, the other events for fd 5 would vanish from the queue. If you were indeed talking about kqueue() / kevent(), please flesh out the example a bit more, showing who calls kevent().
(A race that *can* happen is fd 5 could be closed by another thread after a 'read 5' event is pulled from the event queue and before it is processed, but that could happen with any readiness notification API at all.)
- Dan
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/
Quoted 21 lines · Dan Kegel
Quoted 8 lines · Alan Cox
Quoted 7 lines
Quoted 2 lines
kqueue currently does this; a
close()on an fd will remove any pending events from the queues that they are on which correspond to that fd.the application of a close event. What can I say, "the fd formerly known as X" is now gone? It would be incorrect to say that "fd X was closed", since X no longer refers to anything, and the application may have reused that fd for another file.
Quoted 7 lines
Which is precisely why you need to know where in the chain of events this happened. Otherwise if I see
'read on fd 5'
'read on fd 5'How do I know which read is for which fd in the multithreaded case
That can't happen, can it? Let's say the following happens:
close(5) accept() = 5 call kevent() and rebind fd 5
Quoted 7 lines
The 'close(5)' would remove the old fd 5 events. Therefore, any fd 5 events you see returned from kevent are for the new fd 5.
(I suspect it helps that
kevent()is both the only way to bind events and the only way to pick them up; makes it harder for one thread to sneak a new fd into the event list without the thread callingkevent()noticing.)
Yes, that's how it does and should work. Noticing the close() should be done via thread communication/IPC not stuck into kqueue.
Signature · 6 lines
-Alfred Perlstein - [[email protected]|[email protected]] "I have the heart of a child; I keep it in a jar on my desk." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] Please read the FAQ at http://www.tux.org/lkml/
Quoted 5 lines · Alan Cox
Quoted 4 lines
the application of a close event. What can I say, "the fd formerly known as X" is now gone? It would be incorrect to say that "fd X was closed", since X no longer refers to anything, and the application may have reused that fd for another file.
Quoted 7 lines
Which is precisely why you need to know where in the chain of events this happened. Otherwise if I see
'read on fd 5'
'read on fd 5'How do I know which read is for which fd in the multithreaded case
No you don't, you don't see anything with the current code unless fd 5 is still around, what you're presenting to Jonathan is a application threading problem, not something that need to be resolved by the OS.
Quoted 5 lines
Quoted 3 lines
As for the multi-thread case, this would be a bug; if one thread closes the descriptor, the other thread is going to get an EBADF when it goes to perform the read.
Another thread may already have reused the fd
This is another example of an application threading problem.
Signature · 6 lines
-Alfred Perlstein - [[email protected]|[email protected]] "I have the heart of a child; I keep it in a jar on my desk." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] Please read the FAQ at http://www.tux.org/lkml/