本文深入源码分析了Coffee文件系统垃圾回收collect_garbage技术细节，包括回收模式mode、sector_status、COFFEE_SECTOR_COUNT、get_sector_status、isolate_pages等。
1. collect_garbage
1.1 垃圾回收概述
FLASH先擦后写的特性，也就不可能每次把失效的页及时擦除（效率低下。有些页可能还没失效，则需要转移这些页的数据，才能擦除），只能在适当时候才擦除，这就是垃圾回收。Coffee文件系统默认情况下，文件删除并没有立即进行垃圾回收，而是待到没有空间可用的时候再回收（可理解成批处理），显然这样做有一个明显的缺点，垃圾回收会占用比较长的时间。collect_garbage源代码如下：
static void collect_garbage(int mode) //mode见1.2
{
uint16_t sector;
struct sector_status stats; //sector_status结构体用于统计垃圾回收页面情况，见1.3
coffee_page_t first_page, isolation_count;
PRINTF("Coffee: Running the file system garbage collector in %s mode\n", mode == GC_RELUCTANT ? "reluctant" : "greedy");
/*The garbage collector erases as many sectors as possible. A sector is erasable if there are only free or obsolete pages in it. */
for(sector = 0; sector < COFFEE_SECTOR_COUNT; sector++) //COFFEE_SECTOR_COUNT见1.4
{
isolation_count = get_sector_status(sector, &stats); //见二
PRINTF("Coffee: Sector %u has %u active, %u obsolete, and %u free pages.\n", sector, (unsigned)stats.active, (unsigned)stats.obsolete, (unsigned)stats.free);
if(stats.active > 0)
{
continue;
}
if((mode == GC_RELUCTANT && stats.free == 0) || (mode == GC_GREEDY && stats.obsolete > 0))
{
first_page = sector * COFFEE_PAGES_PER_SECTOR;
if(first_page < *next_free)
{
*next_free = first_page;
}
if(isolation_count > 0) //找到isolation_count个连续的孤立页
{
isolate_pages(first_page + COFFEE_PAGES_PER_SECTOR, isolation_count); //见1.5
}
COFFEE_ERASE(sector);
PRINTF("Coffee: Erased sector %d!\n", sector);
if(mode == GC_RELUCTANT && isolation_count > 0) //如果是GC_RELUCTANT回收策略，一旦有逻辑分区被擦除就停止
{
break;
}
}
}
}
1.2 回收模式mode
系统提供了两种垃圾回收机制：GC_GREEDY和GC_RELUCTANT，前者垃圾回收过程中，擦除尽可能多的区（即贪心回收），后者擦除一个区后就停止。当创建文件或者创建日志，找不到可用空间时（reserve函数），就会用贪心回收GC_GREED。而删除文件采用的是后一种（前提是COFFEE_EXTENDED_WEAR_LEVELLING为0且gc_allowed为1）。两种回收机制源代码如下：
#define GC_GREEDY 0
#define GC_RELUCTANT 1
1.3 sector_status
sector_status结构体用于垃圾回收的统计页面情况，如下：
//struct sector_status stats;
struct sector_status
{
coffee_page_t active;
coffee_page_t obsolete;
coffee_page_t free;
};
1.4 COFFEE_SECTOR_COUNT
Coffee文件系统是按逻辑区擦除的，之所以有这个是为了应付大的存储设备（比如SD卡），在这种情况下，将其设置大一点可加快顺序扫描速度。COFFEE_SECTOR_COUNT宏定义如下：
#define COFFEE_SECTOR_COUNT (unsigned)(COFFEE_SIZE/COFFEE_SECTOR_SIZE)
1.5 isolate_pages
isolate_pages源码如下：
//isolate_pages(first_page + COFFEE_PAGES_PER_SECTOR, isolation_count);
static void isolate_pages(coffee_page_t start, coffee_page_t skip_pages)
{
struct file_header hdr;
coffee_page_t page;
/*Split an obsolete file starting in the previous sector and mark the following pages as isolated.*/
/***将file_header的flags中的A位、I位置1，其他位为0***/
memset(&hdr, 0, sizeof(hdr));
hdr.flags = HDR_FLAG_ALLOCATED | HDR_FLAG_ISOLATED;
/*Isolation starts from the next sector.*/
for(page = 0; page < skip_pages; page++)
{
write_header(&hdr, start + page);
}
PRINTF("Coffee: Isolated %u pages starting in sector %d\n", (unsigned)skip_pages, (int)start/COFFEE_PAGES_PER_SECTOR);
}
2. get_sector_status
get_sector_status源代码如下：
//isolation_count = get_sector_status(sector, &stats);
static coffee_page_t get_sector_status(uint16_t sector, struct sector_status *stats)
{
static coffee_page_t skip_pages;
static char last_pages_are_active;
struct file_header hdr;
coffee_page_t active, obsolete, free;
coffee_page_t sector_start, sector_end;
coffee_page_t page;
memset(stats, 0, sizeof(*stats));
active = obsolete = free = 0;
/*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.*/
if(sector == 0)
{
skip_pages = 0;
last_pages_are_active = 0;
}
sector_start = sector * COFFEE_PAGES_PER_SECTOR;
sector_end = sector_start + COFFEE_PAGES_PER_SECTOR;
/*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.*/
if(last_pages_are_active)
{
if(skip_pages >= COFFEE_PAGES_PER_SECTOR)
{
stats->active = COFFEE_PAGES_PER_SECTOR;
skip_pages -= COFFEE_PAGES_PER_SECTOR;
return 0;
}
active = skip_pages;
}
else
{
if(skip_pages >= COFFEE_PAGES_PER_SECTOR)
{
stats->obsolete = COFFEE_PAGES_PER_SECTOR;
skip_pages -= COFFEE_PAGES_PER_SECTOR;
return skip_pages >= COFFEE_PAGES_PER_SECTOR ? 0 : skip_pages;
}
obsolete = skip_pages;
}
/*Determine the amount of pages of each type that have not been accounted for yet in the current sector.*/
for(page = sector_start + skip_pages; page < sector_end;)
{
read_header(&hdr, page);
last_pages_are_active = 0;
if(HDR_ACTIVE(hdr))
{
last_pages_are_active = 1;
page += hdr.max_pages;
active += hdr.max_pages;
}
else if(HDR_ISOLATED(hdr))
{
page++;
obsolete++;
}
else if(HDR_OBSOLETE(hdr))
{
page += hdr.max_pages;
obsolete += hdr.max_pages;
}
else
{
free = sector_end - page;
break;
}
}
/*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.*/
skip_pages = active + obsolete + free - COFFEE_PAGES_PER_SECTOR;
if(skip_pages > 0)
{
if(last_pages_are_active)
{
active = COFFEE_PAGES_PER_SECTOR - obsolete;
}
else
{
obsolete = COFFEE_PAGES_PER_SECTOR - active;
}
}
stats->active = active;
stats->obsolete = obsolete;
stats->free = free;
/*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.*/
return (last_pages_are_active || (skip_pages >= COFFEE_PAGES_PER_SECTOR)) ? 0: skip_pages;
}