Content search mechanism

• US 20060085533A1
• Filed: 09/12/2005
• Published: 04/20/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., Hussain, Muhammad R., Carlson, David A., Parker, Trent
• Granted Patent: US 8,560,475 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• 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; and

a memory, the memory storing a graph having a plurality of nodes, the processor executing a walker process having an associated walker state to walk the graph to search for a match defined by a regular expression in an input stream, at least one node in the graph associated with a command, upon reaching the at least one node, the processor executing the command to manage the state.

2. A network services processor of claim 1, wherein the command is specified by the node.

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

4. The network services processor of claim 1, wherein the command allows the processor to traverse a same node with different interpretations.

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

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

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

8. The network services processor of claim 1, wherein the walker state comprises at least one of a thread-based state and a break-based state.

9. A content search mechanism comprising:

a compiler that generates a graph having a plurality of intelligent nodes;

and

a walker process that executes a command associated with one of the intelligent nodes to manage a walker state while walking the graph stored in a memory to search for a match in an input stream based on a sequence of characters defined by an expression.

10. The content search mechanism of claim 9, wherein the command is specified by the intelligent node.

11. The content search mechanism of claim 9, wherein the command is specified by an arc in the graph.

12. The content search mechanism of claim 9, wherein the command allows the processor to traverse a same intelligent node with different interpretations.

13. The content search mechanism of claim 9, wherein the walker state comprises at least one of a thread-based state and a break-based state.

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

generating a graph for searching for the expression, the graph having a plurality of intelligent nodes;

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

upon reaching at least one intelligent node in the graph associated with a command, executing the command to manage a walker state associated with the command.

15. A network services processor comprising:

a memory storing a graph having a plurality of intelligent nodes; and

a content search mechanism, the content search mechanism comprising a walker that walks the intelligent nodes in the graph to search for a match in an input stream by executing a command stored in one of the intelligent nodes to manage a walker state associated with the command.

16. The network services processor of claim 15 wherein the content search mechanism further comprises a compiler that generates the graph.

17. The network services processor of claim 15, wherein the walker state comprises at least one of a thread-based state and a break-based state.

18. A computer implemented method for traversing a deterministic finite automata-based graph comprising:

traversing nodes in the graph to search for an expression in an input stream based on pointers to next nodes stored in a node; and

upon detecting a command associated with the node, executing a function identified by the command to manage a walker state.

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

20. The computer implemented method of claim 18, wherein the walker state comprises at least one of a thread-based state and a break-based state.

21. A computer implemented method for generating a deterministic finite automata-based graph comprising:

parsing expressions to determine locations for breaks;

building the graph by creating nodes and arcs to nodes; and

inserting intelligence in a node by storing a command in a node corresponding to a break location, the command being executed when the node is reached during a graph walk.

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

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

24. The computer implemented method of claim 21, wherein inserting further comprises storing another command at a node corresponding to an expression match.

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

26. A deterministic finite automata-based graph comprising:

at least one data node, the data node storing a command, the command executed while walking the graph to search for a match for a sequence of characters defined by a regular expression in an input stream; and

a state for storing status of a data node while walking the graph, the state including start offset, and end offset of an expression.