genirq/timings: Optimize the period detection speed

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
mi

genirq/timings: Optimize the period detection speed

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 <daniel.lezcano@linaro.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Cc: andriy.shevchenko@linux.intel.com
Link: https://lkml.kernel.org/r/20190527205521.12091-4-daniel.lezcano@linaro.org

show more ...

genirq/timings: Fix timings buffer inspection

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

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

If irqts->count is eq

genirq/timings: Fix timings buffer inspection

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 <daniel.lezcano@linaro.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Cc: andriy.shevchenko@linux.intel.com
Link: https://lkml.kernel.org/r/20190527205521.12091-3-daniel.lezcano@linaro.org

show more ...

genirq/timings: Fix next event index function

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

genirq/timings: Fix next event index function

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 <daniel.lezcano@linaro.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Cc: andriy.shevchenko@linux.intel.com
Link: https://lkml.kernel.org/r/20190527205521.12091-2-daniel.lezcano@linaro.org

show more ...

Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux

Merge drm/drm-next into drm-intel-next-queued

Get the HDR dependencies originally merged via drm-misc. Sync up all
i915 changes applied via other trees. And get v5.2-rc2 as the baseline.

Signed-off

Merge drm/drm-next into drm-intel-next-queued

Get the HDR dependencies originally merged via drm-misc. Sync up all
i915 changes applied via other trees. And get v5.2-rc2 as the baseline.

Signed-off-by: Jani Nikula <jani.nikula@intel.com>

show more ...

Merge drm/drm-next into drm-misc-next

Backmerging 5.2-rc1 to -misc-next for robher

Signed-off-by: Sean Paul <seanpaul@chromium.org>

Merge branch 'fixes-dra7' into fixes

Merge tag 'v5.2-rc1' of https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux into fbdev-for-next

Linux 5.2-rc1

Sync with upstream (which now contains fbdev-v5.2 changes) to
prepare a base

Merge tag 'v5.2-rc1' of https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux into fbdev-for-next

Linux 5.2-rc1

Sync with upstream (which now contains fbdev-v5.2 changes) to
prepare a base for fbdev-v5.3 changes.

show more ...

Merge tag 'v5.2-rc1' into spi-5.3

Linux 5.2-rc1

Merge tag 'v5.2-rc1' into regulator-5.3

Linux 5.2-rc1

Merge tag 'v5.2-rc1' into asoc-5.3

Linux 5.2-rc1

Merge branch 'linus' into core/urgent, to merge in dependent changes

Signed-off-by: Ingo Molnar <mingo@kernel.org>

Merge branch 'irq-core-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip

Pull irq updates from Ingo Molnar:
"The changes in this cycle were:

- Remove the irq timings/variance

Merge branch 'irq-core-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip

Pull irq updates from Ingo Molnar:
"The changes in this cycle were:

- Remove the irq timings/variance statistics code that tried to
predict when the next interrupt would occur, which didn't work out
as hoped and is replaced by another mechanism.

- This new mechanism is the 'array suffix computation' estimate,
which is superior to the previous one as it can detect not just a
single periodic pattern, but independent periodic patterns along a
log-2 scale of bucketing and exponential moving average. The
comments are longer than the code - and it works better at
predicting various complex interrupt patterns from real-world
devices than the previous estimate.

- avoid IRQ-work self-IPIs on the local CPU

- fix work-list corruption in irq_set_affinity_notifier()"

* 'irq-core-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip:
irq_work: Do not raise an IPI when queueing work on the local CPU
genirq/devres: Use struct_size() in devm_kzalloc()
genirq/timings: Add array suffix computation code
genirq/timings: Remove variance computation code
genirq: Prevent use-after-free and work list corruption

show more ...

genirq/timings: Add array suffix computation code

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

genirq/timings: Add array suffix computation code

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 <daniel.lezcano@linaro.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
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

show more ...

genirq/timings: Remove variance computation code

The variance computation did not provide the expected results and will be
replaced with a different approach to compute the next interrupt based on
t

genirq/timings: Remove variance computation code

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 <daniel.lezcano@linaro.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
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

show more ...

Merge branch 'next' into for-linus

Prepare input updates for 4.18 merge window.

Merge branches 'clk-warn', 'clk-core', 'clk-spear' and 'clk-qcom-msm8998' into clk-next

* clk-warn:
clk: Print the clock name and warning cause

* clk-core:
clk: Remove clk_init_cb typedef

* cl

Merge branches 'clk-warn', 'clk-core', 'clk-spear' and 'clk-qcom-msm8998' into clk-next

* clk-warn:
clk: Print the clock name and warning cause

* clk-core:
clk: Remove clk_init_cb typedef

* clk-spear:
clk: spear: fix WDT clock definition on SPEAr600

* clk-qcom-msm8998:
clk: qcom: Add MSM8998 Global Clock Control (GCC) driver

show more ...

Merge tag 'v4.17-rc6' into next

Sync up with mainline to bring in Atmel controller changes for Caroline.

Merge branch 'drm-intel-next-queued' into gvt-next

Signed-off-by: Zhi Wang <zhi.a.wang@intel.com>

Merge remote-tracking branch 'drm/drm-next' into drm-misc-next

drm-misc-next is still based on v4.16-rc7, and was getting a bit stale.

Signed-off-by: Maarten Lankhorst <maarten.lankhorst@linux.inte

Merge remote-tracking branch 'drm/drm-next' into drm-misc-next

drm-misc-next is still based on v4.16-rc7, and was getting a bit stale.

Signed-off-by: Maarten Lankhorst <maarten.lankhorst@linux.intel.com>

show more ...

Merge drm/drm-next into drm-intel-next-queued

Need d224985a5e31 ("sched/wait, drivers/drm: Convert wait_on_atomic_t()
usage to the new wait_var_event() API") in dinq to be able to fix
https://bugs.f

Merge drm/drm-next into drm-intel-next-queued

Need d224985a5e31 ("sched/wait, drivers/drm: Convert wait_on_atomic_t()
usage to the new wait_var_event() API") in dinq to be able to fix
https://bugs.freedesktop.org/show_bug.cgi?id=106085.

Signed-off-by: Jani Nikula <jani.nikula@intel.com>

show more ...

Merge tag 'v4.17-rc3' into apparmor-next

Linux v4.17-rc3

Merge in v4.17 for LSM updates

Signed-off-by: John Johansen <john.johansen@canonical.com>

Merge tag 'v4.17-rc2' of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux into fbdev-for-next

Linux 4.17-rc2

Merge tag 'v4.17-rc2' into next-general

Sync to Linux 4.17-rc2 for developers.

Back merge 'drm-intel-fixes' into gvt-fixes

Need for 4.17-rc1

Signed-off-by: Zhenyu Wang <zhenyuw@linux.intel.com>