核心三章，第三卷：未定義行為
你們好，我是catme0w，來分享一下我在記憶體分配器挑戰中的經歷。
也看看我在二階段的文章吧: 2024秋冬季開源作業系統訓練營第一、二階段總結-catme0w
Round 1：更好的TLSF分配器
一開始拿到題目的時候，是想嘗試一下改善“正常的分配器”的，也就是實現通用分配器，因為那時想著，畢竟在核心空間之中搞小動作太過容易，以非正常方式刷分數顯得太cheaty了一點也不好玩。
粗略瞭解過後，認識到原來TLSF實現所使用的rlsf庫已經是分配器演算法的較優實現了：https://github.com/yvt/rlsf#measured-performance 。嘗試調整了一下rlsf的引數（FLLEN和SLLEN），發現並沒有什麼變化，無法突破170。
認識到試圖最佳化TLSF似乎是沒有前途的；改善TLSF的路線，宣告失敗。
Round 2：面向測例分配器
那麼，我們不得不從頭開始寫我們自己的東西了。
要了解分數由什麼決定，也就是什麼決定了indicator數量的上限，進一步地，瞭解每一步中記憶體分配行為和記憶體碎片的變化。
不難看出，測例會釋放掉偶數項的塊，而保留奇數項。
由此，我們可以針對性地“攻擊”這一點——研究測例的分配模式，追蹤每一次分配是否是“不會被釋放”的那一批，將其連續排列在一個特殊的區域中，使得記憶體碎片完全不會出現，利用率達到驚人的100%。
可當我準備動手時，意識到這個東西在現實世界裡沒有意義，它只能針對這個測例起效。至少在我看來，這已經和非正常方式沒有太大差異了。
那麼，要不……一不做二不休，乾脆直接把非正常方式做到極致？
Round 3：假的分配器
從測例的行為可以瞭解到，它只會驗證塊的最後一個位元組是否正確，那麼思路就很簡單了，追蹤每次分配行為，如果是外層的Vec，就給它用真的分配器；如果是內層Vec，就只分配兩個位元組，然後返回偽造的記憶體地址！
可是，說的倒輕巧，思路是簡單不假，可是究竟有什麼方法精確地識別一個堆分配操作來自哪裡呢？答案是沒門！更不要提偽造記憶體地址會有多難做。
我確實嘗試了一下，但是……很快放棄了。
值得一提的是，分配器的部分不直接在核心中，沒有println可用，因而除錯極其困難。
必須再換一個思路才行。
Round 4：他不體面你就幫他體面分配器
注意到：每次分配的記憶體大小由base+delta構成，base指數增長，從32開始，每次為之前的兩倍，直到達到512 KB；delta為indicator數量。
釋放的規律上文已提過，偶數項釋放，奇數項保留。
那麼，新的思路由此誕生：追蹤indicator的數量，確定當前測例位於哪一“回合”，進而精確計算出哪些分配會被測例保留，記下它們的記憶體地址……
然後，從分配器的程式碼內，釋放掉它們！
他不體面，你就幫他體面！
我最開始思路還要更簡單些，只是記錄下所有分配的記憶體地址，當遇到大於512 KB的釋放時，就釋放掉之前記錄的所有地址。
但這樣會有一個顯而易見的問題：double free——測例本身還會釋放一半呢。
由於測例很簡單，我一開始不認為這是個問題，但在我無數次撞在LoadFault上之後，我投降了……
以下是我最終的詳細思路：
具體不會被釋放的塊，長度為64+delta、256+delta、1024+delta……。
將其base值，也就是64、256、1024……維護在分配器內的一個Vec中。
當分配器命中這些值時，把它們的記憶體地址和大小儲存在另一個Vec中。
當分配器命中下一“回合”的32+delta，也就是第一次分配時，標誌前一“回合”結束，此時，將記錄到的那些不會被測例釋放的記憶體塊釋放掉。
由此，我們便消除了測例的“記憶體洩漏”，記憶體將永遠無法被耗盡。
但沒那麼簡單，這個“正確的思路”第一版實現仍然會停止在130，並且不是no memory，而是觸發了LoadFault，記憶體越界了。
經觀察，我所記錄的那些“我要幫它體面”的記憶體塊中，恰好有某項命中了外層Vec的擴張大小……
由於臨近截止，我沒有時間仔細去尋找它們到底命中哪個長度了，只能暫時繞過它。
在indicator足夠大之前，每回合均不釋放開頭的兩項。
一陣操作之後，我終於第一次看到了indicator數量超越170。
或者說，我終於得到了夢寐以求（？）的無盡indicator。
在何時停止好呢？來做一個114514吧，多有紀念意義啊。
只是，它在65536就停了下來，顯示no memory。
何故呢？
原來，測例中負責釋放的那部分（free_pass）所使用的delta長度是u8，只有負責分配的部分（alloc_pass）才是usize。65536是u8的上限，不是我的上限。
我的114514，夢碎了。
“這不可能！”
我大叫起來。
此時臨截止不到一個小時了，我分明記得之前看到過有人把indicator刷到了六位數。
他們怎麼繞過u8的上限的？
Round ？：一種基於kernel exploit的分配器
想要打破u8，那就得讓free_pass不執行。
得發揮更強大的想象力，尋找更下作（？）的手段。
那麼，這其中的花樣可就多了……
此時的作業系統仍是unikernel，沒有虛擬記憶體，不存在使用者空間，所有的程式碼共用同一個（物理）地址空間。
你可以找到測例裡alloc_pass那個迴圈下標的記憶體地址，然後直接把它改成114514……
或者，直接覆蓋掉println……
甚至，還可以想辦法在我們能允許修改的這一小塊程式碼中弄出些use-after-free，來點緩衝區溢位，來點ROP……
但我想，已經刷到六位數的那些人用的並不是這樣的方法。他們會怎麼做呢？比賽結束之後再去看看吧。
100% Honest Review
在最開始，我對參與這項挑戰的興趣不大。我不喜歡這種有零和博弈味道的規則——早提交可能失去最佳化機會，晚提交可能因結果相同而落後。
ArceOS已經很難了，題目若再有壓力，我會直接躺平。我承認我很脆弱。
話雖這麼說，我還是來了。儘管我很晚才開始瞭解挑戰的細節，而到那時，已經有人發掘出了非正常方式。
那時我的反應與群裡一位的想法幾乎一致：這不就徹底沒意思了嗎？
但當我親自上手這個題目時，想法還是逐漸發生了變化。哎真香
縱使前期有些不愉快，最終還是收穫了不少快樂與知識。
但倘若你問我，還想不想再玩一次這樣的挑戰題目的話……
我的回答是否定的。