Deterministic finite automata (DFA) processing

• US 8,392,590 B2
• Filed: 09/07/2005
• Issued: 03/05/2013
• Est. Priority Date: 09/10/2004
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Bouchard, Gregg A., Carlson, David A., Kessler, Richard E., Hussain, Muhammad R.
• Primary Examiner(s): THIAW, CATHERINE B
• Application Number:
  US11/221,408
• Publication Number:
  US 20060069872A1
• Time in Patent Office: 2,736 Days
• Field of Search: 704/2, 704/221, 704/243, 707/2, 711/100, 709/230
• US Class Current: 709/230
• CPC Class Codes: G06F 15/7846 On-chip cache and off-chip main memory
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 63/02 for separating internal from external traffic, e.g. firewalls
• CPC Class Codes: H04L 63/04 for providing a confidential data exchange among entities communicating through data packet networks
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
• CPC Class Codes: H04L 63/164 at the network layer
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A processor for traversing deterministic finite automata (DFA) graphs with incoming packet data in real-time. The processor includes at least one processor core and a DFA module operating asynchronous to the at least one processor core for traversing at least one DFA graph stored in a non-cache memory with packet data stored in a cache-coherent memory.

Claims

1. A network processor, comprising:

at least one processor core;

a deterministic finite automata (DFA) module operating asynchronously to the at least one processor core, the DFA module traversing a plurality of nodes of at least one DFA graph stored in a non-cache memory that is;

i) external to the network processor and ii) sized to accommodate the at least one DFA graph having a number of nodes for searching for multiple patterns in one traversal of the at least one DFA graph, the DFA module including a plurality of DFA thread engines associated in a shared configuration with the at least one processor core;

and responsive to instructions for traversing the plurality of nodes of the at least one DFA from the at least one processor core, with packet data stored in a cache-coherent memory, each of the plurality of DFA thread engines is configured to;

traverse at least one DFA graph independent of others of the plurality of DFA thread engines traversing DFA graphs including the at least one DFA graph,

fetch the packet data stored in the cache-coherent memory,

in response to each byte of packet data fetched from the cache-coherent memory, issue an instruction to access and load a next node of the at least one DFA graph from the non-cache memory to traverse the next node of the at least one DFA graph, and

write intermediate and final results of traversing the at least one DFA graph to the cache-coherent memory.

2. The network processor of claim 1, wherein the DFA module includes:

a non-cache memory controller adapted to access the memory storing the at least one DFA graph;

at least one of the plurality of DFA thread engines in communication with the non-cache memory controller; and

instruction input logic adapted to schedule instructions from the at least one processor core to the at least one of the plurality of DFA thread engine engines.

3. The network processor of claim 2, further comprising an instruction queue into which the at least one processor core submits DFA instructions directed to the DFA module.

4. The network processor of claim 3, wherein the DFA module maintains a pointer to the instruction queue.

5. The network processor of claim 3, wherein the DFA instructions indicate the packet data stored in the cache-coherent memory to use and the at least one DFA graph stored in the non-cache memory to traverse.

6. The network processor of claim 3, wherein the DFA module schedules the DFA instruction to the at least one of the plurality of DFA thread engine engines.

7. The network processor of claim 1, further comprising a result word into which the intermediate and final results are written.

8. The network processor of claim 7, wherein the result word includes an instruction-completed field indicative of a completed DFA instruction when set.

9. The network processor of claim 1, further comprising a node-type identifier for identifying types of nodes of the at least one DFA graph.

10. The network processor of claim 9, wherein the node-type identifier is a marked node, traversal of the marked node unhindering traversal of the graph for identifying a particular node for analysis.

11. A method of traversing DFA graphs with incoming packet data, comprising:

storing at least one DFA graph, having a number of nodes for searching for multiple patterns in one traversal of the at least one DFA graph, in a non-cache coherent memory that is;

i) external to a processor and ii) sized to accommodate the at least one DFA graph;

storing in a cache-coherent memory, a DFA instruction for traversing nodes of the at least one DFA, the DFA instruction indicating packet data stored in the cache-coherent memory to use and the at least one DFA graph stored in the non-cache memory to traverse;

traversing the at least one DFA graph by;

i) fetching the packet data stored in the cache-coherent memory, and ii) in response to each byte of packet data fetched from the cache-coherent memory, issuing an instruction to access and load a next node of the at least one DFA graph from the non-cache memory to traverse the next node of the at least one DFA graph; and

writing intermediate and final results of the traversing to the cache-coherent memory, the at least one DFA graph being traversed by a DFA thread engine that is independent of other DFA thread engines traversing DFA graphs, including the at least one DFA graph.

12. The method of claim 11, further comprising providing a node-type identifier for identifying a respective node type for each of the nodes of the DFA graph, wherein the intermediate and final results are determined from the node-type identifiers.

13. A network processor, comprising:

means for storing at least one DFA graph in a non-cache coherent memory that is;

i) external to the network processor and ii) sized to accommodate the at least one DFA graph having a number of nodes for searching for multiple patterns in one traversal of the at least one DFA graph;

means for storing in a cache-coherent memory, a DFA instruction for traversing the plurality of nodes of the at least one DFA, the DFA instruction indicating packet data stored in the cache-coherent memory to use and the at least one DFA graph stored in the non-cache memory to traverse;

means for traversing the at least one DFA graph by;

i) fetching the packet data stored in the cache-coherent memory, and ii) in response to each byte of packet data fetched from the cache-coherent memory, issuing an instruction to access and load a next node of the at least one DFA graph from the non-cache memory to traverse the next node of the at least one DFA graph, the means for traversing being independent of other means for traversing DFA graphs including the at least one DFA graph, the means for traversing searches a data packet different for data packets being searched by the other means for traversing;

means for writing intermediate and final results of the traversing to the cache-coherent memory.