下面我们看另一个情景，看看当文件长度增加的时候，映射树是如何扩展的。主要函数为
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. 这个星期犯头疼，没力气写东西，所以短一些；希望下星期能好起来。接下来的几篇打算分析文件对象管理，大家捧个场 :-)
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。
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，发现上次看的时候有很多地方理解上还是有问题的，写出来的东西也不严谨，最主要的是，文章不是很有条理。俺打算写完垃圾收集就暂停，待俺第二遍（也许还有第三遍，第四遍……）看结束的时候，整理一下思路，然后重新排标题，写分析。不知诸位是否有兴趣？
