Branch data 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 : : static inline int parent(int i)
12 : : {
13 : 0 : return (i - 1) >> 1;
14 : : }
15 : :
16 : : static inline int left_child(int i)
17 : : {
18 : 0 : return (i << 1) + 1;
19 : : }
20 : :
21 : : 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 : : 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 : 0 : 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 [ # # # # ]: 0 : if ((l < cp->size) && dl_time_before(orig_dl,
46 : 0 : cp->elements[l].dl)) {
47 : : largest = l;
48 : : 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 : : 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 : : idx = largest;
62 : 0 : }
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 : : 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 : 0 : return;
78 : :
79 : : do {
80 : : 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 : : 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 : : 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 : : 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_ptr)) {
124 : : return 1;
125 : : } else {
126 : : int best_cpu = cpudl_maximum(cp);
127 : :
128 [ # # # # : 0 : WARN_ON(best_cpu != -1 && !cpu_present(best_cpu));
# # ]
129 : :
130 [ # # # # ]: 0 : if (cpumask_test_cpu(best_cpu, p->cpus_ptr) &&
131 : 0 : dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
132 [ # # ]: 0 : 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 : 828 : void cpudl_clear(struct cpudl *cp, int cpu)
151 : : {
152 : : int old_idx, new_cpu;
153 : : unsigned long flags;
154 : :
155 [ - + ]: 828 : WARN_ON(!cpu_present(cpu));
156 : :
157 : 828 : raw_spin_lock_irqsave(&cp->lock, flags);
158 : :
159 : 828 : old_idx = cp->elements[cpu].idx;
160 [ - + ]: 828 : 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 : 0 : new_cpu = cp->elements[cp->size - 1].cpu;
168 : 0 : cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl;
169 : 0 : cp->elements[old_idx].cpu = new_cpu;
170 : 0 : cp->size--;
171 : 0 : cp->elements[new_cpu].idx = old_idx;
172 : 0 : cp->elements[cpu].idx = IDX_INVALID;
173 : 0 : cpudl_heapify(cp, old_idx);
174 : :
175 : : cpumask_set_cpu(cpu, cp->free_cpus);
176 : : }
177 : 828 : raw_spin_unlock_irqrestore(&cp->lock, flags);
178 : 828 : }
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 : 0 : void cpudl_set(struct cpudl *cp, int cpu, u64 dl)
191 : : {
192 : : int old_idx;
193 : : unsigned long flags;
194 : :
195 [ # # ]: 0 : WARN_ON(!cpu_present(cpu));
196 : :
197 : 0 : raw_spin_lock_irqsave(&cp->lock, flags);
198 : :
199 : 0 : old_idx = cp->elements[cpu].idx;
200 [ # # ]: 0 : if (old_idx == IDX_INVALID) {
201 : 0 : int new_idx = cp->size++;
202 : :
203 : 0 : cp->elements[new_idx].dl = dl;
204 : 0 : cp->elements[new_idx].cpu = cpu;
205 : 0 : cp->elements[cpu].idx = new_idx;
206 : 0 : cpudl_heapify_up(cp, new_idx);
207 : : cpumask_clear_cpu(cpu, cp->free_cpus);
208 : : } else {
209 : 0 : cp->elements[old_idx].dl = dl;
210 : 0 : cpudl_heapify(cp, old_idx);
211 : : }
212 : :
213 : 0 : raw_spin_unlock_irqrestore(&cp->lock, flags);
214 : 0 : }
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 : 1656 : void cpudl_set_freecpu(struct cpudl *cp, int cpu)
222 : : {
223 : : cpumask_set_cpu(cpu, cp->free_cpus);
224 : 1656 : }
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 : 828 : void cpudl_clear_freecpu(struct cpudl *cp, int cpu)
232 : : {
233 : : cpumask_clear_cpu(cpu, cp->free_cpus);
234 : 828 : }
235 : :
236 : : /*
237 : : * cpudl_init - initialize the cpudl structure
238 : : * @cp: the cpudl max-heap context
239 : : */
240 : 414 : int cpudl_init(struct cpudl *cp)
241 : : {
242 : : int i;
243 : :
244 : 414 : raw_spin_lock_init(&cp->lock);
245 : 414 : cp->size = 0;
246 : :
247 : 828 : cp->elements = kcalloc(nr_cpu_ids,
248 : : sizeof(struct cpudl_item),
249 : : GFP_KERNEL);
250 [ + - ]: 414 : 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 [ + + ]: 2484 : for_each_possible_cpu(i)
259 : 1656 : 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 : 0 : void cpudl_cleanup(struct cpudl *cp)
269 : : {
270 : : free_cpumask_var(cp->free_cpus);
271 : 0 : kfree(cp->elements);
272 : 0 : }
|
