Branch data Line data Source code
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>
16 : : #include "cpudeadline.h"
17 : :
18 : : static inline int parent(int i)
19 : : {
20 : 0 : return (i - 1) >> 1;
21 : : }
22 : :
23 : : static inline int left_child(int i)
24 : : {
25 : 0 : return (i << 1) + 1;
26 : : }
27 : :
28 : : static inline int right_child(int i)
29 : : {
30 : 0 : return (i << 1) + 2;
31 : : }
32 : :
33 : : static inline int dl_time_before(u64 a, u64 b)
34 : : {
35 : 0 : return (s64)(a - b) < 0;
36 : : }
37 : :
38 : 0 : static void cpudl_exchange(struct cpudl *cp, int a, int b)
39 : : {
40 : 0 : int cpu_a = cp->elements[a].cpu, cpu_b = cp->elements[b].cpu;
41 : :
42 : 0 : swap(cp->elements[a], cp->elements[b]);
43 : 0 : swap(cp->cpu_to_idx[cpu_a], cp->cpu_to_idx[cpu_b]);
44 : 0 : }
45 : :
46 : 0 : static void cpudl_heapify(struct cpudl *cp, int idx)
47 : : {
48 : : int l, r, largest;
49 : :
50 : : /* adapted from lib/prio_heap.c */
51 : : while(1) {
52 : : l = left_child(idx);
53 : : r = right_child(idx);
54 : : largest = idx;
55 : :
56 [ # # ][ # # ]: 0 : if ((l < cp->size) && dl_time_before(cp->elements[idx].dl,
57 : : cp->elements[l].dl))
58 : : largest = l;
59 [ # # ][ # # ]: 0 : if ((r < cp->size) && dl_time_before(cp->elements[largest].dl,
60 : : cp->elements[r].dl))
61 : : largest = r;
62 [ # # ]: 0 : if (largest == idx)
63 : : break;
64 : :
65 : : /* Push idx down the heap one level and bump one up */
66 : 0 : cpudl_exchange(cp, largest, idx);
67 : : idx = largest;
68 : 0 : }
69 : 0 : }
70 : :
71 : 0 : static void cpudl_change_key(struct cpudl *cp, int idx, u64 new_dl)
72 : : {
73 [ # # ][ # # ]: 0 : WARN_ON(idx == IDX_INVALID || !cpu_present(idx));
[ # # ]
74 : :
75 [ # # ]: 0 : if (dl_time_before(new_dl, cp->elements[idx].dl)) {
76 : 0 : cp->elements[idx].dl = new_dl;
77 : 0 : cpudl_heapify(cp, idx);
78 : : } else {
79 : 0 : cp->elements[idx].dl = new_dl;
80 [ # # ][ # # ]: 0 : while (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl,
81 : : cp->elements[idx].dl)) {
82 : 0 : cpudl_exchange(cp, idx, parent(idx));
83 : : idx = parent(idx);
84 : : }
85 : : }
86 : 0 : }
87 : :
88 : : static inline int cpudl_maximum(struct cpudl *cp)
89 : : {
90 : : return cp->elements[0].cpu;
91 : : }
92 : :
93 : : /*
94 : : * cpudl_find - find the best (later-dl) CPU in the system
95 : : * @cp: the cpudl max-heap context
96 : : * @p: the task
97 : : * @later_mask: a mask to fill in with the selected CPUs (or NULL)
98 : : *
99 : : * Returns: int - best CPU (heap maximum if suitable)
100 : : */
101 : 0 : int cpudl_find(struct cpudl *cp, struct task_struct *p,
102 : : struct cpumask *later_mask)
103 : : {
104 : : int best_cpu = -1;
105 : : const struct sched_dl_entity *dl_se = &p->dl;
106 : :
107 [ # # ][ # # ]: 0 : if (later_mask && cpumask_and(later_mask, cp->free_cpus,
108 [ # # ]: 0 : &p->cpus_allowed) && cpumask_and(later_mask,
109 : : later_mask, cpu_active_mask)) {
110 : : best_cpu = cpumask_any(later_mask);
111 : 0 : goto out;
112 [ # # ][ # # ]: 0 : } else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) &&
113 : 0 : dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
114 : : best_cpu = cpudl_maximum(cp);
115 [ # # ]: 0 : if (later_mask)
116 : : cpumask_set_cpu(best_cpu, later_mask);
117 : : }
118 : :
119 : : out:
120 [ # # ][ # # ]: 0 : WARN_ON(best_cpu != -1 && !cpu_present(best_cpu));
[ # # ]
121 : :
122 : 0 : return best_cpu;
123 : : }
124 : :
125 : : /*
126 : : * cpudl_set - update the cpudl max-heap
127 : : * @cp: the cpudl max-heap context
128 : : * @cpu: the target cpu
129 : : * @dl: the new earliest deadline for this cpu
130 : : *
131 : : * Notes: assumes cpu_rq(cpu)->lock is locked
132 : : *
133 : : * Returns: (void)
134 : : */
135 : 0 : void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)
136 : : {
137 : : int old_idx, new_cpu;
138 : : unsigned long flags;
139 : :
140 [ - + ]: 1320 : WARN_ON(!cpu_present(cpu));
141 : :
142 : 1320 : raw_spin_lock_irqsave(&cp->lock, flags);
143 : 1320 : old_idx = cp->cpu_to_idx[cpu];
144 [ + - ]: 2640 : if (!is_valid) {
145 : : /* remove item */
146 [ - + ]: 1320 : if (old_idx == IDX_INVALID) {
147 : : /*
148 : : * Nothing to remove if old_idx was invalid.
149 : : * This could happen if a rq_offline_dl is
150 : : * called for a CPU without -dl tasks running.
151 : : */
152 : : goto out;
153 : : }
154 : 0 : new_cpu = cp->elements[cp->size - 1].cpu;
155 : 0 : cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl;
156 : 0 : cp->elements[old_idx].cpu = new_cpu;
157 : 0 : cp->size--;
158 : 0 : cp->cpu_to_idx[new_cpu] = old_idx;
159 : 0 : cp->cpu_to_idx[cpu] = IDX_INVALID;
160 [ # # ][ # # ]: 0 : while (old_idx > 0 && dl_time_before(
161 : : cp->elements[parent(old_idx)].dl,
162 : : cp->elements[old_idx].dl)) {
163 : 0 : cpudl_exchange(cp, old_idx, parent(old_idx));
164 : : old_idx = parent(old_idx);
165 : : }
166 : : cpumask_set_cpu(cpu, cp->free_cpus);
167 : 0 : cpudl_heapify(cp, old_idx);
168 : :
169 : 0 : goto out;
170 : : }
171 : :
172 [ # # ]: 0 : if (old_idx == IDX_INVALID) {
173 : 0 : cp->size++;
174 : 0 : cp->elements[cp->size - 1].dl = 0;
175 : 0 : cp->elements[cp->size - 1].cpu = cpu;
176 : 0 : cp->cpu_to_idx[cpu] = cp->size - 1;
177 : 0 : cpudl_change_key(cp, cp->size - 1, dl);
178 : : cpumask_clear_cpu(cpu, cp->free_cpus);
179 : : } else {
180 : 0 : cpudl_change_key(cp, old_idx, dl);
181 : : }
182 : :
183 : : out:
184 : 1320 : raw_spin_unlock_irqrestore(&cp->lock, flags);
185 : 1320 : }
186 : :
187 : : /*
188 : : * cpudl_init - initialize the cpudl structure
189 : : * @cp: the cpudl max-heap context
190 : : */
191 : 0 : int cpudl_init(struct cpudl *cp)
192 : : {
193 : : int i;
194 : :
195 : 159 : memset(cp, 0, sizeof(*cp));
196 : 159 : raw_spin_lock_init(&cp->lock);
197 : 159 : cp->size = 0;
198 [ + + ]: 1590 : for (i = 0; i < NR_CPUS; i++)
199 : 1272 : cp->cpu_to_idx[i] = IDX_INVALID;
200 : : if (!alloc_cpumask_var(&cp->free_cpus, GFP_KERNEL))
201 : : return -ENOMEM;
202 : : cpumask_setall(cp->free_cpus);
203 : :
204 : : return 0;
205 : : }
206 : :
207 : : /*
208 : : * cpudl_cleanup - clean up the cpudl structure
209 : : * @cp: the cpudl max-heap context
210 : : */
211 : 0 : void cpudl_cleanup(struct cpudl *cp)
212 : : {
213 : : /*
214 : : * nothing to do for the moment
215 : : */
216 : 159 : }
|
