Lines Matching +full:if +full:- +full:idx
1 // SPDX-License-Identifier: GPL-2.0-only
13 return (i - 1) >> 1; in parent()
26 static void cpudl_heapify_down(struct cpudl *cp, int idx) in cpudl_heapify_down() argument
30 int orig_cpu = cp->elements[idx].cpu; in cpudl_heapify_down()
31 u64 orig_dl = cp->elements[idx].dl; in cpudl_heapify_down()
33 if (left_child(idx) >= cp->size) in cpudl_heapify_down()
40 l = left_child(idx); in cpudl_heapify_down()
41 r = right_child(idx); in cpudl_heapify_down()
42 largest = idx; in cpudl_heapify_down()
45 if ((l < cp->size) && dl_time_before(orig_dl, in cpudl_heapify_down()
46 cp->elements[l].dl)) { in cpudl_heapify_down()
48 largest_dl = cp->elements[l].dl; in cpudl_heapify_down()
50 if ((r < cp->size) && dl_time_before(largest_dl, in cpudl_heapify_down()
51 cp->elements[r].dl)) in cpudl_heapify_down()
54 if (largest == idx) in cpudl_heapify_down()
57 /* pull largest child onto idx */ in cpudl_heapify_down()
58 cp->elements[idx].cpu = cp->elements[largest].cpu; in cpudl_heapify_down()
59 cp->elements[idx].dl = cp->elements[largest].dl; in cpudl_heapify_down()
60 cp->elements[cp->elements[idx].cpu].idx = idx; in cpudl_heapify_down()
61 idx = largest; in cpudl_heapify_down()
64 cp->elements[idx].cpu = orig_cpu; in cpudl_heapify_down()
65 cp->elements[idx].dl = orig_dl; in cpudl_heapify_down()
66 cp->elements[cp->elements[idx].cpu].idx = idx; in cpudl_heapify_down()
69 static void cpudl_heapify_up(struct cpudl *cp, int idx) in cpudl_heapify_up() argument
73 int orig_cpu = cp->elements[idx].cpu; in cpudl_heapify_up()
74 u64 orig_dl = cp->elements[idx].dl; in cpudl_heapify_up()
76 if (idx == 0) in cpudl_heapify_up()
80 p = parent(idx); in cpudl_heapify_up()
81 if (dl_time_before(orig_dl, cp->elements[p].dl)) in cpudl_heapify_up()
83 /* pull parent onto idx */ in cpudl_heapify_up()
84 cp->elements[idx].cpu = cp->elements[p].cpu; in cpudl_heapify_up()
85 cp->elements[idx].dl = cp->elements[p].dl; in cpudl_heapify_up()
86 cp->elements[cp->elements[idx].cpu].idx = idx; in cpudl_heapify_up()
87 idx = p; in cpudl_heapify_up()
88 } while (idx != 0); in cpudl_heapify_up()
90 cp->elements[idx].cpu = orig_cpu; in cpudl_heapify_up()
91 cp->elements[idx].dl = orig_dl; in cpudl_heapify_up()
92 cp->elements[cp->elements[idx].cpu].idx = idx; in cpudl_heapify_up()
95 static void cpudl_heapify(struct cpudl *cp, int idx) in cpudl_heapify() argument
97 if (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl, in cpudl_heapify()
98 cp->elements[idx].dl)) in cpudl_heapify()
99 cpudl_heapify_up(cp, idx); in cpudl_heapify()
101 cpudl_heapify_down(cp, idx); in cpudl_heapify()
106 return cp->elements[0].cpu; in cpudl_maximum()
110 * cpudl_find - find the best (later-dl) CPU in the system
111 * @cp: the cpudl max-heap context
115 * Returns: int - CPUs were found
120 const struct sched_dl_entity *dl_se = &p->dl; in cpudl_find()
122 if (later_mask && in cpudl_find()
123 cpumask_and(later_mask, cp->free_cpus, &p->cpus_mask)) { in cpudl_find()
125 int cpu, max_cpu = -1; in cpudl_find()
127 if (!sched_asym_cpucap_active()) in cpudl_find()
132 if (!dl_task_fits_capacity(p, cpu)) { in cpudl_find()
137 if (cap > max_cap || in cpudl_find()
145 if (cpumask_empty(later_mask)) in cpudl_find()
152 WARN_ON(best_cpu != -1 && !cpu_present(best_cpu)); in cpudl_find()
154 if (cpumask_test_cpu(best_cpu, &p->cpus_mask) && in cpudl_find()
155 dl_time_before(dl_se->deadline, cp->elements[0].dl)) { in cpudl_find()
156 if (later_mask) in cpudl_find()
166 * cpudl_clear - remove a CPU from the cpudl max-heap
167 * @cp: the cpudl max-heap context
170 * Notes: assumes cpu_rq(cpu)->lock is locked
181 raw_spin_lock_irqsave(&cp->lock, flags); in cpudl_clear()
183 old_idx = cp->elements[cpu].idx; in cpudl_clear()
184 if (old_idx == IDX_INVALID) { in cpudl_clear()
186 * Nothing to remove if old_idx was invalid. in cpudl_clear()
187 * This could happen if a rq_offline_dl is in cpudl_clear()
188 * called for a CPU without -dl tasks running. in cpudl_clear()
191 new_cpu = cp->elements[cp->size - 1].cpu; in cpudl_clear()
192 cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl; in cpudl_clear()
193 cp->elements[old_idx].cpu = new_cpu; in cpudl_clear()
194 cp->size--; in cpudl_clear()
195 cp->elements[new_cpu].idx = old_idx; in cpudl_clear()
196 cp->elements[cpu].idx = IDX_INVALID; in cpudl_clear()
199 cpumask_set_cpu(cpu, cp->free_cpus); in cpudl_clear()
201 raw_spin_unlock_irqrestore(&cp->lock, flags); in cpudl_clear()
205 * cpudl_set - update the cpudl max-heap
206 * @cp: the cpudl max-heap context
210 * Notes: assumes cpu_rq(cpu)->lock is locked
221 raw_spin_lock_irqsave(&cp->lock, flags); in cpudl_set()
223 old_idx = cp->elements[cpu].idx; in cpudl_set()
224 if (old_idx == IDX_INVALID) { in cpudl_set()
225 int new_idx = cp->size++; in cpudl_set()
227 cp->elements[new_idx].dl = dl; in cpudl_set()
228 cp->elements[new_idx].cpu = cpu; in cpudl_set()
229 cp->elements[cpu].idx = new_idx; in cpudl_set()
231 cpumask_clear_cpu(cpu, cp->free_cpus); in cpudl_set()
233 cp->elements[old_idx].dl = dl; in cpudl_set()
237 raw_spin_unlock_irqrestore(&cp->lock, flags); in cpudl_set()
241 * cpudl_set_freecpu - Set the cpudl.free_cpus
242 * @cp: the cpudl max-heap context
247 cpumask_set_cpu(cpu, cp->free_cpus); in cpudl_set_freecpu()
251 * cpudl_clear_freecpu - Clear the cpudl.free_cpus
252 * @cp: the cpudl max-heap context
257 cpumask_clear_cpu(cpu, cp->free_cpus); in cpudl_clear_freecpu()
261 * cpudl_init - initialize the cpudl structure
262 * @cp: the cpudl max-heap context
268 raw_spin_lock_init(&cp->lock); in cpudl_init()
269 cp->size = 0; in cpudl_init()
271 cp->elements = kcalloc(nr_cpu_ids, in cpudl_init()
274 if (!cp->elements) in cpudl_init()
275 return -ENOMEM; in cpudl_init()
277 if (!zalloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) { in cpudl_init()
278 kfree(cp->elements); in cpudl_init()
279 return -ENOMEM; in cpudl_init()
283 cp->elements[i].idx = IDX_INVALID; in cpudl_init()
289 * cpudl_cleanup - clean up the cpudl structure
290 * @cp: the cpudl max-heap context
294 free_cpumask_var(cp->free_cpus); in cpudl_cleanup()
295 kfree(cp->elements); in cpudl_cleanup()