非易失性文件系统中进行快速编辑的回收算法

摘要

处理设备将片断文件存储到非易失性存储器，这些片断文件在RAM中作为直接指针而被跟踪。原始文件存储在存储器中，数据编辑被存储在新存储位置，并在与存储器块相关联的标题结构中作为文件偏移而被跟踪。新回收/折叠算法采用已编辑的文件偏移将数据折叠到被保留的存储器块。

说明书

随着计算机威力的不断增强，对能够传送多种媒体选择譬如音频和视频 资料的网络的兴趣也不断提高。技术的发展已经允许对大量能够从计算设 备迅速传输到网络内其他设备的语音、视频、图像和数据进行数字化和压 缩。因而，各种不同的数字技术能使大量数据从一个系统传输到另一个系 统。

静态数据类型譬如图像和视频对象和流数据类型譬如音频和视频数据 需要大的存储器空间容量。流数据的发送对能够满足数据对象严格底限要 求的存储器件提出了约束要求。所以需要改进新存储器的性能。

附图说明

在本说明书的结论部分特别指出了关于本发明的主题，并对其明确提出 了权利要求。但是，无论是本发明的组织还是操作方法及其目的、特性和 优点都可以参考下面的详细说明并结合所附附图而获得对本发明的最佳理 解。本发明的附图包括：

图1是表示无线设备的框图，该无线设备组合了电路以便使无线设备能 够执行符合本发明的新回收/折叠算法；

图2是非易失性存储器的框图，该存储器构造成能够在执行该新回收/ 折叠算法之前存储原始文件；

图3是非易失性存储器的框图，该存储器构造成能够在执行该新回收/ 折叠算法之前存储已编辑的数据；以及

图4是非易失性存储器的框图，在执行该新回收/折叠算法之后，该存 储器既存储原始文件数据也存储已编辑文件数据。

应当理解，为了说明的简明和清晰，这些附图中的元件不一定按照比例 绘制。举例来说，为了图形清晰，某些元件的尺寸相对其他元件而言已被 夸大。而且，在认为合适的时候，各图之间也重复使用参考标号以便表示 相应的或类似的元件。

具体实施方式

在下面的详细说明中，设定了许多细节以便提供对本发明的透彻理解。 但是，本领域人员应当理解，本发明可以不采用这些特定细节来实现。在 其他情况下，对人们熟知的方法、过程、部件和电路都没有加以详细说明， 目的就是不希望因此而模糊了本发明的特点。

在下面的说明书和权利要求书中，可以采用术语“耦合到”、“连接到” 以及它们的派生词。但应当理解，这些术语并非是要被用作彼此的同义词。 相反，在特定的实施例中，“连接到”可以被用来表示两个或多个元件彼 此直接物理或电气接触，而“耦合到”可以表示两个或多个元件也许彼此 直接接触，也许彼此不直接接触，但是它们仍然协同运行或者彼此互动。

图1是一幅框图，表示计算系统的一部分，该部分包括了本发明的、可 以被组合到处理设备10的特征。在所示的实施例中，处理设备10是无线 通信设备，但是本发明并不局限于无线应用场合。在该无线实施例中，收 发器12同时从一个或多个天线接收和发送已调制信号。该模拟前端收发器 可以是独立射频(RF)集成模拟电路，作为另一种选择，也可以嵌入处理 器14而成为混合模式集成电路。所接收到的已调制信号可以经过降频变换、 滤波，然后再变换为基带数字信号。

处理器14可以是独立处理设备或者芯片组，包括利用一个或多个处理 器核的基带和应用处理功能。一般来讲，处理器核14可以处理获取指令、 生成解码、寻找操作数以及执行适当操作并存储结果的功能。存储器控制 器20控制存储器接口22，该接口能够使处理器14中嵌入的处理器核和高 速缓存存储器与外部系统存储器交换数据。尽管图中没有画出，但是处理 设备10可以包括其他部件，譬如附加的处理器核、输入/输出(I/O)设备、 外围部件以及系统存储器件。不过，为了简单起见，没有画出这些附加部 件。另外，该系统存储器可以包括磁盘、随机存取存储器(RAM)、只读存 储器(ROM)以及非易失性存储器24等存储器的组合，当然，无论是该系 统存储器中包含的存储器类型还是种类都不是对本发明的限制。

非易失性存储器24可以是NAND存储器件或者NOR存储器件。非易失性 存储器24的示例可以有ETOXTM闪存存储器、电可擦写和可编程只读存储器 (EEPROM)、铁电随机存取存储器(FRAM)、聚合物铁电随机存取存储器 (PFRAM)、磁随机存取存储器(MRAM)、双向开关半导体器件统一存储器 (0UM)或者即使处理设备10处于供电保护模式也能够存储指令和/或数据 并保持该信息的任何其他设备。但是应当理解，本发明的范围并不限于这 些示例。

尽管处理器14和非易失性存储器24被画成组合为无线设备10的形式， 但该处理器和非易失性存储器可以被一道包含在所述无线应用场合之外的 应用场合。相应地，随着将要求保护的主题组合到台式计算机、膝上型电 脑、灵巧电话、MP3播放器、摄像机、通信机以及个人数字助理(PDA)、 医学或生物技术设备、汽车安全性和保护设备、汽车信息娱乐产品等等， 本发明的实施例就可以被应用到各种产品。但是应当理解，本发明的范围 并不限于这些示例。

处理器14包括分级文件管理系统16和随机存取存储器(RAM)表18， 提供处理不同大小数据块的能力以便改进非易失性存储器24内的可用存储 空间的利用情况。由处理器14执行的软件的一个示例是存储器管理软件， 该软件可以被用来管理非易失性存储器24内的代码、数据和文件的存储。 在各种实施例中，存储器管理软件可以被称为代码管理软件、数据管理软 件、文件管理软件、文件系统软件、文件系统管理软件、闪存文件管理软 件或者闪存媒体管理器。

在一个实施例中，该存储器管理软件可以被存储到非易失性存储器24， 并且可以从该非易失性存储器获取和执行而无需将该代码装载到易失性随 机存取存储器(RAM)的步骤，这在某些闪存存储器中称作就地执行(XIP)。 在另一个实施例中，该存储器管理软件可以被存储在处理器14内。

文件管理系统16组合了多个为嵌入式应用提供存储解决方案的独特能 力，包括减少失电替换(PLR)状态数量并减少存储器片断跟踪的增强回收 /折叠算法。

图2表示非易失性存储器24的实施例，该存储器包括被构造成或排列 成一个或多个存储器块的存储器阵列。如该图所示，非易失性存储器24包 括被标记为块202、204、206、208和210的5个存储器块，但是要注意， 无论是块的数量还是块的大小都不是对本发明的限制。换句话说，非易失 性存储器24可以包括少于5块或多于5块的阵列。而且要注意，块210被 标记为备用块，在执行了回收/折叠算法后被用作存储数据的替代块。非易 失性存储器24的阵列可以包括一个或多个备用块，被保留用来在运行回收 算法时存储文件。

该阵列中的每个块包括多个非易失性存储器单元，譬如能够在每个存储 器单元中存储1位信息或多位信息的闪存存储器单元。对存储在这些存储 器块中的信息的存取通过在处理器14上执行的存储器管理软件所生成的物 理地址提供。鉴于非易失性存储器24可以仅仅在块层次上(逐块地)被擦 写，所以特定物理地址范围就映射各个存储器块内在字节层次上存储的信 息。

块标题212、214、216、218和220对应于各个块202、204、206、208 和210，而且可以被用来存储与相关块有关的信息。作为示例，块标题可以 包括存储在相关块内的文件大小、相应文件在该块内的位置(譬如该块内 的字节偏移，指向文件起点的指针)、对相应文件所属的文件加以识别的 标识符以及该相应文件相对于所有其它文件的位置。注意，存储在这些块 标题中的一些信息可以被用来将文件部分链接或结合到一起。

块标题212、214、216、218和220还可以包括表示相应文件状态或状 况的一个或多个状态位。作为示例，该块标题可以包含一个或多个状态位， 表示整个文件的写入是否由于失电而被中断。失电替换(PLR)算法或方案 识别在将文件写入非易失性存储器24的过程中由于失电而生成的已破坏文 件或无效文件。在PLR算法探测已破坏文件时，就会正确设置该块标题中 的恰当状态或状况位。

写入非易失性存储器24中的文件可以被连续存储，作为另一种选择， 该文件可以被划分或分割为一个或多个文件片断。在一些实施例中，该文 件管理软件在接收到将文件存储到非易失性存储器24的请求时，可以将文 件划分或分割为一个或多个文件片断，并将这些片断存储到非易失性存储 器24的一个或多个块中。

图2表示写入闪存存储器的自由空间并在块202和204中简单标记为 “数据”的数据、指令、文件或代码。块标题212和214表示该文件在块 202和204中的存储情况，并包括关于该文件大小、位置等等更新信息。简 单参看图1可以发现，RAM表18通过链接和偏移值来跟踪被写入非易失性 存储器24中的文件。RAM表18在启动时生成，所存储的信息在断电时丢失。 包含所有链接位置的RAM表18允许较快的存储器阅读。RAM表18在初始化 时就已存在，而且被用来读取/寻找文件。

图3是图2所示的、将文件存储到块202和204的示例的延续。图3进 一步表示了对以前存储在块202中的已有文件部分做的修改和编辑。该已 有文件的已编辑部分304在块202中被标记为“可折叠数据”，替换该已 编辑部分的相应新数据308被标记为“已编辑数据”并被存储在块206中。 该文件的未经编辑的、原始的部分被标记为数据302和数据306。同样， 简单地参看图1可以发现，RAM表18采用编辑号码来跟踪编辑，表中只存 储对那个偏移的最新编辑。RAM表18存储可以被用于回收和执行其他操作 的已知的好数据。

图4表示在执行回收/折叠算法后根据本发明存储在非易失性存储器24 中的数据。回收/折叠算法可以在文件管理系统16的控制下周期运行或者 在特定时间启动。回收/折叠算法应当很频繁地运行以便提供有益于无线设 备10的干净存储器系统。RAM表18提供带有链接的指针和偏移值以便将来 自该原始文件和已编辑数据部分的数据写到备用块210。这样，通过运行该 回收/折叠算法，该文件和新的编辑就可以作为连续文件被存储到备用块 210。

当回收/折叠算法被启动时，RAM表18就向处理器14提供指针以便将 存储在块202中标记为数据302的文件部分写到备用块210。在将数据302 写到备用块210结束时，RAM表18就提供指向已编辑数据308的指针，以 前存储在块206的已编辑数据则被写入备用块210。然后，RAM表18就提 供指向数据306的指针，以前存储在块202的数据306则被写入备用块 210。标题220正确地表示新近存储的、属于存储在备用块210中的连续文 件的信息。于是，备用块210就被保留用来既存储原始文件片断，又存储 连续文件中的修改后的文件片断或者执行回收/折叠算法时的文件片断。

在正常运行时，处理器14中所执行的应用程序写入各个存储器块202、 204、206、208和210的许多不同存储器区域。这许多数据块中的每一快都 包括相关的块标题。当回收/折叠算法被执行时，存储器空间被释放，块标 题的数目减少。于是，随着较小的存储器空间被优化成为较大的存储器空 间，标题的数目也类似地减少，分配给块标题的存储器空间就被恢复。所 用RAM空间的这种下降会使自由空间量增加，这会使编辑更加容易、使系 统的读/写更快。

回收/折叠算法通常是较慢的运算。为了改善处理器14的性能，回收/ 折叠算法包括能够以前台方式和后台方式执行的运算，当然，本发明并不 要求这一点。在前台方式中，存储器空间被释放，从而允许在块202、204、 206、208和210中新写入数据。在后台方式中，存储器空间被优化，从而 提供使RAM表18的使用得到优化的较大存储器空间。于是，该回收/折叠 算法可以被用来提高支持片断文件存储的可编辑文件系统的性能。如图2 和图3所示，每个存储器块的一个标题可以被用来为所有文件片断存储PLR 信息。每个存储器块采用一个标题，那么由于PLR信息不是对每个文件片 断被跟踪，而是只在文件层次上被跟踪，所以将文件写到非易失性存储器 24的时间就会减少。

无线设备10的性能提高也是因为执行回收/折叠算法后该片断文件系 统中的文件部分数量较少的原因。文件部分数量较少可以加速文件系统的 编辑。在运行回收/折叠算法时，文件系统内的空白数据块就被合并到一起 而形成较大的块，从而减少了存储系统的片断。无线设备10的性能之所以 提高，也是由于RAM表18只对用来为存储器数据定址的表(动态链接表) 中的较少文件进行跟踪的结果。

至此应当明白，本发明可以允许在片断文件系统中存储文件的处理设备 更容易编辑该文件系统。原始文件被存储在存储器中，数据编辑被存储在 新存储器位置。数据编辑作为标题结构中的文件偏移加以跟踪，指针在RAM 中作为直接指针加以跟踪。在该算法中，存储器区域按照3个不同类型的 区域进行统计：自由存储器区域(图3的备用块210)、脏存储器区域和可 折叠存储器区域(图3的可折叠数据304)。新的回收/折叠算法将数据折 叠回到已编辑文件偏移。于是，新的回收/折叠算法就能够使文件中该编辑 区域附近的存储器区域变得可用。

尽管本文已经描述和说明了本发明的一些特点，但对熟悉该技术的人员 而言，可以设想出许多修改、替代、改变和等效的实施例。所以应当理解， 所附权利要求的目的是要覆盖那些符合本发明的真正精神的所有这些修改 和变化。