一种映射表的重建方法及数据存储设备

摘要

本发明公开了一种映射表的重建方法及数据存储设备，属于存储技术领域。所述映射表的重建方法包括以下步骤：在控制器中配置第一缓存和第二缓存，且第一缓存存储重建时的逻辑地址到物理地址映射表，第二缓存存储重建时的物理地址到逻辑地址映射表；重建逻辑地址到物理地址映射表，并输出闪存块和参与逻辑地址到物理地址映射表重建的最后一个区块的下一个区块；依据重建逻辑地址到物理地址映射表后输出的闪存块和区块，进行物理地址到逻辑地址映射表的重建；以及保留存储有重建后的映射表的部分第一缓存和部分第二缓存，释放其他第一缓存和第二缓存。通过本发明提供的一种映射表的重建方法，可提高映射表重建的效率。

权利要求

1.一种映射表的重建方法，其特征在于，至少包括以下步骤：

在控制器中配置第一缓存和第二缓存，且所述第一缓存存储重建时的逻辑地址到物理地址映射表，所述第二缓存存储重建时的物理地址到逻辑地址映射表；

重建所述逻辑地址到物理地址映射表，并输出闪存块和参与逻辑地址到物理地址映射表重建的最后一个区块的下一个区块；

依据重建的所述逻辑地址到物理地址映射表后输出的闪存块和区块，进行物理地址到逻辑地址映射表的重建；以及保留存储有重建后的所述逻辑地址到物理地址映射表和所述物理地址到逻辑地址映射表的部分第一缓存和部分第二缓存，释放其他第一缓存和第二缓存；

其中，在重建逻辑地址到物理地址映射表时，包括以下步骤：

判断缓存中操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息是否为有效值；判断缓存中操作类型为更新的物理地址到逻辑地址资料结构中的闪存块信息是否为有效值；

且当操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息为无效值，且操作类型为更新的物理地址到逻辑地址资料结构中的闪存块信息为有效值时；

读取操作类型为更新的物理地址到逻辑地址资料结构中闪存块中对应区块的物理地址到逻辑地址映射表，并以读取的物理地址到逻辑地址映射表覆盖缓存中操作类型为刷回的物理地址到逻辑地址映射表，并以读取的物理地址到逻辑地址映射表对应的闪存块信息与区块信息初始化到缓存中操作类型为刷回的物理地址到逻辑地址资料结构中；以及将缓存中物理地址到逻辑地址映射表中所有条目的刷回标志位清除。

2.根据权利要求1所述的映射表的重建方法，其特征在于，在重建逻辑地址到物理地址映射表时，包括以下步骤：在系统闪存区中读取逻辑地址到物理地址记录表，以获取各逻辑地址到物理地址映射表的物理地址；以及在系统闪存中读取物理地址到逻辑地址映射表以及对应的物理地址到逻辑地址资料结构。

3.根据权利要求1所述的映射表的重建方法，其特征在于，在重建逻辑地址到物理地址映射表时，包括以下步骤：当操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息为无效值，且操作类型为更新的物理地址到逻辑地址资料结构中的闪存块信息为无效值时，无需重建所述逻辑地址到物理地址映射表。

4.根据权利要求1所述的映射表的重建方法，其特征在于，在重建逻辑地址到物理地址映射表时，包括以下步骤：当操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息为有效值，读取数据闪存区中该闪存块其余区块中所有的物理地址到逻辑地址映射表，并在缓存中依序放置在操作类型为刷回的物理地址到逻辑地址映射表之后，将操作类型为刷回的物理地址到逻辑地址映射表及其后的物理地址到逻辑地址映射表标识为待刷回状态。

5.根据权利要求4所述的映射表的重建方法，其特征在于，在重建逻辑地址到物理地址映射表时，还包括以下步骤：判断缓存中所有待刷回的物理地址到逻辑地址映射表对应的内容是否为空，若为空，则表示逻辑地址到物理地址映射表重建完成，输出最后的闪存块及区块，若不为空，则将操作类型为刷回的物理地址到逻辑地址映射表及后所有的物理地址到逻辑地址映射表中所有条目的刷回标志位清除；

并在待刷回的物理地址到逻辑地址映射表中，将其中闪存块信息及区块信息与操作类型为更新的物理地址到逻辑地址表相同的，标记刷回标志位；以及同步进行缓存中所有物理地址到逻辑地址映射表的刷回。

6.根据权利要求5所述的映射表的重建方法，其特征在于，将物理地址到逻辑地址映射表中所有条目的刷回标志位清除包括以下步骤：在缓存设值单元中设置位掩码，以清除所有的刷回标志位；

将缓存设值单元中预设值设置为零；

将缓存设值单元中的地址长度设置为需要清除的所有的刷回标志位范围；以及启动缓存设值单元，清除所需范围中所有条目的刷回标志位。

7.根据权利要求1所述的映射表的重建方法，其特征在于，将待刷回的物理地址到逻辑地址映射表标记刷回标志位包括以下步骤：在缓存搜索单元中设置位掩码，且该位掩码比对刷回标志位；

在缓存搜索单元中设置搜索值，且搜索值为刷回标志位；

启动缓存搜索单元，在操作类型为更新的物理地址到逻辑地址映射表中找出所有标记有刷回标志位的条目；

依据搜索结果获取地址区块表；以及

依照地址区块表在目标物理地址到逻辑地址映射表对应条目中标记刷回标志位。

8.根据权利要求1所述的映射表的重建方法，其特征在于，同步进行缓存中所有物理地址到逻辑地址映射表的刷回包括以下步骤：判断物理地址到逻辑地址映射表索引对应的物理地址到逻辑地址条目是否标记为刷回标志位；

读取该物理地址到逻辑地址条目的逻辑地址到物理地址映射表并保存在第一缓存中；

使用缓存搜索单元在所有待刷回的物理地址到逻辑地址映射表中搜索属于该逻辑地址到物理地址映射表的其余条目；

将所有属于此逻辑地址到物理地址映射表的物理地址到逻辑地址条目刷回此逻辑地址到物理地址映射表，并将刷回的物理地址到逻辑地址条目标记刷回标志位。

9.根据权利要求8所述的映射表的重建方法，其特征在于，使用缓存搜索单元在所有待刷回的物理地址到逻辑地址映射表中搜索属于该逻辑地址到物理地址映射表的其余条目包括以下步骤：在缓存搜索单元中预搜索的数据设定为物理地址到逻辑地址条目；

在缓存搜索单元中设置位掩码，仅显示逻辑地址到物理地址映射表的位置信息；以及启动缓存搜索单元，并存储搜索结果。

10.根据权利要求1所述的映射表的重建方法，其特征在于，在重建物理地址到逻辑地址映射表时，包括以下步骤：获取重建的逻辑地址到物理地址映射表输出的闪存块信息和区块信息；以及判断闪存块信息对应的闪存块是否有效，并判断区块是否超出总区块数。

11.根据权利要求10所述的映射表的重建方法，其特征在于，在重建物理地址到逻辑地址映射表时，包括以下步骤：当闪存块信息对应的闪存块无效，或闪存块信息对应的闪存块有效且区块超出总区块数；

则重设物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构为无资料状态，并完成物理地址到逻辑地址映射表的重建。

12.根据权利要求10所述的映射表的重建方法，其特征在于，在重建物理地址到逻辑地址映射表时，当闪存块信息对应的闪存块有效且区块未超出总区块数，所述方法还包括以下步骤：判断闪存块信息与区块信息是否与操作类型为更新的物理地址到逻辑地址资料结构相同，若相同，则读取数据闪存区中物理地址到逻辑地址映射表索引对应的页，以页的元数据中的逻辑地址更新物理地址到逻辑地址映射表，索引持续向前，直到读到空页或映射表末端；若不同，则重设物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构为无资料状态，并以闪存块信息和区块信息初始化物理地址到逻辑地址资料结构，并读取数据闪存区中物理地址到逻辑地址映射表索引对应的页，以页的元数据中的逻辑地址更新物理地址到逻辑地址映射表，索引持续向前，直到读到空页或映射表末端。

13.一种数据存储设备，其特征在于，所述数据存储设备上存储有计算机程序，所述计算机程序被处理器执行时实现如权利要求1所述的映射表的重建方法。

说明书

一种映射表的重建方法及数据存储设备

技术领域

[0001] 本发明属于存储技术领域，特别涉及一种映射表的重建方法及数据存储设备。

背景技术

[0002] 存储装置在运行时，为了能效考量，会将部分或全部的映射表从非易失性存储器读取，暂存于易失性存储器上。随着存储装置持续运行，执行主机端下发的命令或内部的命令，映射表会发生更新，使得暂存于易失性存储器上的映射表的内容与非易失性存储器中映射表的内容不同。若发生异常掉电，映射表内容可能丢失。在掉电后存储的过程中，会因为映射表内容的缺失，写入和读取时发生异常。

发明内容

[0003] 本发明的目的在于提供一种映射表的重建方法及数据存储设备，解决异常掉电时，映射表出现缺失的问题。

[0004] 为解决上述技术问题，本发明是通过以下技术方案实现的：

[0005] 本发明提供一种映射表的重建方法，至少包括以下步骤：

[0006] 在控制器中配置第一缓存和第二缓存，且所述第一缓存存储重建时的逻辑地址到物理地址映射表，所述第二缓存存储重建时的物理地址到逻辑地址映射表；

[0007] 重建所述逻辑地址到物理地址映射表，并输出闪存块和参与逻辑地址到物理地址映射表重建的最后一个区块的下一个区块；

[0008] 依据重建的所述逻辑地址到物理地址映射表后输出的闪存块和区块，进行物理地址到逻辑地址映射表的重建；以及

[0009] 保留存储有重建后的所述逻辑地址到物理地址映射表和所述物理地址到逻辑地址映射表的部分第一缓存和部分第二缓存，释放其他第一缓存和第二缓存。

[0010] 在本发明一实施例中，在重建逻辑地址到物理地址映射表时，包括以下步骤：

[0011] 在系统闪存区中读取逻辑地址到物理地址记录表，以获取各逻辑地址到物理地址映射表的物理地址；以及

[0012] 在系统闪存中读取物理地址到逻辑地址映射表以及对应的物理地址到逻辑地址资料结构。

[0013] 在本发明一实施例中，在重建逻辑地址到物理地址映射表时，包括以下步骤：

[0014] 判断缓存中操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息是否为有效值；以及

[0015] 判断缓存中操作类型为更新的物理地址到逻辑地址资料结构中的闪存块信息是否为有效值。

[0016] 在本发明一实施例中，在重建逻辑地址到物理地址映射表时，包括以下步骤：

[0017] 当操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息为无效值，且操作类型为更新的物理地址到逻辑地址资料结构中的闪存块信息为无效值时，无需重建所述逻辑地址到物理地址映射表。

[0018] 在本发明一实施例中，在重建逻辑地址到物理地址映射表时，包括以下步骤：

[0019] 当操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息为无效值，且操作类型为更新的物理地址到逻辑地址资料结构中的闪存块信息为有效值时；

[0020] 读取操作类型为更新的物理地址到逻辑地址资料结构中闪存块中对应区块的物理地址到逻辑地址映射表，并以读取的物理地址到逻辑地址映射表覆盖缓存中操作类型为刷回的物理地址到逻辑地址映射表，并以读取的物理地址到逻辑地址映射表对应的闪存块信息与区块信息初始化到缓存中操作类型为刷回的物理地址到逻辑地址资料结构中；以及[0021] 将缓存中物理地址到逻辑地址映射表中所有条目的刷回标志位清除。

[0022] 在本发明一实施例中，在重建逻辑地址到物理地址映射表时，包括以下步骤：

[0023] 当操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息为有效值，读取数据闪存区中该闪存块其余区块中所有的物理地址到逻辑地址映射表，并在缓存中依序放置在操作类型为刷回的物理地址到逻辑地址映射表之后，将操作类型为刷回的物理地址到逻辑地址映射表及其后的物理地址到逻辑地址映射表标识为待刷回状态。

[0024] 在本发明一实施例中，在重建逻辑地址到物理地址映射表时，还包括以下步骤：

[0025] 判断缓存中所有待刷回的物理地址到逻辑地址映射表对应的内容是否为空，若为空，则表示逻辑地址到物理地址映射表重建完成，输出最后的闪存块及区块，若不为空，则将操作类型为刷回的物理地址到逻辑地址映射表及后所有的物理地址到逻辑地址映射表中所有条目的刷回标志位清除；

[0026] 并将在待刷回的物理地址到逻辑地址映射表中，将其中闪存块信息及区块信息与操作类型为更新的物理地址到逻辑地址表相同的，标记刷回标志位；以及

[0027] 同步进行缓存中所有物理地址到逻辑地址映射表的刷回。

[0028] 在本发明一实施例中，将物理地址到逻辑地址映射表中所有条目的刷回标志位清除包括以下步骤：

[0029] 在缓存设值单元中设置位掩码，以清除所有的刷回标志位；

[0030] 将缓存设值单元中预设值设置为零；

[0031] 将缓存设值单元中的地址长度设置为需要清除的所有的刷回标志位范围；以及[0032] 启动缓存设值单元，清除所需范围中所有条目的刷回标志位。

[0033] 在本发明一实施例中，将操作类型为待刷回的物理地址到逻辑地址映射表标记刷回标志位包括以下步骤：

[0034] 在缓存搜索单元中设置位掩码，且该位掩码比对刷回标志位；

[0035] 在缓存搜索单元中设置搜索值，且搜索值为刷回标志位；

[0036] 启动缓存搜索单元，在操作类型为更新的物理地址到逻辑地址映射表中找出所有标记有刷回标志位的条目；

[0037] 依据搜索结果获取地址区块表；以及

[0038] 依照地址区块表在目标物理地址到逻辑地址映射表对应条目中标记刷回标志位。

[0039] 在本发明一实施例中，同步进行缓存中所有物理地址到逻辑地址映射表的刷回包括以下步骤：

[0040] 判断物理地址到逻辑地址映射表索引对应的物理地址到逻辑地址条目是否标记为刷回标志位；

[0041] 读取该物理地址到逻辑地址条目的逻辑地址到物理地址映射表并保存在第一缓存中；

[0042] 使用缓存搜索单元在所有待刷回的物理地址到逻辑地址映射表中搜索属于该逻辑地址到物理地址映射表的其余条目；

[0043] 将所有属于此逻辑地址到物理地址映射表的物理地址到逻辑地址条目刷回此逻辑地址到物理地址映射表，并将刷回的物理地址到逻辑地址条目标记刷回标志位。

[0044] 在本发明一实施例中，使用缓存搜索单元在所有待刷回的物理地址到逻辑地址映射表中搜索属于该逻辑地址到物理地址映射表的其余条目包括以下步骤：

[0045] 在缓存搜索单元中预搜索的数据设定为物理地址到逻辑地址条目；

[0046] 在缓存搜索单元中设置位掩码，仅显示逻辑地址到物理地址映射表的位置信息；以及

[0047] 启动缓存搜索单元，并存储搜索结果。

[0048] 在本发明一实施例中，在重建物理地址到逻辑地址映射表时，包括以下步骤：

[0049] 获取重建的逻辑地址到物理地址映射表输出的闪存块信息和区块信息；以及[0050] 判断闪存块信息对应的闪存块是否有效，并判断区块是否超出总区块数。

[0051] 在本发明一实施例中，在重建物理地址到逻辑地址映射表时，包括以下步骤：

[0052] 当闪存块信息对应的闪存块无效，或闪存块信息对应的闪存块有效且区块超出总区块数；

[0053] 则重设物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构为无资料状态，并完成物理地址到逻辑地址映射表的重建。

[0054] 在本发明一实施例中，在重建物理地址到逻辑地址映射表时，当闪存块信息对应的闪存块有效且区块未超出总区块数，所述方法还包括以下步骤：

[0055] 判断闪存块信息与区块信息是否与操作类型为更新的物理地址到逻辑地址资料结构相同，若相同，则读取数据闪存区中物理地址到逻辑地址映射表索引对应的页，以页的元数据中的逻辑地址更新物理地址到逻辑地址映射表，索引持续向前，直到读到空页或映射表末端；若不同，则重设物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构为无资料状态，并以闪存块信息和区块信息初始化物理地址到逻辑地址资料结构，并读取数据闪存区中物理地址到逻辑地址映射表索引对应的页，以页的元数据中的逻辑地址更新物理地址到逻辑地址映射表，索引持续向前，直到读到空页或映射表末端。

[0056] 本发明还提供一种数据存储设备，所述数据存储设备上存储有计算机程序，所述计算机程序被处理器执行时实现如上所述的映射表的重建方法。

[0057] 如上所述本发明提供的一种映射表的重建方法及数据存储设备，在映射表重建时期，将控制器中配置第一缓存和第二缓存，供映表重建使用，在映射表重建完成后释放大部分第一缓存和第二缓存供读取和写入使用，加快映射表的重建效率。在逻辑地址到物理地址映射表重建时，将闪存块中所有区块中的物理地址到逻辑地址映射表读出，并同步进行所有物理地址到逻辑地址映射表的刷回，再次加快映射表重建的速率。在物理地址到逻辑地址映射表的条目中配置有刷回标志位，以辨别已刷回的条目，避免重复刷回，较少闪存块的损耗。且缓存搜索单元可快速定位已刷回的物理地址到逻辑地址映射表条目，避免重复刷回，加快映射表的重建。同时缓存设值单元可快速清除所有条目的刷回标志位，利于物理地址到逻辑地址映射表条目的刷回，加快映射表的重建。本发明提供的映射表的重建方法，能够重建映射表，并大大加快映射表的重建效率。

[0058] 当然，实施本发明的任一产品并不一定需要同时达到以上所述的所有优点。

附图说明

[0059] 为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0060] 图1为本申请中一种数据存储设备结构图。

[0061] 图2为本申请中物理地址到逻辑地址映射表的结构图。

[0062] 图3为本申请中物理地址到逻辑地址资料结构图，以及物理地址到逻辑地址资料结构与物理地址到逻辑地址映射表关系图。

[0063] 图4为本申请中操作类型为刷回的物理地址到逻辑地址映射表向后配置的物理地址到逻辑地址映射表结构图。

[0064] 图5为本申请中缓存搜索单元搜索需要刷回的物理地址到逻辑地址映射表的条目的示意图。

[0065] 图6为本申请中缓存搜索单元搜索快速定位所有标记有刷回标志位的物理地址到逻辑地址映射表的条目的示意图。

[0066] 图7为本申请中缓存设值单元清除物理地址到逻辑地址映射表的条目的所有标记有刷回标志位的示意图。

[0067] 图8为本申请中一种映射表的重建方法流程图。

[0068] 图9为本申请中一种逻辑地址到物理地址映射表的重建流程图。

[0069] 图10为本申请中将缓存中物理地址到逻辑地址映射表中所有条目的刷回标志位清除的流程图。

[0070] 图11为本申请中图将操作类型为待刷回的物理地址到逻辑地址映射表标记刷回标志位的流程图。

[0071] 图12为本申请中同步进行缓存中所有物理地址到逻辑地址映射表的刷回的流程图。

[0072] 图13为本申请中使用缓存搜索单元在所有待刷回的物理地址到逻辑地址映射表中搜索属于该逻辑地址到物理地址映射表的其余条目的流程图。

[0073] 图14为本申请中在缓存中进行物理地址到逻辑地址映射表的重建的流程图。

具体实施方式

[0074] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。

[0075] 请参阅图1所示，数据存储设备100经由接口及电源线与主机200(例如信息处理装置)连接。主机200例如由个人计算机、CPU核或者与网络连接的服务器等构成。主机200对数据存储设备100执行数据存取控制，例如，通过向数据存储设备100发送写请求、读请求及删除请求，对数据存储设备100执行数据的写入、读取及删除。

[0076] 请参阅图1所示，在本发明一实施例中，数据存储设备100例如可以固态硬盘(Solid State Disk，SSD)。且数据存储设备100可以包括控制器110和非易失性存储单元120。非易失性存储单元120是即使切断电源也不会丢失数据的非易失性存储单元120(非暂时的存储器)，非易失性存储单元120可以为NAND闪存、垂直NAND(VNAND)、NOR闪存、电阻随机存取存储器(RRAM)、相变存储器(PRAM)、磁阻随机存取存储器(MRAM)、铁电随机存取存储器(FRAM)或自旋转移力矩随机存取存储器(STT‑RAM)。非易失性存储单元120可以包括连接到字线、串选择线、地选择线和位线的存储单元阵区块。非易失性存储单元120可以包括包含多个存储块的超级块。多个存储块可以包括多个页面。非易失性存储单元120可以包括二维(2D)存储器阵区块或三维(3D)存储器阵区块。也可以使用其他类型的非易失性存储单元
120。本实施例中，以NAND型闪速存储器的结构为例进行说明，可以理解，在其他的实施例中，也可以采用其他类型的非易失性存储单元120结构。

[0077] 请参阅图1所示，在本发明一实施例中，非易失性存储单元120电性连接至存储器控制器202，并且用以储存主机200所写入的数据。非易失性存储单元120中具有闪存块。闪存块可属于同一个存储器晶粒（die）或者属于不同的存储器晶粒。每一闪存块分别具有多个物理页面，并且每一物理页面具有至少一物理扇区，其中属于同一个闪存块的物理页面可被独立地写入且被同时地抹除。例如，每一闪存块是由128个物理页面所组成，并且每一物理页面具有8个物理扇区（sector）。也就是说，在每一物理扇区为512字节（byte）的例子中，每一物理页面的容量为4千字节（Kilobyte，K）。然而，在一实施例中，每一闪存块是可由64个物理页面、256个物理页面或其它任意个物理页面所组成。

[0078] 请参阅图2所示，闪存块（block）为抹除的最小单位。亦即，每一闪存块含有最小数目的一并被抹除的存储单元。物理页面为可编程的最小单元。即，物理页面为写入数据的最小单元。然而，在一些实施例中，写入数据的最小单位亦可以是物理扇区或其它大小。每一物理页面通常包括数据位区与冗余位区。数据位区用以储存使用者的数据，而冗余位区用以储存系统的数据（例如，错误检查与校正码）。

[0079] 请参阅图1所示，在本发明一实施例中，非易失性存储单元120为多层存储单元（Multi Level Cell，MLC）NAND闪存模块。在其他实施例中，非易失性存储单元120亦可是单层存储单元（Single Level Cell，SLC）NAND闪存模块、其它闪存模块或其它具有相同特性的存储器模块。

[0080] 请参阅图1所示，在本发明一实施例中，在非易失性存储单元120中配置有系统闪存区（system block）121、逻辑地址到物理地址闪存区（L2P block）122、数据闪存区（data block）123以及其他闪存区124。

[0081] 请参阅图1所示，在本发明一实施例中，在逻辑地址到物理地址闪存区122中存放有逻辑地址到物理地址（L2P）映射表，每个逻辑地址到物理地址映射表中存储有每条逻辑地址对应的物理地址。

[0082] 请参阅图1所示，在本发明一实施例中，在数据闪存区123中存放有用户资料。每个数据闪存区123中的闪存块可以划分为多个区块（bank），在每一区块的最后存放有物理地址到逻辑地址映射表，每个物理地址到逻辑地址映射表中记录着一区块（bank）中每一4K物理页面的逻辑地址。物理地址到逻辑地址映射表如图2所示，每个物理地址到逻辑地址映射表中包括多个条目，每个条目包括一个逻辑地址和一个刷回标志位（flush bit）。其中，刷回标志位用于判断对应条目的逻辑地址是否被刷回到逻辑地址到物理地址映射表中，可协助映射表的重建。例如当刷回标志位为1时，表示存在刷回标志位，且该条目对应的逻辑地址已经被刷回到逻辑地址到物理地址映射表，当刷回标志位为零时，表示不存在刷回标志位，且该条目对应的逻辑地址未被刷回到逻辑地址到物理地址映射表中。

[0083] 请参阅图1所示，在一些实施例中，在每4K物理页面中附件一个元数据（meta data），元数据包含此4K的逻辑地址。

[0084] 请参阅图1所示，在本发明一实施例中，在系统闪存区121中有备份的物理地址到逻辑地址映射表，物理地址到逻辑地址资料结构和逻辑地址到物理地址记录表及其他必要数据。其中，物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构一一对应，物理地址到逻辑地址资料结构记录着物理地址到逻辑地址映射表的状态。每个物理地址到逻辑地址映射表需要刷回到逻辑地址到物理地址映射表中。逻辑地址到物理地址记录表记录着每一个逻辑地址到物理地址映射表的物理地址。其中，逻辑地址到物理地址记录表记录每一个逻辑地址到物理地址映射表的物理地址。当从系统闪存区121中读取逻辑地址到物理地址记录表时候，可以知道各个逻辑地址到物理地址映射表最后一次的回存在逻辑地址到物理地址闪存区122的哪个位置。

[0085] 请参阅图1所示，在本发明一实施例中，在其他闪存区124中存储有数据。

[0086] 请参阅图1所示，在本发明一实施例中，控制器110内配置有缓存111，缓存111可以为能够高速写入或读取数据的存储器的易失性存储器，例如静态随机存取存储器(SRAM)、动态随机存取存储器(DRAM)，锁存器、触发器或寄存器。缓存111中可在映射表重建时，将大部分缓存111配置作为重建映射表使用，当映射表重建完成后，再释放缓存111用读取和写入使用，进而加快映射表重建的速率。

[0087] 请参阅图1所示，在本发明一实施例中，在数据存储设备工作时，缓存111中存储有映射表。所述映射表包括最新的逻辑地址到物理地址映射表，物理地址到逻辑地址映射表，以及物理地址到逻辑地址资料结构。

[0088] 请参阅图1所示，在本发明一实施例中，在缓存111中配置有第一缓存，第一缓存中存放有最新的逻辑地址到物理地址映射表。在缓存111中配置有第二缓存，其中，第二缓存中存放最新的物理地址到逻辑地址映射表，且物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构对应设置。如图3所示，第二缓存中包括更新和刷回两种类型的物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构。每个物理地址到逻辑地址资料结构中包括物理地址到逻辑地址映射表指针、区块（bank）信息、闪存块（block）信息、物理地址到逻辑地址映射表索引以及操作类型（op）。其中，物理地址到逻辑地址映射表指针指向对应的物理地址到逻辑地址映射表，区块信息和闪存块信息分别表示对应的物理地址到逻辑地址映射表所属的区块和闪存块，物理地址到逻辑地址映射表索引表示正要操作的物理地址到逻辑地址映射表中的条目的索引，操作类型（op）表示对应的物理地址到逻辑地址映射表处于更新操作状态或者刷回操作状态。

[0089] 请参阅图4所示，在一些实施例中，在映射表重建时，当物理地址到逻辑地址映射表对应的操作类型为刷回时，会在物理地址到逻辑地址映射表后配置足够的第二缓存以容纳所有区块上的物理地址到逻辑地址映射表，以同步进行所有物理地址到逻辑地址映射表的刷回，加快映射表的重建速度。

[0090] 请参阅图1所示，本发明一实施例中，在控制器上还配置有缓存搜索单元112，用于快速搜索缓存111上的数据。在缓存搜索单元112中可设定欲搜索的数值、搜索位址、搜索长度及位掩码。位掩码的设定可在搜索时忽略所指定的位。如图5所示，缓存搜索单元112可用在映射表重建中，当使用刷回的物理地址到逻辑地址映射表更新逻辑地址到物理地址映射表时，可快速找出所有需要刷回到逻辑地址到物理地址映射表的物理地址到逻辑地址的条目，加快映射表重建的速度。如图6所示，缓存搜索单元112还可以用在映射表重建，物理地址到逻辑地址映射表刷回的准备步骤中，缓存搜索单元112可快速定位标记有刷回标志位的已刷回条目，以避免重复刷回，加快映射表重建的速度。

[0091] 请参阅图1和图8所示，本发明一实施例中，在控制器上还配置有缓存设值单元113，用于在缓存111上快速设值。通过缓存设值单元113可以设定预设值、地址、长度及位掩码，位掩码的设定可在设值时跳过所指定的位。在映射表的重建中，在物理地址到逻辑地址映射表刷回的准备步骤中，需要快速清除物理地址到逻辑地址映射表中所有条目的刷回标志位，以加快映射表重建的速度。

[0092] 请参阅1所示，控制器110内还设置有其他单元114，其他单元114例如可以对非易失性存储单元120执行垃圾回收、磨损平衡等功能。

[0093] 请结合图1至图2，并参阅图8所示，本发明提供的数据存储设备100为一种计算机可读存储设备，数据存储设备100上存储有计算机程序，所述计算机程序被处理器执行时实现如本发明所述的映射表的重建方法。本发明提供的映射表的重建方法，包括以下步骤S101至S107。

[0094] S101、初始化缓存。

[0095] S102、在缓存中配置第一缓存，在映射表重建时存储逻辑地址到物理地址映射表。

[0096] S103、在缓存中配置第二缓存，在映射表重建时存储物理地址到逻辑地址映射表。

[0097] S104、进行映射表重建。

[0098] S105、收回部分第一缓存，保留部分第一缓存存储重建后的逻辑地址到物理地址映射表。

[0099] S106、收回部分第二缓存，保留部分第二缓存存储重建后的物理地址到逻辑地址映射表。

[0100] S107、将回收的第一缓存和第二缓存用作数据的读取、写入以及其他功能使用。

[0101] 请参阅图8所示，在本发明一实施例中，在初始化缓存时，设定管理缓存的数据结构。在进行映射表重建前，将控制器中的大部分缓存111配置为第一缓存和第二缓存，用于存储物理地址到逻辑地址映射表和逻辑地址到物理地址映射表，加快映射表的重建速度。在映射表重建之后，释放出除存储重建后的物理地址到逻辑地址映射表和逻辑地址到物理地址映射表外的第一缓存和第二缓存，将大部分缓存111用作存储装置的读取和写入功能，保证存储装置的工作性能。在本申请中，映射表的重建包括逻辑地址到物理地址映射表的重建和物理地址到逻辑地址映射表的重建，且先做逻辑地址到物理地址映射表的重建，再做物理地址到逻辑地址映射表的重建。

[0102] 请参阅图9所示，在本发明一实施例中，在缓存111中进行逻辑地址到物理地址映射表的重建包括步骤S201至步骤S212。

[0103] S201、在系统闪存区中读取逻辑地址到物理地址记录表，以获取各逻辑地址到物理地址映射表的物理地址。

[0104] S202、在系统闪存中读取物理地址到逻辑地址映射表以及对应的物理地址到逻辑地址资料结构。

[0105] S203、判断缓存中操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息是否为有效值，若是，则执行步骤S207，否则，执行步骤S204。

[0106] S204、判断缓存中操作类型为更新的物理地址到逻辑地址资料结构中的闪存块信息是否为有效值，若是，则执行步骤S205，否则，执行步骤S212。

[0107] 在本申请中，物理地址到逻辑地址映射表对应的物理地址到逻辑地址资料结构中的操作类型包括更新状态和刷回状态，处于更新状态的物理地址到逻辑地址映射表比处于刷回状态的物理地址到逻辑地址映射表后更新，而物理地址到逻辑地址映射表在刷回时，会从先更新的物理地址到逻辑地址映射表进行刷回。故在进行重建映射表时，首先判断操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息是否为有效值，若操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息为有效值，则从该物理地址到逻辑地址资料结构对应的物理地址到逻辑地址映射表做刷回。若操作类型为刷回的物理地址到逻辑地址资料结构中的闪存块信息为无效值，则再判断操作类型为更新的物理地址到逻辑地址资料结构中的闪存块信息是否为有效值，若操作类型为更新的物理地址到逻辑地址资料结构中的闪存块信息为有效值，则从该物理地址到逻辑地址资料结构对应的物理地址到逻辑地址映射表做刷回，若操作类型为更新的物理地址到逻辑地址资料结构中的闪存块信息也为无效值，则缓存111中的物理地址到逻辑地址映射表无需进行重建。

[0108] S205、读取操作类型为更新的物理地址到逻辑地址资料结构中闪存块中对应区块的物理地址到逻辑地址映射表，并以读取的物理地址到逻辑地址映射表覆盖缓存中操作类型为刷回的物理地址到逻辑地址映射表，并以读取的物理地址到逻辑地址映射表对应的闪存块信息与区块信息初始化到缓存中操作类型为刷回的物理地址到逻辑地址资料结构中。

[0109] S206、将缓存中物理地址到逻辑地址映射表中所有条目的刷回标志位清除。

[0110] S207、读取数据闪存区中该闪存块其余区块中所有的物理地址到逻辑地址映射表，并在缓存中依序放置在操作类型为刷回的物理地址到逻辑地址映射表之后，将缓存中操作类型为刷回的物理地址到逻辑地址映射表及其后的物理地址到逻辑地址映射表标识为待刷回状态。

[0111] S208、判断缓存中所有待刷回的物理地址到逻辑地址映射表对应的内容是否为空。若是，则执行步骤S212，否则执行步骤S209。

[0112] S209、将操作类型为刷回的物理地址到逻辑地址映射表及其后的所有的物理地址到逻辑地址映射表中所有条目的刷回标志位清除。

[0113] S210、 在待刷回的物理地址到逻辑地址映射表中，将其中闪存块信息及区块信息与操作类型为更新的物理地址到逻辑地址表相同的，标记刷回标志位。其中，标记的条目位置须与操作类型为更新的物理地址到逻辑地址映射表相同。

[0114] 在一些实施例中，如步骤S205至步骤S210所示，在对所有物理地址到逻辑地址映射表进行刷回前，需要将需要刷回的所有物理地址到逻辑地址映射表中所有条目的刷回标志位进行清除，以便于物理地址到逻辑地址映射表的刷回，但是需要排除由系统闪存区121读出的操作类型为刷回的物理地址到逻辑地址映射表。可利用缓存设值单元113，对多个物理地址到逻辑地址映射表同时清除。

[0115] 在一些实施例中，如步骤S205至步骤S210所示，在对所有物理地址到逻辑地址映射表进行刷回前，需要判断物理地址到逻辑地址映射表所属的闪存块与区块是否与操作类型为更新的物理地址到逻辑地址映射表相同。若相同，则须依照操作类型为更新的物理地址到逻辑地址映射表中标记有刷回标志位的条目标记刷回标志位，用以避免条目的重复刷回。可利用缓存搜索单元112，快速找出所有标记有刷回标志位的条目。

[0116] S211、同步进行缓存中所有物理地址到逻辑地址映射表的刷回。

[0117] 在一些实施例中，在做物理地址到逻辑地址映射表的刷回时，可以在多张物理地址到逻辑地址映射表中，快速找出属于同一逻辑地址到物理地址映射表的物理地址到逻辑地址映射表条目。

[0118] S212、逻辑地址到物理地址映射表重建完成，输出最后的闪存块及参与逻辑地址到物理地址映射表重建的最后一个区块的下一区块。

[0119] 在一些实施例中，当逻辑地址到物理地址映射表重建完成后，会输出闪存块及参与逻辑地址到物理地址映射表重建的最后一区块的下一区块，物理地址到逻辑地址映射表将根据这闪存块与区块进行重建。

[0120] 如图10所示，在执行步骤S206和步骤209时，具体包括步骤S301至步骤S304。

[0121] S301、在缓存设值单元中设置位掩码，以清除所有的刷回标志位。

[0122] S302、将缓存设值单元中预设值设置为零。

[0123] S303、将缓存设值单元中的地址长度设置为需要清除的所有的刷回标志位范围。

[0124] S304、启动缓存设值单元，清除所需范围中所有条目的刷回标志位。

[0125] 如图11所示，在执行步骤S210时，具体包括步骤S401至步骤S405。

[0126] S401、在缓存搜索单元中设置位掩码，且该位掩码比对刷回标志位。

[0127] S402、在缓存搜索单元中设置搜索值，且搜索值为刷回标志位。

[0128] S403、启动缓存搜索单元，在操作类型为更新的物理地址到逻辑地址映射表中找出所有标记有刷回标志位的条目。

[0129] S404、依据搜索结果获取地址区块表。

[0130] S405、依照地址区块表在目标物理地址到逻辑地址映射表对应条目中标记刷回标志位。

[0131] 如图12所示，在执行步骤S211时，具体包括步骤S501至步骤S505。

[0132] S501、判断物理地址到逻辑地址映射表索引对应的物理地址到逻辑地址条目是否标记为刷回标志位，若是，则执行步骤S505，否则，执行S502。

[0133] S502、读取该物理地址到逻辑地址条目的逻辑地址到物理地址映射表并保存在第一缓存中。

[0134] S503、使用缓存搜索单元在所有待刷回的物理地址到逻辑地址映射表中搜索属于该逻辑地址到物理地址映射表的其余条目。

[0135] S504、将所有属于此逻辑地址到物理地址映射表的物理地址到逻辑地址条目刷回此逻辑地址到物理地址映射表，并将刷回的物理地址到逻辑地址条目标记刷回标志位。

[0136] S505、物理地址到逻辑地址映射表索引增加一。

[0137] S506、判断物理地址到逻辑地址映射表索引是否到最后一个刷回的物理地址到逻辑地址映射表末端，若已到物理地址到逻辑地址映射表末端，则结束流程，若未到物理地址到逻辑地址映射表末端，则返回步骤S501。

[0138] 如图13所示，在执行步骤S503时，具体包括步骤S601至步骤S604。

[0139] S601、在缓存搜索单元中预搜索的数据设定为物理地址到逻辑地址条目。

[0140] S602、在缓存搜索单元中设置位掩码，仅显示逻辑地址到物理地址映射表的位置信息。

[0141] S603、启动缓存搜索单元。

[0142] S604、存取搜索结果。

[0143] 在本发明一实施例中，在缓存中进行物理地址到逻辑地址映射表的重建包括步骤S701至步骤S709。

[0144] S701、获取重建的逻辑地址到物理地址映射表输出的闪存块信息和区块信息。

[0145] S702、判断闪存块信息对应的闪存块是否有效，若有效则执行步骤S703，否则执行步骤S704。

[0146] S703、判断区块是否超出总区块数，若是，则执行步骤S704，否则执行步骤S705。

[0147] S704、重设物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构为无资料状态。并执行步骤S706、物理地址到逻辑地址映射表重建完成。

[0148] S705、判断闪存块信息与区块信息是否与操作类型为更新的物理地址到逻辑地址资料结构相同，若相同，则执行步骤S707，否则依次执行步骤S708和709后，再执行步骤S707。

[0149] S707、判断物理地址到逻辑地址映射表索引是否已经指向物理地址到逻辑地址映射表末端，若是，则执行步骤S706，否则执行S710。

[0150] S708、重设物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构为无资料状态。

[0151] S709、以闪存块信息和区块信息初始化物理地址到逻辑地址资料结构。

[0152] S710、读取数据闪存区中物理地址到逻辑地址映射表索引对应的页。

[0153] S711、判断该页中的内容是否为空，若为空，则执行步骤S706，否则执行S712并返回S707。

[0154] S712、以该页的元数据中的逻辑地址更新物理地址到逻辑地址映射表，物理地址到逻辑地址映射表索引随之增加。

[0155] 在一些实施例中，由逻辑地址到物理地址映射表重建完成所输出的闪存块信息和区块信息决定须重建的物理地址到逻辑地址映射表。且对于物理地址到逻辑地址映射表的重建，使用操作类型为更新的第二缓存及物理地址到逻辑地址资料结构。

[0156] 在一些实施例中，若闪存块为无效值，则判定无物理地址到逻辑地址映射表需要重建，重设物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构为无资料状态。

[0157] 在一些实施例中，若闪存块为有效值，但区块已超出总区块数，则判定无物理地址到逻辑地址映射表需要重建，重设物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构为无资料状态。

[0158] 在一些实施例中，若闪存块为有效值，且区块也未超出总区块数，则须做物理地址到逻辑地址映射表重建。

[0159] 在做物理地址到逻辑地址映射表重建前，须判断闪存块信息及区块信息是否皆与操作类型为更新的物理地址到逻辑地址映射表相同。若相同则直接做重建，继续掉电前的进度。若不同则重设操作类型为更新的物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构为无资料状态，接着以闪存块信息及区块信息初始化物理地址到逻辑地址资料结构，再做物理地址到逻辑地址映射表重建。

[0160] 物理地址到逻辑地址映射表的重建以读取数据闪存中页的元数据进行，由旧到新读取，直到遇到内容为空白的页或已达闪存块的末端为止。读出页的元数据后，以元数据中的逻辑地址更新物理地址到逻辑地址映射表，物理地址到逻辑地址映射表索引值也随之增加。即当闪存块信息与区块信息与操作类型为更新的物理地址到逻辑地址资料结构相同时，则读取数据闪存区中物理地址到逻辑地址映射表索引对应的页，以页的元数据中的逻辑地址更新物理地址到逻辑地址映射表，索引持续向前，直到读到空页或映射表末端；当闪存块信息与区块信息与操作类型为更新的物理地址到逻辑地址资料结构不同时，则重设物理地址到逻辑地址映射表与物理地址到逻辑地址资料结构为无资料状态，并以闪存块信息和区块信息初始化物理地址到逻辑地址资料结构，并读取数据闪存区中物理地址到逻辑地址映射表索引对应的页，以页的元数据中的逻辑地址更新物理地址到逻辑地址映射表，索引持续向前，直到读到空页或映射表末端。

[0161] 综上所述，本发明提供的映射表的重建方法，在重建映射表前，在控制器中配置第一缓存和第二缓存，以重建逻辑地址到物理地址映射表，以及物理地址到逻辑地址映射表。在重建映射表时，首先重建逻辑地址到物理地址映射表，再依据重建的逻辑地址到物理地址映射表输出的闪存块与区块，重建物理地址到逻辑地址映射表。

[0162] 以上公开的本发明实施例只是用于帮助阐述本发明。实施例并没有详尽叙述所有的细节，也不限制该发明仅为所述的具体实施方式。显然，根据本说明书的内容，可作很多的修改和变化。本说明书选取并具体描述这些实施例，是为了更好地解释本发明的原理和实际应用，从而使所属技术领域技术人员能很好地理解和利用本发明。本发明仅受权利要求书及其全部范围和等效物的限制。