18. P4 abstract machine: Evaluation

The evaluation of a P4 program is done in two stages:

static evaluation: at compile time the P4 program is analyzed and all stateful blocks are instantiated.
dynamic evaluation: at runtime each P4 functional block is executed to completion, in isolation, when it receives control from the architecture

Certain expressions in a P4 program have the property that their value can be determined at compile time. Moreover, for some of these expressions, their value can be determined only using information in the current scope. We call these compile-time known values and local compile-time known values respectively.

The following are local compile-time known values:

Integer literals, Boolean literals, and string literals.
Identifiers declared as constants using the const keyword.
Identifiers declared in an error, enum, or match_kind declaration.
The default identifier.
The size field of a value with type header stack.
The _ identifier when used as a select expression label
The expression {#} representing an invalid header or header union value.
Instances constructed by instance declarations (Section [#sec-instantiations]) and constructor invocations.
Identifiers that represent declared types, actions, functions, tables, parsers, controls, or packages.
Tuple expression where all components are local compile-time known values.
Structure-valued expressions, where all fields are local compile-time known values.
Expressions evaluating to a list type, where all elements are local compile-time known values.
Legal casts applied to local compile-time known values.
The following expressions (+, -, |+|, |-|, *, /, %, !, &, |, ^, &&, ||, <<, >>, ~, /, >, <, ==, !=, <=, >=, ++, [:], ?:) when their operands are all local compile-time known values.
Expressions of the form e.minSizeInBits(), e.minSizeInBytes(), e.maxSizeInBits() and e.maxSizeInBytes() where the type of e is not generic.

The following are compile-time known values:

All local compile-time known values.
Constructor parameters (i.e., the declared parameters for a parser, control, etc.)
Tuple expression where all components are compile-time known values.
Expressions evaluating to a list type, where all elements are compile-time known values.
Structure-valued expressions, where all fields are compile-time known values.
Expressions evaluating to a list type, where all elements are compile-time known values.
Legal casts applied to compile-time known values.
The following expressions (+, -, |+|, |-|, *, /, %, cast, !, &, |, ^, &&, ||, <<, >>, ~, /, >, <, ==, !=, <=, >=, ++, [:], ?:) when their operands are all compile-time known values.
Expressions of the form e.minSizeInBits(), e.minSizeInBytes(), e.maxSizeInBits() and e.maxSizeInBytes() where the the type of e is generic.

Intuitively, the main difference between compile-time known values and local compile-time known values is that the former also contains constructor parameters. The distinction is important when it comes to defining the meaning of features like types. For example, in the type bit<e>, the expression e must be a local compile-time known value. Suppose instead that e were a constructor parameter—i.e., merely a compile-time known value. In this situation, it would be impossible to resolve bit<e> to a concrete type using purely local information—we would have to wait until the constructor was instantiated and the value of e known.

Evaluation of a program proceeds in order of declarations, starting in the top-level namespace:

All declarations (e.g., parsers, controls, types, constants) evaluate to themselves.
Each table evaluates to a table instance.
Constructor invocations evaluate to stateful objects of the corresponding type. For this purpose, all constructor arguments are evaluated recursively and bound to the constructor parameters. Constructor arguments must be compile-time known values. The order of evaluation of the constructor arguments should be unimportant — all evaluation orders should produce the same results.
Instantiations evaluate to named stateful objects.
The instantiation of a parser or control block recursively evaluates all stateful instantiations declared in the block.
The result of the program’s evaluation is the value of the top-level main variable.

Note that all stateful values are instantiated at compilation time.

As an example, consider the following program fragment:
Begin P4Example // architecture declaration parser P(/* parameters omitted /); control C(/ parameters omitted /); control D(/ parameters omitted */);

package Switch(P prs, C ctrl, D dep);

extern Checksum16 { /* body omitted */}

// user code Checksum16() ck16; // checksum unit instance

parser TopParser(/* parameters omitted /)(Checksum16 unit) { / body omitted /} control Pipe(/ parameters omitted /) { / body omitted /} control TopDeparser(/ parameters omitted /)(Checksum16 unit) { / body omitted */}

Switch(TopParser(ck16), Pipe(), TopDeparser(ck16)) main; \~ End P4Example

The evaluation of this program proceeds as follows:

The declarations of P, C, D, Switch, and Checksum16 all evaluate to themselves.
The Checksum16() ck16 instantiation is evaluated and it produces an object named ck16 with type Checksum16.
The declarations for TopParser, Pipe, and TopDeparser evaluate as themselves.
The main variable instantiation is evaluated:
The arguments to the constructor are evaluated recursively
TopParser(ck16) is a constructor invocation 1. Its argument is evaluated recursively; it evaluates to the ck16 object
The constructor itself is evaluated, leading to the instantiation of an object of type TopParser
Similarly, Pipe() and TopDeparser(ck16) are evaluated as constructor calls.
All the arguments of the Switch package constructor have been evaluated (they are an instance of TopParser, an instance of Pipe, and an instance of TopDeparser). Their signatures are matched with the Switch declaration.
Finally, the Switch constructor can be evaluated. The result is an instance of the Switch package (that contains a TopParser named prs the first parameter of the Switch; a Pipe named ctrl; and a TopDeparser named dep).
The result of the program evaluation is the value of the main variable, which is the above instance of the Switch package.

Figure [#fig-compileeval] shows the result of the evaluation in a graphical form. The result is always a graph of instances. There is only one instance of Checksum16, called ck16, shared between the TopParser and TopDeparser. Whether this is possible is architecture-dependent. Specific target compilers may require distinct checksum units to be used in distinct blocks.

\~ Figure { #fig-compileeval; caption: “Evaluation result.” } [compileeval] \~ [compileeval]: figs/compileeval.png { width: 5cm; page-align: here }

Every controllable entity exposed in a P4 program must be assigned a unique, fully-qualified name, which the control plane may use to interact with that entity. The following entities are controllable.

value sets
tables
keys
actions
extern instances

A fully qualified name consists of the local name of a controllable entity prepended with the fully qualified name of its enclosing namespace. Hence, the following program constructs, which enclose controllable entities, must themselves have unique, fully-qualified names.

control instances
parser instances

Evaluation may create multiple instances from one type, each of which must have a unique, fully-qualified name.

Computing control-plane names

The fully-qualified name of a construct is derived by concatenating the fully-qualified name of its enclosing construct with its local name. Constructs with no enclosing namespace, i.e. those defined at the global scope, have the same local and fully-qualified names. The local names of controllable entities and enclosing constructs are derived from the syntax of a P4 program as follows.

Value sets

For each value_set construct, its syntactic name becomes the local name of the value set. For example:

\~ Begin P4Example struct vsk_t { @match(ternary) bit\<16> port; } value_set(4) pvs; \~ End P4Example

This value_set’s local name is pvs.

Tables

For each table construct, its syntactic name becomes the local name of the table. For example:

\~ Begin P4Example control c(/* parameters omitted /)() { table t { / body omitted */ } } \~ End P4Example

This table’s local name is t.

Keys

Syntactically, table keys are expressions. For simple expressions, the local key name can be generated from the expression itself; the algorithm by which a compiler derives control-plane names for complex key expressions is target-dependent.

The spec suggests, but does not mandate, the following algorithm for generating names for some kinds of key expressions:

Kind	Example	Name
The `isValid()` method.	`h.isValid()`	`"h.isValid()"`
Array accesses.	`header_stack[1]`	`"header_stack[1]"`
Constants.	`1`	`"1"`
Field projections.	`data.f1`	`"data.f1"`
Slices.	`f1[3:0]`	`"f1[3:0]"`
Masks.	`h.src & 0xFFFF`	`"h.src & 0xFFFF"`

In the following example, the previous algorithm would derive for table t two keys with names data.f1 and hdrs[3].f2.

\~ Begin P4Example table t { keys = { data.f1 : exact; hdrs[3].f2 : exact; } actions = { /* body omitted */ } } \~ End P4Example

If a compiler cannot generate a name for a key it requires the key expression to be annotated with a @name annotation (Section [#sec-control-plane-api-annotations]), as in the following example:

\~ Begin P4Example table t { keys = { data.f1 + 1 : exact @name(“f1_mask”); } actions = { /* body omitted */ } } \~ End P4Example

Here, the @name("f1_mask") annotation assigns the local name "f1_mask" to this key.

Actions

For each action construct, its syntactic name is the local name of the action. For example:

\~ Begin P4Example control c(/* parameters omitted /)() { action a(…) { / body omitted */ } } \~ End P4Example

This action’s local name is a.

Instances

The local names of extern, parser, and control instances are derived based on how the instance is used. If the instance is bound to a name, that name becomes its local control plane name. For example, if control C is declared as,

\~ Begin P4Example control C(/* parameters omitted /)() { / body omitted */ } \~ End P4Example

and instantiated as,
Begin P4Example C() c_inst;

End P4Example

then the local name of the instance is c_inst.

Alternatively, if the instance is created as an actual argument, then its local name is the name of the formal parameter to which it will be bound. For example, if extern E and control C are declared as,

\~ Begin P4Example extern E { /* body omitted / } control C( / parameters omitted / )(E e_in) { / body omitted */ } \~ End P4Example

and instantiated as,
Begin P4Example C(E()) c_inst;

End P4Example

then the local name of the extern instance is e_in.

If the construct being instantiated is passed as an argument to a package, the instance name is derived from the user-supplied type definition when possible. In the following example, the local name of the instance of MyC is c, and the local name of the extern is e2, not e1.

\~ Begin P4Example extern E { /* body omitted */ } control ArchC(E e1); package Arch(ArchC c);

control MyC(E e2)() { /* body omitted */ } Arch(MyC()) main; \~ End P4Example

Note that in this example, the architecture will supply an instance of the extern when it applies the instance of MyC passed to the Arch package. The fully-qualified name of that instance is main.c.e2.

Next, consider a larger example that demonstrates name generation when there are multiple instances.

\~ Begin P4Example control Callee() { table t { /* body omitted */ } apply { t.apply(); } } control Caller() { Callee() c1; Callee() c2; apply { c1.apply(); c2.apply(); } } control Simple(); package Top(Simple s); Top(Caller()) main; \~ End P4Example

The compile-time evaluation of this program produces the structure in Figure [#fig-evalmultiple]. Notice that there are two instances of the table t. These instances must both be exposed to the control plane. To name an object in this hierarchy, one uses a path composed of the names of containing instances. In this case, the two tables have names s.c1.t and s.c2.t, where s is the name of the argument to the package instantiation, which is derived from the name of its corresponding formal parameter.

\~ Figure { #fig-evalmultiple; caption: “Evaluating a program that has several instantiations of the same component.” } [evalmultiple] \~ [evalmultiple]: figs/evalmultiple.png { width: 5cm; page-align: here }

Annotations controlling naming

Control plane-related annotations (Section [#sec-control-plane-api-annotations]) can alter the names exposed to the control plane in the following ways.

The @hidden annotation hides a controllable entity from the control plane. This is the only case in which a controllable entity is not required to have a unique, fully-qualified name.
The @name annotation may be used to change the local name of a controllable entity.

Programs that yield the same fully-qualified name for two different controllable entities are invalid.

Recommendations

The control plane may refer to a controllable entity by a postfix of its fully qualified name when it is unambiguous in the context in which it is used. Consider the following example.

\~ Begin P4Example control c( /* parameters omitted / )() { action a ( / parameters omitted / ) { / body omitted / } table t { keys = { / body omitted */ } actions = { a; } } } c() c_inst; \~ End P4Example

Control plane software may refer to action c_inst.a as a when inserting rules into table c_inst.t, because it is clear from the definition of the table which action a refers to.

Not all unambiguous postfix shortcuts are recommended. For instance, consider the first example in Section [#sec-cp-names]. One might be tempted to refer to s.c1 simply as c1, as no other instance named c1 appears in the program. However, this leads to a brittle program since future modifications can never introduce an instance named c1, or include libraries of P4 code that contain instances with that name.

The dynamic evaluation of a P4 program is orchestrated by the architecture model. Each architecture model needs to specify the order and the conditions under which the various P4 component programs are dynamically executed. For example, in the Simple Switch example from Section [#sec-vss-arch] the execution flow goes Parser->Pipe->Deparser.

Once a P4 execution block is invoked its execution proceeds until termination according to the semantics defined in this document.

Concurrency model

A typical packet processing system needs to execute multiple simultaneous logical “threads.” At the very least there is a thread executing the control plane, which can modify the contents of the tables. Architecture specifications should describe in detail the interactions between the control-plane and the data-plane. The data plane can exchange information with the control plane through extern function and method calls. Moreover, high-throughput packet-processing systems may be processing multiple packets simultaneously, e.g., in a pipelined fashion, or concurrently parsing a first packet while performing match-action operations on a second packet. This section specifies the semantics of P4 programs with respect to such concurrent executions.

Each top-level parser or control block is executed as a separate thread when invoked by the architecture. All the parameters of the block and all local variables are thread-local—i.e., each thread has a private copy of these resources. This applies to the packet_in and packet_out parameters of parsers and deparsers.

As long as a P4 block uses only thread-local storage (e.g., metadata, packet headers, local variables), its behavior in the presence of concurrency is identical with the behavior in isolation, since any interleaving of statements from different threads must produce the same output.

In contrast, extern blocks instantiated by a P4 program are global, shared across all threads. If extern blocks mediate access to state (e.g., counters, registers)—i.e., the methods of the extern block read and write state, these stateful operations are subject to data races. P4 mandates that execution of a method call on an extern instance is atomic.

To allow users to express atomic execution of larger code blocks, P4 provides an @atomic annotation, which can be applied to block statements, parser states, control blocks, or whole parsers.

Consider the following example:
Begin P4Example extern Register { /* body omitted / } control Ingress() { Register() r; table flowlet { / read state of r in an action / } table new_flowlet { / write state of r in an action */ } apply { @atomic { flowlet.apply(); if (ingress_metadata.flow_ipg > FLOWLET_INACTIVE_TIMEOUT) new_flowlet.apply(); }}}

End P4Example

This program accesses an extern object r of type Register in actions invoked from tables flowlet (reading) and new_flowlet (writing). Without the @atomic annotation these two operations would not execute atomically: a second packet may read the state of r before the first packet had a chance to update it.

Note that even within an action definition, if the action does something like reading a register, modifying it, and writing it back, in a way that only the modified value should be visible to the next packet, then, to guarantee correct execution in all cases, that portion of the action definition should be enclosed within a block annotated with @atomic.

A compiler backend must reject a program containing @atomic blocks if it cannot implement the atomic execution of the instruction sequence. In such cases, the compiler should provide reasonable diagnostics.