xref: /titanic_41/usr/src/uts/common/disp/cmt_policy.c (revision 0e7515250c8395f368aa45fb9acae7c4f8f8b786)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 #include <sys/systm.h>
27 #include <sys/types.h>
28 #include <sys/param.h>
29 #include <sys/thread.h>
30 #include <sys/cpuvar.h>
31 #include <sys/cpupart.h>
32 #include <sys/cmn_err.h>
33 #include <sys/disp.h>
34 #include <sys/group.h>
35 #include <sys/bitset.h>
36 #include <sys/lgrp.h>
37 #include <sys/cmt.h>
38 
39 /*
40  * CMT dispatcher policies
41  *
42  * This file implements CMT dispatching policies using Processor Groups.
43  *
44  * The scheduler/dispatcher leverages knowledge of the performance
45  * relevant CMT sharing relationships existing between CPUs to implement
46  * load balancing, and coalescence thread placement policies.
47  *
48  * Load balancing policy seeks to improve performance by minimizing
49  * contention over shared processor resources / facilities. Coalescence
50  * policies improve resource utilization and ultimately power efficiency.
51  *
52  * On NUMA systems, the dispatcher will generally perform load balancing and
53  * coalescence within (and not across) lgroups. This is because there isn't
54  * much sense in trying to correct an imbalance by sending a thread outside
55  * of its home, if it would attempt to return home a short while later.
56  * The dispatcher will implement CMT policy across lgroups however, if
57  * it can do so with a thread homed to the root lgroup, since root homed
58  * threads have no lgroup affinity.
59  */
60 
61 /*
62  * Return non-zero if, given the policy, we should migrate from running
63  * somewhere "here" to somewhere "there".
64  */
65 static int
cmt_should_migrate(pg_cmt_t * here,pg_cmt_t * there,pg_cmt_policy_t policy,int self)66 cmt_should_migrate(pg_cmt_t *here, pg_cmt_t *there, pg_cmt_policy_t policy,
67     int self)
68 {
69 	uint32_t here_util, there_util;
70 
71 	here_util = here->cmt_utilization;
72 	there_util = there->cmt_utilization;
73 
74 	/*
75 	 * This assumes that curthread's utilization is "1"
76 	 */
77 	if (self && bitset_in_set(&here->cmt_cpus_actv_set, CPU->cpu_seqid))
78 		here_util--;	/* Ignore curthread's effect */
79 
80 	/*
81 	 * Load balancing and coalescence are conflicting policies
82 	 */
83 	ASSERT((policy & (CMT_BALANCE|CMT_COALESCE)) !=
84 	    (CMT_BALANCE|CMT_COALESCE));
85 
86 	if (policy & CMT_BALANCE) {
87 		/*
88 		 * Balance utilization
89 		 *
90 		 * If the target is comparatively underutilized
91 		 * (either in an absolute sense, or scaled by capacity),
92 		 * then choose to balance.
93 		 */
94 		if ((here_util > there_util) ||
95 		    (here_util == there_util &&
96 		    (CMT_CAPACITY(there) > CMT_CAPACITY(here)))) {
97 			return (1);
98 		}
99 	} else if (policy & CMT_COALESCE) {
100 		/*
101 		 * Attempt to drive group utilization up to capacity
102 		 */
103 		if (there_util > here_util &&
104 		    there_util < CMT_CAPACITY(there))
105 			return (1);
106 	}
107 	return (0);
108 }
109 
110 /*
111  * Perform multi-level CMT load balancing of running threads.
112  *
113  * tp is the thread being enqueued.
114  * cp is a hint CPU, against which CMT load balancing will be performed.
115  *
116  * Returns cp, or a CPU better than cp with respect to balancing
117  * running thread load.
118  */
119 cpu_t *
cmt_balance(kthread_t * tp,cpu_t * cp)120 cmt_balance(kthread_t *tp, cpu_t *cp)
121 {
122 	int		hint, i, cpu, nsiblings;
123 	int		self = 0;
124 	group_t		*cmt_pgs, *siblings;
125 	pg_cmt_t	*pg, *pg_tmp, *tpg = NULL;
126 	int		level = 0;
127 	cpu_t		*newcp;
128 	extern cmt_lgrp_t *cmt_root;
129 
130 	ASSERT(THREAD_LOCK_HELD(tp));
131 
132 	cmt_pgs = &cp->cpu_pg->cmt_pgs;
133 
134 	if (GROUP_SIZE(cmt_pgs) == 0)
135 		return (cp);	/* nothing to do */
136 
137 	if (tp == curthread)
138 		self = 1;
139 
140 	/*
141 	 * Balance across siblings in the CPUs CMT lineage
142 	 * If the thread is homed to the root lgroup, perform
143 	 * top level balancing against other top level PGs
144 	 * in the system. Otherwise, start with the default
145 	 * top level siblings group, which is within the leaf lgroup
146 	 */
147 	pg = GROUP_ACCESS(cmt_pgs, level);
148 	if (tp->t_lpl->lpl_lgrpid == LGRP_ROOTID)
149 		siblings = &cmt_root->cl_pgs;
150 	else
151 		siblings = pg->cmt_siblings;
152 
153 	/*
154 	 * Traverse down the lineage until we find a level that needs
155 	 * balancing, or we get to the end.
156 	 */
157 	for (;;) {
158 		nsiblings = GROUP_SIZE(siblings);	/* self inclusive */
159 		if (nsiblings == 1)
160 			goto next_level;
161 
162 		hint = CPU_PSEUDO_RANDOM() % nsiblings;
163 
164 		/*
165 		 * Find a balancing candidate from among our siblings
166 		 * "hint" is a hint for where to start looking
167 		 */
168 		i = hint;
169 		do {
170 			ASSERT(i < nsiblings);
171 			pg_tmp = GROUP_ACCESS(siblings, i);
172 
173 			/*
174 			 * The candidate must not be us, and must
175 			 * have some CPU resources in the thread's
176 			 * partition
177 			 */
178 			if (pg_tmp != pg &&
179 			    bitset_in_set(&tp->t_cpupart->cp_cmt_pgs,
180 			    ((pg_t *)pg_tmp)->pg_id)) {
181 				tpg = pg_tmp;
182 				break;
183 			}
184 
185 			if (++i >= nsiblings)
186 				i = 0;
187 		} while (i != hint);
188 
189 		if (!tpg)
190 			goto next_level; /* no candidates at this level */
191 
192 		/*
193 		 * Decide if we should migrate from the current PG to a
194 		 * target PG given a policy
195 		 */
196 		if (cmt_should_migrate(pg, tpg, pg->cmt_policy, self))
197 			break;
198 		tpg = NULL;
199 
200 next_level:
201 		if (++level == GROUP_SIZE(cmt_pgs))
202 			break;
203 
204 		pg = GROUP_ACCESS(cmt_pgs, level);
205 		siblings = pg->cmt_siblings;
206 	}
207 
208 	if (tpg) {
209 		uint_t	tgt_size = GROUP_SIZE(&tpg->cmt_cpus_actv);
210 
211 		/*
212 		 * Select an idle CPU from the target
213 		 */
214 		hint = CPU_PSEUDO_RANDOM() % tgt_size;
215 		cpu = hint;
216 		do {
217 			newcp = GROUP_ACCESS(&tpg->cmt_cpus_actv, cpu);
218 			if (newcp->cpu_part == tp->t_cpupart &&
219 			    newcp->cpu_dispatch_pri == -1) {
220 				cp = newcp;
221 				break;
222 			}
223 			if (++cpu == tgt_size)
224 				cpu = 0;
225 		} while (cpu != hint);
226 	}
227 
228 	return (cp);
229 }
230