From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751317AbcGPBRE (ORCPT ); Fri, 15 Jul 2016 21:17:04 -0400 Received: from mail-qk0-f182.google.com ([209.85.220.182]:36212 "EHLO mail-qk0-f182.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751054AbcGPBRA (ORCPT ); Fri, 15 Jul 2016 21:17:00 -0400 Date: Sat, 16 Jul 2016 09:16:57 +0800 From: Boqun Feng To: Peter Zijlstra Cc: Pan Xinhui , Waiman Long , Ingo Molnar , linux-kernel@vger.kernel.org, Scott J Norton , Douglas Hatch Subject: Re: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem Message-ID: <20160716011657.GA29702@tardis.cn.ibm.com> References: <1464713631-1066-1-git-send-email-Waiman.Long@hpe.com> <1464713631-1066-3-git-send-email-Waiman.Long@hpe.com> <20160715084732.GF30921@twins.programming.kicks-ass.net> <3c5d5c29-7956-572f-2638-b85299c72432@linux.vnet.ibm.com> <20160715100703.GQ30154@twins.programming.kicks-ass.net> <20160715163556.GA7141@twins.programming.kicks-ass.net> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="Kj7319i9nmIyA2yE" Content-Disposition: inline In-Reply-To: <20160715163556.GA7141@twins.programming.kicks-ass.net> User-Agent: Mutt/1.6.2 (2016-07-01) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org --Kj7319i9nmIyA2yE Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, Jul 15, 2016 at 06:35:56PM +0200, Peter Zijlstra wrote: > On Fri, Jul 15, 2016 at 12:07:03PM +0200, Peter Zijlstra wrote: > > > So if we are kicked by the unlock_slowpath, and the lock is stealed by > > > someone else, we need hash its node again and set l->locked to > > > _Q_SLOW_VAL, then enter pv_wait. > >=20 > > Right, let me go think about this a bit. >=20 > Urgh, brain hurt. >=20 > So I _think_ the below does for it but I could easily have missed yet > another case. >=20 > Waiman's patch has the problem that it can have two pv_hash() calls for > the same lock in progress and I'm thinking that means we can hit the > BUG() in pv_hash() due to that. >=20 I think Waiman's patch does have the problem of two pv_hash() calls for the same lock in progress. As I mentioned in the first version: http://lkml.kernel.org/g/20160527074331.GB8096@insomnia And he tried to address this in the patch #3 of this series. However, I think what is proper here is either to reorder patch 2 and 3 or to merge patch 2 and 3, otherwise, we are introducing a bug in the middle of this series. Thoughts, Waiman? That said, I found Peter's way is much simpler and easier to understand ;-) > If we can't, it still has a problem because its not telling us either. >=20 >=20 >=20 > --- a/kernel/locking/qspinlock_paravirt.h > +++ b/kernel/locking/qspinlock_paravirt.h > @@ -20,7 +20,8 @@ > * native_queued_spin_unlock(). > */ > =20 > -#define _Q_SLOW_VAL (3U << _Q_LOCKED_OFFSET) > +#define _Q_HASH_VAL (3U << _Q_LOCKED_OFFSET) > +#define _Q_SLOW_VAL (7U << _Q_LOCKED_OFFSET) > =20 > /* > * Queue Node Adaptive Spinning > @@ -36,14 +37,11 @@ > */ > #define PV_PREV_CHECK_MASK 0xff > =20 > -/* > - * Queue node uses: vcpu_running & vcpu_halted. > - * Queue head uses: vcpu_running & vcpu_hashed. > - */ > enum vcpu_state { > - vcpu_running =3D 0, > - vcpu_halted, /* Used only in pv_wait_node */ > - vcpu_hashed, /* =3D pv_hash'ed + vcpu_halted */ > + vcpu_node_running =3D 0, > + vcpu_node_halted, > + vcpu_head_running, We actually don't need this extra running state, right? Because nobody cares about the difference between two running states right now. > + vcpu_head_halted, > }; > =20 > struct pv_node { > @@ -263,7 +261,7 @@ pv_wait_early(struct pv_node *prev, int > if ((loop & PV_PREV_CHECK_MASK) !=3D 0) > return false; > =20 > - return READ_ONCE(prev->state) !=3D vcpu_running; > + return READ_ONCE(prev->state) & 1; > } > =20 > /* > @@ -311,20 +309,19 @@ static void pv_wait_node(struct mcs_spin > * > * Matches the cmpxchg() from pv_kick_node(). > */ > - smp_store_mb(pn->state, vcpu_halted); > + smp_store_mb(pn->state, vcpu_node_halted); > =20 > - if (!READ_ONCE(node->locked)) { > - qstat_inc(qstat_pv_wait_node, true); > - qstat_inc(qstat_pv_wait_early, wait_early); > - pv_wait(&pn->state, vcpu_halted); > - } > + if (READ_ONCE(node->locked)) > + return; > + > + qstat_inc(qstat_pv_wait_node, true); > + qstat_inc(qstat_pv_wait_early, wait_early); > + pv_wait(&pn->state, vcpu_node_halted); > =20 > /* > - * If pv_kick_node() changed us to vcpu_hashed, retain that > - * value so that pv_wait_head_or_lock() knows to not also try > - * to hash this lock. > + * If pv_kick_node() advanced us, retain that state. > */ > - cmpxchg(&pn->state, vcpu_halted, vcpu_running); > + cmpxchg(&pn->state, vcpu_node_halted, vcpu_node_running); > =20 > /* > * If the locked flag is still not set after wakeup, it is a > @@ -362,18 +359,17 @@ static void pv_kick_node(struct qspinloc > * > * Matches with smp_store_mb() and cmpxchg() in pv_wait_node() > */ > - if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) !=3D vcpu_halted) > + if (cmpxchg(&pn->state, vcpu_node_halted, vcpu_head_running) !=3D vcpu_= node_halted) > return; > =20 > /* > - * Put the lock into the hash table and set the _Q_SLOW_VAL. > - * > - * As this is the same vCPU that will check the _Q_SLOW_VAL value and > - * the hash table later on at unlock time, no atomic instruction is > - * needed. > + * See pv_wait_head_or_lock(). We have to hash and force the unlock > + * into the slow path to deliver the actual kick for waking. > */ > - WRITE_ONCE(l->locked, _Q_SLOW_VAL); > - (void)pv_hash(lock, pn); > + if (cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_HASH_VAL) =3D=3D _Q_LOCKED_VA= L) { > + (void)pv_hash(lock, pn); > + smp_store_release(&l->locked, _Q_SLOW_VAL); > + } > } > =20 > /* > @@ -388,28 +384,22 @@ pv_wait_head_or_lock(struct qspinlock *l > { > struct pv_node *pn =3D (struct pv_node *)node; > struct __qspinlock *l =3D (void *)lock; > - struct qspinlock **lp =3D NULL; > int waitcnt =3D 0; > int loop; > =20 > /* > - * If pv_kick_node() already advanced our state, we don't need to > - * insert ourselves into the hash table anymore. > - */ > - if (READ_ONCE(pn->state) =3D=3D vcpu_hashed) > - lp =3D (struct qspinlock **)1; > - > - /* > * Tracking # of slowpath locking operations > */ > qstat_inc(qstat_pv_lock_slowpath, true); > =20 > for (;; waitcnt++) { > + u8 locked; > + > /* > * Set correct vCPU state to be used by queue node wait-early > * mechanism. > */ > - WRITE_ONCE(pn->state, vcpu_running); > + WRITE_ONCE(pn->state, vcpu_head_running); > =20 > /* > * Set the pending bit in the active lock spinning loop to > @@ -423,33 +413,38 @@ pv_wait_head_or_lock(struct qspinlock *l > } > clear_pending(lock); > =20 > + /* > + * We want to go sleep; ensure we're hashed so that > + * __pv_queued_spin_unlock_slow() can find us for a wakeup. > + */ > + locked =3D cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_HASH_VAL); > + switch (locked) { > + /* > + * We're not hashed yet, either we're fresh from pv_wait_node() > + * or __pv_queued_spin_unlock_slow() unhashed us but we lost > + * the trylock to a steal and have to re-hash. > + */ > + case _Q_LOCKED_VAL: > + (void)pv_hash(lock, pn); > + smp_store_release(&l->locked, _Q_SLOW_VAL); > + break; > =20 > - if (!lp) { /* ONCE */ > - lp =3D pv_hash(lock, pn); > + /* > + * pv_kick_node() is hashing us, wait for it. > + */ > + case _Q_HASH_VAL: > + while (READ_ONCE(l->locked) =3D=3D _Q_HASH_VAL) > + cpu_relax(); > + break; > =20 > - /* > - * We must hash before setting _Q_SLOW_VAL, such that > - * when we observe _Q_SLOW_VAL in __pv_queued_spin_unlock() > - * we'll be sure to be able to observe our hash entry. > - * > - * [S] [Rmw] l->locked =3D=3D _Q_SLOW_VAL > - * MB RMB > - * [RmW] l->locked =3D _Q_SLOW_VAL [L] > - * > - * Matches the smp_rmb() in __pv_queued_spin_unlock(). > - */ > - if (xchg(&l->locked, _Q_SLOW_VAL) =3D=3D 0) { > - /* > - * The lock was free and now we own the lock. > - * Change the lock value back to _Q_LOCKED_VAL > - * and unhash the table. > - */ > - WRITE_ONCE(l->locked, _Q_LOCKED_VAL); > - WRITE_ONCE(*lp, NULL); > - goto gotlock; > - } > + /* > + * Ooh, unlocked, try and grab it. > + */ > + case 0: > + continue; > } > - WRITE_ONCE(pn->state, vcpu_hashed); > + > + WRITE_ONCE(pn->state, vcpu_head_halted); > qstat_inc(qstat_pv_wait_head, true); > qstat_inc(qstat_pv_wait_again, waitcnt); > pv_wait(&l->locked, _Q_SLOW_VAL); > @@ -480,7 +475,7 @@ __pv_queued_spin_unlock_slowpath(struct > struct __qspinlock *l =3D (void *)lock; > struct pv_node *node; > =20 > - if (unlikely(locked !=3D _Q_SLOW_VAL)) { > + if (unlikely(locked !=3D _Q_SLOW_VAL && locked !=3D _Q_HASH_VAL)) { > WARN(!debug_locks_silent, > "pvqspinlock: lock 0x%lx has corrupted value 0x%x!\n", > (unsigned long)lock, atomic_read(&lock->val)); > @@ -488,18 +483,17 @@ __pv_queued_spin_unlock_slowpath(struct > } > =20 > /* > - * A failed cmpxchg doesn't provide any memory-ordering guarantees, > - * so we need a barrier to order the read of the node data in > - * pv_unhash *after* we've read the lock being _Q_SLOW_VAL. > - * > - * Matches the cmpxchg() in pv_wait_head_or_lock() setting _Q_SLOW_VAL. > + * Wait until the hash-bucket is complete. > */ > - smp_rmb(); > + while (READ_ONCE(l->locked) =3D=3D _Q_HASH_VAL) > + cpu_relax(); > =20 This does give a chance to let the lock waiter block the lock holder, right? Considering a lock queue head's vcpu is preempted before it could set the lock to _Q_SLOW_VAL. Could we do something like this here: if (unlikely(cmpxchg(l->locked, _Q_HASH_VAL, 0) =3D=3D _Q_HASH_VAL)) return; =09 And in pv_wait_head_or_lock() locked =3D cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_HASH_VAL); switch(locked) { case _Q_LOCKED_VAL: (void)pv_hash(lock, pn); locked =3D cmpxchg_release(&l->locked, _Q_HASH_VAL, _Q_SLOW_VAL); /* * Only the holder will change the ->locked from * _Q_HASH_VAL to another value, if this * happens, the holder has already released the * lock without trying to wake the head, in this * case, we need to unhash ourselves and there * is a great chance we can get the locke. */ if (unlikely(locked !=3D _Q_HASH_VAL)) { pv_unhash(lock, pn); if (!cmpxchg_relaxed(&l->locked, 0, _Q_LOCKED_VAL) goto gotlock; } break; Wrote those in my mailbox, may miss something. Thoughts? Regards, Boqun > /* > - * Since the above failed to release, this must be the SLOW path. > - * Therefore start by looking up the blocked node and unhashing it. > + * Must first observe _Q_SLOW_VAL in order to observe > + * consistent hash bucket. > */ > + smp_rmb(); > + > node =3D pv_unhash(lock); > =20 > /* --Kj7319i9nmIyA2yE Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQEcBAABCAAGBQJXiYsDAAoJEEl56MO1B/q45kgIAKo7cvP9bIHRzQyN921gIWlF 4R7cQmK2znBH3XRY+WJefnNAdFcT7Yh0GFJqMNZVDxVsqdXII+azIBjmjTZR8UX+ QjMBJ6nGbo98x5H17ODy1TbiHXF/6PKdoZdjJknc1eVs55EfcKvkBjObYMyC7Hvi rm4UAXZWelU81R6JG1t+7WyyU1rcWjZyu9TSTX4pblnFX8rY4KbgRWHvThOEmg+U s/pWBpuwyi5wIvzMV4sSzfUUn0n0bcpeKY9Qw98HnJSVcsiRujXW3A1ilzsAlAgw YMgucE3zNMxYtYm9l7DQ9nhDROmy1jh/J8Dvm/yJQqHJYLTfRdWyJK9b59xFqL0= =L8od -----END PGP SIGNATURE----- --Kj7319i9nmIyA2yE--