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

• US 8,818,921 B2
• Filed: 09/27/2013
• Issued: 08/26/2014
• 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: Hussain, Muhammad R., Carlson, David A., Bouchard, Gregg A., Parker, Trent
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US14/040,323
• Publication Number:
  US 20140032607A1
• Time in Patent Office: 333 Days
• Field of Search: 706/12, 706/45, 706/62
• US Class Current: 706/12
• 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:

at least one processor configured to search for a match of at least one pattern in an input stream by traversing a data structure generated from one or more regular expressions describing patterns for the search; and

at least one memory operatively coupled to the at least one processor and configured to store the generated data structure, the generated data structure including at least one node having an intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node and to qualify validity of the match, of the at least one pattern in the input stream, determined at the at least one node, by comparing at least one offset, of at least one character of the at least one pattern matching in the input stream, to a given range limit, wherein the generated data structure is a Deterministic Finite Automata (DFA) graph.

2. The network services processor of claim 1, wherein the intelligent node structure associates at least one command with the at least one node enabling the at least one processor to call a function to perform the at least one task upon reaching the at least one node, the at least one command being determined by a compiler of the generated data structure.

3. The network services processor of claim 2, wherein the at least one command is based on at least one characteristic, of the one or more regular expressions, determined by the compiler by parsing the one or more regular expressions during generation of the data structure.

4. The network services processor of claim 3, wherein the at least one characteristic includes whether or not the one or more regular expressions is a fixed or non-fixed expression.

5. The network services processor of claim 1, wherein the intelligent node structure associates at least one command with the at least one node enabling the at least one processor to call at least one function to perform the at least one task, the intelligent node structure storing the at least one command directly or referencing another location at which the at least one command is stored.

6. The network services processor of claim 1, wherein the DFA graph is a DFA state machine, the next node represents a next state of the DFA state machine for a given character of the input stream, and the intelligent node structure enables additional state to be generated or checked, the additional state being in addition to and different from state of the DFA state machine.

7. The network services processor of claim 1, wherein the at least one processor is further configured to execute a walker process to traverse the generated data structure with characters from the input stream and the intelligent node structure enables the walker process to generate or check a walker state associated with the walker process.

8. The network services processor of claim 1, wherein the at least one task performed is determined during generation of the DFA graph enabling a size of a traditional DFA graph to be reduced and enabling post processing of results, generated by a search using the traditional DFA, to be obviated.

9. The network services processor of claim 1, wherein the intelligent node structure enables the at least one processor to determine start or end offsets of the at least one pattern matching in the input stream.

10. The network services processor of claim 1, wherein the intelligent node structure enables the at least one processor to apply restrictions on reporting of the match of the at least one pattern in the input stream.

11. The network services processor of claim 1, wherein the intelligent node structure enables the at least one processor to report the match, of the at least one pattern matching in the input stream, at the at least one node, based on applying restrictions to qualify the validity of the match, at the at least one node.

12. A method comprising:

parsing one or more regular expressions describing patterns for searching an input stream for at least one pattern;

generating a data structure, from the one or more regular expressions parsed, to enable a search, by at least one processor, for a match of the at least one pattern in the input stream, by traversing, with characters from the input stream, the data structure generated;

including at least one node having an intelligent node structure in the data structure generated, the intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node and to qualify the match, of the at least one pattern in the input stream, determined at the intelligent node, by comparing at least one offset, of at least one character of the at least one pattern in the input stream, to a given range limit; and

storing the data structure generated in at least one memory operatively coupled to the at least one processor, wherein the data structure generated is a Deterministic Finite Automata (DFA) graph.

13. The method of claim 12, further comprising determining at least one command, the intelligent node structure associating the at least one command determined with the at least one node enabling the at least one processor to call a function to perform the at least one task upon reaching the at least one node.

14. The method of claim 13, wherein the at least one command is determined based on at least one characteristic, of the one or more regular expressions, by parsing the one or more regular expressions during the generating.

15. The method of claim 14, wherein the at least one characteristic includes whether or not the one or more regular expressions is a fixed or non-fixed expression.

16. The method of claim 12, further comprising directly storing the at least one command in the intelligent node structure or providing a reference in the intelligent node structure to another location at which the at least one command determined is stored, wherein the intelligent node structure associates the at least one command determined with the at least one node enabling the at least one processor to call at least one function to perform the at least one task.

17. The method of claim 12, wherein DFA graph is a DFA state machine, the next node represents a next state of the DFA state machine for a given character of the input stream, and the intelligent node structure enables additional state to be generated or checked, the additional state being in addition to and different from state of the DFA state machine.

18. The method of claim 12, further comprising executing a walker process to traverse the data structure generated with characters from the input stream, wherein the intelligent node structure enables the walker process to generate or check a walker state associated with the walker process.

19. The method of claim 12, wherein the at least one task is determined during the generating, enabling a size of a traditional DFA graph to be reduced and enabling post processing of results, generated by a search using the traditional DFA, to be obviated.

20. The method of claim 12, wherein the intelligent node structure enables the at least one processor to determine start or end offsets of the at least one pattern matching in the input stream.

21. The method of claim 12, wherein the intelligent node structure enables the at least one processor to apply restrictions on reporting of the match of the at least one pattern in the input stream.

22. The method of claim 12, wherein the intelligent node structure enables the at least one processor to report the match, of the at least one pattern matching in the input stream, at the at least one node, based on applying restrictions to qualify the validity of the match, at the at least one node.

23. A non-transitory computer-readable medium having stored thereon a sequence of instructions which, when loaded and executed by a processor, causes the processor to:

search for a match of at least one pattern in an input stream by traversing a data structure generated from one or more regular expressions including at least one pattern, the generated data structure including at least one node having an intelligent node structure including information to direct the at least one processor, based on a match result of a given character of the input stream at the at least one node, to traverse to a next node and to perform at least one task upon reaching the at least one node and to qualify validity of the match, of the at least one pattern in the input stream, determined at the at least one node, by comparing at least one offset, of at least one character of the at least one pattern matching in the input stream, to a given range limit, wherein the data structure generated is a Deterministic Finite Automata (DFA) graph.

24. A non-transitory computer-readable medium having stored thereon a sequence of instructions which, when loaded and executed by a processor, causes the processor to:

parse one or more regular expressions describing patterns for searching an input stream for at least one pattern;

generate a data structure, from the one or more regular expressions parsed, to enable a search, by at least one processor, for a match of the at least one pattern in the input stream, by traversing, with characters from the input stream, the data structure generated;

include at least one node having an intelligent node structure in the data structure generated, the intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node and to qualify validity of the match, of the at least one pattern in the input stream, determined at the at least one node, by comparing at least one offset, of at least one character of the at least one pattern matching in the input stream, to a given range limit; and

store the data structure generated in at least one memory operatively coupled to the at least one processor, wherein the data structure generated is a Deterministic Finite Automata (DFA) graph.

25. A network services processor comprising:

at least one processor configured to search for a match of at least one pattern in an input stream by traversing a data structure generated from one or more regular expressions describing patterns for the search; and

at least one memory operatively coupled to the at least one processor and configured to store the generated data structure, the generated data structure including at least one node having an intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node by storing commands packed as a stream of instructions representing commands for interpretation by a walker process being executed by the at least one processor for the traversing, by storing commands compiled into processor-native binaries for direct execution by the at least one processor as a subroutine in the walker process, or by storing a combination thereof.

26. A network services processor comprising:

at least one processor configured to search for a match of at least one pattern in an input stream by traversing a data structure generated from one or more regular expressions describing patterns for the search; and

at least one memory operatively coupled to the at least one processor and configured to store the generated data structure, the generated data structure including at least one node having an intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node, wherein the intelligent node structure enables storing of offsets of characters in the input stream to enable determination and reporting of a start or end offset of the at least one pattern matching in the input stream by a walker process executed by the at least one processor for the traversing.

27. A network services processor comprising:

at least one processor configured to search for a match of at least one pattern in an input stream by traversing a data structure generated from one or more regular expressions describing patterns for the search; and

at least one memory operatively coupled to the at least one processor and configured to store the generated data structure, the generated data structure including at least one node having an intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node, wherein the intelligent node structure associates at least one command, with the at least one node, enabling the at least one processor to store a start offset, end offset, and identifier, associated with a regular expression of the one or more regular expressions, in a report data structure based on the at least one pattern matching in the input stream upon reaching the at least one node.

28. A method comprising:

parsing one or more regular expressions describing patterns for searching an input stream for at least one pattern;

generating a data structure, from the one or more regular expressions parsed, to enable a search, by at least one processor, for a match of the at least one pattern in the input stream, by traversing, with characters from the input stream, the data structure generated;

including at least one node having an intelligent node structure in the data structure generated, the intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node by storing commands packed as a stream of instructions representing commands for interpretation by a walker process being executed by the at least one processor for the traversing, by storing commands compiled into processor-native binaries for direct execution by the at least one processor as a subroutine in the walker process, or by storing a combination thereof; and

storing the data structure generated in at least one memory operatively coupled to the at least one processor.

29. A method comprising:

parsing one or more regular expressions describing patterns for searching an input stream for at least one pattern;

generating a data structure, from the one or more regular expressions parsed, to enable a search, by at least one processor, for a match of the at least one pattern in the input stream, by traversing, with characters from the input stream, the data structure generated;

including at least one node having an intelligent node structure in the data structure generated, the intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node and wherein the intelligent node structure enables storing of offsets of characters in the input stream to enable determination and reporting of a start or end offset of the at least one pattern matching in the input stream by a walker process executed by the at least one processor for the traversing; and

storing the data structure generated in at least one memory operatively coupled to the at least one processor.

30. A method comprising:

parsing one or more regular expressions describing patterns for searching an input stream for at least one pattern;

generating a data structure, from the one or more regular expressions parsed, to enable a search, by at least one processor, for a match of the at least one pattern in the input stream, by traversing, with characters from the input stream, the data structure generated;

including at least one node having an intelligent node structure in the data structure generated, the intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node and wherein the intelligent node structure associates at least one command, with the at least one node, enabling the at least one processor to store a start offset, end offset, and identifier, associated with a regular expression of the one or more regular expressions, in a report data structure based on the at least one pattern matching in the input stream upon reaching the at least one node; and

storing the data structure generated in at least one memory operatively coupled to the at least one processor.