United States Patent [19]
`Young
`
`[54] METHOD FOR CONCURRENTLY
`EXECUTING A CONFIGURED STRING OF
`CONCURRENT I/O COMMAND BLOCKS
`WITHIN A CHAIN TO PERFORM A RAID 5
`I/O OPERATION
`
`[75] Inventor: B. Arlen Young, Palo Alto, Calif.
`[73] Assignee: Adaptec, Inc., Milpitas, Calif.
`
`[21] Appl. No. 615,479
`[22] Filed:
`Mar 15, 1996
`[51] Int. Cl." ............................. G06F 13/12; G06F 13/14
`[52] U.S. Cl. .......................... 395/825; 395/114; 395/596;
`395/827
`[58] Field of Search ..................................... 395/580, 582,
`395/595, 114,597, 825, 827, 441, 671
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,503,499 3/1985 Mason et al. ........................... 364/200
`4,858,105 8/1989 Kuriyama et al. .......
`... 364/200
`5,131,082 7/1992 Bonevento et al. .
`... 395/275
`5,251,312 10/1993 Sodos ...................
`... 395/425
`5,261,097 11/1993 Saxon ...........
`... 395/650
`5,287,467 2/1994 Blaner et al. .
`... 395/375
`5,293,500 3/1994 Ishida et al. .....
`... 395/375
`5,293,624 3/1994 Andrade et al. .
`... 395/425
`5,410,666 4/1995 Nakano et al. ..
`... 395/425
`5,428,802 6/1995 Anglin et al. .
`... 395/800
`5,452,469 9/1995 Sone et al. ....
`... 395/800
`5,455,923 10/1995 Kaplinsky ............
`... 395/481
`5,459,838 10/1995 Coscarella et al. ..
`... 395/827
`5,504,861
`4/1996 Crockett et al. ................... 395/182.11
`
`US00589.2969A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,892,969
`Apr. 6, 1999
`
`5,548,795 8/1996 Au ........................................... 395/872
`5,584,041 12/1996 Odawara et al. ....................... 395/834
`5,615,329 3/1997 Kern et al. ......
`... 395/182.04
`5,649,225 7/1997 White et al. ............................ 395/800
`Primary Examiner—Thomas C. Lee
`Assistant Examiner—Rehana Perveen
`Attorney, Agent, or Firm—Forrest Gunnison
`[57]
`ABSTRACT
`An I/O command block, that is stored in a memory, includes
`information for connecting the I/O command block to other
`I/O command blocks in a chain structure. The I/O command
`block chain structure allows simultaneity of execution,
`provides a mechanism to inhibit and enable execution of an
`individual I/O command block, and a mechanism for estab
`lishing precedence in the sequence of execution of the I/O
`command blocks. A plurality of I/O command blocks are
`configured into a chain of I/O command blocks in a memory
`where each I/O command block includes one of the plurality
`of I/O commands necessary to perform a RAID 5 I/O
`operation. A set of the I/O command blocks in the chain are
`configured so that the set of I/O command blocks are
`enabled to execute concurrently, i.e., the set of I/O command
`blocks are a concurrent string of I/O command blocks. The
`chain of I/O command blocks is executed in a sequence that
`is specified and controlled only by information in the I/O
`command blocks to perform the RAID 5 operation. For a
`RAID 5 write sequence, the string of concurrent I/O com
`mand blocks includes an I/O command block for a read data
`disk, and an I/O command block for a read parity disk. Also,
`one of the I/O command blocks in the chain is configured as
`an offshoot command block from one of the I/O command
`blocks in the string of concurrent I/O command blocks.
`16 Claims, 19 Drawing Sheets
`
`
`
`220
`
`260
`
`HA MEMORY
`
`|-20
`
`HOST
`MICROPROCESSOR
`
`KLX
`
`HA MANAGER
`
`SEQUENCER
`
`HOST COMPUTER
`
`HOST ADAPTER
`
`..T-24
`KFX Divier
`
`NišACE KHEX
`CIRCUIT
`
`242
`
`SCSI
`DEVICE
`
`Ex.1048.001
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 1 of 19
`
`5,892,969
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ex.1048.002
`
`DELL
`
`

`

`US. Patent
`
`Apr. 6,1999
`
`Sheet 2 0f 19
`
`5,892,969
`
`ovm
`
`mom
`
`85mm
`
`i
`
`mom
`
`535
`
`Nwm
`
`mom
`
`55mm
`
`5385ImoEmEZ‘mam
`
`Hmom
`
`mmozngm
`
`EE<Q<50:
`
`m
`on
`
`<m.UE
`
`50:
`
`E03:<1
`
`com
`
`0mm
`
`I$83
`oommomoi
`
`DELL Ex.1048.003
`Ex.1048.003
`
`DELL
`
`

`

`S.U
`
`m
`
`E
`
`%
`
`3
`
`:a
`
`8’
`
`2
`
`w
`
`
`
`MEgg:NEE/a4
`
`so:50:
`
`on”SEQwas:559BED
`.m8m8m8mom
`
`w85mew(em
`
`8mmmeow58
`
`9,mma:
`
`9mm
`
`
`
`0“1,:55:28m22:MEtaWE?E
`
`n:gm
`
`59%EE
`
`1amam6,II
`
`5mmcN_\8mmommom
`
`9rllllja||y
`
`
`mom
`
`muSmo
`
`Hmoz
`
`mmp¢<o<
`
`DELLEXJO48£O4
`Ex.1048.004
`
`DELL
`
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 4 of 19
`
`5,892,969
`
`
`
`300
`
`SCSI
`COMMAND
`BLOCK
`
`350
`
`ABORTED | ABORT | CON | HOLD
`PROGRESS
`CURRENT |
`OFF
`COUNT 306 | FLAG | FLAG |º FLAG
`305
`304
`303 302
`NEXT BLOCK POINTER
`
`320
`
`360
`
`330
`
`OFFSHOOT POINTER
`
`FIG. 3
`
`Ex.1048.005
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 5 of 19
`
`5,892,969
`
`F--— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
`|
`|
`|
`|
`
`
`
`
`
`
`
`
`
`2
`
`404B
`
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`SHARED MEMORY
`255
`
`|- — — — — — — — — — — — — — — — —
`
`
`
`- - - - - - - - - - - - - - ---
`
`1
`30
`
`QN FIFO
`
`MEMORY 250A
`
`00NTA
`
`QCNTB
`
`QIN FIFO
`
`MEMORY 250B
`
`476B
`
`290B
`
`SCBPTRA
`
`SEQUENCER
`
`SCBPTRB
`
`SEQUENCER
`
`HOST ADAPTER
`
`HOST ADAPTER
`
`FIG. 4
`
`Ex.1048.006
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 6 of 19
`
`5,892,969
`
`
`
`501 sº
`
`COMPLETE
`
`YES
`
`502
`
`PROGRESS
`COUNT
`
`-
`
`
`
`503
`
`POST
`COMPLETION
`
`504
`
`505
`
`LOAD
`NEXT BLOCK
`POINTER
`
`£ROGRESSS-506
`COUNT
`
`SKIPS
`SCB
`
`
`
`
`
`
`
`
`
`500 *
`
`508><froGRESS
`COUNT
`
`509
`
`FIG. 5A
`
`Ex.1048.007
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 7 of 19
`
`5,892,969
`
`
`
`
`
`
`
`
`
`HOLD OFF
`FLAG
`
`512
`
`SET
`PROGRESS
`COUNT
`
`RESET
`HOLD FLAG
`
`CON–CURRENT
`FLAG
`
`LOAD
`NEXT
`BLK POINTER
`
`FIG. 5B
`
`
`
`
`
`
`
`
`
`Ex.1048.008
`
`DELL
`
`

`

`U.S. Patent
`
`(~ WOOg
`
`
`
`
`
`
`
`(1009 010079(1009 0|00790009 01
`
`
`
`(10Ç9(1009 0100990009 0|80% 98009 01
`
`
`
`
`
`laer)2—^—)
`
`Ex.1048.009
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 9 of 19
`
`5,892,969
`
`FIG. 6B
`
`
`
`Ex.1048.010
`
`DELL
`
`

`

`US. Patent
`
`Apr. 6, 1999
`
`Sheet 10 0f 19
`
`5,892,969
`
` /700A
`
`706A
`IIIII 710A
`720A
`
`730A
`
`707
`/
`
`
`
`/7OOB
`
`/7OOD
`
`IIIII 7108
`TO 7000
`7203
`TO 7008
`7308
`
`IIIII 71°C
`TO 7000
`7200
`TO 7000
`7300
`
`IIIII 7123;;
`TO 700E
`7
`TO 7000
`7300
`
`
`
`IIEEE 7 105
`TO 7005
`7205
`
`TO 700E
`
`730E
`
`FIG.
`
`'7
`
`DELL Ex.1048.011
`Ex.1048.011
`
`DELL
`
`

`

`US. Patent
`
`Apr. 6, 1999
`
`Sheet 11 0f 19
`
`5,892,969
`
`:%\
`
`8%E8%E8%Ham—EH
`
`<omw
`
`8%E8%BEE—HE
`
`8%E8%a8%HEB—ma
`
`EDoommomwooowOH
`
`8%BEBE-
`
`momw
`
`0mm
`
`#zu
`
`vjm
`
`8%\:20
`
`5%
`
`0mm
`
`memmmeow9.
`
`8%E8%BEBE!
`
`meow
`
` 8%E8%E8%BEBE-I
`
`noon
`
`ooow\‘
`
`8%E8%a8%BEBE!
`
`88w.UE
`
`DELL Ex.1048.012
`Ex.1048.012
`
`DELL
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 12 of 19
`
`5,892,969
`
`
`
`
`
`
`
`
`}0013; IXEN 01
`|(5006-01 ||
`
`0006 0|
`
`0006 0|
`
`(W006-01 ||
`|(10006 01 ||
`
`|(5006 01 . |(5006-01 ||
`TILLIOL) |
`
`Ex.1048.013
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 13 of 19
`
`5,892,969
`
`CHAIN
`ERROR
`
`
`
`1001
`
`DETERMINE
`ERROR
`
`
`
`
`
`
`
`1002
`
`RECONFIGURE
`CHAIN
`
`
`
`
`
`
`
`RELOAD
`POINTER
`
`1003
`
`
`
`^ COMPLETE
`
`1004
`
`
`
`
`
`YES
`
`1005
`
`CONTINUE
`
`FIG 10
`
`Ex.1048.014
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 14 of 19
`
`5,892,969
`
`START CHAIN EXECUTION
`
`SCSI – X HOST
`1100A
`
`SCSI –X HOST
`1100B
`
`SCSI – X HOST
`1100C
`
`CHAIN EXECUTION COMPLETE
`
`FIG 11
`
`
`
`START CHAIN EXECUTION
`
`SCSI – X HOST
`1200A
`
`SCSI – X HOST
`1200B
`
`CHAIN EXECUTION COMPLETE
`
`FIG. 12
`
`Ex.1048.015
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 15 of 19
`
`5,892,969
`
`NO
`
`ABORTED
`?
`
`NO
`
`1302
`
`G)
`
`1330
`
`
`
`YES
`
`TETOT-1303
`PROCESS
`500
`
`NO
`
`ABORTED
`Q
`
`(B)
`
`1306
`
`ABORT
`TARGET
`
`1307
`
`NO
`
`G)
`
`1308
`
`1309
`
`YES
`UPDATE
`TARGET
`STATUS
`
`JUMP TO
`PROCESS
`500
`
`FIG. 13A
`
`Ex.1048.016
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 16 of 19
`
`5,892,969
`
`1310
`
`'9"><ABORT
`AND ABORTED
`º
`
`
`
`1320s;
`
`YES
`ABORT SCB
`
`
`
`
`
`
`
`OFFSHOOT
`POINTER
`
`CURRENT
`POINTER
`
`PREVENT
`DUAL
`ABORTION
`
`
`
`FIG. 13B
`
`Ex.1048.017
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 17 of 19
`
`5,892,969
`
`START CHAIN EXECUTION
`
`1407
`
`
`
`HOST –X MEMORY
`1400A
`
`
`
`MEMORY —X SCSI
`1400B
`
`MEMORY —X SCSI
`14000
`
`CHAIN EXECUTION COMPLETE
`
`FIG. 14
`
`START CHAIN EXECUTION
`
`HOST –X MEMORY
`1500A
`
`READ DATA DISK
`1500B
`
`READ PARITY DISK
`1500C
`
`RTE PARITY DISK
`1500E
`
`1507
`
`
`
`
`
`
`
`WRITE DATA DISK
`1500D
`
`
`
`CHAIN EXECUTION COMPLETE
`
`FIG. 15
`
`Ex.1048.018
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 18 of 19
`
`5,892,969
`
`START CHAIN EXECUTION
`
`TARGET 1 –X MEM
`1600A
`
`1607
`
`
`
`TARGET 2 –X MEM
`1600B
`
`TARGET 5 –X MEM
`1600C
`
`TARGET 4 –X MEM
`1600D
`
`
`
`MEM –X HOST
`1600E
`
`CHAIN EXECUTION COMPLETE
`
`FIG 16
`
`Ex.1048.019
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 6, 1999
`
`Sheet 19 of 19
`
`5,892,969
`
`BEGIN
`
`C. HEAD
`C.C.
`
`C. HEAD
`C.C.
`
`1701
`
`1702
`
`
`
`OFFSHOOT
`NON-FOCAL
`
`FOCAL
`
`1704
`
`1705
`
`
`
`S. END
`OFFSHOOT sº
`C.C.
`NON-F00AL ||NON-FOCAL || SKippºD
`1706
`1708
`
`OFFSHOOT
`NON-FOCAL
`
`** || gº
`
`F00AL
`
`SKIPPED
`
`
`
`
`
`S, END
`C.C.
`SKIPPED
`
`
`
`
`
`
`
`
`
`1709
`
`OFFSHOOT
`NON-FOCAL
`
`NON-F00AL
`
`FOCAL
`
`OFFSHOOT
`NON-FOCAL
`
`1714
`
`
`
`
`
`
`
`
`
`
`
`
`
`S. HEAD
`C.C.
`C.C.
`NONIFOCAL || SKIPPED
`
`
`
`
`
`S. END
`C.C.
`SKIPPED
`
`E. CHAIN
`FOCAL
`
`END CHAIN EXECUTION
`
`FIG. 17
`
`Ex.1048.020
`
`DELL
`
`

`

`5,892,969
`
`1
`METHOD FOR CONCURRENTLY
`EXECUTING A CONFIGURED STRING OF
`CONCURRENT I/O COMMAND BLOCKS
`WITHIN A CHAIN TO PERFORM A RAID 5
`I/O OPERATION
`
`10
`
`45
`
`RELATED APPLICATIONS
`This application is related to the following copending,
`commonly filed, and commonly assigned U.S. Patent Appli
`cations:
`1. U.S. patent application Ser. No. 08/617,990 (now
`pending), entitled “AMETHOD FOR SPECIFYINGA
`SEQUENCE OF EXECUTION OF I/O COMMAND
`BLOCKS IN A CHAIN STRUCTURE,” of B. Arlen
`Young, filed on Mar. 15, 1996 as Attorney Docket No.
`M-3804 US;
`2. U.S. patent application Ser. No. 08/616,817 (now U.S.
`Pat. No. 5,768,621), entitled “A CHAIN MANAGER
`FOR USE IN EXECUTING A CHAIN OF I/O COM
`20
`MAND BLOCKS,” of B. Arlen Young, filed on Mar.
`15, 1996 as Attorney Docket No. M-3913 US;
`3. U.S. patent application Ser. No. 08/616,817 (now U.S.
`Pat. No. 5,812,877), entitled “AN I/O COMMAND
`BLOCK CHAIN STRUCTURE IN A MEMORY,” of
`25
`B. Arlen Young, filed on Mar. 15, 1996 as Attorney
`Docket No. M-3914 US;
`4. U.S. patent application Ser. No. 08/616,476 (now
`pending allowance), entitled “A METHOD FOR
`SPECIFYING CONCURRENT EXECUTION OF A
`30
`STRING OF I/O COMMAND BLOCKS IN A CHAIN
`STRUCTURE,” of B. Arlen Young, filed on Mar 15,
`1996 as Attorney Docket No. M-3915 US;
`5. U.S. patent application Ser. No. 08/616,836 (now U.S.
`35
`Pat. No. 5,797,034), entitled “A METHOD FOR
`SPECIFYING EXECUTION OF ONLY ONE OF A
`PAIR OF I/O COMMAND BLOCKS IN A CHAIN
`STRUCTURE,” of B. Arlen Young, filed on Mar 15,
`1996 as Attorney Docket No. M-3916 US; and
`40
`6. U.S. patent application Ser. No. 08/616,838 (now U.S.
`Pat. No. 5,758,187), entitled “A METHOD FOR
`ENHANCING PERFORMANCE OF A RAID 1
`READ OPERATION USING A PAIR OF I/O COM
`MAND BLOCKS IN A CHAINSTRUCTURE,” of B.
`Arlen Young, filed on Mar. 15, 1996 as Attorney
`Docket No. M-3917.
`Each of the above applications is incorporated herein by
`reference in its entirety.
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention is related generally to control of
`host adapter systems that control transfer of data between
`two buses, and more specifically to a method for controlling
`the sequence of execution of control blocks by a host adapter
`system.
`2. Description of Related Art
`The Small Computer System Interface (SCSI) standard,
`which is specified by the American National Standards
`Institute (ANSIX3.131-1986, which is incorporated herein
`by reference in its entirety) of 1430 Broadway, New York,
`N.Y. 10018, is an example of an industry-recognized stan
`dard for a relatively complex local area network. Descrip
`tions of the SCSI bus may be found for example in U.S. Pat.
`No. 4,864,291 “SCSI Converter” issued Sep. 5, 1989 to J. E.
`Korpi and in U.S. Pat. No. 4,905,184 “Address Control
`
`50
`
`55
`
`60
`
`65
`
`2
`System for Segmented Buffer Memory” issued Feb. 27,
`1990, to R. P. Giridhar, et al., which are incorporated herein
`by reference in their entirety.
`A typical SCSI system 100 is illustrated in FIG. 1. A
`plurality of intelligent devices 120, 140, 141, 142 are
`coupled to SCSI bus 110 so that these devices can exchange
`information. The intelligent devices are (i) a first host system
`120, whose internal structure is shown in detail, that
`includes host adapter system 160 (ii) a second host system
`140 whose internal structure is similar to that shown for
`system 120, (iii) a first SCSI disk drive unit (Target-A) 141,
`and (iv) a second SCSI disk drive unit (Target-B) 142. The
`host adapter system in a host computer can be either a single
`integrated circuit, or a plug-in board. In each case, the host
`adapter system, hereinafter host adapter, transfers data
`between a host computer bus, e.g., an ISA bus, an EISA bus,
`a VME bus, or a PCI bus, and a SCSI bus.
`Typically, a software driver, executing on CPU 121 of
`host computer 120, builds and sends a command block to
`host adapter 160. Each command block specifies exactly
`how a SCSI command is to be executed. Host adapter 160
`executes the command block, and interrupts host computer
`120 to report completion of the execution. Herein, execution
`of a command block means performance of the SCSI
`command contained in the command block. Consequently,
`host computer 120 is interrupted at least once for every
`command block.
`Host adapter 160 does not correlate one command block
`with another, and executes each command block indepen
`dent of all others. Host adapter 160 may order the execution
`of a group of command blocks according to some criterion,
`such as a first-in-first-out execution order. However, typi
`cally no execution ordering information is provided by the
`software driver that generates and transmits the command
`blocks to host adapter 160.
`Nevertheless, at levels higher than host adapter 160, SCSI
`commands are often associated in a group. For example,
`tagged queue commands are members of a queue group.
`Host adapter 160 manages tagged queue commands as a
`special command type, but the command blocks for such
`commands are still managed as independent individual
`command blocks.
`Commands issued to a redundant array of inexpensive
`disks (RAID) over a SCSI bus are grouped by a RAID
`manager that executes on the host computer, but the com
`mands are seen as individual, unrelated SCSI commands by
`the host adapter. For example, a RAID 5 write command is
`a group of four SCSI commands, two read commands and
`two write commands, that are executed in a prescribed order.
`The RAID manager controls the execution order by waiting
`for the read commands to complete before issuing the write
`commands. Consequently, the host adapter sees a stream of
`unrelated read and write commands.
`The control of the execution order by the RAID manager
`places a burden on the computer executing the RAID
`manager and the performance of the RAID manager can be
`affected by interrupts to the host computer that are unrelated
`to the RAID write command. Similarly, the performance of
`a computer executing a SCSI host adapter driver could be
`enhanced if the computer was interrupted less than once per
`command block, and the execution time of each command
`block could be enhanced if it was not necessary to handle
`each command block independently.
`U.S. Pat. No. 5,131,082, entitled “Command Delivery for
`a Computing System for Transfers Between a Host and
`Subsystem Including Providing Direct Commands or Indi
`
`Ex.1048.021
`
`DELL
`
`

`

`5,892,969
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`3
`rect Commands Indicating the Address of The Subsystem
`Control Block,” of Bonevento et al. shows a structure for
`chaining together subsystem control blocks so that the chain
`of subsystem control blocks is treated as one logical request.
`However, this structure and method requires considerable
`storage space. Each subsystem control block includes a
`chain flag, a conditional chain field, first and second chain
`addresses and a chain identification field.
`Further, for each subsystem control block in a chain, a
`termination status block is defined to make it possible to
`handle termination at any point in the chain. Consequently,
`the storage required by the chain is not limited to storage
`required to specify the chain itself but also the storage for the
`termination status blocks.
`The chain disclosed in this patent appears to be a variation
`of a linked list. Only one of the two chain addresses is used.
`A device task decides which chain address to select from the
`subsystem control block depending on the ending state of
`the subsystem control block. Consequently, the chain allows
`only branching to one of the two chain addresses and so
`functions as a linked list with a possible choice of paths at
`each item in the list.
`Thus, despite the excessive storage requirements in the
`subsystem control block, the chain of Bonevento et al. has
`only limited capability. The chain structure does not support
`parallel simultaneous execution paths, enabling execution of
`multiple control blocks simultaneously, aborting a control
`block in the chain, or a method for determining when
`parallel execution paths have completed. Therefore, a more
`flexible chaining method and structure is needed.
`SUMMARY OF THE INVENTION
`According to the principles of this invention, a novel I/O
`command block, that is stored in a memory, includes infor
`mation for connecting the I/O command block to other I/O
`command blocks in a chain structure. Unlike the prior art
`chaining structure that permitted branching to one of two
`chain addresses, the I/O command block chain structure of
`this invention allows simultaneity of execution, provides a
`mechanism to inhibit and enable execution of an individual
`I/O command block, and a mechanism for establishing
`precedence in the sequence of execution of the I/O com
`mand blocks.
`This novel level of capability is provided by only infor
`mation in the I/O command blocks within the chain, and that
`information requires less storage space than the prior art
`technique. The minimization of the storage space required to
`support chaining is an important aspect in making the
`invention available in a wide variety of situations. Also,
`since the chaining structure of this invention supports more
`complex combinations of I/O commands, the load on the
`host computer is diminished in comparison to the prior art
`methods.
`In one embodiment, an I/O command block chain struc
`ture in a memory includes a plurality of I/O command block
`structures in the memory. Each I/O command block structure
`in the chain includes a chain control field and a next block
`pointer.
`The chain control field includes a hold-off flag having first
`and second states. Upon the hold-off flag having the first
`state, execution of the I/O command block structure is
`inhibited. Upon the hold-off flag having the second state,
`execution of the I/O command block structure is enabled.
`Alternatively, other mechanisms can be used with the other
`features of this invention to enable and inhibit execution. For
`example, execution could be inhibited until a pointer to an
`
`4
`I/O command block is loaded into a register or memory that
`in turn is used to initiate execution.
`When the I/O command block structure is other than an
`end of chain I/O command block structure, the next block
`pointer is a pointer to another I/O command block structure
`within the I/O command block chain structure. Upon
`completion of execution of the I/O command in the I/O
`command block structures a chain control field of the
`another I/O command block is analyzed by a chain manager,
`that is described more completely below.
`At least one of the I/O command block structures in the
`I/O command block chain structure in the memory is a head
`of chain I/O command block structure. The hold-off flag in
`the chain control field has the second state upon loading the
`I/O command block chain structure in the memory so that
`the head of chain I/O command block structure is enabled
`for execution.
`Another one of the I/O command block structures in the
`I/O command block chain structure in the memory is an end
`of chain I/O command block structure and the next block
`pointer in the end of chain I/O command block structure is
`a pointer to the end of chain I/O command block structure.
`Alternatively, the next block pointer in the end of chain I/O
`command block structure can be a null pointer.
`The chain control field also includes a progress counter.
`When the progress counter has a first value, e.g., zero, the
`hold-flag is set to the second state to enable execution of the
`I/O command block structure.
`The chain control field also has a concurrent flag. The
`concurrent flag in each I/O command block structure of a
`string of concurrent I/O command block structures in the I/O
`command block chain structure is used to indicate that the
`string of concurrent I/O command block structures are
`simultaneously enabled for execution. In one embodiment,
`the concurrent flag has first and second states, and concur
`rent flags in all I/O command block structures in the string,
`except a last I/O command block structure in the string, have
`the first state. A concurrent flag in the last I/O command
`block structure in the string has the second state.
`In addition, the chain control field includes an abort flag.
`Upon the abort flag being set in a first I/O command block
`structure, an aborted flag in a chain control field of a second
`I/O command block structure in the I/O command block
`chain structure is set during execution of the first I/O
`command block structure. The first I/O command block
`structure in the chain has an offshoot block pointer that
`points to the second command block when the abort flag is
`set. Note, first and second, as used here, do not denote a
`physical location in the chain structure, but rather are used
`to distinguish two I/O command block structures within the
`chain.
`Each I/O command block structure includes an offshoot
`block pointer. When the offshoot block pointer is not used in
`conjunction with the abort flag, the hold-off flag in a second
`I/O command block structure pointed to by the offshoot
`block pointer of the first I/O command block structure is
`unconditionally set to the second state upon completion of
`execution of an I/O command in the first I/O command block
`Structure.
`The chain of I/O command block structures stored in
`memory is a directed graph. To make a chain, the chain
`control field, the next block pointer, and the offshoot block
`pointer are configured in each I/O command block in the
`chain. The process of making a chain is a method for
`specifying a sequence of execution of a chain of I/O com
`mand blocks stored in a memory and execution of each I/O
`
`Ex.1048.022
`
`DELL
`
`

`

`5,892,969
`
`5
`command block using only information in the chain of I/O
`command blocks, because as explained above the chain
`controls the sequence and precedence of execution of the I/O
`command blocks in the chain.
`
`One operation in the method of this invention is resetting
`a hold-off flag in all I/O command blocks at a head of the
`chain, and setting a hold-off flag in all other I/O command
`blocks in the chain. When the hold-off flag is set, execution
`of the [/0 command block is inhibited, and when the
`hold-off flag is reset, execution of the I/O command block is
`enabled.
`
`Another operation in the method is configuring a counter
`in each I/O command block in the chain. The counters and
`the hold-off flags are used in sequencing execution of I/O
`command blocks in the chain.
`
`The configuration of the counter depends on the location
`of the I/O command block in the chain. For a head of chain
`1/0 command block,
`the counter is configured to a pre-
`defined value, e.g., one. For a non-concurrent I/O command
`block, that is other than a head of chain I/O command block
`and an end of chain I/O command block, the counter is
`configured to a number of I/O command blocks immediately
`preceding the non—concurrent I/O command block. When an
`immediately preceding I/O command block is a last I/O
`command block in a string of concurrent I/O command
`blocks, the number of I/O command blocks immediately
`preceding the non-concurrent I/O command block includes
`all I/O command blocks in the string. For a focal I/O
`command block,
`the counter is configured to indicate a
`number of execution paths that converge in the focal I/O
`command block when none of the execution paths are from
`a string of concurrent I/O command blocks.
`For a concurrent I/O command block that is at the head of
`a string of concurrent I/O command blocks and that is other
`than a head of chain [/0 command block, the counter is
`configured to a number of I/O command blocks immediately
`preceding the concurrent [/0 command block. When an
`immediately preceding I/O command block is a last I/O
`command block in another string of concurrent I/O com-
`mand blocks, the number of [/0 command blocks immedi-
`ately preceding the concurrent I/O command block includes
`all I/O command blocks in the another string.
`For an I/O command block at the end of a chain,
`counter is configured to the sum of:
`a.) the number of non-concurrent I/O command blocks
`immediately preceding the I/O command block;
`b.) the total number of concurrent I/O command blocks in
`strings immediately preceding the I/O command block;
`and
`
`the
`
`c.) the number ‘1’ if the I/O command block is part of a
`string of concurrent I/O command blocks.
`In another operation of the method, a next block pointer
`in an I/O command block in the chain is set to point to
`another I/O command block in the chain. Yet another
`operation specifies an I/O command block that is to be
`simultaneously enabled for execution with at least one other
`I/O command block in a string of concurrent I/O command
`blocks by configuring a concurrent flag in the I/O command
`block. Still another operation configures a pair of I/O
`command blocks in the chain as killer I/O command blocks.
`In another embodiment,
`the method for sequencing
`execution of a chain of I/O command blocks that includes a
`plurality of chain execution paths, and for sequencing
`execution of I/O command blocks within a chain execution
`path using only information in the I/O command blocks
`includes configuring a chain control block structure for each
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`I/O command block in a first set of I/O command blocks (i)
`to identify a first chain execution path of the chain that
`includes each I/O command block in the first set of I/O
`commands blocks, and (ii)
`to specify the sequence of
`execution of the I/O command blocks within the first chain
`execution path. According to this method, a control block
`structure for each I/O command block in a second set of I/O
`command blocks is configured (i)
`to identify a second
`execution path of the chain that includes each [/0 command
`block in the second set of I/O command blocks, and (ii) to
`specify the sequence of execution of the I/O command
`blocks within the second execution path. Finally a chain
`control block structure for an I/O command block is con-
`figured as a focal I/O command block for the first and second
`execution paths of the chain.
`After the chain is configured and stored in a memory, a
`chain manager executing on a host adapter processor pro-
`cesses the chaining information in each I/O control block. In
`one embodiment, an I/O command in an I/O command block
`in the chain is executed first. The 1/0 command is executed
`in a manner that
`is similar to execution of a prior art
`unchained I/O command. However, some additional firm-
`ware may be included to allow aborting an I/O command in
`the chain. However, upon completion of execution of the I/O
`command, the chain manager is executed.
`The chain manager examines the chain control field in an
`I/O command block pointed to by a next block pointer in the
`I/O command block. Upon examining the chain control
`field, the chain manager performs at least one operation from
`a plurality of operations. The at
`least one operation is
`selected based on a state of the chain control byte of the I/O
`command block pointed to by the next block pointer
`In one embodiment, the at least one operation includes
`reading a progress count, i.e., the counter described above,
`in the chain control byte in the next I/O command block. The
`chain manager checks the read progress count to determine
`whether the next I/O command block is a skipped I/O
`command block or an unskipped I/O command block.
`If the next I/O command block is an unskipped I/O
`command block, the chain manager decrements the progress
`count. The chain manager then checks the progress count to
`determine if the next I/O command block is ready for
`execution. The chain manager returns the host adapter
`processor to an idle state upon the progress count indicating
`the next I/O command block is not ready for execution.
`Conversely, if the next I/O command block is ready for
`execution, the chain manager determines whether the next
`I/O command block has been enabled for execution. If the
`next [/0 command block was enabled for execution, the
`chain manager posts completion of execution of the chain of
`I/O command blocks. Alternatively,
`the chain manager
`enables execution of the next I/O command block upon
`determining that the next I/O command block has not been
`enabled for execution.
`
`When the initial check of the progress count shows that
`the I/O command block is a skipped I/O command block, the
`chain manager skips to the first I/O command block on the
`chain path that is an unskipped I/O command block. The
`chain manager decrements a progress count in the unskipped
`I/O command block and then performs each of the opera-
`tions described above after decrementing the progress count
`using the unskipped I/O command block.
`While the above method of making and using the struc—
`ture of this invention has great flexibility and power com-
`pared to the prior art method, individual methods within the
`overall method also provide a new level of capability. For
`example, a method for specifying concurrent execution of a
`
`DELL Ex.1048.023
`Ex.1048.023
`
`DELL
`
`

`

`5,892,969
`
`7
`string of I/O command blocks stored in a memory using only
`information in the string of I/O command blocks allows
`concurrent execution of a plurality of I/O commands.
`In one embodiment, the method first configures one I/O
`command block in the string as a head of string concurrent
`I/O command block. Another I/O command block in the
`string is configured as an end of string concurrent I/O
`command block. The remaining 1/0 command blocks, i.e.,
`all other I/O command blocks, in the string are configured as
`concurrent skipped I/O command blocks.
`To configure one [/0 command block in the string as a
`head of string concurrent I/O command block, a concurrent
`flag is set in the head of string concurrent I/O command
`block. A counter in the head of a string of concurrent I/O
`command block is configured to a number of I/O command
`blocks immediately preceding the head of string concurrent
`I/O command block. When an immediately preceding I/O
`command block is a last [/0 command block in another
`string of concurrent I/O command blocks, the number of I/O
`command blocks immediately preceding the head of con-
`current I/O command block includes all I/O command
`blocks in the another string.
`The process of configuring all other I/O command blocks
`in the string as concurrent skipped [/0 command blocks
`includes setting a concurrent flag in each of the all other I/O
`command blocks in the string. Also, a counter in the each of
`the all other I/O command blocks in the string is set to an
`illegal value, e.g., a maximum value.
`The process of configuring one I/O command blocks in
`the string as an end of string concurrent I/O command block
`includes resetting a concurrent flag in the end of string
`concurrent I/O command block. Also, a counter in the end of
`string concurrent I/O command block is configured to the
`illegal value when the end of string concurrent I/O command
`block is not a focal [/0 command block. When the end of
`string I/O block is also the end of chain I/O block,
`the
`counter is configured to the sum of:
`a.) the number of non-concurrent 1/0 command blocks
`immediately preceding the end of string concurrent I/O
`command block;
`b.) the total number of concurrent 1/0 command blocks in
`strings immediately preceding the end of string con-
`current I/O command block; and
`c.) the number one.
`Another method of this invention, permits one I/O com-
`mand block in a chain to kill another I/O command block in
`the chain when the execution of the one I/O command block
`reaches a specified point. Specifically, a method for speci-
`fying abortion of one of a pair of I/O command blocks in a
`cha