| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Tue, 13 Jun 2023 12:51:59 +0200
From: Frederic Weisbecker <frederic@...nel.org>
To: Anna-Maria Behnsen <anna-maria@...utronix.de>
Cc: linux-kernel@...r.kernel.org,
Peter Zijlstra <peterz@...radead.org>,
John Stultz <jstultz@...gle.com>,
Thomas Gleixner <tglx@...utronix.de>,
Eric Dumazet <edumazet@...gle.com>,
"Rafael J . Wysocki" <rafael.j.wysocki@...el.com>,
Arjan van de Ven <arjan@...radead.org>,
"Paul E . McKenney" <paulmck@...nel.org>,
Frederic Weisbecker <fweisbec@...il.com>,
Rik van Riel <riel@...riel.com>,
Steven Rostedt <rostedt@...dmis.org>,
Sebastian Siewior <bigeasy@...utronix.de>,
Giovanni Gherdovich <ggherdovich@...e.cz>,
Lukasz Luba <lukasz.luba@....com>,
"Gautham R . Shenoy" <gautham.shenoy@....com>
Subject: Re: [PATCH v7 19/21] timer: Implement the hierarchical pull model
On Wed, May 24, 2023 at 09:06:27AM +0200, Anna-Maria Behnsen wrote:
> +static bool tmigr_update_events(struct tmigr_group *group,
> + struct tmigr_group *child,
> + struct tmigr_walk *data)
> +{
> + struct tmigr_event *evt, *first_childevt;
> + bool walk_done, remote = data->remote;
> + u64 nextexp;
> +
> + if (child) {
> + if (data->childstate.active)
> + return true;
> +
> + raw_spin_lock(&child->lock);
> + raw_spin_lock_nested(&group->lock, SINGLE_DEPTH_NESTING);
> +
> + first_childevt = tmigr_next_groupevt(child);
> + nextexp = child->next_expiry;
> + evt = &child->groupevt;
> + } else {
> + nextexp = data->nextexp;
> +
> + /*
> + * Set @data->nextexp to KTIME_MAX; it is reused for first
> + * global event which needs to be handled by migrator (in
> + * toplevel group)
> + */
> + data->nextexp = KTIME_MAX;
> +
> + first_childevt = evt = data->evt;
> +
> + /*
> + * Walking the hierarchy is required in any case, when a
> + * remote expiry was done before. This ensures to not lost
> + * already queued events in non active groups (see section
> + * "Required event and timerqueue update after remote
> + * expiry" in documentation at the top).
> + */
> + if (evt->ignore && !remote)
> + return true;
> +
> + raw_spin_lock(&group->lock);
> + }
> +
> + if (nextexp == KTIME_MAX) {
> + evt->ignore = 1;
> +
> + /*
> + * When next child event could be ignored (nextexp is
> + * KTIME_MAX) and there was no remote timer handling before
> + * or the group is already active, there is no need to walk
> + * the hierarchy even if there is a parent group.
> + *
> + * The other way round: even if the event could be ignored,
> + * but if a remote timer handling was executed before and
> + * the group is not active, walking the hierarchy is
> + * required to not miss an enqueued timer in the non active
> + * group. The enqueued timer of the group needs to be
> + * propagated to a higher level to ensure it is handled.
> + */
> + if (!remote || data->groupstate.active) {
> + walk_done = true;
> + goto unlock;
> + }
> + } else {
> + /*
> + * Update of event cpu and ignore bit is required only when
> + * @child is set (child is equal or higher than lvl0), but
> + * it doesn't matter if it is written once more to per cpu
> + * event; make the update unconditional.
> + */
> + evt->cpu = first_childevt->cpu;
> + evt->ignore = 0;
> + }
> +
> + walk_done = !group->parent;
> +
> + /*
> + * If child event is already queued in group, remove it from queue
> + * when expiry time changed only.
> + */
> + if (timerqueue_node_queued(&evt->nextevt)) {
> + if (evt->nextevt.expires == nextexp)
> + goto check_toplvl;
> + else if (!timerqueue_del(&group->events, &evt->nextevt))
> + WRITE_ONCE(group->next_expiry, KTIME_MAX);
> + }
> +
> + evt->nextevt.expires = nextexp;
> +
> + if (timerqueue_add(&group->events, &evt->nextevt))
> + WRITE_ONCE(group->next_expiry, nextexp);
> +
> +check_toplvl:
> + if (walk_done && (data->groupstate.migrator == TMIGR_NONE)) {
> + /*
> + * Toplevel group is idle and it has to be ensured global
> + * timers are handled in time. (This could be optimized by
> + * keeping track of the last global scheduled event and
> + * only arming it on CPU if the new event is earlier. Not
> + * sure if its worth the complexity.)
> + */
> + data->nextexp = tmigr_next_groupevt_expires(group);
This looks racy against a concurrent top migrator going idle.
1) Suppose you have the following configuration:
LVL 1 [GRP1:0]
migrator = GRP0:1
active = GRP0:1
nextevt = KTIME_MAX
/ \
LVL 0 [GRP0:0] [GRP0:1]
migrator = NONE migrator = CPU2
active = NONE active = CPU2
nextevt = KTIME_MAX nextevt = KTIME_MAX
/ \ / \
CPUs 0 1 2 3
idle idle active idle
2) Now CPU 2 goes idle and propagates that entirely:
LVL 1 [GRP1:0]
migrator = NONE
active = NONE
nextevt = KTIME_MAX
/ \
LVL 0 [GRP0:0] [GRP0:1]
migrator = NONE migrator = NONE
active = NONE active = NONE
nextevt = KTIME_MAX nextevt = KTIME_MAX
/ \ / \
CPUs 0 1 2 3
idle idle active idle
3) CPU 0 has a new timer queued from idle, it propagates that
to LVL 0, so far so good:
LVL 1 [GRP1:0]
migrator = NONE
active = NONE
nextevt = KTIME_MAX
/ \
LVL 0 [GRP0:0] [GRP0:1]
migrator = NONE migrator = NONE
active = NONE active = NONE
nextevt = TIMER0 nextevt = KTIME_MAX
/ \ / \
CPUs 0 1 2 3
idle idle active idle
4) Finally CPU 0 is about to propagate TIMER0 to LVL1,
so in tmigr_new_timer_up() it reads the state of GRP1:0
but what makes sure it reads the freshest value modified
in step 2 ? There is no locking or cmpxchg() from the reader
side. It's a plain atomic_read(). It may well observe
the stalled value that was in step 1 which has migrator == GRP0:1
and as a result data->nextexp will stay KTIME_MAX and TIMER0 will
be ignored entirely.
As usual I prefer to announce I may be easily missing something that
makes this impossible to happen :)
Otherwise, fortunately there is an easy way to fix this, you need to read the
group state within the group->lock. Because then you have this ordering:
tmigr_inactive_up() tmigr_new_timer_up()
------------------- --------------------
cmpxchg(&group->migr_state, ..., TMIGR_NONE)
tmigr_update_events() {
spin_lock(&group->lock)
//update events ....
spin_unlock(&group->lock) //release migr_state modification
}
tmigr_update_events() {
spin_lock(&group->lock) // acquire migr_state modificaton
group_state = atomic_read(&group->migr_state)
//update events ....
spin_unlock(&group->lock) //makes migr_state visible
}
Everything happening before an UNLOCK (including before the preceding LOCK) is
visible after the next LOCK. So it works. And if tmigr_new_timer_up() runs
while tmigr_inactive_up() is between the group->migr_state modification and
the call to tmigr_update_events(), it's fine as well because it will lock
group->lock and re-evaluate the situation.
I see another check on data->groupstate.active in tmigr_new_timer_up()
when nextexp == KTIME_MAX. From a quick glance it has the same issue and
could be fixed along the same way.
Thanks.
Powered by blists - more mailing lists