Synchronization and interrupt handlers

[wichtounet]

Hi,

I'm having a hard time figuring out the best way to implementation synchronization when it involves an hardware interrupt handler and some process code.

The problem I see is that interrupt hanlder will not be interrupted. Here is an exemple:

Code: Select all

irq_handler:
   lock
   CS1
   unlock

A:
   lock
   CS2
   unlock

CS2 must put A to sleep and wake him up when CS1 is over.


If lock is implemented using a spinlock and the interrupt is launched just after A locked the code, it'll never go out of the interrupt.

On one of the cases, I implement a simple solution using Test-And-Set, but at this point there was only one process that could wait. What if I would like to implement a sleep queue where threads are woken from the sleep queue from an interrupt ? For instance, if process A is trying to add itself to the queue and at this point the queue is modified by the interrupt handler that modifies also the queue, we may have a problem with the state of queue.

Is there a synchronization primitive that works well in these cases ?
Or is it necessary to think of ways to solve each problem individually ?

Thanks

Baptiste

[Combuster]

Userspace should not hold kernel locks. Regular kernel code should not hold locks required by interrupts. The former because it's a privilege escalation, the latter because there's no concurrency.

What you typically want is to do something that requires no locks in the first place, or to disable interrupts so you can't get deadlocks from preempting critical sections.

[wichtounet]

Userspace should not hold kernel locks.

Sorry, I wasn't clear When I talked about user, I wanted to say process running in kernel via system call.

What you typically want is to do something that requires no locks in the first place, or to disable interrupts so you can't get deadlocks from preempting critical sections.

I would like to avoid disabling interrupts if possible.

Regular kernel code should not hold locks required by interrupts. ..., the latter because there's no concurrency.

I don't get why there wouldn't be any concurrency. What if both parts are manipulating the same datastructure. Let's say a linked list. The interrupt code cannot be in "interrupted" by the kernel code, but the kernel code can be interrupted by the interrupt, isn't it ? And so, the data must be protected. Is this problem typically solved by disabling interrupts ?

[jnc100]

Generally you will have this problem if one critical section protected by a certain lock is interruptible and the other one isn't. The fix is to either make both interruptible or neither interruptible. In your case, either run your interrupt handlers with interrupts enabled, or disable interrupts around the lock in the other part of the kernel that is using the lock.

The neither-interruptible case can be made not too bad latency-wise as long as the critical section is very small.

Regards,
John.

[Brendan]

Hi,

What if both parts are manipulating the same datastructure. Let's say a linked list. The interrupt code cannot be in "interrupted" by the kernel code, but the kernel code can be interrupted by the interrupt, isn't it ? And so, the data must be protected. Is this problem typically solved by disabling interrupts ?

Typically I have 2 types of spinlocks - one that disables task switches for that CPU, and one that disables both task switches and IRQs for that CPU. Any lock that is used by any IRQ handler uses the latter to avoid deadlocks (IRQ handler spinning until the code it interrupted releases the lock). An IRQ handler may still have to wait for code running on a different CPU to release the lock.

Also (because it's a micro-kernel) IRQ handlers only cause messages to be sent to device driver/s, so it's easy to determine which code is used from within an IRQ handler and make sure the right type of spinlock is used for those pieces of code, and most of the micro-kernel can use normal spinlocks that don't disable IRQs.

For a monolithic kernel (where an IRQ handler could call anything) it becomes more complicated - you might want to have a set of functions that can be used by IRQ handlers (that do use the "IRQ disabling locks") and forbid the use of any other functions within IRQ handlers. That set of allowed/safe functions may include a function that puts something on a queue and asks a scheduler to execute whatever you put on the queue later; so that complicated IRQ handlers can be split into "top half" (executed directly by IRQ handler and only able to use specific/safe functions) and "bottom half" (executed later when scheduled, and able to use functions that aren't safe for IRQ handlers). Most monolithic kernels do something like this - they just give it different names (e.g. it's called "deferred procedure calls" on Windows, and "tasklets" on Linux). Of course "putting something on a queue and asking scheduler to execute later" is essentially same as what a micro-kernel does (putting a message on a message queue).


Cheers,

Brendan

[Gigasoft]

For the thread ready queue, you must either disable interrupts, or update the queue in a way that does not require a lock, which is typically accomplished using exchange, exchange-add and compare-exchange operations.

[wichtounet]

Thanks all of you for your answers

Typically I have 2 types of spinlocks - one that disables task switches for that CPU, and one that disables both task switches and IRQs for that CPU. Any lock that is used by any IRQ handler uses the latter to avoid deadlocks (IRQ handler spinning until the code it interrupted releases the lock). An IRQ handler may still have to wait for code running on a different CPU to release the lock.

Also (because it's a micro-kernel) IRQ handlers only cause messages to be sent to device driver/s, so it's easy to determine which code is used from within an IRQ handler and make sure the right type of spinlock is used for those pieces of code, and most of the micro-kernel can use normal spinlocks that don't disable IRQs.

For a monolithic kernel (where an IRQ handler could call anything) it becomes more complicated - you might want to have a set of functions that can be used by IRQ handlers (that do use the "IRQ disabling locks") and forbid the use of any other functions within IRQ handlers. That set of allowed/safe functions may include a function that puts something on a queue and asks a scheduler to execute whatever you put on the queue later; so that complicated IRQ handlers can be split into "top half" (executed directly by IRQ handler and only able to use specific/safe functions) and "bottom half" (executed later when scheduled, and able to use functions that aren't safe for IRQ handlers). Most monolithic kernels do something like this - they just give it different names (e.g. it's called "deferred procedure calls" on Windows, and "tasklets" on Linux). Of course "putting something on a queue and asking scheduler to execute later" is essentially same as what a micro-kernel does (putting a message on a message queue)

I never thought of the difference between micro and monolithic kernel in that way. It is very interesting.

I think I will go with some deferred procedure call system. It sounds very practical and sane.

Generally you will have this problem if one critical section protected by a certain lock is interruptible and the other one isn't. The fix is to either make both interruptible or neither interruptible. In your case, either run your interrupt handlers with interrupts enabled, or disable interrupts around the lock in the other part of the kernel that is using the lock.

The neither-interruptible case can be made not too bad latency-wise as long as the critical section is very small.

That is much clearer to me now.

For the thread ready queue, you must either disable interrupts, or update the queue in a way that does not require a lock, which is typically accomplished
using exchange, exchange-add and compare-exchange operations.

Ok, that is what I thought.