Sequential vectored buffer management

A method and apparatus for managing a buffer memory in a disc drive. An arbitrated buffer stores data read from, or to be written to, the disc. Sequential entries (that store pointers to the data) in the buffer, corresponding to a requested traversal, are traversed prior to voluntarily relinquishing ownership of the buffer.

FIELD OF THE INVENTION

The present invention relates to memory management. More specifically, the present invention relates to the management of buffer memory in a disc drive.

BACKGROUND OF THE INVENTION

Disc drives are typically used for information storage and utilize at least one rotatable disc with concentric tracks defined thereon for storing data. A data head (or transducer) is disposed relative to the disc surface to read data from, and write data to, the various tracks on the disc. The transducer is coupled to, or formed integrally with, an actuator arm which moves the transducer relative to the disc surface in order to access prespecified portions of the disc surface.

In retrieving data from, and writing data to, the discs, the disc drive often employs a cache or buffer memory. For instance, data to be written to the disc is often received from a host controller and written to the buffer or cache until the write circuitry has time to write the data from the buffer or cache to the specified location on the disc. Similarly, data retrieved from the disc is often written into the buffer until it can be retrieved by the host.

It often happens that the host, in writing data to the disc, will write data to a specified logical block address on the disc. That data is first written into cache were it is held until the write circuitry can write it to the actual specified location on the disc. However, prior to that data being written on the disc, the host may issue another write command, specifying different data to be written to the same logical block address on the disc. Vector buffer management techniques have thus been implemented to simply replace the older data in the buffer, or cache, with the new data to be written to the same logical block address. In this way, the write circuitry need only perform one write operation to the disc, rather than performing two separate write operations.

In any case, after performing a number of cache reads and cache writes, the cache or buffer can become highly fragmented. For example, the buffer or cache is typically accessed by a large number of different entities in the disc drive, such as the host, the disc control components (such as the reading and writing circuitry), error correction code (ECC) components, and a traversal engine which actually traverses a linked list in the buffer to determine where to access user (or host) data in the buffer. Some data in the buffer is stored as a single linked list such that the data corresponding to logical blocks (e.g., 512-byte chunks) on the disc are stored in buffer blocks (e.g., a two-byte values comprising a sector address) and are linked in the buffer by an address in one buffer block which points to the address of the next buffer block containing data in the specified logical block in the disc. Some data (such as host data) is stored in seemingly randomly located sectors of space in the buffer, which are located as indicated by the linked list.

In traversing the buffer, the traversal engine has traditionally functioned such that each access of a subsequent buffer or cache address was treated as a completely new and independent access to the cache. Therefore, even in situations where the traversal engine was to traverse three sequential buffer memory addresses, the traversal engine would release ownership of the buffer and re-arbitrate for access to each subsequent (or “next”) buffer address location. This adds significant delay in the command overhead for the drive and degrades drive performance.

SUMMARY OF THE INVENTION

The present invention is implemented as a method or apparatus for managing a buffer memory in a disc drive. An arbitrated buffer stores data read from, or to be written to, the disc. All sequential entries in the buffer, corresponding to a requested traversal, are traversed prior to voluntarily relinquishing ownership of the buffer, until a higher priority requester asks for arbitration.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

FIG. 1is an isometric view of a disc drive100in which the present invention is useful. Disc drive100includes a housing with a base102and a top cover (not shown). Disc drive100further includes a disc pack106, which is mounted on a spindle motor (not shown) by a disc clamp108. Disc pack106includes a plurality of individual discs, which are mounted for co-rotation about central axis109. Each disc surface has an associated slider110which is mounted to disc drive100for communication with the disc surface. In the example shown inFIG. 1, sliders110are supported by suspensions112which are in turn attached to track accessing arms (or actuator arms)114of an actuator116. The actuator shown inFIG. 1is of the type known as a rotary moving coil actuator and includes a voice coil motor (VCM), shown generally at118. Voice coil motor118rotates actuator116with its attached heads110about a pivot shaft120to position heads110over a desired data track along an arcuate path122between a disc inner diameter124and a disc outer diameter126. Voice coil motor118is driven by servo electronics130based on signals generated by heads110and a host computer (shown as number210inFIG. 2).

FIG. 2is a block diagram illustrating a memory management system200in accordance with one embodiment of the present invention. System200shows host210, buffer212, a buffer pointer214, arbiter216, error correction code (ECC) circuitry218, traversal component220, disc accessing circuitry (read/write circuitry)222and first in first out (FIFO), or “accessing,” memory224. In one embodiment, there can be separate memories224for different components (e.g., separate FIFOs for host accesses and disc accesses). As illustrated inFIG. 2, buffer memory212includes a data portion associated with each address in the buffer. The data portion has, attached thereto, a linked list pointer. Therefore, when data for logical blocks on disc106is to be written to disc106, that data is provided by host210, along with a logical block address for storage of the data on disc106. The data is first written into buffer212at buffer address locations. Because the address locations may not be sequential, linked list pointer226points to the next address in buffer212which contains data corresponding to the next logical block address specified for the write operation. Therefore, when disc access circuitry222has finished its other read or write operations, it can access buffer212to obtain the data to be written to disc106, retrieve that data, and write it to the designated logical block address on disc106.

The same is true for read operations. For example, assume the specified logical block addresses0-5from disc106have been requested by host210, have been read from disc106and have been stored in buffer212for access by host210. The data from logical block addresses0-5may be stored at buffer memory addresses0-3,6and8, for instance. In that case, buffer memory address0would contain buffer memory address1in its linked list pointer section226. This indicates that the data associated with that read operation continues at buffer memory address1. Similarly, the data at buffer memory address1would include buffer memory address2in its linked list pointer portion226. This indicates that, after the data at buffer memory address1has been accessed, the next portion of data corresponding to the data request resides in buffer memory address2. This continues such that the data at buffer memory address3includes buffer memory address6in its linked list pointer226. The data at buffer memory address6includes buffer memory address8in its linked list pointer226. By simply following this linked list, the component accessing buffer memory212can obtain all of the memory associated with a given requested traversal for which it is accessing the buffer.

FIG. 2also shows, however, that buffer212can be accessed by a wide variety of different components, including host210, ECC component218, disc access circuitry222and traversal component220. In order to maintain orderly accessing of buffer212, arbiter216is implemented which arbitrates ownership of the buffer pointer214(and hence access to buffer212) among the various components which seek to access buffer212.

Of the components illustrated inFIG. 2, the present discussion will proceed with greater detail with respect to traversal component220. Traversal component220is illustratively a hardware component which actually traverses the buffer memory212in order to hop through the buffer accesses desired for a given traversal request.

In doing so, traversal component220is given, for example, a buffer memory starting address and a number of “hops” (or a number of additional memory addresses) which it must examine in order to satisfy the current buffer memory access operation (or requested traversal). Therefore, traversal component220arbitrates through arbiter216for ownership of the buffer memory pointer214. Once it has successfully arbitrated ownership of pointer214, traversal component220sets pointer214to the buffer memory starting address which it has been provided. Traversal component220can then access the data stored at the pointed-to address and follow the linked list pointer the predetermined number of “hops.” The data contained at each buffer memory address is provided to FIFO224where it can be accessed by the portion of the disc drive which requires it. Again, it should be mentioned that more than one FIFO can be used.

In the past, traversal component220has been required to arbitrate for ownership of pointer214each time it desires to access a new buffer memory address. Therefore, even if, as in the example illustrated above, the requested traversal has a plurality of hops which are sequential in buffer212, and can be performed very quickly, traversal component220has been required to de-arbitrate itself from ownership of pointer214, re-initiate the arbitration process and arbitrate for ownership214, only to access the very next sequential buffer memory address location in buffer212. Thus, even in instances where memory mapping in buffer212has been sequential, traversing buffer212has taken an undesirably large amount of time. However, in accordance with the present invention, traversal component220is now configured to take advantage of sequential memory mapping in buffer212, even where buffer212is not managed in a sequential fashion, but just happens to be storing data sequentially. This is illustrated in greater detail below.

FIG. 3is a more detailed block diagram of one embodiment of the buffer management system shown inFIG. 2.FIG. 3assumes that traversal component220currently has ownership of pointer214. Therefore, arbiter216has been omitted, for the sake of clarity.FIG. 3also shows that traversal component220illustratively includes traversal engine500, counter501, flag503, and FIFO filler502.FIG. 3also shows that the memory management system can include a buffer free list504. Buffer free list504illustratively includes a list of memory locations in buffer212which are currently free to be used. In one illustrative embodiment, buffer free list504not only includes hardware memory, but also includes a software component which encourages sequential buffer memory accesses when possible. When a segment of buffer212is freed, after being previously used, each contiguous sequential piece of the freed memory is compared to gaps in the current buffer free list to see if the newly freed buffer memory can be merged with any of the memory in the current buffer free list to obtain longer contiguous sequential free list segments. The buffer free list504illustratively includes a segment describer. Therefore, when a newly freed buffer segment can be merged with other segments in the buffer free list, the sequential free list segment describer is updated to reflect the change in buffering segmentation. In one illustrative embodiment, the piece of newly freed buffer is attached to a segment described by the free list segments describer.

However, implementation of the present invention does not depend, in any way, on positively managing buffer212in a sequential fashion. Instead, the present invention takes advantage of any sequential mapping in buffer212, regardless of whether this is done on purpose.

While a description of the operation of traversal component220in accordance with the system shown inFIG. 3is discussed in greater detail with respect toFIG. 4, it is discussed here briefly, merely as an overview.

When a traversal request is received by traversal component220, along with the buffer memory212starting address, traversal component220is provided with a number of hops to take in order to completely traverse buffer212in accordance with the present request. The number of hops is loaded into counter501. Upon successfully arbitrating ownership of pointer214, FIFO filler502begins accessing buffer memory212address locations sequentially beginning at the starting buffer memory address location, and places the data from the accessed address in FIFO224. Each time the data at a buffer memory address is accessed, the value in pointer214is incremented by 1. Also, FIFO filler502decrements the hops to traverse counter501.

As FIFO224is being filled, traversal engine500accesses the information which has been loaded into FIFO224. Traversal engine500looks to ensure that the entries in FIFO224actually correspond to sequential entries. By taking the example given above, where memory from logical block addresses0-5is requested and that data has been stored in buffer memory address location0,1,2,3,6and8, the starting buffer memory address loaded into pointer214is buffer memory address0. FIFO filler502thus begins at memory address0and accesses the data stored at that memory address and loads it into FIFO224. Without regard to the linked list pointer226in buffer212, FIFO filler502then increments pointer214by 1, accesses the data stored at that location and loads it into FIFO224. Again, without regard to linked list pointer226, FIFO filler502then again simply increments pointer214by 1 and accesses the data stored at that location in buffer212.

At the same time, traversal engine500begins to examine the entries in FIFO224. Traversal engine500looks at linked list pointer226and compares it to the next buffer memory address fetched from buffer212and stored in FIFO224. Therefore, in the example given above, once traversal engine500has examined the entry from buffer memory address3in FIFO224, it notes that the linked list pointer226is pointing to buffer memory address6. Traversal engine500then looks at the next entry in FIFO224and determines that it was actually taken from buffer memory address4(since FIFO filler502proceeds in a sequential fashion, regardless of linked list pointer226) and determines that such an entry is actually a non-sequential entry and then stops FIFO filler502from continuing to fill FIFO224with sequentially-fetched entries.

In any case, FIFO filler502fills FIFO224sequentially from buffer212while traversal engine500is examining the entries in FIFO224to ensure that they are actually sequential. In one illustrative embodiment, this continues until traversing is completed (e.g., the hops to go counter501is 0 and the FIFO pre-fetched entries are validated as being sequential) or until a higher priority requestor arbitrates ownership of the buffer. In another embodiment, FIFO filler502continues to fill FIFO224and engine500continues to validate those entries until the hops to traverse counter501is decremented to 0, until traversal engine500determines that an entry in FIFO224is actually a non-sequential entry, until FIFO224has been filled, or until another higher priority user successfully arbitrates ownership of pointer214away from traversal component220.

It should also be noted that, after traversal engine500has considered an entry in FIFO224, the data may be clocked out of FIFO224such that FIFO filler502can continue filling FIFO224in a circular fashion.

Once traversal component220has lost access to buffer212for any of the reasons stated above, and if traversal engine500has still not found a non-sequential entry in FIFO224, traversal engine500can continue processing the information in FIFO224until it has processed all entries, or until it reaches a non-sequential entry.

It should also be noted that, because FIFO filler502is necessarily ahead of traversal engine500, FIFO filler502may have placed additional entries in FIFO224after a non-sequential entry. In that instance, FIFO filler502will have erroneously decremented the hops to traverse counter501by the number of entries it has placed in FIFO224, after the non-sequential entry. Therefore, assuming that there is some number N of false sequential entries (i.e., entries in FIFO224which were fetched by FIFO filler502assuming they were sequential, but they actually were not sequential or occurred after a non-sequential entry) traversal engine500decrements pointer214by the number N and also increments hops to traverse counter501by the number N. This resets the hops to traverse counter501and pointer214to the appropriate locations such that traversal of buffer212can again be commenced at the entry containing the first non-sequential linked list pointer.

If the hops to traverse counter501is still non-zero, traversal component220remains active and again arbitrates for ownership of pointer214, at which point the process begins again. However, if the hops to traverse counter501is now 0, traversal component220has performed the requested traversal.

FIG. 4is a more detailed discussion of the operation of the system illustrated inFIG. 3.FIGS. 3 and 4shows that a requested traversal is first received from the drive controller, such as in response to a command from host210, as indicated by block600. In receiving the requested traversal, traversal component220is provided with the starting buffer memory address and the number of hops to take in buffer memory212, as shown in block602. The starting buffer memory address is loaded into pointer214and the number of hops is loaded into counter501.

Next, a software module (although this may be done by a hardware component as well) is executed in parallel with hardware traversal of buffer memory212. The software module simply keeps monitoring the hardware execution to determine whether the traversal is finished. This is indicated by block606. Once the traversal has been completed, the software indicates this to the drive controller as indicated by block608.

FIFO filler502then loads information from the starting buffer memory address into FIFO224and determines whether the number of hops to be taken is set to 0. This is indicated by block610. If the number of hops is 0, then the traversal is complete as indicated by block612. However, if the number hops is not 0, then FIFO filler502sets the fetch for FIFO flag503. Flag503can be accessed by both traversal engine500and FIFO filler502and indicates to both components whether FIFO filler502is commencing its fetching operations into FIFO224. Setting the flag503is indicated by block613.

Once flag503is set, the operation of traversal engine500and FIFO filler502is performed in parallel. This is indicated by symbol614. Therefore, FIFO filler502arbitrates for ownership of pointer214. This is indicated by block616. FIFO filler502then begins fetching entries from buffer212at the address location loaded into pointer214. These entries are loaded into FIFO224. This is indicated by block618.

So long as traversal component220still owns pointer214and so long as flag503is still set, and further so long as FIFO224is not full, FIFO filler502simply continues to increment the buffer memory address in pointer214, fetch the information located at that address location and load it into FIFO224. This is indicated by blocks620and622. When ownership of pointer214is lost, the FIFO is full, or traversal engine220has reset flag503, if any of those things occur, FIFO filler502resets flag503(if it is not already cleared) as indicated by block624. FIFO filler502then waits for traversal engine500to finish its traversal. This is indicated by block626.

As discussed above, while FIFO filler502is filling FIFO224traversal engine500is examining the entries in FIFO224for sequentiality. In the embodiment illustrated inFIGS. 3 and 4, traversal engine500increments and decrements hops to traverse counter501, rather than FIFO filler502. In that case, traversal engine500moves to the next entry to be examined in FIFO224, increases the buffer memory address count by 1 and decrements counter501by 1. This is indicated by block628. In examining this entry in FIFO224, the traversal engine determines whether the next entry in FIFO224is a sequential entry. In doing this, it compares the address in linked list pointer226of the entry under analysis in FIFO224to the current buffer memory address plus 1. If the two numbers are the equivalent, the next entry in FIFO224will be sequential. However, if they are not, then the present entry is the last sequential entry from FIFO224and traversal engine500resets flag503to stop FIFO filler502from continuing to fill FIFO224with sequential entries from buffer212. This is indicated by blocks630and632.

If, at block630, it is determined that the next entry is a sequential entry, but that counter501has decremented to 0, traversal engine500resets flag503to stop FIFO filler502from continuing to fill FIFO filler224. Further, if traversal engine500determines, at block630that FIFO filler502has reset flag503, then processing continues on to block632.

However, if at block630it is determined that the next entry is sequential, that FIFO filler502has not reset flag503, and that counter501is non-zero, then processing continues at block628where traversal engine500examines the next entry in FIFO filler224for sequentiality.

At block632, it is known that one of a number of things has happened. First, the counter501may have been decremented to 0 such that the traversal is complete. Also, however, traversal engine500may have encountered a non-sequential entry in FIFO224. Similarly, flag503may simply have been reset by FIFO filler502either because it no longer owns pointer214or because the FIFO224is full. Depending on the precise reason why traversal engine500has been kicked out of the loop formed by blocks628and630it will take different actions. For example, if, at block634it is determined that counter501is still non-zero and that the FIFO224is not empty, and that the entries in FIFO224, thus far, have been sequential, then traversal engine500continues to analyze the remaining entries in FIFO224for sequentiality. This is indicated by block636. In doing this, traversal engine500increases its buffer memory address counter and reduces the count in counter501with each fetch from FIFO224. This continues until either counter501is 0, FIFO224is empty, or a non-sequential entry is located in FIFO224.

If at block638it is determined that a non-sequential entry in FIFO224has been encountered, then traversal engine500reduces the buffer memory address by 1 and increases the number of hops to traverse by 1. This is indicated by block640. This is because those numbers will have been erroneously adjusted based on the assumption that the next entry in FIFO224is sequential, when in fact it was not. However, if processing reaches block638either because counter501has reached 0 or the FIFO224is empty, FIFO224is simply cleared as indicated in block642, and processing continues at block626. At block626, traversal component220can be in one of a number of different states. For example, the hops to traverse counter501may be 0 indicating that the traverse has been completed. This case is determined at blocks610and612. If processing has reached block626for any other reason, then the requested traversal is still not complete, but must continue. Therefore, processing continues at block613where flag503is set, FIFO filler502arbitrates for pointer214and traversal engine500begins examining the entries in FIFO224.

It can thus be seen that the present invention provides significant advantages over prior art systems. For example, the present invention quickly and efficiently takes advantage of sequential entries in buffer212, without requiring re-arbitration for ownership of the buffer in order to access each subsequent memory location. This significantly reduces the command overhead associated with the drive and thus increases drive performance.

One embodiment of the present invention includes a memory management system200in a disc drive100having at least one data storage disc106. The memory management system includes an arbitrated buffer memory212having a plurality of memory address locations storing data associated with logical block addresses on the disc106. The system200also includes a traversal component220configured to receive a requested traversal, arbitrate ownership of the buffer memory212to traverse sequentially mapped entries in the buffer212associated with the requested traversal prior to de-arbitrating itself from ownership of the buffer memory212.

The traversal component220can illustratively include a memory accessing component502sequentially accessing entries in the buffer memory212based on the requested traversal and storing the entries in an accessing memory224. The traversal component220can also include a traversal engine500configured to access the entries in the accessing memory224and determine whether the entries in the accessing memory224correspond to buffer memory entries corresponding to the requested traversal.

In one embodiment, the buffer memory212comprises a linked list of memory locations. The requested traversal includes a buffer memory starting address and a number of hops to take through the linked list beginning at the buffer memory starting address.

The traversal engine500can be configured to determine whether the entries in the accessing memory224correspond to buffer memory entries corresponding to the requested traversal by determining whether the entries in the accessing memory224correspond to buffer memory locations in the linked list identified by the requested traversal. The memory accessing component502and the traversal engine500are illustratively configured to operate substantially in parallel.

In one embodiment, the present invention is implemented as a method of managing a data buffer212in a disc drive100. The method comprises steps of (a) receiving a traversal request to traverse the data buffer212; (b) arbitrating for ownership of the data buffer212; and (c) traversing all sequential entries in the data buffer212, beginning at an entry point in the data buffer212, corresponding to the traversal request prior to voluntarily relinquishing ownership of the data buffer212.

The receiving step (a) can further include steps of (a)(1) receiving a data buffer starting address; and (a)(2) receiving a number of memory locations in the data buffer212which must be made to complete the traversal request. In one embodiment, the data buffer212comprises a linked list and the traversing step (c) comprises steps of (c)(1) reading sequential entries in the data buffer212into a register224; and (c)(2) determining whether the entries in the register224correspond to the traversal request.

The traversing step (c) can further comprise performing the reading step (c)(1) and the determining step (c)(2) substantially in parallel. The traversing step (c) can also include a step of (c)(3) reducing the number of memory locations from step (a)(2) by one each time the determining step (c)(2) determines that an entry in the register224corresponds to the traversal request.

One embodiment of the method can further include a step of (d) voluntarily relinquishing ownership of the data buffer212after all sequential entries in the data buffer212, corresponding to the traversal request, are read into the register224. In addition, one embodiment of the method can include a step of (e) stopping the reading step (c)(1) when it is determined in step (c)(2) that an entry in the register224does not correspond to the traversal request; and (f) voluntarily relinquishing ownership of the data buffer212. Also, in one embodiment, after ownership of the data buffer212has been relinquished, it is determined whether the number of memory locations from step (a)(2) has been reduced to zero. If it is determined that the number of memory locations from step (a)(2) has not been reduced to zero, ownership of the data buffer212is re-arbitrated.

Further, the method can include continuing the traversing step (c) until the number of memory locations to complete the traversal request is reduced to zero, by beginning traversing the data buffer212at an entry point at a next data buffer location in the linked list corresponding to the traversal request.