New match kind: optional

[stefanheule]

Personnel

• Owner: @stefanheule
• Supporters: @jafingerhut

Design

• Document: See below

Implementation

• p4-spec: Merged into PSA spec
• p4c: Part of PSA.p4, Add match_kind optional to PSA include file p4c#2696

Process

• LDWG discussed: April 2021 https://docs.google.com/document/d/1XSgdXeG1UuF1FM_XAqxDrHeN4dHZWBnJPKVS6SnGNwM/edit#heading=h.smw0dn8iuclh
• LDWG approved: April 2021 https://docs.google.com/document/d/1XSgdXeG1UuF1FM_XAqxDrHeN4dHZWBnJPKVS6SnGNwM/edit#heading=h.smw0dn8iuclh
• Merged into p4-spec:
• Merged into p4c: Add match_kind optional to PSA include file p4c#2696

I would like to propose optional as a new match kind. It is a match kind that matches a value exactly (like exact), or behaves like a wildcard (like ternary with the all-0 mask).

There are two main motivations for introducing this match kind:

• Support for opaque/logical values on fixed hardware. When P4 is used with fixed-function switches (switches that are not fully programmable), some entities use values that are logical, i.e., they have some value in the P4 program that may not be identical to what is actually used in the hardware. For instance, port numbers might be logical, and have a different representation in hardware. In these cases, some match kinds like ternary cannot be used, unless the mask is either the all-1 bitstring (exact match), or the all-0 bitstring (wildcard). Any other mask can likely not be supported. The new match kind optional allows exactly these two cases, and can easily be supported by the hardware. It is more flexible than exact, as matching on it is not required.
• Expressing restrictions on the desired masks. Even when the hardware supports ternary matches with any mask, one might want to limit the masks used by the controlplane. optional is a very natural restriction. For instance, one might use optional to match on eth_type, as eth_type is essentially an enum, and most likely the use of any mask other than all-1 or all-0 is not meaningful.

[jnfoster]

Another nice idea. Again in P4_16, architectures are free to define their own match-kinds. Is the proposal to add this to core.p4?

[stefanheule]

Yes, the proposal is to add it to core.p4. optional (and set) seems like a very generically useful feature, so I think it would be useful to add it to the standard library.

[vgurevich]

@stefanheule ,

While I agree with you and others that the feature is generally useful, I think that the right course of action would be to add it to the architectures that can support it first.

That's especially true about set that certainly requires additional hardware support to create bitmaps on the fly (it can also almost certainly result in wider TCAM allocations), but even optional might not be quite straightforward if you think about P4Runtime implications (you need to define how to pass "don't care" as a separate value).

Once there is some experience with the feature and a consensus, it can certainly be considered for the "promotion" to the core library.

[stefanheule]

Thanks for all the comments. I agree that TCAM allocations can get wider when set is used, there is basically a tradeoff between how many rows are used vs how wide each entry is. On some architectures and in some use-cases, there can be significant wins in terms of resource usage, but obviously not always.

I also agree that P4Runtime will need to be extended, but that is true for any new match kind. I am very interested in actually using these new match kinds, and I would be working on extending P4Runtime support with these new match kinds if they get adopted into core.p4 (or into PSA).

[jafingerhut]

A nice property of the proposed 'optional' is that I have definitely seen use cases in practice where this is a desired restriction on the table entries.

Any platform could implement 'optional' as 'ternary' if it wanted to, so there is no more difficulty to implement this than there already is for 'ternary', other than the control plane restriction on masks.

Plus, there are at least some implementations that could take advantage of the restriction on the mask and do a more efficient job in the data plane of implementing the table.

[vgurevich]

Did we have a chance to discuss it in LDWG?

I do not believe it makes sense to add different match kinds to the core spec right off the bat -- the architectures that desire a certain match kind can always have it. Once a certain match kind becomes popular and implemented in multiple architectures, it can be promoted to the core library. There is a range match kind that was in P4_14 spec that is also generally very useful, but it didn't make it into the core library, because more often than not it is not trivial to implement.

I do have serious concerns with the implementation of this specific match kind on high-speed hardware.

Here is an example:

table port_vlan_mapping {
    key = {
        meta.port : exact;
        meta.outer_vid : exact;
        meta.inner_vid : exact;
   }
   ...
}

Change one or more fields to optional and a table that was easily implementable in SRAM has to be moved to a TCAM, which may become prohibitively expensive (a table like this usually has a lot of entries). At least for ternary and lpm the vast majority of people understand that this will happen, but I I seriously doubt that this is the case with optional.

Moreover, many practical data plane programs simply reserve the value 0 to indicate None/Not-set and thus avoid this problem entiirely

[stefanheule]

No, it was skipped over in last weeks meeting, maybe we can discuss it at the next meeting.

I do have serious concerns with the implementation of this specific match kind on high-speed hardware.

It sounds like the concern is not with the implementation, but whether people understand the implications of of using optional or not. I think in general P4 has the property that a seemingly small change in the program can case a large change in how the program is realized in hardware/how expensive it is in hardware/whether it fits in a given hardware. optional seems no different in this respect.

Using 0 as a special value sometimes works, but clearly not always. It's also just nicer to use optional from a PL standpoint when you have the option to do so, that makes your intentions very clear as opposed to relying on convention to use 0 as a special value.

[vgurevich]

Given that optional seems to be only going together with exact, I think that this is a valid concern.

Note also, that the entries will require priority as well. For example, imagine this table:

table t  {
   key = {
      f1 : optional;
      f2: optional;
      f3: optional;
   }
}

Now, you are trying to insert entries with the following keys:

(1, 2, _), (_, 2, 3), (1, _, 3)

Which one should take the priority?

In any case, I do not see why this needs to be included in the core library right away instead of letting the architectures that wish to implement it (and I do not know how many takers are there) to do it on their own.

I would be more inclined to agree with the proposal if you could demonstrate an efficient non-TCAM implementation for such a match kind. Otherwise, I think this is really a nicety that will probably confuse people more than help.

[stefanheule]

Yes, absolutely, optional entries will need a priority.

To give some more context: We have several use-cases where we would like to use optional (but it does not exist right now), and we use ternary instead. I disagree that "optional goes together with exact", I view optional as a more restrictive version of ternary, for cases where you don't want or need the flexibility, or for cases where you literally cannot use any mask (for ternary) that isn't all-0 or all-1 (i.e., optional). The canonical example here is probably port, where at least some chips do not allow you to use any masks, but you can use a wildcard match, or a full match.

[vgurevich]

@stefanheule , can you please elaborate on the last statement: are you saying that the masks are restricted to be "all 1s" or "all 0s" only? This is probably not the HW restriction -- it is imposed by the SW instead -- the HW implementation is still TCAM.

I feel that once we have a priority involved, we are getting too close to the ternary with the restrictions imposed on the control plane API side. I do not feel that's something that needs to go into the core spec.

[stefanheule]

Lets talk about this in the next meeting and see how the community feels.

[mihaibudiu]

This could be done with:

table t  {
   key = {
      f1 : exact @optional;
   }
}

[mihaibudiu]

The agreement seems to be that the LDWG is asking for a prototype implementation of this feature involving the compiler (probably v1model) and P4Runtime. This would require adding the annotation to v1model.p4, and then we can consider promoting it to core.p4.

[jafingerhut]

If this were implemented via an annotation, rather than a new match_kind, it seems far preferable to me to do it not this way:

table t  {
   key = {
      f1 : exact @optional;
   }
}

but instead like this:

table t  {
   key = {
      f1 : ternary @restrict_mask_only_exact_or_all_wildcard;
   }
}

Where I am not being serious on the annotation name, but trying to be precise on its meaning.

Why do I say this?

With the second form, you can ignore the annotation, and it would implement something in the target that is more general than the user needs, but it would be correct.

With the first form, if you ignore the annotation, it does not implement what the user wants at all, because it cannot do "all wildcard" match on the field.

Sorry, I missed the first hour of the LDWG meeting today, and any discussion that may have been had then on this topic. I am personally fine with having a new match_kind here. I only wanted to respond to the "if it is done as an annotation instead" part of this discussion.

[vgurevich]

@jafingerhut, I agree with you 100% on this one.

[stefanheule]

I made PRs against v1model and P4RT for this feature.

[mihaibudiu]

I think we can close this issue since we have already merged this match_kind into PSA.p4