Skip to contentSkip to conversation

Shrink rbtree

PATCH In review David Woodhouse 8 participants 18 messages Apr 21, 2006 – Apr 23, 2006

Subsystems (7)
lore
Share & tools
lore

David Woodhouse

author maintainer
#0 lore raw

PATCH 1/1 Shrink rbtree

Our rbtree implementation uses a whole integer for colour information. In fact, because of alignment constraints on a 64-bit machine it'll be a whole 64 bits there. We only need a single bit, though -- and we know the pointers are always going to be aligned. So let's just use the lowest bit of the parent pointer instead. This shrinks the rb_node from 4 machine-words to 3.

This doesn't change the documented mode of using rbtrees -- users weren't encouraged to use the parent pointers directly anyway. But we add new accessor macros rb_parent(), rb_is_red() etc. and a few places do need changing to use them.

Some users were just abusing the colour to mark a node as being off-tree, and I've switched those to use same method for that as eventpoll.c does -- setting the parent pointer to point to itself.

There's also an obvious optimisation to rb_erase() which jumped out at me while I was passing.

Full patch below -- individual changes are in a git tree at
git://git.infradead.org/~dwmw2/rbtree-2.6 or viewable by gitweb at
http://git.infradead.org/?p=users/dwmw2/rbtree-2.6.git

[RBTREE] Merge colour and parent fields of struct rb_node. [RBTREE] Remove dead code in rb_erase()
[RBTREE] Update JFFS2 to use rb_parent() accessor macro. [RBTREE] Update eventpoll.c to use rb_parent() accessor macro. [RBTREE] Update key.c to use rb_parent() accessor macro. [RBTREE] Update ext3 to use rb_parent() accessor macro. [RBTREE] Change rbtree off-tree marking in I/O schedulers. [RBTREE] Add accessor macros for colour and parent fields of rb_node

Another pair of eyes on the 'remove dead code in rb_erase()' bit in particular would be appreciated. That's
http://git.infradead.org/?p=users/dwmw2/rbtree-2.6.git;a=commitdiff;h=1975e59375756da4ff4e6e7d12f67485e813ace0

block/as-iosched.c +2 -3
index e25a5d7..ed336ab 100644
@@ -353,10 +353,9 @@ static struct request *as_find_arq_hash(
 /*
  * rb tree support functions
  */
-#define RB_NONE		(2)
 #define RB_EMPTY(root)	((root)->rb_node == NULL)
-#define ON_RB(node)	((node)->rb_color != RB_NONE)
-#define RB_CLEAR(node)	((node)->rb_color = RB_NONE)
+#define ON_RB(node)	(rb_parent(node) != node)
+#define RB_CLEAR(node)	(rb_set_parent(node, node))
 #define rb_entry_arq(node)	rb_entry((node), struct as_rq, rb_node)
 #define ARQ_RB_ROOT(ad, arq)	(&(ad)->sort_list[(arq)->is_sync])
 #define rq_rb_key(rq)		(rq)->sector
block/cfq-iosched.c +1 -7
index 2540dfa..01c416b 100644
@@ -60,14 +60,9 @@ #define RQ_DATA(rq)		(rq)->elevator_priv
 /*
  * rb-tree defines
  */
-#define RB_NONE			(2)
 #define RB_EMPTY(node)		((node)->rb_node == NULL)
-#define RB_CLEAR_COLOR(node)	(node)->rb_color = RB_NONE
 #define RB_CLEAR(node)		do {	\
-	(node)->rb_parent = NULL;	\
-	RB_CLEAR_COLOR((node));		\
-	(node)->rb_right = NULL;	\
-	(node)->rb_left = NULL;		\
+		memset(node, 0, sizeof(*node)); \
 } while (0)
 #define RB_CLEAR_ROOT(root)	((root)->rb_node = NULL)
 #define rb_entry_crq(node)	rb_entry((node), struct cfq_rq, rb_node)
@@ -563,7 +558,6 @@ static inline void cfq_del_crq_rb(struct
 	cfq_update_next_crq(crq);
 
 	rb_erase(&crq->rb_node, &cfqq->sort_list);
-	RB_CLEAR_COLOR(&crq->rb_node);
 
 	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY(&cfqq->sort_list))
 		cfq_del_cfqq_rr(cfqd, cfqq);
block/deadline-iosched.c +2 -3
index 399fa1e..06962d8 100644
@@ -165,10 +165,9 @@ deadline_find_drq_hash(struct deadline_d
 /*
  * rb tree support functions
  */
-#define RB_NONE		(2)
 #define RB_EMPTY(root)	((root)->rb_node == NULL)
-#define ON_RB(node)	((node)->rb_color != RB_NONE)
-#define RB_CLEAR(node)	((node)->rb_color = RB_NONE)
+#define ON_RB(node)	(rb_parent(node) != node)
+#define RB_CLEAR(node)	(rb_set_parent(node, node))
 #define rb_entry_drq(node)	rb_entry((node), struct deadline_rq, rb_node)
 #define DRQ_RB_ROOT(dd, drq)	(&(dd)->sort_list[rq_data_dir((drq)->request)])
 #define rq_rb_key(rq)		(rq)->sector
fs/eventpoll.c +3 -3
index 1b4491c..2695337 100644
@@ -337,20 +337,20 @@ static inline int ep_cmp_ffd(struct epol
 /* Special initialization for the rb-tree node to detect linkage */
 static inline void ep_rb_initnode(struct rb_node *n)
 {
-	n->rb_parent = n;
+	rb_set_parent(n, n);
 }
 
 /* Removes a node from the rb-tree and marks it for a fast is-linked check */
 static inline void ep_rb_erase(struct rb_node *n, struct rb_root *r)
 {
 	rb_erase(n, r);
-	n->rb_parent = n;
+	rb_set_parent(n, n);
 }
 
 /* Fast check to verify that the item is linked to the main rb-tree */
 static inline int ep_rb_linked(struct rb_node *n)
 {
-	return n->rb_parent != n;
+	return rb_parent(n) != n;
 }
 
 /*
fs/ext3/dir.c +1 -1
index f37528e..fbb0d4e 100644
@@ -284,7 +284,7 @@ static void free_rb_tree_fname(struct rb
 		 * beginning of the loop and try to free the parent
 		 * node.
 		 */
-		parent = n->rb_parent;
+		parent = rb_parent(n);
 		fname = rb_entry(n, struct fname, rb_hash);
 		while (fname) {
 			struct fname * old = fname;
fs/jffs2/nodelist.h +0 -1
index 23a67bb..131b67b 100644
@@ -299,7 +299,6 @@ static inline struct jffs2_node_frag *fr
 	return rb_entry(node, struct jffs2_node_frag, rb);
 }
 
-#define rb_parent(rb) ((rb)->rb_parent)
 #define frag_next(frag) rb_entry(rb_next(&(frag)->rb), struct jffs2_node_frag, rb)
 #define frag_prev(frag) rb_entry(rb_prev(&(frag)->rb), struct jffs2_node_frag, rb)
 #define frag_parent(frag) rb_entry(rb_parent(&(frag)->rb), struct jffs2_node_frag, rb)
fs/jffs2/readinode.c +9 -9
index f169564..6f4a7d8 100644
@@ -66,7 +66,7 @@ static void jffs2_free_tmp_dnode_info_li
 			jffs2_free_full_dnode(tn->fn);
 			jffs2_free_tmp_dnode_info(tn);
 
-			this = this->rb_parent;
+			this = rb_parent(this);
 			if (!this)
 				break;
 
@@ -679,12 +679,12 @@ static int jffs2_do_read_inode_internal(
 			jffs2_mark_node_obsolete(c, fn->raw);
 
 		BUG_ON(rb->rb_left);
-		if (rb->rb_parent && rb->rb_parent->rb_left == rb) {
+		if (rb_parent(rb) && rb_parent(rb)->rb_left == rb) {
 			/* We were then left-hand child of our parent. We need
 			 * to move our own right-hand child into our place. */
 			repl_rb = rb->rb_right;
 			if (repl_rb)
-				repl_rb->rb_parent = rb->rb_parent;
+				rb_set_parent(repl_rb, rb_parent(rb));
 		} else
 			repl_rb = NULL;
 
@@ -692,14 +692,14 @@ static int jffs2_do_read_inode_internal(
 
 		/* Remove the spent tn from the tree; don't bother rebalancing
 		 * but put our right-hand child in our own place. */
-		if (tn->rb.rb_parent) {
-			if (tn->rb.rb_parent->rb_left == &tn->rb)
-				tn->rb.rb_parent->rb_left = repl_rb;
-			else if (tn->rb.rb_parent->rb_right == &tn->rb)
-				tn->rb.rb_parent->rb_right = repl_rb;
+		if (rb_parent(&tn->rb)) {
+			if (rb_parent(&tn->rb)->rb_left == &tn->rb)
+				rb_parent(&tn->rb)->rb_left = repl_rb;
+			else if (rb_parent(&tn->rb)->rb_right == &tn->rb)
+				rb_parent(&tn->rb)->rb_right = repl_rb;
 			else BUG();
 		} else if (tn->rb.rb_right)
-			tn->rb.rb_right->rb_parent = NULL;
+			rb_set_parent(tn->rb.rb_right, NULL);
 
 		jffs2_free_tmp_dnode_info(tn);
 		if (ret) {
include/linux/rbtree.h +19 -4
index 4b7cc4f..748be50 100644
@@ -99,8 +99,7 @@ #include <linux/stddef.h>
 
 struct rb_node
 {
-	struct rb_node *rb_parent;
-	int rb_color;
+	unsigned long  rb_parent_colour;
 #define	RB_RED		0
 #define	RB_BLACK	1
 	struct rb_node *rb_right;
@@ -112,6 +111,23 @@ struct rb_root
 	struct rb_node *rb_node;
 };
 
+
+#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_colour & ~3))
+#define rb_colour(r)   ((r)->rb_parent_colour & 1)
+#define rb_is_red(r)   (!rb_colour(r))
+#define rb_is_black(r) rb_colour(r)
+#define rb_set_red(r)  do { (r)->rb_parent_colour &= ~1; } while (0)
+#define rb_set_black(r)  do { (r)->rb_parent_colour |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+	rb->rb_parent_colour = (rb->rb_parent_colour & 3) | (unsigned long)p;
+}
+static inline void rb_set_colour(struct rb_node *rb, int colour)
+{
+	rb->rb_parent_colour = (rb->rb_parent_colour & ~1) | colour;
+}
+
 #define RB_ROOT	(struct rb_root) { NULL, }
 #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
 
@@ -131,8 +147,7 @@ extern void rb_replace_node(struct rb_no
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
 				struct rb_node ** rb_link)
 {
-	node->rb_parent = parent;
-	node->rb_color = RB_RED;
+	node->rb_parent_colour = (unsigned long )parent;
 	node->rb_left = node->rb_right = NULL;
 
 	*rb_link = node;
lib/rbtree.c +93 -96

366 lines not on this page · raw message

security/keys/key.c +4 -4
index b6061fa..3fdc49c 100644
@@ -211,12 +211,12 @@ static inline void key_alloc_serial(stru
 			key->serial = 2;
 		key_serial_next = key->serial + 1;
 
-		if (!parent->rb_parent)
+		if (!rb_parent(parent))
 			p = &key_serial_tree.rb_node;
-		else if (parent->rb_parent->rb_left == parent)
-			p = &parent->rb_parent->rb_left;
+		else if (rb_parent(parent)->rb_left == parent)
+			p = &(rb_parent(parent)->rb_left);
 		else
-			p = &parent->rb_parent->rb_right;
+			p = &(rb_parent(parent)->rb_right);
 
 		parent = rb_next(parent);
 		if (!parent)
Signature · 1 line
dwmw2
#1 lore raw
Quoted 4 lines

the pointers are always going to be aligned. So let's just use the lowest bit of the parent pointer instead. This shrinks the rb_node from 4 machine-words to 3.

We've seen this patch before, haven't we? :) I still like it.

Quoted 2 lines

Another pair of eyes on the 'remove dead code in rb_erase()' bit in particular would be appreciated.

I'll trade you some eyes for a description beyond the four words obvious, remove, dead, and code.

include/linux/rbtree.h #include <linux/stddef.h> · line 102

Quoted 5 lines

struct rb_node
{

include/linux/rbtree.h +1 -2
-	struct rb_node *rb_parent;
-	int rb_color;
+	unsigned long  rb_parent_colour;

How about some kerneldoc comments?

Quoted 4 lines

#define RB_RED 0
#define RB_BLACK 1

+#define rb_colour(r) ((r)->rb_parent_colour & 1)

This creates a pretty strong bond between the two.. maybe a RB_COLOUR_MASK and use that and the _RED/_BLACK defines instead of the raw constants?

include/linux/rbtree.h struct rb_root · line 123

Quoted 7 lines
include/linux/rbtree.h +7 -0
+#define rb_is_red(r)   (!rb_colour(r))
+#define rb_is_black(r) rb_colour(r)
+#define rb_set_red(r)  do { (r)->rb_parent_colour &= ~1; } while (0)
+#define rb_set_black(r)  do { (r)->rb_parent_colour |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
	BUG_ON((unsigned long)p & 3);
Quoted 11 lines
include/linux/rbtree.h +7 -0
+	rb->rb_parent_colour = (rb->rb_parent_colour & 3) | (unsigned long)p;
+}
+static inline void rb_set_colour(struct rb_node *rb, int colour)
+{
+	rb->rb_parent_colour = (rb->rb_parent_colour & ~1) | colour;
+}
+
 #define RB_ROOT	(struct rb_root) { NULL, }
 #define	rb_entry(ptr, type, member) container_of(ptr, type, member)

include/linux/rbtree.h extern void rb_replace_node(struct rb_no · line 150

Quoted 6 lines
include/linux/rbtree.h +1 -2
@@ -131,8 +147,7 @@ extern void rb_replace_node(struct rb_no
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
 				struct rb_node ** rb_link)
 {
-	node->rb_parent = parent;
-	node->rb_color = RB_RED;
+	node->rb_parent_colour = (unsigned long )parent;

use rb_set_parent(node, parent) and get the assertion.

- z

author maintainer
#2 lore raw
Quoted 5 lines · Zach Brown
Quoted 3 lines

the pointers are always going to be aligned. So let's just use the lowest bit of the parent pointer instead. This shrinks the rb_node from 4 machine-words to 3.

We've seen this patch before, haven't we? :) I still like it.

Maybe. I thought I'd actually done it once before, but I couldn't actually find it when I went looking. It should save about 40KiB of RAM on my Nokia 770, because I should get 145 jffs2_node_frag objects in each slab page instead of only 127 -- so yes, I like it too :)

Quoted 5 lines
Quoted 2 lines

Another pair of eyes on the 'remove dead code in rb_erase()' bit in particular would be appreciated.

I'll trade you some eyes for a description beyond the four words obvious, remove, dead, and code.

Plenty more words in the git commit. They don't make much sense without the patch right below them, and you can see them in juxtaposition at
http://git.infradead.org/?p=users/dwmw2/rbtree-2.6.git;a=commitdiff;h=1975e59375756da4ff4e6e7d12f67485e813ace0

Quoted 8 lines
Quoted 4 lines

#define RB_RED 0
#define RB_BLACK 1

+#define rb_colour(r) ((r)->rb_parent_colour & 1)

This creates a pretty strong bond between the two.. maybe a RB_COLOUR_MASK and use that and the _RED/_BLACK defines instead of the raw constants?

I think it's be better just to drop the RB_RED and RB_BLACK definitions.

Quoted 4 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
	BUG_ON((unsigned long)p & 3);

Yeah, I suppose we could.

Quoted 9 lines

include/linux/rbtree.h extern void rb_replace_node(struct rb_no · line 150

Quoted 7 lines
include/linux/rbtree.h +1 -2
@@ -131,8 +147,7 @@ extern void rb_replace_node(struct rb_no
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
 				struct rb_node ** rb_link)
 {
-	node->rb_parent = parent;
-	node->rb_color = RB_RED;
+	node->rb_parent_colour = (unsigned long )parent;

use rb_set_parent(node, parent) and get the assertion.

Que?

Signature · 1 line
dwmw2
#3 lore raw
Quoted 3 lines

Maybe. I thought I'd actually done it once before, but I couldn't actually find it when I went looking.

Yeah, that's what I remember too.

Quoted 1 line

Plenty more words in the git commit.

Ah! of course, thanks.

Quoted 3 lines

They don't make much sense without
the patch right below them, and you can see them in juxtaposition at
http://git.infradead.org/?p=users/dwmw2/rbtree-2.6.git;a=commitdiff;h=1975e59375756da4ff4e6e7d12f67485e813ace0

Indeed, that reasoning looks sound. First the if (parent) .. else {} falls away, then the parent left/right relationship is folded into the test with old. Looks good.

Quoted 1 line

I think it's be better just to drop the RB_RED and RB_BLACK definitions.

I'd agree, I figured you'd left them for a reason.

Quoted 10 lines
Quoted 3 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
	BUG_ON((unsigned long)p & 3);

Yeah, I suppose we could.

Quoted 2 lines

include/linux/rbtree.h extern void rb_replace_node(struct rb_no · line 150

Quoted 1 line
include/linux/rbtree.h +1 -0
+	node->rb_parent_colour = (unsigned long )parent;

use rb_set_parent(node, parent) and get the assertion.

Que?

I meant that if we add the BUG_ON() to rb_set_parent() then we might as well reuse it here..

- z

#4 lore raw
In reply to David Woodhouse

Hi David,

Doesn't seem like a bad idea...

Quoted 4 lines · David Woodhouse

Our rbtree implementation uses a whole integer for colour information. In fact, because of alignment constraints on a 64-bit machine it'll be a whole 64 bits there. We only need a single bit, though -- and we know the pointers are always going to be aligned. So let's just use the

How do we know the pointers are always going to be aligned? IIRC struct address_space needed to be explicitly aligned when doing this trick in page->mapping because some platform byte aligned it.

Nick

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
author maintainer
#5 lore raw
Quoted 3 lines · Nick Piggin

How do we know the pointers are always going to be aligned? IIRC struct address_space needed to be explicitly aligned when doing this trick in page->mapping because some platform byte aligned it.

Really? I've been doing this kind of trick with the jffs2_raw_node_ref for years. We always allocate sufficiently aligned objects.

Signature · 1 line
dwmw2
#6 lore raw
Quoted 7 lines · David Woodhouse
Quoted 3 lines · Nick Piggin

How do we know the pointers are always going to be aligned? IIRC struct address_space needed to be explicitly aligned when doing this trick in page->mapping because some platform byte aligned it.

Really? I've been doing this kind of trick with the jffs2_raw_node_ref for years. We always allocate sufficiently aligned objects.

} __attribute__((aligned(sizeof(long))));
/*
* On most architectures that alignment is already the case; but
* must be enforced here for CRIS, to let the least signficant bit
* of struct page's "mapping" pointer be used for PAGE_MAPPING_ANON. */

You can often get away with it - I notice we never added the same alignment to struct anon_vma, which in theory needed it just as much. Some accident of how structures are packed into slabs on CRIS, I suppose.

Hugh

author maintainer
#7 lore raw
Quoted 11 lines · Hugh Dickins

} __attribute__((aligned(sizeof(long))));
/*
* On most architectures that alignment is already the case; but
* must be enforced here for CRIS, to let the least signficant bit
* of struct page's "mapping" pointer be used for PAGE_MAPPING_ANON. */

You can often get away with it - I notice we never added the same alignment to struct anon_vma, which in theory needed it just as much. Some accident of how structures are packed into slabs on CRIS, I suppose.

That sounds very strange to me, but it's harmless enough to add the explicit alignment.

Signature · 1 line
dwmw2
#8 lore raw
Quoted 8 lines · David Woodhouse
Quoted 4 lines · Hugh Dickins

You can often get away with it - I notice we never added the same alignment to struct anon_vma, which in theory needed it just as much. Some accident of how structures are packed into slabs on CRIS, I suppose.

That sounds very strange to me, but it's harmless enough to add the explicit alignment.

It's occurred to me that the unusual thing about struct address_space is that it does _not_ have a slab cache of its own: it's for years been part of the struct inode itself; and I guess that exposes it to an alignment issue which slab objects themselves avoid. But still a good idea to add the explicit alignment as doc.

Hugh

#9 lore raw
In reply to David Woodhouse
Quoted 2 lines · David Woodhouse

git://git.infradead.org/~dwmw2/rbtree-2.6

include/linux/hrtimer.h: In function `hrtimer_active':
include/linux/hrtimer.h:130: structure has no member named `rb_parent'

Might I cast aspersions upon the quality of your testing?

#define HRTIMER_INACTIVE ((void *)1UL)

...

static inline int hrtimer_active(const struct hrtimer *timer)

{
	return rb_parent(timer->node) != HRTIMER_INACTIVE;
}

So we have somewhat-competing hackery here.

Testing this...

include/linux/hrtimer.h renamed from include/linux/hrtimer.h~git-rbtree-hrtimer-fix +2 -2
@@ -34,7 +34,7 @@ enum hrtimer_restart {
 	HRTIMER_RESTART,
 };
 
-#define HRTIMER_INACTIVE	((void *)1UL)
+#define HRTIMER_INACTIVE	((void *)-2)
 
 struct hrtimer_base;
 
@@ -127,7 +127,7 @@ extern ktime_t hrtimer_get_next_event(vo
 
 static inline int hrtimer_active(const struct hrtimer *timer)
 {
-	return timer->node.rb_parent != HRTIMER_INACTIVE;
+	return rb_parent(&timer->node) != HRTIMER_INACTIVE;
 }
 
 /* Forward a hrtimer so it expires after now: */

_

#10 lore raw
Quoted 3 lines · Andrew Morton

-#define HRTIMER_INACTIVE ((void *)1UL)
+#define HRTIMER_INACTIVE ((void *)-2)

I don't think that's going to work either. Let me try -4..

#11 lore raw
Quoted 7 lines · Andrew Morton
Quoted 3 lines · Andrew Morton

-#define HRTIMER_INACTIVE ((void *)1UL)
+#define HRTIMER_INACTIVE ((void *)-2)

I don't think that's going to work either. Let me try -4..

hrtimer.c has problems too. I think I'll return your patch for some warranty repairs ;)

author maintainer
#12 lore raw
In reply to Andrew Morton
Quoted 1 line · Andrew Morton

#define HRTIMER_INACTIVE ((void *)1UL)

Ah. That's newer than the kernel I tested on. Your patch isn't going to make kernel/hrtimer.c compile though, surely? Let's do it the same way everyone else marks off-tree nodes -- by setting its parent pointer to point to itself....

include/linux/hrtimer.h +1 -1
index 306acf1..7d2a1b9 100644
@@ -127,7 +127,7 @@ #endif
 
 static inline int hrtimer_active(const struct hrtimer *timer)
 {
-	return timer->node.rb_parent != HRTIMER_INACTIVE;
+	return rb_parent(&timer->node) != &timer->node;
 }
 
 /* Forward a hrtimer so it expires after now: */
kernel/hrtimer.c +2 -2
index d2a7296..04ab27d 100644
@@ -393,7 +393,7 @@ static void __remove_hrtimer(struct hrti
 	if (base->first == &timer->node)
 		base->first = rb_next(&timer->node);
 	rb_erase(&timer->node, &base->active);
-	timer->node.rb_parent = HRTIMER_INACTIVE;
+	rb_set_parent(&timer->node, &timer->node);
 }
 
 /*
@@ -578,7 +578,7 @@ void hrtimer_init(struct hrtimer *timer,
 		clock_id = CLOCK_MONOTONIC;
 
 	timer->base = &bases[clock_id];
-	timer->node.rb_parent = HRTIMER_INACTIVE;
+	rb_set_parent(&timer->node, &timer->node);
 }
 
 /**
Signature · 1 line
dwmw2
#13 lore raw

Hi David,

Quoted 7 lines · David Woodhouse
Quoted 1 line · Andrew Morton

#define HRTIMER_INACTIVE ((void *)1UL)

Ah. That's newer than the kernel I tested on. Your patch isn't going to make kernel/hrtimer.c compile though, surely? Let's do it the same way everyone else marks off-tree nodes -- by setting its parent pointer to point to itself....

Yes, but please make it a common helper, since there is a real need for it and code has to agree on the dirty hacks it uses :-)

static inline int rb_in_tree(const struct rb_node *node)

{
	return rb_parent(node) != node;
}

static inline void rb_set_off_tree(struct rb_node *node)

{
	rb_set_parent(node, node);
}

This is trivial, but gives semantics to those strange operations.

Regards

Ingo Oeser

author maintainer
#14 lore raw
Quoted 2 lines · Ingo Oeser

Yes, but please make it a common helper, since there is a real need for it and code has to agree on the dirty hacks it uses :-)

Is there a real need for it? It's all just paranoid debugging checks, isn't it? If there's a _real_ need for marking an object as being inactive because it can be reached through some means other than the rbtree, then that arguably lives in the higher-level object itself, not its rb_node.

I'm reluctant to 'bless' this practice, because we'll then get asked to set it to 'inactive' every time we take a node off the tree, to have a BUG_ON() which checks it in certain places, etc.... it's mostly pointless AFAICT.

Signature · 1 line
dwmw2
#15 lore raw

Hio David,

Quoted 4 lines · David Woodhouse

I'm reluctant to 'bless' this practice, because we'll then get asked to set it to 'inactive' every time we take a node off the tree, to have a BUG_ON() which checks it in certain places, etc.... it's mostly pointless AFAICT.

I understand your point. Can we agree on just doing this for functions which are handed off-tree and on-tree nodes and have to care for locking reasons?

It is ok for functions to enforce their API with BUG_ON(). But this part should not be generalized, since this part really depends on the user.

Each rbtree user having its own private hackery for this is wasted developer resources IMHO.

So please either provide common helpers or just delete the potential users if you think this is not needed.

I'm happy either way.

Regards

Ingo Oeser

#16 lore raw
In reply to Andrew Morton

I'm just adding Thomas Gleixner and Roman Zippel to the CC field since the part in question came from a debate to get rid of a state field in hrtimer.

http://marc.theaimsgroup.com/?l=linux-kernel&m=114215996918851&w=2

-- Steve

Quoted 52 lines · Andrew Morton
Quoted 2 lines · David Woodhouse

git://git.infradead.org/~dwmw2/rbtree-2.6

include/linux/hrtimer.h: In function `hrtimer_active':
include/linux/hrtimer.h:130: structure has no member named `rb_parent'

Might I cast aspersions upon the quality of your testing?

#define HRTIMER_INACTIVE ((void *)1UL)

...

static inline int hrtimer_active(const struct hrtimer *timer)

{
	return rb_parent(timer->node) != HRTIMER_INACTIVE;
}

So we have somewhat-competing hackery here.

Testing this...

include/linux/hrtimer.h renamed from include/linux/hrtimer.h~git-rbtree-hrtimer-fix +2 -2
@@ -34,7 +34,7 @@ enum hrtimer_restart {
 	HRTIMER_RESTART,
 };
 
-#define HRTIMER_INACTIVE	((void *)1UL)
+#define HRTIMER_INACTIVE	((void *)-2)
 
 struct hrtimer_base;
 
@@ -127,7 +127,7 @@ extern ktime_t hrtimer_get_next_event(vo
 
 static inline int hrtimer_active(const struct hrtimer *timer)
 {
-	return timer->node.rb_parent != HRTIMER_INACTIVE;
+	return rb_parent(&timer->node) != HRTIMER_INACTIVE;
 }
 
 /* Forward a hrtimer so it expires after now: */

_

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/