??想了解更多關于開源的內容，請訪問：??
??51CTO 開源基礎軟件社區(qū)??
??https://ost.51cto.com??
前言
前面的littlefs原理分析文章中，第一篇介紹了littlefs的整體結構，第二篇介紹了littlefs中記錄元數(shù)據(jù)的方式，即commit機制。這一篇（littlefs原理分析：（3）fetch操作）的主要內容是介紹littlefs中的fetch操作，這部分還是與元數(shù)據(jù)有關，不過commit過程是寫入元數(shù)據(jù)，fetch操作是讀取元數(shù)據(jù)。
commit時記錄了如超級塊、文件、目錄的創(chuàng)建、刪除等操作。而如何去從這些記錄中獲取所需的信息（如打開文件時需要從其父目錄的元數(shù)據(jù)中獲取文件的塊指針），則是通過對元數(shù)據(jù)中tag的遍歷來完成。
fetch操作實際上就是對元數(shù)據(jù)中tag的遍歷，其功能是遍歷指定NAME類型的tag，如查找文件、目錄等，獲取文件、目錄id等數(shù)據(jù)。commit過程中寫入tag時也是通過tag的遍歷來完成的，不同的是fetch操作一般只用于讀取commit中記錄的數(shù)據(jù)，而commit過程中調用的lfs_dir_traverse函數(shù)一般只用于寫入。
一、fetch作用說明
fetch操作在littlefs中主要用于文件和目錄的讀取，和目錄的遍歷。
下面結合具體的文件、目錄操作，對其相應的commit過程、以及commit之后如何結合fetch操作獲取相應數(shù)據(jù)，進行說明：
1、文件和目錄的讀取
在已知父目錄的元數(shù)據(jù)塊的情況下，文件和目錄的讀取可以分為以下兩個步驟：
- 遍歷查找到REG（DIR）類型的tag，獲取文件（目錄）名和文件（目錄）id
- 根據(jù)文件（目錄）id再次遍歷tag找到相應數(shù)據(jù)tag，即INLINESTRUCT或CTZSTRUCT（DIRSTRUCT）
fetch操作完成了第一步，以下結合具體案例對fetch過程進行說明：
（1）文件創(chuàng)建后
文件剛創(chuàng)建時為inline文件：
![#littlefs原理分析#[三]fetch操作-開源基礎軟件社區(qū)](https://dl-harmonyos.51cto.com/images/202211/c2d714e563d0c86bed9118b34b2949db10dc21.png?x-oss-process=image/resize,w_471,h_229 "#littlefs原理分析#[三]fetch操作-開源基礎軟件社區(qū)")
此時遍歷查找到與文件路徑匹配的REG類型的tag，就能夠獲取文件名和文件id、再通過其文件id再次遍歷tag就能夠獲取文件的數(shù)據(jù)。
如打開剛創(chuàng)建的文件：
lfs_file_rawopencfg(lfs_t *lfs, lfs_file_t *file,
| const char *path, int flags,
| const struct lfs_file_config *cfg)
| // 1. 根據(jù)路徑查找對應tag和id
| // 此時查找的為REG類型的tag，查找到的文件id存儲在file->id
|-> lfs_stag_t tag = lfs_dir_find(lfs, &file->m, &path, &file->id);
|
| // 2. 根據(jù)文件id查找文件數(shù)據(jù)對應tag
| // 此時查找的為STRUCT類型的tag，包括inline文件和outline文件
|-> tag = lfs_dir_get(lfs, &file->m, LFS_MKTAG(0x700, 0x3ff, 0),
| LFS_MKTAG(LFS_TYPE_STRUCT, file->id, 8), &file->ctz);
|
|-> ...
（2）文件刪除后
如刪除剛創(chuàng)建的文件：
![#littlefs原理分析#[三]fetch操作-開源基礎軟件社區(qū)](https://dl-harmonyos.51cto.com/images/202211/d578e1646346893694459581e53666fc39b344.png?x-oss-process=image/resize,w_471,h_281 "#littlefs原理分析#[三]fetch操作-開源基礎軟件社區(qū)")
進行文件或目錄的刪除操作時，會寫入DELETE和CRC類型的tag。其中，CREATE和DELETE類型的tag中的id存儲了相應創(chuàng)建或刪除的文件或目錄的id。
此時若再打開該文件，在遍歷tag時，由于檢查到了包含對應id的DELETE類型tag，則會返回失敗。
在遍歷獲取文件、目錄數(shù)據(jù)的相關函數(shù)中，對DELETE類型tag的相關檢測分析如下：
// 該函數(shù)用于遍歷時查找匹配的tag，如打開文件時查找匹配文件的對應tag
lfs_stag_t lfs_dir_fetchmatch(lfs_t *lfs,
| lfs_mdir_t *dir, const lfs_block_t pair[2],
| lfs_tag_t fmask, lfs_tag_t ftag, uint16_t *id,
| int (*cb)(void *data, lfs_tag_t tag, const void *buffer), void *data)
|-> ...
|
| // 如果當前遍歷到的tag的類型為DELETE，且其id與tempbesttag中id相同
| // 則將tempbesttag置為無效。
|-> if (tag == (LFS_MKTAG(LFS_TYPE_DELETE, 0, 0) |
| (LFS_MKTAG(0, 0x3ff, 0) & tempbesttag))) {
| tempbesttag |= 0x80000000;
| }
|-> ...
（3）其他
- 目錄創(chuàng)建、刪除后的讀取過程與文件創(chuàng)建、刪除后的類似
- 目錄、文件的移動實際上是創(chuàng)建過程和刪除過程的結合，先在新父目錄下創(chuàng)建，再在舊父目錄下刪除。其讀取過程也類似。
2、目錄的遍歷
littlefs中目錄的遍歷是通過TAIL類型的tag來進行的，TAIL類型tag在littlefs存儲結構中已說明，分為SOFTTAIL和HARDTAIL。每個目錄對應的元數(shù)據(jù)塊中都可能存儲指向其他目錄的SOFTTAIL或者指向該目錄下一個元數(shù)據(jù)塊的HARDTAIL。
如何從一個目錄跳轉到其后繼目錄，其實就是通過fetch tail的操作實現(xiàn)。
本節(jié)中著重介紹fetch tail的過程，即已知其父目錄的情況下，如何跳轉到后繼目錄。目錄的鏈接方式見后面的文章。
（1）fetch tail
在父目錄中會記錄其子目錄的創(chuàng)建信息，并會有相應的SOFTTAIL指向該子目錄。具體目錄操作后目錄的鏈接方式見后面的文章，這里只是以一個包含多個子目錄的父目錄的例子來對fetch tail的過程進行說明。
下圖中父目錄有兩個元數(shù)據(jù)對，包含了指向子目錄A、B、C的SOFTTAIL：
![#littlefs原理分析#[三]fetch操作-開源基礎軟件社區(qū)](https://dl-harmonyos.51cto.com/images/202211/15af86f53808a5036d53100d90281cfcfebd4a.png?x-oss-process=image/resize,w_385,h_203 "#littlefs原理分析#[三]fetch操作-開源基礎軟件社區(qū)")
在fetch操作對應函數(shù)lfs_dir_fetchmatch中，能夠檢查到TAIL類型的tag更新傳入的參數(shù)dir->tail，保存TAIL指向的元數(shù)據(jù)對塊。
littlefs中通常是fetch最后一個TAIL，在上圖中即為HARDTAIL和目錄C。littlefs目錄鏈接相關的機制保證這樣遍歷能夠從根目錄遍歷完所有目錄。相關函數(shù)為lfs_dir_fetch：
int lfs_dir_fetch(lfs_t *lfs,
lfs_mdir_t *dir, // fetch tail結果存儲在dir->tail中
const lfs_block_t pair[2] // 父目錄元數(shù)據(jù)對所在塊
) {
// 調用lfs_dir_fetchmatch實現(xiàn)
// 其中fmask、ftag為-1，表示不進行匹配，會fetch到元數(shù)據(jù)末尾
return (int)lfs_dir_fetchmatch(lfs, dir, pair,
(lfs_tag_t)-1, (lfs_tag_t)-1, NULL, NULL, NULL);
}
因為TAIL類型的tag分為SOFTTAIL和HARDTAIL，因此最后dir->tail中保存的tail既可能是HARDTAIL，也可能是SOFTTAIL。以上圖為例：
- 第一次調用lfs_dir_fetch，dir->tail中保存的tail為HARDTAIL，指向該目錄的下一個元數(shù)據(jù)塊
- 第二次調用lfs_dir_fetch，dir->tail中保存的tail為SOFTTAIL，指向子目錄C
（2）fetch下一個目錄
上小節(jié)中，lfs_dir_fetch既可以fetch HARDTAIL，也可以fetch SOFTTAIL。而fetch過程中同時會更新dir->split成員，該成員表示當前目錄塊是否有再分，當dir->split為false即表示在當前目錄塊的末尾。
由此littlefs中常用以下方法fetch下一個目錄：
lfs_mdir_t m = dir.m;
while (m.split) {
lfs_dir_fetch(lfs, &m, m.tail);
}
（3）目錄刪除和移動后
如果SOFTTAIL對應的目錄已被刪除或移動，那么在該CREATE等tag后應有一個DELETE類型的tag。但該DELETE類型tag對fetch tail的過程沒有影響。目錄的鏈接方式只與SOFTTAIL類型tag有關。目錄刪除和移動后具體的鏈接方式變化見后面的文章。
二、fetch流程
fetch操作的相關函數(shù)為lfs_dir_fetchmatch，該函數(shù)遍歷tag并從中匹配和獲取數(shù)據(jù)。該函數(shù)定義在上節(jié)中已提到，該函數(shù)匹配到tag之后會執(zhí)行相應的回調函數(shù)，回調函數(shù)一般為對tag和相應數(shù)據(jù)進行進一步的比較和匹配。流程如下：
![#littlefs原理分析#[三]fetch操作-開源基礎軟件社區(qū)](https://dl-harmonyos.51cto.com/images/202211/43e310e363258992860683e9ad275c90a389fb.png?x-oss-process=image/resize,w_469,h_832 "#littlefs原理分析#[三]fetch操作-開源基礎軟件社區(qū)")
代碼分析如下：
static lfs_stag_t lfs_dir_fetchmatch(lfs_t *lfs,
| lfs_mdir_t *dir, const lfs_block_t pair[2],
| lfs_tag_t fmask, lfs_tag_t ftag, uint16_t *id,
| int (*cb)(void *data, lfs_tag_t tag, const void *buffer), void *data) {
| // 用besttag保存最佳匹配結果
|-> lfs_stag_t besttag = -1;
|
|-> ...
|
| // 準備用于暫存每次匹配中的最佳匹配結果、更新等變量
|-> uint16_t tempcount = 0;
| lfs_block_t temptail[2] = {LFS_BLOCK_NULL, LFS_BLOCK_NULL};
| bool tempsplit = false;
| lfs_stag_t tempbesttag = besttag;
|
| // fetch主流程
|-> while (true) {
| // 1. 從磁盤中解析下一個tag并計算tag的CRC
|-> lfs_bd_read(lfs,
| NULL, &lfs->rcache, lfs->cfg->block_size,
| dir->pair[0], off, &tag, sizeof(tag));
| crc = lfs_crc(crc, &tag, sizeof(tag));
| tag = lfs_frombe32(tag) ^ ptag;
|
| // 2. 檢查邊界，當不在范圍內或tag無效時跳出循環(huán)
|-> if (!lfs_tag_isvalid(tag)) {
| dir->erased = (lfs_tag_type1(ptag) == LFS_TYPE_CRC &&
| dir->off % lfs->cfg->prog_size == 0);
| break;
| } else if (off + lfs_tag_dsize(tag) > lfs->cfg->block_size) {
| dir->erased = false;
| break;
| }
|
| // 3. 如果tag為CRC，則檢查CRC并更新最佳匹配結果
|-> if (lfs_tag_type1(tag) == LFS_TYPE_CRC) {
| // 3.1 檢查CRC
|-> uint32_t dcrc;
| lfs_bd_read(lfs,
| NULL, &lfs->rcache, lfs->cfg->block_size,
| dir->pair[0], off+sizeof(tag), &dcrc, sizeof(dcrc));
| if (crc != dcrc) {
| dir->erased = false;
| break;
| }
|
| // 3.2 更新最佳匹配結果等
|-> besttag = tempbesttag;
| dir->off = off + lfs_tag_dsize(tag);
| dir->etag = ptag;
| dir->count = tempcount;
| dir->tail[0] = temptail[0];
| dir->tail[1] = temptail[1];
| dir->split = tempsplit;
|
| // 3.3 重置CRC
|-> crc = 0xffffffff;
| continue;
}
|
| // 4. 計算entry的CRC
|-> for (lfs_off_t j = sizeof(tag); j < lfs_tag_dsize(tag); j++) {
| uint8_t dat;
| lfs_bd_read(lfs,
| NULL, &lfs->rcache, lfs->cfg->block_size,
| dir->pair[0], off+j, &dat, 1);
| ...
| crc = lfs_crc(crc, &dat, 1);
| }
|
| // 5. 根據(jù)tag類型進行相應更新
|-> if (lfs_tag_type1(tag) == LFS_TYPE_NAME) {
| // 5.1 tag為NAME類型，則根據(jù)其中id更新目錄中count
| // 目錄中的最后一個id為count-1
| if (lfs_tag_id(tag) >= tempcount) {
| tempcount = lfs_tag_id(tag) + 1;
| }
| } else if (lfs_tag_type1(tag) == LFS_TYPE_SPLICE) {
| // 5.2 tag為DELETE類型，如果id和目前的最佳匹配結果對應
| // 則將最佳匹配結果置為無效
| if (tag == (LFS_MKTAG(LFS_TYPE_DELETE, 0, 0) |
| (LFS_MKTAG(0, 0x3ff, 0) & tempbesttag))) {
| tempbesttag |= 0x80000000;
| }
| ...
| } else if (lfs_tag_type1(tag) == LFS_TYPE_TAIL) {
| // 5.3 tag為TAIL類型，則更新tempsplit和temptail
| tempsplit = (lfs_tag_chunk(tag) & 1);
| lfs_bd_read(lfs,
| NULL, &lfs->rcache, lfs->cfg->block_size,
| dir->pair[0], off+sizeof(tag), &temptail, 8);
| ...
| }
|
| // 6. 先用fmask和ftag參數(shù)進行初次匹配
|-> if ((fmask & tag) == (fmask & ftag)) {
| // 6.1 如果匹配則調用cb回調函數(shù)進行進一步匹配
| int res = cb(data, tag, &(struct lfs_diskoff){
| dir->pair[0], off+sizeof(tag)});
| ...
| // 6.2 如果匹配成功則更新到最佳匹配結果
| if (res == LFS_CMP_EQ) {
| tempbesttag = tag;
| } else if (...)
| ...
| }
| }
|
| // 如果讀到結束，則根據(jù)最佳匹配結果返回相應值
|-> if (dir->off > 0) {
| ...
|
| if (lfs_tag_isvalid(besttag)) {
| return besttag;
| } else if (lfs_tag_id(besttag) < dir->count) {
| return LFS_ERR_NOENT;
| } else {
| return 0;
| }
| }
|
|-> ...
1、tag和數(shù)據(jù)的讀取
如上文中對fetch流程的分析，也和commit時tag和數(shù)據(jù)寫入的過程類似，fetch等操作時遍歷讀取tag的數(shù)據(jù)如下圖所示：
![#littlefs原理分析#[三]fetch操作-開源基礎軟件社區(qū)](https://dl-harmonyos.51cto.com/images/202211/c157c5f0782c4b66ed7345a68ef65f56b3eb33.png?x-oss-process=image/resize,w_631,h_255 "#littlefs原理分析#[三]fetch操作-開源基礎軟件社區(qū)")
如上圖，tag和數(shù)據(jù)的讀取過程實際上與commit時tag和數(shù)據(jù)寫入的過程相對稱。在tag和數(shù)據(jù)的讀取過程中，ptag用于進行tag的異或運算，其初始化值為0xffffffff。ptag會依次與將要commit的tag（如上圖中的tagA、tagB、tagC）進行異或運算，每次運算后的結果即為讀取出來的tag。同時每讀取一個tag后，其對應的數(shù)據(jù)也能夠相應進行解析。
2、crc的校驗
如上文中對fetch流程的分析，在fetch過程中會進行crc的校驗，以檢驗commit是否有效。crc校驗時仍用lfs_crc函數(shù)進行計算，該函數(shù)在上一篇文章中已作說明。
crc校驗從元數(shù)據(jù)塊中的revision count開始，逐個與tag或數(shù)據(jù)進行計算，每當遇到crc tag時，則將當前crc結果與crc tag對應crc值進行比對。如果不匹配，則當前commit以及其后的commit中所有tag和數(shù)據(jù)將會被視為無效。crc的校驗使得commit操作具有原子性。
總結
本文介紹了fetch操作的流程及作用，描述了littlefs中是怎樣通過遍歷元數(shù)據(jù)中的tag和數(shù)據(jù)，來獲取所需信息的。后面的文章將會開始介紹具體的目錄和文件操作。
??想了解更多關于開源的內容，請訪問：??
??51CTO 開源基礎軟件社區(qū)??
??https://ost.51cto.com??
