Batch incremental update

• US 10,083,200 B2
• Filed: 03/14/2013
• Issued: 09/25/2018
• Est. Priority Date: 03/14/2013
• 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): Vital, Pierre M
• Assistant Examiner(s): Ho, Andrew N
• Application Number:
  US13/831,415
• Publication Number:
  US 20140279850A1
• Time in Patent Office: 2,021 Days
• Field of Search: 707609
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/235 Update request formulation

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 organizing a plurality incremental updates for adding, deleting, or modifying rules into a batch update, several operations for incorporating the incremental updates may be made more efficient by minimizing a number of updates required.

Claims

1. A method comprising:

receiving a batch update including a plurality of incremental updates for a Rule Compiled Data Structure (RCDS) representing a decision tree for a set of rules used for packet classification, the RCDS being utilized for packet classification by an active search process;

updating the set of rules and one or more rule lists based on the batch update received, each of the one or more rule lists being a subset of the set of rules associated with a category subtree of a housekeeping tree, the housekeeping tree being an augmented representation of the RCDS separate from the RCDS;

updating the housekeeping tree associated with each category subtree associated with the one or more rule lists updated and building a changeset specifying one or more modifications to the RCDS based on the housekeeping tree updated;

updating a shadow image based on the changeset built and determining an update status based on one or more updates to the shadow image and the housekeeping tree, the shadow image reflecting current resources being held by the RCDS and changes to the current resources being held based on the one or more modifications to the RCDS specified and the update status indicating success or failure for the one or more updates to the housekeeping tree and the shadow image;

determining a commit or partial rollback action based on the update status, the commit action being determined given the update status indicates success and the partial rollback action being determined given the update status indicates failure; and

in an event the commit action is determined, applying the changeset built to the RCDS in a manner enabling the RCDS to atomically incorporate the plurality of incremental updates from the perspective of the active search process utilizing the RCDS.

2. The method of claim 1 wherein a number of operations triggered by the plurality of incremental updates included in the batch update received is less than another number of operations triggered by the plurality of incremental updates received on an incremental basis.

3. The method of claim 1 wherein applying the changeset built to the RCDS includes issuing a number of instructions to a device and the number of instructions and a size of the changeset built are reduced in comparison to a cumulative number of instructions and a cumulative changeset size, the cumulative number of instructions and the cumulative changeset size corresponding to the plurality of incremental updates being received on an incremental basis.

4. The method of claim 1 further comprising:

determining one or more rule priority changes based on the batch update received; and

including the one or more rule priority changes determined in the changeset built.

5. The method of claim 1 wherein applying the changeset built to the RCDS is dependent on the commit action being determined.

6. The method of claim 1 wherein the partial rollback action includes:

restoring the set of rules and the one or more rule lists by backing out updates made based on the batch update received;

restoring the housekeeping tree and the shadow image by rolling back the changeset;

preventing the applying of the changeset built to the RCDS; and

deleting the changeset built.

7. The method of claim 6 wherein restoring the housekeeping tree by rolling back the changeset includes:

restoring at least one bucket directly in a bucket database;

restoring leaf nodes linked to the at least one bucket being restored; and

restoring nodes linked to the leaf nodes being restored.

8. The method of claim 6 wherein restoring the shadow image by rolling back the changeset includes freeing memory allocated based on updating the shadow image.

9. The method of claim 1 wherein the decision tree includes a plurality of nodes, each node representing one or more rules of the set of rules and having a leaf node type or a non-leaf node type, each node having the leaf node type being a leaf node linked to a bucket representing rules of the leaf node, and the one or more modifications specified by the changeset include changes to one or more of the plurality of nodes, each change including a location, old value, and new value associated with the change.

10. The method of claim 1 wherein the batch update received includes an add, delete, or modify rule operation, or a combination thereof.

11. The method of claim 1 wherein applying the changeset built to the RCDS in the manner enabling the RCDS to atomically incorporate the plurality of incremental updates includes:

enabling a given search of the active search process to view the RCDS in either a before state or an after state, the before state being a state of the RCDS before receiving the batch update for the RCDS, the after state being another state of the RCDS having the series of one or more updates based on the changeset incorporated in the RCDS, the after state being made visible to the given search based on a single update to the RCDS being searched.

12. The method of claim 1 wherein updating the housekeeping tree associated with each category subtree associated with the one or more rule lists updated includes:

adding a new rule based on the batch incremental update including an add rule operation;

deleting an existing rule based on the batch incremental update including a delete rule operation; and

modifying the existing rule based on the batch incremental update including a modify rule operation, wherein modifying the existing rule includes at least one of;

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

13. The method of claim 12, wherein modifying the priority of the existing rule includes:

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

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

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

14. The method of claim 12, wherein modifying at least one field of the existing rule includes:

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

adding or deleting the one or more rules.

15. The method of claim 1, wherein the decision tree includes a plurality of nodes, each node representing one or more rules of the set of rules and the batch incremental update received includes add, delete, or modify operations, the method of claim 1 further comprising:

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

building the changeset specifying one or more rules to add, delete, or modify based on the batch incremental update received and the cover list; and

updating the cover list based on the changeset determined.

16. An apparatus comprising:

a memory;

a processor coupled to the memory, the processor configured to;

receive a batch update including a plurality of incremental updates for a Rule Compiled Data Structure (RCDS) representing a decision tree for a set of rules used for packet classification, the RCDS being utilized for packet classification by an active search process;

update the set of rules and one or more rule lists based on the batch update received, each of the one or more rule lists being a subset of the set of rules associated with a category subtree of a housekeeping tree, the housekeeping tree being an augmented representation of the RCDS separate from the RCDS;

update the housekeeping tree associated with each category subtree associated with the one or more rule lists updated and building a changeset specifying one or more modifications to the RCDS based on the housekeeping tree updated;

update a shadow image based on the changeset built and determine an update status based on one or more updates to the shadow image and the housekeeping tree, the shadow image reflecting current resources being held by the RCDS and changes to the current resources being held based on the one or more modifications to the RCDS specified, the update status indicating success or failure for the one or more updates to the housekeeping tree and the shadow image;

determine a commit or partial rollback action based on the update status, the commit action being determined given the update status indicates success and the partial rollback action being determined given the update status indicates failure; and

in an event the commit action is determined, apply the changeset built to the RCDS in a manner enabling the RCDS to atomically incorporate the plurality of incremental updates from the perspective of the active search process utilizing the RCDS.

17. The apparatus of claim 16 wherein the processor is further configured to perform a number of operations triggered by the plurality of incremental updates included in the batch update received that is less than another number of operations triggered by the plurality of incremental updates received on an incremental basis.

18. The apparatus of claim 16 wherein to apply the changeset built to the RCDS the processor is further configured to issue a number of instructions to a device and the number of instructions and a size of the changeset built are reduced in comparison to a cumulative number of instructions and a cumulative changeset size, the cumulative number of instructions and the cumulative changeset size corresponding to the plurality of incremental updates being received on an incremental basis.

19. The apparatus of claim 16 wherein the processor is further configured to:

determine one or more rule priority changes based on the batch update received; and

include the one or more rule priority changes determined in the changeset built.

20. The apparatus of claim 16 wherein whether or not to apply the changeset built to the RCDS is dependent on the commit action being determined.

21. The apparatus of claim 16 wherein to perform the partial rollback action the processor is further configured to:

restore the set of rules and the one or more rule lists by backing out updates made based on the batch update received;

restore the housekeeping tree and the shadow image by rolling back the changeset;

prevent the applying of the changeset built to the RCDS; and

delete the changeset built.

22. The apparatus of claim 21 wherein to restore the housekeeping tree by rolling back the changeset the processor is further configured to:

restore at least one bucket directly in a bucket database;

restore leaf nodes linked to the at least one bucket being restored; and

restore nodes linked to the leaf nodes being restored.

23. The apparatus of claim 21 wherein to restore the shadow image by rolling back the changeset the processor is further configured to free memory allocated based on updating the shadow image.

24. The apparatus of claim 16 wherein the decision tree includes a plurality of nodes, each node representing one or more rules of the set of rules and having a leaf node type or a non-leaf node type, each node having the leaf node type being a leaf node linked to a bucket representing rules of the leaf node, and the one or more modifications specified by the changeset include changes to one or more of the plurality of nodes, each change including a location, old value, and new value associated with the change.

25. The apparatus of claim 16 wherein the batch update received includes an add, delete, or modify rule operation, or a combination thereof.

26. The apparatus of claim 16 wherein to apply the changeset built to the RCDS in the manner enabling the RCDS to atomically incorporate the plurality of incremental updates the processor is further configured to:

enable a given search of the active search process to view the RCDS in either a before state or an after state, the before state being a state of the RCDS before receiving the batch update for the RCDS, the after state being another state of the RCDS having the series of one or more updates based on the changeset incorporated in the RCDS, the after state being made visible to the given search based on a single update to the RCDS being searched.

27. The apparatus of claim 16 wherein to update the housekeeping tree associated with each category subtree associated with the one or more rule lists updated the processor is further configured to:

add a new rule based on the batch incremental update including an add rule operation;

delete an existing rule based on the batch incremental update including a delete rule operation; and

modify the existing rule based on the batch incremental update including a modify rule operation, wherein modifying the existing rule includes at least one of;

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

28. The apparatus of claim 27, wherein to modify the priority of the existing rule the processor is further configured to:

identify a priority fit conflict, the priority fit conflict being a change in priority of the existing rule that is inconsistent with a current priority ordering of the existing rule and one or more other rules;

modify the priority of the existing rule based on the priority fit conflict not being identified; and

modify the priority of the existing rule and priority of another rule based on the conflict being identified.

29. The apparatus of claim 27, wherein to modify at least one field of the existing rule the processor is further configured to:

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

add or delete the one or more rules.

30. The apparatus of claim 16, wherein the decision tree includes a plurality of nodes, each node representing one or more rules of the set of rules and the batch incremental update received includes add, delete, or modify operations, and the processor is further configured to:

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

build the changeset specifying one or more rules to add, delete, or modify based on the batch incremental update received and the cover list; and

update the cover list based on the changeset determined.

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

receive a batch update including a plurality of incremental updates for a Rule Compiled Data Structure (RCDS) representing a decision tree for a set of rules used for packet classification, the RCDS being utilized for packet classification by an active search process;

update the set of rules and one or more rule lists based on the batch update received, each of the one or more rule lists being a subset of the set of rules associated with a category subtree of a housekeeping tree, the housekeeping tree being an augmented representation of the RCDS separate from the RCDS;

update the housekeeping tree associated with each category subtree associated with the one or more rule lists updated and building a changeset specifying one or more modifications to the RCDS based on the housekeeping tree updated;

update a shadow image based on the changeset built and determine an update status based on one or more updates to the shadow image and the housekeeping tree, the shadow image reflects current resources being held by the RCDS and changes to the current resources being held based on the one or more modifications to the RCDS specified, the update status indicating success or failure for the one or more updates to the housekeeping tree and the shadow image;

determine a commit or partial rollback action based on the update status, the commit action being determined given the update status indicates success and the partial rollback action being determined given the update status indicates failure; and

in an event the commit action is determined, apply the changeset built to the RCDS in a manner enabling the RCDS to atomically incorporate the plurality of incremental updates from the perspective of the active search process utilizing the RCDS.

32. The non-transitory computer-readable medium of claim 31 wherein the sequence of instructions further causes the processor to perform a number of operations triggered by the plurality of incremental updates included in the batch update received that is less than another number of operations triggered by the plurality of incremental updates received on an incremental basis.

33. The non-transitory computer-readable medium of claim 31 wherein to apply the changeset built to the RCDS the sequence of instructions further causes the processor to issue a number of instructions to a device and the number of instructions and a size of the changeset built are reduced in comparison to a cumulative number of instructions and a cumulative changeset size, the cumulative number of instructions and the cumulative changeset size corresponding to the plurality of incremental updates being received on an incremental basis.

34. The non-transitory computer-readable medium of claim 31 wherein the sequence of instructions further causes the processor to:

determine one or more rule priority changes based on the batch update received; and

include the one or more rule priority changes determined in the changeset built.

35. The non-transitory computer-readable medium of claim 31 wherein whether or not to apply the changeset built to the RCDS is dependent on the commit action being determined.

36. The non-transitory computer-readable medium of claim 31 wherein to perform the partial rollback action the sequence of instructions further causes the processor to:

restore the set of rules and the one or more rule lists by backing out updates made based on the batch update received;

restore the housekeeping tree and the shadow image by rolling back the changeset;

prevent the applying of the changeset built to the RCDS; and

delete the changeset built.

37. The non-transitory computer-readable medium of claim 36 wherein to restore the housekeeping tree by rolling back the changeset the sequence of instructions further causes the processor to:

restore at least one bucket directly in a bucket database;

restore leaf nodes linked to the at least one bucket being restored; and

restore nodes linked to the leaf nodes being restored.

38. The non-transitory computer-readable medium of claim 36 wherein to restore the shadow image by rolling back the changeset the sequence of instructions further causes the processor to free memory allocated based on updating the shadow image.

39. The non-transitory computer-readable medium of claim 31 wherein the decision tree includes a plurality of nodes, each node representing one or more rules of the set of rules and having a leaf node type or a non-leaf node type, each node having the leaf node type being a leaf node linked to a bucket representing rules of the leaf node, and the one or more modifications specified by the changeset include changes to one or more of the plurality of nodes, each change including a location, old value, and new value associated with the change.

40. The non-transitory computer-readable medium of claim 31 wherein the batch update received includes an add, delete, or modify rule operation, or a combination thereof.

41. The non-transitory computer-readable medium of claim 31 wherein to apply the changeset built to the RCDS in the manner enabling the RCDS to atomically incorporate the plurality of incremental updates the sequence of instructions further causes the processor to:

enable a given search of the active search process to view the RCDS in either a before state or an after state, the before state being a state of the RCDS before receiving the batch update for the RCDS, the after state being another state of the RCDS having the series of one or more updates based on the changeset incorporated in the RCDS, the after state being made visible to the given search based on a single update to the RCDS being searched.

42. The non-transitory computer-readable medium of claim 31 wherein to update the housekeeping tree associated with each category subtree associated with the one or more rule lists updated the sequence of instructions further causes the processor to:

add a new rule based on the batch incremental update including an add rule operation;

delete an existing rule based on the batch incremental update including a delete rule operation; and

modify the existing rule based on the batch incremental update including a modify rule operation, wherein modifying the existing rule includes at least one of;

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

43. The non-transitory computer-readable medium of claim 42, wherein to modify the priority of the existing rule the sequence of instructions further causes the processor to:

identify a priority fit conflict, the priority fit conflict being a change in priority of the existing rule that is inconsistent with a current priority ordering of the existing rule and one or more other rules;

modify the priority of the existing rule based on the priority fit conflict not being identified; and

modify the priority of the existing rule and priority of another rule based on the conflict being identified.

44. The non-transitory computer-readable medium of claim 42, wherein to modify at least one field of the existing rule the sequence of instructions further causes the processor to:

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

add or delete the one or more rules.

45. The non-transitory computer-readable medium of claim 31, wherein the decision tree includes a plurality of nodes, each node representing one or more rules of the set of rules and the batch incremental update received includes add, delete, or modify operations, and the sequence of instructions further causes the processor to:

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

build the changeset specifying one or more rules to add, delete, or modify based on the batch incremental update received and the cover list; and

update the cover list based on the changeset determined.