Apply() a table more than once in different branches of a conditional

[edgar-costa]

Some days ago I found the following bug in the bmv2 compiler backend (see conversation below):

http://lists.p4.org/pipermail/p4-dev_lists.p4.org/2017-October/001545.html

I was asked to open an issue and provide an example where the problem can be reproduced. I wrote a very simple program that can be compiled and exhibits the problem.

In the tar.gz you will find a p4 program that acts as a repeater and applies the same table in two different if branches that are selected by either having a TOS field of 0 or something else. Then it will apply test_table and set the tos field to either 100 or 200. No matter what you do that after applying test_table the p4 program will always jump to hdr.ipv4.tos = 200;.

compiler_bug.tar.gz

[mihaibudiu]

Indeed, the generated code is incorrect. The program looks like this:

if (x) {
   t.apply(); 
   z = 1;
} else {
   t.apply();
   z = 2;
}

The "next_table" after t can only have one value; the compiler picks one of the two assignments. For this program we can pull the apply above the "if", but this is not a general solution. We could also reject any program in which a table is applied more than once, no matter where. That would be an easy solution. Anyone have a better proposal? @antoninbas @ChrisDodd @cc10512 @hanw

[mihaibudiu]

I will assume that we can close this bug; the resolution is to give a compile-time error message for such a case.

[MaoJianwei]

Excuse me, no solution, but just give a compile-time error? ...

but how can we move up t.apply() in this case below?

if (x) { t.apply(); z = 1; } else { if() { __ t.apply(); __ z = 100; } else { __z = 2; _____} }

Same problem: https://github.com/p4lang/behavioral-model/issues/470

[antoninbas]

I may be wrong but it seems to me that you could use the following code instead (I use y for the second if condition since you left it empty in your example):

if (x || y) {
    t.apply();
}
if (x) {
    z = 1;
} else if (y) {
    z = 100;
} else {
    z = 2;
}

Not all control-flows can be easily transformed. For example:

if (x) {
    t1.apply();
    t2.apply();
} else {
    t2.apply();
    t1.apply();
}

assuming the order of application for t1 and t2 is important.

[MaoJianwei]

I am sorry that I may not show the key problem to you very clearly.

The key point is the callee don't go back to the right position of the caller.

I think this is important for Programmable. And it may be easy to implement by using some hardware register to keep the invoking stack status, (in hardware layer). thanks!

t1 invoked in line 2 should not go back to line 6.

if (x) { t1.apply(); t2.apply(); } else { t2.apply(); t1.apply(); }

[antoninbas]

I'll be honest, I have no idea what you are trying to say. You gave me a P4 snippet that does not compile and I gave you some equivalent code that does compile because it does not apply the same table twice. I do not know what you mean by "the callee don't go back to the right position of the caller". If you have a P4 program for which the compiler produces an invalid bmv2 JSON, please by all means open a new issue to report this. Otherwise I think we have explained clearly that the bmv2 compiler backend does not support multiple apply statements for the same table because of limitation in the bmv2 representation of control flows. The issue you are referring to, https://github.com/p4lang/behavioral-model/issues/470, is considered closed because we are no longer producing an invalid JSON for you program; instead we are rejecting the program as explained above. I am not saying that we will never support multiple apply statements for the same table in bmv2 and its compiler backend, because that is indeed valid P4 code, but there is no clear road map for this. This issue is meant to track that: https://github.com/p4lang/p4c/issues/457. I do not consider this a very high priority issue, because I have yet to run into a real-world scenario where the program cannot be rewritten easily to avoid the multiple apply statements.

[MaoJianwei]

I believe this schema codes can express the problem clearly,

The problem is: t1 invoked in line 2 will go back to line 6, when t1 returns. And in fact, it should not go back to line 6, but should go back to line 3 (t2.apply)

I think the amendment of this problem is important for Programmibility.

if (x) { t1.apply(); t2.apply(); } else { t2.apply(); t1.apply(); }

This interesting situation can be see in https://github.com/p4lang/behavioral-model/issues/470

thanks.

[antoninbas]

You're describing a bug that no longer exists since the program is now rejected. This has never been the intended / expected / correct behavior.

[mihaibudiu]

The P4-16 specification allows various P4 target devices to impose such constraints on the legal programs. While it would be feasible for the software simulator to allow table accesses in any order, the software simulator is intended to emulate to some degree the behavior of typical hardware devices, such as the RMT chip: https://dl.acm.org/citation.cfm?id=2486011. In such hardware devices the packet processing is done in a pipeline, and tables are physically placed in pipeline stages; the packet only travels forward in the pipeline. This explains why such architectures impose an order on the table traversals.

P4 is not just about programmability, it is about programming real high-speed devices, which may have such constraints. It is actually necessary to understand the constraints as a programmer if you expect your program to run on very high speed devices.

[jafingerhut]

Edgar:

I see an email because I get email notifications of all comments on p4c issues and pull requests, but I do not see this comment on the Github issue on github.com. Did you send it only as an email reply, or perhaps you posted it as a comment on github.com but then decided to delete it?

I can spend a little while looking into the behavior across a few p4c versions with a few programs if you still think things have changed, but at least as one preliminary result, when I compile p4c at commit 7b1733b and compile testdata/p4_16_samples/issue986-bmv2.p4, I see this error message:

$ p4c --target bmv2 --arch v1model issue986-bmv2.p4
issue986-bmv2.p4(35): [--Werror=invalid] error: ingress.t1: Invalid Program
is not supported by this target, because table ingress.t1 has multiple
successors
    table t1 {
          ^^

On Tue, Oct 15, 2019 at 11:20 AM Edgar Costa notifications@github.com wrote:

Not sure if writing in a closed issue is the best way, but since I opened this some years ago I thought writing here would be the best.

So today in a practical session I saw one student applying the same table in a if else branch, I first thought that his program was not compiling because of that, but after fixing the real problem it compiled. As far as I remembered (since this is almost 2 years old) I thought you decided (and verified reading this issue again) to reject all those programs so I got a bit confused.

Later I tried it on my own laptop, and indeed no compiler error. So I checked with the same program and using the p4c from the commit when this issue was fixed: ba40d71 https://github.com/p4lang/p4c/commit/ba40d7181c89a612d845896078ae4348471cbbc5 and that showed an error:

error: Program is not supported by this target, because table t1 has multiple successors table t1 {

Was this removed intentionally or the bug was added back by mistake?

How to reproduce:

I used this testdata file that was created when the issue was closed https://github.com/p4lang/p4c/blob/master/testdata/p4_16_samples/issue986-bmv2.p4

Compiler that throws error: ba40d71 https://github.com/p4lang/p4c/commit/ba40d7181c89a612d845896078ae4348471cbbc5

Compiler that does not throw the error: 7b1733b https://github.com/p4lang/p4c/commit/7b1733b7ffb09fb616e1d32de4020bb026a39d23

Aren't those testdata to check if there is any problem when you update the compiler?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/p4lang/p4c/issues/986?email_source=notifications&email_token=AAA2YPMSZV2ILOD4PFTWWQDQOYCXTA5CNFSM4EAR4TJKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEBJXTVY#issuecomment-542341591, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAA2YPLM5SNGQNSSXWWN5GDQOYCXTANCNFSM4EAR4TJA .

[edgar-costa]

Yes I removed the message because after sending it I tried a bit more and found out that I was wrong and the new compiler does also throw the error. I guess I did something wrong when I tested first. So thats why I removed it. Sorry for bothering.

However, as I said, I first realized of this because one student had a program with the same table applied to times and it compiled without errors. I then realized that if you have something like this:

if (true)
{
    table.apply();
}
else 
{
    table.apply();
}

In this case the compiler does not complain at all. Is that because in some pre-compiling phases code branches that will never be executed are removed?

[mihaibudiu]

The compiler will remove the unreachable branch. In general, bmv2 had traditionally a set of constraints on what patterns were allowed, and the compiler is trying to emulate these constraints. These constraints are inspired by the real hardware constraints of Tofino. If you read old papers about p4 they talk about a table graph, and the "successor of a table". One way to explain the constraints is that any path the control-flow execution takes the order of the tables must be the same. Things are a bit more complicated in P4-16 because the compiler can synthesize new tables for statements that are not table.apply() statements or if statements; in P4-14 there weren't any other statements; all code was in actions.