Memory management in a token stitcher for a content search system having pipelined engines
A content search system includes multiple pipelined search engines that implement different portions of a regular expression search operation. For some embodiments, the search pipeline includes a DFA engine, an NFA engine, and a token stitcher that combines partial match results generated by the DFA and NFA engines. The token stitcher can be configured to implement unbounded sub-expressions without utilizing resources of the DFA or NFA engines. The token stitcher may comprise a flag bank for storing a number of flags. Each flag may identify a sub-expression that matches the input string. The flag bank may be configured to discard one or more flags upon satisfaction of a predetermined condition for purposes of recapturing hardware resources to provide a certain level of performance.
1. A token stitcher for determining whether an input string of characters matches a regular expression comprising a number of sub-expressions, the token stitcher comprising:
a flag bank storing a number of flags, where each flag identifies one or more of the sub-expressions that match the input string; and
a token stitcher engine configured to implement an unbounded sub-expression without utilizing resources of a deterministic finite state automaton (DFA) engine or a non-deterministic finite state automaton (NFA) engine and to identify one or lore programs stored in a program memory that are associated with a new token received by the token stitcher, wherein a particular program in the program memory is configured to indicate a match when a particular set of flags in the flag bank are asserted, and
wherein the flag bank is configured to discard one or more flags upon satisfaction of a predetermined condition and wherein the token stitcher is implemented by at least one processor-based computing device.
2. The token stitcher of claim 1 , wherein the predetermined condition is whether the token stitcher has examined a particular number of input characters of the input string since a sub-expression matched the input string.
3. The token stitcher of claim 1 , wherein the predetermined condition is whether a particular number of flags have been stored in the flag bank.
4. The token stitcher of claim 1 , wherein the predetermined condition is whether the token stitcher has received an instruction to save a state of the token stitcher.
5. The token stitcher of claim 1 , wherein the predetermined condition is whether a current character being examined in the input string is a new line character.
6. The token stitcher of claim 1 , wherein the flag bank is configured to discard, upon satisfaction of the predetermined condition, one flag associated with a sub-expression that was matched at an offset which is further from a current offset being examined in the input string than any other sub-expression.
7. The token stitcher of claim 1 , wherein the flag bank is configured to discard, upon satisfaction of the predetermined condition, all flags associated with sub-expressions that were matched at an offset which is further from a current offset being examined in the input string than any other sub-expression.
8. The token stitcher of claim 1 , wherein the flag bank is configured to discard, upon satisfaction of the predetermined condition, any flag that is associated with a partial match whose relevance in evaluating a match condition has been rendered moot by another flag stored in the flag bank.
9. The token stitcher of claim 1 , wherein the flag bank is configured to discard flags associated with sub-expressions that cannot result in a match across multiple lines when a current character in input string being examined is a new line character.
10. The token stitcher of claim 1 , wherein the flag bank is configured to discard, upon satisfaction of the predetermined condition, any number of flags that are each associated with an offset that is more than a predetermined distance away from a current offset being examined.
11. The token stitcher of claim 1 , wherein the flag bank is configured to store an offset associated with a first occurrence of a sub-expression, but not any other occurrence of the sub-expression, for a flag stored in the flag bank.
12. An apparatus for determining whether an input string of characters matches a regular expression comprising a number of sub-expressions, comprising:
means for storing a record of which sub-expressions match the input string; and
means for implementing an unbounded sub-expression without utilizing resources of a deterministic finite state automaton (DFA) engine or a non-deterministic finite state automaton (NFA) engine and for identifying one or more programs responsible for processing a sub-expression that matches the input string, and
wherein the means for storing is configured to discard one or more records upon satisfaction of a predetermined condition and wherein the means for implementing the unbounded sub-expression is implemented by at least one processor-based computing device.
13. The apparatus of claim 12 , wherein the predetermined condition is whether a particular number of input characters of the input string has been examined since a sub-expression matched the input string.
14. The apparatus of claim 12 , wherein the predetermined condition is whether a particular number of records have been stored by the means for storing.
15. The apparatus of claim 12 , wherein the predetermined condition is whether an instruction to save a state of the apparatus has been received.
16. The apparatus of claim 12 , wherein the predetermined condition is whether a current character being examined in the input string is a new line character.
17. The apparatus of claim 12 , wherein the means for storing is configured to discard, upon satisfaction of the predetermined condition, one record associated with a sub-expression that was matched at an offset which is further from a current offset being examined in the input string than any other sub-expression.
18. The apparatus of claim 12 , wherein the means for storing is configured to discard, upon satisfaction of the predetermined condition, all records associated with sub-expressions that were matched at an offset which is further from a current offset being examined in the input string than any other sub-expression.
19. The apparatus of claim 12 , wherein the means for storing is configured to discard, upon satisfaction of the predetermined condition, any record that is associated with a partial match whose relevance in evaluating a match condition has been rendered moot by another record stored in the means for storing.
20. The apparatus of claim 12 , wherein the means for storing is configured to discard records associated with sub-expressions that cannot result in a match across multiple lines when a current character in the input string being examined is a new line character.
21. The apparatus of claim 12 , wherein the means for storing is configured to discard, upon satisfaction of the predetermined condition, any number of records that are each associated with an offset that is more than a predetermined distance away from a current offset being examined.
22. The apparatus of claim 12 , wherein the means for storing is configured to store an offset associated with a first occurrence of a sub-expression, but not any other occurrence of the sub-expression, for a record stored in the means for storing.