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