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 | ||
110 | if (later_mask && cpumask_and(later_mask, cp->free_cpus, | |
111 | &p->cpus_allowed) && cpumask_and(later_mask, | |
112 | later_mask, cpu_active_mask)) { | |
113 | best_cpu = cpumask_any(later_mask); | |
114 | goto out; | |
115 | } else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) && | |
116 | dl_time_before(dl_se->deadline, cp->elements[0].dl)) { | |
117 | best_cpu = cpudl_maximum(cp); | |
118 | if (later_mask) | |
119 | cpumask_set_cpu(best_cpu, later_mask); | |
120 | } | |
121 | ||
122 | out: | |
eec751ed | 123 | WARN_ON(best_cpu != -1 && !cpu_present(best_cpu)); |
6bfd6d72 JL |
124 | |
125 | return best_cpu; | |
126 | } | |
127 | ||
128 | /* | |
129 | * cpudl_set - update the cpudl max-heap | |
130 | * @cp: the cpudl max-heap context | |
131 | * @cpu: the target cpu | |
132 | * @dl: the new earliest deadline for this cpu | |
133 | * | |
134 | * Notes: assumes cpu_rq(cpu)->lock is locked | |
135 | * | |
136 | * Returns: (void) | |
137 | */ | |
138 | void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid) | |
139 | { | |
140 | int old_idx, new_cpu; | |
141 | unsigned long flags; | |
142 | ||
82b95800 | 143 | WARN_ON(!cpu_present(cpu)); |
6bfd6d72 JL |
144 | |
145 | raw_spin_lock_irqsave(&cp->lock, flags); | |
944770ab | 146 | old_idx = cp->elements[cpu].idx; |
6bfd6d72 JL |
147 | if (!is_valid) { |
148 | /* remove item */ | |
149 | if (old_idx == IDX_INVALID) { | |
150 | /* | |
151 | * Nothing to remove if old_idx was invalid. | |
152 | * This could happen if a rq_offline_dl is | |
153 | * called for a CPU without -dl tasks running. | |
154 | */ | |
155 | goto out; | |
156 | } | |
157 | new_cpu = cp->elements[cp->size - 1].cpu; | |
158 | cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl; | |
159 | cp->elements[old_idx].cpu = new_cpu; | |
160 | cp->size--; | |
944770ab PZ |
161 | cp->elements[new_cpu].idx = old_idx; |
162 | cp->elements[cpu].idx = IDX_INVALID; | |
6bfd6d72 JL |
163 | while (old_idx > 0 && dl_time_before( |
164 | cp->elements[parent(old_idx)].dl, | |
165 | cp->elements[old_idx].dl)) { | |
166 | cpudl_exchange(cp, old_idx, parent(old_idx)); | |
167 | old_idx = parent(old_idx); | |
168 | } | |
169 | cpumask_set_cpu(cpu, cp->free_cpus); | |
170 | cpudl_heapify(cp, old_idx); | |
171 | ||
172 | goto out; | |
173 | } | |
174 | ||
175 | if (old_idx == IDX_INVALID) { | |
176 | cp->size++; | |
177 | cp->elements[cp->size - 1].dl = 0; | |
178 | cp->elements[cp->size - 1].cpu = cpu; | |
944770ab | 179 | cp->elements[cpu].idx = cp->size - 1; |
6bfd6d72 JL |
180 | cpudl_change_key(cp, cp->size - 1, dl); |
181 | cpumask_clear_cpu(cpu, cp->free_cpus); | |
182 | } else { | |
183 | cpudl_change_key(cp, old_idx, dl); | |
184 | } | |
185 | ||
186 | out: | |
187 | raw_spin_unlock_irqrestore(&cp->lock, flags); | |
188 | } | |
189 | ||
190 | /* | |
191 | * cpudl_init - initialize the cpudl structure | |
192 | * @cp: the cpudl max-heap context | |
193 | */ | |
194 | int cpudl_init(struct cpudl *cp) | |
195 | { | |
196 | int i; | |
197 | ||
198 | memset(cp, 0, sizeof(*cp)); | |
199 | raw_spin_lock_init(&cp->lock); | |
200 | cp->size = 0; | |
944770ab PZ |
201 | |
202 | cp->elements = kcalloc(nr_cpu_ids, | |
203 | sizeof(struct cpudl_item), | |
204 | GFP_KERNEL); | |
205 | if (!cp->elements) | |
206 | return -ENOMEM; | |
207 | ||
208 | if (!alloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) { | |
209 | kfree(cp->elements); | |
6bfd6d72 | 210 | return -ENOMEM; |
944770ab PZ |
211 | } |
212 | ||
213 | for_each_possible_cpu(i) | |
214 | cp->elements[i].idx = IDX_INVALID; | |
215 | ||
6bfd6d72 JL |
216 | cpumask_setall(cp->free_cpus); |
217 | ||
218 | return 0; | |
219 | } | |
220 | ||
221 | /* | |
222 | * cpudl_cleanup - clean up the cpudl structure | |
223 | * @cp: the cpudl max-heap context | |
224 | */ | |
225 | void cpudl_cleanup(struct cpudl *cp) | |
226 | { | |
6a7cd273 | 227 | free_cpumask_var(cp->free_cpus); |
944770ab | 228 | kfree(cp->elements); |
6bfd6d72 | 229 | } |