## Linux Project 1
[toc]
**組長：**
**111504512 賴詠文**
組員：
111504507 黃子銘
109401553 楊雲杰
111504008 郭奕宏
:::success
### 題目
**you need to write a new system call `void * my_get_physical_addresses(void *)` so that a process can use it to get the physical address of a virtual address of a process.**
> 此系統呼叫的回傳值是 0 或位址值。 0表示目前沒有實體位址分配給邏輯位址。非零值表示作為其參數提交給系統呼叫的邏輯位址的物理位址（實際上，該位址只是邏輯位址的偏移量）。
https://staff.csie.ncu.edu.tw/hsufh/COURSES/FALL2024/linux_project_1.html
### Demo 時間
- 11/12 11:15~11:30
### 第一次討論
- 10/19 20:30~
### 第二次討論
- 11/1 20:00~
### 第三次討論
- 11/9 20:00~
:::
### Kernel 版本
`wget -P ~/ https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.15.137.tar.xz`
:::success
## 題目
you need to write a new system call `void * my_get_physical_addresses(void *)` so that a process can use it to get the physical address of a virtual address of a process.
此系統呼叫的回傳值是 0 或位址值。 0表示目前沒有實體位址分配給邏輯位址。非零值表示作為其參數提交給系統呼叫的邏輯位址的物理位址（實際上，該位址只是邏輯位址的偏移量）。
:::
## 前置工作
:::spoiler 下載kernel
```shell=
sudo apt update
sudo apt install build-essential libncurses-dev libssl-dev libelf-dev bison flex -y
```
:::
## systemcall 添加及設置
進入解壓縮完的資料夾並在內部建立一個資料夾
```shell=
#進入 linux-5.15.137
cd usr/src/linux-5.15.137/
# 建立一個資料夾 mycall
mkdir mycall
# 在新建立好的資料夾中建立一個system call
vim mycall/my_get_physical_addresses.c
# 建立Makefile
vim mycall/Makefile
# 將my_get_physical_addresses.o編入kernel
obj-y := my_get_physical_addresses.o
# 編輯原系統中的Makefile
core-y += kernel/ certs/ mm/ fs/ ipc/ security/ crypto/ mycall/
# 將系統呼叫對應的函數加入到系統呼叫的標頭檔中
# 開啟檔案`include/linux/syscalls.h`
vim include/linux/syscalls.h
# 並在 #endif前加上
asmlinkage long sys_my_get_physical_addresses(unsigned long __user *usr_ptr);
# 將syscall加入到kernel的syscall table 並開啟檔案
vim arch/x86/entry/syscalls/syscall_64.tbl
# 會發現一系列 x32 系統呼叫，在x32 system call上方加入編號449的system call
449 common my_get_physical_addresses sys_my_get_physical_addresses
```
## 編譯和替換kernel
清理kernel之前的所有配置
```shell=
sudo make mrproper
```
編譯設定
進入 kernel 目錄中，並將目前 Kernel Config 文件複製到當前目錄，最後生成此 kernel 的配置文件
為了避免建置大量不必要的 driver 和 kernel module，使用 `localmodconfig` 來節省時間。
```shell=
cd linux-5.15.137/
cp -v /boot/config-$(uname -r) .config
make localmodconfig
```
因為我們直接從 /boot/config-$(uname -r) 複製設定檔，所以設定檔裡面的設定的是 Debian 官方當初編譯 kernel 時憑證的路徑，若是直接編譯會報錯，因此這邊取消使用憑證，並將值設為空字串
```shell=
scripts/config --disable SYSTEM_TRUSTED_KEYS
scripts/config --disable SYSTEM_REVOCATION_KEYS
scripts/config --set-str CONFIG_SYSTEM_TRUSTED_KEYS ""
scripts/config --set-str CONFIG_SYSTEM_REVOCATION_KEYS ""
```
開始編譯
```shell=
make -j12
```
### Error 處理
No rule to make target 'debian/canonical-certs.pem’
```
sudo vim .config
/ + enter + n(往下)搜尋 `debian/canonical-certs.pem `並直接清除此引號內的值
/ + enter + n(往下)搜尋 `debian/canonical-revoked-certs.pem` 並直接清除此引號內的值
```
BTF: .tmp_vmlinux.btf: pahole (pahole) is not available
```
sudo vim .config
/ + enter + n(往下)搜尋 CONFIG_DEBUG_INFO_BTF 將其值改為 n
```
### 編譯完畢進行安裝
準備kernel的安裝程式
```shell=
sudo make modules_install -j12
```
安裝kernel
```shell=
sudo make install -j12
```
重新啟動
```
sudo update-grub
sudo reboot
```
快速地連續按F4進入開機選單，點選Advanced options for Ubuntu
檢查版本 `uname -rs`
若要看kernel環境訊息或查看printk的結果可以下`sudo dmesg`指令查看
## 實作部分 (virtual address 轉為 physical address )
### 背景小知識
`#ifndef` `#define` `#endif`
#ifndef 的全稱是 "if not defined"，用來檢查某個符號或巨集是否尚未被定義。
如果符號未定義，則編譯器會處理該條件之下的代碼。
優點：避免程式重複編譯!!!
```
#ifndef SOME_MACRO
// 這段代碼會在 SOME_MACRO 尚未定義時被編譯
#define
// 已編譯過會執行這段代碼
#endif
```
在pgtable.h中 offset function
trace code網址：https://elixir.bootlin.com/linux/v5.15.137/source
```cpp=
// include/linux/pgtable.h line 91
#ifndef pte_offset_kernel
static inline pte_t *pte_offset_kernel(pmd_t *pmd, unsigned long address)
{
return (pte_t *)pmd_page_vaddr(*pmd) + pte_index(address);
}
#define pte_offset_kernel pte_offset_kernel
#endif
// ...
// include/linux/pgtable.h line 119
/* Find an entry in the second-level page table.. */
#ifndef pmd_offset
static inline pmd_t *pmd_offset(pud_t *pud, unsigned long address)
{
return pud_pgtable(*pud) + pmd_index(address);
}
#define pmd_offset pmd_offset
#endif
#ifndef pud_offset
// pud_t *pud：頁上級目錄（PUD，Page Upper Directory）的指針。
static inline pud_t *pud_offset(p4d_t *p4d, unsigned long address)
{
// p4d_pgtable(*p4d)：這個會返回 P4D 指向的頁表的基礎地址。
return p4d_pgtable(*p4d) + pud_index(address);
}
#define pud_offset pud_offset
#endif
static inline pgd_t *pgd_offset_pgd(pgd_t *pgd, unsigned long address)
{
return (pgd + pgd_index(address));
};
```
### 整體架構
線性地址轉physical address
:::spoiler kernel內多級頁表 
- GLOBAL DIR (PML4 Index): 高 9 bits，對應 PML4 索引。
- Upper DIR (PDPT Index): 接下來的 9 bits，對應上級頁目錄索引。
- Middle DIR (PD Index): 再往下的 9 bits，對應中間頁目錄索引。
- Table (PT Index): 9 bits，對應頁表的索引。
- OFFSET: 最後 12 bits，是頁框中的偏移量，表示物理頁框內的具體位置。
4 種 page table 結構
- CR3: 開始時，CR3 寄存器存儲的是 PML4 頁表的物理地址（圖中為 CR3 physical address）。PML4 是最高層的頁表。
- PML4 (Page Map Level 4): 使用虛擬地址的前 9 位作為索引（圖中的 pgd_index）來查找對應的 PML4 頁表條目（*pgd_offset）。
- PDPT (Page Directory Pointer Table): 下一層是上級頁目錄（PDPT），使用接下來的 9 位作為索引（pud_index），查找對應的頁表條目（*pud_offset）。
- PD (Page Directory): 中級頁目錄（PD）層使用接下來的 9 位作為索引（pmd_index），查找對應的條目（*pmd_offset）。
- T (Page Table): 最後的 9 位作為頁表索引（pte_index），找到具體的頁表條目（*pte_offset_kernel）。
- Offset: 最後的 12 位是頁框內的偏移量，用於定位頁框內的具體數據（Start Byte）。
:::
- 虛擬位址的最低12位元(4KB的頁大小)和實體位址的最低12位元相同。虛擬位址的4個頁表段page_index可以看做在頁表中的索引。
每一個 Process 都會有自己的 Page Table，存在它自己的 kernel space，Page table 的 Base address 會被存在 CR3 裡面，這是一個 register，又被稱為 PDBR(page directory base register)，存的是實體位址
> 分頁目錄的基底位址是存放在 CR3（或稱 PDBR，page directory base register）
### Page directory and page table
:::spoiler Page directory and page table architecture
- P: present p=1 => in memory
- R/W: =1 => can write
- U/S: user/supervisor 當 U/S = 1 時，表示分頁是一個 user level 的分頁
- A（accessed）旗標：在 A = 0 時，若分頁被存取
- D（dirty）旗標：在 D = 0 時，若對分頁進行寫入動作，則處理器會把它設為 1
- PS（page size）旗標：這個旗標只在分頁目錄 entry 中有作用。當 PS = 0 時，表示這是一個 4KB 的分頁
:::
to physical address 概要
```cppp=
// 當前進程的內存描述符（current->mm）中，計算虛擬地址 vaddr 在頁全局目錄（PGD）中的條目位置。這是查找過程中的第一層。
pgd = pgd_offset(current->mm, vaddr);
//通過 pmd 和 vaddr 計算頁表條目（PTE）的指針
pte = pte_offset_kernel(pmd, vaddr);
//從頁表條目（pte）中提取出物理頁框地址
//PAGE_MASK 是用來過濾掉頁表條目中的非地址部分（例如標誌位）的掩碼
//pte_val(*pte) & PAGE_MASK，只保留頁表條目中的物理頁框地址部分，並將其存儲在 page_addr 中。
page_addr = pte_val(*pte) & PAGE_MASK;
//vaddr 是虛擬地址，它包括了頁表查找所需的高位部分和頁框內的偏移量。
//~PAGE_MASK 是 PAGE_MASK 的反碼，將物理頁框地址的高位清除，保留低位的偏移量部分。
//vaddr & ~PAGE_MASK 是提取虛擬地址中的偏移量部分，這部分表示該地址在物理頁框中的具體位置。
page_offset = vaddr & ~PAGE_MASK;
//將物理頁框地址與偏移量組合，生成最終的物理地址。
paddr = page_addr | page_offset;
```
:::info
### **轉址備註**
`0x5633733901b1`，其前9個bit為 010101100
轉為10進位為172，也就是指”**下一層table的起始位置**”存於此table的第172欄
由於每一個欄位都是由8 byte組成，所以實際的offset的address為 172*8 =1376 轉為16進制為 `0x560` 相當於 010101100 左移3個bit，即 0101 0110 0000 轉為16進制也是 `0x560`
將a.的值(**pgd** )及b.的值(**pgd_index(address)**)合併:
`0xffff9ce09c8e8000` + `0x560` = `0xffff9ce09c8e8560`
`0xffff9ce09c8e8560` 此位置所儲存的值即為計算下一層table起始位置所需的值
在 `*pud_offset` 中的return value為 (p4d_pgtable(*p4d) + pud_index(address))
- p4d_pgtable(*p4d) 為PUD的起始位置，而 *p4d指的是`0xffff9ce09c8e8560`位置中的值
- p4d_pgtable()則是計算起始位置的方法
:::spoiler current-> mm解釋
在這段程式碼中，`current->mm` 是 Linux 核心中的一個結構體指標，指向目前執行的進程（process）的 **記憶體描述符 (memory descriptor)**。以下是詳細解釋：
### `current->mm` 的解釋
1. **`current`**：
- `current` 是一個巨集，用來取得當前執行的進程的 `task_struct` 結構指標。
- `task_struct` 是 Linux 核心用來描述每個進程的資料結構，包含進程的各種信息，如進程 ID、狀態、優先級、資源限制等。
2. **`current->mm`**：
- 在 `task_struct` 結構中，有一個成員變數 `mm`，它是一個指向 **`mm_struct`** 結構的指標。
- `mm_struct` 是記憶體描述符，用於描述進程的虛擬記憶體空間，包含了頁表、分段資訊、堆棧、程式段等相關的記憶體管理資訊。
- `current->mm` 可以理解為當前進程的虛擬記憶體空間的描述符。
3. **`mm_struct` 的用途**：
- `mm_struct` 包含了進程記憶體相關的所有重要資訊，例如：
- **頁全域目錄 (PGD)**：存放頁表層次結構的入口點。
- 在這段程式碼中，`current->mm` 被用來找到進程的頁全域目錄（PGD），從而開始虛擬地址到物理地址的轉換過程。
4. **`pgd_offset` 函數**：
- `pgd_offset` 是用來計算虛擬地址 `vaddr` 在當前進程的頁全域目錄中的偏移量，並返回該地址的 `pgd_t` 型別的指標。
- 這是虛擬地址轉換成物理地址的第一步，用來獲取頁全域目錄 (PGD) 的條目。
### 總結
在這段程式碼中，`current->mm` 是指向目前執行的進程的記憶體描述符的指標，包含該進程的所有虛擬記憶體資訊。利用 `current->mm` 可以開始從虛擬地址到物理地址的頁表查找過程，最終獲取對應的物理地址。
:::
### 完整程式碼
```c=
// SYSCALL_DEFINE1：這個表示定義一個接收一個參數的系統調用。數字 1 表示該系統調用接受一個參數。
// 0x%lx：表示以 16 進制格式打印一個長整數（long 型別）
#include<linux/syscalls.h>
SYSCALL_DEFINE1(my_get_physical_addresses, void *, addr_p)
{
unsigned long vaddr = (unsigned long)addr_p;
pgd_t *pgd;
p4d_t *p4d;
pud_t *pud;
pmd_t *pmd;
pte_t *pte;
unsigned long paddr=0;
unsigned long page_addr=0;
unsigned long page_offset=0;
pgd= pgd_offset(current->mm,vaddr);
printk("pgd_val = 0x%lx\n",pgd_val(*pgd));
printk("pgd_index = %lu\n",pgd_index(vaddr));
if(pgd_none(*pgd)){
printk("not mapped in pgd\n");
}
p4d=p4d_offset(pgd,vaddr);
printk("p4d_val = 0x%lx\n",p4d_val(*p4d));
printk("p4d_index = %lu\n", p4d_index(vaddr));
if(p4d_none(*p4d)){
printk("no mapped in p4d\n");
return 0;
}
pud=pud_offset(p4d,vaddr);
printk("pud_val = 0x%lx\n", pud_val(*pud));
printk("pud_index = %lu\n"), pud_index(vaddr));
if(pud_none(*pud)){
printk("no mapped in pud\n");
return 0;
}
pmd=pmd_offset(pud,vaddr);
printk("pmd_val = 0x%lx\n",pmd_val(*pmd));
printk("pmd_index = %lu\n",pmd_index(vaddr));
if(pmd_none(*pmd)){
printk("no mapped in pmd\n");
return 0;
}
pte = pte_offset_kernel(pmd,vaddr);
printk("pte_val = 0x%lx\n",pte_val(*pte));
printk("pte_index = %lu\n", pte_index(vaddr));
if(pte_none(*pte)){
printk("no mapped in pte\n");
return 0;
}
page_addr=pte_val(*pte) & PTE_PFN_MASK & PAGE_MASK;
page_offset = vaddr & ~PAGE_MASK;
paddr = page_addr | page_offset;
printk("page_addr = %lx, page_offset = %lx\n", page_addr, page_offset);
printk("vaddr = %lx, paddr = %lx\n", vaddr, paddr);
return paddr;
}
```
:::info
### 關於physical address 顯示
可以觀察到除了`pud_val`和`pmd_val`是32bit，而`pgd_val`, `p4d_val`, `pte_val`都是64bit，而最後影響到主要是`pte_val`，因此去看`pte_val`的code
```c=
// /arch/x86/include/asm/pgtable.h,
#define pte_val(x) native_pte_val(x)
```
```c=
// / arch / x86 / include / asm / pgtable_types.h
static inline pteval_t native_pte_val(pte_t pte)
{
return pte.pte;
}
static inline pteval_t pte_flags(pte_t pte)
{
return native_pte_val(pte) & PTE_FLAGS_MASK;
}
```
從上面可以發現`native_pte_val`也把`pte_flag`也取出來了
```c
#define PTE_FLAGS_MASK (~PTE_PFN_MASK)
```
而`PTE_FLAGS_MASK`定義是`(~PTE_PFN_MASK)`，因此我們將pte_val的flag濾掉就好了`page_addr=pte_val(*pte) & PTE_PFN_MASK & PAGE_MASK;`
而`pgd_val`, `p4d_val`也都是將FLAG也取出來
:::
## Question1 (see the effect of copy-on-write.)
:::success
### copy on write
`fork`時，系統會讓子進程和父進程共享相同的物理記憶體頁，而將這些頁標記為「唯讀」。當父或子進程嘗試寫入這些共享頁時，系統才會將該頁的內容複製一份（分配一個新的物理頁框），並允許進行寫入操作，這就是所謂的「寫入時複製」（Copy-on-Write）。
### 測試程式碼解釋
After Fork，由於 `global_a`的頁還沒有被寫入，父子進程此時應該共享相同的物理地址。
子進程寫入 `global_a`（設定 `global_a` = 789），這將觸發 Copy-on-Write 機制。
- 寫入時，作業系統會分配一個新的物理頁框給子進程，然後將 global_a 的新值寫入該頁框中。
- 接著，子進程再次獲取 `global_a` 的物理地址，這次它應該和父進程的 `global_a` 物理地址不同，從而顯示出 Copy-on-Write 的效果。
:::
### 測試程式碼
:::spoiler 測試程式碼
```c=
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
void * my_get_physical_addresses(void *vaddr)
{
return (void*) syscall(449,vaddr);
}
int global_a=123; //global variable
void hello(void)
{
printf("======================================================================================================\n");
}
int main()
{
int loc_a;
void *parent_use, *child_use;
int status;
printf("===========================Before Fork==================================\n");
parent_use=my_get_physical_addresses(&global_a);
printf("pid=%d: global variable global_a:\n", getpid());
printf("Offset of logical address:[%p] Physical address:[%p]\n", &global_a,parent_use);
printf("========================================================================\n");
if(fork())
{ /*parent code*/
printf("vvvvvvvvvvvvvvvvvvvvvvvvvv After Fork by parent vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n");
parent_use=my_get_physical_addresses(&global_a);
printf("pid=%d: global variable global_a:\n", getpid());
printf("******* Offset of logical address:[%p] Physical address:[%p]\n", &global_a,parent_use);
printf("vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n");
wait(&status);
}
else
{ /*child code*/
printf("llllllllllllllllllllllllll After Fork by child llllllllllllllllllllllllllllllll\n");
child_use=my_get_physical_addresses(&global_a);
printf("******* pid=%d: global variable global_a:\n", getpid());
printf("******* Offset of logical address:[%p] Physical address:[%p]\n", &global_a, child_use);
printf("llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll\n");
printf("____________________________________________________________________________\n");
/*----------------------- trigger CoW (Copy on Write) -----------------------------------*/
global_a=789;
printf("iiiiiiiiiiiiiiiiiiiiiiiiii Test copy on write in child iiiiiiiiiiiiiiiiiiiiiiii\n");
child_use=my_get_physical_addresses(&global_a);
printf("******* pid=%d: global variable global_a:\n", getpid());
printf("******* Offset of logical address:[%p] Physical address:[%p]\n", &global_a, child_use);
printf("iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii\n");
printf("____________________________________________________________________________\n");
sleep(1000);
}
}
```
:::
### 結果
:::spoiler 結果
:::
## Question2 (whether a loader loads all data of a process before executing it)
:::success
當進程開始執行時，核心通常不會分配物理記憶體來儲存進程的所有程式碼和資料。
對於 `a[1999999]`，結果顯示物理地址為 `(nil)`示此頁面還沒有被分配物理內存。
這證明內核在進程啟動時並未立即為數組 `a` 的所有元素分配物理內存，僅在訪問` a[0] `時才分配了對應的頁面，未訪問的頁面依然未分配。
Demand paging
只有在頁面被實際訪問時，內核才會為其分配物理內存，並非所有資料在程式啟動時都已載入並分配物理記憶體，只有訪問的頁面才會被分配到物理地址
:::
### 測試程式碼
:::spoiler code
```c=
#include<stdio.h>
// 使用syscall
#include<unistd.h>
void * my_get_physical_addresses(void *vaddr)
{
return (void*) syscall(449,vaddr);
}
int a[2000000];
int main()
{
int loc_a;
void *phy_add;
phy_add=my_get_physical_addresses(&a[0]);
printf("global element a[0]:\n" );
printf("Offset of logical address:[%p] Physical address:[%p]\n", &a[0], phy_add);
printf("========================================================================\n");
phy_add=my_get_physical_addresses(&a[1999999]);
printf("global element a[1999999]:\n" );
printf("Offset of logical address:[%p] Physical address:[%p]\n", &a[1999999], phy_add);
printf("========================================================================\n");
}
```
:::
### 結果
:::spoiler result
:::
## 參考資料
> [add to system call](https://hackmd.io/aist49C9R46-vaBIlP3LDA?view)
> [學長的資料](https://satin-eyebrow-f76.notion.site/Kernel-syscall-3ec38210bb1f4d289850c549def29f9f#6f9c68a389f14319839cf04692b3e064)
> [关于Linux内存寻址与页表处理的一些细节](https://www.cnblogs.com/QiQi-Robotics/p/15630380.html)
> [進階版本](https://hackmd.io/@eugenechou/H1LGA9AiB#Project-1)
> [gcc](https://ithelp.ithome.com.tw/articles/10257387)
## 補充資料
### Page Table 相關數字
```c=
/*
* PGDIR_SHIFT determines what a top-level page table entry can map
*/
#define PGDIR_SHIFT 39
#define PTRS_PER_PGD 512
#define MAX_PTRS_PER_P4D 1
#endif /* CONFIG_X86_5LEVEL */
/*
* 3rd level page
*/
#define PUD_SHIFT 30
#define PTRS_PER_PUD 512
/*
* PMD_SHIFT determines the size of the area a middle-level
* page table can map
*/
#define PMD_SHIFT 21
#define PTRS_PER_PMD 512
/*
* entries per page directory level
*/
#define PTRS_PER_PTE 512
#define PMD_SIZE (_AC(1, UL) << PMD_SHIFT)
#define PMD_MASK (~(PMD_SIZE - 1))
#define PUD_SIZE (_AC(1, UL) << PUD_SHIFT)
#define PUD_MASK (~(PUD_SIZE - 1))
#define PGDIR_SIZE (_AC(1, UL) << PGDIR_SHIFT)
#define PGDIR_MASK (~(PGDIR_SIZE - 1))
```
Sign in with Wallet
Connect another wallet