CACHING METHOD FOR NAND FLASH TRANSLATION LAYER

• US 20080126684A1
• Filed: 08/23/2007
• Published: 05/29/2008
• Est. Priority Date: 11/23/2006
• Status: Active Grant

• Current Assignee: Genesys Logic Incorporated
• Original Assignee: Genesys Logic Incorporated
• Inventors: Kuo, Tei-wei, Wu, Chin-hsien, Hsieh, Hsiang-chi
• Granted Patent: US 7,761,648 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory

Abstract

A caching method provides a cashing mechanism between a logical addresses and a flash memory physical addresses. The cashing mechanism involves a search tree which contains a number of internal and external translation nodes. Each external translation node points to a link list of translation units, and each translation unit records a range of logical addresses and the corresponding range of physical addresses, in addition to a version value. By traversing the search tree to reach a translation unit, the physical address of a target logical address can be determined in an efficient manner. The version value of the translation unit can be used to determine the space taken up for storing the mapping of the logical and physical addresses should be released for reuse.

Claims

1. A caching method for NAND flash translation layer, comprising the following steps:

(A) starting;

(B) establishing a caching mechanism for the address translation between a flash memory'"'"'s logical and physical addresses;

(C) establishing a search tree in the caching mechanism;

(D) establishing a plurality of internal and external translation nodes in the search tree;

(E) pointing the external translation nodes to link list of translation units, respectively, wherein each translation unit specifies a range of consecutive flash memory physical addresses corresponding to a range of consecutive logical addresses, a number of translation units are connected into a link list, and an external translation node points to the link list;

(F) For a target logical address, determining if a translation unit having a range of logical addresses covers the target logical address is found by traversing the search tree from the root and, if yes, obtaining the corresponding flash memory physical address using the translation unit;

(G) determining whether the access is a read or write operation and, if it is a read operation, continuing to step (H);

otherwise, continuing to step (I);

(H) conducting a read access caching operation based on the determined physical address and continuing to step (J);

(I) conducting a write access caching operation based on the determined physical address; and

(J) ending.

2. The caching method as claimed in claim 1, wherein each internal translation node is assigned an attribute.

3. The caching method as claimed in claim 2, wherein the attribute comprises a first attribute value, a second attribute value, and a third attribute value.

4. The caching method as claimed in claim 3, wherein the first and second attribute values specify the first and last logical addresses of a logical address range, respectively.

5. The caching method as claimed in claim 3, wherein the third attribute value points to an external translation node.

6. The caching method as claimed in claim 1, wherein each external translation node is assigned an attribute.

7. The caching method as claimed in claim 6, wherein the attribute comprises a first attribute value, a second attribute value, and a fourth attribute value.

8. The caching method as claimed in claim 7, wherein the first and second attribute values specify the first and last logical addresses of a logical address range, respectively.

9. The caching method as claimed in claim 7, wherein the fourth attribute value points to a link list of at least a translation unit.

10. The caching method as claimed in claim 1, wherein each translation unit is assigned an attribute.

11. The caching method as claimed in claim 10, wherein the attribute comprises a fifth attribute value, a sixth attribute value, a seventh attribute value, and an eighth attribute value.

12. The caching method as claimed in claim 11, wherein the fifth attribute value specifies the first logical address of the range of logical addresses.

13. The caching method as claimed in claim 11, wherein the sixth attribute value specifies the first physical address of a range of the flash memory physical addresses.

14. The caching method as claimed in claim 11, wherein the seventh attribute value specifies the length of the range of the logical addresses.

15. The caching method as claimed in claim 11, wherein the eighth attributes is a timestamp of the translation unit.

16. The caching method as claimed in claim 1, wherein the read access cashing operation comprises the following steps:

(H1) starting;

(H2) determining if the physical address exists and, if yes, continuing to step (H4), otherwise continuing to step (H3);

(H3) using a block level mechanism to determine the physical address corresponding to the target logical address;

(H31) storing the target logical address and the corresponding physical address in a translation unit of the cashing mechanism;

(H4) reading a page of the flash memory containing the corresponding physical address; and

(H5) ending.

17. The caching method as claimed in claim 1, wherein the write access caching operation comprises the following steps:

(I1) starting;

(I2) using a block level mechanism to determine the physical address corresponding to the target logical address;

(I3) writing a page of the flash memory containing the corresponding physical address;

(I4) storing the target logical address and the corresponding physical address in a translation unit of the cashing mechanism;

(I5) determining whether the space for storing the logical and corresponding physical addresses has exceeded an upper bound and, if yes, continuing to the step I6, otherwise continuing to step (I7);

(I6) releasing the space taken up by those logical addresses and their corresponding physical addresses that have not been used for a long time for reuse, based on a version value of the translation unit; and

(I7) ending.