Deterministic finite automata (DFA) processing

• US 20060069872A1
• Filed: 09/07/2005
• Published: 03/30/2006
• 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., Kessler, Richard E., Hussain, Muhammad R., Carlson, David A.
• Granted Patent: US 8,392,590 B2
• Time in Patent Office: Days
• US Class Current: 711/121
• 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; and

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 with packet data stored in a cache-coherent memory responsive to instructions from the at least one processor core.

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

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

at least one DFA thread engine 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 DFA thread engine.

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 DFA thread engine.

7. The network processor of claim 6, wherein the least one DFA thread engine:

fetches the packet data stored in the cache-coherent memory;

issues a non-cache memory load instruction per byte of packet data received from the cache-coherent memory to traverse a next state of the DFA graph stored in the non-cache memory; and

writes intermediate and final results to the cache-coherent memory.

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

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

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

a plurality of DFA thread engines associated in a shared configuration with the at least one processor core, each DFA thread engine adapted to traverse at least one DFA graph stored in the non-cache memory.

11. The network processor of claim 1, further comprising a node-type identifier for identifying types of nodes of the DFA graphs.

12. The network processor of claim 11, wherein the node-type identifier is a marked node, traversal of the marked node unhindering traversal of the graph.

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

storing at least one DFA graph in a non-cache coherent memory;

storing a DFA instruction in a cache-coherent memory, 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; and

traversing the DFA graph using the stored packet data and writing intermediate and final results to the cache-coherent memory.

14. The method of claim 13, wherein the at least one processor core submits DFA instructions to a DFA module.

15. The method of claim 14, wherein the DFA module schedules the DFA instruction to at least one DFA thread engine.

16. The method of claim 15, wherein the least one DFA thread engine:

fetches the packet data stored in the cache-coherent memory;

issues one non-cache memory load instruction per byte of packet data fetched from the cache-coherent memory;

traverses to a next state of the DFA graph stored in the non-cache memory responsive to the fetched byte of packet data; and

writes intermediate and final results to the cache-coherent memory.

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

18. A network processor, comprising:

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

means for storing a DFA instruction in a cache-coherent memory, 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; and

means for traversing the DFA graph using the stored packet data and writing intermediate and final results to the cache-coherent memory.