Startup reconstruction of logical-to-physical address translation data for solid state disks

• US 8,301,861 B2
• Filed: 04/29/2010
• Issued: 10/30/2012
• Est. Priority Date: 09/23/2009
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Reiter, Randy, Swatosh, Timothy, Hempstead, Pamela, Hicken, Michael
• Primary Examiner(s): Dudek, Jr., Edward
• Assistant Examiner(s): DARE, RYAN A
• Application Number:
  US12/769,910
• Publication Number:
  US 20110072199A1
• Time in Patent Office: 915 Days
• Field of Search: None
• US Class Current: 711/170
• 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 reconstruction of logical-to-physical address mapping data for one or more sectors of a storage device at startup of a media controller. The sectors of the storage device are organized into blocks and superblocks and the address mapping data is stored in a volatile memory. At a startup condition of the media controller, a buffer layer module of the media controller allocates space in the volatile memory for one or more logical-to-physical address mapping data structures. A media layer module of the media controller determines a block type of each block of the storage device and places each block of the storage device into corresponding groups based on the determined block type of each block. The one or more blocks of each group are processed, and one or more address mapping data structures for the storage device are constructed in the allocated space in the volatile memory.

Claims

1. A method of reconstructing, by a media controller, logical-to-physical address mapping data for one or more sectors of a storage device, the sectors of the storage device organized into blocks and superblocks and the address mapping data stored in a volatile memory, the method comprising:

at a startup condition of the media controller;

allocating, by a buffer layer module of the media controller, space in the volatile memory for one or more logical-to-physical address mapping data structures;

determining, by a media layer module of the media controller, a block type of each block of the storage device;

grouping, by the media layer module, each block of the storage device into corresponding groups based on the determined block type of each block;

processing, by the media layer module, the one or more blocks of each group;

constructing, by the media layer module, one or more address mapping data structures for the storage device in the allocated space in the volatile memory,

wherein the address mapping data structures comprise;

an active block table (ABT) of the storage device, wherein the ABT stores a location of a currently active block in each superblock;

a page global directory (PGD) of the storage device, wherein the PGD stores i) a pointer to a summary page associated with each Superblock and ii) an ABT pointer to a location of the ABT for the superblock;

a free block list of the storage device, wherein the free block list includes pointers to erased blocks; and

a bad block list of the storage device, wherein the bad block list includes pointers to failed blocks.

2. The method of claim 1, wherein the step of determining a block type of each block of the storage device comprises:

reading a block type from a spare area of a predetermined page of each block;

if the block type was read successfully;

determining a host logical block address (LBA), a media logical sector number (LSN) of the block, and a block type of the block;

otherwise;

erasing the block and, if the block was erased successfully;

adding the block to the free block list of the storage device; and

updating the block type for the block, indicating that the block is a free block;

otherwise;

adding the block to the bad block list of the storage device; and

updating the block type for the block, indicating that the block is a bad block.

3. The method of claim 2, wherein the step of determining, based on at least one of the determined host LBA and media LSN, a block type of the block, comprises:

determining, if the host LBA of the block is within a predefined range, that the block is a data block;

otherwise;

determining, if the media LSN is equal to a predefined value, that the block is a map block, wherein a map block is reserved for storing a summary page of a summary page superblock;

determining, if the media LSN is equal to an LSN in a reserved sector range of the storage device, that the block is a summary block, wherein a summary block is reserved for storing summary pages of a superblock;

determining, if the media LSN is equal to an LSN in an anchor sector range of the storage device, that the block is an anchor block, wherein an anchor block is reserved to store elements of the firmware of the media controller;

otherwise, determining that the block type is unrecognized.

4. The method of claim 1, wherein the step of grouping each block of the storage device into corresponding groups based on the determined block type of each block, comprises:

if the current block is a summary block;

scanning a first page of the summary block determine a sequence number and superblock associated with the page, wherein the sequence number represents the order in which the block was written;

comparing the sequence number of the block to a sequence number of an active block of the superblock, the active block sequence number stored in PGD of the storage device;

if the sequence number of the summary page stored in the PGD satisfies a predefined relationship with the sequence number of the summary page, the PGD is up-to-date;

otherwise, the PGD is updated to point to an address of the summary page; and

scanning subsequent pages of the summary block, if present.

5. The method of claim 1, wherein the step of grouping each block of the storage device into corresponding groups based on the determined block type of each block, comprises:

if the current block is a data block;

determining whether the current block is an active block of the corresponding superblock;

if the current block is the active block;

locating a last written page of the active block; and

updating the ART of the storage device to point to a next free page of the active block;

otherwise;

scanning a first page of the data block determine a sequence number and superblock associated with the page, wherein the sequence number represents the order in which the block was written;

comparing the sequence number of the block to a sequence number of an active block of the superblock, the active block sequence number stored in the POD of the storage device;

if the sequence number of the page stored in the PGD satisfies a predefined relationship with the sequence number of the data page, the PGD is up-to-date;

otherwise, the PGD is updated to point to an address of the data page; and

scanning subsequent pages of the data block, if present.

6. The method of claim 5, wherein if the current block is determined to be the active block of the superblock, comprises:

determining whether a number free pages left in the active block has reached a minimum threshold;

if the minimum threshold has been reached;

allocating a new active block for the superblock;

updating a corresponding summary page of the superblock to point to the new active block;

updating the active block table of the superblock to point to the new active block.

7. The method of claim 1, wherein the step of grouping each block of the storage device into corresponding groups based on the determined block type of each block, comprises:

if the current block is a map block;

locating a last written page of the map block; and

updating the PGD of the storage device to point to the last written page of the map block.

8. 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 reconstructing, by a media controller, logical-to-physical address mapping data for one or more sectors of a storage device, the sectors of the storage device organized into blocks and superblocks and the address mapping data stored in a volatile memory, the method comprising:

at a startup condition of the media controller;

allocating, by a buffer layer module of the media controller, space in the volatile memory for one or more logical-to-physical address mapping data structures;

determining, by a media layer module of the media controller, a block type of each block of the storage device;

grouping, by the media layer module, each block of the storage device into corresponding groups based on the determined block type of each block;

processing, by the media layer module, the one or more blocks of each group;

constructing, by the media layer module, one or more address mapping data structures for the storage device in the allocated space in the volatile memory,

wherein the address mapping data structures comprise;

an active block table (ABT) of the storage device, wherein the ABT stores a location of a currently active block in each superblock;

a page global directory (PGD) of the storage device, wherein the PGD stores i) a pointer to a summary page associated with each Superblock and ii) an ABT pointer to a location of the ABT for the superblock;

a free block list of the storage device, wherein the free block list includes pointers to erased blocks; and

a bad block list of the storage device, wherein the bad block list includes pointers to failed blocks.

9. The non-transitory machine-readable storage medium of claim 8, wherein the step of determining a block type of each block of the storage device comprises:

reading a block type from a spare area of a predetermined page of each block;

if the block type was read successfully;

determining a host logical block address (LBA), a media logical sector number (LSN) of the block, and a block type of the block;

otherwise;

erasing the block and, if the block was erased successfully;

adding the block to the free block list of the storage device; and

updating the block type for the block, indicating that the block is a free block;

otherwise;

adding the block to the bad block list of the storage device; and

updating the block type for the block, indicating that the block is a bad block.

10. The non-transitory machine-readable storage medium of claim 9, wherein the step of determining, based on at least one of the determined host LBA and media LSN, a block type of the block, comprises:

determining, if the host LBA of the block is within a predefined range, that the block is a data block;

otherwise;

determining, if the media LSN is equal to a predefined value, that the block is a map block, wherein a map block is reserved for storing a summary page of a summary page superblock;

determining, if the media LSN is equal to an LSN in a reserved sector range of the storage device, that the block is a summary block, wherein a summary block is reserved for storing summary pages of a superblock;

determining, if the media LSN is equal to an LSN in an anchor sector range of the storage device, that the block is an anchor block, wherein an anchor block is reserved to store elements of the firmware of the media controller;

otherwise, determining that the block type is unrecognized.

11. The non-transitory machine-readable storage medium of claim 8, wherein the step of grouping each block of the storage device into corresponding groups based on the determined block type of each block, comprises:

if the current block is a summary block;

scanning a first page of the summary block determine a sequence number and superblock associated with the page, wherein the sequence number represents the order in which the block was written;

comparing the sequence number of the block to a sequence number of an active block of the superblock, the active block sequence number stored in PGD of the storage device;

if the sequence number of the summary page stored in the PGD satisfies a predefined relationship with the sequence number of the summary page, the PGD is up-to-date;

otherwise, the PGD is updated to point to an address of the summary page; and

scanning subsequent pages of the summary block, if present.

12. The non-transitory machine-readable storage medium of claim 8, wherein the step of grouping each block of the storage device into corresponding groups based on the determined block type of each block, comprises:

if the current block is a data block;

determining whether the current block is an active block of the corresponding superblock;

if the current block is the active block;

locating a last written page of the active block; and

updating the ABT of the storage device to point to a next free page of the active block;

otherwise;

scanning a first page of the data block determine a sequence number and superblock associated with the page, wherein the sequence number represents the order in which the block was written;

comparing the sequence number of the block to a sequence number of an active block of the superblock, the active block sequence number stored in the POD of the storage device;

if the sequence number of the page stored in the PGD satisfies a predefined relationship with the sequence number of the data page, the PGD is up-to-date;

otherwise, the POD is updated to point to an address of the data page; and

scanning subsequent pages of the data block, if present.

13. The non-transitory machine-readable storage medium of claim 12, wherein if the current block is determined to be the active block of the superblock, comprises:

determining whether a number free pages left in the active block has reached a minimum threshold;

if the minimum threshold has been reached;

allocating a new active block for the superblock;

updating a corresponding summary page of the superblock to point to the new active block;

updating the active block table of the superblock to point to the new active block.

14. The non-transitory machine-readable storage medium of claim 8, wherein the step of grouping each block of the storage device into corresponding groups based on the determined block type of each block, comprises:

if the current block is a map block;

locating a last written page of the map block; and

updating the PGD of the storage device to point to the last written page of the map block.

15. A media controller for reconstructing, at startup of the media controller, logical-to-physical address mapping 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 volatile memory for storing one or more logical-to-physical address mapping data structures;

a buffer layer module of the media controller for allocating space in the volatile memory for the one or more logical-to-physical address mapping data structures;

a media layer module of the media controller for i) determining a block type of each block of the storage device, ii) grouping each block of the storage device into corresponding groups based on the determined block type of each block, iii) processing the one or more blocks of each group, and iv) reconstructing the one or more address mapping data structures for the storage device in the allocated space in the volatile memory,

wherein the address mapping data structures comprise;

an active block table (ABT) of the storage device, wherein the ABT stores a location of a currently active block in each superblock;

a page global directory (PGD) of the storage device, wherein the PGD stores i) a pointer to a summary page associated with each Superblock and ii) an ABT pointer to a location of the ABT for the superblock;

a free block list of the storage device wherein the free block list includes pointers to erased blocks; and

a bad block list of the storage device, wherein the bad block list includes pointers to failed blocks.

16. The media controller of claim 15, wherein the storage device is divided into one or more separate physical spaces, comprising:

an anchor space adapted to store data that must be stored in particular physical blocks;

a data space adapted to store user data; and

a reserved space adapted to store logical-to-physical address mapping data,

wherein the anchor space and the reserved space are not accessible by a host device.

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