BiscuitOS 技术分享[请勿回复]
本帖最后由 Buddy_Zhang1 于 2016-04-02 11:41 编辑本帖用于 BiscuitOS 的技术分享.
BiscuitOS 介绍: bbs.chinaunix.net/thread-4241956-1-1.html
本贴请勿回复,回复请到 bbs.chinaunix.net/thread-4241956-1-1.html
技术目录:
1. BiscuitOS 上轻松使用红黑树
2. BiscuitOS 上轻松使用哈希散列式
3. BiscuitOS 上构建 GFP_ZONE_TABLE
4. BiscuitOS - SLUB 分配器 slab page 大小计算方法
5. BiscuitOS中最大文件数计算方法: 这个东西我想参与，但不知道如何入手 本帖最后由 Buddy_Zhang1 于 2016-04-02 11:02 编辑
BiscuitOS / Linux 中最大文件数计算方法:
在文件系统中,涉及一个最大文件数,本帖重点讲述如何计算这个值.
VFS 在初始化过程中,从内核获得当前系统物理页的数量(默认一个物理页的大小为 4K).
一个 struct file 分配的 inode 和 dcache 的空间大概是 1K,内核规定 struct file 占用的内存不能超过总内存的 10%,
于是计算公式如下:
1. mempages 为系统物理页的数量,每个物理页默认为 4K.
2. PAGE_SIZE 为物理页的大小,那么:
"PAGE_SIZE / 1024"
上面表达式的含义为,因为一个 struct file 分配的 inode 和 dcache 空间大小为 1K,那么一个物理页就能存储 4 个 struct file.
3. 那么全部物理页可以存储的 struct file 为:
mempages * (PAGE_SIZE / 1024)
4. 由于内核规定,struct file 的内存空间只能为总内存的 10 %,所以最后文件数为:
(mempages * (PAGE_SIZE / 1024)) / 10
5. 系统默认最大的文件数为 NR_FILE,通过上面的计算,最后最大文件数结果为:
files_stat.max_files = max_t(unsigned long, n, NR_FILE); 本帖最后由 Buddy_Zhang1 于 2016-04-01 08:25 编辑
BiscuitOS - SLUB 分配器 slab page 大小计算方法
在 BiscuitOS / Linux 上使用 kmem_cache_create() 创建缓存时,需要根据分配的对象的大小从 Buddy 分配器中获得空闲页来组成 slab page.
例如:
struct kmem_cache *file_cachep = kmem_cache_create("File",sizeof(struct file),0,0,NULL);
内核通过 sizeof(struct file) 计算的值将从 Buddy 中获得的空闲页,然后将空闲页分成大小为 sizeof(struct file) 的 object.
储存这些 object 的 page 称为 slab page.本帖用于讨论一个 slab page 的大小.
内核根据 object 的 size 来计算 slab page 的大小,
1. 如果 object 的 size 很小,那么一个 slab page 就由一个 page 组成
2. 如果 object 的 size 很大,那么一个 slab page 可能有两个或多个 page 组成.
Slab page 的大小计算如下:
1. 在 slub 中一个 slab page 中规定最小的 object 数量为 slub_min_objects,其值可以为零,
当 slub_min_objects 为零的时候,内核根据 cpu 的数量来进行赋值,其计算公式如下:
slub_min_objects = 4 * (fls(nr_cpu_ids) + 1)
其中函数 fls() 的作用是求参数的最高位的位数,如
fls(00001100B) = 4
fls(00001000B) = 4
fls(00010000B) = 5
fls() 的作用类似于向下除的效果.
nr_cpu_ids 为系统 cpu 的个数.
于是我们可以得出以下结论:
(1) 在单 CPU 的体系中 slub_min_objects 为 8
(2) 在双 CPU 的体系中 slub_min_objects 为 12
(3) 在四 CPU 的体系中 slub_min_objects 为 16
2. 一个 slab page 最大 objects 数量为 max_objects,其计算如下:
max_objects = (PAGE_SIZE << slub_max_order) / size;
max_objects = min(min_objects,max_objects);
上述表达式中 slub_max_order 为 3,其含义为最大的 slab_page 为 2^3,也就是 一个最大的 slab_page 可由 8 page 构成.
size 为 object 的 size.
3. 获得上面两个值之后,内核进行 slab order 的计算,其过程如下:
(1) 对一个 page 构成的 slab page 进行检测,如果在这种情况下, objects 的数量大于 slab page 规定的最大 object 的数量
那么内核直接从 Buddy 分配器中获得最大 object 时的 page. 代码如下:
if ((PAGE_SIZE << min_order) / size > MAX_OBJS_PER_PAGE)
return get_order(size * MAX_OBJS_PER_PAGE) - 1;
(2) 内核计算 object 的 size 对应的最小 order,其计算如下:
order =fls(min_objects * size - 1) - PAGE_SHIFT;
通过上面对 min_objects 的计算,可以获得 object 的最小 order 如下表:
通过上面表的计算,我们可以看出不同的 object size 的 slab page 的最小 order 不同,由于 order 最小为 0,所以最最小 order 进行处理
order = max(min_order,fls(min_objects * size - 1) - PAGE_SHIFT);
(3) 获得最小 order 之后,就从最小 order 开始遍历,只要满足一个 slab page 中,浪费部分小于 1/16 就可以进行分配.因为 object size 大小不同,
而 page 则按 PAGE_SIZE 进行对齐,所以无法避免一定的浪费,但内核规定只要浪费不超过 1/16 就可以进行分配.所以代码如下:
for (order = max(min_order , fls(min_objects * size - 1) - PAGE_SHIFT) ; order <= max_order; order++) {
unsigned long slab_size = PAGE_SIZE << order;
if (slab_size < min_objects * size)
continue;
rem = slab_size % size;
if (rem <= slab_size / fract_leftover)
break;
}
(4) 通过上面的计算之后获得最小 slab page 的 order,接着就可以从 Buddy 中获得对应的 page 来构成 slab page. BiscuitOS 上构建 GFP_ZONE_TABLE
本贴主要讲述如何构建 BiscuitOS 或 Linux 上的 GFP_ZONE_TABLE 表.
当在内核中分配内存的时候,必须指定分配的标志,如:
kmalloc(size,gfp)
kmem_cache_alloc(cache,gfp)
内核通过 gfp 标志来判断从哪个区间分配内存,内核将物理内存按区间分配,在 Linux 中存在 ZONE_DMA,ZONE_NORMAL,ZONE_DMA32 和 ZONE_HIGHMEM 几个 zone.
每个 zone 管理各自内存,调用者只要使用 gfp 标志就可以从不同的 gfp 区间获得内存.
内核使用 gfp_zone(gfp) 函数来将 gfp 标志转换为对应的 zone.其实现如下:static inline enum zone_type gfp_zone(gfp_t flags)
{
enum zone_type z;
int bit = (int)(flags & GFP_ZONEMASK);
z = (GFP_ZONE_TABLE >> (bit * ZONES_SHIFT)) &
((1 << ZONES_SHIFT) - 1);
if(__builtin_constant_p(bit))
BUILD_BUG_ON((GFP_ZONE_BAD >> bit) & 1);
else {
#ifdef CONFIG_DEBUG_VM
BUG_ON((GFP_ZONE_BAD >> bit) & 1);
#endif
}
return z;
}
从上面代码实现过程中可以看出这个转换依赖 GFP_ZONE_TABLE 表.其定义如下:
#define GFP_ZONE_TABLE ( \
(ZONE_NORMAL << 0 * ZONES_SHIFT) \
| (OPT_ZONE_DMA << ___GFP_DMA * ZONES_SHIFT) \
| (OPT_ZONE_HIGHMEM << ___GFP_HIGHMEM * ZONES_SHIFT) \
| (OPT_ZONE_DMA32 << ___GFP_DMA32 * ZONES_SHIFT)\
| (ZONE_NORMAL << ___GFP_MOVABLE * ZONES_SHIFT) \
| (OPT_ZONE_DMA << (___GFP_MOVABLE | ___GFP_DMA) * ZONES_SHIFT)\
| (ZONE_MOVABLE << (___GFP_MOVABLE | ___GFP_HIGHMEM) * ZONES_SHIFT) \
| (OPT_ZONE_DMA32 << (___GFP_MOVABLE | ___GFP_DMA32) * ZONES_SHIFT) \
)
以及另外一个表 GFP_ZONE_BAD.
#define GFP_ZONE_BAD ( \
1 << (___GFP_DMA | ___GFP_HIGHMEM) \
| 1 << (___GFP_DMA | ___GFP_DMA32) \
| 1 << (___GFP_DMA32 | ___GFP_HIGHMEM) \
| 1 << (___GFP_DMA | ___GFP_DMA32 | ___GFP_HIGHMEM) \
| 1 << (___GFP_MOVABLE | ___GFP_HIGHMEM | ___GFP_DMA) \
| 1 << (___GFP_MOVABLE | ___GFP_DMA32 | ___GFP_DMA) \
| 1 << (___GFP_MOVABLE | ___GFP_DMA32 | ___GFP_HIGHMEM) \
| 1 << (___GFP_MOVABLE | ___GFP_DMA32 | ___GFP_DMA | ___GFP_HIGHMEM) \
)
内核是如何构建这两张表?本贴重点讲述内核如何构建这两张表.
首先内核将一个节点分作不同的管理区,每个管理区使用 struct zone 进行管理,内核在 zone 基本分为:
ZONE_DMA,ZONE_NORMAL,ZONE_DMA32 和 ZONE_HIGHMEM,每个管理区使用 gfp 标志表示为:
#define ___GFP_DMA 0x01u
#define ___GFP_HIGHMEM 0x02u
#define ___GFP_DMA32 0x04u
#define ___GFP_MOVABLE 0x08u
在 gfp 标志中低 3 位来表示内存从哪个 zone 获得,其掩码为:
#define GFP_ZONEMASK(__GFP_DMA | __GFP_HIGHMEM | __GFP_DMA32 | __GFP_MOVABLE)
内核规定 ___GFP_DMA,___GFP_HIGHMEM 和 ___GFP_DMA32 其两个或全部不能同时存在于 gfp 标志中.
四个标志排列组合后可以获得下表:
从上面的表很容易构建 GFP_ZONE_BAD,将所有错误情况或起来就行.
1. (___GFP_DMA | ___GFP_HIGHMEM)
2. (___GFP_DMA | ___GFP_DMA32)
3. (___GFP_DMA32 | ___GFP_HIGHMEM )
4. (___GFP_DMA32 | ___GFP_HIGHMEM | ___GFP_DMA)
5. (___GFP_DMA | ___GFP_HIGHMEM | ___GFP_MOVABLE )
6. (___GFP_DMA | ___GFP_DMA32 | ___GFP_MOVABLE)
7. (___GFP_DMA32 | ___GFP_HIGHMEM | ___GFP_MOVABLE)
8. (___GFP_DMA32 | ___GFP_DMA32 | ___GFP_HIGHMEM | ___GFP_MOVABLE)
将上面 8 种情况合成 BAD TABLE 如下:
#define GFP_ZONE_BAD ( \
1 << (___GFP_DMA | ___GFP_HIGHMEM) \
| 1 << (___GFP_DMA | ___GFP_DMA32) \
| 1 << (___GFP_DMA32 | ___GFP_HIGHMEM) \
| 1 << (___GFP_DMA | ___GFP_DMA32 | ___GFP_HIGHMEM) \
| 1 << (___GFP_MOVABLE | ___GFP_HIGHMEM | ___GFP_DMA) \
| 1 << (___GFP_MOVABLE | ___GFP_DMA32 | ___GFP_DMA) \
| 1 << (___GFP_MOVABLE | ___GFP_DMA32 | ___GFP_HIGHMEM) \
| 1 << (___GFP_MOVABLE | ___GFP_DMA32 | ___GFP_DMA | ___GFP_HIGHMEM) \
)
剩下的 8 种情况就是可以分配.分别为:
1.0
2. (___GFP_DMA)
3. (___GFP_HIGHMEM)
4. (___GFP_DMA32)
5. (___GFP_MOVABLE)
6. (___GFP_DMA | ___GFP_MOVABLE)
7. (___GFP_HIGHMEM | ___GFP_MOVABLE)
8. (___GFP_DMA32 | ___GFP_MOVABLE)
构建初期表为
\)
#define TABLE ( \
(1 << 0) \
|(1<<___GFP_DMA) \
|(1 <<___GFP_HIGHMEM) \
|(1 <<___GFP_DMA32) \
|(1 <<___GFP_MOVABLE) \
|(1 << ___GFP_DMA | ___GFP_MOVABLE) \
|(1 << ___GFP_HIGHMEM | ___GFP_MOVABLE) \
|(1 << ___GFP_DMA32 | ___GFP_MOVABLE) \
)将对应的 zone 填充进去,其中
OPT_ZONE_DMA 代表 ___GFP_NORMAL 或者 ___GFP_NORMAL
OPT_ZONE_HGIHMEM 代表 ___GFP_NORMAL 或者 ___GFP_HIGHMEM
OPT_ZONE_DMA32 代表 ___GFP_NORMAL 或者 ___GFP_DMA32
根据表的分析,可获得下面结论:
#define TABLE ( \
(ZONE_NORMAL << 0) \
|(OPT_ZONE_DMA <<___GFP_DMA) \
|(OPT_ZONE_HIGHMEM <<___GFP_HIGHMEM) \
|(OPT_ZONE_DMA32 <<___GFP_DMA32) \
|(ZONE_NORMAL <<___GFP_MOVABLE) \
|(OPT_ZONE_DMA << ___GFP_DMA | ___GFP_MOVABLE) \
|(ZONE_MOVABLE << ___GFP_HIGHMEM | ___GFP_MOVABLE) \
|(OPT_ZONE_DMA32 << ___GFP_DMA32 | ___GFP_MOVABLE) \
)
由于不同的平台会使用不同数量的 zone 管理区,常见的 zone 分配为 ZONE_NORMAL 和 ZONE_HIGHMEM 搭配.
于是内核将 TABLE 的位宽使用 ZONES_SHIFT 表示,如一个具有 ZONE_DMA,ZONE_DMA32,ZONE_NORMAL 和 ZONE_HIGHMEM 的平台
ZONES_SHIFT 为 2,表示 GFP_ZONE_TABLE 每个选项的位宽为 2.于是最终的表为:
#define GFP_ZONE_TABLE ( \
(ZONE_NORMAL << 0 * ZONES_SHIFT) \
| (OPT_ZONE_DMA << ___GFP_DMA * ZONES_SHIFT) \
| (OPT_ZONE_HIGHMEM << ___GFP_HIGHMEM * ZONES_SHIFT) \
| (OPT_ZONE_DMA32 << ___GFP_DMA32 * ZONES_SHIFT)\
| (ZONE_NORMAL << ___GFP_MOVABLE * ZONES_SHIFT) \
| (OPT_ZONE_DMA << (___GFP_MOVABLE | ___GFP_DMA) * ZONES_SHIFT)\
| (ZONE_MOVABLE << (___GFP_MOVABLE | ___GFP_HIGHMEM) * ZONES_SHIFT) \
| (OPT_ZONE_DMA32 << (___GFP_MOVABLE | ___GFP_DMA32) * ZONES_SHIFT) \
) BiscuitOS 上轻松使用哈希散列式
哈希散列式作为 Linux 内核重要的数据结构,负责 Linux 的基本运作,由于其高效的数据管理能力和实用性,
内核也将哈希散列式作为其基本数据结构.本楼重点介绍如何在 BiscuitOS 和 Linux 使用哈希散列式.
哈希散列式的实现方法多种多样,这里以拉链法做为介绍,至于理论部分可以自行查找.
哈希散列式在内核中比较典型的运用如 inode 和 dentry 的管理,pid 管理以及本楼例子 kmap() 分配的内存管理.
内核中 KMAP 的区域就是使用哈希散列式进行管理.
从 ZONE_HIGHMEM 中的 Buddy System 中获得一个空闲 page 之后,使用 hash_ptr(page,PA_HASH_ORDER) 获得哈希散列式的 key.
内核维护了一个哈希散列表头 page_address_htable
内核通过 page_slot(page) 可以获得 hash 表头,在通过内部的 list_head 进行遍历.
哈希散列式使用例子:
源码位于 /BiscuitOS/tools/TestCase_Hash.c#include "linux/kernel.h"
#include "linux/debug.h"
#include "linux/types.h"
#include "linux/slab.h"
#define HEAD_NUM 3
#define VALUE_NUM 100
struct node {
struct hlist_node node;
int num;
};
struct hlist_head *phash = NULL;
/*
* TestCase_Hash
*/
void TestCase_Hash(void)
{
int i,k;
struct hlist_node *hnode;
struct hlist_head *head;
struct node *node;
int *value;
/* Prepare test data */
value = (int *)kmalloc(sizeof(int) * VALUE_NUM,GFP_KERNEL);
for(i = 0 ; i < VALUE_NUM ; i++)
value = i;
/* Prepare hash head array */
phash = (struct hlist_head *)kmalloc(sizeof(struct hlist_head) *
(1 << HEAD_NUM) , GFP_KERNEL);
/* Initialize hash head */
for(i = 0 ; i < (1 << HEAD_NUM) ; i++)
INIT_HLIST_HEAD(&phash);
/* Create Test node */
for(i = 0 ; i < VALUE_NUM ; i++) {
node = (struct node *)kmalloc(sizeof(struct node),GFP_KERNEL);
if(!node) {
mm_err("No memory\n");
/* Never water memory */
goto bad_memory;
}
/* Prepare test data */
node->num = value;
/* Initialize the hash node */
INIT_HLIST_NODE(&node->node);
/* Get the hash head for node */
head = &phash;
/* Add node into hash list */
hlist_add_head(&node->node,head);
}
/* Trave all hash list */
for(i = 0 ; i < (1 << HEAD_NUM) ; i++) {
mm_debug("HEAD %d:",i);
if(!hlist_empty(&phash))
hlist_for_each_entry(node,hnode,&phash,node)
mm_debug("%d->",node->num);
mm_debug("NULL\n");
}
/* Search data in hash list */
k = value;
head = &phash;
mm_debug("Search %d in head %d\n",k,hash_32(k,HEAD_NUM));
if(!hlist_empty(head))
hlist_for_each_entry(node,hnode,head,node)
if(k == node->num)
mm_debug("Find the data %d\n",k);
/* Delete all node */
for(i = 0 ; i < (1 << HEAD_NUM) ; i++)
while(!hlist_empty(&phash)) {
node = hlist_entry(phash.first,struct node,node);
hlist_del(&node->node);
kfree(node);
}
/* Final check */
for(i = 0 ; i < (1 << HEAD_NUM) ; i++) {
if(!hlist_empty(&phash)) {
mm_debug("HEAD %d REMAIN:",i);
hlist_for_each_entry(node,hnode,&phash,node)
mm_debug("%d->",node->num);
mm_debug("NULL\n");
}
}
/* Free all and complete test */
kfree(phash);
kfree(value);
return;
bad_memory:
for(i = 0 ; i < (1 << HEAD_NUM) ; i++)
while(!hlist_empty(&phash)) {
node = hlist_entry(phash.first,struct node,node);
hlist_del(phash.first);
kfree(node);
}
kfree(phash);
kfree(value);
} BiscuitOS 上轻松使用红黑树
红黑树作为 Linux 内核重要的数据结构，负责 Linux 的基本运作，其重要程度和难易程度让人望而却步。
本节通过一个简单例子介绍红黑树在 BiscuitOS 以及 Linux 内核中的使用方法。
红黑树在 Linux 内核很多地方都有使用，比如进程调度的“完全公平调度”，虚拟空间对进程地址管理以及本章重点例子 vmalloc 内存区的管理。
红黑树由于其复杂的构成，这里不过多讲理论，本章侧重讲述如何使用红黑树。
1. 红黑树 API
rb_link_node 将红黑树节点插入到红黑树。
rb_insert_color 红黑树翻转颜色
rb_erase 从红黑树中移除一个节点
rb_first 获得红黑树的第一个节点
rb_next 获得红黑树节点的下一个节点
2. 红黑树在内核中的使用案例
VMALLOC 分配的虚拟地址通过红黑树进行管理，我们可以通过红黑树的 root 和虚拟地址大小来查找 VMALLOC 区的内容。
代码如下：(源码位置 /BiscuitOS/tools/TestCase_vmalloc.c) void TestCase_vmalloc(void)
{
unsigned int addr;
struct rb_node *node;
addr = vmalloc(PAGE_SIZE);
addr = vmalloc(PAGE_SIZE);
addr = vmalloc(PAGE_SIZE);
addr = vmalloc(PAGE_SIZE);
/* Trave all node */
for(node = rb_first(&vmap_area_root) ; node ; node = rb_next(node)) {
struct vmap_area *va;
struct vm_struct *area;
va = rb_entry(node,struct vmap_area,rb_node);
area = va->private;
printk(KERN_INFO "VA %p\n",(void *)(unsigned long)va->va_start);
}
vfree(addr);
}3. 红黑树的使用案例。
(源码位置 /BiscuitOS/tools/TestCase_RB_tree.c)#include "linux/kernel.h"
#include "linux/rbtree.h"
#include "linux/debug.h"
#include "linux/mm.h"
#include "linux/gfp.h"
#include "linux/slab.h"
struct node {
struct rb_node node;
int num;
};
/*
* Insert a node into RBtree.
*/
int insert(struct node *data,struct rb_root *root)
{
struct rb_node **link = &(root->rb_node);
struct rb_node *parent = NULL;
while(*link) {
struct node *node = container_of(*link,struct node,node);
parent = *link;
if(data->num < node->num)
link = &((*link)->rb_left);
else if(data->num > node->num)
link = &((*link)->rb_right);
else
return -1;
}
rb_link_node(&data->node,parent,link);
rb_insert_color(&data->node,root);
return 0;
}
/*
* Search a node from RBtree.
*/
struct node *search(int num,struct rb_root *root)
{
struct rb_node *node = root->rb_node;
while(node) {
struct node *data = container_of(node,struct node,node);
if(num < data->num)
node = node->rb_left;
else if(num > data->num)
node = node->rb_right;
else
return data;
}
return NULL;
}
/*
* Delete a node from RBtree.
*/
void delete(int num,struct rb_root *root)
{
struct node *node = search(num,root);
if(node) {
rb_erase(&node->node,root);
kfree(node);
} else
mm_err("%2d doesn't exits\n",num);
}
/*
* Print all node
*/
void print_all(struct rb_root *root)
{
struct rb_node *node;
for(node = rb_first(root) ; node ; node = rb_next(node))
mm_debug("%2d",rb_entry(node,struct node,node)->num);
mm_debug("\n");
}
/*
* TestCase_RB_user
*/
void TestCase_RB_user(void)
{
struct rb_root root = RB_ROOT;
struct node *node;
int num,i,ret;
int value = { 2, 84 , 43 , 11 , 7, 54 , 21 , 1, 2, 10 ,
34 , 5, 6, 45 , 76 , 0, 12 , 25 , 44 , 11 ,
99 , 65 , 38 , 91 , 35 , 16 ,93, 74 , 33 , 67 };
num = 30;
for(i = 0 ; i < num ; i++) {
node = (struct node *)kmalloc(sizeof(struct node),GFP_KERNEL);
if(!node) {
mm_err("No Memory\n");
/* Never Waste memory */
for(i-- ; i >= 0 ; i--)
delete(value,&root);
return;
}
node->num = value;
/* Insert node into RBtree */
ret = insert(node,&root);
if(ret < 0) {
mm_err("%2d has existed\n",node->num);
kfree(node);
}
}
mm_debug("First Check\n");
print_all(&root);
/* Delete a node */
delete(value,&root);
mm_debug("Second Check [%d]\n",value);
print_all(&root);
/* Search a node */
node = search(value,&root);
mm_debug("Find %d\n",node->num);
/* Get prev node */
mm_debug("Prev num is %d\n",
rb_entry(rb_prev(&node->node),struct node,node)->num);
/* Get next node */
mm_debug("Next num is %d\n",
rb_entry(rb_next(&node->node),struct node,node)->num);
/* The first node */
mm_debug("Min num is %d\n",
rb_entry(rb_first(&root),struct node,node)->num);
/* The last node */
mm_debug("Max num is %d\n",
rb_entry(rb_last(&root),struct node,node)->num);
/* Free All node */
for(i = 0 ; i < num ; i++)
delete(value,&root);
mm_debug("Last Check\n");
print_all(&root);
}
页:
[1]