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 * Since the CPU used/blocked calculation uses wide atomics, the data 188 * types used are different based on the platform. 189 */ 190 191 #if __LP64__ 192 193 #define CLUTCH_CPU_DATA_MAX (UINT64_MAX) 194 typedef uint64_t clutch_cpu_data_t; 195 typedef unsigned __int128 clutch_cpu_data_wide_t; 196 197 #else /* __LP64__ */ 198 199 #define CLUTCH_CPU_DATA_MAX (UINT32_MAX) 200 typedef uint32_t clutch_cpu_data_t; 201 typedef uint64_t clutch_cpu_data_wide_t; 202 203 #endif /* __LP64__ */ 204 205 typedef union sched_clutch_bucket_cpu_data { 206 struct { 207 /* Clutch bucket CPU used across all threads */ 208 clutch_cpu_data_t scbcd_cpu_used; 209 /* Clutch bucket voluntary blocked time */ 210 clutch_cpu_data_t scbcd_cpu_blocked; 211 } cpu_data; 212 clutch_cpu_data_wide_t scbcd_cpu_data_packed; 213 } sched_clutch_bucket_cpu_data_t; 214 215 /* 216 * struct sched_clutch_bucket 217 * 218 * A sched_clutch_bucket represents the set of threads for a thread 219 * group at a particular scheduling bucket in a specific cluster. 220 * It maintains information about the CPU usage & blocking behavior 221 * of all threads part of the clutch_bucket. It inherits the timeshare 222 * values from the clutch_bucket_group for decay and timesharing among 223 * threads in the clutch. 224 * 225 * Since the clutch bucket is a per thread group per-QoS entity it is 226 * important to keep its size small and the structure well aligned. 227 */ 228 struct sched_clutch_bucket { 229 #if CONFIG_SCHED_EDGE 230 /* (P) flag to indicate if the bucket is a foreign bucket */ 231 bool scb_foreign; 232 #endif /* CONFIG_SCHED_EDGE */ 233 /* (I) bucket for the clutch_bucket */ 234 uint8_t scb_bucket; 235 /* (P) priority of the clutch bucket */ 236 uint8_t scb_priority; 237 /* (P) number of threads in this clutch_bucket; should match runq.count */ 238 uint16_t scb_thr_count; 239 240 /* Pointer to the clutch bucket group this clutch bucket belongs to */ 241 struct sched_clutch_bucket_group *scb_group; 242 /* (A) pointer to the root of the hierarchy this bucket is in */ 243 struct sched_clutch_root *scb_root; 244 /* (P) priority queue of threads based on their promoted/base priority */ 245 struct priority_queue_sched_max scb_clutchpri_prioq; 246 /* (P) runq of threads in clutch_bucket */ 247 struct priority_queue_sched_stable_max scb_thread_runq; 248 249 /* (P) linkage for all clutch_buckets in a root bucket; used for tick operations */ 250 queue_chain_t scb_listlink; 251 /* (P) linkage for clutch_bucket in root_bucket runqueue */ 252 queue_chain_t scb_runqlink; 253 /* (P) queue of threads for timesharing purposes */ 254 queue_head_t scb_thread_timeshare_queue; 255 #if CONFIG_SCHED_EDGE 256 /* (P) linkage for all "foreign" clutch buckets in the root clutch */ 257 struct priority_queue_entry_sched scb_foreignlink; 258 #endif /* CONFIG_SCHED_EDGE */ 259 }; 260 typedef struct sched_clutch_bucket *sched_clutch_bucket_t; 261 262 /* 263 * sched_clutch_counter_time_t 264 * 265 * Holds thread counts and a timestamp (typically for a clutch bucket group). 266 * Used to allow atomic updates to these fields. 267 */ 268 typedef union sched_clutch_counter_time { 269 struct { 270 uint64_t scct_count; 271 uint64_t scct_timestamp; 272 }; 273 #if __LP64__ 274 unsigned __int128 scct_packed; 275 #endif /* __LP64__ */ 276 } __attribute__((aligned(16))) sched_clutch_counter_time_t; 277 278 /* 279 * struct sched_clutch_bucket_group 280 * 281 * It represents all the threads for a thread group at a particular 282 * QoS/Scheduling bucket. This structure also maintains the timesharing 283 * properties that are used for decay calculation for all threads in the 284 * thread group at the specific scheduling bucket. 285 */ 286 struct sched_clutch_bucket_group { 287 /* (I) bucket for the clutch_bucket_group */ 288 uint8_t scbg_bucket; 289 /* (A) sched tick when the clutch bucket group load/shifts were updated */ 290 uint32_t _Atomic scbg_timeshare_tick; 291 /* (A) priority shifts for threads in the clutch_bucket_group */ 292 uint32_t _Atomic scbg_pri_shift; 293 /* (A) preferred cluster ID for clutch bucket */ 294 uint32_t _Atomic scbg_preferred_cluster; 295 /* (A) cluster ID for AMP rebalancing */ 296 uint32_t scbg_amp_rebalance_last_chosen; 297 /* (I) clutch to which this clutch bucket_group belongs */ 298 struct sched_clutch *scbg_clutch; 299 #if !__LP64__ 300 /* Lock for synchronizing updates to blocked data (only on platforms without 128-atomics) */ 301 lck_spin_t scbg_stats_lock; 302 #endif /* !__LP64__ */ 303 /* (A/L depending on arch) holds blcked timestamp and runnable/running count */ 304 sched_clutch_counter_time_t scbg_blocked_data; 305 /* (P/A depending on scheduler) holds pending timestamp and thread count */ 306 sched_clutch_counter_time_t scbg_pending_data; 307 /* (P/A depending on scheduler) holds interactivity timestamp and score */ 308 sched_clutch_counter_time_t scbg_interactivity_data; 309 /* (A) CPU usage information for the clutch bucket group */ 310 sched_clutch_bucket_cpu_data_t scbg_cpu_data; 311 /* Storage for all clutch buckets for a thread group at scbg_bucket */ 312 struct sched_clutch_bucket *scbg_clutch_buckets; 313 }; 314 typedef struct sched_clutch_bucket_group *sched_clutch_bucket_group_t; 315 316 317 /* 318 * struct sched_clutch 319 * 320 * A sched_clutch is a 1:1 mapping to a thread group. It maintains the 321 * storage for all clutch buckets for this thread group and some properties 322 * of the thread group (such as flags etc.) 323 */ 324 struct sched_clutch { 325 /* 326 * (A) number of runnable threads in sched_clutch; needs to be atomic 327 * to support cross cluster sched_clutch migrations. 328 */ 329 uint16_t _Atomic sc_thr_count; 330 /* 331 * Grouping specific parameters. Currently the implementation only 332 * supports thread_group based grouping. 333 */ 334 union { 335 /* (I) Pointer to thread group */ 336 struct thread_group *sc_tg; 337 }; 338 /* (I) storage for all clutch_buckets for this clutch */ 339 struct sched_clutch_bucket_group sc_clutch_groups[TH_BUCKET_SCHED_MAX]; 340 }; 341 typedef struct sched_clutch *sched_clutch_t; 342 343 344 /* Clutch lifecycle management */ 345 void sched_clutch_init_with_thread_group(sched_clutch_t, struct thread_group *); 346 void sched_clutch_destroy(sched_clutch_t); 347 348 /* Clutch thread membership management */ 349 void sched_clutch_thread_clutch_update(thread_t, sched_clutch_t, sched_clutch_t); 350 uint32_t sched_edge_thread_preferred_cluster(thread_t); 351 352 /* Clutch timesharing stats management */ 353 uint32_t sched_clutch_thread_run_bucket_incr(thread_t, sched_bucket_t); 354 uint32_t sched_clutch_thread_run_bucket_decr(thread_t, sched_bucket_t); 355 void sched_clutch_cpu_usage_update(thread_t, uint64_t); 356 uint32_t sched_clutch_thread_pri_shift(thread_t, sched_bucket_t); 357 358 /* Clutch properties accessors */ 359 uint32_t sched_clutch_root_count(sched_clutch_root_t); 360 361 /* Grouping specific external routines */ 362 extern sched_clutch_t sched_clutch_for_thread(thread_t); 363 extern sched_clutch_t sched_clutch_for_thread_group(struct thread_group *); 364 365 #if CONFIG_SCHED_EDGE 366 367 /* 368 * Getter and Setter for Edge configuration. Used by CLPC to affect thread migration behavior. 369 */ 370 void sched_edge_matrix_get(sched_clutch_edge *edge_matrix, bool *edge_request_bitmap, uint64_t flags, uint64_t matrix_order); 371 void sched_edge_matrix_set(sched_clutch_edge *edge_matrix, bool *edge_changes_bitmap, uint64_t flags, uint64_t matrix_order); 372 void sched_edge_tg_preferred_cluster_change(struct thread_group *tg, uint32_t *tg_bucket_preferred_cluster, sched_perfcontrol_preferred_cluster_options_t options); 373 374 uint16_t sched_edge_cluster_cumulative_count(sched_clutch_root_t root_clutch, sched_bucket_t bucket); 375 uint16_t sched_edge_shared_rsrc_runnable_load(sched_clutch_root_t root_clutch, cluster_shared_rsrc_type_t load_type); 376 377 #endif /* CONFIG_SCHED_EDGE */ 378 379 #endif /* CONFIG_SCHED_CLUTCH */ 380 381 #endif /* _KERN_SCHED_CLUTCH_H_ */ 382