Page 2 of 2
Re: Spinlocks and deadlocks
Posted: Mon Aug 20, 2012 8:37 pm
by eryjus
evoex wrote: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....?
Re: Spinlocks and deadlocks
Posted: Mon Aug 20, 2012 8:47 pm
by gerryg400
eryjus wrote:evoex wrote: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.
Re: Spinlocks and deadlocks
Posted: Tue Aug 21, 2012 12:26 am
by 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.
Re: Spinlocks and deadlocks
Posted: Tue Aug 21, 2012 12:45 am
by 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.
Re: Spinlocks and deadlocks
Posted: Tue Aug 21, 2012 1:21 am
by rdos
gerryg400 wrote:rdos, to clarify ... does nestable mean recursive ?
No, it means nestable.
gerryg400 wrote: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.
Re: Spinlocks and deadlocks
Posted: Tue Aug 21, 2012 1:38 am
by JamesM
rdos wrote:gerryg400 wrote: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?
Re: Spinlocks and deadlocks
Posted: Tue Aug 21, 2012 1:52 am
by 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.
Re: Spinlocks and deadlocks
Posted: Tue Aug 21, 2012 2:38 am
by 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?
Re: Spinlocks and deadlocks
Posted: Tue Aug 21, 2012 2:43 am
by 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.
Re: Spinlocks and deadlocks
Posted: Tue Aug 21, 2012 2:57 am
by Love4Boobies
JamesM wrote: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.
Re: Spinlocks and deadlocks
Posted: Tue Aug 21, 2012 2:58 pm
by evoex
gerryg400 wrote:eryjus wrote:evoex wrote: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?
Re: Spinlocks and deadlocks
Posted: Tue Aug 21, 2012 4:00 pm
by 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.
Re: Spinlocks and deadlocks
Posted: Wed Aug 22, 2012 7:12 am
by 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?
Re: Spinlocks and deadlocks
Posted: Wed Aug 22, 2012 7:17 am
by 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.