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