一 相关的数据结构

1.1 struct binder_proc中的相关成员

struct binder_proc {
    …
    struct list_head buffers; /*所有binder_buffer的链表，以起始地址大小生序排列，以方便相邻空闲的binder_buffer合并*/
    struct rb_root free_buffers; /*组织所有空闲的binder_buffer在该红黑树中，以所管理的地址空间大小为序，便于地址空间的分配*/
    struct rb_root allocated_buffers;  /*组织所有已分配的binder_buffer在该红黑树中，以地址大小为序，便于根据地址查找*/
    size_t free_async_space; /*空闲异步可用的地址空间*/

    struct page **pages; /*所有物理页指针数组，所有以分配的物理页在这里管理*/
    size_t buffer_size; /*mmap时请求的总地址空间大小*/
   ...
};

1.2 struct binder_buffer

struct binder_buffer {
    struct list_head entry; /* free and allocated entries by address，链接在proc->buffers所指链表中*/
    struct rb_node rb_node; /* free entry by size（空闲红黑树`free_buffers`以所管理的buffer大小组织）  */
                            /* or allocated entry by address  (已分配红黑树`allocated_buffers`以所管理buffer的虚拟地址大小组织)*/
    unsigned free:1;
    unsigned allow_user_free:1;
    unsigned async_transaction:1;
    unsigned debug_id:29;

    struct binder_transaction *transaction;

    struct binder_node *target_node;
    size_t data_size;
    size_t offsets_size;
    uint8_t data[0]; //数据内容的开始地址
};

二 地址空间分配

2.1 分配binder_buffer ---> binder_alloc_buff

static struct binder_buffer *binder_alloc_buf(struct binder_proc *proc,
                          size_t data_size,
                          size_t offsets_size, int is_async)
{
    struct rb_node *n = proc->free_buffers.rb_node;
    struct binder_buffer *buffer;
    size_t buffer_size;/*记录空闲节点的地址空间大小及最后申请分配的空间大小*/
    struct rb_node *best_fit = NULL;
    void *has_page_addr;
    void *end_page_addr;
    size_t size; /*记录data_size和offset_size在分别与指针大小对齐后的总大小*/

    if (proc->vma == NULL) {
        pr_err("%d: binder_alloc_buf, no vma\n",
               proc->pid);
        return NULL;
    }

    /*data_size,offsets_size分别按照指针长度对齐*/
    size = ALIGN(data_size, sizeof(void *)) +
        ALIGN(offsets_size, sizeof(void *));

    if (size < data_size || size < offsets_size) {
        binder_user_error("%d: got transaction with invalid size %zd-%zd\n",
                proc->pid, data_size, offsets_size);
        return NULL;
    }

    /*如果是异步的，还要检查异步空间是否充足*/
    if (is_async &&
        proc->free_async_space < size + sizeof(struct binder_buffer)) {
        binder_debug(BINDER_DEBUG_BUFFER_ALLOC,
                 "%d: binder_alloc_buf size %zd failed, no async space left\n",
                  proc->pid, size);
        return NULL;
    }

  //在空闲的节点中，查找大小最合适的buffer，空闲节点是以大小为序组织在红黑树中的
    while (n) {
        buffer = rb_entry(n, struct binder_buffer, rb_node);
        BUG_ON(!buffer->free);
        buffer_size = binder_buffer_size(proc, buffer); //获取该节点buffer的大小

        if (size < buffer_size) {//节点的buffer大小比请求的大
            best_fit = n;
            n = n->rb_left;
        } else if (size > buffer_size)//节点的buffer大小比请求的小
            n = n->rb_right;
        else {//节点的buffer大小比请求的相等
            best_fit = n;
            break;
        }
    }//该循环结束后，best_fit指向空闲节点中，buffer的大小与请求大小最接近且满足请求大小的节点
    if (best_fit == NULL) {
        pr_err("%d: binder_alloc_buf size %zd failed, no address space\n",
            proc->pid, size);
        return NULL;
    }
    if (n == NULL) {//没有找到大小与请求大小正好的节点(节点拥有的地址空间本次分配后有剩余)，将buffer和buffer_size修正为best_fit指向节点的地址和大小，如果找到大小相等的，这两个值已经是正确的了。
        buffer = rb_entry(best_fit, struct binder_buffer, rb_node);
        buffer_size = binder_buffer_size(proc, buffer);
    }

    binder_debug(BINDER_DEBUG_BUFFER_ALLOC,
             "%d: binder_alloc_buf size %zd got buffer %p size %zd\n",
              proc->pid, size, buffer, buffer_size);

    /*该binder_buffer节点所管理的虚拟地址空间最后一页的起始虚拟地址*/
    has_page_addr =
        (void *)(((uintptr_t)buffer->data + buffer_size) & PAGE_MASK);
    if (n == NULL) {/*节点所拥有的空间大于请求分配的空间，需重新计算*/
        if (size + sizeof(struct binder_buffer) + 4 >= buffer_size) /*节点空闲地址空间在本次分配后不足于容纳其他的binder_buffer*/
            buffer_size = size; /* no room for other buffers */  /*不需要新的binder_buffer来记录节点分配后剩余空间信息*/
        else
            buffer_size = size + sizeof(struct binder_buffer);  /*多申请一个binder_buffer，记录节点分配后剩余空间的状态*/
    }
    /*请求地址空间中最后一页的页末地址*/
    end_page_addr =
        (void *)PAGE_ALIGN((uintptr_t)buffer->data + buffer_size);
    if (end_page_addr > has_page_addr)
        end_page_addr = has_page_addr;
    /*分配物理页框，并和内核态地址和用户地址空间建立映射*/
    if (binder_update_page_range(proc, 1,
        /*这里从data开始进行页对齐的原因是：binder_buffer本身所在的页已经分配过物理页框了*/
        (void *)PAGE_ALIGN((uintptr_t)buffer->data), 
        end_page_addr, NULL))
        return NULL;

    /*从空闲buffer红黑树中移除该节点*/
    rb_erase(best_fit, &proc->free_buffers);
    buffer->free = 0;
    /*将分配的binder_buffer插入到已分配地址的红黑树中, 详见2.3*/
    binder_insert_allocated_buffer(proc, buffer);
    /* 如果找到节点所拥有的buffer大小超过请求分配的大小（外加sizeof(struct binder_buffer) + 4），
    *  则将节点剩余未分配的空间重新插入到空闲buffer的红黑树中
    */
    if (buffer_size != size) {
        struct binder_buffer *new_buffer = (void *)buffer->data + size;    
        list_add(&new_buffer->entry, &buffer->entry);/*将new_buffer插入到buffer之后*/
        new_buffer->free = 1;
        binder_insert_free_buffer(proc, new_buffer); /*详见2.3*/
    }
    binder_debug(BINDER_DEBUG_BUFFER_ALLOC,
             "%d: binder_alloc_buf size %zd got %p\n",
              proc->pid, size, buffer);
    /*更新相关字段：data_size, offsets_size, is_async*/
    buffer->data_size = data_size;
    buffer->offsets_size = offsets_size;
    buffer->async_transaction = is_async;
    if (is_async) {//如果是异步的，还需要更新异步空间的大小。
        proc->free_async_space -= size + sizeof(struct binder_buffer);
        binder_debug(BINDER_DEBUG_BUFFER_ALLOC_ASYNC,
                 "%d: binder_alloc_buf size %zd async free %zd\n",
                  proc->pid, size, proc->free_async_space);
    }

    return buffer;
}

binder_alloc_buf首先将请求的data_size和offsets_size对齐后相加，求得本次请求分配空间的总大小。如果是异步的，还要进一步判断异步空间是否充足。然后在proc的free_buffers红黑树中查找大小合适binder_buffer节点，该红黑树是以binder_buffer所拥有的地址空间的大小为序组织的。如果被分配节点的地址空间在分配完本次请求的大小后还能容纳一个binder_buffer + 4个字节的空间，则需重新创建一个binder_buffer用于管理分配后的剩余地址空间，此时请求binder_update_page_range的分配大小需额外增加一个binder_buffer的大小，否则不需要，然后将求得的所需地址空间大小进行页对齐后，调用binder_update_page_range分配物理页框，建立内核态和用户态的地址映射。紧接着将被分配节点从free_buffers红黑树中删除，更新空闲标识为0，然后插入到已分配红黑树allocated_buffers中，该红黑树以binder_buffer的地址大小为序组织的。如果被分配节点在分配完请求的地址空间大小后还有剩余，需将剩余的地址空间用一个新的binder_buffer管理起来，并插入到proc的buffers链表及free_buffers红黑树中。最后更新分配节点的相关字段，如果申请的异步空间，还需更新异步剩余空间，就可以将分配节点地址返回给调用者了。

2.2 将空闲的binder_buffer插入到空闲红黑树(free_buffers)中

static void binder_insert_free_buffer(struct binder_proc *proc,
                      struct binder_buffer *new_buffer)
{
    struct rb_node **p = &proc->free_buffers.rb_node;
    struct rb_node *parent = NULL;
    struct binder_buffer *buffer;
    size_t buffer_size;
    size_t new_buffer_size;

    BUG_ON(!new_buffer->free);

    new_buffer_size = binder_buffer_size(proc, new_buffer);

    binder_debug(BINDER_DEBUG_BUFFER_ALLOC,
             "%d: add free buffer, size %zd, at %p\n",
              proc->pid, new_buffer_size, new_buffer);
  /*查找合适的插入位置，该红黑树以buffer的大小为序组织*/
    while (*p) {
        parent = *p;
        buffer = rb_entry(parent, struct binder_buffer, rb_node);
        BUG_ON(!buffer->free);

        buffer_size = binder_buffer_size(proc, buffer);

        if (new_buffer_size < buffer_size)
            p = &parent->rb_left;
        else
            p = &parent->rb_right;
    }
    rb_link_node(&new_buffer->rb_node, parent, p);
    rb_insert_color(&new_buffer->rb_node, &proc->free_buffers);
}

2.3 将分配的binder_buffer插入到的已分配的红黑树(allocated_buffers)中：

static void binder_insert_allocated_buffer(struct binder_proc *proc,
                       struct binder_buffer *new_buffer)
{
    struct rb_node **p = &proc->allocated_buffers.rb_node;
    struct rb_node *parent = NULL;
    struct binder_buffer *buffer;

    BUG_ON(new_buffer->free);

  /*查找合适的插入位置，该红黑树是以binder_buffer的地址大小为序组织的*/
    while (*p) {
        parent = *p;
        buffer = rb_entry(parent, struct binder_buffer, rb_node);
        BUG_ON(buffer->free);

        if (new_buffer < buffer)
            p = &parent->rb_left;
        else if (new_buffer > buffer)
            p = &parent->rb_right;
        else
            BUG();
    }
    rb_link_node(&new_buffer->rb_node, parent, p);//插入
    rb_insert_color(&new_buffer->rb_node, &proc->allocated_buffers);
}

需要注意proc已分配的binder_buffer红黑树allocated_buffers是以binder_buffer的地址本身的大小为序组织的，而空闲binder_buffer的红黑树free_buffers则是以binder_buffer中所拥有的地址空间大小为序组织的。

三 地址空间会回收

3.1 释放地址空间binder_free_buf

static void binder_free_buf(struct binder_proc *proc,
                struct binder_buffer *buffer)
{
    size_t size, buffer_size;

    buffer_size = binder_buffer_size(proc, buffer);

    size = ALIGN(buffer->data_size, sizeof(void *)) +
        ALIGN(buffer->offsets_size, sizeof(void *));

    binder_debug(BINDER_DEBUG_BUFFER_ALLOC,
             "%d: binder_free_buf %p size %zd buffer_size %zd\n",
              proc->pid, buffer, size, buffer_size);

    BUG_ON(buffer->free);
    BUG_ON(size > buffer_size);
    BUG_ON(buffer->transaction != NULL);
    BUG_ON((void *)buffer < proc->buffer);
    BUG_ON((void *)buffer > proc->buffer + proc->buffer_size);

  /*如果是异步事务，要更新异步空闲地址的大小*/
    if (buffer->async_transaction) {
        proc->free_async_space += size + sizeof(struct binder_buffer);

        binder_debug(BINDER_DEBUG_BUFFER_ALLOC_ASYNC,
                 "%d: binder_free_buf size %zd async free %zd\n",
                  proc->pid, size, proc->free_async_space);
    }

  /*释放data所拥有的地址空间的物理页框，并取消内核和用户态对该物理页框的地址映射*/
    binder_update_page_range(proc, 0,
        (void *)PAGE_ALIGN((uintptr_t)buffer->data),
        (void *)(((uintptr_t)buffer->data + buffer_size) & PAGE_MASK),
        NULL);
    /*将该binder_buffer从已分配红黑树中移除*/
    rb_erase(&buffer->rb_node, &proc->allocated_buffers);
    /*重新标识该buffer为空闲状态*/
    buffer->free = 1;

    /*如果不是最后节点，且后一个节点也是空闲状态，尝试将其合并*/
    if (!list_is_last(&buffer->entry, &proc->buffers)) {
        struct binder_buffer *next = list_entry(buffer->entry.next,
                        struct binder_buffer, entry);
        if (next->free) {
            /*从free_buffers红黑树中移除后一个节点*/
            rb_erase(&next->rb_node, &proc->free_buffers);
            /*删除后一个`binder_buffer`节点，以将其合并到当前`binder_buffer`中*/
            binder_delete_free_buffer(proc, next);
        }
    }
    /*如果不是第一个节点，且前一个节点也是空闲状态，尝试将其合并*/
    if (proc->buffers.next != &buffer->entry) {
        struct binder_buffer *prev = list_entry(buffer->entry.prev,
                        struct binder_buffer, entry);

        if (prev->free) {
            /*删除当前`binder_buffer`，以合并到前一个`binder_buffer`中*/
            binder_delete_free_buffer(proc, buffer);
            /*从free_buffers红黑树中移除前一个节点*/
            rb_erase(&prev->rb_node, &proc->free_buffers);
            buffer = prev;
        }
    }
    /*将新空闲节点插入free_buffers红黑树中*/
    binder_insert_free_buffer(proc, buffer);
}

binder_free_buf的功能是释放一个binder_buffer所管理的地址空间，具体过程是：它首先释放binder_buffer的data域所占据的地址空间，解除地址内核及用户态的地址映射；接着查看其之后是否也处于空闲状态，如果是的话，合并到当前节点，并尝试释放其后binder_buffer节点所占据的物理页。接着查看前一个的节点，是否处于空闲状态，如果是的话，就将自己合并到前一个节点中，并尝试释放其本身binder_buffer节点所占据的物理页；最后将合并后的节点（如果前后节点是空闲的话）插入到proc的free_buffer红黑树中。

3.2 从buffers链表中删除一个空闲节点 —> binder_delete_free_buffer

static void binder_delete_free_buffer(struct binder_proc *proc,
                      struct binder_buffer *buffer)
{
    struct binder_buffer *prev, *next = NULL;
    int free_page_end = 1;
    int free_page_start = 1;

    BUG_ON(proc->buffers.next == &buffer->entry);/*确定被删除的节点不是buffers中的唯一一个节点*/
    prev = list_entry(buffer->entry.prev, struct binder_buffer, entry);/*取出被删除节点在buffers链表中的前一个节点*/
    BUG_ON(!prev->free);/*确保前一个节点是空闲状态，因为这样节点删除后，其管理的地址空间才能合并到前一个节点中*/
    if (buffer_end_page(prev) == buffer_start_page(buffer)) {
        /* 被删除节点的起始物理页框地址与前一个节点的结束地址（不包括data）所在物理页框是同一个，
        *  此时不能释放这个物理页框，将free_page_start置为0 */
        free_page_start = 0;
        if (buffer_end_page(prev) == buffer_end_page(buffer))
        /* 被删除节点的结束地址(不包括data)物理页框地址与前一个binder_buffer节点的结束地址（不包括data）所在物理页框是同一个，
        *  此时不能释放这个物理页框，将free_page_end置为0 */
            free_page_end = 0;
        binder_debug(BINDER_DEBUG_BUFFER_ALLOC,
                 "%d: merge free, buffer %p share page with %p\n",
                  proc->pid, buffer, prev);
    }

    if (!list_is_last(&buffer->entry, &proc->buffers)) {/*不是buffers中的最后一个节点*/
        next = list_entry(buffer->entry.next, /*取出被删除节点在buffers链表中的下一个节点*/
                  struct binder_buffer, entry);
        if (buffer_start_page(next) == buffer_end_page(buffer)) {
        /*被删除节点的结束地址(不包括data)物理页框地址与后一个binder_buffer节点的结束地址所在物理页框是同一个，
        *  此时不能释放这个物理页框，将free_page_end置为0 */
            free_page_end = 0;
            if (buffer_start_page(next) == buffer_start_page(buffer))
             /* 被删除节点的结束地址(不包括data)物理页框地址与后一个binder_buffer节点的开始地址所在物理页框是同一个，
              * 此时不能释放这个物理页框，将free_page_start置为0 */
                free_page_start = 0;
            binder_debug(BINDER_DEBUG_BUFFER_ALLOC,
                     "%d: merge free, buffer %p share page with %p\n",
                      proc->pid, buffer, prev);
        }
    }
    /*在proc的buffers中删除该binder_buffer节点*/
    list_del(&buffer->entry);
    if (free_page_start || free_page_end) {
        binder_debug(BINDER_DEBUG_BUFFER_ALLOC,
                 "%d: merge free, buffer %p do not share page%s%s with %p or %p\n",
                 proc->pid, buffer, free_page_start ? "" : " end",
                 free_page_end ? "" : " start", prev, next);
        /*解除用户态和内核态地址空间对物理页的映射，并释放物理页框*/
        binder_update_page_range(proc, 0,
             free_page_start ? buffer_start_page(buffer) : buffer_end_page(buffer),
            (free_page_end ? buffer_end_page(buffer) : buffer_start_page(buffer)) + PAGE_SIZE, 
            NULL);
    }
}

• binder_delete_free_buffer该函数的主要功能是从proc->buffers链表中删除一个空闲的binder_buffer, 在删除一个节点前，要先确保被删除节点的前一个节点是处在空闲状态的，这样才有可能将被删除节点的所管理的地址空间合并到前一个节点。
• 因为一个binder_buffer节点可能跨物理页框存储，所以用了两个变量free_page_start,free_page_end来表示是否能释放binder_buffer开始地址和结束地址所在页面。
  • free_page_start: 标识是否能将被删除节点开始地址所在页面释放；如果前一个节点的结束地址或者后一个节点的开始地址也落在了该物理页面，则不能释放该物理页框，值置为0。
  • free_page_end: 标识是否能将被删除节点结束地址所在页面释放，注意包括data域的地址空间；如果前一个节点的结束地址或者后一个节点的开始地址也落在了该物理页面，则不能释放该物理页框，值置为0。
• 最后根据free_page_start,free_page_end决定如何释放物理页：
  • free_page_start和free_page_end都为0: 不需要释放物理页，因为binder_buffer所在的物理页框还在被它之前或者之后节点使用。
  • free_page_start为0，free_page_end为1: 不能释放binder_buffer开始地址所在页框，但是需要释放结束地址所在页框 ——— 此时binder_buffer是跨页框存放的。释放的地址空间范围是binder_buffer结束地址所在页框的起始到结束之间的一页地址空间。
  • free_page_start为1，free_page_end为0: 释放binder_buffer开始地址所在页框，但是不能释放结束地址所在页框 ——— 此时binder_buffer是跨页框存放的。释放的地址空间范围是binder_buffer开始地址所在页框的起始到结束之间的一页地址空间。
  • free_page_start为1，free_page_end为1: 释放binder_buffer开始地址和结束地址所在页框 ——— 此时binder_buffer可能是在同一个页框中，也可能跨页框存放的。如果没有跨页，则释放的地址空间范围是binder_buffer所在那个页框的起始到结束之间的一页地址空间；如果是跨页的，则释放的是binder_buffer地址开始所在页框加上binder_buffer结束地址所在页框，两个页框的地址空间。

3.2.1 计算binder_buffer的起始及结束地址所在页的页面起始地址。

/*binder_buffer节点所在的起始页地址*/
static void *buffer_start_page(struct binder_buffer *buffer)                    
{                                                                               
     return (void *)((uintptr_t)buffer & PAGE_MASK/*对齐到页开始地址*/);                             
 }                                                                               
   
/*binder_buffer节点所在的末页的页地址，注意不包括data所指的区间，对齐到页开始地址*/ 
static void *buffer_end_page(struct binder_buffer *buffer) 
 {  
     return (void *)(((uintptr_t)(buffer + 1) - 1) & PAGE_MASK);  
 }