作者： 斑点
Email: byeyear@hotmail.com

1.前言
略。

2.yaffs文件系统简介
按理说这里应该出现一些诸如“yaffs是一种适合于NAND Flash的文件系统XXXXX”之类的字眼，不过考虑到网络上关于yaffs/yaffs2的介绍已经多如牛毛，所以同上，略。

3.本文内容组织
本文将模仿《linux内核源代码情景分析》一书，以情景分析的方式对yaffs2文件系统的源代码进行分析。首先将分析几组底层函数，如存储空间的分配和释放等；其次分析文件逻辑地址映射；然后是垃圾收集机制；接下来……Sorry，本人还没想好。:-)

4.说明
因为yaffs2貌似还在持续更新中，所以本文所列代码可能和读者手中的代码不完全一致。另外，本文读者应熟悉C语言，熟悉NAND Flash的基本概念（如block和page）。
Ok，步入正题。首先分析存储空间的分配。

5.NAND Flash存储空间分配和释放
我们知道，NAND Flash的基本擦除单位是Block，而基本写入单位是page。yaffs2在分配存储空间的时候是以page为单位的，不过在yaffs2中把基本存储单位称为chunk，和page是一样的大小，在大多数情况下和page是一个意思。在下文中我们使用chunk这个词，以保持和yaffs2的源代码一致。
我们先看存储空间的分配(在yaffs_guts.c中。这个文件也是yaffs2文件系统的核心部分)：
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函数：

[yaffs_AllocateChunk() => 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_GetBlockInfo(dev, dev->allocationBlockFinder);
if (bi->blockState == YAFFS_BLOCK_STATE_EMPTY) {
bi->blockState = YAFFS_BLOCK_STATE_ALLOCATING;
dev->sequenceNumber++;
bi->sequenceNumber = dev->sequenceNumber;
dev->nErasedBlocks--;
T(YAFFS_TRACE_ALLOCATE,
(TSTR("Allocated block %d, seq %d, %d left" TENDSTR),
dev->allocationBlockFinder, dev->sequenceNumber,
dev->nErasedBlocks));
return dev->allocationBlockFinder;
}
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上切下一个chunk：
if (dev->allocationBlock >= 0) {
bi = yaffs_GetBlockInfo(dev, dev->allocationBlock);
retVal = (dev->allocationBlock * dev->nChunksPerBlock) +
dev->allocationPage;
bi->pagesInUse++;
yaffs_SetChunkBit(dev, dev->allocationBlock,
dev->allocationPage);
dev->allocationPage++;
dev->nFreeChunks--;
/* If the block is full set the state to full */
if (dev->allocationPage >= dev->nChunksPerBlock) {
bi->blockState = YAFFS_BLOCK_STATE_FULL;
dev->allocationBlock = -1;
}
if(blockUsedPtr)
*blockUsedPtr = bi;
return retVal;
}
dev->allocationPage记录着上次分配的chunk在block中的序号，每分配一次加1。从这里我们可以看出，系统在分配chunk的时候是从block的开头到结尾按序分配的，直到一个block内的所有chunk全部分配完毕为止。retVal是该chunk在整个device内的总序号。PagesInUse记录着该block中已分配使用的page的数量。
系统在设备描述结构yaffs_Device 中维护着一张位图，该位图的每一位都代表着Flash上的一个chunk的状态。yaffs_SetChunkBit()将刚分配得到的chunk在位图中的对应位置1，表明该块已被使用。更新一些统计量后，就可以返回了。
上面就是我们分析的第一个函数，整个过程比较长，因为要顺带介绍一些重要的数据结构。接下来的分析相对就会简短一些，要不您看着累，俺打字更累:-)


作者：斑点
Email: byeyear@hotmail.com

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

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);
}
} else {
/* T(("Bad news deleting chunk %d\n",chunkId)); */
}
首先要判断一下该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在这点上是类似的。


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


作者：斑点
Email: byeyear@hotmail.com

为了行文方便，后文中将yaffs_Tnode这个指针数组称为“一组”Tnode，而将数组中的每个元素称为“一个”Tnode。树中的每个节点，都是“一组”Tnode。
先看映射树的节点的分配。
static yaffs_Tnode *yaffs_GetTnode(yaffs_Device * dev)
{
yaffs_Tnode *tn = yaffs_GetTnodeRaw(dev);

if(tn)
memset(tn, 0, (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8);

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;

上面说过，叶节点中一个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++;
}
}



作者：斑点
Email: byeyear@hotmail.com

看过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)) {    //当chunk序号跨越32位边界
bitInWord = (32 - bitInWord);    //计算出已读取部分
wordInMap++;    //读取位置+1
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位整数，所以我们需要64 / 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了。

注：
1. 欢迎转载，转载时请注明作者
2. 未经作者同意，不得用于商业目的
3. 俺近日犯头痛，更新会慢一点



作者：斑点
Email: byeyear@hotmail.com

下面我们看另一个情景，看看当文件长度增加的时候，映射树是如何扩展的。主要函数为
static yaffs_Tnode *yaffs_AddOrFindLevel0Tnode(yaffs_Device * dev,
yaffs_FileStructure * fStruct,
__u32 chunkId,
yaffs_Tnode *passedTn)
函数的前几行和yaffs_FindLevel0Tnode一样，对函数参数作一些检查。通过检查之后，首先看原映射树是否有足够的高度，如果高度不够，就先将其“拔高”：
if (requiredTallness > fStruct->topLevel) {
/* Not tall enough,gotta make the tree taller */
for (i = fStruct->topLevel; i < requiredTallness; i++) {
tn = yaffs_GetTnode(dev);
if (tn) {
tn->internal[0] = fStruct->top;
fStruct->top = tn;
} else {
T(YAFFS_TRACE_ERROR,
(TSTR("yaffs: no more tnodes" TENDSTR)));
}
}
fStruct->topLevel = requiredTallness;
}
for循环完成增加新层的功能。新增的每一层都只有一个节点（即一组Tnode），fStruct->top始终指向最新分配的节点。将映射树扩展到所需的高度之后，再根据需要将其“增肥”,扩展其“宽度”：
l = fStruct->topLevel;
tn = fStruct->top;
if(l > 0) {
while (l > 0 && tn) {
x = (chunkId >>
( 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_GetTnode(dev);
} else if(l == 1) {
/* Looking from level 1 at level 0 */
if (passedTn) {
/* If we already have one, then release it.*/
if(tn->internal[x])
yaffs_FreeTnode(dev,tn->internal[x]);
tn->internal[x] = passedTn;
} else if(!tn->internal[x]) {
/* Don't have one, none passed in */
tn->internal[x] = yaffs_GetTnode(dev);
}
}
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主要用于在删除文件时资源的释放。

p.s. 这个星期犯头疼，没力气写东西，所以短一些；希望下星期能好起来。接下来的几篇打算分析文件对象管理，大家捧个场 :-)



作者：斑点
Emai：byeyear@hotmail.com

7.文件系统对象
在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。




作者：斑点
Email: byeyear@hotmail.com

8. Yaffs2的垃圾收集机制
yaffs2的垃圾收集过程实际上包括两个方面：
·一是对那些不再使用的page作物理上的删除。我们在前面介绍chunk释放函数的时候曾经看到，yaffs2在删除chunk的时候仅仅是修改内存中的统计量，而真正的删除工作要留到垃圾收集的时候做。
·二是处理坏块。在对flash进行写操作的时候，我们也许要使用过一个block上的若干page之后才发现这是一个坏块，此时该块上已经有部分有用数据了，在垃圾收集的时候要对这种情况进行处理。
flash在使用过一段时间之后，满足以上两种情况的block也许不止一个，那么，yaffs2按照什么样的原则挑选合适的块进行回收呢？我们看下面的函数：
static int yaffs_BlockNotDisqualifiedFromGC(yaffs_Device * dev,
yaffs_BlockInfo * bi)
这个函数用来判定给定的块bi是否可以回收。
if (!dev->isYaffs2)
return 1; /* disqualification only applies to yaffs2. */
if (!bi->hasShrinkHeader)
return 1; /* can gc */
我们主要关心yaffs2。首先介绍一下什么是 hasShrinkHeader。
还是要提到yaffs2的“软”删除机制。假定我们现在需要减小一个文件的长度，比如从128K缩减到64K，在执行close()系统调用之后，yaffs2会将新的大小写入文件头，而这个文件头是会立即写入flash的，但是由于yaffs2使用软删除机制，原先那后面64K数据仍然残留在flash上，也就是说，出现了文件头和文件内容不一致的情况。此时就将文件头所在block的描述信息中的一个字段hasShrinkHeader置1，表明在垃圾回收时需要特别的处理。如果hasShrinkHeader＝0，那么该块是不需要特别的处理，是可以回收的；但是如果hasShrinkHeader＝1，那就需要注意了：如果我们所做的不仅仅是文件尺寸的收缩，而是文件的删除，并且在物理删除文件内容之前通过垃圾收集机制将文件头删掉了，那么残留的文件内容就成了“没娘要的孩子”，难以处理了。所以，我们必须先处理文件的残留内容，然后处理文件头。下面我们来看看yaffs2是如何实现处理这个目标的：
/* Find the oldest dirty sequence number if we don't know it and save it
* so we don't have to keep recomputing it.
*/
if (!dev->oldestDirtySequence) {
seq = dev->sequenceNumber;
for (i = dev->internalStartBlock; i <= dev->internalEndBlock;
i++) {
b = yaffs_GetBlockInfo(dev, i);
if (b->blockState == YAFFS_BLOCK_STATE_FULL &&
(b->pagesInUse - b->softDeletions) <
dev->nChunksPerBlock && b->sequenceNumber < seq) {
seq = b->sequenceNumber;
}
}
dev->oldestDirtySequence = seq;
}

/* Can't do gc of this block if there are any blocks older than this one that have
* discarded pages.
*/
return (bi->sequenceNumber <= dev->oldestDirtySequence);
在分析这段代码之前，我们再来回顾一下yaffs2的chunk分配过程和特点。如前文所述，yaffs2在分配chunk的时候遵循两个原则：一是在block内部严格从低地址的chunk向高地址的chunk按次序分配，二是一定要将一个block内的page全部分配完毕后才另行选择block进行分配。而且在分配的时候每挑选一个block就会递增一个序号。这样我们从block的序号就可以推断出该block的分配顺序。
除此之外，yaffs2会在应用程序作clsoe()系统调用的时候将新的文件头写入flash。因此，我们可以作出这样的结论：文件头所在block的序号，一定大于等于文件内容所在block的序号。这样，如果一个block信息结构内的hasShrinkHeader字段为1，并且该block的序号在系统中最小，我们就可以认为该block上的所有文件头对应的文件已经没有残余信息留在flash上了——这些残余信息如果存在，它们所在block的序号一定更小。有了这个结论，上面的代码就不难理解了，所以就不作解释了。
这个函数返回之后，我们就知道函数参数所指向的block是否可以回收了。但是，一个flash上可以回收的block大多数情况下不止一个，如何挑选出最合适的一个呢？——且听下回分解:-)

p.s. 最近厂里比较忙，可能更新会慢下来。私人企业，大家都知道的，时间没办法保证啊。

这阵子开始重读yaffs2，发现上次看的时候有很多地方理解上还是有问题的，写出来的东西也不严谨，最主要的是，文章不是很有条理。俺打算写完垃圾收集就暂停，待俺第二遍（也许还有第三遍，第四遍……）看结束的时候，整理一下思路，然后重新排标题，写分析。不知诸位是否有兴趣？