Accessing logical-to-physical address translation data for solid state disks

• US 8,898,371 B2
• Filed: 04/29/2010
• Issued: 11/25/2014
• Est. Priority Date: 09/23/2009
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Reiter, Randy, Swatosh, Timothy, Hempstead, Pamela, Hicken, Michael
• Primary Examiner(s): Sadler, Nathan
• Application Number:
  US12/769,882
• Publication Number:
  US 20110072198A1
• Time in Patent Office: 1,671 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 13/14 Handling requests for interconnection or transfer
• CPC Class Codes: G06F 13/24 using interrupt G06F13/32 takes precedence
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2213/0028 Serial attached SCSI [SAS]
• CPC Class Codes: G06F 3/00 Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements

Abstract

Described embodiments provide a media controller for a storage device having sectors, the sectors organized into blocks and superblocks. The media controller stores, on the storage device, logical-to-physical address translation data in N summary pages, where N corresponds to the number of superblocks of the storage device. A buffer layer module of the media controller initializes a summary page cache in a buffer. The summary page cache has space for M summary page entries, where M is less than or equal to N. For operations that access a summary page, the media controller searches the summary page cache for the summary page. If the summary page is stored in the summary page cache, the buffer layer module retrieves the summary page from the summary page cache. Otherwise, the buffer layer module retrieves the summary page from the storage device and stores the retrieved summary page to the summary page cache.

Claims

1. A method of accessing, by a media controller, logical-to-physical address translation data for one or more sectors of a storage device, the sectors of the storage device organized into blocks and superblocks, the method comprising:

storing, on the storage device, the logical-to-physical address translation data in N summary pages, wherein N is an integer corresponding to the number of superblocks of the storage device;

initializing, by a buffer layer module of the media controller, a summary page cache in a buffer of the media controller, the summary page cache having space for M summary page entries, wherein M is an integer less than or equal to N;

for an operation, by the media controller, accessing a summary page;

searching the summary page cache for the summary page;

if the summary page is stored in the summary page cache;

retrieving, by the buffer layer module, the summary page from the summary page cache;

otherwise, if the required summary page is not stored in the summary page cache;

retrieving, by the buffer layer module, the summary page from the storage device; and

storing the retrieved summary page to the summary page cache.

2. The invention of claim 1, comprising storing the M summary page entries in a linked list with i) a most recently accessed summary page at a head end of the linked list, and ii) a least recently accessed summary page at a tail end of the linked list.

3. The invention of claim 2, wherein the step of retrieving the summary page from the summary page cache further comprises:

moving the retrieved summary page to the head end of the linked list of the summary page cache.

4. The invention of claim 2, wherein the step of retrieving the summary page from the storage device further comprises:

storing the retrieved summary page at a next available entry of the summary page cache; and

moving the retrieved summary page to the head end of the linked list of the summary page cache.

5. The invention of claim 2, where the step of storing the retrieved summary page to the summary page cache further comprises:

if all entries of the summary page cache are occupied;

purging the entry at the tail end of the linked list of the summary page cache;

storing the retrieved summary page to the purged entry; and

moving the retrieved summary page to the head end of the linked list of the summary page cache.

6. The invention of claim 1, comprising providing, by the storage device, one or more wear-level units, each wear-level unit having a corresponding summary page cache.

7. The invention of claim 1, comprising incrementing, for each access of one of the M summary page entries, an access count for the corresponding summary page entry.

8. The invention of claim 1, wherein M is equal to three.

9. A non-transitory machine-readable storage medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of accessing, by a media controller, logical-to-physical address translation data for one or more sectors of a storage device, the sectors of the storage device organized into blocks and superblocks, the method comprising:

storing, on the storage device, the logical-to-physical address translation data in N summary pages, wherein N is an integer corresponding to the number of superblocks of the storage device;

initializing, by a buffer layer module of the media controller, a summary page cache in a buffer of the media controller, the summary page cache having space for M summary page entries, wherein M is an integer less than or equal to N;

for an operation, by the media controller, accessing a summary page;

searching the summary page cache for the summary page;

if the summary page is stored in the summary page cache;

retrieving, by the buffer layer module, the summary page from the summary page cache;

otherwise, if the required summary page is not stored in the summary page cache;

retrieving, by the buffer layer module, the summary page from the storage device; and

storing the retrieved summary page to the summary page cache.

10. The non-transitory machine-readable storage medium of claim 9, comprising storing the M summary page entries in a linked list with i) a most recently accessed summary page at a head end of the linked list, and ii) a least recently accessed summary page at a tail end of the linked list.

11. The non-transitory machine-readable storage medium of claim 10, wherein the step of retrieving the summary page from the summary page cache further comprises:

moving the retrieved summary page to the head end of the linked list of the summary page cache.

12. The non-transitory machine-readable storage medium of claim 10, wherein the step of retrieving the summary page from the storage device further comprises:

storing the retrieved summary page at a next available entry of the summary page cache; and

moving the retrieved summary page to the head end of the linked list of the summary page cache.

13. The non-transitory machine-readable storage medium of claim 10, where the step of storing the retrieved summary page to the summary page cache further comprises:

if all entries of the summary page cache are occupied;

purging the entry at the tail end of the linked list of the summary page cache;

storing the retrieved summary page to the purged entry; and

moving the retrieved summary page to the head end of the linked list of the summary page cache.

14. The non-transitory machine-readable storage medium of claim 9, comprising providing, by the storage device, one or more wear-level units, each wear-level unit having a corresponding summary page cache.

15. The non-transitory machine-readable storage medium of claim 9, comprising incrementing, for each access of one of the M summary page entries, an access count for the corresponding summary page entry.

16. The non-transitory machine-readable storage medium of claim 9, wherein M is equal to three.

17. A media controller for accessing, by a media controller, logical-to-physical address translation data for one or more sectors of a storage device, the sectors of the storage device organized into blocks and superblocks, the media controller comprising:

a reserved area of the storage device having N summary pages, wherein N is an integer corresponding to the number of superblocks of the storage device;

a summary page cache in a buffer of the media controller, the summary page cache having space for M summary page entries, wherein M is an integer less than or equal to N;

a buffer layer module adapted to, when accessing a summary page, i) search the summary page cache for the summary page, ii) if the summary page is stored in the summary page cache, retrieve the summary page from the summary page cache, iii) otherwise, retrieve the summary page from the storage device, and iv) store the retrieved summary page to the summary page cache.

18. The invention of claim 17, wherein the summary page cache is a linked list having a head end and a tail end, wherein the buffer layer module is further adapted to:

if the summary page is stored in the summary page cache;

move the retrieved summary page to the head end of the linked list of the summary page cache; and

otherwise;

if one or more entries of the summary page cache are empty, store the retrieved summary page to an empty entry of the summary page cache and move the retrieved summary page to the head end of the linked list of the summary page cache;

otherwise, if all entries of the summary page cache are full;

purge the entry at the tail end of the linked list of the summary page cache;

store the retrieved summary page to the purged entry; and

move the retrieved summary page to the head end of the linked list of the summary page cache.

19. The invention of claim 17, wherein the storage device is configured to have one or more wear-level units, each wear-level unit having a corresponding summary page cache.

20. The invention of claim 17, wherein the apparatus is implemented in a monolithic integrated circuit chip.