Session

Protocol parsing is perhaps the most common and performance sensitive operation in a networking stack. Every packet received on a network interface needs to be parsed for a variety of purposes, and hence there is a great deal of motivation to build parsers that are highly efficient and programmable to handle a wide variety of protocols. However, protocol parsing is notoriously difficult since it is inherently serialized processing, the number of protocol elements can be combinatorial, and the input to the parser is nondeterministic and sometimes even has malevolent intent (aka a Dos attack). In this paper we will delve into both the theory and implementation of programmable parsers that run with the highest performance in a given target environment. The implementation focus will be on software based parsers, however the techniques can be extrapolated for mapping to hardware implementation.

In the first part of the paper, we will describe protocol parsing as a Finite State Machine (FSM). First we’ll provide the basic FSM with the minimum required operations to do a protocol parse walk, next we’ll add annotations to nodes to perform useful work in the form of metadata extraction and protocol handler functions, and finally we’ll add the constructs to the FSM to parser TLVs (Type Length Value commonly used for options in protocols) and flag-fields (like in GRE).

In the second part of the paper, we’ll describe a declarative representation of a protocol parser with its Finite State Machine. We’ll show how all of the required operations of protocol parsing along with metadata extraction can be represented with a set of parameterized functions. With that we will show how the set of parameterizations can be encoded in a .json schema, so that a .json file thus provides a complete declarative representation of a parser. We will show how the .json representation can serve as the formal Intermediate Representation (IP) for a parser.

In the final section we will apply these concepts to implement high performance programmable parsers. A ubiquitous parser IR facilitates a variety of front end methods to program a parser (PANDA-C, PANDA-Python, P4, etc.), as well as a variety of back end targets (eBPF, DPDK, kParser, hardware offloads, etc.). We’ll look at an example parser called “big-parser” that is a superset of Linux flow-dissector functionality. We’ll start with the PANDA-C code for big-parser, show its compilation into its .json IR, and then show how the IR can be compiled into kParser and optimized eBPF targets for running in the kernel. We provide performance evaluation of “big-parser” running in this targets versus Linux kernel flow-dissector (both native kernel flow-dissector and one written in eBOF).