Method and apparatus for computer disk cache management

Claim 3

The apparatus according to claim 1 wherein said determining means comprises a hash table containing a plurality of pointers, and a plurality of doubly-linked lists of headers wherein each one of said plurality of pointers points to a corresponding doubly-linked list of said plurality of doubly-linked lists and each header identifies a corresponding block of data contained within the cache.

Claim 4

The apparatus according to claim 2 wherein said header comprises: a forward pointer, a backward pointer, a frequency member, a timestamp member, a ValidMap member, a DirtyMap member, a status member, a volume member, an address member, an index member and a data pointer.

Claim 5

The apparatus according to claim 3 wherein said ValidMap member is a bitmap containing a plurality of bits having a one-to-one correspondence with a plurality of data blocks contained within the cache and wherein one of said bits will indicate whether its corresponding data block is contained within the cache.

Claim 6

The apparatus according to claim 4 wherein said DirtyMap is a bitmap containing a plurality of bits having a one-to-one correspondence with said plurality of data blocks contained within the cache and wherein one of said bits will indicate whether its corresponding data block is contained within the cache.

Claim 7

In a computer disk storage system having one or more direct access storage devices, a cache and a cache controller, a method for computer disk cache management comprising the steps of: determining, in response to a request received from an external source for a data block, whether said data block is contained within the cache by: producing an index into an array of pointers by hashing an identifier of said data block; traversing a doubly-linked list of headers pointed to by a pointer, said pointer being located in said array of pointers at an index position, and wherein each of said headers contains a valid indicator which indicates the presence of said block in the cache and a dirty indicator which indicates whether said block in the cache has been modified; and examining the indicator in each of said headers in the doubly-linked list until said block has been located or each of said headers has been examined; identifying, in the event of a cache miss, a victim cache line in the cache for replacement by: selecting a best victim from a heap having a plurality of nodes wherein each node identifies a possible victims and wherein said best victim is indicated by a first entry in the heap; reordering the heap after accessing a block in the cache, by performing a local reorganization such that the heap is in least-frequently-used order further subject to an age rule; and periodically checking the dirty indicator contained in the headers and flushing a cache line containing a dirty block to the direct access storage device.

Claim 8

In a computer disk storage system having one or more direct access storage devices, a cache and a cache controller, a method for computer disk cache management comprising the steps of: determining, in response to a request received from an external source for a data block, whether said data block is contained within the cache by: producing an index into an array of pointers by hashing an identifier of said data block; traversing a doubly-linked list of headers pointed to by a pointer, said pointer being located in said array of pointers at an index position, and wherein each of said headers contains a valid indicator which indicates the presence of said block in the cache and a dirty indicator which indicates whether said block in the cache has been modified; and examining the indicator in each of said headers in the doubly-linked list until said block has been located or each of said headers has been examined; identifying, in the event of a cache miss, a victim cache line in the cache for replacement by: selecting a best victim from a heap having a plurality of nodes wherein each node identifies a possible victims and wherein said best victim is indicated by a first entry in the heap; reordering the heap after accessing a block in the cache, by performing a local reorganization such that the heap is in least-frequently-used order further subject to an age rule; and periodically checking the dirty indicator contained in the headers and flushing a cache line containing a dirty block to the direct access storage device.

Claim 9

The method according to claim 6 wherein said heap is implicitly implemented as an indexed array of elements, wherein a one-to-one correspondence exists between a single element in the array and a single node in the heap.

Claim 10

The method according to claim 7 wherein said valid indicator is a bitmap containing a plurality of bits having a one-to-one correspondence with a plurality of data blocks contained within the cache and wherein one of said bits will indicate whether its corresponding data block is contained within the cache.

Claim 11

The method according to claim 8 wherein said dirty indicator is a bitmap containing a plurality of bits having a one-to-one correspondence with said plurality of data blocks contained within the cache and wherein one of said bits will indicate whether its corresponding data block is contained within the cache.

Claim 12

The method according to claim 9 wherein said index producing step comprises: hashing a data block number with a hash function such that an index into a hash table is produced.