从无到有编写一个OS内核

时间眨眼过去了将近半年,这半年里又发生了许多事,怎个叫人不心痛,就如徐志摩所说:“我若再不把我的心给你看,我就不配爱你,就不配得到你的 爱。” 我曾经也开过玩笑:“理解你的人都已经死了,你理解的人也都已经死了,你还想怎么地?” 不想一语中的,令人悲切。不知道这个家伙算不算是知己,就算不是,我也当作知己了。逝者已逝,生者犹存,好好的活着吧邱永臣。—-追忆昔友

再次登录自己的博客,发现好久没更新,就整合一下以前的东西,重新发布一遍,聊以自我安慰。

这是很久之前做的和操作系统有关的小项目(也不算项目,仅仅是学习),现在把之前写的文章都汇聚到同一篇中,供日后留念。

(一)OS说明

今后,我就要开始折腾操作系统,有了一点小小干劲。

我的计划是,先看过一份用于教育目的的系统源码,再去翻找相应的资料(我手头已有绿宝书),在翻资料的同时开始写代码,然后做好移植真机的工作,DONE!
我也明白,理性很丰满,现实很骨感,这过程不会如同我计划中这般简单和轻松。但是,见难而退可不是我的风格(那样我会被红叶二小姐调戏的),不管如何,我都会,怎么说呢,尽力吧。

出于课程需求,斯坦福那些人亲自写了一个名为“pintos”的系统。pintos的结构比较简单,分为进程管理、文件系统、用户程序、虚拟内存等几个部分,也正是因为这个原因,我选择pintos作为我的参考蓝本,现在在读它的源码。

在接下来的几个月时间里,不出意外的话,我会不断的在博客上更新我的进度。

(三)交叉编译环境

倘若我们要在ubuntu上编译另外一个完整的OS,交叉编译环境是必不可少的玩意,维基百科有云:

交叉编译器(英语:Cross compiler)是指一个在某个系统平台下可以产生另一个系统平台的可执行文件的编译器。
(想起以前,我为了给路由器编译OPENWRT,下载大量源码,愣是编译了几天几夜。那时候的我,真是“可爱”。)
为了配置好交叉编译环境,我废了好大力气,最后勉强找到了组织。
编译环境大致分为2部分,binutils和gcc。我先装好gcc-4.9.1,之后下载gcc-4.9.1和binutils-2.25的源代码,似乎gcc版本与binutils版本要对应来着…

开始编译之前,需要准备全局变量(在命令行中敲入以下命令):

export PREFIX=”$HOME/opt/cross”
export TARGET=i686-elf
export PATH=”$PREFIX/bin:$PATH”
编译Binutils
cd $HOME/binutils-2.25
mkdir build-binutils
cd build-binutils
#注意是在源码目录下面新建一个文件夹,然后cd到该文件夹里,然后才配置configure,不这么做的话,嘿嘿..
../binutils-x.y.z/configure –target=$TARGET –prefix=”$PREFIX” –with-sysroot –disable-nls –disable-werror
make
make install
–disable-nls 告诉binutils,不要添加本地语言支持

–with-sysroot 告诉binutils,在交叉编译器中允许sysroot

编译GCC
cd $HOME/gcc-4.9.1
mkdir build-gcc
cd build-gcc
#注意是在源码目录下面新建一个文件夹,然后cd到该文件夹里,然后才配置configure,不这么做的话,嘿嘿..
../gcc-x.y.z/configure –target=$TARGET –prefix=”$PREFIX” –disable-nls –enable-languages=c,c++ –without-headers
make all-gcc
make all-target-libgcc
make install-gcc
make install-target-libgcc
–disable-nls 告诉GCC,不要添加本地语言支持。

–without-headers 告诉GCC,不要依赖任何本地库,我们必须在自己的OS中实现库。

–enable-languages 告诉GCC,不要支持除了C、C++之外的语言。

提醒
不同机器配置不同,编译速度也不同。

编译这两个软件,我花了近3个钟,机器配置之低自不必说,说了都是泪。

如果任何人的任何编译过程出了任何问题,请仔细地、认真地、用心地再看看上面的命令,在你没有弄懂它的原理之前,请不要擅自做任何“改进”(血淋淋、赤裸裸的教训呀)。

(五)OS模糊框架

翻完了手头的绿宝书,我才晓得,人都是被逼出来的。

操作系统的概念都差不多已经知道,接下来,该由“理论态”切换到“实践态”了喔(书还是不能看太多,会中毒的–)。

对了,从别人推荐的地方弄来了一个框架(曾在android平台写了几万代码,我深深体会到框架的作用),轻松开工吧。

先说明一下这个框架:Meaty Skeleton,开源示例,内核和用户分离,方便扩展,嗯,没了。

最近烦杂事情很多,心情,不算愉快也不算低落吧,近来又梦见红叶,不知道又要发生什么,不管。

(六)内核第一步任务:GDT完成

天色已晚,又下着雨,我也忘记带伞了,嗯,等会儿再回去好了,这个商城的环境还是蛮好的。

今天实现了GDT。

(也不算是实现吧,因为我打算使用纯分页的流氓招数,放弃纯分段或分段分页混合,所以就不太用心于实现GDT,只是浏览INTEL的官网,借用了几个FLAG定义之类的东西,匆匆就写完了GDT)

下面是记忆:

使用内嵌式汇编
分4个段,两个高级的内核分段,两个低级id用户分段
预留了一个TSS,虽然也不打算用硬件实现任务切换(听前辈们说,硬件实现非常的麻烦)
把 设置GDT表的函数(init_gdt)放在kernel/arch/i386/global_descriptor_table.c中,而段 segment_descriptor的定义(seg_desc)则放在kernel/include/kernel /global_descriptor_table.h
引用了英特尔的一份公开资料
一些全局或者说全世界通用的参数放在kernel/include/kernel/global_parameter.h,有些人更绝,把所有函数的原型放在一个地方,哪怕内核级函数和用户级函数混在一起
翻了太多资料,头都晕了
按进度来看,有点紧,也无妨。

(七)内核第二步任务:IDT完成

佛说人者,非人者,名人者。
已经写好IDT的载入,加上之前的GDT载入,就已经完成两个与机器硬件相关的模块(准确的说,应该是给CPU的特定单元载入内容)。不过我并没传说高手那么厉害,高手们一天一个模块,可我近几天连IDT对应的IRC和HANDLE都还没弄。

在bochs上调试时,分别 键入info gdt 和info idt 1,能看到GDT和IDT的内容。

今日要点:

AT&T汇编和寻常的INTEL有些许区别,不过区别不是很大
GDT和IDT都是固定的表,必须实现,实现方法各异
之前留下的TSS并非用于切换任务,而是用于保存从“用户态”回到“内核态”时必须使用的跳转地址
未完待续
后记,IDT里面的OFFSET并没有得到正确的值,因为IRQ还没设置好,相应的HANDLE还没有弄好
2015年4月16日01:14:25补充:

设 置了IDT表中的头32个项,也就是ISR(interrupt service routines),它专门处理诸如“除以0”/“Page Fault”/“Double Fault”等exception,它对exception的处理方式也很简单,或者说根本没有处理,仅仅是打印exception的类型而已。

我 随便写了一句int a = 1/0,调试的时候,bochs提示”write_virtual_checks(): no write access to seg”。可能是内核还没具有从用户态跳转到内核态的能力吧,毕竟IDT的头32个项都拥有ring0的级别,明天再看看。

补上3种中断类型:

Exception: These are generated internally by the CPU and used to alert the running kernel of an event or situation which requires its attention. On x86 CPUs, these include exception conditions such as Double Fault, Page Fault, General Protection Fault, etc.
Interrupt Request (IRQ) or Hardware Interrupt: This type of interrupt is generated externally by the chipset, and it is signalled by latching onto the #INTR pin or equivalent signal of the CPU in question. There are two types of IRQs in common use today.IRQ Lines, or Pin-based IRQs: These are typically statically routed on the chipset. Wires or lines run from the devices on the chipset to an IRQ controller which serializes the interrupt requests sent by devices, sending them to the CPU one by one to prevent races. In many cases, an IRQ Controller will send multiple IRQs to the CPU at once, based on the priority of the device. An example of a very well known IRQ Controller is the Intel 8259 controller chain, which is present on all IBM-PC compatible chipsets, chaining two controllers together, each providing 8 input pins for a total of 16 usable IRQ signalling pins on the legacy IBM-PC.
Message Based Interrupts: These are signalled by writing a value to a memory location reserved for information about the interrupting device, the interrupt itself, and the vectoring information. The device is assigned a location to which it wites either by firmware or by the kernel software. Then, an IRQ is generated by the device using an arbitration protocol specific to the device’s bus. An example of a bus which provides message based interrupt functionality is the PCI Bus.
Software Interrupt: This is an interrupt signalled by software running on a CPU to indicate that it needs the kernel’s attention. These types of interrupts are generally used forSystem Calls. On x86 CPUs, the instruction which is used to initiate a software interrupt is the “INT” instruction. Since the x86 CPU can use any of the 256 available interrupt vectors for software interrupts, kernels generally choose one. For example, many contemporary unixes use vector 0x80 on the x86 based platforms.
今天载入到IDT中的,正是第一种类型(Exception),只不过换了个名字叫ISR而已。

未完待续。

2015年4月18日12:06:45补充:

之前的”write_virtual_checks(): no write access to seg”错误并不是权限的问题,而是段寄存器DS的值错误,它的值应该是0x10,可我给它赋值0x08。0x08是段寄存器CS的值,0x10才是段寄存器DS的值。

另外,这at&t汇编里面,把C语言函数的地址赋给寄存器,必须在函数名前面加上$。

至此,ISR彻底完成,只是,似乎IRQ又出了点问题….

未完待续。

(十)内核第三步任务:分页完成

稍微做下记录…

得到内存大小
首先,利用grab得到物理内存的实际大小。

物理内存管理
然后,用一个数组map来监督物理内存,数组的每一项都对应着一个4K的物理内存。在这里我遇到了一个问题:数组的大小如何设置?因为还没有内存分配功能,所以不可能allocate一块或new一块内存来存放数组。找来找去也没找到合适的方案,就自己弄一个粗鲁一点儿的:设置数组大小为1024 * 1024。这样一来,数组的每一项对应4K,有1024 * 1024项,恰好可以对应4G大小的物理内存。但这样又有一个缺陷,倘若物理内存没有4G而是128M,那么该数组就有大部分元素被废弃了。现在先,额,不管这个,之后再解决。

至于这物理内存它的实际分配,我是这么觉得的:把前64M的物理内存当作内核专属(把内核的所有内容全都加载到此处),剩余的物理内存才是空闲内存,用于allocate。

为了方便分配物理内存,我采取最最最简单的方法:把所有空闲的物理页放到一条链里,需要的时候直接拿出来就可以了。

虚拟内存管理
之后,就是把page_directory地址放入CR3并开启硬件分页功能了。

page_directory,page_table等作用于虚拟地址。对于这4G的虚拟地址空间,排在前面大小为MEM_UPPER的一大块虚拟内存都是内核空间,剩下的排在后面的都是用户空间。也就是说,在有512M的物理的情况下,虚拟内存的前512M是内核态,后面的3584M是用户态。

分页错误
内存分配的过程中,可能出现“页面不存在”、“页面只读”及“权限不足”3种错误。处理分页错误,CPU会自动调用14号ISRS,我们要做的,是把我们写的处理函数地址放到14号ISRS的函数栏即可。

每次分页错误,CUP调用14号ISRS,继而跳入我们设计好的处理函数(-_-陷阱?)。

不过我现在也是暂时先不写分页错误的处理函数,如果内存真的任性真的出错了,我也不会管它的,傲娇就傲娇吧。

到这里,分页就算是初步完成了。

致命的伤痛
很遗憾,物理内存设置好了,虚拟内存设置好了,也正常工作了,但是我一旦开启硬件的分页功能,就有”physical address not available”的错误,直接重启了,到底是怎么回事…再看看吧…

未完待续。

2015年5月1日12:54:14补充:

bochs的”physical address not available”提示是这么个回事,把一个内容不对的分页目录加载进硬件(也就是把分页目录地址置入CR3)。在初始化分页目录时,我直接用了4M大页的方式初始化,但弄错了byte和KB的数量级,所以就出了一点小小的问题。

遗留:page fault函数,待日后再写。

写内存分配去吧!

未完待续。

(十一)内核第四步任务:内存分配完成

内存分配?这可是个麻烦的活,不过,如果你足够聪明的话,就没什么问题了。 ——前人
上 一次,我准备好了分页的相关内容,比如说,载入分页目录/开启硬件支持/划分物理内存/划分虚拟内存等等。这一次,不会怂,就是干(为写内存分配模块而奋 斗,高扛自由的鲜红旗帜,勇敢地向前冲….)。分页准备好之后,下一步是如何地分配内存,比如,如何分配一页空白的可用的物理内存?如何分配一块空白 的虚拟内存?如何连续地分配等等等等。
第一节:申请和释放空白物理内存
申请物理内存,在分页的机制下,就是申请一页或连续几页空白的物理内存,释放则反过来。

在 分页的时候,我已经将所有的空白物理页都放进了一个链表之中,现在要申请一个空白物理页,从链表中拿出来即可,太简单了。释放空白物理页,将物理页重新放 进链表里即可,也是非常的简单,有点简单过头了。当然啦,简单有省时省力的优点,同时,也有“无法同时分配许多页/分配大内存时(比如数十M)很吃力”的 缺点。这,按我的习惯,先留着,以后再说,现在能简单就简单。

写好allocate_page和free_page两个函数之后,分配空白页倒是正常,但是内核出现”double fault”的错误,也就是8号ISR被CPU调用了,具体为甚,现在还不清楚,待我瞧瞧再说。

未完待续。

查资料如下:

Normally, when the processor detects an exception while trying to invoke the handler for a prior exception, the two exceptions can be handled serially. If, however, the processor cannot handle them serially, it signals the double-fault exception instead. To determine when two faults are to be signalled as a double fault, the 80386 divides the exceptions into three classes: benign exceptions, contributory exceptions, and page faults. Table 9-3 shows this classification.

Table 9-4 shows which combinations of exceptions cause a double fault and which do not.

The processor always pushes an error code onto the stack of the double-fault handler; however, the error code is always zero. The faulting instruction may not be restarted. If any other exception occurs while attempting to invoke the double-fault handler, the processor shuts down.

————————————————————————–

Table 9-3. Double-Fault Detection Classes
Class ID Description

1 Debug exceptions
2 NMI
3 Breakpoint
Benign 4 Overflow
Exceptions 5 Bounds check
6 Invalid opcode
7 Coprocessor not available
16 Coprocessor error

0 Divide error
9 Coprocessor Segment Overrun
Contributory 10 Invalid TSS
Exceptions 11 Segment not present
12 Stack exception
13 General protection

Page Faults 14 Page fault
————————————————————————–

Table 9-4. Double-Fault Definition
SECOND EXCEPTION

Benign Contributory Page
Exception Exception Fault
Benign OK OK OK
Exception

FIRST Contributory OK DOUBLE OK
EXCEPTION Exception

Page
Fault OK DOUBLE DOUBLE
————————————————————————–

大概意思是:同时出现了2个中断,CPU不知道该处理哪个先,就是这样,就是如此的简单。之前没有这个错误,但分配和释放几个物理页之后就有这个问题,我估摸着两个都是Page fault,再看看吧。
刚刚调试了一下,我发现不是分配和释放几个物理页的问题,而是cli()和sti()的成对出现,去掉它们就没这个问题;更奇怪的是,就算只有sti() 允许中断出现,也会double fault,莫非我这前面关了中断或者是前面遇到了不可解决的中断遗留到现在?难道,是irq的重定位有问题?到底是为什么呢?先算入历史遗留问题吧,还 有重要的模块要完成。
(事情有点麻烦了呢?并不是内存分配这里出了问题,而是sti()惹的祸,不管这哪个位置,只要调用sti()开启中断,就会double fault,看来必须解决这个问题才行,我不可能一直不开中断吧…-_-)
睡了一觉,起来查资料,看到了关键的一句:make sure you didn’t forget the CPU-pushed error code (for exceptions 8,10 and 14 at least)到了,我翻出代码一看,哎呀嘛,我只注意到了8号软中断,没注意到10号和14号软中断(14号处理page fault),删去两行代码后,顺利开启中断!
未完待续。
第二节:分配内存(malloc/free)
既然已经可以正常地分配和释放物理内存页,那么在这一小节之中,很自然地,我的任务就是分配内存了。

所谓“天将降大任于斯人也,必先让他实现一个内存分配的算法”,不外乎就是说,要实现void* malloc(int size)和int free(void* p, int num_page)两个大众情人函数。

它 的大概思路就是这样的:先初始化一个桶,把可用的内存块都塞进去,要分配内存时,直接从桶里面找,找到了当然万事大吉大家都开心,如果找不到,就调用上面 那个申请空白的物理内存页的函数,弄一个4K物理内存页过来,将这个内存页分割成小块,丢到桶里面,然后继续找,就是这样….
2015年5月5日23:19:08补充:

遇到一个bug:每次申请的时候,可以正常申请,但是一旦使用了申请的内存,内核就报”page fault”的错误。想来想去,看来看去,最终发现,我在初始化分页机制的时候出了点小小的问题。

秘技解决:

初 始化虚拟内存时,我将大小和物理内存一样大(比如129920K)的虚拟内存设为内核级别并可用,剩下3个多G的虚拟内存是用户级别但不可用,我使用4M 大页载入分页表,所以我实际上载入了129920/4096 = 31个大小为4M可用的内核级别虚拟内存页,也就是说,在虚拟内存这个空间里,仅仅有31 * 4096 = 126976K的可用空间,其它的虚拟内存均是不可用的非法的;而在初始化物理内存时,我将前64M留给内核,后面的物理内存用于malloc和 free,比如有129920K,我把它划分为129920 / 4 = 32480个4K大小的物理内存页,也就是说,在物理内存这个空间里,仅仅有32480 * 4 = 129920K的可用空间,其它的物理内存均不在管理范围之内;这样一来,就出大问题了。

假设我们要申请一个物理页,由于使用链的方式管理物理页,申请到的就是排在后面的物理内存,比如申请到了129916K到129920K这一个物理内存页,现在,我们要使用它,会发生什么呢?page fault!!!!!!!

为 什么?很明显,在虚拟内存的空间里,最大的有效内存是126976K,CPU的分页表里只能找到前126976K,现在让CPU去找129916K,它根 本就找不到!它以为这个虚拟地址并没有对应这物理地址,是个错误!(附上page fault的引发条件:A page fault exception is caused when a process is seeking to access an area of virtual memory that is not mapped to any physical memory, when a write is attempted on a read-only page, when accessing a PTE or PDE with the reserved bit or when permissions are inadequate.)
于是我稍作改正,就正常了,可以正常使用申请到的内存-_-。

未完待续。

(十二)内核第五步任务:系统时钟中断、键盘中断

我现在的状态不是很好,刚弄好系统时钟中断,每10ms发出一个中断请求;但键盘中断并没有弄好,没有识别键盘的按键SCAN_CODE,所以暂时只能识别第一次按键,系统收不到第二次按键中断,明个儿我再来看看,已经很晚了-_-!!
未完待续。

2015年5月9日 15:51:00补充:

查了一番资料,调试了一番,现在,键盘中断正常工作了,键盘可以正常工作,每输入一个字符,就在屏幕上显示出来。

嗯哼,可以进入到进程模块了。

(十三)内核第六步任务:进程创建

在自习室里,我突然想到一个问题:一个进程,如何去创建它?(虽然之前翻完了大宝书,但毕竟一个多月都过去了,忘了具体的实现-_-)

翻 翻书,找到一个和我的设想相差不多的方案:用一个特定的结构体代表一个进程,结构体中包含进程的相关信息,比如说进程的pid、上下文、已打开的文件、优 先级、已经占用的CPU时间、已经等待的时间、虚拟内存空间、错误码等等,创建进程的时候,只需要跳转到进程的虚拟内存空间即可。至于如何跳转,那就是内 核态的事情了,一般的进程都处在用户态,也就不必关心太多。

如此,我们便是可以创建并运行一个进程了(不考虑文件系统),既然可以创建进程,可以切换进程,那么进程调度就很容易了,不过就是个复杂的进程切换过程而已,下一节便是写进程的调度罢。

(十四)内核第七步任务:进程切换与进程调度

黄粱一梦。
看到这句古语,顿时感慨万千,没想到仅仅数周时间,我的人生竟发生了这么大的转折(不是一夜暴富),仿佛一夜醒来,到另外一个平行世界里去。甚至,在睡梦中我都会惊醒。

逝 者已逝,再多的话语也没用。只是,我不甘愿就这么结束而已。她也曾经说过:“此身不得自由,又何谈放纵”,现在我竟是极度赞同了。曾经想过在割腕的那一瞬 间,她的脑海里究竟有什么,有没有浮光掠影,有没有回放这一生的片段?如此年轻的生命,选择自我了断,需要多少黑暗沉淀,多少的落寞与失望…似乎一下 子也看开了。

(以上只是个人情感的流露,忍不住必须得写些什么,请忽略)

简单记录一下吧,没什么心情。

进程切换时,只需要切换进程上下文,把context刷新一遍即可。

至于进程调度,这个就简单许多了(其实也挺复杂),在时钟中断到来的时候,调整各个进程的优先级,并切换到相应的进程,就是这么简单。

嗯,就这样吧,现在只想戴上耳机听听音乐….

(十五)暂时停止更新…

时间安排临时有变,往后的3周,有点麻烦事要做,就先暂停这个系统的编写了,待得弄完繁杂的事,我再来更新吧。

后记

把曾经发过的帖子整合之后我惊讶的发现,原来字数已经过万了,好神奇的人哪。那么,从现在开始,就让这篇帖子沉没在历史的尘埃中吧…