106 OS homework 2-2 成果報告書

組長：a126845、盧贊名
組員：o100442、徐煒員
組員：a126546、謝恩平
github: https://github.com/wei-yuan/xv6-public
(Master)

🙂 使用情境說明

Perf是一套仿造Linux內建的系統效能分析工具，能夠紀錄程序執行時的效能數據，讓開發者可以檢視程式的執行狀況，用以做為改善的依據。

Linux Perf提供相當豐富的各項指標與紀錄，但有不少功能是需要硬體支援，在這次的作業中我們選擇優先實作下列幾項指令，主要是stat與sched以及協助提示用的help、list。

perf stat

perf stat能紀錄執行指令的各項指標，如Context switch的次數、CPU執行時間、等待時間和Page fault的次數等等，例如perf stat cat README可以看到印出README所需要的執行時間、CPU消耗的時間以及其他指標。

操作流程
1.輸入perf stat [CMD] [ARGS]
2.待程式執行完畢後，會印出相關記錄數據

perf sched

xv6 os 中目前沒有實作與 kernel tick 對應的實際秒數，因此下列所指的時間都是指 kernel tick 數目。

perf sched 能夠印出所有 process 的總執行時間，以及在 Round Robin 排程演算法中， process 使用 Time slot 的時間，還有 process 等待執行的時間等資訊。

操作流程
1.在command shell中輸入 perf sched
2.等程式執行完畢後，就會印出關於 process 的各項時間資訊

😇 成功畫面

perf stat

執行 perf stat [Cmd] [Args]

其中 Cmd 為欲測量的 command (此例為 ls, 參數忽略不用)

perf sched

執行 user program

user program 中呼叫 perf sched function

perf help / perf list

user program 中直接呼叫 perf help / perf list function

🏃 實作過程

資料結構

Perf.h

//Perf 測量紀錄(User space)
struct perfdata {
    uint totalticks;  //總耗費時間(ticks)
    uint cputicks;    //CPU耗費時間(ticks)
    int conswch;      //Context switch數量
    int pgfault;      //Page fault數量
    int cpuswch;      //CPU migration數量
};

//Perf 測量指令(User space)
struct perfcmd{
    char* test_cmd;   //測量process指令
    char* cmd;        //Internal use.
    int arg1;         //測量process's pid
};

//Perf 測量紀錄(Kernel space)
struct perf_record{
    int recording;
    int pid;
    int cxtsw;
    int pgfault;
    int _ticks;
    int sumticks;
    int startticks;
    int endticks;
    int cpuid;
    int cpusw;
};

//裝填具有成對結構的輸出項目(User space)
struct perfoutput {
    char* title;
    char* descript;
};

perf 實作(User program)

perf 基本用法主要都是去監視某個指令的執行狀態，因此我們希望能夠讓perf當作Proxy，代User去執行各種指令，並在結束後印出報表。

這邊以perf stat做為例子，首先擷取參數argv[1]來確定要執行的perf指令(stat or sched)，接著fork一個child process，並且呼叫perf_stat()(system call)開始紀錄該process，最後將剩下的參數套入exec執行，等到程序執行完畢wait()被觸發後，再次執行perf_stat()(system call)取回測量結果並印出。

考量到擴充性，因此執行參數與取回結果皆以指標傳遞，以方便未來增減指令時不需另外修改。

perf.c

int main(int argc, char *argv[]){

    //Check arguments
    if(argc <= 1){
        printf(2,"few arguments\n");
        exit();
    }
    
    //perf help
    if(strcmp(argv[1],"help") == 0){
        perf_help();
        exit();
    }

    //perf list 
    if(strcmp(argv[1],"list") == 0){
        perf_list();
        exit();
    }    
    
    /*Memory alloc*/
    struct perfcmd *cmd ;
    struct perfdata *ed ;

    cmd = malloc(sizeof(*cmd));
    memset(cmd, 0, sizeof(*cmd));
    ...

    //perf stat [CMD]
    if(strcmp(argv[1],"stat") == 0){

        //Check arguments
        if(argc < 3){
            printf(2,"few arguments\n");
            exit();
        }

        /* Fork a child process to execute user command*/
        int pid;
        pid = fork();

        if(pid == 0){
          cmd->cmd = "start";
          cmd->arg1 = getpid();
          
          //System call here, start meauring.
          perf_stat(cmd,0);
          
          //Invoke the command we want measured.
          exec(argv[2], &argv[2]);
        }
        
        //Wait until child process to finish.
        wait();
        cmd->test_cmd = argv[2];
        cmd->arg1 = pid;
        cmd->cmd = "end";
        
        //System call here, rerival perf measuring data
        perf_stat(cmd,ed);

        //Print out measuring data
        printf(1, "\nPerformance counter stats for '%s':\n\n", cmd->test_cmd);
        ...

    exit();
}

perf stat 實作 (Kernel)

實作(System call)

perf stat的開始紀錄和取回結果是共用同一隻system call，首次呼叫時傳遞測量的相關參數，在測量結束後再提供空間讓kernel寫回結果。

syscall.h

#define SYS_perf_stat 24

syscall.c

extern int sys_perf_stat(void);
... 
static int (*syscalls[])(void) = {
...
[SYS_perf_stat]  sys_perf_stat,
};

usys.S

SYSCALL(perf_stat)

實作(proc.c)

主要修改都在這支程式，首先是perf_table，功能是提供kernel去紀錄各項指標的變數，先宣告陣列，大小是同時間能存在的最大process數量NPROC，未來可以動態配置以減少空間使用。

struct {
  struct spinlock lock;
  struct perf_record perfs[NPROC];
} perf_table;

接著再pinit()中呼叫initperf進行陣列與lock的初始化。

void 
initperf(void)
{
  initlock(&perf_table.lock,"perf");
  memset(perf_table.perfs, 0, sizeof(perf_table.perfs));
}

初始化到此結束，接下來就等使用者執行perf。

當程序第一次呼叫perf_stat時會執行sys_perf_stat()(system call)，通過user space傳入的pid(cmd->arg1)調用startperf()。

int
sys_perf_stat(void)
{
  struct perfcmd* cmd;
  struct perfdata* data;

  if(argptr(0, (void*)&cmd, sizeof(*cmd)) < 0 || argptr(1, (void*)&data, sizeof(*data)) < 0) {
    return -1;
  }

  if(cmd->arg1<0){
    return -1;
  }  

  if(strcompare(cmd->cmd,"start") == 0){
    startperf(cmd->arg1);
    return 0;
  }

  if(strcompare(cmd->cmd,"end") == 0){
    stopperf(cmd->arg1,data);
    return 0;
  }

  return -1;
}

startperf()首先取得lock並從perf_table中找到第一個沒在使用的空間(recording==0)，並將其初始化後設定recording = 1，釋放lock完成alloc。

struct perf_record* startperf(int pid){
  struct perf_record* i;
  
  acquire(&perf_table.lock);
  for( i = perf_table.perfs; i < &perf_table.perfs[NPROC]; i++){
    if(i->recording)
      continue;
    //found and init;
    i->pid = pid;
    i->cxtsw = 0;
    i->pgfault = 0;
    i->sumticks = 0;
    i->startticks = ticks;
    i->endticks = 0;
    i->cpuid = -1;
    i->cpusw = 0;
    i->_ticks = ticks;
    i->recording = 1;
    release(&perf_table.lock);
    return i;
  }
  
  release(&perf_table.lock);
  return 0;
}

中間的紀錄過程稍後再提，先看當使用者第二次執行sys_perf_stat()(system call)時會附上pid與紀錄用的空間變數指標perfdata，sys_perf_stat()會調用stopperf()，stopperf()會取得lock並將資料寫回perfdata，最後清除旗標recording與釋放lock。

int stopperf(int pid, struct perfdata *data){
  struct perf_record* res = getperf(pid);
  acquire(&perf_table.lock);
  if(res){
    data->conswch = res->cxtsw;
    //Page fault not working...
    data->pgfault = res->pgfault;
    data->totalticks = res->endticks - res->startticks;
    data->cputicks = res->sumticks;
    data->cpuswch = res->cpusw;
    res->recording = 0;
    release(&perf_table.lock);    
    return 0;
  }
  release(&perf_table.lock);
  return -1;
}

特別一提的是，因為在紀錄的過程中是每個pid對應自己的紀錄，因此實際上perf_table的各項資料並非share object，因此是不需要synchronized。但在尋找可用空間與釋放perf_table時，因為是對表操作，因此必須要特別用lock去保護。

實作測量點

在perf stat中測量的指標包含，Page fault次數、Context switch次數、Total ticks計數和CPU ticks計數和CPU Migration次數。

Page fault次數

sysproc.c

xv6 中的記憶體是系統一開始就分配好的，在一般情況下不容易發生 Page fault，因此我們採用 Lazy page allocation，即當 process 需要記憶體時再分配。我們需要在 System call sys_sbrk() 中將 growproc() 系統分配記憶體的程式碼註解掉

int
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;

  // For lazy page allocation
  myproc()->sz += n;
  // if(growproc(n) < 0)
    // return -1;
  return addr;
}

trap.c

於 trap() 增加 switch case 來處理 Page fault，利用當下 proc->sz 來實際分配記憶體，並於此 section 插入 counter，保存的方式與 Context switch 相似，依 pid 取得 perf_record 結構，並賦予值

  // For lazy page allocation 
  case T_PGFLT:
  {
    char *mem;
    // 依 pid 取得 perf_record 結構
    struct perf_record* rec = getperf(myproc()->pid);
    // rcr2() returns the virtual address that caused page fault
    // PGROUNDDOWN() find the address of page round down
    uint va = PGROUNDDOWN(rcr2());
    uint newsz = myproc()->sz;
    if(rec && rec->recording){
      // Page fault 計數
      rec->pgfault++;
    }

    // Until we have allocated enough memory for process
    for(; va < newsz; va += PGSIZE){
      // 申請記憶體空間
      mem = kalloc();
      // 若記憶體不足時的例外處理
      if (mem == 0) {
        cprintf("pid %d trap out of memory--kill proc\n", myproc()->pid);
        myproc()->killed = 1;
        break;
      }
      // 將alloc的位址初始化為0
      memset(mem, 0, PGSIZE);
      // 建立虛擬記憶體與實體記憶體的映射關係，並更新分頁表，以及發生例外的處理    
      if(mappages(myproc()->pgdir, (char*) va, PGSIZE, V2P(mem), PTE_W | PTE_U) < 0){
        cprintf("pid %d trap out of memory--kill proc\n", myproc()->pid);
        kfree(mem);
        myproc()->killed = 1;
        break;
      }
    }
    break;
  }

Context switch次數

proc.c

於 sched() 插入紀錄 Context switch 的函式perf_inc_context_swtch(pid)，並於該函式中將值儲存至 perf_record 結構

void 
perf_inc_context_swtch(int pid){
  // 依 pid 取得 recording 結構
  struct perf_record* r = getperf(pid);
  if(r && r->recording){
    // Context switch 計數
    r->cxtsw ++;
  }
}

...

void
sched(void)
{
  ...
  // 紀錄 Context switch
  perf_inc_context_swtch(p->pid);
  // 發生 Context switch
  swtch(&p->context, mycpu()->scheduler);
  ...
}

Total ticks計數

Total ticks是指程序從開始執行到結束時所耗費的ticks，包含sleeping 和 waiting period，這是最簡單計算的一項紀錄，只要在開始時標上start_ticks，在結束時標上end_ticks即可；開始的部分實作放在startperf()，結束的部分則放在exit()中的perf_end_recording()。

void
exit(void)
{
  ...

  curproc->state = ZOMBIE;
  perf_end_period(curproc->pid);
 
  perf_end_recording(curproc->pid);
 
  sched();
  panic("zombie exit");
}

perf_end_recording()很單純就是透過getperf(pid)找到對應的紀錄並且標上endticks而已。

void perf_end_recording(int pid){
  struct perf_record* r = getperf(pid);
  if(r && r->recording){
    r->endticks = ticks;
    r->recording = 0;
  }
}

CPU ticks計數

CPU ticks則稍微複雜些，主要是因為只紀錄使用CPU時的ticks，所以會有區間的概念，在實作上透過使用perf_record結構中的_ticks和sumticks來紀錄開閉區間。

struct perf_record{
    ...
    int _ticks;
    int sumticks;
    ...
};

流程如下：

1. startperf()初始化_ticks = ticks(目前ticks)
2. Process讓出CPU資源，若不在開區間則panic，反之則累計sumticks += ticks - _ticks && _ticks = -1，進入閉區間。
3. Process取得CPU資源，若不在閉區間則panic，反之則更新_ticks = ticks(目前ticks) 進入開區間。
4. 重複以上流程直到recording == 0

void perf_start_period(int pid){
  struct perf_record* pr = getperf(pid);
  if(pr){
    if(pr->_ticks >= 0){
      panic("_ticks >= 0 ");
    }
    pr->_ticks = ticks;
  }
}

void perf_end_period(int pid){
  struct perf_record* pr = getperf(pid);
  if(pr){
    if(pr->_ticks<0){
      panic("_ticks < 0 ");
    }
    pr->sumticks += ticks - pr->_ticks;
    pr->_ticks = -1;
  }
}

進入開區間的點只有一個，也就是被cpu schedulers選中的時候，執行perf_start_period(pid)進入開區間。

void
scheduler(void)
{
    ...
    c->proc = p;
    switchuvm(p);
      
    perf_start_period(p->pid);
    
    p->state = RUNNING;
    swtch(&(c->scheduler), p->context);
    ...
}

但在xv6中封閉區間的觸發點則有多個進入點，分別是呼叫sleep()、執行時間用盡yield()以及執行完畢exit()，都會觸發perf_end_period(pid)紀錄並封閉區間。

void
sleep(void *chan, struct spinlock *lk)
{
  ...
  p->chan = chan;
  p->state = SLEEPING;
  perf_end_period(p->pid);
  sched();
  ...
}

void
exit(void)
{
  ...
  // Jump into the scheduler, never to return.
  curproc->state = ZOMBIE;
  perf_end_period(curproc->pid);
  ...
}

void
yield(void)
{
  acquire(&ptable.lock);  //DOC: yieldlock
  myproc()->state = RUNNABLE;
  perf_end_period(myproc()->pid);
  sched();
  release(&ptable.lock);
}

最後通過sumticks 累計就可以獲得總計的CPU執行時間。

CPU migrations

CPU migrations 即 process 運行過程中發生 CPU 切換的次數，我們利用 perf_record 結構中的 cpuid 與 cpusw 來分辨 CPU 與紀錄切換次數

struct perf_record{
    ...
    int cpuid;
    int cpusw;
};

於 scheduler() 分配 process 時，利用 perf_add_if_cpu_sw() 取得當前的 APIC ID，即可判斷目前 process 在哪顆 CPU 上運行，再與前一次的紀錄作比對，若不同則代表 CPU 切換過，並做計數

void perf_add_if_cpu_sw(int pid, int apicid){
    struct perf_record* pr = getperf(pid);
    if(pr){
      if(pr->cpuid != -1 && pr->cpuid!=apicid)
        pr->cpusw++;
      pr->cpuid = apicid;
    }
}

void
scheduler(void)
{
    ...
    /* round robin scheduling */
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      ...
      c->proc = p;
      switchuvm(p);
      // 紀錄 CPU migrations
      perf_add_if_cpu_sw(p->pid, c->apicid);
      perf_start_period(p->pid);
      p->state = RUNNING;
      swtch(&(c->scheduler), p->context);
      switchkvm();
      ...
    }
    ...
}

perf sched

perf sched 的部分，則是按照前述的部分，註冊 system call 即可。

Header file

syscall.h

#define SYS_psched 23

syscall.c

extern int sys_psched(void);
... 
static int (*syscalls[])(void) = {
...
[SYS_psched]  sys_psched,
};

Assembly

usys.S

SYSCALL(psched)

實作檔

sysproc.c

在 xv6 中，process 本身有6種不同的狀態，分別是尚未使用, 被配置, 準備 run, 正在 run, 等待 I/O 以及 exiting。

要紀錄時間，在 process 對應的狀態，插入必要的紀錄 tick 函式即可。

// 程式碼內容較多，因此以 psuedo code 解釋 
sys_psched(void)
{
  // 指向 proc 這個 struct 的 pointer
  struct proc *p;
  struct recproc *rp;
  // 列出所有的 process state
  static char *states[] = {
  [UNUSED]    "unused",
          ...
  };  
  char *state;

  cprintf("PID\t|\tState\t|\tStart\t|\tEnd\t|\tDuration\t|\tName\t\n");  

  // loop 過 ptable 中的所有 process，將目前 ptable 中的資料拷貝到自定義(self-defined)的 rectable
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
  {
    //當 pid = 0，代表該欄為空，停止複製 ptable 中的資訊
    if(p->pid == 0) break;
    //state 為 UNUSED，跳過檢查下一個 process 
    if(p->state == UNUSED)
      continue;

    //複製 process 資訊
    rp = rectable.recproc; // rp init
    if(p->state >= 0 && p->state < NELEM(states) && states[p->state])
    { 
      rp->state = p->state;
      state = states[rp->state];
    }      
    else
      state = "???";
    
    rp->pid = p->pid;
    rp->startTicks = p->startTicks;
    rp->endTicks = p->endTicks;
    safestrcpy(rp->name, p->name, sizeof(rp->name)); 
        
    // 以內建的 cprintf() 函式印出結果
  }
  return 1;
}

User program

在 xv6 資料夾中新增檔案，檔名叫作user_test_psched.c，用來呼叫自行定義的 system call psched()

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

int 
main(void)
{
    int err = 0;

    err = psched(); //若成功，印出 perf sched 的結果並回傳 1

    if(err == 1)
    {
        //Do nothing
    } 
    else
    {
        printf(1, "\nTest system call psched fail: %d\n", err);
    }
        
    exit();
}

perf help / perf list

perf.c

將字串提出來常數化，若往後有新增項目直接增加到成對結構裡，不用動到 function

// 將字串都常數化
const char hardware_event[] = "[Hardware event]";
const char software_event[] = "[Software event]";
const char Hardware_cache_event[] = "[Hardware cache event]";
const char list_event_message[] = "List of pre-defined events:";
const char usage_message[] = "usage: perf [FLAG] COMMAND [ARGS]";
const char common_message[] = "The most commonly used perf commands are:";

// 裝填到成對的結構裡
struct perfoutput help_output[] = {
    { "list", "List all symbolic event types" },
    { "stat", "Run a command and gather performance counter statistics" },
    { "sched", "Tool to trace/measure scheduler properties (latencies)" }
};
struct perfoutput list_output[] = {
  { "cpu-migrations OR migrations", software_event },    
  { "cpu-ticks", software_event },  
  { "page-faults OR faults", software_event },
  { "context-switches OR cs", software_event }
};

...

int
perf_help(void)
{
  int i, array_size;
  array_size = sizeof(help_output) / sizeof(struct perfoutput);
  cprintf("\n %s\n\n", usage_message);
  cprintf(" %s\n", common_message);
  // 迭代輸出
  for (i = 0; i < array_size; i++) {
    cprintf("   %s%s\n", help_output[i].title, help_output[i].descript);
  }
  cprintf("\n");
  return 0;
}

int
perf_list(void)
{
  int i, array_size;
  array_size = sizeof(list_output) / sizeof(struct perfoutput);
  cprintf("\n %s\n\n", list_event_message);
  // 迭代輸出
  for (i = 0; i < array_size; i++) {
    cprintf("   %s%s\n", list_output[i].title, list_output[i].descript);
  }
  cprintf("\n");
  return 0;
}

😎 結論

perf stat

實作上分別面臨幾項挑戰

1. Context switch：找到 scheduler 中做 swtch 的時機，並於此 section 依據 pid 去紀錄各 process 發生 Context switch 的次數即可，是相對較好實作的項目
2. Page fault：解決問題前需先創造問題，我們試著自己去分配 process 所需要的記憶體，讓 Page fault 發生，但很可惜，目前我們僅捕捉到 fork 階段所產生的 Page fault，而 stat 要記錄的時機卻是在 fork 之後，因此這部分還需要努力
3. CPU cycles：本來想透過rdtsc印出CPU cycles，但很困擾的是透過Assembly取得的是64bit(unsigned long long)的資料，在xv6下沒辦法直接顯示，必須要用assembly實作64bit的除法和取餘。

perf sched

這個 API 需要去追蹤所有的 process 切換狀態的時間點，同時記下在某個狀態執行的時間長度為多少。

也就是 process 在 xv6 Round Robin 排程演算法的 Time slot 中，花費了多少 kernel ticks。

因此需要有一張紀錄所有 process 資訊的 process table，記下在當下 time slot 的起始、結束時間點，以及截至目前累計的 ticks。

process 結束時，主要會有 3 種可能的狀況，分別是中斷(yield)、睡眠(sleeping) 以及 離開(exit) 。這三個函式分別由proc.c 中的 yield()、sleep()以及exit()函式中進行處理，因此必須要在這些程式模組中加入紀錄結束 ticks 的函式 。

因此，實作上主要的難點在於:

1. 如何新增一個 system call 與 process table
2. 找到 process 最終會前往哪3個主要函式，在這些函式中加入紀錄用的自定義函式
3. 為了避免 process 進入函式後發生同時修改的 race condition，需要限定同個 pid 的 process，只能有一個人能夠修改，讓該 process lock 住，修改完再釋放。下一個相同 pid 的需要排隊，等前一個相同 pid 的 process 改完，釋放 lock 之後，才能繼續修改。

若上述 3 點都能達成，則 system call perf 中的選項 sched 就完成了。

perf help / perf list

此項目較無難度，只要事前確認好 spec，將結果輸出即可

📅 組員分工