Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
On 16.11.10 at 22:08, Jeremy Fitzhardinge jer...@goop.org wrote: +static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want) { - struct xen_spinlock *xl = (struct xen_spinlock *)lock; - struct xen_spinlock *prev; int irq = __get_cpu_var(lock_kicker_irq); - int ret; + struct xen_lock_waiting *w = __get_cpu_var(lock_waiting); + int cpu = smp_processor_id(); u64 start; /* If kicker interrupts not initialized yet, just spin */ if (irq == -1) - return 0; + return; start = spin_time_start(); - /* announce we're spinning */ - prev = spinning_lock(xl); + w-want = want; + w-lock = lock; + + /* This uses set_bit, which atomic and therefore a barrier */ + cpumask_set_cpu(cpu, waiting_cpus); Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state? Jan ___ Virtualization mailing list Virtualization@lists.linux-foundation.org https://lists.linux-foundation.org/mailman/listinfo/virtualization
Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
On 11/17/2010 12:11 AM, Jan Beulich wrote: On 16.11.10 at 22:08, Jeremy Fitzhardinge jer...@goop.org wrote: +static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev; int irq = __get_cpu_var(lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = __get_cpu_var(lock_waiting); +int cpu = smp_processor_id(); u64 start; /* If kicker interrupts not initialized yet, just spin */ if (irq == -1) -return 0; +return; start = spin_time_start(); -/* announce we're spinning */ -prev = spinning_lock(xl); +w-want = want; +w-lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu(cpu, waiting_cpus); Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state? Yes, I think you're right - interrupts need to be disabled for the bulk of this function. J ___ Virtualization mailing list Virtualization@lists.linux-foundation.org https://lists.linux-foundation.org/mailman/listinfo/virtualization
Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
On 11/17/2010 12:52 AM, Jeremy Fitzhardinge wrote: On 11/17/2010 12:11 AM, Jan Beulich wrote: On 16.11.10 at 22:08, Jeremy Fitzhardinge jer...@goop.org wrote: +static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want) { - struct xen_spinlock *xl = (struct xen_spinlock *)lock; - struct xen_spinlock *prev; int irq = __get_cpu_var(lock_kicker_irq); - int ret; + struct xen_lock_waiting *w = __get_cpu_var(lock_waiting); + int cpu = smp_processor_id(); u64 start; /* If kicker interrupts not initialized yet, just spin */ if (irq == -1) - return 0; + return; start = spin_time_start(); - /* announce we're spinning */ - prev = spinning_lock(xl); + w-want = want; + w-lock = lock; + + /* This uses set_bit, which atomic and therefore a barrier */ + cpumask_set_cpu(cpu, waiting_cpus); Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state? Yes, I think you're right - interrupts need to be disabled for the bulk of this function. Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting. Another issue may be making sure the writes and reads of w-want and w-lock are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung. J ___ Virtualization mailing list Virtualization@lists.linux-foundation.org https://lists.linux-foundation.org/mailman/listinfo/virtualization
Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
On 17.11.10 at 10:57, Jeremy Fitzhardinge jer...@goop.org wrote: On 11/17/2010 12:52 AM, Jeremy Fitzhardinge wrote: On 11/17/2010 12:11 AM, Jan Beulich wrote: On 16.11.10 at 22:08, Jeremy Fitzhardinge jer...@goop.org wrote: +static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want) { - struct xen_spinlock *xl = (struct xen_spinlock *)lock; - struct xen_spinlock *prev; int irq = __get_cpu_var(lock_kicker_irq); - int ret; + struct xen_lock_waiting *w = __get_cpu_var(lock_waiting); + int cpu = smp_processor_id(); u64 start; /* If kicker interrupts not initialized yet, just spin */ if (irq == -1) - return 0; + return; start = spin_time_start(); - /* announce we're spinning */ - prev = spinning_lock(xl); + w-want = want; + w-lock = lock; + + /* This uses set_bit, which atomic and therefore a barrier */ + cpumask_set_cpu(cpu, waiting_cpus); Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state? Yes, I think you're right - interrupts need to be disabled for the bulk of this function. Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting. That's not my main concern. Instead, what if you get interrupted anywhere here, the interrupt handler tries to acquire another spinlock and also has to go into the slow path? It'll overwrite part or all of the outer context's state. Another issue may be making sure the writes and reads of w-want and w-lock are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung. Yes, proper operation sequence (and barriers) is certainly required here. If you allowed nesting, this may even become simpler (as you'd have a single write making visible the new head pointer, after having written all relevant fields of the new head structure). Jan ___ Virtualization mailing list Virtualization@lists.linux-foundation.org https://lists.linux-foundation.org/mailman/listinfo/virtualization
Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
On 11/17/2010 02:34 AM, Jan Beulich wrote: Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting. That's not my main concern. Instead, what if you get interrupted anywhere here, the interrupt handler tries to acquire another spinlock and also has to go into the slow path? It'll overwrite part or all of the outer context's state. That doesn't matter if the outer context doesn't end up blocking. If it has already blocked then it will unblock as a result of the interrupt; if it hasn't yet blocked, then the inner context will leave the event pending and cause it to not block. Either way, it no longer uses or needs that per-cpu state: it will return to the spin loop and (maybe) get re-entered, setting it all up again. I think there is a problem with the code as posted because it sets up the percpu data before clearing the pending event, so it can end up blocking with bad percpu data. Another issue may be making sure the writes and reads of w-want and w-lock are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung. Yes, proper operation sequence (and barriers) is certainly required here. If you allowed nesting, this may even become simpler (as you'd have a single write making visible the new head pointer, after having written all relevant fields of the new head structure). Yes, simple nesting should be quite straightforward (ie allowing an interrupt handler to take some other lock than the one the outer context is waiting on). J ___ Virtualization mailing list Virtualization@lists.linux-foundation.org https://lists.linux-foundation.org/mailman/listinfo/virtualization
[PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
From: Jeremy Fitzhardinge jeremy.fitzhardi...@citrix.com Replace the old Xen implementation of PV spinlocks with and implementation of xen_lock_spinning and xen_unlock_kick. xen_lock_spinning simply registers the cpu in its entry in lock_waiting, adds itself to the waiting_cpus set, and blocks on an event channel until the channel becomes pending. xen_unlock_kick searches the cpus in waiting_cpus looking for the one which next wants this lock with the next ticket, if any. If found, it kicks it by making its event channel pending, which wakes it up. Signed-off-by: Jeremy Fitzhardinge jeremy.fitzhardi...@citrix.com --- arch/x86/xen/spinlock.c | 281 ++- 1 files changed, 36 insertions(+), 245 deletions(-) diff --git a/arch/x86/xen/spinlock.c b/arch/x86/xen/spinlock.c index 3d9da72..5feb897 100644 --- a/arch/x86/xen/spinlock.c +++ b/arch/x86/xen/spinlock.c @@ -19,32 +19,21 @@ #ifdef CONFIG_XEN_DEBUG_FS static struct xen_spinlock_stats { - u64 taken; u32 taken_slow; - u32 taken_slow_nested; u32 taken_slow_pickup; u32 taken_slow_spurious; - u32 taken_slow_irqenable; - u64 released; u32 released_slow; u32 released_slow_kicked; #define HISTO_BUCKETS 30 - u32 histo_spin_total[HISTO_BUCKETS+1]; - u32 histo_spin_spinning[HISTO_BUCKETS+1]; u32 histo_spin_blocked[HISTO_BUCKETS+1]; - u64 time_total; - u64 time_spinning; u64 time_blocked; } spinlock_stats; static u8 zero_stats; -static unsigned lock_timeout = 1 10; -#define TIMEOUT lock_timeout - static inline void check_zero(void) { if (unlikely(zero_stats)) { @@ -73,22 +62,6 @@ static void __spin_time_accum(u64 delta, u32 *array) array[HISTO_BUCKETS]++; } -static inline void spin_time_accum_spinning(u64 start) -{ - u32 delta = xen_clocksource_read() - start; - - __spin_time_accum(delta, spinlock_stats.histo_spin_spinning); - spinlock_stats.time_spinning += delta; -} - -static inline void spin_time_accum_total(u64 start) -{ - u32 delta = xen_clocksource_read() - start; - - __spin_time_accum(delta, spinlock_stats.histo_spin_total); - spinlock_stats.time_total += delta; -} - static inline void spin_time_accum_blocked(u64 start) { u32 delta = xen_clocksource_read() - start; @@ -105,214 +78,76 @@ static inline u64 spin_time_start(void) return 0; } -static inline void spin_time_accum_total(u64 start) -{ -} -static inline void spin_time_accum_spinning(u64 start) -{ -} static inline void spin_time_accum_blocked(u64 start) { } #endif /* CONFIG_XEN_DEBUG_FS */ -struct xen_spinlock { - unsigned char lock; /* 0 - free; 1 - locked */ - unsigned short spinners;/* count of waiting cpus */ +struct xen_lock_waiting { + struct arch_spinlock *lock; + __ticket_t want; }; static DEFINE_PER_CPU(int, lock_kicker_irq) = -1; +static DEFINE_PER_CPU(struct xen_lock_waiting, lock_waiting); +static cpumask_t waiting_cpus; -#if 0 -static int xen_spin_is_locked(struct arch_spinlock *lock) -{ - struct xen_spinlock *xl = (struct xen_spinlock *)lock; - - return xl-lock != 0; -} - -static int xen_spin_is_contended(struct arch_spinlock *lock) -{ - struct xen_spinlock *xl = (struct xen_spinlock *)lock; - - /* Not strictly true; this is only the count of contended - lock-takers entering the slow path. */ - return xl-spinners != 0; -} - -static int xen_spin_trylock(struct arch_spinlock *lock) -{ - struct xen_spinlock *xl = (struct xen_spinlock *)lock; - u8 old = 1; - - asm(xchgb %b0,%1 - : +q (old), +m (xl-lock) : : memory); - - return old == 0; -} - -static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners); - -/* - * Mark a cpu as interested in a lock. Returns the CPU's previous - * lock of interest, in case we got preempted by an interrupt. - */ -static inline struct xen_spinlock *spinning_lock(struct xen_spinlock *xl) -{ - struct xen_spinlock *prev; - - prev = __get_cpu_var(lock_spinners); - __get_cpu_var(lock_spinners) = xl; - - wmb(); /* set lock of interest before count */ - - asm(LOCK_PREFIX incw %0 - : +m (xl-spinners) : : memory); - - return prev; -} - -/* - * Mark a cpu as no longer interested in a lock. Restores previous - * lock of interest (NULL for none). - */ -static inline void unspinning_lock(struct xen_spinlock *xl, struct xen_spinlock *prev) -{ - asm(LOCK_PREFIX decw %0 - : +m (xl-spinners) : : memory); - wmb(); /* decrement count before restoring lock */ - __get_cpu_var(lock_spinners) = prev; -} - -static noinline int xen_spin_lock_slow(struct arch_spinlock *lock, bool irq_enable) +static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want) { - struct xen_spinlock *xl =