diff options
Diffstat (limited to 'kernel/time/timer_migration.c')
| -rw-r--r-- | kernel/time/timer_migration.c | 1773 |
1 files changed, 1773 insertions, 0 deletions
diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c new file mode 100644 index 000000000000..611cd904f035 --- /dev/null +++ b/kernel/time/timer_migration.c @@ -0,0 +1,1773 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * Infrastructure for migratable timers + * + * Copyright(C) 2022 linutronix GmbH + */ +#include <linux/cpuhotplug.h> +#include <linux/slab.h> +#include <linux/smp.h> +#include <linux/spinlock.h> +#include <linux/timerqueue.h> +#include <trace/events/ipi.h> + +#include "timer_migration.h" +#include "tick-internal.h" + +#define CREATE_TRACE_POINTS +#include <trace/events/timer_migration.h> + +/* + * The timer migration mechanism is built on a hierarchy of groups. The + * lowest level group contains CPUs, the next level groups of CPU groups + * and so forth. The CPU groups are kept per node so for the normal case + * lock contention won't happen across nodes. Depending on the number of + * CPUs per node even the next level might be kept as groups of CPU groups + * per node and only the levels above cross the node topology. + * + * Example topology for a two node system with 24 CPUs each. + * + * LVL 2 [GRP2:0] + * GRP1:0 = GRP1:M + * + * LVL 1 [GRP1:0] [GRP1:1] + * GRP0:0 - GRP0:2 GRP0:3 - GRP0:5 + * + * LVL 0 [GRP0:0] [GRP0:1] [GRP0:2] [GRP0:3] [GRP0:4] [GRP0:5] + * CPUS 0-7 8-15 16-23 24-31 32-39 40-47 + * + * The groups hold a timer queue of events sorted by expiry time. These + * queues are updated when CPUs go in idle. When they come out of idle + * ignore flag of events is set. + * + * Each group has a designated migrator CPU/group as long as a CPU/group is + * active in the group. This designated role is necessary to avoid that all + * active CPUs in a group try to migrate expired timers from other CPUs, + * which would result in massive lock bouncing. + * + * When a CPU is awake, it checks in it's own timer tick the group + * hierarchy up to the point where it is assigned the migrator role or if + * no CPU is active, it also checks the groups where no migrator is set + * (TMIGR_NONE). + * + * If it finds expired timers in one of the group queues it pulls them over + * from the idle CPU and runs the timer function. After that it updates the + * group and the parent groups if required. + * + * CPUs which go idle arm their CPU local timer hardware for the next local + * (pinned) timer event. If the next migratable timer expires after the + * next local timer or the CPU has no migratable timer pending then the + * CPU does not queue an event in the LVL0 group. If the next migratable + * timer expires before the next local timer then the CPU queues that timer + * in the LVL0 group. In both cases the CPU marks itself idle in the LVL0 + * group. + * + * When CPU comes out of idle and when a group has at least a single active + * child, the ignore flag of the tmigr_event is set. This indicates, that + * the event is ignored even if it is still enqueued in the parent groups + * timer queue. It will be removed when touching the timer queue the next + * time. This spares locking in active path as the lock protects (after + * setup) only event information. For more information about locking, + * please read the section "Locking rules". + * + * If the CPU is the migrator of the group then it delegates that role to + * the next active CPU in the group or sets migrator to TMIGR_NONE when + * there is no active CPU in the group. This delegation needs to be + * propagated up the hierarchy so hand over from other leaves can happen at + * all hierarchy levels w/o doing a search. + * + * When the last CPU in the system goes idle, then it drops all migrator + * duties up to the top level of the hierarchy (LVL2 in the example). It + * then has to make sure, that it arms it's own local hardware timer for + * the earliest event in the system. + * + * + * Lifetime rules: + * --------------- + * + * The groups are built up at init time or when CPUs come online. They are + * not destroyed when a group becomes empty due to offlining. The group + * just won't participate in the hierarchy management anymore. Destroying + * groups would result in interesting race conditions which would just make + * the whole mechanism slow and complex. + * + * + * Locking rules: + * -------------- + * + * For setting up new groups and handling events it's required to lock both + * child and parent group. The lock ordering is always bottom up. This also + * includes the per CPU locks in struct tmigr_cpu. For updating the migrator and + * active CPU/group information atomic_try_cmpxchg() is used instead and only + * the per CPU tmigr_cpu->lock is held. + * + * During the setup of groups tmigr_level_list is required. It is protected by + * @tmigr_mutex. + * + * When @timer_base->lock as well as tmigr related locks are required, the lock + * ordering is: first @timer_base->lock, afterwards tmigr related locks. + * + * + * Protection of the tmigr group state information: + * ------------------------------------------------ + * + * The state information with the list of active children and migrator needs to + * be protected by a sequence counter. It prevents a race when updates in child + * groups are propagated in changed order. The state update is performed + * lockless and group wise. The following scenario describes what happens + * without updating the sequence counter: + * + * Therefore, let's take three groups and four CPUs (CPU2 and CPU3 as well + * as GRP0:1 will not change during the scenario): + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:0, GRP0:1 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = CPU0 migrator = CPU2 + * active = CPU0 active = CPU2 + * / \ / \ + * CPUs 0 1 2 3 + * active idle active idle + * + * + * 1. CPU0 goes idle. As the update is performed group wise, in the first step + * only GRP0:0 is updated. The update of GRP1:0 is pending as CPU0 has to + * walk the hierarchy. + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:0, GRP0:1 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * --> migrator = TMIGR_NONE migrator = CPU2 + * --> active = active = CPU2 + * / \ / \ + * CPUs 0 1 2 3 + * --> idle idle active idle + * + * 2. While CPU0 goes idle and continues to update the state, CPU1 comes out of + * idle. CPU1 updates GRP0:0. The update for GRP1:0 is pending as CPU1 also + * has to walk the hierarchy. Both CPUs (CPU0 and CPU1) now walk the + * hierarchy to perform the needed update from their point of view. The + * currently visible state looks the following: + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:0, GRP0:1 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * --> migrator = CPU1 migrator = CPU2 + * --> active = CPU1 active = CPU2 + * / \ / \ + * CPUs 0 1 2 3 + * idle --> active active idle + * + * 3. Here is the race condition: CPU1 managed to propagate its changes (from + * step 2) through the hierarchy to GRP1:0 before CPU0 (step 1) did. The + * active members of GRP1:0 remain unchanged after the update since it is + * still valid from CPU1 current point of view: + * + * LVL 1 [GRP1:0] + * --> migrator = GRP0:1 + * --> active = GRP0:0, GRP0:1 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = CPU1 migrator = CPU2 + * active = CPU1 active = CPU2 + * / \ / \ + * CPUs 0 1 2 3 + * idle active active idle + * + * 4. Now CPU0 finally propagates its changes (from step 1) to GRP1:0. + * + * LVL 1 [GRP1:0] + * --> migrator = GRP0:1 + * --> active = GRP0:1 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = CPU1 migrator = CPU2 + * active = CPU1 active = CPU2 + * / \ / \ + * CPUs 0 1 2 3 + * idle active active idle + * + * + * The race of CPU0 vs. CPU1 led to an inconsistent state in GRP1:0. CPU1 is + * active and is correctly listed as active in GRP0:0. However GRP1:0 does not + * have GRP0:0 listed as active, which is wrong. The sequence counter has been + * added to avoid inconsistent states during updates. The state is updated + * atomically only if all members, including the sequence counter, match the + * expected value (compare-and-exchange). + * + * Looking back at the previous example with the addition of the sequence + * counter: The update as performed by CPU0 in step 4 will fail. CPU1 changed + * the sequence number during the update in step 3 so the expected old value (as + * seen by CPU0 before starting the walk) does not match. + * + * Prevent race between new event and last CPU going inactive + * ---------------------------------------------------------- + * + * When the last CPU is going idle and there is a concurrent update of a new + * first global timer of an idle CPU, the group and child states have to be read + * while holding the lock in tmigr_update_events(). The following scenario shows + * what happens, when this is not done. + * + * 1. Only CPU2 is active: + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:1 + * next_expiry = KTIME_MAX + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = CPU2 + * active = active = CPU2 + * next_expiry = KTIME_MAX next_expiry = KTIME_MAX + * / \ / \ + * CPUs 0 1 2 3 + * idle idle active idle + * + * 2. Now CPU 2 goes idle (and has no global timer, that has to be handled) and + * propagates that to GRP0:1: + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:1 + * next_expiry = KTIME_MAX + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE --> migrator = TMIGR_NONE + * active = --> active = + * next_expiry = KTIME_MAX next_expiry = KTIME_MAX + * / \ / \ + * CPUs 0 1 2 3 + * idle idle --> idle idle + * + * 3. Now the idle state is propagated up to GRP1:0. As this is now the last + * child going idle in top level group, the expiry of the next group event + * has to be handed back to make sure no event is lost. As there is no event + * enqueued, KTIME_MAX is handed back to CPU2. + * + * LVL 1 [GRP1:0] + * --> migrator = TMIGR_NONE + * --> active = + * next_expiry = KTIME_MAX + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = TMIGR_NONE + * active = active = + * next_expiry = KTIME_MAX next_expiry = KTIME_MAX + * / \ / \ + * CPUs 0 1 2 3 + * idle idle --> idle idle + * + * 4. CPU 0 has a new timer queued from idle and it expires at TIMER0. CPU0 + * propagates that to GRP0:0: + * + * LVL 1 [GRP1:0] + * migrator = TMIGR_NONE + * active = + * next_expiry = KTIME_MAX + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = TMIGR_NONE + * active = active = + * --> next_expiry = TIMER0 next_expiry = KTIME_MAX + * / \ / \ + * CPUs 0 1 2 3 + * idle idle idle idle + * + * 5. GRP0:0 is not active, so the new timer has to be propagated to + * GRP1:0. Therefore the GRP1:0 state has to be read. When the stalled value + * (from step 2) is read, the timer is enqueued into GRP1:0, but nothing is + * handed back to CPU0, as it seems that there is still an active child in + * top level group. + * + * LVL 1 [GRP1:0] + * migrator = TMIGR_NONE + * active = + * --> next_expiry = TIMER0 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = TMIGR_NONE + * active = active = + * next_expiry = TIMER0 next_expiry = KTIME_MAX + * / \ / \ + * CPUs 0 1 2 3 + * idle idle idle idle + * + * This is prevented by reading the state when holding the lock (when a new + * timer has to be propagated from idle path):: + * + * CPU2 (tmigr_inactive_up()) CPU0 (tmigr_new_timer_up()) + * -------------------------- --------------------------- + * // step 3: + * cmpxchg(&GRP1:0->state); + * tmigr_update_events() { + * spin_lock(&GRP1:0->lock); + * // ... update events ... + * // hand back first expiry when GRP1:0 is idle + * spin_unlock(&GRP1:0->lock); + * // ^^^ release state modification + * } + * tmigr_update_events() { + * spin_lock(&GRP1:0->lock) + * // ^^^ acquire state modification + * group_state = atomic_read(&GRP1:0->state) + * // .... update events ... + * // hand back first expiry when GRP1:0 is idle + * spin_unlock(&GRP1:0->lock) <3> + * // ^^^ makes state visible for other + * // callers of tmigr_new_timer_up() + * } + * + * When CPU0 grabs the lock directly after cmpxchg, the first timer is reported + * back to CPU0 and also later on to CPU2. So no timer is missed. A concurrent + * update of the group state from active path is no problem, as the upcoming CPU + * will take care of the group events. + * + * Required event and timerqueue update after a remote expiry: + * ----------------------------------------------------------- + * + * After expiring timers of a remote CPU, a walk through the hierarchy and + * update of events and timerqueues is required. It is obviously needed if there + * is a 'new' global timer but also if there is no new global timer but the + * remote CPU is still idle. + * + * 1. CPU0 and CPU1 are idle and have both a global timer expiring at the same + * time. So both have an event enqueued in the timerqueue of GRP0:0. CPU3 is + * also idle and has no global timer pending. CPU2 is the only active CPU and + * thus also the migrator: + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:1 + * --> timerqueue = evt-GRP0:0 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = CPU2 + * active = active = CPU2 + * groupevt.ignore = false groupevt.ignore = true + * groupevt.cpu = CPU0 groupevt.cpu = + * timerqueue = evt-CPU0, timerqueue = + * evt-CPU1 + * / \ / \ + * CPUs 0 1 2 3 + * idle idle active idle + * + * 2. CPU2 starts to expire remote timers. It starts with LVL0 group + * GRP0:1. There is no event queued in the timerqueue, so CPU2 continues with + * the parent of GRP0:1: GRP1:0. In GRP1:0 it dequeues the first event. It + * looks at tmigr_event::cpu struct member and expires the pending timer(s) + * of CPU0. + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:1 + * --> timerqueue = + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = CPU2 + * active = active = CPU2 + * groupevt.ignore = false groupevt.ignore = true + * --> groupevt.cpu = CPU0 groupevt.cpu = + * timerqueue = evt-CPU0, timerqueue = + * evt-CPU1 + * / \ / \ + * CPUs 0 1 2 3 + * idle idle active idle + * + * 3. Some work has to be done after expiring the timers of CPU0. If we stop + * here, then CPU1's pending global timer(s) will not expire in time and the + * timerqueue of GRP0:0 has still an event for CPU0 enqueued which has just + * been processed. So it is required to walk the hierarchy from CPU0's point + * of view and update it accordingly. CPU0's event will be removed from the + * timerqueue because it has no pending timer. If CPU0 would have a timer + * pending then it has to expire after CPU1's first timer because all timers + * from this period were just expired. Either way CPU1's event will be first + * in GRP0:0's timerqueue and therefore set in the CPU field of the group + * event which is then enqueued in GRP1:0's timerqueue as GRP0:0 is still not + * active: + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:1 + * --> timerqueue = evt-GRP0:0 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = CPU2 + * active = active = CPU2 + * groupevt.ignore = false groupevt.ignore = true + * --> groupevt.cpu = CPU1 groupevt.cpu = + * --> timerqueue = evt-CPU1 timerqueue = + * / \ / \ + * CPUs 0 1 2 3 + * idle idle active idle + * + * Now CPU2 (migrator) will continue step 2 at GRP1:0 and will expire the + * timer(s) of CPU1. + * + * The hierarchy walk in step 3 can be skipped if the migrator notices that a + * CPU of GRP0:0 is active again. The CPU will mark GRP0:0 active and take care + * of the group as migrator and any needed updates within the hierarchy. + */ + +static DEFINE_MUTEX(tmigr_mutex); +static struct list_head *tmigr_level_list __read_mostly; + +static unsigned int tmigr_hierarchy_levels __read_mostly; +static unsigned int tmigr_crossnode_level __read_mostly; + +static DEFINE_PER_CPU(struct tmigr_cpu, tmigr_cpu); + +#define TMIGR_NONE 0xFF +#define BIT_CNT 8 + +static inline bool tmigr_is_not_available(struct tmigr_cpu *tmc) +{ + return !(tmc->tmgroup && tmc->online); +} + +/* + * Returns true, when @childmask corresponds to the group migrator or when the + * group is not active - so no migrator is set. + */ +static bool tmigr_check_migrator(struct tmigr_group *group, u8 childmask) +{ + union tmigr_state s; + + s.state = atomic_read(&group->migr_state); + + if ((s.migrator == childmask) || (s.migrator == TMIGR_NONE)) + return true; + + return false; +} + +static bool tmigr_check_migrator_and_lonely(struct tmigr_group *group, u8 childmask) +{ + bool lonely, migrator = false; + unsigned long active; + union tmigr_state s; + + s.state = atomic_read(&group->migr_state); + + if ((s.migrator == childmask) || (s.migrator == TMIGR_NONE)) + migrator = true; + + active = s.active; + lonely = bitmap_weight(&active, BIT_CNT) <= 1; + + return (migrator && lonely); +} + +static bool tmigr_check_lonely(struct tmigr_group *group) +{ + unsigned long active; + union tmigr_state s; + + s.state = atomic_read(&group->migr_state); + + active = s.active; + + return bitmap_weight(&active, BIT_CNT) <= 1; +} + +typedef bool (*up_f)(struct tmigr_group *, struct tmigr_group *, void *); + +static void __walk_groups(up_f up, void *data, + struct tmigr_cpu *tmc) +{ + struct tmigr_group *child = NULL, *group = tmc->tmgroup; + + do { + WARN_ON_ONCE(group->level >= tmigr_hierarchy_levels); + + if (up(group, child, data)) + break; + + child = group; + group = group->parent; + } while (group); +} + +static void walk_groups(up_f up, void *data, struct tmigr_cpu *tmc) +{ + lockdep_assert_held(&tmc->lock); + + __walk_groups(up, data, tmc); +} + +/** + * struct tmigr_walk - data required for walking the hierarchy + * @nextexp: Next CPU event expiry information which is handed into + * the timer migration code by the timer code + * (get_next_timer_interrupt()) + * @firstexp: Contains the first event expiry information when last + * active CPU of hierarchy is on the way to idle to make + * sure CPU will be back in time. + * @evt: Pointer to tmigr_event which needs to be queued (of idle + * child group) + * @childmask: childmask of child group + * @remote: Is set, when the new timer path is executed in + * tmigr_handle_remote_cpu() + */ +struct tmigr_walk { + u64 nextexp; + u64 firstexp; + struct tmigr_event *evt; + u8 childmask; + bool remote; +}; + +/** + * struct tmigr_remote_data - data required for remote expiry hierarchy walk + * @basej: timer base in jiffies + * @now: timer base monotonic + * @firstexp: returns expiry of the first timer in the idle timer + * migration hierarchy to make sure the timer is handled in + * time; it is stored in the per CPU tmigr_cpu struct of + * CPU which expires remote timers + * @childmask: childmask of child group + * @check: is set if there is the need to handle remote timers; + * required in tmigr_requires_handle_remote() only + * @tmc_active: this flag indicates, whether the CPU which triggers + * the hierarchy walk is !idle in the timer migration + * hierarchy. When the CPU is idle and the whole hierarchy is + * idle, only the first event of the top level has to be + * considered. + */ +struct tmigr_remote_data { + unsigned long basej; + u64 now; + u64 firstexp; + u8 childmask; + bool check; + bool tmc_active; +}; + +/* + * Returns the next event of the timerqueue @group->events + * + * Removes timers with ignore flag and update next_expiry of the group. Values + * of the group event are updated in tmigr_update_events() only. + */ +static struct tmigr_event *tmigr_next_groupevt(struct tmigr_group *group) +{ + struct timerqueue_node *node = NULL; + struct tmigr_event *evt = NULL; + + lockdep_assert_held(&group->lock); + + WRITE_ONCE(group->next_expiry, KTIME_MAX); + + while ((node = timerqueue_getnext(&group->events))) { + evt = container_of(node, struct tmigr_event, nextevt); + + if (!evt->ignore) { + WRITE_ONCE(group->next_expiry, evt->nextevt.expires); + return evt; + } + + /* + * Remove next timers with ignore flag, because the group lock + * is held anyway + */ + if (!timerqueue_del(&group->events, node)) + break; + } + + return NULL; +} + +/* + * Return the next event (with the expiry equal or before @now) + * + * Event, which is returned, is also removed from the queue. + */ +static struct tmigr_event *tmigr_next_expired_groupevt(struct tmigr_group *group, + u64 now) +{ + struct tmigr_event *evt = tmigr_next_groupevt(group); + + if (!evt || now < evt->nextevt.expires) + return NULL; + + /* + * The event is ready to expire. Remove it and update next group event. + */ + timerqueue_del(&group->events, &evt->nextevt); + tmigr_next_groupevt(group); + + return evt; +} + +static u64 tmigr_next_groupevt_expires(struct tmigr_group *group) +{ + struct tmigr_event *evt; + + evt = tmigr_next_groupevt(group); + + if (!evt) + return KTIME_MAX; + else + return evt->nextevt.expires; +} + +static bool tmigr_active_up(struct tmigr_group *group, + struct tmigr_group *child, + void *ptr) +{ + union tmigr_state curstate, newstate; + struct tmigr_walk *data = ptr; + bool walk_done; + u8 childmask; + + childmask = data->childmask; + /* + * No memory barrier is required here in contrast to + * tmigr_inactive_up(), as the group state change does not depend on the + * child state. + */ + curstate.state = atomic_read(&group->migr_state); + + do { + newstate = curstate; + walk_done = true; + + if (newstate.migrator == TMIGR_NONE) { + newstate.migrator = childmask; + + /* Changes need to be propagated */ + walk_done = false; + } + + newstate.active |= childmask; + newstate.seq++; + + } while (!atomic_try_cmpxchg(&group->migr_state, &curstate.state, newstate.state)); + + if ((walk_done == false) && group->parent) + data->childmask = group->childmask; + + /* + * The group is active (again). The group event might be still queued + * into the parent group's timerqueue but can now be handled by the + * migrator of this group. Therefore the ignore flag for the group event + * is updated to reflect this. + * + * The update of the ignore flag in the active path is done lockless. In + * worst case the migrator of the parent group observes the change too + * late and expires remotely all events belonging to this group. The + * lock is held while updating the ignore flag in idle path. So this + * state change will not be lost. + */ + group->groupevt.ignore = true; + + trace_tmigr_group_set_cpu_active(group, newstate, childmask); + + return walk_done; +} + +static void __tmigr_cpu_activate(struct tmigr_cpu *tmc) +{ + struct tmigr_walk data; + + data.childmask = tmc->childmask; + + trace_tmigr_cpu_active(tmc); + + tmc->cpuevt.ignore = true; + WRITE_ONCE(tmc->wakeup, KTIME_MAX); + + walk_groups(&tmigr_active_up, &data, tmc); +} + +/** + * tmigr_cpu_activate() - set this CPU active in timer migration hierarchy + * + * Call site timer_clear_idle() is called with interrupts disabled. + */ +void tmigr_cpu_activate(void) +{ + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + + if (tmigr_is_not_available(tmc)) + return; + + if (WARN_ON_ONCE(!tmc->idle)) + return; + + raw_spin_lock(&tmc->lock); + tmc->idle = false; + __tmigr_cpu_activate(tmc); + raw_spin_unlock(&tmc->lock); +} + +/* + * Returns true, if there is nothing to be propagated to the next level + * + * @data->firstexp is set to expiry of first gobal event of the (top level of + * the) hierarchy, but only when hierarchy is completely idle. + * + * The child and group states need to be read under the lock, to prevent a race + * against a concurrent tmigr_inactive_up() run when the last CPU goes idle. See + * also section "Prevent race between new event and last CPU going inactive" in + * the documentation at the top. + * + * This is the only place where the group event expiry value is set. + */ +static +bool tmigr_update_events(struct tmigr_group *group, struct tmigr_group *child, + struct tmigr_walk *data) +{ + struct tmigr_event *evt, *first_childevt; + union tmigr_state childstate, groupstate; + bool remote = data->remote; + bool walk_done = false; + u64 nextexp; + + if (child) { + raw_spin_lock(&child->lock); + raw_spin_lock_nested(&group->lock, SINGLE_DEPTH_NESTING); + + childstate.state = atomic_read(&child->migr_state); + groupstate.state = atomic_read(&group->migr_state); + + if (childstate.active) { + walk_done = true; + goto unlock; + } + + first_childevt = tmigr_next_groupevt(child); + nextexp = child->next_expiry; + evt = &child->groupevt; + + evt->ignore = (nextexp == KTIME_MAX) ? true : false; + } else { + nextexp = data->nextexp; + + first_childevt = evt = data->evt; + + raw_spin_lock(&group->lock); + + childstate.state = 0; + groupstate.state = atomic_read(&group->migr_state); + } + + /* + * If the child event is already queued in the group, remove it from the + * queue when the expiry time changed only or when it could be ignored. + */ + if (timerqueue_node_queued(&evt->nextevt)) { + if ((evt->nextevt.expires == nextexp) && !evt->ignore) + goto check_toplvl; + + if (!timerqueue_del(&group->events, &evt->nextevt)) + WRITE_ONCE(group->next_expiry, KTIME_MAX); + } + + if (evt->ignore) { + /* + * When the 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 || groupstate.active) + walk_done = true; + } else { + evt->nextevt.expires = nextexp; + evt->cpu = first_childevt->cpu; + + if (timerqueue_add(&group->events, &evt->nextevt)) + WRITE_ONCE(group->next_expiry, nextexp); + } + +check_toplvl: + if (!group->parent && (groupstate.migrator == TMIGR_NONE)) { + walk_done = true; + + /* + * Nothing to do when update was done during remote timer + * handling. First timer in top level group which needs to be + * handled when top level group is not active, is calculated + * directly in tmigr_handle_remote_up(). + */ + if (remote) + goto unlock; + + /* + * The top level group is idle and it has to be ensured the + * global timers are handled in time. (This could be optimized + * by keeping track of the last global scheduled event and only + * arming it on the CPU if the new event is earlier. Not sure if + * its worth the complexity.) + */ + data->firstexp = tmigr_next_groupevt_expires(group); + } + + trace_tmigr_update_events(child, group, childstate, groupstate, + nextexp); + +unlock: + raw_spin_unlock(&group->lock); + + if (child) + raw_spin_unlock(&child->lock); + + return walk_done; +} + +static bool tmigr_new_timer_up(struct tmigr_group *group, + struct tmigr_group *child, + void *ptr) +{ + struct tmigr_walk *data = ptr; + + return tmigr_update_events(group, child, data); +} + +/* + * Returns the expiry of the next timer that needs to be handled. KTIME_MAX is + * returned, if an active CPU will handle all the timer migration hierarchy + * timers. + */ +static u64 tmigr_new_timer(struct tmigr_cpu *tmc, u64 nextexp) +{ + struct tmigr_walk data = { .nextexp = nextexp, + .firstexp = KTIME_MAX, + .evt = &tmc->cpuevt }; + + lockdep_assert_held(&tmc->lock); + + if (tmc->remote) + return KTIME_MAX; + + trace_tmigr_cpu_new_timer(tmc); + + tmc->cpuevt.ignore = false; + data.remote = false; + + walk_groups(&tmigr_new_timer_up, &data, tmc); + + /* If there is a new first global event, make sure it is handled */ + return data.firstexp; +} + +static void tmigr_handle_remote_cpu(unsigned int cpu, u64 now, + unsigned long jif) +{ + struct timer_events tevt; + struct tmigr_walk data; + struct tmigr_cpu *tmc; + + tmc = per_cpu_ptr(&tmigr_cpu, cpu); + + raw_spin_lock_irq(&tmc->lock); + + /* + * If the remote CPU is offline then the timers have been migrated to + * another CPU. + * + * If tmigr_cpu::remote is set, at the moment another CPU already + * expires the timers of the remote CPU. + * + * If tmigr_event::ignore is set, then the CPU returns from idle and + * takes care of its timers. + * + * If the next event expires in the future, then the event has been + * updated and there are no timers to expire right now. The CPU which + * updated the event takes care when hierarchy is completely + * idle. Otherwise the migrator does it as the event is enqueued. + */ + if (!tmc->online || tmc->remote || tmc->cpuevt.ignore || + now < tmc->cpuevt.nextevt.expires) { + raw_spin_unlock_irq(&tmc->lock); + return; + } + + trace_tmigr_handle_remote_cpu(tmc); + + tmc->remote = true; + WRITE_ONCE(tmc->wakeup, KTIME_MAX); + + /* Drop the lock to allow the remote CPU to exit idle */ + raw_spin_unlock_irq(&tmc->lock); + + if (cpu != smp_processor_id()) + timer_expire_remote(cpu); + + /* + * Lock ordering needs to be preserved - timer_base locks before tmigr + * related locks (see section "Locking rules" in the documentation at + * the top). During fetching the next timer interrupt, also tmc->lock + * needs to be held. Otherwise there is a possible race window against + * the CPU itself when it comes out of idle, updates the first timer in + * the hierarchy and goes back to idle. + * + * timer base locks are dropped as fast as possible: After checking + * whether the remote CPU went offline in the meantime and after + * fetching the next remote timer interrupt. Dropping the locks as fast + * as possible keeps the locking region small and prevents holding + * several (unnecessary) locks during walking the hierarchy for updating + * the timerqueue and group events. + */ + local_irq_disable(); + timer_lock_remote_bases(cpu); + raw_spin_lock(&tmc->lock); + + /* + * When the CPU went offline in the meantime, no hierarchy walk has to + * be done for updating the queued events, because the walk was + * already done during marking the CPU offline in the hierarchy. + * + * When the CPU is no longer idle, the CPU takes care of the timers and + * also of the timers in the hierarchy. + * + * (See also section "Required event and timerqueue update after a + * remote expiry" in the documentation at the top) + */ + if (!tmc->online || !tmc->idle) { + timer_unlock_remote_bases(cpu); + goto unlock; + } + + /* next event of CPU */ + fetch_next_timer_interrupt_remote(jif, now, &tevt, cpu); + timer_unlock_remote_bases(cpu); + + data.nextexp = tevt.global; + data.firstexp = KTIME_MAX; + data.evt = &tmc->cpuevt; + data.remote = true; + + /* + * The update is done even when there is no 'new' global timer pending + * on the remote CPU (see section "Required event and timerqueue update + * after a remote expiry" in the documentation at the top) + */ + walk_groups(&tmigr_new_timer_up, &data, tmc); + +unlock: + tmc->remote = false; + raw_spin_unlock_irq(&tmc->lock); +} + +static bool tmigr_handle_remote_up(struct tmigr_group *group, + struct tmigr_group *child, + void *ptr) +{ + struct tmigr_remote_data *data = ptr; + struct tmigr_event *evt; + unsigned long jif; + u8 childmask; + u64 now; + + jif = data->basej; + now = data->now; + + childmask = data->childmask; + + trace_tmigr_handle_remote(group); +again: + /* + * Handle the group only if @childmask is the migrator or if the + * group has no migrator. Otherwise the gro |