METHODS, DEVICES AND SYSTEMS FOR TWO STAGE POWER-ON MAP REBUILD WITH FREE SPACE ACCOUNTING IN A SOLID STATE DRIVE

• US 20140258588A1
• Filed: 03/05/2013
• Published: 09/11/2014
• Est. Priority Date: 03/05/2013
• Status: Active Grant

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: TOMLIN, ANDREW J., JONES, JUSTIN, MULLENDORE, RODNEY N.
• Granted Patent: US 9,454,474 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A data storage device comprises a non-volatile memory comprising a plurality of blocks, each configured to store a plurality of physical pages at predetermined physical locations. A controller programs and reads data stored in a plurality of logical pages. A volatile memory comprises a logical-to-physical address translation map configured to enabling determination of the physical location, within one or more physical pages, of the data stored in each logical page. A plurality of journals may be stored, each comprising a plurality of entries associating one or more physical pages to each logical page. At startup, the controller may read at least some of the plurality of journals in an order and rebuild the map; indicate a readiness to service data access commands after the map is rebuilt; rebuild a table from the map and, based thereon, select block(s) for garbage collection after having indicated the readiness to process the commands.

Claims

1. A data storage device controller configured to couple to a non-volatile memory comprising a plurality of blocks, each block being configured to store a plurality of physical pages at predetermined physical locations, the controller comprising:

a processor configured to program data to and read data from the non-volatile memory, the data being stored in a plurality of logical pages;

a volatile memory comprising a logical-to-physical address translation map configured to enable the processor to determine a physical location, within one or more physical pages, of the data stored in each logical page; and

a plurality of journals stored in the non-volatile memory, each journal comprising a plurality of journal entries associating one or more physical pages to each logical page,

wherein the controller is configured, upon startup, to;

read each of the plurality of journals in an order and to rebuild the map in the volatile memory from the read plurality of journals;

indicate a readiness to process data access commands after the map is rebuilt; and

rebuild a table from the map and select, based on the rebuilt table, at least one of the plurality of blocks for garbage collection after having indicated the readiness to process data access commands.

2. The data storage device controller of claim 1, wherein the table is configured to specify free space in each of the plurality of blocks.

3. The data storage device of claim 1, wherein the controller is configured to process a data access command as the table is being rebuilt.

4. The data storage device of claim 1, wherein the controller is configured to garbage collect as the table is being rebuilt.

5. The data storage device controller of claim 2, wherein each of the blocks has a predetermined size and wherein the processor is configured to calculate the amount of free space by subtracting a size of valid data in each block obtained from reading the map from the predetermined size.

6. The data storage device controller of claim 5, wherein the processor is further configured to read sequentially through the map to determine, for each block, a size of valid data and to update a valid size information table with the determined size of valid data.

7. The data storage device controller of claim 6, wherein the processor is further configured to carry out a separate free space accounting operation to update a free space for a block storing a logical page corresponding to an already read entry of the map that is updated after having indicated the readiness to service data access commands.

8. The data storage controller of claim 6, wherein the processor is further configured to refrain from carrying out a separate free space accounting operation to update a free space for a block storing a logical page corresponding to a yet-to-be-read entry of the map that is updated after having indicated the readiness to service data access commands.

9. The data storage device controller of claim 1, wherein the processor is further configured to build a journal map in the volatile memory as each of the plurality of journals is read, the journal map specifying a physical location in the non-volatile memory of each of the read journals.

10. The data storage device controller of claim 1, wherein the non-volatile memory comprises Multi-Level Cells (MLC) and wherein the processor is further configured to store each logical page in a non-volatile buffer at least until an upper page corresponding to a lower page of non-volatile memory where the logical page is stored has been programmed.

11. The data storage device controller of claim 10, wherein the processor is further configured to read logical pages stored in the non-volatile buffer and to rebuild the map using the logical pages read from the non-volatile buffer.

12. The data storage device controller of claim 1, wherein the non-volatile memory comprises Multi-Level Cells (MLC), wherein the non-volatile memory comprises a physical area comprising recently garbage-collected valid logical pages and wherein the processor is further configured to read journals corresponding to the physical area no further than entries thereof corresponding to safe logical pages stored in a lower page of non-volatile memory where the corresponding upper page has been programmed.

13. The data storage device controller of claim 12, wherein, for entries of journals corresponding to the physical area corresponding to unsafe logical pages stored in a lower page where the corresponding upper page has not been programmed, the processor is further configured to read journals associating one or more physical pages of a block from which the valid data was garbage collected.

14. A data storage device, comprising:

the non-volatile memory, and

the data storage device controller of claim 1.

15. A method of controlling a data storage device comprising a non-volatile memory comprising a plurality of blocks, each block being configured to store a plurality of physical pages at predetermined physical locations, the method comprising:

programming data to and reading data from the non-volatile memory, the data being stored in a plurality of logical pages;

maintaining, in a volatile memory, a logical-to-physical address translation map configured to enable a determination of a physical location, within one or more physical pages, of the data stored in each logical page; and

maintaining, in the non-volatile memory, a plurality of journals, each journal comprising a plurality of journal entries associating one or more physical pages to each logical page and, upon startup;

reading each of the plurality of journals in an order and rebuilding the map in the volatile memory from the read plurality of journals;

indicating a readiness to process data access commands after the map is rebuilt; and

rebuilding a table from the map and, based on the rebuilt table, selecting at least one of the plurality of blocks for garbage collection after having indicated the readiness to process data access commands.

16. The method of claim 15, wherein the table is configured to specify an amount of free space in each of the plurality of blocks.

17. The method of claim 15, further comprising processing a data access command as the table is being rebuilt.

18. The method of claim 15, further comprising garbage collecting as the table is being rebuilt.

19. The method of claim 16, wherein each of the blocks has a predetermined size and wherein the method further comprises calculating the amount of free space by subtracting a size of valid data in each block obtained from reading the map from the predetermined size.

20. The method of claim 19, further comprising reading sequentially through the map to determine, for each block, a size of valid data and updating a valid size information table with the determined size of valid data.

21. The method of claim 20, further comprising carrying out a separate free space accounting operation to update a free space for a block storing a logical page corresponding to an already read entry of the map that is updated after having indicated the readiness to service data access commands.

22. The method of claim 19, further comprising refraining from carrying out a separate free space accounting operation to update a free space for a block storing a logical page corresponding to a yet-to-be-read entry of the map that is updated after having indicated the readiness to service data access commands.

23. The method of claim 15, further comprising building a journal map in the volatile memory as each of the plurality of journals is read, the journal map specifying a physical location in the non-volatile memory of each of the read journals.

24. The method of claim 15, wherein the non-volatile memory comprises Multi-Level Cells (MLC) and wherein the method further comprises storing each logical page in a non-volatile buffer at least until an upper page corresponding to a lower page of non-volatile memory where the logical page is stored has been programmed.

25. The method of claim 24, further comprising reading logical pages stored in the non-volatile buffer and rebuilding the map using the logical pages read from the non-volatile buffer.

26. The method of claim 15, wherein the non-volatile memory comprises Multi-Level Cells (MLC), wherein the non-volatile memory comprises a physical area of memory storing data retained from a garbage collection process and wherein the method further comprises reading journals corresponding to the physical area no further than entries thereof corresponding to safe logical pages stored in a lower page of non-volatile memory where the corresponding upper page has been programmed.

27. The method of claim 26 wherein, for entries of journals corresponding to the physical area corresponding to unsafe logical pages stored in a lower page where the corresponding upper page has not been programmed, the method further comprises reading journals associating one or more physical pages of a block from which the valid data was garbage collected.