作者:蔣衛峰 李濤
前言
回顧littlefs的存儲結構,其中最為核心的是中繼資料。中繼資料以tag為單元進行資訊的存儲,以commit的方式進行資訊的更新。當littlefs中進行檔案、目錄的建立、修改、删除等一系列操作時,實際上都是通過向中繼資料中進行commit操作的方式實作。本文将對littlefs中commit機制進行介紹。
1. commit過程
commit具體的過程如下圖所示:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI1ITMfhGL3QTNfdHLlpXazVmcvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5SOidTN1MTMkJDOhJTOkRWN4UzMkhTZyYjYjRWYjhDOkNmZlNTOk9CXwEjMyAjMvw1cldWYtl2Lc12bj5yb0NWM14ycvlnbv1mchhWLsR2Lc9CX6MHc0RHaiojIsJye.png)
每一次commit時都會向中繼資料對中寫入一系列的tag和資料,并計算CRC。因為在commit時總是會進行CRC計算,并且從中繼資料中讀取資料時會做校驗,是以一次commit是一次原子操作。
下面以具體的案例對commit過程進行說明:
1.1 超級塊的建立
當littlefs進行格式化操作時,會進行超級塊的建立。超級塊建立主要是在根目錄對應中繼資料對的塊中進行commit:
如上圖,超級塊建立時調用lfs_dir_commit函數寫入了CREATE、SUPERBLOCK、INLINESTRUCT和CRC類型的tag。lfs_dir_commit函數中進行了commit的實際寫入操作,其主要分為以下兩個步驟:
- 将tag和對應的資料依次寫入中繼資料對應塊中
- 計算CRC,并接着将其tag和CRC資料寫入中繼資料對應塊中
超級塊建立相關函數:
lfs_format(lfs_t *lfs, const struct lfs_config *cfg)
|-> lfs_rawformat(lfs_t *lfs, const struct lfs_config *cfg)
| // 1. 配置設定根目錄,其塊号為0,1
|-> lfs_dir_alloc(lfs, &root);
|
| // 2. 通過commit建立超級塊
|-> lfs_superblock_t superblock = {
| .version = LFS_DISK_VERSION,
| .block_size = lfs->cfg->block_size,
| .block_count = lfs->cfg->block_count,
| .name_max = lfs->name_max,
| .file_max = lfs->file_max,
| .attr_max = lfs->attr_max,
| };
| lfs_dir_commit(lfs, &root, LFS_MKATTRS(
| {LFS_MKTAG(LFS_TYPE_CREATE, 0, 0), NULL},
| {LFS_MKTAG(LFS_TYPE_SUPERBLOCK, 0, 8), "littlefs"},
| {LFS_MKTAG(LFS_TYPE_INLINESTRUCT, 0, sizeof(superblock)),
| &superblock}));
1.1.1 tag和相應資料的寫入
如上圖,在commit過程中,ptag用于進行tag的異或運算,其初始化值為0xffffffff。ptag會依次與将要commit的tag(如上圖中的tagA、tagB、tagC)進行異或運算,然後将運算後的結果存儲到塊中。同時每寫一個tag後,将其對應的資料也進行寫入。
相關函數分析:
lfs_dir_commitattr(lfs_t *lfs, struct lfs_commit *commit,
| lfs_tag_t tag, const void *buffer)
| // 1. 将ptag和tag進行異或運算
| // 注:這裡将tag的有效位置為了0,表示tag有效,并且tag為大端存儲
|-> lfs_tag_t ntag = lfs_tobe32((tag & 0x7fffffff) ^ commit->ptag);
|
| // 2. 寫入異或後的ntag
|-> lfs_dir_commitprog(lfs, commit, &ntag, sizeof(ntag));
|
| // 3. 寫入對應資料
|-> lfs_dir_commitprog(lfs, commit, buffer, dsize-sizeof(tag));
1.1.2 CRC的寫入
commit過程中,當寫入tag(異或後的tag)或資料時,均會進行逐位元組CRC的計算。最後commit完成後,再寫入相應的CRC tag和對應的CRC值。同時為了寫入對齊,在CRC tag後會設定相應的padding。
CRC計算的範圍為從本次commit起始的tag和資料,一直到CRC tag(包括CRC tag)。
寫入CRC後塊中布局如下圖:
相關函數分析:
// 該函數用于寫入tag或資料,每當調用該函數時都會做CRC的計算
lfs_dir_commitprog(lfs_t *lfs, struct lfs_commit *commit,
| const void *buffer, lfs_size_t size)
| // 1. 将傳入的tag或tag對應資料寫入塊中
|-> lfs_bd_prog(lfs,
| &lfs->pcache, &lfs->rcache, false,
| commit->block, commit->off ,
| (const uint8_t*)buffer, size)
|
| // 2. 計算CRC和更新偏移
|-> commit->crc = lfs_crc(commit->crc, buffer, size);
| commit->off += size;
// 該函數用于寫入CRC tag和padding
lfs_dir_commitcrc(lfs_t *lfs, struct lfs_commit *commit)
| // 1. 建立CRC tag,并異或後存儲于footer[0]中
| // 這裡tag的size設定為了noff - off,實際上是包含了padding的大小
| // littlefs中沒有通過填充資料的方式來設定padding,而是設定其tag的size進行标記
|-> tag = LFS_MKTAG(LFS_TYPE_CRC + reset, 0x3ff, noff - off);
| uint32_t footer[2];
| footer[0] = lfs_tobe32(tag ^ commit->ptag);
|
| // 2. 計算CRC并将CRC值存入footer[1]中
| // 這裡是最後一次計算CRC,前面的tag和資料已經在寫入時計算,隻差CRC tag
|-> commit->crc = lfs_crc(commit->crc, &footer[0], sizeof(footer[0]));
| footer[1] = lfs_tole32(commit->crc);
|
| // 3. 寫入CRC tag和CRC值到塊中
|-> lfs_bd_prog(lfs,
| &lfs->pcache, &lfs->rcache, false,
| commit->block, commit->off, &footer, sizeof(footer));
1.1.3 crc的計算
littlefs中crc計算核心函數如下:
uint32_t lfs_crc(uint32_t crc, const void *buffer, size_t size) {
static const uint32_t rtable[16] = {
0x00000000, 0x1db71064, 0x3b6e20c8, 0x26d930ac,
0x76dc4190, 0x6b6b51f4, 0x4db26158, 0x5005713c,
0xedb88320, 0xf00f9344, 0xd6d6a3e8, 0xcb61b38c,
0x9b64c2b0, 0x86d3d2d4, 0xa00ae278, 0xbdbdf21c,
};
const uint8_t *data = buffer;
for (size_t i = 0; i < size; i++) {
crc = (crc >> 4) ^ rtable[(crc ^ (data[i] >> 0)) & 0xf];
crc = (crc >> 4) ^ rtable[(crc ^ (data[i] >> 4)) & 0xf];
}
return crc;
}
本文中不對crc的原理進行具體介紹,有興趣的讀者可參考以下連結:
- Sunshine's Homepage - Understanding CRC
- https://en.wikipedia.org/wiki/Cyclic_redundancy_check
littlefs中crc計算算法的特點是采用了32位的crc結果,輸入資料以4bit為機關進行計算。其中還用到了lookup table進行加速,因為輸入的資料以4bit為機關進行計算,每次有2^4即16種可能的輸入,是以該lookup table的長度為16。從lookup table中還可看出該crc算法對應的多項式值為0x1db71064。
1.2 tag的周遊和寫入總結
與周遊并寫入tag等資料相關的函數為lfs_dir_traverse,該函數被lfs_dir_commit調用。該函數隻用于commit等需要寫入tag資料的過程,不用于周遊擷取資料。其流程如下:
代碼分析如下:
static int lfs_dir_traverse(lfs_t *lfs,
| const lfs_mdir_t *dir, lfs_off_t off, lfs_tag_t ptag,
| const struct lfs_mattr *attrs, int attrcount,
| lfs_tag_t tmask, lfs_tag_t ttag,
| uint16_t begin, uint16_t end, int16_t diff,
| int (*cb)(void *data, lfs_tag_t tag, const void *buffer), void *data) {
|-> while (true) {
| // 1. 從磁盤或attrs中擷取下一個tag和相應資料,如果沒有則結束
| // attrs中儲存的是将要commit的tag和相應資料
| lfs_tag_t tag;
| const void *buffer;
| struct lfs_diskoff disk;
| // 1.1 如果在磁盤偏移範圍内,則從磁盤中擷取下一個tag和資料
| // 一般進行commit時會将偏移設定到磁盤末尾,不從磁盤中擷取之前的tag
| // 隻有如compact等過程中才從磁盤中擷取之前的tag來寫入
|-> if (off+lfs_tag_dsize(ptag) < dir->off) {
| off += lfs_tag_dsize(ptag);
| ...
|
| tag = (lfs_frombe32(tag) ^ ptag) | 0x80000000;
| disk.block = dir->pair[0];
| disk.off = off+sizeof(lfs_tag_t);
| buffer = &disk;
| ptag = tag;
| } else if (attrcount > 0) {
| // 1.2 從attrs中擷取下一個tag和資料
| // attrs中儲存的是将要commit的新的tag和資料
|-> tag = attrs[0].tag;
| buffer = attrs[0].buffer;
| attrs += 1;
| attrcount -= 1;
| } else {
| // 1.3 否則結束
|-> return 0;
| }
|
| // 2. 使用tmask和ttag參數過濾掉不想要寫入的tag
|-> lfs_tag_t mask = LFS_MKTAG(0x7ff, 0, 0);
| if ((mask & tmask & tag) != (mask & tmask & ttag)) {
| continue;
| }
|
| // 3. 去除備援tag等
| if (lfs_tag_id(tmask) != 0) {
| int filter = lfs_dir_traverse(lfs,
| dir, off, ptag, attrs, attrcount,
| 0, 0, 0, 0, 0,
| lfs_dir_traverse_filter, &tag);
| if (filter < 0) {
| return filter;
| }
|
| if (filter) {
| continue;
| }
|
| if (!(lfs_tag_id(tag) >= begin && lfs_tag_id(tag) < end)) {
| continue;
| }
| }
|
| // 4. 處理一些特殊情況
| if (lfs_tag_type3(tag) == ...) {
| ...
| } else {
| // 5. 調用cb回調函數進行寫入
|-> cb(data, tag + LFS_MKTAG(0, diff, 0), buffer);
| ...
| }
| }
}
2. compact過程
當commit時,如果中繼資料對應塊中的空間不夠,則會嘗試進行compact操作。如下圖:
上圖中左邊中繼資料塊中有兩個commit,其中tag A'是tag A的更新版本。當commit一個tag B'作為tag B的更新版本後,如右圖中右邊的中繼資料塊,備援的tag A和tag B被去除,隻剩下一個commit。
如果compact後中繼資料塊中的空間足夠的話,在進行完compact操作之後的中繼資料塊中就隻會剩下一個CRC tag,即隻有一個commit。compact的主要過程其實就是篩除備援的tag和資料之後,将剩下的tag和資料作為一次commit寫入同中繼資料對中的另一個塊中。
2.1 compact去除内容
下面對compact過程中具體會去除的tag和相應資料進行說明。
compact過程中調用了lfs_dir_traverse進行去除備援tag并寫入:
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)
|-> ...
|
| // 去重并寫入tag
| // 這裡使用了LFS_TYPE_NAME的tag類型進行過濾
|-> lfs_dir_traverse(lfs,
| source, 0, 0xffffffff, attrs, attrcount,
| LFS_MKTAG(0x400, 0x3ff, 0),
| LFS_MKTAG(LFS_TYPE_NAME, 0, 0),
| begin, end, -begin,
| lfs_dir_commit_commit, &(struct lfs_dir_commit_commit){
| lfs, &commit});
|
|-> ...
在lfs_dir_traverse中用下面的邏輯進行篩選tag:
static int lfs_dir_traverse(lfs_t *lfs,
| const lfs_mdir_t *dir, lfs_off_t off, lfs_tag_t ptag,
| const struct lfs_mattr *attrs, int attrcount,
| lfs_tag_t tmask, lfs_tag_t ttag,
| uint16_t begin, uint16_t end, int16_t diff,
| int (*cb)(void *data, lfs_tag_t tag, const void *buffer), void *data) {
|-> ...
|
|-> lfs_tag_t mask = LFS_MKTAG(0x7ff, 0, 0);
| if ((mask & tmask & tag) != (mask & tmask & ttag)) {
| continue;
| }
|-> ...
其中,mask為LFS_MKTAG(0x7ff, 0, 0),tmask為LFS_MKTAG(0x400, 3ff, 0),ttag為LFS_MKTAG(LFS_TYPE_NAME, 0, 0)即LFS_MKTAG(0, 0, 0),則篩選邏輯可簡化為:
if ((LFS_MKTAG(400, 0, 0) & tag) != LFS_MKTAG(0, 0, 0)) {
continue;
}
總結有以下類型的tag會被去除:
- LFS_TYPE_SPLICE:包括CREATE和DELETE
- LFS_TYPE_TAIL:包括SOFTTAIL和HARDTAIL
- LFS_TYPE_GLOBALS:即MOVESTATE
- LFS_TYPE_CRC
2.2 compact寫入過程
與commit中tag和資料的寫入過程類似,compact中的寫入過程包括:
- 寫入更新後的revision count
- 寫入去除備援後的tag和資料
- 如果原來有SOFTTAIL或HARDTAIL,則将原來最後一個TAIL補充寫入。是以,compact過程對目錄的周遊方式無影響,具體目錄的周遊見後面的文章。
- 如果原來有MOVESTATE且進行異或之後不為0,則将異或後的gstate作為MOVESTATE tag補充寫入。gstate相關機制見後面的文章。
- 寫入CRC
相關函數分析:
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)
| // 1. 檢查剩餘空間,如果不夠則進行split操作
|-> lfs_dir_split(lfs, dir, attrs, attrcount,
| source, begin+split, end)
|
| // 2. revision count + 1,并寫入
|-> dir->rev += 1;
| lfs_bd_erase(lfs, dir->pair[1]);
| lfs_dir_commitprog(lfs, &commit,
| &dir->rev, sizeof(dir->rev));
|
| // 3. 去重并寫入tag
|-> lfs_dir_traverse(lfs,
| source, 0, 0xffffffff, attrs, attrcount,
| LFS_MKTAG(0x400, 0x3ff, 0),
| LFS_MKTAG(LFS_TYPE_NAME, 0, 0),
| begin, end, -begin,
| lfs_dir_commit_commit, &(struct lfs_dir_commit_commit){
| lfs, &commit});
|
| // 4. 補充寫入tail
|-> if (!lfs_pair_isnull(dir->tail)) {
| ...
| lfs_dir_commitattr(lfs, &commit,
| LFS_MKTAG(LFS_TYPE_TAIL + dir->split, 0x3ff, 8),
| dir->tail);
| ...
| }
|
| // 5. 補充寫入move state
|-> if (!lfs_gstate_iszero(&delta)) {
| ...
| lfs_dir_commitattr(lfs, &commit,
| LFS_MKTAG(LFS_TYPE_MOVESTATE, 0x3ff,
| sizeof(delta)), &delta);
| ...
| }
|
| // 6. 計算CRC
|-> lfs_dir_commitcrc(lfs, &commit);
3. split過程
當commit時,進行compact操作後仍空間不足,則會進行split操作,将中繼資料對劃分為多個塊進行存儲:
如上圖,左圖中右邊的中繼資料塊為最新的中繼資料塊,其中包含一個commit的内容,即tag A'和tag B'。當再次commit tag C和tag D時,一個中繼資料塊裝不下,就會進行split操作。split操作在第一個中繼資料塊commit的末尾加入一個HARDTAIL類型的tag,指向一個新的中繼資料塊。新的中繼資料塊中再裝入剩下的tag和資料。
split操作中會遞歸調用compact和split,使得在一次split的容量無法滿足commit需求的時候,進行多次split。
相關函數分析:
lfs_dir_split(lfs_t *lfs,
| lfs_mdir_t *dir, const struct lfs_mattr *attrs, int attrcount,
| lfs_mdir_t *source, uint16_t split, uint16_t end)
| // 1. 重新配置設定新的塊,用來存儲split後的資料
|-> lfs_dir_alloc(lfs, &tail);
|
| // 2. 将split部分資料再進行compact操作
| // 該調用會遞歸調用compact和split操作直到commit完成或失敗
|-> lfs_dir_compact(lfs, &tail, attrs, attrcount, source, split, end);
|
| // 3. 更新目錄資訊
|-> dir->tail[0] = tail.pair[0];
| dir->tail[1] = tail.pair[1];
| dir->split = true;
4. 異常情況
前文中提到每次commit之後,都會寫入計算的CRC tag,用于校驗。commit過程是以也是一次原子操作。當commit過程中發生掉電等情況導緻commit過程失敗時,磁盤中中繼資料末尾雖然有寫入的部分tag和資料,但沒有最終的CRC tag,是以當進行tag的周遊等操作時并不會将這次commit視為有效。compact過程和split過程中也類似,隻要沒有最終寫入CRC tag,便不會被視為完成一次commit。如下圖:
另外,當split為多個塊時,由前文中相關分析,compact和split會遞歸調用,并提前檢查塊大小是否滿足需求和配置設定相應塊,最終寫入多個塊。split過程時若沒有足夠的塊,則會報錯,且并不寫入實際内容。split過程時若中途commit失敗,則會導緻上一個中繼資料塊末尾的HARDTAIL指向的塊中沒有有效的CRC tag,進行周遊時會直接傳回錯誤,如下圖:
總結
本文介紹了littlefs中的commit機制,包括commit、compact、split操作的過程,怎樣寫入tag和資料,怎樣計算CRC,以及相應的異常情況處理等。commit是一個寫入中繼資料的過程,後面的文章将會介紹怎樣讀取中繼資料,從tag中擷取目标資訊。
更多原創内容請關注:深開鴻技術團隊
入門到精通、技巧到案例,系統化分享OpenHarmony開發技術,歡迎投稿和訂閱,讓我們一起攜手前行共建生态。
本文作者:深開鴻Kaihong