[PATCH 5/6] timers/migration: Prefer lower capacity groups as migrators

[Frederic Weisbecker <frederic@kernel.org>]

Pulling timers to low capacity CPUs may improve power consumption
by executing non performance critical ground work there and increasing
the chances to turn the small CPUs into idle global migrators if such
work keeps them alive for long enough. This way low power CPUs may be
woken up from deep idle instead of high power CPUs.

To implement this, migrators going idle will select the lowest alive
capacity groups as new migrators. And CPUs exiting idle will force
select themselves as the new migrator if their capacity is lower than
the current migrator.

Signed-off-by: Frederic Weisbecker <frederic@kernel.org>
---
 include/linux/sched/topology.h  |  1 +
 kernel/sched/topology.c         | 20 ++++++++++++++++++++
 kernel/time/timer_migration.c   | 33 +++++++++++++++++++++++++++------
 kernel/time/timer_migration.h   |  2 ++
 scripts/timer_migration_tree.py | 24 ++++++++++++------------
 5 files changed, 62 insertions(+), 18 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index 88632825136e..de584bde7dee 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -52,6 +52,7 @@ extern const struct cpumask *tl_pkg_mask(struct sched_domain_topology_level *tl,
 extern int arch_asym_cpu_priority(int cpu);
 extern int sched_asym_count(void);
 extern int sched_asym_max_cpus(void);
+extern int sched_asym_capacity_rank(unsigned long capacity);
 
 struct sched_domain_attr {
 	int relax_domain_level;
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 3b3bd32aea40..7673dfd579db 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -1760,6 +1760,26 @@ int sched_asym_max_cpus(void)
 	return asym_capacity_max_cpus;
 }
 
+int sched_asym_capacity_rank(unsigned long capacity)
+{
+	struct asym_cap_data *entry;
+	int i = 0;
+
+	/*
+	 * Search if capacity already exits. If not, track which the entry
+	 * where we should insert to keep the list ordered descending.
+	 */
+	list_for_each_entry_reverse(entry, &asym_cap_list, link) {
+		if (capacity == entry->capacity)
+			return i;
+		i++;
+	}
+
+	WARN_ONCE(1, "Capacity %lu not found in capacity list", capacity);
+
+	return 0;
+}
+
 /*
  * Build-up/update list of CPUs grouped by their capacities
  * An update requires explicit request to rebuild sched domains
diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c
index 2c2925046f43..a16d265df33e 100644
--- a/kernel/time/timer_migration.c
+++ b/kernel/time/timer_migration.c
@@ -677,11 +677,14 @@ static bool tmigr_active_up(struct tmigr_group *group,
 		newstate = curstate;
 		walk_done = true;
 
-		if (newstate.migrator == TMIGR_NONE) {
+		if (curstate.migrator == TMIGR_NONE ||
+		    (group->want_low_migrator && childmask < curstate.migrator)) {
 			newstate.migrator = childmask;
 
-			/* Changes need to be propagated */
-			walk_done = false;
+			if (curstate.migrator == TMIGR_NONE) {
+				/* Changes need to be propagated */
+				walk_done = false;
+			}
 		}
 
 		newstate.active |= childmask;
@@ -1644,6 +1647,12 @@ static void tmigr_init_group(struct tmigr_group *group, unsigned int lvl,
 
 	group->num_children = 0;
 
+	/* Always prefer a migrator with lower capacity */
+	if (sched_asym_count() > 1 && lvl == tmigr_crossfamily_level)
+		group->want_low_migrator = true;
+	else
+		group->want_low_migrator = false;
+
 	s.migrator = TMIGR_NONE;
 	s.active = 0;
 	s.seq = 0;
@@ -1708,6 +1717,18 @@ static struct tmigr_group *tmigr_get_group(int family, unsigned int lvl)
 	return group;
 }
 
+static void tmigr_init_groupmask(struct tmigr_group *group, u8 groupmask)
+{
+	/*
+	 * Overwrite the groupmask if this is a whole capacity group so that
+	 * candidate migrators are sorted by capacity.
+	 */
+	if (sched_asym_count() > 1 && group->level == tmigr_crossfamily_level - 1)
+		groupmask = BIT(sched_asym_capacity_rank(group->family));
+
+	group->groupmask = groupmask;
+}
+
 static bool tmigr_init_root(struct tmigr_group *group, bool root_up)
 {
 	if (!group->parent && group != tmigr_root) {
@@ -1716,7 +1737,7 @@ static bool tmigr_init_root(struct tmigr_group *group, bool root_up)
 		 * to avoid accidents where yet another new top-level is
 		 * created in the future and made visible before this groupmask.
 		 */
-		group->groupmask = BIT(0);
+		tmigr_init_groupmask(group, BIT(0));
 		WARN_ON_ONCE(root_up);
 
 		return true;
@@ -1750,10 +1771,10 @@ static void tmigr_connect_child_parent(struct tmigr_group *child,
 		 * to the CPU going up has been accounted as the second child.
 		 */
 		WARN_ON_ONCE(parent->num_children != 2);
-		child->groupmask = BIT(0);
+		tmigr_init_groupmask(child, BIT(0));
 	} else {
 		/* Common case adding @child for the CPU going up to @parent. */
-		child->groupmask = BIT(parent->num_children++);
+		tmigr_init_groupmask(child, BIT(parent->num_children++));
 	}
 
 	/*
diff --git a/kernel/time/timer_migration.h b/kernel/time/timer_migration.h
index 3f6c7a110e3c..0bf3a0e7d54c 100644
--- a/kernel/time/timer_migration.h
+++ b/kernel/time/timer_migration.h
@@ -58,6 +58,7 @@ struct tmigr_event {
  *			tmigr_level_list; is required during setup when a
  *			new group needs to be connected to the existing
  *			hierarchy groups
+ * @want_low_migrator:	Group wants the lowest capacity migrator
  */
 struct tmigr_group {
 	raw_spinlock_t		lock;
@@ -71,6 +72,7 @@ struct tmigr_group {
 	unsigned int		num_children;
 	u8			groupmask;
 	struct list_head	list;
+	bool			want_low_migrator;
 };
 
 /**
diff --git a/scripts/timer_migration_tree.py b/scripts/timer_migration_tree.py
index abb321b903c4..4f055fc08435 100755
--- a/scripts/timer_migration_tree.py
+++ b/scripts/timer_migration_tree.py
@@ -33,8 +33,8 @@ class Node:
 	def set_lvl(self, lvl):
 		self.lvl = lvl
 
-	def set_numa(self, numa):
-		self.numa = numa
+	def set_family(self, family):
+		self.family = family
 
 	def set_num_children(self, num_children):
 		self.num_children = num_children
@@ -44,7 +44,7 @@ class Node:
 			parent_grp = self.parent.group
 		else:
 			parent_grp = "-"
-		return "Group: %s mask: %s parent: %s lvl: %d numa: %d num_children: %d" % (self.group, self.groupmask, parent_grp, self.lvl, self.numa, self.num_children)
+		return "Group: %s mask: %s parent: %s lvl: %d family: %d num_children: %d" % (self.group, self.groupmask, parent_grp, self.lvl, self.family, self.num_children)
 
 def get_node(group):
 	if group in Node.node_list:
@@ -55,32 +55,32 @@ def get_node(group):
 		return n
 
 def tmigr_connect_cpu_parent(ts, line):
-	s = re.search("tmigr_connect_cpu_parent: cpu=([0-9]+) groupmask=([0-9a-zA-Z]+) parent=([0-9a-zA-Z]+) lvl=([0-9]+) numa=([-]?[0-9]+) num_children=([0-9]+)", line)
+	s = re.search("tmigr_connect_cpu_parent: cpu=([0-9]+) groupmask=([0-9a-zA-Z]+) parent=([0-9a-zA-Z]+) lvl=([0-9]+) family=([-]?[0-9]+) num_children=([0-9]+)", line)
 	if s is None:
 		return False
-	(cpu, groupmask, parent, lvl, numa, num_children) = (int(s.group(1)), s.group(2), s.group(3), int(s.group(4)), int(s.group(5)), int(s.group(6)))
+	(cpu, groupmask, parent, lvl, family, num_children) = (int(s.group(1)), s.group(2), s.group(3), int(s.group(4)), int(s.group(5)), int(s.group(6)))
 	n = get_node(cpu)
 	p = get_node(parent)
 	n.set_parent(p)
 	n.set_groupmask(groupmask)
 	n.set_lvl(-1)
 	p.set_lvl(lvl)
-	p.set_numa(numa)
-	n.set_numa(numa)
+	p.set_family(family)
+	n.set_family(family)
 	p.set_num_children(num_children)
 	p.add_child(n)
 
 def tmigr_connect_child_parent(ts, line):
-	s = re.search("tmigr_connect_child_parent: group=([0-9a-zA-Z]+) groupmask=([0-9a-zA-Z]+) parent=([0-9a-zA-Z]+) lvl=([0-9]+) numa=([-]?[0-9]+) num_children=([0-9]+)", line)
+	s = re.search("tmigr_connect_child_parent: group=([0-9a-zA-Z]+) groupmask=([0-9a-zA-Z]+) parent=([0-9a-zA-Z]+) lvl=([0-9]+) family=([-]?[0-9]+) num_children=([0-9]+)", line)
 	if s is None:
 		return False
-	(group, groupmask, parent, lvl, numa, num_children) = (s.group(1), s.group(2), s.group(3), int(s.group(4)), int(s.group(5)), int(s.group(6)))
+	(group, groupmask, parent, lvl, family, num_children) = (s.group(1), s.group(2), s.group(3), int(s.group(4)), int(s.group(5)), int(s.group(6)))
 	n = get_node(group)
 	p = get_node(parent)
 	n.set_parent(p)
 	n.set_groupmask(groupmask)
 	p.set_lvl(lvl)
-	p.set_numa(numa)
+	p.set_family(family)
 	p.set_num_children(num_children)
 	p.add_child(n)
 
@@ -88,7 +88,7 @@ def populate(enode, node):
 	enode = enode.add_child(name = node.group)
 	enode.add_feature("groupmask", "m:%s" % node.groupmask)
 	enode.add_feature("lvl", "lvl:%d" % node.lvl)
-	enode.add_feature("numa", "node %d" % node.numa)
+	enode.add_feature("family", "family %d" % node.family)
 	enode.add_feature("num_children", "c=%d" % node.num_children)
 	for child in node.children:
 		populate(enode, child)
@@ -107,4 +107,4 @@ if __name__ == "__main__":
 		group = group.parent
 	root = Tree()
 	populate(root, group)
-	print(root.get_ascii(show_internal=True, attributes=["name", "numa", "lvl"]))
+	print(root.get_ascii(show_internal=True, attributes=["name", "family", "lvl"]))
-- 
2.53.0