Granted Patent B2

US 7,861,291 · App. 11/422,063 · Granted Dec 28, 2010

Abstract

Claims (120)

1. A computer-implemented method comprising:

constructing, using a processor, one or more subtables in a first memory area accessible by the processor;

reading, from a second memory area using the processor, a plurality of rules in order of increasing rule priority, wherein each of the rules includes one or more subkeys and one or more submasks;

upon reading each of the plurality of rules, using the processor to add rule information to the subtables in a manner that stores rule information distinguishing the rule being added from every rule previously added with lower rule priorities, the adding of the rule information further comprising:

identifying a range of indices in one of the subtables corresponding to one of the rule's subkeys and one of the rule's submasks;

looping through a plurality of entries of the subtables, starting at a first entry, wherein the plurality of entries is indexed by the identified range of indices and for each of the entries, determining whether a set of a plurality of key bits corresponding to the rule have been exhausted, wherein the rule's key bits are the bits included in the rule's subkey; and

in response to the rule's key bits being exhausted:

decrementing a counter corresponding to a second subtable being addressed by the first entry;

removing the second subtable in response to the decremented counter indicating that no entries address the second subtable;

receiving, at a network adapter, an incoming packet that includes a plurality of fields and forming a key from the plurality of the fields, wherein the formed key includes a plurality of subkeys; and

searching the entries stored in the subtables for one or more of the subkeys, wherein a different subtable is used to search for each of the subkeys; and wherein a next level subkey is selected and a next level subtable is searched when a pointer value is encountered in the previous level subtable.

2. The method of claim 1 further comprising:

in response to identifying the rule corresponding to one of the entries that corresponds to the searched subkeys:

retrieving a stored key and a stored mask from the entry that identified the rule;

masking the key using the stored mask, the masking resulting in a masked key;

applying the identified rule in response to the masked key matching the stored key; and

applying a default rule in response to the masked key not matching the stored key.

3. The method of claim 1 wherein, in response to the rule's key bits not being exhausted, the method further comprises:

determining whether the subtable entry's type is currently set to a failure data type; and

in response to the subtable entry's type currently being set to a failure data type:

resetting the subtable entry to address a data entry, wherein the addressed data entry corresponds to the rule being added; and

incrementing a data entry counter that corresponds to the number of subtable entries that reference the addressed data entry.

4. The method of claim 3 wherein, in response to the subtable entry's type not currently being set to a failure data type, the method further comprises:

identifying a first subtable currently being addressed by the subtable entry;

decrementing a first counter that tracks the number of entries that reference the first subtable;

determining whether a second subtable which is an alternative version of the first subtable currently exists;

in response to the second subtable not existing:

creating an uncompressed alternate subtable that corresponds to the second subtable;

adding the rule to a plurality of entries in the uncompressed alternate subtable;

generating a reference to a compressed version of the uncompressed alternate subtable; and

storing the created reference in the subtable's entry;

re-addressing the entry to the second subtable;

incrementing a second counter that tracks the number of entries that reference the second subtable; and

determining whether to remove the first subtable.

5. The method of claim 4 wherein the creation of the uncompressed alternate subtable further comprises:

in response to the subtable entry's type being a rule data type, creating the uncompressed alternate subtable of a predetermined size where each entry in the created uncompressed alternate subtable is the rule data type and wherein each entry in the created uncompressed alternate subtable references a common rule entry; and

in response to the subtable entry's type being a pointer type, decompressing the subtable that is referenced by the subtable entry.

6. The method of claim 1 wherein determining whether to remove the subtable further comprises:

removing the subtable from memory in response to determining that the decremented counter is equal to zero.

7. A data processing system comprising:

one or more processors;

a memory array accessible by the processors;

a network connection that connects the data processing system to a computer network;

a set of instructions stored in the memory, wherein one or more of the processors executes the set of instructions in order to perform actions of:

constructing, using a processor, one or more subtables in a first memory area accessible by the processor;

reading, from a second memory area using the processor, a plurality of rules in order of increasing rule priority, wherein each of the rules includes one or more subkeys and one or more submasks;

upon reading each of the plurality of rules, adding rule information to the subtables in a manner that stores rule information distinguishing the rule being added from every rule previously added with lower rule priorities, the adding of the rule information further comprising:

identifying a range of indices in one of the subtables corresponding to one of the rule's subkeys and one of the rule's submasks;

looping through a plurality of entries of the subtables, starting at a first entry, wherein the plurality of entries is indexed by the identified range of indices and for each of the entries, determining whether a set of a plurality of key bits corresponding to the rule have been exhausted, wherein the rule's key bits are the bits included in the rule's subkey; and

in response to the rule's key bits being exhausted:

decrementing a counter corresponding to a second subtable being addressed by the first entry; and

removing the second subtable in response to the decremented counter indicating that no entries address the second subtable;

receiving, at a network adapter, an incoming packet that includes a plurality of fields and forming a key from the plurality of the fields, wherein the formed key includes a plurality of subkeys; and

searching the entries stored in the subtables for one or more of the subkeys, wherein a different subtable is used to search for each of the subkeys; and wherein a next level subkey is selected and a next level subtable is searched when a pointer value is encountered in the previous level subtable.

8. The data processing system of claim 7 wherein the actions further comprise:

in response to identifying the rule corresponding to one of the entries that corresponds to the searched subkeys:

retrieving a stored key and a stored mask from the entry that identified the rule;

masking the key using the stored mask, the masking resulting in a masked key;

applying the identified rule in response to the masked key matching the stored key; and

applying a default rule in response to the masked key not matching the stored key.

9. The data processing system of claim 7 wherein, in response to the rule's key bits not being exhausted, the data processing system further comprises instructions that perform the actions of:

determining whether the subtable entry's type is currently set to a failure data type; and

in response to the subtable entry's type currently being set to a failure data type:

resetting the subtable entry to address a data entry, wherein the addressed data entry corresponds to the rule being added; and

incrementing a data entry counter that corresponds to the number of subtable entries that reference the addressed data entry.

10. The data processing system of claim 9 wherein, in response to the subtable entry's type not currently being set to a failure data type, the data processing system further comprises instructions that perform the actions of:

identifying a first subtable currently being addressed by the subtable entry;

decrementing a first counter that tracks the number of entries that reference the first subtable;

determining whether a second subtable which is an alternative version of the first subtable currently exists;

in response to the second subtable not existing:

creating an uncompressed alternate subtable that corresponds to the second subtable;

adding the rule to a plurality of entries in the uncompressed alternate subtable;

generating a reference to a compressed version of the uncompressed alternate subtable; and

storing the created reference in the subtable's entry;

re-addressing the entry to the second subtable;

incrementing a second counter that tracks the number of entries that reference the second subtable; and

determining whether to remove the first subtable.

11. The data processing system of claim 10 wherein the creation of the uncompressed alternate subtable further comprises instructions that perform the actions of:

in response to the subtable entry's type being a rule data type, creating the uncompressed alternate subtable of a predetermined size where each entry in the created uncompressed alternate subtable is the rule data type and wherein each entry in the created uncompressed alternate subtable references a common rule entry; and

in response to the subtable entry's type being a pointer type, decompressing the subtable that is referenced by the subtable entry.

12. The data processing system of claim 8 further comprising:

a table lookup unit (TLU) accessible by at least one of the processors, wherein the instructions executed by one of the processors to perform the searching further performs the actions of:

sending the key to the table lookup unit, wherein the searching is performed by the TLU.

13. A computer program product stored in a non-transitory computer readable medium, comprising functional descriptive material that, when executed by a data processing system, causes the data processing system to perform actions that include:

constructing, using a processor, one or more subtables in a first memory area accessible by the processor;

reading a plurality of rules in order of increasing rule priority, wherein each of the rules includes one or more subkeys and one or more submasks;

upon reading each of the plurality of rules, using the processor to add rule information to the subtables in a manner that stores rule information distinguishing the rule being added from every rule previously added with lower rule priorities, the adding of the rule information further comprising:

identifying a range of indices in one of the subtables corresponding to one of the rule's subkeys and one of the rule's submasks;

looping through a plurality of entries of the subtables, starting at a first entry, wherein the plurality of entries is indexed by the identified range of indices and for each of the entries, determining whether a set of a plurality of key bits corresponding to the rule have been exhausted, wherein the rule's key bits are the bits included in the rule's subkey; and

in response to the rule's key bits being exhausted:

decrementing a counter corresponding to a second subtable being addressed by the first entry; and

removing the second subtable in response to the decremented counter indicating that no entries address the second subtable;

receiving, at a network adapter, an incoming packet that includes a plurality of fields and forming a key from the plurality of the fields, wherein the formed key includes a plurality of subkeys; and

searching the entries stored in the subtables for one or more of the subkeys, wherein a different subtable is used to search for each of the subkeys; and wherein a next level subkey is selected and a next level subtable is searched when a pointer value is encountered in the previous level subtable.

14. The computer program product of claim 13 further comprising instructions that perform the actions of:

in response to identifying the rule corresponding to one of the entries that corresponds to the searched subkeys:

retrieving a stored key and a stored mask from the entry that identified the rule;

masking the key using the stored mask, the masking resulting in a masked key;

applying the identified rule in response to the masked key matching the stored key; and

applying a default rule in response to the masked key not matching the stored key.

15. The computer program product of claim 13 wherein, in response to the rule's key bits not being exhausted, the computer program product further comprises instructions that perform the actions of:

determining whether the subtable entry's type is currently set to a failure data type; and

in response to the subtable entry's type currently being set to a failure data type:

resetting the subtable entry to address a data entry, wherein the addressed data entry corresponds to the rule being added; and

incrementing a data entry counter that corresponds to the number of subtable entries that reference the addressed data entry.

16. The computer program product of claim 15 wherein, in response to the subtable entry's type not currently being set to a failure data type, the computer program product further comprises instructions that perform the actions of:

identifying a first subtable currently being addressed by the subtable entry;

decrementing a first counter that tracks the number of entries that reference the first subtable;

determining whether a second subtable which is an alternative version of the first subtable currently exists;

in response to the second subtable not existing:

creating an uncompressed alternate subtable that corresponds to the second subtable;

adding the rule to a plurality of entries in the uncompressed alternate subtable;

generating a reference to a compressed version of the uncompressed alternate subtable; and

storing the created reference in the subtable's entry;

re-addressing the entry to the second subtable;

incrementing a second counter that tracks the number of entries that reference the second subtable; and

determining whether to remove the first subtable.

17. The computer program product of claim 16 wherein the creation of the uncompressed alternate subtable further comprises instructions that perform the actions of:

in response to the subtable entry's type being a rule data type, creating the uncompressed alternate subtable of a predetermined size where each entry in the created uncompressed alternate subtable is the rule data type and wherein each entry in the created uncompressed alternate subtable references a common rule entry; and

in response to the subtable entry's type being a pointer type, decompressing the subtable that is referenced by the subtable entry.

Assignments (16)