Runtime sharing of unit memories between match tables in a network forwarding element

1. A method of sharing unit memories between at least two match tables in a data plane packet processing pipeline of a physical forwarding element, the method comprising:

from a plurality of available unit memories of the packet processing pipeline, allocating a first set of unit memories to a first match table and a second set of unit memories to a second match table;

determining that the first set of unit memories is filled to a threshold capacity after storing a plurality of entries in the first set of unit memories;

de-allocating a first unit memory in the second set of unit memories from the second match table by moving contents of the first unit memory in the second set of unit memories to a second unit memory in the second set of unit memories;

prior to de-allocating the first unit memory in the second set of unit memories from the second match table, determining that the first set of unit memories comprises less unit memories than a number of unit memories allowed for the first match table;

allocating the first unit memory in the second set of unit memories to the first match table;

allocating a third set of unit memories from the plurality of available unit memories of the forwarding element to the first match table; and

de-allocating a unit memory from the first match table after a number of unit memories reaches a number of unit memories allowed for the first match table.

2. The method of claim 1 , wherein a unit memory increment size is specified for the first match table, wherein allocating the third set of unit memories to the first match table comprises allocating the unit memories in the third set of unit memories to the first match table in the specified increment size.

3. The method of claim 1 further comprising: when the number of unit memories allowed for the first match table does not exceed an absolute maximum number of unit memories allowed for the first match table, incrementing the number of unit memories allowed for the first match table after allocating the first unit memory to the first match table.

4. The method of claim 1 , wherein a match unit memory allocated to a match table corresponds to one or more unit memories allocated to one or more tables associated with the match table in the packet processing pipeline,

wherein an entry in a match unit memory comprises an address of a corresponding entry in the unit memories allocated to the one or more tables associated with the match table,

wherein moving a match entry to a new location does not require moving the entries in the unit memories allocated to the one or more tables associated with the match table,

wherein the one or more tables associated with the match table comprise one or more of: (i) an action table, (ii) a meter table, (iii) a statistics table, (iv) a table comprising stateful data, (v) a ternary indirection table (TIND), and (vi) a selector table.

5. The method of claim 1 , wherein a match unit memory allocated to a match table corresponds to one or more unit memories allocated to one or more tables associated with the match table in the packet processing pipeline,

wherein an offset to an entry in the match unit memory is a same as an offset to a corresponding entry in the unit memory allocated to an associated table,

wherein moving a match table entry to a new location with a particular offset in the match unit memory requires moving a corresponding unit memory entry allocated to an associated table to a location with a same offset location in an action unit memory,

wherein the one or more tables associated with the match table comprise one or more of: (i) an action table, (ii) a meter table, (iii) a statistics table, (iv) a table comprising stateful data, (v) a ternary indirection table (TIND), and (vi) a selector table.

6. The method of claim 5 , wherein the data plane packet processing pipeline comprises a plurality of move registers to move an entry in a unit memory allocated to a table associated with the match table from a first location to a second location, the move registers configured to:

inhibit a matching operation for the entries in the first and second locations while the entry is being moved;

using a chain of move operations to move contents of the second location to an empty location in the associated table;

moving the contents of the first location into the second location; and

enabling the match operation for the entry in the second unit memory.

7. The method of claim 1 , wherein de-allocating the first unit memory in the second set of unit memories from the second match table and allocating the first unit memory in the second set of unit memories to the first match table comprises:

pausing packet processing operations of the packet processing pipeline;

receiving an incremental configuration from a control plane of the forwarding element to de-allocate the first unit memory from the second match table and allocate the first unit memory to the first match table; and

resuming the packet processing operations of the packet processing pipeline without losing a current state of the packet processing pipeline.

8. The method of claim 7 , wherein the current state of packet processing pipeline comprises contents of one or more of a set of: (i) match tables, (ii) action tables, (iii) status registers, (iv) statistics registers, (v) arithmetic logic units (ALUs), (vi) meter memories, (vii) stateful memories, (viii) ternary indirection memories, and (ix) selector memories in the data plane packet processing pipeline.

9. The method of claim 1 , wherein the forwarding element is one of a network router and a network switch.

10. A physical forwarding element comprising a data plane packet processing pipeline, the data plane packet processing pipeline comprising a plurality of unit memories, the data plane packet processing pipeline configured to:

allocate, from a plurality of available unit memories of the packet processing pipeline, a first set of unit memories to a first match table and a second set of unit memories to a second match table;

determine that the first set of unit memories is filled to a threshold capacity after storage of a plurality of entries in the first set of unit memories;

de-allocate a first unit memory from the second match table by a move of contents of the first unit memory to a second unit memory in the second set of unit memories;

determine, prior to de-allocation of the first unit memory from the second match table, that the first set of unit memories comprises less unit memories than a maximum number of unit memories currently allowed for the first match table;

allocate the first unit memory to the first match table;

allocate a third set of unit memories from the plurality of available unit memories of the forwarding element to the first match table; and

de-allocate a unit memory from the first match table after a number of unit memories reaches a number of unit memories allowed for the first match table.

11. The physical forwarding element of claim 10 , wherein a unit memory increment size is specified for the first match table, wherein allocate the third set of unit memories to the first match table comprises allocate the third set of unit memories to the first match table in the specified increment size.

12. The physical forwarding element of claim 10 , when the number of unit memories allowed for the first match table does not exceed an absolute maximum number of unit memories allowed for the first match table, the packet processing pipeline further configured to increment the maximum number of unit memories currently allowed for the first match table after allocating the first unit memory to the first match table.

13. The physical forwarding element of claim 10 , wherein at least one match unit memory allocated to a match table corresponds to one or more unit memories allocated to one or more tables associated with the match table in the packet processing pipeline,

wherein at least one entry in a match unit memory comprises an address of a corresponding entry in the unit memories allocated to the one or more tables associated with the match table, wherein a move of a match entry to a new location does not require a move of the entries in the unit memories allocated to the one or more tables associated with the match table,

wherein the one or more tables associated with the match table comprise one or more of (i) an action table, (ii) a meter table, (iii) a statistics table, (iv) a table comprising stateful data, (v) a ternary indirection table (TIND), and (vi) a selector table.

14. The physical forwarding element of claim 10 , wherein at least one match unit memory allocated to a match table corresponds to one or more unit memories allocated to one or more tables associated with the match table in the packet processing pipeline,

wherein an offset to an entry in the match unit memory is a same as an offset to a corresponding entry in the unit memory allocated to an associated table,

wherein a move of a match table entry to a new location with a particular offset in the match unit memory requires a move of a corresponding unit memory entry allocated to an associated table to a location with a same offset location in an action unit memory,

wherein the one or more tables associated with the match table comprise one or more of (i) an action table, (ii) a meter table, (iii) a statistics table, (iv) a table comprising stateful data, (v) a ternary indirection table (TIND), and (vi) a selector table.

15. The physical forwarding element of claim 14 , wherein the data plane packet processing pipeline comprises a plurality of move registers to move an entry in a unit memory allocated to a table associated with the match table from a first location to a second location, the move registers configured to:

inhibit a matching operation for the entries in the first and second locations while the entry is being moved;

use a chain of move operations to move contents of the second location to an empty location in the associated table;

move the contents of the first location into the second location; and

enable the match operation for the entry in the second unit memory.

16. The physical forwarding element of claim 10 , wherein de-allocate the first unit memory from the second match table and allocate the first unit memory to the first match table comprises:

pause packet processing operations of the packet processing pipeline;

receive an incremental configuration from a control plane of the forwarding element to de-allocate the first unit memory from the second match table and allocate the first unit memory to the first match table; and

resume the packet processing operations of the packet processing pipeline without losing a current state of the packet processing pipeline.

17. The physical forwarding element of claim 16 , wherein the state of the packet processing pipeline comprises contents of one or more of a set of: (i) match tables, (ii) action tables, (iii) status registers, (iv) statistics registers, (v) arithmetic logic units (ALUs), (vi) meter memories, (vii) stateful memories, (viii) ternary indirection memories, and (ix) selector memories in the data plane packet processing pipeline.

18. The physical forwarding element of claim 10 , wherein the forwarding element is one of a network router and a network switch.