Yaffs_guts

Yaffs_guts

1.Chunk的读写擦除

2.文件地址映射

3.文件系统对象

1.Chunk的读写擦除

我们知道,NAND Flash的基本擦除单位是Block,而基本写入单位是page。yaffs2在分配存储空间的时候是以page为单位的,不过在yaffs2中把基本 存储单位称为chunk,和

page是一样的大小,在大多数情况下和page是一个意思。在下文中我们使用chunk这个词,以保持和yaffs2的源代码一致。我们先看存储空间的分配(在yaffs_guts.c中。这个文件也是yaffs2文件系统的核心部分):Yaffs2中将该函数更名为yaffs_alloc_chunk。

static int yaffs_AllocateChunk(yaffs_Device * dev, int useReserve, yaffs_BlockInfo **blockUsedPtr) 
{
int retVal;
yaffs_BlockInfo *bi; 
if (dev->allocationBlock < 0) { 
/* Get next block to allocate off */ 
dev->allocationBlock = yaffs_FindBlockForAllocation(dev); 
dev->allocationPage = 0; 
 }

函数有三个参数,dev是yaffs_Device结构的指针,yaffs2用这个结构来记录一个NAND器件的属性(如block和page的大小)和系统运行过程中的一些统计值(如器件中可用chunk的总数),还用这个结构维护着一组NAND操作函数(如读、写、删除)的指针。

整个结构体比较大,我们会按情景的不同分别分析。useReserve表示是否使用保留空间。yaffs2文件系统并不会将所有的存储空间全部用于存储文件系统数据,而要空出部分block用于垃圾收集时使用。一般情况下这个参数都是0,只有在垃圾收集时需要分配存储空间的情况下将该参数置1。yaffs_BlockInfo 是描述block属性的结构,主要由一些统计变量组成,比如该block内还剩多少空闲page等。我们同样在具体情景中再分析这个结构中的字段含义。

函数首先判断dev->allocationBlock的值是否小于0。yaffs_Device结构内的allocationBlock字段用于记录当前从中分配chunk(page)的那个block的序号。当一个block内的所有page全部分配完毕时,就将这个字段置为-1,下次进入该函数时就会重新挑选空闲的block。这里我们假定需要重新挑选空闲block,因此进入yaffs_FindBlockForAllocation函数:

static int yaffs_FindBlockForAllocation(yaffs_Device * dev) 
 {
int i; 
yaffs_BlockInfo *bi; 
if (dev->nErasedBlocks < 1) { 
/* Hoosterman we've got a problem. 
* Can't get space to gc 
 /*
T(YAFFS_TRACE_ERROR, 
(TSTR("yaffs tragedy: no more eraased blocks" TENDSTR))); 
return -1;
 }

dev->nErasedBlocks记录着器件内所有可供分配的block的数量。如果该值小于1,那显然是有问题了。不但正常的分配请求无法完成,就连垃圾收集都办不到了。

for (i = dev->internalStartBlock; i <= dev->internalEndBlock; i++) { 
dev->allocationBlockFinder++; 
if (dev->allocationBlockFinder < dev->internalStartBlock 
|| dev->allocationBlockFinder > dev->internalEndBlock) { 
dev->allocationBlockFinder = dev->internalStartBlock; 

internalStartBlock和internalEndBlock分别是yaffs2使用的block的起始序号和结束序号。也就是说yaffs2文件系统不一定要占据整个Flash,可以只占用其中的一部分。 dev->allocationBlockFinder记录着上次分配的块的序号。如果已经分配到系统尾部,就从头重新开始搜索可用块。

bi = yaffs_get_block_info(dev, dev->alloc_block_finder);
if (bi->block_state == YAFFS_BLOCK_STATE_EMPTY) {
bi->block_state = YAFFS_BLOCK_STATE_ALLOCATING;
dev->seq_number++;
bi->seq_number = dev->seq_number;
dev->n_erased_blocks--;
yaffs_trace(YAFFS_TRACE_ALLOCATE,
  "Allocated block %d, seq  %d, %d left" ,
   dev->alloc_block_finder, dev->seq_number,
   dev->n_erased_blocks);
return dev->alloc_block_finder;
}

yaffs_GetBlockInfo函数获取指向block信息结构的指针,该函数比较简单,就不详细介绍了。yaffs_BlockInfo结构中的blockState成员描述该 block的状态,比如空,满,已损坏,当前分配中,等等。因为是要分配空闲块,所以块状态必须是YAFFS_BLOCK_STATE_EMPTY,如果不是,就继续测试下一个block。找到以后将block状态修改为 YAFFS_BLOCK_STATE_ALLOCATING,表示当前正从该block中分配存储空间。正常情况下,系统中只会有一个block处于该状态。另外还要更新统计量ErasedBlocks和sequenceNumber。这个sequenceNumber记录着各block被分配出去的先后顺序,以后在垃圾收集的时候会以此作为判断该block是否适合回收的依据。

现在让我们返回到函数 yaffs_AllocateChunk中。yaffs_CheckSpaceForAllocation()函数检查Flash上是否有足够的可用空间,通过检查后,就从当前供分配的block上切下一个

if (dev->alloc_block >= 0) {
bi = yaffs_get_block_info(dev, dev->alloc_block);
ret_val = (dev->alloc_block * dev->param.chunks_per_block) +
    dev->alloc_page;
bi->pages_in_use++;
yaffs_set_chunk_bit(dev, dev->alloc_block, dev->alloc_page);
dev->alloc_page++;
dev->n_free_chunks--;
/* If the block is full set the state to full */
if (dev->alloc_page >= dev->param.chunks_per_block) {
bi->block_state = YAFFS_BLOCK_STATE_FULL;
dev->alloc_block = -1;
}
if (block_ptr)
*block_ptr = bi;
return ret_val;

dev->allocationPage记录着上次分配的chunk在block中的序号,每分配一次加1。从这里我们可以看出,系统在分配 chunk的时候是从block的开头到结尾按序分配的,直到一个block内的所有chunk全部分配完毕为止。retVal是该chunk在整个 device内的总序号。PagesInUse记录着该block中已分配使用的page的数量。 系统在设备描述结构yaffs_Device 中维护着一张位图,该位图的每一位都代表着Flash上的一个chunk的状态。yaffs_SetChunkBit()将刚分配得到的chunk在位图中的对应位置1,表明该块已被使用。更新一些统计量后,就可以返回了。

看过chunk分配以后,我们再来chunk的释放。和chunk分配不同的是,chunk的释放在大多数情况下并不释放对应的物理介质,这是因为 NAND虽然可以按page写,但只能按block擦除,所以物理介质的释放要留到垃圾收集或一个block上的所有page全部变成空闲的时候才进行。根据应用场合的不同,chunk的释放方式并不唯一,分别由yaffs_DeleteChunk函数和yaffs_SoftDeleteChunk函数完成。我们先看yaffs_DeleteChunk:(该函数在后续版本中被更名为yaffs_chunk_del())

void yaffs_DeleteChunk(yaffs_Device * dev, int chunkId, int markNAND, int lyn)

chunkId就是要删除的chunk的序号,markNand参数用于yaffs一代的代码中,yaffs2不使用该参数。 参数lyn在调用该函数时置成当前行号(__LINE__),用于调试。

首先通过yaffs_GetBlockInfo获得chunk所在block的信息描述结构指针,然后就跑到else里面去了。if语句的判断条件中有一 条!dev->isYaffs2,所以对于yaffs2而言是不会执行if分支的。在else分支里面只是递增一下统计计数就出来了,我们接着往下看。

if (bi->blockState == YAFFS_BLOCK_STATE_ALLOCATING ||
bi->blockState == YAFFS_BLOCK_STATE_FULL ||
bi->blockState == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
bi->blockState == YAFFS_BLOCK_STATE_COLLECTING) { 
dev->nFreeChunks++;
yaffs_ClearChunkBit(dev, block, page); 
bi->pagesInUse--; 
if (bi->pagesInUse == 0 &&
!bi->hasShrinkHeader &&
bi->blockState != YAFFS_BLOCK_STATE_ALLOCATING &&
bi->blockState != YAFFS_BLOCK_STATE_NEEDS_SCANNING) { 
yaffs_BlockBecameDirty(dev, block); 

首先要判断一下该block上是否确实存在着可释放的chunk。block不能为空,不能是坏块。YAFFS_BLOCK_STATE_NEEDS_SCANNING表明正对该块进行垃圾回收,我们后面会分析;YAFFS_BLOCK_STATE_NEEDS_SCANNING在我手上的源代码中似乎没有用到。

通过判断以后,所做的工作和chunk分配函数类似,只是一个递增统计值,一个递减。递减统计值以后还要判断该block上的page是否已全部释放,如果已全部释放,并且不是当前分配块,就通过yaffs_BlockBecameDirty函数删除该block,只要能通过删除操作(不是坏块),该 block就又可以用于分配了。

相比较来说,yaffs_SoftDeleteChunk所做的工作就简单多了。关键的代码只有两行:

static void yaffs_SoftDeleteChunk(yaffs_Device * dev, int chunk) 
 {
 ……
theBlock->softDeletions++;
dev->nFreeChunks++;
 ……
 }

这里递增的是yaffs_blockInfo结构中的另一个统计量 softDeletions,而没有修改pagesInUse成员,也没有修改chunk状态位图。那么,这两个函数的应用场合有什么区别呢?

一般来说,yaffs_DeleteChunk用于文件内容的更新。比如我们要修改文件中的部分内容,这时候yaffs2会分配新的chunk,将更改后的内容写入新chunk中,原chunk的内容自然就没有用了,所以要将pageInUse减1,并修改位图; yaffs_SoftDeleteChunk用于文件的删除。yaffs2在删除文件的时候只是删除该文件在内存中的一些描述结构,而被删除的文件所占用 的chunk不会立即释放,也就是不会删除文件内容,在后续的文件系统操作中一般也不会把这些chunk分配出去,直到系统进行垃圾收集的时候才有选择地释放这些chunk。熟悉DOS的朋友可能还记得,DOS在删除的文件的时候也不会立即删除文件内容,只是将文件名的第一个字符修改为0xA5,事后还可以恢复文件内容。yaffs2在这点上是类似的。

2.文件地址映射

上面说到,yaffs文件系统在更新文件数据的时候,会分配一块新的chunk,也就是说,同样的文件偏移地址,在该地址上的数据更新前和更新后,其对应的flash上的存储地址是不一样的。那么,如何根据文件内偏移地址确定flash存储地址呢?最容易想到的办法,就是在内存中维护一张映射表。由于 flash基本存储单位是chunk,因此,只要将以chunk描述的文件偏移量作为表索引,将flash chunk序号作为表内容,就可以解决该问题了。但是这个方法有几个问题,首先就是在做seek操作的时候,要从表项0开始按序搜索,对于大文件会消耗很多时间;其次是在建立映射表的时候,无法预计文件大小的变化,于是就可能在后来的操作中频繁释放分配内存以改变表长,造成内存碎片。yaffs的解决方法是将这张大的映射表拆分成若干个等长的小表,并将这些小表组织成树的结构,方便管理。我们先看小表的定义:

struct yaffs_tnode {
struct yaffs_tnode *internal[YAFFS_NTNODES_INTERNAL];
}; 

YAFFS_NTNODES_INTERNAL定义为(YAFFS_NTNODES_LEVEL0 / 2),而YAFFS_NTNODES_LEVEL0定义为16,所以这实际上是一个长度为8的指针数组。不管是叶子节点还是非叶节点,都是这个结构。当节点为非叶节点时,数组中的每个元素都指向下一层子节点;当节点为叶子节点时,该数组拆分为16个16位长的短整数(也有例外,后面会说到),该短整数就是文件内容 在flash上的存储位置(即chunk序号)。至于如何通过文件内偏移找到对应的flash存储位置,源代码所附文档(Development/yaffs/Documentation/yaffs-notes2.html)已经有说明,俺就不在此处饶舌了。下面看具体函数。

为了行文方便,后文中将yaffs_Tnode这个指针数组称为“一组”Tnode,而将数组中的每个元素称为“一个”Tnode。树中的每个节点,都是“一组”Tnode。

先看映射树的节点的分配。

struct yaffs_tnode *yaffs_get_tnode(struct yaffs_dev *dev)
{
struct yaffs_tnode *tn = yaffs_alloc_raw_tnode(dev);
if (tn) {
memset(tn, 0, dev->tnode_size);
dev->n_tnodes++;
}
dev->checkpoint_blocks_required = 0;/* force recalculation */
return tn;
}

调用yaffs_GetTnodeRaw分配节点,然后将得到的节点初始化为零。

static yaffs_Tnode *yaffs_GetTnodeRaw(yaffs_Device * dev) 
 {
yaffs_Tnode *tn = NULL; 
/* If there are none left make more */ 
if (!dev->freeTnodes) { 
yaffs_CreateTnodes(dev, YAFFS_ALLOCATION_NTNODES); 
 }

当前所有空闲节点组成一个链表,dev->freeTnodes是这个链表的表头。我们假定已经没有空闲节点可用,需通过yaffs_CreateTnodes创建一批新的节点。

static int yaffs_CreateTnodes(yaffs_Device * dev, int nTnodes) 
 {
 ......
tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8; 
newTnodes = YMALLOC(nTnodes * tnodeSize); 
mem = (__u8 *)newTnodes; 
}

(其实在最新版本的yaffs中已经加入了slab缓冲区,这样提高了效率)上面说过,叶节点中一个Tnode的位宽默认为16位,也就是可以表示65536个chunk。对于时下的大容量flash,chunk的大小为2K,因 此在默认情况下yaffs2所能寻址的最大flash空间就是128M。为了能将yaffs2用于大容量flash上,代码作者试图通过两种手段解决这个问题。第一种手段就是这里的dev->tnodeWidth,通过增加单个Tnode的位宽,就可以增加其所能表示的最大chunk Id;另一种手段是我们后面将看到的chunk group,通过将若干个chunk合成一组用同一个id来表示,也可以增加系统所能寻址的chunk范围。

俺为了简单,分析的时候不考虑这两种情况,因此tnodeWidth取默认值16,也不考虑将多个chunk合成一组的情况,只在遇到跟这两种情况有关的代码时作简单说明。

在32位的系统中,指针的宽度为32位,而chunk id的宽度为16位,因此相同大小的Tnode组,可以用来表示N个非叶Tnode(作为指针使用),也可以用来表示N * 2个叶子Tnode(作为chunk id使用)。代码中分别用YAFFS_NTNODES_INTERNAL和YAFFS_NTNODES_LEVEL0来表示。前者取值为8,后者取值为16。从这里我们也可以看出若将yaffs2用于64位系统需要作哪些修改。 针对上一段叙述的问题,俺以为在内存不紧张的情况下,不如将叶节点Tnode和非叶节点Tnode都设为一个指针的长度。分配得到所需的内存后,就将这些空闲空间组成Tnode链表:

for(i = 0; i < nTnodes -1; i++) { 
curr = (yaffs_Tnode *) &mem[i * tnodeSize]; 
next = (yaffs_Tnode *) &mem[(i+1) * tnodeSize]; 
curr->internal[0] = next; 
}

每组Tnode的第一个元素作为指针指向下一组Tnode。完成链表构造后,还要递增统计量,并将新得到的Tnodes挂入一个全局管理链表yaffs_TnodeList:

dev->nFreeTnodes += nTnodes; 
dev->nTnodesCreated += nTnodes; 
tnl = YMALLOC(sizeof(yaffs_TnodeList)); 
if (!tnl) { 
T(YAFFS_TRACE_ERROR, (TSTR ("yaffs: Could not add tnodes to management list" TENDSTR))); 
} else { 
tnl->tnodes = newTnodes; 
tnl->next = dev->allocatedTnodeList; 
dev->allocatedTnodeList = tnl; 
 }

回到yaffs_GetTnodeRaw,创建了若干组新的Tnode以后,从中切下所需的Tnode,并修改空闲链表表头指针:

if (dev->freeTnodes) { 
tn = dev->freeTnodes; 
dev->freeTnodes = dev->freeTnodes->internal[0]; 
dev->nFreeTnodes--; 
 }

至此,分配工作就完成了。相比较来说,释放Tnodes的工作就简单多了,简单的链表和统计值操作:

static void yaffs_FreeTnode(yaffs_Device * dev, yaffs_Tnode * tn) 
 {
if (tn) { 
tn->internal[0] = dev->freeTnodes; 
dev->freeTnodes = tn; 
dev->nFreeTnodes++;
 }
}

看过Tnode的分配和释放,我们再来看看这些Tnode是如何使用的。在后文中,我们把以chunk为单位的文件内偏移称作逻辑chunk id,文件内容在flash上的实际存储位置称作物理chunk id。先看一个比较简单的函数。

void yaffs_PutLevel0Tnode(yaffs_Device *dev, yaffs_Tnode *tn, unsigned pos,unsigned val)

这个函数将某个Tnode设置为指定的值。tn是指向一组Tnode的指针;pos是所要设置的那个Tnode在该组Tnode中的索引;val就是所要设置的值,也就是物理chunk id。函数名中的Level0指映射树的叶节点。函数开头几行如下:

pos &= YAFFS_TNODES_LEVEL0_MASK; 
val >>= dev->chunkGroupBits; 
bitInMap = pos * dev->tnodeWidth;
wordInMap = bitInMap /32;
bitInWord = bitInMap & (32 -1); 
mask = dev->tnodeMask << bitInWord; 

上面说过,一组Tnode中的8个指针在叶节点这一层转换成16个16位宽的chunk Id,因此需要4位二进制码对其进行索引,这就是 YAFFS_TNODES_LEVEL0_MASK的值。我们还说过这个16位值就是chunk在flash上的序号,当flash容量比较大, chunk数量多时,16位可能无法给flash上的所有chunk编号,这种情况下可以增加chunk id的位宽,具体位宽的值记录在 dev->tnodeWidth中。yaffs2允许使用非字节对齐的tnodeWidth,因此可能出现某个chunk id跨32位边界存储的情况。所以在下面的代码中,需要分边界前和边界后两部分处理:

map[wordInMap] &= ~mask; 
map[wordInMap] |= (mask & (val << bitInWord)); 
if(dev->tnodeWidth > (32-bitInWord)) { 
bitInWord = (32 - bitInWord); 
wordInMap++;;
mask = dev->tnodeMask >> (/*dev->tnodeWidth -*/ bitInWord); map[wordInMap] &= ~mask; 
map[wordInMap] |= (mask & (val >> bitInWord)); 
 }

if语句判断当前chunk序号是否跨越当前32位边界。整个代码初看起来比较难理解,其实只要将 dev->tnodeWidth以16或32代入, 就很好懂了。还有一个类似的函数yaffs_GetChunkGroupBase,返回由tn和pos确定的一组chunk的起始序号,就不详细分析了。

现在我们假设有这样一个情景:已知文件偏移地址,要找到flash上对应的存储地址,该怎么做呢?这项工作的主体是由函数yaffs_FindLevel0Tnode完成的。

static yaffs_Tnode *yaffs_FindLevel0Tnode(yaffs_Device * dev, yaffs_FileStructure * fStruct, __u32 chunkId) 
 {
yaffs_Tnode *tn = fStruct->top; 
__u32 i; 
int requiredTallness; 
int level = fStruct->topLevel; 

函数参数中,fStruct是指向文件描述结构的指针,该结构保存着文件大小、映射树层高、映射树顶层节点指针等信息。chunkId是逻辑chunk id。fStruct->top是映射树顶层节点指针,fStruct->topLevel是映射树层高。注意:当只有一层时,层高为0。

/* First check we're tall enough (ie enough topLevel) */ 
i = chunkId >> YAFFS_TNODES_LEVEL0_BITS; 
requiredTallness = 0; 
while (i) { 
i >>= YAFFS_TNODES_INTERNAL_BITS; 
requiredTallness++;
 }
if (requiredTallness > fStruct->topLevel) {
/* Not tall enough, so we can't find it, return NULL. */ 
return NULL;
}

在看这段代码之前,我们先用一个例子来回顾一下映射树的组成。假定我们有一个大小为128K的文件,flash的page大小为2K,那么我们就需要64个 page(或者说chunk)来存储该文件。一组Tnode的size是8个指针,或者16个16位整数,所以我们需要4组Tnode来存储物理chunk序号。这4组Tnode就是映射树的叶节点,也就是Level0节点。由于这4组Tnode在内存中不一定连续,所以 我们需要另外一组Tnode,将其作为指针数组使用,这个指针数组的前4个元素分别指向4组Level0节点,而fStruct->top就指向这组作为指针数组使用的Tnode。随着文件长度的增大,所需的叶节点越多,非叶节点也越多,树也就越长越高。 回过头来看代码,首先是检查函数参数chunkId是否超过文件长度。作为非叶节点使用的Tnode每组有8个指针,需要3位二进制码对其进行索引,因此树每长高一层,逻辑chunkId就多出3位。相反,每3位非零chunkId就代表一层非叶节点。while循环根据这个原则计算参数chunkId所对应的树高。如果树高超过了文件结构中保存的树高,那就说明该逻辑chunkId已经超出文件长度了。通过文件长度检查之后,同样根据上面的原则,就可以找到逻辑chunkId对应的物理chunkId了。具体的操作通过一个while循环完成:

/* Traverse down to level 0 */ 
while (level > 0 && tn) { 
tn = tn-> internal[(chunkId >>
( YAFFS_TNODES_LEVEL0_BITS +(level - 1) *
YAFFS_TNODES_INTERNAL_BITS) 
& (YAFFS_TNODES_INTERNAL_MASK]; 
level--; 
 }
return tn; 

将返回值和逻辑chunk id作为参数调用yaffs_GetChunkGroupBase,就可以得到物理chunk id了。下面我们看另一个情景,看看当文件长度增加的时候,映射树是如何扩展的。主要函数为

static yaffs_Tnode *yaffs_AddOrFindLevel0Tnode(yaffs_Device * dev, 
yaffs_FileStructure * fStruct, 
__u32 chunkId, 
yaffs_Tnode *passedTn) 

函数的前几行和yaffs_FindLevel0Tnode一样,对函数参数作一些检查。通过检查之后,首先看原映射树是否有足够的高度,如果高度不够,就先将其“拔高”:

if (required_depth > file_struct->top_level) {
/* Not tall enough, gotta make the tree taller */
for (i = file_struct->top_level; i < required_depth; i++) {
tn = yaffs_get_tnode(dev);
if (tn) {
tn->internal[0] = file_struct->top;
file_struct->top = tn;
file_struct->top_level++;
} else {
yaffs_trace(YAFFS_TRACE_ERROR,
"yaffs: no more tnodes");
return NULL;
}
}
}

for循环完成增加新层的功能。新增的每一层都只有一个节点(即一组Tnode),fStruct->top始终指向最新分配的节点。将映射树扩展到所需的高度之后,再根据需要将其“增肥”,扩展其“宽度”:

l = file_struct->top_level;
tn = file_struct->top;
if (l > 0) {
while (l > 0 && tn) {
x = (chunk_id >>
     (YAFFS_TNODES_LEVEL0_BITS +
      (l - 1) * YAFFS_TNODES_INTERNAL_BITS)) &
    YAFFS_TNODES_INTERNAL_MASK;
if ((l > 1) && !tn->internal[x]) {
/* Add missing non-level-zero tnode */
tn->internal[x] = yaffs_get_tnode(dev);
if (!tn->internal[x])
return NULL;
} else if (l == 1) {
/* Looking from level 1 at level 0 */
if (passed_tn) {
/* If we already have one, release it */
if (tn->internal[x])
yaffs_free_tnode(dev,
tn->internal[x]);
tn->internal[x] = passed_tn;
} else if (!tn->internal[x]) {
/* Don't have one, none passed in */
tn->internal[x] = yaffs_get_tnode(dev);
if (!tn->internal[x])
return NULL;
}
}
tn = tn->internal[x];
l--;
}
} 

上面“拔高”的时候是从下往上“盖楼”,这里“增肥”的时候是从上往下“扩展”。 tn->internal[x]为空表示下层节点尚未创建,需要通过yaffs_GetTnode分配之,就是“增肥”了。如果函数参数passedTn有效,就用该组Tnode代替level0上原先的那组Tnode;否则按需分配新的Tnode组。所以这里的函数名似乎应该取作yaffs_AddOrFindOrReplaceLevel0Tnode更加恰当。不过这个新名字也太长了些……

树的创建、搜索和扩展说完了,下面该说什么?……对了,收缩和删除。不过看过创建搜索扩展之后,收缩和删除已经没什么味道了。主要函数有:

yaffs_DeleteWorker() 
yaffs_SoftDeleteWorker() 
yaffs_PruneWorker() 

前两者用于删除,第三个用于收缩。都是从level0开始,以递归的方式从叶节点向上删,并释放被删除Tnode所对应的物理chunk。递归,伟大的递归啊……俺不想把这篇文章做成递归算法教程,除了递归这三个函数也就不剩啥了,所以一概从略。唯一要说的就是yaffs_DeleteWorker和 yaffs_SoftDeleteWorker的区别,这两个函数非常类似,只是在释放物理chunk的时候分别调用yaffs_DeleteChunk 和yaffs_SoftDeleteChunk。其中函数yaffs_DeleteWorker在yaffs2中似乎是不用的,而 yaffs_SoftDeleteWorker主要用于在删除文件时资源的释放。

3.文件系统对象

在yaffs2中,不管是文件还是目录或者是链接,在内存都用一个结构体yaffs_ObjectStruct来描述。我们先简要介绍一下这个结构体中的几个关键字段,然后再来看代码。在后文中提到“文件”或“文件对象”,若不加特别说明,都指广义的“文件”,既可以是文件,也可以是目录。

__u8 deleted:1; /* This should only apply to unlinked files. */ 
__u8 softDeleted:1; /* it has also been soft deleted */ 
__u8 unlinked:1; /* An unlinked file. The file should be in the unlinked directory.*/ 

这三个字段用于描述该文件对象在删除过程中所处的阶段。在删除文件时,首先要将文件从原目录移至一个特殊的系统目录/unlinked,以此拒绝应用程序对该文件的访问,此时将unlinked置1;然后判断该文件长度是否为0,如果为0,该文件就可以直接删除,此时将deleted置1;如果不为0,就将deleted和softDelted都置1,表明该文件数据所占据的chunk还没有释放,要留待后继处理。

struct yaffs_ObjectStruct *parent; 看名字就知道,该指针指向上层目录。

int chunkId; 每个文件在flash上都有一个文件头,存储着该文件的大小、所有者、创建修改时间等信息。chunkId就是该文件头在flash上的chunk序号。

__u32 objectId; /* the object id value */ 每一个文件系统对象都被赋予一个唯一的编号,作为对象标识,也用于将该对象挂入一个散列表,加快对象的搜索速度。

yaffs_ObjectType variantType;
yaffs_ObjectVariant variant; 

前者表示该对象的类型,是目录、普通文件还是链接文件。后者是一个联合体,根据对象类型的不同有不同的解释。其余的成员变量,我们在后面结合函数一起分析。

下面我们来看相关的函数。先看一个简单的:

static yaffs_Object *yaffs_CreateFakeDirectory(yaffs_Device * dev, int number, __u32 mode) 

所谓Fake Directory,就是仅存在于内存中,用于管理目的的目录对象,比如我们上面提到的unlinked目录。这种类型的目录有一些特别的地方,如禁止改名、禁止删除等。由于对象仅存在于内存中,因此不涉及对硬件的操作,所以函数体很简单。首先通过yaffs_CreateNewObject获得一个新对象,然后对其中的一些字段初始化。先把字段初始化看一下,顺便再介绍一些字段:

renameAllowed表示是否允许改名,对于fake对象为0;

unlinkAllowed表示是否允许删除,对于fake对象同样为0;

yst_mode就是linux中的访问权限位;

chunkId是对象头所在chunk,由于fake对象不占flash存储空间,所以置0。

回过头来看yaffs_CreateNewObject:

[yaffs_CreateFakeDirectory --> yaffs_CreateNewObject]
yaffs_Object *yaffs_CreateNewObject(yaffs_Device * dev, int number,yaffs_ObjectType type) 
{ 
yaffs_Object *theObject; 
if (number < 0) { 
number = yaffs_CreateNewObjectNumber(dev); 
}
theObject = yaffs_AllocateEmptyObject(dev); 

前面说过,每个yaffs_Object都有一个唯一的序列号,这个序号既可以在创建对象的时候由上层函数指定,也可以由系统分配。如果number < 0,那就表示由系统分配。序列号分配函数是 yaffs_CreateNewObjectNumber。我们就不深入到这个函数内部了,只说明一下该函数做了些什么:系统为了方便根据对象id找到对象本身,将每个对象都通过指针hashLink挂入了一个散列表,散列函数是number % 256,所以这个散列表有256个表项。

yaffs_CreateNewObjectNumber函数每次搜索10个表项,从中选取挂接链表长度最短的那一项,再根据表索引试图计算出一个和该索引上挂接对象的id号不重复的id。分配到了id号和空闲对象后,再根据对象类型的不同作不同的处理。我们主要关心两种情况,就是对象类型分别为文件和目录的时候:

case YAFFS_OBJECT_TYPE_FILE: 
theObject->variant.fileVariant.fileSize = 0; 
theObject->variant.fileVariant.scannedFileSize = 0; theObject->variant.fileVariant.shrinkSize = 0xFFFFFFFF; /* max __u32 */ 
theObject->variant.fileVariant.topLevel = 0; 
theObject->variant.fileVariant.top = yaffs_GetTnode(dev); 
break; 
case YAFFS_OBJECT_TYPE_DIRECTORY: 
INIT_LIST_HEAD(&theObject->variant.directoryVariant.children); 
break; 

fileSize很好理解;topLevel就是映射树层高,新建的文件层高为0。还要预先分配一组Tnode供该对象使用。 scannedFileSize和shrinkSize用于yaffs2初始化时的flash扫描阶段,这里先跳过。如果该对象是目录,那么所做的工作只是初始化子对象(就是该目录下的文件或子目录)双向链表指针,前后指针都指向链表头自身。 看过Fake对象创建,我们再看看普通对象的创建。按对象类型的不同,有四个函数分别用于创建普通文件、目录、设备文件、符号链接和硬链接,它们分别是:

yaffs_MknodFile;
yaffs_MknodDirectory; 
yaffs_MknodSpecial; 
yaffs_MknodSymLink;
yaffs_Link 

这四个函数最终都调用yaffs_MknodObject来完成创建对象的工作,只是调用参数不一样。

static yaffs_Object *yaffs_MknodObject(yaffs_ObjectType type, 
yaffs_Object * parent, 
const YCHAR * name,
__u32 mode, 
__u32 uid, 
__u32 gid,
yaffs_Object * equivalentObject, 
const YCHAR * aliasString, __u32 rdev) 

函数参数中,前面几个都很好理解,分别是对象类型,上级目录对象,文件名,访问权限,文件所属user id和group id; equivalentObject是创建硬链接时的原始文件对象;aliasString是symLink名称;rdev是设备文件的设备号。函数首先检查在父目录中是否已存在同名文件,然后同样调用yaffs_CreateNewObject创建新对象。参数-1表示由系统自行选择对象id。

if (in) { 
in->chunkId = -1; 
in->valid = 1; 
in->variantType = type; 
in->yst_mode = mode; 
in->yst_atime = in->yst_mtime = in->yst_ctime = Y_CURRENT_TIME;
in->yst_rdev = rdev; in->yst_uid = uid; 
in->yst_gid = gid;
in->nDataChunks = 0; 
yaffs_SetObjectName(in, name);
in->dirty = 1; 
yaffs_AddObjectToDirectory(parent, in); 
in->myDev = parent->myDev; 

这里列出的代码省略了和wince相关的条件编译部分。chunkId是对象头所在chunk,现在还没有将对象写入flash,所以置为-1;该新对象 暂时还没有数据,所以nDataChunks是0。in->dirty = 1表示该新对象信息还没有写入flash。然后通过yaffs_AddObjectToDirectory将新对象挂入父对象的子对象链表。接下来根据对象类型作不同处理:

switch (type) { 
case YAFFS_OBJECT_TYPE_SYMLINK: 
in->variant.symLinkVariant.alias =yaffs_CloneString(aliasString); 
break; 
case YAFFS_OBJECT_TYPE_HARDLINK: 
in->variant.hardLinkVariant.equivalentObject = equivalentObject; 
in->variant.hardLinkVariant.equivalentObjectId = equivalentObject->objectId; 
list_add(&in->hardLinks, &equivalentObject->hardLinks); 
break; 
case YAFFS_OBJECT_TYPE_FILE: 
case YAFFS_OBJECT_TYPE_DIRECTORY: 
case YAFFS_OBJECT_TYPE_SPECIAL: 
case YAFFS_OBJECT_TYPE_UNKNOWN: 
/* do nothing */ 
break; 
 }

对于最常用的文件对象和目录对象不做任何处理;如果是hardlink,就将新对象挂入原对象的 hardLinks链表。从这里我们可以看出,yaffs2在内存中是以链表的形式处理hardlink的。在将hardlink存储到flash上的时候,则是通过objectId将两者关联起来。Hardlink本身占用一个chunk存储对象头。最后,通过yaffs_UpdateObjectHeader将新对象头写入flash。

本文分享自微信公众号 - 瓜大三哥(xiguazai_tortoise),作者:xiguazaitortoise

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-05-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 文件地址映射之yaffs_GetTnode

    yaffs文件系统在更新文件数据的时候,会分配一块新的chunk,也就是说,同样的文件偏移地址,在该地址上的数据更新前和更新后,其对应的flash上的存储地址是...

    瓜大三哥
  • yaffsfs.c

    1.int yaffs_write(int fd, const void *buf, unsigned int nbyte)如果一个需要写入文件大于一个chun...

    瓜大三哥
  • Yaffs_guts(三)

    1.垃圾回收 1.static int yaffs_InitialiseBlocks(yaffs_Device *dev,int nBlocks)//块初始化 ...

    瓜大三哥
  • 文件地址映射之yaffs_GetTnode

    yaffs文件系统在更新文件数据的时候,会分配一块新的chunk,也就是说,同样的文件偏移地址,在该地址上的数据更新前和更新后,其对应的flash上的存储地址是...

    瓜大三哥
  • 【编程基础第四讲】遇到编译错误怎么办?

    存在问题: 现在刚入门的小伙伴,在编译初级的代码一遇到错误就显得不知所措,那么怎么办? 解决方案: 编程的新手,包括刚毕业工作的同学在解决编译错误时有时候不知...

    程序员互动联盟
  • 【目标检测】开源 | CVPR2020 | Scale Match在微小目标检测方面表现SOTA。

    随着深度卷积神经网络的兴起,视觉目标检测取得了前所未有的发展。然而,在大型图像中检测微小的物体(例如小于20像素的微小的人),检测效果仍不理想。由于巨大且复杂的...

    CNNer
  • 复工遭遇需求约束,疫情后将如何重建消费?

    谈到经济形势的判断,现在疫情对经济的冲击是非常大的,短期内对中国经济的影响是比较明显的。

    庄帅
  • Go 笔记之如何测试你的 Go 代码

    不论是开源项目,还是日常程序的开发,测试都是必不可少的一个环节。今天我们开始进入 Go 测试模块 testing 的介绍。

    波罗学
  • 如何选择性价比高的相位噪声测试仪

    假如一个时钟信号的一次谐波可以用一个正弦波来表示,如果某一刻发生变化时,则原本规则的周期正弦信号在变化的过程中将会出现拐点,这时频谱也将跟着会有相应的变化,而是...

    时频专家
  • Spark SQL / Catalyst 内部原理 与 RBO

    从上图可见,无论是直接使用 SQL 语句还是使用 DataFrame,都会经过如下步骤转换成 DAG 对 RDD 的操作

    Jason Guo

扫码关注云+社区

领取腾讯云代金券