Linux Project 2

# Linux Project 2 ### Team 27 : - 108602532 王鼎元 - 109502002 黃文翰 - 109502519 張傑誌 > [題目](https://staff.csie.ncu.edu.tw/hsufh/COURSES/FALL2023/linux_project_2.html) ## Kernel & OS version, VM - Linux Kernel 5.15.137 - [Ubuntu 20.04 LTS](https://releases.ubuntu.com/focal/ubuntu-20.04.6-desktop-amd64.iso) - [Virtual Box 7.0.12](https://download.virtualbox.org/virtualbox/7.0.12/VirtualBox-7.0.12-159484-Win.exe) ## 新增system call 至kernal 原始碼中 #### 主要流程參考助教公布的教學: > [Add a system call to kernel](https://hackmd.io/aist49C9R46-vaBIlP3LDA?view) **桌面 > 右鍵 > Open in terminal** #### 準備系統 ```bash # 管理員權限 su # 更新apt sudo apt update && sudo apt upgrade -y # 安裝需要的package sudo apt install build-essential libncurses-dev libssl-dev libelf-dev bison flex -y # 清除安裝的package sudo apt clean && sudo apt autoremove -y # 下載 kernel source code & 解壓縮 wget -P ~/ https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.15.137.tar.xz tar -xvf linux-5.15.137.tar.xz -C /usr/src ``` #### 在process descriptor當中新增 my_fixed_priority欄位: 按照 Hint 1 的提示，將新增的欄位新增在task_struct最下方，但要在thread_struct上面，才不會影響到當中其他有時候會用offset傳遞的欄位，之所以要在thread_struct上面，是因為thread_struct包含一個可變大小的結構，並且必須位於task_struct的最後面開啟 ```bash # 開啟檔案 nano include/linux/sched.h # 找到 task_struct並在thread_struct上面一行加入以下程式碼 int my_fixed_priority ``` #### 初始化 my_fixed_priority的值按照 Hint 2，在process透過copy_process()創建的時候，在copy_process()當中初始化my_fixed_priority的值 ```bash # 開啟檔案 nano kernel/fork.c # 找到 struct task_struct *copy_process ，並在其中加入以下程式碼 current -> my_fixed_priority = 0; ``` #### 新增system call ```bash # 進入source code資料夾 cd /usr/src/linux-5.15.137 # 新增system call程式資料夾 mkdir my_set_process_priority # 進入資料夾 cd my_set_process_priority # 建立system call 程式碼 nano my_set_process_priority.c ``` System call 目的為將傳入的 priority 數值傳入process descriptor的my_fixed_priority欄位當中 #### System call 程式碼 (Kernel space code): ```c #include <linux/kernel.h> #include <linux/syscalls.h> #include <linux/sched.h> #include <linux/random.h> SYSCALL_DEFINE1(my_set_process_priority, int, x) { // Check if x is valid (101~139) if (x < 101 || x > 139) return 0; current-> my_fixed_priority = x; return 1; } ``` #### 在context switch之後將priority 設定為system call 給定之數字依照題目要求，每次context switch之後都要將process的priority設定為system call給定的值由於在__schedule()當中，kernel會將cpu使用權交給下一個process 因此在__schedule()結束後將 system call指定的priority設定為process的priority - [StackOverflow](https://stackoverflow.com/questions/45125500/how-to-add-a-member-to-task-struct-to-bypass-compiletime-assert) ```bash # 開啟檔案 nano /kernel/sched/core.c # 找到 __schedule(SM_NONE); 並在其下一行加入以下程式碼 if(current -> my_fixed_priority) current -> static_prio = current -> my_fixed_priority; ``` #### 修改 kernel 原始碼 ```bash # 建立新的 Makefile nano Makefile # 在Makefile中輸入以下內容並儲存 obj-y := my_set_process_priority.o # 修改上個目錄的Makefile cd .. nano Makefile # 將此行最後新增 my_get_physical_addresses/ core-y += kernel/ certs/ mm/ fs/ ipc/ security/ crypto/ 變成 core-y += kernel/ certs/ mm/ fs/ ipc/ security/ crypto/ my_set_process_priority/ (nano 中可以用 Ctrl+Q 進行搜尋) # 修改 syscall_64.tbl 檔 nano arch/x86/entry/syscalls/syscall_64.tbl # 增加新的system call，在process_mrelease下一行新增system call，編號應為449 449 common my_set_process_priority sys_my_set_process_priority # 修改 syscalls.h 檔 nano include/linux/syscalls.h # 在最下面一行的 #endif 之前加入下段文字 (Ctrl+Q) asmlinkage long sys_my_set_process_priority(void); ``` ## Kernel 編譯 #### 亦參考助教公布的: > [Add a system call to kernel](https://hackmd.io/aist49C9R46-vaBIlP3LDA?view) ```bash # 設定組態 make localmodconfig # 查看邏輯核心數量 nproc # make 時輸入剛剛看到的核心數量 make -j14 # 安裝kernel sudo make modules_install -j14 sudo make install -j14 # 更新作業系統的bootloader成新的kernel sudo update-grub # 重新啟動 reboot # 查看有沒有成功更新kernel uname -r ``` **更新成功的話應該會顯示 5.15.137** ### 我們遇到的問題: 1. [No rule to make target ‘debian/canonical-certs.pem‘, needed by ‘certs/x509_certificate_list](https://blog.csdn.net/m0_47696151/article/details/121574718) 2. 一開始使用 WSL 一直失敗，經過查詢後發現應該是因為 WSL 使用的 kernel 不是 Linux 而是 WSL 自己的 kernel，想要在 WSL 當中新增新的 System call 應該要下載 WSL 的 kernel source code，WSL 也是 open source，因此理論上應該也是做的到只是因為教學比較少，所以就沒有特別嘗試了，而是改回用 Virtual Box 編譯一般的 Linux 3. [BTF: .tmp_vmlinux.btf: pahole (pahole) is not available](https://stackoverflow.com/questions/61657707/btf-tmp-vmlinux-btf-pahole-pahole-is-not-available) #### 測試檔程式碼 (User space code): ```c #include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <time.h> #include <sys/time.h> #define TOTAL_ITERATION_NUM 100000000 #define NUM_OF_PRIORITIES_TESTED 40 // system call int my_set_process_priority(int x){ return syscall(449, x); } int main(){ int index=0; int priority, i; struct timeval start[NUM_OF_PRIORITIES_TESTED], end[NUM_OF_PRIORITIES_TESTED]; gettimeofday(&start[index], NULL); for(i=1;i<=TOTAL_ITERATION_NUM;i++) rand(); gettimeofday(&end[index], NULL); for(index=1, priority=101;priority<=139;++priority,++index){ if(!my_set_process_priority(priority)) printf("Cannot set priority %d.\n", priority); gettimeofday(&start[index], NULL); for(i=1;i<=TOTAL_ITERATION_NUM;i++) rand(); gettimeofday(&end[index], NULL); } printf("The process spent %ld uses to execute when priority is not adjusted.\n", ((end[0].tv_sec * 1000000 + end[0].tv_usec) - (start[0].tv_sec * 1000000 + start[0].tv_usec))); for(i=1;i<=NUM_OF_PRIORITIES_TESTED-1;i++){ printf("The process spent %ld uses to execute when priority is %d.\n", ((end[i].tv_sec * 1000000 + end[i].tv_usec) - (start[i].tv_sec * 1000000 + start[i].tv_usec)), i+100); } } ``` 需要注意的是 `int my_set_process_priority(int x)` 當中的 `return syscall(449, x);` **449** 需替換為修改kernal時 `arch/x86/entry/syscalls/syscall_64.tbl` 所輸入的新 system call 編號 ## 測試結果: ``` The process spent 369126 uses to execute when priority is not adjusted. The process spent 381358 uses to execute when priority is 101. The process spent 381715 uses to execute when priority is 102. The process spent 374775 uses to execute when priority is 103. The process spent 408680 uses to execute when priority is 104. The process spent 377537 uses to execute when priority is 105. The process spent 465621 uses to execute when priority is 106. The process spent 377302 uses to execute when priority is 107. The process spent 541394 uses to execute when priority is 108. The process spent 378432 uses to execute when priority is 109. The process spent 379621 uses to execute when priority is 110. The process spent 376147 uses to execute when priority is 111. The process spent 383003 uses to execute when priority is 112. The process spent 377720 uses to execute when priority is 113. The process spent 377409 uses to execute when priority is 114. The process spent 377835 uses to execute when priority is 115. The process spent 380432 uses to execute when priority is 116. The process spent 378308 uses to execute when priority is 117. The process spent 379733 uses to execute when priority is 118. The process spent 375452 uses to execute when priority is 119. The process spent 373748 uses to execute when priority is 120. The process spent 383100 uses to execute when priority is 121. The process spent 377462 uses to execute when priority is 122. The process spent 374731 uses to execute when priority is 123. The process spent 377524 uses to execute when priority is 124. The process spent 381492 uses to execute when priority is 125. The process spent 373684 uses to execute when priority is 126. The process spent 380278 uses to execute when priority is 127. The process spent 373138 uses to execute when priority is 128. The process spent 375685 uses to execute when priority is 129. The process spent 376322 uses to execute when priority is 130. The process spent 382546 uses to execute when priority is 131. The process spent 374382 uses to execute when priority is 132. The process spent 371814 uses to execute when priority is 133. The process spent 370950 uses to execute when priority is 134. The process spent 371697 uses to execute when priority is 135. The process spent 380269 uses to execute when priority is 136. The process spent 378576 uses to execute when priority is 137. The process spent 380283 uses to execute when priority is 138. The process spent 382676 uses to execute when priority is 139. ``` 轉換成以下折線圖: ![Figure_1](https://hackmd.io/_uploads/HJsXzYI_T.png) ### 結論在測試檔的結果顯示中，我們觀察不到執行時間的趨勢，因此推測似乎在context switch之後直接修改 static_prio沒有辦法顯著影響 process執行的時間 ## 加分題: ### 第一種嘗試由於vruntime在runqueue中會一直增加，直到離開runqueue，並且通過觀察CFS的原始碼，發現事實上CFS選擇的是vruntime最小的process，因此我們嘗試在 enqueue_entity中進行修改。 enqueue_entity是用來將process加入CFS當中的function，因此如果在這時修改process的vruntime，我們認為理應可以讓CFS認為這個process之前被分到的時間比較少，進而將其排在紅黑樹的左側，我們將程式碼加在兩個 se-> vruntime += cfs_min_vruntime底下，這行code的目的是為了不讓某個process一直占用系統而設的，但我們為了觀察差別因此不需要考慮這點，將vruntime在更下面的部分進行修改，如圖: ![image](https://hackmd.io/_uploads/ryDaVy_Op.png) 此方法並未成功，但我們依然不清楚是否是思路有問題。 ![image](https://hackmd.io/_uploads/SywLIk__T.png) ### 第二種嘗試為了更好的觀察Priority和Nice value的影響，我們使用上述同樣的code分別執行三次，表示三個process間的時間首先我們創建3個process： ```bash= ./3oa -> p1.out ./3oa -> p2.out ./3oa -> p3.out ``` 並且一創建process後立刻CTRL + Z 暫停process，等到三個process建立完畢後，執行三次bg將三個process一起在背景執行。我們可以用top指令觀察process的nice value有沒有變化： ![image](https://hackmd.io/_uploads/rk2pfxv_T.png) 可以發現，雖然Nice value有所改變，但是Priority沒有改變，CPU分配的時間也沒有改變，三個process的nice value會在一段時間後一起增長，表示之間有發生context switch並且執行process的時間會是單一process的三倍。(因為平均的分給3個process執行) ![image](https://hackmd.io/_uploads/SklVvlwOT.png) 另一種情況：我們如果先讓2個process跑一會兒呢？ ![image](https://hackmd.io/_uploads/SkEHe-vdT.png) 可以看到，雖然Nice value改變了，但是Priority沒有改變，因為對於blade使用者來說，都是bash這個shell fork出去的process，他們的priority都為0，理論上雖然會使用相同時間的CPU。 (%CPU (CPU usage) - 由上次 top 畫面更新資料後Process的 CPU 使用率。為Process佔用的 CPU 時間除以實際時間 (CPU 時間 / 實際時間)，以百分比顯示。顯示小數點後一個位。可以按 I 鍵切換 Irix 模式 (一般計算方法) 和 Solaris 模式 (一般的 CPU 使用率再除系統的處理器數目) 改變此欄顯示的數值。) 因此對於CFS來說：引入了另一套選擇任務的機制，Vruntime：根據[這篇文章](https://zhuanlan.zhihu.com/p/363791563): ![image](https://hackmd.io/_uploads/B1WF_fwu6.png) 實際上是將task_struct中的sched_entity排程進cfs的runqueue中，並且會選擇Vruntime最小的process進行process switch。因此我們新增一個system_call，嘗試在process_switch，__schedule()之前修改process的vruntime ```Cpp= #include <linux/kernel.h> #include <linux/syscalls.h> #include <linux/sched.h> #include <linux/random.h> SYSCALL_DEFINE1(my_set_process_vruntime, int, x) { current-> se.vruntime = x; return 1; } ``` 並且在user space code中加上： ```cpp= for(index=1, priority=101;priority<=139;++priority,++index) { if(!my_set_process_priority(priority)) { printf("Cannot set priority %d.\n", priority); } ... if(priority == 130) { syscall(451,0); } ... gettimeofday(&start[index], NULL); for(i=1;i<=TOTAL_ITERATION_NUM;i++) rand(); gettimeofday(&end[index], NULL); } ``` 這樣一來，在priority跑到130之後，Process的Vruntime被調整為0，之後會因為vruntime是rq中極小的，會一直繼續執行Process。我們可以驗證一下： ```bash= gcc -o 3oaruntime 3oaruntime.c ``` 並且一樣照上面的流程開三個process： ```bash= ./3oa -> p_1.out ./3oa -> p_2.out ./3oaruntime -> p_3.out ``` 當nice值跑到9的時候... **這個時候連bash shell(top)都停住了，因為總是先執行3oaruntime:** ![image](https://hackmd.io/_uploads/B1-t0Gvu6.png) 等到再次跳轉的時候，3oaruntime已經執行完了，表示確實搶佔了CPU。 ![image](https://hackmd.io/_uploads/BkjtRGDup.png) 並且我們觀察三個文字檔： (這邊的not adjusted的time不準，因為受我手速影響被pause住了qq) ``` P_1.out The process spent 14550957 uses to execute when priority is not adjusted. The process spent 3347221 uses to execute when priority is 101. The process spent 3134868 uses to execute when priority is 102. The process spent 3380499 uses to execute when priority is 103. The process spent 3551686 uses to execute when priority is 104. The process spent 3246467 uses to execute when priority is 105. The process spent 3387379 uses to execute when priority is 106. The process spent 3525838 uses to execute when priority is 107. The process spent 3207218 uses to execute when priority is 108. The process spent 3236783 uses to execute when priority is 109. The process spent 3426712 uses to execute when priority is 110. The process spent 3165004 uses to execute when priority is 111. The process spent 3388566 uses to execute when priority is 112. The process spent 3408835 uses to execute when priority is 113. The process spent 3541419 uses to execute when priority is 114. The process spent 3415244 uses to execute when priority is 115. The process spent 3311029 uses to execute when priority is 116. The process spent 3286045 uses to execute when priority is 117. The process spent 3264753 uses to execute when priority is 118. The process spent 3199735 uses to execute when priority is 119. The process spent 3295064 uses to execute when priority is 120. The process spent 3305953 uses to execute when priority is 121. The process spent 3254239 uses to execute when priority is 122. The process spent 3192371 uses to execute when priority is 123. The process spent 3345036 uses to execute when priority is 124. The process spent 3309766 uses to execute when priority is 125. The process spent 3200402 uses to execute when priority is 126. The process spent 3392693 uses to execute when priority is 127. The process spent 3159826 uses to execute when priority is 128. **The process spent 14405473 uses to execute when priority is 129.** The process spent 2198226 uses to execute when priority is 130. The process spent 2127417 uses to execute when priority is 131. The process spent 2162753 uses to execute when priority is 132. The process spent 2084300 uses to execute when priority is 133. The process spent 2328249 uses to execute when priority is 134. The process spent 2230377 uses to execute when priority is 135. The process spent 2127896 uses to execute when priority is 136. The process spent 2064666 uses to execute when priority is 137. The process spent 2181846 uses to execute when priority is 138. The process spent 2079758 uses to execute when priority is 139. ``` ``` p_2.out The process spent 10833581 uses to execute when priority is not adjusted. The process spent 3356949 uses to execute when priority is 101. The process spent 3198078 uses to execute when priority is 102. The process spent 3321587 uses to execute when priority is 103. The process spent 3543378 uses to execute when priority is 104. The process spent 3231316 uses to execute when priority is 105. The process spent 3378873 uses to execute when priority is 106. The process spent 3572297 uses to execute when priority is 107. The process spent 3226904 uses to execute when priority is 108. The process spent 3235642 uses to execute when priority is 109. The process spent 3421869 uses to execute when priority is 110. The process spent 3205063 uses to execute when priority is 111. The process spent 3305026 uses to execute when priority is 112. The process spent 3457674 uses to execute when priority is 113. The process spent 3555927 uses to execute when priority is 114. The process spent 3399618 uses to execute when priority is 115. The process spent 3300332 uses to execute when priority is 116. The process spent 3284891 uses to execute when priority is 117. The process spent 3267839 uses to execute when priority is 118. The process spent 3274345 uses to execute when priority is 119. The process spent 3231072 uses to execute when priority is 120. The process spent 3323217 uses to execute when priority is 121. The process spent 3261401 uses to execute when priority is 122. The process spent 3167998 uses to execute when priority is 123. The process spent 3363354 uses to execute when priority is 124. The process spent 3302051 uses to execute when priority is 125. The process spent 3205022 uses to execute when priority is 126. The process spent 3389322 uses to execute when priority is 127. The process spent 3223545 uses to execute when priority is 128. The process spent 3175237 uses to execute when priority is 129. **The process spent 13578154 uses to execute when priority is 130.** The process spent 2152181 uses to execute when priority is 131. The process spent 2128659 uses to execute when priority is 132. The process spent 2126123 uses to execute when priority is 133. The process spent 2294126 uses to execute when priority is 134. The process spent 2232957 uses to execute when priority is 135. The process spent 2168351 uses to execute when priority is 136. The process spent 2067848 uses to execute when priority is 137. The process spent 2133295 uses to execute when priority is 138. The process spent 2244893 uses to execute when priority is 139. ``` ``` p_3.out The process spent 5021564 uses to execute when priority is not adjusted. The process spent 3353412 uses to execute when priority is 101. The process spent 3140800 uses to execute when priority is 102. The process spent 3366701 uses to execute when priority is 103. The process spent 3547275 uses to execute when priority is 104. The process spent 3250639 uses to execute when priority is 105. The process spent 3387868 uses to execute when priority is 106. The process spent 3541557 uses to execute when priority is 107. The process spent 3199871 uses to execute when priority is 108. The process spent 3239124 uses to execute when priority is 109. The process spent 3432801 uses to execute when priority is 110. The process spent 3164327 uses to execute when priority is 111. The process spent 3375484 uses to execute when priority is 112. The process spent 3422385 uses to execute when priority is 113. The process spent 3538050 uses to execute when priority is 114. The process spent 3388560 uses to execute when priority is 115. The process spent 3308487 uses to execute when priority is 116. The process spent 3292420 uses to execute when priority is 117. The process spent 3264576 uses to execute when priority is 118. The process spent 3212488 uses to execute when priority is 119. The process spent 3274654 uses to execute when priority is 120. The process spent 3313426 uses to execute when priority is 121. The process spent 3256756 uses to execute when priority is 122. The process spent 3185388 uses to execute when priority is 123. The process spent 3359377 uses to execute when priority is 124. The process spent 3308796 uses to execute when priority is 125. The process spent 3202259 uses to execute when priority is 126. The process spent 3390223 uses to execute when priority is 127. The process spent 3171561 uses to execute when priority is 128. The process spent 3236249 uses to execute when priority is 129. **The process spent 1113817 uses to execute when priority is 130.** The process spent 1029852 uses to execute when priority is 131. The process spent 1196717 uses to execute when priority is 132. The process spent 1164905 uses to execute when priority is 133. The process spent 1074855 uses to execute when priority is 134. The process spent 1176427 uses to execute when priority is 135. The process spent 1070512 uses to execute when priority is 136. The process spent 1037869 uses to execute when priority is 137. The process spent 1103037 uses to execute when priority is 138. The process spent 1128352 uses to execute when priority is 139. ``` ![image](https://hackmd.io/_uploads/SyzoImvu6.png) 加碼測試: ```cpp= if(priority == 110) { (my_set_process_vruntime(0)); } if(priority == 115) { my_set_process_vruntime(150000); } if(priority == 125) { my_set_process_vruntime(15000*10^15000000); } ``` Shell在(Nice = -12)的時候當機 ![image](https://hackmd.io/_uploads/r13FR7POT.png) Shell在(Nice = 15)之後恢復刷新 ![image](https://hackmd.io/_uploads/Hkho0mDOT.png) ``` test.out The process spent 1729165 uses to execute when priority is not adjusted. The process spent 1576649 uses to execute when priority is 101. The process spent 1235611 uses to execute when priority is 102. The process spent 1120502 uses to execute when priority is 103. The process spent 1174087 uses to execute when priority is 104. The process spent 1082380 uses to execute when priority is 105. The process spent 1218661 uses to execute when priority is 106. The process spent 1047405 uses to execute when priority is 107. The process spent 1077305 uses to execute when priority is 108. The process spent 1142162 uses to execute when priority is 109. The process spent 1130348 uses to execute when priority is 110. The process spent 1083687 uses to execute when priority is 111. The process spent 1127008 uses to execute when priority is 112. The process spent 1251547 uses to execute when priority is 113. The process spent 1072791 uses to execute when priority is 114. The process spent 1128120 uses to execute when priority is 115. The process spent 1200668 uses to execute when priority is 116. The process spent 1169604 uses to execute when priority is 117. The process spent 1169534 uses to execute when priority is 118. The process spent 1133609 uses to execute when priority is 119. The process spent 1166874 uses to execute when priority is 120. The process spent 1110160 uses to execute when priority is 121. The process spent 1123512 uses to execute when priority is 122. The process spent 1079234 uses to execute when priority is 123. The process spent 1142368 uses to execute when priority is 124. The process spent 1114855 uses to execute when priority is 125. **The process spent 1330346 uses to execute when priority is 126.** The process spent 1208250 uses to execute when priority is 127. The process spent 1111728 uses to execute when priority is 128. The process spent 1103382 uses to execute when priority is 129. The process spent 1081741 uses to execute when priority is 130. The process spent 1113158 uses to execute when priority is 131. The process spent 1167193 uses to execute when priority is 132. The process spent 1117955 uses to execute when priority is 133. The process spent 1218660 uses to execute when priority is 134. The process spent 1184397 uses to execute when priority is 135. The process spent 1121901 uses to execute when priority is 136. The process spent 1066173 uses to execute when priority is 137. The process spent 1071310 uses to execute when priority is 138. The process spent 1080588 uses to execute when priority is 139. ``` ```cpp= if(priority == 103) { my_set_process_vruntime(0); } if(priority >= 105 && priority <= 109) { my_set_process_vruntime(10*(priority-104)); } if(priority >= 110 && priority <= 119) { my_set_process_vruntime(100*(priority-109)); } if(priority >= 120 && priority <=129) { my_set_process_vruntime(1000*(priority-119)); } if(priority >= 130 && priority <=134) { my_set_process_vruntime(10000*(priority-129)); } if(priority >=135 && priority <=139) { my_set_process_vruntime(100000*(priority-134)); } ``` ![image](https://hackmd.io/_uploads/HyW9OBPOp.png) https://github.com/freelancer-leon/notes/blob/master/kernel/sched/sched_cfs.md#%E6%96%B0%E8%BF%9B%E7%A8%8B%E8%BF%9B%E5%85%A5%E9%98%9F%E5%88%97

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.