CN119718203A - 存储器管理方法及存储器控制器 - Google Patents

Abstract

一种存储器管理方法及存储器控制器，存储器管理方法适用于配置有可复写式非易失性存储器模块的存储装置，包括：获取多个虚拟块各自的有效计数，每个虚拟块包括可复写式非易失性存储器模块的一或多个物理块；根据每个虚拟块的有效计数，获取每个虚拟块的预回收状态；根据每个虚拟块的预回收状态，决定每个虚拟块的有效数据位图的更新顺序；根据每个虚拟块的有效数据位图的更新顺序，从选择目标虚拟块，以利用对应目标虚拟块的逻辑到物理索引清单和对应逻辑到物理索引清单的逻辑到物理映射表来更新目标虚拟块的目标有效数据位图。该方法通过预先更新有效数据位图并结合预回收状态机制，显着提升了前景垃圾回收的效率，改善了存储设备的性能表现。

Description

存储器管理方法及存储器控制器

技术领域

本公开涉及存储器技术领域，具体涉及一种存储器管理方法及存储器控制器。

背景技术

非易失性存储器(non-volatile memory)是指当电流断掉后，所存储的数据不会消失的电脑存储器，具有数据非易失性、省电、体积小与无机械结构等优点，被广泛地应用于各种电子装置中。

常见的的非易失性存储器(non-volatile memory)为配置闪存(NAND Flash)的存储器(如固态硬盘)，其具有读写速度高，不须机械化结构来进行数据的存取等特点。

在NAND闪存存储设备中，随着数据的频繁写入和更新，存储空间中会产生大量无效数据。为了优化存储空间的利用效率，存储设备需要通过垃圾回收(GarbageCollection，GC)机制来整理存储块中的有效数据。垃圾回收过程可分为前景垃圾回收(Foreground GC)和背景垃圾回收(Background GC)。其中，前景垃圾回收是在主机数据写入过程中，由于剩余存储空间不足而被迫执行的垃圾回收操作。由于前景垃圾回收与主机写入同时进行，需要在垃圾回收过程中频繁查找和更新映射表，这不仅消耗大量系统资源，还会显着影响存储设备的性能表现。因此，如何提高前景垃圾回收的效率，是当前存储设备亟需解决的技术问题。

发明内容

针对上述问题，本公开提供一种存储器管理方法及存储器控制器，通过引入有效数据位图并结合预回收状态机制，显着提升前景垃圾回收的效率。

本公开的一或多个实施例提供一种存储器管理方法，适用于配置有可复写式非易失性存储器模块的存储装置。所述方法包括：获取多个虚拟块各自的有效计数(validcount)，其中每个虚拟块包括所述可复写式非易失性存储器模块的一或多个物理块；根据所述每个虚拟块的有效计数，获取每个虚拟块的预回收状态；根据所述每个虚拟块的所述预回收状态，决定每个虚拟块的有效数据位图的更新顺序；根据每个虚拟块的所述有效数据位图的所述更新顺序，从所述多个虚拟块中选择目标虚拟块，以利用对应所述目标虚拟块的逻辑到物理索引清单和对应所述逻辑到物理索引清单的逻辑到物理映射表来更新所述目标虚拟块的目标有效数据位图。

在本公开的一或多个实施例中，其中所述方法还包括：根据所述每个虚拟块的所述预回收状态，决定每个虚拟块的垃圾回收顺序。

在本公开的一或多个实施例中，其中获取每个虚拟块的所述预回收状态的步骤包括：根据每个虚拟块的所述有效计数，比较每个虚拟块的所述有效计数及不同大小的多个阈值，以决定每个虚拟块的所述有效计数所位于的阈值区间；根据每个虚拟块的所述阈值区间，决定每个虚拟块的所述预回收状态，若一个虚拟块的所述有效计数大于所述多个阈值中的最大阈值，决定所述一个虚拟块的所述预回收状态为最小的所述预回收状态；若一个虚拟块的所述有效计数小于所述多个阈值中的最小阈值，决定所述一个虚拟块的所述预回收状态为最大的所述预回收状态；其中对应最小的所述预回收状态的第一虚拟块被判定不需要更新所对应的第一有效数据位图，并且对应最大的所述预回收状态的第二虚拟块被判定需要优先更新所对应的第二有效数据位图。

在本公开的一或多个实施例中，其中所述多个阈值的数量为3，所述预回收状态包括第一预回收状态、第二预回收状态、第三预回收状态和第四预回收状态，其中所述第一预回收状态对应的有效计数大于第一阈值，所述第二预回收状态对应的有效计数大于第二阈值且小于所述第一阈值，所述第三预回收状态对应的有效计数大于第三阈值且小于所述第二阈值，所述第四预回收状态对应的有效计数小于所述第三阈值，其中所述第一阈值为所述最大阈值，所述第三阈值为所述最小阈值，所述第一阈值大于所述第二阈值，并且所述第二阈值大于所述第三阈值。

在本公开的一或多个实施例中，其中所述逻辑到物理索引清单用于记录与所对应的虚拟块关联的一或多个逻辑到物理映射表的识别码，其中所对应的所述虚拟块所存储的有效数据的物理地址会被记录在所述一或多个逻辑到物理映射表的其中之一。

在本公开的一或多个实施例中，其中所述有效数据位图包括多个比特，每个所述比特对应所述虚拟块中一预设大小的数据区域，用于指示所述数据区域中的数据是否为有效数据。

在本公开的一或多个实施例中，其中所述方法还包括：在所述存储装置处于空闲期间时更新所述目标虚拟块，其中更新所述目标虚拟块的所述目标有效数据位图的步骤包括：通过所述目标虚拟块的所述逻辑到物理索引清单确定与所述目标虚拟块关联的一或多个目标逻辑到物理映射表；检查所述目标虚拟块的每个数据区域的物理地址是否存在于所述一或多个目标逻辑到物理映射表；以及根据每个数据区域的检查结果更新所述目标有效数据位图的所述多个比特，其中完成更新的所述目标有效数据位图被存储到所述可复写式非易失性存储器模块。

在本公开的一或多个实施例中，其中更新所述目标有效数据位图的所述多个比特的步骤包括：若所述目标虚拟块的第一数据区域的第一物理地址存在于所述一或多个目标逻辑到物理映射表的其中之一，将所述目标有效数据位图的所述多个比特中对应所述第一数据区域的第一比特设置为第一值；以及若所述目标虚拟块的第二数据区域的第二物理地址不存在于任一所述一或多个目标逻辑到物理映射表，将所述目标有效数据位图的所述多个比特中对应所述第二数据区域的第二比特设置为第二值。

在本公开的一或多个实施例中，其中决定每个虚拟块的所述垃圾回收顺序包括：在于主机写入操作期间执行前景垃圾回收时，优先选择具有最大的所述预回收状态的虚拟块作为垃圾回收虚拟块进行垃圾回收；以及其次选择具有次大的所述预回收状态的虚拟块作为所述垃圾回收虚拟块进行垃圾回收。

在本公开的一或多个实施例中，其中执行垃圾回收的步骤包括：获取所选的所述垃圾回收虚拟块的所述有效数据位图；根据所选虚拟块的所述有效数据位图中的多个第一比特，将所述垃圾回收虚拟块中对应所述多个第一比特的多个第一数据区域各自的第一数据复制到数据块；以及对所述垃圾回收虚拟块执行擦除操作。

本公开的一或多个实施例提供一种存储器控制器，用于控制配置有可复写式非易失性存储器模块的存储装置。所述存储器控制器包括：存储器接口控制电路，用以电性连接至所述可复写式非易失性存储器模块；数据管理电路，电性连接至所述存储装置的连接接口电路，用以经由所述连接接口电路从主机系统接收数据及指令；缓冲存储器，用以缓存数据；以及处理器，电性连接至所述存储器接口控制电路、所述数据管理电路及所述缓冲存储器。其中，所述处理器被配置以：获取多个虚拟块各自的有效计数，其中每个所述虚拟块包括所述可复写式非易失性存储器模块的一或多个物理块；根据所述每个虚拟块的有效计数，获取每个虚拟块的预回收状态；根据所述每个虚拟块的所述预回收状态，决定每个虚拟块的有效数据位图的更新顺序；根据每个虚拟块的所述有效数据位图的所述更新顺序，从所述多个虚拟块中选择目标虚拟块，以利用对应所述目标虚拟块的逻辑到物理索引清单和对应所述逻辑到物理索引清单的逻辑到物理映射表来更新所述目标虚拟块的目标有效数据位图。

基于上述，本公开实施例所提供的存储器管理方法及存储器控制器，可通过预先建立和更新有效数据位图，显着减少了前景垃圾回收时的映射表查询开销；利用预回收状态机制对虚拟块进行分级管理，使得垃圾回收可优先处理无效数据比例较高的虚拟块，提高了存储空间的回收效率；在存储设备空闲时预先更新有效数据位图，避免了在执行垃圾回收时的实时更新开销，有效提升了存储设备在高负载情况下的响应速度。

附图说明

包含附图以便进一步理解本发明，且附图并入本说明书中并构成本说明书的一部分。附图说明本发明的实施例，并与描述一起用于解释本发明的原理。

图1是根据本发明一实施例的主机系统及存储装置的方块示意图；

图2是根据本发明一实施例的存储器管理方法的流程图；

图3是根据本发明一实施例的写入数据的逻辑到物理索引清单的更新示意图；

图4是根据本发明一实施例的更新有效数据位图的示意图；

图5是根据本发明一实施例的预回收状态分级机制的示意图；

图6是根据本发明一实施例的虚拟块预回收状态表的示意图；

图7是根据本发明另一实施例的存储器管理方法的流程图。

附图标号说明

10：主机系统

20：存储装置

211：第一处理器

110：第二处理器

120：主机存储器

130：数据传输接口电路

210：存储器控制器

212：数据管理电路

213：存储器接口控制电路

214：缓冲存储器

220：可复写式非易失性存储器模块

230：连接接口电路

BM1：有效数据位图

IDX1：逻辑到物理索引清单

L2P1、L2P2：逻辑到物理映射表

TB61：虚拟块预回收状态表

VB1：虚拟块

PG1、PG2、PG3：数据区域

LBA1、LBA11、LBA12、LBA21、LBA22：逻辑地址PBA1、PBA11、PBA12、PBA13、PBA21、PBA22：物理地址C1、C2、C3：第一阈值

CT5：图表

S210-S240：存储器管理方法的流程步骤

S710-S740：存储器管理方法的流程步骤

A31、A32、A41、A42、A43、A44、A45：第一箭头

具体实施方式

现将详细地参考本公开的示范性实施例，示范性实施例的实例说明于附图中。只要有可能，相同组件符号在附图和描述中用来表示相同或相似部分。

图1为根据本公开的实施例所示出的主机系统与存储装置的方块示意图。请参照图1，主机系统10例如是个人电脑、笔记本电脑、服务器。主机系统(Host System)10包括处理器(Processor)110(也称，第二处理器)及主机存储器(Host Memory)120、数据传输接口电路(Data Transfer Interface Circuit)130。在本实施例中，处理器110耦接(也称，电性连接)至主机存储器120及数据传输接口电路130。在另一实施例中，处理器(Processor)110、主机存储器120及数据传输接口电路130之间利用系统总线(System Bus)彼此电性连接。在本实施例中，处理器110、主机存储器120及数据传输接口电路130可设置在主机系统10的主机板上。

存储装置20包括存储器控制器(Storage Controller)210、可复写式非易失性存储器模块(Rewritable Non-Volatile Memory Module)220及连接接口电路(ConnectionInterface Circuit)230。其中，存储器控制器210包括处理器211(也称，第一处理器)、数据管理电路(Data Management Circuit)212与存储器接口控制电路(Memory InterfaceControl Circuit)213。

在本实施例中，主机系统10是通过数据传输接口电路130与存储装置20的连接接口电路230电性连接至存储装置20来进行数据的存取操作。例如，主机系统10可经由数据传输接口电路130将数据存储至存储装置20或从存储装置20中读取数据。

在本实施例中，数据传输接口电路130的数目可以是一或多个。通过数据传输接口电路130，主机板可以经由有线或无线方式电性连接至存储装置20。存储装置20可例如是U盘、存储卡、固态硬盘(Solid State Drive，SSD)或无线存储器存储装置。无线存储器存储装置可例如是近距离无线通讯(Near Field Communication，NFC)存储器存储装置、无线传真(WiFi)存储器存储装置、蓝牙(Bluetooth)存储器存储装置或低功耗蓝牙存储器存储装置(例如，iBeacon)等以各式无线通讯技术为基础的存储器存储装置。此外，主机板也可以通过系统总线电性连接至全球定位系统(Global Positioning System，GPS)模块、网络接口卡、无线传输装置、键盘、屏幕、喇叭等各式I/O装置。

在本实施例中，数据传输接口电路130与连接接口电路230是相容于高速周边零件连接接口(Peripheral Component Interconnect Express，PCI Express)标准的接口电路。并且，数据传输接口电路130与连接接口电路230之间是利用快速非易失性存储器接口标准(Non-Volatile Memory express，NVMe)通讯协定来进行数据的传输。

此外，在另一实施例中，连接接口电路230可与存储器控制器210封装在一个芯片中，或者连接接口电路230是布设于一包含存储器控制器210的芯片外。

在本实施例中，主机存储器120用以暂存处理器110所执行的指令或数据。例如，在本实施例中，主机存储器120可以是动态随机存取存储器(Dynamic Random AccessMemory，DRAM)、静态随机存取存储器(Static Random Access Memory，SRAM)等。然而，必须了解的是，本公开不限于此，主机存储器120也可以是其他适合的存储器。

存储器控制器210用以执行以硬件型式或固件型式实作的多个逻辑门或控制指令并且根据主机系统10的指令在可复写式非易失性存储器模块220中进行数据的写入、读取与抹除等运作。

更详细来说，存储器控制器210中的处理器211为具备运算能力的硬件，其用以控制存储器控制器210的整体运作。具体来说，处理器211被多个控制指令/程序码所程序化，并且在存储装置20运作时，此些控制指令/程序码会被执行以进行数据的写入、读取与抹除等运作。此外，在本实施例中，所述控制指令/程序码更可被执行以实现本公开所提供的存储器管理方法。对应所述存储器管理的控制指令/程序码更可被实作为硬件形式的电路单元，以实现本公开所提供的存储器管理方法。

值得一提的是，在本实施例中，处理器110与处理器211例如是中央处理单元(Central Processing Unit，CPU)、微处理器(micro-processor)、或是其他可程序化的处理单元(Microprocessor)、数字信号处理器(Digital Signal Processor，DSP)、可程序化控制器、特殊应用集成电路(Application Specific Integrated Circuits，ASIC)、可程序化逻辑装置(Programmable Logic Device，PLD)或其他类似电路组件，本公开并不限于此。

在本实施例中，如上所述，存储器控制器210还包括数据管理电路212与存储器接口控制电路213。应注意的是，存储器控制器210各部件所执行的操作亦可视为存储器控制器210所执行的操作。

其中，数据管理电路212电性连接至处理器211、存储器接口控制电路213与连接接口电路230。数据管理电路212用以接受处理器211的指示来进行数据的传输。例如，经由连接接口电路230从主机系统10(如，主机存储器120)读取数据，并且将所读取的数据经由存储器接口控制电路213写入至可复写式非易失性存储器模块220中(如，根据来自主机系统10的写入指令(也称，主机写入指令)来进行写入操作(也称，主机写入操作))。又例如，经由存储器接口控制电路213从可复写式非易失性存储器模块220的一或多个实体单元中读取数据(数据可读取自一或多个实体单元中的一或多个存储单元)，并且将所读取的数据经由连接接口电路230写入至主机系统10(如，主机存储器120)中(如，根据来自主机系统10的读取指令来进行读取操作)。在另一实施例中，数据管理电路212亦可整合至处理器211中。

存储器接口控制电路213用以接受处理器211的指示，配合数据管理电路212来进行对于可复写式非易失性存储器模块220的写入(亦称，程序化，Programming)操作、读取操作或抹除操作(也称，擦除操作)。

此外，欲写入至可复写式非易失性存储器模块220的数据会经由存储器接口控制电路213转换为可复写式非易失性存储器模块220所能接受的格式。具体来说，若处理器211要存取可复写式非易失性存储器模块220，处理器211会传送对应的命令序列给存储器接口控制电路213以指示存储器接口控制电路213执行对应的操作。例如，这些指令序列可包括指示写入数据的写入指令序列、指示读取数据的读取指令序列、指示抹除数据的抹除指令序列、以及用以指示各种存储器操作的相对应的指令序列。这些指令序列可包括一或多个信号，或是在总线上的数据。这些信号或数据可包括指令码或程序码。例如，在读取指令序列中，会包括读取的识别码、存储器地址、物理地址等信息。

在本公开中，存储器控制器210会建立逻辑转实体地址映像表(Logical ToPhysical address mapping table，也称L2P映射表)与实体转逻辑地址映像表(PhysicalTo Logical address mapping tablee，也称P2L映射表)，以记录配置给可复写式非易失性存储器模块220的逻辑单元(如，逻辑块、逻辑页或逻辑列)的逻辑地址与实体单元(如，实体抹除单元/实体块、实体页、实体列)的实体地址(物理地址)之间的映像关系。换言之，存储器控制器210可通过逻辑转实体地址映像表(也称为逻辑转实体映射表)来查找一逻辑单元所映射的实体单元(如，查找逻辑页所映射的实体页；查找逻辑地址所映像的实体地址)，并且存储器控制器210可通过实体转逻辑地址映像表(也称，实体转逻辑映射表)来查找一实体单元所映射的逻辑单元(如，查找实体页所映射的逻辑页；查找实体地址所映像的逻辑地址)。

存储器控制器210还建立数据结构以记录各类映射关系，包括：记录每个虚拟块所对应的物理块的虚拟块映射清单、记录每个虚拟块所关联的L2P映射表的L2P索引清单、记录对应所有虚拟块的虚拟块预回收状态表。

在一实施例中，存储器控制器210还包括缓冲存储器214。缓冲存储器是电性连接至处理器211并且用以暂存来自于主机系统10的数据与指令、来自于可复写式非易失性存储器模块220的数据或其他用以管理存储装置20的系统数据(如，各种映射表、索引表、虚拟块映射清单、L2P索引清单、虚拟块预回收状态表等相关于本公开的系统数据)，以让处理器211可快速地从缓冲存储器214中存取所述数据、指令或系统数据。

在一实施例中，存储器控制器210在缓冲存储器214中预留特定区域用于存储各类映射表和索引信息。存储器控制器210根据访问频率和重要性对这些数据进行分级缓存：将经常访问的映射表信息保存在快速访问区域，而将较少使用的信息存储在普通区域。当缓冲存储器214空间不足时，存储器控制器210优先将较少使用的信息写回到可复写式非易失性存储器模块220中。为了提高数据可靠性，存储器控制器210还会定期将缓冲存储器214中的重要映射信息同步到可复写式非易失性存储器模块220中，并记录同步时间戳，以便在系统异常时能够恢复到最近的有效状态。

在一实施例中，存储器控制器210建立多个数据结构以记录各类映射关系。具体地，存储器控制器210建立虚拟块映射清单(VB mapping list)，用于记录每个虚拟块所对应的一个或多个物理块的标识信息。在某些实施例中，虚拟块映射清单还可以包含物理块在对应虚拟块内的位置信息，各物理块的擦除次数信息以及每个虚拟块的有效计数。存储器控制器210还建立L2P索引清单(L2P index list)，用于记录每个虚拟块所关联的一个或多个逻辑到物理映射表的标识码。此外，存储器控制器210还建立虚拟块预回收状态表(VBPre-GC state table)，用于记录对应所有虚拟块的预回收状态。在一实施例中，虚拟块预回收状态表的每个条目包含：虚拟块识别码、当前有效计数值等信息。

在另一实施例中，存储器控制器210将这些数据结构存储在缓冲存储器中的预设区域，并定期将其更新状态同步至所述可复写式非易失性存储器模块，以确保数据的持久性和一致性。在某些实施例中，当存储器控制器210重新启动时，可以从所述可复写式非易失性存储器模块中恢复这些数据结构的最新状态，确保系统能够继续之前的存储管理操作。

可复写式非易失性存储器模块220是电性连接至存储器控制器210(存储器接口控制电路213)并且用以存储主机系统10所写入的数据。

在本实施例中，可复写式非易失性存储器模块220具有多个字线，其中所述多个字线的每一个字线电性连接至多个存储单元，亦称列(也称，实体列)。同一条字线上的多个列会组成一个实体程序化单元(也称，实体页或物理页)。每个实体页会对应至一个实体地址，用以记录实体页所存储的数据的位置。此外，多个实体页可组成一个实体块(也称，实体抹除单元或物理块)。所述可复写式非易失性存储器模块的多个存储器晶粒中的每个存储器晶粒(芯片)具有多个平面(Plane)，并且每个平面具有多个实体块。应注意的是，本公开并不限定于每一个实体页及逻辑页的大小。

记忆胞类型(又称，存储模式)可用来表示每个记忆胞(Memory Cell，也称存储单元)可存储的比特数。常见的类型包括SLC(单层存储单元，每个存储单元存储1比特)、MLC(多层存储单元，每个存储单元存储2比特)、TLC(三层存储单元，每个存储单元存储3比特)等。不同的存储模式在存储密度、读写速度和耐久性等方面有所差异，影响着闪存的整体性能和特性。

图2是根据本公开一实施例的存储器管理方法的流程图。

参照图2，在一实施例中，存储器控制器210执行一种存储器管理方法。具体地，在步骤S210中，存储器控制器210获取多个虚拟块各自的有效计数，其中每个虚拟块包括所述可复写式非易失性存储器模块220的一或多个物理块。

在一实施例中，存储器控制器210可以通过多种方式获取虚拟块的有效计数。在存储装置20执行写入操作时，存储器控制器210维护一个有效计数计数器，用于实时统计每个虚拟块中的有效数据数量。具体地，当执行写入操作时，存储器控制器210执行以下操作之一：

当写入数据为新数据时，存储器控制器210将目标虚拟块的有效计数计数器加1；当写入数据覆盖原有数据时，存储器控制器210首先根据逻辑到物理映射表确定被覆盖数据所在的源虚拟块，将源虚拟块的有效计数计数器减1，再将目标虚拟块的有效计数计数器加1；当删除数据时，存储器控制器210将对应虚拟块的有效计数计数器减1。

在另一实施例中，存储器控制器210可以在后台定期扫描逻辑到物理映射表，通过统计每个虚拟块在映射表中出现的次数来更新有效计数。这种方式虽然计算开销较大，但可以校正由于系统异常导致的计数误差。

在步骤S220中，存储器控制器210根据所述每个虚拟块的有效计数，获取每个虚拟块的预回收状态。

在一实施例中，存储器控制器210在获取每个虚拟块的预回收状态时，首先根据每个虚拟块的有效计数与预设的多个阈值进行比较，以确定该虚拟块的有效计数所处的阈值区间。具体地，存储器控制器210预设多个不同大小的阈值，并将这些阈值按照从大到小的顺序排列，用于划分多个阈值区间。

存储器控制器210随后根据每个虚拟块的有效计数所处的阈值区间来决定其预回收状态。当某个虚拟块的有效计数大于所述多个阈值中的最大阈值时，存储器控制器210将该虚拟块的预回收状态设定为最小的预回收状态值。相反地，当某个虚拟块的有效计数小于所述多个阈值中的最小阈值时，存储器控制器210将该虚拟块的预回收状态设定为最大的预回收状态值。

例如，当一个第一虚拟块被判定具有最小的预回收状态时，存储器控制器210将该第一虚拟块标记为不需要更新其对应的第一有效数据位图。这是因为具有最小预回收状态的虚拟块通常具有较高的有效数据比例，暂时不需要进行垃圾回收。相反地，当一个第二虚拟块被判定具有最大的预回收状态时，存储器控制器210将该第二虚拟块标记为需要优先更新其对应的第二有效数据位图，因为这类虚拟块的无效数据比例较高，更有可能被选为垃圾回收的目标。

图5是根据本发明一实施例的预回收状态分级机制的示意图。

参照图5，在一实施例中，存储器控制器210实现了一种预回收状态分级机制。如图表CT5所示，坐标轴表示有效计数(Valid Count)，存储器控制器210基于虚拟块的有效计数值将其划分为不同的预回收状态。

在本实施例中，存储器控制器210预设三个阈值，分别为第一阈值(C1)、第二阈值(C2)和第三阈值(C3)，且满足C1大于C2且C2大于C3。存储器控制器210利用这三个阈值将有效计数的取值范围划分为四个区间，并将这四个区间分别对应到四种不同的预回收状态。

具体地，当存储器控制器210检测到某个虚拟块的有效计数大于第一阈值C1时，将该虚拟块的预回收状态设定为"状态1"，并标记为"无需更新"。这表示该虚拟块中的有效数据比例较高，暂时不需要更新其有效数据位图或进行垃圾回收。

当存储器控制器210检测到某个虚拟块的有效计数小于第一阈值C1但大于第二阈值C2时，将该虚拟块的预回收状态设定为"状态2"，并标记为"低优先级"。这表示该虚拟块可在系统资源充足时更新其有效数据位图。

当存储器控制器210检测到某个虚拟块的有效计数小于第二阈值C2但大于第三阈值C3时，将该虚拟块的预回收状态设定为"状态3"，并标记为"次高优先级"。这表示该虚拟块具有相对较高的更新优先级。

当存储器控制器210检测到某个虚拟块的有效计数小于第三阈值C3时，将该虚拟块的预回收状态设定为"状态4"，并标记为"最高优先级"。这表示该虚拟块中的无效数据比例较高，需要优先更新其有效数据位图，并可能被优先选择进行垃圾回收操作。

在一实施例中，在具体实现中，存储器控制器210可以根据存储装置20的性能要求和工作负载特性，动态调整这些阈值的具体数值。例如，在高性能要求场景下，可以提高这些阈值的数值，使得更多的虚拟块被划分到高优先级的预回收状态，从而更积极地进行垃圾回收；在低功耗场景下，则可以降低这些阈值的数值，减少不必要的垃圾回收操作。

此外，虽然上述的例子使用了三个阈值来管理预回收状态的分级，但本公开不限于此。例如，存储器控制器210可使用更多或更少的阈值来管理预回收状态的分级。

回到图2，接着，在步骤S230中，存储器控制器210根据所述每个虚拟块的所述预回收状态，决定每个虚拟块的有效数据位图的更新顺序。

在一实施例中，存储器控制器210优先更新预回收状态值较大的虚拟块的有效数据位图。例如，当检测到存储装置20处于空闲状态时，存储器控制器210首先更新具有第四预回收状态的虚拟块的有效数据位图，然后依次更新具有第三预回收状态和第二预回收状态的虚拟块的有效数据位图。而对于具有第一预回收状态的虚拟块，由于其有效数据比例较高，可以暂不更新其有效数据位图。

在步骤S240中，存储器控制器210根据每个虚拟块的所述有效数据位图的所述更新顺序，从所述多个虚拟块中选择目标虚拟块，以利用对应所述目标虚拟块的逻辑到物理索引清单和对应所述逻辑到物理索引清单的逻辑到物理映射表来更新所述目标虚拟块的目标有效数据位图。

在一实施例中，具体地，存储器控制器210首先通过目标虚拟块的逻辑到物理索引清单找到与该目标虚拟块相关联的所有逻辑到物理映射表。然后，存储器控制器210检查目标虚拟块中每个数据区域的物理地址是否仍存在于这些映射表中。若某数据区域的物理地址仍存在于映射表中，则将目标有效数据位图中对应该数据区域的比特设置为第一值(e.g.,1)；若某数据区域的物理地址不存在于任何映射表中，则将对应的比特设置为第二值(e.g.,0)。更新完成后，存储器控制器210将目标有效数据位图存储到所述可复写式非易失性存储器模块220中。

在一实施例中，当符合预定条件(例如，在存储装置20空闲时)时，存储器控制器210能够预先更新各虚拟块的有效数据位图，为后续的前景垃圾回收操作提供快速的数据有效性判断依据，从而提高垃圾回收的效率。

图3是根据本发明一实施例的写入数据的逻辑到物理索引清单的更新示意图。

参照图3，在一实施例中，当将写入数据TD写入虚拟块VB1时，存储器控制器210更新逻辑到物理索引清单。

详细来说，如箭头A31所示，当存储装置20的虚拟块VB1接收到写入数据时，该数据被分配一个物理地址"PBA1"并存储在虚拟块VB1中。同时，存储器控制器210需要在逻辑到物理映射表L2P1中建立该数据的逻辑地址"LBA1"到物理地址"PBA1"的映射关系。具体地，存储器控制器210在逻辑到物理映射表L2P1中创建一个新的表项，其中包含逻辑地址字段和物理地址字段，分别记录"LBA1"和"PBA1"。

接着，如箭头A32所示，存储器控制器210还需要更新逻辑到物理索引清单IDX1。该逻辑到物理索引清单IDX1用于记录与虚拟块相关联的一个或多个逻辑到物理映射表的识别码。在本实施例中，存储器控制器210在索引清单IDX1中记录了逻辑到物理映射表L2P1的识别码"L2P1"，表示虚拟块VB1中存储的有效数据的物理地址信息可以在映射表L2P1中找到。也表示了，虚拟块VB1的有效数据中会关联到逻辑到物理索引清单IDX1所记录的逻辑到物理映射表L2P1。

在一实施例中，存储器控制器210在建立逻辑到物理索引清单时，采用分层索引结构。第一层是虚拟块标识符，用于快速定位目标虚拟块；第二层是与该虚拟块相关的所有L2P映射表的标识符列表。这种分层结构使得存储器控制器210能够快速找到与特定虚拟块相关的所有映射信息。

存储器控制器210通过以下步骤更新L2P索引清单：当写入新数据时，存储器控制器210首先检查数据的目标虚拟块是否已在索引清单中有对应条目。如果没有，则创建新的索引条目；如果已存在，则检查新数据对应的L2P映射表是否已在该虚拟块的映射表列表中。对于不在列表中的新映射表，存储器控制器210将其标识符添加到列表中。

当同一个虚拟块的数据映射关系分散在多个逻辑到物理映射表中时，存储器控制器210会在该虚拟块对应的索引清单中记录所有相关映射表的识别码。这种设计使得存储器控制器210在进行垃圾回收时，能够快速定位并加载所有需要查询的映射表(加载到缓存存储器214)，提高了数据有效性判断的效率。

通过维护这种索引清单机制，存储器控制器210能够在后续的垃圾回收过程中，快速确定需要检查哪些逻辑到物理映射表，从而提高了有效数据位图的更新效率。当存储器控制器210需要更新某个虚拟块的有效数据位图时，只需查找该虚拟块对应的索引清单，即可获知所有需要检查的映射表的识别码，避免了对所有映射表进行遍历的开销，从而加速了更新有效数据位图的速度。

图4是根据本发明一实施例的更新有效数据位图的示意图。

参照图4，在一实施例中，存储器控制器210建立并维护有效数据位图BM1，该位图包括多个比特。每个比特对应虚拟块VB1中一个预设大小的数据区域(e.g.,PG1、PG2、PG3)，用于指示该数据区域中的数据是否为有效数据。具体地，当某个数据区域存储的数据仍然有效(为有效数据)时，存储器控制器210将对应该区域的比特设置为第一值(e.g.,"1")；当某个数据区域存储的数据已经失效(不为有效数据)时，存储器控制器210将对应该区域的比特设置为第二值(e.g.,"0")。

在一实施例中，当存储装置20处于空闲期间时(例如，没有主机命令需要处理时)，存储器控制器210执行目标虚拟块VB1的有效数据位图更新操作。首先，存储器控制器210访问目标虚拟块VB1对应的逻辑到物理索引清单IDX1，该清单记录了与目标虚拟块VB1相关联的所有逻辑到物理映射表的标识符，包括"L2P1"和"L2P2"。

存储器控制器210访问逻辑到物理索引清单IDX1，该索引清单IDX1记录了与虚拟块VB1相关联的逻辑到物理映射表的标识符，包括"L2P1"和"L2P2"。存储器控制器210据此确定需要加载并检查映射表L2P1和L2P2，以验证虚拟块VB1中数据的有效性。

在加载到映射表L2P1和L2P2到缓存存储器214后，存储器控制器210检查虚拟块的每个存储区域的物理地址是否存在于映射表L2P1和L2P2所记录的物理地址中。

存储器控制器210根据索引清单IDX1中的标识符，加载相关的逻辑到物理映射表L2P1和L2P2。如箭头A41所示，存储器控制器210检查到第一数据区域PG1的第一物理地址"PBA11"存在于映射表L2P1中，且与逻辑地址"LBA11"相关联。因此，存储器控制器210判定第一数据区域PG1的第一物理地址"PBA11"存储了有效数据。接着，如箭头A42所示，存储器控制器210将有效数据位图BM1中对应该第一数据区域的第一比特设置为"1"(也称，第一值)。

如箭头A43所示，存储器控制器210检查到第二数据区域PG2的第二物理地址"PBA12"不存在于任何一个逻辑到物理映射表中(图中用"×"标记表示)。这表明存储在该物理地址的数据已经失效(如，该物理地址对应无效数据)，因此存储器控制器210将有效数据位图BM1中对应该第二数据区域的第二比特设置为"0"(也称，第二值)。

又例如，如箭头A44和A45所示，对于第三数据区域PG3的物理地址"PBA13"，存储器控制器210在映射表L2P2中发现了其对应的有效映射关系，其中该物理地址与逻辑地址"LBA22"相关联。这表明该数据仍然有效，因此存储器控制器210将有效数据位图BM1中对应该第三数据区域的比特设置为"1"。

依此类推，存储器控制器210可更新完对应虚拟块VB1的有效数据位图BM1。通过这种方式，存储器控制器210完成了虚拟块VB1的有效数据位图BM1的更新。更新后的位图准确反映了虚拟块VB1中每个数据区域的有效性状态，为后续的垃圾回收操作提供了可靠的参考依据。

在完成所有数据区域的有效性检查后，存储器控制器210将更新完成的目标有效数据位图BM1存储到可复写式非易失性存储器模块220中，以供后续的垃圾回收操作使用。通过这种方式，存储装置20能够在空闲时间预先完成有效数据位图的更新，从而减少垃圾回收操作时的开销。

在一实施例中，在实际实现中，存储器控制器210可以采用批处理方式，同时检查多个物理地址的有效性，并一次性更新有效数据位图中的多个比特，从而提高更新效率。此外，存储器控制器210还可以在更新过程中维护一个校验和，用于验证更新后的有效数据位图的完整性。

图6是根据本发明一实施例的虚拟块预回收状态表的示意图。

参照图6，在一实施例中，存储器控制器210维护一个虚拟块预回收状态表TB61，用于记录多个虚拟块的状态信息并引导垃圾回收操作。

虚拟块预回收状态表TB61包含多个字段：虚拟块编号/识别码字段，用于唯一标识每个虚拟块；有效计数字段，记录每个虚拟块中的有效数据量；预回收状态字段，指示虚拟块的预回收状态值；以及"是否需要更新"字段，用于标记该虚拟块的有效数据位图是否需要更新。在本实施例中，预回收状态为1的会被判定为因为有效数据的总量超过一定值，而不需要去更新对应的有效数据位图，进而减少了资源上的开销。

在本实施例中，存储器控制器210预设三个阈值：第一阈值C1(45000)、第二阈值C2(35000)和第三阈值C3(20000)。根据有效计数值与这些阈值的比较结果，存储器控制器210为每个虚拟块分配相应的预回收状态。例如，图6中编号为"0"的虚拟块的有效计数为65536，大于C1，因此其预回收状态被设置为"1"；而编号为"1"的虚拟块的有效计数为16000，小于C3，因此其预回收状态被设置为"4"，依此类推。

存储器控制器210根据预回收状态值决定是否需要更新虚拟块的有效数据位图。具体地，当预回收状态值为"1"时，由于其有效数据比例较高，标记为"否"，表示暂不需要更新；当预回收状态值大于"1"时，标记为"是"，表示需要在存储装置20空闲时更新其有效数据位图。

在主机写入操作期间需要执行前景垃圾回收时，存储器控制器210优先选择具有最大预回收状态值(即状态值为"4")的虚拟块作为垃圾回收目标。如图6所示，虚拟块"1"和虚拟块"5"的预回收状态为"4"，其中虚拟块"1"的有效计数更少(16000)，因此被优先选择。如果这些虚拟块已处理完毕，存储器控制器210会转而选择具有次大预回收状态值(即状态值为"3")的虚拟块，如图中的虚拟块"6"和虚拟块"7"，依此类推。也就是说，存储器控制器210可根据所述每个虚拟块的所述预回收状态，决定每个虚拟块的垃圾回收顺序。

以图6为例，当需要执行前景垃圾回收时，存储器控制器210首先选择虚拟块"1"(有效计数16000，预回收状态"4")作为垃圾回收虚拟块；接着选择虚拟块"5"(有效计数15000，预回收状态"4")；然后选择虚拟块"6"和虚拟块"7"(预回收状态均为"3")。这种基于预回收状态的选择策略确保了垃圾回收操作能够优先处理无效数据比例较高的虚拟块，从而提高存储空间的回收效率。

通过这种预回收状态表机制，存储器控制器210能够在前景垃圾回收时快速识别并优先处理最适合回收的虚拟块，显着提升了垃圾回收的效率。

图7是根据本发明另一实施例的存储器管理方法的流程图。

参照图7，在一实施例中，存储装置20执行一种结合前景垃圾回收的存储器管理方法。

在步骤S710中，存储器控制器210获取主机系统10发送的写入指令。在获取到写入指令后，存储器控制器210需要确保存储装置20具有足够的可用空间来完成数据写入操作。

在步骤S720中，存储器控制器210响应于判定需要执行前景垃圾回收操作时，根据每个虚拟块的预回收状态来选择目标虚拟块，并获取对应目标虚拟块的目标有效数据位图。具体地，存储器控制器210优先选择预回收状态值最大的虚拟块作为垃圾回收虚拟块，若存在多个具有相同预回收状态值的虚拟块，则进一步根据有效计数的大小来决定处理顺序。

在一实施例中，存储器控制器210可以通过多种方式判断是否需要执行前景垃圾回收操作。

在一优选实施例中，存储器控制器210通过监控存储装置20的可用空间来判断是否需要执行前景垃圾回收。具体地，存储器控制器210预设一个空闲空间阈值，当检测到存储装置20的可用空间小于该预设阈值时，触发前景垃圾回收操作。该空闲空间阈值可以根据存储装置20的总容量的百分比来设定，例如当可用空间低于总容量的10％时触发垃圾回收。

在另一实施例中，存储器控制器210根据写入请求的数据量与当前可用空间的比较结果来决定是否执行前景垃圾回收。当存储器控制器210接收到主机系统10的写入请求时，计算所需写入的数据量，并与当前可用空间进行比较。如果当前可用空间不足以容纳待写入的数据，则启动前景垃圾回收操作。

在又一实施例中，存储器控制器210通过评估虚拟块的状态分布来判断是否需要执行垃圾回收。具体地，存储器控制器210统计预回收状态为第四预回收状态(最大状态值)的虚拟块数量，当该数量超过预设阈值时，表明存在较多需要回收的块，此时触发前景垃圾回收操作。

在又一实施例中，存储器控制器210通过监控存储装置20的写入性能来判断是否需要执行垃圾回收。当检测到写入速度低于预期性能阈值时，可能表明存储空间碎片化严重，此时触发前景垃圾回收操作以整理存储空间。

存储器控制器210还可以根据不同的触发条件，调整垃圾回收的策略，例如在紧急情况下优先回收预回收状态值较大的虚拟块，以快速释放存储空间。

接着，存储器控制器210将处理分为两个并行执行的分支：

在步骤S730中，存储器控制器210执行所述主机写入指令，将主机系统10发送的数据写入到存储装置20中的有效存储空间。

同时，在步骤S740中，存储器控制器210执行前景垃圾回收操作。具体地，存储器控制器210首先获取所选的垃圾回收虚拟块的有效数据位图。然后，存储器控制器210扫描该有效数据位图中的所有比特，识别出值为第一值(e.g.,"1")的多个第一比特，这些第一比特表示对应的数据区域中存储的是有效数据。

存储器控制器210根据识别出的多个第一比特，定位垃圾回收虚拟块中对应这些第一比特的多个第一数据区域。随后，存储器控制器210将这些第一数据区域中的有效数据依次复制到预先分配的数据块中。

在数据复制过程中，存储器控制器210可以同时更新相应的逻辑到物理映射表，将这些有效数据的新物理地址记录到映射表中。

完成有效数据的复制后，存储器控制器210对该垃圾回收虚拟块执行擦除操作，将其恢复为可用状态。此时，该虚拟块中的所有存储单元被重置为预设值，可以用于后续的数据写入操作。对应的虚拟块映射表、逻辑到物理索引清单、虚拟块预回收状态表都会跟着更新/重置。

通过这种方式，存储器控制器210能够在执行主机写入指令的同时，高效地完成垃圾回收操作，有效提升了存储装置20的整体性能。特别是在存储装置20接近写满状态时，这种基于预回收状态的垃圾回收方法能够快速释放存储空间，确保主机写入操作的顺利进行。

最后，本实施例还提供一种计算机程序产品，包括计算机可读代码，或者承载有计算机可读代码的非易失性计算机可读存储介质，当所述计算机可读代码在主机系统的处理器中运行时，处理器执行上述存储器管理方法的流程步骤且实现存储器控制器的功能。该计算机程序产品可以具体通过硬件、固件、软件或其结合的方式实现。在一个可选实施例中，所述计算机程序产品具体体现为计算机存储介质，在另一个可选实施例中，计算机程序产品具体体现为软件产品，例如软件开发包(Software Development Kit，SDK)等等。

基于上述，本公开实施例所提供的存储器管理方法及存储器控制器，可以实现以下技术效果：

第一，本公开采用虚拟块预回收状态分级机制，根据有效计数将虚拟块划分为不同的预回收状态，并在存储装置空闲时预先更新高优先级虚拟块的有效数据位图。这种预处理机制显着减少了前景垃圾回收时的映射表查询开销，提升了垃圾回收效率。

第二，本公开设计了多层次的垃圾回收触发机制，通过监控存储装置的可用空间、写入负载、块状态分布等多个维度的指标，实现了对垃圾回收操作的精确控制。这种机制能够在适当的时机启动前景垃圾回收，既确保了存储空间的及时释放，又避免了不必要的垃圾回收操作。

第三，本公开通过逻辑到物理索引清单机制，建立了虚拟块与其相关联的逻辑到物理映射表之间的快速索引关系。这种设计显着降低了在更新有效数据位图时查找映射表的开销，提高了位图更新的效率。

第四，本公开在执行前景垃圾回收时，优先选择具有最大预回收状态值的虚拟块进行处理，并基于有效数据位图快速识别和复制有效数据。这种方法最大程度地减少了数据迁移量，提高了垃圾回收的速度。

综上所述，本公开提供的存储器管理方法显着提升了存储装置在高负载情况下的性能表现，尤其适用于需要频繁进行数据写入的应用场景。通过预先更新有效数据位图并结合预回收状态分级机制，本方案有效解决了传统前景垃圾回收效率低下的问题，提高了存储装置的整体运行效率。

最后应说明的是：以上各实施例仅用以说明本公开的技术方案，而非对其限制；尽管参照前述各实施例对本公开进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本公开各实施例技术方案的范围。

Claims (20)

1.一种存储器管理方法，适用于配置有可复写式非易失性存储器模块的存储装置，其特征在于，所述方法包括：

获取多个虚拟块各自的有效计数，其中每个虚拟块包括所述可复写式非易失性存储器模块的一或多个物理块；

根据所述每个虚拟块的有效计数，获取每个虚拟块的预回收状态；

根据所述每个虚拟块的所述预回收状态，决定每个虚拟块的有效数据位图的更新顺序；以及

根据每个虚拟块的所述有效数据位图的所述更新顺序，从所述多个虚拟块中选择目标虚拟块，以利用对应所述目标虚拟块的逻辑到物理索引清单和对应所述逻辑到物理索引清单的逻辑到物理映射表来更新所述目标虚拟块的目标有效数据位图。

2.根据权利要求1所述的存储器管理方法，其特征在于，还包括：

根据所述每个虚拟块的所述预回收状态，决定每个虚拟块的垃圾回收顺序。

3.根据权利要求1所述的存储器管理方法，其特征在于，获取每个虚拟块的所述预回收状态的步骤包括：

根据每个虚拟块的所述有效计数，比较每个虚拟块的所述有效计数及不同大小的多个阈值，以决定每个虚拟块的所述有效计数所位于的阈值区间；

根据每个虚拟块的所述阈值区间，决定每个虚拟块的所述预回收状态，

若一个虚拟块的所述有效计数大于所述多个阈值中的最大阈值，决定所述一个虚拟块的所述预回收状态为最小的所述预回收状态；

若一个虚拟块的所述有效计数小于所述多个阈值中的最小阈值，决定所述一个虚拟块的所述预回收状态为最大的所述预回收状态；

其中对应最小的所述预回收状态的第一虚拟块被判定不需要更新所对应的第一有效数据位图，并且对应最大的所述预回收状态的第二虚拟块被判定需要优先更新所对应的第二有效数据位图。

4.根据权利要求3所述的存储器管理方法，其特征在于，所述多个阈值的数量为3，所述预回收状态包括第一预回收状态、第二预回收状态、第三预回收状态和第四预回收状态，

其中所述第一预回收状态对应的有效计数大于第一阈值，

所述第二预回收状态对应的有效计数大于第二阈值且小于所述第一阈值，

所述第三预回收状态对应的有效计数大于第三阈值且小于所述第二阈值，

所述第四预回收状态对应的有效计数小于所述第三阈值，其中所述第一阈值为所述最大阈值，所述第三阈值为所述最小阈值，所述第一阈值大于所述第二阈值，并且所述第二阈值大于所述第三阈值。

5.根据权利要求1所述的存储器管理方法，其特征在于，所述逻辑到物理索引清单用于记录与所对应的虚拟块关联的一或多个逻辑到物理映射表的识别码，其中所对应的所述虚拟块所存储的有效数据的物理地址会被记录在所述一或多个逻辑到物理映射表的其中之一。

6.根据权利要求1所述的存储器管理方法，其特征在于，所述有效数据位图包括多个比特，每个所述比特对应所述虚拟块中一预设大小的数据区域，用于指示所述数据区域中的数据是否为有效数据。

7.根据权利要求6所述的存储器管理方法，其特征在于，所述方法还包括：

在所述存储装置处于空闲期间时更新所述目标虚拟块，

其中更新所述目标虚拟块的所述目标有效数据位图的步骤包括：

通过所述目标虚拟块的所述逻辑到物理索引清单确定与所述目标虚拟块关联的一或多个目标逻辑到物理映射表；

检查所述目标虚拟块的每个数据区域的物理地址是否存在于所述一或多个目标逻辑到物理映射表；以及

根据每个数据区域的检查结果更新所述目标有效数据位图的所述多个比特，其中完成更新的所述目标有效数据位图被存储到所述可复写式非易失性存储器模块。

8.根据权利要求7所述的存储器管理方法，其特征在于，更新所述目标有效数据位图的所述多个比特的步骤包括：

若所述目标虚拟块的第一数据区域的第一物理地址存在于所述一或多个目标逻辑到物理映射表的其中之一，将所述目标有效数据位图的所述多个比特中对应所述第一数据区域的第一比特设置为第一值；以及

若所述目标虚拟块的第二数据区域的第二物理地址不存在于任一所述一或多个目标逻辑到物理映射表，将所述目标有效数据位图的所述多个比特中对应所述第二数据区域的第二比特设置为第二值。

9.根据权利要求2所述的存储器管理方法，其特征在于，决定每个虚拟块的所述垃圾回收顺序包括：

在于主机写入操作期间执行前景垃圾回收时，优先选择具有最大的所述预回收状态的虚拟块作为垃圾回收虚拟块进行垃圾回收；以及

其次选择具有次大的所述预回收状态的虚拟块作为所述垃圾回收虚拟块进行垃圾回收。

10.根据权利要求9所述的存储器管理方法，其特征在于，执行垃圾回收的步骤包括：

获取所选的所述垃圾回收虚拟块的所述有效数据位图；

根据所选虚拟块的所述有效数据位图中的多个第一比特，将所述垃圾回收虚拟块中对应所述多个第一比特的多个第一数据区域各自的第一数据复制到数据块；以及

对所述垃圾回收虚拟块执行擦除操作。

11.一种存储器控制器，用于控制配置有可复写式非易失性存储器模块的存储装置，其特征在于，所述存储器控制器包括：

存储器接口控制电路，用以电性连接至所述可复写式非易失性存储器模块；

数据管理电路，电性连接至所述存储装置的连接接口电路，用以经由所述连接接口电路从主机系统接收数据及指令；

缓冲存储器，用以缓存数据；以及

处理器，电性连接至所述存储器接口控制电路、所述数据管理电路及所述缓冲存储器，其中所述处理器被配置以：

获取多个虚拟块各自的有效计数，其中每个所述虚拟块包括所述可复写式非易失性存储器模块的一或多个物理块；

根据所述每个虚拟块的有效计数，获取每个虚拟块的预回收状态；

根据所述每个虚拟块的所述预回收状态，决定每个虚拟块的有效数据位图的更新顺序；以及

根据每个虚拟块的所述有效数据位图的所述更新顺序，从所述多个虚拟块中选择目标虚拟块，以利用对应所述目标虚拟块的逻辑到物理索引清单和对应所述逻辑到物理索引清单的逻辑到物理映射表来更新所述目标虚拟块的目标有效数据位图。

12.根据权利要求11所述的存储器控制器，其特征在于，所述处理器还被配置以：

根据所述每个虚拟块的所述预回收状态，决定每个虚拟块的垃圾回收顺序。

13.根据权利要求11所述的存储器控制器，其特征在于，在获取每个虚拟块的所述预回收状态时，所述处理器被配置以：

根据每个虚拟块的所述有效计数，比较每个虚拟块的所述有效计数及不同大小的多个阈值，以决定每个虚拟块的所述有效计数所位于的阈值区间；

根据每个虚拟块的所述阈值区间，决定每个虚拟块的所述预回收状态，

若一个虚拟块的所述有效计数大于所述多个阈值中的最大阈值，决定所述一个虚拟块的所述预回收状态为最小的所述预回收状态；

若一个虚拟块的所述有效计数小于所述多个阈值中的最小阈值，决定所述一个虚拟块的所述预回收状态为最大的所述预回收状态；

其中对应最小的所述预回收状态的第一虚拟块被判定不需要更新所对应的第一有效数据位图，并且对应最大的所述预回收状态的第二虚拟块被判定需要优先更新所对应的第二有效数据位图。

14.根据权利要求13所述的存储器控制器，其特征在于，所述多个阈值的数量为3，所述预回收状态包括第一预回收状态、第二预回收状态、第三预回收状态和第四预回收状态，

其中所述第一预回收状态对应的有效计数大于第一阈值，

所述第二预回收状态对应的有效计数大于第二阈值且小于所述第一阈值，

所述第三预回收状态对应的有效计数大于第三阈值且小于所述第二阈值，

所述第四预回收状态对应的有效计数小于所述第三阈值，其中所述第一阈值为所述最大阈值，所述第三阈值为所述最小阈值，所述第一阈值大于所述第二阈值，并且所述第二阈值大于所述第三阈值。

15.根据权利要求11所述的存储器控制器，其特征在于，所述逻辑到物理索引清单用于记录与所对应的虚拟块关联的一或多个逻辑到物理映射表的识别码，其中所对应的所述虚拟块所存储的有效数据的物理地址会被记录在所述一或多个逻辑到物理映射表的其中之一。

16.根据权利要求11所述的存储器控制器，其特征在于，所述有效数据位图包括多个比特，每个所述比特对应所述虚拟块中一预设大小的数据区域，用于指示所述数据区域中的数据是否为有效数据。

17.根据权利要求16所述的存储器控制器，其特征在于，所述处理器还被配置以

在所述存储装置处于空闲期间时更新所述目标虚拟块，

其中更新所述目标虚拟块的所述目标有效数据位图的步骤包括：

通过所述目标虚拟块的所述逻辑到物理索引清单确定与所述目标虚拟块关联的一或多个目标逻辑到物理映射表；

检查所述目标虚拟块的每个数据区域的物理地址是否存在于所述一或多个目标逻辑到物理映射表；以及

根据每个数据区域的检查结果更新所述目标有效数据位图的所述多个比特，其中完成更新的所述目标有效数据位图被存储到所述可复写式非易失性存储器模块。

18.根据权利要求17所述的存储器控制器，其特征在于，在更新所述目标有效数据位图的所述多个比特时，所述处理器被配置以：

若所述目标虚拟块的第一数据区域的第一物理地址存在于所述一或多个目标逻辑到物理映射表的其中之一，将所述目标有效数据位图的所述多个比特中对应所述第一数据区域的第一比特设置为第一值；以及

若所述目标虚拟块的第二数据区域的第二物理地址不存在于任一所述一或多个目标逻辑到物理映射表，将所述目标有效数据位图的所述多个比特中对应所述第二数据区域的第二比特设置为第二值。

19.根据权利要求12所述的存储器控制器，其特征在于，在决定每个虚拟块的所述垃圾回收顺序时，所述处理器被配置以：

在于主机写入操作期间执行前景垃圾回收时，优先选择具有最大的所述预回收状态的虚拟块作为垃圾回收虚拟块进行垃圾回收；以及

其次选择具有次大的所述预回收状态的虚拟块作为所述垃圾回收虚拟块进行垃圾回收。

20.根据权利要求19所述的存储器控制器，其特征在于，在执行垃圾回收时，所述处理器被配置以：

获取所选的所述垃圾回收虚拟块的所述有效数据位图；

根据所选虚拟块的所述有效数据位图中的多个第一比特，将所述垃圾回收虚拟块中对应所述多个第一比特的多个第一数据区域各自的第一数据复制到数据块；以及

对所述垃圾回收虚拟块执行擦除操作。