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

Groups > linux.kernel > #1184197 > unrolled thread

[PATCH v2 4/6] locking/pvqspinlock: Allow vCPUs kick-ahead

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 v2 4/6] locking/pvqspinlock: Allow vCPUs kick-ahead Waiman Long <Waiman.Long@hp.com> - 2015-07-15 04:20 +0200
    Re: [PATCH v2 4/6] locking/pvqspinlock: Allow vCPUs kick-ahead Peter Zijlstra <peterz@infradead.org> - 2015-07-15 11:40 +0200
      Re: [PATCH v2 4/6] locking/pvqspinlock: Allow vCPUs kick-ahead Waiman Long <waiman.long@hp.com> - 2015-07-16 04:10 +0200
        Re: [PATCH v2 4/6] locking/pvqspinlock: Allow vCPUs kick-ahead Waiman Long <waiman.long@hp.com> - 2015-07-16 17:00 +0200

#1184197 — [PATCH v2 4/6] locking/pvqspinlock: Allow vCPUs kick-ahead

Frequent CPU halting (vmexit) and CPU kicking (vmenter) lengthens
critical section and block forward progress.  This patch implements
a kick-ahead mechanism where the unlocker will kick the queue head
vCPUs as well as up to four additional vCPUs next to the queue head
if they were halted.  The kickings are done after exiting the critical
section to improve parallelism.

The amount of kick-ahead allowed depends on the number of vCPUs
in the VM guest.  This patch, by itself, won't do much as most of
the kickings are currently done at lock time. Coupled with the next
patch that defers lock time kicking to unlock time, it should improve
overall system performance in a busy overcommitted guest.

Linux kernel builds were run in KVM guest on an 8-socket, 4
cores/socket Westmere-EX system and a 4-socket, 8 cores/socket
Haswell-EX system. Both systems are configured to have 32 physical
CPUs. The kernel build times before and after the patch were:

		    Westmere			Haswell
  Patch		32 vCPUs    48 vCPUs	32 vCPUs    48 vCPUs
  -----		--------    --------    --------    --------
  Before patch	 3m25.0s    10m34.1s	 2m02.0s    15m35.9s
  After patch    3m27.4s    10m32.0s	 2m00.8s    14m52.5s

There wasn't too much difference before and after the patch.

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
---
 kernel/locking/qspinlock_paravirt.h |   77 +++++++++++++++++++++++++++++++++-
 1 files changed, 74 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index c8485c4..f3ceeff 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -51,6 +51,7 @@ enum pv_qlock_stat {
 	pvstat_kick_time,
 	pvstat_lock_kick,
 	pvstat_unlock_kick,
+	pvstat_kick_ahead,
 	pvstat_pend_lock,
 	pvstat_pend_fail,
 	pvstat_spurious,
@@ -72,6 +73,7 @@ static const char * const stat_fsnames[pvstat_num] = {
 	[pvstat_kick_time]   = "kick_time_count",
 	[pvstat_lock_kick]   = "lock_kick_count",
 	[pvstat_unlock_kick] = "unlock_kick_count",
+	[pvstat_kick_ahead]  = "kick_ahead_count",
 	[pvstat_pend_lock]   = "pending_lock_count",
 	[pvstat_pend_fail]   = "pending_fail_count",
 	[pvstat_spurious]    = "spurious_wakeup",
@@ -85,7 +87,8 @@ static atomic_t pvstats[pvstat_num];
  * pv_kick_latencies = sum of all pv_kick latencies in ns
  * pv_wake_latencies = sum of all wakeup latencies in ns
  *
- * Avg kick latency = pv_kick_latencies/(lock_kick_count + unlock_kick_count)
+ * Avg kick latency = pv_kick_latencies/
+ *		     (lock_kick_count + unlock_kick_count + kick_ahead_count)
  * Avg wake latency = pv_wake_latencies/kick_time_count
  */
 static atomic64_t pv_kick_latencies, pv_wake_latencies;
@@ -217,6 +220,12 @@ static struct pv_hash_entry *pv_lock_hash;
 static unsigned int pv_lock_hash_bits __read_mostly;
 
 /*
+ * Allow kick-ahead of vCPUs at unlock time
+ */
+#define PV_KICK_AHEAD_MAX	4
+static int pv_kick_ahead __read_mostly;
+
+/*
  * Allocate memory for the PV qspinlock hash buckets
  *
  * This function should be called from the paravirt spinlock initialization
@@ -224,7 +233,16 @@ static unsigned int pv_lock_hash_bits __read_mostly;
  */
 void __init __pv_init_lock_hash(void)
 {
-	int pv_hash_size = ALIGN(4 * num_possible_cpus(), PV_HE_PER_LINE);
+	int ncpus = num_possible_cpus();
+	int pv_hash_size = ALIGN(4 * ncpus, PV_HE_PER_LINE);
+	int i;
+
+	/*
+	 * The minimum number of vCPUs required in each kick-ahead level
+	 */
+	static const u8 kick_ahead_threshold[PV_KICK_AHEAD_MAX] = {
+		4, 8, 16, 32
+	};
 
 	if (pv_hash_size < PV_HE_MIN)
 		pv_hash_size = PV_HE_MIN;
@@ -238,6 +256,18 @@ void __init __pv_init_lock_hash(void)
 					       pv_hash_size, 0, HASH_EARLY,
 					       &pv_lock_hash_bits, NULL,
 					       pv_hash_size, pv_hash_size);
+	/*
+	 * Enable the unlock kick ahead mode according to the number of
+	 * vCPUs available.
+	 */
+	for (i = PV_KICK_AHEAD_MAX; i > 0; i--)
+		if (ncpus >= kick_ahead_threshold[i - 1]) {
+			pv_kick_ahead = i;
+			break;
+		}
+	if (pv_kick_ahead)
+		pr_info("PV unlock kick ahead level %d enabled\n",
+			pv_kick_ahead);
 }
 
 #define for_each_hash_entry(he, offset, hash)						\
@@ -424,6 +454,25 @@ static void pv_wait_node(struct mcs_spinlock *node)
 }
 
 /*
+ * Helper to get the address of the next kickable node
+ * The node has to be in the halted state and is being transitioned to
+ * running state by this function. Otherwise, NULL will be returned.
+ */
+static inline struct pv_node *pv_get_kick_node(struct pv_node *node)
+{
+	struct pv_node *next = (struct pv_node *)READ_ONCE(node->mcs.next);
+
+	if (!next)
+		return NULL;
+
+	if ((READ_ONCE(next->state) != vcpu_halted) ||
+	    (xchg(&next->state, vcpu_running) != vcpu_halted))
+		next = NULL;	/* No kicking is needed */
+
+	return next;
+}
+
+/*
  * Called after setting next->locked = 1, used to wake those stuck in
  * pv_wait_node().
  */
@@ -510,7 +559,8 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 {
 	struct __qspinlock *l = (void *)lock;
-	struct pv_node *node;
+	struct pv_node *node, *nxt, *next[PV_KICK_AHEAD_MAX];
+	int i, nr_kick;
 
 	/*
 	 * We must not unlock if SLOW, because in that case we must first
@@ -527,6 +577,19 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 	node = pv_unhash(lock);
 
 	/*
+	 * Implement unlock kick-ahead
+	 *
+	 * Access the next group of nodes, if available, and prepare to kick
+	 * them after releasing the lock if they are in the halted state. This
+	 * should improve performance on an overcommitted system.
+	 */
+	for (nr_kick = 0, nxt = node; nr_kick < pv_kick_ahead; nr_kick++) {
+		nxt = next[nr_kick] = pv_get_kick_node(nxt);
+		if (!nxt)
+			break;
+	}
+
+	/*
 	 * Now that we have a reference to the (likely) blocked pv_node,
 	 * release the lock.
 	 */
@@ -538,6 +601,14 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 	 */
 	pvstat_inc(pvstat_unlock_kick);
 	pv_kick(node->cpu);
+
+	/*
+	 * Kick the next group of vCPUs, if available.
+	 */
+	for (i = 0; i < nr_kick; i++) {
+		pvstat_inc(pvstat_kick_ahead);
+		pv_kick(next[i]->cpu);
+	}
 }
 /*
  * Include the architecture specific callee-save thunk of the
-- 
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]

#1184529

On Tue, Jul 14, 2015 at 10:13:35PM -0400, Waiman Long wrote:
> Frequent CPU halting (vmexit) and CPU kicking (vmenter) lengthens
> critical section and block forward progress.  This patch implements
> a kick-ahead mechanism where the unlocker will kick the queue head
> vCPUs as well as up to four additional vCPUs next to the queue head
> if they were halted.  The kickings are done after exiting the critical
> section to improve parallelism.
> 
> The amount of kick-ahead allowed depends on the number of vCPUs
> in the VM guest.  This patch, by itself, won't do much as most of
> the kickings are currently done at lock time. Coupled with the next
> patch that defers lock time kicking to unlock time, it should improve
> overall system performance in a busy overcommitted guest.
> 
> Linux kernel builds were run in KVM guest on an 8-socket, 4
> cores/socket Westmere-EX system and a 4-socket, 8 cores/socket
> Haswell-EX system. Both systems are configured to have 32 physical
> CPUs. The kernel build times before and after the patch were:
> 
> 		    Westmere			Haswell
>   Patch		32 vCPUs    48 vCPUs	32 vCPUs    48 vCPUs
>   -----		--------    --------    --------    --------
>   Before patch	 3m25.0s    10m34.1s	 2m02.0s    15m35.9s
>   After patch    3m27.4s    10m32.0s	 2m00.8s    14m52.5s
> 
> There wasn't too much difference before and after the patch.

That means either the patch isn't worth it, or as you seem to imply its
in the wrong place in this series.

> @@ -224,7 +233,16 @@ static unsigned int pv_lock_hash_bits __read_mostly;
>   */
>  void __init __pv_init_lock_hash(void)
>  {
> -	int pv_hash_size = ALIGN(4 * num_possible_cpus(), PV_HE_PER_LINE);
> +	int ncpus = num_possible_cpus();
> +	int pv_hash_size = ALIGN(4 * ncpus, PV_HE_PER_LINE);
> +	int i;
> +
> +	/*
> +	 * The minimum number of vCPUs required in each kick-ahead level
> +	 */
> +	static const u8 kick_ahead_threshold[PV_KICK_AHEAD_MAX] = {
> +		4, 8, 16, 32
> +	};

You are aware we have ilog2(), right?

> +	/*
> +	 * Enable the unlock kick ahead mode according to the number of
> +	 * vCPUs available.
> +	 */
> +	for (i = PV_KICK_AHEAD_MAX; i > 0; i--)
> +		if (ncpus >= kick_ahead_threshold[i - 1]) {
> +			pv_kick_ahead = i;
> +			break;
> +		}

That's missing { }.

> +	if (pv_kick_ahead)
> +		pr_info("PV unlock kick ahead level %d enabled\n",
> +			pv_kick_ahead);

Idem.

That said, I still really dislike this patch, it again seems a random
bunch of hacks.

You also do not offer any support for any of the magic numbers..
--
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]

#1185376

On 07/15/2015 05:39 AM, Peter Zijlstra wrote:
> On Tue, Jul 14, 2015 at 10:13:35PM -0400, Waiman Long wrote:
>> Frequent CPU halting (vmexit) and CPU kicking (vmenter) lengthens
>> critical section and block forward progress.  This patch implements
>> a kick-ahead mechanism where the unlocker will kick the queue head
>> vCPUs as well as up to four additional vCPUs next to the queue head
>> if they were halted.  The kickings are done after exiting the critical
>> section to improve parallelism.
>>
>> The amount of kick-ahead allowed depends on the number of vCPUs
>> in the VM guest.  This patch, by itself, won't do much as most of
>> the kickings are currently done at lock time. Coupled with the next
>> patch that defers lock time kicking to unlock time, it should improve
>> overall system performance in a busy overcommitted guest.
>>
>> Linux kernel builds were run in KVM guest on an 8-socket, 4
>> cores/socket Westmere-EX system and a 4-socket, 8 cores/socket
>> Haswell-EX system. Both systems are configured to have 32 physical
>> CPUs. The kernel build times before and after the patch were:
>>
>> 		    Westmere			Haswell
>>    Patch		32 vCPUs    48 vCPUs	32 vCPUs    48 vCPUs
>>    -----		--------    --------    --------    --------
>>    Before patch	 3m25.0s    10m34.1s	 2m02.0s    15m35.9s
>>    After patch    3m27.4s    10m32.0s	 2m00.8s    14m52.5s
>>
>> There wasn't too much difference before and after the patch.
> That means either the patch isn't worth it, or as you seem to imply its
> in the wrong place in this series.

It needs to be coupled with the next patch to be effective as most of 
the kicking are happening at the lock side, instead of at the unlock 
side. If you look at the sample pvqspinlock stats in patch 3:

lock_kick_count=755354
unlock_kick_count=87

The number of unlock kicks is negligible compared with the lock kicks. 
Patch 5 does have a dependency on patch 4 unless we make it 
unconditionally defers kicking to the unlock call which was what I had 
done in the v1 patch. The reason why I change this in v2 is because I 
found a very slight performance degradation in doing so.

>> @@ -224,7 +233,16 @@ static unsigned int pv_lock_hash_bits __read_mostly;
>>    */
>>   void __init __pv_init_lock_hash(void)
>>   {
>> -	int pv_hash_size = ALIGN(4 * num_possible_cpus(), PV_HE_PER_LINE);
>> +	int ncpus = num_possible_cpus();
>> +	int pv_hash_size = ALIGN(4 * ncpus, PV_HE_PER_LINE);
>> +	int i;
>> +
>> +	/*
>> +	 * The minimum number of vCPUs required in each kick-ahead level
>> +	 */
>> +	static const u8 kick_ahead_threshold[PV_KICK_AHEAD_MAX] = {
>> +		4, 8, 16, 32
>> +	};
> You are aware we have ilog2(), right?

Right, I am not aware of ilog2(). I am going to use that instead.

>> +	/*
>> +	 * Enable the unlock kick ahead mode according to the number of
>> +	 * vCPUs available.
>> +	 */
>> +	for (i = PV_KICK_AHEAD_MAX; i>  0; i--)
>> +		if (ncpus>= kick_ahead_threshold[i - 1]) {
>> +			pv_kick_ahead = i;
>> +			break;
>> +		}
> That's missing { }.
>
>> +	if (pv_kick_ahead)
>> +		pr_info("PV unlock kick ahead level %d enabled\n",
>> +			pv_kick_ahead);
> Idem.

Will fix the {} problems.

> That said, I still really dislike this patch, it again seems a random
> bunch of hacks.

Any suggestions to make it better suit your taste?

> You also do not offer any support for any of the magic numbers..

I chose 4 for PV_KICK_AHEAD_MAX as I didn't see much performance 
difference when I did a kick-ahead of 5. Also, it may be too unfair to 
the vCPU that was doing the kicking if the number is too big. Another 
magic number is  pv_kick_ahead number. This one is kind of arbitrary. 
Right now I do a log2, but it can be divided by 4 (rshift 2) as well.

Cheers,
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] | [next] | [standalone]

#1185937

On 07/16/2015 01:46 AM, Peter Zijlstra wrote:
> On Wed, Jul 15, 2015 at 10:01:02PM -0400, Waiman Long wrote:
>> On 07/15/2015 05:39 AM, Peter Zijlstra wrote:
>>> On Tue, Jul 14, 2015 at 10:13:35PM -0400, Waiman Long wrote:
>>>> Frequent CPU halting (vmexit) and CPU kicking (vmenter) lengthens
>>>> critical section and block forward progress.  This patch implements
>>>> a kick-ahead mechanism where the unlocker will kick the queue head
>>>> vCPUs as well as up to four additional vCPUs next to the queue head
>>>> if they were halted.  The kickings are done after exiting the critical
>>>> section to improve parallelism.
>>>>
>>>> The amount of kick-ahead allowed depends on the number of vCPUs
>>>> in the VM guest.  This patch, by itself, won't do much as most of
>>>> the kickings are currently done at lock time. Coupled with the next
>>>> patch that defers lock time kicking to unlock time, it should improve
>>>> overall system performance in a busy overcommitted guest.
>>>>
>>>> Linux kernel builds were run in KVM guest on an 8-socket, 4
>>>> cores/socket Westmere-EX system and a 4-socket, 8 cores/socket
>>>> Haswell-EX system. Both systems are configured to have 32 physical
>>>> CPUs. The kernel build times before and after the patch were:
>>>>
>>>> 		    Westmere			Haswell
>>>>    Patch		32 vCPUs    48 vCPUs	32 vCPUs    48 vCPUs
>>>>    -----		--------    --------    --------    --------
>>>>    Before patch	 3m25.0s    10m34.1s	 2m02.0s    15m35.9s
>>>>    After patch    3m27.4s    10m32.0s	 2m00.8s    14m52.5s
>>>>
>>>> There wasn't too much difference before and after the patch.
>>> That means either the patch isn't worth it, or as you seem to imply its
>>> in the wrong place in this series.
>> It needs to be coupled with the next patch to be effective as most of the
>> kicking are happening at the lock side, instead of at the unlock side. If
>> you look at the sample pvqspinlock stats in patch 3:
>>
>> lock_kick_count=755354
>> unlock_kick_count=87
>>
>> The number of unlock kicks is negligible compared with the lock kicks. Patch
>> 5 does have a dependency on patch 4 unless we make it unconditionally defers
>> kicking to the unlock call which was what I had done in the v1 patch. The
>> reason why I change this in v2 is because I found a very slight performance
>> degradation in doing so.
> This way we cannot see the gains of the proposed complexity. So put it
> in a place where you can.

OK, I will see what I can do to make the performance change more visible 
on a patch-by-patch basis.

>>> You also do not offer any support for any of the magic numbers..
>> I chose 4 for PV_KICK_AHEAD_MAX as I didn't see much performance difference
>> when I did a kick-ahead of 5. Also, it may be too unfair to the vCPU that
>> was doing the kicking if the number is too big. Another magic number is
>> pv_kick_ahead number. This one is kind of arbitrary. Right now I do a log2,
>> but it can be divided by 4 (rshift 2) as well.
> So what was the difference between 1-2-3-4 ? I would be thinking one
> extra kick is the biggest help, no?
I was seeing diminishing returns with more kicks. I can add a table on 
that in the next patch.

Cheers,
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