* Raghavendra K T <raghavendra.kt@xxxxxxxxxxxxxxxxxx> wrote: > This series replaces the existing paravirtualized spinlock mechanism > with a paravirtualized ticketlock mechanism. The series provides > implementation for both Xen and KVM.(targeted for 3.5 window) > > Note: This needs debugfs changes patch that should be in Xen / linux-next > https://lkml.org/lkml/2012/3/30/687 > > Changes in V8: > - Reabsed patches to 3.4-rc4 > - Combined the KVM changes with ticketlock + Xen changes (Ingo) > - Removed CAP_PV_UNHALT since it is redundant (Avi). But note that we > need newer qemu which uses KVM_GET_SUPPORTED_CPUID ioctl. > - Rewrite GET_MP_STATE condition (Avi) > - Make pv_unhalt = bool (Avi) > - Move out reset pv_unhalt code to vcpu_run from vcpu_block (Gleb) > - Documentation changes (Rob Landley) > - Have a printk to recognize that paravirt spinlock is enabled (Nikunj) > - Move out kick hypercall out of CONFIG_PARAVIRT_SPINLOCK now > so that it can be used for other optimizations such as > flush_tlb_ipi_others etc. (Nikunj) > > Ticket locks have an inherent problem in a virtualized case, because > the vCPUs are scheduled rather than running concurrently (ignoring > gang scheduled vCPUs). This can result in catastrophic performance > collapses when the vCPU scheduler doesn't schedule the correct "next" > vCPU, and ends up scheduling a vCPU which burns its entire timeslice > spinning. (Note that this is not the same problem as lock-holder > preemption, which this series also addresses; that's also a problem, > but not catastrophic). > > (See Thomas Friebel's talk "Prevent Guests from Spinning Around" > http://www.xen.org/files/xensummitboston08/LHP.pdf for more details.) > > Currently we deal with this by having PV spinlocks, which adds a layer > of indirection in front of all the spinlock functions, and defining a > completely new implementation for Xen (and for other pvops users, but > there are none at present). > > PV ticketlocks keeps the existing ticketlock implemenentation > (fastpath) as-is, but adds a couple of pvops for the slow paths: > > - If a CPU has been waiting for a spinlock for SPIN_THRESHOLD > iterations, then call out to the __ticket_lock_spinning() pvop, > which allows a backend to block the vCPU rather than spinning. This > pvop can set the lock into "slowpath state". > > - When releasing a lock, if it is in "slowpath state", the call > __ticket_unlock_kick() to kick the next vCPU in line awake. If the > lock is no longer in contention, it also clears the slowpath flag. > > The "slowpath state" is stored in the LSB of the within the lock tail > ticket. This has the effect of reducing the max number of CPUs by > half (so, a "small ticket" can deal with 128 CPUs, and "large ticket" > 32768). > > For KVM, one hypercall is introduced in hypervisor,that allows a vcpu to kick > another vcpu out of halt state. > The blocking of vcpu is done using halt() in (lock_spinning) slowpath. > > Overall, it results in a large reduction in code, it makes the native > and virtualized cases closer, and it removes a layer of indirection > around all the spinlock functions. > > The fast path (taking an uncontended lock which isn't in "slowpath" > state) is optimal, identical to the non-paravirtualized case. > > The inner part of ticket lock code becomes: > inc = xadd(&lock->tickets, inc); > inc.tail &= ~TICKET_SLOWPATH_FLAG; > > if (likely(inc.head == inc.tail)) > goto out; > for (;;) { > unsigned count = SPIN_THRESHOLD; > do { > if (ACCESS_ONCE(lock->tickets.head) == inc.tail) > goto out; > cpu_relax(); > } while (--count); > __ticket_lock_spinning(lock, inc.tail); > } > out: barrier(); > which results in: > push %rbp > mov %rsp,%rbp > > mov $0x200,%eax > lock xadd %ax,(%rdi) > movzbl %ah,%edx > cmp %al,%dl > jne 1f # Slowpath if lock in contention > > pop %rbp > retq > > ### SLOWPATH START > 1: and $-2,%edx > movzbl %dl,%esi > > 2: mov $0x800,%eax > jmp 4f > > 3: pause > sub $0x1,%eax > je 5f > > 4: movzbl (%rdi),%ecx > cmp %cl,%dl > jne 3b > > pop %rbp > retq > > 5: callq *__ticket_lock_spinning > jmp 2b > ### SLOWPATH END > > with CONFIG_PARAVIRT_SPINLOCKS=n, the code has changed slightly, where > the fastpath case is straight through (taking the lock without > contention), and the spin loop is out of line: > > push %rbp > mov %rsp,%rbp > > mov $0x100,%eax > lock xadd %ax,(%rdi) > movzbl %ah,%edx > cmp %al,%dl > jne 1f > > pop %rbp > retq > > ### SLOWPATH START > 1: pause > movzbl (%rdi),%eax > cmp %dl,%al > jne 1b > > pop %rbp > retq > ### SLOWPATH END > > The unlock code is complicated by the need to both add to the lock's > "head" and fetch the slowpath flag from "tail". This version of the > patch uses a locked add to do this, followed by a test to see if the > slowflag is set. The lock prefix acts as a full memory barrier, so we > can be sure that other CPUs will have seen the unlock before we read > the flag (without the barrier the read could be fetched from the > store queue before it hits memory, which could result in a deadlock). > > This is is all unnecessary complication if you're not using PV ticket > locks, it also uses the jump-label machinery to use the standard > "add"-based unlock in the non-PV case. > > if (TICKET_SLOWPATH_FLAG && > static_key_false(¶virt_ticketlocks_enabled))) { > arch_spinlock_t prev; > prev = *lock; > add_smp(&lock->tickets.head, TICKET_LOCK_INC); > > /* add_smp() is a full mb() */ > if (unlikely(lock->tickets.tail & TICKET_SLOWPATH_FLAG)) > __ticket_unlock_slowpath(lock, prev); > } else > __add(&lock->tickets.head, TICKET_LOCK_INC, UNLOCK_LOCK_PREFIX); > which generates: > push %rbp > mov %rsp,%rbp > > nop5 # replaced by 5-byte jmp 2f when PV enabled > > # non-PV unlock > addb $0x2,(%rdi) > > 1: pop %rbp > retq > > ### PV unlock ### > 2: movzwl (%rdi),%esi # Fetch prev > > lock addb $0x2,(%rdi) # Do unlock > > testb $0x1,0x1(%rdi) # Test flag > je 1b # Finished if not set > > ### Slow path ### > add $2,%sil # Add "head" in old lock state > mov %esi,%edx > and $0xfe,%dh # clear slowflag for comparison > movzbl %dh,%eax > cmp %dl,%al # If head == tail (uncontended) > je 4f # clear slowpath flag > > # Kick next CPU waiting for lock > 3: movzbl %sil,%esi > callq *pv_lock_ops.kick > > pop %rbp > retq > > # Lock no longer contended - clear slowflag > 4: mov %esi,%eax > lock cmpxchg %dx,(%rdi) # cmpxchg to clear flag > cmp %si,%ax > jne 3b # If clear failed, then kick > > pop %rbp > retq > > So when not using PV ticketlocks, the unlock sequence just has a > 5-byte nop added to it, and the PV case is reasonable straightforward > aside from requiring a "lock add". > > TODO: 1) Remove CONFIG_PARAVIRT_SPINLOCK ? > 2) Experiments on further optimization possibilities. (discussed in V6) > 3) Use kvm_irq_delivery_to_apic() in kvm hypercall (suggested by Gleb) > 4) Any cleanups for e.g. Xen/KVM common code for debugfs. > > PS: TODOs are no blockers for the current series merge. > > Results: > ======= > various form of results based on V6 of the patch series are posted in following links > > https://lkml.org/lkml/2012/3/21/161 > https://lkml.org/lkml/2012/3/21/198 > > kvm results: > https://lkml.org/lkml/2012/3/23/50 > https://lkml.org/lkml/2012/4/5/73 > > Benchmarking on the current set of patches will be posted soon. > > Thoughts? Comments? Suggestions?. It would be nice to see > Acked-by/Reviewed-by/Tested-by for the patch series. > > Jeremy Fitzhardinge (9): > x86/spinlock: Replace pv spinlocks with pv ticketlocks > x86/ticketlock: Collapse a layer of functions > xen: Defer spinlock setup until boot CPU setup > xen/pvticketlock: Xen implementation for PV ticket locks > xen/pvticketlocks: Add xen_nopvspin parameter to disable xen pv > ticketlocks > x86/pvticketlock: Use callee-save for lock_spinning > x86/pvticketlock: When paravirtualizing ticket locks, increment by 2 > x86/ticketlock: Add slowpath logic > xen/pvticketlock: Allow interrupts to be enabled while blocking > > Srivatsa Vaddagiri (3): > Add a hypercall to KVM hypervisor to support pv-ticketlocks > Added configuration support to enable debug information for KVM Guests > Paravirtual ticketlock support for linux guests running on KVM hypervisor > > Raghavendra K T (3): > x86/ticketlock: Don't inline _spin_unlock when using paravirt > spinlocks > Fold pv_unhalt flag into GET_MP_STATE ioctl to aid migration > Add documentation on Hypercalls and features used for PV spinlock > > Andrew Jones (1): > Split out rate limiting from jump_label.h > > Stefano Stabellini (1): > xen: Enable PV ticketlocks on HVM Xen > --- > PS: Had to trim down recipient list because, LKML archive does not support > list > 20. Though many more people should have been in To/CC list. > > Ticketlock links: > V7 : https://lkml.org/lkml/2012/4/19/335 > V6 : https://lkml.org/lkml/2012/3/21/161 > > KVM patch links: > V6: https://lkml.org/lkml/2012/4/23/123 > > V5 kernel changes: > https://lkml.org/lkml/2012/3/23/50 > Qemu changes for V5: > http://lists.gnu.org/archive/html/qemu-devel/2012-03/msg04455.html > > V4 kernel changes: > https://lkml.org/lkml/2012/1/14/66 > Qemu changes for V4: > http://www.mail-archive.com/kvm@xxxxxxxxxxxxxxx/msg66450.html > > V3 kernel Changes: > https://lkml.org/lkml/2011/11/30/62 > Qemu patch for V3: > http://lists.gnu.org/archive/html/qemu-devel/2011-12/msg00397.html > > V2 kernel changes : > https://lkml.org/lkml/2011/10/23/207 > > Previous discussions : (posted by Srivatsa V). > https://lkml.org/lkml/2010/7/26/24 > https://lkml.org/lkml/2011/1/19/212 > > Ticketlock change history: > Changes in V7: > - Reabsed patches to 3.4-rc3 > - Added jumplabel split patch (originally from Andrew Jones rebased to > 3.4-rc3 > - jumplabel changes from Ingo and Jason taken and now using static_key_* > instead of static_branch. > - using UNINLINE_SPIN_UNLOCK (which was splitted as per suggestion from Linus) > - This patch series is rebased on debugfs patch (that sould be already in > Xen/linux-next https://lkml.org/lkml/2012/3/23/51) > > Changes in V6 posting: (Raghavendra K T) > - Rebased to linux-3.3-rc6. > - used function+enum in place of macro (better type checking) > - use cmpxchg while resetting zero status for possible race > [suggested by Dave Hansen for KVM patches ] > > KVM patch Change history: > Changes in V6: > - Rebased to 3.4-rc3 > - Removed debugfs changes patch which should now be in Xen/linux-next. > (https://lkml.org/lkml/2012/3/30/687) > - Removed PV_UNHALT_MSR since currently we don't need guest communication, > and made pv_unhalt folded to GET_MP_STATE (Marcello, Avi[long back]) > - Take jumplabel changes from Ingo/Jason into use (static_key_slow_inc usage) > - Added inline to spinlock_init in non PARAVIRT case > - Move arch specific code to arch/x86 and add stubs to other archs (Marcello) > - Added more comments on pv_unhalt usage etc (Marcello) > > Changes in V5: > - rebased to 3.3-rc6 > - added PV_UNHALT_MSR that would help in live migration (Avi) > - removed PV_LOCK_KICK vcpu request and pv_unhalt flag (re)added. > - Changed hypercall documentaion (Alex). > - mode_t changed to umode_t in debugfs. > - MSR related documentation added. > - rename PV_LOCK_KICK to PV_UNHALT. > - host and guest patches not mixed. (Marcelo, Alex) > - kvm_kick_cpu now takes cpu so it can be used by flush_tlb_ipi_other > paravirtualization (Nikunj) > - coding style changes in variable declarion etc (Srikar) > > Changes in V4: > - reabsed to 3.2.0 pre. > - use APIC ID for kicking the vcpu and use kvm_apic_match_dest for matching (Avi) > - fold vcpu->kicked flag into vcpu->requests (KVM_REQ_PVLOCK_KICK) and related > changes for UNHALT path to make pv ticket spinlock migration friendly(Avi, Marcello) > - Added Documentation for CPUID, Hypercall (KVM_HC_KICK_CPU) > and capabilty (KVM_CAP_PVLOCK_KICK) (Avi) > - Remove unneeded kvm_arch_vcpu_ioctl_set_mpstate call. (Marcello) > - cumulative variable type changed (int ==> u32) in add_stat (Konrad) > - remove unneeded kvm_guest_init for !CONFIG_KVM_GUEST case > > Changes in V3: > - rebased to 3.2-rc1 > - use halt() instead of wait for kick hypercall. > - modify kick hyper call to do wakeup halted vcpu. > - hook kvm_spinlock_init to smp_prepare_cpus call (moved the call out of head##.c). > - fix the potential race when zero_stat is read. > - export debugfs_create_32 and add documentation to API. > - use static inline and enum instead of ADDSTAT macro. > - add barrier() in after setting kick_vcpu. > - empty static inline function for kvm_spinlock_init. > - combine the patches one and two readuce overhead. > - make KVM_DEBUGFS depends on DEBUGFS. > - include debugfs header unconditionally. > > Changes in V2: > - rebased patchesto -rc9 > - synchronization related changes based on Jeremy's changes > (Jeremy Fitzhardinge <jeremy.fitzhardinge@xxxxxxxxxx>) pointed by > Stephan Diestelhorst <stephan.diestelhorst@xxxxxxx> > - enabling 32 bit guests > - splitted patches into two more chunks > > Documentation/virtual/kvm/cpuid.txt | 4 + > Documentation/virtual/kvm/hypercalls.txt | 60 +++++ > arch/x86/Kconfig | 10 + > arch/x86/include/asm/kvm_host.h | 4 + > arch/x86/include/asm/kvm_para.h | 16 +- > arch/x86/include/asm/paravirt.h | 32 +-- > arch/x86/include/asm/paravirt_types.h | 10 +- > arch/x86/include/asm/spinlock.h | 128 +++++++---- > arch/x86/include/asm/spinlock_types.h | 16 +- > arch/x86/kernel/kvm.c | 256 ++++++++++++++++++++ > arch/x86/kernel/paravirt-spinlocks.c | 18 +- > arch/x86/kvm/cpuid.c | 3 +- > arch/x86/kvm/x86.c | 44 ++++- > arch/x86/xen/smp.c | 3 +- > arch/x86/xen/spinlock.c | 387 ++++++++++-------------------- > include/linux/jump_label.h | 26 +-- > include/linux/jump_label_ratelimit.h | 34 +++ > include/linux/kvm_para.h | 1 + > include/linux/perf_event.h | 1 + > kernel/jump_label.c | 1 + > 20 files changed, 673 insertions(+), 381 deletions(-) This is looking pretty good and complete now - any objections from anyone to trying this out in a separate x86 topic tree? Thanks, Ingo -- To unsubscribe from this list: send the line "unsubscribe linux-doc" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
