Add definition of initial table entries, without const qualifier

[jfingerh]

[jfingerh]

Intended to be a change to the spec that resolves issue https://github.com/p4lang/p4-spec/issues/1159, but note that it is not complete yet. You are free to add review comments for the changes that have been made so far, but the section defining the options for initial entry priorities has not been written yet.

[jfingerh]

@antoninbas @smolkaj @jnfoster @thantry @mariobaldi @mbudiu-vmw This is ready for review. Corrections and comments (or approval) before the next P4 LDWG meeting on 2022-Dec-05 would be much appreciated, if you have time. Otherwise it probably won't get into the spec for another month or two after that (if it gets into the spec).

Note that the per-entry const qualifier and per-entry initial priority values might require extensions to the data model of P4Runtime API, e..g perhaps adding an optional const field for each entry, and the auto-generated .entries.txt would need a way to specify that a table had initial entries without a global const before entries.

[jafingerhut]

@vgurevich @sayanb @slicking This is ready for review. Corrections and comments (or approval) before the next P4 LDWG meeting on 2022-Dec-05 would be much appreciated, if you have time. Otherwise it probably won't get into the spec for another month or two after that (if it gets into the spec).

See my previous comment on this PR, regarding new fields likely need for P4Runtime .entries.txt files. This feature addition seems likely to require similar enhancements in TDI/bfrt.

[jafingerhut]

@thantry @antoninbas @smolkaj @mariobaldi @vgurevich @sayanb @slicking This is ready for review. Corrections and comments (or approval) before the next P4 LDWG meeting on 2022-Dec-05 (one week from today) would be much appreciated, if you have time. Otherwise it probably won't get into the spec for another month or two after that (if it gets into the spec).

Note that the per-entry const qualifier and per-entry initial priority values might require extensions to the data model of P4Runtime API, e..g perhaps adding an optional const field for each entry, and the auto-generated .entries.txt would need a way to specify that a table had initial entries without a global const before entries.

This feature seems likely to require similar enhancements in TDI/bfrt.

[mariobaldi]

This looks good to me. I am in favor of approving this.

[mihaibudiu]

@jafingerhut please note that the grammar requires more extensive changes to allow "priority" to be used as a regular identifier. (We should review the spec grammar again, it may have fallen behind the implementation.)

[jafingerhut]

TODO for Andy when all other open questions about this PR have been resolved: Add changes to grammar.mdk file, and consider whether priority should be added to list of keywords or not.

[apinski-cavium]

Overall I am ok with this change. I am not happy with the syntax around priorities but I won't block the change if other people are ok with the syntax.

[jfingerh]

@apinksi-cavium Any alternate syntax(es) for specifying priorities that you might suggest?

[apinski-cavium]

@apinksi-cavium Any alternate syntax(es) for specifying priorities that you might suggest?

Just have a colon (':') after the priority if it is present. But as I said I don't want to bike shed the syntax here (https://en.wikipedia.org/wiki/Law_of_triviality ).

[jfingerh]

Understood the desire not to bikeshed, but if we don't have comments here about it, the only other place is the LDWG meetings, and they are short enough that I don't want to wait until those meetings to resolve issues, if possible.

If you mean having a colon after priority=<expression>, that makes sense and seems to me like it could work.

If you mean having a colon but not priority=, that seems to make the grammar ambiguous if the priority and colon are optional. Well, maybe not ambiguous, but two consecutive lines like this seem visually a bit odd to me:

5: a1();   // exact match value of 5 for a table with a single key field, no priority explicitly specified
10: 6: a2();  // priority 10 explicitly specified, exact match value of 6 for the table entry

[jnfoster]

If we are brainstorming syntax, how about using curly braces (or any other kind of brace... could be < ... > or {| ... |} for example) to denote an entry, with the priority optionally listed before the entry itself?

And we could support both

entries = { ... } // no order implied

and

entries = [ ... ] // order implied

which matters if the compiler is allocating priorities.

Putting these two ideas together, you might get something like this:

...
  entries = [
    10 : { 1, a1() },   // priority 10
    { 2,  a2(99) },   // no priority given; compiler allocates 
    _ : { 3, a3() },   // priority explicitly elided, compiler allocates
    100 : { 4, a4() }, // priority 100
    200 : { 5 & 1, a5() } // priority 200
] 

I like the idea that an entry (match + action) is a unit of data that gets special syntactic treatment. I prefer having the priority outside of the entry. But one could also consider moving it inside...

As a further extension, one could also allow using optional labels if being extra explicit:

  100 : { key = 4, action = a4() }, 

Or even,

  priority = 100 : { key = 4, action = a4() }, 

This syntax is obviously not backwards compatible, but we could deprecate the earlier syntax for const entries in several versions. I don't think it's in widespread use, so the disruption should be minimal...

Last thought: rather than making language extension and syntax decisions piecemeal, we will really be more efficient if we can identify the principles that are guiding the language design. Of course, each situation needs to be studied on its merits, but if we can find common principles and patterns to guide our thinking, we will move forward faster. Here I have tried to follow the following principles:

• We do add special syntax for P4's most important domain-specific constructs (here, a match-action table entry)
• We try to reuse syntax for data structures -- here using { ... } to denote an unordered collection and [ ... ] to denote an ordered collection. (This one is debatable and not perfectly followed, but hopefully clear.)
• And we try to reuse syntax for separators (: and ,), labeled arguments (key = and action = ), and elided arguments (_).

[thantry]

I like Nate’s way of specification. It starts to look more like a hashtable with composite types.Otherwise, looks quite good to me.ThanksHariSent from my iPhoneOn Dec 28, 2022, at 9:40 PM, Nate Foster @.***> wrote: If we are brainstorming syntax, how about using curly braces for an entry, with the priority before it? ... entries = [ 10 : { 1, a1() }, // priority 10 { 2, a2(99) }, // no priority given; compiler allocates _ : { 3, a3() }, // priority explicitly elided, compiler allocates 100 : { 4, a4() }, // priority 100 200 : { 5 & 1, a5() } // priority 200 ] I like the idea that an entry (match + action) is a unit of data that gets special syntactic treatment. I prefer having the priority outside of the entry. But one could also consider moving it inside... As a further extension, one could also allow using optional labels if being extra explicit: 100 : { key = 4, action = a4() }, And we could support both entries = { ... } // no order implied

and entries = [ ... ] // order implied

which matters when the compiler is allocating priorities. This syntax is obviously not backwards compatible, but we could deprecate the earlier syntax for const entries in several versions. I don't think it's in widespread use, so the disruption should be minimal...

—Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you were mentioned.Message ID: @.***>

[jafingerhut]

Hari wrote: "I like Nate’s way of specification. It starts to look more like a hashtable with composite types."

I have no objections to the syntax. I would like to caution one about explaining it as a hash table, though. Both the P4Runtime API and TDI control plane APIs explicitly support and allow there to be multiple entries in a table with the same priority as each other.

Background details on what it means if multiple entries have the same priority, and why it might be useful: Which one is the "winner" if more than one entry with the same numeric priority is not specified by the P4Runtime API. Some control plane software only uses this capability in situations where all entries with the same priority are mutually exclusive, i.e. at most one of them can match any given search key value. It can provide efficiency advantage when adding entries to such tables, in that fewer entries need to be moved when new entries are added.

[mihaibudiu]

@jafingerhut will this be ready for discussion at the next LDWG meeting?

[jafingerhut]

Sorry, still no updates to this PR from me, but I would like to try to nail down the desired syntax, if possible.

This comment probably uses too many words to explain why I think we don't need to introduce two separate delimiters like square brackets vs. curly brackets for a list of table entries, and why curly brackets should be sufficient.

Gory details:

Today's const entries = { .... } syntax DOES imply an order to the entries in the ... list. See this paragraph in the current language spec:

If the runtime API requires a priority for the entries of a table—e.g. when using the P4 Runtime API,
tables with at least one ternary search key field—then the entries are matched in program order,
stopping at the first matching entry. Architectures should define the significance of entry order
(if any) for other kinds of tables.

I mention this because of the proposal in comments above for a syntax using square brackets around a list of entries, e.g. entries = [ ... ], with order required, vs. { ... } with order not required. It seems to me like this would be a backwards-incompatible change, and while we can certainly consider such a backwards-incompatible change, we should do it fully aware that we are doing so, and that it is worth doing so.

It is not clear to me that having a way to specify "order not required" is useful here. Sure, there are tables where all key fields are exact match_kind only, and there the order is not important as long as all key values are distinct (and I believe we should require them to be distinct, or give an error message at compile time, in for such exact match tables). But having only a syntax that means "source code of entries is significant" is easy to implement in that case: the compiler can ignore that order if it wants to.

[jafingerhut]

Alternate syntax for initial entries has been proposed in this alternate PR. At most one of this PR and that one should be merged: https://github.com/p4lang/p4-spec/pull/1231

[jafingerhut]

@jnfoster @thantry I have tried to implement a grammar similar to what you propose in your comments above, but everything I have tried that looks similar to your example syntaxes leads to a grammar that causes shift/reduce conflicts in bison. My work in progress version of it can be found on an alternate PR here: #1231

Unless someone can find a bison-friendly grammar for an alternate syntax they like, that alternative syntax will not make any progress.

Addendum: I have found two possible ways to introduce the syntax you propose and keep bison happy.

(1) Define a new table property, e.g. initial_entries. The new table property has your proposed syntax for specifying table entries in its list. bison is happy because once it has seen entries or initial_entries, it can use pretty much arbitrarily different sub-grammars for parsing what appears after that.

(2) Keep the existing current syntax for const entries, but parse your new proposed syntax if there is no const, i.e. it is just entries = { ... }. As far as bison is concerned, this is as easy as (1). It seems a little trickier for explaining to human developers, though, that the syntax of the value is different depending upon whether the const is present or absent, for the same table property name entries.

I kind of like (1). Thoughts?

[jafingerhut]

AI Andy: Suggestion from 2023-Apr-10 LDWG meeting: Try a modification of this grammar that requires a colon character after "priority=10" but before the rest of the entry specification, and see if Bison accepts this grammar (this can be tried from the grammar that is in the p4c PR for the partial implementation of this feature). If Bison likes it, update this PR to have that syntax change.

[jafingerhut]

Commits 13 & 14 made on 2023-Apr-10 should make no changes to this PR's content, other than to merge it with the latest main branch version of the spec, which had some conflicts because of the use of [INCLUDE=grammar.mdk:nonTerminalName] Madoko constructs in the latest main version, which was merged into main after this PR was first written.

[jafingerhut]

Current summary of this issue and possible proposed syntaxes for specifying the initial entries:

See slides 35 and 36 near the end of this slide deck: https://docs.google.com/presentation/d/1GW-9FDtyLuwqV_mdGeDh_qqDiey0VkQ1/edit#slide=id.g22d0e434be1_0_5

It shows examples of the syntaxes of the two PRs that exist for this issue, with links to those two PRs.

I am pinging people who have given comments on preferred syntaxes here. I am personally happy with any of the ones mentioned in the slides linked above. If someone wants to come up with another syntax that is not one of those, then it almost certainly will not happen in the P4 spec release in April 2023, but some later month after we discuss it again in a later LDWG meeting.

@mbudiu-vmw @jnfoster @thantry @apinski-cavium @vgurevich

[mihaibudiu]

I very much prefer mandatory "priority=value:" I will add support for that in the compiler's PR.

[thantry]

Approve! Thanks for the great work in pushing this through!