Memory management for finite automata processing

• US 9,823,895 B2
• Filed: 04/14/2014
• Issued: 11/21/2017
• Est. Priority Date: 08/30/2013
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Billa, Satyanarayana Lakshmipathi, Shanava, Yossef, Nakada, Timothy Toshio, Dikshit, Abhishek
• Primary Examiner(s): Tsai, Henry
• Assistant Examiner(s): Roche, John
• Application Number:
  US14/252,354
• Publication Number:
  US 20150067200A1
• Time in Patent Office: 1,317 Days
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 21/567 using dedicated hardware
• CPC Class Codes: G06F 2205/126 Monitoring of intermediate fill level, i.e. with additional means for monitoring the fill level, e.g. half full flag, almost empty flag
• CPC Class Codes: G06F 2213/2806 Space or buffer allocation for DMA transfers
• CPC Class Codes: G06F 5/14 for overflow or underflow handling, e.g. full or empty flags
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: H04L 41/28 Restricting access to network management systems or functions, e.g. using authorisation function to access network configuration
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

Matching at least one regular expression pattern in an input stream may be optimized by initializing a search context in a run stack based on (i) partial match results determined from walking segments of a payload of a flow through a first finite automation and (ii) a historical search context associated with the flow. The search context may be modified via push or pop operations to direct at least one processor to walk segments of the payload through the at least one second finite automation. The search context may be maintained in a manner that obviates overflow of the search context and obviating stalling of the push or pop operations to increase match performance.

Claims

1. A security appliance operatively coupled to a network, the security appliance comprising:

at least one memory configured to store a first finite automaton, at least one second finite automaton, and a run stack; and

at least one processor operatively coupled to the at least one memory and configured to search for at least one regular expression pattern in a flow, the search including;

initializing a search context in the run stack based on (i) partial match results determined from walking segments of a payload of the flow through the first finite automaton and (ii) a historical search context associated with the flow;

modifying the search context via push or pop operations to direct the at least one processor to walk segments of the payload through the at least one second finite automaton to explore whether at least one partial match of at least one regular expression pattern identified via the first automaton advances along at least one path of the at least one second finite automaton; and

maintaining the search context in a manner obviating overflow of the search context and obviating stalling of the push or pop operations.

2. The security appliance of claim 1, wherein the search context includes a plurality of search context entries and each search context entry is determined based on a given positive partial match result of the partial match results.

3. The security appliance of claim 1, wherein initializing the search context in the run stack includes:

generating a respective subpattern search context entry for each partial match of the at least one regular expression pattern identified as matching in the flow based on walking segments of the payload of the flow through the first finite automaton; and

merging the historical search context and each respective subpattern search context entry in the run stack.

4. The security appliance of claim 3, wherein merging the historical search context and each respective subpattern search context entry in the run stack includes obviating copying of each respective subpattern search context entry and each search context entry of the historical search context.

5. The security appliance of claim 4, wherein obviating copying includes skipping over each respective subpattern search context entry and each search context entry that has a context entry type field configured with a no operation (NOP) type of a plurality of node types.

6. The security appliance of claim 3, wherein merging the historical search context and each respective subpattern search context entry in the run stack includes linking chunks of fixed size buffers via next and previous pointers, each fixed size buffer configured to store a given number of search context entries.

7. The security appliance of claim 3, wherein each at least one second finite automaton is a per-pattern non-deterministic finite automaton (NFA) generated for a respective regular expression pattern and each respective subpattern search context entry includes:

a node identifier of a given node of a given per-pattern NFA of the at least one second finite automaton, the given per-pattern NFA generated for a given regular expression pattern including a respective subpattern identified as matching in the flow;

a location identifier of a given segment of the segments of the payload, the at least one processor further configured to advance the search by subsequently walking the given segment at the given node, the given segment identified based on the location identifier; and

a walk direction for subsequently walking a next segment of the payload at a next node of the given per-pattern NFA, the at least one processor further configured to explore whether a given partial match advances along at least one path by subsequently walking the next segment at the next node based on a positive match of the given segment at the given node.

8. The security appliance of claim 1, wherein the at least one memory further includes a save buffer and the historical search context includes one or more search context entries from a previous search context associated with the flow and saved from the run stack to the save buffer.

9. The security appliance of claim 8, wherein the payload is a current payload and the previous search context was saved from the run stack to the save buffer based on detection of a payload boundary of a previous payload of the flow during walking of segments of the previous payload through the at least one second finite automaton.

10. The security appliance of claim 1, wherein the payload is a current payload and the historical search context includes at least one search context entry configured to enable the at least one processor to walk a given node of a given second finite automaton of the at least one second finite automaton with a given segment of the current payload and wherein the historical search context was created based on detection of a payload boundary during NFA processing of a previous payload in the flow.

11. The security appliance of claim 1, wherein the search context includes at least one search context entry that includes a plurality of fields and the plurality of fields includes:

a context entry type field that is based on a node type, of a plurality of node types, of the given node, the context entry type field signifying which fields, of the plurality of fields, are relevant for the node type;

a match type field that is relevant based on the context entry type field, the match type field being based on the node type and used to determine whether the given node is configured to match a single instance or multiple consecutive instances of a given element in an input stream received from the network;

an element field that is relevant regardless of the context entry type field and identifies the given element for matching at the given node;

a next node address field that is relevant regardless of the context entry type field and identifies a next node;

a count field that is relevant based on the context entry type field and identifies a count value, indicating a number of consecutive instances remaining for positively matching to the given element or having been positively matched to the given element, at the given node, based on the context entry type field;

a discard unexplored context (DUP) field that is relevant regardless of the context entry type field and identifies whether to discard the context entry or walk the next node based on the context, in an event a complete match of at least one regular expression is detected in the input stream;

a reverse walk direction field that is relevant regardless of the context entry type field and identifies a reverse or forward direction of walking; and

an offset field that is relevant regardless of the context entry type field and identifies an offset of a segment of a given payload of the flow in the input stream for matching to the given element at the given node or to a next element at the next node, based on the context entry type field, the next element identified via metadata associated with the next node.

12. The security appliance of claim 1, wherein the at least one memory further includes a save buffer and the search further includes saving the search context from the run stack to the save buffer based on detecting a payload boundary of the payload during the walk of segments of the payload through the at least one second finite automaton, the search context saved to the save buffer in association with the flow to enable the at least one processor to employ the saved search context as the historical search context for directing the at least one processor to walk a previous or subsequent payload of the flow through the at least one second finite automata.

13. The security appliance of claim 1, wherein obviating overflow of the search context and obviating stalling of the push or pop operations includes maintaining the search context by employing an internal circular buffer and an external circular buffer and the run stack has a Last-In-First-Out (LIFO) characteristic.

14. The security appliance of claim 13, wherein maintaining the search context includes maintaining entries of the external circular buffer as a doubly linked list of chunks of fixed size buffers each configured to store a given number of search context entries.

15. The security appliance of claim 13, wherein maintaining the search context includes maintaining a first portion of the search context from the run stack in the internal circular buffer and a second portion of the search context from the run stack in the external circular buffer.

16. The security appliance of claim 13, wherein the search further includes transferring search context entries between the internal and external circular buffers in a manner that prevents (i) overflow of the internal circular buffer, (ii) a combination of an empty state of the internal circular buffer and a non-empty state of the external circular buffer to obviate stalling of the pop operation, and (iii) a full state of the internal circular buffer by maintaining a given number of empty search context entries to obviate stalling of the push operation.

17. The security appliance of claim 13, wherein the search further includes transferring context entries between the internal and external circular buffers as a function of low and high watermarks associated with the internal circular buffer.

18. The security appliance of claim 17, wherein the search further includes:

transferring context entries from the internal circular buffer to the external circular buffer based on a total number of context entries stored in the internal circular buffer relative to the high watermark; and

transferring context entries from the external circular buffer to the internal circular buffer based on the total number of context entries stored in an on-chip buffer relative to the low watermark, wherein each transfer is a direct memory access (DMA) transfer.

19. The security appliance of claim 1, further comprising at least one network interface, wherein the payload is in an input stream received via the at least one network interface, the input stream including multiple packets with payloads of the flow that are consecutive or non-consecutive packets in the input stream.

20. A method comprising:

operatively coupling at least one processor to at least one memory in a security appliance operatively coupled to a network, the least one memory configured to store a first finite automaton, at least one second finite automaton, and a run stack, the at least one processor configured to search for at least one regular expression pattern in a flow, the search including;

initializing a search context in the run stack based on (i) partial match results determined from walking segments of a payload of the flow through the first finite automaton and (ii) a historical search context associated with the flow;

modifying the search context via push or pop operations to direct the at least one processor to walk segments of the payload through the at least one second finite automaton to explore whether at least one partial match of at least one regular expression pattern identified via the first automaton advances along at least one path of the at least one second finite automaton; and

maintaining the search context in a manner obviating overflow of the search context and obviating stalling of the push or pop operations.

21. The method of claim 20, wherein the search context includes a plurality of search context entries and each search context entry is determined based on a given positive partial match result of the partial match results.

22. The method of claim 20, wherein initializing the search context in the run stack includes:

generating a respective subpattern search context entry for each partial match of the at least one regular expression pattern identified as matching in the flow based on walking segments of the payload of the flow through the first finite automaton; and

merging the historical search context and each respective subpattern search context entry in the run stack.

23. The method of claim 22, wherein merging the historical search context and each respective subpattern search context entry in the run stack includes obviating copying of each respective subpattern search context entry and each search context entry of the historical search context.

24. The method of claim 23, wherein obviating copying includes skipping over each respective subpattern search context entry and each search context entry that has a context entry type field configured with a no operation (NOP) type of a plurality of node types.

25. The method of claim 22, wherein merging the historical search context and each respective subpattern search context entry in the run stack includes linking chunks of fixed size buffers via next and previous pointers, each fixed size buffer configured to store a given number of search context entries.

26. The method of claim 22, wherein each at least one second finite automaton is a per-pattern non-deterministic finite automaton (NFA) generated for a respective regular expression pattern and each respective subpattern search context entry includes:

a node identifier of a given node of a given per-pattern NFA of the at least one second finite automaton, the given per-pattern NFA generated for a given regular expression pattern including a respective subpattern identified as matching in the flow;

a location identifier of a given segment of the segments of the payload, the at least one processor further configured to advance the search by subsequently walking the given segment at the given node, the given segment identified based on the location identifier; and

a walk direction for subsequently walking a next segment of the payload at a next node of the given per-pattern NFA, the at least one processor further configured to explore whether a given partial match advances along at least one path by subsequently walking the next segment at the next node based on a positive match of the given segment at the given node.

27. The method of claim 20, wherein the at least one memory further includes a save buffer and the historical search context includes one or more search context entries from a previous search context associated with the flow and saved from the run stack to the save buffer.

28. The method of claim 27, wherein the payload is a current payload and the previous search context was saved from the run stack to the save buffer based on detection of a payload boundary of a previous payload of the flow during walking of segments of the previous payload through the at least one second finite automaton.

29. The method of claim 20, wherein the payload is a current payload and the historical search context includes at least one search context entry configured to enable the at least one processor to walk a given node of a given second finite automaton of the at least one second finite automaton with a given segment of the current payload and wherein the historical search context was created based on detection of a payload boundary during NFA processing of a previous payload in the flow.

30. The method of claim 20, wherein the search context includes at least one search context entry that includes a plurality of fields and the plurality of fields includes:

a context entry type field that is based on a node type, of a plurality of node types, of the given node, the context entry type field signifying which fields, of the plurality of fields, are relevant for the node type;

a match type field that is relevant based on the context entry type field, the match type field being based on the node type and used to determine whether the given node is configured to match a single instance or multiple consecutive instances of a given element in an input stream received from the network;

an element field that is relevant regardless of the context entry type field and identifies the given element for matching at the given node;

a next node address field that is relevant regardless of the context entry type field and identifies a next node;

a count field that is relevant based on the context entry type field and identifies a count value, indicating a number of consecutive instances remaining for positively matching to the given element or having been positively matched to the given element, at the given node, based on the context entry type field;

a discard unexplored context (DUP) field that is relevant regardless of the context entry type field and identifies whether to discard the context entry or walk the next node based on the context, in an event a complete match of at least one regular expression is detected in the input stream;

a reverse walk direction field that is relevant regardless of the context entry type field and identifies a reverse or forward direction of walking; and

an offset field that is relevant regardless of the context entry type field and identifies an offset of a segment of a given payload of the flow in the input stream for matching to the given element at the given node or to a next element at the next node, based on the context entry type field, the next element identified via metadata associated with the next node.

31. The method of claim 20, wherein the at least one memory further includes a save buffer and the search further includes saving the search context from the run stack to the save buffer based on detecting a payload boundary of the payload during the walk of segments of the payload through the at least one second finite automaton, the search context saved to the save buffer in association with the flow to enable the at least one processor to employ the saved search context as the historical search context for directing the at least one processor to walk a previous or subsequent payload of the flow through the at least one second finite automata.

32. The method of claim 20, wherein obviating overflow of the search context and obviating stalling of the push or pop operations includes maintaining the search context by employing an internal circular buffer and an external circular buffer and the run stack has a Last-In-First-Out (LIFO) characteristic.

33. The method of claim 32, wherein maintaining the search context includes maintaining entries of the external circular buffer as a doubly linked list of chunks of fixed size buffers each configured to store a given number of search context entries.

34. The method of claim 32, wherein maintaining the search context includes maintaining a first portion of the search context from the run stack in the internal circular buffer and a second portion of the search context from the run stack in the external circular buffer.

35. The method of claim 32, wherein the search further includes transferring search context entries between the internal and external circular buffers in a manner that prevents (i) overflow of the internal circular buffer, (ii) a combination of an empty state of the internal circular buffer and a non-empty state of the external circular buffer to obviate stalling of the pop operation, and (iii) a full state of the internal circular buffer by maintaining a given number of empty search context entries to obviate stalling of the push operation.

36. The method of claim 32, wherein the search further includes transferring context entries between the internal and external circular buffers as a function of low and high watermarks associated with the internal circular buffer.

37. The method of claim 36, wherein the search further includes:

transferring context entries from the internal circular buffer to the external circular buffer based on a total number of context entries stored in the internal circular buffer relative to the high watermark; and

transferring context entries from the external circular buffer to the internal circular buffer based on the total number of context entries stored in an on-chip buffer relative to the low watermark, wherein each transfer is a direct memory access (DMA) transfer.

38. The method of claim 20, further comprising at least one network interface, wherein the payload is in an input stream received via the at least one network interface, the input stream including multiple packets with payloads of the flow that are consecutive or non-consecutive packets in the input stream.

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

initialize a search context in the run stack based on (i) partial match results determined from walking segments of a payload of the flow through a first finite automaton and (ii) a historical search context associated with the flow;

modify the search context via push or pop operations to direct the at least one processor to walk segments of the payload through the at least one second finite automaton to explore whether at least one partial match of at least one regular expression pattern identified via the first automaton advances along at least one path of the at least one second finite automaton; and

maintain the search context in a manner obviating overflow of the search context and obviating stalling of the push or pop operations.