What can we learn from digging stack?

stack是資訊科學裡的基本概念之一，許多精妙的演算法依賴stack的先進後出特性來實現，而其演算法實現因為function call已經依賴於stack的機制，並且由編譯器幫我們產生相關機器碼，所以往往不需在代碼中手動操作stack。

精妙的演算法將function call視為理所當然，以此為基礎往上發展遞迴算法，但除了往上看高階演算法之餘，不妨花點時間往下從機器的角度看看function call的實現，理解了其實現原理後，我們就會發現，許多巧妙的系統程式機制其實都可以此為基礎開展而來：

• variable numbers of function parameters：透過解析stack上的參數，獲知使用者到底在參數列指定了幾個參數，然後再依序從stack上讀取參數來進行後續動作，可以參考對岸好手李先靜的文章。
• backtrace：由於返回的位址與前一個stack frame的base address都可以從目前的stack frame中獲得，所以要實現backtrace就只需反覆讀取前一個stack frame所存的base address即可，可以參考我之前的文章。
• OS bootstrap：當CPU一開機時並沒有高階語言可以執行的環境，所以只能使用assembly去實現一開始的部份。有趣的是，要如何從assembly切換到C function？基本上只要先stack frame可以正常使用，就能夠完成這項任務。然後，其他功能就繼續慢慢bootstrap~JOS或許是最容易理解的實現，逐步的設定說明在這份文檔的appendice B。
• context switch：作業系統中的多個task要進行切換才能方便實現多工與保護。而這個切換的工作概念上需要兩個步驟：scheduling(選出下一個task)以及context-switch(從目前task切換到下一個task)。在context switch中很重要的一步就是回到之前暫停的指令位址以及stack frame，所以必須從某個per-task的記憶體讀取出相關暫存器來恢復context。ClearRTOS的實作或許最容易理解，因為有專書說明。:-)
• coroutine：jserv的好文章講得非常清楚，也附上了簡易實作。
• ...

很多有趣的系統程式與程式語言機制其實都與操弄stack拖不了關係，我發現如果不想常常在切換到系統層面時就對細節的掌握感到沒有把握的話，熟練地從機器的角度來理解stack的動作就應該列入必備的基本功夫之中。:-)