一种闪存文件的数据恢复方法和装置的制造方法
一种闪存文件的数据恢复方法和装置的制造方法
【技术领域】
[0001]本发明涉及存储技术领域，尤其涉及一种闪存文件的数据恢复方法和装置。
【背景技术】
[0002]闪存(Flash)结合了只读存储器(Read Only Memory,ROM)和随机存储器(RamdomAccess Memory, RAM)的长处,不仅具备电子可擦除可编程(EEPR0M)的性能,还具有非易失性随机访问存储器(Non-Volatile Random Access Memory, NVRAM)的优势一可以快速读取数据，使数据不会因为断电而丢失。在过去的20年里，嵌入式系统一直使用R0M/EPR0M作为它们的存储设备，然而，近年来Flash全面代替了 R0M/EPR0M在嵌入式系统中的地位，用作存储系统启动前引导程序(Bootloader)、操作系统和程序代码；或者，直接当硬盘如固体硬盘(SSD)使用。通常，Flash上存储有很多重要数据，一旦损坏或丢失都将造成严重后果。
[0003]存储技术发展多年，针对传统的机械硬盘即采用磁性介质的硬盘已有较为成熟的文件数据恢复技术，但目前还没有针对Flash具体可行的数据恢复方案。当前，许多闪存都采用第 2 版闪存日志型文件系统(Journalling Flash File System Vers1n 2, JFFS2)将各种信息以文件的形式进行管理和存储。在JFFS2中，对于删除或者修改文件的指令，JFFS2并不实际删除或修改原有的文件数据，而是通过写入新的文件数据节点来实现，这就为针对闪存文件的数据恢复提供了可能。
【发明内容】
[0004]为解决现有存在的技术问题，本发明实施例期望提供一种闪存文件的数据恢复方法和装置，能够针对基于JFFS2的闪存进行文件的数据恢复。
[0005]本发明实施例的技术方案是这样实现的:
[0006]本发明实施例提供一种闪存文件的数据恢复方法，该方法包括:
[0007]扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件；
[0008]根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符；
[0009]根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号；
[0010]当文件的最大版本号为N时，遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树；其中，N为正整数。
[0011]上述方案中，在对文件数据节点创建对应的数据节点描述符之前，所述方法还包括:
[0012]对文件数据节点进行循环冗余校验。
[0013]上述方案中，，所述遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树为:
[0014]按照版本号的降序或升序，建立所述文件的Ν个文件红黑树。
[0015]上述方案中，当为所述文件建立版本号η对应的文件红黑树时，所述方法包括:
[0016]遍历所述临时红黑树；
[0017]将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中；
[0018]其中，1彡η彡Ν，η为正整数。
[0019]上述方案中，当已建立文件的不同版本对应的文件红黑树时，所述方法还包括:
[0020]建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。
[0021]本发明实施例还提供一种闪存文件的数据恢复装置，该装置包括:扫描模块、临时红黑树建立模块、版本号确定模块和文件红黑树建立模块；其中，
[0022]扫描模块，用于扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件；
[0023]临时红黑树建立模块，用于根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符；
[0024]版本号确定模块，用于根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号；
[0025]文件红黑树建立模块，用于当文件的最大版本号为Ν时，遍历所述文件对应的临时红黑树,建立所述文件的Ν个版本所对应的Ν个文件红黑树；其中，Ν为正整数。
[0026]上述方案中，所述扫描模块包括:
[0027]校验单元，用于在对文件数据节点创建对应的数据节点描述符之前，对文件数据节点进行循环冗余校验。
[0028]上述方案中，所述文件红黑树建立模块包括:
[0029]排序单元，用于按照版本号的降序或升序，建立所述文件的Ν个文件红黑树。
[0030]上述方案中，所述文件红黑树建立模块包括:
[0031]遍历单元，用于遍历所述临时红黑树；
[0032]文件红黑树建立单元，用于将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中；
[0033]其中，1彡η彡Ν，η为正整数。
[0034]上述方案中，所述装置还包括:
[0035]结构体建立模块，用于当已建立文件的不同版本对应的文件红黑树时，建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。
[0036]本发明实施例所提供的闪存文件的数据恢复方法和装置，针对基于JFFS2的闪存，利用JFFS2中的内存描述符和红黑树机制，通过为文件建立所有版本号对应的文件红黑树，在脏块回收破坏数据前，能恢复全部删除数据或者历史数据；即使有部分数据被破坏未通过校验，其余通过校验的部分删除数据或者历史数据也可以被恢复。
【附图说明】
[0037]图1为本发明实施例提供的闪存文件数据恢复方法的实现流程示意图；
[0038]图2为本发明实施例提供的闪存文件数据恢复装置的组成结构示意图。
【具体实施方式】
[0039]为了更清楚地说明本发明实施例和技术方案，下面将结合附图及实施例对本发明的技术方案进行更详细的说明，显然，所描述的实施例是本发明的一部分实施例，而不是全部实施例。基本发明的实施例，本领域普通技术人员在不付出创造性劳动的前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0040]在本发明实施例中，闪存采用JFFS2管理所存储的信息。JFFS2是一个日志结构(log-structured)的文件系统，包含数据和原数据(meta-data)的节点在闪存上顺序的存储。JFFS2之所以选择日志结构的存储方式，是因为闪存的擦写块的擦写次数有限，因此，对闪存的更新应该是out-of-place的更新方式，即对文件数据的更新不在原存储区域，而是开辟新的存储区域存储更新后的数据，并以版本号来标识，以实现擦写块的磨损平衡(wearleveling)。
[0041 ] 操作系统内核扫描闪存时，将为闪存中每个文件建立多个描述符，用以表述文件，其中最关键的是索引节点。索引节点可涵盖多种文件系统，只描述所有文件系统共有的普通信息。为了更具体的表述文件，索引节点中包含有一个指针(u域)，指向具体文件系统的用以描述文件的结构体，对于JFFS2，u域指向结构体jffs2_inode_info。在现有的JFFS2中，一个文件对应一个结构体jffs2_in ode_info,在结构体jffs2_inode_info中，包含对应文件的最高版本号、指向文件红黑树根结点的指针和指向jffs2_inode_cache的指针等信息。jffs2_inode_CaChe是系统内核为表述对应文件而建立的内核描述符，包含有对应文件的标识号(ino)、硬链接(hard link)数、指向jffs2_raw_node_ref链表的头指针(nodes)等信息。jffs2_raw_node_ref是系统内核为表述文件的数据节点而建立的内核描述符，以下简称数据节点描述符；文件的一个数据节点对应唯一的数据节点描述符。一个文件的所有数据节点描述符组成一个以nodes为头指针的双向链表，该双向链表中数据节点描述符的存储顺序由系统内核扫描闪存的顺序决定。此外，系统内核为每个文件建立一个对应的临时红黑树，此临时红黑树中包含一个文件所有的数据节点描述符，且按照数据节点的版本号的降序/升序排列。通常，系统内核通过宏ref_0bSelete可判断一个数据节点是否为有效的数据节点，通过宏jfTs2_first_valid_node可得到文件的数据节点描述符双向链表中第一个有效的数据节点的指针，从而JFFS2可将当前有效的数据节点所对应的数据节点描述符按照该数据节点在闪存中偏移的由小到大组成文件红黑树，该文件红黑树的根节点地址存储于文件对应的结构体jffs2_inode_info中。系统内核通过遍历jffs2_inode_info中所指向的文件红黑树，即可获取当前有效的文件数据。当jffs2_inode_cache中硬链接数为0时,表示该jffs2_inode_cache所对应的文件为删除文件,因此现有的JFFS2中不会为该文件建立对应的文件红黑树，即jffs2_inode_info中对应的指针为空。通过jfTs2_raW_node_ref，系统内核可获取到对应的文件数据节点，从而获取该数据节点的版本号。当文件被修改时，JFFS2并不修改原有数据节点，而是在闪存上重新建立新的数据节点，将更新的数据写入，新建立的数据节点的版本号为:原数据节点版本号+1 ;因此，版本号越大表明该数据节点越新。当文件被删除时，JFFS2并不删除原有数据节点，而是写入一个与原硬链接对应的数据节点同名的数据节点，该数据节点类型设为无效，该数据节点的版本号在原数据节点版本号的基础上加1，将原来的硬链接节点设置为无效。
[0042]图1为本发明实施例提供的闪存文件的数据恢复方法的实现流程示意图，如图1所示，该方法包括:
[0043]步骤101，扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件；
[0044]具体的，系统内核为文件数据节点创建对应的数据节点描述符jffs2_raw_node_ref,为文件创建对应的内核描述符jffs2_inode_cache，过程与前述现有JFFS2的处理方法相同。
[0045]进一步的，在对文件数据节点创建对应的数据节点描述符之前，本步骤中还包括:对文件数据节点进行循环冗余校验(CRC)。
[0046]具体的，JFFS2中，文件数据节点中都包含CRC字段，只有CRC校验有效的数据节点中的数据才是可能有恢复价值的数据，若某个文件数据节点不能通过CRC校验，则表明该文件数据节点中的数据已被破坏或污染，不再有进行恢复的价值。
[0047]步骤102，根据数据节点描述符为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符。
[0048]具体的过程与前述现有JFFS2的处理方法相同。
[0049]步骤103，根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号。
[0050]具体的，文件的内核描述符jffs2_inode_cache中包含有对应文件的标识号；由文件的标识号可获取文件的临时红黑树，临时红黑树的节点本身是按照节点对应的数据节点的版本号的降序/升序存储，因此只要获取临时红黑树的头节点或尾节点所对应数据节点的版本号即此临时红黑树对应的文件的最大版本号。例如:文件的标识号为A，临时红黑树节点对应的数据节点的最大版本号N为3，则文件A的最大版本号为3。
[0051]步骤104，当文件的最大版本号为N时，遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树；其中，N为正整数。
[0052]进一步的，本步骤中遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树，可以是:
[0053]按照版本号的降序或升序，建立所述文件的N个文件红黑树。
[0054]具体的，当为所述文件建立版本号η对应的文件红黑树时，本步骤包括:
[0055]遍历所述临时红黑树；
[0056]将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中；
[0057]其中，1彡η彡Ν，η为正整数。
[0058]在一个实施例中，文件Α的最大版本号为3，即N = 3，按照版本号的降序，步骤104具体可包括:
[0059]系统内核建立依次建立版本号3、2、1对应的文件红黑树，即遍历所述临时红黑树，将该临时红黑树中所有版本号小于或等于3的节点加入版本号3对应的文件红黑树中；将该临时红黑树中所有版本号小于或等于2的节点加入版本号2对应的文件红黑树中；将该临时红黑树中所有版本号小于或等于1的节点加入版本号1对应的文件红黑树中，具体过程与JFFS2现有建立文件红黑树的机制相同。
[0060]进一步的，当已建立文件的不同版本对应的文件红黑树时，步骤104中还可包括:
[0061]建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。
[0062]具体的，将文件的不同版本都视为新的文件，为所述新的文件建立对应的索引节点，并将该索引节点的U域指向一个新的结构体jffs2_inode_info,因此,每个jffs2_inode_info对应一个版本的文件，即在现有的JFFS2中对同一个文件的内核描述符jffs2_inode_cache对应不止一个结构体jffs2_inode_info,每个结构体jffs2_inode_info表述一个版本号的文件数据。
[0063]使用上述实施例提供的闪存文件的数据恢复方法，针对基于JFFS2的闪存，利用JFFS2原有的内存描述符和红黑树机制，通过为文件建立所有版本号对应的文件红黑树，在脏块回收破坏数据前，可恢复全部删除数据或者历史数据；即使在部分数据被破坏后，也可恢复部分删除数据或者历史数据。
[0064]图2是本发明实施例提供的闪存文件的数据恢复装置的组成结构示意图，如图2所示，该数据恢复装置包括:扫描模块21、临时红黑树建立模块22、版本号确定模块23和文件红黑树建立模块24 ;其中，
[0065]扫描模块21，用于扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件；
[0066]临时红黑树建立模块22，用于根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符；
[0067]版本号确定模块23,用于根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号；
[0068]文件红黑树建立模块24，用于当文件的最大版本号为N时，遍历所述文件对应的临 时红黑树,建立所述文件的N个版本所对应的N个文件红黑树；其中，N为正整数。。
[0069]进一步的，在上述数据恢复装置中，扫描模块21包括:
[0070]校验单元，用于在对文件数据节点创建对应的数据节点描述符之前，对文件数据节点进行循环冗余校验。
[0071]进一步的，在上述数据恢复装置中，文件红黑树建立模块24包括:
[0072]排序单元，用于按照版本号的降序或升序，建立所述文件的N个文件红黑树。
[0073]进一步的，在上述数据恢复装置中，文件红黑树建立模块24包括:
[0074]遍历单元，用于遍历所述临时红黑树；
[0075]文件红黑树建立单元，用于将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中；
[0076]其中，1彡η彡Ν，η为正整数。
[0077]进一步的，在上述数据恢复装置还可包括:
[0078]结构体建立模块，用于当已建立文件的不同版本对应的文件红黑树时，建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。
[0079]上述各个模块及各个单元在实际应用中，均可由位于数据恢复装置的中央处理器(CPU)、微处理器(MPU)、数字信号处理器(DSP)、或现场可编程门阵列(FPGA)实现。
[0080]本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用硬件实施例、软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器和光学存储器等)上实施的计算机程序产品的形式。
[0081]本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0082]这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0083]这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0084]以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。
【主权项】
1.一种闪存文件的数据恢复方法，其特征在于，所述方法包括: 扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件； 根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符； 根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号； 当文件的最大版本号为N时，遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树；其中，N为正整数。2.根据权利要求1所述的数据恢复方法，其特征在于，在对文件数据节点创建对应的数据节点描述符之前，所述方法还包括: 对文件数据节点进行循环冗余校验。3.根据权利要求1所述的数据恢复方法，其特征在于，所述遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树为: 按照版本号的降序或升序，建立所述文件的N个文件红黑树。4.根据权利要求1所述的数据恢复方法，其特征在于，当为所述文件建立版本号η对应的文件红黑树时，所述方法包括: 遍历所述临时红黑树； 将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中； 其中，1彡η彡Ν，η为正整数。5.根据权利要求1所述的数据恢复方法，其特征在于，当已建立文件的不同版本对应的文件红黑树时，所述方法还包括: 建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。6.一种闪存文件的数据恢复装置，其特征在于，所述装置包括:扫描模块、临时红黑树建立模块、版本号确定模块和文件红黑树建立模块；其中， 扫描模块，用于扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件； 临时红黑树建立模块，用于根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符； 版本号确定模块，用于根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号; 文件红黑树建立模块，用于当文件的最大版本号为Ν时，遍历所述文件对应的临时红黑树，建立所述文件的Ν个版本所对应的Ν个文件红黑树；其中，Ν为正整数。7.根据权利要求6所述的数据恢复装置，其特征在于，所述扫描模块包括: 校验单元，用于在对文件数据节点创建对应的数据节点描述符之前，对文件数据节点进行循环冗余校验。8.根据权利要求6所述的数据恢复装置，其特征在于，所述文件红黑树建立模块包括: 排序单元，用于按照版本号的降序或升序，建立所述文件的N个文件红黑树。9.根据权利要求6所述的数据恢复装置，其特征在于，所述文件红黑树建立模块包括: 遍历单元，用于遍历所述临时红黑树； 文件红黑树建立单元，用于将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中； 其中，1彡η彡Ν，η为正整数。10.根据权利要求6所述的数据恢复装置，其特征在于，所述装置还包括: 结构体建立模块，用于当已建立文件的不同版本对应的文件红黑树时，建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。
【专利摘要】本发明公开了一种闪存文件的数据恢复方法，包括：扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件；根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符；根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号；当文件的最大版本号为N时，遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树；其中，N为正整数。本发明还同时公开了一种闪存文件的数据恢复装置。
【IPC分类】G06F11/14, G06F17/30
【公开号】CN105487939
【申请号】CN201410530972
【发明人】么爱利
【申请人】中兴通讯股份有限公司
【公开日】2016年4月13日
【申请日】2014年10月10日
【公告号】WO2016054899A1
【技术领域】
[0001]本发明涉及存储技术领域，尤其涉及一种闪存文件的数据恢复方法和装置。
【背景技术】
[0002]闪存(Flash)结合了只读存储器(Read Only Memory,ROM)和随机存储器(RamdomAccess Memory, RAM)的长处,不仅具备电子可擦除可编程(EEPR0M)的性能,还具有非易失性随机访问存储器(Non-Volatile Random Access Memory, NVRAM)的优势一可以快速读取数据，使数据不会因为断电而丢失。在过去的20年里，嵌入式系统一直使用R0M/EPR0M作为它们的存储设备，然而，近年来Flash全面代替了 R0M/EPR0M在嵌入式系统中的地位，用作存储系统启动前引导程序(Bootloader)、操作系统和程序代码；或者，直接当硬盘如固体硬盘(SSD)使用。通常，Flash上存储有很多重要数据，一旦损坏或丢失都将造成严重后果。
[0003]存储技术发展多年，针对传统的机械硬盘即采用磁性介质的硬盘已有较为成熟的文件数据恢复技术，但目前还没有针对Flash具体可行的数据恢复方案。当前，许多闪存都采用第 2 版闪存日志型文件系统(Journalling Flash File System Vers1n 2, JFFS2)将各种信息以文件的形式进行管理和存储。在JFFS2中，对于删除或者修改文件的指令，JFFS2并不实际删除或修改原有的文件数据，而是通过写入新的文件数据节点来实现，这就为针对闪存文件的数据恢复提供了可能。
【发明内容】
[0004]为解决现有存在的技术问题，本发明实施例期望提供一种闪存文件的数据恢复方法和装置，能够针对基于JFFS2的闪存进行文件的数据恢复。
[0005]本发明实施例的技术方案是这样实现的:
[0006]本发明实施例提供一种闪存文件的数据恢复方法，该方法包括:
[0007]扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件；
[0008]根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符；
[0009]根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号；
[0010]当文件的最大版本号为N时，遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树；其中，N为正整数。
[0011]上述方案中，在对文件数据节点创建对应的数据节点描述符之前，所述方法还包括:
[0012]对文件数据节点进行循环冗余校验。
[0013]上述方案中，，所述遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树为:
[0014]按照版本号的降序或升序，建立所述文件的Ν个文件红黑树。
[0015]上述方案中，当为所述文件建立版本号η对应的文件红黑树时，所述方法包括:
[0016]遍历所述临时红黑树；
[0017]将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中；
[0018]其中，1彡η彡Ν，η为正整数。
[0019]上述方案中，当已建立文件的不同版本对应的文件红黑树时，所述方法还包括:
[0020]建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。
[0021]本发明实施例还提供一种闪存文件的数据恢复装置，该装置包括:扫描模块、临时红黑树建立模块、版本号确定模块和文件红黑树建立模块；其中，
[0022]扫描模块，用于扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件；
[0023]临时红黑树建立模块，用于根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符；
[0024]版本号确定模块，用于根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号；
[0025]文件红黑树建立模块，用于当文件的最大版本号为Ν时，遍历所述文件对应的临时红黑树,建立所述文件的Ν个版本所对应的Ν个文件红黑树；其中，Ν为正整数。
[0026]上述方案中，所述扫描模块包括:
[0027]校验单元，用于在对文件数据节点创建对应的数据节点描述符之前，对文件数据节点进行循环冗余校验。
[0028]上述方案中，所述文件红黑树建立模块包括:
[0029]排序单元，用于按照版本号的降序或升序，建立所述文件的Ν个文件红黑树。
[0030]上述方案中，所述文件红黑树建立模块包括:
[0031]遍历单元，用于遍历所述临时红黑树；
[0032]文件红黑树建立单元，用于将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中；
[0033]其中，1彡η彡Ν，η为正整数。
[0034]上述方案中，所述装置还包括:
[0035]结构体建立模块，用于当已建立文件的不同版本对应的文件红黑树时，建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。
[0036]本发明实施例所提供的闪存文件的数据恢复方法和装置，针对基于JFFS2的闪存，利用JFFS2中的内存描述符和红黑树机制，通过为文件建立所有版本号对应的文件红黑树，在脏块回收破坏数据前，能恢复全部删除数据或者历史数据；即使有部分数据被破坏未通过校验，其余通过校验的部分删除数据或者历史数据也可以被恢复。
【附图说明】
[0037]图1为本发明实施例提供的闪存文件数据恢复方法的实现流程示意图；
[0038]图2为本发明实施例提供的闪存文件数据恢复装置的组成结构示意图。
【具体实施方式】
[0039]为了更清楚地说明本发明实施例和技术方案，下面将结合附图及实施例对本发明的技术方案进行更详细的说明，显然，所描述的实施例是本发明的一部分实施例，而不是全部实施例。基本发明的实施例，本领域普通技术人员在不付出创造性劳动的前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0040]在本发明实施例中，闪存采用JFFS2管理所存储的信息。JFFS2是一个日志结构(log-structured)的文件系统，包含数据和原数据(meta-data)的节点在闪存上顺序的存储。JFFS2之所以选择日志结构的存储方式，是因为闪存的擦写块的擦写次数有限，因此，对闪存的更新应该是out-of-place的更新方式，即对文件数据的更新不在原存储区域，而是开辟新的存储区域存储更新后的数据，并以版本号来标识，以实现擦写块的磨损平衡(wearleveling)。
[0041 ] 操作系统内核扫描闪存时，将为闪存中每个文件建立多个描述符，用以表述文件，其中最关键的是索引节点。索引节点可涵盖多种文件系统，只描述所有文件系统共有的普通信息。为了更具体的表述文件，索引节点中包含有一个指针(u域)，指向具体文件系统的用以描述文件的结构体，对于JFFS2，u域指向结构体jffs2_inode_info。在现有的JFFS2中，一个文件对应一个结构体jffs2_in ode_info,在结构体jffs2_inode_info中，包含对应文件的最高版本号、指向文件红黑树根结点的指针和指向jffs2_inode_cache的指针等信息。jffs2_inode_CaChe是系统内核为表述对应文件而建立的内核描述符，包含有对应文件的标识号(ino)、硬链接(hard link)数、指向jffs2_raw_node_ref链表的头指针(nodes)等信息。jffs2_raw_node_ref是系统内核为表述文件的数据节点而建立的内核描述符，以下简称数据节点描述符；文件的一个数据节点对应唯一的数据节点描述符。一个文件的所有数据节点描述符组成一个以nodes为头指针的双向链表，该双向链表中数据节点描述符的存储顺序由系统内核扫描闪存的顺序决定。此外，系统内核为每个文件建立一个对应的临时红黑树，此临时红黑树中包含一个文件所有的数据节点描述符，且按照数据节点的版本号的降序/升序排列。通常，系统内核通过宏ref_0bSelete可判断一个数据节点是否为有效的数据节点，通过宏jfTs2_first_valid_node可得到文件的数据节点描述符双向链表中第一个有效的数据节点的指针，从而JFFS2可将当前有效的数据节点所对应的数据节点描述符按照该数据节点在闪存中偏移的由小到大组成文件红黑树，该文件红黑树的根节点地址存储于文件对应的结构体jffs2_inode_info中。系统内核通过遍历jffs2_inode_info中所指向的文件红黑树，即可获取当前有效的文件数据。当jffs2_inode_cache中硬链接数为0时,表示该jffs2_inode_cache所对应的文件为删除文件,因此现有的JFFS2中不会为该文件建立对应的文件红黑树，即jffs2_inode_info中对应的指针为空。通过jfTs2_raW_node_ref，系统内核可获取到对应的文件数据节点，从而获取该数据节点的版本号。当文件被修改时，JFFS2并不修改原有数据节点，而是在闪存上重新建立新的数据节点，将更新的数据写入，新建立的数据节点的版本号为:原数据节点版本号+1 ;因此，版本号越大表明该数据节点越新。当文件被删除时，JFFS2并不删除原有数据节点，而是写入一个与原硬链接对应的数据节点同名的数据节点，该数据节点类型设为无效，该数据节点的版本号在原数据节点版本号的基础上加1，将原来的硬链接节点设置为无效。
[0042]图1为本发明实施例提供的闪存文件的数据恢复方法的实现流程示意图，如图1所示，该方法包括:
[0043]步骤101，扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件；
[0044]具体的，系统内核为文件数据节点创建对应的数据节点描述符jffs2_raw_node_ref,为文件创建对应的内核描述符jffs2_inode_cache，过程与前述现有JFFS2的处理方法相同。
[0045]进一步的，在对文件数据节点创建对应的数据节点描述符之前，本步骤中还包括:对文件数据节点进行循环冗余校验(CRC)。
[0046]具体的，JFFS2中，文件数据节点中都包含CRC字段，只有CRC校验有效的数据节点中的数据才是可能有恢复价值的数据，若某个文件数据节点不能通过CRC校验，则表明该文件数据节点中的数据已被破坏或污染，不再有进行恢复的价值。
[0047]步骤102，根据数据节点描述符为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符。
[0048]具体的过程与前述现有JFFS2的处理方法相同。
[0049]步骤103，根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号。
[0050]具体的，文件的内核描述符jffs2_inode_cache中包含有对应文件的标识号；由文件的标识号可获取文件的临时红黑树，临时红黑树的节点本身是按照节点对应的数据节点的版本号的降序/升序存储，因此只要获取临时红黑树的头节点或尾节点所对应数据节点的版本号即此临时红黑树对应的文件的最大版本号。例如:文件的标识号为A，临时红黑树节点对应的数据节点的最大版本号N为3，则文件A的最大版本号为3。
[0051]步骤104，当文件的最大版本号为N时，遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树；其中，N为正整数。
[0052]进一步的，本步骤中遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树，可以是:
[0053]按照版本号的降序或升序，建立所述文件的N个文件红黑树。
[0054]具体的，当为所述文件建立版本号η对应的文件红黑树时，本步骤包括:
[0055]遍历所述临时红黑树；
[0056]将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中；
[0057]其中，1彡η彡Ν，η为正整数。
[0058]在一个实施例中，文件Α的最大版本号为3，即N = 3，按照版本号的降序，步骤104具体可包括:
[0059]系统内核建立依次建立版本号3、2、1对应的文件红黑树，即遍历所述临时红黑树，将该临时红黑树中所有版本号小于或等于3的节点加入版本号3对应的文件红黑树中；将该临时红黑树中所有版本号小于或等于2的节点加入版本号2对应的文件红黑树中；将该临时红黑树中所有版本号小于或等于1的节点加入版本号1对应的文件红黑树中，具体过程与JFFS2现有建立文件红黑树的机制相同。
[0060]进一步的，当已建立文件的不同版本对应的文件红黑树时，步骤104中还可包括:
[0061]建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。
[0062]具体的，将文件的不同版本都视为新的文件，为所述新的文件建立对应的索引节点，并将该索引节点的U域指向一个新的结构体jffs2_inode_info,因此,每个jffs2_inode_info对应一个版本的文件，即在现有的JFFS2中对同一个文件的内核描述符jffs2_inode_cache对应不止一个结构体jffs2_inode_info,每个结构体jffs2_inode_info表述一个版本号的文件数据。
[0063]使用上述实施例提供的闪存文件的数据恢复方法，针对基于JFFS2的闪存，利用JFFS2原有的内存描述符和红黑树机制，通过为文件建立所有版本号对应的文件红黑树，在脏块回收破坏数据前，可恢复全部删除数据或者历史数据；即使在部分数据被破坏后，也可恢复部分删除数据或者历史数据。
[0064]图2是本发明实施例提供的闪存文件的数据恢复装置的组成结构示意图，如图2所示，该数据恢复装置包括:扫描模块21、临时红黑树建立模块22、版本号确定模块23和文件红黑树建立模块24 ;其中，
[0065]扫描模块21，用于扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件；
[0066]临时红黑树建立模块22，用于根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符；
[0067]版本号确定模块23,用于根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号；
[0068]文件红黑树建立模块24，用于当文件的最大版本号为N时，遍历所述文件对应的临 时红黑树,建立所述文件的N个版本所对应的N个文件红黑树；其中，N为正整数。。
[0069]进一步的，在上述数据恢复装置中，扫描模块21包括:
[0070]校验单元，用于在对文件数据节点创建对应的数据节点描述符之前，对文件数据节点进行循环冗余校验。
[0071]进一步的，在上述数据恢复装置中，文件红黑树建立模块24包括:
[0072]排序单元，用于按照版本号的降序或升序，建立所述文件的N个文件红黑树。
[0073]进一步的，在上述数据恢复装置中，文件红黑树建立模块24包括:
[0074]遍历单元，用于遍历所述临时红黑树；
[0075]文件红黑树建立单元，用于将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中；
[0076]其中，1彡η彡Ν，η为正整数。
[0077]进一步的，在上述数据恢复装置还可包括:
[0078]结构体建立模块，用于当已建立文件的不同版本对应的文件红黑树时，建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。
[0079]上述各个模块及各个单元在实际应用中，均可由位于数据恢复装置的中央处理器(CPU)、微处理器(MPU)、数字信号处理器(DSP)、或现场可编程门阵列(FPGA)实现。
[0080]本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用硬件实施例、软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器和光学存储器等)上实施的计算机程序产品的形式。
[0081]本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0082]这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0083]这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0084]以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。
【主权项】
1.一种闪存文件的数据恢复方法，其特征在于，所述方法包括: 扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件； 根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符； 根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号； 当文件的最大版本号为N时，遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树；其中，N为正整数。2.根据权利要求1所述的数据恢复方法，其特征在于，在对文件数据节点创建对应的数据节点描述符之前，所述方法还包括: 对文件数据节点进行循环冗余校验。3.根据权利要求1所述的数据恢复方法，其特征在于，所述遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树为: 按照版本号的降序或升序，建立所述文件的N个文件红黑树。4.根据权利要求1所述的数据恢复方法，其特征在于，当为所述文件建立版本号η对应的文件红黑树时，所述方法包括: 遍历所述临时红黑树； 将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中； 其中，1彡η彡Ν，η为正整数。5.根据权利要求1所述的数据恢复方法，其特征在于，当已建立文件的不同版本对应的文件红黑树时，所述方法还包括: 建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。6.一种闪存文件的数据恢复装置，其特征在于，所述装置包括:扫描模块、临时红黑树建立模块、版本号确定模块和文件红黑树建立模块；其中， 扫描模块，用于扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件； 临时红黑树建立模块，用于根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符； 版本号确定模块，用于根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号; 文件红黑树建立模块，用于当文件的最大版本号为Ν时，遍历所述文件对应的临时红黑树，建立所述文件的Ν个版本所对应的Ν个文件红黑树；其中，Ν为正整数。7.根据权利要求6所述的数据恢复装置，其特征在于，所述扫描模块包括: 校验单元，用于在对文件数据节点创建对应的数据节点描述符之前，对文件数据节点进行循环冗余校验。8.根据权利要求6所述的数据恢复装置，其特征在于，所述文件红黑树建立模块包括: 排序单元，用于按照版本号的降序或升序，建立所述文件的N个文件红黑树。9.根据权利要求6所述的数据恢复装置，其特征在于，所述文件红黑树建立模块包括: 遍历单元，用于遍历所述临时红黑树； 文件红黑树建立单元，用于将所述临时红黑树中所有版本号小于或等于η的节点加入版本号η对应的文件红黑树中； 其中，1彡η彡Ν，η为正整数。10.根据权利要求6所述的数据恢复装置，其特征在于，所述装置还包括: 结构体建立模块，用于当已建立文件的不同版本对应的文件红黑树时，建立不同的结构体，以描述不同的文件版本，所述结构体中包括文件的版本号和指向所述版本号对应的文件红黑树的根节点指针。
【专利摘要】本发明公开了一种闪存文件的数据恢复方法，包括：扫描闪存存储区域，为文件数据节点创建对应的数据节点描述符，为文件创建对应的内核描述符，所述文件数据节点包括已被标记为无效节点的数据节点，所述文件包括已被标记为删除文件的文件；根据数据节点描述符，为文件建立对应的临时红黑树，所述临时红黑树中包含文件的已被标记为无效节点在内的全部数据节点所对应的数据节点描述符；根据文件对应的内核描述符和临时红黑树，确定文件的最大版本号；当文件的最大版本号为N时，遍历所述文件对应的临时红黑树，建立所述文件的N个版本所对应的N个文件红黑树；其中，N为正整数。本发明还同时公开了一种闪存文件的数据恢复装置。
【IPC分类】G06F11/14, G06F17/30
【公开号】CN105487939
【申请号】CN201410530972
【发明人】么爱利
【申请人】中兴通讯股份有限公司
【公开日】2016年4月13日
【申请日】2014年10月10日
【公告号】WO2016054899A1
最新回复(0)