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