Abstract:
The present invention relates to an algorithm of flash memory capable of quickly building a mapping table and preventing disorder of data due to abnormal disconnection and a control system thereof, wherein pages of a physical block store data of the mapping table of logical block addresses and corresponding physical block addresses. A set of ECC data are used for protection. When the host computer is normally turned on, data of the mapping table are directly stored into a buffer so that the control device can read. The system can quickly build the mapping table to save the time and operation of turning on without the need of a scanning procedure. If an error of the mapping table due to improper operation occurs, the previous mapping table can be retraced to restore the system to the normal state.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates to an algorithm of flash memory and, more particularly, to an algorithm of flash memory capable of quickly building a table and preventing disorder of data due to abnormal disconnection and a control system thereof.  
         BACKGROUND OF THE INVENTION  
         [0002]    Along with continual progress of the information industry, high-speed data storage devices (memories) play very important roles due to influence of ever faster CPUs and development of information appliance (IA) products. Because flash memories have the characteristics of non-volatility and easily changing access of data, they have been eagerly expected by users.  
           [0003]    As shown in FIG. 1A, at least a flash storage device (NAND type flash are the most popular)  11 ˜ 19  is connected to a host computer  29  mainly via a control device  20 . Of course, the control device  20  can also be built in a subsystem of the host computer  29 . The control device  20  comprises a microprocessor  25  therein, which can be connected to the host computer  29  via an interface controller  24  conforming to the protocol of PCMCIA, IDE, ATA, ATAPI, USB, or their combination. One end of the microprocessor  25  can be connected to the data storage device  11  via a storage control logic circuit  26 . The microprocessor  25  can also be connected to a buffer controller  22 . The buffer controller  22  can temporarily store the data to be accessed by the host computer  29  into a data storage region  21  (a first buffer  211 , a second buffer  213 , and an N-th buffer  219 ). Additionally, an ECC logic circuit  23  is respectively connected to the microprocessor  25 , the buffer controller  22 , and the storage control logic circuit  26 . The ECC logic circuit  22  is controlled by the microprocessor  25  to give a corresponding error-correcting code (ECC) data to a data sector to be accessed. Moreover, the microprocessor  25  can be connected to a lookup table  255 , which can be used to keep logic block addresses (L 0 ˜L m+1 ) and all physical block addresses (PBA) of the corresponding data storage device  11 .  
           [0004]    As shown in FIG. 1B, a memory used by the lookup table  255  such as a random access memory (RAM) mainly uses a word as an access unit, and is partitioned into a plurality of word addresses LBA (logic block address, L 0 , L 1 , . . . , L m , L m+1 , . . . .) Each logical block address includes an address data mapping to a corresponding PBA (physical block address; B 3 , B 2 , . . . , B m , B m+1 , . . . ). The flash memory  11  mainly uses a block as an access unit, and is partitioned into a plurality of physical block addresses B 0 ˜B n . A physical block (Data 0 ˜Data n ) of each physical block address includes a plurality of block pages. Each page corresponds to a sector of smallest storage unit at the host end. An error-correcting code (ECC; E 0 ˜E N ) field of each corresponding page in a record block and an LBA (L 2 , L 3 , L 1 , . . . , L m+1 ) field recording a corresponding logical block address data can be attached behind each physical block. The PBA field of the lookup table  255  corresponds to the LBA field of the memory  11 . For example, the logical address data of the data Data 0  stored in the physical block B 0  of memory points to the LBA L 2  in the lookup table  255 . Therefore, L 2  is recorded in the LBA field thereof (this data will be stored and will not disappear even if disconnection occurs). The PBA field of the sector L 2  of the lookup table  255  points to the B 0  (this data will disappear after disconnection occurs), as the double arrowheads of the solid line shown in FIG. 1B.  
           [0005]    When the system is turned on, the PBA fields of the lookup table  255  do not exist. The microprocessor  25  will scan all physical block addresses and logical block addresses (LBAs) of the flash memories  11 ˜ 19 , and fill corresponding relations into the physical block address (PBA) fields according to the LBAs, thereby building the complete lookup table  255 . However, this way of scanning and then building the lookup table is inconvenient and consumes much operation time.  
           [0006]    Moreover, the block B 0  is used as a unit when erasing or accessing data due to the structure of the flash memory  11 . Therefore, when there exists a physical block to be modified (e.g., the B 2 ), it is necessary to store the data Data 2  originally stored in the block B 2  into a clean physical block (e.g., B m+1 ), record the logical address L 1  in the LBA field behind the physical block B m+1 , and then erase the Data 2  in the block B 2  to be modified so that the block becomes a clean block or is recorded as not in use. However, if an abnormal situation such as a sudden disconnection or a crash occurs when the clean block (e.g., B m+1 ) has finished the steps of storing data and filling logical address data but the block B 2  to be modified has not yet finished the step of erasing, the host computer will be turned on again and the microprocessor  25  will again scan all physical block addresses of the memory  11 . The situation that the two data blocks B 2  and B m+1  are recorded to have the same logical block address L 1  and point to the same corresponding address in the lookup table  255  (as the double arrowheads of the dash line shown in FIG. 1B), or the situation that some blocks may be disconnected may occur. Erroneous connection of data or even damage of data may thus easily arise.  
           [0007]    Accordingly, the present invention aims to propose an algorithm of flash memory capable of quickly building a lookup table and preventing disorder of data due to abnormal disconnection and a control system thereof.  
         SUMMARY OF THE INVENTION  
         [0008]    The primary object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing disorder of data due to abnormal disconnection and a control system thereof, wherein pages of a physical block are utilized to store data of a lookup table. When the system is turned on, quick switching is achieved by directly storing into a buffer from the block pages without a microprocessor utilizing a scan program to perform scan of logical addresses to all physical blocks of each memory. Therefore, the operation of the microprocessor can be simplified, and the operation time can also be greatly saved.  
           [0009]    The secondary object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, wherein pages of physical blocks of the memory can store data of a lookup table, thereby preventing abnormality of data due to improper operation.  
           [0010]    Another object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, wherein data of a lookup table can be protected by a set of ECC data to enhance the accuracy of data.  
           [0011]    Yet another object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, wherein all memory blocks can be partitioned into a plurality of segments according to capacity of memory of buffers or block pages. Each segment has a corresponding mapping table of buffers to build the mapping relations of data. When there are data of a block modified, only the related data of the mapping table will be affected. Therefore, time of modification of the mapping table can be effectively decreased, and the situation of erroneous connection of data can be effectively reduced.  
           [0012]    Still yet another object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, whereby all physical blocks can be partitioned into a plurality of segments to let the size of a mapping table be reduced to be just a sector (256 words) so that the mapping table can be used as general data and stored into the flash memory. Therefore, the capacity of memory for recording data of physical block addresses can be greatly saved. The present invention can also apply to a storage system connecting a plurality of flash memories.  
           [0013]    The various objects and advantages of the present invention will be more readily understood from the following detailed description when read in conjunction with the appended drawing, in which: 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]    [0014]FIG. 1A is a structure diagram of a storage system of a general flash memory in the prior art;  
         [0015]    [0015]FIG. 1B is a structure diagram of a lookup table of a flash memory in the prior art;  
         [0016]    [0016]FIG. 2A is a structure diagram of a storage system of a flash memory of the present invention;  
         [0017]    [0017]FIG. 2B is a structure diagram of a lookup table of a flash memory of the present invention;  
         [0018]    [0018]FIG. 2C is a structure diagram of part of pages of physical blocks of a flash memory of the present invention;  
         [0019]    [0019]FIG. 3 is a flowchart of accessing data of a flash memory of the present invention; and  
         [0020]    [0020]FIG. 4 is a flowchart of building a mapping table of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0021]    As shown in FIG. 2A, at least a data storage device  3139  is connected to a host computer  49  mainly via a control device  40 . Of course, the control device  40  can also be built in a subsystem of the host computer  49 . The control device  40  comprises a microprocessor  45  therein, which can be connected to the host computer  49  via an interface controller  44  conforming to the protocol of PCMCIA, IDE, ATA, ATAPI, USB, or their combination. One end of the microprocessor  45  can be connected to the data storage device  31 ˜ 39  via a storage control logic circuit  46 . The microprocessor  45  can also be connected to a buffer controller  42 . The buffer controller  42  can temporarily store the data to be accessed by the host computer  49  into a data storage region  41  (a first buffer  411 , a second buffer  413 , and an N-th buffer  419 , each having the size of a sector). Additionally, an ECC logic circuit  43  is respectively connected to the microprocessor  45 , the buffer controller  42 , and the storage control logic circuit  46 . The ECC logic circuit  42  is controlled by the microprocessor  45  to give a corresponding ECC data to a data sector to be accessed. The buffer  419  of the data storage region  41  can be used as a mapping table  419  for storing corresponding physical block addresses (PBAs) of all memory physical blocks.  
         [0022]    As shown in FIG. 2B, the mapping table  419  for storing corresponding physical block addresses PBAs is recorded into the buffer  419  of the control device  40 . In order to match the storage capacity 256 bytes or 512 bytes (i.e., 128 or 256 words) of page of the buffer  419  or a physical block (B 0 ), each word W 0 , W 1 , . . . , W m  of the mapping table  419  includes the address of a corresponding block B 0 , B 1 , . . . , B m . Therefore, a mapping table  419  can correspond to 128 or less than 256 physical blocks (B 0 ). Therefore, the physical blocks can be partitioned into a plurality of segments (Seg 0 ˜Seg n ). The number of blocks included in each partitioned segment will be limited within 256 (or 128). Of course, each segment has a special reserved block (as the symbol * shown in FIG. 2B or as shown in FIG. 2C) for exclusively recording mapping update.  
         [0023]    Each segment has a corresponding special reserved block for recording mapping update to built mapping relations of data. The initial value of this mapping block is built when the system is initiating. When the host computer  49  is to access a file, the microprocessor  45  of the control device  40  will acquire the mapping table required to be read in by dividing the LBA value introduced from the host computer  49  by the physical block number in the segment, and then by the sector number in the block. The mapping table of this segment will be stored into a mapping buffer  419  by the newest updated page of the special reserved block of mapping update, thereby letting the system conveniently finding out the physical block address this LBA required to map. Moreover, each segment has a special reserved block of mapping update to store newest built mapping relations of data. When there are mapping data of a block modified, only the newest page of the special reserved block of mapping update of this segment will be renewed. Therefore, time of modification of the whole mapping table can be effectively decreased, and the situation of erroneous connection of data can be effectively reduced.  
         [0024]    Because the mapping table of the present invention is itself a storable data, when the recorded data in the mapping table  419  are modified, this data can be stored into a partial page  311  of a physical block of a special reserved block of mapping update. This partial page  311  is a data block, which is not mapped and denoted by a special mark “*” This partial page  311  is partitioned into a plurality of segmented pages MT 0 , MT 1 , MT 2 , . . . , MT m , wherein m is the number of pages in a block. Please refer to FIG. 2C, when the data recorded in the mapping table  419  is modified, this data can be stored into the MT n  of the physical page  311  of a special reserved block of mapping update. When the data is modified once again, the new mapping relation will be stored into the MT n+1 . When new record data are added, the new mapping relation will be written into the next page until fully written. Then, the special reserved block of mapping update will be erased, and renewal of data is started again from page 0 to be used as the data capable of being stored into a buffer  419  when the host computer is turned on next time. It is not necessary in the present invention to use the host computer  49  to scan logical addresses (e.g., the L value shown in FIG. 1B) for building anew a search table as in a conventional storage system. Therefore, the working procedure of the host computer  49  can be omitted, and the time of building and searching the mapping table can be greatly saved.  
         [0025]    Of course, the present invention is characterized in that data of the mapping table can be stored into pages of a physical block to facilitate direct and quick storage into the memory of the mapping table when the system is turned on.  
         [0026]    Furthermore, as shown in FIG. 3, the present invention comprises the following steps.  
         [0027]    Step  301 : After the host computer or the control device is turned on or electrified, the whole system is on standby;  
         [0028]    Step  302 : The system is waiting for the host computer to issue an instruction of writing in;  
         [0029]    Step  303 : When the host computer needs to access a file, the microprocessor of the control device utilizes the already processed LBA data introduced by the host computer to know in which segment the specified physical block address exists, and stores the data of mapping table of this segment from a page of a physical block into a mapping buffer;  
         [0030]    Step  304 : The microprocessor finds out the corresponding physical block of memory of the file to be accessed by the host computer through the data of mapping table, and stores the data to be written in at the host end into a sector buffer;  
         [0031]    Step  305 : The written in page in the old block is compared with the address to be written in to determine whether the instruction of writing in is duplicate. If the answer is negative, data are directly written into the old block without the need of modifying mapping relation; otherwise, Step  306  is performed;  
         [0032]    Step  306  (the data of some page in a physical block are to be duplicated): New data are written into a clean block reserved by the system;  
         [0033]    Step  307 : The data already stored in the old block and not to be modified are moved into this clean block;  
         [0034]    Step  308 : All data in the old block are erased to form another clean block reserved by the system to be used next time;  
         [0035]    Step  309 : Logical address data of the above block are modified and stored into the corresponding mapping table to build correct relations between them;  
         [0036]    Step  310 : Data of mapping table of the buffer are modified and stored into the next page of a special reserved block of mapping update to be used as the data capable of being conveniently searched and stored by the control device when the host computer is turned on next time.  
         [0037]    Finally, as shown in FIG. 4, a flowchart of building a mapping table of the present invention comprises the following steps.  
         [0038]    Step  401 : The system obtains the address of the mapping table of the page required to be loaded in through procession and conversion of the control device. In another embodiment of the present invention, the control device directly finds out the address of the mapping table via a special mark;  
         [0039]    Step  402 : The mapping table of the specified page is read from a reserved and not mapped block;  
         [0040]    Step  403 : Whether the ECC in the mapping table is erroneous is judged. If the answer is positive (i.e., abnormal disconnection or improper operation has occurred during the previous operations), Step  404  is performed; otherwise (i.e., the previous operations are OK), Step  405  is performed;  
         [0041]    Step  404 : The corresponding relation of the previous mapping table must be retraced. The latest previous mapping page in the special reserved block of mapping update is read again into the memory;  
         [0042]    Step  405 : The system continues performing operations.  
         [0043]    To sum up, the present invention relates to an algorithm of flash memory and, more particularly, to an algorithm of flash memory capable of quickly building a table and preventing disorder of data due to abnormal disconnection and a control system thereof.  
         [0044]    Although the present invention has been described with reference to the preferred embodiment thereof, it will be understood that the invention is not limited to the details thereof. Various substitutions and modifications have been suggested in the foregoing description, and other will occur to those of ordinary skill in the art. Therefore, all such substitutions and modifications are intended to be embraced within the scope of the invention as defined in the appended claims.