[[397417]]

文章目錄

• UBI簡介
• flash存儲的內(nèi)容
• 代碼實(shí)現(xiàn)
  • 將flash數(shù)據(jù)讀到內(nèi)存
  • 組織數(shù)據(jù)結(jié)構(gòu)
• volume & EBA子系統(tǒng)初始化
• wear-leveling子系統(tǒng)初始化
• UBI層操作
  • 舉個例子
• 擦寫均衡
  • 擦寫時機(jī)
  • 擦寫條件

正文

UBI簡介

UBI全稱是Unsorted Block Images，上圖為UBI在系統(tǒng)中的層次結(jié)構(gòu)，最下面是flash層(包括flash控制器，各個flash驅(qū)動代碼，spi-mem層等);MTD層是對flash層的抽象，一個flash可能被劃分成不同的分區(qū)，每一個分區(qū)都會對應(yīng)一個MTD設(shè)備;UBI層是基于MTD層之上的更高層，UBI層抽象出一個個邏輯擦寫塊，每個邏輯擦寫塊都有一個物理擦寫塊與之前對應(yīng)，有了這個映射，我們就可以加一些軟件算法，達(dá)到擦寫均衡的目的，從而提高flash的使用壽命;再往上是基于UBI層實(shí)現(xiàn)和各種文件系統(tǒng)，比如UBIFS。

flash存儲的內(nèi)容

首先介紹幾個概念：

• PEB：physical eraseblocks 也就是對應(yīng)flash上的一個擦寫塊
• LEB：logical eraseblocks 軟件上的概念
• Volume：卷

如上圖為flash中(或者說flash一個分區(qū)中)數(shù)據(jù)組織結(jié)構(gòu)：

• ubi層對flash的管理是以擦寫塊為單位的，LEB對應(yīng)軟件上的概念，PEB對應(yīng)flash上一個實(shí)實(shí)在在的擦寫塊，每一個LEB對應(yīng)一個PEB。
• 往上看多個LEB可以組成一個volume，也就是說，可以根據(jù)不同的功能，將LEB劃分到不同的卷中;其中valume-layout是一個ubi內(nèi)部使用的卷，用來存放該MTD設(shè)備上所劃分的各個卷的信息，其包含兩個LEB，它們存儲的內(nèi)容是一樣，互為備份。
• 往下看每個PEB的內(nèi)容包含3部分ech(erase counter header)，vidh(volume identifier header)，data。下面會介紹具體含義。

代碼實(shí)現(xiàn)

linux對UBI層的代碼實(shí)現(xiàn)大致可以總結(jié)為3個方面：

首先數(shù)據(jù)是存儲在flash中的，因此需要將flash中的相關(guān)信息讀到內(nèi)存中，同時也可以檢查出flash中的壞塊

數(shù)據(jù)讀到內(nèi)存后，需要按照內(nèi)部的邏輯關(guān)系組織起來(比如將正在使用的PEB放到紅黑樹上管理起來，空閑的PEB也放到紅黑樹上管理起來)

在內(nèi)存中有了這些數(shù)據(jù)的關(guān)系后，就可以對其進(jìn)行操作(比如讀寫操作，volume增加，刪除，擴(kuò)容等操作，擦寫均衡操作)

將flash數(shù)據(jù)讀到內(nèi)存

UBI初始化時代碼調(diào)用流程如上圖，最終會調(diào)用scan_all() 函數(shù)， scan_all() 函數(shù)會遍歷該MTD設(shè)備

中的每一個PEB，從中讀出ech和vidh，它們的定義如下。

ech的定義如上，其中：

• ec：表示該P(yáng)EB被擦寫的次數(shù)，借助該字段我們就能夠找出被擦寫次數(shù)最少的PEB，從而達(dá)到擦寫均衡的目的
• vid_hdr_offset：表示vidh在該P(yáng)EB中的偏移位置
• data_offset：表示實(shí)際數(shù)據(jù)在該P(yáng)EB中的偏移位置

• vidh的定義如上，其中：
• vol_id：表示該P(yáng)EB屬于那一個volume

lmun：表示LEB在volume中的編號，該字段與PEB在MTD設(shè)備中的編號形成映射關(guān)系通過對MTD設(shè)備的每個PEB進(jìn)行遍歷，可以得知各個PEB的情況，或是被使用的，或是空閑狀態(tài)，或者已經(jīng)損壞，這些信息會被臨時記錄在struct ubi_attach_info 結(jié)構(gòu)中，遍歷過程中的具體細(xì)節(jié)，可以參考scan_all() 函數(shù)。

組織數(shù)據(jù)結(jié)構(gòu)

遍歷PEB后，會將flash信息保存在臨時的結(jié)構(gòu)struct ubi_attach_info 中，接下來會將struct ubi_attach_info 中的臨時信息保存到全局結(jié)構(gòu)struct ubi_device *ubi_devices 中，代碼如下：

分為三個步驟，分別是對volume的初始化，對wear-leveling子系統(tǒng)的初始化，對eba(Eraseblock Association)子系統(tǒng)的初始化;下面我們分別看下。

volume & EBA子系統(tǒng)初始化

前面有介紹到volume-layout是UBI內(nèi)部使用的一個卷，其包含兩個LEB(互為備份)，對應(yīng)PEB中的數(shù)據(jù)內(nèi)容如上圖，data(灰色)部分是一個struct ubi_vtbl_record 結(jié)構(gòu)數(shù)組，記錄了當(dāng)前UBI設(shè)備所有卷的信息， ubi_read_volume_table() 函數(shù)先遍歷臨時結(jié)構(gòu)struct ubi_attach_info 找出volumelayout所在PEB，然后 讀出struct ubi_vtbl_record 結(jié)構(gòu)數(shù)組并保存到內(nèi)存中，也就是struct ubi_device 的struct ubi_volume *volumes[] 字段中，初始化后的數(shù)組結(jié)構(gòu)如下圖，其中struct ubi_volume *volumes[] 是一個指針數(shù)組，數(shù)組中的每一個元素都是struct ubi_volume 結(jié)構(gòu)(詳細(xì)過程見ubi_read_volume_table() 函數(shù))。

在struct ubi_volume 結(jié)構(gòu)體中，有一個比較重要的字段struct ubi_eba_table *eba_tbl ，該字段記錄了當(dāng)前volume中所有LEB與PEB的映射關(guān)系，其中struct ubi_eba_entry *entries 是一個數(shù)組結(jié)構(gòu)，每一個元素對應(yīng)一個struct ubi_eba_table 結(jié)構(gòu)體， struct ubi_eba_entry *entries 數(shù)

組的下標(biāo)對應(yīng)于LEB的編號，數(shù)組元素的內(nèi)容對應(yīng)EB的編號，這樣就將LEB與PEB關(guān)聯(lián)起來了(詳細(xì)過程見ubi_eba_init() 函數(shù))。

wear-leveling子系統(tǒng)初始化

在UBI中將PEB分為4種情況，正在使用、空閑狀態(tài)、需要擦除、已經(jīng)損壞，各個狀態(tài)的PEB被放到不同的紅黑樹中管理。在ubi_eba_init() 函數(shù)中，會先分配一個struct ubi_wl_entry 指針數(shù)組并存儲在sruct ubi_wl_entry **lookuptbl 字段中，數(shù)組下標(biāo)為PEB的編號，數(shù)組內(nèi)容記錄了PEB的擦寫次

數(shù)與編號信息，每一個PEB都有一個這樣的結(jié)構(gòu)與之對應(yīng)如下圖。

另外各個PEB還根據(jù)狀態(tài)放到不同的紅黑樹管理起來，上圖畫出了used, free, scrub三種狀態(tài)的紅黑樹，其中紅黑樹是以擦寫次數(shù)為順序排列的，最小的擦寫次數(shù)排列在最左邊，如果擦寫次數(shù)相同，則比較PEB的編號，編號小的排在樹的左邊，而對應(yīng)的值為struct ubi_wl_entry 指針數(shù)組中的一個元素。

調(diào)用ubi_eba_init() 函數(shù)后，wear-leveling子系統(tǒng)也就初始化完畢，在內(nèi)存中會形成上圖中的數(shù)組關(guān)系。

UBI層操作

經(jīng)過前面的初始化，各個數(shù)據(jù)的結(jié)構(gòu)關(guān)系已經(jīng)保存在內(nèi)存中了，因此UBI層的操作其實(shí)就是對內(nèi)存中這些數(shù)據(jù)的操作。

從用戶空間角度看，UBI初始化后會對應(yīng)三類字符設(shè)備，分別為/dev/ubi_ctrl 、/dev/ubix (x = 0, 1, 2...)， /dev/ubix_y (x = 0, 1, 2..., y = 0, 1, 2)，它們對應(yīng)的操作函數(shù)如下代碼。

• ubi_vol_cdev_operations：是針對某個volume(/dev/ubi1_0等)來操作的，從volume的角度只能看到其中包含的PEB，因此它的操作也是圍繞PEB進(jìn)行的。
• ubi_cdev_operations：是針對UBI設(shè)備(/deb/ubi0等)進(jìn)行操作的，從UBI設(shè)備的角度可以看到不同的volume，因此可以對volume進(jìn)行創(chuàng)建，刪除，擴(kuò)容等操作。
• ubi_ctrl_cdev_operations：是針對UBI層(/dev/ubi_ctrl)的操作，從該角度可以看到UBI設(shè)備，因此可以對UBI設(shè)備進(jìn)行創(chuàng)建，刪除操作。

舉個例子

需求：假如我們想要對/dev/ubi1_0 這個volume進(jìn)行擴(kuò)容，我們應(yīng)用怎樣操作?

用戶空間將volume_id，size兩個參數(shù)傳遞到內(nèi)核空間

在內(nèi)核空間我們根據(jù)volume_id在struct ubi_volume *volumes[] 數(shù)組中找到volume的handler

因?yàn)樾枰獢U(kuò)容(要分配更多的LEB)，所以要重新分配struct ubi_eba_table *eba_tbl 數(shù)組，并將舊數(shù)組中的數(shù)據(jù)拷貝到新數(shù)組中

對于新增的LEB，我們需要從free樹上申請，建立LEB到PEB的映射關(guān)系并保存到struct ubi_eba_table *eba_tbl 數(shù)組，另外還需要更新PEB中ech和vidh，表明該P(yáng)EB屬于那個volume

上面這一系列操作是我自己的想法，并非kernel實(shí)現(xiàn)代碼(具體實(shí)現(xiàn)可以參數(shù)ubi_cdev_ioctl() 函數(shù))。這里想表達(dá)的意思是，在UBI初始化完成后，在內(nèi)存中已經(jīng)存在了各個volume，各個LEB/PEB之間的關(guān)系，因此對于UBI的操作，理論上我們是都可以完成的，所差的只是代碼實(shí)現(xiàn);程序=算法+數(shù)組結(jié)構(gòu)，這里的數(shù)組結(jié)構(gòu)已經(jīng)有了，而算法就是UBI層的各種操作，這里的代碼其實(shí)每個人都可以實(shí)現(xiàn)的，只不過有好有壞，所幸kernel已經(jīng)幫我們實(shí)現(xiàn)了，我們可以參考學(xué)習(xí)。其實(shí)別人寫的文章只能提供個大概，真正的細(xì)節(jié)只有在源碼中才能獲得。

擦寫均衡

flash的擦寫塊都是有壽命限制的，如果頻繁的擦寫flash的某一個PEB，很快這個PEB就會損壞，而擦寫均衡的目的就是將擦除操作平均分配到整個flash，這樣就能提高flash的使用壽命。那怎樣將擦除操作平均分配到整個flash呢，要達(dá)到這個條件還是有些難度的，因此我們退一步，將條件修改為PEB的最大擦寫次數(shù)與最小次數(shù)的的差值小于某個值。

比如flash中包含20個PEB，其中數(shù)字表示該P(yáng)EB被擦寫的次數(shù)，我們約定擦寫次數(shù)的差值最大為15，現(xiàn)在flash中PEB的最小與最大擦寫次數(shù)分別為10、39，由于超過門限值，因此需要我們想一些方法，增加擦寫次數(shù)為10的PEB被擦寫的機(jī)會，減少擦寫次數(shù)為39的PEB被擦寫的機(jī)會，從而使整個flash的擦寫次數(shù)趨于平均。具體的實(shí)現(xiàn)后面會介紹。

擦寫時機(jī)

linux kernel會在下面兩個位置調(diào)用擦寫均衡：

• wear-leveling子系統(tǒng)初始化完成時會檢查一次是否需要擦寫均衡，此時是一個初始狀態(tài)，是檢查的一個時機(jī)。
• 當(dāng)要擦除某個PEB的時候，此時擦寫次數(shù)會增加，有可能達(dá)到擦寫均衡的要求，此時也是一個檢查的時機(jī)。

擦寫條件

除了上面的調(diào)用時機(jī)，擦寫均衡還有一些其它的條件限制，如下圖為擦寫均衡的流程圖：

• 當(dāng)scrub紅黑樹上有節(jié)點(diǎn)時，一定需要進(jìn)行擦寫均衡。在遍歷flash的每個PEB時，如果發(fā)現(xiàn)在從flash中讀出的數(shù)據(jù)有位翻轉(zhuǎn)的情況，就會加上scrub標(biāo)志，并放到scrub紅黑樹上維護(hù)起來，表示該P(yáng)EB需要被擦寫;在擦寫均衡時，先取出scrub樹最左邊節(jié)點(diǎn)e1，再從free樹中找一個合適的節(jié)點(diǎn)e2，然后讀取e1對應(yīng)PEB的數(shù)據(jù)，如果讀取的數(shù)據(jù)還有問題，就會結(jié)束本次擦寫;如果沒有問題就會把e1數(shù)據(jù)copy到e2位置，并擦除e1數(shù)據(jù)完成本次擦寫均衡操作。
• 當(dāng)scrub樹上沒有節(jié)點(diǎn)時，會從used樹上取出最左邊節(jié)點(diǎn)e1，并從free樹上找一個合適的節(jié)點(diǎn)e2，然后檢查e2與e1的PEB擦寫次數(shù)的差值是否大于門限值，如果大于，則將e1數(shù)據(jù)copy到e2位置并擦除e1數(shù)據(jù)完成本次擦寫。為什么這樣做，原因是used樹中的節(jié)點(diǎn)已經(jīng)被初始化過(先整個擦除，然后寫入ech和vidh，后面再寫入數(shù)據(jù)也不需要擦寫)所以不會有擦除操作，在free樹上的節(jié)點(diǎn)，在被使用前需要擦除一次，所以把擦寫次數(shù)大的PEB放到used樹上減少被擦寫的機(jī)會，把擦寫次數(shù)小的節(jié)點(diǎn)放到free樹上增加被擦寫的機(jī)會，這樣就達(dá)到了擦寫均衡的目的。
• 另外在free樹上選擇一個合適的節(jié)點(diǎn)，什么是適合和節(jié)點(diǎn)?最簡單的方法就是從free樹的最右邊拿一上節(jié)點(diǎn)(擦寫次數(shù)最大的節(jié)點(diǎn))，然后與used樹上取下的最左邊的節(jié)點(diǎn)比較，看看差值是否超過門限值。但實(shí)際情況可能會更復(fù)雜些，如下代碼29行，是kernel中在free樹上選擇節(jié)點(diǎn)的方法，其限制了最大擦寫次數(shù)為free樹最左側(cè)節(jié)點(diǎn) + WL_FREE_MAX_DIFF，看上面的注釋說在某些情況下會出現(xiàn)不斷擦寫某一個或幾個PEB的情況，所以作了這樣一個限制。(沒有想道是什么情況??)

如果你覺得你現(xiàn)在走得辛苦，那就證明你在走上坡路。

尹忠凱, Linux內(nèi)核愛好者，2017年6月本科畢業(yè)杭州電子科技大學(xué)。

現(xiàn)在就職于北京地平線信息技術(shù)有限公司，任系統(tǒng)軟件工程師，主要負(fù)責(zé)SPI, I2C, OSPI, DMA等模塊bring up與調(diào)試工作

 本文轉(zhuǎn)載自微信公眾號「Linux閱碼場」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系Linux閱碼場公眾號。