 |
| 熱極則風, 花盛必謝。 |
噢! 當然戰文本身也是很精彩的, 這系列文章有些你來我往的回文, 只要能說出個道理, 都是能從中學到東西的。
coroutine 之前研究過, 它是主動讓出 cpu 執行權, 如果不主動讓出, 該怎麼在執行的 function 中讓出 cpu 呢? os 靠的是 timer 中斷, user mode 程式要怎麼作到類似的效果呢?
在查詢資料的過程, 找到 pthreads-1_60_beta6.tar.gz 這個 user mode pthread, 是由 Chris Provenzano 開發的 pthread 實作品。
這是搭配 linux kernel 1.X 用的 pthread library, 只支援 x86 32bit, 那時候的 linux kernel 還沒有 kernel thread 支援, 我像是挖到寶似的, 想看 Chris Provenzano 是怎麼辦到的, 本想編譯起來用 gdb 追蹤, 不過在目前的環境似乎編不起來, 我放棄了。而我追 code 能力太差, 沒有從 souce code 看出什麼端倪。
另外找到一個課程的作業 - CS170: Project 2 - User Mode Thread Library (20% of project score), 我的媽呀! 還真的有這樣的課程, 不禁為他們學生默哀, 這應該會是讓他們困擾很久的作業的吧! 這是 ucsb 的 os 課程。
ucsb 中文是 - 加州大學聖塔芭芭拉分校, 不太熟悉這間學校。
看到這些學校的作業是這麼的扎實, 記得自己的 os 課程就是教課書 - Operating System Concepts 的內容, 考試則是課本上的知識, 程度真的差太多, 實作太少了, 這樣和非本科的差距並不會太大, 如果是會寫一個 user mode thread library, 和非本科的差距就顯現出來了。
以前老師給了另外的選擇, 看 bsd source code, 不過被全班投票的結果否決了, 真的可惜。
但是該課程也沒那麼狠心, 在 Implementation 一節中, 說明的一些實作細節, 用著我的破英文很勉強的看了看, 得知了幾個關鍵。
需要使用 setjmp/longjmp, signal。
如果對 setjmp/longjmp 很陌生, 可參考 - setjmp/longjmp 實作 (x86 32 bit)。
知道這個概念之後, 相當高興, 以為可以順利寫出來, 但在我開始下手時, 卻發現困難重重, 我不知道應該在哪裡執行 setjmp, 在哪裡執行 longjmp。
ex.c 我該在哪裡插入 setjmp 呢? ex.c L3 ~ L7 之間嗎? 都不對阿! longjmp 應該安插在哪裡呢?
Implementation 原來還有背面, 我漏看了, 重新看過之後得到以下心得:
- setjmp/longjmp - 這個用來保存 2 個 function 切換的狀態, 還需要特別保存 stack。
- signal/SIGALRM - 這個就是我百思不得其解的關鍵, 使用 signal 來中斷正在執行的 function, 在 signal handler 中, 保存正在執行的 function 狀態 (使用 setjmp), 再選出一個 function, 跳去執行它 (透過 longjmp)。
CS170: Project 2 - User Mode Thread Library (20% of project score)
Project Goals
- to understand the idea of threads
- to implement independent, parallel execution within a process
Administrative Information
Implement a basic thread subsystem in Linux user mode
The most well-known and wide-spread standard that defines the interface for threads on Unix-style operating systems is called POSIX threads (or pthreads). The pthreads interface defines a set of functions, a few of which we want to implement for this project. Of course, there are different ways in which the pthreads interface can be realized, and systems have implemented a pthreads subsystem both in the OS kernel and in user mode. For this project, we aim to implement a few pthreads functions in user mode (as a library) on Linux.
More specifically, for this project, we want to implement the following POSIX thread functions (prototypes and explanations partially taken from the respective man pages):
int pthread_create(pthread_t *restrict thread, const pthread_attr_t *restrict attr, void *(*start_routine)(void*), void *restrict arg);The pthread_create() function shall create a new thread within a process. Upon successful completion, pthread_create() shall store the ID of the created thread in the location referenced by thread. In our implementation, the second argument (attr) shall always be NULL. The thread is created executing start_routine with arg as its sole argument. If the start_routine returns, the effect shall be as if there was an implicit call to pthread_exit() using the return value of start_routine as the exit status. Note that the thread in which main() was originally invoked differs from this. When it returns from main(), the effect shall be as if there was an implicit call to exit() using the return value of main() as the exit status.
void pthread_exit(void *value_ptr);The pthread_exit() function shall terminate the calling thread. In our current implementation, we ignore the value passed in as the first argument (value_ptr) and clean up all information related to the terminating thread. The process shall exit with an exit status of 0 after the last thread has been terminated. The behavior shall be as if the implementation called exit() with a zero argument at thread termination time.
pthread_t pthread_self(void);The pthread_self() function shall return the thread ID of the calling thread.
The goal of this project is to implement the three functions introduced above. For more details about error handling, please refer to the respective man pages. The code for these three functions should be compiled into an object file called threads.o, which will act as our thread library. Note that your code will not contain a main routine, and hence, cannot run as a stand-alone executable. To create the thread library, simply call the compiler like this:
gcc/g++ -c -o threads.o [list of your source files]You should include the pthreads header file (#include
gcc/g++ -o application [list of application object files] threads.oTo test your thread implementation, we will compile your thread library with our test application. This test application will call into your pthread functions and check whether threads are properly started and terminated.
Implementation
First, you will need a data structure that can store information about a single thread. This data structure will likely need to hold, at least, information about the state of the thread (its set of registers), information about its stack (e.g., a pointer to the thread's stack area), and information about the status of the thread (whether it is running, ready to run, or has exited). This data structure is often called a thread control block (TCB). Since there will be multiple threads active at the same time, the thread control blocks should be stored in a list or a table (array). To make it easier, you can assume that a program will not create more than 128 threads.
You will likely need a routine that initializes your thread subsystem. This init routine should be called when the application calls pthread_create for the first time. Before that, there is only one thread running (the main program), and there is not much you need to do.
Once multiple threads are running, you will need a way of switching between different threads. To do this, you could use the library functions setjmp and longjmp. In a nutshell, setjmp saves the current state of a thread into a jmp_buf structure. longjmp uses this structure to restore (jump back) to a previously saved state. You will find these functions very useful, since they do exactly what is needed when switching from one thread to another and later resuming this thread's execution. More precisely, you can have the currently executing thread call setjmp and save the result in the thread's TCB. Then, your thread subsystem can pick another thread, and use the saved jmp_buf of that thread together with longjmp to resume the execution of the new thread.
The process of picking another thread is called scheduling. In our system, we want to have a very simply scheduler. Just cycle through the available threads in a round robin fashion, giving an equal, fair share to each thread.
Following the discussion about setjmp and longjmp, there is one question that should immediately arise: How can we force the thread of a program to call setjmp every once in a while (and thus, giving up control of the CPU)? In particular, application developers do not need to know about your thread implementation, so it is unlikely that they will periodically call setjmp and allow your scheduler to switch to a new process. To solve this issue, we can make use of signals and alarms. More precisely, we can use the ualarm or the setitimer function to set up a periodic timer that sends a SIGALRM signal every X milliseconds (for this project, we choose X to be 50ms). Whenever the alarm goes of, the operating system will invoke the signal handler for SIGALRM. So, you can install your own, custom signal handler that performs the scheduling (switching between threads) for you. For installing this signal handler, you should use sigaction with the SA_NODEFER flag (read the man page for sigaction for details). Otherwise (e.g., when using the deprecated signal function, alarms are automatically blocked while you are running the signal handler. This is something that we clearly do not want for this project.
Note that we require that your thread system supports thread preemption and switches between multiple threads that are ready. It is not okay to run each individual thread to completion before giving the next one a chance to execute.
A final problem that needs to be addressed is how to create a new thread. We have previously discussed means to switch between two threads once they have been created. However, there must also be a mechanism to create a new thread "from scratch." To this end, the system has to properly initialize the TCB for the new thread. This means that a new thread ID needs to be created. In addition, the system has to allocate a new stack. This can be done easily using malloc. For this project, we want to allocate for each thread a stack of 32,767 bytes. The last step is to initialize the thread's state so that it "resumes" execution from the start function that is given as argument to the pthread_create function. For this, we could use setjmp to save the state of the current thread in a jmp_buf, and then, modify this jmp_buf in two important ways. First, we want to change the program counter (the EIP) to point to the start function. Second, we want the stack pointer (the ESP) to point to the top of our newly allocated stack.
To modify the jmp_buf directly, we have to first understand that it is a very operating system and processor family-specific data structure that is typically not modified directly. On the CSIL machines, we can see the definition of the jmp_buf here in this header file: /usr/include/bits/setjmp.h. Given that we work on a 64-bit machine on CSIL, the jmp_buf is defined as an array of 8 long (64-bit) integers. Moreover, libc (x86_64/jmpbuf-offsets.h) defines the following constants as the eight integer elements of this structure:
#define JB_RBX 0 #define JB_RBP 1 #define JB_R12 2 #define JB_R13 3 #define JB_R14 4 #define JB_R15 5 #define JB_RSP 6 #define JB_PC 7We can see that the stack pointer (RSP) has index 6 and the program counter (PC) has index 7 into the jmp_buf. This allows us to easily write the new values for ESP and EIP into a jmp_buf. Unfortunately, there is a small complication on the Linux systems in the lab. These machines are equipped with a libc that includes a security feature to protect the addresses stored in jump buffers. This security feature "mangles" (i.e., encrypts) a pointer before saving it in a jmp_buf. Thus, we also have to mangle our new stack pointer and program counter before we can write it into a jump buffer, otherwise decryption (and subsequent uses) will fail. To mangle a pointer before writing it into the jump buffer, make use of the following function:
static long int i64_ptr_mangle(long int p)
{
long int ret;
asm(" mov %1, %%rax;\n"
" xor %%fs:0x30, %%rax;"
" rol $0x11, %%rax;"
" mov %%rax, %0;"
: "=r"(ret)
: "r"(p)
: "%rax"
);
return ret;
}
We are almost there. Now, we just have to remember that the start routine of every new thread expects a single argument (a void pointer called arg). Also, when the start routine returns, it should perform an implicit jump to pthread_exit. We first have to understand how arguments are passed between functions. When you think back to your compiler class, you might remember that arguments were passed on the stack. Indeed, this was the way it was done on "old" 32-bit x86 machines. However, we now have 64-bit machines, and these machines have more registers. To improve the performance of function calls, compiler writers decided to leverage these additional registers. More specifically, the function calling convention was changed, and the first six arguments are passed in registers. Only the 7th argument and onwards are passed on the stack. This page provides some more details about this. Now, the question is how we can pass the required argument to the start function of the thread? One possible solution is to introduce a wrapper function. This wrapper function could grab the argument from the TCB and then invoke the actual start function, passing it the required argument. In addition, the wrapper function also provides a convenient way to handle the case when the start function returns and you have to call pthread_exit. For this, you can simply invoke pthread_exit after the thread returns from the previous call to the start function. When you use a wrapper function, you need to make the program counter (EIP) point to this function instead of the actual start function. And you need to find a way to make the address of the start function available to the wrapper. Once your stack is initialized and the (mangled) stack pointer (ESP) and program counter (EIP) are written to the jmp_buf, your new thread is all ready to go, and when the next SIGALRM arrives, it is ready to be scheduled!
This is a complicated project. Take it one step at a time, and make sure that everything works before moving on. Also, the debugger (gdb) is your friend. Expect that the code will crash. At this point, use the debugger to understand what is going on. For this project, you might want to look at the gdb commands disassemble and stepi. For example, your code might crash when you invoke longjmp for the first time to switch to a new thread, and you don't understand why. To debug this problem, you could set a breakpoint in __longjmp (say yes when the debugger asks whether you want to "make breakpoint pending on future shared library load"). Since __longjmp is a libc library function, you don't have the source directly available to the debugger. However, you can issue the disassemble command to show the assembly code for this (short) function. And you can use stepi to step forward for a single machine (assembly) instruction. This allows you to check if you restore the correct register values and also see the address where you end up jumping to. You can use the commands info registers to list the content of all the CPU registers, and you can use x [address] to print out the value that is stored in the memory at [address]. This is nice when you want to see where your stack pointer points to.
Deliverables
- We use gradescope to manage your project submissions and to communicate the results back to you. You will submit all files that are part of your project via the gradescope web interface.
- All your files must be in a directory named threads. The name of the threads library that we will test must be threads.o, and the POSIX function implementation must be done in C/C++. Of course, you cannot leverage any of the existing pthread library code to implement your thread library.
- All files that you need to build your library must be included (sources, headers, makefile) in that folder. We will just call make and expect that the object file threads.o is built from your sources. Please do not include any object or executable files.
- Gradescope does support built-in autograding, but, currently, we do not intend to use it. Instead, we will test your projects in our own environment. So, do not worry if you don't get immediate feedback or if the system tells you that the autograder is not running.
- Your project must compile on a CSIL machine. If you worked on a Windows machine or your laptop at home, then make sure it still works on CSIL or modify it appropriately!
- Include a README with this project. Explain what you did in the README. If you had problems, tell us why and what.
其實在看提示之前, 我有想到應該在 signal handler 使用 setjmp/longjmp, 只是我被自己迷惑了, 因為在 signal handler 的 stack, 已經不是原本程式的 stack, 為了跳到 signal handle, kernel 對原本的 stack 做了修改, 我自以為在這裡保存這個 stack 是沒有用的, 是我自己想太多了。
基本概念是這樣, 假設我們有 func1, func2 這 2 個 function, func1 先執行, 使用 alarm signal, 讓 5ms 發動一次 alarm signal, 5ms 就會呼叫一次 signa handler, 這時候就可以在這裡將目前執行的 function - func1 setjmp 起來, 然後使用 longjmp 跳到 func2 去執行, 這樣就完成了 5ms 切換 func1, func2, 就達到了 user mode thread 的效果。
這個概念和 os 的 process 切換是類似的。
而對 func1, func2 來說, 需要有各自的 stack, 這樣才不會有相互蓋到 stack 的問題, 使用 setjmp 來保存 register 資料外, 還需要提供一個 stack 空間, 所以要把 jmp_buf 的 esp 欄位改到預先準備好的 stack 空間, simple_thread.c L112, L117。
另外要修改 jmp_buf 的另外一個欄位是 eip, 需要把它指到 func1, func2 的開頭, 這樣一來, longjmp 就會從 func1, func2 的開頭執行。
而不幸的是, jmp_buf 和執行的 cpu 有關係, 所以得要搞懂這個平台的 jmp_buf 是怎麼安排這些暫存器的資料結構。
Implementation 還提供了另外一個重要的訊息, 由於為了安全, jmp_buf 都會被用一個演算法保護起來, 避免被亂改, 所以 Implementation 提供了一段程式碼幫助同學處理這部份。
我沒有用這些方式, 我懶得搞懂這些, 我只想搞懂 user mode thread 怎麼做而已, 所以準備了自己的 setjmp/longjmp, 叫做 my_setjmp, my_long_jmp, 當然對應的 jmp_buf 就是 my_jmp_buf。
再來還剩下一個難題: 在 signal handler 發動自己準備的 my_longjmp 之後, 會發現之後的 signal handler 不會再次被呼叫了, 這裡存在一個很難發現的魔法, 需要對 singal 是怎麼實作有點了解才會知曉或是閱讀相關介紹 signal 書籍, tlpi (The Linux Programming Interface) 那本就不錯, 經典的 apue (Advanced Programming in the UNIX Environment) 當然也是。
如果想知道 signal 是怎麼實作的話, 可以參考「Linux 内核源代码情景分析」6.4 一節。
總之在 signal handler 被呼叫之後, 預設情形這個 signal 會被 block 起來, 直到 signal handler 返回之後, 才會被 unblock, 這時候, 同個 signal 來了之後, 這個 signal handler 才會再次發動。
但是我們的 signal handler 並不會正常返回, 因為我們用 longjmp 跳到 func1 或是 func2, 所謂的 signal handler 正常返回是指在 signal handler return 之後, 還會呼叫 sigreturn (man sigreturn), 這時候會從 user mode 再次切回 kernel mode, 然後才有機會把原來被中斷的地方再次安插回原本的 stack, 如此一來, 下次這個 process 執行的時候, 才會從被中斷的地方繼續執行。所以被 block 的 SIGUSR1 會被一直 block 住, 導致之後的收到 SIGUSR1 後, 都不會再執行 signal handler。
所以要在 simple_thread.c 加入 L62 ~ L64, unblock SIGUSR1。
但是如果你是使用 libc 的 setjmp/longjmp, sigsetjmp/siglongjmp 可能不需要自己 unblock SIGUSR1, 系統的 setjmp/longjmp 可能會處理被 block 的 signal, 如果用 _setjmp/_longjmp 就不會處理 signal, 類似我用自己的 my_setjmp, 這時候就要自己 unblock SIGUSR1。
這邊會遇到進階的 signal 議題, 例如: signal handler 可以被中斷嗎? 在執行 signal hadnler 時, 如果有 2 個 signal 送過來, signale handler 會再次執行 2 次嗎? 如果對這些議題不熟也沒關係, 以這個範例來說, SIGUSR1 signal handler 在執行的時候, 如果再次收到 SIGUSR1, 會等到原本的 SIGUSR1 signal handler 做完, 然後才會再次執行。
這是可以設定的, 那一種作法好呢? 我還沒有答案。
而如果在執行 SIGUSR1 signal handler 期間收到 2 次以上的 SIGUSR1, 之後只會再執行 SIGUSR1 signal handler 一次, 這樣的行為讓你有點擔心吧, 這表示很有可能 func1, func2 的切換行為有可能會漏掉幾次, 是的, 沒辦法, 傳統 signal 就是這麼「不可靠」。
signal 相關問題可參考 - linux/unix signal 議題
疑! 剛剛不是說要用 SIGALRM, 怎麼變成 SIGUSR1, 因為後來發現用 SIGUSR1 比較好測試, 就改用這個了。
程式在 setjmp func1, func2 之後, 會使用 longjmp 執行 func2, 再來就是透過 signal handler 來切換到 func1, 再來又透過 signal handler 再次切換到 func2, 依序下去。
func1 印出 123456789a, function 印出 21 22 23 24 25, 可以從以下影片看出, 當送出 SIGUSR1, func1 和 func2 會相互切換, 基本上算是成功了。當然離完成 pthread 這樣的 library 還很遠, 而且還有很多沒有考慮到, 但至少邁出一小步了。而我的「目的」當然也只是想知道 user mode thread library 是怎麼做的, 也不是想寫出一個 pthread library, 有興趣的朋友可以繼續下去, 完成 ucsb 的作業。
例如: main thread 並沒有繼續下去, 這個版本只會在 func1, func2 交錯執行, main 之後的程式再也不會執行。當然還有一堆不完整的東西沒有實作, 後來我開始實作某些 pthread function, 才發現我漏了很多東西, 而且這些東西難度也不低。只有這個主要觀念離簡單 pthread 實作都還很遠。
可以用以下指令送出 SIGUSR1
killall -s SIGUSR1 simple_thread
整個程式從開始到完成期間: 20200220 ~ 20200226, 20200312 補上 x86_64 setjmp/longjmp 的版本。
CS170 作業可不是只要求這樣, 再來還需要有 atomic 的操作, 要寫支援 mutex 這個作業, 是不是又感覺害怕了。我搞錯了, 不需要到 atomic 的操作, 只要類似關中斷的行為即可, 這個難度就下降很多。
這個作業都是基本中的基本, 但是基本問題可不等於簡單問題, 這些觀念過了在久, 都不會改變的, 把心思花在上頭並不會隨著時間而白費。
好了, 再來就是真的切換 thread, 只要把 SIGUSR1 換成 SIGALRM, 設定成 1 秒切換, 這樣 func1, func2 就會在 1 秒內切換, 你說 1 秒太慢了, 也可以換成 ms, 就留給各位朋友當作業了。
以下影片展示 gdb debug, 同時顯示 c/asm source code 和 asm 的 debug 視窗, 可以看到 setjmp/longjmp 是怎麼運作的。
ctrl+x 2 開啟 2 個視窗 layout asm 開啟 asm debug ctrl+x o 可以切換視窗 最上方是 source code 中間是反組譯的組合語言 最下方是 gdb 指令區
我的 simple 系列又多了一筆 - simple_thread, 不過 simple 系列一點都不 simple。
soure code:
https://github.com/descent/simple_thread
user mode thread implementation:
- ftp://ftp.gnu.org/gnu/pth/pth-1.0.0.tar.gz
- ftp.ai.mit.edu/pub/rst/rsthreads.tgz
- https://stuff.mit.edu/afs/sipb/project/pthreads/stable/src/release/pthreads-1_60_beta6.tar.gz
ref:
以下資訊感謝 KILLE 提供:
這是另外一個簡單的實作 (感覺像是修 CS170 的學生):
https://github.com/DennisZZH/User-Mode-Thread-Library
另外可參考的實作:
https://github.com/prabhendu/operating_system_1/blob/master/gtthread.c
https://github.com/citrix123/Uthreads/blob/master/uthread.c
徹底理解setjmp/longjmp並DIY一個簡單的協程
https://www.twblogs.net/a/5ccbd4fabd9eee1ac30bd85c
彻底理解setjmp/longjmp并DIY一个简单的协程
https://blog.csdn.net/dog250/article/details/89742140
感謝分享，這方面的文章很稀少XDD
回覆刪除和日本壓縮機一樣稀少。
回覆刪除看的人也不多, 大部份的技術文章也都是此類風格。
很高興你有興趣。