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

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

[zijun_hu]

From: zijun_hu <zijun_hu@htc.com>

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 <zijun_hu@htc.com>
---
 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(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index e585018..f3a8596 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -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)
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index d076183..0a839ea 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -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)
-- 
1.9.1

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

[Peter Zijlstra]

On Thu, Aug 18, 2016 at 04:19:10PM +0800, zijun_hu wrote:
> From: zijun_hu <zijun_hu@htc.com>
> 
> 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.

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

[zijun_hu]

On 08/18/2016 05:01 PM, Peter Zijlstra wrote:
> On Thu, Aug 18, 2016 at 04:19:10PM +0800, zijun_hu wrote:
>> From: zijun_hu <zijun_hu@htc.com>
>>
>> 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