linux-kernel - Re: Preemptable Ticket Spinlock

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Tue, 23 Apr 2013 07:24:44 +0530
From:	Raghavendra K T <raghavendra.kt@...ux.vnet.ibm.com>
To:	Jiannan Ouyang <ouyang@...pitt.edu>
CC:	LKML <linux-kernel@...r.kernel.org>,
	Peter Zijlstra <peterz@...radead.org>,
	Avi Kivity <avi.kivity@...il.com>,
	Gleb Natapov <gleb@...hat.com>, Ingo Molnar <mingo@...hat.com>,
	Marcelo Tosatti <mtosatti@...hat.com>,
	Rik van Riel <riel@...hat.com>,
	Srikar <srikar@...ux.vnet.ibm.com>,
	"H. Peter Anvin" <hpa@...or.com>,
	"Nikunj A. Dadhania" <nikunj@...ux.vnet.ibm.com>,
	KVM <kvm@...r.kernel.org>, Thomas Gleixner <tglx@...utronix.de>,
	Chegu Vinod <chegu_vinod@...com>,
	"Andrew M. Theurer" <habanero@...ux.vnet.ibm.com>,
	Srivatsa Vaddagiri <srivatsa.vaddagiri@...il.com>,
	Andrew Jones <drjones@...hat.com>
Subject: Re: Preemptable Ticket Spinlock

On 04/22/2013 10:12 PM, Jiannan Ouyang wrote:
> On Mon, Apr 22, 2013 at 1:58 AM, Raghavendra K T
> <raghavendra.kt@...ux.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 ?

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/