堆相关数据结构及ptmalloc概述

@t3ls  November 12, 2018

堆相关数据结构及ptmalloc概述

  • 宏观

    • arena

      • main arena
      • thread arena
    • heap_info (heap header)
    • malloc_state (arena header)
  • 微观

    • malloc_chunk (chunk header)
    • bin

      • fast bin
      • small bin
      • large bin
      • unsorted bin
    • allocated chunk
    • free chunk
    • top chunk
    • last remainder chunk
  • 堆内存分配(堆管理器)

    • dlmalloc : general purpose allocator(Linux 中早期的堆管理器。在并行处理多个线程时,会共享进程的堆内存空间。)
    • ptmalloc2 : glibc

      • (s)brk
      • mmap
    • jemalloc : FreeBSD 、Firefox and Android
    • tcmalloc : Google Chrome
    • libumem : Solaris

进程内存分布:

进程内存分布

arena(分配区)

arena结构

  • arena 数量限制(包含 main arena

    For 32 bit systems:
         Number of arena = 2 * number of cores + 1.
    For 64 bit systems:
         Number of arena = 8 * number of cores + 1
  • 多个 arena 的管理

main arena

thread arena

当主线程首次调用malloc的时候,glibc malloc会直接为它分配一个main arena,而不需要任何附加条件。

当用户线程1和用户线程2首次调用malloc的时候,glibc malloc会分别为每个用户线程创建一个新的thread arena。此时,各个线程与arena是一一对应的。但是,当用户线程3调用malloc的时候,就出现问题了。因为此时glibc malloc能维护的arena个数已经达到上限,无法再为线程3分配新的arena了,那么就需要重复使用已经分配好的3个arena中的一个(main arena, arena 1或者arena 2)。那么该选择哪个arena进行重复利用呢?

  • 首先,glibc malloc循环遍历所有可用的arena,在遍历的过程中,它会尝试lock该arena。如果成功lock(该arena当前对应的线程并未使用堆内存则表示可lock),比如将main arena成功lock住,那么就将main arena返回给用户,即表示该arena被线程3共享使用。
  • 而如果没能找到可用的arena,那么就将线程3的malloc操作阻塞,直到有可用的arena为止。
  • 现在,如果线程3再次调用malloc的话,glibc malloc就会先尝试使用最近访问的arena(此时为main arena)。如果此时main arena可用的话,就直接使用,否则就将线程3阻塞,直到main arena再次可用为止。

这样线程3与主线程就共享main arena了。至于其他更复杂的情况,以此类推。

  • 当 arena 空间不足时,它可以通过增加 brk 的方式来增加堆的空间。类似地,arena 也可以通过减小 brk 来缩小自己的空间。

Main Arena

  • main arena 没有多个 heap,所以 没有 heap_info
  • main arena 的 malloc_state 并不是 heap segment 的一部分,而是一个全局变量,存储在 libc.so 的数据段。

Thread Arena

thread arena

heap_info (heap header)

程序刚开始执行时,每个线程是没有 heap 区域的。当其申请内存时,就需要一个结构来记录对应的信息,而 heap_info 的作用就是这个。而且当该heap的资源被使用完后,就必须得再次申请内存了。此外,一般申请的 heap 是不连续的,因此需要记录不同heap之间的链接结构。

该数据结构是专门为从 Memory Mapping Segment 处申请的内存(thread arena)准备的,即为非主线程准备的。

主线程可以通过 sbrk() 函数扩展 program break location 获得(直到触及Memory Mapping Segment),只有一个heap,没有 heap_info 数据结构。

heap_info 的主要结构如下

#define HEAP_MIN_SIZE (32 * 1024)
#ifndef HEAP_MAX_SIZE
# ifdef DEFAULT_MMAP_THRESHOLD_MAX
#  define HEAP_MAX_SIZE (2 * DEFAULT_MMAP_THRESHOLD_MAX)
# else
#  define HEAP_MAX_SIZE (1024 * 1024) /* must be a power of two */
# endif
#endif

/* HEAP_MIN_SIZE and HEAP_MAX_SIZE limit the size of mmap()ed heaps
   that are dynamically created for multi-threaded programs.  The
   maximum size must be a power of two, for fast determination of
   which heap belongs to a chunk.  It should be much larger than the
   mmap threshold, so that requests with a size just below that
   threshold can be fulfilled without creating too many heaps.  */

/***************************************************************************/

/* A heap is a single contiguous memory region holding (coalesceable)
   malloc_chunks.  It is allocated with mmap() and always starts at an
   address aligned to HEAP_MAX_SIZE.  */

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;

该结构主要是描述堆的基本信息,包括

  • 堆对应的 arena 的地址
  • 由于一个线程申请一个堆之后,可能会使用完,之后就必须得再次申请。因此,一个可能会有多个堆。prev 即记录了上一个 heap_info 的地址。这里可以看到每个堆的 heap_info 是通过单向链表进行链接的。
  • size 表示当前堆的大小
  • 最后一部分确保对齐(为什么使用负数?)

malloc_state (arena header)

该结构用于管理堆,记录每个 arena 当前申请的内存的具体状态,比如说是否有空闲 chunk,有什么大小的空闲 chunk 等等。无论是 thread arena 还是 main arena,它们都只有一个 malloc state 结构。由于 thread 的 arena 可能有多个,malloc state 结构会在最新申请的 arena 中。

注意,main arena 的 malloc_state 并不是 heap segment 的一部分,而是一个全局变量,存储在 libc.so 的数据段。

其结构如下

struct malloc_state {
    /* Serialize access.  */
    __libc_lock_define(, mutex);

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

    /* 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, help to speed up the process of determinating if a given bin is definitely empty.*/
    unsigned int binmap[ BINMAPSIZE ];

    /* Linked list, points to the next arena */
    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;
};
  • __libc_lock_define(, mutex);

    该变量用于控制程序串行访问同一个分配区,当一个线程获取了分配区之后,其它线程要想访问该分配区,就必须等待该线程分配完成候才能够使用。

  • flags

    flags 记录了分配区的一些标志,比如 bit0 记录了分配区是否有 fast bin chunk ,bit1 标识分配区是否能返回连续的虚拟地址空间。具体如下

/*
   FASTCHUNKS_BIT held in max_fast indicates that there are probably
   some fastbin chunks. It is set true on entering a chunk into any
   fastbin, and cleared only in malloc_consolidate.
   The truth value is inverted so that have_fastchunks will be true
   upon startup (since statics are zero-filled), simplifying
   initialization checks.
 */

#define FASTCHUNKS_BIT (1U)

#define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
#define clear_fastchunks(M) catomic_or(&(M)->flags, FASTCHUNKS_BIT)
#define set_fastchunks(M) catomic_and(&(M)->flags, ~FASTCHUNKS_BIT)

/*
   NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
   regions.  Otherwise, contiguity is exploited in merging together,
   when possible, results from consecutive MORECORE calls.
   The initial value comes from MORECORE_CONTIGUOUS, but is
   changed dynamically if mmap is ever used as an sbrk substitute.
 */

#define NONCONTIGUOUS_BIT (2U)

#define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
#define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)
#define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)
#define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)

/* ARENA_CORRUPTION_BIT is set if a memory corruption was detected on the
   arena.  Such an arena is no longer used to allocate chunks.  Chunks
   allocated in that arena before detecting corruption are not freed.  */

#define ARENA_CORRUPTION_BIT (4U)

#define arena_is_corrupt(A) (((A)->flags & ARENA_CORRUPTION_BIT))
#define set_arena_corrupt(A) ((A)->flags |= ARENA_CORRUPTION_BIT)
  • fastbinsY[NFASTBINS]
    存放每个 fast chunk 链表头部的指针
  • top
    指向分配区的 top chunk
  • last_reminder
    最新的 chunk 分割之后剩下的那部分
  • bins
    用于存储 unstored bin,small bins 和 large bins 的 chunk 链表。
  • binmap
    ptmalloc 用一个 bit 来标识某一个 bin 中是否包含空闲 chunk 。

bins

top chunk

last remainder chunk

ptmalloc2(堆管理器)

  • ptmalloc

Wolfram Gloger 在 Doug Lea 的基础上进行改进使其可以支持多线程,这个堆分配器就是 ptmalloc 。在 glibc-2.3.x. 之后,glibc 中集成了ptmalloc2。

  1. ptmalloc在开始时,若请求的空间小于 mmap 分配阈值(mmap threshold,默认值为 128KB)时,主分配区会调用 sbrk()增加一块大小为 (128 KB + chunk_size) align 4KB 的空间作为 heap。非主分配区会调用 mmap 映射一块大小为 HEAP_MAX_SIZ(E 32位系统上默认为1MB,64位系统上默认为64MB)的空间作为sub-heap。
  2. 当用户请求内存分配时,首先会在这个区域内找一块合适的chunk给用户。当用户释放了heap 中的chunk时,ptmalloc又会使用fast bins 和 bins 来组织空闲 chunk。以备用户的下一次分配。
  3. 若需要分配的 chunk 大小小于 mmap 分配阈值,而 heap 空间又不够,则此时主分配区会通过 sbrk()调用来增加 heap 大小,非主分配区会调用mmap映射一块新的sub-heap,也就是增加top chunk的大小,每次heap增加的值都会对齐到4KB。
  4. 当用户的请求超过mmap 分配阈值,并且主分配区使用sbrk()分配失败的时候,或是非主分配区在 top chunk 中不能分配到需要的内存时,ptmalloc 会尝试使用 mmap()直接映射一块内存到进程内存空间。使用 mmap()直接映射的 chunk 在释放时直接解除映射,而不再属于进程的内存空间。任何对该内存的访问都会产生段错误。而在 heap 中或是 sub-heap 中分配的空间则可能会留在进程内存空间内,还可以再次引用

(s)brk

对于堆的操作,操作系统提供了 brk 函数,glibc 库提供了 sbrk 函数,我们可以通过增加 brk (program break location, the program break is the address of the first location beyond the current end of the data region) 的大小来向操作系统申请内存。

在GNU C中,内存分配是这样的:

每个进程可访问的虚拟内存空间为 3G,但在程序编译时,不可能也没必要为程序分配这么大的空间,只分配并不大的数据段空间,程序中动态分配的空间就是从这一块分配的。如果这块空间不够,malloc函数族(realloc,calloc等)就调用 sbrk 函数将数据段的下界移动,sbrk函数在内核的管理下将虚拟地址空间映射到内存,供 malloc 函数使用。

sbrk 用来改变 brk ("program break" 程序间断点) 的位置,参考上方进程内存图

mmap

内存映射,简而言之就是将用户空间的一段内存区域映射到内核空间,映射成功后,用户对这段内存区域的修改可以直接反映到内核空间,同样,内核空间对这段区域的修改也直接反映用户空间。

那么对于 内核空间 <----> 用户空间 两者之间需要大量数据传输等操作的话效率是非常高的。

  • 当用户请求的内存大于128KB时,并且没有任何arena有足够的空间时,那么系统就会执行mmap函数来分配相应的内存空间。这与这个请求来自于主线程还是从线程无关。

mmap

  • 从操作系统的角度看,进程的内存分配由两个系统调用完成:brk和mmap。brk是将数据段(.data)的最高地址指针 _edata 往高地址推,mmap 是在进程的虚拟地址空间中找一块空闲的。其中,mmap 分配的内存由 munmap 释放,内存释放时将立即归还操作系统;而brk分配的内存需要等到高地址内存释放以后才能释放。也就是说,如果先后通过 brk 申请了 A 和 B 两块内存,在 B 释放之前,A 是不可能释放的,仍然被进程占用,通过 top 查看疑似内存泄露。默认情况下,大于等于128KB的内存分配会调用mmap/mummap,小于128KB的内存请求调用sbrk(可以通过设置M_MMAP_THRESHOLD来调整)
  • Glibc的新特性:M_MMAP_THRESHOLD 可以动态调整。M_MMAP_THRESHOLD 的值在 128KB 到 32MB(32位机) 或者 64MB(64位机) 之间动态调整,假如每次申请并释放一个大小为 2MB 的内存后,那么M_MMAP_THRESHOLD 的值会被调整为 2M 到2M + 4K之间的一个值。示例如下:

    char* no_used = new char[2 * 1024 * 1024];
    memset(no_used, 0xfe, 2 * 1024 * 1024);
    delete[] no_used;
    // M_MMAP_THRESHOLD的值调整为 2M 到 2M + 4K 之间的一个值,后续申请 <= 2 * 1024 * 1024 的内存块都会走 sbrk 而不是 mmap
    //而sbrk需要等到高地址内存释放以后低地址内存才能释放,会造成疑似内存泄漏的现象
  • mmap调用是会导致进程产生缺页中断的,为了提高性能,可以设置如下:

    • 将动态内存改为静态,比如采用内存池技术或者启动的时候给每个线程分配一定大小,以后直接使用;
    • 禁止mmap内存调用,禁止Glibc内存缩紧将内存归还系统,Glibc相当于实现了一个内存池功能。只需要在进程启动的时候加入两行代码
    mallopt(M_MMAP_MAX, 0); // 禁止malloc调用mmap分配内存
    mallopt(M_TRIM_THRESHOLD, 0); // 禁止内存缩进,sbrk申请的内存释放后不会归还给操作系统

关于malloc的系统调用(sbrk、mmap)具体实现,可参考以下这篇文章

ptmalloc2的多线程支持

  • 在原来的 dlmalloc 实现中,当两个线程同时调用malloc时,只有一个线程可以进入临界区,因为freelist(可利用空间表)数据结构是在所有可用线程之间共享的。因此,内存分配在多线程应用程序中需要时间,导致性能下降。
  • 而在ptmalloc2中,当两个线程同时调用malloc时,会立即分配内存,因为每个线程维护一个单独的堆段,因此维护这些堆的freelist数据结构也是分开的。这种为每个线程维护单独的堆和freelist数据结构的行为称为per thread arena
  • 在新的实现中,所有的线程共享多个堆。

ptmalloc 内存分配的具体步骤

malloc

  1. 获取分配区的锁,为了防止多个线程同时访问同一个分配区,在进行分配之前需要取得分配区域的锁。线程先查看线程私有实例中是否已经存在一个分配区,如果存在尝试对该分配区加锁,如果加锁成功,使用该分配区分配内存,否则,该线程搜索分配区循环链表试图获得一个空闲(没有加锁)的分配区。如果所有的分配区都已经加锁,那么 ptmalloc 会开辟一个新的分配区,把该分配区加入到全局分配区循环链表和线程的私有实例中并加锁,然后使用该分配区进行分配操作。开辟出来的新分配区一定为非主分配区,因为主分配区是从父进程那里继承来的。开辟非主分配区时会调用 mmap() 创建一个 sub-heap,并设置好 top chunk。
  2. 将用户的请求大小转换为实际需要分配的chunk空间大小。
  3. 判断所需分配 chunk 的大小是否满足 chunk_size <= max_fast (max_fast 默认为 64B) ,如果是的话,则转下一步,否则跳到第5步。
  4. 首先尝试在 fast bins 中取一个所需大小的 chunk 分配给用户。如果可以找到,则分配结束。否则转到下一步。
  5. 判断所需大小是否处在 small bins 中,即判断 chunk_size < 512B 是否成立。如果 chunk 大小处在 small bins 中,则转下一步,否则转到第6步。
  6. 根据所需分配的chunk的大小,找到具体所在的某个 small bin,从该 bin 的尾部摘取一个恰好满足大小的 chunk。若成功,则分配结束,否则,转到下一步。
  7. 到了这一步,说明需要分配的是一块大的内存,或者 small bins 中找不到合适的 chunk。于是,ptmalloc首先会遍历 fast bins 中的chunk,将相邻的 chunk 进行合并,并链接到 unsorted bin 中,然后遍历 unsorted bin 中的 chunk,如果 unsorted bin 只有一个 chunk,并且这个 chunk 在上次分配时被使用过,并且所需分配的 chunk 大小属于 small bins,并且 chunk 的大小大于等于需要分配的大小,这种情况下就直接将该 chunk 进行切割,分配结束,否则将根据 chunk 的空间大小将其放入 small bins 或是 large bins 中,遍历完成后,转入下一步。
  8. 到了这一步,说明需要分配的是一块大的内存,或者 small bins 和 unsorted bin 中都找不到合适的 chunk,并且 fast bins 和 unsorted bin 中所有的 chunk 都清除干净了。从 large bins 中按照 smallest-first,best-fit 原则,找一个合适的 chunk,从中划分一块所需大小的 chunk,并将剩下的部分链接回到 bins 中。若操作成功,则分配结束,否则转到下一步。
  9. 如果搜索 fast bins 和 bins 都没有找到合适的 chunk,那么就需要操作 top chunk 来进行分配了。判断 top chunk 大小是否满足所需 chunk 的大小,如果是,则从 top chunk 中分出一块来。否则转到下一步。
  10. 到了这一步,说明 top chunk 也不能满足分配要求,所以,于是就有了两个选择: 如果是主分配区,调用 sbrk(),增加 top chunk 大小;如果是非主分配区,调用 mmap() 来分配一个新的 sub-heap,增加 top chunk 大小;或者使用 mmap() 来直接分配。在这里,需要依靠 chunk 的大小来决定到底使用哪种方法。判断所需分配的 chunk 大小是否大于等于 mmap 分配阈值,如果是的话,则转下一步,调用 mmap() 分配,否则跳到第12步,增加 top chunk 的大小。
  11. 使用 mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间。 然后将内存指针返回给用户。
  12. 判断是否为第一次调用 malloc,若是主分配区,则需要进行一次初始化工作,分配一块大小为 (chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。若已经初始化过了,主分配区则调用 sbrk() 增加 heap 空间,分主分配区则在 top chunk 中切割出一个 chunk,使之满足分配需求,并将内存指针返回给用户。

free

free() 函数接受一个指向分配区域的指针作为参数, 释放该指针所指向的 chunk. 而具体的释放方法则看该 chunk 所处的位置和该 chunk 的大小. free()函数的工作步骤如下:

  1. free() 函数同样首先需要获取分配区的锁, 来保证线程安全.
  2. 判断传入的指针是否为0, 如果为0, 则什么都不做, 直接r eturn. 否则转下一步:
  3. 判断所需释放的 chunk 是否为 mmaped chunk, 如果是, 则直接释放 mmaped chunk, 解除内存空间映射. 该空间不再有效. 释放完成. 否则跳到下一步.
  4. 判断 chunk 的大小和所处的位置, 若 chunk_size <= max_fast , 并且 chunk 并不位于 heap 的顶部, 也就是说并不与 top chunk 相邻, 则转到下一步, 否则跳到第6步. (因为与 top chunk 相邻的小 chunk 也和 top chunk 进行合并, 所以这里不仅需要判断大小, 还需要判断相邻情况.)
  5. 将 chunk 放到 fastbins 中, chunk 放入到 fastbins 中时, 并不设置该 chunk 使用位. 也不与相邻的 chunk 进行合并. 只是放进去, 如此而已. 做实验的结果还发现 ptmalloc 放入 fastbins 中的 chunk 中的用户数据去全置为 0. 但是在源代码中找不到相关的代码. 这一步做完之后释放便结束了, 程序从 free() 函数中返回..
  6. 判断前一个 chunk 是否处在使用中, 如果前一个块也是空闲块, 则合并. 并转下一步.
  7. 判断当前释放 chunk 的下一个块是否为 top chunk, 如果是, 则转第9步, 否则转下一步.
  8. 判断下一个 chunk 是否处在使用中, 如果下一个 chunk 也是空闲的. 则合并, 并将合并后的 chunk 放到 bins 中. 注意, 这里在合并的过程中, 要更新 chunk 的大小, 以反映合并后的 chunk 的大小. 并转到第10步.
  9. 如果执行到这一步, 说明释放了一个与 top chunk 相邻的chunk. 则无论它有多大, 都将它与 top chunk 合并, 并更新 top chunk 的大小等信息. 转下一步.
  10. 判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD, 如果是的话, 则会触发进行 fastbins 的合并操作, fastbins 中的 chunk 将被遍历, 并于相邻的空闲 chunk 进行合并, 合并后的 chunk 会被放到 bins 中. fastbins 将变为空, 操作完成之后转下一步.
  11. 判断 top chunk 的大小是否大于 DEFAULT_TRIM_THERESHOLD. 如果是的话, 则会试图归还 top chunk 中的一部分给操作系统. 但是最先分配的 128KB 的空间是不会归还. ptmalloc 会一直控制这部分内存. 用于响应用户的分配请求. 做完这一步之后, 释放结束, 从 free 函数退出.

相关链接


评论已关闭