malloc/free的原理与实现

Chunk
C标准库在管理分配出去的heap时的基本单位是chunk，chunk只是一个逻辑概念，它的数据结构如下：

struct malloc_chunk {
   size_t prev_size;                           /* Size of previous chunk (if free). */
   size_t 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;
};

如果一个chunk是free的状态，那么它的fd和bk就构成一个双链表，记录着那些已经被用户free了内存，这样以后就可以从这里直接分配或者合并成为大的空闲块以后再分配。如果一个chunk已经被alloc了，那么此时从size之后就是用户的数据，也就是说fd、bk等没有意义，这个从注释中不难看出。

当一个chunk被分配出去时，size记录了这个chunk中实际分配给用户程序的内存大小，也就是我们调用malloc时的那个参数值，而prev_size记录的是与当前chunk相邻的上一个chunk的大小。这样设计的原因是可以快速地定位/合并相邻的chunk。例如，如果当前chunk地址为char *p，那么上/下一个chunk的地址分别就是p-p->prev_size和p+p->size。简单分析下下面这两个宏就一目了然了：
(1)从chunk得到用户指针(这里SIZE_SZ即sizeof(size_t))
     #define chunk2mem(p) ((void_t*)((char*)(p) + 2*SIZE_SZ))
(2)从用户指针得到chunk地址
     #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))

在分配内存时，chunk的对其单位是8Byte，这样size的低3位就都是0，那么就可以作为其他用途。在glibc中有两个定义：
    #define PREV_INUSE 0x1
    #define IS_MMAPPED 0x2
这里PREV_INUSE记录了上一个chunk是否被使用(如果被分配则为1)，而IS_MMAPPED标识当前chunk是否是通过mmap分配得到。下面这些宏可以加深我们对chunk的理解：
//获取当前chunk(p)的下一个chunk
#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~PREV_INUSE) ))
//获取当前chunk(p)的上一个chunk
#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
//判断当前chunk(p)是否被使用，注意：p的inuse位信息保存在下一个相邻chunk的size中
#define inuse(p) ((((mchunkptr)(((char*)(p))+((p)->size & ~PREV_INUSE)))->size) & PREV_INUSE)
//将当前chunk(p)设置为被使用，也即设置下一个相邻chunk中size的最低位为1
#define set_inuse(p) ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size |= PREV_INUSE

malloc数据结构
这个数据结构记录了系统当前分配内存的状态，默认情况下，当分配内存小于64B时通过fastbin分配，它是一个caching allocator，也就是说一种memory pool。当分配内存大于512B时，系统按照best-fit算法分配，也就是可以满足需求的最小size的chunk。介于二者之间的情况比较复杂。
struct malloc_state {
/* Serialize access. */
mutex_t mutex;
/* Flags (formerly in max_fast). */
int flags;
   /* Fastbins */
mchunkptr        fastbins[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr        top;
/* The remainder from the most recent split of a small request */
mchunkptr        last_remainder;
/* Normal bins packed as described above */
mchunkptr        bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int     binmap[BINMAPSIZE];
/* Linked list */
struct malloc_state *next;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};

malloc实现(void *malloc(size_t size))
该调用在内部实现为_int_malloc(mstate av, size_t bytes)。主要步骤如下：

1、确定内部分配内存大小，它是用宏request2size计算得到。：
    #define request2size(req)   (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? MINSIZE : ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
malloc中分配内存的最小值为MINSIZE，它的定义如下：
    #define MINSIZE   (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
    #define MIN_CHUNK_SIZE               (offsetof(struct malloc_chunk, fd_nextsize))
    #define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)
    #define MALLOC_ALIGNMENT        (2 * SIZE_SZ)
    #define SIZE_SZ                                (sizeof(INTERNAL_SIZE_T))
    #define INTERNAL_SIZE_T                size_t
综合下来，就是说在我们平常的32位机器上malloc最小分配内存为16B，为什么会这样呢？(下面是我的理解)因为每块分配给用户的内存都是使用chunk来表示的，当chunk分配出去时，prev_size和size表示相邻上一个chunk和当前chunk的大小，而从fd开始是用户内存。而加入chunk没有分配出去，例如被free，那么此时它会通过fd和bk链接成一个双链表，于是，我们至少要表征chunk的前四个数据成员的语义，这就至少需要16B。BTW，从这里我们不难看到加入零散地分配小内存，其结果必然是大大降低有效内存使用量。

2、如果分配内存很小(<64B)，那么首先尝试从fastbin中分配。
if ((unsigned long)(nb) <= (unsigned long)(get_max_fast ())) {
    long int idx = fastbin_index(nb);
    fb = &(av->fastbins[idx]);
    if ( (victim = *fb) != 0) {
      if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
        malloc_printerr (check_action, "malloc(): memory corruption (fast)",
    chunk2mem (victim));
      *fb = victim->fd;
      check_remalloced_chunk(av, victim, nb);
      void *p = chunk2mem(victim);
      if (__builtin_expect (perturb_byte, 0))
          alloc_perturb (p, bytes);
      return p;
    }
}
fastbin_index(nb):
       这是一个宏，定义为#define fastbin_index(sz)   ((((unsigned int)(sz)) >> 3) - 2)。观察malloc_state数据结构，它有一个fastbin的指针数组，每个数组成员分配是一个单链表的表头，可见fastbin[i]专门用于分配大小为16+8i的内存块。
*fb = victim->fd:
       当执行到这一行时，fastbin[idx]肯定不为空，也就是说当前内存分配可以直接从fastbin中满足，那么下面自然是从单链表中取下victim这个chunk，而这行赋值语句正是完成这个任务。这里相当于fastbin[idx]这个指针指向了victim这个chunk的后继(victim->fd)，也就是说将victim从链表中移除。
void *p = chunk2mem(victim)
       前文中已经分析过这个宏了，它返回的是chunk内用户内存的首地址。

3、如果分配内存大于64B，但是小于512B，那么仍属于小块内存请求，从smallbin中分配
if (in_smallbin_range(nb)) {
    idx = smallbin_index(nb);
    bin = bin_at(av,idx);
    if ( (victim = last(bin)) != bin) {
      if (victim == 0) /* initialization check */
        malloc_consolidate(av);
      else {
        bck = victim->bk;
        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);
        if (__builtin_expect (perturb_byte, 0))
             alloc_perturb (p, bytes);
         return p;
      }
    }
}
smallbin_index(nb):
它也是一个宏，它定义等价于 #define smallbin_index(sz) (((unsigned)(sz)) >> 3))。这里因为系统将512B大小以下的闲置内存块都组织为双链表