首页 > 代码库 > Yaffs2文件系统垃圾回收机制诠释

Yaffs2文件系统垃圾回收机制诠释

悲剧,图片贴不出来。。。   

 回收顺序:

    一)回收最老块(500次回收才进行一次回收)
    二)回收最老的脏块(有优先回收的前提下)
    三)回收最老的优先回收块(有优先回收的前提下)(这里目前我认为是优先回收且为最老的脏块)
    四)回收最脏(脏指在阀值范围内)且最老的块(正常情况下)
    五)回收最老的脏块(这种情况是多次找不到回收块,说明当前的系统很干静,可回收的垃圾很少);


    思考点:
    1、出现ECC纠正的块,是否有必要超过三次进行坏块标记?
    2、出现ECC错误的块,是否有必须回收?
    3、垃圾回收时是否可以进行伪坏块检查?制定一个严谨的检查标准?

    如何加快yaffs2文件系统垃圾回收机制?
    网上常见的说法就是yaffs2文件系统有一个控制阀值,这个阀值控制着yaffs2文件系统的回收,阀值控制相当严格,一般不容易满足条件;但实际上除了这个阀值外yaffs2文件系统还有另外一个控制回收时间的参数,这个参数就是dev->gc_not_done,这个参数在没有找到合理的回收块时会累加,当达到10或者20(两种情况,主要是20),yaffs2文件系统将直接回收最老的脏块,无形中大大放宽了回收标准。如果将这里的10修改为0,那么可以保证在有垃圾可回收的情况下每次都会命中一个回收块,不用再10次一块。当然加不加速,最终都会回收得干干净,仅仅是时间上的问题。
    下面是源码修改(加快回收):
  
  yaffs_guts.c
unsigned int yaffs_gc_not_done = 10;
#if (LINUX_VERSION_CODE > KERNEL_VERSION(2, 5, 0))
module_param(yaffs_gc_not_done, uint, 0644);
#else
MODULE_PARM(yaffs_gc_not_done, "i");
#endif


2769行左右:

 
if (!selected && dev->param.is_yaffs2 &&
	    dev->gc_not_done >= (background ? yaffs_gc_not_done : 2 * yaffs_gc_not_done)) {
		yaffs2_find_oldest_dirty_seq(dev);
		if (dev->oldest_dirty_block > 0) {
			printk ("^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
			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;
			printk ("#################################alloc_page : %d\n", dev->alloc_page);
			
		}
	}

   在想加快回收时在命令行执行如下操作:echo 0 > /sys/modules/yaffs/parameters/yaffs_gc_not_done
    加快一段时间后再恢复到之前的回收速度:echo 10 > /sys/modules/yaffs/parameters/yaffs_gc_not_done

    如何确定当前文件系统下有多少可回收的空间?
    

    下面开始YFAAS2文件系统垃圾回收具体分析:

    在我们对yaffs2文件系统使用过程中,垃圾回收机制无疑最为重要的一个环节。
    垃圾回收处理都是在一个后台运行的进程中执行的,每隔一段时间进行一次回收操作,这个时间间隔由回收的紧迫性决定;而回收的紧迫性又由flash的能使用的空间息息相关,下面具体分析垃圾回收机制。

    回收是建立在文件系统被修改后的,文件系统被修改后,dev->is_checkpointed这个参数将会清0,表示文件系统被修改,之前保存的checkpt信息被标记为无效。所以回收的前提是dev->is_checkpointed = 0。当你在命令行界面执行sync后,你会发现垃圾回收机制被关闭了。
        
    第一步就是计算回收的紧急程度,以便于计算下一次回收是什么时候;
    yaffs_bg_gc_uregency(dev);
    这个函数就是计算具体的回收紧急程度。
    
    计算回收紧急程度前先了解两个参数的意义:
    1、dev->n_erased_blocks -> 表示未被使用的好块,dev->n_erased_blocks * 64 用C表示;
    2、dev->n_free_chunks -> 包括两部分,一部分是未被开发的页,用C表示;另一部分是被删除后无效数据页,用B表示;

    

        

    如果B类型小于64,表示紧急代号为0,不紧急,下次回收间隔为HZ * 2;
    如果C类型大于(B+C)的二分之一,表示紧急代号为0,不紧急,下次回收间隔为HZ * 2 ;
    如果C类型大于(B+C)的四分之一,小于(B+C)的二分之一,表示紧急代号为1,较紧急,下次回收间隔为HZ / 10 + 1;
    其它表示紧急代号为2,非常紧急,下次回收间隔为HZ / 20 + 1。

    计算完紧急序列后,下面开始直接的扫描回收块了。

    第二步:扫描真实的回收块号。
    扫描有两种情况,一种是低力度回收,另一种是高力度回收;力度由flash的使用情况决定,用aggressive标识力度大小。当flash中未被使用的块数量小于保留块时,力度标识为1,力度强;否则力度标识为0,力度普通。
    
    保留块包括为yaffs2文件系统保留的5个块和供checkpoint高速挂载机制使用的块(这个不固定,由文件系统使用情况决定)。
    
    现在不得不认识一个新参数dev->gc_block,它表示当前回收机制正在回收的块,小于1表示当前没有回收块;既然现在是进行回收,那么这个gc_block当且认为它为0。
    
    条件1:如果dev->gc_block < 1 && aggressive = 0表示低回收力度条件下进行周期性刷新查找最老块;这里出现一个新名词,何为最老块?在yaffs2文件系统中,每个块先有一个块号,块号从0开始,另外每个被分配出去的块同时会被分配一个序列号,这个序列号随着一个块被分配后累加(制作烧片时,所有的序列号都相同);被后面被分配出去的序列号就越大,越大说明这个块就越新;反之,序列号越小,说明越早被分配出去,它也就是最老的块了。周期性刷新查找最老块是调用yaffs2_find_refresh_block()函数。
    上面提到周期性,多少个周期由参数dev->param.refresh_period决定;yaffs2文件系统默认500个周期刷新一次最老块;代码运行时会将dev->param.refresh_period的值赋给dev->refresh_skip,每一轮(这里指每回收一个块)它会减1,直到减到0,表示现在可以进行最老块扫描,同时将dev->param.refresh_period赋值给dev->refresh_skip,为下一个500次做准备。
    扫描最老块就是扫描整个Flash中所有的块中序列号最小的块,下面贴出这部分代码:
    
	for (b = dev->internal_start_block; b <= dev->internal_end_block; b++) {

		/*已经全部被分配出去的块*/
		if (bi->block_state == YAFFS_BLOCK_STATE_FULL) {

			 //每一个block中都有seq_number,记录被分配的顺序, seq_number是按照0  1  2  3 这样累加的
			if (oldest < 1 || bi->seq_number < oldest_seq) {
				oldest = b;
				oldest_seq = bi->seq_number;
				//所以seq_number值越小,说明它越先被分配,即从分配到现在一直很稳定
			}
		}
		bi++;
	}

    每500次后一定会扫描到一个最老块,也就是说500个来回后,dev->gc_block一定不会再小于1。后续代码将会将dev->gc_block对应的块回收掉。

    条件2:条件1中未达到扫描到最老块的情况,这时dev->gc_block依然小于1。进一步进行坏块回收扫描。这次扫描与力度有一定的联系。
    扫描函数为yaffs_find_gc_block(struct yaffs_dev *dev, int aggressive, int background);
    这里又出现一个新名词:优先回收;什么情况下会出现优先回收呢?这个情况有好几种,下面一一列举。
    1、写操作失败,主要是写调用底层接口失败;
    2、读操作失败,包括读调用底层接口失败、读ECC纠正和读ECC出错。

    出现上面的情况都会使当前操作块进入优先回收状态,同时标识整个Flash中有优先回收块。垃圾回收机制运行时读到这个标识有效且力度aggressive为0的情况时,会再次进行回收块扫描;但这次扫描的条件不一样了;首先必须是优先回收的块,其次是标识优先回收的块还必须是最老的块;总的来说,要想这两个条件同时出现,我个人感觉难于上青天,但是它一定还是会被回收,只是早晚的问题;为什么了?因为yaffs2回收总是以最老块为回收标准,只要yaffs2文件系统有写访问,总有一天这时的序列号会成为最老的。
    
     
	/*如果仔细阅读过yaffs的write函数的话,如果在写某一页的时候发生错误,
	 * yaffs就把该页标记为gc优先回收。has_pending_prioritised_gc表示
	 * yaffs设备上有优先被回收的block,bi->gc_prioritise表示该blokc优先
	 * 被gc回收。yaffs_find_gc_block首先扫描该设备上的所有的block的信息(当
	 * 然只有满block会被回收,如果一页发生写错误的时候,yaffs会跳过该块
	 * 上的其余页,并将该块标记为FULL),同时通过yaffs_block_ok_for_gc
	 * 函数来查看该块是不是yaffs设备上的最老的脏块。在这种情况,
	 * 并须符合上面的两种情况才会被选中。(1)该页被标记为优先回收,并且为
	 * FULL,(2)该页是设备上最老的脏块。*/

	/* First let‘s see if we need to grab a prioritised block */
	/*表示[有]gc优先回收的块*/
	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++) {

			/*上面的has_pending_prioritised_gc表示有优先的块,而这里
			 * 的gc_prioritise表示这个块被定为优先了*/
			if (bi->gc_prioritise) {
				/*打上标志,优先者存在*/
				prioritised_exist = 1;
				if (bi->block_state == YAFFS_BLOCK_STATE_FULL &&
						/*查找是不是最老的脏块*/
				    yaffs_block_ok_for_gc(dev, bi)) {
					/*第一:优先gc
					 * 第二:是最老的脏块(我认为这个条件可能永远达不到?)*/
					/*记录块号?*/
					selected = i;
					prioritised = 1;
				}
			}
			bi++;
		}

		/*
		 * If there is a prioritised block and none was selected then
		 * this happened because there is at least one old dirty block
		 * gumming up the works. Let‘s gc the 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 &&
		    !selected && dev->oldest_dirty_block > 0)
			selected = dev->oldest_dirty_block;

		/*这是对于出错情况的一种修复,上面只有在dev->has_pending_prioritised_gc
		 * 表示该设备中存在优先选择的块时才进行遍历的查找。介理查找发现
		 * 根本没有发现所说的优先回收的块,就需要对
		 * dev->has_pending_prioritsied_gc进行修复。*/
		if (!prioritised_exist)	/* None found, so we can clear this */
			dev->has_pending_prioritised_gc = 0;
	}

    上面如果条件中优先存在(prioritised_exist为真),满足可回收条件的块不存在,但是最老脏块存在,这时这个最老块将会被标识为回收块。这里为什么优先回收最老脏块,而不优先回收标识为优先回收的块了?这是因为标识为优先回收的块基本上都是出现异常的块,这些块回收的风险比较大,故而优先回收最老的块。最老脏块被一一回收了,最后还得回收那个异常的优先块。(这里有一点思考?出现ECC错误的块还有没有必须回收,不怕因错误影响文件系统的正常运行?)

    这里还有一点思考,在有优先回收块的时候,回收原则是优先+最老脏块,优先这个条件不难出现,但是最老脏块就不一定了;如果说这个优先块被优先时没有一个脏页(也就是64个全为有效数据),那就不存在脏的说法,最终这个块将无法在优先机制这块被回收?想被回收也要等到N个500后才有可能被回收?
    
    上面是有优先回收标识的情况,正常情况下是不会出现优先回收这回事;现在开始走正常化路线。正常回收路线是基于flash的一段范围进行扫描的;这个范围就由我们上面分析过的力度决定。
    分析前先了解两个参数:
    1、threshold:这个参数可以认为是一个回收阀值;对于一个块中,如果有效数据chunk最少于这个阀值,那么这个块基本中也就可以回收了(有前提条件的)。
    2、iterations:这个参数可以认为是扫描回收的一个范围;在力度低的情况下,我并不去扫描所有的块,因为扫描所有块这个动作是相当耗时的,得不偿失。
    
    n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
    力度大时:
    threshold = 64; 
    iterations = n_blocks;
    力度小时:
    threshold = 4; 
    iterations = n_blocks / 16 + 1;(这个参数最大值为100,也就是力度低时,最多在100个块中回收)。

    上面计算了回收阀值与回收范围,现在开始正式回收扫描。
    这里先再了解两个参数:
    1、dev->gc_dirtiest -> 表示设备上可回收的最脏块(注意这里并不是表示块上所有的数据都无效,仍然 存在有效数据);
    2、dev->gc_pages_in_use -> 表示被回收的最脏页中有效数据 的chunk数,其实这个值也就是相当于回收的一个阀值了,扫描时,会用这个参数与阀值对比,看是否需要进行回收。

    这两个参数默认情况下应该都是小于1的;
    这里还有一个参数需要了解,dev->gc_block_finder,这个参数记录的是上次回收范围的结束块;对于低力度回收时,我们扫描的空间只是整个flash的中的一个小范围,每次回收完成后,下次回收接着上次的结束块继续扫描一段范围。
    下面是计算最脏块的条件:
    1、块为满块,所有chunk都被申请过;
    2、有效数据chunk数量小于64,我这里写成64,这个参数跟flash的物理性质有关;(这个条件有必要?)
    3、当前不存在最脏块或者有效数据chunk数量小于dev->gc_pages_in_use;
    4、块为最老脏块。
    如果条件成立记录当前块为dev->gc_dirtiest,同时记录dev->gc_pages_in_use = pages_used;
    条件3中后半部分用于甄选最脏块,也就是有效数据chunk最少。

    在当前范围内扫描后,如果最脏块扫描出现来了,且dev->gc_pages_in_use这个参数小于等于阀值threshold,那么表示这个块可以进行回收,否则表示没有找到回收块;
    if (dev->gc_dirtiest > 0 && dev->gc_pages_in_use <= threshold)
        selected = dev->gc_dirtiest;
     
    到这里我认为还是没有找到回收块,还要继续扫描;
    扫描之前了解一个新的参数:dev->gc_not_done,这个参数表示没有找到可以回收的次数,如果gc_not_done超过一定的限额,就表示yaffs2的当前回收很干净了或者资源已经十分紧张了,这时就需要降低回收的标准,如果何降低呢?
    这里往回走一下,之前在计算回收阀值时,有提到threshold这个参数,它由dev->gc_not_done决定,dev->gc_not_done这个参数越大,threshold就越大,回收标准也就越低。而dev->gc_not_done这个参数由回收失败次数决定;当dev->gc_not_done这个参数超过10后,情况又变了!
    什么情况呢?回收不再受任何限制,直接找到一个最老的脏块,回收它(这次的回收不再参照阀值)。没有最老块的话,那说明系统无垃圾可回收或者资源已经快没有了。
    系统回收最理想的情况就是dev->gc_not_done累加,每10次一个周期,每个周期都没有找到回收块(系统太干净了)。
    资源紧张是网络上某某人的说法,当且不论他是否正确。
    无垃圾可回收是我个人验证的结果,当前的系统已经很干净了。
    
    
    第三步:回收块已经找到,正式进行回收处理。
    首先,如果待回收的块是无效掉的checkpt块或者这个块上的数据全部分无效;则直接调用yaffs_block_became_dirty(dev, block)进行擦除回收。回收前,检查当前块是否使用了summary机制,如果使用了,就清掉summary在chunk_bit中的位图,便于回收。

    其次,就是特殊情况了,特殊情况处理起来一般都比较麻烦。
    后面的处理简而言之就是将整个块中有效数据拷贝到新的块中,拷贝完成后执行回收擦除处理。
    这里的拷贝有点特殊,每次回收最多能拷贝5个chunk,也就是说在阀值较大或者最后一种情况下(回收最老脏块),回收块中有效数据chunk一般都是很大的,远远超过5,这时回收机制只能回收一次拷贝5块,直到全部拷贝完成,才回收擦除这个块。