Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1197909 > unrolled thread

[PATCH v4 2/7] locking/pvqspinlock: Add pending bit support

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH v4 2/7] locking/pvqspinlock: Add pending bit support Waiman Long <Waiman.Long@hp.com> - 2015-08-01 04:30 +0200
    Re: [PATCH v4 2/7] locking/pvqspinlock: Add pending bit support Davidlohr Bueso <dave@stgolabs.net> - 2015-08-03 20:40 +0200
      Re: [PATCH v4 2/7] locking/pvqspinlock: Add pending bit support Waiman Long <waiman.long@hp.com> - 2015-08-03 23:40 +0200

#1197909 — [PATCH v4 2/7] locking/pvqspinlock: Add pending bit support

Like the native qspinlock, using the pending bit when it is lightly
loaded to acquire the lock is faster than going through the PV queuing
process which is even slower than the native queuing process. It also
avoids loading two additional cachelines (the MCS and PV nodes).

This patch adds the pending bit support for PV qspinlock. The pending
bit code has a smaller spin threshold (1<<10). It will default back
to the queuing method if it cannot acquired the lock within a certain
time limit.

On a VM with 32 vCPUs on a 32-core Westmere-EX box, the kernel
build times on 4.2-rc1 based kernels were:

  Kernel	Build Time	Sys Time
  ------	----------	--------
  w/o patch	  3m28.5s	28m17.5s
  with patch	  3m19.3s	23m55.7s

Using a locking microbenchmark on the same system, the locking
rates in (kops/s) were:

  Threads		Rate w/o patch	Rate with patch
  -------		--------------	---------------
  2 (same socket)	  6,515,265	  7,077,476
  2 (diff sockets)	  2,967,145	  4,353,851

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
---
 kernel/locking/qspinlock.c          |   27 +++++++++++++-
 kernel/locking/qspinlock_paravirt.h |   67 +++++++++++++++++++++++++++++++++++
 2 files changed, 93 insertions(+), 1 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index 38c4920..6518ee9 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -162,6 +162,17 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
 	WRITE_ONCE(l->locked_pending, _Q_LOCKED_VAL);
 }
 
+/**
+ * clear_pending - clear the pending bit.
+ * @lock: Pointer to queued spinlock structure
+ */
+static __always_inline void clear_pending(struct qspinlock *lock)
+{
+	struct __qspinlock *l = (void *)lock;
+
+	WRITE_ONCE(l->pending, 0);
+}
+
 /*
  * xchg_tail - Put in the new queue tail code word & retrieve previous one
  * @lock : Pointer to queued spinlock structure
@@ -193,6 +204,15 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
 }
 
 /**
+ * clear_pending - clear the pending bit.
+ * @lock: Pointer to queued spinlock structure
+ */
+static __always_inline void clear_pending(struct qspinlock *lock)
+{
+	atomic_add(-_Q_PENDING_VAL, &lock->val);
+}
+
+/**
  * xchg_tail - Put in the new queue tail code word & retrieve previous one
  * @lock : Pointer to queued spinlock structure
  * @tail : The new queue tail code word
@@ -245,6 +265,7 @@ static __always_inline void __pv_wait_head(struct qspinlock *lock,
 					   struct mcs_spinlock *node) { }
 
 #define pv_enabled()		false
+#define pv_pending_lock(l, v)	false
 
 #define pv_init_node		__pv_init_node
 #define pv_wait_node		__pv_wait_node
@@ -286,8 +307,11 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 
 	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
 
-	if (pv_enabled())
+	if (pv_enabled()) {
+		if (pv_pending_lock(lock, val))
+			return;	/* Got the lock via pending bit */
 		goto queue;
+	}
 
 	if (virt_queued_spin_lock(lock))
 		return;
@@ -463,6 +487,7 @@ EXPORT_SYMBOL(queued_spin_lock_slowpath);
 #undef pv_wait_node
 #undef pv_kick_node
 #undef pv_wait_head
+#undef pv_pending_lock
 
 #undef  queued_spin_lock_slowpath
 #define queued_spin_lock_slowpath	__pv_queued_spin_lock_slowpath
diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index 2dd4b39..5325877 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -22,6 +22,14 @@
 
 #define _Q_SLOW_VAL	(3U << _Q_LOCKED_OFFSET)
 
+/*
+ * Queued Spinlock Spin Threshold
+ *
+ * The vCPU will spin a relatively short time in pending mode before falling
+ * back to queuing.
+ */
+#define PENDING_SPIN_THRESHOLD	(SPIN_THRESHOLD >> 5)
+
 enum vcpu_state {
 	vcpu_running = 0,
 	vcpu_halted,
@@ -152,6 +160,65 @@ static void pv_init_node(struct mcs_spinlock *node)
 }
 
 /*
+ * Try to acquire the lock and wait using the pending bit
+ */
+static int pv_pending_lock(struct qspinlock *lock, u32 val)
+{
+	int loop = PENDING_SPIN_THRESHOLD;
+	u32 new, old;
+
+	/*
+	 * wait for in-progress pending->locked hand-overs
+	 */
+	while ((val == _Q_PENDING_VAL) && loop) {
+		cpu_relax();
+		val = atomic_read(&lock->val);
+		loop--;
+	}
+
+	/*
+	 * trylock || pending
+	 */
+	for (;; loop--) {
+		if (val & ~_Q_LOCKED_MASK)
+			goto queue;
+		new = _Q_LOCKED_VAL;
+		if (val == new)
+			new |= _Q_PENDING_VAL;
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+		if (!loop)
+			goto queue;
+	}
+
+	if (new == _Q_LOCKED_VAL)
+		goto gotlock;
+	/*
+	 * We are pending, wait for the owner to go away.
+	 */
+	for (; loop; loop--, cpu_relax()) {
+		val = smp_load_acquire(&lock->val.counter);
+		if (!(val & _Q_LOCKED_MASK)) {
+			clear_pending_set_locked(lock);
+			goto gotlock;
+		}
+	}
+
+	/*
+	 * Fail to acquire the lock within the spinning period,
+	 * so clear the pending bit and fall back to queuing.
+	 */
+	clear_pending(lock);
+
+queue:
+	return 0;
+
+gotlock:
+	return 1;
+}
+
+/*
  * Wait for node->locked to become true, halt the vcpu after a short spin.
  * pv_kick_node() is used to wake the vcpu again.
  */
-- 
1.7.1

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1199168

On Fri, 2015-07-31 at 22:21 -0400, Waiman Long wrote:
>  /*
> + * Try to acquire the lock and wait using the pending bit
> + */
> +static int pv_pending_lock(struct qspinlock *lock, u32 val)

Sorry but, why did yo not rewrite the function as we had previously
discussed. This is very confusing to read, the one I suggested follows a
much nicer flow and purposely illustrates the intention. You also failed
to address my loop semantics concerns altogether.

Thanks,
Davidlohr

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1199286

On 08/03/2015 02:37 PM, Davidlohr Bueso wrote:
> On Fri, 2015-07-31 at 22:21 -0400, Waiman Long wrote:
>>   /*
>> + * Try to acquire the lock and wait using the pending bit
>> + */
>> +static int pv_pending_lock(struct qspinlock *lock, u32 val)
> Sorry but, why did yo not rewrite the function as we had previously
> discussed. This is very confusing to read, the one I suggested follows a
> much nicer flow and purposely illustrates the intention. You also failed
> to address my loop semantics concerns altogether.
>
> Thanks,
> Davidlohr
>

I am sorry that I might have misinterpret what you wanted. Right now, 
the latest code have 3 loops in the pending function:
1. Waiting for pending locker to become lock holder
2. A loop to do the trylock or set the pending bit.
3. With the pending bit set, another loop to wait until the lock holder 
frees the lock.

The 2nd loop may be a bit confusing to look at. I will try to add more 
comment to clarify that. The second loop can return without calling 
clear_pending() because the pending bit will not be set until it breaks 
out of the loop.

I think it will make the code more complicated if we try to merge the 
2nd and 3rd loops.

Please let me know what kind of rewriting you have in mind.

Thanks,
Longman




--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web