FALL2023 Linux Operating System Project 1

# FALL2023 Linux Operating System Project 1 ###### tags: `Linux` `project` 112522105 曾尚群 112522121 馬維欣 112522028 李軒豪 ## 題目 [Project 1](https://staff.csie.ncu.edu.tw/hsufh/COURSES/FALL2023/linux_project_1.html) ## References > [Thread-Local Storage](https://web.mit.edu/rhel-doc/3/rhel-gcc-en-3/thread-local.html) > [G. T. Wang, C 語言 pthread 多執行緒平行化程式設計入門教學與範例](https://blog.gtwang.org/programming/pthread-multithreading-programming-in-c-tutorial/) > [Jason/cntofu.com, 深入 Linux 多線程編程](https://cntofu.com/book/46/linux_system/shen_rulinux_duo_xian_cheng_bian_cheng.md) > [Project 1 from course website](http://staff.csie.ncu.edu.tw/hsufh/COURSES/FALL2023/linux_project_1.html) > [Adding A System Call To The Linux Kernel](https://dev.to/jasper/adding-a-system-call-to-the-linux-kernel-5-8-1-in-ubuntu-20-04-lts-2ga8) > [get_pid和get_task_mm](https://zhuanlan.zhihu.com/p/41788388) > [__task_pid_nr_ns和find_get_pid](https://zhuanlan.zhihu.com/p/41260133) > [Memory mapping - The Linux Kernel documentation](https://linux-kernel-labs.github.io/refs/pull/222/merge/labs/memory_mapping.html) > [Linux kernel 内存 - 页表映射（SHIFT，SIZE，MASK）和转换(32位，64位) - 苏小北1024 - 博客园](https://www.cnblogs.com/muahao/p/10297852.html) > [Linux Kernel - HackMD](https://hackmd.io/@eugenechou/H1LGA9AiB#Project-1) > ## 多執行緒程式實作此實作為一個簡單的多執行緒程式，透過執行此程式, system call 與 gdb 可以確認系統配置給一個多執行緒程式的 virtual memory layout ### Environment > Linux kernel version: 5.15.137 Distribution: Ubuntu 22.04.3 gcc: 11.4.0 gdb: 12.1 ### Kernel Space Code (New System Call)  #### my_get_physical_addresses.c > [Kconfig - arch/x86/Kconfig - Linux source code (v5.15.137) - Bootlin](https://elixir.bootlin.com/linux/v5.15.137/source/arch/x86/Kconfig#L384) ``` config PGTABLE_LEVELS int default 5 if X86_5LEVEL default 4 if X86_64 default 3 if X86_PAE default 2 ``` 在 X86_64 沒有開啟 PAE (physical address extension) 的情況下 page table 應為五層 (pgd, p4d, pud, pmd, pte) ``` hank@hank-virtual-machine:~/Downloads$ cat /boot/config-`uname -r` | grep 5LEVEL CONFIG_X86_5LEVEL=y ``` > [pgtable.h - arch/x86/include/asm/pgtable.h - Linux source code (v5.15.137) - Bootlin](https://elixir.bootlin.com/linux/v5.15.137/source/arch/x86/include/asm/pgtable.h) `pgd_offset()`, `p4d_offset()` 等 functions 定義在上述 header file，透過這些 functions & `current->mm->pgd` 我們就能確定 kernel 有無對某 virtual address 分配 page frame，沒有的話以下新增的 system call 會傳回 0，若有則將傳入的 virtual address 在 page tables 中對應的 physical address 回傳以下為原始程式碼 my_get_physical_addresses.c 的內容 [Link to my_get_physical_addresses.c](https://github.com/Hank8933/Linux-Operating-System-Projects/blob/main/Project%201/my_get_physical_addresses.c) ### 新增 system call 與編譯核心過程 > [about how to add a system call](https://hackmd.io/aist49C9R46-vaBIlP3LDA?view) > [Adding A System Call To The Linux Kernel](https://dev.to/jasper/adding-a-system-call-to-the-linux-kernel-5-8-1-in-ubuntu-20-04-lts-2ga8) ### User Space Code 以下為原始程式碼 (動態連結 dlmalloc 以比較其與原本 malloc 差異) [Link to test.c](https://github.com/Hank8933/Linux-Operating-System-Projects/blob/main/Project%201/test.c) [Link to dlmalloc.c](https://gee.cs.oswego.edu/pub/misc/malloc.c) [Link to malloc.h](https://gee.cs.oswego.edu/pub/misc/malloc.h) Need to add #define USE_DL_PREFIX to both dlmalloc.c & malloc.h #### Compile & Run Dynamic linking ``` gcc -fPIC -shared -o libdlmalloc.so dlmalloc.c gcc -o test test.c -L. -ldlmalloc # Set library path export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:. # or sudo cp libdlmalloc.so /usr/local/lib sudo ldconfig ./test ``` Static linking ``` gcc -c dlmalloc.c ar cr libdlmalloc.a dlmalloc.o gcc -o test test.c -static -L. -ldlmalloc ./test ```  ### Ouput of `./test` 在當前目錄下輸入 `./test` 會得到以下輸出 (執行緒間輸出的順序不固定) ``` Starting program: /home/hank/Downloads/test [Thread debugging using libthread_db enabled] Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1". [New Thread 0x7ffff7d73640 (LWP 17640)] I am thread with ID 17640 executing func1(). In thread 17640 the value of gloable varialbe a is 123, the offset of the logical address of a is 0x555555558010, the physical address of global variable a is 0x329bf2010 the offset of the logical address of heap variable malloc_ptr is 0x7ffff0000f80, the physical address of heap variable malloc_ptr is 0x324f97f80 the offset of the logical address of heap variable dlmalloc_ptr is 0x55555557a010, the physical address of heap variable dlmalloc_ptr is 0x310789010 the value of local varialbe b is 17650, the offset of the logical address of b is 0x7ffff7d72e04, the physical address of local variable b is 0x2a39fde04 the offset of the logical address of thread local varialbe tx is 0x7ffff7d7362c, the physical address of thread local variable tx is 0x31f7d662c the offset of the logical address of function hello is 0x555555555261, the physical address of function hello is 0x2a3770261 the offset of the logical address of function func1 is 0x555555555583, the physical address of function func1 is 0x2a3770583 the offset of the logical address of function func2 is 0x55555555560a, the physical address of function func2 is 0x2a377060a the offset of the logical address of function main is 0x555555555691, the physical address of function main is 0x2a3770691 the offset of the logical address of library function printf is 0x7ffff7dd76f0, the physical address of library function printf is 0x10e3cc6f0 ==================================================================================================================== [New Thread 0x7ffff7572640 (LWP 17641)] I am main thread with ID 17637. In thread 17637 the value of gloable varialbe a is 123, the offset of the logical address of a is 0x555555558010, the physical address of global variable a is 0x329bf2010 the offset of the logical address of heap variable malloc_ptr is 0x555555559500, the physical address of heap variable malloc_ptr is 0x312a31500 the offset of the logical address of heap variable dlmalloc_ptr is 0x55555557a030, the physical address of heap variable dlmalloc_ptr is 0x310789030 the value of local varialbe b is 17647, the offset of the logical address of b is 0x7fffffffde94, the physical address of local variable b is 0x2c1b14e94 the offset of the logical address of thread local varialbe tx is 0x7ffff7d7472c, the physical address of thread local variable tx is 0x28f74c72c the offset of the logical address of function hello is 0x555555555261, the physical address of function hello is 0x2a3770261 the offset of the logical address of function func1 is 0x555555555583, the physical address of function func1 is 0x2a3770583 the offset of the logical address of function func2 is 0x55555555560a, I am thread with ID 17641 executing func2(). In thread 17641 the value of gloable varialbe a is 123, the offset of the logical address of a is 0x555555558010, the physical address of global variable a is 0x329bf2010 the offset of the logical address of heap variable malloc_ptr is 0x7fffe8000b70, the physical address of heap variable malloc_ptr is 0x2d4c93b70 the offset of the logical address of heap variable dlmalloc_ptr is 0x55555557a050, the physical address of function func2 is 0x2a377060a the offset of the logical address of function main is 0x555555555691, the physical address of function main is 0x2a3770691 the offset of the logical address of library function printf is 0x7ffff7dd76f0, the physical address of library function printf is 0x10e3cc6f0 ==================================================================================================================== the physical address of heap variable dlmalloc_ptr is 0x310789050 the value of local varialbe b is 17651, the offset of the logical address of b is 0x7ffff7571e04, the physical address of local variable b is 0x31cb18e04 the offset of the logical address of thread local varialbe tx is 0x7ffff757262c, the physical address of thread local variable tx is 0x313e0862c the offset of the logical address of function hello is 0x555555555261, the physical address of function hello is 0x2a3770261 the offset of the logical address of function func1 is 0x555555555583, the physical address of function func1 is 0x2a3770583 the offset of the logical address of function func2 is 0x55555555560a, the physical address of function func2 is 0x2a377060a the offset of the logical address of function main is 0x555555555691, the physical address of function main is 0x2a3770691 the offset of the logical address of library function printf is 0x7ffff7dd76f0, the physical address of library function printf is 0x10e3cc6f0 ==================================================================================================================== ``` - 可以發現全域變數 `static __thread sdata tx` 在**不同執行緒裡都有一份 (virtual address, physical address 不同)** 符合 [Thread-Local Storage](https://web.mit.edu/rhel-doc/3/rhel-gcc-en-3/thread-local.html) 裡面對 thread-local variable 的說明 - 全域變數位址都是完全相同的，在**不同執行緒裡都是存取到同一變數 (virtual address, physical address 相同)**，因此可以確認 data segment, BSS segment 確實是共享的 - physical address 若為 0 表示 virtual address 對應的某一層 page directory 或 table entry 的值為 0，kernel 並沒有配置 page frame 給該 virtual address - 有關 stack & heap 的狀況請見下方  --- ### Virtual Memory Layout  根據 [Jason/cntofu.com, 深入 Linux 多線程編程](https://cntofu.com/book/46/linux_system/shen_rulinux_duo_xian_cheng_bian_cheng.md)，同一個 process 內的執行緒共享 global variables, heap 但每個執行緒都有自己的 stack，由此推論 `int b` 應位於執行緒自身的 stack 中 (在函式中宣告，為 local variable) 結合上方程式輸出與下方 gdb `info proc mapping` 的輸出，能夠發現 main thread 呼叫的 `hello()` 中的 `int b` 位於 [stack] 區段，而另外兩個執行緒所呼叫的 `hello()` 中的 `int b` 則位於位址較低的兩個不同的可讀可寫區段，應可判斷此區段即為執行緒自身的 stack  #### Memory Space Mapping Generated by `info proc mapping` in GDB ``` gef➤ info proc mapping process 17637 Mapped address spaces: Start Addr End Addr Size Offset Perms objfile 0x555555554000 0x555555555000 0x1000 0x0 r--p /home/hank/Downloads/test 0x555555555000 0x555555556000 0x1000 0x1000 r-xp /home/hank/Downloads/test 0x555555556000 0x555555557000 0x1000 0x2000 r--p /home/hank/Downloads/test 0x555555557000 0x555555558000 0x1000 0x2000 r--p /home/hank/Downloads/test 0x555555558000 0x555555559000 0x1000 0x3000 rw-p /home/hank/Downloads/test 0x555555559000 0x55555557b000 0x22000 0x0 rw-p [heap] 0x7fffe8000000 0x7fffe8021000 0x21000 0x0 rw-p 0x7fffe8021000 0x7fffec000000 0x3fdf000 0x0 ---p 0x7ffff0000000 0x7ffff0021000 0x21000 0x0 rw-p 0x7ffff0021000 0x7ffff4000000 0x3fdf000 0x0 ---p 0x7ffff6d72000 0x7ffff6d73000 0x1000 0x0 ---p 0x7ffff6d73000 0x7ffff7573000 0x800000 0x0 rw-p 0x7ffff7573000 0x7ffff7574000 0x1000 0x0 ---p 0x7ffff7574000 0x7ffff7d77000 0x803000 0x0 rw-p 0x7ffff7d77000 0x7ffff7d9f000 0x28000 0x0 r--p /usr/lib/x86_64-linux-gnu/libc.so.6 0x7ffff7d9f000 0x7ffff7f34000 0x195000 0x28000 r-xp /usr/lib/x86_64-linux-gnu/libc.so.6 0x7ffff7f34000 0x7ffff7f8c000 0x58000 0x1bd000 r--p /usr/lib/x86_64-linux-gnu/libc.so.6 0x7ffff7f8c000 0x7ffff7f90000 0x4000 0x214000 r--p /usr/lib/x86_64-linux-gnu/libc.so.6 0x7ffff7f90000 0x7ffff7f92000 0x2000 0x218000 rw-p /usr/lib/x86_64-linux-gnu/libc.so.6 0x7ffff7f92000 0x7ffff7f9f000 0xd000 0x0 rw-p 0x7ffff7fad000 0x7ffff7fae000 0x1000 0x0 r--p /home/hank/Downloads/libdlmalloc.so 0x7ffff7fae000 0x7ffff7fb8000 0xa000 0x1000 r-xp /home/hank/Downloads/libdlmalloc.so 0x7ffff7fb8000 0x7ffff7fb9000 0x1000 0xb000 r--p /home/hank/Downloads/libdlmalloc.so 0x7ffff7fb9000 0x7ffff7fba000 0x1000 0xb000 r--p /home/hank/Downloads/libdlmalloc.so 0x7ffff7fba000 0x7ffff7fbb000 0x1000 0xc000 rw-p /home/hank/Downloads/libdlmalloc.so 0x7ffff7fbb000 0x7ffff7fbd000 0x2000 0x0 rw-p 0x7ffff7fbd000 0x7ffff7fc1000 0x4000 0x0 r--p [vvar] 0x7ffff7fc1000 0x7ffff7fc3000 0x2000 0x0 r-xp [vdso] 0x7ffff7fc3000 0x7ffff7fc5000 0x2000 0x0 r--p /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2 0x7ffff7fc5000 0x7ffff7fef000 0x2a000 0x2000 r-xp /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2 0x7ffff7fef000 0x7ffff7ffa000 0xb000 0x2c000 r--p /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2 0x7ffff7ffb000 0x7ffff7ffd000 0x2000 0x37000 r--p /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2 0x7ffff7ffd000 0x7ffff7fff000 0x2000 0x39000 rw-p /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2 0x7ffffffde000 0x7ffffffff000 0x21000 0x0 rw-p [stack] 0xffffffffff600000 0xffffffffff601000 0x1000 0x0 --xp [vsyscall] ``` 進一步確認可發現 1. **三個執行緒的 local variable `int b` 位於不同的區段**，這些區域應為執行緒各自的 stack 2. 原先透過 `malloc()` (ptmalloc2) 動態配置的空間位於**三個不同的可讀可寫區段** 根據 [Jason/cntofu.com, 深入 Linux 多線程編程](https://cntofu.com/book/46/linux_system/shen_rulinux_duo_xian_cheng_bian_cheng.md)，該空間應屬於 shared library, shared memory，且執行緒間共享 heap - 問題一: 若同一 process 內的執行緒共享 [heap] 的話，則與上述 2. 的狀況不符 > [Heap Exploitation Part 1: Understanding the Glibc Heap Implementation | Azeria Labs](https://azeria-labs.com/heap-exploitation-part-1-understanding-the-glibc-heap-implementation/) 上述連結中的 **arena**, **subheap** 應該與此有關 > 在 multithreaded application 裡面為避免 race condition 需要用 mutex lock 來確保任何時間點僅有單一的 thread 可以和 heap 互動，但此策略在 multithreaded application 裡因 heap operations 為 performance sensitive 的操作會導致效能低下的狀況，因此有了 "arenas" 的概念 > 一開始的 (“main”) arena 僅包含單一的 heap，對於 single-threaded application 來說這是 heap manager 唯一用到的 arena。當新的 threads 產生之後 heap manager 會配置次要的 (secondary) arenas 給這些新的 threads，這麼做能夠降低執行緒為了執行像是 malloc, free 這類 heap operations 而等待其他執行緒的機率。若我們採用 [dlmalloc()](https://hackmd.io/@sShaAanGg/SkN8LwXUi#Compile-amp-Run) 的話，三個執行緒配置在 heap 的空間開頭分別為 `0x55555557a010`, `0x55555557a030`, `0x55555557a050`，可以得知此為三塊連續配置的 `chunk` (64 位元中最小 chunk size 為 32 bytes)。如此三個執行緒就會共享一個 heap ### Summary Figure ![VMA.drawio (2)](https://hackmd.io/_uploads/BJ-eowJBa.png)