Messages in this thread | | | Date | Thu, 09 Apr 2015 17:41:44 -0400 | From | Waiman Long <> | Subject | Re: [PATCH v15 09/15] pvqspinlock: Implement simple paravirt support for the qspinlock |
| |
On 04/09/2015 02:13 PM, Peter Zijlstra wrote: > On Mon, Apr 06, 2015 at 10:55:44PM -0400, Waiman Long wrote: >> +++ b/kernel/locking/qspinlock_paravirt.h >> @@ -0,0 +1,321 @@ >> +#ifndef _GEN_PV_LOCK_SLOWPATH >> +#error "do not include this file" >> +#endif >> + >> +/* >> + * Implement paravirt qspinlocks; the general idea is to halt the vcpus instead >> + * of spinning them. >> + * >> + * This relies on the architecture to provide two paravirt hypercalls: >> + * >> + * pv_wait(u8 *ptr, u8 val) -- suspends the vcpu if *ptr == val >> + * pv_kick(cpu) -- wakes a suspended vcpu >> + * >> + * Using these we implement __pv_queue_spin_lock_slowpath() and >> + * __pv_queue_spin_unlock() to replace native_queue_spin_lock_slowpath() and >> + * native_queue_spin_unlock(). >> + */ >> + >> +#define _Q_SLOW_VAL (3U<< _Q_LOCKED_OFFSET) >> + >> +enum vcpu_state { >> + vcpu_running = 0, >> + vcpu_halted, >> +}; >> + >> +struct pv_node { >> + struct mcs_spinlock mcs; >> + struct mcs_spinlock __res[3]; >> + >> + int cpu; >> + u8 state; >> +}; >> + >> +/* >> + * Hash table using open addressing with an LFSR probe sequence. >> + * >> + * Since we should not be holding locks from NMI context (very rare indeed) the >> + * max load factor is 0.75, which is around the point where open addressing >> + * breaks down. >> + * >> + * Instead of probing just the immediate bucket we probe all buckets in the >> + * same cacheline. >> + * >> + * http://en.wikipedia.org/wiki/Hash_table#Open_addressing >> + * >> + * Dynamically allocate a hash table big enough to hold at least 4X the >> + * number of possible cpus in the system. Allocation is done on page >> + * granularity. So the minimum number of hash buckets should be at least >> + * 256 to fully utilize a 4k page. >> + */ >> +#define LFSR_MIN_BITS 8 >> +#define LFSR_MAX_BITS (2 + NR_CPUS_BITS) >> +#if LFSR_MAX_BITS< LFSR_MIN_BITS >> +#undef LFSR_MAX_BITS >> +#define LFSR_MAX_BITS LFSR_MIN_BITS >> +#endif >> + >> +struct pv_hash_bucket { >> + struct qspinlock *lock; >> + struct pv_node *node; >> +}; >> +#define PV_HB_PER_LINE (SMP_CACHE_BYTES / sizeof(struct pv_hash_bucket)) >> +#define HB_RESERVED ((struct qspinlock *)1) > This is unused.
You are right, I will remove that.
>> + >> +static struct pv_hash_bucket *pv_lock_hash; >> +static unsigned int pv_lock_hash_bits __read_mostly; > static unsigned int pv_taps __read_mostly;
It will depend on whether we keep the lfsr code or not.
>> + >> +#include<linux/hash.h> >> +#include<linux/lfsr.h> >> +#include<linux/bootmem.h> >> + >> +/* >> + * Allocate memory for the PV qspinlock hash buckets >> + * >> + * This function should be called from the paravirt spinlock initialization >> + * routine. >> + */ >> +void __init __pv_init_lock_hash(void) >> +{ >> + int pv_hash_size = 4 * num_possible_cpus(); >> + >> + if (pv_hash_size< (1U<< LFSR_MIN_BITS)) >> + pv_hash_size = (1U<< LFSR_MIN_BITS); >> + /* >> + * Allocate space from bootmem which should be page-size aligned >> + * and hence cacheline aligned. >> + */ >> + pv_lock_hash = alloc_large_system_hash("PV qspinlock", >> + sizeof(struct pv_hash_bucket), >> + pv_hash_size, 0, HASH_EARLY, >> + &pv_lock_hash_bits, NULL, >> + pv_hash_size, pv_hash_size); > pv_taps = lfsr_taps(pv_lock_hash_bits); >
I don't understand what you meant here.
>> +} >> + >> +static inline u32 hash_align(u32 hash) >> +{ >> + return hash& ~(PV_HB_PER_LINE - 1); >> +} >> + >> +static struct qspinlock **pv_hash(struct qspinlock *lock, struct pv_node *node) >> +{ >> + unsigned long init_hash, hash = hash_ptr(lock, pv_lock_hash_bits); >> + struct pv_hash_bucket *hb, *end; >> + >> + if (!hash) >> + hash = 1; >> + >> + init_hash = hash; >> + hb =&pv_lock_hash[hash_align(hash)]; >> + for (;;) { >> + for (end = hb + PV_HB_PER_LINE; hb< end; hb++) { >> + if (!cmpxchg(&hb->lock, NULL, lock)) { >> + WRITE_ONCE(hb->node, node); >> + /* >> + * We haven't set the _Q_SLOW_VAL yet. So >> + * the order of writing doesn't matter. >> + */ >> + smp_wmb(); /* matches rmb from pv_hash_find */ > This doesn't make sense. Both sites do ->lock first and ->node second. > No amount of ordering can 'fix' that. > > I think we can safely remove this wmb and the rmb below, because the > required ordering is already provided by setting/observing l->locked == > SLOW. >
Right, I was over-cautious here. Will remove that.
>> + goto done; >> + } >> + } >> + >> + hash = lfsr(hash, pv_lock_hash_bits, 0); > Since pv_lock_hash_bits is a variable, you end up running through that > massive if() forest to find the corresponding tap every single time. It > cannot compile-time optimize it.
The minimum bits size is now 8. So unless the system has more than 64 vCPUs, it will get the right value in the first if statement.
> Hence: > hash = lfsr(hash, pv_taps); > > (I don't get the bits argument to the lfsr). > > In any case, like I said before, I think we should try a linear probe > sequence first, the lfsr was over engineering from my side.
As I said before, I am fine with removing the lfsr() code.
>> + hb =&pv_lock_hash[hash_align(hash)]; >> + BUG_ON(hash == init_hash); >> + } >> + >> +done: >> + return&hb->lock; >> +} >> + >> +static struct pv_node *pv_hash_find(struct qspinlock *lock) >> +{ >> + unsigned long init_hash, hash = hash_ptr(lock, pv_lock_hash_bits); >> + struct pv_hash_bucket *hb, *end; >> + struct pv_node *node = NULL; >> + >> + if (!hash) >> + hash = 1; >> + >> + init_hash = hash; >> + hb =&pv_lock_hash[hash_align(hash)]; >> + for (;;) { >> + for (end = hb + PV_HB_PER_LINE; hb< end; hb++) { >> + struct qspinlock *l = READ_ONCE(hb->lock); >> + >> + if (l == lock) { >> + smp_rmb(); /* matches wmb from pv_hash() */ > per the above this can go, IF we observe SLOW we must also observe a > consistent bucket.
Will remove that.
>> + node = READ_ONCE(hb->node); >> + goto done; >> + } >> + } >> + >> + hash = lfsr(hash, pv_lock_hash_bits, 0); > idem the previous lfsr comment. > >> + hb =&pv_lock_hash[hash_align(hash)]; >> + BUG_ON(hash == init_hash); >> + } >> +done: >> + /* >> + * Clear the hash bucket >> + */ >> + WRITE_ONCE(hb->lock, NULL); >> + return node; >> +} >> +/* >> + * Wait for l->locked to become clear; halt the vcpu after a short spin. >> + * __pv_queue_spin_unlock() will wake us. >> + */ >> +static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) >> +{ >> + struct __qspinlock *l = (void *)lock; >> + struct qspinlock **lp = NULL; >> + struct pv_node *pn = (struct pv_node *)node; >> + int slow_set = false; >> + int loop; >> + >> + for (;;) { >> + for (loop = SPIN_THRESHOLD; loop; loop--) { >> + if (!READ_ONCE(l->locked)) >> + return; >> + >> + cpu_relax(); >> + } >> + >> + WRITE_ONCE(pn->state, vcpu_halted); >> + if (!lp) >> + lp = pv_hash(lock, pn); >> + /* >> + * lp must be set before setting _Q_SLOW_VAL >> + * >> + * [S] lp = lock [RmW] l = l->locked = 0 >> + * MB MB >> + * [S] l->locked = _Q_SLOW_VAL [L] lp >> + * >> + * Matches the cmpxchg() in pv_queue_spin_unlock(). >> + */ >> + if (!slow_set&& >> + !cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL)) { >> + /* >> + * The lock is free and _Q_SLOW_VAL has never been >> + * set. Need to clear the hash bucket before getting >> + * the lock. >> + */ >> + WRITE_ONCE(*lp, NULL); >> + return; >> + } else if (slow_set&& !READ_ONCE(l->locked)) >> + return; >> + slow_set = true; > I'm somewhat puzzled by the slow_set thing; what is wrong with the thing > I had, namely: > > if (!lp) { > lp = pv_hash(lock, pn); > > /* > * comment > */ > lv = cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL); > if (lv != _Q_LOCKED_VAL) { > /* we're woken, unhash and return */ > WRITE_ONCE(*lp, NULL); > return; > } > } >> + >> + pv_wait(&l->locked, _Q_SLOW_VAL); > > If we get a spurious wakeup (due to device interrupts or random kick) > we'll loop around but ->locked will remain _Q_SLOW_VAL.
The purpose of the slow_set flag is not about the lock value. It is to make sure that pv_hash_find() will always find a match. Consider the following scenario:
cpu1 cpu2 cpu3 ---- ---- ---- pv_wait spurious wakeup loop l->locked
read _Q_SLOW_VAL pv_hash_find() unlock
pv_hash() <- same entry
cmpxchg(&l->locked) clear hash (?)
Here, the entry for cpu3 will be removed leading to panic when pv_hash_find() can find the entry. So the hash entry can only be removed if the other cpu has no chance to see _Q_SLOW_VAL.
>> + } >> + /* >> + * Lock is unlocked now; the caller will acquire it without waiting. >> + * As with pv_wait_node() we rely on the caller to do a load-acquire >> + * for us. >> + */ >> +} >> + >> +/* >> + * To be used in stead of queue_spin_unlock() for paravirt locks. Wakes >> + * pv_wait_head() if appropriate. >> + */ >> +__visible void __pv_queue_spin_unlock(struct qspinlock *lock) >> +{ >> + struct __qspinlock *l = (void *)lock; >> + struct pv_node *node; >> + >> + if (likely(cmpxchg(&l->locked, _Q_LOCKED_VAL, 0) == _Q_LOCKED_VAL)) >> + return; >> + >> + /* >> + * The queue head has been halted. Need to locate it and wake it up. >> + */ >> + node = pv_hash_find(lock); >> + smp_store_release(&l->locked, 0); > Ah yes, clever that. > >> + /* >> + * At this point the memory pointed at by lock can be freed/reused, >> + * however we can still use the PV node to kick the CPU. >> + */ >> + if (READ_ONCE(node->state) == vcpu_halted) >> + pv_kick(node->cpu); >> +} >> +PV_CALLEE_SAVE_REGS_THUNK(__pv_queue_spin_unlock); > However I feel the PV_CALLEE_SAVE_REGS_THUNK thing belongs in the x86 > code.
That is why I originally put my version of the qspinlock_paravirt.h header file under arch/x86/include/asm. Maybe we should move it back there. Putting the thunk in arch/x86/kernel/kvm.c didn't work when you consider that the Xen code also need that.
Cheers, Longman
| |