适用于嵌入式系统的slab分配器的设计与实现

随着硬件技术的发展和内存容量的扩大，操作系统中内存管理技术日趋完善。但是在嵌入式领域中，硬件性能和内存容量远远落后于PC机，其内存管理受到多种因素制约，若直接采用操作系统中的内存管理技术，不仅难以达到预期效果，而且会影响嵌入式系统的性能。

在嵌入式系统内存管理设计过程中，发现操作系统中的slab分配器虽然在PC机上有良好的性能，但是在嵌入式系统中不但不能发挥其优势，还降低了系统的整体性能。本文通过分析，指出了slab分配器的不足，并给出相应的解决方案。实验结果表明，slab分配器经过改进可适用于嵌入式系统。

1 slab分配器分析

操作系统内核运行时会频繁地为某些对象分配内存空间，而这些对象往往只需要几十或几百KB的空间，如果直接采用页面管理器进行内存分配，将产生很多内存碎片，造成严重的内存浪费。slab分配器支持细粒度的内存分配，较好地解决了此问题。由于性能优越，slab被Linux、FreeBSD等操作系统采用，是目前应用最广的内核内存管理器之一.

1.1 slab分配器设计思想

基于页面分配器,将一页或几页的内存组织起来，划分成一定数量的小块内存，这种连续的页面称之为slab.它为内核中使用频繁的对象建立专门的缓冲区（cache），每种类型的对象都有自己专用的cache一个cache管理着多个slab,每个slab又管理着多个对象。slab的大小与所管理对象的大小有关。根据slab管理对象的分配情况，可将每个cache中的slab分为3类:（1）slab管理的对象已经完全分配，没有空闲的对象；（2）slab管理的对象部分分配，还有部分空闲对象；（3）slab中的对象都未分配，都是空闲对象。

不同的slab分别放入不同的队列中，即每个cache管理3个slab队列，cache与cache之间的关系如图1虚框①内所示，cache与slab的关系如图1虚框②内所示。

当slab分配器接收到内存申请时，根据所申请内存的大小找到合适的cache,从cache管理的第二类slab中分配对象，若失败则从第三类slab中分配对象，若还不成功则说明cache中没有空闲对象，须为cache创建一个新的slab,从新的slab中分配空闲对象。

对象释放过程中，不仅要清空对象占用的空间，而且还要调整对象所属slab的状态，判断是否改变此slab在cache中的位置。

slab分配器采用着色机制将不同slab中的对象放入不同的偏移处，利用硬件高速缓存的映射机制，将页的不同偏移映射到硬件缓存的不同地址。而每个slab的开始部分访问频率最高，只要slab中起始对象的偏移不同则映射到硬件高速缓存的位置就不同，从而降低了频繁换入换出的性能损失.

1.2 slab分配器在嵌入式系统中的缺陷

slab分配器虽然能解决系统对小块内存的频繁需求，但是管理结构复杂，内存分配策略开销较大。在内存受限的嵌入式系统中，slab的缺陷大大影响了系统的整体性能。总之，slab分配器存在以下三方面的缺陷：

（1）slab管理结构和存储开销较大

每个slab由slab描述结构、管理空闲对象的整型数组和对象三部分组成，整型数组把slab中空闲对象组成一个顺序队列，数组大小与对象数有关，每个对象对应一个整数，如图2所示。当对象较小时，整型数组将造成较大的内存开销。

（2）cache结构复杂而且数量较多

系统中存在着专用对象和通用对象。专用对象专门存储特定用途的数据结构，例如CPU、文件系统等，其数量与系统密切相关；通用对象用来存储一般的数据结构，大小在几十KB到几千KB之间（一般为2的整次幂字节），有十多种。不管是专用对象还是通用对象，slab分配器都为其建立了一个cache结构，众多cache组织和管理的较大开销是嵌入式系统难以承受的。

（3）复杂的队列管理

如图1所示，slab分配器中存在较多的队列，每个cache管理着3个slab队列，每个slab队列与cache组成循环队列。所有的cache组成双向循环队列。面对众多的队列，如何有效地管理是很困难的。

1.3 slab在嵌入式系统中的改进

针对上节中slab分配器的三点缺陷，给出相应的改进方案。

（1）改进slab结构

针对slab中对象管理数组开销过大的问题，可以将多个不同的slab合并成一个slab,从而减少slab的数量，即一个slab管理对象的大小可在一个小范围内浮动。由于slab中对象大小不同，无法确定slab中对象的大小、数量和位置，所以必须重新设置slab结构。

（2）限制slab分配器管理的内存粒度范围

由于内核内存管理器主要负责细粒度的内存管理，所以限制所管理对象的大小。对于大块内存的申请，直接由页面分配器处理。

（3）精简队列管理

简化cache中繁杂的队列，将cache中的前两个slab队列合并成一个队列。

本文将经过上述三方面改进的分配器称之为e_slab分配器。

2 e_slab分配器设计

2.1 基本管理结构

e_slab分配器有3个重要的基本结构，下面分别对其作相关介绍。

（1）object_t结构

typedef struct object {

unsigned long size;

unsigned long offset;

} object_t;

object_t是描述对象的基本结构，每个对象对应一个object_t结构，它描述了对象的大小和下一个空闲对象的地址。

（2）e_slab_t结构

typedef struct e_slab _s {

struct list_head list;

void *s_mem;

unsigned int units;

unsigned int free;

} e_slab _t;

e_slab _t是管理对象的基本结构，它不仅描述了本结构的页块起始地址，而且存储了空闲对象的数量和地址等信息。

object_t、e_slab _t和对象结构如图3虚框②内所示。

（3）cache结构

typedef struct cache_s {

struct list_head next;

struct list_head slab_list;

unsigned int objsize;

unsigned int gfporder;

unsigned int num;

…

} cache_t;

cache的描述结构为cache_t,它主要描述了所管e_slab的基本信息。由于cache_t结构大小相同，可把cache_t看做一个专用对象，所有的cache组织在一起。

cache管理的所有e_slab被加入到list队列。把管理所有cache的结构称之为cache_cache.cache_cache与cache之间有两种关系：一种是双向队列关系，如图3虚框①内所示，cache_cache利用双向链表将系统中所有的cache（包括专用cache和通用cache）组成循环队列；一种是cache与对象之间的关系。

2.2 e_slab分配器初始化

e_slab分配器初始化主要完成cache、e_slab_t等结构的创建，为对象的分配做好准备。

2.2.1 cache的创建

cache_cache是系统中所有cache的管理者，它的创建优先于所有的cache.系统会为每种对象创建一个cache,创建流程如下：

（1）申请一个cache空间。从cache_cache中分配一个专用对象，即cache.设置cache中的各个域，包括管理的对象大小的上限和e_slab大小，其中e_slab大小与对象大小有关。

（2）将此cache加入管理队列。将cache加入cache_cache组成的双向队列中，双向队列采用通用链表链接所有的cache.

（3）将cache加入分配队列。用一个全局的cache指针指向生成的cache.

2.2.2 e_slab的创建

在cache的创建过程中，需为每个cache创建一个e_slab.e_slab中的对象全部空闲，可供分配，其流程如下：

（1）借助页面分配器申请连续物理页面。根据e_slab申请的大小和是否有DMA请求，在相应的内存区申请连续页块。

（2）设置页面属性。主要设置该页面的e_slab标志，并将该页块与cache和e_slab关联。

（3）设置e_slab描述结构，初始化对象结构。

2.3 对象的分配与释放

对象的分配与释放是内存管理模块提供的两个基本接口。

2.3.1 对象的分配

当系统需要小内存块或者专用对象时，系统会调用对象分配操作，完成对对象的分配，具体流程如图4所示。

（1）找到对应的cache.根据申请对象的大小定位相应的cache.

（2）确定对应的e_slab.检查cache中的e_slab,找到满足本次请求的e_slab,如果所有的e_slab均不能满足，则创建一个新的e_slab并添加到cache管理的队列中。

（3）从e_slab中分配一个空闲对象。从e_slab为系统分配一个空闲对象和object_t结构，将对象返还给系统，调整e_slab中对象，管理数组结构。

2.3.2 对象的释放

系统使用完对象后，应及时释放对象，否则内存会越用越少。对象释放流程如图5所示。

（1）确定对象对应的cache与e_slab.根据对象的地址可以获得所在页面的描述符结构，从而获得对应的cache和e_slab.

（2）释放对象。获得对象在e_slab中的偏移，采用头插法将对象加入空闲对象队列，并使e_slab中空闲内存增加释放值。

（3）e_slab的调整。检查e_slab中空闲内存大小，若等于e_slab中所有对象都释放，则清除页面的e_slab标志，并把e_slab占用页块归还给物理内存管理器。

2.4 e_slab分配器的回收

在系统退出、内存回收等不再需要e_slab分配器时，需进行e_slab分配器的回收，主要完成e_slab的释放和cache的释放。

2.4.1 e_slab的释放

在对象释放过程中，若发现某个e_slab已经全部空闲，没有分配的对象，则将其释放，流程如下：

（1）将e_slab从cache结构中删除。e_slab从cache的list队列中摘掉。

（2）清除页面标志。将e_slab所在物理页面的e_slab标志清除，并清除页面与e_slab和cache的关联，使页面回到初始状态。

2.4.2 cache的释放

当系统不再使用某种对象时，系统要销毁管理对象的cache.cache销毁流程如下：

（1）将cache从管理队列摘掉。将cache从cache_cache组成的双向队列中删除。

（2）确定cache中没有e_slab.在cache销毁前，必须确定所管理的对象都已释放，检查cache的list队列，为空则cache中没有e_slab,否则进行e_slab释放。

（3）释放cache结构占用的内存。由于cache是cache_cache管理的对象，cache结构的释放过程就是对象的释放过程。

3 性能测试

在嵌入式系统内存管理设计过程中，分别采用页面分配器与slab分配器相结合的方案和页面分配器与e_slab分配器相结合的方案，比较两种方案中slab和e_slab管理结构的内存占用量和内存分配释放中的性能。

在管理结构内存占用方面，e_slab比slab节省了43%的空间；在对象的c过程中，e_slab的速度比slab快8%;内存释放过程中，e_slab比slab快5%.可见，不管在时间上还是空间上，e_slab性能都比slab优越。