Commit | Line | Data |
---|---|---|
6bfd6d72 JL |
1 | /* |
2 | * kernel/sched/cpudl.c | |
3 | * | |
4 | * Global CPU deadline management | |
5 | * | |
6 | * Author: Juri Lelli <j.lelli@sssup.it> | |
7 | * | |
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 | |
11 | * of the License. | |
12 | */ | |
13 | ||
14 | #include <linux/gfp.h> | |
15 | #include <linux/kernel.h> | |
944770ab | 16 | #include <linux/slab.h> |
6bfd6d72 JL |
17 | #include "cpudeadline.h" |
18 | ||
19 | static inline int parent(int i) | |
20 | { | |
21 | return (i - 1) >> 1; | |
22 | } | |
23 | ||
24 | static inline int left_child(int i) | |
25 | { | |
26 | return (i << 1) + 1; | |
27 | } | |
28 | ||
29 | static inline int right_child(int i) | |
30 | { | |
31 | return (i << 1) + 2; | |
32 | } | |
33 | ||
34 | static inline int dl_time_before(u64 a, u64 b) | |
35 | { | |
36 | return (s64)(a - b) < 0; | |
37 | } | |
38 | ||
88f1ebbc | 39 | static void cpudl_exchange(struct cpudl *cp, int a, int b) |
6bfd6d72 JL |
40 | { |
41 | int cpu_a = cp->elements[a].cpu, cpu_b = cp->elements[b].cpu; | |
42 | ||
944770ab PZ |
43 | swap(cp->elements[a].cpu, cp->elements[b].cpu); |
44 | swap(cp->elements[a].dl , cp->elements[b].dl ); | |
45 | ||
46 | swap(cp->elements[cpu_a].idx, cp->elements[cpu_b].idx); | |
6bfd6d72 JL |
47 | } |
48 | ||
88f1ebbc | 49 | static void cpudl_heapify(struct cpudl *cp, int idx) |
6bfd6d72 JL |
50 | { |
51 | int l, r, largest; | |
52 | ||
53 | /* adapted from lib/prio_heap.c */ | |
54 | while(1) { | |
55 | l = left_child(idx); | |
56 | r = right_child(idx); | |
57 | largest = idx; | |
58 | ||
59 | if ((l < cp->size) && dl_time_before(cp->elements[idx].dl, | |
60 | cp->elements[l].dl)) | |
61 | largest = l; | |
62 | if ((r < cp->size) && dl_time_before(cp->elements[largest].dl, | |
63 | cp->elements[r].dl)) | |
64 | largest = r; | |
65 | if (largest == idx) | |
66 | break; | |
67 | ||
68 | /* Push idx down the heap one level and bump one up */ | |
69 | cpudl_exchange(cp, largest, idx); | |
70 | idx = largest; | |
71 | } | |
72 | } | |
73 | ||
88f1ebbc | 74 | static void cpudl_change_key(struct cpudl *cp, int idx, u64 new_dl) |
6bfd6d72 | 75 | { |
eec751ed | 76 | WARN_ON(idx == IDX_INVALID || !cpu_present(idx)); |
6bfd6d72 JL |
77 | |
78 | if (dl_time_before(new_dl, cp->elements[idx].dl)) { | |
79 | cp->elements[idx].dl = new_dl; | |
80 | cpudl_heapify(cp, idx); | |
81 | } else { | |
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)); | |
86 | idx = parent(idx); | |
87 | } | |
88 | } | |
89 | } | |
90 | ||
91 | static inline int cpudl_maximum(struct cpudl *cp) | |
92 | { | |
93 | return cp->elements[0].cpu; | |
94 | } | |
95 | ||
96 | /* | |
97 | * cpudl_find - find the best (later-dl) CPU in the system | |
98 | * @cp: the cpudl max-heap context | |
99 | * @p: the task | |
100 | * @later_mask: a mask to fill in with the selected CPUs (or NULL) | |
101 | * | |
102 | * Returns: int - best CPU (heap maximum if suitable) | |
103 | */ | |
104 | int cpudl_find(struct cpudl *cp, struct task_struct *p, | |
105 | struct cpumask *later_mask) | |
106 | { | |
107 | int best_cpu = -1; | |
108 | const struct sched_dl_entity *dl_se = &p->dl; | |
109 | ||
16b26943 | 110 | if (later_mask && |
9659e1ee | 111 | cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) { |
6bfd6d72 JL |
112 | best_cpu = cpumask_any(later_mask); |
113 | goto out; | |
114 | } else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) && | |
115 | dl_time_before(dl_se->deadline, cp->elements[0].dl)) { | |
116 | best_cpu = cpudl_maximum(cp); | |
117 | if (later_mask) | |
118 | cpumask_set_cpu(best_cpu, later_mask); | |
119 | } | |
120 | ||
121 | out: | |
eec751ed | 122 | WARN_ON(best_cpu != -1 && !cpu_present(best_cpu)); |
6bfd6d72 JL |
123 | |
124 | return best_cpu; | |
125 | } | |
126 | ||
127 | /* | |
128 | * cpudl_set - update the cpudl max-heap | |
129 | * @cp: the cpudl max-heap context | |
130 | * @cpu: the target cpu | |
131 | * @dl: the new earliest deadline for this cpu | |
132 | * | |
133 | * Notes: assumes cpu_rq(cpu)->lock is locked | |
134 | * | |
135 | * Returns: (void) | |
136 | */ | |
137 | void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid) | |
138 | { | |
139 | int old_idx, new_cpu; | |
140 | unsigned long flags; | |
141 | ||
82b95800 | 142 | WARN_ON(!cpu_present(cpu)); |
6bfd6d72 JL |
143 | |
144 | raw_spin_lock_irqsave(&cp->lock, flags); | |
944770ab | 145 | old_idx = cp->elements[cpu].idx; |
6bfd6d72 JL |
146 | if (!is_valid) { |
147 | /* remove item */ | |
148 | if (old_idx == IDX_INVALID) { | |
149 | /* | |
150 | * Nothing to remove if old_idx was invalid. | |
151 | * This could happen if a rq_offline_dl is | |
152 | * called for a CPU without -dl tasks running. | |
153 | */ | |
154 | goto out; | |
155 | } | |
156 | new_cpu = cp->elements[cp->size - 1].cpu; | |
157 | cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl; | |
158 | cp->elements[old_idx].cpu = new_cpu; | |
159 | cp->size--; | |
944770ab PZ |
160 | cp->elements[new_cpu].idx = old_idx; |
161 | cp->elements[cpu].idx = IDX_INVALID; | |
6bfd6d72 JL |
162 | while (old_idx > 0 && dl_time_before( |
163 | cp->elements[parent(old_idx)].dl, | |
164 | cp->elements[old_idx].dl)) { | |
165 | cpudl_exchange(cp, old_idx, parent(old_idx)); | |
166 | old_idx = parent(old_idx); | |
167 | } | |
168 | cpumask_set_cpu(cpu, cp->free_cpus); | |
169 | cpudl_heapify(cp, old_idx); | |
170 | ||
171 | goto out; | |
172 | } | |
173 | ||
174 | if (old_idx == IDX_INVALID) { | |
175 | cp->size++; | |
176 | cp->elements[cp->size - 1].dl = 0; | |
177 | cp->elements[cp->size - 1].cpu = cpu; | |
944770ab | 178 | cp->elements[cpu].idx = cp->size - 1; |
6bfd6d72 JL |
179 | cpudl_change_key(cp, cp->size - 1, dl); |
180 | cpumask_clear_cpu(cpu, cp->free_cpus); | |
181 | } else { | |
182 | cpudl_change_key(cp, old_idx, dl); | |
183 | } | |
184 | ||
185 | out: | |
186 | raw_spin_unlock_irqrestore(&cp->lock, flags); | |
187 | } | |
188 | ||
16b26943 XP |
189 | /* |
190 | * cpudl_set_freecpu - Set the cpudl.free_cpus | |
191 | * @cp: the cpudl max-heap context | |
192 | * @cpu: rd attached cpu | |
193 | */ | |
194 | void cpudl_set_freecpu(struct cpudl *cp, int cpu) | |
195 | { | |
196 | cpumask_set_cpu(cpu, cp->free_cpus); | |
197 | } | |
198 | ||
199 | /* | |
200 | * cpudl_clear_freecpu - Clear the cpudl.free_cpus | |
201 | * @cp: the cpudl max-heap context | |
202 | * @cpu: rd attached cpu | |
203 | */ | |
204 | void cpudl_clear_freecpu(struct cpudl *cp, int cpu) | |
205 | { | |
206 | cpumask_clear_cpu(cpu, cp->free_cpus); | |
207 | } | |
208 | ||
6bfd6d72 JL |
209 | /* |
210 | * cpudl_init - initialize the cpudl structure | |
211 | * @cp: the cpudl max-heap context | |
212 | */ | |
213 | int cpudl_init(struct cpudl *cp) | |
214 | { | |
215 | int i; | |
216 | ||
217 | memset(cp, 0, sizeof(*cp)); | |
218 | raw_spin_lock_init(&cp->lock); | |
219 | cp->size = 0; | |
944770ab PZ |
220 | |
221 | cp->elements = kcalloc(nr_cpu_ids, | |
222 | sizeof(struct cpudl_item), | |
223 | GFP_KERNEL); | |
224 | if (!cp->elements) | |
225 | return -ENOMEM; | |
226 | ||
16b26943 | 227 | if (!zalloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) { |
944770ab | 228 | kfree(cp->elements); |
6bfd6d72 | 229 | return -ENOMEM; |
944770ab PZ |
230 | } |
231 | ||
232 | for_each_possible_cpu(i) | |
233 | cp->elements[i].idx = IDX_INVALID; | |
234 | ||
6bfd6d72 JL |
235 | return 0; |
236 | } | |
237 | ||
238 | /* | |
239 | * cpudl_cleanup - clean up the cpudl structure | |
240 | * @cp: the cpudl max-heap context | |
241 | */ | |
242 | void cpudl_cleanup(struct cpudl *cp) | |
243 | { | |
6a7cd273 | 244 | free_cpumask_var(cp->free_cpus); |
944770ab | 245 | kfree(cp->elements); |
6bfd6d72 | 246 | } |