Buffer management and system coordination method

A controller for providing access to a data buffer, the data buffer including a plurality of data blocks for storing data retrieved from or to be stored in a storage device, each data block having a size and an address, the controller comprising:

• (a) a buffer list including a plurality of entries each corresponding to a data block, each entry for maintaining a partial address common to both the next buffer list entry and a data block corresponding to said next buffer list entry;
• (b) a buffer list register for maintaining a memory address of the buffer list;
• (c) an offset register for maintaining a partial address common to both a buffer list entry and the corresponding data block;
• and
• (d) a logic circuit configured by program instructions to provide access to the data blocks, said logic circuit:
• (i) calculates the address of a buffer list entry by steps including adding the partial address in the offset register to the buffer list base address in the buffer list base address register;
• and
• (ii) calculates the address of the corresponding data block by steps including multiplying the partial address in the offset register with said data block size.

A controller for coordinating transfer of data into and out of a data buffer, the data buffer including a plurality of data blocks each for storage of data retrieved from, or to be stored into, a storage device, the controller comprising:

• (a) a buffer list including a plurality of entries each corresponding to a data block, each entry for maintaining a status code selected from a cyclical set of sequential status codes having a period of N, the status codes sequentially, and alternately, representing the most recent history of a data block, said status codes including:
• (i) full status, indicating data in the data block has been retrieved from the storage device or is to be stored to the storage device, and (ii) empty status, indicating data has been transferred out of the data block to a host or to the storage device;
• (b) a store flag for maintaining a status code from said cyclical set representing empty status;
• (c) a retrieve flag for maintaining a status code from said cyclical set representing full status, the retrieve flag status code immediately following or immediately preceding the store flag status code in said cyclical set;
• and
• (d) a logic circuit configured by program instructions to control the storing of data into, and retrieving of data from the data buffer, said logic circuit:
• (1) when storing data into the data buffer:
• (i) locates in said buffer list a desired entry;
• (ii) stores data into the corresponding data block when the status code of the entry matches the store flag status code, representing a corresponding empty data block;
• (iii) updates the entry with a status code from said cyclical set next in sequence to the store flag status code, indicating the data block is full;
• and
• (iv) if the entry is at the end of the buffer list, updates the store flag by sequentially advancing the store flag status code in said cyclical set twice;
• and
• (2) when retrieving data from the data buffer:
• (i) locates in said buffer list a desired entry;
• (ii) retrieves data from the corresponding data block when the status code of the entry matches the retrieve flag status code, representing a corresponding full data block;
• (iii) updates the entry with a status code from said cyclical set next in sequence to the retrieve flag status code, indicating the data block is empty;
• and
• (iv) if the entry is at the end of the buffer list, updates the retrieve flag by sequentially advancing the retrieve flag status code in said cyclical set twice.

In a data buffer system comprising a data buffer for storing data retrieved from or to be stored in a storage device, the data buffer including a plurality of data blocks for storing data, each data block having a size and an address, a method of providing access to, and coordinating transfer of data into and out of, the data blocks comprising the steps of:

• (a) maintaining a buffer list including a plurality of entries each corresponding to a data block, each entry including (i) a partial address common to both the next buffer list entry and a data block corresponding to said next buffer list entry, and (ii) a status code selected from a cyclical set of sequential status codes having a period of N, the status codes sequentially, and alternately, representing the most recent history of a data block, said status codes including:
• (1) full status, indicating data in the data block has been retrieved from the storage device or is to be stored to the storage device, and (2) empty status, indicating data has been transferred out of the data block to a host or to the storage device;
• (b) maintaining in a store flag, a store flag status code consisting of one of said status codes from said cyclical set representing empty status;
• (c) maintaining in a retrieve flag, a retrieve flag status code consisting of one said status codes from said cyclical set representing full status, the retrieve flag status code immediately following or immediately preceding the store flag status code in said cyclical set;
• (d) initializing each entry of the buffer list to empty status code;
• (e) maintaining in a buffer list register, a memory address of the buffer list;
• (f) storing in an offset register, a partial address common to both a current buffer list entry and the corresponding data block;
• (g) when storing data into the data buffer:
• (1) traversing the buffer list to locate a desired entry by:
• (i) calculating the address of the current entry by steps including adding the partial address in the offset register to the buffer list base address in the buffer list base address register;
• (ii) determining if the current entry is the desired entry;
• (iii) if not, storing into the offset register, the partial address in the current entry, said partial address being common to both the next buffer list entry and a corresponding data block, and repeating steps (i)-(ii);
• (2) storing data into the data block corresponding to the desired entry with a status code matching the store flag status code, including:
• (i) calculating the address of the corresponding data block by steps including multiplying the partial address in the offset register with said data block size, and (ii) accessing the data block at the calculated block address and storing data therein when the status code of the entry matches the store flag status code;
• (3) accessing the entry at the entry address to update the entry with a status code from said cyclical set next in sequence to the store flag status code, indicating the corresponding data block is full;
• and
• (4) if the entry is at the end of the buffer list, updating the store flag by sequentially advancing the store flag status code in said cyclical set twice;
• and
• (h) when retrieving data from the data buffer:
• (1) traversing the buffer list to locate a desired entry by:
• (i) calculating the address of the current entry by steps including adding the partial address in the offset register to the buffer list base address in the buffer list base address register, (ii) determining if the current entry is the desired entry;
• (iii) if not, storing into the offset register, the partial address in the current entry, said partial address being common to both the next buffer list entry and a corresponding data block, and repeating steps (i)-(ii);
• (2) storing data into the data block corresponding to the desired entry with a status code matching the retrieve flag status code, including:
• (i) calculating the address of the corresponding data block by steps including multiplying the partial address in the offset register with said data block size, and (ii) accessing the data block at the calculated block address and retrieving data therefrom when the status code of the entry matches the retrieve flag status code;
• (3) accessing the entry at the entry address to update the entry with a status code from said cyclical set next in sequence to the retrieve flag status code, indicating the corresponding data block is empty;
• and
• (4) if the entry is at the end of the buffer list, updating the retrieve flag by sequentially advancing the retrieve flag status code in said cyclical set twice.

In a data buffer system comprising at least one data buffer for storing data retrieved from or to be stored in a storage device, the data buffer including a plurality of data blocks each for the storage of data, a method of coordinating storing of data into and retrieving of data from the data buffer, comprising the steps of:

• (a) maintaining a buffer list including a plurality of entries each corresponding to a data block, each entry including a status code selected from a cyclical set of sequential status codes having a period of N, the status codes sequentially, and alternately, representing the most recent history of a data block, said status codes including:
• (i) full status, indicating data in the data block has been retrieved from the storage device or is to be stored to the storage device, and (ii) empty status, indicating data has been transferred out of the data block to a host or to the storage device;
• (b) maintaining in a store flag, a store flag status code consisting of one of said status codes from said cyclical set representing empty status;
• (c) maintaining in a retrieve flag, a retrieve flag status code consisting of one of said status codes from said cyclical set representing full status, the retrieve flag status code immediately following or immediately preceding the store flag status code in said cyclical set;
• (d) initializing each entry of the buffer list to empty status code;
• (e) when storing data into the data buffer:
• (i) locating in said buffer list a desired entry;
• (ii) storing data into the corresponding data block when the status code of the entry matches the store flag status code, representing a corresponding empty data block;
• (iii) updating the entry with a status code from said cyclical set next in sequence to the store flag status code, indicating the data block is full;
• and
• (iv) if the entry is at the end of the buffer list, updating the store flag by sequentially advancing the store flag status code in said cyclical set twice;
• and
• (f) when retrieving data from the data buffer:
• (i) locating in said buffer list a desired entry;
• (ii) retrieving data from the corresponding data block when the status code of the entry matches the retrieve flag status code, representing a corresponding full data block;
• (iii) updating the entry with the status code from said cyclical set next in sequence to the retrieve flag status code, indicating the data block is empty;
• and
• (iv) if the entry is at the end of the buffer list, updating the retrieve flag by sequentially advancing the retrieve flag status code in said cyclical set twice.

In a computer system comprising at least one host connected to at least one disk drive through a data buffer system, the data buffer system comprising at least one data buffer for storing data retrieved from or to be stored in the disk drive, the data buffer including a plurality of data blocks each for the storage of data, a method of coordinating storing of data into and retrieving of data from the data buffer by the host and by the disk drive, the method comprising the steps of:

• (a) maintaining a buffer list including a plurality of entries each corresponding to a data block, each entry including a status code selected from a cyclical set of sequential status codes having a period of N, the status codes comprising 0, 1, . . . , N-1, and sequentially, and alternately, representing the most recent history of a data block, said status codes including:
• (i) full status, indicating data has been stored into the data block by the disk drive or by the host, and (ii) empty status, indicating data has been retrieved from the data block by the host or by the disk drive;
• (b) maintaining in a store flag, a store flag status code consisting of one of said status codes from said cyclical set representing empty status;
• (c) maintaining in a retrieve flag, a retrieve flag status code consisting of one of said status codes from said cyclical set representing full status, the retrieve flag status code immediately following or immediately preceding the store flag status code in said cyclical set;
• (d) initializing each entry of the buffer list to empty status code;
• (e) when storing data into the data buffer:
• (i) locating in said buffer list a desired entry;
• (ii) storing data into the corresponding data block when the status code of the entry matches the store flag status code, representing a corresponding empty data block;
• (iii) updating the entry with a status code from said cyclical set next in sequence to the store flag status code, indicating the data block is full;
• and
• (iv) if the entry is at the end of the buffer list, updating the store flag by sequentially advancing the store flag status code in said cyclical set twice;
• and
• (f) when retrieving data from the data buffer:
• (i) locating in said buffer list a desired entry;
• (ii) retrieving data from the corresponding data block when the status code of the entry matches the retrieve flag status code, representing a corresponding full data block;
• (iii) updating the entry with the status code from said cyclical set next in sequence to the retrieve flag status code, indicating the data block is empty;
• and
• (iv) if the entry is at the end of the buffer list, updating the retrieve flag by sequentially advancing the retrieve flag status code in said cyclical set twice.

In a data buffer system comprising a data buffer for storing data retrieved from or to be stored in a storage device, the data buffer including a plurality of data blocks for storing data, each data block organized in data sectors having a size, an offset within the data block, and an address, a method of providing access to the data blocks comprising the steps of:

• (a) maintaining a buffer list including a plurality of entries each corresponding to a data block, each entry including a partial address common to both the next buffer list entry and a data block corresponding to said next buffer list entry;
• (b) maintaining in a buffer list register, a memory address of the buffer list;
• (c) storing in an offset register, a partial address common to both a buffer list entry and the corresponding data block;
• (d) calculating the address of the buffer list entry by steps including adding the partial address in the offset register to the buffer list base address in the buffer list base address register;
• (e) calculating the address of a sector within the corresponding data block by steps including multiplying said sector size with the sum of the corresponding sector offset and the partial address in the offset register;
• and
• (f) traversing the buffer list by storing into the offset register the partial address in a buffer list entry, said partial address being common to both the next buffer list entry and a corresponding data block, and repeating steps (d) and (e) for said next buffer list entry and said corresponding data block.

In a data buffer system comprising a data buffer for storing data retrieved from or to be stored in a storage device, the data buffer including a plurality of data blocks for storing data, each data block having a size and an address, a method of providing access to the data blocks comprising the steps of:

• (a) maintaining a buffer list including a plurality of entries each corresponding to a data block, each entry including a partial address common to both the next buffer list entry and a data block corresponding to said next buffer list entry;
• (b) maintaining in a buffer list base address register, the base memory address of the buffer list;
• (c) storing in an offset register, a partial address common to both a buffer list entry and the corresponding data block;
• (d) calculating the address of the buffer list entry by steps including adding the partial address in the offset register to the buffer list base address in the buffer list base address register;
• and
• (e) calculating the address of the corresponding data block by steps including multiplying the partial address in the offset register with said data block size.