文章目录
  1. 1. 运行环境
  2. 2. 开发语言
  3. 3. 引导启动
  4. 4. 显示器输出
  5. 5. 中断处理
  6. 6. 物理内存
  7. 7. 虚拟内存
  8. 8. 内核线程
  9. 9. 硬盘读写
  10. 10. 一些遗憾
  11. 11. 总结
  12. 12. 链接
  13. 13. 参考资料

花了两个礼拜时间,大致实现了一个OS内核。总的过程还是蛮好玩的,从启动引导,到内核线程的创建,再到硬盘读写,学到了不少有意思的东西。不过在弄明白原理之后,剩下的基本都是比较枯燥的工作,自己也没什么心思再写下去,留下了一点遗憾。

目前这个内核实现了:

  • 引导启动
  • 显示器输出
  • 中断处理,包括键盘输入,定时器中断
  • 物理内存管理:分页、分段
  • 虚拟内存管理:二级页表、动态内存分配
  • 内核线程,以及一个简单的线程调度器
  • IDE硬盘读写

运行环境

使用了qemu虚拟机,从一个软盘镜像启动,内核本身用grub加载。这个虚拟机非常轻量级,启动非常迅速,另外,它可以直接用gdb来调试,非常方便。

搭建环境的过程基本参考了Hurlex,所以在这里花了很少的时间。

开发语言

Hurlex是用C完成的开发,但我在写C的过程中感觉非常不适,所以后来就采用C++开发。用C++开发倒没有什么大的问题,只是一开始犯了蠢,跟汇编交互的部分全都用了手动mangling,非常之痛苦。后来发现用extern “C”基本可以完成C++和汇编函数的交互,所以这个问题也不存在了。

用C++开发会有很多限制,比如标准库基本不能用,只能使用一部分语言特性。例如静态局部对象貌似就不太能用,因为这个会用到线程同步;全局对象也不太奏效,因为全局对象的初始化是依赖runtime的,这里只会为之分配内存,于.bss段,但不会执行初始化,所以还要手动初始化;说到手动初始化,比较好的方式是placement new,但kernel里也不能直接使用placement new,因为这是标准库的一部分。。

不过好在我们可以自己实现一个placement new:

1
2
3
4
5
6
7
8
9
10
11
inline void* operator new(uint32_t count) { return kmalloc(count); }

inline void* operator new[](uint32_t count) { return kmalloc(count); }

inline void* operator new(uint32_t count, void* ptr) { return ptr; }

inline void* operator new[](uint32_t count, void* ptr) { return ptr; }

inline void operator delete(void* ptr) { kfree(ptr); }

inline void operator delete[](void* ptr) { kfree(ptr); }

只需要这样简答的实现就好了,其余构造函数调用会由编译器来完成,我们也无能为力;这里调用的kmalloc/kfree是内存管理函数,所以这也意味着new/delete需要在完成虚拟内存管理模块之后才能使用。

C++在kernel中的限制基本就是内存上的限制,还有对象模型什么的,在OSdev上有讲述。另外,理论上讲是能够使用STL的容器的,但是我尝试使用了SGI STL,发现它还是有不少依赖,会由一些不兼容的部分,所以在kernel中就没有使用STL,自己写了一些非常bull shit的容器,因为完整地实现STL container工作量实在是比较大,哪天有空再去重构一下把。

除了这些限制之外,用C++开发能够获得这些好处:

  • OO,容易进行模块化,比如Allocator,Scheduler
  • template,在实现printk函数的时候,使用变长模版参数会简化很多工作
  • reference,nullptr,type cast,default parameter什么的还是很方便的

所以,我个人觉得C++写kernel会比较方便,如果能把STL的容器移植过去就更爽了。

引导启动

由于用grub引导,所以稍微修改了一下grub的配置,把启动文件改成内核的名字。

内核的初始化,用汇编语言完成,设定一些Magic Number,栈地址,然后就跳到entry函数。

其实到这里内核就已经初始化了,我们可以在里面计算加减乘除什么的都没有问题,只是,目前没有IO,这个黑盒里的东西我们什么都看不到。迫在眉睫的事情就是让它能够显示什么东西出来。

显示器输出

显示器的输出也比较简单,地址空间的0xB8000是显存的起始地址,往后每两个字节对应屏幕上的一个字符,共80×25。两个字节,一个字节控制显示字符,另一个控制前景色和背景色。除此之外还有光标,这需要通过IO端口来完成。

我们基于此可以实现在屏幕上显示一个“hello world”,算是小有成就。

之后可以对此进行完善,实现颜色控制,屏幕滚动等功能。

中断处理

中断,当CPU收到中断时,会检查idt指向的中断表,根据中断号执行到相应的ISR。

键盘中断,对应的中断号是33,通过0x60 IO口接收输入字符;键盘按下和释放都会触发一次。另外,向按键组合,都是需要程序的逻辑来实现。拿shift举例,按下shift的同时,再按其他的字符由小写变大写,大写变小写,所以我们需要至少两张字符映射表,shift键的按下与否需要维护,来实现按键组合的功能。

实现了键盘中断之后,我们就可以在屏幕上打字了。理论上讲我们已经有了输入输出,其实可以在此基础上写一个贪吃蛇什么都没有问题。

时钟中断是另一个重要的中断。CPU外部有多个定时器,可以通过编程的方式,让它们定时向CPU发出中断,于是kernel就有了时间的概念。之后的进程调度什么也会在此基础上进行。

物理内存

内存管理是比较复杂的一块。

grub在加载内核时,一般是加载到0x100000的地址,也就是1M。低地址空间下会有很多外部设备,往上才是我们能够利用的空间。

如何使用这么多内存,是物理内存管理的主题。

分段,是80386时引入的一个技术,它使得16位的cpu能够使用20位的地址空间,并且也带来了权限管理、内存隔离的功能。不过现代的OS基本都绕过了分段机制,也就是把段基址都设为0,段长都设为0xFFFFFFFF,分段也就没什么用了。

分页,是把连续的内存分为很多页,通常为4K。

在此基础上,就有了很多内存分配技术,我只采用了比较简单的隐式链表。就是说,现在有一块很大的内存,我们在这一块内存的起始处拿一块作为block header,记录上块大小和分配状态。然后基于大小信息就可以寻找到下一个块了。在分配的时候,找到一个空闲快,然后把这个空闲块一分为二,前面一块分配出去,后面的继续保留。而在回收的时候,则需要合并前后的空闲块。

Linux内核中实现了一些更为复杂的算法,例如Buddy system:把所有的内存块都视为2的k次幂,分配的时候,如果没有合适的块,就把当前的块一分为二,大小一样;直到找到一个满足2^k-1 <= size <= 2^k块。在这个过程中,大的块会被切成很多小的块,放到多个bucket里。分配的时候查找这些bucket,会非常快,对于4G的内存,只需要32个bucket。回收内存的时候,除了把内存放回bucket里,还需要把小的块合并成大的,防止没有内存可用。

虚拟内存

虚拟内存也是一个伟大的技术。

它所带来的功能,比如进程隔离、进程共享、权限管理、页面换出等等,都是一个成熟的OS必不可少的。

对于32位的kernel,每个进程能够使用的地址空间都是4G,每个进程都能访问到相同的地址,而这个地址自然是虚拟地址,通过虚拟内存技术,映射到不同的物理地址。

虚拟内存的实现需要OS和硬件来协作。MMU是负责地址翻译的硬件,它拿到一个虚拟地址,去查询页表,计算相应的物理地址,而这个页表,需要OS来创建,也就是说映射需要OS来维护。通常来说OS会采用多级页表,以实现更好的空间利用率。并用TLB来缓存。

不过这里比较复杂的一点是,系统启动时我们使用的是物理地址,开启分页模式后才进入虚拟地址,对于代码来说,它的地址需要变动吗?代码中使用的地址在编译时已经确定,而内核的加载地址就是0x100000,如果代码使用3G~4G的虚拟地址,必然就会存在冲突。所以这里的解决方案是,先做一个妥协,一部分代码采用0x100000以上的地址,它负责建立一个临时页表,把内核的加载部分以及3G以上的虚拟地址都映射到同一个物理地址,于是内核里的所有代码都能运行了;然后另一段代码使用3G~4G的地址空间,它来建立真正的页表。

这里使用了按需分页的技术,内核只固定分配很小的一段空间,其他的地址都在产生page_fault的时候才去分配。

在实现页目录的时候,有一点需要注意,页目录的PDE存放的是物理地址,但是在代码中却不能使用物理地址去操作,只能用虚拟地址,所以还要做一次转换。

内核线程

内核线程。线程对应了一个函数调用栈,以及一组寄存器,作为它的上下文。所以创建一个线程,就是分配一个栈,以及它的上下文。对于这些信息会有一个封装结构,通常为task_struct,也就是PCB。我们把这个PCB存放在栈顶,不过这也意味着,如果爆栈,这些数据都会被破坏。

线程初始化很有意思:

1
2
3
4
5
uint32_t* stack_top = reinterpret_cast<uint32_t*>((uint32_t)new_task + STACK_SIZE);
*(--stack_top) = (uint32_t)new_task->pid; // the parameter to kthread_exit
*(--stack_top) = 0; // return address above the kthread_exit frame
*(--stack_top) = (uint32_t)kthread_exit;
*(--stack_top) = (uint32_t)fn;

以此把线程id,0,线程退出函数,以及线程入口函数push到栈里。这个结构需要跟线程上下文切换来一起看:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
switch_to:
; the first function parameter
mov eax, [esp+4]

mov [eax+0], esp
mov [eax+4], ebp
mov [eax+8], ebx
mov [eax+12], esi
mov [eax+16], edi
pushf
pop ecx
mov [eax+20], ecx

; the second function parameter
mov eax, [esp+8]

mov esp, [eax+0]
mov ebp, [eax+4]
mov ebx, [eax+8]
mov esi, [eax+12]
mov edi, [eax+16]
mov eax, [eax+20]
push eax
popf

ret

这里的大部分代码都是切换上下文,没有什么大问题。不过在最后ret的时候,由于没有保存ebp,跳转的地址就是栈顶的地址,对于之前的栈结构来说,就是栈顶的fn,线程入口函数;对于中断上下文来说,栈顶则是保存的返回地址,所以用一个ret就可以实现统一。

栈上的第二个函数的kthread_exit,线程退出函数,函数fn执行完毕,kthread_exit会被当做返回地址来跳转,所以直接执行kthread_exit。

再网上,是一个0,暂时不说。最底下的是线程id,这是作为kthread_exit的函数参数,因此前面的那个0也显而易见,是作为kthread_exit函数帧的返回地址,不过它是线程的终结,没有返回地址,就用了一个0来代替。借此能够拿到最底下的函数参数。如果需要传递参数给fn函数,也可以把这个值改成参数。

硬盘读写

通过Program IO的方式读写IDE接口硬盘,简单来说就是会有一组控制寄存器和数据寄存器,发一个命令,然后去IO端口拿数据。

在此之前需要用qemu-img创建一个硬盘镜像,并挂载上去。之后的过程也是比较顺利。

一些遗憾

  • 由于是C、C++、assembly混杂,代码很多地方都写的比较乱,没有做好设计。特别是链表,写了一个非常bull shit的实现。
  • 没有实现一些通用的数据结构,抽象做的很差
  • 没有实现用户进程,没有实现系统调用,因此也没有在此基础上写一个shell什么的
  • 没有实现文件系统
  • 内存分配那块可以完善的地方还有很多,只实现了最简单的算法
  • 没有实现通用的定时器,没有实现墙上时间
  • 线程调度,没有实现挂起,resume
  • 没有做内核同步
  • 总之这个kernel的完成度很低

总结

虽然留了很多的遗憾,但是自己暂时没心思也没功夫写这个kernel了。

收获还是蛮多的,也长了不少见识,实践是最好的学习方式。

链接

文章目录
  1. 1. 运行环境
  2. 2. 开发语言
  3. 3. 引导启动
  4. 4. 显示器输出
  5. 5. 中断处理
  6. 6. 物理内存
  7. 7. 虚拟内存
  8. 8. 内核线程
  9. 9. 硬盘读写
  10. 10. 一些遗憾
  11. 11. 总结
  12. 12. 链接
  13. 13. 参考资料