littlefs原理分析—磨損均衡（六）

作者：蔣衛(wèi)峰李濤 2022-11-22 15:21:55

系統(tǒng) OpenHarmony

本文介紹了littlefs中與磨損均衡相關(guān)的策略以及塊分配算法。

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

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

前言

前面已經(jīng)對(duì)littlefs的原理分析了5篇文章，內(nèi)容包括了：

littlefs整體的存儲(chǔ)結(jié)構(gòu)
commit機(jī)制
fetch操作
目錄操作
文件讀寫操作

本文是littlefs原理分析系列最后一篇文章，主要介紹littlefs中與磨損均衡相關(guān)的策略，同時(shí)也會(huì)對(duì)其中的塊分配算法進(jìn)行介紹。

littlefs有以下防止磨損相關(guān)的措施：

寫時(shí)壞塊的檢測(cè)和寫入恢復(fù)。
均勻地進(jìn)行塊的分配：由塊分配算法實(shí)現(xiàn)。
定期重分配元數(shù)據(jù)所在塊。

1、寫時(shí)壞塊的檢測(cè)和寫入恢復(fù)

littlefs中當(dāng)進(jìn)行文件、目錄元數(shù)據(jù)等的寫入時(shí)，最后會(huì)調(diào)用函數(shù)lfs_bd_flush將數(shù)據(jù)最終寫入到磁盤。lfs_bd_flush函數(shù)寫入完后，會(huì)將內(nèi)存中寫入的數(shù)據(jù)和磁盤上的數(shù)據(jù)進(jìn)行比較。如果數(shù)據(jù)不一致，則可能是壞塊。

方法如下：

寫入時(shí)通過回讀磁盤上的數(shù)據(jù)進(jìn)行驗(yàn)證，來檢測(cè)壞塊。
檢測(cè)到壞塊后，清除壞塊，重新分配塊，然后重新寫入。

lfs_bd_flush函數(shù)檢查數(shù)據(jù)是否一致部分的分析如下：

// 當(dāng)將緩存中的數(shù)據(jù)回寫到磁盤時(shí)，檢測(cè)壞塊
lfs_bd_flush(lfs_t *lfs,
|       lfs_cache_t *pcache, lfs_cache_t *rcache, bool validate) 
|   ...
|
|   // 調(diào)用lfs_bd_cmp比較磁盤上的數(shù)據(jù)是否與寫入的數(shù)據(jù)相同
|   // 如果不同則可能遇到了壞塊
|-> if (validate) {
|       lfs_bd_cmp(lfs,
|               NULL, rcache, diff,
|               pcache->block, pcache->off, pcache->buffer, diff); 
|   }
|
|-> ...

如在文件寫入數(shù)據(jù)時(shí)，在函數(shù)lfs_file_flush中，檢測(cè)到壞塊時(shí)會(huì)重新分配塊再進(jìn)行寫入操作：

lfs_file_flush(lfs_t *lfs, lfs_file_t *file)
|-> ...
|
|-> while (true) {
|       // 調(diào)用lfs_bd_flush寫入數(shù)據(jù)，并比較數(shù)據(jù)是否寫入正確
|       int err = lfs_bd_flush(lfs, &file->cache, &lfs->rcache, true);
|       if (err) {
|           // 檢測(cè)到壞塊則跳轉(zhuǎn)到relocate
|           if (err == LFS_ERR_CORRUPT) {
|               goto relocate;
|           }
|           return err;
|       }
|       break;
|
|   relocate:
|       // 重新分配塊并再次進(jìn)行寫入操作
|       LFS_DEBUG("Bad block at 0x%"PRIx32, file->block);
|       err = lfs_file_relocate(lfs, file);
|       if (err) {
|           return err;
|       }
|   }

2、塊分配

（1）lookahead buffer

littlefs中使用一個(gè)lookahead buffer來管理和分配塊。lookahead buffer是一個(gè)固定大小的bitmap，記錄一片區(qū)域內(nèi)塊分配的信息。

lookahead buffer圖例如下，其中假設(shè)總共有64個(gè)塊，lookahead buffer的大小為8，lookahead buffer對(duì)應(yīng)塊中現(xiàn)分配了文件A、D和目錄B、C的塊：

#littlefs原理分析#[六]磨損均衡-開源基礎(chǔ)軟件社區(qū)

lookahead buffer相關(guān)數(shù)據(jù)結(jié)構(gòu)如下：

struct lfs_free {
    lfs_block_t off;     // lookahead所有block整體的偏移
    lfs_block_t size;    // lookahead中塊的總數(shù)
    lfs_block_t i;       // 在lookahead_size中的索引，表示當(dāng)前位于第幾個(gè)block
    lfs_block_t ack;     // 所有剩余空閑block個(gè)數(shù)
    uint32_t *buffer;    // lookahead的bitmap塊管理緩存區(qū)
} free;

（2）查找已分配的塊

lookahead buffer只記錄了一片區(qū)域內(nèi)塊分配的信息，當(dāng)需要知道其他區(qū)域塊分配的情況時(shí)，就需要進(jìn)行掃描文件系統(tǒng)來查找已分配的塊。如lookahead buffer中已經(jīng)沒有空閑塊、需要推移lookahead buffer來查找文件系統(tǒng)中的其他空閑塊。

掃描和查找已分配的塊的過程如下：

將lookahead buffer位置推移一個(gè)lookahead_size，并將lookahead buffer清0。
從超級(jí)塊開始遍歷文件系統(tǒng)中所有目錄和文件，以遍歷所有已分配的塊。如果塊位于lookahead buffer所管理區(qū)域，則將lookahead buffer中相應(yīng)位置為1。

lookahead buffer只用固定大小的bitmap存儲(chǔ)已分配塊的信息，是littlefs中的一種權(quán)衡，這樣雖然更耗費(fèi)時(shí)間，但有效節(jié)省了RAM空間資源。

代碼分析如下：

lfs_alloc(lfs_t *lfs, lfs_block_t *block)
|   ...
|
|   // 當(dāng)lookahead buffer中沒有空閑塊時(shí)，需進(jìn)行掃描
|
|   // 1. 推移lookahead buffer
|-> lfs->free.off = (lfs->free.off + lfs->free.size)
|            % lfs->cfg->block_count;
|   lfs->free.size = lfs_min(8*lfs->cfg->lookahead_size, lfs->free.ack);
|   lfs->free.i = 0;
|
|   // 2. 將lookahead buffer清0
|-> memset(lfs->free.buffer, 0, lfs->cfg->lookahead_size);
|
|   // 3. 遍歷文件系統(tǒng)進(jìn)行掃描和查找
|-> lfs_fs_rawtraverse(lfs, lfs_alloc_lookahead, lfs, true);
|
|-> ...

其中，lfs_fs_rawtraverse函數(shù)會(huì)從超級(jí)塊開始遍歷整個(gè)文件系統(tǒng)，對(duì)整個(gè)文件系統(tǒng)中所有已經(jīng)分配的塊調(diào)用回調(diào)函數(shù)lfs_alloc_lookahead。lfs_alloc_lookahead函數(shù)分析如下：

// lfs_fs_rawtraverse函數(shù)傳入到lfs_alloc_lookahead函數(shù)的參數(shù)
// 分別為lfs結(jié)構(gòu)體指針p，和塊號(hào)block
lfs_alloc_lookahead(void *p, lfs_block_t block)
|-> lfs_t *lfs = (lfs_t*)p;
|
|   // 獲取塊號(hào)相對(duì)lookahead buffer的偏移
|-> lfs_block_t off = ((block - lfs->free.off)
|           + lfs->cfg->block_count) % lfs->cfg->block_count;
|
|   // 若該塊處于lookahead buffer所管理的范圍內(nèi)，
|   // 則設(shè)置bitmap對(duì)應(yīng)位，表示該塊已分配
|-> if (off < lfs->free.size) {
|       lfs->free.buffer[off / 32] |= 1U << (off % 32);
|   }
|   return 0;

（3）塊分配算法

塊分配算法的過程總結(jié)：首先嘗試從lookahead buffer中找到下一個(gè)空閑塊，若沒有則將lookahead buffer位置推移一個(gè)lookahead_size，執(zhí)行上一小節(jié)中的掃描和查找文件系統(tǒng)過程，再嘗試從lookahead buffer中找到下一個(gè)空閑塊，以此循環(huán)進(jìn)行。

以下為幾次分配和掃描的示例：

boot...         lookahead:
                fs blocks: fffff9fffffffffeffffffffffff0000
scanning...     lookahead: fffff9ff
                fs blocks: fffff9fffffffffeffffffffffff0000
alloc = 21      lookahead: fffffdff
                fs blocks: fffffdfffffffffeffffffffffff0000
alloc = 22      lookahead: ffffffff
                fs blocks: fffffffffffffffeffffffffffff0000
scanning...     lookahead:         fffffffe
                fs blocks: fffffffffffffffeffffffffffff0000
alloc = 63      lookahead:         ffffffff
                fs blocks: ffffffffffffffffffffffffffff0000
scanning...     lookahead:         ffffffff
                fs blocks: ffffffffffffffffffffffffffff0000
scanning...     lookahead:                 ffffffff
                fs blocks: ffffffffffffffffffffffffffff0000
scanning...     lookahead:                         ffff0000
                fs blocks: ffffffffffffffffffffffffffff0000
alloc = 112     lookahead:                         ffff8000
                fs blocks: ffffffffffffffffffffffffffff8000

（4）均勻分配方法

介紹了塊分配算法后，現(xiàn)在回過來介紹塊分配算法中與磨損均衡相關(guān)的策略。

littlefs中使用了一個(gè)簡(jiǎn)單的策略來實(shí)現(xiàn)均勻地分配：

使用lookahead buffer線性地分配塊，這樣在一次運(yùn)行中塊分配是循環(huán)磁盤均勻進(jìn)行的。
每次掛載文件系統(tǒng)時(shí)，將lookahead buffer推移一個(gè)隨機(jī)的偏移量，這樣在多次運(yùn)行過程中，只要這個(gè)隨機(jī)偏移量是均勻的，那么整體的分配也是均勻的。

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

lfs_mount(lfs_t *lfs, const struct lfs_config *cfg)
|-> lfs_rawmount(lfs_t *lfs, const struct lfs_config *cfg)
    |-> ...
    |
    |   // 1. 計(jì)算隨機(jī)數(shù)
    |-> lfs_dir_fetchmatch(...)
        |-> ...
        |
        |   // 使用crc計(jì)算隨機(jī)數(shù)
        |-> lfs->seed = lfs_crc(lfs->seed, &crc, sizeof(crc));
        |
        |-> ...
    |
    |   // 2. 隨機(jī)對(duì)lookahead buffer進(jìn)行偏移
    |-> lfs->free.off = lfs->seed % lfs->cfg->block_count;

3、定期重分配元數(shù)據(jù)所在塊

littlefs中會(huì)定期進(jìn)行元數(shù)據(jù)對(duì)應(yīng)塊的重分配，以防止元數(shù)據(jù)塊的磨損。

每次元數(shù)據(jù)commit過程中因空間不足，而進(jìn)行compact或split操作時(shí)，revision count也會(huì)隨著更新。當(dāng)revision count為block_cycles的整數(shù)倍時(shí)，會(huì)進(jìn)行元數(shù)據(jù)對(duì)應(yīng)塊的重分配。其中，block_cycles為用戶配置的值。

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

lfs_dir_compact(lfs_t *lfs,
|       lfs_mdir_t *dir, const struct lfs_mattr *attrs, int attrcount,
|       lfs_mdir_t *source, uint16_t begin, uint16_t end) 
|-> ...
|
|   // revision count為block_cycles的整數(shù)倍時(shí)，進(jìn)行元數(shù)據(jù)對(duì)應(yīng)塊的重分配
|-> if (lfs->cfg->block_cycles > 0 &&
|       (dir->rev % ((lfs->cfg->block_cycles+1)|1) == 0)) {
|       ...
|
|       // we're writing too much, time to relocate
|       tired = true;
|       goto relocate;
|   }
|
|-> ...
|
|   relocate:
|-> ...

總結(jié)

本文介紹了littlefs中與磨損均衡相關(guān)的策略以及塊分配算法，到這里littlefs文件系統(tǒng)原理分析系列文章已經(jīng)結(jié)束。小編也是希望通過對(duì)littlefs文件系統(tǒng)的仔細(xì)分析，讓相關(guān)讀者更深入了解OpenHarmony LiteOS-A內(nèi)核的文件系統(tǒng)的原理，而且littlefs文件系統(tǒng)也不僅僅是在OpenHarmony系統(tǒng)上使用，它也是一個(gè)廣泛使用的小型文件系統(tǒng)，相信掌握它的原理對(duì)嵌入式開發(fā)者有著“鼎力相助”的作用。

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

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

責(zé)任編輯：jianghua 來源： 51CTO開源基礎(chǔ)軟件社區(qū)