CN104238956A - Data writing method, memory controller and memory storage device - Google Patents

Abstract

The present invention relates to a data writing method, a memory controller and a memory storage device. The method is used for a rewritable non-volatile memory module. The method includes extracting a physical erase unit as a global chaos area and establishing a global chaos area search table to record multiple update information of updated logical pages corresponding to the updated data temporarily stored in the global chaos area in the global chaos area. The method also includes receiving updated data to be stored in a logical page; determining whether the data fragmentation degree corresponding to this global chaos area is less than the data fragmentation degree threshold. The method also includes, and if the data fragmentation degree corresponding to this global chaos area is less than the data fragmentation degree threshold, writing this updated data into this global chaos area and recording the update information corresponding to this logical page in the global chaos area search table.

Description

Data writing method, memory controller and memory storage device

technical field

The invention relates to a data writing method for a rewritable non-volatile memory, a memory controller and a memory storage device using the method.

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. Because rewritable non-volatile memory (rewritable non-volatile memory) has the characteristics of non-volatile data, power saving, small size, no mechanical structure, and fast read and write speed, it is most suitable for portable electronic products, such as notebooks. computer. A solid state drive is a memory storage device that uses flash memory as a storage medium. Therefore, the flash memory industry has become a very popular part of the electronics industry in recent years.

The flash memory module has a plurality of physical erasing units (physical erasing unit) and each physical erasing unit has a plurality of physical programming units (physical pages), wherein when writing data in the physical erasing unit, it must be based on the physical programming unit Write data in order. In addition, the physical programming unit that has been written with data needs to be erased before it can be used to write data again. In particular, the physical erasing unit is the smallest unit of erasing, and the physical programming unit is the smallest unit of programming (also known as writing). Therefore, in the management of the flash memory module, the physical erasing unit is divided into a data area and an idle area.

The physical erasing unit of the data area is used to store data stored in the host system. Specifically, the memory management circuit in the memory storage device will convert the logical access address accessed by the host system into the logical page of the logical block and map the logical page of the logical block to the physical erase unit of the data area. Physical programming unit. That is to say, the physical erasing unit of the management data area of the flash memory module is regarded as the physical erasing unit that has been used (for example, the data written by the host system has been stored). For example, the memory management circuit will use the logical-to-physical address mapping table to record the mapping relationship between the logical block and the physical erasing unit of the data area, wherein the logical page in the logical block is the physical programming corresponding to the mapped physical erasing unit unit.

The physical erasing unit in the spare area is used to replace the physical erasing unit in the data area. Specifically, as mentioned above, the physical erasing unit that has written data must be erased before it can be used to write data again. Therefore, the physical erasing unit in the spare area is designed to write update data to Replaces physical erase units that map logical blocks. Based on this, the physical erasing unit in the spare area is an empty or usable physical erasing unit, that is, no recorded data or invalid data marked as useless.

That is to say, the physical programming unit of the physical erasing unit and the physical programming unit of the data area and the idle area map the logical pages of the logical block in an alternate manner to store the data written by the host system. For example, the memory management circuit of the memory storage device will extract one or more physical erasing units from the spare area as the global chaos physical erasing unit, and when the logical access address of the host system to write update data is the corresponding memory storage device For a certain logical page of a certain logical block, the memory management circuit of the memory storage device will write the update data into the physical programming unit of the global chaos physical erasing unit.

In particular, during the operation of the memory storage device, when the global chaos physical erasing unit is almost exhausted, the memory management circuit of the memory storage device will organize the data stored in the global chaos physical erasing unit into the corresponding physical erasure In the unit (hereinafter referred to as "valid data merge operation"), in order to free up the storage space of the global chaos physical erasure unit, the subsequent write command has been executed. After sorting the data stored in the global chaotic physical erasing unit into the corresponding physical erasing unit, the memory management circuit of the memory storage device needs to update the logical-to-physical address mapping table so that subsequent access operations can be normally performed implement. Since the capacity of the memory storage device is getting larger and larger, generally multiple logical-to-physical address mapping tables are used to record the mapping between all logical blocks and physical erasing units. Therefore, when the "effective data merge operation" is required to complete the write command from the host system, it may be necessary to load and restore different logical-to-physical address mapping tables multiple times to confuse the entire domain. The information in the area search table is recorded into the logical-to-physical address mapping table, which delays the completion of the write command, resulting in low performance of the memory storage device.

Contents of the invention

The invention provides a data writing method, a memory controller, a memory controller and a memory storage device, which can effectively reduce the delay caused by combining valid data of global chaos physical erasing units when executing a write command.

An exemplary embodiment of the present invention provides a data writing method for writing data into a rewritable non-volatile memory module, wherein the rewritable non-volatile memory module has a plurality of physical erasing units, each A physical erasing unit has a plurality of physical programming units, and these physical erasing units are at least grouped into a data area and an idle area, and the physical erasing unit in the idle area is used to replace the physical erasing unit in the data area to write data, Multiple logical units are configured to map the physical erase units of the data area, and each logical unit has multiple logical pages. The data writing method includes: extracting at least one physical erasing unit from the physical erasing unit in the spare area as a global chaotic area, wherein the global chaotic area is used to temporarily store data belonging to a plurality of updated logical pages, and these The updated logical page belongs to a plurality of updated logical units among the logical units. The data writing method further includes establishing a global chaotic area search table to record a plurality of update information corresponding to the updated logical pages in the global chaotic area. The data writing method also includes receiving a write command and update data corresponding to the write command, wherein the update data belongs to the first logical page and the first logical page belongs to the first logical unit among the logical units. This data writing method also includes recording the fragmentation degree of data corresponding to the global chaos area; judging whether the data fragmentation degree corresponding to the global chaos area is less than the data fragmentation degree threshold; and if the data fragmentation degree corresponding to the global chaos area is less than the data fragmentation degree When the threshold is reached, the update data is written into the global chaotic area and the update information corresponding to the first logical page is recorded in the global chaotic area search table.

In an exemplary embodiment of the present invention, the above-mentioned data writing method further includes: if the data fragmentation degree corresponding to the global chaos area is not less than the data fragmentation degree threshold, extracting the first physical erasing unit from the spare area as Write update data into the sub-physical erasing unit corresponding to the first logical unit, and update the logic-to-physical address mapping table corresponding to the first logical unit, wherein the sub-physical erasing unit is only used for Data belonging to the first logical unit is stored.

In an exemplary embodiment of the present invention, the above-mentioned data writing method further includes: grouping these logical units into multiple logical areas; and configuring multiple logical-to-physical address mapping tables to be assigned to these logical areas respectively , wherein these logical-to-physical address mapping tables are used to record multiple mapping relationships between the logical units of these logical areas and the physical erasing units of the above-mentioned data area, and each logical-to-physical address mapping table is independently configured for One of these logical regions.

In an exemplary embodiment of the present invention, the updated logical units belong to a plurality of updated logical areas in the logical areas. Moreover, the step of recording the fragmentation degree of data corresponding to the global chaotic area includes: calculating the number of the updated logical areas; and recording the number of the updated logical areas as the data fragmentation degree corresponding to the global chaotic area.

In an exemplary embodiment of the present invention, the step of recording the data fragmentation degree corresponding to the global chaos area includes: calculating the number of the above-mentioned updated logical units; and recording the number of these updated logical units as the corresponding global chaos area Fragmentation of data.

In an exemplary embodiment of the present invention, the step of recording the degree of fragmentation of data corresponding to the global chaotic area includes: calculating the number of multiple logical-to-physical address mapping tables to be updated and recording these logical-to-physical address mapping tables to be updated The number is used as the fragmentation degree of data corresponding to the global chaotic area, wherein the logical-to-physical address mapping tables to be updated are used to record the mapping between the updated logical unit and the physical erasing unit of the data area.

In an exemplary embodiment of the present invention, the above-mentioned data writing method further includes: judging whether there is valid data belonging to the first logic unit in the global chaos area; and if there is valid data belonging to the first logic unit in the global chaos area When there is valid data in the unit, write the above-mentioned update data into the global chaos area, wherein the step of judging whether the data fragmentation degree corresponding to the global chaos area is less than the data fragmentation degree threshold is that there is no data belonging to the above-mentioned first Executed when there is valid data for the logical unit.

An exemplary embodiment of the present invention provides a memory controller for controlling a rewritable non-volatile memory module, wherein the rewritable non-volatile memory module has a plurality of physical erasing units, and each physical erasing unit There are a plurality of physical programming units, and these physical erasing units are at least grouped into a data area and an idle area, and the physical erasing units in the idle area are used to replace the physical erasing units in the data area to write data. The memory controller includes a host interface, a memory interface and a memory management circuit. The host interface is used to electrically connect to the host system. The memory interface is used for electrically connecting to the rewritable non-volatile memory module. The memory management circuit is electrically connected to the host interface and the memory interface, and is used to configure a plurality of logical units to map the physical erasing units of the data area, wherein each logical unit has a plurality of logical pages. In addition, the memory management circuit is also used to extract at least one physical erasing unit from the physical erasing unit in the spare area as a global chaos area, wherein the global chaos area is used to temporarily store data belonging to a plurality of updated logical pages, and this These updated logical pages belong to a plurality of updated logical units among the above logical units. In addition, the memory management circuit is also used to establish a global chaotic area lookup table to record a plurality of update information corresponding to the updated logical pages in the global chaotic area. Here, the memory management circuit is further configured to receive a write command and update data corresponding to the write command, the update data belongs to the first logical page and the first logical page belongs to the first logical unit. Furthermore, the memory management circuit is also used for recording the data fragmentation degree corresponding to the global chaos area and judging whether the data fragmentation degree corresponding to the global chaos area is less than the data fragmentation degree threshold. If the data fragmentation degree corresponding to the global chaos area is less than the data fragmentation degree threshold, the memory management circuit writes update data into the global chaos area and records update information corresponding to the first logical page in the global chaos area search table.

In an exemplary embodiment of the present invention, if the data fragmentation degree corresponding to the global chaos area is not less than the data fragmentation degree threshold, the memory management circuit extracts the first physical erasing unit from the idle area as the corresponding first logical unit Sub-physical erasing unit, write update data into this sub-physical erasing unit, and update the logical-to-physical address mapping table corresponding to the first logical unit, wherein this sub-physical erasing unit is only used to store data belonging to the first logical unit unit's data.

In an exemplary embodiment of the present invention, the above-mentioned memory management circuit is further used to group these logical units into multiple logical areas and configure multiple logical-to-physical address mapping tables to be respectively assigned to these logical areas, wherein the These logical-to-physical address mapping tables are used to record multiple mappings between the logical units of these logical areas and the physical erasing units of the above-mentioned data area, and each logical-to-physical address mapping table is independently configured for these logical areas one of the .

In an exemplary embodiment of the present invention, the updated logical units belong to a plurality of updated logical areas in the logical areas. And, in the operation of recording the data fragmentation degree corresponding to the global chaos area, the memory management circuit calculates the number of these updated logical areas and records the number of these updated logical areas as the data fragmentation degree corresponding to the global chaos area .

In an exemplary embodiment of the present invention, during the operation of recording the fragmentation degree of data corresponding to the global chaotic area, the memory management circuit calculates the number of updated logical units and records the number of updated logical units as a corresponding The degree of fragmentation of data in the global chaotic area.

In an exemplary embodiment of the present invention, during the operation of recording the fragmentation degree of data corresponding to the global chaotic area, the memory management circuit calculates the number of multiple logic-to-physical address mapping tables to be updated and records the logic to be updated The number of the physical address mapping table is used as the fragmentation degree of the data corresponding to the global chaotic area, wherein the logical to physical address mapping tables to be updated are used to record the mapping between the updated logical unit and the physical erasing unit of the data area.

In an exemplary embodiment of the present invention, the memory management circuit is further used to determine whether there is valid data belonging to the first logic unit in the global chaos area, wherein if there is valid data belonging to the first logic unit in the global chaos area data, the memory management circuit writes the update data into the global chaos area, wherein the memory management circuit performs the above judgment when there is no valid data belonging to the first logic unit in the global chaos area. Whether the degree is less than the threshold of data fragmentation degree.

An exemplary embodiment of the present invention provides a memory storage device, which includes a connector, a rewritable non-volatile memory module, and a memory controller. The connector is used to electrically connect to the host system. 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. These physical erasing units are at least grouped into a data area and an idle area, and the physical area of the idle area is The erasing unit is used to replace the physical erasing unit of the data area to write data. The memory controller is electrically connected to the connector and the rewritable non-volatile memory module, and is used to configure a plurality of logical units to map the physical erasing units of the data area, wherein each logical unit has a plurality of logical pages. In addition, the memory controller is also used to extract at least one physical erasing unit from the physical erasing unit in the spare area as a global chaotic area, wherein the global chaotic area is used to temporarily store data belonging to a plurality of updated logical pages, and this These updated logical pages belong to a plurality of updated logical units among the above logical units. In addition, the memory controller is also used to establish a global chaotic area lookup table to record a plurality of update information corresponding to the updated logical pages in the global chaotic area. Here, the memory controller is further configured to receive a write command and update data corresponding to the write command, the update data belongs to the first logical page and the first logical page belongs to the first logical unit. Furthermore, the memory controller is also used to record the data fragmentation degree corresponding to the global chaos area and determine whether the data fragmentation degree corresponding to the global chaos area is less than the data fragmentation degree threshold. If the data fragmentation degree corresponding to the global chaos area is less than the data fragmentation degree threshold, the memory controller writes update data into the global chaos area and records update information corresponding to the first logical page in the global chaos area search table.

In an exemplary embodiment of the present invention, if the data fragmentation degree corresponding to the global chaos area is not less than the data fragmentation degree threshold, the memory controller extracts the first physical erasing unit from the spare area as the corresponding first logical unit sub-physical erasing unit, write update data into the sub-physical erasing unit corresponding to the first logical unit, and update the logic-to-physical address mapping table corresponding to the first logical unit, wherein the sub-physical erasing unit only uses to store data belonging to the first logical unit.

In an exemplary embodiment of the present invention, the above-mentioned memory controller is further configured to group these logical units into multiple logical areas and configure multiple logical-to-physical address mapping tables to be respectively assigned to these logical areas, wherein the These logical-to-physical address mapping tables are used to record multiple mapping relationships between the logical units of these logical areas and the physical erasing units of the above-mentioned data area, and each logical-to-physical address mapping table is independently configured for these logical one of the regions.

In an exemplary embodiment of the present invention, the updated logical units belong to a plurality of updated logical areas in the logical areas. And, in the operation of recording the data fragmentation degree corresponding to the global chaos area, the above-mentioned memory controller calculates the number of these updated logical areas and records the number of these updated logical areas as the data fragmentation degree corresponding to the global chaos area .

In an exemplary embodiment of the present invention, during the operation of recording the fragmentation degree of data corresponding to the global chaotic area, the memory controller calculates the number of updated logical units and records the number of updated logical units as a corresponding The degree of fragmentation of data in the global chaotic area.

In an exemplary embodiment of the present invention, during the operation of recording the degree of fragmentation of data corresponding to the global chaotic area, the memory controller calculates the number of a plurality of logic-to-physical address mapping tables to be updated and records the logic to be updated The number of the physical address mapping table is used as the fragmentation degree of the data corresponding to the global chaotic area, wherein the logical to physical address mapping tables to be updated are used to record the mapping between the updated logical unit and the physical erasing unit of the data area.

In an exemplary embodiment of the present invention, the memory controller is also used to determine whether there is valid data belonging to the first logic unit in the global chaos area, wherein if there is valid data belonging to the first logic unit in the global chaos area data, the memory controller writes the update data into the global chaos area, wherein the memory controller executes the above judgment when there is no valid data belonging to the first logical unit in the global chaos area. Whether the degree is less than the threshold of data fragmentation degree.

Based on the above, the data writing method, the memory controller, and the memory storage device of the exemplary embodiments of the present invention can avoid spending too much time on updating the logical-to-physical address mapping table when performing the global chaos physical erasing unit effective data combination operation, by This increases the speed at which write instructions are executed.

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 shows a host system and a memory storage device according to an exemplary embodiment.

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

FIG. 3 is a schematic diagram of a host system and a memory storage device according to an exemplary embodiment of the present invention.

FIG. 4 is a schematic block diagram illustrating the memory storage device shown in FIG. 1 .

FIG. 5 is a schematic block diagram of a memory controller according to an exemplary embodiment.

FIG. 6 and FIG. 7 are exemplary schematic diagrams of managing physical blocks according to the first exemplary embodiment.

8-14 illustrate simplified examples of writing data using the global chaos area.

FIG. 15 is a simplified example of the global chaos area search table shown in FIG. 14 .

FIGS. 16-21 illustrate simplified examples of executing the global chaotic area valid data merging process to complete subsequent write commands.

FIGS. 22 to 24 illustrate examples of using sub-physical units to write update data.

FIG. 25 is a flowchart of a data writing method according to an exemplary embodiment.

【Symbol Description】

1000: host system

1100: computer

1102: Microprocessor

1104: random access memory

1106: Input/Output Device

1108: System bus

1110: data transmission interface

1202: mouse

1204: keyboard

1206: display

1208: Printer

1212: Pen drive

1214: memory card

1216: SSD

1310: Digital camera

1312: SD card

1314: MMC card

1316: memory stick

1318: CF card

1320: Embedded storage device

100: memory storage device

102: Connector

104: memory controller

106: Rewritable non-volatile memory module

202: memory management circuit

204: host interface

206: memory interface

208: buffer memory

210: power management circuit

212: Error checking and correction circuit

410(0)～410(N): physical erasing unit

502: System area

504: data area

506: idle area

508: Replacement area

550: Global Chaos Zone

LBA(0)～LBA(H): logic unit

LZ(0)～LZ(M): logical area

800: Global Chaos Area Search Table

810(0)～810(4): root unit

902: First field

904: Second field

906: The third field

S2501, S2503, S2505, S2507, S2509, S2511: steps of data writing method

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 shows a host system and a memory storage device according to an exemplary embodiment.

Referring to FIG. 1 , the host system 1000 generally includes a computer 1100 and an input/output (I/O) device 1106 . The computer 1100 includes a microprocessor 1102 , a random access memory (random access memory, RAM) 1104 , a system bus 1108 and a data transmission interface 1110 . The input/output device 1106 includes a mouse 1202 , a keyboard 1204 , a monitor 1206 and a printer 1208 as shown in FIG. 2 . It must be understood that the device shown in FIG. 2 is not limited to the input/output device 1106, and the input/output device 1106 may also include other devices.

In the embodiment of the present invention, the memory storage device 100 is electrically connected with other components of the host system 1000 through the data transmission interface 1110 . Data can be written into or read from the memory storage device 100 through the operation of the microprocessor 1102 , the random access memory 1104 and the input/output device 1106 . For example, the memory storage device 100 may be a rewritable non-volatile memory storage device such as a flash drive 1212, a memory card 1214, or a solid state drive (Solid State Drive, SSD) 1216 as shown in FIG. 2 .

In general, host system 1000 is any system that can cooperate substantially with memory storage device 100 to store data. Although in this exemplary embodiment, the host system 1000 is illustrated as a computer system, however, in another exemplary embodiment of the present invention, the host system 1000 may be a digital camera, video camera, communication device, audio player or video player and other systems. For example, when the host system is a digital camera (video camera) 1310, the rewritable non-volatile memory storage device is an SD card 1312, an MMC card 1314, a memory stick (memory stick) 1316, a CF card 1318 or An embedded storage device 1320 (as shown in FIG. 3 ). The embedded storage device 1320 includes an embedded multimedia card (Embedded MMC, eMMC). 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 illustrating the memory storage device shown in FIG. 1 .

Referring to FIG. 4 , the memory storage device 100 includes a connector 102 , a memory controller 104 and a rewritable non-volatile memory module 106 .

In this exemplary embodiment, the connector 102 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 connector 102 may also be a high-speed, high-speed Peripheral Component Interconnect Express (PCI Express) standard, Universal Serial Bus (Universal Serial Bus, USB) standard, Ultra High Speed-I (UHS-I) interface standard, Ultra High Speed II (Ultra High Speed-II, UHS-II) interface standard, Secure Digital (Secure Digital, SD) interface standard, Memory Stick (Memory Stick, MS) interface standard, multimedia memory card (MultiMedia Card, MMC) interface standard, small flash (Compact Flash, CF) interface standard, Integrated Device Electronics (IDE) standard, or other suitable standards.

The memory controller 104 is used to execute a plurality of logic gates or control instructions implemented in the form of hardware or firmware, and write and read data in the rewritable non-volatile memory module 106 according to the instructions of the host system 1000 Fetch and erase operations.

The rewritable non-volatile memory module 106 is electrically connected to the memory controller 104 and used for storing data written by the host system 1000 . The rewritable non-volatile memory module 106 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 physical 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 area contains multiple physical access addresses to store user data, and the redundant bit area is used to store system data (eg, control information and error correction code). In this exemplary embodiment, the data bit area of each physical programming unit includes 4 physical access addresses, and the size of one physical access address is 512 bytes. However, in other exemplary 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 an exemplary 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 exemplary embodiment, the rewritable non-volatile memory module 106 is a multi-level memory cell (Multi Level Cell, MLC) NAND flash memory module (that is, a memory cell can store 2 bits of data flash flash memory module). However, the present invention is not limited thereto, and the rewritable non-volatile memory module 106 may also be a single-level memory cell (Single Level Cell, SLC) NAND flash memory module (that is, one memory cell can store 1 bit of data flash memory module), multi-level memory cell (Trinary Level Cell, TLC) NAND flash memory module (that is, a flash memory module that can store 3 bits of data in a memory cell), other flash memory modules or Other memory modules with the same characteristics.

FIG. 5 is a schematic block diagram of a memory controller according to an exemplary embodiment.

Referring to FIG. 5 , the memory controller 104 includes a memory management circuit 202 , a host interface 204 and a memory interface 206 .

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

In this exemplary embodiment, the control commands of the memory management circuit 202 are implemented in the form of firmware. For example, the memory management circuit 202 has a microprocessor unit (not shown) and a ROM (not shown), and these control instructions are burned into the ROM. When the memory storage device 100 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 exemplary embodiment of the present invention, the control instructions of the memory management circuit 202 may also be stored in a specific area of the rewritable non-volatile memory module 106 in the form of program codes (for example, a system dedicated to storing system data in the memory module) area). In addition, the memory management circuit 202 has a microprocessor unit (not shown), a read only memory (not shown) and a random access memory (not shown). In particular, the ROM has driver code, and when the memory controller 104 is enabled, the microprocessor unit will first execute the driver code segment to store the control code stored in the rewritable non-volatile memory module 106. The instructions are loaded into random access memory of the memory management circuit 202 . Afterwards, the microprocessor unit runs these control instructions to perform operations such as writing, reading and erasing data.

In addition, in another exemplary embodiment of the present invention, the control instructions of the memory management circuit 202 may also be implemented in a hardware form. For example, the memory management circuit 202 includes a microcontroller, a memory cell management circuit, a memory writing circuit, a memory reading circuit, a memory erasing circuit and a data processing circuit. The memory cell management circuit, the memory writing circuit, the memory reading circuit, the memory erasing circuit and the data processing circuit are electrically connected to the microcontroller. Wherein, the memory cell management circuit is used to manage the physical erasing unit of the rewritable non-volatile memory module 106; the memory write circuit is used to issue a write command to the rewritable non-volatile memory module 106 to write data into the rewritable nonvolatile memory module 106; the memory read circuit is used to issue a read instruction to the rewritable nonvolatile memory module 106 to read from the rewritable nonvolatile memory module 106 Data; the memory erasing circuit is used to issue an erase command to the rewritable non-volatile memory module 106 to erase data from the rewritable non-volatile memory module 106; and the data processing circuit is used to process the data to be written Data input to the rewritable non-volatile memory module 106 and data read from the rewritable non-volatile memory module 106.

The host interface 204 is electrically connected to the memory management circuit 202 and used for receiving and identifying commands and data transmitted by the host system 1000 . That is to say, the commands and data transmitted by the host system 1000 are transmitted to the memory management circuit 202 through the host interface 204 . In this exemplary embodiment, the host interface 204 is compatible with the SATA standard. However, it must be understood that the present invention is not limited thereto, and the host interface 204 can also be compatible with PATA standard, IEEE1394 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 206 is electrically connected to the memory management circuit 202 and used for accessing the rewritable non-volatile memory module 106 . That is to say, the data to be written into the rewritable nonvolatile memory module 106 will be converted into a format acceptable to the rewritable nonvolatile memory module 106 via the memory interface 206 .

In an exemplary embodiment of the present invention, the memory controller 104 further includes a buffer memory 208 , a power management circuit 210 and an error checking and correction circuit 212 .

The buffer memory 208 is electrically connected to the memory management circuit 202 and used for temporarily storing data and instructions from the host system 1000 or data from the rewritable non-volatile memory module 106 .

The power management circuit 210 is electrically connected to the memory management circuit 202 and used to control the power of the memory storage device 100 .

The error checking and correcting circuit 212 is electrically connected to the memory management circuit 202 and used for executing error checking and correcting procedures to ensure the correctness of data. Specifically, when the memory management circuit 202 receives a write command from the host system 1000, the error checking and correction circuit 212 will generate a corresponding error checking and correcting code (Error Checking and Correcting Code, ECC Code), and the memory management circuit 202 will write the data corresponding to the write command and the corresponding error checking and correction code into the rewritable non-volatile memory module 106. Afterwards, when the memory management circuit 202 reads data from the rewritable non-volatile memory module 106, it will simultaneously read the error checking and correction code corresponding to the data, and the error checking and correction circuit 212 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.

FIG. 6 and FIG. 7 are schematic diagrams illustrating examples of managing physical erasing units according to the first exemplary embodiment.

Referring to FIG. 6, the memory controller 104 (or the memory management circuit 202) will logically group the physical erasing units 410(0)-410-(N) into a data area 502, an idle area 504, a system area 506, and a replacement area. 508.

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

The physical erase units logically belonging to the system area 506 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 physical erasing units of the rewritable nonvolatile memory module, the number of physical programming units per physical erasing unit, and the like.

The physical erasing units logically belonging to the replacement area 508 are used in the bad physical erasing unit replacement process to replace the damaged physical erasing units. Specifically, if there are still normal physical erasing units in the replacement area 508 and the physical erasing units in the data area 502 are damaged, the memory management circuit 202 will extract normal physical erasing units from the replacement area 508 to replace the damaged ones. physical erasing unit.

In particular, the numbers of physical erasing units in the data area 502 , spare area 504 , system area 506 and replacement area 508 are different according to different memory specifications. In addition, it must be understood that during the operation of the memory storage device 100 , the grouping relationship of the physical erase unit associated with the data area 502 , the spare area 504 , the system area 506 and the replacement area 508 will change dynamically. For example, when the physical erasing unit in the spare area 504 is damaged and replaced by the physical erasing unit in the replacement area 508 , the original physical erasing unit in the replacement area 508 will be associated with the spare area 504 .

Referring to FIG. 7, the memory controller 104 (or the memory management circuit 202) configures the logical units LBA(0)-LBA(H) to map the physical erasing units of the data area 502, wherein each logical unit has multiple logical pages to map the physical programming units of the corresponding physical erasing units. And, when the host system 100 intends to write data to the logical unit or update the data stored in the logical unit, the memory controller 104 (or the memory management circuit 202) will extract a physical erase unit from the spare area 504 to write data to rotate the physical erase units of the data area 502 .

In order to identify the physical erasing unit in which the data of each logical unit of data is stored, in this exemplary embodiment, the memory controller 104 (or the memory management circuit 202 ) records the mapping between the logical unit and the physical erasing unit. Moreover, when the host system 1000 intends to access data in the logical page, the memory controller 104 (or the memory management circuit 202) will confirm the logical unit to which the logical page belongs, and in the physical erase unit mapped to the logical unit to access data. For example, in this exemplary embodiment, the memory controller 104 (or the memory management circuit 202) stores a logical-to-physical address mapping table in the rewritable non-volatile memory module 106 to record the physical address mapped to each logical unit. The unit is erased, and the memory controller 104 (or the memory management circuit 202 ) loads the logical-to-physical address mapping table into the buffer memory 208 for maintenance when data is to be accessed.

It is worth mentioning that due to the limited capacity of the buffer memory 208, it is impossible to store a mapping table that records the mapping relationship of all logical units. Therefore, in this exemplary embodiment, the memory controller 104 (or memory management circuit 202) will store the logical units LBA(0)-LBA(H) are grouped into multiple logical zones LZ(0)-LZ(M), and a logical-to-physical address mapping table is configured for each logical zone. In particular, when the memory controller 104 (or the memory management circuit 202) intends to update the mapping of a certain logical unit, the logical-to-physical address mapping table corresponding to the logical area to which the logical unit belongs will be loaded into the buffer memory 208 for being renew.

In this exemplary embodiment, the memory controller 104 (or the memory management circuit 202) extracts the physical erase unit from the spare area 504 as a global chaotic area, and writes the data included in the write command from the host system 1000 ( Also called update data) is written into the physical erasing unit of the global chaos area (also called the global chaos physical erasing unit). In this exemplary embodiment, the global chaos physical erasure unit is designed to store data respectively corresponding to different logical units.

Specifically, when the memory storage device 100 receives a write command from the host system 1000, the data in the write command from the host system 1000 can be written into the physical erase unit of the global chaos area. And, when this global chaos physical erasing unit is full, the memory controller 104 (or memory management circuit 202) will extract an empty physical erasing unit from the spare area 504 as another global chaos physical erasing unit , to continue writing update data corresponding to the write command from the host system 1000 . When the number of physical erasing units as the global chaos area has reached an upper limit, the memory controller 104 (or the memory management circuit 202) will execute the data merging program, so that the data stored in the global chaos physical erasing unit become invalid data, and then associate the global chaos physical erasure unit whose stored data is all invalid data back to the spare area 504 .

8-14 illustrate simplified examples of writing data using the global chaos area.

For the convenience of description, it is assumed that the data area 502 has 5 physical erasing units, the idle area 504 has 4 physical erasing units, and each physical erasing unit has 3 physical programming units. The data of the erasing units must be written in the order of the physical programming units, and the upper limit of the number of physical erasing units serving as global chaos physical erasing units is 2.

Please refer to FIG. 8, in the initial state of the memory storage device 100, the physical programming of the physical erasing units 410(0)-410(4) of the logical page mapping data area 502 of the logical units LBA(0)-LBA(4) units, and the spare area 504 has physical erase units 410(5)˜410(8). That is to say, the memory controller 104 (or the memory management circuit 202) records the logical units LBA(0)-LBA(4) and the physical erasing units 410(0)-410(4) in the logical-to-physical address mapping table and the physical programming units of the physical erasing units 410(0)-410(4) are regarded as having stored the data belonging to the logical pages of the logical units LBA(0)-LBA(4) (that is, the initial Data ID1~ID15). It must be understood that when the memory storage device 100 is just shipped from the factory, the initial data ID1-ID15 may be empty data. In addition, the memory controller 104 (or the memory management circuit 202 ) records the available physical erase units 410 ( 5 )˜ 410 ( 8 ) in the spare area 504 .

Please refer to FIG. 9 , assuming that the update data UD1 is to be programmed and the update data UD1 belongs to the first logical page of the logical unit LBA (0), the memory controller 104 (or the memory management circuit 202) will extract the physical page from the spare area 504 The erasing unit 410(5) serves as the physical erasing unit of the global chaos area 550 and issues a programming command to write the update data UD1 into the 0th physical programming unit of the physical erasing unit 410(5).

Please refer to FIG. 10 , continuing FIG. 9 , assuming that the update data UD2 is to be reprogrammed and the update data UD2 belongs to the 0th logical page of the logical unit LBA (1), the memory controller 104 (or the memory management circuit 202) will issue a programming command to write the update data UD2 into the first physical programming unit of the physical erasing unit 410(5).

Please refer to FIG. 11 and continue with FIG. 10. Assuming that the update data UD3 is to be reprogrammed and the update data UD3 belongs to the first logical page of the logic unit LBA (2), the memory controller 104 (or the memory management circuit 202) will issue a program command to write the update data UD3 into the second physical programming unit of the physical erasing unit 410(5).

Please refer to FIG. 12 and continue with FIG. 11. Assuming that the update data UD4 is to be reprogrammed and the update data UD4 belongs to the 0th logical page of the logical unit LBA (3), the physical erasing unit 410 (5) has no memory due to global confusion. Therefore, the memory controller 104 (or the memory management circuit 202) will extract the physical erase unit 410(6) from the spare area 504 as the physical erase unit of the global chaos area 550 and issue a program command to update the data UD4 Write to the 0th physical programming unit of the physical erasing unit 410(6).

Please refer to FIG. 13 and continue with FIG. 12. Assuming that the update data UD5 is to be reprogrammed and the update data UD5 belongs to the first logical page of the logic unit LBA (3), the memory controller 104 (or the memory management circuit 202) will issue a programming command to write the update data UD5 into the first physical programming unit of the physical erasing unit 410(6).

Please refer to FIG. 14 and continue with FIG. 13. Assuming that the update data UD6 is to be reprogrammed and the update data UD6 belongs to the second logical page of the logical unit LBA (0), the memory controller 104 (or the memory management circuit 202) will issue a program command to write the update data UD6 into the second physical programming unit of the physical erasing unit 410(6).

In order to be able to identify that the data stored in the physical erasing unit of the global chaotic area belongs to that logical page (also called an updated logical page) of that logical unit (also called an updated logical unit), in this exemplary embodiment , the memory management circuit 202 will establish a global chaos area search table to facilitate the search of valid data. Here, the logical page to which the update data temporarily stored in the global chaotic area belongs is called an updated logical page and the logical unit block to which the updated logical page belongs is called an updated logical unit. In the global chaotic area search table, the memory controller 104 (or the memory management circuit 202 ) will create multiple root units and configure a login link for each root unit. In particular, the memory controller 104 (or the memory management circuit 202) will group the logical pages of the logical units to correspond to one of the root units respectively, and record the update information of the updated logical pages in the login chain of the corresponding root unit knot. Based on this, when it is desired to search for update data of a specific logical unit in the global chaos physical erasing unit, only the login link of the corresponding root unit needs to be searched.

For example, in this exemplary embodiment, the memory controller 104 (or the memory management circuit 202 ) maps the logical pages of each logical unit to the same root unit. That is, the logical pages of the same logical unit correspond to the same root unit. It must be understood that the present invention is not limited thereto. For example, in another exemplary implementation of the present invention, a part of logical pages of a logical unit may also be grouped into a root unit and another part of logical pages of this logical unit may be grouped into another root unit. a unit.

In addition, when a log link is configured for each root unit and whenever a write command is executed, the memory controller 104 (or memory management circuit 202) will create a log on the corresponding log link to record the write Update information for incoming instructions. For example, each entry includes a first field (e.g., field 902 of FIG. 15), a second field (e.g., field 904 of FIG. 15) and a third field (e.g., field 906 of FIG. 6) , wherein the first column records the address of the updated logical page, the second column records the physical address for storing the update data of the updated logical page, and the third column marks whether the login is valid. Here, if the registration is valid, the third field will be marked as '1', for example; and if the registration is invalid, the third field will be marked as '0', for example. It must be understood that the method of marking valid logins and invalid logins is not limited to this. For example, it is also possible to have a '1' for an invalid login and a '0' for a valid login.

FIG. 15 is a simplified example of the global chaos area search table shown in FIG. 14 .

Please refer to FIG. 15, the global chaos area search table 800 includes root units 810(0)-810(4), wherein the logical pages of the logical unit LBA(0) correspond to the root unit 810(0), and the logical pages of the logical unit LBA(1) The logical page is the corresponding root unit 810(1), the logical page of the logical unit LBA(2) is the corresponding root unit 810(2), the logical page of the logical unit LBA(3) is the corresponding root unit 810(3), and the logical unit The logical page of LBA(4) is the corresponding root unit 810(4).

Include 2 valid entries in the entry link of the root unit 810(0) to record the 1st logical page (i.e., information "LBA(0)-1") and the 2nd logical page of the logical unit LBA(0) The page (i.e., the information "LBA(0)-2") has been updated, wherein the update data of the 1st logical page of the logical unit LBA(0) is written to the 0th page of the physical erase unit 410(5) In the physical program unit (i.e., information "410(5)-0") and the update data of the 2nd logical page of the logical unit LBA(0) is written to the 2nd physical page of the physical erase unit 410(6) in the programming unit (ie, information "410(6)-2").

Include 1 valid entry in the entry link of root unit 810(1) to record that logical page 0 of logical unit LBA(1) (i.e., information "LBA(1)-0") has been updated, where The update data of the 0th logical page of the logical unit LBA(1) is written into the 1st physical programming unit (ie, information “410(5)-1”) of the physical erasing unit 410(5).

Include 1 valid login in the login link of root unit 810(2) to record that logical page 1 of logical unit LBA(2) (i.e., information "LBA(2)-1") has been updated, where The update data of the first logical page of the logical unit LBA(2) is written into the second physical programming unit of the physical erasing unit 410(5) (ie, information “410(5)-2”).

Include 2 valid entries in the entry link of the root unit 810(3) to record the 0th logical page of the logical unit LBA(3) (i.e., the information "LBA(3)-0") and the 1st logical page The page (i.e., the information "LBA(3)-1") has been updated, wherein the update data of the 0th logical page of the logical unit LBA(3) is written to the 0th logical page of the physical erase unit 410(6) In the physical program unit (i.e., information "410(6)-0") and the update data of the 1st logical page of the logical unit LBA(3) is written to the 1st physical page of the physical erase unit 410(6) in the programming unit (ie, information "410(6)-1").

In addition, one empty entry is included in the entry links of the root units 810 ( 0 ) to 810 ( 4 ), indicating the end of the entry links. For example, if it is desired to search for data belonging to the logical unit LBA (4) in the global chaos physical erasing unit, the memory controller 104 (or the memory management circuit 202) can only have the free space according to the login link of the root unit 810 (4). However, it is recognized that no data belonging to the logical unit LBA (4) is stored in the global chaotic physical erasing unit, so that the data can be directly obtained from the physical programming unit of the corresponding physical erasing unit according to the information in the logical-to-physical address mapping table. read data.

By analogy, the memory controller 104 (or the memory management circuit 202 ) will sequentially write the data to be stored by the host system 1000 into the physical erasing unit serving as the global chaotic area. In particular, when the number of physical erasing units in the global chaotic area reaches 3, the memory controller 104 (or the memory management circuit 202) will execute the data consolidation program when executing the write command, so as to prevent the physical erasing of the idle area. The division unit is exhausted.

FIGS. 16-21 illustrate simplified examples of executing the global chaotic area valid data merging process to complete subsequent write commands.

Please refer to FIG. 16 and continue with FIG. 14. Assuming that the update data UD7 is to be reprogrammed and the update data UD7 belongs to the 0th logical page of the logical unit LBA (2), the physical erasing unit 410 (6) has no memory due to global confusion. space, and the number of physical erase units serving as the global chaos area 550 has reached 2, therefore, the memory management circuit 202 will perform a data consolidation procedure before performing a write operation. That is to say, in this example, during the execution of the write command, the memory management circuit 202 will also execute the data merging procedure.

For example, first, the memory controller 104 (or the memory management circuit 202 ) will select the logical unit LBA(0) to perform data merging. At this point, the memory management circuit 202 will recognize that the logical unit LBA(0) is a mapped physical erase unit 410(0), extract the physical erase unit 410(7) from the spare area 504, and map the physical erase unit 410(0) And the valid data belonging to the logical unit LBA(0) in the global chaos area 550 is copied to the physical erasing unit 410(7). Specifically, the memory controller 104 (or the memory management circuit 202) sequentially transfers the data ID1 in the physical erasing unit 410(0), the UD1 in the physical erasing unit 410(5) and the data ID1 in the physical erasing unit 410 The data UD6 in (6) is written into the 0th to 2nd physical programming units of the physical erasing unit 410 (7), and the 0th physical programming unit of the physical erasing unit 410 (5) and the physical erasing The second physical programming unit of unit 410(6) is marked invalid (as shown by the slash). Afterwards, the memory controller 104 (or the memory management circuit 202) performs an erase operation on the physical erase unit 410(0), and remaps the logical unit LBA(0) to the physical erase unit in the logical-to-physical address mapping table 410(7), and associate the physical erase unit 410(0) to the spare area 504.

Referring to FIG. 17 , next, the memory controller 104 (or the memory management circuit 202 ) will select the logic unit LBA( 1 ) to perform data merging. At this point, the memory management circuit 202 will recognize that the logical unit LBA(1) is a mapped physical erase unit 410(1), extract the physical erase unit 410(8) from the spare area 504, and map the physical erase unit 410(1) to And the valid data belonging to the logical unit LBA(1) in the global chaotic area 550 is copied to the physical erasing unit 410(8). Afterwards, the memory controller 104 (or the memory management circuit 202) performs an erase operation on the physical erase unit 410(1), and remaps the logical unit LBA(1) to the physical erase unit in the logical-to-physical address mapping table 410(8), and associate physical erase unit 410(1) to spare area 504.

Referring to FIG. 18 , next, the memory controller 104 (or the memory management circuit 202 ) will select the logic unit LBA( 2 ) to perform data merging. At this point, the memory management circuit 202 will recognize that the logical unit LBA(2) is a mapped physical erase unit 410(2), extract the physical erase unit 410(0) from the spare area 504, and map the physical erase unit 410(2) And the valid data belonging to the logical unit LBA(2) in the global chaotic area 550 is copied to the physical erasing unit 410(0). Afterwards, the memory controller 104 (or the memory management circuit 202) performs an erase operation on the physical erase unit 410(2), and remaps the logical unit LBA(2) to the physical erase unit in the logical-to-physical address mapping table 410(0), and associate physical erase unit 410(2) to spare area 504.

Please refer to FIG. 19, and then, when the memory controller 104 (or memory management circuit 202) selects the logic unit LBA (3) for data merging, the memory management circuit 202 will recognize that the logic unit LBA (3) is a mapping physical erasing unit 410(3), extract the physical erasing unit 410(1) from the spare area 504, and copy the valid data belonging to the logical unit LBA(3) in the physical erasing unit 410(3) and the global chaotic area 550 to the physical erasing unit 410(3) In unit 410(1). Afterwards, the memory controller 104 (or the memory management circuit 202) performs an erase operation on the physical erase unit 410(3), and remaps the logical unit LBA(3) to the physical erase unit in the logical-to-physical address mapping table 410(1), and associate physical erase unit 410(3) to spare area 504.

In particular, at this time, the data stored in the physical erasing units of the global chaos area 550 are all invalid data, therefore, the memory controller 104 (or the memory management circuit 202) will perform physical erasing on the physical erasing units 410(5) and 410( 6) Execute the erasing operation, and associate the erased physical erasing units 410(5) and 410(6) to the idle area 504 (as shown in FIG. 20 ), thereby completing the effective data merging of the global chaotic area 550 operate.

Please refer to FIG. 21 , after the valid data merging operation of the global chaos area 550 is completed, the memory controller 104 (or memory management circuit 202 ) will extract the physical unit 410 ( 2 ) from the spare area 504 as a physical wipe of the global chaos area 550 Delete cells and issue a program command to write this update data UD7 to the 0th physical page of physical unit 410(2).

Therefore, according to the above-mentioned operation, the memory controller 104 (or the memory management circuit 202) will store back the valid data on the physical erasing unit in the global chaos area 550 to the physical erasing unit mapped to the logical unit, and store The global chaos physical erasure unit of invalid data is associated back to the spare area 504, and the empty physical erasure unit is extracted from the spare area 504 as the global chaos physical erasure unit, so that the number of physical erasure units in the global chaos area 550 is kept less than Upper limit.

It is worth mentioning that, as mentioned above, when performing the data merge operation of the global chaos area 550, the memory controller 104 (or the memory management circuit 202) needs to merge valid data belonging to different logical units, and update the logical-to-physical address mapping surface. In particular, as mentioned above, due to the limited capacity of the buffer memory 208, only a limited logic-to-physical address mapping table can be loaded, therefore, if these logical units belong to different logical regions, the memory controller 104 (or memory management The circuit 202) needs to load and restore different logic-to-physical address mapping tables multiple times in order to complete the data merging operation of the global chaos area 550, resulting in a delay in the execution of the write command. Based on this, in this exemplary embodiment, the memory controller 104 (or the memory management circuit 202) will record the current data fragmentation degree of the global chaos area 550, and determine whether the current data fragmentation degree of the global chaos area 550 is less than the data fragmentation degree threshold . In particular, the memory controller 104 (or the memory management circuit 202) will use the global chaos area 550 to store data from the host system 1000 only when the data fragmentation degree corresponding to the current global chaos area 550 is less than the data fragmentation degree threshold .

For example, in an exemplary embodiment of the present invention, the memory controller 104 (or the memory management circuit 202 ) records how many logical areas of data are stored in the global chaos area 550 . Specifically, when the update data of a logical page is stored in the global chaos area 550, the memory controller 104 (or the memory management circuit 202) can know which logical unit this logical page belongs to (that is, the updated logical unit) and This logical unit belongs to that logical area (that is, the logical area that has been updated), therefore, the memory controller 104 (or the memory management circuit 202) can record the number of the logical area that has been updated (that is, how many data in the logical area have been updated) stored in the global chaos area 550). In particular, if the current number of updated logical regions is greater than the preset value, the memory controller 104 (or the memory management circuit 202 ) will identify that the current data fragmentation degree of the global chaos area 550 is not less than the data fragmentation degree threshold.

It should be noted that judging the fragmentation of data in the global chaos area 550 by the number of updated logical areas is just an example, and the present invention is not limited thereto. For example, in another exemplary embodiment, the memory controller 104 (or the memory management circuit 202 ) may also update the number of logical units to identify the data fragmentation degree of the global chaos area 550 . For example, if the current number of updated logical units is greater than the preset value, the memory controller 104 (or the memory management circuit 202 ) will identify that the current data fragmentation degree of the global chaos area 550 is not less than the data fragmentation degree threshold.

Furthermore, since the data merging operation of the global chaotic area 550 is performed, the logical-to-physical address mapping table corresponding to the updated logical unit (hereinafter referred to as the logical-to-physical address mapping table to be updated) needs to be updated. Therefore, in another exemplary embodiment, the memory controller 104 (or the memory management circuit 202 ) can also identify the data fragmentation degree of the global chaos area 550 by the number of logical-to-physical address mapping tables to be updated. For example, if the number of logical-to-physical address mapping tables to be updated is greater than a preset value, the memory controller 104 (or the memory management circuit 202 ) will identify that the current data fragmentation degree of the global chaos area 550 is not less than the data fragmentation degree threshold.

In this exemplary embodiment, if the data fragmentation degree corresponding to the current global chaos area 550 is not less than the data fragmentation degree threshold, the memory controller 104 (or the memory management circuit 202) will use the sub-physical erase unit to write data from the data from the host system 1000 and update the corresponding logical-to-physical address mapping table.

22 to 24 illustrate examples of using sub-physical erasing units to write update data.

Please refer to FIGS. 22 to 24 at the same time. For example, in the mapping state where the logical unit LBA(0) is mapped to the physical erasing unit 410(0), when the memory controller 104 (or the memory management circuit 202) from the host system 1000 When receiving a write command and wanting to write data to a logical page belonging to the logical unit LBA(0), the memory controller 104 (or memory management circuit 202) identifies the current state of the logical unit LBA(0) according to the logical-to-physical address mapping table Yes maps to physical erase unit 410(0) and extracts physical erase unit 410(H+1) from spare area 504 to alternate physical erase unit 410(0). However, when new data is written into the physical erasing unit 410(H+1), the memory controller 104 (or the memory management circuit 202) may not immediately move all valid data in the physical erasing unit 410(0) Go to physical erase unit 410(H+1) to erase physical erase unit 410(0). Specifically, the memory controller 104 (or the memory management circuit 202) will read from the physical erasing unit 410(0) the valid data to be written before the physical programming unit (that is, the data of the physical erasing unit 410(0) Data in the 0th physical programming unit and the 1st physical programming unit). Afterwards, the memory controller 104 (or the memory management circuit 202) will write the valid data in the physical erasing unit 410(0) before the physical programming unit to the 0th bit of the physical erasing unit 410(H+1). The physical programming unit and the first physical programming unit (as shown in FIG. 22 ), and write new data into the second to fourth physical programming units of the physical erasing unit 410 (H+1) (as shown in FIG. 23 Show). At this point, the memory controller 104 (or the memory management circuit 202 ) completes the writing operation. Because the valid data in the physical erase unit 410(0) may become invalid in the next operation (for example, a write command), the valid data in the physical erase unit 410(0) is immediately moved to the physical erase unit 410(0). Unit 410(H+1) may cause unnecessary movement. In addition, data must be sequentially written to the physical programming units in the physical erasing unit, therefore, the memory controller 104 (or the memory management circuit 202) can first move the valid data (ie, storage Data in the 0th physical programming unit and the 0th physical programming unit of the physical erasing unit 410 (0), and the remaining valid data (that is, stored in the 5th to Kth physical programming unit 410 (0) of the physical erasing unit 410 (0) data in physical programming units).

In this exemplary embodiment, the operation of temporarily maintaining these transient relationships is called opening (opening) the parent-child physical erasing unit, and the original physical erasing unit (for example, the above-mentioned physical erasing unit 410(0)) is called The physical erasing unit (for example, the above physical erasing unit 410(H+1)) used to replace the mother physical erasing unit is called a child physical erasing unit.

Afterwards, when the data of the physical erasing unit 410 (0) and the physical erasing unit 410 (H+1) need to be merged (merge), the memory controller 104 (or memory management circuit 202) will physically erase the unit 410 (0) and the data of the physical erasing unit 410 (H+1) are merged into one physical erasing unit, thereby improving the usage efficiency of the physical erasing unit. Here, the operation of merging the parent-child physical erasing unit is called a data merging procedure or closing (close) the parent-child physical erasing unit. For example, as shown in FIG. 24 , when the parent-child block is closed, the memory controller 104 (or the memory management circuit 202) will read the remaining valid data from the physical erase unit 410 (0) (that is, the physical erase Data in the 5th to K physical programming units of unit 410 (0), write the remaining valid data in physical erasing unit 410 (0) to the fifth physical programming of physical erasing unit 410 (H+1) In the unit to the Kth physical programming unit, the erase operation is performed on the physical erase unit 410(0), and the erased physical erase unit 410(0) is associated with the idle area 504 and the physical erase unit 410 (H+ 1) Link to the data area 502 . That is to say, the memory controller 104 (or the memory management circuit 202 ) remaps the logical unit LBA(0) to the physical erasing unit 410(H+1) in the logical-to-physical address mapping table. It is worth mentioning that the number of physical erasing units in the spare area 504 is limited. Therefore, during the operation of the memory storage device 100 , the number of activated parent-child physical erasing unit groups is also limited. Therefore, when the memory storage device 100 receives a write command from the host system 1000, if the number of the opened mother-child physical erasing unit groups reaches the upper limit, the memory controller 104 needs to close at least one group of currently opened mother-child physical erasing units. This write command can only be executed after the cell group is erased.

FIG. 25 is a flowchart of a data writing method according to an exemplary embodiment of the present invention.

Referring to FIG. 25 , in step S2501 , at least one physical erasing unit is extracted from the spare area 504 as a physical erasing unit of the global chaotic area 550 .

In step S2503 , a global chaotic area search table is established and stored in the buffer memory 208 to record update information corresponding to a plurality of updated logical pages in the global chaotic area 550 .

In step S2505, the write command indicating to write data to a logical page (hereinafter referred to as the first logical page) of a logical unit (hereinafter referred to as the first logical unit) and the update data corresponding to the write command will be take over.

In step S2507, the current data fragmentation degree of the global chaos area 550 will be recorded and judged whether it is smaller than the data fragmentation degree threshold.

If the current fragmentation of data in the global chaos area 550 is less than the data fragmentation threshold, then in step S2509, the update data will be written into the global chaos area 550 and the update information corresponding to the first logical page will be recorded in In the global chaos area search table. The manner of writing update data into the global chaos area 550 and recording the update information in the search table of the global chaos area has been described in detail above with reference to FIGS. 8-15 , and will not be repeated here.

If the fragmentation degree of data in the global chaotic area 550 is not less than the data fragmentation degree threshold, then in step S2511, a physical erasing unit (hereinafter referred to as the first physical erasing unit) will be extracted from the spare area 504 as a corresponding The sub-physical erasing unit of the first logical unit and update data are written into the sub-physical erasing unit corresponding to the first logical unit. The manner of writing update data in sub-physical erasing units has been described above in detail with reference to FIGS. 22-24 , and will not be repeated here.

It is worth mentioning that if the global chaotic area already has logical units that belong to the current data to be written into, writing the update data into the global chaotic area 550 will not increase the fragmentation of data in the global chaotic area 550, so , the update data can be directly stored in the global chaos area 550 . For example, in another exemplary embodiment of the present invention, before the above step S2507, it may be further determined whether the global chaos area 550 stores valid data belonging to the first logic unit. Moreover, if the global chaos area 550 stores valid data belonging to the first logic unit, step S2509 will be executed. Step S2507 is executed only if no valid data belonging to the first logical unit is stored in the global chaos area 550 .

To sum up, the data writing method, memory controller and memory storage device of the exemplary embodiments of the present invention will calculate the data fragmentation degree of the global chaotic area before writing the update data into the global chaotic area, and only when the global chaotic area The updated data is temporarily stored in the global chaos area only when the fragmentation degree of the data is less than the threshold value of the fragmentation degree of data, thereby avoiding wasting too much time on updating the logical-to-physical address table when performing the effective data merging operation of the global chaos physical erasing unit, Instead, the execution of the write instruction is delayed. Therefore, the data writing method, the memory controller and the memory storage device of the exemplary embodiments of the present invention can effectively improve the performance of data writing.

Claims (21)

1. a method for writing data, for writing data to reproducible nonvolatile memorizer module, wherein this reproducible nonvolatile memorizer module has multiple physics erased cell, each these physics erased cell has multiple physics programming unit, these physics erased cell are at least grouped into a data field and an idle district, the physics erased cell in this idle district is in order to replace the physics erased cell of this data field to write data, multiple logical block is configured to these physics erased cell mapping this data field, and each these logical block has multiple logical page (LPAGE), this method for writing data comprises:

At least one physics erased cell is extracted as the chaotic district of a universe from these physics erased cell in this idle district, wherein the chaotic district of this universe is in order to the temporary data belonging to multiple more new logical page, and these more new logical page to belong among these logical blocks multiple upgrades logical block;

Set up the chaotic district's search table of a universe to be recorded in multiple lastest imformations of these more new logical page corresponding in the chaotic district of this universe;

Receive a write instruction with to a more new data that should write instruction, wherein this more new data be belong to one first logical page (LPAGE) and this first logical page (LPAGE) belongs to one first logical block among these logical blocks;

Record should the scattered degree of data in the chaotic district of universe;

Judge the scattered degree of these data in the chaotic district of universe whether being less than the scattered degree threshold value of data; And

If to should the scattered degree of these data in the chaotic district of universe be less than these data scattered degree threshold value time, by this more new data to write in the chaotic district of this universe and record should a lastest imformation of the first logical page (LPAGE) in the chaotic district's search table of this universe.

2. method for writing data as claimed in claim 1, also comprises:

If to should the scattered degree of these data in the chaotic district of universe is non-be less than these data scattered degree threshold value time, one first physics erased cell is extracted as to should a muon physics erased cell of the first logical block among these physics erased cell in this idle district, by this more new data write in this muon physics erased cell, and upgrade a logic of the first logical block turning physical address mapping table, wherein this muon physics erased cell is only in order to store the data belonging to this first logical block.

3. method for writing data as claimed in claim 1, also comprises:

These logical blocks are grouped into multiple logic region; And

Configure multiple logic and turn physical address mapping table to be assigned to these logic regions respectively, wherein these logics turn physical address mapping table in order to record multiple mapping relations between the logical block of these logic regions and the physics erased cell of this data field and each these logic turns physical address mapping table is configured independently to one of them of these logic regions.

4. method for writing data as claimed in claim 3, wherein these have upgraded multiple that logical block belongs among these logic regions and have upgraded logic region,

Wherein record should the step of the scattered degree of these data in the chaotic district of universe comprise:

Calculate the number that these have upgraded logic region; And

Record these numbers having upgraded logic region as to should the scattered degree of these data in the chaotic district of universe.

5. method for writing data as claimed in claim 1, wherein records should the step of the scattered degree of these data in the chaotic district of universe comprise:

Calculate the number that these have upgraded logical block; And

Record these numbers having upgraded logical block as to should the scattered degree of these data in the chaotic district of universe.

6. method for writing data as claimed in claim 1, wherein records should the step of the scattered degree of these data in the chaotic district of universe comprise:

Calculate the number that multiple logic to be updated turns physical address mapping table, wherein these logics to be updated turn physical address mapping table in order to the mapping between the physics erased cell that records these and upgraded logical block and this data field; And

Record number that these logics to be updated turn physical address mapping table as to should the scattered degree of these data in the chaotic district of universe.

7. method for writing data as claimed in claim 1, also comprises:

Judge whether there are the valid data belonging to this first logical block in the chaotic district of this universe; And

If when having the valid data belonging to this first logical block in the chaotic district of this universe, by this more new data write in the chaotic district of this universe,

Wherein above-mentioned judgement to should the scattered degree of these data in the chaotic district of the universe step that whether is less than the scattered degree threshold value of these data be and do not have the valid data belonging to this first logical block in the chaotic district of this universe time be performed.

8. a Memory Controller, for controlling a reproducible nonvolatile memorizer module, this Memory Controller comprises:

One host interface, in order to be electrically connected to a host computer system;

One memory interface, in order to be electrically connected to this reproducible nonvolatile memorizer module, wherein this reproducible nonvolatile memorizer module has multiple physics erased cell, each these physics erased cell has multiple physics programming unit, these physics erased cell are at least grouped into a data field and an idle district, and the physics erased cell in this idle district is in order to replace the physics erased cell of this data field to write data; And

One memory management circuitry, is electrically connected to this host interface and this memory interface, and in order to configure multiple logical block to map these physics erased cell of this data field, wherein each these logical block has multiple logical page (LPAGE),

Wherein this memory management circuitry also in order to extract at least one physics erased cell as the chaotic district of a universe from these physics erased cell in this idle district, wherein the chaotic district of this universe is in order to the temporary data belonging to multiple more new logical page, and these more new logical page to belong among these logical blocks multiple upgrades logical block

Wherein this memory management circuitry is also in order to set up the chaotic district's search table of a universe to be recorded in multiple lastest imformations of these more new logical page corresponding in the chaotic district of this universe,

Wherein this memory management circuitry also in order to receive a write instruction with to a more new data that should write instruction, this more new data be belong to one first logical page (LPAGE) and this first logical page (LPAGE) belongs to one first logical block among these logical blocks,

Wherein this memory management circuitry also in order to record to should the chaotic district of universe the scattered degree of data and judge the scattered degree of these data in universe confusion district whether being less than the scattered degree threshold value of data,

If wherein to should the scattered degree of these data in the chaotic district of universe be less than these data scattered degree threshold value time, this memory management circuitry by this more new data to write in the chaotic district of this universe and record should a lastest imformation of the first logical page (LPAGE) in the chaotic district's search table of this universe.

9. Memory Controller as claimed in claim 8, if wherein to should the scattered degree of these data in the chaotic district of universe is non-be less than these data scattered degree threshold value time, this memory management circuitry extracts one first physics erased cell as to should a muon physics erased cell of the first logical block among these physics erased cell in this idle district, by this more new data write in this muon physics erased cell, and upgrade a logic of the first logical block turning physical address mapping table

Wherein this muon physics erased cell is only in order to store the data belonging to this first logical block.

10. Memory Controller as claimed in claim 8, wherein this memory management circuitry also turns physical address mapping table to be assigned to these logic regions respectively in order to these logical blocks are grouped into multiple logic region and configure multiple logic,

Wherein these logics turn physical address mapping table in order to record multiple mapping relations between the logical block of these logic regions and the physics erased cell of this data field and each these logic turns physical address mapping table is configured independently to one of them of these logic regions.

11. Memory Controllers as claimed in claim 10, wherein these have upgraded multiple that logical block belongs among these logic regions and have upgraded logic region,

Wherein record to should the chaotic district of universe the scattered degree of these data running in, this memory management circuitry calculates these numbers having upgraded logic region and records these numbers having upgraded logic region as to should the scattered degree of these data in the chaotic district of universe.

12. Memory Controllers as claimed in claim 8, wherein record to should the chaotic district of universe the scattered degree of these data running in, this memory management circuitry calculates these numbers having upgraded logical block and records these numbers having upgraded logical block as to should the scattered degree of these data in the chaotic district of universe.

13. Memory Controllers as claimed in claim 8, wherein record to should the chaotic district of universe the scattered degree of these data running in, this memory management circuitry calculates multiple logic to be updated and turns the number of physical address mapping table and record number that these logics to be updated turn physical address mapping table as to should the scattered degree of these data in the chaotic district of universe

Wherein these logics to be updated turn physical address mapping table in order to the mapping between the physics erased cell that records these and upgraded logical block and this data field.

14. Memory Controllers as claimed in claim 8, wherein this memory management circuitry is also in order to judge whether there are the valid data belonging to this first logical block in the chaotic district of this universe,

If when wherein having the valid data belonging to this first logical block in the chaotic district of this universe, this memory management circuitry by this more new data write in the chaotic district of this universe,

Above-mentioned judgement is performed to the scattered degree of these data in the chaotic district of universe whether being less than the running of these data scattered degree threshold value when wherein this memory management circuitry is and does not have the valid data belonging to this first logical block in the chaotic district of this universe.

15. 1 kinds of memory storage apparatus, comprising:

A connector, in order to be electrically connected to a host computer system;

One reproducible nonvolatile memorizer module, there is multiple physics erased cell, each these physics erased cell has multiple physics programming unit, these physics erased cell are at least grouped into a data field and an idle district, and the physics erased cell in this idle district is in order to replace the physics erased cell of this data field to write data; And

One Memory Controller, is electrically connected to this connector and this reproducible nonvolatile memorizer module, and in order to configure multiple logical block to map these physics erased cell of this data field, wherein each these logical block has multiple logical page (LPAGE),

Wherein this Memory Controller also in order to extract at least one physics erased cell as the chaotic district of a universe from these physics erased cell in this idle district, wherein the chaotic district of this universe is in order to the temporary data belonging to multiple more new logical page, and these more new logical page to belong among these logical blocks multiple upgrades logical block

Wherein this Memory Controller is also in order to set up the chaotic district's search table of a universe to be recorded in multiple lastest imformations of these more new logical page corresponding in the chaotic district of this universe,

Wherein this Memory Controller also in order to receive a write instruction with to a more new data that should write instruction, this more new data be belong to one first logical page (LPAGE) and this first logical page (LPAGE) belongs to one first logical block among these logical blocks,

Wherein this Memory Controller also in order to record to should the chaotic district of universe the scattered degree of data and judge the scattered degree of these data in universe confusion district whether being less than the scattered degree threshold value of data,

If wherein to should the scattered degree of these data in the chaotic district of universe be less than these data scattered degree threshold value time, this Memory Controller by this more new data to write in the chaotic district of this universe and record should a lastest imformation of the first logical page (LPAGE) in the chaotic district's search table of this universe.

16. memory storage apparatus as claimed in claim 15, if wherein to should the scattered degree of these data in the chaotic district of universe is non-be less than these data scattered degree threshold value time, this Memory Controller extracts one first physics erased cell as to should a muon physics erased cell of the first logical block among these physics erased cell in this idle district, by this more new data write in this muon physics erased cell, and upgrade a logic of the first logical block turning physical address mapping table

Wherein this muon physics erased cell is only in order to store the data belonging to this first logical block.

17. memory storage apparatus as claimed in claim 15, wherein this Memory Controller also turns physical address mapping table to be assigned to these logic regions respectively in order to these logical blocks are grouped into multiple logic region and configure multiple logic,

Wherein these logics turn physical address mapping table in order to record multiple mapping relations between the logical block of these logic regions and the physics erased cell of this data field and each these logic turns physical address mapping table is configured independently to one of them of these logic regions.

18. memory storage apparatus as claimed in claim 17, wherein these have upgraded multiple that logical block belongs among these logic regions and have upgraded logic region,

Wherein record to should the chaotic district of universe the scattered degree of these data running in, this Memory Controller calculates these numbers having upgraded logic region and records these numbers having upgraded logic region as to should the scattered degree of these data in the chaotic district of universe.

19. memory storage apparatus as claimed in claim 15, wherein record to should the chaotic district of universe the scattered degree of these data running in, this Memory Controller calculates these numbers having upgraded logical block and records these numbers having upgraded logical block as to should the scattered degree of these data in the chaotic district of universe.

20. memory storage apparatus as claimed in claim 15, wherein record to should the chaotic district of universe the scattered degree of these data running in, this Memory Controller calculates multiple logic to be updated and turns the number of physical address mapping table and record number that these logics to be updated turn physical address mapping table as to should the scattered degree of these data in the chaotic district of universe

Wherein these logics to be updated turn physical address mapping table in order to the mapping between the physics erased cell that records these and upgraded logical block and this data field.

21. memory storage apparatus as claimed in claim 15, wherein this Memory Controller is also in order to judge whether there are the valid data belonging to this first logical block in the chaotic district of this universe,

If when wherein having the valid data belonging to this first logical block in the chaotic district of this universe, this Memory Controller by this more new data write in the chaotic district of this universe,

Above-mentioned judgement is performed to the scattered degree of these data in the chaotic district of universe whether being less than the running of these data scattered degree threshold value when wherein this Memory Controller is and does not have the valid data belonging to this first logical block in the chaotic district of this universe.