文件地址映射之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--; 
 }

至此,分配工作就完成了。

原文发布于微信公众号 - 瓜大三哥(xiguazai_tortoise)

原文发表时间:2016-05-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏jojo的技术小屋

原 荐 自己写JSON编辑器

作者:汪娇娇 时间:2018年1月15日 下一篇:自己写代码对比工具 时间过得好快,一下子就2018年了,想起好久没写博客,不觉有些浪费了时光,今天便来补一篇。...

8987
来自专栏小勇DW3

自己手动写代码实现数据库连接池

池:一个高级的集合体(集合存储元素 + 管理方式–>提高效率),是对外提供同一种类型对象的集合,如(线程池、数据库连接池)  特性:复用性(每条连接可重复使用)...

1673
来自专栏决胜机器学习

《Redis设计与实现》读书笔记(二) ——Redis中的字典(Hash)

《Redis设计与实现》读书笔记(二) ——Redis中的字典(Hash) (原创内容,转载请注明来源,谢谢) 一、概述 字典,又称符号表、关联数组、映射,是一...

39910
来自专栏逸鹏说道

C# 温故而知新:Stream篇(六)

BufferedStream 目录: 简单介绍一下BufferedStream 如何理解缓冲区? BufferedStream的优势 从BufferedStre...

3435
来自专栏阮一峰的网络日志

JavaScript Source Map 详解

上周,jQuery 1.9发布。 ? 这是2.0版之前的最后一个新版本,有很多新功能,其中一个就是支持Source Map。 访问 http://ajax.go...

3435
来自专栏枕边书

搭建自己的PHP框架心得(二)

续言 对于本次更新,我想说: 本框架由本人挑时间完善,而我还不是PHP大神级的人物,所以框架漏洞难免,求大神们指出。 本框架的知识点应用都会写在博客里,大家有什...

2618
来自专栏DOTNET

.Net多线程编程—并发集合

并发集合 1 为什么使用并发集合? 原因主要有以下几点: System.Collections和System.Collections.Generic名称空间中所...

3497
来自专栏编程

用户输入input&int

1、input():让程序暂停,等待用户输入一些文本,获取用户输入后再执行下一行代码,例如: car = input("请问你需要租什么样的车:") print...

2080
来自专栏逆向技术

异常处理第二讲,结构化异常(微软未公开)

            异常处理第二讲,结构化异常(微软未公开) 讲解之前,请熟悉WinDbg的使用,工具使用的博客链接 一丶认识段寄存器FS的内容,以及作用 ...

2267
来自专栏张戈的专栏

Linux运维基础技能: 脚本编程与Linux命令

本系列文章一共三篇,分别为《脚本编程与 Linux 命令》、《接入层与网络基础》和《 MySQL 与 SQL 优化》,由腾讯高级工程师 luaruan(阮永顺)...

2282

扫码关注云+社区

领取腾讯云代金券