Page aligning method and lookup table generating method of data storage device

A page aligning method for a data storage device is provided. The data storage device includes a non-volatile memory and the page aligning method includes steps of: executing a system initialization on the non-volatile memory to obtain a remaining storage capacity; selecting a number from a lookup table as an initial storage capacity according to the remaining storage capacity and a lookup table; and referring the initial storage capacity as a fixed capacity in the data storage device and writing the initial storage capacity into the non-volatile memory. A lookup table generating method and the data storage device are also provided.

FIELD OF THE INVENTION

The present invention relates to a page aligning method of a data storage device, and more particularly to a page aligning method and a lookup table generating method of a data storage device capable of reducing hidden spaces.

BACKGROUND OF THE INVENTION

A data storage device, such as disk or portable disk, includes a non-volatile memory for storing data. The non-volatile memory includes a plurality of pages. In order to improve the reading speed of the data storage device, page alignment is executed on the storage space in the data storage device so as to make each record of data with a size identical to the storage capacity of a page to be written into a completely empty page. Namely, each record of data is written into one page, thereby avoiding the record of data being written across more than one page. However, in conventional page alignment, some pages are configured for not storing data and the remaining storage capacity are designed as empty pages for storing data. However, these pages configured for not storing data may be determined as unallocated space by the operating system and the pages are configured for not storing data may occupy too much storage space; therefore, the user may loss some storage space. In addition, when the data storage device is re-formatted and the file system parameters change accordingly, the effect of page alignment may be moot thus leading to a poor system performance.

SUMMARY OF THE INVENTION

Therefore, in order to achieve the purpose of page alignment without occupying too much storage space, the present invention provides a page aligning method for a data storage device. The data storage device includes a non-volatile memory and the page aligning method includes steps of: executing a system initialization on the non-volatile memory to obtain a remaining storage capacity; selecting a number from a lookup table as an initial storage capacity according to the remaining storage capacity and a lookup table; and referring the initial storage capacity as a fixed capacity in the data storage device and writing the initial storage capacity into the non-volatile memory.

The present invention further provides a lookup table generating method alignment of pages in a data storage device. The data storage device includes a non-volatile memory and the lookup table generating method includes steps of: setting a simulative initial storage capacity; setting a hidden space; simulating a formatting process on the simulative initial storage capacity without altering the hidden space to generate a valid storage capacity; and storing a current simulative initial storage capacity into a lookup table when the current valid storage capacity satisfies a predetermined condition and the hidden space is smaller than a default value.

The present invention still provides a data storage device. The data storage device includes a non-volatile memory and a memory controller. The non-volatile memory is for storing data, and includes a plurality of data blocks; and each of the data blocks includes a plurality of data pages. The memory controller is for controlling operations of the non-volatile memory and determining a valid storage capacity of the data storage device according to a fixed capacity stored in an information block.

The present invention still further provides a data storage device. The data storage device includes a plurality of data blocks and a memory controller. Each of the data blocks includes a plurality of data pages for storing data. The memory controller is for logically defining the data blocks into an information block and a plurality of remaining blocks and determining a valid storage capacity of the remaining storage capacity of the remaining blocks according to a fixed capacity.

In summary, because the present invention simulates various storage capacities in advance and selects one of the simulated storage capacities as the initial storage capacity which has passed a page alignment check, a data storage device adopting the initial storage capacity is page aligned accordingly. In addition, because the hidden space corresponding to the selected initial storage capacity is smaller than a default value, the data storage device is page aligned and the hidden space is not determined as an unallocated space by an operating system and less storage capacity is reserved/occupied.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

FIG. 1is a schematic block view of a system in accordance with an embodiment of the present invention. As shown inFIG. 1, the system of the present embodiment includes a host10and a data storage device20. The host10may be an electronic device such as a desktop computer or a tablet computer. The host10is electrically coupled to the data storage device20. The data storage device20is configured to receive a write command or a read command issued from the host10, write received data into the data storage device20according to the write command, or read data stored in the data storage device20according to the read command. The data storage device20includes a memory controller21and a non-volatile memory22. The memory controller21includes a microprocessor211and a register212. The microprocessor211is electrically coupled to the register212. The non-volatile memory22may be a data storage medium such as a flash memory, MRAM (Magnetic RAM), FRAM (Ferroelectric RAM), PCM (Phase Change Memory), STTRAM (Spin-Transfer Torque RAM), ReRAM (Resistive RAM), Memristor or other memory-like device suitable for long-term data storage. The non-volatile memory22includes a plurality of blocks for storing data. Each of the blocks includes a plurality of pages. Each of the pages includes a plurality of areas. Before storing any data, the non-volatile memory22has an original storage capacity. The microprocessor211is electrically coupled to the non-volatile memory22and configured to write data into or read data from the non-volatile memory22according to the write command or the read command.

Manufacturer performs an initiation process on the data storage device20via the host10when the data storage device20is in the manufacturing stage. The initiation process mainly includes a system initialization and a low-level format. The system initialization is for generating an information block (or blocks).FIG. 2is a schematic illustration of a distribution of a storage capacity of the non-volatile memory22. As shown inFIG. 2, the storage capacity of information block237occupies a portion of the storage capacity of the non-volatile memory22. The information block mainly includes in-system programming firmware and product information. The product information includes the basic information about the data storage device20, such as: the manufacturer number, the product model, the storage capacity of the pages in the non-volatile memory22(e.g., 16 kilobytes (KB)), the size of data protection area and the bad block record table. The storage capacity of the bad blocks which is prohibited to be accessed by the user is included into the storage capacity of information block237. When the system initialization is completed, the information block is written into the non-volatile memory22and an initial storage capacity232of the data storage device20is determined. As shown inFIG. 2, the initial storage capacity232of the non-volatile memory22is referred to as the capacity deducting the storage capacity of information block237from the original storage capacity231.

When the low-level format is executed, the memory controller21generates format data according to a specific file system. The specific file system may be FAT (File Allocation Table), EXFAT (Extended File Allocation Table) or NTFS (New Technology File System) which are commonly used in Windows operating system or EXT (Extended File System) which is commonly used in Linux operating system. Taking the SD (Secure Digital) disk as an example, the file system specification drafted by the SD disk association (version 3.0 and the release date: Apr. 16, 2009) provides various suggestions for file systems according to the data storage devices with different available storage capacities. For example, FAT32 is suggested as the file system if the valid storage capacity is ranged from 2 gigabytes (GB) to 32 GB. Different operating systems define different sizes of clusters for the data storage devices20with different original storage capacities; wherein each cluster includes a plurality of sectors with a size of 512 bytes (B) for example. Taking Windows 7.0 and FAT32 as an example, the default cluster has a size of 4 KB if the valid storage capacity is ranged from 256 megabytes (MB) to 8 GB.

To simplify the description of the present invention, FAT32 is taken as an example for the description of the present invention, but the present invention is not limited thereto. As shown inFIG. 2, the storage capacity of deducting a storage capacity of format data238from the initial storage capacity232is referred to as a valid storage capacity233. The format data mainly includes the MBR (Master Boot Record) and the System Area. The valid storage capacity233may correspond to the user area, which is defined in FAT32 and for storing data. It is noted that the content of the MBR is unaltered in the high-level format unless the low-level format is executed again.

For the convenience in use, the manufacturer may execute the high-level format on the data storage device20after the initiation process directly. To achieve page alignment, the manufacturer may reserve a specific capacity in the storage capacity of format data238, and the specific capacity may be determined as an unallocated space by the operating system. Otherwise, the effect of page alignment may be moot when the user re-executes the high-level format and thus leading to a poor system performance of the data storage device20if without the reserved specific capacity.

To overcome the aforementioned problem, the present invention provides a page aligning method for a data storage device and a cooperative lookup table generating method.FIG. 3is a flow chart of a lookup table generating method in accordance with an embodiment of the present invention. First, executing step S301: setting a simulative initial storage capacity. The simulative initial storage capacity is for simulating the initial storage capacity and its size is not limited to the below exemplary numbers. For example, the simulative initial storage capacity may be set to 32 MB in one embodiment, but the present invention is not limited thereto. Thereafter, executing step S303: setting a hidden space. The size of the hidden space is not limited to the below exemplary number. For example, the hidden space may be set to 0 in one embodiment, but the present invention is not limited thereto. The hidden space may be located between the system area and the user area defined in FAT32; or, the hidden space may be located in the system area and adjacent to the MBR technically, wherein the hidden space is not supposed to store any data.

Thereafter, executing step S305: simulating the low-level and high-level formats without altering the hidden space and thereby generating the valid storage capacity inFIG. 2. Specifically, the host10simulates the low-level format on the data storage device20and assumes that there is only one partition initially; wherein the result of the aforementioned simulation generates the format data. The MBR in the format data includes, for example, four partition tables and each of which records the start address and the capacity of the respective partition in the valid storage capacity; and therefore, the host10knows the start address and the capacity of each partition. Because there is one partition (e.g., the first partition) only, pages in the user area are aligned if the start address of the first partition has page alignment. It is noted that the capacity of the partition is the valid storage capacity233. The start address of the first partition table may vary with the size of the hidden space. For example, the start address of the first partition table is, for example, the 1000thsector if the size of the hidden space is 0; and, the start address of the first partition table is, for example, the 1032thsector if the size of the hidden space increases to 32 sectors.

Thereafter, executing step S307: determining whether the valid storage capacity are page aligned, that is, determining whether the storage capacity of the user area is N times of the capacity of one page. If the determination result obtained in step S307is no, then executing step S309: increasing the hidden space. In one embodiment, the hidden space is increased to 32 sectors, but the present invention is not limited thereto. Then, steps S305and S307are re-executed sequentially.

Alternatively, if the determination result obtained in step S307is yes, then executing step S311: determining whether the current hidden space is smaller than a default value. In one embodiment, the aforementioned default value is 15 MB, but the present invention is not limited thereto. In one preferred embodiment, the aforementioned default value is equal to a value that the operating system determines the existence of the unallocated space. If the determination result obtained in step S311is yes which indicates that the current valid storage capacity233is page aligned and the corresponding hidden space is not determined as the unallocated space by the operating system, then executing step S313: storing the current simulative initial storage capacity into a lookup table. Thereafter, executing step S315: increasing the simulative initial storage capacity. In one embodiment, the simulative initial storage capacity is increased to 128 sectors, but the present invention is not limited thereto. Then steps S303is re-executed.

In general, a lookup table has huge content; therefore, to simply the description of the present invention, only three simulative initial storage capacities 31.55 GB, 31.7 GB and 32.1 GB are exemplarily listed in the lookup table ofFIG. 4. If the determination result obtained in step S311is no which indicates that the current simulative initial storage capacity cannot meet the requirement of the present invention, then steps S315and S303are executed sequentially. Once all of the possible initial storage capacities such as 32 MB-2 terabytes (TB) are simulated, the lookup table generating method of the present invention ends.

To achieve the purpose of the present invention, the page aligning method for a data storage device of the present invention is implemented based on the initial storage capacity of the data storage device20set according to the lookup table of the present invention.FIG. 5is a flow chart of a page aligning method for a data storage device in accordance with an embodiment of the present invention andFIG. 6is another schematic illustration of a distribution of a storage capacity of the non-volatile memory22. Please refer toFIGS. 5 and 6together. First, executing step S501: executing the system initialization to generate the information block and obtain a remaining storage capacity236in the data storage device20. Because the information block is written into the non-volatile memory22in the system initialization, the data storage capacity of the data storage device20(or the non-volatile memory22) is changed to the remaining storage capacity236by the original storage capacity231; wherein the remaining storage capacity236is referred to as the capacity deducting the storage capacity of information block237from the original storage capacity231.

Thereafter, executing step S503: selecting a number from a lookup table of the present invention as the initial storage capacity232of the data storage device20according to the remaining storage capacity236; wherein the initial storage capacity232is smaller than the remaining storage capacity236. The initial storage capacity232is selected from the simulative initial storage capacities in the lookup table of the present invention. In one preferred embodiment, the initial storage capacity232is smaller than and most closes to the remaining storage capacity236. For example, if the remaining storage capacity236is 32 GB, the host10selects 31.7 GB (which is smaller than and most closes to 32 GB) from the lookup table ofFIG. 4as the initial storage capacity232of the data storage device20. The difference234between the initial storage capacity232(e.g., 31.7 GB) and the remaining storage capacity236(e.g., 32 GB) is 0.3 GB, which can be referred to as or added into the capacity of the spare blocks. The aforementioned spare blocks are for replacement. Specifically, when a block stored with data needs a refresh, the stored data needs to move to an empty spare block first and then the block originally stored with the data is erased and be a spare block. In order to provide sufficient numbers of spare blocks, in another embodiment the initial storage capacity232is smaller than the remaining storage capacity236and the difference between the two is greater than a threshold (e.g., 0.4 GB) or 1% of the remaining storage capacity236(e.g., 0.32 GB). Therefore, the host10selects 31.55 GB from the lookup table ofFIG. 4as the initial storage capacity232of the data storage device20due to the difference234between the two is 0.45 GB which satisfies the threshold.

Thereafter, executing step S505: writing the selected initial storage capacity232into the information block. Thereafter, the page aligning method for a data storage device of the present invention ends. Because the data storage device20provides the function of fixed capacity, the data storage device20always replies the same initial storage capacity232which has passed the simulations of the low-level and high-level formats when the host10asks for the initial storage capacity232of the data storage device20. Therefore, when the host10executes the real low-level and high-level formats on the data storage device20, the data storage device20performs the steps S307and S309to insert the hidden space thereby achieving the effect of page alignment. As a result, the purpose of the present invention is achieved without having to record the hidden space in the lookup table of the present invention, sacrificing page alignment in the data storage device20and having unallocated space.

In summary, because the lookup table generating method of the present invention simulates the formatting steps performed while manufacturing the data storage device20, the storage capacity can be aligned is simulated accurately and the corresponding hidden space would not determined as unallocated space by the operating system. In addition, because the storage capacity occupied by format data generated by every formatting is identical, the storage capacity in the user area is still page aligned even the user executes formatting after the data storage device20is manufactured. Namely, pages in the data storage device20would remain aligned after the format is re-executed.