4 * Global CPU deadline management
6 * Author: Juri Lelli <j.lelli@sssup.it>
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; version 2
14 #include <linux/gfp.h>
15 #include <linux/kernel.h>
16 #include <linux/slab.h>
17 #include "cpudeadline.h"
19 static inline int parent(int i
)
24 static inline int left_child(int i
)
29 static inline int right_child(int i
)
34 static void cpudl_heapify_down(struct cpudl
*cp
, int idx
)
38 int orig_cpu
= cp
->elements
[idx
].cpu
;
39 u64 orig_dl
= cp
->elements
[idx
].dl
;
41 if (left_child(idx
) >= cp
->size
)
44 /* adapted from lib/prio_heap.c */
52 if ((l
< cp
->size
) && dl_time_before(orig_dl
,
53 cp
->elements
[l
].dl
)) {
55 largest_dl
= cp
->elements
[l
].dl
;
57 if ((r
< cp
->size
) && dl_time_before(largest_dl
,
64 /* pull largest child onto idx */
65 cp
->elements
[idx
].cpu
= cp
->elements
[largest
].cpu
;
66 cp
->elements
[idx
].dl
= cp
->elements
[largest
].dl
;
67 cp
->elements
[cp
->elements
[idx
].cpu
].idx
= idx
;
70 /* actual push down of saved original values orig_* */
71 cp
->elements
[idx
].cpu
= orig_cpu
;
72 cp
->elements
[idx
].dl
= orig_dl
;
73 cp
->elements
[cp
->elements
[idx
].cpu
].idx
= idx
;
76 static void cpudl_heapify_up(struct cpudl
*cp
, int idx
)
80 int orig_cpu
= cp
->elements
[idx
].cpu
;
81 u64 orig_dl
= cp
->elements
[idx
].dl
;
88 if (dl_time_before(orig_dl
, cp
->elements
[p
].dl
))
90 /* pull parent onto idx */
91 cp
->elements
[idx
].cpu
= cp
->elements
[p
].cpu
;
92 cp
->elements
[idx
].dl
= cp
->elements
[p
].dl
;
93 cp
->elements
[cp
->elements
[idx
].cpu
].idx
= idx
;
96 /* actual push up of saved original values orig_* */
97 cp
->elements
[idx
].cpu
= orig_cpu
;
98 cp
->elements
[idx
].dl
= orig_dl
;
99 cp
->elements
[cp
->elements
[idx
].cpu
].idx
= idx
;
102 static void cpudl_heapify(struct cpudl
*cp
, int idx
)
104 if (idx
> 0 && dl_time_before(cp
->elements
[parent(idx
)].dl
,
105 cp
->elements
[idx
].dl
))
106 cpudl_heapify_up(cp
, idx
);
108 cpudl_heapify_down(cp
, idx
);
111 static inline int cpudl_maximum(struct cpudl
*cp
)
113 return cp
->elements
[0].cpu
;
117 * cpudl_find - find the best (later-dl) CPU in the system
118 * @cp: the cpudl max-heap context
120 * @later_mask: a mask to fill in with the selected CPUs (or NULL)
122 * Returns: int - CPUs were found
124 int cpudl_find(struct cpudl
*cp
, struct task_struct
*p
,
125 struct cpumask
*later_mask
)
127 const struct sched_dl_entity
*dl_se
= &p
->dl
;
130 cpumask_and(later_mask
, cp
->free_cpus
, &p
->cpus_allowed
)) {
133 int best_cpu
= cpudl_maximum(cp
);
134 WARN_ON(best_cpu
!= -1 && !cpu_present(best_cpu
));
136 if (cpumask_test_cpu(best_cpu
, &p
->cpus_allowed
) &&
137 dl_time_before(dl_se
->deadline
, cp
->elements
[0].dl
)) {
139 cpumask_set_cpu(best_cpu
, later_mask
);
148 * cpudl_clear - remove a cpu from the cpudl max-heap
149 * @cp: the cpudl max-heap context
150 * @cpu: the target cpu
152 * Notes: assumes cpu_rq(cpu)->lock is locked
156 void cpudl_clear(struct cpudl
*cp
, int cpu
)
158 int old_idx
, new_cpu
;
161 WARN_ON(!cpu_present(cpu
));
163 raw_spin_lock_irqsave(&cp
->lock
, flags
);
165 old_idx
= cp
->elements
[cpu
].idx
;
166 if (old_idx
== IDX_INVALID
) {
168 * Nothing to remove if old_idx was invalid.
169 * This could happen if a rq_offline_dl is
170 * called for a CPU without -dl tasks running.
173 new_cpu
= cp
->elements
[cp
->size
- 1].cpu
;
174 cp
->elements
[old_idx
].dl
= cp
->elements
[cp
->size
- 1].dl
;
175 cp
->elements
[old_idx
].cpu
= new_cpu
;
177 cp
->elements
[new_cpu
].idx
= old_idx
;
178 cp
->elements
[cpu
].idx
= IDX_INVALID
;
179 cpudl_heapify(cp
, old_idx
);
181 cpumask_set_cpu(cpu
, cp
->free_cpus
);
183 raw_spin_unlock_irqrestore(&cp
->lock
, flags
);
187 * cpudl_set - update the cpudl max-heap
188 * @cp: the cpudl max-heap context
189 * @cpu: the target cpu
190 * @dl: the new earliest deadline for this cpu
192 * Notes: assumes cpu_rq(cpu)->lock is locked
196 void cpudl_set(struct cpudl
*cp
, int cpu
, u64 dl
)
201 WARN_ON(!cpu_present(cpu
));
203 raw_spin_lock_irqsave(&cp
->lock
, flags
);
205 old_idx
= cp
->elements
[cpu
].idx
;
206 if (old_idx
== IDX_INVALID
) {
207 int new_idx
= cp
->size
++;
208 cp
->elements
[new_idx
].dl
= dl
;
209 cp
->elements
[new_idx
].cpu
= cpu
;
210 cp
->elements
[cpu
].idx
= new_idx
;
211 cpudl_heapify_up(cp
, new_idx
);
212 cpumask_clear_cpu(cpu
, cp
->free_cpus
);
214 cp
->elements
[old_idx
].dl
= dl
;
215 cpudl_heapify(cp
, old_idx
);
218 raw_spin_unlock_irqrestore(&cp
->lock
, flags
);
222 * cpudl_set_freecpu - Set the cpudl.free_cpus
223 * @cp: the cpudl max-heap context
224 * @cpu: rd attached cpu
226 void cpudl_set_freecpu(struct cpudl
*cp
, int cpu
)
228 cpumask_set_cpu(cpu
, cp
->free_cpus
);
232 * cpudl_clear_freecpu - Clear the cpudl.free_cpus
233 * @cp: the cpudl max-heap context
234 * @cpu: rd attached cpu
236 void cpudl_clear_freecpu(struct cpudl
*cp
, int cpu
)
238 cpumask_clear_cpu(cpu
, cp
->free_cpus
);
242 * cpudl_init - initialize the cpudl structure
243 * @cp: the cpudl max-heap context
245 int cpudl_init(struct cpudl
*cp
)
249 raw_spin_lock_init(&cp
->lock
);
252 cp
->elements
= kcalloc(nr_cpu_ids
,
253 sizeof(struct cpudl_item
),
258 if (!zalloc_cpumask_var(&cp
->free_cpus
, GFP_KERNEL
)) {
263 for_each_possible_cpu(i
)
264 cp
->elements
[i
].idx
= IDX_INVALID
;
270 * cpudl_cleanup - clean up the cpudl structure
271 * @cp: the cpudl max-heap context
273 void cpudl_cleanup(struct cpudl
*cp
)
275 free_cpumask_var(cp
->free_cpus
);