[RFC v8 28/28] clockevents: move non-adjustable devices to the tail of the list

[Nicolai Stange <nicstange@gmail.com>]

clockevents_adjust_all_freqs() iterates over all devices in the
clockevent_devices list and adjusts frequencies as appropriate, skipping
over those that have either of CLOCK_EVT_FEAT_DUMMY and
CLOCK_EVT_FEAT_NO_ADJUST set or aren't oneshot capable.

This results in unnecessary memory accesses to these list members.

Avoid this by moving all such devices to the end of the clockevents_devices
list and making clockevents_adjust_all_freqs() return as soon as it
encounters the first of them.

For the list insertion part, introduce the ced_list_add() helper and
use it where appropriate.

Benchmark results:
The following measurements have been carried out on a Raspberry Pi 2B
(armv7, 4 cores, 900MHz). The adjustment process has been driven by
periodically injecting a certain offset via adjtimex(2) approximately
every 3.7h. A 'stress --vm 8 --vm-bytes 32M' was running. The runtime of
clockevents_adjust_all_freqs() has been measured.

- Before this patch:
  Mean: 6916.90+-782.63
  Quantiles:
    0%    25%    50%    75%    100%
  3072   6412   6927   7430   10989 (ns)

- After this patch:
  Mean: 6505.18+-740.85
  Quantiles:
    0%    25%    50%    75%    100%
  2708   6054   6523   6980   10885 (ns)

Signed-off-by: Nicolai Stange <nicstange@gmail.com>
---
 kernel/time/clockevents.c | 22 +++++++++++++++++++---
 1 file changed, 19 insertions(+), 3 deletions(-)

diff --git a/kernel/time/clockevents.c b/kernel/time/clockevents.c
index 6146d2f..038fa82 100644
--- a/kernel/time/clockevents.c
+++ b/kernel/time/clockevents.c
@@ -341,6 +341,22 @@ int clockevents_program_event(struct clock_event_device *dev, ktime_t expires,
 	return (rc && force) ? clockevents_program_min_delta(dev) : rc;
 }
 
+static void ced_list_add(struct clock_event_device *dev)
+{
+	/*
+	 * Insert all devices which aren't candidates for NTP
+	 * frequency adjustments at the end of the list such that
+	 * clockevents_adjust_all_freqs() can skip the tail once
+	 * encountering the first of them.
+	 */
+	if (!(dev->features & CLOCK_EVT_FEAT_ONESHOT) ||
+	    (dev->features & CLOCK_EVT_FEAT_DUMMY) ||
+	    (dev->features & CLOCK_EVT_FEAT_NO_ADJUST))
+		list_add_tail(&dev->list, &clockevent_devices);
+	else
+		list_add(&dev->list, &clockevent_devices);
+}
+
 /*
  * Called after a notify add to make devices available which were
  * released from the notifier call.
@@ -353,7 +369,7 @@ static void clockevents_notify_released(void)
 		dev = list_entry(clockevents_released.next,
 				 struct clock_event_device, list);
 		list_del(&dev->list);
-		list_add(&dev->list, &clockevent_devices);
+		ced_list_add(dev);
 		tick_check_new_device(dev);
 	}
 }
@@ -524,7 +540,7 @@ void clockevents_register_device(struct clock_event_device *dev)
 
 	raw_spin_lock_irqsave(&clockevents_lock, flags);
 
-	list_add(&dev->list, &clockevent_devices);
+	ced_list_add(dev);
 	tick_check_new_device(dev);
 	clockevents_notify_released();
 
@@ -638,7 +654,7 @@ void clockevents_adjust_all_freqs(u32 mult_cs_mono, u32 mult_cs_raw)
 		if (!(dev->features & CLOCK_EVT_FEAT_ONESHOT) ||
 		    (dev->features & CLOCK_EVT_FEAT_DUMMY) ||
 		    (dev->features & CLOCK_EVT_FEAT_NO_ADJUST))
-			continue;
+			break;
 
 		/*
 		 * The cached last_mult_adjusted is only valid if
-- 
2.10.2