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