Method for data recovery for flash devices

• US 8,381,018 B2
• Filed: 05/21/2010
• Issued: 02/19/2013
• Est. Priority Date: 05/21/2010
• Status: Active Grant

• Current Assignee: MediaTek, Inc.
• Original Assignee: MediaTek, Inc.
• Inventors: Lee, Chia-Wen, Chen, Shih-Hsin, Hung, Shih-Ta, Chen, Ping-Sheng, Lu, Po-Ching
• Primary Examiner(s): Manoskey, Joseph D
• Application Number:
  US12/784,593
• Publication Number:
  US 20110289352A1
• Time in Patent Office: 1,005 Days
• Field of Search: 714/5, 714/5.1, 714/6.1, 714/6.11, 714/6.3, 714/15, 714/20, 714/42, 711/103, 711/202
• US Class Current: 714/6.1
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages

Abstract

The invention provides a method for data recovery. In one embodiment, a memory comprises a plurality of pages for data storage. First, first data is obtained from a host. A first page for storing the first data is then selected from the pages of the memory. A start page link indicating the first page is then stored in the memory. The first data, a first page link indicating a next page, and first FTL fragment data corresponding to the first page are then written into the first page. Next data is then obtained from the host. The next data, a next page link indicating a subsequent page, and FTL fragment data corresponding to the next page are written into the next page.

Claims

1. A method for data recovery, wherein a memory comprises a plurality of pages for data storage, a random access memory stores flash-translation-layer (FTL) data according to a mapping relationship between logical addresses and physical addresses of the pages, and the memory stores a previous version of the FTL data, comprising:

obtaining first data from a host;

selecting a first page for storing the first data from the pages of the memory;

storing a start page link indicating the first page in the memory;

writing the first data, a first page link indicating a next page, and first FTL fragment data corresponding to the first page into the first page;

obtaining next data from the host; and

writing the next data, a next page link indicating a subsequent page, and FTL fragment data corresponding to the next page into the next page.

2. The method as claimed in claim 1, wherein the steps for writing the next data, the next page link, and the FTL fragment data are repeatedly performed until the host does not send the new data.

3. The method as claimed in claim 1, wherein the method comprises:

after power of the memory is recovered, determining the first page according to the start page link stored in the memory;

reading the first page to obtain the first FTL fragment data corresponding to the first page;

determining the next page according to the first page link of the first page;

reading the next page to obtain the FTL fragment data corresponding to the next page;

repeatedly determining a new next page according to the next page link of the current next page and reading the new next page to obtain the FTL fragment data corresponding to the new next page until the next page link of the current next page points to null;

integrating the first FTL fragment data and all of the FTL fragment data together to obtain FTL patch data; and

combining the previous version of the FTL data stored in the memory with the FTL patch data to obtain a latest version of the FTL data.

4. The method as claimed in claim 3, wherein the method further comprises:

converting logical addresses received from the host into physical addresses according to the latest version of the FTL data; and

accessing data stored in the memory according to the physical addresses.

5. The method as claimed in claim 1, wherein the first FTL fragment data corresponding to the first page is compressed FTL data corresponding to the first page, and the FTL fragment data corresponding to the next page is compressed FTL fragment data corresponding to the next page.

6. A device capable of data recovery, comprising:

a memory, comprises a plurality of pages for data storage;

a random access memory, storing flash-translation-layer (FTL) data according to a mapping relationship between logical addresses and physical addresses of the pages; and

a microprocessor, obtaining first data from a host, selecting a first page for storing the first data from the pages of the memory, storing a start page link indicating the first page in the memory, writing the first data, a first page link indicating a next page, and first FTL fragment data corresponding to the first page into the first page, obtaining next data from the host, and writing the next data, a next page link indicating a subsequent page, and FTL fragment data corresponding to the next page into the next page.

7. The device as claimed in claim 6, wherein the microprocessor repeatedly obtains new next data from the host and writes the new next data, a new next page link, and new FTL fragment data to a new next page until the host does not send the new next data to the device.

8. The device as claimed in claim 6, wherein after power of the device is recovered, the microprocessor determines the first page according to the start page link stored in the memory, reads the first page to obtain the first FTL fragment data corresponding to the first page, determines the next page according to the first page link of the first page, reads the next page to obtain the FTL fragment data corresponding to the next page, repeatedly determines a new next page according to the next page link of the current next page and reads the new next page to obtain the FTL fragment data corresponding to the new next page until the next page link of the current next page points to null, integrates the first FTL fragment data and all of the FTL fragment data together to obtain FTL patch data, and combines the previous-version FTL data stored in the memory with the FTL patch data to obtain a latest version of the FTL data.

9. The device as claimed in claim 8, wherein the microprocessor converts logical addresses received from the host into physical addresses according to the latest version of the FTL data, and accesses data stored in the memory according to the physical addresses.

10. The device as claimed in claim 6, wherein the first FTL fragment data corresponding to the first page is compressed FTL data corresponding to the first page, and the FTL fragment data corresponding to the next page is compressed FTL data corresponding to the next page.

11. A method for data recovery for a flash device, wherein a flash memory of the flash device comprises a plurality of pages for data storage, a random access memory stores flash-translation-layer data recording to a mapping relationship between logical addresses and physical addresses of the pages, and the flash memory stores a previous version of the FTL data, comprising:

obtaining first data from a host;

selecting a first page for storing first data from the pages of the flash memory;

writing the first data, a first page link indicating the previous version of the FTL data, and first FTL fragment data corresponding to the first page into the first page;

obtaining next data from the host; and

writing the next data, a previous page link indicating the first page, and FTL fragment data corresponding to a next page into the next page.

12. The method as claimed in claim 11, wherein the method further comprises:

obtaining new next data from the host;

writing the new next data, a previous page link indicating a previous page, and FTL fragment data corresponding to the new next page to the new next page; and

repeating the steps for obtaining new next data from the host and writing the new next data, the previous page link, and the FTL fragment data to the new next page continuously, until the host does not send new data to the flash device.

13. The method as claimed in claim 11, wherein the method comprises:

after power of the flash device is recovered, searching the pages of the flash memory for a last page;

reading the last page to obtain the FTL fragment data corresponding to the last page;

determining a previous page according to a last page link of the last page;

reading the previous page to obtain the FTL fragment data corresponding to the previous page;

repeatedly determining a new previous page according to the previous page link of the current previous page and reading the new previous page to obtain the FTL fragment data corresponding to the new previous page until the previous page link of the current previous page indicates the first page;

integrating the first FTL fragment data and all of the FTL fragment data together to obtain FTL patch data; and

combining the previous version of the FTL data stored in the flash memory with the FTL patch data to obtain a latest version of the FTL data.

14. The method as claimed in claim 13, wherein the method further comprises:

converting logical addresses received from the host into physical addresses according to the latest version of the FTL data; and

accessing data stored in the flash memory according to the physical addresses.

15. The method as claimed in claim 11, wherein the method further comprises:

when power of the flash device is shut down, recording an end page link indicating a last page in a storage device; and

after power of the flash device is recovered, determining the last page according to the end page link stored in the storage device.

16. The method as claimed in claim 11, wherein the first FTL fragment data corresponding to the first page is compressed FTL data corresponding to the first page, and the FTL fragment data corresponding to the next page is compressed FTL data corresponding to the next page.

17. A method for data recovery for a flash device, wherein a flash memory of the flash device comprises a plurality of blocks, and each of the blocks comprises a plurality of pages for data storage, comprising:

when writing data to a target page of a target block selected from the blocks, recording a block type and a physical block number of the target block in the target page;

after power of the flash device is recovered, determining whether the target block is a garbage collection block according to the block types and the physical block numbers stored in the pages of the target block; and

rebuilding flash-translation-layer (FTL) data recorded a mapping relationship between logical numbers and physical numbers according to whether the target block is a garbage collection block.

18. The method as claimed in claim 17, wherein determining of whether the target block is a garbage collection block comprises:

obtaining the target block;

determining whether the target block comprises a first page storing a first physical block number that is different from a second physical block number of the target block; and

when the target block comprises the first page storing the first physical block number that is different from the second physical block number of the target block, determining the target block to be a garbage collection block.

19. The method as claimed in claim 18, wherein determining of whether the target block is a garbage collection block further comprises:

determining whether the target block comprises at least two second pages storing different block types; and

when the target block comprises at least two second pages storing different block types, determining the target block to be a garbage collection block.

20. The method as claimed in claim 17, wherein the method further comprises:

after power of the flash device is recovered, obtaining a plurality of first blocks mapped to a target logical block number;

determining whether the first blocks are garbage collection blocks;

when the first blocks comprise only one garbage collection block, determining the garbage collection block to be a new block;

when the first blocks comprise a plurality of garbage collection blocks, searching the garbage collection blocks for a target garbage collection block comprising pages storing physical block numbers of other garbage collection blocks, and determining the garbage collection block to be the newest block; and

recording a mapping relationship between the newest block and the target logical block number in the FTL data.

21. The method as claimed in claim 20, wherein the method further comprises:

when the first blocks comprises a plurality of garbage collection blocks, determining block types of the first block; and

when the first blocks comprises an active block, determining the active block to be the newest block.

22. The method as claimed in claim 17, wherein the method further comprises:

when writing data to the target page of the target block selected from the blocks and the target block is an active block storing update data for a data source block, recording a physical block number of the data source block as a data-source physical block number in the target page.

23. The method as claimed in claim 22, wherein the method further comprises:

after power of the flash device is recovered, obtaining a plurality of first blocks mapped to a target logical block number;

determining whether the first blocks are garbage collection blocks;

when the first blocks comprise only one garbage collection block, determining the garbage collection block to be a new block; and

rebuilding a FTL data according to data stored in the newest block.

24. The method as claimed in claim 23, wherein the method further comprises:

when the first blocks comprise a plurality of garbage collection blocks, checking whether a plurality of specific physical block numbers or a plurality of specific data-source physical block numbers stored in pages of the garbage collection blocks are not equal to physical block numbers of the garbage collection blocks;

determining a plurality of old blocks with physical block numbers equal to the specific physical block numbers or the specific data-source physical block numbers stored in the pages of the garbage collection blocks;

determining a newest block from the first blocks which are not the old blocks; and

rebuilding a FTL data according to data stored in the newest block.

25. The method as claimed in claim 17, wherein the blocks of the flash memory have block types of a data block, an active block, and a garbage collection block, and the step of recording a block type of the target block in the target page further comprises:

when the target block is a garbage collection block, recording the block type of the target block to be a garbage collection block in the target page.

26. A device capable of data recovery, comprising:

a memory, comprising a plurality of blocks, wherein each of the blocks comprises a plurality of pages for data storage; and

a microcontroller, recording a block type and a physical block number of a target block in a target page when data is written into the target page, determining whether the target block is a garbage collection block according to the block types and the physical block numbers stored in the pages of the target block after power of the device is recovered, and rebuilding flash-translation-layer (FTL) data recorded a mapping relationship between logical numbers and physical numbers according to the determining result.

27. The device as claimed in claim 26, wherein when the target block is determined to be a garbage collection block, the microcontroller obtains the target block, determines whether the target block comprises a first page storing a first physical block number that is different from a second physical block number of the target block, and determines the target block to be a garbage collection block when the target block comprises the first page storing the first physical block number that is different from the second physical block number of the target block.

28. The device as claimed in claim 27, wherein when the target block is determined to be a garbage collection block, the microcontroller further determines whether the target block comprises at least two second pages storing different block types, and determines the target block to be a garbage collection block when the target block comprises at least two second pages storing different block types.

29. The device as claimed in claim 26, wherein the microcontroller obtains a plurality of first blocks mapped to a target logical block number after power of the device is recovered, determines whether the first blocks are garbage collection blocks, determines the garbage collection block to be a new block when the first blocks comprise only one garbage collection block, searches the garbage collection blocks for a target garbage collection block comprising pages storing physical block numbers of other garbage collection blocks, and determines the garbage collection block to be the newest block when the first blocks comprise a plurality of garbage collection blocks, and records a mapping relationship between the newest block and the target logical block number in the FTL data.

30. The device as claimed in claim 29, wherein the microcontroller further determines block types of the first block when the first blocks comprises a plurality of garbage collection blocks, and determines the active block to be the newest block when the first blocks comprises an active block.

31. The device as claimed in claim 26, wherein when data is written into the target page of the target block selected from the blocks and the target block is an active block storing update data for a data source block, the microcontroller records a physical block number of the data source block as a data-source physical block number in the target page.

32. The device as claimed in claim 31, wherein the microcontroller obtains a plurality of first blocks mapped to a target logical block number after power of the device is recovered, determines whether the first blocks are garbage collection blocks, determines the garbage collection block to be a new block when the first blocks comprise only one garbage collection block, and rebuilds a FTL data according to data stored in the newest block.

33. The device as claimed in claim 32, wherein when the first blocks comprise a plurality of garbage collection blocks, the microcontroller further checks whether a plurality of specific physical block numbers or a plurality of specific data-source physical block numbers stored in pages of the garbage collection blocks are not equal to physical block numbers of the garbage collection blocks, determines a plurality of old blocks with physical block numbers equal to the specific physical block numbers or the specific data-source physical block numbers stored in the pages of the garbage collection blocks, determines a newest block from the first blocks which are not the old blocks, and rebuilds a FTL data according to data stored in the newest block.

34. The device as claimed in claim 26, wherein the blocks of the memory have block types of a data block, an active block, and a garbage collection block, and the microcontroller records the block type of the target block to be a garbage collection block in the target page when the target block is a garbage collection block.