Shrink rbtree
Subsystems (7)
David Woodhouse
maintainerPATCH 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 atgit://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
@@ -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
@@ -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(structcfq_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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -66,7 +66,7 @@ static void jffs2_free_tmp_dnode_info_lijffs2_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
@@ -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 1struct rb_node *rb_right;
@@ -112,6 +111,23 @@ struct rb_rootstruct 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_nostatic 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
@@ -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
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_nodefrom 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_RED0
#defineRB_BLACK1+#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_nostatic 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
David Woodhouse
maintainerQuoted 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_nodefrom 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_RED0
#defineRB_BLACK1+#define
rb_colour(r)((r)->rb_parent_colour & 1)This creates a pretty strong bond between the two.. maybe a
RB_COLOUR_MASKand 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_nostatic 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
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_REDandRB_BLACKdefinitions.
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
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
David Woodhouse
maintainerQuoted 3 lines · Nick Piggin
How do we know the pointers are always going to be aligned? IIRC struct
address_spaceneeded to be explicitly aligned when doing this trick inpage->mappingbecause 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
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_spaceneeded to be explicitly aligned when doing this trick inpage->mappingbecause some platform byte aligned it.Really? I've been doing this kind of trick with the
jffs2_raw_node_reffor 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
David Woodhouse
maintainerQuoted 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 forPAGE_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
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
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(vostatic 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: */
_
Quoted 3 lines · Andrew Morton
-#define
HRTIMER_INACTIVE((void *)1UL)
+#defineHRTIMER_INACTIVE((void *)-2)
I don't think that's going to work either. Let me try -4..
Quoted 7 lines · Andrew Morton
Quoted 3 lines · Andrew Morton
-#define
HRTIMER_INACTIVE((void *)1UL)
+#defineHRTIMER_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 ;)
David Woodhouse
maintainerQuoted 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
@@ -127,7 +127,7 @@ #endifstatic 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
@@ -393,7 +393,7 @@ static void __remove_hrtimer(struct hrtiif (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
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.ccompile 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
David Woodhouse
maintainerQuoted 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
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
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(vostatic 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/
Quoted 5 lines · Steven Rostedt
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
David found a way to solve it already.
tglx