Contiki学习笔记：Coffee文件组织及若干数据结构

摘要：

    本文介绍了Coffee文件系统的物理上和内存上的组织，还详细介绍了若干关键数据结构，如文件头flie_header、protected_mem_t 、文件描述符file_desc、文件file。

一、物理组织

1.1 概述

    Coffee一个文件在FLASH的组织示意图如下[1]，原始文件包括文件头、数据区，还有可能部分空闲区(文件没那么大，一页用不完)。当修改(modified)一个文件时，不是在原文件修改(不现实，因为FLASH先擦后写)，而是创建一个微日志结构的文件(micro log file)，并链接到原始文件[1]。原文是modified，但我觉得应该是追加的意思。如果对原始文件进行修改，应该是先把文件内容加载到RAM，修改完再写到新的页上，并标记原始文件无效，这只是猜测，还需结合源代码加以验证。

    索引表(Index table)如下图[1]，Coffee文件系统采用Extent索引机制，很多文件系统采用这种机制是为了减少碎片(reduce fragmentation)，但Coffee则是为了降低文件系统的复杂性[1]。同时，采用Extent机制让文件结构体更简单，从而减少元数据的缓存。

    索引机制是文件系统的核心技术[3]，extent和blockmap是两类典型的索引实现方案，前者基于片断索引(如NTFS、Vxfs、JFS、Ext4)，后者基于分配块的位图索引(如UFS、SCO HTFS、Ext2/3)[3]。具体说来，Extent索引是按分配的片断记录，只记录起始块、连续块数、文件内部块位置[3]，如果一个文件由多组不连续的块组成，则需要多条记录。blockmap索引机制，文件的每个分配块都有一个索引与之一一对应。blockmap可以快速定位到文件特定的块，但需要很大的索引空间(极端情况，缓冲机制无法一次读入，效率便会下降)，也浪费磁盘空间，所以现在blockmap机制已经很少使用了。而Extent需要索引空间小，连续读写会有优势，但算法复杂度略高[3]。

1.2 file_header

    file_header用于描述一个文件的元数据，即描述了一个文件的基本信息(比如占用页情况)，file_header位于文件(log file或micro log file)第一页的开始处。源代码如下：

/*The file header structure mimics the representation of file headers in the physical storage medium*/
struct file_header
{
  coffee_page_t log_page;
  uint16_t log_records;
  uint16_t log_record_size;
  coffee_page_t max_pages;
  uint8_t deprecated_eof_hint;
  uint8_t flags;
  char name[COFFEE_NAME_LENGTH];
};

file_header结构体可以直观表示成下图[1]：

各成员变量含义如下：

log_page

    如果配置了微日志(见cfs-coffee-arch.h文件配置#define COFFEE_MICRO_LOGS 0)，那么log_page指向微日志的第一页，见Figure 1。 

log_records

    表示日志可以容纳的记录数量(log records denotes the number of records that the log can hold)

log_record_size

    log_record_size表示微日志文件大小，如果为0，则设置成默认值(见cfs-coffee-arch.h文件配置#define COFFEE_LOG_SIZE 128)。

max_pages

    max_pages指为文件保留着页面数(The max pages field specifies the amount of pages that have been reserved for the file)

deprecated_eof_hint

    因为文件头不能存储文件长度(缘于文件长度经常变化着)，所以用deprecated_eof_hint指向文件的最后一个字节。文件关闭时，如果文件长度增加则需更新deprecated_eof_hint(先擦后写，如何更新？)。

flags

    flags反映了文件当前状态(The flag field tells us the current state)，页有3种状态空闲(free，即可以用来写)、有效(active，即数据有效)、无效(obsolete，即数据无效且还没擦除，不能用来写)。如Figure2，flags用了6个位，分别是ALOMIV，接下来详细解释之：

    A(allocated)

    如果该位被设置，表示文件正在使用。反之，当前页及所有保留页(直到下一个逻辑区的边界)是空闲的。

    O(obsolete)

    当文件被删除时，O标记保留页是无效的(obsolete)[2]。不是吧，这些页不用擦除就可以直接使用的，怎么说也应该标记成空闲free？

    M(modified)

    资料[1][2]居然没提这个标志，得根据源代码推测了:-( 在cfs-coffee.c的flags宏定义可得知，M表示文件已被修改，日志存在(Modified file, log exists)。

    L(log)

    L(log)标记文件已被修改，与微日志文件存在有关(and that a related log file exists)。不同于M，应该是指微日志的修改标志(待读源码确认)。

    I(isolated)

    I标记孤立的页，所有Coffee算法每次都会处理孤立的页面(Isolated pages are processed one at a time by all Coffee algorithms, and are treated the same way as obsolete files)

    V(valid)

    V(valid)标记文件头是完整的(helps by marking that the header data is complete)，To discover garbled headers-typically caused by a system reboot during a header write operation。

为方便操作，Coffee将这些flags单独定义成宏，源代码如下(在cfs-coffee.c文件)：

/* File header flags. */
#define HDR_FLAG_VALID        0x1    /* Completely written header. */
#define HDR_FLAG_ALLOCATED    0x2    /* Allocated file. */
#define HDR_FLAG_OBSOLETE     0x4    /* File marked for GC. */
#define HDR_FLAG_MODIFIED     0x8    /* Modified file, log exists. */
#define HDR_FLAG_LOG          0x10    /* Log file. */
#define HDR_FLAG_ISOLATED     0x20    /* Isolated page. */

    注：这6个标志是有优先顺序的，依次是the valid flag(V)、the isolated flag(I), the obsolete flag(O),、the log flag(L)、the allocated flag(A)。(不晓得M该处于哪个位置)

name

    文件名，其中文件长度COFFEE_NAME_LENGTH可配置，在contiki/cpu/平台(如arm/stm32f103)/cfs-coffee-arch.h

二、内存组织

    为了提高性能，Coffee缓存了文件元数据，并用文件描述符file_desc与之映射，Coffee文件系统在内存组织逻辑图如下：

图 Coffee文件系统在内存组织逻辑图[2]

    Coffee将文件描述符file_desc组织成一个数组，作为protected_mem_t的一个成员变量，数组个数(即系统缓存file_desc最大数目)，可以在cfs-coffee-arch.h进行配置，默认情况是8条，如下：

#define COFFEE_FD_SET_SIZE 8

protected_mem_t 结构体源代码如下：

/*The protected memory consists of structures that should not be overwritten during system checkpointing because they may be used by the checkpointing implementation. These structures need not be protected if checkpointing is not used.*/
static struct protected_mem_t
{
  struct file coffee_files[COFFEE_MAX_OPEN_FILES];
  struct file_desc coffee_fd_set[COFFEE_FD_SET_SIZE];
  coffee_page_t next_free;
  char gc_wait;
} protected_mem;

static struct file *const coffee_files = protected_mem.coffee_files;
static struct file_desc *const coffee_fd_set = protected_mem.coffee_fd_set;
static coffee_page_t *const next_free = &protected_mem.next_free;
static char *const gc_wait = &protected_mem.gc_wait;

2.1 文件描述符结构体file_desc

系统缓存file_desc示意图如下：

图 Coffee缓存file_desc示意图

这跟Linux文件系统类似，offset存储文件偏移量，file指针指向2.2的file，源码如下：

/* The file descriptor structure. */
struct file_desc
{
  cfs_offset_t offset;
  struct file *file;
  uint8_t flags;
  #if COFFEE_IO_SEMANTICS
    uint8_t io_flags;
  #endif
};

    Coffee文件系统出现多次flags，有些含义相同，有些则不同。file_desc的flags与1.2的flags含义不同，共4个取值，如下，用于标记文件的权限，即读、写、追加、空闲。

#define COFFEE_FD_FREE        0x0
#define COFFEE_FD_READ        0x1
#define COFFEE_FD_WRITE       0x2
#define COFFEE_FD_APPEND      0x4

    对于某些存储器，为了优化文件访问(optimize file access on certain storage types)，可以配置COFFEE_IO_SEMANTICS。Coffeee定义了io_flags的两种值，

#define CFS_COFFEE_IO_FLASH_AWARE      0x1
#define CFS_COFFEE_IO_FIRM_SIZE        0x2

    当写超过预留的大小时，Coffee文件系统不会再扩展文件。当文件有固定大小的限制，CFS_COFFEE_IO_FIRM_SIZE必须设置，保护不被写超了(protect against writes beyond this limit)。CFS_COFFEE_IO_FLASH_AWARE，还不晓得什么意思，先贴出源码注释，

2.2 file

系统缓存file示意图如下：

图 Coffee缓存file示意图

file源代码如下：

/* The structure of cached file objects. */
struct file
{
  cfs_offset_t end;
  coffee_page_t page;
  coffee_page_t max_pages;
  int16_t record_count;
  uint8_t references;
  uint8_t flags;
};

    file包容了元数据文件头file_header一些信息(可以理解成file缓存了file_header)，值得一提的是end和references。end存放文件的最后一个字节的偏移量，当打开一个文件时，Coffee用蛮力法找到文件末尾(即Extent末尾向前找每一个非空字节[1]？？？)。references记录文件的引用次数，Contiki提供类多线程编程环境，会有这样的情况，多个线程同时打开一个文件，需要记录引用次数。

参考资料：

[1] Enabling Large-Scale Storage in Sensor Networks with the Coffee File System.pdf

[2] 

[3] 博文《文件系统的两种文件索引模式extent和blockmap》