Data backup method, data recovery method and storage controller

A data recovery method, adapted to a storage device equipped with a rewritable non-volatile memory module, wherein the rewritable non-volatile memory module has a plurality of physical units, and the rewritable non-volatile memory module is allocated with a plurality of physical addresses, wherein a host system coupled to the storage device is allocated with a plurality of logical address, the method comprising:

• re-establishing a first logical-to-physical table according to the first logical-to-physical table stored in the rewritable non-volatile memory module, a physical address of all valid data of which a timestamp is larger than a timestamp of the first logical-to-physical table in the rewritable non-volatile memory module, and a corresponding logical address, and storing the re-established first logical-to-physical table to a memory as a second logical-to-physical table;
• if the rewritable non-volatile memory module stores one or more first trim information lists, identifying a latest second trim information list among the one or more trim information lists, wherein the second trim information list records one or more trim information, and the second trim information list is stored in a target physical page of a target physical unit,
• wherein each of the trim information records an invalid data starting logical address, an invalid data length, a trim information page order and a trim information timestamp, wherein the trim information page order is an order of the target physical page in all of the physical pages of the target physical unit, wherein the trim information timestamp is a timestamp of the target physical unit,
• wherein a timestamp of the one or more first trim information lists is larger than a timestamp of the first logical-to-physical table;
• and
• updating the second logical-to-physical table or updating a third trim information list stored in the memory according to all of the trim information in the second trim information list and the second logical-to-physical table.

A storage controller, for controlling a storage device equipped with a rewritable non-volatile memory module, and comprising:

• a connection interface circuit, coupled to a host system allocated with a plurality of logical addresses;
• a memory interface controlling circuit, coupled to the rewritable non-volatile memory module, wherein the rewritable non-volatile memory module comprises a plurality of physical units, and the rewritable non-volatile memory module is allocated with a plurality of physical addresses;
• and
• a processor, coupled to the connection interface circuit and the memory interface control circuit,
• wherein the processor receives a trim command from the host system, wherein the trim command indicates an invalid data stored in a logical address section,
• wherein the processor generates a trim information according to the trim command and a target physical address among the physical addresses, so as to update a first trim information list as a second trim information list according to the trim information by adding the generated trim information behind other trim information in the first trim information list maintained in a memory, wherein the target physical address is an address of a target physical page of a target physical unit, and the target physical page is used for storing the second trim information list,
• wherein the trim information records an invalid data starting logical address, an invalid data length, a trim information page order and a trim information timestamp,
• wherein the processor further stores the second trim information list to the target physical address, wherein the first or the second trim information list records one or more trim information in order according to a time sequence of receiving a trim command corresponding to the one or more trim information, wherein the trim information page order is an order of the target physical page in all of the physical pages of the target physical unit, wherein the trim information timestamp is a timestamp of the target physical unit,
• wherein the processor further records the target physical address for storing the second trim information list to a trim information list physical address recorded of a first logical-to-physical table, so as to update the first logical-to-physical table as a second logical-to-physical table,
• wherein when a predetermined condition is fulfilled, the processor further stores the second logical-to-physical table to the rewritable non-volatile memory module.

A storage controller, for controlling a storage device equipped with a rewritable non-volatile memory module, and comprising:

• a connection interface circuit, coupled to a host system allocated with a plurality of logical addresses;
• a memory interface control circuit, coupled to the rewritable non-volatile memory module, wherein the rewritable non-volatile memory module has a plurality of physical units, and the rewritable non-volatile memory module is allocated with a plurality of physical addresses;
• and
• a processor, coupled to the connection interface circuit and the memory interface control circuit,
• wherein the processor re-establishes the first logical-to-physical table according to a first logical-to-physical table stored in the rewritable non-volatile memory module, a physical address of all valid data of which a timestamp of the rewritable non-volatile memory module is larger than a timestamp of the first logical-to-physical table in the rewritable non-volatile memory module, and corresponding logical address, and storing the re-established first logical-to-physical table to a memory as a second logical-to-physical table,
• wherein if the rewritable non-volatile memory module stores one or more first trim information lists, the processor further identifies a latest second trim information list among the one or more first trim information lists, wherein the second trim information list records one or more trim information, and the second trim information list is stored in a target physical page of a target physical unit,
• wherein each of the trim information records an invalid data starting logical address, an invalid data length, a trim information page order and a trim information timestamp, wherein the trim information page order is an order of the target physical page in all of the physical pages of the target physical unit, wherein the trim information timestamp is a timestamp of the target physical unit,
• wherein a timestamp of the one or more first trim information list is larger than the timestamp of the first logical-to-physical table,
• wherein the processor further updates the second logical-to-physical table or updates a third trim information list stored in the memory according to all of the trim information in the second trim information list and the second logical-to-physical table.