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 290EA3A7F55 for ; Tue, 24 Feb 2026 16:38:56 +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=1771951136; cv=none; b=aPIyMT7nozconbMl+yuICwNrwo7BRb+krhqregH1Tdcje47+dpYWJRt6UXiNEI6yzExILQn5ZZHkOSukJCzTGDB3gRVJk4nKTqJGyKwG42OLMH3eiYncSNeBnAyeZk3YUdAAU+G/s+69u9Y4b2gDZQEQSEDKGY22srjP06WYnOo= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1771951136; c=relaxed/simple; bh=ERFU2wUzLFOSg47So7ssEiGp38boms4jLm0JhxZ2SQs=; h=Date:Message-ID:From:To:Cc:Subject:References:MIME-Version: Content-Type; b=ZzEqC/TI6zysOaSpDRVrQYerUQbIEcc9uy5JUm3diVaeSp9PpVLvPhOt2ARZOsdHXBPP433N40+baQbqIEmDJpzpzTgBJ01BYpOLALkpLlA6tpAErRJr6G42lFnCX7dtg/e7R5f83V7SqFoJFa+GWgCE7dJuK9NBZr5Jg3yZb4g= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=urU3Ec3h; 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="urU3Ec3h" Received: by smtp.kernel.org (Postfix) with ESMTPSA id 308E3C116D0; Tue, 24 Feb 2026 16:38:54 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1771951136; bh=ERFU2wUzLFOSg47So7ssEiGp38boms4jLm0JhxZ2SQs=; h=Date:From:To:Cc:Subject:References:From; b=urU3Ec3hyKGdIYh4UxhZvKhQwI2A91MrCt2Oh/28joIK2E/JPj1QZC/ixzlvRzc+Q k/j3Q5eRnafSc5KqBZpWnuPl7AtNd7K6iepT6SqJkjVDxSXlVWkq6JUKMzhqA7rdeM 54IKyF5T9RWz1h+T13ZBjuouT2PUUmHFhWK6Pm68+oHLXK4l+q+CAi6coUz49h/arj bLVyNz/ireE/u2VtIZDReRqzPaIRAHpP5TS7tuWpGhzJOOBHXSlXy0u45Di3N/PjZU eIM5juepR/ESCgqFO0KxzCVCfNEmwzDQL6J0Ub4iIHHvybas4JSm3NojMi+YlAp2eL nppUhhD4pAyHw== Date: Tue, 24 Feb 2026 17:38:52 +0100 Message-ID: <20260224163431.734827095@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 45/48] timerqueue: Provide 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 The hrtimer subsystem wants to peak ahead to the next and previous timer to evaluated whether a to be rearmed timer can stay at the same position in the RB tree with the new expiry time. The linked RB tree provides the infrastructure for this as it maintains links to the previous and next nodes for each entry in the tree. Provide timerqueue wrappers around that. Signed-off-by: Thomas Gleixner #include -extern bool timerqueue_add(struct timerqueue_head *head, - struct timerqueue_node *node); -extern bool timerqueue_del(struct timerqueue_head *head, - struct timerqueue_node *node); -extern struct timerqueue_node *timerqueue_iterate_next( - struct timerqueue_node *node); +bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node); +bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node); +struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node); + +bool timerqueue_linked_add(struct timerqueue_linked_head *head, struct timerqueue_linked_node *node); /** * timerqueue_getnext - Returns the timer with the earliest expiration time @@ -19,8 +18,7 @@ extern struct timerqueue_node *timerqueu * * Returns a pointer to the timer node that has the earliest expiration time. */ -static inline -struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) +static inline struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) { struct rb_node *leftmost = rb_first_cached(&head->rb_root); @@ -41,4 +39,46 @@ static inline void timerqueue_init_head( { head->rb_root = RB_ROOT_CACHED; } + +/* Timer queues with linked nodes */ + +static __always_inline +struct timerqueue_linked_node *timerqueue_linked_first(struct timerqueue_linked_head *head) +{ + return rb_entry_safe(head->rb_root.rb_leftmost, struct timerqueue_linked_node, node); +} + +static __always_inline +struct timerqueue_linked_node *timerqueue_linked_next(struct timerqueue_linked_node *node) +{ + return rb_entry_safe(node->node.next, struct timerqueue_linked_node, node); +} + +static __always_inline +struct timerqueue_linked_node *timerqueue_linked_prev(struct timerqueue_linked_node *node) +{ + return rb_entry_safe(node->node.prev, struct timerqueue_linked_node, node); +} + +static __always_inline +bool timerqueue_linked_del(struct timerqueue_linked_head *head, struct timerqueue_linked_node *node) +{ + return rb_erase_linked(&node->node, &head->rb_root); +} + +static __always_inline void timerqueue_linked_init(struct timerqueue_linked_node *node) +{ + RB_CLEAR_LINKED_NODE(&node->node); +} + +static __always_inline bool timerqueue_linked_node_queued(struct timerqueue_linked_node *node) +{ + return !RB_EMPTY_LINKED_NODE(&node->node); +} + +static __always_inline void timerqueue_linked_init_head(struct timerqueue_linked_head *head) +{ + head->rb_root = RB_ROOT_LINKED; +} + #endif /* _LINUX_TIMERQUEUE_H */ --- a/include/linux/timerqueue_types.h +++ b/include/linux/timerqueue_types.h @@ -6,12 +6,21 @@ #include struct timerqueue_node { - struct rb_node node; - ktime_t expires; + struct rb_node node; + ktime_t expires; }; struct timerqueue_head { - struct rb_root_cached rb_root; + struct rb_root_cached rb_root; +}; + +struct timerqueue_linked_node { + struct rb_node_linked node; + ktime_t expires; +}; + +struct timerqueue_linked_head { + struct rb_root_linked rb_root; }; #endif /* _LINUX_TIMERQUEUE_TYPES_H */ --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -82,3 +82,17 @@ struct timerqueue_node *timerqueue_itera return container_of(next, struct timerqueue_node, node); } EXPORT_SYMBOL_GPL(timerqueue_iterate_next); + +#define __node_2_tq_linked(_n) \ + container_of(rb_entry((_n), struct rb_node_linked, node), struct timerqueue_linked_node, node) + +static __always_inline bool __tq_linked_less(struct rb_node *a, const struct rb_node *b) +{ + return __node_2_tq_linked(a)->expires < __node_2_tq_linked(b)->expires; +} + +bool timerqueue_linked_add(struct timerqueue_linked_head *head, struct timerqueue_linked_node *node) +{ + return rb_add_linked(&node->node, &head->rb_root, __tq_linked_less); +} +EXPORT_SYMBOL_GPL(timerqueue_linked_add);