// 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;} /** * 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 * hierarchy is completely idle. When CPU itself was the * last going idle, information makes sure, that CPU will * be back in time. When using this value in the remote * expiry case, firstexp is stored in the per CPU tmigr_cpu * struct of CPU which expires remote timers. It is updated * in top level group only. Be aware, there could occur a * new top level of the hierarchy between the 'top level * call' in tmigr_update_events() and the check for the * parent group in walk_groups(). Then @firstexp might * contain a value != KTIME_MAX even if it was not the * final top level. This is not a problem, as the worst * outcome is a CPU which might wake up a little early. * @evt: Pointer to tmigr_event which needs to be queued (of idle * child group) * @childmask: groupmask of child group * @remote: Is set, when the new timer path is executed in * tmigr_handle_remote_cpu()Lines 1–500 of 1855. Load more
// 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; } /** * 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 * hierarchy is completely idle. When CPU itself was the * last going idle, information makes sure, that CPU will * be back in time. When using this value in the remote * expiry case, firstexp is stored in the per CPU tmigr_cpu * struct of CPU which expires remote timers. It is updated * in top level group only. Be aware, there could occur a * new top level of the hierarchy between the 'top level * call' in tmigr_update_events() and the check for the * parent group in walk_groups(). Then @firstexp might * contain a value != KTIME_MAX even if it was not the * final top level. This is not a problem, as the worst * outcome is a CPU which might wake up a little early. * @evt: Pointer to tmigr_event which needs to be queued (of idle * child group) * @childmask: groupmask of child group * @remote: Is set, when the new timer path is executed in * tmigr_handle_remote_cpu()