Define unidirectional vs. bidirectional tables in spec

[jafingerhut]

The current PNA says that the main control processes a mingled stream of packets, some from network-to-host, others from host-to-network, in the same P4 control, each with their direction identified via a standard metadata direction input field.

Regardless of whether we keep this, or have separate P4 controls for network-to-host and host-to-network directions, but both of those controls can make calls to 'shared' controls that contain tables, there will be tables that can be apply'd by packets being processed in both directions.

There are several packet processing use cases that require either a table that can be apply'd on packets in both directions, or some communication and cooperation between pairs of tables. The current PNA architecture is based upon the idea that tables that are apply'd by packets in both directions of traffic flow through a NIC are useful things that should be supported explicitly.

As long as such tables are supported in PNA by one of the mechanisms described above, or a different mechanism, it seems to be a useful adjective to define explicitly in the PNA specification. Here is a first cut at such definitions:

A table is bidirectional if it can be apply'd sometimes by packets in net-to-host direction, and sometimes by packets in the host-to-net direction.

A table is unidirectional if it can only be apply'd by packets in one of those two directions, never the other.

Given the current P4_16 language specification and all of the ways that PNA code might be organized described above, it is possible to determine from static analysis of a P4 program whether a table is bidirectional or unidirectional. This can be done by examining the complete conditional expression that qualifies apply() statements on the table. If that condition implies that the packet's direction is always net-to-host, or always host-to-net, then the table is unidirectional. If the condition is sometimes true for host-to-net packets, and sometimes true for net-to-host packets, then the table is bidirectional.

We could imagine creating an annotation indicating what the developer thinks each table should be, and have the compiler give an error if that annotation is statically determined by the compiler to be incorrect, but it is not obvious that this is a very valuable kind of consistency/lint type of check in a P4 program. I mention it only because there should be no need for such an annotation, and even if there were one, the compiler should be able to determine what the annotation should be, given the contents of the rest of the program.

If a bidirectional table has direct resources, e.g. direct counter, direct meter, direct register idle_timeout timer state, or data plane add-on-miss functionality, it is far easier to implement it as a single physical table in hardware. If one attempted to implement such a bidrectional table as two unidirectional tables in hardware, it would lead to the same kinds of potential inconsistencies between the state of the two hardware tables that one finds in switch architectures with such tables, and multiple independent pipelines. See https://p4.org/p4-spec/docs/PSA-v1.1.0.html#appendix-multi-pipeline-psa-devices for some discussion of that topic.

[jnfoster]

Just to note: given mutable state (e.g., registers, or even a header stack) and any form of recirculation, it probably won't be decidable whether a table is bidirectional or unidirectional.

[jafingerhut]

If this is more subtle than I am imagining, it is probably best to talk about this in person rather than over Github issues, but all I am thinking of here is that in a single execution of a P4 control, it should be possible to symbolically and statically determine from the source code of that control a logical condition under which a table is applied if it is true, and not applied if it is false.

I realize that not all formulas are this simple, but a straightforward example is:

if ((stdmeta.direction == PNA_Direction_t.NET_TO_HOST) && (meta.foo == 5)) {
    t1.apply();
}

This is clearly a unidirectional table, since the condition implies that the stdmeta.direction must be NET_TO_HOST.

There are other such logical formulas where it definitely does NOT imply that stdmeta.direction is always one value, or always the other (e.g. the condition (hdr.ipv4.dstAddr > 50), at least in the absence of knowledge of any relationship between that input field and the direction of the packet). If there truly are undecidable cases, then I'd say that a compiler should call it a bidirectional table in the absence of straightforward provable evidence that it is unidirectional.

[hesingh]

Why use annotation? Use a new table property to specify if a table is used for incoming or outgoing or both direction. For Network Packet Broker, only hardware is used with a symmetric hash which matches both directions.