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 */
59struct 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};
65typedef 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 */
89struct 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};
112typedef 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 */
125struct 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};
175typedef struct sched_clutch_root *sched_clutch_root_t;
176
177/* forward declaration for sched_clutch */
178struct 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)
188typedef uint64_t clutch_cpu_data_t;
189typedef unsigned __int128 clutch_cpu_data_wide_t;
190
191typedef 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 */
214struct 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};
246typedef 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 */
254typedef 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 */
270struct 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};
294typedef 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 */
304struct 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};
321typedef struct sched_clutch *sched_clutch_t;
322
323
324/* Clutch lifecycle management */
325void sched_clutch_init_with_thread_group(sched_clutch_t, struct thread_group *);
326void sched_clutch_destroy(sched_clutch_t);
327
328/* Clutch thread membership management */
329void sched_clutch_thread_clutch_update(thread_t, sched_clutch_t, sched_clutch_t);
330uint32_t sched_edge_thread_preferred_cluster(thread_t);
331
332/* Clutch timesharing stats management */
333uint32_t sched_clutch_thread_run_bucket_incr(thread_t, sched_bucket_t);
334uint32_t sched_clutch_thread_run_bucket_decr(thread_t, sched_bucket_t);
335void sched_clutch_cpu_usage_update(thread_t, uint64_t);
336uint32_t sched_clutch_thread_pri_shift(thread_t, sched_bucket_t);
337
338/* Clutch properties accessors */
339uint32_t sched_clutch_root_count(sched_clutch_root_t);
340
341/* Grouping specific external routines */
342extern sched_clutch_t sched_clutch_for_thread(thread_t);
343extern 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 */
350void sched_edge_matrix_get(sched_clutch_edge *edge_matrix, bool *edge_request_bitmap, uint64_t flags, uint64_t matrix_order);
351void sched_edge_matrix_set(sched_clutch_edge *edge_matrix, bool *edge_changes_bitmap, uint64_t flags, uint64_t matrix_order);
352void sched_edge_tg_preferred_cluster_change(struct thread_group *tg, uint32_t *tg_bucket_preferred_cluster, sched_perfcontrol_preferred_cluster_options_t options);
353
354uint16_t sched_edge_cluster_cumulative_count(sched_clutch_root_t root_clutch, sched_bucket_t bucket);
355uint16_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