Understanding the FreeBSD locking mechanism

[vasanth sabavat]

On Sun, Apr 9, 2017 at 3:14 AM Yubin Ruan <ablacktshirt at gmail.com> wrote:

> On 2017/4/6 17:31, Ed Schouten wrote:
> > Hi Yubin,
> >
> > 2017-04-06 11:16 GMT+02:00 Yubin Ruan <ablacktshirt at gmail.com>:
> >> Does this function provides the ordinary "spinlock" functionality? There
> >> is no special "test-and-set" instruction, and neither any extra locking
> >> to protect internal data structure manipulation. Isn't this subjected to
> >> race condition?
> >
> > Locking a spinlock is done through macro mtx_lock_spin(), which
> > expands to __mtx_lock_spin() in sys/sys/mutex.h. That macro first
> > calls into the function you looked at, spinlock_enter(), to disable
> > interrupts. It then calls into the _mtx_obtain_lock_fetch() to do the
> > test-and-set operation you were looking for.
>
> Thanks for replying. I have read some of those codes.
>
> Just a few more questions, if you don't mind:
>
> (1) why are spinlocks forced to disable interrupt in FreeBSD?
>
>  From the book "The design and implementation of the FreeBSD Operating
> System", the authors say "spinning can result in deadlock if a thread
> interrupted the thread that held a mutex and then tried to acquire the
> mutex"...(section 4.3, Mutex Synchronization, paragraph 4)
>
> I don't get the point why a spinlock(or *spin mutex* in the FreeBSD
> world) has to disable interrupt. Being interrupted does not necessarily
> mean a deadlock. Assume that thread A holding a lock T gets interrupted
> by another thread B(context switch here) and thread B try to acquire
> the lock T. After finding out that lock T has already been acquired,
> thread B will just spin until it gets preempted, after which thread A
> gets waken up and run and release the lock T.


Assume single CPU, If thread B spins where will thread A get to run and
finish up its critical section and release the lock? The one CPU you have
is held by thread b for spinning.

For spin locks on single core, it does not make sense to spin. We just
disable interrupts as we are currently the only ones running we just need
to make sure no others will get to preempt us. That's why spin locks should
be held for short duration.

When you have multiple cores,  ThreadA can spin on cpu1, while thread B
holding the lock on cpu2 can finish up and release it. We disable
interrupts only on cpu1 so we don't want to preempt threadA. The cost of
preemption is very high compared to short spin. Note: short spin.

Look at adaptive spin locks.



So, you see there is not
> necessarily any deadlock even if thread A get interrupted.
>
> I can only remember two conditions where using spinlock without
> disabling interrupts will cause deadlock:
>
> #######1, spinlock used in an interrupt handler
> If a thread A holding a spinlock T get interrupted and the interrupt
> handler responsible for this interrupt try to acquire T, then we have
> deadlock, because A would never have a chance to run before the
> interrupt handler return, and the interrupt handler, unfortunately,
> will continue to spin ... so in this situation, one has to disable
> interrupt before spinning.
>
> As far as I know, in Linux, they provide two kinds of spinlocks:
>
>    spin_lock(..);   /* spinlock that does not disable interrupts */
>    spin_lock_irqsave(...); /* spinlock that disable local interrupt */
>
>
> #######2, priority inversion problem
> If thread B with a higher priority get in and try to acquire the lock
> that thread A currently holds, then thread B would spin, while at the
> same time thread A has no chance to run because it has lower priority,
> thus not being able to release the lock.
> (I haven't investigate enough into the source code, so I don't know
> how FreeBSD and Linux handle this priority inversion problem. Maybe
> they use priority inheritance or random boosting?)
>
> thanks,
> Yubin Ruan
> _______________________________________________
> freebsd-hackers at freebsd.org mailing list
> https://lists.freebsd.org/mailman/listinfo/freebsd-hackers
> To unsubscribe, send any mail to "freebsd-hackers-unsubscribe at freebsd.org"
>
-- 
Thanks,
Vasanth