堆概述

malloc(size_t n)

n为0时，返回当前系统允许的堆的最小内存块（32位为16字节，64为为24或32字节）
n为负数时,在大多数系统中，size_t是一个无符号类型，所以程序会尝试申请很大一块内存空间，而这往往会失败，因为没这么多内存能分配

free(void* p)

p为空时，不执行任何操作。
p已经被释放后，再次进行释放会产生不好的效果，即double free
除非禁用（使用mallopt），释放非常大的空间时将在可能的情况下自动触发操作，将未使用的内存归还给系统，从而减小程序的占用空间

堆相关数据结构

malloc_chunk

glibc中的代码定义

struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_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;
};

prev_size用来存储物理地址相邻的上一个chunk的大小（如果上一个chunk为空闲的话），上一个chunk也可以使用prev_size所占空间。
size用来存储当前chunk的大小，大小必须为2 * SIZE_SZ的整数倍，如果申请的大小不是2 * SIZE_SZ的整数倍，则会被转换成满足大小的最小的2 * SIZE_SZ的整数倍。32位下，SIZE_SZ大小为4；64位下，SIZE_SZ大小为8。
- 其在末尾有三个字段|A|M|P|
  - A：NON_MAIN_ARENA，记录当前chunk是否由主线程分配，0为不是，1为是。
  - M：IS_MMAPPED，记录当前chunk是否由mmap分配，0为不是，1为是。
  - P：PREV_INUSE，记录前一个chunk是否被分配，0为不是，1为是。
  一般来说，堆中第一个分配的chunk的P位都会被设置为1，以便于防止访问前面的非法内存。
  
  当一个chunk的P位为0时，我们可以通过prev_size字段来获取前一个chunk的大小以及地址。
  
  同时便于空闲chunk间的合并。
fd指向下一个（非物理相邻）的空闲chunk。
bk指向前一个（非物理相邻）的空闲chunk。

注意：

chunk属于被分配状态时，从fd字段为用户数据。而空闲时被加到对应的空闲管理链表(unsortedbin,fastbin,smallbin等)。

通过fd和bk可以便于空闲chunk的管理，将chunk放到对应的空闲chunk管理链表中。

fd_nextsize指向下一个与当前chunk大小不同的第一个空闲块，不包含bin的头指针。
bk_nextsize指向前一个与当前chunk大小不同的第一个空闲块，不包含bin的头指针。

注意：

这两个字段只有在chunk空闲时使用，不过其用于较大的chunk(large chunk)。

一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。

一个被分配的chunk示例大概是这样：

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of previous chunk, if unallocated (P clear)  |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of chunk, in bytes                     |A|M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             User data starts here...                          .
	    .                                                               .
	    .             (malloc_usable_size() bytes)                      .
	    .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             (size of chunk, but used for application data)    |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of next chunk, in bytes                |A|0|1|
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

一个被释放的chunk会被存到双向循环链表中，大概是这样

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of previous chunk, if unallocated (P clear)  |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                     |A|0|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Forward pointer to next chunk in list             |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Back pointer to previous chunk in list            |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Unused space (may be 0 bytes long)                .
	    .                                                               .
	    .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of next chunk, in bytes                |A|0|0|
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

bin

ptmalloc使用分箱式方法对空闲chunk进行管理，其根据chunk的大小以及使用状态将空闲chunk分为这四类

fast bins
small bins
large bins
unsorted bins

对于small bins large bins unsorted bins，ptmalloc将他们维护在同一个数组中。这些bin对应的数据结构在malloc_state结构体下

#define NBINS 128
struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

  /* Fastbins */
  mfastbinptr fastbinsY[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;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

堆处理相关宏和函数

check_remalloced_chunk

chunk2mem

fastbin_index

smallbin_index

bin_at

malloc_consolidate

mark_bin

malloc流程分析

malloc前的准备工作

调用malloc函数时，会先进入__libc_malloc函数

该函数会首先检查__malloc_hook是否存在，若存在则先执行__malloc_hook中的函数指针

void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));

否则直接执行下面的代码

1 2	arena_get (ar_ptr, bytes); victim = _int_malloc (ar_ptr, bytes);

对于arena_get函数，其作用是为本次 malloc 分配选择一个合适的内存 arena，并获取对该 arena 的独占访问权（锁）。

_int_malloc

malloc功能实际上是由_int_malloc函数所实现

一些检查

在_int_malloc的开始，会先检查传入的字节大小

1	checked_request2size (bytes, nb);

该函数的定义如下

#define REQUEST_OUT_OF_RANGE(req)                                 \
  ((unsigned long) (req) >=						      \
   (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))

/* pad request bytes into a usable size -- internal version */

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

/*  Same, except also perform argument check */

#define checked_request2size(req, sz)                             \
  if (REQUEST_OUT_OF_RANGE (req)) {					      \
      __set_errno (ENOMEM);						      \
      return 0;								      \
    }									      \
  (sz) = request2size (req);

先检查申请大小是否大于系统最大支持申请大小，符合大小范围内的话，把申请的字节数与八字节对齐

一切检查完和处理完后，开始检查arena

/* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
     mmap.  */
if (__glibc_unlikely (av == NULL))
{
    void *p = sysmalloc (nb, av);
    if (p != NULL)
        alloc_perturb (p, bytes);
    return p;
}

如果没有可用的堆内存，则使用sysmalloc进行申请

sysmalloc-申请堆空间

sysmalloc会使用mmap申请一块堆内存

1 2	// malloc.c #L2324 mm = (char *) (MMAP (0, size, PROT_READ \| PROT_WRITE, 0));

除了申请新的堆空间外，sysmalloc还可以拓展原有堆空间，对于这一块逻辑我们后续再分析

从fastbin中分配内存

fastbin是_int_malloc分配内存最先考虑的bin

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;
    }
}

首先检查申请大小是否符合fastbin大小

符合的话，则获取申请的chunk在fastbin中的索引和对应头指针，接着如果fastbinY[idx]中存在符合要求的chunk即返回给用户，没有则开始检查其他的bin中是否有符合要求的chunk

要注意的是，这里会检查申请后chunk在fastbin中的idx是否等于原来的idx，防止double free等利用手法

从smallbin中分配内存

如果fastbin中没有符合要求的chunk但是大小在smallbin范围的话，则开始检查smallbin中的chunk

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;
            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;
        }
    }
}

首先获取目标chunk大小在smallbin中的idx和smallbin的头结点

接着将victim赋值为头结点的bk指针，检查bk指针是否为bin本身

由于smallbin的数据结构为双向链表，所以头节点的bk指针也就代表着该链表中的最后一个结点，所以这一行也就是检查smallbin是否为空。

如果smallbin为空，则利用malloc_consolidate函数清理内存碎片，将合并后的chunk放到unsorted bin中

如果smallbin不为空，则将尾结点返回给用户。

注意，这里会检查尾结点的fd指针是否指向的是自身

至此，如果fastbin和smallbin都无法满足需求的话，则开始检查largebin中的chunk是否有符合的

else
{
    idx = largebin_index (nb);
    if (have_fastchunks (av))
        malloc_consolidate (av);
}

但是在进行下面的处理逻辑之前，_int_malloc会先将fastbin中的chunk进行合并然后放到unsorted bin中。

_int_malloc-2

unsorted_bin处理

接下来会进入一个大循环，该循环的主要作用是处理unsorted bin

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);

处理last_remainder

逐次取出尾结点chunk，接着检查其大小并获取其大小

if (in_smallbin_range (nb) &&
    bck == unsorted_chunks (av) &&
    victim == av->last_remainder &&
    (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
    /* split and reattach remainder */
    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;
}

如果申请的chunk大小属于smallbin范围内，先将last_remainder分割出申请大小部分内存，然后转换为mem模式分配给用户。

1
2
3

/* remove from unsorted list */
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

exact fit

如果不存在last_remainder，则先将尾结点chunk取出备用。

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;
}

接着检查该chunk大小是否刚好符合用户需求，如果是则直接返回。

分门别类

if (in_smallbin_range (size))
{
    victim_index = smallbin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd;
}

如果并不能满足exact fit的话，检查当前chunk大小是否符合smallbin范围：如果是，则归到smallbin中进行管理；如果不是，将其放到large_bin中。

else
{
    victim_index = largebin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd;

    /* maintain large bins in sorted order */
    if (fwd != bck)
    {
        /* Or with inuse bit to speed comparisons */
        size |= PREV_INUSE;
        /* if smaller than smallest, bypass loop below */
        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)
                /* Always insert in the second position.  */
                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;
        }
...

对于large_bin，其使用的数据结构为双向循环链表。

flowchart TD

A[largebin入链流程] --> B{large bin 是否为空?}

B -- 是 --> C[make victim single node nextsize ring]
B -- 否 --> D{size < smallest chunk?}

D -- yes --> E[头插法插入largebin\nupdate nextsize links]
D -- no --> F[traverse nextsize list: while size < fwd.size]

F --> G{size == fwd.size?}

G -- yes --> H[insert victim as second node of same-size group]
G -- no --> I[insert victim before fwd in nextsize list]

H --> J[set bck = fwd.bk]
I --> J[set bck = fwd.bk]

C --> Z[end]
J --> Z[end]

mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

最后链成环

_int_malloc-3

处理并分门别类完unsorted bin中所有chunk后，进入largebin分配流程

mick0960's blog

手撕ptmalloc2

堆概述

malloc(size_t n)

free(void* p)

堆相关数据结构

malloc_chunk

bin

堆处理相关宏和函数

check_remalloced_chunk

chunk2mem

fastbin_index

smallbin_index

bin_at

malloc_consolidate

mark_bin

malloc流程分析

malloc前的准备工作

_int_malloc

一些检查

sysmalloc-申请堆空间

从fastbin中分配内存

从smallbin中分配内存

_int_malloc-2

unsorted_bin处理

处理last_remainder

exact fit

分门别类

_int_malloc-3

堆概述

malloc(size_t n)

free(void* p)

堆相关数据结构

malloc_chunk

bin

堆处理相关宏和函数

check_remalloced_chunk

chunk2mem

fastbin_index

smallbin_index

bin_at

malloc_consolidate

mark_bin

malloc流程分析

malloc前 的准备工作

_int_malloc

一些检查

sysmalloc-申请堆空间

从fastbin中分配内存

从smallbin中分配内存

_int_malloc-2

unsorted_bin处理

处理last_remainder

exact fit

分门别类

_int_malloc-3

malloc前的准备工作