timers: Implement the hierarchical pull model

Placing timers at enqueue time on a target CPU based on dubious heuristics
does not make any sense:

1) Most timer wheel timers are canceled or rearmed

timers: Implement the hierarchical pull model

Placing timers at enqueue time on a target CPU based on dubious heuristics
does not make any sense:

1) Most timer wheel timers are canceled or rearmed before they expire.

2) The heuristics to predict which CPU will be busy when the timer expires
are wrong by definition.

So placing the timers at enqueue wastes precious cycles.

The proper solution to this problem is to always queue the timers on the
local CPU and allow the non pinned timers to be pulled onto a busy CPU at
expiry time.

Therefore split the timer storage into local pinned and global timers:
Local pinned timers are always expired on the CPU on which they have been
queued. Global timers can be expired on any CPU.

As long as a CPU is busy it expires both local and global timers. When a
CPU goes idle it arms for the first expiring local timer. If the first
expiring pinned (local) timer is before the first expiring movable timer,
then no action is required because the CPU will wake up before the first
movable timer expires. If the first expiring movable timer is before the
first expiring pinned (local) timer, then this timer is queued into an idle
timerqueue and eventually expired by another active CPU.

To avoid global locking the timerqueues are implemented as a hierarchy. The
lowest level of the hierarchy holds the CPUs. The CPUs are associated to
groups of 8, which are separated per node. If more than one CPU group
exist, then a second level in the hierarchy collects the groups. Depending
on the size of the system more than 2 levels are required. Each group has a
"migrator" which checks the timerqueue during the tick for remote expirable
timers.

If the last CPU in a group goes idle it reports the first expiring event in
the group up to the next group(s) in the hierarchy. If the last CPU goes
idle it arms its timer for the first system wide expiring timer to ensure
that no timer event is missed.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Reviewed-by: Frederic Weisbecker <frederic@kernel.org>
Link: https://lore.kernel.org/r/20240222103710.32582-1-anna-maria@linutronix.de

show more ...

Merge branch 'next' into for-linus

Prepare input updates for 5.17 merge window.

Merge tag 'v5.15' into next

Sync up with the mainline to get the latest APIs and DT bindings.

Merge branch 'for-5.15-printk-index' into for-linus

Merge branch 'perf/urgent' into perf/core, to pick up fixes

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

Merge tag 'v5.14-rc6' into locking/core, to pick up fixes

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

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

Required bump from v5.13-rc3 to v5.14-rc3, and to pick up sysfb compilation fixes.

Signed-off-by: Maarten Lankhorst <maarten.lankh

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

Required bump from v5.13-rc3 to v5.14-rc3, and to pick up sysfb compilation fixes.

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

show more ...

Merge drm/drm-next into drm-intel-gt-next

Catching up with 5.14-rc1 and also preparing for a
needed common topic branch for the "Minor revid/stepping
and workaround cleanup"

Reference: https://patc

Merge drm/drm-next into drm-intel-gt-next

Catching up with 5.14-rc1 and also preparing for a
needed common topic branch for the "Minor revid/stepping
and workaround cleanup"

Reference: https://patchwork.freedesktop.org/series/92299/
Signed-off-by: Rodrigo Vivi <rodrigo.vivi@intel.com>

show more ...

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

Catching up with 5.14-rc1

Signed-off-by: Rodrigo Vivi <rodrigo.vivi@intel.com>

Merge branch 'fixes-v5.14' into fixes

Merge branch 'cpufreq/cppc-fie' into cpufreq/arm/linux-next

Merge remote-tracking branch 'torvalds/master' into perf/core

To pick up fixes.

Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>

Merge tag 'timers-core-2021-06-29' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip

Pull timer updates from Thomas Gleixner:
"Time and clocksource/clockevent related updates:

Core change

Merge tag 'timers-core-2021-06-29' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip

Pull timer updates from Thomas Gleixner:
"Time and clocksource/clockevent related updates:

Core changes:

- Infrastructure to support per CPU "broadcast" devices for per CPU
clockevent devices which stop in deep idle states. This allows us
to utilize the more efficient architected timer on certain ARM SoCs
for normal operation instead of permanentely using the slow to
access SoC specific clockevent device.

- Print the name of the broadcast/wakeup device in /proc/timer_list

- Make the clocksource watchdog more robust against delays between
reading the current active clocksource and the watchdog
clocksource. Such delays can be caused by NMIs, SMIs and vCPU
preemption.

Handle this by reading the watchdog clocksource twice, i.e. before
and after reading the current active clocksource. In case that the
two watchdog reads shows an excessive time delta, the read sequence
is repeated up to 3 times.

- Improve the debug output and add a test module for the watchdog
mechanism.

- Reimplementation of the venerable time64_to_tm() function with a
faster and significantly smaller version. Straight from the source,
i.e. the author of the related research paper contributed this!

Driver changes:

- No new drivers, not even new device tree bindings!

- Fixes, improvements and cleanups and all over the place"

* tag 'timers-core-2021-06-29' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip: (30 commits)
time/kunit: Add missing MODULE_LICENSE()
time: Improve performance of time64_to_tm()
clockevents: Use list_move() instead of list_del()/list_add()
clocksource: Print deviation in nanoseconds when a clocksource becomes unstable
clocksource: Provide kernel module to test clocksource watchdog
clocksource: Reduce clocksource-skew threshold
clocksource: Limit number of CPUs checked for clock synchronization
clocksource: Check per-CPU clock synchronization when marked unstable
clocksource: Retry clock read if long delays detected
clockevents: Add missing parameter documentation
clocksource/drivers/timer-ti-dm: Drop unnecessary restore
clocksource/arm_arch_timer: Improve Allwinner A64 timer workaround
clocksource/drivers/arm_global_timer: Remove duplicated argument in arm_global_timer
clocksource/drivers/arm_global_timer: Make symbol 'gt_clk_rate_change_nb' static
arm: zynq: don't disable CONFIG_ARM_GLOBAL_TIMER due to CONFIG_CPU_FREQ anymore
clocksource/drivers/arm_global_timer: Implement rate compensation whenever source clock changes
clocksource/drivers/ingenic: Rename unreasonable array names
clocksource/drivers/timer-ti-dm: Save and restore timer TIOCP_CFG
clocksource/drivers/mediatek: Ack and disable interrupts on suspend
clocksource/drivers/samsung_pwm: Constify source IO memory
...

show more ...

time: Improve performance of time64_to_tm()

The current implementation of time64_to_tm() contains unnecessary loops,
branches and look-up tables. The new one uses an arithmetic-based algorithm
appea

time: Improve performance of time64_to_tm()

The current implementation of time64_to_tm() contains unnecessary loops,
branches and look-up tables. The new one uses an arithmetic-based algorithm
appeared in [1] and is approximately 3x faster (YMMV).

The drawback is that the new code isn't intuitive and contains many 'magic
numbers' (not unusual for this type of algorithm). However, [1] justifies
all those numbers and, given this function's history, the code is unlikely
to need much maintenance, if any at all.

Add a KUnit test for it which checks every day in a 160,000 years interval
centered at 1970-01-01 against the expected result.

[1] Neri, Schneider, "Euclidean Affine Functions and Applications to
Calendar Algorithms". https://arxiv.org/abs/2102.06959

Signed-off-by: Cassio Neri <cassio.neri@gmail.com>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Link: https://lore.kernel.org/r/20210622213616.313046-1-cassio.neri@gmail.com

show more ...

clocksource: Provide kernel module to test clocksource watchdog

When the clocksource watchdog marks a clock as unstable, this might
be due to that clock being unstable or it might be due to delays t

clocksource: Provide kernel module to test clocksource watchdog

When the clocksource watchdog marks a clock as unstable, this might
be due to that clock being unstable or it might be due to delays that
happen to occur between the reads of the two clocks. It would be good
to have a way of testing the clocksource watchdog's ability to
distinguish between these two causes of clock skew and instability.

Therefore, provide a new clocksource-wdtest module selected by a new
TEST_CLOCKSOURCE_WATCHDOG Kconfig option. This module has a single module
parameter named "holdoff" that provides the number of seconds of delay
before testing should start, which defaults to zero when built as a module
and to 10 seconds when built directly into the kernel. Very large systems
that boot slowly may need to increase the value of this module parameter.

This module uses hand-crafted clocksource structures to do its testing,
thus avoiding messing up timing for the rest of the kernel and for user
applications. This module first verifies that the ->uncertainty_margin
field of the clocksource structures are set sanely. It then tests the
delay-detection capability of the clocksource watchdog, increasing the
number of consecutive delays injected, first provoking console messages
complaining about the delays and finally forcing a clock-skew event.
Unexpected test results cause at least one WARN_ON_ONCE() console splat.
If there are no splats, the test has passed. Finally, it fuzzes the
value returned from a clocksource to test the clocksource watchdog's
ability to detect time skew.

This module checks the state of its clocksource after each test, and
uses WARN_ON_ONCE() to emit a console splat if there are any failures.
This should enable all types of test frameworks to detect any such
failures.

This facility is intended for diagnostic use only, and should be avoided
on production systems.

Reported-by: Chris Mason <clm@fb.com>
Suggested-by: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Tested-by: Feng Tang <feng.tang@intel.com>
Link: https://lore.kernel.org/r/20210527190124.440372-5-paulmck@kernel.org

show more ...

Merge remote-tracking branch 'net/master'

Merge branch 'next' into for-linus

Prepare input updates for 5.12 merge window.

Merge tag 'v5.11' into next

Merge with mainline to get latest APIs and device tree bindings.

Merge tag 'amba-make-remove-return-void' of https://git.pengutronix.de/git/ukl/linux into devel-stable

Tag for adaptions to struct amba_driver::remove changing prototype

Merge branch 'cpuidle-fix' into fixes

Merge drm/drm-next into drm-intel-gt-next

Backmerging to get a common base for merging topic branches between
drm-intel-next and drm-intel-gt-next.

Signed-off-by: Joonas Lahtinen <joonas.lahtinen@l

Merge drm/drm-next into drm-intel-gt-next

Backmerging to get a common base for merging topic branches between
drm-intel-next and drm-intel-gt-next.

Signed-off-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>

show more ...

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

sync-up to not fall too much behind.

Signed-off-by: Rodrigo Vivi <rodrigo.vivi@intel.com>

Merge branch 'for-linus' into for-next

Back-merge of 5.11-devel branch for syncing the result changes.

Signed-off-by: Takashi Iwai <tiwai@suse.de>

Merge tag 'asoc-fix-v5.11-rc2' of https://git.kernel.org/pub/scm/linux/kernel/git/broonie/sound into for-linus

ASoC: Fixes for v5.11

A collection of mostly driver specific fixes, plus a maintainers

Merge tag 'asoc-fix-v5.11-rc2' of https://git.kernel.org/pub/scm/linux/kernel/git/broonie/sound into for-linus

ASoC: Fixes for v5.11

A collection of mostly driver specific fixes, plus a maintainership
update for TI and a fix for DAPM driver removal paths.

show more ...

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

Staying in sync to drm-next, and to be able to pull ttm fixes.

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