littlefs的块分配器用于为littlefs分配空闲的Flash块。这个块分配器具有如下特征：
- 格式化文件系统时：块0和块1被分配。
- 挂载文件系统时及其以后：所分配到的块的顺序是随机的。
1 原理概述
块分配器未在Flash中存储任何相关的数据，而仅在运行时读取文件系统对Flash块的使用情况并以位图的形式记录于内存中。内存中的位图并不记录整个Flash所有的块的使用情况，而仅仅记录整个Flash中连续若干个块的使用情况，举例来说：整个Flash拥有1024个块，而块分配器仅在内存中记录索引为32~63的块的分配信息；待索引32~63的块均被分配完毕，则在内存中记录索引64~95的块的分配信息并继续分配……
我们称呼分配器在内存中的位图为窗口，并创建以下两个相关的名词：
- 窗口偏移：窗口中首个Flash块在Flash中的索引
- 窗口大小：窗口能观测到块的个数
块分配器工作时，分配块的规律如下：
- 窗口内的块按顺序分配。
- 当格式化文件系统时，窗口偏移设置为0。格式化文件系统期间分配且只分配块0和块1。
- 当挂载文件系统时，窗口偏移设置为随机值。随机种子来源于挂载文件系统时文件系统的状态。
- 当挂载文件系统后，使用“挂载文件系统时”设置的窗口来分配块，并在窗口内不含空闲块时后移窗口偏移继续分配块。
2 源码分析
2.1 数据结构
结构体 lfs_t 的成员 free 的定义如下，用于记录块分配器的运行时状态。
struct lfs_free {
lfs_block_t off; // 窗口偏移。
lfs_block_t size; // 窗口大小。
lfs_block_t i; // 对窗口内的块进行索引。窗口内此值之前的块全部被分配，此值及其之后可能存在空闲块待分配。
lfs_block_t ack; // 整个Flash已被分配的块的个数。当值为0时意味着Flash再无可被分配的块。
uint32_t *buffer; // 位图。记录窗口内块的分配情况。值为0表示块空闲，值为1表示块已使用。
} free;2.2 算法
块分配器通过方法 lfs_alloc 来为文件系统分配一个空闲块。
/*
* \brief 分配空闲块
*
* \param[in] lfs 文件系统指针
* \param[out] block 分配到的块
*
* \return 分配成功或失败，类型实际上为enum lfs_error
*/
static int lfs_alloc(lfs_t *lfs, lfs_block_t *block) {
while (true) {
// 由分配器窗口内分配一个空闲块
// 如果找到到了一个空闲块，则会尝试更新窗口内的索引i，使其指向的块是空闲的。最后退出函数
while (lfs->free.i != lfs->free.size) {
lfs_block_t off = lfs->free.i;
lfs->free.i += 1;
lfs->free.ack -= 1;
if (!(lfs->free.buffer[off / 32] & (1U << (off % 32)))) {
*block = (lfs->free.off + off) % lfs->cfg->block_count;
while (lfs->free.i != lfs->free.size &&
(lfs->free.buffer[lfs->free.i / 32]
& (1U << (lfs->free.i % 32)))) {
lfs->free.i += 1;
lfs->free.ack -= 1;
}
return 0;
}
}
// 代码如果执行到这里，意味着在窗口里没有分配到空闲块
// 整个Flash没有空闲块了，返回空间不足的错误码
if (lfs->free.ack == 0) {
LFS_ERROR("No more free space %"PRIu32, lfs->free.i + lfs->free.off);
return LFS_ERR_NOSPC;
}
// 后移窗口偏移
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;
// 由文件系统内读取后移后窗口内块的使用情况，并在回调函数lfs_alloc_lookahead将块的使用情况标记在位图lfs->free.buffer中
memset(lfs->free.buffer, 0, lfs->cfg->lookahead_size);
int err = lfs_fs_rawtraverse(lfs, lfs_alloc_lookahead, lfs, true);
if (err) {
lfs_alloc_drop(lfs);
return err;
}
}
}
