自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

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

作者：蔣衛(wèi)峰 李濤
系統(tǒng) OpenHarmony
本文對目錄創(chuàng)建、目錄刪除和目錄移動操作進(jìn)行了分析，包括目錄操作的過程、操作之后目錄的鏈接方式變化、目錄操作中的一些特殊處理等內(nèi)容。

??想了解更多關(guān)于開源的內(nèi)容，請訪問：??

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

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

前言

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

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

一、目錄創(chuàng)建

1、commit過程

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

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

commit過程如下：

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)

2、鏈接方式變化

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

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)

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

用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
    |   // 存儲一個指向父目錄末尾目錄的塊指針
    |-> 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過程

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

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)


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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)

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

2、鏈接方式變化

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)


用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一個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目錄

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)

此時目錄B就成了orphan目錄。

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

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

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

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

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

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

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)

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

  1. 第一次commit前，標(biāo)記gstate為orphan狀態(tài)。這樣第一次commit時就可以記錄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，會記錄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)行檢查時被調(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)前目錄沒有父目錄，則當(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操作
            |   // 同時寫入MOVESTATE tag
            |-> lfs_dir_commit(lfs, dir, LFS_MKATTRS(
            |        {LFS_MKTAG(LFS_TYPE_TAIL + tail->split, 0x3ff, 8), tail->tail}));
    |   }
|   }

三、目錄移動

1、commit過程

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

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)

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

2、鏈接方式變化

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

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)存在一個文件或目錄，則將其刪除
    |   // 3.2 在新父目錄下創(chuà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. 在舊父目錄中刪除被移動目錄
    |-> lfs_dir_commit(lfs, &oldcwd, LFS_MKATTRS(
    |           {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(oldtag), 0), NULL})

4、move狀態(tài)

與目錄刪除過程中類似，在目錄移動的過程中，當(dāng)?shù)谝淮蝐ommit成功，但第二次commit因為掉電等原因未完成時，也產(chǎn)生一個中間狀態(tài)。例如，將目錄C從A移動到B：

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)

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

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

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

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

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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)


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

# littlefs原理分析#[四]目錄操作-開源基礎(chǔ)軟件社區(qū)


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

  1. 第一次commit前，標(biāo)記gstate為move狀態(tài)。這樣第一次commit時就可以記錄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. 在舊父目錄中刪除被移動目錄
    |-> 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)行檢查時被調(diào)用
lfs_fs_demove(lfs_t *lfs)
|-> ...
|
|   // 在新目錄中刪除被移動目錄的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é)

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

??想了解更多關(guān)于開源的內(nèi)容，請訪問：??

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

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

責(zé)任編輯：jianghua 來源： 51CTO開源基礎(chǔ)軟件社區(qū)
littlefs目錄操作
相關(guān)推薦

2022-11-07 15:27:07

LittlefsFetch操作

2022-11-15 09:24:16

littlefs文件讀寫

2022-10-27 16:07:24

littlefs存儲結(jié)構(gòu)

2022-11-22 15:21:55

littlefs磨損均衡

2022-11-02 15:56:45

littlefscommit機(jī)制

2009-02-27 08:56:30

IIS.Net原理分析

2021-07-12 10:25:03

RocketMQ數(shù)據(jù)結(jié)構(gòu)kafka

2011-08-18 09:46:40

活動目錄驗證原理

2011-05-31 13:12:15

Android 目錄結(jié)構(gòu)

2009-10-26 15:11:25

VB.NET多媒體編程

2018-04-27 10:59:30

Linux目錄結(jié)構(gòu)lib

2020-10-13 07:35:22

JUC - Count

2023-04-26 08:39:41

Bitmap元素存儲

2022-04-13 08:23:31

Golang并發(fā)

2021-10-12 17:19:17

Random局限性變量

2018-09-30 10:18:44

Linux 文件系統(tǒng)目錄

2010-07-15 14:01:10

Perl目錄句柄

2011-01-11 14:17:29

Linux文件目錄

2012-12-03 16:57:37

HDFS

2010-04-15 11:47:37

微軟活動目錄邏輯結(jié)構(gòu)
點贊
收藏

51CTO技術(shù)棧公眾號