CN110515858B

CN110515858B - Memory management method and memory controller

Info

Publication number: CN110515858B
Application number: CN201810494040.4A
Authority: CN
Inventors: 萧又华; 谢宏志; 方子维
Original assignee: Shenzhen Daxin Electronic Technology Co ltd
Current assignee: Shenzhen Daxin Electronic Technology Co ltd
Priority date: 2018-05-22
Filing date: 2018-05-22
Publication date: 2023-09-05
Anticipated expiration: 2038-05-22
Also published as: CN110515858A

Abstract

The invention provides a memory management method and a memory controller suitable for a memory device provided with a rewritable nonvolatile memory module. The rewritable nonvolatile memory module has a plurality of physical blocks divided into a plurality of block strings. The method comprises the following steps: scanning the plurality of physical blocks to identify one or more bad physical blocks of the plurality of physical blocks; calculating a plurality of effective weight values respectively corresponding to the plurality of block strings according to a plurality of data access time parameters, a plurality of effective data count values and the identified one or more bad physical blocks of the rewritable nonvolatile memory module; and selecting a target block string from the plurality of block strings according to the plurality of valid weight values to perform garbage collection operations.

Description

Memory management method and memory controller

Technical Field

The present invention relates to a memory management method, and more particularly, to a memory management method and a memory controller suitable for a memory device configured with a rewritable nonvolatile memory module.

Background

Generally, when the spare space of the rewritable nonvolatile memory module is insufficient, the controller of the rewritable nonvolatile memory module performs a garbage collection operation on the block string of the rewritable nonvolatile memory module to free up the available space of the block string.

However, in the case of the rewritable nonvolatile memory module having bad physical blocks, the block strings having bad physical blocks may release less available space through the garbage collection operation than the block strings not having bad physical blocks.

Therefore, how to consider the existence of bad physical blocks to select proper block strings for performing garbage collection operation, thereby improving the efficiency and the release space of garbage collection operation is one of the subjects of the study of the person skilled in the art.

Disclosure of Invention

The invention provides a memory management method and a memory controller suitable for a memory device provided with a rewritable nonvolatile memory module, which can consider the existence of bad physical blocks to select a block string for executing garbage collection operation, thereby increasing the effect of the garbage collection operation.

An embodiment of the invention provides a memory management method, which is suitable for a memory device configured with a rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module has a plurality of physical blocks, the plurality of physical blocks are divided into a plurality of Block strings, and the plurality of Block strings (Block strings) are arranged according to a first order. The method comprises the following steps: scanning the plurality of physical blocks to identify one or more bad physical blocks of the plurality of physical blocks; identifying a plurality of valid data count values each corresponding to the plurality of block strings; calculating a plurality of effective weight values respectively corresponding to the plurality of block strings according to a plurality of data access time parameters of the rewritable nonvolatile memory module, the plurality of effective data count values and the identified positions of the one or more bad physical blocks; and selecting a target valid weight value from the plurality of valid weight values, and performing garbage collection operation on a target block string corresponding to the target valid weight value from the plurality of block strings.

An embodiment of the present invention provides a memory controller for controlling a memory device configured with a rewritable nonvolatile memory module. The memory controller includes: the memory comprises a connection interface circuit, a memory interface control circuit, a block string management circuit unit and a processor. The connection interface circuit is used for being electrically connected to the host system. The memory interface control circuit is electrically connected to the rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module is provided with a plurality of physical blocks, the physical blocks are divided into a plurality of Block strings, and the Block strings (Block strings) are arranged according to a first sequence. The block string management circuit unit is configured to scan the plurality of physical blocks to identify one or more bad physical blocks among the plurality of physical blocks, wherein the block string management circuit unit is further configured to identify a plurality of valid data count values each corresponding to the plurality of block strings, wherein the block string management circuit unit is further configured to calculate a plurality of valid weight values each corresponding to the plurality of block strings according to a plurality of data access time parameters of the rewritable non-volatile memory module, the plurality of valid data count values, and the identified positions of the one or more bad physical blocks, wherein the block string management circuit unit is further configured to select a target valid weight value from the plurality of valid weight values, and perform a garbage collection operation on a target block string corresponding to the target valid weight value among the plurality of block strings.

Based on the above, the memory management method and the memory controller provided by the embodiments of the present invention can scan and identify bad physical blocks, calculate a plurality of effective weight values corresponding to a plurality of block strings according to a plurality of data access time parameters of the rewritable nonvolatile memory module, the plurality of effective data count values and the identified positions of the one or more bad physical blocks, so as to select a target block string of the plurality of block strings according to the plurality of effective weight values to execute garbage collection operation, and further select a more appropriate block string capable of releasing more space under the condition of considering bad physical blocks, so that the efficiency of garbage collection operation is increased.

In order to make the above features and advantages of the present invention more comprehensible, embodiments accompanied with figures are described in detail below.

Drawings

FIG. 1 is a block diagram of a host system and a storage device according to an embodiment of the invention.

FIG. 2 is a flow chart of a memory management method according to an embodiment of the invention.

FIG. 3 is a schematic diagram of a plurality of block strings of a rewritable nonvolatile memory module according to an embodiment of the present invention.

Fig. 4 is a schematic diagram of a bad physical block according to an embodiment of the invention.

Description of the reference numerals

10: host system

20: storage device

110. 211: processor and method for controlling the same

120: host memory

130: data transmission interface circuit

210: memory controller

212: data management circuit

213: memory interface control circuit

214: error checking and correcting circuit

215: block string management circuit unit

2151: bad block scanning circuit

2152: effective weight calculation circuit

216: buffer memory

217: power management circuit

220: rewritable nonvolatile memory module

230: connection interface circuit

S21, S23, S25, S27: flow steps of memory management method

D1: packaging

LUN1: logical number

P1 (1) to P1 (6), P1 (M-1), P2 (1) to P2 (6), P2 (M-1), P2 (M), P3 (1) to P3 (6), P3 (M-1), P3 (M), P4 (1) to P4 (6), P4 (M-1), P4 (M): physical block

P1 to P4: plane surface

BS (1) to BS (6), BS (M-1), BS (M): block string

Detailed Description

In this embodiment, the storage device includes a rewritable nonvolatile memory module (rewritable non-volatile memory module) and a storage device controller (also referred to as a storage controller or a storage control circuit). In addition, the storage device is used with a host system so that the host system can write data to or read data from the storage device.

Referring to fig. 1, a Host System (Host System) 10 includes a Processor (Processor) 110, a Host Memory (Host Memory) 120, and a data transfer interface circuit (Data Transfer Interface Circuit) 130. In the present embodiment, the data transmission interface circuit 130 is electrically connected (also referred to as an electrical connection) to the processor 110 and the host memory 120. In another embodiment, the processor 110, the host memory 120 and the data transmission interface circuit 130 are electrically connected to each other by a System Bus (System Bus).

The memory device 20 includes a memory controller (Storage Controller) 210, a Rewritable nonvolatile memory module (Rewritable Non-Volatile Memory Module) 220, and a connection interface circuit (Connection Interface Circuit) 230. The memory controller 210 includes a processor 211, a data management circuit (Data Management Circuit) 212, and a memory interface control circuit (Memory Interface Control Circuit) 213.

In the present embodiment, the host system 10 is electrically connected to the storage device 20 through the data transmission interface circuit 130 and the connection interface circuit 230 of the storage device 20 to perform data access operation. For example, the host system 10 may store data to the storage device 20 or read data from the storage device 20 via the data transfer interface circuit 130.

In the present embodiment, the processor 110, the host memory 120 and the data transmission interface circuit 130 may be disposed on a motherboard of the host system 10. The number of data transmission interface circuits 130 may be one or more. The motherboard can be electrically connected to the memory device 20 through a wired or wireless manner via the data transmission interface circuit 130. The storage device 20 may be, for example, a USB flash drive, a memory card, a solid state disk (Solid State Drive, SSD), or a wireless memory storage device. The wireless memory storage device may be, for example, a near field communication (Near Field Communication, NFC) memory storage device, a wireless facsimile (WiFi) memory storage device, a Bluetooth (Bluetooth) memory storage device, or a Bluetooth low energy memory storage device (e.g., iBeacon) or the like based on a variety of wireless communication technologies. In addition, the motherboard may also be electrically connected to various I/O devices such as a global positioning system (Global Positioning System, GPS) module, a network interface card, a wireless transmission device, a keyboard, a screen, and a speaker through a system bus.

In the present embodiment, the data transmission interface circuit 130 and the connection interface circuit 230 are interface circuits compatible with the high-speed peripheral component connection interface (Peripheral Component Interconnect Express, PCI Express) standard. The data transmission interface circuit 130 and the connection interface circuit 230 use the rapid nonvolatile memory interface standard (Non-Volatile Memory express, NVMe) protocol to transmit data.

However, it should be understood that the present invention is not limited thereto, and the data transmission interface circuit 130 and the connection interface circuit 230 may also be a parallel advanced technology attachment (Parallel Advanced Technology Attachment, PATA) standard, an institute of electrical and electronics engineers (Institute of Electrical and Electronic Engineers, IEEE) 1394 standard, a serial advanced technology attachment (Serial Advanced Technology Attachment, SATA) standard, a universal serial bus (Universal Serial Bus, USB) standard, an SD interface standard, an Ultra High Speed-I (UHS-I) interface standard, an Ultra High Speed second-II (UHS-II) interface standard, a Memory Stick (Memory Stick, MS) interface standard, a Multi-Chip Package (Multi-Chip Package) interface standard, a multimedia Card (MMC) interface standard, an eMMC interface standard, a universal flash Memory (Universal Flash Storage, UFS) interface standard, an ehfcinterface standard, a CF interface standard, an integrated drive electronics interface (Integrated Device Electronics, IDE) standard, or other suitable standards. In addition, in another embodiment, the connection interface circuit 230 may be packaged with the memory controller 210 in a chip, or the connection interface circuit 230 may be disposed outside a chip including the memory controller 210.

In the present embodiment, the host memory 120 is used for temporarily storing instructions or data executed by the processor 110. For example, in the present exemplary embodiment, the host memory 120 may be a dynamic random access memory (Dynamic Random Access Memory, DRAM), a static random access memory (Static Random Access Memory, SRAM), or the like. However, it should be understood that the present invention is not limited thereto and that host memory 120 may be other suitable memory.

The memory controller 210 is configured to execute a plurality of logic gates or control instructions implemented in hardware or firmware and perform operations such as writing, reading and erasing data in the rewritable nonvolatile memory module 220 according to the instructions of the host system 10.

In more detail, the processor 211 in the memory controller 210 is hardware with operation capability, which is used to control the overall operation of the memory controller 210. Specifically, the processor 211 has a plurality of control instructions, and when the memory device 20 is operated, the control instructions are executed to perform operations such as writing, reading and erasing data.

It should be noted that, in the present embodiment, the processor 110 and the processor 211 are, for example, a central processing unit (Central Processing Unit, CPU), a Microprocessor (micro-processor), or other programmable processing units (micro processor), a digital signal processor (Digital Signal Processor, DSP), a programmable controller, an application specific integrated circuit (Application Specific Integrated Circuits, ASIC), a programmable logic device (Programmable Logic Device, PLD), or other similar circuit elements, which are not limited to this embodiment.

In one embodiment, the memory controller 210 also has read-only memory (not shown) and random access memory (not shown). In particular, the rom has a boot code (boot code), and when the memory controller 210 is enabled, the processor 211 executes the boot code to load the control instructions stored in the rewritable nonvolatile memory module 220 into the ram of the memory controller 210. The processor 211 then runs the control commands to perform data writing, reading and erasing operations. In another embodiment, the control instructions of the processor 211 may also be stored in a program code format in a specific area of the rewritable nonvolatile memory module 220, for example, in a physical memory unit dedicated to storing system data in the rewritable nonvolatile memory module 220.

In the present embodiment, as described above, the memory controller 210 further includes the data management circuit 212 and the memory interface control circuit 213. It should be noted that the operations performed by the various components of the memory controller 210 may also be considered operations performed by the memory controller 210.

The data management circuit 212 is electrically connected to the processor 211, the memory interface control circuit 213 and the connection interface circuit 230. The data management circuit 212 is configured to receive the instruction from the processor 211 to transmit data. For example, data is read from the host system 10 (e.g., host memory 120) via the connection interface circuit 230, and the read data is written into the rewritable nonvolatile memory module 220 via the memory interface control circuit 213 (e.g., write operations are performed according to write instructions from the host system 10). For another example, data is read from one or more physical units of the rewritable nonvolatile memory module 220 via the memory interface control circuit 213 (data may be read from one or more memory units in the one or more physical units) and the read data is written into the host system 10 (e.g., the host memory 120) via the connection interface circuit 230 (e.g., a read operation is performed according to a read instruction from the host system 10). In another embodiment, the data management circuit 212 may also be integrated into the processor 211.

The memory interface control circuit 213 is used for receiving the instruction of the processor 211, and performs a write (also called Programming) operation, a read operation or an erase operation on the rewritable nonvolatile memory module 220 in cooperation with the data management circuit 212.

For example, the processor 211 may execute a sequence of write instructions to instruct the memory interface control circuit 213 to write data into the rewritable non-volatile memory module 220; the processor 211 may execute a sequence of read instructions to instruct the memory interface control circuit 213 to read data from one or more physical units of the rewritable non-volatile memory module 220 that correspond to the read instructions; the processor 211 may execute an erase command sequence to instruct the memory interface control circuit 213 to perform an erase operation on the rewritable nonvolatile memory module 220. The write command sequence, the read command sequence, and the erase command sequence may each include one or more program codes or command codes and are used to instruct the rewritable nonvolatile memory module 220 to perform corresponding writing, reading, and erasing operations. In an embodiment, the memory interface control circuit 213 may also perform corresponding operations (e.g., bad block scan operations, wear leveling operations, garbage collection operations, etc.) on the rewritable nonvolatile memory module 220 according to other received instruction sequences. These instruction sequences may include one or more signals, or data, on a bus. Such signals or data may include instruction code or program code. For example, the read instruction sequence may include information such as a read identification code and a memory address; the write command sequence includes information such as a logical address to be written, write data, and a write mode to be used (e.g., a single-plane write mode or a multi-plane write mode).

In addition, the data to be written into the rewritable nonvolatile memory module 220 is converted into a format acceptable to the rewritable nonvolatile memory module 220 by the memory interface control circuit 213.

The rewritable nonvolatile memory module 220 is electrically connected to the memory controller 210 (the memory interface control circuit 213) and is used for storing data written by the host system 10. The rewritable nonvolatile memory module 220 may be a single-Level memory Cell (Single Level Cell, SLC) NAND type flash memory module (i.e., a flash memory module that can store 1 bit in one memory Cell), a Multi-Level memory Cell (MLC) NAND type flash memory module (i.e., a flash memory module that can store 2 bits in one memory Cell), a third-Level memory Cell (Triple Level Cell, TLC) NAND type flash memory module (i.e., a flash memory module that can store 3 bits in one memory Cell), a fourth-Level memory Cell (Quadruple Level Cell, QLC) NAND type flash memory module (i.e., a flash memory module that can store 4 bits in one memory Cell), a three-dimensional NAND type flash memory module (3D NAND flash memory module) or a vertical NAND type flash memory module (Vertical NAND flash memory module), or other flash memory modules having the same characteristics. The memory cells in the rewritable nonvolatile memory module 220 are arranged in an array.

In this embodiment, the rewritable nonvolatile memory module 220 has a plurality of word lines, wherein each of the plurality of word lines includes a plurality of memory cells. Multiple memory cells on the same word line may constitute one or more physical programming units (physical pages). In addition, a plurality of physical program units can form a physical unit (physical block or physical erase unit). In the present embodiment, a three-level memory cell (Triple Level Cell, TLC) NAND type flash memory module is taken as an example, that is, in the following embodiments, a memory cell capable of storing 3 bit values is taken as a physical programming unit (that is, in each programming operation, a programming voltage is applied to one physical programming unit and then one physical programming unit to program data), where each memory cell can be divided into a lower physical page (Lower Physical Page), a middle physical page (Middle Physical Page) and an upper physical page (Upper Physical Page) each capable of storing one bit value.

In the present embodiment, the memory cell is the minimum unit for writing (programming) data. The physical cells are the smallest unit of erase, i.e., each physical cell contains one of the smallest number of erased memory cells. Each physical unit may have a plurality of memory cells.

In the following embodiments, one physical block is taken as an example of one physical unit. However, in another embodiment, a physical unit may refer to any number of memory units, depending on the physical requirements. Furthermore, it should be understood that when the processor 211 groups memory cells (or physical cells/physical blocks) in the rewritable nonvolatile memory module 220 to perform corresponding management operations, the memory cells (or physical cells) are logically grouped without changing their actual locations.

The memory controller 210 may configure a plurality of logic units for the rewritable nonvolatile memory module 220. The host system 10 accesses user data stored in a plurality of physical units through a configured logical unit. Here, each logical unit may be composed of one or more logical addresses. For example, the Logical unit may be a Logical Block (Logical Block), a Logical Page (Logical Page), or a Logical Sector (Logical Sector). A logical unit may be mapped to one or more physical units, where a physical unit may be one or more physical addresses, one or more physical sectors, one or more physical program units, or one or more physical erase units. In this embodiment, the logic unit is a logic block, and the logic subunit is a logic page. Each logic unit has a plurality of logic subunits.

In addition, the memory controller 210 establishes a logical-to-physical address mapping table (Logical To Physical address mapping table) and a physical-to-logical address mapping table (Physical To Logical address mapping table) to record the mapping relationship between the logical units (e.g., logical blocks, logical pages, or logical sectors) and the physical units (e.g., physical erase units, physical program units, physical sectors) allocated to the rewritable nonvolatile memory module 220. In other words, the storage controller 210 may look up a physical unit mapped by a logical unit through the logical-to-physical address mapping table, and the storage controller 210 may look up a logical unit mapped by a physical unit through the physical-to-logical address mapping table. However, the above technical concept related to mapping between logical units and physical units is a common technical means for those skilled in the art, and will not be described herein.

In the present embodiment, the error checking and correcting circuit 214 is electrically connected to the processor 211 and is used for performing an error checking and correcting procedure to ensure the correctness of the data. Specifically, when the processor 211 receives a write command from the host system 10, the error checking and correcting circuit 508 generates a corresponding error correction code (error correcting code, ECC) and/or error checking code (error detecting code, EDC) for the data corresponding to the write command, and the processor 211 writes the data corresponding to the write command and the corresponding error correction code and/or error checking code into the rewritable nonvolatile memory module 220. Then, when the processor 211 reads data from the rewritable nonvolatile memory module 220, the error correction code and/or the error check code corresponding to the data are read at the same time, and the error check and correction circuit 214 performs an error check and correction procedure on the read data according to the error correction code and/or the error check code. In addition, after the error checking and correcting process, if the read data is successfully decoded, the error checking and correcting circuit 214 may return the error bit value to the processor 211.

In one embodiment, the memory controller 210 further includes a buffer memory 216 and a power management circuit 217. The buffer memory is electrically connected to the processor 211 and is used for temporarily storing data and instructions from the host system 10, data from the rewritable nonvolatile memory module 220 or other system data for managing the memory device 20, so that the processor 211 can quickly access the data, instructions or system data from the buffer memory 216. The power management circuit 217 is electrically connected to the processor 211 and is used for controlling the power of the memory device 20.

In the present embodiment, the block string management circuit unit 215 includes a bad block scanning circuit (Bad Block scanning circuits) 2151 and an effective weight calculating circuit (Effective weight calculating circuit) 2152. The block string management circuit unit 215 is configured to calculate an effective weight value of each block string according to the identified bad physical blocks, so that the processor 211 can select a target block string for performing garbage collection operation according to all the effective weight values of all the block strings. It should be noted that the operations performed by the respective components of the block string management circuit unit 215 may also be regarded as operations performed by the block string management circuit unit 215.

The following describes the method of selecting/determining the block string (also referred to as the target block string) for performing garbage collection operation and the details of the memory management method, the memory controller and the block string management circuit unit 215 according to the present embodiment in conjunction with fig. 2, 3 and 4.

FIG. 2 is a flow chart of a memory management method according to an embodiment of the invention. It should be noted that the memory management method shown in fig. 2 may also be referred to as garbage collection block string selection method (Garbage Collection Block Stripe Selection Method). Referring to fig. 1 and 2, in step S21, the block string management circuit unit 215 scans a plurality of physical blocks to identify one or more bad physical blocks among the plurality of physical blocks, wherein the plurality of physical blocks are divided into a plurality of block strings. Specifically, in the present embodiment, the processor 211 may perform one of the following operations: (1) When the storage device 20 is idle (i.e., the storage device 20 is idle beyond a predetermined time threshold); (2) when the storage device is powered on; or (3) when the number of error bits of the data read from a physical block exceeds a threshold value of the number of error bits, the bad block scanning circuit 2151 in the block string management circuit unit 215 is instructed to perform a bad physical block scanning operation, which scans all or a specific (e.g., the physical block corresponding to the condition (3)) physical block to determine whether the scanned physical block is a bad physical block. In addition, the bad block scanning circuit 2151 can identify the physical address (or identification code) and the total number of physical blocks determined to be bad physical blocks. In another embodiment, the processor 211 may select a physical block with a poor physical state (e.g. a physical block with a high erasure count or a high error bit count) as the scanned physical block according to one or a combination of the statistics of all physical blocks and the error bit count. In one embodiment, the processor 211 may also randomly select the target physical block to perform the bad physical block scanning operation. The details of the bad physical block scanning operation are technical means commonly used by those skilled in the art, and are not described herein. That is, after performing the bad physical block scanning operation, the processor 211 or the bad block scanning circuit 2151 can know whether each block string has a bad physical block. If a block string has one or more bad physical blocks, the processor 211 or the bad block scanning circuit 2151 also knows the positions and numbers of the one or more bad physical blocks of the block string.

In addition, in another embodiment, the processor 211 may determine that the physical block corresponding to the specific event is a bad physical block according to the specific event in real time during the operation of the storage device 20.

In this embodiment, the processor 211 or the block string management circuit unit 215 can record the position and the number of the identified bad physical blocks by using a table (e.g. a bad physical block table or a block string management table). The concept of a block string is explained below with reference to fig. 3.

FIG. 3 is a schematic diagram of a plurality of block strings of a rewritable nonvolatile memory module according to an embodiment of the present invention. Referring to fig. 3 in more detail, the rewritable nonvolatile memory module 220 may have a plurality of packages (pages), each package may have a plurality of physical blocks, the plurality of physical blocks may be divided into N planes, and part or all of the planes may be logically divided into one logical number (Logical unit number, LUN). For simplicity of explanation, it is assumed that the rewritable nonvolatile memory module 220 has one package D1, and the package D1 has a plurality of physical blocks. The plurality of physical blocks are divided (grouped) into 4 planes (planes) P1 to P4 (N is equal to 4), wherein the 4 planes are divided into one logical number LUN 1. In addition, each plane has M physical units ordered according to the first order, for example, plane P1 has M physical blocks P1 (1) to P1 (M); the plane P2 is provided with M physical blocks P2 (1) to P2 (M); the plane P2 has M physical blocks P3 (1) to P3 (M); the plane P4 has M physical blocks P4 (1) to P4 (M). In this embodiment, physical blocks with the same rank in each plane are formed into a Block string (Block Stripe). For example, the block string BS (1) includes a physical block P1 (1), a physical block P2 (1), a physical block P3 (1), and a physical block P4 (1). That is, all the physical blocks in the 4 planes may constitute M block strings BS (1) to BS (M) arranged according to the first order.

In the present embodiment, the garbage collection operation performed by the memory controller 210 is performed in units of one block string. More specifically, when the processor 211 is to perform the garbage collection operation, the processor 211 first selects/determines a block string (also referred to as a target block string) for performing the garbage collection operation from all the block strings BS (1) to BS (M). Next, the processor 211 identifies the location (physical address) of the valid data and the location (physical address) of the bad physical block of the target block string, copies all the valid data to other physical blocks, and performs the erase operation on the normal physical blocks (physical blocks other than the bad physical blocks) of the target block string. Since the above-mentioned "the position (physical address) of the effective data of the target block string and the position (physical address) of the bad physical block" copy all the effective data to other physical blocks, and perform the garbage collection operation of the erase operation on the normal physical block (the physical block other than the bad physical block) of the target block string "is a technical means well known to those skilled in the art, and will not be described herein again. However, it should be noted that the spirit of the present invention is how to improve the manner of selecting/determining the appropriate target block strings to reduce the negative impact of bad physical blocks. That is, the above-described method of selecting/determining a target block string for performing garbage collection operation from among all the block strings BS (1) to BS (M) is improved.

Fig. 4 is a schematic diagram of a bad physical block according to an embodiment of the invention. For convenience of explanation, it is assumed that M is 6, that is, each plane has 6 physical blocks arranged according to the first order, and one logical number LUN has 6 block strings BS (1) to BS (6) in total. Further, assume that the bad block scanning circuit 2151 recognizes bad physical blocks P1 (1), P1 (3), P2 (3), P3 (4), P4 (3), P4 (5) (e.g., gray-scale blocks) through the performed bad physical block scanning operation. Referring to fig. 4, as described above, the number of normal physical blocks in the block strings BS (1), BS (3), BS (4), BS (5) is smaller than the number of normal physical blocks in the block strings BS (2), BS (6). In other words, if the processor 211 performs garbage collection operation on all the block strings BS (1) to BS (6), the space released by one of the block strings BS (1), BS (3), BS (4) and BS (5) is smaller than the space released by one of the block strings BS (2) and BS (6). That is, the effect of performing garbage collection operation on the block strings BS (2), BS (6) is greater than that of performing garbage collection on the block strings BS (1), BS (3), BS (4), BS (5).

Referring back to fig. 2, in step S23, the processor 211 identifies a plurality of valid data count values corresponding to the plurality of block strings. The valid data count value of each block string is a quotient obtained by dividing the total amount (total size) of all the valid data stored in the block string by a predetermined unit size. In the present embodiment, the predetermined unit is set as one physical page, but the present invention is not limited thereto. For example, in other embodiments, the predetermined unit may be set to the size of more than two physical pages. For another example, in other embodiments, the predetermined unit may be set to other kinds of unit sizes (e.g., one or more codewords, one or more word lines, a plurality of sectors, a physical block size may be set to the predetermined unit size).

Specifically, the processor 211 or the block string management circuit 215 records a Valid Data Count value (Valid Data Count) of each block string. For example, each time a new stored write data updates the data stored in the physical block of one block string, the processor 211 or the block string management circuit unit 215 identifies the size of the updated data, divides the size by a predetermined unit to obtain a quotient value, and subtracts the quotient value from the effective data count value of the current one block string to reflect the fact that the amount of effective data stored in this virtual block string is reduced. It should be noted that, for convenience of description, the following example uses "one physical page" as a predetermined unit.

For example, for convenience of explanation, it is assumed that each physical block has 6 physical pages, each logical block has 6 logical pages, and the size of the logical pages is equal to the physical pages. In addition, it is also assumed that all physical blocks of the block string BS (2) are already full of valid data, and the valid data count value of the block string BS (2) is 24 (the quotient obtained by dividing the valid data of 24 physical page sizes by 1 physical page size is 24). The processor 211 can know that the size of the effective data currently stored in the 4 physical blocks (total 24 physical pages) of the block string BS (2) is the size of the total 24 physical pages according to the current effective data count value "24" of the block string BS (2).

In this example, it is assumed that the processor 211 is currently writing a write data (new data) of 6 physical pages into a first logic block. This first logical block originally has stored old data and is mapped to physical block P1 (2) (i.e., the old data stored in the first logical block is actually written to the 2 nd physical block of plane P1). The processor 211 writes new data to an idle physical block (e.g., the physical block P4 (6) is the idle physical block and is written with the new data), maps the first logical block to the physical block P4 (6), and regards the old data of the physical block P1 (2) as invalid data to complete the write operation of storing the new data to the first logical block (the data of the first logical block is updated by the new data). Next, the processor 211 recognizes the total size of the old data, which becomes invalid data, calculates a quotient (e.g., 6/1=6) obtained by dividing the total size of the old data by the size of a predetermined unit, and subtracts the quotient from the valid data count value of the block string BS (2), i.e., the valid data count value of the block string BS (2) becomes 18 (i.e., 24-6=18) after the writing operation of the new data is completed. The processor 211 may know that the size of the valid data currently stored in the block string BS (2) is 18 physical pages according to the current valid data count value "18" of the block string BS (2).

On the other hand, when a physical block is written with new valid data, the valid data count value of the block string of the physical block is increased corresponding to the size of the new valid data.

Continuing with the above example, it is assumed that only physical block P4 (6) of block string BS (6) is blank, i.e., physical block P4 (6) is an idle physical block, before writing new data. Further, it is assumed that the effective data count value of the block string BS (6) at this time is 18. In this case, the processor 211 can know that 3 physical blocks P1 (6), P2 (6), P3 (6) of the block string BS (6) are each full of valid data (18/3=6) having a size of 6 physical pages. After the writing operation of the new data is completed, the physical block P4 (6) is filled with the new data, and the processor 211 or the block string management circuit unit 215 adds 6 to the effective data count value of the block string BS (6), i.e. the new effective data count value of the block string BS (6) is 24.

In this embodiment, after all physical units of a block string have stored data, the processor 211 or the block string management circuit 215 records the valid data count value of the block string.

Referring back to fig. 2, in step S25, the block string management circuit unit 215 is configured to calculate a plurality of valid weight values corresponding to the plurality of block strings according to a plurality of data access time parameters of the rewritable nonvolatile memory module, the plurality of valid data count values and the identified positions of the one or more bad physical blocks.

In this embodiment, the plurality of data access time parameters include a write unit time, a read unit time, a block string erase time, and a system operation time. The write unit time is used to represent the time taken to complete a write operation of writing data of the predetermined unit size to the rewritable nonvolatile memory module. The read unit time is used to represent the time taken to complete a read operation of reading data of the predetermined unit size from the rewritable nonvolatile memory module. The block string erase time is used to represent the time taken to complete all erase operations performed on all normal physical blocks of a block string of the rewritable non-volatile memory module, wherein the one physical block has a size of one or more predetermined units. The system operation time is used to represent the time taken to complete multiple system operations performed on a string of blocks. The system operations include (1) reading a physical-to-logical address mapping table corresponding to the ith block string, and (2) identifying physical addresses of all valid data of the ith block string.

In more detail, in the first embodiment, in the operation of the block string management circuit unit 215 for calculating the plurality of valid weight values corresponding to the plurality of block strings according to the plurality of data access time parameters, the plurality of valid data count values and the identified one or more bad physical blocks of the rewritable nonvolatile memory module (assuming that the valid weight value of the first block string of the plurality of block strings is currently calculated), the block string management circuit unit 215 (e.g., the valid weight calculation circuit 2152) identifies one or more normal physical blocks existing in the first block string according to the identified one or more bad physical blocks. Then, the block string management circuit unit 215 divides the size of the available space released through the erase operation performed on the one or more normal physical blocks of the first block string by the quotient of the predetermined unit as a first release amount; and the block string management circuit unit 215 calculates a first processing time corresponding to the first block string according to the first effective count value and the plurality of data access time parameters, wherein a first effective weight value corresponding to the first block string among the plurality of effective weight values comprises a quotient value obtained by dividing the first processing time by the first release amount, and the quotient value is taken as a first time efficiency ratio of the first block string. More specifically, the block string management circuit unit 215 (e.g., the effective weight calculation circuit 2152) is configured to calculate the effective weight value of the i-th block string of the plurality of block strings via the following formula (F1):

In formula (F1), tert is used to refer to the time efficiency ratio of the i-th block string of the plurality of block strings. Vi is used to refer to the valid data count value of the ith block string. tR is used to refer to the time taken to complete a read operation (also referred to as a read unit time) to read valid data of the predetermined unit size from the rewritable nonvolatile memory module. tW is used to refer to the time taken to complete a write operation (also referred to as a write unit time) of writing valid data of the predetermined unit size to the rewritable nonvolatile memory module. tE is used to refer to the time taken to complete the erase operation (also referred to as erase unit time) performed on all normal physical blocks of the ith block string, and tC is used to refer to the time taken to complete the plurality of system operations performed on the ith block string. EPi is used to refer to the release amount of the ith block string (e.g., a first release amount for a first block string). That is, the processing time of one burst (e.g., the first processing time of the first burst) is calculated by the numerator to the right of the equal sign in the formula (F1), i.e., the operation formula (vi×tr+vi×tw+te+tc), and the denominator to the right of the equal sign in the formula (F1) is the release amount of one burst. In other words, the time efficiency ratio of one block string (e.g., the first time efficiency ratio of the first block string) is a quotient obtained by dividing the processing time of one block string by the release amount of one block string.

In a first embodiment, the effective weight value of the ith block string is equal to (set to) the time efficiency ratio of the ith block string (e.g., a first effective weight value of a first block string is equal to a first time efficiency ratio). However, the present invention is not limited thereto. The effective weight value of a string of blocks may be set to the time efficiency ratio of the string of blocks plus a particular value.

For example, in the second embodiment, the effective weight value of the i-th block string is equal to (set to) the time efficiency ratio of the i-th block string plus a sum obtained by a delay parameter corresponding to the i-th block string (e.g., a first effective weight value of a first block string is equal to a first time efficiency ratio plus a first delay parameter corresponding to the first block string).

Specifically, when the garbage collection operation performed on a block string (e.g., a first block string) is completed, the block string management circuit unit 215 sets the value of the first delay parameter to a predetermined delay value, and subtracts one from the delay parameter of the other block strings; and the block string management circuit unit 215 decrements the first delay parameter by one when another block string other than the first block string of the plurality of block strings is subjected to the garbage collection operation. The predetermined delay value is a positive integer set according to manufacturer's requirements. In other words, the effective weight of a block string is characterized by the addition of a "delay parameter" mechanism: after the garbage collection operation is performed, the effective weight value becomes a larger value, and the effective weight value is gradually reduced according to the number of garbage collection operations performed by other block strings.

More specifically, in an embodiment, the block string management circuit unit 215 (e.g., the effective weight calculation circuit 2152) is further configured to calculate the effective weight value of the i-th block string of the plurality of block strings via the following formula (F2):

W _i ＝R _i +TER _i (F2)

in the formula (F2), tert is used to refer to the time efficiency ratio of the i-th block string of the plurality of block strings, which is calculated as in the formula (F1) in the first embodiment described above. Wi is used to refer to the effective weight value of an ith block string of the plurality of block strings, and Ri is used to refer to the delay parameter of the ith block string.

It should be noted that the block string management circuit unit 215 updates the valid weight value of each block string according to the data access or system operation performed by the storage device 20 in real time, and the block string management circuit unit 215 (e.g., the valid weight calculation circuit 2152) records the valid weight value. For example, when the effective data count value of one block string is changed, or when one block string is subjected to garbage collection operation, the effective weight value of the one block string is changed, and the changed effective weight value is recorded/updated.

Referring back to fig. 2, after calculating (updating) the valid weight value of each block string, the block string management circuit unit 215 selects a target valid weight value from the valid weight values, and performs garbage collection operation on a target block string corresponding to the target valid weight value from the block strings.

Specifically, in the above operation of the block string management circuit unit 215 selecting the target valid weight value from the valid weight values, the block string management circuit unit 215 compares the valid weight values with a garbage collection weight threshold value. Next, the block string management circuit unit 215 uses, as the target valid weight value, a valid weight value among the plurality of valid weight values that is smaller than the garbage collection weight threshold value.

That is, the valid weight of the target block string selected to perform the garbage collection operation may be less than the garbage collection weight. If the number of the target block strings is multiple, the target block strings are arranged into a garbage collection block string sequence from small to large according to the size sequence of the target effective weight values of the target block strings, and the target block strings arranged at the forefront in the garbage collection block string sequence are subjected to garbage collection operation first.

In other words, when the processor 211 determines that it is currently necessary to perform a garbage collection operation to free up space, the processor 211 selects a block string having the smallest valid weight value according to the established garbage collection block string sequence to perform the garbage collection operation.

It should be noted that, the negative effect caused by the bad physical block can be solved by using the effective weight value obtained in the first embodiment. For example, referring to fig. 4, assume that the number of physical pages of each physical block is 256; the block strings BS (1) and BS (2) are both full of valid data; the number of valid data of the burst BS (1) is 768 (e.g., 256×3) and the release amount is 768 (e.g., 256×3), and the number of valid data of the burst BS (1) is 1024 (e.g., 256×4) and the release amount is 1024 (e.g., 256×4). From equation (F1), it can be known that the effective weight value (i.e., the time efficiency ratio) of the block string BS (1) will be greater than the effective weight value of the block string BS (2) (because the denominator "1024" of the time efficiency ratio of the block string BS (2) is much greater than the denominator "768" of the time efficiency ratio of the block string BS (1)). Therefore, the block string BS (2) is also selected as the target block string to perform garbage collection operation as compared to the block string BS (1). In other words, the block string selected to perform the garbage collection operation is a block string with fewer bad physical blocks through the memory management method provided in the above embodiment.

On the other hand, with the effective weight value obtained in the above second embodiment, the phenomenon that the "block string is frequently subjected to garbage collection operation" due to excessively frequent updating of data can also be solved. Specifically, as described above, the effective weight value becomes a large value after the garbage collection operation is performed. Therefore, when the next garbage collection operation is to be performed, the effective weight value of the block string just after the garbage collection operation is performed is not selected as the target block string because of the newly set larger delay parameter, so that the phenomenon that one block string performs the garbage collection operation excessively frequently is avoided. In this way, the negative effects of excessively wearing out a block string due to excessively frequent garbage collection operations performed on the block string can be avoided.

In summary, the memory management method and the memory controller provided by the embodiments of the present invention can scan and identify bad physical blocks, perform bad physical block remapping operation on the identified bad physical blocks to update the virtual block string management table, and perform write operation according to the virtual block string management table via the multi-plane write mode, so as to generate more virtual block strings to which the multi-plane write mode can be applied, thereby increasing the data access efficiency and the space of the memory device.

Although the invention has been described with reference to the above embodiments, it should be understood that the invention is not limited thereto, but rather may be modified or altered somewhat by persons skilled in the art without departing from the spirit and scope of the invention.

Claims

1. A memory management method, adapted for a storage device configured with a rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module has a plurality of physical blocks, wherein the plurality of physical blocks are divided into a plurality of block strings, and the plurality of block strings are arranged according to a first order, the method comprising:

scanning the plurality of physical blocks to identify one or more bad physical blocks of the plurality of physical blocks;

identifying a plurality of valid data count values each corresponding to the plurality of block strings;

calculating a plurality of effective weight values respectively corresponding to the plurality of block strings according to a plurality of data access time parameters of the rewritable nonvolatile memory module, the plurality of effective data count values and the identified positions of the one or more bad physical blocks; and

Selecting a target valid weight value from the plurality of valid weight values, and performing garbage collection operation on a target block string corresponding to the target valid weight value from the plurality of block strings,

wherein a first effective data count value of a first block string corresponding to the plurality of block strings among the plurality of effective data count values is a quotient obtained by dividing a total amount of effective data stored by all first physical blocks of the first block string by a predetermined unit size,

wherein the plurality of data access time parameters includes:

a write unit time to represent a time taken to complete a write operation of writing data of the predetermined unit size to the rewritable nonvolatile memory module;

a read unit time to represent a time taken to complete a read operation of reading data of the predetermined unit size from the rewritable nonvolatile memory module;

a block string erase time representing a time taken to complete all erase operations performed on all normal physical blocks of a block string of the rewritable non-volatile memory module, wherein the one physical block has a size of one or more predetermined units; and

The system operation time is used to represent the time taken to complete the system operations performed on a block string.

2. The memory management method according to claim 1, wherein the selecting the target valid weight value from the plurality of valid weight values includes:

comparing the plurality of effective weight values with a garbage collection weight threshold value; and

and taking the effective weight value smaller than the garbage collection weight threshold value in the effective weight values as the target effective weight value.

3. The memory management method of claim 1, wherein calculating the plurality of valid weight values that each correspond to the plurality of strings of blocks from the plurality of data access time parameters, the plurality of valid data count values, and the locations of the identified one or more bad physical blocks of the rewritable nonvolatile memory module comprises:

identifying one or more normal physical blocks present in the first block string according to the identified one or more bad physical blocks, wherein the one or more normal physical blocks do not belong to the one or more bad physical blocks;

dividing the size of the available space released by the erase operation performed on the one or more normal physical blocks of the first block string by a quotient of the predetermined unit as a first release amount; and

Calculating a first processing time corresponding to the first block string according to the first effective data count value and the plurality of data access time parameters, wherein a first effective weight value corresponding to the first block string in the plurality of effective weight values comprises a quotient value obtained by dividing the first processing time by the first release amount, and the quotient value is taken as a first time efficiency ratio of the first block string.

4. The memory management method of claim 3, wherein the effective weight value for each of the plurality of strings of blocks is computable via the following first formula:

where TERI is used to refer to the time efficiency ratio of an ith block string of the plurality of block strings, vi is used to refer to the effective data count value of the ith block string, tR is used to refer to the time taken to complete a read operation of reading effective data of the predetermined unit size from the rewritable non-volatile memory module, tW is used to refer to the time taken to complete a write operation of writing effective data of the predetermined unit size to the rewritable non-volatile memory module, tE is used to refer to the time taken to complete all erase operations performed on all normal physical blocks of the ith block string, tC is used to refer to the time taken to complete a plurality of system operations performed on the ith block string, and EPi is used to refer to the release amount of the ith block string, wherein the plurality of system operations include (1) reading a physical-to-logical address mapping table corresponding to the ith block string, and (2) identifying all physical addresses of the ith block string,

Wherein the first processing time is obtained via calculating a numerator of the first formula and the first release amount is obtained via calculating a denominator of the first formula, wherein the effective weight value of the i-th block string is equal to the time efficiency ratio.

5. The memory management method of claim 3, wherein the first valid weight value of the plurality of valid weight values corresponding to the first block string is a sum of the quotient obtained by dividing the first processing time by the first release amount plus a first delay parameter, the method further comprising:

when the garbage collection operation performed on the first block string is completed, the value of the first delay parameter is set to a predetermined delay value, and the delay parameters of the other block strings are subtracted by one; and

the first delay parameter is decremented by one when another one of the plurality of block strings other than the first block string is performed the garbage collection operation.

6. The memory management method of claim 5 wherein the effective weight value for each of the plurality of strings of blocks is computable via the following second formula:

Wi＝R i+TER i

Where Wi is used to refer to the effective weight value of an i-th block string of the plurality of block strings, and Ri is used to refer to the delay parameter of the i-th block string.

7. A memory controller for controlling a memory device configured with a rewritable non-volatile memory module, the memory controller comprising:

the connection interface circuit is used for being electrically connected to the host system;

the memory interface control circuit is used for being electrically connected to the rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module is provided with a plurality of physical blocks, the physical blocks are divided into a plurality of block strings, and the block strings are arranged according to a first sequence;

a block string management circuit unit; and

a processor electrically connected to the connection interface circuit, the memory interface control circuit and the block string management circuit unit,

wherein the block string management circuit unit is used for scanning the plurality of physical blocks to identify one or more bad physical blocks in the plurality of physical blocks,

wherein the block string management circuit unit is further configured to identify a plurality of valid data count values corresponding to the plurality of block strings respectively,

Wherein the block string management circuit unit is further configured to calculate a plurality of valid weight values corresponding to the plurality of block strings respectively according to a plurality of data access time parameters of the rewritable nonvolatile memory module, the plurality of valid data count values and the identified positions of the one or more bad physical blocks,

wherein the block string management circuit unit is further configured to select a target valid weight value from the plurality of valid weight values, and perform a garbage collection operation on a target block string corresponding to the target valid weight value from the plurality of block strings,

wherein the plurality of data access time parameters includes:

8. The memory controller of claim 7 wherein, in the operation wherein said block string management circuit unit is further configured to select said target valid weight value from said plurality of valid weight values,

the block string management circuit unit compares the plurality of effective weight values with a garbage collection weight threshold value; and

the block string management circuit unit takes the effective weight value which is smaller than the garbage collection weight threshold value in the effective weight values as the target effective weight value.

9. The memory controller of claim 7, wherein the block string management circuit unit is further configured to calculate the plurality of valid weight values corresponding to the plurality of block strings based on the plurality of data access time parameters of the rewritable nonvolatile memory module, the plurality of valid data count values, and the identified locations of the one or more bad physical blocks,

The block string management circuit unit identifies one or more normal physical blocks existing in the first block string according to the identified one or more bad physical blocks, wherein the one or more normal physical blocks do not belong to the one or more bad physical blocks;

the block string management circuit unit divides a size of an available space released through an erase operation performed on the one or more normal physical blocks of the first block string by a quotient of the predetermined unit as a first release amount; and

the block string management circuit unit calculates a first processing time corresponding to the first block string according to the first effective data count value and the plurality of data access time parameters, wherein a first effective weight value corresponding to the first block string in the plurality of effective weight values comprises a quotient value obtained by dividing the first processing time by the first release amount, and the quotient value is taken as a first time efficiency ratio of the first block string.

10. The memory controller of claim 9, wherein the block string management circuit unit is to calculate the effective weight value for each of the plurality of block strings via a first formula:

Where TERI is used to refer to the time efficiency ratio of an ith block string of the plurality of block strings, vi is used to refer to the effective data count value of the ith block string, tR is used to refer to the time taken to complete a read operation of reading effective data of the predetermined unit size from the rewritable non-volatile memory module, tW is used to refer to the time taken to complete a write operation of writing the effective data of the predetermined unit size to the rewritable non-volatile memory module, tE is used to refer to the time taken to complete all erase operations performed on all normal physical blocks of the ith block string, tC is used to refer to the time taken to complete a plurality of system operations performed on the ith block string, and EPi is used to refer to the release amount of the ith block string, wherein the plurality of system operations include (1) reading a physical-to-logical mapping table corresponding to the ith block string, and (2) identifying all physical addresses of the effective data of the ith block string

11. The memory controller of claim 9, wherein the first valid weight value of the plurality of valid weight values corresponding to the first string of blocks is a sum of the quotient obtained by dividing the first processing time by the first release amount plus a first delay parameter, wherein

When the garbage collection operation performed on the first block string is completed, the block string management circuit unit sets the value of the first delay parameter to a predetermined delay value, and subtracts one from the delay parameter of the other plurality of block strings; and

the block string management circuit unit subtracts one from the first delay parameter when another block string other than the first block string of the plurality of block strings is subjected to the garbage collection operation.

12. The memory controller of claim 11, wherein the block string management circuit unit is to calculate the effective weight value for each of the plurality of block strings via a second formula:

Wi＝R i+TER i