-- a/arch/powerpc/platforms/cell/spufs/sched.c

++ b/arch/powerpc/platforms/cell/spufs/sched.c

-- /dev/null

++ b/Documentation/scheduler/sched-BFS.txt

-- a/Documentation/sysctl/kernel.txt

BFS - The Brain Fuck Scheduler by Con Kolivas.

Goals.

The goal of the Brain Fuck Scheduler, referred to as BFS from here on, is to

completely do away with the complex designs of the past for the cpu process

scheduler and instead implement one that is very simple in basic design.

The main focus of BFS is to achieve excellent desktop interactivity and

responsiveness without heuristics and tuning knobs that are difficult to

understand, impossible to model and predict the effect of, and when tuned to

one workload cause massive detriment to another.

Design summary.

BFS is best described as a single runqueue, O(n) lookup, earliest effective

virtual deadline first design, loosely based on EEVDF (earliest eligible virtual

deadline first) and my previous Staircase Deadline scheduler. Each component

shall be described in order to understand the significance of, and reasoning for

it. The codebase when the first stable version was released was approximately

9000 lines less code than the existing mainline linux kernel scheduler (in

2.6.31). This does not even take into account the removal of documentation and

the cgroups code that is not used.

Design reasoning.

The single runqueue refers to the queued but not running processes for the

entire system, regardless of the number of CPUs. The reason for going back to

a single runqueue design is that once multiple runqueues are introduced,

per-CPU or otherwise, there will be complex interactions as each runqueue will

be responsible for the scheduling latency and fairness of the tasks only on its

own runqueue, and to achieve fairness and low latency across multiple CPUs, any

advantage in throughput of having CPU local tasks causes other disadvantages.

This is due to requiring a very complex balancing system to at best achieve some

semblance of fairness across CPUs and can only maintain relatively low latency

for tasks bound to the same CPUs, not across them. To increase said fairness

and latency across CPUs, the advantage of local runqueue locking, which makes

for better scalability, is lost due to having to grab multiple locks.

A significant feature of BFS is that all accounting is done purely based on CPU

used and nowhere is sleep time used in any way to determine entitlement or

interactivity. Interactivity "estimators" that use some kind of sleep/run

algorithm are doomed to fail to detect all interactive tasks, and to falsely tag

tasks that aren't interactive as being so. The reason for this is that it is

close to impossible to determine that when a task is sleeping, whether it is

doing it voluntarily, as in a userspace application waiting for input in the

form of a mouse click or otherwise, or involuntarily, because it is waiting for

another thread, process, I/O, kernel activity or whatever. Thus, such an

estimator will introduce corner cases, and more heuristics will be required to

cope with those corner cases, introducing more corner cases and failed

interactivity detection and so on. Interactivity in BFS is built into the design

by virtue of the fact that tasks that are waking up have not used up their quota

of CPU time, and have earlier effective deadlines, thereby making it very likely

they will preempt any CPU bound task of equivalent nice level. See below for

more information on the virtual deadline mechanism. Even if they do not preempt

a running task, because the rr interval is guaranteed to have a bound upper

limit on how long a task will wait for, it will be scheduled within a timeframe

that will not cause visible interface jitter.

Design details.

Task insertion.

BFS inserts tasks into each relevant queue as an O(1) insertion into a double

linked list. On insertion, *every* running queue is checked to see if the newly

queued task can run on any idle queue, or preempt the lowest running task on the

system. This is how the cross-CPU scheduling of BFS achieves significantly lower

latency per extra CPU the system has. In this case the lookup is, in the worst

case scenario, O(n) where n is the number of CPUs on the system.

Data protection.

BFS has one single lock protecting the process local data of every task in the

global queue. Thus every insertion, removal and modification of task data in the

global runqueue needs to grab the global lock. However, once a task is taken by

a CPU, the CPU has its own local data copy of the running process' accounting

information which only that CPU accesses and modifies (such as during a

timer tick) thus allowing the accounting data to be updated lockless. Once a

CPU has taken a task to run, it removes it from the global queue. Thus the

global queue only ever has, at most,

	(number of tasks requesting cpu time) - (number of logical CPUs) + 1

tasks in the global queue. This value is relevant for the time taken to look up

tasks during scheduling. This will increase if many tasks with CPU affinity set

in their policy to limit which CPUs they're allowed to run on if they outnumber

the number of CPUs. The +1 is because when rescheduling a task, the CPU's

currently running task is put back on the queue. Lookup will be described after

the virtual deadline mechanism is explained.

Virtual deadline.

The key to achieving low latency, scheduling fairness, and "nice level"

distribution in BFS is entirely in the virtual deadline mechanism. The one

tunable in BFS is the rr_interval, or "round robin interval". This is the

maximum time two SCHED_OTHER (or SCHED_NORMAL, the common scheduling policy)

tasks of the same nice level will be running for, or looking at it the other

way around, the longest duration two tasks of the same nice level will be

delayed for. When a task requests cpu time, it is given a quota (time_slice)

equal to the rr_interval and a virtual deadline. The virtual deadline is

offset from the current time in jiffies by this equation:

	jiffies + (prio_ratio * rr_interval)

The prio_ratio is determined as a ratio compared to the baseline of nice -20

and increases by 10% per nice level. The deadline is a virtual one only in that

no guarantee is placed that a task will actually be scheduled by this time, but

it is used to compare which task should go next. There are three components to

how a task is next chosen. First is time_slice expiration. If a task runs out

of its time_slice, it is descheduled, the time_slice is refilled, and the

deadline reset to that formula above. Second is sleep, where a task no longer

is requesting CPU for whatever reason. The time_slice and deadline are _not_

adjusted in this case and are just carried over for when the task is next

scheduled. Third is preemption, and that is when a newly waking task is deemed

higher priority than a currently running task on any cpu by virtue of the fact

that it has an earlier virtual deadline than the currently running task. The

earlier deadline is the key to which task is next chosen for the first and

second cases. Once a task is descheduled, it is put back on the queue, and an

O(n) lookup of all queued-but-not-running tasks is done to determine which has

the earliest deadline and that task is chosen to receive CPU next.

The CPU proportion of different nice tasks works out to be approximately the

	(prio_ratio difference)^2

The reason it is squared is that a task's deadline does not change while it is

running unless it runs out of time_slice. Thus, even if the time actually

passes the deadline of another task that is queued, it will not get CPU time

unless the current running task deschedules, and the time "base" (jiffies) is

constantly moving.

Task lookup.

BFS has 103 priority queues. 100 of these are dedicated to the static priority

of realtime tasks, and the remaining 3 are, in order of best to worst priority,

SCHED_ISO (isochronous), SCHED_NORMAL, and SCHED_IDLEPRIO (idle priority

scheduling). When a task of these priorities is queued, a bitmap of running

priorities is set showing which of these priorities has tasks waiting for CPU

time. When a CPU is made to reschedule, the lookup for the next task to get

CPU time is performed in the following way:

First the bitmap is checked to see what static priority tasks are queued. If

any realtime priorities are found, the corresponding queue is checked and the

first task listed there is taken (provided CPU affinity is suitable) and lookup

is complete. If the priority corresponds to a SCHED_ISO task, they are also

taken in FIFO order (as they behave like SCHED_RR). If the priority corresponds

to either SCHED_NORMAL or SCHED_IDLEPRIO, then the lookup becomes O(n). At this

stage, every task in the runlist that corresponds to that priority is checked

to see which has the earliest set deadline, and (provided it has suitable CPU

affinity) it is taken off the runqueue and given the CPU. If a task has an

expired deadline, it is taken and the rest of the lookup aborted (as they are

chosen in FIFO order).

Thus, the lookup is O(n) in the worst case only, where n is as described

earlier, as tasks may be chosen before the whole task list is looked over.

Scalability.

The major limitations of BFS will be that of scalability, as the separate

runqueue designs will have less lock contention as the number of CPUs rises.

However they do not scale linearly even with separate runqueues as multiple

runqueues will need to be locked concurrently on such designs to be able to

achieve fair CPU balancing, to try and achieve some sort of nice-level fairness

across CPUs, and to achieve low enough latency for tasks on a busy CPU when

other CPUs would be more suited. BFS has the advantage that it requires no

balancing algorithm whatsoever, as balancing occurs by proxy simply because

all CPUs draw off the global runqueue, in priority and deadline order. Despite

the fact that scalability is _not_ the prime concern of BFS, it both shows very

good scalability to smaller numbers of CPUs and is likely a more scalable design

at these numbers of CPUs.

It also has some very low overhead scalability features built into the design

when it has been deemed their overhead is so marginal that they're worth adding.

The first is the local copy of the running process' data to the CPU it's running

on to allow that data to be updated lockless where possible. Then there is

deference paid to the last CPU a task was running on, by trying that CPU first

when looking for an idle CPU to use the next time it's scheduled. Finally there

is the notion of "sticky" tasks that are flagged when they are involuntarily

descheduled, meaning they still want further CPU time. This sticky flag is

used to bias heavily against those tasks being scheduled on a different CPU

unless that CPU would be otherwise idle. When a cpu frequency governor is used

that scales with CPU load, such as ondemand, sticky tasks are not scheduled

on a different CPU at all, preferring instead to go idle. This means the CPU

they were bound to is more likely to increase its speed while the other CPU

will go idle, thus speeding up total task execution time and likely decreasing

power usage. This is the only scenario where BFS will allow a CPU to go idle

in preference to scheduling a task on the earliest available spare CPU.

The real cost of migrating a task from one CPU to another is entirely dependant

on the cache footprint of the task, how cache intensive the task is, how long

it's been running on that CPU to take up the bulk of its cache, how big the CPU

cache is, how fast and how layered the CPU cache is, how fast a context switch

is... and so on. In other words, it's close to random in the real world where we

do more than just one sole workload. The only thing we can be sure of is that

it's not free. So BFS uses the principle that an idle CPU is a wasted CPU and

utilising idle CPUs is more important than cache locality, and cache locality

only plays a part after that.

When choosing an idle CPU for a waking task, the cache locality is determined

according to where the task last ran and then idle CPUs are ranked from best

to worst to choose the most suitable idle CPU based on cache locality, NUMA

node locality and hyperthread sibling business. They are chosen in the

following preference (if idle):

* Same core, idle or busy cache, idle threads

* Other core, same cache, idle or busy cache, idle threads.

* Same node, other CPU, idle cache, idle threads.

* Same node, other CPU, busy cache, idle threads.

* Same core, busy threads.

* Other core, same cache, busy threads.

* Same node, other CPU, busy threads.

* Other node, other CPU, idle cache, idle threads.

* Other node, other CPU, busy cache, idle threads.

* Other node, other CPU, busy threads.

This shows the SMT or "hyperthread" awareness in the design as well which will

choose a real idle core first before a logical SMT sibling which already has

tasks on the physical CPU.

Early benchmarking of BFS suggested scalability dropped off at the 16 CPU mark.

However this benchmarking was performed on an earlier design that was far less

scalable than the current one so it's hard to know how scalable it is in terms

of both CPUs (due to the global runqueue) and heavily loaded machines (due to

O(n) lookup) at this stage. Note that in terms of scalability, the number of

_logical_ CPUs matters, not the number of _physical_ CPUs. Thus, a dual (2x)

quad core (4X) hyperthreaded (2X) machine is effectively a 16X. Newer benchmark

results are very promising indeed, without needing to tweak any knobs, features

or options. Benchmark contributions are most welcome.

Features

As the initial prime target audience for BFS was the average desktop user, it

was designed to not need tweaking, tuning or have features set to obtain benefit

from it. Thus the number of knobs and features has been kept to an absolute

minimum and should not require extra user input for the vast majority of cases.

There are precisely 2 tunables, and 2 extra scheduling policies. The rr_interval

and iso_cpu tunables, and the SCHED_ISO and SCHED_IDLEPRIO policies. In addition

to this, BFS also uses sub-tick accounting. What BFS does _not_ now feature is

support for CGROUPS. The average user should neither need to know what these

are, nor should they need to be using them to have good desktop behaviour.

rr_interval

There is only one "scheduler" tunable, the round robin interval. This can be

accessed in

	/proc/sys/kernel/rr_interval

The value is in milliseconds, and the default value is set to 6ms. Valid values

are from 1 to 1000. Decreasing the value will decrease latencies at the cost of

decreasing throughput, while increasing it will improve throughput, but at the

cost of worsening latencies. The accuracy of the rr interval is limited by HZ

resolution of the kernel configuration. Thus, the worst case latencies are

usually slightly higher than this actual value. BFS uses "dithering" to try and

minimise the effect the Hz limitation has. The default value of 6 is not an

arbitrary one. It is based on the fact that humans can detect jitter at

approximately 7ms, so aiming for much lower latencies is pointless under most

circumstances. It is worth noting this fact when comparing the latency

performance of BFS to other schedulers. Worst case latencies being higher than

7ms are far worse than average latencies not being in the microsecond range.

Experimentation has shown that rr intervals being increased up to 300 can

improve throughput but beyond that, scheduling noise from elsewhere prevents

further demonstrable throughput.

Isochronous scheduling.

Isochronous scheduling is a unique scheduling policy designed to provide

near-real-time performance to unprivileged (ie non-root) users without the

ability to starve the machine indefinitely. Isochronous tasks (which means

"same time") are set using, for example, the schedtool application like so:

	schedtool -I -e amarok

This will start the audio application "amarok" as SCHED_ISO. How SCHED_ISO works

is that it has a priority level between true realtime tasks and SCHED_NORMAL

which would allow them to preempt all normal tasks, in a SCHED_RR fashion (ie,

if multiple SCHED_ISO tasks are running, they purely round robin at rr_interval

rate). However if ISO tasks run for more than a tunable finite amount of time,

they are then demoted back to SCHED_NORMAL scheduling. This finite amount of

time is the percentage of _total CPU_ available across the machine, configurable

as a percentage in the following "resource handling" tunable (as opposed to a

scheduler tunable):

	/proc/sys/kernel/iso_cpu

and is set to 70% by default. It is calculated over a rolling 5 second average

Because it is the total CPU available, it means that on a multi CPU machine, it

is possible to have an ISO task running as realtime scheduling indefinitely on

just one CPU, as the other CPUs will be available. Setting this to 100 is the

equivalent of giving all users SCHED_RR access and setting it to 0 removes the

ability to run any pseudo-realtime tasks.

A feature of BFS is that it detects when an application tries to obtain a

realtime policy (SCHED_RR or SCHED_FIFO) and the caller does not have the

appropriate privileges to use those policies. When it detects this, it will

give the task SCHED_ISO policy instead. Thus it is transparent to the user.

Because some applications constantly set their policy as well as their nice

level, there is potential for them to undo the override specified by the user

on the command line of setting the policy to SCHED_ISO. To counter this, once

a task has been set to SCHED_ISO policy, it needs superuser privileges to set

it back to SCHED_NORMAL. This will ensure the task remains ISO and all child

processes and threads will also inherit the ISO policy.

Idleprio scheduling.

Idleprio scheduling is a scheduling policy designed to give out CPU to a task

_only_ when the CPU would be otherwise idle. The idea behind this is to allow

ultra low priority tasks to be run in the background that have virtually no

effect on the foreground tasks. This is ideally suited to distributed computing

clients (like setiathome, folding, mprime etc) but can also be used to start

a video encode or so on without any slowdown of other tasks. To avoid this

policy from grabbing shared resources and holding them indefinitely, if it

detects a state where the task is waiting on I/O, the machine is about to

suspend to ram and so on, it will transiently schedule them as SCHED_NORMAL. As

per the Isochronous task management, once a task has been scheduled as IDLEPRIO,

it cannot be put back to SCHED_NORMAL without superuser privileges. Tasks can

be set to start as SCHED_IDLEPRIO with the schedtool command like so:

	schedtool -D -e ./mprime

Subtick accounting.

It is surprisingly difficult to get accurate CPU accounting, and in many cases,

the accounting is done by simply determining what is happening at the precise

moment a timer tick fires off. This becomes increasingly inaccurate as the

timer tick frequency (HZ) is lowered. It is possible to create an application

which uses almost 100% CPU, yet by being descheduled at the right time, records

zero CPU usage. While the main problem with this is that there are possible

security implications, it is also difficult to determine how much CPU a task

really does use. BFS tries to use the sub-tick accounting from the TSC clock,

where possible, to determine real CPU usage. This is not entirely reliable, but

is far more likely to produce accurate CPU usage data than the existing designs

and will not show tasks as consuming no CPU usage when they actually are. Thus,

the amount of CPU reported as being used by BFS will more accurately represent

how much CPU the task itself is using (as is shown for example by the 'time'

application), so the reported values may be quite different to other schedulers.

Values reported as the 'load' are more prone to problems with this design, but

per process values are closer to real usage. When comparing throughput of BFS

to other designs, it is important to compare the actual completed work in terms

of total wall clock time taken and total work done, rather than the reported

"cpu usage".

Con Kolivas <kernel@kolivas.org> Tue, 5 Apr 2011

-- a/fs/proc/base.c

++ b/fs/proc/base.c

			(unsigned long long)task->se.sum_exec_runtime,

			(unsigned long long)tsk_seruntime(task),

-- a/include/linux/init_task.h

++ b/include/linux/init_task.h

#endif /* CONFIG_SCHED_BFS */

-- a/include/linux/ioprio.h

++ b/include/linux/ioprio.h

-- a/include/linux/sched.h

++ b/include/linux/sched.h

	int on_rq;

#if defined(CONFIG_SMP) || defined(CONFIG_SCHED_BFS)

	bool on_cpu;

#endif

#ifndef CONFIG_SCHED_BFS

	bool on_rq;

#endif

#ifdef CONFIG_SMP

#if defined(CONFIG_SMP) && !defined(CONFIG_SCHED_BFS)

static inline void set_task_cpu(struct task_struct *p, unsigned int cpu)

static inline void set_task_cpu(struct task_struct *p, int cpu)

-- a/init/Kconfig

++ b/init/Kconfig

	depends on !S390 && !NO_HZ_FULL

	depends on !S390 && !NO_HZ_FULL && !SCHED_BFS

	depends on HAVE_CONTEXT_TRACKING && 64BIT

	depends on HAVE_CONTEXT_TRACKING && 64BIT && !SCHED_BFS

	depends on HAVE_CONTEXT_TRACKING && SMP

	depends on HAVE_CONTEXT_TRACKING && SMP && !SCHED_BFS

	depends on TREE_RCU || TREE_PREEMPT_RCU

	depends on (TREE_RCU || TREE_PREEMPT_RCU) && !SCHED_BFS

	bool "SLUB (Unqueued Allocator)"

	def_bool y

	help

	   SLUB is a slab allocator that minimizes cache line usage

	   instead of managing queues of cached objects (SLAB approach).

	   Per cpu caching is realized using slabs of objects instead

	   of queues of objects. SLUB can use memory efficiently

	   and has enhanced diagnostics. SLUB is the default choice for

	   a slab allocator.

config SLOB

	depends on EXPERT

	bool "SLOB (Simple Allocator)"

	help

	   SLOB replaces the stock allocator with a drastically simpler

	   allocator. SLOB is generally more space efficient but

	   does not perform as well on large systems.

endchoice

-- a/init/main.c

++ b/init/main.c

-- a/kernel/delayacct.c

++ b/kernel/delayacct.c

	t3 = tsk->se.sum_exec_runtime;

	t3 = tsk_seruntime(tsk);

-- a/kernel/exit.c

++ b/kernel/exit.c

		sig->sum_sched_runtime += tsk->se.sum_exec_runtime;

		sig->sum_sched_runtime += tsk_seruntime(tsk);

-- a/kernel/posix-cpu-timers.c

++ b/kernel/posix-cpu-timers.c

	add_device_randomness((const void*) &tsk->se.sum_exec_runtime,

	add_device_randomness((const void*) &tsk_seruntime(tsk),

		       utime, stime, tsk->se.sum_exec_runtime);

		       utime, stime, tsk_seruntime(tsk));

		       tsk->se.sum_exec_runtime + sig->sum_sched_runtime);

		       tsk_seruntime(tsk) + sig->sum_sched_runtime);

		if (!--maxfire || tsk->se.sum_exec_runtime < t->expires.sched) {

		if (!--maxfire || tsk_seruntime(tsk) < t->expires.sched) {

		    tsk->rt.timeout > DIV_ROUND_UP(hard, USEC_PER_SEC/HZ)) {

		    tsk_rttimeout(tsk) > DIV_ROUND_UP(hard, USEC_PER_SEC/HZ)) {

		if (tsk->rt.timeout > DIV_ROUND_UP(soft, USEC_PER_SEC/HZ)) {

		if (tsk_rttimeout(tsk) > DIV_ROUND_UP(soft, USEC_PER_SEC/HZ)) {

			.sum_exec_runtime = tsk->se.sum_exec_runtime

			.sum_exec_runtime = tsk_seruntime(tsk)

-- a/kernel/sysctl.c

++ b/kernel/sysctl.c

static int one_hundred = 100;

static int __maybe_unused one_hundred = 100;

#ifdef CONFIG_SCHED_BFS

extern int rr_interval;

extern int sched_iso_cpu;

static int __read_mostly one_thousand = 1000;

#endif

#ifdef CONFIG_SCHED_DEBUG

#if defined(CONFIG_SCHED_DEBUG) && !defined(CONFIG_SCHED_BFS)

-- a/lib/Kconfig.debug

++ b/lib/Kconfig.debug

	depends on DEBUG_KERNEL

	depends on DEBUG_KERNEL && !SCHED_BFS

-- a/include/linux/jiffies.h

++ b/include/linux/jiffies.h

#define INITIAL_JIFFIES ((unsigned long)(unsigned int) (-300*HZ))

#define INITIAL_JIFFIES ((unsigned long)(unsigned int) (-10*HZ))

-- a/drivers/cpufreq/cpufreq.c

++ b/drivers/cpufreq/cpufreq.c

-- a/drivers/cpufreq/cpufreq_ondemand.c

++ b/drivers/cpufreq/cpufreq_ondemand.c

#define DEF_FREQUENCY_DOWN_DIFFERENTIAL		(10)

#define DEF_FREQUENCY_DOWN_DIFFERENTIAL		(26)

#define DEF_FREQUENCY_UP_THRESHOLD		(80)

#define DEF_FREQUENCY_UP_THRESHOLD		(63)

 * Every sampling_rate, we check, if current idle time is less than 20%

 * Every sampling_rate, we check, if current idle time is less than 37%

 * over 30%. If such a frequency exist, we try to decrease to this frequency.

 * over 63%. If such a frequency exist, we try to decrease to this frequency.

-- /dev/null

++ b/kernel/sched/bfs.c

-- a/include/uapi/linux/sched.h

/*

 *  kernel/sched/bfs.c, was kernel/sched.c

 *

 *  Kernel scheduler and related syscalls

 *

 *  Copyright (C) 1991-2002  Linus Torvalds

 *

 *  1996-12-23  Modified by Dave Grothe to fix bugs in semaphores and

 *		make semaphores SMP safe

 *  1998-11-19	Implemented schedule_timeout() and related stuff

 *		by Andrea Arcangeli

 *  2002-01-04	New ultra-scalable O(1) scheduler by Ingo Molnar:

 *		hybrid priority-list and round-robin design with

 *		an array-switch method of distributing timeslices

 *		and per-CPU runqueues.  Cleanups and useful suggestions

 *		by Davide Libenzi, preemptible kernel bits by Robert Love.

 *  2003-09-03	Interactivity tuning by Con Kolivas.

 *  2004-04-02	Scheduler domains code by Nick Piggin

 *  2007-04-15  Work begun on replacing all interactivity tuning with a

 *              fair scheduling design by Con Kolivas.

 *  2007-05-05  Load balancing (smp-nice) and other improvements

 *              by Peter Williams

 *  2007-05-06  Interactivity improvements to CFS by Mike Galbraith

 *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri

 *  2007-11-29  RT balancing improvements by Steven Rostedt, Gregory Haskins,

 *              Thomas Gleixner, Mike Kravetz

 *  now		Brainfuck deadline scheduling policy by Con Kolivas deletes

 *              a whole lot of those previous things.

 */

#include <linux/mm.h>

#include <linux/module.h>

#include <linux/nmi.h>

#include <linux/init.h>

#include <asm/uaccess.h>

#include <linux/highmem.h>

#include <asm/mmu_context.h>

#include <linux/interrupt.h>

#include <linux/capability.h>

#include <linux/completion.h>

#include <linux/kernel_stat.h>

#include <linux/debug_locks.h>

#include <linux/perf_event.h>

#include <linux/security.h>

#include <linux/notifier.h>

#include <linux/profile.h>

#include <linux/freezer.h>

#include <linux/vmalloc.h>

#include <linux/blkdev.h>

#include <linux/delay.h>

#include <linux/smp.h>

#include <linux/threads.h>

#include <linux/timer.h>

#include <linux/rcupdate.h>

#include <linux/cpu.h>

#include <linux/cpuset.h>

#include <linux/cpumask.h>

#include <linux/percpu.h>

#include <linux/proc_fs.h>

#include <linux/seq_file.h>

#include <linux/syscalls.h>

#include <linux/times.h>

#include <linux/tsacct_kern.h>

#include <linux/kprobes.h>

#include <linux/delayacct.h>

#include <linux/log2.h>

#include <linux/bootmem.h>

#include <linux/ftrace.h>

#include <linux/slab.h>

#include <linux/init_task.h>

#include <linux/binfmts.h>

#include <linux/context_tracking.h>

#include <asm/switch_to.h>

#include <asm/tlb.h>

#include <asm/unistd.h>

#include <asm/mutex.h>

#ifdef CONFIG_PARAVIRT

#include <asm/paravirt.h>

#endif

#include "cpupri.h"

#include "../workqueue_internal.h"

#include "../smpboot.h"

#define CREATE_TRACE_POINTS

#include <trace/events/sched.h>

#include "bfs_sched.h"

#define rt_prio(prio)		unlikely((prio) < MAX_RT_PRIO)

#define rt_task(p)		rt_prio((p)->prio)

#define rt_queue(rq)		rt_prio((rq)->rq_prio)

#define batch_task(p)		(unlikely((p)->policy == SCHED_BATCH))

#define is_rt_policy(policy)	((policy) == SCHED_FIFO || \

					(policy) == SCHED_RR)

#define has_rt_policy(p)	unlikely(is_rt_policy((p)->policy))

#define idleprio_task(p)	unlikely((p)->policy == SCHED_IDLEPRIO)

#define iso_task(p)		unlikely((p)->policy == SCHED_ISO)

#define iso_queue(rq)		unlikely((rq)->rq_policy == SCHED_ISO)

#define rq_running_iso(rq)	((rq)->rq_prio == ISO_PRIO)

#define ISO_PERIOD		((5 * HZ * grq.noc) + 1)

/*

 * Convert user-nice values [ -20 ... 0 ... 19 ]

 * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],

 * and back.

 */

#define NICE_TO_PRIO(nice)	(MAX_RT_PRIO + (nice) + 20)

#define PRIO_TO_NICE(prio)	((prio) - MAX_RT_PRIO - 20)

#define TASK_NICE(p)		PRIO_TO_NICE((p)->static_prio)

/*

 * 'User priority' is the nice value converted to something we

 * can work with better when scaling various scheduler parameters,

 * it's a [ 0 ... 39 ] range.

 */

#define USER_PRIO(p)		((p) - MAX_RT_PRIO)

#define TASK_USER_PRIO(p)	USER_PRIO((p)->static_prio)

#define MAX_USER_PRIO		(USER_PRIO(MAX_PRIO))

#define SCHED_PRIO(p)		((p) + MAX_RT_PRIO)

#define STOP_PRIO		(MAX_RT_PRIO - 1)

/*

 * Some helpers for converting to/from various scales. Use shifts to get

 * approximate multiples of ten for less overhead.

 */

#define JIFFIES_TO_NS(TIME)	((TIME) * (1000000000 / HZ))

#define JIFFY_NS		(1000000000 / HZ)

#define HALF_JIFFY_NS		(1000000000 / HZ / 2)

#define HALF_JIFFY_US		(1000000 / HZ / 2)

#define MS_TO_NS(TIME)		((TIME) << 20)

#define MS_TO_US(TIME)		((TIME) << 10)

#define NS_TO_MS(TIME)		((TIME) >> 20)

#define NS_TO_US(TIME)		((TIME) >> 10)

#define RESCHED_US	(100) /* Reschedule if less than this many μs left */

void print_scheduler_version(void)

{

	printk(KERN_INFO "BFS CPU scheduler v0.442 by Con Kolivas.\n");

}

/*

 * This is the time all tasks within the same priority round robin.

 * Value is in ms and set to a minimum of 6ms. Scales with number of cpus.

 * Tunable via /proc interface.

 */

int rr_interval __read_mostly = 6;

/*

 * sched_iso_cpu - sysctl which determines the cpu percentage SCHED_ISO tasks

 * are allowed to run five seconds as real time tasks. This is the total over

 * all online cpus.

 */

int sched_iso_cpu __read_mostly = 70;

/*

 * The relative length of deadline for each priority(nice) level.

 */

static int prio_ratios[PRIO_RANGE] __read_mostly;

/*

 * The quota handed out to tasks of all priority levels when refilling their

 * time_slice.

 */

static inline int timeslice(void)

{

	return MS_TO_US(rr_interval);

}

/*

 * The global runqueue data that all CPUs work off. Data is protected either

 * by the global grq lock, or the discrete lock that precedes the data in this

 * struct.

 */

struct global_rq {

	raw_spinlock_t lock;

	unsigned long nr_running;

	unsigned long nr_uninterruptible;

	unsigned long long nr_switches;

	struct list_head queue[PRIO_LIMIT];

	DECLARE_BITMAP(prio_bitmap, PRIO_LIMIT + 1);

#ifdef CONFIG_SMP

	unsigned long qnr; /* queued not running */

	cpumask_t cpu_idle_map;

	bool idle_cpus;

#endif

	int noc; /* num_online_cpus stored and updated when it changes */

	u64 niffies; /* Nanosecond jiffies */

	unsigned long last_jiffy; /* Last jiffy we updated niffies */

	raw_spinlock_t iso_lock;

	int iso_ticks;

	bool iso_refractory;

};

#ifdef CONFIG_SMP

/*

 * We add the notion of a root-domain which will be used to define per-domain

 * variables. Each exclusive cpuset essentially defines an island domain by

 * fully partitioning the member cpus from any other cpuset. Whenever a new

 * exclusive cpuset is created, we also create and attach a new root-domain

 * object.

 *

 */

struct root_domain {

	atomic_t refcount;

	atomic_t rto_count;

	struct rcu_head rcu;

	cpumask_var_t span;

	cpumask_var_t online;

	/*

	 * The "RT overload" flag: it gets set if a CPU has more than

	 * one runnable RT task.

	 */

	cpumask_var_t rto_mask;

	struct cpupri cpupri;

};

/*

 * By default the system creates a single root-domain with all cpus as

 * members (mimicking the global state we have today).

 */

static struct root_domain def_root_domain;

#endif /* CONFIG_SMP */

/* There can be only one */

static struct global_rq grq;

DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

static DEFINE_MUTEX(sched_hotcpu_mutex);

#ifdef CONFIG_SMP

struct rq *cpu_rq(int cpu)

{

	return &per_cpu(runqueues, (cpu));

}

#define this_rq()		(&__get_cpu_var(runqueues))

#define task_rq(p)		cpu_rq(task_cpu(p))

#define cpu_curr(cpu)		(cpu_rq(cpu)->curr)

/*

 * sched_domains_mutex serialises calls to init_sched_domains,

 * detach_destroy_domains and partition_sched_domains.

 */

static DEFINE_MUTEX(sched_domains_mutex);

/*

 * By default the system creates a single root-domain with all cpus as

 * members (mimicking the global state we have today).

 */

static struct root_domain def_root_domain;

int __weak arch_sd_sibling_asym_packing(void)

{

       return 0*SD_ASYM_PACKING;

}

#endif /* CONFIG_SMP */

static inline void update_rq_clock(struct rq *rq);

/*

 * Sanity check should sched_clock return bogus values. We make sure it does

 * not appear to go backwards, and use jiffies to determine the maximum and

 * minimum it could possibly have increased, and round down to the nearest

 * jiffy when it falls outside this.

 */

static inline void niffy_diff(s64 *niff_diff, int jiff_diff)

{

	unsigned long min_diff, max_diff;

	if (jiff_diff > 1)

		min_diff = JIFFIES_TO_NS(jiff_diff - 1);

	else

		min_diff = 1;

	/*  Round up to the nearest tick for maximum */

	max_diff = JIFFIES_TO_NS(jiff_diff + 1);

	if (unlikely(*niff_diff < min_diff || *niff_diff > max_diff))

		*niff_diff = min_diff;

}

#ifdef CONFIG_SMP

static inline int cpu_of(struct rq *rq)

{

	return rq->cpu;

}

/*

 * Niffies are a globally increasing nanosecond counter. Whenever a runqueue

 * clock is updated with the grq.lock held, it is an opportunity to update the

 * niffies value. Any CPU can update it by adding how much its clock has

 * increased since it last updated niffies, minus any added niffies by other

 * CPUs.

 */

static inline void update_clocks(struct rq *rq)

{

	s64 ndiff;

	long jdiff;

	update_rq_clock(rq);

	ndiff = rq->clock - rq->old_clock;

	/* old_clock is only updated when we are updating niffies */

	rq->old_clock = rq->clock;

	ndiff -= grq.niffies - rq->last_niffy;

	jdiff = jiffies - grq.last_jiffy;

	niffy_diff(&ndiff, jdiff);

	grq.last_jiffy += jdiff;

	grq.niffies += ndiff;

	rq->last_niffy = grq.niffies;

}

#else /* CONFIG_SMP */

static struct rq *uprq;

#define cpu_rq(cpu)	(uprq)

#define this_rq()	(uprq)

#define task_rq(p)	(uprq)

#define cpu_curr(cpu)	((uprq)->curr)

static inline int cpu_of(struct rq *rq)

{

	return 0;

}

static inline void update_clocks(struct rq *rq)

{

	s64 ndiff;

	long jdiff;

	update_rq_clock(rq);

	ndiff = rq->clock - rq->old_clock;

	rq->old_clock = rq->clock;

	jdiff = jiffies - grq.last_jiffy;

	niffy_diff(&ndiff, jdiff);

	grq.last_jiffy += jdiff;

	grq.niffies += ndiff;

}

#endif

#define raw_rq()	(&__raw_get_cpu_var(runqueues))

#include "stats.h"

#ifndef prepare_arch_switch

# define prepare_arch_switch(next)	do { } while (0)

#endif

#ifndef finish_arch_switch

# define finish_arch_switch(prev)	do { } while (0)

#endif

#ifndef finish_arch_post_lock_switch

# define finish_arch_post_lock_switch()	do { } while (0)

#endif

/*

 * All common locking functions performed on grq.lock. rq->clock is local to

 * the CPU accessing it so it can be modified just with interrupts disabled

 * when we're not updating niffies.

 * Looking up task_rq must be done under grq.lock to be safe.

 */

static void update_rq_clock_task(struct rq *rq, s64 delta);

static inline void update_rq_clock(struct rq *rq)

{

	s64 delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;

	rq->clock += delta;

	update_rq_clock_task(rq, delta);

}

static inline bool task_running(struct task_struct *p)

{

	return p->on_cpu;

}

static inline void grq_lock(void)

	__acquires(grq.lock)

{

	raw_spin_lock(&grq.lock);

}

static inline void grq_unlock(void)

	__releases(grq.lock)

{

	raw_spin_unlock(&grq.lock);

}

static inline void grq_lock_irq(void)

	__acquires(grq.lock)

{

	raw_spin_lock_irq(&grq.lock);

}

static inline void time_lock_grq(struct rq *rq)

	__acquires(grq.lock)

{

	grq_lock();

	update_clocks(rq);

}

static inline void grq_unlock_irq(void)

	__releases(grq.lock)

{

	raw_spin_unlock_irq(&grq.lock);

}

static inline void grq_lock_irqsave(unsigned long *flags)

	__acquires(grq.lock)

{

	raw_spin_lock_irqsave(&grq.lock, *flags);

}

static inline void grq_unlock_irqrestore(unsigned long *flags)

	__releases(grq.lock)

{

	raw_spin_unlock_irqrestore(&grq.lock, *flags);

}

static inline struct rq

*task_grq_lock(struct task_struct *p, unsigned long *flags)

	__acquires(grq.lock)

{

	grq_lock_irqsave(flags);

	return task_rq(p);

}

static inline struct rq

*time_task_grq_lock(struct task_struct *p, unsigned long *flags)

	__acquires(grq.lock)

{

	struct rq *rq = task_grq_lock(p, flags);

	update_clocks(rq);

	return rq;

}

static inline struct rq *task_grq_lock_irq(struct task_struct *p)

	__acquires(grq.lock)

{

	grq_lock_irq();

	return task_rq(p);

}

static inline void time_task_grq_lock_irq(struct task_struct *p)

	__acquires(grq.lock)

{

	struct rq *rq = task_grq_lock_irq(p);

	update_clocks(rq);

}

static inline void task_grq_unlock_irq(void)

	__releases(grq.lock)

{

	grq_unlock_irq();

}

static inline void task_grq_unlock(unsigned long *flags)

	__releases(grq.lock)

{

	grq_unlock_irqrestore(flags);

}

/**

 * grunqueue_is_locked

 *

 * Returns true if the global runqueue is locked.

 * This interface allows printk to be called with the runqueue lock

 * held and know whether or not it is OK to wake up the klogd.

 */

bool grunqueue_is_locked(void)

{

	return raw_spin_is_locked(&grq.lock);

}

void grq_unlock_wait(void)

	__releases(grq.lock)

{

	smp_mb(); /* spin-unlock-wait is not a full memory barrier */

	raw_spin_unlock_wait(&grq.lock);

}

static inline void time_grq_lock(struct rq *rq, unsigned long *flags)

	__acquires(grq.lock)

{

	local_irq_save(*flags);

	time_lock_grq(rq);

}

static inline struct rq *__task_grq_lock(struct task_struct *p)

	__acquires(grq.lock)

{

	grq_lock();

	return task_rq(p);

}

static inline void __task_grq_unlock(void)

	__releases(grq.lock)

{

	grq_unlock();

}

/*

 * Look for any tasks *anywhere* that are running nice 0 or better. We do

 * this lockless for overhead reasons since the occasional wrong result

 * is harmless.

 */

bool above_background_load(void)

{

	int cpu;

	for_each_online_cpu(cpu) {

		struct task_struct *cpu_curr = cpu_rq(cpu)->curr;

		if (unlikely(!cpu_curr))

			continue;

		if (PRIO_TO_NICE(cpu_curr->static_prio) < 1) {

			return true;

		}

	}

	return false;

}

#ifndef __ARCH_WANT_UNLOCKED_CTXSW

static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)

{

}

static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)

{

#ifdef CONFIG_DEBUG_SPINLOCK

	/* this is a valid case when another task releases the spinlock */

	grq.lock.owner = current;

#endif

	/*

	 * If we are tracking spinlock dependencies then we have to

	 * fix up the runqueue lock - which gets 'carried over' from

	 * prev into current:

	 */

	spin_acquire(&grq.lock.dep_map, 0, 0, _THIS_IP_);

	grq_unlock_irq();

}

#else /* __ARCH_WANT_UNLOCKED_CTXSW */

static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)

{

#ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW

	grq_unlock_irq();

#else

	grq_unlock();

#endif

}

static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)

{

	smp_wmb();

#ifndef __ARCH_WANT_INTERRUPTS_ON_CTXSW

	local_irq_enable();

#endif

}

#endif /* __ARCH_WANT_UNLOCKED_CTXSW */

static inline bool deadline_before(u64 deadline, u64 time)

{

	return (deadline < time);

}

static inline bool deadline_after(u64 deadline, u64 time)

{

	return (deadline > time);

}

/*

 * A task that is queued but not running will be on the grq run list.

 * A task that is not running or queued will not be on the grq run list.

 * A task that is currently running will have ->on_cpu set but not on the

 * grq run list.

 */

static inline bool task_queued(struct task_struct *p)

{

	return (!list_empty(&p->run_list));

}

/*

 * Removing from the global runqueue. Enter with grq locked.

 */

static void dequeue_task(struct task_struct *p)

{

	list_del_init(&p->run_list);

	if (list_empty(grq.queue + p->prio))

		__clear_bit(p->prio, grq.prio_bitmap);

}

/*

 * To determine if it's safe for a task of SCHED_IDLEPRIO to actually run as

 * an idle task, we ensure none of the following conditions are met.

 */

static bool idleprio_suitable(struct task_struct *p)

{

	return (!freezing(p) && !signal_pending(p) &&

		!(task_contributes_to_load(p)) && !(p->flags & (PF_EXITING)));

}

/*

 * To determine if a task of SCHED_ISO can run in pseudo-realtime, we check

 * that the iso_refractory flag is not set.

 */

static bool isoprio_suitable(void)

{

	return !grq.iso_refractory;

}

/*

 * Adding to the global runqueue. Enter with grq locked.

 */

static void enqueue_task(struct task_struct *p)

{

	if (!rt_task(p)) {

		/* Check it hasn't gotten rt from PI */

		if ((idleprio_task(p) && idleprio_suitable(p)) ||

		   (iso_task(p) && isoprio_suitable()))

			p->prio = p->normal_prio;

		else

			p->prio = NORMAL_PRIO;

	}

	__set_bit(p->prio, grq.prio_bitmap);

	list_add_tail(&p->run_list, grq.queue + p->prio);

	sched_info_queued(p);

}

/* Only idle task does this as a real time task*/

static inline void enqueue_task_head(struct task_struct *p)

{

	__set_bit(p->prio, grq.prio_bitmap);

	list_add(&p->run_list, grq.queue + p->prio);

	sched_info_queued(p);

}

static inline void requeue_task(struct task_struct *p)

{

	sched_info_queued(p);

}

/*

 * Returns the relative length of deadline all compared to the shortest