Hi!

Am 02.11.21 um 17:02 schrieb Michal Koutn?:
> [snip]
> I have a reproducer (attached) that can hit this window quite easily
> after tuning. I can observe consequences of it even with a recent 5.15
> kernel. (And I also have reports from real world workloads failing due
> to a7b359fc6a37 ("sched/fair: Correctly insert cfs_rq's to list on
> unthrottle").)

Thanks for the reproducer!

To provide yet another data point, Kevin (on Cc) is running into this
bug as well very reliable with a production workload, so we started
looking into this too. His crashes indicate a use-after-free of a cfs_rq
in update_blocked_averages(), much like you already diagnosed in your
initial patch description -- there are live cfs_rq's (on_list=1) in an
about to be kfree()'d task group in free_fair_sched_group().

His kernel config happened to lead to a layout of struct sched_entity
that put the 'my_q' member directly into the middle of the object which
makes it incidentally overlap with SLUB's freelist pointer. That in
combination with SLAB_FREELIST_HARDENED's freelist pointer mangling
leads to a reliable access violation in form of a #GP which allowed us
to make the UAF fail fast.

As the real root cause cannot be seen from the crash backtrace only, we
tested a debug patch (attached) that unveiled that the real offender is
tg_unthrottle_up() getting called via sched_cfs_period_timer() via the
timer interrupt at an inconvenient time, namely when
unregister_fair_sched_group() unlinks all cfs_rq's from the dying task
group. It doesn't protect itself from getting interrupted, so if the
timer interrupt triggers while we iterate over all CPUs or after
unregister_fair_sched_group() has finished but prior to unlinking the
task group in sched_offline_group(), sched_cfs_period_timer() will
execute and walk the list of task groups, trying to unthrottle cfs_rq's
and possibly re-add them to the dying task group. These will later -- in
free_fair_sched_group() -- be kfree()'ed while still being linked,
leading to the fireworks Kevin and you are seeing.

We tried the below patch which, unfortunately, doesn't fix the issue. So
there must be something else. :(

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 978460f891a1..afee07e9faf9 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -9506,13 +9506,17 @@ void sched_offline_group(struct task_group *tg)
{
unsigned long flags;

- /* End participation in shares distribution: */
- unregister_fair_sched_group(tg);
-
+ /*
+ * Unlink first, to avoid walk_tg_tree_from() from finding us
+ * (via sched_cfs_period_timer()).
+ */
spin_lock_irqsave(&task_group_lock, flags);
list_del_rcu(&tg->list);
list_del_rcu(&tg->siblings);
spin_unlock_irqrestore(&task_group_lock, flags);
+
+ /* End participation in shares distribution: */
+ unregister_fair_sched_group(tg);
}

static void sched_change_group(struct task_struct *tsk, int type)

> [snip]
>
> The possibilities for the current problem:
>
> 1) Revert a7b359fc6a37 ("sched/fair: Correctly insert cfs_rq's to list on unthrottle") and its fixups.
> (Not exclusive with the other suggestions, rather a stop-gap for the
> time being.)
>
> 2) Don't add offlined task_groups into the undecayed list
> - Your proposal with overloaded on_list=2 could serve as mark of that,
> but it's a hack IMO.

> - Proper way (tm) would be to use css_tryget_online() and css_put() when
> dealing with the list (my favorite at the moment).

That might work, as -- at least in Kevin's case -- it all gets triggered
by a dying cgroup.

> 3) Narrowing the race-window dramatically
> - that is by moving list removal from unregister_fair_sched_group() to
> free_fair_sched_group(),

That might work, too. However, the unlinking needs protection against
the timer interrupt (and other sources?) which might try to re-add
entries. Or won't that happen any more, as at lesat one RCU GP has
passed? Anyhow, the kfree() calls likely would need to become
kfree_rcu() to handle concurrent traversal of cfs_rq's.

> - <del>or use list_empty(tg->list) as indicator whether we're working
> with onlined task_group.</del> (won't work for RCU list)
>
> 4) Rework how throttled load is handled (hand waving)
> - There is remove_entity_load_avg() that moves the load to parent upon
> final removal. Maybe it could be generalized for temporary removals by
> throttling (so that unthrottling could again add only non-empty
> cfs_rqs to the list and undecayed load won't skew fairness).
> - or the way of [1].
>
> 5) <your ideas>

It should be something that can be backported to stable kernels, as this
seem to affect v5.13, too.

Thanks,
Mathias

Attachments:

5.14-sched-fair-dbg.diff (2.60 kB)

2021-11-03 10:53:30

by Mathias Krause

[permalink] [raw]

Subject: Re: task_group unthrottling and removal race (was Re: [PATCH] sched/fair: Use rq->lock when checking cfs_rq list) presence

Heh, sometimes a good night sleep helps unfolding the knot in the head!

Am 03.11.21 um 10:51 schrieb Mathias Krause:
> [snip]
>
> We tried the below patch which, unfortunately, doesn't fix the issue. So
> there must be something else. :(
>
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 978460f891a1..afee07e9faf9 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -9506,13 +9506,17 @@ void sched_offline_group(struct task_group *tg)
> {
> unsigned long flags;
>
> - /* End participation in shares distribution: */
> - unregister_fair_sched_group(tg);
> -
> + /*
> + * Unlink first, to avoid walk_tg_tree_from() from finding us
> + * (via sched_cfs_period_timer()).
> + */
> spin_lock_irqsave(&task_group_lock, flags);
> list_del_rcu(&tg->list);
> list_del_rcu(&tg->siblings);
> spin_unlock_irqrestore(&task_group_lock, flags);
> +
> + /* End participation in shares distribution: */

Adding synchronize_rcu() here will ensure all concurrent RCU "readers"
will have finished what they're doing, so we can unlink safely. That
was, apparently, the missing piece.

> + unregister_fair_sched_group(tg);
> }
>
> static void sched_change_group(struct task_struct *tsk, int type)
>

Now, synchronize_rcu() is quite a heavy hammer. So using a RCU callback
should be more appropriate. I'll hack up something and post a proper
patch, if you don't beat me to.

Mathias

2021-11-03 11:13:26

by Michal Koutný

[permalink] [raw]

Subject: Re: task_group unthrottling and removal race (was Re: [PATCH] sched/fair: Use rq->lock when checking cfs_rq list) presence

On Wed, Nov 03, 2021 at 11:51:12AM +0100, Mathias Krause <[email protected]> wrote:
> Adding synchronize_rcu() here will ensure all concurrent RCU "readers"
> will have finished what they're doing, so we can unlink safely. That
> was, apparently, the missing piece.

What reader(s) are you referring to here? The
list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
throttled_list) in distribute_cfs_runtime()?

I'm think (not sure) that wouldn't work since the unthrottle_cfs_rq can
still be called after this synchronize_rcu() but before
free_fair_sched_group().

(But if you considered update_blocked_averages() as the reader(s) and
synchronize_rcu() within free_fair_sched_group(), that may ensure UBA
won't step on a free'd cfs_rq (+unlinking would need to happen only in
free_fair_sched_group() too.))

Michal

2021-11-03 14:19:52

2021-11-10 15:20:54

by Vincent Guittot

[permalink] [raw]

Subject: Re: [PATCH] sched/fair: Prevent dead task groups from regaining cfs_rq's

On Tue, 9 Nov 2021 at 19:47, Michal Koutný <[email protected]> wrote:
>
> Hello.
>
> Let me add a little summary (and I'm CCing cgroups ML too).
>
> The cgroup API allows following callbacks (simplified explanation):
>
> - .css_offline called after killing main reference
> - .css_released called when css.refcnt hits zero
> - .css_free called after css_released and RCU GP
>
> (The hidden catch is that they're not called directly but through workqueues,
> see css_free_work_fn() for details. .css_free() is queued after RCU GP though.)
>
> How is this currently used in the cpu controller:
>
> - .css_offline not used
> - .css_released sched_offline_group / unregister_fair_sched_group
> - .css_free sched_free_group / free_fair_sched_group
>
>
> On Mon, Nov 08, 2021 at 12:40:19PM +0100, Peter Zijlstra <[email protected]> wrote:
> > Something like so good?
>
> Thanks for putting this together, in short I understand it reshuffles as follows:
>
> .css_offline not used
> .css_released cpu_cgroup_css_released
> sched_released_group(tg)
> // unlinking from tg tree
> .css_free cpu_cgroup_css_free
> sched_unregister_group(tg)
> unregister_fair_sched_group(tg)
> for_each(cpu)
> remove_entity_load_avg(cfs_rq)
> list_del_leaf_cfs_rq(cfs_rq) (1)
> destroy_cfs_bandwidth(tg) (2)
> call_rcu(sched_free_group_rcu) (3)
> [rcu] sched_free_group
>
> I see two following issues with this:
>
> The cfs_bandwidth.period_timer is still active between (1) and (2) and can be
> fired and tg_unthrottle_up() may add a cfs_rq back to the leaf list (subsequent
> GP won't help).
> (Admittedly, this window is shorter than the original window between
> cpu_cgroup_css_released() and cpu_cgroup_css_released().)
>
> Having another call_rcu() at (3) seems overly complex given the cgroup API
> provides a grace period for free (pun intended :-).
>
>
> Therefore, symbolically, the symbolic ordering should be:
>
> .css_offline not used
> .css_released cpu_cgroup_css_released
> sched_unregister_group(tg)
> unregister_fair_sched_group(tg)
> destroy_cfs_bandwidth(tg)
> for_each(cpu)
> remove_entity_load_avg(cfs_rq)
> list_del_leaf_cfs_rq(cfs_rq)

As we are not unlinked from tg tree, parent can walk_tg_tree_from and
add it back

> sched_released_group(tg)
> // unlinking from tg tree
>
> .css_free cpu_cgroup_css_free
> sched_free_group
>
> That is, the destroy_cfs_bandwidth() is called first to make sure the
> tg_unthrottle_up() won't undo some of the cleanups and the respective
> structures are only freed after RCU grace period.
>
> (Considering Vincent's remark, remove_entity_load_avg() and
> list_del_leaf_cfs_rq() should be swapped but I'd keep that for a different
> patch.)
>
> To continue the discussion, the suggestion above in a form of diff (I stripped
> the commit message for now).
>
> --8<--
> diff --git a/kernel/sched/autogroup.c b/kernel/sched/autogroup.c
> index 2067080bb235..8629b37d118e 100644
> --- a/kernel/sched/autogroup.c
> +++ b/kernel/sched/autogroup.c
> @@ -31,7 +31,7 @@ static inline void autogroup_destroy(struct kref *kref)
> ag->tg->rt_se = NULL;
> ag->tg->rt_rq = NULL;
> #endif
> - sched_offline_group(ag->tg);
> + sched_release_group(ag->tg);
> sched_destroy_group(ag->tg);
> }
>
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 523fd602ea90..a5ca3ae6837b 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -9771,12 +9771,12 @@ void sched_destroy_group(struct task_group *tg)
> call_rcu(&tg->rcu, sched_free_group_rcu);
> }
>
> -void sched_offline_group(struct task_group *tg)
> +void sched_release_group(struct task_group *tg)
> {
> unsigned long flags;
>
> - /* End participation in shares distribution: */
> unregister_fair_sched_group(tg);
> + unregister_rt_sched_group(tg);
>
> spin_lock_irqsave(&task_group_lock, flags);
> list_del_rcu(&tg->list);
> @@ -9896,7 +9896,7 @@ static void cpu_cgroup_css_released(struct cgroup_subsys_state *css)
> {
> struct task_group *tg = css_tg(css);
>
> - sched_offline_group(tg);
> + sched_release_group(tg);
> }
>
> static void cpu_cgroup_css_free(struct cgroup_subsys_state *css)
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 13950beb01a2..6e476f6d9435 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -11456,8 +11456,6 @@ void free_fair_sched_group(struct task_group *tg)
> {
> int i;
>
> - destroy_cfs_bandwidth(tg_cfs_bandwidth(tg));
> -
> for_each_possible_cpu(i) {
> if (tg->cfs_rq)
> kfree(tg->cfs_rq[i]);
> @@ -11534,6 +11532,8 @@ void unregister_fair_sched_group(struct task_group *tg)
> struct rq *rq;
> int cpu;
>
> + destroy_cfs_bandwidth(tg_cfs_bandwidth(tg));
> +
> for_each_possible_cpu(cpu) {
> if (tg->se[cpu])
> remove_entity_load_avg(tg->se[cpu]);
> diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> index bb945f8faeca..b48baaba2fc2 100644
> --- a/kernel/sched/rt.c
> +++ b/kernel/sched/rt.c
> @@ -137,13 +137,17 @@ static inline struct rq *rq_of_rt_se(struct sched_rt_entity *rt_se)
> return rt_rq->rq;
> }
>
> -void free_rt_sched_group(struct task_group *tg)
> +void unregister_rt_sched_group(struct task_group *tg)
> {
> - int i;
> -
> if (tg->rt_se)
> destroy_rt_bandwidth(&tg->rt_bandwidth);
>
> +}
> +
> +void free_rt_sched_group(struct task_group *tg)
> +{
> + int i;
> +
> for_each_possible_cpu(i) {
> if (tg->rt_rq)
> kfree(tg->rt_rq[i]);
> @@ -250,6 +254,8 @@ static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
> return &rq->rt;
> }
>
> +void unregister_rt_sched_group(struct task_group *tg) { }
> +
> void free_rt_sched_group(struct task_group *tg) { }
>
> int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index 7f1612d26c18..0e66749486e7 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -488,6 +488,7 @@ extern void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b);
> extern void start_cfs_bandwidth(struct cfs_bandwidth *cfs_b);
> extern void unthrottle_cfs_rq(struct cfs_rq *cfs_rq);
>
> +extern void unregister_rt_sched_group(struct task_group *tg);
> extern void free_rt_sched_group(struct task_group *tg);
> extern int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent);
> extern void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
> @@ -503,7 +504,7 @@ extern struct task_group *sched_create_group(struct task_group *parent);
> extern void sched_online_group(struct task_group *tg,
> struct task_group *parent);
> extern void sched_destroy_group(struct task_group *tg);
> -extern void sched_offline_group(struct task_group *tg);
> +extern void sched_release_group(struct task_group *tg);
>
> extern void sched_move_task(struct task_struct *tsk);
>
>