Preparing for introduction of intelli_plug: update scheduler and mutex code.

Porting last patches from
https://github.com/faux123/htc-m7/commits/kk_mr1_GE/kernel/sched/core.c
(Jan 04, 2014)
and
https://github.com/faux123/moto_x/commits/kk_mr1_pub/kernel/sched/core.c
(Feb 12, 2014)

----------
scheduler: compute time-average nr_running per run-queue

Compute the time-average number of running tasks per run-queue for a
trailing window of a fixed time period. The detla add/sub to the
average value is weighted by the amount of time per nr_running value
relative to the total measurement period.

https://github.com/faux123/htc-m7/commit/28a88f1dc2f4dd745981cd394655b673b28b7a00

----------
scheduler: Re-compute time-average nr_running on read

Re-compute time-average nr_running when it is read. This would
prevent reading stalled average value if there were no run-queue
changes for a long time. New average value is returned to the reader,
but not stored to avoid concurrent writes. Light-weight sequential
counter synchronization is used to assure data consistency for
re-computing average.

https://github.com/faux123/htc-m7/commit/3dc726471fc7f7434f79e460c1e054fd9504e9d6

----------
mutex: Queue mutex spinners with MCS lock to reduce cacheline contention

The current mutex spinning code (with MUTEX_SPIN_ON_OWNER option turned
on) allow multiple tasks to spin on a single mutex concurrently. A
potential problem with the current approach is that when the mutex
becomes available, all the spinning tasks will try to acquire the
mutex more or less simultaneously. As a result, there will be a lot of
cacheline bouncing especially on systems with a large number of CPUs.

This patch tries to reduce this kind of contention by putting the
mutex spinners into a queue so that only the first one in the queue
will try to acquire the mutex. This will reduce contention and allow
all the tasks to move forward faster.

The queuing of mutex spinners is done using an MCS lock based
implementation which will further reduce contention on the mutex
cacheline than a similar ticket spinlock based implementation. This
patch will add a new field into the mutex data structure for holding
the MCS lock. This expands the mutex size by 8 bytes for 64-bit system
and 4 bytes for 32-bit system. This overhead will be avoid if the
MUTEX_SPIN_ON_OWNER option is turned off.

https://github.com/faux123/htc-m7/commit/b6cab60dbd24a0864348907acea8ae09d8df43a1

----------
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.

So, save pointer to first SD while running the iteration loop over tl's.

https://github.com/faux123/moto_x/commit/35e4182af1c130bbda9a4ac055c2a9c039287821

----------
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.

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.

https://github.com/faux123/moto_x/commit/4a0b943f51022029db67e19c993381ea3fdabcc0

----------
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.

https://github.com/faux123/moto_x/commit/c240acfd414a136c9eb339569ae59d39fa42d0b7

----------
sched: Use cached value of span instead of calling sched_domain_span()

In the beginning of build_sched_groups() we called sched_domain_span()
and
cached its return value in span. Few statements later we are calling it
again to
get the same pointer.

Lets use the cached value instead as it hasn't changed in between.

https://github.com/faux123/moto_x/commit/653be0170e58858fd9da6f46ede1b75ee449f41c

----------
sched: don't call get_group() for covered cpus

In build_sched_groups() we don't need to call get_group() for cpus which
are
already covered in previous iterations. So, call get_group() after
checking if
cpu is covered or not.

https://github.com/faux123/moto_x/commit/f1c67cfcdb097b1034643c638b1edd296737ee6c

----------
sched: remove WARN_ON(!sd) from init_sched_groups_power()

sd can't be NULL in init_sched_groups_power() and so checking it for
NULL isn't
useful. In case it is required, then also we need to rearrange the code
a bit as
we already accessed invalid pointer sd to get sg: sg = sd->groups.

https://github.com/faux123/moto_x/commit/6dd7d04c792ae883f36e5dffed0bde3df9a233a0

----------
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.

https://github.com/faux123/moto_x/commit/2b0ff53b6b1580af58e759b2162e68344ddd2b98

----------
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.

https://github.com/faux123/moto_x/commit/92ddc5baad81b16fbef4ea39b1bc9ac482a86f31

----------
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.

https://github.com/faux123/moto_x/commit/8da8770e58f8b1158c7b270d69212d0d219a17d3

----------
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.

https://github.com/faux123/moto_x/commit/6b15a2c548018491e7fa143034f8d7dad7a33855