Re: [RFC PATCHv1] Prototype ticket locks

[David Vrabel <david.vrabel@citrix.com>]

On 03/02/15 13:55, Jan Beulich wrote:
>>>> On 03.02.15 at 12:50, <david.vrabel@citrix.com> wrote:
>> Use ticket locks for spin locks instead of the current byte locks.
>> Ticket locks are fair.  This is an important property for hypervisor
>> locks.
> 
> Isn't Linux moving to queue locks? Shouldn't we skip the intermediate
> step then, not the least because they will cause problems when Xen
> itself gets run virtualized?

ticket locks are trivial.  Why should we wait for the mythical future
where someone implements queue locks to actually get better/fairer locks?

I also don't think the characteristics of queue locks vs ticket locks
are really any different in a virtualized guest.  FWIW, the latest Linux
queue lock series falls back to byte locks in non-PV-aware guests.

>> This prototype has the following limitations:
>> - Only 256 CPUs (8 bit tickets).
>> - Broken lock profiling.
>> - x86 only.
>>
>> Note that spin_lock_irq() and spin_lock_irqsave() now spin with irqs
>> disabled (previously, they would spin with irqs enabled if possible).
>> This is required to prevent deadlocks when the irq handler tries to
>> take the same lock with a higher ticket.
> 
> That's another pretty undesirable property (albeit it's not a strict
> implication of using ticket locks - one can make them work with
> interrupts getting properly re-enabled while spinning).

I've seen too many Linux deadlocks caused be re-enabling irqs while
spinning to consider this a good idea.  The ticket stealing stuff that
Suse kernels do doesn't play nice with rw locks or certain hand rolled
synchronization code (in short, if the interrupt spins on something
other than a ticket lock it breaks).

> It was for these reasons that so far I didn't go and steal Linux'es
> ticket lock implementation (and I think you should at least mention
> the origin in the description).

Sorry, this was taken (almost as-is) from Nick Piggin's Linux
implementation.

David