| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Thu, 27 May 2010 17:29:43 +0200
From: Peter Zijlstra <peterz@...radead.org>
To: mingo@...hat.com, hpa@...or.com, linux-kernel@...r.kernel.org,
venkatesh.pallipadi@...el.com, suresh.b.siddha@...el.com,
tglx@...utronix.de
Cc: linux-tip-commits@...r.kernel.org
Subject: Re: [tip:x86/pat] rbtree: Add support for augmented rbtrees
On Fri, 2010-02-19 at 00:21 +0000, tip-bot for Pallipadi, Venkatesh
wrote:
> Commit-ID: 17d9ddc72fb8bba0d4f67868c9c612e472a594a9
> Gitweb: http://git.kernel.org/tip/17d9ddc72fb8bba0d4f67868c9c612e472a594a9
> Author: Pallipadi, Venkatesh <venkatesh.pallipadi@...el.com>
> AuthorDate: Wed, 10 Feb 2010 15:23:44 -0800
> Committer: H. Peter Anvin <hpa@...or.com>
> CommitDate: Thu, 18 Feb 2010 15:40:56 -0800
>
> rbtree: Add support for augmented rbtrees
>
> Add support for augmented rbtrees in core rbtree code.
>
> This will be used in subsequent patches, in x86 PAT code, which needs
> interval trees to efficiently keep track of PAT ranges.
>
> Signed-off-by: Venkatesh Pallipadi <venkatesh.pallipadi@...el.com>
> LKML-Reference: <20100210232343.GA11465@...ux-os.sc.intel.com>
> Signed-off-by: Suresh Siddha <suresh.b.siddha@...el.com>
> Signed-off-by: H. Peter Anvin <hpa@...or.com>
> --- a/lib/rbtree.c
> +++ b/lib/rbtree.c
> @@ -44,6 +44,11 @@ static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
> else
> root->rb_node = right;
> rb_set_parent(node, right);
> +
> + if (root->augment_cb) {
> + root->augment_cb(node);
> + root->augment_cb(right);
> + }
> }
>
> static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
> @@ -67,12 +72,20 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
> else
> root->rb_node = left;
> rb_set_parent(node, left);
> +
> + if (root->augment_cb) {
> + root->augment_cb(node);
> + root->augment_cb(left);
> + }
> }
>
Did someone measure what these extra conditionals do to the scheduler?
Also, I don't think you actually need this callback, you can augment
externally like this ('borrowed' the idea from the BFQ code):
full patch at:
http://programming.kicks-ass.net/kernel-patches/sched_eevdf.patch
+static inline struct sched_entity *se_of(struct rb_node *node)
+{
+ return rb_entry(node, struct sched_entity, run_node);
+}
+
+static inline s64 deadline_key(struct cfs_rq *cfs_rq, u64 deadline)
+{
+ return (s64)(deadline - cfs_rq->min_vruntime);
+}
+
+#define deadline_gt(cfs_rq, field, lse, rse) \
+({ deadline_key(cfs_rq, lse->field) > \
+ deadline_key(cfs_rq, rse->field); })
+
+static void update_min_deadline(struct cfs_rq *cfs_rq,
+ struct sched_entity *se, struct rb_node *node)
+{
+ if (node && deadline_gt(cfs_rq, min_deadline, se, se_of(node)))
+ se->min_deadline = se_of(node)->min_deadline;
+}
+
+/*
+ * se->min_deadline = min(se->deadline, left->min_deadline, right->min_deadline)
+ */
+static void update_node(struct cfs_rq *cfs_rq, struct rb_node *node)
+{
+ struct sched_entity *se = rb_entry(node, struct sched_entity, run_node);
+
+ se->min_deadline = se->deadline;
+ update_min_deadline(cfs_rq, se, node->rb_right);
+ update_min_deadline(cfs_rq, se, node->rb_left);
+}
+
+/*
+ * update min_deadline for all nodes that could have been affected by
+ * a rebalance pass up from @node
+ */
+static void update_tree(struct cfs_rq *cfs_rq, struct rb_node *node)
+{
+ struct rb_node *parent;
+
+up:
+ update_node(cfs_rq, node);
+ parent = rb_parent(node);
+ if (!parent)
+ return;
+
+ if (node == parent->rb_left && parent->rb_right)
+ update_node(cfs_rq, parent->rb_right);
+ else if (parent->rb_left)
+ update_node(cfs_rq, parent->rb_left);
+
+ node = parent;
+ goto up;
+}
+
+/*
+ * after inserting @se into the tree, update min_deadline to account for
+ * both the new deadline and any damage done by rebalance
+ */
+static void update_tree_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+ struct rb_node *node = &se->run_node;
+
+ if (node->rb_left)
+ node = node->rb_left;
+ else if (node->rb_right)
+ node = node->rb_right;
+
+ update_tree(cfs_rq, node);
+}
+
+/*
+ * before removing the node, find the deepest node on the rebalance path
+ * that will still be there after @se gets removed
+ */
+static struct rb_node *update_tree_dequeue_begin(struct sched_entity *se)
+{
+ struct rb_node *deepest;
+ struct rb_node *node = &se->run_node;
+
+ if (!node->rb_right && !node->rb_left)
+ deepest = rb_parent(node);
+ else if (!node->rb_right)
+ deepest = node->rb_left;
+ else if (!node->rb_left)
+ deepest = node->rb_right;
+ else {
+ deepest = rb_next(node);
+ if (deepest->rb_right)
+ deepest = deepest->rb_right;
+ else if (rb_parent(deepest) != node)
+ deepest = rb_parent(deepest);
+ }
+
+ return deepest;
+}
+
+/*
+ * now that the entity got removed, update min_deadline to undo the missing
+ * deadine and any rebalance damage
+ */
+static void update_tree_dequeue_end(struct cfs_rq *cfs_rq, struct rb_node *node)
+{
+ if (node)
+ update_tree(cfs_rq, node);
}
/*
@@ -360,10 +578,14 @@ static void __enqueue_entity(struct cfs_
rb_link_node(&se->run_node, parent, link);
rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
+
+ update_tree_enqueue(cfs_rq, se);
}
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
+ struct rb_node *node = update_tree_dequeue_begin(se);
+
if (cfs_rq->rb_leftmost == &se->run_node) {
struct rb_node *next_node;
@@ -372,16 +594,145 @@ static void __dequeue_entity(struct cfs_
}
rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
+ update_tree_dequeue_end(cfs_rq, node);
+ avg_vruntime_sub(cfs_rq, se);
}
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists