AM Copter Control Screen Shot

NOVELL She Calves Puzzle

iIf a cow produces its first she-calf at age two years and after that
produces another single she-calf every year, how many she-calves are
there after 12 years? assuming none die.

My Answer

Linux 0.11 内核完全注释 笔记(三)

>2 fork 做什么？
>半斤回答：准备LDT，TSS，页目录，页表...

在Linux内核中，一个进程是用struct task_struct类型的变量来标记。所以fork首先是创建了一个新的struct task_struct类型的变量，对其进行相应的赋值。

重要的是，新建进程的TSS，LDT表，页目录和页表是全新创建的，在存储上和父进程完全没有关系，不同的两个实体。但新进程LDT所指向的数据段和代码段完全照抄父亲进程，指令指针也同父进程一致。也就是说，父子进程共享代码段，数据段和堆栈段都是相同的地址空间。好比两个锦囊装着同一妙计，嘿嘿！

插一句：从这里看fork的两次返回是那么的自然，两个进程指令指针(EIP)都一样，能没有两个返回吗？

更重要的事，fork过程中将父子进程所有页表都设置成了Read Only, 为啥子啊？ 为了实现Copy On Write技术。由于页表项设置成了只读模式，每次写页表项所对应的页面时(比如函数调用把参数放入堆栈)都会引起写保护页异常，CPU会自动执行异常处理函数，进而调用 do_wp_page 函数来分配一个新的页面，挂载到引起写异常的页表项目，之后设置页表项可读可写。这个技术就叫Copy On Write。Copy On Write 完全是一种按需分配的技术，缺页/写保护页面异常是伟大的设计，因为它缔造了Copy On Write，缔造了虚拟内存技术！

这里还有一个问题值得思考，假设fork之后的程序马上会对数据段进行写动作，进而导致CPU进入写保护页面异常处理程序，谁的页表项会指向新分配的空间呢？父 or 子？

答案取决于谁先引起写保护页面异常。假设儿子引起了异常，那么儿子的页表项会指向新的分配空间；假设是父亲引起了异常，父亲的页表项会指向新空间，这样之前父亲占用的空间就归儿子所有了。很有趣的逻辑啊！

代码参考：
sys_fork -> copy_process
http://oldlinux.org/lxr/http/source/kernel/fork.c#L68
un_wp_page
http://oldlinux.org/lxr/http/source/mm/memory.c#L221

Linux 0.11 内核完全注释 笔记(二)

有句话说提出问题比解决问题重要。是啊，我想看书也是一样。能预先提出问题，带着问题去看书会事半功倍。这次我再读此书想先问自己N多关心的问题，在阅读的时候去求索，然后写出笔记一一解开自己的心结。虽然这些问题我大概略之一二，但是半斤八两的感觉和我此次刨根问底的原则不吻合。目前能想到的关键问题如下：


进程管理

1 进程如何切换？
半斤回答：JMP 到预切换到任务的 TSS

2 fork 做什么？
半斤回答：准备LDT，TSS，页目录，页表...

3 exec 做什么？

4 进程调度算法？

内存管理

5 系统的发动机，缺页异常具体实现？
半斤回答：就是从SWAP/FS往内存放数据

设备管理

6 磁盘请求队列算法？
半斤回答：电梯算法，插入使链表排序。

7 键盘驱动？

8 显示器如何折腾？

文件系统

9 fd管理与pipe通信？

10 知识盲区啊，提不出什么好问题了？！

Linux 0.11 内核完全注释 笔记(一)

有人说：”初恋不懂爱情！“。的确，五年前我读了《Linux 0.11 内核完全注释》一书，茫然的看完，悄然的离去。所幸的是种下了一个Idea：“这书还是不错的。”

五年后，再读此书，感触颇多，当读到move_to_user_mode这个神器时不由自主在weibo上像文人骚客一样发出如下感叹：

”一生至少该有一次，为了某段代码而陶醉自己，不求年代，不求国籍，不求编程语言，甚至不求编译运行，只求在我思索的年华里，遇到你。“
http://oldlinux.org/lxr/http/source/include/asm/system.h#L1

言归正传，笔记开始！

写操作系统不读CPU手册和上厕所不带纸是一个概念，不是扯淡就是高手！所以此书上来先介绍了X86保护模式编程的东东，只有弄清楚这些东东，才能9浅1深的去理解Kernel。X86的保护模式编程个人感觉还是挺复杂的，毕竟要游走于N多概念之间。

Q1 逻辑地址如何转换到物理地址？

Logical Address (逻辑地址)
Linear Address (线性地址)
Physical Address (物理地址)

这些是地址，我们的程序编译完的地址可以粗略理解成逻辑地址，在开启保护模式的情况下，CPU在指令运算时，都需要把程序的逻辑地址转换到真实的物理地址上。怎么转换？靠查表！怎么查？要查表首先要知道表在哪里，然后要知道表的Index，进而得到表项，得到表项后再分析就可以得到真实的物理地址。顺藤摸瓜也！Intel的X86 CPU已经把藤和瓜所需的数据结构都准备好了。

Local Descriptor Table (局部描述符表）LDT
Gloal Descriptor Table (全局描述符表）GDT
Local Descriptor Table Register (局部描述符表寄存器）LDTR
Gloal Descriptor Table Register (全局描述符表寄存器）GDTR
LDT/GDT是表，表的线性地址放在了LDTR/GDTR寄存器中，这是“藤1”。


Code Segment Selector (代码断选择符) CS
Data Segment Selector (数据段选择符) DS
Stack Segment Selector (堆栈段选择符) SS
{C|D|S}S这些是段选择符，Bit2标识使用GDT or IDT，bit3～15是Index信息，这是“藤2”。

Code Segment Descriptor (代码段描述符）
Data Segment Descriptor (数据段描述符）
System Segment Descriptor (系统段描述符）
系统断描述符又可分为：
1 LDT段描述符
2 TSS(Task State Segment)描述符
3 中断门描述符
4 调用门描述符
5 任务门描述符
6 陷阱门描述符
LDT/GDT中的表项就是这些{断|门}描述符，每个描述符都占用8个Byte空间，这是“藤3”。

所以CPU在逻辑地址转换到物理地址过程中，顺着藤1，藤2，找到了藤3。
找到藤3之后，CPU解剖了藤3，挖出了段基地址，然后与逻辑地址相加，这样就得出线性地址。

在没有开启分页机制情况下，线性地址就是真实的物理地址。如果已经开启分页，那就要再顺着“藤4”去摸。CR3寄存器存放着当前任务使用页目录的物理地址。这是"藤4“。经过分析后直接找到物理地址，顺藤摸瓜结束。

Intel还算厚道，没来个18摸，最多也就是Inception的3重梦境。累了，以后再写！

LFS 纪念

今天已经成功将LFS Linux放到了U盘。从5月初下载源码包，到今天也一个多月了。断断续续的在复制粘贴着命令，初步统计为此计划耗时应该在20小时左右。20小时的工作，我分散到了一个月做，不是我有耐力，而是有用一个poor/short记忆力，总想不起来此事。:-(

目前LFS Linux进入Shell大概需要20s,速度有些慢，主要时间是花在从U盘拷贝 kernel到RAM。后续还需要多多折腾。

我所使用的是LFS 6.8 http://www.linuxfromscratch.org/lfs/downloads/stable/LFS-BOOK-6.8-HTML.tar.bz2 只要从头到尾做，基本可以确定会顺利启动属于你自己的Linux。期间唯一遇到的问题是Kernel无法挂载ROOT文件系统，主要是没包含NVidia的SATA驱动，去Menuconig打*瞬间解决。出于对GRUB的恐惧，没有在机器大硬盘折腾GRUB，只在grub.cfg加个选项，用原有硬盘GRUB启动我的LFS Linux。

为了制作U盘版本，首先fdisk new a primary partition which is bootable,然后将GRUB放到U盘中。大致命令如下：

#
#sudo mount /dev/sdb1 /mnt
#sudo grub-install --root-directory=/mnt /dev/sdb
#sudo grub
grub>find /boot/grub/stage1
(hd1, 0)
grub>root (hd1)
grub>setup (hd1)
#

而后干了一个比较SB的事情，去Windows下玩了这个U盘，U盘还有另一个无用分区，我在Windows下点选删除此分区，结果整个U盘的分区都被删除了，U盘变成砖头！我晕！！！！！

无奈去Linux下重新fdisk建立分区，还好我之前fdisk建立分区的尺寸是+2G，我这次也用同一参数，找回了之前的分区，数据索性还在。只是我不得不承认我很贱，为何去Windows里面折腾带有Ext3的U盘！

Windows在分区这块太过傲慢，插个自己不认识的U盘，就问你是否需要格式化，一副当带头大哥的嘴脸！Windows何时能放下傲慢？拥抱非FAT/NTFS分区？

partition algorithm



int partition(int array[], int start, int end)
{
int i, j, tmp;
int key = array[start];

i = start;
for (j = start + 1; j <= end; ++j) {
if (array[j] <= key && ++i != j) {
// array[j] <=> array[i]
tmp = array[j];
array[j] = array[i];
array[i] = tmp;
}
}
array[start] = array[i];
array[i] = key;

return i;
}

void printf_array(int array[], int from, int len)
{
int i;
for (i = 0; i < len; ++i)
printf("%d,", array[from + i]);
printf("\n");
}

int main(int argc, char** argv)
{
int array[10] = {3, 7, 21, 6, 2, -3, 90, 23443, -3000, 5};

printf("partition=%d\n", partition(array, 0, 9));
printf_array(array, 0, 10);

return 0;
}