UBIFS 檔案系統分析1 - 磁盤結構【轉】

版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。

ubifs磁盤結構

UBIFS檔案系統把UBI volume劃分為六個部分，分别為

1. superblock area，使用LEB0

2. master area，使用LEB1和LEB2

3. log area，從LEB3開始，log area區的大小

4. LPT area，跟随在log area之後，LPT的大小在建立檔案系統時确定

5. orpan area，在log area和main area之間，使用固定數目的LEBs，一般來說，占用一個LEB足以

6. main area，最後一個area，存放檔案系統資料和index

Superblock area

占用一個LEB存儲superblock node，一般來說，superblock node儲存檔案系統很少變化的參數。superblock node僅僅占用LEB0的前4096個位元組。

superblock node磁盤資料結構如下：

/**

 * struct ubifs_sb_node - superblock node.

 * @ch: common header

 * @padding: reserved for future, zeroes

 * @key_hash: type of hash function used in keys

 * @key_fmt: format of the key

 * @flags: file-system flags (%UBIFS_FLG_BIGLPT, etc)

 * @min_io_size: minimal input/output unit size

 * @leb_size: logical eraseblock size in bytes

 * @leb_cnt: count of LEBs used by file-system

 * @max_leb_cnt: maximum count of LEBs used by file-system

 * @max_bud_bytes: maximum amount of data stored in buds

 * @log_lebs: log size in logical eraseblocks

 * @lpt_lebs: number of LEBs used for lprops table

 * @orph_lebs: number of LEBs used for recording orphans

 * @jhead_cnt: count of journal heads

 * @fanout: tree fanout (max. number of links per indexing node)

 * @lsave_cnt: number of LEB numbers in LPT's save table

 * @fmt_version: UBIFS on-flash format version

 * @default_compr: default compression algorithm (%UBIFS_COMPR_LZO, etc)

 * @padding1: reserved for future, zeroes

 * @rp_uid: reserve pool UID

 * @rp_gid: reserve pool GID

 * @rp_size: size of the reserved pool in bytes

 * @padding2: reserved for future, zeroes

 * @time_gran: time granularity in nanoseconds

 * @uuid: UUID generated when the file system image was created

 * @ro_compat_version: UBIFS R/O compatibility version

 */

struct ubifs_sb_node {

    struct ubifs_ch ch;

    __u8 padding[2];

    __u8 key_hash;

    __u8 key_fmt;

    __le32 flags;

    __le32 min_io_size;

    __le32 leb_size;

    __le32 leb_cnt;

    __le32 max_leb_cnt;

    __le64 max_bud_bytes;

    __le32 log_lebs;

    __le32 lpt_lebs;

    __le32 orph_lebs;

    __le32 jhead_cnt;

    __le32 fanout;

    __le32 lsave_cnt;

    __le32 fmt_version;

    __le16 default_compr;

    __u8 padding1[2];

    __le32 rp_uid;

    __le32 rp_gid;

    __le64 rp_size;

    __le32 time_gran;

    __u8 uuid[16];

    __le32 ro_compat_version;

    __u8 padding2[3968];

} __attribute__ ((packed));

@key_hash：檔案系統生成key的hash函數類型

@min_io_size：檔案系統最小讀寫單元

@leb_size：Logical erased block尺寸

@leb_cnt：檔案系統實際的leb count

@max_leb_cnt：檔案系統允許使用的最大leb count

@log_lebs：log area 占用的邏輯LEB數目

@lpt_lebs：lprops table占用的邏輯LEB數目

@orph_lebs：orphan area占用的邏輯LEB數目

@jhead_cnt：journal head記錄下一個節點寫到flash上的位置，UBIFS采用多線程journal來寫入兩種主要的heads：base head和data head．jhead_cnt記錄這個數目．

@fanout：ubifs檔案系統樹的最大扇出數．

@lsave_cnt：LPT save table中LEB Numbers的數目，LEB saved table用來在mount時加快查找LPT中空閑eraseblocks的速度．

@fmt_version：UBIFS on flash format version．

superblock幾乎不改變，隻有一種情況會導緻superblock

node被重寫，就是自動resize時。之是以需要自動resize，是因為建立ubifs檔案系統鏡像時，并不知道将要mount的UBI

bolume的大小，是以當我們将UBIFS鏡像安裝到UBI上時，UBI的尺寸可能實際上小于UBIFS鏡像所需要的最大空間，此時就需要把UBIFS

resize以适合UBI volume。

Master area

占用LEB1 LEB2．一般情況下，這兩個LEBs儲存着相同資料，master node尺寸為512 bytes，每次寫入master

node會順序的使用LEB的空閑page，直到沒有空閑page時，再從offset zero開始寫master

node，這時會重新unmapped LEBs為另一個erased LEB．

注意，master node不會同時unmapped兩個LEBs，因為這會導緻檔案系統沒有有效master node，如果此時掉電，系統無法找到有效master node．

master node磁盤資料結構如下

 * struct ubifs_mst_node - master node.

 * @highest_inum: highest inode number in the committed index

 * @cmt_no: commit number

 * @flags: various flags (%UBIFS_MST_DIRTY, etc)

 * @log_lnum: start of the log

 * @root_lnum: LEB number of the root indexing node

 * @root_offs: offset within @root_lnum

 * @root_len: root indexing node length

 * @gc_lnum: LEB reserved for garbage collection (%-1 value means the LEB was not reserved and should be reserved on mount)

 * @ihead_lnum: LEB number of index head

 * @ihead_offs: offset of index head

 * @index_size: size of index on flash

 * @total_free: total free space in bytes

 * @total_dirty: total dirty space in bytes

 * @total_used: total used space in bytes (includes only data LEBs)

 * @total_dead: total dead space in bytes (includes only data LEBs)

 * @total_dark: total dark space in bytes (includes only data LEBs)

 * @lpt_lnum: LEB number of LPT root nnode

 * @lpt_offs: offset of LPT root nnode

 * @nhead_lnum: LEB number of LPT head

 * @nhead_offs: offset of LPT head

 * @ltab_lnum: LEB number of LPT's own lprops table

 * @ltab_offs: offset of LPT's own lprops table

 * @lsave_lnum: LEB number of LPT's save table (big model only)

 * @lsave_offs: offset of LPT's save table (big model only)

 * @lscan_lnum: LEB number of last LPT scan

 * @empty_lebs: number of empty logical eraseblocks

 * @idx_lebs: number of indexing logical eraseblocks

struct ubifs_mst_node {

    __le64 highest_inum;

    __le64 cmt_no;

    __le32 log_lnum;

    __le32 root_lnum;

    __le32 root_offs;

    __le32 root_len;

    __le32 gc_lnum;

    __le32 ihead_lnum;

    __le32 ihead_offs;

    __le64 index_size;

    __le64 total_free;

    __le64 total_dirty;

    __le64 total_used;

    __le64 total_dead;

    __le64 total_dark;

    __le32 lpt_lnum;

    __le32 lpt_offs;

    __le32 nhead_lnum;

    __le32 nhead_offs;

    __le32 ltab_lnum;

    __le32 ltab_offs;

    __le32 lsave_lnum;

    __le32 lsave_offs;

    __le32 lscan_lnum;

    __le32 empty_lebs;

    __le32 idx_lebs;

    __u8 padding[344];

master node大小為512 byter，和superblock node padding 為4096是不同的，這樣可以更有效的利用master LEB．

@highest_inum: 目前系統最高的inode number，新建立的inode

number就是以這個作為基礎的，ubifs的inode number是不能複用的，也就是說已經使用過的inode

number，将不能再使用，這是基于ubifs檔案系統生命周期内，inode number不會超過0xffff0000這樣的假設

@cmt_no:

@flags:

@log_lnum:

@root_lnum: LEB number of the root indexing node

@root_offs: offset within @root_lnum

@root_len: root indexing node length

@gc_lnum: LEB reserved for garbage collection (%-1 value means the LEB was not reserved and should be reserved on mount)

@ihead_lnum: LEB number of index head

@ihead_offs: offset of index head

@index_size: size of index on flash

@total_free: total free space in bytes

@total_dirty: total dirty space in bytes

@total_used: total used space in bytes (includes only data LEBs)

@total_dead: total dead space in bytes (includes only data LEBs)

@total_dark: total dark space in bytes (includes only data LEBs)

@lpt_lnum: LEB number of LPT root nnode

@lpt_offs: offset of LPT root nnode

@nhead_lnum: LEB number of LPT head

@nhead_offs: offset of LPT head

@ltab_lnum: LEB number of LPT's own lprops table，ubifs假定ltab可以儲存在一個LEB内．

@ltab_offs: offset of LPT's own lprops table

@lsave_lnum: LEB number of LPT's save table (big model only)

@lsave_offs: offset of LPT's save table (big model only)

@lscan_lnum: LEB number of last LPT scan

@empty_lebs: number of empty logical eraseblocks

@idx_lebs: number of indexing logical eraseblocks

@leb_cnt: count of LEBs used by file-system

@padding: reserved for future, zeroes

log area

log 比較複雜，暫時掠過。

LPT area - LEB Properties Tree

LPT area 包含LEB Properties樹，LPT area eraseblock表(ltab)，以及saved LEB numbers表(lsave)．LPT在log area和orphan area之間．

LPT area的大小在檔案系統建立時就已經确定了，通過LEB 尺寸和檔案系統最大LEB count自動計算出LPT area占用的LEB數目。

LPT area類似一個小型的自包含檔案系統，它有自己的LEB properties，也就是LEB properties area的LEB

properties(ltab)．LPT area要求不能耗光自己的空間，能夠快速通路和update，以及算法上的可擴充性．LPT

properties tree是用wandering tree實作的，LPT area有自己的垃圾收集器。

LPT有兩種稍微不同的形式：small model和big model

在整個LEB properties table可以寫在一塊LEB上時，使用small

model，垃圾收集會寫整個表，是以使得所有其他的eraseblock都變得可用．而對于big model，垃圾收集僅僅選擇dirty

eraseblock，垃圾收集标記這個LEB上的clean node做為dirty，然後僅僅dirty

nodes被write-out．此外，在big model下，儲存empty LEB

number使得UBIFS在第一次mount時，不需要掃描整個LPT來擷取空的eraseblock。

main area内LEBs可以通過LEB properties三個值來辨別，這三個值分别為：

1. free space

空閑空間是一個eraseblock後面還沒有被寫的位元組數目

2. dirty space

是廢棄nodes和padding占據的位元組數，有可能被GC回收的部分．

3. 這個eraseblock是否為index eraseblock．

index nodes和non-index nodes是不可能放在同一個eraseblock中的，也就是說一個index eraseblock隻包含index nodes，而non-index eraseblock僅包含non-index nodes．

LPT磁盤結構

LPT樹儲存在LEBs中，包含兩種類型的節點: pnode和nnode，pnode是LPT的葉子節點，nnode是中間節點

pnode on-flash結構如下, n為pnode的扇出數：

| CRC | node type | pcnt | lprops-1 | lprops-2 | ... | lprops-n |

pcnt：記錄pnode number

nnode on-flash結構如下, n為nnode的扇出數

| CRC | node type | pcnt | nbranch-1 | nbranch-2 | ... | nbranch-n |

lprops on-flash結構

| free space | dirty space | flags |

flags辨別LEB是否包含index nodes

nbranch on-flash結構

| LEB number | LEB offs |

ltab - LEB properties of LEB properties area

| CRC | node type | ltab-1 | ltab-2 | ... | ltab-n |

UBIFS認為所有的ltab都儲存在一個擦除塊中（不知對于超大的ubifs檔案系統是否适用，也可能檔案系統的其他上限，確定了這個假設是正确的）

ltab-n on-flash結構

| free space | dirty space |

lsave - LPT save table, for quickly find empty eraseblock

| CRC | node type | lsave-1 | lsave-2 | ... | lsave-n |

orphan area

記錄已經删除的檔案的inode number．orphan area的意義在于删除過程unclean

unmount發生，已經删除的孤兒inodes必須被删除，這就要求掃描整個index來查找他們，或者在某處儲存一個清單，ubifs就是在orphan

area儲存這樣一個清單

main area

儲存檔案系統index node和non-index node

UBIFS包含幾種類型的non-index節點：file inode, directory entry，extend attribute entry和file data node

UBIFS維護着一棵wandering tree，葉子節點儲存着檔案資訊，他們是檔案系統的有效節點。樹的内部節點是index node儲存着到children的索引。是以wandering tree可以視為兩

個部分，頂部儲存樹結構的索引nodes，底部則是真正檔案資料的leaf node.

檔案inode node on-flash結構：

 * struct ubifs_ino_node - inode node.

 * @key: node key

 * @creat_sqnum: sequence number at time of creation

 * @size: inode size in bytes (amount of uncompressed data)

 * @atime_sec: access time seconds

 * @ctime_sec: creation time seconds

 * @mtime_sec: modification time seconds

 * @atime_nsec: access time nanoseconds

 * @ctime_nsec: creation time nanoseconds

 * @mtime_nsec: modification time nanoseconds

 * @nlink: number of hard links

 * @uid: owner ID

 * @gid: group ID

 * @mode: access flags

 * @flags: per-inode flags (%UBIFS_COMPR_FL, %UBIFS_SYNC_FL, etc)

 * @data_len: inode data length

 * @xattr_cnt: count of extended attributes this inode has

 * @xattr_size: summarized size of all extended attributes in bytes

 * @xattr_names: sum of lengths of all extended attribute names belonging to

 *               this inode

 * @compr_type: compression type used for this inode

 * @data: data attached to the inode

 *

 * Note, even though inode compression type is defined by @compr_type, some

 * nodes of this inode may be compressed with different compressor - this

 * happens if compression type is changed while the inode already has data

 * nodes. But @compr_type will be use for further writes to the inode.

 * Note, do not forget to amend 'zero_ino_node_unused()' function when changing

 * the padding fields.

struct ubifs_ino_node {

    __u8 key[UBIFS_MAX_KEY_LEN];

    __le64 creat_sqnum;

    __le64 size;

    __le64 atime_sec;

    __le64 ctime_sec;

    __le64 mtime_sec;

    __le32 atime_nsec;

    __le32 ctime_nsec;

    __le32 mtime_nsec;

    __le32 nlink;

    __le32 uid;

    __le32 gid;

    __le32 mode;

    __le32 data_len;

    __le32 xattr_cnt;

    __le32 xattr_size;

    __u8 padding1[4]; /* Watch 'zero_ino_node_unused()' if changing! */

    __le32 xattr_names;

    __le16 compr_type;

    __u8 padding2[26]; /* Watch 'zero_ino_node_unused()' if changing! */

    __u8 data[];

@size：檔案的資料長度（未壓縮前）

@data_len: inode data長度

@data:

磁盤inode節點附帶的資料，這個field對于不同類型的檔案，存儲不同的資料。對于REG檔案，可用來儲存xattr；對于SYMLINK，用來存儲符号連接配接；對于字元或者塊裝置>節點，用來存儲主從裝置号。注意ubifs

on-flash inode本身并沒有像ext2/ext3那樣，把普通檔案資料的索引資訊放在磁盤inode中。

既然無法通過ubifs_ino_node找到檔案資料的索引資訊，那麼ubifs是如何讀取一個檔案的資料的呢？這就是UBIFS的索引樹的作用，一個檔案的每一片資料，都是一個資料節點，>可以通過這片資料對應的key在ubifs

index樹中找到資料節點的具體位置。

目錄entry node on-flash結構：

 * struct ubifs_dent_node - directory entry node.

 * @inum: target inode number

 * @type: type of the target inode (%UBIFS_ITYPE_REG, %UBIFS_ITYPE_DIR, etc)

 * @nlen: name length

 * @name: zero-terminated name

 * Note, do not forget to amend 'zero_dent_node_unused()' function when

 * changing the padding fields.

struct ubifs_dent_node {

    __le64 inum;

    __u8 padding1;

    __u8 type;

    __le16 nlen;

    __u8 padding2[4]; /* Watch 'zero_dent_node_unused()' if changing! */

    __u8 name[];

@key: node key, | parent ino(32 bits) | key type(3 bits) | hash value(29 bits) |

@inum：目錄項對應檔案的inode number

@type: 目錄項對應檔案的類型

@nlen: 目錄項名稱的長度

@name: 目錄項名稱

ubifs目錄項看起來和其他檔案系統并沒有什麼差別，但是目錄項操作的實作卻比較獨特，這是因為UBIFS某個目錄下的目錄項并不是集中存放的，UBIFS使用index樹來管理目錄項>，目錄項的查找先通過key(由父inode

number + 目錄項名字hash來實作)在index樹查找，然後再比對路徑解決沖突問題。

UBIFS的readdir實作也很奇技淫巧，UBIFS首先找到key最小的目錄項，然後找到下一個，依次進行，周遊所有的目錄項。這個傳統檔案系統的readdir是完全不同的。

ubifs_readdir的注釋中也提到了ubifs使用directory entry hash value作為directory offsets，是以seekdir和telldir是無法正常工作的，當然，大多數情況下，這沒什麼問題

。

data node on-flash 結構

 * struct ubifs_data_node - data node.

 * @size: uncompressed data size in bytes

 * @compr_type: compression type (%UBIFS_COMPR_NONE, %UBIFS_COMPR_LZO, etc)

 * @data: data

 * Note, do not forget to amend 'zero_data_node_unused()' function when

struct ubifs_data_node {

    __le32 size;

    __u8 padding[2]; /* Watch 'zero_data_node_unused()' if changing! */

@key: | ino(32 bits) | key type(3 bits) | block number(29 bits) |

@size: 資料節點的未壓縮尺寸（真實資料尺寸是ch.len - sizeof(struct ubifs_data_node)）

@data: 壓縮的資料

ubifs_data_node是ubifs檔案資料的載體，ubifs不存在傳統檔案系統的資料索引，對資料的通路，需要首先生成待通路資料所對應節點的key，然後根據這個key到UBIFS wandering 樹中找到這個ubifs_data_node。

【新浪微網誌】 張昺華--sky

【twitter】 @sky2030_

【facebook】 張昺華 zhangbinghua

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利.