BiscuitOS 系统发布【增加内核实践】

Buddy_Zhang1

BiscuitOS 是一个类 Linux 系统,其实现原理是在 Linux 用户空间分配一定的内存作为 Biscuit 的物理内存.基于 BiscuitOS 的物理内存构建一个操作系统,其实现原理继承 Linux 实现过程.

BiscuitOS 创作的主要目的:
          Linux 内核的学习是一个充满挑战又艰难的过程.对初学 Linux 内核来说,无数的理论以及无法将理论转化为实践的尴尬充斥着整个学习初期.
          这成为很多人无法翻越的大山.俗话说 "实践是检验真理的唯一标准".突然有一天有个想法,如何增加内核实践量,又不用搭建繁杂的开发环境,于是 BiscuitOS 就诞生了.
          BiscuitOS 是为想增加 Linux 内核实践,了解 Linux 内核实现原理的同学设计的操作系统,BiscuitOS 的实现过程完全使用 Linux 实现方法.

BiscuitOS 实现原理:
         BiscuitOS 是通过在用户空间申请两个 256M 的数组,然后将这两个数组当做虚拟物理内存.基于虚拟物理内存构建 BiscuitOS 的物理内存和虚拟内存.BiscuitOS 目前只具备内存管理功能,
         您可以在这个系统上了解 Linux 内存管理系统从内核启动到初始化,最后到一个完整的内存管理系统的整个过程,让你从源码 + 实践级别了解 Linux 内核.


BiscuitOS Feature:
  优点:
         1. BiscuitOS 的实现完全遵循 Linux 内核,在 BiscuitOS 实现的代码可以移植到 Linux.
         2. BiscuitOS 实现在 Linux 用户空间,快速编译内核,轻松测试您的代码.
         3. BiscuitOS 属于 Linux 用户空间程序,可以使用 gdb 等调试工具进行调试.
         4. BiscuitOS 经过一年的开发周期,丰富的测试用例供使用者使用.
         5. 用户可以随意修改代码,并且增加并贡献代码.
         6. BiscuitOS 增加了很多内核接口的使用例子,比如红黑树,buddy system 等使用案例,不仅可以增加您的内核开发经验,也可以降低内核学习的门槛.
         7. BiscuitOS 开发了很多 debug 工具,您可以直接看 BiscuitOS 的物理内存数据.
  缺点:
        1.  BiscuitOS 只是一个模拟器!其硬件模拟基于 ARMv7.
        2.  BiscuitOS 是一个正在开发的系统,第一个版本系统为 MemoryCookOS ,该系统只包含 Linux 内存管理部分.后续会将四大基本模块加载进来.
        3. 由于 BiscuitOS 是一个 32bit 的系统,但 Linux 用户空间是 64bit 系统.所以在源码中存在 64bit 转 32bit 的处理.
        4. 由于 BiscuitOS 是基于 "虚拟物理内存".所以代码中存在内存转换的代码.

BiscuitOS 下载地址:
          BiscuitOS_Debug 为一直开发的系统,目标将 Linux 四大模块 Merge 到这个系统中,有兴趣的同学可以加入一起开发:
                                        git@github.com:BiscuitOS/BiscuitOS_Debug.git
          BiscuitOS_Stable: 为经过调试基本可运行的稳定版 BiscuitOS.
                                        git@github.com:BiscuitOS/BiscuitOS_Stable.git
          MemoryCookOS: 为纯内存管理的 BiscuitOS.
                                        git@github.com:BiscuitOS/MemoryCookOS.git

BiscuitOS 使用方法:
          1. 通过 github 下载源码解压
          2. cd /BiscuitOS
          3. make
          BiscuitOS 的编程入口位于 /BiscuitOS/init/main.c 里面的 kernel_space()
          BiscuitOS 丰富的测试用例位于 /BiscuitOS/tools/TestCase_xxx.c

如何解决您的问题:
          1. 遇到编译报错的问题,请将 /BiscuitOS/obj/compiler.log 内容贴出来.
          2. 遇到运行时段错误问题,请将 /BiscuitOS/obj/a 文件邮件给我.
              FAQ 邮箱: buddy.zhang@aliyun.com

Buddy_Zhang1

BiscuitOS 开发介绍:
           BiscuitOS 博客:
                          blog.chinaunix.net/uid/30647659.html
           FAQ 邮箱:
                          buddy.zhang@aliyun.com
           BiscuitOS 论坛讨论:
                          ChinaUnix论坛 > 程序设计 > 内核源码
           BiscuitOS gitbub:
                          github.com/BiscuitOS


BiscuitOS  运行截图。

Buddy_Zhang1

BiscuitOS 开发进度:

- 2016.3.26
    -  vfs_caches_init() Merge

Buddy_Zhang1

BiscuitOS 应用实例

1. BiscuitOS 上轻松使用红黑树
2. BiscuitOS 上轻松使用哈希散列式
3. BiscuitOS 上构建 GFP_ZONE_TABLE
4. BiscuitOS - SLUB 分配器 slab page 大小计算方法
5. BiscuitOS / Linux 中最大文件数计算方法:

Buddy_Zhang1

回复 6# Godbach


    谢谢版主!

Buddy_Zhang1

回复 8# Godbach


    我实践过，在上面可以加入很多子系统，实践起来真的很爽，可以把自己很多想法都在上面验证。

    现在正在把 VFS 加入到里面。

Buddy_Zhang1

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)

1. void TestCase_vmalloc(void)
   
2. {
   
3.         unsigned int addr;
   
4.         struct rb_node *node;
   
5. 
   
6.         addr = vmalloc(PAGE_SIZE);
   
7. 
   
8.         addr = vmalloc(PAGE_SIZE);
   
9. 
   
10.         addr = vmalloc(PAGE_SIZE);
    
11.        
    
12.         addr = vmalloc(PAGE_SIZE);
    
13.        
    
14. 
    
15.         /* Trave all node */
    
16.         for(node = rb_first(&vmap_area_root) ; node ; node = rb_next(node)) {
    
17.                 struct vmap_area *va;
    
18.                 struct vm_struct *area;
    
19. 
    
20.                 va = rb_entry(node,struct vmap_area,rb_node);
    
21.                 area = va->private;
    
22.                 printk(KERN_INFO "VA %p\n",(void *)(unsigned long)va->va_start);
    
23.           }
    
24.        
    
25.         vfree(addr);
    
26. }

复制代码

3. 红黑树的使用案例。
(源码位置 /BiscuitOS/tools/TestCase_RB_tree.c)

1. #include "linux/kernel.h"
   
2. #include "linux/rbtree.h"
   
3. #include "linux/debug.h"
   
4. #include "linux/mm.h"
   
5. #include "linux/gfp.h"
   
6. #include "linux/slab.h"
   
7. 
   
8. struct node {
   
9.         struct rb_node node;
   
10.         int num;
    
11. };
    
12. 
    
13. 
    
14. /*
    
15. * Insert a node into RBtree.
    
16. */
    
17. int insert(struct node *data,struct rb_root *root)
    
18. {
    
19.         struct rb_node **link = &(root->rb_node);
    
20.         struct rb_node *parent = NULL;
    
21. 
    
22.         while(*link) {
    
23.                 struct node *node = container_of(*link,struct node,node);
    
24. 
    
25.                 parent = *link;
    
26.                 if(data->num < node->num)
    
27.                         link = &((*link)->rb_left);
    
28.                 else if(data->num > node->num)
    
29.                         link = &((*link)->rb_right);
    
30.                 else
    
31.                         return -1;
    
32.         }
    
33.         rb_link_node(&data->node,parent,link);
    
34.         rb_insert_color(&data->node,root);
    
35.         return 0;
    
36. }
    
37. 
    
38. /*
    
39. * Search a node from RBtree.
    
40. */
    
41. struct node *search(int num,struct rb_root *root)
    
42. {
    
43.         struct rb_node *node = root->rb_node;
    
44. 
    
45.         while(node) {
    
46.                 struct node *data = container_of(node,struct node,node);
    
47. 
    
48.                 if(num < data->num)
    
49.                         node = node->rb_left;
    
50.                 else if(num > data->num)
    
51.                         node = node->rb_right;
    
52.                 else
    
53.                         return data;
    
54.         }
    
55.         return NULL;
    
56. }
    
57. 
    
58. /*
    
59. * Delete a node from RBtree.
    
60. */
    
61. void delete(int num,struct rb_root *root)
    
62. {
    
63.         struct node *node = search(num,root);
    
64. 
    
65.         if(node) {
    
66.                 rb_erase(&node->node,root);
    
67.                 kfree(node);
    
68.         } else
    
69.                 mm_err("%2d doesn't exits\n",num);
    
70. }
    
71. 
    
72. /*
    
73. * Print all node
    
74. */
    
75. void print_all(struct rb_root *root)
    
76. {
    
77.         struct rb_node *node;
    
78. 
    
79.         for(node = rb_first(root) ; node ; node = rb_next(node))
    
80.                 mm_debug("%2d  ",rb_entry(node,struct node,node)->num);
    
81. 
    
82.         mm_debug("\n");
    
83. }
    
84. 
    
85. /*
    
86. * TestCase_RB_user
    
87. */
    
88. void TestCase_RB_user(void)
    
89. {
    
90.         struct rb_root root = RB_ROOT;
    
91.         struct node *node;
    
92.         int num,i,ret;
    
93.         int value[30] = { 2  , 84 , 43 , 11 , 7  , 54 , 21 , 1  , 2  , 10 ,
    
94.                           34 , 5  , 6  , 45 , 76 , 0  , 12 , 25 , 44 , 11 ,
    
95.                           99 , 65 , 38 , 91 , 35 , 16 ,93  , 74 , 33 , 67 };
    
96. 
    
97.         num = 30;
    
98. 
    
99.         for(i = 0 ; i < num ; i++) {
    
100.                 node = (struct node *)kmalloc(sizeof(struct node),GFP_KERNEL);
     
101.                 if(!node) {
     
102.                         mm_err("No Memory\n");
     
103. 
     
104.                         /* Never Waste memory */
     
105.                         for(i-- ; i >= 0 ; i--)
     
106.                                 delete(value[i],&root);
     
107. 
     
108.                         return;
     
109.                 }
     
110. 
     
111.                 node->num = value[i];
     
112. 
     
113.                 /* Insert node into RBtree */
     
114.                 ret = insert(node,&root);
     
115.                 if(ret < 0) {
     
116.                         mm_err("%2d has existed\n",node->num);
     
117.                         kfree(node);
     
118.                 }
     
119.         }
     
120. 
     
121.         mm_debug("First Check\n");
     
122.         print_all(&root);
     
123. 
     
124.         /* Delete a node */
     
125.         delete(value[4],&root);
     
126.         mm_debug("Second Check [%d]\n",value[4]);
     
127.         print_all(&root);
     
128. 
     
129.         /* Search a node */
     
130.         node = search(value[2],&root);
     
131.         mm_debug("Find %d\n",node->num);
     
132. 
     
133.     /* Get prev node */
     
134.         mm_debug("Prev num is %d\n",
     
135.                         rb_entry(rb_prev(&node->node),struct node,node)->num);
     
136.         /* Get next node */
     
137.         mm_debug("Next num is %d\n",
     
138.                         rb_entry(rb_next(&node->node),struct node,node)->num);
     
139.         /* The first node */
     
140.         mm_debug("Min num is %d\n",
     
141.                         rb_entry(rb_first(&root),struct node,node)->num);
     
142.         /* The last node */
     
143.         mm_debug("Max num is %d\n",
     
144.                         rb_entry(rb_last(&root),struct node,node)->num);
     
145. 
     
146.         /* Free All node */
     
147.         for(i = 0 ; i < num ; i++)
     
148.                 delete(value[i],&root);
     
149. 
     
150.         mm_debug("Last Check\n");
     
151.         print_all(&root);
     
152. }

复制代码

Buddy_Zhang1

回复 13# chinaandcompute


        HI:
         您好,我需要和您确认,您 gitbub 的版本是否为 MemoryCookOS?
        
         能否描述为什么注释掉 /linux/types.h 里面的 size_t.

         1. 能否将不却掉 size_t 的编译文件给我一下,编译文件位于 /obj/compiler.log
  
         2. 请将去掉 size_t 之后编译生成的 /obj/a 文件邮件发给我分析一下.谢谢
   
              邮箱-> buddy.zhang@aliyun.com
         

Buddy_Zhang1

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

1. #include "linux/kernel.h"
   
2. #include "linux/debug.h"
   
3. #include "linux/types.h"
   
4. #include "linux/slab.h"
   
5. 
   
6. #define HEAD_NUM    3
   
7. #define VALUE_NUM   100
   
8. 
   
9. struct node {
   
10.         struct hlist_node node;
    
11.         int num;
    
12. };
    
13. 
    
14. struct hlist_head *phash = NULL;
    
15. /*
    
16. * TestCase_Hash
    
17. */
    
18. void TestCase_Hash(void)
    
19. {
    
20.         int i,k;
    
21.         struct hlist_node *hnode;
    
22.         struct hlist_head *head;
    
23.         struct node *node;
    
24.         int *value;
    
25. 
    
26.         /* Prepare test data */
    
27.         value = (int *)kmalloc(sizeof(int) * VALUE_NUM,GFP_KERNEL);
    
28.         for(i = 0 ; i < VALUE_NUM ; i++)
    
29.                 value[i] = i;
    
30. 
    
31.         /* Prepare hash head array */
    
32.         phash = (struct hlist_head *)kmalloc(sizeof(struct hlist_head) *
    
33.                                         (1 << HEAD_NUM) , GFP_KERNEL);
    
34.         /* Initialize hash head */
    
35.         for(i = 0 ; i < (1 << HEAD_NUM) ; i++)
    
36.                 INIT_HLIST_HEAD(&phash[i]);
    
37. 
    
38.         /* Create Test node */
    
39.         for(i = 0 ; i < VALUE_NUM ; i++) {
    
40.                 node = (struct node *)kmalloc(sizeof(struct node),GFP_KERNEL);
    
41.                 if(!node) {
    
42.                         mm_err("No memory\n");
    
43. 
    
44.                         /* Never water memory */
    
45.                         goto bad_memory;
    
46.                 }
    
47. 
    
48.                 /* Prepare test data */
    
49.                 node->num = value[i];
    
50.                 /* Initialize the hash node */
    
51.                 INIT_HLIST_NODE(&node->node);
    
52.                 /* Get the hash head for node */
    
53.                 head = &phash[hash_32(node->num,HEAD_NUM)];
    
54.                 /* Add node into hash list */
    
55.                 hlist_add_head(&node->node,head);
    
56.         }
    
57. 
    
58.         /* Trave all hash list */
    
59.         for(i = 0 ; i < (1 << HEAD_NUM) ; i++) {
    
60.                 mm_debug("HEAD %d:",i);
    
61.                 if(!hlist_empty(&phash[i]))
    
62.                         hlist_for_each_entry(node,hnode,&phash[i],node)
    
63.                                 mm_debug("%d->",node->num);
    
64.                 mm_debug("NULL\n");
    
65.         }
    
66. 
    
67.         /* Search data in hash list */
    
68.         k = value[34];
    
69.         head = &phash[hash_32(k,HEAD_NUM)];
    
70.         mm_debug("Search %d in head %d\n",k,hash_32(k,HEAD_NUM));
    
71.         if(!hlist_empty(head))
    
72.                 hlist_for_each_entry(node,hnode,head,node)
    
73.                         if(k == node->num)
    
74.                                 mm_debug("Find the data %d\n",k);
    
75. 
    
76.         /* Delete all node */
    
77.         for(i = 0 ; i < (1 << HEAD_NUM) ; i++)
    
78.                 while(!hlist_empty(&phash[i])) {
    
79.                         node = hlist_entry(phash[i].first,struct node,node);
    
80.                         hlist_del(&node->node);
    
81.                         kfree(node);
    
82.                 }
    
83. 
    
84.         /* Final check */
    
85.         for(i = 0 ; i < (1 << HEAD_NUM) ; i++) {
    
86.                 if(!hlist_empty(&phash[i])) {
    
87.                         mm_debug("HEAD %d REMAIN:",i);
    
88.                         hlist_for_each_entry(node,hnode,&phash[i],node)
    
89.                                 mm_debug("%d->",node->num);
    
90.                         mm_debug("NULL\n");
    
91.                 }
    
92.         }
    
93.         /* Free all and complete test */
    
94.         kfree(phash);
    
95.         kfree(value);
    
96. 
    
97.         return;
    
98. bad_memory:
    
99.         for(i = 0 ; i < (1 << HEAD_NUM) ; i++)
    
100.                 while(!hlist_empty(&phash[i])) {
     
101.                         node = hlist_entry(phash[i].first,struct node,node);
     
102.                         hlist_del(phash[i].first);
     
103.                         kfree(node);
     
104.                 }
     
105.         kfree(phash);
     
106.         kfree(value);
     
107. }

复制代码

Buddy_Zhang1

回复 16# chinaandcompute


      HI:
           我在 32bit 的 Ubuntu 上做了测试,遇到您说的问题,将 size_t 注释之后,系统可以正常运行.
           使用您编译生成的 a 进行调试之后,发现 memmap_init_zone() -> set_page_zone() 有问题,请合入邮件中的补丁,进行调试.



diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 9759569..218bc0f 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -366,7 +366,10 @@ void __meminit memmap_init_zone(unsigned long size,int nid,unsigned long zone,
                continue;
        }
        page = pfn_to_page(pfn);
+       mm_debug("page %p\n",page);
+       mm_debug("pfn %p\n",pfn);
        set_page_links(page,zone,nid,pfn);
+       mm_debug("nid %p zone-> %d\n",nid,zone);
        mminit_verify_page_links(page,zone,nid,pfn);
        init_page_count(page);
        reset_page_mapcount(page);