Patent Publication Number: US-9405668-B1

Title: Data storage device initialization information accessed by searching for pointer information

Description:
BACKGROUND 
     Data storage devices are ubiquitous in everyday life. For example, nearly all computers have hard disk drives (HDD) or solid state memory for non-volatile storage. There may be multiple types of storage medium, including removable media such as Compact Disk (CD), Digital Versatile Disk (DVD) or Universal Serial Bus (USB) devices for information storage. It is not uncommon for a system to employ multiple types of storage medium. 
     Many types of data storage devices incorporate programming initialization information needed by the data storage device to operate. It is advantageous to store this information on the storage medium contained in the storage device itself. A small resident program may be used at initialization time to read the initialization information for the data storage device to become fully operational. Some systems may use a boot block that is stored in a permanent fixed location that can be accessed to get the needed information to locate the initialization information. 
     The present invention overcomes the limitations of the prior art and provides a method of initializing a data storage device robustly. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a data storage device according to one embodiment. 
         FIG. 2  illustrates initialization information areas, pointer areas, and initialization pointers according to one embodiment. 
         FIG. 3  is a flow chart illustrating a process for initialization of a data storage device according to one embodiment of the invention. 
         FIG. 4  is a flow chart illustrating a process for updating initialization information according to one embodiment of the invention. 
         FIG. 5  illustrates a conceptual overview of a solid state storage device according to one embodiment. 
         FIG. 6  illustrates a solid state drive according to one embodiment. 
         FIG. 7  illustrates a disk drive according to one embodiment. 
         FIG. 8  illustrates a shingle formatted HDD according to one embodiment. 
     
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
       FIG. 1  illustrates a data storage device  10  according to one embodiment of the invention. The data storage device  10  may be any device containing a processor  11  and a non-volatile storage medium  12 . The non-volatile storage medium  12  may be incorporated as part of the device  10 , for example as memory chips, magnetic disks, NAND memory, or as peripherals contained on a system bus. 
       FIG. 2  illustrates a non-volatile memory  200  of a data storage device according to one embodiment of the invention. As will be described later, the non-volatile memory  200  may comprise an HDD  12  and/or SSD  13 —or any other appropriate non-volatile memory medium—in the data storage device  100  shown in  FIG. 1 . 
     The non-volatile memory  200  comprises first initialization information area (INA)  230  and an optional INA  240 . First INA  230  includes first initialization information (INI)  235  and, in one embodiment, first INA  230  may have additional space  236  to store multiple INIs. The optional INA  240  includes second INI  245  and additional space  246 . Although shown as being smaller for ease of depiction, additional spaces  236  and  246  may be, and generally will be, physically larger than first and second INIs  235  and  245 , respectively. For instance, INA  230  and  240  may comprise numerous instances of initialization information as various versions of initialization information are written to INA  230  and  240 . Initialization pointers (INP) first INP  210  and second INP  210 ′ are stored in a pointer area (PA)  220 . The PA  220  may comprise multiple INPs as illustrated by blocks  221 - 229 . Non-volatile memory  200  will typically also have memory  290  for system and user data. 
     INI may comprise information used by the data storage device for a variety of purposes, including for example system program code, system data, system hardware configuration information such as servo or channel settings, user hardware or firmware settings or preferences, file information, system resource allocation, permissions, factory information, logical-to-physical mapping information, defect information, lookup tables, error information, wear leveling information or other information that may be needed to bring the data storage device to a fully operational condition. Information in the INI may be changed at any time due to normal operation or changes in system or user requirements. 
     In this embodiment, non-volatile memory  200  comprises data that is addressed by the processor  11  according to physical block address (PBA). For clarity, memory contents are illustrated singly, but may comprise one or more physical memory locations addressed through PBAs, such as sectors or pages. In some embodiments, PBAs may be mapped to logical block addresses (LBAs) that may be used for addressing by a host connected to the data storage device  100 . LBAs may be consecutively numbered, but mapped to non-consecutive physical locations with non-consecutive PBAs. Such mapping schemes are advantageous for HDD and SSD storage devices according to some embodiments. It will be apparent to one of skill in the art that any such mapping schemes may be used without departing from the spirit of the invention. The expression PBA may therefore include embodiments with LBA address mapping. 
     First INP  210  shown in block  221  of PA  220  comprises first PBA pointer  211 , first sequence identifier  212 , and first metadata  213 . Second INP  210 ′ shown in block  226  of PA  220  comprises second PBA pointer  211 ′, second sequence identifier  212 ′, and second metadata  213 ′. INPs stored in PA  220  may be in any order. For example, in one embodiment, block  221  is written with a first INP and then block  222  is written with the next INP and so forth. When all of the blocks  221 - 229  are full, the next INP may be written to the least-recently used block (i.e., block  221 ) and the process continues as before. As will be discussed further below, PA  220  may comprise one or more tracks of an HDD or, in another embodiment, PA  220  may comprise one or more blocks of non-volatile semiconductor memory. 
     First PBA pointer  211  comprises the PBA of first PBA starting location  231 . First PBA location  231  is the starting address where first INI  235  is stored within INA  230 . In another embodiment, first PBA pointer  211  may comprise more than one PBA. For example, first PBA pointer  211  may point to two or more different types of INIs that are located at different PBAs. When any of the different types of INIs are updated, a new PBA pointer may be written to point to all of the current INI locations. 
     First sequence identifier  212  comprises information related to the order that first INP  210  was written into PA  220 . Sequence identifiers may be any data that can be used to determine that an INP has been written after other INPs in the PA or signify a version or revision of an INP. Sequence identifiers may comprise for example: a revision number, a sequence string, a sequence number, a time stamp, and/or a validation code. 
     First INP  210  may optionally comprise first metadata  213 . Metadata may be for example: additional pointers, code, parameters, or initialization information. Embodiments of the invention may find the optional metadata space useful for initialization and the invention is not limited by the contents or absence of metadata. 
     PA  220  may comprise more than one INP, and in one embodiment of the invention, updating INI may be performed by writing second INI  245  and second INP  210 ′. The contents of second INP  210 ′ follow the same description as first INP  210 , however, second INP  210 ′ comprises more recent information. Second PBA pointer  211 ′ comprises a pointer that now points to second PBA starting location  241  for second INI  245 . Second sequence identifier  212 ′ comprises contents that can be recognized as more recent than all other sequence identifiers contained in PA  220 . Optional second metadata  213 ′ may comprise updated metadata. In other embodiments, second INI  245  may be in first INA  230  or in a separated location, such as a separate physical medium. The separate physical medium may be a different volume, a different disk surface, or a different semiconductor memory, for example. 
       FIG. 3  is a flow chart of a process  300  for initializing of a data storage device according to one embodiment of the invention. Beginning at block  305 , typically performed after power-on or reset operations, a processor will read the INPs contained in the PA. In block  310 , the processor will examine the sequence identifiers contained in each INP to determine which is the most recent. In block  330 , the processor uses the PBA pointer from the most recent INP as an index to the PBA starting location of most recent INI. In block  340 , the processor reads the data beginning at the PBA starting location and performs initialization. Once initialization has completed or become interrupted, the process checks to see if the initialization process was successful in block  350 . If the initialization was successful, the operation is completed. If the initialization was not successful, the process begins recovery in block  360 . In block  360 , the process will use a less recent—typically the next most recent—INP and PBA pointer, and return to block  340  to index to the previous INI and perform initialization using the selected INI. In the event of further failures, additional prior INPs may be used to access older INIs by repeating blocks  340 ,  350 , and  360  until a successful initialization is achieved. In other embodiments, the process may stop and/or an error message may be provided to the user or host after a certain number of unsuccessful initialization attempts. 
       FIG. 4  is a flow chart of a process  400  for updating initialization information according to one embodiment of the invention. For example, new initialization information may be stored in the first INA  230  when an updated mapping table of LBAs to PBAs is flushed to the non-volatile storage due to recent user data writes. Beginning in block  410 , a processor will read the INPs contained in the PA. In block  420 , the processor will examine the sequence identifiers contained in each INP to determine which is the most recent. In block  430 , the processor uses the PBA pointer from the most recent INP as an index to determine the PBA starting location of most recent INI. In block  440 , the processor uses the PBA starting location to select a location to put the new INI. In some embodiments, the new INI location may be in optional PA  240  or a different medium, page or erase block. In block  450 , the processor writes the new INI to the selected location. In block  460 , the processor creates a new most recent PBA pointer, which includes a most recent sequence identifier. In block  470 , the processor writes a new INP into any available location in the PA. For example, in one embodiment, the new INP may be written to the next available location in PA  220  of  FIG. 2  or may overwrite the least-recently used location in PA  220  if all of the locations have been used. 
     In another embodiment, rather than perform blocks  410 ,  420 , and  430 , the processor may store the location of the most recent initialization information and/or the most recent initialization pointer in volatile memory after determining that initialization was successful in block  350  of  FIG. 3 . This information can then be quickly accessed for use in block  440 . In this embodiment, each time new initialization information and/or a new initialization pointer is written to non-volatile memory, the new locations would be stored on volatile memory for later use in block  440  of  FIG. 4 . 
       FIG. 5  illustrates a conceptual overview of solid state memory  500  according to one embodiment, which may be in SSD  62  shown in data storage device  60  in  FIG. 6 . Solid state memory  500  may comprise multiple physical memory devices mapped to PBAs of data storage device  100 . Semiconductor memories  505 ,  505 ′ and  505 ″ in solid state memory  500  are shown as an example, and more or less such devices may be found in data storage device  60 . 
     Semiconductor memory  505  may comprise any non-volatile semiconductor memory, for example, NAND flash memory. In one embodiment, semiconductor memory  505  may be divided into erase blocks  510 ,  520 ,  530 ,  540 , and extending to ending erase block  599 . In this embodiment, an erase block is a portion of the semiconductor memory  505  that can be written (sometimes referred to as programming) and erased independently from all other erase blocks. 
     In one embodiment, one or more erase blocks may be divided into pages. Erase block  510  is shown divided into page  1 , page  2 , page n, and up to page m shown as  511 ,  512 ,  513 , and  514  respectively. Erase block  520  is similarly divided into page  1 , page  2 , page n and up to page m shown as  521 ,  522 ,  523 , and  524  respectively. All the erase blocks in semiconductor memory  505  may be similarly divided into pages. In some embodiments with NAND memory, a page may be a portion of an erase block that can be accessed by one or more PBAs and can be written as a unit. In order to rewrite a page that has been previously written, the entire erase block must typically be erased first. If a hazardous event such as power loss occurs during writing or erasing of an NAND memory, loss of data may occur. If the writing or erasing was part of updating INI or INP, the data loss can be catastrophic if not handled properly. 
     Some embodiments of the invention may prevent such catastrophic loss by writing updated INI and INP into different erase blocks rather than overwriting prior INI and INP. In one embodiment, each update may be written alternately to two erase blocks. In a further embodiment, each update may be written to different pages of an erase block, and in yet another embodiment, updates may be written to different pages of alternating erase blocks. The advantage of maintaining older versions of INI and INP is that they may be used for restore operations in the event that an erase block or page becomes corrupted or the new update is inoperable. 
       FIG. 7  illustrates a data storage device  70  according to one embodiment of the invention. Data storage device  70  includes a processor  71 , and a disk drive  72 . The disk drive  72  may comprise one or more magnetic disks for storing data and one or more heads for accessing the data on the disk surface. Disk drive  72  may also comprise non-volatile semiconductor memory, sometimes referred to as a hybrid drive. The processor  71  may be tightly coupled with the disk drive  72  by being included on a PCBA of the disk drive  72  or the processor may communicate remotely with the disk drive  72  over an interface. 
       FIG. 8  illustrates a non-volatile memory  800  similar to the non-volatile memory  200  illustrated in  FIG. 2  according to one embodiment. The non-volatile memory  200  may be embodied in a disk drive  62  that is written in a shingle format, which is a method of writing adjacent concentric tracks of data with wide tracks using a write transducer that has a writer width greater than the final track width. In general, a first track is written as a wide track, and when an adjacent second track is written, it partially overwrites a fraction of the first track leaving a narrow first track and a wide second track. Subsequent writes to adjacent tracks similarly overwrite a fraction of the previous track, leaving behind multiple narrow tracks. The resulting format has higher track density, but has disadvantages for non-sequential or random writing. 
     In one embodiment, multiple tracks may be written in order from an inner diameter (ID) to an outer diameter (OD) direction of a recording disk, or vice versa. In a band of tracks written in a shingle format, it is typically not possible to write a single track without overwriting adjacent tracks, and various methods have been developed to overcome this potential constraint. Some methods incorporate indirect addressing to break the fixed connection between physical and logical addresses by using address mapping tables. Shingle format and indirect addressing may increase the frequency of updates to mapping tables due to the need to consolidate shingled tracks and recover storage using methods commonly referred to as garbage collection. In addition, since the initialization information itself may employ shingle format, the frequency and duration of risk due to failure or power loss increases substantially. 
     The non-volatile memory  800  in  FIG. 8  comprises PA  820  and INPs  821  through  829 , however, the number of INPs and/or initialization information areas are not limited. First INA  830  comprises first INI  835  and additional space  836 . Optional second INA  840  comprises second INI  845  and additional space  846 . System and user storage is shown in block  890 . Guard bands  801 ,  802 ,  803 , and  804  are provided between the PA  830 , first INA  830 , optional INA  840 , and system and user storage  890 . In one embodiment, guard bands  801 ,  802 ,  803 , and  804  are at least as wide as the write transducer writer width. In another embodiment, guard bands  801 ,  802 ,  803 , and/or  804  may be wide enough to prevent adjacent track interference or erasure due to stray magnetic flux lines that occur when writing tracks near the area to be protected. 
     In one embodiment, PA  820  comprises a single track of data. In a further embodiment, PA  820  may be located near the ID of at least one of the disk surfaces. Guard bands  801  and  802  are provided to prevent overwriting of INPs when adjacent tracks are written in shingle format. For example, without guard band  802 , if the first INI  835  or any of first INA  830  is written, a wide shingle write transducer may overwrite part of PA  820 . Similarly, if PA  820  were written, part of first INA  830  may be overwritten. Guard bands  801 ,  802 ,  803 , and  804  provide enough space for writing any of PA  820 , first INA  830 , optional INA  840 , and system and user storage  890  without overwriting adjacent areas. 
     Another advantage of providing guard bands  801  and  802  on each side of PA  820  is that, in some embodiments, PA  820  can operate in a conventional non-shingle format that provides non-sequential and random writing performance. 
     Some embodiments of the present invention may provide for robust initialization of a data storage device and updating of initialization of INI. In order to protect INI from loss from catastrophic events such as power loss, some embodiments of the invention allow for updating a system while protecting old initialization information without the need to update or preserve any fixed storage location. Also, replacing a fixed boot pointer with a pointer search area permits updating INI and pointers with code that can be protected during updates and allow recovery to a prior initialization pointer and initialization information. 
     Although the foregoing has been described in terms of certain embodiments, other embodiments will be apparent to those of ordinary skill in the art from the disclosure herein. For example, in an alternative embodiment, operations may be performed concurrently, rather than sequentially, thereby improving performance. In another embodiment, the examination of pointers and initialization may be performed in a hardware implementation and performed automatically without software involvement. A processor may include many alternatives, such as a microprocessor, microcontroller, sequencer, or state machine. Processors may also be local in the data storage device or remotely, such as in a host computer. Alternatives to embody the invention in combinations of hardware, firmware, and/or software running on a processor, or as a hardware implementation that is reconfigurable to operate in multiple modes would be design choices apparent to those of ordinary skill in the art. As a consequence, the system and method of the present invention may be embodied as software which provides such programming, such as a set of instructions and/or metadata embodied within a computer readable medium. The described embodiments have been presented by way of example only and are not intended to limit the scope of the disclosure. Indeed, the novel methods and systems described herein may be embodied in a variety of other forms without departing from the spirit thereof. Thus, the invention is not limited by any preferred embodiments, but is defined by reference to the appended claims.