---
# System prepended metadata

title: FALL2023 Linux Operating System Project 1
tags: [project, Linux]

---

# 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)

<!-- #### 1. get_task_mm.c
引用自 [Process Descriptor - Understanding the Linux Kernel](https://www.oreilly.com/library/view/understanding-the-linux/0596002130/ch03s02.html)
> This is the role of the process descriptor — a **task_struct** type structure whose fields contain all the information related to a single process.

引用自 [Memory mapping - The Linux Kernel documentation](https://linux-kernel-labs.github.io/refs/pull/222/merge/labs/memory_mapping.html)
> struct mm_struct encompasses all memory areas associated with a process.

> struct vm_area_struct holds information about a contiguous virtual memory area. The memory areas of a process can be viewed by inspecting the maps attribute of the process via procfs

> [img src1](http://esos.hanyang.ac.kr/tc/2015gradproject2/i/entry/2)
> [img src2](https://stackoverflow.com/questions/63497757/why-does-the-vm-area-struct-have-start-code-end-code-field)
![img link](https://i.stack.imgur.com/0kIuB.jpg)

此系統呼叫能透過 pid 得到 current process 的 task_struct，再透過 task_struct 得到其成員 mm_struct，藉此存取 mm_struct 的成員 **mmap (a list of vm_area_struct)**, start_code,end_code, start_data, end_data ...

以下為原始程式碼 get_task_mm.c 的內容
-->


#### 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
```
<!--
編譯時須加上 -lpthread 選項
```gcc main.c -lpthread -o main```
-->

### 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 的狀況請見下方
<!-- ### Output of `dmesg`
此時再輸入 `dmesg` 會得到以下輸出

```
[  221.596637] start_code of mm_struct is 400000 (pa: d542d000)
[  221.596639] end_code of mm_struct is 401364 (pa: 6c9e364)
[  221.596639] start_data of mm_struct is 601e00 (pa: cfefce00)
[  221.596640] end_data of mm_struct is 6020a8 (pa: 41690a8)
[  221.596640] start_brk of mm_struct is 249e000 (pa: 11c47000)
[  221.596641] brk of mm_struct is 24bf000 (pa: ffffffffffffffff)

[  221.596641] mmap_base of mm_struct is 7fbd7d6f6000 (pa: ffffffffffffffff)

[  221.596642] start_stack of mm_struct is 7ffeb831db90 (pa: 1b85bb90)
[  221.596642] arg_start of mm_struct is 7ffeb831ee36
[  221.596643] arg_end of mm_struct is 7ffeb831ee3d
[  221.596643] env_start of mm_struct is 7ffeb831ee3d
[  221.596643] env_end of mm_struct is 7ffeb831fff1

[  221.596645] vm_start: 400000 (pa: d542d000)    vm_end: 402000    size: 2000
[  221.596645] vm_start: 601000 (pa: cfefc000)    vm_end: 602000    size: 1000
[  221.596646] vm_start: 602000 (pa: 4169000)    vm_end: 603000    size: 1000
[  221.596647] vm_start: 249e000 (pa: 11c47000)    vm_end: 24bf000    size: 21000
[  221.596648] vm_start: 7fbd70000000 (pa: d5591000)    vm_end: 7fbd70021000    size: 21000
[  221.596649] vm_start: 7fbd70021000 (pa: ffffffffffffffff)    vm_end: 7fbd74000000    size: 3fdf000
[  221.596650] vm_start: 7fbd777ff000 (pa: ffffffffffffffff)    vm_end: 7fbd77800000    size: 1000
[  221.596650] vm_start: 7fbd77800000 (pa: ffffffffffffffff)    vm_end: 7fbd78000000    size: 800000
[  221.596651] vm_start: 7fbd78000000 (pa: c98c000)    vm_end: 7fbd78021000    size: 21000
[  221.596652] vm_start: 7fbd78021000 (pa: ffffffffffffffff)    vm_end: 7fbd7c000000    size: 3fdf000
[  221.596653] vm_start: 7fbd7c4d0000 (pa: 10bb67000)    vm_end: 7fbd7c4e6000    size: 16000
[  221.596653] vm_start: 7fbd7c4e6000 (pa: ffffffffffffffff)    vm_end: 7fbd7c6e5000    size: 1ff000
[  221.596654] vm_start: 7fbd7c6e5000 (pa: 119c7000)    vm_end: 7fbd7c6e6000    size: 1000
[  221.596655] vm_start: 7fbd7c6e6000 (pa: ffffffffffffffff)    vm_end: 7fbd7c6e7000    size: 1000
[  221.596656] vm_start: 7fbd7c6e7000 (pa: ffffffffffffffff)    vm_end: 7fbd7cee7000    size: 800000
[  221.596656] vm_start: 7fbd7cee7000 (pa: 11fe3f000)    vm_end: 7fbd7d0a7000    size: 1c0000
[  221.596657] vm_start: 7fbd7d0a7000 (pa: ffffffffffffffff)    vm_end: 7fbd7d2a7000    size: 200000
[  221.596658] vm_start: 7fbd7d2a7000 (pa: 119f7000)    vm_end: 7fbd7d2ab000    size: 4000
[  221.596659] vm_start: 7fbd7d2ab000 (pa: 55e00000)    vm_end: 7fbd7d2ad000    size: 2000
[  221.596659] vm_start: 7fbd7d2ad000 (pa: d228f000)    vm_end: 7fbd7d2b1000    size: 4000
[  221.596660] vm_start: 7fbd7d2b1000 (pa: 11fe1a000)    vm_end: 7fbd7d2c9000    size: 18000
[  221.596661] vm_start: 7fbd7d2c9000 (pa: ffffffffffffffff)    vm_end: 7fbd7d4c8000    size: 1ff000
[  221.596662] vm_start: 7fbd7d4c8000 (pa: 42da000)    vm_end: 7fbd7d4c9000    size: 1000
[  221.596662] vm_start: 7fbd7d4c9000 (pa: d106e000)    vm_end: 7fbd7d4ca000    size: 1000
[  221.596663] vm_start: 7fbd7d4ca000 (pa: ffffffffffffffff)    vm_end: 7fbd7d4ce000    size: 4000
[  221.596664] vm_start: 7fbd7d4ce000 (pa: 11fd3e000)    vm_end: 7fbd7d4f4000    size: 26000
[  221.596665] vm_start: 7fbd7d6d4000 (pa: 1902b000)    vm_end: 7fbd7d6d8000    size: 4000
[  221.596665] vm_start: 7fbd7d6f3000 (pa: d54bb000)    vm_end: 7fbd7d6f4000    size: 1000
[  221.596666] vm_start: 7fbd7d6f4000 (pa: 1eb0000)    vm_end: 7fbd7d6f5000    size: 1000
[  221.596667] vm_start: 7fbd7d6f5000 (pa: 1a0b3000)    vm_end: 7fbd7d6f6000    size: 1000
[  221.596668] vm_start: 7ffeb82fe000 (pa: ffffffffffffffff)    vm_end: 7ffeb8320000    size: 22000
[  221.596668] vm_start: 7ffeb8331000 (pa: ffffffffffffffff)    vm_end: 7ffeb8334000    size: 3000
[  221.596669] vm_start: 7ffeb8334000 (pa: 69396000)    vm_end: 7ffeb8336000    size: 2000
``` -->


---
### Virtual Memory Layout
<!-- *(此 multi-thead program 的 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

<!-- 在 [此開發環境下](https://hackmd.io/8LilirqBQQ6oZR1pFr6Shw?view#Environment) PIE (Position Independent Executables) 預設不會開啟，text segment 的位址不會隨機變動，配置於 data segemnt, BSS segment 的變數位址也不會改變，每一次執行時上述的變數位址輸出均為固定 (`&global_str` 與 `&BSS_str`) -->

#### 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)
