This is an archived copy of the Xen.org mailing list, which we have preserved to ensure that existing links to archives are not broken. The live archive, which contains the latest emails, can be found at http://lists.xen.org/
Home Products Support Community News


[Xen-devel] Re: [PATCH RFC 10/12] x86/pvticketlock: keep count of blocke

To: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Subject: [Xen-devel] Re: [PATCH RFC 10/12] x86/pvticketlock: keep count of blocked cpus
From: Jeremy Fitzhardinge <jeremy@xxxxxxxx>
Date: Tue, 03 Aug 2010 08:45:26 -0700
Cc: Nick Piggin <npiggin@xxxxxxx>, Xen-devel <xen-devel@xxxxxxxxxxxxxxxxxxx>, Linux Kernel Mailing List <linux-kernel@xxxxxxxxxxxxxxx>, Jan Beulich <JBeulich@xxxxxxxxxx>, Avi Kivity <avi@xxxxxxxxxx>
Delivery-date: Tue, 03 Aug 2010 08:46:08 -0700
Envelope-to: www-data@xxxxxxxxxxxxxxxxxxx
In-reply-to: <1280824360.1923.421.camel@laptop>
List-help: <mailto:xen-devel-request@lists.xensource.com?subject=help>
List-id: Xen developer discussion <xen-devel.lists.xensource.com>
List-post: <mailto:xen-devel@lists.xensource.com>
List-subscribe: <http://lists.xensource.com/mailman/listinfo/xen-devel>, <mailto:xen-devel-request@lists.xensource.com?subject=subscribe>
List-unsubscribe: <http://lists.xensource.com/mailman/listinfo/xen-devel>, <mailto:xen-devel-request@lists.xensource.com?subject=unsubscribe>
References: <cover.1279328276.git.jeremy.fitzhardinge@xxxxxxxxxx> <9d5625e61c7f35e72156e8cb881e55910b4fa5dc.1279328276.git.jeremy.fitzhardinge@xxxxxxxxxx> <1280824360.1923.421.camel@laptop>
Sender: xen-devel-bounces@xxxxxxxxxxxxxxxxxxx
User-agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv: Gecko/20100720 Fedora/3.1.1-1.fc13 Lightning/1.0b2pre Thunderbird/3.1.1
 On 08/03/2010 01:32 AM, Peter Zijlstra wrote:
On Fri, 2010-07-16 at 18:03 -0700, Jeremy Fitzhardinge wrote:
@@ -26,6 +26,9 @@ typedef struct arch_spinlock {
                         __ticket_t head, tail;
                 } tickets;
+       __ticket_t waiting;
  } arch_spinlock_t;
This bloats spinlock_t from u32 to u64 on most distro configs I think,
since they'll have NR_CPUS=4096 or something large like that and
probably also want to have this PARAVIRT_SPINLOCKS thing.

Yes, it is very unfortunate. In principle I could make it work with a single bit: set it when a cpu blocks and will need kicking; clear it when the lock becomes uncontended again (since everything is FIFO, so if something blocks itself there's a good chance that everything afterwards will also decide to block). But a bit takes as much space as a word (and it isn't obvious to me how to implement the "clearing when it becomes uncontended" part in a race-free way). (But see below for some handwaving)

I could store this out in a secondary structure, but it really needs to be efficient to access from the unlock fast-path (to determine whether it needs to do the slow-path kick), so something out of line isn't going to work.

Without the separate "waiting" counter, the previous code just checked to see if there was anyone else has a ticket on the lock. This is too pessimistic, since it isn't all that uncommon to have someone else who has been waiting on the lock for a little while, but has not yet decided to block themselves, and it results in many spurious calls into the unlock slow path.

I was thinking of getting a bit in the ticket lock structure by stealing a counter bit: halve the supported number of cpus (128 for byte, 32k for word), add/sub 2, and use the LSB for the "needs kicking" flag. And that actually gives us two bits to play with, which may be useful for dealing with the clearing race (perhaps can be done cleverly in the unlock itself, or something). But I haven't thought this through in detail.


Xen-devel mailing list

<Prev in Thread] Current Thread [Next in Thread>