使用空闲链表bins管理用户free掉的内存作为下次使用,而不是直接还给os,可避免频繁的系统调用,降低内存分配的开销;
若分配区锁竞争激烈,会导致非主分区快速增长,当非主分区数量达到阈值之后,会因为无法分配新的非主分区而导致线程阻塞,从而影响ptmalloc的效率;
先申请的内存先释放会导致内存无法收缩。这是因为ptmalloc的内存收缩是从Top chunk开始的,若Top chunk相邻的内存未释放,则Top chunk以下的所有内存都不能释放,从而导致内存泄漏;
申请/释放内存都需要加锁。
linux 32位操作系统:
heap从低地址向高地址扩展,与mmap相对扩展,直至耗尽虚拟地址空间中的剩余区域;
offset:随机偏移量,避免通过缓冲区溢出进行攻击;
应用程序所使用的主要是heap/mmap,前者通过sbrk->brk进行申请,后者通过mmap/unmmap将一个文件映射进内存;
由于brk/mmap属于系统调用,若每次都使用它们申请内存,则每次都会产生系统调用,影响性能;其次,由于堆是从低地址到高地址扩展的数据结构,若高地址内存未释放,则低地址内存即使已被释放也无法回收,故这种申请方式容易产生内存碎片。
基于这种原因,malloc采用内存池的管理方式(ptmalloc),ptmalloc 采用边界标记法将内存划分成很多块,从而对内存的分配与回收进行管理。为了保证内存分配的高效性,ptmalloc会预先向操作系统申请一块内存,当申请/释放内存时,ptmalloc会将这些内存管理起来,并通过一些策略来判断是否将其回收给操作系统。这样做的最大好处就是,使内存的申请/释放更为高效,避免产生过多的内存碎片。
旧版本的ptmalloc只有一个主分配区,而线程在分配/释放内存时都需要对主分配区加锁,因此对多线程不友好。改进后的ptmalloc由一个主分配区和若干个非主分配区构成,它们通过一个环形链表进行管理。
非主分配区只增不减;
分配内存时,需要遍历环形链表,找到一个未被任何线程锁定的非分配区。若存在这样一个分配区,则锁定,否则新增一个非主分配区,插入环形链表并锁定;
主分配区与非主分配区的区别:主分配区可以通过sbrk/mmap分配内存,非主分配区只能通过mmap分配内存;
ptmalloc中分配/释放的内存都被表示成chunk。chunk按结构可分为使用中和空闲两种类型。
使用中的chunk:
chunk指针:指向chunk的开始地址;mem指针:指向用户内存块的开始地址;
A:主分区/非主分区标识符,0:主分配区分配,1:非主分配区分配;
M:0:heap区域分配,1:mmap映射区域分配;
P:前一个chunk的状态, 0:前一个chunk为空闲(此时prev_size有效), 1:前一个chunk正在使用(此时prev_size无效)。ptmalloc 分配的第一个块总是将P置为1, 以防止程序引用不存在的chunk区域。
P主要用于内存块的合并操作。
空闲的chunk:
说明:
空闲的chunk只有AP状态,无M状态;
原本是用户数据区的地方存储了四个指针:
1)fd/bk:分别指向后/前一个空闲chunk。malloc通过这两个指针将大小相近的chunk连成一个双向链表;
2)fd_nextsize/bk_nextsize:存在于large bin中,用于加快在large bin中查找最近匹配的空闲chunk。不同的chunk链表又是通过bins或者fastbins来组织的。
用户free掉的内存,ptmalloc并不会马上还给os,而是用空闲链表bins管理起来了,这样当下次malloc一块内存时,ptmalloc会直接从bins上寻找一块合适大小的内存块分配给用户使用。这样的好处可以避免频繁的系统调用,降低内存分配的开销。
ptmalloc按chunk的大小将bins分成四类:fast/unsorted/small/large bins。
fast bins:
unsorted bins:
bins 数组的第一个元素,用于加快分配速度。当用户释放的内存大于max_fast或fast bins合并后的chunk都会首先插入unsorted bin中;
small bins:
小于512字节的chunk称为small chunk,而保存small chunks的bin被称为small bin。small bin存储在bins数组第2个至第65个位置,前后两个bin相差8个字节,同一个bin中的chunk大小相同。
large bins:
大于等于512字节的chunk称为large chunk,而保存large chunks的bin被称为large bin。large bin位于small bins后面。每一个large bin包含了给定范围内的chunk,large bin内的chunk按先大小后最近使用时间递减排序。
并不是所有chunk都按以上四种方式进行组织,以下两种情况例外:
Top chunk:
分配区的顶部空闲内存,当所有的bins上都不能满足内存分配要求时,就会使用top chunk进行分配。
若Top chunk的大小大于用户请求的内存大小时,则分割top chunk成两部分:User chunk(用户请求大小)和Remainder chunk(剩余大小)。其中Remainder chunk将成为新的Top chunk;
当Top chunk的大小小于用户请求的内存大小时,则通过sbrk(main arena)或mmap(thread arena)系统调用来扩容Top chunk。
mmaped chunk:
当用户请求的内存非常大(大于分配阀值,默认128K)时,需被mmap映射,则会放到mmaped chunk上,当释放mmaped chunk上的内存的时候会直接还给os。
锁定一个分配区,防止多线程冲突;
将用户请求分配的内存大小向上取整到class_size;
若class_size < max_fast(64B),则检查fast bins是否存在适合的chunk。存在则分配结束,否则继续;
运行到此步,说明fast bins上未有合适的chunk或class_size > 64B且class_size<512B,则检查small bins是否存在合适的chunk。存在则分配结束,否则继续;
遍历fast bins,将相邻的chunk合并后链接到unsorted bin中。
若unsorted bins中只有一个chunk且大于class_size,则切割并将剩余chunk重新放回unsorted bins;
若unsorted bins中有class_size大小的chunk,则从unsorted bins删除并返回;
若unsorted bins中的chunk属于small bins的范围,则插入small bins的头部;
若unsorted bins中的chunk属于large bins的范围,则插入large bins。
运行到此步,说明fast/unsorted/small bins都不满足分配要求,则从large bins中查找找到合适的chunk进行切割,一部分分配给用户,剩下的放入unsorted bin中;
运行到此步,说明fast/unsorted/small/large bin都不满足分配要求,则检查Top chunk:
若Top chunk的大小大于用户请求的内存大小时,则分割top chunk成两部分:User chunk(用户请求大小)和Remainder chunk(剩余大小)。其中Remainder chunk将成为新的Top chunk;
当Top chunk的大小小于用户请求的内存大小时,则通过sbrk(main arena)或mmap(thread arena)系统调用来扩容Top chunk。
获取待释放内存所属的分配区,若该分配区已被其他线程锁定,则等待;
根据chunk的M标识判断该chunk是否由mmap映射的内存。是,则直接使用unmmap()释放,否则继续;
判断chunk释放与Top chunk相邻。是,则与Top chunk合并跳转到6),否则继续;
若chunk > max_fast(64B),则插入unsorted bin,并且检查是否有合并,有合并情况并且和Top chunk相邻,则转到步骤8;
若chunk < max_fast(64B),则插入fast bin。
插入后若当前chunk的下一个chunk也是空闲的,则合并后插入unsorted bin。若合并后的大小 > 64B,则触发fast bins的合并操作:遍历fast bins,将相邻的空闲chunk合并病插入unsorted bin中,fast bin会变为空。(若合并后的chunk与Top chunk相邻,则与Top chunk合并。)
判断Top chunk是否大于mmap收缩阈值(默认为128KB)。是,则将Top chunk中的一部分还给os。
对多线程友好,对于小内存(256K以下)的分配,基本不用加锁;大内存的分配通过自旋锁实现;
减少内存碎片;
内存只增不减,除非通过API:releaseFreeMemory强制释放。
PageHeap:
PageHeap由若干个链表和一个集合组成;
链表节点称为span,同一个链表中节点大小相同,为N*Page,N从1至128,1Page=4K;
超过128Page的,由集合管理;
为了平摊系统调用的开销,PageHeap每次向os申请若干个Page。
CenterCache:
由若干个链表组成;
同一个链表中节点大小相同,不同链表按8k、16k、32K、48K、……、256K分类;
CenterCache的内存来源于PageHeap;
ThreadCache:
由若干个链表组成;
同一个链表中节点大小相同,不同链表按8k、16k、32K、48K、……、256K分类;
ThreadCache的内存来源于CenterCache;
TheadCache为线程的私有线程池,不需要加锁;
tcmalloc将内存分为3类:
小对象:(0, 256K];
中对象:(256k, 128Page];
大对象:(128Page, -)
对于小对象,按8k、16k、32K、48K、……、256K等class_size分类,为了避免内存碎片,它们之间并不是成简单的2的幂次方关系。分配内存时,采用向上取整方式,即申请1-7字节都会被分配一块8字节内存。这是因为若采用2的幂次方,则当申请33字节时,会被分配一块64字节内存,从而导致50%的内存碎片。
小对象内存分配:
假设申请的内存大小为size,将size向上取整到class_size;
检查ThreadCache class_size对应的链表是否为空。否,则取出一个节点作为分配结果,否则继续;
检查CenterCache class_size对应的链表是否为空。否,则为了平摊锁的开销,会一次性取出若干个节点,一个作为分配结果,剩余的存储到ThreadCache中;否则继续;
将class_size向上取整到NPage。N的取值为:(NPage-Mclass_size)/(NPage)<=1/8,通过这种方法可以将内存碎片控制在12.5%。
遍历PageHeap从NPage至128Page的链表,检查是否有大于NPage的节点。是,假设节点大小为MPage,则将MPage切割成N*Page和(M-N)*Page两部分,前一部分按class_size分割后存储到CenterCache,后一部分插入到HeapPage中(M-N)*Page的链表中,否则继续;
若PageHeap不为空,则取出一个节点,假设为MPage,切割成NPage和(M-N)*Page两部分前一部分按class_size分割后存储到CenterCache,后一部分若大于128Page,则重新插入集合,否则插入到HeapPage中(M-N)*Page的链表中,否则继续;
使用mmap/sbrk向os申请内存;
中对象内存分配与小对象类似,区别在于不会查找ThreadCache/CenterCache,而是直接检索PageHeap链表,链表分配失败,则继续查找PageHeap集合,之后再直接向os申请。
大对象内存分配则直接检索PageHeap集合,分配失败后,直接向os申请。
若释放的内存大于1*Page,则插入到PageHeap中,否则继续;
将内存插入到ThreadCache链表中,若插入后链表长度超过阈值,则将若干个节点插入到CenterCache的链表中;
若CenterCache链表长度超过阈值,则合并后插入到PageHeap;
减少多线程竞争。采用多个arena管理内存并与线程绑定(small/large都由arena分配),当线程数不超过arena数时,可保证各线程独占一个arena。由于arena之间不存在地址关联,因此此时线程之间不存在锁竞争。当线程数超过arena数时,存在多个线程共享一个arena,此时可通过arena内部的锁机制进行同步;
各线程都有自己的tcache,可避免多线程同步;
地址空间重用,减少碎片。释放的内存会首先存入tcache,同时在一定的条件下可与相邻的空闲空间合并,并归还给arena或os;
使用了红黑树等策略实现低地址优先(总是从低地址开始分配),以降低内存碎片化;
jemalloc大概需要2%的额外开销(tcmalloc 1%,ptmalloc最少8B)。
内存被划分成若干个arena;
每个arena被划分成若干个chunk(每个chunk默认为4M);
每个chunk被划分成若干个run;
每个run由若干个page组成(每个page默认为4K),同一个run中的page又被细分成若干个大小相同的region;
为了减少内存碎片及快速定位到合适大小的内存,jemalloc将run按以下class_size分成44类(同一个run下的region大小相同):
small(<4K): [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840]
large(4K-4M): [4K, 8K, 12K, …, 4072K]
huge(>4M): [4M, 8M, 12M, …]
对于小于4K内存的申请,jemalloc直接向上取整到最小的class_size,例如申请1-7字节,都会分配一个8字节内存。
struct arena_s { unsigned ind; //当前arena在arenas数组中的索引 unsigned nthreads; //已绑定的线程数 malloc_mutex_t lock; //锁同步,绑定线程(修改nthreads)、新增chunk/run是需要加锁 ql_head(tcache_t) tcache_ql; //ring queue, 存储于了所有与当前arena绑定的线程的tcache arena_chunk_tree_t chunks_dirty; //红黑树, 节点为含有dirty page的chunk(dirty:已被分配) arena_chunk_t *spare; //存储最近一次被释放的chunk,当需要创建一个新chunk时, 首先会检索spare, 由此提高频繁分配释放而可能导致chunk利用率下降的问题 size_t nactive; //当前arena中正在使用的page数 size_t ndirty; size_t npurgatory; arena_avail_tree_t runs_avail; //红黑树, 记录所有空闲的runs(run被释放后,会存储在这里) chunk_alloc_t *chunk_alloc; chunk_dalloc_t *chunk_dalloc; arena_bin_t bins[NBINS]; //记录各small class_size中non-full runs的使用情况 };
arena_bin_s 结构:
struct arena_bin_s { malloc_mutex_t lock; arena_run_t *runcur; //当前可用于分配的run, 一般情况下指向地址最低的non-full run, 同一时间一个bin只有一个current run用于分配 arena_run_tree_t runs; //记录当前arena中该bin对应small class_size的所有non-full runs。因为分配是通过current run完成的, 所以也相当于current run的仓库 malloc_bin_stats_t stats; };
struct arena_chunk_s { arena_t *arena; //属于哪个arena rb_node(arena_chunk_t) dirty_link; //若该chunk含有dirty page,则该node挂载到红黑树arena.chunks_dirty中 size_t ndirty; //含有的dirty page数量 size_t nruns_avail; //内部available runs数量 size_t nruns_adjac; arena_chunk_map_t map[1]; //动态数组, 指向并记录内部各page状态:unallocated(还未建立run的page)和small/large(该page所属run的类型为small/large)三类 }
run header结构:
struct arena_run_s { arena_bin_t *bin; //所属的bin uint32_t nextind; //下一个clean region的索引 unsigned nfree; //当前空闲region数量 map; //指向并记录内部各region的状态 }
struct tcache_s { ql_elm(tcache_t) link; //链接节点,用于将同一个arena下的所有tcache链接起来 uint64_t prof_accumbytes; arena_t *arena; //指向所属的arena unsigned ev_cnt; //周期计数器。tcache每执行一次分配/释放, ev_cnt记录一次,当周期到来时, jemalloc会清理tcache中多余的region, 将它们归还给run,以便交给其他更饥饿的线程以分配使用 unsigned next_gc_bin; //指向下一次gc的binidx. tcache gc按照一周期清理一个bin执行 tcache_bin_t tbins[1]; //动态数组 };
tcache bin结构:
struct tcache_bin_s { tcache_bin_stats_t tstats; int low_water; unsigned lg_fill_div; //跟cache refill有关,当tcache耗尽时, 会请求arena run进行refill。 unsigned ncached; //当前空闲的region数量 void **avail; //保存region指针的stack, 称为avail-stack }
将size向上取整到class_size;
若class_size > 4M,则跳转到6;
检查当前线程是否已绑定arena,若未绑定,则选择并绑定一个arena。
如何选择arena?
遍历指针数组arenas,检查是否存在未被任何线程绑定的arena。有,则与当前线程绑定,否则继续;
检查已创建的arena总数是否超过最大阈值(阈值跟cpu核数有关,初始状态只有一个arena)。否,则新增一个arena,在与当前线程绑定后存入数组arenas;否则继续;
将当前线程与绑定的线程数最少的arena绑定;
注:
当线程数 <= area数时,可以保证每个线程都能独占一个area,而由于两个arena在地址空间上几乎不存在任何联系, 故此时可以避免多线程竞争;
当线程数 > area数时,则会出现多个线程绑定同一个arena,此时线程之间的内存分配需要加锁。
若class_size < 4K:
检查线程私有存储空间tcache.tbins[class_size]是有空闲region,有则取出栈顶节点作为分配结果,否则继续;
尝试从arena.bins[class_size].runs获取new run。若获取失败,则继续,否则跳转到5);
尝试从arena.runs_avail上获取一个new run。若获取失败,则继续,否则跳转到5);
构造一个新的chunk并分割成若干个new run,其中一个作为本次使用,剩余的存储到arena.runs_avail中;
在使用new run之前, 再次检查当前bin的runcur是否可用(这里有两种可能,一是其他线程可能通过free释放了多余的region/run, 另一种是其他线程抢在当前线程之前分配了新run)。若runcur可用且new run是空,则释放new run;若runcur可用且new run不为空且其地址低于runcur, 则交换二者, 并将runcur插入arena.runs_avail;否则继续;
在new run中分配若干region,其中一个作为分配结果,其余的挂载在tcache.tbins[class_size].avail下作为下次使用;
若class_size > 4K且class_size < 4M:
检查线程私有存储空间tcache.tbins[class_size]是否空闲region。有则直接分配,否则继续;
从从arena.runs_avail上获取一个new run。若获取成功,则切割一块class_size作为分配结果(不会分配多块填充tcache.tbins),剩余部分放回arena.runs_avail,否则继续;
分配一个新的chunk,分割,剩余部分放回arena.runs_avail;
通过mmap分配;
对于所有small/large的region,会直接插入到线程私有存储空间tcache_t.tbins[class_size]的栈顶(为了保持region的热度,保证下次最先被分配出去);
当tcache_t.tbins[class_size]满载时,需要将栈底的N个region放回到run内,即将arena_chunk_s.map对应位置标记为空闲,然后将剩余部分整体移到栈低(为了保持cache热度);
将tcache_t.tbins[class_size]中的region塞回run后,若塞入之前该run已没有剩余region,则塞入之后需要将该run插入所属的bin中,即arena_bin_s.runs;若塞入之后,整个run都为空闲,则需将其从所属的arena_bin_s.runs移除,并插入到arena.runs_avail;
在3)中将run释放后,会与相邻的空闲run合并,若整个chunk都空闲,则需要将chunk插入到arena.spare中。若arena.spare已有chunk,则插入前需要将旧chunk移除并释放其物理内存;
通过不同线程,测试并发能力;通过随机分配,测试不同大小的分配速度。只测试malloc,因为申请后马上释放,再申请,可能会复用前一次的内存(释放给系统后,不会马上归还到虚拟/物理内存)。
单线程随机分配100-150字节:
2个线程随机分配100-150字节:
4个线程随机分配100-150字节:
8个线程随机分配100-150字节:
测试伪代码:
for(int I = 0; I < num; ++i) { p[i] = alloc(***); } //for(int I = 0; I < num - 1; ++i) //全部释放 for(int I = 0; I < num - 1; ++i) //最后一块不释放 { free(p[i]); }
malloc后free全部内存:
分配测试free前一半,再free后一半:
allocated:应用程序分配的字节总数;
active:应用程序分配的活动页面中的字节总数(默认为每页4 KB)。 这是页面大小的倍数,并且大于或等于allocated;
mapped:映射的活动块中的字节总数(默认为每块4MB)。 这是块大小的倍数,并且大于JeMalloc活动字节。
联系客服