TWI740446B - Computer program product and method and apparatus for managing garbage collection (gc) processes - Google Patents

Abstract

A method for managing garbage collection (GC) processes, performed by a flash controller, is introduced to include: determining source blocks to be processed; programming user data of the source blocks’ valid pages whose page amount is less than a total amount of empty pages of a first-type physical block into empty pages of a second-type physical block, wherein the total amount of empty pages of the first-type physical block is greater than a total amount of empty pages of the second-type physical block; and filling the remaining empty pages of the second-type physical block with dummy values.

Description

Computer program product, method and device for managing garbage collection process

The invention relates to a storage device, in particular to a computer program product, method and device for managing garbage collection procedures.

Flash memory is generally divided into NOR flash memory and NAND flash memory. NOR flash memory is a random access device. The central processing unit (Host) can provide any address to access the NOR flash memory on the address pin, and obtain the data stored at that address from the data pin of the NOR flash memory in time material. On the contrary, NAND flash memory is not random access, but serial access. NAND flash memory cannot access any random address like NOR flash memory. Instead, the central processing unit needs to write the value of the sequence of bytes (Bytes) into the NAND flash memory to define the type of request command (Command) (such as , Read, write, erase, etc.), and the address used in this command. The address can point to a page (the smallest data block for a write operation in the flash memory) or a block (the smallest data block for an erase operation in the flash memory).

After multiple accesses, a physical block may contain valid and invalid pages (also called expired pages), where valid pages store valid user data, and invalid pages store invalid (old) user data. When the flash memory controller detects that the available space of the storage device is lower than the threshold, it can issue a read command to instruct the storage device to read and collect user data of valid pages in several physical blocks, and then issue a write command to instruct storage The device rewrites the collected valid user data to the empty physical page of the idle block or the active block, so that these data blocks containing invalid user data can be changed to idle blocks, which can be provided after erasing Data storage space. The procedure described above is called Garbage Collection (Garbage Collection, GC). However, poorly designed garbage collection procedures will affect the overall performance of the storage device. Therefore, the present invention provides a computer program product, method, and device for managing garbage collection procedures, which are used to optimize the execution time of garbage collection procedures.

In view of this, how to reduce or eliminate the deficiencies in the above-mentioned related fields is indeed a problem to be solved.

This manual relates to a computer program product used to manage garbage collection procedures, including program code loaded and executed by the processing unit of the flash memory controller: determine multiple source blocks to be processed; reduce the source blocks to be smaller than the first type of physical block The user data of the valid pages of the total number of empty pages is written into the empty pages in the second type of physical block; and the remaining empty pages in the second type of physical block are filled with false values.

This manual also relates to a garbage collection program management method, executed by the flash memory controller, including: determining multiple source blocks to be processed; writing user data of valid pages in the source blocks that are less than the total number of empty pages of the first type of physical block Inserting empty pages in the second type of physical block; and filling the remaining empty pages in the second type of physical block with false values.

This specification also relates to a garbage collection program management device, including: a flash memory interface; and a processing unit. The flash memory interface is coupled to the flash memory module, and the processing unit is coupled to the flash memory interface. The processing unit determines multiple source blocks to be processed in the flash memory module; the drive flash interface writes user data of valid pages in the source block that is less than the total number of empty pages in the first type of physical block into the empty pages in the second type of physical block ; And drive the flash memory interface to fill the remaining empty pages in the second type of physical block with false values.

Each source block contains at least one invalid page, and the total number of empty pages of the first type of physical block is greater than the total number of empty pages of the second type of physical block.

One of the advantages of the above-mentioned embodiment is that through the above-mentioned write operation, the resources and time required to close the physical block can be reduced, and the efficiency of executing the garbage collection procedure can be improved.

Other advantages of the present invention will be explained in more detail with the following description and drawings.

10: Electronic device

110: host side

130: flash memory controller

131: Host Interface

132: Bus

134: Processing Unit

136: Random Access Memory

138: Direct Memory Access Controller

139: Flash interface

150: Flash memory module

151: Interface

153#0~153#15: NAND flash memory unit

CH#0~CH#3: Channel

CE#0~CE#3: Enabling signal

310, 330: data plane

310#0~310#m,330#0~330#m: physical block

P#0~P#n: physical page

410#0~410#5: SLC block

430: TLC block

S510~S560: Method steps

610: SLC block

710#0~710#5: SLC block

730: TLC block

750: SLC block

FIG. 1 is a system architecture diagram of an electronic device according to an embodiment of the invention.

FIG. 2 is a schematic diagram of a flash memory module according to an embodiment of the invention.

FIG. 3 is a schematic diagram of a NAND flash memory cell according to an embodiment of the invention.

FIG. 4 is a schematic diagram of garbage collection according to some embodiments.

Fig. 5 is a flowchart of a method for writing a garbage collection program according to an embodiment of the present invention.

6 and 7 are schematic diagrams of garbage collection according to an embodiment of the present invention.

The following descriptions are preferred implementations for completing the invention, and their purpose is to describe the basic spirit of the invention, but not to limit the invention. The actual content of the invention must refer to the scope of the claims that follow.

It must be understood that the words "including" and "including" used in this specification are used to indicate the existence of specific technical features, values, method steps, operations, elements, and/or components, but they do not exclude the possibility of adding More technical features, values, method steps, job processing, components, components, or any combination of the above.

Words such as "first", "second", and "third" in the claims are used to modify the elements in the claims, not to indicate that there is a priority, prerequisite relationship, or an element Prior to another element, or the chronological order of execution of method steps, is only used to distinguish elements with the same name.

It must be understood that when an element is described as being “connected” or “coupled” to another element, it can be directly connected or coupled to other elements, and intervening elements may appear. Conversely, when an element is described as being "directly connected" or "directly coupled" to another element, there are no intervening elements. Other terms used to describe the relationship between elements can also be interpreted in a similar manner, such as "between" versus "directly between", or "adjacent" versus "directly adjacent" and so on.

Refer to Figure 1. The electronic device 10 includes a host side 110, a flash memory controller 130, and a flash memory module 150, and the flash memory controller 130 and the flash memory module 150 can be collectively referred to as a device End (Device Side). The electronic device 10 can be implemented in electronic products such as personal computers, laptop PCs, tablet computers, mobile phones, digital cameras, and digital cameras. The host interface (Host Interface) 137 of the host terminal 110 and the flash memory controller 130 can be universal serial bus (USB), advanced technology attachment (ATA), serial advanced technology attachment (serial advanced technology attachment, SATA), peripheral component interconnect express (PCI-E), universal flash storage (Universal Flash Storage UFS), embedded multimedia card (Embedded Multi-Media Card eMMC) and other communication protocols communicate with each other. The flash interface (Flash Interface) 139 of the flash memory controller 130 and the flash module 150 can communicate with each other through the Double DataRate DDR communication protocol, for example, Open NAND Flash Interface ONFI, double data Rate switch (DDR Toggle) or other communication protocols. The flash memory controller 130 includes a processing unit 134, which can be implemented in a variety of ways, such as using general-purpose hardware (for example, a single processor, multiple processors with parallel processing capabilities, graphics processors, or other processors with computing capabilities), and When executing software and/or firmware commands, it provides the functions described later. The processing unit 134 receives host commands, such as Read Command, Write Command, Erase Command, etc., through the host interface 131, schedules and executes these commands. The flash memory controller 130 further includes a random access memory (Random Access Memory, RAM) 136, which can be implemented as a dynamic random access memory (Dynamic Random Access Memory, DRAM) or a static random access memory (Static Random Access Memory, SRAM) or a combination of the above two, used to configure the space as a data buffer to store user data (also called host data) read from the host 110 and to be written to the flash memory module 150, and from the flash memory module The group 150 reads and will output the user data to the host terminal 110. The random access memory 136 can also store data needed during execution, such as variables, data tables, and host-to-flash comparison tables (Host-to-Flash, H2F). Table), Flash-to-Host (F2H Table), etc. The flash memory interface 139 includes a NAND Flash Controller (NFC), which provides functions required for accessing the flash memory module 150, such as Command Sequencer (Command Sequencer), Low Density Parity Check (LDPC) Wait.

The flash memory controller 130 can be configured with a bus architecture 132 for coupling components to transfer data, addresses, control signals, etc. These components include a host interface 131, a processing unit 134, RAM 136, Direct Memory Access (DMA) controller 138, flash memory interface 139, etc. In some embodiments, the host interface 131, the processing unit 134, the RAM 136, the DMA controller 138, and the flash memory interface 139 may be coupled to each other through a single bus. In other embodiments, a high-speed bus may be configured in the flash memory controller 130 for coupling the processing unit 134, the DMA controller 138, and the RAM 136 to each other, and a low-speed bus may be configured for the processing unit 134, DMA The controller 138, the host interface 131, and the flash memory interface 139 are coupled to each other. The DMA controller 138 can move data between components through the bus architecture 132 according to the instructions of the processing unit 134, for example, move data from a specific data buffer (Data Buffer) in the host interface 131 or the flash memory interface 139 to the RAM 136 The specific address is to move the data at the specific address in the RAM 136 to the specific data register in the host interface 131 or the flash memory interface 139, etc.

The bus bar includes parallel physical lines to connect more than two components in the flash memory controller 130. The bus is a shared transmission medium. At any time, only two devices can use these lines to communicate with each other for data transmission. Data and control signals can propagate in both directions along the data and control lines between components, but on the other hand, address signals can only propagate in one direction along the address line. For example, when the processing unit 134 wants to read data at a specific address of the RAM 136, the processing unit 134 transmits the address to the RAM 136 on the address line. Then, the data at this address will reply to the processing unit 134 on the data line. In order to complete the data reading operation, the control signal will be transmitted using the control line.

The flash memory module 150 provides a large amount of storage space, usually hundreds of gigabytes (GB), or even several terabytes (Terabytes, TB) for storing large amounts of user data. For example, high-resolution pictures, videos, etc. The flash memory module 150 includes a control circuit and a memory array. The memory cells in the memory array may include single level cells (SLCs), multiple level cells (MLCs) and triple level cells (Triple). Level Cells, TLCs), Quad-Level Cells (QLCs) or any combination of the above. The processing unit 134 writes user data to the designated address (destination address) in the flash memory module 150 through the flash memory interface 139, and reads the user data from the designated address (source address) in the flash memory module 150. The flash memory interface 139 uses several electronic signals to coordinate data and command transmission between the flash memory controller 130 and the flash memory module 150, including data lines, clock signals, and control signals. The data line can be used to transfer commands, addresses, read and write data; the control signal line can be used to transfer Chip Enable CE, Address Latch Enable ALE, and Command Extraction Enable ( Control signals such as Command Latch Enable CLE and Write Enable WE.

When each memory cell of a physical block is set as a single-layer cell and can record two states, a physical character line only stores a single page of user data. When each memory unit of a physical block is set as a multi-layer unit and can record four states, one physical character line can store two pages of user data, including the Most Significant Bit (MSB Page) ) And the Least Significant Bit page (LSB). When each memory cell of a physical block is set as a three-layer cell and can record eight states, one physical character line can store three pages of user data, including the most significant bit page and the middle effective bit page (Center Significant Bit, CSB Page) and the least significant bit page. When each memory cell of a physical block is set as a four-layer cell and can record 16 states, one physical word line can store except for the most significant bit page and the middle effective bit page In addition to the user data on the least significant bit page, it also includes storing the user data on the top significant bit page (TSB Page). The above-mentioned physical blocks of memory cells including SLC, MLC, TLC, and QLC can be regarded as different types of physical blocks.

Referring to FIG. 2, the interface 151 in the flash memory module 150 may include four I/O channels (hereinafter referred to as channels) CH#0 to CH#3, and each channel is connected to four NAND flash memory cells, for example, channels CH#0 is connected to NAND flash memory cells 153#0, 153#4, 153#8, and 153#12. Each NAND flash memory cell can be packaged as an independent die. The flash memory interface 139 can send one of the enabling signals CE#0 to CE#3 through the interface 151 to enable the NAND flash memory cells 153#0 to 153#3, 153#4 to 153#7, 153#8 to 153#11 , Or 153#12 to 153#15, then read user data from the enabled NAND flash memory cell in parallel, or write user data to the enabled NAND flash memory cell.

Each NAND flash memory cell may include multiple data planes, each data plane may include multiple physical blocks (Physical Blocks), and each physical block may include multiple physical pages (Physical Pages). Referring to the embodiment of FIG. 3, the NAND flash memory cell 153#0 includes two data planes 310 and 330. The data plane 310 includes physical blocks 310#0 to 310#m, and the data plane 330 includes physical blocks 330#0 to 330#m. Each physical block contains n+1 physical pages. NAND flash memory cells, physical blocks, and physical pages can be identified by Logical Block Number (LUN), Block Number, and Page Number, respectively, and any combination of the above numbers can be called a flash memory module The physical address of 150. Any physical block in each data plane can be set as an SLC, MLC, TLC or QLC block.

When the available storage space of the flash module 150 is less than the threshold, such as 1/2 of the physical block, 1/3 of the physical block, the flash controller 130 starts a garbage collection (Garbage Collection, GC) program to release invalid Storage space for the page. It should be noted here that the GC program is a program actively launched by the flash memory controller 130, and is not subject to the host side. 110 command to start. In some embodiments, the processing unit 134 may collect user data of valid pages of multiple SLC blocks (may be called source blocks), and then write the collected user data into the TLC block (may be called destination blocks). Empty page. After the source block is erased by the processing unit 134, storage space can be provided for user data received in the future. However, when the number of valid pages in the source block is less than the total number of pages in one TLC block, the remaining empty pages without user data need to be filled with false values to close the physical block (Close Block). Referring to FIG. 4, the processing unit 134 collects user data (represented by diagonal squares) of valid pages in SLC block 410#0 to 410#5, and writes the collected user data into the empty page in TLC block 430 ( Represented by a slashed square). Next, the processing unit 134 fills the remaining empty pages with dummy values (Dummy Values). Although the false value is useless, filling the false value is also a write operation, and the flash memory module 150 also takes the same time as writing user data to complete the operation.

In order to solve the problems of the above-mentioned embodiments, an embodiment of the present invention proposes a GC program management method, which is implemented when the processing unit 134 loads and executes related firmware or software instructions. Refer to Figure 5, the detailed steps are as follows:

Step S510: Determine the source block to be processed in the flash memory module 150. The processing unit 134 can select multiple physical blocks containing invalid pages as the source blocks. The source block can be an SLC, MLC, TLC, QLC block, or any combination of the above.

Step S520: Calculate the number of valid pages in the source block.

Step S530: Determine whether the number of valid pages is equal to or greater than the total number of pages in one TLC block. If so, the flow proceeds to the processing of step S540; otherwise, the flow proceeds to the processing of step S550.

Step S540: Write user data of ixN valid pages in the source block into at least one TLC block (also called destination block) in the flash memory module 150, ixN<M, i represents a positive integer greater than zero, and M represents a valid page Number, N represents the total number of pages in a TLC block. The processing unit 134 drives the flash memory interface 139 to complete the read operation of ixN valid pages in the multiple source blocks and the write operation of the TLC block.

Step S550: Write the user data of the remaining valid pages in the source block (the number of which is less than the total number of pages of one TLC block) into the empty page of at least one SLC block (also referred to as the destination block) in the flash memory module 150. It should be noted here that the number of remaining valid pages in the source block may exceed the total number of pages in one SLC block. The processing unit 134 drives the flash memory interface 139 to complete the read operation of the remaining valid pages in one or more source blocks and the write operation of one or more SLC blocks.

Step S560: Fill the remaining empty pages in the SLC block (destination block) in the flash memory module 150 with false values. It should be noted here that, since the writing operation of the TLC block uses Foggy-to-Fine (Foggy-to-Fine, F2F) technology, the complexity of the steps for writing data is higher than that of writing the SLC block, and its The time required is usually longer. In addition, since the total number of empty pages in the TLC block is more than the total number of empty pages in the SLC block, which is about three times the total number of empty pages in the SLC block, the total number of remaining empty pages in the TLC block is usually greater than the total number of remaining empty pages in the SLC block. .

In contrast to the use case shown in Figure 4, refer to Figure 6. Through the method described above, the processing unit 134 writes the collected user data (indicated by diagonal squares) of valid pages in the SLC block 410#0 to 410#5 into the empty pages (indicated by diagonal lines) in the SLC block 610. The square indicates), therefore, there are fewer false values that need to be filled in.

In addition, refer to another use case shown in Figure 7. The processing unit 134 collects the user data of the valid pages in the SLC block 710#0 to 710#5 (represented by the slashed box), and writes the collected user data to all pages in the TLC block 730 (represented by the slashed box) ), and write the remaining user data into the page in the SLC block 750 (represented by a diagonal square). Next, the processing unit 134 fills the remaining empty pages in the SLC block 750 with false values.

Although the effective page and the invalid page in each physical block shown in FIG. 6 and FIG. 7 are two continuous areas respectively, this is only a simplified expression for convenience of description. In fact, valid pages and invalid pages in each physical block are often interleaved with each other, and the present invention is not limited thereby. For example, the effective pages of a physical block are pages P#0~5, P#10~15, P#20~25 And P#30~35.

As described above, the GC program management method of the embodiment of the present invention can be appropriately modified and applied to the context of the QLC block. Step S530 can be modified to determine whether the number of valid pages is equal to or greater than the total number of pages in one QLC block. Step S540 can be modified to write user data of ixN valid pages in the source block of the flash memory module 150 into an empty page of at least one QLC block (also referred to as the destination block) in the flash memory module 150, ixN<M, i represents A positive integer greater than zero, M represents the number of valid pages, and N represents the total number of pages in a QLC block. Step S550 can be modified to write user data of the remaining valid pages (the number of which is less than the total number of pages of one QLC block) in the source block into the empty pages of at least one SLC block (also referred to as the destination block) in the flash memory module 150.

In one aspect of the present invention, the processing unit 134 determines multiple source blocks to be processed, wherein each source block contains at least one invalid page; The user data of the valid page is written into the empty page in the second type of physical block, wherein the total number of pages of a first type of physical block is higher than the total number of pages of a second type of physical block; and the remaining of the second type of physical block The empty page of is filled with false values to avoid spending too much time and resources to fill in false values. For example, the total number of pages of a first type physical block (such as a TLC or QLC block) is at least twice the total number of pages of a second type physical block (such as an SLC block). The total number of pages of a first-type physical block and the total number of pages of a second-type physical block refer to the maximum total number of empty pages used to store user data in a first-type physical block and a second-type physical block, respectively.

Therefore, compared with the previous embodiment, the judgment in step S530 and the writing operation in step S560 can reduce the resources and time required to close the physical block, and improve the efficiency of the garbage collection procedure.

All or part of the steps in the method of the present invention can be implemented by computer instructions, such as a firmware translation layer (FTL) in a storage device, a driver of a specific hardware, and the like. In addition, it can also be implemented in other types of programs. Technology Those with ordinary knowledge in the field can write the methods of the embodiments of the present invention into computer instructions, which will not be described for brevity. The computer instructions implemented according to the method of the embodiment of the present invention can be stored in an appropriate computer readable medium, such as DVD, CD-ROM, USB disk, hard disk, and can also be placed on a network (such as the Internet, or Other appropriate vehicles).

Although FIGS. 1 and 2 include the above-described elements, it is not excluded that, without violating the spirit of the invention, more other additional elements can be used to achieve better technical effects. In addition, although the flowchart in FIG. 5 is executed in a specified order, those skilled in the art can modify the order of these steps on the premise of achieving the same effect without violating the spirit of the invention. Therefore, the present invention does not It is not limited to using only the sequence described above. In addition, those skilled in the art can also integrate several steps into one step, or in addition to these steps, perform more steps sequentially or in parallel, and the present invention is not limited thereby.

Although the present invention is described using the above embodiments, it should be noted that these descriptions are not intended to limit the present invention. On the contrary, this invention covers modifications and similar arrangements that are obvious to those skilled in the art. Therefore, the scope of applied claims must be interpreted in the broadest way to include all obvious modifications and similar settings.

S510~S560: Method steps

Claims (13)

A computer program product for managing garbage collection procedures, including program codes loaded and executed by a processing unit of a flash memory controller, for determining multiple source blocks to be processed, wherein each of the above source blocks includes At least one invalid page; write user data of valid pages in the source block that is less than the total number of pages of a first type of physical block into an empty page in a second type of physical block, one of the pages of the first type of physical block The total number is greater than the total number of pages of one physical block of the second type; and the remaining empty pages in the physical block of the second type are filled with false values. The computer program product described in claim 1, including program code loaded and executed by the processing unit of the flash memory controller: calculating the number of valid pages in the source block; determining the number of valid pages in the source block Whether it is equal to or greater than the total number of pages of one physical block of the first type; when the number of valid pages in the source block is equal to or greater than the total number of pages of one physical block of the first type, the total number of ixN valid pages in the source block User data is written into at least one empty page in the first type physical block, ixN<M, i represents a positive integer greater than zero, x represents a multiplication operation, M represents the number of valid pages, and N represents an entity of the first type. The total number of pages in the block, and the user data of the remaining valid pages in the source block are written into the empty pages in the second type physical block; and when the number of valid pages in the source block is less than one first type entity When the total number of pages in the block is concerned, the user data of the valid page in the source block is written into the empty page in the second type physical block. The computer program product according to any one of Claims 1 to 2, wherein the total number of pages of one physical block of the first type is twice or more than the total number of pages of one physical block of the second type. The computer program product according to any one of claims 1 to 2, wherein the first type of physical block is a three-layered unit block or a four-layered unit block, and the second type of physical block is a single-layered unit block . The computer program product according to any one of claims 1 to 2, wherein each of the above-mentioned source blocks is a single-layer unit block. A garbage collection program management method, executed by a flash memory controller, includes: determining a plurality of source blocks to be processed, wherein each of the source blocks includes at least one invalid page; and reducing the source blocks to be less than one physical block of the first type The user data of the valid pages of the total number of pages is written into an empty page in a second type of physical block, where the total number of pages of one of the above-mentioned first type physical blocks is greater than the total number of pages of one of the above-mentioned second type physical blocks; and The remaining empty pages in the second type physical block are filled with false values. The garbage collection program management method according to claim 6, wherein the total number of pages of one physical block of the first type is twice or more than the total number of pages of one physical block of the second type. The garbage collection program management method according to claim 6, wherein the first type of physical block is a three-tiered unit block or a four-tiered unit block, and the second type of physical block is a single Layered unit block. A garbage collection program management device includes: a flash memory interface coupled to a flash memory module; and a processing unit coupled to the flash memory interface for determining a plurality of source blocks to be processed in the flash memory module, wherein each Each of the source blocks includes at least one invalid page; the flash memory interface is driven to write user data of valid pages that are less than the total number of pages of a first type physical block in the source block into a second type physical block of the flash memory module The total number of pages of one of the first type physical blocks is greater than the total number of pages of one of the second type physical blocks; and the flash memory interface is driven to fill the remaining empty pages in the second type of physical blocks with false values. The garbage collection program management device according to claim 9, wherein the processing unit calculates the number of valid pages in the source block; determines whether the number of valid pages in the source block is equal to or greater than one physical block of the first type When the number of effective pages in the source block is equal to or greater than the total number of pages in one physical block of the first type, the flash memory interface is driven to send users who have ixN effective pages in the source block in the flash memory module Data is written into at least one empty page in the first type physical block, ixN<M, i represents a positive integer greater than zero, x represents a multiplication operation, M represents the number of effective pages, and N represents one of the first type physical blocks. The total number of pages, the flash memory interface is driven to write the user data of the remaining valid pages in the source block of the flash memory module into the empty pages in the second type of physical block; and when the number of valid pages in the source block is less than one When the total number of pages of the first type of physical block, the flash memory interface is driven to write the user data of the valid page in the source block of the flash memory module into the empty page of the second type of physical block. The garbage collection program management device according to any one of claims 9 to 10, wherein: The total number of pages of one physical block of the first type is twice or more than the total number of pages of one physical block of the second type. The garbage collection program management device according to any one of claim 9 to 10, wherein the first type of physical block is a three-layered unit block or a four-layered unit block, and the second type of physical block is a single-layered unit block. Unit block. The garbage collection program management device according to any one of claims 9 to 10, wherein each of the above-mentioned source blocks is a single-layer unit block.

Images