Chinaunix

标题: BiscuitOS 技术分享[请勿回复] [打印本页]

作者: Buddy_Zhang1 时间: 2016-03-30 10:17
标题: 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-03-30 10:21
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[30] = { 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[i],&root);
return;
}
node->num = value[i];
/* 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[4],&root);
mm_debug("Second Check [%d]\n",value[4]);
print_all(&root);
/* Search a node */
node = search(value[2],&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[i],&root);
mm_debug("Last Check\n");
print_all(&root);
}

复制代码

作者: Buddy_Zhang1 时间: 2016-03-30 19:36
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[1 << PA_HASH_ORDER]
内核通过 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] = 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[i]);
/* 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[i];
/* Initialize the hash node */
INIT_HLIST_NODE(&node->node);
/* Get the hash head for node */
head = &phash[hash_32(node->num,HEAD_NUM)];
/* 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[i]))
hlist_for_each_entry(node,hnode,&phash[i],node)
mm_debug("%d->",node->num);
mm_debug("NULL\n");
}
/* Search data in hash list */
k = value[34];
head = &phash[hash_32(k,HEAD_NUM)];
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[i])) {
node = hlist_entry(phash[i].first,struct node,node);
hlist_del(&node->node);
kfree(node);
}
/* Final check */
for(i = 0 ; i < (1 << HEAD_NUM) ; i++) {
if(!hlist_empty(&phash[i])) {
mm_debug("HEAD %d REMAIN:",i);
hlist_for_each_entry(node,hnode,&phash[i],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[i])) {
node = hlist_entry(phash[i].first,struct node,node);
hlist_del(phash[i].first);
kfree(node);
}
kfree(phash);
kfree(value);
}

复制代码

作者: Buddy_Zhang1 时间: 2016-03-31 08:32
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_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) \
      )

作者: Buddy_Zhang1 时间: 2016-04-01 08:23
本帖最后由 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.

作者: Buddy_Zhang1 时间: 2016-04-02 10:53
本帖最后由 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);

作者: 我爱你我的菜 时间: 2016-04-14 16:15
这个东西我想参与，但不知道如何入手

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)