[PATCH 0/3] Generic rb tree code

[PATCH 0/3] Generic rb tree code

[Kent Overstreet]

Right now, users of the rb tree code have to open code their own search and
insert functions. This provides generic versions that you pass a comparison
function to.

I highly doubt the extra function calls are going to have a measurable
performance impact in practice - the pointer chasing is going to dominate. I
did provide inline versions just in case, though - it's modelled after the
spinlock code.

The inline version of rb_search() is important for another reason, though - you
have to pass rb_search a pointer to your struct for it to compare against,
which has to be allocated on the stack. For most users I think that'll be fine,
but for the elevator code struct rb_node is embedded in struct request, which
is rather large. By using the inline version that stack allocation goes away.

(I looked at the generated assembly of elv_rb_find() before and after, and if
I'm reading it right it's not using any extra stack. Code is a bit worse, but
IMO removing code duplication is worth it).

Kent Overstreet (3):
  rbtree: Add rb_insert(), rb_search(), etc.
  timerqueue: convert to generic rb tree code
  block: convert elevator to generic rb tree code

 block/elevator.c       |   42 ++++++------------
 include/linux/rbtree.h |  110 ++++++++++++++++++++++++++++++++++++++++++++++++
 lib/rbtree.c           |   28 ++++++++++++
 lib/timerqueue.c       |   23 ++++------
 4 files changed, 159 insertions(+), 44 deletions(-)

-- 
1.7.9.3.327.g2980b

[PATCH 1/3] rbtree: Add rb_insert(), rb_search(), etc.

[Kent Overstreet]

Change-Id: I072d94a42b75454aa62be849c724980d27523b08

Signed-off-by: Kent Overstreet <koverstreet@google.com>
---
 include/linux/rbtree.h |  110 ++++++++++++++++++++++++++++++++++++++++++++++++
 lib/rbtree.c           |   28 ++++++++++++
 2 files changed, 138 insertions(+)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 033b507..4447919 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -174,4 +174,114 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
 	*rb_link = node;
 }
 
+typedef int (rb_cmp_t) (struct rb_node *l, struct rb_node *r);
+
+static inline int _rb_insert(struct rb_root *root,
+			     struct rb_node *new,
+			     rb_cmp_t cmp)
+{
+	struct rb_node **n = &root->rb_node, *parent = NULL;
+	int res;
+
+	while (*n) {
+		parent = *n;
+		res = cmp(new, *n);
+		if (!res)
+			return -1;
+		n = res < 0
+			? &(*n)->rb_left
+			: &(*n)->rb_right;
+	}
+
+	rb_link_node(new, parent, n);
+	rb_insert_color(new, root);
+	return 0;
+}
+
+static inline void _rb_insert_allow_dup(struct rb_root *root,
+				       struct rb_node *new,
+				       rb_cmp_t cmp)
+{
+	struct rb_node **n = &root->rb_node, *parent = NULL;
+
+	while (*n) {
+		parent = *n;
+		n = cmp(new, *n) < 0
+			? &(*n)->rb_left
+			: &(*n)->rb_right;
+	}
+
+	rb_link_node(new, parent, n);
+	rb_insert_color(new, root);
+}
+
+static inline struct rb_node *_rb_search(struct rb_root *root,
+					 struct rb_node *search,
+					 rb_cmp_t cmp)
+{
+	struct rb_node *n = root->rb_node;
+
+	while (n) {
+		int res = cmp(search, n);
+		if (!res)
+			return n;
+
+		n = res < 0
+			? n->rb_left
+			: n->rb_right;
+	}
+
+	return NULL;
+}
+
+static inline struct rb_node *_rb_greater(struct rb_root *root,
+					  struct rb_node *search,
+					  rb_cmp_t cmp)
+{
+	struct rb_node *n = root->rb_node;
+	struct rb_node *ret = NULL;
+
+	while (n) {
+		int res = cmp(search, n);
+
+		if (res < 0) {
+			ret = n;
+			n = n->rb_left;
+		} else {
+			n = n->rb_right;
+		}
+	}
+
+	return ret;
+}
+
+int rb_insert(struct rb_root *root, struct rb_node *new, rb_cmp_t cmp);
+void rb_insert_allow_dup(struct rb_root *root,
+			 struct rb_node *new,
+			 rb_cmp_t cmp);
+struct rb_node *rb_search(struct rb_root *root,
+			  struct rb_node *search,
+			  rb_cmp_t cmp);
+struct rb_node *rb_greater(struct rb_root *root,
+			   struct rb_node *search,
+			   rb_cmp_t cmp);
+
+#define container_of_or_null(ptr, type, member)				\
+({									\
+	typeof(ptr) _ptr = ptr;						\
+	_ptr ? container_of(_ptr, type, member) : NULL;			\
+})
+
+#define RB_FIRST(root, type, member)					\
+	container_of_or_null(rb_first(root), type, member)
+
+#define RB_LAST(root, type, member)					\
+	container_of_or_null(rb_last(root), type, member)
+
+#define RB_NEXT(ptr, member)						\
+	container_of_or_null(rb_next(&(ptr)->member), typeof(*ptr), member)
+
+#define RB_PREV(ptr, member)						\
+	container_of_or_null(rb_prev(&(ptr)->member), typeof(*ptr), member)
+
 #endif	/* _LINUX_RBTREE_H */
diff --git a/lib/rbtree.c b/lib/rbtree.c
index d417556..53641b7 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -135,6 +135,34 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 }
 EXPORT_SYMBOL(rb_insert_color);
 
+int rb_insert(struct rb_root *root, struct rb_node *new, rb_cmp_t cmp)
+{
+	return _rb_insert(root, new, cmp);
+}
+EXPORT_SYMBOL(rb_insert);
+
+void rb_insert_allow_dup(struct rb_root *root, struct rb_node *new, rb_cmp_t cmp)
+{
+	_rb_insert_allow_dup(root, new, cmp);
+}
+EXPORT_SYMBOL(rb_insert_allow_dup);
+
+struct rb_node *rb_search(struct rb_root *root,
+			  struct rb_node *search,
+			  rb_cmp_t cmp)
+{
+	return _rb_search(root, search, cmp);
+}
+EXPORT_SYMBOL(rb_search);
+
+struct rb_node *rb_greater(struct rb_root *root,
+			   struct rb_node *search,
+			   rb_cmp_t cmp)
+{
+	return _rb_greater(root, search, cmp);
+}
+EXPORT_SYMBOL(rb_greater);
+
 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 			     struct rb_root *root)
 {
-- 
1.7.9.3.327.g2980b

Re: [PATCH 1/3] rbtree: Add rb_insert(), rb_search(), etc.

[Tejun Heo]

Hello, Kent.

Please cc akpm.

On Fri, May 25, 2012 at 01:57:39PM -0700, Kent Overstreet wrote:
> Change-Id: I072d94a42b75454aa62be849c724980d27523b08
> 
> Signed-off-by: Kent Overstreet <koverstreet@google.com>

Same complaints.

And function comments please.

> +static inline int _rb_insert(struct rb_root *root,
> +			     struct rb_node *new,
> +			     rb_cmp_t cmp)
> +{
> +	struct rb_node **n = &root->rb_node, *parent = NULL;
> +	int res;
> +
> +	while (*n) {
> +		parent = *n;
> +		res = cmp(new, *n);
> +		if (!res)
> +			return -1;

-EINVAL?

> +		n = res < 0
> +			? &(*n)->rb_left
> +			: &(*n)->rb_right;

I don't know.  I'm finding this formatting rather weird.  If ?: has to
be used and line has to break, how about the following?

		n = res < 0 ? A
			    : B;

Or how about using good'ol if else?

	if (res < 0)
		n = A;
	else if (res > 0)
		n = B;
	else
		return -EINVAL;

> +	}
> +
> +	rb_link_node(new, parent, n);
> +	rb_insert_color(new, root);
> +	return 0;
> +}
> +
> +static inline void _rb_insert_allow_dup(struct rb_root *root,
> +				       struct rb_node *new,
> +				       rb_cmp_t cmp)
> +{
> +	struct rb_node **n = &root->rb_node, *parent = NULL;
> +
> +	while (*n) {
> +		parent = *n;
> +		n = cmp(new, *n) < 0
> +			? &(*n)->rb_left
> +			: &(*n)->rb_right;

Ditto.

> +	}
> +
> +	rb_link_node(new, parent, n);
> +	rb_insert_color(new, root);
> +}
> +
> +static inline struct rb_node *_rb_search(struct rb_root *root,
> +					 struct rb_node *search,
> +					 rb_cmp_t cmp)
> +{
> +	struct rb_node *n = root->rb_node;
> +
> +	while (n) {
> +		int res = cmp(search, n);
> +		if (!res)
> +			return n;
> +
> +		n = res < 0
> +			? n->rb_left
> +			: n->rb_right;
> +	}
> +
> +	return NULL;
> +}
> +
> +static inline struct rb_node *_rb_greater(struct rb_root *root,
> +					  struct rb_node *search,
> +					  rb_cmp_t cmp)
> +{
> +	struct rb_node *n = root->rb_node;
> +	struct rb_node *ret = NULL;
> +
> +	while (n) {
> +		int res = cmp(search, n);
> +
> +		if (res < 0) {
> +			ret = n;
> +			n = n->rb_left;
> +		} else {
> +			n = n->rb_right;
> +		}
> +	}
> +
> +	return ret;
> +}

What does _rb_greater() do?  If these are gonna be inlined, can't we
mostly just have single lookup function which returns either the found
node or insertion position and let each wrapper deal with the
specifics?

Thanks.

-- 
tejun

[PATCH 2/3] timerqueue: convert to generic rb tree code

[Kent Overstreet]

Change-Id: Ib31c42c037203b7eb78515673475130db9fa6b0b

Signed-off-by: Kent Overstreet <koverstreet@google.com>
---
 lib/timerqueue.c |   23 +++++++++--------------
 1 file changed, 9 insertions(+), 14 deletions(-)

diff --git a/lib/timerqueue.c b/lib/timerqueue.c
index a382e4a..3014abe 100644
--- a/lib/timerqueue.c
+++ b/lib/timerqueue.c
@@ -27,6 +27,14 @@
 #include <linux/rbtree.h>
 #include <linux/export.h>
 
+static int timerqueue_cmp(struct rb_node *l, struct rb_node *r)
+{
+	return clamp_t(int64_t,
+		       rb_entry(l, struct timerqueue_node, node)->expires.tv64 -
+		       rb_entry(r, struct timerqueue_node, node)->expires.tv64,
+		       -1, 1);
+}
+
 /**
  * timerqueue_add - Adds timer to timerqueue.
  *
@@ -38,23 +46,10 @@
  */
 void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
 {
-	struct rb_node **p = &head->head.rb_node;
-	struct rb_node *parent = NULL;
-	struct timerqueue_node  *ptr;
-
 	/* Make sure we don't add nodes that are already added */
 	WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
 
-	while (*p) {
-		parent = *p;
-		ptr = rb_entry(parent, struct timerqueue_node, node);
-		if (node->expires.tv64 < ptr->expires.tv64)
-			p = &(*p)->rb_left;
-		else
-			p = &(*p)->rb_right;
-	}
-	rb_link_node(&node->node, parent, p);
-	rb_insert_color(&node->node, &head->head);
+	rb_insert_allow_dup(&head->head, &node->node, timerqueue_cmp);
 
 	if (!head->next || node->expires.tv64 < head->next->expires.tv64)
 		head->next = node;
-- 
1.7.9.3.327.g2980b

[PATCH 3/3] block: convert elevator to generic rb tree code

[Kent Overstreet]

Change-Id: I676968e201f0de9a0d0a7813e2fcc6873343e8c3

Signed-off-by: Kent Overstreet <koverstreet@google.com>
---
 block/elevator.c |   42 ++++++++++++------------------------------
 1 file changed, 12 insertions(+), 30 deletions(-)

diff --git a/block/elevator.c b/block/elevator.c
index f016855..7429682 100644
--- a/block/elevator.c
+++ b/block/elevator.c
@@ -295,28 +295,21 @@ static struct request *elv_rqhash_find(struct request_queue *q, sector_t offset)
 	return NULL;
 }
 
+static int elv_rb_cmp(struct rb_node *l, struct rb_node *r)
+{
+	return clamp_t(int64_t,
+		       blk_rq_pos(rb_entry(l, struct request, rb_node)) -
+		       blk_rq_pos(rb_entry(r, struct request, rb_node)),
+		       -1, 1);
+}
+
 /*
  * RB-tree support functions for inserting/lookup/removal of requests
  * in a sorted RB tree.
  */
 void elv_rb_add(struct rb_root *root, struct request *rq)
 {
-	struct rb_node **p = &root->rb_node;
-	struct rb_node *parent = NULL;
-	struct request *__rq;
-
-	while (*p) {
-		parent = *p;
-		__rq = rb_entry(parent, struct request, rb_node);
-
-		if (blk_rq_pos(rq) < blk_rq_pos(__rq))
-			p = &(*p)->rb_left;
-		else if (blk_rq_pos(rq) >= blk_rq_pos(__rq))
-			p = &(*p)->rb_right;
-	}
-
-	rb_link_node(&rq->rb_node, parent, p);
-	rb_insert_color(&rq->rb_node, root);
+	rb_insert_allow_dup(root, &rq->rb_node, elv_rb_cmp);
 }
 EXPORT_SYMBOL(elv_rb_add);
 
@@ -330,21 +323,10 @@ EXPORT_SYMBOL(elv_rb_del);
 
 struct request *elv_rb_find(struct rb_root *root, sector_t sector)
 {
-	struct rb_node *n = root->rb_node;
-	struct request *rq;
-
-	while (n) {
-		rq = rb_entry(n, struct request, rb_node);
+	struct request search = { .__sector = sector };
+	struct rb_node *r = _rb_search(root, &search.rb_node, elv_rb_cmp);
 
-		if (sector < blk_rq_pos(rq))
-			n = n->rb_left;
-		else if (sector > blk_rq_pos(rq))
-			n = n->rb_right;
-		else
-			return rq;
-	}
-
-	return NULL;
+	return container_of_or_null(r, struct request, rb_node);
 }
 EXPORT_SYMBOL(elv_rb_find);
 
-- 
1.7.9.3.327.g2980b

Re: [PATCH 3/3] block: convert elevator to generic rb tree code

[Tejun Heo]

On Fri, May 25, 2012 at 01:57:41PM -0700, Kent Overstreet wrote:
> Change-Id: I676968e201f0de9a0d0a7813e2fcc6873343e8c3
> 
> Signed-off-by: Kent Overstreet <koverstreet@google.com>

You know what I was gonna complain about here, right?  :)

>  struct request *elv_rb_find(struct rb_root *root, sector_t sector)
>  {
> -	struct rb_node *n = root->rb_node;
> -	struct request *rq;
> -
> -	while (n) {
> -		rq = rb_entry(n, struct request, rb_node);
> +	struct request search = { .__sector = sector };

This is dangerous.  You can't put things like struct request on stack.
It might look like it's working ok on the tested setup but archs
differ in stack pressure and more importantly people may add
arbitrarily sized fields, including debugging stuff, to struct
request.  So, no, please don't do that.

Thanks.

-- 
tejun

Re: [PATCH 3/3] block: convert elevator to generic rb tree code

[Kent Overstreet]

On Tue, May 29, 2012 at 08:17:17AM +0900, Tejun Heo wrote:
> On Fri, May 25, 2012 at 01:57:41PM -0700, Kent Overstreet wrote:
> > Change-Id: I676968e201f0de9a0d0a7813e2fcc6873343e8c3
> > 
> > Signed-off-by: Kent Overstreet <koverstreet@google.com>
> 
> You know what I was gonna complain about here, right?  :)

Yep :P

> >  struct request *elv_rb_find(struct rb_root *root, sector_t sector)
> >  {
> > -	struct rb_node *n = root->rb_node;
> > -	struct request *rq;
> > -
> > -	while (n) {
> > -		rq = rb_entry(n, struct request, rb_node);
> > +	struct request search = { .__sector = sector };
> 
> This is dangerous.  You can't put things like struct request on stack.
> It might look like it's working ok on the tested setup but archs
> differ in stack pressure and more importantly people may add
> arbitrarily sized fields, including debugging stuff, to struct
> request.  So, no, please don't do that.

I was telling you about this exact issue before - and I looked at the
assembly to make sure that when the inlined version of rb_search() was
used the struct request on the stack was optimized away, and it was.

So in practice there's no extra stack usage. Whether this is an
optimization we want to depend I'm not going to say; I suspect it's
pretty safe w.r.t. the optimizer but it's definitely sketchy and if at
some point someone came along and switched it to the uninline version
we'd have problems.

So we might want to leave this one open coded. Which would make me sad,
but I can't think of a sane way of implementing generic rb_search() that
doesn't require passing it a type t to compare against.

I dunno.

Re: [PATCH 3/3] block: convert elevator to generic rb tree code

[Tejun Heo]

Hello, Kent.

On Mon, May 28, 2012 at 11:25:02PM -0400, Kent Overstreet wrote:
> On Tue, May 29, 2012 at 08:17:17AM +0900, Tejun Heo wrote:
> > This is dangerous.  You can't put things like struct request on stack.
> > It might look like it's working ok on the tested setup but archs
> > differ in stack pressure and more importantly people may add
> > arbitrarily sized fields, including debugging stuff, to struct
> > request.  So, no, please don't do that.
> 
> I was telling you about this exact issue before - and I looked at the
> assembly to make sure that when the inlined version of rb_search() was
> used the struct request on the stack was optimized away, and it was.
> 
> So in practice there's no extra stack usage. Whether this is an
> optimization we want to depend I'm not going to say; I suspect it's
> pretty safe w.r.t. the optimizer but it's definitely sketchy and if at
> some point someone came along and switched it to the uninline version
> we'd have problems.

I don't think we can depend on that.  Note that compiler may as well
decide not to inline an inline function (e.g. if it sees many calling
instances).  Depending on such behavior is way too fragile.

> So we might want to leave this one open coded. Which would make me sad,
> but I can't think of a sane way of implementing generic rb_search() that
> doesn't require passing it a type t to compare against.

I don't know either.  Open coding isn't the end of the world but I
suspect a lot of data structures which go on rbtree wouldn't be stack
friendly, so having common helper which can't handle that might not be
too helpful.

Thanks.

--
tejun

Re: [PATCH 3/3] block: convert elevator to generic rb tree code

[Kent Overstreet]

On Tue, May 29, 2012 at 02:24:58PM +0900, Tejun Heo wrote:
> > So in practice there's no extra stack usage. Whether this is an
> > optimization we want to depend I'm not going to say; I suspect it's
> > pretty safe w.r.t. the optimizer but it's definitely sketchy and if at
> > some point someone came along and switched it to the uninline version
> > we'd have problems.
> 
> I don't think we can depend on that.  Note that compiler may as well
> decide not to inline an inline function (e.g. if it sees many calling
> instances).  Depending on such behavior is way too fragile.

Bah, I forgot about the compiler uninlining stuff. There's
__always_inline, but... yeah, I agree, too dangerous.

> > So we might want to leave this one open coded. Which would make me sad,
> > but I can't think of a sane way of implementing generic rb_search() that
> > doesn't require passing it a type t to compare against.
> 
> I don't know either.  Open coding isn't the end of the world but I
> suspect a lot of data structures which go on rbtree wouldn't be stack
> friendly, so having common helper which can't handle that might not be
> too helpful.

There's > 100 users in the kernel, I have no clue what the average size
of the containing struct is.

I think I'm gonna split rb_search() out into its own patch, as
rb_insert() fortunately doesn't have this problem.

I'm starting to think the sanest solution is a macro (not quite my
original RB_SEARCH() macro, though).

Re: [PATCH 0/3] Generic rb tree code

[Tejun Heo]

On Fri, May 25, 2012 at 01:57:38PM -0700, Kent Overstreet wrote:
> Right now, users of the rb tree code have to open code their own search and
> insert functions. This provides generic versions that you pass a comparison
> function to.
> 
> I highly doubt the extra function calls are going to have a measurable
> performance impact in practice - the pointer chasing is going to dominate. I
> did provide inline versions just in case, though - it's modelled after the
> spinlock code.

Modeled after spinlock code how?  AFAICS, spinlock code doesn't
present inline and !inline versions to users.  All the current users
are inline anyway, why not just provide inlined versions and worry
about whether inlining is beneifical in a separate patch?

Thanks.

-- 
tejun

Re: [PATCH 0/3] Generic rb tree code

[Kent Overstreet]

On Tue, May 29, 2012 at 08:22:46AM +0900, Tejun Heo wrote:
> On Fri, May 25, 2012 at 01:57:38PM -0700, Kent Overstreet wrote:
> > Right now, users of the rb tree code have to open code their own search and
> > insert functions. This provides generic versions that you pass a comparison
> > function to.
> > 
> > I highly doubt the extra function calls are going to have a measurable
> > performance impact in practice - the pointer chasing is going to dominate. I
> > did provide inline versions just in case, though - it's modelled after the
> > spinlock code.
> 
> Modeled after spinlock code how?  AFAICS, spinlock code doesn't
> present inline and !inline versions to users. 

That probably wasn't intended, but it's how it works out.
__raw_spin_lock() and all the variants are defined as inline functions,
and then depending on whether CONFIG_INLINE_BLAH is enabled
_raw_spin_lock_blah() is defined to __raw_spin_lock_blah(), otherwise
_raw_spin_lock_blah() is a wrapper in a .c file.

But the end result is that the inline versions are also available.

> All the current users
> are inline anyway, why not just provide inlined versions and worry
> about whether inlining is beneifical in a separate patch?

Yeah, possible. I think it's only going to be an issue for rb_search()
in practice (since rb_search needs the stack allocated search argument),
should probably just drop the inline version of rb_insert().

Re: [PATCH 0/3] Generic rb tree code

[Tejun Heo]

Hello, Kent.

On Mon, May 28, 2012 at 11:30:32PM -0400, Kent Overstreet wrote:
> > Modeled after spinlock code how?  AFAICS, spinlock code doesn't
> > present inline and !inline versions to users. 
> 
> That probably wasn't intended, but it's how it works out.
> __raw_spin_lock() and all the variants are defined as inline functions,
> and then depending on whether CONFIG_INLINE_BLAH is enabled
> _raw_spin_lock_blah() is defined to __raw_spin_lock_blah(), otherwise
> _raw_spin_lock_blah() is a wrapper in a .c file.
> 
> But the end result is that the inline versions are also available.

Doesn't matter.  Nobody outside spinlock implementation proper should
be using them.

> > All the current users
> > are inline anyway, why not just provide inlined versions and worry
> > about whether inlining is beneifical in a separate patch?
> 
> Yeah, possible. I think it's only going to be an issue for rb_search()
> in practice (since rb_search needs the stack allocated search argument),
> should probably just drop the inline version of rb_insert().

As long as there's single version of the thing....

Thanks.

-- 
tejun

Re: [PATCH 0/3] Generic rb tree code

[Jan Kara]

On Fri 25-05-12 13:57:38, Kent Overstreet wrote:
> Right now, users of the rb tree code have to open code their own search and
> insert functions. This provides generic versions that you pass a comparison
> function to.
> 
> I highly doubt the extra function calls are going to have a measurable
> performance impact in practice - the pointer chasing is going to dominate. I
> did provide inline versions just in case, though - it's modelled after the
> spinlock code.
> 
> The inline version of rb_search() is important for another reason, though - you
> have to pass rb_search a pointer to your struct for it to compare against,
> which has to be allocated on the stack. For most users I think that'll be fine,
> but for the elevator code struct rb_node is embedded in struct request, which
> is rather large. By using the inline version that stack allocation goes away.
> 
> (I looked at the generated assembly of elv_rb_find() before and after, and if
> I'm reading it right it's not using any extra stack. Code is a bit worse, but
> IMO removing code duplication is worth it).
> 
> Kent Overstreet (3):
>   rbtree: Add rb_insert(), rb_search(), etc.
>   timerqueue: convert to generic rb tree code
>   block: convert elevator to generic rb tree code
  Hum, are you aware of another generic rb-tree attempt -
 https://lkml.org/lkml/2012/4/30/132 ?

								Honza
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR