Method and apparatus for reliably storing data to be written to a peripheral device subsystem using plural controllers

Claim 2

In a computer system including a central processor coupled to first and second redundant peripheral device controllers coupled together by a communications path, each including a cache memory, wherein the cache memory in the second controller contains an array of pointers each capable of pointing to a block of memory in the cache memory of the second controller, and the cache memory in the first controller contains a stack containing a plurality of entries, each stack entry containing data representing a respective one of the pointers in the array of pointers, a method for reliably storing write data comprising the steps of: receiving write data from the central processor in the first controller; storing the write data in the cache memory of the first controller; transmitting a copy of the write data from the first controller to the second controller via the communications path by: popping the top stack entry off the stack; appending the pointer representative data contained in the popped stack entry to the copy of the write data; and transmitting the combination of the pointer representative data and the copy of the write data to the second controller; and storing the transmitted copy of the write data in the cache memory of the second controller by: storing the transmitted copy of the write data in a block of memory in the cache memory of the second controller; and storing a pointer to the block of memory containing the transmitted copy of the write data in the one of the pointers in the array of pointers represented by the appended pointer representative data; and processing the write data in the first controller.

Claim 3

The method of claim 1, wherein the first controller is subject to failure, and further comprising the step of, if the first controller fails, processing the copy of the write data in the second controller.

Claim 4

The method of claim 2 wherein the step of processing the copy of the write data in the second controller comprises the steps of: traversing every one of the pointers in the array of pointers in cache memory of the second controller; and if the one of the pointers points to a block containing a copy of write data, processing the copy of write data contained in the block pointed to by the one of the pointers in the second controller.

Claim 5

The method of claim 3 wherein: the step of storing the copy of the write data in a block of memory in the cache memory of the second controller comprises the step of appending a time code to the block of memory containing the write data; and the step of processing the copy of the write data in the second controller further comprises, before the traversing step, the steps of: sorting the entries in the array of pointers based on the value of the time code appended to the write data; and traversing every entry in the array of pointers in sorted order.

Claim 6

The method of claim 4 wherein the step of appending a time code comprises the steps of: appending the value of a counter to the block of memory containing the write data; and incrementing the counter.

Claim 7

The method of claim 5 further comprising the steps of: periodically resequencing the time code values appended to the blocks of memory containing write data; and resetting the value of the counter.

Claim 8

The method of claim 1, wherein the cache memory in the first controller further contains a tag array, containing a plurality of tag entries, and wherein: the step of storing write data in the first controller comprises the steps of: storing the write data in a data block in the cache memory of the first controller; allocating a tag entry to correspond to the data block containing the write data; and storing a pointer to the data block containing the write data in the allocated tag entry; the transmitting step further comprises the step of, after the popping step, storing the pointer representative data in the allocated tag entry; and the processing step comprises the steps of: selecting an entry in the tag array; processing the data block corresponding to the selected tag entry; pushing the pointer representative data in the selected tag entry onto the stack; and releasing the tag entry.

Claim 9

The method of claim 1, further comprising, after the step of storing the transmitted copy of the write data, the step of returning an acknowledgement from the second controller to the first controller via the communications path.

Claim 10

The method of claim 8, further comprising, after the acknowledgement step, the step of notifying the central processor that the write data has been successfully received.

Claim 11

The method of claim 1, wherein the first controller is subject to failure, and further comprising the step of, if the first controller #ails, processing the copy of the write data in the second controller.

Claim 12

The method of claim 10, wherein the system further comprises a peripheral device coupled to the first and second controllers, and the step of processing the copy of the write data comprises the step of writing the copy of the write data from the second controller to the peripheral device.

Claim 13

The method of claim 1, wherein the system further comprises a peripheral device coupled to the first and second controllers, and the processing step comprises the step of writing the write data from the first controller to the peripheral device.

Claim 14

A computer system comprising: a central processor, for producing write data; first and second redundant peripheral device controllers, each coupled to the central processor and including a respective cache memory; and a communications path coupled between the first and second controllers; wherein: the first controller comprises: circuitry for receiving the write data from the central processor; circuitry for storing the write data in its cache memory circuitry for maintaining in its cache memory a stack containing a plurality of entries, each stack entry containing data representing a respective one of an array of pointers maintained in the cache memory of the second controller; circuitry for transmitting a copy of the write data from the first controller to the second controller via the communications path, wherein the transmitting circuitry comprises: circuitry for popping the top stack entry off the stack; circuitry for appending the pointer representative data contained in the popped stack entry to a copy of the write data; and circuitry for transmitting the combination of the pointer representative data and the copy of the write data to the second controller; and circuitry for processing the write data; and wherein: the second controller comprises: circuitry for maintaining in its cache memory an array of pointers each capable of pointing to a block of memory in its cache memory; circuitry for storing the transmitted copy of he write data in its cache memory, wherein the circuitry for storing the transmitted copy of the write data comprises: circuitry for storing the transmitted copy of the write data in a block of memory in the cache memory of the second controller; and circuitry for storing a pointer to the block of memory containing the transmitted copy of the write data in the one of the pointers in the array of pointers represented by the appended pointer representative data.

Claim 15

A computer system comprising: a central processor, for producing write data; first and second redundant peripheral device controllers, each coupled to the central processor and including a respective cache memory; and a communications path coupled between the first and second controllers; wherein: the first controller comprises: circuitry for receiving the write data from the central processor; circuitry for storing the write data in its cache memory circuitry for maintaining in its cache memory a stack containing a plurality of entries, each stack entry containing data representing a respective one of an array of pointers maintained in the cache memory of the second controller; circuitry for transmitting a copy of the write data from the first controller to the second controller via the communications path, wherein the transmitting circuitry comprises: circuitry for popping the top stack entry off the stack; circuitry for appending the pointer representative data contained in the popped stack entry to a copy of the write data; and circuitry for transmitting the combination of the pointer representative data and the copy of the write data to the second controller; and circuitry for processing the write data; and wherein: the second controller comprises: circuitry for maintaining in its cache memory an array of pointers each capable of pointing to a block of memory in its cache memory; circuitry for storing the transmitted copy of he write data in its cache memory, wherein the circuitry for storing the transmitted copy of the write data comprises: circuitry for storing the transmitted copy of the write data in a block of memory in the cache memory of the second controller; and circuitry for storing a pointer to the block of memory containing the transmitted copy of the write data in the one of the pointers in the array of pointers represented by the appended pointer representative data.

Claim 16

The system of claim 13, wherein the first controller is subject to failure, and the second controller further comprises circuitry for processing the copy of the write data in the second controller, if the first controller fails.

Claim 17

The system of claim 14, wherein the circuitry for processing the copy of the write data in the second controller comprises: circuitry for traversing every one of the pointers in the array of pointers in cache memory of the second controller; and circuitry for processing the copy of write data contained in the block pointed to by the one of the pointers in the second controller if the one of the pointers points to a block containing a copy of write data.

Claim 18

The system of claim 15, wherein: the circuitry for storing the copy of the write data in a block of memory in the cache memory of the second controller comprises circuitry for appending a time code to the block of memory containing the write data; and the circuitry for processing the copy of the write data in the second controller further comprises: circuitry for sorting the entries in the array of pointers based on the value of the time code appended to the write data; and circuitry for traversing every entry in the array of pointers in sorted order.

Claim 19

The system of claim 16, wherein the circuitry for appending a time code comprises: circuitry for appending the value of a counter to the block of memory containing the write data; and circuitry for incrementing the counter.

Claim 20

The system of claim 17 wherein the second controller further comprises: circuitry for periodically resequencing the time code values appended to the blocks of memory containing write data; and circuitry for resetting the value of the counter.

Claim 21

The system of claim 13, wherein: the first controller further comprises circuitry for maintaining a tag array, containing a plurality of tag entries, in its cache memory; the circuitry for storing write data in the first controller comprises: circuitry for storing the write data in a data block in the cache memory of the first controller; circuitry for allocating a tag entry to correspond to the data block containing the write data; and circuitry for storing a pointer to the data block containing the write data in the allocated tag entry; the transmitting circuitry further comprises circuitry for storing the pointer representative data in the allocated tag entry; and the processing circuitry comprises: circuitry for selecting an entry in the tag array; circuitry for processing the data block corresponding to the selected tag entry; circuitry for pushing the pointer representative data in the selected tag entry onto the stack; and circuitry for releasing the tag entry.

Claim 22

The system of claim 13, wherein the second controller further comprises circuitry for returning an acknowledgement from the second controller to the first controller via the communications path when the transmitted copy of the write data has been stored.

Claim 23

The system of claim 20, wherein the first controller further comprises circuitry, responsive to an acknowledgement received from the second controller, for notifying the central processor that the write data has been successfully received.

Claim 24

The system of claim 13, wherein the first controller is subject to failure, and the second controller further comprises circuitry for processing the copy of the write data in the second controller, if the first controller fails.

Claim 25

The system of claim 22, further comprising a peripheral device coupled to the first and second controllers, wherein the circuitry in the second controller for processing the copy of the write data comprises circuitry for writing the copy of the write data from the second controller to the peripheral device.

Claim 26

The system of claim 13, further comprising a peripheral device coupled to the first and second controllers, wherein the processing circuitry in the first controller comprises circuitry for writing the write data from the first controller to the peripheral device.

Claim 27

The system of claim 13, wherein: the first controller comprises a resident processor, and the receiving, storing, transmitting and processing circuitry are comprised in its resident processor; and the second controller comprises a resident processor, and the storing circuitry is comprises in its resident processor.