CN111208932B

CN111208932B - Mapping table updating method, memory control circuit unit and memory storage device

Info

Publication number: CN111208932B
Application number: CN201811389248.6A
Authority: CN
Inventors: 颜嘉汉; 陈全祥
Original assignee: Phison Electronics Corp
Current assignee: Phison Electronics Corp
Priority date: 2018-11-21
Filing date: 2018-11-21
Publication date: 2023-03-24
Anticipated expiration: 2038-11-21
Also published as: CN111208932A

Abstract

The invention provides a mapping table updating method, a memory control circuit unit and a memory storage device. The method comprises the following steps: respectively calculating a plurality of updated data counts of the plurality of updated logic units in the active physical erasing unit according to the physical-logic mapping table; selecting a first updated logic cell from the plurality of updated logic cells according to the update data count, wherein the number of the first updated logic cells is less than the number of the updated logic cells; loading a first logical-to-physical mapping table corresponding to the first updated logical unit; and updating the mapping information in the first logical-to-physical mapping table according to the mapping information of the first updated logical unit in the physical-to-logical mapping table.

Description

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

Technical Field

The invention relates to a mapping table updating method, a memory control circuit unit and a memory storage device.

Background

Digital cameras, cellular phones, and MP3 have grown rapidly over the years, resulting in a rapid increase in consumer demand for storage media. Since the rewritable non-volatile memory (rewritable non-volatile memory) has the characteristics of non-volatility, power saving, small volume, no mechanical structure, high read-write speed and the like, the rewritable non-volatile memory is most suitable for portable electronic products such as notebook computers. A solid state disk is a memory storage device using a 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 erase units and each physical erase unit has a plurality of physical program units (physical pages), wherein data must be written according to the sequence of the physical program units when data is written in the physical erase units. In addition, the physical programming unit to which data has been written needs to be erased before it can be used for writing data again. In particular, a physically erased cell is the smallest unit of erase, and a physically programmed cell is the smallest unit of programming (also called writing). Therefore, in the management of the flash memory module, the physical erase unit is divided into a data area and an idle area.

The physical erasing units of the data area are used for storing data stored by a host system. Specifically, the memory management circuit in the memory storage device converts the logical access address accessed by the host system into the logical page of the logical block and maps the logical page of the logical block to the physical programming unit of the physical erasing unit of the data area. That is, the physical erase units of the managed data area of the flash memory module are considered as used physical erase units (e.g., stored data written by the host system). For example, the memory management circuit uses a logical-physical mapping table (logical-physical mapping table) to describe the mapping relationship between the logical page and the physical program unit of the data area.

The physical erasing units in the idle area are used for replacing the physical erasing units in the data area. Specifically, as described above, the physical erase unit to which data has been written must be erased before being used again for writing data, and therefore, the physical erase unit in the spare area is designed to write the update data to replace the physical erase unit of the mapped logical block. Therefore, the physical erasing units in the idle area are empty or the physical erasing units which can be used for writing data.

In a general write operation, after data is written into the physical erase unit of the idle area, the memory management circuit in the memory storage device does not immediately change the mapping relationship between the logical page and the physical program unit in the logical-to-physical mapping table, but stores mapping information corresponding to the write operation by using a physical-to-logical mapping table (physical-to-logical mapping table) stored in the buffer memory. Specifically, in a write operation, the memory management circuit writes the update data into a physical erase unit (also called an active physical erase unit) in the spare area, and records mapping information between the logical page related to the write operation and the physical program unit for storing the update data in the physical-to-logical mapping table. When the mapping information between the logical page and the physical program unit is updated, the memory management circuit loads the corresponding logical-to-physical mapping table according to the mapping information in the physical-to-logical mapping table. Then, the memory management circuit will restore the updated logical-physical mapping table to the rewritable non-volatile memory. The operation of updating the logical-to-physical mapping table according to the mapping information in the physical-to-logical mapping table is also referred to as "flush operation" (flush operation).

However, in the conventional flush operation, when the mapping information required to be updated in a logical-to-physical mapping table is very few (for example, only the mapping information between one logical page and the physical program unit needs to be updated), the efficiency of updating the mapping information is usually reduced. In more detail, if the above operations are repeatedly performed, a large amount of time is spent on loading and restoring the logical-physical mapping table, and only a small amount of time is actually used for performing the update of the mapping information. Therefore, how to increase the efficiency of updating the logical-physical mapping table is one of the problems to be solved by those skilled in the art.

Disclosure of Invention

The invention provides a mapping table updating method, a memory control circuit unit and a memory storage device, which can improve the efficiency of a logic-physical mapping table during updating.

The invention provides a mapping table updating method used for a rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module is provided with a plurality of physical erasing units, a plurality of logic-physical mapping tables are stored in the rewritable nonvolatile memory module to record mapping information between the plurality of logic units and the plurality of physical erasing units, and the mapping table updating method comprises the following steps: establishing a physical-logical mapping table, wherein the physical-logical mapping table records mapping information between at least one active physical erasure unit in the plurality of physical erasure units and a plurality of updated logical units in the plurality of logical units; respectively calculating a plurality of updated data counts of the plurality of updated logic units in the active physical erasing unit according to the physical-logic mapping table; selecting at least one first updated logic cell from the plurality of updated logic cells according to the plurality of updated data counts, wherein the number of the first updated logic cells is smaller than the number of the plurality of updated logic cells; loading at least a first logical-to-physical mapping table corresponding to the first updated logical unit from the plurality of logical-to-physical mapping tables; and updating the mapping information in the first logical-to-physical mapping table according to the mapping information of the first updated logical unit in the physical-to-logical mapping table.

In an embodiment of the present invention, the method further includes: clearing mapping information of the first updated logical unit in the physical-logical mapping table; reserving mapping information of other updated logical units except the first updated logical unit in the physical-logical mapping table; and storing the updated first logic-physical mapping table back to the rewritable nonvolatile memory module.

In an embodiment of the present invention, a first refresh data count of the first refreshed logical unit of the plurality of refresh data counts is greater than a first threshold value.

In an embodiment of the present invention, a first refresh data count of the first refreshed logic unit of the plurality of refresh data counts is less than a second threshold.

In an embodiment of the present invention, the step of selecting the first updated logical unit from the plurality of updated logical units comprises: sorting the plurality of update data counts; determining a third threshold value according to the plurality of sorted updated data counts; and dividing the plurality of update data count regions into at least one second update data count and at least one third update data count according to the third threshold value. Wherein the second update data count is greater than the third threshold value and the third update data count is not greater than the third threshold value.

In an embodiment of the present invention, the step of selecting the first updated logical unit from the plurality of updated logical units further comprises: identifying at least a second updated logical unit of the plurality of updated logical units corresponding to the second updated data count as the first updated logical unit, or identifying at least a third updated logical unit of the plurality of updated logical units corresponding to the third updated data count as the first updated logical unit.

The invention provides a memory control circuit unit, which is used for controlling a rewritable nonvolatile memory module and comprises: a host interface, a memory interface, and memory management circuitry. The host interface is used for electrically connecting to a host system. The memory interface is electrically connected to the rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module is provided with a plurality of physical erasing units, and a plurality of logic-physical mapping tables are stored in the rewritable nonvolatile memory module to record mapping information between a plurality of logic units and the physical erasing units. The memory management circuit is electrically connected to the host interface and the memory interface. The memory management circuit is used for executing the following operations: establishing a physical-logical mapping table, wherein the physical-logical mapping table records mapping information between at least one active physical erasure unit in the plurality of physical erasure units and a plurality of updated logical units in the plurality of logical units; respectively calculating a plurality of updated data counts of the plurality of updated logic units in the active physical erasing unit according to the physical-logic mapping table; selecting at least one first updated logic cell from the plurality of updated logic cells according to the plurality of updated data counts, wherein the number of the first updated logic cells is smaller than the number of the plurality of updated logic cells; loading at least a first logical-to-physical mapping table corresponding to the first updated logical unit from the plurality of logical-to-physical mapping tables; and updating the mapping information in the first logical-to-physical mapping table according to the mapping information of the first updated logical unit in the physical-to-logical mapping table.

In an embodiment of the invention, the memory management circuit is further configured to clear mapping information of the first updated logical unit in the physical-to-logical mapping table, retain mapping information of other updated logical units except the first updated logical unit in the physical-to-logical mapping table, and restore the updated first logical-to-physical mapping table to the rewritable nonvolatile memory module.

In an embodiment of the invention, in an operation of selecting the first updated logic cell from the plurality of updated logic cells, the memory management circuit is further configured to sort the plurality of updated data counts, determine a third threshold value according to the sorted plurality of updated data counts, and divide the plurality of updated data counts into at least one second updated data count and at least one third updated data count according to the third threshold value. Wherein the second update data count is greater than the third threshold value and the third update data count is not greater than the third threshold value.

In one embodiment of the present invention, in the operation of selecting the first updated logical unit from the plurality of updated logical units, the memory management circuit is further configured to identify at least one second updated logical unit corresponding to the second updated data count among the plurality of updated logical units as the first updated logical unit, or identify at least one third updated logical unit corresponding to the third updated data count among the plurality of updated logical units as the first updated logical unit.

The invention provides a memory storage device. The memory storage device comprises a connection interface unit, a rewritable nonvolatile memory module and a memory control circuit unit. The connection interface unit is used for electrically connecting to a host system. The rewritable nonvolatile memory module is provided with a plurality of physical erasing units, and a plurality of logic-physical mapping tables are stored in the rewritable nonvolatile memory module to record mapping information between a plurality of logic units and the physical erasing units. And the memory control circuit unit is electrically connected to the connection interface unit and the rewritable nonvolatile memory module. The memory control circuit unit is used for executing the following operations: establishing a physical-logical mapping table, wherein the physical-logical mapping table records mapping information between at least one active physical erasure unit in the plurality of physical erasure units and a plurality of updated logical units in the plurality of logical units; respectively calculating a plurality of updated data counts of the plurality of updated logic units in the active physical erasing unit according to the physical-logic mapping table; selecting at least a first updated logical unit from the plurality of updated logical units according to the plurality of updated data counts, wherein the number of the first updated logical unit is smaller than the number of the plurality of updated logical units; loading at least a first logical-to-physical mapping table corresponding to the first updated logical unit from the plurality of logical-to-physical mapping tables; and updating mapping information in the first logical-to-physical mapping table according to mapping information of the first updated logical unit in the physical-to-logical mapping table.

In an embodiment of the invention, the memory control circuit unit is further configured to clear mapping information of the first updated logical unit in the physical-to-logical mapping table, retain mapping information of other updated logical units except the first updated logical unit in the physical-to-logical mapping table, and restore the updated first logical-to-physical mapping table to the rewritable nonvolatile memory module.

In an embodiment of the invention, in an operation of selecting the first updated logic unit from the plurality of updated logic units, the memory control circuit unit is further configured to sort the plurality of updated data counts, determine a third threshold value according to the sorted plurality of updated data counts, and divide the plurality of updated data counts into at least one second updated data count and at least one third updated data count according to the third threshold value. Wherein the second update data count is greater than the third threshold value and the third update data count is not greater than the third threshold value.

In one embodiment of the present invention, in the operation of selecting the first updated logic cell from the plurality of updated logic cells, the memory control circuit unit is further configured to identify at least one second updated logic cell corresponding to the second updated data count among the plurality of updated logic cells as the first updated logic cell, or identify at least one third updated logic cell corresponding to the third updated data count among the plurality of updated logic cells as the first updated logic cell.

The invention provides a mapping table updating method used for a rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module is provided with a plurality of physical erasing units, a plurality of logic-physical mapping tables are stored in the rewritable nonvolatile memory module to record mapping information between the plurality of logic units and the plurality of physical erasing units, and the mapping table updating method comprises the following steps: establishing a physical-logical mapping table, wherein the physical-logical mapping table records mapping information between at least one active physical erasure unit in the plurality of physical erasure units and a plurality of updated logical units in the plurality of logical units; respectively calculating a plurality of updated data counts of the plurality of updated logic units in the active physical erasing unit according to the physical-logic mapping table; selecting at least one first updated logic cell from the plurality of updated logic cells according to the plurality of updated data counts, wherein the number of the first updated logic cells is less than the number of the plurality of updated logic cells and a first updated data count of the first updated logic cell in the plurality of updated data counts is greater than a first threshold value; loading at least a first logical-to-physical mapping table corresponding to the first updated logical unit from the plurality of logical-to-physical mapping tables; updating mapping information in the first logical-to-physical mapping table according to mapping information of the first updated logical unit in the physical-to-logical mapping table; clearing mapping information of the first updated logical unit in the physical-logical mapping table; and retaining mapping information of other updated logical units except the first updated logical unit in the physical-logical mapping table.

Based on the above, the mapping table updating method, the memory control circuit unit and the memory storage device of the present invention may load the corresponding logical-to-physical mapping table according to only a part of the mapping information in the physical-to-logical mapping table to perform the updating of the mapping information, and retain the other remaining part of the mapping information in the physical-to-logical mapping table. Therefore, the efficiency of the logic-physical mapping table during updating can be improved.

In order to make the aforementioned and other features and advantages of the invention more comprehensible, embodiments accompanied with figures are described in detail below.

Drawings

FIG. 1 is a diagram illustrating a host system, a memory storage device, and an input/output (I/O) device according to an example embodiment of the present invention;

FIG. 2 is a diagram illustrating a host system, a memory storage device, and an I/O device according to another example embodiment of the present invention;

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

FIG. 4 is a schematic block diagram of a memory storage device according to an exemplary embodiment of the present invention;

FIGS. 5A and 5B are schematic diagrams of an exemplary memory cell architecture and physical erase cells according to the present exemplary embodiment;

FIG. 6 is a schematic block diagram illustrating a memory control circuit unit according to an exemplary embodiment of the present invention;

FIGS. 7 and 8 are exemplary diagrams illustrating the management of physically erased cells in accordance with one exemplary embodiment;

FIGS. 9A-9C are simplified examples of data writes according to one embodiment of the present invention;

FIGS. 10A-10C are simplified examples of mapping table updates according to the first embodiment of the present invention;

FIGS. 11A-11C are simplified examples of mapping table updates according to a second embodiment of the present invention;

FIG. 12 is a flowchart illustrating a mapping table updating method according to an embodiment of the invention;

fig. 13 is a flowchart illustrating a mapping table updating method according to another embodiment of the present invention.

Description of the reference numerals

10: memory storage device

11: host system

110: system bus

111: processor with a memory for storing a plurality of data

112: random access memory

113: read-only memory

114: data transmission interface

12: input/output (I/O) device

20: main machine board

201: u disk

202: memory card

203: solid state disk

204: wireless memory storage device

205: global positioning system module

206: network interface card

207: wireless transmission device

208: keyboard with a keyboard body

209: screen

210: horn type loudspeaker

32: SD card

33: CF card

34: embedded memory device

341: embedded multimedia card

342: embedded multi-chip packaging storage device

402: connection interface unit

404: memory control circuit unit

406: rewritable nonvolatile memory module

702: memory management circuit

704: host interface

706: memory interface

708: error checking and correcting circuit

710: buffer memory

712: power management circuit

502: data area

504: idle zone

506: temporary storage area

508: substitution zone

510 (0) to 510 (N), 410 (0) to 410 (5): physical erase cell

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

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

ID1 to ID12: initial data

UD 1-UD 6: updating data

600: physical-logical mapping table

700: updating data count table

S1201: establishing a physical-to-logical mapping table, wherein the physical-to-logical mapping table records mapping information between an active physical erasure unit in the plurality of physical erasure units and a plurality of updated logical units in the plurality of logical units

S1203: respectively calculating a plurality of updated data counts of the plurality of updated logical units in the active physical erase unit according to the physical-logical mapping table

S1205: selecting a first updated logic cell from the plurality of updated logic cells according to the plurality of updated data counts, wherein the number of the first updated logic cells is less than the number of the updated logic cells

S1207: step of loading a first logical-to-physical mapping table corresponding to a first updated logical unit from a plurality of logical-to-physical mapping tables

S1209: updating mapping information in a first logical-to-physical mapping table based on mapping information for a first updated logical unit in the physical-to-logical mapping table

S1211: the step of restoring the updated first logical-physical mapping table to the rewritable nonvolatile memory module

S1301: establishing a physical-to-logical mapping table, wherein the physical-to-logical mapping table records mapping information between an active physical erasure unit in the plurality of physical erasure units and a plurality of updated logical units in the plurality of logical units

S1303: respectively calculating a plurality of updated data counts of the plurality of updated logical units in the active physical erase unit according to the physical-logical mapping table

S1305: selecting a first updated logic cell from the plurality of updated logic cells according to a plurality of updated data counts, wherein the number of the first updated logic cells is less than the number of the updated logic cells and the first updated data count of the first updated logic cell in the updated data counts is greater than a first threshold value

S1307: step of loading a first logical-to-physical mapping table corresponding to a first updated logical unit from a plurality of logical-to-physical mapping tables

S1309: updating mapping information in a first logical-to-physical mapping table based on mapping information for a first updated logical unit in the physical-to-logical mapping table

S1311: clearing mapping information of first updated logic unit in physical-logic mapping table

S1313: step of reserving mapping information of other updated logical units except the first updated logical unit in the physical-logical mapping table

S1315: the step of restoring the updated first logical-physical mapping table to the rewritable nonvolatile memory module

Detailed Description

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

FIG. 1 is a diagram illustrating a host system, a memory storage device, and an input/output (I/O) device according to an exemplary embodiment of the invention. FIG. 2 is a diagram illustrating a host system, a memory storage device and an I/O device according to another example embodiment of the invention.

Referring to fig. 1 and 2, the host system 11 generally includes a processor 111, a Random Access Memory (RAM) 112, a Read Only Memory (ROM) 113, and a data transmission interface 114. The processor 111, the random access memory 112, the read only memory 113, and the data transmission interface 114 are all electrically connected to a system bus (system bus) 110.

In the present exemplary embodiment, the host system 11 is electrically connected to the memory storage device 10 through the data transmission interface 114. For example, host system 11 may store data to memory storage device 10 or read data from memory storage device 10 via data transfer interface 114. In addition, the host system 11 is electrically connected to the I/O device 12 via the system bus 110. For example, the host system 11 may transmit output signals to the I/O device 12 or receive input signals from the I/O device 12 via the system bus 110.

In the present exemplary embodiment, the processor 111, the random access memory 112, the read only memory 113 and the data transmission interface 114 can be disposed on the motherboard 20 of the host system 11. The number of data transfer interfaces 114 may be one or more. The motherboard 20 may be electrically connected to the memory storage device 10 through the data transmission interface 114 by wire or wirelessly. The memory storage device 10 may be, for example, a usb disk 201, a memory card 202, a Solid State Drive (SSD) 203, or a wireless memory storage device 204. The wireless memory storage device 204 can be a memory storage device based on various wireless Communication technologies, such as Near Field Communication (NFC) memory storage device, wireless facsimile (WiFi) memory storage device, bluetooth (Bluetooth) memory storage device, or Bluetooth low energy memory storage device (e.g., iBeacon). In addition, the motherboard 20 may also be electrically connected to various I/O devices such as a Global Positioning System (GPS) module 205, a network interface card 206, a wireless transmission device 207, a keyboard 208, a screen 209, a speaker 210, and the like through the System bus 110. For example, in an exemplary embodiment, the motherboard 20 may access the wireless memory storage device 204 via the wireless transmission device 207.

In an exemplary embodiment, the host system referred to is substantially any system that can cooperate with a memory storage device to store data. Although the host system is described as a computer system in the above exemplary embodiment, fig. 3 is a schematic diagram of a host system and a memory storage device according to another exemplary embodiment of the invention. Referring to fig. 3, in another exemplary embodiment, the host system 31 may also be a digital camera, a video camera, a communication device, an audio player, a video player, or a tablet computer, and the memory storage device 30 may be various non-volatile memory storage devices such as an SD card 32, a CF card 33, or an embedded storage device 34. The embedded memory device 34 includes embedded Multi-media cards (eMMC) 341 and/or embedded Multi-Chip Package memory devices (eMCP) 342, and various types of embedded memory devices electrically connecting the memory module to the substrate of the host system.

FIG. 4 is a schematic block diagram of a memory storage device according to an exemplary embodiment of the present invention.

Referring to fig. 4, the memory storage device 10 includes a connection interface unit 402, a memory control circuit unit 404 and a rewritable nonvolatile memory module 406.

In the exemplary embodiment, connection interface unit 402 is compatible with the Serial Advanced Technology Attachment (SATA) standard. However, it should be understood that the present invention is not limited thereto, and the connection interface unit 402 may also conform to the Parallel Advanced Technology Attachment (PATA) standard, the Institute of Electrical and Electronics Engineers (IEEE) 1394 standard, the High-Speed Peripheral Component connection interface (PCI Express) standard, the Universal Serial Bus (USB) standard, the Secure Digital (SD) interface standard, the Ultra High Speed (UHS-I) interface standard, the Ultra High Speed (Ultra High Speed) interface standard, UHS-II) interface standard, memory Stick (MS) interface standard, multi-Chip Package (Multi-Chip Package) interface standard, multimedia Memory Card (MMC) interface standard, embedded Multimedia Memory Card (eMMC) interface standard, universal Flash Memory Storage (UFS) interface standard, embedded Multi-Chip Package (cp) interface standard, compact Flash (CF) interface standard, integrated Device Electronics (IDE) standard, or other suitable standard. The connection interface unit 402 may be packaged with the memory control circuit unit 404 in a chip, or the connection interface unit 402 may be disposed outside a chip including the memory control circuit unit 404.

The memory control circuit unit 404 is used for executing a plurality of logic gates or control commands implemented in a hardware type or a firmware type, and performing operations such as writing, reading, erasing and merging of data in the rewritable nonvolatile memory module 406 according to commands of the host system 11.

The rewritable nonvolatile memory module 406 is electrically connected to the memory control circuit unit 404 and is used for storing data written by the host system 11. The rewritable nonvolatile memory module 406 has physical erase units 510 (0) to 510 (N). For example, the physical erase units 510 (0) -510 (N) may belong to the same memory die (die) or to different memory dies. Each physical erase cell has a plurality of physical program cells, for example, in the exemplary embodiment of the present invention, each physical erase cell includes 258 physical program cells, and the physical program cells belonging to the same physical erase cell can be independently written and simultaneously erased. However, it should be understood that the invention is not limited thereto, and each physical erase unit may be composed of 64 physical program units, 256 physical program units, or any other physical program units.

In more detail, the physical erase unit is the minimum unit of erase. That is, each physically erased cell contains one of the smallest number of memory cells that are erased. The physical programming unit is the minimum unit for programming. That is, the physical programming unit is the smallest unit for writing data. Each physical programming cell typically includes a data bit region and a redundancy bit region. The data bit area includes a plurality of physical access addresses for storing user data, and the redundancy bit area stores system data (e.g., control information and error correction codes). In the exemplary embodiment, each physical program unit includes 4 physical access addresses in the data bit area, and one physical access address has a size of 512 bytes (byte). However, in other exemplary embodiments, the data bit area may include a greater or lesser number of physical access addresses, and the size and number of the physical access addresses are not limited in the present invention.

In an exemplary embodiment of the invention, the rewritable nonvolatile memory module 406 is a multi-Level Cell (TLC) NAND flash memory module (i.e., a flash memory module capable of storing 3 bits of data in one memory Cell). However, the invention is not limited thereto, and the rewritable nonvolatile memory module 406 may also be a Multi-Level Cell (MLC) NAND type flash memory module (i.e., a flash memory module capable of storing 2 bits of data in one memory Cell), other flash memory modules, or other memory modules with the same characteristics.

FIGS. 5A and 5B are schematic diagrams illustrating an exemplary memory cell architecture and physical erase cells according to an embodiment of the present invention.

Referring to fig. 5A, the memory state of each memory cell of the rewritable nonvolatile memory module 406 can be identified as "111", "110", "101", "100", "011", "010", "001", or "000" (as shown in fig. 5A), wherein the 1 st bit from the left side is LSB, the 2 nd bit from the left side is CSB, and the 3 rd bit from the left side is MSB. In addition, the memory cells arranged on the same word line may constitute 3 physical program cells, wherein the physical program cell constituted by the LSB of the memory cells is referred to as a lower physical program cell, the physical program cell constituted by the CSB of the memory cells is referred to as a middle physical program cell, and the physical program cell constituted by the MSB of the memory cells is referred to as an upper physical program cell.

Referring to fig. 5B, a physical erase unit is composed of a plurality of physical program unit groups, wherein each physical program unit group includes a lower physical program unit, a middle physical program unit and an upper physical program unit composed of a plurality of memory cells arranged on the same word line. For example, in the physically erased cells, the 0 th physically programmed cell belonging to the lower physically programmed cell, the 1 st physically programmed cell belonging to the middle physically programmed cell, and the 2 nd physically programmed cell belonging to the upper physically programmed cell are considered as one physically programmed cell group. Similarly, the 3 rd, 4 th, and 5 th physical programming cells are considered as a physical programming cell group, and so on, other physical programming cells are divided into a plurality of physical programming cell groups according to the same manner.

FIG. 6 is a schematic block diagram of a memory control circuit unit according to an exemplary embodiment of the present invention.

Referring to FIG. 6, the memory control circuit unit 404 includes a memory management circuit 702, a host interface 704, a memory interface 706 and an error checking and correcting circuit 708.

The memory management circuit 702 is used to control the overall operation of the memory control circuit unit 404. Specifically, the memory management circuit 702 has a plurality of control commands, and the control commands are executed to write, read, and erase data during operation of the memory storage device 10. When the operation of the memory management circuit 702 or any circuit element included in the memory control circuit unit 404 is described below, the operation of the memory control circuit unit 404 is equivalently described.

In the exemplary embodiment, the control instructions of the memory management circuit 702 are implemented in firmware. For example, the memory management circuit 702 has a microprocessor unit (not shown) and a read only memory (not shown), and the control commands are burned into the read only memory. When the memory storage device 10 is in operation, the control instructions are executed by the microprocessor unit to perform operations such as writing, reading, and erasing data.

In another exemplary embodiment, the control instructions of the memory management circuit 702 may also be stored in a program code form in a specific area of the rewritable non-volatile memory module 406 (e.g., a system area dedicated to storing system data in the memory module). Further, the memory management circuit 702 has a microprocessor unit (not shown), a read only memory (not shown), and a random access memory (not shown). In particular, the ROM has a boot code (BOOT code), and when the memory control circuit 404 is enabled, the microprocessor unit first executes the boot code to load the control instructions stored in the rewritable nonvolatile memory module 406 into the RAM of the memory management circuit 702. Then, the microprocessor unit operates the control commands to perform operations such as data writing, reading and erasing.

In addition, in another exemplary embodiment, the control instructions of the memory management circuit 702 may also be implemented in a hardware type. For example, the memory management circuit 702 includes a microcontroller, a memory cell management circuit, a memory write circuit, a memory read circuit, a memory erase circuit, and a data processing circuit. The memory unit 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. The memory cell management circuit is used for managing the memory cells or groups thereof of the rewritable nonvolatile memory module 406. The memory write circuit is configured to issue a write command sequence to the rewritable nonvolatile memory module 406 to write data into the rewritable nonvolatile memory module 406. The memory reading circuit is used for issuing a reading instruction sequence to the rewritable nonvolatile memory module 406 to read data from the rewritable nonvolatile memory module 406. The memory erase circuit issues an erase command sequence to the rewritable nonvolatile memory module 406 to erase data from the rewritable nonvolatile memory module 406. The data processing circuit is used for processing data to be written into the rewritable nonvolatile memory module 406 and data read from the rewritable nonvolatile memory module 406. The write command sequence, the read command sequence, and the erase command sequence may respectively include one or more program codes or command codes and instruct the rewritable nonvolatile memory module 406 to perform corresponding operations of writing, reading, and erasing. In an example embodiment, the memory management circuit 702 may issue other types of command sequences to the rewritable nonvolatile memory module 406 to instruct the corresponding operations to be performed.

The host interface 704 is electrically connected to the memory management circuit 702 and is used for receiving and recognizing commands and data transmitted by the host system 11. That is, commands and data transmitted by the host system 11 are transmitted to the memory management circuit 702 through the host interface 704. In the exemplary embodiment, host interface 704 is compatible with the SATA standard. However, it should be understood that the present invention is not limited thereto, and the host interface 704 may be compatible with the PATA standard, the IEEE 1394 standard, the PCI Express standard, the USB standard, the SD standard, the UHS-I standard, the UHS-II standard, the MS standard, the MMC standard, the eMMC standard, the UFS standard, the CF standard, the IDE standard, or other suitable data transfer standard.

The memory interface 706 is electrically connected to the memory management circuit 702 and is used for accessing the rewritable nonvolatile memory module 406. That is, the data to be written into the rewritable nonvolatile memory module 406 is converted into a format accepted by the rewritable nonvolatile memory module 406 through the memory interface 706. Specifically, if the memory management circuit 702 wants to access the rewritable nonvolatile memory module 406, the memory interface 706 transmits a corresponding instruction sequence. For example, the instruction sequences may include a write instruction sequence for indicating write data, a read instruction sequence for indicating read data, an erase instruction sequence for indicating erase data, and corresponding instruction sequences for indicating various memory operations (e.g., changing read voltage levels or performing garbage collection procedures, etc.). These instruction sequences are generated by the memory management circuit 702 and transferred to the rewritable non-volatile memory module 406 through the memory interface 706, for example. The sequences of instructions may include one or more signals or data on a bus. These signals or data may include instruction code or program code. For example, the read command sequence includes read identification codes, memory addresses, and other information.

The error checking and correcting circuit 708 is electrically connected to the memory management circuit 702 and is used for performing an error checking and correcting process to ensure the correctness of data. Specifically, when the memory management circuit 702 receives a write command from the host system 11, the error checking and correcting circuit 708 generates an Error Correcting Code (ECC) and/or an Error Detecting Code (EDC) for data corresponding to the write command, and the memory management circuit 702 writes the data corresponding to the write command and the corresponding ECC and/or EDC into the rewritable nonvolatile memory module 406. Thereafter, when the memory management circuit 702 reads data from the rewritable nonvolatile memory module 406, the error correction code and/or the error check code corresponding to the data are simultaneously read, and the error checking and correcting circuit 708 performs an error checking and correcting process on the read data according to the error correction code and/or the error check code.

In an exemplary embodiment, the memory control circuit unit 404 further includes a buffer memory 710 and a power management circuit 712.

The buffer memory 710 is electrically connected to the memory management circuit 702 and is used for temporarily storing data and instructions from the host system 11 or data from the rewritable nonvolatile memory module 406. The power management circuit 712 is electrically connected to the memory management circuit 702 and is used for controlling the power of the memory storage device 10.

In the exemplary embodiment, the error checking and correcting circuit 708 can perform single-frame (single-frame) coding on data stored in the same physical program unit, or perform multi-frame (multi-frame) coding on data stored in a plurality of physical program units. The single-frame coding and the multi-frame coding may respectively use at least one of coding algorithms such as a low density parity check code (LDPC), a BCH code, a convolutional code (convolutional code), and a turbo code. Alternatively, in an example embodiment, the multi-frame coding may also employ Reed-solomon (RS) codes or exclusive or (XOR) algorithms. In addition, in another exemplary embodiment, more unlisted coding algorithms may be used, and are not described herein. Depending on the encoding algorithm employed, the ECC circuitry 708 may encode the data to be protected to generate corresponding ECC and/or ECC codes. For convenience of explanation, the error correction code and/or the error check code generated through encoding will be collectively referred to as encoded data hereinafter.

FIGS. 7 and 8 illustrate exemplary diagrams of managing physical erase cells according to one exemplary embodiment.

Referring to FIG. 7, the rewritable nonvolatile memory module 406 has physical erase units 510 (0) to 510 (N), and the memory management circuit 702 is logically divided (partitioned) into a data area 502, an idle area 504, a temporary area 506 and a replacement area 508.

The physical erase units logically belonging to the data area 502 and the idle area 504 are used for storing data from the host system 11. Specifically, the physical erase units in the data area 502 are regarded as physical erase units with stored data, and the physical erase units in the idle area 504 are used to replace the physical erase units in the data area 502. That is, when receiving a write command and data to be written from the host system 11, the memory management circuit 702 extracts physical erase units from the idle region 504 and writes the data into the extracted physical erase units to replace the physical erase units in the data region 502.

The physical erase unit logically belonging to the temporary storage area 506 is used for recording system data. For example, the system data includes a logical-to-physical mapping table, a manufacturer and a model of the rewritable non-volatile memory module, a physical erase unit count of the rewritable non-volatile memory module, a physical program unit count of each physical erase unit, and the like.

The physically erased cells logically belonging to the replacement area 508 are used in the bad physically erased cell replacement procedure to replace the damaged physically erased cells. Specifically, if there are normal physical erased cells in the replacement area 508 and the physical erased cells in the data area 502 are damaged, the memory management circuit 702 extracts the normal physical erased cells from the replacement area 508 to replace the damaged physical erased cells.

In particular, the number of physically erased cells in the data area 502, the idle area 504, the temporary area 506 and the replacement area 508 may vary according to different memory specifications. In addition, it should be understood that the grouping relationship of the physical erase units associated with the data area 502, the idle area 504, the temporary area 506 and the replacement area 508 may dynamically change during the operation of the memory storage device 10. For example, when the physical erased cells in the idle area 504 are damaged and replaced by the physical erased cells in the replacement area 508, the physical erased cells in the replacement area 508 are associated with the idle area 504.

Referring to FIG. 8, the memory management circuit 702 allocates logical units LBA (0) -LBA (H) to map the physical erase units of the data area 502, wherein each logical unit has a plurality of logical sub-units to map the physical program unit of the corresponding physical erase unit. Moreover, when the host system 11 wants to write data to the logical units or update the data stored in the logical units, the memory management circuit 702 extracts a physical erase unit from the idle area 504 to write data, so as to replace the physical erase unit in the data area 502. In the present exemplary embodiment, the logical subunit may be a logical page or a logical sector.

In order to identify the physical erase unit in which the data of each logical unit is stored, in the exemplary embodiment, the memory management circuit 702 records the mapping between the logical units and the physical erase units. Moreover, when the host system 11 intends to access data in the logical subunit, the memory management circuit 702 identifies the logical unit to which the logical subunit belongs, and accesses data in the physical erase unit mapped by the logical unit. For example, in the exemplary embodiment, the memory management circuit 702 stores a logical-to-physical mapping table in the rewritable non-volatile memory module 406 to record the physical erase unit mapped by each logical unit, and the memory management circuit 702 loads the logical-to-physical mapping table into the buffer memory 710 for maintenance when data is to be accessed.

It should be noted that, since the buffer 710 has a limited capacity and cannot store a mapping table for recording mapping relationships of all the logical units, in the exemplary embodiment, the memory management circuit 702 groups the logical units LBA (0) to LBA (H) into a plurality of logical zones LZ (0) to LZ (M), and configures a logical-physical mapping table for each logical zone. In particular, when the memory management circuit 702 wants to update the mapping of a logical unit, the logical-physical mapping table corresponding to the logical area to which the logical unit belongs is loaded into the buffer memory 710 for updating. In the present exemplary embodiment, the space required to store all the logical-to-physical mapping tables is one in one out of one in one out of the space available for storing data in the rewritable non-volatile memory module 406. That is, assuming that the capacity of the rewritable nonvolatile memory module 406 is 1TB (Terabyte), the space required to store all the logical-physical mapping tables is 1GB (Gigabyte). However, in other example embodiments, the space required to store all logical-to-physical mapping tables may vary depending on the capacity of the rewritable non-volatile memory module 406.

In the present exemplary embodiment, when the host system 11 is going to perform a write operation, the memory management circuit 702 extracts an active physical erase unit from the idle region 504 and writes data (also referred to as update data) included in a write command from the host system 11 into the active physical erase unit.

Specifically, when the memory storage device 10 receives a write command from the host system 11, data in the write command from the host system 11 can be written into an active physical erase unit in the idle region 504. When the physical erase unit is full, the memory management circuit 702 will extract an empty physical erase unit from the idle area 504 as another active physical erase unit to continue writing the updated data corresponding to the write command from the host system 11.

FIGS. 9A-9C are simplified examples of data writing according to one embodiment of the present invention.

For convenience of illustration, it is assumed that the data area 502 has 4 physically erased cells, which are physically erased cells 410 (0) -410 (3), respectively, and the idle area 504 has 2 physically erased cells, which are physically erased cells 410 (4) -410 (5), respectively.

Referring to fig. 9A, fig. 9B and fig. 9C, it is assumed that in the state of the memory storage device 10 of fig. 9A, the logical pages of the logical units LBA (0) to LBA (3) map the physical program units of the physical erase units 410 (0) to 410 (3) of the data area 502, and the idle area 504 has the physical erase units 410 (4) to 410 (5). That is, the memory management circuit 702 records the mapping relationship between the logical units LBA (0) to LBA (3) and the physical erase units 410 (0) to 410 (5) in the logical-physical mapping table, and regards the physical program unit of the physical erase units 410 (0) to 410 (3) as having stored the data (i.e., the initial data ID1 to ID 12) belonging to the logical pages of the logical units LBA (0) to LBA (3). In addition, the memory management circuit 702 records the available physical erase units 410 (4) -410 (5) in the idle area 504, and when the host system 11 performs a write operation, the memory management circuit 702 records the mapping information of the update data corresponding to the write operation to the physical-to-logical mapping table 600 shown in FIG. 9B in the buffer memory 710.

Specifically, when the host system 11 performs a write operation with respect to a logical page, the memory management circuit 702 writes the update data corresponding to the write operation into the active physical erase unit selected from the idle region 504. Meanwhile, the memory management circuit 702 does not change the mapping relationship between the logical units LBA (0) to LBA (3) and the physical erase units 410 (0) to 410 (5) in the logical-to-physical mapping table, and the memory management circuit 702 records the address (also referred to as a physical address) of the physical program unit used for storing the update data in the physical erase unit and the address (also referred to as a logical address) of the logical page corresponding to the write operation into the physical-to-logical mapping table 600 in fig. 9B. After the physical-logical mapping table 600 is fully written, the corresponding logical-physical mapping table is loaded into the buffer memory 710 according to the mapping information (i.e., the logical address corresponding to the updated data) in the physical-logical mapping table 600, so as to update the mapping relationship between the logical units LBA (0) to LBA (3) and the physical erasing units 410 (0) to 410 (5). It should be noted that when the memory storage device 10 is in an idle state for a period of time (for example, 30 seconds without receiving any command from the host system 11), the memory management circuit 702 may also load the corresponding logical-to-physical mapping table into the buffer memory 710 according to the mapping information in the physical-to-logical mapping table 600, so as to update the mapping relationship between the logical units LBA (0) to LBA (3) and the physical erase units 410 (0) to 410 (5).

In addition, in the present exemplary embodiment, the memory management circuit 702 creates the updated data count table 700 as shown in FIG. 9C. It should be noted that, after a write operation is performed to write data of a logical page into the physical erase unit, the logical unit to which the logical page belongs may be referred to as an "updated logical unit". In other words, the logical unit to which the logical address recorded in the physical-to-logical mapping table 600 belongs is the aforementioned "updated logical unit". The update data count table 700 is used to record the number of valid update data (also called update data count) currently available in the active physical erase unit for each updated logical unit corresponding to the write operation. In other words, the update data count of an updated logical unit can be used to represent how many pieces of mapping information in the updated logical unit need to be updated. In the present exemplary embodiment, the logic unit having the non-zero update data count in the update data count table 700 may also be regarded as the aforementioned "updated logic unit". It should be noted that if there are multiple write operations to repeatedly write to the same logical address, the updated data of the logical address valid in the active physical erase unit is the updated data written by the last write operation.

Referring to fig. 9A, 9B and 9C, if the host system 11 is to write the update data UD1 and the update data UD1 belongs to the 1 st logical page of the logical unit LBA (0), the memory management circuit 702 extracts, for example, the physical erase unit 410 (4) from the idle area 504 as an active physical erase unit, and issues a write command to write the update data UD1 to the 0 th physical program unit of the physical erase unit 410 (4). Next, as shown in FIG. 9B, the memory management circuit 702 records the mapping information of the 0 th physical programming unit (i.e. information "410 (4) -0") of the physical erase unit 410 (4) and the 1 st logical page (i.e. information "LBA (0) -1") of the logical unit LBA (0) in the physical-to-logical mapping table 600. In addition, as shown in fig. 9C, the memory management circuit 702 modifies the update data count corresponding to the logical unit LBA (0) in the update data count table 700 to 1 to represent that a piece of mapping information in the logical unit LBA (0) needs to be updated in response to the write operation.

Then, assuming that the host system 11 wants to write the update data UD2 again and the update data UD2 belongs to the 1 st logical page of the logical unit LBA (2), the memory management circuit 702 writes the update data UD2 to the 1 st physical programming unit of the physical erase unit 410 (4). Next, as shown in FIG. 9B, the memory management circuit 702 records the mapping information of the 1 st physical programming unit (i.e., information "410 (4) -1") of the physical erase unit 410 (4) and the 1 st logical page (i.e., information "LBA (2) -1") of the logical unit LBA (2) in the physical-to-logical mapping table 600. In addition, the memory management circuit 702 modifies the update data count corresponding to the logical unit LBA (2) in the update data count table 700 to 1 to indicate that a piece of mapping information in the logical unit LBA (2) needs to be updated in response to the write operation.

Then, assuming that the host system 11 wants to write the update data UD3 again and the update data UD3 belongs to the 2 nd logical page of the logical unit LBA (2), the memory management circuit 702 writes the update data UD3 to the 2 nd physical program unit of the physical erase unit 410 (4). Next, as shown in FIG. 9B, the memory management circuit 702 records the mapping information of the 2 nd physical programming unit (i.e. information "410 (4) -2") of the physical erase unit 410 (4) and the 2 nd logical page (i.e. information "LBA (2) -2") of the logical unit LBA (2) in the physical-to-logical mapping table 600. In addition, the memory management circuit 702 modifies the update data count corresponding to the logical unit LBA (2) in the update data count table 700 to 2 to represent that two pieces of mapping information in the logical unit LBA (2) need to be updated, as shown in fig. 9C, in response to the write operation.

Then, assuming that the host system 11 wants to write the update data UD4 again and the update data UD4 belongs to the 1 st logical page of the logical unit LBA (3), the memory management circuit 702 extracts the physical erase unit 410 (5) from the idle area 504. The memory management circuit 702 writes the updated data UD4 into the 0 th physical programming unit of the physical erase unit 410 (5). Next, as shown in FIG. 9B, the memory management circuit 702 records the mapping information of the 0 th physical programming unit (i.e., information "410 (5) -0") of the physical erase unit 410 (5) and the 1 st logical page (i.e., information "LBA (3) -1") of the logical unit LBA (3) in the physical-to-logical mapping table 600. In addition, the memory management circuit 702 modifies the update data count corresponding to the logical unit LBA (3) in the update data count table 700 to 1 to indicate that a piece of mapping information in the logical unit LBA (3) needs to be updated in response to the write operation.

Then, assuming that the host system 11 wants to write the update data UD5 again and the update data UD5 belongs to the 2 nd logical page of the logical unit LBA (3), the memory management circuit 702 writes the update data UD5 to the 1 st physical program unit of the physical erase unit 410 (5). Next, as shown in FIG. 9B, the memory management circuit 702 records the mapping information of the 1 st physical programming unit (i.e., information "410 (5) -1") of the physical erase unit 410 (5) and the 2 nd logical page (i.e., information "LBA (3) -2") of the logical unit LBA (3) in the physical-to-logical mapping table 600. In addition, the memory management circuit 702 modifies the update data count corresponding to the logical unit LBA (3) in the update data count table 700 to 2 to represent that two pieces of mapping information in the logical unit LBA (3) need to be updated, as shown in fig. 9C, in response to the write operation.

Then, assuming that the host system 11 is about to write the update data UD6 again and the update data UD6 belongs to the 1 st logical page of the logical unit LBA (1), the memory management circuit 702 writes the update data UD6 to the 2 nd physical program unit of the physical erase unit 410 (5). Next, as shown in FIG. 9B, the memory management circuit 702 records the mapping information of the 2 nd physically programmed unit (i.e. information "410 (5) -2") of the physically erased unit 410 (5) and the 1 st logical page (i.e. information "LBA (1) -1") of the logical unit LBA (1) in the physical-to-logical mapping table 600. In response to the write operation, the memory management circuit 702 modifies the update data count corresponding to the logical unit LBA (1) in the update data count table 700 to 1 to represent that two pieces of mapping information in the logical unit LBA (1) need to be updated, as shown in fig. 9C.

After the foregoing write operation, as shown in the update data count table 700 of fig. 9C, the update data count of the logical unit LBA (0) is 1. The update data count of the logical unit LBA (1) is 1, the update data count of the logical unit LBA (2) is 2, and the update data count of the logical unit LBA (3) is 2. In other words, after the above-mentioned write operation, the mapping information of one logical address in the logical unit LBA (0) needs to be updated, the mapping information of one logical address in the logical unit LBA (1) needs to be updated, the mapping information of two logical addresses in the logical unit LBA (2) needs to be updated, and the mapping information of two logical addresses in the logical unit LBA (3) needs to be updated.

It should be understood that, since the physical-to-logical mapping table 600 is fully written, the memory management circuit 702 loads the corresponding logical-to-physical mapping table into the buffer memory 710 according to the logical address corresponding to the information written in the physical-to-logical mapping table 600, so as to update the mapping relationship between the logical units LBA (0) to LBA (3) and the physical erasing units 410 (0) to 410 (5).

The mapping table updating method of the present invention is described below in several embodiments.

[ first embodiment ]

FIGS. 10A-10C are simplified examples of mapping table updates according to the first embodiment of the present invention.

Referring to fig. 10A, fig. 10B and fig. 10C, continuing with fig. 9A, fig. 9B and fig. 9C, the memory management circuit 702 first selects the logical-physical mapping table to be loaded and update the mapping information according to the updated data count table 700 of fig. 9C. In the first embodiment of the present invention, the memory management circuit 702 may set one threshold value (also referred to as a first threshold value) in advance, for example. When the updated data count corresponding to a logical unit is greater than the first threshold, the memory management circuit 702 loads the logical-to-physical mapping table of the logical unit into the buffer memory 710 and updates the logical-to-physical mapping table of the logical unit according to the information in the physical-to-logical mapping table 600. It should be noted that the present invention is not limited to the exact value of the first threshold.

In more detail, in the embodiment of fig. 10A, 10B and 10C, it is assumed that the first threshold is 1. The memory management circuit 702 selects the logic unit LBA (2) and the logic unit LBA (3) whose update data count is greater than the first threshold value. The memory management circuit 702 loads the logical-to-physical mapping table (i.e., the first logical-to-physical mapping table) corresponding to the logical unit LBA (2) and the logical unit LBA (3) (collectively referred to as the first updated logical unit) from the rewritable nonvolatile memory module 406 according to the physical-to-logical mapping table 600. Specifically, since the physical-to-logical mapping table 600 in fig. 9B stores the update information (i.e., the information "LBA (2) -1" and "LBA (2) -2") about the 1 st logical page of the logical unit LBA (2) and the update information (i.e., the information "LBA (3) -1" and "LBA (3) -2") about the 1 st logical page of the logical unit LBA (3), the memory management circuit 702 loads the logical-to-physical mapping table of the logical unit LBA (2) and the logical-to-physical mapping table of the logical unit LBA (3) into the buffer memory 710 from the rewritable nonvolatile memory module 406 correspondingly. In this example, the number of first updated logical units (i.e., 2) is less than the number of logical units (also referred to as updated logical units) in the update data count table 700 for which the update data count is not zero (i.e., 4).

Next, the memory management circuit 702 updates the logical unit LBA (2) and the mapping relationship between the logical unit LBA (3) and the physical erase units 410 (0) -410 (5) according to the information stored in the physical-to-logical mapping table 600 in FIG. 9B. Specifically, since the physical-to-logical mapping table 600 stores the update information UD2 regarding the 1 st logical page of the logical unit LBA (2) (i.e., the information "LBA (2) -1") stored to the 1 st physical programming unit (i.e., the information "410 (4) -1") of the physical erase unit 410 (4), the update information UD3 regarding the 2 nd logical page of the logical unit LBA (2) (i.e., the information "LBA (2) -2") stored to the 2 nd physical programming unit (i.e., the information "410 (4) -2") of the physical erase unit 410 (4), the update information regarding the 1 st logical page of the logical unit LBA (3) (i.e., the update data UD4 of the information "LBA (3) -1") is stored to the update information of the 0 th physical program unit (i.e., the information "410 (5) -0") of the physical erase unit 410 (5) and the update data UD5 of the 2 nd logical page (i.e., the information "LBA (3) -2") of the logical unit LBA (3) is stored to the update information of the 1 st physical program unit (i.e., the information "410 (5) -1") of the physical erase unit 410 (5), the memory management circuit 702 will respectively update the logical-to-physical mapping table of the logical unit LBA (2) and the logical-to-physical mapping table of the logical unit LBA (3), to map the 1 st logical page of the logical unit LBA (2) to the 1 st physically programmed unit of the physically erased unit 410 (4), the 2 nd logical page of the logical unit LBA (2) to the 2 nd physically programmed unit of the physically erased unit 410 (4), the 1 st logical page of the logical unit LBA (3) to the 0 th physically programmed unit of the physically erased unit 410 (5), and the 2 nd logical page of the logical unit LBA (3) to the 1 st physically programmed unit of the physically erased unit 410 (5), as shown in FIG. 10A.

After the mapping information is updated, the initial data ID8-ID9 in the 1 st-2 nd physical program unit of the physical erase unit 410 (2) to which the 1 st-2 nd logical page of the logical unit LBA (2) is mapped is identified as invalid data, and the initial data ID11-ID12 in the 1 st-2 nd physical program unit of the physical erase unit 410 (3) to which the 1 st-2 nd logical page of the logical unit LBA (3) is mapped is identified as invalid data.

Then, the memory management circuit 702 restores the updated logical-to-physical mapping table of the logical unit LBA (2) and the logical unit LBA (3) to the rewritable nonvolatile memory module 406. It should be noted that the example embodiments are not intended to limit the time for restoring the first logical-to-physical mapping table to the rewritable nonvolatile memory module 406.

In addition, the memory management circuit 702 modifies the physical-to-logical mapping table 600 in FIG. 9B to the physical-to-logical mapping table 600 in FIG. 10B. In more detail, the memory management circuit 702 also clears the update information UD2 regarding the 1 st logical page (i.e., information "LBA (2) -1") of the logical unit LBA (2) stored to the 1 st physical programming unit (i.e., information "410 (4) -1") of the physical erasure unit 410 (4), the update information regarding the 2 nd logical page (i.e., information "LBA (2) -2") of the logical unit LBA (2) stored to the 2 nd physical programming unit (i.e., information "410 (4) -2") of the physical erasure unit 410 (4), the update information regarding the 1 st logical page (i.e., information "LBA (3) -1") of the logical unit LBA (3) stored to the 0 th physical programming unit (i.e., information "410 (5) -0") of the physical erasure unit 410 (5), and the update information regarding the 2 nd logical page (i.e., information "LBA (3) -1") of the logical unit LBA (3) stored to the 0 th physical programming unit (i.e., information "LBA (5) -5") stored to the physical erasure unit LBA (410 (5) stored in the physical erasure map 600. In particular, in the present embodiment, the memory management circuit 702 also retains the update information of the physical-to-logical mapping table 600 that the update data UD1 regarding the 1 st logical page (i.e., information "LBA (0) -1") of the logical unit LBA (0) is stored to the 0 th physical programming unit (i.e., information "410 (4) -0") of the physical erase unit 410 (4) and the update data UD6 regarding the 1 st logical page (i.e., information "LBA (1) -1") of the logical unit LBA (1) is stored to the 2 nd physical programming unit (i.e., information "410 (5) -2") of the physical erase unit 410 (5).

In addition, memory management circuit 702 modifies update data count table 700 in fig. 9C to update data count table 700 as in fig. 10C. More specifically, since the logical unit LBA (2) and logical unit LBA (3) have no mapping information to be updated, the update data counts of logical unit LBA (2) and logical unit LBA (3) are set to zero.

It should be noted that, in the foregoing example, the memory management circuit 702 selects the logical unit LBA (2) and the logical unit LBA (3) having the updated data count greater than the first threshold value and loads the logical-physical mapping table corresponding to the logical unit LBA (2) and the logical unit LBA (3) to update the mapping information. In other words, according to the first threshold, the update quantity of the mapping information in the loaded logical-physical mapping table can be ensured to reach a certain value, thereby improving the efficiency of the logical-physical mapping table during updating. For the logical unit LBA (0) and the logical unit LBA (1) whose update data count is not greater than the first threshold, the memory management circuit 702 may continue to perform the subsequent write operation and wait until the update data count of the logical unit LBA (0) and the logical unit LBA (1) is greater than the first threshold, and then load the logical-physical mapping table corresponding to the logical unit LBA (0) and the logical unit LBA (1) to update the mapping information. Therefore, the problem that when the updating quantity of the mapping information in a logical-physical mapping table is less, most of the time is spent in loading and restoring the logical-physical mapping table in the warehouse cleaning operation, and the updating efficiency of the mapping table is low can be avoided.

[ second embodiment ]

FIGS. 11A-11C are simplified examples of mapping table updates according to a second embodiment of the present invention.

Referring to fig. 11A, fig. 11B and fig. 11C, continuing with fig. 9A, fig. 9B and fig. 9C, the memory management circuit 702 first selects the logical-physical mapping table to be loaded and updates the mapping information according to the updated data count table 700 of fig. 9C. In the second embodiment of the present invention, the memory management circuit 702 can set a threshold value (also referred to as a second threshold value) in advance, for example. When the updated data count corresponding to a logical unit is smaller than the second threshold, the memory management circuit 702 loads the logical-to-physical mapping table of the logical unit into the buffer memory 710 and updates the logical-to-physical mapping table of the logical unit according to the information in the physical-to-logical mapping table 600. It is noted that the invention is not intended to be limited to the exact value of the second threshold.

In more detail, in the embodiment of fig. 11A, 11B and 11C, it is assumed that the second threshold is 2. The memory management circuit 702 selects the logic unit LBA (0) and the logic unit LBA (1) whose updated data count is less than the second threshold value. The memory management circuit 702 loads the logical-to-physical mapping table (i.e., the first logical-to-physical mapping table) corresponding to the logical unit LBA (0) and the logical unit LBA (1) (which is referred to as the first updated logical unit) from the rewritable nonvolatile memory module 406 according to the physical-to-logical mapping table 600. Specifically, since the physical-to-logical mapping table 600 in fig. 9B stores the update information (i.e., the information "LBA (0) -1") of the 1 st logical page of the logical unit LBA (0) and the update information (i.e., the information "LBA (1) -1") of the 1 st logical page of the logical unit LBA (1), the memory management circuit 702 loads the logical-to-physical mapping table of the logical unit LBA (0) and the logical-to-physical mapping table of the logical unit LBA (1) into the buffer memory 710 from the rewritable nonvolatile memory module 406 correspondingly. In this example, the number of first updated logical units (i.e., 2) is less than the number of logical units (also referred to as updated logical units) in the updated data count table 700 for which the updated data count is not zero (i.e., 4).

Next, the memory management circuit 702 updates the logical unit LBA (0) and the mapping relationship between the logical unit LBA (1) and the physical erase units 410 (0) -410 (5) according to the information stored in the physical-to-logical mapping table 600 in FIG. 9B. Specifically, since the physical-to-logical mapping table 600 stores the update information of the 1 st logical page of the logical unit LBA (0) (i.e., the information "LBA (0) -1") (UD 1) stored in the 0 th physical programming unit of the physical erase unit 410 (4) (i.e., the information "410 (4) -0") and the update information of the 1 st logical page of the logical unit LBA (1) (i.e., the information "LBA (1) -1") (UD 6) stored in the physical erase unit 410 (5) (i.e., the information "410 (5) -2"), the memory management circuit 702 respectively updates the logical-to-physical mapping table of the logical unit LBA (0) and the logical-to-physical mapping table of the logical unit LBA (1) to map the 1 st logical page of the logical unit LBA (0) to the 0 th physical programming unit of the physical erase unit 410 (4) and maps the 1 st logical page of the logical unit LBA (1) to the 2 nd physical programming unit LBA (5) of the physical erase unit 410 (a), as shown in fig. 11.

After the mapping information is updated, the initial data ID2 in the 1 st physical program cell of the physical erase cell 410 (0) originally mapped to the 1 st logical page of the logical cell LBA (0) is identified as invalid data, and the initial data ID5 in the 1 st physical program cell of the physical erase cell 410 (1) originally mapped to the 1 st logical page of the logical cell LBA (1) is identified as invalid data.

Then, the memory management circuit 702 will restore the updated logical-to-physical mapping table of the logical unit LBA (0) and the logical unit LBA (1) to the rewritable nonvolatile memory module 406. It should be noted that the example embodiments are not intended to limit the time for restoring the first logical-to-physical mapping table to the rewritable nonvolatile memory module 406.

In addition, the memory management circuit 702 modifies the physical-to-logical mapping table 600 in FIG. 9B to the physical-to-logical mapping table 600 in FIG. 11B. In more detail, the memory management circuit 702 also clears the update information in the physical-to-logical mapping table 600 that the update data UD1 regarding the 1 st logical page of the logical unit LBA (0) (i.e., the information "LBA (0) -1") is stored to the 0 th physical programming unit of the physical erase unit 410 (4) (i.e., the information "410 (4) -0") and the update data UD6 regarding the 1 st logical page of the logical unit LBA (1) (i.e., the information "LBA (1) -1") is stored to the 2 nd physical programming unit of the physical erase unit 410 (5) (i.e., the information "410 (5) -2"). In particular, in the present embodiment, the memory management circuit 702 also retains the update information of the 1 st logical page of the logical unit LBA (2) (i.e., the information "LBA (2) -1") in the physical-logical mapping table 600, the update information of the 1 st physical programming unit (i.e., the information "410 (4) -1") stored to the physical erasing unit 410 (4), the update information of the 2 nd logical page of the logical unit LBA (2) (i.e., the information "LBA (2) -2") stored to the 2 nd physical programming unit (i.e., the information "410 (4) -2") stored to the physical erasing unit 410 (4), the update information of the 1 st logical page of the logical unit LBA (3) (i.e., the information "LBA (3) -1") stored to the 0 th physical programming unit (i.e., the information "410 (5) -0") stored to the physical erasing unit 410 (5), and the update information of the 2 nd logical page of the logical unit LBA (3), the information "LBA (3) -1") stored to the physical erasing unit 410 (5).

In addition, memory management circuit 702 modifies update data count table 700 in fig. 9C to update data count table 700 as in fig. 11C. More specifically, since the logical unit LBA (0) and logical unit LBA (1) have no mapping information to be updated, the update data counts of the logical unit LBA (0) and logical unit LBA (1) are set to zero.

It should be noted that, in the foregoing example, the memory management circuit 702 selects the logical unit LBA (0) and the logical unit LBA (1) having the updated data count smaller than the second threshold value and loads the logical-physical mapping table corresponding to the logical unit LBA (0) and the logical unit LBA (1) to update the mapping information. In other words, if the update data count of a logic unit is not less than the second threshold value, it means that a higher probability exists in a subsequent write operation that data of the logic unit whose update data count is not less than the second threshold value is continuously written. After the logical-physical mapping table of the logical unit with the updated data count smaller than the second threshold is loaded to update the mapping information, the mapping information of the logical unit with the updated data count smaller than the second threshold in the physical-logical mapping table may be cleared, so that more space is reserved for storing the mapping information of the logical unit with the updated data count not smaller than the second threshold.

In addition, it should be noted that, in the first embodiment, the write operation to be performed by the host system is to write data to one or more random logical units; in the second embodiment, the write operation to be performed by the host system writes data to one or more logical units with logical addresses within a fixed range.

[ third embodiment ]

In the third embodiment of the present invention, the memory management circuit 702 may set one threshold value (also referred to as a third threshold value) in advance, for example. More specifically, the memory management circuit 702 sorts the plurality of update data counts in the update data count table, and determines the third threshold value from the sorted update data counts such that the number of update data counts (also referred to as second update data counts) that are greater than the third threshold value among the plurality of update data counts is equal to the number of update data counts (also referred to as third update data counts) that are not greater than the third threshold value among the plurality of update data counts. In other words, the third threshold value may be used to divide the logic cells recorded in the update data count table into two types of the same number, one type of the logic cells whose update data count is greater than the third threshold value, and the other type of the logic cells whose update data count is not greater than the third threshold value.

More specifically, in continuation of the examples of fig. 9A, 9B, and 9C, the memory management circuit 702 sorts the plurality of update data counts in the update data count table 700 in fig. 9C, and determines the third threshold value (for example, 1) such that the number of update data counts larger than the third threshold value in the update data count table 700 (that is, 2) is equal to the number of update data counts not larger than the third threshold value in the update data count table 700 (that is, 2) from the sorted update data counts. With the third threshold value, the memory management circuit 702 can divide the logical units LBA (0) to LBA (3) in fig. 9C into two types having the same number, one type being a logical unit LBA (2) and LBA (3) whose update data count is greater than the third threshold value, and the other type being a logical unit LBA (0) and LBA (1) whose update data count is not greater than the third threshold value.

Thereafter, the memory management circuit 702 may identify the logical unit LBA (2) and the logical unit LBA (3) (collectively, the second updated logical unit) as the first updated logical unit as described in the first embodiment, and perform the mapping table updating method as in the first embodiment. However, in another embodiment, the memory management circuit 702 can identify the logic unit LBA (0) and the logic unit LBA (1) (collectively, the third updated logic unit) as the first updated logic unit as described in the second embodiment, and perform the mapping table updating method as in the second embodiment. The manner of updating the mapping table has been described in detail in the foregoing first embodiment and second embodiment, and thus is not described herein again.

In the above example, the memory management circuit 702 divides the logic cells recorded in the update data count table into two types of logic cells with the same number according to the third threshold value, wherein one type of logic cell is a logic cell with an update data count larger than the third threshold value, and the other type of logic cell is a logic cell with an update data count not larger than the third threshold value. Thereafter, memory management circuitry 702 may select a logical unit in one of the classes and load the logical-to-physical mapping table for the logical unit of the class for updating. In other words, when the updated data counts of the logical units in the updated data count table 700 are all relatively close or even, the mapping table updating method of the third embodiment can be directly performed to clear half of the mapping information recorded in the physical-logical mapping table and to make half of the space in the physical-logical mapping table.

Note that, in the foregoing example, the third threshold value may be used to divide the logic cells recorded in the update data count table into two types having the same number, one type being a logic cell whose update data count is greater than the third threshold value, and the other type being a logic cell whose update data count is not greater than the third threshold value, but the present invention is not limited thereto. For example, in another embodiment, the memory management circuit 702 may divide the logic cells recorded in the update data count table into two types of different numbers according to the third threshold value, one type of the logic cells having an update data count greater than the third threshold value, and the other type of the logic cells having an update data count not greater than the third threshold value. The proportional relationship between the total number of logic units greater than the third threshold value and the total number of logic units whose update data count is not greater than the third threshold value may be approximately or equal to a predetermined ratio. In other words, the memory management circuit 702 can select one of the classes of the plurality of logical units to directly execute the mapping table updating method of the third embodiment to clear the plurality of logical units recorded in the physical-to-logical mapping table corresponding to the selected one of the classes and to make room for a part of the physical-to-logical mapping table.

Fig. 12 is a flowchart illustrating a mapping table updating method according to an embodiment of the present invention.

Referring to fig. 12, in step S1201, the memory management circuit 702 builds the physical-to-logical mapping table 600. The physical-to-logic mapping table 600 records mapping information between an active physical erase unit of the plurality of physical erase units and a plurality of updated logical units of the plurality of logical units. In step S1203, the memory management circuit 702 calculates a plurality of updated data counts of the plurality of updated logical units in the active physical erase unit according to the physical-to-logical mapping table 600. In step S1205, the memory management circuit 702 selects a first updated logical unit from the plurality of updated logical units according to the aforementioned update data count. Wherein the number of the first updated logic units is less than the number of the plurality of updated logic units. Next, in step S1207, the memory management circuit 702 loads a first logical-to-physical mapping table corresponding to the first updated logical unit from the plurality of logical-to-physical mapping tables. In step S1209, the memory management circuit 702 updates the mapping information in the first logical-to-physical mapping table according to the mapping information of the first updated logical unit in the physical-to-logical mapping table 600. Finally, in step S1211, the memory management circuit 702 restores the updated first logical-to-physical mapping table back to the rewritable nonvolatile memory module.

Referring to fig. 13, in step S1301, the memory management circuit 702 establishes a physical-to-logical mapping table 600. The physical-to-logic mapping table 600 records mapping information between an active physical erase unit of the plurality of physical erase units and a plurality of updated logical units of the plurality of logical units. In step S1303, the memory management circuit 702 calculates a plurality of updated data counts of the plurality of updated logical units in the active physical erase unit according to the physical-to-logical mapping table 600. In step S1305, the memory management circuit 702 selects a first updated logical unit from the plurality of updated logical units according to the aforementioned update data count. Wherein the number of the first updated logic cells is less than the number of the plurality of updated logic cells and the first updated data count of the first updated logic cell in the plurality of updated data counts is greater than a first threshold. Next, in step S1307, the memory management circuit 702 loads the first logical-to-physical mapping table corresponding to the first updated logical unit from among the plurality of logical-to-physical mapping tables. In step S1309, the memory management circuit 702 updates the mapping information in the first logical-to-physical mapping table according to the mapping information of the first updated logical unit in the physical-to-logical mapping table 600. In step S1311, the memory management circuit 702 clears the mapping information of the first updated logical unit in the physical-to-logical mapping table 600. In step S1313, the memory management circuit 702 retains mapping information of updated logical units other than the first updated logical unit in the physical-to-logical mapping table 600. Finally, in step S1315, the memory management circuit 702 restores the updated first logical-to-physical mapping table to the rewritable nonvolatile memory module.

In summary, the mapping table updating method, the memory control circuit unit and the memory storage device of the present invention can load the corresponding logical-to-physical mapping table according to only a part of the mapping information in the physical-to-logical mapping table to update the mapping information, and retain the other remaining part of the mapping information in the physical-to-logical mapping table. Therefore, the efficiency of the logical-physical mapping table during updating can be improved.

Although the present invention has been described with reference to the above embodiments, it should be understood that various changes and modifications can be made therein by those skilled in the art without departing from the spirit and scope of the invention.

Claims

1. A mapping table updating method for a rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module has a plurality of physical erasing units, and a plurality of logical-to-physical mapping tables are stored in the rewritable nonvolatile memory module to record mapping information between the plurality of logical units and the plurality of physical erasing units, the mapping table updating method comprising:

establishing a physical-logical mapping table, wherein the physical-logical mapping table records mapping information between at least one active physical erasure unit in the plurality of physical erasure units and a plurality of updated logical units in the plurality of logical units;

respectively calculating a plurality of updated data counts of the plurality of updated logic units in the active physical erase unit according to the physical-logic mapping table;

selecting a first updated logical unit from the plurality of updated logical units according to the plurality of update data counts, wherein the number of the first updated logical unit is less than the number of the plurality of updated logical units;

loading a first logical-to-physical mapping table corresponding to the first updated logical unit from the plurality of logical-to-physical mapping tables; and

updating mapping information in the first logical-to-physical mapping table according to mapping information of the first updated logical unit in the physical-to-logical mapping table.

2. The mapping table updating method according to claim 1, further comprising:

clearing mapping information of the first updated logical unit in the physical-logical mapping table;

reserving mapping information of other updated logical units except the first updated logical unit in the physical-logical mapping table; and

and storing the updated first logic-physical mapping table back to the rewritable nonvolatile memory module.

3. The method for mapping table update of claim 1, wherein a first update data count of the first updated logical unit of the plurality of update data counts is greater than a first threshold.

4. The mapping table updating method as claimed in claim 1, wherein a first updated data count of the first updated logic unit among the plurality of updated data counts is smaller than a second threshold value.

5. The mapping table updating method of claim 1, wherein the step of selecting the first updated logical unit from the plurality of updated logical units comprises:

sorting the plurality of update data counts;

determining a third threshold value according to the plurality of sorted updated data counts; and

dividing the plurality of update data counts into at least one second update data count and at least one third update data count according to the third threshold value,

wherein the second update data count is greater than the third threshold value and the third update data count is not greater than the third threshold value.

6. The mapping table updating method of claim 5, wherein the step of selecting the first updated logical unit from the plurality of updated logical units further comprises:

identifying at least a second updated logical unit of the plurality of updated logical units corresponding to the second updated data count as the first updated logical unit, or identifying at least a third updated logical unit of the plurality of updated logical units corresponding to the third updated data count as the first updated logical unit.

7. A memory control circuit unit for controlling a rewritable nonvolatile memory module, the memory control circuit unit comprising:

a host interface for electrically connecting to a host system;

a memory interface electrically connected to the rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module has a plurality of physical erasing units, and a plurality of logical-physical mapping tables are stored in the rewritable nonvolatile memory module to record mapping information between the plurality of logical units and the plurality of physical erasing units;

a memory management circuit electrically connected to the host interface and the memory interface,

wherein the memory management circuit is configured to establish a physical-to-logical mapping table, wherein the physical-to-logical mapping table records mapping information between at least one active physical erase unit of the plurality of physical erase units and a plurality of updated logical units of the plurality of logical units,

wherein the memory management circuit is further configured to calculate a plurality of updated data counts of the plurality of updated logical units in the active physical erase unit according to the physical-to-logical mapping table,

wherein the memory management circuitry is further configured to select at least a first updated logical unit from the plurality of updated logical units according to the plurality of update data counts, wherein the number of the first updated logical unit is less than the number of the plurality of updated logical units,

wherein the memory management circuitry is further to load at least a first logical-to-physical mapping table corresponding to the first updated logical unit from the plurality of logical-to-physical mapping tables,

wherein the memory management circuitry is further to update mapping information in the first logical-to-physical mapping table based on mapping information of the first updated logical unit in the physical-to-logical mapping table.

8. The memory control circuit unit of claim 7, wherein

The memory management circuit is further configured to clear mapping information of the first updated logical unit in the physical-to-logical mapping table, retain mapping information of other updated logical units other than the first updated logical unit in the physical-to-logical mapping table, and restore the updated first logical-to-physical mapping table to the rewritable non-volatile memory module.

9. The memory control circuit unit of claim 7, wherein a first refresh data count of the first refreshed logic unit of the plurality of refresh data counts is greater than a first threshold value.

10. The memory control circuitry unit of claim 7, wherein a first update data count of the first updated logic unit of the plurality of update data counts is less than a second threshold value.

11. The memory control circuit unit of claim 7, wherein in the operation of selecting the first updated logic unit from the plurality of updated logic units,

the memory management circuit is further configured to sort the plurality of update data counts, determine a third threshold value according to the sorted plurality of update data counts, divide the plurality of update data counts into at least one second update data count and at least one third update data count according to the third threshold value,

12. The memory control circuit unit of claim 11, wherein in the operation of selecting the first updated logic unit from the plurality of updated logic units,

the memory management circuitry is further configured to identify at least a second one of the plurality of updated logical units corresponding to the second update data count as the first updated logical unit or identify at least a third one of the plurality of updated logical units corresponding to the third update data count as the first updated logical unit.

13. A memory storage device, comprising:

the connection interface unit is used for electrically connecting to a host system;

the system comprises a rewritable nonvolatile memory module, a first memory module and a second memory module, wherein the rewritable nonvolatile memory module is provided with a plurality of physical erasing units, and a plurality of logic-physical mapping tables are stored in the rewritable nonvolatile memory module to record mapping information between the plurality of logic units and the plurality of physical erasing units; and

a memory control circuit unit electrically connected to the connection interface unit and the rewritable nonvolatile memory module,

wherein the memory control circuit unit is used for establishing a physical-to-logical mapping table, wherein the physical-to-logical mapping table records mapping information between at least one active physical erasure unit in the plurality of physical erasure units and a plurality of updated logical units in the plurality of logical units,

wherein the memory control circuit unit is further configured to calculate a plurality of updated data counts of the plurality of updated logic units in the active physical erase unit according to the physical-to-logic mapping table,

wherein the memory control circuitry is further configured to select at least a first updated logic cell from the plurality of updated logic cells based on the plurality of update data counts, wherein the number of the first updated logic cells is less than the number of the plurality of updated logic cells,

wherein the memory control circuitry is further configured to load at least a first logical-to-physical mapping table corresponding to the first updated logical unit from the plurality of logical-to-physical mapping tables,

wherein the memory control circuitry unit is further configured to update mapping information in the first logical-to-physical mapping table based on mapping information of the first updated logical unit in the physical-to-logical mapping table.

14. The memory storage device of claim 13, wherein

The memory control circuit unit is further configured to clear mapping information of the first updated logical unit in the physical-to-logical mapping table, retain mapping information of other updated logical units except the first updated logical unit in the physical-to-logical mapping table, and restore the updated first logical-to-physical mapping table to the rewritable nonvolatile memory module.

15. The memory storage device of claim 13, wherein a first update data count of the first updated logic cell of the plurality of update data counts is greater than a first threshold value.

16. The memory storage device of claim 13, wherein a first update data count of the first updated logic cell of the plurality of update data counts is less than a second threshold value.

17. The memory storage device of claim 13, wherein in the operation of selecting the first updated logic cell from the plurality of updated logic cells,

the memory control circuit unit is further configured to count and sort the plurality of update data, and determine a third threshold value according to the sorted plurality of update data counts.

18. The memory storage device of claim 17, wherein in the operation of selecting the first updated logic cell from the plurality of updated logic cells,

the memory control circuit unit is further configured to sort the plurality of update data counts, determine a third threshold value according to the sorted plurality of update data counts, divide the plurality of update data counts into at least one second update data count and at least one third update data count according to the third threshold value,

19. A mapping table updating method for a rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module has a plurality of physical erasing units, and a plurality of logical-to-physical mapping tables are stored in the rewritable nonvolatile memory module to record mapping information between the plurality of logical units and the plurality of physical erasing units, the mapping table updating method comprising:

respectively calculating a plurality of updated data counts of the plurality of updated logic units in the active physical erasing unit according to the physical-logic mapping table;

selecting at least a first updated cell from the plurality of updated cells according to the plurality of updated data counts, wherein the number of the first updated cell is less than the number of the plurality of updated cells and a first updated data count of the first updated cell in the plurality of updated data counts is greater than a first threshold value;

loading at least a first logical-to-physical mapping table corresponding to the first updated logical unit from the plurality of logical-to-physical mapping tables;

updating mapping information in the first logical-to-physical mapping table according to mapping information of the first updated logical unit in the physical-to-logical mapping table;

clearing mapping information of the first updated logical unit in the physical-logical mapping table; and

and reserving mapping information of other updated logical units except the first updated logical unit in the physical-logical mapping table.