39 static void cpudl_exchange(struct cpudl *cp, int a, int b)  in cpudl_exchange()  argument
41 	int cpu_a = cp->elements[a].cpu, cpu_b = cp->elements[b].cpu;  in cpudl_exchange()
43 	swap(cp->elements[a].cpu, cp->elements[b].cpu);  in cpudl_exchange()
44 	swap(cp->elements[a].dl , cp->elements[b].dl );  in cpudl_exchange()
46 	swap(cp->elements[cpu_a].idx, cp->elements[cpu_b].idx);  in cpudl_exchange()
49 static void cpudl_heapify(struct cpudl *cp, int idx)  in cpudl_heapify()  argument
59 		if ((l < cp->size) && dl_time_before(cp->elements[idx].dl,  in cpudl_heapify()
60 							cp->elements[l].dl))  in cpudl_heapify()
62 		if ((r < cp->size) && dl_time_before(cp->elements[largest].dl,  in cpudl_heapify()
63 							cp->elements[r].dl))  in cpudl_heapify()
69 		cpudl_exchange(cp, largest, idx);  in cpudl_heapify()
74 static void cpudl_change_key(struct cpudl *cp, int idx, u64 new_dl)  in cpudl_change_key()  argument
78 	if (dl_time_before(new_dl, cp->elements[idx].dl)) {  in cpudl_change_key()
79 		cp->elements[idx].dl = new_dl;  in cpudl_change_key()
80 		cpudl_heapify(cp, idx);  in cpudl_change_key()
82 		cp->elements[idx].dl = new_dl;  in cpudl_change_key()
83 		while (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl,  in cpudl_change_key()
84 					cp->elements[idx].dl)) {  in cpudl_change_key()
85 			cpudl_exchange(cp, idx, parent(idx));  in cpudl_change_key()
91 static inline int cpudl_maximum(struct cpudl *cp)  in cpudl_maximum()  argument
93 	return cp->elements[0].cpu;  in cpudl_maximum()
104 int cpudl_find(struct cpudl *cp, struct task_struct *p,  in cpudl_find()  argument
111 	    cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {  in cpudl_find()
114 	} else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) &&  in cpudl_find()
115 			dl_time_before(dl_se->deadline, cp->elements[0].dl)) {  in cpudl_find()
116 		best_cpu = cpudl_maximum(cp);  in cpudl_find()
137 void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)  in cpudl_set()  argument
144 	raw_spin_lock_irqsave(&cp->lock, flags);  in cpudl_set()
145 	old_idx = cp->elements[cpu].idx;  in cpudl_set()
156 		new_cpu = cp->elements[cp->size - 1].cpu;  in cpudl_set()
157 		cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl;  in cpudl_set()
158 		cp->elements[old_idx].cpu = new_cpu;  in cpudl_set()
159 		cp->size--;  in cpudl_set()
160 		cp->elements[new_cpu].idx = old_idx;  in cpudl_set()
161 		cp->elements[cpu].idx = IDX_INVALID;  in cpudl_set()
163 				cp->elements[parent(old_idx)].dl,  in cpudl_set()
164 				cp->elements[old_idx].dl)) {  in cpudl_set()
165 			cpudl_exchange(cp, old_idx, parent(old_idx));  in cpudl_set()
168 		cpumask_set_cpu(cpu, cp->free_cpus);  in cpudl_set()
169                 cpudl_heapify(cp, old_idx);  in cpudl_set()
175 		cp->size++;  in cpudl_set()
176 		cp->elements[cp->size - 1].dl = 0;  in cpudl_set()
177 		cp->elements[cp->size - 1].cpu = cpu;  in cpudl_set()
178 		cp->elements[cpu].idx = cp->size - 1;  in cpudl_set()
179 		cpudl_change_key(cp, cp->size - 1, dl);  in cpudl_set()
180 		cpumask_clear_cpu(cpu, cp->free_cpus);  in cpudl_set()
182 		cpudl_change_key(cp, old_idx, dl);  in cpudl_set()
186 	raw_spin_unlock_irqrestore(&cp->lock, flags);  in cpudl_set()
194 void cpudl_set_freecpu(struct cpudl *cp, int cpu)  in cpudl_set_freecpu()  argument
196 	cpumask_set_cpu(cpu, cp->free_cpus);  in cpudl_set_freecpu()
204 void cpudl_clear_freecpu(struct cpudl *cp, int cpu)  in cpudl_clear_freecpu()  argument
206 	cpumask_clear_cpu(cpu, cp->free_cpus);  in cpudl_clear_freecpu()
213 int cpudl_init(struct cpudl *cp)  in cpudl_init()  argument
217 	memset(cp, 0, sizeof(*cp));  in cpudl_init()
218 	raw_spin_lock_init(&cp->lock);  in cpudl_init()
219 	cp->size = 0;  in cpudl_init()
221 	cp->elements = kcalloc(nr_cpu_ids,  in cpudl_init()
224 	if (!cp->elements)  in cpudl_init()
227 	if (!zalloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) {  in cpudl_init()
228 		kfree(cp->elements);  in cpudl_init()
233 		cp->elements[i].idx = IDX_INVALID;  in cpudl_init()
242 void cpudl_cleanup(struct cpudl *cp)  in cpudl_cleanup()  argument
244 	free_cpumask_var(cp->free_cpus);  in cpudl_cleanup()
245 	kfree(cp->elements);  in cpudl_cleanup()