Non-volatile memory based storage system capable of directly overwriting without using redundancy and its writing method

A non-volatile memory based storage system capable of directly overwriting without using redundancy and its writing method are provided. The invention first writes data into a register. Then, a portion of MCF information of the decoded logical writing destination address is taken as a physical writing address and used to determine whether there is data in a block corresponding to the physical writing address. If yes, a new swap block is taken out from a swap table and at least one record of data in the register is written into the swap block.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a non-volatile memory based storage system and its writing method and, more particularly, to a non-volatile memory based storage system capable of directly overwriting without using redundancy and its method, so as to increase the data access efficiency.

2. Description of Related Art

Typically, an erasing operation for deleting a previously recorded data is required prior to writing data into a flash memory. Thus, a relatively long period of time is required for data writing. This is a drawback of the flash memory. Therefore, there is a need to develop a non-volatile memory capable of being overwritten without the erasing operation. It is envisaged that such non-volatile memory can increase an access efficiency of data.

For writing data into the flash memory, a plurality of blocks in the flash memory are employed as a writing unit. Generally, several bytes at the end of each block is taken as a redundancy field for recording a data writing status of the block and information related to other blocks. As such, it is required to check the redundancy of a target block prior to writing data into the same, resulting in an increase of writing time. Furthermore, the available space for writing data into a block is undesirably reduced because the redundancy occupies a portion of the limited storage space of each block to be written.

Therefore, it is desirable to provide a novel non-volatile memory based storage system capable of directly overwriting without using redundancy and its writing method in order to mitigate and/or obviate the aforementioned problem.

SUMMARY OF THE INVENTION

The object of the present invention is to provide a non-volatile memory based storage system capable of directly overwriting without using redundancy and its method, which can save time in writing data into non-volatile memory and prevent data from losing in case of an unexpected event while writing.

In one aspect of the present invention, a non-volatile memory based storage system capable of directly overwriting without using redundancy comprises: at least one non-volatile memory including a plurality of blocks wherein at least one block is stored with a system management table having a plurality of mapping control field (MCF) tables, each having a plurality of MCFs; and a register for storing at least one target data to be written into said at least one non-volatile memory, the register including a temporal MCF table having at least one MCF of the system management table; wherein a host executes a writing command to write said at least one target data into said at least one non-volatile memory and the writing command includes a target MCF number for writing said at least target data into said at least one non-volatile memory based on a target MCF of the temporal MCF table corresponding the target MCF number.

In another aspect of the present invention, there is provided a writing method for allowing a host to directly overwrite a non-volatile memory based storage system without using a redundancy. The storage system includes a register and at least one non-volatile memory having a plurality of blocks. The at least one block is used for storing a system management table including a plurality of mapping control field (MCF) tables, each having a plurality of MCFs, a table attribute (TA), a MCF table flag (MTF), a MCF table number (MTN), a MCF group number (MGN), and a plurality of swap block addresses, each MCF having a mapping physical block address (MPBA). The register having a temporal MCF table including at least one MCF of the system management table. The writing method comprises the steps of: (A) decoding a writing command from the host to obtain a logical writing destination address corresponding to the writing command wherein the logical writing destination address comprises the MCF number (MCFN) of a target MCF; (B) writing target data from the writing command into the register; (C) if the target MCF does not exist in the temporal MCF table, directly searching at least one MCF table containing the target MCF in the system management table based on a temporal MCF index table and a plurality of MGNs, and loading the at least one MCF table into the temporal MCF table; (D) taking the MPBA of the target MCF as a physical writing address of the at least one non-volatile memory; (E) if no data exists in at least one block corresponding to the physical writing address, writing at least one target data stored in the register into at least one block corresponding to the physical writing address; and (F) if data exists in at least one block corresponding to the physical writing address, taking at least one swap block out via at least one swap block address, writing said at least one target data stored in the register into said at least one swap block, and updating the temporal MCF table by the at least one swap block address.

Other objects, advantages, and novel features of the invention will become more apparent from the detailed description when taken in conjunction with the accompanying drawings.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

With reference toFIG. 1, there is shown a schematic diagram of a structure according to the invention comprising a host1and a storage system2. The host1is implemented as a computer having a microprocessor or a controller, or portable device (e.g., notebook, personal digital assistant (PDA)). The storage system2comprises a register3and a non-volatile memory module4. The register3comprises a first sector set A and a second sector set B. Each sector set comprises a plurality of sectors31. In this embodiment, preferably each sector set comprises four sectors31.

The register3further comprises a mapping control field (MCF) table32and an extension table which can be a swap table33or a temporal MCF index table34. The register3may be implemented as one of a variety of forms of storage. In this embodiment, preferably the register3is a random access memory (RAM).

The non-volatile memory module4comprises a plurality of non-volatile memory sections. In this embodiment, the non-volatile memory module4comprises non-volatile memories5,6, and7. The first non-volatile memory5comprises at least one data registers51, a plurality of data blocks52, a plurality of swap blocks53, a system management table54occupying at least one block, a block state table55for recording a state (e.g., good or bad) of all blocks in the first non-volatile memory section5, and a general information table56for storing parameters about system operations and MCF group index table. A detail about data format of the temporal MCF index table34will be described hereinafter.

In this embodiment, preferably the first non-volatile memory5comprises a data register51which preferably has four pages511. Each data block52of the first non-volatile memory5preferably has four pages521,522,523, and524, each having a size equal to that of the sector31of the register3and equal to that of a page511of the data register51. The non-volatile memory module4may be embedded into a portable device or assembled in a portable multimedia storage card, such as a Personal Computer Memory Card International Association (PCMCIA) card or a Security Digital (SD) card.

The second and third non-volatile memories6and7have their own block state tables64and74, respectively. The second non-volatile memory section6can be stored with a part of the system management table63if the system management table54is too large to be stored in the first non-volatile memory5. Furthermore, if the system management table63is still too large to be stored in the second non-volatile memory6, the remaining portion of the system management table63can be stored in the third non-volatile memory7. The system management table54comprises a plurality of MCF tables, i.e., a MCF table group including MCF table0, MCF table1, MCF table2, . . . , MCF table n. The fields and functions of the MCF tables are describes as follows.

With reference toFIG. 2a, there is shown a diagram of a first configuration of a MCF table according to the invention. The MCF table541(e.g., MCF table0) comprises a plurality of MCFs5411, a table attribute (TA)542, a MCF table flag (MTF)543, a MCF table number (MTN)544, a MCF group number (MGN)545, other information545, and a plurality of swap block addresses547.

With reference toFIG. 2b, there is shown the data format of the MCF according to the invention. The MCF comprises a data unit state (DUS)5412, a mapping device number (MDN)5413, and a mapping physical block address5414(MPBA). In this embodiment, preferably MCF table541has 256 MCFs5411.

Each MCF5411has a MDN5413for directly corresponding to one of the non-volatile memories5,6, and7. As a result, it is able to save time and thus increase the efficiency of writing data into a corresponding device. For instance, a MCF5411corresponds to the first non-volatile memory5if MDN=0, and corresponds to the second non-volatile memory section6if MDN=1. Each MCF5411further corresponds to a swap block address547. For example, MCF0directly corresponds to Swap0. Also, the swap block address547can be recycled. Moreover, each MCF5411can correspond to a plurality of swap block addresses547.

The TA542represents an attribute of the MCF table541(seeFIG. 2a). For instance, the TA542being ‘M’ represents a MCF table541. The TA542being ‘B’ represents a block state table55. The TA542being ‘G’ represents a general information table56. The MTN544represents a number of the MCF table541, such as MCF0, MCF1, . . . , MCF N.

The MTF543is used to remark the MTN544for solving the problem of two identical MTNs544appearing in the MCF table541. An algorithm of remarking will be described hereinafter. The MGN545represents a MCF group associated with the MCF table541. Notation ‘other’546represents other information about the MCF table541or is reserved for other uses.

With reference toFIG. 2c, there is shown a diagram of the temporal MCF index table34. The temporal MCF index table34comprises a plurality of MCF groups341, each comprising a using device number (UDN)3411, a table searching length (TSL)3412, and a searching begin address (SBA)3413. The MCF group341corresponds to the MGN545shown inFIG. 2b. In a case that the MCF5411corresponding to the target MTN544does not exist in the temporal MCF table32(see FIG.1), it is possible of directly searching and finding at least one MCF including a target MCF in the system management table54based on the temporal MCF index table34, and loading the found at least one MCF into the temporal MCF table32. For example, MCF group341is [00—001111b 0x1234h], in which ‘00’ represents that the corresponding MCF table541is stored in the non-volatile memory5(seeFIGS. 1 and 2a); ‘0x1234h’ represents the searching begin address (SBA); and ‘001111’ represents the TSL of a table to be searched. Hence, a MCF table541in the first non-volatile memory5is searched, and the searching range is from 0x1234h to 0x1244h (001111b+0x1234h=0x1244h). Alternatively, the above process for searching at least one MCF including a target MCF in the system management table54can be carried out by a hash finction searching or other searching method.

With reference toFIG. 3, there is shown a diagram of a second configuration of the MCF table and the data format of the MCF thereof according to the invention. The system management table54(seeFIG. 1) comprises a plurality of MCF tables548, each including a plurality of MCFs5481. Each MCF5481comprises a data unit state (DUS)5482, a MCF priority flag (MPF)5483, a MTN5484, other block information5485, and a MPBA5486, in which the MPF5483is substantially the same as the MTF543ofFIG. 2afor remarking the MTN5484.

FIG. 4is flow chart illustrating a process of writing data from the host1to the storage system2according to the invention. Also with reference toFIGS. 1 and 2a, andFIG. 5that illustrates the process of data writing according to the first embodiment of the invention, the host1first executes a writing command to the storage system2at an address 0x11021 in which there is only one data writing (step S201). Next, an address decoding (i.e., logical address conversion) is performed for obtaining a logical writing destination address corresponding to the writing command (step S202). The logical writing destination address has a MCFN5411.

Next, the target data is written into the register2and a search on a target MCF is performed (MCFN is 0x0006) (step S203). If the target MCF does not exist in the MCF table32, the temporal MCF index table34is used to search the MCF table including the target MCF in the system management table54for obtaining MCF information (step S204). If the target MCF exists, MCF information can be obtained. MCF information comprises DUS5412(0000b), MDN5413(0000b), and MPBA5414(0x1234).

Then, the DUS5412is used to determine the writing state of the physical mapping block corresponding to the target MCF. If the first bit of the DUS5412is in a logical high state (i.e., 1) it indicates that the first page of the physical mapping block is not free. On the contrary, if the first bit of the DUS5412is in a logical low state (i.e., 0), it represents that the first page of the physical mapping block is free and data writing is permitted. In response, one target data stored in the register is written into a second page (e.g., Page1) in the physical mapping block having a physical address of 1234h (step S205). Alternatively, if one bit of the DUS5412is in a logical high state, it represents that the physical mapping block is not free. As such, data is required to be written into a free swap block.

With reference toFIG. 6, there is shown a second preferred embodiment of the present invention. Also with reference toFIGS. 1,2a, and4, it is shown that the block corresponding to the physical writing address is not free, and a data writing is performed via at least one swap block. The process of writing target data of this second embodiment is similar to that of the first embodiment. The only difference is that the DUS5412of the target MCF is 1000b; i.e., there is data in the block corresponding to a physical writing address (MPBA=80 0x1234) (at Page0). The existing original data is moved to the first sector set A of the register3.

If the original data in a block corresponding to the physical writing address overwrites data to be written (i.e., target data) in the register3, the original data in the block has to be discarded. In this embodiment, the original data doesn't overwrite target data because the target data is written into the sector A-1of the register3and the original data is written into the sector A-0of the register3. Each MCF corresponds to at least one swap block address (seeFIG. 2a). As such, a valid free block is obtained via a swap block address547directly corresponding to the target MCF. The obtained block is served as a new MPBA writing address of the target MCF (step S206). This can prevent data failure in case of an unexpected event (e.g., power out) while writing.

With reference toFIG. 7, there is shown a flow chart illustrating a process of writing data into an updated swap block according to the second preferred embodiment of the invention. A swap block address directly corresponding to the target MCF (1234h) is served as a new writing block of the target MCF (step S206). Next, data stored in the register3(i.e., at sectors A-0to A-1) is written into the Page0to Page1of the new swap block (2566h) respectively (step S207). MPBA5414of MCF5411(0x0006) in temporal MCF table32of the register3is updated. That is, MPBA5414in MCF having a value of 0x0006 in MCF5411of the original temporal MCF table32is updated as 2566h (step S208). Next, block at 1234h is released to become a free swap block. Also, the swap block address547is updated as 1234h for providing a swap block for a next use. Moreover, the swap block address can be recycled for increasing an access efficiency of the swap block (step S209).

Next, an updating of the system management table54is performed. In detail, a swap block at the same MCF table group is obtained. A remark on MTF543is performed to represent a priority of MCF table having the same number in the same group, so as to determine, when there exist two MCF tables having the same number of544, which one is the most effective and most recently updated (step S210). In this embodiment, preferably three setting values α, β, and γ are used for determining the priority. Also, such α, β, and γ follow an algorithm: α has a priority lower than that of β; β has a priority lower than that of γ; and γ has a priority lower than that of α.

The MTF543of the updated MCF table is remarked as β when MTF543of the original MTN544in the system management table53is α. As such, MTF543remarked as β can be used to access the most recently updated MCF table (β) in a next access of MCF table. Furthermore, MTN544(α) is treated as old information which will be overwritten by a next updating of swap block address547, thereby achieving the purpose of recycle.

Data is first written into the data register51in the first non-volatile memory5when data in the register3is to be written into the first non-volatile memory5. Next, data is written into a target block in the first non-volatile memory5. Hence, at least one page is taken as a writing unit of the first non-volatile memory5in each writing of target data. For example, if there are four records of data to be written. The first record of data is written into sector A-0in the register3(see FIG.1). After confirming that data is capable of writing into the corresponding block, data is written into a first page in data register51of the first non-volatile memory5. Then, the second, third, and fourth records of data are written sequentially. The writing operation of each of the second, third, and fourth records of data is the same as that of the first record of data. As a result, data writing is performed by going through the data register51from the register3.

Furthermore, the data in the data register51is written into the corresponding physical block at one time. Therefore, at least one page (at most four pages) of data in the data register51is written into the corresponding block per writing. This can achieve a set interleaving of writing data into the corresponding block of the first non-volatile memory5.

The writing process implemented in either embodiment can use another MCF data format shown in FIG.3. The extension table of the register3is implemented as a swap table33. The swap table33comprises a plurality of free swap block addresses for being able to access a free swap block via the swap table33. Furthermore, a counter is provided in the swap table33for counting the number of free blocks that have been accessed. The swap table33is loaded with free block addresses from the system management table54in the initial state. Thereafter, new added free blocks are used cyclically for increasing an access efficiency of the free blocks.

In view of the foregoing, it is known that the invention utilizes a decoded MCF information as a physical writing address. Further, a portion of the MCF information is used to determine whether there is data in the physical writing address of a block. If there is data in the corresponding block, a new swap block is taken out via a swap block address. At least one record of data in the register is then written into a data register in the corresponding non-volatile memory. Finally, data is written into the corresponding blocks sequentially. This can save time and thus increase the efficiency of writing data into a corresponding device. Furthermore, the time required to write data into the non-volatile memory section is reduced, and data can be prevented from losing in writing due to an unexpected event. In addition, it is possible of determining a writing state of a target block to be written without writing data into a redundancy of the target block.