freebsd9.2-UMA-相关数据结构
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_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;-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; /* Per cpu caches */
339 };
-与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;
-用来描述一个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; /* actual number bigger */
257 };-用来描述一个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; /* actual number bigger */
269 };-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_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,在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 }-链表的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);-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:/************************************************************************************************
* 当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; 高大上啊 有时间也好好拜读下 2022年再看这个文章 ,写得真好。用BSD的人多点就好了。
页:
[1]