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