pegasusq (based on ondemand): cpuidle detection

I found a problem with the ondemand governor while in earlysuspend
suspend mode (ondemand keeping the freq close to the max at all times
despite near 0% load). The problem is that the cpu starts to go in
long cpuidle cycles, a sampling_rate of 10000 (usec) is applied only
once in a while and the real sampling_rate becomes 1 second (or more).

So when a wakeup happens we return to the 10000usec sampling rate. The
ondemand sees lots of activity after the wakeup but those "loads" must
be adjusted down if the previous wall_time delta was huge and the
current one is tiny. We're too close to long cpuidle to worry about
the cpu freq anyway and it may be just a jitter load that if we take
into account without adjusting it down, will lead to the next long
cpuidle to be entered at the max freq again, and this repeats forever.

So my solution is to tweak the ondemand to scale down the "load"
according to the decrease in the wall_time delta ratio
(deep_sleep_ratio variable). This allows the CPU to stay at the lowest
freq during the deep sleeps even when the ondemand governor is enabled
and the sampling_rate is set to 10000. (setting the sampling_rate to
values >100000 would also tend to hide the problem but it'd screw the
interactive behavior by running at the lowest frequency for too long
during interactive usage)

During interactive usage with the screen on (not in earlysuspend
mode), or during playback or voip with screen off the deep_sleep_rate
is set to 1 practically all the time so it won't alter the behavior of
the ondemand governor unless the system is very idle (and in turn when
we want it to stay at low freq).

Change-Id: If0391e6d6c41c1c8c9fa590502e88e681a800b04

Signed-off-by: Andrea Arcangeli <andrea@cpushare.com>
iosched: prevent aliased requests from starving other I/O

Hi, Jens,

If you recall, I posted an RFC patch for this back in July of last year:
http://lkml.org/lkml/2010/7/13/279

The basic problem is that a process can issue a never-ending stream of
async direct I/Os to the same sector on a device, thus starving out
other I/O in the system (due to the way the alias handling works in both
cfq and deadline).  The solution I proposed back then was to start
dispatching from the fifo after a certain number of aliases had been
dispatched.  Vivek asked why we had to treat aliases differently at all,
and I never had a good answer.  So, I put together a simple patch which
allows aliases to be added to the rb tree (it adds them to the right,
though that doesn't matter as the order isn't guaranteed anyway).  I
think this is the preferred solution, as it doesn't break up time slices
in CFQ or batches in deadline.  I've tested it, and it does solve the
starvation issue.  Let me know what you think.

Cheers,
Jeff

Signed-off-by: Jeff Moyer <jmoyer@redhat.com>
Signed-off-by: Jens Axboe <jaxboe@fusionio.com>

Conflicts:
	block/vr-iosched.c
fix derp