littlefs原理分析--目錄操作（四）

作者：蔣衛峰李濤 2022-11-09 08:52:57

本文對目錄創建、目錄刪除和目錄移動操作進行了分析，包括目錄操作的過程、操作之后目錄的鏈接方式變化、目錄操作中的一些特殊處理等內容。

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

前言

前面的三篇文章中分別介紹了littlefs的整體結構、commit機制和fetch操作。在介紹了 littlefs中元數據的讀取和寫入過程之后，這篇以及接下來的文章將開始對littlefs中的具體文件、目錄操作和策略等進行介紹。

本文主要對目錄的創建、刪除和移動操作進行總結，包括目錄操作的過程、操作之后目錄的鏈接方式變化、目錄操作中的一些特殊處理等。目錄的讀取、寫入和遍歷操作實際上在前面的文章中以及介紹過了，目錄的讀寫實際上就是元數據的讀寫操作，目錄的遍歷實際上就是fetch tail的操作。

一、目錄創建

1、commit過程

目錄創建會進行兩次commit。第一次commit時，是在新創建的目錄元數據中插入指向父目錄中末尾目錄的塊指針；第二次commit時，是在父目錄元數據中插入新創建目錄的塊指針。

目錄創建的過程是原子性的，只有第二次commit完成，父目錄元數據中才會記錄新創建的目錄。

commit過程如下：

創建新目錄。其中，SOFTTAIL指向父目錄元數據中最后一個有效的SOFTTAIL，如果父目錄中沒有有效的SOFTTAIL，則SOFTTAIL為空。

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

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

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

2、鏈接方式變化

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

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

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

注：SOFTTAIL用箭頭進行鏈接，只有SOFTTAIL為目錄最后的TAIL時用實線表示。

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

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

3、相關函數分析

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. 在新目錄中進行commit
    |   // 存儲一個指向父目錄末尾目錄的塊指針
    |-> lfs_dir_commit(lfs, &dir, LFS_MKATTRS(
    |       {LFS_MKTAG(LFS_TYPE_SOFTTAIL, 0x3ff, 8), pred.tail}));
    |
    |   // 4. 在父目錄中進行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過程

目錄刪除的過程分為兩個步驟：

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

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

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

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

注：上圖的commit中還有一個MOVESTATE類型的tag，該tag與gstate和orphan目錄有關，見后面目錄刪除和移動操作中異常情況的分析。

2、鏈接方式變化

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

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

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

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

3、相關函數分析

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一個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. 斷開刪除目錄與前繼目錄的鏈接
    |-> lfs_dir_drop(lfs, &cwd, &dir.m);

4、orphan目錄

目錄刪除的過程時，有可能因為掉電等原因產生一個中間狀態，即第一次commit成功，而第二次commit失敗。例如，刪除目錄B，但只完成了第一步：

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

為了解決這個問題，littlefs中采用了gstate機制來進行異常狀態的記錄和檢查。

（1）gstate機制簡介

gstate是littlefs內存中維護的一組全局狀態，同時可作為MOVESTATE tag存儲于磁盤中。簡而言之，gstate機制通過如下方法記錄和檢查異常狀態：

當進行如目錄刪除這樣可能因掉電導致異常狀態的操作時，會將內存中維護的gstate在commit前標記為異常狀態。因為這樣可以使得commit過程中將異常狀態作為MOVESTATE tag寫入磁盤。（lfs_dir_commit函數會檢查內存中的gstate變量，并根據gstate增加寫入MOVESTATE tag）
當讀取磁盤元數據時，根據MOVESTATE tag中的信息，可以知道有無異常情況發生、異常情況是否解決等信息。這樣檢查到異常狀態后，就可以根據具體情況執行修復操作。
gstate檢查時是通過異或操作計算所有MOVESTATE tag中的值，結果不為0則表示異常。

（2）orphan狀態的記錄和修復

當進行目錄刪除操作時，磁盤中orphan狀態的記錄和修復步驟如下：

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

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

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

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

當進行目錄刪除操作時，內存gstate中orphan狀態的記錄和恢復步驟如下：

第一次commit前，標記gstate為orphan狀態。這樣第一次commit時就可以記錄MOVESTATE tag。
第一次commit后，還原gstate

記錄orphan狀態相關代碼分析如下：

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

修復orphan狀態相關代碼分析如下：

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

三、目錄移動

1、commit過程

littlefs中將目錄或文件從舊的父目錄移動到新的父目錄下主要經過兩個步驟：

在新父目錄中commit，創建目錄并指向將要移動的目錄。其中，如果新父目錄下已經存在一個同名的文件或目錄，需要先將其刪除。值得注意的是，與創建目錄時不同，這里父目錄下并沒有commit一個SOFTTAIL類型的tag。如下圖：

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

在舊父目錄中commit，刪除要移動的目錄。如下圖：

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

注：上圖的commit中還有一個MOVESTATE類型的tag，該tag與gstate和move狀態有關，見后面move狀態相關分析。

2、鏈接方式變化

在目錄的移動過程中，新父目錄中沒有commit一個新的SOFTTAIL，舊父目錄中也沒有commit一個新的SOFTTAIL覆蓋原來的SOFTTAIL。由于鏈接方式和遍歷順序只與TAIL類型的tag有關，因此目錄移動后，其鏈接方式并沒有變化，只是存儲結構發生了變化，遍歷時目錄的順序仍然不變。

3、相關函數分析

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. 在新父目錄中進行commit
    |   // 3.1 如果新路徑下已經存在一個文件或目錄，則將其刪除
    |   // 3.2 在新父目錄下創建將要移動的目錄
    |-> 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. 在舊父目錄中刪除被移動目錄
    |-> lfs_dir_commit(lfs, &oldcwd, LFS_MKATTRS(
    |           {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(oldtag), 0), NULL})

4、move狀態

與目錄刪除過程中類似，在目錄移動的過程中，當第一次commit成功，但第二次commit因為掉電等原因未完成時，也產生一個中間狀態。例如，將目錄C從A移動到B：

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

注：上圖中實線只表示存儲結構關系。

此時目錄B標記為move狀態。同樣的，move狀態也是通過gstate機制進行檢查和修復。

（1）move狀態的記錄和修復

當進行目錄移動操作時，與orphan狀態的記錄和恢復類似，磁盤中orphan狀態的記錄和修復步驟如下：

第一次commit，在新父目錄下創建目錄，此時記錄MOVESTATE tag于新父目錄的元數據中。存儲結構變化如下圖：

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

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

# littlefs原理分析#[四]目錄操作-開源基礎軟件社區

當進行目錄刪除操作時，內存gstate中move狀態的記錄和恢復步驟如下：

第一次commit前，標記gstate為move狀態。這樣第一次commit時就可以記錄MOVESTATE tag。
第一次commit后，還原gstate

記錄move狀態相關代碼分析如下：

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狀態到gstate
    |-> lfs_fs_prepmove(lfs, newoldid, oldcwd.pair);
    |
    |   // 2. 在新父目錄中進行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. 恢復gstate中的move狀態
    |-> lfs_fs_prepmove(lfs, 0x3ff, NULL);
    |
    |   // 4. 在舊父目錄中刪除被移動目錄
    |-> lfs_dir_commit(lfs, &oldcwd, LFS_MKATTRS(
    |           {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(oldtag), 0), NULL})

修復move狀態相關代碼分析如下：

// 該函數在mount后進行檢查時被調用
lfs_fs_demove(lfs_t *lfs)
|-> ...
|
|   // 在新目錄中刪除被移動目錄的id，并恢復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}));

總結

本文對目錄創建、目錄刪除和目錄移動操作進行了分析，包括目錄操作的過程、操作之后目錄的鏈接方式變化、目錄操作中的一些特殊處理等內容。接下來的文章將會介紹littlefs系統的文件相關操作。

??想了解更多關于開源的內容，請訪問：??

??51CTO 開源基礎軟件社區??

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

責任編輯：jianghua 來源： 51CTO開源基礎軟件社區

littlefs 目錄操作