一、Add System Call


In this exercise you’ll add a feature to xv6 that periodically alerts a process as it uses CPU time. This might be useful for compute-bound processes that want to limit how much CPU time they chew up, or for processes that want to compute but also want to take some periodic action.

添加一个系统调用:alarm(interval, handler)

If an application calls alarm(n, fn), then after every n “ticks” of CPU time that the program consumes, the kernel will cause application function fn to be called. When fn returns, the application will resume where it left off.

A tick is a fairly arbitrary unit of time in xv6, determined by how often a hardware timer generates interrupts.

添加一个用户程序 alarmtest.c,代码如下:

#include "types.h"
#include "stat.h"
#include "user.h"

void periodic();

int main(int argc, char *argv[])
{
  int i;
  printf(1, "alarmtest starting\n");
  alarm(10, periodic);
  for(i = 0; i < 25*500000; i++){
    if((i % 250000) == 0)
      write(2, ".", 1);
  }
  exit();
}

void
periodic()
{
  printf(1, "alarm!\n");
}

The program calls alarm(10, periodic) to ask the kernel to force a call to periodic() every 10 ticks, and then spins for a while.

大致步骤同前一个作业HW: System Calls的实现:

you’ll need to modify the Makefile to cause alarmtest.c to be compiled as an xv6 user program.

UPROGS=\
	_cat\
	_echo\
	_forktest\
	_grep\
	_init\
	_kill\
	_ln\
	_ls\
	_mkdir\
	_rm\
	_sh\
	_stressfs\
	_usertests\
	_wc\
	_zombie\
	_date\
	_alarmtest\

put the right declaration in user.h

int alarm(int ticks, void (*handler)());

You will also have to update syscall.h and usys.S to allow alarmtest to invoke the alarm system call.

在 syscall.h 中添加:

#define SYS_alarm  23

在 usys.S 中添加:

SYSCALL(alarm)

Your sys_alarm() should store the alarm interval and the pointer to the handler function in new fields in the proc structure; see proc.h.

struct proc 中添加两个成员:

// add for alarmtest.c
int alarmticks;
void (*alarmhandler)();

并在 sysproc.c 中添加如下代码:

int sys_alarm(void)
{
  int ticks;
  void (*handler)();
  if(argint(0, &ticks) < 0)
    return -1;
  if(argptr(1, (char**)&handler, 1) < 0)
    return -1;
  /*获取到alarm()系统调用参数后,将其赋值给当前进程的成员*/
  myproc()->alarmticks = ticks;
  myproc()->alarmhandler = handler;
  return 0;
}

Add an entry for SYS_ALARM to the syscalls arrays in syscall.c

extern int sys_alarm(void);
[SYS_alarm] sys_alarm

You’ll need to keep track of how many ticks have passed since the last call (or are left until the next call) to a process’s alarm handler; you’ll need a new field in struct proc for this too. You can initialize proc fields in allocproc() in proc.c.

再在 struct proc 结构体中添加一个成员:

int tick_counts;

并且选择在 proc.c/allocproc() 中初始化这个成员:

p->tick_counts = 0;

Every tick, the hardware clock forces an interrupt, which is handled in trap() by case T_IRQ0 + IRQ_TIMER; you should add some code here.

在上面的 case 子句里处理 timer interrupt。

 

二、Add Timer Interrupt Handler


到这里我们可以梳理一下这个作业要求的整个脉络,首先在用户程序 alarmtest 里执行一个系统调用 alarm(),该系统调用的最终目的就是在 sys_alarm() 函数里,将系统调用的两个参数保存进 struct proc 结构体,最后结束系统调用,返回到用户态。这一步的目的是为 timer interrupt 准备一些数据。

剩下的就是通过 timer interrupt 来定时的提醒 kernel 去调用一个函数,这个函数是通过 alarm() 第二个参数指定的,是一个用户态函数。

kernel 通过在 trap() 函数的 case 子句(如下)里添加相应的处理,来达到定时调用的目的。

+-----+    trap      +------------------------+
| for |------------> |timer interrupt hanlder |  
+-----+              +------------------------+
   ^                         |
   |                         |
+----------+                 |
| periodic | <---------------+ 
+----------+

整个处理顺序大致如上,在执行 for 循环的时候,接受到硬件中断timer interrupt,陷入后,执行 trap() 函数对应的 case 子句,case 子句将用户态的返回点换成绑定的 periodic() 函数,执行完此函数后,再接着 for 语句执行,后面就是反复的执行这几步。

这里面有两个难点:一是返回用户态后执行 periodic(),二是执行完 periodic() 后返回到 for 循环上次停止的地方接着执行。

具体代码如下:

case T_IRQ0 + IRQ_TIMER:
  if(cpuid() == 0){
    acquire(&tickslock);
    ticks++;
    wakeup(&ticks);
    release(&tickslock);
  }
  lapiceoi();
  if (myproc() != 0 && (tf->cs & 3) == 3)   /*只处理在用户态时接受到的timer中断*/
  {
    myproc()->tick_counts++;
    if (myproc()->tick_counts == myproc()->alarmticks)
    {
      tf->esp -= 4;
      *((uint *)(tf->esp)) = tf->eip; /*首先需要保存现在trapframe中的eip值,也就是在for循环中停止(陷入)的地方*/
      /*
       * 因为这里执行完后就要返回,并restore trapframe里的值到寄存器,恢复到用户态了,
       * 所以将trapframe里的eip设置为alarmhandler函数的值,使一返回到用户态就执行alarmhandler里保存的函数
       */ 
      tf->eip = (uint)myproc()->alarmhandler; 
      myproc()->tick_counts = 0;
    }      
  }   

其实关键工作就是在返回用户态之前,设置好用户栈的结构,大致如下:

 stack
+-----+
|     |               
|     |        
|     |               
+-----+
| eip | return address
+-----+ <- esp -= 4 --+
|     |               |
|     |        stackframe for periodic()
|     |               |
+-----+ --------------+

中间的 eip 的值等于 for 循环中发生中断时的下一条指令的地址,把 eip 设置在这个地方,相当于设置了 main 函数栈帧的 return address,只不过这个 return address 由我们自己设置,正常情况下在用户态通过 call 指令,会形成这个 return address。

 

三、总结


由于之前的作业已经添加过系统调用,所以这个作业的重点在第二部分,设置用户栈。还要区分硬件中断与系统调用的区别,虽然他们都是通过 IDT 进入内核,但性质是不一样的。

The kernel “upcall” to periodic() is a simplified UNIX signal.

看 signal 函数:

sighandler_t signal(int signum, sighandler_t handler);

UNIX 中的信号范围更广一些,它能注册处理更多的中断,例如将第一个参数设置为 SIGINT(interrupt from keyboard),当产生一个来自键盘的中断后,就会执行注册的用户态函数 hanlder,与 int alarm(int ticks, void (*handler)()) 有异曲同工之妙。

3.1、Q & A

Q: what’s the security problem in my new trap() code?

由于系统调用可以被硬件中断打断,所以有可能在内核函数 sys_alarm() 还没完成之前,就来了一个 timer interrupt,我们应该进行相应的设置,不让 trap() 函数处理这个中断(来太早了)。由于这时是处于内核态,将寄存器的值压入内核栈,%cs 中 CPL 为 0,所以利用 (tf->cs & 3) == 3 来防止太早到来的 timer 中断。

Q: what if trap() directly called alarmhandler()?

在 alarmhandler() 中可能会有产生其它系统调用,例如上面 periodic() 中的 printf() 就会产生系统调用,注意这时的系统调用是在内核态中产生的(没有特权级的切换)。在 xv6-book 中说明了,如果没有特权级的切换,int 指令不会将 %ss 和 %esp 的值压栈:

+------+ -----+
| ss   |      |
+------+      |-> only present on privilege change
| esp  |      |
+------+ -----+
|eflags|
+------+
| cs   |
+------+
|  ..  |
+------+

Kernel stack after an int instruction

记住这一点后,来看一下调用 printf() 形成的内核栈调用链:

+-----------+
|  printf() |
+-----------+
      |
     \/
+-----------+
|  write()  |
+-----------+
      |
     \/       -----int 64陷入内核-------
+-----------+
|sys_write()|
+-----------+
      |
     \/
+-----------+
| argint()  |
+-----------+  

关键就在 argint() 函数:

// Fetch the nth 32-bit system call argument.
int argint(int n, int *ip)
{
  /*虽然此时栈指针已经切换到了内核栈, 但是不妨碍通过trapframe中的用户栈地址去获取用户栈上的参数*/
  return fetchint((myproc()->tf->esp) + 4 + 4 * n, ip);
}

上面说了由于没有特权级的切换,所以 myproc()->tf->esp 的值是无效的:取不到系统调用正确的参数。所以,一般来说,不能在内核态中调用用户态的代码,因为这些代码中很有可能包含系统调用。

it is disturbing how close this came to working!

  1. why can kernel code directly jump to user instructions? 因为它们都是使用的同一张页表。
  2. why can user instructions modify the kernel stack? 因为user instruction是在内核态执行的。
  3. why do system calls (INT) work from the kernel? 因为kernel拥有最高特权级。

3.2、Interrupt introduces Concurrency

my code:             interrupt:
_______________________________
                   |
%eax = 0;          |
if (%eax = 0) then | %eax = 1;
  func();          |

这种情况下 func() 可能会执行可能不会执行。这种现象是致命的,为了避免,首先想到的就是:To make a block of code “atomic”, turn off-on interrupts with cli() and sti().

这是我们学习 xv6 的过程中第一次见到 Concurrency 的概念,后面讨论锁的时候还会详细介绍 Concurrency 相关的知识。

3.2、Interrupt vs Polling

对于磁盘这种低速设备来说,使用 interrupt 是相对划算的。而如果遇到高速设备(例如网卡),每秒钟接受上百万的网络包,频繁的中断会频繁的 sava/restore register,这是很大一笔开销。为了避免这种情况,使用另一个解决方案:Polling(another way of interacting with device)

Processor spins until device wants attention. Wastes processor cycles if device is slow. But inexpensive if device is fast. No saving of registers etc. If events are always waiting, no need to keep alerting the software

Interrupt vs Polling:

  1. Polling rather than interrupting, for high-rate devices
  2. Interrupt for low-rate devices, e.g. keyboard
  3. Switch between polling and interrupting automatically: interrupt when rate is low (and polling would waste CPU cycles); poll when rate is high(and interrupting would waste CPU cycles)
  4. Faster forwarding of interrupts to user space
    • for page faults and user-handled devices
    • h/w delivers directly to user, w/o kernel intervention?
    • faster forwarding path through kernel?