[patch 46/48] hrtimer: Use linked timerqueue

[Thomas Gleixner <tglx@kernel.org>]

To prepare for optimizing the rearming of enqueued timers, switch to the
linked timerqueue. That allows to check whether the new expiry time changes
the position of the timer in the RB tree or not, by checking the new expiry
time against the previous and the next timers expiry.

Signed-off-by: Thomas Gleixner <tglx@kernel.org
---
 include/linux/hrtimer_defs.h  |   16 ++++++++--------
 include/linux/hrtimer_types.h |    8 ++++----
 kernel/time/hrtimer.c         |   34 +++++++++++++++++-----------------
 kernel/time/timer_list.c      |   10 ++++------
 4 files changed, 33 insertions(+), 35 deletions(-)

--- a/include/linux/hrtimer_defs.h
+++ b/include/linux/hrtimer_defs.h
@@ -25,14 +25,14 @@
  * @offset:		offset of this clock to the monotonic base
  */
 struct hrtimer_clock_base {
-	struct hrtimer_cpu_base	*cpu_base;
-	unsigned int		index;
-	clockid_t		clockid;
-	seqcount_raw_spinlock_t	seq;
-	ktime_t			expires_next;
-	struct hrtimer		*running;
-	struct timerqueue_head	active;
-	ktime_t			offset;
+	struct hrtimer_cpu_base		*cpu_base;
+	unsigned int			index;
+	clockid_t			clockid;
+	seqcount_raw_spinlock_t		seq;
+	ktime_t				expires_next;
+	struct hrtimer			*running;
+	struct timerqueue_linked_head	active;
+	ktime_t				offset;
 } __hrtimer_clock_base_align;
 
 enum  hrtimer_base_type {
--- a/include/linux/hrtimer_types.h
+++ b/include/linux/hrtimer_types.h
@@ -17,7 +17,7 @@ enum hrtimer_restart {
 
 /**
  * struct hrtimer - the basic hrtimer structure
- * @node:	timerqueue node, which also manages node.expires,
+ * @node:	Linked timerqueue node, which also manages node.expires,
  *		the absolute expiry time in the hrtimers internal
  *		representation. The time is related to the clock on
  *		which the timer is based. Is setup by adding
@@ -39,15 +39,15 @@ enum hrtimer_restart {
  * The hrtimer structure must be initialized by hrtimer_setup()
  */
 struct hrtimer {
-	struct timerqueue_node		node;
-	ktime_t				_softexpires;
-	enum hrtimer_restart		(*__private function)(struct hrtimer *);
+	struct timerqueue_linked_node	node;
 	struct hrtimer_clock_base	*base;
 	bool				is_queued;
 	bool				is_rel;
 	bool				is_soft;
 	bool				is_hard;
 	bool				is_lazy;
+	ktime_t				_softexpires;
+	enum hrtimer_restart		(*__private function)(struct hrtimer *);
 };
 
 #endif /* _LINUX_HRTIMER_TYPES_H */
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -557,10 +557,10 @@ static ktime_t hrtimer_bases_next_event_
 		 * If the excluded timer is the first on this base evaluate the
 		 * next timer.
 		 */
-		struct timerqueue_node *node = timerqueue_getnext(&base->active);
+		struct timerqueue_linked_node *node = timerqueue_linked_first(&base->active);
 
 		if (unlikely(&exclude->node == node)) {
-			node = timerqueue_iterate_next(node);
+			node = timerqueue_linked_next(node);
 			if (!node)
 				continue;
 			expires = ktime_sub(node->expires, base->offset);
@@ -576,7 +576,7 @@ static ktime_t hrtimer_bases_next_event_
 
 static __always_inline struct hrtimer *clock_base_next_timer(struct hrtimer_clock_base *base)
 {
-	struct timerqueue_node *next = timerqueue_getnext(&base->active);
+	struct timerqueue_linked_node *next = timerqueue_linked_first(&base->active);
 
 	return container_of(next, struct hrtimer, node);
 }
@@ -938,9 +938,9 @@ static bool update_needs_ipi(struct hrti
 	active &= cpu_base->active_bases;
 
 	for_each_active_base(base, cpu_base, active) {
-		struct timerqueue_node *next;
+		struct timerqueue_linked_node *next;
 
-		next = timerqueue_getnext(&base->active);
+		next = timerqueue_linked_first(&base->active);
 		expires = ktime_sub(next->expires, base->offset);
 		if (expires < cpu_base->expires_next)
 			return true;
@@ -1112,7 +1112,7 @@ static bool enqueue_hrtimer(struct hrtim
 	/* Pairs with the lockless read in hrtimer_is_queued() */
 	WRITE_ONCE(timer->is_queued, HRTIMER_STATE_ENQUEUED);
 
-	if (!timerqueue_add(&base->active, &timer->node))
+	if (!timerqueue_linked_add(&base->active, &timer->node))
 		return false;
 
 	base->expires_next = hrtimer_get_expires(timer);
@@ -1121,7 +1121,7 @@ static bool enqueue_hrtimer(struct hrtim
 
 static inline void base_update_next_timer(struct hrtimer_clock_base *base)
 {
-	struct timerqueue_node *next = timerqueue_getnext(&base->active);
+	struct timerqueue_linked_node *next = timerqueue_linked_first(&base->active);
 
 	base->expires_next = next ? next->expires : KTIME_MAX;
 }
@@ -1148,9 +1148,9 @@ static void __remove_hrtimer(struct hrti
 	/* Pairs with the lockless read in hrtimer_is_queued() */
 	WRITE_ONCE(timer->is_queued, newstate);
 
-	was_first = &timer->node == timerqueue_getnext(&base->active);
+	was_first = !timerqueue_linked_prev(&timer->node);
 
-	if (!timerqueue_del(&base->active, &timer->node))
+	if (!timerqueue_linked_del(&base->active, &timer->node))
 		cpu_base->active_bases &= ~(1 << base->index);
 
 	/* Nothing to update if this was not the first timer in the base */
@@ -1212,8 +1212,8 @@ remove_and_enqueue_same_base(struct hrti
 	/* Remove it from the timer queue if active */
 	if (timer->is_queued) {
 		debug_hrtimer_deactivate(timer);
-		was_first = &timer->node == timerqueue_getnext(&base->active);
-		timerqueue_del(&base->active, &timer->node);
+		was_first = !timerqueue_linked_prev(&timer->node);
+		timerqueue_linked_del(&base->active, &timer->node);
 	}
 
 	/* Set the new expiry time */
@@ -1226,7 +1226,7 @@ remove_and_enqueue_same_base(struct hrti
 	WRITE_ONCE(timer->is_queued, HRTIMER_STATE_ENQUEUED);
 
 	/* If it's the first expiring timer now or again, update base */
-	if (timerqueue_add(&base->active, &timer->node)) {
+	if (timerqueue_linked_add(&base->active, &timer->node)) {
 		base->expires_next = expires;
 		return true;
 	}
@@ -1758,7 +1758,7 @@ static void __hrtimer_setup(struct hrtim
 	timer->is_hard = !!(mode & HRTIMER_MODE_HARD);
 	timer->is_lazy = !!(mode & HRTIMER_MODE_LAZY_REARM);
 	timer->base = &cpu_base->clock_base[base];
-	timerqueue_init(&timer->node);
+	timerqueue_linked_init(&timer->node);
 
 	if (WARN_ON_ONCE(!fn))
 		ACCESS_PRIVATE(timer, function) = hrtimer_dummy_timeout;
@@ -1923,7 +1923,7 @@ static void __run_hrtimer(struct hrtimer
 
 static __always_inline struct hrtimer *clock_base_next_timer_safe(struct hrtimer_clock_base *base)
 {
-	struct timerqueue_node *next = timerqueue_getnext(&base->active);
+	struct timerqueue_linked_node *next = timerqueue_linked_first(&base->active);
 
 	return next ? container_of(next, struct hrtimer, node) : NULL;
 }
@@ -2369,7 +2369,7 @@ int hrtimers_prepare_cpu(unsigned int cp
 
 		clock_b->cpu_base = cpu_base;
 		seqcount_raw_spinlock_init(&clock_b->seq, &cpu_base->lock);
-		timerqueue_init_head(&clock_b->active);
+		timerqueue_linked_init_head(&clock_b->active);
 	}
 
 	cpu_base->cpu = cpu;
@@ -2399,10 +2399,10 @@ int hrtimers_cpu_starting(unsigned int c
 static void migrate_hrtimer_list(struct hrtimer_clock_base *old_base,
 				struct hrtimer_clock_base *new_base)
 {
-	struct timerqueue_node *node;
+	struct timerqueue_linked_node *node;
 	struct hrtimer *timer;
 
-	while ((node = timerqueue_getnext(&old_base->active))) {
+	while ((node = timerqueue_linked_first(&old_base->active))) {
 		timer = container_of(node, struct hrtimer, node);
 		BUG_ON(hrtimer_callback_running(timer));
 		debug_hrtimer_deactivate(timer);
--- a/kernel/time/timer_list.c
+++ b/kernel/time/timer_list.c
@@ -56,13 +56,11 @@ print_timer(struct seq_file *m, struct h
 		(long long)(ktime_to_ns(hrtimer_get_expires(timer)) - now));
 }
 
-static void
-print_active_timers(struct seq_file *m, struct hrtimer_clock_base *base,
-		    u64 now)
+static void print_active_timers(struct seq_file *m, struct hrtimer_clock_base *base, u64 now)
 {
+	struct timerqueue_linked_node *curr;
 	struct hrtimer *timer, tmp;
 	unsigned long next = 0, i;
-	struct timerqueue_node *curr;
 	unsigned long flags;
 
 next_one:
@@ -72,13 +70,13 @@ print_active_timers(struct seq_file *m,
 
 	raw_spin_lock_irqsave(&base->cpu_base->lock, flags);
 
-	curr = timerqueue_getnext(&base->active);
+	curr = timerqueue_linked_first(&base->active);
 	/*
 	 * Crude but we have to do this O(N*N) thing, because
 	 * we have to unlock the base when printing:
 	 */
 	while (curr && i < next) {
-		curr = timerqueue_iterate_next(curr);
+		curr = timerqueue_linked_next(curr);
 		i++;
 	}