Software management tree implementation for a network processor

• US 7,107,265 B1
• Filed: 04/06/2000
• Issued: 09/12/2006
• Est. Priority Date: 04/06/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jeffries, Clark Debs, Calvignac, Jean Louis, Heddes, Marco C., Patel, Piyush Chunilal, Rinaldi, Mark Anthony
• Primary Examiner(s): Kindred, Alford W.
• Application Number:
  US09/545,100
• Time in Patent Office: 2,350 Days
• Field of Search: 707 1- 4, 707 6- 7, 707/100, 707/205, 709213-216
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Novel data structures, methods and apparatus for a Software Managed Tree (SMT) which provides a mechanism to create tree structures that follow a search mechanism defined by a control point processor. The search mechanism does not require storage on the previous pointer and uses only a forward pointer along with a next bit or group of bits to test thereby reducing storage space for nodes. The search mechanism processes multiple filter rules for an application without requiring multiple searches and also allows various filter rules to be chained. Two patterns of the same length are stored in each leaf to define a range compare. A compare at the end operation is either a compare under range or a compare under mask. In a compare under range, the input key is checked to determine if it is in the range defined by the two patterns. In a compare under mask, the bits in the input key are compared with the bits in a first leaf pattern under a mask specified in a second leaf pattern.

Claims

1. A method for performing a pattern range comparison for a variable length search key in a software managed tree by a computer processing device, comprising the acts of:

reading an input key as a search string;

using the N most significant bits of the search key as an index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf;

determining if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree;

reading the next branch contents if the pointer does not point to the leaf of the corresponding search tree;

reading the leaf contents when the leaf of a corresponding search tree is reached and comparing a pair of patterns in the leaf with the search key to determine if the range defined by the pair of leaf patterns includes the search key; and

returning the contents of the leaf found to the requesting application if the leaf patterns include the search key.

2. The method for performing the pattern range comparison of claim 1 further comprising hashing the input key using a programmable hash function to form a search key.

3. The method for performing the pattern range comparison of claim 1 wherein the table representing a plurality of root nodes of search trees contains 2N entries.

4. The method for performing the pattern range comparison of claim 1 wherein the computer processing device is a network processor.

5. The method for performing the pattern range comparison of claim 1 wherein the contents of the next branch of the corresponding search tee points to another next branch.

6. The method for performing the pattern range comparison of claim 1 wherein the contents of the next branch points to the leaf of the corresponding search tree.

7. The method for performing the pattern range comparison of claim 1 further comprising returning a no success indication if the leaf patterns do not include the search key and do not contain a pointer to another leaf.

8. The method for performing the pattern range comparison of claim 1 further comprising returning a no success indication if the index into the table is to an empty entry.

9. The method for performing the pattern range comparison of claim 1 further comprising appending the contents of a color register to the search key to provide a final search key.

10. The method for performing the pattern range comparison of claim 1 further comprising appending a string of zeros to the search key to provide a final search key.

11. The method for performing the pattern range comparison of claim 1 wherein the act of comparing a pair of patterns comprises compare under range operation in which the bits in the search key are treated as an integer that is checked to determine if it is in a range defined by the pair of patterns.

12. The method of claim 1 wherein the act of comparing a pair of patterns comprises a compare under mask operation in which the bits in the search key are compared with the bits in a first leaf pattern under a mask specified in a second leaf pattern.

13. The method for performing the pattern range comparison of claim 1 further comprising the acts of:

if the leaf contains a chain pointer to another leaf, reading a pair of patterns stored in another leaf and comparing the patterns with the search key; and

returning an indication of no success if the patterns stored do not include the search key and do not contain a pointer to a next leaf in the chain.

14. The method for performing the pattern range comparison of claim 1 further comprising the acts of:

if the leaf contains a chain pointer to another leaf, reading a pair of patterns stored in another leaf and comparing the patterns with the search key; and

returning an indication of success if the patterns stored include the search key.

15. A computer readable medium containing a plurality of data structures for performing a pattern range comparison for a variable length search key in a software managed tree, comprising:

a pattern or key that is to be searched;

a direct table that stores a first address location for a search tree;

a plurality of pattern search control blocks that each represent a branch in the search tree;

a compare table that specifies at least one range compare associated with each entry;

a programmable color key register to enable sharing a single table data structure among a plurality of independent search trees; and

a plurality of leaves wherein each leaf stores a pair of patterns to compare with the search key.

16. The computer readable medium containing a plurality of data structures for performing the pattern range comparison of claim 15 wherein comprising a lookup definition table that manages a tree search memory.

17. The computer readable medium containing a plurality of data structures for performing the pattern range comparison of claim 15 wherein the lookup definition table comprises entries that define a physical memory that the tee resides in, a size of the key and leaf, and a type of search to be performed.

18. The computer readable medium containing a plurality of data structures for performing the pattern range comparison of claim 15 wherein the lookup definition table is implemented in a plurality of memories.

19. The computer readable medium containing a plurality of data structures for performing the pattern range comparison of claim 15 wherein a format for a direct table entry includes at least one of:

a search control block;

a next pattern address that point to a next pattern search control block;

a leaf control block address that points to a leaf or result;

a next bit or bits to test; and

a direct leaf.

20. The computer readable medium containing a plurality of data structures for performing the pattern range comparison of claim 15 wherein a format for a pattern search control block includes at least one of:

a search control block;

a next pattern address that point to a next pattern search control block;

a leaf control block address that points to a leaf or result, and a next bit or bits to test.

21. The computer readable medium containing a plurality of data structures for performing the pattern range comparison of claim 15 wherein the compare table comprises entries that define at least one range compare, each range compare being defined by an offset parameter which is a position of the first bit of the field and a length parameter which is the length of the field in bits.

22. The computer readable medium containing a plurality of data structures for performing the pattern range comparison of claim 15 wherein a leaf data structure includes at least one of a leaf chaining pointer;

a prefix length;

a pair of patterns to be compared to the search key; and

variable user data.

23. The computer readable medium containing a plurality of data structures for performing the pattern range comparison of claim 15 wherein the direct leaf is stored directly in a direct table entry and includes a search control block and a pair of patterns to be compared to a search key.

24. The computer readable medium containing a plurality of data structures for performing the pattern range comparison of claim 15 wherein a pattern search control block is inserted in the search tree at a position where the leaf patterns differ.

25. The computer readable medium containing a plurality of data structures for performing the pattern range comparison of claim 15 wherein a pattern search control block has a shape defined by a width of one and a height of one and is stored in a memory that has a line length of at least 36 bits.

26. An apparatus fabricated on a semiconductor substrate for performing a pattern range comparison for a variable length search key in a software managed tree, comprising:

an embedded processor complex including a plurality of protocol processors and an internal control point processor that provide frame processing;

a plurality of hardware accelerator co-processors accessible to each protocol processor and providing high speed pattern searching, data manipulation, and frame parsing;

a plurality of programmable memory devices that store a plurality of data structures that represent at least one search tree, wherein the data structures include a direct table, a pattern search control block, a compare table and a leaf including a pair of patterns to compare with the search key;

a programmable color key register to enable sharing a single table data structure among a plurality of independent search trees; and

an control memory arbiter that controls the access of each protocol processor to the plurality of memory devices.

27. The apparatus fabricated on a semiconductor substrate for performing the pattern range comparison of claim 26 further comprising a tree search engine that operates in parallel with protocol processor execution to perform tree search instructions including memory reads and writes and memory range checking.

28. The apparatus fabricated on a semiconductor substrate for performing the pattern range comparison of claim 26 wherein the plurality of memory devices further comprises at least one of internal static random access memory, external static random access memory, and external dynamic random access memory.

29. The apparatus fabricated on a semiconductor substrate for performing the pattern range comparison of claim 26 wherein the control memory arbiter manages control memory operations by allocating memory cycles between the plurality of protocol processors and the plurality of memory devices.

30. The apparatus fabricated on a semiconductor substrate for performing the pattern range comparison of claim 26 wherein each protocol processor comprises a primary data buffer, a scratch pad data buffer and control registers for data store operations.

31. The apparatus fabricated on a semiconductor substrate for performing the pattern range comparison of claim 26 further comprising a hash box component that performs a geometric hash function on the search key.

32. The apparatus fabricated on a semiconductor substrate for performing the pattern range comparison of claim 26 further comprising a programmable search key register and a programmable hashed key register.

33. The apparatus fabricated on a semiconductor substrate for performing the pattern range comparison of claim 26, wherein the contents of the color register, if enabled, are appended to the hash output to produce a final hashed key.

34. The apparatus fabricated on a semiconductor substrate for performing the pattern range comparison of claim 26, wherein if the color register is not enabled, appending an equivalent number of zeros to the hash output to produce a final hashed key.

35. A computer readable medium containing a computer program product for performing a pattern range comparison for a variable length search key in a software managed tree, comprising:

program instructions that read an input key as a search string;

program instructions that use the N most significant bits of the search key as an index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf;

program instructions that determine if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree;

program instructions that read the next branch contents if the pointer does not point to the leaf of the corresponding search tree;

program instructions that read the leaf contents when the leaf of a corresponding search tree is reached and compare a pair of patterns in the leaf with the search key to determine if the range defined by the pair of leaf patterns includes the search key; and

program instructions that return the contents of the leaf found to the requesting application if the leaf patterns include the search key.

36. The computer program product for performing the pattern range comparison of claim 35 further comprising program instructions that hash the input key using a programmable hash function to form a search key.

37. The computer program product for performing the pattern range comparison of claim 35 wherein the table representing a plurality of root nodes of search trees contains 2N entries.

38. The computer program product for performing the pattern range comparison of claim 35 wherein the computer processing device is a network processor.

39. The computer program product for performing the pattern range comparison of claim 36 wherein the contents of the next branch of the corresponding search tree points to another next branch.

40. The computer program product for performing the pattern range comparison of claim 35 wherein the contents of the next branch points to the leaf of the corresponding search tree.

41. The computer program product for performing the pattern range comparison of claim 35 further comprising program instructions that return a no success indication if the leaf patterns do not include the search key and do not contain a pointer to another leaf.

42. The computer program product for performing the pattern range comparison of claim 35 further comprising program instructions that return a no success indication if the index into the table is to an empty entry.

43. The computer program product for performing the pattern range comparison of claim 35 further comprising program instructions that append the contents of a color register to the search key to provide a final search key.

44. The computer program product for performing the pattern range comparison of claim 35 further comprising program instructions that append a string of zeros to the search key to provide a final search key.

45. The computer program product for performing the pattern range comparison of claim 35 further comprising program instructions that perform a compare under range operations in which the bits in the search key are treated as an integer that is checked to determine if it is in a range defined by the pair of patterns.

46. The computer program product for performing the pattern range comparison of claim 35 further comprising program instructions that perform a compare under mask operation in which the bits in the search key are compared with the bits in a first leaf position under a mask specified in a second leaf pattern.

47. The computer program product for performing the pattern range comparison of claim 35 further comprising:

program instructions that read a pair of patterns stored in another leaf and compare the patterns with the search key if the leaf contains a chain pointer to another leaf; and

program instructions that return an indication of no success if the patterns stored do not include the search key and do not contain a pointer to a next leaf in the chain.

48. The computer program product for performing the pattern range comparison of claim 35 further comprising:

program instructions that read a pair of patterns stored in another leaf and compare the patterns with the search key if the leaf contains a chain pointer to another leaf; and

program instructions that return an indication of success if the patterns stored include the search key.