Add ExactMap and TernaryMap extern definitions to pna.p4

[jfingerh]

See https://github.com/p4lang/pna/issues/45 for some notes on an earlier discussion of these externs.

[mihaibudiu]

I think this should be a separate library file, which can be included in pna.p4 if it is deemed to be standard.

[mihaibudiu]

This was discussed in the LDWG in May 2021: https://github.com/p4lang/p4c/pull/2739

[jfingerh]

"I think this should be a separate library file, which can be included in pna.p4 if it is deemed to be standard." Making it part of the PNA standard is exactly the reason this is being proposed and discussed. It might not meet with wide enough approval to become part of pna.p4, but that is my hope.

Of course we could make N optional parts of PNA. If that is met with reasonably wide agreement, we might do that. In practice, the larger N is, and the more often P4 developers use the optional features that are not implemented by all target devices, the less portable their programs will be. That doesn't automatically make every optional thing "bad", just less desirable than something all vendors agree to implement.

[jfingerh]

@apinski-cavium Is it quick for you to point out the way in which this code violates the current P4 language spec?

@mbudiu-vmw If you or Andrew have any thoughts on changes to this proposal that would enable an argument like const_entries to be specified, I am curious to learn about them. I would prefer one that did NOT require defining a separate constructor for each different number of entries, as that seems doomed to fail whenever someone wants to specify one more entry than the maximum someone picked when defining the constructors.

As you can tell from this proposal, I am OK if a proposal does not enable the p4c front/mid-end code to type check the value of const_entries, and any such type checking is relegated to the back end code of the target. Once that checking is done for one target in open source, other implementations could hopefully reuse it.

[apinski-cavium]

So it looks like I was wrong about _ types. See 7.2.13 Don't care types but I am still not 100% understand the semantics here. The example given in Section 17.1 only allows them on generics type while doing type unification on the generic type's paramaters (basically an anymous generic paramater type). When this was added, there was a good example and what seemed like a better explaination of it but it was changed and the example was moved and explanation changed.

[jafingerhut]

@apinski-cavium Do you mean that Section 7.2.13, and/or Section 17.1, were different in earlier versions of the spec that had a different explanation/example of _ types? I did a quick spot-check of the corresponding sections back to version 1.0.0 of the spec (available in the "Archives" section of this page https://p4.org/specs/) but did not notice any differences there.

[apinski-cavium]

@apinski-cavium Do you mean that Section 7.2.13, and/or Section 17.1, were different in earlier versions of the spec that had a different explanation/example of _ types? I did a quick spot-check of the corresponding sections back to version 1.0.0 of the spec (available in the "Archives" section of this page https://p4.org/specs/) but did not notice any differences there.

I looked into the git history (rather than published version of the spec) on this one to find where it changed. It changed when https://github.com/p4lang/p4-spec/commit/84db45872a112fd267485a2b16db51174b7f09af commit was pulled in. The example was never right to begin with anyways (because control type definition vs control definition). Note I still think there needs to be a clarification in the language dealing with extern constructors and externs functions because I think the current definition only allows it for (package, control and parser and action) type definitions rather than function calls.

[mihaibudiu]

The right solution is to extend the p4 type system to support generic lists. The entries is a list literal. The braces notation is somewhat overloaded now: it is used for tuples and structs too.

[jafingerhut]

@apinski-cavium Do you think that with a clarification in the language spec, that this proposed extern definition would be more clearly according to that clarified definition?

[mihaibudiu]

Why don't we actually add List or Vector types and literals to the language? May not be that difficult. We can talk about it at the next design working group. I will try to prototype something to make sure it works.

[jafingerhut]

@mbudiu-vmw @jnfoster How likely do you think extending the P4 type system to support generic lists would be in, say 3 to 6 months? I know that of course the answer depends upon how much effort is put into it, but wondering if you have some kind of guesstimate. If a smaller change to the language spec would make this PR legal using _ as it does (or some small variation), I'm content defining it that way for now.

[mihaibudiu]

This could be done in a couple of days of work if there are no unexpected surprises.

[jnfoster]

Agree. Just adding polymorphic lists would be an easy task.

[mihaibudiu]

Here is a possible example: https://github.com/p4lang/p4c/pull/3520. Check out the test files.

[mihaibudiu]

p4c actually accepts the vectors of tuples, but there's a bug in the tuple elimination pass in the midend which replaces tuples with structs, that one causes the errors reported.

[mihaibudiu]

I have amended the PR to accept the vectors of tuples correctly.

[jafingerhut]

Commit 2 on this PR updates the proposed new externs so that they use the new list type that may soon be added to the P4_16 language. For more information, see this PR for the language spec: https://github.com/p4lang/p4-spec/pull/1168, which contains a link to the PR for the p4lang/p4c repo that adds this feature.

As of 2022-Nov-18, this PR has been merged into open source p4c https://github.com/p4lang/p4c/pull/3520 and I have verified that with those changes, this code compiles without any errors.

[jafingerhut]

These are so similar to existing tables (the comments even show the equivalence), I think it would be nicer if we could somehow implement this using a table property. A couple ideas:

    table emap2 {
        key = {
            val1: exact;
            val2: exact;
        }
        // notice lack of "actions =" line here
        // lookup would be a special action recognised by the compiler
        default_action = lookup(emap2_val);
        // alternatively, we could introduce this new table property:
        direct_value = emap2_val;
    }
    (...)
    bit<4>  my_val1 = ...;
    bit<12> my_val2 = ...;
    emap2_val my_resp = emap2.lookup(my_val1, my_val2);

Personally I have a slight preference for direct_value, as this is an action-less table (and so default_action doesn't really make sense).

The underlying BCAM/TCAM primitives aren't something which is specific to a NIC as far as I know.

I think this should be a separate library file, which can be included in pna.p4 if it is deemed to be standard.

Of course we could make N optional parts of PNA. If that is met with reasonably wide agreement, we might do that. In practice, the larger N is, and the more often P4 developers use the optional features that are not implemented by all target devices, the less portable their programs will be. That doesn't automatically make every optional thing "bad", just less desirable than something all vendors agree to implement.

The flip side is that once something is in pna.p4 it becomes very hard to change our minds down the road. However going the other way is easier, i.e. moving an optional extern into the main pna.p4 file.

I am perfectly OK if we end up just creating more general P4 tables for this purpose, but note one of the original motivations for this in #45, repeated here:

(a) their lookup method can be called from inside the body of a P4 action. The P4_16 language spec explicitly disallows table_name.apply() calls within P4 action calls today, and always has since version 1.0.

I believe it was Roop who asked recently about this same issue, and I pointed out to him this limitation in the current P4 language spec, and our use case for wanting to call these externs within actions, and I also pointed out the following issue on the public p4-spec Github repo where the P4 language spec is discussed: https://github.com/p4lang/p4-spec/issues/947

Roop said he is motivated to raise this issue again, hopefully in the next P4 language design work group meeting on 2022-Dec-05, and I urge you to also attend that meeting to make your case, or support Roop however you can, if you want such a change made in the spec.

[jafingerhut]

The 2022-Dec-05 P4 language design work group meeting resulted in the list type being added to the P4 language spec, and it is part of open source p4c as I mentioned in an earlier comment, so at least in those ways, there is no impediment to considering this for PNA now.

I am mindful of Thomas Calvert's comment here https://github.com/p4lang/pna/pull/52#pullrequestreview-1189715364 Unfortunately the topic of generalizing P4 tables was not discussed at the 2022-Dec-05 language design work group meeting, at least partly due to a full plate of topics.

@thomascalvert-xlnx If you would like that issue discussed at the next (2nd Monday of January) language design work group meeting, we may as well suggest adding it to the agenda now. Would you like me to propose the discussion topic there, or would you like to?

[thomascalvert-xlnx]

@jafingerhut thanks for the poke, I've just sent Mihai an email to suggest adding it to the agenda.

[jfingerh]

@jafingerhut Add link to P4 LDWG issue related to this topic for reference.

[jafingerhut]

Here is link to issue proposing generalizing P4 tables in language design work group, which was discussed early in 2023, but not accepted: https://github.com/p4lang/p4-spec/issues/1209