文件地址映射之yaffs_GetTnode
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--;
}至此，分配工作就完成了。