#include <push_pop.h>

Inheritance diagram for HeaderPushPop:

Additional Inherited Members
Public Types inherited from P4::Visitor
typedef Visitor_Context	Context

Public Member Functions inherited from P4::Transform
const IR::Node *	apply_visitor (const IR::Node , const char name=0) override

profile_t	init_apply (const IR::Node *root) override

virtual void	loop_revisit (const IR::Node *)

virtual const IR::Node *	postorder (IR::Node *n)

virtual const IR::Node *	preorder (IR::Node *n)

void	prune ()

virtual void	revisit (const IR::Node , const IR::Node )

void	revisit_visited ()

bool	visit_in_progress (const IR::Node *) const

void	visitAgain () const override

void	visitOnce () const override

Public Member Functions inherited from P4::Visitor
virtual bool	check_global (cstring)

virtual void	clear_globals ()

virtual Visitor *	clone () const

virtual ControlFlowVisitor *	controlFlowVisitor ()

virtual void	end_apply ()

virtual void	end_apply (const IR::Node *root)

virtual void	erase_global (cstring)

template<class T >
const T *	findContext () const

template<class T >
const T *	findContext (const Context *&c) const

template<class T >
const T *	findOrigCtxt () const

template<class T >
const T *	findOrigCtxt (const Context *&c) const

virtual Visitor &	flow_clone ()

virtual void	flow_merge (Visitor &)

virtual bool	flow_merge_closure (Visitor &)

virtual void	flow_merge_global_from (cstring)

virtual void	flow_merge_global_to (cstring)

const Context *	getChildContext () const

int	getChildrenVisited () const

const Context *	getContext () const

int	getContextDepth () const

const IR::Node *	getCurrentNode () const

template<class T >
const T *	getCurrentNode () const

const IR::Node *	getOriginal () const

template<class T >
const T *	getOriginal () const

template<class T >
const T *	getParent () const

virtual bool	has_flow_joins () const

profile_t	init_apply (const IR::Node root, const Context parent_context)

bool	isInContext (const IR::Node *n) const

virtual const char *	name () const

template<class T >
void	parallel_visit (const IR::Vector< T > &v, const char *name, int cidx)

template<class T >
void	parallel_visit (const IR::Vector< T > &v, const char *name=0)

template<class T >
void	parallel_visit (IR::Vector< T > &v, const char *name, int cidx)

template<class T >
void	parallel_visit (IR::Vector< T > &v, const char *name=0)

void	print_context () const

const Visitor &	setCalledBy (const Visitor *visitor)

void	setName (const char *name)

void	visit (const IR::Node &n, const char *name, int cidx)

void	visit (const IR::Node &n, const char *name=0)

void	visit (const IR::Node &n, const char name, int cidx)

void	visit (const IR::Node &n, const char name=0)

void	visit (const IR::Node const &n, const char name, int cidx)

void	visit (const IR::Node const &n, const char name=0)

void	visit (IR::Node &n, const char *name, int cidx)

void	visit (IR::Node &n, const char *name=0)

void	visit (IR::Node &, const char =0, int=0)

template<class T , typename = std::enable_if_t<Util::has_SourceInfo_v<T> && !std::is_pointer_v<T>>, class... Args>
void	warn (const int kind, const char *format, const T &node, Args &&...args)
	The const ref variant of the above.

template<class T , typename = std::enable_if_t<Util::has_SourceInfo_v<T>>, class... Args>
void	warn (const int kind, const char format, const T node, Args &&...args)

bool	warning_enabled (int warning_kind) const

Static Public Member Functions inherited from P4::Visitor
static cstring	demangle (const char *)

static bool	warning_enabled (const Visitor *visitor, int warning_kind)

Public Attributes inherited from P4::Visitor
const Visitor *	called_by = nullptr

cstring	internalName

SplitFlowVisit_base *&	split_link

SplitFlowVisit_base *	split_link_mem = nullptr

Protected Member Functions inherited from P4::Transform
const IR::Node *	transform_child (const IR::Node *child)

Protected Member Functions inherited from P4::Visitor
virtual void	init_join_flows (const IR::Node *)

virtual bool	join_flows (const IR::Node *)

virtual void	post_join_flows (const IR::Node , const IR::Node )

void	visit_children (const IR::Node *, std::function< void()> fn)

Protected Attributes inherited from P4::Transform
bool	forceClone = false

Protected Attributes inherited from P4::Visitor
bool	dontForwardChildrenBeforePreorder = false

bool	joinFlows = false

bool	visitDagOnce = true

Detailed Description

Lowers push_front and pop_front primitives to a sequence of modify_field primitives that perform the work.

To understand how these primitives are implemented, it's important to understand the data structure that's used for header stack POV bits. A header stack's POV bits are organized in a sequential layout within a single container, as follows (in little-endian order):

[ push bits ] [ entry 0 POV bit, entry 1 POV bit, ...] [ pop bits ]

There is one POV bit per header stack entry. These bits are set to indicate that a specific entry is valid. When the program writes to a specific header stack index, we update the corresponding bit. The bits are also used in the deparser to decide which entries should be written into the output packet. In other words, when you access a specific header stack entry, the POV bits behave just as if they were the POV bits for a group of unrelated headers.

When the program executes a push_front or pop_front primitive, we need to shift all the entries over to make room for new values. These primitives don't actually set any new values, though; they just make room. They could just as well be called shift_forward or shift_back.

The contents of the entries are shifted by copying each field from its old position to its new position with modify_field. The POV bits also need to be shifted, and that's what the "push bits" and "pop bits" are for. The push bits are all set to 1 (that happens in the parser; see the StackPushShims pass) and the pop bits are all set to 0.

When you push, modify_field copies from the header stack POV container to the same container. Consider the what happens when we execute push_front(header_stack, 2):

                   [  SOURCE ]

[ 1 1 .. push bits .. 1 1 ] [ 1 0 0 0 ] [ 0 0 .. pop bits .. 0 0 ] [DEST ]

The four bits labeled SOURCE - two 1's from the push bits, the 1 from entry 0's POV bit, and the 0 from entry 1's POV bit - are copied over the four entry POV bits, labeled DEST. Before the copy, only entry 0's POV bit was set; after the copy, the POV bits for entry 0, 1, and 2 are set - we've pushed two new, valid (because we'll immediate write to them) entries into the header stack. In other words, the entry POV bits now look like this:

[ 1 1 1 0 ]

It should be obvious that this will work correctly regardless of the existing values of the entry POV bits. We just need to ensure that we have enough push bits for the largest push_front operation we'll execute (that's why we compute the maxpush and maxpop values) and that we overwrite all of the existing entry POV bits when we do the update.

The situation is analogous for pop_front(header_stack, 3):

                                 [  SOURCE ]

[ 1 1 .. push bits .. 1 1 ] [ 1 1 1 1 ] [ 0 0 0 .. pop bits .. 0 0 ] [DEST ]

Here we're still overwriting all of the entry POV bits (labelled DEST). Since we're popping three entries, we take three 0's from the pop bits and use only a single entry POV bit, which is set to 1. The resulting entry POV bits:

[ 1 0 0 0 ]

That's just what we'd expect after popping three entries.

When writing the code to implement this, the layout is very important. The MakeSlice calls below accept bit indices in little endian order, but the push bits need to be positioned adjacent to the POV bit for the first entry, and the pop bits need to be positioned adjacent to the POV bit for the last entry. That means that as things stand, the container bit indices will be ordered like this (though the specific indices will depend on the size of the header stack, maxpush, and maxpop):

[ push bits ] [ entry 0 POV bit, entry 1 POV bit] [ pop bits ] 5 4 3 2 1 0

The numbering for the header stack entry POV bits moves in the opposite direction from the numbering of the bits in the container!

In the code, we name the field containing the push bits for header_stack header_stack.$push. The pop bits are in header_stack.$pop. The entries are in header_stack[0].$valid and so forth. A special field header_stack.$stkvalid is overlaid over the entire sequence of bits so that they can be referred to as a unit, and in practice we often manipulate the other fields by writing to that one.

Additional Inherited Members

Detailed Description