Generalize BMv2 JSON file format to enable the same identical table to be applied multiple times in a single pipeline

[jafingerhut]

I am considering making changes to BMv2 and p4c’s BMv2 back end that would allow compiling and executing P4 programs that apply the same table multiple times during the invocation of a single ingress or egress control.

Root cause for current restriction:

The BMv2 JSON data has a "tables" key, where for each table it has a "next_tables" key, with a value that is one of these two things:

• {action-name-executed -> next-table-or-condition-to-execute}
• {hit/miss -> next-table-or-conditional-to-execute}

Thus each named table in the P4 source code, if it is applied more than once in the same pipeline, the current BMv2 JSON schema can only represent it if all such table applies for a table t1 have the same "next_tables" value.

Motivation: Mainly personal dissatisfaction that this restriction has existed since BMv2 was originally developed, and having answered occasional questions about it over the years to newcomers.

Plan to generalize:

Create a new kind of object in a pipeline, perhaps named "table_applies", that is a list of nodes, each of which has the following fields:

• "next_tables", exactly like "next_tables" is now in a "table", except that instead of referring to next-tables, it will be next-table-applies.
• "table", the name of the table to apply when this "table_applies" node is executed.

Remove the "next_tables" field from "tables" objects.

Normally there will be exactly one "table_applies" node for each "table", but if a table is applied multiple times in the same pipeline, there will be one "table_applies" node for each such apply call, all pointing at the same "table" object.

"conditionals" nodes would also never point at "tables" in their "next_tables" fields, instead pointing at table-applies nodes.

There would be a new minor version number created in the BMv2 JSON file in order to take advantage of this new schema.

I think it would be best to continue supporting the current BMv2 JSON schema for at least a year or two, given how prevalent it is. That will require checking the version number in a few places during processing of the BMv2 JSON file.

Note: After such a change is made, and p4c's BMv2 back end is changed to take advantage of it, this would also make it possible to support for loops inside of a P4 control in the BMv2 back end.

[jafingerhut]

Some thoughts on implementation details:

Currently BMv2 internal data structures for table entries record not only the match criteria, action, and action parameters, but also the next-table value inside of each entry, which is calculated at the time the entry is added.

This is a performance optimization, to avoid needing to determine the next-table from the action executed, and the "next_tables" value.

Since by far the most common case is that a table is only applied once per pipeline, it would be nice to keep this performance optimization, as long as the final behavior remains correct.

I propose that for tables that are only applied once per pipeline, we keep this optimization exactly as it is now.

For tables that are applied N > 1 times per pipeline, we use this optimization for exactly one of the table-applies, but for the N-1 other table-applies, we determine at packet processing time from the action executed, plus hit/miss, what the next-table-apply-or-conditional is to be performed during packet processing. The in-memory data structures will remember which of the N table-applies is using the cached next-table-apply value in all of the entries, so that it will only be used for that table-apply.