庖丁解牛Linux内核笔记: 操作系统是如何工作的 - 一个简单的时间片轮转躲到程序内核代码

Linux OS Note

作者：Sandy 原创作品转载请注明出处
《Linux内核分析》MOOC课程http://mooc.study.163.com/learn/USTC-1000072000
依照学术诚信条款，我保证此回答为本人原创，所有回答中引用的外部材料已经做了出处标记。

#

函数的堆栈框架

分析流程

• 第一步: 初始状态

  • 注意一开始的esp, ebp分别指向了栈顶和栈底. 如下图所示: . 注意此时栈中是调用者堆栈框架. 即main的堆栈框架.

• 第二步: push %ebp

  • 注意老师的表示方法. 箭头表明ebp此时的值(其实可以放入值, 像lab1一样). 如下图所示:

• 第三步: movl %esp, %ebp

  • 然后update ebp(栈顶指针), 指向esp处. .
  • 此时, 一个新的堆栈就建立好了.

• 第四步: return x+y

  • 如下图所示: , 先把main中保存的参数存到reg: eax中, 并相加.
  • 局部变量保存在栈中, 所以用变址寻址来获得x,y.
  • 返回值通过eax寄存器传递.

知识点

观察main中的局部变量

• 为什么开头除了push, mov建立堆栈, 还要sub esp呢? 原来老的编译器都是要求在函数的开头部分声明局部变量, 从而在堆栈中留下空地. 所以K&R(?)中都是把变量声明放在了函数的开头, 不仅仅是便于debug, 还是由于stack/compiler的缘故.
• 如课件所述: 几个局部变量存在esp空出来的0x18个空间中.
  

中断

如何实现中断? ---> kernel stack

• 讲完3大法宝的存储程序计算机模型, 函数调用堆栈. 轮到第3个了.
• 由CPU和kernel代码共同实现了保存现场和恢复现场. 将EIP, EBP, ESP保存到kernel stack中.

mykernel基础上构造一个简单的操作系统内核

Clang中潜入汇编代码

• 语法一句话表述就是: asm("statement": output_regs: input_regs: clobbered_regs);

__asm__ volatile(
    汇编语句模版:
    输出部分:
    输入部分:
    破坏描述部分);

• 举个例子:

int main()
{
    *val1+val2=val3*/
    unsigned int val1 = 1;
    unsigned int val2 = 2;
    unsigned int val3 = 0;
    printf("val1:%d,val2:%d,val3:%d\n",val1,val2,val3);
    asm volatile(
    "movl $0,%%eax\n\t" /*clear %eax to 0*/
    "addl %1,%%eax\n\t" /*%eax += val1*/
    "addl %2,%%eax\n\t" /*%eax += val2*/
    "movl %%eax,%0\n\t" /*val2 = %eax*/
    : "=m" (val3) /* output =m mean only write output memory variable*/
    : "c" (val1),"d" (val2) /*input c or d mean %ecx/%edx*/
    );
    printf("val1:%d+val2:%d=val3:%d\n",val1,val2,val3);
    return 0
}

• 分析如下:

  • line 8~12: statements.
    
    • 注意2点:
      
      • (1) 平时的1个%, 这里用2个.
      • (2) %1, %2, ..., %k. 表示I/O regs. 从output_regs开始排起.
  • line 13: output_regs. 注意这里的=m表示write-only的, 内存变量.
  • line 14: input_regs. 注意"c", "d"分别表示用%ecx, %edx保存val1, val2.

• 在output/input_regs中都可以在每一个var前面使用限定符. 例如"c", "d", "=m".

一个简单的操作系统内核源代码

先分析一下3个文件的关系

• 由2个c文件, 和1个头文件组成.
• mypcb.h: 定义了2个常数: MAX_TASK_NUM, KERNEL_STACK_SIZE. 以及2个struct: Thread, PCB. 以及一个function的declaration: my_schedule().
• mymain.c: 定义了3个var: task[], my_current_task, my_need_sched. 以及定义了2个function: my_start_kernel, my_process. 用于内核初始化和0号进程启动
• myinterrupt.c: 使用extern表明了mymain中定义的3个var(我有个问题: 为什么要定义extern? 为什么不放在header里?), 一个local var, 定义了2个function: my_timer_handler, my_schedule.

关键点

• my_start_kernel是mykernel的入口函数. 应该是patch修改了kernel的start point. (要求证一下)
• my_start_kernel中的内联汇编: 他的作用是初始化了0号进程的stack和入口, 并在ret之后立即启动process 0! my_process()中使用的是主动调度: 1千万cpu tick才调度一次.
• myinterrupt.time_count即时间片. my_timer_handler()设置时间片的大小, 时间片用完时设置一下调度标志., 时钟中断发生1000次且my_need_sched为0, 则使能调度.

• myinterrupt.my_schedule里面的movl $1f,%1中$1f是forwarding 标号1的位置, 果然见到下面隔2行就是1:. 但是问题是: 在else中也有movl $1f, %1, 但是else里面的内联汇编中没有label 1! 其实老师在论坛里面回答了:

  这里分几种情况：1）两个正在运行的进程之间切换；2）新进程执行或切换到一个新进程
  对于2显然需要通过ret修改eip指向新进程的起点，而对于1需要先保存当前进程的eip（即movl $1f,%1\n\t）然后恢复即将执行的下一个进程的eip，这里与2相同通过ret修改eip，只是这里eip指向的是1:\t的位置即$1f，为什么呢？因为即将执行的下一个进程的eip曾经被切换出去过，怎么被切换出去的？即movl $1f, %1\n\t。
  这里有个鸡生蛋蛋生鸡的循环，理解起来稍动脑筋，新进程的执行就是现有鸡还是现有蛋的问题.
  孟宁老师2015-7-28

• 而且segmentFault帖子里面也回答了, 我觉得这个更好理解!

  对论坛上 else中movl $1f,%1\n\t 的问题，看到老师的回复是$1f放到eip里使用才算生效吧，不能见$1f就找标号1。我的理解是这样的：if中的自然不必说，else中代码只有进程第一次被执行的时候才会运行，此时将$1f存入prev->thread.ip，但当进程被重新调度执行的时候，此时进入了if代码块中，因此将执行if代码块中的1：标号处的代码，所以else中没有"1："也就不奇怪了。

• 计算机硬件的3大法宝是: 存储程序计算机模型, 程序调用堆栈, 和中断. 同样, 操作系统的"两把剑": 中断上下文和进程上下文的切换.

mykernel实验指导（操作系统是如何工作的）

数据结构分析 (CPU-specific state of this task)

struct Thread

• 为什么是thread呢?
• ip : instruction pointer. 指向该进程下一条执行指令的地址
• sp : stack pointer. 该进程的堆栈的栈顶指针, 初始化为stack[KERNEL_STACK_SIZE-1], 即bp. 注意: linux kernel中, 每一个process都有2个stacks: kernel space堆栈, user space堆栈. 这里简化为只有1个kernel space stack.

分析流程

• 入口: init/main.c的start_kernel(void)的最后call: myinterrupt中的mymain.c的my_start_kernel(void).

• mykernel实现的是一个简单的时间片轮转多道程序. 重点是进程的启动和切换机制. 是由内联汇编实现的(eip处理以及函数堆栈的恢复与建立).

进入my_start_kernel

• 进入my_start_kernel

  • 先是在该function的前半部分初始化task[0]~task[3], 并将他们连起来成为一个闭合的单向链表. 这就是PCB链表, 让kernel可以完全的控制和了解所有process的状态, 从而schedule.
  • 然后在后半部分的asm中, 启动process 0.
  • 重点:
    
    • 当前处在哪一个stack是由当前的esp决定的, 所以第一句: movl %1,%%esp使得我们进入了task[0].stack
    • 进入task[0].stack并不是开始process 0! 只有在ret结束的时候, 才开始process 0. 由于eip指向task[0].thread.ip = &my_process. 所以process 0跑my_process. 如果eip是另一个值, 则process 0跑另一个function.
    • inline asm部分只是显式地操作eip/ebp. 在所有function的调用中, 开头结尾都是enter/leave. 即保存/恢复context!

• 开始asm的my_start_kernel的stack如下: ![00]

• movl %1,%%esp\n\t: 将task[0].thread.sp赋值给esp, 这一句将我们导引到task[0]的stack. 因为task[0].thread.sp初始值是task[0]堆栈的base.
• pushl %1\n\t: 将esp压栈, 或者说ebp.
• pushl %0: 将task[0].thread.ip压栈, 初始值是&my_process.
• ret: 将esp指向的slot的value赋值给eip, 并回退esp. 从而开始process 0.

第一次进入my_process. 这是进程0的.

• 在1000,0000个tick之后, 检查my_need_sched是否为1. 如果是, 则设置为0, 并进入my_schedule.
  
  • 这个global var my_need_sched是在my_timer_handler中改变. 这个ISR被时钟中断触发, 没1000个time interval则会处理1次. 可以通过改变这里的常数来控制主动调动的时间间隔.
• 之所以称之为主动调度是因为my_process调用的my_schedule而不是linux一般的自己的系统调度器来调度process.

进入my_schedule. 开始从process 0到process 1的处理.

• 当第一次满足调动, 则进入my_schedule. 和往常的函数调用一样,会再进入my_schedule的开头保存context.

• 进入my_schedule中, 先调度: next设置为下一个node, 即task[1], prev=task[0].

• 注意: 由于task[0]没有运行过, 所以初始状态时unrunnable. 所以进入else. 将next的状态设置为runnable, current_task为task[1]. 进入switch to new process的inline asm.

• 注意task[0]中的ebp, esp已经update. 因为function call, 以及内部变量. 注意此时还是位于task[0]的stack 所以如图所示.

• pushl %%ebp: 压栈ebp
• movl %%esp,%0: 保存esp到prev->thread.sp. 即task[0]->thread.sp. 这是为了在proc0切入proc1之前保护proc0的context. 从而在schedule会proc0的时候可以恢复现场. (Q: 为什么只把esp存到pcb.thread?)
• movl %2,%%esp: 恢复esp为next->thread.sp.
• movl %2,%%ebp: 恢复ebp为next->thread.sp. 此刻进入task[1]的stack. 注意thread.sp初始值为task[1]的栈顶.

• movl $1f,%1: 这个是一个难点, 按照老师的回复:

  它把label 1的地址保存到prev->thread.ip. 虽然是forwarding. 但实际上compile之后, 是在运行的时候才将forwarding作为寻找方向. 因为prev->thread.ip只有在if中才用到. 所以不会有问题. (Q: 实际上, 我在compile optimization中将o2改成o1则会出现找不到label的问题...)

• pushl %3: 将next->thread.ip保存起来, 即task[1]->thread.ip. 即初始值: &my_process.

• ret: 将my_process pop给eip. 此时开始process 1的my_process. 在一定时候之后, 满足调度条件. 准备process 1切到process 2.

process 2,3

• 由于是顺序执行. 所以process 1切入process 2, 运行process 2的my_process, 一次类推进入process 3, 然后切回process 1是一个略过他们的stack分析. 直接分析process 3切回process 0.

process 1切回process 0, 调用my_schedule

• 由于process 0的task[0].state=0. 所以是2个运行的process的调度. 所以是进入if. 注意此时stack中ebp, esp.
• 此时next=task[0], prev=task[1].
• pushl %%ebp: 保存ebp
• movl %%esp, $0: 保存esp到prev->thread.sp. ebp压栈, 而esp保存到pcb的thread.sp是为什么呢?
• movl %2,%%esp: 读取esp. 将esp设置为next->thread.sp. 从而esp又回到了task[0]的堆栈. 注意这个值在从0->1的时候已经保存到PCB.thread中, 是指向task[0]的栈顶. 此处保存了old ebp.
• movl $1f,%1: 保存eip, 即将eip指向label 1.
• pushl %3: 将next->thread.ip压栈. 为进入process 0的process设置eip.
• ret: 结合上一句, eip回到了process 0. 即label 1处, 于是popl ebp, 所以一个个的退回old ebp, 回到了my_start_kernel中inline asm的ret后的popl ebp.
• 这一步将eip继续走到my_schedule的return, 从而完成proc 0对my_schedule的调用, 从而结束process 0的my_process, 然后继续无线轮回: process 0->process 1->process 2->process 3->process 0-> ...

总结分析

• 分析流程中使我加强了我对画图分析的能力, 因为lab1中分析简单的function call都会由于画stack中间, 停了几分钟, 回过头来就不记得eip到哪里了. 所以画图分析一定要写下来当前的eip, data struct的state, 要写有用的注释!
• 分析流程并不是目的, 这只是为了理解老师的my_kernel的实现. 重要的是: PCB数据结构的设计, 以及my_schedule, my_process, my_time_handler的设计. 特别是其中的inline asm.