Data storage device and method of performing partial garbage collection
A data storage device is provided. The data storage device includes: a flash memory and a microcontroller. The flash memory includes a plurality of physical blocks. The microcontroller selects one source block and one destination block from the plurality of physical blocks, and performs a garbage collection operation according to a check map corresponding to the selected source block to copy data stored in one or more valid physical addresses of the source block to the selected destination block.
1. A data storage device, comprising:
a flash memory, comprising a plurality of physical blocks; and
a microcontroller, selecting one source block and one destination block from the plurality of physical blocks, and performing a garbage collection operation according to a check map corresponding to the selected source block to copy data stored in one or more valid physical addresses of the source block to the selected destination block,
wherein the check map records whether a mapping relationship of each physical address in a physical-to-logical mapping table corresponding to the source block has been compared to that of one or more corresponding group logical-to-physical tables,
wherein the microcontroller selects a first entry of a physical-to-logical mapping table of the source block, and loads a group logical-to-physical mapping table, corresponding to a specific logic address recorded in the first entry, to a random access memory, wherein the first entry is a non-dummy entry.
2. The data storage device as claimed in claim 1 , wherein the microcontroller checks a plurality of entries in the physical-to-logical mapping table to obtain at least one second entry corresponding to the group logical-to-physical mapping table, wherein the at least one second entry comprises the first entry.
3. The data storage device as claimed in claim 2 , wherein the microcontroller respectively selects each second entry corresponding to the group logical-to-physical mapping table from the physical-to-logical mapping table, and determines whether the selected second entry is valid.
4. The data storage device as claimed in claim 3 , wherein:
when the selected second entry is valid, the microcontroller labels a check bit corresponding to the checked second entry in the check map; and
when the selected second entry is invalid, the microcontroller invalidates a logical address recorded in the checked second entry, and labels the check bit corresponding to the checked second entry in the check map.
5. The data storage device as claimed in claim 4 , wherein when each second entry in the physical-to-logical mapping table has been checked, the microcontroller sequentially copies data from the labeled and valid second entries in the physical-to-logical mapping table to the destination block, and invalidates the logical address recorded in the at least one second entry having the copied data.
6. The data storage device as claimed in claim 5 , wherein the microcontroller writes the data from the at least one second entry to the destination block using a first-in first-out method to complete the garbage collection operation.
7. The data storage device as claimed in claim 5 , wherein the microcontroller does not write the data from the at least one second entry to the destination block until a predetermined of data from the at least one second entry has been stored, thereby completing the garbage collection operation.
8. A data storage device, comprising:
a flash memory, comprising a plurality of physical blocks; and
a microcontroller, selecting one source block and one destination block from the plurality of physical blocks, and dividing the source block into a plurality of virtual blocks,
wherein the microcontroller selects one of the virtual blocks, and performs a garbage collection operation according to a check map corresponding to the selected virtual block to copy data, stored in one or more valid physical addresses of the virtual block, to the selected destination block,
wherein the check map records whether a mapping relationship of each physical address in a virtual physical-to-logical mapping table corresponding to the selected virtual block of the source block has been compared to that of one or more corresponding group logical-to-physical tables,
wherein the microcontroller selects a first entry of the virtual physical-to-logical mapping table of the selected virtual block, and loads a group logical-to-physical mapping table, corresponding to a specific logic address recorded in the first entry, to a random access memory, wherein the first entry is a non-dummy entry.
9. The data storage device as claimed in claim 8 , wherein the microcontroller checks a plurality of entries in the virtual physical-to-logical mapping table to obtain at least one second entry corresponding to the group logical-to-physical mapping table, wherein the at least one second entry comprises the first entry.
10. The data storage device as claimed in claim 9 , wherein the microcontroller respectively selects each second entry corresponding to the group logical-to-physical mapping table from the virtual physical-to-logical mapping table, and determines whether the selected second entry is valid.
11. The data storage device as claimed in claim 10 , wherein:
when the selected second entry is valid, the microcontroller labels a check bit corresponding to the checked second entry in the check map; and
when the selected second entry is invalid, the microcontroller invalidates a logical address recorded in the checked second entry, and labels the check bit corresponding to the checked second entry in the check map.
12. The data storage device as claimed in claim 11 , wherein when each second entry in the virtual physical-to-logical mapping table has been checked, the microcontroller sequentially copies data from the labeled and valid second entries in the virtual physical-to-logical mapping table to the destination block, and invalidates the logical address recorded in the at least one second entry having the copied data.
13. The data storage device as claimed in claim 12 , wherein the microcontroller writes the data from the at least one second entry to the destination block using a first-in first-out method to complete the garbage collection operation.
14. The data storage device as claimed in claim 12 , wherein the microcontroller does not write the data from the at least one second entry to the destination block until a predetermined amount of data from the at least one second entry has been stored, thereby completing the garbage collection operation.
15. A data storage device, comprising:
a flash memory, comprising a plurality of physical blocks; and
a microcontroller, selecting one source block and one destination block from the plurality of physical blocks, and dividing the source block into a plurality of virtual blocks,
wherein the microcontroller selects one of the virtual blocks, and reads a virtual valid data count of the selected virtual block,
wherein when the microcontroller determines that the virtual valid data count of the selected virtual block is equal to a maximum storage size of the selected virtual block, the microcontroller performs a garbage collection operation to copy data, stored in a plurality of physical addresses of the selected virtual block, to the selected destination block.
16. The data storage device as claimed in claim 15 , wherein when the microcontroller determines that the virtual valid data count of the selected virtual block is equal to 0, the microcontroller ends the garbage collection operation.