Re: Preemptable Ticket Spinlock

[Raghavendra K T <raghavendra.kt@linux.vnet.ibm.com>]

On 04/22/2013 10:12 PM, Jiannan Ouyang wrote:
> On Mon, Apr 22, 2013 at 1:58 AM, Raghavendra K T
> <raghavendra.kt@linux.vnet.ibm.com> wrote:

[...]

>>>    static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
>>>    {
>>>           register struct __raw_tickets inc = { .tail = 1 };
>>> +       unsigned int timeout = 0;
>>> +       __ticket_t current_head;
>>>
>>>           inc = xadd(&lock->tickets, inc);
>>> -
>>> +       if (likely(inc.head == inc.tail))
>>> +               goto spin;
>>> +
>>> +       timeout =  TIMEOUT_UNIT * (inc.tail - inc.head);

Forgot to mention about this, for immediate wait case,
you can busyloop instead of timeout (I mean

timeout =  TIMEOUT_UNIT * (inc.tail - inc.head -1);

This ideas was used by Rik in his spinlock  backoff patches.

>>> +       do {
>>> +               current_head = ACCESS_ONCE(lock->tickets.head);
>>> +               if (inc.tail <= current_head) {
>>> +                       goto spin;
>>> +               } else if (inc.head != current_head) {
>>> +                       inc.head = current_head;
>>> +                       timeout =  TIMEOUT_UNIT * (inc.tail - inc.head);
>>
>>
>> Good idea indeed to base the loop on head and tail difference.. But for
>> virtualization I believe this "directly proportional notion" is little
>> tricky too.
>>
>
> Could you explain your concern a little bit more?
>

Consider a big machine with 2 VMs running.
If nth vcpu of say VM1 waiting in the queue, the question is,

Do we have to have all the n VCPU doing busyloop and thus burning
sigma (n*(n+1) * TIMEOUT_UNIT)) ?

OR

Is it that, far off vcpu in the queue worth giving his time back so that 
probably some other vcpu of VM1 doing good work OR vcpu of VM2 can 
benefit from this.

I mean far the vcpu in the queue, let him yield voluntarily. (inversely 
proportional notion just because it is vcpu). and of course for some n < 
THRESHOLD we can still have directly proportional wait idea.

Does this idea sound good ?