Messages in this thread | | | Date | Tue, 13 Jun 2023 12:51:59 +0200 | From | Frederic Weisbecker <> | 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.
| |