Spinlocks and deadlocks

[eryjus]

Hi,

I hope I am posting in the right place for this question, and if not can one of the mods help me understand and relocate the thread.

It occurs to me that there is a condition in my code that may lead me to a deadlock when using spinlocks with multiple threads. Let me illustrate with a situation:
* Process 1 has a normal priority. It has successfully obtained a spinlock and while completing the section of work, gets preempted.
* Process 2 is a new process that immediately tries to obtain the same spinlock.
* Process 3 is also a new process that immediately tries to obtain the same spinlock.

The point is that in the above situation, Process 1 will never be granted CPU time to complete its work and release the spinlock, so a deadlock will occur. I have read the wiki http://wiki.osdev.org/Deadlock.

I have a couple of ideas that I have considered to resolve the concern:
1. Artificially and temporarily increase the priority of Process 1 to complete the work -- When the lock is released, the priority of the process would be returned to its normal state and could give up control. However, this may have a concern with my design that could impact other time-sensitive processes (such as future UI updates) and could lead to abuse.
2. Prevent preemption while Process 1 has the lock -- OK, not a great idea since it could lead to serious abuse.... but I thought about it.
3. Note which spinlock is being requested as Processes 2 & 3 attempt to lock and voluntarily give up control (putting the process into a spinlock-wait state) and then when Process 1 gives up the lock, ready the other Processes 2 & 3 and perform a reschedule -- might be a good solution, but does this violate the idea of a spinlock?
4. Modify #3 slightly so that the spinlock-wait state has no knowledge of which spinlock is being waited on -- when any spinlock (not necessarily the spinlock held by process 1) is released, all spinlock-waiting processes are ready'd, followed by a reschedule. I'm leaning toward this concept.

What other possibilities might I be missing? Also, what would be the better implementation?


Thanks for your replies.

[Owen]

In general, spinlocks which are held by code at differing priorities seems like a bad idea: they very quickly turn into something as expensive as a normal mutex. Spinlocks should probably only be used in cases where you're unable to use a normal mutex (e.g. inside the scheduler, or in code which may be called inside the scheduler) or between cooperating tasks. Otherwise, I'd say use a normal mutex.

For normal mutexes, what you outlined as "option 1" is the common (and most fair) solution. It means that a process at priority 3 can't be blocked by permanently a CPU bound process at priority 2 because a process at priority 1 took a mutex it shared. Think of it as the blocked process "donating its priority and timeslices" in order to be able to get back to its own work ASAP

[eryjus]

Think of it as the blocked process "donating its priority and timeslices" in order to be able to get back to its own work ASAP

Interesting....

Some time ago, I asked about context switching, and Brendan replied with this: http://forum.osdev.org/viewtopic.php?f= ... 52#p199880

Quoting from that reply:

Also, you'll find that "Reschedule()" is called from more than just the timer IRQ - for example, if a thread blocks for any reason (e.g. "sleep()", waiting for file IO, etc) then the kernel code that handles these things will call "Reschedule()" themselves. Once you upgrade to a better scheduling algorithm you'll probably also have cases where a high priority thread unblocks and you want it to preempt the currently running (lower priority) thread; and you'll want to switch directly to the high priority thread (without the extra overhead of deciding which thread to switch to, because you already know).

With the concept Brendan offered (and the implementation suggestion of a SwitchToProcess(pid) function) and with Owen's additional suggestion, anytime a higher priority process blocked waiting for a lock held by an equal or lower priority process, it would be simple for the GetLock() [fill in the proper flavor of Lock()] to simply yield the balance of its quantum to the process that holds the lock. It would get around the need to bump and lower priorities as it would be a scheduling rule in the design.

I'm curious about any other thoughts. Thanks again for your replies.

[gravaera]

Yo:

The most typical implementation of spinlocks is one where you disable IRQs while the lock is held. This way, all of the above considerations are precluded.

Code: Select all

void spin_lock(int *lock)
{
   local_irq_disable();
   while (atomic_xchg(lock, 1) != 0) { cpu_relax(); };
}

void spin_unlock(int *lock)
{
   atomic_xchg(lock, 0);
   local_irq_enable();
}

int myFunc(void)
{
   int i, j, k;

   i=0;
   j=setupJ();
   k=smp_processorid();

   spin_lock(&important_lock.lock);
   do_important_thing();
   signal_important_component();
   queue_important_operation();
   spin_unlock(&important_lock.lock);
   return 0;
}

You'll notice that I've used names similar to those used in the Linux source -- this is helpful to you because it will allow you to more effectively use/search Linux source for research, because unless you see locking in practice, it's challenging to understand the subtleties. The scheduler timer is not accepted until local IRQs are unmasked. Therefore no task can be pre-empted while it is executing code within a critical section. Any abstraction that goes beyond this generally has some form of mitigation or complex signaling to ensure that the situation you described above does not occur. As a rule however, critical sections should not be not long enough to require that you allow IRQs to come in while they are being executed. Also, by definition a critical section is a stretch of code that should not be interrupted

EDIT: So technically, the code for "myFunc()" above should look more like:

Code: Select all

int myFunc(void)
{
   int i, j, k;

   i=0;
   j=setupJ();
   k=smp_processorid();

   spin_lock(&shared_resource_or_hardware_register_lock.lock);
   do_important_thing_that_accesses_registers_or_shared_resource();
   spin_unlock(&shared_resource_or_hardware_register_lock.lock);

   queue_important_operation();
   signal_important_component();
   return 0;
}

--Peace out
gravaera

[eryjus]

Gravaera, thanks for your reply. What you illustrate in code is what I was envisioning in my thought #2. I will research the Linux code as you suggest, even though I am not trying to duplicate Linux.

Thanks

[evoex]

One potential warning about gravaera's code, though it may only have served as a proof of concept: the code will break when you nest spinlocks. Let's say you lock two spinlocks, and then one of them gets unlocked, such as:

Code: Select all

spin_lock(lock1);
...
spin_lock(lock2);
...
spin_unlock(lock2);

Now IRQs are enabled again, which could cause an interrupt to be executed before "spin_unlock(lock1);".

I'm not sure how common it is to need to nest spinlocks though.

[rdos]

I don't think you should nest spinlocks. The most obvious sulutions to the problem you presented are:

1. Disable scheduling. This is ok if the spinlock cannot be taken by IRQs. Works well even if the protected code is rather long. Might support nesting if the scheduler disable code can handle nesting

2. Disable interrupts. This works regardless of where the spinlocks are taken, but cannot handle nesting. It should be avoided if the protected code takes "too long" to execute (bad interrupt latency)

I use both types. The spinlocks that synchronize with IRQs use version #2, while the others use version #1.

Edit: In order for the spinlock that disable interrupts to be "well-behaved" it should enable interrupts again in situations of contention.

[JamesM]

2. Disable interrupts. This works regardless of where the spinlocks are taken, but cannot handle nesting. It should be avoided if the protected code takes "too long" to execute (bad interrupt latency)

Will break in an SMP environment.

There are legitimate situations in which you may need a reentrant spinlock; it's usual to provide a specific lock type for this case.

[rdos]

2. Disable interrupts. This works regardless of where the spinlocks are taken, but cannot handle nesting. It should be avoided if the protected code takes "too long" to execute (bad interrupt latency)

Will break in an SMP environment.

There are legitimate situations in which you may need a reentrant spinlock; it's usual to provide a specific lock type for this case.

I meant that the spinlock would be taken with interrupts disabled, not that disabling interrupts would be enough on SMP. That would not break on SMP.

[gerryg400]

Code that disables interrupts should save the old interrupt state during a spin_lock() and restore the state during spin_unlock(). That way spin_locks can be safely nested. Something like this perhaps ....

Code: Select all

static int inline spin_wrlock_irq(spinlock_t volatile *p_slock) {

    int int_enabled = rd_flags() & 0x200 ? 1 : 0;

    __cli();

    spin_wrlock(p_slock);

    return int_enabled;
}

static void inline spin_unlock_irq(spinlock_t volatile *p_slock, int int_enabled) {

    spin_unlock(p_slock);

    if (int_enabled) {
        __sti();
    }
}

You absolutely need to nest spinlocks in an SMP environment if you want to achieve any sort of concurrency. If you don't nest spinlocks then you are arguing for a big kernel lock, or perhaps a few biggish kernel locks.

Recursive spinlocks on the other hand are generally avoidable.

[evoex]

Code that disables interrupts should save the old interrupt state during a spin_lock() and restore the state during spin_unlock(). That way spin_locks can be safely nested. Something like this perhaps ....

Code: Select all

static int inline spin_wrlock_irq(spinlock_t volatile *p_slock) {

    int int_enabled = rd_flags() & 0x200 ? 1 : 0;

    __cli();

    spin_wrlock(p_slock);

    return int_enabled;
}

static void inline spin_unlock_irq(spinlock_t volatile *p_slock, int int_enabled) {

    spin_unlock(p_slock);

    if (int_enabled) {
        __sti();
    }
}

You absolutely need to nest spinlocks in an SMP environment if you want to achieve any sort of concurrency. If you don't nest spinlocks then you are arguing for a big kernel lock, or perhaps a few biggish kernel locks.

Recursive spinlocks on the other hand are generally avoidable.

Wouldn't it be easier/better to store the "int_enabled" state in the spinlock_t type? Then you don't need to store it in a separate variable...

[gerryg400]

Wouldn't it be easier/better to store the "int_enabled" state in the spinlock_t type? Then you don't need to store it in a separate variable...

If you prefer you can do it that way.

[eryjus]

Thanks everyone for your replies. A few things to think about, for sure.

Such as:

Code: Select all

static int inline spin_wrlock_irq(spinlock_t volatile *p_slock) {

    int int_enabled = rd_flags() & 0x200 ? 1 : 0;

    __cli();

    spin_wrlock(p_slock);

    return int_enabled;
}

static void inline spin_unlock_irq(spinlock_t volatile *p_slock, int int_enabled) {

    spin_unlock(p_slock);

    if (int_enabled) {
        __sti();
    }
}

You absolutely need to nest spinlocks in an SMP environment if you want to achieve any sort of concurrency.

But,

Code: Select all

int a = spin_wrlock_irq(locka);
int b = spin_wrlock_irq(lockb);
...
spin_unlock_irq(locka, a);  // or even, god forbid: unlock_irq(lockb, a);

... enables interrupts before all the locks are released, and we are back at the same question -- an opportunity to deadlock. To get around this, you would have to maintain a stack of interrupt flag states and pop them off as you unlock the spinlocks to ensure you didn't get into trouble, which feels like brute-force coding.

In my mind, I still go back to the elegance of what Owen suggested. It seems it would be a simple task to modify my spinlock structure to save the PID of the process holding the lock and when ever Process 2 or 3 attempt to get the lock while Process 1 has it, the process yields its time slice to the PID holding the lock. Process 1 would never actually get a bump in priority, and Processed 2 & 3 would never actually go to a blocked state. Once Process 1 released the lock, it could yield as well.

I get it that this solution would not resolve every deadlock situation, but can any algorithm really do that? (maybe for another thread...)

Thanks for the discussion!

[evoex]

But,

Code: Select all

int a = spin_wrlock_irq(locka);
int b = spin_wrlock_irq(lockb);
...
spin_unlock_irq(locka, a);  // or even, god forbid: unlock_irq(lockb, a);

... enables interrupts before all the locks are released, and we are back at the same question -- an opportunity to deadlock. To get around this, you would have to maintain a stack of interrupt flag states and pop them off as you unlock the spinlocks to ensure you didn't get into trouble, which feels like brute-force coding.

The line you comment is simply mis-use of the function. Sure, if you call a function wrong, you screw things up. But the actual code seems to unlock a before it unlocks b? I really can't imagine a case where this would be a good thing to do. Simply make sure you unlock b before you unlock a, and there is no problem. If you can't do this in your code's design, there's something wrong with the design.

[gerryg400]

Generally speaking this should be okay

Code: Select all

    lock(A)
    lock(B)
    unlock(A)
    ...
    unlock(B)

I do this occasionally in my kernel.

However, as you say, this does not work with lock_irq()/unlock_irq() unless those functions 'count' the cli/sti pairs.

It's not okay to take locks in different order. For example if you do this

Code: Select all

    lock(A)
    lock(B)

you can't do this elsewhere

Code: Select all

    lock(B)
    lock(A)

This means that in the first example above, you cannot do this

Code: Select all

    lock(A)
    lock(B)
    unlock(A)
    ...
    lock(A)  <== this might deadlock
    ...