Message Queues and Interrupts

[rkennedy9064]

I've been looking into message queues and was wondering everyone's thoughts on adding messages through interrupts. My initial plan was to have a loop that continually checks for messages and add a message to the queue in an interrupt. For example, when the mouse interrupt fires, if it moved, or a button was pressed/released, generate the appropriate message and add it to the queue. Is that a common approach when generating messages? I know you want to keep interrupts as short as possible, so I figured just adding it to the message queue and not blocking would be a decent approach. What do you guys think? Is this a pretty common approach to a message queues? Are there any alternative, or better ways then just adding the generated message inside of the interrupt itself?

[nullplan]

The common approach is to switch from interrupt handlers to kernel threads. Instead of having an interrupt handler do something, it only increments a semaphore that the handler thread is waiting for, and otherwise blocks the interrupt. If the actual interrupt returns normally, the interrupt is re-enabled. This approach allows the scheduler to handle task prioritization. Also, the interrupt handler will be running in thread context, and can therefore do more things

Handling input devices by generating queues of events is indeed the common approach. So long as you throw them away if nobody is listening to them, anyway. Otherwise you risk overflows.

[rkennedy9064]

The common approach is to switch from interrupt handlers to kernel threads. Instead of having an interrupt handler do something, it only increments a semaphore that the handler thread is waiting for, and otherwise blocks the interrupt.

That sounds like a pretty interesting approach. So using the keyboard interrupt as an example, you would just have an interrupt handler that increments a semaphore and then issues an end of interrupt to the PIC, and the kernel thread would then read from port 0x60 and use the data? If so, is there a possibility the kernel thread might not read from the port in time before more interrupts happen and you end up losing data?

Handling input devices by generating queues of events is indeed the common approach. So long as you throw them away if nobody is listening to them, anyway. Otherwise you risk overflows.

I was thinking about this also and it seemed like a ring buffer would be a good approach for overflows. That way you can generate messages at a steady rate and if nothing is reading them it just overwrites the old messages that never got read. Is that the common data structure most people implement message queues with, or are there better ones?

[Octocontrabass]

So using the keyboard interrupt as an example, you would just have an interrupt handler that increments a semaphore and then issues an end of interrupt to the PIC, and the kernel thread would then read from port 0x60 and use the data? If so, is there a possibility the kernel thread might not read from the port in time before more interrupts happen and you end up losing data?

The PS/2 keyboard controller is not capable of raising a new interrupt or receiving more data from the keyboard (or mouse) until the interrupt is acknowledged by reading port 0x60. The keyboard (and mouse) can buffer a few bytes while waiting for the PS/2 controller to be ready to receive more data. You can still lose data if the buffer overflows, but your kernel would have to be very busy to reach that point.

The keyboard is a very slow device, though. You may have to be more careful about scheduling your kernel threads to avoid losing data with faster devices.

Also, keep in mind that this design assumes edge-triggered interrupts. With level-triggered interrupts, you'll cause an interrupt flood if you try to send the EOI before you acknowledge the device raising the interrupt.

[bzt]

...generate the appropriate message and add it to the queue. Is that a common approach when generating messages?

For microkernels yes. This is what most do.

I know you want to keep interrupts as short as possible, so I figured just adding it to the message queue and not blocking would be a decent approach. What do you guys think? Is this a pretty common approach to a message queues?

Absolutely. Actually this is exactly what Minix does: each and every interrupt generates a message which is then enqueued in the appropriate device driver task's message queue.

FYI, this is also what my kernel does, with a little twist. When an interrupt happens, I mask the corresponding IRQ in the IC. I only re-enable it when the device driver task acknowledges that the IRQ message has been processed. This is not the most efficient solution, but performs very well and keeps the code brainf*ck simple. This allows me to have multiple IRQs at the same time without complexity in the code (for example a keyboard IRQ fires, then it's masked and a message is sent to the ps2 driver. Other IRQs, like network card's are allowed to fire before the ps2 driver is scheduled and communicates with the keyboard hardware).

Are there any alternative, or better ways then just adding the generated message inside of the interrupt itself?

There are some exceptions in Minix, for example there's no message for the "clock" task, that's handled right away. Also, just to be on the safe side, the Minix kernel's interrupt handler checks at the end of the function if there are any pending interrupts, and if so, enqueues them as well. This should very rarely happen as sending a message is fast, so the kernel spends just a little amount of time in the handler with interrupts masked (there's no per IRQ masking in Minix). Generating a message is simple, fast and straightforward. You can diverge from this simple scheme, but you should ask yourself if the additional complexity worth it. For the clock interrupt it most certainly does, but not sure about the other interrupts. Maybe simplicity is better for your kernel.

Cheers,
bzt

[OSwhatever]

I've been looking into message queues and was wondering everyone's thoughts on adding messages through interrupts. My initial plan was to have a loop that continually checks for messages and add a message to the queue in an interrupt. For example, when the mouse interrupt fires, if it moved, or a button was pressed/released, generate the appropriate message and add it to the queue. Is that a common approach when generating messages? I know you want to keep interrupts as short as possible, so I figured just adding it to the message queue and not blocking would be a decent approach. What do you guys think? Is this a pretty common approach to a message queues? Are there any alternative, or better ways then just adding the generated message inside of the interrupt itself?

Adding messages in an interrupt context can be difficult as it might be an allocation and queuing in the interrupt context which usually bad. You can have pre-allocated messages though. Usually what you use is bottom halves that is doing all the allocation and message queuing. Then who ever gets that message does the actual processing of the interrupt. Basically this is roughly what you are suggesting and it is a very common way to handle interrupts.

Bottom halves are like message queues but should be considered as work queues instead. In order to implement this, best way is pre-allocate the scheduled structures. Use lockless algorithms like lists and queues as far as you can because they are your friend in interrupt contexts.

[rkennedy9064]

Thanks for all the suggestions so far. I got a basic working version setup for the keyboard and mouse. I just read the data from the port on interrupt and add it to a non locking pre-allocated ring buffer like suggested. Then I have a separate task that polls and processes each queue. Currently all it does is print the data to a serial port for debugging, but so far so good. I should be able to build on this to actually allocate and dispatch messages as needed.

[AndrewAPrice]

How do people deal with there being too many messages queued?

I've seen some people (in other threads) suggest that you can block the caller, but I don't like this approach because the caller could be the kernel (that an interrupt was fired) or a system service (e.g. the window manager saying you're now in focus.)

The most obviously worrisome being "the mouse has moved" queuing thousands of times while the thread is doing some processing.

[nullplan]

How do people deal with there being too many messages queued?

Dropping the event. If you move the mouse, and tons of mouse-move events are generated, and the consumer can't keep up, it will likely not be the end of the world if some of those mouse-move events end up being dropped.

Alternatively, especially in the case of mouse-move events, you can combine some of them. If a move event is still in the queue by the time the next one arrives, just add the new mouse movement to the one not yet read. The user is unlikely to care that the pointer did not travel from A to B via C, especially if they are all on the same line anyway.

Other scenario: Someone is holding down a key, and the keyboard buffer is filling faster than the consumer can keep up with. What to do? Probably throttling the key-repeat is a good idea, but if push comes to shove and the queue is just full, you have to drop additional events. The user is also unlikely to care that they just input a string of length 5127, when it should have been 5130.

In general, on resource exhaustion the only thing you can often do is record an error and otherwise back out of the action you were attempting. If an Ethernet frame is received and you have no buffer free for it, you can also only drop it. This is no different in principle.

[AndrewAPrice]

How do people deal with there being too many messages queued?

Dropping the event. If you move the mouse, and tons of mouse-move events are generated, and the consumer can't keep up, it will likely not be the end of the world if some of those mouse-move events end up being dropped.

We could implement "this program is unresponsive" and terminate if the queue gets full. It would force applications to consume messages as fast a possible, then put the actual handling code in a different thread. Then the userland code would be that consumes the messages could decide how to merge together multiple mouse move messages if the handling logic in the other thread hasn't caught up. Perhaps this would be too Draconian.

Alternatively, especially in the case of mouse-move events, you can combine some of them. If a move event is still in the queue by the time the next one arrives, just add the new mouse movement to the one not yet read. The user is unlikely to care that the pointer did not travel from A to B via C, especially if they are all on the same line anyway.

How would you implement this in a fast, generic way in the context of a microkernel that doesn't have any concept of a mouse? e.g. Mouse and keyboard messages are good candidates to merge together, window gained/lost focus could be merged to just have the latest state, while you probably want to process every individual event that says a child process closed.

[nullplan]

We could implement "this program is unresponsive" and terminate if the queue gets full.

Wrong layer of abstraction. This is only about input devices and how to read them out, it has nothing to do with process management. What you are talking about is more like an application in a windowing system not responding to events fast enough. Which is fine if the windowing system wants to implement this, but this is already twice removed from reading the input device (Device --> Windowing system --> Application). I suppose, the best thing you can do is inject an "overflow occurred" message into the event stream when the buffer is full. You save somewhere in the kernel/driver that an overflow occurred, and next time the message queue is read, after removing a message from the queue, an overflow event is injected at the end of the stream and reset the overflow flag. That way, the userland driver can reset state or explicitly ask for the current state if appropriate, to make sure at the very least it has the most up-to-date picture of what is going on.

Then the userland code would be that consumes the messages could decide how to merge together multiple mouse move messages if the handling logic in the other thread hasn't caught up. Perhaps this would be too Draconian.

It would be supremely unfair, given the kernel is what decides which process runs and for how long, and how many other processes are allowed to run alongside it. Essentially you would be punishing processes for starving them in certain situations. I do not think a high-load situation is going to be improved massively by killing processes that are too slow. And your users probably won't appreciate their browser being killed for a bad website, either.

How would you implement this in a fast, generic way in the context of a microkernel that doesn't have any concept of a mouse?

The mouse driver has a concept of a mouse. The queue between mouse driver and event consumer must be such that the mouse driver can inspect at least the latest event in it. Then you can update that even in-place if it happens to be of the right type. You only want to merge mouse-move events that are consecutive. If a mouse-button event is in there, you do not want to update the pointer position before the click with moves that happened later. There, that is O(1), doesn't get much faster, conceptually.

Mouse and keyboard messages are good candidates to merge together,[...]

Mouse moves, yes. Mouse buttons, no. Keyboard, also no. If you get "Z button pressed" and "Z button released" very quickly, then that is probably because the user typed a Z and wants it to show up in whatever application is running. You do not want to merge these as saying the button was never pressed at all, just because X11 is a little slow to respond today.

[...] window gained/lost focus could be merged to just have the latest state,[...]

That is for the windowing system to figure out, which I shall not have in my kernel. So it is not my concern.

[...]while you probably want to process every individual event that says a child process closed.

Also no. The traditional UNIX way of doing this (and, you know, those who do not learn from UNIX are doomed to reinvent it, badly), is to send a SIGCHLD to the parent process. There is only a single bit of storage in-kernel for that event having occurred, so when multiple processes die before the SIGCHLD can be handled, the process does not actually get multiple SIGCHLD signals. Therefore, the parent process has to call "wait()" repeatedly in a mode that will, contrary to the name, actually not wait. That way the parent process can figure out which children died and take appropriate action.

[OSwhatever]

How do people deal with there being too many messages queued?

I've seen some people (in other threads) suggest that you can block the caller, but I don't like this approach because the caller could be the kernel (that an interrupt was fired) or a system service (e.g. the window manager saying you're now in focus.)

The most obviously worrisome being "the mouse has moved" queuing thousands of times while the thread is doing some processing.

This is very specific regarding what type of interrupt you are processing and the underlying hardware. I've noticed that I can disable the interrupt while the interrupt is in the queue and waiting to be processed for most types of interrupts. The interrupt is enabled again after some user space process has handled the request. Why is this? Because many HW has FIFOs and as soon the interrupt is enabled again the interrupt is fired for the next item in the FIFOs. Basically, the HW does the queuing as well which is neat.

Now there are interrupts that don't have this possibility. One suggestion here is to have several but limited amount of bottom half queue items. If there are too many interrupts than you can process you have lost the game anyway. Often for these types of interrupts multistage queuing can be beneficial, that the interrupt handling routine just quickly queues up the interrupt data and exits, the processing is done later in another thread. This queuing must of course have higher priority than the rest of the bulk threads. However, having several bottom half queue items is often pointless if you get an interrupt and then should read some status register. If you have several interrupts that value might already have been overwritten. So again it really depends on the hardware.

[nullplan]

This is very specific regarding what type of interrupt you are processing and the underlying hardware. I've noticed that I can disable the interrupt while the interrupt is in the queue and waiting to be processed for most types of interrupts. The interrupt is enabled again after some user space process has handled the request. Why is this? Because many HW has FIFOs and as soon the interrupt is enabled again the interrupt is fired for the next item in the FIFOs. Basically, the HW does the queuing as well which is neat.

Problem with that is, then the event will just drop on the HW side when the FIFO is full. There is no getting around the fact that resources in a computer are finite, and exhaustion may happen.

[AndrewAPrice]

We could implement "this program is unresponsive" and terminate if the queue gets full.

Wrong layer of abstraction. This is only about input devices and how to read them out, it has nothing to do with process management. What you are talking about is more like an application in a windowing system not responding to events fast enough. Which is fine if the windowing system wants to implement this, but this is already twice removed from reading the input device (Device --> Windowing system --> Application). I suppose, the best thing you can do is inject an "overflow occurred" message into the event stream when the buffer is full. You save somewhere in the kernel/driver that an overflow occurred, and next time the message queue is read, after removing a message from the queue, an overflow event is injected at the end of the stream and reset the overflow flag. That way, the userland driver can reset state or explicitly ask for the current state if appropriate, to make sure at the very least it has the most up-to-date picture of what is going on.

Sorry, I meant having a full queue is one possible signal that the kernel could use to identify that a program (be it a user program, service, or driver) could be unresponsive. This could alert the process manager to say, hey this process got stuck, perhaps we should try restarting it? (With some limits in place - if a driver crashes <1 per day, log it because there's a bug somewhere, but you could probably restart the driver and continue business as usual. If a driver crashes >1 per minute, this driver is a dud and it should stay dead.)

I do not think a high-load situation is going to be improved massively by killing processes that are too slow. And your users probably won't appreciate their browser being killed for a bad website, either.

Fair enough. For a user program, I'd rather my web browser or word processor to occasionally lag than to randomly die.

If this logic is in the process manager (a userland process in my microkernel), it could keep track of what should reset (it's probably fine if to reset a network driver or video card driver - user programs will have to be implemented in a way that they can reupload textures and reopen connections if this happens), whereas you wouldn't want to kill the user's word processor (perhaps alert the window manager to show a busy cursor or gray out the title bar or something.)

How would you implement this in a fast, generic way in the context of a microkernel that doesn't have any concept of a mouse?

The mouse driver has a concept of a mouse. The queue between mouse driver and event consumer must be such that the mouse driver can inspect at least the latest event in it. Then you can update that even in-place if it happens to be of the right type. You only want to merge mouse-move events that are consecutive. If a mouse-button event is in there, you do not want to update the pointer position before the click with moves that happened later. There, that is O(1), doesn't get much faster, conceptually.

Would this need a FIFO queue per sender/receiver pair? Having one incoming queue per process would be a security risk (and also a race risk) if anybody could see and modify it.

Now there are interrupts that don't have this possibility. One suggestion here is to have several but limited amount of bottom half queue items. If there are too many interrupts than you can process you have lost the game anyway.

Having a priority queue would be interesting. Give processes a priority (0 = kernel, 1000 = drivers, 2000 = services, 3000 = programs - the lower the number the higher the priority) and you can send messages at a priority number that is equal to or higher than your process's priority (so a driver could send a low priority message, but a program can't send a driver-priority message)?

Still, a priority queue is still a queue and we have finite space and computation power.

So some approaches we could take:
a) Let every message be a unique message (so it's fine if there are 20 "mouse moved" or "interrupt fired" events) and if the queue gets full we just ignore messages.
b) Have some kernel support for combining messages. In my OS, message IDs are unique to the receiver, and the messages themselves are small, fixed sized (small enough to fit in registers). I wonder if I could possibly register with the kernel the "combine" conditions of each register, with combine conditions such as "SUM" (mouse movement), "REPLACE" (window focus state, timestamp of the message, etc), "IGNORE" (the interrupt fired, don't really care about the parameters.)
c) Move the above logic to userland. Expect user processes to have a message processing thread (that's at a higher priority than the process's other threads), whos job is to process messages (combining together messages for the worker thread.) This feels like the purest option for a microkernel and would be super flexible, but would require additional syscalls (the wake the worker thread and sleep the messaging thread) + thread switch to get to the actual that would do something with the message.