Hardware mechanism for managing cache structures in a data storage system

• US 6,216,199 B1
• Filed: 08/04/1999
• Issued: 04/10/2001
• Est. Priority Date: 08/04/1999
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Kloeppner, John Richard, Gates, Dennis Eugene, DeKoning, Rodney Allen
• Primary Examiner(s): Nguyen, Hiep T.
• Application Number:
  US09/366,827
• Time in Patent Office: 615 Days
• Field of Search: 711/3, 711/118, 711/137, 707/102
• US Class Current: 711/3
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space

Abstract

A system and method for managing data stored in a cache block in a cache memory includes a cache block is located at a cache block address in the cache memory, and the data in the cache block corresponds to a storage location in a storage array identified by a storage location identifier. A storage processor accesses the cache block in the cache memory and provides a cache management command to a command processor. A processor memory coupled to the storage processor stores a search key based on the storage location identifier corresponding to the cache block. A command processor coupled to the storage processor receives a cache management command specified by the storage processor and transfers the storage location identifier from the processor memory. A cache management memory stores a cache management structure including the cache block address and the search key. A cache management processor is coupled to the cache management memory by a second link to manipulate the cache management structure in a hash table with linked lists at each hash queue element within the cache management memory in accordance with the cache management command and the search key.

Claims

1. A system for managing data stored in a cache block in a cache memory, the cache block being located at a cache block address in the cache memory, wherein the data in the cache block corresponds to a storage location in a storage array identified by a storage location identifier, the system comprising:

a storage processor that accesses the cache block in the cache memory and provides a cache management command;

a processor memory coupled to the storage processor that stores a search key based on the storage location identifier corresponding to the cache block;

a command processor coupled to the storage processor, said command processor receives a cache management command specified by the storage processor and transfers the storage location identifier from the processor memory;

a cache management memory that stores a cache management structure including the cache block address and the search key; and

a cache management processor coupled to the cache management memory to manipulate the cache management structure in a linked data structure within the cache management memory in accordance with the cache management command and the search key.

2. The system of claim 1 wherein the storage element identifier includes a logical unit number associated with a storage disk.

3. The system of claim 1 wherein the storage element identifier includes a logical block addressing address associated with the storage location of a storage disk.

4. The system of claim 1 wherein the cache management processor comprises:

an insert module that inserts the cache management structure in the linked data structure in accordance with the search key, wherein the cache management structure stores the cache block address.

5. The system of claim 1 wherein the cache management processor comprises:

a search module that searches for the cache management structure in the linked data structure in accordance with the search key and provides the cache block address stored in the cache management structure to the storage processor, if the cache management structure is found.

6. The system of claim 1 wherein the cache management processor comprises:

a delete module that deletes from the linked data structure the cache management structure corresponding to the search key.

7. The system of claim 1 wherein the cache management processor comprises:

a hashing module that hashes on the search key to generate an identifier corresponding to the linked data structure stored in the cache management memory.

8. The system of claim 1 wherein the linked data structure comprises a binary tree and the cache management processor comprises a balancing module that balances the binary tree responsive to the cache management command.

9. The system of claim 1 wherein the cache management structure comprises a recovery control block including a status value indicating whether the cache block associated with the cache management structure is valid.

10. The system of claim 1 wherein the cache management structure comprises a recovery control block including a status value indicating whether the cache block associated with the cache management structure is dirty.

11. The system of claim 1 wherein the cache management structure comprises a recovery control block including a status value indicating whether the cache block associated with the cache management structure is mirrored.

12. The system of claim 1 wherein the cache management memory comprises battery backed memory.

13. A method for managing data stored in a cache block in a cache memory, the cache block being located at a cache block address in the cache memory, wherein the data in the cache block corresponds to a storage location in a storage array identified by a storage location identifier, the method comprising:

receiving a cache management command from a storage processor;

receiving from the storage processor a processor memory address associated with a search key based on the storage location identifier;

transferring the search key from the processor memory in accordance with the processor memory address;

manipulating a cache management structure in a linked data structure in the cache management memory in accordance with the cache management command and the search key.

14. The method of claim 13 further comprising:

transferring cache management data associated with the search key from processor memory to the cache management structure in the cache management memory.

15. The method of claim 13 wherein the manipulating operation comprises inserting the cache management structure into the linked data structure in accordance with the search key, wherein the cache management structure stores the cache block address.

16. The method of claim 13 wherein the manipulating operation comprises deleting the cache management structure from the linked data structure in accordance with the search key.

17. The method of claim 13 wherein the manipulating operation comprises searching for the cache management structure in the linked data structure in accordance with the search key and returning the cache block address stored in the cache management structure to the storage processor.

18. The system of claim 13 further comprising:

hashing on the search key to generate an identifier corresponding to the linked data structure stored in the cache management memory.

19. The method of claim 13 wherein the linked data structure comprises a binary tree and further comprising balancing the binary tree responsive to the cache management command.