kernel/sched/cpudeadline.c

   1 /*
   2  *  kernel/sched/cpudl.c
   3  *
   4  *  Global CPU deadline management
   5  *
   6  *  Author: Juri Lelli <j.lelli@sssup.it>
   7  *
   8  *  This program is free software; you can redistribute it and/or
   9  *  modify it under the terms of the GNU General Public License
  10  *  as published by the Free Software Foundation; version 2
  11  *  of the License.
  12  */
  13
  14 #include <linux/gfp.h>
  15 #include <linux/kernel.h>
  16 #include <linux/slab.h>
  17 #include "cpudeadline.h"
  18
  19 static inline int parent(int i)
  20 {
  21         return (i - 1) >> 1;
  22 }
  23
  24 static inline int left_child(int i)
  25 {
  26         return (i << 1) + 1;
  27 }
  28
  29 static inline int right_child(int i)
  30 {
  31         return (i << 1) + 2;
  32 }
  33
  34 static void cpudl_heapify_down(struct cpudl *cp, int idx)
  35 {
  36         int l, r, largest;
  37
  38         int orig_cpu = cp->elements[idx].cpu;
  39         u64 orig_dl = cp->elements[idx].dl;
  40
  41         if (left_child(idx) >= cp->size)
  42                 return;
  43
  44         /* adapted from lib/prio_heap.c */
  45         while(1) {
  46                 u64 largest_dl;
  47                 l = left_child(idx);
  48                 r = right_child(idx);
  49                 largest = idx;
  50                 largest_dl = orig_dl;
  51
  52                 if ((l < cp->size) && dl_time_before(orig_dl,
  53                                                 cp->elements[l].dl)) {
  54                         largest = l;
  55                         largest_dl = cp->elements[l].dl;
  56                 }
  57                 if ((r < cp->size) && dl_time_before(largest_dl,
  58                                                 cp->elements[r].dl))
  59                         largest = r;
  60
  61                 if (largest == idx)
  62                         break;
  63
  64                 /* pull largest child onto idx */
  65                 cp->elements[idx].cpu = cp->elements[largest].cpu;
  66                 cp->elements[idx].dl = cp->elements[largest].dl;
  67                 cp->elements[cp->elements[idx].cpu].idx = idx;
  68                 idx = largest;
  69         }
  70         /* actual push down of saved original values orig_* */
  71         cp->elements[idx].cpu = orig_cpu;
  72         cp->elements[idx].dl = orig_dl;
  73         cp->elements[cp->elements[idx].cpu].idx = idx;
  74 }
  75
  76 static void cpudl_heapify_up(struct cpudl *cp, int idx)
  77 {
  78         int p;
  79
  80         int orig_cpu = cp->elements[idx].cpu;
  81         u64 orig_dl = cp->elements[idx].dl;
  82
  83         if (idx == 0)
  84                 return;
  85
  86         do {
  87                 p = parent(idx);
  88                 if (dl_time_before(orig_dl, cp->elements[p].dl))
  89                         break;
  90                 /* pull parent onto idx */
  91                 cp->elements[idx].cpu = cp->elements[p].cpu;
  92                 cp->elements[idx].dl = cp->elements[p].dl;
  93                 cp->elements[cp->elements[idx].cpu].idx = idx;
  94                 idx = p;
  95         } while (idx != 0);
  96         /* actual push up of saved original values orig_* */
  97         cp->elements[idx].cpu = orig_cpu;
  98         cp->elements[idx].dl = orig_dl;
  99         cp->elements[cp->elements[idx].cpu].idx = idx;
 100 }
 101
 102 static void cpudl_heapify(struct cpudl *cp, int idx)
 103 {
 104         if (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl,
 105                                 cp->elements[idx].dl))
 106                 cpudl_heapify_up(cp, idx);
 107         else
 108                 cpudl_heapify_down(cp, idx);
 109 }
 110
 111 static inline int cpudl_maximum(struct cpudl *cp)
 112 {
 113         return cp->elements[0].cpu;
 114 }
 115
 116 /*
 117  * cpudl_find - find the best (later-dl) CPU in the system
 118  * @cp: the cpudl max-heap context
 119  * @p: the task
 120  * @later_mask: a mask to fill in with the selected CPUs (or NULL)
 121  *
 122  * Returns: int - best CPU (heap maximum if suitable)
 123  */
 124 int cpudl_find(struct cpudl *cp, struct task_struct *p,
 125                struct cpumask *later_mask)
 126 {
 127         int best_cpu = -1;
 128         const struct sched_dl_entity *dl_se = &p->dl;
 129
 130         if (later_mask &&
 131             cpumask_and(later_mask, cp->free_cpus, tsk_cpus_allowed(p))) {
 132                 best_cpu = cpumask_any(later_mask);
 133                 goto out;
 134         } else if (cpumask_test_cpu(cpudl_maximum(cp), tsk_cpus_allowed(p)) &&
 135                         dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
 136                 best_cpu = cpudl_maximum(cp);
 137                 if (later_mask)
 138                         cpumask_set_cpu(best_cpu, later_mask);
 139         }
 140
 141 out:
 142         WARN_ON(best_cpu != -1 && !cpu_present(best_cpu));
 143
 144         return best_cpu;
 145 }
 146
 147 /*
 148  * cpudl_set - update the cpudl max-heap
 149  * @cp: the cpudl max-heap context
 150  * @cpu: the target cpu
 151  * @dl: the new earliest deadline for this cpu
 152  *
 153  * Notes: assumes cpu_rq(cpu)->lock is locked
 154  *
 155  * Returns: (void)
 156  */
 157 void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)
 158 {
 159         int old_idx, new_cpu;
 160         unsigned long flags;
 161
 162         WARN_ON(!cpu_present(cpu));
 163
 164         raw_spin_lock_irqsave(&cp->lock, flags);
 165         old_idx = cp->elements[cpu].idx;
 166         if (!is_valid) {
 167                 /* remove item */
 168                 if (old_idx == IDX_INVALID) {
 169                         /*
 170                          * Nothing to remove if old_idx was invalid.
 171                          * This could happen if a rq_offline_dl is
 172                          * called for a CPU without -dl tasks running.
 173                          */
 174                         goto out;
 175                 }
 176                 new_cpu = cp->elements[cp->size - 1].cpu;
 177                 cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl;
 178                 cp->elements[old_idx].cpu = new_cpu;
 179                 cp->size--;
 180                 cp->elements[new_cpu].idx = old_idx;
 181                 cp->elements[cpu].idx = IDX_INVALID;
 182                 cpudl_heapify(cp, old_idx);
 183                 cpumask_set_cpu(cpu, cp->free_cpus);
 184
 185                 goto out;
 186         }
 187
 188         if (old_idx == IDX_INVALID) {
 189                 int new_idx = cp->size++;
 190                 cp->elements[new_idx].dl = dl;
 191                 cp->elements[new_idx].cpu = cpu;
 192                 cp->elements[cpu].idx = new_idx;
 193                 cpudl_heapify_up(cp, new_idx);
 194                 cpumask_clear_cpu(cpu, cp->free_cpus);
 195         } else {
 196                 cp->elements[old_idx].dl = dl;
 197                 cpudl_heapify(cp, old_idx);
 198         }
 199
 200 out:
 201         raw_spin_unlock_irqrestore(&cp->lock, flags);
 202 }
 203
 204 /*
 205  * cpudl_set_freecpu - Set the cpudl.free_cpus
 206  * @cp: the cpudl max-heap context
 207  * @cpu: rd attached cpu
 208  */
 209 void cpudl_set_freecpu(struct cpudl *cp, int cpu)
 210 {
 211         cpumask_set_cpu(cpu, cp->free_cpus);
 212 }
 213
 214 /*
 215  * cpudl_clear_freecpu - Clear the cpudl.free_cpus
 216  * @cp: the cpudl max-heap context
 217  * @cpu: rd attached cpu
 218  */
 219 void cpudl_clear_freecpu(struct cpudl *cp, int cpu)
 220 {
 221         cpumask_clear_cpu(cpu, cp->free_cpus);
 222 }
 223
 224 /*
 225  * cpudl_init - initialize the cpudl structure
 226  * @cp: the cpudl max-heap context
 227  */
 228 int cpudl_init(struct cpudl *cp)
 229 {
 230         int i;
 231
 232         memset(cp, 0, sizeof(*cp));
 233         raw_spin_lock_init(&cp->lock);
 234         cp->size = 0;
 235
 236         cp->elements = kcalloc(nr_cpu_ids,
 237                                sizeof(struct cpudl_item),
 238                                GFP_KERNEL);
 239         if (!cp->elements)
 240                 return -ENOMEM;
 241
 242         if (!zalloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) {
 243                 kfree(cp->elements);
 244                 return -ENOMEM;
 245         }
 246
 247         for_each_possible_cpu(i)
 248                 cp->elements[i].idx = IDX_INVALID;
 249
 250         return 0;
 251 }
 252
 253 /*
 254  * cpudl_cleanup - clean up the cpudl structure
 255  * @cp: the cpudl max-heap context
 256  */
 257 void cpudl_cleanup(struct cpudl *cp)
 258 {
 259         free_cpumask_var(cp->free_cpus);
 260         kfree(cp->elements);
 261 }