關於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這麼細的筆尖來看，我覺得它的表現仍可以稱得上滑順

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

關於"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了