全部博文（94）
分类： LINUX
2011-09-21 07:38:06
这里不得不说linux内存缓冲管理。因为进程运行时经常会用到一些缓冲区，比如建立进程增加task_struct 结构，而当进程撤销时释放进程的task_struct 结构。和页内存管理不同，页内存管理是静态的阵列；而此为动态的。在情景分析中说如果使用像用户空间那样动态分配，从统一的存储空间堆中需要多少就切多少。
缺点许改进：
1、容易产生碎片，所以一般都按2^n大小来分配空间。
2、都要进行初始化
3、在有告诉缓存的情况下，那些缓冲区的组织和管理直接影响到高速缓存的命中。若使用最先符合的方法，那么当一个片段不能满足，那么就去下一个片段，由于在不同的页面，所以每次都不能命中
4、不适合多处理器公用内存的情况
引入slab
typedef struct slab_s{
struct list_head list;/*list将以快slab列入一个专用缓冲区队列*/
unsigned long colouroff;/*本slab上着色区的大小*/
void *s_mem;/*指针s_mem指向对象区的起点*/
unsigned int inuse;/*分配对象的计数器*/
keme_bufctl_t free;/*指向了空闲链中的第一个对象,typedef unsigned int kmem_buff_t;*/
}slab_t;
在空闲对象的连接数组中，链内对象所对应的元素值是下一个对象的序号，最后一个对象的元素值是BUFCTL_END.
slab_t身记录对象信息，但是也在某一个专用缓冲队列中.
为每种对象建立的slab队列都有个对头，结构为kmem_cache_t。该结构有维持slab队列的 各种指针，也有队列中每个slab的各种参数，以及函数指针,constructor和拆除函数dectrctor).
每种对象的slab对象的对头也是一个kemem_cache_t结构，成为cache_cache。
struct kmem_cache_s{
struct list_head slabs;/*其中存储着slab队列*/
struct list_head *firstnotfull;/*第一个没有满的slab队列*/
unsigned int objsize;/*原始数据结构大小sizeof(struct sk_buff)*/
unsigned int flags;
unsigned int num;/*表示每个slab上有几个缓冲区*/
spinlock_t spinlock;
#ifdef CONFIG_SMP
unsigned int batchcount;
#endif
unsigned int gfporder;/*表示每个slab的大小,每个slab都是由2^n页面构成，gfporder 是n*/
unsigned int gfpflags;
size_t colour;/*每个slab队列都要计算出它的颜色数量，colour为颜色的数量*/
unsigned int colour_off;/*颜色偏移值*/
unsigned int colour_next;/*保存下一个slab要用的颜色值,colour_next到达0时，就重新开始*/
kmem_cache_t *slab_cache;
unsigned int growing;
unsigned int dflags;
void (*ctor)(void *, kmem_cache_t *, unsigned long);
void (*dtor)(void *, kmem_cache_t, unsigned long);
unsigned long failures;
char name[CACHE_NAMELEN];
struct list_head *next;
#ifdef CONFIG_SMP
cpucache_t *cpudata[NR_CPUS];
#endif
#if STATS
unsigned long num_active;
unsigned long num_allocations;
unsigned long high_mark;
unsigned long grown;
unsigned long reaped;
unsigned long error;
#ifdef CONFIG_SMP
atomic_t allochit;
atomic_t allocmiss;
atomic_t freehit;
atomic_t freemiss;
#endif
#endif
};
typedef struct kmem_cache_s kmem_cache_t;
此形成一个层次式的树形结构:
cache_cache是一个kmem_cache_t结构，维持第一层的slab队列，这些slab上的对象都是kmem_cache_t数据结构。
每个第一层的slab即kmem_cache_t也是队头，维持第二层的slab队列。
第二层slab队列都为某种对象，即数据结构专用的。
第二层的slab队列上维持着一个空闲对象队列。
如图: linux内核情景分析 P142.
从通用缓冲池分配和释放缓冲区的函数是
void *kmalloc(size_t size, int flags);
void kfree(const void * objp);
分配一个不具有专用slab队列的数据结构而不需分配整个页面就用kmalloc()分配。
void * vmalloc(unsigned long size);
void vfree(void *addr);
函数vmalloc是从内核虚拟空间(3GB+HIGH以上)分配一个虚存及相应物理内存，类似brk()。brk()是在用户空间启动并从用户空间分配，而vmalloc是内核空间的。
分配kmem_cache_t结构以后，kmem_cache_create()进行一系列的计算，确定最佳的slab构成。
slab对象的分配和回收－他山篇
slab对象的分配和回收kmem_bufctl_t的用法。slab缓存的内存布局，slab缓存分为两部分.－部分是用于管理slab对象，另一部分是slab对象本身。
1、slab对象和管理slab对象的缓存一起存放。
2、分开存放
对于管理区分为两部分，一部分描述slab的数据结构，struct slab,令一部分用于描述slab对象的offset的一个数组，叫做kmem_bufctl_t
管理区：slab struct | kmem_bufctl_t array
KMEM_BUFCTL_S结构
typedef struct kmem_bufctl_s{
union {
struct kmem_bufctl_s *buf_nextp;/*用于空闲对象*/
kmem_slab_t *buf_slabp;/*用于活动的不规整对象保存slab块的指针*/
void * buf_objp; /*用于活动的规整对象，保存该对象的地址*/
}u;
}kmem_bufctl_t;
KMEM_SLAB_T结构
typedef struct kmem_slab_s{
struct kmem_bufctl_s *s_freep; //指向第一个空闲对象*/
struct kmem_bufctl_s *s_index;//指向规整对象链表*/
unsigned long s_magic:/*判断该slab有没有被销毁*/
unsigned long s_inuse; /*活动对象的数目*/
struct kmem_slab_s *s_nextp; /*用于指向双向链表*/
struct kmem_slab_s *s_prevp;
void *s_mem;/*该块中第一个对象地址*/
unsigned long s_offset: SLAB_OFFSET_BITS,/*16,用于地址对齐*/
s_dma : 1 //是否用于dma操作*/
}kmem_slab_t／*这个有点争议，貌似不是2.4内核
专用缓冲区队列建立.
void __init skb_init(void)
{
int i;
skbuff_head_cache = kmem_cache(“skbbuff_head_cache”, sizeof(struct sk_buff), 0, SLAB_HWCACHE_ALAIN, skb_headerinit, NULL);
if (! skbuff_head_cache)
panic(“Can't create skbuff cache”);
for ( i = 0; i< NR_CPUS, i++)
skb_queue_head_init(&skb_head_pool[i].list);
}/*此处举例为网络驱动子系统建立一个sk_buff结构队列
缓冲区的分配和释放
建立了一种缓冲区专用缓冲队列以后，用kmem_cache_alloc()来分配缓冲区。
struct sk_buff *alloc_skb(unsigned int size, int gfp_mask)
{
..........
skb = skb_head_from_pool();/*在缓冲池中找*/
if (skb == NULL){
skb = kmem_cache_alloc(skbuff_head_cache, gfp_mask);如果没有就分配-------------------------------->其中的skbuff_head_cache是全局变量，指向相应的slab队列*/
if (skb == NULL)
goto nohead;
}
. . .
}
alloc_skb()是驱动程序对kmem_cache_alloc的包装，建立自己的缓冲管理机制，包括一个sk_buff结构的缓冲池。
要分配一个sk_buff的数据结构，要通过skb_head_from_pool()来试缓冲池。
alloc_skb()>kmem_cache_alloc()
void *kmem_cache_alloc(kmem_cache_t *cachep, int flags) /*其中的skbuff_head是全局变量，指向相应的slab队列*/
{
return __ kmem_cache_alloc(cachep, flags);
}
alloc_skb()>kmem_cache_alloc()>__kmem_cache_alloc()
static inline void *__kmem_cache_alloc(kmem_cache_t *cachep, int flags)
{
unsigned long save_flags;
void * objp;
kmem_cache_alloc_head(cachep, flags);/*空函数*/
try_again:
local_irq_save(save_flags);
#ifdef CONFIG_SMP
...
#else
objp = kmem_cache_alloc_one(cachep);/*此为一个宏定义*/
#endif
local_irq_restore(save_flags);
return objp;
alloc_new_slab:
#ifdef CONFIG_SMP
......
#endif
local_irq_restore(save_flags);
if (kmem_cache_grow(cachep, flags))
goto try_again;
retrun NULL;
}
#define kmem_cache_alloc_one(cachep) \
({ \
slab_t *slab; \
{ \
struct list_head *p = cachep->firstnotfull; \ \*找到slab队列头中的指针,firstnotfull,找到队列中第一个空闲对象slab.
if (p == &cachep->slabs) \ /*如果指针指向slab队列的链头，那么说明队列中没有空闲对象*/
goto alloc_new_slab; \/*扩充slab队列*/
slabp = list_entry(p, slab_t, list); \
} \
kmem_cache_alloc_one_tail(cachep, slabp);/*如果找到了含有空闲对象的slab队列，那么就分配一个空闲对象并返回其指针-------------------------------->。
})
alloc_skb()> kmem_cache_alloc()>__kmem_cache_alloc()>kmem_cache_alloc_one_tail()
static inline void *kmem_cache_alloc_one_tail(kmem_cache_t *cachep, slab_t *slabp)
{
void *objp;
STATS_INC_ALLOCED(cachep);
STATS_INC_ATCTIVE(cachep);
STATS_SET_HIGH(cachep);
slabp->inuse ++;
objp = slab->s_mem + slabp->free * cachep->objsize;
if (slabp->free == BUFCTL_END)
cachep->firstnotfull = slab->list.next;
#if DEBUG
.....
#endif
return objp;
}
/*slab_t结构中记录着下一次可以分配的空闲对象的序号，s_mem指向slab中的对象区，根据这些数据可以计算出空闲对象的起始地址。然后通过宏操作slab_bufctl()改变字段的free的值，使它指明下一个空闲对象的序号*/
#define slab_bufctl(slabp) \
((kmem_bufctl_t *)(((slab_t *)slap ) + 1)) /*此返回一个kmem_bufctl_t数组的地址，数组就在slab中数据结构slab_t的上方，紧挨着数据结构slab_t。该数组以当前对象的序号为下标，而元素的值表明下一个空闲对象的序号。改变了slab_t的free字段值，隐含了该对象被分配*/
假设slab队列中已经没有了含有空闲对象的slab，所以要转到前面代码中的标号alloc_new_slab处，通过kmem_cache_grow()来分配一块新的slab,使缓冲区队列生长起来。
alloc_skb()>kmem_cache_alloc()>__kmem_cache_alloc()>kmem_cache_grow()
static int kmem_cache_grow(kmem_cache_t *cachep, int flags)
{
slab_t * slabp;
struct page *page;
void *objp;
size_t offset;
unsigned long offset;
unsigned int i , local, flags;
unsigned long ctor_flags;
unsigned long save_flags;
if (flags & ~(SLAB_DMA| SLAB_LEVEL_MASK | SLAB_NO_GROW))
BUG();
if (flags & SLAB_NO_GROW)
return 0;
if (in_interrupt() && (flags &SLAB_LEVEL_MASK) != SLAB_ATOMIC)
BUG();
ctor_flags = SLAB_CTOR_CONSTRUCTOR;
local_flags = (flags & SLAB_LEVEL_MASK);
if (local_flags == SLAB_ATOMIC)
ctor_flags | = SLAB_CTOR_ATOMIC;
offset = cachep->colour_next;
cachep->colour_next++;
if (cachep->colour_next >= cachep->colour)
cachep->colour_next = 0;
offset *= cachep->colour_off;
cachep->dflags |= DFLAGS_GROWN;
cachep->growing ++;
spin_unlock_irqrestore(&cachep->spinlock, save_flags);
if (!(objp = keme_getpage(cachep, flags)))
goto failed;
if (! (slabp = kmem_cache_slabmgme(cachep, objp, offset, local_flags)))
goto oppsl;
i = 1<< cachep->gfporder;
page = virt_to_page(objp);
do {
SET_PAGE_CACHE(page, cachep);
SET_PAGE_SLAB(page, slabp);
PageSetSlab(page);
page ++;
}while(--i);
kmem_cache_init_objs(cachep, slabp, ctor_flags);
spin_lock_irqsave(&cachep->spinlock, save, flags);
cache->growing --;
list_add_tail(&slab->list, &cache->slabs);
if (cachep->firstnotfull == &cache->list;
STATS_INC_GROWN(slabp);
cachep->failures = 0;
spin_unlock_irqrestore(&cache->spinlock, save_flags);
return 1;
opps1:
kmem_freepages(cachep, objp);
failed :
spin_lock_irqrestore(&cachep->spinlock, save_flags);
cacbe->growing --;
spin_unlock_irqrestore(&cache->spinlock, save_flags);
return 0;
}
/*此处讲讲list_add()函数*/
list_add(new, head);/*将当前节点添入链表*/
list_add是构建双向链表的过程
static __inline__ void list_add(struct list_head *new, struct list_head *head){
__list_add(new, head, head->next);
}
static __inline__ void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next){
next->prev = new;
new->next = next;
new->prev = prev;
prev ->next = new;
}
对链表插入操作有两种：在表头插入或从表尾插入。linux提供两个接口：
static inline void list_add(struct list_head *new, struct list_head *head);
static inline void list_add_tail(struct list_head *new, struct list_head *head);
分别调用__list_add(new, head, head->next);__list_add_tail(new, head->prev, head);实现在插入在head之后还是在head->prev之后。
