System and method for rule matching in a processor

Patent metadata

Field	Value
Publication number	US-9866540-B2
Application number	US-201615145052-A
Country	US
Kind code	B2
Filing date	May 3, 2016
Priority date	Aug 2, 2011
Publication date	Jan 9, 2018
Grant date	Jan 9, 2018

Abstract

In one embodiment, a system includes a format block configured to receive a key, at least one rule, and rule formatting information. The rule can have one or more dimensions. The format block can be further configured to extract each of the dimensions from the at least one rule. The system can further include a plurality of dimension matching engines (DME). Each DME can be configured to receive the key and a corresponding formatted dimension, and process the key and the corresponding dimension for returning a match or nomatch. The system can further include a post processing block configured to analyze the matches or no matches returned from the DMEs and return a response based on the returned matches or nomatches.

First claim

What is claimed is:

1. A system comprising:
a format block configured to (a) receive a key including one or more bits from a packet, at least one rule for matching the key, and rule formatting information, the at least one rule having at least one rule dimension, the at least one rule dimension including a set of one or more bits from a corresponding rule of the at least one rule, and (b) extract each at least one rule dimension from the at least one rule; and
a plurality of dimension matching engines (DMEs), each DME, of the plurality of DMEs, coupled to the format block and configured to receive the key and a corresponding formatted dimension, and process the key and the corresponding formatted dimension for returning a match or nomatch.

2. The system of claim 1 , wherein the matches or no matches returned from the plurality of DMEs enables an analysis of the matches or no matches and return of a response based on the returned matches or nomatches.

3. The system of claim 1 , wherein the format block includes:
a start block configured to find rule starts, mark invalid or deactivated rules, and pre-calculate terms of the at least one rule dimension;
a middle block configured to remove marked rules, extract rule format from headers, and extract priority from headers;
a tween block configured to calculate rule header end position information and rule dimension end position information; and
a finish block configured to calculate control for the plurality of DMEs.

4. The system of claim 1 , wherein the plurality of DMEs are further configured to match the key to at least one of a range indicated by a minimum and maximum in the corresponding formatted dimension, an exact match indicated by a match value in the corresponding formatted dimension, a prefix match indicated by a prefix length and a match value in the corresponding formatted dimension, and a mask indicated by a bit mask and a match value indicated by the corresponding formatted dimension.

5. The system of claim 1 , wherein the plurality of DMEs further include at least one rule data aligner configured to align bits of a match value of the rule of the corresponding formatted dimension to a particular granularity.

6. The system of claim 1 , wherein the plurality of DMEs further include at least one key data aligner configured to align bits of the key to a particular granularity.

7. The system of claim 1 , wherein the plurality of DMEs further include a match unit to compare the key to the match value of the corresponding formatted dimension.

8. The system of claim 1 , wherein the plurality of DMEs further include a DME buffer unit configured to receive portions of a particular dimension in a buffer over a plurality of clock cycles and reassemble the portions into the particular dimension.

9. The system of claim 1 , further comprising a post processing block configured to return a response representing a Boolean—and of the matches or no matches returned from the plurality of DMEs.

10. The system of claim 9 , wherein the post processing block is further configured to sort multiple responses from the plurality of DMEs for multiple rules.

11. The system of claim 1 , wherein the format block is further configured to receive the at least one rule by receiving at least one line of data, each line of data having a particular size and each line further storing at least one rule and/or at least one partial rule that occupy the particular size, where the at least one partial rule can continue on a subsequent line of the at least one line or be continued from a previous line of the at least one line.

12. A method comprising:
in a hardware processor:
receiving from a memory, at a format block, a key including one or more bits from a packet, at least one rule for matching the key, and rule formatting information, the at least one rule having at least one rule dimension;
extracting, at the format block, each at least one rule dimension from the at least one rule, the at least one rule dimension including a set of one or more bits from a corresponding rule of the at least one rule;
receiving, at a plurality of dimension matching engines (DMEs), each DME, of the plurality of DMEs, coupled to the format block, the key and a corresponding formatted dimension; and
processing, at the plurality of DMEs, the key and the corresponding formatted dimension for returning a match or nomatch.

13. The method of claim 12 , wherein the matches or no matches returned from the plurality of DMEs enables an analysis of the matches or no matches and return of a response based on the returned matches or nomatches.

14. The method of claim 12 , further comprising:
within the format block:
finding, in a start block, rule starts;
marking, in the start block, invalid or deactivated rules;
pre-calculating, in the start block, terms of the at least one rule dimension;
removing, in a middle block, marked rules;
extracting, in the middle block, rule format from headers and priority from headers;
calculating, in a tween block, rule header end position information and rule dimension end position information; and
calculating, in a finish block, control for the plurality of DMEs.

15. The method of claim 12 , further comprising matching, at the plurality of DMEs, the key to at least one of a range indicated by a minimum and maximum in the corresponding formatted dimension, an exact match indicated by a match value in the corresponding formatted dimension, a prefix match indicated by a prefix length and a match value in the corresponding formatted dimension, and a mask indicated by a bit mask and a match value indicated by the corresponding formatted dimension.

16. The method of claim 12 , further comprising aligning, at a rule data aligner within the plurality of DMEs, bits of a match value of the rule of the corresponding formatted dimension to a particular granularity.

17. The method of claim 12 , further comprising aligning, at a key data aligner within the plurality of DMEs, bits of the key to a particular granularity.

18. The method of claim 12 , further comprising comparing, at a match unit within the plurality of DMEs, the key to the match value of the corresponding formatted dimension.

19. The method of claim 12 , further comprising:
receiving, at a DME buffer unit within the plurality of DMEs, portions of a particular dimension in a buffer over a plurality of clock cycles; and
reassembling, at the DME buffer unit, the portions into the particular dimension.

20. The method of claim 12 , further comprising returning, at a post processing block, a response representing a Boolean—and of the matches or no matches returned from the plurality of DMEs.

21. The method of claim 20 , further comprising sorting, at the post processing block, multiple responses from the plurality of DMEs for multiple rules.

22. The method of claim 12 , wherein receiving the at least one rule includes receiving at least one line of data, each line of data having a particular size and each line further storing at least one rule and/or at least one partial rule that occupy the particular size, where the at least one partial rule can continue on a subsequent line of the at least one line or be continued from a previous line of the at least one line.

Assignees

• Cavium Inc

Inventors

• Bouchard Gregg A
• Goyal Rajan
• Lund Gregory E

Classifications

• G06F13/16

  for access to memory bus (G06F13/28 takes precedence) · CPC title

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• H04L45/742

  Route cache; Operation thereof · CPC title

• G06F9/46

  Multiprogramming arrangements · CPC title

• G11C7/1075

  for multiport memories each having random access ports and serial ports, e.g. video RAM · CPC title