/*
* Copyright (c) 2018 Apple Inc. All rights reserved.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. The rights granted to you under the License
* may not be used to create, or enable the creation or redistribution of,
* unlawful or unlicensed copies of an Apple operating system, or to
* circumvent, violate, or enable the circumvention or violation of, any
* terms of an Apple operating system software license agreement.
*
* Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
*/
#ifndef _KERN_SCHED_CLUTCH_H_
#define _KERN_SCHED_CLUTCH_H_
#include <kern/sched.h>
#include <kern/priority_queue.h>
#include <kern/bits.h>
#if !SCHED_TEST_HARNESS
#include <machine/atomic.h>
#include <kern/thread_group.h>
#endif /* !SCHED_TEST_HARNESS */
#if CONFIG_SCHED_CLUTCH
/*
* For the current implementation, bound threads are not managed
* in the clutch hierarchy. This helper macro is used to indicate
* if the thread should be in the hierarchy.
*/
#define SCHED_CLUTCH_THREAD_ELIGIBLE(thread) ((thread->bound_processor) == PROCESSOR_NULL)
#if CONFIG_SCHED_EDGE
#define SCHED_CLUTCH_THREAD_CLUSTER_BOUND(thread) (thread->th_bound_cluster_id != THREAD_BOUND_CLUSTER_NONE)
#define SCHED_CLUTCH_THREAD_CLUSTER_BOUND_SOFT(thread) ((thread->sched_flags & TH_SFLAG_BOUND_SOFT) != 0)
#else /* CONFIG_SCHED_EDGE */
#define SCHED_CLUTCH_THREAD_CLUSTER_BOUND(thread) (0)
#define SCHED_CLUTCH_THREAD_CLUSTER_BOUND_SOFT(thread) (0)
#endif /* CONFIG_SCHED_EDGE */
/*
* Clutch Bucket Runqueue Structure.
*/
struct sched_clutch_bucket_runq {
int scbrq_highq;
int scbrq_count;
bitmap_t scbrq_bitmap[BITMAP_LEN(NRQS_MAX)];
circle_queue_head_t scbrq_queues[NRQS_MAX];
};
typedef struct sched_clutch_bucket_runq *sched_clutch_bucket_runq_t;
/*
*
* Clutch hierarchy locking protocol
*
* The scheduler clutch hierarchy is protected by a combination of
* atomics and pset lock.
* - All fields protected by the pset lock are annotated with (P)
* - All fields updated using atomics are annotated with (A)
* - All fields that are unprotected and are not updated after
* initialization are annotated with (I)
*/
/*
* struct sched_clutch_root_bucket
*
* A clutch_root_bucket represents all threads across all thread groups
* that are in the same scheduler bucket (FG/IN/...). The clutch_root_bucket
* is selected for execution by the root level bucket selection algorithm
* which bases the decision on the clutch_root_bucket's deadline (EDF). The
* deadline for a root bucket is calculated based on its runnable timestamp
* and the worst-case-execution-latency values specied in sched_clutch_root_bucket_wcel[]
*/
struct sched_clutch_root_bucket {
/* (I) sched bucket represented by this root bucket */
uint8_t scrb_bucket;
/* (I) Indicates the root bucket represents cluster bound threads */
bool scrb_bound;
/* (P) Indicates if the root bucket is in starvation avoidance mode */
bool scrb_starvation_avoidance;
union {
/* (P) priority queue for all unbound clutch buckets in this sched bucket */
struct sched_clutch_bucket_runq scrb_clutch_buckets;
/* (P) Runqueue for all bound threads part of this root bucket */
struct run_queue scrb_bound_thread_runq;
};
/* (P) priority queue entry to use for enqueueing root bucket into root prioq */
struct priority_queue_entry_deadline scrb_pqlink;
/* (P) warped deadline for root bucket */
uint64_t scrb_warped_deadline;
/* (P) warp remaining for root bucket */
uint64_t scrb_warp_remaining;
/* (P) timestamp for the start of the starvation avoidance window */
uint64_t scrb_starvation_ts;
};
typedef struct sched_clutch_root_bucket *sched_clutch_root_bucket_t;
/*
* struct sched_clutch_root
*
* A clutch_root represents the root of the hierarchy. It maintains a
* priority queue of all runnable root buckets. The clutch_root also
* maintains the information about the last clutch_root_bucket scheduled
* in order to implement bucket level quantum. The bucket level quantums
* allow low priority buckets to get a "fair" chance of using the CPU even
* if they contain a bunch of short executing threads. The bucket quantums
* are configured using sched_clutch_root_bucket_quantum[]
*/
struct sched_clutch_root {
/* (P) root level priority; represents the highest runnable thread in the hierarchy */
int16_t scr_priority;
/* (P) total number of runnable threads in the hierarchy */
uint16_t scr_thr_count;
/* (P) root level urgency; represents the urgency of the whole hierarchy for pre-emption purposes */
int16_t scr_urgency;
#if CONFIG_SCHED_EDGE
/* (P) runnable shared resource load enqueued in this cluster/root hierarchy */
uint16_t scr_shared_rsrc_load_runnable[CLUSTER_SHARED_RSRC_TYPE_COUNT];
#endif /* CONFIG_SCHED_EDGE */
uint32_t scr_cluster_id;
/* (I) processor set this hierarchy belongs to */
processor_set_t scr_pset;
/*
* (P) list of all runnable clutch buckets across the system;
* allows easy iteration in the sched tick based timesharing code
*/
queue_head_t scr_clutch_buckets;
/*
* (P) priority queue of all runnable foreign buckets in this hierarchy;
* used for tracking thread groups which need to be migrated when
* psets are available or rebalancing threads on CPU idle.
*/
struct priority_queue_sched_max scr_foreign_buckets;
/* Root level bucket management */
/* (P) bitmap of all runnable unbounded root buckets */
bitmap_t scr_unbound_runnable_bitmap[BITMAP_LEN(TH_BUCKET_SCHED_MAX)];
/* (P) bitmap of all runnable unbounded root buckets which have warps remaining */
bitmap_t scr_unbound_warp_available[BITMAP_LEN(TH_BUCKET_SCHED_MAX)];
/* (P) bitmap of all runnable bounded root buckets */
bitmap_t scr_bound_runnable_bitmap[BITMAP_LEN(TH_BUCKET_SCHED_MAX)];
/* (P) bitmap of all runnable bounded root buckets which have warps remaining */
bitmap_t scr_bound_warp_available[BITMAP_LEN(TH_BUCKET_SCHED_MAX)];
/* (P) priority queue of all runnable unbounded root buckets in deadline order */
struct priority_queue_deadline_min scr_unbound_root_buckets;
/* (P) priority queue of all bounded root buckets in deadline order */
struct priority_queue_deadline_min scr_bound_root_buckets;
/* (P) cumulative run counts at each bucket for load average calculation */
uint16_t _Atomic scr_cumulative_run_count[TH_BUCKET_SCHED_MAX];
/* (P) storage for all unbound clutch_root_buckets */
struct sched_clutch_root_bucket scr_unbound_buckets[TH_BUCKET_SCHED_MAX];
/* (P) storage for all bound clutch_root_buckets */
struct sched_clutch_root_bucket scr_bound_buckets[TH_BUCKET_SCHED_MAX];
};
typedef struct sched_clutch_root *sched_clutch_root_t;
/* forward declaration for sched_clutch */
struct sched_clutch;
/*
* sched_clutch_bucket_cpu_data_t
*
* Used for maintaining clutch bucket used and blocked time. The
* values are used for calculating the interactivity score for the
* clutch bucket.
*/
#define CLUTCH_CPU_DATA_MAX (UINT64_MAX)
typedef uint64_t clutch_cpu_data_t;
typedef unsigned __int128 clutch_cpu_data_wide_t;
typedef union sched_clutch_bucket_cpu_data {
struct {
/* Clutch bucket CPU used across all threads */
clutch_cpu_data_t scbcd_cpu_used;
/* Clutch bucket voluntary blocked time */
clutch_cpu_data_t scbcd_cpu_blocked;
} cpu_data;
clutch_cpu_data_wide_t scbcd_cpu_data_packed;
} sched_clutch_bucket_cpu_data_t;
/*
* struct sched_clutch_bucket
*
* A sched_clutch_bucket represents the set of threads for a thread
* group at a particular scheduling bucket in a specific cluster.
* It maintains information about the CPU usage & blocking behavior
* of all threads part of the clutch_bucket. It inherits the timeshare
* values from the clutch_bucket_group for decay and timesharing among
* threads in the clutch.
*
* Since the clutch bucket is a per thread group per-QoS entity it is
* important to keep its size small and the structure well aligned.
*/
struct sched_clutch_bucket {
#if CONFIG_SCHED_EDGE
/* (P) flag to indicate if the bucket is a foreign bucket */
bool scb_foreign;
#endif /* CONFIG_SCHED_EDGE */
/* (I) bucket for the clutch_bucket */
uint8_t scb_bucket;
/* (P) priority of the clutch bucket */
uint8_t scb_priority;
/* (P) number of threads in this clutch_bucket; should match runq.count */
uint16_t scb_thr_count;
/* Pointer to the clutch bucket group this clutch bucket belongs to */
struct sched_clutch_bucket_group *scb_group;
/* (A) pointer to the root of the hierarchy this bucket is in */
struct sched_clutch_root *scb_root;
/* (P) priority queue of threads based on their promoted/base priority */
struct priority_queue_sched_max scb_clutchpri_prioq;
/* (P) runq of threads in clutch_bucket */
struct priority_queue_sched_stable_max scb_thread_runq;
/* (P) linkage for all clutch_buckets in a root bucket; used for tick operations */
queue_chain_t scb_listlink;
/* (P) linkage for clutch_bucket in root_bucket runqueue */
queue_chain_t scb_runqlink;
/* (P) queue of threads for timesharing purposes */
queue_head_t scb_thread_timeshare_queue;
#if CONFIG_SCHED_EDGE
/* (P) linkage for all "foreign" clutch buckets in the root clutch */
struct priority_queue_entry_sched scb_foreignlink;
#endif /* CONFIG_SCHED_EDGE */
};
typedef struct sched_clutch_bucket *sched_clutch_bucket_t;
/*
* sched_clutch_counter_time_t
*
* Holds thread counts and a timestamp (typically for a clutch bucket group).
* Used to allow atomic updates to these fields.
*/
typedef union sched_clutch_counter_time {
struct {
uint64_t scct_count;
uint64_t scct_timestamp;
};
unsigned __int128 scct_packed;
} __attribute__((aligned(16))) sched_clutch_counter_time_t;
/*
* struct sched_clutch_bucket_group
*
* It represents all the threads for a thread group at a particular
* QoS/Scheduling bucket. This structure also maintains the timesharing
* properties that are used for decay calculation for all threads in the
* thread group at the specific scheduling bucket.
*/
struct sched_clutch_bucket_group {
/* (I) bucket for the clutch_bucket_group */
uint8_t scbg_bucket;
/* (A) sched tick when the clutch bucket group load/shifts were updated */
uint32_t _Atomic scbg_timeshare_tick;
/* (A) priority shifts for threads in the clutch_bucket_group */
uint32_t _Atomic scbg_pri_shift;
/* (A) preferred cluster ID for clutch bucket */
uint32_t _Atomic scbg_preferred_cluster;
/* (A) cluster ID for AMP rebalancing */
uint32_t scbg_amp_rebalance_last_chosen;
/* (I) clutch to which this clutch bucket_group belongs */
struct sched_clutch *scbg_clutch;
/* (A) holds blocked timestamp and runnable/running count */
sched_clutch_counter_time_t scbg_blocked_data;
/* (P/A depending on scheduler) holds pending timestamp and thread count */
sched_clutch_counter_time_t scbg_pending_data;
/* (P/A depending on scheduler) holds interactivity timestamp and score */
sched_clutch_counter_time_t scbg_interactivity_data;
/* (A) CPU usage information for the clutch bucket group */
sched_clutch_bucket_cpu_data_t scbg_cpu_data;
/* Storage for all clutch buckets for a thread group at scbg_bucket */
struct sched_clutch_bucket *scbg_clutch_buckets;
};
typedef struct sched_clutch_bucket_group *sched_clutch_bucket_group_t;
/*
* struct sched_clutch
*
* A sched_clutch is a 1:1 mapping to a thread group. It maintains the
* storage for all clutch buckets for this thread group and some properties
* of the thread group (such as flags etc.)
*/
struct sched_clutch {
/*
* (A) number of runnable threads in sched_clutch; needs to be atomic
* to support cross cluster sched_clutch migrations.
*/
uint16_t _Atomic sc_thr_count;
/*
* Grouping specific parameters. Currently the implementation only
* supports thread_group based grouping.
*/
union {
/* (I) Pointer to thread group */
struct thread_group *sc_tg;
};
/* (I) storage for all clutch_buckets for this clutch */
struct sched_clutch_bucket_group sc_clutch_groups[TH_BUCKET_SCHED_MAX];
};
typedef struct sched_clutch *sched_clutch_t;
/* Clutch lifecycle management */
void sched_clutch_init_with_thread_group(sched_clutch_t, struct thread_group *);
void sched_clutch_destroy(sched_clutch_t);
/* Clutch thread membership management */
void sched_clutch_thread_clutch_update(thread_t, sched_clutch_t, sched_clutch_t);
uint32_t sched_edge_thread_preferred_cluster(thread_t);
/* Clutch timesharing stats management */
uint32_t sched_clutch_thread_run_bucket_incr(thread_t, sched_bucket_t);
uint32_t sched_clutch_thread_run_bucket_decr(thread_t, sched_bucket_t);
void sched_clutch_cpu_usage_update(thread_t, uint64_t);
uint32_t sched_clutch_thread_pri_shift(thread_t, sched_bucket_t);
/* Clutch properties accessors */
uint32_t sched_clutch_root_count(sched_clutch_root_t);
/* Grouping specific external routines */
extern sched_clutch_t sched_clutch_for_thread(thread_t);
extern sched_clutch_t sched_clutch_for_thread_group(struct thread_group *);
#if CONFIG_SCHED_EDGE
/*
* Getter and Setter for Edge configuration. Used by CLPC to affect thread migration behavior.
*/
void sched_edge_matrix_get(sched_clutch_edge *edge_matrix, bool *edge_request_bitmap, uint64_t flags, uint64_t matrix_order);
void sched_edge_matrix_set(sched_clutch_edge *edge_matrix, bool *edge_changes_bitmap, uint64_t flags, uint64_t matrix_order);
void sched_edge_tg_preferred_cluster_change(struct thread_group *tg, uint32_t *tg_bucket_preferred_cluster, sched_perfcontrol_preferred_cluster_options_t options);
uint16_t sched_edge_cluster_cumulative_count(sched_clutch_root_t root_clutch, sched_bucket_t bucket);
uint16_t sched_edge_shared_rsrc_runnable_load(sched_clutch_root_t root_clutch, cluster_shared_rsrc_type_t load_type);
#endif /* CONFIG_SCHED_EDGE */
#endif /* CONFIG_SCHED_CLUTCH */
#endif /* _KERN_SCHED_CLUTCH_H_ */