[PATCH] alios: sched: Fix race between runtime distribution and assignment

[PATCH] alios: sched: Fix race between runtime distribution and assignment

[Huaixin Chang]

Currently, there is a potential race between distribute_cfs_runtime()
and assign_cfs_rq_runtime(). Race happens when cfs_b->runtime is read,
distributes without holding lock and finds out there is not enough
runtime to charge against after distribution. Because
assign_cfs_rq_runtime() might be called during distribution, and use
cfs_b->runtime at the same time.

Fibtest is the tool to test this race. Assume all gcfs_rq is throttled
and cfs period timer runs, slow threads might run and sleep, returning
unused cfs_rq runtime and keeping min_cfs_rq_runtime in their local
pool. If all this happens sufficiently quickly, cfs_b->runtime will drop
a lot. If runtime distributed is large too, over-use of runtime happens.

A runtime over-using by about 70 percent of quota is seen when we
test fibtest on a 96-core machine. We run fibtest with 1 fast thread and
95 slow threads in test group, configure 10ms quota for this group and
see the CPU usage of fibtest is 17.0%, which is far from than the
expected 10%.

On a smaller machine with 32 cores, we also run fibtest with 96
threads. CPU usage is more than 12%, which is also more than expected
10%. This shows that on similar workloads, this race do affect CPU
bandwidth control.

Solve this by holding lock inside distribute_cfs_runtime().

Fixes: c06f04c70489 ("sched: Fix potential near-infinite distribute_cfs_runtime() loop")
Signed-off-by: Huaixin Chang <changhuaixin@linux.alibaba.com>
---
 kernel/sched/fair.c | 31 ++++++++++++-------------------
 1 file changed, 12 insertions(+), 19 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c1217bfe5e81..c9f0e89fe5da 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4629,11 +4629,11 @@ void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
 		resched_curr(rq);
 }
 
-static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
+static void distribute_cfs_runtime(struct cfs_bandwidth *cfs_b)
 {
 	struct cfs_rq *cfs_rq;
-	u64 runtime;
-	u64 starting_runtime = remaining;
+	u64 runtime, remaining;
+	unsigned long flags;
 
 	rcu_read_lock();
 	list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
@@ -4648,10 +4648,13 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
 		/* By the above check, this should never be true */
 		SCHED_WARN_ON(cfs_rq->runtime_remaining > 0);
 
+		raw_spin_lock_irqsave(&cfs_b->lock, flags);
 		runtime = -cfs_rq->runtime_remaining + 1;
-		if (runtime > remaining)
-			runtime = remaining;
-		remaining -= runtime;
+		if (runtime > cfs_b->runtime)
+			runtime = cfs_b->runtime;
+		cfs_b->runtime -= runtime;
+		remaining = cfs_b->runtime;
+		raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
 
 		cfs_rq->runtime_remaining += runtime;
 
@@ -4666,8 +4669,6 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
 			break;
 	}
 	rcu_read_unlock();
-
-	return starting_runtime - remaining;
 }
 
 /*
@@ -4678,7 +4679,6 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
  */
 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun, unsigned long flags)
 {
-	u64 runtime;
 	int throttled;
 
 	/* no need to continue the timer with no bandwidth constraint */
@@ -4708,23 +4708,17 @@ static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun, u
 
 	/*
 	 * This check is repeated as we are holding onto the new bandwidth while
-	 * we unthrottle. This can potentially race with an unthrottled group
-	 * trying to acquire new bandwidth from the global pool. This can result
-	 * in us over-using our runtime if it is all used during this loop, but
-	 * only by limited amounts in that extreme case.
+	 * we unthrottle.
 	 */
 	while (throttled && cfs_b->runtime > 0 && !cfs_b->distribute_running) {
-		runtime = cfs_b->runtime;
 		cfs_b->distribute_running = 1;
 		raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
 		/* we can't nest cfs_b->lock while distributing bandwidth */
-		runtime = distribute_cfs_runtime(cfs_b, runtime);
+		distribute_cfs_runtime(cfs_b);
 		raw_spin_lock_irqsave(&cfs_b->lock, flags);
 
 		cfs_b->distribute_running = 0;
 		throttled = !list_empty(&cfs_b->throttled_cfs_rq);
-
-		lsub_positive(&cfs_b->runtime, runtime);
 	}
 
 	/*
@@ -4858,10 +4852,9 @@ static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
 	if (!runtime)
 		return;
 
-	runtime = distribute_cfs_runtime(cfs_b, runtime);
+	distribute_cfs_runtime(cfs_b);
 
 	raw_spin_lock_irqsave(&cfs_b->lock, flags);
-	lsub_positive(&cfs_b->runtime, runtime);
 	cfs_b->distribute_running = 0;
 	raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
 }
-- 
2.14.4.44.g2045bb6

Re: [PATCH] alios: sched: Fix race between runtime distribution and assignment

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 5953 bytes --]

Hi Huaixin,

Thank you for the patch! Perhaps something to improve:

[auto build test WARNING on tip/sched/core]
[also build test WARNING on tip/auto-latest linus/master linux/master v5.6-rc7 next-20200325]
[if your patch is applied to the wrong git tree, please drop us a note to help
improve the system. BTW, we also suggest to use '--base' option to specify the
base tree in git format-patch, please see https://stackoverflow.com/a/37406982]

url:    https://github.com/0day-ci/linux/commits/Huaixin-Chang/alios-sched-Fix-race-between-runtime-distribution-and-assignment/20200326-064002
base:   https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git 9c40365a65d62d7c06a95fb331b3442cb02d2fd9
config: openrisc-randconfig-a001-20200326 (attached as .config)
compiler: or1k-linux-gcc (GCC) 9.2.0
reproduce:
        wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        GCC_VERSION=9.2.0 make.cross ARCH=openrisc 

If you fix the issue, kindly add following tag
Reported-by: kbuild test robot <lkp@intel.com>

Note: it may well be a FALSE warning. FWIW you are at least aware of it now.
http://gcc.gnu.org/wiki/Better_Uninitialized_Warnings

All warnings (new ones prefixed by >>):

   kernel/sched/fair.c: In function 'distribute_cfs_runtime':
>> kernel/sched/fair.c:4875:6: warning: 'remaining' may be used uninitialized in this function [-Wmaybe-uninitialized]
    4875 |   if (!remaining)
         |      ^

vim +/remaining +4875 kernel/sched/fair.c

671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4838  
a340e0a2673eff kernel/sched/fair.c Huaixin Chang  2020-03-25  4839  static void distribute_cfs_runtime(struct cfs_bandwidth *cfs_b)
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4840  {
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4841  	struct cfs_rq *cfs_rq;
a340e0a2673eff kernel/sched/fair.c Huaixin Chang  2020-03-25  4842  	u64 runtime, remaining;
a340e0a2673eff kernel/sched/fair.c Huaixin Chang  2020-03-25  4843  	unsigned long flags;
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4844  
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4845  	rcu_read_lock();
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4846  	list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4847  				throttled_list) {
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4848  		struct rq *rq = rq_of(cfs_rq);
8a8c69c3277886 kernel/sched/fair.c Peter Zijlstra 2016-10-04  4849  		struct rq_flags rf;
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4850  
c0ad4aa4d8416a kernel/sched/fair.c Peter Zijlstra 2019-01-07  4851  		rq_lock_irqsave(rq, &rf);
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4852  		if (!cfs_rq_throttled(cfs_rq))
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4853  			goto next;
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4854  
5e2d2cc2588bd3 kernel/sched/fair.c Liangyan       2019-08-26  4855  		/* By the above check, this should never be true */
5e2d2cc2588bd3 kernel/sched/fair.c Liangyan       2019-08-26  4856  		SCHED_WARN_ON(cfs_rq->runtime_remaining > 0);
5e2d2cc2588bd3 kernel/sched/fair.c Liangyan       2019-08-26  4857  
a340e0a2673eff kernel/sched/fair.c Huaixin Chang  2020-03-25  4858  		raw_spin_lock_irqsave(&cfs_b->lock, flags);
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4859  		runtime = -cfs_rq->runtime_remaining + 1;
a340e0a2673eff kernel/sched/fair.c Huaixin Chang  2020-03-25  4860  		if (runtime > cfs_b->runtime)
a340e0a2673eff kernel/sched/fair.c Huaixin Chang  2020-03-25  4861  			runtime = cfs_b->runtime;
a340e0a2673eff kernel/sched/fair.c Huaixin Chang  2020-03-25  4862  		cfs_b->runtime -= runtime;
a340e0a2673eff kernel/sched/fair.c Huaixin Chang  2020-03-25  4863  		remaining = cfs_b->runtime;
a340e0a2673eff kernel/sched/fair.c Huaixin Chang  2020-03-25  4864  		raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4865  
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4866  		cfs_rq->runtime_remaining += runtime;
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4867  
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4868  		/* we check whether we're throttled above */
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4869  		if (cfs_rq->runtime_remaining > 0)
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4870  			unthrottle_cfs_rq(cfs_rq);
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4871  
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4872  next:
c0ad4aa4d8416a kernel/sched/fair.c Peter Zijlstra 2019-01-07  4873  		rq_unlock_irqrestore(rq, &rf);
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4874  
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21 @4875  		if (!remaining)
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4876  			break;
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4877  	}
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4878  	rcu_read_unlock();
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4879  }
671fd9dabe5239 kernel/sched_fair.c Paul Turner    2011-07-21  4880  

:::::: The code at line 4875 was first introduced by commit
:::::: 671fd9dabe5239ad218c7eb48b2b9edee50250e6 sched: Add support for unthrottling group entities

:::::: TO: Paul Turner <pjt@google.com>
:::::: CC: Ingo Molnar <mingo@elte.hu>

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org

[-- Attachment #2: config.gz --]
[-- Type: application/gzip, Size: 32519 bytes --]

[PATCH v2] sched: Fix race between runtime distribution and assignment

[Huaixin Chang]

Currently, there is a potential race between distribute_cfs_runtime()
and assign_cfs_rq_runtime(). Race happens when cfs_b->runtime is read,
distributes without holding lock and finds out there is not enough
runtime to charge against after distribution. Because
assign_cfs_rq_runtime() might be called during distribution, and use
cfs_b->runtime at the same time.

Fibtest is the tool to test this race. Assume all gcfs_rq is throttled
and cfs period timer runs, slow threads might run and sleep, returning
unused cfs_rq runtime and keeping min_cfs_rq_runtime in their local
pool. If all this happens sufficiently quickly, cfs_b->runtime will drop
a lot. If runtime distributed is large too, over-use of runtime happens.

A runtime over-using by about 70 percent of quota is seen when we
test fibtest on a 96-core machine. We run fibtest with 1 fast thread and
95 slow threads in test group, configure 10ms quota for this group and
see the CPU usage of fibtest is 17.0%, which is far more than the
expected 10%.

On a smaller machine with 32 cores, we also run fibtest with 96
threads. CPU usage is more than 12%, which is also more than expected
10%. This shows that on similar workloads, this race do affect CPU
bandwidth control.

Solve this by holding lock inside distribute_cfs_runtime().

Fixes: c06f04c70489 ("sched: Fix potential near-infinite distribute_cfs_runtime() loop")
Signed-off-by: Huaixin Chang <changhuaixin@linux.alibaba.com>
---
v2: fix spelling, initialize variable rumaining in distribute_cfs_runtime()
---
 kernel/sched/fair.c | 31 ++++++++++++-------------------
 1 file changed, 12 insertions(+), 19 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c1217bfe5e81..fd30e06a7ffc 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4629,11 +4629,11 @@ void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
 		resched_curr(rq);
 }
 
-static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
+static void distribute_cfs_runtime(struct cfs_bandwidth *cfs_b)
 {
 	struct cfs_rq *cfs_rq;
-	u64 runtime;
-	u64 starting_runtime = remaining;
+	u64 runtime, remaining = 1;
+	unsigned long flags;
 
 	rcu_read_lock();
 	list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
@@ -4648,10 +4648,13 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
 		/* By the above check, this should never be true */
 		SCHED_WARN_ON(cfs_rq->runtime_remaining > 0);
 
+		raw_spin_lock_irqsave(&cfs_b->lock, flags);
 		runtime = -cfs_rq->runtime_remaining + 1;
-		if (runtime > remaining)
-			runtime = remaining;
-		remaining -= runtime;
+		if (runtime > cfs_b->runtime)
+			runtime = cfs_b->runtime;
+		cfs_b->runtime -= runtime;
+		remaining = cfs_b->runtime;
+		raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
 
 		cfs_rq->runtime_remaining += runtime;
 
@@ -4666,8 +4669,6 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
 			break;
 	}
 	rcu_read_unlock();
-
-	return starting_runtime - remaining;
 }
 
 /*
@@ -4678,7 +4679,6 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
  */
 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun, unsigned long flags)
 {
-	u64 runtime;
 	int throttled;
 
 	/* no need to continue the timer with no bandwidth constraint */
@@ -4708,23 +4708,17 @@ static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun, u
 
 	/*
 	 * This check is repeated as we are holding onto the new bandwidth while
-	 * we unthrottle. This can potentially race with an unthrottled group
-	 * trying to acquire new bandwidth from the global pool. This can result
-	 * in us over-using our runtime if it is all used during this loop, but
-	 * only by limited amounts in that extreme case.
+	 * we unthrottle.
 	 */
 	while (throttled && cfs_b->runtime > 0 && !cfs_b->distribute_running) {
-		runtime = cfs_b->runtime;
 		cfs_b->distribute_running = 1;
 		raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
 		/* we can't nest cfs_b->lock while distributing bandwidth */
-		runtime = distribute_cfs_runtime(cfs_b, runtime);
+		distribute_cfs_runtime(cfs_b);
 		raw_spin_lock_irqsave(&cfs_b->lock, flags);
 
 		cfs_b->distribute_running = 0;
 		throttled = !list_empty(&cfs_b->throttled_cfs_rq);
-
-		lsub_positive(&cfs_b->runtime, runtime);
 	}
 
 	/*
@@ -4858,10 +4852,9 @@ static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
 	if (!runtime)
 		return;
 
-	runtime = distribute_cfs_runtime(cfs_b, runtime);
+	distribute_cfs_runtime(cfs_b);
 
 	raw_spin_lock_irqsave(&cfs_b->lock, flags);
-	lsub_positive(&cfs_b->runtime, runtime);
 	cfs_b->distribute_running = 0;
 	raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
 }
-- 
2.14.4.44.g2045bb6

Re: [PATCH v2] sched: Fix race between runtime distribution and assignment

[bsegall]

Huaixin Chang <changhuaixin@linux.alibaba.com> writes:

> Currently, there is a potential race between distribute_cfs_runtime()
> and assign_cfs_rq_runtime(). Race happens when cfs_b->runtime is read,
> distributes without holding lock and finds out there is not enough
> runtime to charge against after distribution. Because
> assign_cfs_rq_runtime() might be called during distribution, and use
> cfs_b->runtime at the same time.
>
> Fibtest is the tool to test this race. Assume all gcfs_rq is throttled
> and cfs period timer runs, slow threads might run and sleep, returning
> unused cfs_rq runtime and keeping min_cfs_rq_runtime in their local
> pool. If all this happens sufficiently quickly, cfs_b->runtime will drop
> a lot. If runtime distributed is large too, over-use of runtime happens.
>
> A runtime over-using by about 70 percent of quota is seen when we
> test fibtest on a 96-core machine. We run fibtest with 1 fast thread and
> 95 slow threads in test group, configure 10ms quota for this group and
> see the CPU usage of fibtest is 17.0%, which is far more than the
> expected 10%.
>
> On a smaller machine with 32 cores, we also run fibtest with 96
> threads. CPU usage is more than 12%, which is also more than expected
> 10%. This shows that on similar workloads, this race do affect CPU
> bandwidth control.
>
> Solve this by holding lock inside distribute_cfs_runtime().

Some minor requests below, other than that

Reviewed-by: Ben Segall <bsegall@google.com>

>
> Fixes: c06f04c70489 ("sched: Fix potential near-infinite distribute_cfs_runtime() loop")
> Signed-off-by: Huaixin Chang <changhuaixin@linux.alibaba.com>
> ---
> v2: fix spelling, initialize variable rumaining in distribute_cfs_runtime()
> ---
>  kernel/sched/fair.c | 31 ++++++++++++-------------------
>  1 file changed, 12 insertions(+), 19 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index c1217bfe5e81..fd30e06a7ffc 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -4629,11 +4629,11 @@ void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
>  		resched_curr(rq);
>  }
>  
> -static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
> +static void distribute_cfs_runtime(struct cfs_bandwidth *cfs_b)
>  {
>  	struct cfs_rq *cfs_rq;
> -	u64 runtime;
> -	u64 starting_runtime = remaining;
> +	u64 runtime, remaining = 1;
> +	unsigned long flags;
>  
>  	rcu_read_lock();
>  	list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
> @@ -4648,10 +4648,13 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
>  		/* By the above check, this should never be true */
>  		SCHED_WARN_ON(cfs_rq->runtime_remaining > 0);
>  
> +		raw_spin_lock_irqsave(&cfs_b->lock, flags);

No need for _irqsave/_irqrestore, the rqlock already did.

>  		runtime = -cfs_rq->runtime_remaining + 1;
> -		if (runtime > remaining)
> -			runtime = remaining;
> -		remaining -= runtime;
> +		if (runtime > cfs_b->runtime)
> +			runtime = cfs_b->runtime;
> +		cfs_b->runtime -= runtime;
> +		remaining = cfs_b->runtime;
> +		raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
>  
>  		cfs_rq->runtime_remaining += runtime;
>  
> @@ -4666,8 +4669,6 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
>  			break;
>  	}
>  	rcu_read_unlock();
> -
> -	return starting_runtime - remaining;
>  }
>  
>  /*
> @@ -4678,7 +4679,6 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
>   */
>  static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun, unsigned long flags)
>  {
> -	u64 runtime;
>  	int throttled;
>  
>  	/* no need to continue the timer with no bandwidth constraint */
> @@ -4708,23 +4708,17 @@ static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun, u
>  
>  	/*
>  	 * This check is repeated as we are holding onto the new bandwidth while
> -	 * we unthrottle. This can potentially race with an unthrottled group
> -	 * trying to acquire new bandwidth from the global pool. This can result
> -	 * in us over-using our runtime if it is all used during this loop, but
> -	 * only by limited amounts in that extreme case.
> +	 * we unthrottle.

"This check is repeated as we release cfs_b->lock while we unthrottle."
or something like that. This code is no longer even holding onto the new
bandwidth on its own.

>  	 */
>  	while (throttled && cfs_b->runtime > 0 && !cfs_b->distribute_running) {
> -		runtime = cfs_b->runtime;
>  		cfs_b->distribute_running = 1;
>  		raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
>  		/* we can't nest cfs_b->lock while distributing bandwidth */
> -		runtime = distribute_cfs_runtime(cfs_b, runtime);
> +		distribute_cfs_runtime(cfs_b);
>  		raw_spin_lock_irqsave(&cfs_b->lock, flags);
>  
>  		cfs_b->distribute_running = 0;
>  		throttled = !list_empty(&cfs_b->throttled_cfs_rq);
> -
> -		lsub_positive(&cfs_b->runtime, runtime);
>  	}
>  
>  	/*
> @@ -4858,10 +4852,9 @@ static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
>  	if (!runtime)
>  		return;
>  
> -	runtime = distribute_cfs_runtime(cfs_b, runtime);
> +	distribute_cfs_runtime(cfs_b);
>  
>  	raw_spin_lock_irqsave(&cfs_b->lock, flags);
> -	lsub_positive(&cfs_b->runtime, runtime);
>  	cfs_b->distribute_running = 0;
>  	raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
>  }

[PATCH v3] sched/fair: Fix race between runtime distribution and assignment

[Huaixin Chang]

Currently, there is a potential race between distribute_cfs_runtime()
and assign_cfs_rq_runtime(). Race happens when cfs_b->runtime is read,
distributes without holding lock and finds out there is not enough
runtime to charge against after distribution. Because
assign_cfs_rq_runtime() might be called during distribution, and use
cfs_b->runtime at the same time.

Fibtest is the tool to test this race. Assume all gcfs_rq is throttled
and cfs period timer runs, slow threads might run and sleep, returning
unused cfs_rq runtime and keeping min_cfs_rq_runtime in their local
pool. If all this happens sufficiently quickly, cfs_b->runtime will drop
a lot. If runtime distributed is large too, over-use of runtime happens.

A runtime over-using by about 70 percent of quota is seen when we
test fibtest on a 96-core machine. We run fibtest with 1 fast thread and
95 slow threads in test group, configure 10ms quota for this group and
see the CPU usage of fibtest is 17.0%, which is far more than the
expected 10%.

On a smaller machine with 32 cores, we also run fibtest with 96
threads. CPU usage is more than 12%, which is also more than expected
10%. This shows that on similar workloads, this race do affect CPU
bandwidth control.

Solve this by holding lock inside distribute_cfs_runtime().

Fixes: c06f04c70489 ("sched: Fix potential near-infinite distribute_cfs_runtime() loop")
Signed-off-by: Huaixin Chang <changhuaixin@linux.alibaba.com>
Reviewed-by: Ben Segall <bsegall@google.com>
Link: https://lore.kernel.org/lkml/20200325092602.22471-1-changhuaixin@linux.alibaba.com/
---
 kernel/sched/fair.c | 31 +++++++++++--------------------
 1 file changed, 11 insertions(+), 20 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c1217bfe5e81..0eaa12d0f1b9 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4629,11 +4629,10 @@ void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
 		resched_curr(rq);
 }
 
-static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
+static void distribute_cfs_runtime(struct cfs_bandwidth *cfs_b)
 {
 	struct cfs_rq *cfs_rq;
-	u64 runtime;
-	u64 starting_runtime = remaining;
+	u64 runtime, remaining = 1;
 
 	rcu_read_lock();
 	list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
@@ -4648,10 +4647,13 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
 		/* By the above check, this should never be true */
 		SCHED_WARN_ON(cfs_rq->runtime_remaining > 0);
 
+		raw_spin_lock(&cfs_b->lock);
 		runtime = -cfs_rq->runtime_remaining + 1;
-		if (runtime > remaining)
-			runtime = remaining;
-		remaining -= runtime;
+		if (runtime > cfs_b->runtime)
+			runtime = cfs_b->runtime;
+		cfs_b->runtime -= runtime;
+		remaining = cfs_b->runtime;
+		raw_spin_unlock(&cfs_b->lock);
 
 		cfs_rq->runtime_remaining += runtime;
 
@@ -4666,8 +4668,6 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
 			break;
 	}
 	rcu_read_unlock();
-
-	return starting_runtime - remaining;
 }
 
 /*
@@ -4678,7 +4678,6 @@ static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, u64 remaining)
  */
 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun, unsigned long flags)
 {
-	u64 runtime;
 	int throttled;
 
 	/* no need to continue the timer with no bandwidth constraint */
@@ -4707,24 +4706,17 @@ static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun, u
 	cfs_b->nr_throttled += overrun;
 
 	/*
-	 * This check is repeated as we are holding onto the new bandwidth while
-	 * we unthrottle. This can potentially race with an unthrottled group
-	 * trying to acquire new bandwidth from the global pool. This can result
-	 * in us over-using our runtime if it is all used during this loop, but
-	 * only by limited amounts in that extreme case.
+	 * This check is repeated as we release cfs_b->lock while we unthrottle.
 	 */
 	while (throttled && cfs_b->runtime > 0 && !cfs_b->distribute_running) {
-		runtime = cfs_b->runtime;
 		cfs_b->distribute_running = 1;
 		raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
 		/* we can't nest cfs_b->lock while distributing bandwidth */
-		runtime = distribute_cfs_runtime(cfs_b, runtime);
+		distribute_cfs_runtime(cfs_b);
 		raw_spin_lock_irqsave(&cfs_b->lock, flags);
 
 		cfs_b->distribute_running = 0;
 		throttled = !list_empty(&cfs_b->throttled_cfs_rq);
-
-		lsub_positive(&cfs_b->runtime, runtime);
 	}
 
 	/*
@@ -4858,10 +4850,9 @@ static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
 	if (!runtime)
 		return;
 
-	runtime = distribute_cfs_runtime(cfs_b, runtime);
+	distribute_cfs_runtime(cfs_b);
 
 	raw_spin_lock_irqsave(&cfs_b->lock, flags);
-	lsub_positive(&cfs_b->runtime, runtime);
 	cfs_b->distribute_running = 0;
 	raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
 }
-- 
2.14.4.44.g2045bb6

Re: [PATCH v3] sched/fair: Fix race between runtime distribution and assignment

[Peter Zijlstra]

On Fri, Mar 27, 2020 at 11:26:25AM +0800, Huaixin Chang wrote:
> Currently, there is a potential race between distribute_cfs_runtime()
> and assign_cfs_rq_runtime(). Race happens when cfs_b->runtime is read,
> distributes without holding lock and finds out there is not enough
> runtime to charge against after distribution. Because
> assign_cfs_rq_runtime() might be called during distribution, and use
> cfs_b->runtime at the same time.
> 
> Fibtest is the tool to test this race. Assume all gcfs_rq is throttled
> and cfs period timer runs, slow threads might run and sleep, returning
> unused cfs_rq runtime and keeping min_cfs_rq_runtime in their local
> pool. If all this happens sufficiently quickly, cfs_b->runtime will drop
> a lot. If runtime distributed is large too, over-use of runtime happens.
> 
> A runtime over-using by about 70 percent of quota is seen when we
> test fibtest on a 96-core machine. We run fibtest with 1 fast thread and
> 95 slow threads in test group, configure 10ms quota for this group and
> see the CPU usage of fibtest is 17.0%, which is far more than the
> expected 10%.
> 
> On a smaller machine with 32 cores, we also run fibtest with 96
> threads. CPU usage is more than 12%, which is also more than expected
> 10%. This shows that on similar workloads, this race do affect CPU
> bandwidth control.
> 
> Solve this by holding lock inside distribute_cfs_runtime().
> 
> Fixes: c06f04c70489 ("sched: Fix potential near-infinite distribute_cfs_runtime() loop")
> Signed-off-by: Huaixin Chang <changhuaixin@linux.alibaba.com>
> Reviewed-by: Ben Segall <bsegall@google.com>

Thanks!