2008年7月30日 星期三

關於PCI的probing

.

PCI已經是一個被廣泛使用的bus了,很多的硬體都是PCI介面的,當然,現在更流行的是USB介面,如果我們要撰寫PCI bus上的硬體的driver,第一個要面對的問題是,怎麼確定我們的硬體是否存在PCI bus,以及如何去存取它

之前在看比較傳統的OS的driver,在PCI階段就遇到pci probing和configuration的問題,然而現在雖然linux都幫我們做掉了(是的,pci的部份linux都處理掉了,不需自己probe and get configuration,linux傳給你的struct pci_dev中已經有了它幫我們probe好的informatin),不過因為有看過,還是把它記下來吧

PCI的spec目前到2.2,可以抓下來參考,很多pci存取的細節都被定義在PCI的spec中

我著重在PCI的存取部份的介紹,所以若有看不懂的地方,那就必需去查詢PCI的spec了,PCI有define 64 bit的extension,但是在這裡我們只討論32bit的pci

PCI有自己的space,這個space一般稱為pci configuration space,這個space的address是32bit,每個PCI device佔有一塊固定大小64 dwords(256 byte)的空間,而在每個PCI device自己的空間中,其前面16 dwords(64 byte)的欄位都是一樣的,而存取這16個dwords的位址,其實就等於存取PCI device上對應的16個register,PCI device的資訊都存在這些register中

PCI的configuration register layout如下圖所示:



那麼我們就會面臨到兩個問題:
1.如何存取PCI configuration space?
2.每個device的位址為何? 不知道device的位址,我們就沒法存取

要存取PCI有兩種方式,一是透過IO port,另外一個是在得到memory mapped後的address後,就可以直接存取記憶體位址,利用memory mapped access了
但是在還沒獲得memory mapped的address之前,初始我們還是必需透過IO port存取
IO port的存取是間接存取,其必需透過c語言的in和out指令,讀取的時候,將我們要訪問的PCI configuration space中的address寫入(也就是in)0x0cf8這個port,然後就可以從port 0x0c00讀出(也就是out)結果,這種利用IO port的讀取我們先將其命名為IO port read

而在讀出BAR (base address register)這個register中的值後,我們就知道這個PCI device的configuration space被mapping到記憶體空間的哪裡,於是就可以像存取記憶體一樣去存取PCI device了


在知道如何存取PCI configuration space後,接下來的問題是,我們要如何從PCI configuration space中找到我們driver要support的device?

首先,PCI spec中提供了兩種configuration transaction,分別為Type 0和Type 1,Type 0和Type 1的差別可以看spec,而我們主要用到的是Type 1 configuration transaction

Type1 configuration時,其address layout如下圖所示:

所以我們要怎麼利用configuration transaction找出電腦上插了哪些PCI device,是否有我們driver support的PCI device?
很簡單,我們不可能知道該卡的bus number和device number,所以我們只能probe,也就是一個個掃過去,換句話說,就是數學上的窮舉
從bus number = 1 ~ 16 (一般電腦上通常只有一個bus),device number = 1 ~ 32,一個一個利用IO port read去讀出每個device空間上的第一組register,也就是PCI device的Vendor ID和Device ID

若該位址不存在PCI device,則IO port read讀出的值為0xffffffff
反之,該位址存在PCI device,則由於IO port read讀出的值包含Vendor ID和Device ID,如Intel的Vendor ID為0x8086,藉由比會Vendor ID、Device ID、Revision ID等值,很輕易的就能比對出probe到的這個PCI device是否為我們driver想要support的對像了
然後,讀出其BAR register的值,我們就能很輕易的存取該PCI device了

而在舊的OS中(如MS-DOS或pso中),這個動作要我們自己來做,而在linux中,很幸運的,linux都幫你做好了,於是你就可以將心力放在自己的driver上

.

白金牌鋼筆的奇怪現象

不得不說,白金(platinum)的鋼筆都很優秀,即使是在低價的鋼筆上也有一定的表現

到目前用過一些白金的鋼筆發現白金的鋼筆在較細的筆尖上有的會有一個奇怪的現象,那就是剛使用時會覺得很刮紙,然後會覺得天啊,怎會這樣難用………
然而再繼續堅持下去,大約在快寫完一管墨水時,會覺得豁然開朗,突然就不刮紙了,變好寫了目前手上有三隻筆都經歷過這個現象,分別是

日製3776 極細(EF)鋼尖日製3776
超極細(UEF)鋼尖
很久的白金18K WG(這隻是從台南同鄉筆閣網友cleanerdie兄讓給我的)

很神奇的,就在某一天起來,打開筆時,就突然覺得變好寫了

另外,由於UEF太細了,即使相對來說變滑順了,但還是稍微有點刮紙,不過我覺得這是天生的物理限制,避不了的,畢竟壓力等於力量/面積,而摩擦力又和壓力成正比,而筆尖越細,和紙的接觸面積就越小……以3776 UEF這麼細的筆尖來看,我覺得它的表現仍可以稱得上滑順

2008年7月18日 星期五

Kad的心得

前言
Kad是Kademlia的縮寫,Kad是一個廣泛被實做的DHT protocol,目前最流行的BT和eMule都實做了Kad
DHT的目的就是為了實現沒有server的目標(decentralized),更準確的說就是人人都是server,人人都是 client

理論上,p2p在實做Kad後,可以在沒有tracker (BT)或是server (eMule)的情況下,搜尋檔案或是找到抓同一個檔案的peer,在知道哪些peer在抓同一個檔案後,就可以開始p2p了,eMule和BT都是用udp實做Kad

Kad使用了xor (exclusive or)的方法去計算距離,需要注意的是,如果把Kad network視為overlay network,那麼Kad計算的是ovlay network上邏輯上的距離,而非真的實體距離

在暸解Kad之前,必需先暸解何為DHT(在BitTorrent的main line中,他只有DHT這個選項而沒有Kad這個選項,儘管他是Kad實作DHT)



我所理解的DHT
DHT是Distributed Hash Table的縮寫,在我的理解中,Table是一個2-column table,每一筆entry就是 pair,而DHT的行為大概接近如下,有檔案的檔腦將他的檔案hash之後得到key,而自己的電腦的IP就是value,再依照"特定的方法"指到一臺電腦將 pair存到他的電腦上,所有有同樣檔的人都會依照"特定的方法"找到"同一臺"電腦將 pair存到他的電腦上,而想要抓該檔案的人在有key的情況下,就可以找到"同一臺"電腦得到所有的 pair,由於value就是IP,因此他就知道哪些IP有這個檔案了,也就可以開始P2P了

在這個過程中,hash的value稱為key是因為,所有人只要有key就能找到同一臺電腦
在這我們稱該臺被找到的電腦為"負責人",所有有同一個檔案的人都可以得到同一把key,然後全都可以告訢該負責人"他們都有這個檔案",而所有要抓檔案的人只要有key都可以找到負責人問出"哪些人有這個檔案",所有key是關鍵,而key又是經由hash得到的,而對DHT而言,"如何依照特定的方法找到負責人"才是研究的人要關心的,Kad就是這樣的一個方法,而Kad的前輩chord,也是一個方法



我所理解的chord
Kad和chord很像,暸解了chord,你就知道Kad怎運作
在chord中,每一個node的IP就是本身的ID,chord把一個object(object可以為實體的檔案,如歌、電影、文件之類的,也可以為任何邏輯上的物件)投影(就是hash,但是我認為hash的邏輯上的意義就是投影)到和4Byte(32bit)IP相同的空間

我們令投影的結果,也就是hash value為key,而value就是有這個object的node的IP,所有的P2P中server負責的任務不過就是讓所以query的人知道有這個檔案的IP是哪些,於是他就可以跟這些IP交換這個檔案,而DHT就是把這個工均攤到所有人身上,換句話說,在將object hash得到key,而有這個object的電腦的IP的value,於是我們就會有一對 pair,在DHT中,擁有該檔案的人或正在抓該檔案的人將 store 到某個被找到的"負責人"身上

假設所有的IP都存在於chord network中(這裡不考慮private IP的3段range),那麼最理想的狀況是,所有的key都找得到人負責,而且是1-to-1 mapping(別忘了,key落在IP的space,而每個IP都存在),所以這時的狀況就很簡單,誰的IP等於該key,那麼誰就是該key的負責人

遺憾的是,這種事不會發生,大部份的情況下,擁有該key的IP的node都不存在,那麼怎麼辦?參考下圖,我們將32bit的space想像是一個有方向性的圓,而且是單方向性(uni-directional)的圓,IP過了(2^32-1)會wrap around回0,於是可以存在一個很簡單的邏輯,那就是若不存在IP == key的node,那麼就從key往下搜尋(也就是IP++,incremental),直到遇到的第一個活著的node,那麼他就是負責人,依照這個邏輯,publish和query都可以輕易的找到同一個負責人,大概就如下圖所示的方法

大致流程可以這樣想像
假設,有三臺電腦分別為a, b, c,他們都有一條歌叫hero.mp3,假設hero.mp3的hash value為x,也就是說hero.mp3的key = x,於是在a, b, c進入chord network時,他們必需做publish這個動作
publish指的就是告訴別人你有什麼檔案,也就是說,如果你有10個檔案要分享,那麼你必需將這三個檔案publish出去,將10個檔案的 pair儲存在對應的負責人身上

於是a, b, c會而用key x找到一個負責人y,然後a, b, c會將 pair,也就是、、 儲存到負責人y的table中
現在有一臺腦z想要抓hero.mp3這首歌,而z也算出hero.mp3的key = x,於是z利用x找到負責人y,y再將table中的3個entry傳回,於是z就知道a, b, c都有這首歌,也就可以跟他們抓了



Kademlia
Kadd的paper只有6頁,很短 ,paper的全名為Kademlia: A Peer-to-peer Information System Based on the XOR Metric

Kad的想法很簡單,就是找出利XOR計算出任二點在Kad network上邏輯的距離,有了這個距離後,一個key就讓距離該key最近的K個node負責,同理,query時也是同時query距離該key最近的K個node,k是一個系統參數

Kad的paper中,他把NodeID和Key的space定為160bit,並且強調你可以認為Kad中的node是用類似random的方式產生,實際上,每個人實做或多或少都會修改,比如eMule的Kad就是使用128bit的space實做,而非paper中的160bit

有了NodeID後,Kad利用對NodeID和key使用xor計算出距離,這是xor的特性能夠保證結果唯一,xor具備以下特徵
若令d(a, b) = a xor b,則
d(a, a) = 0
對任意b!=a,則d(a, b) = d(b, a) != 0
且xor也有類似三角形兩邊之合大於第三邊的特質
d(a, b) + d(b, c) > d(a, c)

所以在Kad中,每個進入Kad network的人都會有一個160bit的NodeID,而每個object經過hash也會得到一個160bit的key
然後每一個node和key的距離就等於 distance between node and key = d(NodeID, key),也就是NodeID xor key
然後,有檔案的人就把 pari存到距離key最近的k個node即可,也就是說找出k個和key distance最小的node,而要query的人就先找到離key最近的k個node,然後發出k個query,任何一個query有結果就可以p2p了,這樣可以達到parallel的效果以加速
整個Kad就像下圖所示





eMule的實做
eMule的Kad實做採用udp(BT也是),不同的是eMule是採用128bit(16Byte)的space,為什麼?
因為
1.eMule的NodeID剛好就是16Byte
2.eMule本來就是使用MD5來辨認file,而非檔名,而MD5 value剛好也是16Byte
於是一切就水到渠成,接下來Kad的實做就跟Kad的paper一樣了

但是由於eMule是對file content做MD5得到MD5 hash value(也就是key),這樣會有個問題,沒有該檔案或是完整檔案的人沒法算出MD5,沒有key,就不能找到負責人,也就無法抓檔,這一點,除了透過論譠的ed2k連結來解決之外(eMule的ed2k連結中包合了檔名,檔案大小,以及MD5等欄位),還有另一種解法,也就是keyword search

簡單的說,keyword search要用Kad找兩次,第一次利用keyword找出要抓的檔案的MD5 hash,第二次才是找出哪些人有檔案

舉例來說,如果有一臺電腦a有一首歌the power of love.mp3,它的MD5為x,那麼他必需publish兩次,一次是file hash的publish,也就是的publish,另一次則是將file hash關聯到keyword

以the power of love中,關鍵字(keyword)有兩個,也就是power和love,假設power和love一樣做hash(看高興用什麼就用什麼,也可以padding再MD5)得到兩個key,分別為y和z,那麼a就必需將file hash關聯到keyword的 pair publish到離y和z的k個node上,只不過publish的value為(file name, file hash),所以a會將和

於是今天我們想要抓the power of love這首歌,我們輸入the power of love給程式搜尋,程式判斷出keyword為power和love,同時算出key為y和z,做Kad query,離y和z最近的k臺電腦會傳回所有data,也就是file name和file hash的組合,程式再進行比對哪一組pair的file name等於the power of love,找到後就得到the power of love的file hash,有了file hash後於是就進入正常的kad流程了

keyword search中value必需包合file name是因為一個關鍵字會關聯到太多file name,所以必需再加入file name做篩選,比如說,power關鍵字可能還關聯到power supply,power point,power planet等相關檔名,而這些都會以power做關鍵字,所以value中才必需加入file name以做進一步的篩選

Kad的優缺點如下:
優點:
可平行處理
快速,paper 中證明只需要 (logn 取上高斯) + c 次就可找到,其中c是一個小的常數
缺點:
至少要認識一個Kad node才能進入Kad network,而該node就擔任bootstrap的角色
不平均的loading,雖然是達到把server的effort分散的效果,可是不保證loading是平均,舉例來說,若有人的NodeID剛好在某個熱門檔案的k個最近node的範圍內,那他的loading肯定會比某些只負責小檔案的node大很多

這是我present的ppt

2008年7月15日 星期二

關於"enable_irq unbalanced from"的錯誤訊息

在寫網卡的driver時需要用到enable_irq和disable_irq這兩個funtion

不過會遇到類似
enable_irq(12) unbalanced from c083f544
之類的message

查了一下發現是disable_irq和enable_irq的呼叫順序沒有正確配對所致
參考http://lists.freebsd.org/pipermail/aic7xxx/2000-March/003064.html

這個訊息是無害的,若有一個driver在沒任何device使用該irq時呼叫disable irq, 而且其已經是disabled的,於是該disable_irq就會被kernel給忽略
所以當我們call enable_irq時core kernel code就會認為其是unblanced的,但其實它不是(unblanced)

kernel panic時自動reboot

我是linux使用上很新的新手,雖然我正在寫linux的driver,不過寫程式本來就和os的使用熟練與否不需要正相關

還好我有一個對linux很熟的學弟,可以隨叫隨問

最近在寫網卡的driver,因為driver是在kernel space,所以只要任何一個地方寫錯就會造成kernel panic,於是開發平臺就要開開關關………

而每一次開機就要好久,除了因為linux本身開機就久之外,還因為我不是正常關機………

學弟教了我一個方法讓linux在kernel panic時自動重開

可以去設定/proc/sys/kernel/panic的值,預設是0,也就是不自動重開,若將其值設成3,如
echo 3 /proc/sys/kernel/panic
則機器會在kernel panic 3 秒後自動重開

但是學弟說此方法每次重開機都要重寫一次,於是又教了我一個永久設定該值的方法
去修改/etc/sysctl.conf,在最下面新增一行kernel.panic = 3
於是每次重開機後/proc/sys/kernel/panic的值都是3

從此以後,kernel panic後重開機的速度快了不少

另外,由於linux tty放久了會自動logout,即使用console login也是一樣,此時沒法判斷是kernel panic後自動重開,還是放久了自動logout,學弟又教了一招
uptime
會顯示開機後運行多久時間,格式是 時:分,也就是說,若顯示01:09,表示開機後到現在已經經過了1小時又9分鍾,這樣就可以判斷中間是否有發生過kernel panic了

2008年5月22日 星期四

Coolstreaming: Design, Theory, and Practice.ppt

這是李波在2005 infocom提出的coolstreaming system在加強後再撰寫的journal paper
這篇paper被刊登在2007 12月的IEEE Transaction on Multimedia
李波現在是香港科技大學的教授

他在2005提出的的coolstreaming是第一篇提出在p2p streaming system上使用data driven概念的paper,由於是第一篇,在這之後很多人都follow他的研究,講到topology,資工的人其實第一時間都會想到tree的架搆,但是tree根本就不適合用在p2p streaming,而data driven則打開了tree的桎梏,這種無序的topology就被命名為swarm,data driven說穿了不神奇,畢竟file based的p2p software如BT/eMule之類的就是data driven

現在的這篇journal paper則改進許多

他將peer定義成3種層次的關係,依序為member、partner、parent/child
一個client會收到固定大小的peer list並將其存到名單中,member是名單中的peer但沒有建TCP交換availability information,而partner就是有建TCP交換availability information的member,然後parent/child就是從partner中挑出來的,有真的傳出/收進sreaming data的peer了,所以顯然的,parent/child包含於partner,而partner又包含於member

他也觀察到原先pool based(BT like)的scheme無論是latency還是overhead都有點太大,latency會變長很直覺,而overhead則是per block的transmission都會有control message的overhead,畢竟每一個block都是要靠程式去拉回來的

可是若是改回push不就又變回tree的topology了嗎?於是他將stream分解成multiple substreams,分解的部份有點像是switch fabric的TDMA或是邏輯閘的Multiplexer,而接受的動作比較像是switch fabric的TDMA或是邏輯閘的DeMultiplexer

之後的一切改變都跟這個有關係了,於是一個stream就被分解成幾個substream,於是一個peer就變成他只需要決定跟哪一個peer要哪一個substream,而非要哪一個block,顯然的,第一,運算變簡單了,第二,control message變少了

他先將stream拆成固定大小的block,每個block都給個sequence number,由於是採用TCP,保證收到的block的順序是inorder的,所以顯然的,一個peer只需要告訴別人他substream的最新block的sequence number即可,於是有幾條substream,就只需要傳幾個sequence number,而用sequence number也比較好運算

他說他將本來的pure pull改進成hybrid pull and push scheme,我的理解是
一個peer (child)決定跟某個peer (parent)要哪個substream的動作是pull,因為是由要的人去跟人家拉回來的
而之後,被要的peer (parent)就一直將child要的substream主動送給他,這裡就是push了,這個部份就跟以前要一個block一個block去要差很多了

另外,他將選擇parent的權利留給child,所以一個parent從不obsolete一個child,而是由child來決定是否要obsolete一個parent
他引進了兩個threshold用來判斷是要obsolete一個parent,而這兩個threshold任何一個被違反那麼child就會決定obsolete他的parent,這兩個threshold分別是Ts和Tp
我的感覺是
Ts就是用來判斷child自己收到的substream的速度是否一致,所以Ts就是在child自己的substream之間比較
Tp就是用來判斷child的某個parnet是否落後其他partner太多的,所以Tp就是parent與自己的所有partner比較
在網路中最難判斷的就是一個peer的上傳頻寬是否足夠,他現在導入了這個機制雖然算出的是相對的結果,不過我覺得這個結果就夠用了,因為,網路的環境太過複雜,頻寬從來就不是固定值,所以不能夠被算出來,這種機制很適合實做的p2p streaming system參考

於是這個機制就可以讓這個p2p system變成self organized system,而self organized又是決定p2p system的scale的關鍵,因為self organized 就可以decentralized,而decentralized後p2p的scale才能變大

整個paper到這裡就差不多了,剩下的就是他證明他這樣設計的p2p overlay會是converge to stable
老實說這一段最關鍵的那個公式我看不懂,他說We can model peer adaptation by a continuous time branching process,很遺憾的,我不知道什麼是continuous time branching process,於是我就沒法理解為什麼他可以直接跳出那個結果,不過這並不防礙這是一篇優秀的實做的系統的paper的事實

後面的部份就是看圖說故事了,沒什麼

這篇paper值得一看

這是我present的ppt

百樂parallel pen

在看到牧師的LAMY與金豬一文後,首次得知了有此東西,下面是這隻筆的原廠原結
百樂原廠連結

剛好大舅子要從日本回來投票,就寫信請他帶一隻回來玩玩,我原本屬意2.4mm的,無奈太晚寫信,大舅子只找得到1.5mm的,要調貨需要一段時間,所以最後拿到的是1.5mm的
順便請大舅子帶一盒橘色的卡水回來,從帶回來的卡水紙盒顏色看,此筆銷路顯然不太好

帶回來的盒子裡有筆身一隻,黑色、紅色卡水各一管,吸墨器一隻,清潔片一塊,說明書一張

為什麼叫平行筆(parallel pen)?
我猜是因為它的筆尖是由兩片平行的鋼板夾起來的,所以才叫平行筆

這隻是平尖筆,可以用來寫西洋書法,附的書明書也有教你如何用這隻筆寫西洋書法,不過我本身買來是打算將它當做瑩光筆用


筆盒,紅黑卡水、吸墨器、清潔片 點圖放大
全部一覽點圖放大
筆尖正面 點圖放大
筆尖側面點圖放大
筆全身照,筆蓋是用轉的 點圖放大
說明書點圖放大
說明書:清潔片用法點圖放大
說明書:教你怎用此筆寫出漂亮字點圖放大
試寫點圖放大