一种降低混合映射算法中映射表内存资源占用的方法

摘要

本发明公开了一种降低混合映射算法中映射表内存资源占用的方法。本发明针对现有技术存在的问题，提供了一种降低内存资源消耗的方法，可以降低混合映射算法中映射表内存资源占用，对与系统内存资源较为宝贵的嵌入式的片上系统具有实际意义。所述方法预先定义对应于NAND Flash的数据结构CPMT[N]及数据结构LatestW[M]，存储项字节数分别为X、Y,上述两个数据结构均存储在内存中；N、M、X、Y为预先定义好的整数；所述CPMT[N]用于记录物理块内物理页逻辑地址到物理地址的映射信息，LatestW[M]用于记录NAND Flash所有物理块最后一次被写的物理页页号信息。NAND Flash每个物理页的存储空间分成两个部分，一部分用于存储用户数据，一部分用于存储CPMT[N],每个物理块最后一次写入的物理页上的CPMT[N]保存该物理块最新的物理页映射信息。

说明书

技术领域

本发明涉及NAND Flash存储器存储数据领域，尤其是涉及降低混合映射算法中映射表内存资源占用的方法。本发明针对现有技术存在的问题，提供了一种降低混合映射算法中映射表内存资源占用的方法，可以降低基于页映射的日志块映射表的缓存占用，对与系统内存资源较为宝贵的嵌入式的片上系统具有实际意义。

背景技术

半导体行业的蓬勃发展，出现了高性能的存储器NAND Flash，NAND Flash存储器使用半导体作为存储介质，具有高速，低能耗和防震等优点，但NAND Flash存储器本身也存在一些不足。首先，它的存储块的擦除次数是有限的；其次，NAND Flash必须要擦除之后才能重新写入，导致写入性能较低。因此，磨损均衡显得尤为重要，好的磨损均衡管理方法不但能够提高NAND Flash性能和效率，还能够大大的延长NAND Flash的使用寿命。基于此，出现了专门为NAND Flash存储器所使用的文件系统，如JFFS、JFFS2、YAFFS、TrueFFS等，这些NAND Flash专用的文件系统进行存储管理为NAND Flash设备提供专门的驱动和更好的数据管理。但是对于一个小型的SoC，由于资源的限制，想采用以上的文件系统对NAND Flash进行管理不太现实，所以亟需一个轻量级的管理方法，能够在有限资源的条件下，满足对NAND Flash的磨损均衡控制。目前对于小型的系统，常采用的管理方法为FTL(Flash Translation Layer)。

典型的FTL管理机制采用以页为单位进行存储管理的方式，如图1所示，将物理页地址与逻辑页地址来进行一一对应，读、写操作都是按页进行，数据存储时存储在空白的页面存储区中，数据写入完成后需更新地址映射表中的转换信息。这种管理算法比较直接，但是由于采用的页映射机制，对于容量小、页数少的存储器，是极为方便的一种方法。但是，对于大容量NAND Flash来说，就显得比较吃力，例如，对于美光公司的MT29F32G08CBACA这个型号的NAND Flash来说，共有4096个物理块，每块有256页，基于页映射共需要4096*256*4 = 4MB的内存空间来保存当前的映射表，对于片上系统来说内存消耗过大。

为了解决这个问题，提出了混合映射（Hybrid mapping）算法，它是基于块和页的混合映射的机制，如图2所示，在该算法中，将NAND Flash在逻辑上分为数据块和日志块两个部分，日志块是有多个空闲块组成。同时，在内存中存储着两个表：基于块映射的数据块地址映射表DBMT和基于页映射的日志块页映射表LPMT。根据混合映射算法，以MT29F32G08CBACA型号的NAND Flash为例，物理结构如图3，DBMT块映射表映射粒度为块，MT29F32G08CBACA共有4096个块，则DBMT存储的数值范围为0~0x1000，用2个字节就可以表示出完整的信息，LPMT页映射表映射粒度为页，MT29F32G08CBACA共有4096*256个块,数值范围为0~0x100000，需要4个字节才可以表示出完整的信息，需要消耗的内存如下：4096*2+ (TBN-X)*256*4，其中(TBN-X)为分配的日志块个数，可以看出，该算法所消耗的内存与日志块个数(TBN-X)有关，若(TBN-X)为128，则需要消耗内存为：4096*2+ 128*256*4 = 136KB。相对于基于页映射的算法，该算法内存消耗已经大大降低，但是经过分析发现，内存消耗主要部分为日志映射表LPMT，并且内存消耗与(TBN-X)相关，成倍数增长。

发明内容

为解决上述问题，本发明提供了一种降低内存资源占用的方法，包括如下步骤：

步骤一：预先定义对应于NAND Flash的数据结构CPMT[N]及数据结构LatestW[M]，存储项字节数分别为X、Y, 上述两个数据结构均存储在内存中；N、M、X、Y为预先定义好的整数；所述CPMT[N]用于记录物理块内物理页逻辑地址到物理地址的映射信息。LatestW[M]用于记录NAND Flash所有物理块最后一次被写的物理页页号信息。

步骤二：将NAND Flash每个物理页的存储空间分成两个部分，一部分用于存储用户数据，一部分用于存储CPMT[N],每个物理块最后一次写入的物理页上的CPMT[N]保存该物理块最新的物理页映射信息。

步骤三：对NAND Flash进行读，包括如下步骤：

步骤3.1 获取用户数据。

步骤3.2 根据主机下发的逻辑地址计算对应物理块的块号Block_Num。

步骤3.3 根据该Block_Num查询LatestW[M]数据结构，得到该物理块的最后一次写入的数据页号LatestW_Page_Num。

步骤3.3 读取LatestW_Page_Num页号数据，获得CPMT[N] ，分配新的物理页，页号为LatestW_Page_Num+1。

步骤3.5 更新LatestW[M]数据结构，记录最后操作的物理页的页号，更新CPMT[N]数据结构，记录最新的逻辑地址到物理地址映射信息。

步骤3.6 向新的物理页写入用户数据，同时写入的CPMT[N]数据结构到该物理页中。

优选的，还包括读操作流程，包括如下步骤：

步骤1：根据主机下发的逻辑地址计算对应物理块的块号Block_Num。

步骤2：根据Block_Num查询LatestW[M]数据结构，得到该物理块的最后一次写入的数据页号LatestW_Page_Num。

步骤3：读取LatestW_Page_Num页号数据，获取最新的CPMT[N]。

步骤4：根据CPMT[N]获取主机下发的逻辑地址对应的实际物理页的物理地址Page_Addr；

步骤5：读取Page_Addr对应物理页，得到主机所需的数据。

进一步的，N等于物理页页数。

进一步的，M等于物理块块数。

进一步的，CPMT[N] 的存储项字节数为4。

进一步的，LatestW[M] 的存储项字节数为4。

进一步的，NAND Flash物理页内用于存储用户数据的空间大小为该物理页的总存储字节数减去N*4的差值。

本发明的有益效果为：

本发明提出了一种资源消耗小的算法，可广泛应用于资源有限的片上SoC中，提升系统写入数据的性能。

采用本发明，成本无需增加就能取得很好的技术效果，具有广泛的应用前景。

附图说明

图1 基于页映射的映射表示意图；

图2 基于混合映射的映射表示意图；

图3 NAND Flash结构示意图；

图4 用户数据与CMPT数据结构存储示意图；

图5 数据写入流程图；

图6 数据读取流程图。

具体实施方式

在执行本方法前，需要预先确定NAND Flash，用B代表NAND Flash具有的物理块数量，用P代表每个物理块中有具有的物理页数量，B、P均为整数。

下面对本发明进行步骤性说明。

步骤一：预先定义对应于NAND Flash的数据结构CPMT[N]及数据结构LatestW[M]，存储项字节数分别为X、Y，上述两个数据结构均存储在内存中。N、M、X、Y为预先定义好的整数。所述CPMT[N]用于记录物理块内物理页逻辑地址到物理地址的映射信息，LatestW[M]用于记录NAND Flash所有物理块最后一次被写的物理页页号信息。

X、Y为预先定义好的整数。其中N大小与NAND Flash介质相关，若一片NAND Flash有B个物理块，每个物理块中有P个物理页，则为了保存该物理块的映射表信息，则需要P个表项，即N为P， M为B。应该理解，N为P，M为B的设计不会浪费存储空间，并使得各个物理块及物理页信息都得到存储。

在本发明中采用将用户数据与CPMT[N]同步更新的方式保证每个NAND Flash物理块中最后一次被写的物理页中保存着该物理块的最新CPMT[N]信息。

步骤二：将NAND Flash每个物理页的存储空间分成两个部分，一部分用于存储用户数据，一部分用于存储CPMT[N]。（如图4所示）。

设NAND Flash一个物理页大小为D_page字节,>user=D_page–>

步骤三：对NAND Flash进行写操作，如图5所示，包括如下步骤：

步骤3.1 获取用户数据。

步骤3.2 根据主机下发的逻辑地址计算对应物理块的块号Block_Num。

步骤3.3 根据该Block_Num查询LatestW[M]数据结构，得到该物理块的最后一次写入的数据页号LatestW_Page_Num。

步骤3.4 读取LatestW_Page_Num页号数据，获得CPMT[N] ，分配新的物理页，页号为LatestW_Page_Num+1。

步骤3.5 更新LatestW[M]数据结构，记录最后操作的页号，更新CPMT[N]数据结构，记录最新的逻辑页到物理页映射信息。

步骤3.6 向新的物理页写入用户数据，同时写入的CPMT[N]数据结构到该物理页中。

当然，还可以对NAND Flash进行读操作时，如图6所示，包括如下步骤：

步骤1：根据主机下发的逻辑地址计算对应物理块的块号Block_Num。

步骤2：根据Block_Num查询LatestW[M]数据结构，得到该物理块的最后一次写入的数据页号LatestW_Page_Num。

步骤3：读取LatestW_Page_Num页号数据，获取最新的CPMT[N]。

步骤4：根据CPMT[N]获取主机下发的逻辑地址对应的实际物理地址Page_Addr。

步骤5：读取Page_Addr数据，得到主机所需的数据。

下面举例说明利用本发明所述方法后资源情况：

选用美光公司MT29F32G08CBACA型NAND Flash作为试验对象，物理结构如图3所示。该NAND Flash有4096个物理块，每个块有256个物理页，每个物理页大小有4096字节存储空间，则用于记录页映射表的数据结构为CPMT[256]，存储字节数为4字节，共占用空间为1K字节；用于记录每个物理块最后一次编程的页页号信息的数据结构为LatestW[4096]，存储字节数为4字节，共占用空间为16K字节；所以该算法一共占用16+1 = 17K字节，远远小于采用页映射算法所需的4M字节以及采用通用混合映射算法所需的136K字节，并且该算法占用空间恒定，与其他参数无关，对小型的SoC上实现NAND Flash管理算法具有很重要的实际意义。