Yaffs的垃圾回收机制

由于NANDFLASH的独特的特性，使得overwrite变得很困难，而且性能低下。虽然变通的block-mapping机制能够很好的解决这个问题，但是同时也引入了新的问题，即如何确切的了解文件系统的空闲空间，如何从脏页中回收空间等等一系列问题。

我们知道由于VFS缓存机制的引入使得问题变得更加复杂（yaffs没有使用内核的缓存页，但是它使用内部的yaffs_cache）。

Yaffs提供一种gc机制，即垃圾回收，在文件系统内部空间不足时，通过回收一些脏页来重新获得可以使用的空间。

垃圾回收都是由后台进程来定期的完成的，因为这样的工作很费时，如果真的等到逼不得已的时候才去进行垃圾回收的话，耗时就很长了。那么为什么不设定一个阈值，让后台进程定期的进行垃圾回收呢？

static int yaffs_check_gc(struct yaffs_dev *dev, int background)

其中输入参数dev为需要进行垃圾回收的设备（每个设备上只能挂载一个yaffs文件系统），background用于表示是否是后台运行的。由yaffs_bg_gc函数调用的时候background始终为1.

if (!dev->is_checkpointed) {

urgency = yaffs_bg_gc_urgency(dev);

gc_result = yaffs_bg_gc(dev, urgency);

if (urgency > 1)

next_gc = now + HZ / 20 + 1;

else if (urgency > 0)

next_gc = now + HZ / 10 + 1;

else

next_gc = now + HZ * 2;

}

yaffs_bg_start函数中启动了后台进程yaffs_bg_thread_fn，该进程通过调用yaffs_bg_gc函数来进行垃圾回收。

上面提到了垃圾回收是定期的，这太过于简单化了，前面提到垃圾回收的过程是很耗时，那么如果文件系统当前的空闲块比较多（已经满足大多数情况下的使用），就完全可以推迟垃圾回收。所以垃圾回收其实是一个不定期的时候，具体是有函数yaffs_bg_gc_urgency进行判断的，其中变量next_gc指下次进行垃圾回收的时间。

yaffs_bg_gc具体实现垃圾回收，整个函数是有一个do while循环完成的。

do {

max_tries++;

checkpt_block_adjust = yaffs_calc_checkpt_blocks_required(dev);

函数yaffs_calc_checkpt_blocks_required用于计算check pointer所需要的空间，关于checkpt我也不甚了解，只能用yaffs文档中的一段描述来回答：

Boot-time scanning to build the file structure lists only requires one pass reading NAND. If proper shutdowns happen the current RAM summary of the filesystem status is saved to flash, called 'checkpointing'. This saves re-scanning the flash on startup, and gives huge boot/mount time savings.

/* If we need a block soon then do aggressive gc. */

if (dev->n_erased_blocks < min_erased)

aggressive = 1;

如果系统的空闲block数小于 min_erased的下线。那么就需要启动aggressive 模式的垃圾回收了（力度不一样）。

else {

if (!background

    && erased_chunks > (dev->n_free_chunks / 4))

break;

if (dev->gc_skip > 20)

dev->gc_skip = 20;

if (erased_chunks < dev->n_free_chunks / 2 ||

    dev->gc_skip < 1 || background)

aggressive = 0;

else {

dev->gc_skip--;

break;

}

}

有后台进程运行的时候，由于background为1，所以aggressive = 0.当然也可能由于if (dev->n_erased_blocks < min_erased)导致aggressive = 1.但是一般不可能出现这种情况，由于后台进程的周期性，使得文件系统都保留一定的空闲块。

if (dev->gc_block < 1 && !aggressive) {

dev->gc_block = yaffs2_find_refresh_block(dev);

dev->gc_chunk = 0;

dev->n_clean_ups = 0;

}

其中dev->gc_block用于记录被gc后台进程正在回收的block的块号，如果没有正在回收的blcok，并且aggressive=0的话，调用 yaffs2_find_refresh_block函数查找一个block用于回收。

u32 yaffs2_find_refresh_block(struct yaffs_dev *dev)

for (b = dev->internal_start_block; b <= dev->internal_end_block; b++) {

if (bi->block_state == YAFFS_BLOCK_STATE_FULL) {

if (oldest < 1 || bi->seq_number < oldest_seq) {

oldest = b;

oldest_seq = bi->seq_number;

}

}

bi++;

}

函数遍历地查找yaffs设备的所有的block，其中seq_number是一个全局的变量，用于记录block分配的先后顺序，这样就可以找出最老的block了。试想一下：如果刚刚垃圾回收的一些数据在后面又被overwrite，势必又产生一些垃圾，这样的块的回收的价值就不大。那么代表他在设备稳定存在的时间足够长（如果被修改的话，seq也会变），那么也就意味着它其中的数据是稳定的。这就是垃圾回收机制中所谓的cold-hot的概念。很多文章中将flash类型文件系统中的数据分为hot data和cold data。显然hot data由于频繁的更新，它回收的意义就不明显了。

上面是aggressive=0的情况，说明yaffs中缺少空闲块的情况还不太严重。如果aggressive=1，就需要调用yaffs_find_gc_block函数来选择被回收的块。

if (dev->gc_block < 1) {

dev->gc_block =

    yaffs_find_gc_block(dev, aggressive, background);

dev->gc_chunk = 0;

dev->n_clean_ups = 0;

}

yaffs_find_gc_block稍显复杂，下面我们一步步的分析，跟着上面的后台进程到这儿的话，yaffs_find_gc_block的输入参数aggressive = 0.background=1.

static unsigned yaffs_find_gc_block(struct yaffs_dev *dev,

    int aggressive, int background)

{

int i;

int iterations;

unsigned selected = 0;

int prioritised = 0;

int prioritised_exist = 0;

struct yaffs_block_info *bi;

int threshold;

/* First let's see if we need to grab a prioritised block */

if (dev->has_pending_prioritised_gc && !aggressive) {

dev->gc_dirtiest = 0;

bi = dev->block_info;

for (i = dev->internal_start_block;

     i <= dev->internal_end_block && !selected; i++) {

if (bi->gc_prioritise) {

prioritised_exist = 1;

if (bi->block_state == YAFFS_BLOCK_STATE_FULL &&

    yaffs_block_ok_for_gc(dev, bi)) {

selected = i;

prioritised = 1;

}

}

bi++;

}

如果仔细阅读过yaffs的write函数的话，如果在写某一页的时候发生错误，yaffs就把该页标记为gc优先回收。has_pending_prioritised_gc表示yaffs设备上有优先被回收的block，bi->gc_prioritise表示该block优先被gc回收。yaffs_find_gc_block首先扫描该设备上的所有block的信息（当然只有满block会被回收，如果一页发生写错误的时候，yaffs会跳过该块上的其余也，并将该块标记为FULL），同时通过yaffs_block_ok_for_gc函数来查看该块是不是yaffs设备上的最老的块。在这种情况，并须符合上面的两种情况才会被选中。（1）该页被标记为优先回收，并且为FULL，（2）该页是设备上最老的块。

if (prioritised_exist &&

    !selected && dev->oldest_dirty_block > 0)

selected = dev->oldest_dirty_block;

如果通过上面的遍历查找，发发现了被标记为优先回收的块，selected  = 0。，也就是说yaffs_block_ok_for_gc返回0，那么selected = dev->oldest_dirty_block。在这儿我们看到了yaffs的选择，它优先选择了最老的脏块用于回收。其实yaffs做出这种选择是可以理解的。我想可能出于下面的考虑：（1）上面说道了在发生写错误的时候将一些标记为优先回收块，但是既然发生了写错误，该页被回收之后还可能发生写错误，那么这个回收就存在很大的风险。（2）yaffs没有专门的均衡损耗的处理，这儿选择最老的块可能就是均衡损耗的一方面考虑。同时需要注意这儿dev->oldest_dirty_block的描述，这儿的dirty的意思是该块中没有可用数据，即整块中的数据全部被废弃，注意与后面的gc_dirtiest比较。

if (!prioritised_exist) /* None found, so we can clear this */

dev->has_pending_prioritised_gc = 0;

这是对于出错情况的一种修复，上面只有在dev->has_pending_prioritised_gc 表示该设备中存在优先选择的块时才进行遍历的查找。但是查找发现根本没有发现所说的优先回收的块，就需要对dev->has_pending_prioritised_gc进行修复。再次感慨一下内核源码的健壮性。

if (!selected) {

int pages_used;

int n_blocks =

    dev->internal_end_block - dev->internal_start_block + 1;

if (aggressive) {

threshold = dev->param.chunks_per_block;

iterations = n_blocks;

} else {

int max_threshold;

if (background)

max_threshold = dev->param.chunks_per_block / 2;

else

max_threshold = dev->param.chunks_per_block / 8;

if (max_threshold < YAFFS_GC_PASSIVE_THRESHOLD)

max_threshold = YAFFS_GC_PASSIVE_THRESHOLD;

threshold = background ? (dev->gc_not_done + 2) * 2 : 0;

if (threshold < YAFFS_GC_PASSIVE_THRESHOLD)

threshold = YAFFS_GC_PASSIVE_THRESHOLD;

if (threshold > max_threshold)

threshold = max_threshold;

iterations = n_blocks / 16 + 1;

if (iterations > 100)

iterations = 100;

}

上面的代码稍显有点长，但是它的作用就一句话，根据当前设备中空闲块得数目来确定本次垃圾回收的力度，参数iterations 用于表示回收需要查找的块数（可以认为是力度）。如果aggressive=1的话，毫无疑问需要查找设备上的所有块，iterations = n_blocks。

for (i = 0; i < iterations && (dev->gc_dirtiest < 1 ||

      dev->gc_pages_in_use > YAFFS_GC_GOOD_ENOUGH); i++) {

dev->gc_block_finder++;

if (dev->gc_block_finder < dev->internal_start_block ||

    dev->gc_block_finder > dev->internal_end_block)

dev->gc_block_finder = dev->internal_start_block;

bi = yaffs_get_block_info(dev, dev->gc_block_finder);

pages_used = bi->pages_in_use - bi->soft_del_pages;

if (bi->block_state == YAFFS_BLOCK_STATE_FULL &&

    pages_used < dev->param.chunks_per_block &&

    (dev->gc_dirtiest < 1 ||

     pages_used < dev->gc_pages_in_use) &&

    yaffs_block_ok_for_gc(dev, bi)) {

dev->gc_dirtiest = dev->gc_block_finder;

dev->gc_pages_in_use = pages_used;

}

}

dev->gc_dirtiest用于表示设备上回收的最脏的块（注意这儿的描述，最脏，隐藏的含义是说该块上不全是无效数据，任然存在有效数据），如果没有标识的话，就需要遍历的查找iterations所标识的块的范围。dev->gc_pages_in_use是指上一个被回收的最脏页中有效数据的chunk数。这样通过一个遍历找出设备上最脏的块。

if (dev->gc_dirtiest > 0 && dev->gc_pages_in_use <= threshold)

selected = dev->gc_dirtiest;

如果该块中的有效数据chunk数已经低于了阈值，那么该页就可以被回收。

if (!selected && dev->param.is_yaffs2 &&

    dev->gc_not_done >= (background ? 10 : 20)) {

yaffs2_find_oldest_dirty_seq(dev);

if (dev->oldest_dirty_block > 0) {

selected = dev->oldest_dirty_block;

dev->gc_dirtiest = selected;

dev->oldest_dirty_gc_count++;

bi = yaffs_get_block_info(dev, selected);

dev->gc_pages_in_use =

    bi->pages_in_use - bi->soft_del_pages;

} else {

dev->gc_not_done = 0;

}

}

其中dev->gc_not_done用于表示gc没有找到可以回收的次数，如果gc_not_done超过了一定的限额。就表示yaffs的资源已经十分的紧张了，这时候就需要降低回收的标准了。先通过函数yaffs2_find_oldest_dirty_seq（注意在这个函数中加入了对b->soft_del_pages考虑，我们都知道fat文件系统中一些删除的数据是可以恢复的。为什么数据被删除后还可以能恢复呢？因为删除并没有数据真正的删除掉，而只是在软件上标记为删除掉。所以这儿再一次降低了gc的标准）找出设备上最老的的block，然后selected = dev->oldest_dirty_block回收这个最老的block。可能有人会问上面代码中的dev->gc_not_done = 0有什么用？看似没有，但是在上面的代码中有：

threshold = background ? (dev->gc_not_done + 2) * 2 : 0;

如果dev->gc_not_done = 0的话，就等于降低了回收脏页时候的下线条件。

回到yaffs_check_gc函数中，我们可以看到在aggressive在等于1和不等于1的两种情况下，gc回收的力度，特别在aggressive=1的情况下，一次又一次的降低gc的下线标准，（因为gc的资源太紧张了，必须回收到空闲块）。

if (dev->gc_block > 0) {

dev->all_gcs++;

if (!aggressive)

dev->passive_gc_count++;

yaffs_trace(YAFFS_TRACE_GC,

"yaffs: GC n_erased_blocks %d aggressive %d",

dev->n_erased_blocks, aggressive);

gc_ok = yaffs_gc_block(dev, dev->gc_block, aggressive);

}

在找到了可用于回收的block之后，下面接着处理的就是真正的垃圾回收过程。关于垃圾回收，用yaffs文件系统内核文档中描述就是：

Garbage collection is performed by copying the valid data pages into new data pages thus rendering all the pages in this block dirty and freeing it up for erasure. 

void yaffs_block_became_dirty(struct yaffs_dev *dev, int block_no)

if (bi->block_state == YAFFS_BLOCK_STATE_FULL)

bi->block_state = YAFFS_BLOCK_STATE_COLLECTING;

如果该页是满页，那么在回收过程中将该块的状态设为YAFFS_BLOCK_STATE_COLLECTING。

if (block_no == dev->gc_block)

dev->gc_block = 0;

/* If this block is currently the best candidate for gc

 * then drop as a candidate */

if (block_no == dev->gc_dirtiest) {

dev->gc_dirtiest = 0;

dev->gc_pages_in_use = 0;

}

同时由于该页将要被回收，那么需要将dev->gc_block、dev->gc_dirtiest以及dev->gc_pages_in_use等复位。

if (!bi->needs_retiring) {

yaffs2_checkpt_invalidate(dev);

erased_ok = yaffs_erase_block(dev, block_no);

if (!erased_ok) {

dev->n_erase_failures++;

}

}

bi->needs_retiring用于表示该块是否重试，注意yafs_write_new_chunk函数中关于needs_retiring的相关操作，当写失败的时候在函数yaffs_handle_chunk_wr_error将needs_retiring置1，即当发生错误的时候该页需要重试。如果不需要重试，那么该页可以直接擦除。

{

u8 *buffer = yaffs_get_temp_buffer(dev);

yaffs_verify_blk(dev, bi, block);

max_copies = (whole_block) ? dev->param.chunks_per_block : 5;

old_chunk = block * dev->param.chunks_per_block + dev->gc_chunk;

for (/* init already done */ ;

     ret_val == YAFFS_OK &&

     dev->gc_chunk < dev->param.chunks_per_block &&

     (bi->block_state == YAFFS_BLOCK_STATE_COLLECTING) &&

     max_copies > 0;

     dev->gc_chunk++, old_chunk++) {

if (yaffs_check_chunk_bit(dev, block, dev->gc_chunk)) {

/* Page is in use and might need to be copied */

max_copies--;

ret_val = yaffs_gc_process_chunk(dev, bi,

old_chunk, buffer);

}

}

yaffs_release_temp_buffer(dev, buffer);

}

其中函数yaffs_check_chunk_bit用于查看位图来确定该chunk是否被使用，如果该chunk正在被使用（即包含有效数据），那么调用yaffs_gc_process_chunk来进行数据的搬运。

到现在为止，被回收的block已经不包含任何有用的数据信息，在下一次垃圾回收的时候会被擦除。同时由于数据的删除，还有一些clearup的工作，在此不再赘述。

事实上，除了yaffs_bg_gc调用了yaffs_check_gc函数之外。还分别在yaffs_wr_data_obj，yaffs_update_oh以及yaffs_check_gc中主动的调用了yaffs_check_gc函数，只不过此时的输入参数background为0.

至此，通过极其冗长的篇幅分析了yaffs垃圾回收的过程。