malloc源码分析——_int_malloc

发表于 | 分类于 |

1. malloc源码分析—_int_malloc

根据上一章的分析，malloc会调用__libc_malloc分配内存，__libc_malloc会调用malloc_hook_ini 进行初始化，然后回调__libc_malloc函数，这时候会执行_int_malloc开始分配内存，定义在malloc.c中，因为非常长，这里分段来看，

1.1 _int_malloc第一部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static void * _int_malloc(mstate av, size_t bytes) {
    INTERNAL_SIZE_T nb;
    unsigned int idx;
    mbinptr bin;
    mchunkptr victim;
    INTERNAL_SIZE_T size;
    int victim_index;
    mchunkptr remainder;
    unsigned long remainder_size;
    unsigned int block;
    unsigned int bit;
    unsigned int map;
    mchunkptr fwd;
    mchunkptr bck;
    const char *errstr = NULL;
    checked_request2size(bytes, nb);
    if (__glibc_unlikely(av == NULL)) {
        void *p = sysmalloc(nb, av);
        if (p != NULL)
            alloc_perturb(p, bytes);
        return p;
    }
    ...

首先调用checked_request2size将需要分配的内存大小bytes转换为chunk的大小。checked_request2size是个宏定义，主要调用request2size进行计算，

1
2
3
4
#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

为了说明request2size，首先看一下ptmalloc中关于chunk的定义，

1
2
3
4
5
6
7
8
9
10
11
struct malloc_chunk {
    INTERNAL_SIZE_T prev_size;
    INTERNAL_SIZE_T size;
    struct malloc_chunk* fd; 
    struct malloc_chunk* bk;
    struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
    struct malloc_chunk* bk_nextsize;
};

当一个chunk为空闲时，至少要有prev_size、size、fd和bk四个参数，因此MINSIZE就代表了这四个参数需要占用的内存大小；而当一个chunk被使用时，prev_size可能会被前一个chunk用来存储，fd和bk也会被当作内存存储数据，因此当chunk被使用时，只剩下了size参数需要设置，request2size中的SIZE_SZ就是INTERNAL_SIZE_T类型的大小，因此至少需要req+SIZE_SZ的内存大小。MALLOC_ALIGN_MASK用来对齐，因此request2size就计算出了所需的chunk的大小。

传入的参数av是在上一章__libc_malloc中调用arena_get获得的分配去指针，如果为null，就表示没有分配区可用，这时候就直接调用sysmalloc通过mmap获取chunk。

1.2 sysmalloc

sysmalloc的代码很长，但只有前面一小部分是这里需要分析的，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
static void * sysmalloc(INTERNAL_SIZE_T nb, mstate av) {
    mchunkptr old_top;
    INTERNAL_SIZE_T old_size;
    char *old_end;
    long size;
    char *brk;
    long correction;
    char *snd_brk;
    INTERNAL_SIZE_T front_misalign;
    INTERNAL_SIZE_T end_misalign;
    char *aligned_brk;
    mchunkptr p;
    mchunkptr remainder;
    unsigned long remainder_size;
    size_t pagesize = GLRO(dl_pagesize);
    bool tried_mmap = false;
    if (av == NULL
            || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
                    && (mp_.n_mmaps < mp_.n_mmaps_max))) {
        char *mm;
        try_mmap:
        if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
            size = ALIGN_UP(nb + SIZE_SZ, pagesize);
        else
            size = ALIGN_UP(nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
        tried_mmap = true;
        if ((unsigned long) (size) > (unsigned long) (nb)) {
            mm = (char *) (MMAP(0, size, PROT_READ | PROT_WRITE, 0));
            if (mm != MAP_FAILED) {
                if (MALLOC_ALIGNMENT == 2 * SIZE_SZ) {
                    assert(
                            ((INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK) == 0);
                    front_misalign = 0;
                } else
                    front_misalign = (INTERNAL_SIZE_T) chunk2mem(
                            mm) & MALLOC_ALIGN_MASK;
                if (front_misalign > 0) {
                    correction = MALLOC_ALIGNMENT - front_misalign;
                    p = (mchunkptr) (mm + correction);
                    p->prev_size = correction;
                    set_head(p, (size - correction) | IS_MMAPPED);
                } else {
                    p = (mchunkptr) mm;
                    set_head(p, size | IS_MMAPPED);
                }
                int new = atomic_exchange_and_add(&mp_.n_mmaps, 1) + 1;
                atomic_max(&mp_.max_n_mmaps, new);
                unsigned long sum;
                sum = atomic_exchange_and_add(&mp_.mmapped_mem, size) + size;
                atomic_max(&mp_.max_mmapped_mem, sum);
                check_chunk (av, p);
                return chunk2mem(p);
            }
        }
    }
    if (av == NULL)
        return 0;
    ...

首先，可以直接通过mmap分配chunk有两个前提条件，一是需要分配的内存大小大于实用mmap进行分配的阀值mp_.mmap_threshold，二是通过mp_.n_mmaps判断系统还可以有可以使用mmap分配的空间。
下面就要计算需要分配多少内存，在前面已经通过request2size计算了需要分配的内存大小，这里为什么还要计算呢？这是因为通过使用mmap直接分配的chunk不需要添加到链表中，因此不存在前后关系，当一个chunk被使用时，不能借用后一个chunk的prev_size字段，这里需要把该字段的长度SIZE_SZ加上。并且这里假设MALLOC_ALIGNMENT == 2 * SIZE_SZ。
接下来判断需要分配的内存大小是否会溢出，然后就调用MMAP分配内存，MMAP是一个宏定义，最后就是通过系统调用来分配内存，后面来看这个函数。
再往下就是通过set_head在chunk中的size参数里设置标志位，因为chunk是按8字节对齐的，而size标识chunk占用的字节数，所以最后三位是没有用的，ptmalloc将这三位用来作为标志位，这里便是设置其中一个标志位，用来标识该chunk是直接通过mmap分配的。

1
#define set_head(p, s)       ((p)->size = (s))

设置完标志位后，接下来就是设置全局变量_mp，将mp_.n_mmaps加1，表示当前进程通过mmap分配的chunk个数，对应的mp_.max_n_mmaps表示最大chunk个数。mp_.mmapped_mem标识已经通过mmap分配的内存大小，mp_.max_mmapped_mem对应可分配内存的最大值。其中，atomic_exchange_and_addb表示原子加，atomic_max则是原子取最大值。
最后，通过chunk2mem返回chunk中内存的起始指针。

1
#define chunk2mem(p)   ((void*)((char*)(p) + 2*SIZE_SZ))

这里也可以知道，当chunk被使用时，用户是从结构体中的变量fd开始使用内存的。回到_int_malloc函数中，假设通过sysmalloc分配成功，接下来就需要调用alloc_perturb对刚刚分配的内存进行初始化，

1
2
3
4
static void alloc_perturb(char *p, size_t n) {
    if (__glibc_unlikely(perturb_byte))
        memset(p, perturb_byte ^ 0xff, n);
}

刚函数没有什么实际意义，所以不管它。

1.3 MMAP

为了方便分析，这里贴一段调用MMAP的代码，

1
mm = (char *) (MMAP(0, size, PROT_READ | PROT_WRITE, 0));

MMAP在glibc中为宏定义，其定义很长，这里简单将它改写，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define INTERNAL_SYSCALL_MAIN_6(name, err, arg1, arg2, arg3,        \
                arg4, arg5, arg6)           \
  struct libc_do_syscall_args _xv =                 \
    {                                   \
      (int) (0),                            \
      (int) (-1),                           \
      (int) (0)                         \
    };                                  \
    asm volatile (                          \
    "movl %1, %%eax\n\t"                        \
    "call __libc_do_syscall"                        \
    : "=a" (resultvar)                          \
    : "i" (__NR_mmap2), "c" (size), "d" (PROT_READ | PROT_WRITE), "S" (MAP_ANONYMOUS|MAP_PRIVATE), "D" (&_xv) \
    : "memory", "cc")

__libc_do_syscall是一段汇编代码，最后就是系统调用啦，这里就进入了linux内核中的代码，在arch/x86/entry/syscalls/syscall_32.tbl中有如下定义，

1
192 i386    mmap2           sys_mmap_pgoff

因此，MMAP最后调用linux内核中的sys_mmap_pgoff函数，定义在mm/mmap.c中，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
SYSCALL_DEFINE6(mmap_pgoff, unsigned long, addr, unsigned long, len,
        unsigned long, prot, unsigned long, flags,
        unsigned long, fd, unsigned long, pgoff){
    struct file *file = NULL;
    unsigned long retval = -EBADF;
    if (!(flags & MAP_ANONYMOUS)) {
        ...
    } else if (flags & MAP_HUGETLB) {
        ...
    }
    flags &= ~(MAP_EXECUTABLE | MAP_DENYWRITE);
    retval = vm_mmap_pgoff(file, addr, len, prot, flags, pgoff);
    return retval;
}

SYSCALL_DEFINE6是个宏定义，就是将系统调用号和函数联系起来，这里其实就是定义了sys_mmap_pgoff函数。根据前面传入的flags，这里直接跳过判断，因此下面主要就是执行vm_mmap_pgoff函数，定义在mm/utils.c中，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
unsigned long vm_mmap_pgoff(struct file *file, unsigned long addr,
    unsigned long len, unsigned long prot,
    unsigned long flag, unsigned long pgoff)
{
    unsigned long ret;
    struct mm_struct *mm = current->mm;
    unsigned long populate;
    ret = security_mmap_file(file, prot, flag);
    if (!ret) {
        down_write(&mm->mmap_sem);
        ret = do_mmap_pgoff(file, addr, len, prot, flag, pgoff,
                    &populate);
        up_write(&mm->mmap_sem);
        if (populate)
            mm_populate(ret, populate);
    }
    return ret;
}

这里首先获得进程的mm_struct结构，该结构保存了虚拟内存和物理内存的映射关系，security_mmap_file和linux安全有关，这里不关心，因此调用do_mmap_pgoff执行主要的mmap内容，前后加了信号量。do_mmap_pgoff定义在mm/mmap.c中，这里省略了很多不关键的代码，

1.4 do_mmap_pgoff

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
unsigned long do_mmap_pgoff(struct file *file, unsigned long addr,
            unsigned long len, unsigned long prot,
            unsigned long flags, unsigned long pgoff,
            unsigned long *populate){
    struct mm_struct *mm = current->mm;
    vm_flags_t vm_flags;
    *populate = 0;
    if (!(flags & MAP_FIXED))
        addr = round_hint_to_min(addr);
    len = PAGE_ALIGN(len);
    addr = get_unmapped_area(file, addr, len, pgoff, flags);
    vm_flags = calc_vm_prot_bits(prot) | calc_vm_flag_bits(flags) |
            mm->def_flags | VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;
    if (file) {
        ...
    } else {
        switch (flags & MAP_TYPE) {
        case MAP_SHARED:
            ...
            break;
        case MAP_PRIVATE:
            pgoff = addr >> PAGE_SHIFT;
            break;
        default:
            return -EINVAL;
        }
    }
    addr = mmap_region(file, addr, len, vm_flags, pgoff);
    return addr;
}

传入的flags没有MAP_FIXED，表是映射的地址不固定（这里传入的addr为0），由内核分配。接下来通过调用round_hint_to_min和PAGE_ALIGN对地址和长度进行页对齐，并且检查地址是否溢出或者太小。
下面调用get_unmapped_area在进程的用户空间里查找已经分配的虚拟内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
unsigned long get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, unsigned long pgoff, unsigned long flags){
    unsigned long (*get_area)(struct file *, unsigned long,
                  unsigned long, unsigned long, unsigned long);
    ...
    get_area = current->mm->get_unmapped_area;
    ...
    addr = get_area(file, addr, len, pgoff, flags);
    if (IS_ERR_VALUE(addr))
        return addr;
    ...
    return addr;
}

这里首先获取get_area函数指针用来查找用户空间中已经分配的虚拟内存，这里根据mmap的方向可以获取到arch_get_unmapped_area_topdown或者arch_get_unmapped_area两个函数指针，其arch_get_unmapped_area_topdown对应的mmap方向是从高地址往低地址方向扩展的，本章还是分析传统的从低地址往高地址拓展对应的arch_get_unmapped_area函数，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
unsigned long
arch_get_unmapped_area(struct file *filp, unsigned long addr,
        unsigned long len, unsigned long pgoff, unsigned long flags){
    struct mm_struct *mm = current->mm;
    struct vm_area_struct *vma;
    struct vm_unmapped_area_info info;
    unsigned long begin, end;
    if (flags & MAP_FIXED)
        return addr;
    ...
    if (addr) {
        addr = PAGE_ALIGN(addr);
        vma = find_vma(mm, addr);
        if (end - len >= addr &&
            (!vma || addr + len <= vma->vm_start))
            return addr;
    }
    ...
}

首先，如果是固定地址映射，直接返回addr地址。本章分析的不是这种情况，省略的代码和一些随机映射有关，这里省略了不分析。这样就进入了底下的if语句里，对地址对齐后，就调用find_vma查找addr地址开始已经分配出去的虚拟内存vma，最后addr到addr+len这个地址范围内没有虚拟内存，就将地址返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
    struct rb_node *rb_node;
    struct vm_area_struct *vma;
    vma = vmacache_find(mm, addr);
    if (likely(vma))
        return vma;
    rb_node = mm->mm_rb.rb_node;
    vma = NULL;
    while (rb_node) {
        struct vm_area_struct *tmp;
        tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
        if (tmp->vm_end > addr) {
            vma = tmp;
            if (tmp->vm_start <= addr)
                break;
            rb_node = rb_node->rb_left;
        } else
            rb_node = rb_node->rb_right;
    }
    if (vma)
        vmacache_update(addr, vma);
    return vma;
}

这里就不往下继续看代码的，简单来说，进程已经分配的虚拟内存保存在一个红黑树中，红黑树简单的作用就是防止一个树结构不平衡，出现某个左子树严重大于右子树的情况。为了加快查找的速度，这里设立了缓存。通过观察while结构，这里就是查找第一个结束地址大于addr的已经分配的虚拟内存，然后返回。

回到do_mmap_pgoff中，calc_vm_prot_bits和calc_vm_flag_bits用来将prot和flags中的标志位转化为vm的标志位，例如prot中的PROT_READ转化为VM_READ，flags中的MAP_GROWSDOWN转化为VM_GROWSDOWN。根据前面prot和flags中的值，这里转化后，vm_flags为VM_READ|VM_WRITE|mm->def_flags | VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC。最后就调用mmap_region构造一个vma用来保存刚刚获得的虚拟内存。

1.5 mmap_region

为了方便分析和查看，这里对mmap_region代码做了适当的删除和改写，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
unsigned long mmap_region(struct file *file, unsigned long addr,
        unsigned long len, vm_flags_t vm_flags, unsigned long pgoff)
{
    struct mm_struct *mm = current->mm;
    struct vm_area_struct *vma, *prev;
    int error;
    struct rb_node **rb_link, *rb_parent;
    unsigned long charged = 0;
    if (!may_expand_vm(mm, len >> PAGE_SHIFT)) {
        ...
    }
    error = -ENOMEM;
    while (find_vma_links(mm, addr, addr + len, &prev, &rb_link,
                  &rb_parent)) {
        if (do_munmap(mm, addr, len))
            return -ENOMEM;
    }
    vm_flags |= VM_ACCOUNT;
    vma = vma_merge(mm, prev, addr, addr + len, vm_flags, NULL, file, pgoff,
            NULL);
    if (vma)
        goto out;
    vma = kmem_cache_zalloc(vm_area_cachep, GFP_KERNEL);
    vma->vm_mm = mm;
    vma->vm_start = addr;
    vma->vm_end = addr + len;
    vma->vm_flags = vm_flags;
    vma->vm_page_prot = vm_get_page_prot(vm_flags);
    vma->vm_pgoff = pgoff;
    INIT_LIST_HEAD(&vma->anon_vma_chain);
    vma_link(mm, vma, prev, rb_link, rb_parent);
out:
    vm_stat_account(mm, vm_flags, file, len >> PAGE_SHIFT);
    if (vm_flags & VM_LOCKED) {
        if (!((vm_flags & VM_SPECIAL) || is_vm_hugetlb_page(vma) ||
                    vma == get_gate_vma(current->mm)))
            mm->locked_vm += (len >> PAGE_SHIFT);
        else
            vma->vm_flags &= ~VM_LOCKED;
    }
    if (file)
        uprobe_mmap(vma);
    vma->vm_flags |= VM_SOFTDIRTY;
    vma_set_page_prot(vma);
    return addr;
}

may_expand_vm用于判断加上即将分配的虚拟内存，是否超过了系统的限制，如果超过了就需要进行相应的操作或者返回错误，这里假设不会超过系统限制，不管它。
find_vma_links的定义如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
static int find_vma_links(struct mm_struct *mm, unsigned long addr,
        unsigned long end, struct vm_area_struct **pprev,
        struct rb_node ***rb_link, struct rb_node **rb_parent){
    struct rb_node **__rb_link, *__rb_parent, *rb_prev;
    __rb_link = &mm->mm_rb.rb_node;
    rb_prev = __rb_parent = NULL;
    while (*__rb_link) {
        struct vm_area_struct *vma_tmp;
        __rb_parent = *__rb_link;
        vma_tmp = rb_entry(__rb_parent, struct vm_area_struct, vm_rb);
        if (vma_tmp->vm_end > addr) {
            if (vma_tmp->vm_start < end)
                return -ENOMEM;
            __rb_link = &__rb_parent->rb_left;
        } else {
            rb_prev = __rb_parent;
            __rb_link = &__rb_parent->rb_right;
        }
    }
    *pprev = NULL;
    if (rb_prev)
        *pprev = rb_entry(rb_prev, struct vm_area_struct, vm_rb);
    *rb_link = __rb_link;
    *rb_parent = __rb_parent;
    return 0;
}

该函数做了两件事，第一件事是重新检查一遍即将分配的虚拟内存是否已经被使用，主要是其他进程可能在这期间分配了该虚拟内存，第二件事是确定即将插入红黑树中的位置，保存在prev、rb_link和rb_parent中。prev保存了虚拟内存结束地址小于即将分配的虚拟内存开始地址的红黑树节点，rb_link一般为null，rb_parent简单说就是保存了离即将分配的虚拟内存开始地址最近的红黑树节点。

再往下通过vma_merge函数查看是否有虚拟空间可以合并，如果有则合并并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
struct vm_area_struct *vma_merge(struct mm_struct *mm,
            struct vm_area_struct *prev, unsigned long addr,
            unsigned long end, unsigned long vm_flags,
            struct anon_vma *anon_vma, struct file *file,
            pgoff_t pgoff, struct mempolicy *policy){
    pgoff_t pglen = (end - addr) >> PAGE_SHIFT;
    struct vm_area_struct *area, *next;
    int err;
    if (vm_flags & VM_SPECIAL)
        return NULL;
    if (prev)
        next = prev->vm_next;
    else
        next = mm->mmap;
    area = next;
    if (next && next->vm_end == end)
        next = next->vm_next;
    if (prev && prev->vm_end == addr &&
            mpol_equal(vma_policy(prev), policy) &&
            can_vma_merge_after(prev, vm_flags,
                        anon_vma, file, pgoff)) {
        if (next && end == next->vm_start &&
                mpol_equal(policy, vma_policy(next)) &&
                can_vma_merge_before(next, vm_flags,
                    anon_vma, file, pgoff+pglen) &&
                is_mergeable_anon_vma(prev->anon_vma,
                              next->anon_vma, NULL)) {
            err = vma_adjust(prev, prev->vm_start,
                next->vm_end, prev->vm_pgoff, NULL);
        } else
            err = vma_adjust(prev, prev->vm_start,
                end, prev->vm_pgoff, NULL);
        if (err)
            return NULL;
        khugepaged_enter_vma_merge(prev, vm_flags);
        return prev;
    }
    if (next && end == next->vm_start &&
            mpol_equal(policy, vma_policy(next)) &&
            can_vma_merge_before(next, vm_flags,
                    anon_vma, file, pgoff+pglen)) {
        if (prev && addr < prev->vm_end)
            err = vma_adjust(prev, prev->vm_start,
                addr, prev->vm_pgoff, NULL);
        else                    
            err = vma_adjust(area, addr, next->vm_end,
                next->vm_pgoff - pglen, NULL);
        if (err)
            return NULL;
        khugepaged_enter_vma_merge(area, vm_flags);
        return area;
    }
    return NULL;
}

这里就不详细分析这个函数了，主要通过prev->vm_end == addr判断即将分配的虚拟内存能否往前合并，通过end == next->vm_start判断即将分配的虚拟内存能否往后合并。其中，合并函数为vma_adjust。再往下就不分析了。

回到函数中，假设不能合并，就要通过slab构造一个vm_area_struct结构体，并设置相应的信息，slab是linux内核中分配小块内存的框架。然后通过vma_link插入到进程的红黑树中，

1
2
3
4
5
6
7
static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
            struct vm_area_struct *prev, struct rb_node **rb_link,
            struct rb_node *rb_parent){
    __vma_link(mm, vma, prev, rb_link, rb_parent);
    mm->map_count++;
}

__vma_link执行实际的插入操作，就是一些红黑树的操作，不往下看了。

回到mmap_region中，最后通过vma_set_page_prot继续设置一些标志位，然后就返回分配到的虚拟内存的起始地址addr了，该返回值一直向上返回，然后退出系统调用，返回到glibc中。
到这里简单总结一下MMAP，其实质就是通过mmap在进程的内存管理结构中的红黑树中分配一块没有使用的虚拟内存。

1.6 _int_malloc — fastbin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
static void * _int_malloc(mstate av, size_t bytes) {
    ...
    if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ())) {
        idx = fastbin_index(nb);
        mfastbinptr *fb = &fastbin(av, idx);
        mchunkptr pp = *fb;
        do {
            victim = pp;
            if (victim == NULL)
                break;
        } while ((pp = catomic_compare_and_exchange_val_acq(fb, victim->fd, victim))
                != victim);
        if (victim != 0) {
            if (__builtin_expect(fastbin_index (chunksize (victim)) != idx, 0)) {
                errstr = "malloc(): memory corruption (fast)";
                errout: malloc_printerr(check_action, errstr, chunk2mem(victim),
                        av);
                return NULL;
            }check_remalloced_chunk (av, victim, nb);
            void *p = chunk2mem(victim);
            alloc_perturb(p, bytes);
            return p;
        }
    }
    ...
}

get_max_fast返回fastbin可以存储内存的最大值，它在ptmalloc的初始化函数malloc_init_state中定义，后面会分析这个函数。
如果需要分配的内存大小nb落在fastbin的范围内，首先调用fastbin_index获得chunk大小nb对应的fastbin索引。

1
2
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

减2是根据fastbin存储的内存最小值计算的，本章假设SIZE_SZ=4，因此改写后idx = nb/8-2。
获得索引idx后，就通过fastbin取出空闲chunk链表指针，mfastbinptr其实就是malloc_chunk指针，

1
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

下面的do、while循环又是一个CAS操作，其作用是从刚刚得到的空闲chunk链表指针中取出第一个空闲的chunk(victim)，并将链表头设置为该空闲chunk的下一个chunk(victim->fd)。这里注意，fastbin中使用的是单链表，而后面smallbin使用的是双链表。
获得空闲chunk后，需要转换为可以存储的内存指针，chunk2mem上一章分析过了，就是返回malloc_chunk结构中fd所在的位置，因为当一个chunk被使用时，malloc_chunk结构中fd、bk包括后面的变量都没有用了。最后调用alloc_perturb对用户使用的内存进行初始化，然后就返回该内存的指针了。
假设fastbin中没有找到空闲chunk，或者fastbin根本没有初始化，或者其他原因，就进入下一步，从smallbin中获取内存，因此继续往下看.

1.7 _int_malloc — smallbin & largebin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
static void * _int_malloc(mstate av, size_t bytes) {
    ...
    if (in_smallbin_range(nb)) {
        idx = smallbin_index(nb);
        bin = bin_at (av, idx);
        if ((victim = last(bin)) != bin) {
            if (victim == 0)
                malloc_consolidate(av);
            else {
                bck = victim->bk;
                if (__glibc_unlikely(bck->fd != victim)) {
                    errstr = "malloc(): smallbin double linked list corrupted";
                    goto errout;
                }
                set_inuse_bit_at_offset(victim, nb);
                bin->bk = bck;
                bck->fd = bin;
                if (av != &main_arena)
                    victim->size |= NON_MAIN_ARENA;
                check_malloced_chunk (av, victim, nb);
                void *p = chunk2mem(victim);
                alloc_perturb(p, bytes);
                return p;
            }
        }
    }else {
        idx = largebin_index(nb);
        if (have_fastchunks(av))
            malloc_consolidate(av);
    }
    ...
}

首先

1
2
#define in_smallbin_range(sz)  \
  ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

基于本章假设，MIN_LARGE_SIZE经过换算后为512字节，因此低于512字节大小的内存块都归smallbin管理。
接下来通过bin_at获得smallbin空闲chunk链表指针，

1
2
3
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))               \
             - offsetof (struct malloc_chunk, fd))

这里乘2，并且减去fd相对于malloc_chunk中的位置是因为smallbin中存储的是fd和bk指针。
last定义为

1
#define last(b)      ((b)->bk)

该函数获得chunk的前一个chunk，由因为该chunk是smallbin的链表头，因此获得的是最后一个chunk，如果两者相等，表示对应的链表为空，什么都不做。
这里假设不相等，接下来有两种情况，第一种是victim=0，表示smallbin还没有初始化，这里需要特别说明一下这里。smallbin初始化为malloc_chunk指针数组，虽然定义为指针数组，但实际上存储的是fd和bk指针，如下所示
|fd|bk|fd|bk|…|fd|bk|
当smallbin还未初始化时，假设idx=1，根据bin_at取出的bin是一个虚拟的malloc_chunk指针，bin->fd，是第二个fd，因此bin->bk就是对应的bk，其值为0（bin->bk取出的不是地址，而是值）。因此当victim为0时，可以断定smallbin未初始化，此时调用malloc_consolidate进行初始化，

1
2
3
4
5
6
7
8
9
10
11
12
13
static void malloc_consolidate(mstate av) {
    ...
    if (get_max_fast () != 0) {
        ...
    } else {
        malloc_init_state(av);
        check_malloc_state(av);
    }
}

省略代码的if语句里是将fastbin中的chunk进行合并，然后添加到bins中，这里不分析，因为还未初始化，因此get_max_fast返回0，后面的章节碰到了再分析。进入else部分，check_malloc_state为空函数，malloc_init_state就是主要的初始化函数，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void malloc_init_state(mstate av) {
    int i;
    mbinptr bin;
    for (i = 1; i < NBINS; ++i) {
        bin = bin_at (av, i);
        bin->fd = bin->bk = bin;
    }
#if MORECORE_CONTIGUOUS
    if (av != &main_arena)
#endif
        set_noncontiguous(av);
    if (av == &main_arena)
        set_max_fast(DEFAULT_MXFAST);
    av->flags |= FASTCHUNKS_BIT;
    av->top = initial_top (av);
}

该函数做了四件事情，第一是初始化malloc_state中的bins数组，初始化的结果是对bins数组中的每一个fd和对应的bk，都初始化为fd的地址，即fd=bk=&fd；第二是设置fastbin可管理的内存块的最大值，即global_max_fast，DEFAULT_MXFAST定义为，

1
#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)

本章假设为64，set_max_fast定义为

1
2
3
#define set_max_fast(s) \
  global_max_fast = (((s) == 0)                           \
                     ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))

第三是设置一些标志位；第四是初始化分配去中的top chunk，就是一个malloc_chunk指针，fd保存在bins[0]中（smallbin中不使用bins[0]和bins[1]）。
重新回到_int_malloc中，假设victim不为0，下面就从双向链表中取出victim，设置其中的标志位，然后返回用户可分配的内存指针。
假设smallbin中没有空闲chunk可用，下面就要开始寻找largebin了，largebin_index定义为

1
2
3
4
#define largebin_index(sz) \
  (SIZE_SZ == 8 ? largebin_index_64 (sz)                                     \
   : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz)                     \
   : largebin_index_32 (sz))

根据前面SIZE_SZ的假设，这里largebin_index对应的就是largebin_index_32，定义为

1
2
3
4
5
6
7
#define largebin_index_32(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 38) ?  56 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

这里就不多解释了，如果需要知道sz和索引的对应关系，可以自己计算一下。
再接下来have_fastchunks根据标志位判断fastbin中是否有空闲chunk，如果有，就调用malloc_consolidate将这些chunk和并，然后加入到unsortedbin中。

1.8 _int_malloc — 合并fastbin

下面重新看一下malloc_consolidate函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
static void malloc_consolidate(mstate av) {
    mfastbinptr* fb;
    mfastbinptr* maxfb;
    mchunkptr p;
    mchunkptr nextp;
    mchunkptr unsorted_bin;
    mchunkptr first_unsorted;
    mchunkptr nextchunk;
    INTERNAL_SIZE_T size;
    INTERNAL_SIZE_T nextsize;
    INTERNAL_SIZE_T prevsize;
    int nextinuse;
    mchunkptr bck;
    mchunkptr fwd;
    if (get_max_fast () != 0) {
        clear_fastchunks(av);
        unsorted_bin = unsorted_chunks(av);
        maxfb = &fastbin(av, NFASTBINS - 1);
        fb = &fastbin(av, 0);
        do {
            p = atomic_exchange_acq(fb, 0);
            if (p != 0) {
                do {
                    check_inuse_chunk(av, p);
                    nextp = p->fd;
                    size = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
                    nextchunk = chunk_at_offset(p, size);
                    nextsize = chunksize(nextchunk);
                    if (!prev_inuse(p)) {
                        prevsize = p->prev_size;
                        size += prevsize;
                        p = chunk_at_offset(p, -((long ) prevsize));
                        unlink(av, p, bck, fwd);
                    }
                    if (nextchunk != av->top) {
                        nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
                        if (!nextinuse) {
                            size += nextsize;
                            unlink(av, nextchunk, bck, fwd);
                        } else
                            clear_inuse_bit_at_offset(nextchunk, 0);
                        first_unsorted = unsorted_bin->fd;
                        unsorted_bin->fd = p;
                        first_unsorted->bk = p;
                        if (!in_smallbin_range(size)) {
                            p->fd_nextsize = NULL;
                            p->bk_nextsize = NULL;
                        }
                        set_head(p, size | PREV_INUSE);
                        p->bk = unsorted_bin;
                        p->fd = first_unsorted;
                        set_foot(p, size);
                    }
                    else {
                        size += nextsize;
                        set_head(p, size | PREV_INUSE);
                        av->top = p;
                    }
                } while ((p = nextp) != 0);
            }
        } while (fb++ != maxfb);
    } else {
        ...
    }
}

因为ptmalloc前面已经初始化过了，这里直接进入if内部，首先通过clear_fastchunks设置标志位表示fastbin中存在空闲chunk，

1
#define clear_fastchunks(M)    catomic_or (&(M)->flags, FASTCHUNKS_BIT)

然后通过unsorted_chunks获得bins数组中unsortedbin对应的malloc_chunk指针（其fd和bk指针对应bins[0]和bins[1]）。

1
#define unsorted_chunks(M)          (bin_at (M, 1))

再往下，将fastbin中的最大和最小的chunk对应的malloc_chunk指针赋值给maxfb和fb，然后通过do，while循环遍历fastbin中的每个chunk链表，atomic_exchange_acq又是一个CAS操作，该函数取出fb指针，并将原来的chunk链表头指针的值设为0，表示chunk链表空闲了。然后开始进入内层的循环，这里遍历的是每个chunk链表中的每个malloc_chunk指针。
接下来首先去除chunk中的PREV_INUSE和NON_MAIN_ARENA标志，为了获得chunk的大小（size中的最低三位被用来作为标志位，并且fastbin中chunk的标志位IS_MMAPPED默认为0）。然后通过chunk_at_offset和chunksize获得下一个chunk以及其大小，

1
2
3
#define chunk_at_offset(p, s)  ((mchunkptr) (((char *) (p)) + (s)))
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
#define chunksize(p)         ((p)->size & ~(SIZE_BITS))

再往下，如果chunk的前一个chunk没在使用中，就合并该chunk与前一个chunk，主要是重新计算malloc_chunk的指针，并调用unlink将前一个chunk从bins数组中删除，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define unlink(AV, P, BK, FD) {                                            \
    FD = P->fd;                                   \
    BK = P->bk;                                   \
    if (__builtin_expect (FD->bk != P || BK->fd != P, 0))             \
      malloc_printerr (check_action, "corrupted double-linked list", P, AV);  \
    else {                                    \
        FD->bk = BK;                                  \
        BK->fd = FD;                                  \
        if (!in_smallbin_range (P->size)                      \
            && __builtin_expect (P->fd_nextsize != NULL, 0)) {            \
        if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)        \
        || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))    \
          malloc_printerr (check_action,                      \
                   "corrupted double-linked list (not small)",    \
                   P, AV);                        \
            if (FD->fd_nextsize == NULL) {                    \
                if (P->fd_nextsize == P)                      \
                  FD->fd_nextsize = FD->bk_nextsize = FD;             \
                else {                                \
                    FD->fd_nextsize = P->fd_nextsize;                 \
                    FD->bk_nextsize = P->bk_nextsize;                 \
                    P->fd_nextsize->bk_nextsize = FD;                 \
                    P->bk_nextsize->fd_nextsize = FD;                 \
                  }                               \
              } else {                                \
                P->fd_nextsize->bk_nextsize = P->bk_nextsize;             \
                P->bk_nextsize->fd_nextsize = P->fd_nextsize;             \
              }                                   \
          }                                   \
      }                                       \
}

简单来说，该宏定义就是将前一个chunk从两个双线链表中删除，fd和bk指针构成的双向链表存在于smallbin和largebin中，fd_nextsize和bk_nextsize指针构成的双向链表只存在于largebin中。
再往下，如果相邻的下一个chunk不是top chunk，并且下一个chunk不在使用中，就继续合并，否则，就清除下一个chunk的PREV_INUSE，表示该chunk已经空闲了。
然后将刚刚合并完的chunk添加进unsorted_bin中，unsorted_bin也是一个双向链表。
如果合并完的chunk属于smallbin的大小，则需要清除fd_nextsize和bk_nextsize，因为smallbin中的chunk不会使用这两个指针。并且通过setHead保证不会有相邻的两个chunk都空闲，并且通过setFoot设置下一个chunk的prev_size。
如果相邻的下一个chunk是top chunk，则将合并完的chunk继续合并到top chunk中。
至此，malloc_consolidate就分析完了，总结一下，malloc_consolidate就是遍历fastbin中每个chunk链表的每个malloc_chunk指针，合并前一个不在使用中的chunk，如果后一个chunk是top chunk，则直接合并到top chunk中，如果后一个chunk不是top chunk，则合并后一个chunk并添加进unsorted_bin中。

1.9 _int_malloc — unsortedbin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
static void * _int_malloc(mstate av, size_t bytes) {
...
    for (;;) {
        int iters = 0;
        while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)){
            bck = victim->bk;
            if (__builtin_expect(victim->size <= 2 * SIZE_SZ, 0)
                    || __builtin_expect(victim->size > av->system_mem, 0))
                malloc_printerr(check_action, "malloc(): memory corruption",
                        chunk2mem(victim), av);
            size = chunksize(victim);
            if (in_smallbin_range (nb) &&
            bck == unsorted_chunks (av) &&
            victim == av->last_remainder &&
            (unsigned long) (size) > (unsigned long) (nb + MINSIZE)) {
                remainder_size = size - nb;
                remainder = chunk_at_offset(victim, nb);
                unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
                av->last_remainder = remainder;
                remainder->bk = remainder->fd = unsorted_chunks (av);
                if (!in_smallbin_range(remainder_size)) {
                    remainder->fd_nextsize = NULL;
                    remainder->bk_nextsize = NULL;
                }
                set_head(victim,
                        nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
                set_head(remainder, remainder_size | PREV_INUSE);
                set_foot(remainder, remainder_size);
                check_malloced_chunk (av, victim, nb);
                void *p = chunk2mem(victim);
                alloc_perturb(p, bytes);
                return p;
            }
            unsorted_chunks (av)->bk = bck;
            bck->fd = unsorted_chunks (av);
            if (size == nb) {
                set_inuse_bit_at_offset(victim, size);
                if (av != &main_arena)
                    victim->size |= NON_MAIN_ARENA;
                check_malloced_chunk (av, victim, nb);
                void *p = chunk2mem(victim);
                alloc_perturb(p, bytes);
                return p;
            }
            ...
        }
    ...
    }
}

这部分代码的整体意思就是遍历unsortedbin，从中查找是否有符合用户要求大小的chunk并返回。
第一个while循环从尾到头依次取出unsortedbin中的所有chunk，将该chunk对应的前一个chunk保存在bck中，并将大小保存在size中。
如果用户需要分配的内存大小对应的chunk属于smallbin，unsortedbin中只有这一个chunk，并且该chunk属于last remainder chunk且其大小大于用户需要分配内存大小对应的chunk大小加上最小的chunk大小（保证可以拆开成两个chunk），就将该chunk拆开成两个chunk，分别为victim和remainder，进行相应的设置后，将用户需要的victim返回。
如果不能拆开，就从unsortedbin中取出该chunk（victim）。
再下来，如果刚刚从unsortedbin中取出的victim正好是用户需要的大小nb，就设置相应的标志位，直接返回该victim。

继续往下看_int_malloc函数，为了使整个代码结构清晰，这里保留了外层的for循环和while循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
static void * _int_malloc(mstate av, size_t bytes) {
    ...
    for (;;) {
        int iters = 0;
        while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)){
            ...
            if (in_smallbin_range(size)) {
                victim_index = smallbin_index(size);
                bck = bin_at (av, victim_index);
                fwd = bck->fd;
            } else {
                victim_index = largebin_index(size);
                bck = bin_at (av, victim_index);
                fwd = bck->fd;
                if (fwd != bck) {
                    size |= PREV_INUSE;
                    assert((bck->bk->size & NON_MAIN_ARENA) == 0);
                    if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) {
                        fwd = bck;
                        bck = bck->bk;
                        victim->fd_nextsize = fwd->fd;
                        victim->bk_nextsize = fwd->fd->bk_nextsize;
                        fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize =
                                victim;
                    } else {
                        assert((fwd->size & NON_MAIN_ARENA) == 0);
                        while ((unsigned long) size < fwd->size) {
                            fwd = fwd->fd_nextsize;
                            assert((fwd->size & NON_MAIN_ARENA) == 0);
                        }
                        if ((unsigned long) size == (unsigned long) fwd->size)
                            fwd = fwd->fd;
                        else {
                            victim->fd_nextsize = fwd;
                            victim->bk_nextsize = fwd->bk_nextsize;
                            fwd->bk_nextsize = victim;
                            victim->bk_nextsize->fd_nextsize = victim;
                        }
                        bck = fwd->bk;
                    }
                } else
                    victim->fd_nextsize = victim->bk_nextsize = victim;
            }
            mark_bin(av, victim_index);
            victim->bk = bck;
            victim->fd = fwd;
            fwd->bk = victim;
            bck->fd = victim;
    #define MAX_ITERS       10000
            if (++iters >= MAX_ITERS)
                break;
        }
    ...
    }
}

这部分代码的整体意思是如果从unsortedbin中取出的chunk不符合用户要求的大小，就将该chunk合并到smallbin或者largebin中。
首先如果取出的chunk（victim）属于smallbin，就通过smallbin_index计算需要插入的位置victim_index，然后获取smallbin中对应位置的链表头指针保存在bck中，最后直接插入到smallbin中，由于smallbin中的chunk不使用fd_nextsize和bk_nextsize指针，插入操作只需要更新bk和fd指针，具体的插入操作在后面。这里需解释一下，fd_nextsize指针指向的是chunk双向链表中下一个大小不同的chunk，bk_nextsize指向的是chunk双向链表中前一个大小不同的chunk。
如果取出的chunk（victim）属于largebin，通过largebin_index计算需要插入的位置victim_index，然后获取largebin链表头指针保存在bck中。
如果fwd等于bck，即bck->fd=bck，则表示largebin中对应位置上的chunk双向链表为空，直接进入后面的else部分中，代码victim->fd_nextsize = victim->bk_nextsize = victim表示插入到largebin中的victim是唯一的chunk，因此其fd_nextsize和bk_nextsize指针都指向自己。
如果fwd不等于bck，对应的chunk双向链表存在空闲chunk，这时就要在该链表中找到合适的位置插入了。因为largebin中的chunk链表是按照chunk大小从大到小排序的，如果victim的size小于bck->bk->size即最后一个chunk的大小，则表示即将插入victim的大小在largebin的chunk双向链表中是最小的，因此要把victim插入到该链表的最后。在这种情况下，经过操作后的结果如下所示（因为我手边的画图软件有限，这里就用符号“|”隔出数组，然后从代码中摘除核心的fd_nextsize和bk_nextsize指针的修改操作，对照这两个指针的意思，很容易看懂），

1
2
3
4
5
| fwd（头指针） | fwd->fd | ... | bck | victim（插入到末尾） |
fwd->fd->bk_nextsize = victim
victim->bk_nextsize->fd_nextsize = victim
victim->fd_nextsize = fwd->fd
victim->bk_nextsize = fwd->fd->bk_nextsize

如果要插入的victim的size不是最小的，就要通过一个while循环遍历找到合适的位置，这里是从双向链表头bck->fd开始遍历，利用fd_nextsize加快遍历的速度，找到第一个size>=fwd->size的chunk。如果size=fwd->size，就只是改变victim以及前后相应chunk的bk、fd指针就行。这里要特别注意，先做一个假设，假设chunk双向链表中A、B、C是三个不同大小的chunk集合，A集合有A0=A1=…，B集合有B0=B1=…，C集合有C0=C1=…，然后构造chunk链表，
| A0 | A1 | A2 | B0 | B1 | B2 | C0 | C1 | C2 |
特别注意，在ptmalloc中，只有A0、B0、C0可以配置fd_nextsize和bk_nextsize指针，其他位置是不用配置这两个指针的。因此相同大小的chunk只有最低地址的chunk会设置fd_nextsize和bk_nextsize指针。根据这个假设，很容易知道当两个size相等时，为什么要执行fwd = fwd->fd，因为要保证插入victim的位置是相同大小的chunk的右边，即高地址的地方。插入后的链表如下，

1
...| bck | victim | fwd |...

链表中所有chunk的fd_nextsize 和bk_nextsize指针不变。
再往下，如果size不相等，则直接插入在fwd的左边，这样也能保证所有的fd_nextsize和bk_nextsize指针设置在相同chunk大小的最地地址处（最左边）。插入后的链表如下，

1
2
3
4
5
...| bck | victim | fwd |...
victim->fd_nextsize = fwd
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim
fwd->bk_nextsize->fd_nextsize = victim

再往下，mark_bin用来标识malloc_state中的binmap，标识相应位置的chunk空闲。然后就更改fd、bk指针，插入到双向链表中，这个插入操作同时适用于smallbin和largebin，因此放在这里。最后如果在unsortedbin中处理了超过10000个chunk，就直接退出循环，这里保证不会因为unsortedbin中chunk太多，处理的时间太长了。
在这部分代码中，有个size |= PREV_INUSE是暂时让我比较费解的地方，经过分析后，暂时认为size |= PREV_INUSE是没必要的，虽然不会产生错误，也不会影响largebin中的排序，并且注释说这行代码能加速排序，但没看出能加速的地方，经过分析这里反而会多出一个无效的指针赋值，希望往后看代码时能解决这里的问题，或者希望有人能解答这行代码的具体作用。

1.10 _int_malloc — largebin

回到_int_malloc函数中，继续往下看，为了使整个代码结构清晰，这里继续保留了外层的for循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
static void * _int_malloc(mstate av, size_t bytes) {
    ...
    for (;;) {
        ...
        if (!in_smallbin_range(nb)) {
            bin = bin_at (av, idx);
            if ((victim = first(bin)) != bin
                    && (unsigned long) (victim->size) >= (unsigned long) (nb)) {
                victim = victim->bk_nextsize;
                while (((unsigned long) (size = chunksize(victim))
                        < (unsigned long) (nb)))
                    victim = victim->bk_nextsize;
                if (victim != last(bin) && victim->size == victim->fd->size)
                    victim = victim->fd;
                remainder_size = size - nb;
                unlink(av, victim, bck, fwd);
                if (remainder_size < MINSIZE) {
                    set_inuse_bit_at_offset(victim, size);
                    if (av != &main_arena)
                        victim->size |= NON_MAIN_ARENA;
                }
                else {
                    remainder = chunk_at_offset(victim, nb);
                    bck = unsorted_chunks (av);
                    fwd = bck->fd;
                    if (__glibc_unlikely(fwd->bk != bck)) {
                        errstr = "malloc(): corrupted unsorted chunks";
                        goto errout;
                    }
                    remainder->bk = bck;
                    remainder->fd = fwd;
                    bck->fd = remainder;
                    fwd->bk = remainder;
                    if (!in_smallbin_range(remainder_size)) {
                        remainder->fd_nextsize = NULL;
                        remainder->bk_nextsize = NULL;
                    }
                    set_head(victim,
                            nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
                    set_head(remainder, remainder_size | PREV_INUSE);
                    set_foot(remainder, remainder_size);
                }
                check_malloced_chunk (av, victim, nb);
                void *p = chunk2mem(victim);
                alloc_perturb(p, bytes);
                return p;
            }
        }
        ...
    }
}

这部分代码的整体意思就是要尝试从largebin中取出对应的chunk了。
这里的idx是在前面（上一章分析的_int_malloc函数前面一部分中）根据宏largebin_index计算的。接下来就要根据idx获得largebin中的双向链表头指针bin，然后从bin->bk开始从尾到头（根据chunk大小从小到大）遍历整个双向链表，找到第一个大于用户需要分配的chunk大小nb的chunk指针victim。
找到victim后，需要将其拆开成两部分，第一部分是要返回给用户的chunk，第二部分分为两种情况，如果其大小小于MINSIZE，则不能构成一个最小chunk，这种情况下就将拆开前的整个victim返回给用户；如果大于MINSIZE，就将拆开后的第二部分remainder插入到unsortedbin中，然后把第一部分victim返回给用户。

继续往下看_int_malloc函数，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
static void * _int_malloc(mstate av, size_t bytes) {
    ...
    for (;;) {
        ...
        ++idx;
        bin = bin_at (av, idx);
        block = idx2block(idx);
        map = av->binmap[block];
        bit = idx2bit(idx);
        for (;;) {
            if (bit > map || bit == 0) {
                do {
                    if (++block >= BINMAPSIZE) /* out of bins */
                        goto use_top;
                } while ((map = av->binmap[block]) == 0);
                bin = bin_at (av, (block << BINMAPSHIFT));
                bit = 1;
            }
            while ((bit & map) == 0) {
                bin = next_bin(bin);
                bit <<= 1;
                assert(bit != 0);
            }
            victim = last(bin);
            if (victim == bin) {
                av->binmap[block] = map &= ~bit;
                bin = next_bin(bin);
                bit <<= 1;
            }
            else {
                size = chunksize(victim);
                assert((unsigned long ) (size) >= (unsigned long ) (nb));
                remainder_size = size - nb;
                unlink(av, victim, bck, fwd);
                if (remainder_size < MINSIZE) {
                    set_inuse_bit_at_offset(victim, size);
                    if (av != &main_arena)
                        victim->size |= NON_MAIN_ARENA;
                }
                else {
                    remainder = chunk_at_offset(victim, nb);
                    bck = unsorted_chunks (av);
                    fwd = bck->fd;
                    if (__glibc_unlikely(fwd->bk != bck)) {
                        errstr = "malloc(): corrupted unsorted chunks 2";
                        goto errout;
                    }
                    remainder->bk = bck;
                    remainder->fd = fwd;
                    bck->fd = remainder;
                    fwd->bk = remainder;
                    if (in_smallbin_range(nb))
                        av->last_remainder = remainder;
                    if (!in_smallbin_range(remainder_size)) {
                        remainder->fd_nextsize = NULL;
                        remainder->bk_nextsize = NULL;
                    }
                    set_head(victim,
                            nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
                    set_head(remainder, remainder_size | PREV_INUSE);
                    set_foot(remainder, remainder_size);
                }check_malloced_chunk (av, victim, nb);
                void *p = chunk2mem(victim);
                alloc_perturb(p, bytes);
                return p;
            }
        }
        ...
    }
}

这一部分的整体意思是，前面在largebin中寻找特定大小的空闲chunk，如果没找到，这里就要遍历largebin中的其他更大的chunk双向链表，继续寻找。
开头的++idx就表示，这里要从largebin中下一个更大的chunk双向链表开始遍历。ptmalloc中用一个bit表示malloc_state的bins数组中对应的位置上是否有空闲chunk，bit为1表示有，为0则没有。ptmalloc通过4个block（一个block 4字节）一共128个bit管理bins数组。因此，代码中计算的block表示对应的idx属于哪一个block，map就表是block对应的bit组成的二进制数字。
接下来进入for循环，如果bit > map，表示该map对应的整个block里都没有大于bit位置的空闲的chunk，因此就要找下一个block。因为后面的block只要不等于0，就肯定有空闲chunk，并且其大小大于bit位置对应的chunk，下面就根据block，取出block对应的第一个双向链表的头指针。这里也可以看出，设置map和block也是为了加快查找的速度。如果遍历完所有block都没有空闲chunk，这时只能从top chunk里分配chunk了，因此跳转到use_top。
如果有空闲chunk，接下来就通过一个while循环依次比较找出到底在哪个双向链表里存在空闲chunk，最后获得空闲chunk所在的双向链表的头指针bin和位置bit。
接下来，如果找到的双向链表又为空，则继续前面的遍历，找到空闲chunk所在的双向链表的头指针bin和位置bit。如果找到的双向链表不为空，就和上面一部分再largebin中找到空闲chunk的操作一样了，这里就不继续分析了。

1.11 _int_malloc — topchunk

继续往下看_int_malloc，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
static void * _int_malloc(mstate av, size_t bytes) {
    ...
    for (;;) {
        ...
        use_top:
        victim = av->top;
        size = chunksize(victim);
        if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE )) {
            remainder_size = size - nb;
            remainder = chunk_at_offset(victim, nb);
            av->top = remainder;
            set_head(victim,
                    nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
            set_head(remainder, remainder_size | PREV_INUSE);
            check_malloced_chunk (av, victim, nb);
            void *p = chunk2mem(victim);
            alloc_perturb(p, bytes);
            return p;
        }
        else if (have_fastchunks(av)) {
            malloc_consolidate(av);
            if (in_smallbin_range(nb))
                idx = smallbin_index(nb);
            else
                idx = largebin_index(nb);
        }
        else {
            void *p = sysmalloc(nb, av);
            if (p != NULL)
                alloc_perturb(p, bytes);
            return p;
        }
    }
}

这里就是_int_malloc的最后一部分了，这部分代码的整体意思分为三部分，首先从top chunk中尝试分配内存；如果失败，就检查fastbin中是否有空闲内存了（其他线程此时可能将释放的chunk放入fastbin中了），如果不空闲，就合并fastbin中的空闲chunk并放入smallbin或者largebin中，然后会回到_int_malloc函数中最前面的for循环，重新开始查找空闲chunk；如果连fastbin中都没有空闲内存了，这时只能通过sysmalloc从系统分配内存了，该函数前面几章里已经分析过了一部分了，下一章会再次进入这个函数进行分析。这部分代码很简单，关键函数前面几章都碰到过了，这里就不详细分析了。

2. 总结

下面简单总结一遍_int_malloc函数的整体思路。
第一步：如果进程没有关联的分配区，就通过sysmalloc从操作系统分配内存。
第二步：从fastbin查找对应大小的chunk并返回，如果失败进入第三步。
第三步：从smallbin查找对应大小的chunk并返回，或者将fastbin中的空闲chunk合并放入unsortedbin中，如果失败进入第四步。
第四步：遍历unsortedbin，从unsortedbin中查找对应大小的chunk并返回，根据大小将unsortedbin中的空闲chunk插入smallbin或者largebin中。进入第五步。
第五步：从largebin指定位置查找对应大小的chunk并返回，如果失败进入第六步。
第六步：从largebin中大于指定位置的双向链表中查找对应大小的chunk并返回，如果失败进入第七步。
第七步：从topchunk中分配对应大小的chunk并返回，topchunk中没有足够的空间，就查找fastbin中是否有空闲chunk，如果有，就合并fastbin中的chunk并加入到unsortedbin中，然后跳回第四步。如果fastbin中没有空闲chunk，就通过sysmalloc从操作系统分配内存。