Contiki学习笔记：Coffee文件系统垃圾回收collect_garbage

摘要：

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

一、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_GREEDY。而删除文件采用的是后一种(前提是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);
}

二、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;
}