Support nested structs in bmv2 compiler backend

[antoninbas]

I'm attaching a sample program.
nested_struct.p4.txt

[jafingerhut]

Not sure if this is a duplicate of #455
Whether it is or not, please keep this issue in mind, too: #486

[hesingh]

Sorry, I was buried with other work and got back to my pull request for nested bit-vec structs today. I have help during this summer to work on this issue. I updated code to cast between bit-vec structs and bits. I also fixed a bug in the onlybits... method. Note well, I not only want to support nested structs but also nested P4 headers with bit-vectors.

See latest code:

#971

The reason the pull request has been stalled is because code review asked for a midend pass to remove nested structs altogether. The reason was, in case, any code breaks. I could not get to this pass yet. A few clarifications on the pass would help. For brevity when I say "nested struct" I mean both "nested struct" and "nested header".

Do I remove any nested struct in control or parser parameters?
The midend pass cannot support extern method.
Remove any global nested structs
Remove nested struct from table key
Test control-plane API generation. However, I don't know how to test this one.
Anything else?

thanks.

Hemant

[jafingerhut]

If by "nested header" you mean enabling one header to be nested inside of another header, I would recommend not allowing that, unless you have proposed behavior for that (e.g. what would it mean to do setValid on an inner header, when the outer header was invalid?)

There are no such corner cases that I am aware of with allowing structs inside of headers.

[hesingh]

Yes. Ah, sorry, I forgot about the setValid() behavior in nested headers! So, I agree with you to not allow nested headers. So the trimmed down list is:

1. nested bit-vector structs.
2. Struct in Removed broken test #1 to be part of a p4 header?

[hesingh]

Code review for, https://github.com/p4lang/p4c/pull/971/files, said to remove nested structs altogether in a new midend pass. However, the PR has changed the frontend to support nested structs. So, the frontend generates control-plane API with control, parser, action, method, table key with nested structs, but, subsequently, the new midend pass flattens the nested structs in API.

Thus, the new pass is a frontend pass, not a midend pass.

[hesingh]

@ Mihai I could use some help with the frontend pass which flattens nested structs altogether and also changes any Casts. Thus, the pass is used when the frontend has structs/types, Casts, and table keys available. Where does the new pass get inserted in the list of frontend passes? I have included a short list below to show where I think the new pass goes in. Please confirm.

  new PrettyPrint(options),
    // Simple checks on parsed program
    new ValidateParsedProgram(),
    // Synthesize some built-in constructs
    new CreateBuiltins(),
    new ResolveReferences(&refMap, true),  // check shadowing
    // First pass of constant folding, before types are known --
    // may be needed to compute types.
    new ConstantFolding(&refMap, nullptr),
    // Desugars direct parser and control applications
    // into instantiations followed by application
    new InstantiateDirectCalls(&refMap),
                              NEW PASS                         <=== here?
    // Type checking and type inference.  Also inserts
    // explicit casts where implicit casts exist.
    new ResolveReferences(&refMap),  // check shadowing

[mihaibudiu]

There is no hard rule. The pass should be inserted as early as possible because no passes after that have to worry about the new construct. However, if you want this information to be available to the control-plane API you will have to make it a mid-end pass, because the API is generated after the front-end.

[hesingh]

If control-plane API is generated after the front-end, why was an action-inlining pass added to the frontend when, in the past action-inlining was only a midend pass? This is why I thought of a frontend pass. Anyway, I will develop the pass and then we can decide where the pass goes. thanks.

[mihaibudiu]

There is no reason to expose inlined actions to the control-plane, they are not inserted into tables.
That's why the action inlining can be part of the front-end.

[hesingh]

An update: I have tasked my summer intern (https://github.com/kartik-s) to develop the midend pass.
He used the P4 sample program provided in this issue and has been able to flatten nested structs in a new midend pass. Specifically, the code:

1. Sweeps over the whole program, finds nested bit-vector structs, and flattens them.
2. Finds any use of the nested struct in the program and translates the nested struct use to flattened struct use. We are working off of IR::Expression. Table keys and assignments have been used for unit testing.

Next week's plan:

1. Any use of nested bit-vec struct in an assignment statement and Casting is TODO. For example
   ip = (bit<32>) b.sip; // b is a bit-vec struct with "sip_t sip" as a bit-vec struct for member.
   The struct sip has already been flattened before the above line of code is processed. Shouldn't be too hard to fix.
2. Leverage's Mihai's nestedStructs midend pass to deal with b.sip as an argument to P4 control, or parser, or action.

[hesingh]

My summer intern has returned to college. For most of the summer, he spent time to develop the new midend pass to flatten nested data structures. I have emailed code changes to Mihai to take a look. Also, about 91 tests fail out of 1119. The failures will be worked on after Mihai's review.

[mihaibudiu]

The tricky part here are the struct initializers. These are list expressions, which do not carry enough type information. I am thinking to change the IR to add a struct initializer expression, which would have enough information; ListExpressions that are struct initializers have to be converted by the type checker into struct initializer expressions.

[hesingh]

@mbudiu-vmw Makes sense, thanks. Also, thanks for the flatten pass code review. I will change code and get back.

[mihaibudiu]

I think that your task is too difficult, you should perhaps wait for a StructInitializer expression in the IR. Then this would become much easier.

[hesingh]

ok, sounds good.

[mihaibudiu]

I will try to work on this next week.

[mihaibudiu]

The most useful thing you can do is write a short spec of what you expect this PR to cover.

[hesingh]

Will do and get back.

[hesingh]

nested-flatten-structs.pdf

Folks, I have attached a pdf doc regarding a short spec. Please review. thanks.

[mihaibudiu]

The problem with flattening structures is that it changes the structure of APIs. For example, if a header with nested fields is used as a table key then the fields will necessarily change when the structure is flattened. This will cause the control-plane API not to match anymore. So this proposal should be accompanied by a description of how control-plane APIs are supposed to handle headers with nested structure.

Why do we need to support structures in headers in the first place?
Many use cases for nested fields may be addressed suitably by using structure overlays, as written up in this proposal: p4lang/p4-spec#656

[hesingh]

@mbudiu-vmw I will look into control-plane API generation and add its dependency to the spec.

The programmable switch asic we developed a p4c backed for, uses union of data structures. P4 only supports union of P4 headers via a header_union. Thus our backend data structures are P4 headers. However, the asic hardware sub-element (Mux Comparator) uses a data structure with bit-fields and structures. This use case demands structures in headers. A Mux Comparator, common to many switching asics, performs comparisons in parallel. The comparisons are performed on parsed P4 code. The hardware has finite number of instructions to compare data. If a data structure is un-rolled, the Mux Comparator runs out of instructions. The Mux has enough width but not enough instructions to compare. This is why nested bit-vector structs work with this Mux. We used the simplest solution by changing p4c frontend to support nested bit-vector for struct and P4 header along with Cast support. The backend didn't have to change. Alternatives may exist to solve the problem, but may complicate the backend.

A structure overlay creates more complexity in the backend vs. a nested bit-vector structure. Also, nested bit-vector struct requires Cast support as well. Do you plan to add Cast support with structure overlay.

[hesingh]

I have attached a new pdf doc for spec and another .txt file for use of nested-structs. The summary turns out of be not using nested bit-vector structs or headers with any P4Runtime type - the types are listed in the pdf doc. Only parameters to Control blocks (control, action, and parser) can be nested bit-vector struct/header. At the moment it is only certain that nested bit-vector structs are supported. I need more time to confirm nested bit-vector structs as part of P4 header.
nested-flatten-structs-1.121.pdf

nested-structs-use.txt

[hesingh]

Folks have confirmed the need for supporting a nested bit-vector in a P4 header. An example is given below. I have added the same example to the nested-struct-use.txt file.

struct sip_t {
bit<28> lower28Bits;
bit<4> upper4Bits;
}

header our_bitvec_header {
bit<2> g2;
bit<3> g3;
sip_t sip;
}

[debmalyapan53]

eth.p4.txt
I am trying out a nested structure implementation in p4, but getting compiler bug error instead. Any workaround here?

[hesingh]

The bmv2 backend does not support nested structs yet.

[cbolson1]

Is there a workaround for this issue?

[mihaibudiu]

The workaround is to inline the structure in the header manually.
We have an open issue with the P4 spec to define how such nested structures are supposed to work.

[mihaibudiu]

Actually the conversation here seems to include several different topics. The issue is about nested structs.
The workaround is to flatten the structs.

[mihaibudiu]

The new midend pass added as part of the PR #1605 should handle most use cases (if not all) required by BMv2.

[mihaibudiu]

@cbolson1 : perhaps you can test it with your programs and let us know whether it works.

[hesingh]

@mbudiu: this PR includes nested_structs.p4 at the top. We can test the new midend pass with the P4 program if we haven't done so already. thanks.

[hesingh]

@mbudiu: I don't see recursive nested structs check in the new midend pass.

[mihaibudiu]

Look at the included test case

[hesingh]

Got it - good to go.

[cbolson1]

I tried this out with my code, and it seems to work. Thanks!

[mkwjoh004uct]

I am new to p4 linux and I am trying to run multiqueueing example but I get this error:
multi_queueing.p4(146): [--Werror=type-error] error: Field qid is not a member of structure struct standard_metadata
hdr.ipv4.tos = (bit<8>)standard_metadata.qid;
^^^
/usr/local/share/p4c/p4include/v1model.p4(61)
struct standard_metadata_t {
^^^^^^^^^^^^^^^^^^^
Compilation Error

How do I edit the v1model.p4 file in /usr/local/share/p4c/p4include/v1model.p4?

[hesingh]

@mkwjoh004uct Why did you pick this issue to discuss your problem because the problem is not related to nested struct?

A P4 program is not expected to change standard_metadata_t. v1model.p4 supports user metadata in the architecture. Stick qid in user metadata. See use of user metadata at this line of code.

https://github.com/p4lang/p4c/blob/master/p4include/v1model.p4#L719

Also, v1model.p4 is a frozen for any changes.