文件地址映射之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 条评论
登录 后参与评论

相关文章

来自专栏逆向技术

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

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

2157
来自专栏张戈的专栏

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

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

1742
来自专栏码洞

基于Netty实现Redis协议的编码解码器

上面是Netty的服务器端基本消息处理结构,为了便于初学者理解,它和真实的结构有稍许出入。Netty是基于NIO的消息处理框架,用来高效处理网络IO。处理网络消...

2201
来自专栏jojo的技术小屋

原 荐 自己写JSON编辑器

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

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

JavaScript Source Map 详解

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

3405
来自专栏陈树义

简单笔记

1、类的表面类型和实际类型 实例对象有两个类型:表面类型(Apparent Type)和实际类型(ActualType),表面类型是声明时的类型,实际类型是对象...

2585
来自专栏史上最简单的Spring Cloud教程

Openresty最佳案例 | 第2篇:Lua入门

什么是lua Lua 是一种轻量小巧的脚本语言,用标准C语言编写并以源代码形式开放, 其设计目的是为了嵌入应用程序中,从而为应用程序提供灵活的扩展和定制功能...

6789
来自专栏Java帮帮-微信公众号-技术文章全总结

Java中的24种设计模式与7大原则

一、创建型模式 1、抽象工厂模式(Abstract factory pattern): 提供一个接口, 用于创建相关或依赖对象的家族, 而不需要指定具体类. 2...

3567
来自专栏木子昭的博客

Shell编程入门实例

图形化界面的Shell 幼儿园的小孩,可以面对图形化界面的电脑,手持鼠标,愉快的上网冲浪 字符型界面的Shell 计算机专业的新生面对的无界面的Linux,...

2856
来自专栏枕边书

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

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

2308

扫码关注云+社区