Chinaunix

标题: [73%]正在写一个模拟 Linux 内存管理的系统 [打印本页]
作者: Buddy_Zhang1    时间: 2016-03-02 16:53
标题: [73%]正在写一个模拟 Linux 内存管理的系统
本帖最后由 Buddy_Zhang1 于 2016-03-24 20:38 编辑

我想写一个关于内存管理的小系统,该系统的内存管理机制完全模拟 Linux 的内存管理机制.

我的想法是在用户空间申请两个大小为 256M 的数组,然后把这两个数组模拟成两块内存块,
我就基于这两块虚拟内存块,在其上面构建一个和 Linux 内存管理机制一样的系统.
这个系统是运行在用户空间的,也就是一个用户程序而已!

这样是否可行?大家提提意见.

写这个系统的目的就是学习 Linux 内存管理从创建到运行管理的整个过程,如果可行,并且写出来,我会开源出来.

谢谢!
作者: Buddy_Zhang1    时间: 2016-03-03 08:41
本帖最后由 Buddy_Zhang1 于 2016-03-04 11:47 编辑

经过考虑,我做以下模拟:
1. 硬件模拟支持 MMU 的 ARMv7
2. 使用纯 C 编写.
3. 使用 main() 函数的构造函数作为 Uboot,使用 main() 作为 kernel 空间.
4. 单核 UMA
5. 两块模拟内存块之间存在一定大小 hole.

作者: Buddy_Zhang1    时间: 2016-03-04 11:45
Feature Update:
该内存管理系统支持内存分配器如下:
1. Bootmem Allocator
2. Per-CPU Allocator
3. Buddy Allocator
4. PCP Allocator
5. SLUB Allocator
6. VMALLOC Allocator
7. KMAP Allocator
作者: nswcfd    时间: 2016-03-04 18:00
赞！+U！

PS，为啥需要模拟硬件，哪些逻辑跟arch相关？
作者: Buddy_Zhang1    时间: 2016-03-04 21:06
本帖最后由 Buddy_Zhang1 于 2016-03-04 21:08 编辑

回复 4# nswcfd


主要是模拟硬件 MMU 和页表转换过程，其中 setup_arch() 函数中比较多
和 arch 关系最大的当属 Bootmem Allocator 了


   
作者: Buddy_Zhang1    时间: 2016-03-06 12:04
本帖最后由 Buddy_Zhang1 于 2016-03-06 12:04 编辑

Feature Update:
核心算法支持:
1. 红黑树
2. 优先查找树
3. 基数树.
4. HASH
5. 伙伴系统算法
作者: Buddy_Zhang1    时间: 2016-03-07 12:08
技术问题:
我使用的是 64 位的系统,但我写的系统是一个 32 位的系统,所以在 64 位用户空间模拟 32 位程序是一个难题.

大家有没相应的经验,交流一下.
作者: Buddy_Zhang1    时间: 2016-03-08 10:42
Feature Update:
伙伴系统算法更新:
从伙伴系统中获得一个物理页:

struct TestCase_get_free_page(void)
{
     struct pglist_data *pgdat;
     struct zonelist *zonelist;
     struct zone *zone;
     struct free_area *area;
     struct page *page;
     int migratetype;
     int order,current_order;

     pgdat = NODE_DATA(0);
     zonelist = pgdat->node_zonelists;
     first_zones_zonelist(zonelist,0,NULL,&zone);
     migratetype = MIGRATE_MOVABLE;
     int order = 0;

     for(current_order = 0 ; current_order < MAX_ORDER ; current_order++) {
           unsigned long size;

           area = &zone->free_area[current_order];
           if(list_empty(&area->free_list[migratetype]))
                      continue;
   
           page = list_entry(area->free_list[migratetype].next,
                                struct page,lru);
           list_del(&page->lru);
           rmv_page_order(page);
           area->nr_free--;
         
           size = 1 << current_order;
           while(order < current_order) {
                ara--;
                current_order--;
                size >>= 1;
                list_add(&page[size],lru,
                              &area->free_list[migratetype]);
                set_page_order(&page[size],current_order);
                area->nr_free++;
          }
          if(!PageBuddy(page))
                 goto out;
     }
     printk(KERN_INFO "Can't get free page\n");
     return;

out:
      printk(KERN_INFO "Get free page\n");
}

释放一个 page 回伙伴系统

void TestCase_free_page(void)
{
      struct page *page = /* 已知*/;
      struct zone *zone;
      struct page *buddy;
      unsigned long page_idx,buddy_idx;
      unsigned long combine_idx;
      int order = 0;

     zone = page_zone(page);
     migratetype = get_pageblock_migratetype(page);
     page_idx = page_to_pfn(page);

     while(order < MAX_ORDER  -1) {
           buddy_idx = __find_buddy_index(page_idx,order);
           buddy = page + (buddy_idx - page_idx);
           if(!page_is_buddy(page,buddy,order))
                    break;

           list_del(&buddy.lru);
           rmv_page_order(buddy);
           zone->free_area[order].nr_free--;
           combine_idx = buddy_idx & page_idx;
           page = page + (combine_idx - page_idx);
           page_idx = combine_idx;
           order++;
    }
    set_page_order(page,order);

    if((order < MAX_ORDER - 2) && (pfn_valid_within(page_to_pfn(page)))) {
          struct page *higher_page,*higher_buddy;

          combine_idx = buddy_idx & page_idx;
          higher_page = page + (combine_idx - page_idx);
          buddy_idx = __find_buddy_index(combine_idx,order + 1);
          higher_buddy = higher_page + (buddy_idx - combine_idx);
          if(page_is_buddy(higher_page,higher_buddy,order + 1)) {
                   list_add_tail(&page->lru,
                      &zone->free_area[order].free_list[migratetype]);
                   goto out;
          }
    }
    list_add(&page->lru,
                   &zone->free_area[order].free_list[migratetype]);
out:
    zone->free_area[order].nr_free++;
}
作者: nswcfd    时间: 2016-03-08 20:20
3. 使用 main() 函数的构造函数作为 Uboot,使用 main() 作为 kernel 空间.

这句话怎么理解？
作者: Buddy_Zhang1    时间: 2016-03-08 22:07
本帖最后由 Buddy_Zhang1 于 2016-03-08 22:10 编辑

回复 9# nswcfd


    就是 C 语言中 main() 函数的构造函数,main() 函数有它的构造函数和析构函数,我把构造函数当做 uboot 过程,把析构函数当做关机过程.
    该方法已经实现.


    具体实现方法如下:


/*
* Simulate U-boot
*/
__attribute__((constructor)) __uboot U_boot(void)
{
        mm_debug("[%s]Boot From U_Boot\n",__FUNCTION__);
        u_boot_start();
        mm_debug("[%s]Uboot finish,start kernel...\n",__FUNCTION__);
        start_kernel();
        mm_debug("Kernel Running.....\n=====Hello World=====\n";
}
/*
* Simulate power-down.
*/
__attribute__((destructor)) __exit Pown_down(void)
{
        mm_debug("=======Goodbye=======\n";
        mm_debug("[%s]Pown down......\n",__func__);
}
作者: Buddy_Zhang1    时间: 2016-03-09 21:10
本帖最后由 Buddy_Zhang1 于 2016-03-10 15:25 编辑

Feature Update
在 64 位系统上模拟 32 位程序技巧分析：
1. 对于基于内存问题的变量，使用 unsigned int !! 而不使用 unsigned long
2. 内存对齐时，使用 unsigned int 对齐，不使用 long 或 unsigned long 对齐。
3. 位操作时候，使用 U 而不使用 UL
4. 64 位指针转换为 32 指针,使用 unsigned long 技巧。
5. void * 位 8 byte
作者: _nosay    时间: 2016-03-09 21:56
搞个赞，加油。
作者: Godbach    时间: 2016-03-10 11:14
回复 1# Buddy_Zhang1

LZ 一直在更新。赞！


   
作者: Buddy_Zhang1    时间: 2016-03-10 15:20
本帖最后由 Buddy_Zhang1 于 2016-03-11 14:18 编辑

Feature Update
重大更新:

1. 支持 TLB.   
    TLB 主要用来存储虚拟地址到物理地址转化的缓存.为了实现这种模拟,我的做法如下:
    1) 使用下面结构来存储一个转换关系.
         struct node {
             struct rb_node node;
             unsigned int phys_addr;
             unsigned int virt_addr;
             unsigned int mem_addr;
         }__attribute((aligned(unsigned int)));
    2) 使用红黑树进行管理,使用虚拟地址作为红黑树的平衡因子.
    3) 引入 TLB 的目的主要是解决该模拟器模拟用户空间地址转换或 vmallc() 分配的虚拟地址,加速转换为物理地址!
    4) struct node 使用 __attribute((aligned(unsigned int))) 进行对齐,这样有助于数据在 TLB 中的管理.
    5) 对 TLB 的管理,后期我会查考相关 TLB 知识,应该会引入 VIPT 或 VIVT 机制.
    6) 用户空间或高端内存虚拟区获取物理地址参照下面例程:
         
unsigned int TLB_virt_to_phys(unsigned int virt)
{
        struct rb_node *node = TLB_root->rb_node;  // TLB_root 为 TLB 的红黑树根节点.
        
        while(node) {
             struct node *data = container_of(node,struct node,node);
         
             if(virt  > data->virt_addr)
                    node = node->rb_right;
             else if(virt < data->virt_addr)
                    node = node->rb_left;
             else
                    return data->phys_addr;
        }
        return 0xFFFFFFFF;
}
         

   
   
作者: Buddy_Zhang1    时间: 2016-03-11 14:12
Feature Update
支持三级页表机制:
1. PGD 页表:
                     位于 swapper_pg_dir 处 16K 大小,存储 0 ~ 4G 的一级页表.
                     操作函数为:
                     pgd_t *pgd;
                     pgd_offset()
                     pgd_index()
2. PMD 页表:
                     ARM 硬件只支持两级页表,而 Linux 模拟支持该层页表,所以 PMD 页表就是 PGD 页表.
                     但 PMD 页表有其特定的作用.
                     其定义为 typedef struct {unsigned long pmd[2];} pmd_t;
                     由于 PMD 页表的作用是指向 PTE 页表的.内核使用一个 page 来存储 PTE 页表.
                     对于这个 PTE page 的分布是 0 ~ 2K 存储软件 PTE,2K ~ 4K 存储硬件 PTE.
                     内核将 2K ~ 4K 分作了两个入口,每个入口包含 256 个PTE 页表.所以
                     pmd[0] = H/W PTE0.
                     pmd[1] = H/W PTE1.
3. PTE 页表:
                    从 buddy system 中分配一个物理页用来做 PTE page,正如上面所说,
                    0 ~ 1K 用来存储软件 PTE0, 1K ~ 2K 用来存储软件 PTE1,总共 512 个 PTE 入口.
                    相关函数为:
                    pte_offset_map()
                    pte_offset_kernel()
                    pte_index()
                           
            
作者: Buddy_Zhang1    时间: 2016-03-14 12:17
技术问题:
由于系统源码的不断增大,头文件数量不断增多,这样导致一个问题:
   "头文件相互嵌套问题"
有什么方法防止头文件相互嵌套问题????
作者: Buddy_Zhang1    时间: 2016-03-15 16:36
Feature Update:
支持 ATAG 机制:
    通过 uboot 传递的 ATAG 参数,内核可以设置 struct meminfo 的大小
作者: nswcfd    时间: 2016-03-16 12:03
基本问题吧

/* xxx.h */
#ifndef XXX_HEADER_FILE
#define XXX_HEADER_FILE

/* your header file here */

#endif
作者: Buddy_Zhang1    时间: 2016-03-16 13:45
回复 18# nswcfd


    恩恩,这也是一种解决办法,但我测试我的头文件集合的时候,有 80 多个头文件,还是无法避免头文件循环嵌套.
    但经过不断调试之后,我总结出解决头文件嵌套的问题,其中我的主要原则就是不随意引用头文件.
    毕竟头文件和预处理有关,我审视了相关的 C 文件之后解决了这个问题.
作者: Buddy_Zhang1    时间: 2016-03-17 20:27
Feature Update
实现 Vmalloc Allocator 分配器，实现接口如下：
    1. vmalloc
    2. vfree
    3. vread
    4. vwrite

增加 Mempool 的支持接口
实现 buddy，slab 和 vmalloc 的 Mempool 机制
作者: _nosay    时间: 2016-03-18 09:20
回复 16# Buddy_Zhang1


我自己遇到这种情况，会用下面这两种方法：

① 把类型提前声明一下
file-a.h:
#include "file-b.h"
struct B;
struct A {
   struct B *b;
};

file-b.h:
#include "file-a.h"
struct A;
struct B {
   struct A *a;
};


② 把struct A、struct B定义在comm.h，然后:
file-a.h:
#include "comm.h"

file-b.h:
#include "comm.h"
作者: Buddy_Zhang1    时间: 2016-03-21 21:20
Feature Update

由于部分内存管理依赖于虚拟文件系统,譬如 pagecache 和 swap 等.
为此,我将把 VFS 加入到这个模拟器中.
       又要花半年时间进行调试......
作者: Buddy_Zhang1    时间: 2016-03-22 19:23



最新系统启动截图，本周末释放 Preview 版。
作者: nswcfd    时间: 2016-03-23 11:24
BiscuitOS 赞
作者: hanshu830    时间: 2016-03-23 16:22
我有点混乱了。。。。 这到底是模拟器呢？ 还是一个应用程序把kernel的log 打印一遍？
作者: Buddy_Zhang1    时间: 2016-03-23 16:42
回复 25# hanshu830


    这是一个应用程序,这个应用程序的功能就是用来实现 linux 内存管理的功能.

    这个应用程序也可以称为一个小型内核,因为它已经具备了内存管理的能力,可以分配,使用并回收内存.
作者: hanshu830    时间: 2016-03-23 17:20
回复 26# Buddy_Zhang1
额， 看你的log， 简直像在跑kernel code. Kernel代码被merge到你的程序里了？

   
作者: Buddy_Zhang1    时间: 2016-03-23 17:24
回复 27# hanshu830


    对,我就是在用户空间上分配了两个很大的数组来充当我的内存.然后基于这两块内存来跑内核代码.
    但我的代码只有内存管理部分的代码(还包括内核启动的相关代码)
作者: hanshu830    时间: 2016-03-23 17:44
回复 28# Buddy_Zhang1


    Merge的工作量估计相当大啊。。。。
作者: Buddy_Zhang1    时间: 2016-03-23 17:47
本帖最后由 Buddy_Zhang1 于 2016-03-23 17:52 编辑

回复 29# hanshu830


    算下来,学理论 + merge代码 + 调试功能 + 逻辑性调试----> 正好一年时间


   现在正在将 VFS 加入到这个系统中,估计花半年时间...
作者: hanshu830    时间: 2016-03-23 17:49
回复 30# Buddy_Zhang1


    哦, 加油
作者: Buddy_Zhang1    时间: 2016-03-23 17:52
回复 31# hanshu830


    恩恩,本周我将代码开源出来
作者: Buddy_Zhang1    时间: 2016-03-24 20:39
Feature Update
1. 增加 kobject 模型
2. 增加内核命令行机制
3. 增加链接器段机制




欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2