1 | /* |
2 | * Copyright (c) 2018 Apple Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | |
29 | #ifndef _KERN_SCHED_CLUTCH_H_ |
30 | #define _KERN_SCHED_CLUTCH_H_ |
31 | |
32 | #include <kern/sched.h> |
33 | #include <machine/atomic.h> |
34 | #include <kern/priority_queue.h> |
35 | #include <kern/thread_group.h> |
36 | #include <kern/bits.h> |
37 | |
38 | #if CONFIG_SCHED_CLUTCH |
39 | |
40 | /* |
41 | * For the current implementation, bound threads are not managed |
42 | * in the clutch hierarchy. This helper macro is used to indicate |
43 | * if the thread should be in the hierarchy. |
44 | */ |
45 | #define SCHED_CLUTCH_THREAD_ELIGIBLE(thread) ((thread->bound_processor) == PROCESSOR_NULL) |
46 | |
47 | #if CONFIG_SCHED_EDGE |
48 | #define SCHED_CLUTCH_THREAD_CLUSTER_BOUND(thread) (thread->th_bound_cluster_id != THREAD_BOUND_CLUSTER_NONE) |
49 | #define SCHED_CLUTCH_THREAD_CLUSTER_BOUND_SOFT(thread) ((thread->sched_flags & TH_SFLAG_BOUND_SOFT) != 0) |
50 | |
51 | #else /* CONFIG_SCHED_EDGE */ |
52 | #define SCHED_CLUTCH_THREAD_CLUSTER_BOUND(thread) (0) |
53 | #define SCHED_CLUTCH_THREAD_CLUSTER_BOUND_SOFT(thread) (0) |
54 | #endif /* CONFIG_SCHED_EDGE */ |
55 | |
56 | /* |
57 | * Clutch Bucket Runqueue Structure. |
58 | */ |
59 | struct sched_clutch_bucket_runq { |
60 | int scbrq_highq; |
61 | int scbrq_count; |
62 | bitmap_t scbrq_bitmap[BITMAP_LEN(NRQS_MAX)]; |
63 | circle_queue_head_t scbrq_queues[NRQS_MAX]; |
64 | }; |
65 | typedef struct sched_clutch_bucket_runq *sched_clutch_bucket_runq_t; |
66 | |
67 | /* |
68 | * |
69 | * Clutch hierarchy locking protocol |
70 | * |
71 | * The scheduler clutch hierarchy is protected by a combination of |
72 | * atomics and pset lock. |
73 | * - All fields protected by the pset lock are annotated with (P) |
74 | * - All fields updated using atomics are annotated with (A) |
75 | * - All fields that are unprotected and are not updated after |
76 | * initialization are annotated with (I) |
77 | */ |
78 | |
79 | /* |
80 | * struct sched_clutch_root_bucket |
81 | * |
82 | * A clutch_root_bucket represents all threads across all thread groups |
83 | * that are in the same scheduler bucket (FG/IN/...). The clutch_root_bucket |
84 | * is selected for execution by the root level bucket selection algorithm |
85 | * which bases the decision on the clutch_root_bucket's deadline (EDF). The |
86 | * deadline for a root bucket is calculated based on its runnable timestamp |
87 | * and the worst-case-execution-latency values specied in sched_clutch_root_bucket_wcel[] |
88 | */ |
89 | struct sched_clutch_root_bucket { |
90 | /* (I) sched bucket represented by this root bucket */ |
91 | uint8_t scrb_bucket; |
92 | /* (I) Indicates the root bucket represents cluster bound threads */ |
93 | bool scrb_bound; |
94 | /* (P) Indicates if the root bucket is in starvation avoidance mode */ |
95 | bool scrb_starvation_avoidance; |
96 | |
97 | union { |
98 | /* (P) priority queue for all unbound clutch buckets in this sched bucket */ |
99 | struct sched_clutch_bucket_runq scrb_clutch_buckets; |
100 | /* (P) Runqueue for all bound threads part of this root bucket */ |
101 | struct run_queue scrb_bound_thread_runq; |
102 | }; |
103 | /* (P) priority queue entry to use for enqueueing root bucket into root prioq */ |
104 | struct priority_queue_entry_deadline scrb_pqlink; |
105 | /* (P) warped deadline for root bucket */ |
106 | uint64_t scrb_warped_deadline; |
107 | /* (P) warp remaining for root bucket */ |
108 | uint64_t scrb_warp_remaining; |
109 | /* (P) timestamp for the start of the starvation avoidance window */ |
110 | uint64_t scrb_starvation_ts; |
111 | }; |
112 | typedef struct sched_clutch_root_bucket *sched_clutch_root_bucket_t; |
113 | |
114 | /* |
115 | * struct sched_clutch_root |
116 | * |
117 | * A clutch_root represents the root of the hierarchy. It maintains a |
118 | * priority queue of all runnable root buckets. The clutch_root also |
119 | * maintains the information about the last clutch_root_bucket scheduled |
120 | * in order to implement bucket level quantum. The bucket level quantums |
121 | * allow low priority buckets to get a "fair" chance of using the CPU even |
122 | * if they contain a bunch of short executing threads. The bucket quantums |
123 | * are configured using sched_clutch_root_bucket_quantum[] |
124 | */ |
125 | struct sched_clutch_root { |
126 | /* (P) root level priority; represents the highest runnable thread in the hierarchy */ |
127 | int16_t scr_priority; |
128 | /* (P) total number of runnable threads in the hierarchy */ |
129 | uint16_t scr_thr_count; |
130 | /* (P) root level urgency; represents the urgency of the whole hierarchy for pre-emption purposes */ |
131 | int16_t scr_urgency; |
132 | /* (P) runnable shared resource load enqueued in this cluster/root hierarchy */ |
133 | uint16_t scr_shared_rsrc_load_runnable[CLUSTER_SHARED_RSRC_TYPE_COUNT]; |
134 | |
135 | uint32_t scr_cluster_id; |
136 | /* (I) processor set this hierarchy belongs to */ |
137 | processor_set_t scr_pset; |
138 | /* |
139 | * (P) list of all runnable clutch buckets across the system; |
140 | * allows easy iteration in the sched tick based timesharing code |
141 | */ |
142 | queue_head_t scr_clutch_buckets; |
143 | |
144 | /* |
145 | * (P) priority queue of all runnable foreign buckets in this hierarchy; |
146 | * used for tracking thread groups which need to be migrated when |
147 | * psets are available or rebalancing threads on CPU idle. |
148 | */ |
149 | struct priority_queue_sched_max scr_foreign_buckets; |
150 | |
151 | /* Root level bucket management */ |
152 | |
153 | /* (P) bitmap of all runnable unbounded root buckets */ |
154 | bitmap_t scr_unbound_runnable_bitmap[BITMAP_LEN(TH_BUCKET_SCHED_MAX)]; |
155 | /* (P) bitmap of all runnable unbounded root buckets which have warps remaining */ |
156 | bitmap_t scr_unbound_warp_available[BITMAP_LEN(TH_BUCKET_SCHED_MAX)]; |
157 | /* (P) bitmap of all runnable bounded root buckets */ |
158 | bitmap_t scr_bound_runnable_bitmap[BITMAP_LEN(TH_BUCKET_SCHED_MAX)]; |
159 | /* (P) bitmap of all runnable bounded root buckets which have warps remaining */ |
160 | bitmap_t scr_bound_warp_available[BITMAP_LEN(TH_BUCKET_SCHED_MAX)]; |
161 | |
162 | /* (P) priority queue of all runnable unbounded root buckets in deadline order */ |
163 | struct priority_queue_deadline_min scr_unbound_root_buckets; |
164 | /* (P) priority queue of all bounded root buckets in deadline order */ |
165 | struct priority_queue_deadline_min scr_bound_root_buckets; |
166 | |
167 | /* (P) cumulative run counts at each bucket for load average calculation */ |
168 | uint16_t _Atomic scr_cumulative_run_count[TH_BUCKET_SCHED_MAX]; |
169 | |
170 | /* (P) storage for all unbound clutch_root_buckets */ |
171 | struct sched_clutch_root_bucket scr_unbound_buckets[TH_BUCKET_SCHED_MAX]; |
172 | /* (P) storage for all bound clutch_root_buckets */ |
173 | struct sched_clutch_root_bucket scr_bound_buckets[TH_BUCKET_SCHED_MAX]; |
174 | }; |
175 | typedef struct sched_clutch_root *sched_clutch_root_t; |
176 | |
177 | /* forward declaration for sched_clutch */ |
178 | struct sched_clutch; |
179 | |
180 | /* |
181 | * sched_clutch_bucket_cpu_data_t |
182 | * |
183 | * Used for maintaining clutch bucket used and blocked time. The |
184 | * values are used for calculating the interactivity score for the |
185 | * clutch bucket. |
186 | */ |
187 | #define CLUTCH_CPU_DATA_MAX (UINT64_MAX) |
188 | typedef uint64_t clutch_cpu_data_t; |
189 | typedef unsigned __int128 clutch_cpu_data_wide_t; |
190 | |
191 | typedef union sched_clutch_bucket_cpu_data { |
192 | struct { |
193 | /* Clutch bucket CPU used across all threads */ |
194 | clutch_cpu_data_t scbcd_cpu_used; |
195 | /* Clutch bucket voluntary blocked time */ |
196 | clutch_cpu_data_t scbcd_cpu_blocked; |
197 | } cpu_data; |
198 | clutch_cpu_data_wide_t scbcd_cpu_data_packed; |
199 | } sched_clutch_bucket_cpu_data_t; |
200 | |
201 | /* |
202 | * struct sched_clutch_bucket |
203 | * |
204 | * A sched_clutch_bucket represents the set of threads for a thread |
205 | * group at a particular scheduling bucket in a specific cluster. |
206 | * It maintains information about the CPU usage & blocking behavior |
207 | * of all threads part of the clutch_bucket. It inherits the timeshare |
208 | * values from the clutch_bucket_group for decay and timesharing among |
209 | * threads in the clutch. |
210 | * |
211 | * Since the clutch bucket is a per thread group per-QoS entity it is |
212 | * important to keep its size small and the structure well aligned. |
213 | */ |
214 | struct sched_clutch_bucket { |
215 | #if CONFIG_SCHED_EDGE |
216 | /* (P) flag to indicate if the bucket is a foreign bucket */ |
217 | bool scb_foreign; |
218 | #endif /* CONFIG_SCHED_EDGE */ |
219 | /* (I) bucket for the clutch_bucket */ |
220 | uint8_t scb_bucket; |
221 | /* (P) priority of the clutch bucket */ |
222 | uint8_t scb_priority; |
223 | /* (P) number of threads in this clutch_bucket; should match runq.count */ |
224 | uint16_t scb_thr_count; |
225 | |
226 | /* Pointer to the clutch bucket group this clutch bucket belongs to */ |
227 | struct sched_clutch_bucket_group *scb_group; |
228 | /* (A) pointer to the root of the hierarchy this bucket is in */ |
229 | struct sched_clutch_root *scb_root; |
230 | /* (P) priority queue of threads based on their promoted/base priority */ |
231 | struct priority_queue_sched_max scb_clutchpri_prioq; |
232 | /* (P) runq of threads in clutch_bucket */ |
233 | struct priority_queue_sched_stable_max scb_thread_runq; |
234 | |
235 | /* (P) linkage for all clutch_buckets in a root bucket; used for tick operations */ |
236 | queue_chain_t scb_listlink; |
237 | /* (P) linkage for clutch_bucket in root_bucket runqueue */ |
238 | queue_chain_t scb_runqlink; |
239 | /* (P) queue of threads for timesharing purposes */ |
240 | queue_head_t scb_thread_timeshare_queue; |
241 | #if CONFIG_SCHED_EDGE |
242 | /* (P) linkage for all "foreign" clutch buckets in the root clutch */ |
243 | struct priority_queue_entry_sched scb_foreignlink; |
244 | #endif /* CONFIG_SCHED_EDGE */ |
245 | }; |
246 | typedef struct sched_clutch_bucket *sched_clutch_bucket_t; |
247 | |
248 | /* |
249 | * sched_clutch_counter_time_t |
250 | * |
251 | * Holds thread counts and a timestamp (typically for a clutch bucket group). |
252 | * Used to allow atomic updates to these fields. |
253 | */ |
254 | typedef union sched_clutch_counter_time { |
255 | struct { |
256 | uint64_t scct_count; |
257 | uint64_t scct_timestamp; |
258 | }; |
259 | unsigned __int128 scct_packed; |
260 | } __attribute__((aligned(16))) sched_clutch_counter_time_t; |
261 | |
262 | /* |
263 | * struct sched_clutch_bucket_group |
264 | * |
265 | * It represents all the threads for a thread group at a particular |
266 | * QoS/Scheduling bucket. This structure also maintains the timesharing |
267 | * properties that are used for decay calculation for all threads in the |
268 | * thread group at the specific scheduling bucket. |
269 | */ |
270 | struct sched_clutch_bucket_group { |
271 | /* (I) bucket for the clutch_bucket_group */ |
272 | uint8_t scbg_bucket; |
273 | /* (A) sched tick when the clutch bucket group load/shifts were updated */ |
274 | uint32_t _Atomic scbg_timeshare_tick; |
275 | /* (A) priority shifts for threads in the clutch_bucket_group */ |
276 | uint32_t _Atomic scbg_pri_shift; |
277 | /* (A) preferred cluster ID for clutch bucket */ |
278 | uint32_t _Atomic scbg_preferred_cluster; |
279 | /* (A) cluster ID for AMP rebalancing */ |
280 | uint32_t scbg_amp_rebalance_last_chosen; |
281 | /* (I) clutch to which this clutch bucket_group belongs */ |
282 | struct sched_clutch *scbg_clutch; |
283 | /* (A) holds blocked timestamp and runnable/running count */ |
284 | sched_clutch_counter_time_t scbg_blocked_data; |
285 | /* (P/A depending on scheduler) holds pending timestamp and thread count */ |
286 | sched_clutch_counter_time_t scbg_pending_data; |
287 | /* (P/A depending on scheduler) holds interactivity timestamp and score */ |
288 | sched_clutch_counter_time_t scbg_interactivity_data; |
289 | /* (A) CPU usage information for the clutch bucket group */ |
290 | sched_clutch_bucket_cpu_data_t scbg_cpu_data; |
291 | /* Storage for all clutch buckets for a thread group at scbg_bucket */ |
292 | struct sched_clutch_bucket *scbg_clutch_buckets; |
293 | }; |
294 | typedef struct sched_clutch_bucket_group *sched_clutch_bucket_group_t; |
295 | |
296 | |
297 | /* |
298 | * struct sched_clutch |
299 | * |
300 | * A sched_clutch is a 1:1 mapping to a thread group. It maintains the |
301 | * storage for all clutch buckets for this thread group and some properties |
302 | * of the thread group (such as flags etc.) |
303 | */ |
304 | struct sched_clutch { |
305 | /* |
306 | * (A) number of runnable threads in sched_clutch; needs to be atomic |
307 | * to support cross cluster sched_clutch migrations. |
308 | */ |
309 | uint16_t _Atomic sc_thr_count; |
310 | /* |
311 | * Grouping specific parameters. Currently the implementation only |
312 | * supports thread_group based grouping. |
313 | */ |
314 | union { |
315 | /* (I) Pointer to thread group */ |
316 | struct thread_group *sc_tg; |
317 | }; |
318 | /* (I) storage for all clutch_buckets for this clutch */ |
319 | struct sched_clutch_bucket_group sc_clutch_groups[TH_BUCKET_SCHED_MAX]; |
320 | }; |
321 | typedef struct sched_clutch *sched_clutch_t; |
322 | |
323 | |
324 | /* Clutch lifecycle management */ |
325 | void sched_clutch_init_with_thread_group(sched_clutch_t, struct thread_group *); |
326 | void sched_clutch_destroy(sched_clutch_t); |
327 | |
328 | /* Clutch thread membership management */ |
329 | void sched_clutch_thread_clutch_update(thread_t, sched_clutch_t, sched_clutch_t); |
330 | uint32_t sched_edge_thread_preferred_cluster(thread_t); |
331 | |
332 | /* Clutch timesharing stats management */ |
333 | uint32_t sched_clutch_thread_run_bucket_incr(thread_t, sched_bucket_t); |
334 | uint32_t sched_clutch_thread_run_bucket_decr(thread_t, sched_bucket_t); |
335 | void sched_clutch_cpu_usage_update(thread_t, uint64_t); |
336 | uint32_t sched_clutch_thread_pri_shift(thread_t, sched_bucket_t); |
337 | |
338 | /* Clutch properties accessors */ |
339 | uint32_t sched_clutch_root_count(sched_clutch_root_t); |
340 | |
341 | /* Grouping specific external routines */ |
342 | extern sched_clutch_t sched_clutch_for_thread(thread_t); |
343 | extern sched_clutch_t sched_clutch_for_thread_group(struct thread_group *); |
344 | |
345 | #if CONFIG_SCHED_EDGE |
346 | |
347 | /* |
348 | * Getter and Setter for Edge configuration. Used by CLPC to affect thread migration behavior. |
349 | */ |
350 | void sched_edge_matrix_get(sched_clutch_edge *edge_matrix, bool *edge_request_bitmap, uint64_t flags, uint64_t matrix_order); |
351 | void sched_edge_matrix_set(sched_clutch_edge *edge_matrix, bool *edge_changes_bitmap, uint64_t flags, uint64_t matrix_order); |
352 | void sched_edge_tg_preferred_cluster_change(struct thread_group *tg, uint32_t *tg_bucket_preferred_cluster, sched_perfcontrol_preferred_cluster_options_t options); |
353 | |
354 | uint16_t sched_edge_cluster_cumulative_count(sched_clutch_root_t root_clutch, sched_bucket_t bucket); |
355 | uint16_t sched_edge_shared_rsrc_runnable_load(sched_clutch_root_t root_clutch, cluster_shared_rsrc_type_t load_type); |
356 | |
357 | #endif /* CONFIG_SCHED_EDGE */ |
358 | |
359 | #endif /* CONFIG_SCHED_CLUTCH */ |
360 | |
361 | #endif /* _KERN_SCHED_CLUTCH_H_ */ |
362 | |