root/kernel/sched/cpudeadline.c

DEFINITIONS

1. parent
2. left_child
3. right_child
4. cpudl_heapify_down
5. cpudl_heapify_up
6. cpudl_heapify
7. cpudl_maximum
8. cpudl_find
9. cpudl_clear
10. cpudl_set
11. cpudl_set_freecpu
12. cpudl_clear_freecpu
13. cpudl_init
14. cpudl_cleanup

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