Abstract
This article is a low-level tutorial explaining why and how to write your own Google Protocol Buffer (protobuf) deserializer using the C programming language. Using the techniques discussed here, you can write your own code to supplant or replace the code generated via protobuf-c or Nanopb. This tutorial is specific to Farsight Security’s nmsg package. If you write C code that deals with NMSGs, or directly with protobufs, this article is for you.
Before reading this article, it is recommended that you read the Farsight Security Blog series on NMSG with specific attention to Farsight’s Network Message, Volume 3: Headers and Encoding.
Counting NMSG Payloads
Farsight Security has a simple use case in which we need to count the number of payloads in on-wire NMSG containers. The environment this needs to be done is our real-time SIE switch fabric, which, in aggregate, has extremely high bit rates.
Farsight solved this problem by rolling our own protobuf deserializer. We
think the concept and overall process to be useful to our peers and customers.
As such, we extracted the code from our production tool and wrapped it into a
standalone program named nmsgpcnt-fsi. Also included for benchmarking are
two reference implementations, nmsgpcnt-npb and nmsgpcnt-ptc which are
written using popular open source C-based protobuf implementations.
All three tools accomplish the same thing. Each parses on-disk NMSG protobufs and counts the number of containers and total number of payloads. They differ mainly in two areas, code complexity and speed of execution.
Why In The World Would You Do This?
The reason we wrote this low-level code when it would be much easier to use a
generated API is singular: speed of execution. As you’ll see, nmsgpcnt-fsi,
is quite a bit faster than the other two benchmark programs. Our protagonist,
nmsgpcnt-fsi should be faster — it is purpose-built to perform very specific
operations on protobufs. The protobuf code generators are designed to be
multipurpose and support a wide range of operations across many different data
types. As such, for many operations on protobufs, there are calls to
malloc(), memcpy(), and free(). nmsgpcnt-fsi has none of these.
Because of this, the comparison between nmsgpcnt-fsi and the other two
is definitely skewed in favor of nmsgpcnt-fsi.
nmsgpcnt-npb and nmsgpcnt-ptc
The first reference program ,nmsgpcnt-npb, is built using Nanopb, a C-based
protobuf implementation with a “small code size”. Targeted for embedded systems
and 32-bit microcontrollers, Nanopb touts minimal requirements for RAM and
code space. While there are no malloc()/free() calls during
deserialization, some speed has been sacrificed for code size. This will be
clearly shown in our tests below.
The second reference program, nmsgpcnt-ptc, is built using protobuf-c, a
feature-rich pure C protobuf implementation.
The source code complexity for both is relatively low.
Both programs are invoked identically, with a single file argument referring to
a binary NMSG file. For benchmarking, we’ll use a large NMSG file containing
just over 2,000,000 payloads as captured using
nmsgtool on Farsight Security’s Passive DNS feed on
SIE Channel 202.
$ nmsgpcnt-npb
nmsgpcnt-npb parse an NMSG file and emit container/payload count
usage: ./nmsgpcnt-npb file.nmsg
$ ./nmsgpcnt-npb 202-2000000.nmsg
containers: 720
payloads: 2000481
$ ./nmsgpcnt-ptc 202-2000000.nmsg
containers: 720
payloads: 2000481
nmsgpcnt-fsi
nmsgpcnt-fsi is the Farsight Security in-house built protobuf deserializer.
It follows the same overall logic as the other two but the code is quite a bit
larger and more complex. This is because nmsgpcnt-fsi has no external
dependencies and carries with it exactly and only the code it needs to decode
an NMSG protobuf and count each payload.
The workhorse in nmsgpcnt is the decode_pb() function. It is responsible
for deserializing and parsing the NMSG container and processing Nmsg
fields. The function is about as fast as it can be. It iterates over an NMSG
container and populates a passed-by-referenced structure. It does no memory
allocation or deallocation, no memory copies, and has just four possible
branches.
Disclaimer: while nmsgpcnt-fsi is faster than its contemporaries, the source
code is more than twice the size and more tedious to read, write, and
maintain. Also, the very nature of dealing with code that operates at the
bit-level practically invites mistakes and requires a lot of testing. Caveat
emptor.
Benchmarking NMSG Payload Counting
Included with the
nmsgpcnt distribution is a shell script test.sh that executes and times all three
programs, displaying the results. You can see the crosswalk below:
$ ./test.sh 202-2000000.nmsg
Running nmsgpcnt-npb (nanopb) against 202-2000000.nmsg
containers: 720
payloads: 2000481
real 2.31
user 1.84
sys 0.47
Running nmsgpcnt-ptc (protoc-c) against 202-2000000.nmsg
containers: 720
payloads: 2000481
real 1.47
user 0.97
sys 0.49
Running nmsgpcnt-fsi (Farsight Security) against 202-2000000.nmsg
containers: 720
payloads: 2000481
real 0.59
user 0.15
sys 0.44
The nmsgpcnt-fsi program is more than twice as fast as the protobuf-c
variant, and almost five times faster than the Nanopb version. In production,
this translates into faster processing of NMSG datagrams and lower packet loss.
nmsgpcnt-fsi source
The following is a discussion of the full nmsgpcnt-fsi C source code
with in-line annotations.
The full source code, including the code for the other benchmark programs, is available for download from Farsight Security’s blog-code GitHub page here.
Preamble
The first section contains the source code license and the standard C header file include progression:
/*
* Copyright (c) 2015 by Farsight Security, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <sys/stat.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdbool.h>
#include "./common.h"
Define Protobuf Symbolic Constants
The following symbolic constants are defined for convenience and code clarity.
/* protocol buffer constants */
#define PB_WIRETYPE_MASK 7 /* AND mask to get wire type bits */
#define PB_WT_VI 0 /* wire type: varint */
#define PB_WT_64 1 /* wire type: 64-bit */
#define PB_WT_LD 2 /* wire type: length delimited */
#define PB_WT_32 5 /* wire type: 32-bit */
/* protocol buffer Nmsg field numbers */
#define PB_NMSG_PAYLOAD 1 /* payload */
#define PB_NMSG_PAYLOAD_CRC 2 /* payload CRC */
#define PB_NMSG_SEQSRC 3 /* sequence source */
#define PB_NMSG_SEQID 4 /* sequence ID */
Define Varint Decoder
All of the magic performed below is done using C’s bitwise operators. If you’re not already, you’ll want to get familiar with them and with how protobufs are encoded. You also might find interesting this discussion of varints and accompanying C++ code from which the following was inspired.
The CHNM_DCDE_VARINT() macro decodes an unsigned varint. It has the following
arguments:
- shifter: Used to shift decoded bits into their correct position.
- buf: The buffer containing the stream of protobuf bytes.
- val: An accumulator that will contain the decoded value.
- idx: The index into buf.
With varint encoding, the lower 7 bits of each byte are used to store the two’s complement representation of the number in groups of 7 bits, least significant group first. The most significant bit is used as a sentinel value to let the decoder know if more bytes are coming.
The macro works by iterating over protobuf bytes in buf, decoding each byte
and iteratively storing the result in val. It strips the most significant
bits from each byte and accumulates them in val. It does this until
buf[idx] & 0x80 evaluates to false, which means it has decoded the last
byte in the varint. To see why this is true, recall the following:
- Most significant bit set: More bytes to come.
- Most significant bit cleared: No more bytes to come.
Finally, CHNM_DCDE_VARINT() is declared as a macro in order to ensure the
code is placed inline and obviate the overhead a function call would require.
/* decode a varint and stick results in val */
#define CHNM_DCDE_VARINT(shifter, buf, val, idx) \
shifter = 0, val = 0; \
do \
{ \
idx++; \
val |= (buf[idx] & 0x7F) << shifter; \
shifter += 7; \
} \
while (buf[idx] & 0x80); \
Define NMSG Protobuf Data type
The following opaque structure is used to hold data about an NMSG container.
For the use case in this article, nmsgpcnt-fsi is only concerned about the
number of payloads, but it can be extended by adding additional members to
nmsg_pb_data_t and adding more decoding logic to decode_pb().
/* holds results of protobuf deserialization */
struct nmsg_pb_data
{
uint32_t n_payloads; /* number of payloads */
};
typedef struct nmsg_pb_data nmsg_pb_data_t;
Define The Decoder
The function that does the decoding is defined here. The workflow is here straightforward.
- An outer loop walks the entire contents of the protobuf.
- The current byte is logically ANDed with the
PB_WIRETYPE_MASKwhich masks off the protobuf wire type bits. This value is used to branch from in the switch table. - Depending on the wire type, the appropriate action is taken. Here,
nmsgpcnt-fsionly cares about wire typePB_WT_LDwith a field number of1. This heralds the start of an NMSG payload. The payload counter is incremented and the length of payload is decoded (which itself is a varint encoded value). The payload bytes are stepped over and control passes back to the top of the loop.
Sidebar: The switch table makes extending the decoder to understand other NMSG protobuf fields quite easy. In fact this code is actually part of a larger, more extensible framework used inside Farsight for programs that need to get at other parts of the NMSG protobuf beyond an ordinal payload count.
int
decode_pb(const uint8_t *pb_data, uint32_t len, nmsg_pb_data_t *nmsg_data)
{
int idx;
uint8_t wire_type;
uint64_t i, j;
uint64_t shifter;
memset(nmsg_data, 0, sizeof (*nmsg_data));
i = 0;
idx = 0;
while (i < len)
{
/*
* Each key in the streamed message is a varint with the value
* (field_number << 3) | wire_type.
*
* To decode a protobuf byte, AND off the lower 3 bits
* (GPB_WIRETYPE_MASK) to get the wire type. From there, right
* shift by 3 to get the field number.
*
* For an NMSG protobuf, the field numbers are:
*
* message Nmsg
* {
* repeated NmsgPayload payloads = 1;
* repeated uint32 payload_crcs = 2;
* optional uint32 sequence = 3;
* optional uint64 sequence_id = 4;
* }
*
* And the protobuf wiretypes are:
*
* 0 Varint PB_WT_VI
* 1 64-bit PB_WT_64
* 2 length (payload) PB_WT_LD
* 5 32-bit PB_WT_32
*/
wire_type = pb_data[i] & PB_WIRETYPE_MASK;
switch (wire_type)
{
case PB_WT_VI:
CHNM_DCDE_VARINT(shifter, pb_data, j, i);
i++;
break;
case PB_WT_64:
/* next byte has the 64-bit value; skip both */
i += 9;
break;
case PB_WT_LD:
if ((pb_data[i] >> 3) == PB_NMSG_PAYLOAD)
{
/* field number 1 == payload */
nmsg_data->n_payloads++;
}
CHNM_DCDE_VARINT(shifter, pb_data, j, i);
/* skip over payload bytes */
i += j;
i++;
break;
case PB_WT_32:
/* next byte has the 32-bit value; skip both */
i += 5;
break;
default:
/* unknown wire type */
/* bad NMSG payload, possibly malfunctioning hardware? */
return -1;
}
}
return 1;
}
Main Entry Point
Here is the main entry point into the program. The only notable bit here
is the load_container() function (contained in common.c). It is responsible
for the following:
- Open the NMSG file specified at the command line.
- Figure out how big it is.
- Allocate enough memory to hold its contents.
- Read contents into memory.
- Return a buffer containing the NMSG container.
A successful call to load_container() needs to be balanced with a
subsequent corresponding call to free().
int main(int argc, char **argv)
{
ssize_t n;
uint32_t payloads, processed, containers;
uint8_t *buf = NULL;
if (argc != 2)
{
printf("%s parse an NMSG file and emit container/payload count\n",
argv[0]);
printf("usage: %s file.nmsg\n", argv[0]);
return EXIT_FAILURE;
}
buf = load_container(argv[1], &n);
if (buf == NULL)
{
return EXIT_FAILURE;
}
Loop over Containers
Next is the main event loop. An NMSG can have one or more containers (that each can have zero or more payloads). The program iterates over conntainers and serially processes each one.
/* loop through file, processing as many containers as we find */
for (containers = payloads = processed = 0; processed < n; )
{
uint32_t c_len;
uint8_t *p = NULL, version, flags;
nmsg_pb_data_t nmsg_data;
p = buf + processed;
Process NMSG Header
Before nmsgpcnt-fsi can decode a protobuf, it needs to first do some header
verification. If any of the following checks fail, the program breaks from the
event loop and exits.
- Confirm the NMSG magic number in the header.
- Confirm the NMSG protocol version (is
2). - Confirm the container does not contain compressed payloads.
- Confirm the container does not contain fragmented payloads.
- Get the length of the container.
The NMSG header is now processed and nmsgpcnt-fsi is ready to decode the
container itself.
/* confirm NMSG header */
if (CHECK_MAGIC(p) != 0)
{
fprintf(stderr, "NMSG header verification failed\n");
break;
}
/* step over magic */
p += 4;
/* load version and flags */
LOAD_VERSION_AND_FLAGS(p, version, flags);
/* confirm NMSG protocol version */
if (version != 2U)
{
fprintf(stderr, "NMSG version check failed\n");
break;
}
/* we don't process compressed payloads */
if (flags & NMSG_FLAG_ZLIB)
{
fprintf(stderr, "NMSG container contains compressed payloads\n");
break;
}
/* we don't process fragmented payloads */
if (flags & NMSG_FLAG_FRAGMENT)
{
fprintf(stderr, "NMSG container contains fragmented payloads\n");
break;
}
/* step over version/flags */
p += 2;
/* get container length */
c_len = ntohl(*((uint32_t* )(p)));
/* step over length */
p += 4;
Decode the Protobuf
Next the decoder is run. If no errors are encountered, the container and payload counters are incremented and control returns to the top of the event loop.
/* deserialize the protobuf encoded container */
if (decode_pb(p, c_len, &nmsg_data) < 0)
{
fprintf(stderr, "error: can't parse NMSG payload\n");
break;
}
containers++;
processed += c_len + 10;
payloads += nmsg_data.n_payloads;
}
Wrap up and Shutdown
After all of the containers are exhausted the totals are emitted to stdout.
Next, the memory held by buf is released and the program exits.
printf("containers:\t%d\n", containers);
printf("payloads:\t%d\n", payloads);
if (buf)
{
free(buf);
}
return 0;
}
Mike Schiffman is a Packet Esotericist for Farsight Security, Inc.
