2017-02-23
一、伙伴系统
LInux下用伙伴系统管理物理内存页，伙伴系统得益于其良好的算法，一定程度上可以避免外部碎片为何这么说？先回顾下Linux下虚拟地址空间的分布。
在X86架构下，系统有4GB的虚拟地址空间，其中0-3GB作为用户空间，而3-4GB是系统地址空间。linux系统系统地址空间理论上应该不可换出，即每个虚拟页面均会对应一个物理页帧。如果这样的话，系统地址空间就能使用1GB，如果系统有多余的内存，这里仍然使用不上，这就限制了其性能的发展。为了解决这一问题，就有了高端内存的概念（本质上是由于虚拟地址空间的不足，在64位模式下，由于虚拟地址空间异常庞大，没有高端内存的概念）。
所以这1GB的地址空间就划分成了三部分：
这1GB地址空间的最低16M是作为DMA的空间，最为昂贵；而NORMAL区是一致映射区，即这部分和前面DMA区的虚拟页面都是和物理内存页面一一对应，通过一个偏移量即可把这部分的虚拟地址转化成具体的物理地址，LInux内核正是加载在这个区域。而高端内存区是为了建立临时映射用的，所以这部分地址基本要避免被长期占用。在程序中分配内存，要首先从高端内存分配，其次NORMAL区，最后才到DMA区。
而伙伴系统又是如何工作的呢？LInux系统在初始化伙伴系统时，会根据空闲页面（物理页帧）的连续程度，形成不同的链表。在LINux下有三个内存域（不考虑NUMA），即上面提到的三个，每个内存域由zone结构表示，在zone 结构表示如下：
struct zone{ ... struct free_area free_area[MAX_ORDER] ... }
MAX_ORDER 指定连续页面的数量，其值一般从0-11表示页面大小从2^0~2^11即从单页面到2048个页面。相同大小的连续内存区对应一个表项。当分配内存时，根据指定的值，首选在指定的匹配的内存链表中选择，如果没有对应的空闲内存块，则从上面一级的空闲内存块分割一块可用的内存。其中一块用于分配，另一块加入适当的链表。依次类推，这种就避免了我要申请一个page，结果从维护10个连续页面的链表页面中分配一个页，造成的外部碎片问题。而free_area结构如下：
struct free_area{ struct list_head free_list[MIGRATE_TYPES]; unsigned long nr_free; }
该结构其实维护着一组链表，为何呢？先看上面，伙伴系统一定程度上避免了外部碎片，但是随着系统运行时间的增加，仍然会存在很多小碎片，虽然在用户层，可以实现交叉映射（物理地址不连续，逻辑上连续），但是由于内核空间的一致映射，碎片问题还是无法避免。基于此，Linux开发者就对页面根据可移动性质，分了几种类型：
enum { MIGRATE_UNMOVABLE, MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_PCPTYPES, /* the number of types on the pcp lists */ MIGRATE_RESERVE = MIGRATE_PCPTYPES, #ifdef CONFIG_CMA /* * MIGRATE_CMA migration type is designed to mimic the way * ZONE_MOVABLE works. Only movable pages can be allocated * from MIGRATE_CMA pageblocks and page allocator never * implicitly change migration type of MIGRATE_CMA pageblock. * * The way to use it is to change migratetype of a range of * pageblocks to MIGRATE_CMA which can be done by * __free_pageblock_cma() function. What is important though * is that a range of pageblocks must be aligned to * MAX_ORDER_NR_PAGES should biggest page be bigger then * a single pageblock. */ MIGRATE_CMA, #endif #ifdef CONFIG_MEMORY_ISOLATION MIGRATE_ISOLATE, /* can‘t allocate from here */ #endif MIGRATE_TYPES };
这样让具有相同性质的内存集中分配，就可以避免其他内存被占用而不能移除的情况。在初始状态，内存本身没有这些性质，只是随着系统的运行，系统固定在某个地方分配某种内存，形成的这种分布。
具体架构如下图所示：
在启用NUMA的系统中（目前主流的系统都加入了对NUMA的支持），对于桌面类的系统，一般都是作为一个NUMA节点，但是的确是NUMA的流程实现的内存分配。NUMA下的各个内存域的关系如下：
内存分配首先在当前CPU关联的节点内分配，如果当前CPU内存不足，则可以通过备用列表，分配其他节点的内存，从这一点来看，貌似是把或伙伴系统扩大了，两个相邻节点也可作为伙伴，但是速度会受到影响。
二、SLAB机制
伙伴系统作为底层的内存管理机制，虽然已经做到足够优秀，但是其内存的分配总是以页为单位，面对小内存块的需求，通过伙伴系统分配就有点杀鸡用牛刀的感觉了。况且比较频繁的对伙伴系统进行调用对性能也有不少影响。基于此，SLAB分配器便被引入进来。这里SLAB分配器的思想就好比是一个代售点，而伙伴系统就好比是厂家。厂家不允许商品单独销售，只会按照一定的规格发售。而一般来讲，普通用户达不到厂家发售的量，但是普通用户却构成了比较大的消费群体。这时候，SLAB发现了商机（哈哈），他一次性的从伙伴系统批发足够多的内存，然后对普通用户发售。普通用户使用完毕，由SLAB回收，但是SLAB不用交还给伙伴系统，这样在下次又有请求，直接从SLAB这里分配即可，不需要走伙伴系统的流程，从这一点就大大提高了分配的效率。说到这里，大家可能就明白了，说到底SLAB不就是一个缓存么，内核中缓存的思想太多了。windows中的非换页内存的管理，其实就有点这种意思。
SLAB分配的功能
SLAB主要由两个功能：
1、对对象的管理
2、对小内存块的管理
1.1 对对象的管理
对于对象的管理，系统中存在某些对象需要频繁的申请和销毁。比如进程对象task_struct，针对这种需求，内核首先分配好一定数量的对象通过某种数据结构保存起来，在有分配需求的时候，直接从对应数据结构获取即可。使用完毕再交换给相应数据结构。这里实现这种功能的就是SLAB。
针对一个对象的缓存，有一个专门的结构kmem_cache表示,一个cache可能有多个slab组成，系统中的cache形成一条链表，而一个cache中的slab也会形成链表，只不过按照slab中的对象使用情况，分成三条链表：全部使用、部分使用、全部空闲。
系统中缓存组织结构如下:
缓存结构kmem_cache如下：
struct kmem_cache { /* 1) Cache tunables. Protected by cache_chain_mutex */ unsigned int batchcount; unsigned int limit; unsigned int shared; unsigned int size; u32 reciprocal_buffer_size; /* 2) touched by every alloc & free from the backend */ unsigned int flags; /* constant flags */ unsigned int num; /* # of objs per slab */ /* 3) cache_grow/shrink */ /* order of pgs per slab (2^n) */ unsigned int gfporder; /* force GFP flags, e.g. GFP_DMA */ gfp_t allocflags; size_t colour; /* cache colouring range */ unsigned int colour_off; /* colour offset */ struct kmem_cache *slabp_cache; unsigned int slab_size; /* constructor func */ void (*ctor)(void *obj); /* 4) cache creation/removal */ const char *name; struct list_head list; int refcount; int object_size; int align; /* 5) statistics */ #ifdef CONFIG_DEBUG_SLAB unsigned long num_active; unsigned long num_allocations; unsigned long high_mark; unsigned long grown; unsigned long reaped; unsigned long errors; unsigned long max_freeable; unsigned long node_allocs; unsigned long node_frees; unsigned long node_overflow; atomic_t allochit; atomic_t allocmiss; atomic_t freehit; atomic_t freemiss; /* * If debugging is enabled, then the allocator can add additional * fields and/or padding to every object. size contains the total * object size including these internal fields, the following two * variables contain the offset to the user object and its size. */ int obj_offset; #endif /* CONFIG_DEBUG_SLAB */ #ifdef CONFIG_MEMCG_KMEM struct memcg_cache_params *memcg_params; #endif /* 6) per-cpu/per-node data, touched during every alloc/free */ /* * We put array[] at the end of kmem_cache, because we want to size * this array to nr_cpu_ids slots instead of NR_CPUS * (see kmem_cache_init()) * We still use [NR_CPUS] and not [1] or [0] because cache_cache * is statically defined, so we reserve the max number of cpus. * * We also need to guarantee that the list is able to accomodate a * pointer for each node since "nodelists" uses the remainder of * available pointers. */ struct kmem_cache_node **node; struct array_cache *array[NR_CPUS + MAX_NUMNODES]; /* * Do not add fields after array[] */ };
关于此结构不在详细描述，只是最后一个字段array数组记录CPU缓存的使用情况。每次申请和释放完对象都要访问该字段。array_cache结构如下：
struct array_cache { unsigned int avail;//可用对象的数目 unsigned int limit;//可拥有的最大对象的数目 unsigned int batchcount;// unsigned int touched; spinlock_t lock; void *entry[]; /*主要是为了访问后面的对象 * Must have this definition in here for the proper * alignment of array_cache. Also simplifies accessing * the entries. * * Entries should not be directly dereferenced as * entries belonging to slabs marked pfmemalloc will * have the lower bits set SLAB_OBJ_PFMEMALLOC */ };
具体到slab本身，一个slab包含两部分：管理数据和被管理的对象。对象的存储一般并不是连续的，而是按照一定的方式进行对齐。目前有两种方式：1、按照硬件缓存行进行对对齐；2、按照处理器位数对齐。比如32位处理器就是4字节对齐，对于6个字节的对象，后面就填充两个字节，对其到8字节。填充字节可以加速对slab中对象的访问，相当于拿空间换时间吧，毕竟现在硬件的性能逐步提升，内存容量也是指数级增加。
管理数据可以位于slab的起始位置，也可以位于堆空间。首先是一个slab结构，结构后面是一个管理数组，每个数组项对应一个slab对象，slab结构如下所示：
struct slab { union { struct { struct list_head list; unsigned long colouroff; //slab第一个对象的偏移 void *s_mem; /* including colour offset 第一个对象的地址*/ unsigned int inuse; /* num of objs active in slab 被使用对象的数目*/ kmem_bufctl_t free;//下一个空闲对象的下标 unsigned short nodeid;///用于寻址具体CPU高速缓存 }; struct slab_rcu __slab_cover_slab_rcu; }; };
slab结构位于slab起始处，在slab结构之后，是一个kmem_bufctl_t数组，用以跟踪slab对象的使用情况。大致结构如下：
在上述结构中可以看到，slab结构中的free表示下一个可用的对象索引，按照图中所示，下一个可用的索引是3，那么当这个对象分配之后，需要充值free，这里就是取kmem_buctl_t[3]的值作为下一个可用的索引。上图描述的是管理数据部分和对象部分在一块内存上的情形。而当管理数据部分和对象部分不再一块内存的情形，原理根上面是一致的，由slab结构中的s_mem指针指向对象存储区。当slab对象的大小超过八分之一个页，就采用后者的方式建立缓存。否则，使用同一块内存区。
1.2 slab存在的问题
大家可能能够注意到slab结构中有个color字段，字面意思是着色，实际上就是一个偏移。此字段的意义是啥呢？前面已经提到，一个cache可能由多个slab组成，由于slab的分配都是页对齐的，而CPU的缓存行一般都是根据低地址寻址，即不同slab上的相同索引的对象会被映射到同一个缓存行。这样就容易造成某个固定位置的缓存行被过渡使用，而某些位置的确很新。于硬件保养很不利。当然，最大的原因还是发生冲突就需要更新缓存行，对于缓存行的利用率比较低下，从而造成效率的低下。为了解决这一问题，就有了上面着色的概念，即在每个slab的最开始随机放一个偏移量，这样就可以让容易发生冲突的缓存行映射到不同的地方。提到缓存行的利用率，如下图所示。然而在服务器系统中，即使加上偏移，经过一个循环，就再次发生冲突，所以着色并不能解决根本问题，只能相对减少这种影响，这也是slab的本质问题
对小内存块的管理请参考下篇博文，下篇文章将重点介绍小内存块的分配并结合代码描述SLAB的具体实现
参考资料：
1、http://www.secretmango.com/jimb/Whitepapers/slabs/slab.html
2、LInux 3.10.1源代码
原文：http://www.cnblogs.com/ck1020/p/6433560.html