Methods and apparatus for accessing a doubly linked list in a data storage system

• US 6,941,308 B1
• Filed: 10/05/2001
• Issued: 09/06/2005
• Est. Priority Date: 10/05/2001
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Chilton, Kendell A.
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/972,321
• Time in Patent Office: 1,432 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 711/100, 711113-114, 711/133, 711160-163, 711171-173, 710/1, 710/52
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A data storage system has storage devices, a processor which is configured to move data to and from the storage devices, and a bus coupled to the processor. The data storage system further includes a memory board having (i) an interface which couples to the bus, (ii) memory which is configured to store a doubly linked list data structure, and (iii) a memory board control circuit coupled to the interface and the memory. The memory board control circuit is capable of accessing the data structure. In particular, the memory board control circuit is configured to receive a modify command from the processor through the interface and the bus, atomically modify the data structure in accordance with the modify command, and provide a result to the processor through the interface and the bus in response to modifying the data structure.

Claims

1. A memory board for a data storage system, comprising:

an interface which is configured to couple to a bus of the data storage system;

memory which is configured to store a doubly linked list data structure; and

a memory board control circuit, coupled to the interface and the memory, the memory board control circuit being configured to;

receive a modify command from a processor of a data storage system through the interface, the processor being configured to move data within the data storage system,

atomically modify the doubly linked list data structure in accordance with the modify command, and

provide a result to the processor of the data storage system through the interface in response to modifying the doubly linked list data structure.

2. The memory board of claim 1 wherein the doubly linked list data structure is a doubly linked list shared data structure.

3. The memory board of claim 2 wherein the doubly linked list shared data structure includes multiple entries, wherein the modify command is a remove instruction, and wherein the memory board control circuit is configured to atomically modify the doubly linked list shared data structure by removing an entry from the doubly linked list shared data structure in response to the remove instruction.

4. The memory board of claim 2 wherein the doubly linked list shared data structure includes multiple entries, wherein the modify command is an add instruction, and wherein the memory board control circuit is configured to atomically modify the doubly linked list shared data structure by adding an entry to the doubly linked list shared data structure in response to the add instruction.

5. The memory board of claim 2 wherein the doubly linked list shared data structure includes multiple entries, wherein the modify command is a move instruction, and wherein the memory board control circuit is configured to atomically modify the doubly linked list shared data structure by moving an entry from a first position in the doubly linked list shared data structure to a second position in the doubly linked list shared data structure in response to the move instruction.

6. The memory board of claim 2 wherein the memory board control circuit is configured to atomically modify the doubly linked list shared data structure by performing a series of individual transactions on the doubly linked list shared data structure, and wherein the memory board control circuit is configured to provide, as the result, a series of transaction outputs respectively corresponding to the series of individual transactions.

23. The memory board of claim 1 wherein the memory board control circuit, when atomically modifying the doubly linked list data structure in accordance with the modify command, is configured to:

change the doubly linked list data structure in a non-interruptible, single operation.

24. The memory board of claim 23 wherein the memory board control circuit, when changing the doubly linked list data structure in the non-interruptible, single operation, is configured to:

prevent execution of any overlapping context to alleviate having to coordinate modification of the doubly linked list data structure using shared data structure locking overhead operations.

31. The memory board of claim 24 wherein the modify command is a single communication between the processor and the memory board over the bus;

and wherein the memory board control circuit, when preventing execution of any overlapping context, is configured to;

respond to the single communication between the processor and the memory board over the bus to reduce bus contention, lower latency and alleviate a need for shared data structure locking overhead.

7. A data storage system, comprising:

a set of storage devices;

a processor which is configured to move data to and from the set of storage devices;

a bus coupled to the processor; and

a memory board that includes (i) an interface which couples to the bus, (ii) memory which is configured to store a doubly linked list data structure, and (iii) a memory board control circuit, coupled to the interface and the memory, the memory board control circuit being configured to;

receive a modify command from the processor of the data storage system through the interface and the bus,

atomically modify the doubly linked list data structure in accordance with the modify command, and

provide a result to the processor of the data storage system through the interface and the bus in response to modifying the doubly linked list data structure.

8. The data storage system of claim 7 wherein the doubly linked list data structure is a doubly linked list shared data structure.

9. The data storage system of claim 8 wherein the doubly linked list shared data structure includes multiple entries, wherein the modify command is a remove instruction, and wherein the memory board control circuit is configured to atomically modify the doubly linked list shared data structure by removing an entry from the doubly linked list shared data structure in response to the remove instruction.

10. The data storage system of claim 8 wherein the doubly linked list shared data structure includes multiple entries, wherein the modify command is an add instruction, and wherein the memory board control circuit is configured to atomically modify the doubly linked list shared data structure by adding an entry to the doubly linked list shared data structure in response to the add instruction.

11. The data storage system of claim 8 wherein the doubly linked list shared data structure includes multiple entries, wherein the modify command is a move instruction, and wherein the memory board control circuit is configured to atomically modify the doubly linked list shared data structure by moving an entry from a first position in the doubly linked list shared data structure to a second position in the doubly linked list shared data structure in response to the move instruction.

12. The data storage system of claim 8 wherein the memory board control circuit is configured to atomically modify the doubly linked list shared data structure by performing a series of individual transactions on the doubly linked list shared data structure, and wherein the memory board control circuit is further configured to provide, as the result, a series of transaction outputs respectively corresponding to the series of individual transactions.

13. The data storage system of claim 12 wherein the series of transaction outputs provided by the memory board control circuit includes a first transaction output and a second transaction output;

wherein the processor is configured to (i) generate a pseudo transaction output based on the first transaction output and (ii) compare the pseudo transaction output to the second transaction output in order to error check operation of the memory board.

25. The data storage system of claim 7 wherein the memory board control circuit, when atomically modifying the doubly linked list data structure in accordance with the modify command, is configured to:

change the doubly linked list data structure in a non-interruptible, single operation.

26. The data storage system of claim 25 wherein the memory board control circuit, when changing the doubly linked list data structure in the non-interruptible, single operation, is configured to:

prevent execution of any overlapping context to alleviate having to coordinate modification of the doubly linked list data structure using shared data structure locking overhead operations.

32. The data storage system of claim 26 wherein the modify command is a single communication between the processor and the memory board over the bus;

and wherein the memory board control circuit, when preventing execution of any overlapping context, is configured to;

respond to the single communication between the processor and the memory board over the bus to reduce bus contention, lower latency and alleviate a need for shared data structure locking overhead.

14. In a memory board of a data storage system, a method for accessing a doubly linked list data structure, the method comprising the steps of:

receiving a modify command from a processor of a data storage system through a bus of the data storage system, the processor being configured to move data within the data storage system,

atomically modifying the doubly linked list data structure in accordance with the modify command, and

providing a result to the processor of the data storage system through the bus in response to modifying the doubly linked list data structure.

15. The method of claim 14 wherein the step of atomically modifying the doubly linked list data structure includes the step of:

updating, as the doubly linked list data structure, a doubly linked list shared data structure in an atomic manner.

16. The method of claim 15 wherein the doubly linked list shared data structure includes multiple entries, wherein the modify command is a remove instruction, and wherein the step of updating the doubly linked list shared data structure includes the step of:

removing an entry from the doubly linked list shared data structure in response to the remove instruction.

17. The method of claim 15 wherein the doubly linked list shared data structure includes multiple entries, wherein the modify command is an add instruction, and wherein the step of updating the doubly linked list shared data structure includes the step of:

adding an entry to the doubly linked list shared data structure in response to the add instruction.

18. The method of claim 15 wherein the doubly linked list shared data structure includes multiple entries, wherein the modify command is a move instruction, and wherein the step of updating the doubly linked list shared data structure includes the step of:

moving an entry from a first position in the doubly linked list shared data structure to a second position in the doubly linked list shared data structure in response to the move instruction.

19. The method of claim 15 wherein the step of updating the doubly linked list shared data structure includes the step of:

performing a series of individual transactions on the doubly linked list shared data structure, and

wherein the step of providing the result includes the step of;

outputting, as the result, a series of transaction outputs respectively corresponding to the series of individual transactions.

20. The method of claim 19 wherein the series of transaction outputs provided by the memory board control circuit includes a first transaction output and a second transaction output;

and wherein the method further comprises the step of;

performing an error handling routine in response to an error message from the processor resulting from (i) generation of a pseudo transaction output based on the first transaction output and (ii) a comparison of the pseudo transaction output to the second transaction output in order to error check operation of the memory board.

27. The method of claim 14 wherein the step of atomically modifying the doubly linked list data structure in accordance with the modify command includes the step of:

changing the doubly linked list data structure in a non-interruptible, single operation.

28. The method of claim 27 wherein the step of changing the doubly linked list data structure in the non-interruptible, single operation includes the step of:

preventing execution of any overlapping context to alleviate having to coordinate modification of the doubly linked list data structure using shared data structure locking overhead operations.

33. The method of claim 28 wherein the modify command is a single communication between the processor and the memory board over the bus;

and wherein preventing execution includes;

responding to the single communication between the processor and the memory board over the bus to reduce bus contention, lower latency and alleviate a need for shared data structure locking overhead.

21. A memory board control circuit for accessing a doubly linked list data structure of a data storage system, the memory board control circuit being mountable to a memory board, the memory board control circuit comprising:

an input port that couples to a bus of the data storage system;

an output port that couples to the bus of the data storage system; and

control logic, connected to the input port and to the output port, that is configured to;

receive a modify command from a processor of a data storage system through the input port, the processor being configured to move data within the data storage system,

atomically modify the doubly linked list data structure in accordance with the modify command, and

provide a result to the processor of the data storage system through the output port in response to modifying the doubly linked list data structure.

22. The memory board control circuit of claim 21 wherein the doubly linked list is a doubly linked list shared data structure.

29. The memory board control circuit of claim 21 wherein the control logic, when atomically modifying the doubly linked list data structure in accordance with the modify command, is configured to:

change the doubly linked list data structure in a non-interruptible, single operation.

30. The memory board control circuit of claim 29 wherein the control logic, when changing the doubly linked list data structure in the non-interruptible, single operation, is configured to:

prevent execution of any overlapping context to alleviate having to coordinate modification of the doubly linked list data structure using shared data structure locking overhead operations.

34. The memory board control circuit of claim 30 wherein the modify command is a single communication between the processor and the memory board control circuit over the bus;

and wherein the control logic, when preventing execution of any overlapping context, is configured to;

respond to the single communication between the processor and the memory board control circuit over the bus to reduce bus contention, lower latency and alleviate a need for shared data structure locking overhead.