sched: cpu_power: enable ARCH_POWER

Heteregeneous ARM platform uses arch_scale_freq_power function to reflect the relative capacity of each core
sched: Guarantee new group-entities always have weight

Currently, group entity load-weights are initialized to zero. This admits some races with respect to the first time they are re-weighted in earlty use. ( Let g[x] denote the se for "g" on cpu "x". )

Suppose that we have root->a and that a enters a throttled state, immediately followed by a[0]->t1 (the only task running on cpu[0]) blocking:

  put_prev_task(group_cfs_rq(a[0]), t1)
  put_prev_entity(..., t1)
  check_cfs_rq_runtime(group_cfs_rq(a[0]))
  throttle_cfs_rq(group_cfs_rq(a[0]))

Then, before unthrottling occurs, let a[0]->b[0]->t2 wake for the first time:

  enqueue_task_fair(rq[0], t2)
  enqueue_entity(group_cfs_rq(b[0]), t2)
  enqueue_entity_load_avg(group_cfs_rq(b[0]), t2)
  account_entity_enqueue(group_cfs_ra(b[0]), t2)
  update_cfs_shares(group_cfs_rq(b[0]))
  < skipped because b is part of a throttled hierarchy >
  enqueue_entity(group_cfs_rq(a[0]), b[0])
  ...

We now have b[0] enqueued, yet group_cfs_rq(a[0])->load.weight == 0 which violates invariants in several code-paths. Eliminate the possibility of this by initializing group entity weight.
sched: Fix select_idle_sibling() bouncing cow syndrome

If the previous CPU is cache affine and idle, select it.

The current implementation simply traverses the sd_llc domain, taking the first idle CPU encountered, which walks buddy pairs hand in hand over the package, inflicting excruciating pain.

1 tbench pair (worst case) in a 10 core + SMT package:

  pre   15.22 MB/sec 1 procs
  post 252.01 MB/sec 1 procs
sched: Implement smarter wake-affine logic

The wake-affine scheduler feature is currently always trying to pull the wakee close to the waker. In theory this should be beneficial if the waker's CPU caches hot data for the wakee, and it's also beneficial in the extreme ping-pong high context switch rate case.

Testing shows it can benefit hackbench up to 15%.

However, the feature is somewhat blind, from which some workloads such as pgbench suffer. It's also time-consuming algorithmically.

Testing shows it can damage pgbench up to 50% - far more than the benefit it brings in the best case.

So wake-affine should be smarter and it should realize when to stop its thankless effort at trying to find a suitable CPU to wake on.

This patch introduces 'wakee_flips', which will be increased each time the task flips (switches) its wakee target.

So a high 'wakee_flips' value means the task has more than one wakee, and the bigger the number, the higher the wakeup frequency.

Now when making the decision on whether to pull or not, pay attention to the wakee with a high 'wakee_flips', pulling such a task may benefit the wakee. Also imply that the waker will face cruel competition later, it could be very cruel or very fast depends on the story behind 'wakee_flips', waker therefore suffers.

Furthermore, if waker also has a high 'wakee_flips', that implies that multiple tasks rely on it, then waker's higher latency will damage all of them, so pulling wakee seems to be a bad deal.

Thus, when 'waker->wakee_flips / wakee->wakee_flips' becomes higher and higher, the cost of pulling seems to be worse and worse.

The patch therefore helps the wake-affine feature to stop its pulling work when:

	wakee->wakee_flips > factor &&
	waker->wakee_flips > (factor * wakee->wakee_flips)

The 'factor' here is the number of CPUs in the current CPU's NUMA node, so a bigger node will lead to more pulling since the trial becomes more severe.

After applying the patch, pgbench shows up to 40% improvements and no regressions.

Tested with 12 cpu x86 server and tip 3.10.0-rc7.

The percentages in the final column highlight the areas with the biggest wins, all other areas improved as well:

	pgbench		    base	smart

	| db_size | clients |  tps  |	|  tps  |
	+---------+---------+-------+   +-------+
	| 22 MB   |       1 | 10598 |   | 10796 |
	| 22 MB   |       2 | 21257 |   | 21336 |
	| 22 MB   |       4 | 41386 |   | 41622 |
	| 22 MB   |       8 | 51253 |   | 57932 |
	| 22 MB   |      12 | 48570 |   | 54000 |
	| 22 MB   |      16 | 46748 |   | 55982 | +19.75%
	| 22 MB   |      24 | 44346 |   | 55847 | +25.93%
	| 22 MB   |      32 | 43460 |   | 54614 | +25.66%
	| 7484 MB |       1 |  8951 |   |  9193 |
	| 7484 MB |       2 | 19233 |   | 19240 |
	| 7484 MB |       4 | 37239 |   | 37302 |
	| 7484 MB |       8 | 46087 |   | 50018 |
	| 7484 MB |      12 | 42054 |   | 48763 |
	| 7484 MB |      16 | 40765 |   | 51633 | +26.66%
	| 7484 MB |      24 | 37651 |   | 52377 | +39.11%
	| 7484 MB |      32 | 37056 |   | 51108 | +37.92%
	| 15 GB   |       1 |  8845 |   |  9104 |
	| 15 GB   |       2 | 19094 |   | 19162 |
	| 15 GB   |       4 | 36979 |   | 36983 |
	| 15 GB   |       8 | 46087 |   | 49977 |
	| 15 GB   |      12 | 41901 |   | 48591 |
	| 15 GB   |      16 | 40147 |   | 50651 | +26.16%
	| 15 GB   |      24 | 37250 |   | 52365 | +40.58%
	| 15 GB   |      32 | 36470 |   | 50015 | +37.14%
sched: Micro-optimize the smart wake-affine logic

Smart wake-affine is using node-size as the factor currently, but the overhead of the mask operation is high.

Thus, this patch introduce the 'sd_llc_size' percpu variable, which will record the highest cache-share domain size, and make it to be the new factor, in order to reduce the overhead and make it more reasonable.
sched: Reduce overestimating rq->avg_idle

When updating avg_idle, if the delta exceeds some max value, then avg_idle gets set to the max, regardless of what the previous avg was. This can cause avg_idle to often be overestimated.

This patch modifies the way we update avg_idle by always updating it with the function call to update_avg() first. Then, if avg_idle exceeds the max, we set it to the max.
sched: Consider max cost of idle balance per sched domain

In this patch, we keep track of the max cost we spend doing idle load balancing for each sched domain. If the avg time the CPU remains idle is less then the time we have already spent on idle balancing + the max cost of idle balancing in the sched domain, then we don't continue to attempt the balance. We also keep a per rq variable, max_idle_balance_cost, which keeps track of the max time spent on newidle load balances throughout all its domains. Additionally, we swap sched_migration_cost used in idle_balance for rq->max_idle_balance_cost.

By using the max, we avoid overrunning the average. This further reduces the chance we attempt balancing when the CPU is not idle for longer than the cost to balance.

I also limited the max cost of each domain to 5*sysctl_sched_migration_cost as a way to prevent the max from becoming too inflated.
sched: Periodically decay max cost of idle balance

This RFC patch builds on patch 2 and periodically decays that max value to do idle balancing per sched domain.

Though we want to decay it fairly consistently, we may not want to lower it by too much each time, especially since avg_idle is capped based on that value. So I thought that decaying the value every second and lowering it by half a percent each time appeared to be fairly reasonable.

This change would allow us to remove the limit we set on each domain's max cost to idle balance. Also, since the max can be reduced now, we now have to update rq->max_idle balance_cost more frequently. So after every idle balance, we loop through the sched domain to find the max sd's newidle load balance cost for any one domain. Then we will set rq->max_idle_balance_cost to that value.

Since we are now decaying the max cost to do idle balancing, that max cost can also become not high enough. One possible explanation for why is that besides the time spent on each newidle load balance, there are other costs  associated with attempting idle balancing. Idle balance also releases and reacquires a spin lock. That cost is not counted when we keep track of each domain's cost to do newidle load balance. Also, acquiring the rq locks can potentially prevent other CPUs from running something useful. And after migrating tasks, it might potentially have to pay the costs of cache misses and refreshing tasks' cache.

Because of that, this patch also compares avg_idle with max cost to do idle balancing + sched_migration_cost. While using the max cost helps reduce overestimating the average idle, the sched_migration_cost can help account for those additional costs of idle balancing.
sched: change load balance number to h_nr_running of run queue

Since rq->nr_running would include both migration and rt task, it is not reasonable to seek to move nr_running number of task in the load_balance function, since it only apply to cfs type.

Change it to cfs's h_nr_running, which could well present the task number in current cfs queue.
sched: change cpu_avg_load_per_task using h_nr_running

Since cpu_avg_load_per_task is used only by cfs scheduler, its meaning should present the average cfs type task load in the current run queue. Thus we change it to h_nr_running for well presenting its meaning.
sched: change pick_next_task_fair to h_nr_running

Since pick_next_task_fair only want to ensure there is some task in the run queue to be picked up, it should use the h_nr_running instead of nr_running, since nr_running cannot present all tasks if group existed.
sched: change update_sg_lb_stats to h_nr_running

Since update_sg_lb_stats is used to calculate sched_group load difference of cfs type task, it should use h_nr_running instead of nr_running of rq.
sched: change find_busiest_queue to h_nr_running

Since find_busiest_queue try to avoid do load balance for runqueue which has only one cfs task and its load is above the imbalance value calculated, we should use h_nr_running of cfs instead of nr_running of rq.
sched: change active_load_balance_cpu_stop to use h_nr_running

We should only avoid do the active load balance when there is no cfs type task. If just use rq->nr_running, it is possible for the source cpu has multiple rt task, while zero cfs task, so that it would confuse the active load balance function that try to move, but find no task it could move.
sched: document the difference between nr_running and h_nr_running
sched: Optimize build_sched_domains() for saving first SD node for a cpu

We are saving first scheduling domain for a cpu in build_sched_domains() by iterating over the nested sd->child list. We don't actually need to do it this way.

*per_cpu_ptr(d.sd, i) is guaranteed to be NULL in the beginning as we have called __visit_domain_allocation_hell() which does a memset to zero for struct s_data.

tl will be equal to sched_domain_topology for the first iteration and so we can set *per_cpu_ptr(d.sd, i) based on that.

So, save pointer to first SD while running the iteration loop over tl's.
sched: Remove unused params of build_sched_domain()

build_sched_domain() never uses parameter struct s_data *d and so passing it is useless. Remove it.