Methods and apparatus for updating data structures during in-service upgrade of software in network processor

1. A method of managing data structures associated with code executable on a packet processor, comprising the steps of:

identifying data structures in the code as being one of static data structures and non-static data structures, wherein a static data structure comprises a data structure that is not changed during execution of the packet processor code and a non-static data structure comprises a data structure that is changed during execution of the packet processor code; and

managing one or more data structures associated with the packet processor code in a manner specific to the identification of the one or more data structures as static data structures or non-static data structures, wherein the manner in which the static data structures are managed differs from the manner in which the non-static data structures are managed;

wherein at least a portion of the data structures comprise tree structures;

wherein the managing step comprises updating the one or more tree structures associated with the packet processor code in a manner specific to the identification of the one or more tree structures as static tree structures or non-static tree structures, wherein the manner in which the static data structures are updated differs from the manner in which the non-static data structures are updated; and

wherein the step of updating the one or more tree structures comprises updating the one or more tree structures in accordance with a multi-staged upgrade process;

wherein the multi-staged upgrade process comprises a preparation stage, an update stage and a cleanup stage;

wherein the preparation stage for a non-static tree structure comprises allocating an indirection address for a flow function referenced by the non-static tree; and

wherein the indirection address for the flow function points to an address of the flow function in a current version of the packet processor code, and wherein the preparation stage for a non-static tree further comprises modifying one or more references to the flow function to point to the indirection address for the flow function.

2. The method of claim 1 , wherein the preparation stage for a static tree structure comprises building a new tree structure.

3. The method of claim 2 , wherein the preparation stage for a static tree structure further comprises generating and storing one or more write operations for use in accessing the new tree structure, wherein the one or more write operations are operative to modify a root address to point to the new tree structure.

4. The method of claim 3 , wherein the update stage for a static tree structure comprises propagating the one or more write operations to the packet processor.

5. The method of claim 4 , wherein the cleanup stage for a static tree structure comprises reclaiming one or more memory locations available after the update stage.

6. The method of claim 1 , wherein the preparation stage for a non-static tree structure further comprises generating and storing one or more write operations for use in accessing the non-static tree structure in an updated version of the packet processor code, wherein the one or more write operations are operative to update the indirection address for the flow function to point to an address of the flow function in the updated version of the packet processor code.

7. The method of claim 6 , wherein the update stage for a non-static tree structure comprises propagating the one or more write operations to the packet processor.

8. The method of claim 7 , wherein the cleanup stage for a non-static tree structure comprises replacing the allocated indirection address with the address of the flow function in the updated version of the packet processor code.

9. A method of updating tree structures associated with code executable on a network processor, comprising the steps of:

identifying tree structures in the code as being one of static tree structures and non-static tree structures, wherein a static tree structure comprises a tree structure that is not changed during execution of the network processor code and a non-static tree structure comprises a tree structure that is changed during execution of the network processor code; and

upgrading one or more tree structures associated with the network processor code in a manner specific to the identification of the one or more tree structures as static tree structures or non-static tree structures, wherein the manner in which the static tree structures are upgraded differs from the manner in which the non-static tree structures are upgraded;

wherein the step of updating the one or more tree structures comprises updating the one or more tree structures in accordance with a multi-staged upgrade process;

wherein the multi-staged upgrade process comprises a preparation stage, an update stage and a cleanup stage;

wherein the preparation stage for a non-static tree structure comprises allocating an indirection address for a flow function referenced by the non-static tree; and

wherein the indirection address for the flow function points to an address of the flow function in a current version of the packet processor code, and wherein the preparation stage for a non-static tree further comprises modifying one or more references to the flow function to point to the indirection address for the flow function.

10. The method of claim 9 , wherein the code executable on the network processor comprises code for executing a packet classification function.

11. A network processor configured to have tree structures associated with code executable thereon updated by a process comprising the steps of:

identifying tree structures in the code as being one of static tree structures and non-static tree structures, wherein a static tree structure comprises a tree structure that is not changed during execution of the network processor code and a non-static tree structure comprises a tree structure that is changed during execution of the network processor code; and

upgrading one or more tree structures associated with the network processor code in a manner specific to the identification of the one or more tree structures as static tree structures or non-static tree structures, wherein the manner in which the static data structures are upgraded differs from the manner in which the non-static data structures are upgraded;

wherein the step of updating the one or more tree structures comprises updating the one or more tree structures in accordance with a multi-staged upgrade process;

wherein the multi-staged upgrade process comprises a preparation stage, an update stage and a cleanup stage;

wherein the preparation stage for a non-static tree structure comprises allocating an indirection address for a flow function referenced by the non-static tree; and

wherein the indirection address for the flow function points to an address of the flow function in a current version of the packet processor code, and wherein the preparation stage for a non-static tree further comprises modifying one or more references to the flow function to point to the indirection address for the flow function; and wherein the network processor comprises circuitry.

12. The network processor of claim 11 , wherein the network processor is implemented on an integrated circuit.