Skip to main content

Posts

linker (ld) 在做 symbol resolving 的 order 跟過程

嘗試想要從 linker 中偷到一些有用的資訊來判斷 caller 跟 callee 之間的關係. 而 linker 的確夠複雜, 而且非常 undocumented, 因此記錄下來, 不僅分享, 也讓我當之後忘記這複雜的 detail 後不要重新推敲, 可以回頭看這篇文章即可.

1) 首先來說說 linker 在一堆 .so (shared library) 裡面找 undefined symbol 的過程:

若在 link 的過程中, 要在 command line 指定的多個 .so 檔中搜尋一個 undefined symbol, 搜尋的順序是以 breadth-first-search 的方式進行. 這是 ELF format 定義的方式: (From ELF spec)
When resolving symbolic references, the dynamic linker examines the symbol tables with a breadth-first search. 這個就要舉例來說明了, 否則很難懂.

如果 link 時候的 command line 指定要 link a.so, b.so, c.so, 而 a.so 依靠 a_1.so, a_1.so 又依靠 a_2.so. c.so 依靠 c_1.so. 則以圖形表示如下:

--- a.so --- b.so --- c.so
      |                       |
      +--- a_1.so        +--- c_1.so
                 |
                 +--- a_2.so

這是一個 .so 的 tree, 所以尋找 undefined symbol 就以 breadth-first-search 來進行. 也就是會以下面的順序來尋找: a.so --> b.so --> c.so --> a_1.so --> c_1.so --> a_2.so

是的, 沒看錯, 就是這樣. ld 的確就是這樣在 .so 裡面找 undefined symbol 的.

2) 再來說說 linker 在一堆 .a 檔案 (archive, 也就是 static library) 裡面尋找 un…

My simple Excel gantt chart template

For doing task management well, I found that vertex42 does make a good Excel gantt chart template. However, I can not modify that template due to I don't know the unprotect password. Hence, I make a similar one, and add some features useful to me. My simple Excel gantt chart template can be downloaded from Here (<-- download link is here~! at Google Code)

Note: If you have any modifications & suggestions, please contribute to this project, and make it better and better.


"Shared library" + "C++" + "static" is evil

Shared library 在 Microsoft windows 上通常是以 .dll 作為檔名結尾,而在 UNIX like 系統上則是以 .so 作為結束。為什麼會有這麼大的差異呢?這是因為 shared library 並沒有一個跨 OS 的 standard 可以遵循,所以在撰寫 C/C++ 程式時就會碰到很多麻煩。

基本上,只要使用到 shared library,這個程式就不 portable 了。所有用來處理 shared library 的機制都不 portable。 Windows 有他自己的一套,UNIX 有它自己的另一套。當 C++ 程式裡面使用到 static 時更是嚴重,如果再加上 template 的話,那基本上就很難去切割的很模組化了。

舉例來說,下面是 dll 的 .h 檔:



再來看 exe 的 .c 檔:



為求完整,附上 dll 的 .c 檔:



這樣子經過 Visual C++ 2008 express edition 編譯後,執行時會發現在 .exe 跟 .dll 內部都會存在一份 static member 的 memory space。所以執行後的結果會得到 .exe 跟 .dll 看到的是不一樣的值:



這是因為在 Visual C++ 中的 default 設定是 .exe 或 .dll 內的 symbol 都不會被 export 出去,如果沒有特別設定的話,都預設是專屬於該 .exe 或 .dll 內部的,也就是說外面是看不到的。所以如果外面也要能夠存取到的話,那麼 Visual C++ 提供一個 keyword,也就是 __declspec(dllimport) 跟 __declspec(dllexport),可以做到這件事情。透過這兩個 keyword 的使用,就可以讓 .exe 檔也能存取 .dll 內的 static member,而不會產生不一致的現象了。所以新的 .dll 的 .h 檔會像是如下所示:





我在 mingw gcc 4.2.3 上做試驗,也得到一樣的結果,一定要加上 __declspec(dllimport) 以及 __declspec(dllexport) 這樣的關鍵字才有用。

我沒有在 linux 版上的 gcc 做試驗,不過我記得 gcc 的 default 行為是 export module 內所有…

Open source 的 scene graph library 的選擇

3D scene graph 在很多地方都見得到,例如 Java 的 JSR-184 (a.k.a m3g),3D studio max 裡面也有自己的一套 (要用 3dsmax sdk 或更高一層的 3DXI 才存取得到)。談到 open source 的 3D scene graph library,常見到的幾乎就是下列三套:
Open Scene GraphOpenSGCoin3D其中的 Coin3D 是 GPL license,所以如果你的 project 不是 GPL license, 那麼就不用考慮他了。OpenSG 採用的是 LGPL,而 Open Scene Graph 採用的也是類似 LGPL,但卻是更寬鬆的 license,他容許 static linking 以及直接 embedded 到 application 中。所以就 license 而言,Open Scene Graph 是最有彈性的。

另外就使用者及社群的活躍性而言,以這個網頁的資料來看,Open Scene Graph 不論是在使用者以及社群活躍度上,都比另外兩個 project 來的蓬勃。OpenSG 次之,Coin3D 敬陪末座。

在架構上,Open Scene Graph 跟 OpenSG 類似,都是採用 Application-driven 的方式,也就是在 application 的執行期間內,會一直不斷的進行 render 的動作,所以適合用在遊戲以及模擬類的程式中 (比方說飛行模擬)。而 Coin3D 只會在 scene 的內容有變的時候,才會 render,比方說 view point 改變等等。

Coin3D 是基於 SGI 的 OpenInventor 這套 API 而來,所以他跟 OpenInventor 是 API 相容的。雖然他跟 SGI 的 OpenInventor 相容,但也加入了不少自己的一些 extension。而且 SGI OpenInventor 上次的 source release 是在 2003 年,跟一直在進行更新的 Coin3D 相比,似乎活躍度差了那麼一點。

另外,就網路上查到的資料,同樣的一個 3D scene,用這三套 library 來撰寫,結果似乎以 OpenSG 撰寫所得到的 performance 最好,Open Scene Gr…

C 語言中如何保護跨檔案的 exported symbol

有時候我們想把一個 module 分成好幾個 source/header 檔案, 因為這樣比較好管理, 也比較好看, 每個檔案也比較小, refactoring (re-compile) 的時間也比較短. 不過這樣的缺點是, 勢必有若干個原本是在一個 .c 檔裡的 static global variable 或 static function 會變成 global 的 variable 或 function. 這會增加別的 module (programmer) 誤用的風險, 在此提供一個保護這些你不願意讓其他 module 使用, 但卻可以在自己數個 .c 檔裡共用 variable (或 function) 的方法.

其實方法很簡單, 就是在 C 裡面借用 C++ 的 name mangling.

例如有一個 module A. 我用下面的 macro 來替每個希望只能用在 module 內部的 global variable (或 function) 加上一段文字:



在這邊用 "__this_(data | function)_should_not_be_(accessed | called)_outside_module_A" 這個字串來讓其他 programmer 很清楚的知道他不應該呼叫或存取這個 data (或 function), 但我又擔心這樣的防護還是不夠, 所以又加了一個 compiler predefined 的 macro, _INTEGRAL_MAX_BITS, 來增加使用的難度. 這個 _INTEGRAL_MAX_BITS 是由 Microsoft Visual C/C++ compiler 所定義的, 有可能會隨著不同版本的 VC++ 而不同, 也很有可能其他家的 compiler 不支援, 比方說 gcc, ARM CC 等等. 基本上, 這個 compiler predefined 的 macro 是看你所用的 compiler 而自由定義的.

=============================================================
註:

在一般的 VC 2005 使用上, _INTEGRAL_MAX_BITS 會被展開成為 32 這個數字.
====================…

BSD 與 Embedded BSD簡介

在類 Unix 系統的家族中,目前最為人所知的大概就算是 Linux 系統了。然而,還有另一支跟 Linux 系統很像,但又有點不太一樣的類 Unix 系統叫做 BSD 系統,也常被拿來使用。最近一個蠻有名的例子是 Apple 公司的 Mac OS X 作業系統,其底層所用的 Darwin 核心就是拿FreeBSD 的核心來做修改而來的。 BSD 系統的歷史一開始的時候,加州大學柏客萊分校的電腦科學研究團隊 (CSRG,Computer Systems Research Group) 對貝爾實驗室 (Bell Labs) 所開發的 Unix 系統不太滿意,因此自行對它做了一些修改。後來越改越多,漸漸的跟原本 Bell Labs 的 Unix 系統越來越不一樣,因此後來這個由 CSRG 所開發的類 Unix 系統另外又稱做是 BSD (Berkeley Software Distribution) 系統。

後來 CSRG 解散了,原本他們所維護的 BSD 系統程式碼被 386BSD 計畫拿去移植並使用在 Intel 的 i386 系統上。過了幾年,這個 386BSD 計畫也終止了,但他們所維護的 386BSD 程式碼被 FreeBSD 跟 NetBSD 這兩個計畫拿去繼續發展。稍後由於 NetBSD 內部的意見分歧,有些人就從 NetBSD 內部獨立出來成立另一個 OpenBSD 計畫。 主流的 BSD 系統 因此目前主流的 BSD 系統大致有下列三種:

FreeBSD
http://www.freebsd.org/


圖:用來代表 FreeBSD 的小惡魔

原本專注於 i386 平台上的開發,後來也慢慢的加入了對 Alpha,Sparc 等其他平台的支援。FreeBSD 最主要的目標是成為Intel/AMD 平台上一個穩定並且經過最佳化後的 BSD 系統。

NetBSD
http://www.netbsd.org/

(按一下放大)
圖:舊的 NetBSD 圖示

立志要成為一個能夠在最多平台上運行的作業系統,到目前為止 NetBSD 可以在 50 多個硬體平台上執行,例如 Macintosh,Atari ST,Amiga,Intel,Playstation2,Sega Dreamcast 等等。時到今日,NetBSD 最主要的成就在於其高度的可移植性,以及成為學術上的研究目標。 很…

Embedded Linux簡介

在近幾年的電腦發展趨勢裡面,Linux已經從伺服器或桌上型市場跨足到嵌入式(embedded)的環境。而這些所謂的嵌入式裝置,在大部分的情況下, 其運算能力及可用資源都沒有伺服器以及桌上電腦那麼的強大。然而,Linux在最近幾年的發展及進步,已經可以讓它勝任某部份嵌入式系統所應用的範圍。因 此在本文內,筆者將簡單的介紹嵌入式Linux,包括它的發展現況以及開發流程。 嵌入式Linux簡介對於嵌入式Linux(Embedded Linux)的定義,各家說法或有不同。簡單來說,只要不是在個人電腦或伺服器上面運作的Linux,就是所謂的是嵌入式Linux。所謂的「嵌入式」, 說穿了就是將精簡過的Linux系統寫入至Flash Rom,而日後可以藉由刷新韌體,來做功能的增加及系統的修補。而嵌入式Linux的應用其實相當廣泛,大到伺服器,小到家電,都可以看到嵌入式 Linux的影子。 只要硬體本身不故障的情況下,機器本身所內嵌的Linux,是不會遭受到任何的毀損,因此不需費心去考慮「重灌」的問題。 目前在embedded linux界有數家廠商合作起來成立一個名叫CELF的組織,透過這個組織來推動linux在家電市場的應用。


圖:CELF是一個將焦點放在如何使linux應用於消費性電子產品上面的組織(取自CELF網站) 常見的核心版本 而在嵌入式Linux的執行環境中,核心佔了相當重要的地位。一般而言,常見的Embedded Linux核心版本大概有下列數種: 由Linux之父:Linus Torvalds所維護的「正宗Linux 核心版本」。知名的MontaVista公司所修改的版本。專門使用在便宜且不具備記憶體管理單元(Memory-Management Unit,MMU)硬體的uCLinux。專門應用在即時(Real-Time)系統中的RTAI以及RTLinux(RTLinux/Pro)。 當然以Linux「Open Source」的特性,說不定在網路上還有其他可供用來開發嵌入式Linux的核心,如果有興趣的話,可以去網路上找找,說不定還有意想不到的發現。 C語言函式庫的支援 除了核心之外,嵌入式Linux系統還需要很多其他的軟體元件,這些元件包括了標準的C語言函式庫。雖然GNU有發展過一套C語言函式庫可供開發時使用,但這套函式庫對嵌入式環境來說還是過於肥大,…

MIDP 的使用方向

目前國內在使用 J2ME 的 MIDP 套件上, 主要分成三類: 撰寫 midlet:

所謂的 midlet 就是專門在 MIDP 這個環境中所執行的 Java 程式. 這也就是說, 如果你是這一類的 programmer 的話, 你所需要具備的技能將會是 Java 程式的撰寫能力, 以及 midlet programming 的相關知識. 由於當初 MIDP 在設計的時候, 就是要使用在那些系統資源比較差的小型裝置上, 因此你所撰寫出來的 midlet 程式也將會受到一些限制, 包括你必須要遵循著某種固定的格式來撰寫你的 midlet. 基本上, 撰寫 midlet 跟撰寫一般的 Java 程式一樣, 一點都不難, 你只需要看個文件, 花點時間, 搞懂撰寫 midlet 的方法後, 就可以開始撰寫你自己的 midlet 了.
增加特定功能的 class 模組:

由於 Sun 的 R.I 只提供了基本的 class 模組, 例如 java.lang.Integer, java.lang.Object, java.io.DataInput 等等類別, 以及一些專屬於 J2ME 領域內的 javax.microedition.io.Datagram, javax.microedition.io.Connection 等等類別. 但是由於廠商想要創造出一些與其他品牌不同的特點, 因此通常都會自行增加一些額外的功能, 比方說振動, 閃光等等, 而在這些額外的功能之中, 有不少已經標準化了, 比方說 MMAPI (Mobile Media API) 這個提供多媒體功能的額外類別模組.
移植到新的 GUI 系統上:

J2ME 最主要的使用範圍是在小型的嵌入式系統 (embedded system) 中, 而在這些所謂的小型裝置上, 很難找到一個統一的圖形使用者介面 (GUI), 因此, 當廠商拿到 Sun 的 R.I. 之後, 通常第一件要作的事情便是把 Sun 的 R.I. 給移植到該廠商所使用的 GUI 系統上. 而目前常見的 Embedded GUI 包括了 Embedded Qt, MiniGUI, 以及 Microwindows 等等.

在進行 GUI 層面的移植時, 所需要修改的部份有下列數項:

Soft button 的模擬.

MIDP 的執行環境中, 有兩顆專門叫做 So…

CLDC 的使用方向

你可以把 CLDC 切割為兩大塊, 這兩大塊的關係分別是 "上與下" 的關係. 位於下層的是一個小型的 Java 虛擬機器 (Java Virtual Machine), 名字叫做 KVM. 而位於上層的則是一些 Java 環境中最基本的 class 模組. 而目前在國內提到有關 CLDC 的使用時, 不外乎可以區分為下面幾大類: 修改 KVM:

Ok, 在討論這一項之前, 我先描述一個名詞, 這個名詞叫做 R.I, 它的全名叫做 Reference Implementation. Ok, 那麼甚麼叫做 Reference Implementation 呢? 基本上, 你可以想像一個情景, 有一本專門用來規範 KVM 架構的書, 而這本書就叫做 Reference. 而依照這本規格書中所定義的內容所撰寫出來的程式碼, 就叫做 Reference Implementation.

而 Sun 這家公司呢, 有撰寫它自己的 Reference Implementation, 而其中的某個版本便可以從 Sun 的網站 (http://wwws.sun.com/software/communitysource/j2me/cldc/download.html) 下載回來使用. 不過想當然爾, 能夠讓你下載的原始碼, 並沒有非常認真的考慮到程式撰寫的最佳化, 以及執行時期的效率等等議題.

但也就是因為 Sun 有釋放出一個版本的 KVM R.I., 因此目前大多數廠商在 CLDC 上所作的使用就是去 Sun 的網站下載原始碼, 然後回來作一些修改. 基本上, 目前大部份的修改不外乎屬於下面幾類:

移植到其他的作業系統:

由於 Sun 的 R.I. 是以 UNIX 或 Mircosoft Windows 為預設的作業系統所撰寫出來的, 因此, 假如說今天你所要跑得作業系統跟這兩者差很多的話, 那你就得作出相對應的修改. 比方說, 在某些情況下, 你得在 Nucleus (http://www.acceleratedtechnology.com/) 這個作業系統上執行 KVM, 那麼你就必須要針對 Nucleus 的特性來在 KVM 裡面作修改.

通常這些修改包括了下列數項:

Big-endian 以及 little-endian 的選擇.
64-bit 整數型態的加減乘除:

如…