Flash storage devices and methods for organizing address mapping tables in flash storage devices

• US 9,600,209 B2
• Filed: 04/23/2015
• Issued: 03/21/2017
• Est. Priority Date: 06/12/2014
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Chaitanya, Kavirayani Venkata Ramakrishna, Singh, Santosh, Singh, Vikram
• Primary Examiner(s): Lane, John A
• Application Number:
  US14/694,060
• Publication Number:
  US 20150363327A1
• Time in Patent Office: 698 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

In some example embodiments, a method of organizing an address mapping table of a flash storage device based on Logical Block Address (LBA) size may comprise: identifying an extent of correlation between the LBA and flash page sizes, wherein the extent of correlation indicates greater or lesser extent; computing a total number of entries in each meta page of the table; and/or organizing the table with the total number of entries. In some example embodiments, a method of organizing an address mapping table of a flash storage device based on LBA size may comprise: determining flash page size of the flash storage device; determining the LBA size; and/or comparing the flash page and LBA sizes. When the flash page size is greater, the table may be organized based on flash page size. When the flash page size is less, the table may be organized based on LBA size.

Claims

1. A method of organizing an address mapping table of a flash storage device based on a Logical Block Address (LBA) size, the method comprising:

identifying an extent of correlation between the LBA size and a flash page size, wherein the extent of correlation indicates one of greater extent and lesser extent;

computing a total number of entries in each meta page of the address mapping table; and

organizing the address mapping table with the computed total number of entries in each meta page of the address mapping table.

2. The method of claim 1, wherein the computing of the total number of entries in each meta page of the address mapping table comprises:

calculating an extent value between the LBA size and the flash page size, wherein the extent value indicates one of a number of times the LBA size is greater than the flash page size and a number of times the LBA size is less than the flash page size;

determining whether each of the entries in the address mapping table is maintained based on one of the LBA size and the flash page size; and

computing the total number of entries in each meta page based on one of the page size and a size of each entry in the meta page in response to determining that each of the entries in the address mapping table is maintained based on one of the LBA size and the flash page size.

3. The method of claim 1, wherein the organizing of the address mapping table with the computed total number of entries in each the meta page of the address mapping table comprises:

calculating a number of meta pages required to store the entries in the address mapping table based on the computed total number of entries in each meta page; and

allocating memory to store the calculated number of meta pages.

4. The method of claim 1, wherein data of the LBA size is stored contiguously in the meta pages.

5. The method of claim 1, further comprising:

maintaining each entry in the address mapping table representing data of the LBA size based on the correlation.

6. The method of claim 1, further comprising:

accessing the organized address mapping table by one of input operation and output operation.

7. The method of claim 6, wherein the accessing of the organized address mapping table by one of the input operation and output operation comprises:

identifying an entry representing data associated with one of the input operation and output operation, wherein the entry is identified among the number of entries; and

computing a number of pages to access the data based on a size of each entry in the address mapping table and the flash page size.

8. A flash storage device for organizing an address mapping table based on a Logical Block Address (LBA) size, the flash storage device comprising:

a plurality of flash arrays that store data; and

a controller configured to;

identify an extent of correlation between the LBA size and a flash page size, wherein the extent of correlation indicates one of greater extent and lesser extent;

compute a total number of entries in each meta page of the address mapping table; and

organize the address mapping table with the computed total number of the entries in each meta page of the address mapping table.

9. The flash storage device of claim 8, wherein the controller is further configured to compute the total number of entries in each meta page of the address mapping table LBA size by:

calculating an extent value between the LBA size and the flash page size, wherein the extent value indicates one of a number of times the LBA size is greater than the flash page size and a number of times the LBA size is less than the flash page size;

determining whether each of the entries in the address mapping table is maintained based on one of the LBA size and the flash page size; and

computing the total number of entries in each meta page based on one of the page size and a size of each of the entries in the meta page in response to determining that each of the entries in the address mapping table is maintained based on one of the LBA size and the flash page size.

10. The flash storage device of claim 8, wherein the controller is further configured to organize the address mapping table with the computed total number of entries in each meta page of the address mapping table by:

calculating a number of meta pages required to store the entries in the address mapping table based on the computed total number of entries in each meta page; and

allocating memory to store the calculated number of meta pages.

11. The flash storage device of claim 8, wherein data of the LBA size is stored contiguously in the meta pages.

12. The flash storage device of claim 8, wherein the controller is further configured to maintain each entry in the address mapping table representing data of the LBA size based on the correlation.

13. The flash storage device of claim 8, the controller is further configured to:

access the organized address mapping table by one of input operation and output operation.

14. The flash storage device of claim 13, wherein the controller is further configured to access the organized address mapping table by one of the input operation and output operation by:

identifying an entry representing data associated with one of the input operation and output operation, wherein the entry is identified among the number of entries; and

computing a number of pages to access the data based on a size of each entry in the address mapping table and the flash page size.

15. A method of organizing an address mapping table of a flash storage device based on a Logical Block Address (LBA) size, the method comprising:

determining a flash page size of the flash storage device;

determining the LBA size; and

comparing the flash page size to the LBA size;

wherein when the flash page size is greater than the LBA size, the address mapping table is organized based on the flash page size, and

wherein when the flash page size is less than the LBA size, the address mapping table is organized based on the LBA size.

16. The method of claim 15, wherein data in groups of the LBA size is stored contiguously in meta pages of the address mapping table.

17. The method of claim 15, further comprising:

accessing the organized address mapping table by input operation.

18. The method of claim 17, wherein the accessing of the organized address mapping table by the input operation comprises:

identifying an entry representing data associated with the input operation;

wherein the entry is identified among a number of entries in the address mapping table.

19. The method of claim 18, wherein the accessing of the organized address mapping table by the input operation further comprises:

computing a number of pages to access the data based on a size of the entries in the address mapping table and the flash page size.

20. The method of claim 15, further comprising:

accessing the organized address mapping table by output operation.