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

Groups > linux.kernel > #1331087 > unrolled thread

Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted bandwidth

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

  Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Juri Lelli <juri.lelli@arm.com> - 2016-02-10 12:40 +0100
    Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth luca abeni <luca.abeni@unitn.it> - 2016-02-10 12:50 +0100
      Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Juri Lelli <juri.lelli@arm.com> - 2016-02-10 13:00 +0100
        Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth luca abeni <luca.abeni@unitn.it> - 2016-02-19 14:50 +0100
          Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Steven Rostedt <rostedt@goodmis.org> - 2016-02-19 15:30 +0100
            Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Steven Rostedt <rostedt@goodmis.org> - 2016-02-19 16:00 +0100
            Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth luca abeni <luca.abeni@unitn.it> - 2016-02-19 16:00 +0100
              Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth luca abeni <luca.abeni@unitn.it> - 2016-02-22 12:10 +0100
        [PATCH 0/3] cleanup per rq tracking of admitted bandwidth  Luca Abeni <luca.abeni@unitn.it> - 2016-02-22 12:00 +0100
          [PATCH 2/4] Move the remaining __dl_{sub,add}_ac() calls from core.c to deadline.c Luca Abeni <luca.abeni@unitn.it> - 2016-02-22 12:00 +0100
          [PATCH 1/4] Move some calls to __dl_{sub,add}_ac() from core.c to deadline.c Luca Abeni <luca.abeni@unitn.it> - 2016-02-22 12:00 +0100
          [PATCH 3/4] Remove dl_new Luca Abeni <luca.abeni@unitn.it> - 2016-02-22 12:00 +0100
    Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth luca abeni <luca.abeni@unitn.it> - 2016-02-10 13:50 +0100
      Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Juri Lelli <juri.lelli@arm.com> - 2016-02-10 14:50 +0100
    Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Steven Rostedt <rostedt@goodmis.org> - 2016-02-10 15:40 +0100
      Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Juri Lelli <juri.lelli@arm.com> - 2016-02-10 17:30 +0100
        Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Juri Lelli <juri.lelli@arm.com> - 2016-02-11 13:20 +0100
          Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth luca abeni <luca.abeni@unitn.it> - 2016-02-11 13:30 +0100
            Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Juri Lelli <juri.lelli@arm.com> - 2016-02-11 13:30 +0100
              Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Juri Lelli <juri.lelli@arm.com> - 2016-02-11 13:50 +0100
                Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth luca abeni <luca.abeni@unitn.it> - 2016-02-11 14:10 +0100
                  Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Steven Rostedt <rostedt@goodmis.org> - 2016-02-11 15:30 +0100
                    Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Juri Lelli <juri.lelli@arm.com> - 2016-02-11 18:10 +0100
                      Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Peter Zijlstra <peterz@infradead.org> - 2016-02-12 18:10 +0100
                        Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Juri Lelli <juri.lelli@arm.com> - 2016-02-12 18:20 +0100
                    Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth Luca Abeni <luca.abeni@unitn.it> - 2016-02-11 22:50 +0100
              Re: [PATCH 1/2] sched/deadline: add per rq tracking of admitted  bandwidth luca abeni <luca.abeni@unitn.it> - 2016-02-11 13:50 +0100

Page 2 of 2 — ← Prev page 1 [2]

#1331930

On Thu, 11 Feb 2016 12:49:59 +0000
Juri Lelli <juri.lelli@arm.com> wrote:
[...]
> > > > > Luca, did you already face this problem (if I got it right)
> > > > > and thought of a way to fix it? I'll go back and stare a bit
> > > > > more at those paths.
> > > > In my patch I took care of the first case (modifying
> > > > select_task_rq_dl() to move the utilization from the "old rq"
> > > > to the "new rq"), but I never managed to trigger
> > > > select_fallback_rq() in my tests, so I overlooked that case.
> > > > 
> > > 
> > > Right, I was thinking to do the same. And you did that after
> > > grabbing both locks, right?
> > 
> > Not sure if I did everything correctly, but my code in
> > select_task_rq_dl() currently looks like this (you can obviously
> > ignore the "migrate_active" and "*_running_bw()" parts, and focus on
> > the "*_rq_bw()" stuff):
> > [...]
> >         if (rq != cpu_rq(cpu)) {
> >                 int migrate_active;
> > 
> >                 raw_spin_lock(&rq->lock);
> >                 migrate_active =
> > hrtimer_active(&p->dl.inactive_timer); if (migrate_active) {
> >                         hrtimer_try_to_cancel(&p->dl.inactive_timer);
> >                         sub_running_bw(&p->dl, &rq->dl);
> >                 }
> >                 sub_rq_bw(&p->dl, &rq->dl);
> >                 raw_spin_unlock(&rq->lock);
> >                 rq = cpu_rq(cpu);
> 
> Can't something happen here? My problem is that I use per-rq bw
> tracking to save/restore root_domain state. So, I fear that a
> root_domain update can happen while we are in the middle of moving bw
> from one cpu to another.
Well, I never used the rq utilization to re-build the root_domain
utilization (and I never played with root domains too much... :)...
So, I do not really know. Maybe the code should do:
	raw_spin_lock(&rq->lock);
	raw_spin_lock(&cpu_rq(cpu)->lock);
	sub_rq_bw(&p->dl, &rq->dl);
	add_rq_bw(&p->dl, &cpu_rq(cpu)->dl);
	[...]
?


			Luca

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

#1332041

On Thu, 11 Feb 2016 14:05:45 +0100
luca abeni <luca.abeni@unitn.it> wrote:

  
> Well, I never used the rq utilization to re-build the root_domain
> utilization (and I never played with root domains too much... :)...
> So, I do not really know. Maybe the code should do:
> 	raw_spin_lock(&rq->lock);
> 	raw_spin_lock(&cpu_rq(cpu)->lock);

Of course you want to use double_rq_lock() here instead.

-- Steve

> 	sub_rq_bw(&p->dl, &rq->dl);
> 	add_rq_bw(&p->dl, &cpu_rq(cpu)->dl);
> 	[...]
> ?
> 
> 
> 			Luca

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

#1332242

On 11/02/16 09:25, Steven Rostedt wrote:
> On Thu, 11 Feb 2016 14:05:45 +0100
> luca abeni <luca.abeni@unitn.it> wrote:
> 
>   
> > Well, I never used the rq utilization to re-build the root_domain
> > utilization (and I never played with root domains too much... :)...
> > So, I do not really know. Maybe the code should do:
> > 	raw_spin_lock(&rq->lock);
> > 	raw_spin_lock(&cpu_rq(cpu)->lock);
> 
> Of course you want to use double_rq_lock() here instead.
> 

Right. Is something like this completely out of question/broken?

I slighly tested it with Steve's test and I don't see the warning
anymore (sched_debug looks good as well); but my confidence is still
pretty low. :(

--->8---

From 9713e12bc682ca364e62f9d69bcd44598c50a8a9 Mon Sep 17 00:00:00 2001
From: Juri Lelli <juri.lelli@arm.com>
Date: Thu, 11 Feb 2016 16:55:49 +0000
Subject: [PATCH] fixup! sched/deadline: add per rq tracking of admitted
 bandwidth

Signed-off-by: Juri Lelli <juri.lelli@arm.com>
---
 include/linux/init_task.h |  1 +
 include/linux/sched.h     |  1 +
 kernel/sched/core.c       |  5 ++++-
 kernel/sched/deadline.c   | 26 +++++++++++++++++++++++++-
 4 files changed, 31 insertions(+), 2 deletions(-)

diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index f2cb8d4..c582f9d 100644
--- a/include/linux/init_task.h
+++ b/include/linux/init_task.h
@@ -199,6 +199,7 @@ extern struct task_group root_task_group;
 	.policy		= SCHED_NORMAL,					\
 	.cpus_allowed	= CPU_MASK_ALL,					\
 	.nr_cpus_allowed= NR_CPUS,					\
+	.fallback_cpu	= -1,						\
 	.mm		= NULL,						\
 	.active_mm	= &init_mm,					\
 	.restart_block = {						\
diff --git a/include/linux/sched.h b/include/linux/sched.h
index a10494a..a6fc95c 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1401,6 +1401,7 @@ struct task_struct {
 	struct task_struct *last_wakee;
 
 	int wake_cpu;
+	int fallback_cpu;
 #endif
 	int on_rq;
 
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 7fb9246..4e4bc41 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -1442,7 +1442,8 @@ static int select_fallback_rq(int cpu, struct task_struct *p)
 				continue;
 			if (!cpu_active(dest_cpu))
 				continue;
-			if (cpumask_test_cpu(dest_cpu, tsk_cpus_allowed(p)))
+			if (cpumask_test_cpu(dest_cpu, tsk_cpus_allowed(p))) {
+				p->fallback_cpu = dest_cpu;
 				return dest_cpu;
 		}
 	}
@@ -1490,6 +1491,7 @@ out:
 		}
 	}
 
+	p->fallback_cpu = dest_cpu;
 	return dest_cpu;
 }
 
@@ -1954,6 +1956,7 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 	if (task_cpu(p) != cpu) {
 		wake_flags |= WF_MIGRATED;
 		set_task_cpu(p, cpu);
+		p->fallback_cpu = -1;
 	}
 #endif /* CONFIG_SMP */
 
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 6368f43..1eccecf 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1043,6 +1043,21 @@ static void yield_task_dl(struct rq *rq)
 
 #ifdef CONFIG_SMP
 
+static void swap_task_ac_bw(struct task_struct *p,
+			    struct rq *from,
+			    struct rq *to)
+{
+	unsigned long flags;
+
+	lockdep_assert_held(&p->pi_lock);
+	local_irq_save(flags);
+	double_rq_lock(from, to);
+	__dl_sub_ac(from, p->dl.dl_bw);
+	__dl_add_ac(to, p->dl.dl_bw);
+	double_rq_unlock(from, to);
+	local_irq_restore(flags);
+}
+
 static int find_later_rq(struct task_struct *task);
 
 static int
@@ -1077,8 +1092,10 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
 		if (target != -1 &&
 				(dl_time_before(p->dl.deadline,
 					cpu_rq(target)->dl.earliest_dl.curr) ||
-				(cpu_rq(target)->dl.dl_nr_running == 0)))
+				(cpu_rq(target)->dl.dl_nr_running == 0))) {
 			cpu = target;
+			swap_task_ac_bw(p, rq, cpu_rq(target));
+		}
 	}
 	rcu_read_unlock();
 
@@ -1807,6 +1824,12 @@ static void prio_changed_dl(struct rq *rq, struct task_struct *p,
 		switched_to_dl(rq, p);
 }
 
+static void migrate_task_rq_dl(struct task_struct *p)
+{
+	if (p->fallback_cpu != -1)
+		swap_task_ac_bw(p, task_rq(p), cpu_rq(p->fallback_cpu));
+}
+
 const struct sched_class dl_sched_class = {
 	.next			= &rt_sched_class,
 	.enqueue_task		= enqueue_task_dl,
@@ -1820,6 +1843,7 @@ const struct sched_class dl_sched_class = {
 
 #ifdef CONFIG_SMP
 	.select_task_rq		= select_task_rq_dl,
+	.migrate_task_rq	= migrate_task_rq_dl,
 	.set_cpus_allowed       = set_cpus_allowed_dl,
 	.rq_online              = rq_online_dl,
 	.rq_offline             = rq_offline_dl,
-- 
2.7.0

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

#1332911

On Thu, Feb 11, 2016 at 05:10:12PM +0000, Juri Lelli wrote:
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 6368f43..1eccecf 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c

> +static void swap_task_ac_bw(struct task_struct *p,
> +			    struct rq *from,
> +			    struct rq *to)
> +{
> +	unsigned long flags;
> +
> +	lockdep_assert_held(&p->pi_lock);
> +	local_irq_save(flags);
> +	double_rq_lock(from, to);
> +	__dl_sub_ac(from, p->dl.dl_bw);
> +	__dl_add_ac(to, p->dl.dl_bw);
> +	double_rq_unlock(from, to);
> +	local_irq_restore(flags);
> +}

> +static void migrate_task_rq_dl(struct task_struct *p)
> +{
> +	if (p->fallback_cpu != -1)
> +		swap_task_ac_bw(p, task_rq(p), cpu_rq(p->fallback_cpu));
> +}

This patch scares me.

Now, my brain is having an awfully hard time trying to re-engage after
flu, but this looks very wrong.

So we call sched_class::migrate_task_rq() from set_task_cpu(), and we
call set_task_cpu() while potentially holding rq::lock's (try
push_dl_task() for kicks).

Sure, you play horrible games with fallback_cpu, but those games are
just that, horrible.


So your initial patch migrates the bandwidth along when a runnable task
gets moved about, this hack seems to be mostly about waking up. The
'normal' accounting is done on enqueue/dequeue, while here you use the
migration hook.

Having two separate means of accounting this also feels more fragile
than one would want.

Let me think a bit about this.

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

#1332934

On 12/02/16 18:05, Peter Zijlstra wrote:
> On Thu, Feb 11, 2016 at 05:10:12PM +0000, Juri Lelli wrote:
> > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> > index 6368f43..1eccecf 100644
> > --- a/kernel/sched/deadline.c
> > +++ b/kernel/sched/deadline.c
> 
> > +static void swap_task_ac_bw(struct task_struct *p,
> > +			    struct rq *from,
> > +			    struct rq *to)
> > +{
> > +	unsigned long flags;
> > +
> > +	lockdep_assert_held(&p->pi_lock);
> > +	local_irq_save(flags);
> > +	double_rq_lock(from, to);
> > +	__dl_sub_ac(from, p->dl.dl_bw);
> > +	__dl_add_ac(to, p->dl.dl_bw);
> > +	double_rq_unlock(from, to);
> > +	local_irq_restore(flags);
> > +}
> 
> > +static void migrate_task_rq_dl(struct task_struct *p)
> > +{
> > +	if (p->fallback_cpu != -1)
> > +		swap_task_ac_bw(p, task_rq(p), cpu_rq(p->fallback_cpu));
> > +}
> 
> This patch scares me.
> 

Yeah, same here. However, I didn't find yet something different to fix
this and wanted some help :).

> Now, my brain is having an awfully hard time trying to re-engage after
> flu, but this looks very wrong.
> 
> So we call sched_class::migrate_task_rq() from set_task_cpu(), and we
> call set_task_cpu() while potentially holding rq::lock's (try
> push_dl_task() for kicks).
> 
> Sure, you play horrible games with fallback_cpu, but those games are
> just that, horrible.
> 

Right. I'm counting on fallback_cpu to be able to not call
swap_task_ac_bw() (and the rq locks) during push/pull migrations.
I was actually thinking that we could have a non locked version of swap
and call that in push/pull from migrate_task_rq_dl. But this is most
probably more horrible.

> 
> So your initial patch migrates the bandwidth along when a runnable task
> gets moved about, this hack seems to be mostly about waking up. The
> 'normal' accounting is done on enqueue/dequeue, while here you use the
> migration hook.
> 

The problem is that I don't do anything in enqueue/dequeue (apart from
when cpuset migrates us while still on_rq), and I think we don't want to
do anything there as a task dl_bw should remain in ac_bw when it goes to
sleep, etc. This is the static view of admitted bw. We want to
save/restore the admitted bw in the root_domain also when tasks are
sleeping/blocked.

> Having two separate means of accounting this also feels more fragile
> than one would want.
> 
> Let me think a bit about this.
> 

I was looking at sending out a v2 with this as RFC. I guess is better if
I wait :).

Thanks!

Best,

- Juri

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

#1332396

On Thu, 11 Feb 2016 09:25:46 -0500
Steven Rostedt <rostedt@goodmis.org> wrote:

> On Thu, 11 Feb 2016 14:05:45 +0100
> luca abeni <luca.abeni@unitn.it> wrote:
> 
>   
> > Well, I never used the rq utilization to re-build the root_domain
> > utilization (and I never played with root domains too much... :)...
> > So, I do not really know. Maybe the code should do:
> > 	raw_spin_lock(&rq->lock);
> > 	raw_spin_lock(&cpu_rq(cpu)->lock);
> 
> Of course you want to use double_rq_lock() here instead.
Right... Of course I always miss something obvious ;-)


			Luca

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

#1331922

On Thu, 11 Feb 2016 12:27:54 +0000
Juri Lelli <juri.lelli@arm.com> wrote:

> On 11/02/16 13:22, Luca Abeni wrote:
> > Hi Juri,
> > 
> > On Thu, 11 Feb 2016 12:12:57 +0000
> > Juri Lelli <juri.lelli@arm.com> wrote:
> > [...]
> > > I think we still have (at least) two problems:
> > > 
> > >  - select_task_rq_dl, if we select a different target
> > >  - select_task_rq might make use of select_fallback_rq, if
> > > cpus_allowed changed after the task went to sleep
> > > 
> > > Second case is what creates the problem here, as we don't update
> > > task_rq(p) and fallback_cpu ac_bw. I was thinking we might do so,
> > > maybe adding fallback_cpu in task_struct, from
> > > migrate_task_rq_dl() (it has to be added yes), but I fear that we
> > > should hold both rq locks :/.
> > > 
> > > Luca, did you already face this problem (if I got it right) and
> > > thought of a way to fix it? I'll go back and stare a bit more at
> > > those paths.
> > In my patch I took care of the first case (modifying
> > select_task_rq_dl() to move the utilization from the "old rq" to the
> > "new rq"), but I never managed to trigger select_fallback_rq() in my
> > tests, so I overlooked that case.
> > 
> 
> Right, I was thinking to do the same. And you did that after grabbing
> both locks, right?

Not sure if I did everything correctly, but my code in
select_task_rq_dl() currently looks like this (you can obviously
ignore the "migrate_active" and "*_running_bw()" parts, and focus on
the "*_rq_bw()" stuff):
[...]
        if (rq != cpu_rq(cpu)) {
                int migrate_active;

                raw_spin_lock(&rq->lock);
                migrate_active = hrtimer_active(&p->dl.inactive_timer);
                if (migrate_active) {
                        hrtimer_try_to_cancel(&p->dl.inactive_timer);
                        sub_running_bw(&p->dl, &rq->dl);
                }
                sub_rq_bw(&p->dl, &rq->dl);
                raw_spin_unlock(&rq->lock);
                rq = cpu_rq(cpu);
                raw_spin_lock(&rq->lock);
                add_rq_bw(&p->dl, &rq->dl);
                if (migrate_active)
                        add_running_bw(&p->dl, &rq->dl);
                raw_spin_unlock(&rq->lock);
        }
[...]

lockdep is not screaming, and I am not able to trigger any race
condition or strange behaviour (I am currently at more than 24h of
continuous stress-testing, but maybe my testcase is not so good in
finding races here :)



				Luca

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | linux.kernel

csiph-web