内存分配器ptmalloc,jemalloc,tcmalloc调研与对比

rtoax
2020年12月

1. 概述 
ptmalloctcmallocjemalloc

1.1. Linux内存布局

先了解一下内存布局，以x86 32位系统为例：
在这里插入图片描述

栈自顶向下扩展，堆至底向上扩展，mmap映射区域至顶乡下扩展。mmap映射区和堆相对扩展，直至耗尽虚拟地址空间中的剩余区域，这种结构便于C语言运行时库使用mmap映射区域和堆进行内存分配。

1.2. 系统调用

1.2.1. brk() sbrk()

#include <unistd.h>
int brk(void *addr);
void *sbrk(intptr_t increment);

brk()sbrk()

1.2.2. mmap()

#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags,
          int fd, off_t offset);
int munmap(void *addr, size_t length);
  1. 用法1：映射磁盘文件到内存；
  2. 用法2：向映射区申请一块内存；
2. ptmalloc(Glibc) 
ptmalloc支持多线程
ptmalloc环形链表ptmallocptmallocptmallocmmap()HEAP_MAX_SIZEptmallocHEAP_MAX_SIZEmmap()freemunmap()ptmalloc

2.1. 系统层面

在「glibc malloc」中主要有 3 种数据结构：

malloc_state(Arena header)heap_info(Heap Header)malloc_chunk(Chunk header)
//基于GLibc-2.32
/*
   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;
};

/* 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;

/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
*/
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;
};

2.1.1. main_arena

/* There are several instances of this struct ("arenas") in this
   malloc.  If you are adapting this malloc in a way that does NOT use
   a static or mmapped malloc_state, you MUST explicitly zero-fill it
   before using. This malloc relies on the property that malloc_state
   is initialized to all zeroes (as is true of C statics).  */
static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

在这里插入图片描述

2.2. 用户层面

  1. 当某一线程需要调用malloc()分配内存空间时，该线程先查看线程私有变量中是否已经存在一个分配区；
  2. 如果存在，尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存；
  3. 如果失败，该线程搜索循环链表试图获得一个没有加锁的分配区。
  4. 如果所有的分配区都已经加锁，那么malloc()会开辟一个新的分配区，把该分配区加入到全局分配区循环链表并加锁，然后使用该分配区进行分配内存操作。
  5. 在释放操作中，线程同样试图获得待释放内存块所在分配区的锁，如果该分配区正在被别的线程使用，则需要等待直到其他线程释放该分配区的互斥锁之后才可以进行释放操作。

2.2.1. 线程中内存管理

free chunks

从工作原理来看：

Fast binsUnsorted binSmall binsLarge bins

从作用来看：

Fast binsUnsorted binSmall binsLarge bin
fast binsmalloc_statefastbinsYmalloc_state

在这里插入图片描述

2.2.2. Chunk说明

top chunk
last remainder chunk

存在的问题

  • 如果后分配的内存先释放，无法及时归还系统。因为 ptmalloc 收缩内存是从 top chunk 开始,如果与 top chunk 相邻的 chunk 不能释放, top chunk 以下的 chunk 都无法释放。
  • 内存不能在线程间移动，多线程使用内存不均衡将导致内存浪费
  • 每个chunk至少8字节的开销很大
  • 不定期分配长生命周期的内存容易造成内存碎片，不利于回收。
  • 加锁耗时，无论当前分区有无耗时，在内存分配和释放时，会首先加锁，在多核多线程情况下，对主分配区竞争激烈，严重影响性能。

从上述来看ptmalloc的主要问题其实是内存浪费、内存碎片、以及加锁导致的性能问题。

备注：glibc 2.26( 2017-08-02 )中已经添加了tcache(thread local cache)优化malloc速度

2.3. __libc_malloc（glibc 2.32）

在这里插入图片描述

2.4. 主分配去与非主分配区

内存分配器中，为了解决多线程竞争锁的问题，分为主分配去main_area和非主分配区no_main_area。

  1. 主分配区和非主分配区形成一个链表进行管理。
  2. 每个分配区利用互斥锁使线程对于该分配区的访问互斥。
  3. 每个进程只有一个主分配区，允许多个非主分配区。
  4. ptmalloc根据系统对分配区的争用动态增加分配区的大小，分配区的数量一旦增加，则不会减少。
  5. 主分配区可以使用brk和mmap来分配，非主分配区只能用mmap来映射。
  6. 申请小内存是会产生很多内存碎片，ptmalloc在整理时也要对分配区做加锁操作。

当一个线程需要malloc分配内存：

  1. 先查看该线程私有变量中是否已经存在一个分配区；
  2. 若存在，尝试加锁；
  3. 若加锁成功，使用该分配区分配内存；
  4. 若失败，遍历循环链表，获取一个未加锁的分配区；
  5. 若没找到未加锁分配区，开辟新的分配区，加入全局链表并加锁，然后分配内存；

当free释放内存：

  1. 先获取待释放内存块所在的分配区的锁；
  2. 若有其他线程持有该锁，必须等待其他线程释放该分配区互斥锁；
3. jemalloc(FackBook,FreeBSD,FireFox) 
firefoxfacebookandroid 5.0
FreeBSD libc

3.1. 系统层面

lock contentionfalse sharing

3.1.1. struct arena_s

struct arena_s {
	/*
	 * Number of threads currently assigned to this arena.  Each thread has
	 * two distinct assignments, one for application-serving allocation, and
	 * the other for internal metadata allocation.  Internal metadata must
	 * not be allocated from arenas explicitly created via the arenas.create
	 * mallctl, because the arena.<i>.reset mallctl indiscriminately
	 * discards all allocations for the affected arena.
	 *
	 *   0: Application allocation.
	 *   1: Internal metadata allocation.
	 *
	 * Synchronization: atomic.
	 */
	atomic_u_t		nthreads[2];
	/* Next bin shard for binding new threads. Synchronization: atomic. */
	atomic_u_t		binshard_next;/* 绑定的新线程的下一个bin 碎片 */
	/*
	 * When percpu_arena is enabled, to amortize the cost of reading /
	 * updating the current CPU id, track the most recent thread accessing
	 * this arena, and only read CPU if there is a mismatch.
	 */
	tsdn_t		*last_thd;/* 用于跟踪上一次使用的CPU */
	/* Synchronization: internal. */
	arena_stats_t		stats;/* arena统计信息 */
	/*
	 * Lists of tcaches and cache_bin_array_descriptors for extant threads
	 * associated with this arena.  Stats from these are merged
	 * incrementally, and at exit if opt_stats_print is enabled.
	 *
	 * Synchronization: tcache_ql_mtx.
	 */
	ql_head(tcache_slow_t)			tcache_ql;/* tcache指针 */
	ql_head(cache_bin_array_descriptor_t)	cache_bin_array_descriptor_ql;/* cache bin array描述符指针 */
	malloc_mutex_t				tcache_ql_mtx;/* 锁 */
	/*
	 * Represents a dss_prec_t, but atomically.
	 *
	 * Synchronization: atomic.
	 */
	atomic_u_t		dss_prec;
	/*
	 * Extant large allocations.
	 *
	 * Synchronization: large_mtx.
	 */
	edata_list_active_t	large;/* 现存的大块分配内存 */
	/* Synchronizes all large allocation/update/deallocation. */
	malloc_mutex_t		large_mtx;/* 大块内存的锁 */
	/* The page-level allocator shard this arena uses. */
	pa_shard_t		pa_shard;/* 页级别分配器碎片 */
	/*
	 * bins is used to store heaps of free regions.
	 *
	 * Synchronization: internal.
	 */
	bins_t			bins[SC_NBINS];/* 存放堆的free regions */
	/*
	 * Base allocator, from which arena metadata are allocated.
	 *
	 * Synchronization: internal.
	 */
	base_t			*base;/* base 分配器 */
	/* Used to determine uptime.  Read-only after initialization. */
	nstime_t		create_time;/* 创建时间 */
};

【目前jemalloc 5.2.1中已经找不到chunk结构了】
chunk是仅次于arena的次级内存结构，arena都有专属的chunks, 每个chunk的头部都记录了chunk的分配信息。chunk是具体进行内存分配的区域，目前的默认大小是4M。chunk以page（默认为4K)为单位进行管理，每个chunk的前几个page（默认是6个）用于存储chunk的元数据，后面跟着一个或多个page的runs。后面的runs可以是未分配区域， 多个小对象组合在一起组成run, 其元数据放在run的头部。 大对象构成的run, 其元数据放在chunk的头部。在使用某一个chunk的时候，会把它分割成很多个run，并记录到bin中。不同size的class对应着不同的bin，在bin里，都会有一个红黑树来维护空闲的run，并且在run里，使用了bitmap来记录了分配状态。此外，每个arena里面维护一组按地址排列的可获得的run的红黑树。

在这里插入图片描述

3.2. 用户层面

jemalloc 按照内存分配请求的尺寸，分了 small object (例如 1 – 57344B)、 large object (例如 57345 – 4MB )、 huge object (例如 4MB以上)。jemalloc同样有一层线程缓存的内存名字叫tcache，当分配的内存大小小于tcache_maxclass时，jemalloc会首先在tcache的small object以及large object中查找分配，tcache不中则从arena中申请run，并将剩余的区域缓存到tcache。若arena找不到合适大小的内存块， 则向系统申请内存。当申请大小大于tcache_maxclass且大小小于huge大小的内存块时，则直接从arena开始分配。而huge object的内存不归arena管理， 直接采用mmap从system memory中申请，并由一棵与arena独立的红黑树进行管理。
在这里插入图片描述

3.3. jemalloc的优势

多线程下加锁大大减少

4. tcmalloc(Google,Golang)

由于网上介绍的版本与代码版本找不到匹配关系，甚至介绍版本是C语言开发，网上下载的代码为C++开发，此处不做详细的源码讲解，只做结构性介绍。

tcmalloc是Google开发的内存分配器，在Golang、Chrome中都有使用该分配器进行内存分配。有效的优化了ptmalloc中存在的问题。当然为此也付出了一些代价，按下表，先看tcmalloc的具体实现。

4.1. 系统层面

4kbPage
inline constexpr size_t kPageShift = 12;
inline constexpr size_t kPageSize = 1 << kPageShift;

p>>kPageShift
// Information kept for a span (a contiguous run of pages). 
struct Span { 
    PageID start; // Starting page number 
    Length length; // Number of pages in span 
    Span* next; // Used when in link list 
    Span* prev; // Used when in link list 
    union { 
        void* objects; // Linked list of free objects 
        // Span may contain iterator pointing back at SpanSet entry of 
        // this span into set of large spans. It is used to quickly delete 
        // spans from those sets. span_iter_space is space for such 
        // iterator which lifetime is controlled explicitly. 
        char span_iter_space[sizeof(SpanSet::iterator)]; 
    }; 
    unsigned int refcount : 16; // Number of non-free objects 
    unsigned int sizeclass : 8; // Size-class for small objects (or 0) 
    unsigned int location : 2; // Is the span on a freelist, and if so, which? 
    unsigned int sample : 1; // Sampled object? 
    bool has_span_iter : 1; // If span_iter_space has valid 
    // iterator. Only for debug builds. 
    // What freelist the span is on: IN_USE if on none, or normal or returned 
    enum { 
        IN_USE, 
        ON_NORMAL_FREELIST, 
        ON_RETURNED_FREELIST 
    }; 
}; // We segregate spans of a given size into two circular linked 
// lists: one for normal spans, and one for spans whose memory 
// has been returned to the system. 
struct SpanList { 
    Span normal; 
    Span returned; 
}; 
// Array mapping from span length to a doubly linked list of free spans 
// 
// NOTE: index 'i' stores spans of length 'i + 1'. SpanList free_[kMaxPages]; 
// Sets of spans with length > kMaxPages. 
// 
// Rather than using a linked list, we use sets here for efficient 
// best-fit search. 
SpanSet large_normal_; 
SpanSet large_returned_;

在这里插入图片描述

4.2. 用户层面

TCMalloc是专门对多线并发的内存管理而设计的，TCMalloc主要是在线程级实现了缓存，使得用户在申请内存时大多情况下是无锁内存分配。

从用户角度看tcmalloc架构

整个tcmalloc实现了三级缓存，分别是：

  1. ThreadCache – 线程级别缓存；
  2. CentralCache - 中央缓存CentralFreeList；（需要加锁访问）
  3. PageHeap – 页缓存；（需要加锁访问）

在这里插入图片描述

Tcmalloc分配内存的流程：

  1. 每个线程都有一个线程局部ThreadCache，ThreadCache中包含一个链表数据组FreeList list_[kNumClasses]，维护了不同规格的空闲内存的规则的内存。
  2. 如果ThreadCache对象不够了，就从CentralCache中批量分配；
  3. 如果CentralCache依然不够，就从PageHeap中申请Span；
  4. PageHeap首先从free[n,128]中查找，然后到large set中查找，目标是为了找到一个最小满足要求的空闲Span，优先使用normal类链表中的Span。
  5. 如果找到了一个Span，则尝试分裂（Carve）这个Span并分配出去；如果所有的链表中都没找到length>=n的Span，则只能从操作系统中申请了。
  6. Tcmalloc一次最少向OS申请1MB内存，默认情况下使用是sbrk()，sbrk()失败后使用mmap()。
5. 三种分配器的对比测试

内存分配无非需要的是malloc和free的性能，版本信息如下：

glibc-2.25.1-31.base.el75.2.1-586-g92e189be8b725be1f4de5f476f410173db29bc7dgperftools 2.0
malloc()

5.1. 虚拟机

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

5.2. 服务器

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

6. 总结
  • 作为基础库的ptmalloc是最为稳定的内存管理器，无论在什么环境下都能适应，但是分配效率相对较低。
  • tcmalloc针对多核情况有所优化，性能有所提高，但是内存占用稍高，大内存分配容易出现CPU飙升。
  • jemalloc的内存占用更高，但是在多核多线程下的表现也最为优异。

在什么情况下我们应该考虑好内存分配如何管理：

  • 多核多线程的情况下，内存管理需要考虑：内存分配加锁、异步内存释放、多线程之间的内存共享、线程的生命周期；
  • 内存当作磁盘使用的情况下，需要考虑内存分配和释放的效率，是使用内存管理库还是应该自己进行大对象大内存的管理（在搜索以及推荐系统中尤为突出）。
7. 参考文章
  • 《jemalloc简介》
  • 《图解tcmalloc内存分配器》
  • 《TCMalloc：线程缓存Malloc以及tcmalloc与ptmalloc性能对比》
  • 《ptmalloc、tcmalloc与jemalloc内存分配器对比分析》
  • 《使用jemalloc在Go中进行手动内存管理》
  • 《理解 glibc malloc：主流用户态内存分配器实现原理》
  • 《Glibc 内存管理 Ptmalloc2 源代码分析》
  • 《TCMalloc分析 - 如何减少内存碎片》
  • 《TCMalloc分析笔记(gperftools-2.4)》
  • 《jemalloc源码解析-内存管理》
8. 参考链接
  • http://mqzhuang.iteye.com/blog/1005909
  • https://paper.seebug.org/papers/Archive/refs/heap/glibc%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86ptmalloc%E6%BA%90%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%90.pdf
  • http://core-analyzer.sourceforge.net/index_files/Page335.html
  • https://blog.csdn.net/maokelong95/article/details/51989081
  • https://zhuanlan.zhihu.com/p/29216091
  • https://zhuanlan.zhihu.com/p/29415507
  • https://blog.csdn.net/zwleagle/article/details/45113303
  • http://game.academy.163.com/library/2015/2/10/17713_497699.html
  • https://www.cnblogs.com/taoxinrui/p/6492733.html
  • https://blog.csdn.net/vector03/article/details/50634802
  • http://brionas.github.io/2015/01/31/jemalloc%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%90-%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86/