kernel/sched/ems/load_balance.c

   1 /*
   2  * Load balance - Exynos Mobile Scheduler
   3  *
   4  * Copyright (C) 2018 Samsung Electronics Co., Ltd
   5  * Lakkyung Jung <lakkyung.jung@samsung.com>
   6  */
   7
   8 #include <linux/sched.h>
   9 #include <linux/cpuidle.h>
  10 #include <linux/pm_qos.h>
  11 #include <linux/sched/energy.h>
  12 #include <linux/ems.h>
  13
  14 #include <trace/events/ems.h>
  15
  16 #include "ems.h"
  17 #include "../sched.h"
  18 #include "../tune.h"
  19
  20 struct list_head *lb_cfs_tasks(struct rq *rq, int sse)
  21 {
  22         return sse ? &rq->sse_cfs_tasks : &rq->uss_cfs_tasks;
  23 }
  24
  25 void lb_add_cfs_task(struct rq *rq, struct sched_entity *se)
  26 {
  27         struct list_head *tasks = lb_cfs_tasks(rq, task_of(se)->sse);
  28
  29         list_add(&se->group_node, tasks);
  30 }
  31
  32 int lb_check_priority(int src_cpu, int dst_cpu)
  33 {
  34         if (capacity_orig_of_sse(dst_cpu, 0) > capacity_orig_of_sse(src_cpu, 0))
  35                 return 0;
  36         else if (capacity_orig_of_sse(dst_cpu, 1) > capacity_orig_of_sse(src_cpu, 1))
  37                 return 1;
  38         else
  39                 return 0;
  40 }
  41
  42 struct list_head *lb_prefer_cfs_tasks(int src_cpu, int dst_cpu)
  43 {
  44         struct rq *src_rq = cpu_rq(src_cpu);
  45         int sse = lb_check_priority(src_cpu, dst_cpu);
  46         struct list_head *tasks;
  47
  48         tasks = lb_cfs_tasks(src_rq, sse);
  49         if (!list_empty(tasks))
  50                 return tasks;
  51
  52         return lb_cfs_tasks(src_rq, !sse);
  53 }
  54
  55 static inline int
  56 check_cpu_capacity(struct rq *rq, struct sched_domain *sd)
  57 {
  58         return ((rq->cpu_capacity * sd->imbalance_pct) <
  59                                 (rq->cpu_capacity_orig * 100));
  60 }
  61
  62 #define lb_sd_parent(sd) \
  63         (sd->parent && sd->parent->groups != sd->parent->groups->next)
  64
  65 int lb_need_active_balance(enum cpu_idle_type idle, struct sched_domain *sd,
  66                                         int src_cpu, int dst_cpu)
  67 {
  68         struct task_struct *p = cpu_rq(src_cpu)->curr;
  69         unsigned int src_imb_pct = lb_sd_parent(sd) ? sd->imbalance_pct : 1;
  70         unsigned int dst_imb_pct = lb_sd_parent(sd) ? 100 : 1;
  71         unsigned long src_cap = capacity_orig_of_sse(src_cpu, p->sse);
  72         unsigned long dst_cap = capacity_orig_of_sse(dst_cpu, p->sse);
  73
  74         int level = sd->level;
  75
  76         /* dst_cpu is idle */
  77         if ((idle != CPU_NOT_IDLE) &&
  78             (cpu_rq(src_cpu)->cfs.h_nr_running == 1)) {
  79                 if ((check_cpu_capacity(cpu_rq(src_cpu), sd)) &&
  80                     (src_cap * sd->imbalance_pct < dst_cap * 100)) {
  81                         return 1;
  82                 }
  83
  84                 /* This domain is top and dst_cpu is bigger than src_cpu*/
  85                 if (!lb_sd_parent(sd) && src_cap < dst_cap)
  86                         if (lbt_overutilized(src_cpu, level) || global_boosted())
  87                                 return 1;
  88         }
  89
  90         if ((src_cap * src_imb_pct < dst_cap * dst_imb_pct) &&
  91                         cpu_rq(src_cpu)->cfs.h_nr_running == 1 &&
  92                         lbt_overutilized(src_cpu, level) &&
  93                         !lbt_overutilized(dst_cpu, level)) {
  94                 return 1;
  95         }
  96
  97         return unlikely(sd->nr_balance_failed > sd->cache_nice_tries + 2);
  98 }
  99
 100 /****************************************************************/
 101 /*                      Load Balance Trigger                    */
 102 /****************************************************************/
 103 #define DISABLE_OU              -1
 104 #define DEFAULT_OU_RATIO        80
 105
 106 struct lbt_overutil {
 107         bool                    top;
 108         struct cpumask          cpus;
 109         unsigned long           capacity;
 110         int                     ratio;
 111 };
 112 DEFINE_PER_CPU(struct lbt_overutil *, lbt_overutil);
 113
 114 static inline struct sched_domain *find_sd_by_level(int cpu, int level)
 115 {
 116         struct sched_domain *sd;
 117
 118         for_each_domain(cpu, sd) {
 119                 if (sd->level == level)
 120                         return sd;
 121         }
 122
 123         return NULL;
 124 }
 125
 126 static inline int get_topology_depth(void)
 127 {
 128         struct sched_domain *sd;
 129
 130         for_each_domain(0, sd) {
 131                 if (sd->parent == NULL)
 132                         return sd->level;
 133         }
 134
 135         return -1;
 136 }
 137
 138 static inline int get_last_level(struct lbt_overutil *ou)
 139 {
 140         int level, depth = get_topology_depth();
 141
 142         for (level = 0; level <= depth ; level++) {
 143                 if (&ou[level] == NULL)
 144                         return -1;
 145
 146                 if (ou[level].top == true)
 147                         return level;
 148         }
 149
 150         return -1;
 151 }
 152
 153 /****************************************************************/
 154 /*                      External APIs                           */
 155 /****************************************************************/
 156 bool lbt_overutilized(int cpu, int level)
 157 {
 158         struct lbt_overutil *ou = per_cpu(lbt_overutil, cpu);
 159         bool overutilized;
 160
 161         if (!ou)
 162                 return false;
 163
 164         overutilized = (ml_cpu_util(cpu) > ou[level].capacity) ? true : false;
 165
 166         if (overutilized)
 167                 trace_ems_lbt_overutilized(cpu, level, ml_cpu_util(cpu),
 168                                 ou[level].capacity, overutilized);
 169
 170         return overutilized;
 171 }
 172
 173 void update_lbt_overutil(int cpu, unsigned long capacity)
 174 {
 175         struct lbt_overutil *ou = per_cpu(lbt_overutil, cpu);
 176         int level, last = get_last_level(ou);
 177
 178         for (level = 0; level <= last; level++) {
 179                 if (ou[level].ratio == DISABLE_OU)
 180                         continue;
 181
 182                 ou[level].capacity = (capacity * ou[level].ratio) / 100;
 183         }
 184 }
 185
 186 /****************************************************************/
 187 /*                              SYSFS                           */
 188 /****************************************************************/
 189 #define lbt_attr_init(_attr, _name, _mode, _show, _store)               \
 190         sysfs_attr_init(&_attr.attr);                                   \
 191         _attr.attr.name = _name;                                        \
 192         _attr.attr.mode = VERIFY_OCTAL_PERMISSIONS(_mode);              \
 193         _attr.show      = _show;                                        \
 194         _attr.store     = _store;
 195
 196 static struct kobject *lbt_kobj;
 197 static struct attribute **lbt_attrs;
 198 static struct kobj_attribute *lbt_kattrs;
 199 static struct attribute_group lbt_group;
 200
 201 static ssize_t show_overutil_ratio(struct kobject *kobj,
 202                 struct kobj_attribute *attr, char *buf)
 203 {
 204         struct lbt_overutil *ou = per_cpu(lbt_overutil, 0);
 205         int level = attr - lbt_kattrs;
 206         int cpu, ret = 0;
 207
 208         for_each_possible_cpu(cpu) {
 209                 ou = per_cpu(lbt_overutil, cpu);
 210
 211                 if (ou[level].ratio == DISABLE_OU)
 212                         continue;
 213
 214                 ret += sprintf(buf + ret, "cpu%d ratio:%3d capacity:%4lu\n",
 215                                 cpu, ou[level].ratio, ou[level].capacity);
 216         }
 217
 218         return ret;
 219 }
 220
 221 static ssize_t store_overutil_ratio(struct kobject *kobj,
 222                 struct kobj_attribute *attr, const char *buf,
 223                 size_t count)
 224 {
 225         struct lbt_overutil *ou;
 226         unsigned long capacity;
 227         int level = attr - lbt_kattrs;
 228         int cpu, ratio;
 229
 230         if (sscanf(buf, "%d %d", &cpu, &ratio) != 2)
 231                 return -EINVAL;
 232
 233         /* Check cpu is possible */
 234         if (!cpumask_test_cpu(cpu, cpu_possible_mask))
 235                 return -EINVAL;
 236         ou = per_cpu(lbt_overutil, cpu);
 237
 238         /* If ratio is outrage, disable overutil */
 239         if (ratio < 0 || ratio > 100)
 240                 ratio = DEFAULT_OU_RATIO;
 241
 242         for_each_cpu(cpu, &ou[level].cpus) {
 243                 ou = per_cpu(lbt_overutil, cpu);
 244                 if (ou[level].ratio == DISABLE_OU)
 245                         continue;
 246
 247                 ou[level].ratio = ratio;
 248                 capacity = capacity_orig_of(cpu);
 249                 update_lbt_overutil(cpu, capacity);
 250         }
 251
 252         return count;
 253 }
 254
 255 static int alloc_lbt_sysfs(int size)
 256 {
 257         if (size < 0)
 258                 return -EINVAL;
 259
 260         lbt_attrs = kzalloc(sizeof(struct attribute *) * (size + 1),
 261                         GFP_KERNEL);
 262         if (!lbt_attrs)
 263                 goto fail_alloc;
 264
 265         lbt_kattrs = kzalloc(sizeof(struct kobj_attribute) * (size),
 266                         GFP_KERNEL);
 267         if (!lbt_kattrs)
 268                 goto fail_alloc;
 269
 270         return 0;
 271
 272 fail_alloc:
 273         kfree(lbt_attrs);
 274         kfree(lbt_kattrs);
 275
 276         pr_err("LBT(%s): failed to alloc sysfs attrs\n", __func__);
 277         return -ENOMEM;
 278 }
 279
 280 static int __init lbt_sysfs_init(void)
 281 {
 282         int depth = get_topology_depth();
 283         int i;
 284
 285         if (alloc_lbt_sysfs(depth + 1))
 286                 goto out;
 287
 288         for (i = 0; i <= depth; i++) {
 289                 char buf[25];
 290                 char *name;
 291
 292                 scnprintf(buf, sizeof(buf), "overutil_ratio_level%d", i);
 293                 name = kstrdup(buf, GFP_KERNEL);
 294                 if (!name)
 295                         goto out;
 296
 297                 lbt_attr_init(lbt_kattrs[i], name, 0644,
 298                                 show_overutil_ratio, store_overutil_ratio);
 299                 lbt_attrs[i] = &lbt_kattrs[i].attr;
 300         }
 301
 302         lbt_group.attrs = lbt_attrs;
 303
 304         lbt_kobj = kobject_create_and_add("lbt", ems_kobj);
 305         if (!lbt_kobj)
 306                 goto out;
 307
 308         if (sysfs_create_group(lbt_kobj, &lbt_group))
 309                 goto out;
 310
 311         return 0;
 312
 313 out:
 314         kfree(lbt_attrs);
 315         kfree(lbt_kattrs);
 316
 317         pr_err("LBT(%s): failed to create sysfs node\n", __func__);
 318         return -EINVAL;
 319 }
 320 late_initcall(lbt_sysfs_init);
 321
 322 /****************************************************************/
 323 /*                      Initialization                          */
 324 /****************************************************************/
 325 static void free_lbt_overutil(void)
 326 {
 327         int cpu;
 328
 329         for_each_possible_cpu(cpu) {
 330                 if (per_cpu(lbt_overutil, cpu))
 331                         kfree(per_cpu(lbt_overutil, cpu));
 332         }
 333 }
 334
 335 static int alloc_lbt_overutil(void)
 336 {
 337         int cpu, depth = get_topology_depth();
 338
 339         for_each_possible_cpu(cpu) {
 340                 struct lbt_overutil *ou = kzalloc(sizeof(struct lbt_overutil) *
 341                                 (depth + 1), GFP_KERNEL);
 342                 if (!ou)
 343                         goto fail_alloc;
 344
 345                 per_cpu(lbt_overutil, cpu) = ou;
 346         }
 347         return 0;
 348
 349 fail_alloc:
 350         free_lbt_overutil();
 351         return -ENOMEM;
 352 }
 353
 354 static void default_lbt_overutil(int level)
 355 {
 356         struct sched_domain *sd;
 357         struct lbt_overutil *ou;
 358         struct cpumask cpus;
 359         bool top;
 360         int cpu;
 361
 362         /* If current level is same with topology depth, it is top level */
 363         top = !(get_topology_depth() - level);
 364
 365         cpumask_clear(&cpus);
 366
 367         for_each_possible_cpu(cpu) {
 368                 int c;
 369
 370                 if (cpumask_test_cpu(cpu, &cpus))
 371                         continue;
 372
 373                 sd = find_sd_by_level(cpu, level);
 374                 if (!sd) {
 375                         ou = per_cpu(lbt_overutil, cpu);
 376                         ou[level].ratio = DISABLE_OU;
 377                         ou[level].top = top;
 378                         continue;
 379                 }
 380
 381                 cpumask_copy(&cpus, sched_domain_span(sd));
 382                 for_each_cpu(c, &cpus) {
 383                         ou = per_cpu(lbt_overutil, c);
 384                         cpumask_copy(&ou[level].cpus, &cpus);
 385                         ou[level].ratio = DEFAULT_OU_RATIO;
 386                         ou[level].top = top;
 387                 }
 388         }
 389 }
 390
 391 static void set_lbt_overutil(int level, const char *mask, int ratio)
 392 {
 393         struct lbt_overutil *ou;
 394         struct cpumask cpus;
 395         bool top, overlap = false;
 396         int cpu;
 397
 398         cpulist_parse(mask, &cpus);
 399         cpumask_and(&cpus, &cpus, cpu_possible_mask);
 400         if (!cpumask_weight(&cpus))
 401                 return;
 402
 403         /* If current level is same with topology depth, it is top level */
 404         top = !(get_topology_depth() - level);
 405
 406         /* If this level is overlapped with prev level, disable this level */
 407         if (level > 0) {
 408                 ou = per_cpu(lbt_overutil, cpumask_first(&cpus));
 409                 overlap = cpumask_equal(&cpus, &ou[level-1].cpus);
 410         }
 411
 412         for_each_cpu(cpu, &cpus) {
 413                 ou = per_cpu(lbt_overutil, cpu);
 414                 cpumask_copy(&ou[level].cpus, &cpus);
 415                 ou[level].ratio = overlap ? DISABLE_OU : ratio;
 416                 ou[level].top = top;
 417         }
 418 }
 419
 420 static void parse_lbt_overutil(struct device_node *dn)
 421 {
 422         struct device_node *lbt, *ou;
 423         int level, depth = get_topology_depth();
 424
 425         /* If lbt node isn't, set by default value (80%) */
 426         lbt = of_get_child_by_name(dn, "lbt");
 427         if (!lbt) {
 428                 for (level = 0; level <= depth; level++)
 429                         default_lbt_overutil(level);
 430                 return;
 431         }
 432
 433         if (!cpumask_equal(cpu_possible_mask, cpu_all_mask)) {
 434                 for (level = 0; level <= depth; level++)
 435                         default_lbt_overutil(level);
 436                 return;
 437         }
 438
 439         for (level = 0; level <= depth; level++) {
 440                 char name[20];
 441                 const char *mask[NR_CPUS];
 442                 struct cpumask combi, each;
 443                 int ratio[NR_CPUS];
 444                 int i, proplen;
 445
 446                 snprintf(name, sizeof(name), "overutil-level%d", level);
 447                 ou = of_get_child_by_name(lbt, name);
 448                 if (!ou)
 449                         goto default_setting;
 450
 451                 proplen = of_property_count_strings(ou, "cpus");
 452                 if ((proplen < 0) || (proplen != of_property_count_u32_elems(ou, "ratio"))) {
 453                         of_node_put(ou);
 454                         goto default_setting;
 455                 }
 456
 457                 of_property_read_string_array(ou, "cpus", mask, proplen);
 458                 of_property_read_u32_array(ou, "ratio", ratio, proplen);
 459                 of_node_put(ou);
 460
 461                 /*
 462                  * If combination of each cpus doesn't correspond with
 463                  * cpu_possible_mask, do not use this property
 464                  */
 465                 cpumask_clear(&combi);
 466                 for (i = 0; i < proplen; i++) {
 467                         cpulist_parse(mask[i], &each);
 468                         cpumask_or(&combi, &combi, &each);
 469                 }
 470                 if (!cpumask_equal(&combi, cpu_possible_mask))
 471                         goto default_setting;
 472
 473                 for (i = 0; i < proplen; i++)
 474                         set_lbt_overutil(level, mask[i], ratio[i]);
 475                 continue;
 476
 477 default_setting:
 478                 default_lbt_overutil(level);
 479         }
 480
 481         of_node_put(lbt);
 482 }
 483
 484 static int __init init_lbt(void)
 485 {
 486         struct device_node *dn = of_find_node_by_path("/cpus/ems");
 487
 488         if (alloc_lbt_overutil()) {
 489                 pr_err("LBT(%s): failed to allocate lbt_overutil\n", __func__);
 490                 of_node_put(dn);
 491                 return -ENOMEM;
 492         }
 493
 494         parse_lbt_overutil(dn);
 495         of_node_put(dn);
 496         return 0;
 497 }
 498 pure_initcall(init_lbt);