July 04, 2008
不再囉唆：NetBSD 簡化 BSD 授權條款
儘管絕大多數的開發者都知曉 BSD 授權條款較為寬鬆，沒有 GNU GPL 本質上 "copyleft" 的「病毒式」感染性，但實務應用仍有值得推敲之處。NetBSD 基金會近日甚至宣佈，進一步簡化其使用多年的 BSD 授權條款，相較於繁瑣的 GNU GPLv3，NetBSD 此舉可說追趕 FreeBSD 與 OpenBSD，樹立 BSD 授權的「自由派」訴求。BSD License 為 "Berkeley Software Distribution license" 的縮寫，顧名思義，源於加州柏克萊大學的 BSD 一系列的軟體，最早的著作權人為 Regents of the University of California'（加州大學董事會)，BSD 授權條款本身相當清楚，最初的版本有四個條款，也就是規範被授權人的條件限制，如下：
- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
- Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
- All advertising materials mentioning features or use of this software must display the following acknowledgement: This product includes software developed by the University of California, Berkeley and its contributors.
- Neither the name of the University nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
- 規範以原始程式碼形式的再散播，需保有同樣的授權聲明
- 要求二進位可執行形式的再散播，需在檔案或所屬的媒介中，附上授權、免責條款等資訊
- 軟體本身應提供如廣告般的機制，附帶提及告知研發軟體的加州大學
- 未獲得許可前，禁止以原作者或加州大學之名，行衍生軟體之背書、推廣、促銷等行為
隨著 BSD 的成熟，人們意識到摻雜 AT&T UNIX 的程式碼，意味著高價的授權 (AT&T License) 與使用上的限制，沒辦法透過當時開始發展的網路作廣泛的散播，是此，在許多貢獻者的投入下，1989 年六月，Networking Release 1 (Net/1) 誕生了，不需 AT&T 授權也使用，當時一個劃時代的變革就是將上述四個條款的 BSD 授權聲明含入，只要在這個新的遊戲規則下，都可自由再發佈。而我們也可從這原始的四項被授權人的條件限制中，看出對於原始程式與二進位執行檔的散播形式 (需保有授權與免責聲明)、於程式本體提及 Net/1 研發背後的加州大學、禁止以貢獻者或加州大學之名，行衍生軟體之背書、推廣、促銷等行為，意思就是為這嶄新的系統，制定得以自由使用的規則。而到了 1991 年六月，Net/2 已幾近全新的作業系統，不含 AT&T 的程式碼，而 Net/2 在 Intel 80386 硬體架構的移植，由 William Jolitz 負責下進行，也被稱為 386BSD，後來，由握有 System V 版權、Unix 商標的 UNIX Systems Laboratories (USL，為 AT&T 附屬子公司) 對 Net/2 在 80386 硬體的封閉專屬 BSD/OS 背後研發的 Berkeley Software Design (BSDi) 公司，提出法律訴訟，延宕了多年，直到 1994 年一月份才落幕，並引來 BSD 原始程式碼重整的動作，顯然，對系出同門的 386BSD 來說，不免也受到影響，而無法在法律爭端休止前，作自由的開發與使用。
也因此，386BSD 無疑是短命的作業系統，但卻奠定 NetBSD 與 FreeBSD 的基礎，同時，這兩個專案也繼承 BSD 授權條款，作為發行的規則，而，BSD 授權也因其簡單明確，帶來廣泛的成功，許多非加州大學開發的軟體也紛紛採用這個授權，將著作歸屬人的加州大學，改為自己從屬的單位，就透過網路或等價媒介作廣泛散播。不過，GNU/FSF 發現 BSD 授權的問題，導致無法與 GNU GPL 保持相容，從而將原本四個條款的 BSD 授權之中的一項，稱為 [obnoxious BSD advertising clause]，也就是上述的第三條：
-
"All advertising materials mentioning features or use of this software must display the following acknowledgement: This product includes software developed by the University of California, Berkeley and its contributors."
在 2008 年六月上旬，我們可看到自由的 BSD 家族，採用的 BSD 授權條款如下：
- NetBSD 仍使用原始的 BSD 授權條款 (4-clause)
- FreeBSD 使用兩句版授權條款 (2-clause)，另行於末尾添加非 FreeBSD 基金會的貢獻者列表
- DragonFlyBSD 使用 3-clause/new- BSD 授權條款，與 FreeBSD 4 分家前同
- OpenBSD 對所有添加的軟體，採用 Internet Systems Consortium, Inc 的版權條款，就其功能 來說，也就是 2-clause BSD 授權
-
"Neither the name of the University nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission."
- we have seen organisations and people concerned about the old clause 3 (the advertising clause) in the license, to the extent where NetBSD code could not be used in commercial products; the new license means that these concerns are no longer valid
- UCB moved some time ago to remove clause 3 from the code contributed to UCB; this change mirrors that one
- we have seen some instances where clause 3 was ignored by groups and organisations
- the members of the NetBSD Foundation (i.e. its developers) no longer considered clause 4 (the "endorsement" clause) to be useful in today's software world
大環境來看，現在 copyleft 的代表為 GNU GPLv3，而自由派 (也稱為 copycenter) 的代表幾乎就是 2-clause BSD license，兩者的分野就更鮮明了。另外，[hubertf] 提到 GPL 與 BSDL 改版的字數比較圖，頗有意思：
GNU GPL 就好像法律條文，冗長令人生懼，但捍衛自由，又不得不如此；BSD License 則像女人的迷你裙，越短越受歡迎。
Posted by jserv at 11:53 AM
| Comments (1)
July 03, 2008
取得 GNU/Linux 行程的執行檔路徑
本文試著探討 GNU/Linux 於執行時期 (run-time) 的行程 (Process) 如何取得執行檔路徑，並探討 /proc/self/exe 的機制與其應用。進入主題前，我們該來思考本文標題：
-
「取得 Linux 行程的執行檔路徑，有什麼好處？在什麼場合需要？」
由於該文年代久遠 (注意：筆者認為現在將 Floppy Linux 當作嵌入式系統的實習對象，已不合時宜，畢竟軟硬體進步與需求的幅度變動極大，實在沒必要削足適履，故，該文不予更新，但歡迎在原本的基礎上再行擴充，比方說打造 Disk-On-Chip/Linux 的新主題)，busybox 早已經過多次翻修 (當時用 0.6.x 版本，而且贊助此專案的 Lineo 公司也早遭收購)，對應的程式碼也經過大幅改寫，所以本文順便更新前文描述的實做部份。busybox 將可重複使用的部份拆到名為 libbb (bb 即 busybox 簡稱，乃為該專案的程式碼命名慣例)，其中包含解析 argv[0]，以下列出 main() 函式的實做，位於 busybox 1.7+ 原始程式碼的 libbb/appletlib.c 檔案中，簡化的列表如下：(本文的程式碼列表皆為簡化版本)
int main(int argc ATTRIBUTE_UNUSED, char **argv) { applet_name = argv[0]; if (applet_name[0] == '-') applet_name++; applet_name = bb_basename(applet_name); parse_config_file(); /* ...maybe, if FEATURE_SUID_CONFIG */ run_applet_and_exit(applet_name, argv); /*bb_error_msg_and_die("applet not found"); - sucks in printf */ full_write2_str(applet_name); full_write2_str(": applet not found\n"); xfunc_die(); }很顯然，周遊於自訂的函式中，這行 "run_applet_and_exit(applet_name, argv)" 讓我們感到興趣，這就攸關 busybox 的原理，所以咱們看看此函式如何將 argv[0] 作處置，在同一檔案的實做碼如下：
void FAST_FUNC run_applet_and_exit(const char *name, char **argv) { int applet = find_applet_by_name(name); if (applet >= 0) run_applet_no_and_exit(applet, argv); if (!strncmp(name, "busybox", 7)) exit(busybox_main(argv)); }所以重點就是 find_applet_by_name() 函式，顧名思義，就是解析的動作，繼續看實做碼：
int FAST_FUNC find_applet_by_name(const char *name) { /* Do a binary search to find the applet entry given the name. */ const char *p; p = bsearch(name, applet_names, ARRAY_SIZE(applet_main), 1, applet_name_compare); if (!p) return -1; return p - applet_names; }看到這裡，其實就不必再追下去了，都使出標準函式庫的 binary search 函式，顯然就是從內建的 applet 列表中比對，抓出合適的 applet 實做的索引值，內部勢必有對應的執行機制。所以，以 "ls" 來說，在 busybox 的設計中，無論我們在 shell 下執行 "../bin/ls"、"/bin/ls"、"./ls" 等等，只要能在檔案系統中找到 symbolic link 的 "ls" symbol name 與 busybox 執行檔主體，當執行時，argv[0] 就被賦予絕對或相對路徑的字串，busybox 程式透過以上機制，解析名稱，找到 (精簡的) ls applet 實做並將參數代入執行，而，「取得執行時期的執行檔路徑」對於實做 shell 本身，如 ash, msh 來說，就相當重要，因為在 shell (當然，也是由 busybox 提供實做) 下執行程式，其實就是做了 fork()/vfork() 一類的系統呼叫。
實際上，基於安全性考量、程式碼重用性，busybox 內部實做變得更為複雜，讓我們不禁得想想，argv[0] 的應用有哪些限制？看看 argv[0] 可能的內容會有：
- 絕對路徑：基本上只要去除多餘的字串表示，如 "//"，即可使用
- 相對路徑：需要配合目前執行程式的路徑，在檔案系統中，找出最終的絕對路徑
- 只有程式名稱、沒有路徑：因為 shell 透過 $PATH 環境變數找到程式，但 argv[0] 接收時僅有名稱，這時候，得循序依 $PATH 字串內容，逐一於檔案系統中找到程式的絕對路徑
- 其他：當透過 exec 系列的系統呼叫時，什麼名稱都有可能，端視呼叫的形式，這時候就得找出方法 (沒有一定準則)
# ls -l /proc/1/exe lrwxrwxrwx 1 root root 0 2008-07-03 22:10 /proc/1/exe -> /sbin/init當然，目錄 /proc/1/ 底下有很多檔案可探索，筆者就不詳述了，只要知曉 Linux /proc 如此的設計即可。再者，當一個執行中的行程存取目錄 /proc/self/ 時，其效力等同於 /proc/目前行程的 pid/，這也就是說，"/proc/self/exe" 就是對應到「目前行程對應的執行檔」。看來 /proc/self/exe 似乎可解決前述議題，但注意，這僅適用於應用程式本身，不包含其動態函式庫，對於後者，一個普遍的作法是，查閱 /proc/self/maps 的內容，即可依據位址找尋對應的函式庫名稱，或者，透過 GNU/Linux 專有的 DL_info + dladdr 組合，可取得 DL_info::dli_fname 的值，即可指出到底位於動態函式庫或應用程式主體，熟悉 Win32 API 的朋友，大概就會想到等效的 GetModuleFileName()。
在 UNIX 家族中，也提供對應於 GNU/Linux 的 /proc/self/exe 機制，FreeBSD 上是 "/proc/curproc/file"，Solaris 是 "/proc/self/auxv"。咱們來作個小實驗，看看「自我重複執行的行程」會怎麼設計與呈現，以下是簡單的測試程式 (fork-self.c)
#include <sys/types.h> #include <unistd.h> #define MSG_1 "child ends.\n" #define MSG_2 "parent about to fork self.\n" extern char **environ; int main(int argc, char *argv[]) { char *fn[] = { "/proc/self/exe", 0 }; pid_t pid = fork(); if (0 == pid) { write(1, MSG_1, sizeof(MSG_1)); } else if (-1 == pid) { /* unable to fork */ _exit(-1); } else { write(1, MSG_2, sizeof(MSG_2)); execve(*fn, fn, environ); } return 0; }上述程式碼列表有若干重點，如下：
- "/proc/self/exe" 與 exec 函式的搭配
- fork() 後，我們試著 exec "/proc/self/exe"，也就是本行程對應的執行檔名，以取代 parent process
- 由於重複該動作，fork() 可能會失敗，務必作確認與例外情況處理 (_exit)
$ gcc -o fork-self fork-self.c $ ./fork-self child ends. parent about to fork self. child ends. parent about to fork self. child ends. parent about to fork self. ... (重複) ...這過程中，若打開 top 或 htop 一類的工具查看記憶體，會發現可用的記憶體很快會被消耗，不過別擔心，最後失敗就作 _exit 以離開。在未結束前，用 pstree 觀察看看 fork-self 的呈現：
init-+-NetworkManager---{NetworkManager}
|-NetworkManagerD
|-acpid
...
|-rxvt-unicode--bash---exe-+-11599*[exe]
| `-fork-self
...
前述論及 argv[0] 在 exec 系列系統呼叫的限制即在此，上述 pid 是會跳動的，而名稱又貌似一致，不過，Linux 內部會有機制將 /proc/self/exe 找出，是此，取得 GNU/Linux 行程的執行檔路徑，大致如此。不過，我們還是會有疑惑，既然 argv[0] 的限制這麼多、處理複雜又可能不正確，那為何 busybox 經歷多次改版，為何還保留 argv[0] 複雜的處理呢？要注意的是，busybox 可在許多不同硬體的 GNU/Linux 上運作，包含沒有 MMU 的平台，也就是 ucLinux，而，後者 (預設) 沒有 /proc/self/exe 的機制，所以，一般的作法，就是寫死執行檔路徑，當然，這樣的嵌入式系統設計就得相當小心。Posted by jserv at 10:53 PM
| Comments (8)
July 01, 2008
推薦「E-GI建築師事務所實習報告」
最近，放了從求學、職場生涯以來，最長的一次休假。這整整半年的時間內，試著去接觸不同層面的人事物，認識了 egi、閱讀了她豐富的 [E-GI建築師事務所實習報告]，從旁探訪她的內心世界，謹此推薦給各位朋友。有個頗有成就的舅舅任教於台大土木系，小時曾多次耳聞他參與北二高設計與整體規劃的花絮，當時每回都聽得很入迷，但或許覺得自己比較適合敲鍵盤，而不是碰尺規，所以選擇資訊系就讀。大學時代，曾與一位多才多藝且出眾的建築系女生交往，自此交融著對於建築設計的愛好，去建築系館約會時，往往則在這古色古香的建築與多元的設計呈現所傾倒。
事實上，軟體業界的 Architect 這個名詞就是從建築業界借用來的，整個軟體工程的目標更可說是建築設計的抽象呈現：軟體開發如同建築設計，過程中，得針對整體需求、分析、設計、實作、佈署等各項工作流程之不同觀點予以呈現，也就是軟體系統之「塑模」(modeling)。至今，我還記得當時在成大附近的住所，翻閱她帶來 Christopher Alexander 在 1970 年代的大作《A Pattern Language: Town, Building,. Construction》，予我極大的共鳴。
但建築不全然是工程，當談及建築，不免會聯想到「空間感」一詞，是為人們的精神世界鋪就的一條通向終極的理想道路，駐足於此，心境頓時得到永恆的寧靜與祥和，好似，一門之隔卻的有兩個世界。也因此，建築設計是人們內心世界的體驗、感情的記錄，予以具象呈現，偶然在 funP 上瞥見 egi 的文章，按圖索驥尋出其文章的脈絡，不乏詼諧的趣事、情感的轉折與猶豫徘徊，而隱約有著設計人一貫的執著與敏感，或許不顯現於圖文，但存於斯。
從舅舅與前女友身上，大概知曉建築業的生活方式，所以對 egi 的文章偶投以會心一笑與祝福，畢竟這個行業是如此嚴肅又切近我們的生活。其中，最有感觸的文章大概是 [ 230公里的風景] 一文，標題取自於台南到雲林麥寮、花費四個多小時的 230 公里路程。人生際遇往往可用煽情的字句，去誇飾情緒的波瀾壯闊，一如被連續劇養成的感官表現，但平凡中見真情，生命的可貴因此美麗，也因而厚實，我想，egi 的文字就屬於後者，再搭配獨特的圖片更具張力。[ 230公里的風景] 一文取鏡頗耐人尋味，營造出遠離塵囂、反璞歸真之感，又適時以「無政府狀態的張貼模式」凸顯文化與自然環境的對比。很喜歡「波光嶙峋，恰是閑美」前後幾張圖，或許讀者可得以如南台灣普照的陽光一般。
egi 的 [自我介紹] 大概說明了一切：
-
喜歡畫畫，但是不是藝術家。
喜歡發呆，但是腦袋總塞爆想法。
喜歡，一切。
Posted by jserv at 06:18 PM
| Comments (1)
觀察 Linux 的虛擬記憶體
延續 [尋幽訪勝話系統--以 Linux 探索軟硬體整合設計] 的演講，要觀察 GNU/Linux 運作時期的虛擬記憶體 (Virtaul Memory，以下簡稱 vm)，其實沒有想像中的難。首先，可透過 vmstat 工具程式，執行方式如下：$ vmstat -S m procs -----------memory---------- ---swap-- -----io---- -system-- ----cpu---- r b swpd free buff cache si so bi bo in cs us sy id wa 1 0 0 81 110 895 0 0 11 36 160 161 62 17 21 1可列印 vm 的切割與狀態資訊。在 Linux 2.4 轉變到 2.6 的過程中，vm 經過很大的調整，cache 的設計也因此導致不同的表現，在上述 vmstat 的輸出可看到 "cache" 一欄的值，可透過 htop 工具程式作即時顯示系統的變化。不過，就算不安裝外部的工具程式，其實也有「窮人記憶體觀察工具」，那就是 /proc/meminfo ，可搭配 watch 使用：
$ watch cat /proc/meminfo顯示的效果如下圖：
每兩秒在終端機上更新一次，可清楚看到 vm 內各種類別的消長。
在 Linux 2.6.16 以後，引入 drop caches 的機制，所以咱們來看看 cache 的變化，如下圖：
htop 的視窗中，黃色部份就是 cache，當 /proc/sys/vm/drop_caches 的值被設定為 1 時，表示要求核心捨棄沒在使用的 cache (一般的)，而被設定為 2 時則要求將 dentry, inode 所用的 cache memory 一併釋放，而設定為 3 時，就是 (1) + (2) 的效果，也就是幾乎把非作用的 cache 都釋放了。所以，在上圖中，很明顯可見，原本運作中的 GNU/Linux 的 vm 配置了可觀的 cache，在要求釋放後，就幾乎都清空。
Posted by jserv at 04:03 PM
| Comments (0)
httping : 針對 HTTP Request 的仿 ping 程式
[httping] 這個程式非常有意思，能夠以類似 ping 工具程式的方式，將 HTTP Request 的回應情況，呈現給操作者，簡介如下：-
Give it an url, and it'll show you how long it takes to connect, send a request and retrieve the reply (only the headers). Be aware that the transmission across the network also takes time!
$ httping -g http://www.google.com -c 5 PING www.google.com:80 (http://www.google.com): connected to www.google.com:80, seq=0 time=641.30 ms connected to www.google.com:80, seq=1 time=672.34 ms connected to www.google.com:80, seq=2 time=692.74 ms connected to www.google.com:80, seq=3 time=660.11 ms connected to www.google.com:80, seq=4 time=654.99 ms --- http://www.google.com ping statistics --- 5 connects, 5 ok, 0.00% failed round-trip min/avg/max = 641.3/664.3/692.7 ms由上可見，對著 Google 的某幾台機器的 port 80 作 HTTP request，並等待 header 的回應情況，我們可比對 ping 工具程式的輸出：
$ ping www.google.com -c 5 PING www.l.google.com (74.125.19.104) 56(84) bytes of data. 64 bytes from cf-in-f104.google.com (74.125.19.104): icmp_seq=1 ttl=241 time=258 ms 64 bytes from cf-in-f104.google.com (74.125.19.104): icmp_seq=2 ttl=241 time=258 ms 64 bytes from cf-in-f104.google.com (74.125.19.104): icmp_seq=3 ttl=241 time=257 ms 64 bytes from cf-in-f104.google.com (74.125.19.104): icmp_seq=4 ttl=241 time=257 ms --- www.l.google.com ping statistics --- 5 packets transmitted, 4 received, 20% packet loss, time 4019ms rtt min/avg/max/mdev = 257.860/258.053/258.395/0.656 ms另外，[httping] 支援 https (使用 OpenSSL 函式庫)，也可以要求只做一次 DNS resolve，對於 roundrobin DNS 的環境來說很重要。
Posted by jserv at 11:11 AM
| Comments (1)
演講：快快樂樂學 GNU Debugger (gdb) Part I + II [台中]
幾個月前，在台南舉辦演講：快快樂樂學 GNU Debugger (gdb) [Part I] 與 [Part II]，現在也有台中的場次，詳情可見酷！學園的 [討論區]，摘錄如下：- 簡介：期望使聽者得以透過 GNU Debugger (gdb) 來加速系統開發與分析，讓這個臥在硬碟深處許久的強力程式，激發其威力。本議程捨棄過往教條式的介紹形式，延續「深入淺出 HelloWorld」系列的「作中學」途徑逐一探討使用情境與案例分析
- 議程主題：
- Why - 為何我們該善用 Debugger？
- Who - 誰會因為熟悉 Debugger 而受益？
- What - 史上最強大的 Debugger -- gdb 與一系列系統軟體
- Where - 利用 Debugger 的場合
- How - 還用說嗎？來就對了！
- 涵蓋項目：
- 實用 GDB 指令
- macro 與技巧
- 當 GDB 遇上 C/C++：具體的範例
- 參考資訊：
- 簡報與範例檔案： http://jserv.sayya.org/debugger/
- GNU Debugger: http://sourceware.org/gdb/
- 時間：七月 12 日 10:00-12:00 (Part I), 13:30-17:00 (Part II)
- 地點：亞洲大學 (台中縣霧峰鄉柳豐路500號) 管理大樓 B1 M009 教室
- 費用： 0 –
- 人數限制：無限制
- 報名網站：http://registrano.com/events/sataichung080712
- 交通： 自行開車； 搭乘客運或公車至台中火車站--前站（建國路）對面搭乘100號公車往省諮議會方向--最後一站 亞洲大學
Posted by jserv at 10:05 AM
| Comments (0)
June 30, 2008
追憶似水年華
-
眾鳥高飛盡，孤雲獨去閑
相看兩不厭，只有敬亭山
因為我們兩個小鬼都在六月份出生 (11 日與 30 日)，所以雙親乾脆就買一份蛋糕，同時為我們慶生，照片是在苗栗老家的客廳中，兄妹滿心期待地望著生日蛋糕，妹妹當時 3 歲，如紅色蠟燭所示，而右邊的蠟燭是青的，表示我的年紀滿 3 + 1 歲，這大概是少數我們充滿歡笑的合影。妹妹的乳名叫做「小美」，在客家話裡頭很常見，不過，也可說是七次登臨敬亭山、留下了人山兩不厭的太白式浪漫的展現，她的成長歷程一度是很順利，也聰明討人歡喜，有大量的創作與活動，但這十幾年來，過得很痛苦，自限於象牙塔中，有如中世紀的武士，獨自對抗著難為我們所察的敵人，而身心俱疲。
在年幼時，受到過度保護、與外界隔絕的我，幾乎不知什麼是朋友，與同學的關係僅限於課堂，而妹妹則是唯一的玩伴，只要鑰匙兒童一回家，兄妹倆立刻拉下鐵門簾，要不看電視、玩積木、談天、下棋，就是各自讀書，偶爾，我們一同打水仗、打電腦、拼圖、繪畫等等，那些是兒時美好的記憶，我們很少吵架，感情也很好。過去，妹妹在許多層面的表現一直大幅超越我，諸如功課、繪畫、鋼琴、身高、人緣，而處於身旁的我，就好像是個弟弟。後來發生了許多轉折，在我離鄉背井到台中唸書時發生的連鎖效應，總之，一切變調了，我幾乎無法與人談論妹妹所發生的事情，以及我們家庭的處理態度。
山脈對地球來說，只是短暫的穩定，是沈積與地質運動的產物，對生命短暫如飛絮的我們來說，就跟其他自然景物一般，無所謂雋永與否。但，若見到我們無法接受、或不喜愛的景物，可能牽引而生煩躁的心情，若所見者在我們的主觀感受，覺得它是美好的，生命本身即可能被牽引而進入美好的狀態。詩仙看山就是這樣的心境，產生了心理的變化，並緩緩帶領生命進入另一種難以言喻的變化。換句話說，人心好似一面鏡，當用平淡祥和的心態，去觀察周圍的人或事物時，周圍的人或事物也會用相同的眼光來看待自身。對我來說，看著過去的敬婷，就像詩仙見敬亭山，一幕幕鮮明的意象，仍映入心智想像中，只是逐漸遠去，我們一同生活的美好體驗，及於生活中的每一分、每一秒。
「生日快樂，小美」這句話，我一直不知道該如何再開口，只希望現在有機會能聽進去。眾鳥高飛，孤雲獨去，誰與誰能夠，不離不棄？
Posted by jserv at 01:39 PM
| Comments (5)
June 28, 2008
用 Makefile 實現 quick sort
在大學課程中，quick sort 大概是用來闡述遞迴概念的最佳範例，因為既簡潔又實用。多數的程式語言也可採用此概念，甚至連 GNU make 裡頭 function call 也能遞迴，所以，何不試著實做 quick sort 呢？以下是 proof-of-concept 的試作品：TRUE = 11111 gt = $(shell if [ $1 -gt $2 ] ; then echo $(TRUE); fi) lt = $(shell if [ $1 -lt $2 ] ; then echo $(TRUE); fi) le = $(shell if [ $1 -le $2 ] ; then echo $(TRUE); fi) qsort = \ $(if $(call le,$(words $1),1),$1, \ $(call qsort, \ $(foreach i,$1, \ $(if $(call gt,$(firstword $1),$i), $i,))) \ $(firstword $1) \ $(call qsort, \ $(foreach i,$1, \ $(if $(call lt,$(firstword $1),$i), $i,)))) data = $(shell od -vAn -N10 -w1 -tu1 < /dev/urandom) all: @echo $(call qsort, $(data))$(data) 給定自十個隨機亂數，取於 /dev/urandom，原理是讀入二進位的亂數資料後，透過 od 指令將每一個 byte 轉換成一個無符號整數。當然重點是 "qsort"，我們可看到 Makefile 中的宣告與實做中，遞迴地呼叫自身，也就是 $(call qsort, ...) 的動作，將 "divine and conquer" 的想法予以實現：先分成左右兩半，再來排序。 取得預先準備的 [Makefile.qsort]，執行的情況類似以下輸出：
$ make -f Makefile.qsort 2 20 29 58 88 165 172 230 242 246既然輸入資料取於亂數，所以只要看到遞增數列即可。
Posted by jserv at 07:27 AM
| Comments (5)
June 27, 2008
教育訓練：Gtk+ 程式設計初體驗
過去很榮幸得以在不同的場合，與朋友分享過一些電腦技術主題的演講，下個月則嘗試時間較長的教育訓練，但仍維持免費的分享形式。主題是「Gtk+ 程式設計初體驗」，由 [酷學園] 張羅議程的進行，詳細資訊可參考 [公告]，以下摘錄部份內容：
- 簡介
-
學習 GUI 程式設計，一開始從 "Hello World" 等級程式出發都沒問題，但頗為枯燥，「做中學」的模式較易讓人產生自信。本議程以專案目標導向的形式，探討 [Gtk+] 與相關技術，如：
- 用 Gtk+ 搭配 GStreamer，打造簡易的 media player
- 以 Gtk+ 的延伸 widget set，打造個 text editor
- 透過 Gtk+/WebKit，打造可嵌入到 Gtk+ 應用程式的 Web Browser
- 時間：2008 年 7 月 26 日 (星期六) 10:00 - 17:00
- 時間規劃： 總共 6 小時 (Part I: 10-12, Part II: 13-17)
- 地點：國立臺灣大學進修推廣部-303教室 台北市羅斯福路四段107號 (位於羅斯福路上靠近基隆路口)
- 費用： 0 -
- 地理位置/交通路線: http://training.dpd.ntu.edu.tw/NTU/Portal/ntumap.htm
- 活動報名網址：http://registrano.com/events/sataipei200807
- 注意事項：
- 本議題提供錄影
- 報名時請務必填寫正確 E-Mail，主辦單位會在講者完成課程所需要的程式碼 +摘要電子檔後，將資料寄送給報名者
- 物件導向的思維與實做
- 視窗系統中的事件與其對應的操作處理
- 圖形元件的設計概念與組合、互動形式
- MVC (Model-View-Control) 設計模式的引入
Posted by jserv at 06:11 PM
| Comments (1)
June 25, 2008
探訪 stack frame：談不定數量參數
前文 [以 C 語言實做 Functional Language 的 Currying] 已探討在 IA32 stack 的操作，讓 Currying 的行為得以在此基礎，予以實現，而我們還可看另一種應用：C 語言的不定數量參數，也就是 stdarg.h 裡規範的行為。當我們使用 printf() 函式搭配強大的資料格式化處理 (printf 本身就是個小型的 interpreter) 時，不免會其運作行為感到好奇，以下是 GNU/Linux 上 /usr/include/stdio.h 的 prototype：(取自 glibc)__BEGIN_NAMESPACE_STD ... /* Write formatted output to stdout. This function is a possible cancellation point and therefore not marked with __THROW. */ extern int printf (__const char *__restrict __format, ...);注意到函式參數列裡頭的 "..."，語法上表示不定個數的參數輸入，在實做面則不離 stack 的行為，筆者以一個簡單的小程式，說明其運作原理： (multiply.c)
#include <stdio.h> #include <stdlib.h> static int multiply() { int *bp; int result = 1; /* Start stack traverse */ #if defined(__i386) __asm__( "movl %%ebp, %0" : "=g"(bp)); #elif defined(__x86_64__) __asm__( "movq %%rbp, %0" : "=g"(bp)); #else /* * Caution: this would fail if it points to the end of the saved * registers instead of the start. (gcc bug in 4.1 branch) */ bp = (void **) __builtin_frame_address(0); #endif bp += 2; while (abs(*bp) < 0x1000000) { result *= *bp++; } return result; } int main() { printf("1! = %7d\n", multiply(1)); printf("2! = %7d\n", multiply(1,2)); printf("3! = %7d\n", multiply(1,2,3)); printf("4! = %7d\n", multiply(1,2,3,4)); printf("5! = %7d\n", multiply(1,2,3,4,5)); printf("6! = %7d\n", multiply(1,2,3,4,5,6)); printf("7! = %7d\n", multiply(1,2,3,4,5,6,7)); printf("8! = %7d\n", multiply(1,2,3,4,5,6,7,8)); printf("9! = %7d\n", multiply(1,2,3,4,5,6,7,8,9)); return 0; }先看看 main() 裡頭的函式呼叫方式，數學的 1!, 2!, 3!, .., 9! (階層運算) 定義就是 1, 1*2, 1*2*3, ..., 1*2*3*...*8*9, 這裡用 multiply() 函式實現，又，筆者在前文已大致提及 C 語言的 function call 與 IA32 stack 的執行時期行為對應：%ebp 指向 frame pointer 頂端，function 本體必須在 prologue 處理好 caller/callee 的 frame pointer，而參數的傳遞也是這時該考量的。所以，若我們可取得 stack 中 frame pointer 的內含值，往後推算，不就可取得參數內容嗎？進而，我們可拿這些資料作自行規範的舉動，比方說本範例的乘法運算。
取得 %ebp 的方式可透過 inline assembly，如程式碼列表中 x86 與 x86_64 的動作，或者考慮到不同平台，可援引 GCC 的 GNU Extension : __builtin_frame_address，以下是文件的描述：
-
void *__builtin_frame_address (int level);
This function is similar to __builtin_return_address, but it returns the address of the function frame rather than the return address of the function. Calling __builtin_frame_address with a value of 0 yields the frame address of the current function, a value of 1 yields the frame address of the caller of the current function, and so forth.
The frame is the area on the stack which holds local variables and saved registers. The frame address is normally the address of the first word pushed on to the stack by the function. However, the exact definition depends upon the processor and the calling convention. On the Motorola 68000, if the function has a frame, then __builtin_frame_address will return the value of the frame pointer register a6 if level is 0.
stack frame 就是保存變數與暫存器的區域，通常是此函式被推入 (push) 到 stack 中頂端的位址，不過，確切的行為需要視硬體處理器 (如 x86 vs. RISC) 與呼叫方式 (如 ARM 的 OABI vs. EABI) 而定，不過我們這裡只想取得傳遞給 multiply() 的參數序列，就先不思考這麼多。需要留意的是，在 GNU gcc 4.1 branch 中，__builtin_frame_address(0) 的回傳值「有時」會是錯誤的，所以筆者先使用 inline assembly 處理。筆者先進行位移的動作，以自 %ebp 後方取得參數列表，在不參照參數個數的情況下，筆者用投機的途徑來判斷，因為代入者都是小整數序列，基本上只要確定是否落在合理範圍即可。以下是編譯執行的輸出：
$ gcc -xc multiply.c -O0 && ./a.out 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880由可見依序將 multiply() 後方傳遞的參數取出，將其累乘得階層運算值。注意，我們必須將 gcc optimization 關掉，以避免 gcc 將參數捨棄的狀況，另外，也不能傳遞 gcc 編譯的參數 "-fomit-frame-pointer"，這會導致 %ebp 取得與前述方式不一致而無法正確執行的問題。
另外，在 NetBSD/PowerPC 上， stdarg.h 其實就是使用 __builtin_frame_address 來實做對不定個數參數的處理，參見 /usr/src/sys/arch/powerpc/include/stdarg.h 的相關宣告如下：
#define va_start(ap, last) \ (__builtin_next_arg(last), \ (ap).__stack = __va_stack_args, \ (ap).__base = __va_reg_args, \ (ap).__gpr = __va_first_gpr, \ (ap).__fpr = __va_first_fpr) #define __va_first_gpr (__builtin_args_info(0)) #define __va_first_fpr (__builtin_args_info(1) - 32 - 1) #define __va_stack_args \ ((char *)__builtin_saveregs() + \ (__va_first_gpr >= 8 ? __va_first_gpr - 8 : 0) * sizeof(int)) #define __va_reg_args \ ((char *)__builtin_frame_address(0) + __builtin_args_info(4))不過，NetBSD 與 GNU/Linux 對 gcc 處理的更迭，現已用不同的方式封裝，但原理還是一致的。
Posted by jserv at 01:33 PM
| Comments (0)
June 21, 2008
操作 X 的 Cut and Paste Buffer
在 X Window System 要處理 X client 之間的資料分享，因為設計本質上與傳統 GUI 有極大差異，所以，不可等閒視之，也就是說，在 Win32 下很普通的 Clipboard 處理，搬到 X 下，其實得考慮相當多。Win32 Clipboard 無法「直接」對應到 X Clipboard，我們必須分很多層級去思考，一般的 X client 中，以滑鼠(mouse) / 指標(pointer) 作區域的文字 / 物件選擇動作，在真正貼上或複製到標的視窗前，其實涉及到跨越實體環境的資料分享 (考慮到 X Protocol 分散式處理本質) 的議題，所以，光是如何保存這些中間資訊，就是很大的學問。簡單的文字，可透過名為 X cut buffer 的空間，暫時保存 X cut-paste 過程的內容，但這僅是最基本的操作，一般設計較為複雜的 X Toolkit 如 Gtk+ 或 Qt，其實都援引不同的機制，不過，這不妨礙我們對系統的理解。作為最基本的資料分享機制，X cut and paste buffer 僅是很單純的存取緩衝區的資料，我們可這樣實做簡單的寫入操作，程式如下： (xcutbuf-set.c)
#define _GNU_SOURCE #include <X11/Xlib.h> #include <X11/Xatom.h> #include <stdio.h> #include <string.h> #define BUF_LENGTH 8080 int main(int argc, char* argv[]) { char buf[BUF_LENGTH]; Display *disp = XOpenDisplay(0); fgets(buf, BUF_LENGTH, stdin); XStoreBytes(disp, buf, strnlen(buf, BUF_LENGTH)); while (XGetSelectionOwner(disp, XA_PRIMARY) != None) { XSetSelectionOwner(disp, XA_PRIMARY, None, CurrentTime); } return 0; }這裡用到 XStoreBytes(3) 來對緩衝區作寫入動作，編譯並執行如下：
$ gcc -o xcutbuf-set xcutbuf-set.c -lX11 $ echo -n "Let's Do It" | ./xcutbuf-set自標準輸入取得資料後，就透過 XStoreBytes(3) 寫入 x cut buffer，需要留意的是，我們必須透過 XSetSelectionOwner(3) 來讓現在的 window selection (X 術語，表示指定的「選擇」動作，像是 cut-n-paste 的動作) 生效。在 rxvt 或 rxvt-unicode 下，我們可按下 "Shift" + "Insert" 按鍵組合，會自 X cut buffer 取出已寫入的資料，也就是剛剛那字串："Let's Do It"。透過函式呼叫，可取出裡頭的字串，程式碼如下： (xcutbuf-get.c)
#include <X11/Xlib.h> #include <stdio.h> int main(int argc, char* argv[]) { int count; Display *disp = XOpenDisplay(0); printf("==> %s\n", XFetchBytes(disp, &count)); return 0; }編譯並執行：
$ gcc -o xcutbuf-get xcutbuf-get.c -lX11 $ ./xcutbuf-get ==> Let's Do It以上，咱們邁出認識 X client 間資料交換最簡單的機制：X cut buffer 的操作，未來將會探討 X clipboard 運作的機制。
Posted by jserv at 12:11 AM
| Comments (0)
