軟體學徒forever

原文作者： Eli Bendersky 原文連結： http://eli.thegreenplace.net/2011/11/11/position-independent-code-pic-in-shared-libraries-on-x64/ 前一篇文章 解釋過與位址無關程式碼（position independent code, PIC）如何運作，並使用在 x86 上編譯過的程式作為範例。我承諾過在另一篇文章中涵蓋 x64 上的 PIC ，也就是現在這篇。既然大家都已經了解 PIC 的基本原理，這篇文章將不會牽扯太多細節。一般情況下，概念在不同平台下都是相似的，但細節會因為機器架構而有所不同。 RIP-relative 定址 在 x86 上，函式的呼叫（使用 call 指令）使用與目前指令相對位移的方式定址，資料的取用（使用 mov 指令）只支援絕對定址。既然 PIC 無可避免地需要利用 IP-relative 的定址方式，絕對位址就不容易與 PIC 同時存在，而 這也造成我們在前一篇文章看到 PIC 會比較沒有效率的原因。 x64 透過一個新的"RIP-relative 定址模式"修正了這點，這是 64 位元的 mov 指令去存去記憶體的預設模式（此模式也在其他指令中使用，像 lea ）。根據"英特爾架構手冊第二冊"中的說明：   一個新的定址模式，RIP-relative（相對於 instruction-pointer），在64 位元模式中被實作。一種有效率的方式去增加相對於指向下一個指令的 64 位元 RIP 的位移   在 RIP-relative 模式中的位移長度為 32 位元。由於正負值的位移都有需要，所以在 RIP 中的此種模式，支援的最大位移大概有最多 +/- 2GB 的位移。 在 x64 PIC 中取用資料 – 一個例子 作為一個簡單的對照，我會使用跟前篇文章同樣的 C 代碼作為取用資料的例子： int myglob = 42 ; int ml_func ( int a, int b) { return myglob + a + b; } 讓我們看看 ml_func 的反組譯：  00000000000005ec <

perforce 是一個商業公司所出的 VCS ，有不少公司採用 （雖然我覺得很不順手...） ，包括我目前待的公司，在 Linux 上安裝其圖形操作介面後，一執行居然吐出 abort...WTF?! 由於它們只提供 binary 檔，無法確認問題。根據經驗，很多開源軟體都要讀取設定檔，但往往在檔案不存在的情況下用錯誤的模式而無法開啟，然後又不檢查是否開啟成功就使用 file descriptor，所以就會掛點。不過 perforce 是一家那麼久的軟體公司耶！應該不會犯這種低級錯誤吧？不管了，死馬當活馬醫，用 strace 觀察一下，結果真的看到： stat64("/home/mars/.p4qt/ApplicationSettings.xml", 0xa547e6c) = -1 ENOENT (No such file or directory) lstat64("/home/mars/.p4qt/ApplicationSettings.xml", 0xbf983a30) = -1 ENOENT (No such file or directory) open("/home/mars/.p4qt/log.config", O_RDONLY|O_LARGEFILE|0x80000) = -1 ENOENT (No such file or directory) futex(0x7458a88, FUTEX_WAKE_PRIVATE, 2147483647) = 0 rt_sigprocmask(SIG_UNBLOCK, [ABRT], NULL, 8) = 0 tgkill(30326, 30326, SIGABRT)           = 0 --- SIGABRT (Aborted) @ 0 (0) --- +++ killed by SIGABRT +++ 好像是真的這種白癡錯耶...手動生出這兩個空白檔，開起來了，運作正常... -_-

上週 曾經為了讓 racket 的互動式介面好用一點，寫了一個小工具，後來又遇到另一個命令列程式有類似的問題（ ydict ），所以就想要寫一個通用的版本，希望可以一次解決同樣的麻煩。也就是說，我想用類似下列的指令： $ realineaddon cmd 就讓 cmd 獲得 readline 的功能。 後來寫到一半，遇到幾個問題點，本來要開始翻查 man page ，但念頭一轉，我應該不是第一個想作這件事的人吧？找了一下，果然發現 rlwrap 這個好物，rlwrap 不只有我想要的功能，作者還額外提供了： cmd 可以是 terminal-based program。作者以 pseudo terminal 的方式來傳遞輸入輸出，而不只是單純的 pipe。 支援 filter （須以 Perl 撰寫模組）。讓使用者攔截輸入、輸出...可以為文字介面程式操作帶來更多可能性。 rlwrap 的程式碼可讀性也很高，綜合了創意、實作完成度，實在是小程式的精品啊！:-)

在一個已知的未排序 list 中尋找第 k 大的物件是經典的 selection 問題 。有許多的演算法針對各種變形提出極為優化的解法。底下是我練習 C.A.R. Hoare  的 quickselect ，但我將其改成 not-in-place 的版本。（為何有這篇?因為臨時有一個小時不知道要幹嘛...拿來複習遞迴剛剛好 :-P） #!/usr/bin/env python import   random   def  kth ( L, k ) :         le =  [ ]         eq =  [ ]         gt =  [ ]         pivot = L [ random . randint ( 0 ,  len ( L ) ) ]          for  e  in  L:                  if  e  <  pivot:                         le. append ( e )                  elif  e  >  pivot:                         gt. append ( e )                  else :                         eq. append ( e )          if  k  < =  len ( gt ) :                  return  kth ( gt, k )          elif  k  < =  ( len ( gt )  +  len ( eq ) ) :                  return  pivot          else :                  return  kth ( le,  ( k -  len ( gt )  -  len ( eq ) ) )   print ( kth ( range ( 1000 ) ,  5 ) )

racket 是一個許多人在用的 scheme 實作，但其 interpreter 在 interactive mode 時並沒有很方便的控制方式。既不能使用方向鍵移動修改，也沒有 history 的功能。要為 racket 直接加入這個功能其實也不難，但想到要先找出進入點就有點累... 剛好在 系統程序員成長計畫 中看到類似的問題（想讓命令列 jdb 的使用更方便），該作者提出了一個解法  - 增加一層 shell 。這個想法很棒，可以在使用原本 binary 檔的情況下預作 readline 的動作，這麼一來就可達成我要的效果。溝通的機制則用 pipe 即可（若是要為 terminal-based program 做這件事，就得祭出 pseudo terminal 了）。OK，江湖一點訣，點破不值錢，實作如下： #include <stdlib.h> #include <stdio.h> #include <unistd.h> #include <readline/readline.h> #include <readline/history.h> int  main ( ) {          char *  input;          int  pipe_fds [ 2 ] ;         ssize_t input_bytes  =   0 ;          char  output [ 1024 ] ;          if   ( pipe ( pipe_fds )   ==   -1 )   {                 fprintf ( stderr,  "pipe open fail \n " ) ;                 exit ( -1 ) ;          }          switch   ( fork ( ) )   {                  case   -1 :                         fprintf ( stderr,  "for