Logical-to-physical address translation for solid state disks

• US 8,219,776 B2
• Filed: 12/21/2009
• Issued: 07/10/2012
• 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: Forhan, Carl, Hempstead, Pamela, Hicken, Michael, Reiter, Randy, Swatosh, Timothy
• Primary Examiner(s): Savla, Arpan P.
• Application Number:
  US12/643,471
• Publication Number:
  US 20110072194A1
• Time in Patent Office: 932 Days
• Field of Search: 711/103, 711170-171, 711202-203, 711206-209, 365/185.33
• US Class Current: 711/202
• 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 logical-to-physical address translation for data stored on a storage device having sectors organized into blocks and superblocks. A flash translation layer maps a physical address in the storage device to a logical sector address. The logical sector address corresponds to mapping data that includes i) a page index, ii) a block index, and iii) a superblock number. The mapping data is stored in at least one summary page corresponding to the superblock containing the physical address. A block index and a page index of a next empty page in the superblock are stored in a page global directory corresponding to the superblock. A block index and a page index of the at least one summary page and the at least one active block table for each superblock are stored in at least one active block table of the storage device.

Claims

1. A method of transferring data between one or more sectors of a storage device and an external device, the sectors of the storage device organized into blocks and superblocks, the method comprising:

at a flash translation layer;

mapping a physical address in the storage device to a logical sector address, wherein the logical sector address corresponds to mapping data comprising;

i) a page index, ii) a block index, and iii) a superblock number of the storage device;

storing the mapping data in at least one summary page corresponding to the superblock containing the physical address;

storing one or more page offsets of an active block in the superblock in at least one active block table corresponding to the superblock;

storing a block index and a page index of the at least one summary page and an address of the at least one active block table, for each superblock of the storage device, in a page global directory corresponding to the storage device;

receiving a data request, the data request comprising i) a starting logical sector address and ii) a span of sectors to be accessed; and

at the flash translation layer;

identifying for the data request, based on the starting logical sector address, the corresponding i) superblock number, ii) block index and iii) page index of the requested data within the storage device;

locating, from the page global directory of the storage device, the at least one active block table and the summary page corresponding to the superblock number; and

iteratively identifying physical addresses for sectors in the span of sectors to be accessed based on i) the at least one active block table of the superblock, if the physical address is in an active block of the superblock, otherwise, ii) the summary page of the superblock, based on the block index and page index.

2. The method of claim 1, further comprising the steps of:

at a buffer layer;

segmenting the span of sectors to be accessed into a plurality of chunks, wherein each chunk corresponds to at least one sector of the storage device;

determining a number of chunks to be transferred between the storage device and the external device; and

allocating buffer space in a buffer corresponding to the number of chunks to be transferred.

3. The method of claim 2, further comprising the steps of:

at a host layer;

receiving the data request from one or more external devices via a communication link; and

transferring the data of the request between the communication link and the storage device via the allocated buffer space.

4. The method of claim 3, wherein a first set of one or more chunks are transferred between the communication link and the allocated buffer space, and a second set of one or more chunks are transferred between the allocated buffer space and the storage device in parallel.

5. The method of claim 1, further comprising the steps of:

if no active block was previously allocated for the superblock;

allocating an active block for the superblock;

generating a default active page index for the active block; and

updating the page global directory entry for the superblock to point to the active block.

6. The method of claim 1, further comprising:

determining if the at least one active block of the superblock contains more data than a predetermined threshold;

if the active block does contain data in excess of the predetermined threshold;

locating, from a page global directory of the storage device, the at least one summary page corresponding to the superblock;

allocating a new active block for the superblock;

updating the at least one active block table to point to a first available physical address in the new active block;

updating the at least one summary page to point to the at least one updated active block table; and

updating the page global directory to point to the updated summary page and updated at least one active block table;

otherwise, if the active block does not contain data in excess of the predetermined threshold;

update the at least one active block table to point to the first available physical address in the active block.

7. The method of claim 1, further comprising:

updating, during predetermined times, the at least one summary page for each superblock, wherein the step of updating comprises;

reading, in last-in, first-out order, the at least one active block table of the storage device;

merging, if data stored in the at least one active block table is more recent than data stored in the summary page for each superblock, the data in the at least one active block table and the data in the at least one summary page into at least one updated summary page;

saving the at least one updated summary page; and

purging at least part of the at least one active block table.

8. The method of claim 7, wherein, at startup of the storage device, the data in the at least one active block table is more recent than the data in the at least one summary page if a sequence number of the data in the page global directory is higher than the sequence number of data in the at least one summary page.

9. The method of claim 1, wherein, for the method, the storage device comprises flash memory, the flash memory comprising one or more flash memory dies.

10. The method of claim 1, wherein the storage device is configured to have one or more wear-level units, each wear-level unit having a corresponding page global directory.

11. The method of claim 1, wherein the at least one summary page corresponding to each superblock of the storage device are stored in a separate, reserved superblock of the storage device.

12. The method of claim 1, wherein the page global directory of the storage device is stored in a reserved superblock of the storage device.

13. The method of claim 1, wherein at least one active block table corresponding to each superblock of the storage device is stored in random access memory (RAM).

14. The method of claim 1, wherein the method is implemented by a machine executing program code encoded on a machine-readable storage medium.

15. The method of claim 1, wherein the data request is one of:

read, write, skip-read, and skip-write.

16. The method of claim 1, wherein method performs the steps at startup of the storage device.

17. An apparatus for transferring data between one or more sectors of a storage device and at least one external device via a communication link, the sectors of the storage device organized into blocks and superblocks, the apparatus comprising:

a host layer module adapted to send data to, and receive data from, the communication link, wherein data requests are received from the at least one external device, and wherein the data requests comprise i) a starting logical sector address and ii) a span of sectors to be transferred;

a buffer for storing data to be transferred to or from the storage device;

a buffer layer module for i) managing the buffer and ii) allocating storage space in the buffer corresponding to the span of sectors to be transferred;

at least one active block table corresponding to each superblock, the active block table for storing one or more page offsets of an active block in the corresponding superblock;

at least one summary page for storing mapping data corresponding to each superblock, wherein the mapping data maps a physical address in the storage device to a logical sector address, the mapping data comprising;

i) a page index, ii) a block index, and iii) a superblock number;

a page global directory for storing a block index and a page index of the at least one summary page and an address of the at least active block table for each superblock of the storage device;

a flash translation layer module for i) identifying for the data request, based on the starting logical sector address, the corresponding page index, block index, and superblock number, ii) maintaining the data stored in the page global directory, the active block tables, and the summary pages, and iii) iteratively identifying physical addresses for sectors in the span of sectors based on i) the active block table of the superblock, if the physical address is in the active block of the superblock, otherwise, ii) the summary page of the superblock, based on the block index and page index.

18. The apparatus of claim 17, wherein the storage device comprises at least one flash memory.

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