火星蚊的地球記事

 火星蚊的地球記事

Posted on Edited on

讓使用者能取得一個 collection 內的每個 element，而不需要暴露此 collection 的 implememtation。

Iterator Pattern 封裝了「拿出下一個 element」這件事，讓外部可以不需要知道 collection 實際上以什麼方式實作，如 array、list、stack 等等，就能以一致的方式取得 element。iterator 也讓 collection 的責任更簡單，collection 負責管理一群 object，而 iterator 負責 traverse element。

使用情境

有多種 collection 一同使用，希望能用同樣方式 traverse element 時。

UML

Iterator Pattern

library 及語言支援

C++ STL、Qt、Java 等等的 container 都有支援 iterator。用 iterator 要注意 iterate 過程中能不能更動該 container，因為 iterator 會直接或間接的 access container 內部資料，所以不同實作方式會影響 iterator 的使用。例如 Qt 對 container 用 implicit sharing，所以使用 iterator 期間 copy container 要注意會不會搞爛 iterator 或 iterator 指向的 container 跟預想不同。

在某些語言，如 PHP，會提供 foreach 的語法，這進一步將 iterator 變成 syntax 了。

Posted on Edited on

《科技渴望社會》的第一篇。這本書集結了科技與社會有關的文章與演講稿等等的翻譯，是 STS (Science, Technology and Society) 領域的讀本。

這篇描述三個在美國電氣化過程中十分活耀的人：愛迪生、英瑟爾、密契爾，分別在電氣化不同階段扮演不同角色。愛迪生主要技術但跨越了管理以及財務等等，讓電氣化得以開始推展。英瑟爾有技術知識也是財務專家，但長處在於管理，透過管理將電力事業的規模擴大。而密契爾則是以金融策略使電力事業進一步擴大為區域系統。三位都對多個領域有所涉獵與了解，綜合各種因素以不同所長推展美國的電力發展。

其中愛迪生的篇幅是我看得最能理解在幹嘛的部分……

從這篇文章的研究中，可以看到愛迪生的思考脈絡以及因果邏輯。因目的是取代煤氣燈，所以先考量經濟效益，才結合科學上的靈感，繼而搜尋與試驗特定目標，而非如給小朋友看的故事所述──只是不斷地嘗試。姑且不論從眾多文獻中回推因果是否真是當年愛迪生所想，但看到回推出有邏輯的思考脈絡，才能認為這是合理、可行可能的，而非如神話般的不可思議。

科學歷史應該要呈現這樣的部份，呈現科學發展的交錯跟曲折性，呈現當時人們的思考脈絡，而非講得科學猶如直升飛機筆直上升，各個有所成果的科學家不是天才就是堅忍不拔云云。像是《科學發現幕後的黑色喜劇》跟《電的旅程》就有這種交(ㄨㄞ)錯(ㄑ一)曲(ㄋ一ㄡˇ)折(ㄅㄚ)但比較真實的科學史。

至於英瑟爾跟密契爾因為又是管理又是金融的，我實在看不太懂到底在寫什麼……Orz

總之，可以說是三個人都有跨領域的能力，一步步推展電力發展。從一間公司需要技術的不斷改良以突破擴大的障礙，接著公司開始變大、變多而需要管理才能繼續擴大，之後需要用金融方式讓系統進一步擴張到區域等級，每個時期有不同的關鍵知識跟能力。

要說有 fu 的感想……應該是「只會技術很難完整建立或推展一個事業系統」。

Posted on Edited on

不愧是技術出身的人創辦的公司，完全以技術為重。喜歡這本書所呈現的務實觀，以真正做出好用東西為最高原則的務實。

職業生涯

思考五年後你希望從事的理想工作，你希望在哪裡工作？你想做什麼？希望賺多少錢？敘述這個職務：如果你在網路上看到這個工作機會，徵才內容會是什麼？現在，快轉到四、五年後，假設你在做這份工作，你這五年間的履歷表內容是什麼模樣？從現在起，你經過哪些途徑，到達那個時候的理想工作？

持續想著這份理想工作，根據它來評估你目前的長處與缺點，你需要做出哪些改進？這一步需要外人提供的意見，因此和你的經理或同儕談談，徵詢他們的意見。最後，你要如何獲得這份理想工作？你需要哪些訓練？需要什麼工作經驗？

我想補充，思考職涯前要先想生涯，因為工作是生活的一部份，是讓工作配合生活，而不是反過來。你重視的是什麼？想要的生活是什麼？現在有的是什麼？有什麼能力能幫助你獲得想要的？

釐清生涯之後才去想怎麼樣的工作能配合？畢竟，有偉大的理想或願景很好，但那並不是每個人都想要的。每個人重要的事物都不同，本來就不該用一套標準套用在所有人。

共識跟搖鈴

所謂共識，在於找到最佳方法，而不是用自己的方法。

最佳方法應該是對團隊、對工作最有益的。

然後呢，討論要有人拿捏什麼時候該喊停做出結論，會開得久但沒結論實在是很浪費。

歐普拉法則

科技人常犯一個錯，總認為如果根據資料和明智的分析提出一個聰明、考慮周到的論點，人們就會改變他們的看法。其實不然。如果你想改變人們的行為，你不能只在論點上勝出，你必須感動他們的心

（狀態顯示為中箭）

要說故事讓人家有 fu，才會想去做那件事……

想想也是，人不是理性的生物呀~ˊ_>ˋ

70/20/10 的資源分配法則

70% 資源用於核心事業，20% 資源用於有一些小成功的新產品，10% 資源分配給全新的計畫。

這是資源分配喔，不是那個 20% 時間。這邊指的資源應該是人員，畢竟 Google 做軟體的，資源最主要就是人了。

投資高風險的新東西要小心過度投資，過度投資會讓人想回收過去投注的資源而傾向只看好的、不容易承認失敗或錯誤，簡單講就是個賭徒的概念。(欸)

20% 時間計畫

20% 時間計劃應該是 Google 有名的制度之一。

重點在自由而不在時間，重點在可以自由地去做想做的事。

根據自我決定理論，人類對於自主（根據自己的意志和抉擇而行為，而非受外界施壓而行為）、勝任能力，以及和其他人的關聯都有強烈的需求。自我決定理論認為，人們是否覺得他們的工作有動力且有成就感，有相當程度取決於工作能否滿足他們的這些需求。

20% 時間計畫不需要金錢酬勞，因為他們不想讓外在獎酬取代內在獎酬而扼殺創造力。

看起來也不是一個自己悶著頭做就行的，除了有點子之外也要能吸引其他人一起加入。

從書中看起來，20% 時間要產生很棒的新產品不是很容易，它需要員工有足夠的自身動力，更需要有無數無數的時間與嘗試。如書中所說，20% 時間產生的產品或功能並非最重要的「產出」，真正重要的是在過程中得到經驗以及學習的智慧創作者，這些經驗會帶在這些人身上繼續下一次的發揮。比起產生新創產品，20% 時間或許更重要的反而是在教育訓練上。

20% 時間與其說是 Google 的一個與眾不同的制度，不如說他們只是將那種鼓勵創新、不怕失敗的文化變成一個制度。先有文化才有制度，而不是想以這個制度去培養創新文化，先後順序不一樣的。

詢問困難的問題

「當這家公司的成功與獲利最仰賴的競爭優勢消失時，公司該怎麼辦？」

在剛開始看到對手的時候，甚至在更早、還很順利的時候就詢問困難的問題，然後思考對策、解決方式。

問這問題難，難在這樣的問題令人不安。回答這樣的問題也難，但沒有好的答案能問出問題總是一線希望。

最後書中也列舉許多重要的問題，當作結語總結整本書。

Posted on Edited on

要執行一隻程式須將它的 instruction 跟 data load 到 memory。現代 OS 結合 virtual memory 以及 memory management 的 paging 機制來 load process。

virtual memory 將 process 認知的 memory space 跟 physical memory 分離，藉此達到 process 不一定要在它認定的 physical memory address 上執行。如果實際有的記憶體比較少，virtual memory 也可以在記憶體不足的情況下讓 process 以為它有這麼多 memory 可用。

每個 process 有自己的 virtual memory space，virtual memory space 的大小由平台的定址 bit 數決定，例如 32 bit 的平台可定址的 address 就從 0 到 2^32 - 1，總大小為 4 GB。process 在 32 bit 系統中的 virtual memory space 大小是 4GB，但不是 4GB 都可以為 process 使用，process 只能用 OS 分配給它的空間，亂用的話會被強制結束。

paging 簡單來說是將 memory space 分成固定 size 的 page，現在 OS 大多使用 4K size 的 page。virtual memory space 跟 physical memory space 都以 page 切分，MMU（Memory Management Unit）負責 virtual page 與 physical page 的 mapping。virtual page 不存在 physical memory 而該 virtual page 又要被使用時會發生 page fault，此時 OS 負責將 virtual page 從 disk 中讀到 memory 並建立 virtual page 與 physical page 之間的 mapping。

結合 virtual memory 跟 paging 的 load process 步驟：

  1. 建立這個 process 的 virtual memory space，實際上是建立 virtual page 對應到 physical page 所需的 data structure。
  2. 由 executable file header 的資訊建立 virtual space 與 executable file 的關係，也就是 process 的 virtual memory space 哪一塊對應到 executable file 的哪一塊。
  3. 將 PC register 設到執行入口，process 開始執行。
  4. process 執行到的程式或需要的 data 沒有 load 進 physical memory，發生 page fault。OS 依照 virtual space 與 executable file 的對應關係知道要從 disk load 哪個 page 到 physical memory，load 進 physical memory 後建立 virtual apge 與該 physical page 的關係，這段即一般講 load 所指的動作。控制權還給 process 繼續跑。

其中 step 4 會不斷發生。至於 physical memory 被用到需要換掉裡面的 page 才能放新 page 又是另一個故事了……

View

對 load 來說，executabl file 裡 section 內容是什麼不重要，重要的是權限。ELF 檔以 load 的角度被分為多個 segment，而一個 segment 裡會有多個屬性類似的 section。以不同角度劃分 executable file 在 ELF 中稱為不同 view，以 section 角度劃分是 linking view，以 segment 角度劃分是 execution view。

之所以分了 section 又以 segment 再區分 ELF 檔，是因為以上述的 loading 方式，load 必須以 page 為單位。如果依據 section 區分 page 會使用太多 page 而且每個 page 又只用一點點，很浪費 memory。

Program header table

executable file 用 program header table 保存 segment 的資訊，可以用 readelf -l 查看。

program header table 中每個 segment 都有些欄位分別表示不同意義，其中 file size 跟 memory size 分別表示這個 segment 在 ELF file 中的 size 以及 load 到 memory 後佔用多少 virtual memory。正常來說 file size <= memory size，兩個相等沒什麼好說的，就是 file 內容 load 進 memory。出現 file size < memory size 其中一個可能是 bss section。

bss section 是放 C 語言裡沒有初始化或初始化為 0 的 global variable，在 ELF 檔中只會記錄「有這個 variable」以及它的 size，不會給予該 variable 所需要的空間，因而能縮小 ELF 檔。到執行時當然要給這些 variable 其所需要的空間好讓它存 value，所以以 segment 角度來看包含 bss section 的 segment 會看到 memory size > file size。另外，C 語言規定 bss section 的初始內容都是 0，不同系統會以不同方式實作。

Example

用 Static link 裡的例子看 segment。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
$ readelf -l foo

Elf file type is EXEC (Executable file)
Entry point 0x40010d
There are 3 program headers, starting at offset 64

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  LOAD           0x0000000000000000 0x0000000000400000 0x0000000000400000
                 0x0000000000000180 0x0000000000000180  R E    200000
  LOAD           0x0000000000000180 0x0000000000600180 0x0000000000600180
                 0x0000000000000018 0x0000000000000018  RW     200000
  GNU_STACK      0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x0000000000000000 0x0000000000000000  RW     10

 Section to Segment mapping:
  Segment Sections...
   00     .text .eh_frame 
   01     .data 
   02

type 是 LOAD 才是需要 load 的 segment（這句話怎麼聽起來像廢話）。有兩個 segment，分別是 .text section 所在的可讀可執行 segment 以及 .data section 所在的可讀可寫 segment，他們分別會 load 到 0x400000 跟 0x600180，執行後可以用 cat /proc/<pid>/maps 驗證。這個例子的 file size 跟 memory size 相等，因為裡面沒有 .bss section，加個未 initialize 的 global 變數就可以看到不一樣啦～

Ref

Posted on Edited on

最近工作在跑scrum，來篇觀察日記(欸)。一個端午連假吃飽太閒的概念

頭一兩次planning meeting只有「混亂」兩個字可以形容。人多到坐了好幾張桌子，後面不知道前面在講什麼、前面不知道後面在幹嘛，直接分裂成好幾個小圈圈自己討論，整個會開下來都不知道在做什麼。混亂了一兩次之後，與會人數才縮減到比較能進行討論的數量。

一開始的討論是上面講上面的、底下自己懂自己的，到底真懂還是假懂，到底我的懂跟你的懂一不一樣都沒人知道，實作下去就發現做下來跟原本想的不一樣。接著的planning meeting開始出現會澄清彼此認知跟假設以及資訊的交流，到這裡才有那麼點資訊流通的樣子出來。不過這樣的澄清跟交流主要還是靠主持人push，而現在的主持人還是scrum master，以這點來說應該是非常不符合scrum……XD 但是我覺得以當前狀況來說這是可以接受的。到目前為止，雖然有RD跟QA參與（先別管什麼跨功能），但討論比較多還是在RD之間跟向PO確認使用者想要的東西，可能因為story被拆小，目前為止的story的測試成分不高。

我承認有時候planning開一開會覺得很煩躁，怎麼同一段話每個人的理解都不一樣、奇怪這上次不是講過了、啊現在到底是怎樣、能不能快點達成共識啊？可是，這正是討論需要做的，如果不讓每個人表達意見、發問跟參與討論，我們會直接失去不同的想法與聲音，那也沒必要開這種會，看誰厲害聽他的就好了。

planning meeting中可以讓member知道為什麼要做這個功能、使用者如何使用、需求又是什麼，我覺得這對RD蠻好的，畢竟大家通常會想知道為什麼要做這個功能、為什麼要這麼做，知道理由跟也能認為合理蠻重要的。而RD知道這些，在實作之外，或許也能提供其他建議。

估size也可以觀察到很有趣的事情。出牌的重點不在精確估出size而在資訊交流及溝通。頭幾次一個story就出很多次牌，好像想出到大家都是一致的，沒幾次就讓人想從眾，尤其是你不想講話或者講到沒什麼好講的時候。我曾經閃過因為不想講話乾脆去猜大多數人會出的牌的念頭，不過想想不太對就沒這麼幹。可能發現這樣出牌會沒完沒了，後來估size變成出兩次牌或收斂到兩三個區間就用權重算size，這似乎讓人變得比較忠於自己的想法。

人的行為會被環境跟過往經驗影響。出牌跟別人不一樣需要說明，說完出牌還是跟其他人有落差的時候，有些人會選擇堅持自己的想法，有些人會因為不想再被cue而出得跟大家一樣。原本就堅持自己想法的人很好，但考量台灣教育及工作環境的薰陶，對於「表達意見」的看法可能是負面的，而scrum希望每個人可以表達自己的想法，應該在實際做法上設法減少從眾跟鼓勵表達。我不覺得只是口頭上說「大家應該要表達自己的想法啊」、「應該要有熱情有向上的心啊」有多大意義，對表達想法的鼓勵與否，重點之一在有人提出意見後「發生什麼事」。開會開到一片死寂也沒那麼容易，總有人身先士卒的說些什麼，說完之後得到什麼樣的回應會影響其他人開口的意願，這種事實跟環境氣氛比嘴上說說更有說服力。

daily meeting的部分，好吧雖然可以理解但實在不太喜歡調整後的開始時間，先不論這個的話，我覺得不錯的地方是主持人一個個問有沒有什麼阻礙，雖然成員可以主動說出阻礙是比較好的，可是在還沒建立這樣的習慣前，刻意詢問每個人就是給予機會去表達跟習慣，雖然被動但總比沒有好。如果像我比較害羞或者有時候就是忘了，反正每天都有機會。也注意到自從有次問阻礙被變成提問題後，daily流程中在問阻礙前多了開放提問。從這些流程的小地方可以看到「改變與改善」，我覺得這才是agile精神真正的作為。

而retrospective，我不知道為什麼就是很難在那個當下做出反應，很難順著遊戲規則去想，常常腦袋一片空白。有點像是，不是對跑scrum沒什麼想法，而是我在那個當下就是對遊戲規則反應不過來的沒進入狀況。這可能是因為我還在收上個project的尾，對正在進行的story只出一張嘴，所以很難知道到底碰到什麼狀況。另一個可能的原因是，我在某些遊戲規則或者引導下需要比較長時間進入狀況，因為在其他場合也多次出現類似的情形。

說完實際上運作的種種，來談談精神層面(?)。agile的基本精神──因應改變而改變──我是認同的，可是沒辦法相信宣稱agile就是真正的agile。精神固然重要，但現階段實際做法是不是符合那精神更重要，否則都只是披著agile的皮的不知道什麼東西。講不知道什麼東西已經是好聽了，基於對台灣資方的不信任感，我覺得很容易是披著agile的皮的壓榨……

同樣一句話十個人聽都可以有十種解釋了，而agile的精神違反物理定律「慣性」(咦?)，我不認為每個人理解跟認知的agile精神就真的是其精神的內涵（對，連我自己都可能不是真的理解）。「聽其言，觀其行」比較準確，與其聽人宣稱不如直接檢視實際作為。人的行為到這個年紀基本上會有某些pattern，這種東西不會一下子說變就變，是可以從各方面跟小地方觀察到些什麼的。

最後，說到改變，agile說改變改變但不是隨便亂變。

scrum流程裡sprint中間不能隨便亂改要做的事，這是改變中的「不變」。變動越大越頻繁，越需要某程度的不變去作為穩定跟結構，這是讓人知道什麼時間點會做調整、什麼時候不會動而能安心做事，否則沒有規則的亂變會導致無所適從或者直接暴衝。變動充滿不確定性，但是人會想要控制感，這是人性，不斷改變帶來的是許多不確定感，而在這之中的不變跟些許規則是讓人能知道有什麼是能夠掌握的。雖然不知道背後緣由，但我想scrum規範這樣的流程是有其原因的。

Posted on Edited on

所謂 Static Link（靜態連結）──在 linking 階段針對未知 address 的 symbol 填入 address，把一堆 object file 黏在一起變成可執行檔。

沒了。(誤)

object file 是 compile 後的 binary 中間檔，它有多種 format，ELF 是其中之一。linking 主要是將其他 object file 中 symbol 的正確 address 填進 reference 到它的指令中，例如 object file A 的指令 reference 到 object file B 的 symbol x，link 前 object A 無法得知 x 的 address，link 時才會知道 x 正確的 address 並將之填進 object file A 的指令中。

Two-pass linking

Static link 的流程是 two-pass linking，將 linking 分為兩個步驟：

  1. 分配 virtual address space
  2. symbol resolution and relocation

1. 分配 virtual address space

合併多個 object file 成一個檔案。

  • 掃描所有 object file，合併相同的 section，例如合併 a.o 跟 b.o 的 .text section。
  • linker 透過 object file 中的各種 table 得知各 section 的長度、屬性以及位置。
  • 收集所有 object file symbol table 中的 symbol definition 跟 symbol reference 放到 global symbol table。
  • 合併完 object file，各 symbol 的 virtual address 已經確定，linker 會計算 symbol 的 virtual address。
    • symbol 的 virtual address = 所在 section 合併後的 address + symbol 的 offset

2. symbol relocation and resolution

static link 的重點。

compiler 不知道 reference 到別的 object file 中 variable 或 function 的 address，所以遇到其他 object file 的 symbol 時會塞假的 address 進 instruction。

利用 relocation table 將真正的 virtual address 填進 instruction 即為 symbol relocation。relocation table 記錄需要調整的 instruction 所在位置以及如何調整。每個需要 relocate 的 section 都有一個 relocation table，relocation table 也是 ELF 檔中的一個 section，如 .rel.text section 是 .text 的 relocation table。可以利用 objdump -r xxx.o 看 relocation table。

linker 由 global symbol table 得知 symbol 的 address，接著依據不同定址模式將 address 填進 instruction。所有 object file 中原本 undefined 的 symbol 經過 relocate 及 resolve 後應該要能在 global symbol table 中找到對應的 address，否則會出現 undefined reference 的 error。

Example

來點例子比較有 fu。

source

foo.c
1
2
3
4
5
6
7
8
9
10
extern int sum;
static int globalvar = 2;

int foo(int a, int b)
{
    static int staticvar = 1;
    sum = a + b;
    static int* p = &staticvar;
    p = &sum;
}

sum 宣告成 extern，表示是其他檔案的 symbol，在 foo() 裡使用就是跨 object file 的 reference。

static 的 global 變數 globalvar 是只在這個 file 裡才看得到的變數。

main.c
1
2
3
4
5
6
7
8
extern int foo(int, int);
int sum = 1;

int main()
{
    foo(5, 3);
    return 0;
}

宣告 foo() 在別的檔案。

$ gcc -c foo.c main.c compile 成 object file。

$ ld foo.o main.o -e main -o foo link 兩個 object file，以 -e 指定 entry point。

PS：以上述簡化的 compile 及 link，程式會在跑到要結束的時候發生 segmentation fault，可能跟自己指定 entry point、未使用 C Runtime 處理開始及結束 process 有關。

分配空間及 address

首先分配空間及 address，將多個 object file 裡相同的 section 放在一起並分配空間及 address，觀察三個檔案的 section：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
$ readelf -S foo.o

There are 13 section headers, starting at offset 0x318:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000000000  00000040
       0000000000000025  0000000000000000  AX       0     0     1
  [ 2] .rela.text        RELA             0000000000000000  000002a0
       0000000000000048  0000000000000018   I      11     1     8
  [ 3] .data             PROGBITS         0000000000000000  00000068
       0000000000000014  0000000000000000  WA       0     0     8
  [ 4] .rela.data        RELA             0000000000000000  000002e8
       0000000000000018  0000000000000018   I      11     3     8
  [ 5] .bss              NOBITS           0000000000000000  0000007c
       0000000000000000  0000000000000000  WA       0     0     1
  [ 6] .comment          PROGBITS         0000000000000000  0000007c
       000000000000001e  0000000000000001  MS       0     0     1
  [ 7] .note.GNU-stack   PROGBITS         0000000000000000  0000009a
       0000000000000000  0000000000000000           0     0     1
  [ 8] .eh_frame         PROGBITS         0000000000000000  000000a0
       0000000000000038  0000000000000000   A       0     0     8
  [ 9] .rela.eh_frame    RELA             0000000000000000  00000300
       0000000000000018  0000000000000018   I      11     8     8
  [10] .shstrtab         STRTAB           0000000000000000  000000d8
       000000000000005e  0000000000000000           0     0     1
  [11] .symtab           SYMTAB           0000000000000000  00000138
       0000000000000138  0000000000000018          12    11     8
  [12] .strtab           STRTAB           0000000000000000  00000270
       000000000000002f  0000000000000000           0     0     1

$ readelf -S main.o

There are 12 section headers, starting at offset 0x268:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000000000  00000040
       000000000000001a  0000000000000000  AX       0     0     1
  [ 2] .rela.text        RELA             0000000000000000  00000238
       0000000000000018  0000000000000018   I      10     1     8
  [ 3] .data             PROGBITS         0000000000000000  0000005c
       0000000000000004  0000000000000000  WA       0     0     4
  [ 4] .bss              NOBITS           0000000000000000  00000060
       0000000000000000  0000000000000000  WA       0     0     1
  [ 5] .comment          PROGBITS         0000000000000000  00000060
       000000000000001e  0000000000000001  MS       0     0     1
  [ 6] .note.GNU-stack   PROGBITS         0000000000000000  0000007e
       0000000000000000  0000000000000000           0     0     1
  [ 7] .eh_frame         PROGBITS         0000000000000000  00000080
       0000000000000038  0000000000000000   A       0     0     8
  [ 8] .rela.eh_frame    RELA             0000000000000000  00000250
       0000000000000018  0000000000000018   I      10     7     8
  [ 9] .shstrtab         STRTAB           0000000000000000  000000b8
       0000000000000059  0000000000000000           0     0     1
  [10] .symtab           SYMTAB           0000000000000000  00000118
       0000000000000108  0000000000000018          11     8     8
  [11] .strtab           STRTAB           0000000000000000  00000220
       0000000000000015  0000000000000000           0     0     1

$ readelf -S foo

There are 8 section headers, starting at offset 0x3c8:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         00000000004000e8  000000e8
       000000000000003f  0000000000000000  AX       0     0     1
  [ 2] .eh_frame         PROGBITS         0000000000400128  00000128
       0000000000000058  0000000000000000   A       0     0     8
  [ 3] .data             PROGBITS         0000000000600180  00000180
       0000000000000018  0000000000000000  WA       0     0     8
  [ 4] .comment          PROGBITS         0000000000000000  00000198
       000000000000001d  0000000000000001  MS       0     0     1
  [ 5] .shstrtab         STRTAB           0000000000000000  000001b5
       000000000000003a  0000000000000000           0     0     1
  [ 6] .symtab           SYMTAB           0000000000000000  000001f0
       0000000000000180  0000000000000018           7    10     8
  [ 7] .strtab           STRTAB           0000000000000000  00000370
       0000000000000053  0000000000000000           0     0     1

Static link step1

foo.o 跟 main.o 的 .text 以及 .data section 在 foo 合在一起啦！

relocation

section 合併之後就能計算出 symbol 的 address，進入 static link 的重頭戲 relocation。

先看還沒 relocate 的 foo.o 的 symbol：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$ readelf -s foo.o

Symbol table '.symtab' contains 13 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS foo.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1 
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    3 
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    5 
     5: 0000000000000000     4 OBJECT  LOCAL  DEFAULT    3 globalvar
     6: 0000000000000008     8 OBJECT  LOCAL  DEFAULT    3 p.1749
     7: 0000000000000010     4 OBJECT  LOCAL  DEFAULT    3 staticvar.1748
     8: 0000000000000000     0 SECTION LOCAL  DEFAULT    7 
     9: 0000000000000000     0 SECTION LOCAL  DEFAULT    8 
    10: 0000000000000000     0 SECTION LOCAL  DEFAULT    6 
    11: 0000000000000000    37 FUNC    GLOBAL DEFAULT    1 foo
    12: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND sum
  • Num：symbol table array 的 index。
  • Name：st_name，symbol name。
  • Value：st_value，symbol value，該 symbol 的 address。
  • Size：st_size，表示所佔的大小。如果 symbol 是變數且在這個 object file 內，size 會有值，再根據有沒有 initialized 決定放在 .data 或 .bss section。global 跟 local static 有 initialized 的變數會在 compile 階段挖好空間、決定好 address，也就會在 executable file 中佔有空間。
  • Type 及 Bind 對應 st_info，GLOBAL 表示 global 可見，LOCAL 則表示在這個 compile unit 中可見。
  • Ndx：st_shndx，屬於哪個 section，UND 表示這個 symbol 還是 undefined。

globalvar 跟 staticvar 兩個變數都放在 .data section，foo 在 code section .text，sum 被宣告成 extern 則是 undefined 要等 link 的時候才知道在哪。

main.o 的 symbol：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ readelf -s main.o

Symbol table '.symtab' contains 11 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS main.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1 
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    3 
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    4 
     5: 0000000000000000     0 SECTION LOCAL  DEFAULT    6 
     6: 0000000000000000     0 SECTION LOCAL  DEFAULT    7 
     7: 0000000000000000     0 SECTION LOCAL  DEFAULT    5 
     8: 0000000000000000     4 OBJECT  GLOBAL DEFAULT    3 sum
     9: 0000000000000000    26 FUNC    GLOBAL DEFAULT    1 main
    10: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND foo

sum 定義在 main.o 裡，foo 在 main.o 則是 undefined。

foo 的 symbol：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
$ readelf -s foo

Symbol table '.symtab' contains 16 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 00000000004000e8     0 SECTION LOCAL  DEFAULT    1 
     2: 0000000000400128     0 SECTION LOCAL  DEFAULT    2 
     3: 0000000000600180     0 SECTION LOCAL  DEFAULT    3 
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    4 
     5: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS foo.c
     6: 0000000000600180     4 OBJECT  LOCAL  DEFAULT    3 globalvar
     7: 0000000000600188     8 OBJECT  LOCAL  DEFAULT    3 p.1749
     8: 0000000000600190     4 OBJECT  LOCAL  DEFAULT    3 staticvar.1748
     9: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS main.c
    10: 0000000000600194     4 OBJECT  GLOBAL DEFAULT    3 sum
    11: 0000000000600198     0 NOTYPE  GLOBAL DEFAULT    3 __bss_start
    12: 000000000040010d    26 FUNC    GLOBAL DEFAULT    1 main
    13: 00000000004000e8    37 FUNC    GLOBAL DEFAULT    1 foo
    14: 0000000000600198     0 NOTYPE  GLOBAL DEFAULT    3 _edata
    15: 0000000000600198     0 NOTYPE  GLOBAL DEFAULT    3 _end

link 後 symbol 填上 value，原本是 undefined 的 sum 跟 foo 都有各自的 address 跟所屬的 section。這個合併後的 symbol table 就是 global symbol table。

接著，linker 從 global symbol table 知道 symbol 的 address，並依據 relocation table 知道哪些幾個指令要改以及怎麼改。main.o 跟 foo.o 的 relocation table：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
$ readelf -r foo.o

Relocation section '.rela.text' at offset 0x2a0 contains 3 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000014  000c00000002 R_X86_64_PC32     0000000000000000 sum - 4
00000000001b  000300000002 R_X86_64_PC32     0000000000000000 .data + 0
00000000001f  000c0000000b R_X86_64_32S      0000000000000000 sum + 0

Relocation section '.rela.data' at offset 0x2e8 contains 1 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000008  000300000001 R_X86_64_64       0000000000000000 .data + 10

Relocation section '.rela.eh_frame' at offset 0x300 contains 1 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000020  000200000002 R_X86_64_PC32     0000000000000000 .text + 0


$ readelf -r main.o

Relocation section '.rela.text' at offset 0x238 contains 1 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
00000000000f  000a00000002 R_X86_64_PC32     0000000000000000 foo - 4

Relocation section '.rela.eh_frame' at offset 0x250 contains 1 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000020  000200000002 R_X86_64_PC32     0000000000000000 .text + 0

offset 欄位表示需要 relocate 的 instrcution 所在位置，如 foo.o 的 0x14 是需要 sum address 的位置。

修正 address 的方式依據 instruction 而定。簡單分成相對定址跟絕對定址，可由 relocation entry 的 type 知道是哪種定址模式。相對定址填入相對下一個指令 address 的 offset，絕對定址填入 symbol 的絕對 address，所以執行檔中有以 offset 跟絕對 address 得到 symbol address 的 instruction。R_X86_64_PC32 屬於相對定址，R_X86_64_32S 屬於絕對定址。看看 link 後會 instruction 怎麼改變：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
$ objdump -d foo.o

Disassembly of section .text:

0000000000000000 <foo>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   89 7d fc                mov    %edi,-0x4(%rbp)
   7:   89 75 f8                mov    %esi,-0x8(%rbp)
   a:   8b 55 fc                mov    -0x4(%rbp),%edx
   d:   8b 45 f8                mov    -0x8(%rbp),%eax
  10:   01 d0                   add    %edx,%eax
  12:   89 05 00 00 00 00       mov    %eax,0x0(%rip)        # 18 <foo+0x18>
  18:   48 c7 05 00 00 00 00    movq   $0x0,0x0(%rip)        # 23 <foo+0x23>
  1f:   00 00 00 00 
  23:   5d                      pop    %rbp
  24:   c3                      retq   
  

$ objdump -d main.o

Disassembly of section .text:

0000000000000000 <main>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   be 03 00 00 00          mov    $0x3,%esi
   9:   bf 05 00 00 00          mov    $0x5,%edi
   e:   e8 00 00 00 00          callq  13 <main+0x13>
  13:   b8 00 00 00 00          mov    $0x0,%eax
  18:   5d                      pop    %rbp
  19:   c3                      retq   


$ objdump -d foo

Disassembly of section .text:

00000000004000e8 <foo>:
  4000e8:       55                      push   %rbp
  4000e9:       48 89 e5                mov    %rsp,%rbp
  4000ec:       89 7d fc                mov    %edi,-0x4(%rbp)
  4000ef:       89 75 f8                mov    %esi,-0x8(%rbp)
  4000f2:       8b 55 fc                mov    -0x4(%rbp),%edx
  4000f5:       8b 45 f8                mov    -0x8(%rbp),%eax
  4000f8:       01 d0                   add    %edx,%eax
  4000fa:       89 05 94 00 20 00       mov    %eax,0x200094(%rip)        # 600194 <sum>
  400100:       48 c7 05 7d 00 20 00    movq   $0x600194,0x20007d(%rip)        # 600188 <p.1749>
  400107:       94 01 60 00 
  40010b:       5d                      pop    %rbp
  40010c:       c3                      retq   

000000000040010d <main>:
  40010d:       55                      push   %rbp
  40010e:       48 89 e5                mov    %rsp,%rbp
  400111:       be 03 00 00 00          mov    $0x3,%esi
  400116:       bf 05 00 00 00          mov    $0x5,%edi
  40011b:       e8 c8 ff ff ff          callq  4000e8 <foo>
  400120:       b8 00 00 00 00          mov    $0x0,%eax
  400125:       5d                      pop    %rbp
  400126:       c3                      retq

compile foo.c 跟 main.c 時 compiler 不知道 reference 到外部 symbol 的 address，在 instruction 中填入 0，link 才填入真正的 address。

foo.o 的 instruction 從

1
2
3
12:   89 05 00 00 00 00       mov    %eax,0x0(%rip)        # 18 <foo+0x18>
18:   48 c7 05 00 00 00 00    movq   $0x0,0x0(%rip)        # 23 <foo+0x23>
1f:   00 00 00 00

變成

1
2
3
4000fa:       89 05 94 00 20 00       mov    %eax,0x200094(%rip)        # 600194 <sum>
400100:       48 c7 05 7d 00 20 00    movq   $0x600194,0x20007d(%rip)        # 600188 <p.1749>
400107:       94 01 60 00

mov 使用相對定址 access sum (0x600194)，將下一個 instruction 的 address 0x400100 加上 0x200094 得到 sum 的 address，可從 symbol table 驗證。movq 使用絕對定址，由上 0x400107 可以看到 sum 的 address 直接寫進 instruction 了。之所以在 instruction 中數值看起來是反過來的，是因為 intel x86 CPU 使用 little-endian（Endianness wiki）。

main.o 則是

1
e:   e8 00 00 00 00          callq  13 <main+0x13>

變成

1
40011b:       e8 c8 ff ff ff          callq  4000e8 <foo>

callq 指令要 call foo()，其中 e8 是指令本身，ffffffc8 是 offset，以二的補數來看是十進位 -56，所以 0x400120 - 0x38 = 0x4000e8，就是 foo() 的 address 啦。

Ref

Posted on Edited on

這個 pattern 是用來建立一個 algorithm 的 template。在一個 method 中定義 algorithm 的骨架，其中的小步驟定義在 derived class。可以在不改變 algorithm 架構的狀況下改變其中某些步驟的做法。

UML

Template Method

template method 定義了 algorithm 的骨架，derived class 藉由 override 其中的步驟 function 改變 algorithm 的行為。

在 base class 中可以定義共用的 operation。有些 operation 在 algorithm 概念上是 derived class 一定要 implement 的，C++ 裡可用 pure virtual function。通常 base class 會有一份 hook 的 implement，derived class 可以選擇性 override hook，依據 hook 在 template method 裡的使用，override hook 可能影響 algorithm 的行為，例如做或不做某些步驟。

相關 pattern

Factory Method pattern 是 Template Method 的特殊版，用來生 object。

Strategy 跟 Template Method 都用來封裝 algorithm，不過不太一樣。Strategy 是各個 derived class 自己完整 implement algorithm，Template Method 則是先訂好一個 “template”，其中的步驟是可以被改變的。

應用

很多 UI framework，例如 Java 的 UI framework 跟 Qt，都有 paint() 之類的 painting function 以及 event handling function（例如處理 mouse event）就是使用 Template Method pattern。framework 已經決定何時會 call 這些 function，而 user 寫的 UI component 則依據需要 override 這些 function 決定實際上要做什麼事，如畫什麼東西、按滑鼠時要做什麼等等。

Posted on Edited on

Facade 定義較簡單（抽象程度更高）的 interface 來讓 client 更容易使用複雜的 sub system。

目的在簡化 sub system 的使用方式。

使用情境

sub system 提供很多功能與 interface 但太複雜，希望有簡單的方式使用 sub system。

UML

Facade Pattern

Facade 沒有封裝 sub system，只是提供簡化的 interface 方便使用。

client 可以用 Facade 的簡單 interface，也可以使用原本 sub system 提供的 interface。就像有些軟體在設定頁只放一般常用設定，需要調整細部設定的使用者再按「進階」鈕進入設定。

相關 pattern

Posted on Edited on

將一個 class 的 interface 轉換成另一個 interface 供其他人使用，讓原本不相容的 interface 可以相容。

一個轉接頭的概念。

使用情境

不想改其他使用 class A 的 code 卻想用 class B 達成相同功能時，以 Adapter 將 class B 的 interface 轉成 class A。

Adapter 因為受限 Adaptee 的能力，不一定能完美 implement interface 所提供的功能，這種時候通常用文件（就大家講好）或 exception 等等方式處理。之前一直以為 Adpater 要完全 implement interface 提供的功能，遇到受限的狀況就有點 confuse 這樣是不是 adpater…

UML

Adapter Pattern (合成)

Client 只知道 Target 的 interface，不知道 Adaptee 的 interface，Class 跟 Adaptee 之間是鬆綁的。如果需要同時使用兩種 interface，Adapater 也可以 implement 多個 Target interface，例如有 Target1 及 Target2 兩個 interface，有些地方原本使用 Target1，後來新寫的 code 使用 Target2，Adapter 同時支援兩者就可以不改動到原有的 code。

我比較習慣用合成讓 Adapter 使用 Adaptee，有另一種做法是用繼承，沒很懂這樣用的好處跟時機，先記著有這種方式：

Adapter Pattern (繼承)

跟其他 pattern 比較

  • Adapter 是做 interface 轉換。
  • Facade 是為了提供簡單的 interface 讓其他人易於操作 sub system，Adapter 跟 Facade 的差別在「目的」。
  • Decorator 是加功能。

Posted on Edited on

由 kernel 注意某些 fd 是否 active（readable、writable 及有 error），有則 return 讓 application process 對 active 的 fd 做相應的處理。用 select() 可避免 application process 去 polling 看各個 socket 是否 active、浪費 CPU 資源。如果沒有 fd active、沒設 timeout、沒有 signal 打斷，select() 是 blocking。

正常狀況下 select() return 三個 fdset 共有多少 fd active。timeout 時 return 0。收到 signal return -1 且 errno 設為 EINTR，不會測試 fd 也不會修改 fd_set，所以不能用 fd 判斷是否 active。select() 之所以在被 signal 打斷時不修改 fd_set，是為了避免 select() 跟 signal handler 不斷修改同一個 flag 造成 infinite loop。例如 select() 發現某 flag 是 0 會將 flag 設為 1，而某個 signal handler 遇到 flag 是 1 又把 flag 設為 0，沒完沒了。

pselect() 可設定擋住哪些 signal，讓這些 signal 不打斷 pselect()。

Sample Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <sys/types.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <cstring>
#include <cstdlib>
#include <errno.h>
#include <set>
#include <iostream>

#define MAXBUF 1000

using namespace std;

void run(int listenPort, int qlen);
int CreateListenSock(int listenPort, int qlen);

int main()
{
    run(8899, 5);
    return 0;
}

void run(int listenPort, int qlen)
{
    fd_set afdset, rfdset, wfdset, efdset;
    int listenfd = CreateListenSock(listenPort, qlen);
    int maxfd = listenfd;
    set<int> fds;
    bool bNeedWrite = false;

    FD_ZERO(&afdset); FD_ZERO(&rfdset); FD_ZERO(&wfdset); FD_ZERO(&efdset);
	FD_SET(listenfd, &afdset);

    fds.insert(listenfd);

    while (true)
    {
        int iActive = 0;
        struct timeval timeout;

        rfdset = afdset;
        efdset = afdset;

        if (bNeedWrite)
        {
            wfdset = afdset;
        }
        else
        {
            FD_ZERO(&wfdset);
        }

        timeout.tv_sec = 3;
		timeout.tv_usec = 0;
		
        if ((iActive = select(maxfd + 1, &rfdset, &wfdset, &efdset, &timeout)) == -1)
        {
            // handle error
            if (errno == EINTR)
            {
            }
            else
            {
            }
        }
        else
        {
            int iHandled = 0;
			set<int>::iterator fdIter = fds.begin();
            for (; fdIter != fds.end() && iHandled < iActive; ++fdIter)
            {
                int fd = *fdIter;

                if (FD_ISSET(fd, &rfdset))
                {
                    if (fd == listenfd)
                    {
                        // handle new connection
                        struct sockaddr_in cliaddr;
                        socklen_t cliaddrlen = sizeof(cliaddr);

                        bzero((char *)&cliaddr, sizeof(cliaddr));

                        int connfd = accept(listenfd, (struct sockaddr *)&cliaddr, &cliaddrlen);

                        fds.insert(connfd);
                        FD_SET(connfd, &afdset);
                        if (connfd > maxfd)
						{
							maxfd = connfd;
						}
                    }
                    else
                    {
                        // handle read
                        char readBuf[MAXBUF];
                        int iRead = 0;

                        bzero(readBuf, MAXBUF);

                        if ((iRead = read(fd, &readBuf, MAXBUF - 1)) > 0)
                        {
                            readBuf[iRead] = 0;
                        }
                        else if (iRead == 0)
                        {
                            close(fd);
                            FD_CLR(fd, &afdset);
                            fds.erase(fd);
                        }
                        else
                        {
                            // handle read error
                        }
                    }

                    iHandled++;
                }

                if (FD_ISSET(fd, &wfdset))
                {
                    // handle write
                    iHandled++;
                }

                if (FD_ISSET(fd, &efdset))
                {
                    // handle error
                    iHandled++;
                }
            }
        }
    }
}

int CreateListenSock(int listenPort, int qlen)
{
    struct sockaddr_in servAddr;
    int listenfd = -1;

    if ((listenfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) 
	{
        cerr << "Create socket failed" << endl;
        exit(1);
    }

    bzero((char *)&servAddr, sizeof(servAddr));
    servAddr.sin_family = AF_INET;
    servAddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servAddr.sin_port = htons(listenPort);

    if (bind(listenfd, (struct sockaddr *)&servAddr, sizeof(servAddr)) < 0) 
	{
        cerr << "Bind socket failed" << endl;
        exit(1);
    }

    listen(listenfd, qlen);

    return listenfd;
}