Sector translation layer for hard disk drives

An apparatus having a memory and a controller is disclosed. The memory may have a write head and sectors in tracks. The controller may have a sector map and a translation map and may be configured to (i) receive a write command having a logical block address and a range value, (ii) examine the sector map to find a sector sequence (a) marked free, (b) about to reach the write head and (c) at least as long as the range value, (iii) write new data in the sector sequence, (iv) update the translation map to associate the logical block address of the write command with a physical address of the written sectors and (v) update the sector map according to the sectors written. Each entry in the sector map generally corresponds to a respective sector and indicates whether the respective sector contains valid data or is free.

FIELD OF THE INVENTION

The present invention relates to hard disk drives generally and, more particularly, to a method and/or architecture for a sector translation layer for hard disk drives.

BACKGROUND OF THE INVENTION

Accessing a sector of a conventional rotating media to read or write data involves delays called a seek time delay and a rotational latency delay. The seek time delay measures a time for a head assembly on an actuator arm to travel to a track of a disk platter where the data is read or written. The rotational latency is a delay waiting for the rotation of the disk platter to bring the requested sector to the head assembly. Both types of delay impact data transfer performance. The impact can be significant during random reads and/or writes.

It would be desirable to implement a sector translation layer for hard disk drives.

SUMMARY OF THE INVENTION

The present invention concerns an apparatus having a memory and a controller. The memory may have a write head and sectors in tracks. The controller may have a sector map and a translation map and may be configured to (i) receive a write command having a logical block address and a range value, (ii) examine the sector map to find a sector sequence (a) marked free, (b) about to reach the write head and (c) at least as long as the range value, (iii) write new data in the sector sequence, (iv) update the translation map to associate the logical block address of the write command with a physical address of the written sectors and (v) update the sector map according to the sectors written. Each entry in the sector map generally corresponds to a respective sector and indicates whether the respective sector contains valid data or is free.

The objects, features and advantages of the present invention include providing a sector translation layer for hard disk drives that may (i) improve write performance compared with conventional hard disk drives, (ii) incorporate a limited amount of NAND or NOR flash memory for mapping purposes, (iii) reduce a seek time to a writable sector, (iv) reduce rotational latency delays, (v) provide a single controller that works with both the flash and the rotating media, (vi) write to non-sequential sectors, (vii) write to multiple platter surfaces simultaneously and/or (viii) be implemented with one or more integrated circuits.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Embodiments of the present invention provide a sector translation layer for hard disk drives. The architecture generally implements a “tightly coupled hybrid” solution, meaning a controller that works with nonvolatile memory for mapping purposes and at the same time writes in (on) a rotating media. The writes may be made in sequential and/or non-sequential sectors. The architecture may improve random write performance by reducing head movement prior to the writes. Furthermore, the hard disk drive may utilize multiple heads simultaneously (or concurrently) to actively write data in (on) multiple platter surfaces.

Referring toFIG. 1, a block diagram of an example implementation of an apparatus90in accordance with a preferred embodiment of the present invention is shown. The apparatus (or circuit, system, or device)90generally implements a computer having rotating storage media. The apparatus90generally comprises a block (or circuit)92and a block (or circuit)100. The circuit100generally comprises a block (or circuit)102and a block (or device)104. The circuits92to102may represent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry and/or one or more electronic design tools.

One or more signals (e.g., HOST I/O) may be exchanged between the circuit92and the circuit100. The signal HOST I/O may be a bidirectional signal that transfers host input/output information. The signal HOST I/O generally includes, but is not limited to, a logical address component and a range value used to access data in the circuit100, a host command component that controls the circuit100, a write data component that transfers write data from the circuit92to the circuit100and/or a read data component that transfers read data from the circuit100to the circuit92. One or more signals (e.g., CONTROL) may be exchanged between the circuit102and the device104. The signal CONTROL may be a bidirectional signal that transfers control information and feedback information. The signal CONTROL generally includes, but is not limited to, a physical address component used to access data in the device104, a memory command component that controls the device104(e.g., read or write commands) and/or one or more feedback components. A data signal (e.g., DATA) may be exchanged between the circuit102and the device104. The signal DATA may be a bidirectional signal. The signal DATA generally conveys data written to and/or read from the device104. Other signal components may be implemented to meet the criteria of a particular application.

The circuit92may implement a host circuit. The circuit92is generally operational to read from and write data to the device104via the circuit102. When reading or writing, the circuit92transfers a logical address value and a range value in the signal HOST I/O to identify which set(s) of data is(are) to be written to or read from the device104. The address generally resides in a logical address range of the circuit92.

The circuit92may use a logical block addressing scheme to specify locations of data blocks stored on storage devices, generally secondary storage systems such as hard disks (e.g., the device104). The logical block addressing scheme is generally a linear addressing scheme. The blocks may be located by an integer index, with an initial block being LBA0, a next block being LBA1, and so on.

The circuit100may implement a hard disk drive circuit. The circuit100is generally operational to store write data received from the circuit92via the signal HOST I/O. The circuit100may also be operational to send read data via the signal HOST I/O to the circuit92. In various embodiments, the circuit100is configured to communicate with the circuit92using one or more communications interfaces and/or protocols. According to various embodiments, one or more communications interfaces and/or protocols may comprise one or more of a serial advanced technology attachment (e.g., SATA) interface; a serial attached small computer system interface (e.g., serial SCSI or SAS interface), a peripheral component interconnect express (e.g., PCIe) interface; a Fibre Channel interface, an Ethernet Interface (such as 10 Gigabit Ethernet), a non-standard version of any of the preceding interfaces, a custom interface, and/or any other type of interface used to interconnect storage and/or communications and/or computing devices.

The circuit102may implement a controller circuit. The circuit102is generally operational to control reading from and writing to the device104in response to commands and logical addresses received from the circuit92via the signal HOST I/O. Control of the device104is generally accomplished using components of the signal CONTROL. Data may be exchanged with the device104in the signal DATA.

The device104may implement one or more rotating storage media. The device104is generally operational to store data in a nonvolatile condition. The data may be received from and sent to the circuit102in the signal DATA. Control of the storage operation may be implemented by the signal CONTROL. In various embodiments, the device104may implement magnetic media, optical media and/or magneto-optical media. Other types of storage media may be implemented to meet the criteria of a particular application.

The circuit102generally comprises a block (or circuit)120, a block (or circuit)122and a block (or circuit)124. The circuits120to124may represent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry and/or one or more electronic design tools. Additional circuitry may be implemented in the circuit102to meet the criteria of a particular application.

A signal (e.g., MAPS) may be exchanged between the circuit120and the circuit122. The signal MAPS may be a bidirectional signal that transfers a multi-layer address translation map and a physical address free sector map between the circuit120and the circuit122. A signal (e.g., INT) may be exchanged between the circuit120an the circuit124. The signal INT may be a bidirectional signal that transfers internal communications involving data and instructs between the circuit120and the circuit124for accessing the device104.

The circuit120may implement a processor circuit. The circuit120is generally operational to control reading to and writing from the device104. The circuit120may include an ability to encode the write data received from the circuit92. The resulting encoded write data may be stored in the device104. The circuit120may also include an ability to decode the read data received from the device104. The resulting decoded data may be presented to the circuit92via the signal HOST I/O and/or re-encoded and written back into the circuit120. The circuit120comprises one or more integrated circuits (or chips or die) implementing the controller of one or more drives, embedded storage, or other suitable control applications.

The circuit122may implement one or more nonvolatile (or persistent storage) memory circuits. According to various embodiments, the circuit122generally comprises one or more nonvolatile semiconductor devices (e.g., solid-state memories). The circuit122may be operational to store data in a nonvolatile condition. The circuit122is generally implemented as NAND flash memory, NOR flash memory, flash memory using polysilicon or silicon nitride charge storage cells, two-dimensional or three-dimensional nonvolatile memory, ferromagnetic memory, phase-change memory, racetrack memory, resistive random access memory, magnetic random access memory and similar types of memory devices and/or storage media. Other nonvolatile memory technologies may be implemented to meet the criteria of a particular application.

The circuit124may implement a storage media interface (I/F) circuit. The circuit124is generally operational to communicate with and control the device104. The circuit124may also be operational to communicate with the circuit120via the signal INT. The data is sent to and received from the circuit124via the signal DATA. A command component of the signal CONTROL may govern positioning of read/write heads in the device104. A position component of the signal CONTROL may provide a position of the read/write head to the circuit124. A speed component of the signal CONTROL generally controls a rotational speed of one or more disk platters of the device104.

Referring toFIG. 2, a detailed block diagram of an example implementation of the device104and the circuit124is shown. The circuit124generally comprises a block (or circuit)142, a block (or circuit)144, a block (or circuit)146, a block (or circuit)156and a block (or circuit)158. The device104generally comprises a block (or circuit)148, a block (or device)150, a block (or device)152and a block (or device)154. The circuits142to158may represent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry and/or one or more electronic design tools.

The signal DATA may be exchanged between the circuit146and the circuit148. The signal CONTROL generally comprises a signal (e.g., CMD), a signal (e.g., POS) and a signal (e.g., SPEED). The signal CMD may carry command information generated by the circuit156that controls the device152. The signal POS may convey position information from the device152to the circuit156. The signal SPEED may be a speed control signal generated by the circuit156that controls a rotational speed of the device154. The signal INT generally comprises a signal (e.g., WRITE DATA) and a signal (e.g., READ DATA). The signal WRITE DATA may be received by the circuit144from the circuit120. The signal WRITE DATA generally carries write data to be stored in (on) the device150through the circuit148. The signal READ DATA may be generated by the circuit144and transferred to the circuit120. The signal READ DATA may carry data read from the device150by the circuit148.

The circuit142may implement an interface controller. The circuit142is generally operational to control the interface between the circuit120and the circuits144and158. Controls may include, but are not limited to, commands to start and stop the device154and/or commands to position the device152. Information may include, but is not limited to, the position of the device152.

The circuit144may implement a read/write channel circuit. In a write mode, the circuit144is generally operational to format write data in a form suitable for storage in the device104. In a read mode, the circuit144may be operational to reformat the data read from the device104.

The circuit146may implement a preamplifier circuit. In the write mode, the circuit146is generally operational to amplify the write data received from the circuit144. In the read mode, the circuit146is generally operational to amplify the read data received from the device104.

The circuit148may implement one or more read/write head assemblies. Each head assembly148generally resides at the end of an arm pivotably attached to the device152. Each write head of each head assembly148is generally operational in the write mode to store the write data received in the signal DATA in the device150. In the read mode, each read head of each head assembly148is operational to read data from the device150.

The device150may implement one or more disk platters. Each platter150is generally operational to store data in (on) a nonvolatile medium. In various embodiments, each platter150may have two sides in which the data is stored. The data on the platter150generally comprises groups of magnetic signals that may be detected by the head assembly148when the head assembly148is properly positioned relative to the platter150.

The device152may implement a voice coil motor (e.g., VCM) circuit. The device152is generally operational to position the head assembly148in a radial direction along the surfaces of the platter150. The positioning of the head assembly148by the device152may be controlled by the signal MT. The actual position and/or velocity of the head assembly148may be reported by the device152in the signal POS.

The device154may implement a spindle motor circuit. The device154is generally operational to rotate the platter150at a speed (e.g., 5,400 to 10,000 revolutions per minute). Speed of the rotation may be controlled by the signal SPEED.

The circuit156may implement a motor controller. The circuit156is generally operational to generate the signal CMD and the signal SPEED to control the rotational speed of the platter150and the positioning of the head assembly148relative to the platter150.

The circuit158may implement a hard disk controller. The circuit158is generally operational to control generation of the signals that govern the reading to and writing from the device104. The circuit158may control operations of the device104through the circuit156. The circuit158may provide the position and/or velocity feedback to the circuit142.

In a typical read operation, the head assembly148may be accurately aligned by the circuit156and the device152to a desired data track on the platter150. The circuit156both positions the head assembly148in relation to the platter150and drives the spindle motor device154. The device154may spin the platter150at a determined spin rate (e.g., RPMs). The read channel circuit144may receive information from the circuit146and perform a data decode/detection process to recover the data (e.g., the signal READ DATA) stored by the platter150.

In operation, the head assembly148may be positioned adjacent a data track on the platter150. Magnetic signals representing data on the platter150may be sensed by the head assembly148as the platter150is rotated by device154. The sensed magnetic signals may be provided as a continuous, minute analog signal representative of the magnetic data on the platter150. The analog signal may be transferred from the head assembly148to the circuit144via the preamplifier circuit146. The circuit146is generally operable to amplify the analog signals accessed from the platter150. In turn, the read channel circuit144may decode and digitize the received analog signal to recreate the information originally written to the platter150. The data is provided as read data in the signal READ DATA.

In a typical write operation, the circuit144may receive write data (e.g., the signal WRITE DATA) and provide the write data to the circuit146in a form writable to the platter150. A write operation is substantially the opposite of the read operation with write data in the signal WRITE DATA being provided to the circuit144. The write data may subsequently be encoded and written to the platter150. In some embodiments, the circuit144is implemented as a separate integrated circuit.

In the logical block addressing scheme, sectors may be numbered as integer indexes. When mapped to CHS (cylinder-head-sector) tuples, the logical block address numbering generally starts with an initial cylinder, an initial head, and an initial sector in an initial track. Once the track is exhausted, numbering may continue to a next head, while staying in the initial cylinder. Once all of the sectors inside the initial cylinder are exhausted, the numbering generally continues to the next cylinder, and so on. Thus, the lower the logical block address value is, the closer the physical sector is to an outermost cylinder of the hard drive.

The CHS values may be mapped to the logical block addresses per formula 1 as follows:
LBA=(C×HPC+H)×SPT+(S−1),   (1)
where C, H and S may be the cylinder number, the head number, and the sector number, respectivly, LBA may be the logical block address, HPC may be a maximum number of heads per cylinder (usually reported by the disk drive, typically 16 for a 28-bit LBA) and SPT may be a maximum number of sectors per track (usually reported by the disk drive, typically 63 for the 28-bit LBA).

The logical block addresses may be mapped to the CHS values per formulae 2-4 as follows:
C=LBA÷(HPC×SPT),   (2)
H=(LBA÷SPT) mod HPC,   (3)
S=(LBA mod SPT)+1,   (4)
where the operation “mod” may be a modulo operation.

Consider an example translation where S may range from 1 to 63, H may range from 0 to 15 and C may range from 0 to 31. Since each platter has two sides, a total number of platters may be 8 and hence a total number of heads is 16. Example translations of several logical block address values into corresponding CHS values may be illustrated in Table I as follows:

Some common hard disk drives use a zone-bit recording (e.g., ZBR) arrangement. Without the zone-bit recording, an inner zone of the platter150generally has a higher bit density than an outer zone of the platter150. With zone-bit recording, as a distance from the center of the platter150increases, the number of sectors in a given angle increases. Various embodiments of the circuit100may be implemented to work with platters150that do not implement the zone-bit recording. Other embodiments of the circuit100may be implemented to work with platters150that implement the zone-bit recording.

Consider the following example where the platter does not implement the zone-bit recording. Since all of the heads of the head assembly148generally move together, a structure of the physical address may be given by Table II as follows:

Referring toFIG. 3, a functional flow diagram of a sector translation layer is shown. The circuit122may store multiple maps (or tables)160and162. The circuit120generally comprises a block (or circuit)164. The circuit164may buffer maps (or tables)166and168.

The circuit164may implement a cache circuit. The circuit164is generally operational to buffer all or a portion of each map stored in the circuit122. In various embodiments, the circuit164is designed as part of the circuit120. In other embodiments, the circuit164may be separate from the circuit120.

In some embodiments, the circuit164may be designed as a random access memory (e.g., RAM). The RAM may have a low-access latency. The RAM may be controlled to function as a cache for the maps. In various embodiments, a common double data rate (e.g., DDR) RAM may be used to implement the circuit164. For example, a 4,096 byte sector size with a 2 terabyte capacity in the device104generally results in 64 megabytes of data in the map168.

The map160may implement a logical address (e.g., LA) to physical address (e.g., PA) translation map (or table). Entries of the map160generally identify physical addresses of sectors in the device104that correspond to logical block addresses generated by the circuit92. In various embodiments, the map160may be implemented as a multi-level (e.g., two level) address translation layer.

The map162may implement a physical address free sector (e.g., PA-FREE SECTOR) bitmap. The map162generally maintains a flag for each sector in the device104. In various embodiments, each flag may be a single bit. Each flag in a free state (e.g., a logical one state) generally indicates that the corresponding sector in the device104currently contains stale data or no data (e.g., unwritten) and so is free to be written. Each flag in an occupied state (e.g., a logical zero state) generally indicates that the corresponding sector in the device104currently contains valid data (e.g., written).

The map166may be a cached copy containing all or a portion of the map160. In various embodiments where the map160is a two-level sector translation map, the map166may comprise the first level and portions of the second level of the map160. Other combinations of map levels may be implemented to meet the criteria of a particular application.

The map168may be a cached copy containing all or a portion of the map162. In some embodiments, the map168may be cached copy of the entire map162. In other embodiments, the map168may contain a portion of the map162corresponding to the tracks (or cylinders) neighboring a current position of the head assembly148. For example, the map168may include flags of the current track aligned to the head assembly148and flags for N (e.g., 3 to 5) tracks to either side of the current track.

Therefore, the map168may be used to quickly identify free (stale data or unwritten) sectors near the head assembly148. Hence, writes may be quickly committed to the media with little to no movement of the head assembly148. The number of neighboring tracks generally depends on the speed at which the head assembly148may change tracks relative to the speed at which the flags of a new track may be copied from the map162to the map166.

In various embodiments, the full first level of the map160and the full map162may be copied to the maps166and168on power up. Movement of the head assembly148among the tracks may result in flushing out of the cache contents to the circuit122. Existing cache content may be written out before loading the next content from the circuit122to the cache164if the existing cache content is dirty. If the cache164is not dirty, no writes to the circuit122may happen. In situation where the cache164is loaded only for reading, no cache flushing may be performed.

The cache flushing may be triggered on a power loss. Power loss circuitry may initiate the flushing of the cache164to the circuit122. An onboard capacitor generally maintains enough charge to support the flushing of pending maps and checkpoints in the cache164to the circuit122. The cache flushing may also be triggered by the circuit92. For example, a standby immediate command (e.g., a command to move a device into a standby mode) may cause the circuit120to flush the contents of the cache164to the circuit122. The cache flushing may also be triggered at checkpoint intervals. For example, the maps166and168may be flushed to the maps160and162every few (e.g.,2) seconds.

In some embodiments, the map162may be stored in a NOR flash memory. The NOR flash generally permits the map162to be accessed like a random access memory as the head assembly148moves across the platter150. Therefore, the cached map168may be eliminated.

Referring toFIG. 4, a diagram of an example portion of the platter150is shown. The platter150is shown having multiple tracks (or cylinders)170a-170d. The head assembly148may be currently aligned to engage a current track (e.g.,170c as shown).

The circuit92may issue a write command with a logical block address and a count value to the circuit100at any time. The circuit102(e.g., the circuit120) may respond to the write command by identifying a physical address in the LA-to-PA map166that corresponds to the logical block address. If the physical address is in the current track (e.g.,170c) and approaching the head assembly148, the circuit120may wait for the platter150to rotate and then write the data into the appropriate physical address. If the physical address is not in the current track (e.g.,170c), the circuit120may search the map168to locate information about one or more next free sector near where the head assembly148is currently placed. The circuit120may allocate the identified free sectors for the write and update the map168to indicate that the free sectors are written. The map166may also be updated to link the logical block address to the about-to-be-written free sectors. After the data has been written in the medium, the map166and/or the map168may be flushed to the circuit122based on a caching policy of the circuit100. Updating between the maps160and166and between maps162and168may be programmable. The programming may be provided by the circuit92and/or during manufacturing.

Some embodiments of the circuit100may include one or more policies regarding writes to free sectors. Consider a case where each sector has a size of several (e.g., 4) kilobytes. Under a particular write policy (e.g., a write policy A), an initial write command may be received by the circuit100with a logical block address of 300 and a count value of 8 sectors. The circuit120may inspect the map168and find that a current sector at a physical address of zero is about to reach the head assembly148.

Therefore, the free sector map168may be updated by the circuit120to indicate that the physical addresses of the sectors0to7are written. The circuit120may map (or link) the logical block address of300to the current physical address (e.g., 0) with a length of 8. The circuit120may optionally flush one or both of the maps166and/or168to the circuit122.

Continuing the example, the circuit92may issue another write command for a logical block address of700with a count value of 4 sectors. The circuit120generally responds to the write command by checking the map168for free sectors. Since the head assembly148is still in the current track, the circuit120may allocate the free sectors at physical addresses8to11as written in the map168. The map166may be updated to link the logical block address of 700 to the physical address of 8 with a length of 4. One or both maps166and/or168may subsequently be flushed to the circuit122. The write data associated with the current write command may be written to the platter150in the sectors with the physical addresses of 8 to 11.

The circuit92may issue a third write command with a logical block address of304and a count value of 8 sectors. The circuit120generally responds to the write command by checking the map168for free sectors. Since the head assembly148is still in the current track, the circuit120may allocate the free sectors at physical addresses12to19as written in the map168. The map166may be updated to link the logical block address of304to the physical address of 12 with a length of 8. The write data associated with the current write command may be written to the platter150in the sectors with the physical addresses of 12 to 19. Note that the logical block addresses304to307were previously written by the initial write command (e.g., LBA300with a sector count of 8) into physical addresses4to7. Therefore, the circuit120may update the free sector map168to show that the sectors at the physical addresses4to7are now free (contain stale data). One or both maps166and/or168may subsequently be flushed to the circuit122.

In some write policies (e.g., a write policy B), the circuit120may seek the nearest track containing a sequence of contiguous free sectors sufficiently large to store all of the data associated with the write command. Consider a case as shown inFIG. 4where the head assembly148is about to reach multiple (e.g., 4) free sectors172. If the write command has too much data for the free sectors172to store, the circuit120may conclude that the free sectors178are the nearest set of contiguous free sectors. Therefore, the head assembly148may be moved from the current track170cto the track170ato align with the free sectors178. Depending on the speed of the voice coil motor152and the spindle motor154, the head assembly148may reach the free sectors178in the track170ain less than a single rotation of the platter150or after one or more rotations of the platter150.

In other write policies, the circuit120may split writes into multiple segments of sequential free sectors. Consider again the case as shown inFIG. 4where the head assembly148is about to reach the four sequential free sectors172. A write command may be received with a sector count value of greater than four (e.g., count value=6). The circuit120may search the map168for free sectors near the current position of the head assembly148and conclude that the initial four sectors172may be written with the data associated the initial four logical block addresses. The circuit120may decide to write the remaining two sectors of data in the free sectors176(e.g., a write policy C to use temporally nearest free sectors) or in the free sectors174(e.g., a write policy D to use the physically nearest free sectors). Selection of the free sectors generally depends on the speed of the voice coil motor152and the speed of the spindle motor154. In another write policy (e.g., a write policy E), the circuit120may conclude that the nearest free sectors are any free sectors within the current track. Another write policy (e.g., a write policy F) generally splits the write data into two or more parts and writes each part substantially simultaneously on a different surface of one or more platters150. Other write policies may be implemented to meet the criteria of a particular application.

Referring toFIG. 5, a functional flow diagram of an example technique180for mapping the logical block addresses to the physical addresses is shown. The technique (or method or process)180may be performed by the circuits120and164. The technique180generally comprises a step (or state)182, a step (or state)184, a step (or state)186, a step (or state)188, multiple steps (or states)190a-190nand multiple steps (or states)192a-192n. The steps180to192nrepresent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry, one or more electronic design tools, and/or other implementations.

Second-level map parameters maybe stored in programmable registers of the circuit120in the step182. The circuit92may provide an access command (e.g., a read command or a write command) with a logical block address to the circuit120. An integer division of the logical block address may be performed by the circuit120in the step184based on the parameters stored in the registers in the step182. A quotient of the division generally establishes a first-level map index value (e.g., FLM INDEX). A remainder of the division forms a second-level map page index (e.g., SLM PAGE INDEX). In some embodiments, the divider step184may be coupled to the first-level map186and the one or more second-level map pages188(a representative single second level page is shown). In various embodiments, some or all of the process of mapping logical block addresses, such as the divider step184, is implemented (e.g., in firmware or software) executing in the circuit120.

A mapping of the logical block addresses to the physical addresses of the sectors in the device104may be a two-level map having a first-level map186and one or more second-level map pages188. The two-level map may be implemented via first-level map elements coupled to one or more second-level map elements. The first-level map186generally includes a plurality of entries (or pages)190a-190n. Each entry190a-190nmay contain information about a corresponding second-level map page. Each entry190a-190nof the first-level map186may point to a respective one of the second-level map pages (such as the second-level map page188).

Each second-level map page188may include a plurality of entries192a-192n. Each entry192a-192ngenerally contains information about a physical address of a corresponding sector.

Each entry192a-192nmay point to a location in the device104where data begins (e.g., a read unit storing at least the beginning of host write data for a logical block address).

The quotient FLM INDEX may be used to select a first-level map entry190a-190n. A page field of the selected first-level map entry may be read as a second-level map pointer (e.g., SLM POINTER). The page field is used to select a second-level map188, and the remainder SLM PAGE INDEX may be used (e.g., as an offset) to select an entry192a-192nof the selected second-level map page188.

A field of the selected second-level map page entry192a-192nmay be used to select a particular physical address (e.g., PA) location in the device104where at least a beginning of the sector sequence corresponding to the presented logical block address is stored. In various embodiments, the physical addresses include cylinder values, head values and sector values.

In various embodiments, the quotient may be used as a key to access the cache (e.g., the circuit164), such as a fully associative cache of the second-level map pages. If a hit occurs in the cache for a particular second-level map page, a latest copy of the particular second-level map page may be found in the cache without accessing the map160in the circuit122. Providing fast access to a plurality of second-level map pages enables, in some embodiments and/or usage scenarios, may result in more efficient processing of multiple independent streams of sequential data accesses to the device104(e.g., a stream of sequential data accesses to a region of logical block addresses interspersed with another stream of sequential data accesses to another region of logical block addresses).

Referring toFIG. 6, a flow diagram of an example implementation of a write method200is shown. The method (or process or operation)200may be implemented by the circuits104and120-124. The method200generally comprises a step (or state)202, a step (or state)204, a step (or state)206, a decision step (or state)208, a step (or state)210, a step (or state)212, a step (or state)214, a step (or state)216, a step (or state)218, a decision step (or state)220and a step (or state)222. The steps202-222may represent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry, one or more electronic design tools, and/or other implementations. The sequence of the steps is shown as a representative example. Other step orders may be implemented to meet the criteria of a particular application.

In the step202, the circuit120may receive from the circuit92a write command with a logical address. In parallel (or sequentially or concurrently), the circuit120may lookup free sectors near the heads in the step204and begin fetching a second level map (e.g., SLM) for the logical address in the step206, if not already cached. In the decision step208, the circuit120may determine if the nearest free sectors (per a current one or more write policies) is in the same cylinder as the head assembly148. If the nearest free sectors are in a different cylinder, the circuits120and124may command movement of the head assembly148in the step210. In the step212, the circuit120may wait for the selected free sectors to reach the selected head assembly148.

The circuits120and124and the head assembly148may write the write data into the free sectors in the step214. The free sector map168may be updated by the circuit120in the step216. If the just-written data is an updated version of previously written data currently stored in the device104, flags of the sectors holding the now-obsolete data may be marked as free. Flags of the newly-written sectors may be marked as written.

The circuit120may update the translation map166in the step218. The update may include changing the logical address to physical address mapping and marking the updated second level maps as dirty. A check may be performed by the circuit120in the step220to determine if the sector count of the write command is done. If more data remains to be written, the method200may return to the step204and206to find additional free sectors. Once all the data has been written, the circuits120and124may command movement of the head assembly148to a defragmented and/or free cylinder in the step222.

Referring toFIG. 7, a flow diagram of an example implementation of a trim method240is shown. The method (or process or operation)240may be implemented by the circuits104and120-124. The trim method240may be performed without accessing the device104or altering any data stored in (on) the device104. The method240generally comprises a step (or state)242, a step (or state)244, a step (or state)246, a step (or state)248and a decision step (or state)250. The steps242-250may represent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry, one or more electronic design tools, and/or other implementations. The sequence of the steps is shown as a representative example. Other step orders may be implemented to meet the criteria of a particular application.

In the step242, the circuit120may receive a trim command from the circuit92. The trim command generally includes a logical block address and sector count value of data stored in the device104that is no longer used by the circuit92. The circuit120may begin fetching a second level map for the logical address in the step244, if not already cached. In the step246, the circuit120generally updates the second level map information in the translation map166in response to the trim command. The update may include setting the physical address to a trim value (e.g., a predetermined out of range value) and marking the second level map as dirty in the map166. The circuit120may also update the free sector map168in the step248in response to the trim command. The update may mark as free the old (former) physical addresses of the trimmed sectors. A check may be performed by the circuit120in the step250to determine if all of the trimmed sectors have been processed. If not, the method240may return to the step244and fetch another second level map that corresponds to the unprocessed sectors. Once all of the trimmed sectors have been processed, the method240may end.

Referring toFIG. 8, a flow diagram of an example implementation of a defragmentation method260is shown. The method (or process or operation)260may be implemented by the circuits104and120-124. The method260generally comprises a step (or state)262, a step (or state)264, a step (or state)266, a step (or state)268, a step (or state)270, a step (or state)272and a step (or state)274. The steps262-274may represent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry, one or more electronic design tools, and/or other implementations. The sequence of the steps is shown as a representative example. Other step orders may be implemented to meet the criteria of a particular application.

In the step262, a defragmentation may be triggered by the circuit120. In various embodiments, the trigger may be an input/output rate from the circuit92falling below a threshold and/or the circuit100having time to run background tasks. The circuit120may locate valid data stored in the sectors of every other cylinder (e.g., cylinders N, N+2, N+4, etc.) in the step264. In various embodiments, the sectors containing the valid data may be marked in the free sector map168as written. The circuit120may copy the valid data from some to all of the located sectors in the step266into a buffer. The buffered valid data may be written back to the circuit104in free sectors in every other (alternate) cylinder (e.g., cylinders N+1, N+3, N+5, etc.) in the step268. In the step270, the free sector map168may be updated to flag the sectors containing the valid data copied into the cylinders N+1, N+3, N+5, etc. as written, and the sectors containing the data left behind in the cylinders N, N+2, N+4, etc. as free. The circuit120may also update the translation map166in the step272such that the logical block addresses are translated into the new physical locations. In the step274, the circuits120and124may command movement of the head assembly148into alignment with a cylinder now containing all free sectors (e.g., a defragmented/free cylinder). Creation of the defragmented cylinders full of free sectors and locating the head assembly148on or near such cylinders generally speeds up writes because the writes may be done into the free sectors of the defragmented/free cylinders with little to no movement of the head assembly148. Other defragmentation sequences of written cylinders and free cylinders may be implemented to meet the criteria of a particular application.

In some embodiments, the circuit100may be overprovisioned. An overprovisioned circuit100generally has more available space on the platter150than is known to the circuit92. For example, the platter150may provide several (e.g., 20-30) percent overprovisioning. Therefore, a track may be kept free every few tracks by the circuit120(e.g., 1 track free in every 4 tracks for a 25% overprovisioning). After defragmentation of the platter150, the tracks N, N+1, N+2 and N+3 may contain the valid data while the track N+4 may be completely empty.

Referring toFIG. 9, a flow diagram of an example implementation of a cache flush method280is shown. The method (or process or operation)280may be implemented by the circuits120,122and164. The cache164generally contains a group282of nodes284a-284n. The nodes284a-284nmay be sorted within the group282into dirty nodes and non-dirty (or clean) nodes. A current level of the group282generally separates the dirty nodes from the non-dirty nodes. The method280generally comprises a decision step (or state)290, a step (or state)292, a step (or state)294and a step (or state)296. The steps290-296may represent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry, one or more electronic design tools, and/or other implementations. The sequence of the steps is shown as a representative example. Other step orders may be implemented to meet the criteria of a particular application.

In the decision step290, the circuit120may check the current level of the node group282. If the current level is below a second level map flush watermark level (e.g., not many dirty nodes), the method280may end. If the current level is higher than the second level map flush watermark level (e.g., too many dirty nodes), a copying of the map166to the circuit122(e.g., a flush of the map166to the map160) may be performed in the step292. In the step294, the just-flushed dirty nodes in the node group280may me marked as clean. In the step296, the first level map may be updated with the flash addresses of the second level maps.

Various embodiments may include one or more policies for handling read commands. Consider again the case where each sector has a size of several (e.g.,4) kilobytes. An initial read policy (e.g., read policy A) may handle a single read command at a time.

For example, the circuit120may receive a read command with the LEA of 300 with the sector count value of8. The translation map166may translate the LEA of 300 to the physical address of zero and a length of 4 (because the sectors4-7were marked as free sectors due to the example third write command). The circuit120may translate the next LEA304to the physical address of sector12with a length of 8. The physical sectors0-3and12-15may be read in order or in a rearranged order to optimize the head movement.

Referring toFIG. 10, a flow diagram of an example implementation of a single read method300is shown. The method (or process or operation)300may be implemented by the device104and the circuits120-124. The method300generally comprises a step (or state)302, a step (or state)304, a decision step (or state)306, a step (or state)308, a step (or state)310, a step (or state)312, a decision step (or state)314and a step (or state)316. The steps302-316may represent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry, one or more electronic design tools, and/or other implementations. The sequence of the steps is shown as a representative example. Other step orders may be implemented to meet the criteria of a particular application.

In the step302, the circuit120may receive from the circuit92a read command with a logical address. The circuit120generally translates the logical block address into a physical address in the step304. A check is made in the step304by the circuit120to determine if the data being accessed is currently trimmed (e.g., check the physical address for the predetermined out of range value). If the data is currently trimmed, the circuit120may return all zeros to the circuit92in the step310.

If the requested data is currently valid (e.g., is not currently trimmed), the circuit120may command the circuit124to move the arm to position the head assembly148in the appropriate cylinder in the step308. Once the head assembly148is positioned, the requested read data may be read from the platter150in the step312by the circuit124.

A check may be performed by the circuit120in the step314to determine if all of the requested read data has been obtained from the platter150. If not, the method300may return to the step304to determine the next physical address to be read. Once the read request has been serviced, the circuits120and124may command movement of the head assembly148to a defragmented/free cylinder in the step316in preparation for a write command.

Referring toFIG. 11, a flow diagram of an example implementation of a multiple read method320is shown. The method (or process or operation)320may be implemented by the device104and the circuits120-124. The method320generally comprises a step (or state)322, a step (or state)324, a step (or state)326, a step (or state)328, a step (or state)330, a step (or state)332, a step (or state)334, a decision step (or state)336and a step (or state)338. The steps322-338may represent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry, one or more electronic design tools, and/or other implementations. The sequence of the steps is shown as a representative example. Other step orders may be implemented to meet the criteria of a particular application.

In the step322, the circuit120may receive from the circuit92a rapid sequence of multiple read commands. In the step324, the circuit120may buffer the read commands. The circuit120may subsequently rearrange the sequence of read commands in the step326to improve movement efficiency of the head assembly148during the read sequence.

In the step328, the circuits120and124may command movement of the head assembly148to a cylinder corresponding to an initial read command in the rearranged sequence of read commands. An initial read of the read data may be performed by the circuits120and124in the step330. In the step332, the circuits120and124may command movement of the head assembly148to a next read command in the rearranged sequence. The circuits120and124may read the next read data from the media in the step334.

If one or more read commands remain to be serviced, the decision step336may return to the step332. Thereafter, the head assembly148may be moved again and the next read data may be read from the media. The loop around the step332,334and336may continue until all of the read commands in the rearranged list of read commands have been serviced. In the step338, the circuit120and124may command movement of the head assembly148to a defragmented/free cylinder in the step338to prepare for a new write command.

Referring toFIG. 12, diagrams illustrating head movement based on a read sequence with and without rearrangement are shown. In an example movement without rearrangement360, a temporal sequence of three read commands362(e.g., LBA1000),364(e.g., LBA1001) and366(e.g., LBA1002) is shown. To service the read command362, the head assembly148is moved from a current location to an outer track to access the LBA1000. After the read command362has been completed, the head assembly148is moved390to an inner track to service the read command364to access the LBA1001. After the read command364has completed, the head assembly148is moved again392to a middle track to service the read command366.

In the example movement with the rearrangement370, the rearranged sequence of read commands may be364,366and362. The head assembly148may be initially moved to the inner track to service the read command364to access the LBA1001. After the read command364has completed, the head assembly148may be moved392to the middle track to service the read request366. After the read command366has completed, the head assembly148may be moved again394to the outer track to service the read request362. By rearranging the read commands, the head assembly148movement may be along an overall shorter path because the movement394in the rearranged sequence is shorter than the movement390in the original sequence. Thus, the rearranged read commands may be serviced in less time than in the original sequence of commands.

Referring toFIG. 13, a block diagram of an example implementation of an apparatus90ais shown. The apparatus90amay be a variation on the apparatus90. The apparatus90agenerally comprises the circuit92and a block (or circuit)100a. The circuit100agenerally comprises a block (or circuit)102aand the device104. The circuit102agenerally comprises the circuit120, the circuit122, the circuit124, a block (or circuit)382, a block (or circuit)384and a block (or circuit)386. The circuits100ato386may represent modules and/or blocks, embodiments of which include one or more of hardware circuitry, executable code (e.g., software, microcode, programming instructions, firmware, etc.) in a storage device used by the hardware circuitry, one or more electronic design tools, and/or other implementations.

The signal MAPS may be exchanged between the circuit122and the circuit384. One or more signals (e.g., H) may be exchanged between the circuit120and the circuit386. The signal H generally carries commands and data received from and sent to the host circuit92. Components of the signal H may include, but are not limited to, read commands, read data, write command, write data, trim commands and/or defragment commands. One or more signals NVM may be exchanged between the circuit382and the circuit384. Components of the signal NVM may convey nonvolatile memory commands and map data. One or more signals (e.g., C) may be exchanged between the circuit120and the circuit382. Components of the signal C may include, but are not limited to, the map data, cache flushing commands and/or cache fetching commands.

The circuit382is shown as the cache circuit external to the circuit120. The circuit164may be in communication with the circuit120to permit the circuit120to access the maps166and168. The circuit382may also be in communication with the circuit384to flush the cache data to the circuit122and fetch data from the circuit122to update the cache.

The circuit384may implement a nonvolatile memory interface circuit. The circuit384is generally operational to control the circuit122, read data from the circuit122and write data to the circuit122. Additional operations of the circuit384may include, but are not limited to, error correction encode data written to the circuit122, decode (e.g., hard decode and/or soft decode) and error correct data read from the circuit122, adjust read threshold voltages in the circuit122, perform wear leveling on blocks in the circuit122, perform garbage collection in the circuit122, control read amplification in the circuit122, control read disturb in the circuit122, and command block erases in the circuit122.

The circuit386may implement a host interface circuit. The circuit386is generally operational to provide communication between the circuit120and the circuit92via the signal HOST I/O.

Other signals may be implemented between the circuits92and386to meet the criteria of a particular application.

Various embodiments of the present invention may aid in minimizing head seek during random writes thereby improving both writing latency and writing throughput. Writing to the nearest free sectors generally results in higher writing speed. Writing to multiple platter surfaces in parallel may also improve writing speed. An endurance of a servo head assembly may be improved by reducing the average movement used in servicing write commands. The trim operations may be easily supported and may result in little to no head assembly/voice coil motor movement.

Various embodiments of the invention may implement a sector translation layer to optimize the seek time and rotational delay that, in turn, generally improve the throughput of the drive. The controller may use a persistent storage to map LBA-to-CHS (e.g., logical address-to-physical address) address translations.

Flash memory may be used at the persistent storage for such applications. When a write request received from the host, a map of free sectors nearest to the current head position may be analyzed. The write data is subsequently written to the nearest unmapped free sectors. The write technique generally reduces head movement and so may reduce both the seek time delay and the rotational latency delay.

Various embodiments of the invention may reorder read commands so that the head traversal may be optimized (e.g., moved in a single direction). A buffer management capability may be included in the hard disk drive controller to transfer the read data to correct offsets in a buffer. The resulting overall read time may be reduced relative to reading the platter in the same order that the read commands were received.

The functions and structures illustrated in the diagrams ofFIGS. 1-13may be designed, implemented, modeled, emulated and/or simulated using one or more of a conventional general purpose processor, digital computer, microprocessor, microcontroller and/or similar computational machines, programmed according to the teachings of the present specification, as will be apparent to those skilled in the relevant art(s). Appropriate software, firmware, coding, routines, instructions, opcodes, microcode, and/or program modules may readily be prepared by skilled programmers based on the teachings of the present disclosure, as will also be apparent to those skilled in the relevant art(s). The software is generally embodied in a medium or several media, for example non-transitory storage media, and may be executed by one or more of the processors sequentially or in parallel.

Embodiments of the present invention may also be implemented by the preparation of ASICs (application specific integrated circuits), FPGAs (field programmable gate arrays), PLDs (programmable logic devices), CPLDs (complex programmable logic device), sea-of-gates, ASSPs (application specific standard products), one or more integrated circuits, circuitry based on hardware description languages, flash memory, nonvolatile memory, random access memory, read-only memory, magnetic disks, floppy disks, optical disks such as DVDs and DVD RAM, and magneto-optical disks, modifications of which will be readily apparent to those skilled in the art(s). As used herein, the term “simultaneously” is meant to describe events that share some common time period but the term is not meant to be limited to events that begin at the same point in time, end at the same point in time, or have the same duration.