This is an automated email from the ASF dual-hosted git repository. jiuzhudong pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit 018e6d50c524412e679583d7ad9f4cf6c052cb91 Author: ouyangxiangzhen <[email protected]> AuthorDate: Fri Jan 16 10:51:45 2026 +0800 sched/hrtimer: Fix finding the rbtree left-most node. Determining whether a red-black tree node is the left-mode node using `RB_LEFT(hrtimer, node) == NULL` is functionally incorrect. This is because the left node of any leaf node can also be NULL. For example, in the following rbtree: 5 / \ 3 7 \ 4 the left node of the right-most node 7 would also be NULL. To avoid extra performance overhead to find the left-most node when the rb-tree changed, this commit used `g_cached_first` to cache the left-most node. Signed-off-by: ouyangxiangzhen <[email protected]> --- sched/hrtimer/hrtimer.h | 26 +++++++++++++++++++++++--- sched/hrtimer/hrtimer_initialize.c | 1 + 2 files changed, 24 insertions(+), 3 deletions(-) diff --git a/sched/hrtimer/hrtimer.h b/sched/hrtimer/hrtimer.h index f20801cb4d4..e738c6c111c 100644 --- a/sched/hrtimer/hrtimer.h +++ b/sched/hrtimer/hrtimer.h @@ -84,6 +84,7 @@ extern seqcount_t g_hrtimer_lock; /* Red-Black tree containing all active high-resolution timers */ extern struct hrtimer_tree_s g_hrtimer_tree; +extern struct FAR hrtimer_s *g_hrtimer_head; #else /* List containing all active high-resolution timers */ @@ -218,16 +219,26 @@ RB_PROTOTYPE(hrtimer_tree_s, hrtimer_s, node, hrtimer_compare); static inline_function bool hrtimer_remove(FAR hrtimer_t *hrtimer) { + bool is_head; #ifdef CONFIG_HRTIMER_TREE + is_head = g_hrtimer_head == hrtimer; + RB_REMOVE(hrtimer_tree_s, &g_hrtimer_tree, hrtimer); + + if (is_head) + { + g_hrtimer_head = RB_MIN(hrtimer_tree_s, &g_hrtimer_tree); + } #else + is_head = list_is_head(&g_hrtimer_list, &hrtimer->node); list_delete_fast(&hrtimer->node); #endif /* Explicitly mark the timer as dequeued. */ hrtimer->func = NULL; - return RB_LEFT(hrtimer, node) == NULL; + + return is_head; } /**************************************************************************** @@ -248,8 +259,17 @@ static inline_function bool hrtimer_remove(FAR hrtimer_t *hrtimer) static inline_function bool hrtimer_insert(FAR hrtimer_t *hrtimer) { #ifdef CONFIG_HRTIMER_TREE + bool is_head = false; RB_INSERT(hrtimer_tree_s, &g_hrtimer_tree, hrtimer); - return RB_LEFT(hrtimer, node) == NULL; + + if (g_hrtimer_head == NULL || + HRTIMER_TIME_BEFORE(hrtimer->expired, g_hrtimer_head->expired)) + { + g_hrtimer_head = hrtimer; + is_head = true; + } + + return is_head; #else FAR hrtimer_t *curr; uint64_t expired = hrtimer->expired; @@ -282,7 +302,7 @@ static inline_function bool hrtimer_insert(FAR hrtimer_t *hrtimer) static inline_function FAR hrtimer_t *hrtimer_get_first(void) { #ifdef CONFIG_HRTIMER_TREE - return RB_MIN(hrtimer_tree_s, &g_hrtimer_tree); + return g_hrtimer_head; #else return list_first_entry(&g_hrtimer_list, FAR hrtimer_t, node); #endif diff --git a/sched/hrtimer/hrtimer_initialize.c b/sched/hrtimer/hrtimer_initialize.c index 96da76f99cd..b381a06bbd4 100644 --- a/sched/hrtimer/hrtimer_initialize.c +++ b/sched/hrtimer/hrtimer_initialize.c @@ -62,6 +62,7 @@ seqcount_t g_hrtimer_lock = SEQLOCK_INITIALIZER; /* Red-black tree for hrtimer storage (requires CONFIG_HRTIMER_TREE) */ struct hrtimer_tree_s g_hrtimer_tree = RB_INITIALIZER(g_hrtimer_tree); +struct FAR hrtimer_s *g_hrtimer_head; #else /* Linked list for hrtimer storage (fallback when tree is disabled) */
