Multi-tier address mapping in flash memory

• US 8,341,340 B2
• Filed: 07/21/2010
• Issued: 12/25/2012
• Est. Priority Date: 07/21/2010
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Rub, Bernardo
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US12/840,938
• Publication Number:
  US 20120023282A1
• Time in Patent Office: 888 Days
• Field of Search: 711/103, 711/206
• US Class Current: 711/103
• 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

A user data portion of a flash memory arrangement is grouped into a plurality of mapping units. Each of the mapping units includes a user data memory portion and a metadata portion. The mapping units form a plurality of groups that are associated with at least one lower tier of a forward memory map. For each of the groups, a last written mapping unit within the group is determined. The last written mapping unit includes mapping data in the metadata portion that facilitates determining a physical address of other mapping units within the group. A top tier of the forward memory map is formed that includes at least physical memory locations of the last written mapping units of each of the groups. A physical address of a targeted memory is determined using the top tier and the metadata of the at least one lower tier.

Claims

1. A method comprising:

grouping a user data portion of a flash memory arrangement into a plurality of mapping units, wherein each of the mapping units comprises a user data memory portion and a metadata portion;

forming the mapping units into a plurality of groups, wherein the groups are associated with at least one lower tier of a forward memory map;

for each of the groups, determining a last written mapping unit within the group, wherein the last written mapping unit includes mapping data in the metadata portion that facilitates determining a physical address of other mapping units within the group;

forming a top tier of the forward memory map that includes at least physical memory locations of the last written mapping units of each of the groups; and

determining a physical address of a targeted memory using the top tier and the metadata of the at least one lower tier.

2. The method of claim 1, where the physical addresses of the mapping units are arbitrarily assigned to corresponding logical addresses used by a host to access the user data memory portions of the mapping units.

3. The method of claim 1, where determining a physical address of the targeted memory using the top tier and the metadata of the at least one lower tier comprises:

selecting a first last written memory unit from a selected one of groups based on a logical address of the targeted memory;

determining the physical address of the targeted memory based on the metadata portion of the first last written memory unit.

4. The method of claim 1, wherein the at least one lower tier comprises a second tier and a third tier, and wherein the groups are associated with the second tier.

5. The method of claim 4, wherein each of the groups comprise a plurality of subgroups, and wherein the subgroups are associated with the third tier.

6. The method of claim 5, where determining the physical address of the targeted memory using the top tier and the metadata of the at least one lower tier comprises:

selecting a first last written memory unit from a selected one of groups based on a logical address of the targeted memory;

determining a second last written memory unit of a selected one of the subgroups based on the metadata portion of the first last written memory unit; and

determining the physical address of the targeted memory based on the metadata portion of the second last written memory unit.

7. The method of claim 1, wherein the mapping data of the last written mapping units do not include the physical addresses of the respective last written mapping units.

8. An apparatus, comprising:

a user data portion of a flash memory arrangement grouped into a plurality of mapping units, wherein each of the mapping units comprises a user data memory portion and a metadata portion; and

a controller configured to provide access to the user data portion of the flash memory based on logical addresses, the controller configured with instructions that cause the apparatus to;

form the mapping units into a plurality of groups, wherein the groups are associated with at least one lower tier of a forward memory map;

for each of the groups, determine a last written mapping unit within the group, wherein the last written mapping unit includes mapping data in the metadata portion that facilitates determining a physical address of other mapping units within the group;

form a top tier of the forward memory map that includes at least physical memory locations of the last written mapping units of each of the groups; and

determine a physical address of a targeted memory using the top tier and the metadata of the at least one lower tier.

9. The apparatus of claim 8, where the physical addresses of the mapping units are arbitrarily assigned to corresponding logical addresses used by a host to access the user data memory portions of the mapping units.

10. The apparatus of claim 8, where determining a physical address of the targeted memory using the top tier and the metadata of the at least one lower tier comprises:

selecting a first last written memory unit from a selected one of groups based on a logical address of the targeted memory;

determining the physical address of the targeted memory based on the metadata portion of the first last written memory unit.

11. The apparatus of claim 8, wherein the at least one lower tier comprises a second tier and a third tier, and wherein the groups are associated with the second tier.

12. The apparatus of claim 11, wherein each of the groups comprise a plurality of subgroups, and wherein the subgroups are associated with the third tier.

13. The apparatus of claim 12, where determining the physical address of the targeted memory using the top tier and the metadata of the at least one lower tier comprises:

selecting a first last written memory unit from a selected one of groups based on a logical address of the targeted memory;

determining a second last written memory unit of a selected one of the subgroups based on the metadata portion of the first last written memory unit; and

determining the physical address of the targeted memory based on the metadata portion of the second last written memory unit.

14. The apparatus of claim 8, wherein the mapping data of the last written mapping units do not include the physical addresses of the respective last written mapping units.

15. A method comprising:

receiving, at a flash memory device, an access request for user data based a logical memory address;

determining, from a top tier of a forward map based on the logical memory address, a physical address of a last written mapping unit of a lower tier group of the forward map, wherein the lower tier group comprises a plurality of mapping units, including the last written mapping unit, and wherein the mapping units each comprise a user data memory portion and a metadata portion;

determining, from lower tier mapping data within the metadata portion of the last written mapping unit, a second physical address of a mapping unit of the lower tier group; and

facilitating access to the user data based on the second physical address.

16. The method of claim 15, wherein the physical addresses of the mapping units are arbitrarily assigned to the corresponding logical addresses.

17. The method of claim 15, wherein the access request comprises a write request, the method further comprising:

selecting an new mapping unit of the lower tier group for receiving user data of the write request;

updating the lower tier mapping data based on a physical address of the new mapping unit;

writing the user data and the mapping data to the respective user data memory portion and metadata portion of the new mapping unit; and

updating the top tier with a physical address of the new mapping unit.

18. The method of claim 15, wherein the determining of the second physical address from the lower tier mapping data of the last written mapping unit only occurs if the last written mapping unit does not correspond to the logical memory address, and if the last written mapping unit corresponds to the logical memory address, providing physical address of the last written mapping unit as the second physical address to facilitate access to the user data.

19. The method of claim 15, wherein the lower tier mapping data comprises second tier mapping data, and wherein facilitating access to the user data based on the second physical address comprises:

determining, from the second tier mapping data, a physical address of a second last written mapping unit of a third tier group of the forward map, wherein the third tier group comprises a subset of the lower tier group;

determining, from third tier mapping data within the metadata portion of the second last written mapping unit, a third physical address of a mapping unit of the third tier group; and

facilitating access to the user data based on the third physical address.

20. An apparatus, comprising a user data portion of a flash memory arrangement and a controller configured with instructions that cause the apparatus to perform the operations set forth in the method of claim 15, wherein the user data portion of the flash memory comprises the plurality of mapping units.