Blame view
kernel/sched/cpupri.c
6.8 KB
6e0534f27 sched: use a 2-d ... |
1 |
/* |
391e43da7 sched: Move all s... |
2 |
* kernel/sched/cpupri.c |
6e0534f27 sched: use a 2-d ... |
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
* * CPU priority management * * Copyright (C) 2007-2008 Novell * * Author: Gregory Haskins <ghaskins@novell.com> * * This code tracks the priority of each CPU so that global migration * decisions are easy to calculate. Each CPU can be in a state as follows: * * (INVALID), IDLE, NORMAL, RT1, ... RT99 * * going from the lowest priority to the highest. CPUs in the INVALID state * are not eligible for routing. The system maintains this state with * a 2 dimensional bitmap (the first for priority class, the second for cpus * in that class). Therefore a typical application without affinity * restrictions can find a suitable CPU with O(1) complexity (e.g. two bit * searches). For tasks with affinity restrictions, the algorithm has a * worst case complexity of O(min(102, nr_domcpus)), though the scenario that * yields the worst case search is fairly contrived. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; version 2 * of the License. */ |
5a0e3ad6a include cleanup: ... |
29 |
#include <linux/gfp.h> |
8bd75c77b sched/rt: Move rt... |
30 31 |
#include <linux/sched.h> #include <linux/sched/rt.h> |
4dac0b638 sched/cpupri: Rep... |
32 |
#include <linux/slab.h> |
391e43da7 sched: Move all s... |
33 |
#include "cpupri.h" |
6e0534f27 sched: use a 2-d ... |
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
/* Convert between a 140 based task->prio, and our 102 based cpupri */ static int convert_prio(int prio) { int cpupri; if (prio == CPUPRI_INVALID) cpupri = CPUPRI_INVALID; else if (prio == MAX_PRIO) cpupri = CPUPRI_IDLE; else if (prio >= MAX_RT_PRIO) cpupri = CPUPRI_NORMAL; else cpupri = MAX_RT_PRIO - prio + 1; return cpupri; } |
6e0534f27 sched: use a 2-d ... |
51 52 53 54 |
/** * cpupri_find - find the best (lowest-pri) CPU in the system * @cp: The cpupri context * @p: The task |
13b8bd0a5 sched_rt: don't a... |
55 |
* @lowest_mask: A mask to fill in with selected CPUs (or NULL) |
6e0534f27 sched: use a 2-d ... |
56 57 |
* * Note: This function returns the recommended CPUs as calculated during the |
2a61aa401 Fix misspellings ... |
58 |
* current invocation. By the time the call returns, the CPUs may have in |
6e0534f27 sched: use a 2-d ... |
59 60 61 62 63 |
* fact changed priorities any number of times. While not ideal, it is not * an issue of correctness since the normal rebalancer logic will correct * any discrepancies created by racing against the uncertainty of the current * priority configuration. * |
e69f61862 sched: Fix some k... |
64 |
* Return: (int)bool - CPUs were found |
6e0534f27 sched: use a 2-d ... |
65 66 |
*/ int cpupri_find(struct cpupri *cp, struct task_struct *p, |
68e74568f sched: convert st... |
67 |
struct cpumask *lowest_mask) |
6e0534f27 sched: use a 2-d ... |
68 |
{ |
014acbf0d sched: Fix minor ... |
69 70 |
int idx = 0; int task_pri = convert_prio(p->prio); |
6e0534f27 sched: use a 2-d ... |
71 |
|
6227cb00c sched: Use CPUPRI... |
72 |
BUG_ON(task_pri >= CPUPRI_NR_PRIORITIES); |
c92211d9b sched/cpupri: Rem... |
73 74 |
for (idx = 0; idx < task_pri; idx++) { |
6e0534f27 sched: use a 2-d ... |
75 |
struct cpupri_vec *vec = &cp->pri_to_cpu[idx]; |
d473750b4 sched/cpupri: Fix... |
76 |
int skip = 0; |
6e0534f27 sched: use a 2-d ... |
77 |
|
c92211d9b sched/cpupri: Rem... |
78 |
if (!atomic_read(&(vec)->count)) |
d473750b4 sched/cpupri: Fix... |
79 |
skip = 1; |
c92211d9b sched/cpupri: Rem... |
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
/* * When looking at the vector, we need to read the counter, * do a memory barrier, then read the mask. * * Note: This is still all racey, but we can deal with it. * Ideally, we only want to look at masks that are set. * * If a mask is not set, then the only thing wrong is that we * did a little more work than necessary. * * If we read a zero count but the mask is set, because of the * memory barriers, that can only happen when the highest prio * task for a run queue has left the run queue, in which case, * it will be followed by a pull. If the task we are processing * fails to find a proper place to go, that pull request will * pull this task if the run queue is running at a lower * priority. */ smp_rmb(); |
6e0534f27 sched: use a 2-d ... |
99 |
|
d473750b4 sched/cpupri: Fix... |
100 101 102 |
/* Need to do the rmb for every iteration */ if (skip) continue; |
ade42e092 sched/core: Use t... |
103 |
if (cpumask_any_and(tsk_cpus_allowed(p), vec->mask) >= nr_cpu_ids) |
6e0534f27 sched: use a 2-d ... |
104 |
continue; |
07903af15 sched: Fix race i... |
105 |
if (lowest_mask) { |
ade42e092 sched/core: Use t... |
106 |
cpumask_and(lowest_mask, tsk_cpus_allowed(p), vec->mask); |
07903af15 sched: Fix race i... |
107 108 109 110 111 112 113 114 115 116 117 118 |
/* * We have to ensure that we have at least one bit * still set in the array, since the map could have * been concurrently emptied between the first and * second reads of vec->mask. If we hit this * condition, simply act as though we never hit this * priority level and continue on. */ if (cpumask_any(lowest_mask) >= nr_cpu_ids) continue; } |
6e0534f27 sched: use a 2-d ... |
119 120 121 122 123 124 125 126 127 128 |
return 1; } return 0; } /** * cpupri_set - update the cpu priority setting * @cp: The cpupri context * @cpu: The target cpu |
fa757281a kernel-doc: fix k... |
129 |
* @newpri: The priority (INVALID-RT99) to assign to this CPU |
6e0534f27 sched: use a 2-d ... |
130 131 132 133 134 135 136 |
* * Note: Assumes cpu_rq(cpu)->lock is locked * * Returns: (void) */ void cpupri_set(struct cpupri *cp, int cpu, int newpri) { |
014acbf0d sched: Fix minor ... |
137 138 139 |
int *currpri = &cp->cpu_to_pri[cpu]; int oldpri = *currpri; int do_mb = 0; |
6e0534f27 sched: use a 2-d ... |
140 141 142 143 144 145 146 147 148 149 |
newpri = convert_prio(newpri); BUG_ON(newpri >= CPUPRI_NR_PRIORITIES); if (newpri == oldpri) return; /* * If the cpu was currently mapped to a different value, we |
c3a2ae3d9 sched: Add new pr... |
150 151 |
* need to map it to the new value then remove the old value. * Note, we must add the new value first, otherwise we risk the |
5710f15b5 sched/cpupri: Rem... |
152 |
* cpu being missed by the priority loop in cpupri_find. |
6e0534f27 sched: use a 2-d ... |
153 |
*/ |
6e0534f27 sched: use a 2-d ... |
154 155 |
if (likely(newpri != CPUPRI_INVALID)) { struct cpupri_vec *vec = &cp->pri_to_cpu[newpri]; |
68e74568f sched: convert st... |
156 |
cpumask_set_cpu(cpu, vec->mask); |
c92211d9b sched/cpupri: Rem... |
157 158 159 160 161 |
/* * When adding a new vector, we update the mask first, * do a write memory barrier, and then update the count, to * make sure the vector is visible when count is set. */ |
4e857c58e arch: Mass conver... |
162 |
smp_mb__before_atomic(); |
c92211d9b sched/cpupri: Rem... |
163 |
atomic_inc(&(vec)->count); |
d473750b4 sched/cpupri: Fix... |
164 |
do_mb = 1; |
6e0534f27 sched: use a 2-d ... |
165 |
} |
c3a2ae3d9 sched: Add new pr... |
166 167 |
if (likely(oldpri != CPUPRI_INVALID)) { struct cpupri_vec *vec = &cp->pri_to_cpu[oldpri]; |
c92211d9b sched/cpupri: Rem... |
168 |
/* |
d473750b4 sched/cpupri: Fix... |
169 170 171 172 173 174 175 176 177 178 179 180 |
* Because the order of modification of the vec->count * is important, we must make sure that the update * of the new prio is seen before we decrement the * old prio. This makes sure that the loop sees * one or the other when we raise the priority of * the run queue. We don't care about when we lower the * priority, as that will trigger an rt pull anyway. * * We only need to do a memory barrier if we updated * the new priority vec. */ if (do_mb) |
4e857c58e arch: Mass conver... |
181 |
smp_mb__after_atomic(); |
d473750b4 sched/cpupri: Fix... |
182 183 |
/* |
c92211d9b sched/cpupri: Rem... |
184 185 186 187 |
* When removing from the vector, we decrement the counter first * do a memory barrier and then clear the mask. */ atomic_dec(&(vec)->count); |
4e857c58e arch: Mass conver... |
188 |
smp_mb__after_atomic(); |
c3a2ae3d9 sched: Add new pr... |
189 |
cpumask_clear_cpu(cpu, vec->mask); |
c3a2ae3d9 sched: Add new pr... |
190 |
} |
6e0534f27 sched: use a 2-d ... |
191 192 193 194 195 196 197 198 |
*currpri = newpri; } /** * cpupri_init - initialize the cpupri structure * @cp: The cpupri context * |
e69f61862 sched: Fix some k... |
199 |
* Return: -ENOMEM on memory allocation failure. |
6e0534f27 sched: use a 2-d ... |
200 |
*/ |
68c38fc3c sched: No need fo... |
201 |
int cpupri_init(struct cpupri *cp) |
6e0534f27 sched: use a 2-d ... |
202 203 204 205 206 207 208 |
{ int i; memset(cp, 0, sizeof(*cp)); for (i = 0; i < CPUPRI_NR_PRIORITIES; i++) { struct cpupri_vec *vec = &cp->pri_to_cpu[i]; |
c92211d9b sched/cpupri: Rem... |
209 |
atomic_set(&vec->count, 0); |
68c38fc3c sched: No need fo... |
210 |
if (!zalloc_cpumask_var(&vec->mask, GFP_KERNEL)) |
68e74568f sched: convert st... |
211 |
goto cleanup; |
6e0534f27 sched: use a 2-d ... |
212 |
} |
4dac0b638 sched/cpupri: Rep... |
213 214 215 |
cp->cpu_to_pri = kcalloc(nr_cpu_ids, sizeof(int), GFP_KERNEL); if (!cp->cpu_to_pri) goto cleanup; |
6e0534f27 sched: use a 2-d ... |
216 217 |
for_each_possible_cpu(i) cp->cpu_to_pri[i] = CPUPRI_INVALID; |
4dac0b638 sched/cpupri: Rep... |
218 |
|
68e74568f sched: convert st... |
219 220 221 222 223 224 |
return 0; cleanup: for (i--; i >= 0; i--) free_cpumask_var(cp->pri_to_cpu[i].mask); return -ENOMEM; |
6e0534f27 sched: use a 2-d ... |
225 |
} |
68e74568f sched: convert st... |
226 227 228 229 230 231 232 |
/** * cpupri_cleanup - clean up the cpupri structure * @cp: The cpupri context */ void cpupri_cleanup(struct cpupri *cp) { int i; |
6e0534f27 sched: use a 2-d ... |
233 |
|
4dac0b638 sched/cpupri: Rep... |
234 |
kfree(cp->cpu_to_pri); |
68e74568f sched: convert st... |
235 236 237 |
for (i = 0; i < CPUPRI_NR_PRIORITIES; i++) free_cpumask_var(cp->pri_to_cpu[i].mask); } |