[隐藏]

背景

在内核中,slab分配器用于分配较小块内存,它将多个相同大小的对象放在同一个内存页中,但这些对象可能不能正好占满整个内存页,从而产生碎片造成浪费,于是内核尝试为对象分配多个物理连续内存页从而使碎片尽可能小,但在低内存设备上要分配多个连续内存页可能十分困难,特别在系统运行较长时间后,这变得几乎不可能。最坏情况下,当对象大小略大于PAGE_SIZE/2时,每个内存页接近一般的内存将被浪费。

所以,我们需要一种新的分配器,用于像vmalloc那样分配只要求虚拟连续的内存块。

Zsmalloc分配器尝试将多个相同大小的对象存放在组合页(称为zspage)中,这个组合页不要求物理连续,从而提高内存的使用率。但是,使用zsmalloc分配器有以下条件:

  • 不要求物理内存连续
  • 在使用对象前必须显示映射
  • 对象必须在原子上下文中访问

分配器API

该函数用于创建一个zsmalloc的内存池,在使用zsmalloc之前必须调用该函数创建zs_pool。name是内存池的名称,flags是分配标志。zs_pool的定义在实现文件中,因为使用者不需要关心它的定义。

该函数释放zs_pool实例。当一个pool被释放后,从其中分配的对象将不可访问。

zs_malloc和zs_free分别用于分配和释放对象。

size是需要分配的内存块的大小(字节),如果成功,返回一个对象的handle,否则返回0。

这个handle不是一个可以直接访问的对象,要获得真正可访问的对象需要调用如下函数进行映射:

handle是从zs_malloc获得的待映射的handle,mm为映射模式:

该函数的返回值是一个可访问的对象的虚拟地址。该地址本质上是一个per-CPU对象,在同一时间,在确定的cpu上,只有一个对象可以被安全的映射,同时调用该函数也将进入原子上下文,直到调用zs_unmap_object解除映射:

API的声明在include/linux/zsmalloc.h中;实现在mm/zsmalloc.c中。本文使用的内核版本为4.4-rc5

数据结构

name 该pool的名称
size_class 该成员是一个指针数组,数组的每一项都指向一个struct size_class结构,该结构保存了为分配特定大小对象的内存页。
handle_cachep slab缓存池,后面介绍
flags 分配标志
pages_allocated 已分配的内存页个数
stats 内存池统计信息

可以看到,该成员只保存了在收缩时有多少页被释放掉。
shrinker 用来缩减内核缓存的收缩器。暂不讨论
stat_dentry 当开启zsmalloc统计功能时有该成员,用于在proc中显示统计信息。暂不讨论

fullness_list 保存了几乎满或几乎空的内存页链表(zspage)。完全满和完全空的内存页不保存其中。
完全满和完全空容易理解,zspage中的对象都已在使用,不能再分配新对象就是完全满,对象都未使用则为空。
什么是几乎满呢?一个几乎满的zspage应满足 n > N / f。n表示使用中的对象数,N表示该zspage中总的对象个数,f = fullness_threshold_frac

否则,它是几乎空的。
size 指定了该size_class保存的对象的大小。
index 该size_class的阶。
pages_per_zspage 每个zspage中的内存页个数
stats 统计信息。保存了已分配的、在使用中的等对象个数
huge 是否是巨型对象,即该对象需要独自一页
各个数据结构的关系可以用下图表示:

size_class->fullness_list[ZS_ALMOST_FULL]和size_class->fullness_list[ZS_ALMOST_EMPTY]都指向一个page,该page是zspage的首页(first_page),一个zspage包含一个或多个单页。每个zspage通过首页的lru成员连接形成链表。

首页的flag被置为PG_private,而尾页的flag被置为PG_private2。

首页的private成员指向第二页,第二页至尾页的private都指向首页。第二页至尾页通过lru成员连接形成链表。

首页的objects成员保存了该zspage中对象总数,mapping成员保存了该zspage的fullness属性(ZS_ALMOST_FULL或ZS_ALMOST_EMPTY)和该zspage所属的size_class的index。

首页的inuse成员保存了当前有多少对象在使用中。

首页的freelist指向第一个空闲对象。

page->freelist和page->index在一个联合体中,除了首页,其他页的index表示第一个对象在页中的偏移,这没有问题,因为首页的第一个对象的偏移总是0.

在内存块中,每个对象头部有一个link_free结构:

该结构将所有空闲对象组织在单链表中,对于已使用对象则保存了该对象对应的handle。

实现

zs_create_pool

不出所料,该函数首先分配必须的内存。给pool->size_class数组分配了zs_size_classes个成员的内存,该值的计算后面介绍。

create_handle_cache 用于为pool创建一个slab缓存池。

该缓存是为分配handle准备的,以后调用zs_malloc获得的handle的内存就是从这个缓存中获得的。

接着初始化每个size_class成员。每个不同的size_class保存的对象大小是不一样的,size指定了该size_class中对象的大小。大小范围从ZS_MIN_ALLOC_SIZE到ZS_MAX_ALLOC_SIZE。

ZS_MAX_PAGES_PER_ZSPAGE指定了单个zspage中最多内存页的个数,即4个。

MAX_PHYSMEM_BITS指定了系统可访问内存的总位数,该系统支持的最大内存即为2^MAX_PHYSMEM_BITS;_PFN_BITS表示页帧号需要占用的bit数。MAX_PHYSMEM_BITS在32位系统上通常为32,如果开启了PAE(物理地址扩展)则为36,在64位系统上为46。我们以不支持PAE的32位系统,内存页大小为4k为例,_PFN_BITS=20,剩下的12位分配给obj index和obj tag(后面介绍),OBJ_TAG_BITS=1,OBJ_INDEX_BITS=11,所以ZS_MIN_ALLOC_SIZE = 32.最大的对象大小为一个页(如前所述,这种对象称为巨型对象)

ZS_SIZE_CLASS_DELTA指定了相邻两个size_class的对象大小差

所以ZS_SIZE_CLASS_DELTA=16

这样就使得对象大小可以是32、48。。。4k,一共255种可能。

但是pool->size_class数组大小受限于zs_size_classes,那么实际范围是不是要更小呢?

可以看到zs_size_classes的计算和ZS_SIZE_CLASS_DELTA、ZS_MIN_ALLOC_SIZE、ZS_MAX_ALLOC_SIZE是有关系的。这使得zs_size_classes即为所有可能的个数。

get_pages_per_zspage计算一个合适的值,为这种size的size_class分配特定个内存页,使得在这种情况下被浪费的内存最小。

can_merge判断是否可以使用上一次分配的size_class作为本次的size_class。如果本次要分配的页数和上次分配的页数相同,并且两次可保存的最大对象数也相同,则使用上次的size_class。如果条件成立,意味着如果为本次分配新的size_class,将产生比上次更大的内存碎片而造成浪费,这时不如直接用上次的size_class。这就是为什么for循环是从zs_size_classes – 1开始向下遍历,而不是从0开始。

如果不能merge,则创建新的size_class并初始化各个成员变量。注意,此时并未为size_class分配内存页。

size_class创建完成后,接着初始化pool的其他成员。关于统计和收缩器部分不做讨论。

zs_destroy_pool函数的工作就是释放各种内存,不再讨论。

zs_malloc

首先调用alloc_handle从slab中分配一个handle。然后将对象大小加上ZS_HANDLE_SIZE后从size_class数组中查找合适的class,find_get_zspage返回该class的第一个page。

如果class中没有可用的page,则需要新建zspage,完成该工作的是alloc_zspage。该函数分配出class->pages_per_zspage个单个的内存页按前述的zspage结构组合成一个zspage。并初始化link_free,如前所述,link_free是一个由空闲对象组成的单链表,如果对象已被分配,则该位置保存了该对象对应的handle。这就是为什么开始时要将size加上ZS_HANDLE_SIZE,它占用了内存块的前ZS_HANDLE_SIZE字节。

最后调用zs_stat_inc更新统计信息。

set_zspage_mapping用于设置首页的mapping成员,该成员被用来保存class的index和fullness属性。

index和fullness一共占用32位(CLASS_IDX_BITS=28,FULLNESS_BITS=4),所以一个指针的bit数足够保存这两个信息。

得到zspage后就可以调用obj_malloc从其中分配对象了。

如果需要,调用fix_fullness_group修改fullness属性。这可能需要修改该zspage在class->fullness_list中的位置;对于新创建的zspage,分配一个对象后,需要将该zspage放到class->fullness_list[ZS_ALMOST_EMPTY]中;如果zspage已没有空闲空间,则将其从class->fullness_list[ZS_ALMOST_FULL]中删除。

record_obj只是简单的将obj值保存在handle中。(别忘了handle其实是一个指针,它指向slab中一个指针大小的内存块,可以用来保存obj)

有趣的是,obj并不是一个可以访问的地址。

在前面已经见过OBJ_INDEX_BITS了,表示index占用的bit数。在每一个内存页中,obj的index总是从0重新开始的,而不是接着前一个内存页的index累加;tag占用1个bit,用来表示obj是否已被分配。

所以一个obj值保存了三个信息:对象所在的页帧号、对象在页帧中的编号,对象是否已被分配。根据前两个信息和对象的大小(size_class->size)、以及页中第一个对象的偏移(page->index)即可计算出对象的准确地址。

理解了zs_malloc的工作过程,zs_free的工作过程就不难理解了,基本上是zs_malloc的逆过程。如果释放过对象后zspage变为空(fullness==ZS_EMPTY),则将该zspage全部释放。

zs_map_object

pin_tag确定该handle没有在迁移,pool在收缩时,其中受影响的handle即为迁移中。关于收缩的话题后面讨论。

现在已经知道,handle中保存了obj值;obj值中保存了页帧号和obj index;page->mapping中保存了class index和fullness。根据这些信息,即可得到该handle是在哪个size_class中分配的,以及obj在页帧中的偏移。

zs_map_area是一个per-cpu变量

它保存了映射地址和模式,所以同一时间同一cpu只能有一个handle被映射。

CONFIG_PGTABLE_MAPPING用来配置是否使用页表映射来访问对象。默认情况下,zsmalloc使用基于拷贝的映射方法来访问保存在两个page中的对象,但是在一些平台上,使用vmalloc区域映射要比copy更快,这时可以配置该选项。否则使用拷贝的方法将两个page中的内容拷贝到vm_buf中。

如果对象完整保存在一个page中,映射之后直接返回即可,否则调用__zs_map_object进行映射,根据CONFIG_PGTABLE_MAPPING配置选项,__zs_map_object具有两种实现,采用如上所述的方法映射内存页,然后返回映射后的地址。

对于非巨型对象,头ZS_HANDLE_SIZE个字节保存了list_free,用户的对象地址需后移ZS_HANDLE_SIZE字节。

同样的,zs_unmap_object几乎是zs_map_object的逆过程,不再讨论。

zs_compact

zs_compact遍历pool中所有的size_class,调用__zs_compact进行收缩工作。

isolate_source_page从class的ZS_ALMOST_EMPTY链表或ZS_ALMOST_FULL链表中移出一个zspage。

zs_can_compact根据总的对象个数和已使用的对象个数计算有多少对象空闲,以此得到最多可收缩多少个页。

接着再次从class中移出一个zspage,尝试将src_page中的使用中的handle迁移到dst_page中。迁移操作由migrate_zspage完成。它遍历所有对象,如果对象的obj tag标记被置为OBJ_ALLOCATED_TAG,表示对象在使用中,调用trypin_tag将该对象标记为迁移中,迁移中的标志并没有使用另外的标记位,而是将obj tag标记置为0,这不会有问题,因为未使用的对象一定在list_free链表中,简单的将obj tag置为0并不会使该对象被当作未使用对象。当然,迁移handle也需要将与该handle关联的对象的内存拷贝到新的内存页中。

如果migrate_zspage返回0,表示src_page中的handle已全部迁移到dst_page,退出循环;否则从class中获得下一个zspage继续迁移。

putback_zspage用于将指定zspage放到class的zspage列表中,如果zspage是满的,则不进行操作,如果是空的,则将zspage释放。

如果dst_page == NULL成立,表示遍历了所有zspage,仍没有将src_page中的对象全部迁移,退出外层循环,将src_page重新插入链表。

否则,如果src_page中的对象确实迁移完毕,则将其释放。调用cond_resched使得cpu有机会去处理更紧急的任务,也使该迁移操作可以及时观察到zspage链表的变化。然后继续循环尝试合并其他的zspage。