From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 166F43A9015 for ; Tue, 24 Feb 2026 16:39:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1771951141; cv=none; b=LyC+d5Yfxyp1Oq58NYxMcuAgn+p/m46OqnbK6t+oYmAXoHMYsF0irdTLNQztgdALy2MuDXgitJZUSV3KNlnRFgttXMKn+8610xLk+9G0iHzMP3li4Wjhss2tsApKdQIrYWd5wVrf/2rZdsFNMTZH/Zu5RHeJIrsxlQ80hWTxE5Y= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1771951141; c=relaxed/simple; bh=bKQhrRJiiIbQvKDunwFGX+aEdKgIU1SPhMoabfS3wfQ=; h=Date:Message-ID:From:To:Cc:Subject:References:MIME-Version: Content-Type; b=Gh/ky38jcdBAm5MQvy6LTNKK09i5+Axcb1hRHquuKznEj3WhXCKrGSJl5aTifWCGb9ZAPh47d6/u54uoSaYlissT2yUjQdt7VenUepim/sNGCGsm6YPZ6jBiCaDgNUyPbq20GDF4r4JY2SCWFrOAoZ6VSRdPyiDxtoI2WX8Ekmk= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=bjORec1D; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="bjORec1D" Received: by smtp.kernel.org (Postfix) with ESMTPSA id 5F0A7C116D0; Tue, 24 Feb 2026 16:39:00 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1771951141; bh=bKQhrRJiiIbQvKDunwFGX+aEdKgIU1SPhMoabfS3wfQ=; h=Date:From:To:Cc:Subject:References:From; b=bjORec1D9vabH6D/F9q7U8AnCKqmucMivxRhYPKfSL9efq1E0TRYE13gJwLHjKINa Zfhx3nNgCjyvlzk34/72K8GMSW66r3WQ1mJMPTY6YzwJ+nFQrrnpJq7LowqCaKW4r1 Padj/LIbkAJhM5KAWaAZ6I92EocO9oapyBsNkq6tM3RaLyBoVbyqXwP/NIleebZfMe Kx4B6cVEImvPXerkyn+ltaVndOfD+VAXqRWxZ6zvmdDpoKmiW+YfjMhfxqV+hlujVF Z2IZ6e09H9OaA/+PcJ1UWQMYh+XZeZU6AmUUTsEzECktalWjyablDBX595KVimKaZ9 OhUeOk/N79lYg== Date: Tue, 24 Feb 2026 17:38:57 +0100 Message-ID: <20260224163431.806643179@kernel.org> User-Agent: quilt/0.68 From: Thomas Gleixner To: LKML Cc: Anna-Maria Behnsen , John Stultz , Stephen Boyd , Daniel Lezcano , Juri Lelli , Vincent Guittot , Dietmar Eggemann , Steven Rostedt , Ben Segall , Mel Gorman , Valentin Schneider , x86@kernel.org, Peter Zijlstra , Frederic Weisbecker , Eric Dumazet Subject: [patch 46/48] hrtimer: Use linked timerqueue References: <20260224163022.795809588@kernel.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 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 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++; }