Chinaunix首页 | 论坛 | 博客
  • 博客访问: 209203
  • 博文数量: 54
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 230
  • 用 户 组: 普通用户
  • 注册时间: 2011-09-25 13:58
文章分类

全部博文(54)

文章存档

2014年(12)

2013年(42)

分类: LINUX

2013-03-25 16:38:22

原文地址:yaffs2源代码分析(二) 作者:piaoyizu

下面我们看另一个情景,看看当文件长度增加的时候,映射树是如何扩展的。主要函数为
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,发现上次看的时候有很多地方理解上还是有问题的,写出来的东西也不严谨,最主要的是,文章不是很有条理。俺打算写完垃圾收集就暂停,待俺第二遍(也许还有第三遍,第四遍……)看结束的时候,整理一下思路,然后重新排标题,写分析。不知诸位是否有兴趣?

阅读(1667) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~