Incremental update

• US 9,137,340 B2
• Filed: 08/02/2012
• Issued: 09/15/2015
• Est. Priority Date: 08/02/2011
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Bullis, Kenneth A., Billa, Satyanarayana Lakshmipathi
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Wang, Dongming
• Application Number:
  US13/565,775
• Publication Number:
  US 20130036102A1
• Time in Patent Office: 1,139 Days
• Field of Search: 707/694
• US Class Current: 1/1
• CPC Class Codes: G06F 11/203 using migration
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0207 with multidimensional access, e.g. row/column, matrix
• CPC Class Codes: G06F 12/04 Addressing variable-length words or parts of words
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 12/0623 for memory modules
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 13/16 for access to memory bus G06F13/28 takes precedence
• CPC Class Codes: G06F 13/1642 with request queuing
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/027 Frames
• CPC Class Codes: G11C 7/1075 for multiport memories each having random access ports and serial ports, e.g. video RAM
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 45/742 : Route cache; Operation thereof
• CPC Class Codes: H04L 45/745 : Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 : Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459
• CPC Class Codes: H04L 47/2441 : relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/39 : Credit based
• CPC Class Codes: H04L 63/0227 : Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/0263 : Rule management
• CPC Class Codes: H04L 63/06 : for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/10 : for controlling access to devices or network resources
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/02 : Protocol performance
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers
• CPC Class Codes: Y02B 70/30 : Systems integrating technologies related to power network operation and communication or information technologies for improving the carbon footprint of the management of residential or tertiary loads, i.e. smart grids as climate change mitigation technology in the buildings sector, including also the last stages of power distribution and the control, monitoring or operating management systems at local level
• CPC Class Codes: Y02D 10/00 : Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A system, apparatus, and method are provided for adding, deleting, and modifying rules in one update from the perspective of an active search process for packet classification. While a search processor searches for one or more rules that match keys generated from received packets, there is a need to add, delete, or modify rules. By adding, deleting, and modifying rules in one update from the perspective of an active search process for packet classification, performance and functionality of the active search process may be maintained, thereby preventing packet loss and preserving throughput.

Claims

1. A method comprising:

receiving an incremental update for a Rule Compiled Data Structure (RCDS), the RCDS representing a set of rules for packet classification, the RCDS utilized for packet classification by an active search process;

maintaining a housekeeping tree, an augmented representation of the RCDS including additional information of the RCDS for determining updates for the RCDS;

using the housekeeping tree to create a change list; and

atomically updating the RCDS based on the incremental update received, the change list created for atomically updating the RCDS from the perspective of the active search process utilizing the RCDS.

2. The method of claim 1, wherein atomically updating the RCDS includes:

restricting a state of the RCDS to a before state and an after state, the before state being a state of the RCDS before receiving the incremental update for the RCDS, the after state being a state of the RCDS after a series of one or more modifications to the RCDS has been completed, the series of one or more modifications having been completed based on the incremental update received, the series of one or more modifications being visible to the active search process based on performing one update to the RCDS being searched.

3. The method of claim 1, wherein updating the RCDS based on the incremental update received includes:

atomically adding a new rule to the RCDS based on the incremental update being an add rule operation;

atomically deleting a rule from the RCDS based on the incremental update being a delete rule operation; and

atomically modifying a rule in the RCDS based on the incremental update being a modify rule operation, wherein modifying the rule includes at least one of;

modifying a priority of the rule or modifying at least one field of the rule.

4. The method of claim 3, wherein modifying the priority of the rule includes:

identifying a priority fit conflict based on a change in priority of the rule being inconsistent with a current priority ordering of the rule and one or more other rules;

atomically modifying the priority of the rule based on the priority fit conflict not being identified; and

atomically modifying the priority of the rule and priority of another rule based on the conflict being identified.

5. The method of claim 3, wherein modifying at least one field of the rule includes:

determining whether one or more rules need to be added or deleted; and

adding or deleting the one or more rules, wherein adding or deleting the one or more rules is atomic.

6. The method of claim 1, further comprising:

atomically invalidating a specified rule in the RCDS based on the incremental update being a delete operation specifying the rule, wherein the active search process skips the specified rule invalidated.

7. The method of claim 1, further comprising:

representing the RCDS as a tree of the set of rules, the tree being a binary data structure including one or more nodes and one or more leaves;

representing at least one of the one or more nodes as a parent node and linking the parent node to one or more children, the one or more children being a node or a leaf, wherein linking the parent node to the one or more children includes pointing the parent node to a sibling list, the sibling list including the one or more children;

linking nodes of the tree to one or more nodes and one or more leaves of the tree; and

linking leaves of the tree to one or more buckets, each bucket representing a subset of the set of rules, each bucket including one or more bucket entries corresponding to the subset of the set of rules, bucket entries being ordered by increasing or decreasing rule priority; and

storing the set of rules in a rule table, the rules within the rule table being ordered or unordered.

8. The method of claim 1, wherein the RCDS is a performance tree,

the housekeeping tree includes field ranges of the rules and lists of the rules at each node in the performance tree, and wherein updating the performance tree atomically further includes utilizing the housekeeping tree such that a series of one or more modifications to the performance tree is made visible to the active search process based on one update to the performance tree being searched.

9. The method of claim 8, further comprising:

creating a change list specifying the one or more modifications to the performance tree.

10. The method of claim 8, wherein the incremental update is an add, delete, or modify operation, the method further comprising:

including a cover list of rules for each rule in the housekeeping tree;

creating the change list specifying one or more rules to add, delete, or modify based on the cover list; and

updating the cover list based on the change list determined.

11. The method of claim 8, further comprising:

maintaining in each leaf a pointer to a bucket from among the one or more buckets and a bucket rule counter, the bucket rule counter tracking a number of rules included in the bucket, the bucket rule counter being incremented based on a rule being added to the bucket and the bucket rule counter being decremented based on a rule being deleted from the bucket.

12. The method of claim 8, further comprising:

tracking at each node a total number of incremental updates;

determining at a given node a ratio of a number of rules represented by the given node to the total number of incremental updates tracked for the given node; and

adaptively adjusting the performance tree by recompiling a subtree based on the ratio being greater than a given threshold value.

13. The method of claim 7, wherein the incremental update includes atomically adding a new rule to the tree, the method further comprising:

splitting a leaf of the tree into one or more new nodes and adding the rule to a bucket associated with one or more leaves of the one or more new nodes.

14. The method of claim 7, wherein each bucket is a data structure and the one or more bucket entries is a rule, an index to a rule, a pointer to a rule, a pointer to a set of rules, or a pointer to another bucket.

15. The method of claim 7, wherein the incremental update includes atomically adding a new rule to the tree, the method further comprising:

identifying a destination bucket from among the one or more buckets to include the new rule; and

appending the new rule to the end of the destination bucket based on determining a space fit and priority fit of the new rule in the destination bucket, wherein appending the new rule to the end of the destination bucket takes one update.

16. The method of claim 15, wherein the space fit is based on a current number of rules in the destination bucket being less than a maximum number of rules for the destination bucket.

17. The method of claim 15, wherein the priority fit is based on the priority associated with the new rule being consistent with a priority ordering of current rules in the destination bucket.

18. The method of claim 7, wherein the incremental update includes atomically adding a new rule to the tree, the method further comprising:

identifying a destination bucket from among the one or more buckets to include the new rule;

creating a new bucket based on determining the priority associated with the new rule being inconsistent with a priority ordering of rules in the destination bucket, the active search process being unaffected by the new bucket created;

including the set of rules of the destination bucket in the new bucket;

including the new rule in the new bucket;

adjusting an order of the set of rules and the new rule based on increasing or decreasing priority order; and

updating a link of a leaf in the tree, the leaf having a link to a destination bucket from among the one or more buckets, wherein the link update includes pointing the leaf to the new bucket, wherein the link update takes one update.

19. The method of claim 7, wherein the incremental update includes atomically adding a new rule to the tree, the method further comprising:

identifying a destination bucket from among the one or more buckets to include the new rule;

creating a new bucket, the active search process being unaffected by the new bucket created;

including the new rule in the new bucket; and

updating a bucket entry of the destination bucket to point to the new bucket, wherein the bucket entry updated takes one update.

20. The method of claim 7, wherein the incremental update includes atomically adding a new rule to the tree, the method further comprising:

identifying a destination bucket from among the one or more buckets to include the new rule;

creating a subtree based on determining lack of space in the destination bucket for the new rule, lack of space in the destination bucket being determined based on a maximum number of rules set for the destination bucket, the subtree including one or more new leaves or new nodes, the active search process being unaffected by the subtree created;

adding the new rule to one or more buckets of the subtree;

adding one or more rules of the destination bucket to one or more buckets of the subtree; and

linking the subtree to the tree by updating a link of a leaf in the tree, the leaf having a link to the destination bucket from among the one or more buckets, wherein the link update includes pointing the leaf to the subtree, converting the leaf to a node, wherein the link update takes one update.

21. The method of claim 7, wherein the incremental update includes atomically adding a new leaf or a new node to a parent node in the tree, wherein the parent node in the tree is linked to a current sibling list, the current sibling list including one or more leaves or one or more nodes, the method further including:

creating a new sibling list, the active search process being unaffected by the new sibling list created;

adding the new leaf or the new node to the new sibling list, the new sibling list including the current sibling list; and

including the new sibling list in the tree by updating a link of the parent to point the parent node to the new sibling list, wherein the link update takes one update.

22. The method of claim 7, further comprising:

reserving a defragmentation portion of the memory space, the defragmentation portion of the memory space being a designated defragmentation area, the defragmentation area being a contiguous portion of the memory space reserved at a designated area of the memory space;

identifying a dead area of the RCDS, the dead area being a portion of the memory space being occupied by at least one unreferenced leaf, node, bucket, or sibling list; and

defragmenting the RCDS by recovering the dead area, the active search process being unaffected by the dead area recovered, the RCDS defragmented atomically.

23. The method of claim 22, wherein recovering the dead area includes:

relocating a used portion of memory, the used portion including one or more nodes or leaves located adjacent to the dead area identified to the designated defragmentation area; and

moving a new sibling list to a recovered memory space, the recovered memory space including the dead area identified and the used portion of memory relocated.

24. The method of claim 23, further including:

moving the used portion of memory relocated to the defragmentation area out of the defragmentation area to an end portion of the memory space reserved for the RCDS.

25. The method of claim 7, wherein the incremental update includes atomically deleting a specified rule from the tree, wherein a bucket entry of a bucket includes the specified rule, the method further comprising:

linking, with a link, the bucket to a leaf by a leaf bucket pointer;

invalidating the specified rule in the bucket entry; and

updating the link by setting the leaf bucket pointer to null if all bucket entries in the bucket are invalidated, wherein invalidating the specified rule and updating the leaf bucket pointer to null take one update, wherein the active search process skips a bucket if the leaf bucket pointer is null.

26. The method of claim 7, wherein the incremental update includes atomically deleting a specified rule from the tree, wherein a bucket entry of a bucket includes a rule pointer pointing to the specified rule, the method further comprising:

linking, with a link, the bucket to a leaf by a leaf bucket pointer;

setting the rule pointer to null; and

updating the link by setting the leaf bucket pointer to null if all rule pointers in the bucket are null, wherein setting the rule pointer to null and setting the leaf bucket pointer to null take one update, wherein the active search process skips null leaf bucket pointers and skips null rule pointers.

27. The method of claim 7, wherein the incremental update includes atomically deleting a specified rule from the tree, wherein a bucket entry of a bucket includes a rule chunk pointer pointing to a set of one or more rules including the specified rule, the method further comprising:

linking, with a link, the bucket to a leaf by a leaf bucket pointer;

invalidating the specified rule;

setting the rule chunk pointer to null if all rules in the set of one or more rules are invalidated; and

updating the link by setting the leaf bucket pointer to null if all bucket entries in the bucket are invalidated, wherein invalidating the specified rule, setting the rule chunk pointer to null, and setting the leaf bucket pointer to null take one update, wherein the active search process skips null leaf bucket pointers, null rule chunk pointers, invalidated rules.

28. The method of claim 7, wherein the incremental update includes atomically adding one or more rules based on deleting a specified rule from the tree, the method further including:

identifying a destination bucket from among the one or more buckets to include the new rule;

creating a subtree based on determining lack of space in the destination bucket for the new rule, lack of space in the destination bucket being determined based on a maximum number of rules set for the destination bucket, the subtree including one or more new leaves or new nodes, the active search process being unaffected by the subtree created;

adding the new rule to one or more buckets of the subtree;

adding one or more rules of the destination bucket to one or more buckets of the subtree; and

linking the subtree to the tree by updating a link of a leaf in the tree, the leaf having a link to the destination bucket from among the one or more buckets, wherein the link update includes pointing the leaf to the subtree, converting the leaf to a node, wherein the link update takes one update.

29. The method of claim 7, wherein the incremental update includes atomically adding one or more rules based on deleting a specified rule from the tree, the method further including:

identifying a destination bucket from among the one or more buckets to include the new rule; and

appending the new rule to the end of the destination bucket based on determining a space fit and priority fit of the new rule in the destination bucket, wherein appending the new rule to the end of the destination bucket takes one update.

30. The method of claim 1, wherein the incremental update is an add rule operation, a delete rule operation, or a modify rule operation, and further wherein updating the RCDS based on the incremental update received further includes:

atomically adding, deleting, modifying, or any combination thereof, one or more rules to/from the RCDS.

31. An apparatus comprising:

a first memory configured to store a Rule Compiled Data Structure (RCDS), the RCDS representing a set of rules for packet classification;

a second memory for maintaining a housekeeping tree, an augmented representation of the RCDS including additional information of the RCDS for determining updates for the RCDS, the housekeeping tree used to create a change list; and

a processor coupled to the first memory, the processor receiving the change list, the change list including an incremental update for the RCDS;

the processor performing an active search of the RCDS to classify received packets; and

the processor updating the RCDS atomically from the perspective of the active search being performed based on the incremental update for the RCDS.

32. The apparatus of claim 31, further comprising an interface, wherein the interface receives the change list.

33. The apparatus of claim 31, wherein the processor is a search processor.

34. The apparatus of claim 31, wherein the RCDS includes a compiled set of rules and an updated RCDS includes the compiled set of rules and one or more applied incremental updates, wherein the updated RCDS achieves a same performance as a pre-complied version of the updated RCDS.

35. The apparatus of claim 31, wherein:

the processor restricts a state of the RCDS to a before state and an after state, the before state being a state of the RCDS before receiving the incremental update for the RCDS, the after state being a state of the RCDS after a series of one or more modifications to the RCDS has been completed, the series of one or more modifications having been completed based on the incremental update received, the series of one or more modifications being visible to the active search process based on performing one update to the RCDS being searched.

36. The apparatus of claim 31, wherein:

the processor adds, atomically, a new rule to the RCDS based on the incremental update being an add rule operation;

the processor deletes, atomically, a rule from the RCDS based on the incremental update being a delete rule operation; and

the processor modifies, atomically, a rule in the RCDS based on the incremental update being a modify rule operation, wherein modifying the rule includes at least one of;

modifying a priority of the rule or modifying at least one field of the rule.

37. The apparatus of claim 36, wherein a priority fit conflict is based on a change in priority of the rule being inconsistent with a current priority ordering of the rule and one or more other rules, and:

the processor modifies, atomically, the priority of the rule based on the priority fit conflict not being identified; and

the processor modifies, atomically, the priority of the rule and priority of another rule based on the conflict being identified.

38. The apparatus of claim 36, wherein:

the processor adds or deletes the one or more rules, and wherein adding or deleting the one or more rules is atomic.

39. The apparatus of claim 31, wherein:

the processor invalidates, atomically, a specified rule in the RCDS based on the incremental update being a delete operation specifying the rule, and wherein the active search process skips the specified rule invalidated.

40. The apparatus of claim 31, wherein:

the processor represents the RCDS as a tree of the set of rules, the tree being a binary data structure including one or more nodes and one or more leaves;

the processor represents at least one of the one or more nodes as a parent node and linking the parent node to one or more children, the one or more children being a node or a leaf, wherein linking the parent node to the one or more children includes pointing the parent node to a sibling list, the sibling list including the one or more children;

the processor links nodes of the tree to one or more nodes and one or more leaves of the tree; and

the processor links leaves of the tree to one or more buckets, each bucket representing a subset of the set of rules, each bucket including one or more bucket entries corresponding to the subset of the set of rules, bucket entries being ordered by increasing or decreasing rule priority; and

the processor stores the set of rules in a rule table, the rules within the rule table being ordered or unordered.

41. The apparatus of claim 40, wherein the incremental update includes adding a new rule to the tree, atomically, and wherein:

the processor splits a leaf of the tree into one or more new nodes and adds the rule to a bucket associated with one or more leaves of the one or more new nodes, atomically.

42. The apparatus of claim 40, wherein each bucket is a data structure and the one or more bucket entries is a rule, an index to a rule, a pointer to a rule, a pointer to a set of rules, or a pointer to another bucket.

43. The apparatus of claim 40, wherein the incremental update includes adding a new rule to the tree, atomically, wherein:

the processor appends the new rule to the end of a destination bucket based on determining a space fit and priority fit of the new rule in the destination bucket, wherein appending the new rule to the end of the destination bucket takes one update.

44. The apparatus of claim 43, wherein the space fit is based on a current number of rules in the destination bucket being less than a maximum number of rules for the destination bucket.

45. The apparatus of claim 43, wherein the priority fit is based on the priority associated with the new rule being consistent with a priority ordering of current rules in the destination bucket.

46. The apparatus of claim 40, wherein the incremental update includes adding a new rule to the tree, atomically, and wherein:

the processor creates a new bucket based on determining the priority associated with the new rule being inconsistent with a priority ordering of rules in a destination bucket, the active search process being unaffected by the new bucket created;

the processor includes the set of rules of the destination bucket in the new bucket;

the processor includes the new rule in the new bucket;

the processor adjusts an order of the set of rules and the new rule based on increasing or decreasing priority order; and

the processor updates a link of a leaf in the tree, the leaf having a link to a destination bucket from among the one or more buckets, wherein the link update includes pointing the leaf to the new bucket, wherein the link update takes one update.

47. The apparatus of claim 40, wherein the incremental update includes adding a new rule to the tree, atomically, and wherein:

the processor creates a new bucket, the active search process being unaffected by the new bucket created;

the processor includes the new rule in the new bucket; and

the processor updates a bucket entry of a destination bucket to point to the new bucket, wherein the bucket entry updated takes one update.

48. The apparatus of claim 40, wherein the incremental update includes adding a new rule to the tree, atomically, and:

a subtree based on determining lack of space in the destination bucket for the new rule, lack of space in a destination bucket being determined based on a maximum number of rules set for the destination bucket, the subtree including one or more new leaves or new nodes, the active search process being unaffected by the subtree created;

the processor adds the new rule to one or more buckets of the subtree;

the processor adds one or more rules of the destination bucket to one or more buckets of the subtree; and

the processor links the subtree to the tree by updating a link of a leaf in the tree, the leaf having a link to the destination bucket from among the one or more buckets, wherein the link update includes pointing the leaf to the subtree, converting the leaf to a node, wherein the link update takes one update.

49. The apparatus of claim 40, wherein the incremental update includes adding a new leaf or a new node to a parent node in the tree, atomically, wherein the parent node in the tree is linked to a current sibling list, the current sibling list including one or more leaves or one or more nodes, and wherein:

the processor creates a new sibling list, the active search process being unaffected by the new sibling list created;

the processor adds the new leaf or the new node to the new sibling list, the new sibling list including the current sibling list; and

the processor creates the new sibling list in the tree by updating a link of the parent to point the parent node to the new sibling list, wherein the link update takes one update.

50. The apparatus of claim 40, wherein:

the processor reserves a defragmentation portion of the memory space, the defragmentation portion of the memory space being a designated defragmentation area, the defragmentation area being a contiguous portion of the memory space reserved at a designated area of the memory space; and

the processor defragments the RCDS by recovering the dead area, the active search process being unaffected by the dead area recovered, the RCDS defragmented atomically.

51. The apparatus of claim 50, wherein:

the processor relocates a used portion of memory, the used portion including one or more nodes or leaves located adjacent to the dead area identified to the designated defragmentation area; and

the processor moves a new sibling list to a recovered memory space, the recovered memory space including the dead area identified and the used portion of memory relocated.

52. The apparatus of claim 51, wherein:

the processor moves the used portion of memory relocated to the defragmentation area out of the defragmentation area to an end portion of the memory space reserved for the RCDS.

53. The apparatus of claim 40, wherein the incremental update includes deleting a specified rule from the tree, atomically, wherein a bucket entry of a bucket includes the specified rule, and wherein:

the processor links, with a link, the bucket to a leaf by a leaf bucket pointer;

the processor invalidates the specified rule in the bucket entry; and

the processor updates the link by setting the leaf bucket pointer to null if all bucket entries in the bucket are invalidated, wherein invalidating the specified rule and updating the leaf bucket pointer to null take one update, wherein the active search process skips a bucket if the leaf bucket pointer is null.

54. The apparatus of claim 40, wherein the incremental update includes deleting a specified rule from the tree, atomically, wherein a bucket entry of a bucket includes a rule pointer pointing to the specified rule, and wherein:

the processor links, with a link, the bucket to a leaf by a leaf bucket pointer;

the processor sets the rule pointer to null; and

the processor updates the link by setting the leaf bucket pointer to null if all rule pointers in the bucket are null, wherein setting the rule pointer to null and setting the leaf bucket pointer to null take one update, wherein the active search process skips null leaf bucket pointers and skips null rule pointers.

55. The apparatus of claim 40, wherein the incremental update includes deleting a specified rule from the tree, atomically, wherein a bucket entry of a bucket includes a rule chunk pointer pointing to a set of one or more rules including the specified rule, and wherein:

the processor links, with a link, the bucket to a leaf by a leaf bucket pointer;

the processor invalidates the specified rule;

the processor sets the rule chunk pointer to null if all rules in the set of one or more rules are invalidated; and

the processor updates the link by setting the leaf bucket pointer to null if all bucket entries in the bucket are invalidated, wherein invalidating the specified rule, setting the rule chunk pointer to null, and setting the leaf bucket pointer to null take one update, wherein the active search process skips null leaf bucket pointers, null rule chunk pointers, invalidated rules.

56. The apparatus of claim 40, wherein the incremental update includes adding one or more rules, atomically, based on deleting a specified rule from the tree, and wherein:

a subtree based on determining lack of space in the destination bucket for the new rule, lack of space in a destination bucket being determined based on a maximum number of rules set for the destination bucket, the subtree including one or more new leaves or new nodes, the active search process being unaffected by the subtree created;

the processor adds the new rule to one or more buckets of the subtree;

the processor adds one or more rules of the destination bucket to one or more buckets of the subtree; and

the processor links the subtree to the tree by updating a link of a leaf in the tree, the leaf having a link to the destination bucket from among the one or more buckets, wherein the link update includes pointing the leaf to the subtree, converting the leaf to a node, wherein the link update takes one update.

57. The apparatus of claim 40, wherein the incremental update includes adding one or more rules, atomically, based on deleting a specified rule from the tree, and wherein:

the processor appends the new rule to the end of a destination bucket based on determining a space fit and priority fit of the new rule in the destination bucket, wherein appending the new rule to the end of the destination bucket takes one update.

58. An apparatus comprising:

a memory;

a processor coupled to the memory, the processor including an incremental update module;

the incremental update module receiving an incremental update; and

the incremental update module creating a change list in the memory, the change list created to update a Rule Compiled Data Structure (RCDS), atomically, from the perspective of an active search process utilizing the RCDS, wherein the processor maintains a housekeeping tree, an augmented representation of the RCDS including additional information of the RCDS to enable the incremental update module to determine updates for the RCDS, the incremental update module using the housekeeping tree for creating the change list, the processor atomically updating the RCDS based on the incremental update received.

59. The apparatus of claim 58, further comprising:

an interface, wherein the incremental update module communicates the change list over the interface;

a compiler module coupled to the memory, the compiler module receiving a set of rules, compiling the set of rules into a binary tree, storing the binary tree in the memory, and communicating the binary tree over the interface, wherein the binary tree represents at least one of the one or more nodes as a parent node and links the parent node to one or more children, the one or more children being a node or a leaf, wherein linking the parent node to the one or more children includes pointing the parent node to a sibling list, the sibling list including the one or more children, and further wherein the binary tree links nodes of the tree to one or more nodes and one or more leaves of the tree and links leaves of the tree to one or more buckets.

60. The apparatus of claim 58, wherein the RCDS is a performance tree,

the housekeeping tree includes field ranges of the rules and lists of the rules at each node in the performance tree, and wherein updating the performance tree atomically further includes utilizing the housekeeping tree such that a series of one or more modifications to the performance tree is made visible to the active search process based on one update to the performance tree being searched.

61. The apparatus of claim 59, wherein:

the processor creates the change list specifying the one or more modifications to the performance tree.

62. The apparatus of claim 59, wherein the incremental update is an add, delete, or modify operation, and further wherein the processor:

includes a cover list of rules for each rule in the housekeeping tree;

creates the change list specifying one or more rules to add, delete, or modify based on the cover list; and

updates the cover list based on the change list determined.

63. The apparatus of claim 59, wherein the processor:

maintains in each leaf a pointer to a bucket from among the one or more buckets and a bucket rule counter, the bucket rule counter tracking a number of rules included in the bucket, the bucket rule counter being incremented based on a rule being added to the bucket and the bucket rule counter being decremented based on a rule being deleted from the bucket.

64. The apparatus of claim 59, wherein:

the processor tracks at each node a total number of incremental updates;

the processor determines at a given node a ratio of a number of rules represented by the given node to the total number of incremental updates tracked for the given node; and

the processor adjusts, adaptively, the performance tree by recompiling a subtree based on the ratio being greater than a given threshold value.

65. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when executed by a processor, causes the processor to:

receive an incremental update for a Rule Compiled Data Structure (RCDS), the RCDS representing a set of rules for packet classification, the RCDS utilized for packet classification by an active search process;

maintain a housekeeping tree, an augmented representation of the RCDS;

use the housekeeping tree to create a change list; and

atomically update the RCDS based on the incremental update received, the change list created for atomically updating the RCDS from the perspective of the active search process utilizing the RCDS.