Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output addressing
Reexamination Certificate
2000-04-28
2002-12-03
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output addressing
C710S005000, C710S015000, C710S018000, C710S024000, C710S038000, C710S039000, C711S210000
Reexamination Certificate
active
06490635
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a disk drive controller that provides for the handling of queued commands from a host device and in particular to a method for detecting a command conflict that would restrict reordering of queued commands.
BACKGROUND OF THE INVENTION
FIG. 1
illustrates a conventional interface
100
for exchanging data between a hard disk drive
120
and a host
110
. The host
110
is typically a computer such as a personal computer, server or workstation. The disk drive
120
typically provides mass data storage for the computer. The disk drive
120
comprises a head disk assembly (HDA)
130
and an integrated controller
140
. The head disk assembly
130
includes one or more storage disks
132
. The controller
140
is hardware and associated firmware that interfaces to the host
110
and controls the transfer of data between the disk drive and the controller's data buffer or cache (not shown). The host
110
and disk drive
120
are connected by a bus
112
, which provides a standard physical and data link layer between the host
110
and controller
140
. Associated protocols provide a standard communications link layer between the host
110
and controller
140
. The most common standards for these physical, data and communications layers of the host-controller interface
100
are SCSI and ATA. One ATA standard, described in ANSI document number NCITS 317-1998 entitled “AT Attachment with Packet Interface Extension (ATA/ATAPI-4),” commonly known as ATA-4, defines a protocol for queued host commands.
Command queuing is an optional command scheme whereby the host
110
sends multiple tagged commands for processing by the controller
140
. The tagged commands are stored in a command queue, to be executed sequentially. Potentially, these commands can be reordered by the controller's microprocessor into an optimal execution sequence for enhanced disk drive performance, as described below. Command queuing also reduces interface bus overhead because the controller
140
can perform disk accesses while waiting for the next host command. Further, command queuing allows the controller
140
to release the interface bus
112
if command execution will be delayed.
Command reordering is a technique used with command queuing to mitigate the effects of seek time and rotational latency, the slowest aspects of disk drive data transfers. If the command order can be changed so that commands accessing data in areas closer to the head are given greater priority, then the performance of the drive improves. For example, if a first command received from the host requests data from an inner track, a second command requests data from an outer track and a third command requests data, also from an inner track, the head has to travel from the inner tracks to the outer tracks, and then back to the inner tracks to execute the commands in chronological order. Command reordering would efficiently execute the first and third commands sequentially.
FIG. 2
illustrates the taskfile register content for queued commands, as defined in the ATA-4 specification. The taskfile register
200
is a memory located on the controller
140
(
FIG. 1
) at specific host I/O addresses. The host writes to the taskfile register
200
to initiate commands, and the host reads the taskfile register to obtain data transfer status (not shown). For a queued read or write command, the taskfile register
200
contains a block count
210
, a tag
220
, a logical block address (LBA)
230
and a command code
240
. The LBA
230
specifies the logical starting address on the storage disks
132
(
FIG. 1
) for a read or write. The block count
210
specifies the number of blocks of data to transfer between the storage disks
132
(
FIG. 1
) and the host
110
(FIG.
1
). The tag
220
is a host designated command identifier, allowing the host
110
(
FIG. 1
) to determine which of several queued and possibly reordered commands was subsequently executed by the controller
140
(FIG.
1
). The command code
240
is a unique bit pattern that specifies a particular host command.
A problem that arises with respect to queued commands and, in particular, with command reordering is that a conflict can exist when the address range of a write command overlaps with the range of a previously queued read or write command.
FIG. 3A
illustrates one such conflict between two write commands
310
,
320
. For example, assume a first queued write command
310
has an address range extending from
100
to
199
, as shown. Assume a second queued write command
320
is received with an address range extending from
45
to
119
, as shown. The host would assume that these commands
310
,
320
are executed chronologically, with the overlapping data portion
322
of the second write command
320
overwriting the data portion
312
of the first write command
310
in the address range from
100
to
119
. If the controller reorders these queued commands
310
,
320
, then the overlapping data portion
312
of the first write command
310
would, instead, overwrite the data portion
322
of the second write command
320
. A subsequent disk read in the address range of
100
to
119
would return erroneous results to the host.
FIG. 3B
illustrates a conflict between a queued read command
330
and a subsequent queued write command
340
. For example, assume the queued read command
330
has an address range extending from
100
to
199
, as shown. Assume the subsequent queued write command
340
has an address range extending from
170
to
244
, as shown. The host would assume that these commands
330
,
340
are executed chronologically, with the read command returning data from the address range
170
to
199
prior to being overwritten by the write command
340
. If the controller reorders these queued commands
330
,
340
, then the overlapping data portion
342
of the write command
340
would, instead, overwrite the data portion
332
subsequently accessed by the read command
330
, returning erroneous data to the host.
A read command overlapping with another read command is not a conflict, because correct data is returned to the host regardless of the order of execution of read commands. Further, a subsequent read command overlapping with a previous write command is not a conflict. The data for the queued write would be held in the controller's cache. If the read command is reordered to occur before the write command, the overlapping portion of the read command would be provided from the cache rather than from the storage disks. Thus, the data returned to the host from the overlapping portion of the read command would be the same regardless of the order of command execution.
SUMMARY OF THE INVENTION
One aspect of the present invention is a conflict detection method for a disk drive controller, such a conflict potentially occurring if the execution sequence of queued commands sent from a host is reordered to optimize disk drive data transfers. The conflict detection method comprises the steps of decoding a first command, where the first command is a queued read or a write, and reading an associated first logical block address (LBA) and first block count, where the first LBA and the first block count define a first address range. The method further comprises the steps of decoding a second command, where the second command is a write, and reading an associated second LBA and a second block count, where the second LBA and the second block count define a second address range. The method also comprises the steps of detecting an overlap between the first address range and the second address range and setting a conflict flag based on the overlap. In addition the method comprises the step of restricting command reordering based upon the flag in order to prevent the conflict from occurring.
In one embodiment, the conflict detection method described in the previous paragraph further comprises the steps of reading a tag value associated with the first command, creating an entry in random access memory (RAM)
Gaffin Jeffrey
Perveen Rehana
Shara, Esq. Milad G.
Smith, Esq. Glenn R.
Western Digital Technologies Inc.
LandOfFree
Conflict detection for queued command handling in disk drive... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Conflict detection for queued command handling in disk drive..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conflict detection for queued command handling in disk drive... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2990797