Makes sense, thanks for the explanation.<div><br></div><div>I agree that a more formalized way to define deparsers would be good to have in a future spec.<span></span><br><br>On Monday, June 20, 2016, Antonin Bas <<a href="mailto:antonin@barefootnetworks.com">antonin@barefootnetworks.com</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div><div><div><div><div>In my opinion, the example in the spec is not chosen well. If you have A -> B and B->A, then you cannot obtain a topological sort because you end up with a loop in the parse graph (cyclic graph). The current compiler will throw an error and reject your program.<br></div>The deparsing order is determined entirely at compile time by running a topological sort. Calls to add_header etc. have no impact on the header ordering. If multiple orderings are valid, <b>one is chosen "at random"</b>, which I would agree is far from optimal (I am not even sure the compiler gives a warning).<br></div>For example, let's assume you have 2 possible parse paths only:<br></div>hdrA -> hdrB<br></div>and<br></div>hdrA -> hdrC<br></div>The parse graph in this case is very simple. Yet we have two distinct valid topological ordering: hdrA -> hdrB -> hdrC and hdrA -> hdrC -> hdrB.<br></div>Imagine a packet comes in which takes the first path. At the beginning of the pipeline, hdrA and hdrB are therefore valid, while hdrC is not. If the packet goes to the deparser like this (without any processing), there is no real ambiguity and the outgoing packet will be identical to the incoming packet.<br>However, if during the match-action pipeline I call add_header(hdrC) and make hdrC valid, then the deparser will either produce hdrA/hdrB/hdrC or hdrA/hdrC/hdrB. In some cases, you know that only hdrA/hdrB/hdrC makes sense from a networking / protocol point of view. You can therefore add a dummy transition in path1:<br></div>hdrA -> hdrB -> hdrC<br></div>thus making the topological sorting unique<br><br></div>Antonin<br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jun 20, 2016 at 6:19 PM, Javier Blazquez <span dir="ltr"><<a href="javascript:_e(%7B%7D,'cvml','jblazquez@riotgames.com');" target="_blank">jblazquez@riotgames.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Thanks Antonin. I have a few questions about the topological sort you mentioned.<div><br></div><div>As you say, if a packet may have header A followed by header B _or_ header B followed by header A then the static parser graph does indeed have multiple topological sortings. However, when an actual packet flows through the pipeline this packet will have only one of the two orderings, hence it should be possible to reconstruct those headers in the right order.</div><div><br></div><div>I assume the issue is that the P4 compiler currently builds its deparser from a static view of the parse graph, and it therefore can't modify its behavior at runtime depending on how the input packet looked like? If the deparser knew which `extract` calls were made in which order then it could reconstruct the packet correctly in those situations.</div><div><br></div><div>What about calls to `add_header`/`push`/etc? Those calls don't appear in parsers, so how does the deparser find those headers when it reconstructs the output packet? I assume it visits every single header in the P4 program and checks its valid bit, and if so writes out the header. If that's the case, which ordering does it choose for those headers that have been pushed or added in compound actions? Do they all go after the regular headers that were extracted in a parser?</div><div><br></div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jun 20, 2016 at 4:50 PM, Antonin Bas <span dir="ltr"><<a href="javascript:_e(%7B%7D,'cvml','antonin@barefootnetworks.com');" target="_blank">antonin@barefootnetworks.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div>Hi,<br><br></div>As Javier say, the deparser behavior is not rigorously specified in P4 v1.1, which hopefully should change in the next version of the language. As I explained in this previous email to the mailing list (<a href="http://lists.p4.org/pipermail/p4-dev_lists.p4.org/2016-May/000319.html" target="_blank">http://lists.p4.org/pipermail/p4-dev_lists.p4.org/2016-May/000319.html</a>), the P4 compiler uses a topological sorting on the parse graph to determine the deparsing behavior. The deparser then follows this ordering and emits headers for which the validity bit is set.<br>This can make things tricky / ambiguous because a topological sorting is not always unique. Furthermore, in some cases, you may wish to emit packets (e.g. CPU packets) which the parser may not need to know about. In this case, you may have no choice but to add dummy transitions to your parse graph. See the copy_to_cpu program in the tutorials repository for an example: <a href="https://github.com/p4lang/tutorials/blob/master/examples/copy_to_cpu/p4src/copy_to_cpu.p4#L45" target="_blank">https://github.com/p4lang/tutorials/blob/master/examples/copy_to_cpu/p4src/copy_to_cpu.p4#L45</a><br></div>In your case, you have no choice but to make appropriate calls to add_header / remove_header to mark headers as valid / invalid. Maybe future P4 versions will let us program the deparser in a more structured way.<br><br></div>Best,<br><br></div>Antonin<br></div><div class="gmail_extra"><div><div><br><div class="gmail_quote">On Mon, Jun 20, 2016 at 4:22 PM, Javier Blazquez <span dir="ltr"><<a href="javascript:_e(%7B%7D,'cvml','jblazquez@riotgames.com');" target="_blank">jblazquez@riotgames.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>I think of deparsing as simply the reversal of the parsing process, that is, going through whatever `extract` operations have been executed and copying those headers back from the Parsed Representation into the packet for transmission.</div><div><br></div><div>In that scenario the use of metadata to switch among parsers shouldn't change things because all that matters is what `extract` operations have been performed on actual headers and in which order. Remember that metadata is by definition not part of the actual packet on the wire so whatever values your metadata headers have shouldn't matter when it comes to assembling the packet for transmission.</div><div><br></div><div>However, an interesting side question that comes to mind is regarding the `push`, `pop`, `add_header` and `remove_header` primitive actions. These are not used during the parsing phase; they're used as part of compound actions in the ingress or egress pipeline, but they affect the packet that will be assembled for transmission.</div><div><br></div><div>So deparsing isn't _just_ the reversal of the parsing process, but also the addition/removal of headers as per those primitives above? In which case, does the order of headers in the transmitted packet follow the order in which push/add_header/etc have executed for a given packet? And regarding header stacks, I assume they're always serialized as a single block (i.e. all valid headers in the stack following each other)? The 1.1 spec doesn't seem to specify the order in which headers will be serialized to the output packet.</div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jun 20, 2016 at 3:01 PM, Huynhtu Dang <span dir="ltr"><<a href="javascript:_e(%7B%7D,'cvml','huynh.tu.dang@usi.ch');" target="_blank">huynh.tu.dang@usi.ch</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Dear all,<br>
<br>
I wonder if metadata is considered in deparsing phase? As I set the value of metadata in an action and use this metadata value to switch among parsers. But it seems the deparser skips checking the value of metadata or the value of metadata is reset before deparsing.<br>
<br>
Best,<br>
Tu Dang<br>
<br>
<br>
_______________________________________________<br>
P4-dev mailing list<br>
<a href="javascript:_e(%7B%7D,'cvml','P4-dev@lists.p4.org');" target="_blank">P4-dev@lists.p4.org</a><br>
<a href="http://lists.p4.org/mailman/listinfo/p4-dev_lists.p4.org" rel="noreferrer" target="_blank">http://lists.p4.org/mailman/listinfo/p4-dev_lists.p4.org</a><br>
</blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
P4-dev mailing list<br>
<a href="javascript:_e(%7B%7D,'cvml','P4-dev@lists.p4.org');" target="_blank">P4-dev@lists.p4.org</a><br>
<a href="http://lists.p4.org/mailman/listinfo/p4-dev_lists.p4.org" rel="noreferrer" target="_blank">http://lists.p4.org/mailman/listinfo/p4-dev_lists.p4.org</a><br></blockquote></div><br><br clear="all"><br></div></div><span><font color="#888888">-- <br><div data-smartmail="gmail_signature"><div dir="ltr">Antonin<br></div></div>
</font></span></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br><br clear="all"><br>-- <br><div data-smartmail="gmail_signature"><div dir="ltr">Antonin<br></div></div>
</div></div>
</blockquote></div>