Header processing engine

• US 8,743,877 B2
• Filed: 01/12/2010
• Issued: 06/03/2014
• Est. Priority Date: 12/21/2009
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: SolarFlare Communications Incorporated (Advanced Micro Devices, Inc.)
• Inventors: Pope, Steven L., Riddoch, David, Kitariev, Dimitri, Roberts, Derek
• Primary Examiner(s): WILSON, ROBERT W
• Application Number:
  US12/686,280
• Publication Number:
  US 20110149966A1
• Time in Patent Office: 1,603 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Roughly described, a header processing engine for a network interface device has a header recognizer to parse the headers of a data packet stored at a buffer to identify the type and position of each header in the packet; a constructor unit; and a processor including an execution pipeline. The header recognizer is configured to, for each header: select in dependence on the header type commands stored at a command memory; and form one or more messages for the constructor unit identifying the selected commands and the position of the header in the data packet. The commands selected for the packet headers are collectively such as to, if executed by the constructor unit, cause the constructor unit to generate a data structure which operates to cause the processor to process of the packet headers without accessing the data packet at the buffer.

Claims

1. A header processing engine comprising:

a command memory;

a header recognizer configured to parse headers of a data packet stored at a buffer so as to identify the type and position of each header in the data packet;

a constructor unit having read access to the headers of the data packet; and

a processor including an execution pipeline;

the header recognizer being further configured to, for each header;

(a) select in dependence on the type of the header one or more commands stored at the command memory; and

(b) form one or more messages for the constructor unit identifying the selected commands and the position of the header in the data packet;

wherein the constructor unit is configured to receive the messages and execute the commands identified therein, the commands selected for the headers of the data packet being collectively such as to, when executed by the constructor unit, cause the constructor unit to generate a data structure which is such as to be operable to cause the processor to effect processing of the headers of the data packet without accessing the data packet at the buffer.

2. A header processing engine as claimed in claim 1, the header processing engine further comprising a shared memory accessible to the processor at which the constructor unit is configured to write the data structure.

3. A header processing engine as claimed in claim 1, wherein the data structure identifies a set of instructions for execution by the processor and the processor is configured to access the data structure and execute the instructions identified therein so as to effect processing of the headers of the data packet.

4. A header processing engine as claimed in claim 1, wherein the data structure includes one or more parts of the headers.

5. A header processing engine as claimed in claim 1, wherein the data structure identifies a set of instructions for execution by the processor and the processor is configured to access the data structure and execute the instructions identified therein so as to effect processing of the headers of the data packet,

and wherein the data structure includes only those parts of the headers required for the execution of one or more of the said instructions.

6. A header processing engine as claimed in claim 3, wherein the data structure includes a packet class identifier which uniquely represents the sequence of headers of the data packet, the packet class identifier identifying the said set of instructions for execution by the processor.

7. A header processing engine as claimed in claim 6, wherein the packet class identifier represents a memory address at an instruction memory of the processor and the processor is configured to, on reading the packet class identifier, access the memory address and initiate execution of the instructions stored at the memory address.

8. A header processing engine as claimed in claim 6, wherein the constructor unit is configured to generate the packet class identifier by forming a representation of the particular sequence of headers of the data packet and passing the representation to a compression engine whose only available outputs correspond to valid sequences of headers, the output of the compression engine being the packet class identifier.

9. A header processing engine as claimed in claim 3, wherein the header processing engine further comprises a shared memory accessible to the processor at which the constructor unit is configured to write the data structure,

wherein the shared memory is configured to hold a plurality of data structures, each data structure corresponding to a different data packet.

10. A header processing engine as claimed in claim 9, wherein the shared memory is configured to allow the constructor unit and the processor to have concurrent access to different data structures, the processor having exclusive access to data structures completed by the constructor unit.

11. A header processing engine as claimed in claim 9, wherein the processor is configured to, on initiating execution of one or more predetermined instructions that cause the processor to call a functional unit which does not share the execution pipeline of the processor, switch execution threads by:

storing the state of its execution pipeline at the data structure corresponding to the data packet in respect of which the call is made;

loading the state of a different data structure stored at the shared memory into its execution pipeline; and

executing the set of instructions identified at the different data structure.

12. A header processing engine as claimed in claim 11, wherein the processor is configured such that the data returned in response to a call to a functional unit is written to a selected register of the processor so as to be available to the execution pipeline when the processor next loads the state stored at the data structure corresponding to the data packet in respect of which the call was made.

13. A header processing engine as claimed in claim 12, wherein the processor is configured to, on making a call to a functional unit, set a flag for the selected register into which data returned in response to that call is to be written, the flag preventing the processor selecting that register for another call until the flag is cleared.

14. A header processing engine as claimed in claim 13, wherein the processor is configured to, on reading the data from the selected register, clear said flag so as to allow the processor to select that register for a subsequent call.

15. A header processing engine as claimed in claim 11, wherein at least one of the predetermined instructions cause the processor to, when executed, call a lookup engine or a hash engine.

16. A header processing engine as claimed in claim 9, wherein the processor is configured to, responsive to the said instructions, write to each data structure the respective output of the processor.

17. A header processing engine as claimed in claim 3, wherein the header processing engine is located at a network interface device of a data processing system supporting one or more operating systems, and the processor is configured to, responsive to said instructions, provide to the network interface device data identifying a receive queue of the data processing system to which at least part of the received data packet is to be written.

18. A header processing engine as claimed in claim 17, wherein the header processing engine is further configured to, on the processor completing processing of the headers of the data packet, make at least part of the output of the processor available to a packet processing engine of the network interface device, the packet processing engine being configured to process the data packets held at the buffer at least partly in dependence on the output of the processor.

19. A header processing engine as claimed in claim 3, wherein the data packet is a partially-formed data packet and the processor is configured to, responsive to said instructions, process the headers of the partially-formed data packet in such a way as to complete the data packet.

20. A header processing engine as claimed in claim 19, wherein the processor is configured to complete the data packet by performing one or more of the following operations:

if the data packet belongs to a data flow to be transmitted in accordance with a predetermined level of a quality of service protocol, write appropriate quality of service parameters to the data packet so as to cause the data packet to be handled in accordance with that predetermined level;

if the data packet is to be transmitted over a virtual LAN, write appropriate virtual LAN parameters to the data packet so as to cause the data packet to be routed over that virtual LAN; and

if the data packet originated at a virtual interface of a network interface device, perform packet filtering so as to ensure that the data packet is transmitted onto the network only if the destination address of the data packet is a network endpoint to which that virtual interface has been granted access.

21. A header processing engine as claimed in claim 1, wherein each header of the data packet comprises a set of data bits formatted in accordance with a network data protocol and each set of data bits is located within nested headers of the data packet, a footer of the data packet, or at any other point in the data packet.

22. A header processing engine for performing header processing of a sequence of data packets each having multiple headers, the header processing engine comprising:

a header recognizer configured to parse the multiple headers of each data packet in a sequence of data packets and, for each data packet, form one or more messages indicating the type and position of each header in the data packet, the header recognizer being configured to parse the data packets in sequence; and

a processor configured to perform header processing on each data packet of the sequence in dependence on the one or more messages formed for that data packet and provide processed data packets in sequence at an output of the processor;

wherein the header recognizer and the processor are configured to operate in parallel so as to allow the processor to perform header processing on the data packets out of sequence.

23. A header processing engine as claimed in claim 22, wherein the header recognizer and processor operate such that when the processor is processing one data packet in a sequence of data packets, the header recognizer is parsing another data packet in the sequence.

24. A header processing engine as claimed in claim 22, wherein the header recognizer is configured to parse the headers of the data packet sequentially and to, on identifying the type and position of each header in the data packet, form a message for the processor comprising the type of that header and the position of that header in the data packet.

25. A header processing engine as claimed in claim 22, wherein the header recognizer is configured to identify the position of each header in the data packet by detecting one or more predetermined sequences of bits in the headers of the data packet.

26. A header processing engine as claimed in claim 25, wherein the predetermined sequences of bits indicate the start or end of a header.

27. A header processing engine as claimed in claim 22, wherein the header recognizer is operable to identify the type of a header in the data packet by detecting one or more predetermined values representing header type.

28. A header processing engine as claimed in claim 22, wherein the header recognizer is operable to identify the type of a header in the data packet using the position of the header in the data packet.

29. A header processing engine as claimed in claim 22, wherein the processor is configured to, in dependence on the types of header identified in the one or more messages formed for a particular data packet, select a set of instructions stored at an instruction memory of the processor and process that data packet using the selected set of instructions.

30. A header processing engine as claimed in claim 22, wherein the header recognizer is configured to, in dependence on the types of header identified in the one or more messages formed for a particular data packet, select a set of instructions stored at an instruction memory of the processor and cause the processor to process that data packet using the selected set of instructions.

31. A header processing engine for performing header processing of a sequence of data packets stored at a buffer, each of the data packets in the sequence having multiple headers and the header processing engine comprising:

a processor having an execution pipeline; and

a pre-processor unit configured to parse headers of a data packet stored at the buffer and, in dependence on the types of headers in the data packet, form a data structure identifying a set of instructions, the data structure being such as to be operable to cause the processor to effect processing of the headers of the data packet without accessing the data packet stored at the buffer;

wherein the processor is configured to access the data structure and execute the said set of instructions so as to process the headers of the data packet.

32. A header processing engine as claimed in claim 31, the header processing engine further comprising a shared memory accessible to the processor at which the pre-processor unit is configured to write the data structure.

33. A header processing engine as claimed in claim 31, wherein the data structure includes one or more parts of the headers of the data packet.

34. A header processing engine as claimed in claim 33, wherein the data structure includes only those parts of the headers required by one or more of the said instructions.

35. A header processing engine as claimed in claim 31, wherein the pre-processor unit is configured to select the set of instructions in dependence on the types of headers in the data packet.

36. A header processing engine as claimed in claim 31, wherein the processor supports an instruction memory and the set of instructions are stored in the instruction memory at a location identified in the data structure.

37. A header processing engine as claimed in claim 31, wherein the pre-processor unit is configured to generate a packet class identifier which uniquely represents the types of headers of the data packet, the packet class identifier being included in the data structure and identifying the said set of instructions for execution by the processor.

38. A header processing engine as claimed in claim 37, wherein the packet class identifier represents a memory address at an instruction memory of the processor and the processor is configured to, on reading the packet class identifier, access the memory address and initiate execution of the instructions stored at the memory address.

39. A header processing engine as claimed in claim 37, wherein the pre-processor unit is configured to generate the packet class identifier by forming a representation of the particular sequence of headers of the data packet and passing the representation to a compression engine whose only available outputs correspond to valid sequences of headers, the output of the compression engine being the packet class identifier.

40. A header processing engine as claimed in claim 33, wherein the header processing engine further comprises a shared memory accessible to the processor at which the pre-processor unit is configured to write the data structure,

wherein the shared memory is configured to hold a plurality of data structures, each data structure corresponding to the headers of a different data packet.

41. A header processing engine as claimed in claim 40, wherein the shared memory is configured to allow the pre-processor unit and the processor to have concurrent access to different data structures, the processor having exclusive access to data structures completed by the pre-processor unit.

42. A header processing engine as claimed in claim 40, wherein the processor is configured to, on initiating one or more predetermined instructions that cause the processor to call a functional unit which does not share the execution pipeline of the processor, store the state of its execution pipeline at the data structure corresponding to the data packet in respect of which the call is made and load the state of a different data structure stored at the shared memory into its execution pipeline.

43. A header processing engine as claimed in claim 42, wherein the processor is configured such as to cause the data returned in response to a call to a functional unit to be written to a selected register of the processor so as to be available to the execution pipeline when the processor next loads the state stored at the data structure corresponding to the data packet in respect of which the call was made.

44. A header processing engine as claimed in claim 43, wherein the processor is configured to, on making a call to a functional unit, set a flag for the selected register into which data returned in response to that call is to be written, the flag preventing the processor selecting that register for another call.

45. A header processing engine as claimed in claim 44, wherein the processor is configured to, on reading the data from the selected register, clear said flag so as to allow the processor to select that register for a subsequent call.

46. A header processing engine as claimed in claim 42, wherein at least one of the predetermined instructions cause the processor to, when executed, call a lookup engine, a hash engine, a checksum or CRC calculation engine, an encryption engine, or a chain of any of the aforementioned engines arranged in any order.

47. A header processing engine as claimed in claim 40, wherein the processor is configured to, responsive to the said instructions, write to each data structure the respective output of processing performed by the processor.

48. A processor configured for processing network data packets, the processor comprising:

an instruction memory storing a plurality of instruction sequences;

a processor memory for storing a plurality of instruction references and sets of state of the processor, each instruction reference identifying an instruction sequence stored at the instruction memory and each set of state corresponding to an instruction reference; and

an execution pipeline operable to execute an instruction sequence identified by an instruction reference using the corresponding set of state stored at the processor memory, an instruction sequence and its corresponding state defining an execution thread for processing a particular network data packet;

the processor being configured to, during processing of a first network data packet by executing an instruction sequence identified by a first instruction reference, switch execution threads so as to process a second network data packet by;

writing the state of the execution pipeline to a first set of state at the processor memory;

loading a second set of state into the execution pipeline from the processor memory; and

executing a second instruction sequence identified by an instruction reference corresponding to the second set of state;

wherein the processor is configured to switch execution threads on initiating execution of one or more predetermined instructions in an instruction sequence.

49. A processor as claimed in claim 48, wherein the first set of state includes an indication of the position in the first instruction sequence up to which execution has been performed.

50. A processor as claimed in claim 48, wherein the predetermined instruction causes the processor to, when executed, call a functional unit which does not share the execution pipeline of the processor.

51. A processor as claimed in claim 50, wherein the functional unit is supported at the processor.

52. A processor as claimed in claim 50, the processor further comprising a plurality of registers and being configured such as to cause the data returned in response to a call to the functional unit to be written to a selected one of the registers.

53. A processor as claimed in claim 48, the processor being configured to switch between the plurality of execution threads defined at the processor memory on a round-robin basis and, on subsequently switching back to the execution thread defined by the first set of state and the first instruction sequence:

write the state of the execution pipeline to the processor memory at the set of state corresponding to the instruction sequence being executed at the execution pipeline;

load the first set of state into the execution pipeline; and

continue execution of the first instruction sequence.

54. A method for switching between execution threads at a processor configured for processing network data packets, the method comprising:

processing a first network data packet by executing by an execution pipeline of the processor a first instruction sequence identified by a first instruction reference stored in a memory of the processor;

pausing the execution pipeline;

writing a state of the execution pipeline to a first set of state in the processor memory;

loading a second set of state into the execution pipeline from the processor memory; and

executing in the execution pipeline a second instruction sequence identified by a second instruction reference stored in the processor memory, so as to effect processing of a second network data packet,

wherein the first instruction sequence and second instruction sequence correspond to execution threads for processing respectively the first and second network packets.