时间戳

首页 > 技术文章 > FlashTLV-适用于Nor-Flash的KVDB

FlashTLV-适用于Nor-Flash的KVDB

yanye0xff 2022-05-14 13:02 原文

TLV格式简介

TLV是一种可变长格式，Type/Tag和Length自身占用的长度固定，一般为2、4字节（uint16_t或uint32_t)；Length表示数据的长度，单位为字节；Value为实际携带的数据。其结构非常简单，元数据(metadata)占用较少，优点是打包解包效率高，省内存。

1 2 3
T Type/Tag 标识类型
L Length 数据长度
V Value 数据内容

关于flashTLV

这是为嵌入式环境设计的一种KVDB，目的是解决设备配置、激活码、识别码等小数据的存取。它使用2个扇区(其中一个扇区作为垃圾回收的担保空间)存储1个扇区的数据，支持多个物理扇区合并为1个逻辑扇区使用。提供数据的读/写/删操作，但无任何SQL功能，每条记录都有唯一的键(key)对应，二次写入同一个键的记录会使前一个失效。
特性如下：

  • 使用SPI Nor-Flash或者单片机内部Flash作为存储介质，最小擦除单位为1扇区，需要能单字节随机访问。
  • 支持多扇区合并实现存储较大的单条记录，但单条记录的长度限制为65534字节(0xFFFF - 1)
  • 数据更新使用COW（copy on write）方式，读出旧数据，异地写入新数据，标记旧数据无效。
  • 写入掉电时产生的坏数据块检测。（仅检测TLV结构，保证存储结构不受影响，但不校验数据域）
  • 查询时间复杂度O(n)，可选的缓存(默认16条)，采用简单的LFU算法管理，缓存查询和追加的时间复杂度为O(n)。
  • GC方式采用标记+复制，完成一次GC后无碎片产生。
  • 掉电保护范围：记录块写入完整性校验，记录块二次更新，扇区垃圾回收。
  • 实现代码不到500行，草履虫也能看懂。

存储结构

1号扇区的数据示例：
image
1号扇区写满，经过一次垃圾回收，2号扇区的数据：
image
扇区头结构

typedef struct _tlv_sector_header {
    // 标识头
    uint16_t tag;
    // 版本号
    uint16_t version;
} tlv_sector_header_t;

记录块头结构

typedef struct _tlv_block {
    // 结构头 固定0x55 0xaa
    uint16_t header;
    // 结构状态
    uint8_t status;
    // X^8+X^2+X^1+1
    // crc8 = calc_crc8(tag + length + entity[...])
    uint8_t crc8;
    uint16_t tag;
    uint16_t length;
    // 数据域的起始地址(此参数不存储到Flash)
    uint32_t entity;
} tlv_block_t;

API说明

flash_tlv_init

Type Note
Function 初始化FlashTLV工作扇区。
Prototype void flash_tlv_init(
tlv_sector_t *sector,
uint32_t major,
uint32_t minor,
uint16_t size)
Parameter tlv_sector_t *sector: FlashTLV数据结构
uint32_t major: 可用扇区1地址
uint32_t minor: 可用扇区2地址
uint16_t size: 扇区大小(bytes)
Return none
Note 如果启用了缓存，一并初始化缓存结构，major和minor扇区经过GC后会交换使用。
示例：

存储设备使用SPI Nor-Flash，起始地址为0x0，物理扇区大小为4KB，FlashTLV使用0~1号物理扇区。

tlv_sector_t tlv_sector;
flash_tlv_init(&tlv_sector, 0x0, 0x1000, 4096);

存储设备使用SPI Nor-Flash，起始地址为0x0，物理扇区大小为4KB，合并2个物理扇区作为一个逻辑扇区，FlashTLV使用0~3号物理扇区。

tlv_sector_t tlv_sector;
flash_tlv_init(&tlv_sector, 0x0, 0x2000, 8192);

存储设备使用单片机内部Flash，起始地址为0x08000000，物理扇区大小为2KB，FlashTLV使用62~63号物理扇区。

tlv_sector_t tlv_sector;
flash_tlv_init(&tlv_sector, 0x801F000, 0x801F800, 2048);

flash_tlv_format

Type Note
Function 格式化FlashTLV使用的扇区。
Prototype void flash_tlv_format(
tlv_sector_t *sector)
Parameter tlv_sector_t *sector: FlashTLV数据结构
Return none
Note 通常不需要主动调用（除非需要快速删除全部数据），首次创建的FlashTLV会在查询/追加/删除数据时自动初始化。

flash_tlv_append

Type Note
Function 追加一条记录。
Prototype bool flash_tlv_append(
tlv_sector_t *sector,
uint16_t tag,
const uint8_t *data,
uint16_t length)
Parameter tlv_sector_t *sector: FlashTLV数据结构
uint16_t tag: 数据标签(0x0000~0xFFFF)
const uint8_t *data: 被写入的数据
uint16_t length: 写入数据的长度，最大支持65534字节
Return true: 写入成功, false: 空间不足写入失败
Note 如果存在tag相同的旧记录，它将被标记删除；如果启用了缓存，追加到Flash的记录会同步到缓存列表

flash_tlv_query

Type Note
Function 查询指定Tag的记录。
Prototype bool flash_tlv_query(
tlv_sector_t *sector,
uint16_t tag,
tlv_block_t *block)
Parameter tlv_sector_t *sector: FlashTLV数据结构
uint16_t tag: 数据标签(0x0000~0xFFFF)
tlv_block_t *block: 存储查询到的记录信息
Return true:查询成功, false: 没有这个Tag的数据
Note 如果启用了缓存，优先从缓存中取；如果缓存中没有，查询Flash并加入缓存

flash_tlv_read

Type Note
Function 读取查询到的记录。
Prototype uint32_t flash_tlv_read(
tlv_block_t *block,
uint8_t *buffer,
uint16_t offset,
uint16_t length)
Parameter tlv_block_t *block: 记录块信息
uint8_t *buffer: 存储读取到的数据
uint16_t offset: 记录块中数据的偏移量
uint16_t length: 需要读取的长度，最大支持65534字节
Return uint32_t: 实际读取到的长度
Note 先调用flash_tlv_query查询到指定Tag的记录块结构，才能读取数据。

flash_tlv_verify

Type Note
Function 验证flash_tlv_query获取到的TLV记录块完整性。
Prototype bool flash_tlv_verify(
tlv_block_t *block)
Parameter tlv_block_t *block: 记录块信息
Return true:CRC8校验成功, false: 校验失败
Note TLV记录块在写入后经过回读校验后才标记数据有效，因此查询后的验证操作是可选的。

flash_tlv_delete

Type Note
Function 删除指定Tag的TLV记录块。
Prototype bool flash_tlv_delete(
tlv_sector_t *sector,
uint16_t tag)
Parameter tlv_sector_t *sector: FlashTLV数据结构
uint16_t tag 需要删除的Tag
Return true: 删除成功, false: 无此标签
Note 如果使用了缓存，将一并删除缓存中记录。

Flash操作接口

使用FlashTLV需要实现以下三个接口：

/**
 * @brief Flash擦除
 * @param addr 擦除的起始地址
 * @param size 擦除的大小(bytes)
 * */
void flash_erase(uint32_t addr, uint32_t size);

/**
 * @brief Flash写入
 * @note 写入前需要保证地址对应的扇区擦除过
 * @param addr 写入的起始地址
 * @param length 写入的长度(bytes)
 * @param buffer 写入的数据
 * */
void flash_write(uint32_t addr, uint32_t length, const uint8_t *buffer);

/**
 * @brief Flash读取
 * @param addr 读取的起始地址
 * @param length 读取的长度(bytes)
 * @param buffer 存放读出的数据
 * */
void flash_read(uint32_t addr, uint32_t length, uint8_t *buffer);

项目地址

https://github.com/Yanye0xFF/FlashTLV

目录结构

src
flash_tlv.c FlashTLV实现
flash_tlv.h
flash_tlv_cache.c TLV缓存实现
flash_tlv_cache.h
spi_flash.c 模拟SPI Nor-Flash
spi_flash.h
utils.h CRC8，CRC32
utils.c
main.c 测试样例

应用案例

2.13寸三色蓝牙标签，FlashTLV被用于存储蓝牙配置，设备激活信息。

推荐阅读