鏈接器是如何一步步發明出來的？

在計算機編程的早期年代，你面臨一個揮之不去的的噩夢。。。

你找了一個剛剛運行成功的程序仔細看了看：

你一眼就注意到main.asm中的那些數字了，0x1234和0x5678。

這些是函數在最終內存中的絕對地址，也是所有程序員的噩夢，因爲這些地址都是程序員手動計算出來的！

例如，如果math.asm被加載到內存地址0x1000，而add函數在模塊內的偏移是0x234，那麼add的絕對地址就是0x1234。

這個過程不僅繁瑣，而且極易出錯，更糟糕的是維護問題。

牽一髮而動全身

你清楚地知道，如果程序員在math.asm的開頭添加了一個新函數，會發生什麼！

這個看似無害的修改會導致add函數的位置發生變化！它的偏移量增加了，絕對地址也隨之改變。現在，main.asm中的call 0x1234指令將跳轉到錯誤的位置！

程序員必須重新計算add函數的新地址並修改所有調用add的地方。

如果程序有數十個模塊，數百個函數調用，這個過程將變成一場噩夢，每次修改代碼，都可能引發一連串的地址更新工作。

於是你的開始思索，需要一種機制，能夠自動處理這些地址綁定，讓程序員們專注於代碼邏輯而非地址計算，爲實現這種機制就決不能在程序中使用絕對內存地址！

窮則思變

不使用內存地址使用啥呢？

此時你想到當你找喊一個人的時候直呼其名而不是喊這個人的經緯度座標，對了！這裡也可以使用名字而不是地址來引用函數和變量，想到這裡符號（Symbol）概念誕生了。

是啊，爲啥要用內存地址硬編碼，程序員可以使用符號啊：

這種方法的核心思想是：程序員只需關心名字（如add、print），而不必關心這些函數最終在內存中的確切位置。

這是一個巨大的抽象飛躍！

你設計的符號概念帶來了2個關鍵優勢：

減少錯誤：不再需要手動計算和更新地址，消除了一大類潛在錯誤。

簡化維護：當函數位置變化時，只需保持符號名不變，調用代碼無需修改。

最重要的是，符號爲自動化解決依賴關係奠定了基礎。

遺留問題

符號概念是很優雅，但問題是：如何確定符號名最終的內存地址呢？

顯然這次需要有一個能夠自動確定符號最終內存地址的工具，讓程序員徹底擺脫地址計算的負擔，到底該怎麼做到呢？

要達到這個目的就不能讓編譯器直接生成機器碼，而是把這個過程拆成兩步：

編譯器處理各個模塊，但不必關心跨模塊引用

根據各個模塊提供的信息來確定符號最終的內存地址併合並所有的模塊爲一個最終可執行文件

就這樣在你的設想中你把整個編程過程拆成了兩步，第一步是編譯、第二步你將其稱之爲鏈接，link。

第二步中各個模塊提供的信息還是比較模糊，這個信息是什麼，該怎麼提供？

目標文件的誕生

既然編譯器不直接生成最終的機器碼，那麼就需要一種文件來承接這一階段編譯器的輸出，這個用來記錄編譯器第一階段輸出的文件就是所謂的目標文件，Object File。

這個文件包含機器碼，但不去確定引用的外部符號的內存地址：

你把所有這樣的符號收集起來記錄來目標文件中，這就是所謂的重定位表（Relocation Table），標記代碼中需要在鏈接時填充正確地址的位置，這就是所謂的重新定位，重定位。

同時這個文件記錄模塊定義的所有符號（函數、變量）及其相對位置，這就是所謂符號表（Symbol Table）：記錄模塊定義的所有符號（函數、變量）及其相對位置。

它們可能長這樣：

目標文件的出現是一個關鍵突破，因爲它：

分離了編譯和鏈接：編譯器只需關注單個模塊的翻譯，不必處理跨模塊引用。

明確記錄了依賴關係：每個模塊清楚地表達了"我提供什麼"（符號表）和"我需要什麼"（未解析引用）。

爲自動化鏈接提供了數據結構：重定位表明確標記了需要修正的地址位置。

現在， 你的任務就變得明確了：讀取多個目標文件，解析它們的符號和依賴關係，然後將它們正確地"鏈接"在一起。

但如何實現這個鏈接過程？很明顯，你需要實現兩個核心算法：符號解析和重定位。

符號解析與重定位

符號解析解決一個基本問題：將每個模塊的"需求"與其他模塊的"供給"匹配起來。

具體來說，你需要：

收集所有符號：遍歷每個目標文件的符號表，建立一個全局符號字典，記錄每個符號的定義位置。

檢查未解析引用：對每個模塊的未解析引用，在全局符號字典中查找其定義。

處理衝突和錯誤：如果一個符號有多個定義（衝突）或沒有定義（未解析），生成適當的錯誤信息。

如果所有未解析引用都能在全局符號表中找到對應的定義，符號解析就成功了。否則，你的算法會生成一個錯誤，這就是後來的程序員熟悉的"undefined reference to..."。

符號解析解決了"符號供需匹配"問題，重定位的任務是：確定每個模塊和符號在最終內存中的確切位置。

重定位過程包括：

內存佈局規劃：決定各個模塊在最終內存空間中的排列順序和基址。

地址計算：根據模塊基址和符號在模塊內的偏移，計算每個符號的最終絕對地址。

填充重定位條目：遍歷每個模塊的重定位表，將正確的地址填充到代碼中的相應位置。

符號解析和重定位這兩個步驟解決了模塊化編程中最核心的問題：如何讓分散在不同文件中的代碼片段正確地找到並調用彼此。

鏈接器的誕生

至此，這兩個核心算法的實現徹底解放了程序員，讓他們不再需要手動計算和修改地址。

來源：碼農的荒島求生

編輯：未

轉載內容僅代表作者觀點

不代表中科院物理所立場

如需轉載請聯繫原公衆號