yaffs2源代码分析(一)
?
yaffs2源代码分析(一)(转linuxforum 精华)
2007-09-22 20:24
3259人阅读
评论(0)
收藏
举报
yaffs2源代码情景分析 看过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)? 为了行文方便,后文中将yaffs_Tnode这个指针数组称为“一组”Tnode,而将数组中的每个元素称为“一个”Tnode。树中的每个节点,都是“一组”Tnode。 先看映射树的节点的分配。 static yaffs_Tnode *yaffs_GetTnode(yaffs_Device * dev) { yaffs_Tnode *tn = yaffs_GetTnodeRaw(dev); if(tn) memset(tn,(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++; } }? ?看过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位整数,所以我们需要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. 俺近日犯头痛,更新会慢一点 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |