34 static void cpudl_exchange(struct cpudl *cp, int a, int b)  in cpudl_exchange()  argument
36 	int cpu_a = cp->elements[a].cpu, cpu_b = cp->elements[b].cpu;  in cpudl_exchange()
38 	swap(cp->elements[a].cpu, cp->elements[b].cpu);  in cpudl_exchange()
39 	swap(cp->elements[a].dl , cp->elements[b].dl );  in cpudl_exchange()
41 	swap(cp->elements[cpu_a].idx, cp->elements[cpu_b].idx);  in cpudl_exchange()
44 static void cpudl_heapify(struct cpudl *cp, int idx)  in cpudl_heapify()  argument
54 		if ((l < cp->size) && dl_time_before(cp->elements[idx].dl,  in cpudl_heapify()
55 							cp->elements[l].dl))  in cpudl_heapify()
57 		if ((r < cp->size) && dl_time_before(cp->elements[largest].dl,  in cpudl_heapify()
58 							cp->elements[r].dl))  in cpudl_heapify()
64 		cpudl_exchange(cp, largest, idx);  in cpudl_heapify()
69 static void cpudl_change_key(struct cpudl *cp, int idx, u64 new_dl)  in cpudl_change_key()  argument
73 	if (dl_time_before(new_dl, cp->elements[idx].dl)) {  in cpudl_change_key()
74 		cp->elements[idx].dl = new_dl;  in cpudl_change_key()
75 		cpudl_heapify(cp, idx);  in cpudl_change_key()
77 		cp->elements[idx].dl = new_dl;  in cpudl_change_key()
78 		while (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl,  in cpudl_change_key()
79 					cp->elements[idx].dl)) {  in cpudl_change_key()
80 			cpudl_exchange(cp, idx, parent(idx));  in cpudl_change_key()
86 static inline int cpudl_maximum(struct cpudl *cp)  in cpudl_maximum()  argument
88 	return cp->elements[0].cpu;  in cpudl_maximum()
99 int cpudl_find(struct cpudl *cp, struct task_struct *p,  in cpudl_find()  argument
106 	    cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {  in cpudl_find()
109 	} else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) &&  in cpudl_find()
110 			dl_time_before(dl_se->deadline, cp->elements[0].dl)) {  in cpudl_find()
111 		best_cpu = cpudl_maximum(cp);  in cpudl_find()
132 void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)  in cpudl_set()  argument
139 	raw_spin_lock_irqsave(&cp->lock, flags);  in cpudl_set()
140 	old_idx = cp->elements[cpu].idx;  in cpudl_set()
151 		new_cpu = cp->elements[cp->size - 1].cpu;  in cpudl_set()
152 		cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl;  in cpudl_set()
153 		cp->elements[old_idx].cpu = new_cpu;  in cpudl_set()
154 		cp->size--;  in cpudl_set()
155 		cp->elements[new_cpu].idx = old_idx;  in cpudl_set()
156 		cp->elements[cpu].idx = IDX_INVALID;  in cpudl_set()
158 				cp->elements[parent(old_idx)].dl,  in cpudl_set()
159 				cp->elements[old_idx].dl)) {  in cpudl_set()
160 			cpudl_exchange(cp, old_idx, parent(old_idx));  in cpudl_set()
163 		cpumask_set_cpu(cpu, cp->free_cpus);  in cpudl_set()
164                 cpudl_heapify(cp, old_idx);  in cpudl_set()
170 		cp->size++;  in cpudl_set()
171 		cp->elements[cp->size - 1].dl = 0;  in cpudl_set()
172 		cp->elements[cp->size - 1].cpu = cpu;  in cpudl_set()
173 		cp->elements[cpu].idx = cp->size - 1;  in cpudl_set()
174 		cpudl_change_key(cp, cp->size - 1, dl);  in cpudl_set()
175 		cpumask_clear_cpu(cpu, cp->free_cpus);  in cpudl_set()
177 		cpudl_change_key(cp, old_idx, dl);  in cpudl_set()
181 	raw_spin_unlock_irqrestore(&cp->lock, flags);  in cpudl_set()
189 void cpudl_set_freecpu(struct cpudl *cp, int cpu)  in cpudl_set_freecpu()  argument
191 	cpumask_set_cpu(cpu, cp->free_cpus);  in cpudl_set_freecpu()
199 void cpudl_clear_freecpu(struct cpudl *cp, int cpu)  in cpudl_clear_freecpu()  argument
201 	cpumask_clear_cpu(cpu, cp->free_cpus);  in cpudl_clear_freecpu()
208 int cpudl_init(struct cpudl *cp)  in cpudl_init()  argument
212 	memset(cp, 0, sizeof(*cp));  in cpudl_init()
213 	raw_spin_lock_init(&cp->lock);  in cpudl_init()
214 	cp->size = 0;  in cpudl_init()
216 	cp->elements = kcalloc(nr_cpu_ids,  in cpudl_init()
219 	if (!cp->elements)  in cpudl_init()
222 	if (!zalloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) {  in cpudl_init()
223 		kfree(cp->elements);  in cpudl_init()
228 		cp->elements[i].idx = IDX_INVALID;  in cpudl_init()
237 void cpudl_cleanup(struct cpudl *cp)  in cpudl_cleanup()  argument
239 	free_cpumask_var(cp->free_cpus);  in cpudl_cleanup()
240 	kfree(cp->elements);  in cpudl_cleanup()