Programmable rule processing apparatus for conducting high speed contextual searches and characterizations of patterns in data

• US 7,451,143 B2
• Filed: 08/27/2003
• Issued: 11/11/2008
• Est. Priority Date: 08/28/2002
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Patil, Rajesh, Sharangpani, Harshvardhan
• Primary Examiner(s): Le; Miranda
• Assistant Examiner(s): TIMBLIN, ROBERT M
• Application Number:
  US10/650,363
• Publication Number:
  US 20040059725A1
• Time in Patent Office: 1,903 Days
• Field of Search: 707/6, 707/3, 712/220, 712/224, 712/10, 712/16, 377/54, 326/39
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and apparatus is disclosed herein for a rule processor for conducting contextual searches, the processor comprising a plurality of input payload search registers, search execution engine coupled to the plurality of search registers to perform one or more contextual searches on content in the search registers by via parallel pattern matching in response to executing rules specifying the one or more searches, and presenting one or more patterns to the content in the search registers.

Claims

1. A system for conducting contextual searches, the system comprising:

a rule processor comprising;

a plurality of M input payload search registers, wherein a data stream of content data to be searched is input into the plurality of payload search registers;

a search execution engine comprising;

a search array coupled to the plurality of M search registers, wherein the search array comprises;

a plurality of M rows of search array elements coupled to a plurality of M output match lines; and

a plurality of N columns of search array elements coupled to a plurality of N pattern input lines comprising a search pattern, wherein the search array comprises an array of M by N search array elements, and wherein the content data in the plurality of M search registers is replicated and stored N times in the plurality of N columns in the search array, wherein the N content data in each column of the N columns are shifted in row positions relative to the row positions of the content data in each of the other columns of the N columns; and

a sorter coupled to the search array to perform one or more contextual searches on content in the search array via parallel pattern matching in response to executing one or more search instructions specifying the one or more pattern searches and presenting one or more patterns to the content, wherein the parallel pattern matching comprises performing a simultaneous search within all M rows for all of the N search pattern elements input by the N pattern input lines, all in one clock period.

2. The system defined in claim 1 wherein fields of the one or more search instructions are coupled to the plurality of search registers and the search execution engine.

3. The system defined in claim 1 wherein at least one of the one or more search instructions specifies a pattern that is to be searched against the content in the search array and zero or more search parameters.

4. The system defined in claim 3 wherein one parameter specifies a portion of the pattern to be masked to enable a subset of the pattern to be searched against the content in the search array.

5. The system defined in claim 4 wherein the portion of the pattern to be masked is specified by a mask vector to mask off specific bytes in the pattern.

6. The system defined in claim 4 wherein the zero or more parameters specify starting and ending locations that constitute a range of the content within the search array within which the search execution engine is to constrain a search.

7. The system defined in claim 4 wherein the at least one of the instructions specifies a windowed-find-first-forward search.

8. The system defined in claim 4 wherein the at least one of the instructions specifies a windowed-find-first-reverse search.

9. The system defined in claim 1 wherein the search execution engine generates at least one result output indicative of success in searching the content in the search array.

10. The system defined in claim 9, wherein the at least one result output comprises an indication of whether or not a match occurred between a pattern specified in at least one of the instructions and the content in the search array.

11. The system defined in claim 9, wherein the at least one result output comprises an indication of a location in the search array where a match occurred between a pattern specified in at least one of the instructions and the content in the search array.

12. The system defined in claim 1 wherein at least one search instruction includes a field that specifies a parameter to use to control the search or a pointer into a memory that stores the parameter to control the search.

13. The system defined in claim 12 wherein the pointer points to a general purpose register.

14. The system defined in claim 12 wherein a value to which the pointer points is a result of a previously performed search by a search execution hardware.

15. The system defined in claim 12 wherein the parameter corresponds to one of a group that includes a mask, a search window parameter, and a control parameter.

16. The system defined in claim 1 wherein the plurality of input payload search registers comprises a register file.

17. The system defined in claim 16 wherein the register file comprises 2K entries of one byte each.

18. The system defined in claim 16 wherein the register file comprises a plurality of entries addressed by 11-bit register addresses.

19. The system defined in claim 1 further comprising a memory to store one or more search instructions to be applied to content in the search array.

20. The system defined in claim 1 wherein the search instructions cause the search execution engine to perform searches for arbitrarily long patterns in the content in the search array.

21. The system defined in claim 1 further comprising an instruction sequencer for applying one or more search instructions to the search execution engine.

22. The system defined in claim 21 wherein the one or more search instructions specify at least one pattern, range control, and program control flow.

23. The system defined in claim 21 wherein the one or more search instructions include a pointer to specify a memory location that stores information that specifies at least one pattern, range control, and program control flow.

24. The system defined in claim 21 wherein at least one search instruction in the one or more search instructions comprises opcode information to indicate a search operation type, pattern information to specify a pattern to be located, a mask to specify a portion of the pattern information that comprises the pattern, and a pair of offsets to specify starting and ending bounds of locations in the search registers for the search for the at least one search instruction.

25. The system defined in claim 1 wherein the search execution engine comprises a first output indication indicative of search success of execution of one search instruction and a second output indication indicative of a location within the search registers of a pattern specified by the one search instruction.

26. The system defined in claim 1 wherein the search array comprises M match lines with each of the M match lines associated with a group of data stored in the search array and being indicative of whether a pattern specified by one of the one or more search instructions matches data in its associated group of data stored in the search array.

27. The system defined in claim 26 wherein the sorter is coupled to receive the M match lines to perform the one or more operations associated with matches indicated by the M match lines.

28. The system defined in claim 27 wherein the information specifies a range, and the sorter sorts the M match lines only in the specified range.

29. The system defined in claim 28 wherein the range is specified in the search instruction.

30. The system defined in claim 28 wherein the information specifies a location in a memory at which the range is stored.

31. The system defined in claim 30 wherein the memory is a register file.

32. The system defined in claim 1 wherein the search array comprises a first input to receive bits including the pattern and a second input for a mask, the search array to mask zero or more bits of the bits corresponding to the pattern based on the mask.

33. The system defined in claim 32 wherein the bits including the pattern comprises N bytes and the mask comprises N bits, each of the N bits being associated with a different one of the N bytes, wherein the search array masks one of the N bytes of the pattern when its associated bit of the N bit mask is in a first state.

34. The system defined in claim 1 wherein the sorter has a first output indicating whether one or more of the match lines match and a second output indicative of a result of performing the one or more operations.

35. The system defined in claim 34 wherein the second output is indicative of a location into the search array of a first occurrence of a match between the pattern and data stored in the search array in relation to one side of the search array.

36. The system defined in claim 34 wherein the second output is indicative of a number of matches in a range of the M match lines.

37. The system defined in claim 1 wherein the sorter operates in response to a range mask to mask out one or more outputs of the search array for a search operation.

38. The system defined in claim 1 wherein the sorter further comprises:

a priority encoder to identify a location in the search array corresponding to the M match lines corresponding to a first occurrence of a match between the pattern and data stored in the search array in relation to one side of the search array.

39. The system defined in claim 38 wherein the priority encoder is an ascending priority encoder and the one side of the search array is the top of the search array.

40. The system defined in claim 38 wherein the priority encoder is a descending priority encoder and the one side of the search array is the bottom of the search array.

41. The system defined in claim 1 wherein the sorter further comprises a counter to determine a number of matches in the search array.

42. The system defined in claim 1 wherein the sorter further comprises:

an ascending priority encoder to identify a location in the search array corresponding to the M match lines corresponding to a first occurrence of a match between the pattern and data stored in the search array in relation to a top side of the search array;

a descending priority encoder to identify a location in the search array corresponding to the M match lines corresponding to a first occurrence of a match between the pattern and data stored in the search array in relation to a bottom side of the search array;

a counter to determine a number of matches in a range of the M match lines; and

a selector coupled to the ascending priority encoder, the descending priority encoder and the counter and having a first output, the selector operable to select an output of the ascending priority encoder, the descending priority encoder and the counter as the first output of the sorter.

43. The system defined in claim 42 wherein the selector has a second output indicating if a match occurred between the pattern and data in the search array.

44. The system defined in claim 1 wherein the search array comprises:

a plurality of rows of memory locations to store bytes of data;

a plurality of rows of byte comparators to compare bytes of the data stored in the plurality of rows of memory locations with bytes of the pattern, each comparator of the plurality of rows of byte comparators having an output;

a plurality of masked reduction units, each of the plurality of masked reduction units coupled to receive byte masks and comparator outputs of comparators in one row of byte comparators, the plurality of masked reduction units masking individual comparator outputs based on the byte masks and combining unmasked comparator outputs for each row into one of a plurality of mask lines.

45. The system defined in claim 1 further comprising:

a rule memory to store a plurality of rules;

a rule sequencer coupled to the rule memory to select one or more rules for execution; and

a decoder to decode the one or more rules selected by the rule sequencer, the decoder coupled to the search array and sorter to provide decoded information to the search array and the sorter.

46. The system of claim 1, wherein the search array performs pattern matching between data stored in the search array and an N byte pattern from a search instruction received on a first input, the search array having M match lines as outputs with each of the M match lines associated with a group of data stored in the array and being indicative of whether the N byte pattern matches data stored in its associated group of data stored in the search array, and wherein the sorter receives the M match lines to perform one or more operations associated with matches indicated by the M match lines, the one or more operations being performed in response to information specified by the rule, and further wherein the sorter outputs data indicative of any match found.

47. The system defined in claim 46, wherein the sorter has a first output indicating whether one or more of the match lines match and a second output indicative of a result of performing the one or more operations.

48. The system defined in claim 46 wherein the search array includes a second input to receive an N bit mask to apply to the N byte pattern.

49. The system defined in claim 46 wherein the sorter comprises a range mask to mask out a portion of the M mask lines based on a range.

50. The system defined in claim 49 wherein the range mask logically ANDs the M mask lines with a pair of offsets specified by the search instruction.

51. The system defined in claim 50 wherein the rule includes the pair of offsets.

52. The system defined in claim 49 wherein the rule includes a pointer to a location in a memory where the offsets are stored.

53. The system defined in claim 46 wherein the data output for the sorter is feedback for use and an input to the sorter in the next cycle.

54. The system defined in claim 46 wherein the sorter further comprises:

a priority encoder to identify a location in the search array corresponding to the M match lines corresponding to a first occurrence of a match between the pattern and data stored in the search array in relation to one side of the search array.

55. The system defined in claim 54 wherein the priority encoder is an ascending priority encoder and the one side of the search array is the top of the search array.

56. The system defined in claim 54 wherein the priority encoder is a descending priority encoder and the one side of the search array is the bottom of the search array.

57. The system defined in claim 46 wherein the sorter further comprises a counter to determine a number of matches in a range of the M match lines.

58. The system defined in claim 46 wherein the sorter further comprises:

an ascending priority encoder to identify a location in the search array corresponding to the M match lines corresponding to a first occurrence of a match between the pattern and data stored in the search array in relation to a top side of the search array;

a descending priority encoder to identify a location in the search array corresponding to the M match lines corresponding to a first occurrence of a match between the pattern and data stored in the search array in relation to a bottom side of the search array;

a counter to determine a number of matches in a range of the M match lines; and

a selector coupled to the ascending priority encoder, the descending priority encoder and the counter and having a first output, the selector operable to select an output of the ascending priority encoder, the descending priority encoder and the counter as the first output of the sorter.

59. The system defined in claim 54 wherein the selector has a second output indicating if a match occurred between the pattern and data in the search array.

60. The system defined in claim 46 wherein each of the N bits is associated with a different one of the N bytes, wherein the search array masks one of the N bytes of the pattern when its associated bit of the N bit mask is in a first state.

61. The system defined in claim 46 wherein the information specifies a range, and the sorter sorts the M match lines only in the specified range.

62. The system defined in claim 61 wherein the range is specified in the search instruction.

63. The system defined in claim 61 wherein the information specifies a location in a memory at which the range is stored.

64. The system defined in claim 46 wherein the search array comprises:

a plurality of rows of memory locations to store bytes of the data;

a plurality of rows of byte comparators to compare bytes of the data stored in the plurality of rows of memory locations with bytes of pattern, each comparator of the plurality of rows of byte comparators having an output;

a plurality of masked reduction units, each of the plurality of masked reduction units coupled to receive byte masks and comparator outputs of comparators in one row of byte comparators, the plurality of masked reduction units masking individual comparator outputs based on the byte masks and combining unmasked comparator outputs for each row into one of the M mask lines.

65. The system defined in claim 46 further comprising:

a rule memory to store a plurality of search instructions;

a rule sequencer coupled to the search instruction memory to select one or more search instructions for execution; and

a decoder to decode the one or more search instructions selected by the rule sequencer, the decoder coupled to the search array and sorter to provide decoded information to the search array and the sorter.

66. A process comprising:

loading a set of input payload search registers with content data;

storing a replication of the content data in the payload search registers in a search array coupled to the registers, wherein the search array comprises;

a plurality of M rows of search array elements coupled to a plurality of M output match lines; and

a plurality of N columns of search array elements coupled to a plurality of N pattern input lines comprising a search pattern, wherein the search array comprises an array of M by N search array elements, and wherein the storing of the replication of content comprises replicating and storing the content in the M input payload search registers a plurality of times, in the plurality of N columns of search array elements, wherein the N content data in each column of the N columns are shifted in row positions relative to the row positions of the content data in each of the other columns of the N columns;

presenting by means of the plurality of N pattern input lines a pattern identified by a search instruction to be searched in the search registers;

performing parallel pattern matching between the pattern and the content stored in the search array, wherein the parallel pattern matching comprises performing a search query simultaneously within all M rows for all of the N search pattern elements input by the N pattern input lines, all in one clock period; and

outputting by means of the plurality of M output match lines an indication of a result of performing the pattern matching.

67. The process defined in claim 66 further comprising:

generating a plurality of match lines associated with rows of the search array, wherein match lines of the plurality of match lines indicating whether a match occurred between the pattern and data in a row associated with one of the match lines;

performing the one or more operations on at least a set of the match lines in response to information specified by the search instruction;

outputting an indication as to whether one or more of the match lines match the pattern and a result of performing the one or more operations.

68. The process defined in claim 66 wherein loading the search registers is performed to store, replicate, and interleave data such that data for one row is stored in an adjacent row in shifted form.

69. The process defined in claim 66 further comprising:

converting code into a sequence of search instructions;

executing the sequences of search instructions in consecutive cycles such that pattern matching is performed for each of the plurality of search instructions.

70. A process for performing contextual searches in a pipelined fashion, the process comprising:

fetching a rule from a rule memory;

decoding the rule and assembling indirect fields, if any;

storing a replication of content in a plurality of input payload search registers in a search array coupled to the registers,

wherein the search array comprises;

a plurality of M rows of search array elements coupled to a plurality of M output match lines; and

a plurality of N columns of search array elements coupled to a plurality of N pattern input lines comprising a search pattern, wherein the search array comprises an array of M by N search array elements, wherein the storing of the replication of content comprises replicating and storing the content in the M input payload search registers N times, once in each of the N columns of search array elements, wherein the row positions of the replicated content within each column of the N columns of search array elements is shifted relative to the row positions of the replicated content in each of its adjacent columns of search array elements;

executing one or more search operations on values in the search array; and

performing sort operations on results of executing the one or more search operations.

71. The process defined in claim 70 wherein the process is performed in a four stage pipeline with a search array and a sorter.