Spinlocks and deadlocks

[eryjus]

The line you comment is simply mis-use of the function. Sure, if you call a function wrong, you screw things up. [...] 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.

Oh, I completely agree! The snippet of code is for illustration only and I can't imagine a reason to do that either... but, with that said, I wonder what if....?

[gerryg400]

The line you comment is simply mis-use of the function. Sure, if you call a function wrong, you screw things up. [...] 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.

Oh, I completely agree! The snippet of code is for illustration only and I can't imagine a reason to do that either... but, with that said, I wonder what if....?

'A' might be a lock for your process table, 'B' might be a lock on a particular entry in the table. In this case you might want to lock(A), lock(B), unlock(A), perform some work and finally unlock(B). I don't see anything wrong with that.

[rdos]

I disagree that it is necesary to have nestable spinlocks. IMO, spinlocks are the basics for synhronization used to build more complex synchronization functions like mutexes, which are nestable. Complex nested synchronization will thus use mutexes and not spinlocks, which would be far better in terms of interrupt latency (and scheduler latency), as the spinlock is only used when a mutex is taken and released, not during a complete nested operation. And each mutex has it's own spinlock, so there are no increased contention for spinlocks.

Then the bulk of the kernel synchronization is done by mutexes, and spinlocks are only used directly when there is a need to synchronize with IRQs.

[gerryg400]

rdos, to clarify ... does nestable mean recursive ? Or does it mean a core can only hold a single single spinlock ?

The types of primitives needed depends on the kernel design. A true microkernel might not need anything more complex than a simple spinlock because there is never any reason to lock other than to protect data structures. The longest held lock might be only a few lines of C.

[rdos]

rdos, to clarify ... does nestable mean recursive ?

No, it means nestable.

Or does it mean a core can only hold a single single spinlock ?

At least only a single spinlock that disables interrupts. The only nesting I use (in the scheduler), is first to request a spinlock that disables scheduler, and then a spinlock that disables interrupts. There were some issue with timers that might have benefitted from a nested "interrupt" spinlock, but it could be solved in alternative ways.

[JamesM]

rdos, to clarify ... does nestable mean recursive ?

No, it means nestable.

To me in terms of locks they're synonymous - could you please explain the difference as you see it?

[gerryg400]

For me, and I believe RDOS, nestable means that a thread may call spin_lock() while it already holds a different lock.

Recursive means that a thread may call spin_lock() more than once on the same lock and that the lock will 'count' the spin_lock() and spin_unlock() calls and not unlock until the count is zero.

[JamesM]

For me, and I believe RDOS, nestable means that a thread may call spin_lock() while it already holds a different lock.

Nah - by that definition, all spinlocks are nestable. Why wouldn't you be able to hold more than one lock at once? How would you solve the counting philosopher's problem then?

[Combuster]

Like you do with locks in general: manage them away.

The most efficient solution to the dining philosophers is after all buying extra chopsticks.

[Love4Boobies]

How would you solve the counting philosopher's problem then?

By using message-passing, of course. Locks aren't scalable so you should avoid them if you can.

[evoex]

The line you comment is simply mis-use of the function. Sure, if you call a function wrong, you screw things up. [...] 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.

Oh, I completely agree! The snippet of code is for illustration only and I can't imagine a reason to do that either... but, with that said, I wonder what if....?

'A' might be a lock for your process table, 'B' might be a lock on a particular entry in the table. In this case you might want to lock(A), lock(B), unlock(A), perform some work and finally unlock(B). I don't see anything wrong with that.

The piece of code he was talking about was the line in the comment:

Code: Select all

int a = spin_wrlock_irq(locka);
int b = spin_wrlock_irq(lockb);
...
unlock_irq(lockb, a);

Which is simply a mis-use of the function. It would enable interrupts again, even though you wouldn't want to. This is one of the reasons I said I thought it was a better solution to store the returned variable in the lock structure, rather than as a separate variable.

I do wonder what the best solution here is, though. I haven't done SMP, but how quickly can the kernel detect what processor it's running on? Maybe you could do something similar to this to allow for nested spinlocks:

Code: Select all

void spin_lock(spinlock_t *lock)
{
  if(!processor_locks[smp_getprocessor_id()]++)
    irq_disable();
  ...
}

void spin_unlock(spinlock_t *lock)
{
  if(!--processor_locks[smp_getprocessor_id()])
    irq_enable();
}

Would something like that be possible, without too much overhead? Or is this a Bad Idea?

[gerryg400]

You need to establish a quick way to identify the core that you are running on. The core ID can be stored in an internal register (e.g. TR) or in a core-local data segment.

Also remember that once a spinlock_irq is taken, the thread cannot migrate to another core so that simplifies the unlock code. After all, one of the reasons that we disabled interrupts was to prevent interference from the scheduler.

Your idea for counting the cli/sti will work fine. Whether it is necessary or not will depend on your kernel design.

[OSwhatever]

Sigh, I have a deadlock situation to deal with right now and it is not easy to find the root cause. The general question is often "who has taken that lock" and without any help it is very difficult to find out.

What kind of help do you use in order to investigate who has taken certain locks?

[Combuster]

If you want lock debugging, just add another 32/64-bit field after the rest of your mutex, and stick something in there that'll identify the thread. For locks in kernel space, logging the stackpointer might be an interesting choice.