Skip to contentSkip to conversation

rbtree: correct mask for extracting node's parent

PATCH In review zijun_hu 2 participants 3 messages Aug 18, 2016

lore
Share & tools
lore

zijun_hu

author
#0 lore raw

PATCH 1/1 rbtree: correct mask for extracting node's parent

From: zijun_hu <[email protected]>

for LP64 ABI, struct rb_node aligns at 8 bytes boundary due to sizeof(long) == 8 normally, so 0x07 should be used to extract node's parent rather than 0x03

the mask is corrected based on normal alignment of struct rb_node macros are introduced to replace hard coding numbers too

Signed-off-by zijun_hu <[email protected]>

---
an alternative to macro RB_PARENT_MASK is shown below via __alignof__

 #define RB_PARENT_MASK  \
	(~((unsigned long)__alignof__(struct rb_node) - 1))
 include/linux/rbtree.h           | 4 +++-
 include/linux/rbtree_augmented.h | 5 +++--
 2 files changed, 6 insertions(+), 3 deletions(-)
include/linux/rbtree.h +3 -1
index e585018..f3a8596 100644
@@ -44,8 +44,10 @@ struct rb_root {
 	struct rb_node *rb_node;
 };
 
+#define RB_PARENT_MASK	 (~((unsigned long)sizeof(long) - 1))
 
-#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
+#define rb_parent(r)   \
+	((struct rb_node *)((r)->__rb_parent_color & RB_PARENT_MASK))
 
 #define RB_ROOT	(struct rb_root) { NULL, }
 #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
include/linux/rbtree_augmented.h +3 -2
index d076183..0a839ea 100644
@@ -96,10 +96,11 @@ rbstatic const struct rb_augment_callbacks rbname = {			\
 
 #define	RB_RED		0
 #define	RB_BLACK	1
+#define RB_COLOR_MASK	 1UL
 
-#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
+#define __rb_parent(pc)    ((struct rb_node *)(pc & RB_PARENT_MASK))
 
-#define __rb_color(pc)     ((pc) & 1)
+#define __rb_color(pc)     ((pc) & RB_COLOR_MASK)
 #define __rb_is_black(pc)  __rb_color(pc)
 #define __rb_is_red(pc)    (!__rb_color(pc))
 #define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
Signature · 1 line
1.9.1
#1 lore raw
Quoted 5 lines · zijun_hu

From: zijun_hu <[email protected]>

for LP64 ABI, struct rb_node aligns at 8 bytes boundary due to sizeof(long) == 8 normally, so 0x07 should be used to extract node's parent rather than 0x03

Doesn't matter though, in practise. The remaining bits are always 0.

author
#2 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 5 lines · zijun_hu

From: zijun_hu <[email protected]>

for LP64 ABI, struct rb_node aligns at 8 bytes boundary due to sizeof(long) == 8 normally, so 0x07 should be used to extract node's parent rather than 0x03

Doesn't matter though, in practise. The remaining bits are always 0.

okay, understand
it maybe more readable to replace hard coding numbers by macros