linux.git/kernel/irq/timings.c, branch v5.9

genirq/timings: Add selftest for next event computation

2019-06-12T08:47:05+00:00

The circular buffers are now validated with selftests. The next interrupt
index algorithm which is the hardest part to validate needs extra coverage.

Add a selftest which uses the intervals stored in the arrays and insert all
the values except the last one. The next event computation must return the
same value as the last element which was not inserted.

Signed-off-by: Daniel Lezcano 
Signed-off-by: Thomas Gleixner 
Cc: andriy.shevchenko@linux.intel.com
Link: https://lkml.kernel.org/r/20190527205521.12091-9-daniel.lezcano@linaro.org

genirq/timings: Add selftest for irqs circular buffer

2019-06-12T08:47:05+00:00

After testing the per cpu interrupt circular event, make sure the per
interrupt circular buffer usage is correct.

Add tests to validate the interrupt circular buffer.

Signed-off-by: Daniel Lezcano 
Signed-off-by: Thomas Gleixner 
Cc: andriy.shevchenko@linux.intel.com
Link: https://lkml.kernel.org/r/20190527205521.12091-8-daniel.lezcano@linaro.org

genirq/timings: Add selftest for circular array

2019-06-12T08:47:04+00:00

Due to the complexity of the code and the difficulty to debug it, add some
selftests to the framework in order to spot issues or regression at boot
time when the runtime testing is enabled for this subsystem.

This tests the circular buffer at the limits and validates:
 - the encoding / decoding of the values
 - the macro to browse the irq timings circular buffer
 - the function to push data in the circular buffer

Signed-off-by: Daniel Lezcano 
Signed-off-by: Thomas Gleixner 
Cc: andriy.shevchenko@linux.intel.com
Link: https://lkml.kernel.org/r/20190527205521.12091-7-daniel.lezcano@linaro.org

genirq/timings: Encapsulate storing function

2019-06-12T08:47:04+00:00

For the next patches providing the selftest, it is required to insert
interval values directly in the buffer in order to check the correctness of
the code. Encapsulate the code doing that in a always inline function in
order to reuse it in the test code.

No functional changes.

Signed-off-by: Daniel Lezcano 
Signed-off-by: Thomas Gleixner 
Cc: andriy.shevchenko@linux.intel.com
Link: https://lkml.kernel.org/r/20190527205521.12091-6-daniel.lezcano@linaro.org

genirq/timings: Optimize the period detection speed

2019-06-12T08:47:03+00:00

With a minimal period and if there is a period which is a multiple of it
but lesser than the max period then it will be detected before and the
minimal period will be never reached.

 1 2 1 2 1 2 1 2 1 2 1 2
 <-----> <-----> <----->
 <-> <-> <-> <-> <-> <->

In that case, the minimum period is 2 and the maximum period is 5. That
means all repeating pattern of 2 will be detected as repeating pattern of
4, it is pointless to go up to 2 when searching for the period as it will
always fail.

Remove one loop iteration by increasing the minimal period to 3.

Signed-off-by: Daniel Lezcano 
Signed-off-by: Thomas Gleixner 
Cc: andriy.shevchenko@linux.intel.com
Link: https://lkml.kernel.org/r/20190527205521.12091-4-daniel.lezcano@linaro.org

genirq/timings: Fix timings buffer inspection

2019-06-12T08:47:03+00:00

It appears the index beginning computation is not correct, the current
code does:

     i = (irqts->count & IRQ_TIMINGS_MASK) - 1

If irqts->count is equal to zero, we end up with an index equal to -1,
but that does not happen because the function checks against zero
before and returns in such case.

However, if irqts->count is a multiple of IRQ_TIMINGS_SIZE, the
resulting & bit op will be zero and leads also to a -1 index.

Re-introduce the iteration loop belonging to the previous variance
code which was correct.

Fixes: bbba0e7c5cda "genirq/timings: Add array suffix computation code"
Signed-off-by: Daniel Lezcano 
Signed-off-by: Thomas Gleixner 
Cc: andriy.shevchenko@linux.intel.com
Link: https://lkml.kernel.org/r/20190527205521.12091-3-daniel.lezcano@linaro.org

genirq/timings: Fix next event index function

2019-06-12T08:47:03+00:00

The current code is luckily working with most of the interval samples
testing but actually it fails to correctly detect pattern repetition
breaking at the end of the buffer.

Narrowing down the bug has been a real pain because of the pointers,
so the routine is rewrittne by using indexes instead.

Fixes: bbba0e7c5cda "genirq/timings: Add array suffix computation code"
Signed-off-by: Daniel Lezcano 
Signed-off-by: Thomas Gleixner 
Cc: andriy.shevchenko@linux.intel.com
Link: https://lkml.kernel.org/r/20190527205521.12091-2-daniel.lezcano@linaro.org

genirq/timings: Add array suffix computation code

2019-04-05T20:51:29+00:00

The previous approach based on the variance was discarding values from
the timings when they were considered as anomalies as stated by the
normal law statistical model.

However in the interrupt life, there can be multiple anomalies due to the
nature of the device generating the interrupts, and most of the time a
repeating pattern can be observed, that is particulary true for network,
console, MMC or SSD devices.

The variance approach missed the patterns and it was only able to deal with
the interrupt coming in regular intervals, thus reducing considerably the
scope of what is predictable.

In order to find out the repeating patterns, the interrupt intervals are
grouped in a ilog2 basis to create a suite of numbers with small
amplitude. Every group contains an exponential moving average of the values
belonging to the group. The array suffix, a data structure used for string
searching, data compression, etc ..., is built from the suite of numbers
and the suffixes are then searched in this suite.

The tests showed the algorithm is able to find all repeating patterns,
as well as regular interval in less than 1us on x86-i7.

Signed-off-by: Daniel Lezcano 
Signed-off-by: Thomas Gleixner 
Cc: rjw@rjwysocki.net
Cc: ulf.hansson@linaro.org
Cc: linux-pm@vger.kernel.org
Link: https://lkml.kernel.org/r/20190328151336.5316-2-daniel.lezcano@linaro.org

genirq/timings: Remove variance computation code

2019-04-05T20:51:29+00:00

The variance computation did not provide the expected results and will be
replaced with a different approach to compute the next interrupt based on
the array suffixes derived algorithm.

There is no good way to transform the variance code to the new algorithm,
so for ease of review remove the existing code first.

Signed-off-by: Daniel Lezcano 
Signed-off-by: Thomas Gleixner 
Cc: rjw@rjwysocki.net
Cc: ulf.hansson@linaro.org
Cc: linux-pm@vger.kernel.org
Link: https://lkml.kernel.org/r/20190328151336.5316-1-daniel.lezcano@linaro.org

genirq: Remove license boilerplate/references

2018-03-20T13:23:28+00:00

Now that SPDX identifiers are in place, remove the boilerplate or
references.

The change in timings.c has been acked by the author.

Signed-off-by: Thomas Gleixner 
Acked-by: Daniel Lezcano 
Cc: Kate Stewart 
Cc: Greg Kroah-Hartman 
Cc: Philippe Ombredanne 
Link: https://lkml.kernel.org/r/20180314212030.668321222@linutronix.de