Content search mechanism that uses a deterministic finite automata (DFA) graph, a DFA state machine, and a walker process

• US 8,560,475 B2
• Filed: 09/12/2005
• Issued: 10/15/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: Carlson, David A., Bouchard, Gregg A., Parker, Trent, Hussain, Muhammad R.
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US11/224,728
• Publication Number:
  US 20060085533A1
• Time in Patent Office: 2,955 Days
• Field of Search: 715/736, 709/223, 706/12, 706/45, 706/62
• US Class Current: 706/45
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 9/4498 Finite state machines

Abstract

An improved content search mechanism uses a graph that includes intelligent nodes avoids the overhead of post processing and improves the overall performance of a content processing application. An intelligent node is similar to a node in a DFA graph but includes a command. The command in the intelligent node allows additional state for the node to be generated and checked. This additional state allows the content search mechanism to traverse the same node with two different interpretations. By generating state for the node, the graph of nodes does not become exponential. It also allows a user function to be called upon reaching a node, which can perform any desired user tasks, including modifying the input data or position.

Claims

1. A network services processor comprising:

a processor;

a memory storing a Deterministic Finite Automata (DFA) graph having a plurality of nodes, each node of the plurality representing a state of a DFA state machine, from each state of the DFA state machine there is one valid state transition, the DFA graph having at least one node associated with a command that allows the processor to interpret the state of the DFA state machine represented by a subject node;

the processor executing a walker process to traverse the DFA graph to search for a match defined by a regular expression in an input stream, the walker process having an associated walker state;

upon the walker process reaching the at least one node associated with the command, the processor executing the command to set or check the walker state, the walker state being set or checked is different and in addition to the states of the DFA state machine represented by the plurality of nodes; and

the processor interpreting the state of the DFA state machine represented by the subject node based on the walker state set or checked by the executed command.

2. The network services processor of claim 1, wherein the command is specified by the at least one node.

3. The network services processor of claim 1, wherein the command is specified by an arc in the DFA graph.

4. The network services processor of claim 1, further comprising a second memory accessible by the processor, the second memory storing the walker process.

5. The network services processor of claim 1, wherein the memory comprises a low-latency memory directly accessible by the processor.

6. The network services processor of claim 1, wherein the state includes start offset, end offset and depth into an expression.

7. The network services processor of claim 1, wherein the walker state further includes at least one of a thread-based state that is set or checked by the command for non-fixed-length expressions matching a variable number of characters and a break-based state that is set or checked by the command upon a match of a part of the regular expression.

8. A method for performing a search for a match for an expression in a string of characters comprising:

generating a Deterministic Finite Automata (DFA) graph for searching for the expression, the DFA graph having a plurality of nodes, each node representing a state of a DFA state machine, from each state of the DFA state machine there is one valid state transition, the DFA graph having at least one node associated with a command that allows the state of the DFA state machine represented by a subject node to be interpreted;

walking the DFA graph for each character in the string of characters to search for the match defined by the expression in the string;

upon reaching the at least one node in the DFA graph associated with the command, executing the command to set or check a walker state associated with the walking, the walker state being set or checked is different and in addition to the states of the DFA state machine represented by the plurality of nodes; and

interpreting the state of the DFA state machine represented by the subject node based on the walker state set or checked by the executed command.

9. A network services processor comprising:

a memory storing a Deterministic Finite Automata (DFA) graph having a plurality of nodes, each node of the plurality representing a state of a DFA state machine, from each state of the DFA state machine there is one valid state transition, the DFA graph having at least one node associated with a command that allows the processor to interpret the state of the DFA state machine represented by a subject node;

a content search mechanism, the content search mechanism comprising;

a walker that walks the nodes in the DFA graph to search for a match in an input stream by executing a command stored in one of the nodes to set or check a walker state associated with the walker, the walker state being set or checked is different and in addition to the states of the DFA state machine represented by the plurality of nodes; and

an interpreter that interprets the state of the DFA state machine represented by the subject node based on the walker state set or checked by the executed command.

10. The network services processor of claim 9 wherein the content search mechanism further comprises a compiler that generates the DFA graph.

11. The network services processor of claim 9, wherein the walker state further includes at least one of a thread-based state that is set by the command for non-fixed-length expressions, the non-fixed-length expressions matching a variable number of characters and a break-based state that is set or checked by the command upon a match of a part of the input stream.

12. A computer implemented method for traversing a deterministic finite automata-based (DFA) graph comprising:

traversing nodes in the DFA graph to search for an expression in an input stream based on pointers to next nodes stored in a node, each node representing a state of a DFA state machine, from each state of the DFA state machine there is one valid state transition, the DFA graph having at least one node associated with a command that allows the processor to interpret the state of the DFA state machine represented by a subject node;

upon detecting a command associated with the node, executing a function identified by the command to set or check a walker state, the walker state being set or checked is different and in addition to the states of the DFA state machine represented by the nodes; and

interpreting the state of the DFA state machine represented by the subject node based on the walker state set or checked by the executed function identified by the command.

13. The computer implemented method of claim 12, wherein the command reports a match for the expression in the input stream.

14. The computer implemented method of claim 12, wherein the walker state further includes at least one of a thread-based state that is set or checked by the command for non-fixed-length expressions, the non-fixed-length expressions matching a variable number of characters and a break-based state that is set or checked by the command upon a match of a part of the expression in the input stream.

15. A computer implemented method for generating a deterministic finite automata-based (DFA) graph comprising:

parsing expressions to determine locations for breaks;

building the DFA graph by creating nodes and arcs to nodes, each node representing a state of a DFA state machine and each arc representing a valid state transition from each state;

inserting intelligence in a node by storing a command in a node corresponding to a break location, the break location being set or checked by the command upon a match of a part of the parsed expressions, the command being stored sets or checks a walker state that is different and in addition to the states of the DFA state machine represented by the nodes, the command being executed when the node is reached during a graph walk; and

enabling a state of the state of the DFA state machine represented by a subject node to be interpreted based on the walker state set or checked by the command.

16. The computer implemented method of claim 15, wherein inserting further comprises storing another command at a node corresponding to a break exit.

17. The computer implemented method of claim 15, wherein inserting further comprises storing another command at a node corresponding to a thread change.

18. The computer implemented method of claim 15, wherein inserting further comprises storing another command at a node corresponding to an expression no longer matching.