CN106372000B - Mapping table updating method, memory control circuit unit and memory storage device - Google Patents

Abstract

The present invention proposes a mapping table update method, a memory control circuit unit and a memory storage device. The method includes allocating a mapping table storage space in a buffer memory to store a physical address-logical address mapping table; determining whether the remaining storage space of the mapping table storage space is less than a threshold value; if the remaining storage space is less than the threshold value, updating the mapping information of the physical address-logical address mapping table stored in the mapping table storage space to at least one logical address-physical address mapping table, and clearing the mapping information of the physical address-logical address mapping table stored in the mapping table storage space; and storing the updated mapping information corresponding to the programmed actuated physical erase unit in the mapping table storage space. The present invention can avoid the situation where the programmed data cannot be restored due to the programming failure of other physical programming units after updating the mapping table.

Description

Mapping table update method, memory control circuit unit and memory storage device

technical field

The present invention relates to a mapping table updating method, in particular to a logical address-physical address mapping table updating method for a rewritable non-volatile memory module, a memory control circuit unit and a memory storage device.

Background technique

The rapid growth of digital cameras, mobile phones, and MP3 players has led to a rapid increase in consumer demand for storage media. Since rewritable non-volatile memory (rewritable non-volatile memory) has the characteristics of data non-volatility, power saving, small size, no mechanical structure, fast read and write speed, etc., in recent years, rewritable non-volatile memory The memory industry has become a very popular part of the electronics industry. For example, a solid-state drive using flash memory as a storage medium has been widely used as a hard disk of a computer host to improve the access performance of the computer.

A memory storage device that uses a rewritable non-volatile memory module as a storage medium will establish a logical address-physical address mapping table to record the mapping information between logical units and physical units, so that the host system can smoothly access the rewritable non-volatile memory module. data of the volatile memory block. For example, when the host system intends to write data, the memory storage device can program the data into the physical unit, and update the mapping relationship between the logical unit and the physical unit of the data to the logical address-physical address mapping table. Specifically, the memory storage device loads the logical address-physical address mapping table corresponding to the logical unit into the buffer memory for updating.

And because the logic unit that the host system wants to write data each time may correspond to different logical address-physical address mapping tables, in order to avoid frequently updating the logical address-physical address mapping tables, the memory storage device will allocate a temporary storage space to store The mapping table is temporarily stored, and the data to be written is programmed into the active entity erasing unit, and the mapping relationship between the logic unit to which the data belongs and the operating entity erasing unit is stored in the temporary storage space. When the temporary storage space is full, the mapping information of the temporary storage mapping table stored in the temporary storage space is updated to the logical address-physical address mapping table once.

However, the amount of data actually programmable to each physical unit may be different (for example, the data is compressed), that is, each physical unit may be mapped to a different number of logical units. Therefore, the size of the mapping information corresponding to each entity unit in the temporary storage mapping table will also be different. In this way, when the temporary storage space is full, it may result in a situation that the erasing unit of the actuating entity has not been fully written. And in this case, because the temporary storage space is full, the control circuit of the memory storage device will update the mapping information of the temporary storage mapping table stored in the temporary storage space to the logical address-physical address mapping table, and write The entered data is programmed to the unprogrammed physical programming unit in the active physical erasing unit according to the programming sequence.

For example, a physical erasing unit of a multi-level cell (Multi Level Cell, MLC) NAND flash memory includes a lower physical programming unit (also known as a fast page) and an upper physical programming unit (also known as a slow page). After updating the mapping information of the temporary storage mapping table to the logical address-physical address mapping table, if the data to be written is programmed to the upper physical programming unit in the active physical erasing unit according to the programming sequence, a programming error occurs (For example, an unexpected power failure occurs), which will cause errors in the data of the programmed lower physical programming unit corresponding to the upper physical programming unit. However, since the logical address-physical address mapping table has been updated, there is no way to know the old address of the data, and the data cannot be recovered.

Contents of the invention

Embodiments of the present invention provide a mapping table update method, a memory control circuit unit, and a memory storage device, which can efficiently update the logical address-physical address mapping table, and avoid the programmed A condition in which data cannot be recovered due to programming failure of other physical programming cells.

An embodiment of the present invention provides a method for updating a mapping table, which is used in a memory storage device. The memory storage device has a rewritable nonvolatile memory module. The rewritable non-volatile memory module has a plurality of physical erasing units, and each physical erasing unit has a plurality of physical programming units. The method for updating the mapping table includes: allocating a mapping table storage space in the buffer memory to store the physical address-logical address mapping table; judging whether the remaining storage space in the mapping table storage space is less than a first threshold; if judging that the remaining storage space is less than The first threshold value is to update the mapping information of the physical address-logical address mapping table stored in the mapping table storage space to at least one logical address-physical address mapping table; clear the physical address-logic address stored in the mapping table storage space The mapping information of the address mapping table; and programming a plurality of writing data belonging to a plurality of logical programming units to a plurality of physical programming units of an actuating physical erasing unit among the physical erasing units, establishing the programming described A plurality of updated mapping information between the physical programming unit and the logical programming unit of the data is written, and the updated mapping information is stored in the storage space of the mapping table.

In an embodiment of the present invention, the above-mentioned step of storing the updated mapping information in the mapping table storage space includes: when storing a part of the updated mapping information in the mapping table storage space and the When the remaining storage space is not greater than the second threshold value, it is judged whether there is at least one first physical programming unit in the active physical erasing unit, wherein the at least one first physical programming unit is a lower physical programming unit, and the at least one The first physical programming unit has been programmed with valid data and the upper physical programming unit corresponding to the at least one first physical programming unit has not been programmed; if it is determined that the at least one first physical programming unit is stored in the active physical erasing unit , then program the dummy data to the upper physical programming unit corresponding to the at least one first physical programming unit; after programming the dummy data to the upper physical programming unit corresponding to the at least one first physical programming unit, the data stored in the mapping The mapping information of the physical address-logical address mapping table in the table storage space is updated to at least one logical address-physical address mapping table; and the mapping information of the physical address-logical address mapping table stored in the mapping table storage space is cleared and all The remaining part of the updated mapping information is stored in the storage space of the mapping table.

In an embodiment of the present invention, a plurality of updated mapping information corresponding to a plurality of programmed physical erase units has been stored in the above-mentioned mapping table storage space.

In an embodiment of the present invention, the above-mentioned mapping table updating method further includes: calculating the size of the update mapping information of one of the programmed physical erasing units corresponding to the programmed physical erasing unit, wherein the one of the programmed physical erasing units The programming physical erasing unit is the last programmed physical erasing unit before the write data is programmed to a plurality of physical programming units of the actuating physical erasing unit; and an update map of one of the programmed physical erasing units is set The size of the information is used as the first threshold.

In an embodiment of the present invention, the above-mentioned mapping table updating method further includes: calculating the size of the update mapping information corresponding to each programmed physical erasing unit; calculating the size of the updating mapping information of the programmed physical erasing unit the average value of ; and setting the average value as the first threshold value.

In an embodiment of the present invention, the above-mentioned mapping table updating method further includes: calculating the size of the update mapping information corresponding to each programmed physical erasing unit; identifying the size of the updating mapping information corresponding to the programmed physical erasing unit a maximum value among the sizes; and setting the maximum value as the first threshold value.

In an embodiment of the present invention, at least a part of the written data is data generated by compressing multiple pieces of original data received from the host system.

An embodiment of the present invention provides a memory control circuit unit for controlling a rewritable non-volatile memory module of a memory storage device. The rewritable non-volatile memory module has a plurality of physical erasing units, and each physical erasing unit has a plurality of physical programming units. The memory control circuit unit includes: a host interface, a memory interface and a memory management circuit. The host interface is electrically connected to the host system; the memory interface is electrically connected to the rewritable non-volatile memory module; and the memory management circuit is electrically connected to the host interface and the memory interface. The memory management circuit is used to allocate the mapping table storage space in the buffer memory to store the physical address-logical address mapping table. In addition, the memory management circuit is also used to judge whether the remaining storage space in the mapping table storage space is less than a first threshold value . If it is determined that the remaining storage space is smaller than the first threshold, the memory management circuit is further configured to update the mapping information of the physical address-logical address mapping table stored in the mapping table storage space to at least one logical address-physical address mapping table. Furthermore, the memory management circuit is also used for clearing the mapping information of the physical address-logical address mapping table stored in the mapping table storage space. In addition, the memory management circuit is also used to program multiple pieces of writing data belonging to multiple logical programming units to a plurality of physical programming units of an actuating physical erasing unit among the physical erasing units, and to establish programming of the physical erasing unit. A plurality of updated mapping information between the physical programming unit of data and the logical programming units is written, and the updated mapping information is stored in the storage space of the mapping table.

In an embodiment of the present invention, when a part of the updated mapping information is stored in the storage space of the mapping table and the remaining storage space of the storage space of the mapping table is not greater than the second threshold value, the memory management circuit is also used to determine the Whether there is at least one first physical programming unit in the active physical erasing unit, wherein the at least one first physical programming unit is a lower physical programming unit, and the at least one first physical programming unit has been programmed with valid data and corresponds to the The upper physical programming unit of the at least one first physical programming unit is not programmed. In addition, if it is determined that the at least one first physical programming unit exists in the active physical erasing unit, the memory management circuit is also used to program dummy data to the upper physical programming unit corresponding to the at least one first physical programming unit . Moreover, after programming the dummy data to the upper physical programming unit corresponding to the at least one first physical programming unit, the memory management circuit is also used to store the mapping information of the physical address-logical address mapping table in the mapping table storage space Updating to at least one logical address-physical address mapping table. Moreover, the memory management circuit is also used for clearing the mapping information of the physical address-logical address mapping table stored in the mapping table storage space and storing the rest of the updated mapping information in the mapping table storage space.

In an embodiment of the present invention, a plurality of updated mapping information corresponding to a plurality of programmed physical erase units has been stored in the above-mentioned mapping table storage space.

In an embodiment of the present invention, the above-mentioned memory management circuit is also used to calculate the size of the update mapping information of one of the programmed physical erase units corresponding to the programmed physical erase unit, wherein the one of the programmed physical erase units The erasing unit is the last programmed physical erasing unit before programming the write data to the plurality of physical programming units that activate the physical erasing unit. Moreover, the memory management circuit is also used to set the size of the update mapping information of one of the programmed physical erase units as the first threshold value.

In an embodiment of the present invention, the above-mentioned memory management circuit is also used to calculate the size of the update mapping information corresponding to each programmed physical erasing unit. In addition, the memory management circuit is also used to calculate the average value of the size of the updated mapping information of the programmed physical erasing units, and set the average value as the first threshold value.

In an embodiment of the present invention, the above-mentioned memory management circuit is also used to calculate the size of the update mapping information corresponding to each programmed physical erasing unit. In addition, the memory management circuit is also used to identify the maximum value among the sizes of the update mapping information corresponding to the programmed physical erasing units, and set the maximum value as the first threshold value.

In an embodiment of the present invention, at least a part of the written data is data generated by compressing multiple pieces of original data received from the host system through the memory management circuit.

An embodiment of the present invention provides a memory storage device, including: a connection interface unit, a rewritable non-volatile memory module, and a memory control circuit unit. The connection interface unit is used to electrically connect to the host system; the rewritable non-volatile memory module includes a plurality of entity erasing units; the memory control circuit unit is electrically connected to the connection interface unit and the rewritable non-volatile memory module . The memory control circuit unit is used for allocating the mapping table storage space in the buffer memory for storing the physical address-logic address mapping table. In addition, the memory control circuit unit is also used to determine whether the remaining storage space in the storage space of the mapping table is smaller than a first threshold value. If it is determined that the remaining storage space is smaller than the first threshold, the memory control circuit unit is further configured to update the mapping information of the physical address-logical address mapping table stored in the mapping table storage space to at least one logical address-physical address mapping table. Furthermore, the memory control circuit unit is also used for clearing the mapping information of the physical address-logical address mapping table stored in the mapping table storage space. In addition, the memory control circuit unit is also used to program multiple pieces of write data belonging to multiple logical programming units to a plurality of physical programming units of an actuating physical erasing unit among the physical erasing units, so as to establish programming A plurality of updated mapping information between the physical programming unit and the logical programming unit in which the data is written, and store the updated mapping information in the storage space of the mapping table.

In an embodiment of the present invention, when a part of the updated mapping information is stored in the mapping table storage space and the remaining storage space in the mapping table storage space is not greater than the second threshold value, the memory control circuit unit is further used to judging whether there is at least one first physical programming unit in the active physical erasing unit, wherein the at least one first physical programming unit is a lower physical programming unit, and the at least one first physical programming unit has programmed valid data and corresponds to An upper physical programming unit of the at least one first physical programming unit is not programmed. In addition, if it is determined that the at least one first physical programming unit exists in the operating physical erasing unit, the memory control circuit unit is also used to program dummy data to the upper physical programming unit corresponding to the at least one first physical programming unit. unit. Moreover, after programming the dummy data to the upper physical programming unit corresponding to the at least one first physical programming unit, the memory control circuit unit is also used to map the physical address-logical address mapping table stored in the mapping table storage space The information is updated to at least one logical address-physical address mapping table. Furthermore, the memory control circuit unit is also used for clearing the mapping information of the physical address-logical address mapping table stored in the mapping table storage space and storing the rest of the updated mapping information in the mapping table storage space.

In an embodiment of the present invention, a plurality of updated mapping information corresponding to a plurality of programmed physical erase units has been stored in the above-mentioned mapping table storage space.

In an embodiment of the present invention, the above-mentioned memory control circuit unit is also used to calculate the size of the update mapping information of one of the programmed physical erasing units corresponding to the programmed physical erasing unit, wherein the one of the programmed physical erasing units The physical erasing unit is the last programmed physical erasing unit before the write data is programmed into the plurality of physical programming units that activate the physical erasing unit. Moreover, the memory control circuit unit is also used to set the update mapping information size of one of the programmed physical erasing units as the first threshold value.

In an embodiment of the present invention, the memory control circuit unit is further used to calculate the size of the update mapping information corresponding to each programmed physical erase unit. In addition, the memory control circuit unit is also used to calculate the average value of the size of the updated mapping information of the programmed physical erasing units, and set the average value as the first threshold value.

In an embodiment of the present invention, the memory control circuit unit is further used to calculate the size of the update mapping information corresponding to each programmed physical erase unit. In addition, the memory control circuit unit is also used to identify the maximum value among the sizes of the update mapping information corresponding to the programmed physical erasing units, and set the maximum value as the first threshold value.

In an embodiment of the present invention, at least a part of the written data is data generated by compressing multiple pieces of original data received from the host system through the memory control circuit unit.

Based on the above, the mapping table update method, memory control circuit unit, and memory storage device provided by the embodiments of the present invention can improve the update efficiency of the logical address-physical address mapping table, and avoid the programmed The data cannot be recovered due to programming failure of other physical programming units.

In order to make the above-mentioned features and advantages of the present invention more comprehensible, the following specific embodiments are described in detail with reference to the accompanying drawings.

Description of drawings

FIG. 1 is a schematic diagram of a host system and a memory storage device shown in an embodiment of the present invention;

2 is a schematic diagram of a computer, an input/output device and a memory storage device shown in an embodiment of the present invention;

3 is a schematic diagram of a host system and a memory storage device shown in an embodiment of the present invention;

4 is a schematic block diagram of a memory storage device shown in an embodiment of the present invention;

5 is a schematic block diagram of a memory control circuit unit shown in an embodiment of the present invention;

FIG. 6A and FIG. 6B are exemplary schematic diagrams of a management entity erasing unit shown in an embodiment of the present invention;

FIG. 7A, FIG. 7B and FIG. 7C are exemplary schematic diagrams of storing the updated mapping information of the actuating entity erasing unit in the storage space of the mapping table shown in the embodiment of the present invention;

FIG. 8 is a schematic diagram of an example of storing part of the updated mapping information of the active entity erasing unit in the storage space of the mapping table shown in the embodiment of the present invention;

FIG. 9 is a schematic diagram of the arrangement order of the physical programming units shown in the embodiment of the present invention;

FIG. 10A and FIG. 10B are exemplary schematic diagrams of programming dummy data to an upper physical programming unit that operates a physical erasing unit shown in an embodiment of the present invention;

FIG. 11 is a flowchart of a method for updating a mapping table shown in an embodiment of the present invention;

FIG. 12 is another exemplary flow chart of the method for updating the mapping table shown in the embodiment of the present invention.

Explanation of reference signs:

10: memory storage device;

11: host system;

12: computer;

13: input/output device;

122: microprocessor;

124: random access memory (RAM);

126: system bus;

128: Data transmission interface

21: mouse;

22: keyboard;

23: Display;

24: printer;

25: Pen drive;

26: memory card;

27: SSD;

31: digital camera;

32: SD card;

33: MMC card;

34: memory stick;

35: CF card;

36: embedded storage device;

402: connect the interface unit;

404: memory control circuit unit;

406: a rewritable non-volatile memory module;

410(0)～410(N): entity erasing unit;

502: memory management circuit;

504: host interface;

506: memory interface;

508: buffer memory;

510: power management circuit;

512: error checking and correction circuit;

514: data compression/decompression circuit;

602: data area;

604: idle area;

606: system area;

608: replace area;

610(0)～610(D): logic address;

701, 801: mapping table storage space;

UM0, UM1, UM2, UM3: update mapping information;

PBA(0-0)～PBA(0-K): Entity programming unit;

W(0)～W(L): character line;

D0～D5: valid data

DD: dummy data

S1101, S1103, S1105, S1107, S1109, S1111, S1201, S1203, S1205, S1207: Steps in the method for updating the mapping table.

Detailed ways

Generally speaking, a memory storage device (also called a memory storage system) includes a rewritable non-volatile memory module and a controller (also called a control circuit). Typically memory storage devices are used with a host system such that the host system can write data to or read data from the memory storage device.

FIG. 1 is a schematic diagram of a host system and a memory storage device according to an embodiment of the present invention, and FIG. 2 is a schematic diagram of a computer, an input/output device and a memory storage device according to an embodiment of the present invention.

Referring to FIG. 1 , the host system 11 generally includes a computer 12 and an input/output (input/output, I/O for short) device 13 . The computer 12 includes a microprocessor 122 , a random access memory (random access memory, RAM for short) 124 , a system bus 126 and a data transmission interface 128 . The input/output device 13 includes a mouse 21 , a keyboard 22 , a monitor 23 and a printer 24 as shown in FIG. 2 . It must be understood that the device shown in FIG. 2 is not limited to the input/output device 13, and the input/output device 13 may also include other devices.

In this embodiment, the memory storage device 10 is electrically connected to other components of the host system 11 through the data transmission interface 128 . Data can be written into the memory storage device 10 or read from the memory storage device 10 through the operation of the microprocessor 122 , the random access memory 124 and the input/output device 13 . For example, the memory storage device 10 may be a rewritable non-volatile memory storage device such as a flash drive 25, a memory card 26, or a solid state drive (Solid State Drive, SSD for short) 27 as shown in FIG. 2 .

FIG. 3 is a schematic diagram of a host system and a memory storage device shown in an embodiment of the present invention.

In general, host system 11 is any system that can cooperate substantially with memory storage device 10 to store data. Although in this embodiment, the host system 11 is described as a computer system, however, in another embodiment, the host system 11 may be a digital camera, video camera, communication device, audio player or video player and other systems. For example, when the host computer system is a digital camera (video camera) 31 among Fig. 3, the rewritable non-volatile memory storage device is an SD card 32, an MMC card 33, a storage stick (memory stick) 34, CF card 35 or embedded storage device 36 (as shown in FIG. 3 ). The embedded storage device 36 includes an embedded multimedia card (Embedded MMC, eMMC for short). It is worth mentioning that the embedded multimedia card is directly electrically connected to the substrate of the host system.

FIG. 4 is a schematic block diagram of a memory storage device shown in an embodiment of the present invention.

Referring to FIG. 4 , the memory storage device 10 includes a connection interface unit 402 , a memory control circuit unit 404 and a rewritable non-volatile memory module 406 .

In this embodiment, the connection interface unit 402 is compatible with the Serial Advanced Technology Attachment (SATA) standard. However, it must be understood that the present invention is not limited thereto, and the connection interface unit 402 may also conform to the Parallel Advanced Technology Attachment (PATA) standard, the Institute of Electrical and Electronic Engineers (Institute of Electrical and Electronic Engineers, IEEE) 1394 standard, Peripheral Component Interconnect Express (PCI Express) standard, Universal Serial Bus (Universal Serial Bus, referred to as USB) standard, Ultra High Speed-I (UHS-I for short) interface Standard, Ultra High Speed-II (UHS-II) interface standard, Secure Digital (Secure Digital, SD) interface standard, Memory Stick (Memory Stick, referred to as MS) interface standard, Multi Media Card (Multi Media Card, MMC for short) interface standard, Compact Flash (CF for short) interface standard, Integrated Device Electronics (IDE) standard, or other suitable standards. In this embodiment, the connection interface unit and the memory control circuit unit can be packaged in a chip, or arranged outside a chip including the memory control circuit unit.

The memory control circuit unit 404 is used to execute a plurality of logic gates or control instructions realized in the form of hardware or software, and write and read data in the rewritable non-volatile memory module 406 according to the instructions of the host system 11. Fetch and erase operations.

The rewritable non-volatile memory module 406 is electrically connected to the memory control circuit unit 404 and used for storing data written by the host system 11 . The rewritable non-volatile memory module 406 has physical erasing units 410(0)˜410(N). For example, the physical erase units 410(0)˜410(N) may belong to the same memory die or belong to different memory dies. Each physical erasing unit has a plurality of physical programming units, wherein the physical programming units belonging to the same physical erasing unit can be written independently and erased simultaneously. However, it must be understood that the present invention is not limited thereto, and each physical erasing unit may be composed of 64 physical programming units, 256 physical programming units, or any other number of physical programming units.

In more detail, the physical erasing unit is the smallest unit of erasing. That is, each physical erase unit contains a minimum number of memory cells that are erased. The entity programming unit is the smallest unit of programming. That is, the physical programming unit is the minimum unit for writing data. Each physical programming unit generally includes a data bit field and a redundant bit field. The data bit field contains a plurality of physical access addresses for storing user data, and the redundant bit field is used for storing system data (eg, control information and error correction code). In this embodiment, the data bit area of each physical programming unit includes 8 physical access addresses, and the size of one physical access address is 512 bytes. However, in other embodiments, the data bit area may also include more or less physical access addresses, and the present invention does not limit the size and number of physical access addresses. For example, in one embodiment, the physical erasing unit is a physical block, and the physical programming unit is a physical page or a physical sector, but the invention is not limited thereto.

In this embodiment, the rewritable non-volatile memory module 406 is a Multi Level Cell (MLC) NAND flash memory module (that is, a flash memory module that can store 2 data bits in one memory cell). However, the present invention is not limited thereto, and the rewritable non-volatile memory module 406 may also be a single-level storage cell (Single Level Cell, referred to as SLC) NAND flash memory module (that is, a flash memory that can store 1 data bit in a storage unit) module), complex-level storage cell (Trinary Level Cell, TLC for short) NAND flash memory module (that is, a flash memory module that can store 3 data bits in a storage unit), other flash memory modules, or other memory modules with the same characteristics.

FIG. 5 is a schematic block diagram of a memory control circuit unit shown in an embodiment of the present invention.

Referring to FIG. 5 , the memory control circuit unit 404 includes a memory management circuit 502 , a host interface 504 and a memory interface 506 .

The memory management circuit 502 is used to control the overall operation of the memory control circuit unit 404 . Specifically, the memory management circuit 502 has a plurality of control instructions, and when the memory storage device 10 is operating, these control instructions are executed to perform operations such as writing, reading, and erasing data.

In this embodiment, the control instructions of the memory management circuit 502 are implemented in the form of software. For example, the memory management circuit 502 has a microprocessor unit (not shown) and a read-only memory (not shown), and these control instructions are burned into the read-only memory. When the memory storage device 10 is in operation, these control instructions will be executed by the microprocessor unit to perform operations such as writing, reading, and erasing data.

In another embodiment of the present invention, the control instructions of the memory management circuit 502 can also be stored in a specific area of the rewritable non-volatile memory module 406 in the form of program code (for example, the system area dedicated to storing system data in the memory module )middle. In addition, the memory management circuit 502 has a microprocessor unit (not shown), a read only memory (not shown), and a random access memory (not shown). In particular, the ROM has a driver code, and when the memory control circuit unit 404 is enabled, the microprocessor unit will first execute the driver code segment to store the data stored in the rewritable non-volatile memory module 406. The control instructions are loaded into the random access memory of the memory management circuit 502 . Afterwards, the microprocessor unit executes these control instructions to perform operations such as writing, reading and erasing data.

The host interface 504 is electrically connected to the memory management circuit 502 and is used to electrically connect to the connection interface unit 402 to receive and identify commands and data transmitted by the host system 11 . That is to say, the commands and data sent by the host system 11 are sent to the memory management circuit 502 through the host interface 504 . In this embodiment, the host interface 504 is compatible with the SATA standard. However, it must be understood that the present invention is not limited thereto, and the host interface 504 may also be compatible with PATA standard, IEEE 1394 standard, PCI Express standard, USB standard, UHS-I interface standard, UHS-II interface standard, SD standard, MS standard, MMC standard, CF standard, IDE standard or other suitable data transmission standards.

The memory interface 506 is electrically connected to the memory management circuit 502 and used for accessing the rewritable non-volatile memory module 406 . That is to say, the data to be written into the rewritable non-volatile memory module 406 will be converted into a format acceptable to the rewritable non-volatile memory module 406 through the memory interface 506 .

In one embodiment, the memory control circuit unit 404 further includes a buffer memory 508 , a power management circuit 510 , an error checking and correction circuit 512 and a data compression/decompression circuit 514 .

The buffer memory 508 is electrically connected to the memory management circuit 502 and used for temporarily storing data and instructions from the host system 11 or data from the rewritable non-volatile memory module 406 .

The power management circuit 510 is electrically connected to the memory management circuit 502 and used to control the power of the memory storage device 10 .

The error checking and correcting circuit 512 is electrically connected to the memory management circuit 502 and used for executing error checking and correcting procedures to ensure the correctness of data. Specifically, when the memory management circuit 502 receives a write command from the host system 11, the error checking and correcting circuit 512 will generate a corresponding error checking and correcting code (Error Checking and Correcting Code) for the data corresponding to the write command. , ECC Code for short), and the memory management circuit 502 will write the data corresponding to the write command and the corresponding ECC code into the rewritable non-volatile memory module 406 . Afterwards, when the memory management circuit 502 reads data from the rewritable non-volatile memory module 406, it will simultaneously read the error checking and correction code corresponding to the data, and the error checking and correction circuit 512 will read the error checking and correction code according to the error checking and correction code. The correction code performs error checking and correction procedures on the read data.

The data compression/decompression circuit 514 is electrically connected to the memory management circuit 502 . Here, the data compression/decompression circuit 514 is used to compress the data to be written into the rewritable non-volatile memory module 406 and to decompress the data read from the rewritable non-volatile memory module 406 data. For example, the data compression/decompression circuit 514 includes a compressor and a decompressor. The compressor can be used to find out the data redundancy existing in the original data (original data), remove the found redundancy, encode the remaining necessary data and output the encoding result (ie, compressed data). The decompressor is used to decode the read-in compressed data according to predetermined steps and send out the decoding result (that is, decompressed data (decompressed data). In this exemplary embodiment, the data compression/decompression circuit 514 uses no Distortion compression algorithm to compress data so that the compressed data can be restored.

FIG. 6A and FIG. 6B are exemplary schematic diagrams of the erasing unit of the management entity shown in the embodiment of the present invention.

It must be understood that when describing the operation of the physical erasing unit of the rewritable non-volatile memory module 106, words such as "extract", "group", "divide", and "associate" are used to operate physical erase A unit is a logical concept. That is to say, the actual position of the physical erasing unit of the rewritable non-volatile memory module is not changed, but the physical erasing unit of the rewritable non-volatile memory module is logically operated.

Please refer to FIG. 6A, the memory control circuit unit 404 (or the memory management circuit 502) will logically group the physical erasing units 410(0)-410(N) into a data area 602, an idle area 604, a system area 606, and a replacement area. 608.

The physical erase units logically belonging to the data area 602 and the free area 604 are used to store data from the host system 11 . Specifically, the physical erasing unit of the data area 602 is regarded as a physical erasing unit of stored data, and the physical erasing unit of the spare area 604 is a physical erasing unit used to replace the data area 602 . That is to say, when receiving the write command and the data to be written from the host system 11, the memory management circuit 502 will extract the physical erase unit from the spare area 604, and write the data into the extracted physical erase unit. In the unit, replace the physical erase unit of the data area 602.

The physical erase units logically belonging to the system area 606 are used to record system data. For example, the system data includes the manufacturer and model of the rewritable nonvolatile memory module, the number of physically erased units of the rewritable nonvolatile memory module, the number of physically programmed units per physically erased unit, and the like.

Physically erased units logically belonging to the replacement area 608 are used for bad physically erased unit replacement procedures to replace damaged physically erased units. Specifically, if there are still normal physical erasing units in the replacement area 608 and the physical erasing units in the data area 602 are damaged, the memory management circuit 502 will extract normal physical erasing units from the replacement area 608 to replace the damaged ones. The physical erasing unit of .

In particular, the numbers of physical erase units in the data area 602 , spare area 604 , system area 606 and replacement area 608 vary according to different memory specifications. In addition, it must be understood that during the operation of the memory storage device 10 , the grouping relationship of the physical erasing unit associated with the data area 602 , the spare area 604 , the system area 606 and the replacement area 608 will change dynamically. For example, when a physically erased unit in the spare area 604 is damaged and replaced by a physically erased unit in the replacement area 608 , the original physically erased unit in the replacement area 608 will be associated with the spare area 604 .

Referring to FIG. 6B , as mentioned above, the physical erasing units of the data area 602 and the free area 604 store the data written by the host system 11 in an alternate manner. In this embodiment, the memory control circuit unit 404 (or the memory management circuit 502) configures logical addresses 610(0)-610(D) to the host system 11 to map to the physical erase unit 414 in the data area 602 (0)-410(F-1), so as to facilitate data access in the physical erasing units that store data in the aforementioned alternate manner. In particular, the host system 11 accesses the data in the data area 602 through logical addresses 610(0)˜610(D). In addition, the memory control circuit unit 404 (or the memory management circuit 502 ) establishes a logical address-physical address mapping table to record the mapping relationship between logical units and physical units. This logical address-physical address mapping table can, for example, record the mapping relationship between logical address and physical erasing unit, logical address and physical programming unit, logical programming unit and physical erasing unit, and/or logical programming unit and physical programming unit The correspondence between various logics and entities, etc., is not limited in the present invention.

In this embodiment, the rewritable non-volatile memory module 406 of the memory storage device 10 may be managed on a physical programming unit basis (also referred to as a page basis). For example, when executing a write command, regardless of which logical programming unit the current data is to be written into, the memory control circuit unit 404 (or the memory management circuit 502) will write in the form of one physical programming unit following one physical programming unit. input data (also known as random write mechanism). Specifically, the memory control circuit unit 404 (or the memory management circuit 502 ) extracts an empty physical erasing unit from the spare area 604 as an active physical erasing unit to write data. And, when the active physical erasing unit is full, the memory control circuit unit 404 (or the memory management circuit 502) will extract another empty physical erasing unit from the spare area 604 as the active physical erasing unit , to continue writing data corresponding to the write command from the host system 11 .

In this embodiment, the memory control circuit unit 404 (or the memory management circuit 502) allocates a mapping table storage space in the buffer memory 508 to store a physical address-logical address mapping table (physical address-logical address mapping table), To record the mapping relationship between the programmed physical programming unit of the active entity erasing unit and the logical programming unit to which the data belongs. In this embodiment, the data programmed into the physical programming unit may be compressed or uncompressed. Therefore, one physical programming unit can map one or more logical programming units. If a physical programming unit is mapped to a logical programming unit (for example, the data programmed to the actuating entity erasing unit is not compressed), when the actuating entity erasing unit is full, multiple The size of the updated mapping information formed by the multiple mapping relationships between the physical programming unit and the multiple logical programming units is exactly 1 unit. The memory control circuit unit 404 (or the memory management circuit 502 ) can allocate 4 units of storage space in the buffer memory 508 as the mapping table storage space to store the physical address-logical address mapping table. However, more or less storage space may be allocated as the storage space of the mapping table according to actual needs, which is not limited by the present invention.

FIG. 7A , FIG. 7B and FIG. 7C are exemplary schematic diagrams of storing the updated mapping information of the erasing unit of the actuating entity in the storage space of the mapping table shown in the embodiment of the present invention.

Please refer to FIG. 7A , for the convenience of description, the present embodiment starts from the fact that no physical erasing unit has been associated with the data area. The memory control circuit unit 404 (or the memory management circuit 502 ) allocates the mapping table storage space 701 of 4 units of storage space in the buffer memory 508 to store the physical address-logical address mapping table. When the memory control circuit unit 404 (or memory management circuit 502) receives a write command to write data into a logical address from the host system 11, the memory control circuit unit 404 (or memory management circuit 502) will extract a An empty physical erase unit (ie, physical erase unit 410(0)) acts as an active physical erase unit. The memory control circuit unit 404 (or the memory management circuit 502 ) will program data into the physical programming units of the physical erasing unit 410 ( 0 ) according to the programming sequence of the physical programming units that activate the physical erasing unit. The memory control circuit unit 404 (or the memory management circuit 502) establishes update mapping information according to the mapping relationship between the programmed physical programming unit in the physical erasing unit 410 (0) and the logical programming unit to which the data belongs, and stores the update mapping information to the mapping table storage space 701. When the active physical erasing unit (that is, the physical erasing unit 410 (0)) is full, the memory control circuit unit 404 (or the memory management circuit 502) will extract another empty physical erasing unit 410 ( 1) Erasing the unit as a new operating entity to store the data of subsequent write commands.

In this embodiment, when the active physical erasing unit is full and another empty physical erasing unit needs to be selected from the idle area 604 as a new active physical erasing unit, the memory control circuit unit 404 (or memory The management circuit 502) will determine whether to update the logical address-physical address mapping table. Specifically, the memory control circuit unit 404 (or the memory management circuit 502) will estimate whether the remaining storage space of the mapping table storage space 701 can completely store the update mapping information corresponding to a physical erasing unit, and then decide whether to store The mapping information of the physical address-logical address mapping table in the mapping table storage space 701 is updated to the logical address-physical address mapping table. In this embodiment, the memory control circuit unit 404 (or the memory management circuit 502 ) determines whether the remaining storage space of the mapping table storage space 701 is smaller than a specific first threshold. If the remaining storage space is less than the first threshold value, the memory control circuit unit 404 (or the memory management circuit 502) will load the corresponding logical address-physical address mapping table according to the mapping information stored in the physical address-logical address mapping table 701 to the buffer memory 508, and update the mapping information to the logical address-physical address mapping table.

In this embodiment, the first threshold may be set as the size of the updated mapping information stored in the mapping table storage space 701 corresponding to one of the programmed physical erasing units. For example, one of the physical erase units may be the last programmed physical erase unit before selecting a new active physical erase unit.

In this embodiment, when the physical erasing unit 410 (0) is full and the physical erasing unit 410 (1) is selected as a new actuating physical erasing unit, the memory control circuit unit 404 (or memory management circuit 502) The size of the updated mapping information UM0 corresponding to the programmed physical erase unit 410(0) in the mapping table storage space 701 is calculated as 1 unit, and the remaining storage space of the mapping table storage space 701 is 3 units. At this time, the last programmed physical erase unit before selecting a new active physical erase unit is the physical erase unit 410(0). Therefore, the memory control circuit unit 404 (or the memory management circuit 502 ) sets the size (ie, 1 unit) of the update mapping information UM0 of the physical erasing unit 410 ( 0 ) as the first threshold value. Further, the memory control circuit unit 404 (or the memory management circuit 502) will judge that the remaining storage space (ie, 3 units) of the mapping table storage space 701 is not less than the first threshold value (ie, 1 unit), without updating the logical address-entity Address mapping table. That is to say, the updated mapping information of the new active entity erasing unit can be stored in the mapping table storage space 701 .

Referring to FIG. 7B, the memory control circuit unit 404 (or the memory management circuit 502) selects the physical erasing unit 410(1) as the active physical erasing unit, and programs data into the physical erasing unit 410(1). The memory control circuit unit 404 (or the memory management circuit 502) establishes update mapping information according to the mapping relationship between the programmed physical programming unit in the physical erasing unit 410(1) and the logical programming unit to which the data belongs, and stores the update mapping information in In the mapping table storage space. When the physical erasing unit 410 (1) is full, the memory control circuit unit 404 (or the memory management circuit 502) calculates the update mapping of the programmed physical erasing unit 410 (1) in the physical address-logical address mapping table 701 The size of the information UM1 is 1.5 units.

At this time, the mapping table storage space 701 has stored the updated mapping information UM0 corresponding to the physical erasing unit 410(0) and the updated mapping information UM1 corresponding to the physical erasing unit 410(1), wherein the size of the updated mapping information UM0 is 1 unit, the size of the update mapping information UM1 is 1.5 units. The memory control circuit unit 404 (or the memory management circuit 502 ) calculates that the remaining storage space of the mapping table storage space 701 is 1.5 units. The last programmed physical erase unit before selecting a new active physical erase unit is the physical erase unit 410 ( 1 ). Therefore, the memory control circuit unit 404 (or the memory management circuit 502 ) sets the size (ie, 1.5 units) of the update mapping information UM1 of the physical erasing unit 410(1) as the first threshold value. Further, the memory control circuit unit 404 (or the memory management circuit 502 ) determines that the remaining storage space (ie 1.5 units) is not less than the first threshold (ie 1.5 units), thereby not updating the logical address-physical address mapping table. That is to say, the updated mapping information of the new active entity erasing unit can be stored in the mapping table storage space 701 .

Referring to FIG. 7C, the memory control circuit unit 404 (or the memory management circuit 502) selects the physical erasing unit 410(2) as the active physical erasing unit, and programs data into the physical erasing unit 410(2). The memory control circuit unit 404 (or the memory management circuit 502) establishes update mapping information according to the mapping relationship between the programmed physical programming unit in the physical erasing unit 410(2) and the logical programming unit to which the data belongs, and stores the update mapping information in In the mapping table storage space 701. When the entity erasing unit 410 (2) is full, the memory control circuit unit 404 (or the memory management circuit 502) calculates the updated mapping information UM2 corresponding to the programmed entity erasing unit 410 (2) in the mapping table storage space 701 The size is 1 unit.

At this time, the mapping table storage space 701 has stored the updated mapping information UM0 corresponding to the physical erasing unit 410 (0), the updated mapping information UM1 corresponding to the physical erasing unit 410 (1) and the corresponding physical erasing unit 410 (2) The size of the update mapping information UM2 is 1 unit, the size of the update mapping information UM1 is 1.5 units, and the size of the update mapping information UM2 is 1 unit. The memory control circuit unit 404 (or the memory management circuit 502 ) calculates that the remaining storage space of the mapping table storage space 701 is 0.5 units. The last programmed physical erase unit before selecting a new active physical erase unit is physical erase unit 410(2). Therefore, the memory control circuit unit 404 (or the memory management circuit 502 ) sets the size (ie, 1 unit) of the update mapping information UM1 of the physical erasing unit 410(2) as the first threshold value. Further, the memory control circuit unit 404 (or the memory management circuit 502 ) judges that the remaining storage space (ie 0.5 units) is less than the first threshold (ie 1 unit), and needs to update the logical address-physical address mapping table. That is to say, the mapping table storage space 701 may not be able to completely store the update mapping information corresponding to a new actuating entity erasing unit, and the mapping information of the physical address-logical address mapping table stored in the mapping table storage space 701 needs to be Store in the logical address-physical address mapping table, and clear the mapping information of the physical address-logical address mapping table in the mapping table storage space 701 .

In another embodiment of the present invention, the first threshold value can also be set as the maximum value among the sizes of the updated mapping information corresponding to each programmed physical erase unit stored in the mapping table storage space.

For example, referring to FIG. 7A , at this moment, the mapping table storage space 701 only stores the update mapping information UM0 of the corresponding entity erasing unit 410 (0), wherein the size of the update mapping information UM0 is 1 unit, and the mapping table storage space 701 The remaining storage space is 3 units. The memory control circuit unit 404 (or the memory management circuit 502 ) identifies that the size of the update mapping information UM0 of the physical erase unit 410 ( 0 ) is the maximum among the sizes of the update map information corresponding to each programmed physical erase unit. Therefore, the memory control circuit unit 404 (or the memory management circuit 502 ) sets the size (ie, 1 unit) of the update mapping information UM0 of the physical erasing unit 410 ( 0 ) as the first threshold value. Further, the memory control circuit unit 404 (or the memory management circuit 502) judges that the remaining storage space (ie, 3 units) of the mapping table storage space 701 is not less than the first threshold value (ie, 1 unit), thereby not updating the logical address-entity Address mapping table.

For example, please refer to FIG. 7B. At this time, the mapping table storage space 701 has stored the update mapping information UM0 corresponding to the entity erasing unit 410 (0) and the update mapping information UM1 corresponding to the entity erasing unit 410 (1), wherein the update The size of the mapping information UM0 is 1 unit, the size of the update mapping information UM1 is 1.5 units, and the remaining storage space of the mapping table storage space 701 is 1.5 units. The memory control circuit unit 404 (or the memory management circuit 502 ) identifies that the size of the update mapping information UM1 of the physical erase unit 410(1) is the maximum among the sizes of the update map information corresponding to each programmed physical erase unit. Therefore, the memory control circuit unit 404 (or the memory management circuit 502 ) sets the size (ie, 1.5 units) of the update mapping information UM1 of the physical erasing unit 410(1) as the first threshold value. Further, the memory control circuit unit 404 (or the memory management circuit 502) judges that the remaining storage space (ie, 1.5 units) of the mapping table storage space 701 is not less than the first threshold value (ie, 1.5 units), and thus does not update the logical address-entity Address mapping table.

For example, please refer to FIG. 7C. At this time, the mapping table storage space 701 has stored the update mapping information UM0 of the corresponding entity erasing unit 410 (0), the update mapping information UM1 of the corresponding entity erasing unit 410 (1) and the corresponding entity The updated mapping information UM2 of the erasing unit 410 (2), wherein the size of the updated mapping information UM0 is 1 unit, the size of the updated mapping information UM1 is 1.5 units, the size of the updated mapping information UM2 is 1 unit, and the mapping table storage space 701 The remaining storage space of is 0.5 units. The memory control circuit unit 404 (or the memory management circuit 502 ) identifies that the size of the update mapping information UM1 of the physical erase unit 410(1) is the maximum among the sizes of the update map information corresponding to each programmed physical erase unit. Therefore, the memory control circuit unit 404 (or the memory management circuit 502 ) sets the size (ie, 1.5 units) of the update mapping information UM1 of the physical erasing unit 410(1) as the first threshold value. Further, the memory control circuit unit 404 (or the memory management circuit 502) judges that the remaining storage space (ie, 0.5 units) of the mapping table storage space 701 is less than the first threshold value (ie, 1.5 units), and will store in the mapping table storage space 701 The mapping information of the physical address-logical address mapping table in is stored in the logical address-physical address mapping table, and the mapping information of the physical address-logical address mapping table in the mapping table storage space 701 is cleared.

In the above-mentioned embodiment, the first threshold is set as the size of the update mapping information stored in the mapping table storage space 701 corresponding to one of the programmed physical erasing units. However, in another embodiment of the present invention, the first threshold value may also be set as an average value of the update mapping information corresponding to each programmed physical erase unit stored in the mapping table storage space.

For example, referring to FIG. 7A , at this moment, the mapping table storage space 701 only stores the update mapping information UM0 of the corresponding entity erasing unit 410 (0), wherein the size of the update mapping information UM0 is 1 unit, and the mapping table storage space 701 The remaining storage space is 3 units. The memory control circuit unit 404 (or the memory management circuit 502 ) calculates the average value of the size of the update mapping information corresponding to each programmed physical erase unit as 1 unit, and sets the first threshold as 1 unit. Further, the memory control circuit unit 404 (or the memory management circuit 502) judges that the remaining storage space (ie, 3 units) of the mapping table storage space 701 is not less than the first threshold value (ie, 1 unit), and does not update the logical address-physical address mapping surface.

For example, please refer to FIG. 7B. At this time, the mapping table storage space 701 has stored the update mapping information UM0 corresponding to the entity erasing unit 410 (0) and the update mapping information UM1 corresponding to the entity erasing unit 410 (1), wherein the update The size of the mapping information UM0 is 1 unit, the size of the update mapping information UM1 is 1.5 units, and the remaining storage space of the mapping table storage space 701 is 1.5 units. The memory control circuit unit 404 (or the memory management circuit 502 ) calculates the average value of the update mapping information corresponding to each programmed physical erase unit as 1.25 units, and sets the first threshold as 1.25 units. Further, the memory control circuit unit 404 (or the memory management circuit 502) judges that the remaining storage space (ie, 1.5 units) of the mapping table storage space 701 is not less than the first threshold value (ie, 1.25 units), and does not update the logical address-physical address mapping surface.

For example, please refer to FIG. 7C. At this time, the mapping table storage space 701 has stored the updated mapping information UM0 of the corresponding entity erasing unit 410 (0), the updated mapping information UM1 of the corresponding entity erasing unit 410 (1) and the corresponding entity The updated mapping information UM2 of the erasing unit 410 (2), wherein the size of the updated mapping information UM0 is 1 unit, the size of the updated mapping information UM1 is 1.5 units, the size of the updated mapping information UM2 is 1 unit, and the mapping table storage space 701 The remaining storage space of is 0.5 units. The memory control circuit unit 404 (or the memory management circuit 502 ) calculates the average value of the update mapping information corresponding to each programmed physical erase unit as 1.17 units, and sets the first threshold as 1.17 units. Further, the memory control circuit unit 404 (or the memory management circuit 502) judges that the remaining storage space (that is, 0.5 units) of the physical address-logical address mapping table 701 is less than the first threshold value (that is, 1.17 units), and stores in the mapping table The mapping information of the physical address-logical address mapping table in the space 701 is stored in the logical address-physical address mapping table, and the mapping information of the physical address-logical address mapping table in the mapping table storage space 701 is cleared.

Because, the present invention estimates whether the remaining storage space of the mapping table storage space can completely store a new actuating entity with the size of the update mapping information corresponding to each programmed entity erasing unit stored in the mapping table storage space Update mapping information for erase units. Therefore, when the size of the updated mapping information of the new actuating entity erasing unit is not as expected, but greater than the remaining storage space of the mapping table storage space, it will form that the actuating entity erasing unit is not fully written, and the mapping table storage space is only The case where a part of the update mapping information corresponding to the new active entity erasure unit is stored is already full.

FIG. 8 is a schematic diagram of an example of storing part of the updated mapping information of the erasing unit of the active entity in the storage space of the mapping table shown in the embodiment of the present invention.

Referring to FIG. 8 , the physical erasing unit 410 ( 0 ) and the physical erasing unit 410 ( 1 ) are programmed physical erasing units. When the physical erasing unit 410 (0) and the physical erasing unit 410 (1) are full, the mapping table storage space 801 stores the update mapping information UM0 of the corresponding physical erasing unit 410 (0), and the corresponding physical erasing unit 410 (0) The updated mapping information UM1 of the dividing unit 410(1), wherein the size of the updated mapping information UM0 is 1 unit, the size of the updated mapping information UM1 is 1.5 units, and the remaining storage space is 1.5 units. The memory control circuit unit 404 (or the memory management circuit 502) selects the physical erasing unit 410(2) as the active physical erasing unit. The memory control circuit unit 404 (or the memory management circuit 502) sets the size ( That is, 1.5 units) as the first threshold. Further, the memory control circuit unit 404 (or the memory management circuit 502) judges that the remaining storage space (ie 1.5 units) of the mapping table storage space 801 is not less than the first threshold value (ie 1.5 units), and does not update the logical address-physical address mapping table. Therefore, the memory control circuit unit 404 (or the memory management circuit 502) programs the data into the physical erasing unit 410(2), and according to the programmed physical programming unit in the physical erasing unit 410(2) and the logical programming to which the data belongs The mapping relationship of the units establishes updated mapping information, and stores the updated mapping information in the mapping table storage space 801 .

In this embodiment, the memory control circuit unit 404 (or the memory management circuit 502) can further determine whether the remaining storage space of the mapping table storage space 801 is not greater than the second threshold value, so as to determine whether to determine whether to activate the entity erasing unit ( That is, whether the physical erasing unit 410(2)) can be programmed is the upper physical programming unit in sequence. The second threshold can be smaller than the first threshold, or equal to zero (that is, the mapping table storage space 801 is full), or set according to actual needs, which is not limited by the present invention. The following will describe the case where the second threshold value is zero.

In this embodiment, in fact, when the physical erasing unit 410 (2) is full, according to the mapping relationship between the programmed physical programming unit in the physical erasing unit 410 (2) and the logical programming unit to which the data belongs The size of the updated mapping information is 2 units, but the remaining storage space of the mapping table storage space 801 can only store 1.5 units of updated mapping information. Therefore, the mapping table storage space 801 has only stored the part of the update mapping information UM3 corresponding to the entity erasing unit 410 (2) (that is, the size of the part of the update mapping information UM3 is 1.5 units) has been filled, but the entity erasing Cell 410(2) is not yet full.

When the mapping table storage space 801 is full, that is to say, there is no remaining storage space in the mapping table storage space 801 to store and update the mapping information, the physical address-logical address mapping table stored in the mapping table storage space 801 The mapping information is updated to the logical address-physical address mapping table, and the mapping information of the physical address-logical address mapping table in the mapping table storage space 801 is cleared. However, since the actuating entity erasing unit (i.e., the entity erasing unit 410(2)) has not been fully written, the memory control circuit unit 404 (or the memory management circuit 502) will first judge the operation before updating the logical address-physical address mapping table. The physical erasing unit (ie, the physical erasing unit 410( 2 )) is determined in order whether the physical programming unit that can be programmed is the upper physical programming unit. Specifically, the memory control circuit unit 404 (or the memory management circuit 502) will determine whether there is a lower physical programming unit programmed with valid data in the active physical erasing unit (that is, the physical erasing unit 410(2)), and this The upper physical programming unit corresponding to the lower physical programming unit has not been programmed yet. If it is judged that the above-mentioned lower physical programming unit exists in the active physical erasing unit (i.e., the physical erasing unit 410(2), the memory control circuit unit 404 (or the memory management circuit 502) will program a dummy data into In the upper physical programming unit corresponding to the above lower physical programming unit.

FIG. 9 is a schematic diagram of the arrangement sequence of physical programming units shown in the embodiment of the present invention. Here, the physical erasing unit 410(2) is taken as an example for illustration, and the structures of other physical erasing units can also be deduced in the same way.

Referring to FIG. 9, the physical erasing unit 410(2) includes physical programming units PBA(0-0)˜PBA(0-K). For example, in this embodiment, K is an integer. For example, K is 255. Entity programming unit PBA(0-0) and entity programming unit PBA(0-2) are composed of memory cells on the word line W(0); entity programming unit PBA(0-1) and entity programming unit PBA(0 -4) is composed of memory cells on word line W(1); physical programming unit PBA(0-3) and physical programming unit PBA(0-6) are formed by memory cells on word line W(2) Composition; Entity programming unit PBA (0-5) and entity programming unit PBA (0-8) are constituted by memory cells on the word line W (3); and by analogy, entity programming unit PBA (0-(K -4)) and the entity programming unit PBA (0-(K-1)) are composed of memory cells on the word line W (L-1) and the entity programming unit PBA (0-(K-2)) and the entity Program cells PBA(0-K) are composed of memory cells on word line W(L). Here, the entity programming units PBA(0-0), PBA(0-1), PBA(0-3), PBA(0-5), ..., PBA(0-(K-4)), PBA(0 -(K-2)) is the lower entity programming unit, and the entity programming unit PBA (0-2), PAB (0-4), PBA (0-6), PBA (0-8), ..., PBA (0 -(K-1)), PBA(0-K) are the upper entity programming units.

FIG. 10A and FIG. 10B are exemplary schematic diagrams of programming dummy data into an upper physical programming unit that operates a physical erasing unit according to an embodiment of the present invention.

Please refer to FIG. 10A, when the mapping table storage space 801 is full, the entity programming unit of the active entity erasing unit (that is, the entity erasing unit 410 (2)) having programmed valid data is the lower entity programming unit PBA (0- 0), PBA(0-1), PBA(0-3) and the upper entity programming units PBA(0-2), PBA(0-4). Wherein, the memory control circuit unit 404 (or the memory management circuit 502) judges that the upper physical programming unit PBA (0-6) corresponding to the lower physical programming unit PBA (0-3) of the physical erasing unit 410 (2) has not been programmed . Based on this, the memory control circuit unit 404 (or the memory management circuit 502) will first program the dummy data to the upper physical programming unit PBA (0-6) of the physical erasing unit 410 (2), and then store the dummy data in the mapping table. The mapping information of the physical address-logical address mapping table in the space 801 is updated to the logical address-physical address mapping table, and the mapping information of the physical address-logical address mapping table in the mapping table storage space 801 is cleared.

Please refer to FIG. 10B. In another embodiment of the present invention, when the mapping table storage space 801 is full, the physical programming unit that has programmed valid data in the physical erasing unit (i.e., the physical erasing unit 410(2)) is activated. Programming units PBA(0-0), PBA(0-1), PBA(0-3), PBA(0-5) for the lower entity and PBA(0-2), PBA(0-4) for the upper entity . Wherein, the memory control circuit unit 404 (or the memory management circuit 502) judges the upper entity programming unit PBA (0-6) corresponding to the lower entity programming unit PBA (0-3) of the entity erasing unit 410 (2) and the lower entity The upper physical programming units PBA(0-8) corresponding to the programming units PBA(0-5) have not been programmed yet. Based on this, the memory control circuit unit 404 (or the memory management circuit 502) will program dummy data to the upper physical programming unit PBA(0-6) and the upper physical programming unit PBA(0-8) of the physical erasing unit 410(2). ), update the mapping information of the physical address-logical address mapping table in the mapping table storage space 801 to the logical address-physical address mapping table, and clear the mapping of the physical address-logical address mapping table in the mapping table storage space 801 information.

FIG. 11 is a flowchart of a method for updating a mapping table shown in an embodiment of the present invention.

Referring to FIG. 11 , in step S1101 , the memory control circuit unit 404 (or the memory management circuit 502 ) allocates storage space for the mapping table to store the physical address-logical address mapping table. Specifically, the memory control circuit unit 404 (or the memory management circuit 502 ) allocates the storage space of the mapping table in the buffer memory 508 .

In step S1103 , the memory control circuit unit 404 (or the memory management circuit 502 ) receives a plurality of write data from the host system 11 , wherein the write data belongs to a plurality of logic programming units.

In step S1105, the memory control circuit unit 404 (or the memory management circuit 502) selects a physical erasing unit as an active physical erasing unit. Specifically, the memory control circuit unit 404 (or the memory management circuit 502 ) selects one of the multiple physical erasing units of the rewritable non-volatile memory module 406 as the active physical erasing unit.

In step S1107, the memory control circuit unit 404 (or the memory management circuit 502) determines whether the remaining storage space of the mapping table storage space is smaller than the first threshold value. The first threshold value can be set to different specific values according to actual needs, this part has been described in the previous embodiments, and will not be repeated here.

If the remaining storage space of the mapping table storage space is less than the first threshold value, in step S1109, the memory control circuit unit 404 (or the memory management circuit 502) stores the physical address-logical address mapping table in the mapping table storage space The mapping information is updated to at least one logical address-physical address mapping table, and the mapping information of the physical address-logical address mapping table stored in the mapping table storage space is cleared. The memory control circuit unit 404 (or the memory management circuit 502) can immediately clear the mapping information of the physical address-logical address mapping table stored in the mapping table storage space after updating the mapping information to at least one logical address-physical address mapping table . However, the memory control circuit unit 404 (or the memory management circuit 502 ) can also be cleared at any time point before the next program operation entity erases the unit, which is not limited by the present invention.

In step S1111, the memory control circuit unit 404 (or the memory management circuit 502) programs the write data to a plurality of physical programming units that operate the physical erase unit, and establishes a plurality of physical programming units for programming the write data. A plurality of updated mapping information between the unit and the logic programming units, and store the updated mapping information in the storage space of the mapping table. Specifically, in step S1107, if it is determined that the remaining storage space of the mapping table storage space is not less than the first threshold value, the memory control circuit unit 404 (or the memory management circuit 502) directly executes step S1111. In contrast, in step S1107, if it is determined that the remaining storage space of the mapping table storage space is less than the first threshold value, the memory control circuit unit 404 (or the memory management circuit 502) first executes step S1109, and then executes step S1111. It should be noted that, in this embodiment, before programming the write data into the active entity erasing unit, it is first judged whether the remaining storage space of the mapping table storage space is less than the first threshold value. However, in another embodiment, it is also possible to determine whether the remaining storage space of the mapping table storage space is less than the first threshold value after the active entity for programming the written data erases the unit, which is not limited by the present invention.

FIG. 12 is another exemplary flow chart of the method for updating the mapping table shown in the embodiment of the present invention. FIG. 12 is a flow chart of an exemplary embodiment of the step of storing the updated mapping information in the storage space of the mapping table shown in FIG. 11 .

Please refer to FIG. 12, in the step of storing a plurality of updated mapping information of the actuating entity erasing unit into the storage space of the mapping table, when only a part of the updated mapping information is stored in the storage space of the mapping table and the entity address -When the logical address mapping table is not greater than the second threshold value, in step S1201, the memory control circuit unit 404 (or the memory management circuit 502) will judge whether there are at least the following entities of programmed valid data in the active entity erasing unit programming unit, and the upper physical programming unit corresponding to the at least one lower physical programming unit is not programmed.

If it is determined that the at least one physical programming unit exists in the active physical erasing unit, in step S1203, the memory control circuit unit 404 (or the memory management circuit 502) programs a dummy data to the upper physical unit corresponding to the at least one physical programming unit. in the programming unit.

In step S1205, the memory control circuit unit 404 (or the memory management circuit 502) updates the mapping information of the physical address-logical address mapping table stored in the mapping table storage space to at least one logical address-physical address mapping table. Specifically, in step S1201, if it is determined that the at least one physical programming unit does not exist, the memory control circuit unit 404 (or the memory management circuit 502) directly executes step S1205. In contrast, in step S1201, if it is determined that the at least one physical programming unit exists, the memory control circuit unit 404 (or the memory management circuit 502) first executes step S1203, and then executes step S1205.

In step S1207, the memory control circuit unit 404 (or the memory management circuit 502) will clear the mapping information of the physical address-logical address mapping table stored in the mapping table storage space, and store the rest of the updated mapping information in In the mapping table storage space.

To sum up, the mapping table update method, memory control circuit unit and memory storage device proposed by the embodiments of the present invention use the mapping table storage space to store the update of the physical address-logical address mapping table corresponding to the actuating entity erasing unit and determine whether to update the mapping information of the physical address-logical address mapping table stored in the mapping table storage space to the logical address-physical address mapping table according to the size of the remaining storage space in the mapping table storage space. When the active physical erase unit is not full, but the mapping information of the physical address-logical address mapping table stored in the mapping table storage space needs to be updated to the logical address-physical address mapping table, if the judgment is in order The physical programming unit of the programmable data is the upper physical programming unit, then the dummy data is written into the upper physical programming unit. Based on this, the efficiency of updating the logical address-physical address mapping table can be improved, and the situation that the programmed data cannot be recovered due to programming failure of other physical programming units after updating the logical address-physical address mapping table can be avoided.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than limiting them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: It is still possible to modify the technical solutions described in the foregoing embodiments, or perform equivalent replacements for some or all of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the technical solutions of the various embodiments of the present invention. scope.

Claims (21)

1. A mapping table update method for a memory storage device, characterized in that the memory storage device has a rewritable non-volatile memory module, and the rewritable non-volatile memory module has multiple A physical erasing unit, each of these physical erasing units has a plurality of physical programming units, and the mapping table update method includes: allocating a mapping table storage space in a buffer memory to store a physical address-logical address mapping table; judging whether a remaining storage space in the storage space of the mapping table is smaller than a first threshold; If it is judged that the remaining storage space is smaller than the first threshold value, updating the mapping information of the physical address-logical address mapping table stored in the mapping table storage space to at least one logical address-physical address mapping table ; clearing the mapping information of the physical address-logical address mapping table stored in the mapping table storage space; and Programming a plurality of writing data belonging to a plurality of logical programming units to a plurality of physical programming units of an actuating physical erasing unit among the physical erasing units, and establishing the physical programming units for programming the writing data and a plurality of updated mapping information between the logical programming units, and store the updated mapping information in the physical address-logical address mapping table in the mapping table storage space. 2. The method for updating the mapping table according to claim 1, wherein the step of storing the updated mapping information in the storage space of the mapping table comprises: When a part of the updated mapping information is stored in the mapping table storage space and the remaining storage space in the mapping table storage space is not greater than a second threshold value, it is determined that the actuating entity erasing unit Whether there is at least one first physical programming unit, wherein the at least one first physical programming unit is the following physical programming unit, the at least one first physical programming unit has programmed a valid data and corresponds to the at least one first physical programming unit The upper physical programming unit of the physical programming unit is not programmed; If it is determined that the at least one first physical programming unit is stored in the active physical erasing unit, programming a dummy data to an upper physical programming unit corresponding to the at least one first physical programming unit; After programming the dummy data to the upper physical programming unit corresponding to the at least one first physical programming unit, updating the mapping information of the physical address-logical address mapping table stored in the mapping table storage space to the at least one logical address-physical address mapping table; and Clearing the mapping information of the physical address-logical address mapping table stored in the mapping table storage space and storing the rest of the updated mapping information in the mapping table storage space. 3. The method for updating the mapping table according to claim 1, wherein a plurality of update mapping information corresponding to a plurality of programmed physical erase units has been stored in the storage space of the mapping table. 4. The mapping table update method according to claim 3, further comprising: Calculating the size of the update mapping information corresponding to one of the programmed physical erasing units, wherein the one of the programmed physical erasing units is used for programming these write data to the operating Physically erased cells that are programmed last before a plurality of physically programmed cells that move the physically erased cells; and The size of the update mapping information of the one of the programmed physical erase units is set as the first threshold value. 5. The mapping table update method according to claim 3, further comprising: Calculating the size of the update mapping information corresponding to each of the programmed physical erase units; calculating an average value of the size of the update mapping information of the programmed physical erase units; and setting the average value as the first threshold. 6. The mapping table update method according to claim 3, further comprising: Calculating the size of the update mapping information corresponding to each of the programmed physical erase units; identifying a maximum value among sizes of update mapping information corresponding to the programmed physically erased cells; and Set the maximum value as the first threshold value. 7. The mapping table updating method according to claim 1, wherein at least a part of the written data is data generated by compressing multiple pieces of original data received from a host system. 8. A memory control circuit unit, used to control a rewritable nonvolatile memory module, characterized in that, the rewritable nonvolatile memory module has a plurality of entity erasing units, each of which The entity erasing unit has multiple entity programming units, and the memory control circuit unit includes: a host interface for electrically connecting to a host system; a memory interface for electrically connecting to the rewritable non-volatile memory module; and a memory management circuit electrically connected to the host interface and the memory interface, Wherein, the memory management circuit is used to allocate a mapping table storage space in a buffer memory to store a physical address-logical address mapping table, Wherein, the memory management circuit is also used to judge whether a remaining storage space in the storage space of the mapping table is smaller than a first threshold value, Wherein, if it is judged that the remaining storage space is smaller than the first threshold value, the memory management circuit is further configured to update the mapping information of the physical address-logical address mapping table stored in the mapping table storage space to at least a logical address-physical address mapping table, Wherein, the memory management circuit is also used to clear the mapping information of the physical address-logical address mapping table stored in the storage space of the mapping table, Wherein, the memory management circuit is also used to program a plurality of writing data belonging to a plurality of logical programming units to a plurality of physical programming units of an actuating physical erasing unit among the physical erasing units, and to establish programming of the physical erasing unit. A plurality of updated mapping information between the physical programming units and the logical programming units of the written data, and store the updated mapping information in the physical address-logical address mapping in the storage space of the mapping table surface. 9. The memory control circuit unit according to claim 8, wherein when a part of the updated mapping information is stored in the mapping table storage space and the remaining storage space in the mapping table storage space When not greater than a second threshold value, the memory management circuit is also used to determine whether there is at least one first physical programming unit in the active physical erasing unit, wherein the at least one first physical programming unit is as follows A physical programming unit, the at least one first physical programming unit has been programmed with valid data and the upper physical programming unit corresponding to the at least one first physical programming unit has not been programmed, Wherein, if it is determined that the at least one first physical programming unit is stored in the active physical erasing unit, the memory management circuit is also used to program a dummy data to the corresponding at least one first physical programming unit The upper entity programming unit, Wherein, after programming the dummy data to the upper physical programming unit corresponding to the at least one first physical programming unit, the memory management circuit is also used to write the physical address stored in the storage space of the mapping table to - updating the mapping information of the logical address mapping table to the at least one logical address-physical address mapping table, Wherein, the memory management circuit is also used to clear the mapping information of the physical address-logical address mapping table stored in the mapping table storage space and store the rest of the updated mapping information in the mapping table storage space. in space. 10 . The memory control circuit unit according to claim 8 , wherein a plurality of updated mapping information corresponding to a plurality of programmed physical erase units has been stored in the storage space of the mapping table. 11 . 11. The memory control circuit unit according to claim 10, wherein the memory management circuit is also used to calculate the update mapping information corresponding to one of the programmed physical erase units. size, wherein said one of the programmed physical erasing units is the last programmed physical erasing unit before programming the write data to the plurality of physical programming units of the actuating physical erasing unit, Wherein the memory management circuit is also used to set the update mapping information size of one of the programmed physical erase units as the first threshold value. 12. The memory control circuit unit according to claim 10, wherein the memory management circuit is also used to calculate the size of the update mapping information corresponding to each of the programmed physical erase units, Wherein, the memory management circuit is also used to calculate an average value of the size of the update mapping information of the programmed physical erase units, Wherein, the memory management circuit is further configured to set the average value as the first threshold value. 13. The memory control circuit unit according to claim 10, wherein the memory management circuit is also used to calculate the size of the update mapping information corresponding to each of the programmed physical erase units, Wherein the memory management circuit is also used to identify a maximum value among the sizes of the update mapping information corresponding to the programmed physical erase units, Wherein the memory management circuit is further configured to set the maximum value as the first threshold value. 14. The memory control circuit unit according to claim 8, characterized in that at least a part of the written data is compressed by the memory management circuit from a plurality of original data received from the host system data generated afterwards. 15. A memory storage device, comprising: a connection interface unit for electrically connecting to a host system; A rewritable non-volatile memory module, including a plurality of physical erasing units, each of the physical erasing units has a plurality of physical programming units; and a memory control circuit unit electrically connected to the connection interface unit and the rewritable non-volatile memory module, Wherein, the memory control circuit unit is used to allocate a mapping table storage space in a buffer memory for storing a physical address-logical address mapping table, Wherein, the memory control circuit unit is also used to judge whether a remaining storage space in the storage space of the mapping table is smaller than a first threshold value, Wherein, if it is judged that the remaining storage space is smaller than the first threshold value, the memory control circuit unit is further configured to update the mapping information of the physical address-logical address mapping table stored in the mapping table storage space to at least one logical address-physical address mapping table, Wherein, the memory control circuit unit is also used to clear the mapping information of the physical address-logical address mapping table stored in the mapping table storage space, Wherein, the memory control circuit unit is also used to program a plurality of writing data belonging to a plurality of logical programming units to a plurality of physical programming units of an actuating physical erasing unit among the physical erasing units, to establish programming A plurality of updated mapping information between the physical programming units and the logical programming units of the written data, and store the updated mapping information in the physical address-logical address in the storage space of the mapping table mapping table. 16. The memory storage device according to claim 15, wherein when a part of the updated mapping information is stored in the mapping table storage space and the remaining storage space in the mapping table storage space is not When it is greater than a second threshold value, the memory control circuit unit is also used to judge whether there is at least one first physical programming unit in the active physical erasing unit, wherein the at least one first physical programming unit is: A physical programming unit, the at least one first physical programming unit has been programmed with valid data and the upper physical programming unit corresponding to the at least one first physical programming unit has not been programmed, Wherein, if it is determined that the at least one first physical programming unit exists in the active physical erasing unit, the memory control circuit unit is also used to program a dummy data corresponding to the at least one first physical programming unit. unit's upper entity programming unit, Wherein, after programming the dummy data to the upper physical programming unit corresponding to the at least one first physical programming unit, the memory control circuit unit is also used to program the physical programming unit stored in the mapping table storage space updating the mapping information of the address-logical address mapping table to the at least one logical address-physical address mapping table, Wherein, the memory control circuit unit is also used to clear the mapping information of the physical address-logical address mapping table stored in the mapping table storage space and store the rest of the updated mapping information in the mapping table in storage space. 17. The memory storage device according to claim 15, wherein a plurality of updated mapping information corresponding to a plurality of programmed physical erase units has been stored in the storage space of the mapping table. 18. The memory storage device according to claim 17, wherein the memory control circuit unit is also used to calculate the update mapping information corresponding to one of the programmed physical erasing units. size, wherein said one of the programmed physical erasing units is the last programmed physical erasing unit before programming the write data to the plurality of physical programming units of the actuating physical erasing unit, The memory control circuit unit is further configured to set the update mapping information size of one of the programmed physical erase units as the first threshold value. 19. The memory storage device according to claim 17, wherein the memory control circuit unit is also used to calculate the size of the update mapping information corresponding to each of the programmed physical erase units, Wherein, the memory control circuit unit is also used to calculate an average value of the update mapping information of the programmed physical erasing units, Wherein, the memory control circuit unit is further configured to set the average value as the first threshold value. 20. The memory storage device according to claim 17, wherein the memory control circuit unit is also used to calculate the size of the update mapping information corresponding to each of the programmed physical erase units, Wherein the memory control circuit unit is also used to identify a maximum value among the sizes of the update mapping information corresponding to the programmed physical erase units, Wherein the memory control circuit unit is further configured to set the maximum value as the first threshold value. 21. The memory storage device according to claim 15, wherein at least a part of the written data is compressed by the memory control circuit unit from a plurality of original data received from the host system data generated afterwards.