cpuidle: Quickly notice prediction failure for repeat mode

The prediction for future is difficult and when the cpuidle governor prediction
fails and govenor possibly choose the shallower C-state than it should. How to
quickly notice and find the failure becomes important for power saving.

cpuidle menu governor has a method to predict the repeat pattern if there are 8
C-states residency which are continuous and the same or very close, so it will
predict the next C-states residency will keep same residency time.

There is a real case that turbostat utility (tools/power/x86/turbostat)
at kernel 3.3 or early. turbostat utility will read 10 registers one by one at
Sandybridge, so it will generate 10 IPIs to wake up idle CPUs. So cpuidle menu
 governor will predict it is repeat mode and there is another IPI wake up idle
 CPU soon, so it keeps idle CPU stay at C1 state even though CPU is totally
idle. However, in the turbostat, following 10 registers reading is sleep 5
seconds by default, so the idle CPU will keep at C1 for a long time though it is
 idle until break event occurs.
In a idle Sandybridge system, run "./turbostat -v", we will notice that deep
C-state dangles between "70% ~ 99%". After patched the kernel, we will notice
deep C-state stays at >99.98%.

In the patch, a timer is added when menu governor detects a repeat mode and
choose a shallow C-state. The timer is set to a time out value that greater
than predicted time, and we conclude repeat mode prediction failure if timer is
triggered. When repeat mode happens as expected, the timer is not triggered
and CPU waken up from C-states and it will cancel the timer initiatively.
When repeat mode does not happen, the timer will be time out and menu governor
will quickly notice that the repeat mode prediction fails and then re-evaluates
deeper C-states possibility.

Below is another case which will clearly show the patch much benefit:

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <signal.h>
#include <sys/time.h>
#include <time.h>
#include <pthread.h>

volatile int * shutdown;
volatile long * count;
int delay = 20;
int loop = 8;

void usage(void)
{
	fprintf(stderr,
		"Usage: idle_predict [options]\n"
		"  --help	-h  Print this help\n"
		"  --thread	-n  Thread number\n"
		"  --loop     	-l  Loop times in shallow Cstate\n"
		"  --delay	-t  Sleep time (uS)in shallow Cstate\n");
}

void *simple_loop() {
	int idle_num = 1;
	while (!(*shutdown)) {
		*count = *count + 1;

		if (idle_num % loop)
			usleep(delay);
		else {
			/* sleep 1 second */
			usleep(1000000);
			idle_num = 0;
		}
		idle_num++;
	}

}

static void sighand(int sig)
{
	*shutdown = 1;
}

int main(int argc, char *argv[])
{
	sigset_t sigset;
	int signum = SIGALRM;
	int i, c, er = 0, thread_num = 8;
	pthread_t pt[1024];

	static char optstr[] = "n:l:t:h:";

	while ((c = getopt(argc, argv, optstr)) != EOF)
		switch (c) {
			case 'n':
				thread_num = atoi(optarg);
				break;
			case 'l':
				loop = atoi(optarg);
				break;
			case 't':
				delay = atoi(optarg);
				break;
			case 'h':
			default:
				usage();
				exit(1);
		}

	printf("thread=%d,loop=%d,delay=%d\n",thread_num,loop,delay);
	count = malloc(sizeof(long));
	shutdown = malloc(sizeof(int));
	*count = 0;
	*shutdown = 0;

	sigemptyset(&sigset);
	sigaddset(&sigset, signum);
	sigprocmask (SIG_BLOCK, &sigset, NULL);
	signal(SIGINT, sighand);
	signal(SIGTERM, sighand);

	for(i = 0; i < thread_num ; i++)
		pthread_create(&pt[i], NULL, simple_loop, NULL);

	for (i = 0; i < thread_num; i++)
		pthread_join(pt[i], NULL);

	exit(0);
}

Get powertop V2 from git://github.com/fenrus75/powertop, build powertop.
After build the above test application, then run it.
Test plaform can be Intel Sandybridge or other recent platforms.
#./idle_predict -l 10 &
#./powertop

We will find that deep C-state will dangle between 40%~100% and much time spent
on C1 state. It is because menu governor wrongly predict that repeat mode
is kept, so it will choose the C1 shallow C-state even though it has chance to
sleep 1 second in deep C-state.

While after patched the kernel, we find that deep C-state will keep >99.6%.

Signed-off-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Youquan Song <youquan.song@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
cpuidle: Quickly notice prediction failure in general case

The prediction for future is difficult and when the cpuidle governor prediction
fails and govenor possibly choose the shallower C-state than it should. How to
quickly notice and find the failure becomes important for power saving.

The patch extends to general case that prediction logic get a small predicted
residency, so it choose a shallow C-state though the expected residency is large
. Once the prediction will be fail, the CPU will keep staying at shallow C-state
for a long time. Acutally, the CPU has change enter into deep C-state.
So when the expected residency is long enough but governor choose a shallow
C-state, an timer will be added in order to monitor if the prediction failure.

When C-state is waken up prior to the adding timer, the timer will be cancelled
initiatively. When the timer is triggered and menu governor will quickly notice
prediction failure and re-evaluates deeper C-states possibility.

Signed-off-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Youquan Song <youquan.song@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
cpuidle: Set residency to 0 if target Cstate not enter

When cpuidle governor choose a C-state to enter for idle CPU, but it notice that
there is tasks request to be executed. So the idle CPU will not really enter
the target C-state and go to run task.

In this situation, it will use the residency of previous really entered target
C-states. Obviously, it is not reasonable.

So, this patch fix it by set the target C-state residency to 0.

Signed-off-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Youquan Song <youquan.song@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
cpuidle: Get typical recent sleep interval

The function detect_repeating_patterns was not very useful for
workloads with alternating long and short pauses, for example
virtual machines handling network requests for each other (say
a web and database server).

Instead, try to find a recent sleep interval that is somewhere
between the median and the mode sleep time, by discarding outliers
to the up side and recalculating the average and standard deviation
until that is no longer required.

This should do something sane with a sleep interval series like:

	200 180 210 10000 30 1000 170 200

The current code would simply discard such a series, while the
new code will guess a typical sleep interval just shy of 200.

The original patch come from Rik van Riel <riel@redhat.com>.

Signed-off-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Youquan Song <youquan.song@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
PM / OPP: predictable fail results for opp_find* functions, v2

Currently the opp_find* functions return -ENODEV when:
a) it cant find a device (e.g. request for an OPP search on device
   which was not registered)
b) When it cant find a match for the search strategy used

This makes life a little in-efficient for users such as devfreq
to make reasonable judgement before switching search strategies.

So, standardize the return results as following:
 -EINVAL for bad pointer parameters
 -ENODEV when device cannot be found
 -ERANGE when search fails

This has the following benefit for devfreq implementation:
The search fails when an unregistered device pointer is provided.
This is a trigger to change the search direction and search for
a better fit, however, if we cannot differentiate between a valid
search range failure Vs an unregistered device, second search goes
through the same fail return condition. This can be avoided by
appropriate handling of error return code.

With this change, we also fix devfreq for the improved search
strategy with updated error code.

Signed-off-by: Nishanth Menon <nm@ti.com>
Reviewed-by: Kevin Hilman <khilman@ti.com>
Acked-by: MyungJoo Ham <myungjoo.ham@samsung.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
cpufreq: fix jiffies/cputime mixup in conservative/ondemand governors

The function get_cpu_idle_time_jiffy in both the conservative and
ondemand governors use jiffies_to_usecs to convert a cputime value to
usecs which gives the wrong value on architectures where cputime and
jiffies use different units.  Only matters if NO_HZ is disabled, since
otherwise get_cpu_idle_time_us should already return a valid value, and
get_cpu_idle_time_jiffy isn't actually called.

Signed-off-by: Andreas Schwab <schwab@linux-m68k.org>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Merge branch 'pm-cpufreq-next' into linux-next

* pm-cpufreq-next:
  cpufreq: fix jiffies/cputime mixup in conservative/ondemand governors
  cpufreq: Improve debug prints
  cpufreq: Move common part from governors to separate file, v2
  cpufreq / core: Fix printing of governor and driver name
  cpufreq / core: Fix typo in comment describing show_bios_limit()
Merge branch 'pm-cpuidle-next' into linux-next

* pm-cpuidle-next:
  cpuidle: Get typical recent sleep interval
  cpuidle: Set residency to 0 if target Cstate not enter
  cpuidle: Quickly notice prediction failure in general case
  cpuidle: Quickly notice prediction failure for repeat mode
  cpuidle / sysfs: move kobj initialization in the syfs file
  cpuidle / sysfs: change function parameter
Merge branch 'pm-devfreq-next' into linux-next

* pm-devfreq-next:
  PM / devfreq: make devfreq_class static
  PM / devfreq: fix sscanf handling for writable sysfs entries
  PM / devfreq: kernel-doc typo corrections
  PM / devfreq: Add current freq callback in device profile
  PM / devfreq: Add suspend and resume apis
  PM / devfreq: Core updates to support devices which can idle
Merge branch 'pm-opp-next' into linux-next

* pm-opp-next:
  PM / OPP: predictable fail results for opp_find* functions, v2
  PM / OPP: Export symbols for module usage.
  PM / OPP: RCU reclaim
Merge branch 'pm-runtime-next' into linux-next

* pm-runtime-next:
  base: power - use clk_prepare_enable and clk_prepare_disable
Merge branch 'pm-sleep-next' into linux-next

* pm-sleep-next:
  PM / Hibernate: use rb_entry
  PM / sysfs: replace strict_str* with kstrto*
Merge branch 'acpi-next' into linux-next

* acpi-next:
  ACPI / PM: Fix device PM kernedoc comments and #ifdefs
  ACPI: move acpi_no_s4_hw_signature() declaration into #ifdef CONFIG_HIBERNATION
  ACPI / Sleep: add acpi_sleep=nonvs_s3 parameter
  ACPI: Remove unused lockable in acpi_device_flags
  ACPI: Fix stale pointer access to flags.lockable
  ACPI: Fix a hard coding style when determining if a device is a container.
  ACPI / x86: Add quirk for "CheckPoint P-20-00" to not use bridge _CRS_ info
  ACPI / processor: prevent cpu from becoming online
  ACPI: strict_strtoul() and printk() cleanup in acpi_pad
  ACPI: dock: Remove redundant ACPI NS walk
  ACPI / EC: Don't count a SCI interrupt as a false one
  ACPI: Remove the useless check in osl.c
  ACPI / EC: Add more debug info and trivial code cleanup
  ACPI / EC: Cleanup the member name for spinlock/mutex in struct