Microkernel - asynchronous interrupt handling

[max]

Hey!

I couldn't find a topic about this yet (if there is one, please let me know): asynchronous interrupt handling. I'm writing a pure microkernel, therefore I want all drivers to run in userspace (I'm working with the PIC currently). So I have to somehow tell a process that an interrupt has happend. Here are the ways I figured out:

- Redirecting: the driver user process could register itself as an interrupt handling process for a specific interrupt number and provide the address of a handling function. When the interrupt occurs, the kernel would push the current EIP of the userspace process to the user stack, and then set it to that interrupt handling function. Then when returning to userspace, the interrupt handling function does its work when "return"ing it would take the old EIP from it's stack and continue its work. This could work in theory, but it seems to be a really ugly thing to do..

- Messaging: when an interrupt occurs, a message is sent to the process (or to a port as in my system). The process would then have to continuously check if there is a message waiting, what would waste performance. Same thing with..

- Polling: when an interrupt occurs, the kernel itself memorizes that this interrupt has happened. The process must then also continuously poll the kernel via a syscall if that interrupt has happend.. also bad.

What do you think about these ways? Also, how do you solve this in your systems (and when do you ACK)?

Thank you!
Greets, Max

[zhiayang]

Let me first preface my post with a disclaimer: I'm definitely not the most knowledgable person on this subject (or any subject for that matter).

Hey!

Hey!

- Redirecting: the driver user process could register itself as an interrupt handling process for a specific interrupt number and provide the address of a handling function. When the interrupt occurs, the kernel would push the current EIP of the userspace process to the user stack, and then set it to that interrupt handling function. Then when returning to userspace, the interrupt handling function does its work when "return"ing it would take the old EIP from it's stack and continue its work. This could work in theory, but it seems to be a really ugly thing to do..

I don't quite get what you're trying to say here. Aren't these handler things what most people use (at least when starting)? ie. Handler is called from the interrupt gate, interrupt gate restores previous state. What you're describing (push the current RIP etc) seems to describe what the CPU does when it goes into an interrupt gate.

ie.

Code: Select all

CPU executing normally
INT
CPU pushes rflags, rip, ss, cs and some other things
CPU jumps to indicated address in IDT
handler does things including ACK the PIT
handler does iret
CPU pops rflags, rip etc. from the stack
state is restored
CPU executes normally.
GOTO 0

This might be a misunderstanding on my part, but the above sounds like what you're describing and yes, it works in user mode as well.

- Messaging: when an interrupt occurs, a message is sent to the process (or to a port as in my system). The process would then have to continuously check if there is a message waiting, what would waste performance. Same thing with..

This is what I personally use. I'll elaborate below.

- Polling: when an interrupt occurs, the kernel itself memorizes that this interrupt has happened. The process must then also continuously poll the kernel via a syscall if that interrupt has happend.. also bad.

This seems like the worst of the 3 solutions you have proposed... The kernel would have to maintain a list of all pending interrupts, which would likely require looping on somebody's part to check for a particular interrupt... not a good idea.





As for how I do it:
My kernel started out as a large unstable monolithic piece of crap, but has slowly evolved into a somewhat more stable, somewhat more microkernel-ish design.

Once the kernel finishes its job (the kernel really just sets up the system and provides a set of system calls and interfaces to hardware, IMO it doesn't actually 'DO' anything after that), it becomes some sort of dispatch system.

While I realise this is probably quite slow, it enables a somewhat more extensible (ie. lazy on my part) system, where I can run drivers in userspace as processes communicating via IPC (honestly the main reason for going in this direction).

Basically, the kernel installs a set of default INT handlers that don't do anything except send messages to the dispatch thread. The dispatch thread checks a list of processes that are interested in whatever interrupts, then simply forwards the interrupts to the processes.

'Interested' processes send a message to the dispatch thread indicating their intended INT vector, which the dispatcher will put in its list of interested threads for that vector. This also means I don't need to fiddle with the IDT directly afterwards.


The above works for synchronous interrupts, or threads that only do things when an interrupt happens (like a keyboard handler or something). For asynchronous interrupts, you'll likely want your dispatcher to also accept a callback function, and for the thread to register its interest with that callback function pointer.
This lets it do its other things, then process an interrupt when it needs to via the interrupt callback. At least I think this is how most asynchronous systems work, callbacks.

As for the problem of having to constantly check for messages, the simplest way to do that is to just implement a Block() function that waits on an IPC message. The function that sends a message (in the kernel code) should check if its sleeping, and if so put it into the run list. Note that for asynchronous messaging, this is not an issue since you'd be doing something else while waiting for the message anyway, so the callback method works.



While I will say this is by far not the best way, I am just describing how I do it, others are welcome to criticise (the hell out of) this.

[max]

Thanks for the answer!

I don't quite get what you're trying to say here. Aren't these handler things what most people use (at least when starting)? ie. Handler is called from the interrupt gate, interrupt gate restores previous state. What you're describing (push the current RIP etc) seems to describe what the CPU does when it goes into an interrupt gate.

I think you misunderstood what i mean I don't talk about the normal interrupt handlers, they exist in my kernel and are called when an interrupt occurs. I just want to give userspace-code the possibility to handle these interrupts once it has registered itself for it. I'm thereby thinking of the observer pattern - a piece of code in the userspace that acts as a "Listener", and the kernel calls that listener at any time. Like this (example: Keyboard driver):

Code: Select all

- Keyboard-driver-process (kdp) spawns
- KDP contains a interrupt handling function, tells the kernel via a syscall that it wants this function to be called for example when the keyboard interrupt fires
- Execution continues as normal, other processes do their work, the KDP does something or just yields in a loop
- A keyboard interrupt comes in
- the interrupt handling routine in the kernel is called, checks if there is a process registered for that specific interrupt
- it finds the KDP process:
- It then pushes the EIP from this processes CPU state to this processes user stack
- Then it sets the EIP of this process to the interrupt handling function the KDP has provided to the kernel earlier (via the syscall)
- When the KDP has its turn, it seems like its normal execution is interrupted, and it just is inside of the handler function
- Once the handler function in the KDP has done its work, the RET pops the old EIP from the processes user stack and it just continues its old work (even in the same timeslice)

This would allow userspace code to handle interrupts just like a kernel interrupt handler.. Im just not sure if its OK to just change EIP at a time, and assume that the interrupt handling function does it's work clean without messing with registers..

For the messaging part that you do - what do you do if there are too many interrupts waiting to be handled, and the message buffer overflows? And also, the process has to continuously ask if there was a message, right?

Greets

[zhiayang]

Thanks for the answer!

I don't quite get what you're trying to say here. Aren't these handler things what most people use (at least when starting)? ie. Handler is called from the interrupt gate, interrupt gate restores previous state. What you're describing (push the current RIP etc) seems to describe what the CPU does when it goes into an interrupt gate.

I think you misunderstood what i mean I don't talk about the normal interrupt handlers, they exist in my kernel and are called when an interrupt occurs. I just want to give userspace-code the possibility to handle these interrupts once it has registered itself for it. I'm thereby thinking of the observer pattern - a piece of code in the userspace that acts as a "Listener", and the kernel calls that listener at any time. Like this (example: Keyboard driver):

Code: Select all

- Keyboard-driver-process (kdp) spawns
- KDP contains a interrupt handling function, tells the kernel via a syscall that it wants this function to be called for example when the keyboard interrupt fires
- Execution continues as normal, other processes do their work, the KDP does something or just yields in a loop
- A keyboard interrupt comes in
- the interrupt handling routine in the kernel is called, checks if there is a process registered for that specific interrupt
- it finds the KDP process:
- It then pushes the EIP from this processes CPU state to this processes user stack
- Then it sets the EIP of this process to the interrupt handling function the KDP has provided to the kernel earler
- Now, when the KDP has its turn, it seems like its normal execution is interrupted, and it just is inside of the handler function
- Once the handler function in the KDP has done its work, the RET pops the old EIP from the processes user stack and it just continues its old work (even in the same timeslice)

Im just not sure if its OK to just change EIP at a time, and assume that the interrupt handling function does it's work clean without messing with registers..

For the messaging part that you do - what do you do if there are too many interrupts waiting to be handled, and the message buffer overflows? And also, the process has to continuously ask if there was a message, right?

Greets

Ah, I have indeed misunderstood.
1. As for the message buffer overflowing, use a circular buffer, so the oldest message is overwritten by newer ones.
2. I get what you're trying to do.

I don't see the point in doing that weird stack manipulation (personally I try and keep weird manipulation to a minimum). What I do is place the target process in the first position in the run queue and yield the CPU to the scheduler. This effectively does what you're trying to do, but using existing implementations (although possibly slower due to the involvement of an interrupt gate)

(You might want to reread my post, I edited it quite a few times, answering the question about checking for messages)

[embryo]

I have to somehow tell a process that an interrupt has happend.

Actually you have only one way and this name is called "polling". The implementation can be more or less efficient, but the name always will be the same. So you should implement some efficient variant, but if the OS is "just for fun" it is possible to implement something "nice" (as it seems to you).

[max]

The stack magic I thought about doing there would just allow me to do nothing more than letting the normal code execution go on, and only pushing EIP to the stack shouldn't be too bad.. otherwise the interrupt handling function had to use a syscall to exit, to avoid RETing to some trash value

(You might want to reread my post, I edited it quite a few times, answering the question about checking for messages)

I did, and I got your point I thought about some kind of blocking mechanism too. I'd then have to block on a specific interrupt, that would be an idea too.

Actually you have only one way and this name is called "polling". The implementation can be more or less efficient, but the name always will be the same. So you should implement some efficient variant, but if the OS is "just for fun" it is possible to implement something "nice" (as it seems to you).

There is never an "only way", especially when it comes to polling things... Please read what I wrote about the redirecting method, above.
Why do you think it's just for fun?

[zhiayang]

embryo:
Your view is clearly myopic, I don't believe something like a callback function is polling. In fact, blocking is not polling, because it relies on an external source to reactivate the thread, an external source that isn't running on a tight if loop.


max:
I get the point of your stack manipulation, I'm just saying that you can reuse your existing code to do the exact same thing.

[gravaera]

Yo:

There are several plausble approaches, and your choice will mostly be dictated by how much jitter you're willing to allow to be observable from userspace, how responsive you want your kernel to be to IRQs, and how "pure" you'd like your design to be, with reference to microkernel-dogma.

I'll start with the premise that your SAS drivers can listen for event messages from the kernel in one way or another. This may entail some form of IPC, or spinning in a message loop, or whatever your design is. The majority of the decision making is really to do with determining how much processing is done within IRQ context, and how you intend to push the rest of the processing off for later.

• Each device's driver registers an IRQ handler on behalf of the device. The handler sits on a particular pin or MSI-IRQ slot. Upon IRQ entry, the kernel determines which IRQ was raised (which pin or MSI-slot), and then if there is more than one device sharing that pin, it runs the handler for each device. Each device's handler will interrogate its device to determine whether or not its device raised the IRQ.
  
  The handler for the device that raised the IRQ also reads any necessary event data from the device and then ACKs the IRQ in a device-specific manner. When the handler returns, the kernel also ACKs the IRQ at the interrupt controller, and then captures the event-data from the handler, and sends an IRQ-event-notification message to the driver process containing the event-data. The kernel now exits IRQ context.
• Each device's driver registers an IRQ handler on behalf of the device. The handler sits on a particular pin or MSI-IRQ slot. Upon IRQ entry, the kernel determines which IRQ was raised (which pin or MSI-slot), and then if there is more than one device sharing that pin, it runs the handler for each device. Each device's handler will interrogate its device to determine whether or not its device raised the IRQ.
  
  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.
  
  The driver process now must read any event-data from its device, then perform a device-specific ACK, and send a message back to the kernel telling it that it should now ACK the pin at the interrupt controller. Keep in mind that during all of this, and until the kernel has ACKed the IRQ at the interrupt controller, no other IRQs may be asserted on that pin, and in some cases, depending on the interrupt controller in use, no other IRQs may come in at all until the pending IRQ has been ACKed.
• Each device's driver gives the kernel an indication that its device has begun to assert IRQs on a particular pin/slot. No handler is registered. Upon IRQ, the kernel simply dispatches event notifications indiscriminately to all the driver processes that share the IRQ, and then exits IRQ context.
  
  Each driver process now picks up the event notification that was queued on its event queue and all of them asynchronously interrogate their device using I/O commands from userspace. Keep in mind that the kernel has not yet ACKed the pin at the interrupt controller. If the driver process is sure that it is not its device that raised the IRQ, it just ignores the message. Else, it will read any event data from the device, and then send a device-specific ACK to the device. Next, the driver process must send a message to the kernel telling it to ACK the pin/slot at the interrupt controller.

In each case you can see the IRQ latency issues involved, and the potential pros and cons. Responsiveness, jitter, purity of design, minimalization of the kernel's required work, etc are all factors in determining which approach you take.

--Peace out,
gravaera

[bwat]

You're thinking like a desktop OS developer which is fine if you're developing a desktop OS. In other worlds, your assumptions sound a bit strange!

- Messaging: when an interrupt occurs, a message is sent to the process (or to a port as in my system). The process would then have to continuously check if there is a message waiting, what would waste performance. Same thing with..

Let the handler block on message receive/port receive/semaphore and have the kernel send/signal on an interrupt. The handler will then deal with the cause of the interrupt when its priority allows it to. This gives greater control of what runs on the CPU. The idea that interrupts should have a de facto high priority isn't good when you have vital compute bound processes.

- Polling: when an interrupt occurs, the kernel itself memorizes that this interrupt has happened. The process must then also continuously poll the kernel via a syscall if that interrupt has happend.. also bad.

Systems that must survive an erroneous overabundance of interrupts can use polling to act a low pass filter. You poll at a certain frequency, if the events want to activate interrupts at a higher frequency then some events get ignored.

[AndrewAPrice]

It depends how you want it to work.

Are your drivers event based? Do you want the driver to receive a message?

In that case message passing would work. You can pass a message saying "Interrupt occured!" to the driver process, and the driver would have something like:

Code: Select all

MSG msg;
bool shutdown = false;
while(!shutdown) {
  GetMessage(&msg); // sleeps the process if there are no new messages so it's not continously polling
  switch(msg.type) {
     case M_QUIT:
       shutdown = true;
       break;
    case M_INTERRUPT:
       handleInterupt(msg.param); // handle the interrupt
       break;
  }
}

The second way would be to interrupt the process the same way the hardware interrupts the OS. The program needs a register handle:

Code: Select all

void interruptHandler(int i) {
  // handle interrupt here
}

registerInterruptHandler(interruptHandler)
listenForInterrupt(0x32);
listenForInterrupt(0x1A);

Then, when an interrupt occurs, the process jumps into the handler. If the process has not returned from the handler, then stick it on a queue so it immediately handles the next interrupt when it returns, until no more interrupts are left.

Internally, with either system (interrupts, or a message queue) I would avoid a system that performs dynamic memory allocation inside the interrupt handler. The 'message' that an interrupt occured would probably better to be a bit field of triggered interrupts attached to the process, which the system call for GetMessage can scan to generate a MSG object from. You can optimize this to make it super fast.

[Brendan]

Hi,

I use asynchronous messaging (so that task switches can be avoided/postponed). When a message is sent:

• the message is moved to the receiver's FILO message queue
• if the receiver was blocked waiting for a message, it is unblocked
• if the receiver is unblocked and has higher priority than the currently running thread, then it pre-empts the currently running thread immediately

For this sort of system, the kernel's IRQ handler can just send "IRQ #n occurred" messages to whoever asked for them. This has worked fine for me in the past; but for my next micro-kernel I will be adding some improvements.

With FILO message queues, if there are lots of messages on the queue when an IRQ occurs, then the receiver has to receive all of the older messages before it will receive the kernel's "IRQ #n occurred" message. For interrupt latency it would be nice if those "IRQ #n occurred" messages could skip ahead. It would also be nice if the kernel didn't have to construct the message and append it to the receiver's queue while stuck in an IRQ handler, as there's typically several locks involved (for the message queue and memory management).

For this reason, I'm planning to use a set of bits (one bit per IRQ, per thread). The kernel's "get message" code can be extended to check if any of these "IRQ occured flags" are set and create/return the "IRQ #n occurred" message instead of getting a message from the queue; which means it's trivial to make those "IRQ #n occurred" messages skip ahead of everything else on the queue, and (because it's easy to atomically set/clear flags, especially on 80x86) it reduces the need to deal with some locking in the kernel's IRQ handler. In addition to this, if multiple IRQs have occurred then it's easy to combine them into a single "all of these IRQs occurred" message rather than having a separate message for each IRQ.

Now; let me talk about IRQ numbering. There are 4 different IRQ numbering schemes:

• the device's own IRQ numbers (e.g. "the device's nth IRQ line")
• the bus' IRQ numbering (e.g. "PCI_IRQA", "ISA_IRQ12", etc)
• the PIC or IO APIC's numbering (e.g. "IO APIC input #18)
• the CPU's interrupt numbering (e.g. "IDT entry 0x44")

It's easy to use the CPU's interrupt numbering (and this is what I've done in the past). For my next micro-kernel I'll be using the device's own IRQ numbers instead. In this case:

• the device driver can just use hard-coded "device IRQ numbers" that never change (regardless of whether the kernel is using PIC or IO APIC or what the kernel does with the IDT)
• because a device's driver doesn't know or care about "CPU interrupt numbers", the kernel can change the "CPU interrupt number" that a device's IRQ is mapped to at any time it likes, without worrying about the device driver
• because a device can only have a maximum of 32 "device IRQs" there only needs to be 32 "IRQ occured flags" per thread (rather than 256 or 224 "IRQ occurred flags" per thread). This (combined with the "multiple IRQs in one message" from above) means that the kernel's "get message" code can do an atomic "XCHG" to clear the thread's "IRQ occurred flags" and get the old set of bits to store in the returned "all of these IRQs occurred" message.

Cheers,

Brendan

[jnc100]

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.

Regards,
John.

[embryo]

I don't believe something like a callback function is polling. In fact, blocking is not polling, because it relies on an external source to reactivate the thread, an external source that isn't running on a tight if loop.

The callback implementation still uses polling. And running on a tight loop is just one kind of polling, another kind - thread can sleep for some time. And yet another kind of polling is yielding thread's time to another execution context. But all of the polling kinds have one common part - they must test that event has occurred. And when we talk about OS it is not a good way of thinking when somebody hides real world under the hood of "an external source". Any external source must be implemented by OS developer, so it is just another part of OS, just another part of your work. If you forget one part of your work the entire work will be broken.

[Combuster]

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. In particular, you don't design, build, or implement the device - you simply trust that the device is taking the initiative when it should, and you respond to that.

Pull communication is a direct tradeoff between processing power and latency. Push communication lacks that relationship and turns both into fixed low values, and is therefore often the superior solution.

[max]

Hey folks, first I must say thank you for all the very good and helpful answers.

You're thinking like a desktop OS developer which is fine if you're developing a desktop OS. In other worlds, your assumptions sound a bit strange!

I do develop a desktop OS:) I'm trying to keep the design as microkernelish as possible, so the kernel itself is really only a message dispatcher and provides things like shared memory mapping to the processes, everything else is done in userspace.

Then, when an interrupt occurs, the process jumps into the handler. If the process has not returned from the handler, then stick it on a queue so it immediately handles the next interrupt when it returns, until no more interrupts are left.

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..

For this reason, I'm planning to use a set of bits (one bit per IRQ, per thread).

That's basically what I'm doing at the moment. When an interrupt comes in, I set this interrupt as "fired" in a bitmap, immediately send an EOI to the controller, and when a process asks if that interrupt has happend I just clear it in the bitmap. But how can I handle the case if the same interrupt happens again before some process asks for it?


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? For example:

- Some device fires an interrupt
- Kernel handler remembers this event, and sends an EOI to the interrupt controller
- Userspace programs continue as normal, but the specific driver for that device doesn't poll that interrupt/doesn't ask for the data from the device early enough, so it happens that
- the device fires another interrupt
Is the data for the first interrupt possibly lost? How can one work around this?