Message-ID: <20200508153604.GA27289@geo.homenetwork>
Date:   Fri, 8 May 2020 23:36:04 +0800
From:   Tao Zhou <zohooouoto@...o.com.cn>
To:     John Mathew <john.mathew@...kie.com>
Cc:     linux-doc@...r.kernel.org, linux-kernel@...r.kernel.org,
        corbet@....net, mingo@...hat.com, peterz@...radead.org,
        juri.lelli@...hat.com, vincent.guittot@...aro.org,
        dietmar.eggemann@....com, rostedt@...dmis.org, bsegall@...gle.com,
        mgorman@...e.de, bristot@...hat.com, tsbogend@...ha.franken.de,
        lukas.bulwahn@...il.com, x86@...nel.org,
        linux-mips@...r.kernel.org, tglx@...utronix.de,
        mostafa.chamanara@...emark.com, rdunlap@...radead.org,
        Oleg Tsymbal <oleg.tsymbal@...kie.com>
Subject: Re: [RFC PATCH v3 2/3] docs: scheduler: Add scheduler overview
 documentation

Hi John,

On Thu, May 07, 2020 at 09:05:52PM +0300, John Mathew wrote:
> Add documentation for
>  -scheduler overview
>  -scheduler state transtion
>  -CFS overview
>  -scheduler data structs
> 
> Add rst for scheduler APIs and modify sched/core.c
> to add kernel-doc comments.
> 
> Suggested-by: Lukas Bulwahn <lukas.bulwahn@...il.com>
> Co-developed-by: Mostafa Chamanara <mostafa.chamanara@...emark.com>
> Signed-off-by: Mostafa Chamanara <mostafa.chamanara@...emark.com>
> Co-developed-by: Oleg Tsymbal <oleg.tsymbal@...kie.com>
> Signed-off-by: Oleg Tsymbal <oleg.tsymbal@...kie.com>
> Signed-off-by: John Mathew <john.mathew@...kie.com>
> ---
>  Documentation/scheduler/cfs-overview.rst      | 113 ++++++++
>  Documentation/scheduler/index.rst             |   7 +-
>  Documentation/scheduler/overview.rst          | 266 ++++++++++++++++++
>  .../scheduler/sched-data-structs.rst          | 253 +++++++++++++++++
>  Documentation/scheduler/scheduler-api.rst     |  31 ++
>  kernel/sched/core.c                           |  28 +-
>  kernel/sched/sched.h                          | 169 ++++++++++-
>  7 files changed, 858 insertions(+), 9 deletions(-)
>  create mode 100644 Documentation/scheduler/cfs-overview.rst
>  create mode 100644 Documentation/scheduler/sched-data-structs.rst
>  create mode 100644 Documentation/scheduler/scheduler-api.rst
> 
> diff --git a/Documentation/scheduler/cfs-overview.rst b/Documentation/scheduler/cfs-overview.rst
> new file mode 100644
> index 000000000000..b717f2d3e340
> --- /dev/null
> +++ b/Documentation/scheduler/cfs-overview.rst
> @@ -0,0 +1,113 @@
> +.. SPDX-License-Identifier: GPL-2.0+
> +
> +=============
> +CFS Overview
> +=============
> +
> +Linux 2.6.23 introduced a modular scheduler core and a Completely Fair
> +Scheduler (CFS) implemented as a scheduling module. A brief overview of the
> +CFS design is provided in :doc:`sched-design-CFS`
> +
> +In addition there have been many improvements to the CFS, a few of which are
> +
> +**Thermal Pressure**:
> +cpu_capacity initially reflects the maximum possible capacity of a CPU.
> +Thermal pressure on a CPU means this maximum possible capacity is
> +unavailable due to thermal events. Average thermal pressure for a CPU
> +is now subtracted from its maximum possible capacity so that cpu_capacity
> +reflects the remaining maximum capacity.
> +
> +**Use Idle CPU for NUMA balancing**:
> +Idle CPU is used as a migration target instead of comparing tasks.
> +Information on an idle core is cached while gathering statistics
> +and this is used to avoid a second scan of the node runqueues if load is
> +not imbalanced. Preference is given to an idle core rather than an
> +idle SMT sibling to avoid packing HT siblings due to linearly scanning
> +the node cpumask. Multiple tasks can attempt to select an idle CPU but
> +fail because a NUMA balance is active on that CPU, in this case instead of
> +failing, an alternative idle CPU scanned.
> +
> +**Asymmetric CPU capacity wakeup scan**:
> +Previous assumption that CPU capacities within an SD_SHARE_PKG_RESOURCES
> +domain (sd_llc) are homogeneous didn't hold for newer generations of big.LITTLE
> +systems (DynamIQ) which can accommodate CPUs of different compute capacity
> +within a single LLC domain. A new idle sibling helper function was added
> +which took CPU capacity into account. The policy is to pick the first idle
> +CPU which is big enough for the task (task_util * margin < cpu_capacity).
> +If no idle CPU is big enough, the idle CPU with the highest capacity is
> +picked.
> +
> +**Optimized idle core selection**:
> +Previously all threads of a core were looped through to evaluate if the
> +core is idle or not. This was unnecessary. If a thread of a core is not
> +idle, skip evaluating other threads of a core. Also while clearing the
> +cpumask, bits of all CPUs of a core can be cleared in one shot.
> +
> +**Load balance aggressively for SCHED_IDLE CPUs**:
> +The fair scheduler performs periodic load balance on every CPU to check
> +if it can pull some tasks from other busy CPUs. The duration of this
> +periodic load balance is set to scheduler domain's balance_interval and
> +multiplied by a busy_factor (set to 32 by default) for the busy CPUs. This
> +multiplication is done for busy CPUs to avoid doing load balance too
> +often and rather spend more time executing actual task. While that is
> +the right thing to do for the CPUs busy with SCHED_OTHER or SCHED_BATCH
> +tasks, it may not be the optimal thing for CPUs running only SCHED_IDLE
> +tasks. With the recent enhancements in the fair scheduler around SCHED_IDLE
> +CPUs, it is now preferred to enqueue a newly-woken task to a SCHED_IDLE
> +CPU instead of other busy or idle CPUs. The same reasoning is applied
> +to the load balancer as well to make it migrate tasks more aggressively
> +to a SCHED_IDLE CPU, as that will reduce the scheduling latency of the
> +migrated (SCHED_OTHER) tasks. Fair scheduler now does the next
> +load balance soon after the last non-SCHED_IDLE task is dequeued from a
> +runqueue, i.e. making the CPU SCHED_IDLE.
> +
> +**Load balancing algorithm Reworked**:
> +The load balancing algorithm contained some heuristics which became
> +meaningless since the rework of the scheduler's metrics like the
> +introduction of PELT. The new load balancing algorithm fixes several
> +pending wrong tasks placement
> +
> + * the 1 task per CPU case with asymmetric system
> + * the case of CFS task preempted by other class
> + * the case of tasks not evenly spread on groups with spare capacity
> +
> +Also the load balance decisions have been consolidated in the 3 separate
> +functions.
> +
> +**Energy-aware wake-ups speeded up**:
> +EAS computes the energy impact of migrating a waking task when deciding
> +on which CPU it should run. However, the previous approach had high algorithmic
> +complexity, which resulted in prohibitively high wake-up latencies on
> +systems with complex energy models, such as systems with per-CPU DVFS. On
> +such systems, the algorithm complexity was O(n^2). To address this,
> +the EAS wake-up path was re-factored to compute the energy 'delta' on a
> +per-performance domain basis, rather than system-wide, which brings the
> +complexity down to O(n).
> +
> +**Selection of an energy-efficient CPU on task wake-up**:
> +If an Energy Model (EM) is available and if the system isn't overutilized,
> +waking tasks are re-routed into an energy-aware placement algorithm.
> +The selection of an energy-efficient CPU for a task is achieved by estimating
> +the impact on system-level active energy resulting from the placement of the
> +task on the CPU with the highest spare capacity in each performance domain.
> +This strategy spreads tasks in a performance domain and avoids overly
> +aggressive task packing. The best CPU energy-wise is then selected if it
> +saves a large enough amount of energy with respect to prev_cpu.
> +
> +**Consider misfit tasks when load-balancing**:
> +On asymmetric CPU capacity systems load intensive tasks can end up on
> +CPUs that don't suit their compute demand. In this scenario 'misfit'
> +tasks are migrated to CPUs with higher compute capacity to ensure better
> +throughput. A new group_type: group_misfit_task is added and indicates this
> +scenario. Tweaks to the load-balance code are done to make the migrations
> +happen. Misfit balancing is done between a source group of lower per-CPU
> +capacity and destination group of higher compute capacity. Otherwise, misfit
> +balancing is ignored.
> +
> +**Make schedstats a runtime tunable that is disabled by default**:
> +schedstats is very useful during debugging and performance tuning but it
> +incurred overhead to calculate the stats. A kernel command-line and sysctl
> +tunable was added to enable or disable schedstats on demand (when it's built in).
> +It is disabled by default. The benefits are dependent on how
> +scheduler-intensive the workload is.
> +
> diff --git a/Documentation/scheduler/index.rst b/Documentation/scheduler/index.rst
> index ede1a30a6894..f311abe5b711 100644
> --- a/Documentation/scheduler/index.rst
> +++ b/Documentation/scheduler/index.rst
> @@ -17,10 +17,13 @@ specific implementation differences.
>      :maxdepth: 2
>  
>      overview
> +    sched-data-structs
> +    cfs-overview
>      sched-design-CFS
>      sched-features
> -    arch-specific.rst
> -    sched-debugging.rst
> +    arch-specific
> +    sched-debugging
> +    scheduler-api
>  
>  .. only::  subproject and html
>  
> diff --git a/Documentation/scheduler/overview.rst b/Documentation/scheduler/overview.rst
> index aee16feefc61..f2cb0c901208 100644
> --- a/Documentation/scheduler/overview.rst
> +++ b/Documentation/scheduler/overview.rst
> @@ -3,3 +3,269 @@
>  ====================
>  Scheduler overview
>  ====================
> +
> +Linux kernel implements priority-based scheduling. More than one process are
> +allowed to run at any given time and each process is allowed to run as if it
> +were the only process on the system. The process scheduler coordinates which
> +process runs when. In that context, it has the following tasks:
> +
> +* share CPU cores equally among all currently running processes.
> +* pick appropriate process to run next if required, considering scheduling
> +  class/policy and process priorities.
> +* balance processes between multiple cores in SMP systems.
> +
> +The scheduler attempts to be responsive for I/O bound processes and efficient
> +for CPU bound processes. The scheduler also applies different scheduling
> +policies for real time and normal processes based on their respective
> +priorities. Higher priorities in the kernel have a numerical smaller
> +value. Real time priorities range from 1 (highest) – 99 whereas normal
> +priorities range from 100 – 139 (lowest). SCHED_DEADLINE tasks have negative
> +priorities, reflecting the fact that any of them has higher priority than
> +RT and NORMAL/BATCH tasks.
> +
> +Process Management
> +==================
> +
> +Each process in the system is represented by struct task_struct. When a
> +process/thread is created, the kernel allocates a new task_struct for it.
> +The kernel then stores this task_struct in an RCU list. Macro next_task()
> +allows a process to obtain its next task and for_each_process() macro enables
> +traversal of the list.
> +
> +Frequently used fields of the task struct are:
> +
> +*state:* The running state of the task. The possible states are:
> +
> +* TASK_RUNNING: The task is currently running or in a run queue waiting
> +  to run.
> +* TASK_INTERRUPTIBLE: The task is sleeping waiting for some event to occur.
> +  This task can be interrupted by signals. On waking up the task transitions
> +  to TASK_RUNNING.
> +* TASK_UNINTERRUPTIBLE: Similar to TASK_INTERRUPTIBLE but does not wake
> +  up on signals. Needs an explicit wake-up call to be woken up. Contributes
> +  to loadavg.
> +* __TASK_TRACED: Task is being traced by another task like a debugger.
> +* __TASK_STOPPED: Task execution has stopped and not eligible to run.
> +  SIGSTOP, SIGTSTP etc causes this state.  The task can be continued by
> +  the signal SIGCONT.
> +* TASK_PARKED: State to support kthread parking/unparking.
> +* TASK_DEAD: If a task dies, then it sets TASK_DEAD in tsk->state and calls
> +  schedule one last time. The schedule call will never return.
> +* TASK_WAKEKILL: It works like TASK_UNINTERRUPTIBLE with the bonus that it
> +  can respond to fatal signals.
> +* TASK_WAKING: To handle concurrent waking of the same task for SMP.
> +  Indicates that someone is already waking the task.
> +* TASK_NOLOAD: To be used along with TASK_UNINTERRUPTIBLE to indicate
> +  an idle task which does not contribute to loadavg.
> +* TASK_NEW: Set during fork(), to guarantee that no one will run the task,
> +  a signal or any other wake event cannot wake it up and insert it on
> +  the runqueue.
> +
> +*exit_state* : The exiting state of the task. The possible states are:
> +
> +* EXIT_ZOMBIE: The task is terminated and waiting for parent to collect
> +  the exit information of the task.
> +* EXIT_DEAD: After collecting the exit information the task is put to
> +  this state and removed from the system.
> +
> +*static_prio:* Nice value of a task. The value of this field does
> + not change.  Value ranges from -20 to 19. This value is mapped to nice
> + value and used in the scheduler.
> +
> +*prio:* Dynamic priority of a task. Previously a function of static
> + priority and tasks interactivity. Value not used by CFS scheduler but used
> + by the RT scheduler. Might be boosted by interactivity modifiers. Changes
> + upon fork, setprio syscalls, and whenever the interactivity estimator
> + recalculates.
> +
> +*normal_prio:* Expected priority of a task. The value of static_prio
> + and normal_prio are the same for non-real-time processes. For real time
> + processes value of prio is used.
> +
> +*rt_priority:* Field used by real time tasks. Real time tasks are
> + prioritized based on this value.
> +
> +*sched_class:* Pointer to sched_class CFS structure.
> +
> +*sched_entity:* Pointer to sched_entity CFS structure.
> +
> +*policy:* Value for scheduling policy. The possible values are:
> +
> +* SCHED_NORMAL: Regular tasks use this policy.
> +* SCHED_BATCH: Tasks which need to run longer without preemption
> +  use this policy. Suitable for batch jobs.
> +* SCHED_IDLE: Policy used by background tasks.
> +* SCHED_FIFO & SCHED_RR: These policies for real time tasks. Handled by
> +  real time scheduler.
> +* SCHED_DEADLINE: Tasks which are activated on a periodic or sporadic fashion
> +  use this policy. This policy implements the Earliest Deadline First (EDF)
> +  scheduling algorithm. This policy is explained in detail in the
> +  :doc:`sched-deadline` documentation.
> +
> +*nr_cpus_allowed:* Bit field containing tasks affinity towards a set of
> + CPU cores.  Set using sched_setaffinity() system call.
> +
> +New processes are created using the fork() system call which is described
> +at manpage :manpage:`FORK(2)` or the clone system call described at
> +:manpage:`CLONE(2)`.
> +Users can create threads within a process to achieve parallelism. Threads
> +share address space, open files and other resources of the process. Threads
> +are created like normal tasks with their unique task_struct, but clone()
> +is provided with flags that enable the sharing of resources such as address
> +space ::
> +
> +	clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0);
> +
> +The scheduler schedules task_structs so from scheduler perspective there is
> +no difference between threads and processes. Threads are created using
> +the system call pthread_create described at :manpage:`PTHREAD_CREATE(3)`
> +POSIX threads creation is described at :manpage:`PTHREADS(7)`
> +
> +The Scheduler Entry Point
> +=========================
> +
> +The main scheduler entry point is an architecture independent schedule()
> +function defined in kernel/sched/core.c. Its objective is to find a process in
> +the runqueue list and then assign the CPU to it. It is invoked, directly
> +or in a lazy (deferred) way from many different places in the kernel. A lazy
> +invocation does not call the function by its name, but gives the kernel a
> +hint by setting a flag TIF_NEED_RESCHED. The flag is a message to the kernel
> +that the scheduler should be invoked as soon as possible because another
> +process deserves to run.
> +
> +Following are some places that notify the kernel to schedule:
> +
> +* scheduler_tick()
> +
> +* Running task goes to sleep state : Right before a task goes to sleep,
> +  schedule() will be called to pick the next task to run and the change
> +  its state to either TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE. For
> +  instance, prepare_to_wait() is one of the functions that makes the
> +  task go to the sleep state.
> +
> +* try_to_wake_up()
> +
> +* yield()
> +
> +* wait_event()
> +
> +* cond_resched() : It gives the scheduler a chance to run a higher-priority
> +  process.
> +
> +* cond_resched_lock() : If a reschedule is pending, drop the given lock,
> +  call schedule, and on return reacquire the lock.
> +
> +* do_task_dead()
> +
> +* preempt_schedule() : The function checks whether local interrupts are
> +  enabled and the preempt_count field of current is zero; if both
> +  conditions are true, it invokes schedule() to select another process
> +  to run.
> +
> +* preempt_schedule_irq()
> +
> +Calling functions mentioned above leads to a call to __schedule(). Note
> +that preemption must be disabled before it is called and enabled after
> +the call using preempt_disable and preempt_enable functions family.
> +
> +
> +The steps during invocation are:
> +--------------------------------
> +1. Disable preemption to avoid another task preempting the scheduling
> +   thread itself.
> +2. Retrieve the runqueue of current processor and its lock is obtained to
> +   allow only one thread to modify the runqueue at a time.
> +3. The state of the previously executed task when the schedule()
> +   was called is examined. If it is not runnable and has not been
> +   preempted in kernel mode, it is removed from the runqueue. If the
> +   previous task has non-blocked pending signals, its state is set to
> +   TASK_RUNNING and left in the runqueue.
> +4. Scheduler classes are iterated and the corresponding class hook to
> +   pick the next suitable task to be scheduled on the CPU is called.
> +   Since most tasks are handled by the sched_fair class, a shortcut to this
> +   class is implemented in the beginning of the function.
> +5. TIF_NEED_RESCHED and architecture specific need_resched flags are cleared.
> +6. If the scheduler class picks a different task from what was running
> +   before, a context switch is performed by calling context_switch().
> +   Internally, context_switch() switches to the new task's memory map and
> +   swaps the register state and stack. If scheduler class picked the same
> +   task as the previous task, no task switch is performed and the current
> +   task keeps running.
> +7. Balance callback list is processed. Each scheduling class can migrate tasks
> +   between CPUs to balance load. These load balancing operations are queued
> +   on a Balance callback list which get executed when balance_callback() is
> +   called.
> +8. The runqueue is unlocked and preemption is re-enabled. In case
> +   preemption was requested during the time in which it was disabled,
> +   schedule() is run again right away.
> +
> +Scheduler State Transition
> +==========================
> +
> +A very high level scheduler state transition flow with a few states can
> +be depicted as follows. ::
> +
> +                                       *
> +                                       |
> +                                       | task
> +                                       | forks
> +                                       v
> +                        +------------------------------+
> +                        |           TASK_NEW           |
> +                        |        (Ready to run)        |
> +                        +------------------------------+
> +                                       |
> +                                       |
> +                                       v
> +                     +------------------------------------+
> +                     |            TASK_RUNNING            |
> +   +---------------> |           (Ready to run)           | <--+
> +   |                 +------------------------------------+    |
> +   |                   |                                       |
> +   |                   | schedule() calls context_switch()     | task is preempted
> +   |                   v                                       |
> +   |                 +------------------------------------+    |
> +   |                 |            TASK_RUNNING            |    |
> +   |                 |             (Running)              | ---+
> +   | event occurred  +------------------------------------+
> +   |                   |
> +   |                   | task needs to wait for event
> +   |                   v
> +   |                 +------------------------------------+
> +   |                 |         TASK_INTERRUPTIBLE         |
> +   |                 |        TASK_UNINTERRUPTIBLE        |
> +   +-----------------|           TASK_WAKEKILL            |
> +                     +------------------------------------+
> +                                       |
> +                                       | task exits via do_exit()
> +                                       v
> +                        +------------------------------+
> +                        |          TASK_DEAD           |
> +                        |         EXIT_ZOMBIE          |
> +                        +------------------------------+
> +
> +
> +Scheduler provides tracepoints tracing all major events of the scheduler.
> +The tracepoints are defined in ::
> +
> +  include/trace/events/sched.h
> +
> +Using these tracepoints it is possible to model the scheduler state transition
> +in an automata model. The following journal paper discusses such modeling:
> +
> +Daniel B. de Oliveira, Rômulo S. de Oliveira, Tommaso Cucinotta, **A thread
> +synchronization model for the PREEMPT_RT Linux kernel**, *Journal of Systems
> +Architecture*, Volume 107, 2020, 101729, ISSN 1383-7621,
> +https://doi.org/10.1016/j.sysarc.2020.101729.
> +
> +To model the scheduler efficiently the system was divided in to generators
> +and specifications. Some of the generators used were "need_resched",
> +"sleepable" and "runnable", "thread_context" and "scheduling context".
> +The specifications are the necessary and sufficient conditions to call
> +the scheduler. New trace events were added to specify the generators
> +and specifications. In case a kernel event referred to more than one
> +event, extra fields of the kernel event was used to distinguish between
> +automation events. The final model was generated from parallel composition
> +of all generators and specifications which composed of 34 events,
> +12 generators and 33 specifications. This resulted in 9017 states, and
> +20103 transitions.
> diff --git a/Documentation/scheduler/sched-data-structs.rst b/Documentation/scheduler/sched-data-structs.rst
> new file mode 100644
> index 000000000000..ec900367cc0c
> --- /dev/null
> +++ b/Documentation/scheduler/sched-data-structs.rst
> @@ -0,0 +1,253 @@
> +.. SPDX-License-Identifier: GPL-2.0+
> +
> +=========================
> +Scheduler Data Structures
> +=========================
> +
> +The main parts of the Linux scheduler are:
> +
> +Runqueue
> +~~~~~~~~
> +
> +:c:type:`struct rq <rq>` is the central data structure of process
> +scheduling. It keeps track of tasks that are in a runnable state assigned
> +for a particular processor. Each CPU has its own run queue and stored in a
> +per CPU array::
> +
> +    DEFINE_PER_CPU(struct rq, runqueues);
> +
> +Access to the queue requires locking and lock acquire operations must be
> +ordered by ascending runqueue. Macros for accessing and locking the runqueue
> +are provided in::
> +
> +    kernel/sched/sched.h
> +
> +The runqueue contains scheduling class specific queues and several scheduling
> +statistics.
> +
> +Scheduling entity
> +~~~~~~~~~~~~~~~~~
> +Scheduler uses scheduling entities which contain sufficient information to
> +actually accomplish the scheduling job of a task or a task-group. The
> +scheduling entity may be a group of tasks or a single task. Every task is
> +associated with a sched_entity structure. CFS adds support for nesting of
> +tasks and task groups. Each scheduling entity may be run from its parents
> +runqueue. The scheduler traverses the sched_entity hierarchy to pick the
> +next task to run on the CPU. The entity gets picked up from the cfs_rq on
> +which it is queued and its time slice is divided among all the tasks on its my_q.
> +
> +Virtual Runtime
> +~~~~~~~~~~~~~~~~~
> +Virtual Run Time or vruntime is the amount of time a task has spent running
> +on the CPU. It is updated periodically by scheduler_tick(). Tasks are stored
> +in the CFS scheduling class rbtree sorted by vruntime. scheduler_tick() calls
> +corresponding hook of CFS which first updates the runtime statistics of the
> +currently running task and checks if the current task needs to be preempted.
> +vruntime of the task based on the formula ::
> +
> +    vruntime += delta_exec * (NICE_0_LOAD/curr->load.weight);
> +
> +where:
> +
> +* delta_exec is the time in nanoseconds spent by the task since the last time
> +  vruntime was updated.
> +* NICE_0_LOAD is the load of a task with normal priority.
> +* curr is the shed_entity instance of the cfs_rq struct of the currently

s/shed_entity/sched_entity/

> +  running task.
> +* load.weight: sched_entity load_weight. load_weight is the encoding of
> +  the tasks priority and vruntime. The load of a task is the metric
> +  indicating the number of CPUs needed to make satisfactory progress on its
> +  job. Load of a task influences the time a task spends on the CPU and also
> +  helps to estimate the overall CPU load which is needed for load balancing.
> +  Priority of the task is not enough for the scheduler to estimate the
> +  vruntime of a process. So priority value must be mapped to the capacity of
> +  the standard CPU which is done in the array :c:type:`sched_prio_to_weight[]`.
> +  The array contains mappings for the nice values from -20 to 19. Nice value
> +  0 is mapped to 1024. Each entry advances by approximately 1.25 which means
> +  for every increment in nice value the task gets 10% less CPU and vice versa.
> +
> +Scheduler classes
> +~~~~~~~~~~~~~~~~~
> +It is an extensible hierarchy of scheduler modules. The modules encapsulate
> +scheduling policy details. They are called from the core code which is
> +independent. Scheduling classes are implemented through the sched_class
> +structure. dl_sched_class for deadline scheduler, fair_sched_class for CFS
> +and rt_sched_class for RT are implementations of this class.
> +
> +The important methods of scheduler class are:
> +
> +enqueue_task and dequeue_task
> +    These functions are used to put and remove tasks from the runqueue
> +    respectively. The function takes the runqueue, the task which needs to
> +    be enqueued/dequeued and a bit mask of flags. The main purpose of the
> +    flags is to describe why the enqueue or dequeue is being called.
> +    The different flags used are described in ::
> +
> +        kernel/sched/sched.h
> +
> +    enqueue_task and dequeue_task are called for following purposes.
> +
> +    - When waking a newly created task for the first time. Called with
> +      ENQUEUE_NOCLOCK
> +    - When migrating a task from one CPU's runqueue to another. Task will be
> +      first dequeued from its old runqueue, new CPU will be added to the
> +      task struct,  runqueue of the new CPU will be retrieved and task is
> +      then enqueued on this new runqueue.
> +    - When do_set_cpus_allowed() is called to change a tasks CPU affinity. If
> +      the task is queued on a runqueue, it is first dequeued with the
> +      DEQUEUE_SAVE and DEQUEUE_NOCLOCK flags set. The set_cpus_allowed()
> +      function of the corresponding scheduling class will be called.
> +      enqueue_task() is then called with ENQUEUE_RESTORE and ENQUEUE_NOCLOCK
> +      flags set.
> +    - When changing the priority of a task using rt_mutex_setprio(). This
> +      function implements the priority inheritance logic of the RT mutex
> +      code. This function changes the effective priority of a task which may
> +      in turn change the scheduling class of the task. If so enqueue_task is
> +      called with flags corresponding to each class.
> +    - When user changes the nice value of the task. If the task is queued on
> +      a runqueue, it first needs to be dequeued, then its load weight and
> +      effective priority needs to be set. Following which the task is
> +      enqueued with ENQUEUE_RESTORE and ENQUEUE_NOCLOCK flags set.
> +    - When __sched_setscheduler() is called. This function enables changing
> +      the scheduling policy and/or RT priority of a thread. If the task is
> +      on a runqueue, it will be first dequeued, changes will be made and
> +      then enqueued.
> +    - When moving tasks between scheduling groups. The runqueue of the tasks
> +      is changed when moving between groups. For this purpose if the task
> +      is running on a queue, it is first dequeued with DEQUEUE_SAVE, DEQUEUE_MOVE
> +      and DEQUEUE_NOCLOCK flags set, followed by which scheduler function to
> +      change the tsk->se.cfs_rq and tsk->se.parent and then task is enqueued
> +      on the runqueue with the same flags used in dequeue.
> +
> +pick_next_task
> +    Called by __schedule() to pick the next best task to run.
> +    Scheduling class structure has a pointer pointing to the next scheduling
> +    class type and each scheduling class is linked using a singly linked list.
> +    The __schedule() function iterates through the corresponding
> +    functions of the scheduler classes in priority order to pick up the next
> +    best task to run. Since tasks belonging to the idle class and fair class
> +    are frequent, the scheduler optimizes the picking of next task to call
> +    the pick_next_task_fair() if the previous task was of the similar
> +    scheduling class.
> +
> +put_prev_task
> +    Called by the scheduler when a running task is being taken off a CPU.
> +    The behavior of this function depends on individual scheduling classes
> +    and called in the following cases.
> +
> +    - When do_set_cpus_allowed() is called and if the task is currently running.
> +    - When scheduler pick_next_task() is called, the put_prev_task() is
> +      called with the previous task as function argument.
> +    - When rt_mutex_setprio() is called and if the task is currently running.
> +    - When user changes the nice value of the task and if the task is
> +      currently running.
> +    - When __sched_setscheduler() is called and if the task is currently
> +      running.
> +    - When moving tasks between scheduling groups through the sched_move_task()
> +      and if the task is ćurrently running.

s/ćurrently/currently

Thanks,
Tau

> +
> +    In CFS class this function is used to put the currently running task back
> +    into the CFS RB tree. When a task is running it is dequeued from the tree.
> +    This is to prevent redundant enqueue's and dequeue's for updating its
> +    vruntime. vruntime of tasks on the tree needs to be updated by update_curr()
> +    to keep the tree in sync. In DL(deadline) and RT classes additional tree is
> +    maintained for facilitating task migration between CPUs through push
> +    operation between runqueues for load balancing. Task will be added to
> +    this queue if it is present on the scheduling class rq and the task has
> +    affinity to more than one CPU.
> +
> +set_next_task
> +    Pairs with the put_prev_task(), this function is called when the next
> +    task is set to run on the CPU. This function is called in all the places
> +    where put_prev_task is called to complete the 'change'. Change is defined
> +    as the following sequence of calls::
> +
> +         - dequeue task
> +         - put task
> +         - change the property
> +         - enqueue task
> +         - set task as current task
> +
> +    It resets the run time statistics for the entity with
> +    the runqueue clock.
> +    In case of CFS scheduling class, it will set the pointer to the current
> +    scheduling entity to the picked task and accounts bandwidth usage on
> +    the cfs_rq. In addition it will also remove the current entity from the
> +    CFS runqueue for vruntime update optimization opposite to what was done
> +    in put_prev_task.
> +    For the SCHED_DEADLINE and RT classes it will
> +
> +    - dequeue the picked task from the tree of pushable tasks.
> +    - update the load average in case the previous task belonged to another
> +      class.
> +    - queues the function to push tasks from current runqueue to other CPUs
> +      which can preempt and start execution. Balance callback list is used.
> +
> +task_tick
> +    Called from scheduler_tick(), hrtick() and sched_tick_remote() to update
> +    the current task statistics and load averages. Also restarting the high
> +    resolution tick timer is done if high resolution timers are enabled.
> +    scheduler_tick() runs at 1/HZ and is called from the timer interrupt
> +    handler of the Kernel internal timers.
> +    hrtick() is called from high resolution timers to deliver an accurate
> +    preemption tick as the regular scheduler tick that runs at 1/HZ can be
> +    too coarse when nice levels are used.
> +    sched_tick_remote() Gets called by the offloaded residual 1Hz scheduler
> +    tick. In order to reduce interruptions to bare metal tasks, it is possible
> +    to outsource these scheduler ticks to the global workqueue so that a
> +    housekeeping CPU handles those remotely.
> +
> +select_task_rq
> +    Called by scheduler to get the CPU to assign a task to and migrating
> +    tasks between CPUs. Flags describe the reason the function was called.
> +    Called by try_to_wake_up() with SD_BALANCE_WAKE flag which wakes up a
> +    sleeping task.
> +    Called by wake_up_new_task() with SD_BALANCE_FORK flag which wakes up a
> +    newly forked task.
> +    Called by sched_exec() with SD_BALANCE_EXEC which is called from execv
> +    syscall.
> +    SCHED_DEADLINE class decides the CPU on which the task should be woken
> +    up based on the deadline. RT class decides based on the RT priority. Fair
> +    scheduling class balances load by selecting the idlest CPU in the
> +    idlest group, or under certain conditions an idle sibling CPU if the
> +    domain has SD_WAKE_AFFINE set.
> +
> +balance
> +    Called by pick_next_task() from scheduler to enable scheduling classes
> +    to pull tasks from runqueues of other CPUs for balancing task execution
> +    between the CPUs.
> +
> +task_fork
> +    Called from sched_fork() of scheduler which assigns a task to a CPU.
> +    Fair scheduling class updates runqueue clock, runtime statistics and
> +    vruntime for the scheduling entity.
> +
> +yield_task
> +    Called from SYSCALL sched_yield to yield the CPU to other tasks.
> +    SCHED_DEADLINE class forces the runtime of the task to zero using a special
> +    flag and dequeues the task from its trees. RT class requeues the task
> +    entities to the end of the run list. Fair scheduling class implements
> +    the buddy mechanism. This allows skipping onto the next highest priority
> +    scheduling entity at every level in the CFS tree, unless doing so would
> +    introduce gross unfairness in CPU time distribution.
> +
> +check_preempt_curr
> +    Check whether the task that woke up should preempt the currently
> +    running task. Called by scheduler,
> +
> +    * when moving queued task to new runqueue
> +    * ttwu()
> +    * when waking up newly created task for the first time.
> +
> +    SCHED_DEADLINE class compares the deadlines of the tasks and calls
> +    scheduler function resched_curr() if the preemption is needed. In case
> +    the deadlines are equal, migratability of the tasks is used a criteria
> +    for preemption.
> +    RT class behaves the same except it uses RT priority for comparison.
> +    Fair class sets the buddy hints before calling resched_curr() to preempt.
> +
> +Scheduler sets the scheduler class for each task based on its priority.
> +Tasks assigned with SCHED_NORMAL, SCHED_IDLE and SCHED_BATCH call
> +fair_sched_class hooks and tasks assigned with SCHED_RR and
> +SCHED_FIFO call rt_sched_class hooks. Tasks assigned with SCHED_DEADLINE
> +policy calls dl_sched_class hooks.
> diff --git a/Documentation/scheduler/scheduler-api.rst b/Documentation/scheduler/scheduler-api.rst
> new file mode 100644
> index 000000000000..1fc6bd4c2908
> --- /dev/null
> +++ b/Documentation/scheduler/scheduler-api.rst
> @@ -0,0 +1,31 @@
> +.. SPDX-License-Identifier: GPL-2.0+
> +
> +=============================
> +Scheduler related functions
> +=============================
> +
> +
> +.. kernel-doc:: kernel/sched/core.c
> +	:functions: __schedule
> +
> +.. kernel-doc:: kernel/sched/core.c
> +	:functions: scheduler_tick
> +
> +.. kernel-doc:: kernel/sched/core.c
> +	:functions: try_to_wake_up
> +
> +.. kernel-doc:: kernel/sched/core.c
> +	:functions: do_task_dead
> +
> +.. kernel-doc:: kernel/sched/core.c
> +	:functions: preempt_schedule_irq
> +
> +.. kernel-doc:: kernel/sched/core.c
> +	:functions: prepare_task_switch
> +
> +.. kernel-doc:: kernel/sched/core.c
> +	:functions: finish_task_switch
> +
> +.. kernel-doc:: kernel/sched/sched.h
> +	:functions: rq
> +
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 9a2fbf98fd6f..b349ed9b4d92 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -3576,9 +3576,13 @@ void arch_set_thermal_pressure(struct cpumask *cpus,
>  		WRITE_ONCE(per_cpu(thermal_pressure, cpu), th_pressure);
>  }
>  
> -/*
> +/**
> + * scheduler_tick - sched tick timer handler
> + *
>   * This function gets called by the timer code, with HZ frequency.
>   * We call it with interrupts disabled.
> + *
> + * Return: 0.
>   */
>  void scheduler_tick(void)
>  {
> @@ -3959,8 +3963,10 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>  	BUG();
>  }
>  
> -/*
> - * __schedule() is the main scheduler function.
> +/**
> + * __schedule() - the main scheduler function.
> + *
> + * @preempt: preemption enabled/disabled
>   *
>   * The main means of driving the scheduler and thus entering this function are:
>   *
> @@ -4089,6 +4095,12 @@ static void __sched notrace __schedule(bool preempt)
>  	balance_callback(rq);
>  }
>  
> +/**
> + * do_task_dead - handle task exit
> + *
> + * Changes the the task state to TASK_DEAD and calls
> + * schedule to pick next task to run.
> + */
>  void __noreturn do_task_dead(void)
>  {
>  	/* Causes final put_task_struct in finish_task_switch(): */
> @@ -4320,7 +4332,8 @@ EXPORT_SYMBOL_GPL(preempt_schedule_notrace);
>  
>  #endif /* CONFIG_PREEMPTION */
>  
> -/*
> +/**
> + * preempt_schedule_irq - schedule from irq context
>   * This is the entry point to schedule() from kernel preemption
>   * off of irq context.
>   * Note, that this is called and return with irqs disabled. This will
> @@ -5618,6 +5631,13 @@ SYSCALL_DEFINE0(sched_yield)
>  }
>  
>  #ifndef CONFIG_PREEMPTION
> +/**
> + * _cond_resched - explicit rescheduling
> + *
> + * gives the scheduler a chance to run a higher-priority process
> + *
> + * Return: 1 if reschedule was done, 0 if reschedule not done.
> + */
>  int __sched _cond_resched(void)
>  {
>  	if (should_resched(0)) {
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index db3a57675ccf..21f2953b72c7 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -865,12 +865,175 @@ struct uclamp_rq {
>  };
>  #endif /* CONFIG_UCLAMP_TASK */
>  
> -/*
> - * This is the main, per-CPU runqueue data structure.
> +/**
> + * struct rq - This is the main, per-CPU runqueue data structure.
>   *
>   * Locking rule: those places that want to lock multiple runqueues
>   * (such as the load balancing or the thread migration code), lock
>   * acquire operations must be ordered by ascending &runqueue.
> + *
> + * @lock:
> + *	lock to be acquired while modifying the runqueue
> + * @nr_running:
> + *	number of runnable tasks on this queue
> + * @nr_numa_running:
> + *	number of tasks running that care about their placement
> + * @nr_preferred_running:
> + *	number of tasks that are optimally NUMA placed
> + * @numa_migrate_on:
> + *	per run-queue variable to check if NUMA-balance is
> + *	active on the run-queue
> + * @last_blocked_load_update_tick:
> + *	tick stamp for decay of blocked load
> + * @has_blocked_load:
> + *	idle CPU has blocked load
> + * @nohz_tick_stopped:
> + *	CPU is going idle with tick stopped
> + * @nohz_flags:
> + *	flags indicating NOHZ idle balancer actions
> + * @nr_load_updates:
> + *	unused
> + * @nr_switches:
> + *	number of context switches
> + * @uclamp:
> + *	utilization clamp values based on CPU's RUNNABLE tasks
> + * @uclamp_flags:
> + *	flags for uclamp actions, currently one flag for idle.
> + * @cfs:
> + *	fair scheduling class runqueue
> + * @rt:
> + *	rt scheduling class runqueue
> + * @dl:
> + *	dl scheduing class runqueue
> + * @leaf_cfs_rq_list:
> + *	list of leaf cfs_rq on this CPU
> + * @tmp_alone_branch:
> + *	reference to add child before its parent in leaf_cfs_rq_list
> + * @nr_uninterruptible:
> + *	global counter where the total sum over all CPUs matters. A task
> + *      can increase this counter on one CPU and if it got migrated
> + *	afterwards it may decrease it on another CPU. Always updated under
> + *	the runqueue lock
> + * @curr:
> + *	points to the currently running task of this rq.
> + * @idle:
> + *	points to the idle task of this rq
> + * @stop:
> + *	points to the stop task of this rq
> + * @next_balance:
> + *	shortest next balance before updating nohz.next_balance
> + * @prev_mm:
> + *	real address space of the previous task
> + * @clock_update_flags:
> + *	RQCF clock_update_flags bits
> + * @clock:
> + *	sched_clock() value for the queue
> + * @clock_task:
> + *	clock value minus irq handling time
> + * @clock_pelt:
> + *	clock which scales with current capacity when something is
> + *	running on rq and synchronizes with clock_task when rq is idle
> + * @lost_idle_time:
> + *	idle time lost when utilization of a rq has reached the
> + *	maximum value
> + * @nr_iowait:
> + *	account the idle time that we could have spend running if it
> + *	were not for IO
> + * @membarrier_state:
> + *	copy of membarrier_state from the mm_struct
> + * @rd:
> + *	root domain, each exclusive cpuset essentially defines an island
> + *	domain by fully partitioning the member CPUs from any other cpuset
> + * @sd:
> + *	a domain heirarchy of CPU groups to balance process load among them
> + * @cpu_capacity:
> + *	information about CPUs heterogeneity used for CPU performance
> + *	scaling
> + * @cpu_capacity_orig:
> + *	original capacity of a CPU before being altered by
> + *	rt tasks and/or IRQ
> + * @balance_callback:
> + *	queue to hold load balancing push and pull operations
> + * @idle_balance:
> + *	flag to do the nohz idle load balance
> + * @misfit_task_load:
> + *	set whenever the current running task has a utilization
> + *	greater than 80% of rq->cpu_capacity. A non-zero value
> + *	in this field enables misfit load balancing
> + * @active_balance:
> + *	synchronizes accesses to ->active_balance_work
> + * @push_cpu:
> + *	idle cpu to push the running task on to during active load
> + *	balancing.
> + * @active_balance_work:
> + *	callback scheduled to run on one or multiple cpus
> + *	with maximum priority monopolozing those cpus.
> + * @cpu:
> + *	CPU of this runqueue
> + * @online:
> + *	Used by scheduling classes to support CPU hotplug
> + * @cfs_tasks:
> + *	an MRU list used for load balancing, sorted (except
> + *	woken tasks) starting from recently given CPU time tasks
> + *	toward tasks with max wait time in a run-queue
> + * @avg_rt:
> + *	track the utilization of RT tasks for a  more accurate
> + *	view of the utilization of the CPU when overloaded by CFS and
> + *	RT tasks
> + * @avg_dl:
> + *	track the utilization of DL tasks as CFS tasks can be preempted
> + *	by DL tasks and the CFS's utilization might no longer describe
> + *	the real utilization level
> + * @avg_irq:
> + *	track the the utilization of interrupt to give a more accurate
> + *	level of utilization of CPU taking into account the time spent
> + *	under interrupt context when rqs' clock is updated
> + * @avg_thermal:
> + *	tracks thermal pressure which is the reduction in maximum
> + *	possible capacity due to thermal events
> + * @idle_stamp:
> + *	time stamp at which idle load balance started for this rq.
> + *	Used to find the idlest CPU, when multiple idle CPUs are in
> + *	the same state
> + * @avg_idle:
> + *	average idle time for this rq
> + * @max_idle_balance_cost:
> + *	used to determine avg_idle's max value
> + * @prev_irq_time:
> + *	updated to account time consumed when a previous
> + *	update_rq_clock() happened inside a {soft,}irq region
> + * @prev_steal_time:
> + *	to account how much elapsed time was spent in steal
> + * @prev_steal_time_rq:
> + *	for fine granularity task steal time accounting by
> + *	making update_rq_clock() aware of steal time
> + * @calc_load_update:
> + *	sample window for global load-average calculations
> + * @calc_load_active:
> + *	fold any nr_active delta into a global accumulate
> + * @hrtick_csd:
> + *	call_single_data used to set hrtick timer state on a specific CPU
> + * @hrtick_timer:
> + *	HR-timer to deliver an accurate preemption tick
> + * @rq_sched_info:
> + *	runqueue specific latency stats
> + * @rq_cpu_time:
> + *	runqueue specific accumulated per-task cpu runtime
> + * @yld_count:
> + *	runqueue specific sys_sched_yield() stats
> + * @sched_count:
> + *	runqueue specific __schedule() stats
> + * @sched_goidle:
> + *	runqueue specific idle scheduling class stats
> + * @ttwu_count:
> + *	runqueue specific idle ttwu stats , both remote and local
> + * @ttwu_local:
> + *	ttwu count for the CPU of the rq
> + * @wake_list:
> + *	list which stores tasks being woken up remotely by ttwu
> + * @idle_state:
> + *	cpuidle state pointer of the CPU of this rq used to make a
> + *	better decision when balancing tasks
>   */
>  struct rq {
>  	/* runqueue lock: */
> @@ -1136,7 +1299,7 @@ static inline u64 rq_clock_task(struct rq *rq)
>  	return rq->clock_task;
>  }
>  
> -/**
> +/*
>   * By default the decay is the default pelt decay period.
>   * The decay shift can change the decay period in
>   * multiples of 32.
> -- 
> 2.17.1
> 

Powered by blists - more mailing lists