成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

littlefs原理分析--存儲結構(一)

系統 OpenHarmony
本文介紹littlefs的整體結構,包括超級塊、文件、目錄等在磁盤上的存儲,以及文件、目錄打開后在內存中的表示,希望能讓讀者對littlefs有一個大概的印象。

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

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

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

前言

littlefs是一個小型的文件系統,其特點有:

(1)具有磨損均衡功能。

(2)具有掉電保護能力。

(3)適用于ROM和RAM有限的場景。

本系列文章將對littlefs的原理進行分析。作為系列的第一篇,首先對littlefs整體的存儲結構進行介紹,在后面的文章中,再對具體的目錄、文件操作等進行分析。

1、總覽

#littlefs原理分析#[一]存儲結構-開源基礎軟件社區

littlefs的存儲結構大體上如上圖所示。其中超級塊是littlefs存儲目錄和文件的起點,根目錄緊隨其后。littlefs中的目錄均可以指向其他的目錄,構成樹狀結構。在目錄中可以包含多個文件,上圖中右邊的目錄中即包含了一個inline文件和一個outline文件。

2、元數據對

在對littlefs的存儲結構進行具體介紹之前,先對littlefs中一個核心的數據結構,即元數據,進行介紹。littlefs中使用元數據對存儲目錄信息、超級塊信息、文件信息、inline文件的數據等內容,是其設計的核心數據結構。

元數據對的存儲結構如下圖:

#littlefs原理分析#[一]存儲結構-開源基礎軟件社區

以下為具體說明:

  • 一個元數據對與物理上的兩個塊相對應,且均記錄了一個revision count。revision count較大的塊存儲的為較新的內容,每當更新其中的數據時,revision count就會加1。使用兩個塊的好處是,當一個塊放不下更新的內容時,可以將數據壓縮并轉存到另一個塊上(如進行compact操作),避免直接破壞原有的數據。
  • 每個超級塊、目錄均有其對應的一個或多個元數據對,其中記錄了超級塊或目錄相關的信息。如目錄對應的元數據對中可能存儲該目錄下的文件信息等。
  • 元數據對以tag為單元進行信息的存儲,以commit的方式進行信息的更新,這里是借鑒了logging文件系統的做法。如創建一個目錄,就會在對應的元數據對中進行一次commit,記錄CREATE、DIR、DIRSTRUCT等tag,最后計算CRC。
  • 元數據對每次進行commit時會計算CRC,以實現數據的校驗等功能。

(1)tag

如上文所述,tag是元數據中存儲信息的單元,其結構如下:

[----            32             ----]
[1|-- 11 --|-- 10 --|-- 10 --]
^. ^ . ^ ^- length
|. | . '------------ id
|. '-----.------------------ type (type3)
'.-----------.------------------ valid bit
[-3-|-- 8 --]
^ ^- chunk
'------- type (type1)

其中包含了tag的有效位、類型、id、長度等信息。對于不同類型的tag,其儲存的內容也不同。通常在tag后會緊跟其相應數據的內容,如CTZSTRUCT類型的tag后的data中存儲了文件大小和文件跳表頭所在的塊號:

tag                          data
[-- 32 --][-- 32 --|-- 32 --]
[1|- 11 -| 10 | 10 ][-- 32 --|-- 32 --]
^ ^ ^ ^ ^ ^- file size
| | | | '-------------------- file head
| | | '- size (8)
| | '------ id
| '------------ type (0x202)
'----------------- valid bit

3、超級塊

超級塊是littlefs存儲目錄和文件的起點,其元數據對所在的塊號起始為0,1。
超級塊以單個或多個元數據對的方式進行存儲,下圖為單個元數據對存儲超級塊的具體情形:

#littlefs原理分析#[一]存儲結構-開源基礎軟件社區

其中包含了LFS_TYPE_CREATE類型、LFS_TYPE_SUPERBLOCK類型等的tag。其中超級塊的具體數據信息存儲于LFS_TYPE_INLINESTRUCT類型的tag中。

相關數據結構如下:

typedef struct lfs_superblock {
uint32_t version; // littlefs版本
lfs_size_t block_size; // 一個塊的大小
lfs_size_t block_count; // 文件系統中塊的總數
lfs_size_t name_max; // 文件名字節數的最大值
lfs_size_t file_max; // 文件大小字節數的最大值
lfs_size_t attr_max; // 文件屬性字節數的最大值
} lfs_superblock_t;

4、目錄

目錄的存儲結構如上文總覽中所示,以單個或多個元數據對的方式進行存儲。以根目錄為起點,通過末尾對其他元數據對的塊指針,可以構成一個樹形結構。

單個目錄的元數據對具體存儲如下圖:

#littlefs原理分析#[一]存儲結構-開源基礎軟件社區

上圖中,中間的目錄使用了兩個元數據對進行存儲。第一個元數據對中SOFTTAIL類型的tag中存儲了指向父目錄中末尾目錄的塊指針(即在父目錄中最后創建的子目錄,當父目錄中還沒有創建子目錄時,該塊指針為空)。第二個元數據對中存儲了創建的子目錄的信息(包括CREATE、DIR、DIRSTRUCT等類型的tag),并指向了子目錄。

注:上述目錄與其父目錄、子目錄之間的鏈接方式只是可能的一種情況。隨著目錄的創建、刪除、移動等操作,具體的鏈接方式會發生變化,具體見后面的文章。

其中相關tag的表示如下:

  • 元數據對的塊指針相關:
  • HARDTAIL:表示同一目錄的下一個元數據對的塊指針。
  • SOFTTAIL:表示不同目錄的下一個元數據對的塊指針。
  • 目錄創建信息相關:在父目錄中會記錄CREATE、DIR、DIRSTRUCT、SOFTTAIL等類型的tag。
  • DIR:存儲目錄名和id。
  • DIRSTRUCT:存儲創建的子目錄的元數據對的塊指針。
  • SOFTTAIL:記錄了創建的子目錄的元數據對的塊指針。

(1)相關數據結構

目錄信息在內存中的表示如下:

typedef struct lfs_mdir {
lfs_block_t pair[2]; // 元數據對塊指針
uint32_t rev; // revision count

// 當前在元數據塊中的偏移
// 用于commit和fetch相關函數
// 作為起始偏移傳入,結束時保存了寫入后的偏移
lfs_off_t off;

// entry tag,用于記錄當前的ptag
// ptag用于commit過程中計算異或tag、計算CRC等,見commit機制和tag的遍歷
// 當fetch時,fetch到一個commit時,會將計算的ptag存入etag
// 當進行commit時,ptag就可以初始化為etag
uint32_t etag;

uint16_t count; // 目錄中屬性數量(文件、子目錄數)

// 表示下一個commit是否寫入完成
// 用于commit和fetch相關函數,見commit機制和tag的遍歷
// 當fetch時,fetch到末尾還未匹配,會把erased置為true
// 在commit函數中,只有erased為true才進行commit
bool erased;

bool split; // 表示當前目錄塊后面是否還有塊,為false時表示末尾

// 表示當前目錄塊中最后一個TAIL
// 既可能是HARDTAIL,也可能是SOFTTAIL
// 與fetch機制、目錄的遍歷等有關
lfs_block_t tail[2];

// 注:off、etag、erased、tail與commit機制、tag的遍歷等有關,見后面的文章
} lfs_mdir_t;

另外,littlefs中,內存中打開的目錄使用lfs_dir_t類型的數據結構進行記錄。見littlefs中mlist的介紹。

5、文件

文件的tag存儲于其父目錄的元數據對中。文件又分為inline文件和outline文件。當文件剛創建時,默認為inline文件。當文件大小超過1/8 block_size、或超過文件cache大小時,會重新分配為outline文件。

(1)inline文件

#littlefs原理分析#[一]存儲結構-開源基礎軟件社區

具體tag存儲信息如下:

  • REG:存儲文件名和id
  • INLINESTRUCT:存儲inline文件的數據

(2)outline文件

#littlefs原理分析#[一]存儲結構-開源基礎軟件社區

如上圖,littlefs中outline文件的數據是用跳表存儲的。其中CTZSTRUCT類型的tag中存儲了文件大小和跳表頭指針信息,跳表頭指針指向了文件末尾的塊。跳表中每個塊對其他塊的指針儲存在該塊的塊頭處。

跳表中塊指針按固定規律分布:對block ,如果可以被整除,那么該block就含有一個指向block 的塊指針。以block 4為例:

  • 4可以被整除,則block 4含有即block 3的塊指針。
  • 4可以被整除,則block 4含有即block 2的塊指針。
  • 4可以被整除,則block 4含有即block 0的塊指針。

由此規律,又因為塊的大小是固定的,那么只要知道文件的偏移位置,就可以獲取該偏移位置所在block在跳表中的序號、該塊上有幾個塊指針等信息:

  • 獲取跳表中塊序號:根據文件偏移和塊大小計算,相關函數為lfs_ctz_index。
  • 獲取塊頭部塊指針數量:用ctz指令,ctz(塊序號)。

(3)相關數據結構

文件在內存中表示如下:

typedef struct lfs_file {
// 以下4個成員與mlist相關,見后文mlist的介紹
struct lfs_file *next;
uint16_t id;
uint8_t type;
lfs_mdir_t m;

struct lfs_ctz {
lfs_block_t head; // 跳表頭指針,inline文件時為LFS_BLOCK_INLINE
lfs_size_t size; // 文件大小,inline和outline文件均用此記錄
} ctz;

uint32_t flags; // INLINE、OUTLINE、DIRTY、WRITING等標志
lfs_off_t pos; // 文件當前的偏移字節數
lfs_block_t block; // 文件當前的block
lfs_off_t off; // 文件在當前block的偏移
lfs_cache_t cache; // 文件緩存,用于讀寫等操作

const struct lfs_file_config *cfg; // 文件的其他配置信息
} lfs_file_t;

6、文件和目錄在內存中的表示(mlist)

littlefs中,mlist用于記錄打開的文件和目錄,存在于內存中。

mlist主要用于遍歷打開的文件和目錄。

(1)相關數據結構

mlist

typedef struct lfs {
...
struct lfs_mlist {
struct lfs_mlist *next; // 下一個鏈表中的節點
uint16_t id; // 文件或目錄在其父目錄中的id
uint8_t type; // 類型,表明是文件還是目錄
lfs_mdir_t m; // 父目錄元數據對信息
} *mlist;
...
} lfs_t;

打開的文件

typedef struct lfs_file {
struct lfs_file *next; // 下一個鏈表中的節點
uint16_t id; // 文件在父目錄中的id
uint8_t type; // 類型,文件類型應為LFS_REG_TYPE
lfs_mdir_t m; // 父目錄元數據對信息

// 以下成員見上文中存儲結構
...
} lfs_file_t;

打開的目錄

typedef struct lfs_dir {
struct lfs_dir *next; // 下一個鏈表中的節點
uint16_t id; // 目錄在父目錄中的id
uint8_t type; // 類型,目錄應為LFS_DIR_TYPE
lfs_mdir_t m; // 父目錄元數據對信息

lfs_off_t pos; // 當前目錄或文件在父目錄中的位置,.和..分別為0和1
lfs_block_t head[2]; // 第一個元數據對所在塊號
} lfs_dir_t;

(2)記錄打開的文件和目錄

由前面的數據結構,littlefs中mlist是一個單鏈表,其中記錄了打開的文件和目錄。 mlist既可以插入lfs_file_t,也可以插入lfs_dir_t,lfs_mlist、lfs_file_t和lfs_dir_t的前幾個成員的結構體是相同的。

在打開文件過程中

打開文件時,相應lfs_file_t類型的文件數據加入到mlist:

lfs_file_open(lfs_t *lfs, lfs_file_t *file, const char *path, int flags)
|-> lfs_file_rawopen(lfs_t *lfs, lfs_file_t *file,
| const char *path, int flags)
|-> lfs_file_rawopencfg(lfs_t *lfs, lfs_file_t *file,
| const char *path, int flags,
| const struct lfs_file_config *cfg)
|-> ...
|
| // 將file加入到mlist
|-> lfs_mlist_append(lfs, (struct lfs_mlist *)file);
|
|-> ...

在關閉文件過程中

關閉文件時,mlist會刪除對應的文件:

lfs_file_close(lfs_t *lfs, lfs_file_t *file)
|-> lfs_file_rawclose(lfs_t *lfs, lfs_file_t *file)
|-> lfs_mlist_remove(lfs, (struct lfs_mlist*)file);
|
|-> ...

在打開目錄過程中

打開命令時,相應lfs_dir_t類型的目錄數據加入到mlist:

lfs_dir_open(lfs_t *lfs, lfs_dir_t *dir, const char *path)
|-> lfs_dir_rawopen(lfs_t *lfs, lfs_dir_t *dir, const char *path)
|-> ...
|
|-> lfs_mlist_append(lfs, (struct lfs_mlist *)dir);

在關閉目錄過程中

關閉目錄時,mlist中會刪除對應的目錄:

lfs_dir_close(lfs_t *lfs, lfs_dir_t *dir)
|-> lfs_dir_rawclose(lfs_t *lfs, lfs_dir_t *dir)
|-> lfs_mlist_remove(lfs, (struct lfs_mlist *)dir);

總結

本文介紹了littlefs的整體結構,包括超級塊、文件、目錄等在磁盤上的存儲,以及文件、目錄打開后在內存中的表示,希望能讓讀者對littlefs有一個大概的印象。后續的文章會繼續分析littlefs原理。

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

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

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

責任編輯:jianghua 來源: 51CTO開源基礎軟件社區
相關推薦

2022-11-07 15:27:07

LittlefsFetch操作

2022-11-15 09:24:16

littlefs文件讀寫

2022-11-02 15:56:45

littlefscommit機制

2022-11-22 15:21:55

littlefs磨損均衡

2022-11-09 08:52:57

littlefs目錄操作

2018-06-13 08:53:39

HadoopHBase存儲

2014-11-27 09:59:02

dockerlinux技巧

2010-04-21 16:07:04

Oracle邏輯存儲結

2010-04-21 16:55:06

Oracle物理存儲結

2019-04-29 11:14:25

MySQL存儲排序

2021-07-23 13:22:49

InnoDB存儲結構

2019-06-03 15:15:09

MySQL索引數據庫

2012-03-15 16:12:57

JavaHashMap

2010-01-05 14:18:56

高層交換機

2022-06-08 07:34:02

持久化數據存儲原理索引存儲格式

2019-01-08 11:57:10

Redis存儲數據結構

2018-09-30 10:58:20

云存儲原理網盤

2019-07-03 15:14:00

Oracle存儲結構

2019-08-06 09:11:49

數據庫數據結構操作系統

2011-05-31 13:12:15

Android 目錄結構
點贊
收藏

51CTO技術棧公眾號

主站蜘蛛池模板: 午夜免费在线观看 | 亚洲天堂久久新 | 欧美精品tv | 久久国产精品色av免费观看 | 日本精品久久久久久久 | 国产欧美在线视频 | 亚洲欧洲一区 | 欧美精品一区二区在线观看 | 狼人伊人影院 | 欧美日韩在线一区二区 | 国产999精品久久久 精品三级在线观看 | 日日夜夜精品 | 成人精品鲁一区一区二区 | 一区精品视频在线观看 | 精品国产一级 | 99热热精品| 国产精品久久久久久久毛片 | 91精品国产一区 | 91亚洲欧美 | 欧美黑人国产人伦爽爽爽 | 成人免费高清 | 狠狠艹| 久久精品小视频 | 九九九色 | 中文字幕在线一区 | 日韩欧美在线观看 | 国产成人99久久亚洲综合精品 | 五月婷六月丁香 | 欧美a在线 | 国产二区三区 | 欧美久久一区 | 欧美日韩亚洲系列 | 琪琪午夜伦伦电影福利片 | 天天操夜夜艹 | 国产成人在线视频 | 国产精品日韩一区二区 | 免费在线观看一区二区 | 成人免费在线小视频 | 99视频精品| 一区二区伦理电影 | 中文字幕日韩欧美一区二区三区 |