Proposed new externs ExactMap and TernaryMap

[jfingerh]

This was first discussed in a public PNA meeting on 2022-Jun-13.

The original motivation for the new proposed externs is to have constructs that are in some ways similar to P4 tables, but:

(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.

(b) they simply "return a value" rather than execute an arbitrary P4 action.

Attached is a P4_16 source file pna_extern_defns.p4.txt that defines the extern objects. Something like this would be added to the pna.p4 #include file if this proposal goes forward.

Below is an edited version of a file that I used to explain the new extern's behavior in the first meeting discussing it, plus some notes of discussion we had during that meeting.

The originally proposed name of ExactMap was ExactMatchLookupTable. Not only does this seem too long, but putting "table" anywhere in its name makes it more confusing to talk about, since it is not a P4 table (despite the similarities). ExactMap was proposed as a shorter name that avoids the "table" word confusion.

Here are some examples of how to instantiate and call the originally proposed extern object originally proposed, as defined in the file pna_extern_defns.p4:

    // Example of ExactMap with type bit<W> for key type and return
    // value type.

    // instantiation of an instance named `emap1`, in a control before
    // the apply { ... } block

    ExactMap<bit<8>, bit<16>, _>(
            size = 128,
            default_value = 42)  // default value returned for all other keys
        emap1;

    bit<16> v;

    apply {
        // ... other code here ...
        v = emap1.lookup({hdr.ipv4.protocol);

        // A target _might_ support multiple lookup() operations on
        // the same instance per packet, or it might limit the number
        // of lookup() operations to 1 per packet, 2 per packet, etc.
        // That is a target-specific decision.  The most portable P4
        // code would limit itself to 1 lookup operation per instance,
        // per packet, just as P4 developers do today for P4 table
        // apply() calls.

        //w = emap1.lookup(hdr.ipv4.srcAddr[7:0]);

        // ... more other code here ...
    }

For the purposes of understanding the behavior of the code above, it should be the same as the code below, which does not use the new extern.

    // Code that behaves the same as the above, and has a very similar
    // control plane API

    bit<16> v;

    action emap1_set_value (bit<16> val) { v = val; }

    table emap1_table {
        key = { hdr.ipv4.protocol : exact; }
        actions = { emap1_set_value; }
        size = 128;
        default_action = emap1_set_value(42);
    }

    apply {
        // ... other code here ...
        emap1_table.apply();
        // ... more other code here ...
    }

The example below is nearly the same as the first one above, but it uses a struct type for the key type. This is a straightforward way in existing P4_16 to have "multiple fields" in such an extern as the lookup key.

Independently from the key, the return value type could also be a struct type. The example below uses a struct type for the return value, as well as for the key.

    // Example of ExactMap with struct types for key type and return
    // value type.

    struct MyKeyType1_t {
        bit<8> f1;
        bit<16> f2;
    }
    struct MyValType1_t {
        bit<1> valid;
        bit<16> foo;
    }

    MyValType1_t v;
    ExactMap<MyKeyType1_t, MyValType1_t, _>(
            size = 1024,
            default_value = {valid = 0, foo = 0})  // default value returned for all other keys
        emap2;

    apply {
        // ...
        v = emap2.lookup({hdr.ipv4.protocol, hdr.ipv4.srcAddr[15:0]});
    }

One advantage of using struct types for key types is that it gives a clear choice for what to use for "key field names" in a table-like control plane API when adding/deleting entries to this extern -- i.e. use the names of the struct members, of the struct that is type K.

Note that P4Runtime API 1.x does not support struct types as table keys today. It could be extended, of course, but not there now. Proposal here would be to use field names f1, f2 for emap2 as key fields in control plane API of emap2.

TODO: Would tuples have any advantages over structs for emap2 example? One potential disadvantage vs struct is that struct members have names that control plane API could use for emap2, but tuple members do not have names.

Vlad: Note that for TernaryMap, the type of a key field int should have a mask with type bit, probably, not int.

Thomas: This seems fairly target-specific. Why not go to the P4_16 language spec and make a separate method? e.g. table_name.lookup(key_expr), as shown in sample code snippet below?

    // Thomas Calvert: Why not make this look more like an existing P4
    // table, but perhaps with different table properties to
    // distinguish it?

    bit<16> v;

    table emap3 {
        key = { hdr.ipv4.protocol : exact; }
        size = 128;
        value_type = bit<16>;  // Andy: I am making up possible syntax here on the fly
        default_value = 42;
        // actions table property is NOT ALLOWED for this variant of
        // table, because value_type table property is defined.
    }

    apply {
        // ...
        v = emap3.lookup();
        // ...
    }

Alan Lo: Is there a way to make the above look more like other P4 table definitions?

Perhaps using the 'implementation' table property, as shown in code snippet below.

    table emap4 {
        key = { hdr.ipv4.protocol : exact; }
        size = 128;
        implementation = ValueReturner;   // making up proposed name `ValueReturner` on the fly during discussion here
        // TODO what the other table properties would be, and what the
        // definition of the ValueReturner extern is.
    }

Andy is summarizing in his (Andy's) own words a week after Vlad said something like the following near the end of the meeting. Any differences between this and what Vlad actually said are Andy's fault. pna_extern_defns.p4.txt

[jfingerh]

Partially remembered and new comments regarding going to the P4 language design work group and extending the definitions of P4 tables to enable similar features.

• One of the motivations for making these externs is that extern calls can be made within expressions, including within the bodies of P4 actions, and we would like to enable the new extern lookup() calls to be performed within action bodies, among other places in the code.

Note that the P4 language spec has for all 1.x versions released since 2017 disallowed performing table_name.apply() calls within P4 action bodies. Or at least, it has said that P4 implementations need not support this, and the open source p4c compiler has always so far given an error message if you attempt to do so. See Appendix F of the P4_16 language specification, the last table, the row labeled "table", and the column labeled "action", where the cell contains the word "no". That is intended to mean "tables cannot be called (i.e. apply()'d) from within a P4 action".

• Another reason is that the P4 language design work group is, fairly reasonably, a conservative bunch, representing developers of multiple P4 target devices. Extending tables is possible, but is not a quick process. I certainly do not mind if some day P4 tables are extended with similar capabilities, but one way to convince a conservative group of folks that something is a good, solid, workable idea is to show that multiple targets can implement it, and any issues in its specification have been worked out. Defining new externs can be done in any P4 architecture, without changes to the P4 language specification, and is one way towards this.

[mihaibudiu]

This seems related to this https://github.com/p4lang/p4c/pull/2739

[jfingerh]

This issue for the P4 language specification is tracking the possible addition of a list type in the P4 language spec, which would be useful in enabling the p4c front end to perform type-checking on the const_entries or entries argument value of these proposed ExactMap / TernaryMap externs. We can define these externs without that language feature, too, but then the P4 compiler back-ends would need to do all error-checking on the value of those constructor parameters.

Not a big deal to me either way, but if the list type is added to the language spec and p4c relatively soon (e.g. before end of 2022 calendar year), I will update this PR to use that list type for those parameters to these extern constructor calls.