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_clear - remove a cpu from the cpudl max-heap
 149  * @cp: the cpudl max-heap context
 150  * @cpu: the target cpu
 151  *
 152  * Notes: assumes cpu_rq(cpu)->lock is locked
 153  *
 154  * Returns: (void)
 155  */
 156 void cpudl_clear(struct cpudl *cp, int cpu)
 157 {
 158         int old_idx, new_cpu;
 159         unsigned long flags;
 160
 161         WARN_ON(!cpu_present(cpu));
 162
 163         raw_spin_lock_irqsave(&cp->lock, flags);
 164
 165         old_idx = cp->elements[cpu].idx;
 166         if (old_idx == IDX_INVALID) {
 167                 /*
 168                  * Nothing to remove if old_idx was invalid.
 169                  * This could happen if a rq_offline_dl is
 170                  * called for a CPU without -dl tasks running.
 171                  */
 172         } else {
 173                 new_cpu = cp->elements[cp->size - 1].cpu;
 174                 cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl;
 175                 cp->elements[old_idx].cpu = new_cpu;
 176                 cp->size--;
 177                 cp->elements[new_cpu].idx = old_idx;
 178                 cp->elements[cpu].idx = IDX_INVALID;
 179                 cpudl_heapify(cp, old_idx);
 180
 181                 cpumask_set_cpu(cpu, cp->free_cpus);
 182         }
 183         raw_spin_unlock_irqrestore(&cp->lock, flags);
 184 }
 185
 186 /*
 187  * cpudl_set - update the cpudl max-heap
 188  * @cp: the cpudl max-heap context
 189  * @cpu: the target cpu
 190  * @dl: the new earliest deadline for this cpu
 191  *
 192  * Notes: assumes cpu_rq(cpu)->lock is locked
 193  *
 194  * Returns: (void)
 195  */
 196 void cpudl_set(struct cpudl *cp, int cpu, u64 dl)
 197 {
 198         int old_idx;
 199         unsigned long flags;
 200
 201         WARN_ON(!cpu_present(cpu));
 202
 203         raw_spin_lock_irqsave(&cp->lock, flags);
 204
 205         old_idx = cp->elements[cpu].idx;
 206         if (old_idx == IDX_INVALID) {
 207                 int new_idx = cp->size++;
 208                 cp->elements[new_idx].dl = dl;
 209                 cp->elements[new_idx].cpu = cpu;
 210                 cp->elements[cpu].idx = new_idx;
 211                 cpudl_heapify_up(cp, new_idx);
 212                 cpumask_clear_cpu(cpu, cp->free_cpus);
 213         } else {
 214                 cp->elements[old_idx].dl = dl;
 215                 cpudl_heapify(cp, old_idx);
 216         }
 217
 218         raw_spin_unlock_irqrestore(&cp->lock, flags);
 219 }
 220
 221 /*
 222  * cpudl_set_freecpu - Set the cpudl.free_cpus
 223  * @cp: the cpudl max-heap context
 224  * @cpu: rd attached cpu
 225  */
 226 void cpudl_set_freecpu(struct cpudl *cp, int cpu)
 227 {
 228         cpumask_set_cpu(cpu, cp->free_cpus);
 229 }
 230
 231 /*
 232  * cpudl_clear_freecpu - Clear the cpudl.free_cpus
 233  * @cp: the cpudl max-heap context
 234  * @cpu: rd attached cpu
 235  */
 236 void cpudl_clear_freecpu(struct cpudl *cp, int cpu)
 237 {
 238         cpumask_clear_cpu(cpu, cp->free_cpus);
 239 }
 240
 241 /*
 242  * cpudl_init - initialize the cpudl structure
 243  * @cp: the cpudl max-heap context
 244  */
 245 int cpudl_init(struct cpudl *cp)
 246 {
 247         int i;
 248
 249         memset(cp, 0, sizeof(*cp));
 250         raw_spin_lock_init(&cp->lock);
 251         cp->size = 0;
 252
 253         cp->elements = kcalloc(nr_cpu_ids,
 254                                sizeof(struct cpudl_item),
 255                                GFP_KERNEL);
 256         if (!cp->elements)
 257                 return -ENOMEM;
 258
 259         if (!zalloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) {
 260                 kfree(cp->elements);
 261                 return -ENOMEM;
 262         }
 263
 264         for_each_possible_cpu(i)
 265                 cp->elements[i].idx = IDX_INVALID;
 266
 267         return 0;
 268 }
 269
 270 /*
 271  * cpudl_cleanup - clean up the cpudl structure
 272  * @cp: the cpudl max-heap context
 273  */
 274 void cpudl_cleanup(struct cpudl *cp)
 275 {
 276         free_cpumask_var(cp->free_cpus);
 277         kfree(cp->elements);
 278 }