Skip to contentSkip to conversation

Introduce group balancer

RFC PATCH In review Tianchen Ding 2 participants 12 messages Mar 8, 2022 – Apr 6, 2022

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

v2 cover Introduce group balancer

Modern platform are growing fast on CPU numbers. To achieve better utility of CPU resource, multiple apps are starting to sharing the CPUs.

What we need is a way to ease confliction in share mode, make groups as exclusive as possible, to gain both performance and resource efficiency.

The main idea of group balancer is to fulfill this requirement by balancing groups of tasks among groups of CPUs, consider this as a dynamic demi-exclusive mode. Task trigger work to settle it's group into a proper partition (minimum predicted load), then try migrate itself into it. To gradually settle groups into the most exclusively partition.

GB can be seen as an optimize policy based on load balance, it obeys the main idea of load balance and makes adjustment based on that.

Our test on ARM64 platform with 128 CPUs shows that, throughput of sysbench memory is improved about 25%, and redis-benchmark is improved up to about 10%.

See each patch for detail:
The 1st patch introduces infrastructure.
The 2nd patch introduces detail about partition info. The 3rd patch is the main part of group balancer. The 4th patch is about stats.

v2:
Put partition info and period settings to cpuset subsys of cgroup_v2.

v1: https://lore.kernel.org/all/98f41efd-74b2-198a-839c-51b785b748a6-KPsoFbNs7GizrGE5bRqYAgC/[email protected]/

Michael Wang (1):
sched: Introduce group balancer

Tianchen Ding (3):
sched, cpuset: Introduce infrastructure of group balancer
cpuset: Handle input of partition info for group balancer cpuset, gb: Add stat for group balancer

 include/linux/cpuset.h   |   5 +
 include/linux/sched.h    |   5 +
 include/linux/sched/gb.h |  70 ++++++
 init/Kconfig             |  12 +
 kernel/cgroup/cpuset.c   | 405 +++++++++++++++++++++++++++++++-
 kernel/sched/Makefile    |   1 +
 kernel/sched/core.c      |   5 +
 kernel/sched/debug.c     |  10 +-
 kernel/sched/fair.c      |  26 ++-
 kernel/sched/gb.c        | 487 +++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h     |  14 ++
 11 files changed, 1037 insertions(+), 3 deletions(-)
 create mode 100644 include/linux/sched/gb.h
 create mode 100644 kernel/sched/gb.c
Signature · 1 line
2.27.0
#1 lore raw

RFC PATCH v2 1/4 sched, cpuset: Introduce infrastructure of group balancer

Introduce CONFIG and struct about group balancer.
Add a few interfaces on cpuset and debugfs to read&write params.

In detail:
cgroup:
cpuset.gb.period_us:
To control work period.
Write a positive number to enable group balancer for all descendants EXCEPT itself.
Write 0 to disable it.
MAX 1000000. (1s)
Can only write after partition info set.

cpuset.gb.partition:
Partition info used by group balancer. Tasks in child cgroups (EXCEPT itself) will try to settle at one of given partitions when gb enabled.

/sys/kernel/debug/sched/group_balancer/:
settle_period_ms:
Default settle period for each group.

settle_period_max_ms:
Max settle period for each group.

global_settle_period_ms:
Global settle period for all groups.
For one group, the operation of settling must
satisfy the periods of itself and global.

---
 include/linux/sched/gb.h |  29 +++++++++++
 init/Kconfig             |  12 +++++
 kernel/cgroup/cpuset.c   | 109 +++++++++++++++++++++++++++++++++++++++
 kernel/sched/Makefile    |   1 +
 kernel/sched/debug.c     |  10 +++-
 kernel/sched/gb.c        |  14 +++++
 kernel/sched/sched.h     |   4 ++
 7 files changed, 178 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/sched/gb.h
 create mode 100644 kernel/sched/gb.c
include/linux/sched/gb.h new file +29 -0
new file mode 100644
index 000000000000..63c14289a748
@@ -0,0 +1,29 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ *  Group Balancer header
+ *
+ *  Copyright (C) 2021 Alibaba, Inc., Michael Wang <yun.wang-KPsoFbNs7GizrGE5bRqYAgC/[email protected]>
+ */
+#ifndef _LINUX_SCHED_GB_H
+#define _LINUX_SCHED_GB_H
+
+#include <linux/sched.h>
+
+struct gb_info {
+	/* ---for ancestor as controller--- */
+	/* Period(ns) for task work in task tick, 0 means disabled. */
+	u64 gb_period;
+
+	/* ---for descendants who scheduled by group balancer--- */
+	/* Period for settling to specific partition. */
+	unsigned long settle_period;
+
+	/* Stamp to record next settling. */
+	unsigned long settle_next;
+};
+
+#ifdef CONFIG_GROUP_BALANCER
+extern unsigned int sysctl_gb_settle_period;
+#endif
+
+#endif
init/Kconfig +12 -0
index 8b79eda8e1d4..8f05e5e7e299 100644
@@ -1043,6 +1043,18 @@ config RT_GROUP_SCHED
 	  realtime bandwidth for them.
 	  See Documentation/scheduler/sched-rt-group.rst for more information.
 
+config GROUP_BALANCER
+	bool "Group balancer support for SCHED_OTHER"
+	depends on (CGROUP_SCHED && SMP)
+	default CGROUP_SCHED
+	help
+	  This feature allow you to do load balance in group mode. In other
+	  word, balance groups of tasks among groups of CPUs.
+
+	  This can reduce the conflict between task groups and gain benefit
+	  from hot cache and affinity domain, usually for the cases when there
+	  are multiple apps sharing the same CPUs.
+
 endif #CGROUP_SCHED
 
 config UCLAMP_TASK_GROUP
kernel/cgroup/cpuset.c +109 -0

158 lines not on this page · raw message

kernel/sched/Makefile +1 -0
index c83b37af155b..cb5b86bb161e 100644
@@ -40,3 +40,4 @@ obj-$(CONFIG_MEMBARRIER) += membarrier.o
 obj-$(CONFIG_CPU_ISOLATION) += isolation.o
 obj-$(CONFIG_PSI) += psi.o
 obj-$(CONFIG_SCHED_CORE) += core_sched.o
+obj-$(CONFIG_GROUP_BALANCER) += gb.o
kernel/sched/debug.c +9 -1
index 102d6f70e84d..1800bdfe1d61 100644
@@ -299,7 +299,7 @@ static struct dentry *debugfs_sched;
 
 static __init int sched_init_debug(void)
 {
-	struct dentry __maybe_unused *numa;
+	struct dentry __maybe_unused *numa, *gb;
 
 	debugfs_sched = debugfs_create_dir("sched", NULL);
 
@@ -336,6 +336,14 @@ static __init int sched_init_debug(void)
 	debugfs_create_u32("scan_size_mb", 0644, numa, &sysctl_numa_balancing_scan_size);
 #endif
 
+#ifdef CONFIG_GROUP_BALANCER
+	gb = debugfs_create_dir("group_balancer", debugfs_sched);
+
+	debugfs_create_u32("settle_period_ms", 0644, gb, &sysctl_gb_settle_period);
+	debugfs_create_u32("settle_period_max_ms", 0644, gb, &sysctl_gb_settle_period_max);
+	debugfs_create_u32("global_settle_period_ms", 0644, gb, &sysctl_gb_global_settle_period);
+#endif
+
 	debugfs_create_file("debug", 0444, debugfs_sched, NULL, &sched_debug_fops);
 
 	return 0;
kernel/sched/gb.c new file +14 -0
new file mode 100644
index 000000000000..4a2876ec1cca
@@ -0,0 +1,14 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ *  Group Balancer code
+ *
+ *  Copyright (C) 2021 Alibaba, Inc., Michael Wang <yun.wang-KPsoFbNs7GizrGE5bRqYAgC/[email protected]>
+ */
+#include <linux/sched/gb.h>
+
+#include "sched.h"
+
+/* Params about settle period. (ms) */
+unsigned int sysctl_gb_settle_period = 200;
+unsigned int sysctl_gb_settle_period_max = 10000;
+unsigned int sysctl_gb_global_settle_period = 200;
kernel/sched/sched.h +4 -0
index ac1f9470c617..d6555aacdf78 100644
@@ -2433,6 +2433,10 @@ extern unsigned int sysctl_numa_balancing_scan_delay;
 extern unsigned int sysctl_numa_balancing_scan_period_min;
 extern unsigned int sysctl_numa_balancing_scan_period_max;
 extern unsigned int sysctl_numa_balancing_scan_size;
+
+extern unsigned int sysctl_gb_settle_period;
+extern unsigned int sysctl_gb_settle_period_max;
+extern unsigned int sysctl_gb_global_settle_period;
 #endif
 
 #ifdef CONFIG_SCHED_HRTICK
Signature · 1 line
2.27.0
#2 lore raw

RFC PATCH v2 2/4 cpuset: Handle input of partition info for group balancer

In reply to Tianchen Ding

Partition info is the key param of group balancer. It represents the division of effective cpus. Cpus are divided into several parts, and group balancer will select one part for each cgroup (called settle) and try to gather all tasks of that cgroup running on the cpus of selected part.

For example, the effective cpulist is "0-63". A valid input of partition info can be "0-15;16-31;32-47;48-63;". This divide cpus into 4 parts, each part with 16 cpus.
Intersections between parts or conflicts with effective cpus are not allowd, e.g., "0-40;30-63" or "0-31;32-70;".

Once the partition info is set, the corresponding cgroup becomes a controller. All descendants of it are managed by group balancer, according to params set in this controller cgroup.
A cgroup can become a controller only when its ancestors and descendants are not controller.

To unset a controller, write empty string to it.
(i.e., echo > cpuset.gb.partition)
This will clear its partition info and reset the relationship between itself and its descendants.

Setting, modifying, or unsetting partition info must be done when group balancer is disabled. (i.e., gb.period_us = 0.)

ROOT_CG

   |
   |
   |_________
   |         |
 CG_A       CG_B(controller, gb.partition = "...", gb.period_us > 0)
             |
             |
             |________________
             |                |

CG_C(gb active) CG_D(gb active)
(prefer=0) (prefer=3)

For example, if we input valid partition info "0-15;16-31;32-47;48-63;" and positive period to CG_B, group balancer for all descendants of CG_B is enabled. All tasks in CG_C will tend to run on cpus of part0 (0-15), and all tasks in CG_D will tend to run on part3 (48-63).

After setting partition info, CG_B becomes a controller. So setting another partition info in ROOT_CG, CG_C or CG_D is not allowed until CG_B is disabled and unset. While CG_A can still be set.

---
 include/linux/sched/gb.h |  29 +++++
 kernel/cgroup/cpuset.c   | 245 +++++++++++++++++++++++++++++++++++++--
 2 files changed, 267 insertions(+), 7 deletions(-)
include/linux/sched/gb.h +29 -0
index 63c14289a748..b03a2b4ef4b7 100644
@@ -8,9 +8,30 @@
 #define _LINUX_SCHED_GB_H
 
 #include <linux/sched.h>
+#include <linux/cpumask.h>
+
+#define CPU_PART_MAX		32
+struct gb_part {
+	int id;
+	struct cpumask cpus;
+};
+
+struct gb_part_info {
+	int nr_part;
+	struct rcu_head rcu_head;
+	struct gb_part parts[CPU_PART_MAX];
+	int ctop[NR_CPUS];
+};
 
 struct gb_info {
 	/* ---for ancestor as controller--- */
+	/*
+	 * Partition info. Non-NULL means this cgroup acting as a controller.
+	 * While otherwise, NULL means not a controller.
+	 * (Maybe a descendant of a controller, or not managed by gb at all.)
+	 */
+	struct gb_part_info *part_info;
+
 	/* Period(ns) for task work in task tick, 0 means disabled. */
 	u64 gb_period;
 
@@ -22,6 +43,14 @@ struct gb_info {
 	unsigned long settle_next;
 };
 
+#define for_each_gbpart(i, pi)			\
+	for (i = 0; i < (pi)->nr_part; i++)
+
+static inline struct cpumask *part_cpus(struct gb_part_info *pi, int id)
+{
+	return &pi->parts[id].cpus;
+}
+
 #ifdef CONFIG_GROUP_BALANCER
 extern unsigned int sysctl_gb_settle_period;
 #endif
kernel/cgroup/cpuset.c +238 -7

310 lines not on this page · raw message

Signature · 1 line
2.27.0
#3 lore raw

RFC PATCH v2 3/4 sched: Introduce group balancer

In reply to Tianchen Ding

From: Michael Wang <yun.wang-KPsoFbNs7GizrGE5bRqYAgC/[email protected]>

Modern platform are growing fast on CPU numbers, multiple apps sharing one box are very common, they used to have exclusive cpu setting but nowadays things are changing.

To achieve better utility of CPU resource, multiple apps are starting to sharing the CPUs. The CPU resources usually overcommitted since app's workload are undulated.

This introduced problems on performance when share mode vs exclusive mode, for eg with cgroup A,B and C deployed in exclusive mode, it will be:

  CPU_X (100%)     CPU_Y (100%)     CPU_Z (50%)
  T_1_CG_A         T_1_CG_B         T_1_CG_C
  T_2_CG_A         T_2_CG_B         T_2_CG_C
  T_3_CG_A         T_3_CG_B
  T_4_CG_A         T_4_CG_B

while the share mode will be:

  CPU_X (100%)     CPU_Y (75%)     CPU_Z (75%)
  T_1_CG_A         T_2_CG_A         T_1_CG_B
  T_2_CG_B         T_3_CG_B         T_2_CG_C
  T_4_CG_B         T_4_CG_A         T_3_CG_A

T_1_CG_C

As we can see, the confliction between groups on CPU resources are now happening all over the CPUs.

The testing on sysbench-memory show 30+% drop on share mode, and redis-benchmark show 10+% drop too, compared to the exclusive mode.

However, despite of the performance drop, in real world we still prefer share mode. The undulated workload can make the exclusive mode so unefficient on CPU utilization, for eg the next period, when CG_A become 'idle', exclusive mode will like:

  CPU_X (0%)     CPU_Y (100%)     CPU_Z (50%)
                 T_1_CG_B         T_1_CG_C
                 T_2_CG_B         T_2_CG_C
                 T_3_CG_B
                 T_4_CG_B

while share mode like:

CPU_X (50%) CPU_Y (50%) CPU_Z (50%)

  T_2_CG_B         T_1_CG_C        T_3_CG_B
  T_4_CG_B         T_1_CG_B        T_2_CG_C

The CPU_X is totally wasted in exclusive mode, the resource efficiency are really poor.

Thus what we need, is a way to ease confliction in share mode, make groups as exclusive as possible, to gain both performance and resource efficiency.

The main idea of group balancer is to fulfill this requirement by balancing groups of tasks among groups of CPUs, consider this as a dynamic demi-exclusive mode. Task trigger work to settle it's group into a proper partition (minimum predicted load), then try migrate itself into it. To gradually settle groups into the most exclusively partition.

Just like balance the task among CPUs, now with GB a user can put CPU X,Y,Z into three partitions, and balance group A,B,C into these partition, to make them as exclusive as possible. GB can be seen as an optimize policy based on load balance, it obeys the main idea of load balance and makes adjustment based on that.

How to use:

First, make sure the children of your cgroup both enabling "cpu" and "cpuset" subsys, because group balancer gather load info from task group and partition info from cpuset group. So tasks should stay at the same cgroup. Do this recursively if necessary:
echo "+cpu +cpuset" > $CGROUP_PATH/cgroup.subtree_control

To create partition, for example run:
echo "0-15;16-31;32-47;48-63;" > $CGROUP_PATH/cpuset.gb.partition

This will create 4 partitions contain CPUs 0-15,16-31,32-47 and 48-63 separately.

Then enable GB for your cgroup, run:
echo 200000 > $CGROUP_PATH/cpuset.gb.period_us

This will enable GB for all descendants of $CGROUP_PATH, EXCEPT itself.

Testing Results:
In order to enlarge the differences, we do testing on ARM platform with 128 CPUs, create 8 partition according to cluster info.

Since we pick benchmark which can gain benefit from exclusive mode, this is more like a functional testing rather than performance, to show that GB help winback the performance.

Create 8 cgroup each running 'sysbench memory --threads=16 run', the output of share mode is:

    events/s (eps):                      4939865.8892
    events/s (eps):                      4699033.0351
    events/s (eps):                      4373262.0563
    events/s (eps):                      3534852.1000
    events/s (eps):                      4724359.4354
    events/s (eps):                      3438985.1082
    events/s (eps):                      3600268.9196
    events/s (eps):                      3782130.8202
  the output of gb mode is:
    events/s (eps):                      4919287.0608
    events/s (eps):                      5926525.9995
    events/s (eps):                      4933459.3272
    events/s (eps):                      5184040.1349
    events/s (eps):                      5030940.1116
    events/s (eps):                      5773255.0246
    events/s (eps):                      4649109.0129
    events/s (eps):                      5683217.7641

Create 4 cgroup each running redis-server with 16 io threads, 4 redis-benchmark per each server show average rps as:

                    share mode       gb mode
  PING_INLINE        45903.94        46529.9      1.36%
  PING_MBULK         48342.58        50881.99     5.25%
  SET                38681.95        42108.17     8.86%
  GET                46774.09        51067.99     9.18%
  INCR               46092.24        50543.98     9.66%
  LPUSH              41723.35        45464.73     8.97%
  RPUSH              42722.77        47667.76     11.57%
  LPOP               41010.75        45077.65     9.92%
  RPOP               43198.33        47248.05     9.37%
  SADD               44750.16        50253.79     12.30%
  HSET               44352           47940.12     8.09%
  SPOP               47436.64        51658.99     8.90%
  ZADD               43124.02        45992.96     6.65%
  ZPOPMIN            46854.7         51561.52     10.05%
  LPUSH              41723.35        45464.73     8.97%
  LRANGE_100         22411.47        23311.32     4.02%
  LRANGE_300         11323.8         11585.06     2.31%
  LRANGE_500         7516.12         7577.76      0.82%
  LRANGE_600         6632.1          6737.31      1.59%
  MSET               27945.01        29401.3      5.21%
---
 include/linux/cpuset.h   |   5 +
 include/linux/sched.h    |   5 +
 include/linux/sched/gb.h |  10 +
 kernel/cgroup/cpuset.c   |  39 ++++
 kernel/sched/core.c      |   5 +
 kernel/sched/fair.c      |  26 ++-
 kernel/sched/gb.c        | 448 +++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h     |  10 +
 8 files changed, 547 insertions(+), 1 deletion(-)
include/linux/cpuset.h +5 -0
index d58e0476ee8e..3be2ab42bb98 100644
@@ -178,6 +178,11 @@ static inline void set_mems_allowed(nodemask_t nodemask)
 	task_unlock(current);
 }
 
+#ifdef CONFIG_GROUP_BALANCER
+struct gb_info *task_gi(struct task_struct *p, bool get_controller);
+cpumask_var_t *gi_cpus(struct gb_info *gi);
+#endif
+
 #else /* !CONFIG_CPUSETS */
 
 static inline bool cpusets_enabled(void) { return false; }
include/linux/sched.h +5 -0
index 5e0b5b4a4c8f..fca655770925 100644
@@ -1289,6 +1289,11 @@ struct task_struct {
 	unsigned long			numa_pages_migrated;
 #endif /* CONFIG_NUMA_BALANCING */
 
+#ifdef CONFIG_GROUP_BALANCER
+	u64			gb_stamp;
+	struct callback_head		gb_work;
+#endif
+
 #ifdef CONFIG_RSEQ
 	struct rseq __user *rseq;
 	u32 rseq_sig;
include/linux/sched/gb.h +10 -0
index b03a2b4ef4b7..7af91662b740 100644
@@ -9,10 +9,14 @@
 
 #include <linux/sched.h>
 #include <linux/cpumask.h>
+#include <linux/seq_file.h>
+#include <linux/cgroup-defs.h>
 
 #define CPU_PART_MAX		32
 struct gb_part {
 	int id;
+	unsigned int mgrt_on;
+	u64 predict_load;
 	struct cpumask cpus;
 };
 
@@ -41,6 +45,12 @@ struct gb_info {
 
 	/* Stamp to record next settling. */
 	unsigned long settle_next;
+
+	/*
+	 * Record preferred partition (in part_info of controller) of this cgroup.
+	 * Default -1.
+	 */
+	int gb_prefer;
 };
 
 #define for_each_gbpart(i, pi)			\
kernel/cgroup/cpuset.c +39 -0
index 4b456b379b87..de13c22c1921 100644
@@ -235,6 +235,20 @@ static struct gb_info *css_gi(struct cgroup_subsys_state *css, bool get_controll
 
 	return get_controller ? cs->control_gi : &cs->gi;
 }
+
+struct gb_info *task_gi(struct task_struct *p, bool get_controller)
+{
+	struct cpuset *cs = task_cs(p);
+
+	return cs ? css_gi(&cs->css, get_controller) : NULL;
+}
+
+cpumask_var_t *gi_cpus(struct gb_info *gi)
+{
+	struct cpuset *cs = container_of(gi, struct cpuset, gi);
+
+	return &cs->effective_cpus;
+}
 #else
 static inline struct gb_info *cs_gi(struct cpuset *cs)
 {
@@ -2572,6 +2586,21 @@ static inline void update_child_gb_controller(struct cpuset *cs, struct gb_info
 	rcu_read_unlock();
 }
 
+static inline void reset_child_gb_prefer(struct cpuset *cs)
+{
+	struct cpuset *cp;
+	struct cgroup_subsys_state *pos_css;
+
+	rcu_read_lock();
+	cpuset_for_each_descendant_pre(cp, pos_css, cs) {
+		if (cp == cs)
+			continue;
+
+		cs_gi(cp)->gb_prefer = -1;
+	}
+	rcu_read_unlock();
+}
+
 static inline void update_gb_part_info(struct cpuset *cs, struct gb_part_info *new)
 {
 	struct gb_info *gi = cs_gi(cs);
@@ -2606,6 +2635,7 @@ static inline void init_gb(struct cpuset *cs)
 
 	gi->settle_period = msecs_to_jiffies(sysctl_gb_settle_period);
 	gi->settle_next = jiffies + gi->settle_period;
+	gi->gb_prefer = -1;
 
 	/* Search upwards to find any existing controller. */
 	for (css = cs->css.parent; css; css = css->parent) {
@@ -2637,6 +2667,7 @@ static int gb_period_write_u64(struct cgroup_subsys_state *css, struct cftype *c
 	struct cpuset *cs = css_cs(css);
 	struct gb_info *gi = cs_gi(cs);
 	int retval = -EINVAL;
+	bool reset;
 
 	if (val > MAX_GB_PERIOD)
 		return retval;
@@ -2650,9 +2681,17 @@ static int gb_period_write_u64(struct cgroup_subsys_state *css, struct cftype *c
 	if (!gi->part_info)
 		goto out_unlock;
 
+	/* gb_period = 0 means disabling group balancer. */
+	reset = gi->gb_period && !val;
+
 	gi->gb_period = val * NSEC_PER_USEC;
 	retval = 0;
 
+	if (reset) {
+		synchronize_rcu();
+		reset_child_gb_prefer(cs);
+	}
+
 out_unlock:
 	percpu_up_write(&cpuset_rwsem);
 	return retval;
kernel/sched/core.c +5 -0
index 5e5365755bdd..d57d6210bcfc 100644
@@ -4484,6 +4484,11 @@ int sched_fork(unsigned long clone_flags, struct task_struct *p)
 #ifdef CONFIG_SMP
 	plist_node_init(&p->pushable_tasks, MAX_PRIO);
 	RB_CLEAR_NODE(&p->pushable_dl_tasks);
+#endif
+#ifdef CONFIG_GROUP_BALANCER
+	p->gb_stamp = 0;
+	p->gb_work.next = &p->gb_work;
+	init_task_work(&p->gb_work, group_balancing_work);
 #endif
 	return 0;
 }
kernel/sched/fair.c +25 -1
index 10c8dc9b7494..c1bd3f62e39c 100644
@@ -1609,6 +1609,9 @@ static void update_numa_stats(struct task_numa_env *env,
 			    !cpumask_test_cpu(cpu, env->p->cpus_ptr))
 				continue;
 
+			if (group_hot(env->p, env->src_cpu, cpu) == 0)
+				continue;
+
 			if (ns->idle_cpu == -1)
 				ns->idle_cpu = cpu;
 
@@ -1944,6 +1947,9 @@ static void task_numa_find_cpu(struct task_numa_env *env,
 		if (!cpumask_test_cpu(cpu, env->p->cpus_ptr))
 			continue;
 
+		if (group_hot(env->p, env->src_cpu, cpu) == 0)
+			continue;
+
 		env->dst_cpu = cpu;
 		if (task_numa_compare(env, taskimp, groupimp, maymove))
 			break;
@@ -6050,8 +6056,11 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p,
 		target = wake_affine_weight(sd, p, this_cpu, prev_cpu, sync);
 
 	schedstat_inc(p->stats.nr_wakeups_affine_attempts);
-	if (target == nr_cpumask_bits)
+	if (target == nr_cpumask_bits) {
+		if (group_hot(p, prev_cpu, this_cpu) == 1)
+			return this_cpu;
 		return prev_cpu;
+	}
 
 	schedstat_inc(sd->ttwu_move_affine);
 	schedstat_inc(p->stats.nr_wakeups_affine);
@@ -7846,6 +7855,10 @@ int can_migrate_task(struct task_struct *p, struct lb_env *env)
 		return 0;
 	}
 
+	tsk_cache_hot = group_hot(p, env->src_cpu, env->dst_cpu);
+	if (tsk_cache_hot != -1)
+		return tsk_cache_hot;
+
 	/*
 	 * Aggressive migration if:
 	 * 1) active balance
@@ -8266,6 +8279,15 @@ static unsigned long task_h_load(struct task_struct *p)
 	return div64_ul(p->se.avg.load_avg * cfs_rq->h_load,
 			cfs_rq_load_avg(cfs_rq) + 1);
 }
+
+#ifdef CONFIG_GROUP_BALANCER
+unsigned long cfs_h_load(struct cfs_rq *cfs_rq)
+{
+	update_cfs_rq_h_load(cfs_rq);
+	return cfs_rq->h_load;
+}
+#endif
+
 #else
 static bool __update_blocked_fair(struct rq *rq, bool *done)
 {
@@ -11213,6 +11235,8 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
 	if (static_branch_unlikely(&sched_numa_balancing))
 		task_tick_numa(rq, curr);
 
+	task_tick_gb(rq, curr);
+
 	update_misfit_status(curr, rq);
 	update_overutilized_status(task_rq(curr));
 
kernel/sched/gb.c +448 -0

455 lines not on this page · raw message

kernel/sched/sched.h +10 -0
index d6555aacdf78..97c621bcded3 100644
@@ -3148,3 +3148,13 @@ extern int sched_dynamic_mode(const char *str);
 extern void sched_dynamic_update(int mode);
 #endif
 
+#ifdef CONFIG_GROUP_BALANCER
+extern unsigned long cfs_h_load(struct cfs_rq *cfs_rq);
+extern int group_hot(struct task_struct *p, int src_cpu, int dst_cpu);
+extern void task_tick_gb(struct rq *rq, struct task_struct *curr);
+extern void group_balancing_work(struct callback_head *work);
+#else
+static inline int group_hot(struct task_struct *p, int src_cpu, int dst_cpu) { return -1; }
+static inline void task_tick_gb(struct rq *rq, struct task_struct *curr) {};
+static inline void group_balancing_work(struct callback_head *work) {};
+#endif
Signature · 1 line
2.27.0
#4 lore raw

RFC PATCH v2 4/4 cpuset, gb: Add stat for group balancer

In reply to Tianchen Ding

When group balancer is enabled by:
echo 200000 > $CGROUP_PATH/cpuset.gb.period_us

Then you can check:
$CPU_CGROUP_PATH/childX/cpuset.gb.stat

which give output as:
PART-0 0-15 1008 1086 *
PART-1 16-31 0 2
PART-2 32-47 0 0
PART-3 48-63 0 1024

The partition ID followed by it's CPUs range, load of group, load of partition and a star mark as preferred.

---
 include/linux/sched/gb.h |  2 ++
 kernel/cgroup/cpuset.c   | 24 ++++++++++++++++++++++++
 kernel/sched/gb.c        | 25 +++++++++++++++++++++++++
 3 files changed, 51 insertions(+)
include/linux/sched/gb.h +2 -0
index 7af91662b740..ec5a97d8160a 100644
@@ -63,6 +63,8 @@ static inline struct cpumask *part_cpus(struct gb_part_info *pi, int id)
 
 #ifdef CONFIG_GROUP_BALANCER
 extern unsigned int sysctl_gb_settle_period;
+int gb_stat_show(struct seq_file *sf, struct cgroup_subsys_state *css,
+		 struct gb_info *gi, struct gb_part_info *pi);
 #endif
 
 #endif
kernel/cgroup/cpuset.c +24 -0
index de13c22c1921..035606e8fa95 100644
@@ -2863,6 +2863,24 @@ static ssize_t gb_partition_write(struct kernfs_open_file *of, char *buf,
 	cpus_read_unlock();
 	return retval ?: nbytes;
 }
+
+static int gb_stat_seq_show(struct seq_file *sf, void *v)
+{
+	struct cgroup_subsys_state *css = seq_css(sf);
+	struct gb_info *control_gi;
+	int retval = -EINVAL;
+
+	rcu_read_lock();
+	control_gi = css_gi(css, true);
+	if (!control_gi || !control_gi->gb_period)
+		goto out_unlock;
+
+	retval = gb_stat_show(sf, css, css_gi(css, false), control_gi->part_info);
+
+out_unlock:
+	rcu_read_unlock();
+	return retval;
+}
 #else
 static inline void init_gb(struct cpuset *cs) { }
 static inline void remove_gb(struct cpuset *cs) { }
@@ -3179,6 +3197,12 @@ static struct cftype dfl_files[] = {
 		.max_write_len = (100U + 6 * NR_CPUS),
 		.private = FILE_GB_CPULIST,
 	},
+
+	{
+		.name = "gb.stat",
+		.seq_show = gb_stat_seq_show,
+		.flags = CFTYPE_NOT_ON_ROOT,
+	},
 #endif
 	{ }	/* terminate */
 };
kernel/sched/gb.c +25 -0
index f7da96253ad0..8ae1db83b587 100644
@@ -46,6 +46,31 @@ static u64 load_of_part(struct gb_part_info *pi, int id)
 	return load;
 }
 
+int gb_stat_show(struct seq_file *sf, struct cgroup_subsys_state *css,
+		 struct gb_info *gi, struct gb_part_info *pi)
+{
+	struct cgroup_subsys_state *tg_css;
+	struct task_group *tg;
+	int i;
+
+	tg_css = cgroup_e_css(css->cgroup, &cpu_cgrp_subsys);
+	/* Make sure that "cpu" and "cpuset" subsys belonging to the same cgroup. */
+	if (tg_css->cgroup != css->cgroup)
+		return -EINVAL;
+	tg = container_of(tg_css, struct task_group, css);
+
+	for_each_gbpart(i, pi) {
+		seq_printf(sf, "PART-%d ", i);
+		seq_printf(sf, "%*pbl ", cpumask_pr_args(part_cpus(pi, i)));
+		seq_printf(sf, "%llu ", tg_load_of_part(pi, tg, i));
+		seq_printf(sf, "%llu ", load_of_part(pi, i));
+		if (gi->gb_prefer == i)
+			seq_puts(sf, " *");
+		seq_putc(sf, '\n');
+	}
+	return 0;
+}
+
 static inline int part_mgrt_lock(struct gb_part_info *pi, int src, int dst)
 {
 	struct gb_part *src_part, *dst_part;
Signature · 1 line
2.27.0
maintainer
#5 lore raw
In reply to Tianchen Ding

Hello,

Quoted 14 lines · Tianchen Ding

Modern platform are growing fast on CPU numbers. To achieve better utility of CPU resource, multiple apps are starting to sharing the CPUs.

What we need is a way to ease confliction in share mode, make groups as exclusive as possible, to gain both performance and resource efficiency.

The main idea of group balancer is to fulfill this requirement by balancing groups of tasks among groups of CPUs, consider this as a dynamic demi-exclusive mode. Task trigger work to settle it's group into a proper partition (minimum predicted load), then try migrate itself into it. To gradually settle groups into the most exclusively partition.

Quoted 7 lines

GB can be seen as an optimize policy based on load balance, it obeys the main idea of load balance and makes adjustment based on that.

Our test on ARM64 platform with 128 CPUs shows that, throughput of sysbench memory is improved about 25%, and redis-benchmark is improved up to about 10%.

The motivation makes sense to me but I'm not sure this is the right way to architecture it. We already have the framework to do all these - the sched domains and the load balancer. Architecturally, what the suggested patchset is doing is building a separate load balancer on top of cpuset after using cpuset to disable the existing load balancer, which is rather obviously convoluted.

* AFAICS, none of what the suggested code does is all that complicated or needs a lot of input from userspace. it should be possible to parametrize the existing load balancer to behave better.

* If, for some reason, you need more customizable behavior in terms of cpu allocation, which is what cpuset is for, maybe it'd be better to build the load balancer in userspace. That'd fit way better with how cgroup is used in general and with threaded cgroups, it should fit nicely with everything else.

Thanks.

Signature · 1 line
tejun
#6 lore raw
Quoted 25 lines · Tejun Heo

Hello,

Quoted 14 lines · Tianchen Ding

Modern platform are growing fast on CPU numbers. To achieve better utility of CPU resource, multiple apps are starting to sharing the CPUs.

What we need is a way to ease confliction in share mode, make groups as exclusive as possible, to gain both performance and resource efficiency.

The main idea of group balancer is to fulfill this requirement by balancing groups of tasks among groups of CPUs, consider this as a dynamic demi-exclusive mode. Task trigger work to settle it's group into a proper partition (minimum predicted load), then try migrate itself into it. To gradually settle groups into the most exclusively partition.

Quoted 7 lines

GB can be seen as an optimize policy based on load balance, it obeys the main idea of load balance and makes adjustment based on that.

Our test on ARM64 platform with 128 CPUs shows that, throughput of sysbench memory is improved about 25%, and redis-benchmark is improved up to about 10%.

Quoted 7 lines

The motivation makes sense to me but I'm not sure this is the right way to architecture it. We already have the framework to do all these - the sched domains and the load balancer. Architecturally, what the suggested patchset is doing is building a separate load balancer on top of cpuset after using cpuset to disable the existing load balancer, which is rather obviously convoluted.

"the sched domains and the load balancer" you mentioned are the ways to "balance" tasks on each domains. However, this patchset aims to "group" them together to win hot cache and less competition, which is different from load balancer. See commit log of the patch 3/4 and this link:
https://lore.kernel.org/all/11d4c86a-40ef-6ce5-6d08-e9d0bc9b512a-KPsoFbNs7GizrGE5bRqYAgC/[email protected]/

Quoted 4 lines

* AFAICS, none of what the suggested code does is all that complicated or needs a lot of input from userspace. it should be possible to parametrize the existing load balancer to behave better.

Group balancer mainly needs 2 inputs from userspace: cpu partition info and cgroup info.
Cpu partition info does need user input (and maybe a bit complicated). As a result, the division methods are __free__ to users(can refer to NUMA nodes, clusters, cache, etc.) Cgroup info doesn't need extra input. It's naturally configured.

It do parametrize the existing load balancer to behave better.
Group balancer is a kind of optimize policy, and should obey the basic
policy (load balance) and improve it.
The relationship between load balancer and group balancer is explained in detail at the above link.

Quoted 6 lines

* If, for some reason, you need more customizable behavior in terms of cpu allocation, which is what cpuset is for, maybe it'd be better to build the load balancer in userspace. That'd fit way better with how cgroup is used in general and with threaded cgroups, it should fit nicely with everything else.

We put group balancer in kernel space because this new policy does not depend on userspace apps. It's a "general" feature.
Doing "dynamic cpuset" in userspace may also introduce performance issue, since it may need to bind and unbind different cpusets for several times, and is too strict(compared with our "soft bind").

maintainer
#7 lore raw

Hello,

Quoted 5 lines · Tianchen Ding

"the sched domains and the load balancer" you mentioned are the ways to "balance" tasks on each domains. However, this patchset aims to "group" them together to win hot cache and less competition, which is different from load balancer. See commit log of the patch 3/4 and this link:
https://lore.kernel.org/all/11d4c86a-40ef-6ce5-6d08-e9d0bc9b512a-KPsoFbNs7GizrGE5bRqYAgC/[email protected]/

I read that but it doesn't make whole lot of sense to me. As Peter noted, we already have issues with cross NUMA node balancing interacting with in-node balancing, which likely indicates that it needs more unified solution rather than more fragmented. I have a hard time seeing how adding yet another layer on top helps the situation.

Quoted 9 lines
Quoted 6 lines

* If, for some reason, you need more customizable behavior in terms of cpu allocation, which is what cpuset is for, maybe it'd be better to build the load balancer in userspace. That'd fit way better with how cgroup is used in general and with threaded cgroups, it should fit nicely with everything else.

We put group balancer in kernel space because this new policy does not depend on userspace apps. It's a "general" feature.

Well, it's general for use cases which are happy with the two knobs that you defined for your use case.

Quoted 3 lines

Doing "dynamic cpuset" in userspace may also introduce performance issue, since it may need to bind and unbind different cpusets for several times, and is too strict(compared with our "soft bind").

My bet is that you're gonna be able to get just about the same bench results with userspace diddling with thread cgroup membership. Why not try that first? The interface is already there. I have a hard time seeing the justification for hard coding this into the kernel at this stage.

Thanks.

Signature · 1 line
tejun
#8 lore raw
Quoted 32 lines · Tejun Heo

Hello,

Quoted 5 lines · Tianchen Ding

"the sched domains and the load balancer" you mentioned are the ways to "balance" tasks on each domains. However, this patchset aims to "group" them together to win hot cache and less competition, which is different from load balancer. See commit log of the patch 3/4 and this link:
https://lore.kernel.org/all/11d4c86a-40ef-6ce5-6d08-e9d0bc9b512a-KPsoFbNs7GizrGE5bRqYAgC/[email protected]/

I read that but it doesn't make whole lot of sense to me. As Peter noted, we already have issues with cross NUMA node balancing interacting with in-node balancing, which likely indicates that it needs more unified solution rather than more fragmented. I have a hard time seeing how adding yet another layer on top helps the situation.

Quoted 9 lines
Quoted 6 lines

* If, for some reason, you need more customizable behavior in terms of cpu allocation, which is what cpuset is for, maybe it'd be better to build the load balancer in userspace. That'd fit way better with how cgroup is used in general and with threaded cgroups, it should fit nicely with everything else.

We put group balancer in kernel space because this new policy does not depend on userspace apps. It's a "general" feature.

Well, it's general for use cases which are happy with the two knobs that you defined for your use case.

Quoted 3 lines

Doing "dynamic cpuset" in userspace may also introduce performance issue, since it may need to bind and unbind different cpusets for several times, and is too strict(compared with our "soft bind").

Quoted 7 lines

My bet is that you're gonna be able to get just about the same bench results with userspace diddling with thread cgroup membership. Why not try that first? The interface is already there. I have a hard time seeing the justification for hard coding this into the kernel at this stage.

Thanks.

Well, I understand your point is putting this in userspace. However, we've considered about that but found it hard to do so. If you have any better idea, please share with us. :-)

If we want to build group balancer in userspace, we need:
1) gather load info from each rq periodically
2) make decision to set cpuset.cpus of each cgroup

However, there're some problems about this way.

For 1), we need to consider how frequently collecting these info, which may impact performance and accuracy. If the load changes hugely right after we get it once, our data are expired and then the decision may be wrong. (If we are in kernel, faster action can be taken.)

We believe 2) is harder. The specific policy may be complex and alter according to different scenes. There's not a general method.
e.g., with 16cpus and 4 cgroups, how to decide when we set one of them 0-3(when busy)or 0-7(when some of other cgroups are idle)? If there are much more threads in cgroupA than cgroupB/C/D , and we want to satisfy cgroupA as far as possible(on the premise of fairness of B/C/D), dynamically enlarging(when B/C/D partly idle) and shrinking(when B/C/D busy) cpuset of cgroupA requires complex policy. In this example, fairness and performance can be provided by existing scheduler, but when it comes to grouping hot cache or decreasing competion, both scheduler in kernel and action in userspace are hard to solve. What's more, in many cloud computing scenes, there may be hundreds or thousands of containers, which are much larger than partition number. These containers may be dynamically created and destroyed at any time. Making policy to manage them from userspace will not be practical.

These problems become easy when going to kernelspace. We get info directly from scheduler, and help revising its decision at some key points, or do some support work(e.g., task migration if possible).

Thanks.

maintainer
#9 lore raw

Hello,

Quoted 10 lines · Tianchen Ding

If we want to build group balancer in userspace, we need:
1) gather load info from each rq periodically
2) make decision to set cpuset.cpus of each cgroup

However, there're some problems about this way.

For 1), we need to consider how frequently collecting these info, which may impact performance and accuracy. If the load changes hugely right after we get it once, our data are expired and then the decision may be wrong. (If we are in kernel, faster action can be taken.)

We now have a pretty well established way to transport data to userspace at really low overhead. If you piggy back on bpf interfaces, they can usually be pretty unintrusive and low effort as long as you have the right kind of data aggregated already, which shouldn't be that difficult here.

Quoted 11 lines

We believe 2) is harder. The specific policy may be complex and alter according to different scenes. There's not a general method. e.g., with 16cpus and 4 cgroups, how to decide when we set one of them 0-3(when busy)or 0-7(when some of other cgroups are idle)? If there are much more threads in cgroupA than cgroupB/C/D , and we want to satisfy cgroupA as far as possible(on the premise of fairness of B/C/D), dynamically enlarging(when B/C/D partly idle) and shrinking(when B/C/D busy) cpuset of cgroupA requires complex policy. In this example, fairness and performance can be provided by existing scheduler, but when it comes to grouping hot cache or decreasing competion, both scheduler in kernel and action in userspace are hard to solve.

So, I get that it's not easy. In fact, we don't even yet know how to properly compare loads across groups of CPUs - simple sums that you're using break down when there are big gaps in weight numbers across tasks and can become meaningless in the presence of CPU affinities. They can still work when the configuration is fairly homogeenous and controlled but the standard should be far higher for something we bake into the kernel and expose userland-visible interface for.

Quoted 8 lines

What's more, in many cloud computing scenes, there may be hundreds or thousands of containers, which are much larger than partition number. These containers may be dynamically created and destroyed at any time. Making policy to manage them from userspace will not be practical.

These problems become easy when going to kernelspace. We get info directly from scheduler, and help revising its decision at some key points, or do some support work(e.g., task migration if possible).

I don't think they become necessarily easy. Sure, you can hack up something which works for some cases by poking into existing code; however, the bar for acceptance is also way higher for a kernel interface - it should be generic, consistent with other interfaces (I won't go into cgroup interface issues here), and work orthogonally with other kernel features (ie. task / group weights should work in an explainable way). I don't think the proposed patches are scoring high in those axes.

I'm not against the goal here. Given that cgroups express the logical structure of applications running on the system, it does make sense to factor that into scheduling decisions. However, what's proposed seems too premature and I have a hard time seeing why this level of functionality would be difficult to be implement from userspace with some additions in terms of visibility which is really easy to do these days.

Thanks.

Signature · 1 line
tejun
#10 lore raw
Quoted 14 lines · Tejun Heo

Hello,

Quoted 10 lines · Tianchen Ding

If we want to build group balancer in userspace, we need:
1) gather load info from each rq periodically
2) make decision to set cpuset.cpus of each cgroup

However, there're some problems about this way.

For 1), we need to consider how frequently collecting these info, which may impact performance and accuracy. If the load changes hugely right after we get it once, our data are expired and then the decision may be wrong. (If we are in kernel, faster action can be taken.)

Quoted 5 lines

We now have a pretty well established way to transport data to userspace at really low overhead. If you piggy back on bpf interfaces, they can usually be pretty unintrusive and low effort as long as you have the right kind of data aggregated already, which shouldn't be that difficult here.

Yes, bpf is a good way to fetch these data.
In fact we may also consider impacting on some decisions of scheduler in some scenes. But it seems to be a long term work...

Quoted 12 lines
Quoted 11 lines

We believe 2) is harder. The specific policy may be complex and alter according to different scenes. There's not a general method. e.g., with 16cpus and 4 cgroups, how to decide when we set one of them 0-3(when busy)or 0-7(when some of other cgroups are idle)? If there are much more threads in cgroupA than cgroupB/C/D , and we want to satisfy cgroupA as far as possible(on the premise of fairness of B/C/D), dynamically enlarging(when B/C/D partly idle) and shrinking(when B/C/D busy) cpuset of cgroupA requires complex policy. In this example, fairness and performance can be provided by existing scheduler, but when it comes to grouping hot cache or decreasing competion, both scheduler in kernel and action in userspace are hard to solve.

Quoted 4 lines

So, I get that it's not easy. In fact, we don't even yet know how to properly compare loads across groups of CPUs - simple sums that you're using break down when there are big gaps in weight numbers across tasks and can become meaningless in the presence of CPU affinities. They can still work

"simple sums" is fine because we only use this load when selecting partitions, not migrating.

If I understand correctly, do you mean a scene that:
cgroupA has only one thread with full busy load (1024) cgroup B/C/D have many threads with small load (maybe 100) There're two CPU partitons:0-3 and 4-7

If A choose 0-3 (we suppose its thread sticking on cpu0), so the load of partition 0-3 becomes 1024 because simple sums. So B/C/D will all choose partition 4-7. This will be fine since our group balancer is a kind of "soft" bind. If we are waking a thread from cgroupB and find there is no free cpu in 4-7, we'll fallback to normal path and select other idle cpu (i.e., 1-3) if possible. Otherwise, if there is no idle cpu totally, meaning the whole system is busy. The existing load balance mechanism will handle it, and our patches only try to switch two tasks if their cache in their own cgroups can be closer after migration.

Quoted 4 lines

when the configuration is fairly homogeenous and controlled but the standard should be far higher for something we bake into the kernel and expose userland-visible interface for.

Our aim is to improve performance of apps, so will not limit cpu usage strictly. This kind of soft bind also helps to avoid conflicts with existing load balance mechanism. We may explain this in document.

Quoted 9 lines
Quoted 8 lines

What's more, in many cloud computing scenes, there may be hundreds or thousands of containers, which are much larger than partition number. These containers may be dynamically created and destroyed at any time. Making policy to manage them from userspace will not be practical.

These problems become easy when going to kernelspace. We get info directly from scheduler, and help revising its decision at some key points, or do some support work(e.g., task migration if possible).

Quoted 8 lines

I don't think they become necessarily easy. Sure, you can hack up something which works for some cases by poking into existing code; however, the bar for acceptance is also way higher for a kernel interface - it should be generic, consistent with other interfaces (I won't go into cgroup interface issues here), and work orthogonally with other kernel features (ie. task / group weights should work in an explainable way). I don't think the proposed patches are scoring high in those axes.

We set the interface into cpuset subsys because partition info should follow effective_cpus. There may be a problem that we need to get load info from cpu subsys, so "cpu" and "cpuset" should be both enabled in the same cgroup. Fortunately, this is easy in cgroup-v2. Any other conflict do you see?

About "work orthogonally with other kernel features", we've explained above. Weights are only used in selecting partitions and we just tend to trying pulling tasks to their selected partitions, not force.

Quoted 6 lines

I'm not against the goal here. Given that cgroups express the logical structure of applications running on the system, it does make sense to factor that into scheduling decisions. However, what's proposed seems too premature and I have a hard time seeing why this level of functionality would be difficult to be implement from userspace with some additions in terms of visibility which is really easy to do these days.

Just as out explanation in the last mail, we believe building this in userspace is not easy. Because interfaces provided by kernel now is inflexible. From the view of cgroup, it is given a binded "cpuset.cpus", and all cpus in this range are treated equally, while all cpus out of this range are strictly forbidden. The existing cpuset mechanisms do help resource limitation and isolation, but may be weak on improving perforamce.

So, our idea is, doing this in userspace, which relies on existing kernel interfaces, is hard. Only exposing more data to increase visibility in userspace is not enough. We need a whole solution from collecting data to impacting decisions of the scheduler. Maybe eBPF can cover all these works in the future, but it takes long time to develop and maybe too much to achieve just dynamic cpu bind.

Thanks.

#11 lore raw
In reply to Tianchen Ding

Ping~
Any idea for this patchset? :-)

Quoted 56 lines · Tianchen Ding

Modern platform are growing fast on CPU numbers. To achieve better utility of CPU resource, multiple apps are starting to sharing the CPUs.

What we need is a way to ease confliction in share mode, make groups as exclusive as possible, to gain both performance and resource efficiency.

The main idea of group balancer is to fulfill this requirement by balancing groups of tasks among groups of CPUs, consider this as a dynamic demi-exclusive mode. Task trigger work to settle it's group into a proper partition (minimum predicted load), then try migrate itself into it. To gradually settle groups into the most exclusively partition.

GB can be seen as an optimize policy based on load balance, it obeys the main idea of load balance and makes adjustment based on that.

Our test on ARM64 platform with 128 CPUs shows that, throughput of sysbench memory is improved about 25%, and redis-benchmark is improved up to about 10%.

See each patch for detail:
The 1st patch introduces infrastructure.
The 2nd patch introduces detail about partition info. The 3rd patch is the main part of group balancer. The 4th patch is about stats.

v2:
Put partition info and period settings to cpuset subsys of cgroup_v2.

v1: https://lore.kernel.org/all/98f41efd-74b2-198a-839c-51b785b748a6-KPsoFbNs7GizrGE5bRqYAgC/[email protected]/

Michael Wang (1):
sched: Introduce group balancer

Tianchen Ding (3):
sched, cpuset: Introduce infrastructure of group balancer
cpuset: Handle input of partition info for group balancer cpuset, gb: Add stat for group balancer

  include/linux/cpuset.h   |   5 +
  include/linux/sched.h    |   5 +
  include/linux/sched/gb.h |  70 ++++++
  init/Kconfig             |  12 +
  kernel/cgroup/cpuset.c   | 405 +++++++++++++++++++++++++++++++-
  kernel/sched/Makefile    |   1 +
  kernel/sched/core.c      |   5 +
  kernel/sched/debug.c     |  10 +-
  kernel/sched/fair.c      |  26 ++-
  kernel/sched/gb.c        | 487 +++++++++++++++++++++++++++++++++++++++
  kernel/sched/sched.h     |  14 ++
  11 files changed, 1037 insertions(+), 3 deletions(-)

create mode 100644 include/linux/sched/gb.h
create mode 100644 kernel/sched/gb.c