Skip to contentSkip to conversation

Paravirtual spinlocks

RFC PATCH In review Jeremy Fitzhardinge 5 participants 38 messages Jul 7, 2008 – Jul 9, 2008

Subsystems (5)
x86 virtio core Xen hypervisor interface Xen hypervisor x86 +1 more subsystems
lore
Share & tools
lore

Jeremy Fitzhardinge

author
#0 lore raw

cover Paravirtual spinlocks

At the most recent Xen Summit, Thomas Friebel presented a paper ("Preventing Guests from Spinning Around",
http://xen.org/files/xensummitboston08/LHP.pdf) investigating the interactions between spinlocks and virtual machines. Specifically, he looked at what happens when a lock-holding VCPU gets involuntarily preempted.

The obvious first order effect is that while the VCPU is not running, the effective critical region time goes from being microseconds to milliseconds, until it gets scheduled again. This increases the chance that there will be be contention, and the contending VCPU will waste time spinning.

This is a measurable effect, but not terribly serious. After all, since Linux tends to hold locks for very short periods of time, the likelihood of being preempted while holding a lock is low.

The real eye-opener is the secondary effects specific to ticket locks.

Clearly ticket locks suffer the same problem as all spinlocks. But when the lock holder releases the lock, the real fun begins.

By design, ticket locks are strictly fair, by imposing a FIFO order lock holders. The micro-architectural effect of this is that the lock cache line will bounce around between the contending CPUs until it finds the next in line, who then takes the lock and carries on.

When running in a virtual machine, a similar effect happens at the VCPU level. If all the contending VCPUs are not currently running on real CPUs, then VCPU scheduler will run some random subset of them. If it isn't a given VCPUs turn to take the lock, it will spin, burning a VCPU timeslice. Eventually the next-in-line will get scheduled, take the lock, release it, and the remaining contending VCPUs will repeat the process until the next in line is scheduled.

This means that the effective contention time of the lock is not merely the time if takes the original lock-holder to take and release the lock - including any preemption it may suffer - but the spin-scheduling storm that follows to schedule the right VCPU to next take the lock. This could happen if the original contention was not as a result of preemption, but just normal spinlock level contention.

One of the results Thomas presents is a kernbench run which normally takes less than a minute going for 45 minutes, with 99+% spent in ticket lock contention. I've reproduced similar results.

This series has:
- a paravirt_ops spinlock interface, which defaults to the standard ticket lock algorithm,
- a second spinlock implementation based on the pre-ticket-lock "lock-byte" algorithm,
- And a Xen-specific spinlock algorithm which voluntarily preempts a VCPU if it spins for too long. [FOR REFERENCE ONLY: will not apply to a current git tree.]

When running on native hardware, the overhead of enabling CONFIG_PARAVIRT is an extra direct call/return on the lock/unlock paths; the paravirt-ops patching machinery eliminates any indirect calls. With a small amount of restructuring, this overhead could be eliminated (by making spin_lock()/unlock() inline functions, containing calls to __raw_spin_lock/unlock).

My experiments show that using a Xen-specific lock helps guest performance a bit (reduction in elapsed and system time in a kernbench run), but most significantly, reduces overall physical CPU consumption by 10%, and so increases overall system scalability.

J

author
#1 lore raw

RFC PATCH 1/4 x86/paravirt: add hooks for spinlock operations

Ticket spinlocks have absolutely ghastly worst-case performance characteristics in a virtual environment. If there is any contention for physical CPUs (ie, there are more runnable vcpus than cpus), then ticket locks can cause the system to end up spending 90+% of its time spinning.

The problem is that (v)cpus waiting on a ticket spinlock will be granted access to the lock in strict order they got their tickets. If the hypervisor scheduler doesn't give the vcpus time in that order, they will burn timeslices waiting for the scheduler to give the right vcpu some time. In the worst case it could take O(n^2) vcpu scheduler timeslices for everyone waiting on the lock to get it, not counting new cpus trying to take the lock while the log-jam is sorted out.

These hooks allow a paravirt backend to replace the spinlock implementation.

At the very least, this could revert the implementation back to the old lock algorithm, which allows the next scheduled vcpu to take the lock, and has basically fairly good performance.

It also allows the spinlocks to take advantages of the hypervisor features to make locks more efficient (spin and block, for example).

The cost to native execution is an extra direct call when using a spinlock function. There's no overhead if CONFIG_PARAVIRT is turned off.

The lock structure is fixed at a single "unsigned int", initialized to zero, but the spinlock implementation can use it as it wishes.

Thanks to Thomas Friebel's Xen Summit talk "Preventing Guests from Spinning Around" for pointing out this problem.

Signed-off-by Jeremy Fitzhardinge <[email protected]>
Cc Nick Piggin <[email protected]>
Cc Thomas Friebel <[email protected]>
---
 arch/x86/kernel/paravirt.c       |   10 ++++++
 include/asm-x86/paravirt.h       |   37 +++++++++++++++++++++++++
 include/asm-x86/spinlock.h       |   55 +++++++++++++++++++++++++++-----------
 include/asm-x86/spinlock_types.h |    2 -
 4 files changed, 88 insertions(+), 16 deletions(-)

===================================================================

arch/x86/kernel/paravirt.c +10 -0
@@ -123,6 +123,7 @@
 		.pv_irq_ops = pv_irq_ops,
 		.pv_apic_ops = pv_apic_ops,
 		.pv_mmu_ops = pv_mmu_ops,
+		.pv_lock_ops = pv_lock_ops,
 	};
 	return *((void **)&tmpl + type);
 }

@@ -445,6 +446,15 @@
 	.set_fixmap = native_set_fixmap,
 };
 
+struct pv_lock_ops pv_lock_ops = {
+	.spin_is_locked = __ticket_spin_is_locked,
+	.spin_is_contended = __ticket_spin_is_contended,
+
+	.spin_lock = __ticket_spin_lock,
+	.spin_trylock = __ticket_spin_trylock,
+	.spin_unlock = __ticket_spin_unlock,
+};
+
 EXPORT_SYMBOL_GPL(pv_time_ops);
 EXPORT_SYMBOL    (pv_cpu_ops);
 EXPORT_SYMBOL    (pv_mmu_ops);

===================================================================

include/asm-x86/paravirt.h +37 -0
@@ -329,6 +329,15 @@
 			   unsigned long phys, pgprot_t flags);
 };
 
+struct raw_spinlock;
+struct pv_lock_ops {
+	int (*spin_is_locked)(struct raw_spinlock *lock);
+	int (*spin_is_contended)(struct raw_spinlock *lock);
+	void (*spin_lock)(struct raw_spinlock *lock);
+	int (*spin_trylock)(struct raw_spinlock *lock);
+	void (*spin_unlock)(struct raw_spinlock *lock);
+};
+
 /* This contains all the paravirt structures: we get a convenient
  * number for each function using the offset which we use to indicate
  * what to patch. */

@@ -339,6 +348,7 @@
 	struct pv_irq_ops pv_irq_ops;
 	struct pv_apic_ops pv_apic_ops;
 	struct pv_mmu_ops pv_mmu_ops;
+	struct pv_lock_ops pv_lock_ops;
 };
 
 extern struct pv_info pv_info;

@@ -348,6 +358,7 @@
 extern struct pv_irq_ops pv_irq_ops;
 extern struct pv_apic_ops pv_apic_ops;
 extern struct pv_mmu_ops pv_mmu_ops;
+extern struct pv_lock_ops pv_lock_ops;
 
 #define PARAVIRT_PATCH(x)					\
 	(offsetof(struct paravirt_patch_template, x) / sizeof(void *))

@@ -1377,6 +1388,31 @@
 void _paravirt_nop(void);
 #define paravirt_nop	((void *)_paravirt_nop)
 
+static inline int __raw_spin_is_locked(struct raw_spinlock *lock)
+{
+	return PVOP_CALL1(int, pv_lock_ops.spin_is_locked, lock);
+}
+
+static inline int __raw_spin_is_contended(struct raw_spinlock *lock)
+{
+	return PVOP_CALL1(int, pv_lock_ops.spin_is_contended, lock);
+}
+
+static __always_inline void __raw_spin_lock(struct raw_spinlock *lock)
+{
+	return PVOP_VCALL1(pv_lock_ops.spin_lock, lock);
+}
+
+static __always_inline int __raw_spin_trylock(struct raw_spinlock *lock)
+{
+	return PVOP_CALL1(int, pv_lock_ops.spin_trylock, lock);
+}
+
+static __always_inline void __raw_spin_unlock(struct raw_spinlock *lock)
+{
+	return PVOP_VCALL1(pv_lock_ops.spin_unlock, lock);
+}
+
 /* These all sit in the .parainstructions section to tell us what to patch. */
 struct paravirt_patch_site {
 	u8 *instr; 		/* original instructions */

@@ -1461,6 +1497,7 @@
 	return f;
 }
 
+
 /* Make sure as little as possible of this mess escapes. */
 #undef PARAVIRT_CALL
 #undef __PVOP_CALL

===================================================================

include/asm-x86/spinlock.h +40 -15

127 lines not on this page · raw message

===================================================================

include/asm-x86/spinlock_types.h +1 -1
@@ -5,7 +5,7 @@
 # error "please don't include this file directly"
 #endif
 
-typedef struct {
+typedef struct raw_spinlock {
 	unsigned int slock;
 } raw_spinlock_t;
author
#2 lore raw

RFC PATCH 1/4 x86/paravirt: add hooks for spinlock operations

In reply to Jeremy Fitzhardinge

Ticket spinlocks have absolutely ghastly worst-case performance characteristics in a virtual environment. If there is any contention for physical CPUs (ie, there are more runnable vcpus than cpus), then ticket locks can cause the system to end up spending 90+% of its time spinning.

The problem is that (v)cpus waiting on a ticket spinlock will be granted access to the lock in strict order they got their tickets. If the hypervisor scheduler doesn't give the vcpus time in that order, they will burn timeslices waiting for the scheduler to give the right vcpu some time. In the worst case it could take O(n^2) vcpu scheduler timeslices for everyone waiting on the lock to get it, not counting new cpus trying to take the lock while the log-jam is sorted out.

These hooks allow a paravirt backend to replace the spinlock implementation.

At the very least, this could revert the implementation back to the old lock algorithm, which allows the next scheduled vcpu to take the lock, and has basically fairly good performance.

It also allows the spinlocks to take advantages of the hypervisor features to make locks more efficient (spin and block, for example).

The cost to native execution is an extra direct call when using a spinlock function. There's no overhead if CONFIG_PARAVIRT is turned off.

The lock structure is fixed at a single "unsigned int", initialized to zero, but the spinlock implementation can use it as it wishes.

Thanks to Thomas Friebel's Xen Summit talk "Preventing Guests from Spinning Around" for pointing out this problem.

Signed-off-by Jeremy Fitzhardinge <[email protected]>
Cc Nick Piggin <[email protected]>
Cc Thomas Friebel <[email protected]>
---
 arch/x86/kernel/paravirt.c       |   10 ++++++
 include/asm-x86/paravirt.h       |   37 +++++++++++++++++++++++++
 include/asm-x86/spinlock.h       |   55 +++++++++++++++++++++++++++-----------
 include/asm-x86/spinlock_types.h |    2 -
 4 files changed, 88 insertions(+), 16 deletions(-)

===================================================================

arch/x86/kernel/paravirt.c +10 -0
@@ -123,6 +123,7 @@
 		.pv_irq_ops = pv_irq_ops,
 		.pv_apic_ops = pv_apic_ops,
 		.pv_mmu_ops = pv_mmu_ops,
+		.pv_lock_ops = pv_lock_ops,
 	};
 	return *((void **)&tmpl + type);
 }

@@ -445,6 +446,15 @@
 	.set_fixmap = native_set_fixmap,
 };
 
+struct pv_lock_ops pv_lock_ops = {
+	.spin_is_locked = __ticket_spin_is_locked,
+	.spin_is_contended = __ticket_spin_is_contended,
+
+	.spin_lock = __ticket_spin_lock,
+	.spin_trylock = __ticket_spin_trylock,
+	.spin_unlock = __ticket_spin_unlock,
+};
+
 EXPORT_SYMBOL_GPL(pv_time_ops);
 EXPORT_SYMBOL    (pv_cpu_ops);
 EXPORT_SYMBOL    (pv_mmu_ops);

===================================================================

include/asm-x86/paravirt.h +37 -0
@@ -329,6 +329,15 @@
 			   unsigned long phys, pgprot_t flags);
 };
 
+struct raw_spinlock;
+struct pv_lock_ops {
+	int (*spin_is_locked)(struct raw_spinlock *lock);
+	int (*spin_is_contended)(struct raw_spinlock *lock);
+	void (*spin_lock)(struct raw_spinlock *lock);
+	int (*spin_trylock)(struct raw_spinlock *lock);
+	void (*spin_unlock)(struct raw_spinlock *lock);
+};
+
 /* This contains all the paravirt structures: we get a convenient
  * number for each function using the offset which we use to indicate
  * what to patch. */

@@ -339,6 +348,7 @@
 	struct pv_irq_ops pv_irq_ops;
 	struct pv_apic_ops pv_apic_ops;
 	struct pv_mmu_ops pv_mmu_ops;
+	struct pv_lock_ops pv_lock_ops;
 };
 
 extern struct pv_info pv_info;

@@ -348,6 +358,7 @@
 extern struct pv_irq_ops pv_irq_ops;
 extern struct pv_apic_ops pv_apic_ops;
 extern struct pv_mmu_ops pv_mmu_ops;
+extern struct pv_lock_ops pv_lock_ops;
 
 #define PARAVIRT_PATCH(x)					\
 	(offsetof(struct paravirt_patch_template, x) / sizeof(void *))

@@ -1377,6 +1388,31 @@
 void _paravirt_nop(void);
 #define paravirt_nop	((void *)_paravirt_nop)
 
+static inline int __raw_spin_is_locked(struct raw_spinlock *lock)
+{
+	return PVOP_CALL1(int, pv_lock_ops.spin_is_locked, lock);
+}
+
+static inline int __raw_spin_is_contended(struct raw_spinlock *lock)
+{
+	return PVOP_CALL1(int, pv_lock_ops.spin_is_contended, lock);
+}
+
+static __always_inline void __raw_spin_lock(struct raw_spinlock *lock)
+{
+	return PVOP_VCALL1(pv_lock_ops.spin_lock, lock);
+}
+
+static __always_inline int __raw_spin_trylock(struct raw_spinlock *lock)
+{
+	return PVOP_CALL1(int, pv_lock_ops.spin_trylock, lock);
+}
+
+static __always_inline void __raw_spin_unlock(struct raw_spinlock *lock)
+{
+	return PVOP_VCALL1(pv_lock_ops.spin_unlock, lock);
+}
+
 /* These all sit in the .parainstructions section to tell us what to patch. */
 struct paravirt_patch_site {
 	u8 *instr; 		/* original instructions */

@@ -1461,6 +1497,7 @@
 	return f;
 }
 
+
 /* Make sure as little as possible of this mess escapes. */
 #undef PARAVIRT_CALL
 #undef __PVOP_CALL

===================================================================

include/asm-x86/spinlock.h +40 -15

127 lines not on this page · raw message

===================================================================

include/asm-x86/spinlock_types.h +1 -1
@@ -5,7 +5,7 @@
 # error "please don't include this file directly"
 #endif
 
-typedef struct {
+typedef struct raw_spinlock {
 	unsigned int slock;
 } raw_spinlock_t;
author
#3 lore raw

RFC PATCH 2/4 paravirt: introduce a "lock-byte" spinlock implementation

In reply to Jeremy Fitzhardinge

Implement a version of the old spinlock algorithm, in which everyone spins waiting for a lock byte. In order to be compatible with the ticket-lock's use of a zero initializer, this uses the convention of '0' for unlocked and '1' for locked.

This algorithm is much better than ticket locks in a virtual envionment, because it doesn't interact badly with the vcpu scheduler. If there are multiple vcpus spinning on a lock and the lock is released, the next vcpu to be scheduled will take the lock, rather than cycling around until the next ticketed vcpu gets it.

To use this, you must call paravirt_use_bytelocks() very early, before any spinlocks have been taken.

Signed-off-by Jeremy Fitzhardinge <[email protected]>
Cc Nick Piggin <[email protected]>
Cc Thomas Friebel <[email protected]>
---
 arch/x86/kernel/paravirt.c |    9 ++++++
 include/asm-x86/paravirt.h |    2 +
 include/asm-x86/spinlock.h |   65 +++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 75 insertions(+), 1 deletion(-)

===================================================================

arch/x86/kernel/paravirt.c +9 -0
@@ -269,6 +269,15 @@
 	return __get_cpu_var(paravirt_lazy_mode);
 }
 
+void __init paravirt_use_bytelocks(void)
+{
+	pv_lock_ops.spin_is_locked = __byte_spin_is_locked;
+	pv_lock_ops.spin_is_contended = __byte_spin_is_contended;
+	pv_lock_ops.spin_lock = __byte_spin_lock;
+	pv_lock_ops.spin_trylock = __byte_spin_trylock;
+	pv_lock_ops.spin_unlock = __byte_spin_unlock;
+}
+
 struct pv_info pv_info = {
 	.name = "bare hardware",
 	.paravirt_enabled = 0,

===================================================================

include/asm-x86/paravirt.h +2 -0
@@ -1388,6 +1388,8 @@
 void _paravirt_nop(void);
 #define paravirt_nop	((void *)_paravirt_nop)
 
+void paravirt_use_bytelocks(void);
+
 static inline int __raw_spin_is_locked(struct raw_spinlock *lock)
 {
 	return PVOP_CALL1(int, pv_lock_ops.spin_is_locked, lock);

===================================================================

include/asm-x86/spinlock.h +64 -1

71 lines not on this page · raw message

author
#4 lore raw

RFC PATCH 2/4 paravirt: introduce a "lock-byte" spinlock implementation

In reply to Jeremy Fitzhardinge

Implement a version of the old spinlock algorithm, in which everyone spins waiting for a lock byte. In order to be compatible with the ticket-lock's use of a zero initializer, this uses the convention of '0' for unlocked and '1' for locked.

This algorithm is much better than ticket locks in a virtual envionment, because it doesn't interact badly with the vcpu scheduler. If there are multiple vcpus spinning on a lock and the lock is released, the next vcpu to be scheduled will take the lock, rather than cycling around until the next ticketed vcpu gets it.

To use this, you must call paravirt_use_bytelocks() very early, before any spinlocks have been taken.

Signed-off-by Jeremy Fitzhardinge <[email protected]>
Cc Nick Piggin <[email protected]>
Cc Thomas Friebel <[email protected]>
---
 arch/x86/kernel/paravirt.c |    9 ++++++
 include/asm-x86/paravirt.h |    2 +
 include/asm-x86/spinlock.h |   65 +++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 75 insertions(+), 1 deletion(-)

===================================================================

arch/x86/kernel/paravirt.c +9 -0
@@ -269,6 +269,15 @@
 	return __get_cpu_var(paravirt_lazy_mode);
 }
 
+void __init paravirt_use_bytelocks(void)
+{
+	pv_lock_ops.spin_is_locked = __byte_spin_is_locked;
+	pv_lock_ops.spin_is_contended = __byte_spin_is_contended;
+	pv_lock_ops.spin_lock = __byte_spin_lock;
+	pv_lock_ops.spin_trylock = __byte_spin_trylock;
+	pv_lock_ops.spin_unlock = __byte_spin_unlock;
+}
+
 struct pv_info pv_info = {
 	.name = "bare hardware",
 	.paravirt_enabled = 0,

===================================================================

include/asm-x86/paravirt.h +2 -0
@@ -1388,6 +1388,8 @@
 void _paravirt_nop(void);
 #define paravirt_nop	((void *)_paravirt_nop)
 
+void paravirt_use_bytelocks(void);
+
 static inline int __raw_spin_is_locked(struct raw_spinlock *lock)
 {
 	return PVOP_CALL1(int, pv_lock_ops.spin_is_locked, lock);

===================================================================

include/asm-x86/spinlock.h +64 -1

71 lines not on this page · raw message

author
#5 lore raw

RFC PATCH 3/4 xen: use lock-byte spinlock implementation

In reply to Jeremy Fitzhardinge

Switch to using the lock-byte spinlock implementation, to avoid the worst of the performance hit from ticket locks.

Signed-off-by Jeremy Fitzhardinge <[email protected]>
Cc Thomas Friebel <[email protected]>
---
 arch/x86/xen/smp.c |    1 +
 1 file changed, 1 insertion(+)

===================================================================

arch/x86/xen/smp.c +1 -0
@@ -430,4 +430,5 @@
 {
 	smp_ops = xen_smp_ops;
 	xen_fill_possible_map();
+	paravirt_use_bytelocks();
 }
author
#6 lore raw

RFC PATCH 3/4 xen: use lock-byte spinlock implementation

In reply to Jeremy Fitzhardinge

Switch to using the lock-byte spinlock implementation, to avoid the worst of the performance hit from ticket locks.

Signed-off-by Jeremy Fitzhardinge <[email protected]>
Cc Thomas Friebel <[email protected]>
---
 arch/x86/xen/smp.c |    1 +
 1 file changed, 1 insertion(+)

===================================================================

arch/x86/xen/smp.c +1 -0
@@ -430,4 +430,5 @@
 {
 	smp_ops = xen_smp_ops;
 	xen_fill_possible_map();
+	paravirt_use_bytelocks();
 }
author
#7 lore raw

RFC PATCH 4/4 xen: implement Xen-specific spinlocks

In reply to Jeremy Fitzhardinge

The standard ticket spinlocks are very expensive in a virtual environment, because their performance depends on Xen's scheduler giving vcpus time in the order that they're supposed to take the spinlock.

This implements a Xen-specific spinlock, which should be much more efficient.

The fast-path is essentially the old Linux-x86 locks, using a single lock byte. The locker decrements the byte; if the result is 0, then they have the lock. If the lock is negative, then locker must spin until the lock is positive again.

When there's contention, the locker spin for 2^16[*] iterations waiting to get the lock. If it fails to get the lock in that time, it adds itself to the contention count in the lock and blocks on a per-cpu event channel.

When unlocking the spinlock, the locker looks to see if there's anyone blocked waiting for the lock by checking for a non-zero waiter count. If there's a waiter, it traverses the per-cpu "lock_spinners" variable, which contains which lock each CPU is waiting on. It picks one CPU waiting on the lock and sends it an event to wake it up.

This allows efficient fast-path spinlock operation, while allowing spinning vcpus to give up their processor time while waiting for a contended lock.

[*] 2^16 iterations is threshold at which 98% locks have been taken according to Thomas Friebel's Xen Summit talk "Preventing Guests from Spinning Around". Therefore, we'd expect the lock and unlock slow paths will only be entered 2% of the time.

Signed-off-by Jeremy Fitzhardinge <[email protected]>
Cc Thomas Friebel <[email protected]>
---
 arch/x86/xen/smp.c           |  172 +++++++++++++++++++++++++++++++++++++++++-
 drivers/xen/events.c         |   27 ++++++
 include/asm-x86/xen/events.h |    1 
 include/xen/events.h         |    7 +
 4 files changed, 206 insertions(+), 1 deletion(-)

===================================================================

arch/x86/xen/smp.c +171 -1
@@ -15,6 +15,7 @@
  * This does not handle HOTPLUG_CPU yet.
  */
 #include <linux/sched.h>
+#include <linux/kernel_stat.h>
 #include <linux/err.h>
 #include <linux/smp.h>
 

@@ -34,6 +35,8 @@
 
 #include "xen-ops.h"
 #include "mmu.h"
+
+static void __cpuinit xen_init_lock_cpu(int cpu);
 
 cpumask_t xen_cpu_initialized_map;
 

@@ -179,6 +182,8 @@
 {
 	unsigned cpu;
 
+	xen_init_lock_cpu(0);
+
 	smp_store_cpu_info(0);
 	cpu_data(0).x86_max_cores = 1;
 	set_cpu_sibling_map(0);

@@ -301,6 +306,7 @@
 	clear_tsk_thread_flag(idle, TIF_FORK);
 #endif
 	xen_setup_timer(cpu);
+	xen_init_lock_cpu(cpu);
 
 	per_cpu(cpu_state, cpu) = CPU_UP_PREPARE;
 

@@ -413,6 +419,170 @@
 	return IRQ_HANDLED;
 }
 
+struct xen_spinlock {
+	unsigned char lock;		/* 0 -> free; 1 -> locked */
+	unsigned short spinners;	/* count of waiting cpus */
+};
+
+static int xen_spin_is_locked(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+
+	return xl->lock != 0;
+}
+
+static int xen_spin_is_contended(struct raw_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 raw_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(int, lock_kicker_irq) = -1;
+static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);
+
+static inline void spinning_lock(struct xen_spinlock *xl)
+{
+	__get_cpu_var(lock_spinners) = xl;
+	wmb();			/* set lock of interest before count */
+	asm(LOCK_PREFIX " incw %0"
+	    : "+m" (xl->spinners) : : "memory");
+}
+
+static inline void unspinning_lock(struct xen_spinlock *xl)
+{
+	asm(LOCK_PREFIX " decw %0"
+	    : "+m" (xl->spinners) : : "memory");
+	wmb();			/* decrement count before clearing lock */
+	__get_cpu_var(lock_spinners) = NULL;
+}
+
+static noinline int xen_spin_lock_slow(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+	int irq = __get_cpu_var(lock_kicker_irq);
+	int ret;
+
+	/* If kicker interrupts not initialized yet, just spin */
+	if (irq == -1)
+		return 0;
+
+	/* announce we're spinning */
+	spinning_lock(xl);
+
+	/* clear pending */
+	xen_clear_irq_pending(irq);
+
+	/* check again make sure it didn't become free while
+	   we weren't looking  */
+	ret = xen_spin_trylock(lock);
+	if (ret)
+		goto out;
+
+	/* block until irq becomes pending */
+	xen_poll_irq(irq);
+	kstat_this_cpu.irqs[irq]++;
+
+out:
+	unspinning_lock(xl);
+	return ret;
+}
+
+static void xen_spin_lock(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+	int timeout;
+	u8 oldval;
+
+	do {
+		timeout = 1 << 10;
+
+		asm("1: xchgb %1,%0\n"
+		    "   testb %1,%1\n"
+		    "   jz 3f\n"
+		    "2: rep;nop\n"
+		    "   cmpb $0,%0\n"
+		    "   je 1b\n"
+		    "   dec %2\n"
+		    "   jnz 2b\n"
+		    "3:\n"
+		    : "+m" (xl->lock), "=q" (oldval), "+r" (timeout)
+		    : "1" (1)
+		    : "memory");
+
+	} while (unlikely(oldval != 0 && !xen_spin_lock_slow(lock)));
+}
+
+static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
+{
+	int cpu;
+
+	for_each_online_cpu(cpu) {
+		/* XXX should mix up next cpu selection */
+		if (per_cpu(lock_spinners, cpu) == xl) {
+			xen_send_IPI_one(cpu, XEN_SPIN_UNLOCK_VECTOR);
+			break;
+		}
+	}
+}
+
+static void xen_spin_unlock(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+
+	smp_wmb();		/* make sure no writes get moved after unlock */
+	xl->lock = 0;		/* release lock */
+
+	/* make sure unlock happens before kick */
+	barrier();
+
+	if (unlikely(xl->spinners))
+		xen_spin_unlock_slow(xl);
+}
+
+static __cpuinit void xen_init_lock_cpu(int cpu)
+{
+	int irq;
+	const char *name;
+
+	name = kasprintf(GFP_KERNEL, "spinlock%d", cpu);
+	irq = bind_ipi_to_irqhandler(XEN_SPIN_UNLOCK_VECTOR,
+				     cpu,
+				     xen_reschedule_interrupt,
+				     IRQF_DISABLED|IRQF_PERCPU|IRQF_NOBALANCING,
+				     name,
+				     NULL);
+
+	if (irq >= 0) {
+		disable_irq(irq); /* make sure it's never delivered */
+		per_cpu(lock_kicker_irq, cpu) = irq;
+	}
+
+	printk("cpu %d spinlock event irq %d\n", cpu, irq);
+}
+
+static void __init xen_init_spinlocks(void)
+{
+	pv_lock_ops.spin_is_locked = xen_spin_is_locked;
+	pv_lock_ops.spin_is_contended = xen_spin_is_contended;
+	pv_lock_ops.spin_lock = xen_spin_lock;
+	pv_lock_ops.spin_trylock = xen_spin_trylock;
+	pv_lock_ops.spin_unlock = xen_spin_unlock;
+}
+
 static const struct smp_ops xen_smp_ops __initdata = {
 	.smp_prepare_boot_cpu = xen_smp_prepare_boot_cpu,
 	.smp_prepare_cpus = xen_smp_prepare_cpus,

@@ -430,5 +600,5 @@
 {
 	smp_ops = xen_smp_ops;
 	xen_fill_possible_map();
-	paravirt_use_bytelocks();
+	xen_init_spinlocks();
 }

===================================================================

drivers/xen/events.c +27 -0
@@ -741,6 +741,33 @@
 	}
 }
 
+/* Clear an irq's pending state, in preparation for polling on it */
+void xen_clear_irq_pending(int irq)
+{
+	int evtchn = evtchn_from_irq(irq);
+
+	if (VALID_EVTCHN(evtchn))
+		clear_evtchn(evtchn);
+}
+
+/* Poll waiting for an irq to become pending.  In the usual case, the
+   irq will be disabled so it won't deliver an interrupt. */
+void xen_poll_irq(int irq)
+{
+	evtchn_port_t evtchn = evtchn_from_irq(irq);
+
+	if (VALID_EVTCHN(evtchn)) {
+		struct sched_poll poll;
+
+		poll.nr_ports = 1;
+		poll.timeout = 0;
+		poll.ports = &evtchn;
+
+		if (HYPERVISOR_sched_op(SCHEDOP_poll, &poll) != 0)
+			BUG();
+	}
+}
+
 void xen_irq_resume(void)
 {
 	unsigned int cpu, irq, evtchn;

===================================================================

include/asm-x86/xen/events.h +1 -0
@@ -5,6 +5,7 @@
 	XEN_RESCHEDULE_VECTOR,
 	XEN_CALL_FUNCTION_VECTOR,
 	XEN_CALL_FUNCTION_SINGLE_VECTOR,
+	XEN_SPIN_UNLOCK_VECTOR,
 
 	XEN_NR_IPIS,
 };

===================================================================

include/xen/events.h +7 -0
@@ -45,4 +45,11 @@
 extern void xen_irq_resume(void);
 extern void xen_evtchn_do_upcall(struct pt_regs *regs);
 
+/* Clear an irq's pending state, in preparation for polling on it */
+void xen_clear_irq_pending(int irq);
+
+/* Poll waiting for an irq to become pending.  In the usual case, the
+   irq will be disabled so it won't deliver an interrupt. */
+void xen_poll_irq(int irq);
+
 #endif	/* _XEN_EVENTS_H */
#8 lore raw

Re: [PATCH RFC 4/4] xen: implement Xen-specific spinlocks

Hi,

Quoted 107 lines · Jeremy Fitzhardinge

The standard ticket spinlocks are very expensive in a virtual environment, because their performance depends on Xen's scheduler giving vcpus time in the order that they're supposed to take the spinlock.

This implements a Xen-specific spinlock, which should be much more efficient.

The fast-path is essentially the old Linux-x86 locks, using a single lock byte. The locker decrements the byte; if the result is 0, then they have the lock. If the lock is negative, then locker must spin until the lock is positive again.

When there's contention, the locker spin for 2^16[*] iterations waiting to get the lock. If it fails to get the lock in that time, it adds itself to the contention count in the lock and blocks on a per-cpu event channel.

When unlocking the spinlock, the locker looks to see if there's anyone blocked waiting for the lock by checking for a non-zero waiter count. If there's a waiter, it traverses the per-cpu "lock_spinners" variable, which contains which lock each CPU is waiting on. It picks one CPU waiting on the lock and sends it an event to wake it up.

This allows efficient fast-path spinlock operation, while allowing spinning vcpus to give up their processor time while waiting for a contended lock.

[*] 2^16 iterations is threshold at which 98% locks have been taken according to Thomas Friebel's Xen Summit talk "Preventing Guests from Spinning Around". Therefore, we'd expect the lock and unlock slow paths will only be entered 2% of the time.

Signed-off-by Jeremy Fitzhardinge <[email protected]>
Cc Thomas Friebel <[email protected]>
---
 arch/x86/xen/smp.c           |  172 +++++++++++++++++++++++++++++++++++++++++-
 drivers/xen/events.c         |   27 ++++++
 include/asm-x86/xen/events.h |    1 
 include/xen/events.h         |    7 +
 4 files changed, 206 insertions(+), 1 deletion(-)

===================================================================

arch/x86/xen/smp.c +30 -0
@@ -15,6 +15,7 @@
  * This does not handle HOTPLUG_CPU yet.
  */
 #include <linux/sched.h>
+#include <linux/kernel_stat.h>
 #include <linux/err.h>
 #include <linux/smp.h>
 

@@ -34,6 +35,8 @@
 
 #include "xen-ops.h"
 #include "mmu.h"
+
+static void __cpuinit xen_init_lock_cpu(int cpu);
 
 cpumask_t xen_cpu_initialized_map;
 

@@ -179,6 +182,8 @@
 {
 	unsigned cpu;
 
+	xen_init_lock_cpu(0);
+
 	smp_store_cpu_info(0);
 	cpu_data(0).x86_max_cores = 1;
 	set_cpu_sibling_map(0);

@@ -301,6 +306,7 @@
 	clear_tsk_thread_flag(idle, TIF_FORK);
 #endif
 	xen_setup_timer(cpu);
+	xen_init_lock_cpu(cpu);
 
 	per_cpu(cpu_state, cpu) = CPU_UP_PREPARE;
 

@@ -413,6 +419,170 @@
 	return IRQ_HANDLED;
 }
 
+struct xen_spinlock {
+	unsigned char lock;		/* 0 -> free; 1 -> locked */
+	unsigned short spinners;	/* count of waiting cpus */
+};
+
+static int xen_spin_is_locked(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+
+	return xl->lock != 0;
+}
+
+static int xen_spin_is_contended(struct raw_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 raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;

arch/x86/xen/smp.c line 455

Quoted 10 lines
arch/x86/xen/smp.c +10 -0
+	u8 old = 1;
+
+	asm("xchgb %b0,%1"
+	    : "+q" (old), "+m" (xl->lock) : : "memory");
+
+	return old == 0;
+}
+
+static DEFINE_PER_CPU(int, lock_kicker_irq) = -1;
+static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);

The plural is a bit misleading, as this is a single pointer per CPU.

Quoted 67 lines
arch/x86/xen/smp.c +67 -0
+static inline void spinning_lock(struct xen_spinlock *xl)
+{
+	__get_cpu_var(lock_spinners) = xl;
+	wmb();			/* set lock of interest before count */
+	asm(LOCK_PREFIX " incw %0"
+	    : "+m" (xl->spinners) : : "memory");
+}
+
+static inline void unspinning_lock(struct xen_spinlock *xl)
+{
+	asm(LOCK_PREFIX " decw %0"
+	    : "+m" (xl->spinners) : : "memory");
+	wmb();			/* decrement count before clearing lock */
+	__get_cpu_var(lock_spinners) = NULL;
+}
+
+static noinline int xen_spin_lock_slow(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+	int irq = __get_cpu_var(lock_kicker_irq);
+	int ret;
+
+	/* If kicker interrupts not initialized yet, just spin */
+	if (irq == -1)
+		return 0;
+
+	/* announce we're spinning */
+	spinning_lock(xl);
+
+	/* clear pending */
+	xen_clear_irq_pending(irq);
+
+	/* check again make sure it didn't become free while
+	   we weren't looking  */
+	ret = xen_spin_trylock(lock);
+	if (ret)
+		goto out;
+
+	/* block until irq becomes pending */
+	xen_poll_irq(irq);
+	kstat_this_cpu.irqs[irq]++;
+
+out:
+	unspinning_lock(xl);
+	return ret;
+}
+
+static void xen_spin_lock(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+	int timeout;
+	u8 oldval;
+
+	do {
+		timeout = 1 << 10;
+
+		asm("1: xchgb %1,%0\n"
+		    "   testb %1,%1\n"
+		    "   jz 3f\n"
+		    "2: rep;nop\n"
+		    "   cmpb $0,%0\n"
+		    "   je 1b\n"
+		    "   dec %2\n"
+		    "   jnz 2b\n"
+		    "3:\n"
+		    : "+m" (xl->lock), "=q" (oldval), "+r" (timeout)
+		    : "1" (1)

arch/x86/xen/smp.c line 533

Quoted 10 lines
arch/x86/xen/smp.c +10 -0
+		    : "memory");
+
+	} while (unlikely(oldval != 0 && !xen_spin_lock_slow(lock)));
+}
+
+static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
+{
+	int cpu;
+
+	for_each_online_cpu(cpu) {

Would it be feasible to have a bitmap for the spinning CPUs in order to do a for_each_spinning_cpu() here instead? Or is setting a bit in spinning_lock() and unsetting it in unspinning_lock() more overhead than going over all CPUs here?

Quoted 115 lines
arch/x86/xen/smp.c +53 -1
+		/* XXX should mix up next cpu selection */
+		if (per_cpu(lock_spinners, cpu) == xl) {
+			xen_send_IPI_one(cpu, XEN_SPIN_UNLOCK_VECTOR);
+			break;
+		}
+	}
+}
+
+static void xen_spin_unlock(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+
+	smp_wmb();		/* make sure no writes get moved after unlock */
+	xl->lock = 0;		/* release lock */
+
+	/* make sure unlock happens before kick */
+	barrier();
+
+	if (unlikely(xl->spinners))
+		xen_spin_unlock_slow(xl);
+}
+
+static __cpuinit void xen_init_lock_cpu(int cpu)
+{
+	int irq;
+	const char *name;
+
+	name = kasprintf(GFP_KERNEL, "spinlock%d", cpu);
+	irq = bind_ipi_to_irqhandler(XEN_SPIN_UNLOCK_VECTOR,
+				     cpu,
+				     xen_reschedule_interrupt,
+				     IRQF_DISABLED|IRQF_PERCPU|IRQF_NOBALANCING,
+				     name,
+				     NULL);
+
+	if (irq >= 0) {
+		disable_irq(irq); /* make sure it's never delivered */
+		per_cpu(lock_kicker_irq, cpu) = irq;
+	}
+
+	printk("cpu %d spinlock event irq %d\n", cpu, irq);
+}
+
+static void __init xen_init_spinlocks(void)
+{
+	pv_lock_ops.spin_is_locked = xen_spin_is_locked;
+	pv_lock_ops.spin_is_contended = xen_spin_is_contended;
+	pv_lock_ops.spin_lock = xen_spin_lock;
+	pv_lock_ops.spin_trylock = xen_spin_trylock;
+	pv_lock_ops.spin_unlock = xen_spin_unlock;
+}
+
 static const struct smp_ops xen_smp_ops __initdata = {
 	.smp_prepare_boot_cpu = xen_smp_prepare_boot_cpu,
 	.smp_prepare_cpus = xen_smp_prepare_cpus,

@@ -430,5 +600,5 @@
 {
 	smp_ops = xen_smp_ops;
 	xen_fill_possible_map();
-	paravirt_use_bytelocks();
+	xen_init_spinlocks();
 }

===================================================================

drivers/xen/events.c +27 -0
@@ -741,6 +741,33 @@
 	}
 }
 
+/* Clear an irq's pending state, in preparation for polling on it */
+void xen_clear_irq_pending(int irq)
+{
+	int evtchn = evtchn_from_irq(irq);
+
+	if (VALID_EVTCHN(evtchn))
+		clear_evtchn(evtchn);
+}
+
+/* Poll waiting for an irq to become pending.  In the usual case, the
+   irq will be disabled so it won't deliver an interrupt. */
+void xen_poll_irq(int irq)
+{
+	evtchn_port_t evtchn = evtchn_from_irq(irq);
+
+	if (VALID_EVTCHN(evtchn)) {
+		struct sched_poll poll;
+
+		poll.nr_ports = 1;
+		poll.timeout = 0;
+		poll.ports = &evtchn;
+
+		if (HYPERVISOR_sched_op(SCHEDOP_poll, &poll) != 0)
+			BUG();
+	}
+}
+
 void xen_irq_resume(void)
 {
 	unsigned int cpu, irq, evtchn;

===================================================================

include/asm-x86/xen/events.h +1 -0
@@ -5,6 +5,7 @@
 	XEN_RESCHEDULE_VECTOR,
 	XEN_CALL_FUNCTION_VECTOR,
 	XEN_CALL_FUNCTION_SINGLE_VECTOR,
+	XEN_SPIN_UNLOCK_VECTOR,
 
 	XEN_NR_IPIS,
 };

===================================================================

include/xen/events.h +0 -0
@@ -45,4 +45,11 @@
 extern void xen_irq_resume(void);

include/xen/events.h line 55

Quoted 10 lines
include/xen/events.h +7 -0
 extern void xen_evtchn_do_upcall(struct pt_regs *regs);
 
+/* Clear an irq's pending state, in preparation for polling on it */
+void xen_clear_irq_pending(int irq);
+
+/* Poll waiting for an irq to become pending.  In the usual case, the
+   irq will be disabled so it won't deliver an interrupt. */
+void xen_poll_irq(int irq);
+
 #endif	/* _XEN_EVENTS_H */

Hannes

author
#9 lore raw

Re: [PATCH RFC 4/4] xen: implement Xen-specific spinlocks

Quoted 6 lines · Johannes Weiner

arch/x86/xen/smp.c line 455

Quoted 3 lines
arch/x86/xen/smp.c +2 -0
+static DEFINE_PER_CPU(int, lock_kicker_irq) = -1;
+static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);

The plural is a bit misleading, as this is a single pointer per CPU.

Yeah. And it's wrong because it's specifically *not* spinning, but blocking.

Quoted 12 lines

arch/x86/xen/smp.c line 533

Quoted 6 lines
arch/x86/xen/smp.c +5 -0
+static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
+{
+	int cpu;
+
+	for_each_online_cpu(cpu) {

Would it be feasible to have a bitmap for the spinning CPUs in order to do a for_each_spinning_cpu() here instead? Or is setting a bit in spinning_lock() and unsetting it in unspinning_lock() more overhead than going over all CPUs here?

Not worthwhile, I think. This is a very rare path: it will only happen if 1) there's lock contention, that 2) wasn't resolved within the timeout. In practice, this gets called a few thousand times per cpu over a kernbench, which is nothing.

My very original version of this code kept a bitmask of interested CPUs within the lock, but there's only space for 24 cpus if we still use a byte for the lock itself. It all turned out fairly awkward, and this version is a marked improvement.

J

#10 lore raw

Re: [PATCH RFC 4/4] xen: implement Xen-specific spinlocks

Hi,

Quoted 10 lines · Jeremy Fitzhardinge
Quoted 6 lines · Johannes Weiner

arch/x86/xen/smp.c line 455

Quoted 3 lines
arch/x86/xen/smp.c +2 -0
+static DEFINE_PER_CPU(int, lock_kicker_irq) = -1;
+static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);

The plural is a bit misleading, as this is a single pointer per CPU.

Yeah. And it's wrong because it's specifically *not* spinning, but blocking.

I thought of it as `virtually spinning', so had no problems with the naming itself :)

Quoted 13 lines
Quoted 12 lines

arch/x86/xen/smp.c line 533

Quoted 6 lines
arch/x86/xen/smp.c +5 -0
+static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
+{
+	int cpu;
+
+	for_each_online_cpu(cpu) {

Would it be feasible to have a bitmap for the spinning CPUs in order to do a for_each_spinning_cpu() here instead? Or is setting a bit in spinning_lock() and unsetting it in unspinning_lock() more overhead than going over all CPUs here?

Quoted 4 lines

Not worthwhile, I think. This is a very rare path: it will only happen if 1) there's lock contention, that 2) wasn't resolved within the timeout. In practice, this gets called a few thousand times per cpu over a kernbench, which is nothing.

Okay, I agree.

Hannes

#11 lore raw

Re: [PATCH RFC 4/4] xen: implement Xen-specific spinlocks

In reply to Jeremy Fitzhardinge

Hi,

Quoted 10 lines · Jeremy Fitzhardinge
Quoted 6 lines · Johannes Weiner

arch/x86/xen/smp.c line 455

Quoted 3 lines
arch/x86/xen/smp.c +2 -0
+static DEFINE_PER_CPU(int, lock_kicker_irq) = -1;
+static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);

The plural is a bit misleading, as this is a single pointer per CPU.

Yeah. And it's wrong because it's specifically *not* spinning, but blocking.

I thought of it as `virtually spinning', so had no problems with the naming itself :)

Quoted 13 lines
Quoted 12 lines

arch/x86/xen/smp.c line 533

Quoted 6 lines
arch/x86/xen/smp.c +5 -0
+static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
+{
+	int cpu;
+
+	for_each_online_cpu(cpu) {

Would it be feasible to have a bitmap for the spinning CPUs in order to do a for_each_spinning_cpu() here instead? Or is setting a bit in spinning_lock() and unsetting it in unspinning_lock() more overhead than going over all CPUs here?

Quoted 4 lines

Not worthwhile, I think. This is a very rare path: it will only happen if 1) there's lock contention, that 2) wasn't resolved within the timeout. In practice, this gets called a few thousand times per cpu over a kernbench, which is nothing.

Okay, I agree.

Hannes

author
#12 lore raw

Re: [PATCH RFC 4/4] xen: implement Xen-specific spinlocks

In reply to Johannes Weiner
Quoted 6 lines · Johannes Weiner

arch/x86/xen/smp.c line 455

Quoted 3 lines
arch/x86/xen/smp.c +2 -0
+static DEFINE_PER_CPU(int, lock_kicker_irq) = -1;
+static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);

The plural is a bit misleading, as this is a single pointer per CPU.

Yeah. And it's wrong because it's specifically *not* spinning, but blocking.

Quoted 12 lines

arch/x86/xen/smp.c line 533

Quoted 6 lines
arch/x86/xen/smp.c +5 -0
+static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
+{
+	int cpu;
+
+	for_each_online_cpu(cpu) {

Would it be feasible to have a bitmap for the spinning CPUs in order to do a for_each_spinning_cpu() here instead? Or is setting a bit in spinning_lock() and unsetting it in unspinning_lock() more overhead than going over all CPUs here?

Not worthwhile, I think. This is a very rare path: it will only happen if 1) there's lock contention, that 2) wasn't resolved within the timeout. In practice, this gets called a few thousand times per cpu over a kernbench, which is nothing.

My very original version of this code kept a bitmask of interested CPUs within the lock, but there's only space for 24 cpus if we still use a byte for the lock itself. It all turned out fairly awkward, and this version is a marked improvement.

J

#13 lore raw

Re: [PATCH RFC 4/4] xen: implement Xen-specific spinlocks

In reply to Jeremy Fitzhardinge

Hi,

Quoted 107 lines · Jeremy Fitzhardinge

The standard ticket spinlocks are very expensive in a virtual environment, because their performance depends on Xen's scheduler giving vcpus time in the order that they're supposed to take the spinlock.

This implements a Xen-specific spinlock, which should be much more efficient.

The fast-path is essentially the old Linux-x86 locks, using a single lock byte. The locker decrements the byte; if the result is 0, then they have the lock. If the lock is negative, then locker must spin until the lock is positive again.

When there's contention, the locker spin for 2^16[*] iterations waiting to get the lock. If it fails to get the lock in that time, it adds itself to the contention count in the lock and blocks on a per-cpu event channel.

When unlocking the spinlock, the locker looks to see if there's anyone blocked waiting for the lock by checking for a non-zero waiter count. If there's a waiter, it traverses the per-cpu "lock_spinners" variable, which contains which lock each CPU is waiting on. It picks one CPU waiting on the lock and sends it an event to wake it up.

This allows efficient fast-path spinlock operation, while allowing spinning vcpus to give up their processor time while waiting for a contended lock.

[*] 2^16 iterations is threshold at which 98% locks have been taken according to Thomas Friebel's Xen Summit talk "Preventing Guests from Spinning Around". Therefore, we'd expect the lock and unlock slow paths will only be entered 2% of the time.

Signed-off-by Jeremy Fitzhardinge <[email protected]>
Cc Thomas Friebel <[email protected]>
---
 arch/x86/xen/smp.c           |  172 +++++++++++++++++++++++++++++++++++++++++-
 drivers/xen/events.c         |   27 ++++++
 include/asm-x86/xen/events.h |    1 
 include/xen/events.h         |    7 +
 4 files changed, 206 insertions(+), 1 deletion(-)

===================================================================

arch/x86/xen/smp.c +30 -0
@@ -15,6 +15,7 @@
  * This does not handle HOTPLUG_CPU yet.
  */
 #include <linux/sched.h>
+#include <linux/kernel_stat.h>
 #include <linux/err.h>
 #include <linux/smp.h>
 

@@ -34,6 +35,8 @@
 
 #include "xen-ops.h"
 #include "mmu.h"
+
+static void __cpuinit xen_init_lock_cpu(int cpu);
 
 cpumask_t xen_cpu_initialized_map;
 

@@ -179,6 +182,8 @@
 {
 	unsigned cpu;
 
+	xen_init_lock_cpu(0);
+
 	smp_store_cpu_info(0);
 	cpu_data(0).x86_max_cores = 1;
 	set_cpu_sibling_map(0);

@@ -301,6 +306,7 @@
 	clear_tsk_thread_flag(idle, TIF_FORK);
 #endif
 	xen_setup_timer(cpu);
+	xen_init_lock_cpu(cpu);
 
 	per_cpu(cpu_state, cpu) = CPU_UP_PREPARE;
 

@@ -413,6 +419,170 @@
 	return IRQ_HANDLED;
 }
 
+struct xen_spinlock {
+	unsigned char lock;		/* 0 -> free; 1 -> locked */
+	unsigned short spinners;	/* count of waiting cpus */
+};
+
+static int xen_spin_is_locked(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+
+	return xl->lock != 0;
+}
+
+static int xen_spin_is_contended(struct raw_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 raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;

arch/x86/xen/smp.c line 455

Quoted 10 lines
arch/x86/xen/smp.c +10 -0
+	u8 old = 1;
+
+	asm("xchgb %b0,%1"
+	    : "+q" (old), "+m" (xl->lock) : : "memory");
+
+	return old == 0;
+}
+
+static DEFINE_PER_CPU(int, lock_kicker_irq) = -1;
+static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);

The plural is a bit misleading, as this is a single pointer per CPU.

Quoted 67 lines
arch/x86/xen/smp.c +67 -0
+static inline void spinning_lock(struct xen_spinlock *xl)
+{
+	__get_cpu_var(lock_spinners) = xl;
+	wmb();			/* set lock of interest before count */
+	asm(LOCK_PREFIX " incw %0"
+	    : "+m" (xl->spinners) : : "memory");
+}
+
+static inline void unspinning_lock(struct xen_spinlock *xl)
+{
+	asm(LOCK_PREFIX " decw %0"
+	    : "+m" (xl->spinners) : : "memory");
+	wmb();			/* decrement count before clearing lock */
+	__get_cpu_var(lock_spinners) = NULL;
+}
+
+static noinline int xen_spin_lock_slow(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+	int irq = __get_cpu_var(lock_kicker_irq);
+	int ret;
+
+	/* If kicker interrupts not initialized yet, just spin */
+	if (irq == -1)
+		return 0;
+
+	/* announce we're spinning */
+	spinning_lock(xl);
+
+	/* clear pending */
+	xen_clear_irq_pending(irq);
+
+	/* check again make sure it didn't become free while
+	   we weren't looking  */
+	ret = xen_spin_trylock(lock);
+	if (ret)
+		goto out;
+
+	/* block until irq becomes pending */
+	xen_poll_irq(irq);
+	kstat_this_cpu.irqs[irq]++;
+
+out:
+	unspinning_lock(xl);
+	return ret;
+}
+
+static void xen_spin_lock(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+	int timeout;
+	u8 oldval;
+
+	do {
+		timeout = 1 << 10;
+
+		asm("1: xchgb %1,%0\n"
+		    "   testb %1,%1\n"
+		    "   jz 3f\n"
+		    "2: rep;nop\n"
+		    "   cmpb $0,%0\n"
+		    "   je 1b\n"
+		    "   dec %2\n"
+		    "   jnz 2b\n"
+		    "3:\n"
+		    : "+m" (xl->lock), "=q" (oldval), "+r" (timeout)
+		    : "1" (1)

arch/x86/xen/smp.c line 533

Quoted 10 lines
arch/x86/xen/smp.c +10 -0
+		    : "memory");
+
+	} while (unlikely(oldval != 0 && !xen_spin_lock_slow(lock)));
+}
+
+static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
+{
+	int cpu;
+
+	for_each_online_cpu(cpu) {

Would it be feasible to have a bitmap for the spinning CPUs in order to do a for_each_spinning_cpu() here instead? Or is setting a bit in spinning_lock() and unsetting it in unspinning_lock() more overhead than going over all CPUs here?

Quoted 115 lines
arch/x86/xen/smp.c +53 -1
+		/* XXX should mix up next cpu selection */
+		if (per_cpu(lock_spinners, cpu) == xl) {
+			xen_send_IPI_one(cpu, XEN_SPIN_UNLOCK_VECTOR);
+			break;
+		}
+	}
+}
+
+static void xen_spin_unlock(struct raw_spinlock *lock)
+{
+	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
+
+	smp_wmb();		/* make sure no writes get moved after unlock */
+	xl->lock = 0;		/* release lock */
+
+	/* make sure unlock happens before kick */
+	barrier();
+
+	if (unlikely(xl->spinners))
+		xen_spin_unlock_slow(xl);
+}
+
+static __cpuinit void xen_init_lock_cpu(int cpu)
+{
+	int irq;
+	const char *name;
+
+	name = kasprintf(GFP_KERNEL, "spinlock%d", cpu);
+	irq = bind_ipi_to_irqhandler(XEN_SPIN_UNLOCK_VECTOR,
+				     cpu,
+				     xen_reschedule_interrupt,
+				     IRQF_DISABLED|IRQF_PERCPU|IRQF_NOBALANCING,
+				     name,
+				     NULL);
+
+	if (irq >= 0) {
+		disable_irq(irq); /* make sure it's never delivered */
+		per_cpu(lock_kicker_irq, cpu) = irq;
+	}
+
+	printk("cpu %d spinlock event irq %d\n", cpu, irq);
+}
+
+static void __init xen_init_spinlocks(void)
+{
+	pv_lock_ops.spin_is_locked = xen_spin_is_locked;
+	pv_lock_ops.spin_is_contended = xen_spin_is_contended;
+	pv_lock_ops.spin_lock = xen_spin_lock;
+	pv_lock_ops.spin_trylock = xen_spin_trylock;
+	pv_lock_ops.spin_unlock = xen_spin_unlock;
+}
+
 static const struct smp_ops xen_smp_ops __initdata = {
 	.smp_prepare_boot_cpu = xen_smp_prepare_boot_cpu,
 	.smp_prepare_cpus = xen_smp_prepare_cpus,

@@ -430,5 +600,5 @@
 {
 	smp_ops = xen_smp_ops;
 	xen_fill_possible_map();
-	paravirt_use_bytelocks();
+	xen_init_spinlocks();
 }

===================================================================

drivers/xen/events.c +27 -0
@@ -741,6 +741,33 @@
 	}
 }
 
+/* Clear an irq's pending state, in preparation for polling on it */
+void xen_clear_irq_pending(int irq)
+{
+	int evtchn = evtchn_from_irq(irq);
+
+	if (VALID_EVTCHN(evtchn))
+		clear_evtchn(evtchn);
+}
+
+/* Poll waiting for an irq to become pending.  In the usual case, the
+   irq will be disabled so it won't deliver an interrupt. */
+void xen_poll_irq(int irq)
+{
+	evtchn_port_t evtchn = evtchn_from_irq(irq);
+
+	if (VALID_EVTCHN(evtchn)) {
+		struct sched_poll poll;
+
+		poll.nr_ports = 1;
+		poll.timeout = 0;
+		poll.ports = &evtchn;
+
+		if (HYPERVISOR_sched_op(SCHEDOP_poll, &poll) != 0)
+			BUG();
+	}
+}
+
 void xen_irq_resume(void)
 {
 	unsigned int cpu, irq, evtchn;

===================================================================

include/asm-x86/xen/events.h +1 -0
@@ -5,6 +5,7 @@
 	XEN_RESCHEDULE_VECTOR,
 	XEN_CALL_FUNCTION_VECTOR,
 	XEN_CALL_FUNCTION_SINGLE_VECTOR,
+	XEN_SPIN_UNLOCK_VECTOR,
 
 	XEN_NR_IPIS,
 };

===================================================================

include/xen/events.h +0 -0
@@ -45,4 +45,11 @@
 extern void xen_irq_resume(void);

include/xen/events.h line 55

Quoted 10 lines
include/xen/events.h +7 -0
 extern void xen_evtchn_do_upcall(struct pt_regs *regs);
 
+/* Clear an irq's pending state, in preparation for polling on it */
+void xen_clear_irq_pending(int irq);
+
+/* Poll waiting for an irq to become pending.  In the usual case, the
+   irq will be disabled so it won't deliver an interrupt. */
+void xen_poll_irq(int irq);
+
 #endif	/* _XEN_EVENTS_H */

Hannes

#14 lore raw
In reply to Jeremy Fitzhardinge
Quoted 6 lines · On Tuesday 08 July 2008 05:07:49 Jeremy Fitzhardinge wrote:

At the most recent Xen Summit, Thomas Friebel presented a paper ("Preventing Guests from Spinning Around",
http://xen.org/files/xensummitboston08/LHP.pdf) investigating the interactions between spinlocks and virtual machines. Specifically, he looked at what happens when a lock-holding VCPU gets involuntarily preempted.

I find it interesting that gang scheduling the guest was not suggested as an obvious solution.

Anyway, concept looks fine; lguest's solution is more elegant of course :)

A little disappointing that you can't patch your version inline.

Cheers,
Rusty.

author
#15 lore raw
Quoted 10 lines · Rusty Russell
Quoted 7 lines · On Tuesday 08 July 2008 05:07:49 Jeremy Fitzhardinge wrote:

At the most recent Xen Summit, Thomas Friebel presented a paper ("Preventing Guests from Spinning Around",
http://xen.org/files/xensummitboston08/LHP.pdf) investigating the interactions between spinlocks and virtual machines. Specifically, he looked at what happens when a lock-holding VCPU gets involuntarily preempted.

Quoted 2 lines

I find it interesting that gang scheduling the guest was not suggested as an obvious solution.

It's an obvious answer, but not an obvious solution. You trade off wasting time spinning vs wasting time waiting for N vcpus to be free for scheduling. Or something; seems much more complex, particularly if you can do a small guest tweak to solve the problem.

Quoted 2 lines

Anyway, concept looks fine; lguest's solution is more elegant of course :)

You could remove all mutable state and call it "erlang".

Quoted 1 line

A little disappointing that you can't patch your version inline.

Spinlock code isn't inlined currently, so I hadn't considered it. The fast path code for both lock and unlock is nearly small enough to consider it, but it seems a bit fiddly.

If the "spin_lock" and "spin_unlock" functions were inlined functions which called the out of line __raw_spin_lock/unlock functions, then after patching they would result in a direct call to the backend lock functions, which would be exactly equivalent to what happens now (since I hook __raw_spin_lock into calls via pv_lock_ops).

J

#16 lore raw
Quoted 9 lines · On Tuesday 08 July 2008 10:37:54 Jeremy Fitzhardinge wrote:
Quoted 8 lines · Rusty Russell
Quoted 6 lines · On Tuesday 08 July 2008 05:07:49 Jeremy Fitzhardinge wrote:

At the most recent Xen Summit, Thomas Friebel presented a paper ("Preventing Guests from Spinning Around",
http://xen.org/files/xensummitboston08/LHP.pdf) investigating the interactions between spinlocks and virtual machines. Specifically, he looked at what happens when a lock-holding VCPU gets involuntarily preempted.

Quoted 6 lines
Quoted 2 lines

I find it interesting that gang scheduling the guest was not suggested as an obvious solution.

It's an obvious answer, but not an obvious solution. You trade off wasting time spinning vs wasting time waiting for N vcpus to be free for scheduling.

Perhaps, but with huge numbers of cores (as The Future seems to promise) and significant overcommit not sure how bad this would be.

Quoted 2 lines

Or something; seems much more complex, particularly if you can do a small guest tweak to solve the problem.

But AFAICT it's one of a related set of problems where all VCPUs are required for a task. Hackbench comes to mind. There's going to be a lot of ping-ponging and you'll approach gang scheduling to get decent performance.

Quoted 5 lines
Quoted 1 line

A little disappointing that you can't patch your version inline.

Spinlock code isn't inlined currently, so I hadn't considered it. The fast path code for both lock and unlock is nearly small enough to consider it, but it seems a bit fiddly.

Yeah, OK.

Thanks,
Rusty.

#17 lore raw
In reply to Jeremy Fitzhardinge
Quoted 9 lines · On Tuesday 08 July 2008 10:37:54 Jeremy Fitzhardinge wrote:
Quoted 8 lines · Rusty Russell
Quoted 6 lines · On Tuesday 08 July 2008 05:07:49 Jeremy Fitzhardinge wrote:

At the most recent Xen Summit, Thomas Friebel presented a paper ("Preventing Guests from Spinning Around",
http://xen.org/files/xensummitboston08/LHP.pdf) investigating the interactions between spinlocks and virtual machines. Specifically, he looked at what happens when a lock-holding VCPU gets involuntarily preempted.

Quoted 6 lines
Quoted 2 lines

I find it interesting that gang scheduling the guest was not suggested as an obvious solution.

It's an obvious answer, but not an obvious solution. You trade off wasting time spinning vs wasting time waiting for N vcpus to be free for scheduling.

Perhaps, but with huge numbers of cores (as The Future seems to promise) and significant overcommit not sure how bad this would be.

Quoted 2 lines

Or something; seems much more complex, particularly if you can do a small guest tweak to solve the problem.

But AFAICT it's one of a related set of problems where all VCPUs are required for a task. Hackbench comes to mind. There's going to be a lot of ping-ponging and you'll approach gang scheduling to get decent performance.

Quoted 5 lines
Quoted 1 line

A little disappointing that you can't patch your version inline.

Spinlock code isn't inlined currently, so I hadn't considered it. The fast path code for both lock and unlock is nearly small enough to consider it, but it seems a bit fiddly.

Yeah, OK.

Thanks,
Rusty.

author
#18 lore raw
In reply to Rusty Russell
Quoted 10 lines · Rusty Russell
Quoted 7 lines · On Tuesday 08 July 2008 05:07:49 Jeremy Fitzhardinge wrote:

At the most recent Xen Summit, Thomas Friebel presented a paper ("Preventing Guests from Spinning Around",
http://xen.org/files/xensummitboston08/LHP.pdf) investigating the interactions between spinlocks and virtual machines. Specifically, he looked at what happens when a lock-holding VCPU gets involuntarily preempted.

Quoted 3 lines

I find it interesting that gang scheduling the guest was not suggested as an obvious solution.

It's an obvious answer, but not an obvious solution. You trade off wasting time spinning vs wasting time waiting for N vcpus to be free for scheduling. Or something; seems much more complex, particularly if you can do a small guest tweak to solve the problem.

Quoted 2 lines

Anyway, concept looks fine; lguest's solution is more elegant of course :)

You could remove all mutable state and call it "erlang".

Quoted 1 line

A little disappointing that you can't patch your version inline.

Spinlock code isn't inlined currently, so I hadn't considered it. The fast path code for both lock and unlock is nearly small enough to consider it, but it seems a bit fiddly.

If the "spin_lock" and "spin_unlock" functions were inlined functions which called the out of line __raw_spin_lock/unlock functions, then after patching they would result in a direct call to the backend lock functions, which would be exactly equivalent to what happens now (since I hook __raw_spin_lock into calls via pv_lock_ops).

J

#19 lore raw
In reply to Rusty Russell
Quoted 8 lines · Rusty Russell
Quoted 6 lines · On Tuesday 08 July 2008 05:07:49 Jeremy Fitzhardinge wrote:

At the most recent Xen Summit, Thomas Friebel presented a paper ("Preventing Guests from Spinning Around",
http://xen.org/files/xensummitboston08/LHP.pdf) investigating the interactions between spinlocks and virtual machines. Specifically, he looked at what happens when a lock-holding VCPU gets involuntarily preempted.

Quoted 4 lines

I find it interesting that gang scheduling the guest was not suggested as an obvious solution.

Anyway, concept looks fine; lguest's solution is more elegant of course :)

What's lguest's solution?

#22 lore raw
In reply to Rusty Russell
Quoted 8 lines · Rusty Russell
Quoted 6 lines · On Tuesday 08 July 2008 05:07:49 Jeremy Fitzhardinge wrote:

At the most recent Xen Summit, Thomas Friebel presented a paper ("Preventing Guests from Spinning Around",
http://xen.org/files/xensummitboston08/LHP.pdf) investigating the interactions between spinlocks and virtual machines. Specifically, he looked at what happens when a lock-holding VCPU gets involuntarily preempted.

Quoted 4 lines

I find it interesting that gang scheduling the guest was not suggested as an obvious solution.

Anyway, concept looks fine; lguest's solution is more elegant of course :)

What's lguest's solution?

#23 lore raw
In reply to Jeremy Fitzhardinge
Quoted 6 lines · On Tuesday 08 July 2008 05:07:49 Jeremy Fitzhardinge wrote:

At the most recent Xen Summit, Thomas Friebel presented a paper ("Preventing Guests from Spinning Around",
http://xen.org/files/xensummitboston08/LHP.pdf) investigating the interactions between spinlocks and virtual machines. Specifically, he looked at what happens when a lock-holding VCPU gets involuntarily preempted.

I find it interesting that gang scheduling the guest was not suggested as an obvious solution.

Anyway, concept looks fine; lguest's solution is more elegant of course :)

A little disappointing that you can't patch your version inline.

Cheers,
Rusty.

#24 lore raw
In reply to Jeremy Fitzhardinge
Quoted 4 lines · Jeremy Fitzhardinge

My experiments show that using a Xen-specific lock helps guest performance a bit (reduction in elapsed and system time in a kernbench run), but most significantly, reduces overall physical CPU consumption by 10%, and so increases overall system scalability.

that's rather impressive and looks nice, considering the fairly low impact.

as there were no fundamental objections in this thread i've created a tip/x86/paravirt-spinlocks topic branch for these patches and started testing them.

i based the topic branch on tip/xen-64bit, so you should be able to get the latest code by doing:

git-merge tip/x86/paravirt-spinlocks

on tip/master.

Ingo

#25 lore raw

PATCH 1/1 x86: paravirt spinlocks, !CONFIG_SMP build fixes (was: Re: [PATCH RFC 0/4] Paravirtual spinlocks)

Quoted 3 lines · Ingo Molnar

as there were no fundamental objections in this thread i've created a tip/x86/paravirt-spinlocks topic branch for these patches and started testing them.

small UP build fixes below.

Ingo

----------------->
commit c77bc635bb0486b0ddbe03012a8662b399ae9cdb

Author: Ingo Molnar <[email protected]>
Date:   Wed Jul 9 14:33:33 2008 +0200

x86: paravirt spinlocks, !CONFIG_SMP build fixes

Signed-off-by Ingo Molnar <[email protected]>
arch/x86/kernel/paravirt.c +4 -0
index bba4041..6aa8aed 100644
@@ -270,11 +270,13 @@ enum paravirt_lazy_mode paravirt_get_lazy_mode(void)
 
 void __init paravirt_use_bytelocks(void)
 {
+#ifdef CONFIG_SMP
 	pv_lock_ops.spin_is_locked = __byte_spin_is_locked;
 	pv_lock_ops.spin_is_contended = __byte_spin_is_contended;
 	pv_lock_ops.spin_lock = __byte_spin_lock;
 	pv_lock_ops.spin_trylock = __byte_spin_trylock;
 	pv_lock_ops.spin_unlock = __byte_spin_unlock;
+#endif
 }
 
 struct pv_info pv_info = {

@@ -461,12 +463,14 @@ struct pv_mmu_ops pv_mmu_ops = {
 };
 
 struct pv_lock_ops pv_lock_ops = {
+#ifdef CONFIG_SMP
 	.spin_is_locked = __ticket_spin_is_locked,
 	.spin_is_contended = __ticket_spin_is_contended,
 
 	.spin_lock = __ticket_spin_lock,
 	.spin_trylock = __ticket_spin_trylock,
 	.spin_unlock = __ticket_spin_unlock,
+#endif
 };
 
 EXPORT_SYMBOL_GPL(pv_time_ops);
include/asm-x86/paravirt.h +4 -0
index 65ed02c..b2aba8f 100644
@@ -1387,6 +1387,8 @@ void _paravirt_nop(void);
 
 void paravirt_use_bytelocks(void);
 
+#ifdef CONFIG_SMP
+
 static inline int __raw_spin_is_locked(struct raw_spinlock *lock)
 {
 	return PVOP_CALL1(int, pv_lock_ops.spin_is_locked, lock);

@@ -1412,6 +1414,8 @@ static __always_inline void __raw_spin_unlock(struct raw_spinlock *lock)
 	return PVOP_VCALL1(pv_lock_ops.spin_unlock, lock);
 }
 
+#endif
+
 /* These all sit in the .parainstructions section to tell us what to patch. */
 struct paravirt_patch_site {
 	u8 *instr; 		/* original instructions */
#26 lore raw

PATCH 1/1 x86: paravirt spinlocks, !CONFIG_SMP build fixes (was: Re: [PATCH RFC 0/4] Paravirtual spinlocks)

In reply to Ingo Molnar
Quoted 3 lines · Ingo Molnar

as there were no fundamental objections in this thread i've created a tip/x86/paravirt-spinlocks topic branch for these patches and started testing them.

small UP build fixes below.

Ingo

----------------->
commit c77bc635bb0486b0ddbe03012a8662b399ae9cdb

Author: Ingo Molnar <[email protected]>
Date:   Wed Jul 9 14:33:33 2008 +0200

x86: paravirt spinlocks, !CONFIG_SMP build fixes

Signed-off-by Ingo Molnar <[email protected]>
arch/x86/kernel/paravirt.c +4 -0
index bba4041..6aa8aed 100644
@@ -270,11 +270,13 @@ enum paravirt_lazy_mode paravirt_get_lazy_mode(void)
 
 void __init paravirt_use_bytelocks(void)
 {
+#ifdef CONFIG_SMP
 	pv_lock_ops.spin_is_locked = __byte_spin_is_locked;
 	pv_lock_ops.spin_is_contended = __byte_spin_is_contended;
 	pv_lock_ops.spin_lock = __byte_spin_lock;
 	pv_lock_ops.spin_trylock = __byte_spin_trylock;
 	pv_lock_ops.spin_unlock = __byte_spin_unlock;
+#endif
 }
 
 struct pv_info pv_info = {

@@ -461,12 +463,14 @@ struct pv_mmu_ops pv_mmu_ops = {
 };
 
 struct pv_lock_ops pv_lock_ops = {
+#ifdef CONFIG_SMP
 	.spin_is_locked = __ticket_spin_is_locked,
 	.spin_is_contended = __ticket_spin_is_contended,
 
 	.spin_lock = __ticket_spin_lock,
 	.spin_trylock = __ticket_spin_trylock,
 	.spin_unlock = __ticket_spin_unlock,
+#endif
 };
 
 EXPORT_SYMBOL_GPL(pv_time_ops);
include/asm-x86/paravirt.h +4 -0
index 65ed02c..b2aba8f 100644
@@ -1387,6 +1387,8 @@ void _paravirt_nop(void);
 
 void paravirt_use_bytelocks(void);
 
+#ifdef CONFIG_SMP
+
 static inline int __raw_spin_is_locked(struct raw_spinlock *lock)
 {
 	return PVOP_CALL1(int, pv_lock_ops.spin_is_locked, lock);

@@ -1412,6 +1414,8 @@ static __always_inline void __raw_spin_unlock(struct raw_spinlock *lock)
 	return PVOP_VCALL1(pv_lock_ops.spin_unlock, lock);
 }
 
+#endif
+
 /* These all sit in the .parainstructions section to tell us what to patch. */
 struct paravirt_patch_site {
 	u8 *instr; 		/* original instructions */
#27 lore raw

PATCH 1/1 x86: paravirt spinlocks, modular build fix (was: Re: [PATCH RFC 0/4] Paravirtual spinlocks)

In reply to Ingo Molnar

another small fixlet.

Ingo

----------------->
commit 0ea0f032767f41fb0a9586ab6acb5c1408ef16c5

Author: Ingo Molnar <[email protected]>
Date:   Wed Jul 9 14:39:15 2008 +0200

x86: paravirt spinlocks, modular build fix

fix:

MODPOST 408 modules
ERROR: "pv_lock_ops" [net/dccp/dccp.ko] undefined!
ERROR: "pv_lock_ops" [fs/jbd2/jbd2.ko] undefined!
ERROR: "pv_lock_ops" [drivers/media/common/saa7146_vv.ko] undefined!

Signed-off-by Ingo Molnar <[email protected]>
arch/x86/kernel/paravirt.c +1 -0
index 6aa8aed..3edfd7a 100644
@@ -472,6 +472,7 @@ struct pv_lock_ops pv_lock_ops = {
 	.spin_unlock = __ticket_spin_unlock,
 #endif
 };
+EXPORT_SYMBOL_GPL(pv_lock_ops);
 
 EXPORT_SYMBOL_GPL(pv_time_ops);
 EXPORT_SYMBOL    (pv_cpu_ops);
#28 lore raw

PATCH 1/1 x86: paravirt spinlocks, modular build fix (was: Re: [PATCH RFC 0/4] Paravirtual spinlocks)

In reply to Ingo Molnar

another small fixlet.

Ingo

----------------->
commit 0ea0f032767f41fb0a9586ab6acb5c1408ef16c5

Author: Ingo Molnar <[email protected]>
Date:   Wed Jul 9 14:39:15 2008 +0200

x86: paravirt spinlocks, modular build fix

fix:

MODPOST 408 modules
ERROR: "pv_lock_ops" [net/dccp/dccp.ko] undefined!
ERROR: "pv_lock_ops" [fs/jbd2/jbd2.ko] undefined!
ERROR: "pv_lock_ops" [drivers/media/common/saa7146_vv.ko] undefined!

Signed-off-by Ingo Molnar <[email protected]>
arch/x86/kernel/paravirt.c +1 -0
index 6aa8aed..3edfd7a 100644
@@ -472,6 +472,7 @@ struct pv_lock_ops pv_lock_ops = {
 	.spin_unlock = __ticket_spin_unlock,
 #endif
 };
+EXPORT_SYMBOL_GPL(pv_lock_ops);
 
 EXPORT_SYMBOL_GPL(pv_time_ops);
 EXPORT_SYMBOL    (pv_cpu_ops);
#29 lore raw
In reply to Ingo Molnar

the patches caused a boot hang with this config:

http://redhat.com/~mingo/misc/config-Wed_Jul__9_14_47_04_CEST_2008.bad

i have bisected it down to:

commit e17b58c2e85bc2ad2afc07fb8d898017c2b75ed1
Author: Jeremy Fitzhardinge <[email protected]>
Date: Mon Jul 7 12:07:53 2008 -0700

xen: implement Xen-specific spinlocks

i.e. applying that patch alone causes the hang. The hang happens in the ftrace self-test:

initcall utsname_sysctl_init+0x0/0x19 returned 0 after 0 msecs calling init_sched_switch_trace+0x0/0x4c
Testing tracer sched_switch: PASSED
initcall init_sched_switch_trace+0x0/0x4c returned 0 after 167 msecs calling init_function_trace+0x0/0x12
Testing tracer ftrace:
[hard hang]

it should have continued like this:

Testing tracer ftrace: PASSED
initcall init_function_trace+0x0/0x12 returned 0 after 198 msecs calling init_irqsoff_tracer+0x0/0x14
Testing tracer irqsoff: PASSED
initcall init_irqsoff_tracer+0x0/0x14 returned 0 after 3 msecs calling init_mmio_trace+0x0/0x12
initcall init_mmio_trace+0x0/0x12 returned 0 after 0 msecs

note: ftrace is a user of raw spinlocks. Another speciality of the config is that it has paravirt enabled (obviously), and that it also has lock debugging enabled.

Ingo

#30 lore raw

PATCH 1/1 x86, paravirt-spinlocks: fix boot hang (was: Re: [PATCH RFC 0/4] Paravirtual spinlocks)

Quoted 3 lines · Ingo Molnar

the patches caused a boot hang with this config:

http://redhat.com/~mingo/misc/config-Wed_Jul__9_14_47_04_CEST_2008.bad

ok, fixed it via the patch below.

Ingo

-------------->
commit 6412367fe22dc54cc727e7bec5bd65c36c1a0754

Author: Ingo Molnar <[email protected]>
Date:   Wed Jul 9 15:42:09 2008 +0200

x86, paravirt-spinlocks: fix boot hang

the paravirt-spinlock patches caused a boot hang with this config:

http://redhat.com/~mingo/misc/config-Wed_Jul__9_14_47_04_CEST_2008.bad

i have bisected it down to:

| commit e17b58c2e85bc2ad2afc07fb8d898017c2b75ed1 | Author: Jeremy Fitzhardinge <[email protected]>
| Date: Mon Jul 7 12:07:53 2008 -0700
|
| xen: implement Xen-specific spinlocks

i.e. applying that patch alone causes the hang. The hang happens in the ftrace self-test:

initcall utsname_sysctl_init+0x0/0x19 returned 0 after 0 msecs calling init_sched_switch_trace+0x0/0x4c
Testing tracer sched_switch: PASSED
initcall init_sched_switch_trace+0x0/0x4c returned 0 after 167 msecs calling init_function_trace+0x0/0x12
Testing tracer ftrace:
[hard hang]

it should have continued like this:

Testing tracer ftrace: PASSED
initcall init_function_trace+0x0/0x12 returned 0 after 198 msecs calling init_irqsoff_tracer+0x0/0x14
Testing tracer irqsoff: PASSED
initcall init_irqsoff_tracer+0x0/0x14 returned 0 after 3 msecs calling init_mmio_trace+0x0/0x12
initcall init_mmio_trace+0x0/0x12 returned 0 after 0 msecs

the problem is that such lowlevel primitives as spinlocks should never be built with -pg (which ftrace does). Marking paravirt.o as non-pg and marking all spinlock ops as always-inline solve the hang.

Signed-off-by Ingo Molnar <[email protected]>
arch/x86/kernel/Makefile +2 -1
index 2dd1ccd..faba669 100644
@@ -7,10 +7,11 @@ extra-y                := head_$(BITS).o head$(BITS).o head.o init_task.o vmlinu
 CPPFLAGS_vmlinux.lds += -U$(UTS_MACHINE)
 
 ifdef CONFIG_FTRACE
-# Do not profile debug utilities
+# Do not profile debug and lowlevel utilities
 CFLAGS_REMOVE_tsc_64.o = -pg
 CFLAGS_REMOVE_tsc_32.o = -pg
 CFLAGS_REMOVE_rtc.o = -pg
+CFLAGS_REMOVE_paravirt.o = -pg
 endif
 
 #
author
#31 lore raw

Re: [patch] x86, paravirt-spinlocks: fix boot hang

Quoted 52 lines · Ingo Molnar
Quoted 4 lines · Ingo Molnar

the patches caused a boot hang with this config:

http://redhat.com/~mingo/misc/config-Wed_Jul__9_14_47_04_CEST_2008.bad

ok, fixed it via the patch below.

Ingo

-------------->
commit 6412367fe22dc54cc727e7bec5bd65c36c1a0754

Author: Ingo Molnar <[email protected]>
Date:   Wed Jul 9 15:42:09 2008 +0200

x86, paravirt-spinlocks: fix boot hang

the paravirt-spinlock patches caused a boot hang with this config:

http://redhat.com/~mingo/misc/config-Wed_Jul__9_14_47_04_CEST_2008.bad

i have bisected it down to:

| commit e17b58c2e85bc2ad2afc07fb8d898017c2b75ed1 | Author: Jeremy Fitzhardinge <[email protected]>
| Date: Mon Jul 7 12:07:53 2008 -0700
|
| xen: implement Xen-specific spinlocks

i.e. applying that patch alone causes the hang. The hang happens in the ftrace self-test:

initcall utsname_sysctl_init+0x0/0x19 returned 0 after 0 msecs calling init_sched_switch_trace+0x0/0x4c
Testing tracer sched_switch: PASSED
initcall init_sched_switch_trace+0x0/0x4c returned 0 after 167 msecs calling init_function_trace+0x0/0x12
Testing tracer ftrace:
[hard hang]

it should have continued like this:

Testing tracer ftrace: PASSED
initcall init_function_trace+0x0/0x12 returned 0 after 198 msecs calling init_irqsoff_tracer+0x0/0x14
Testing tracer irqsoff: PASSED
initcall init_irqsoff_tracer+0x0/0x14 returned 0 after 3 msecs calling init_mmio_trace+0x0/0x12
initcall init_mmio_trace+0x0/0x12 returned 0 after 0 msecs

Quoted 4 lines

the problem is that such lowlevel primitives as spinlocks should never be built with -pg (which ftrace does). Marking paravirt.o as non-pg and marking all spinlock ops as always-inline solve the hang.

Thanks Ingo, that would have taken me a while to work out.

Presumably that means that xen/smp.o should also be built without -pg. In fact, should I move the spinlock code into its own file, so that ftrace can cover as much as it can?

J

#32 lore raw

Re: [patch] x86, paravirt-spinlocks: fix boot hang

Quoted 7 lines · Jeremy Fitzhardinge
Quoted 5 lines

should never
be built with -pg (which ftrace does). Marking paravirt.o as non-pg and marking all spinlock ops as always-inline solve the hang.

Thanks Ingo, that would have taken me a while to work out.

yeah, i figured i'd be the better candidate to debug ftrace related problems ;-)

Quoted 3 lines

Presumably that means that xen/smp.o should also be built without -pg. In fact, should I move the spinlock code into its own file, so that ftrace can cover as much as it can?

hm, yeah. Anything that can be called via the lowest level spinlock functions should be either notrace, or, better, in a -pg-excluded .o file. Putting it all into a separate file would cover it nicely i think.

Ingo

#33 lore raw

Re: [patch] x86, paravirt-spinlocks: fix boot hang

In reply to Jeremy Fitzhardinge
Quoted 7 lines · Jeremy Fitzhardinge
Quoted 5 lines

should never
be built with -pg (which ftrace does). Marking paravirt.o as non-pg and marking all spinlock ops as always-inline solve the hang.

Thanks Ingo, that would have taken me a while to work out.

yeah, i figured i'd be the better candidate to debug ftrace related problems ;-)

Quoted 3 lines

Presumably that means that xen/smp.o should also be built without -pg. In fact, should I move the spinlock code into its own file, so that ftrace can cover as much as it can?

hm, yeah. Anything that can be called via the lowest level spinlock functions should be either notrace, or, better, in a -pg-excluded .o file. Putting it all into a separate file would cover it nicely i think.

Ingo

author
#34 lore raw

Re: [patch] x86, paravirt-spinlocks: fix boot hang

In reply to Ingo Molnar
Quoted 52 lines · Ingo Molnar
Quoted 4 lines · Ingo Molnar

the patches caused a boot hang with this config:

http://redhat.com/~mingo/misc/config-Wed_Jul__9_14_47_04_CEST_2008.bad

ok, fixed it via the patch below.

Ingo

-------------->
commit 6412367fe22dc54cc727e7bec5bd65c36c1a0754

Author: Ingo Molnar <[email protected]>
Date:   Wed Jul 9 15:42:09 2008 +0200

x86, paravirt-spinlocks: fix boot hang

the paravirt-spinlock patches caused a boot hang with this config:

http://redhat.com/~mingo/misc/config-Wed_Jul__9_14_47_04_CEST_2008.bad

i have bisected it down to:

| commit e17b58c2e85bc2ad2afc07fb8d898017c2b75ed1 | Author: Jeremy Fitzhardinge <[email protected]>
| Date: Mon Jul 7 12:07:53 2008 -0700
|
| xen: implement Xen-specific spinlocks

i.e. applying that patch alone causes the hang. The hang happens in the ftrace self-test:

initcall utsname_sysctl_init+0x0/0x19 returned 0 after 0 msecs calling init_sched_switch_trace+0x0/0x4c
Testing tracer sched_switch: PASSED
initcall init_sched_switch_trace+0x0/0x4c returned 0 after 167 msecs calling init_function_trace+0x0/0x12
Testing tracer ftrace:
[hard hang]

it should have continued like this:

Testing tracer ftrace: PASSED
initcall init_function_trace+0x0/0x12 returned 0 after 198 msecs calling init_irqsoff_tracer+0x0/0x14
Testing tracer irqsoff: PASSED
initcall init_irqsoff_tracer+0x0/0x14 returned 0 after 3 msecs calling init_mmio_trace+0x0/0x12
initcall init_mmio_trace+0x0/0x12 returned 0 after 0 msecs

Quoted 4 lines

the problem is that such lowlevel primitives as spinlocks should never be built with -pg (which ftrace does). Marking paravirt.o as non-pg and marking all spinlock ops as always-inline solve the hang.

Thanks Ingo, that would have taken me a while to work out.

Presumably that means that xen/smp.o should also be built without -pg. In fact, should I move the spinlock code into its own file, so that ftrace can cover as much as it can?

J

#35 lore raw

PATCH 1/1 x86, paravirt-spinlocks: fix boot hang (was: Re: [PATCH RFC 0/4] Paravirtual spinlocks)

In reply to Ingo Molnar
Quoted 3 lines · Ingo Molnar

the patches caused a boot hang with this config:

http://redhat.com/~mingo/misc/config-Wed_Jul__9_14_47_04_CEST_2008.bad

ok, fixed it via the patch below.

Ingo

-------------->
commit 6412367fe22dc54cc727e7bec5bd65c36c1a0754

Author: Ingo Molnar <[email protected]>
Date:   Wed Jul 9 15:42:09 2008 +0200

x86, paravirt-spinlocks: fix boot hang

the paravirt-spinlock patches caused a boot hang with this config:

http://redhat.com/~mingo/misc/config-Wed_Jul__9_14_47_04_CEST_2008.bad

i have bisected it down to:

| commit e17b58c2e85bc2ad2afc07fb8d898017c2b75ed1 | Author: Jeremy Fitzhardinge <[email protected]>
| Date: Mon Jul 7 12:07:53 2008 -0700
|
| xen: implement Xen-specific spinlocks

i.e. applying that patch alone causes the hang. The hang happens in the ftrace self-test:

initcall utsname_sysctl_init+0x0/0x19 returned 0 after 0 msecs calling init_sched_switch_trace+0x0/0x4c
Testing tracer sched_switch: PASSED
initcall init_sched_switch_trace+0x0/0x4c returned 0 after 167 msecs calling init_function_trace+0x0/0x12
Testing tracer ftrace:
[hard hang]

it should have continued like this:

Testing tracer ftrace: PASSED
initcall init_function_trace+0x0/0x12 returned 0 after 198 msecs calling init_irqsoff_tracer+0x0/0x14
Testing tracer irqsoff: PASSED
initcall init_irqsoff_tracer+0x0/0x14 returned 0 after 3 msecs calling init_mmio_trace+0x0/0x12
initcall init_mmio_trace+0x0/0x12 returned 0 after 0 msecs

the problem is that such lowlevel primitives as spinlocks should never be built with -pg (which ftrace does). Marking paravirt.o as non-pg and marking all spinlock ops as always-inline solve the hang.

Signed-off-by Ingo Molnar <[email protected]>
arch/x86/kernel/Makefile +2 -1
index 2dd1ccd..faba669 100644
@@ -7,10 +7,11 @@ extra-y                := head_$(BITS).o head$(BITS).o head.o init_task.o vmlinu
 CPPFLAGS_vmlinux.lds += -U$(UTS_MACHINE)
 
 ifdef CONFIG_FTRACE
-# Do not profile debug utilities
+# Do not profile debug and lowlevel utilities
 CFLAGS_REMOVE_tsc_64.o = -pg
 CFLAGS_REMOVE_tsc_32.o = -pg
 CFLAGS_REMOVE_rtc.o = -pg
+CFLAGS_REMOVE_paravirt.o = -pg
 endif
 
 #
#36 lore raw
In reply to Ingo Molnar

the patches caused a boot hang with this config:

http://redhat.com/~mingo/misc/config-Wed_Jul__9_14_47_04_CEST_2008.bad

i have bisected it down to:

commit e17b58c2e85bc2ad2afc07fb8d898017c2b75ed1
Author: Jeremy Fitzhardinge <[email protected]>
Date: Mon Jul 7 12:07:53 2008 -0700

xen: implement Xen-specific spinlocks

i.e. applying that patch alone causes the hang. The hang happens in the ftrace self-test:

initcall utsname_sysctl_init+0x0/0x19 returned 0 after 0 msecs calling init_sched_switch_trace+0x0/0x4c
Testing tracer sched_switch: PASSED
initcall init_sched_switch_trace+0x0/0x4c returned 0 after 167 msecs calling init_function_trace+0x0/0x12
Testing tracer ftrace:
[hard hang]

it should have continued like this:

Testing tracer ftrace: PASSED
initcall init_function_trace+0x0/0x12 returned 0 after 198 msecs calling init_irqsoff_tracer+0x0/0x14
Testing tracer irqsoff: PASSED
initcall init_irqsoff_tracer+0x0/0x14 returned 0 after 3 msecs calling init_mmio_trace+0x0/0x12
initcall init_mmio_trace+0x0/0x12 returned 0 after 0 msecs

note: ftrace is a user of raw spinlocks. Another speciality of the config is that it has paravirt enabled (obviously), and that it also has lock debugging enabled.

Ingo

#37 lore raw
In reply to Jeremy Fitzhardinge
Quoted 4 lines · Jeremy Fitzhardinge

My experiments show that using a Xen-specific lock helps guest performance a bit (reduction in elapsed and system time in a kernbench run), but most significantly, reduces overall physical CPU consumption by 10%, and so increases overall system scalability.

that's rather impressive and looks nice, considering the fairly low impact.

as there were no fundamental objections in this thread i've created a tip/x86/paravirt-spinlocks topic branch for these patches and started testing them.

i based the topic branch on tip/xen-64bit, so you should be able to get the latest code by doing:

git-merge tip/x86/paravirt-spinlocks

on tip/master.

Ingo