FDS的GC操作

本文介绍FDS库的GC操作。

1. GC是什么

在FDS的概念中，写入Flash的数据以Record的形式保存。Record的格式为：

Flash只能以32-bit的字（Word）为单位进行写操作。Record Header包含三个字，分别是：

• TL Part: Record Key和Data Length
• IC Part: File ID和CRC Value
• ID Part: Record ID

有效的Record Key范围是（0x0001 ~ 0xBFFF）。如果Record Key == 0x0000，表示它是一条无效数据，或脏数据（Dirty Record）。

• 删除Record，实际是将该数据设置为脏数据。
• 更新Record，实际是将该数据设置为脏数据，再写入一个新数据。
• 读取Record，将忽略所有脏数据。

所以，删除和更新Record都会产生脏数据。

经过反复的写入、更新和删除操作，有效数据和脏数据最终占满整个FDS区域，此时我们需要从Flash中删除脏数据以释放空间，这个过程称之为垃圾回收，简称GC（Garbage Collection）。

GC完成以后，FDS区域中的脏数据都被物理删除。

2. GC的步骤

Flash空间物理上分成不同的页，每页起始地址按Word对齐，每页长度固定为4kB（1024 words）。在程序中可以指定若干页为FDS区域（FDS Area）。

FDS在每页的起始地址写入两个字的页头（Page Head），将其标记为有效的FDS页。根据页头的不同，FDS页分为数据页和交换页：

• 数据页的页头：0xDEADC0DE F11E01FE
• 交换页的页头： 0xDEADC0DE F11E01FF

二者仅最后一个比特不同，交换页可以通过对该比特写0变成数据页，反过来则不行。

上图中，灰色底色的方块表示脏数据，黄色底色的方块表示有效数据，空白处表示没有数据。

它描述了GC的四个步骤：

1. 将原数据页中的全部有效数据复制到交换页
2. 擦除原数据页
3. 将原交换页的页头改写成数据页
4. 对原数据页写入交换页的页头

从图中我们可以读到以下有用信息：

（1）脏数据与有效数据可能交替存放，没有固定规律

（2）交换页的实际地址经过GC后会发生变化

（3）有效数据在Flash中的绝对地址经过GC后会发生变化

（4）GC操作实际上执行了一次擦除页和大量的写操作，它是个Flash密集操作行为，所以在程序中不要频繁的执行GC

（5）图中没有明确表达出来但值得注意的是，GC总是一页执行完后再执行下一次，所以不能通过GC将两个数据页的数据“合并”到一个数据页中——这暗含了FDS的设计思路，用户不要关注Record在Flash中的存储细节

3. GC源代码

GC的源码比较繁复，读懂它是一个挑战。

FDS在初始化时候通过page_scan()函数遍历全部数据页，然后在各页中检查所有的Record Header，如果遇到脏数据，则通过全局变量m_pages.can_gc记录它。

在每次执行更新、删除操作产生脏数据的时候也记录在can_gc中。

FDS设计了一套状态机来分布执行GC

• GC_BEGIN
• GC_NEXT_PAGE
• GC_FIND_NEXT_RECORD
• GC_COPY_RECORD
• GC_ERASE_PAGE
• GC_DISCARD_SWAP
• GC_PROMOTE_SWAP
• GC_TAG_NEW_SWAP

在 GC_NEXT_PAGE 中，它通过m_pages.can_gc来找到需要执行GC的页。

在 GC_FIND_NEXT_RECORD 中，通过gc_record_find_next()和gc_record_copy()找到的有效数据依次复制到交换页。

处理完全部数据，跳到GC_ERASE_PAGE 中，使用gc_page_erase()将该数据页擦除。

然后进入GC_PROMOTE_SWAP，使用gc_swap_promote()将原交换页的页头改成数据页页头。

然后进入GC_TAG_NEW_SWAP， 使用gc_page_erase() 将刚才擦除的数据页写成交换页。

然后进入GC_NEXT_PAGE，执行下一轮GC。

整个过程在以下两个函数中来回反复跳转：

• gc_execute()
• gc_state_advance()

不知道使用了什么设计模式，实现代码很奇怪，两个函数在状态机之间跳来跳去，看的眼睛疼。

（完）