Abstract:
A link table recovery method for a flash memory having a plurality of blocks is provided. The method includes: selecting one block from the blocks; selecting a last page containing data of the selected block; checking the last page to determine whether the last page has errors; moving the correct data in the selected block to one of the spare blocks when the last page of the selected block detects errors; and updating a link table of the flash memory.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention relates to a link table recovery method, and more particularly to a link table recovery method after sudden power failure. 
     2. Description of the Related Art 
     Flash memory is a non-volatile memory that can be electrically erased and reprogrammed. Flash memories are primarily used in memory cards and USB flash drives for general storage and transfer of data between computers and other digital products. Flash memory costs far less than EEPROM and therefore has become a dominant memory device. Examples of flash memory applications include applications in Personal Digital Assistants (PDA) and laptop computers, digital audio players, digital cameras and mobile phones. 
     Generally speaking, flash memory is controlled by a flash controller. However, if power failure occurs while the flash controller is performing an access operation, for example in the middle of writing data to the flash memory, the contents of the interrupted page or block become unreadable after the flash memory has been powered up again and may be random. This is because, while some of the affected bits in the flash memory may have reached the state assigned to them by the flash memory operation by the time of the power interruption, remaining affected bits in the flash memory may have not. Thus, there is a need for an improved flash management system, capable of dealing with flash memory power interruptions. 
     BRIEF SUMMARY OF THE INVENTION 
     An embodiment of a link table recovery method for a flash memory having a plurality of blocks is disclosed. The method comprises: selecting one block from the blocks; selecting a last page containing data of the selected block; checking the last page to determine whether the last page has errors; moving the correct data in the selected block to one of the spare blocks when the last page of the selected block detects errors; and updating a link table of the flash memory. 
     An embodiment of the link table recovery method for a flash memory comprising a plurality of blocks after sudden power failure is provided. The method comprises: selecting a last accessed block; checking pages of the last accessed block to determine whether the last accessed block has errors; moving correct data from the last accessed block to a spare block when detecting error in a first page; and updating a link table of the flash memory. 
     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  is a block diagram of a flash memory device. 
         FIG. 2  is a flow chart of an embodiment of a link table recovery method for a flash memory according to the invention. 
         FIG. 3  shows the structure of a block according to an embodiment of the invention. 
         FIG. 4  is an embodiment of the link table block according to the invention. 
         FIG. 5  is a flow chart of another embodiment of a link table recovery method for a flash memory according to the invention. 
         FIG. 6  is a block diagram of an embodiment of the flash memory system according to the invention. 
     
    
    
     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  is a block diagram of a flash memory device. The flash memory device  10  comprises a memory controller  11 , and a non-volatile flash memory  12 . The memory controller  11  comprises interface logic  13 , a volatile buffer  14 , control logic  16  and microprocessor  15 , wherein the interface logic  13  transmits data to/from a host (not shown in  FIG. 1 ), the volatile buffer  14  is used to temporality store data written in or read from the non-volatile flash memory  12 . The logic elements  13 ,  14 , and  16  are controlled by the microprocessor  15 . The non-volatile flash memory  12  comprises a plurality of blocks and data can be over-written to the blocks only after the blocks are erased. In other words, the data can only be written to the empty blocks. 
       FIG. 2  is a flow chart of an embodiment of a link table recovery method for a flash memory according to the invention. The method especially focuses on the link table recovery method after the sudden power failure while the flash memory is being programmed. It is noted that only one block of the flash memory may fail when the sudden power failure occurs during the programming of the flash memory, but sometimes the ECC error may also occur on the adjacent pages. The flash memory comprises a plurality of blocks and each block comprises a plurality pages. In step S 201 , the flash memory controller selects the first block of the flash memory. In the step S 202 , the controller determines whether the selected block is the last block. If yes, the method goes to step S 210 . If not, the method goes to step S 203 . In step S 203 , the controller reads the spare regions of the selected block to determine the type of the selected block. The block comprises a plurality of pages and each page contains a spare region. The spare region contains ECC (error checking and correction) parity, firmware parameters and identification (ID) of the selected block. Please refer to  FIG. 3 .  FIG. 3  shows the structure of a block according to an embodiment of the invention. In this embodiment, the block comprises 64 pages and each page comprises a data region and a spare region. The spare is also called the overhead data to store some parameters associated with the blocks. The structure of  FIG. 3  is only for illustration, and the structure may vary based on the standard of different types of flash memories. 
     In step S 203 , the controller determines whether the selected block is the first class block based on the ID stored in the spare region. The first class block is a kind of data block for storing user data, for example, may be the FAT (file allocation table) block, mother block, child block, or temp block. If the selected block belongs to the first class block, the controller executes the step S 205 . If the selected block does not belong to the first class block, the controller executes the step S 206  to mark the selected block as the spare block and go to step S 209  after step S 206 . In step S 205 , the controller searches and checks the last page containing data. In this embodiment, the controller searches the last page containing data for the ECC check because only one page may contain error while the sudden power failure occurs. In another embodiment, the controller can check a plurality of pages near the selected page or all the pages of the selected block. In step S 207 , the controller executes an ECC check on the selected page. The controller reads the user data and the ECC related data stored in the spare region and verifies the user data based on the ECC related data. If the select page passes, the method goes to the step S 209 . If the selected page fails to verification, the controller executes the step S 208  to store the error type information of the selected pages. The error type information comprises the physical address of the selected block and the page number of the error page. 
     After saving the error type information, the method goes to step S 209  to select another block for check. In this embodiment, the blocks are sequentially selected, but the invention is not limited thereto. When the selected block is the last block, the method goes to the step S 210  to check whether the last block has an error. If the last block does not have an error, the controller further determines whether the previous blocks have an error. If all the blocks do not have error, the method finishes. If any block contains an error, the controller moves the correct data of the error block to a new block, for example the spare block, in step S 211 , wherein the correct data of the error block is the data stored in the pages previous to the error page. After the step S 211 , the controller updates the link table in step S 212 . When accessing one MU (management unit) of the flash memory, the corresponding link table is acquired and stored in RAM. The controller accesses and modifies the link table from the RAM and stores the modified link table to the RAM and the MU. After the step S 212 , the controller repeats the method again and rebuilds the link table. As to the link table, please refer to  FIG. 4 . 
       FIG. 4  is an embodiment of the link table block according to the invention. The link table is used for logical addresses and the flash memory controller manages the flash memory by physical addresses. The link table acts as a look-up table to ensure the controller correctly translates logical addresses into physical addresses. In other words, the link table ensures data correctness by interchanging of the logical address used for the controller and the actual address of the block in the flash memory. In  FIG. 4 , the RAM address represents the logic address and the content of RAM address stores the corresponding physical address of the block. For example, the RAM address 0x00, i.e., the logic block address (shown as L.B. Address 0x00) stores the physical block address N, and when the flash memory controller accesses the block of the logic block address 0x00, the flash memory controller actually accesses the block of the physical address N. In the step S 212  of  FIG. 2 , the controller changes the RAM content to update the link table. For example, the block of the logic block address 0x0Z is the spare block and the block of the logic block address 0x02 is the error block. The controller moves the correct data of the error block to the spare block and exchanges the RAM content of the logic block address 0x02 with the content of the logic block address 0x0Z. Next, when the controller accesses the logic block address 0x02, the controller actually accesses the block of the physical address I, not the block of the physical address T. 
       FIG. 5  is a flow chart of another embodiment of a link table recovery method for a flash memory according to the invention. In step S 51 , the controller checks all pages of the last accessed child block to determine whether the last accessed child block has errors. The embodiment of  FIG. 5  is illustrated with the child block, but is not limited thereto. The link table recovery method shown in  FIG. 5 , can also be used for the temp block, FAT block, child-to-FAT block or other block type. If the last accessed child block does not have errors, the link table recovery method finishes or checks the blocks adjacent to the last accessed child block. If the last accessed child bock has errors, the method goes to step S 52 . In step S 52 , the controller selects a new block from a spare block pool and moves the correct data of the last accessed block to the new block, wherein the correct data is the data stored in the pages previous to the error page of the error child block. In the step S 53 , the controller copies the remaining data in the mother block to the new block. For example, if the mother block and the child block have 1024 pages, and the controller error is found in the 100 th  page of the child block, the controller first move the data from the 1 st  page to the 99 th  page of the child block to the new block, and then copies the data from the 100 th  to the 1024 th  page of the mother block to the corresponding pages of the new block. In the step S 54 , the controller updates the physical address of the new block in the link table. The updating is similar to the updating described previously. In the step S 55 , the controller erases the child block and the mother block and marks the child block and the mother block as the spare blocks. 
       FIG. 6  is a block diagram of an embodiment of the flash memory system according to the invention. The flash memory system  60  comprises RAM  62 , controller  61  and flash memory  63 . The controller  61  receives and writes data to the flash memory  63  based on the corresponding link table stored in RAM  62 . When the controller  61  accesses the MU of the flash memory  63 , such as the MU0, the controller  61  acquires and stores the corresponding link table to the RAM  62 . When the controller  61  accesses the flash memory  63  and the sudden power failure occurs, the controller  61  executes a link table recovery method, such as that shown in  FIG. 2  and  FIG. 5 , to ensure that the flash memory  63  can be normally accessed. 
     While the invention has been described by way of example and in terms of preferred embodiment, it is to be understood that the invention is not limited thereto. To 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.