Deterministic finite automata (DFA) instruction

• US 20060075206A1
• Filed: 09/07/2005
• Published: 04/06/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,301,788 B2
• Time in Patent Office: Days
• US Class Current: 711/202
• 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 method for automatically performing a pattern search in input data using a plurality of previously-stored deterministic finite automata (DFA) graphs comprising:

providing an instruction including a plurality of fields;

writing a DFA graph identifier into a respective one of the plurality of fields identifying one of the plurality of previously-stored DFA graphs;

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 process the input data using the identified DFA graph and to provide results as instructed by the output reference.

2. The method of claim 1, wherein the DFA graph identifier comprises a base memory address to the identified one of the plurality of previously-stored DFA graph.

3. The method of claim 1, further comprising 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.

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

5. The method of claim 1, further comprising writing a start-node identifier into a respective one of the plurality of fields, identifying one of a plurality of nodes of the previously-stored DFA graph, at which processing of the input data will begin.

6. 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.

7. 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.

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

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

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

11. A computer-readable instruction for searching for a pattern in input data using a deterministic finite automaton (DFA) graph previously-stored in a computer memory comprising:

a DFA graph identifier field identifying the previously-stored DFA graph;

an input data reference field identifying the start location of input data to be searched using the identified DFA graph; and

an output reference field identifying the location in memory of results generated by traversing the identified DFA graph responsive to the input data.

12. The instruction of claim 11, wherein the DFA graph identifier field comprises a base memory address to the identified one of the plurality of previously-stored DFA graphs.

13. The instruction of claim 11, 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.

14. The instruction of claim 11, wherein the output reference field comprises a memory reference into which results are written.

15. The instruction of claim 11, further comprising a start-node identifier field, the start-node identifier field identifying one of a plurality of nodes of the previously-stored DFA graph at which processing of the input data will begin.

16. The instruction of claim 11, 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.

17. The instruction of claim 11, 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.

18. The instruction of claim 11, wherein the plurality of fields are arranged into a plurality of words stored in memory.

19. The instruction of claim 11, wherein the identified DFA graph can include up to about 128,000 nodes.

20. The instruction of claim 11, wherein the identified DFA graph can include up to about 1,000,000 nodes.

21. A processor adapted to automatically process data using a plurality of previously-stored deterministic finite automata (DFA) graphs comprising:

means for providing an instruction including a plurality of fields;

means for writing a DFA graph identifier into a respective one of the plurality of fields identifying one of the plurality of previously-stored DFA graphs;

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 graphs;

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 process the input data using the identified DFA graphs and to provide results as instructed by the output reference.