Mapping engine for a storage device

• US 8,402,198 B1
• Filed: 05/28/2010
• Issued: 03/19/2013
• Est. Priority Date: 06/03/2009
• Status: Active Grant

• Current Assignee: Innovations In Memory LLC
• Original Assignee: Violin Memory Incorporated
• Inventors: de la Iglesia, Erik, Sikdar, Som, Parker, David, Sivaram, Dommeti
• Primary Examiner(s): PEUGH, BRIAN R
• Application Number:
  US12/790,255
• Time in Patent Office: 1,026 Days
• Field of Search: None
• US Class Current: 711/3
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache

Abstract

A hardware search structure quickly determines the status of cache lines associated with a large disk array and at the same time reduces the amount of memory space needed for tracking the status. The search structure is configurable in hardware to different cache line sizes and different primary and secondary index sizes. A maintenance feature invalidates state record entries based both on their time stamps and on associated usage statistics.

Claims

1. An apparatus, comprising:

a primary index table configured to store primary index entries;

a secondary index table configured to store index groups referenced by the primary index entries, wherein the index groups contain pointers; and

a state records table configured to store state record entries referenced by the pointers in the index groups, wherein the state record entries identify storage locations in a cache resource.

2. The apparatus according to claim 1 wherein the primary index entries map to substantially all data blocks in a disk array and wherein the secondary index table map cache lines to a subset of any of the data blocks.

3. The apparatus according to claim 1 wherein:

a primary index address section of a storage address is configured as an address or offset into the primary index table;

a secondary index address section of the storage address is configured as an address or offset into the secondary index table; and

a cache line offset section of the storage address is configured as an offset into a cache line in the cache resource.

4. The apparatus according to claim 3 wherein the number of bits in the primary index address section, secondary index address section, and cache line offset section are configurable according to memory access patterns.

5. The apparatus according to claim 1 wherein the state record entries include timestamp values that identify when associated cache lines were accessed, and wherein the associated cache lines are invalidated according to the timestamp values.

6. The apparatus according to claim 5 wherein the state record entries include statistics counter values that identify access patterns for the associated cache lines, wherein the cache lines are invalidated according to both the associated timestamp values and statistics counter values.

7. The apparatus according to claim 1 wherein the state record entries include state information indicating a validity status for associated cache lines.

8. The apparatus according to claim 1 wherein the state record entries include cache pointers that point to the storage locations in the cache resource.

9. The apparatus according to claim 1 wherein the state record entries reference different blocks of data in the cache resource.

10. A storage device, comprising:

a proxy engine configured to receive storage addresses associated with storage locations in a storage array;

a mapping engine configured to map the storage addresses to cache lines in a cache resource; and

a hardware based search structure configured to identify the status of the cache lines.

11. The storage device according to claim 10 wherein the search structure includes a primary index table addressed by a first section of the storage addresses and a secondary index table addressed by a second section of the storage addresses.

12. The storage device according to claim 11 wherein locations in the cache lines are addressed or provided an address offset by a third section of the storage addresses.

13. The storage device according to claim 11 wherein the primary index table includes primary index entries that address or provide an address offset to group entries in the secondary index table and the secondary index table stores pointers that address or provide an address offset to state record entries in a state records table.

14. The storage device according to claim 13 wherein the search structure is configured to identify one of the cache lines as invalid when one of the primary index entries associated with the storage address is identified as invalid.

15. The storage device according to claim 13 wherein the search structure is configured to identify one of the cache lines as invalid when one of the pointers in the secondary index table associated with the storage address is identified as invalid.

16. The storage device according to claim 10 wherein the search structure is configured to automatically invalidate cache lines according to time stamp values associated with the cache lines and according to memory access counter values associated with the cache lines.

17. The storage device according to claim 10 wherein the storage device is coupled between initiator devices that generate the storage addresses and the storage array that contains data associated with the storage addresses, and wherein the proxy engine forwards the storage addresses to the mapping engine for determining a status for the cache lines associated with the storage addresses.

18. A method, comprising:

receiving a storage address;

addressing a primary index table with a primary index address of the storage address;

using a primary index entry addressed in the primary index table to address an index group in a secondary index table;

identifying a pointer in the addressed index group with a secondary index address of the storage address; and

using the identified pointer to address a state record entry in a state record table.

19. The method according to claim 18 further comprising:

receiving a search request for the storage address;

indicating a search miss when the primary index entry, the pointer, or the state record entry associated with the storage address are invalid; and

indicating a search hit when the primary index entry, the pointer, and the state record entry associated with the storage address are all valid.

20. The method according to claim 18 further comprising:

receiving an add request for the storage address;

adding a new primary index entry to the primary index table, adding a new index group to the secondary index table, and adding a new state record to the state record table when there is no valid primary index entry associated with the storage address;

adding a new pointer to the secondary index table and adding a new state record to the state record table when there is no valid pointer in the secondary index table associated with the storage address;

adding a new state record to the state record table when there is no valid state record in the state record table associated with the storage address; and

indicating an add failure when the primary index entry in the primary index table associated with the storage address is valid, the pointer in the secondary index table associated with the storage address is valid, and the state record entry in the state record table associated with the storage address is valid.

21. The method according to claim 18 further comprising:

receiving a delete request for the storage address;

indicating a delete failure when the primary index entry, the pointer, or the state record entry associated with the storage address is invalid; and

invalidating the state record entry associated with the storage address when the primary index entry, the pointer, and the state record entry associated with the storage address are all valid.

22. The method according to claim 18 further comprising invalidating the state record entry according to both a time stamp value in the state record entry and cache line access statistics in the state record entry.