glibc-malloc.c源码阅读笔记

  1. glibc-malloc.c源代码阅读笔记
    1. 0x00. 前言
    2. 0x01. 一些重要的结构体
    3. 0x02. malloc 源码分析
    4. 0.03. free 源码分析

glibc-malloc.c源代码阅读笔记

0x00. 前言

malloc.c其中重要的源代码进行部分精读,部分通读的学习。主要作用还是用来自我学习,如有不当之处请多批评。-.-

选择了2.23版本的作为基础,后续可能会进行磕磕绊绊的版本补充。

未完结,长期更新中

鸽不鸽看心情


0x01. 一些重要的结构体

用于管理分配区:

/*
   have_fastchunks indicates that there are probably some fastbin chunks.
   It is set true on entering a chunk into any fastbin, and cleared early in
   malloc_consolidate.  The value is approximate since it may be set when there
   are no fastbin chunks, or it may be clear even if there are fastbin chunks
   available.  Given it's sole purpose is to reduce number of redundant calls to
   malloc_consolidate, it does not affect correctness.  As a result we can safely
   use relaxed atomic accesses.
 */
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;
};

管理参数:

struct malloc_par
{
    /* Tunable parameters */
    unsigned long trim_threshold;
    INTERNAL_SIZE_T top_pad;
    INTERNAL_SIZE_T mmap_threshold;
    INTERNAL_SIZE_T arena_test;
    INTERNAL_SIZE_T arena_max;

    /* Memory map support */
    int n_mmaps;
    int n_mmaps_max;
    int max_n_mmaps;
    /* the mmap_threshold is dynamic, until the user sets
     it manually, at which point we need to disable any
     dynamic behavior. */
    int no_dyn_threshold;

    /* Statistics */
    INTERNAL_SIZE_T mmapped_mem;
    /*INTERNAL_SIZE_T  sbrked_mem;*/
    /*INTERNAL_SIZE_T  max_sbrked_mem;*/
    INTERNAL_SIZE_T max_mmapped_mem;
    INTERNAL_SIZE_T max_total_mem;  /* only kept for NO_THREADS */

    /* First address handed out by MORECORE/sbrk.  */
    char *sbrk_base;
};

记录不同heap区域相关信息的heap_info结构体:

typedef struct _heap_info
{
    mstate ar_ptr; /* Arena for this heap. */
    struct _heap_info *prev; /* Previous heap. */
    size_t size;   /* Current size in bytes. */
    size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
    /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
    char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

堆块的基本单位chunk的结构:

struct malloc_chunk {

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

0x02. malloc 源码分析

以下代码均基于glibc2.23

malloc其实就是__libc_malloc

strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, malloc)

所以直接看__libc_malloc

void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;

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

  arena_get (ar_ptr, bytes);

  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }

  if (ar_ptr != NULL)
    (void) mutex_unlock (&ar_ptr->mutex);

  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}
libc_hidden_def (__libc_malloc)

7-10:如果__malloc_hook里不为空,则执行这个地址指向的函数。

12:arena_get:根据所需的bytes,获得arena的指针,暂时没进入去看,先当成main_arena

14:调用_int_malloc来进行操作,传入了arena以及bytes

直接看_int_malloc,入口参数两个,一个是arena,一个是需要分配大小bytes

checked_request2sizebytes转化成真正会被分配的大小nb

checked_request2size (bytes, nb);
if (__glibc_unlikely (av == NULL))
{
    void *p = sysmalloc (nb, av);
    if (p != NULL)
        alloc_perturb (p, bytes);
    return p;
}

如果arena没传进来,那么用sysmalloc来操作。

fastbin相关,首先宏观理解一下fastbin

arena里面有一个fastbinY数组,一共10个元素,每个元素都相当于链表头部,记录着对应的堆块指针

如果对应索引里面有堆块,那么就取出来,然后链表头部指向下一个堆块(如果有),这个是通过fd判断的。

所以fastbin每一条链上的堆块大小都是一样的,而且属于先进后出FILO结构。

如果fastbin对应idx里有元素,才进入其中操作:

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

1:如果nb小于get_max_fast ()得到的global_max_fast值,就是fastbin,这个值默认为0x80

3:根据传入的nb调用fastbin_indexd得到对应索引值

4-5:fbfastbin的对应链表的头节点。pp为链表里面的第一个元素。

6-13:进入循环,victim赋值为链表第一个元素,循环条件里面在干的事情相当于让fastbin对应链表更新。

16-21:检测,如果现在victimsize不满足当前所在fastbinidx,会报错。这个malloc_printerr是会调用abort()的。

24-26:得到堆块的数据指针,这里mem就是数据指针,从fd开始指,chunk就是整个堆块,从pre_size开始指。以后就记为memptrchunkptr

check_remalloced_chunk (av, victim, nb)是一个做了一大堆检测的函数:

#if !MALLOC_DEBUG
# define check_remalloced_chunk(A, P, N)
#else
# define check_remalloced_chunk(A, P, N) do_check_remalloced_chunk (A, P, N)
static void
do_check_remalloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
{
  INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);

  if (!chunk_is_mmapped (p))
    {
      assert (av == arena_for_chunk (p));
      if (chunk_non_main_arena (p))
        assert (av != &main_arena);
      else
        assert (av == &main_arena);
    }

  do_check_inuse_chunk (av, p);

  /* Legal size ... */
  assert ((sz & MALLOC_ALIGN_MASK) == 0);
  assert ((unsigned long) (sz) >= MINSIZE);
  /* ... and alignment */
  assert (aligned_OK (chunk2mem (p)));
  /* chunk is less than MINSIZE more than request */
  assert ((long) (sz) - (long) (s) >= 0);
  assert ((long) (sz) - (long) (s + MINSIZE) < 0);
}

传入的是arenachunkptrnb

md怎么里面还有检测函数,暂时当作无事发生。 -.-!

这里的alloc_perturb是填充堆块用的,我也不清除这个perturb_byte什么时候有效:

static int perturb_byte;

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

然后如果fastbin里面没找到可以用的堆块,进入下一步smallbin

unsortbinsmallbinlargebin,这些其实也都是链表结构,只不过有的表现简单,有的复杂。

这里面unsortbin只有一条链,剩下两个都有很多。

这些链表的特点是双向,如果链表里没有元素,那么fd就和bk会指向自己。

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

1:先判断nb是否在smallbin的大小范围内,不在的话直接就pass

3-4:还是,获取对应索引值,bin是获得的链表头。

6:判断一下链表里是不是有元素,因为没有就会指向自己。这个last取得是bk

8-9:smallbin里的链表指向了空,呃,什么情况暂时不祥,就会触发malloc_consolidate,这个函数会将arena中的fastbin全部能合并的合并,然后并到各种bin里,目的就是为了减少碎片,也是malloc过程里唯一的unlink调用。

12-16:bck为当前victimbk,这里说一下,victimbckfwd这些,都是一些临时变量,在对应位置对应看就好。一般来说victim表示的是当前我正在进行处理的指针,bckfwd分别对应它的bkfd

然后检测了一下,粗暴的说就是在检测我自己后面的前面是不是我自己。

18-20:然后对pre_inuse进行设置,这里设置的是victim在虚拟地址上相邻的下一个堆块,nb的目的就是为了找到虚拟地址相邻的下一个堆块!然后下两句就是把这个victim从链上脱下来的操作。

22-23:这个涉及到线程什么的了,我也暂时不明白,反正单线程永远是main_arena就是了。

24-27:检测清空返回一气呵成。

如果nb不在smallbin的范围里,那么先计算出largebinidx,然后检测arenafastbin是否存在,然后如上述所说来合并一下碎片。

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

之后会进入一个很大很恶心的多重循环结构来对unsortbin进行操作:

先看一下源码作者的注释:

/*
     Process recently freed or remaindered chunks, taking one only if
     it is exact fit, or, if this a small request, the chunk is remainder from
     the most recent non-exact fit.  Place other traversed chunks in
     bins.  Note that this step is the only place in any routine where
     chunks are placed in bins.

     The outer loop here is needed because we might not realize until
     near the end of malloc that we should have consolidated, so must
     do so and retry. This happens at most once, and only when we would
     otherwise need to expand memory to service a "small" request.

 */

大概意思就是说:

如果unsortbin的大小跟需求完全相同,直接返回。

如果是个小的请求,就从unsortbin切一块下来,剩下的留着。

然后把unsortbin里的堆块都依次放到对应的bin里面。

这个流程是放堆块到指定bin的唯一指定步骤!

外部的循环虽然看着是个死循环,但其实最多执行一次,那是因为有时候可能整个malloc流程到最后,我们才意识到需要对unsortbin操作一下。

先对unsortbin也有个宏观的把控:

首先它只有一条链,free的时候只要不是fastbin,那么统统先丢到这里链起来,这么做其实就是为了快。

arena里面有一个last_remainder,这个只有当unsortbin被切的时候才会有值,指向剩余的部分。

它是FIFO先进先出的队列结构,从bk开始索引。

一点一点地看:

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

1:检测unsortbin不为空,同时也依次从bk开始便利unsortbin的链。

3-7:得到victimbkbck以及fwd等的用法和上面都是一样的。检测一下size不能太小也不能太大。

8:得到当前操作堆块的size,这里要知道nb是我们使用malloc的时候需求的大小,size是正在处理的对快的大小,这些要区分开。

然后开始试图去用last_remainder:

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

1-4:判断条件还是很多的,nb要在smallbin范围内,unsortbin链上只能有一个堆块,last_remainder指向这个唯一堆块,堆块的size还得比nb+MINSIZE要大。

6-11:很简单的操作,相当于从这个唯一堆块里切一块大小nb下来,然后last_remainder重新赋值,然后把留下来的堆块里面的各种结构完善一下。

12-16:其实算辅助之后largebin的相关操作,两个指针置空,问题不大。

之后就是给这个victim和剩下的remainder弄成一个正经堆块的样子。

然后检测清空返回一气呵成。

那么如果上面那个苛刻的条件但凡有一条没满足,那就把这个victim卸下来:

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

如果sizenb相同,也就是与我们的需求完美契合,那就直接返回:

/* Take now instead of binning if exact fit */

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

不契合的话,先把victim放入对应bin中,smallbin的很简单没什么可说的:

/* place chunk in bin */

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

然后largebin的有点长,还是先宏观把控:

largebin,首先要知道,每条链上可以有很多堆块,且他们的大小是可以不同的。

所以就会用到fd_nextsize以及bk_nextsize来维护链内的另一条链,用来记录其中的大小关系。

所以对largebin排序的时候可能就会有一些复杂,但是记住以下的规则:

首先按照由大到小的顺序排序,相同大小的话,先free的在后面。

大小相同的若干堆块,只有首部的堆块fd_nextsizebk_nextsize有值,fd_nextsize指向比这些堆块大小还小的若干堆块首部,bk_nextsize则指向比这些堆块大小还大的若干堆块首部。最大组的bk_nextsize指向最小组,最小组的fd_nextsize指向最大组。

fdbk在所有堆块中使用。

此时的victim是从unsortbin链上卸下来的哪个,size也是他的size

越说越乱,直接写代码了:

#include <stdlib.h>

int main(int argc, char **argv)
{
    char *p1;
    char *p2;
    char *p3;
    char *p4;
    char *p5;
    char *p6;

    p1 = malloc(0x450);
    p6 = malloc(0x10);

    p2 = malloc(0x460);
    p6 = malloc(0x10);

    p3 = malloc(0x450);
    p6 = malloc(0x10);

    p4 = malloc(0x440);
    p6 = malloc(0x10);

    p5 = malloc(0x460);
    p6 = malloc(0x10);

    free(p1);
    free(p2);
    free(p3);
    free(p4);
    free(p5);

    malloc(0x1000);

    return 0;
}

gdb调试查看到的结果:

gdb-peda$ x/6gx 0x602000
0x602000:    0x0000000000000000    0x0000000000000461
0x602010:    0x0000000000602910    0x0000000000603200
0x602020:    0x0000000000602d90    0x0000000000602480

gdb-peda$ x/6gx 0x602480
0x602480:    0x0000000000000000    0x0000000000000471
0x602490:    0x0000000000603200    0x00007ffff7dd1f78
0x6024a0:    0x0000000000602000    0x0000000000602d90

gdb-peda$ x/6gx 0x602910
0x602910:    0x0000000000000000    0x0000000000000461
0x602920:    0x0000000000602d90    0x0000000000602000
0x602930:    0x0000000000000000    0x0000000000000000

gdb-peda$ x/6gx 0x602d90
0x602d90:    0x0000000000000000    0x0000000000000451
0x602da0:    0x00007ffff7dd1f78    0x0000000000602910
0x602db0:    0x0000000000602480    0x0000000000602000

gdb-peda$ x/6gx 0x603200
0x603200:    0x0000000000000000    0x0000000000000471
0x603210:    0x0000000000602000    0x0000000000602480
0x603220:    0x0000000000000000    0x0000000000000000

只画出bk是这个样子的:

1563332705266

fd没有画,其实就是bk反向指回去。

可以看到每个小链上存着同大小的堆块,先free的在前面(bk索引的话在后面),整个大链上的小链按由小到大的顺序连接

fdbk相当于记录了所有堆块的顺序关系。

fd_nextsizebk_nextsize单独画出来:

1563333888713

看着有点乱,但其实就是fd_nextsize指向size比自己小的小链的第一个成员,bk_nextsize指向size比自己大的小链的第一个成员,最大sizebk_nextsize指向最小链第一个成员,同理最小的fd_nextsize指向最大链第一个成员,

所以可以知道fd_nextsizebk_nextsize是用来记录链与链之间大小关系的。

再回到源代码:

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;
        }
    }
    else
        victim->fd_nextsize = victim->bk_nextsize = victim;
}

2-5:获得largbin的索引,获得对应头节点,然后此时bck是头节点,fwd是头节点的fd

8 & 45-46:如果largebin为空,则victimfd_nextsizebk_nextsize指向自己。

14-22:在这之前又做了些size的检测,不是很想管了。然后这里有点复杂,因为victimsize小于binbk指向元素的size,也就是在该链里面最小,所以将victim以这种方式插入链中。

24-43:不是最小的,那么就开始找他对应的分组位置,如果正好大小相同,那就插入进来,如果大小不同,那就自成一组,然后跟其他组连接起来。

之后:

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

mark_bin设置一下bitmap,我也不知道有啥用的。

然后将victim插入到对应链里。

然后回到while循环,依次操作unsortbin每个元素

然后才开始从largebin里找对应的堆块分配出来,所以这里知道了,如果fastbinsmallbin不满足分配需求,那么会先把unsortbin的堆块全部放到指定的bin链表里,然后再进行malloc的操作。

来到largebin这里:

/*
         If a large request, scan through the chunks of current bin in
         sorted order to find smallest that fits.  Use the skip list for this.
       */

if (!in_smallbin_range (nb))
{
    bin = bin_at (av, idx);

    /* skip scan if empty or largest chunk is too small */
    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;

        /* Avoid removing the first entry for a size so that the skip
                 list does not have to be rerouted.  */
        if (victim != last (bin) && victim->size == victim->fd->size)
            victim = victim->fd;

        remainder_size = size - nb;
        unlink (av, victim, bck, fwd);

        /* Exhaust */
        if (remainder_size < MINSIZE)
        {
            set_inuse_bit_at_offset (victim, size);
            if (av != &main_arena)
                victim->size |= NON_MAIN_ARENA;
        }
        /* Split */
        else
        {
            remainder = chunk_at_offset (victim, nb);
            /* We cannot assume the unsorted list is empty and therefore
                     have to perform a complete insert here.  */
            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;
    }
}

8:idx在很久很久之前就被获取到了,largebin的idx,得到了对应的链表头

11-12:要满足bin里的第一个堆块victim存在,而且尺寸必须比nb大才继续,否则跳过

14-17:从这条largebin链里小链由小到大开始选取,直到size满足大小,进入小链

21-22:找到的victim如果不是大链的最后一个(也就是不能是最小size小链的第一个)同时也不是对应小链的第一个,就取它小链对应前面的元素为新的victim

24-25:获取remainder_size,然后对一个largebin进行unlink,是一个完整的unlink流程,size是从15行那里来的

28-33:如果获得的remainder_size小于MINSIZE,对紧邻下一个堆块pre_inuse置位。如果剩余还挺大,那就进入else

37-41:从victim切一块nb大小,剩下的由remainder指针指向。然后检测了一下unsortedbin,不知道为什么。

47-50:这里知道上面到底要干嘛了,原来要把remainder插到unsortedbin里面。

51-55:很简单,如果是laregbin大小,那就先给两个指针置0

56-59:给victim和remainder设置各种chunk的结构信息,之后返回。

其实完整的unlink仍然是解链操作,只不过因为laregbin自身四个指针的复杂结构,导致unlink过程中分了好几种情况讨论,后续会补充这部分,这里先咕咕咕。

/* Take a chunk off a bin list */
#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;              \
              }                                      \
          }                                      \
      }                                          \
}

接下来的操作其实就是堆管理系统满足我,所以通过binmap来快速选择一个差不多的堆块来用。

其代码以及相关的宏定义:

++idx;
bin = bin_at (av, idx);
block = idx2block (idx);
map = av->binmap[block];
bit = idx2bit (idx);

#define BINMAPSHIFT      5
#define idx2block(i)     ((i) >> BINMAPSHIFT)
#define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))

1:idx神奇的加了1,然后得到对应的bin,这里一定是分配没成功,才过来的,所以应该是要对binmap的一些操作。

2-3:得到bin之后,block为idx位右移5位,一共126个bin,加上1就是127,二进制的0b1111111,所以友谊五位后范围就是0-3。binmap正好有四个元素。所以block的作用就是先找到大概范围。

4:得到binmap对应位置元素,记为map

5:通过idx取得对应的bit值,找到大概范围里的具体范围。

然后进入了一个循环:

for (;; )
{
    /* Skip rest of block if there are no more set bits in this block.  */
    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;
    }

    /* Advance to bin with set bit. There must be one. */
    while ((bit & map) == 0)
    {
        bin = next_bin (bin);
        bit <<= 1;
        assert (bit != 0);
    }

    /* Inspect the bin. It is likely to be non-empty */
    victim = last (bin);

    /*  If a false alarm (empty bin), clear the bit. */
    if (victim == bin)
    {
        av->binmap[block] = map &= ~bit; /* Write through */
        bin = next_bin (bin);
        bit <<= 1;
    }

    else
    {
        size = chunksize (victim);

        /*  We know the first chunk in this bin is big enough to use. */
        assert ((unsigned long) (size) >= (unsigned long) (nb));

        remainder_size = size - nb;

        /* unlink */
        unlink (av, victim, bck, fwd);

        /* Exhaust */
        if (remainder_size < MINSIZE)
        {
            set_inuse_bit_at_offset (victim, size);
            if (av != &main_arena)
                victim->size |= NON_MAIN_ARENA;
        }

        /* Split */
        else
        {
            remainder = chunk_at_offset (victim, nb);

            /* We cannot assume the unsorted list is empty and therefore
                     have to perform a complete insert here.  */
            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;

            /* advertise as last 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;
    }
}

虽然很长,但是其实36-最后的代码,和之前是一样的。

1:死循环,但是内部有退出条件,找到堆块返回了,或者去用topchunk。

太乱了,暂时不想看。先去看topchunk。

topchunk相当于一块大蛋糕,如果够用就切一块分配出来,如果不够大,那就去搞一块更大的。

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

/* When we are using atomic ops to free fast chunks we can get
         here for all block sizes.  */
else if (have_fastchunks (av))
{
    malloc_consolidate (av);
    /* restore original bin index */
    if (in_smallbin_range (nb))
        idx = smallbin_index (nb);
    else
        idx = largebin_index (nb);
}

/*
         Otherwise, relay to handle system-dependent cases
       */
else
{
    void *p = sysmalloc (nb, av);
    if (p != NULL)
        alloc_perturb (p, bytes);
    return p;
}

2-3:获取到topchunk给victim,得到topchunk的size

5-18:第一种情况,size比我们需要的nb大,切一块给用户,剩下的留着。

22-30:第二种情况,topchunk不够大,有fastbin,去调用malloc_consolidate进行一些操作,然后得到对应的idx值。这里应该也是进入到最开始的大循环第二次的唯一入口。

35-41:topchunk不够大,没有fastbin,用syscall开辟一块nb大小的堆块返还给用户。

0.03. free 源码分析

__libc_freemalloc流程类似,都是对hook进行判断:

void
__libc_free (void *mem)
{
  mstate ar_ptr;
  mchunkptr p;                          /* chunk corresponding to mem */

  void (*hook) (void *, const void *)
    = atomic_forced_read (__free_hook);
  if (__builtin_expect (hook != NULL, 0))
    {
      (*hook)(mem, RETURN_ADDRESS (0));
      return;
    }

  if (mem == 0)                              /* free(0) has no effect */
    return;

  p = mem2chunk (mem);

  if (chunk_is_mmapped (p))                       /* release mmapped memory. */
    {
      /* see if the dynamic brk/mmap threshold needs adjusting */
      if (!mp_.no_dyn_threshold
          && p->size > mp_.mmap_threshold
          && p->size <= DEFAULT_MMAP_THRESHOLD_MAX)
        {
          mp_.mmap_threshold = chunksize (p);
          mp_.trim_threshold = 2 * mp_.mmap_threshold;
          LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
                      mp_.mmap_threshold, mp_.trim_threshold);
        }
      munmap_chunk (p);
      return;
    }

  ar_ptr = arena_for_chunk (p);
  _int_free (ar_ptr, p, 0);
}
libc_hidden_def (__libc_free)

connect 1037178204@qq.com

文章标题:glibc-malloc.c源码阅读笔记

本文作者:t1an5t

发布时间:2019-07-17, 16:18:02

最后更新:2020-02-05, 20:49:30

原始链接:http://yoursite.com/glibc-malloc-c%E6%BA%90%E7%A0%81%E9%98%85%E8%AF%BB%E7%AC%94%E8%AE%B0/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录