
平台论坛博客文库

› 论坛 › 操作系统 › BSD › freebsd9.2-UMA-相关数据结构

[FreeBSD] freebsd9.2-UMA-相关数据结构 [复制链接]

71v5

家境小康

论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2014-07-23 16:43 |只看该作者 |倒序浏览

UMA(Universal Memory Allocator)即通用内存分配器或者叫做slab分配程序，是由Solaris首先实现的，下面通过Solaris中对slab分配程序的简要描述再结合
freebsd9.2中的相关数据结构及其源代码，看看freebsd9.2是如何实现slab分配程序的，关于Solaris中对slab分配程序的简要描述可以参考"Solaris内核
结构"这本书。

Solaris & Freebsd：
Solaris提供了一个通用的内存分配程序，该程序可以进行任意大小的内存分配，把这个分配程序叫做slab分配程序，这是因为它首先会消耗一些大的slab(内存片)
，然后再用每片内存的一部分来响应更小的分配请求。slab分配程序使用对象(object)来描述单个内存分配单元(比如，在freebsd中，分配一个进程描述符即
struct proc对象，单个内存分配单元此时就和进程描述符对应)，使用缓存(cache)用来指代许多相同对象组成的池(在freebsd中，和缓存对应的是uma zone)，使用
内存片(slab)来指代缓存中的一组对象，每一种对象类型都只有一个缓存，该缓存由一个或者多个slab组成。

freebsd9.2中相关的数据结构：

[下面两个数据结构实现了对象在每cpu上的高速缓存]：
/***************************************************************************************************
* 这个高速缓存不是cpu硬件缓存，而是一个bucket，bucket中保存了一些可以使用的对象，当分配
一个对象时，首先从bucket中获取，而不需要调用函数zone_alloc_item从更低一层来获取对象，
Solaris中的描述中，引入的这一层缓存可以避免两个thread同时从一个uma zone中获取对象时产生
的竞争条件，这个貌似不容易看出来，不过很明显的一个好处就是降低了响应时间。
<struct uma_bucket>-相当于一个bucket：
ub_link：用来将bucket链接到struct uma_zone对象的uz_full_bucket或者uz_free_bucket成员里。
ub_cnt：bucket中当前可以分配的对象的数目，同时也作为数组ub_bucket的索引，在分配对象时，
如果bucket非空，就简单的返回ub_bucket[ub_cnt]，同时递减ub_cnt。
ub_entries：在分配bucket时设置为固定的值，可以取的值为16，32，64，128。
ub_bucket：通用指针数组，在分配bucket时设置，数组ub_bucket中的元素指向所要分配的对象。
使用bucket前，由函数zone_alloc_bucket负责填充，同时递增ub_cnt。
<struct uma_cache>:
uc_freebucket：指向一个bucket，释放的对象被添加到该bucket中。
uc_allocbucket：指向一个bucket，当前分配的对象取自该bucket。
uc_allocs：当从相应缓存中分配一个对象时，递增该成员。
uc_frees：当释放一个对象到相应缓存中时，递增该成员。
uc_freebucket和uc_allocbucket指向的bucket取自相关联的struct uma_zone对象的uz_full_bucket或者
uz_free_bucket成员，在从缓存中分配对象时，uc_freebucket和uc_allocbucket可以swap。
********************************************************************/
175 struct uma_bucket {
176 LIST_ENTRY(uma_bucket) ub_link; /* Link into the zone */
177 int16_t ub_cnt; /* Count of free items. */
178 int16_t ub_entries; /* Max items. */
179 void *ub_bucket[]; /* actual allocation storage */
180 };
181
182 typedef struct uma_bucket * uma_bucket_t;
183
184 struct uma_cache {
185 uma_bucket_t uc_freebucket; /* Bucket we're freeing to */
186 uma_bucket_t uc_allocbucket; /* Bucket to allocate from */
187 u_int64_t uc_allocs; /* Count of allocations */
188 u_int64_t uc_frees; /* Count of frees */
189 } UMA_ALIGN;
190
191 typedef struct uma_cache * uma_cache_t;

复制代码

[struct uma_zone]-Universal Memory Allocator的最顶层数据结构，当创建一个uma zone时，就会分配一个类型为struct uma_zone的
对象来描述该uma zone：

/*********************************************************************************************
* Zone management structure
*
* 成员简要描述：
* uz_name：uma zone的name，创建uma zone时提供。
uz_link：用来将struct uma_zone对象链接到相关联的struct uma_keg对象的uk_zones成员里。
uz_full_bucket：链表中的bucket中装满了对象，可以用来响应对象的分配。
uz_free_bucket：链表中的bucket为空，释放的对象可以填充到该bucket中。
uz_kegs：链表的head，链接了与uma zone相关联的struct uma_keg对象。
uz_klink：用来将相关联的struct uma_heg对象链接到上面的成员uz_keg里。
uz_slab：获取slab的函数,通常情况下，指向函数zone_fetch_slab。
uz_ctor：指向一个构造函数，当从相应的uma zone获取到一个对象时，就要调用该构造函数
对已经获取的对象进行一些处理。
uz_dtor：指向一个析构函数，完成和uz_ctor相反的工作。
uz_init：指向一个函数，当从相应的uma zone获取到一个对象时，由该成员指向的函数
对已经获取的对象进行必要的初始化，可以通过函数uma_zone_set_zinit修改。
uz_fini：指向一个函数，完成和uz_init相反的工作，可以通过函数uma_zone_set_zfini修改。
uz_flags：相关标志。
uz_size：该uma zone中分配的对象的大小。
uz_allocs：一个计数器，对从uma zone中已经分配的对象进行计数。
uz_frees：一个计数器，对uma zone中的空闲对象进行计数。
uz_fails：如果分配slab失败，就递增该成员。
uz_sleeps：如果分配slab时需要睡眠，就递增该成员。
uz_fills：在填充bucket时使用该成员防止不必要的内存分配。
uz_count：函数bucket_alloc使用该成员选择一个合适的uma zone，该uma zone用来分配
struct uma_bucket对象。
uz_cpu：实现了要分配的对象在cpu上的缓存，系统中每个cpu在数组uz_cpu中都有对应的元素。
*********************************************/
307 struct uma_zone {
308 const char *uz_name; /* Text name of the zone */
309 struct mtx *uz_lock; /* Lock for the zone (keg's lock) */
310
311 LIST_ENTRY(uma_zone) uz_link; /* List of all zones in keg */
312 LIST_HEAD(,uma_bucket) uz_full_bucket; /* full buckets */
313 LIST_HEAD(,uma_bucket) uz_free_bucket; /* Buckets for frees */
314
315 LIST_HEAD(,uma_klink) uz_kegs; /* List of kegs. */
316 struct uma_klink uz_klink; /* klink for first keg. */
317
318 uma_slaballoc uz_slab; /* Allocate a slab from the backend. */
319 uma_ctor uz_ctor; /* Constructor for each allocation */
320 uma_dtor uz_dtor; /* Destructor */
321 uma_init uz_init; /* Initializer for each item */
322 uma_fini uz_fini; /* Discards memory */
323
324 u_int32_t uz_flags; /* Flags inherited from kegs */
325 u_int32_t uz_size; /* Size inherited from kegs */
326
327 u_int64_t uz_allocs UMA_ALIGN; /* Total number of allocations */
328 u_int64_t uz_frees; /* Total number of frees */
329 u_int64_t uz_fails; /* Total number of alloc failures */
330 u_int64_t uz_sleeps; /* Total number of alloc sleeps */
331 uint16_t uz_fills; /* Outstanding bucket fills */
332 uint16_t uz_count; /* Highest value ub_ptr can have */
333
334 /*
335 * This HAS to be the last item because we adjust the zone size
336 * based on NCPU and then allocate the space for the zones.
337 */
338 struct uma_cache uz_cpu[1]; /* Per cpu caches */
339 };

复制代码

[struct uma_keg]-与struct uma_zone对象相关联：

/***********************************************************************************************************
* Keg management structure
*
* 在freebsd9.2中，每一个struct uma_zone对象都有一个与之相关联的struct uma_keg对象，
一般情况下，struct uma_keg对象和struct uma_zone对象的关系为1:1；当使用uma_zsecond_create
函数创建一个uma zone时，这个关系就为1:n的关系。
uk_link：用来将struct uma_keg对象insert到链表uma_kegs中。
uk_hash：用来管理slab的哈希表。
uk_zones：链表的head，链接了和该struct uma_keg相关联的全部struct uma_zone对象。
uk_part_slab：链表的head，该链表上的slab包含了部分空闲的对象。
uk_free_slab：链表的head，该链表上的slab包含的对象全部空闲。
uk_full_slab：链表的head，该链表上的slab包含的对象都已经被分配。
uk_recurse：源代码中对该成员的解释为to prevent us from recursively trying to allocate buckets，
后面结合代码再看看。
uk_align：对齐掩码。
uk_pages：记录了已经分配给slab的页框数目。
uk_free：全部slab中空闲对象的数目。
uk_size：比如我们要创建一个分配struct proc对象的uma zone，那么成员uk_size就被设置为
sizeof(struct proc)。
uk_rsize：对成员uk_size进行了对齐操作后的值。
uk_maxpages：如果uma zone中没有空闲的slab，那么就要获取一个空闲的页框，此时就会比较uk_pages
和uk_maxpages，条件满足时就会睡眠，可以通过函数uma_zone_set_max修改。
uk_init：当分配一个slab时，uk_init对新分配的slab做一些初始化处理，通常情况下设置为zero_init，
可以通过函数uma_zone_set_init修改。
uk_fini：完成和uk_init相反的操作，通常情况下设置为NULL，可以通过函数uma_zone_set_fini修改。
uk_allocf：指向的函数用来获取页框，在UMA BOOT阶段，为startup_alloc，初始化完成后被设置为
通用的page_alloc函数，可以通过函数uma_zone_set_allocf修改。
uk_freef：指向的函数用来释放通过uk_allocf函数获取的页框，通常情况下为page_free函数。
可以通过函数uma_zone_set_freef修改。
uk_obj,uk_kva:当调用函数uma_zone_set_obj时，会设置这两个成员，同时会更新uk_allocf成员，将其
设置为ohj_alloc函数。
uk_slabzone：指向一个uma zone，该uma zone用来分配管理slab的数据结构即struct uma_slab对象或者
struct uma_slab_refcnt对象，只有当管理slab的struct uma_slab对象或者
struct uma_slab_refcnt对象没有内嵌在所分配的slab中时，该成员才有意义。
指向slabrefzone或者slabzone。
uk_pgoff：当描述slab的struct uma_slab对象或者struct uma_slab_refcnt对象内嵌在所分配
的slab中时，该成员保存一个偏移量，即slab = (uma_slab_t )(mem + keg->uk_pgoff);
在创建一个uma zone时，由构造函数keg_ctor设置。
uk_ppera：在调用uk_allocf指向的函数分配页框的，该成员指定了每次可以分配页框的数目。
uk_ipers：每个slab中包含的对象数目。
uk_flags：相关标志。
uk_ppera，uk_ipers，uk_rsize三个成员在创建uma zone时由函数keg_small_init或者keg_large_init
或者keg_cachespread_init根据对象的大小，浪费的空间大小等设置，同时更新uk_flags成员。
*******************************************************/
199 struct uma_keg {
200 LIST_ENTRY(uma_keg) uk_link; /* List of all kegs */
201
202 struct mtx uk_lock; /* Lock for the keg */
203 struct uma_hash uk_hash;
204
205 const char *uk_name; /* Name of creating zone. */
206 LIST_HEAD(,uma_zone) uk_zones; /* Keg's zones */
207 LIST_HEAD(,uma_slab) uk_part_slab; /* partially allocated slabs */
208 LIST_HEAD(,uma_slab) uk_free_slab; /* empty slab list */
209 LIST_HEAD(,uma_slab) uk_full_slab; /* full slabs */
210
211 u_int32_t uk_recurse; /* Allocation recursion count */
212 u_int32_t uk_align; /* Alignment mask */
213 u_int32_t uk_pages; /* Total page count */
214 u_int32_t uk_free; /* Count of items free in slabs */
215 u_int32_t uk_size; /* Requested size of each item */
216 u_int32_t uk_rsize; /* Real size of each item */
217 u_int32_t uk_maxpages; /* Maximum number of pages to alloc */
218
219 uma_init uk_init; /* Keg's init routine */
220 uma_fini uk_fini; /* Keg's fini routine */
221 uma_alloc uk_allocf; /* Allocation function */
222 uma_free uk_freef; /* Free routine */
223
224 struct vm_object *uk_obj; /* Zone specific object */
225 vm_offset_t uk_kva; /* Base kva for zones with objs */
226 uma_zone_t uk_slabzone; /* Slab zone backing us, if OFFPAGE */
227
228 u_int16_t uk_pgoff; /* Offset to uma_slab struct */
229 u_int16_t uk_ppera; /* pages per allocation from backend */
230 u_int16_t uk_ipers; /* Items per slab */
231 u_int32_t uk_flags; /* Internal flags */
232 };
233 typedef struct uma_keg * uma_keg_t;

复制代码

[struct uma_slab]-用来描述一个slab:

/***************************************************************************************
* The standard slab structure
在使用函数uma_zcreate创建一个uma zone时，如果没有设置UMA_ZONE_REFCNT标志，
就使用标准的struct uma_slab对象来描述slab。
us_head：内嵌的一个struct uma_slab_head对象。
us_freelist：可以看成一个类型为u_int8_t的数组，数组元素的值为slab中空闲对象的
索引，数组元素的数目为uk_ipers。
***********************************/
252 struct uma_slab {
253 struct uma_slab_head us_head; /* slab header data */
254 struct {
255 u_int8_t us_item;
256 } us_freelist[1]; /* actual number bigger */
257 };

复制代码

[struct uma_slab_refcnt]-用来描述一个slab：

/*********************************************************************************
* 创建分配网络子系统使用的mbuf对象的uma zone时使用。
在使用函数uma_zcreate创建一个uma zone时，如果设置UMA_ZONE_REFCNT标志，就使用
struct uma_slab_refcnt对象来描述slab。
us_head：内嵌的一个struct uma_slab_head对象。
us_freelist：和struct uma_slab对象中的us_freelist，只不过这里给slab中的每个
对象都添加了一个引用计数器。
***********************************/
263 struct uma_slab_refcnt {
264 struct uma_slab_head us_head; /* slab header data */
265 struct {
266 u_int8_t us_item;
267 u_int32_t us_refcnt;
268 } us_freelist[1]; /* actual number bigger */
269 };

复制代码

[struct uma_slab_head]-slab的head：

[struct uma_slab_head]-slab的head：
/***********************************************************************************
* us_keg：指向相关联的struct uma_keg对象。
联合us_type：
通常情况下使用_us_link成员将struct slab对象或者struct uma_slab_refcnt对象链接
到相关联的struct uma_keg对象中的uk_part_slab，uk_free_slab，uk_full_slab链表
中的一个；内核的mallc函数会使用_us_size成员。
us_hlink：用来将struct slab对象或者struct uma_slab_refcnt对象链接到哈希表上。
us_data：指向保存对象的起始内存地址。
us_flags：相关标志。
us_freecount：slab中空闲对象的数目。
us_firstfree：第一个空闲对象的索引，如下：
i = us_firstfree；
item = slab->us_data + (keg->uk_rsize * i);
item指向所请求的对象。
*********************************************/
238 struct uma_slab_head {
239 uma_keg_t us_keg; /* Keg we live in */
240 union {
241 LIST_ENTRY(uma_slab) _us_link; /* slabs in zone */
242 unsigned long _us_size; /* Size of allocation */
243 } us_type;
244 SLIST_ENTRY(uma_slab) us_hlink; /* Link for hash table */
245 u_int8_t *us_data; /* First item */
246 u_int8_t us_flags; /* Page flags see uma.h */
247 u_int8_t us_freecount; /* How many are free? */
248 u_int8_t us_firstfree; /* First free item index */
249 };

复制代码

[struct uma_hash]-管理struct uma_slab对象或者struct uma_slab_refcnt对象的哈希表，这样在释放一个对象
时，能够快速确定包含其的slab：

/**********************************************************************************
* uh_slab_hash：类型为struct slabhead的数组，数组元素数目为32(哈希表未扩展).
在创建uma zone时，从hashzone标识的uma zone中获取。
uh_hashsize：哈希表当前的大小。
uh_hashmask：值为uh_hashsize - 1。
*******************************************/
156 struct uma_hash {
157 struct slabhead *uh_slab_hash; /* Hash table for slabs */
158 int uh_hashsize; /* Current size of the hash table */
159 int uh_hashmask; /* Mask used during hashing */
160 };

复制代码

[可以把slab看成一个内存区，使用struct uma_slab或者struct uma_slab_refcnt描述slab，假设使用struct uma_slab描述slab]:
在freebsd9.2中，slab大小为一个页框(4KB)，在创建uma zone时，会根据uma zone中对象的大小，slab的大小，以及所浪费空间等结合
起来确定(1，每个slab中保存的对象数目；2，当uma zone中的slab为空时，调用uk_allocf指向的函数获取页框的数目；3，是将描述slab的
struct uma_slab对象内嵌在slab中，还是从slabzone标识的uma zone中单独获取一个struct uma_slab对象来描述slab等)。

[struct uma_slab内嵌在slab中，如下图所示]:

[单独分配struct uma_slab，在freebsd9.2中，称作"slab header is OFFPAGE"]：
从slabzone标识的uma zone中获取一个struct slab对象来描述slab，同时给相关联struct uma_keg对象的uk_flags成员设置相关标志，
在这种情况下，有两种方式管理struct slab对象(根据某个具体对象迅速获取描述其所在slab的struct slab对象)，哈希表和vtoslab，
我们先看一下哈希表(最常见的情况)，vtoslab后续再描述：
UMA_ZONE_OFFPAGE | UMA_ZONE_HASH // 哈希表
UMA_ZONE_OFFPAGE | UMA_ZONE_VTOSLAB // vtoslab

部分变量描述：
[相关的uma zone]：

/***************************************************************************
* masterkeg：和masterzone_k相关联的struct uma_keg对象。
masterzone_k：分配struct uma_keg对象的uma zone。
masterzone_z：分配struct uma_zone对象的uma zone。
slabzone：分配struct uma_slab对象的uma zone。
slabrefzone：分配struct uma_slab_refcnt对象的uma zone。
hashzone：分配哈希表的uma zone，即struct uma_keg对象的uk_hash成员。
上面的uma zone都是在函数uma_startup中初始化。
************************************************/
96 static struct uma_keg masterkeg;
97 static struct uma_zone masterzone_k;
98 static struct uma_zone masterzone_z;
99 static uma_zone_t kegs = &masterzone_k;
100 static uma_zone_t zones = &masterzone_z;
103 static uma_zone_t slabzone;
104 static uma_zone_t slabrefzone; /* With refcounters (for UMA_ZONE_REFCNT) */
110 static uma_zone_t hashzone;

复制代码

[变量bucketdisable相关]：

/******************************************************************************************
* uma_callout：
内核中用来描述等待事件的数据结构，比如我们可以用一个函数，事件被处理前的等待时间等数据
初始化一个struct callout对象，让后将其添加到合适的callout队列中，hardclock超时后会检查
相应的callout队列是否有等待事件需要被处理，如果有，就调用初始化struct callout对象
时用到的函数。在UMA BOOT阶段，uma_startup3函数会初始化uma_callout，并将其添加到合适的
callout队列中，等待时间为20s，回调函数为uma_timeout，这里可以将其简单的理解为每隔20s都
会执行uma_timeout函数，函数uma_timeout会调用bucket_enable函数。
bucketdisable：
值为1：当bucket用完时，禁止分配bucket。
值为0：当bucket用完时，可以分配bucket。
在系统正常运行后，pageout守护进程会根据当前空闲物理页框的数量更新cnt.v_free_min，
cnt.v_free_count，cnt.v_cache_count等计数器的值，所以vm_page_count_min函数的返回值
是动态变化的，意味着bucketdisable的值也是动态变化的。
通常情况下，调用uma_zalloc分配一个具体对象的时候，会经过bucket这一层，bucket这一层
相对比较独立，我们可以先绕过。
*********************************************************/
148 static struct callout uma_callout;
149 #define UMA_TIMEOUT 20 /* Seconds for callout interval. */
120 static int bucketdisable = 1;
267 static void
268 bucket_enable(void)
269 {
270 bucketdisable = vm_page_count_min();
271 }
144 static __inline
145 int
146 vm_page_count_min(void)
147 {
148 return (cnt.v_free_min > (cnt.v_free_count + cnt.v_cache_count));
149 }

复制代码

[uma_kegs]-链表的head，链接了系统中全部的struct uma_keg对象：

/********************************************************************************
* struct {
struct uma_keg * lh_first；
}uma_kegs = { NULL}；
******************************/
123 static LIST_HEAD(,uma_keg) uma_kegs = LIST_HEAD_INITIALIZER(uma_kegs);

复制代码

[booted]-Is the virtual memory done starting up?

/*****************************************************************
* uma_startup函数执行完后，booted的值为UMA_STARTUP。
uma_startu2函数执行完后，booted的值为UMA_STARTUP2。
这个值的主要用途是确定在UMA BOOT阶段，如何获取物理页框。
************************************/
136 static int booted = 0;
137 #define UMA_STARTUP 1
138 #define UMA_STARTUP2 2

复制代码

[uma_max_ipers & uma_max_ipers_ref]:

/************************************************************************************************
* 当struct uma_slab或者struct uma_slab_refcnt没有内嵌在slab中时：
uma_max_ipers：使用struct uma_lab描述slab时，每个slab可以保存的对象的最大数目。
uma_max_ipers_ref：使用struct uma_slab_refcnt描述slab时，每个slab可以保存的对象的最大数目。
这两个变量都在函数uma_startup中初始化。
***************************************************/
141 static u_int uma_max_ipers;
142 static u_int uma_max_ipers_ref;

复制代码