sched: make __update_entity_runnable_avg() fast

__update_entity_runnable_avg forms the core of maintaining an entity's runnable
load average.  In this function we charge the accumulated run-time since last
update and handle appropriate decay.  In some cases, e.g. a waking task, this
time interval may be much larger than our period unit.

Fortunately we can exploit some properties of our series to perform decay for a
blocked update in constant time and account the contribution for a running
update in essentially-constant* time.

[*]: For any running entity they should be performing updates at the tick which
gives us a soft limit of 1 jiffy between updates, and we can compute up to a
32 jiffy update in a single pass.

C program to generate the above:

#include <math.h>
#include <stdio.h>

#define N 32
#define WMULT_SHIFT 32

const long WMULT_CONST = ((1UL << N) - 1);
double y;

long runnable_avg_yN_inv[N];
void calc_mult_inv() {
	int i;
	double yn = 0;

	printf("inverses\n");
	for (i = 0; i < N; i++) {
		yn = (double)WMULT_CONST * pow(y, i);
		runnable_avg_yN_inv[i] = yn;
		printf("%2d: 0x%8lx\n", i, runnable_avg_yN_inv[i]);
	}
	printf("\n");
}

long mult_inv(long c, int n) {
	return (c * runnable_avg_yN_inv[n]) >> WMULT_SHIFT;
}

void calc_yn_sum(int n)
{
	int i;
	double sum = 0, sum_fl = 0, diff = 0;

	/*
	 * We take the floored sum to ensure the sum of partial sums is never
	 * larger than the actual sum.
	 */
	printf("sum y^n\n");
	printf("   %8s  %8s %8s\n", "exact", "floor", "error");
	for (i = 1; i <= n; i++) {
		sum = (y * sum + y * 1024);
		sum_fl = floor(y * sum_fl+ y * 1024);
		printf("%2d: %8.0f  %8.0f %8.0f\n", i, sum, sum_fl,
			sum_fl - sum);
	}
	printf("\n");
}

void calc_conv(long n) {
	long old_n;
	int i = -1;

	printf("convergence (LOAD_AVG_MAX, LOAD_AVG_MAX_N)\n");
	do {
		old_n = n;
		n = mult_inv(n, 1) + 1024;
		i++;
	} while (n != old_n);
	printf("%d> %ld\n", i - 1, n);
	printf("\n");
}

void main() {
	y = pow(0.5, 1/(double)N);
	calc_mult_inv();
	calc_conv(1024);
	calc_yn_sum(N);
}

[ Compile with -lm ]
Signed-off-by: Paul Turner <pjt@google.com>
Reviewed-by: Ben Segall <bsegall@google.com>