Microkernel - asynchronous interrupt handling

[Kevin]

That's what I tried to explain with redirecting, so the process registers itself with a handling function as an interrupt handler. The only problem I have with this is: is it okay to change EIP at a random point of code execution? Can I be sure that the function I'm jumping to will do clean work and that all registers will be the same afterwards? I'd have to push 1. the return address which is the current EIP, and 2. the interrupt number on the process stack, and then clean up only number 2 because 1 is popped by the RET..

What you're implementing here is essentially Unix signals. They do work in a way, people are relatively familiar with them, and they are a PITA to use because you need to be extermely careful in signal handlers and it's too easy to use unsafe operations and break things. (tyndur uses them, by the way, so this is a lesson I learnt the hard way. That said, it does work if you're careful enough.)

Another thing: gravaera talked about acknowledging the interrupt on the specific device. So that's what I do for the device that has actually fired the interrupt, for example i tell the PS2 controller: "Hey, I've handled the event, you can go on". But what do i tell the interrupt controller? Is it okay to immediately write 0x20 to port 0x20 to tell the controller that the interrupt has ended? Is it possible that the device only remembers data until it fires the next interrupt?

The kernel can't tell the PS/2 controller anything, because only the driver knows how to do this. You also don't want to block interrupts until the userspace driver has completed its job, So what you may want to do is to queue a message/send a signal, mask the specific interrupt in the interrupt controller (IRQ sharing? Bad luck...), send EOI and go on. When the userspace driver signals completion (i.e. it has acknowledged the interrupt on the device level), you can reenable the interrupt in the interrupt controller.

[gravaera]

Yo:

... Is it possible that the device only remembers data until it fires the next interrupt?

Yes, depending on the device, this may be the case. Depending on the device, it also may not. Most devices will not have an on-chip memory area where they preserve old event-data, so most devices will "overwrite" old event data when a new IRQ comes in.

Specifically:

However, the handler does not read any event data from the device, and it does not do a device-specific ACK either since if it ACKs the IRQ, it will lose any event-data that it needs to read. The handler simply returns a value to the kernel telling it that "This IRQ belongs to my device". The kernel will then also not ACK the IRQ at the interrupt controller, and it will form and dispatch a message to the driver process notifying it that an IRQ has occured. The kernel now exits IRQ context.

Keep in mind that Kevin also just outlined a very important point, which is that alternatively, you can mask the pin/MSI-slot off, then EOI the interrupt controller.

With the approach I proposed, only IRQ pins that have a higher priority than the one currently being handled would be delivered to the kernel while the current pin has not been ACKed/EOId, because you have not yet ACKed the interrupt controller, so it still has the active pin's bit set in the In-Service Register. Therefore, it will not deliver any other IRQs unless the pin is of a higher priority than the highest active pin in the In-Service register.

With Kevin's approach, you mask the pin that is currently being handled, then EOI the interrupt controller, effectively allowing all IRQ pins other than the one being handled to be delivered, since by EOI-ing the interrupt controller, you clear the pin's bit in the In-Service Register (i.e, the interrupt controller now doesn't know that it shouldn't deliver lower priority IRQs, because it doesn't know what priority it's currently sitting at).

Depending on your design goals and whether or not you actually need to respect IRQ-pin prioritization, you may find yourself desiring either approach. On the IBM-PC, it probably doesn't matter since you probably don't actually have any devices that can reasonably be said to be of higher real-time priority than others. That said, if you have a Gigabit ethernet card firing IRQs in a storm, and you also have a periodic timer IRQ firing IRQs at say 1KHz, you might not want to allow the ethernet card's IRQ to nest and pre-empt the timer IRQs, since timer IRQs being delayed will have a worse effect on the system than the ethernet card dropping a few frames.

--Peace out,
gravaera

[Brendan]

Hi,

Brendan, at risk of derailing the thread, are you hard-coding the 32 interrupt-per-device limit or can it be exceeded? For example, MSI-X allows up to 2048 interrupt lines per device.

For 80x86 there's a maximum of 256 IDT entries. 32 are reserved for exceptions, some are needed for "spurious" IRQ sources, some are needed for the local APIC (timer, performance monitoring), and some will be used by the OS for IPIs. Let's assume we're left with about 210 IDT entries. Is it a good idea for an OS to allow a single device to allocate all of them? Given the limited number of IDT entries available to use; what would be a sane "max. number of vectors per device" limit?

If a device wants 2048 interrupt lines, then these can be mapped to 32 interrupt vectors (or less), and the OS's IRQ handlers can use a set of 32 flags (or maybe 64 for 64-bit kernels). The kernel's messaging code could expand the set of 32 bits into a set of 2048 bits; such that each of the 32 bits correspond to none or more of the 2048 bits. For an extreme example, maybe the OS only used 2 vectors for a device that wants 2048 interrupts, where each of the 2 bits cause 1024 bits to be set in the "these IRQs occurred" message sent to the driver.

Note: For 80x86 the actual limit is 256 IDT entries per CPU. In theory, with (e.g.) 16 CPUs it would be possible to have 16*210 = 3360 usable interrupt vectors. This is one of the things I want to explore (although not necessarily one IDT per CPU, but maybe one IDT per NUMA domain instead).


Cheers,

Brendan

[embryo]

Any external source must be implemented by OS developer

That's quite a bogus statement, Because in the end the difference between polling (pull communication) and push communication is the system taking the initiative.

When we talk about interrupt handling the system almost always just changes some state and lets the pull part to do it's job. So the source of interrupt related information is the OS, not hardware.

While it is possible to create some kind of system which will serve interrupt requests completely within an interrupt handler, but it is not a viable solution because of concurrency issues. It means the push communication is still just a dream for OS designers, but not a useful tool.

But may be you can show some way of robust event processing within event handler in a highly concurrent environment?

[Rusky]

You don't have to do all the processing in the interrupt handler to be push-driven. You don't even need hardware interrupts for a system in general to be push driven. You just need the event handler to be called when the event happens, rather than having something else ask if the event has happened.

[max]

You don't have to do all the processing in the interrupt handler to be push-driven. You don't even need hardware interrupts for a system in general to be push driven. You just need the event handler to be called when the event happens, rather than having something else ask if the event has happened.

embryo see this. If an interrupt fires and one of the tasks in the system is interrupted during its work and continues in the interrupt handler as described previously, then the handling happens neither completely in the interrupt handler nor is any kind of pulling involved - it's actually is a push mechanism.

My implementation now looks like this:
When an interrupt occurs, the irq is masked in the interrupt controller (thanks for the idea kevin ) and marked in a bitmap. Then there is a system call "wait for interrupt". It checks if the interrupt is already set in the bitmap, if yes it clears it and unmasks the interrupt. If the interrupt is not set, the task is set to waiting state. Then, when the scheduler tries to switch to the task, the bitmap is checked again, and if the requested IRQ happened, the bit is cleared and the interrupt unmasked.

[embryo]

My implementation now looks like this:
When an interrupt occurs, the irq is masked in the interrupt controller (thanks for the idea kevin ) and marked in a bitmap. Then there is a system call "wait for interrupt". It checks if the interrupt is already set in the bitmap, if yes it clears it and unmasks the interrupt. If the interrupt is not set, the task is set to waiting state. Then, when the scheduler tries to switch to the task, the bitmap is checked again, and if the requested IRQ happened, the bit is cleared and the interrupt unmasked.

In my view the most efficient way is to somehow schedule driver's thread within the interrupt handler. But this way leads to the race condition with the scheduler's timer interrupt (which is generally of higher priority) and in the end it's implementation becomes not so trivial, unfortunately. And even such way can be called "poll type communication" because of the scheduler must check if there is new thread to be run - typical loop with condition check, even if the loop is implemented as a timer interrupt.

[bwat]

In my view the most efficient way is to somehow schedule driver's thread within the interrupt handler. But this way leads to the race condition with the scheduler's timer interrupt (which is generally of higher priority) and in the end it's implementation becomes not so trivial, unfortunately.

It's not difficult at all. It can be done with a single semaphore like object: thread waits, interrupt handler signals. Once the thread has been inserted into the ready queue then there's no problem with an interrupt handler triggering a reschedule - after all that's what the timer does in most systems with scheduling quanta.

And even such way can be called "poll type communication" because of the scheduler must check if there is new thread to be run - typical loop with condition check, even if the loop is implemented as a timer interrupt.

[Edit: stuff deleted.]
This is my second attempt at an answer to this part. I misunderstood you the first time. I don't think any implementation that polls for the result of an interrupt is much good. Either use the interrupt or disable it and poll.

[Rusky]

Push/pull doesn't have much to do with the implementation. Like I said, you don't need interrupts for something to be considered "push." It's an API-level design thing- if the program is notified when an event fires, it's push driven. If the program is unaffected by the event until it asks for it specifically, it's pull driven.

You could even consider a typical GUI event loop-based program to be push-based, since the main thread doesn't have to say "did they push the button yet? did they push the button yet? did they push the button yet?" and instead just says "hey what happened- oh the button okay."

This makes even more sense when you consider that GetMessage() will typically put the program to sleep if there's no events to handle- it's similar to IRET saying "hey we're done handling the event go back to what you were doing until you have something else for me to do," although even if GetMessage() were implemented with polling it would still be presenting a push driven API.

[bwat]

Push/pull doesn't have much to do with the implementation.

This push/pull thing, which is new to me seems, like a unhelpful dichotomy. Others seem to be having problems with it as well.

[Rusky]

It's just a question of who determines that an event needs to be handled. Is it the consumer that has to keep checking? This is good when you don't care about handling the event right away and just need to know if it's happened (or even just what's happening at the moment and don't care about other times). Or, is it the producer that says "hey, something happened- somebody handle it." This is good when you want to handle the event when it happens, like with user input, network events, etc.

[bwat]

Then it's purely a question of synchronisation between producer and consumer? If so, then what's this push/pull model giving that the traditional sync/async variants of the message passing, and synchronised shared memory don't? If not, what on earth is it?

I've never heard of push/pull so I'm genuinely interested in the answer. This isn't me rubishing it - I just haven't seen the need for the coining of new terms.

[Combuster]

I've never heard of push/pull so I'm genuinely interested in the answer.

http://en.wikipedia.org/wiki/Push_technology

[bwat]

Right, so I was wrong. It's not synchronisation but rôle reversal in an unequal relationship (server starts acting like client), or maybe an introduction of equality to a communication relationship which is usually seen as unequal (no server or client just peers).

Is this helpful with regards to interrupts which in some machines supply an address to the CPU upon interrupt activation (push) but can often be masked (pull). Also, the processor will usually sample the IRQ lines at the end or close to the end of instruction execution (pull).

Maybe this push/pull distinction is only really used at higher levels?

[Rusky]

You're correct that a system can be implemented with different choices between push and pull at different levels of detail. It's typically talked about at the API level, but it still applies at lower levels.