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