Define new operations on varbits

[jafingerhut]

Personnel

• [x] Owner: @jafingerhut
• [ ] Supporters:

Design

• [ ] Document: See below

Implementation

• [ ] p4-spec:
• [ ] p4c:

Process

• [ ] LDWG discussed:
• [ ] LDWG approved:
• [ ] Merged into p4-spec:
• [ ] Merged into p4c:

This is intended to be post P4-16. I wanted to add a placeholder issue to remind me to flesh out more details later.

The basic idea is that for some protocols, it would be useful to be able to read bits from, and modify bits within, a varbit field. This would be most useful if the bit offsets can be run-time calculated (if they were restricted to be at fixed bit offsets, then most likely the field could have been defined as a header with fixed width fields, and wouldn't have been defined as a varbit).

Draft version of signatures, open to refinement:

// return current dynamic length of @vb
bit<32> varbit_length(in varbit<W> vb);

// Change the dynamic length of @vb to @new_length_in_bits, or to W if @new_length_in_bits
// is larger than W.
void varbit_resize(inout varbit<W> vb, in bit<32> new_length_in_bits);

// I am not clear whether X needs to be a parameter as well as part of the return type.
// Extract and return @length_in_bits_X consecutive bit positions of @vb starting at offset
// @start_bit_offset.  @start_bit_offset == 0 is the most significant bit position of @vb.
// The return value is undefined in any bit positions that one attempts to extract from
// outside of the current dynamic length of @vb.
bit<X> varbit_slice(in varbit<W> vb, in bit<32> start_bit_offset, in bit<32> length_in_bits_X);

// replace X consecutive bit positions of @vb starting at offset @start_bit_offset with contents of
// @data.  @start_bit_offset == 0 is the most significant bit position of @vb.
// Any bits one attempts to inject outside of the current dynamic length of @vb are lost.
void varbit_inject(inout varbit<W> vb, in bit<32> start_bit_offset, in bit<X> data);

[mihaibudiu]

If you really want to manipulate varbits you probably should parse them. One way to do some of this stuff is to create a packet_in constructor with a varbit argument; then you can just use extract to slice it. You can also have a packet_out that writes to a varbit, and you can emit into it, but it is not clear what happens if you overflow.

These essentially would treat the varbit as a byte stream. One wrinkly is that today you cannot call a parser from a control.

[jnfoster]

Suppose I want to invert the middle (i.e., length(f) / 2) bit in a varbit field f. This is easy to do with @jafingerhut's proposal. How do I do this with yours?

If you really want to manipulate varbits you probably should parse them.

My example can't be parsed because the field for the middle bit would be surrounded by two varbit fields. But we restrict headers to a single varbit field.

One way to do some of this stuff is to create a packet_in constructor with a varbit argument; then you can just use extract to slice it.

I'm confused. We removed packet_in's constructor for a reason?

-N

You can also have a packet_out that writes to a varbit, and you can emit into it, but it is not clear what happens if you overflow.

These essentially would treat the varbit as a byte stream. One wrinkly is that today you cannot call a parser from a control.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/p4lang/p4-spec/issues/264#issuecomment-302744273, or mute the thread https://github.com/notifications/unsubscribe-auth/ABwi0lfjzg1ZMRtJMvwpzC2r_ry6J3Sxks5r7b4BgaJpZM4Ndbe- .

[mihaibudiu]

The spec allows any number of varbit fields in a header. The extract method only knows how to handle one, though. In our previous design we had an annotation called @length on a varbit field which works like the P4-14 field length. This would allow you to handle any number of varbit fields in the compiler. In fact, this is how the P4-14 -> P4-16 translation works, it adds these annotations. In the future we could amend the spec to allow any number of varbit fields in an extract, and the compiler could break the header into pieces for you.

[jafingerhut]

Another motivation for such a change - currently there is no way to modify the contents of a variable-length header, or to create one in an output packet unless that exact same header with a varbit field was parsed in the received packet. Lifting those restrictions would be nice in a few use cases.

[debmalyapan53]

How to modify the contents of a varbit field in a header, after extracting it using parser?

[jafingerhut]

The only operations on a varbit field defined in the P4 language specs as of right now are:

• extract it
• make the header containing it invalid via P4_16 setInvalid(), causing the varbit field to not be emit'd later, along with the rest of the header it lies within.

There are no standard ways defined to read parts of it, to modify parts of it, nor to make a header containing one valid via setValid(), and then initializing its contents.

Individual P4 implementations are free to define extensions that enable this, but I do not know if any of them do.

The best way I know of to read, or modify, or add, headers that are variable length, is to create multiple fixed length headers, one for each length case you want to handle in your P4 program.

[vgurevich]

My recommendation here (and in general) -- let's follow the actual capabilities of the practical hardware and even then start with an extern and then promote to the standard language capability.

Until then we are not going to do a good job anyway.

[KB00100100]

@jafingerhut Hi, I am very interested in the way to modify variable length headers. Could you give me some references or related papers?

The best way I know of to read, or modify, or add, headers that are variable length, is to create multiple fixed length headers, one for each length case you want to handle in your P4 program.

[jafingerhut]

I have hacked up a skeleton P4_16 program that demonstrates parsing of a variable length header for at least 4 different cases of length, into one of 4 different header types (one type for each of the 4 different lengths handled by the program).

You can see it here: https://github.com/jafingerhut/p4-guide/tree/master/variable-length-header

[jafingerhut]

And now there are two variations of the program, both of which I believe can parse the same set of packet headers, but one uses a header stack for an array of same-format repeated header contents, vs. the other which uses multiple header definitions with different formats (the latter is more general, since it can be used in situations where a header stack cannot).

[gbrebner]

Rekindling this discussion after a couple of real-life use cases indicated that possible extension of varbit capabilities would be a solution to a requirement: allowing run-time set-up of header values stored in tables for dynamic encapsulation. Hypothetical code fragment attached: varbit_example.txt

(Alternative solutions within the current language spec welcome, of course ...)

[jafingerhut]

At the 2019-Nov-04 LDWG meeting, I volunteered to test out a very simple P4_16 program that attempts to have an action that takes a type varbit<W> parameter from the control plane, and assign it to a field in a header that is then emitted with the output packet. The program I tried is attached to this comment, and the action is similar to one shown during the meeting.

Summary: It appears that everything needed for the functionality discussed in the meeting already exists in P4_16 the language specification. p4test gives no errors for the attached program, so it is legal according to the front end p4c code.

The BMv2 v1model architecture back end code of p4c does not support parameters of type varbit as action parameters, though. I do not know how much effort it would be to enhance it, but given the other things in the p4c back end and BMv2 code that do handle varbit field (see below), i would guess not a lot.

Gory details begin here:

Version of p4c source code I tested:

commit 92d6e69d760eb86f0131a5f1a18808835ce2a763
Author: Jed Liu <jliu@barefootnetworks.com>
Date:   Mon Oct 28 15:55:32 2019 -0700

No error from p4test, which seems consistent with the P4_16 language spec -- there is nothing illegal about this program, and assignment from one variable of type varbit<W> to another variable of that type with the same value of W is allowed.

$ p4test try-varbit-action-parameter.p4

When trying to compile this to a BMv2 JSON file with the v1model architecture, it gives the error message shown below. Not too surprisingly, the BMv2 v1model back end code does not support any types for action parameters other than bit<W> and int<W>. BMv2 implementation does support one varbit field in headers for extract, emit, assignment, and equality testing (see test cases mentioned below), so at least some of the support for handling varbit fields is in BMv2 already, and the p4c BMv2 back end code, just not as an action parameter.

$ p4c --target bmv2 --arch v1model try-varbit-action-parameter.p4
try-varbit-action-parameter.p4(68): [--Werror=invalid] error: options: Invalid action parameters must be bit<> or int<> on this target
    action add_options(bit<8> typeCode, bit<8> lenBytes, varbit<256> options) {
                                                                     ^^^^^^^

There are several existing test programs in the compiler that extract and emit headers containing one varbit field, and calculate and update checksums for them, using the v1model architecture primitives provided for the checksum calculations, and that have STF files to exercise these programs with BMv2 and check the output packets contain the expected values, e.g. checksum1-bmv2.p4, issue1025-bmv2.p4, and their corresponding .stf files.

equality-bmv2 - tests equality comparison between fields of type varbit, and between two headers containing a varbit, and assignment of one varbit field in a header to a same-max-width varbit field in a different header. Verified with STF test.

equality-varbit-bmv2 - a little more equality testing similar to previous program, with STF test try-varbit-action-parameter.p4.txt

[gbrebner]

Andy, thanks for the swift testing work, with encouraging results.

Just to summarize where I think we got to at today's LDWG meeting, we are (in the first instance) looking at "Create varbit values" as opposed to a more general "Define new operations on varbits". Created varbit values can be copied, and can be emitted.

So current situation is that parsing is the only way to create a varbit value.

We are now looking at varbit values coming in from action parameters, as an alternative. This has implications for P4Runtime. Antonin pointed out that it has support for varbit (https://github.com/p4lang/p4runtime/blob/master/proto/p4/v1/p4data.proto#L36), though this is not currently in use for populating tables.

Nate mentioned a third possibility for creating a varbit value: a constant fixed bit string is cast to a varbit value (with length) when assigned to a varbit. This seems fairly uncontroversial.

We acknowledge that some targets might not be able to support these two additional ways of creating a varbit value.

[jafingerhut]

Gordon, sounds like a good summary. The only part of what you describe in the previous comment that seems to me would be any change at all in the P4_16 language spec would be if we wanted to proceed with "creating a varbit value: a constant fixed bit string is cast to a varbit value (with length) when assigned to a varbit". Everything else is no change to the language spec (but an updated P4Runtime API spec for support via that API for varbit action parameters).

[gbrebner]

That's right. It would seem fairly uncontroversial, if we are liberating varbit from being just a captive of the parser scene.

While I'm on, and this may be false memory syndrome, but did we briefly also discuss the possibility of completing the "assignable, not operable" picture by allowing assignment of varbits to bits (I have a memory of Nate mentioning padding/truncation at one point, and that may have been the context)?

[vgurevich]

@jafingerhut, @gbrebner

Sorry for being late to the discussion -- I could not attend the last meeting on Monday.

I've read the proposal and I have some concerns that I'd like to discuss.

One basic concern is that even though a varbit<N> is allowed to have any length in the range 0..N bits, more often than not the valid values are limited to N - m * (8 * k), where k is usually a multiplier that is used by the corresponding "length" field in the preceding header. For example, a typical varbit<320> that is used to represent IPv4 options can only have lengths 0, 32, 64, 96, ... 320 and nothing in between. Note, that N itself does not have to be a multiple of 8, i.e. a varbit can, potentially start not on a byte boundary. (As an aside, the current extract() method for headers with varbits makes it pretty much impossible for a header to have more than one varbit field and as a result makes the requirement that valid lengths must be in least 8 bit increments mandatory).

When we perform varbit parsing, it is possible to ensure that the field has the correct length, because the compiler has the required information contained in the arguments of extract()

The current proposal, unfortunately, makes it very easy to create table programming that will result in very unpleasant situations, because I do not see the way the length can be reliably checked.

Also, a quick look at the examples seem to indicate that a fixed-length header would do just fine for what the authors want to do.

If the varbit field was not extracted from the packet in the first place, it is as easy and a lot safer to add a new fixed-length header and put the proper length into the corresponding length field of the previous header. Nobody on the receiving side cares whether these bits were varbit or not, but it actually creates safer code.

If the varbit field was extracted from the packet, then we have two situations. In the first case, we just want to replace it. Then, it is the same as the previous case, except that you need to invalidate the parsed header with the varbit first. If, on the other hand, you want to replace thee first L bytes of that varbit, then (a) the current proposal doesn't address that :) and (b) it would, again, be a lot safer if that varbit was parsed a little further as a fixed-length header and some other (shorter) varbit, otherwise how do you even know you can rewrite the first L bytes safely.

[jafingerhut]

Vladimir, there was only a little bit of discussion during the meeting about other operations on varbit types, but the one shown in the example program attached above was said by Gordon to be useful enough to justify examining it for whether it needed any extensions to the language spec. It seems that it does not, as the language spec already allows it. Implementations are free to subset or restrict the language spec capabilities, as has been discussed on multiple occasions, and implementers should describe those restrictions in their documentation, ideally.

One of those restrictions could certainly be on lengths. Note that the language spec as written today does not even restrict headers to be multiples of 8 bits long. It explicitly allows implementations to make those restrictions, and most I know of do that, including the open source BMv2 implementation.

I do not understand what you mean by "I do not see the way the length can be reliably checked". When a program is adding a variable-length header to a packet, presumably the control plane is putting the correct length header in there. If the P4 program needs to know its length (that is not necessarily the case for all P4 programs dealing with varbit headers), a separate action parameter populated by the control plane can provide that as a normal bit<W> type value that the P4 program can manipulate in all the usual ways.

Of course, variable length headers may be added by having an N different actions, one for each desired header length, that each add a fixed-length header. In fact, that could be one way to implement the example program by an implementation, "under the covers", i.e. hidden from the P4 programmer. The example program could simply be nicer shorter syntactic sugar that avoid the need for the P4 programmer to go to the extra steps of writing those N actions, and/or writing a Python program that writes those actions for them :-)

[vgurevich]

Andy,

Hmm, you are correct, the language spec doesn't restrict headers to have the lengths that are multiple of 8 bits. Frankly, I feel that this is a serious hole, because it makes it extremely difficult to reason about the program behavior, at least in out byte-oriented world. I feel that it probably makes sense to tighten the spec there.

Obviously, we can, again, say that "it's just the spec and the targets are free to restrict the actual lengths" (which is what the spec says in this case), but I feel that this actually weakens the spec making the programs even less portable (especially since all known targets do have this restriction).

Here's what I mean by "reliably checked". For example, Tofino does have that "restriction" that headers have to have lengths that are multiple of 8 bits. As a result, the compiler actually checks that when you extract a header with a varbit, the requested length is a multiple of 8 bits. At least on Tofino we can do it at compile-time. I am not sure what BMv2 does if you try to extract a varbit that doesn't end on the byte boundary -- it is certainly possible to write such a program for BMv2 -- and what happens when you try to extract a header after that.

Once you allow varbits as action data, then it might also happen that you will have to deparse a header that doesn't end at the byte boundary. That might be more difficult to enforce -- either the compiler will encode the constraints in p4_info or you will have to define what happens if the control plane sets the action parameter incorrectly.

Again, it is possible to say that the behavior will be target-dependent, but I think that this will only make the spec weaker -- one of the better properties of the spec is that it allows us to reason about the program behavior without knowing these "details".

While I agree with you that adding a variable length field might require N different actions in general case, I have a feeling that when you add it, it is usually a known header to begin with.

Given that the frontend seems to allow this anyway, my personal preference would be to allow certain implementations that would like to have this feature to implement it as an extension to the spec. Once the feature proves its safety and usefulness, we can officially put it in the spec (or not) instead of putting it there right away.

[jafingerhut]

The feature as in the attached example program is already legal according to the spec. It compiles using the open source p4test compiler with no errors, and I am not aware of anything in the spec that it violates. Implementations are explicitly allowed to subset the spec.

An implementation that supported this program, but only with particular lengths of varbit fields as action parameters, could enforce it at the control plane API level, returning an error if a wrong length varbit field was attempted to be configured in a table entry.

[jafingerhut]

Also, the variable-length header extract operation in the P4_16 language spec, if it gives a number of bits that the target cannot support, is defined that it may cause a parser error, a new one in version 1.2.0 of the spec named ParserInvalidArgument.

Starting about 6 to 9 months ago, BMv2 checks the second argument to the 2-arg variant of extract, and if it is not a multiple of 8 bits long, it causes that parser error to occur and stops parsing. There is a test case I wrote for p4c, which runs on BMv2 with packets passing through, that verifies this works.

[vgurevich]

@jafingerhut

An implementation that supported this program, but only with particular lengths of varbit fields as action parameters, could enforce it at the control plane API level, returning an error if a wrong length varbit field was attempted to be configured in a table entry.

I agree, but that will require the compiler passing the constraints to p4runtime agent somehow.

[mihaibudiu]

I don't see any actionable items here yet. Perhaps add support to bmv2 for varbit action args?

[gbrebner]

Given Andy's experiment indicating the current front end is good, then BMv2 support would be an obvious follow-up. (I will intend for support being added for one other target.) Aside from that, there is then the matter of P4Runtime support. Distilling the Andy/Vlad discussion above, one would want support for varbit action args for table entries, and this should include target-specific checking for byte-lengthedness if that is a constraint. (I perhaps have an unusual target where byte-style is not necessarily necessary.)

That addresses the initial proposal. If we were to expand into things like constant assignments to varbits and/or varbit assignment to bit, then that would involve further investigation. These are also both in the category of the operation being assignment, nothing fancier than that.

[antoninbas]

Feel free to file an issue against bmv2 for the varbit support. Please provide a P4 program that covers all the use cases you want to support, even if the p4c-bm2-ss compiler cannot yet produce a JSON for it. It is likely that some small changes are required to the JSON format to support varbits (e.g. as action parameters).

[jafingerhut]

@antoninbas There are perhaps two feature additions involved here, at least in the near term:

(a) support varbit types as action parameters, as shown in the attached example program in an earlier comment

(b) if the LDWG discusses it and gets some kind of agreement, supporting assignments between values of type varbit and bit might become useful, too.

If you don't mind keeping (b) for a possible future enhancement request for bmv2, I can open an issue requesting the enhancement (a) now.

[jafingerhut]

I decided to go ahead and create an issue on the behavioral-model repository about item (a) in my previous comment, leaving out whatever might be desired later, until it has been decided upon.

[mihaibudiu]

See also https://github.com/p4lang/p4-spec/pull/883

[jnfoster]

In the interest of tidying up the set of active issues on the P4 specification repository, I'm marking this as "stalled" and closing it. Of course, we can always re-open it in the future if there is interest in resurrecting it.