[v5,16/18] timer: Implement the hierarchical pull model

  Placing timers at enqueue time on a target CPU based on dubious heuristics
does not make any sense:

 1) Most timer wheel timers are canceled or rearmed before they expire.

 2) The heuristics to predict which CPU will be busy when the timer expires
    are wrong by definition.

So placing the timers at enqueue wastes precious cycles.

The proper solution to this problem is to always queue the timers on the
local CPU and allow the non pinned timers to be pulled onto a busy CPU at
expiry time.

Therefore split the timer storage into local pinned and global timers:
Local pinned timers are always expired on the CPU on which they have been
queued. Global timers can be expired on any CPU.

As long as a CPU is busy it expires both local and global timers. When a
CPU goes idle it arms for the first expiring local timer. If the first
expiring pinned (local) timer is before the first expiring movable timer,
then no action is required because the CPU will wake up before the first
movable timer expires. If the first expiring movable timer is before the
first expiring pinned (local) timer, then this timer is queued into a idle
timerqueue and eventually expired by some other active CPU.

To avoid global locking the timerqueues are implemented as a hierarchy. The
lowest level of the hierarchy holds the CPUs. The CPUs are associated to
groups of 8, which are seperated per node. If more than one CPU group
exist, then a second level in the hierarchy collects the groups. Depending
on the size of the system more than 2 levels are required. Each group has a
"migrator" which checks the timerqueue during the tick for remote expirable
timers.

If the last CPU in a group goes idle it reports the first expiring event in
the group up to the next group(s) in the hierarchy. If the last CPU goes
idle it arms its timer for the first system wide expiring timer to ensure
that no timer event is missed.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
v5:
  - Review remarks of Frederic
  - Return nextevt when CPU is marked offline in timer migration hierarchy
    instead of KTIME_MAX
  - Fix update of group events issue, after remote expiring

v4:
  - Fold typo fix in comment into proper patch "timer: Split out "get next
    timer interrupt" functionality"
  - Update wrong comment for tmigr_state union definition
  - Fix fallout of kernel test robot
---
 include/linux/cpuhotplug.h    |    1 +
 kernel/time/Makefile          |    3 +
 kernel/time/timer.c           |   67 +-
 kernel/time/timer_migration.c | 1255 +++++++++++++++++++++++++++++++++
 kernel/time/timer_migration.h |  123 ++++
 5 files changed, 1441 insertions(+), 8 deletions(-)
 create mode 100644 kernel/time/timer_migration.c
 create mode 100644 kernel/time/timer_migration.h
  

Le Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen a écrit :
> diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c
> new file mode 100644
> index 000000000000..5a600de3623b
> --- /dev/null
> +++ b/kernel/time/timer_migration.c
> +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;
> +	u32 childmask;
> +
> +	childmask = data->childmask;
> +	newstate = curstate = data->groupstate;
> +
> +retry:
> +	walk_done = true;
> +
> +	if (newstate.migrator == TMIGR_NONE) {
> +		newstate.migrator = (u8)childmask;
> +
> +		/* Changes need to be propagated */
> +		walk_done = false;
> +	}
> +
> +	newstate.active |= (u8)childmask;
> +
> +	newstate.seq++;

Are you sure you need this seq counter? What bad scenario can happen without it?

Thanks.
>
  

On Tue, 14 Mar 2023, Frederic Weisbecker wrote:

> Le Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen a écrit :
> > diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c
> > new file mode 100644
> > index 000000000000..5a600de3623b
> > --- /dev/null
> > +++ b/kernel/time/timer_migration.c
> > +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;
> > +	u32 childmask;
> > +
> > +	childmask = data->childmask;
> > +	newstate = curstate = data->groupstate;
> > +
> > +retry:
> > +	walk_done = true;
> > +
> > +	if (newstate.migrator == TMIGR_NONE) {
> > +		newstate.migrator = (u8)childmask;
> > +
> > +		/* Changes need to be propagated */
> > +		walk_done = false;
> > +	}
> > +
> > +	newstate.active |= (u8)childmask;
> > +
> > +	newstate.seq++;
> 
> Are you sure you need this seq counter? What bad scenario can happen without it?
> 

Without the seq counter we might get an inconsistent overall state of the
groups when the order of propagating two changes of the child to the parent
changes. To clarify what I mean, let me give you an example what happens
without seqcount (maybe this should be described more detailed in the union
tmigr_state description...).

Let's take three groups and four CPUs (CPU2 and CPU3 as well as Group C
will not change during the scenario):

   	      	  Group A
		  migrator = Group B
		  active = Group B, Group C
	       /             \
    Group B			Group C
    migrator = CPU0		migrator = CPU2
    active = CPU0		active = CPU2
     /    \ 			 /  \
   CPU0   CPU1	 	      CPU2  CPU3
  active  idle               active idle


1. CPU0 goes idle (changes are updated in Group B; afterwards current
states of Group B and Group A are stored in the data for walking the
hierarchy):

   	      	  Group A
		  migrator = Group B
		  active = Group B, Group C
	       /             \
    Group B			Group C
->  migrator = TMIGR_NONE	migrator = CPU2
->  active =    		active = CPU2
     /    \ 			 /  \
   CPU0   CPU1	 	      CPU2  CPU3
-> idle   idle               active idle


2. CPU1 comes out of idle (changes are update in Group B; afterwards
current states of Group B and Group A are stored in the data for walking
the hierarchy):

   	      	  Group A
		  migrator = Group B
		  active = Group B, Group C
	       /             \
    Group B			Group C
->  migrator = CPU1		migrator = CPU2
->  active = CPU1   		active = CPU2
     /    \ 			 /  \
   CPU0   CPU1	 	      CPU2  CPU3
   idle -> active            active idle


3. Here comes the change of the order: Propagating the changes of
   2. through the hierarchy to group A - nothing to be done, because Group
   B is already up to date.

4. Propagating the changes of 1. through the hierarchy to group A:

   	      	  Group A
	      ->  migrator = Group C
	      ->  active =  Group C
	       /             \
    Group B			Group C
    migrator = CPU1		migrator = CPU2
    active = CPU1   		active = CPU2
     /    \ 			 /  \
   CPU0   CPU1	 	      CPU2  CPU3
   idle  active              active idle

And now we have this inconsistent overall state...

Thanks,

	Anna-Maria
  

Le Tue, Mar 14, 2023 at 03:49:38PM +0100, Anna-Maria Behnsen a écrit :
> On Tue, 14 Mar 2023, Frederic Weisbecker wrote:
> 
> > Le Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen a écrit :
> > > diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c
> > > new file mode 100644
> > > index 000000000000..5a600de3623b
> > > --- /dev/null
> > > +++ b/kernel/time/timer_migration.c
> > > +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;
> > > +	u32 childmask;
> > > +
> > > +	childmask = data->childmask;
> > > +	newstate = curstate = data->groupstate;
> > > +
> > > +retry:
> > > +	walk_done = true;
> > > +
> > > +	if (newstate.migrator == TMIGR_NONE) {
> > > +		newstate.migrator = (u8)childmask;
> > > +
> > > +		/* Changes need to be propagated */
> > > +		walk_done = false;
> > > +	}
> > > +
> > > +	newstate.active |= (u8)childmask;
> > > +
> > > +	newstate.seq++;
> > 
> > Are you sure you need this seq counter? What bad scenario can happen without it?
> > 
> 
> Without the seq counter we might get an inconsistent overall state of the
> groups when the order of propagating two changes of the child to the parent
> changes. To clarify what I mean, let me give you an example what happens
> without seqcount (maybe this should be described more detailed in the union
> tmigr_state description...).
> 
> Let's take three groups and four CPUs (CPU2 and CPU3 as well as Group C
> will not change during the scenario):
> 
>    	      	  Group A
> 		  migrator = Group B
> 		  active = Group B, Group C
> 	       /             \
>     Group B			Group C
>     migrator = CPU0		migrator = CPU2
>     active = CPU0		active = CPU2
>      /    \ 			 /  \
>    CPU0   CPU1	 	      CPU2  CPU3
>   active  idle               active idle
> 
> 
> 1. CPU0 goes idle (changes are updated in Group B; afterwards current
> states of Group B and Group A are stored in the data for walking the
> hierarchy):
> 
>    	      	  Group A
> 		  migrator = Group B
> 		  active = Group B, Group C
> 	       /             \
>     Group B			Group C
> ->  migrator = TMIGR_NONE	migrator = CPU2
> ->  active =    		active = CPU2
>      /    \ 			 /  \
>    CPU0   CPU1	 	      CPU2  CPU3
> -> idle   idle               active idle
> 
> 
> 2. CPU1 comes out of idle (changes are update in Group B; afterwards
> current states of Group B and Group A are stored in the data for walking
> the hierarchy):
> 
>    	      	  Group A
> 		  migrator = Group B
> 		  active = Group B, Group C
> 	       /             \
>     Group B			Group C
> ->  migrator = CPU1		migrator = CPU2
> ->  active = CPU1   		active = CPU2
>      /    \ 			 /  \
>    CPU0   CPU1	 	      CPU2  CPU3
>    idle -> active            active idle
> 
> 
> 3. Here comes the change of the order: Propagating the changes of
>    2. through the hierarchy to group A - nothing to be done, because Group
>    B is already up to date.
> 
> 4. Propagating the changes of 1. through the hierarchy to group A:
> 
>    	      	  Group A
> 	      ->  migrator = Group C
> 	      ->  active =  Group C
> 	       /             \
>     Group B			Group C
>     migrator = CPU1		migrator = CPU2
>     active = CPU1   		active = CPU2
>      /    \ 			 /  \
>    CPU0   CPU1	 	      CPU2  CPU3
>    idle  active              active idle
> 
> And now we have this inconsistent overall state..

Ooh I see now. Also that can't ever wrap up since you can only ever have no more than 8 racers
competing on a given node.

Tricky ;)
  

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +static u64 tmigr_handle_remote_cpu(unsigned int cpu, u64 now,
> +				   unsigned long jif)
> +{
> +	struct timer_events tevt;
> +	struct tmigr_walk data;
> +	struct tmigr_cpu *tmc;
> +	u64 next = KTIME_MAX;
> +	unsigned long flags;
> +
> +	tmc = per_cpu_ptr(&tmigr_cpu, cpu);
> +
> +	raw_spin_lock_irqsave(&tmc->lock, flags);
> +	/*
> +	 * Remote CPU is offline or no longer idle or other cpu handles cpu
> +	 * timers already or next event was already expired - return!
> +	 */
> +	if (!tmc->online || tmc->remote || tmc->cpuevt.ignore ||
> +	    now < tmc->cpuevt.nextevt.expires) {
> +		raw_spin_unlock_irqrestore(&tmc->lock, flags);
> +		return next;
> +	}
> +
> +	tmc->remote = 1;
> +
> +	/* Drop the lock to allow the remote CPU to exit idle */
> +	raw_spin_unlock_irqrestore(&tmc->lock, flags);
> +
> +	if (cpu != smp_processor_id())
> +		timer_expire_remote(cpu);
> +
> +	/* next event of cpu */
> +	fetch_next_timer_interrupt_remote(jif, now, &tevt, cpu);

If the target CPU gets an idle interrupt right after the above call and enqueues
a new timer (which becomes the new earliest), tmigr_cpu_deactivate() ->
tmigr_new_timer() is going to ignore it due to tmc->remote = 1, right?

Or am I missing something else that would make that timer correctly handled?

Thanks.
  

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +static bool tmigr_inactive_up(struct tmigr_group *group,
> +			      struct tmigr_group *child,
> +			      void *ptr)
> +{
> +	union tmigr_state curstate, newstate;
> +	struct tmigr_walk *data = ptr;
> +	bool walk_done;
> +	u32 childmask;
> +
> +	childmask = data->childmask;
> +	newstate = curstate = data->groupstate;
> +
> +retry:
> +	walk_done = true;
> +
> +	/* Reset active bit when child is no longer active */
> +	if (!data->childstate.active)
> +		newstate.active &= ~(u8)childmask;
> +
> +	if (newstate.migrator == (u8)childmask) {
> +		/*
> +		 * Find a new migrator for the group, because child group
> +		 * is idle!
> +		 */
> +		if (!data->childstate.active) {
> +			unsigned long new_migr_bit, active = newstate.active;
> +
> +			new_migr_bit = find_first_bit(&active, BIT_CNT);
> +
> +			/* Changes need to be propagated */
> +			walk_done = false;

Do you need to propagate the changes even if you found a new migrator for the
group?

> +
> +			if (new_migr_bit != BIT_CNT)
> +				newstate.migrator = BIT(new_migr_bit);
> +			else
> +				newstate.migrator = TMIGR_NONE;

Thanks.
  

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +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;
> +	u32 childmask;
> +
> +	childmask = data->childmask;
> +	newstate = curstate = data->groupstate;
> +
> +retry:
> +	walk_done = true;
> +
> +	if (newstate.migrator == TMIGR_NONE) {
> +		newstate.migrator = (u8)childmask;
> +
> +		/* Changes need to be propagated */
> +		walk_done = false;
> +	}
> +
> +	newstate.active |= (u8)childmask;
> +
> +	newstate.seq++;
> +
> +	if (atomic_cmpxchg(group->migr_state, curstate.state, newstate.state) != curstate.state) {
> +		newstate.state = curstate.state = atomic_read(group->migr_state);
> +		goto retry;
> +	}

	if (!atomic_try_cmpxchg(group->migr_state, &curstate.state, newstate.state)) {
		newstate.state = curstate.state;
		goto retry;
	}

> +
> +	if (group->parent && (walk_done == false)) {
> +		data->groupstate.state = atomic_read(group->parent->migr_state);
> +		data->childmask = group->childmask;
> +	}
> +
> +	/*
> +	 * Group is active, event will be ignored - bit is updated without
> +	 * holding the lock. In case bit is set while another CPU already
> +	 * handles remote events, nothing happens, because it is clear that
> +	 * CPU became active just in this moment, or in worst case event is
> +	 * handled remote. Nothing to worry about.
> +	 */
> +	group->groupevt.ignore = 1;
> +
> +	return walk_done;
> +}
  

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +static bool tmigr_inactive_up(struct tmigr_group *group,
> +			      struct tmigr_group *child,
> +			      void *ptr)
> +{
> +	union tmigr_state curstate, newstate;
> +	struct tmigr_walk *data = ptr;
> +	bool walk_done;
> +	u32 childmask;
> +
> +	childmask = data->childmask;
> +	newstate = curstate = data->groupstate;
> +
> +retry:
> +	walk_done = true;
> +
> +	/* Reset active bit when child is no longer active */
> +	if (!data->childstate.active)
> +		newstate.active &= ~(u8)childmask;
> +
> +	if (newstate.migrator == (u8)childmask) {
> +		/*
> +		 * Find a new migrator for the group, because child group
> +		 * is idle!
> +		 */
> +		if (!data->childstate.active) {
> +			unsigned long new_migr_bit, active = newstate.active;
> +
> +			new_migr_bit = find_first_bit(&active, BIT_CNT);
> +
> +			/* Changes need to be propagated */
> +			walk_done = false;
> +
> +			if (new_migr_bit != BIT_CNT)
> +				newstate.migrator = BIT(new_migr_bit);
> +			else
> +				newstate.migrator = TMIGR_NONE;
> +		}
> +	}
> +
> +	newstate.seq++;
> +
> +	DBG_BUG_ON((newstate.migrator != TMIGR_NONE) && !(newstate.active));
> +
> +	if (atomic_cmpxchg(group->migr_state, curstate.state, newstate.state) != curstate.state) {
> +		/*
> +		 * Something changed in child/parent group in the meantime,
> +		 * reread the state of child and parent; Update of
> +		 * data->childstate is required for event handling;
> +		 */
> +		if (child)
> +			data->childstate.state = atomic_read(child->migr_state);
> +		newstate.state = curstate.state = atomic_read(group->migr_state);
> +
> +		goto retry;
> +	}

Idem:

	if (!atomic_try_cmpxchg(group->migr_state, &curstate.state, newstate.state)) {
		newstate.state = curstate.state;
		if (child)
			data->childstate.state = atomic_read(child->migr_state);
		goto retry;
	}

> +
> +	data->groupstate = newstate;
> +	data->remote = false;
> +
> +	/* Event Handling */
> +	tmigr_update_events(group, child, data);
> +
> +	if (group->parent && (walk_done == false)) {
> +		data->childmask = group->childmask;
> +		data->childstate = newstate;
> +		data->groupstate.state = atomic_read(group->parent->migr_state);
> +	}
> +
> +	/*
> +	 * data->nextexp was set by tmigr_update_events() and contains the
> +	 * expiry of first global event which needs to be handled
> +	 */
> +	if (data->nextexp != KTIME_MAX) {
> +		DBG_BUG_ON(group->parent);
> +		/*
> +		 * Toplevel path - If this cpu is about going offline wake
> +		 * up some random other cpu so it will take over the
> +		 * migrator duty and program its timer properly. Ideally
> +		 * wake the cpu with the closest expiry time, but that's
> +		 * overkill to figure out.
> +		 */
> +		if (!(this_cpu_ptr(&tmigr_cpu)->online)) {
> +			unsigned int cpu = smp_processor_id();
> +
> +			cpu = cpumask_any_but(cpu_online_mask, cpu);
> +			smp_send_reschedule(cpu);
> +		}
> +	}
> +
> +	return walk_done;
> +}
  

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +static bool tmigr_requires_handle_remote_up(struct tmigr_group *group,
> +					 struct tmigr_group *child,
> +					 void *ptr)
> +{
> +	struct tmigr_remote_data *data = ptr;
> +	u32 childmask;
> +
> +	childmask = data->childmask;
> +
> +	/*
> +	 * Handle the group only if child is the migrator or if the group
> +	 * has no migrator. Otherwise the group is active and is handled by
> +	 * its own migrator.
> +	 */
> +	if (!tmigr_check_migrator(group, childmask))
> +		return true;
> +
> +	/*
> +	 * Racy lockless check for next_expiry
> +	 */
> +	if (data->now >= group->next_expiry) {

I'm not far enough along to tell; but on 32bit this can/will suffer from
split loads and basically turn into a random number generator. I'm
presuming the 'check = 1' thing here covers that case?

> +		data->check = 1;
> +		return true;
> +	}
> +
> +	/* Update of childmask for next level */
> +	data->childmask = group->childmask;
> +	return false;
> +}
  

(since the code is structured such, I also wrote the comments bottom-up)

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:

> +static struct tmigr_group *tmigr_get_group(unsigned int cpu, unsigned int node,
> +					   unsigned int lvl)
> +{
> +	struct tmigr_group *tmp, *group = NULL;
> +	bool first_loop = true;
> +	atomic_t *migr_state;

When first reading this I was wondering what was protecting the lists;
since this is at least 2 deep from where you take the lock. Perhaps add:

	lockdep_assert_held(&tmigr_mutex);

to clarify the locking context.

> +
> +reloop:
> +	/* Try to attach to an exisiting group first */
> +	list_for_each_entry(tmp, &tmigr_level_list[lvl], list) {
> +		/*
> +		 * If @lvl is below the cross numa node level, check whether
> +		 * this group belongs to the same numa node.
> +		 */
> +		if (lvl < tmigr_crossnode_level && tmp->numa_node != node)
> +			continue;
> +
> +		/* Capacity left? */
> +		if (tmp->num_childs >= TMIGR_CHILDS_PER_GROUP)
> +			continue;
> +
> +		/*
> +		 * If this is the lowest level of the hierarchy, make sure
> +		 * that thread siblings share a group. It is only executed
> +		 * when siblings exist. ALL groups of lowest level needs to
> +		 * be checked for thread sibling, before thread cpu is
> +		 * added to a random group with capacity. When all groups
> +		 * are checked and no thread sibling was found, reloop of
> +		 * level zero groups is required to get a group with
> +		 * capacity.
> +		 */
> +		if (!lvl && (tmigr_cores_per_group != TMIGR_CHILDS_PER_GROUP)) {
> +			if (first_loop == true && !sibling_in_group(cpu, tmp)) {
> +				continue;
> +			} else if (first_loop == false) {
> +				if (tmp->num_cores >= tmigr_cores_per_group)
> +					continue;
> +				else
> +					tmp->num_cores++;
> +			}
> +		}
> +
> +		group = tmp;
> +		break;
> +	}
> +
> +	if (group) {
> +		return group;
> +	} else if (first_loop == true) {
> +		first_loop = false;
> +		goto reloop;
> +	}
> +
> +	/* Allocate and	set up a new group with corresponding migr_state */
> +	group = kzalloc_node(sizeof(*group), GFP_KERNEL, node);
> +	if (!group)
> +		return ERR_PTR(-ENOMEM);
> +
> +	migr_state = kzalloc_node(sizeof(atomic_t), GFP_KERNEL, node);
> +	if (!migr_state) {
> +		kfree(group);
> +		return ERR_PTR(-ENOMEM);
> +	}
> +
> +	tmigr_init_group(group, lvl, node, migr_state);
> +	/* Setup successful. Add it to the hierarchy */
> +	list_add(&group->list, &tmigr_level_list[lvl]);
> +	return group;
> +}
> +
> +static void tmigr_connect_child_parent(struct tmigr_group *child,
> +				       struct tmigr_group *parent)
> +{
> +	union tmigr_state childstate;
> +	unsigned long flags;
> +
> +	raw_spin_lock_irqsave(&child->lock, flags);

Both callsites are in tmigr_setup_groups(), which must be ran in
preemptible context due to GFP_KERNEL allocations. Please use
raw_spin_lock_irq().

> +	raw_spin_lock_nested(&parent->lock, SINGLE_DEPTH_NESTING);
> +
> +	child->parent = parent;
> +	child->childmask = BIT(parent->num_childs++);
> +
> +	raw_spin_unlock(&parent->lock);
> +	raw_spin_unlock_irqrestore(&child->lock, flags);
> +
> +	/*
> +	 * To prevent inconsistent states, active childs needs to be active
> +	 * in new parent as well. Inactive childs are already marked
> +	 * inactive in parent group.
> +	 */
> +	childstate.state = atomic_read(child->migr_state);
> +	if (childstate.migrator != TMIGR_NONE) {
> +		struct tmigr_walk data;
> +
> +		data.childmask = child->childmask;
> +		data.groupstate.state = atomic_read(parent->migr_state);
> +
> +		/*
> +		 * There is only one new level per time. When connecting
> +		 * child and parent and set child active when parent is
> +		 * inactive, parent needs to be the upperst
> +		 * level. Otherwise there went something wrong!
> +		 */
> +		WARN_ON(!tmigr_active_up(parent, child, &data) && parent->parent);
> +	}
> +}
> +
> +static int tmigr_setup_groups(unsigned int cpu, unsigned int node)
> +{
> +	struct tmigr_group *group, *child, **stack;
> +	int top = 0, err = 0, i = 0;
> +	struct list_head *lvllist;
> +	size_t sz;
> +
> +	sz = sizeof(struct tmigr_group *) * tmigr_hierarchy_levels;
> +	stack = kzalloc(sz, GFP_KERNEL);
> +	if (!stack)
> +		return -ENOMEM;
> +
> +	do {
> +		group = tmigr_get_group(cpu, node, i);
> +		if (IS_ERR(group)) {
> +			err = IS_ERR(group);
> +			break;
> +		}
> +
> +		top = i;
> +		stack[i++] = group;
> +
> +		/*
> +		 * When booting only less CPUs of a system than CPUs are
> +		 * available, not all calculated hierarchy levels are required.
> +		 *
> +		 * The loop is aborted as soon as the highest level, which might
> +		 * be different from tmigr_hierarchy_levels, contains only a
> +		 * single group.
> +		 */
> +		if (group->parent || i == tmigr_hierarchy_levels ||
> +		    (list_empty(&tmigr_level_list[i]) &&
> +		     list_is_singular(&tmigr_level_list[i - 1])))
> +			break;
> +
> +	} while (i < tmigr_hierarchy_levels);
> +
> +	do {
> +		group = stack[--i];
> +
> +		if (err < 0) {
> +			list_del(&group->list);
> +			kfree(group);
> +			continue;
> +		}
> +
> +		DBG_BUG_ON(i != group->level);
> +
> +		/*
> +		 * Update tmc -> group / child -> group connection
> +		 */
> +		if (i == 0) {
> +			struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu);
> +			unsigned long flags;
> +
> +			raw_spin_lock_irqsave(&group->lock, flags);

You're holding a mutex, you just did a GFP_KERNEL allocation; there is
no way IRQs are already disabled here, please use raw_spin_lock_irq() to
reduce confusion.

> +
> +			tmc->tmgroup = group;
> +			tmc->childmask = BIT(group->num_childs);
> +
> +			group->cpus[group->num_childs++] = cpu;
> +
> +			raw_spin_unlock_irqrestore(&group->lock, flags);
> +
> +			/* There are no childs that needs to be connected */
> +			continue;
> +		} else {
> +			child = stack[i - 1];
> +			tmigr_connect_child_parent(child, group);
> +		}
> +
> +		/* check if upperst level was newly created */
> +		if (top != i)
> +			continue;
> +
> +		DBG_BUG_ON(top == 0);
> +
> +		lvllist = &tmigr_level_list[top];
> +		if (group->num_childs == 1 && list_is_singular(lvllist)) {
> +			lvllist = &tmigr_level_list[top - 1];
> +			list_for_each_entry(child, lvllist, list) {
> +				if (child->parent)
> +					continue;
> +
> +				tmigr_connect_child_parent(child, group);
> +			}
> +		}
> +	} while (i > 0);
> +
> +	kfree(stack);
> +
> +	return err;
> +}
> +
> +static int tmigr_add_cpu(unsigned int cpu)
> +{
> +	unsigned int node = cpu_to_node(cpu);
> +	int ret;
> +	mutex_lock(&tmigr_mutex);
> +	ret = tmigr_setup_groups(cpu, node);
> +	mutex_unlock(&tmigr_mutex);
> +
> +	return ret;
> +}
> +
> +static int tmigr_cpu_online(unsigned int cpu)
> +{
> +	struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu);
> +	unsigned long flags;
> +	unsigned int ret;
> +
> +	/* First online attempt? Initialize CPU data */
> +	if (!tmc->tmgroup) {
> +		raw_spin_lock_init(&tmc->lock);
> +
> +		ret = tmigr_add_cpu(cpu);
> +		if (ret < 0)
> +			return ret;
> +
> +		if (tmc->childmask == 0)
> +			return -EINVAL;
> +
> +		timerqueue_init(&tmc->cpuevt.nextevt);
> +		tmc->cpuevt.nextevt.expires = KTIME_MAX;
> +		tmc->cpuevt.ignore = 1;
> +		tmc->cpuevt.cpu = cpu;
> +
> +		tmc->remote = 0;
> +		tmc->idle = 0;
> +		tmc->wakeup = KTIME_MAX;
> +	}
> +	raw_spin_lock_irqsave(&tmc->lock, flags);

You just called tmigr_add_cpu() which takes a mutex, there is no
possible way this can be called with IRQs already disabled. Please use
raw_spin_lock_irq() to reduce confusion.

Also, offline below does that and this is just inconsistent.

> +	__tmigr_cpu_activate(tmc);
> +	tmc->online = 1;
> +	raw_spin_unlock_irqrestore(&tmc->lock, flags);
> +	return 0;
> +}
> +
> +static int tmigr_cpu_offline(unsigned int cpu)
> +{
> +	struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu);
> +
> +	raw_spin_lock_irq(&tmc->lock);
> +	tmc->online = 0;
> +	__tmigr_cpu_deactivate(tmc, KTIME_MAX);
> +	raw_spin_unlock_irq(&tmc->lock);
> +
> +	return 0;
> +}
  

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +		/*
> +		 * There is only one new level per time. When connecting
> +		 * child and parent and set child active when parent is
> +		 * inactive, parent needs to be the upperst
> +		 * level. Otherwise there went something wrong!
> +		 */

> +		/* check if upperst level was newly created */

Sorry for being a pain and with the caveat that I'm not a native speaker
either, but I think upperst should be uppermost. You actually had me
google to see what the word meant..
  

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:

> +	group->num_childs = 0;
k
> +	 * To prevent inconsistent states, active childs needs to be active
> +	 * in new parent as well. Inactive childs are already marked
> +	 * inactive in parent group.
> +	 */

> +			/* There are no childs that needs to be connected */

s/childs/children/ and s/needs/need/

The child needs ...
The children need ...
  

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:

> +static void tmigr_init_group(struct tmigr_group *group, unsigned int lvl,
> +			     unsigned int node, atomic_t *migr_state)
> +{
> +	union tmigr_state s;
> +
> +	raw_spin_lock_init(&group->lock);
> +
> +	group->level = lvl;
> +	group->numa_node = lvl < tmigr_crossnode_level ? node : NUMA_NO_NODE;
> +
> +	group->num_childs = 0;
> +
> +	/*
> +	 * num_cores is required for level=0 groups only during setup and
> +	 * when siblings exists but it doesn't matter if this value is set
> +	 * in other groups as well
> +	 */
> +	group->num_cores = 1;
> +
> +	s.migrator = TMIGR_NONE;
> +	s.active = 0;
> +	s.seq = 0;
> +	atomic_set(migr_state, s.state);
> +
> +	group->migr_state = migr_state;
> +
> +	timerqueue_init_head(&group->events);
> +	timerqueue_init(&group->groupevt.nextevt);
> +	group->groupevt.nextevt.expires = KTIME_MAX;
> +	group->next_expiry = KTIME_MAX;
> +	group->groupevt.ignore = 1;
> +}

> +static struct tmigr_group *tmigr_get_group(unsigned int cpu, unsigned int node,
> +					   unsigned int lvl)
> +{
> +	struct tmigr_group *tmp, *group = NULL;
> +	bool first_loop = true;
> +	atomic_t *migr_state;
> +

...

> +
> +	/* Allocate and	set up a new group with corresponding migr_state */
> +	group = kzalloc_node(sizeof(*group), GFP_KERNEL, node);
> +	if (!group)
> +		return ERR_PTR(-ENOMEM);
> +
> +	migr_state = kzalloc_node(sizeof(atomic_t), GFP_KERNEL, node);
> +	if (!migr_state) {
> +		kfree(group);
> +		return ERR_PTR(-ENOMEM);
> +	}
> +
> +	tmigr_init_group(group, lvl, node, migr_state);

I'm confused by migr_state.. why is that allocated seperately, if it is
*always* 1:1 related to the group. Why isn't it a direct member?

> +	/* Setup successful. Add it to the hierarchy */
> +	list_add(&group->list, &tmigr_level_list[lvl]);
> +	return group;
> +}
  

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:

> diff --git a/kernel/time/timer_migration.h b/kernel/time/timer_migration.h
> new file mode 100644
> index 000000000000..ceb336e705df
> --- /dev/null
> +++ b/kernel/time/timer_migration.h
> @@ -0,0 +1,123 @@
> +#ifndef _KERNEL_TIME_MIGRATION_H
> +#define _KERNEL_TIME_MIGRATION_H
> +
> +/* Per group capacity. Must be a power of 2! */
> +#define TMIGR_CHILDS_PER_GROUP 8
> +
> +/**
> + * struct tmigr_event - a timer event associated to a CPU
> + * @nextevt:	The node to enqueue an event in the parent group queue
> + * @cpu:	The CPU to which this event belongs
> + * @ignore:	Hint whether the event could be ignored; it is set when
> + *		CPU or group is active;
> + */
> +struct tmigr_event {
> +	struct timerqueue_node	nextevt;
> +	unsigned int		cpu;
> +	int			ignore;
> +};
> +
> +/**
> + * struct tmigr_group - timer migration hierarchy group
> + * @lock:		Lock protecting the event information
> + * @cpus:		Array with CPUs which are member of group; required for
> + *			sibling CPUs; used only when level == 0

That's 32 bytes wasted for every group that isn't 0, maybe stick on the
end and conditionally allocate? Also, afaict it is only ever used during
setup, and as such should not be placed in a hot line, unless you've
done that explicitly as padding, in which case it needs a comment to
that effect.

Also, since it's setup only, why can't you match against:

  per_cpu_ptr(&tmigr_cpu, cpu)->parent

?

> + * @parent:		Pointer to parent group
> + * @list:		List head that is added to per level tmigr_level_list

Also setup only?

> + * @level:		Hierarchy level of group
> + * @numa_node:		Is set to numa node when level < tmigr_crossnode_level;
> + *			otherwise it is set to NUMA_NO_NODE; Required for setup
> + *			only
> + * @num_childs:		Counter of group childs; Required for setup only
> + * @num_cores:		Counter of cores per group; Required for setup only when
> + *			level == 0 and siblings exist

Also setup only, move the end?

> + * @migr_state:		State of group (see struct tmigr_state)
> + * @childmask:		childmask of group in parent group; is set during setup
> + *			never changed; could be read lockless
> + * @events:		Timer queue for child events queued in the group
> + * @groupevt:		Next event of group; it is only reliable when group is
> + *			!active (ignore bit is set when group is active)
> + * @next_expiry:	Base monotonic expiry time of next event of group;
> + *			Used for racy lockless check whether remote expiry is
> + *			required; it is always reliable

This is basically leftmost of @events? A racy lockless check sorta
implies not reliable, comment is confusing.

Also, isn't this identical to @groupevt.nextevt.expiry ?

> + */
> +struct tmigr_group {
> +	raw_spinlock_t		lock;
> +	unsigned int		cpus[TMIGR_CHILDS_PER_GROUP];
> +	struct tmigr_group	*parent;
> +	struct list_head	list;
> +	unsigned int		level;
> +	unsigned int		numa_node;
> +	unsigned int		num_childs;
> +	unsigned int		num_cores;
> +	atomic_t		*migr_state;

Per the other email; why isn't this:

	union tmigr_state	migr_state;

?

> +	u32			childmask;
> +	struct timerqueue_head	events;
> +	struct tmigr_event	groupevt;
> +	u64			next_expiry;
> +};
> +
> +/**
> + * struct tmigr_cpu - timer migration per CPU group
> + * @lock:	Lock protecting tmigr_cpu group information
> + * @online:	Indicates wheter CPU is online

What I'm missing is *why* we're keeping this state. I suspect you need
serialization on tmigr_cpu->lock between hotplug and something.

> + * @idle:	Indicates wheter CPU is idle in timer migration hierarchy
> + * @remote:	Is set when timers of CPU are expired remote

How are these not the same? When idle timers are expired remote, no?

> + * @tmgroup:	Pointer to parent group
> + * @childmask:	childmask of tmigr_cpu in parent group
> + * @cpuevt:	CPU event which could be queued into parent group
> + * @wakeup:	Stores the first timer when the timer migration hierarchy is
> + *		completely idle and remote expiry was done; is returned to
> + *		timer code when tmigr_cpu_deactive() is called and group is
> + *		idle; afterwards a reset to KTIME_MAX is required;
> + */
> +struct tmigr_cpu {
> +	raw_spinlock_t		lock;
> +	int			online;
> +	int			idle;
> +	int			remote;
> +	struct tmigr_group	*tmgroup;
> +	u32			childmask;
> +	struct tmigr_event	cpuevt;
> +	u64			wakeup;
> +};
> +
> +/**
> + * union tmigr_state - state of tmigr_group
> + * @state:	Combined version of the state - only used for atomic
> + * 		read/cmpxchg function
> + * @struct:	Splitted version of the state - only use the struct members to
> + *		update information to stay independant of endianess
> + */
> +union tmigr_state {
> +	u32 state;
> +	/**
> +	 * struct - splitted state of tmigr_group
> +	 * @active:	Contains each childmask bit of active childs
> +	 * @migrator:	Contains childmask of child which is migrator
> +	 * @seq:	Seqence number to prevent race when update in child
> +	 *		group are propagated in wrong order (especially when
> +	 *		migrator changes are involved)
> +	 */
> +	struct {
> +		u8	active;
> +		u8	migrator;

So childmask is the bit set in either of these masks, but it is u32
elsewhere and u8 here. Surely if the target type is u8, then it is best
to keep it consistently u8 elsewhere too, no?

> +		u16	seq;
> +	} __packed;
> +};
  

On Tue, 21 Mar 2023, Frederic Weisbecker wrote:

> On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> > +static u64 tmigr_handle_remote_cpu(unsigned int cpu, u64 now,
> > +				   unsigned long jif)
> > +{
> > +	struct timer_events tevt;
> > +	struct tmigr_walk data;
> > +	struct tmigr_cpu *tmc;
> > +	u64 next = KTIME_MAX;
> > +	unsigned long flags;
> > +
> > +	tmc = per_cpu_ptr(&tmigr_cpu, cpu);
> > +
> > +	raw_spin_lock_irqsave(&tmc->lock, flags);
> > +	/*
> > +	 * Remote CPU is offline or no longer idle or other cpu handles cpu
> > +	 * timers already or next event was already expired - return!
> > +	 */
> > +	if (!tmc->online || tmc->remote || tmc->cpuevt.ignore ||
> > +	    now < tmc->cpuevt.nextevt.expires) {
> > +		raw_spin_unlock_irqrestore(&tmc->lock, flags);
> > +		return next;
> > +	}
> > +
> > +	tmc->remote = 1;
> > +
> > +	/* Drop the lock to allow the remote CPU to exit idle */
> > +	raw_spin_unlock_irqrestore(&tmc->lock, flags);
> > +
> > +	if (cpu != smp_processor_id())
> > +		timer_expire_remote(cpu);
> > +
> > +	/* next event of cpu */
> > +	fetch_next_timer_interrupt_remote(jif, now, &tevt, cpu);
> 
> If the target CPU gets an idle interrupt right after the above call and enqueues
> a new timer (which becomes the new earliest), tmigr_cpu_deactivate() ->
> tmigr_new_timer() is going to ignore it due to tmc->remote = 1, right?

It's worse. The newly enqueued timer is updated in the timer migration
hierarchy when CPU goes back idle and afterwards it will be overwritten by
the group walk propagating the old first timer in
tmigr_handle_remote_cpu()...

I will change the code after remote timer expiry:

1. take the remote timer bases locks
2. take the tmc->lock
3. get the next timer interrupt remote
4. drop the remote timer bases locks
5. propagate new timer changes
6. drop the tmc->lock

Thanks,

	Anna-Maria
  

On Tue, Apr 04, 2023 at 04:05:27PM +0200, Anna-Maria Behnsen wrote:
> On Tue, 21 Mar 2023, Frederic Weisbecker wrote:
> 
> > On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> > > +static u64 tmigr_handle_remote_cpu(unsigned int cpu, u64 now,
> > > +				   unsigned long jif)
> > > +{
> > > +	struct timer_events tevt;
> > > +	struct tmigr_walk data;
> > > +	struct tmigr_cpu *tmc;
> > > +	u64 next = KTIME_MAX;
> > > +	unsigned long flags;
> > > +
> > > +	tmc = per_cpu_ptr(&tmigr_cpu, cpu);
> > > +
> > > +	raw_spin_lock_irqsave(&tmc->lock, flags);
> > > +	/*
> > > +	 * Remote CPU is offline or no longer idle or other cpu handles cpu
> > > +	 * timers already or next event was already expired - return!
> > > +	 */
> > > +	if (!tmc->online || tmc->remote || tmc->cpuevt.ignore ||
> > > +	    now < tmc->cpuevt.nextevt.expires) {
> > > +		raw_spin_unlock_irqrestore(&tmc->lock, flags);
> > > +		return next;
> > > +	}
> > > +
> > > +	tmc->remote = 1;
> > > +
> > > +	/* Drop the lock to allow the remote CPU to exit idle */
> > > +	raw_spin_unlock_irqrestore(&tmc->lock, flags);
> > > +
> > > +	if (cpu != smp_processor_id())
> > > +		timer_expire_remote(cpu);
> > > +
> > > +	/* next event of cpu */
> > > +	fetch_next_timer_interrupt_remote(jif, now, &tevt, cpu);
> > 
> > If the target CPU gets an idle interrupt right after the above call and enqueues
> > a new timer (which becomes the new earliest), tmigr_cpu_deactivate() ->
> > tmigr_new_timer() is going to ignore it due to tmc->remote = 1, right?
> 
> It's worse. The newly enqueued timer is updated in the timer migration
> hierarchy when CPU goes back idle and afterwards it will be overwritten by
> the group walk propagating the old first timer in
> tmigr_handle_remote_cpu()...

Hmm then that would require the remote CPU to exit dynticks and then
re-enter dynticks, right? Yes, sounds possible too.

> 
> I will change the code after remote timer expiry:
> 
> 1. take the remote timer bases locks
> 2. take the tmc->lock
> 3. get the next timer interrupt remote
> 4. drop the remote timer bases locks
> 5. propagate new timer changes
> 6. drop the tmc->lock

Right that sounds good!

Thanks.

> 
> Thanks,
> 
> 	Anna-Maria
  

On Thu, 23 Mar 2023, Peter Zijlstra wrote:

> On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> 
> > diff --git a/kernel/time/timer_migration.h b/kernel/time/timer_migration.h
> > new file mode 100644
> > index 000000000000..ceb336e705df
> > --- /dev/null
> > +++ b/kernel/time/timer_migration.h
> > @@ -0,0 +1,123 @@
> > +#ifndef _KERNEL_TIME_MIGRATION_H
> > +#define _KERNEL_TIME_MIGRATION_H
> > +
> > +/* Per group capacity. Must be a power of 2! */
> > +#define TMIGR_CHILDS_PER_GROUP 8
> > +
> > +/**
> > + * struct tmigr_event - a timer event associated to a CPU
> > + * @nextevt:	The node to enqueue an event in the parent group queue
> > + * @cpu:	The CPU to which this event belongs
> > + * @ignore:	Hint whether the event could be ignored; it is set when
> > + *		CPU or group is active;
> > + */
> > +struct tmigr_event {
> > +	struct timerqueue_node	nextevt;
> > +	unsigned int		cpu;
> > +	int			ignore;
> > +};
> > +
> > +/**
> > + * struct tmigr_group - timer migration hierarchy group
> > + * @lock:		Lock protecting the event information
> > + * @cpus:		Array with CPUs which are member of group; required for
> > + *			sibling CPUs; used only when level == 0
> 
> That's 32 bytes wasted for every group that isn't 0, maybe stick on the
> end and conditionally allocate? Also, afaict it is only ever used during
> setup, and as such should not be placed in a hot line, unless you've
> done that explicitly as padding, in which case it needs a comment to
> that effect.
> 
> Also, since it's setup only, why can't you match against:
> 
>   per_cpu_ptr(&tmigr_cpu, cpu)->parent
> 
> ?

This cpus array is currently used to make sure siblings will end up in the
same level 0 group. When matching against the per_cpu_ptr(&tmigr_cpu,
cpu)->parent, I would need to rely on the topology mask and have a look if
the sibling already has a parent.

My question here is: Is it required that siblings end up in the same group
in level 0, or is it enough if the numa node is the same?

> > + * @parent:		Pointer to parent group
> > + * @list:		List head that is added to per level tmigr_level_list
> 
> Also setup only?

Jupp.

> > + * @level:		Hierarchy level of group
> > + * @numa_node:		Is set to numa node when level < tmigr_crossnode_level;
> > + *			otherwise it is set to NUMA_NO_NODE; Required for setup
> > + *			only
> > + * @num_childs:		Counter of group childs; Required for setup only
> > + * @num_cores:		Counter of cores per group; Required for setup only when
> > + *			level == 0 and siblings exist
> 
> Also setup only, move the end?

Same. Will move all the setup stuff to the end.

> > + * @migr_state:		State of group (see struct tmigr_state)
> > + * @childmask:		childmask of group in parent group; is set during setup
> > + *			never changed; could be read lockless
> > + * @events:		Timer queue for child events queued in the group
> > + * @groupevt:		Next event of group; it is only reliable when group is
> > + *			!active (ignore bit is set when group is active)
> > + * @next_expiry:	Base monotonic expiry time of next event of group;
> > + *			Used for racy lockless check whether remote expiry is
> > + *			required; it is always reliable
> 
> This is basically leftmost of @events? A racy lockless check sorta
> implies not reliable, comment is confusing.

It's always updated and contains the expiry value of the first event which
is enqueued into timer queue "events" - reliable is the wrong term here.

> Also, isn't this identical to @groupevt.nextevt.expiry ?

No, it is not identical. Because groupevt is only used and reliable, when
the group is idle to enqueue the first group event into the parent
group. But the migrator of the group needs to check whether timers needs to
be handled remote because some children are idle. Therefore I do not have to
update the whole event.

> > + */
> > +struct tmigr_group {
> > +	raw_spinlock_t		lock;
> > +	unsigned int		cpus[TMIGR_CHILDS_PER_GROUP];
> > +	struct tmigr_group	*parent;
> > +	struct list_head	list;
> > +	unsigned int		level;
> > +	unsigned int		numa_node;
> > +	unsigned int		num_childs;
> > +	unsigned int		num_cores;
> > +	atomic_t		*migr_state;
> 
> Per the other email; why isn't this:
> 
> 	union tmigr_state	migr_state;
> 
> ?

I will change this into a direct member. The reason for not being a direct
member is - because it grows like this...

Only for handling the tmigr_group->migr_state, atomic operations are used
the splitted members are never accessed. All other states are not handled
with atomic operations. If it is 'union tmigr_state' inside the
tmigr_group, then I would need an atomic_t inside the union and the union
gets more complex. I hope I was able to explain my point.

> > +	u32			childmask;
> > +	struct timerqueue_head	events;
> > +	struct tmigr_event	groupevt;
> > +	u64			next_expiry;
> > +};
> > +

I come back to your other remarks in a separate mail.

Thanks,

	Anna-Maria
  

On Tue, 21 Mar 2023, Frederic Weisbecker wrote:

> On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> > +static bool tmigr_inactive_up(struct tmigr_group *group,
> > +			      struct tmigr_group *child,
> > +			      void *ptr)
> > +{
> > +	union tmigr_state curstate, newstate;
> > +	struct tmigr_walk *data = ptr;
> > +	bool walk_done;
> > +	u32 childmask;
> > +
> > +	childmask = data->childmask;
> > +	newstate = curstate = data->groupstate;
> > +
> > +retry:
> > +	walk_done = true;
> > +
> > +	/* Reset active bit when child is no longer active */
> > +	if (!data->childstate.active)
> > +		newstate.active &= ~(u8)childmask;
> > +
> > +	if (newstate.migrator == (u8)childmask) {
> > +		/*
> > +		 * Find a new migrator for the group, because child group
> > +		 * is idle!
> > +		 */
> > +		if (!data->childstate.active) {
> > +			unsigned long new_migr_bit, active = newstate.active;
> > +
> > +			new_migr_bit = find_first_bit(&active, BIT_CNT);
> > +
> > +			/* Changes need to be propagated */
> > +			walk_done = false;
> 
> Do you need to propagate the changes even if you found a new migrator for the
> group?

No, you shouldn't require the walk then. Will think about it again, fix
(and test) it.

> > +
> > +			if (new_migr_bit != BIT_CNT)
> > +				newstate.migrator = BIT(new_migr_bit);
> > +			else
> > +				newstate.migrator = TMIGR_NONE;
> 
> Thanks.
> 

Thanks,

	Anna-Maria