Garbage collection method for data storage device

Patent metadata

Field	Value
Publication number	US-10657048-B2
Application number	US-201715783953-A
Country	US
Kind code	B2
Filing date	Oct 13, 2017
Priority date	Nov 10, 2016
Publication date	May 19, 2020
Grant date	May 19, 2020

Abstract

A garbage collection method for a data storage device includes steps of: entering a background mode from a foreground mode; selecting a plurality of source data blocks from a plurality of in-use data blocks; dividing a mapping table into a plurality of sub-mapping tables and selecting one of the sub-mapping tables as a target sub-mapping table, wherein the target sub-mapping table is used to manage one of the source data blocks; selecting a destination data block from a plurality of spare data blocks; and sequentially updating a correspondence relationship of data stored in the target sub-mapping table from the source data blocks to the destination data block, wherein the updating comprises copying the data stored in the source data blocks to the destination data block.

First claim

What is claimed is:

1. A garbage collection method for a data storage device, comprising:
entering a background mode from a foreground mode;
selecting a plurality of source data blocks from a plurality of in-use data blocks;
dividing a mapping table stored in a non-volatile storage medium of the data storage device into a plurality of sub-mapping tables, storing the plurality of sub-mapping tables in the non-volatile storage medium of the data storage device, and selecting one of the sub-mapping tables from the non-volatile storage medium as a target sub-mapping table, wherein the target sub-mapping table is used to manage one of the source data blocks;
selecting a destination data block from a plurality of spare data blocks;
sequentially copying a plurality of valid data stored in the source data blocks to the destination data block;
updating a correspondence relationship of the copied valid data in the target sub-mapping table from the source data blocks to the destination data block;
determining the correspondence relationship of the data stored in the target sub-mapping table has been not completely updated;
selecting another destination data block from the spare data blocks to copy the remaining valid data from the source data blocks to another destination data block until the target sub-mapping table has been completely updated; and
recovering one of the source data blocks as a spare data block when the one of the source data blocks does not contain any valid data.

2. The garbage collection method according to claim 1 , wherein one of the source data blocks is one of the in-use data blocks having an extreme value of valid data count.

3. The garbage collection method according to claim 1 , wherein one of the source data blocks is one of the in-use data blocks having an extreme value of erase count.

4. The garbage collection method according to claim 1 , wherein one of the source data blocks is one of the in-use data blocks having an extreme value of read count.

5. The garbage collection method according to claim 1 , wherein the source data blocks are randomly selected from the in-use data blocks.

6. The garbage collection method according to claim 1 , wherein the source data blocks are sequentially selected from the in-use data blocks according to a serial number.

7. The garbage collection method according to claim 1 , wherein the target sub-mapping table is sequentially selected from the sub-mapping tables.

8. The garbage collection method according to claim 1 , wherein the target sub-mapping table is randomly selected from the sub-mapping tables.

9. The garbage collection method according to claim 1 , wherein the destination data block is randomly selected from the spare data blocks.

10. The garbage collection method according to claim 1 , wherein the destination data block is sequentially selected from the spare data blocks.

11. The garbage collection method according to claim 1 , wherein the destination data block is one of the spare data blocks having an extreme value of erase count.

12. The garbage collection method according to claim 1 , wherein the data storage device comprises the in-use data blocks storing valid data and the spare data blocks not storing the valid data.

13. The garbage collection method according to claim 1 , wherein the data storage device comprises a dynamic random access memory (DRAM), and a size of the mapping table is larger than a size of the DRAM.

14. The garbage collection method according to claim 1 , wherein the background mode is entered from the foreground mode when the data storage device does not receive a command.

15. The garbage collection method according to claim 1 , wherein the background mode is entered from the foreground mode when a total number of the spare data blocks is lower than a threshold.

16. The garbage collection method according to claim 1 , wherein the background mode is entered from the foreground mode when a power state of the data storage device is changed.

Assignees

• Silicon Motion Inc

Inventors

• Hsu Hong-Jung
• Kuo Chun-Chieh

Classifications

• G06F3/0608 Primary

  Saving storage space on storage systems · CPC title

• G06F12/0253

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F2212/7205

  Cleaning, compaction, garbage collection, erase control · CPC title

• G06F3/068

  Hybrid storage device · CPC title