分类： LINUX
2011-11-07 11:24:44
我们知道对于物理内存的分配与回收，是先通过内存页面的管理，首先在虚存空间中分配一个虚存区间，然后根据需要为此区间建立起相应的映射并分配对应的物理页面。由于linux操作系统是多任务、多用户的，所以会有很多用户程序的执行与结束，如此频繁的进行内存分配与释放，势必造成许多小块闲散空间的产生，如何能利用起来？
linux采用了伙伴算法来解决问题。伙伴算法的主要思想是把所有闲散的页面分为10块用链表链接起来，每个链表的块中还有2的幂次方的页面。当我们需要一定数量的页面时，先从对应的链表中查找，如果存在就分配，不存載就继续向高一块查找是否有空闲，有的话分配出来，然后将剩余的空间插入到下面相应的链表。
物理页块的分配是通过函数__get_free_pages实现的。
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
{
struct page *page;
VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
page = alloc_pages(gfp_mask, order);
if (!page)
return 0;
return (unsigned long) page_address(page);
}
其参数gfp_mask:表示所分配内存的特殊要求。常用的标志为GFP_KERNEL和GFP_ATOMIC,前者表示在分配内存期间可以睡眠，用于进程；后者表示不可以睡眠，用于中断处理程序。 __get_free_pages() 返回值是个32位的地址。从上面函数可以看出来物理页面的分配实际上是通过alloc_pages进行分配完成的。
除了分配内存之外，还要确保剩余内存足以应对紧急情况的处理。
页块分配出去用完后要进行回收，linux使用free_pages进行页块回收。
void free_pages(unsigned long addr, unsigned int order)
{
if (addr != 0) {
VM_BUG_ON(!virt_addr_valid((void *)addr));
__free_pages(virt_to_page((void *)addr), order);
}
}
其中 VM_BUG_ON宏其实就是一个循环操作，宏定义如下：
#define VM_BUG_ON(cond) do { (void)(cond); } while (0)
而 virt_addr_valid则是对地址进行一系列判断，宏定义如下：
#define virt_addr_valid(kaddr) (((void *)(kaddr) >= (void *)PAGE_OFFSET) && ((void *)(kaddr) < (void*)memory_end))
当然真正其回收作用的就是__ __free_pages函数。
自此我们知道伙伴算法分配内存时，每次至少分配一个页面，当我们需要的内存少于一个页面时，或者更小的数据时，该如何做？Linux引入了slab分配模式。
slab的主要思想是对内核数据进行页面分配时，首先要对数据结构进行初始化，用完之后就要回收。这样不就在重复初始化上花费了很多时间，为了避免这种情况，slab并不会丢弃已分配的对象，而是释放后依然把他们保留在缓冲区中，以便以后请求分配同一对象时，就可以快速获得而免去了初始化。
slab 缓存分配器提供了很多优点。首先，内核通常依赖于对小对象的分配，它们会在系统生命周期内进行无数次分配。slab 缓存分配器通过对类似大小的对象进行缓存而提供这种功能，从而避免了常见的碎片问题。slab 分配器还支持通用对象的初始化，从而避免了为同一目而对一个对象重复进行初始化。最后，slab 分配器还可以支持硬件缓存对齐和着色，这允许不同缓存中的对象占用相同的缓存行，从而提高缓存的利用率并获得更好的性能。
Slab的构成如下图：
linux把缓冲区分为专用和通用，其中专用缓冲区主要用于频繁使用的数据结构，而通用缓冲区就主要用于开销不大的数据结构了。
Slab的API主要如下：
专用缓冲区：
缓冲区的创建通过kmem_cache_create()建立，其原型如下：
struct kmem_cache *kmem_cache_create( const char *name, size_t size, size_t offset,
unsigned long c_flags; void (*ctor)(void*, struct kmem_cache *, unsigned long), void (*dtor)(void*, struct kmem_cache *, unsigned long));其中name为缓冲区的名字，size为对象的大小，offset参数定义了每个对象必需的对齐。 c_flags 参数指定了为缓存启用的选项。其可能取值SLAB_HWCACHE_ALIGN表示与第一个缓冲区中的缓冲行边界对其；SLAB_NO_REAP表示允许系统回收内存；SLAB_CACHE_DMA表示使用的是DMA内存（DMA是直接存储器访问的缩写，他允许不同速度的硬件装置来沟通，而不需要依于 CPU 的大量 中断 负载）；最后两个函数分别是构造函数（用于对数据初始化）和析构函数（用于对数据回收处理）。其中数据结构kmem_cache是用来对缓冲区进行管理的。其数据结构如下：
struct kmem_cache {
53 /* 1) per-cpu data, touched during every alloc/free */
54 struct array_cache *array[NR_CPUS];
55 /* 2) Cache tunables. Protected by cache_chain_mutex */
56 unsigned int batchcount;
57 unsigned int limit;
58 unsigned int shared;
59
60 unsigned int buffer_size;
61 u32 reciprocal_buffer_size;
62 /* 3) touched by every alloc & free from the backend */
63
64 unsigned int flags; /* constant flags */
65 unsigned int num; /* # of objs per slab */
…...........
}
缓冲区的分配与释放函数分别如下：
kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags);
kmem_cache_free(struct kmem_cache *cachep, void *objp)
内核函数 kmem_cache_destroy 用来销毁缓存。这个调用是由内核模块在被卸载时执行的。在调用这个函数时，缓存必须为空。
void kmem_cache_destroy( struct kmem_cache *cachep );
通用缓冲区：
通用缓冲区中分配和释放缓冲区的函数为：
void *kmalloc(size_t,int flags );
void kfree(const void *objp);
当然还有其他函数来辅助slab完成任务。kmem_cache_size 函数会返回这个缓存所管理的对象的大小。您也可以通过调用 kmem_cache_name 来检索给定缓存的名称（在创建缓存时定义）。具体函数原型如下：
unsigned int kmem_cache_size( struct kmem_cache *cachep );
const char *kmem_cache_name( struct kmem_cache *cachep );
实现上述函数的内核模块
