伙伴算法的数据结构

伙伴系统的数据结构是free_area_struct: l struct free_area_struct{ l struct page *next; //双向链表指针，链 l //表每个成员是一个块的第一个物理页描述符 l struct page *prev; l unsigned int *map; //指向对应的位图 l unsigned long count;//链表元素个数 l }

数据结构的分析：free_area[0]到free_area[9]都是free_area_struct类型的结构，分别对应不同大小块的链表，并且分别对应一个位图。
位图的大小取决于系统物理页面的数量。第k项位图的每一位描述大小为2k的物理页的两个伙伴块的状态。如果位图的某一位为0，表示一对伙伴块中或者都忙或者都空闲；如果为1，肯定有一块为忙。当伙伴块都空闲时，内核把他们当作一个大小为2k+1的块来处理。例如，一个128mb的ram，可以分成32768个页，16384个大小为2个页的块，…，则free_area[0]的位图有16384位，free_area[1]的有8192位…

伙伴系统数据结构图
【图】

slab分配机制

为什么要提出slab机制l原因：
伙伴系统采用页作为基本内存区，适合于对大块内存的请求。但是如果请求内存的大小与分配给它的大小不匹配，容易产生内部碎片。 l

解决之道：
linux2.0采用的方法是：linux提供按几何分布的内存区大小，即建立了13个按几何分布的空闲内存链表，大小从32到131056字节。伙伴系统的调用，既为了获得额外所需的物理页以存放新的内存区，也为了释放不再包含内存区的物理页。
linux2.2起采用了slab分配模式
linux采用slab分配器模式管理内存区。它把内存区看作对象，对象有一组数据结构和构造、析构函数组成，但为提高效率，指向构造和析构函数的指针都为null。 slab分配器把对象分组放进高速缓存。每个高速缓存存放着同一种类型的对象。高速缓存被划分成多个slab，每个slab由一个或多个连续的物理页组成。这些页中包含已分配的对象，也包含空闲对象 linux中引入slab主要目的是减少对伙伴算法的调用次数

slab分配器的组成：
注意：这里的高速缓存不是cpu中的高速缓存。它实际存在于物理内存中，由于分配速度相对于伙伴系统比较快，称谓高速缓存。
【图】
实际上，缓冲区就是主存中的一片区域，把这片区域划分为多个块，每块就是一个slab，每个slab由一个或多个页面组成，每个slab中存放的就是对象

cache的数据结构l l
struct kmem_cache_s { l kmem_slab_t *c_freep;//指向第一个含有 l //空闲对象的slab的指针 l
unsigned long c_flags; //描述cache静态特性的标志，例如slab（object）描述符的 存储位置，外部存储还是内部存储 l
unsigned long c_offset; //cache中对象的大 小（如果要求对象的起始地址必须是在 l //内存对齐，就可以对这个大小取整）

lunsigned long c_magic; //从一组预先定义好的数值中选出的一个魔数，用于检查高速缓存的当前状态和一致性
lunsigned long c_inuse; /* kept at zero */ lkmem_slab_t *c_firstp; //slab链表表头 lkmem_slab_t *c_lastp; //slab链表表尾
lspinlock_t c_spinlock;//多个处理器同时访问cache 时起保护作用的旋转锁 lunsigned long c_growing; lunsigned long c_dflags;//描述cache动态特性的标志，例如内核是否正在为cache分配新的slab

size_t c_org_size; lunsigned long c_gfporder;//每个slab包含的连续页面数目为2c_gfporder个 lvoid (*c_ctor)(void *, kmem_cache_t *, unsigned long); //构造函数 lvoid (*c_dtor)(void*, kmem_cache_t*, unsigned long); //析构函数 lunsigned long c_align; //对象的对齐因子 lsize_t c_colour; /* cache colouring range */ lsize_t c_colour_next;/* cache colouring */

unsigned long c_failures; lconst char *c_name; //cache名 lstruct kmem_cache_s *c_nextp; l //指向下一个cache l kmem_cache_t *c_index_cachep; l //指向外部对象描述符所在的高速缓存 l //的高速缓存描述符 l};

高速缓存分为两种类型：通用和专用。前者只由slab分配器用于自己使用，后者由内核其余部分使用。 l 通用高速缓存是： l （1）第一个高速缓存包含由内核使用的其余高速缓存的高速缓存描述符。cache_cache变量包含第一个高速缓存的描述符。 l （2）第二个高速缓存包含没有存放在slab内的slab描述符。cache_slabp变量指向第二个高速缓存描述符。

（3）13个高速缓存包含几何分布的内存区。cache_sizes数组元素分别指向13个高速缓存描述符，与其相关的内存区大小为32，64，…，131072字节。 l 系统初始化时调用kmem_cache_init和kmem_cache_sizes_init建立通用高速缓存，调用kmem_cache_create创建专用高速缓存。

slab的数据结构
typedef struct kmem_slab_s { struct kmem_bufctl_s *s_freep; //指向slab //中第一个空闲对象的指针 struct kmem_bufctl_s *s_index;//指向外 //部对象描述符所在的内存区 unsigned long s_magic; unsigned long s_inuse;//slab中当前分配 //的对象数目 struct kmem_slab_s *s_nextp;//指向同一 //个cache中与该slab相邻的两个slab的指针 struct kmem_slab_s *s_prevp;//构成双向链表

l unsigned long _offset:slab_offset_bits, l s_dma:1; l} kmem_slab_t;

对象的数据结构l对象数据结构如下： ltypedef struct kmem_bufctl_s { l union { l struct kmem_bufctl_s *buf_nextp; l //指向下一个空闲对象 l kmem_slab_t *buf_slabp; //对象被分配， l //且对象描述符在外面，指向对象所在的 l //slab的slab描述符 l void * buf_objp; //对象被分配，且对象描 l //述符在外面，则指向该对象 l } u; l} kmem_bufctl_t;

对象描述符可以存放在slab内部，紧接描述符所描述的对象之后； 如果存放在slab之外，存放在由cache_sizes指向的一个通用高速缓存中。对象本身所在的高速缓存，通过cache的c_index_cachep和slab的s_index两个域被连到它们的描述符所在的高速缓存。

slab分配器所管理的对象可以在内存对齐，也就是说，存放它们的起始物理地址是一个给定常数的倍数，这个常数叫做对齐因子，存放在cache的c_align域中。 存放对象大小的c_offset域要考虑增加填充字节数来对齐。如果对象大小大于高速缓存行的一半，就在ram中把这个对象的大小对齐到ll_cache_bytes的倍数，也就是行的开始。否则，这个对象的大小就是ll_cache_bytes的因子取整。

slab着色的产生背景：由于相同大小的对象很可能存放于高速缓存的相同的偏移量处，在不同slab内具有相同偏移量的对象最终可能映射在同一高速缓存行中。slab分配器使用slab着色的策略解决这个问题。 slab分配器利用空闲未用的字节来对slab着色，可用颜色个数为空闲字节数/c_align+1。

如果用颜色col对一个slab着色，那末，第一个对象偏移量（相对于slab起始地址）等于col*c_align。这个值存放在slab的s_offset域。
【图】

slab内存分配机制：
作用：分配内核内存（小内存）
几何分布的内存区大小
内碎片小于50%
32-131072 共13级
1． 所存放数据类型影响分配区
2． 内核函数倾向于反复请求同一类型内存区
3． 请求根据发生频率分类
4． 引入对象若不是按几何分布，可以用硬件高速缓存
5． 尽量限制使用伙伴系统

3种相关数据结构
slab_s 一个slab块的管理信息
list: slab链表
colouroff: 染色偏移
s_mem: 指向第一个对象
inuse: 活动的对象数（已分配）
free: 第一个空闲对象号

kmem_bufctl_t 其实就是unsigned int，形成数组，用于标识slab中的每个对象是否已用，并形成空闲对象链

kmeme_cache_s 缓存块管理信息
slabs
firstnotfull
objsize 对象大小
flags
num 一个slab中对象个数
spinlock
gfporder每个slab的页面数的对数
colour colour_off colour_next 染色相关变量
slabp_cache 对off slab方式使用，指乡向公共的cache_slabp,它存放每个slab的slab_t
构造，析构函数
name
next

结构：在cache_cache中分配，存放所有的cache，这些cache中，有cache_slabp，专门分配off slab模式的slab_t与kmem_bufctl_t数组，也有由cache_sizes指针数组所指向的一些通用cache，另有一些独立的专用cache
每个cache管理一组slab，每个slab管理一组对象，这些slab中的对象大小，个数，都相同，占用的空间也相同，只是存放的起示位置不同N[(_sBwjIYWIxRa [此资料转贴于学习网电脑课堂LINUX教程 ]http://www.Gzu521.ComN[(_sBwjIYWIxRa

两种方式：
on slab 小对象用，<512
偏移 | slab_t | kmem_bufctl_t数组 | 对象 | 剩余空间
off slab >=512 slab_t kmem_bufctl_t数组都由cache_slabp统一分配，于是，结构为
偏移 | 对象 | 剩余空间