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()

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

(完)

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据