Bitmap P4 Representation

I was wondering in P4, how are Bitmap lookups typically done/recreated? Would creating a bitstring in metadata in the data plane be a sensible approach? For example, if I wanted a 2^16 long bitmap/bitstring, what would be the recommended way to write the P4 code s.t. I can do index lookups and also set values? Thank you!

Sidenote: Curious how such bitmap lookups will fit in pipeline approaches that have multiple stages. It wouldn’t necessarily count as a match-action so how would such a thing be mapped? Thanks!

A P4 register array is one way to create a bitmap of the size you mention that many target devices can support. They might have restrictions like requiring you to define an array of 2^13 32-bit elements, totaling 2^16 bits, and they might impose restrictions such as only being able to read, modify, and write back one of those 2^13 array elements per “pass” of processing a packet. By “pass” I mean that if the target supports recirculating packets, recirculating a packet gives you another “pass” to process that packet through your P4 code again.

Such a P4 register array would typically be mapped into one processing stage of a Tofino pipeline, for example. I cannot answer for other hardware-based targets off the top of my head.

I will look into registers then thank you! Out of curiosity, what would the effect/feasibility be of just declaring a local bit<2^16> bitmap1 variable in the control apply {} block locally and setting the value/generating the p4 code externally through like a python script? Thank you!

Or maybe what I’m getting at is what makes registers ideal for implementing bitmaps as opposed to just one really long bitstring primitive?

If you declare a local variable with type bit<2^16>, or any local variable, its value is NOT preserved across processing of different packets. The value is initialized fresh on each arriving packet, perhaps to an unspecified value if you do not assign it one to initialize it.

A Register array extern object is defined to preserve its value across the processing of different packets.

Also, I suspect that while a P4 program compiled for a general purpose CPU target (such as BMv2, or the DPDK back end) may support such large bit strings as local variables, most low-cost-per-Tbps devices I am aware of would not have that much memory available to store local variables.

Thank you! I looked around online and couldn’t find any such examples. Is it possible to write to the register/set up its value from the json file similar to how I’m loading in table entries with the same json file like this:

“table”: “MyIngress.ipv4_lpm”,
“match”: {
“hdr.ipv4.dstAddr”: [“”, 32]
“action_name”: “MyIngress.ipv4_forward”,
“action_params”: {
“dstAddr”: “08:00:00:00:03:33”,
“port”: 1

I’m a bit stuck on how I can load the desired 2^16 bits into the register only once during the setup as opposed to setting it everytime a packet arrives - especially from the control plane.

If you are using BMv2, then unfortunately while there is a P4Runtime API mechanism defined to write the values of registers, it has not been fully implemented in an open source implementation. There is a kind of a workaround way to do it with BMv2 by sending a packet from the control plane software into the data plane, and then having the data plane process the packet by writing the register. An example of that technique can be found here: p4-guide/ptf-tests/registeraccess at master · jafingerhut/p4-guide · GitHub

I’ve been fiddling with the solution and I’ve run into an obstacle I can’t seem to find a way around. My situation is now this: I have a 32-bit long variable bit<32> bitmap that is set to some result from a table match. I have another variable that serves as the index into the bitmap that I want to use to retrieve the bit value at that index.

I tried the following:
bitVal = bitmap[meta.index:meta.index] // essentially doing a bit slice of 1 at the position in the bitmap

However, I’m getting a slice bit index values must be constants error that I can’t figure out a solution to. My whole algorithm predicates on logically being able to use a variable index to retrieve a one bit value from a retrieved bitstring. Has this situation come up before?

Some of P4’s restrictions can be a bit annoying at times, yes :-).

One way to work around this restriction is to set a bit j in a 32-bit value using an assignment like:

new_val = old_val | (32w1 << j);

and similarly to clear a bit position j

new_val = old_val & ~(32w1 << j);

I came up with a makeshift solution to extract the bit at position j with bit operations like this:

  1. right shift bitmap by j bits
  2. extract bitslice [0:0]
  3. bitwise AND the result with 1 to see if the desired bit was a 0 or 1

However, now I’m running into another bottleneck. I’m seeing a:
–Werror=overlimit error: >>: shift amount limited to 8 bits on this target

Is there a way to increase the cap? (I’m trying to shift by an 11-bit value)
The only solution I can think of is to “shrink” the 11-bit value into an 8-bit value by dividing by 8 and performing 8 shifts. Would that hypothetically be a solution?

I’m a bit surprised about this error because I believe the maximum bit length for bmv2 is 2048 so I thought a right shift of 11 bits would be the intended max. Thank you!

If you keep the bit vectors down to at most 256 bits wide, then an 8-bit shift value is enough, yes? Is that size of bit vector too small for you for some reason?

Got it to work! Thanks so much. It was an error on my part.