0ace75a7a87b5428bd8a1b972e8acf729f2fc9d9
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 - best CPU (heap maximum if suitable)
124 int cpudl_find(struct cpudl
*cp
, struct task_struct
*p
,
125 struct cpumask
*later_mask
)
128 const struct sched_dl_entity
*dl_se
= &p
->dl
;
131 cpumask_and(later_mask
, cp
->free_cpus
, tsk_cpus_allowed(p
))) {
132 best_cpu
= cpumask_any(later_mask
);
134 } else if (cpumask_test_cpu(cpudl_maximum(cp
), tsk_cpus_allowed(p
)) &&
135 dl_time_before(dl_se
->deadline
, cp
->elements
[0].dl
)) {
136 best_cpu
= cpudl_maximum(cp
);
138 cpumask_set_cpu(best_cpu
, later_mask
);
142 WARN_ON(best_cpu
!= -1 && !cpu_present(best_cpu
));
148 * cpudl_set - update the cpudl max-heap
149 * @cp: the cpudl max-heap context
150 * @cpu: the target cpu
151 * @dl: the new earliest deadline for this cpu
153 * Notes: assumes cpu_rq(cpu)->lock is locked
157 void cpudl_set(struct cpudl
*cp
, int cpu
, u64 dl
, int is_valid
)
159 int old_idx
, new_cpu
;
162 WARN_ON(!cpu_present(cpu
));
164 raw_spin_lock_irqsave(&cp
->lock
, flags
);
165 old_idx
= cp
->elements
[cpu
].idx
;
168 if (old_idx
== IDX_INVALID
) {
170 * Nothing to remove if old_idx was invalid.
171 * This could happen if a rq_offline_dl is
172 * called for a CPU without -dl tasks running.
176 new_cpu
= cp
->elements
[cp
->size
- 1].cpu
;
177 cp
->elements
[old_idx
].dl
= cp
->elements
[cp
->size
- 1].dl
;
178 cp
->elements
[old_idx
].cpu
= new_cpu
;
180 cp
->elements
[new_cpu
].idx
= old_idx
;
181 cp
->elements
[cpu
].idx
= IDX_INVALID
;
182 cpudl_heapify(cp
, old_idx
);
183 cpumask_set_cpu(cpu
, cp
->free_cpus
);
188 if (old_idx
== IDX_INVALID
) {
189 int new_idx
= cp
->size
++;
190 cp
->elements
[new_idx
].dl
= dl
;
191 cp
->elements
[new_idx
].cpu
= cpu
;
192 cp
->elements
[cpu
].idx
= new_idx
;
193 cpudl_heapify_up(cp
, new_idx
);
194 cpumask_clear_cpu(cpu
, cp
->free_cpus
);
196 cp
->elements
[old_idx
].dl
= dl
;
197 cpudl_heapify(cp
, old_idx
);
201 raw_spin_unlock_irqrestore(&cp
->lock
, flags
);
205 * cpudl_set_freecpu - Set the cpudl.free_cpus
206 * @cp: the cpudl max-heap context
207 * @cpu: rd attached cpu
209 void cpudl_set_freecpu(struct cpudl
*cp
, int cpu
)
211 cpumask_set_cpu(cpu
, cp
->free_cpus
);
215 * cpudl_clear_freecpu - Clear the cpudl.free_cpus
216 * @cp: the cpudl max-heap context
217 * @cpu: rd attached cpu
219 void cpudl_clear_freecpu(struct cpudl
*cp
, int cpu
)
221 cpumask_clear_cpu(cpu
, cp
->free_cpus
);
225 * cpudl_init - initialize the cpudl structure
226 * @cp: the cpudl max-heap context
228 int cpudl_init(struct cpudl
*cp
)
232 memset(cp
, 0, sizeof(*cp
));
233 raw_spin_lock_init(&cp
->lock
);
236 cp
->elements
= kcalloc(nr_cpu_ids
,
237 sizeof(struct cpudl_item
),
242 if (!zalloc_cpumask_var(&cp
->free_cpus
, GFP_KERNEL
)) {
247 for_each_possible_cpu(i
)
248 cp
->elements
[i
].idx
= IDX_INVALID
;
254 * cpudl_cleanup - clean up the cpudl structure
255 * @cp: the cpudl max-heap context
257 void cpudl_cleanup(struct cpudl
*cp
)
259 free_cpumask_var(cp
->free_cpus
);
This page took 0.049079 seconds and 4 git commands to generate.