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_exchange(struct cpudl *cp, int a, int b)
  35 {
  36         int cpu_a = cp->elements[a].cpu, cpu_b = cp->elements[b].cpu;
  37
  38         swap(cp->elements[a].cpu, cp->elements[b].cpu);
  39         swap(cp->elements[a].dl , cp->elements[b].dl );
  40
  41         swap(cp->elements[cpu_a].idx, cp->elements[cpu_b].idx);
  42 }
  43
  44 static void cpudl_heapify_down(struct cpudl *cp, int idx)
  45 {
  46         int l, r, largest;
  47
  48         /* adapted from lib/prio_heap.c */
  49         while(1) {
  50                 l = left_child(idx);
  51                 r = right_child(idx);
  52                 largest = idx;
  53
  54                 if ((l < cp->size) && dl_time_before(cp->elements[idx].dl,
  55                                                         cp->elements[l].dl))
  56                         largest = l;
  57                 if ((r < cp->size) && dl_time_before(cp->elements[largest].dl,
  58                                                         cp->elements[r].dl))
  59                         largest = r;
  60                 if (largest == idx)
  61                         break;
  62
  63                 /* Push idx down the heap one level and bump one up */
  64                 cpudl_exchange(cp, largest, idx);
  65                 idx = largest;
  66         }
  67 }
  68
  69 static void cpudl_heapify_up(struct cpudl *cp, int idx)
  70 {
  71         while (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl,
  72                         cp->elements[idx].dl)) {
  73                 cpudl_exchange(cp, idx, parent(idx));
  74                 idx = parent(idx);
  75         }
  76 }
  77
  78 static void cpudl_heapify(struct cpudl *cp, int idx)
  79 {
  80         if (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl,
  81                                 cp->elements[idx].dl))
  82                 cpudl_heapify_up(cp, idx);
  83         else
  84                 cpudl_heapify_down(cp, idx);
  85 }
  86
  87 static inline int cpudl_maximum(struct cpudl *cp)
  88 {
  89         return cp->elements[0].cpu;
  90 }
  91
  92 /*
  93  * cpudl_find - find the best (later-dl) CPU in the system
  94  * @cp: the cpudl max-heap context
  95  * @p: the task
  96  * @later_mask: a mask to fill in with the selected CPUs (or NULL)
  97  *
  98  * Returns: int - best CPU (heap maximum if suitable)
  99  */
 100 int cpudl_find(struct cpudl *cp, struct task_struct *p,
 101                struct cpumask *later_mask)
 102 {
 103         int best_cpu = -1;
 104         const struct sched_dl_entity *dl_se = &p->dl;
 105
 106         if (later_mask &&
 107             cpumask_and(later_mask, cp->free_cpus, tsk_cpus_allowed(p))) {
 108                 best_cpu = cpumask_any(later_mask);
 109                 goto out;
 110         } else if (cpumask_test_cpu(cpudl_maximum(cp), tsk_cpus_allowed(p)) &&
 111                         dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
 112                 best_cpu = cpudl_maximum(cp);
 113                 if (later_mask)
 114                         cpumask_set_cpu(best_cpu, later_mask);
 115         }
 116
 117 out:
 118         WARN_ON(best_cpu != -1 && !cpu_present(best_cpu));
 119
 120         return best_cpu;
 121 }
 122
 123 /*
 124  * cpudl_set - update the cpudl max-heap
 125  * @cp: the cpudl max-heap context
 126  * @cpu: the target cpu
 127  * @dl: the new earliest deadline for this cpu
 128  *
 129  * Notes: assumes cpu_rq(cpu)->lock is locked
 130  *
 131  * Returns: (void)
 132  */
 133 void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)
 134 {
 135         int old_idx, new_cpu;
 136         unsigned long flags;
 137
 138         WARN_ON(!cpu_present(cpu));
 139
 140         raw_spin_lock_irqsave(&cp->lock, flags);
 141         old_idx = cp->elements[cpu].idx;
 142         if (!is_valid) {
 143                 /* remove item */
 144                 if (old_idx == IDX_INVALID) {
 145                         /*
 146                          * Nothing to remove if old_idx was invalid.
 147                          * This could happen if a rq_offline_dl is
 148                          * called for a CPU without -dl tasks running.
 149                          */
 150                         goto out;
 151                 }
 152                 new_cpu = cp->elements[cp->size - 1].cpu;
 153                 cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl;
 154                 cp->elements[old_idx].cpu = new_cpu;
 155                 cp->size--;
 156                 cp->elements[new_cpu].idx = old_idx;
 157                 cp->elements[cpu].idx = IDX_INVALID;
 158                 cpudl_heapify(cp, old_idx);
 159                 cpumask_set_cpu(cpu, cp->free_cpus);
 160
 161                 goto out;
 162         }
 163
 164         if (old_idx == IDX_INVALID) {
 165                 int new_idx = cp->size++;
 166                 cp->elements[new_idx].dl = dl;
 167                 cp->elements[new_idx].cpu = cpu;
 168                 cp->elements[cpu].idx = new_idx;
 169                 cpudl_heapify_up(cp, new_idx);
 170                 cpumask_clear_cpu(cpu, cp->free_cpus);
 171         } else {
 172                 cp->elements[old_idx].dl = dl;
 173                 cpudl_heapify(cp, old_idx);
 174         }
 175
 176 out:
 177         raw_spin_unlock_irqrestore(&cp->lock, flags);
 178 }
 179
 180 /*
 181  * cpudl_set_freecpu - Set the cpudl.free_cpus
 182  * @cp: the cpudl max-heap context
 183  * @cpu: rd attached cpu
 184  */
 185 void cpudl_set_freecpu(struct cpudl *cp, int cpu)
 186 {
 187         cpumask_set_cpu(cpu, cp->free_cpus);
 188 }
 189
 190 /*
 191  * cpudl_clear_freecpu - Clear the cpudl.free_cpus
 192  * @cp: the cpudl max-heap context
 193  * @cpu: rd attached cpu
 194  */
 195 void cpudl_clear_freecpu(struct cpudl *cp, int cpu)
 196 {
 197         cpumask_clear_cpu(cpu, cp->free_cpus);
 198 }
 199
 200 /*
 201  * cpudl_init - initialize the cpudl structure
 202  * @cp: the cpudl max-heap context
 203  */
 204 int cpudl_init(struct cpudl *cp)
 205 {
 206         int i;
 207
 208         memset(cp, 0, sizeof(*cp));
 209         raw_spin_lock_init(&cp->lock);
 210         cp->size = 0;
 211
 212         cp->elements = kcalloc(nr_cpu_ids,
 213                                sizeof(struct cpudl_item),
 214                                GFP_KERNEL);
 215         if (!cp->elements)
 216                 return -ENOMEM;
 217
 218         if (!zalloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) {
 219                 kfree(cp->elements);
 220                 return -ENOMEM;
 221         }
 222
 223         for_each_possible_cpu(i)
 224                 cp->elements[i].idx = IDX_INVALID;
 225
 226         return 0;
 227 }
 228
 229 /*
 230  * cpudl_cleanup - clean up the cpudl structure
 231  * @cp: the cpudl max-heap context
 232  */
 233 void cpudl_cleanup(struct cpudl *cp)
 234 {
 235         free_cpumask_var(cp->free_cpus);
 236         kfree(cp->elements);
 237 }