Android10.0 Binder通信原理(五)-Binder驱动分析

阅读本文大约需要花费35分钟。

《Android取经之路》系列文章：

《系统启动篇》

《日志系统》

《Binder系列》

1.概述

在Android中，用户空间的应用程序都可以看做是一个独立的进程，进程间存在隔离，进程不能互相访问数据，如果需要访问就需要借助内核。

每个应用程序都有它自己独立的内存空间，若不同的应用程序之间涉及到通信，需要通过内核进行中转，因为需要用到内核的copy_from_user()和copy_to_user()等函数。因此在Binder的通信中，也引入了Binder内核驱动，用来提供数据中转。

Binder驱动就是一个多个进程之间的中枢神经，支撑起了Android中进程间通信，它内部的设计，与应用程序进程中的业务，不存在任何耦合关系，只负责实现进程间数据通信。

Binder驱动的核心是维护一个binder_proc类型的链表。里面记录了包括ServiceManager在内的所有Client信息，当Client去请求得到某个Service时，Binder驱动就去binder_proc中查找相应的Service返回给Client，同时增加当前Service的引用个数。

2.Binder架构

在整个Binder通信流程中，Binder驱动肩负了载体的作用，承上启下，使用户的数据可以顺畅交互。

3.Binder中重要的数据结构

4.核心内容

用户态的程序调用Kernel层驱动是需要陷入内核态，进行系统调用(syscall)，比如打开Binder驱动方法的调用链为：open-> __open() -> binder_open()。open()为用户空间的方法，__open()便是系统调用中相应的处理方法，通过查找，对应调用到内核binder驱动的binder_open()方法，至于其他的从用户态陷入内核态的流程也基本一致。

几个重要方法说明：

binder_init：初始化字符设备 "/dev/binder","/dev/hwbinder","/dev/vndbinder"；

binder_open：打开驱动设备；

binder_mmap：申请内存空间；

binder_ioctl：执行相应的ioctl操作；

4.1 初始化 binder_init()

内核初始化时，会调用到device_initcall()进行初始化，从而启动binder_init。

binder_init()主要负责注册misc设备,通过调用misc_register()来实现。

在Android8.0之后，现在Binder驱动有三个：/dev/binder; /dev/hwbinder; /dev/vndbinder.

device_initcall(binder_init);
static HLIST_HEAD(binder_devices);

static int __init binder_init(void)
{
       int ret;
       char *device_name, *device_names, *device_tmp;
       struct binder_device *device;
       struct hlist_node *tmp;

       ret = binder_alloc_shrinker_init();
       if (ret)
               return ret;

       atomic_set(&binder_transaction_log.cur, ~0U);
       atomic_set(&binder_transaction_log_failed.cur, ~0U);

    //在debugfs文件系统中创建一个目录，返回值是指向dentry的指针
    //在手机对应的目录：/sys/kernel/debug/binder，里面创建了几个文件，用来记录binder操作过程中的信息和日志：
    //failed_transaction_log、state、stats、transaction_log、transactions
       binder_debugfs_dir_entry_root = debugfs_create_dir("binder", NULL);
       if (binder_debugfs_dir_entry_root)
        //创建目录:/sys/kernel/debug/binder/proc
               binder_debugfs_dir_entry_proc = debugfs_create_dir("proc",
                                                binder_debugfs_dir_entry_root);
    ...

       device_names = kzalloc(strlen(binder_devices_param) + 1, GFP_KERNEL);
       if (!device_names) {
               ret = -ENOMEM;
               goto err_alloc_device_names_failed;
       }
       strcpy(device_names, binder_devices_param);

       device_tmp = device_names;
   //Android8.0 中引入了hwbinder，vndbinder，所以现在有三个binder，分别需要创建三个binder device:
   // /dev/binder、/dev/hwbinder、/dev/vndbinder
   //循环注册binder 的三个设备：/dev/binder、/dev/hwbinder、/dev/vndbinder
       while ((device_name = strsep(&device_tmp, ","))) {
               ret = init_binder_device(device_name);
               if (ret)
                       goto err_init_binder_device_failed;
       }

       return ret;

err_init_binder_device_failed:
       hlist_for_each_entry_safe(device, tmp, &binder_devices, hlist) {
               misc_deregister(&device->miscdev);
               hlist_del(&device->hlist);
               kfree(device);
       }

       kfree(device_names);

err_alloc_device_names_failed:
       debugfs_remove_recursive(binder_debugfs_dir_entry_root);

       return ret;
}

static int __init init_binder_device(const char *name)
{
       int ret;
       struct binder_device *binder_device;

    //申请内存空间，
       binder_device = kzalloc(sizeof(*binder_device), GFP_KERNEL);
       if (!binder_device)
               return -ENOMEM;

       binder_device->miscdev.fops = &binder_fops;
       binder_device->miscdev.minor = MISC_DYNAMIC_MINOR;
       binder_device->miscdev.name = name;

       binder_device->context.binder_context_mgr_uid = INVALID_UID;
       binder_device->context.name = name;
       mutex_init(&binder_device->context.context_mgr_node_lock);

       ret = misc_register(&binder_device->miscdev);
       if (ret < 0) {
               kfree(binder_device);
               return ret;
       }

       hlist_add_head(&binder_device->hlist, &binder_devices);

       return ret;
}

Android8.0及之后的Binder域如下图所示：

4.1.1 注册设备的几个重要结构体

binder的device包含了一个哈希链表，一个misc设备结构，一个binder context，结构如下：

struct binder_device {
       struct hlist_node hlist;
       struct miscdevice miscdev;  //misc 设备
       struct binder_context context;  //context
};

misc 设备结构中，我们主要关注name，fops，结构如下：

struct miscdevice  {
       int minor;                          //次设备号 动态分配 MISC_DYNAMIC_MINOR
       const char *name;                   //设备名  "/dev/binder、/dev/hwbinder、/dev/vndbinder"
       const struct file_operations *fops; //设备的文件操作结构，这是file_operations结构
       struct list_head list;
       struct device *parent;
       struct device *this_device;
       const struct attribute_group **groups;
       const char *nodename;
       umode_t mode;
};

在获取了一些设备编号后，我们还没有将任何驱动程序操作连接到这些编号，file_operations结构就是用来建立这种连接的。

binder_fops主要包含了Binder的一些操作方法配置，例如open、mmap、ioctl，结构如下：

static const struct file_operations binder_fops = {
       .owner = THIS_MODULE,
       .poll = binder_poll,
       .unlocked_ioctl = binder_ioctl,
       .compat_ioctl = binder_ioctl,
       .mmap = binder_mmap,
       .open = binder_open,
       .flush = binder_flush,
       .release = binder_release,
};

4.2 binder_open

当我们在Native C\C++层通过系统调用open()来打开binder驱动时，驱动层会根据设备文件的主设备号，找到相应的设备驱动程序，然后读取这个数据结构相应的函数指针，接着把控制权交给该函数。

因此，open()到驱动层，就会调用binder_open()

binder_open()主要负责打开驱动设备，创建binder_proc对象，并把当前进程等信息保存到binder_proc对象，该对象管理IPC所需的各种信息并拥有其他结构体的根结构体；再把binder_proc对象保存到文件指针filp，以及把binder_proc加入到全局链表binder_procs。

binder_open()职责如下：

1.首先创建了binder_proc结构体实例proc

2.接着开始初始化一系列成员：tsk, todo, default_priority, pid， delivered_death等。

3.更新了统计数据：binder_proc的创建个数加1

4.紧接着将初始化好的proc，存放到文件指针filp->private_data中，以便于在之后的mmap、ioctl中获取。

5.将binder_proc链入binder_procs哈希链表中；

6.最后查看是否创建的了/sys/kernel/debug/binde/proc/目录，有的话再创建一个/sys/kernel/debug/binde/proc/pid文件，用来记录binder_proc的状态

static HLIST_HEAD(binder_procs);
static int binder_open(struct inode *nodp, struct file *filp)
{
       struct binder_proc *proc;           // binder进程
       struct binder_device *binder_dev;   // binder device

       binder_debug(BINDER_DEBUG_OPEN_CLOSE, "%s: %d:%d\n", __func__,
                    current->group_leader->pid, current->pid);

       proc = kzalloc(sizeof(*proc), GFP_KERNEL);  // 为binder_proc结构体在分配kernel内存空间
       if (proc == NULL)
               return -ENOMEM;
       spin_lock_init(&proc->inner_lock);
       spin_lock_init(&proc->outer_lock);
       atomic_set(&proc->tmp_ref, 0);
       get_task_struct(current->group_leader);//增加线程引用计数
       proc->tsk = current->group_leader;     //将当前线程的task保存到binder进程的tsk
       mutex_init(&proc->files_lock);
       INIT_LIST_HEAD(&proc->todo);                 //初始化todo队列，用于存放待处理的请求（server端）
    //配置binder优先级
       if (binder_supported_policy(current->policy)) {
               proc->default_priority.sched_policy = current->policy;
               proc->default_priority.prio = current->normal_prio;
       } else {
               proc->default_priority.sched_policy = SCHED_NORMAL;
               proc->default_priority.prio = NICE_TO_PRIO(0);
       }

       binder_dev = container_of(filp->private_data, struct binder_device,
                                 miscdev);
       proc->context = &binder_dev->context;   //拿到binder device的context，传给binder_proc 
       binder_alloc_init(&proc->alloc);

       binder_stats_created(BINDER_STAT_PROC); //类型为BINDER_STAT_PROC对象的创建个数加1
       proc->pid = current->group_leader->pid; //记录当前进程的pid
       INIT_LIST_HEAD(&proc->delivered_death);
       INIT_LIST_HEAD(&proc->waiting_threads);
       filp->private_data = proc;  //将binder_proc存放在filp的private_data域，以便于在之后的mmap、ioctl中获取

       mutex_lock(&binder_procs_lock);
       hlist_add_head(&proc->proc_node, &binder_procs);    //将proc_node节点添加到binder_procs为表头的队列
       mutex_unlock(&binder_procs_lock);

    // 如果/sys/kernel/debug/binder/proc 目录存在，在该目录中创建相应pid对应的文件，名称为pid，用来记录binder_proc的状态
       if (binder_debugfs_dir_entry_proc) {
               char strbuf[11];

               snprintf(strbuf, sizeof(strbuf), "%u", proc->pid);
               proc->debugfs_entry = debugfs_create_file(strbuf, 0444,
                       binder_debugfs_dir_entry_proc,
                       (void *)(unsigned long)proc->pid,
                       &binder_proc_fops);
       }

       return 0;
}

4.2.1 重要结构 binder_proc

binder_proc 与应用层的binder实体一一对应，每个进程调用open()打开binder驱动都会创建该结构体，用于管理IPC所需的各种信息。

其中有4个红黑树threads、nodes、refs_by_desc、refs_by_node， 在一个进程中，有多少“被其他进程进行跨进程调用的”binder实体，就会在该进程对应的nodes树中生成多少个红黑树节点。另一方面，一个进程要访问多少其他进程的binder实体，则必须在其refs_by_desc树中拥有对应的引用节点。

struct binder_proc {
       struct hlist_node proc_node;    //进程节点
       struct rb_root threads;         //记录执行传输动作的线程信息, binder_thread红黑树的根节点
       struct rb_root nodes;           //用于记录binder实体  ,binder_node红黑树的根节点，它是Server在Binder驱动中的体现
       struct rb_root refs_by_desc;    //记录binder引用, 便于快速查找,binder_ref红黑树的根节点(以handle为key)，它是Client在Binder驱动中的体现
       struct rb_root refs_by_node;    //记录binder引用, 便于快速查找,binder_ref红黑树的根节点（以ptr为key），它是Client在Binder驱动中的体现
       struct list_head waiting_threads;
       int pid;    //相应进程id
       struct task_struct *tsk;    //相应进程的task结构体
       struct files_struct *files; //相应进程的文件结构体
       struct mutex files_lock;
       struct hlist_node deferred_work_node;
       int deferred_work;
       bool is_dead;

       struct list_head todo;      //进程将要做的事
       struct binder_stats stats;  //binder统计信息
       struct list_head delivered_death;   //已分发的死亡通知
       int max_threads;        //最大线程数
       int requested_threads;  //请求的线程数
       int requested_threads_started;  //已启动的请求线程数
       atomic_t tmp_ref;
       struct binder_priority default_priority;    //默认优先级
       struct dentry *debugfs_entry;
       struct binder_alloc alloc;
       struct binder_context *context;
       spinlock_t inner_lock;
       spinlock_t outer_lock;
};

binder_procs哈希链表, 存储了所有open() binder驱动的进程对象，如下图所示：

4.3 binder_mmap

主要功能：首先在内核虚拟地址空间，申请一块与用户虚拟内存相同大小的内存；然后再申请page物理内存，

再将同一块物理内存分别映射到内核虚拟地址空间和用户虚拟内存空间，从而实现了用户空间的Buffer和内核空间的Buffer同步操作的功能。

参数：

filp: 文件描述符

vma: 用户虚拟内存空间

流程：

1.filp->private_data保存了我们open设备时创建的binder_proc信息;

2.为用户进程分配一块内核空间作为缓冲区;

3.把分配的缓冲区指针存放到binder_proc的buffer字段;

4.分配pages空间;

5.在内核分配一块同样页数的内核空间,并把它的物理内存和前面为用户进程分配的内存地址关联;

6.将刚才分配的内存块加入用户进程内存链表;

static int binder_mmap(struct file *filp, struct vm_area_struct *vma)
{
       int ret;
       struct binder_proc *proc = filp->private_data; //private_data保存了我们open设备时创建的binder_proc信息
       const char *failure_string;

       if (proc->tsk != current->group_leader)
               return -EINVAL;

       //vma->vm_end, vma->vm_start 指向要 映射的用户空间地址, map size 不允许 大于 4M
       if ((vma->vm_end - vma->vm_start) > SZ_4M)
               vma->vm_end = vma->vm_start + SZ_4M;
       ...
       //mmap 的 buffer 禁止用户进行写操作。mmap 只是为了分配内核空间，传递数据通过 ioctl()
       if (vma->vm_flags & FORBIDDEN_MMAP_FLAGS) {
               ret = -EPERM;
               failure_string = "bad vm_flags";
               goto err_bad_arg;
       }

       // 将 VM_DONTCOP 置起，禁止 拷贝，禁止 写操作
       vma->vm_flags |= VM_DONTCOPY | VM_MIXEDMAP;
       vma->vm_flags &= ~VM_MAYWRITE;

       vma->vm_ops = &binder_vm_ops;
       vma->vm_private_data = proc;

       // 再次完善 binder buffer allocator
       ret = binder_alloc_mmap_handler(&proc->alloc, vma);
       if (ret)
               return ret;
       mutex_lock(&proc->files_lock);  //同步锁
       proc->files = get_files_struct(current);
       mutex_unlock(&proc->files_lock);    //释放锁
       return 0;

err_bad_arg:
       pr_err("%s: %d %lx-%lx %s failed %d\n", __func__,
              proc->pid, vma->vm_start, vma->vm_end, failure_string, ret);
       return ret;
}


int binder_alloc_mmap_handler(struct binder_alloc *alloc,
                             struct vm_area_struct *vma)
{
       int ret;
       const char *failure_string;
       struct binder_buffer *buffer;   //每一次Binder传输数据时，都会先从Binder内存缓存区中分配一个binder_buffer来存储传输数据

       mutex_lock(&binder_alloc_mmap_lock);    //同步锁
       if (alloc->buffer) {        // 不需要重复mmap
               ret = -EBUSY;
               failure_string = "already mapped";
               goto err_already_mapped;
       }

       alloc->buffer = (void __user *)vma->vm_start; //指向用户进程内核虚拟空间的 start地址
       mutex_unlock(&binder_alloc_mmap_lock);               //释放锁

   //分配物理页的指针数组，数组大小为vma的等效page个数
       alloc->pages = kzalloc(sizeof(alloc->pages[0]) *
                                  ((vma->vm_end - vma->vm_start) / PAGE_SIZE),
                              GFP_KERNEL);
       if (alloc->pages == NULL) {
               ret = -ENOMEM;
               failure_string = "alloc page array";
               goto err_alloc_pages_failed;
       }
       alloc->buffer_size = vma->vm_end - vma->vm_start;

       buffer = kzalloc(sizeof(*buffer), GFP_KERNEL);  //申请一个binder_buffer的内存
       if (!buffer) {
               ret = -ENOMEM;
               failure_string = "alloc buffer struct";
               goto err_alloc_buf_struct_failed;
       }

       buffer->user_data = alloc->buffer;                 //指向用户进程内核虚拟空间的 start地址，即为当前进程mmap的内核空间地址
       list_add(&buffer->entry, &alloc->buffers);  //将binder_buffer地址 加入到所属进程的buffers队列
       buffer->free = 1;
       binder_insert_free_buffer(alloc, buffer);   //将 当前 buffer 加入到 红黑树 alloc->free_buffers 中，表示当前 buffer 是空闲buffer
       alloc->free_async_space = alloc->buffer_size / 2; // 将 异步事务 的空间大小设置为 整个空间的一半
       barrier();
       alloc->vma = vma;
       alloc->vma_vm_mm = vma->vm_mm;
       /* Same as mmgrab() in later kernel versions */
       atomic_inc(&alloc->vma_vm_mm->mm_count);

       return 0;

err_alloc_buf_struct_failed:
       kfree(alloc->pages);
       alloc->pages = NULL;
err_alloc_pages_failed:
       mutex_lock(&binder_alloc_mmap_lock);
       alloc->buffer = NULL;
err_already_mapped:
       mutex_unlock(&binder_alloc_mmap_lock);
       pr_err("%s: %d %lx-%lx %s failed %d\n", __func__,
              alloc->pid, vma->vm_start, vma->vm_end, failure_string, ret);
       return ret;
}

4.3.1 重要结构 binder_buffer

每一次Binder传输数据时，都会先从Binder内存缓存区中分配一个binder_buffer来存储传输数据。

struct binder_buffer {
       struct list_head entry; //buffer实体的地址
       struct rb_node rb_node; //buffer实体的地址
       unsigned free:1;            //标记是否是空闲buffer，占位1bit
       unsigned allow_user_free:1;  //是否允许用户释放，占位1bit
       unsigned async_transaction:1;//占位1bit
       unsigned debug_id:29;          //占位29bit

       struct binder_transaction *transaction; //该缓存区的需要处理的事务

       struct binder_node *target_node; //该缓存区所需处理的Binder实体
       size_t data_size;          //数据大小
       size_t offsets_size;      //数据偏移量
       size_t extra_buffers_size;
       void __user *user_data;   //用户数据
};

4.3.3 内存分配情况

ServiceManager启动后，会通过系统调用mmap向内核空间申请128K的内存，用户进程会通过mmap向内核申请(1M-8K)的内存空间。

这里用户空间mmap (1M-8K)的空间，为什么要减去8K，而不是直接用1M?

 Android的git commit记录：

Modify the binder to request 1M - 2 pages instead of 1M. The backing store in the kernel requires a guard page, so 1M allocations fragment memory very badly. Subtracting a couple of pages so that they fit in a power of two allows the kernel to make more efficient use of its virtual address space.

大致的意思是：kernel的“backing store”需要一个保护页，这使得1M用来分配碎片内存时变得很差，所以这里减去两页来提高效率，因为减去一页就变成了奇数。

系统定义：BINDER_VM_SIZE ((1 * 1024 * 1024) - sysconf(_SC_PAGE_SIZE) * 2)   = （1M- sysconf(_SC_PAGE_SIZE) * 2）        

这里的8K，其实就是两个PAGE的SIZE, 物理内存的划分是按PAGE(页)来划分的，一般情况下，一个Page的大小为4K。

内核会增加一个guard page，再加上内核本身的guard page，正好是两个page的大小，减去后，就是用户空间可用的大小。        

在内存分配这块，还要分为32位和64位，32位的系统很好区分，虚拟内存为4G，用户空间从低地址开始占用3G，内核空间占用剩余的1G。

ARM32内存占用分配：

但随着现在的硬件发展越来越迅速，应用程序的运算也越来越复杂，占用空间越来越大，原有的4G虚拟内存已经不能满足用户的需求，因此，现在的Android基本都是用64位的内存机制。

理论上讲，64位的地址总线可以支持高达16EB（2^64）的内存。AMD64架构支持52位（4PB）的地址总线和48位（256TB）的虚拟地址空间。在linux arm64中，如果页的大小为4KB，使用3级页表转换或者4级页表转换，用户空间和内核空间都支持有39bit（512GB）或者48bit（256TB）大小的虚拟地址空间。

2^64 次方太大了，Linux 内核只采用了 64 bits 的一部分（开启 CONFIG_ARM64_64K_PAGES 时使用 42 bits，页大小是 4K 时使用 39 bits），该文假设使用的页大小是 4K（VA_BITS = 39）

ARM64 有足够的虚拟地址，用户空间和内核空间可以有各自的 2^39 = 512GB 的虚拟地址。

ARM64内存占用分配：

用户地址空间(服务端-数据接收端)和内核地址空间都映射到同一块物理地址空间。

Client(数据发送端)先从自己的用户进程空间把IPC数据通过copy_from_user()拷贝到内核空间。而Server端（数据接收端）与内核共享数据(mmap到同一块物理内存)，不再需要拷贝数据，而是通过内存地址空间的偏移量，即可获悉内存地址，整个过程只发生一次内存拷贝。

 图片来源于Gityuan

4.4 binder_ioctl

binder_ioctl()函数负责在两个进程间收发IPC数据和IPC reply数据，Native C\C++ 层传入不同的cmd和数据，根据cmd的值，进行相应的处理并返回

参数：

filp：文件描述符

cmd：ioctl命令

arg：数据类型

ioctl命令说明:

static long binder_ioctl(struct file *filp, unsigned int cmd, unsigned long arg)
{
       int ret;
   //filp->private_data 在open()binder驱动时，保存了一个创建的binder_proc，即是此时调用进程的binder_proc.
       struct binder_proc *proc = filp->private_data;
       //binder线程
       struct binder_thread *thread;
       unsigned int size = _IOC_SIZE(cmd);
       void __user *ubuf = (void __user *)arg;

       binder_selftest_alloc(&proc->alloc);

       trace_binder_ioctl(cmd, arg);
       //进入休眠状态，直到中断唤醒
       ret = wait_event_interruptible(binder_user_error_wait, binder_stop_on_user_error < 2);
       if (ret)
               goto err_unlocked;

       //获取binder线程信息，如果是第一次调用ioctl()，则会为该进程创建一个线程
       thread = binder_get_thread(proc);
       if (thread == NULL) {
               ret = -ENOMEM;
               goto err;
       }

       switch (cmd) {
       //binder的读写操作，使用评论较高
       case BINDER_WRITE_READ: 
               ret = binder_ioctl_write_read(filp, cmd, arg, thread);
               if (ret)
                       goto err;
               break;
   //设置Binder线程最大个数
       case BINDER_SET_MAX_THREADS: { 
               int max_threads;

               if (copy_from_user(&max_threads, ubuf,
                                  sizeof(max_threads))) {
                       ret = -EINVAL;
                       goto err;
               }
               binder_inner_proc_lock(proc);
               proc->max_threads = max_threads;
               binder_inner_proc_unlock(proc);
               break;
       }
   //设置Service Manager节点，带flag参数， servicemanager进程成为上下文管理者
       case BINDER_SET_CONTEXT_MGR_EXT: { 
               struct flat_binder_object fbo;

               if (copy_from_user(&fbo, ubuf, sizeof(fbo))) {
                       ret = -EINVAL;
                       goto err;
               }
               ret = binder_ioctl_set_ctx_mgr(filp, &fbo);
               if (ret)
                       goto err;
               break;
       }
   //设置Service Manager节点，不带flag参数， servicemanager进程成为上下文管理者
       case BINDER_SET_CONTEXT_MGR:
               ret = binder_ioctl_set_ctx_mgr(filp, NULL);
               if (ret)
                       goto err;
               break;
       ...
   //获取Binder版本信息
       case BINDER_VERSION: {
               struct binder_version __user *ver = ubuf;

               if (size != sizeof(struct binder_version)) {
                       ret = -EINVAL;
                       goto err;
               }
               if (put_user(BINDER_CURRENT_PROTOCOL_VERSION,
                            &ver->protocol_version)) {
                       ret = -EINVAL;
                       goto err;
               }
               break;
       }
       ...
       default:
               ret = -EINVAL;
               goto err;
       }
       ret = 0;
err:
       if (thread)
               thread->looper_need_return = false;
       wait_event_interruptible(binder_user_error_wait, binder_stop_on_user_error < 2);
       if (ret && ret != -ERESTARTSYS)
               pr_info("%d:%d ioctl %x %lx returned %d\n", proc->pid, current->pid, cmd, arg, ret);
err_unlocked:
       trace_binder_ioctl_done(ret);
       return ret;
}

4.4.1 获取binder线程

方法：binder_get_thread()

作用：从当前进程中获取线程信息，如果当前进程中没有线程信息，那么创建一个线程，把proc指向当前进程，并进行线程初始化

static struct binder_thread *binder_get_thread(struct binder_proc *proc)
{
       struct binder_thread *thread;
       struct binder_thread *new_thread;

       binder_inner_proc_lock(proc);
       //从当前进程中获取线程
       thread = binder_get_thread_ilocked(proc, NULL);
       binder_inner_proc_unlock(proc);
       if (!thread) {
              //如果当前进程中没有线程，那么创建一个
               new_thread = kzalloc(sizeof(*thread), GFP_KERNEL);
               if (new_thread == NULL)
                       return NULL;
               binder_inner_proc_lock(proc);
               thread = binder_get_thread_ilocked(proc, new_thread);
               binder_inner_proc_unlock(proc);
               if (thread != new_thread)
                       kfree(new_thread);
       }
       return thread;
}

binder_get_thread_ilocked()流程：

1.先遍历threads节点的红黑树链表;

2.如果没有查找到,则分配一个struct binder_thread长度的空间;

3.初始化等待队列头节点和thread的todo链表;

4.将该线程插入到进程的threads节点;

static struct binder_thread *binder_get_thread_ilocked(
               struct binder_proc *proc, struct binder_thread *new_thread)
{
       struct binder_thread *thread = NULL;
       struct rb_node *parent = NULL;
       struct rb_node **p = &proc->threads.rb_node;

       //根据当前进程的pid，从binder_proc中查找相应的binder_thread
       while (*p) {
               parent = *p;
               thread = rb_entry(parent, struct binder_thread, rb_node);

               if (current->pid < thread->pid)
                       p = &(*p)->rb_left;
               else if (current->pid > thread->pid)
                       p = &(*p)->rb_right;
               else
                       return thread;
       }
       if (!new_thread)
               return NULL;
       //若当前进程中没有线程信息，那么创建一个新的线程，并进行相应的初始化操作
       thread = new_thread;
       binder_stats_created(BINDER_STAT_THREAD);
       thread->proc = proc;                //线程的proc指向当前进程
       thread->pid = current->pid; //线程pid为当前进程的pid
       get_task_struct(current);
       thread->task = current;
       atomic_set(&thread->tmp_ref, 0);
       init_waitqueue_head(&thread->wait);
       INIT_LIST_HEAD(&thread->todo); //初始化等待队列头节点和thread的todo链表
       //把线程节点加入到proc的 threads红黑树中，平衡红黑树
       rb_link_node(&thread->rb_node, parent, p);
       rb_insert_color(&thread->rb_node, &proc->threads);
       thread->looper_need_return = true;
       thread->return_error.work.type = BINDER_WORK_RETURN_ERROR;
       thread->return_error.cmd = BR_OK;
       thread->reply_error.work.type = BINDER_WORK_RETURN_ERROR;
       thread->reply_error.cmd = BR_OK;
       INIT_LIST_HEAD(&new_thread->waiting_thread_node);
       return thread;
}

4.4.1.1 重要结构 binder_thread

binder_thread结构体代表当前binder操作所在的线程

struct binder_thread {
       struct binder_proc *proc;   //线程所属的进程
       struct rb_node rb_node;         //红黑树节点
       struct list_head waiting_thread_node;
       int pid;                          //线程pid
       int looper;               //looper的状态
       bool looper_need_return;  
       struct binder_transaction *transaction_stack;   //线程正在处理的事务
       struct list_head todo;                   //将要处理的链表
       bool process_todo;
       struct binder_error return_error;   //write失败后，返回的错误码
       struct binder_error reply_error;
       wait_queue_head_t wait;                 //等待队列的队头
       struct binder_stats stats;          //binder线程的统计信息
       atomic_t tmp_ref;
       bool is_dead;
       struct task_struct *task;
};

4.4.2 ServiceManager守护进程设置

方法：binder_ioctl_set_ctx_mgr()

ServiceManager、HwServiceManager、VNDServiceManager，在Native C层通过ioctl()发送BINDER_SET_CONTEXT_MGR_EXT 命令，让自身成为上下文管理者，即各自的守护进程。

binder_ioctl_set_ctx_mgr()处理如下：

1.open()binder驱动时得到的filp->private_data，存入binder_proc，代表当前进程的信息

2.检查当前进程是否具注册Context Manager的SELinux安全权限

3.进行uid检查，线程只能注册自己，且只能有一个线程设置为Context Manager

4.设置当前线程euid作为ServiceManager的uid

5.创建一个binder实体binder_node，并加入到当前进程的nodes红黑树中，我们这里可以是ServiceManager

6.把新创建的binder_node,赋值给当前进程的binder_context_mgr_node，这样该进程就成为了上下文的管理者，这是一个约定的过程

static int binder_ioctl_set_ctx_mgr(struct file *filp,
                                   struct flat_binder_object *fbo)
{
       int ret = 0;
       //filp->private_data 在open()binder驱动时，保存了一个创建的binder_proc，即是此时调用进程的binder_proc.
       struct binder_proc *proc = filp->private_data;
       //获得当前进程的context
       struct binder_context *context = proc->context;
       struct binder_node *new_node;
       kuid_t curr_euid = current_euid();

       mutex_lock(&context->context_mgr_node_lock);

   //保证只创建一次mgr_node对象
       if (context->binder_context_mgr_node) {
               pr_err("BINDER_SET_CONTEXT_MGR already set\n");
               ret = -EBUSY;
               goto out;
       }

   //检查当前进程是否具注册Context Manager的SEAndroid安全权限
       ret = security_binder_set_context_mgr(proc->tsk);
       if (ret < 0)
               goto out;
   //检查已的uid是否有效
       if (uid_valid(context->binder_context_mgr_uid)) {
               //uid有效但是与当前运行线程的效用户ID不相等，则出错。
               //即线程只能注册自己，且只能有一个线程设置为Context Manager
               if (!uid_eq(context->binder_context_mgr_uid, curr_euid)) {
                       pr_err("BINDER_SET_CONTEXT_MGR bad uid %d != %d\n",
                              from_kuid(&init_user_ns, curr_euid),
                              from_kuid(&init_user_ns,
                                        context->binder_context_mgr_uid));
                       ret = -EPERM;
                       goto out;
               }
       } else {
               //设置当前线程euid作为ServiceManager的uid
               context->binder_context_mgr_uid = curr_euid;
       }

       //创建binder实体，并加入到当前进程的nodes红黑树中，我们这里可以是ServiceManager
       new_node = binder_new_node(proc, fbo);
       if (!new_node) {
               ret = -ENOMEM;
               goto out;
       }
       binder_node_lock(new_node);
       //更新new_node的相关强弱引用计数
       new_node->local_weak_refs++;
       new_node->local_strong_refs++;
       new_node->has_strong_ref = 1;
       new_node->has_weak_ref = 1;
   //new_node 赋值给进程的上下文管理节点，作为上下文管理者
       context->binder_context_mgr_node = new_node;
       binder_node_unlock(new_node);
       binder_put_node(new_node);
out:
       mutex_unlock(&context->context_mgr_node_lock);
       return ret;
}

4.4.2.1 重要结构 binder_node

binder_node代表binder实体

struct binder_node {
       int debug_id;   //节点创建时分配，具有全局唯一性，用于调试使用
       spinlock_t lock;
       struct binder_work work;
       union {
               struct rb_node rb_node;          //binder节点正常使用，union
               struct hlist_node dead_node;//binder节点已销毁，union
       };
       struct binder_proc *proc;   //binder所在的进程
       struct hlist_head refs;     //所有指向该节点的binder引用队列
       int internal_strong_refs;
       int local_weak_refs;
       int local_strong_refs;
       int tmp_refs;
       binder_uintptr_t ptr;     //指向用户空间binder_node的指针，对应flat_binder_object.binder
       binder_uintptr_t cookie;   //数据，对应flat_binder_object.cookie
       struct {
               /*
                * bitfield elements protected by
                * proc inner_lock
                */
               u8 has_strong_ref:1;
               u8 pending_strong_ref:1;
               u8 has_weak_ref:1;
               u8 pending_weak_ref:1;
       };
       struct {
               /*
                * invariant after initialization
                */
               u8 sched_policy:2;
               u8 inherit_rt:1;
               u8 accept_fds:1;
               u8 txn_security_ctx:1;
               u8 min_priority;
       };
       bool has_async_transaction;
       struct list_head async_todo;    //异步todo队列
};

4.4.3 Binder读写操作

方法：binder_ioctl_write_read()

作用：根据从用户空间传来的binder_write_read数据进行判断，是否进行读写操作， 这也是binder数据交互的核心入口。

流程如下：

1.如果write_size大于0，表示用户进程有数据发送到驱动，则调用binder_thread_write()发送数据，binder_thread_write()中有错误发生，则read_consumed设为0，表示kernel没有数据返回给进程；

2.如果read_size大于0， 表示进程用户态地址空间希望有数据返回给它，则调用binder_thread_read()进行处理，读取完后，如果proc->todo链表不为空，则唤醒在proc->wait等待队列上的进程，如果binder_thread_read返回小于0，可能处理一半就中断了，需要将bwr拷贝回进程的用户态地址；

       3.处理成功的情况，也需要将bwr拷贝回进程的用户态地址空间

static int binder_ioctl_write_read(struct file *filp,
                               unsigned int cmd, unsigned long arg,
                               struct binder_thread *thread)
{
       int ret = 0;
       struct binder_proc *proc = filp->private_data;
       unsigned int size = _IOC_SIZE(cmd);
       void __user *ubuf = (void __user *)arg;
       struct binder_write_read bwr;

       if (size != sizeof(struct binder_write_read)) {
               ret = -EINVAL;
               goto out;
       }
       if (copy_from_user(&bwr, ubuf, sizeof(bwr))) {
               ret = -EFAULT;
               goto out;
       }
       ...
       if (bwr.write_size > 0) {
               //write_size大于0，表示用户进程有数据发送到驱动，则调用binder_thread_write发送数据
               ret = binder_thread_write(proc, thread,
                                         bwr.write_buffer,
                                         bwr.write_size,
                                         &bwr.write_consumed);
               trace_binder_write_done(ret);
               if (ret < 0) {
                       //binder_thread_write中有错误发生，则read_consumed设为0，表示kernel没有数据返回给进程
                       bwr.read_consumed = 0;
                       //将bwr返回给用户态调用者，bwr在binder_thread_write中会被修改
                       if (copy_to_user(ubuf, &bwr, sizeof(bwr)))
                               ret = -EFAULT;
                       goto out;
               }
       }
       //read_size大于0， 表示进程用户态地址空间希望有数据返回给它，则调用binder_thread_read进行处理
       if (bwr.read_size > 0) {
               ret = binder_thread_read(proc, thread, bwr.read_buffer,
                                        bwr.read_size,
                                        &bwr.read_consumed,
                                        filp->f_flags & O_NONBLOCK);
               trace_binder_read_done(ret);
               binder_inner_proc_lock(proc);
               //读取完后，如果proc->todo链表不为空，则唤醒在proc->wait等待队列上的进程
               if (!binder_worklist_empty_ilocked(&proc->todo))
                       binder_wakeup_proc_ilocked(proc);
               binder_inner_proc_unlock(proc);
               if (ret < 0) {
                       //如果binder_thread_read返回小于0，可能处理一半就中断了，需要将bwr拷贝回进程的用户态地址
                       if (copy_to_user(ubuf, &bwr, sizeof(bwr)))
                               ret = -EFAULT;
                       goto out;
               }
       }
       ...
   //处理成功的情况，也需要将bwr拷贝回进程的用户态地址空间
       if (copy_to_user(ubuf, &bwr, sizeof(bwr))) {
               ret = -EFAULT;
               goto out;
       }
out:
       return ret;
}

4.4.3.1 重要结构 binder_write_read

binder的读写结构， 记录了binder中读和写的数据信息

struct binder_write_read {
       binder_size_t                write_size;          //要写入的字节数,write_buffer的总字节数
       binder_size_t                write_consumed; //驱动程序占用的字节数,write_buffer已消费的字节数
       binder_uintptr_t        write_buffer;   //写缓冲数据的指针
       binder_size_t                read_size;          //要读的字节数,read_buffer的总字节数
       binder_size_t                read_consumed;  //驱动程序占用的字节数,read_buffer已消费的字节数
       binder_uintptr_t        read_buffer;    //读缓存数据的指针
};

binder_thread_write() 和 binder_thread_read()的逻辑太冗长，加起来有1千多行，放到下一节的《Binder数据定向打击》 进行单独分析

6.红黑树分析

6.1 为什么binder驱动中要用到红黑树

其实我也不知道为什么，采用红黑树，说明我们要存储数据，要复合插入、修改、删除、查找等操作。既然不知道为什么，那就找几个复合类型的数据结构做个比较：
       1)数组

优点：内存大小固定，操作流程简单，查找数据方便；

缺点：内存要么很大，会浪费内存，要么很小，数据存储空间不够，删除或插入数据比较麻烦；

2)链表

优点：在内存中可以存在任何地方，不要求连续，不指定大小，扩展方便。链表大小不用定义，数据随意增删，增加数据和删除数据很容易；

缺点：查找数据时效率低，因为不具随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。要找到第三个人，必须从第一个人开始问起；

3)二叉树

 特点：左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大

 优点：快速查找，不需要为二叉树预先分配固定的空间，所的元素在树中是排序好的

缺点：极端情况下，时间复杂度会由O（logn）变成O（n），即变成了一种链式结构

4)平衡二叉树

特点：具有二叉树的全部特性，每个节点的左子树和右子树的高度差至多等于1 

优点：具有二叉树的所有优点，并解决了二叉树的 链式极端情况，时间复杂度保持在O（logn）

缺点：每次进行插入/删除节点的时候，几乎都会破坏平衡树的规则(每个节点的左子树和右子树的高度差至多等于1 )，每次都需要调整，使得性能大打折扣

5)红黑树

特点：具有二叉树的特点；根节点是黑色的；叶子节点不存数据；任何相邻的节点都不能同时为红色；每个节点，从该节点到达其可达的叶子节点是所路径，都包含相同数目的黑色节点

优点：具有二叉树所有特点，与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，减少性能消耗；

缺点：代码复杂，查找效率比平衡二叉树低

通过上面几个存储的数据结构，当我们需要频繁对数据进行插入、修改、删除、查找时，我们的选择如下：

平衡二叉树\红黑树 > 二叉树 > 链表 > 数组

其中红黑树虽然查找效率比平衡二叉树低，但是减少了性能消耗，这在内核中尤为重要，因此binder驱动中使用了红黑树。

当然上面的流程也只是我的推测，也有可能谷歌工程师开发时就喜欢用红黑树呢，当然这是题外话，不影响我们继续撸代码。

6.2 binder_proc 中的4棵红黑树

struct binder_proc {
    struct hlist_node proc_node;
    struct rb_root threads;
    struct rb_root nodes;
    struct rb_root refs_by_desc;
    struct rb_root refs_by_node;
    ...
}

threads 执行传输动作的线程信息, nodes 记录binder实体,refs_by_desc 和refs_by_node 记录binder代理, 便于快速查找

以nodes树为例，每个binder_node中都有一个rb_node节点，rb_node 又分为左子树和右子树，如图所示：

truct rb_root {
    struct rb_node *rb_node;
};

struct rb_node {
    unsigned long  __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

6.3 Binder 中红黑树的转换

在Binder驱动中，会为每个Client创建对应的Binder引用，即会为每个Client创建binder_ref对象；会为每一个Server都创建一个Binder实体，即会为每个Server都创建一个binder_node对象

 "Binder实体"和"Binder引用"可以很好的将Server和Client关联起来：因为Binder实体和Binder引用分别是Server和Client在Binder驱动中的体现。Client获取到Server对象后，"Binder引用所引用的Biner实体(即binder_ref.node)" 会指向 "Server对应的Biner实体"；同样的，Server被某个Client引用之后，"Server对应的Binder实体的引用列表(即，binder_node.refs)" 会包含 "Client对应的Binder引用"。

7.Binder协议码

BC码--Binder响应码：

BR码--Binder回复码：

代码路径：

\kernel\msm-4.9\drivers\android\binder.c

\kernel\msm-4.9\drivers\android\binder_alloc.c

github 中 LineageOS Kernel4.9代码下载地址：

https://github.com/LineageOS/android_kernel_google_msm-4.9

参考：

《Binder机制情景分析之深入驱动》

https://segmentfault.com/a/1190000017136925?utm_source=tag-newest

《Binder系列1—Binder Driver初探》

http://gityuan.com/2015/11/01/binder-driver/

《Binder（传输机制篇_上）》

https://my.oschina.net/youranhongcha/blog/152233

《Binder中的数据结构》

http://wangkuiwu.github.io/2014/09/02/Binder-Datastruct/

《linux内核中的红黑树代码解析》

https://www.cnblogs.com/chengxuyuancc/archive/2013/04/06/3002044.html