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 inline int dl_time_before(u64 a
, u64 b
)
36 return (s64
)(a
- b
) < 0;
39 static void cpudl_exchange(struct cpudl
*cp
, int a
, int b
)
41 int cpu_a
= cp
->elements
[a
].cpu
, cpu_b
= cp
->elements
[b
].cpu
;
43 swap(cp
->elements
[a
].cpu
, cp
->elements
[b
].cpu
);
44 swap(cp
->elements
[a
].dl
, cp
->elements
[b
].dl
);
46 swap(cp
->elements
[cpu_a
].idx
, cp
->elements
[cpu_b
].idx
);
49 static void cpudl_heapify(struct cpudl
*cp
, int idx
)
53 /* adapted from lib/prio_heap.c */
59 if ((l
< cp
->size
) && dl_time_before(cp
->elements
[idx
].dl
,
62 if ((r
< cp
->size
) && dl_time_before(cp
->elements
[largest
].dl
,
68 /* Push idx down the heap one level and bump one up */
69 cpudl_exchange(cp
, largest
, idx
);
74 static void cpudl_change_key(struct cpudl
*cp
, int idx
, u64 new_dl
)
76 WARN_ON(idx
== IDX_INVALID
|| !cpu_present(idx
));
78 if (dl_time_before(new_dl
, cp
->elements
[idx
].dl
)) {
79 cp
->elements
[idx
].dl
= new_dl
;
80 cpudl_heapify(cp
, idx
);
82 cp
->elements
[idx
].dl
= new_dl
;
83 while (idx
> 0 && dl_time_before(cp
->elements
[parent(idx
)].dl
,
84 cp
->elements
[idx
].dl
)) {
85 cpudl_exchange(cp
, idx
, parent(idx
));
91 static inline int cpudl_maximum(struct cpudl
*cp
)
93 return cp
->elements
[0].cpu
;
97 * cpudl_find - find the best (later-dl) CPU in the system
98 * @cp: the cpudl max-heap context
100 * @later_mask: a mask to fill in with the selected CPUs (or NULL)
102 * Returns: int - best CPU (heap maximum if suitable)
104 int cpudl_find(struct cpudl
*cp
, struct task_struct
*p
,
105 struct cpumask
*later_mask
)
108 const struct sched_dl_entity
*dl_se
= &p
->dl
;
110 if (later_mask
&& cpumask_and(later_mask
, later_mask
, cp
->free_cpus
)) {
111 best_cpu
= cpumask_any(later_mask
);
113 } else if (cpumask_test_cpu(cpudl_maximum(cp
), &p
->cpus_allowed
) &&
114 dl_time_before(dl_se
->deadline
, cp
->elements
[0].dl
)) {
115 best_cpu
= cpudl_maximum(cp
);
117 cpumask_set_cpu(best_cpu
, later_mask
);
121 WARN_ON(best_cpu
!= -1 && !cpu_present(best_cpu
));
127 * cpudl_set - update the cpudl max-heap
128 * @cp: the cpudl max-heap context
129 * @cpu: the target cpu
130 * @dl: the new earliest deadline for this cpu
132 * Notes: assumes cpu_rq(cpu)->lock is locked
136 void cpudl_set(struct cpudl
*cp
, int cpu
, u64 dl
, int is_valid
)
138 int old_idx
, new_cpu
;
141 WARN_ON(!cpu_present(cpu
));
143 raw_spin_lock_irqsave(&cp
->lock
, flags
);
144 old_idx
= cp
->elements
[cpu
].idx
;
147 if (old_idx
== IDX_INVALID
) {
149 * Nothing to remove if old_idx was invalid.
150 * This could happen if a rq_offline_dl is
151 * called for a CPU without -dl tasks running.
155 new_cpu
= cp
->elements
[cp
->size
- 1].cpu
;
156 cp
->elements
[old_idx
].dl
= cp
->elements
[cp
->size
- 1].dl
;
157 cp
->elements
[old_idx
].cpu
= new_cpu
;
159 cp
->elements
[new_cpu
].idx
= old_idx
;
160 cp
->elements
[cpu
].idx
= IDX_INVALID
;
161 while (old_idx
> 0 && dl_time_before(
162 cp
->elements
[parent(old_idx
)].dl
,
163 cp
->elements
[old_idx
].dl
)) {
164 cpudl_exchange(cp
, old_idx
, parent(old_idx
));
165 old_idx
= parent(old_idx
);
167 cpumask_set_cpu(cpu
, cp
->free_cpus
);
168 cpudl_heapify(cp
, old_idx
);
173 if (old_idx
== IDX_INVALID
) {
175 cp
->elements
[cp
->size
- 1].dl
= 0;
176 cp
->elements
[cp
->size
- 1].cpu
= cpu
;
177 cp
->elements
[cpu
].idx
= cp
->size
- 1;
178 cpudl_change_key(cp
, cp
->size
- 1, dl
);
179 cpumask_clear_cpu(cpu
, cp
->free_cpus
);
181 cpudl_change_key(cp
, old_idx
, dl
);
185 raw_spin_unlock_irqrestore(&cp
->lock
, flags
);
189 * cpudl_init - initialize the cpudl structure
190 * @cp: the cpudl max-heap context
192 int cpudl_init(struct cpudl
*cp
)
196 memset(cp
, 0, sizeof(*cp
));
197 raw_spin_lock_init(&cp
->lock
);
200 cp
->elements
= kcalloc(nr_cpu_ids
,
201 sizeof(struct cpudl_item
),
206 if (!alloc_cpumask_var(&cp
->free_cpus
, GFP_KERNEL
)) {
211 for_each_possible_cpu(i
)
212 cp
->elements
[i
].idx
= IDX_INVALID
;
214 cpumask_setall(cp
->free_cpus
);
220 * cpudl_cleanup - clean up the cpudl structure
221 * @cp: the cpudl max-heap context
223 void cpudl_cleanup(struct cpudl
*cp
)
225 free_cpumask_var(cp
->free_cpus
);