Newer New API 小註解

話說我們的 kernel 從 2.6.12 進版到 2.6.34 時, 網路速度似乎有點下滑. 為了瞭解這個進版對網路 driver 有什麼影響, 我發現了這個改良版的 New API – Newer New API.

原來的 New API [1] 是做啥的呢？ 它是為了避免 CPU 太忙所產生的處理方式.

早期網路 driver 在收到 packet 的時候, 都會發 IRQ （interrupt request）去通知 CPU 搬 data. 隨著網路的速度愈來愈快, CPU 漸漸就沒辦法做這麼瑣碎的雜事了. 假如一個 MTU 是 1500 Bytes, 那麼, 15 Mbps 的影片就會在每秒發出 15,000,000 / (1,500 x 8) = 10000 / 8 = 1250 個中斷. [2].

只要網路流量低, 那麼 IRQ 還是可以用. 一旦網路流量超過某個界限, CPU 就改用 Polling (輪詢) 的方式去撈 data. 這就是 NAPI 的基本觀念. 由於不是看到 packet 就發 IRQ, 把更多 data 留在 buffer 裡, 也可以減低 re-order 的機會. 萬一 CPU 根本處理不了那麼多 data, 新的資料會直接覆蓋掉舊的, 不會讓 CPU 到了來不及的最後關頭才丟棄資料 [1].

在這組 API 裡面, 支援了設定網卡工作模式 (IRQ or Pollng), 進入或退出工作模式的幾個 function call.

到了 Linux 2.6.24, NAPI 的名字仍然被沿用, 但是內容已經更新了.  主要的改變分為幾點:

1. NAPI 和 net_device 不再是一對一, 一個 network device 可以支援好幾個 port, 每個 port 根據自己忙碌的程度, 決定它在哪一種工作模式.

2. 註冊輪詢的 API 異動

void netif_rx_schedule(struct net_device *dev); 

→

void netif_napi_add(struct net_device *dev, struct napi_struct *napi,  int (*poll)(struct napi_struct *, int), int weight)

也就是說原來可以加入輪詢的 API 多了指定獨立資料結構的 struct napi_struct *napi, 輪詢方法的  int (*poll)(struct napi_struct *, int), 也把 weight 從 dev→weight 的資料結構中拔出來明確指定.

3. 輪詢的 prototype 也改了, 不再依據 device.

int (*poll)(struct net_device *dev, int *budget); 

→

int (*poll)(struct napi_struct *napi, int budget); 

4.  關閉輪詢功能的 API 當然也改了, 以前是關 net_device, 現在是關某個輪詢方法. 

__netif_rx_complete(dev)

→

void netif_rx_complete(struct net_device *dev,  struct napi_struct *napi); 

更細微的改動我就不列了. 我好奇的是, 如果 driver 是用舊的 NAPI 寫的, 直接拿到 2.6.24 以後的版本去用, 會不會註冊不了 polling function, 只好一直發 IRQ 而導致 performance 不好呢？還是根本編不過?

今天已經快睡著又變餓了, 明天再繼續研究這個問題. 

[後記]

看了 Wireless network 的 driver, 裡面果然都是用 tasklet.

[ref]

1. New API

2. Linux网络性能优化方法简析

3. Linux kernel 2.6.24 Porting 雜記.

4. NAPI 技术在 Linux 网络驱动上的应用和完善

WIFI Direct 連線小註解

WIFI Direct 是 WiFi 聯盟所提出的規格, 目的在於讓兩個無線裝置不透過 AP (access point) 就直接溝通. 或曰, 不是有 TDLS 嗎? WIFI 聯盟說了 [1]:

TDLS operates in the background of a Wi-Fi network to optimize performance, while Wi-Fi Direct-certified devices can quickly connect to one another while on the go, even when a Wi-Fi network is unavailable.  Many devices will be certified for both solutions and use them in different situations.

WIFI Direct 不需要 AP 仲介, 也不需要已經建立的網路.首先雙方以 discovery 發現對方.如果有一方講話有人在聽的話, 對話就成立了. 這就是 search-listen 組合, device 1 發出的 probe request 收到了 device 2 的 probe response 的回應.

此後 device 1 開始 formation, 送出 GO negotiation request, 等待 device 回應 GO negotiation response, 如果對方沒有進入 formation 的階段, request 會得到 fail 的結果. 若是能夠正常回應, 這樣就可以準備 GO 了嗎?! 非也, 這裡的 GO 並不是英文 go! go! go! 的那個 go, 而是 group owner 的縮寫.  Device 1 是 client, 而 device 2 是 group owner, 相當於一台 AP 的角色. 所以一個 GO 也可以有很多 clients.

那麼如何決定誰是那麼如何決定誰是 group owner 呢? 方法就是圖中的比大小. Device 1 在送出 request 的時候, 會附上 intent = 3.可惜 device 出的 intent = 3, 既然 10 > 3, 所以 device 2 就當 GO. 要是雙方不巧平手的話,就看雙方誰做莊? 做莊的那個會在 tie-breaker bit 註明, 這個值是隨機的.如果雙方都出王牌 (intent value >= 15), 搶著當 GO, 那麼連線就會失敗.

雙方角色確定之後, 還要有一個 GO negotiation confirm 才算完成 request / response / confirmation 三部曲.這是 Formation 中決定角色的完整步驟. 到了 Formation 的後段, P2P 的 device 要互相鑑別對方 (authentification), 然後 client 要發 association request 和獲得 association response, 這樣才和 GO 完成所有的 standard formation 的工作.

另外一種 formation 叫做 persistent.它可以把 group 中的成員記下來, 後續再連線時,可以直接邀請 (invite) 對方加入 group.Invitation 也分成 3 種, 就是 GO 請 device 加入變成 client, 或是 client 邀請 device 變成 group member (前兩者 invitation request frame = 0), 以及先前 persistent formation 的 GO (一定要有 GO) 和 client 重建當時的連線關係 (invitation request frame = 1).

Persistent invitation 的好處就是不需要複雜的認證,只是做 WSC (WIFI simple configuration). 而 GO 要負責在 invite response 時, 提供這一堆資訊:P2P Group BSSID, Channel List, Operating Channel and Configuration Timeout attributes to indicate the Group BSSID, potential Operating Channels, intended Operating Channel and any GO Configuration Time 讓連線快速恢復上次的狀態.

[ref]

1. http://www.wi-fi.org/knowledge-center/faq/what-difference-between-tdls-and-wi-fi-direct

2. http://www.hughes-systique.com/Portals/0/Uploads/Articles/WFD_Technology_Whitepaper_v_1.7635035318321315728.pdf

BogoMips 小註解

BogoMips 顧名思義是 Bogus 的 MIPS (Million Instructions Per Second). Bogus 表示 "偽".BogoMIPS 就是假的 MIPS.

一般常用的 DMIPS (Dhrystone MIPS) 主要是測量文書處理的表現. 如果要比較 CPU 是否夠快, 看主頻率 (clock) 也是不準的. 比方說 Intel i7 是 23.860 MIPS/MHz, ARM Cortex A8 僅有 2 MIPS/MHz [1], 所以 1GHz 的 i7 還是比 2GHz 的 A8 快很多! 

為什麼 MIPS 也會有假的呢? 原因是 BogoMips 本來就不是用來比較 CPU 的計算能力的, 它是用來調校 Linux kernel 的計時單位.

假如我要 delay 1 mini-second (ms),那麼在不借助特殊硬體的情況之下, 我怎麼知道多久是 1 ms 呢? 最簡單的方法, 就是做一個簡單的迴圈,再看看繞完 X 圈後, 花掉多少時間, 然後反推繞幾圈是 1ms. 這個每秒繞幾圈就是 loops_per_jiffy.

因此在 [ref 2] 中, 我們可以看到它介紹 delay loop 怎麼做? loops_by_jiffy 怎麼做? 卻沒講到關鍵的 “為什麼?", 這部份只得去看[3]的說明, 配合 [4] 的程式. 總之, BogoMips 直接就對應到 loops_per_jiffy.

在 calibrate.c [4] 裡面有印出 BogoMips 的地方.

/* Round the value and print it */ 

		printk("%lu.%02lu BogoMIPS (lpj=%lu)n",
			loops_per_jiffy/(500000/HZ),
			(loops_per_jiffy/(5000/HZ)) % 100,
			loops_per_jiffy);

那麼一個 jiffy 是多久呢? Linux 預設為 4ms,但其實可以調整為 1~10 ms, 這也是 Linux 一個 tick 所需要的時間.至於一圈 loop 是幾條指令? 這個也不一定, 在 Linux C code 裡面,會用一個迴圈取多次的值平均.

如果只看一次,可以簡化成: 

                pre_start = 0;
		read_current_timer(&start);
		start_jiffies = jiffies;
		while (jiffies <= (start_jiffies + 1)) {
			pre_start = start;
			read_current_timer(&start);
		}
		read_current_timer(&post_start);

		pre_end = 0;
		end = post_start;
		while (jiffies <=
		       (start_jiffies + 1 + DELAY_CALIBRATION_TICKS)) {
			pre_end = end;
			read_current_timer(&end);
		}
		read_current_timer(&post_end);

		tsc_rate_max = (post_end - pre_start) / DELAY_CALIBRATION_TICKS; // loops per jiffy

至於為何 start 和 end 都要有 pre_ 和 post_, 是為了抓到剛好跨過 jiffy 進 1 的點.

[ref]

1. MIPS (計算機)

2. BogoMIPS

3. What are BogoMips

4. calibrate.c

5. Jiffies

我讀 «發明炫點子»

這本書原來是 N 年前買給小孩看的, 希望她可以有所啟發. 不過, 她應該是連翻都沒有翻過吧? 我只好自己拿來看了.本書原名 “Whose Right Idea was it?", 作者是 Mr. Larry Verstrate, 譯者是黃咸弘先生. 

本書分為好幾個章節, 把同類的發明放在一起, 比方說吃的、影音的、玩具的、…等等. 不過基本上都是在介紹發明的背景, 讓我們更深入地看到那個小故事.比方說, 大家都知道便利貼是 3M 發明的, 西爾佛 (Spencer Silver)本來要製造超強黏性的膠 (1970 年), 結果超不黏的失敗之作反而意外變成暢銷品.

但深入這個故事後, 我們可以知道: 西爾佛的發明因為找不到用途而被擱置了. 1974 年, 他的同事佛萊 (Arthur Fly) 為了整理唱詩班的小紙片, 才想到西爾佛的發明可以用在 “黏性書籤". 即便如此,又過了 3 年, “便利貼" 才正式上市. 結果在兩個城市滯銷, 而在另外兩個城市熱銷.在熱銷的城市, 便利貼可以免費試用, 所以人們自己找到用途才去買. 而在滯銷的城市, 產品定位就是黏性書籤, 果然如大家預期的沒有人想要有黏性的書籤.

書中很多的發明家都擁有酷愛發明的天性, 擁有不只一項的發明, 像是發明大王愛迪生就有 1,093 項發明專利. 另外一位連小學都沒畢業的史賓賽 (Perct L. Spencer) 則有 120 項發明專利, 其中最重要的發明就是微波爐.史賓賽並不是因為熟讀 Maxwell’s Equation 而產生靈感, 而是因為他坐在雷達設備旁邊,結果口袋的巧克力融化了.基於這個發明, 他所服務的公司就賣起了微波爐.

至於發明的難度,可以說有天壤之別. 首先, 有不小心做出來就可以賣的. 像是史汀力 (Norman Stingley)發明回力球 (丟下去可以彈很高的球). 有些發明人是從大自然得到靈感的,像是蒙適多 (George de Mestral) 從刺果發明魔鬼氈.有些只是把某種東西重製, 例如葛利登 (Joseph F. Glidden) 發明鐵絲網時, 是參考農民把有刺灌木拿來圍住牲口的做法改良一下而已.

此外, 發明甜筒是因為盤子不夠 (漢威 – Ernest Hamwi)、發明聖代是冰淇淋不夠 (史密松 – Smithson), 完全是誤打誤撞.甚至於有時候發明是基於憤怒,洋芋片的發明是因為客人一直挑剔廚師喬治 (George Grum) 的薯條不夠薄脆也不鹹. 所以喬治火大想把客人鹹死, 於是端出超鹹焦炭薄片想給客人一個教訓, 誰知道大受歡迎.(所以大家不要再吃了,傷腎又傷心啊!)

當然,很多人是特意想要發明某種東西來解決問題,如果要解決的問題很小, 那麼發明也就簡單. 發明 OK 繃的艾爾 (Earl) 因為老婆是個差勁的廚娘, 自己上班的公司 (嬌生, 書上翻作強生)又在賣繃帶, 所以先做好一些 OK 繃在家備用. 後來公司同事看到這東西也很喜歡, 嬌生公司就開始賣起 OK 繃. 

不過也有多花費多年光陰才成功的例子, 例如發明 WD-40 防鏽潤滑劑就改變了 40 次配方.發明柯達相機的伊士曼 (George Eastman) 從發想到產品上市大約是 14 年. 周德森 (Whitcmb Judson) 為了發明拉鏈, 從 1893 年努力到 1912 年才建立基礎. 他的工人桑備克 (Gideon Sunback) 又改良了 4 年, 拉鍊才不會自動鬆開.而到了 1932 年, 這東西才開始大賣,並且獲得 Zipper 這個名字, 表示 “滋" (zip) 一聲就能拉上.

在悲情組的方面, 巴比吉 (Charles Babbage) 花了 37 年的時間 (1812~) 企圖發明機械式計算機 (也就是現在的電腦), 結果當然是失敗了. 但是他和他的數學家朋友艾達 (Augusta Ada Lovelace) 卻留下了名聲. Ada 也因為是第一個在計算機上用打孔卡片寫程式的人, 後來變成一種程式語言的名字.

總之, 有人發明致富, 有人只以低價賤賣專利權 (華特 – Walter Hunt, 安全別針, 400 USD),有人的發明只讓公司大賺 (派克豪斯 – Albert J. Parkhouse, 鐵絲衣架),有人的發明讓他離職開公司 (葛拉漢 – Bette Nesmith Graham, 立可白),還有人不屑申請專利而與財富無緣.幸好我們不是每個人都有發明的頭腦, 不需要太為這些事情傷腦筋.最後我用個小故事結尾,說明發明必須以市場結合.

金百利克拉克公司因為製造出的纖維素過剩, 因此推出一種卸妝用紙來消化庫存, 並命名為 “可麗舒".起初這個東西賣得不好, 即使大力促銷也賣不出去. 後來偶然間訂單突然增加, 並且源源不絕. 公司的行銷人員調查之後, 才發現人們並不是拿可麗舒來卸妝, 61% 的人因為它很便宜, 所以用來擤鼻涕. 於是金百利克拉克公司就改賣 “面紙", 並且宣傳 “不要把感冒留在口袋裡!", 從此銷量更是增加. So…

UltraViolet 小註解

UltraViolet (紫外光) 是一種可攜式的 DRM, 如果我買了一部正版的藍光 DVD, 難道我一定要用藍光播放機才能看? 在 iPad 上看就算盜版嗎？為了解決這個不合理的狀況, UltraViolet 技術應運而生.它是範圍更大的 DECE (Digital Entertainment Content Ecosystem)的主要部分 [3].

基本上, 我們可以把 UltraViolet 分成 3 個要件來理解, 第一個是 UltraViolet 的影片, 裡面會有 DRM License. 第二個是UltraViolet Player (播放機), 裡面有 domain ID. 最後則是 UltraViolet account (帳戶), 對應到他所擁有的全部影片 (digital collection). 一個帳戶可以擁有很多影片 (digital collection),  也可以擁有很多台播放機. 

當使用者購買一部影片的時候, 這部影片就被加到這個 UltraViolet 帳號的 digital collection. 當他把這部片子放在他的第一台機器上播放時,播放機裡面當然沒有這部片子的資料. 於是播放機要去 DSP (download service provider) server 找出這個帳戶是否擁有這部影片 (check if exist)? 如果有的話, 它就可以播放, 並且把這個播放機的 domain ID 記錄下來, 下次就不用再查 (check and play).

如果一個播放機上有多個帳戶, 第一次觀看的使用者就已經把 domain ID 加給 DRM license, 好像其他帳戶也可以觀看此片. 但是 domain ID 是依據帳戶區分, 透過 DRM client 所處理的 (the DRM client gets a domain ID corresponding to the account) [1], 所以其它帳戶無法分享這項權利. 不過, 一個帳戶可以有 6 個 member,頭號 member 還可以設定其它 member 的權限.比方說, 爸爸可以指定小孩不能看限制級. 

一個帳號又可以擁有 12 台播放機 (household account).假如合法的使用者把影片拷貝到他的另外一台播放機,基本上只是重複上述的步驟, 直到超過 12 次為止.如果還想增加新的播放機, 可以先取消一台舊的播放機. 拷貝到雲端硬碟也是合法的, 但是可能會限制同時同時連線的數量, 例如 3 個.

基本上, UltraViolet 只用雲端來管制是否合法授權, 而不是管制播放機是否被授權, 這是一個不同於已往的地方.(Digital locker: By creating a digital-rights locker rather than a digital media storage locker, UltraViolet bypasses the cost of storage and bandwidth used when the media is accessed and passes that cost on to various service providers.)[2].

那麼如果我買了一片 BD, 我可以把它拷貝到硬碟去播嗎? 不行! 使用者要到網路上註冊, 然後再下載可以拷貝的版本 (if you redeem an UltraViolet right that comes with a Blu-ray Disc or DVD you’ve purchased, or buy an UltraViolet movie or TV show online, those rights are stored in your UltraViolet Collection..)[1] 而非 Ultraviolet 的 DVD 有升級的機會, 但不一定能成立.

Ultraviolet下載的檔案名稱是 .uvu [1], 而格式是 CFF (common file format.)[2].雖然 .uvu 已經商業運轉了, 但是 CFF 的細節還沒有確定. 而且播放機都是 beta 版.

假如檔案是拷貝到一個未被授權的新帳戶, 那麼 UltraViolet 會有購買的提示. 如果下載就能合法地觀看/拷貝/分享, 提供使用者足夠的方便, 倒也不失為減少盜版的對策.

[ref]

1. UV-FAQ

2. WIKI – UltraViolet (system)

3. DECE (Digital Entertainment Content Ecosystem)