??想了解更多關(guān)于開(kāi)源的內(nèi)容，請(qǐng)?jiān)L問(wèn)：??

??51CTO 開(kāi)源基礎(chǔ)軟件社區(qū)??

??https://ost.51cto.com??

前言

前面的三篇文章中分別介紹了littlefs的整體結(jié)構(gòu)、commit機(jī)制和fetch操作。在介紹了 littlefs中元數(shù)據(jù)的讀取和寫(xiě)入過(guò)程之后，這篇以及接下來(lái)的文章將開(kāi)始對(duì)littlefs中的具體文件、目錄操作和策略等進(jìn)行介紹。

本文主要對(duì)目錄的創(chuàng)建、刪除和移動(dòng)操作進(jìn)行總結(jié)，包括目錄操作的過(guò)程、操作之后目錄的鏈接方式變化、目錄操作中的一些特殊處理等。目錄的讀取、寫(xiě)入和遍歷操作實(shí)際上在前面的文章中以及介紹過(guò)了，目錄的讀寫(xiě)實(shí)際上就是元數(shù)據(jù)的讀寫(xiě)操作，目錄的遍歷實(shí)際上就是fetch tail的操作。

一、目錄創(chuàng)建

1、commit過(guò)程

目錄創(chuàng)建會(huì)進(jìn)行兩次commit。第一次commit時(shí)，是在新創(chuàng)建的目錄元數(shù)據(jù)中插入指向父目錄中末尾目錄的塊指針；第二次commit時(shí)，是在父目錄元數(shù)據(jù)中插入新創(chuàng)建目錄的塊指針。

目錄創(chuàng)建的過(guò)程是原子性的，只有第二次commit完成，父目錄元數(shù)據(jù)中才會(huì)記錄新創(chuàng)建的目錄。

commit過(guò)程如下：

1. 創(chuàng)建新目錄。其中，SOFTTAIL指向父目錄元數(shù)據(jù)中最后一個(gè)有效的SOFTTAIL，如果父目錄中沒(méi)有有效的SOFTTAIL，則SOFTTAIL為空。

2. 父目錄插入新目錄。其中，SOFTTAIL指向子目錄。

2、鏈接方式變化

創(chuàng)建目錄實(shí)際上是在parent->dir tail的單鏈表直接插入新目錄，變成parent->new dir->dir tail。

例如：向目錄C中創(chuàng)建目錄D，大致鏈接方式變化如下：

注：SOFTTAIL用箭頭進(jìn)行鏈接，只有SOFTTAIL為目錄最后的TAIL時(shí)用實(shí)線表示。

用fetch遍歷目錄順序的變化如下：

• 前：A->C->B
• 后：A->C->D->B

3、相關(guān)函數(shù)分析

lfs_mkdir(lfs_t *lfs, const char *path)
|-> lfs_rawmkdir(lfs_t *lfs, const char *path)
    |   // 1. 查找路徑和父目錄
    |-> lfs_dir_find(lfs, &cwd.m, &path, &id);
    |
    |   // 2. 分配新目錄
    |-> lfs_dir_alloc(lfs, &dir);
    |
    |   // 3. 在新目錄中進(jìn)行commit
    |   // 存儲(chǔ)一個(gè)指向父目錄末尾目錄的塊指針
    |-> lfs_dir_commit(lfs, &dir, LFS_MKATTRS(
    |       {LFS_MKTAG(LFS_TYPE_SOFTTAIL, 0x3ff, 8), pred.tail}));
    |
    |   // 4. 在父目錄中進(jìn)行commit
    |   // 將新目錄插入父目錄
    |-> lfs_dir_commit(lfs, &cwd.m, LFS_MKATTRS(
    |       {LFS_MKTAG(LFS_TYPE_CREATE, id, 0), NULL},
    |       {LFS_MKTAG(LFS_TYPE_DIR, id, nlen), path},
    |       {LFS_MKTAG(LFS_TYPE_DIRSTRUCT, id, 8), dir.pair},
    |       {LFS_MKTAG_IF(!cwd.m.split,
    |           LFS_TYPE_SOFTTAIL, 0x3ff, 8), dir.pair}));

二、目錄刪除

1、commit過(guò)程

目錄刪除的過(guò)程分為兩個(gè)步驟：

1. 在其父目錄中commit一個(gè)DELETE類型的tag，表示從父目錄中將目錄刪除。該步驟與文件刪除的過(guò)程類似。如下圖：

2. 在被刪除目錄的前繼目錄（其tail指向被刪除的目錄）中commit新的SOFTTAIL類型的tag，表示斷開(kāi)與將要?jiǎng)h除目錄的鏈接。新的SOFTTAIL指向被刪除目錄的后繼目錄（被刪除目錄tail指向的目錄）。如下圖：

注：上圖的commit中還有一個(gè)MOVESTATE類型的tag，該tag與gstate和orphan目錄有關(guān)，見(jiàn)后面目錄刪除和移動(dòng)操作中異常情況的分析。

2、鏈接方式變化

例如，刪除目錄B，其鏈接方式變化如下：

用fetch遍歷目錄順序的變化如下：

• 前：parent->C->B->A
• 后：parent->C->A

3、相關(guān)函數(shù)分析

lfs_remove(lfs_t *lfs, const char *path)
|-> lfs_rawremove(lfs_t *lfs, const char *path)
    |   // 1. 查找路徑和父目錄
    |-> lfs_dir_find(lfs, &cwd, &path, NULL);
    |
    |   // 2. 在父目錄中commit一個(gè)DELETE tag
    |-> lfs_dir_commit(lfs, &cwd, LFS_MKATTRS(
    |       {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(tag), 0), NULL}));
    |
    |   // 3. 找到刪除目錄的前繼目錄
    |-> lfs_fs_pred(lfs, dir.m.pair, &cwd);
    |
    |   // 4. 斷開(kāi)刪除目錄與前繼目錄的鏈接
    |-> lfs_dir_drop(lfs, &cwd, &dir.m);

4、orphan目錄

目錄刪除的過(guò)程時(shí)，有可能因?yàn)榈綦姷仍虍a(chǎn)生一個(gè)中間狀態(tài)，即第一次commit成功，而第二次commit失敗。例如，刪除目錄B，但只完成了第一步：

此時(shí)目錄B就成了orphan目錄。

為了解決這個(gè)問(wèn)題，littlefs中采用了gstate機(jī)制來(lái)進(jìn)行異常狀態(tài)的記錄和檢查。

（1）gstate機(jī)制簡(jiǎn)介

gstate是littlefs內(nèi)存中維護(hù)的一組全局狀態(tài)，同時(shí)可作為MOVESTATE tag存儲(chǔ)于磁盤(pán)中。簡(jiǎn)而言之，gstate機(jī)制通過(guò)如下方法記錄和檢查異常狀態(tài)：

• 當(dāng)進(jìn)行如目錄刪除這樣可能因掉電導(dǎo)致異常狀態(tài)的操作時(shí)，會(huì)將內(nèi)存中維護(hù)的gstate在commit前標(biāo)記為異常狀態(tài)。因?yàn)檫@樣可以使得commit過(guò)程中將異常狀態(tài)作為MOVESTATE tag寫(xiě)入磁盤(pán)。（lfs_dir_commit函數(shù)會(huì)檢查內(nèi)存中的gstate變量，并根據(jù)gstate增加寫(xiě)入MOVESTATE tag）
• 當(dāng)讀取磁盤(pán)元數(shù)據(jù)時(shí)，根據(jù)MOVESTATE tag中的信息，可以知道有無(wú)異常情況發(fā)生、異常情況是否解決等信息。這樣檢查到異常狀態(tài)后，就可以根據(jù)具體情況執(zhí)行修復(fù)操作。
  gstate檢查時(shí)是通過(guò)異或操作計(jì)算所有MOVESTATE tag中的值，結(jié)果不為0則表示異常。

（2）orphan狀態(tài)的記錄和修復(fù)

當(dāng)進(jìn)行目錄刪除操作時(shí)，磁盤(pán)中orphan狀態(tài)的記錄和修復(fù)步驟如下：

1. 第一次commit，從父目錄中將目錄刪除。此時(shí)記錄MOVESTATE tag于父目錄的元數(shù)據(jù)中。鏈接方式變化如下圖：

2. 第二次commit，這次即可能發(fā)生在第一次commit后，也可能是掉電后通過(guò)檢查gstate發(fā)現(xiàn)異常后的修復(fù)操作。此時(shí)記錄MOVESTATE tag于被刪除目錄的前繼目錄的元數(shù)據(jù)中。該MOVESTATE tag數(shù)據(jù)與在父目錄元數(shù)據(jù)中記錄的值相對(duì)應(yīng)，這樣gstate檢查時(shí)進(jìn)行異或計(jì)算就可與前面記錄的MOVESTATE tag進(jìn)行抵消，表示異常已解決。鏈接方式變化如下圖：

當(dāng)進(jìn)行目錄刪除操作時(shí)，內(nèi)存gstate中orphan狀態(tài)的記錄和恢復(fù)步驟如下：

1. 第一次commit前，標(biāo)記gstate為orphan狀態(tài)。這樣第一次commit時(shí)就可以記錄MOVESTATE tag。
2. 第一次commit后，還原gstate

記錄orphan狀態(tài)相關(guān)代碼分析如下：

lfs_remove(lfs_t *lfs, const char *path)
|-> lfs_rawremove(lfs_t *lfs, const char *path)
 |-> ...
 |
 |   // 在第一次commit前記錄gstate
 |-> lfs_fs_preporphans(lfs, +1);
 |
 |   // 第一次commit，會(huì)記錄MOVESTATE tag
 |-> lfs_dir_commit(lfs, &cwd, LFS_MKATTRS(
 |       {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(tag), 0), NULL}));
 |
 |   // 在第一次commit后恢復(fù)gstate
 |-> lfs_fs_preporphans(lfs, -1);
 |
 |-> ...

修復(fù)orphan狀態(tài)相關(guān)代碼分析如下：

// 該函數(shù)在mount后進(jìn)行檢查時(shí)被調(diào)用
lfs_fs_deorphan(lfs_t *lfs)
|   // 遍歷文件系統(tǒng)
|-> while (...) {
    |   // 1. 查找當(dāng)前orphan目錄的父目錄
    |-> lfs_stag_t tag = lfs_fs_parent(lfs, pdir.tail, &parent);
    |
    |   // 2. 如果當(dāng)前目錄沒(méi)有父目錄，則當(dāng)前目錄為orphan目錄，進(jìn)行恢復(fù)
    |-> if (tag == LFS_ERR_NOENT) {
    |       lfs_dir_drop(lfs, &pdir, &dir);
            |   // 2.1 檢查目錄中的異常狀態(tài)并記錄于gstate
            |-> lfs_dir_getgstate(lfs, tail, &lfs->gdelta);
            |
            |   // 2.2 commit新的TAIL類型tag，完成目錄刪除的第二次commit操作
            |   // 同時(shí)寫(xiě)入MOVESTATE tag
            |-> lfs_dir_commit(lfs, dir, LFS_MKATTRS(
            |        {LFS_MKTAG(LFS_TYPE_TAIL + tail->split, 0x3ff, 8), tail->tail}));
    |   }
|   }

三、目錄移動(dòng)

1、commit過(guò)程

littlefs中將目錄或文件從舊的父目錄移動(dòng)到新的父目錄下主要經(jīng)過(guò)兩個(gè)步驟：

1. 在新父目錄中commit，創(chuàng)建目錄并指向?qū)⒁苿?dòng)的目錄。其中，如果新父目錄下已經(jīng)存在一個(gè)同名的文件或目錄，需要先將其刪除。值得注意的是，與創(chuàng)建目錄時(shí)不同，這里父目錄下并沒(méi)有commit一個(gè)SOFTTAIL類型的tag。如下圖：

2. 在舊父目錄中commit，刪除要移動(dòng)的目錄。如下圖：

注：上圖的commit中還有一個(gè)MOVESTATE類型的tag，該tag與gstate和move狀態(tài)有關(guān)，見(jiàn)后面move狀態(tài)相關(guān)分析。

2、鏈接方式變化

在目錄的移動(dòng)過(guò)程中，新父目錄中沒(méi)有commit一個(gè)新的SOFTTAIL，舊父目錄中也沒(méi)有commit一個(gè)新的SOFTTAIL覆蓋原來(lái)的SOFTTAIL。由于鏈接方式和遍歷順序只與TAIL類型的tag有關(guān)，因此目錄移動(dòng)后，其鏈接方式并沒(méi)有變化，只是存儲(chǔ)結(jié)構(gòu)發(fā)生了變化，遍歷時(shí)目錄的順序仍然不變。

3、相關(guān)函數(shù)分析

lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath)
|-> lfs_rawrename(lfs_t *lfs, const char *oldpath, const char *newpath)
    |   // 1. 查找舊路徑和舊父目錄
    |-> lfs_stag_t oldtag = lfs_dir_find(lfs, &oldcwd, &oldpath, NULL);
    |
    |   // 2. 查找新路徑和新父目錄
    |-> lfs_stag_t prevtag = lfs_dir_find(lfs, &newcwd, &newpath, &newid);
    |
    |   // 3. 在新父目錄中進(jìn)行commit
    |   // 3.1 如果新路徑下已經(jīng)存在一個(gè)文件或目錄，則將其刪除
    |   // 3.2 在新父目錄下創(chuàng)建將要移動(dòng)的目錄
    |-> lfs_dir_commit(lfs, &newcwd, LFS_MKATTRS(
    |       {LFS_MKTAG_IF(prevtag != LFS_ERR_NOENT,
    |           LFS_TYPE_DELETE, newid, 0), NULL},
    |       {LFS_MKTAG(LFS_TYPE_CREATE, newid, 0), NULL},
    |       {LFS_MKTAG(lfs_tag_type3(oldtag), newid, strlen(newpath)), newpath},
    |       {LFS_MKTAG(LFS_FROM_MOVE, newid, lfs_tag_id(oldtag)), &oldcwd},
    |       {LFS_MKTAG_IF(samepair,
    |           LFS_TYPE_DELETE, newoldid, 0), NULL}));
    |
    |   // 4. 在舊父目錄中刪除被移動(dòng)目錄
    |-> lfs_dir_commit(lfs, &oldcwd, LFS_MKATTRS(
    |           {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(oldtag), 0), NULL})

4、move狀態(tài)

與目錄刪除過(guò)程中類似，在目錄移動(dòng)的過(guò)程中，當(dāng)?shù)谝淮蝐ommit成功，但第二次commit因?yàn)榈綦姷仍蛭赐瓿蓵r(shí)，也產(chǎn)生一個(gè)中間狀態(tài)。例如，將目錄C從A移動(dòng)到B：

注：上圖中實(shí)線只表示存儲(chǔ)結(jié)構(gòu)關(guān)系。

此時(shí)目錄B標(biāo)記為move狀態(tài)。同樣的，move狀態(tài)也是通過(guò)gstate機(jī)制進(jìn)行檢查和修復(fù)。

（1）move狀態(tài)的記錄和修復(fù)

當(dāng)進(jìn)行目錄移動(dòng)操作時(shí)，與orphan狀態(tài)的記錄和恢復(fù)類似，磁盤(pán)中orphan狀態(tài)的記錄和修復(fù)步驟如下：

1. 第一次commit，在新父目錄下創(chuàng)建目錄，此時(shí)記錄MOVESTATE tag于新父目錄的元數(shù)據(jù)中。存儲(chǔ)結(jié)構(gòu)變化如下圖：

2. 第二次commit，從舊父目錄中刪除目錄，此時(shí)記錄MOVESTATE tag于舊目錄的元數(shù)據(jù)中。類似的，這次即可能發(fā)生在第一次commit后，也可能是掉電后通過(guò)檢查gstate發(fā)現(xiàn)異常后的修復(fù)操作。鏈接方式變化如下圖：

當(dāng)進(jìn)行目錄刪除操作時(shí)，內(nèi)存gstate中move狀態(tài)的記錄和恢復(fù)步驟如下：

1. 第一次commit前，標(biāo)記gstate為move狀態(tài)。這樣第一次commit時(shí)就可以記錄MOVESTATE tag。
2. 第一次commit后，還原gstate

記錄move狀態(tài)相關(guān)代碼分析如下：

lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath)
|-> lfs_rawrename(lfs_t *lfs, const char *oldpath, const char *newpath)
    |-> ...
    |
    |   // 1. 在第一次commit前記錄move狀態(tài)到gstate
    |-> lfs_fs_prepmove(lfs, newoldid, oldcwd.pair);
    |
    |   // 2. 在新父目錄中進(jìn)行commit
    |-> lfs_dir_commit(lfs, &newcwd, LFS_MKATTRS(
    |       {LFS_MKTAG_IF(prevtag != LFS_ERR_NOENT,
    |           LFS_TYPE_DELETE, newid, 0), NULL},
    |       {LFS_MKTAG(LFS_TYPE_CREATE, newid, 0), NULL},
    |       {LFS_MKTAG(lfs_tag_type3(oldtag), newid, strlen(newpath)), newpath},
    |       {LFS_MKTAG(LFS_FROM_MOVE, newid, lfs_tag_id(oldtag)), &oldcwd},
    |       {LFS_MKTAG_IF(samepair,
    |           LFS_TYPE_DELETE, newoldid, 0), NULL}));
    |
    |   // 3. 恢復(fù)gstate中的move狀態(tài)
    |-> lfs_fs_prepmove(lfs, 0x3ff, NULL);
    |
    |   // 4. 在舊父目錄中刪除被移動(dòng)目錄
    |-> lfs_dir_commit(lfs, &oldcwd, LFS_MKATTRS(
    |           {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(oldtag), 0), NULL})

修復(fù)move狀態(tài)相關(guān)代碼分析如下：

// 該函數(shù)在mount后進(jìn)行檢查時(shí)被調(diào)用
lfs_fs_demove(lfs_t *lfs)
|-> ...
|
|   // 在新目錄中刪除被移動(dòng)目錄的id，并恢復(fù)gstate
|-> uint16_t moveid = lfs_tag_id(lfs->gdisk.tag);
|   lfs_fs_prepmove(lfs, 0x3ff, NULL);
|   lfs_dir_commit(lfs, &movedir, LFS_MKATTRS(
|           {LFS_MKTAG(LFS_TYPE_DELETE, moveid, 0), NULL}));

總結(jié)

本文對(duì)目錄創(chuàng)建、目錄刪除和目錄移動(dòng)操作進(jìn)行了分析，包括目錄操作的過(guò)程、操作之后目錄的鏈接方式變化、目錄操作中的一些特殊處理等內(nèi)容。接下來(lái)的文章將會(huì)介紹littlefs系統(tǒng)的文件相關(guān)操作。

??想了解更多關(guān)于開(kāi)源的內(nèi)容，請(qǐng)?jiān)L問(wèn)：??

??51CTO 開(kāi)源基礎(chǔ)軟件社區(qū)??

??https://ost.51cto.com??。