ACCELERATING GARBAGE COLLECTION OF FLUSHED LOGICAL ERASE BLOCKS IN NON-VOLATILE MEMORY

• US 20190340121A1
• Filed: 05/02/2018
• Published: 11/07/2019
• Est. Priority Date: 05/02/2018
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: PLETKA, ROMAN A., PAPANDREOU, NIKOLAOS, TOMIC, SASA, IOANNOU, NIKOLAS
• Granted Patent: US 10,459,839 B1
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7211 Wear leveling
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A controller of a non-volatile memory tracks identifiers of logical erase blocks (LEBs) for which programming has closed. A first subset of the closed LEBs tracks LEBs that are ineligible for selection for garbage collection, and a second subset of the closed LEBs tracks LEBs that are eligible for selection for garbage collection. The controller continuously migrates closed LEBs from the first subset to the second subset over time. In response to closing a particular LEB, the controller places an identifier of the particular LEB into one of the first and second subsets selected based on a first amount of dummy data programmed into the closed LEBs tracked in the first subset. Thereafter, in response to selection of the particular LEB for garbage collection, the controller performs garbage collection on the particular LEB.

Claims

1. A method of garbage collection in a non-volatile memory, the method comprising:

a controller of the non-volatile memory tracking identifiers of closed logical erase blocks (LEBs) of non-volatile memory for which programming has closed until after the LEBs are erased, wherein the tracking includes tracking a first subset of the closed LEBs that are ineligible for selection for garbage collection and tracking a different second subset of the closed LEBs that are eligible for selection for garbage collection;

the controller continuously migrating closed LEBs from the first subset to the second subset over time;

in response to closing a particular LEB, the controller placing an identifier of the particular LEB into one of the first and second subsets selected based on a first amount of dummy data programmed into the closed LEBs tracked in the first subset; and

thereafter, in response to selection of the particular LEB for garbage collection, the controller performing garbage collection on the particular LEB.

2. The method of claim 1, wherein:

the tracking includes the controller tracking the first subset in a first data structure and tracking the second subset in a different second data structure.

3. The method of claim 1, wherein:

the placing includes placing the identifier of the particular LEB into the first subset based on both the first amount of dummy data and a second amount of dummy data in the particular LEB.

4. The method of claim 3, and further comprising the controller determining the second amount of dummy data in the particular LEB based on a number of consecutive physical pages containing no valid logical pages of data.

5. The method of claim 1, wherein:

the particular LEB comprises a first LEB;

the method further comprising;

the controller, responsive to closing programming of a second LEB containing less than a threshold amount of dummy data, placing an identifier of the second LEB into a third subset if no invalidation of a logical page of data in the second LEB has been performed; and

thereafter, the controller migrating the identifier of the second LEB from the third subset to the first subset in response to invalidation of a logical page of data in the second LEB.

6. The method of claim 1, and further comprising:

the controller programming the particular LEB with one or more physical pages of dummy data responsive to at least a predetermined number of reads being made to the particular LEB while the particular LEB is open for programming.

7. The method of claim 1, and further comprising the controller selecting LEBs for wear leveling from both the first subset and the second subset.

8. A data storage system, comprising:

a controller for a non-volatile memory, wherein the controller is configured to perform;

the controller tracking identifiers of closed logical erase blocks (LEBs) of the non-volatile memory for which programming has closed until after the LEBs are erased, wherein the tracking includes tracking a first subset of the closed LEBs that are ineligible for selection for garbage collection and tracking a different second subset of the closed LEBs that are eligible for selection for garbage collection;

the controller continuously migrating closed LEBs from the first subset to the second subset over time;

in response to closing a particular LEB, the controller placing an identifier of the particular LEB into one of the first and second subsets selected based on a first amount of dummy data programmed into the closed LEBs tracked in the first subset; and

thereafter, in response to selection of the particular LEB for garbage collection, the controller performing garbage collection on the particular LEB.

9. The data storage system of claim 8, wherein:

the tracking includes the controller tracking the first subset in a first data structure and tracking the second subset in a different second data structure.

10. The data storage system of claim 8, wherein:

the placing includes placing the identifier of the particular LEB into the first subset based on both the first amount of dummy data and a second amount of dummy data in the particular LEB.

11. The data storage system of claim 10, wherein the controller is further configured to perform:

the controller determining the second amount of dummy data in the particular LEB based on a number of consecutive physical pages containing no valid logical pages of data.

12. The data storage system of claim 8, wherein:

the particular LEB comprises a first LEB;

the controller is further configured to perform;

the controller, responsive to closing programming of a second LEB containing less than a threshold amount of dummy data, placing an identifier of the second LEB into a third subset if no invalidation of a logical page of data in the second LEB has been performed; and

thereafter, the controller migrating the identifier of the second LEB from the third subset to the first subset in response to invalidation of a logical page of data in the second LEB.

13. The data storage system of claim 8, wherein the controller is further configured to perform:

the controller programming the particular LEB with one or more physical pages of dummy data responsive to at least a predetermined number of reads being made to the particular LEB while the particular LEB is open for programming.

14. The data storage system of claim 8, wherein the controller is further configured to perform:

the controller selecting LEBs for wear leveling from both the first subset and the second subset.

15. The data storage system of claim 8, and further comprising the non-volatile memory.

16. A computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions being executable by a controller of a non-volatile memory to cause the controller to perform:

a controller of the non-volatile memory tracking identifiers of closed logical erase blocks (LEBs) of non-volatile memory for which programming has closed until after the LEBs are erased, wherein the tracking includes tracking a first subset of the closed LEBs that are ineligible for selection for garbage collection and tracking a different second subset of the closed LEBs that are eligible for selection for garbage collection;

the controller continuously migrating closed LEBs from the first subset to the second subset over time;

in response to closing a particular LEB, the controller placing an identifier of the particular LEB into one of the first and second subsets selected based on a first amount of dummy data programmed into the closed LEBs tracked in the first subset; and

thereafter, in response to selection of the particular LEB for garbage collection, the controller performing garbage collection on the particular LEB.

17. The computer program product of claim 16, wherein:

the tracking includes the controller tracking the first subset in a first data structure and tracking the second subset in a different second data structure.

18. The computer program product of claim 16, wherein:

the placing includes placing the identifier of the particular LEB into the first subset based on both the first amount of dummy data and a second amount of dummy data in the particular LEB.

19. The computer program product of claim 18, wherein the program instructions further cause the controller to perform:

the controller determining the second amount of dummy data in the particular LEB based on a number of consecutive physical pages containing no valid logical pages of data.

20. The computer program product of claim 16, wherein:

the particular LEB comprises a first LEB;

the program instructions further cause the controller to perform;

the controller, responsive to closing programming of a second LEB containing less than a threshold amount of dummy data, placing an identifier of the second LEB into a third subset if no invalidation of a logical page of data in the second LEB has been performed; and

thereafter, the controller migrating the identifier of the second LEB from the third subset to the first subset in response to invalidation of a logical page of data in the second LEB.