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

* git://git.infradead.org/~dwmw2/rbtree-2.6:
  [RBTREE] Switch rb_colour() et al to en_US spelling of 'color' for consistency
  Update UML kernel/physmem.c to use rb_parent() accessor macro
  [RBTREE] Update hrtimers to use rb_parent() accessor macro.
  [RBTREE] Add explicit alignment to sizeof(long) for struct rb_node.
  [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

13 files changed, 140 insertions, 136 deletions

diff --git a/arch/um/kernel/physmem.c b/arch/um/kernel/physmem.c
index fc0f0b085ca7..166cb09cae4c 100644
--- a/arch/um/kernel/physmem.c
+++ b/arch/um/kernel/physmem.c
@@ -69,7 +69,7 @@ static void insert_phys_mapping(struct phys_desc *desc)
                 panic("Physical remapping for %p already present",
                       desc->virt);
 
-        rb_link_node(&desc->rb, (*n)->rb_parent, n);
+        rb_link_node(&desc->rb, rb_parent(*n), n);
         rb_insert_color(&desc->rb, &phys_mappings);
 }
 
diff --git a/block/as-iosched.c b/block/as-iosched.c
index a7caf35ca0c2..0c750393be4a 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -353,10 +353,9 @@ static struct request *as_find_arq_hash(struct as_data *ad, sector_t offset)
 /*
  * 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
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 052b17487625..6200d9b9af28 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -60,14 +60,9 @@ static DEFINE_SPINLOCK(cfq_exit_lock);
 /*
  * 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)
@@ -567,7 +562,6 @@ static inline void cfq_del_crq_rb(struct cfq_rq *crq)
         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);
diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index 3bd0415a9828..c94de8e12fbf 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -165,10 +165,9 @@ deadline_find_drq_hash(struct deadline_data *dd, sector_t offset)
 /*
  * 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
diff --git a/fs/eventpoll.c b/fs/eventpoll.c
index 1b4491cdd115..2695337d4d64 100644
--- a/fs/eventpoll.c
+++ b/fs/eventpoll.c
@@ -337,20 +337,20 @@ static inline int ep_cmp_ffd(struct epoll_filefd *p1,
 /* 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;
 }
 
 /*
diff --git a/fs/ext3/dir.c b/fs/ext3/dir.c
index f37528ed222e..fbb0d4ed07d4 100644
--- a/fs/ext3/dir.c
+++ b/fs/ext3/dir.c
@@ -284,7 +284,7 @@ static void free_rb_tree_fname(struct rb_root *root)
                  * 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;
diff --git a/fs/jffs2/nodelist.h b/fs/jffs2/nodelist.h
index 7ad8ee043880..b16c60bbcf6e 100644
--- a/fs/jffs2/nodelist.h
+++ b/fs/jffs2/nodelist.h
@@ -315,7 +315,6 @@ static inline struct jffs2_node_frag *frag_last(struct rb_root *root)
         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)
diff --git a/fs/jffs2/readinode.c b/fs/jffs2/readinode.c
index 5ea4faafa2d3..5fec012b02ed 100644
--- a/fs/jffs2/readinode.c
+++ b/fs/jffs2/readinode.c
@@ -66,7 +66,7 @@ static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
                         jffs2_free_full_dnode(tn->fn);
                         jffs2_free_tmp_dnode_info(tn);
 
-                        this = this->rb_parent;
+                        this = rb_parent(this);
                         if (!this)
                                 break;
 
@@ -708,12 +708,12 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
                         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;
 
@@ -721,14 +721,14 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
 
                 /* 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) {
diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h
index 306acf1dc6d5..7d2a1b974c5e 100644
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -127,7 +127,7 @@ extern ktime_t hrtimer_get_next_event(void);
 
 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: */
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 4b7cc4fe366d..f37006f21664 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -99,19 +99,36 @@ static inline struct page * rb_insert_page_cache(struct inode * inode,
 
 struct rb_node
 {
-        struct rb_node *rb_parent;
-        int rb_color;
+        unsigned long  rb_parent_color;
 #define RB_RED          0
 #define RB_BLACK        1
         struct rb_node *rb_right;
         struct rb_node *rb_left;
-};
+} __attribute__((aligned(sizeof(long))));
+    /* The alignment might seem pointless, but allegedly CRIS needs it */
 
 struct rb_root
 {
         struct rb_node *rb_node;
 };
 
+
+#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
+#define rb_color(r)   ((r)->rb_parent_color & 1)
+#define rb_is_red(r)   (!rb_color(r))
+#define rb_is_black(r) rb_color(r)
+#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
+#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+        rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
+}
+static inline void rb_set_color(struct rb_node *rb, int color)
+{
+        rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
+}
+
 #define RB_ROOT (struct rb_root) { NULL, }
 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
 
@@ -131,8 +148,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
 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_color = (unsigned long )parent;
         node->rb_left = node->rb_right = NULL;
 
         *rb_link = node;
diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index 01fa2ae98a85..18324305724a 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -393,7 +393,7 @@ static void __remove_hrtimer(struct hrtimer *timer, struct hrtimer_base *base)
         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);
 }
 
 /*
@@ -582,7 +582,7 @@ void hrtimer_init(struct hrtimer *timer, clockid_t clock_id,
                 clock_id = CLOCK_MONOTONIC;
 
         timer->base = &bases[clock_id];
-        timer->node.rb_parent = HRTIMER_INACTIVE;
+        rb_set_parent(&timer->node, &timer->node);
 }
 EXPORT_SYMBOL_GPL(hrtimer_init);
 
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 14b791ac5089..1e55ba1c2edf 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -26,60 +26,66 @@
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
         struct rb_node *right = node->rb_right;
+        struct rb_node *parent = rb_parent(node);
 
         if ((node->rb_right = right->rb_left))
-                right->rb_left->rb_parent = node;
+                rb_set_parent(right->rb_left, node);
         right->rb_left = node;
 
-        if ((right->rb_parent = node->rb_parent))
+        rb_set_parent(right, parent);
+
+        if (parent)
         {
-                if (node == node->rb_parent->rb_left)
-                        node->rb_parent->rb_left = right;
+                if (node == parent->rb_left)
+                        parent->rb_left = right;
                 else
-                        node->rb_parent->rb_right = right;
+                        parent->rb_right = right;
         }
         else
                 root->rb_node = right;
-        node->rb_parent = right;
+        rb_set_parent(node, right);
 }
 
 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
 {
         struct rb_node *left = node->rb_left;
+        struct rb_node *parent = rb_parent(node);
 
         if ((node->rb_left = left->rb_right))
-                left->rb_right->rb_parent = node;
+                rb_set_parent(left->rb_right, node);
         left->rb_right = node;
 
-        if ((left->rb_parent = node->rb_parent))
+        rb_set_parent(left, parent);
+
+        if (parent)
         {
-                if (node == node->rb_parent->rb_right)
-                        node->rb_parent->rb_right = left;
+                if (node == parent->rb_right)
+                        parent->rb_right = left;
                 else
-                        node->rb_parent->rb_left = left;
+                        parent->rb_left = left;
         }
         else
                 root->rb_node = left;
-        node->rb_parent = left;
+        rb_set_parent(node, left);
 }
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
         struct rb_node *parent, *gparent;
 
-        while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
+        while ((parent = rb_parent(node)) && rb_is_red(parent))
         {
-                gparent = parent->rb_parent;
+                gparent = rb_parent(parent);
 
                 if (parent == gparent->rb_left)
                 {
                         {
                                 register struct rb_node *uncle = gparent->rb_right;
-                                if (uncle && uncle->rb_color == RB_RED)
+                                if (uncle && rb_is_red(uncle))
                                 {
-                                        uncle->rb_color = RB_BLACK;
-                                        parent->rb_color = RB_BLACK;
-                                        gparent->rb_color = RB_RED;
+                                        rb_set_black(uncle);
+                                        rb_set_black(parent);
+                                        rb_set_red(gparent);
                                         node = gparent;
                                         continue;
                                 }
@@ -94,17 +100,17 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                                 node = tmp;
                         }
 
-                        parent->rb_color = RB_BLACK;
-                        gparent->rb_color = RB_RED;
+                        rb_set_black(parent);
+                        rb_set_red(gparent);
                         __rb_rotate_right(gparent, root);
                 } else {
                         {
                                 register struct rb_node *uncle = gparent->rb_left;
-                                if (uncle && uncle->rb_color == RB_RED)
+                                if (uncle && rb_is_red(uncle))
                                 {
-                                        uncle->rb_color = RB_BLACK;
-                                        parent->rb_color = RB_BLACK;
-                                        gparent->rb_color = RB_RED;
+                                        rb_set_black(uncle);
+                                        rb_set_black(parent);
+                                        rb_set_red(gparent);
                                         node = gparent;
                                         continue;
                                 }
@@ -119,13 +125,13 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                                 node = tmp;
                         }
 
-                        parent->rb_color = RB_BLACK;
-                        gparent->rb_color = RB_RED;
+                        rb_set_black(parent);
+                        rb_set_red(gparent);
                         __rb_rotate_left(gparent, root);
                 }
         }
 
-        root->rb_node->rb_color = RB_BLACK;
+        rb_set_black(root->rb_node);
 }
 EXPORT_SYMBOL(rb_insert_color);
 
@@ -134,43 +140,40 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 {
         struct rb_node *other;
 
-        while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
+        while ((!node || rb_is_black(node)) && node != root->rb_node)
         {
                 if (parent->rb_left == node)
                 {
                         other = parent->rb_right;
-                        if (other->rb_color == RB_RED)
+                        if (rb_is_red(other))
                         {
-                                other->rb_color = RB_BLACK;
-                                parent->rb_color = RB_RED;
+                                rb_set_black(other);
+                                rb_set_red(parent);
                                 __rb_rotate_left(parent, root);
                                 other = parent->rb_right;
                         }
-                        if ((!other->rb_left ||
-                             other->rb_left->rb_color == RB_BLACK)
-                            && (!other->rb_right ||
-                                other->rb_right->rb_color == RB_BLACK))
+                        if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+                            (!other->rb_right || rb_is_black(other->rb_right)))
                         {
-                                other->rb_color = RB_RED;
+                                rb_set_red(other);
                                 node = parent;
-                                parent = node->rb_parent;
+                                parent = rb_parent(node);
                         }
                         else
                         {
-                                if (!other->rb_right ||
-                                    other->rb_right->rb_color == RB_BLACK)
+                                if (!other->rb_right || rb_is_black(other->rb_right))
                                 {
-                                        register struct rb_node *o_left;
+                                        struct rb_node *o_left;
                                         if ((o_left = other->rb_left))
-                                                o_left->rb_color = RB_BLACK;
-                                        other->rb_color = RB_RED;
+                                                rb_set_black(o_left);
+                                        rb_set_red(other);
                                         __rb_rotate_right(other, root);
                                         other = parent->rb_right;
                                 }
-                                other->rb_color = parent->rb_color;
-                                parent->rb_color = RB_BLACK;
+                                rb_set_color(other, rb_color(parent));
+                                rb_set_black(parent);
                                 if (other->rb_right)
-                                        other->rb_right->rb_color = RB_BLACK;
+                                        rb_set_black(other->rb_right);
                                 __rb_rotate_left(parent, root);
                                 node = root->rb_node;
                                 break;
@@ -179,38 +182,35 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                 else
                 {
                         other = parent->rb_left;
-                        if (other->rb_color == RB_RED)
+                        if (rb_is_red(other))
                         {
-                                other->rb_color = RB_BLACK;
-                                parent->rb_color = RB_RED;
+                                rb_set_black(other);
+                                rb_set_red(parent);
                                 __rb_rotate_right(parent, root);
                                 other = parent->rb_left;
                         }
-                        if ((!other->rb_left ||
-                             other->rb_left->rb_color == RB_BLACK)
-                            && (!other->rb_right ||
-                                other->rb_right->rb_color == RB_BLACK))
+                        if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+                            (!other->rb_right || rb_is_black(other->rb_right)))
                         {
-                                other->rb_color = RB_RED;
+                                rb_set_red(other);
                                 node = parent;
-                                parent = node->rb_parent;
+                                parent = rb_parent(node);
                         }
                         else
                         {
-                                if (!other->rb_left ||
-                                    other->rb_left->rb_color == RB_BLACK)
+                                if (!other->rb_left || rb_is_black(other->rb_left))
                                 {
                                         register struct rb_node *o_right;
                                         if ((o_right = other->rb_right))
-                                                o_right->rb_color = RB_BLACK;
-                                        other->rb_color = RB_RED;
+                                                rb_set_black(o_right);
+                                        rb_set_red(other);
                                         __rb_rotate_left(other, root);
                                         other = parent->rb_left;
                                 }
-                                other->rb_color = parent->rb_color;
-                                parent->rb_color = RB_BLACK;
+                                rb_set_color(other, rb_color(parent));
+                                rb_set_black(parent);
                                 if (other->rb_left)
-                                        other->rb_left->rb_color = RB_BLACK;
+                                        rb_set_black(other->rb_left);
                                 __rb_rotate_right(parent, root);
                                 node = root->rb_node;
                                 break;
@@ -218,7 +218,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                 }
         }
         if (node)
-                node->rb_color = RB_BLACK;
+                rb_set_black(node);
 }
 
 void rb_erase(struct rb_node *node, struct rb_root *root)
@@ -238,48 +238,41 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
                 while ((left = node->rb_left) != NULL)
                         node = left;
                 child = node->rb_right;
-                parent = node->rb_parent;
-                color = node->rb_color;
+                parent = rb_parent(node);
+                color = rb_color(node);
 
                 if (child)
-                        child->rb_parent = parent;
-                if (parent)
-                {
-                        if (parent->rb_left == node)
-                                parent->rb_left = child;
-                        else
-                                parent->rb_right = child;
-                }
-                else
-                        root->rb_node = child;
-
-                if (node->rb_parent == old)
+                        rb_set_parent(child, parent);
+                if (parent == old) {
+                        parent->rb_right = child;
                         parent = node;
-                node->rb_parent = old->rb_parent;
-                node->rb_color = old->rb_color;
+                } else
+                        parent->rb_left = child;
+
+                node->rb_parent_color = old->rb_parent_color;
                 node->rb_right = old->rb_right;
                 node->rb_left = old->rb_left;
 
-                if (old->rb_parent)
+                if (rb_parent(old))
                 {
-                        if (old->rb_parent->rb_left == old)
-                                old->rb_parent->rb_left = node;
+                        if (rb_parent(old)->rb_left == old)
+                                rb_parent(old)->rb_left = node;
                         else
-                                old->rb_parent->rb_right = node;
+                                rb_parent(old)->rb_right = node;
                 } else
                         root->rb_node = node;
 
-                old->rb_left->rb_parent = node;
+                rb_set_parent(old->rb_left, node);
                 if (old->rb_right)
-                        old->rb_right->rb_parent = node;
+                        rb_set_parent(old->rb_right, node);
                 goto color;
         }
 
-        parent = node->rb_parent;
-        color = node->rb_color;
+        parent = rb_parent(node);
+        color = rb_color(node);
 
         if (child)
-                child->rb_parent = parent;
+                rb_set_parent(child, parent);
         if (parent)
         {
                 if (parent->rb_left == node)
@@ -327,6 +320,8 @@ EXPORT_SYMBOL(rb_last);
 
 struct rb_node *rb_next(struct rb_node *node)
 {
+        struct rb_node *parent;
+
         /* If we have a right-hand child, go down and then left as far
            as we can. */
         if (node->rb_right) {
@@ -342,15 +337,17 @@ struct rb_node *rb_next(struct rb_node *node)
            ancestor is a right-hand child of its parent, keep going
            up. First time it's a left-hand child of its parent, said
            parent is our 'next' node. */
-        while (node->rb_parent && node == node->rb_parent->rb_right)
-                node = node->rb_parent;
+        while ((parent = rb_parent(node)) && node == parent->rb_right)
+                node = parent;
 
-        return node->rb_parent;
+        return parent;
 }
 EXPORT_SYMBOL(rb_next);
 
 struct rb_node *rb_prev(struct rb_node *node)
 {
+        struct rb_node *parent;
+
         /* If we have a left-hand child, go down and then right as far
            as we can. */
         if (node->rb_left) {
@@ -362,17 +359,17 @@ struct rb_node *rb_prev(struct rb_node *node)
 
         /* No left-hand children. Go up till we find an ancestor which
            is a right-hand child of its parent */
-        while (node->rb_parent && node == node->rb_parent->rb_left)
-                node = node->rb_parent;
+        while ((parent = rb_parent(node)) && node == parent->rb_left)
+                node = parent;
 
-        return node->rb_parent;
+        return parent;
 }
 EXPORT_SYMBOL(rb_prev);
 
 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
                      struct rb_root *root)
 {
-        struct rb_node *parent = victim->rb_parent;
+        struct rb_node *parent = rb_parent(victim);
 
         /* Set the surrounding nodes to point to the replacement */
         if (parent) {
@@ -384,9 +381,9 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
                 root->rb_node = new;
         }
         if (victim->rb_left)
-                victim->rb_left->rb_parent = new;
+                rb_set_parent(victim->rb_left, new);
         if (victim->rb_right)
-                victim->rb_right->rb_parent = new;
+                rb_set_parent(victim->rb_right, new);
 
         /* Copy the pointers/colour from the victim to the replacement */
         *new = *victim;
diff --git a/security/keys/key.c b/security/keys/key.c
index b6061fa29da7..3fdc49c6a02c 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -211,12 +211,12 @@ static inline void key_alloc_serial(struct key *key)
                         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)