• ptmalloc源码分析 - _int_malloc函数实现smallbins/unsorted bin（07）

    目录

    一、smallbins的定义和空闲链表的使用条件

    二、smallbins的具体实现

    三、malloc_consolidate整理操作

    四、unsorted bin的具体实现

    前一章，我们讲解了fastbins的空闲链表的分配逻辑。这一章，我们主要讲一下smallbins和unsorted bin的分配逻辑。

    一、smallbins的定义和空闲链表的使用条件

    smallbins的定义：

    • smallbins放置在malloc_state-> bins数组上，数组从2开始编号到63，前62个bin为small bins
    • 小于512字节（64位机器1024字节）的chunk被称为small chunk，而保存small chunks的bin被称为small bin
    • small bin每个bin之间相差8个字节（64位16字节），同一个small bin中的chunk具有相同大小。起始bin大小为16字节（64位系统32）。

    smallbins空闲链表的使用条件：

    • 需要符合smallbin的大小，并且空闲链表上正好有空闲的chunk，则可以分配
    • 数组对应的chunk链表，默认情况下需要有2个及以上的元素，才能分配。如果只有一个chunk，则这个chunk是用于管理和连接链表的

    二、smallbins的具体实现

    具体的实现步骤如下：

    1. 如果符合smallbin的大小，则从smallbin的数组上获取一个chunk进行内存分配

    2. 如果是smallbin，则通过bins的数组下标获取到对应的chunk双向链表

    3. 如果空闲链表中有空闲的chunk，然后从链表的尾部通过弹出一个chunk，并修改双向链表

    4. 如果空闲链表中没有空闲的chunk，则此次分配失败，需要跳出smallbins上的分配逻辑，往下走其他逻辑的分配方式

    5. 获取得到的victim就是要操作的内存chunk对象，通过chunk2mem和alloc_perturb函数，初始化对象

    1.  /*
    2.    * 如果符合smallbin的大小，则从smallbin的数组上获取一个chunk进行内存分配，如果存在空闲chunk则分配成功；如果空闲链表为空，则分配失败需要往下走
    3.    * 1. 如果是smallbin，则通过bins的数组下标获取到对应的chunk双向链表
    4.    * 2. 然后从链表的尾部通过弹出一个chunk，并修改双向链表
    5.    * 3. 获取得到的victim就是要操作的内存chunk对象，通过chunk2mem和alloc_perturb函数，初始化对象 */
    6.   if (in_smallbin_range (nb))
    7.     {
    8.       idx = smallbin_index (nb); //获取smallbin的数组下标
    9.       bin = bin_at (av, idx); //av->获取数组上的bin ； bins数组为：mchunkptr结构的数组
    10.  
    11.       //只有bin这个chunk双向链表有2个以上值，才会分配
    12.       //bin是mchunkptr结构的链表（双向链表）；last(bin) 获取bin->bk，获取最后一个chunk；从链表的尾部，取一个victim
    13.       //Case1： A -> B -> C -> D 四个chunk，则取出D，调整双向链表：A -> B -> C
    14.       //Case2： A -> B 两个chunk，则取出B，调整双向链表:A->bk = A / A->fd = A
    15.       if ((victim = last (bin)) != bin)
    16.         {
    17.           bck = victim->bk; //获取victim的前一个bin
    18. 	  if (__glibc_unlikely (bck->fd != victim))
    19. 	    malloc_printerr ("malloc(): smallbin double linked list corrupted");
    20.           set_inuse_bit_at_offset (victim, nb); //将victim设置为已使用状态
    21.           bin->bk = bck; //将bin->bk设置为bck
    22.           bck->fd = bin; //将bck->fd设置为bin
    23.  
    24.           if (av != &main_arena)
    25. 	    set_non_main_arena (victim);
    26.           check_malloced_chunk (av, victim, nb);
    27.  
    28. ..................简
    29.  
    30.           void *p = chunk2mem (victim); //通过chunk结构，获取data数据部分的指针地址
    31.           alloc_perturb (p, bytes); //初始化内存块
    32.           return p;
    33.         }
    34.     }

    三、malloc_consolidate整理操作

     如果是largebin，则会把fast bin中的chunk进行一次整理合并。然后将合并后的chunk放入unsorted bin中，这是通过malloc_consolidate这个函数完成。核心逻辑就是进行一次碎片化整理。

    malloc_consolidate具体不展开了，核心处理逻辑：

    1. 遍历fastbins，针对里面的chunk进行一次循环遍历操作，检查每个chunk的前一个和后一个chunk是否是free状态，如果是free状态，则合并
    2. 如果合并后的chunk不和top chunk挨着，则将这个chunk放进unsorted bins中
    3. 如果合并后的chunk和top chunk挨着，则重新设置top chunk的起始位置
    1.   /*
    2.      If this is a large request, consolidate fastbins before continuing.
    3.      While it might look excessive to kill all fastbins before
    4.      even seeing if there is space available, this avoids
    5.      fragmentation problems normally associated with fastbins.
    6.      Also, in practice, programs tend to have runs of either small or
    7.      large requests, but less often mixtures, so consolidation is not
    8.      invoked all that often in most programs. And the programs that
    9.      it is called frequently in otherwise tend to fragment.
    10.    */
    11.  
    12.   else
    13.     {
    14. 	  /* 如果是largebin，则会把fast bin中的chunk进行一次整理合并
    15. 	   * 然后将合并后的chunk放入unsorted bin中，这是通过malloc_consolidate这个函数完成*/
    16.       idx = largebin_index (nb);
    17.       if (atomic_load_relaxed (&av->have_fastchunks))
    18.         malloc_consolidate (av);
    19.     }

    四、unsorted bin的具体实现

    unsorted bin的定义：

    • 是bins的一个缓冲区，bins数组下标为1的即是unstored bin，被释放后未存储的bin。
    • 当用户释放的内存大于max_fast或者fast bins合并后的chunk都会进入unsorted bin上
    • 当用户malloc的时候，如果fastbins和smallbins没有分配成功，则会到unsorted bin上查找是否有合适的bin，如果没有合适的bin，ptmalloc会将unsorted bin上的chunk放入bins上，然后到bins上查找合适的空闲chunk。

    核心处理流程：

    1. 从unsorted bin的双向链表上去循环遍历每一个未存储的chunk，进行内存分配或者重新放置到smallbins和largebins上去

    2. 如果，我们分配的是一个small类型的，遇到合适大小的chunk，则可以将chunk进行切割，并且切割后返回分配的内存chunk

    3. 如果，请求的大小，正好和chunk大小匹配，则直接分配成功

    4. 如果，上面两步的分配都不成功，则将该chunk根据大小类型，放置到smallbins或者largebins上去

    5. 最后，继续开始循环迭代操作

    1.   //尝试从unsorted bin中分配
    2.   for (;; )
    3.     {
    4.       int iters = 0;
    5.       //从unsorted bin的双向链表上去循环处理，直到循环回到起始节点
    6.       //unsorted bin放置在av->bins[1]的数组上，也是chunk类型的双向链表
    7.       while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
    8.         {
    9.           bck = victim->bk; //获取前一个chunk
    10.           //确认当前chunk的大小，因为unsorted bin放置的是整理后的bin，大小并不是由small bin和large bin这种数组下标来决定的
    11.           size = chunksize (victim);
    12.           mchunkptr next = chunk_at_offset (victim, size); //获取内存块上相邻的下一个chunk的地址，这个不是双向链表上的，是内存相邻的chunk
    13.  
    14. .............简
    15.  
    16.           /*
    17.            * 分配的是small类型的并且小于当前的chunk，则可以进行切割分配
    18.            * 几个条件：
    19.            * 1. 需要符合smallbin
    20.            * 2. unsorted bins上只剩下一个bin
    21.            * 3. 当前的chunk等于last_remainder
    22.            * 4. size需要大于nb，并且分割后的last_remainder，仍然可以使用*/
    23.           if (in_smallbin_range (nb) &&
    24.               bck == unsorted_chunks (av) &&
    25.               victim == av->last_remainder &&
    26.               (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
    27.             {
    28.               /* split and reattach remainder 进行chunk的切割操作 */
    29.               remainder_size = size - nb; //remainder的大小
    30.               remainder = chunk_at_offset (victim, nb); //remainder指针地址
    31.               unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
    32.               av->last_remainder = remainder;
    33.               remainder->bk = remainder->fd = unsorted_chunks (av);
    34.               if (!in_smallbin_range (remainder_size))
    35.                 {
    36.                   remainder->fd_nextsize = NULL;
    37.                   remainder->bk_nextsize = NULL;
    38.                 }
    39.  
    40.               set_head (victim, nb | PREV_INUSE |
    41.                         (av != &main_arena ? NON_MAIN_ARENA : 0)); //设置mchunk_size 大小
    42.               set_head (remainder, remainder_size | PREV_INUSE); //设置mchunk_size 大小
    43.               set_foot (remainder, remainder_size); //设置下一个chunk->mchunk_prev_size
    44.  
    45.               check_malloced_chunk (av, victim, nb);
    46.               void *p = chunk2mem (victim); //通过chunk结构，获取data数据部分的指针地址
    47.               alloc_perturb (p, bytes); //初始化内存块
    48.               return p;
    49.             }
    50.  
    51.           /* remove from unsorted list */
    52.           if (__glibc_unlikely (bck->fd != victim))
    53.             malloc_printerr ("malloc(): corrupted unsorted chunks 3");
    54.           unsorted_chunks (av)->bk = bck;
    55.           bck->fd = unsorted_chunks (av);
    56.  
    57.           /* Take now instead of binning if exact fit */
    58.           /* 请求的大小，正好和chunk大小匹配，则直接分配成功 */
    59.           if (size == nb)
    60.             {
    61.               set_inuse_bit_at_offset (victim, size); //将victim设置为已使用状态
    62.               if (av != &main_arena)
    63. 		set_non_main_arena (victim);
    64. ............简
    65.               check_malloced_chunk (av, victim, nb);
    66.               void *p = chunk2mem (victim);//通过chunk结构，获取data数据部分的指针地址
    67.               alloc_perturb (p, bytes);//初始化内存块
    68.               return p;
    69.  
    70.             }
    71.  
    72.           /* place chunk in bin */
    73.           //当前chunk属于small bin的范围，将其放回small bin
    74.           if (in_smallbin_range (size))
    75.             {
    76.               victim_index = smallbin_index (size);
    77.               bck = bin_at (av, victim_index);
    78.               fwd = bck->fd;
    79.             }
    80.           else //当前chunk属于large bin的范围，将其放回large bin
    81.             {
    82.               victim_index = largebin_index (size);
    83.               bck = bin_at (av, victim_index);
    84.               fwd = bck->fd;
    85.  
    86.           ................简
    87.  
    88.           mark_bin (av, victim_index);
    89.           // bck -> fwd 插入victim   bck -> victim -> fwd
    90.           victim->bk = bck;
    91.           victim->fd = fwd;
    92.           fwd->bk = victim;
    93.           bck->fd = victim;
    94.  
    95.  
    96.  
    97. #define MAX_ITERS       10000
    98.           //循环最多10000次，则结束
    99.           if (++iters >= MAX_ITERS)
    100.             break;
    101.         }

    下一章节，我们继续看_int_malloc函数里面的largebins和topchunk的实现

  • 相关阅读:
    回溯搜索函数
    从统计语言模型到预训练语言模型---预训练语言模型（BERT，GPT，BART系列）
    Ruby on Rails Post项目设置网站初始界面
    roarctf_2019_easy_pwn
    jQuery元素的筛选
    DAY03_瑞吉外卖——公共字段自动填充&新增分类&分类信息分页查询&删除分类&修改分类
    Postman使用
    GPU性能优化与模型训练概览
    碘乙酰胺在Desthiobiotin-Iodoacetamide试剂中的作用？
    Vue以及整合ElementUI
  • 原文地址：https://blog.csdn.net/initphp/article/details/132754647