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