八、内存管理（二）-创新互联

2、内存管理区

本节关注具有连续的物理地址和任意长度的内存单元序列。

伙伴系统算法采用页框作为基本内存区，这适合于大块内存的请求。显然如果为了存放很少的字节而分配一整个页框，非常浪费。内碎片是由于请求内存的大小与分配给它的大小不匹配造成的。

2.1 slab分配器

slab分配算法基于下列前提：

①、所存放数据的类型可以影响内存区的分配方式。slab分配器把内存区看成对象，这些对象由一组数据结构和几个叫构造和析构的函数组成，前者初始化内存区，后者回收内存区。为了避免重复初始化对象，slab分配器并不丢弃已分配的对象，而是释放但把他们保存在内存中。当以后又要请求的新的对象时，就可以从内存获取而不用重新初始化。

②、内核倾向于反复请求同一类型的内存区。例如，只要内核创建一个新进程就要为一些固定大小的表如进程描述符、打开文件对象等等分配内存区。当进程结束时，包含这些表的内存区还可以被重新使用。因为进程的创建和撤销非常频繁。

③、对内存区的请求可以根据他们发生的频率来分类。对于预期频繁请求一个特定大小的内存区而言，可以通过创建一组具有适当大小的专用对象来高效的处理，由此避免内存碎片的产生。对于很少遇到的内存区大小，可以通过基于一系列几何分布大小的对象分配模式来处理，即使这种方式会导致内存碎片。

④、在引入的对象大小不是几何分布的情况下，即数据结构的起始物理地址不是2的次幂，可以借助处理器硬件高速缓存。

⑤、因为伙伴系统函数的每次调用都弄脏硬件高速缓存，所以增加了内存的平均访问时间。

slab分配器把对象分组放进高速缓存。每个高速缓存都是同种类型对象的一种储备。包含高速缓存的主内存区被划分为多个slab，每个slab由一个或多个连续的页框组成。这些页框中既包含已分配的对象，也包含空闲对象。

slab分配器数据结构图

2.2 高速缓存描述符

每个高速缓存都是有kmem_cache_t类型的数据结构来描述。

struct kmem_cache_t{
　　struct  array_cache *[] array;//每CPU指针数组指向包含空闲对象的本地高速缓存　　unsigned int batchcount ;//要转移进本地高速缓存或从本地高速缓存中转移出的大批对象的数量　　unsigned int limit　　;//本地高速缓存中空闲对象的大数目。　　struct  kmem_list3 lists;
　　unsignedint　objsize; //高速缓存中包含对象的大小　　unsigned int flags;//描述高速缓存永久属性的标志　　unsigned int num;//封装在一个单独的slab中的对象个数（高速缓存中所有slab具有相同大小　　unsigned int free_limit;//整个slab高速缓存中空闲对象的上限　　spinlock_t spinlock;//高速缓存自旋锁　　unsigned int gfporder; //一个单独slab中包含的连续页框数目的对数　　unsigned int gfpflags;//分配页框时传递给伙伴系统函数的一组标志　　size_t colour;　　//slab 使用的颜色个数　　unsigned int colour_off;// slab中基本对齐偏移
　　unsignedint colour_next; //下一个被分配的slab使用的颜色　　kem_cache_t * slabp_cache ;//指针指向包含slab描述符的普通slab高速缓存　　unsigned int slab_size ;//单个slab的大小　　unsigned int dflags //描述高速缓存动态属性标志　　void * ctor; //指向与高速缓存相关的构造方法指针　　void * dtor;//析构　　const char* name; //高速缓存名字　　struct list_head next;//高速缓存描述符双向链表}

kmem_cache_t描述符的lists字段又是一个结构体：

struct kmem_list3{
　　struct list_head slabs_partial;//部分满　　struct list_head slabs_full ;//全满　　struct list_head slabs_free;//空闲　　unsigned long free_objects; //空闲对象的个数　　int　　free_touched;//由slab分配器页回收算法使用　　unsigned long next_reap;//同上　　struct array_cache* shared ;//指向所有cpu共享的一个本地高速缓存的指针}

2.3 slab描述符

struct slab{
　　struct list_head list; //指向以上三个链表中一个　　unsigned long colouroff; //slab中第一对象的偏移　　void * s_mem;//slab中第一个对象地址　　unsigned int inuse ;//当前正在使用的slab中的对象个数　　unsigned int free ；//slab中下一个空闲对象的下标，如果没有剩下空闲对象则为BUFCTL_END}

slab描述符可以存放在两个可能的地方：
①、外部slab描述符：存放slab外部，位于cache_sizes指向的一个不适合ISA DMA的普通高速缓存中

②、内部slab描述符：存放在slab内部，位于分配给slab的第一个页框的起始位置

当对象小于512M或者当内部碎片为slab描述符和对象描述符在slab中留下足够的空间时，slab分配器选择第二种方案。如果slab描述符放在slab外部，则kmem_cache_t的flags字段中CFLGS_OFF_SLAB值为1否则为0；

2.4 普通和专用高速缓存

普通：

①、第一个高速缓存叫做kmem_cache，包含由内核使用的其余高速缓存的高速缓存描述符。cache_cache变量包含第一个高速缓存的描述符。

②、另外一些高速缓存包含用作普通用途的内存区。一个叫做malloc_sizes的表（元素类型为cache_sizes）分别指向26个高速缓存描述符，与其相关的内存区大小为32、64、128...131072字节。对于每种大小，都有两个高速缓存：一个使用与ISA MDA分配，另一个适用于常规分配。

在系统初始化期间调用kmem_cache_init()和kmem_cache_sizes_init()来建立普通高速缓存。

专用高速缓存是有kmem_cache_create()函数创建的。这个函数首先根据参数确定处理新高速缓存的方法：是在slab内还是slab外包含slab描述符。然后它从cache_cache中为新的告诉缓存分配一个高速缓存描述符，并把这个描述符插入到高速缓存描述符的cache_chain链表中。

kmem_cache_destroy()撤销一个高速缓存并将其从cache_chain链表上删除。这个函数主要用于模块中，即装入模块时创建自己的高速缓存，卸载时撤销高速缓存。为了避免浪费空间，内核必须在撤销高速缓存本身之前就撤销其所有的slab。kmem_cache_shrink()函数通过反复调用slab_destroy()撤销高速缓存中的所有slab().

2.4.1 slab分配器与分区页框分配器接口

当slab分配器创建新的slab时，它依靠分区页框分配器来获得一组连续的空闲页框。通过kmem_getpages()函数实现。大体如下：

void *kmem_getpages(kmem_cache_t *cachep,int flags){

struct page *page;

int i;

flags |= cachep->gfpflags;

page = alloc_pages(flags,cachep->gfporders);

if(!page)

return NULL:

void * address = page_address(page);

i = (1<gfporder);

if(cache->flags&SLAB_RECLAIM_ACCOUT)

atomic_add(i,&slab_reclaim_pages);

while(i--)

SetPageSlab(page++);

return address;

}

相反的操作，通过调用kmem_freepages()函数可以释放分配给slab的页框

void kmem_freepages(kmem_cache_t *cahcep,void *addr){

unsigned long i = (1<gfporder);

struct page *page = virt_to_page(addr);

if(current->reclaim_state)

current->reclaim_state->reclaimd_slab +=i;

while(i--)

ClearPageSlab(page++);

free_pages((unsigned long)addr,cachep->gfporder);

if(cachep->flags & SLAB_RECLAIM_ACCOUNT)

atomic_sub(1<gfporder,&slab_reclaim_pages);

}

2.4.2 给高速缓存分配slab

当发出一个分配新对象的请求，并且高速缓存中并不包含任何空闲对象时，slab分配器通过调用cache_grow()函数给高速缓存分配一个新的slab。而这个函数调用kmem_getpages()从分区页框分配器获得一组页框来存放一个单独的slab，然后又调用alloc_slabmgmt()获得一个新的slab描述符。如果高速缓存描述符的CFLGS_OFF_SLAB设置，则从高速缓存描述符的slabp_cache字段指向的普通高速缓存中分配这个新的slab描述符；否则，从slab的第一个页框中分配这个slab描述符。

给定一个页框，内核必须确定他是否被slab分配器使用，如果是，就迅速得到相应高速缓存和slab描述符的地址。因此，cache_grow()扫描分配给新slab的所有页框的页描述符，并将对应高速缓存地址和slab描述符地址分别赋给页描述符lru字段的next和prev字段。这项工作不会出错，因为只有当页框空闲时，伙伴系统的函数才会使用lru字段，而只要涉及到伙伴系统，slab分配器函数所处理的页框就不空闲并将PG_slab标志设置。通过slab描述符中s_mem字段可以确定slab块中第一个页框的地址，通过高速缓存描述符gfporder可以确定slab的大小，则slab要使用哪些页框可以确定。

接着，cache_grow()调用cache_init_objs()，它将构造方法应用到新slab包含的所有对象上。

最后，cache_grow()调用list_add_tail()来将新得到的slab描述符*slabp，添加到高速缓存描述符*cachep的全空slab链表的末端，并更新高速缓存中的空闲对象计数器。

list_add_tail(&slabb->list,&cachep->lists->slabs_free);

cachep->lists->free_objects += cachep->num;//因为新创建slab中所有对象空闲，所以添加一个slab中所有对象的数量到free_objects中。

2.4.2 从高速缓存中释放slab

当高速缓存中有太多空闲对象或周期性定时器函数确定是否有完全未使用的slab能被释放时，调用slab_destory()函数撤销一个slab，并释放相应的页框到分区页框分配器：

void slab_destory(kmem_cache_t *cachep,slab_t *slabp){

if(cachep->dtor){

int i ;

for(i=0;inum;i++){

void* objp = slabp->s_mem + cachep->objsize*i;

(cachep->dtor)(objp,cachep,0);

}

}

kmem_freepages(cachep,slabp->s_mem-slabp->colouroff);

if(cachep->flags&CFLGS_OFF_SLAB)

kmem_cache_free(cache->slabp_cache,slabp);

}

}

2.5 对象描述符

每个对象都有类型为kmem_bufctl_t的一个描述符。对象描述符放在一个数组中，位于相应的slab描述符之后。数组中的第一个对象描述符描述slab第一个对象，以此类推。对象描述符是一个无符号整数，只有在对象空闲时有意义。它包含的是下一个空闲对象在slab对象数组中的下标。

2.6 对齐内存中的对象

kmem_cache_create()函数按如下方式处理请求：

①、如果对象大小高于高速缓存行的一半，就在RAM中根据L1_CACHE_BYTES的倍数（也就是行的开始）对齐对象。

②、否则，对象的大小就是L1_CACHE_BYTES的因子取整。可以保证一个小对象不会横跨两个高速缓存行。

2.7 slab着色

先要理解硬件高速缓存：http://miaoo.in/talk-about-the-cache.html；

同一硬件高速缓存行可以映射RAM中很多不同的块。相同大小的对象倾向于存放在kmem_cache_t高速缓存中相同的偏移量处。在不同的slab内具有相同偏移量的对象最终很可能映射在同一硬件高速缓存行中。硬件高速缓存可能因此而花费内存周期在同一高速缓存行与RAM内存单元之间来来往往传送两个对象，而其他的高速缓存行并未充分使用。slab分配器通过一种叫做slab着色的策略，尽量降低高速缓存的这种不愉快行为：把叫做颜色的不同随机数分配给slab。

slab分配器利用空闲未用的字节free来对slab着色。着色只是用来细分slab，并允许内存分配器把对象展开在不同的线性地址中。这样的话可以是这些线性地址映射到硬件高速缓存的不同行中。

具有不同颜色的slab把slab的第一个对象存放在不同的内存单元，同时满足对齐约束。可用颜色的个数是free/aln。因此，第一个颜色表示为0，最后一个颜色表示为free/aln -1.

如果用颜色col对一个slab着色，那么第一个对象的偏移量（相对于slab的起始地址）就等于col * aln + dsize(slap描述符大小加上所有对象描述符大小）。着色的本质是把slab中的一些空闲区域从末尾移到开始。

只有当free足够大时，着色才起作用。如果对象没有请求对齐，或者如果slab内free小于所请求的对齐（free<

通过把当前颜色存放在高速缓存描述符的colour_next字段，就可以在一个给定对象类型的slab之间平等地发布各种颜色。cache_grow()函数把colour_next所表示的颜色赋给一个新的slab，并递增这个字段的值。当colour_next的值变为colour后，又从0开始。这样每个新创建的slab都与前一个slab具有不同的颜色，直到大可用颜色。此外，cache_grow()函数从高速缓存描述符的colour_off字段获得值aln，根据slab内对象的个数计算dsize，最后把col * aln + dsize的值存放到slab描述符的colouroff字段中。

2.8 空闲Slab对象的本地高速缓存

为了减少处理器之间对自旋锁的竞争并更好的利用硬件高速缓存，slab分配器的每个高速缓存包含一个被称作slab本地高速缓存的每CPU数据结构，该结构由一个指向被释放对象的小指针数组组成。slab对象的大多数分配和释放只影响本地数组，只有在本地数组下溢或上溢时才涉及slab数据结构。

高速缓存描述符的array字段是一组指向array_cache数据结构的指针，系统中每个CPU对应于一个元素。每个array_cache数据结构是空闲对象的本地高速缓存的一个描述符。

array_cache结构的字段：

unsigned int avail; //指向本地高速缓存中可以使用对象的指针的个数。它同时也作为高速缓存中第一个空闲的下标

unsigned int limit ;//本地高速缓存的大小，也就是本地高速缓存中指针的大个数

unsigned int batchcount ;//本地高速缓存重新填充或腾空时使用的块大小

unsigned int touched ;// 如果本地高速缓存最近已经被使用过，则该标志为1

本地高速缓存描述符并不包含本地高速缓存本身的地址；事实本地高速缓存本身的地址在本地高速缓存描述符之后。本地高速缓存存放的是指向已经释放的对象的指针，而不是对象本身，对象本身总是位于高速缓存的slab中。

当创建一个新的slab高速缓存时，kmem_cache_create()函数决定本地高速缓存大小、分配本地高速缓存，并将它们的指针存放在高速缓存描述符的array字段。

2.8.1 分配slab对象

通过调用kmem_cache_alloc()函数可以获得新对象。函数本质上等于以下代码：

void * kmem_cache(kmem_cache_t *cachep,int flags){

unsigned long save_flags;

void *objp;

struct array_cache *ac;

local_irq_save(save_flags);

ac = cachep->array[smp_processor_id()];

if(ac->avail){

ac->touched = 1;

objp = ((void**)(ac+1))[--ac->avail];

}else

objp = cache_alloc_refill(cachep,flags);

local_irq_restore(save_flags);

return objp;

}

cache_alloc_refill()函数本质上执行如下步骤：

①、将本地高速缓存描述符的地址存放在ac局部变量中：ac = cachep->array[smp_processer_id()];

②、获得cachep->spinlock锁

③、如果slab高速缓存包含共享本地高速缓存，并且该共享本地高速缓存包含一些空闲对象，函数就通过从共享本地高速缓存中上移ac->batchcount个指针来重新填充CPU的本地高速缓存。然后，函数跳到第6步。

④、函数视图填充本地高速缓存，填充值为高速缓存的slab中包含的多大ac->batchcount个空闲对象的指针

a、查看slab_patial和slabs_free，并获得可用slab的描述符地址slabp，如果不存在空闲slab，则goto 5；

b、对于slab中的每个空闲对象，函数增加slab描述符的inuse字段，将对象的地址加入本地高速缓存，并更新free字段使他存放下一个空闲对象的下标：

slabp->inuse++;

((void**)(ac+1))[ac->avail++] = slabp->s_mem + slab->free*cachep->obj_size;

slabp->free = ((kmem_bufctl_t*)(slabp+1))[slabp->free];

c、如果必要，将清空的slab插入到适当的链表上，可以是slab_full链表，也可以是slab_partial链表。

⑤、被加到本地高速缓存上的指针个数被存放在ac->avail字段：函数递减同样数量的kmem_list3结构的free_objects字段来说明这些对象不再空闲。

⑥、释放cachep->spinlock。如果现在ac->avail字段大于0，函数将ac->touched字段设为1，并返回最后插入到本地高速缓存的空闲对象指针：

return ((void**)(ac+1))[--ac->avail];

否则，没有发生任何高速缓存再填充的情况：调用cache_grow()获得一个新slab，从而获得新的空闲对象。如果cache_grow()失败了，则函数返回NULL；否则它返回第一步重复该过程。

2.8.2 释放slab对象

kmem_cache_free()函数释放一个曾经由slab分配器分配给某个内核函数的对象。

void kmem_cache_free(kmem_cache_t *cachep,void *objp){

unsigned long flags;

struct array_cache* ac;

local_irq_save(flags);

ac = cachep->array[smp_processor_id()];

if(ac->avail==ac->limit)//检查空闲slab对象本地高速缓存是否已满。满了，就清空本地高速缓存。

cache_flusharray(cachep,ac);

((void**)(ac+1))[ac->avail++] = objp;//将释放的对象指针加入空闲slab对象本地高速缓存中

local_irq_restore(flags);

}

cache_flusharray()执行如下操作：

①、获得cachep->spinlock

②、如果slab高速缓存包含一个共享本地高速缓存，并且如果该共享本地高速缓存还未满，函数句通过从CPU的本地高速缓存中上移ac->batchcount个指针来填充共享本地高速缓存。

③、调用free_block()函数将当前包含在本地高速缓存中的ac->batchcount个对象归还给slab分配器。

④、释放cache->spinlock

⑤、通过减去被移动到共享本地高速缓存或被释放到slab分配器的对象的个数来更新本地高速缓存描述符的avail字段。

⑥、移动本地高速缓存组起始处的那个本地高速缓存中的所有指针。

2.9 通用对象

如果对存储区的请求不频繁，就用一组普通高速缓存来处理，普通高速缓存中的对象具有几何分布大小，范围为32——131072字节。

调用kmalloc()函数就可以得到这种类型的对象，函数等价于：

void *kmalloc(size_t size,int flags){

struct cache_sizes *csizep = malloc_sizes;

kmem_cache_t * cachep;

for(;csizep->cs_size;csizep++){

if(size>csizep->cs_size)

continue;

if(flags&__GFP_DMA)

cachep = csizep->cs_dmacachep;

else

cachep = csizep->cs_cachep;

return kmem_cach_alloc(cachep,flags);

}

return NULL;

}

调用kmalloc()所获得的对象可以通过调用kfree()来释放：

void kfree(const void *objp){

kmem_cache_t *c;

unsigned long flags;

if(!objp)

return;

local_irq_save(flags);

c = (kmem_cache_t *)(virt_to_page(objp)->lru.next);//通过读取内存区所在的第一个页框描述符的lru.next子字段，确定出合适的高速缓存描述符

kmem_cache_free(c,(void*)objp);

local_irq_restore(flags);

}

2.10 内存池

一个内存池允许一个内核成分，如块设备子系统，仅在内存不足的紧急情况下分配一些动态内存来使用。

如果动态内存变得极其稀有以至于所有普通内存分配请求都失败的话，那么作为最后的解决手段，内核成分就能调用特定的内存池函数提出储备得到所需内存。

一个内存池常常叠加在slab分配器之上，他被用来保存slab对象的储备。内存池能被用来分配任何一种类型的动态内存，从整个页框到使用kmalloc()分配的小内存区。一般将内存池处理的内存单元看做内存元素。

内存池由mempool_对象描述。字段：

spinlock_t lock;

int min_nr;//内存池中大元素的个数

int curr_nr;//内存池当前元素个数

void ** elements;//数组指针，该数组由指向保留元素的指针组成

void *pool_data; //池的拥有者可获得的私有数据

mempool_alloc_t * alloc; //分配一个元素的方法

mempool_free_t * free ;//释放一个元素的方法

wait_queue_head_t wait;//当内存池为空时使用的等待队列

当内存元素时slab对象时，alloc和free方法一般由mempool_alloc_slab()和mempool_free_slab()函数实现，他们分别是调用kmem_cache_alloc()和kmem_cache_free()函数。在这种情况下，mempool_t对象的pool_data字段存放了slab高速缓存描述符的地址。

mempool_create()创建一个新的内存池，参数为min_nr，alloc和free方法和赋给pool_data字段的任意值。

mempool_alloc()从内存池分配一个元素。函数本质上先从基本内存分配器入手，基本内存无法满足，才触及内存池。

mempool_free()释放一个元素到内存池，如果内存池已满，则调用free（）方法释放元素到基本内存分配器。