Patent Publication Number: US-9842030-B2

Title: Data storage device and flash memory control method

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is a Continuation of pending U.S. application Ser. No. 14/534,633, filed Nov. 6, 2014, which claims the benefit of U.S. Provisional Application No. 61/920,830, filed Dec. 26, 2013, the entirety of which is incorporated by reference herein. 
    
    
     BACKGROUND OF THE INVENTION 
     Field of the Invention 
     The present invention relates to data storage devices with flash memory and flash memory control methods. 
     Description of the Related Art 
     Flash memory, a data storage medium, is common in today&#39;s data storage devices. For example, flash memory is typically used in memory cards, USB flash devices, solid-state drives, and so on. In another application with multi-chip package technology, a NAND flash chip and a controller chip are combined in one package as an embedded multi-media card (e.g. eMMC). 
     A flash memory device provides storage space which is divided into blocks, and each block includes a plurality of pages. An erase operation designed for flash memory is performed on a block-by-block basis, to release space one block at a time. When updating data, the new data is written into a spare space rather than being overwritten on old data. To manage the flash memory, the physical-to-logical address mapping information has to be recorded in the flash memory. It is more complex to manage a flash memory rather than other conventional storage mediums, especially for a large-sized flash memory. It can be very tricky to manage the mapping information of a large-sized flash memory. 
     BRIEF SUMMARY OF THE INVENTION 
     Data storage device with flash memory and flash memory control method with high erasing efficiency are disclosed. 
     In one embodiment, a data storage device, comprises: a flash memory, divided into a plurality of blocks with each block comprising a plurality of physical pages; and a control unit, coupling the flash memory to a host and comprising a microcontroller and a random access memory. The microcontroller maintains a plurality of logical-to-physical address mapping tables and a link table on the flash memory to record mapping information between the host and the flash memory and records a link table indicator on the flash memory to indicate a position of the link table. The link table indicates positions of the plurality of logical-to-physical address mapping tables, and each entry in the link table corresponds to one logical-to-physical address mapping table. In addition, the microcontroller erases user of logical addresses corresponding to N logical-to-physical address mapping tables by downloading the link table from the flash memory to the random access memory, invalidating N entries corresponding to the N logical-to-physical address mapping tables in the link table on the random access memory, uploading the link table with the N entries of invalid data back to the flash memory, and records an updated link table indicator on the flash memory to indicate a position of the uploaded link table on the flash memory, where N is an integer. 
     In an embodiment, a flash memory control method, comprises: maintaining a plurality of logical-to-physical address mapping tables and a link table on a flash memory to record mapping information between a host and the flash memory, wherein the flash memory provides a storage space divided into a plurality of blocks with each block comprising a plurality of pages, and the link table indicates positions of the plurality of logical-to-physical address mapping tables, and each entry in the link table corresponds to one logical-to-physical address mapping table; recording a link table indicator on the flash memory to indicate a position of the link table; erasing user of logical addresses corresponding to N logical-to-physical address mapping tables by downloading the link table from the flash memory to a random access memory, invalidating N entries corresponding to N logical-to-physical address mapping tables in the link table on the random access memory, uploading the link table with the N entries of invalid data back to the flash memory, and recording an updated link table indicator on the flash memory to indicate a position of the uploaded link table on the flash memory, where N is an integer. 
     A detailed description is given in the following embodiments with reference to the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present invention can be more fully understood by reading the subsequent detailed description and examples with references made to the accompanying drawings, wherein: 
         FIG. 1  depicts a storage space provided by a flash memory  100 ; 
         FIG. 2  depicts a logical-to-physical address mapping table in accordance with an exemplary embodiment of the disclosure; 
         FIG. 3  is a block diagram depicting a data storage device  300  in accordance with an exemplary embodiment of the disclosure; 
         FIG. 4  depicts the link table H2FLink modification with respect to the architecture of  FIG. 3 ; and 
         FIG. 5  is a flowchart depicting how to erase the large-sized user data (with logical addresses corresponding to the N entries  332  of the link table H2FLink, with logical-to-physical address mapping information stored in the N logical-to-physical address mapping tables H2Fi . . . H2Fi+N−1) in accordance with an exemplary embodiment of the disclosure. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The following description is of the best-contemplated mode of carrying out the invention. This description is made for the purpose of illustrating the general principles of the invention and should not be taken in a limiting sense. The scope of the invention is best determined by reference to the appended claims. 
       FIG. 1  depicts a storage space provided by a flash memory  100 . The storage space provided by the flash memory  100  is divided into blocks (e.g., BLK 1 , BLK 2  . . . BLKN . . . ). Each block includes a plurality of physical pages. Each physical page includes a plurality of sectors. For example, physical page  102  provided within block BLKN includes four sectors  104 ,  106 ,  108  and  110 . 
     When each sector is allocated for the storage of the user data of one host page (corresponding to a series of logical addresses, e.g. LBAk to LBAk+7), each physical page stores four host pages. For example, the four sectors  104 ,  106 ,  108  and  110  correspond to four host pages Hm (i.e. from LBAk0 to LBAk0+7), Hm+1 (i.e. from LBAk1 to LBAk1+7), Hm+2 (i.e. from LBAk2 to LBAk2+7) and Hm+3 (i.e. from LBAk3 to LBAk3+7), respectively. When one block contains 128 physical pages, there are 128×4 host pages corresponding to the 128×4 sectors of the block. For each block, the mapping information between the 128×4 sectors and the 128×4 host pages has to be recorded for storage space management. For a large-sized flash memory, large amounts of mapping information have to be managed. 
     In an exemplary embodiment, the considerable quantity of mapping information is recorded in the flash memory  100  for non-volatile storage. The mapping information is presented in a multi-level architecture. A plurality of logical-to-physical address mapping tables (abbreviated to H2Fs) and a link table indicating the positions of the plurality of logical-to-physical address mapping tables H2Fs are provided within a flash memory to show the mapping information. 
       FIG. 2  depicts a logical-to-physical address mapping table H2F in accordance with an exemplary embodiment of the disclosure. The logical-to-physical address mapping table H2F is 16 KB, equal to 1 physical page. Each entry in the logical-to-physical address mapping table H2F is 4B. Thus, there is mapping information about 4K (=16 KB/4B) host pages per logical-to-physical address mapping table. Each entry corresponds to one host page and is recorded with a block number B_N and a page number P_N showing where the host page is stored in the flash memory. It is not intended to limit the table size to 16 KB, and it is not intended to limit the mapping information about each host page to 4B. 
       FIG. 3  is a block diagram depicting a data storage device  300  in accordance with an exemplary embodiment of the disclosure. The data storage device  300 , operating in accord with commands from the host  302 , includes a flash memory  304  and a control unit  306 . In the flash memory  304 , the blocks are allocated for several purposes. Blocks  308  are stored with in-system programs (ISPs). Blocks  310  store system information. User data are stored in the data pool  312 . The flash memory  304  may further contain free blocks, spare blocks and run-time write blocks not shown in the figure. 
     The control unit  306  couples the flash memory  304  to the host  302  and comprises a microcontroller  320 , a random access memory  322  and a read-only memory  324 . A ROM code is stored in the read-only memory  324 . The microcontroller  320  operates the flash memory  304  by executing the ROM code stored in the read-only memory  324  or/and by executing the ISPs stored in the blocks  308  of the flash memory  304 . The microcontroller  320  is configured to perform the block allocation of the flash memory  304  (as shown in  FIG. 3 ). 
     The microcontroller  320  is further configured to provide a link table indicator *H2FLink, logical-to-physical address mapping tables H2F1 . . . H2Fi . . . H2Fi+N−1 . . . H2FK and a link table H2FLink on the flash memory  304  to record logical-to-physical address mapping information between the host  302  and the flash memory  304 . The link table indicator *H2FLink in a system block  330  indicates the position of the link table H2FLink. The link table indicator *H2FLink may indicate the position of the link table H2FLink by a block number and a page number. The link table H2FLink indicates the positions of the plurality of logical-to-physical address mapping tables H2F1 . . . H2FK. The different entries in the link table H2FLink correspond to the different logical-to-physical address mapping tables H2F1 . . . H2FK. In an exemplary embodiment, each entry in the link table H2FLink may be stored with a block number and a page number that indicate the position of the logical-to-physical address mapping table corresponding thereto. In the following discussion, a request to erase user data of logical addresses corresponding to N logical-to-physical address mapping tables H2Fi . . . H2Fi+N−1 is requested. As shown, N entries  332  in the link table H2FLink correspond to the N logical-to-physical address mapping tables H2Fi . . . H2Fi+N−1. The microcontroller  320  is configured to read the system block  330  to download the link table indicator *H2FLink from the flash memory  304  to a space  334  of the random access memory  322 . Furthermore, based on the link table indicator *H2FLink, the microcontroller  320  downloads the link table H2FLink from the flash memory  304  to a space  336  of the random access memory  322  and invalidates the N entries  338  of the link table on the random access memory  322 . The microcontroller  320  uploads the link table with the N entries  338  of invalid data back to the flash memory  304  (e.g. into a spare area  340  of the flash memory  304 ). When uploading the link table with the N entries  338  of invalid data back to the flash memory  304  (into the spare area  340 ), the microcontroller  320  further updates the system block  330  with an updated link table indicator  342  to indicate the new position  340  of the updated link table. In this manner, even though a large-sized erase operation for the logical addresses relating to the N logical-to-physical address mapping tables H2Fi . . . H2Fi+N−1 is requested (e.g. a request to erase sequential data along the logical address covered by the N logical-to-physical address mapping tables H2Fi . . . H2Fi+N−1), just a few system resources are required. Instead of downloading all of the N logical-to-physical address mapping tables H2Fi . . . H2Fi+N−1 from the flash memory  304  to the random access memory  322  for mapping information modification, the large-sized erase operation is achieved by easily modifying the link table indicator *H2FLink and the link table H2FLink. The system efficiency of the data storage device  300  is considerably improved. 
       FIG. 4  depicts the link table H2FLink modification with respect to the architecture of  FIG. 3 . As shown, the link table H2FLink is stored with pointers *H2F1 . . . *H2FK linked to the logical-to-physical address mapping tables H2F1 . . . H2FK, respectively. To erase user data of logical addresses corresponding to the N logical-to-physical address mapping tables H2Fi . . . H2Fi+N−1, the link table H2FLink is downloaded to space  336  of the random access memory  322  and the N entries  338  of the link table are invalidated on the random access memory  322 . Then the link table with the N entries  338  of invalid data is uploaded back to the flash memory  304  into space  340 . The former link table H2FLink is invalidated. 
       FIG. 5  is a flowchart depicting how to erase the large-sized user data (with logical addresses corresponding to the N entries  332  of the link table H2FLink, with logical-to-physical address mapping information stored in the N logical-to-physical address mapping tables H2Fi . . . H2Fi+N−1) in accordance with an exemplary embodiment of the disclosure. The flowchart of  FIG. 5  is discussed with respect to the architecture of  FIG. 3 . 
     In step S 502 , the system block  330  is accessed and thereby the link table indicator *H2FLink is retrieved therefrom and temporarily stored into space  334  of the random access memory  322 . In step S 504 , the link table H2FLink is downloaded from the flash memory  304  and temporarily stored into the random access memory  322  in space  336 . In step S 506 , the N entries  338  of the link table stored in the random access memory  322  is invalidated and the link table with the N entries of invalid data is uploaded back to the flash memory  304  into space  340 . In step S 508 , the link table indicator in space  334  is updated to indicate the position of the space  340  and the updated link table indicator is uploaded back to the flash memory  304  into space  342 . 
     Any technique using the aforementioned concept to control a flash memory is within the scope of the invention. The invention further involves flash memory control methods, which are not limited to any specific controller architecture. 
     While the invention has been described by way of example and in terms of the embodiments, it is to be understood that the invention is not limited to the disclosed embodiments. On the contrary, it is intended to cover various modifications and similar arrangements (as would be apparent to those skilled in the art). Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.