From: "tip-bot2 for Peter Zijlstra" <tip-bot2@linutronix.de>
To: linux-tip-commits@vger.kernel.org
Cc: "Peter Zijlstra (Intel)" <peterz@infradead.org>,
Ingo Molnar <mingo@kernel.org>,
x86@kernel.org, linux-kernel@vger.kernel.org
Subject: [tip: sched/core] rbtree: Add rb_add_augmented_cached() helper
Date: Thu, 10 Aug 2023 07:10:56 -0000 [thread overview]
Message-ID: <169165145631.27769.14339276495833528763.tip-bot2@tip-bot2> (raw)
In-Reply-To: <20230531124603.862983648@infradead.org>
The following commit has been merged into the sched/core branch of tip:
Commit-ID: 99d4d26551b56f4e523dd04e4970b94aa796a64e
Gitweb: https://git.kernel.org/tip/99d4d26551b56f4e523dd04e4970b94aa796a64e
Author: Peter Zijlstra <peterz@infradead.org>
AuthorDate: Wed, 31 May 2023 13:58:43 +02:00
Committer: Ingo Molnar <mingo@kernel.org>
CommitterDate: Wed, 19 Jul 2023 09:43:58 +02:00
rbtree: Add rb_add_augmented_cached() helper
While slightly sub-optimal, updating the augmented data while going
down the tree during lookup would be faster -- alas the augment
interface does not currently allow for that, provide a generic helper
to add a node to an augmented cached tree.
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Link: https://lore.kernel.org/r/20230531124603.862983648@infradead.org
---
include/linux/rbtree_augmented.h | 26 ++++++++++++++++++++++++++
1 file changed, 26 insertions(+)
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index 7ee7ed5..6dbc5a1 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -60,6 +60,32 @@ rb_insert_augmented_cached(struct rb_node *node,
rb_insert_augmented(node, &root->rb_root, augment);
}
+static __always_inline struct rb_node *
+rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree,
+ bool (*less)(struct rb_node *, const struct rb_node *),
+ const struct rb_augment_callbacks *augment)
+{
+ struct rb_node **link = &tree->rb_root.rb_node;
+ struct rb_node *parent = NULL;
+ bool leftmost = true;
+
+ while (*link) {
+ parent = *link;
+ if (less(node, parent)) {
+ link = &parent->rb_left;
+ } else {
+ link = &parent->rb_right;
+ leftmost = false;
+ }
+ }
+
+ rb_link_node(node, parent, link);
+ augment->propagate(parent, NULL); /* suboptimal */
+ rb_insert_augmented_cached(node, tree, leftmost, augment);
+
+ return leftmost ? node : NULL;
+}
+
/*
* Template for declaring augmented rbtree callbacks (generic case)
*
next prev parent reply other threads:[~2023-08-10 7:11 UTC|newest]
Thread overview: 104+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-05-31 11:58 [PATCH 00/15] sched: EEVDF and latency-nice and/or slice-attr Peter Zijlstra
2023-05-31 11:58 ` [PATCH 01/15] sched/fair: Add avg_vruntime Peter Zijlstra
2023-06-02 13:51 ` Vincent Guittot
2023-06-02 14:27 ` Peter Zijlstra
2023-06-05 7:18 ` Vincent Guittot
2023-08-10 7:10 ` [tip: sched/core] sched/fair: Add cfs_rq::avg_vruntime tip-bot2 for Peter Zijlstra
2023-10-11 4:15 ` [PATCH 01/15] sched/fair: Add avg_vruntime Abel Wu
2023-10-11 7:30 ` Peter Zijlstra
2023-10-11 8:30 ` Abel Wu
2023-10-11 9:45 ` Peter Zijlstra
2023-10-11 10:05 ` Peter Zijlstra
2023-10-11 13:08 ` Peter Zijlstra
2023-05-31 11:58 ` [PATCH 02/15] sched/fair: Remove START_DEBIT Peter Zijlstra
2023-08-10 7:10 ` [tip: sched/core] sched/fair: Remove sched_feat(START_DEBIT) tip-bot2 for Peter Zijlstra
2023-05-31 11:58 ` [PATCH 03/15] sched/fair: Add lag based placement Peter Zijlstra
2023-08-10 7:10 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2023-10-11 12:00 ` [PATCH 03/15] " Abel Wu
2023-10-11 13:24 ` Peter Zijlstra
2023-10-12 7:04 ` Abel Wu
2023-10-13 7:37 ` Peter Zijlstra
2023-10-13 8:14 ` Abel Wu
2023-10-12 19:15 ` Benjamin Segall
2023-10-12 22:34 ` Peter Zijlstra
2023-10-13 16:35 ` Peter Zijlstra
2023-10-14 8:08 ` Mike Galbraith
2023-10-13 14:34 ` Peter Zijlstra
2023-05-31 11:58 ` [PATCH 04/15] rbtree: Add rb_add_augmented_cached() helper Peter Zijlstra
2023-08-10 7:10 ` tip-bot2 for Peter Zijlstra [this message]
2023-05-31 11:58 ` [PATCH 05/15] sched/fair: Implement an EEVDF like policy Peter Zijlstra
2023-08-10 7:10 ` [tip: sched/core] sched/fair: Implement an EEVDF-like scheduling policy tip-bot2 for Peter Zijlstra
2023-09-29 21:40 ` [PATCH 05/15] sched/fair: Implement an EEVDF like policy Benjamin Segall
2023-10-02 17:39 ` Peter Zijlstra
2023-10-11 4:14 ` Abel Wu
2023-10-11 7:33 ` Peter Zijlstra
2023-10-11 11:49 ` Abel Wu
2023-09-30 0:09 ` [PATCH] sched/fair: fix pick_eevdf to always find the correct se Benjamin Segall
2023-10-03 10:42 ` [tip: sched/urgent] sched/fair: Fix pick_eevdf() tip-bot2 for Benjamin Segall
[not found] ` <CGME20231004203940eucas1p2f73b017497d1f4239a6e236fdb6019e2@eucas1p2.samsung.com>
2023-10-04 20:39 ` [PATCH] sched/fair: fix pick_eevdf to always find the correct se Marek Szyprowski
2023-10-09 7:53 ` [tip: sched/urgent] sched/eevdf: Fix pick_eevdf() tip-bot2 for Benjamin Segall
2023-10-11 12:12 ` [PATCH] sched/fair: fix pick_eevdf to always find the correct se Abel Wu
2023-10-11 13:14 ` Peter Zijlstra
2023-10-12 10:04 ` Abel Wu
2023-10-11 21:01 ` Benjamin Segall
2023-10-12 10:25 ` Abel Wu
2023-10-12 17:51 ` Benjamin Segall
2023-10-13 3:46 ` Abel Wu
2023-10-13 16:51 ` Benjamin Segall
2023-05-31 11:58 ` [PATCH 06/15] sched: Commit to lag based placement Peter Zijlstra
2023-08-10 7:10 ` [tip: sched/core] sched/fair: " tip-bot2 for Peter Zijlstra
2023-05-31 11:58 ` [PATCH 07/15] sched/smp: Use lag to simplify cross-runqueue placement Peter Zijlstra
2023-08-10 7:10 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2023-09-12 15:32 ` [PATCH 07/15] " Sebastian Andrzej Siewior
2023-09-13 9:03 ` Peter Zijlstra
2023-10-04 1:17 ` [PATCH] sched/fair: Preserve PLACE_DEADLINE_INITIAL deadline Daniel Jordan
2023-10-04 13:09 ` [PATCH v2] " Daniel Jordan
2023-10-04 15:46 ` Chen Yu
2023-10-06 16:31 ` Daniel Jordan
2023-10-12 4:48 ` K Prateek Nayak
2023-10-05 5:56 ` [PATCH] " K Prateek Nayak
2023-10-06 16:35 ` Daniel Jordan
2023-10-06 16:48 ` [PATCH] sched/fair: Always update_curr() before placing at enqueue Daniel Jordan
2023-10-06 19:58 ` Peter Zijlstra
2023-10-18 0:43 ` Daniel Jordan
2023-10-16 5:39 ` K Prateek Nayak
2023-05-31 11:58 ` [PATCH 08/15] sched: Commit to EEVDF Peter Zijlstra
2023-06-16 21:23 ` Joel Fernandes
2023-06-22 12:01 ` Ingo Molnar
2023-06-22 13:11 ` Joel Fernandes
2023-08-10 7:10 ` [tip: sched/core] sched/fair: " tip-bot2 for Peter Zijlstra
2023-05-31 11:58 ` [PATCH 09/15] sched/debug: Rename min_granularity to base_slice Peter Zijlstra
2023-08-10 7:10 ` [tip: sched/core] sched/debug: Rename sysctl_sched_min_granularity to sysctl_sched_base_slice tip-bot2 for Peter Zijlstra
2023-05-31 11:58 ` [PATCH 10/15] sched/fair: Propagate enqueue flags into place_entity() Peter Zijlstra
2023-08-10 7:10 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2023-05-31 11:58 ` [PATCH 11/15] sched/eevdf: Better handle mixed slice length Peter Zijlstra
2023-06-02 13:45 ` Vincent Guittot
2023-06-02 15:06 ` Peter Zijlstra
2023-06-10 6:34 ` Chen Yu
2023-06-10 11:22 ` Peter Zijlstra
2023-05-31 11:58 ` [RFC][PATCH 12/15] sched: Introduce latency-nice as a per-task attribute Peter Zijlstra
2023-05-31 11:58 ` [RFC][PATCH 13/15] sched/fair: Implement latency-nice Peter Zijlstra
2023-06-06 14:54 ` Vincent Guittot
2023-06-08 10:34 ` Peter Zijlstra
2023-06-08 12:44 ` Peter Zijlstra
2023-10-11 23:24 ` Benjamin Segall
2023-05-31 11:58 ` [RFC][PATCH 14/15] sched/fair: Add sched group latency support Peter Zijlstra
2023-05-31 11:58 ` [RFC][PATCH 15/15] sched/eevdf: Use sched_attr::sched_runtime to set request/slice Peter Zijlstra
2023-06-01 13:55 ` Vincent Guittot
2023-06-08 11:52 ` Peter Zijlstra
2023-08-24 0:52 ` [PATCH 00/15] sched: EEVDF and latency-nice and/or slice-attr Daniel Jordan
2023-09-06 13:13 ` Peter Zijlstra
2023-09-29 16:54 ` Youssef Esmat
2023-10-02 15:55 ` Youssef Esmat
2023-10-02 18:41 ` Peter Zijlstra
2023-10-05 12:05 ` Peter Zijlstra
2023-10-05 14:14 ` Peter Zijlstra
2023-10-05 14:42 ` Peter Zijlstra
2023-10-05 18:23 ` Youssef Esmat
2023-10-06 0:36 ` Youssef Esmat
2023-10-10 8:08 ` Peter Zijlstra
2023-10-07 22:04 ` Peter Zijlstra
2023-10-09 14:41 ` Peter Zijlstra
2023-10-10 0:51 ` Youssef Esmat
2023-10-10 8:01 ` Peter Zijlstra
2023-10-16 16:50 ` Peter Zijlstra
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=169165145631.27769.14339276495833528763.tip-bot2@tip-bot2 \
--to=tip-bot2@linutronix.de \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-tip-commits@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=peterz@infradead.org \
--cc=x86@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).