Understanding the FreeBSD locking mechanism

[Yubin Ruan]

On 2017/4/9 21:28, vasanth sabavat wrote:
>
> On Sun, Apr 9, 2017 at 3:14 AM Yubin Ruan <ablacktshirt at gmail.com
> <mailto: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
>     <mailto: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.

Can't the scheduler preempt thread B and put thread A to run? After all,
we did not disable interrupt.

regards,
Yubin Ruan

>
>     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 <mailto: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
>     <mailto:freebsd-hackers-unsubscribe at freebsd.org>"
>
> --
> Thanks,
> Vasanth