Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 1 | /* |
| 2 | * kernel/sched_cpupri.c |
| 3 | * |
| 4 | * CPU priority management |
| 5 | * |
| 6 | * Copyright (C) 2007-2008 Novell |
| 7 | * |
| 8 | * Author: Gregory Haskins <ghaskins@novell.com> |
| 9 | * |
| 10 | * This code tracks the priority of each CPU so that global migration |
| 11 | * decisions are easy to calculate. Each CPU can be in a state as follows: |
| 12 | * |
| 13 | * (INVALID), IDLE, NORMAL, RT1, ... RT99 |
| 14 | * |
| 15 | * going from the lowest priority to the highest. CPUs in the INVALID state |
| 16 | * are not eligible for routing. The system maintains this state with |
| 17 | * a 2 dimensional bitmap (the first for priority class, the second for cpus |
| 18 | * in that class). Therefore a typical application without affinity |
| 19 | * restrictions can find a suitable CPU with O(1) complexity (e.g. two bit |
| 20 | * searches). For tasks with affinity restrictions, the algorithm has a |
| 21 | * worst case complexity of O(min(102, nr_domcpus)), though the scenario that |
| 22 | * yields the worst case search is fairly contrived. |
| 23 | * |
| 24 | * This program is free software; you can redistribute it and/or |
| 25 | * modify it under the terms of the GNU General Public License |
| 26 | * as published by the Free Software Foundation; version 2 |
| 27 | * of the License. |
| 28 | */ |
| 29 | |
Tejun Heo | 5a0e3ad | 2010-03-24 17:04:11 +0900 | [diff] [blame] | 30 | #include <linux/gfp.h> |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 31 | #include "sched_cpupri.h" |
| 32 | |
| 33 | /* Convert between a 140 based task->prio, and our 102 based cpupri */ |
| 34 | static int convert_prio(int prio) |
| 35 | { |
| 36 | int cpupri; |
| 37 | |
| 38 | if (prio == CPUPRI_INVALID) |
| 39 | cpupri = CPUPRI_INVALID; |
| 40 | else if (prio == MAX_PRIO) |
| 41 | cpupri = CPUPRI_IDLE; |
| 42 | else if (prio >= MAX_RT_PRIO) |
| 43 | cpupri = CPUPRI_NORMAL; |
| 44 | else |
| 45 | cpupri = MAX_RT_PRIO - prio + 1; |
| 46 | |
| 47 | return cpupri; |
| 48 | } |
| 49 | |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 50 | /** |
| 51 | * cpupri_find - find the best (lowest-pri) CPU in the system |
| 52 | * @cp: The cpupri context |
| 53 | * @p: The task |
Rusty Russell | 13b8bd0 | 2009-03-25 15:01:22 +1030 | [diff] [blame] | 54 | * @lowest_mask: A mask to fill in with selected CPUs (or NULL) |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 55 | * |
| 56 | * Note: This function returns the recommended CPUs as calculated during the |
Adam Buchbinder | 2a61aa4 | 2009-12-11 16:35:40 -0500 | [diff] [blame] | 57 | * current invocation. By the time the call returns, the CPUs may have in |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 58 | * fact changed priorities any number of times. While not ideal, it is not |
| 59 | * an issue of correctness since the normal rebalancer logic will correct |
| 60 | * any discrepancies created by racing against the uncertainty of the current |
| 61 | * priority configuration. |
| 62 | * |
| 63 | * Returns: (int)bool - CPUs were found |
| 64 | */ |
| 65 | int cpupri_find(struct cpupri *cp, struct task_struct *p, |
Rusty Russell | 68e7456 | 2008-11-25 02:35:13 +1030 | [diff] [blame] | 66 | struct cpumask *lowest_mask) |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 67 | { |
| 68 | int idx = 0; |
| 69 | int task_pri = convert_prio(p->prio); |
| 70 | |
Steven Rostedt | c92211d | 2011-08-02 16:36:12 -0400 | [diff] [blame^] | 71 | if (task_pri >= MAX_RT_PRIO) |
| 72 | return 0; |
| 73 | |
| 74 | for (idx = 0; idx < task_pri; idx++) { |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 75 | struct cpupri_vec *vec = &cp->pri_to_cpu[idx]; |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 76 | |
Steven Rostedt | c92211d | 2011-08-02 16:36:12 -0400 | [diff] [blame^] | 77 | if (!atomic_read(&(vec)->count)) |
| 78 | continue; |
| 79 | /* |
| 80 | * When looking at the vector, we need to read the counter, |
| 81 | * do a memory barrier, then read the mask. |
| 82 | * |
| 83 | * Note: This is still all racey, but we can deal with it. |
| 84 | * Ideally, we only want to look at masks that are set. |
| 85 | * |
| 86 | * If a mask is not set, then the only thing wrong is that we |
| 87 | * did a little more work than necessary. |
| 88 | * |
| 89 | * If we read a zero count but the mask is set, because of the |
| 90 | * memory barriers, that can only happen when the highest prio |
| 91 | * task for a run queue has left the run queue, in which case, |
| 92 | * it will be followed by a pull. If the task we are processing |
| 93 | * fails to find a proper place to go, that pull request will |
| 94 | * pull this task if the run queue is running at a lower |
| 95 | * priority. |
| 96 | */ |
| 97 | smp_rmb(); |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 98 | |
Rusty Russell | 68e7456 | 2008-11-25 02:35:13 +1030 | [diff] [blame] | 99 | if (cpumask_any_and(&p->cpus_allowed, vec->mask) >= nr_cpu_ids) |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 100 | continue; |
| 101 | |
Gregory Haskins | 07903af | 2009-07-30 10:57:28 -0400 | [diff] [blame] | 102 | if (lowest_mask) { |
Rusty Russell | 13b8bd0 | 2009-03-25 15:01:22 +1030 | [diff] [blame] | 103 | cpumask_and(lowest_mask, &p->cpus_allowed, vec->mask); |
Gregory Haskins | 07903af | 2009-07-30 10:57:28 -0400 | [diff] [blame] | 104 | |
| 105 | /* |
| 106 | * We have to ensure that we have at least one bit |
| 107 | * still set in the array, since the map could have |
| 108 | * been concurrently emptied between the first and |
| 109 | * second reads of vec->mask. If we hit this |
| 110 | * condition, simply act as though we never hit this |
| 111 | * priority level and continue on. |
| 112 | */ |
| 113 | if (cpumask_any(lowest_mask) >= nr_cpu_ids) |
| 114 | continue; |
| 115 | } |
| 116 | |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 117 | return 1; |
| 118 | } |
| 119 | |
| 120 | return 0; |
| 121 | } |
| 122 | |
| 123 | /** |
| 124 | * cpupri_set - update the cpu priority setting |
| 125 | * @cp: The cpupri context |
| 126 | * @cpu: The target cpu |
| 127 | * @pri: The priority (INVALID-RT99) to assign to this CPU |
| 128 | * |
| 129 | * Note: Assumes cpu_rq(cpu)->lock is locked |
| 130 | * |
| 131 | * Returns: (void) |
| 132 | */ |
| 133 | void cpupri_set(struct cpupri *cp, int cpu, int newpri) |
| 134 | { |
| 135 | int *currpri = &cp->cpu_to_pri[cpu]; |
| 136 | int oldpri = *currpri; |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 137 | |
| 138 | newpri = convert_prio(newpri); |
| 139 | |
| 140 | BUG_ON(newpri >= CPUPRI_NR_PRIORITIES); |
| 141 | |
| 142 | if (newpri == oldpri) |
| 143 | return; |
| 144 | |
| 145 | /* |
| 146 | * If the cpu was currently mapped to a different value, we |
Steven Rostedt | c3a2ae3 | 2009-07-29 00:21:23 -0400 | [diff] [blame] | 147 | * need to map it to the new value then remove the old value. |
| 148 | * Note, we must add the new value first, otherwise we risk the |
| 149 | * cpu being cleared from pri_active, and this cpu could be |
| 150 | * missed for a push or pull. |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 151 | */ |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 152 | if (likely(newpri != CPUPRI_INVALID)) { |
| 153 | struct cpupri_vec *vec = &cp->pri_to_cpu[newpri]; |
| 154 | |
Rusty Russell | 68e7456 | 2008-11-25 02:35:13 +1030 | [diff] [blame] | 155 | cpumask_set_cpu(cpu, vec->mask); |
Steven Rostedt | c92211d | 2011-08-02 16:36:12 -0400 | [diff] [blame^] | 156 | /* |
| 157 | * When adding a new vector, we update the mask first, |
| 158 | * do a write memory barrier, and then update the count, to |
| 159 | * make sure the vector is visible when count is set. |
| 160 | */ |
| 161 | smp_wmb(); |
| 162 | atomic_inc(&(vec)->count); |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 163 | } |
Steven Rostedt | c3a2ae3 | 2009-07-29 00:21:23 -0400 | [diff] [blame] | 164 | if (likely(oldpri != CPUPRI_INVALID)) { |
| 165 | struct cpupri_vec *vec = &cp->pri_to_cpu[oldpri]; |
| 166 | |
Steven Rostedt | c92211d | 2011-08-02 16:36:12 -0400 | [diff] [blame^] | 167 | /* |
| 168 | * When removing from the vector, we decrement the counter first |
| 169 | * do a memory barrier and then clear the mask. |
| 170 | */ |
| 171 | atomic_dec(&(vec)->count); |
| 172 | smp_wmb(); |
Steven Rostedt | c3a2ae3 | 2009-07-29 00:21:23 -0400 | [diff] [blame] | 173 | cpumask_clear_cpu(cpu, vec->mask); |
Steven Rostedt | c3a2ae3 | 2009-07-29 00:21:23 -0400 | [diff] [blame] | 174 | } |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 175 | |
| 176 | *currpri = newpri; |
| 177 | } |
| 178 | |
| 179 | /** |
| 180 | * cpupri_init - initialize the cpupri structure |
| 181 | * @cp: The cpupri context |
Rusty Russell | 68e7456 | 2008-11-25 02:35:13 +1030 | [diff] [blame] | 182 | * @bootmem: true if allocations need to use bootmem |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 183 | * |
Rusty Russell | 68e7456 | 2008-11-25 02:35:13 +1030 | [diff] [blame] | 184 | * Returns: -ENOMEM if memory fails. |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 185 | */ |
Pekka Enberg | 68c38fc | 2010-07-15 23:18:22 +0300 | [diff] [blame] | 186 | int cpupri_init(struct cpupri *cp) |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 187 | { |
| 188 | int i; |
| 189 | |
| 190 | memset(cp, 0, sizeof(*cp)); |
| 191 | |
| 192 | for (i = 0; i < CPUPRI_NR_PRIORITIES; i++) { |
| 193 | struct cpupri_vec *vec = &cp->pri_to_cpu[i]; |
| 194 | |
Steven Rostedt | c92211d | 2011-08-02 16:36:12 -0400 | [diff] [blame^] | 195 | atomic_set(&vec->count, 0); |
Pekka Enberg | 68c38fc | 2010-07-15 23:18:22 +0300 | [diff] [blame] | 196 | if (!zalloc_cpumask_var(&vec->mask, GFP_KERNEL)) |
Rusty Russell | 68e7456 | 2008-11-25 02:35:13 +1030 | [diff] [blame] | 197 | goto cleanup; |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 198 | } |
| 199 | |
| 200 | for_each_possible_cpu(i) |
| 201 | cp->cpu_to_pri[i] = CPUPRI_INVALID; |
Rusty Russell | 68e7456 | 2008-11-25 02:35:13 +1030 | [diff] [blame] | 202 | return 0; |
| 203 | |
| 204 | cleanup: |
| 205 | for (i--; i >= 0; i--) |
| 206 | free_cpumask_var(cp->pri_to_cpu[i].mask); |
| 207 | return -ENOMEM; |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 208 | } |
| 209 | |
Rusty Russell | 68e7456 | 2008-11-25 02:35:13 +1030 | [diff] [blame] | 210 | /** |
| 211 | * cpupri_cleanup - clean up the cpupri structure |
| 212 | * @cp: The cpupri context |
| 213 | */ |
| 214 | void cpupri_cleanup(struct cpupri *cp) |
| 215 | { |
| 216 | int i; |
Gregory Haskins | 6e0534f | 2008-05-12 21:21:01 +0200 | [diff] [blame] | 217 | |
Rusty Russell | 68e7456 | 2008-11-25 02:35:13 +1030 | [diff] [blame] | 218 | for (i = 0; i < CPUPRI_NR_PRIORITIES; i++) |
| 219 | free_cpumask_var(cp->pri_to_cpu[i].mask); |
| 220 | } |