System and method for efficient implementation of a shared receive queue

• US 7,496,698 B2
• Filed: 03/22/2005
• Issued: 02/24/2009
• Est. Priority Date: 03/22/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Machulsky, Zorik, Biran, Giora, Recio, Renato John, Makhervaks, Vadim, Hufferd, John Lewis
• Primary Examiner(s): Patel; Niketa I
• Assistant Examiner(s): Snyder; Steven G
• Application Number:
  US11/086,713
• Publication Number:
  US 20060218316A1
• Time in Patent Office: 1,435 Days
• Field of Search: 710/52, 710/54, 710/310, 713/1, 713/100, 709/228
• US Class Current: 710/52
• CPC Class Codes: G06F 13/1657 Access to multiple memories

Abstract

A method, computer program product, and a data processing system for posting and retrieving WQEs to a shared receive queue in a manner that alleviates head-of-line blocking issues is provided. The present invention provides a shared receive queue and a posting routine for allowing non-sequential work request postings in the shared receive queue. Additionally, a fetch routine is provided for non-sequential fetching of work queue elements from the shared receive queue.

Claims

1. A method that facilitates non-sequential posting and retrieving of work queue elements to and from a shared receive queue, the method comprising the computer implemented steps of:

including, in each one of the work queue elements, a first field for storing a first state indicator that indicates whether the work queue element is in a completed state;

including, in each one of the work queue elements, a second field for storing a second state indicator that indicates whether the work queue element is in an in-processing state;

including, in each one of the work queue elements, a third field for storing a third state indicator that indicates whether the work queue element is in a posted state;

wherein multiple work queue elements are in only one of the completed state, in-processing state, and posted state at a time;

generating, by a consumer, a first work queue element for posting to the shared receive queue, the queue including a plurality of entries;

sequentially traversing and evaluating the plurality of entries until a first entry is located that includes a second work queue element having a first state indicator that indicates that the second work queue element has completed processing; and

responsive to locating the first entry, writing the first work queue element to the first entry.

2. The method of claim 1, further comprising:

for each one of the work queue elements;

transitioning the work queue element to the posted state when the work queue element is written to the shared receive queue;

transitioning the work queue element from the posted state to the in-processing state when hardware fetches the work queue element; and

transitioning the work queue element from the in-processing state to the completed state when the work queue element has completed.

3. The method of claim 1, further comprising:

responsive to writing the first work queue element, writing a value to the first state indicator included in the first work queue element that indicates that the first work queue element has not completed processing.

4. The method of claim 1, further comprising:

responsive to writing the first work queue element to the first entry, updating the third state indicator for the first work queue element to indicate that the first work queue element has posted.

5. The method of claim 1, wherein the step of sequentially traversing and evaluating is repeated until a tail entry of the plurality of entries is reached, the method further comprising referencing a head entry of the shared receive queue and repeating the traversing and evaluating steps until locating the first entry.

6. The method of claim 1, wherein the first entry comprises a head entry of the shared receive queue.

7. The method of claim 1, further comprising:

sequentially traversing and evaluating, by a hardware entity, the plurality of entries until a second entry is located that maintains a third work queue element that has a third state indicator that indicates that the third work queue element has been posted; and

responsive to locating the second entry, fetching the second work queue element for processing by the hardware entity.

8. The method of claim 7, further comprising:

responsive to fetching the third work queue element;

changing, by the hardware entity, a second state indicator included in the third work queue element to a value that indicates that the third work queue element is in processing; and

changing, by the hardware entity, a third state indicator included in the third work queue element to a value that indicates that the third work queue element is not posted.

9. The method of claim 8, further comprising:

responsive to fetching the third work queue element, processing the third work queue element; and

responsive to completion of processing of the third work queue element;

changing a first state indicator included in the third work queue element to a value that indicates that the third work queue element has completed processing; and

changing the second state indicator included in the third work queue element to indicate that the third work queue element is not in processing.

10. A computer program product, which is stored in a computer recordable-type medium, for facilitating non-sequential posting and retrieving of work queue elements to and from a shared receive queue, the computer program product comprising:

instructions for including, in each one of the work queue elements, a first field for storing a first state indicator that indicates whether the work queue element is in a completed state;

instructions for including, in each one of the work queue elements, a second field for storing a second state indicator that indicates whether the work queue element is in an in-processing state;

instructions for including, in each one of the work queue elements, a third field for storing a third state indicator that indicates whether the work queue element is in a posted state;

wherein multiple work queue elements are in only one of the completed state, in-processing state, and posted state at a time;

instructions for generating, by a consumer, a first work queue element for posting to the shared receive queue, the queue including a plurality of entries;

instructions that sequentially traverse and evaluate entries of the plurality of entries until a first entry is located that includes a second work queue element having a first state indicator that indicates that the second work queue element has completed processing; and

instructions that, responsive to locating the first entry, write the first work queue element to the first entry.

11. The computer program product of claim 10,

for each one of the work queue elements:

instructions for transitioning the work queue element to the posted state when the work queue element is written to the shared receive queue;

instructions for transitioning the work queue element from the posted state to the in-processing state when hardware fetches the work queue element; and

instructions for transitioning the work queue element from the in-processing state to the completed state when the work queue element has completed.

12. The computer program product of claim 10, further comprising:

instructions that, responsive to writing the first work queue, write a value to the first state indicator included in the first work queue element that indicates that the first work queue element has not completed processing.

13. The computer program product of claim 12,

responsive to writing the first work queue element to the first entry, instructions for updating the third state indicator for the first work queue element to indicate that the first work queue element has posted.

14. The computer program product of claim 10, wherein the instructions for sequentially traversing and evaluating are repeated until a tail entry of the plurality of entries is reached, and further comprising responsive to reaching the tail entry, instructions for referencing a head entry of the shared receive queue and repeatedly traversing and evaluating the plurality of entries until the first entry is located.

15. The computer program product of claim 10, wherein the first entry comprises a head entry of the shared receive queue.

16. The computer program product of claim 10, further comprising:

instructions for sequentially traversing and evaluating by a hardware entity the plurality of entries until a second entry is located that maintains a third work queue element that has a third state indicator that indicates that the third work queue element has been posted; and

instructions for, responsive to locating the second entry, fetching the third work queue element of the second entry for processing by the hardware entity.

17. The computer program product of claim 16, further comprising:

instructions for, responsive to fetching the third work queue element, changing a second state indicator included in the third work queue element to a value that indicates that the third work queue element is in processing; and

instructions for changing by the hardware entity, a third state indicator included in the third work queue element to a value that indicates that the third work queue element is not posted.

18. The computer program product of claim 17, further comprising:

instructions for, responsive to fetching the third work queue element, processing the third work queue element; and

responsive to completing processing of the third work queue element;

instructions for changing a first state indicator included in the third work queue element to a value that indicates that the third work queue element has completed processing; and

instructions for changing the second state indicator included in the third work queue element to indicate that the third work queue element is not in processing.

19. A data processing system for facilitating non-sequential posting and retrieving of work queue elements to and from a shared receive queue, comprising:

a channel adapter comprising the shared receive queue having a plurality of entries;

each one of the work queue elements including a first field for storing a first state indicator that indicates whether the work queue element is in a completed state;

each one of the work queue elements including a second field for storing a second state indicator that indicates whether the work queue element is in an in-processing state;

each one of the work queue elements including a third field for storing a third state indicator that indicates whether the work queue element is in a posted state;

wherein multiple work queue elements are in only one of the completed state, in-processing state, and posted state at a time;

a memory that contains a software entity and a set of instructions for writing work queue elements to the shared receive queue; and

a processing unit that, responsive to execution of the set of instructions, generates, by a consumer, a first work queue element for posting to the shared receive queue that includes a plurality of entries;

sequentially traverses and evaluates the plurality of entries until a first entry is located that includes a second work queue element having a first state indicator that indicates that the second work queue element has completed processing; and

responsive to locating the first entry, writes the first work queue to the first entry.

20. The data processing system of claim 19, wherein, for each one of the work queue elements, the processing unit:

transitions the work queue element to the posted state when the work queue element is written to the shared receive queue;

transitions the work queue element from the posted state to the in-processing state when hardware fetches the work queue element; and

transitions the work queue element from the in-processing state to the completed state when the work queue element has completed.

21. The data processing system of claim 19, wherein the processing unit repeats traversing and evaluating the plurality of entries until a tail entry of the plurality of entries is reached, wherein the processing unit references a head entry of the shared receive queue and repeats the traversing and evaluating steps until locating the first entry.

22. The data processing system of claim 19, wherein the hardware entity sequentially traverses and evaluates the plurality of entries until a second entry is located that maintains a third work queue element that has a third state indicator that indicates that the third work queue element has been posted, and wherein, responsive to locating the second entry, the hardware entity fetches the third work queue element of the second entry for processing.

23. The data processing system of claim 22, wherein responsive to fetching the third work queue element, the hardware entity:

changes a second state indicator included in the third work queue element to a value that indicates that the third work queue element is in processing; and

changes a third state indicator included in the third work queue element to a value that indicates that the third work queue element is not posted.

24. The data processing system of claim 22, wherein the hardware entity, responsive to fetching the third work queue element:

processes the third work queue element, and wherein responsive to completing processing of the third work queue element by the hardware entity;

a first state indicator included in the third work queue element is changed to a value that indicates that the third work queue element has completed processing; and

the second state indicator that is included in the third work queue element is changed to indicate that the third work queue element is not in processing.