本文以初学者的角色对glibc的malloc进行简单的解析，从而了解malloc的简要知识，根据此文章，可以知道什么是fastbin，smallbin，largebin等等。

一、malloc时的内存布局

我们需要知道的是，通过glibc的malloc申请的内存，其返回的指针地址只是整个内存的chunk的userdata，其整体布局应该如下：

根据上图，我们可以知道如下信息：

userdata是malloc返回的指针
malloc申请的内存，包含多个chunk
多个chunk上下相连
每个chunk都包含一个prev_size
prev_size本身存放了上一个未使用的chunk大小
prev_size的下一个字节存放的是本chunk的size和AMP标志
其中A标志代表此内存是否来自main arena/main heap
其中M标志代表此内存是否来自mmap syscall
其中P标志代表此内存的prev chunk是否正在使用，如果正在使用，则prev_size的值无效根据此，我们知道了malloc时的内存布局情况，下面看看free时，指针的布局情况

二、free时的内存布局

我们需要知道的是，通过glibc的free释放的内存，它不会直接返还给操作系统从而让其他程序使用，而是简单的标记这块地址为reused，只有程序的内存到达一定的阈值情况下，或者程序申请内存时当前chunk不足以满足的情况下，触发glibc的consolidate。如下是free时的指针布局情况，如下：

根据上图，结合https://sourceware.org/glibc/wiki/MallocInternals，我们可以知道如下信息：

M标志位和free chunk无关，因为mmap的内存通过munmap来实现，不是通过free
free chunk维护了一个fwd/bck指针，这里fwd是forward，bck是backup，用于构造双向循环链表或单链表
如果P标志未置位，则代表free chunk的上一个chunk是unused的，也就是free的，那么可以向上合并这两个chunk
同理，如果下一个chunk是free chunk，那么也会被下一个chunk合并
我们知道所有的chunk来自于top chunk，所以如何free chunk和top chunk相邻，则合并到top chunk
如果tcache有空闲就，那么会将此free chunk放在tcache中
判断此free chunk大小，放入对应的bin中，例如（fastbin，smallbin，largebin）根据此，我们可以知道系统中的malloc和free的基本行为如下：

malloc分配了一个地址给应用使用，实际还包含了一个chunk struct
free并没有释放内存给系统，而是等到consolidate时尝试合并和释放

三、各类bin的情况

根据上面的信息，我们提到了各类的bin，当我们在malloc和free时，其实对应的是每个chunk，而每个chunk都根据chunk_size代表一个bin类型。注意，这里的chunk_size是包含chunk结构体的size大小，而不是给用户的内存地址和偏移下的大小。

对于常规bin，例如smallbin，largebin等一共是126个，如下：

对于fastbin，一个10个，所以总共有136个bin，如下：

这里我们谈论的bin的个数其实是bin的数组，实际上不同的bin数组内部是用不同的链表实现。例如fastbin使用单链表，其他bin使用双向循环链表

因为fastbin是单链表，所以结构体中的bck指针是没用的，只用到了fwd指针，如下：

对于其他的bin，它使用了双向循环链表，如下：

这里比较清晰的是，在free chunk中，fwd和bck指针都用到了。

除了各种bin的链表管理方式不同之外，我们还需要知道区分其bin的方式，通过内存大小，如下：


32 <= fastbin_size <= 128
128 < smallbin_size <= 1024
1024 < largebin_size <= 128*1024

注意，根据上面提到的，这个chunk size是包括chunk struct的size，而不是用户malloc的size。

至此，我们可以知道，通过malloc和free管理的内存，分为多个bin，有fastbin，smallbin，largebin等等。下面通过代码的方式来验证一下

四、测试程序

我们想要写一个测试程序，用来验证我们上述情况，首先，我们需要拿到chunk struct，这里以glibc 2.31为例，其结构体如下


struct malloc_chunk {
  size_t mchunk_prev_size;  /* Size of previous chunk (if free).  */
  size_t mchunk_size;       /* Size in bytes, including overhead. */
 
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
 
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

根据上面我们可以看到，在64位系统上malloc_chunk的大小是48（6*8）

为了解析chunk，我编写了inpect_chunk函数，如下


static void inspect_chunk(void *ptr)
{
    struct malloc_chunk *chunk = (struct malloc_chunk *)((char *)ptr - 2*sizeof(size_t));
    size_t chunk_size = chunk->mchunk_size & ~0x7;  // Mask out the metadata bits
    int prev_inuse = chunk->mchunk_size & 1;
    int is_mmapped = chunk->mchunk_size & 2;
    int main_arena = chunk->mchunk_size & 4;
 
    printf("Chunk address=%p. ", (void *)chunk);
    printf("size=%zu. AMP=%#lx: \n\t", chunk_size, chunk->mchunk_size & 0x7);
    printf("main-arena=%s. ", main_arena ? "[No]" : "[Yes]");
    printf("with_mmap=%s. ", is_mmapped ? "[Yes]" : "[No]");
    printf("prev_in_use=%s. ", prev_inuse ? "[Yes]" : "[No]");
 
    if (chunk_size <= 128) {
        printf("is fast bin.\n");
    } else if (chunk_size <= 1024) {
        printf("is small bin.\n");
    } else {
        printf("is large bin.\n");
    }
}

我对用户malloc的指针向前推进了16字节，此时我们得到一个chunk指针，它的类型是malloc_chunk。然后我用chunk来进行判断

为了进行一系列的bin测试，我编写了测试函数如下：


void main()
{
        malloc_stats();
        int* a = malloc(sizeof(int));
 
        inspect_chunk(a);
        free(a);
 
        a = malloc(0);
        inspect_chunk(a);
        free(a);
 
        a = malloc(128-8);
        inspect_chunk(a);
        free(a);
 
        a = malloc(128-7);
        inspect_chunk(a);
        free(a);
 
        a = malloc(1024-8);
        inspect_chunk(a);
        free(a);
 
        a = malloc(1024-7);
        inspect_chunk(a);
        free(a);
 
        a = malloc(128*1024-23);
        inspect_chunk(a);
        free(a);
 
        printf("%ld <= fastbin_size <= %ld\n", MIN_CHUNK_SIZE, DEFAULT_MXFAST);
        printf("%ld < smallbin_size <= %ld\n", DEFAULT_MXFAST, MIN_LARGE_SIZE);
        printf("%ld < largebin_size <= 128*1024 \n", MIN_LARGE_SIZE);
        malloc_stats();
}

我分别malloc了0，128，1024，128*1024等相关字节

为了让这个代码正常运行，需要包含malloc.h头文件和必要的宏定义，宏定义需要从glibc源码中摘抄如下：


#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#include <stddef.h>
 
# define INTERNAL_SIZE_T size_t
#define SIZE_SZ (sizeof (INTERNAL_SIZE_T))
 
#define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \
                          ? __alignof__ (long double) : 2 * SIZE_SZ)
 
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
 
#define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))
#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)

至此，我们可以轻松的运行这个程序，如下：


gcc test_malloc_chunk.c -o test_malloc_chunk && ./test_malloc_chunk

从而得到输出如下：


Arena 0:
system bytes = 135168
in use bytes = 3680
Total (incl. mmap):
system bytes = 135168
in use bytes = 3680
max mmap regions = 0
max mmap bytes = 0
---------------------------------------------
Chunk address=0x559f9f0270. size=32. AMP=0x1:
 main-arena=[Yes]. with_mmap=[No]. prev_in_use=[Yes]. is fast bin.
Chunk address=0x559f9f0270. size=32. AMP=0x1:
 main-arena=[Yes]. with_mmap=[No]. prev_in_use=[Yes]. is fast bin.
Chunk address=0x559f9f0290. size=128. AMP=0x1:
 main-arena=[Yes]. with_mmap=[No]. prev_in_use=[Yes]. is fast bin.
Chunk address=0x559f9f0310. size=144. AMP=0x1:
 main-arena=[Yes]. with_mmap=[No]. prev_in_use=[Yes]. is small bin.
Chunk address=0x559f9f03a0. size=1024. AMP=0x1:
 main-arena=[Yes]. with_mmap=[No]. prev_in_use=[Yes]. is small bin.
Chunk address=0x559f9f07a0. size=1040. AMP=0x1:
 main-arena=[Yes]. with_mmap=[No]. prev_in_use=[Yes]. is large bin.
Chunk address=0x7f96c52000. size=135168. AMP=0x2:
 main-arena=[Yes]. with_mmap=[Yes]. prev_in_use=[No]. is large bin.
32 <= fastbin_size <= 128
128 < smallbin_size <= 1024
1024 < largebin_size <= 128*1024
---------------------------------------------
Arena 0:
system bytes = 135168
in use bytes = 7088
Total (incl. mmap):
system bytes = 135168
in use bytes = 7088
max mmap regions = 1
max mmap bytes = 135168

注意，这里我使用了glibc的malloc信息函数malloc_stats，它能够打印当前的malloc信息，我解析如下：


Arena 0: //Arena ID. There is only one thread.
system bytes = 135168 //Dynamic memory obtained by the thread from the OS. 
in use bytes = 7088 //Dynamic memory used by the thread. 
Total (incl. mmap): //Total usage of the dynamic memory, that is, the accumulated dynamic memory used by each thread. 
system bytes = 135168 //Dynamic memory obtained by the process from the OS. 
in use bytes = 7088 //Dynamic memory used by the process. 
max mmap regions = 1 //Maximum number of mmap regions 
max mmap bytes = 135168 //Size of the memory corresponding to mmap regions

这里值得注意的是


1. 为什么in use bytes差8字节，这8字节在哪里？

这里7088 - 3680 = 2408，但实际上 1024+1040+144+128+32+32=2400。多了一个8字节

这是因为最开始的chunk，我们需要一个空的prev_size，这个prev_size的类型是size_t，也就是8。


2.  为什么是135168，系统字节是135168，mmap字节是135168

这里我们知道一个常识是，当内存超过128k时，系统通过mmap系统调用来分配内存，这时候是128*1024=131072

但是管理mmap这么多内存需要一个结构体，这样同时知道分配内存的最小单位是4k，那么4k为4*1024=4096

那么131072+4096=135168。

另一方面，我们在使用glibc程序时，默认程序启动时，glibc的内存管理提供你128k内存供你使用，这里还需要附带1个4k页。然后程序的malloc行为实际上是通过top chunk来进行分配即可。

所以一个程序运行时，默认glibc管理程序会给这个程序提供135168字节的system bytes

目录

一、malloc时的内存布局

二、free时的内存布局

三、各类bin的情况

四、测试程序