Non-volatile memory controller, control method, and non-transitory computer-readable storage medium

1 . A non-volatile memory controller, comprising:

a communication interface, coupled to a non-volatile memory; and

a processor, operating the non-volatile memory through the communication interface,

wherein:

space allocation of the non-volatile memory is presented by a plurality of logical-to-physical address mapping sub-tables;

the processor selects a plurality of source blocks and a destination block from the non-volatile memory for garbage collection; and

in order from the lowest to the highest logical address, the processor selects the logical-to-physical address mapping sub-tables in turn for use as a scan target, to perform a full scan of each logical-to-physical address mapping sub-table, and thereby to collect valid data in the source blocks and program the valid data obtained from the source blocks to the destination block;

wherein based on a valid data count of each source block, the processor divides the source blocks into primary clearing blocks and secondary clearing blocks such that a total amount of valid data in the primary clearing blocks does not exceed a spare space size of the destination block; and

the processor initializes a residual value according to a difference between the total amount of valid data in the primary clearing blocks and the spare space size, and stops collecting valid data from the secondary clearing blocks in response to the residual value dropping to a threshold value after being decreased during the collection of valid data.

2 . The non-volatile memory controller as claimed in claim 1 , wherein:

the processor scans the scan target on a mapping management unit basis, to obtain a mapped physical address mapped to a target logical address; and

when the mapped physical address leads to one of the source blocks, the processor collects data indicated by the mapped physical address, and programs the collected data to the destination block.

3 . The non-volatile memory controller as claimed in claim 1 , wherein:

the processor selects N blocks with the lowest valid data counts in the non-volatile memory as the source blocks, where N is a positive integer;

the processor classifies blocks with the lowest valid data counts among the source blocks as the primary clearing blocks, and blocks with the highest valid data counts among the source blocks as the secondary clearing blocks;

the total amount of valid data in the primary clearing blocks does not exceed a tolerance value related to the spare space size; and

the threshold value for judging the residual value is 0.

4 . The non-volatile memory controller as claimed in claim 1 , wherein:

when collecting valid data of the source blocks and programming the collected valid data to the destination block, the processor decreases valid data counts of the corresponding source blocks; and

the processor excludes blocks with zero valid data from the source blocks.

5 . A method for controlling a non-volatile memory, comprising:

managing a plurality of logical-to-physical address mapping sub-tables to present space allocation of the non-volatile memory;

selecting a plurality of source blocks and a destination block from the non-volatile memory for garbage collection;

in order from low to high logical address, selecting the logical-to-physical address mapping sub-tables as a scan target in turn, to perform a full scan of each logical-to-physical address mapping sub-table, and thereby to identify valid data in the source blocks and collect the valid data obtained from the source blocks and programs the collected valid data to the destination block;

dividing the source blocks into primary clearing blocks and secondary clearing blocks based on a valid data count of each source block such that a total amount of valid data in the primary clearing blocks does not exceed a spare space size of the destination block;

initializing a residual value according to a difference between the total amount of valid data in the primary clearing blocks and the spare space size;

decreasing the residual value in response to collecting valid data from the secondary clearing blocks and programming the collected valid data to the destination block; and

stopping collecting valid data of the secondary clearing blocks to the destination block in response to the residual value dropping to a threshold value.

6 . The method as claimed in claim 5 , further comprising:

scanning the scan target on a mapping management unit basis, to obtain a mapped physical address mapped to a target logical address; and

when the mapped physical address leads to one of the source blocks, collecting data indicated by the mapped physical address to the destination block.

7 . The method as claimed in claim 5 , further comprising:

selecting N blocks with the lowest valid data counts in the non-volatile memory as the source blocks, where N is a positive integer; and

classifying blocks with the lowest valid data counts among the source blocks as the primary clearing blocks, and blocks with the highest valid data counts among the source blocks as the secondary clearing blocks;

wherein:

the total amount of valid data in the primary clearing blocks does not exceed a tolerance value related to the spare space size; and

the threshold value for judging the residual value is 0.

8 . The method as claimed in claim 5 , further comprising:

when collecting valid data of the source blocks and programming the collected valid data to the destination block, decreasing valid data counts of the corresponding source blocks; and

excluding blocks with zero valid data from the source blocks.

9 . A non-transitory computer-readable storage medium, storing program code to be executed by a processor to implement the method as claimed claim 5 .

10 . A non-transitory computer-readable storage medium, storing program code to be executed by a processor to implement the method as claimed in claim 6 .

11 . A non-transitory computer-readable storage medium, storing program code to be executed by a processor to implement the method as claimed in claim 7 .