binder 红黑树rb_node转实体对象

太过爱你忘了你带给我的痛 2022-11-12 09:36 94阅读 0赞

# c内存的骚操作 #

我们看下下面的代码，给你一个成员变量的地址如何转化为其包裹的父结构体的对象？

struct Node {
        
        long next;
    };
    
    typedef struct _student {
        
        char sname[20];
        Node mynode;
    } ;
    
    struct _student * getFromMember(Node *node){
        
            //todo？获取从node对象转化为_student *对象
    } 
    
    int main(int argc, char *argv[]) {
        
    
        //初始化一个结构体
        struct _student p{
        "小明", {
        3}};
        Node &node = p.mynode;
        _student *pStudent = getFromMember(&node);
    
    }

这个问题在`binder驱动`红黑树节点转化为实际节点对象会用到

解决方案：

//一个宏函数解决
    #define getParentAddr(memberAddr, type, member)           \
                                                            reinterpret_cast<type *>((size_t) memberAddr -(size_t) (&(((type *) 0)->member)));           \

struct _student * getFromMember(Node *node){
        
           getParentAddr(node, struct _student, mynode);
    }

上面的宏函数起始等价于下面的几部操作

//1. 把0地址视为struct _student
        struct _student *zeroStudent = (struct _student *) 0;
        //2. 取出某个成员变量的地址，因为是0地址，所以得到的地址是相对于其父亲的地址的偏移。这里返回0x18,
        //也就是说 struct _student对象的起始地址 +0x18 就是mynode对象
        size_t mynodeOffset = reinterpret_cast<size_t>(&(zeroStudent->mynode));
        //3. 得到对象的_student的起始位置
        size_t realyAddr = (size_t) &node - mynodeOffset;
        //4. 直接转化
        struct _student *realyObj = reinterpret_cast<_student *>(realyAddr);

可能对java程序员来说有点恶心，但是对于c语言程序员应该不陌生。

# 理解binder驱动的节点转化 #

`linux`提供了一些红黑树的基础api给上层使用如下

// /linux/rbtree.h 这个文件是linux系统所提供的而不是binder创建的
    struct rb_node {
        
    	unsigned long  __rb_parent_color;
    	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;
    };
    
    //这个函数时将rb节点转化为对应父亲等价于我们上文的getParentAddr函数
    #define	rb_entry(ptr, type, member) container_of(ptr, type, member)

你可以惊奇的发现红黑树的节点`rb_node`没有提供额外的属性字段去存储实际数据，所以它的用法和我们常见的红黑树有点不一样。

我们看下`binder驱动`的用例

struct binder_proc {
        
      //红黑树的根节点
      struct rb_root nodes; // binder_proc进程内的binder实体组成的红黑树(关联binder_node->rb_node)
    };
    
    //nodes这个红黑树的节点的存储对象
    struct binder_node {
        
         struct rb_node rb_node;     // 如果这个Binder实体还在使用，则将该节点链接到proc->nodes中。   
    };

根据上面的我们可以得到以下红黑树图:  
![binder红黑树][binder]  
我们看下如何完成`binder驱动`的源码遍历代码

struct rb_node *n;
    for (n = rb_first(&proc->nodes); n != NULL; n = rb_next(n)) {
        
    		//将红黑树对象转化为binder_node ，rb_entry函数类似上文的getParentAddr
    		struct binder_node *node = rb_entry(n, struct binder_node,
    						    rb_node);
    }

# rb\_entry的实现 #

推荐一个在线浏览linux内核代码的网址：  
[在线浏览linux源码][linux]

// /linux/rbtree.h 
    
    #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
    
    // include/linux/kernel.h
    #define container_of(ptr, type, member) ({				\
    	void *__mptr = (void *)(ptr);					\
    	((type *)(__mptr - offsetof(type, member))); })
    
    // include/linux/stddef.h
    #undef offsetof
    #ifdef __compiler_offsetof
    #define offsetof(TYPE, MEMBER)	__compiler_offsetof(TYPE, MEMBER)
    #else
    #define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
    #endif

其实和我们的开篇介绍的差不多，只不过博主用的c++语法

# 参考 #

[binder数据结构][binder 1]

[binder]: /images/20221022/ea1d356c0bda4719ad6ba2726d8a8e96.png
[linux]: https://elixir.bootlin.com/linux/latest/source/include/linux/rbtree.h
[binder 1]: http://wangkuiwu.github.io/2014/09/02/Binder-Datastruct/#anchor1_4