osfmk/kern/sched_clutch.h

   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  * Clutch ordering based on thread group flags (specified
  42  * by the thread grouping mechanism). These properties
  43  * define a thread group specific priority boost.
  44  *
  45  * The current implementation gives a slight boost to
  46  * HIGH & MED thread groups which effectively deprioritizes
  47  * daemon thread groups which are marked "Efficient" on AMP
  48  * systems.
  49  */
  50 #define SCHED_CLUTCH_TG_PRI_LOW           0x0
  51 #define SCHED_CLUTCH_TG_PRI_MED           0x1
  52 #define SCHED_CLUTCH_TG_PRI_HIGH          0x2
  53
  54 /*
  55  * For the current implementation, bound threads are not managed
  56  * in the clutch hierarchy. This helper macro is used to indicate
  57  * if the thread should be in the hierarchy.
  58  */
  59 #define SCHED_CLUTCH_THREAD_ELIGIBLE(thread)    ((thread->bound_processor) == PROCESSOR_NULL)
  60
  61 /*
  62  *
  63  * Clutch hierarchy locking protocol
  64  *
  65  * The scheduler clutch hierarchy is protected by a combination of
  66  * atomics and pset lock.
  67  * - All fields protected by the pset lock are annotated with (P)
  68  * - All fields updated using atomics are annotated with (A)
  69  * - All fields that are unprotected and are not updated after
  70  *   initialization are annotated with (I)
  71  */
  72
  73 /*
  74  * struct sched_clutch_root_bucket
  75  *
  76  * A clutch_root_bucket represents all threads across all thread groups
  77  * that are in the same scheduler bucket (FG/IN/...). The clutch_root_bucket
  78  * is selected for execution by the root level bucket selection algorithm
  79  * which bases the decision on the clutch_root_bucket's deadline (EDF). The
  80  * deadline for a root bucket is calculated based on its runnable timestamp
  81  * and the worst-case-execution-latency values specied in sched_clutch_root_bucket_wcel[]
  82  */
  83 struct sched_clutch_root_bucket {
  84         /* (I) sched bucket represented by this root bucket */
  85         uint8_t                         scrb_bucket;
  86         /* (P) priority queue for all clutch buckets in this sched bucket */
  87         struct priority_queue           scrb_clutch_buckets;
  88         /* (P) priority queue entry to use for enqueueing root bucket into root prioq */
  89         struct priority_queue_entry     scrb_pqlink;
  90         /* (P) ageout deadline for this root bucket */
  91         uint64_t                        scrb_deadline;
  92         /* (P) warped deadline for root bucket */
  93         uint64_t                        scrb_warped_deadline;
  94         /* (P) warp remaining for root bucket */
  95         uint64_t                        scrb_warp_remaining;
  96 };
  97 typedef struct sched_clutch_root_bucket *sched_clutch_root_bucket_t;
  98
  99 /*
 100  * struct sched_clutch_root
 101  *
 102  * A clutch_root represents the root of the hierarchy. It maintains a
 103  * priority queue of all runnable root buckets. The clutch_root also
 104  * maintains the information about the last clutch_root_bucket scheduled
 105  * in order to implement bucket level quantum. The bucket level quantums
 106  * allow low priority buckets to get a "fair" chance of using the CPU even
 107  * if they contain a bunch of short executing threads. The bucket quantums
 108  * are configured using sched_clutch_root_bucket_quantum[]
 109  */
 110 struct sched_clutch_root {
 111         /* (P) root level priority; represents the highest runnable thread in the hierarchy */
 112         int16_t                         scr_priority;
 113         /* (P) total number of runnable threads in the hierarchy */
 114         uint16_t                        scr_thr_count;
 115         /* (P) root level urgency; represents the urgency of the whole hierarchy for pre-emption purposes */
 116         int16_t                         scr_urgency;
 117
 118         /* (I) processor set this hierarchy belongs to */
 119         processor_set_t                 scr_pset;
 120         /*
 121          * (P) list of all runnable clutch buckets across the system;
 122          * allows easy iteration in the sched tick based timesharing code
 123          */
 124         queue_head_t                    scr_clutch_buckets;
 125         /*
 126          * (P) list of all runnable foreign buckets in this hierarchy;
 127          * used for tracking thread groups which need to be migrated when
 128          * psets are available
 129          */
 130         queue_head_t                    scr_foreign_buckets;
 131
 132         /* Root level bucket management */
 133
 134         /* (P) bitmap of all runnable clutch_root_buckets; used for root pri calculation */
 135         bitmap_t                        scr_runnable_bitmap[BITMAP_LEN(TH_BUCKET_SCHED_MAX)];
 136         /* (P) bitmap of all runnable root buckets which have warps remaining */
 137         bitmap_t                        scr_warp_available[BITMAP_LEN(TH_BUCKET_SCHED_MAX)];
 138         /* (P) priority queue of all runnable clutch_root_buckets */
 139         struct priority_queue           scr_root_buckets;
 140         /* (P) storage for all possible clutch_root_buckets */
 141         struct sched_clutch_root_bucket scr_buckets[TH_BUCKET_SCHED_MAX];
 142 };
 143 typedef struct sched_clutch_root *sched_clutch_root_t;
 144
 145 /* forward declaration for sched_clutch */
 146 struct sched_clutch;
 147
 148 /*
 149  * sched_clutch_bucket_cpu_data_t
 150  *
 151  * Used for maintaining clutch bucket used and blocked time. The
 152  * values are used for calculating the interactivity score for the
 153  * clutch bucket.
 154  *
 155  * Since the CPU used/blocked calculation uses wide atomics, the data
 156  * types used are different based on the platform.
 157  */
 158
 159 #if __arm64__
 160
 161 #define CLUTCH_CPU_DATA_MAX             (UINT64_MAX)
 162 typedef uint64_t                        clutch_cpu_data_t;
 163 typedef unsigned __int128               clutch_cpu_data_wide_t;
 164
 165 #else /* __arm64__ */
 166
 167 #define CLUTCH_CPU_DATA_MAX             (UINT32_MAX)
 168 typedef uint32_t                        clutch_cpu_data_t;
 169 typedef uint64_t                        clutch_cpu_data_wide_t;
 170
 171 #endif /* __arm64__ */
 172
 173 typedef union sched_clutch_bucket_cpu_data {
 174         struct {
 175                 /* Clutch bucket CPU used across all threads */
 176                 clutch_cpu_data_t       scbcd_cpu_used;
 177                 /* Clutch bucket voluntary blocked time */
 178                 clutch_cpu_data_t       scbcd_cpu_blocked;
 179         } cpu_data;
 180         clutch_cpu_data_wide_t          scbcd_cpu_data_packed;
 181 } sched_clutch_bucket_cpu_data_t;
 182
 183 /*
 184  * struct sched_clutch_bucket
 185  *
 186  * A sched_clutch_bucket represents the set of threads for a thread
 187  * group at a particular scheduling bucket. It maintains information
 188  * about the CPU usage & blocking behavior of all threads part of
 189  * the clutch_bucket and maintains the timesharing attributes for
 190  * threads in its runq. It uses the decay based algorithm to timeshare
 191  * among threads in the runq.
 192  */
 193 struct sched_clutch_bucket {
 194         /* (I) bucket for the clutch_bucket */
 195         uint8_t                         scb_bucket;
 196         /* (P) priority of the clutch bucket */
 197         uint8_t                         scb_priority;
 198         /* (P) interactivity score of the clutch bucket */
 199         uint8_t                         scb_interactivity_score;
 200         /* (P) flag to indicate if the bucket is a foreign bucket */
 201         bool                            scb_foreign;
 202
 203         /* Properties used for timesharing threads in this clutch_bucket */
 204
 205         /* (P) number of threads in this clutch_bucket; should match runq.count */
 206         uint16_t                        scb_thr_count;
 207         /* (A) run count (running + runnable) for this clutch_bucket */
 208         uint16_t _Atomic                scb_run_count;
 209         /* (A) sched tick when the clutch bucket load/shifts were updated */
 210         uint32_t _Atomic                scb_timeshare_tick;
 211         /* (A) priority shifts for threads in the clutch_bucket */
 212         uint32_t _Atomic                scb_pri_shift;
 213         /* (P) linkage for all clutch_buckets in a root bucket; used for tick operations */
 214         queue_chain_t                   scb_listlink;
 215
 216
 217         /* (P) timestamp for the last time the interactivity score was updated */
 218         uint64_t                        scb_interactivity_ts;
 219         /* (P) timestamp for the last time the clutch_bucket blocked */
 220         uint64_t                        scb_blocked_ts;
 221
 222         /* (A) CPU usage information for the clutch bucket */
 223         sched_clutch_bucket_cpu_data_t  scb_cpu_data;
 224
 225         /* (P) linkage for clutch_bucket in root_bucket priority queue */
 226         struct priority_queue_entry     scb_pqlink;
 227         /* (I) clutch to which this clutch bucket belongs */
 228         struct sched_clutch             *scb_clutch;
 229         /* (A) pointer to the root of the hierarchy this bucket is in */
 230         struct sched_clutch_root        *scb_root;
 231         /* (P) priority queue of threads based on their promoted/base priority */
 232         struct priority_queue           scb_clutchpri_prioq;
 233         /* (P) runq of threads in clutch_bucket */
 234         struct run_queue                scb_runq;
 235 };
 236 typedef struct sched_clutch_bucket *sched_clutch_bucket_t;
 237
 238
 239 /*
 240  * struct sched_clutch
 241  *
 242  * A sched_clutch is a 1:1 mapping to a thread group. It maintains the
 243  * storage for all clutch buckets for this thread group and some properties
 244  * of the thread group (such as flags etc.)
 245  */
 246 struct sched_clutch {
 247         /*
 248          * (A) number of runnable threads in sched_clutch; needs to be atomic
 249          * to support cross cluster sched_clutch migrations.
 250          */
 251         uint16_t _Atomic                sc_thr_count;
 252         /*
 253          * Grouping specific parameters. Currently the implementation only
 254          * supports thread_group based grouping.
 255          */
 256         union {
 257                 /* (A) priority specified by the thread grouping mechanism */
 258                 uint8_t _Atomic         sc_tg_priority;
 259         };
 260         union {
 261                 /* (I) Pointer to thread group */
 262                 struct thread_group     *sc_tg;
 263         };
 264         /* (I) storage for all clutch_buckets for this clutch */
 265         struct sched_clutch_bucket      sc_clutch_buckets[TH_BUCKET_SCHED_MAX];
 266 };
 267 typedef struct sched_clutch *sched_clutch_t;
 268
 269
 270 /* Clutch lifecycle management */
 271 void sched_clutch_init_with_thread_group(sched_clutch_t, struct thread_group *);
 272 void sched_clutch_destroy(sched_clutch_t);
 273
 274 /* Clutch thread membership management */
 275 void sched_clutch_thread_clutch_update(thread_t, sched_clutch_t, sched_clutch_t);
 276
 277 /* Clutch timesharing stats management */
 278 uint32_t sched_clutch_thread_run_bucket_incr(thread_t, sched_bucket_t);
 279 uint32_t sched_clutch_thread_run_bucket_decr(thread_t, sched_bucket_t);
 280 void sched_clutch_cpu_usage_update(thread_t, uint64_t);
 281 uint32_t sched_clutch_thread_pri_shift(thread_t, sched_bucket_t);
 282
 283 /* Clutch properties accessors */
 284 uint32_t sched_clutch_root_count(sched_clutch_root_t);
 285
 286 /* Grouping specific external routines */
 287 extern sched_clutch_t sched_clutch_for_thread(thread_t);
 288
 289 #endif /* CONFIG_SCHED_CLUTCH */
 290
 291 #endif /* _KERN_SCHED_CLUTCH_H_ */