Should ternary "const entries" be allowed for an exact match field?

[vgurevich]

Attached is a trivial test program issue2515.p4.txt. Compile it with -DISSUE_2514_FIX for now to work around #2514 .

The program compiles just fine, but I wonder if that's correct. The reason is that the table has two exact match fields, but the const entries fill the table using entries with ternary specification:

    table t {
        key = {
            hdr.h.f1 : exact;
            hdr.h.f2 : exact;
        }
        actions = { hit; }
        const entries = {
            (16w0x0101, 0)                     : hit(1);
            (16w0x0101 &&& 16w0x0505, 0 &&& 0) : hit(5);
            (_,_)                              : hit(0);
        }
    }

It might or might not be explicitly allowed by the spec, but can (in case one has a wide key) create a lot of issues for the driver (and the backend), which will try to evaluate (_) for a 128-bit-wide key, for example.

[hesingh]

If a table keyElement has exact match type, configuring a ternary const entry for it is possible because we can use "value &&& 0xffff...". The compiler could block all other ternary const entries since match is exact. Maybe, a target backend can block ternary const entry if the table only has exact match keyElements.

I saw issue 2514. A single keyElement in table key is fine. One should not have to use another keyElement to make any table and const entries work.

[jafingerhut]

When I try a v1model architecture program that does something like your example program, it gives an error that the &&& operator is not supported in exact key expressions:

p4c --target bmv2 --arch v1model issue2515-try2.p4
issue2515-try2.p4(108): [--Werror=unsupported] error: &&&: unsupported exact key expression
            (0x0101 &&& 0x0505, 0 &&& 0) : set_bd_dmac_intf(4, 5, 6);
             ^^^^^^^^^^^^^^^^^
issue2515-try2.p4(108): [--Werror=unsupported] error: &&&: unsupported exact key expression
            (0x0101 &&& 0x0505, 0 &&& 0) : set_bd_dmac_intf(4, 5, 6);
                                ^^^^^^^
issue2515-try2.p4(109): [--Werror=unsupported] error: DefaultExpression: unsupported exact key expression
            (_,_) : my_drop();
             ^
issue2515-try2.p4(109): [--Werror=unsupported] error: DefaultExpression: unsupported exact key expression
            (_,_) : my_drop();
               ^

I do not know, but it might be that this error check is performed in the v1model back end of p4c, not the front or mid end.

Note that if you want such checks performed in front or mid-end code, note that the range match_kind is not defined in core.p4 for P4_16 (or at least it hasn't been yet). issue2515-try2.p4.txt

[jafingerhut]

As a small bit of additional evidence, p4test issue2515-try2.p4 gives no error messages at all, for the program mentioned in my previous comment above.

[vgurevich]

@jafingerhut -- thanks for checking and chiming in.

1. I do certainly agree that it is weird that we have the syntax in the language for the range sets (start..end), but do not have range match kind among the core ones. :)
2. We can certainly leave the checks to the backends, but that will make programs even less portable

[jafingerhut]

I suppose it might be reasonable to perform the checks for all match_kind's defined in core.p4 in front/mid end, and leave others not defined in core.p4 for the back end? That is more a question than an answer -- @mbudiu-vmw do you have any thoughts on that idea?

[mihaibudiu]

The initializers for tables are a particularly difficult problem, since we don't know at compile time all the various match kinds that can exist, and how the table contents is specified for each of them. We have hardwired in the grammar some syntax for ternary one, but we cannot support other ones currently.

[jafingerhut]

p4c with the v1model bmv2 back end supports exact, lpm, optional, range, and ternary today, where the syntax for lpm uses the same syntax for ternary, but with a restriction that the mask must be a prefix mask: https://github.com/p4lang/behavioral-model/blob/master/docs/simple_switch.md#specifying-match-criteria-for-table-entries-using-const-entries

All of those seem like reasonable syntaxes to me, although having one that was more convenient for lpm, e.g. where you specify a value and a prefix length instead of a value and a mask, would be nice, e.g. instead of 0xcafe0000 &&& 0xffff0000 you could write something closer to 0xcafe0000 / 16, except not exactly that syntax, because that means dividing two integers in all other contexts of P4_16, and it seems fairly awkward to have the / operator have two different meanings in different contexts (possible, but a bit awkward).

[mihaibudiu]

No one says that the initializer for a table has to match the table type. In some cases the compiler may be able to convert one type to another. For example, using an exact table with a mask of 0x03 may translate into 4 different exact entries. Similarly, ranges may be converted to masks, as done today in select expressions. So the errors are relegated to the back-end of a specific architecture, which may know more about the kinds of table implementations. The front-end should only make sure that the widths are compatible.

[jfingerh]

Maybe I am misunderstanding you, but it seems perfectly reasonable to me to give a p4c front/mid-end error if a table key field is matchkind exact, but the const entries for that field is anything but a compile-time known value of the same type. That is, if it has an expression with &&& or .. or ``, that is an error.

Similarly, if it says it is ternary, the const entries initializer must be a single compile-time known value, or <value_expr> &&& <mask_expr>, or _, and anything else is an error.

If a match_kind is range, you only support a single <min_and_max_value, or <min_value> .. <max_value>. If the back end converts that to multiple ternary entries, no problem, but the programmer isn't allowed to say <value_expr> &&& <mask_expr> -- that would be a compile time error.

Is there anything you see controversial in such decisions?

[mihaibudiu]

No, my argument is just the opposite. A table is just a mapping from keys to actions. For convenience sometimes we express a set of keys using a compact expression. In the P4 grammar these are keysets. For example, a &&& b represents a set of 2^k keys, where k is the number of ones in b. Various hardware implementations support natively such compact representations, e.g., TCAMs.

But I don't see it necessary to tie a particular set representation to a particular implementation; it may be more convenient to express the sets of keys using some syntax for a table with a different implementation. For example, I think you should be allowed to use ranges and masks for exact tables. The compiler should only give an error if the table capacity is insufficient.

[jafingerhut]

It isn't necessary to tie them together, but I think it is extremely common for control plane APIs for P4 to make similar restrictions when adding/modifying/removing table entries as the ones I describe in my previous comment, because while it is possible to expand 0 &&& 0 for a 16-bit exact field into 65,536 entries (or even larger, 65,536 times the cross product of all other exact match fields that you use such techniques), imposing these restrictions on the users of such control plane APIs keeps at least some notion of data plane table capacity in mind. (I know that range entries in a control plane API are often implemented with multiple ternary entries -- but anyone that cares about predicting and managing number of TCAM entries in hardware finds this troublesome to keep track of, until and unless they learn how much the hardware expands these things into).

[jafingerhut]

I should have put this on the previous comment, but it seems very reasonable to me that for the same reason that control plane APIs impose such restrictions on the developers using them, it seems like a reasonable idea to make such restrictions in const entries.

[mihaibudiu]

Perhaps this should be a compiler flag. By default we would require them to match, but if the flag is set the compiler would make an effort to convert.

[mihaibudiu]

I made this into an enhancement, requesting such a compiler flag.