xnu-6153.11.26.tar.gz

[apple/xnu.git] / osfmk / kern / sched_clutch.h

/*
 * 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 <machine/atomic.h>
#include <kern/priority_queue.h>
#include <kern/thread_group.h>
#include <kern/bits.h>

#if CONFIG_SCHED_CLUTCH

/*
 * Clutch ordering based on thread group flags (specified
 * by the thread grouping mechanism). These properties
 * define a thread group specific priority boost.
 *
 * The current implementation gives a slight boost to
 * HIGH & MED thread groups which effectively deprioritizes
 * daemon thread groups which are marked "Efficient" on AMP
 * systems.
 */
#define SCHED_CLUTCH_TG_PRI_LOW           0x0
#define SCHED_CLUTCH_TG_PRI_MED           0x1
#define SCHED_CLUTCH_TG_PRI_HIGH          0x2

/*
 * 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)

/*
 *
 * 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;
	/* (P) priority queue for all clutch buckets in this sched bucket */
	struct priority_queue           scrb_clutch_buckets;
	/* (P) priority queue entry to use for enqueueing root bucket into root prioq */
	struct priority_queue_entry     scrb_pqlink;
	/* (P) ageout deadline for this root bucket */
	uint64_t                        scrb_deadline;
	/* (P) warped deadline for root bucket */
	uint64_t                        scrb_warped_deadline;
	/* (P) warp remaining for root bucket */
	uint64_t                        scrb_warp_remaining;
};
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;

	/* (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) list of all runnable foreign buckets in this hierarchy;
	 * used for tracking thread groups which need to be migrated when
	 * psets are available
	 */
	queue_head_t                    scr_foreign_buckets;

	/* Root level bucket management */

	/* (P) bitmap of all runnable clutch_root_buckets; used for root pri calculation */
	bitmap_t                        scr_runnable_bitmap[BITMAP_LEN(TH_BUCKET_SCHED_MAX)];
	/* (P) bitmap of all runnable root buckets which have warps remaining */
	bitmap_t                        scr_warp_available[BITMAP_LEN(TH_BUCKET_SCHED_MAX)];
	/* (P) priority queue of all runnable clutch_root_buckets */
	struct priority_queue           scr_root_buckets;
	/* (P) storage for all possible clutch_root_buckets */
	struct sched_clutch_root_bucket scr_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.
 *
 * Since the CPU used/blocked calculation uses wide atomics, the data
 * types used are different based on the platform.
 */

#if __arm64__

#define CLUTCH_CPU_DATA_MAX             (UINT64_MAX)
typedef uint64_t                        clutch_cpu_data_t;
typedef unsigned __int128               clutch_cpu_data_wide_t;

#else /* __arm64__ */

#define CLUTCH_CPU_DATA_MAX             (UINT32_MAX)
typedef uint32_t                        clutch_cpu_data_t;
typedef uint64_t                        clutch_cpu_data_wide_t;

#endif /* __arm64__ */

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. It maintains information
 * about the CPU usage & blocking behavior of all threads part of
 * the clutch_bucket and maintains the timesharing attributes for
 * threads in its runq. It uses the decay based algorithm to timeshare
 * among threads in the runq.
 */
struct sched_clutch_bucket {
	/* (I) bucket for the clutch_bucket */
	uint8_t                         scb_bucket;
	/* (P) priority of the clutch bucket */
	uint8_t                         scb_priority;
	/* (P) interactivity score of the clutch bucket */
	uint8_t                         scb_interactivity_score;
	/* (P) flag to indicate if the bucket is a foreign bucket */
	bool                            scb_foreign;

	/* Properties used for timesharing threads in this clutch_bucket */

	/* (P) number of threads in this clutch_bucket; should match runq.count */
	uint16_t                        scb_thr_count;
	/* (A) run count (running + runnable) for this clutch_bucket */
	uint16_t _Atomic                scb_run_count;
	/* (A) sched tick when the clutch bucket load/shifts were updated */
	uint32_t _Atomic                scb_timeshare_tick;
	/* (A) priority shifts for threads in the clutch_bucket */
	uint32_t _Atomic                scb_pri_shift;
	/* (P) linkage for all clutch_buckets in a root bucket; used for tick operations */
	queue_chain_t                   scb_listlink;


	/* (P) timestamp for the last time the interactivity score was updated */
	uint64_t                        scb_interactivity_ts;
	/* (P) timestamp for the last time the clutch_bucket blocked */
	uint64_t                        scb_blocked_ts;

	/* (A) CPU usage information for the clutch bucket */
	sched_clutch_bucket_cpu_data_t  scb_cpu_data;

	/* (P) linkage for clutch_bucket in root_bucket priority queue */
	struct priority_queue_entry     scb_pqlink;
	/* (I) clutch to which this clutch bucket belongs */
	struct sched_clutch             *scb_clutch;
	/* (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           scb_clutchpri_prioq;
	/* (P) runq of threads in clutch_bucket */
	struct run_queue                scb_runq;
};
typedef struct sched_clutch_bucket *sched_clutch_bucket_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 {
		/* (A) priority specified by the thread grouping mechanism */
		uint8_t _Atomic         sc_tg_priority;
	};
	union {
		/* (I) Pointer to thread group */
		struct thread_group     *sc_tg;
	};
	/* (I) storage for all clutch_buckets for this clutch */
	struct sched_clutch_bucket      sc_clutch_buckets[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);

/* 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);

#endif /* CONFIG_SCHED_CLUTCH */

#endif /* _KERN_SCHED_CLUTCH_H_ */