Deterministic finite automata (DFA) instruction

• US 8,301,788 B2
• Filed: 09/07/2005
• Issued: 10/30/2012
• 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): SHAW, PETER C
• Application Number:
  US11/220,899
• Publication Number:
  US 20060075206A1
• Time in Patent Office: 2,610 Days
• Field of Search: 709/208, 709/221, 709/231, 709/246, 709/230, 704/1, 704/2, 704/9, 711/121, 711/138, 341/51, 341/52, 341/174, 370/389, 370/392, 370/503
• US Class Current: 709/230
• CPC Class Codes: G06F 9/30003 Arrangements for executing specific machine instructions
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end

Abstract

A computer-readable instruction is described for traversing deterministic finite automata (DFA) graphs to perform a pattern search in the in-coming packet data in real-time. The instruction includes one or more pre-defined fields. One of the fields includes a DFA graph identifier for identifying one of several previously-stored DFA graphs. Another one of the fields includes an input reference for identifying input data to be processed using the identified DFA graphs. Yet another one of the fields includes an output reference for storing results generated responsive to the processed input data. The instructions are forwarded to a DFA engine adapted to process the input data using the identified DFA graph and to provide results as instructed by the output reference.

Claims

1. A computer-implemented method for automatically performing a pattern search in input data, the method comprising:

providing an instruction including a plurality of fields for traversing nodes of a DFA graph, any of which can be, without prior definition, a start node at which processing of input data starts, the instruction being provided allows the processing of the input data to start at any node of the DFA graph;

writing a DFA graph identifier into a respective one of the plurality of fields identifying which one of a plurality of previously-stored DFA graphs to traverse, the DFA graph identifier comprising a base memory address providing a location in memory of where the identified DFA graph is stored;

writing an input reference into a respective one of the plurality of fields identifying input data to be processed using the identified DFA graph;

writing an output reference into a respective one of the plurality of fields identifying the output reference for storing results generated responsive to the processed input data; and

forwarding the instruction to a DFA engine adapted to traverse the nodes of the identified DFA graph starting at the start node to process the input data and to provide results as instructed by the output reference.

2. The method of claim 1, further comprising selecting an input-mode indicator selectable between a direct mode and a gather mode, the direct mode indicating that the input reference identifies a memory reference to input data stored in memory, the gather mode indicating that the input reference identifies a memory reference to a gather list of pointers, each pointer of the gather list identifying a memory reference to a respective portion of the input data.

3. The method of claim 1, wherein the output reference comprises a memory reference into which results are written.

4. The method of claim 1, further comprising writing a replication factor into a respective one of the plurality of fields, the replication factor identifying a number of replicated copies available of the previously-stored DFA graph.

5. The method of claim 1, further comprising writing a maximum results value into a respective one of the plurality of fields, the maximum results value identifying a maximum allowed number of results, wherein processing of input data is terminated responsive to the number of results exceeding the maximum results value.

6. The method of claim 1, wherein the plurality of fields are arranged into a plurality of words stored in memory.

7. The method of claim 1, wherein the identified DFA graph can include up to about 128,000 nodes.

8. The method of claim 1, wherein the identified DFA graph can include up to about 1,000,000 nodes.

9. A non-transitory computer-readable medium storing instructions for searching for a pattern in input data that, when executed by a computer, cause the computer to:

write a DFA graph identifier into a respective one of a plurality of fields of an instruction for traversing nodes of a DFA graph, any of which can be, without prior definition, a start node at which processing of input data starts, the instruction being provided allows the processing of the input data to start at any node of the DFA graph, the DFA graph identifier identifying a previously-stored DFA graph to traverse, the DFA graph identifier comprising a base memory address providing a location in memory of where the identified DFA graph is stored;

write an input data reference into a respective one of the plurality of fields identifying the start location of input data to be searched using the identified DFA graph;

write an output reference into a respective one of the plurality of fields identifying the location in memory of results generated by traversing nodes of the identified DFA graph responsive to the input data; and

forward the instruction to a DFA engine adapted to traverse the nodes of the identified DFA graph starting at the start node to process the input data and to provide results as instructed by the output reference.

10. The non-transitory computer readable medium of claim 9, further comprising an input-mode indicator field selectable between a direct mode and a gather mode, the direct mode indicating that the input reference identifies a memory reference to input data stored in contiguous memory locations, the gather mode indicating that the input reference identifies a memory reference to a gather list of pointers, each pointer of the gather list identifying a memory reference to a respective portion of the input data.

11. The non-transitory computer readable medium of claim 9, wherein the output reference field comprises a memory reference into which results are written.

12. The non-transitory computer readable medium of claim 9, further comprising a replication field, the replication field adapted to contain a replication factor identifying a number of available replicated copies of the previously-stored DFA graph.

13. The non-transitory computer readable medium of claim 9, further comprising a maximum results field, the maximum results field adapted to contain a value identifying a maximum allowed number of results, wherein processing of input data is terminated responsive to the number of results exceeding the maximum results value.

14. The non-transitory computer readable medium of claim 9, wherein the plurality of fields are arranged into a plurality of words stored in memory.

15. The non-transitory computer readable medium of claim 9, wherein the identified DFA graph can include up to about 128,000 nodes.

16. The non-transitory computer readable medium of claim 9, wherein the identified DFA graph can include up to about 1,000,000 nodes.

17. A processor adapted to automatically process data, the processor comprising:

means for providing an instruction including a plurality of fields for traversing nodes of a DFA graph, any of which can be without prior definition a start node at which processing of input data starts, the instruction being provided allows the processing of the input data to start at any node of the DFA graph;

means for writing a DFA graph identifier into a respective one of a plurality of fields identifying which one of a plurality of previously-stored DFA graphs to traverse, the DFA graph identifier comprising a base memory address providing a location in memory of where the identified DFA graph is stored;

means for writing an input reference into a respective one of the plurality of fields identifying input data to be processed using the identified DFA graph;

means for writing an output reference into a respective one of the plurality of fields identifying output reference for storing results generated responsive to the processed input data; and

means for forwarding the instruction to a DFA engine adapted to traverse the nodes of the identified DFA graph starting at the start node to process the input data and to provide results as instructed by the output reference.