Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1420743
  • 博文数量: 124
  • 博客积分: 4078
  • 博客等级: 中校
  • 技术积分: 3937
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-21 11:28
个人简介

新博客:http://sparkandshine.net/

文章分类

全部博文(124)

分类: 嵌入式

2012-01-07 15:21:54

摘要:

    本文深入源码分析了Coffee文件系统垃圾回收collect_garbage技术细节,包括回收模式mode、sector_status、COFFEE_SECTOR_COUNT、get_sector_status、isolate_pages等。


一、collect_garbage

1.1 垃圾回收概述

    FLASH先擦后写的特性,也就不可能每次把失效的页及时擦除(效率低下。有些页可能还没失效,则需要转移这些页的数据,才能擦除),只能在适当时候才擦除,这就是垃圾回收。Coffee文件系统默认情况下,文件删除并没有立即进行垃圾回收,而是待到没有空间可用的时候再回收(可理解成批处理),显然这样做有一个明显的缺点,垃圾回收会占用比较长的时间。collect_garbage源代码如下:

  1. static void collect_garbage(int mode) //mode见1.2
  2. {
  3.   uint16_t sector;
  4.   struct sector_status stats; //sector_status结构体用于统计垃圾回收页面情况,见1.3
  5.   coffee_page_t first_page, isolation_count;

  6.   PRINTF("Coffee: Running the file system garbage collector in %s mode\n", mode == GC_RELUCTANT ? "reluctant" : "greedy");
  7.   
  8.   /*The garbage collector erases as many sectors as possible. A sector is erasable if there are only free or obsolete pages in it. */

  9.   for(sector = 0; sector < COFFEE_SECTOR_COUNT; sector++) //COFFEE_SECTOR_COUNT见1.4
  10.   {
  11.     isolation_count = get_sector_status(sector, &stats); //见二
  12.     
  13.     PRINTF("Coffee: Sector %u has %u active, %u obsolete, and %u free pages.\n", sector, (unsigned)stats.active, (unsigned)stats.obsolete, (unsigned)stats.free);

  14.     if(stats.active > 0)
  15.     {
  16.       continue;
  17.     }

  18.     if((mode == GC_RELUCTANT && stats.free == 0) || (mode == GC_GREEDY && stats.obsolete > 0))
  19.     {
  20.       first_page = sector * COFFEE_PAGES_PER_SECTOR;
  21.       if(first_page < *next_free)
  22.       {
  23.         *next_free = first_page;
  24.       }

  25.       if(isolation_count > 0) //找到isolation_count个连续的孤立页
  26.       {
  27.         isolate_pages(first_page + COFFEE_PAGES_PER_SECTOR, isolation_count); //见1.5
  28.       }

  29.       COFFEE_ERASE(sector);
  30.       PRINTF("Coffee: Erased sector %d!\n", sector);

  31.       if(mode == GC_RELUCTANT && isolation_count > 0) //如果是GC_RELUCTANT回收策略,一旦有逻辑分区被擦除就停止
  32.       {
  33.         break;
  34.       }
  35.     }
  36.   }
  37. }

1.2 回收模式mode

    系统提供了两种垃圾回收机制:GC_GREEDY和GC_RELUCTANT,前者垃圾回收过程中,擦除尽可能多的区(即贪心回收),后者擦除一个区后就停止。当创建文件或者创建日志,找不到可用空间时(reserve函数),就会用贪心回收GC_GREEDY。而删除文件采用的是后一种(前提是COFFEE_EXTENDED_WEAR_LEVELLING 为0且gc_allowed为1)。两种回收机制源代码如下: 

  1. #define GC_GREEDY 0 
  2. #define GC_RELUCTANT 1

1.3 sector_status

sector_status结构体用于垃圾回收的统计页面情况,如下:

  1. //struct sector_status stats;
  2. struct sector_status
  3. {
  4.   coffee_page_t active;
  5.   coffee_page_t obsolete;
  6.   coffee_page_t free;
  7. };

1.4 COFFEE_SECTOR_COUNT

    Coffee文件系统是按逻辑区擦除的,之所以有这个是为了应付大的存储设备(比如SD卡),在这种情况下,将其设置大一点可加快顺序扫描速度。COFFEE_SECTOR_COUNT宏定义如下:

  1. #define COFFEE_SECTOR_COUNT (unsigned)(COFFEE_SIZE/COFFEE_SECTOR_SIZE)

1.5 isolate_pages

isolate_pages源码如下:

  1. //isolate_pages(first_page + COFFEE_PAGES_PER_SECTOR, isolation_count);
  2. static void isolate_pages(coffee_page_t start, coffee_page_t skip_pages)
  3. {
  4.   struct file_header hdr;
  5.   coffee_page_t page;

  6.   /*Split an obsolete file starting in the previous sector and mark the following pages as isolated.*/
  7.   
  8.   /***将file_header的flags中的A位、I位置1,其他位为0***/
  9.   memset(&hdr, 0, sizeof(hdr));
  10.   hdr.flags = HDR_FLAG_ALLOCATED | HDR_FLAG_ISOLATED;

  11.   /*Isolation starts from the next sector.*/
  12.   for(page = 0; page < skip_pages; page++)
  13.   {
  14.     write_header(&hdr, start + page);
  15.   }
  16.   PRINTF("Coffee: Isolated %u pages starting in sector %d\n", (unsigned)skip_pages, (int)start/COFFEE_PAGES_PER_SECTOR);
  17. }


二、get_sector_status

get_sector_status源代码如下:

  1. //isolation_count = get_sector_status(sector, &stats);
  2. static coffee_page_t get_sector_status(uint16_t sector, struct sector_status *stats)
  3. {
  4.   static coffee_page_t skip_pages;
  5.   static char last_pages_are_active;
  6.   struct file_header hdr;
  7.   coffee_page_t active, obsolete, free;
  8.   coffee_page_t sector_start, sector_end;
  9.   coffee_page_t page;

  10.   memset(stats, 0, sizeof(*stats));
  11.   active = obsolete = free = 0;

  12.   /*get_sector_status() is an iterative function using local static state. It therefore requires the the caller loops starts from sector 0 in order to reset the internal state.*/
  13.   if(sector == 0)
  14.   {
  15.     skip_pages = 0;
  16.     last_pages_are_active = 0;
  17.   }

  18.   sector_start = sector * COFFEE_PAGES_PER_SECTOR;
  19.   sector_end = sector_start + COFFEE_PAGES_PER_SECTOR;

  20.   /*Account for pages belonging to a file starting in a previous segment that extends into this segment. If the whole segment is covered, we do not need to continue counting pages in this iteration.*/
  21.   if(last_pages_are_active)
  22.   {
  23.     if(skip_pages >= COFFEE_PAGES_PER_SECTOR)
  24.     {
  25.       stats->active = COFFEE_PAGES_PER_SECTOR;
  26.       skip_pages -= COFFEE_PAGES_PER_SECTOR;
  27.       return 0;
  28.     }
  29.     active = skip_pages;
  30.   }
  31.   else
  32.   {
  33.     if(skip_pages >= COFFEE_PAGES_PER_SECTOR)
  34.     {
  35.       stats->obsolete = COFFEE_PAGES_PER_SECTOR;
  36.       skip_pages -= COFFEE_PAGES_PER_SECTOR;
  37.       return skip_pages >= COFFEE_PAGES_PER_SECTOR ? 0 : skip_pages;
  38.     }
  39.     obsolete = skip_pages;
  40.   }

  41.   /*Determine the amount of pages of each type that have not been accounted for yet in the current sector.*/
  42.   for(page = sector_start + skip_pages; page < sector_end;)
  43.   {
  44.     read_header(&hdr, page);
  45.     last_pages_are_active = 0;
  46.     if(HDR_ACTIVE(hdr))
  47.     {
  48.       last_pages_are_active = 1;
  49.       page += hdr.max_pages;
  50.       active += hdr.max_pages;
  51.     }
  52.     else if(HDR_ISOLATED(hdr))
  53.     {
  54.       page++;
  55.       obsolete++;
  56.     }
  57.     else if(HDR_OBSOLETE(hdr))
  58.     {
  59.       page += hdr.max_pages;
  60.       obsolete += hdr.max_pages;
  61.     }
  62.     else
  63.     {
  64.       free = sector_end - page;
  65.       break;
  66.     }
  67.   }

  68.   /*Determine the amount of pages in the following sectors that should be remembered for the next iteration. This is necessary because no page except the first of a file contains information about what type of page it is. A side effect of remembering this amount is that there is no need to read in the headers of each of these pages from the storage.*/
  69.   skip_pages = active + obsolete + free - COFFEE_PAGES_PER_SECTOR;
  70.   if(skip_pages > 0)
  71.   {
  72.     if(last_pages_are_active)
  73.     {
  74.       active = COFFEE_PAGES_PER_SECTOR - obsolete;
  75.     }
  76.     else
  77.     {
  78.       obsolete = COFFEE_PAGES_PER_SECTOR - active;
  79.     }
  80.   }

  81.   stats->active = active;
  82.   stats->obsolete = obsolete;
  83.   stats->free = free;

  84.   /*To avoid unnecessary page isolation, we notify the callee that "skip_pages" pages should be isolated only if the current file extent ends in the next sector. If the file extent ends in a more distant sector, however, the garbage collection can free the next sector immediately without requiring page isolation.*/
  85.   return (last_pages_are_active || (skip_pages >= COFFEE_PAGES_PER_SECTOR)) ? 0: skip_pages;
  86. }

阅读(2728) | 评论(2) | 转发(3) |
给主人留下些什么吧!~~

Jelline2013-11-20 17:47:58

macom_zzl:博主可否对第二部分稍作解释?谢谢

好久没弄了,想不起来,对不起。

回复 | 举报

macom_zzl2013-11-16 19:53:19

博主可否对第二部分稍作解释?谢谢