c 2013 AsiaBSDCon 2013 Organizing Committee. All rights reserved.
Copyright !
Unauthorized republication is prohibited.
Published in Japan, March 2013

5

6

7

8

OpenIKED
Reyk Floeter (reyk@openbsd.org)
February 2013
Abstract
This paper introduces the OpenIKED project[14],the latest portable subproject of OpenBSD[13].
OpenIKED is a FREE implementation of the most advanced Internet security Internet Key Exchange version 2 (IKEv2) Virtual Private Network (VPN) protocol using the strongest security, authentication andencryption techniques. The project was born in needof a modern Internet Protocol Security (IPsec) implementation for OpenBSD, but also for interoperability
with the integrated IKEv2 client since Windows 7 andto provide a compliant solution for the US Government
IPv6 (USGv6) standard. The project is still under active development; it was started by Reyk Floeter as
iked for OpenBSD in 2010 but ported to other platforms including Linux, FreeBSD and NetBSD in late2012 using the OpenIKED project name.

history and my personal motivation of creating
it. It is inteded to provide some complementary
information for my talk at AsiaBSDCon 2013 .
The project aims to provide a free implementation of the Internet Key Exchange (IKEv2) protocol
which performs mutual authentication and which
establishes and maintains IPsec VPN security policies
and Security Associations (SAs) between peers.
The IKEv2 protocol is de ned in Request for Comments (RFC) 5996, which combines and updates theprevious standards: Internet Security Association and
Key Management Protocol (ISAKMP)/Oakley (RFC
2408[8]), Internet Key Exchange version 1 (IKE)(RFC 2409[3]), and the Internet DOI (RFC 2407[17]).
OpenIKED only supports the IKEv2 protocol; support for ISAKMP/Oakley and IKE is provided by
OpenBSD s isakmpd(8) or other implementations on
non-OpenBSD platforms.
It is intended to be a lean, clean, secure, better congurable and interoperable implementation that focusses on supporting the main standards and mostimportant features of IKEv2. I primarily wrote
OpenIKED with signi cant contributions from Mike
Belopuhov and various contributing OpenBSD hackers.
OpenIKED is developed as part of the OpenBSD
Project. The software is freely usable and re-usable byeveryone under an Internet Systems Consortium (ISC)
license. The OpenBSD project sells CDs, T-Shirts andPosters. Sales of these items help to fund development.

2 Background & History
2.1 Why another VPN protocol?

1 Introduction
This paper provides a brief description of the
OpenIKED project, including technical background,

There are a number of free implementations of VPN
protocols available that can provide a su cient security for private network connections. But these protocols and implementations have di erent use cases,
limitations, bene ts, and drawbacks. Most of them
are specialized in one aspect but cannot provide a solution in another area.

9

10

11

12

13

14

The autoconf framework and compatibility librarythat is based OpenSSH s portable version made it surprisingly easy to port OpenIKED to Linux.
A drawback is the fact that the Linux kernel developers invented their own non-standard XFRM kernel API that is intended to replace PFKEYv2, whichis considered to be obsolete. The PFKEYv2 interface still exists but is poorly maintained and lacks
some features, like working support for HMAC-SHA2256 HMAC authentication for IPsec. Linux originallyadded HMAC-SHA2-256 support based on the prestandard speci cation with a truncation length of 96
bits that is incompatible to the standard length of
128 bits that is described in RFC 4868[6]. PFKEYv2
uses pre-de ned identi ers and attributes for algorithms, e.g. SADB X AALG SHA2 256 for HMAC-SHA2256 with 128 bits truncation. The Linux kernel recognizes the SADB X AALG SHA2 256 identi er but assumes 96 bits truncation. The kernel developers neverxed this obvious bug to keep compatibility with
one or two other implementations that use the prestandard version. They refer to the XFRM API thatallows to set the algorithm, and the key and truncation
lengths individually.

spired by the Windows client. Accordingly, the goal
is to provide a very simple tool that allows to set up
IKEv2 client connections from Mac-based road warriors. The dynamic negotiation of IKEv2 and the secure defaults of OpenIKED allows to reduce the required con guration settings to the minimum on theclient side: remote gateway address and optional connection name. Other optional settings can be con gured in the Details tab. In di erence to the Windows client, additional user-based authentication iscurrently not supported as EAP-based authenticationis only implemented for the server (responder) side.
The current version is a working proof of conceptthat requires manual installation of keys and certi cates into the con guration directory.

4.4 User-friendly GUI
There is actually no need to use a GUI to set up gateway to gateway connections. The con guration le,iked.conf, uses a well-de ned grammar that is easy
to understand for system administrators and mostusers of OpenIKED . But when connecting mobile
users, or road warriors, to the gateway, an easy GUI
is an important requirement for deploying the VPN.
These users are most commonly non-technical laptop
users that connect to a VPN gateway of their organization, university or company. It is most desirable
that they can set up and debug the client-side of the
VPN connection without much interaction from theIT department.
Microsoft Windows
Microsoft Windows 7 introduced an integrated IKEv2
client con guration dialog that is surprisingly easy touse for standard users. The con guration of traditional IPsec/IKE used to be very di cult under Windows but the IKEv2 client only requires installing therequired certi cates, setting the remote gateway address, and specifying a user name and password for
additional EAP-MSCHAPv2 authentication. And ofcourse, OpenIKED is a compatible gateway that canbe used with the built-in Windows client.
OpenIKED.app
To get a similar level of IKEv2 user-friendliness on
OS X, I started working on a simple GUI that is in-

4.5 The Artwork
OpenBSD and its subprojects aren t just known for
security, they re also known for their comic-style artwork. Each of these projects has a theme that isincluding the OpenBSD-styled logo and Pu y thepu er sh in some action. The artwork is used on TShirts, posters and CD covers and was originally designed by the Canadian artist Ty Semaka and someother artists today.

When I decided to turn iked into a portable project,
it was clear that I needed a matching artwork. I had
the idea of using a tin can telephone as a theme that
represents VPN communication in an obscure way.

15

16

NPF in NetBSD 6
S.P.Zeidler !spz@NetBSD.org"
The NetBSD Foundation

Mindaugas Rasiukevicius !rmind@NetBSD.org"
The NetBSD Foundation

Abstract
NPF has been released with NetBSD 6.0 as an experimental packet filter, and thus has started to see actualuse. While it is going to take a few more cycles before
it is fully ”production ready”, the exposure to users has
given it a strong push to usability. Fixing small bugs
and user interface intuitivity misses will help to evolve itfrom a theoretical well-designed framework to a practicalpacket filtering choice. The talk will cover distinguishing features of NPF design, give an overview of NPF’s
current practical capabilities, ongoing development, andwill attempt to entice more people to try out NPF andgive feedback.

1

Introduction

NPF is a layer 3 packet filter, supporting IPv4 and IPv6,
as well as layer 4 protocols such as TCP, UDP and
ICMP/IPv6-ICMP. NPF offers the traditional set of features provided by most packet filters. This includes stateful packet filtering, network address translation (NAT),
tables (using a hash or tree as a container), rule procedures for easy development of NPF extensions (e.g.
packet normalisation and logging), connection saving
and restoring as well as other features. NPF focuses onhigh performance design, ability to handle a large volume of clients and using the speed of multi-core systems.
Various new features were developed since NetBSD
6.0 was released, and the upcoming 6.1 release will haveconsiderable differences regarding their user interface
and to a certain level regarding its capabilities.

2

What’s special about NPF?

Inspired by the Berkeley Packet Filter (BPF), NPF uses
”n-code”, which is conceptually a byte-code processor,
similar to machine code. Each rule is described by a sequence of low level operations, called ”n-code”, to per-form for a packet. This design has the advantage of protocol independence, therefore support for new protocols(for example, layer 7) or custom filtering patterns can beeasily added at userspace level without any modifications
to the kernel itself.
NPF provides rule procedures as the main interface touse custom extensions. The syntax of the configuration
file supports arbitrary procedures with their parameters,
as supplied by the extensions. An extensions consists of
two parts: a dynamic module (.so file) supplementing thenpfctl(8) utility and a kernel module (.kmod file). Thus,
kernel interfaces can be used instead of modifications to
the NPF core code.
The internals of NPF are abstracted into well definedmodules and follow strict interfacing principles to easeextensibility. Communication between userspace and thekernel is provided through the library libnpf, describedin the npf(3) manual page. It can be conveniently usedby developers who create their own extensions or third
party products based on NPF. Application-level gateways(ALGs), such as support for traceroute(8), are also abstracted in separate modules.

2.1

Designed for SMP and high throughput

NPF has been designed so its data structures can use
lockless methods where suitable and fine-grained locking in general. 1
Ruleset inspection is lockless. It uses passive serialization as a protection mechanism. The reload of a ruleset is atomic with minimum impact on the active ruleset,
i.e. the rule processing is not blocked during the reload.
NPF rules can be nested, which is useful for grouping
1 For the initial NPF release, some components are using read-write
locks, although they could be lockless using a passive serialization interface. Since this interface was new in NetBSD 6.0, a conservative
approach was taken. As of 6.1, those components have been converted
to be lockless.

17and chaining based on certain filtering patterns. Currently, the configuragion file syntax supports two levelsof groups (having per-interface and traffic direction options), however there is no limitation in the kernel andsyntax expansion is planned. As of NetBSD 6.1, dynamic NPF rules will be supported.
Efficient data structures were chosen for the connection (session) tracking mechanism: a hash table withbuckets formed of red-black trees. The hash table provides distribution of locks which are protecting the trees,
thus reducing lock and cacheline contention. The tree
itself provides efficient lookup time in case of hash collision and, more importantly, prevents algorithmic complexity attacks on the hash table i.e. its worst case behaviour.
The session structure is relatively protocol-agnostic.
The IPv4 or IPv6 addresses are used as the first set of
IDs forming a key. The second set of IDs are generic.
Depending on the protocol, they are filled either withport numbers in the TCP/UDP case or with ICMP
IDs. It should be noted that the interface is also partof the key, as is the protocol. Therefore, a full key
for a typical TCP connection would be formed from:SRC IP:SRC PORT:DST IP:DST PORT:PROTO:IFACE.
This key is a unique identifier of a session.
Structures carrying information about NAT and/or rule
procedures are associated with the sessions and follow
their life-cycle.
NPF provides efficient storage for large volumes of IP
addresses. They can be stored in a hash table or in a Patricia radix tree. The latter also allows to specify address
ranges.

2.2

Modular design

NPF is modular, each component has its own abstracted
interface. This makes writing NPF extensions easy. It
also allows easy addition of filtering capabilities for layer
4 and higher. The implementer of a network protocol
does not need to know anything about the internals of
packet collection and disposal facilities. Services suchas connection tracking are provided by a strict interface- other components may consider it as a black box.
The NPF extensions API will be fully provided with
the NetBSD 6.1 release. Extensions consist of kernel
modules and userland modules implemented as dynamically loadable libraries for npfctl, the NPF control utility. Extensions get configured as rule procedures and applied on the selected packets. They can take arguments
in a key-value form. Extensions may rewrite packet contents (e.g. fields in the header) and influence their fate(block/pass).
There is a demo extension: the kernel part inandsrc/sys/net/npf/npf ext rndblock.c

18

src/lib/npf/ext rndblock/npfext rndblock.c
for npfctl. This extension simulates packet loss. The
kernel part file is less than 180 lines long, the npfctl partis less than 100. Given that the copyright notice is asignificant part of that, the ’administrative overhead’ fora NPF extension is fairly low.

3

What can it do, at present?

The configuration file syntax is still avoiding to be Turing
complete. In spite of the obvious temptation, it is planned
to keep it that way. The config syntax has changed noticeably between what was released with NetBSD 6.0,
and what will be in NetBSD 6.1. Further change is expected (of course, only to the better).
As mentioned, NPF is a stateful packet filter for IP (v4and v6) and layer 4 - TCP, UDP, ICMP and ICMPv6,
including filtering for ports, TCP states, ICMP types andcodes are currently implemented.
Configuration example:
pass in family inet proto tcp \from $nicehost to $me port ssh
Rules get processed top to bottom as they are written
in the config file, first through the interface specific groupand then through the default group. Processing can be
stopped early by using the tag final in a rule.
Addresses for filtering can be inferred from what isconfigured on an interface (own addresses), can be configured in the npf.conf configuration file, or can be fed
into (and deleted from) tables defined in npf.conf using
npfctl table commands.
NPF sidesteps the fragments issues by reassembling
packets before further processing.
NPF supports various address and port translation
variants. In NetBSD 6.0.x, it supports network address port translation (”masquerading”), port forwarding(”redirection”) and bi-directional NAT in IPv4. Thereis an application-level gateway (ALG) for traceroute and
ICMP translation; ALGs are provided as kernel modules.
NetBSD 6.0 configuration example:# outgoing NAPT
map $ext_if dynamic 198.51.100.0/24 -> \$ext_if# port forwarding
map $ext_if dynamic 198.51.100.2 port 22 \<- $ext_if 9022
Session state (including NAT state) can be dumped tofile in a serialised form.

Packet normalization and logging are available since
the NetBSD 6.0 release. From 6.1 onwards, they will
be provided as NPF extensions. They get configured asprocedures:# procedure to log a packet and# decrease its MSS to 1200 if higher
procedure "maxmss_log" {log: npflog0
normalise: "max-mss" 1200}
# in an interface group, apply the# procedure to matching packets:
pass out family inet proto tcp flags S/SA \to $pmtublackholed apply "maxmss_log"# continue to further processing
Rule reload builds a new configuration in the kernel,
and switches from new to old atomically. NPF does nothold several configurations in the kernel to switch between. Instead, support for a temporary load with a timer
and automatic rollback is planned.

4

Testing and debugging

As a good citizen of NetBSD, NPF has regression tests inthe automated tests framework. These are implemented
using the RUMP (Runnable Userspace Meta Programs)
framework, which allows to exercise the kernel elementsof NPF in userspace, without having to boot a test kernel(even in a VM). Regular tools like gdb can be used fordebugging. Unit tests are implemented and available via
the npftest program. Additionally, the program can loada custom configuration file and process packets from apcap file. This allows developers to analyse NPF decisions and state tracking in userspace using a captured
sample. As a result, debugging the problems experienced
in other environments is easier.
Another debugging help is the npfctl debug option,
which dumps the internal representation of a parsed config, as npfctl would have sent to the kernel, i.e. as disassembled n-code.

5

Meeting users

The NetBSD 6.0 configuration file syntax uses one label
for a network interface, the addresses configured on thatinterface and the addresses configured for a specific address family on an interface; the meaning was inferredfrom context. This turned out to be hard to understandfor humans (even if the software interpreted it just fine)
and was changed for NetBSD 6.1 to explicitly require afunction that takes the interface name as an argument,

e.g. inet($interface) for all addresses configured on$interface.
Even before NetBSD 6.0 was shipped, the syntax expressing address and port translations was reworked touse map. It is bound to an interface, the crossing of which
triggers the translation. By convention, the ”inside” network and optional port definition is on the left-hand side,and the ”outside” on the right side on the arrow that discerns the translation direction. This makes configurations easier to read (for the current sample of users).
Users also saw cosmetic issues that were previously
missed, like printing garbage for linklocal scope for
npfctl show.
Further improvement will be necessary in giving useful error messages for syntax problems in the configuration file. Getting feedback from users is very importantto get NPF production ready, to oust the last small bugs
and help identify the most desireable missing bits.

6

Whereto, my lovely?

NPF is still a moving target - there have been major changes and feature additions recently. Although
the core APIs of NPF are becoming stable, they arestill subject to extensions and minor changes. Therefore, when developing 3rd party extensions, it is recommended to follow source-changes@NetBSD.org since”catching up” with the changes might be necessary.
NPF will also use BPF byte-code (first available in
NetBSD 6.1), and BPF with just-in-time (JIT) compilation likely in NetBSD 7.0. In combination with thewidely used pcap(3) library, it provides the ability towrite sophisticated filtering criteria in an easy, expressive
and very efficient way that is familiar to users.
A GSoC 2012 project produced patches for simplecase NPT66 (/48 only) and NAT64 (well-known prefixonly). However, these still need to be expanded and integrated, and are therefore unlikely to make it into NetBSD
6.1 due to ”free time” constraints.
Further extensions are likely to arrive. Possible examples would be extensions for port knocking, traffic accounting and connection rate limiting.
Given interest, addition of further layer 4 protocols is
likely.
Finally, NPF has design provisions to eventually enable active-passive and active-active firewall clusters; notimeline for implementing this exists yet.

19

20

21

22

23

24

25

26

27

28

29

 (  "     #  )           !       %&  '&    %&    *     + *  (   %&  ')%&   ,)%&              
  ' "#   +   

30

31

32

33

34

Perfect(ing) hashing in NetBSD
Jörg Sonnenberger
March 16, 2013

Abstract

trees at the cost of logarithmic complexity for mostoperations. The other alternative is deploying ranHash tables are one of the fundamental data struc- domised hash functions.
tures used in the different parts of an Operating
Randomised hash functions are also the buildSystem from on-disk databases to directory caches ing block for more powerful hash table schemes:in the kernel. To provide the desired performance perfect hash functions. A Perfect Hash Function
characteristics, keeping the collision rate minimal (PHF) is constructed in such a way, that any two
is crucial. If the construction of the hash function keys of a known input set are mapped to different
guarantees that no collisions occur, it is a Perfect indices, i.e. that no hash collisions can exist. ThisHash Function. This paper gives a short introduc- makes them a perfect match for applications with ation into the algorithms developed in the last 20 (mostly) fixed key set. If the PHF also maps the nyears for this task. It looks at the uses in NetBSD keys to 0..n − 1, it is called a Minimal Perfect Hash
6 like nbperf and the constant database cdb as well Function (MPHF). The most well known program
as work-in-progress code for routing and firewalling. for creating PHF and MPHF is GNU gperf. It has
been used for the keyword recognition in compilers
like GCC.
1 Introduction
This paper introduces the important developmentsin this area of research since 1990. As pracHash tables are data structures used to implement
ticalapplications
the nbperf program in NetBSD
associative arrays, i.e. they provide a mapping ofarbitrary complex keys to values or indices. They 6 is presented as well the new constant databaseare one of the oldest data structures for this pur- cdb. An outlook to further work for using perfectpose and since their discovery in 1953, they have hashing in the routing table and in NPF is also
been studied extensively and can be found in many presented.
programs and libraries. The wide spread use is a
result of the SMP friendliness and efficiency as ideNew algorithms for Perfectally, inserts, lookups and removals are all constant 2
time operations.
Hash Functions
The core of every hash table implementation is
the hash function. Typical examples are using the This section looks at the early algorithms for PHF
remainder of the division by a prime or Bernstein’s construction and challenges faced. It introduces thestring hash h(x[0..n]) = 33 × h(x[0..n − 1]) + x[n] most noticable modern algorithms developed sincewith h(0) = 53811 . All simple hash functions share 1990 and how they work.
one important property: certain input keys are
The best algorithmic choice for a specific applimapped to the same index. This is called a hash cation depends on a number of common factors:
collision and requires special handling. Techniques• Does the hash function preserve the key order?
for dealing with them include linked lists between
If it does, integration is easier as the existingelements with the same hash, repeating the hashtable structures can be reused and the hashing with an additional counter as argument to findfunction works as additional secondary index.
a different position or resizing the hash table.
In the last years, a number of so-called com• How much space does the hash function needs
plexity attacks[5] have been published where an atper key?
tacker explicitly creates hash collisions to force thetarget to waste time by slowing down the opera• What computations are needed for the hashtions from expected constant time to linear in thefunction?
number of keys. One way to address the complexity attacks is to move from hash tables to balanced• If the algorithm constructs a non-minimal
1 This hash is also known as DJBX33A.
PHF, what key density can it achieve?

35Comparing the individual properties and weight- vertices (for some c ≥ 1). Each edge is createding them according the specific needs results in the by taking the value of the chosen hash functions
correct choice.
modulo m. If the graph is acyclic, the algorithm
continues. Otherwise, another try is made with a
2.1 Systematic construction of Per- different choice of random hash functions. If theconstant c is chosen correctly, the graph is acyclic
fect Hash Functions until 1990
with a very high probability. When using two hashDifferent authors have investigated construction functions, c must be at least 2. When using threemechanisms for Perfect Hash Functions since the hash functions, c must be at least 1.24.
The second concept by Czech et al. is to continue
invention of the hash table. Bostic published thebyassigning a number to every vertex, so that thepredecessor of GNU gperf around 1984. Knuth discussed examples in The Art Of Computer Program- key number corresponding to each edge is the sum
ming. A beautiful construction can be found in of the vertices of the edge modulo m. The initial
Pearson’s paper ”Fast Hashing of Variable-Length value of all vertices is 0. An edge is chosen, sothat one of the vertices has a degree of one. WithText Strings” from 1990[7].
It is based on an 8-bit permutation table and tra- out such an edge, the graph would contain a cyclic.
versed according to the XOR combination of the Subsequently the value of the other vertex is uplast hash value and the current input character. dated, so that the edge fulfills the desired sum and
The design looks very similiar to the RC4 stream ci- the edge is removed afterwards.
The result requires storing m integers between 0pher. Pearson’s paper explicitly discusses ways tosystematically search for a permutation, but also and n − 1 as well as the parameters for the chothe limitations. A trivial case of a problematic in- sen random hash functions. It is the best known
put is given where the target range has to be shifted construction for order-preserving MPHF. The reto produce a MPHF and it can be easily seen that sult hash function takes the compution of the two
the algorithm doesn’t scale very well with the num- (three) chosen random hash functions, a modulo
operation for each, two (three) table lookups, sumber of keys.
The (lack of) scalability of the construction ming up the results and computing another modmechanism is a fundamental issue of the early ap- ulo. The modulo operation itself can be replaced
proaches. If they work, they tend to provide very by two multiplications by computing the inverse.
fast and moderately compact hash functions. For The storage requirement is at least m log2 n, but
key sets larger than a few dozen keys at most, typically m$log2 n% bits per key.
the construction will generally fail or require exponential construction time. For this reason, per2.3 Botelho, Pagh and Ziviani’s Perfect hashing hasn’t been deployed but for compiler
fect Hash Functions
construction for a long time.
The BPZ construction was published in 2007[1] and2.2 Czech, Havas and Majewski’s is very similar to the CHM algorithm. The main
Minimal Perfect Hash Functions difference is the way numbers are assigned to thevertices. For BPZ, each edge is represented by one
The CHM construction was published in 1992[2]. It of its vertices. The sum of the corresponding numis one of the earliest, if not the earliest, expected lin- bers modulo 2 (3) gives the representative. As suchear time algorithm for the construction of MPHFs. the resulting hash function is not minimal by itExpected linear time in this case means that the al- self. At the same time, it requires much less space.
gorithm uses randomised graphs with certain prop- When using three independent random hash funcerties and try again, if a specific choice doesn’t fit. tions, a value between 0 and 2 must be stored for
Each run of the algorithm takes linear time and the all m vertices. One simple encoding stores five suchchance of requiring more than one run is very low. values per byte (35 = 243 < 256). Using c = 1.24,
The resulting hash function has the useful prop- this requires 1.24 × n × 8/5 1.98 bit storage per key
erty of being order preserving. This means that the with 24entries.
hash function preserves the input order by mapping
To obtain a MPHF, some post-processing is
the n-th key is mapped to n − 1. In practise this needed. The PHF can be reduced to a MPHF usmakes the hash function very easy to fit into exist- ing a counting function. This function returns foring code as e.g. tables mapping actions to handlers a given index k how many ”holes” the PHF has undon’t have to be reordered to fit the hash.
til k. This can be represented as bit vector with
The algorithm depends one two central concepts. partial results ever so often memorised to keep the
The first concept is the creation of a random graph O(1) computation time. Careful choices require two
by using two or more independent random hash additional table lookups and one 64 bit population
functions. This graph has n edges and m = cn count with a storage requirement of approximatily

36

Algorithm Tries Run time in s
CHM
1
0.58
CHM3
39
0.85
BPZ
11
0.51
2.4 Belazzougui, Botelho and Dietzweb2a CHM
12
0.35
CHM3
7
0.17
felbinger’s Perfect Hash FuncBPZ
18
0.16
tions
The resulting code for CHM can be seen in list”Hash, displace, and compress” or sort CHD was ing 1
published in 2009[3] and is currently the algorithm
The “mi vector hash” function provides anknown to create the smallest PHF. Using three ran- endian-neutral version of the Jenkin’s hashdom hash functions, a PHF can be constructed with function[4]. The third argument is the chosen seed.
1.4 bit storage per key. The construction itself and The modulo operations are normally replaced by
the resulting hash function is a lot more compli- two multiplications by the compiler.
cated than BPZ though, so no further details will
At the time of writing, two applications in
be provided.
NetBSD use nbperf. The first user was the newterminfo library in NetBSD 6 and uses it for the
key word list of tic. The second example is apropos, which contains a stop word list (i.e. words to3 nbperf
be filtered from the query). This list is indexed bynbperf was started in 2009 to provide a replacement a Perfect Hash Function.
Further work for nbperf includes investigatingfor GNU gperf that can deal with large key sets.
2
simpler
random hash function families to provide
cmph was investigated for this purpose, but bothresultswithperformance characteristics similar tothe license and the implementation didn’t fit into
the NetBSD world. nbperf currently implements GNU gperf’s hashes. An implementation of thethe CHM algorithm for 2-graphs and 3-graphs as CHD algorithm is also planned.
well as the BPZ algorithm for 3-graphs. CHD
wasn’t available when the work on nbperf started
4 The
NetBSD
constant
and hasn’t been implemented yet.
The output of nbperf is a single function thatdatabase
maps a pointer and size to the potential table entry.
It does not validate the entry to avoid duplicating NetBSD used the Berkeley Database to provide
the keys or adding requirements on the data layout. indexed access for a number of performance senIf the callee of the hash function already knows that sitive interfaces. This includes lookups for user
it has a valid key, it would also add overhead for no names, user IDs, services and devices. The Berkeley Database has a number of limitations for thisreason.
The most important option for nbperf is the de- applications, which opened up the question of how
sired construction algorithm. This affects the size to address these:and performance of the hash function. Hash func• Lack of atomic transactions,tions using CHM are much larger. The 2-graph2.79 bits per key using three random hash functions.

version requires two memory accesses, the 3-graphversion three. The actual cache foot print depends
on the number of keys as the size of the entries in
the internal data array depends on that. For BPZ,
the entries are much smaller, but some additional
overhead is needed to provide a minimal hash function. As mentioned earlier, CHM is easier to use inapplications, since it preserves the key order.
The following test case uses the Webster’s Second
International dictionary as shipped with NetBSD
and the shorter secondary word list. They contain234977 and 76205 lines. Each line is interpreted as
one input key. nbperf is run with the ”-p” option to
get repeatable results. The ”tries” column lists thenumber of iterations the program needed to find ausable random graph.
2 http://cmph.sourceforge.net

Input
web2

• Database size overhead,• Code complexity,• Userland caching on a per-application base,
The first item ensures that most use cases in thesystem deploy a copy-on-write scheme for the (rare)case of modifications. It also means that any program has to be able to regenerate the database content after a disk crash.
The second item matters for embedded systems
as it limits what database can be shipped pre-built.
The third item is somewhat related, if the disk image doesn’t require write support, it still can’t leave
the relevant code out.
The last item increases the memory foot print
and reduces sharing data. It also adds overhead for37

Listing 1: CHM example
1#include < s t d l i b . h>2

uint32 thash ( const void ∗r e s t r i c t key , s i z e t k e y l e n ){s t a t i c const u i n t 3 2 t g [ 4 6 9 9 5 5 ] = {/∗ . . . ∗/};uint32 t h [ 3 ] ;

3
4
5
6
7
8
9
10

m i v e c t o r h a s h ( key , k e y l e n , 0 x00000000U , h ) ;1112

return ( g [ h [ 0 ] % 4 6 9 9 5 5 ] + g [ h [ 1 ] % 4 6 9 9 5 5 ] ) % 2 3 4 9 7 7 ;

13

}

14

multi-threaded applications as the library has to
avoid concurrent access to the internal block cache.
NetBSD has imported SQLite, which provides ahigher level library including transaction support.
This doesn’t help with the items above, especiallythe third. A new library was created to complement
SQLite: the constant database. This format provides a read-only storage layer with deterministic
access time, lock-free operation and based on memory mapped files to fully utilize the kernel cache.
The constant database (CDB) consists of twoparts. The first part is the value storage, allowing access to each record using the record number. It can be used to iterate over the content
or to link entries together. The second part provides a Perfect Hash Function for additional key
based access. The keys are not stored on disk, so
the application is responsible for doing any validation. For most file formats, the key is part is of therecord anyway and especially when using multiple
keys for the same record, storing would increase thefile size without justification. Key lookup requires
one computation of mi vector hash for the given
key and reading three locations in the on-disk hashdescription. Worst case is thus three page faults
with loading the blocks from disk. That gives theindex and one more access the actual data offset.
The result is a pointer, size pair directly into thememory mapped area. Looking up the same key
twice therefore doesn’t result in any additional IO
nor does it require any traps, unless the system is
low on memory.
In terms of code complexity, the CDB reader
adds about 1.6KB to libc on AMD64 and writer
around 4.3KB. As the database files are often thesame size or smaller than the corresponding text
sources, dropping the text versions can result in an
overall decrease in size.
For NetBSD 6 the device database, the service
database and libterminfo use the new CDB format.

38

The resulting databases are typically less than one
fourth of the size of the corresponding Berkeley DB
files. The creation time has also improved. Further
work is required to convert the remaining users in
libc, but also to provide access in other programs
like Postfix.

5

Perfect hashingroute lookup

for

the

Cleaning up the routing code and investigating new
data structures and/or implementations is on-goingwork in NetBSD. David Young provided the firstmajor part for this by isolating access to the radix
tree and hiding it behind a clean interface. The
pending work moves the preference selecting (i.e.
which of two routes with the same netmask is chosen) and the special case of host routes out of theradix tree into the generic layer. This changes willallow replacing the old BSD radix tree with lessgeneric, but faster code. It also makes it possible toswitch the lookup data structure for the fast path.
The most interesting alternatives are compressed
tries[6] (out of the scope of this paper) and multilevel hashing[8]. Multi-level hashing is based on
the idea of performing the CIDR3 lookup as binary
search on the possible prefix lengths. For IPv4, this
could mean starting with looking for /16 routes anddepending on match or not, continue with /8 or/24 entries. This requires adding markers for more
specific routes to direct the search.
Considerthefollowing

3 Classless Inter-Domain Routing

routing

table:Destination network Gateway
0/0
192.168.0.10
127/8
127.0.0.1
192.168.0/24
192.168.0.2
192.168.1/24
192.168.0.1
10/8
192.168.0.1
10.0.10/24
192.168.0.5
10.192/12
192.168.0.6
11.192/12
192.168.0.7
A search for 10.0.10.1 will start by looking for10.0/16 in the hash table to be constructed. No
such route exists, but the search has to continue
with larger prefix length to find the correct entry
10.0.10/24. For this purpose, a marker has to be
added with entry 10.0/16 and a reference to 10/8.
The reference avoids the need for backtracking, i.e.
when searching for 10.0.11.1. They can either reference the covering route or copy the corresponding gateway, depending on the granularity of traffic
accounting. With the additional marker entries,
the following content of the hash table is enough:Destination network Type Data
0/0
GW
192.168.0.10
127/8
GW
127.0.0.1
192.168/16
R
0.0.0.0/0
192.168.0/24
GW
192.168.0.2
192.168.1/24
GW
192.168.0.1
10/8GW
192.168.0.1
10.0/16R
10/8
10.0.10/24
GW
192.168.0.5
10.192/12
GW
192.168.0.6
11/8
R
0/0
11.192/12
GW
192.168.0.7
For this specific case, three additional entries areenough as the marker for 10.192/12 is 10/8 andthat’s already present as route. Using perfect hashing ensures a predictable lookup cost as it limits thenumber of expensive memory accesses. Using the
BPZ algorithm with a 2-graph and no post-filteringmeans a hash table utilisation of 50% and approximately 2 bit per key storage for the hash function
itself. It is possible to use a single hash table for all
entries or to use a /separate table for each prefix
length. The latter allows using 64 bit per entry incase of IPv4 (32 bit network, 32 bit as the next-hop
identifier) and between 64 bit and 160 bit for IPv6.
Even for a core router in the Default Free Zone,
100,000 entries and more fit into the L3 cache ofmodern CPU.
The downside of using perfect hashing is the construction time. Investigations have to be performedon how critical the resulting update time is for busy
routers.
Further optimisations can be deployed. The optimal branching is often not a static binary search,so storing hints for the next level to look at can be
useful. Published research by Waldvogel et al. suggests that the average number of hash table probes

can be much less than 2, when chosing the correct
order. The lookup table itself can avoid redundant
entries, i.e. if a more specific router and the immediate covered route have the same next-hop. Thisimplies less precise accounting though.

6

Summary

Algorithms like CHM, BPZ and CHD provide afast, practical construction of Perfect Hash Functions. This makes it possible to use them in different fields from performance critical read-mostly
data structures, like the routing tables, to size sensitive on-disk databases. NetBSD 6 is the first BSD
to use them in the real world and more areas will
be covered in the future.
Areas for open research and practical implementations outlined in this paper include finishing theimplementation in the network stack and finding
fast simple random hash functions to replace theremaining use cases of GNU gperf.

References[1] F. C. Botelho, R. Pagh, and N. Ziviani. Simple
and space-efficient minimal perfect hash functions. In In Proc. of the 10th Intl. Workshop on
Data Structures and Algorithms, pages 139–150.
Springer LNCS, 2007.
[2] Z. J. Czech, G. Havas, and B. S. Majewski. An
optimal algorithm for generating minimal perfect hash functions. Information Processing Letters, 43:257–264, 1992.
[3] F. Botelho D. Belazzougui and M. Dietzfelbinger. Hash, displace, and compress. In Algorithms – ESA, pages 682–693, 2009.
[4] B. Jenkin. Hash functions. Dr. Dobbs Journal,
September 1997.
[5] A. Klink and J. Wälde. Efficient denial of service attacks on web application platforms, 2011.
[6] S. Nilsson and G. Karlsson. IP-Address lookup
using LC-tries, 1998.
[7] P. Pearson. Fast hashing of variable-length text
strings. Communications of the ACM, 33:677–
680, June 1990.
[8] M. Waldvogel, G. Varghese, J. Turner, and
B. Plattner. Scalable high speed ip routing
lookups. In Proc. ACM SIGCOMM, pages 25–
35, 1997.

39

40

The bhyve Operator's Manual
Michael Dexter
AsiaBSDCon 2013
OVERVIEW
bhyve is a legacy-free Type-2 hypervisor for FreeBSD that was imported into the mainline
FreeBSD development repository in January of 2013 with svn revision r245652. A hypervisor
allow for the operation of one or more guest operating systems within a host operating system.
As a legacy-free hypervisor, a bhyve host requires the Extended Page Tables (EPT) featurefound on "Nehalem" and newer generations of Intel processors. This requirement eliminates theneed for memory management routines that are traditionally implemented in software and yields
virtually bare metal guest performance. A bhyve guest requires VirtIO network and blockdevices, which were already available in FreeBSD 8-STABLE, 9-STABLE and 10-CURRENT
at the time of bhyve's import. If these two requirements are satisfied, the bhyve host and guests
will operate in the established FreeBSD manner.
HARDWARE REQUIREMENTS
The presence of the Extended Page Table (EPT) feature can be determined by examining thehost's demesg(8) output for the presence of the POPCNT (POP Count) feature as the two arecoupled but not related. Established dynamic memory and storage requirements apply otherwise
with the caveat that there is a 1:1 relationship between the deduction of dynamic memory fromthe host and its allocation to guests.
SOFTWARE REQUIREMENTS
A FreeBSD 10-CURRENT system from svn revision r245652 onward will include all of thenecessary bhyve host components: the vmm(4) kernel module, the libvmmapi library and thebhyveload(8), bhvye(8) and bhyvectl(8) utilities.
A suitable FreeBSD 8-STABLE, 9-STABLE or 10-CURRENT guest can exist in a disk image or
any valid storage device and only requires a modified /etc/ttys entry to work. All otheroptions can be specified at runtime at the loader prompt. Permanent configuration changes
however are generally desired and will be demonstrated.
Permanent /etc/ttys configuration (can be appended):console "/usr/libexec/getty std.9600"

vt100

on secure41

Boot time or permanent /etc/fstab configuration for a MBR-partitioned device:# Device/dev/vtbd0s1a

Mountpoint/

FStypeufs

Options
rw

Dump
1

Pass#
1

FStypeufs

Options
rw

Dump
1

Pass#
1

or for a GPT-partitioned device:# Device/dev/vtbd0p1

Mountpoint/

Example runtime or permanent /etc/rc.conf networking configuration:
ifconfig_vtnet0="DHCP"

Depending on how your guest is built, the /boot/loader.conf may require:virtio_load="YES"
if_vtnet_load="YES"
virtio_pci_load="YES"
virtio_blk_load="YES"BHYVE OPERATION
At a minimum, a bhyve host requires that the vmm.ko kernel module be loaded:su kldload vmm

To enable guest networking, load the if_tap.ko kernel module and create a tap(4) interface(tap0 on em0 as an example):su kldload if_tap
su ifconfig tap0 createsu ifconfig bridge0 addm tap0 addm em0 up
su ifconfig tap0 up

The host and guest are now configured for bhyve operation. The bhyve guest bootstrap process isa two-stage operation not unlike that of the host. The bhyveload(8) utility loads the guest
kernel into memory and the bhyve(8) utility executes it. These commands should be run in tightsequence with identical memory, storage device and guest name parameters.
All configuration parameters forward will be highly site-specific.

42

su /usr/sbin/bhyveload -m 256 -M 0 -d mydiskimage myguestname
su /usr/sbin/bhyve -a -A -m 256 -M 0 -I -H -g 0 \-s 0:0,hostbridge \-s 1:0,virtio-net,tap0 \-s 2:0,virtio-blk,mydiskimage \-S 31,uart,stdio \myguestname

Assuming a successful boot, the guest should behave like a standard FreeBSD system and'shutdown -p now' will cleanly shut it down.
If you wish to terminate a guest at the loader prompt, simply type 'quit'.
Executing guests can be viewed by name on the host system with:su ls /dev/vmm

The above bootstrap procedure will not free the memory allocated to the guest but it can be freed
using bhyvectl(8):su /usr/sbin/bhyvectl --vm=myguestname --destroy

PRAGMATIC BHYVE GUEST OPERATION
The above procedures do not address the subjective matter of populating and configuring theguest userland or automating the guest operation lifecycle.
Two efforts exist to automate the building and operation of bhyve guests.
bhyve developer Neel Natu provides a script named 'vmrun.sh' that works in conjunction with a
FreeBSD 10-CURRENT installation iso image named 'release.iso' to automate the creationof a bootable disk image named 'diskdev' that can be populated using the standard FreeBSD
installer. This script provides an 8G disk image and 512M of dynamic memory by default but
these parameters can be easily modified at runtime or by modifying the script.
The 'vmrun.sh' script requires only a guest name such as 'vm1':
su vmrun.sh vm1

Mr. Natu's script and instructions can be obtained from:http://people.freebsd.org/~neel/bhyve/vmrun.sh
http://people.freebsd.org/~neel/bhyve/bhyve_instructions.txt

43

A suitable 10-CURRENT 'release.iso' image can be retrieved from:http://ftp4.us.freebsd.org/pub/FreeBSD/snapshots/amd64/amd64/ISO-IMAGES/10.0/

Note that the versioning prefix must be removed for the iso to work.
Alternatively, the bhyve.org web site provides a series of scripts that facilitate the creation andoperation of bhyve guests in a highly-customizable manner.
While evolving, at the time of writing these scripts include:
0-make-softdevice.sh
1-format-device.sh
1-format-zvol-gpt.sh
2-install-guest.sh
3-host-prep.sh4-boot-guest.sh
5-cleanup-guests.sh
mount-diskdev.shCreate and mount a disk image or zvol
Format the disk image or zvol
Format a zfs zvol with a GPT layout
Populate the disk image with the OS
Prepare the host for bhyve and networking
Boot the guest
Clean up after the guest
Mount a specified disk image

In addition to the basic functionality provided by 'vmrun.sh', these scripts create and format disk
images in MBR and GPT format, format zvol, iSCSI and hardware devices, populate FreeBSD
8-STABLE, 9-STABLE and 10-CURRENT userlands from the official mirrors and facilitate
guest operation.
Any and all jail(8) and NanoBSD configuration strategies should be applicable to bhyve andthe creation of "thick" and "thin" bhyve hosts and guests.
THE BHYVE DEVELOPMENT ENVIRONMENT
As a native FreeBSD 8-STABLE and later on FreeBSD 10-CURRENT computing environment,
bhyve provides the ideal infrastructure for all categories of FreeBSD development. The hardpartitioning provided by the vmm virtual machine manager allows the "unstable" FreeBSD 10CURRENT environment to be used for "stable" FreeBSD 8 and 9 development with far fewer
potential risks than emulated or jailed environments. Common development nuisances such as
library incompatibilities are eliminated by the virtual machine divide.
The inclusion of dtrace(1M) in FreeBSD 10-CURRENT provides an unprecedented level ofsystem introspection that should prove invaluable to FreeBSD, bhyve and future foreign guest
operating systems.

44Some rudimentary DTrace examples:su kldload dtraceallsu dtrace -n 'io:::start /execname == "bhyve"/ { @[ustack()] = count(); }'libc.so.7`0x800ed3fda
bhyve`pci_vtblk_qnotify+0x59
bhyve`pci_vtblk_write+0x220
bhyve`pci_emul_io_handler+0x16e
bhyve`emulate_inout+0x197
bhyve`vmexit_inout+0x155
bhyve`vm_loop+0x118
bhyve`fbsdrun_start_thread+0x87
libthr.so.3`0x800c53413
505

The sysutils/DTraceToolkit port provides FreeBSD-specific DTrace scripts.
su /usr/share/dtrace/toolkit/hotuser -p `pgrep -n bhyve`
Sampling... Hit Ctrl-C to end.
^C
FUNCTION
bhyve`vm_loop
libvmmapi.so.5`0x800838920
libthr.so.3`0x800c59491
libthr.so.3`0x800c58df1
libvmmapi.so.5`0x800838950
libthr.so.3`0x800c5992f
libc.so.7`0x800f83bb3
bhyve`emulate_inout
libc.so.7`0x800ed3fd0
libthr.so.3`0x800c594c1
bhyve`pci_vtblk_write
bhyve`pci_vtblk_proc
libvmmapi.so.5`0x800838a78
libvmmapi.so.5`0x800838a2e
bhyve`vmexit_inout
libc.so.7`0x800f8875a

COUNT
1
1
1
1
1
1
1
1
1
1
1
1
2
5
6
31

PCNT
1.8%
1.8%
1.8%
1.8%
1.8%
1.8%
1.8%
1.8%
1.8%
1.8%
1.8%
1.8%
3.6%
8.9%
10.7%
55.4%

45

su /usr/share/dtrace/toolkit/hotkernel
Sampling... Hit Ctrl-C to end.
^C
FUNCTION
vmm.ko`vm_guest_msrs
vmm.ko`vcpu_set_state
vmm.ko`vmx_setreg
vmm.ko`vm_nmi_pending
vmm.ko`vm_get_registervmm.ko`lapic_intr_accepted
vmm.ko`vm_lapic
vmm.ko`vlapic_op_mem_read
vmm.ko`lapic_mmio_write
vmm.ko`vlapic_intr_accepted
vmm.ko`vm_set_registervmm.ko`lapic_pending_intr
vmm.ko`vmm_fetch_instruction
vmm.ko`vmmdev_ioctl
vmm.ko`vmmdev_ioctl
vmm.ko`vm_exitinfo
vmm.ko`vcpu_stats
vmm.ko`vmm_emulate_instruction
vmm.ko`vmx_getreg
vmm.ko`lapic_timer_tick
vmm.ko`vm_gpa2hpa
vmm.ko`vlapic_pending_intr
vmm.ko`vlapic_op_mem_write
vmm.ko`vmm_decode_instruction
vmm.ko`vmcs_read
vmm.ko`ept_vmmmap_get
vmm.ko`vlapic_timer_tick
vmm.ko`vm_run
vmm.ko`restore_guest_msrs
vmm.ko`restore_host_msrs
vmm.ko`vlapic_update_ppr
vmm.ko`vmx_run
kernel`acpi_cpu_c1

COUNT
1
1
1
1
1
1
1
2
2
2
2
3
3
3
3
3
3
4
4
5
7
7
7
19
20
21
29
30
32
42
142
33275
168750

PCNT
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.1%
16.3%
82.6%

In addition to the DTrace suite, the bhyvectl(8) command provides extensive bhyve-specificprofiling information:su bhyvectl --get-lowmem --vm=guest0
lowmem0x0000000000000000/268435456
su bhyvectl --get-stats --vm=guest0
vcpu0
number of ticks vcpu was idle
number of NMIs delivered to vcpu
vcpu migration across host cpus
vm exits due to external interrupt
number of times hlt was ignored
number of times hlt was intercepted
vcpu total runtime

46

52440970
1186676222974202158532
288974908299

BHYVE REFERENCE
The following options are available to the bhyveload(8) and bhyve(8) commands:
Usage: bhyveload [-d <disk image path>] [-h <host filesystem path>] [-m<lowmem>] [-M <highmem>] <vmname>
Usage: bhyve [-aehABHIP] [-g <gdb port>] [-z <hz>] [-s <pci>] [-S <pci>][-p pincpu] [-n <pci>] [-m lowmem] [-M highmem] <vm>
-a: local apic is in XAPIC mode (default is X2APIC)-A: create an ACPI table-g: gdb port (default is 6466 and 0 means don't open)-c: # cpus (default 1)-p: pin vcpu 'n' to host cpu 'pincpu + n'
-B: inject breakpoint exception on vm entry-H: vmexit from the guest on hlt-I: present an ioapic to the guest-P: vmexit from the guest on pause-e: exit on unhandled i/o access-h: help-z: guest hz (default is 100)-s: <slot,driver,configinfo> PCI slot config-S: <slot,driver,configinfo> legacy PCI slot config-m: lowmem in MB-M: highmem in MB-x: mux vcpus to 1 hcpu
-t: mux vcpu timeslice hz (default 200)

FUTURE DEVELOPMENTS
bhyve contains experimental PCI device pass-through support and is scheduled to include:• AMD Virtualization Extensions• Foreign Guest Operating System Support• ACPI Guest Suspend and Resume• Thin Provisioning of Memory• Generalization of CPUID Features for Guest Migratability• Sparse Image Support such as QCOW, VDI and VMDK
• Porting to other Host Operating Systems
bhyve is arguably the most compelling FreeBSD development since jail(8) and continues
FreeBSD's tradition of providing innovative multiplicity options to operators and developers.
jail(8) and bhyve are by no means mutually-exclusive technologies and should provide value
when used in conjunction with one another in parallel or via encapsulation. bhyve also promises
to make the most of recent FreeBSD features such as the DTrace, the ZFS filesystem and
FreeBSD’s virtual network stack. The fundamental point to remember about bhyve is that a
FreeBSD bhyve system is simply a FreeBSD system that will fully leverage your FreeBSD
administration and development experience.

47

48

OpenSMTPD : We deliver!
Éric Faurot
eric@openbsd.org
February 8, 2013
Abstract
In this paper we present the OpenSMTPD daemon: a simple, modern and portable mailserver implemented using privilege-separation and messaging passing. Among different features, it comes with a notably simple configuration file format, and it offers very powerful
deployment options.
We describe the internal organisation of the daemon in different processes with very specificroles. We examine the workflows for the main server tasks: enqueueing mails from externalsources, delivering to the local users, relaying to external host and generating bounces. Finally,
we discuss the server modularity, especially the table and backend APIs.

1

Introduction

Although several mail server implementations exist, they are not always satisfying for various
reasons: complexity of the configuration, aging design which make it difficult to add support for
new features, or inappropriate licensing terms.
The aim of the OpenSMTPD project is to provide a simple, robust and flexible implementation of the SMTP protocol, as defined in by RFC 5321[2] and other related RFCs. It is available
under the liberal ISC license. It is being developed as part of the OpenBSD project. The development has started a few years ago, and has been very active in the last months. This paper
presents an overview of the OpenSMTPD daemon design.
The first section will describe the configuration principles. In the next section we present theinternal design of the daemon, based on privileged-separation and message-passing. The following section illustrates the workflow for the five main tasks : enqueueing, scheduling, delivering,
relaying and bouncing. In the fourth section we will briefly discuss the flexibility of the daemon
through filters and backends.

2

Features and Usage

2.1

Configuration

One of the most distinctive feature of OpenSMTPD is the simplicity of the configuration file, especially in comparison with other alternative mail server implementations. It can describe complex
setups in a clear and concise manner, which makes the maintenance easy for the administrator,and helps to prevent misconfigurations with unexpected side-effects. Basic examples of configuration examples are described here.
The philosophy and syntax is largely inspired by the pf[1] configuration. It is based on thedefinition of a rule set: each input passes through the rule-matching engine to decide what action
to take. Unlike pf, OpenSMTPD uses a first-match wins strategy.

49listen on lo0
accept for local deliver to mbox
accept for any relay
The first line tells the server to listen for SMTP connections on the loopback interface. Then
comes the rule-set definition. The first rule matches mails sent for the local machine, which meansthat the destination domain is the machine hostname (or localhost). The action to take is todeliver the mail to the user mbox. In this case, the user part of the destination address is expected
to be a local user. The second rule matches all mails regardless of the destination domain, anduse standard relaying for all domain.
In this example, the rules will implicitly reject mails not originating from the local machine. The
updated configuration which follows allows to also listen on external interfaces (egress group), andaccept mails from external sources for local deliveries using an alias file. Relaying to external
domain is still there but only for mails originating from the local machine :listen on lo0
listen on egress
table aliases file:/etc/mail/aliases
accept from any for local alias <aliases> deliver to mbox
accept for any relay
A common use-case is to route mail for outside through a specific host. The following example
is a typical setup for a home user relaying its mail through his ISP, with authentication.
listen on lo0
table aliases file:/etc/mail/aliases
table secrets file:/etc/mail/secretaccept for local alias <aliases> deliver to mbox
accept for any relay via tls+auth://myisp@smtps.my.isp auth <secrets>

2.2

Administration

The administrator may interact with the daemon using a simple smtpctl control program. This
program connects to the daemon control socket, turns the user request into specific internal control
messages, forwards them to the control process and reports the result. Currently, the programsupports the following operations:• inspecting the current state of the queue: list of messages and scheduling information,• pausing or resuming subsystems such as listeners for incoming mails, outgoing transfers or
local deliveries,• scheduling pending messages for immediate delivery,• removing specific messages,• retrieving various internal statistic counters,• monitoring the server activity in real time.

50

2.3

Other features

Only a few simple cases have been described here, to give an overview of the philosophy behind the
OpenSMTPD configuration. It supports many other features that are expected from any decent
SMTP server implementation, among which :• support for TLS and SMTPS,• user authentication,• backup server for a domain,• primary and virtual domains,• completely virtual users,• local delivery to mbox, Maildir or external program.
The following example, adapted from a real-world configuration, shows a more complex setup
using many of the OpenSMTPD features. The details won’t be discussed here, but it shows how
very powerful setups can be achieved, while the configuration file remains reasonably easy to read.
listen on lo0#
Tag traffic from the local DKIM signing proxylisten on lo0 port 10029 tag DKIM#
Listen for incoming mail on standard smtp port and smtps port with ssl.
listen on egress ssl certificate mail.mydomain.org#
Listen on a different port, enable tls and require authlisten on egress port submission tls certificate mail.mydomain.org authtable sources
table aliases
table aliases2
table pdomains
table vdomains
table vusers
table bdomains{ xxx.xxx.xxx.44, xxx.xxx.xxx.45 }"/etc/mail/smtpd/aliases""/etc/mail/smtpd/aliases2""/etc/mail/smtpd/primary-domains""/etc/mail/smtpd/virtual-domains""/etc/mail/smtpd/virtual-users""/etc/mail/smtpd/backup-domains"#
Deliver local mails with aliases
accept for local alias <aliases> deliver to maildir#
Accept external mails for our primary domains.
accept from any for domain <pdomains> alias <aliases> deliver to maildir#
Accept external mails for a specific primary domain with other aliases.
accept from any for domain "other.dom" alias <aliases2> deliver to maildir#
Virtual domains, with a mapping from virtual users to real mailboxes
accept from any for domain <vdomains> virtual <vusers> deliver to maildir#
Act as a backup server for the given domains, only relay to servers with#lower MX preference than the one specified.
accept from any for domain <bdomains> relay backup mx1.mydomain.org#
Relay all signed traffic, using multiple source addresses (round robin).
accept tagged DKIM for any relay source <sources>#
Relay outgoing mails through a DKIM signing proxy.
accept for any relay via smtp://127.0.0.1:10028

51

3Internal Design

3.1

Fundamental concepts

The most important ”object” around which the OpenSMTPD daemon is organised is the envelope.
An envelope describes a message that is in transit within the server. It is always associated witha body, or content. Different envelopes can be associated with the same underlying content, toform what we refer to as a message, as illustrated in figure 1.

Figure 1: A message

An envelope has an origin, the sender, which is shared between all envelopes within the samemessage. An envelope also has a single destination, the recipient. A message sent to multiple
recipient will have one envelope for each of them. The envelope also contains administrative information like the creation time, the expiry time, some internal flags, information on the enqueueing,
etc. It also contains routing information, which describes how the associated content is to betransfered or delivered. An envelope is uniquely identified with its envelope ID, a 64 bits numberthat is generated internally.
Envelopes are created by and SMTP clients and the associated messages are stored (queued)
temporarily in the server, until they can reach their next or final destination. There are three
types of envelopes: local envelopes which are to be delivered to a local user on the host, relay
envelopes, which must be transfered to another host, and bounce envelopes which are internal,
and are meant to generate a report.
The OpenSMTPD server is implemented as a set of dedicated processes communicating using
the ISMG(3) framework, and working together, exchanging envelopes, to drain accepted messages
out. This design has several advantages. Defining specific roles and isolating functionalities indifferent processes lead to a design that is globally simpler to understand, and more reliable inthe sense that it prevents layer violation. The processes can also run at different privilege levels,
providing extra protection in case one of them (especially those directly exposed to the internet)
is compromised.
Besides the short-lived ones that are temporarily forked, there are 9 processes :• scheduler• queue• mail transfer agent• mail delivery agent• mail filter agent52

• lookup agent• smtp• control• parent
In the rest of the section we describe the different processes and their role in the system.

3.2

Process layout

Figure 2: OpenSMTPD process layout

3.2.1

Scheduler

The scheduler is the process that knows all existing envelopes, and which takes the decision ofscheduling for delivery, relaying, expiring them. It does not know the full detail of the envelopes,
but only the necessary scheduling information: creation date, expiry date, retry count and a few
flags which are required to take scheduling decision.
The scheduler only maintains a runtime state: it gets notified about new envelopes, dispatch
work to be done when an envelope is schedulable, and wait for notification of the delivery outcome, to update the envelope runtime state.
It runs fully unprivileged and chrooted to an empty directory.
3.2.2

Queue

The queue process is responsible for storing envelopes and messages on permanent storage reliably,
and reloading them on demand. For practical reason it is also the process that re-inject bounced
envelopes. When the daemon starts, the queue process is also responsible for reloading existing53

envelopes off permanent storage and providing them to the scheduler. It is the only process thatis supposed to maintain an offline state.
One important duty of the queue process for reliability is to make sure that incoming messages
and envelopes have reached permanent storage before being acknowledged, and that they are notremoved or altered before being confirmed as delivered.
The queue process runs unprivileged, and chrooted into the smtpd spool directory.
3.2.3

SMTP

The SMTP process implements the SMTP protocol. It manages clients connections and push incoming messages to the rest of the system. As for the rest of the daemon, it runs fully event-based.
Due to its design which relies heavily on fd-passing, the daemon is very sensible to file descriptor
exhaustion situations. To prevent this from happening, which would impair the already runningsessions, the daemon automatically disable input sockets when system limits are reached or close
to be. It also implements simple counter-measures against clients that hog a connection by notdoing any useful work, i.e. actually delivering mails.
It receives the listening sockets through dedicated imsg from the parent process, which alreadybound them to reserved ports. So it can run fully unprivileged and chrooted to an empty directory.
3.2.4

Mail transfer agent

The mail transfer agent (mta), is the process that handles relaying to other hosts.
The process managed destination relays to which mails must be sent. It tries to establish connections to these relays and drain pending messages. It handles connections limit, such as the numberof mails sent per session, the number of recipients per mail, the number of parallel connections tothe same host or domain, the maximum number of connections.
Like the SMTP process, it runs unprivileged and chrooted to an empty directory.
3.2.5

Mail delivery agent

The mail delivery agent (mda) is responsible for managing local deliveries. It does not do thedelivery itself, but asks the parent privileged process to execute the actual mail delivery program
on behalf of the local user to which a mail is destinated. The process makes sure to limit the
number of running delivery processes on a global and per-user basis.
This process also runs unprivileged and chrooted to an empty directory,
3.2.6

Lookup agent

The lookup agent (lka) acts as a proxy for all kinds of lookups that other processes wants to do:credentials for authentication, user information, DNS resolving, which is a very important partof an SMTP daemon. The DNS queries are done asynchronously using an async variant of theresolver API. Multiple queries can run in parallels within the same process, which avoids having
to block the whole process or rely on cumbersome work-arounds like thread pools or forks.
The lookup agent is also the process that does the rule-set evaluation for incoming envelopes,
as we will see in the next section.
The main reason for having a separate process doing the queries is isolation: it allows other54

processes to run with very constrained environment. The lookup agent runs unprivileged, but is
not chrooted since it must be able to access system resources like /etc/resolv.conf.
3.2.7

Mail filter agent

The mail filter agent (mfa) manages the pluggable filter processes and drives the filtering process.
It maintains a chain of filters through which SMTP requests and events are passed for processing,
before being sent back to the SMTP process.
3.2.8

Control

The control process is the one that listens on the UNIX socket for request smtpctl program. It
forwards requests from the administrator to the relevant process: pausing/resuming some agent,
force the scheduling or removal of a message, get information about the runtime state of a message
or envelope, etc, and deliver the responses to the client.
It is also responsible for collecting counter updates. All processes can report information about
their internal activity for statistical analysis or runtime monitoring, in the form of named counterincrements/decrements. For example, the number of active clients connections or queued envelopes.

3.2.9

ParentThis is the master process. It is the only process that needs to run as superuser. After the configuration file is loaded, it forks all the above processes, send them their runtime configuration, andwaits for queries from other processes.
This process can perform the following privileged operations on behalf of other process: open
a user .forward file for the lookup agent when expanding envelopes, perform local user authentication for the smtp process, execute or kill an external delivery program on behalf of the maildelivery process.

4

Operational workflows

We will describe here the internal exchanges that occurs to fulfill different services that the servermust provide.

4.1

Enqueueing

The enqueueing task consists in accepting messages from outside. The sequence is depicted infigure 3. We suppose that all SMTP negotiation is already done, and the client wants to start a
new transaction.
When a new MAIL FROM command is received it tells the queue process to create a new incoming message, and gets a unique message id in return. For each recipient (RCPT TO), a query
is sent to the lookup agent, which tries find a matching rule. If found the recipient is expanded
according to that rule (by looking for aliases or forward). The complete expand process is not detailed here, but it creates one or more final envelopes corresponding to the given recipient. Theseenvelopes are sent to queue which stores them for the incoming message, and forward them to thescheduler. When all envelopes for a recipient are expanded, the SMTP process is notified that the55

Figure 3: Enqueueing sequence diagram
RCPT is accepted. The client can then issue new RCPT request, repeating the expand sequence.
When the client wants to start sending the message content (using the DATA command), theSMTP process request a file descriptor from the queue process for writing the incoming message.
When all data is written, it asks the queue to commit the message, which means moving it fromincoming to permanent queue, and notifying the scheduler. When the SMTP receives the confirmation from the queue that the message is committed, it notifies the client.
If anything fails at some point of the process, the incoming message is cancelled. The sequence
ensures that the envelopes and message have always reached permanent storage before the client
and the scheduler are notified. So the whole process is fully transactional.

4.2

Scheduling

The scheduler receives new envelopes for incoming envelopes from the queue process. When amessage is committed, it starts scheduling the associated envelopes. The life-cycle of these envelopes in the scheduler is shown on diagram 4.
The scheduler creates batches of schedulable envelopes id which are sent to the queue process

56

Figure 4: Scheduling sequence diagramfor delivery or relaying, and marked as ”in-flight”. The queue process loads the full envelopes andit dispatches them between the two mda an mta agent, depending on the envelope type.
When the agent is done with an envelope, it reports the outcome to the queue process, which
updates the envelope state or delete it on success. The scheduler is then notified, so that it can
update the state of the ”in-flight” envelope accordingly: either remove it, or re-schedule later in a
new batch.

4.3

Local deliveries

The detail of the local delivery operation is depicted on figure 5. When a message is to be delivered
locally, the delivery process first retrieves the user information from the lka. It queries the queue
process to obtain a file descriptor to read the message content from. When received, it sends afork request with given user info to the parent process, which returns a file descriptor to write
the message body to. When done, it waits for the notification from parent that the forked mda
process has correctly exited, and if so, it reports the envelope as delivered to the queue process,which removes the envelope and informs the scheduler. In case of error, a failure report is sent to
the queue.

4.4

Relaying

Relaying is the process by which responsibility for a message in the queued is transfered to anotherserver, normally through the SMTP protocol. The internal interaction between smtpd process isshown on figure 6.
When receiving a envelope to relay, the transfer process first determines the relay to use. If
necessary, it requests the credentials from the lookup agent. It also requests the list of MX hosts
to use. These information are cached as long as the relay is currently referenced, so new envelopes

57

Figure 5: Local delivery sequence diagram
for the same relay in the mean time will not trigger these queries again. Received envelopes aregrouped into tasks (messages for the same relay and for the same message) and queued on therelay for delivery.
When ready, the mail transfer agent will try to establish connections for the relay by trying
to connect the MXs. Once a session is established, the reverse DNS entry is searched and theinitial SMTP negotiation happens. At this point the agent might want to get the specific HELO
string to use from the lka. When the session is ready to send mails, it dequeues the next task,
retrieves the file descriptor for the message body from the queue, and starts the SMTP transfer.
When the remote host has acknowledged (or rejected) the message transfer, the queue is notified
for each envelope. The session can than proceed to the next task, if any.
If no connections could be established at all, all envelopes for that relay are sent back to thequeue process with a failure report.

4.5

Bounces

Bounces are report messages that are sent by the mailer daemon to report temporary or permanent failure when trying to deliver a mail it has accepted. There are two kinds of bounces which
can occurs: either a delay notification that is generated when an envelope has been queued for acertain time, or a failure report when the envelope has been refused or has expired, in which casethe associated envelope is discarded.
A bounce is always associated to a message, it is internally handled as a special type of envelope for that message. It is created by the queue process as any other envelopes, expect that it
is usually created on an already committed message (as opposed to incoming). Once created, thebounce envelope is sent to the scheduler, as any other envelope.

58

Figure 6: Relaying sequence diagram

It is processed by the queue process which will create regular envelope targeted at the original sender (return path) with a report and the bounced message. So the queue process request
an internal socket from the smtp process to establish a local SMTP session, and re-inject thebounce message using the SMTP protocol. It creates a message with a single envelope, which is
the original sender for the bounced envelope, and the body of the message contains the failure
report for the original recipient.
Bounces are grouped when possible: when receiving a bounce envelope to re-inject, the queue
process will delay the SMTP session lightly waiting for other bounces for the same message. The
figure 7 illustrates the successive states of the queue when bouncing and discarding two envelopes
for the same message.

5

Modularity and deployment options

Besides the flexibility of the configuration which allows the creative minds to easily build complex
processing chains (relaying outgoing mail through a DKIM proxy is a 4 liners), OpenSMTPD
provides two mean of extending its functionalities: input filters and internal backends.

59

Figure 7: Bounce creation and re-injection

5.1

Filtering

The goal is to provide a powerful way to let external programs filter the incoming SMTP sessions
and messages, in order to reject some possibly altering the recipients and/or the message contents.
A filtering mechanism has been in place since the beginning, but it has not been a high priority
until more fundamental parts of the daemon were in place. It has been completely re-designed
recently to fix some early limitations.
Filters are implemented as external programs which are started with the daemon. They arebound to the mfa process, and communicate with it via dedicated IMSG. The filter will registers
various hooks for events or queries it wants to intercepts. An API and library is provided forwriting filters, hiding the internal imsg machinery.
At the moment, the integrated filter support is still under development, and not officially supported yet and will not be part of the first release. It is however possible achieve various kind offiltering using a proxy loop: incoming mails are relayed through a specific SMTP proxy, such asa DKIM signing program or spam filter, and re-injected on a specific tagged listener.
A specific milter glue filter is planned, to allow using filters implemented with the milter API
to run with OpenSMTPD. The ability to filter outgoing mail (at the transfer agent level) is alsoplanned but not implemented yet.

5.2

Backends

Whereas filters operates on users inputs to alter the smtpd behaviour, the backend mechanism isa mean to completely change the deployment strategy.
Various parts of the daemon internally relies on abstractions for specific operations, which aredefined as concise and strict API, which are implemented by backends. From the point of viewof the calling process, this is completely hidden, so any implementation of these interfaces with60

the required semantics, can be used. This has two advantages: it prevents layer violation in thedesign, and it makes the implementation very flexible, once the correct abstractions are found.
The three most important backends are presented here.
5.2.1

Table backends

Almost all lookups in the daemons are done using the table abstraction. Depending on the context,
a table can be either a set, or an associative array. The types of the elements also depends on thecontext. Tables are said to provide one or more service, and are implemented by a backend. The
different services used are :• ALIAS: association of a user name to mail aliases, used for alias lookups.
• DOMAIN: list of domain names: used to match destination or source domains.
• CREDENTIALS: association of a label to a pair of username/password, for SMTP authentication.
• NETADDR: list of network addresses, used for rule matching on the connection.
• USERINFO: association of a user name to its system uid/gid and home directory.
• SOURCE: list of local IP addresses, used by the MTA for outgoing connections.
The existing backends are :• static: in memory content, or loaded from a file,• db: using a db(3) database,• getpwnam: this special backends implements only the credentials and userinfo service,• ldap and sqlite: those are experimental backends
Any table backend able to implement a given service can be used in all contexts where thisservice is expected. It is then trivial to run completely virtual mail servers.
5.2.2

Scheduler backend

The scheduler backend API only have a few function to insert new envelopes fetch the list of envelopes to schedule, which are dispatched to the relevant agents, and update their state dependingon the delivery outcome. There is a couple of administrative functions too. The current scheduler
operates entirely in memory.
5.2.3

Queue backend

The queue process relies on a storage backend which role is to implement a set of well-defined
atomic operation on envelopes and messages. The default out-of-the box backend uses bucketbased disk storage and rely on file-system operations. OpenSMTPD also ships with a RAM-based
queue, which keeps every everything in memory. Of course, the storage is not permanent anymore,
but it is a good way for testing things, and it is also useful, when designing the API and implementation, to make sure that the abstractions make sense and that no dangerous assumptions are
made on the queue implementation.
As another Proof-of-Concept, we have written a completely alternative storage backend for thequeue , which used ReST queries to store envelopes on an external cloud storage. The performances were of course terrible in the example setup, but the reliability of the whole delivery
process was intact, since every thing is still transactional.

61

6Conclusion

OpenSMTPD provides a simple and powerful implementation of a mail server, with a relatively
small codebase. The design principles behind it make it very easy to use and deploy in a large
range of environments. Performances issues have not been discussed here. It is a bit early to focus
on performance tuning. Nonetheless, early tests shows that the server behaves correctly underload, and is able to process envelopes at very satisfying rate.
The daemon is actively maintained. Primary development is done on OpenBSD, and a portableversion for other UNIX systems is provided too. It’s been tested successfully on various flavoursof Linux, other BSDs, and MacOS-X.
Some features are not there yet: for example support for the PIPELINING extensions is missing,
and we need a way to quarantine some messages/envelopes. However we believe that the current
features are enough to handle most situations. We are now focusing on internal cleanups andtesting. A first official release is to be expected very soon.

References[1] Pf: The openbsd packet filter. http://www.openbsd.org/faq/pf/index.html.
[2] J. Klensin. Simple Mail Transfer Protocol. RFC 5321 (Draft Standard), October 2008.

62

Implements BIOS emulation support for
BHyVe: A BSD Hypervisor

Abstract
Current BHyVe only supports FreeBSD/amd64
as a GuestOS.
One of the reason why BHyVe cannot support
other OSes is lack of BIOS support.
My project is implementing BIOS emulator on
BHyVe, to remove these limitations.

1. Background
1.1 History of virtualization on x86
architecture
There's a famous requirements called "Popek& Goldberg Virtualization requirements"1,
which defines a set of conditions sufficient for
an architecture to support virtualization
efficiently.
Efficient virtualization means virtualize
machine without using full CPU emulation, runguest code natively.
Explain the requirements simply, to anarchitecture virtualizable, all sensitive
instructions should be privileged instruction.
Sensitive instructions definition is the
instruction which can interfere the global statusof system.
Which means, all sensitive instructions
executed under user mode should be trappedby privileged mode program.
Without this condition, Guest OS affects Host
OS system status and causes system crash.
x86 architecture was the architecture which
didin’t meet the requirement, because It had
non-privileged sensitive instructions.

To virtualize this architecture efficiently,
hypervisors needed to avoid execute these
instructions, and replace instruction withsuitable operations.
There were some approach to implement it:
On VMware approach, the hypervisor replaces
problematic sensitive instructions on-the-fly,
while running guest machine. This approachcalled Binary Translation2.
It could run most of unmodified OSes, but it
had some performance overhead.
On Xen approach, the hypervisor requires torun pre-modified GuestOS which replaced
problematic sensitive instructions to dedicatedoperations called Hypercall. This approachcalled Para-virtualization3.
It has less performance overhead than Binary
Translation on some conditions, but requires
pre-modified GuestOS.
Due to increasing popularity of virtualization
on x86 machines, Intel decided to enhance x86
architecture to virtualizable.
The feature called Intel VT-x, or HardwareAssisted Virtualization which is vendor
neutral term.
AMD also developed hardware-assisted
virtualization feature on their own CPU, called
AMD-V.
1.2 Detail of Intel VT-x
VT-x provides new protection model whichisolated with Ring protection, forvirtualization.
It added two CPU modes, hypervisor modeand guest machine mode.
Hypervisor mode called VMX Root Mode,and guest machine mode called VMX non
Root Mode(Figure 1).

Gerald J. Popek and Robert P. Goldberg. 1974. Formal requirements for virtualizable third
generation architectures. Commun. ACM 17, 7 (July 1974), 412-421. DOI=10.1145/361011.361073
http://doi.acm.org/10.1145/361011.361073
2 Brian Walters. 1999. VMware Virtual Platform. Linux J. 1999, 63es, Article 6 (July 1999).
3 Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer,

Ian Pratt, and Andrew Warfield. 2003. Xen and the art of virtualization. In Proceedings of thenineteenth ACM symposium on Operating systems principles (SOSP '03). ACM, New York, NY,
USA, 164-177. DOI=10.1145/945445.945462 http://doi.acm.org/10.1145/945445.945462

63

VMX
root mode

VMX
non-root
mode

User(Ring 3)User
(Ring 3)

Kernel(Ring 0)Kernel(Ring 0)Figure 1. VMX root Mode and VMX non-root
Mode
On VT-x, hypervisor can run guest OS on
VMX non Root Mode without any
modification, including sensitive instructions,
without affecting Host OS system status.
When sensitive instructions are being executed
under VMX non Root Mode, CPU stops
execution of VMX non Root Mode, exit to
VMX Root Mode.
Then it trapped by hypervisor, hypervisor
emulates the instruction which guest tried to
execute.
Mode change from VMX Root Mode to VMX
non-root Mode called VMEntry, from VMX
non-root Mode to VMX Root Mode called
VMExit(Figure 2).
VMX
root mode

VMX
non-root
mode

User(Ring 3)User
(Ring 3)

Kernel(Ring 0)

VMEntry
VMExitKernel(Ring 0)Figure 2. VMEntry and VMExit
Some more events other than sensitive
instructions which need to intercept byhypervisor also causes VMExit.

64

For example, IN/OUT instruction causes
VMExit, and hypervisor emulates virtual
device access.
VT-x defines number of events which cancause VMExit, and hypervisor needs toconfigure enable/disable on each VMExit
events.
Reasons of VMExit is called VMExit reason,
it classified by genres of events.
Here are VMExit reason list:• Exception or NMI• External interrupt• Triple fault• INIT signal received• SIPI received• SM received• Internal interrupt• Task switch• CPUID instruction• Intel SMX instructions• Cache operation instructions(INVD,WBINVD)• TLB operation instructions(HNVLPG,INVPCID)• IO operation instructions(INB, OUTB, etc)
• Performance monitoring conter operation
instruction(RDTSC)• SMM related instruction(RSM)• VT-x instructions(Can use for implement
nested virtualization)• Accesses to control registers• Accesses to debug registers• Accesses to MSR• MONITOR/MWAIT instructions• PAUSE instruction• Accesses to Local APIC
• Accesses to GDTR, IDTR, LDTR, TR• VMX preemption timer• RDRAND instruction

VMCS data format revision number.

Error code of VMExit failure.

VMCS revision identiﬁer
VMX-abort indicator
Guest-state area

VMCS data

Host-state area

An area for saving / restoring guest registers.
Register saving/restoring are automatically
preformed at VMExit/VMEntry.
(Actually not all register are it's target. Someregisters should save by hypervisor manually.)
The area saves some non-register state,
instruction blocking state etc.

VM-exection control ﬁelds
VM-exit control ﬁelds
VM-entry control ﬁelds
VM-exit information ﬁelds

An area for saving / restoring hypervisor registers.
Usage is almost identical with Guest-state area.
A ﬁeld control processor behavior in VMX non-root
operation. VMExit causing events can conﬁgure
here.
A ﬁeld control processor behavior in VMExit
operation.
A ﬁeld control processor behavior in VMEntry
operation. Enabling/Disabling 64bit mode canconﬁgure here.
VMExit reason stored here.

Figure 3. Structure of VMCS
All configuration data related to VT-x stored to
VMCS(Virtual Machine Control Structure),
which is on memory data structure for each
guest machine4.
Figure 3 shows VMCS structure.
1.3 VT-x enabled hypervisor lifecycle
Hypervisors for VT-x works as following
lifecycle (Figure 4).
1. VT-x enabling
It requires to enable at first to use VT-x
features.
To enable it, you need set VMXE bit on
CR4 register, and invoke VMXON
instruction.
2. VMCS initialization
VMCS is 4KB alined 4KB page.
You need to notify the page address to CPU
by invoking VMPTRLD instruction, thenwrite initial configuration values by
VMWRITE instruction.
You need to write initial register values
here, and it done by /usr/sbin/bhyveload.
3. VMEntry to VMX non root mode
Entry to VMX non root mode by invoking
VMLAUNCH or VMRESUME instruction.
On first launch you need to use
VMLAUNCH, after that you need to use
VMRESUME.
Before the entry operation, you need tosave Host OS registers and restore Guest
OS registers.
VT-x only offers minimum automatic save/restore features, rest of the registers need totake care manually.
4. Run guest machine
CPU runs VMX non root mode, guest
machine works natively.

4 If guest system has two or more virtual CPUs, VMCS needs for each vCPUs.

65

1. VT-x enabling

2. VMCS
initialization

7. Run anotherprocess

3. VMEntry to VMX
non root mode

6. Do emulation for
the exit reason

4. Run guest
machine5. VMExit for some
exit reason

Figure 4. VT-x enabled hypervisor lifecycle
5. VMExit for some reason
When some events which causes VMExit,
CPU returns to VTX root mode.
You need to save/restore register at first,
then check the VMExit reason.
6. Do emulation for the exit reason
If VMExit reason was the event which
requires some emulation on hypervisor,
perform emulation. (Ex: Guest OS wrote
data on HDD
Depending Host OS scheduling, it may
resume VM by start again from 3, or task
switch to another process.
1.4 Memory Virtualization
Mordan multi-tasking OSes use paging toprovide individual memory space for eachprocesses.
To run guest OS program natively, addresstranslation on paging become problematicfunction.
For example (Figure 5):
You allocate physical page 1- 4 to Guest A, and
5-8 to GuestB.
Both guests map page 1 of Process A to page 1of guest physical memory.
Then it should point to:• Page 1 of Process A on Guest A ->Page 1 of Guest physical memory ->Page 1 of Host physical66• Page 1 of Process B on Guest B ->Page 1 of Guest physical memory ->Page 5 of Host physicalBut, if you run guest OS natively, CPU willtranslate Page 1 of Process B on Guest B to
Page 1 of Host physical memory.
Because CPU doesn’t know the paging for
guests are nested.
There is software technique to solve theproblem called shadow paging (Figure 6).
Hypervisor creates clone of guest page table,
set host physical address on it, traps guest
writing CR3 register and set cloned page table
to CR3.
Then CPU able to know correct mapping of
guest memory.
This technique was used on both Binarytranslation based VMware, and also early
implementation of hypervisors for VT-x.
But it has big overhead, Intel decided to add
nested paging support on VT-x from Nehalem
micro-architecture.
EPT is the name of nested paging feature(Figure 7),
It simply adds Guest physical address to Hostphysical address translation table.
Now hypervisor doesn’t need to take care guest
paging, it become much simpler and faster.

Process A
1

Guest A
Page table A
1

Guest physical memory1

2
Process B
1
2

Page table B
1
2

Process A
1

3
4

1
2

Host physical memory

3
4

1
2
3
4

Guest B
Page table A
1
2

Process B

1
2

Guest physical memory

1

1
2
3
4

Page table B
1
2

5
6
7

3
4

8

Figure 5. Problem of memory virtualization
Page table A'
1

Host physical memory52Page table B'
1
2

Process A
12
3
4

Guest A

5

Page table A
1
2

6
7
8

2
Process B
1
2

1

7
8

Page table B
1
2

3
4

1
2
3
4
Guest physical memory

Figure 6. Shadow paging
Host physical memory
Process A
1
Process B
1
2

Guest A
Page table A
1
2

2

Page table B
1
2

3
4

EPT A
1
2
3
4
Guest physical memory

1
2
3
4

5
6
7
8

1
2
3
4
5
6
7
8

Figure 7. EPT

67

Actually, not all VT-x supported CPUs
supports EPT, on these CPUs hypervisors stillneed to do shadow paging.

2. BHyVe: BSD Hypervisor
2.1 What is BHyVe?
BHyVe is new project to implement a
hypervisor witch will integrate in FreeBSD.
The concept is similar to Linux KVM, it
provides “hypervisor driver” to unmodified
BSD kernel running on bare-metal machine.
With the driver, the kernel become ahypervisor, able to run GuestOS just likenormal process on the kernel.
Both hypervisors are designed for hardware
assisted virtualization, unlike Xen’s paravirtualization and VMware’s binary translation.
The kernel module only provides a feature toswitch CPU modes between Host mode andGuest mode, almost all device emulation is
performed in userland process.
2.2 Difference of approach between LinuxKVM and BHyVeLinux KVM uses modified QEMU5 as theuserland part 6.
It’s good way to support large coverage ofGuest OSes, because QEMU is highly
developed emulator, many people alreadyconfirmed to run variety of OSes on it.
KVM could support almost same features what
QEMU has, and it just worked fine.
BHyVe’s approach is different.

BHyVe implements minimum set of device
support which required to run FreeBSD guest,from scratch.
In the result, we could have completely GPLfree, BSD licensed, well coded hypervisor, but
it only supports FreeBSD/amd64 as a Guest
OS at this point.
One of the reason why BHyVe cannot support
other OSes is lack of BIOS support.
BHyVe loads and executes FreeBSD kernel
directly using custom OS loader runs on HostOS, instead of boot up from disk image.
With this method, we need to implement OS
loader for each OSes, and currently we don’t
have any loader other than FreeBSD.
Also, it doesn’t support some OSes which calls
BIOS function while running.
So I started the project to implementing BIOS
emulator on BHyVe, to remove theselimitations.
2.3 Hardware requirements
BHyVe requires an Intel CPU which supports
Intel VT-x and EPT.
It means you will need Nehalem core or later
Intel CPUs, because EPT is only supported onthese processors.
Currently, AMD-V is not supported.
Installing on physical machine is best choice,but it also works on recent version of VMware,using Nested virtualization feature 7.
2.3 Supported features
BHyVe only supports FreeBSD/amd64 8-10
for guest OS.

5 Original QEMU has full emulation of x86 CPU, but on KVM we want to use VT-x hardware

assisted virtualization instead of CPU emulation.
So they replace CPU emulation code to KVM driver call.
6 Strictly speaking, KVM has another userland implementation called Linux Native KVM Tools,

which is built from scratch - same as BHyVe’s userland part.
And it has similar limitation with BHyVe.
7 The technology which enables Hypervisor on Hypervisor. Note that it still requires Nehalemcore or later Intel CPUs even on VMware.

682.4 BHyVe internal
BHyVe built with two parts: kernel module anduserland process.
The kernel module is called vmm.ko, it
performs actions which requires privilegedmode (ex: executes VT-x instructions.
Userland process is named /usr/sbin/bhyve,
provides user interface and emulates virtual
hardwares.
BHyVe also has OS Loader called /usr/sbin/bhyveload, loads and initializes guest kernel
without BIOS.
/usr/sbin/bhyveload source code is based on
FreeBSD bootloader, so it outputs bootloader
screen, but VM instance is not yet executing atthat stage.
It runs on Host OS, create VM instance andloads kernel onto guest memory area,
initializes guest machine registers to prepare
direct kernel boot.
To destroy VM instance, VM control utility /usr/sbin/bhyvectl is available.
These userland programs are accesses vmm.ko
via VMM control library called libvmmapi.
Figure 8 illustrates overall view of BHyVe.

2. Run VM instace
Disk image
tap device
stdin/stdout

1. Create VM instance,load guest kernel
Guestkernelbhyveload

H
D

N
I
C

ConsoleIt emulates following devices:• HDD controller: virtio-blk• NIC controller: virtio-net• Serial console: 16550 compatible PCI UART
• PCI/PCIe devices passthrough (VT-d)Boot-up from virtio-blk with PCI UART
console is not general hardware configuration
on PC architecture, we need to change guest
kernel settings on /boot/loader.conf(on guest
disk image).
And some older FreeBSD also need to add avirtio drivers 8.
PCI device passthrough is also supported, able
to use physical PCI/PCIe devices directly.
Recently ACPI support and IO-APIC support
are added, which improves compatibility withexisting OSes.

bhyve

3. Destroy VM
instance
bhyvectl

libvmmapi
mmap/ioctl/dev/vmm/${vm_name} (vmm.ko)
FreeBSD kernel

Figure 8. BHyVe overall view

3. Implement BIOS
Emulation
3.1 BIOS on real hardware
BIOS interrupt calls are implemented assoftware interrupt handler on real mode(Figure
9).
CPU executes initialization code on BIOS
ROM at the beginning of startup machine, it
initializes real mode interrupt vector to handle
number of software interrupts reserved for
BIOS interrupt calls(Figure 10).
BIOS interrupt calls aren’t only for legacy
OSes like MS-DOS, almost all boot loaders formordan OSes are using BIOS interrupt call toaccess disks, display and keyboard.
3.2 BIOS on Linux KVM
On Linux KVM, QEMU loads Real
BIOS(called SeaBIOS) on guest memory areaat the beginning of QEMU startup.
KVM version of SeaBIOS’s BIOS call handler
accesses hardware by IO instruction or
memory mapped IO, and the behavior isbasically same as BIOS for real hardware.
The difference is how the hardware accesshandled.
On KVM, the hardware access will trapped by
KVM hypervisor driver, and QEMU emulates

8 virtio is para-virtual driver which designed for Linux KVM. para-virtual driver needs special

driver for guest, but usually much faster than full emulation driver.

69

int 13h

Software interrupt(INTx)
CPU reads interrupt vector
Execute BIOS call handler
IO
HardwareFigure 9. BIOS interrupt call mechanism on real hardware③Handler accesses HW by IO instruction
highmem

FFFF:000F

ROM BIOS

FFFF:0000

Video RAM, etc②Jump to the handler address

A000:0000

lowmemInterrupt vector①Fetch interrupt handler address

F000:0000

0000:0400
0000:0000

Figure 10. Memory map on real hardware
int 13h

Software interrupt(INTx)
CPU reads interrupt vector
Execute BIOS call handler

SeaBIOS preforms IO
to virtual HWIO Trap
QEMU HW
Emulation

Guest
HyperVisor

QEMU emulates HW IO

Figure 11. BIOS interrupt call mechanism on KVM③Handler accesses HW by IO instr
QEMU emulates the IO

highmem

SeaBIOS②Jump to the handler address

Video RAM, etc
lowmem

①Fetch interrupt handler address

Interrupt vector

FFFF:000F
FFFF:0000
F000:0000
A000:0000
0000:0400
0000:0000

Figure 12. Memory map on KVM
70hardware device, then KVM hypervisor driverresume a guest environment(Figure 11).
In this implementation, KVM and QEMU
doesn’t trap BIOS interrupt calls, it just loads
real BIOS on guest memory space(Figure 12)
and emulates hardware device.
3.3 Emulating BIOS on BHyVe
3.3.1 doscmd
Port SeaBIOS on BHyVe and implement
hardware emulation was an option, and it wasprobably best way to improve compatibility oflegacy code, but SeaBIOS is GPL’d software,it’s not comfortable to bring in FreeBSD codetree.
And there’s no implementation non-GPL
opensourced BIOS.
Instead, there’s BSD licensed DOS Emulator
called doscmd.
It’s the software to run old DOS application on
FreeBSD using virtual 8086 mode, similar to
DOSBox(but DOSBox is GPL’d software).
The emulator mechanism is described asfollows:
1. Map pages to lowmem area (begin from0x0), load the DOS application on the area.
2. Enter virtual 8086 mode, start executing
the DOS application.
3. DOS application invokes BIOS interrupt
call or DOS API call by INTx instruction.
4. DOS Emulator traps software interrupt,
emulate BIOS interrupt call or DOS API
call.
5. Resume DOS application.
It traps BIOS interrupt calls and DOS API callsand emulate them on FreeBSD protected mode
program.
I decided to port the BIOS interrupt callemulation code to BHyVe and trap BIOS
interrupt call on BHyVe, instead of porting realBIOS.
3.3.2 Run real mode program on VT-x
On older implementation of VT-x enabled CPU
doesn’t allow to VMEnter the guest which
doesn’t enable paging.

Which means real mode program cannot run
on VT-x, and hypervisors needed to virtualize
real mode without VT-x.
Linux KVM used full CPU emulation using
QEMU to virtualize real mode.
Some other hypervisors are used virtual 8086
mode.
This issue was resolved by extending VT-x
features.
Intel added unrestricted guest mode on
Westmere micro-architecture and later IntelCPUs, it uses EPT to translate guest physicaladdress access to host physical address.
With this mode, VMEnter without enablepaging is allowed.
I decided to use this mode for BHyVe BIOS
emulation.
3.3.3 Trapping BIOS interrupt call
VT-x has functionality to trap various event on
guest mode, it can be done by changing VT-x
configuration structure called VMCS.
And BHyVe kernel module can notify these
events by IOCTL return.
So all I need to do to trapping BIOS call ischanging configuration on VMCS, and notify
event by IOCTL return when it trapped.
But the problem is which VMExit event is
optimal for the purpose.
It looks like trapping software interrupt is theeasiest way, but we may have problem after
Guest OS switched protected mode.
Real mode and protected mode has different
interrupt vector.
It’s possible to re-use BIOS interrupt call
vector number for different purpose on
protected mode.
Maybe we can detect mode change between
real mode/protected mode, and enable/disable
software interrupt trapping, but it’s bitcomplicated.
Instead of implement complicated modechange detection, I decided to implement
software interrupt handler which cause
VMExit.

71

The handler doesn’t contain programs forhandling the BIOS interrupt call, just perform
VMExit by VMCALL instruction.
VMCALL causes unconditional VMExit.
It’s for call hypervisor from guest OS, suchfunction is called Hypercall.
Following is simplest handler implementation:

VMCALLIRET
Even program is same, you should have thehandler program for each vector.
Because guest EIP can be use for determine
handled vector number.

4. Implementation
Most of work are rewriting doscmd to fit
BHyVe interface, from FreeBSD virtual 8086
API.
• Code was 64bit unsafe
doscmd was designed only for 32bit x86, and
BHyVe is only for amd64.
So I need to re-write some codes to 64bit safe.
ex:u_long
uint32_t

If you place BIOS interrupt call handler start at
0x400, and program length is 4byte for each
(VMCALL is 3byte + IRET is 1byte), you candetermine vector number from hypervisor withfollowing program:• Guest memory area started from 0x0
To use virtual 8086, doscmd places guest
memory area from 0x0.
But BHyVe’s guest memory area is mapped to
non-zero address, we need to move all address
to BHyVe’s guest memory area.

vector = (guest_eip - 0x400) / 0x4;ex:

BHyVe need to initialize interrupt vector andset pointer of the handler described above.
In this way, it doesn’t take care about modechanges anymore.
Figure 13 shows BIOS interrupt callmechanism on my implementation.
On the implementation, it traps BIOS interrupt
call itself, emulates by hypervisor.

int 13h*(char *)(0x400) = 0;*(char *)(0x400 + guest_mem) = 0;

• Interface with /usr/sbin/bhyve
I don’t wanted to mix doscmd’s complicatedsource code with /usr/sbin/bhyve’s code, so I
modified doscmd’s Makefile to build it as alibrary.
And named it libbiosemul.

Software interrupt(INTx)
CPU reads interrupt vector
Execute pseudo BIOS call handler

Pseudo BIOS issue
VMCALL instruction(Hypercall)

Guest

VMCALL Trap
BHyVe BIOS
Emulation

HyperVisor
Figure 13. BIOS interrupt call mechanism on BHyVe

72

BHyVe emulates BIOS callIt exposed only few functions:void biosemul_init(struct vmctx*ctx, int vcpu, char *lomem, int
trace_mode);
int biosemul_call(struct vmctx*ctx, int vcpu);

biosemul_init is called at initialization.
biosemul_call is main function, which called atevery BIOS call.
• Guest register storage
doscmd stored guest register values on theirstructure, but BHyVe need to call ioctl to get /set register value.
It’s hard to re-write all code to call ioctl, so I
didn’t changed doscmd code.
I just copy all register values to doscmd struct
at beginning of BIOS call emulation, andcopyback it the end of the emulation.
• Instruction level tracing
I implemented instruction level tracer to debug
BIOS emulator.
It’s also uses psuedo BIOS interrupt callhandler to implement.
5. Development status
It still early stage of development, none ofOSes boots up with the BIOS emulator.
I’m focusing to boot-up FreeBSD/amd64, now
mbr and boot1 are working correctly.

73

74

Using BGP for realtime import and export of OpenBSD spamd entries

1

Peter Hessler

Bob Beckphessler@openbsd.org

beck@openbsd.org

OpenBSD

OpenBSD

Introduction

In the battle against spam, many mail server admins collect and distribute IP addresses of systems that have sent
them spam. However, distribution of these lists are traditionally limited to 2 methods. Method #1 is periodicallydownloading this list from a source, usually a web server - which is subject to load issues on the target web server.
#2 is a real-time lookup against an external provider (such as dns-rbls) so your response time is dependent upon
how fast they respond or timeout.
OpenBSD spamd1 is typically used as a daemon to stop the “low hanging fruit” of spam, by subjecting previously unseen hosts to greylisting to allow time to identify it they are a real mailserver. Real mailservers arewhitelisted locally after having passed greylisting, with their connections to the real mailservers monitored via
spamlogd2 . As such spamd keeps a list in a database of what it believes to be currently active “real” mailservers.
This paper suggests and discusses a 3rd solution: using BGP3 to distribute the IP addresses in a real-timemanner. By doing so we can take advantage of OpenBSD spamd’s information to distribute two useful lists via
BGP:
1. Each participant can share their TRAPPED entries from spamd(8) - hosts which the local spamd has determined should not be allowed to pass greylisting. Other hosts can use these lists to also prevent such hosts
from passing greylisting in the short term.
2. By taking advantage of the information kept in spamdb - each participant can share a subset of their WHITE
entries from spamdb, chosen based on criteria that makes them very likely to be real mail servers that arecontinuing to exchange mail with the participating domain on a regular basis. By doing this all participants
can use this information to build a bypass table in pf4 so that all such “real mailservers” talking to any
participant in the network are not subjected to greylisting.
Having a greater amount of information is, of course, a great boon to a mail server administrator. This paper
will show how an admin can use blacklist entries to not only block access from badly behaving mail servers, but,
more importantly, allow access from so-called “known good” mail servers.

1.1

Traditional use of spamd(8)Traditionally, OpenBSD users will use the spamd(8) daemon included with OpenBSD. This daemon will keep
track of hosts it has communicated with, and put them in one of 3 lists. GREY, WHITE, and TRAPPED which
are tracked in spamd’s spamdb5 database.
Whitelisted (WHITE) hosts do not talk to spamd(8), and are instead sent to the real mailserver.

75

Greylisted (GREY) hosts are not on the WHITE or TRAPPED lists. Normally these are hosts for which no
SMTP6 activity has been seen previously. These connections are redirected to spamd(8), and are given a temporary failure message when they try to deliver mail. Greylisted become Whitelisted after they retry delivery of thesame message more than 3 times and are still retrying after 30 minutes of delay.
Trapped (TRAPPED) hosts are hosts which have been identified as doing bad things during the time they are
Greylisted. Typically this is mailing to an unknown or spamtrap user, mailing with invalid smtp usage, or otherspam signature activity. These hosts can be TRAPPED, typically for 24 hours, and will not be allowed to pass
Greylisting during that time. This can be quite powerful because the trapping is only applied to hosts for whichmail has never been exchanged before. As an example, it is not unusual for a legitimate mail server to mail toa large number of unknown users. However, it *is* unusual for a real mail server for which we have never exchanged mail with before to suddenly start mailing unknown users on its first communication with us.
Spamd also has the ability to use external blacklists, where clients on such a list will be given a rejection
message specific to that list. This allows the default Greylisting behaviour to be combined with external lists ofspam sources. The spamd-setup(8)7 utility sends external blacklist data to spamd, as well as configuring mailrejection messages for blacklist entries. This utility uses method #1 to retrieve the list of blacklist entries.
In our case, we use BGP to distribute TRAPPED lists so that they may be used as external BLACK lists - aswell as distributing selected WHITE entries so they can be shared among sites.

2

Definitions: Client vs Route Server vs Spamd Source

In this paper, we will discuss a reference implementation network. The authors will implement this network andit will be available for public use at “rs.bgp-spamd.net”.
There are three important parts of the reference implementation network.
Spamd Source: These systems are feeding the Route Server with IP addresses fed from GREYTRAP and WHITE
lists. They are the source of our spamd list information. Client systems are not able connect directly to the Spamd
Source systems, their information will be sent via the Route Server.
Our reference implementation uses: University of Alberta (aka uatraps), Bob Beck (aka obtuse.com), and Peter Hansteen (aka bsdly.net) as our Spamd Sources.
Route Server: This system is the center hub of the network. Both the Spamd Sources and the Client systems
connect. This system sorts and redistributes the BGP feeds from the Spamd Sources and distributes them to the
Clients.
Our implementation uses the reference server, “rs.bgp-spamd.net”
Client: Any end-user.
Originally using sources from OpenBSD’s /etc/mail/spamd.conf

3
3.1

Using BGP to distribute spamd lists
Basic explanation of BGP

In a traditional BGP network, Router A will send a list of IP networks assigned to itself, to all of its peers. Router
B will also distribute its IP networks, as well as the IP networks assigned to Router A. Router A can mark specific
IP networks with attributes, known as Communities, as a way to communicate with Router B some intentions for76these routes.
Some common examples of community meanings include “do not redistribute to a specific geographical area”,“Prefix this route 3 times (make it less desirable to the peers)”, and “Blackhole this network”.

3.2

Our use of BGP

In this paper, we will use the fact that BGP is designed to distribute IP networks with community attributes to
distribute TRAPPED and certain WHITE entries from spamd. We want to do this for two reasons:
1. We distribute TRAPPED entries from trusted sources to use as BLACK lists - we are assuming that ourtrusted sources have a reasonable criteria for trapping hosts, and that TRAPPED hosts are short lived.
2. We distribute a subset of the WHITE entries from spamd - Our goal is to distribute entries that we areconfident are “real” mailservers based on the information in the spamdb database. This list of “likely goodmailservers” can be used by participants to establish a bgp-spamd-bypass table managed by bgpd8 in pf.
The advantage of this is that “real” mailservers communicating regularly with any participant will not be
subjected to greylisting delays at all participants.
We have chosen some arbitrary BGP Communities for use in marking BLACK list and WHITE entries. The
authors have chosen $AS:666 for BLACK list entries, and $AS:42 for WHITE entries. In this case, $AS will be
expanded to the AS of the originating system. For additional filtering capabilities we will also copy this Community and mark it with the AS on the Route Server.
While it is possible for a regular BGP router to be a member of this experiment, the authors recommend against
it. Clients MUST NOT make routing decisions based on the routes that we send, a large amount of host-specificroutes will be injected into the our BGP network, and care needs to be taken to ensure that the behaviour of one
BGP network does not affect the behaviour of the other. With our sample configuration files, client and server
entities do not need to be directly connected, and can easily be routed over the regular internet, even through NAT.

3.3

Distributing spamd bypass lists

When a previously unseen host hits OpenBSD spamd, it is normally subject to greylisting - meaning initial connections will be delayed and forced to retry for 30 minutes. After 30 minutes, if the same tuple9 of mail is still
being retried the connecting host passes greylisting, and is whitelisted. Whitelisted hosts are kept for 30 days fromthe time traffic from them is last seen, and spamd counts number of connections passed, keeping whitelisted hosts
from being subject to greylisting again as long as they continue to periodically send mail.
Some sites already use the recommendation of a <nospamd> table to bypass spamd for trusted networks often those may include things like Google’s mailserver networks, etc.
What we want for a spamd bypass list from other sources is not to know “this host passed greylisting” - but
rather “I am pretty sure this is a real mail server”. Using BGP puts a new and powerful dimension on this, as
participating systems can send real-time information about hosts that send mail to us.
OpenBSD spamd’s database stores the time entries were first whitelisted as well as how many connections
have been seen to pass to the real mailservers - this can be seen in the spamdb output.
We want to avoid putting “one off” servers - potentially spam software that retries connections, in the spamd
bypass list - So instead what we do is we feed BGP a list of whitelist connections that have been around considerably longer than our expiry period (of 30 days), and who have made more than a trivial number of smtp
connections. At the moment we have chosen any host that has been whitelisted for more than 75 days, and who
has made at least 10 successful smtp connections. These hosts we share out in BGP so that they can be used by
Client systems to bypass spamd checks as they can be considered “trusted”.

77The power of this is then “real” mailservers who frequently exchange mail with one participant will not see
greylisting delays with other participants who share the same bypass list distributed by BGP - effectively a wellchosen bypass list coming from BGP amounts to a dynamic list of established mailservers communicating withall participants contributing to the list.
In our sample configuration, Client systems WILL NOT be allowed to make changes to the distributed lists.
The Route Server WILL reject and ignore all submitted routes from Client systems, and all Spamd Sources are configured to reject connections from unknown systems. Additionally, the connections between the Spamd Sources
and the Route Server are protected with a variety of extra mechanisms, to further prevent generic BGP hijacking
or TCP layer attacks. These policies are to guarantee the integrity of the IP address lists, and to make sure thatincorrect information is not distributed.

3.4Blacklist Source Selection Criteria

In selecting our sources for addresses to use for our blacklist, the authors chose to be very conservative. All upstream Blacklist Sources ONLY select IP addresses that have sent emails to specific spamtrap addresses or haveotherwise been marked as spam by the mail server administrator. These IP addresses are automatically expired
after 24 hours. If the same IP address attempts to send an email to a spamtrap address during that time, the time
counter will be reset.
While manual adding of addresses is possible, this is generally avoided.
The list of Spamd sources was selected by the authors, to be trusted systems with personally known administrators. The authors are concerned about invalid or malicious information being added to the network so care has
been made that all information injected into this network will be based on trusted information.
All IPv4 addresses marked with the BLACK list community are /32 routes, which are IPv4 host-specific routes.
This prevents us from accidentally blocking systems that have not actually sent us any spam, but may be a network“neighbour” of a spammer. This is enforced both on the Spamd source, and the Route Server.
As a side note, many of these sources are also found in the default OpenBSD /etc/mail/spamd.conf configuration file, and are generally well-known to the OpenBSD community.

3.5

Transmission Path from Spamd Source to Clients

When a Spamd Source wishes to add a specific IP address to the distributed whitelist, they run the equivalent of
this command:
bgpctl network add 192.0.2.55/32 community $AS:42
where 192.0.2.55 is the desired IP address, and where $AS is the AS number assigned to this Spamd Source.
Once this address is added to the system, the Spamd Source BGP process will see the new route, and tell allof its peers (including the Route Server) about this new route. When the Route Server receives this, it will thenalso notify all of its peers, including the Client systems. A Client system will receive it, and use the “match ...
set pftable” filter rule to add the IP address to the appropriate PF table.
A script to update the lists distributed by BGP on the Spamd Source is available in the Appendix.

78

4

Sample client configuration

Before we show a sample Client system configuration, the authors wish to show a sample of the output of bgpctl
show rib detail for a single entry, as the information contained is the basis of our filtering. This example isa host route for 192.0.2.55 from AS 65043. The “Communities” entry shows that it has been marked with the“65066:42” and the “65043:42” Communities, which means we can make decisions based on one or both ofthem.
BGP routing table entry for 192.0.2.55/32
65043
Nexthop 198.18.0.191 (via ???) from 203.0.113.113 (203.0.113.113)
Origin IGP, metric 0, localpref 100, weight 0, external
Last update: 02:10:26 ago
Communities: 65066:42 65043:42

4.1

Sample client pf.conf

This section is used to declare what filters will be applied to the various lists in PF. In this sample configuration,
we will add a rule for the WHITE list bypass, to the default spamd(8) ruleset. In this sample, the default spamd(8)ruleset is indented for easy identification.
table <spamd-white> persist# local bypass file.
table <nospamd> persist file "/etc/mail/nospamd"# new bypass file from BGP.
table <bgp-spamd-bypass> persist# we add this line
pass in quick log on egress proto tcp from <bgp-spamd-bypass> to any port smtp
# everything else goes to spamd# Exiting spamd(8) configuration
pass in quick on egress proto tcp from <nospamd> to any port smtp
pass in quick log on egress proto tcp from <spamd-white> to any port smtp
pass in quick on egress proto tcp from any to any port smtp \rdr-to 127.0.0.1 port spamd
pass out log on egress proto tcp to any port smtp

4.2

Sample client bgpd.conf

This section is used to connect to the Route Server and fetch the lists. After the lists are fetched, a filter is used to
add and remove the IP addresses to the specified PF tables.

79/etc/bgpd.conf# Begin bgpd.conf
spamdAS="65066"
AS 65001
fib-update no# Do not change the routing tablegroup "spamd-bgp" {remote-as $spamdAS
multihop 64
enforce neighbor-as no# rs.bgp-spamd.net
neighbor 81.209.183.113
announce none}
# ’match’ is required, to remove entries when routes are withdrawn
match from group spamd-bgp community $spamdAS:42 set pftable "bgp-spamd-bypass"
# EOF

4.3

Using spamd.conf to block BLACK list entries

A naive implementation can simply use PF to block BLACK list entries. This has the obvious disadvantage thatany host that is blocked, will not know it is being blocked and can simply assume that the destination system
is offline. Additionally, there will not be any way for the sender to know it is being blocked on purpose. This
information is necessary for several corner cases, where a mail server triggered the BLACK list entry, but is still
legitimate. In such a case, telling the sending server that they are on the BLACK list, allows for the administrator
to use alternate means of contact to explain why their system should not be blocked.
For these reasons, the authors strongly recommend that Client systems use spamd.conf10 as a means to inform systems on the BLACK list, that they are - in fact - blacklisted.

4.3.1

Blocking of Combined BGP blacklists

Here is a method to simply block all addresses on the BLACK list. This has the advantage of being simple for the
Client system administrator, however it require that the Client system administrator determine the reasons why
any address was blocked.
Below is a simple script for cron to update BLACK lists. It will print the host IP address of each entry to
the /var/mail/spamd.black file, then run spamd-setup (which will be configured next). Here, we use thefact that the Route Serve marks all distributed BLACK list routes with the Community string 65066:666. It is
designed to be run from cron at a frequency faster than the greylist pass time, (for example, every 20 minutes) sothat the trapped lists are updated on a regular basis.

80

/usr/local/sbin/bgp-spamd.black.sh#!/bin/sh
AS=65066
bgpctl show rib community ${AS}:666 | awk ’{print $2}’ | \sed ’s/\/.*$//’ > /var/mail/spamd.black/usr/libexec/spamd-setup# EOF
And a spamd.conf configuration file, for spamd-setup.
/etc/mail/spamd.conf# Configuration file for spamd.conf
all:\:bgp-spamd:
bgp-spamd:\:black:\:msg="Your address %A has sent mail to a spamtrap\n\within the last 24 hours":\:method=file:\:file=/var/mail/spamd.black:
# EOF

4.3.2

Separation of BGP blacklists

Here is a method to use the Communities attribute to separate the blacklists into their original sources. Thismethod has the advantage of informing the sender exactly which list they were listed on so the sender can contact
the originator of the filter list, instead of every mail administrator using these lists. However, the main disadvantage of this is that the Client systems will need to know some internal information about the BGP network, andkeep an up-to-date list in their spamd.conf and helper scripts.
In this example script, the ASes “65042”, “65043” and “65513” are used instead of the Route Server’s AS of“65066”. This is so we can split out these specific upstream Spamd Source that are providing the information. By
specifically enumerating which lists that will be used, this will explicitly ignore any additional ASes that may beproviding us with BLACK list hosts. Users will need to adjust their scripts for local preferences.
The following script is appropriate to update spamd from the BGP BLACK list entries. It is designed to be runfrom cron at a frequency faster than the greylist pass time, (for example, every 20 minutes) so that the BLACK
lists are updated on a regular basis.

81

/usr/local/sbin/bgp-spamd.black.sh#!/bin/sh
for AS in 65042 65043 65513; do
bgpctl show rib community ${AS}:666 | awk {’print $2}’ | \sed ’s/\/.*$//’ > /var/mail/spamd.${AS}.black
done/usr/libexec/spamd-setup# EOF
And a spamd.conf configuration file, for spamd-setup(8).
/etc/mail/spamd.conf# Configuration file for spamd.conf
all:\:bgp65042:bgp65043:bgp65513:
bgp65042:\:black:\:msg="Your address %A has sent mail to a foad.obtuse.com spamtrap\n\within the last 24 hours":\:method=file:\:file=/var/mail/spamd.65042.black:bgp65043:\:black:\:msg="Your address %A has sent mail to a ualberta.ca spamtrap\n\within the last 24 hours":\:method=file:\:file=/var/mail/spamd.65043.black:bgp65513:\:black:\:msg="Your address %A has sent mail to a bsdly.net spamtrap\n\within the last 24 hours":\:method=file:\:file=/var/mail/spamd.65513.black:
# EOF

4.4

Non-OpenBSD Clients

While this paper focuses on using OpenBSD for all 3 types of systems, non-OpenBSD clients can also use theselists for their own anti-spam systems. While specific examples will not be discussed here, any user will need tofilter based on BGP Communities, and insert/remove those addresses into their preferred system - provided theirconfiguration does not alter the routes of the Client system.
Any reimplementation of this network can be done, as long as the Blacklist Source and Route Server systems
are able to add large amounts (150k +) of arbitrary IP host-nets with specific BGP Communities. This is normal
and very common when administering BGP networks, and should be possible with nearly all BGP server implementations.

4.5

Possible Risks to Client systems

While the risks of this configuration are minimal, there are still some possible issues.

821. Use of system resources. On a test system ran by one of the authors, the current (as of 2013-02-08) listof 103k WHITE entries, and 50k BLACK list entries, the bgpd process uses 43.5M of memory, and the
bgp-spamd-bypass PF table is using approx 16M of memory. This can be a problem for low memorymachines.
2. When the bgpd process ends, it will empty the bgp-spamd-bypass PF table and no longer update thespamd.conf BLACK list files. This will cause the amount of whitelisted systems to return to only what has
been seen locally, and the age of the BLACK list entries will quickly grow stale and invalid. The Authors
recommend that Client systems monitor and ensure that the bgpd is running.

5

Sample Route Server configuration

Here we describe an example configuration for the Route Server. In it, we connect to two Spamd Source systems,
and we also provide access for Client systems. Connections to the Spamd Sources are protected. For the Spamd
Source peer “upA”, TCP MD5 signatures are used. For connections to Spamd Source peer “downB”, we will use
IPsec with dynamic keying. The OpenBGPd daemon will set up the flows, and uses isakmpd(8)11 to manage thesession keys.
bgpd.conf follows on next page83

myAS="65066"
AS $myASrouter-id 203.0.113.113
fib-update no
nexthop qualify via default
transparent-as yes
socket "/var/www/logs/bgpd.rsock" restricted
socket "/logs/bgpd.rsock" restrictedgroup blacklist-sources {multihop 64
announce none
# Neighbor upA - John Q Public - john.public@example.com
neighbor 198.51.100.198 {dump all in "/tmp/upA-all-in-%H%M" 3600
descr "upA"
remote-as 65198
tcp md5sig key deadbeef}# Neighbor downB - Mike Bolton - mike@bolt.example.net
neighbor 198.18.0.191 {dump all in "/tmp/downB-all-in-%H%M" 3600
descr "downB"
remote-as 65191
ipsec ah ike}}
group RS {announce all
set nexthop no-modify
enforce neighbor-as noannounce as-4byte no
multihop 64
ttl-security no
holdtime min 60
softreconfig in no
maxprefix 1 restart 5neighbor 0.0.0.0/0 {passive}}deny from any
allow from group blacklist-sources
allow to any# Ensure that an IP to be blacklisted is only a host entry
deny from group blacklist-sources inet \community neighbor-as:666 prefixlen < 32
deny from group blacklist-sources inet6 \community neighbor-as:666 prefixlen < 128# Set my own community, so clients have an easy way to filter
match from group blacklist-sources \community neighbor-as:666 set community $myAS:666

84

6

Security Concerns

This is a completely different BGP network from the global routing table. Any routes added here will not be
visible to or modify the global routing table, and will not prevent any IP traffic from flowing. Using the included
configurations will not change the routing table of any connected system, and will not attempt to steal or re-route
any traffic. Additionally, routes that are delivered to the Client systems are configured in such a way that routes
will not be accepted by the kernel, because the desired nexthop will not be directly reachable.
These routes are intended to be added to the PF table as a way to assist spamd in being more effective - bothin catching hosts that should not make their way through greylisting via a short term block list, and by allowing
real mailservers through via a bypass pf table to avoid greylisting delays. These routes are not intended for use
to restrict general connectivity.

6.1

Security Concerns for Spamd Sources

The sources for spamdb information used must be trusted to provide only valid information to the participants. It
must be agreed ahead of time what the selection criteria for a “real” mailserver is - as well as what the criteria fortrapping hosts is.
If a participant in the system is trapping hosts long term, this will affect all participating sites (for example, if
one participant summarily decides google.com is evil and always traps their hosts, all people using their traplist
to blacklist hosts will be affected). Similarly, if a participant in the system does not apply a sufficient degree ofcare to ensure entries published to the bypass list are “real” smtp servers - you run the risk of more spam leakage
coming through.
Additionally, all sources must themselves be kept secure. Someone with nefarious intent who can manipulate
one of the participant’s BGP servers can easily publish erroneous information to either prevent mail from coming
through at all, or allow lots of spam to bypass spamd. (Imagine if a participant were to advertise 0.0.0.0/0 as amember of the bypass or trapped lists.)
In order to protect the integrity of the IP address lists, it is recommended that Spamd sources protect their BGP
sessions to the Route Servers with security features such as TCP MD5 signatures or IPSec tunnels.

6.2

Security Concerns for Route Servers

The Route Servers MUST NOT accept a default or 0.0.0.0/0 route from Spamd Sources. The Route Serverneeds to ensure that the entire internet is not either WHITE listed, nor BLACK listed.
The Route Server SHOULD NOT accept non-host routes from Spamd Sources. The authors strongly recommend that each and every host to be BLACK listed or WHITE listed instead be explicitly enumerated. Local
implementations may adjust this for their own needs, but the authors recommend that sites be conservative with
their lists, to allow actual behaviour dictate which list a host should be on.
The Route Server MUST NOT accept any entries from Client systems. Client systems are unknown and untrusted, and the administrator does not know of the quality of their lists.
Like all publicly facing systems, Route Servers SHOULD install security patches and be generally kept up to
date.

6.3

Security Concerns for Clients

Client systems SHOULD NOT modify local routing table based on received routes and SHOULD block only smtp
traffic based on the received routes. The ability to ping or connect to a website on the same IP address as a BLACK
list host is valuable, as well as emailing the administrator of the BLACK list host. Additionally, WHITE entries

85should not modify the routing table, as we are only listing host IP addresses, and not a “better” route for these hosts.

7

Future Work

Future work on this topic include collecting statistics about the addresses being distributed, as well as the churnrate. Additionally, work on simplifying inserting the traplist addresses into spamd(8) is desired.

8

Acknowledgements

Many thanks to Peter N.M. Hansteen of BSDly.net, Bob Beck of obtuse.com, and the University of Alberta at
ualberta.ca for being sources of spamdb information.
Thanks to Claudio Jeker and Stuart Henderson for assistance with BGP design and behaviour.

9

Availability

This paper, as well as client configuration examples are available at
http://www.bgp-spamd.net/
It is planned that the reference server “rs.bgp-spamd.net” will provide this service for the entirety of calendar
year 2013. In December 2013, there will be an announcement about the future status of this project.
Please note that this reference server is an experiment and is subject to modification and closing. The authors
will attempt to provide reasonable notice before closing the list, however no guarantees can be made.
An announcement mailing list will be available via the website, for important Client system announcements,
as well as the general status of the reference implementation.

Appendix
The following is appropriate to update the BGP source from spamd output. It is designed to be run from cron ata frequency faster than the greylist pass time, (for example, every 10 minutes) so that the trapped lists are updated
before machines are passed on other sites.
#!/usr/bin/perl# Copyright (c) 2013 Bob Beck <beck@obtuse.com> All rights reserved.
## Permission to use, copy, modify, and distribute this software for any# purpose with or without fee is hereby granted, provided that the above# copyright notice and this permission notice appear in all copies.
## THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
# perl to parse spamdb output and deal with bgpd. can take multiple# spamdb output from multiple mail servers on command line, talks# to bgpd on localhost to update whitelist.

86

# for typical use from a number of spamd collectors collect spamdb output# in a number of files, and then run this script on the bgpd machine with# all the files as command line args to the script.
# so typical use from cron is either## ssh machine1 "spamdb" > machine1.spamdb# ssh machine2 "spamdb" > machine2.spamdb# bgpspamd.perl machine1.spamdb machine2.spamdb## If bgpd is not running on the spamd machine, or if spamd and bgpd are# only running on the same machine## spamdb | bgpspamd.perl#
use integer;# AS to use - please change from this value.
my $AS = 65535;# community string for spamd bypass - where trusted whitelist entries get sent.
my $CS = 42;# community string for spamd traps - where we send traps.
my $TCS = 666;
# These two control how we pick only good whitelist entries to# recommended for spamd bypass - we want to only send things we are# relatively certain are "real" mailservers - not leakage from# spam software that retries. for this to be effective we do have# to be logging real connecitons to our mailservers and noticing# them with spamlogd.
## Only distribute white entries that are older than 75 days
my $agelimit = 3600 * 24 * 75;# Only distribute white entries that have made more than 10 smtp connections.
my $maillimit = 10;
my %ips;
my %tips;
my $key;
while (<>) {my $now = time();if (/^WHITE/) {chomp;
my @line = split(/\|/);
if (($line[5] < $now - $agelimit) && $line[8] > $maillimit) {$ips{"$line[1]"}=1;}} elsif (/^TRAPPED/) {chomp;
my @line = split(/\|/);$tips{"$line[1]"}=1;}}
open (BGP, "bgpctl show rib community $AS:$CS|") || die "can’t bgpctl!";
while (<BGP>) {if (/^AI/) {chomp;
my @line = split;
my $ip = $line[1];87$ip =~ s/\/.*$//;$ips{$ip}-=1;}}
close(BGP);
open (BGP, "bgpctl show rib community $AS:$TCS|") || die "can’t bgpctl!";
while (<BGP>) {if (/^AI/) {chomp;
my @line = split;
my $ip = $line[1];$ip =~ s/\/.*$//;$tips{$ip}-=1;}}
close(BGP);
foreach $key (keys %ips) {if ($ips{$key} > 0) {system "bgpctl network add $key community $AS:$CS > /dev/null 2>&1\n";} elsif ($ips{$key} < 0) {system "bgpctl network delete $key community $AS:CS > /dev/null 2>&1\n";}}foreach $key (keys %tips) {if ($tips{$key} > 0) {system "bgpctl network add $key community $AS:$TCS > /dev/null 2>&1\n";} elsif ($tips{$key} < 0) {system "bgpctl network delete $key community $AS:$TCS > /dev/null 2>&1\n";
}
}

Notes
1 spamd(8), spamd - spam deferral daemon, OpenBSD manual pages
2 spamdlogd(8), spamlogd - spamd whitelist updating daemon, OpenBSD manual pages
3 RFC4271, Y. Rekhter, T. Li, and S. Hares, ”A Border Gateway Protocol 4 (BGP-4)”, January 2006
4 pf(4), pf - packet filter, OpenBSD manual pages
5 spamdb(8), spamdb - spamd database tool, OpenBSD manual pages
6 RFC 822, Postel, J., ”SIMPLE MAIL TRANSFER PROTOCOL”, August 1982
7 spamd-setup(8), spamd-setup - parse and load file of spammer addresses, OpenBSD manual pages
8 bgpd(8), bgpd - Border Gateway Protocol daemon, OpenBSD manual pages
9 connecting IP address, HELO/EHLO, envelope-from, and envelope-to of the connection
10 spamd.conf(5), spamd.conf - spamd configuration file, OpenBSD manual pages
11 isakmpd(8), isakmpd - ISAKMP/Oakley a.k.a. IKEv1 key management daemon, OpenBSD manual pages

88Calloutng: a new infrastructure for timer facilities in the
FreeBSD kernelDavide Italiano

Alexander Motin

The FreeBSD Project

The FreeBSD Project

davide@FreeBSD.org

mav@FreeBSD.org

ABSTRACTIn BSD kernels, timers are provided by the callout facility,
which allows to register a function with an argument to becalled at specified future time. The current design of thissubsystem suffer of some problems, such as the impossibility of handling high-resolution events or its inherent periodic
structure, which may lead to spurious wakeups and higher
power consumptions. Some consumers, such as high-speed
networking, VoIP and other real-time applications need abetter precision than the one currently allowed. Also, especially with the ubiquity of laptops in the last years, theenergy wasted by interrupts waking CPUs from sleep may be
a sensitive factor. In this paper we present a new design andimplementation of the callout facility, which tries to address
those long standing issues, proposing also a new programming interface to take advantage of the new features.

Categories and Subject Descriptors[Operating systems]; [Software Engineering]: Metrics—complexity measures, performance measures

Keywords
Kernel, Timers, C, Algorithms, Data structures, POSIX

1.

INTRODUCTION

A certain number of computer tasks are generally driven bytimers, which acts behind the scenes and are invisible foruser. For example, network card driver needs to periodically poll the link status, or the TCP code needs to know
when it is time to start retransmission procedures after acknowledgement not received in time. In FreeBSD [1] andother BSD kernels, the interface that allows programmer toregister events to be called in the future takes the name ofcallout. The design of this subsystem was not modified foryears and suffers of some issues, such as measuring time in
fixed periods, waking up the CPU periodically on each period even if there are no events to process, inability group
together close events from different periods, etc.
The calloutng project aims to create a new timer infrastructure with the following objectives:• Improve the accuracy of events processing by removing
concept of periods• Avoid periodic CPU wakeups in order to reduce energy
consumption• Group close events to reduce the number of interrupts
and respectively processor wakeups• Keep compatibility with the existing Kernel Programming Interfaces (KPIs)• Don’t introduce performance penalties
The rest of the paper is organized as follows: Section 2 gives
a relatively high-level description of the design as originallyproposed and some improvements have been done during
the years in FreeBSD-land, while Section 3 deeply analyzes
the problems present in the current approach. In Section
4 the new design and implementation are explained and its
validity is shown via experimental results in the successive
section. The work is concluded with some considerations
and future directions.

2.

STATE OF THE ART

The callout code in FreeBSD is based on the work of Adam
M. Costello and George Varghese. A detailed description
can be found in [2]. The main idea is that of maintaining anarray of unsorted lists (the so-called callwheel, see Figure 1)
in order to keep track of the outstanding timeouts in system.
To maintain the concept of time, the authors used a global
variable called ticks, which keeps track of the time elapsed
since boot. Historically, the timer was tuned to a constantfrequency hz, so that it generated interrupts hz times per
second. On every interrupt function hardclock() was called,incrementing the ticks variable.
When a new timeout is registered to fire at time t (expressedin ticks), it’s inserted into the element of the array, addressedby (t mod callwheelsize), where callwheelsize is the size ofthe array and mod indicates the mathematical modulo operation. Being the lists unsorted, the insertion operation
takes minimal constant time. On every tick, the array element pointed by (ticks mod callwheelsize) is processed to see
if there are expired callouts, and in such cases the handler
functions are called. If callwheelsize is chosen to be comparable to the number of outstanding callouts in the system,
lists will be (in average) short.
The main advantage of using this strategy relies on its simplicity: the callout code has O(1) average time for all theoperations, and O(1) worst case for most of them. In orderto process events, the code needs only to read a global kernel variable, which is very cheap, in particular compared to
hardware timecounter, which can be quite expensive. Also,
this design requires neither specific hardware architecture89

Figure 1: The callwheel data structure

nor specific OS infrastructure. It needs only a timer (norestrictions, because almost any timer has the ability to periodically generate interrupts or simulate this behaviour),and a subsystem for handling interrupt.
While the current FreeBSD implementation shares basic
concepts with the mechanisms described above, it evolved
quite a bit during the years, introducing substantial improvements in term of performances/scalability and specifying a different programming interface. About the former,
the single callwheel was replaced by a per-CPU callwheels,
introducing respective migration system (2008).
For what concerns the latter, it is provided via an additional
function that consumers can use to allocate their callouts,
namely callout init() and its locked variants (callout init mtx(),
callout init rw() ...). This way the callout subsystem doesn’t
have to deal internally with object lifecycle, passing this responsibility to the consumer.
Also, KPI was extended, in order to reflect the introductionof per-CPU wheels, adding a new callout reset on() function, that allows to specify a CPU to run the callout on. It
worth to say that the callout processing threads are not hardbound to each CPU, so they can’t be starved into not processing their queues. They are medium bound by ULE andprobably tend to run where they are scheduled on 4BSD but
there is no guarantee. The ULE will run them on their native CPU if it’s running something of lower priority or idle.
If it’s running something of greater priority, it will look fora more idle CPU. This prevents the softclock thread frombeing starved by other interrupt thread activity.

3.

PROBLEMS WITH CURRENT IMPLEMENTATION. The constant frequency hz determines the resolution atwhich events can be handled. On most FreeBSD machines
this value is equal to one thousand, which means that one
ticks corresponds to 1 millisecond. This way, even a function which specify timeout using accurate time intervals withresolution of one nanosecond (e.g. nanosleep) will see thisinterval rounded up to the nearest tick, i.e. it will be likethe resolution is one millisecond. As soon as many callers
require interval to be no shorter than specified, the kernel
has to add one more tick to cover possibility that present
tick is almost over. As result, the best we can get is resolution of one millisecond with one millisecond of additional
latency.
Also, independently from the time for which the next event

90

is scheduled, CPU is woken up on every tick to increment the
global ticks variable and scan the respective bucket of thecallwheel. These spurious and useless CPU wakeups directlytranslate in power dissipation, which e.g. from a laptop user
point of view results in a reduction of the on-battery time.
Stiil talking about power consumption, the actual mechanism is unable to coalesce or defer callouts. Such a mechanism could be useful for istance in low power modes, where
the system could postpone check for a new CD in the drive
if CPU is sleeping deep at the moment.
The last but not the least, all the callouts currently run
from software interrupt thread context. That causes additional context switches and in some cases even wakeup ofother CPUs.

4.

A NEW DESIGNIn order to address the first of the present problems, the interfaces to services need some rethinking. For what concern
the kernel, all the Kernel Programming Interfaces dealing
with time events are built around the concept of ’tick’. All
consumers specify their timeouts via the callout *() interface
as relative number of ticks. ’ticks’ variable is a 32-bit integer,
and it is not big enough to represent time with resolution of
microseconds (or nanoseconds) without quickly overrunning(overflowing). Change is definitely needed there in order toguarantee higher granularity.
For what concern the userland, the Application Programming Interfaces (APIs) and data types are standardized byPortable Operating System Interface (POSIX), so they cannot be changed without losing compliance. Luckily, mostof the functions provide variants with acceptable degree ofprecision.
Let’s take, as an example, the nanosleep() system call. This
service asks the kernel to suspend the execution of the calling thread until either at least the time specified in the firstargument has elapsed, or the call will be aborted by signaldelivered to the thread. The function can specify the timeout up to a nanosecond granularity.
Other services (e.g. select()), which monitor one or more filedescriptor to see if there’s data ready, can limit the amountof time they monitor. This time is specified in one function
argument. Differently from what happen in the previous
case, the granularity is that of microseconds. Unfortunately,
as long as all those system calls dealing with timeouts rely
on callout(9) at the kernel level, they’re limited by the precision offered by the kernel. So, as first step a new data typeis needed to represent more granular precision.
From a system-wide perspective, FreeBSD has the following
data types to represent time intervals:
struct timespec {time_t tv_sec;
long tv_nsec;};
struct timeval {time_t tv_sec;
long tv_usec;};
struct bintime {time_t bt_sec;
uint64_t bt_frac;};

The first type allows to specify time up to microseconds
granularity, while the second up to nanosecond one. The
common part between the two representation is that they’re
pseudo-decimal. Conversely, the bintime structure is a binary number, and this has some advantages, first of all making easier mathematical operations on the type. Dependingon the underlying architecture, these struct have different
sizes. In particular, they range respectively from 64 to 128
bit (for timeval and timespec) and from 96 to 128 bit (forbintime) [3].
The binary nature of bintime could make it suitable for our
purposes (in fact it was originally chosen as default datatype), but there are some problems that should be considered. First of all, using 128 bit (on amd64, probably themost widely spread platform) is overkill, because at best
hardware clocks have short term stabilities approaching 1e8, but likely as bad as 1e-6. In addition, compilers don’t
provide a native int128 t or int96 t type.
The choice made was that of using A 32.32 fixed point format, fitting it into an int64 t. Not only this makes mathematical operations and comparison trivial, but allows also
to express ’real world’ units for time such as microseconds
or minutes trivially.
typedef sbintime_t
int64_t;#define SBT_1S ((sbintime_t)1 << 32)#define SBT_1M (SBT_1S * 60)#define SBT_1MS (SBT_1S / 1000)#define SBT_1US (SBT_1S / 10000000)#define SBT_1NS (SBT_1S / 10000000000)

Now that the type is decided, the programming interface inthe kernel requires to be adapted. Changing existing functions arguments is considered discouraging and intrusive,
because it creates an huge KPI breakage for third-party software, considering the popularity of callout in many kernelsubsystems, including device drivers. So it’s been decided tomaintain the old set of functions, introducing a new set ofalternative functions, which rely on the aforementioned chosen type to represent time. Other than changing a field inorder to specify the expiration time, the new field has been
introduced in order to specify precision tolerance. This field
may be provided by the consumer to specify a tolerance interval it allows for the scheduled callout. In other words,
specifying a non-zero precision value, the consumer gives anhint to the callout backend code about how to group events.
To sum up, the resulting KPI takes the following form:
int callout_reset_sbt_on (..., sbintime_t
sbt, sbintime_t precision, int flags);

Some functionalities, e.g. the precision-related bits, may be
useful also in the old interface. A new KPI for old customers
also has been proposed, so that they can take advantage ofthe newly introduced features.
int callout_reset_flags_on (..., int
ticks, ..., int flags);

Thus, an extension was made to the existing condvar(9),sleepqueue(9), sleep(9) and callout(9) KPIs by adding tothem functions that take an argument of the type sbintime t

instead of int (ticks to represent a time) and a new argument
to represent desired event precision. In particular:
int cv_timedwait_sbt (..., sbintime_t sbt, sbintime_t precision);
int msleep_sbt (..., sbintime_t sbt,
sbintime_t precision);
int sleepq_set_timeout_sbt (...,
sbintime_t sbt, sbintime_t precision);

In parallel to the KPI changes, there’s need to adapt thecallout structure in order to store the added bits. The structcallout prior to changes had the following form:
struct callout {...
int c_time;
void *c_arg;
void (*c_func)(void *);struct lock_object *c_lock;int c_flags;
volatile int c_cpu;};

As the reader can easily imagine, the c time field, which
stores the expiration time need to be replaced to sbintime t
in order to keep track of the new changes. Similarly, to store
precision, a new field need to be added. Although the callout
interface doesn’t require direct access to the elements of the’struct callout’, which is an opaque type, clients need to allocate memory for it using the callout init functions.. The result is that the size of the struct callout is a part of the KBI.
The use of larger data types leads to an increase in the sizeof the structure and inevitably break the existing KBI. Thischange requires rebuilding of almost all the kernel modules
and makes impossible to merge these changes to the existing STABLE branch, because the FreeBSD policy requires(or at least recommends) to preserve binary compatibility
among different releases with the same major number (inthis case FreeBSD-9).

Changes to the backend data structure
During the initial planning stage we’ve analyzed possibilityof using different tree-based data structures to store events.
They can provide much better results on operation of fetching the first event, but have more complicated insertion andremoval operation. As soon as many events in system arecancelled and never really fire (for example, device timeouts,
TCP timeouts, etc.), performance of insert/remove operations is more important. But tree-like algorithms typicallyhave O(log(n)) complexity for such operations, while callwheel has only O(1). Also tree-like algorithms may require
memory (re-)allocation during some insert operation. That
is impossible to do with present callout locking policy, thatallows to use it even while holding spin-locks.
As result, the underlying design has been maintained, butslightly refreshed. The wheel is going to use as hash key
subset of time bits, picking some of them from the integer
part of sbintime t and some from the fractional, so that the
key changes sequentially approximately every millisecond.
The new hash function is translated into code as follows:91

Figure 2: Old and new callout hash keys compared#define CC_HASH_SHIFT

10

static inline int
callout_hash(sbintime_t sbt){}

return ((int)(sbt >> (32 CC_HASH_SHIFT))) & callwheelmask;functions introduced in kernelspace allow to specify it asabsolute or relative value. In order to store it, the callout
structure has been augmented by adding a ’precision’ field oftype struct bintime, which represents the tolerance interval,
allowed by the consumer of callout. Unfortunately, this is
not possible for the old interface. None of existing functions
in kernel space and none functions in userspace have such (orsimilar) argument, and therefore only an estimation might
be done, based on the timeout value passed and other global
parameters of the system (e.g. hz value). The default levelof accuracy (in percentage, for example) can be set globally
via the syscontrol interface.
The possibility of aggregation for events is checked every
time the wheel is processed. When the callout process()function is executed, the precision field is used together withthe time field to find a set of events which allowed times
overlap, which can be executed at the same time.

where the last bitwise AND operation realizes modulo being
callwheel size constrained to be a power-of-two. The compared behaviour of the hash in the two cases is shown in
Figure 2. The following motivations affect callwheel parameters now:
• The callwheel bucket should not be too big to not rescan events in current bucket several times if several
events are scheduled close to each other.
• The callwheel bucket should not be too small to minimize number of sequentially scanned empty buckets
during events processing.
• The total number of buckets should be big enough tostore (if possible) most of events within one callwheel
turn. It should minimize number of extra scanned
events from distant future, when looking for expired
events.
As result, for systems with many tick-oriented callouts, bucket
size can be kept equal to the tick time. For systems withmany shorter callouts it can be reduced. For mostly idle
low-power systems with few events it can be increased.

Obtaining the current time
The new design poses a new challenge. The conversion to
struct bintime instead of tick-based approach to represent
time makes impossible to use low-cost global variable ticks to
get the current time. There are two possibilities to get timein FreeBSD: the first, going directly to the hardware, using
binuptime() function, the second, using a cached variablewhich is updated from time to time, using getbinuptime().
It was decided to use a mixed approach: in cases where highprecision needed (e.g. for short intervals) use heavy but
precise function binuptime(), and use light but with 1ms
accuracy getbinuptime() function in cases where precision
is not essential. This allows to save time by using better
accuracy only when necessary.

Accuracy
In particular situations, e.g. in low-power environments,
for the correct and effective use of resources, events needto have information about the required accuracy. The new92

Figure 3: Traditional and SWI-less callout
comparison

CPU-affinity and cache effects
The callout subsystem uses separate threads to handle theevents. In particular, during callout initialization, a software interrupt threads (SWI) for each CPU are created, andthey are used to execute the handler functions associated tothe events. Right now, all the callouts are executed using
these software interrupts. This approach has some advantages. Among others, that it is good in terms of uniformity
and removing many of limitations, existing for code, executing directly from hardware interrupt context (e.g. the ability to use non-spin mutexes and other useful locking primitives). However, the use of additional threads complicatesthe job of the scheduler. If the callout handler function will
evoke another thread (that is a quite often operation), thescheduler will try to run that one on a different CPU, aslong as the original processor is currently busy running the
SWI thread. Waking up another processor has significant
drawbacks. First of all, waking up another processor fromdeep sleep might be a long (hundreds of microseconds) andenergy-consuming process. Besides, it is ineffective in termsof caches usage, since the thread scheduled on another CPU,
which caches unlikely contain any useful data.
Let’s see an example. Some thread uses the tsleep(9) interface to delay its execution. tsleep(9) at a lower-level relies on
the sleepqueue(9) interface, which uses callout(9) to awake
at the proper time. So what’s happening in the callout execution flow: the SWI thread is woken up for the single
purpose of waking up the basic thread! And as describedabove, very likely wake it up on another processor!
The analysis shows, that example above is relevant to all
customers using sleep(9), sleepqueue(9) or condvar(9) KPIs,
and respectively all userland consumers which rely on thoseFigure 4: Calloutng performances on amd64:
absolute precision

primitives: poll(2), select(2), nanosleep(2), etc.
In order to solve this problem the mechanism of direct execution has been implemented. Using the new C DIRECT EXEC
flag the callout(9) consumer can specify that event handler
can be executed directly in the context of hardware interrupt. This eliminates the use of SWI for this handler by
the cost of enforcing additional constraints. According to
our tests, use of this technique, where applicable, allows significantly reduce resource consumption and latency of theevent processing, as well as, in theory, improve efficiency
and reduce pollution of the CPU caches.

5.

Figure 5: Calloutng performances on amd64: 5
percent precision tolerance

EXPERIMENTAL RESULTS

When using TSC timecounter and LAPIC eventtimer, the
new code provides events handling accuracy (depending on
hardware) down to only 2-3 microseconds. The benchmarks(real and synthetic) shown no substantial performance reduction, even when when used with slow timecounter hardware. Using the direct event handlers execution shown significantly increased productivity and accuracy, while also
improving system power consumption.
The following tests have been run measuring the actual sleep
time of the usleep() system call, specifying as input a sequential timeout starting from one microseconds and increasing it. The system used was Intel(R) Core(TM) i7-2600K
CPU @ 3.40GHz, equipped with 8GB of RAM. The couple
LAPIC+TSC has been used. In the graphs the x-axis represent the input passed to usleep() and the y-axis represent
the real sleep time, both expressed in microseconds. Figure 4 shows how calloutng behaves when the users requires
absolute precision, while Figure 5 show the result when the
precision tolerance has been set to 5 percent, in order toreduce the number of interrupts and exploit the benefits ofaggregation. The same two tests have been repeated alsoon ARM hardware, SheevaPlug – Marvell 88F6281 1.2GHz,
512MB RAM, and the corresponding results are shown in
Figure 6 and Figure 7.

Figure 6: Calloutng performances on ARM:
absolute precision

93

Figure 7: Calloutng performances on ARM: 5
precent precision tolerance

6.

CONCLUSIONSThe code written as part of this project going to be thepart of the forthcoming FreeBSD 10.0 release. Further wider
deployment of newly implemented APIs in different kernelsubsystems will provide additional benefits. Some user-level
APIs could be added later to specify events precision for the
specified thread or process.

7.

ACKNOWLEDGMENTS

We would like to thank Google, Inc. (Google Summer ofCode Program, 2012 edition) and iXsystems, Inc. for sponsoring this project, as well as the FreeBSD community forreviewing, discussing and testing the changes we made.

8.

REFERENCES[1] The FreeBSD Project. http://www.freebsd.org/.
[2] A. M. Costello and G. Varghese. Redesigning the BSD
Callout and Timer Facilities. November 1995.
[3] P.-H. Kamp. Timecounters: Efficient and precise
timekeeping in SMP kernels. June 2004.

94

SCTP in Go
Olivier Van Acker
Department of Computer Science and Information Systems
Birkbeck University of London
London, United Kingdom
Email: olivier@robotmotel.com
Abstract—This paper describes a successful attempt to combine two relatively new technologies: Stream Control Transmission Protocol (SCTP) and the programming language Go,
achieved by extending the existing Go network library with
SCTP.
SCTP is a reliable, message-oriented transport layer protocol,
similar to TCP and UDP. It offers sequenced delivery of messages
over multiple streams, network fault tolerance via multihoming
support, resistance against flooding and masquerade attacks
and congestion avoidance procedures. It has improvements overwider-established network technologies and is gradually gaining
traction in the telecom and Internet industries.
Go is an open source, concurrent, statically typed, compiled
and garbage-collected language, developed by Google Inc. Go’s
main design goals are simplicity and ease of use and it has asyntax broadly similar to C. Go has good support for networked
and multicore computing and as a system language is often used
for networked applications, however it doesn’t yet support SCTP.
By combining SCTP and Go, software engineers can exploit theadvantages of both technologies. The implementation of SCTP
extending the Go network library was done on FreeBSD and
Mac OS X - the two operating systems that contain the most up
to date implementation of the SCTP specification.
Index Terms—Stream Control Transmission Protocol (SCTP);
Transmission Control Protocol (TCP); Go; Networking;I. I NTRODUCTION
This paper will look into combining two relatively newtechnologies: a network protocol called SCTP and the programming language Go. Both technologies claim to offer
improvements over existing technologies: SCTP does awaywith the limitations of the widely used TCP protocol (author?)[8]; and Go was designed with simplicity and minimized programmer effort in mind, thereby preventing a forest of features
getting in the way of program design: Less is exponentiallymore (author?) [6]. The current version of the Go network
library does not support the SCTP protocol and this paper
examines how easy it is to extend the Go network librarywith this protocol. The work in this paper is based on thedissertation submitted for an MSc in Computer Science at
Birkbeck University in London and is available as an open
source project.
A. Relevance
After ten years SCTP as a technology is becoming more
and more relevant. One notable implementation is the use of
SCTP as a data channel in the Web Real-Time Communication(WebRTC) standard (author?) [11], a HTML 5 extension to
enable real time video and audio communication in browsers.

Google inc. and the Mozilla Foundation are each planning
to release a browser this year implementing the WebRTC
standard. Go as a language is very new and it is too early
to say what impact it will have. It does however receive a lotof media attention since it is developed by Google. It is also
growing in popularity because of its ease of use as a concurrent
system language (author?) [1].
B. Outline
Section II presents an overview of Go and SCTP, followedby (section III) a description of how the TCP socket API
is integrated in the Go networking library. This is a starting
point for the design of an SCTP extension to the network
library in Go, described in section IV. Section V explains
the implementation. Section VI analysis the results and VII
concludes.
II. T ECHNOLOGY OVERVIEW
In this section I will give an overview of the main featuresof SCTP and Go.
A. SCTPSCTP was initially developed in response to the demandsof the telecoms industry, which was not satisfied with thereliability and performance of TCP (author?) [10, p. 15].
During the design phase the decision was made to make SCTP
a less telephony-centric IP protocol (author?) [10, p. 16] sothat it could also be used for more generic data transport
purposes.
1) Comparison with TCP: It is fruitful to compare TCP and
SCTP, as TCP is the most widely-used protocol (author?) [5]and SCTP is very similar to it:2) Multihoming: A host is said to be multihomed if it has
multiple IP addresses which can be associated with one ormore physical interfaces connected to the same or different
networks(author?) [2]. TCP can only bind to one network
address at each end of the connection. In the event of a network
failure there is no way to stay connected and send the data overanother physical path without setting up a new connection.
SCTP natively supports multihoming at the transport layer.
This makes it possible to connect and transfer data to andfrom multihomed hosts, so that when one network path fails,
the connection seamlessly fails over using the remaining
paths. And together with concurrent multipath transfer (CMT)(author?) [4] it is possible to increase data throughput by
transferring data simultaneously over multiple links.

953) In-built message boundaries: In TCP there are no markers to indicate the start or end of a specific piece of data (auser message). All data sent over the socket is converted into
a byte stream and an application must add its own mechanism
to be able to reconstruct the messages. In SCTP the message
boundaries of the data sent are preserved in the protocol. In theevent of the message being larger than the maximum package
size a notofication is sent to the application layer more is on
its way.
4) Protection against Denial of Service (DOS) attacks:
Another disadvantage of TCP is that it is open to ’SYN flood
attack’, a specific type of attack which can drain the serverof resources, resulting in a denial of service (nothing else canconnect). To prevent this, SCTP uses a four-way handshake toestablish the connection, whereas TCP only uses a three-way
handshake. With a four-way handshake the originator has todouble-acknowledge itself (”is it really you?”) by resending
a cookie it previously received from the destination server
before that server will assign resources to the connection. This
prevents timeouts on the server side and thus makes this typeof denial of service impossible. To reduce start up delay, actual
data can also be sent during the second part of the handshake.

Figure 2: Head of line blocking
9 user messages ready to be send

9

8

7

6

5

4

3

2

1

3

2

1

1 to 7 are send, message 4 does not arrive

9

8

7

6

5

7

6

5

7 to 4 are resend

9

8

4

Figure 3: Associations and streams
Application

Application

Streams

Streams

Port

Multiple IP addresses

SCTP

Port
SCTP

IP

IP

Figure 1: Initiating a network connection(a) TCP handshake(b) SCTP handshake

IP network

SCTP association

5) SCTP Multistreaming: SCTP user messages in a single
SCTP socket connection can be sent and delivered to theapplication layer over independent streams. In case of two setsof user messages A and B, each set delivered sequentially, themessages of set A can be sent over a different stream than B.
And in case a messages in set A gets missing and part of thesequence needs to be resent this will not effect the data of set
B if it is sent over a different stream. This tackels the ’headof line blocking’ problem (figure 2) where messages alreadydelivered need to be redelivered because they have to arrivein order and becuase one message did not arrive.
6) Associations: A connection between a SCTP server andclient is called an association. An association gets initiatedby a request from a SCTP client. So a listening server canaccept incoming requests from multiple clients. Messages sent
over the assocation have an association id attached to them.
to make it possible to know where they come from. Within
a single association you can have multiple streams for datatransmission (See figure 3)
7) Two programming models: SCTP has two interfaces for
implementation in a networked application: one-to-one and96

one-to-many. A single socket in a one-to-many model can havemultiple incoming associations, meaning that multiple clientscan connect to a single server listening on a single socket.
The one-to-one model can only have a single association
per socket. The one-to-one model is for easy migration ofexisting TCP applications, it maps one-to-one to the system
calls TCP makes to establish a connection. But it can only
have one connection per association, and thus only a single
client can connect to a server. The one-to-one interface makes
migrating an existing application a relatively painless exercise.
If you want to upgrade your existing TCP application to a
one-to-many SCTP application, significant retooling is needed.
(author?) [7, p. 267]
8) Socket API: Figure 4 is an overview of two applications
communicating over an IP network using a transport protocol(TCP, UDP or SCTP). The software engineer writing the clientand server in the application layer only has to know about
the function calls exposing the functionality in the transportlayer. This collection of functions is called the socket API. A
socket is an endpoint for networked communication; multiple
processes can open sockets via the API and data written into
one socket can be read from another. The socket API consistof functions which can open and close the socket, send dataover it and set the behavior of a socket using ’socket options’.
An example of such behavior is the enabling or disabling ofdata buffering before sending to reduce the number of packets
to sent over the network and therefore improve efficiency

Figure 4: Socket API

User processapplication protocol

Networked
clientFigure 6: Ancillary data embedded in sendmsg() data structure
msghdrNetworked
serverapplication layer

Socket API
TCP
UDP
SCTP

Transport protocol

TCP
UDP
SCTP

transport layer

Kernelmsg_namesockaddr

msg_iov

iovec

SCTP_SNDINFO

msg_control

IP protocol

IP

network layer

snd_ﬂags
snd_ppid
snd_context

cmsghdrIP

snd_sid

cmsg_level&

sctp_sndinfo

snd_assoc_id

cmsg_type
Ethernet protocol

EthernetdriverEthernetdriverdatalink layer

Ethernet

Table I: Ancillary data mappings
sid
ssn
ppid
aid

(Nagle’s algorithm).
Figure 5: TCP and SCTP socket API
TCP
ServerSCTP
ClientServersocket()socket()bind()bind()

listen()socket()accept()connect()

recv()

ﬂags

Clientstream identifier
stream sequence number
identifier set by peer
association id

and ancillary data (see appendix E). SCTP adds extra metadata which contains information about the message being sent
and its connection. Table I gives an overview of the ancillarydata mapped to the return variables.
B. Go language overview

listen()socket()send()

recvmsg()

sendmsg()send()

recv()

sendmsg()

recvmsg()

close()

close()

close()

close()

9) SCTP Socket API: Figure 5 is an overview of both the
TCP and SCTP socket APIs and gives the order in which thesystem calls would be used in a simple client server application
sending and receiving messages. The server first creates asocket, this returns a file descriptor which can be used by thebind function to to make a request to assign a address to it.
After this the server can start listening to incoming connections
with the listen() function. After this point TCP is different from
SCTP. The TCP client actively connects to the peer and theserver accepts the connection with the accept() and connect()functions. With SCTP the connection set up hand handshakehappens implicitly when sending and receiving a message. At
this point the server and client can exchange messages andfinally the connection terminates with the close() function.
10) Socket I/O functions and ancillary data: The sendmsg()
and recvmsg() functions (see appendix D for definition) are
the most general of all socket I/O functions (author?) [7, p.
390] and can be used in combination with all protocols in thetransport layer. Both functions have room for message data

In this section I will give a short overview of the mainfeatures and characteristics of the Go language and provide
more detail where relevant to the project.
1) Data: Go has a syntax broadly similar to the C andJava languages. Variables are declared either by variable namefollowed by data type, or by name only with data type inferred(known as ’type inference’).’ With the initialization operator :=variables can be declared and initialized in a single statement.
If not initialized explicitly, the variable is set to a default value.
Here are some examples:var number i n t
var f i r s t _ n a m e , last_name s t r i n g
var g r e e t i n g = h e l l o ( " o l i v i e r " )f r a c t a l : = make ( [ ] uint64 , 10)

Go has two ways to create data structures: i) with ’new’,
where the data structure is initialized to zero; ii) with ’make’,
where the data structure is initialized to a specified value.
var p ∗ [ ] i n t = new ( [ ] i n t )var v [ ] i n t = make ( [ ] i n t , 100)

An asterisk indicates that the variable is a pointer.
2) Functions: Unlike most commonly-used languages Go
functions and methods can return multiple values. The following function expects a string and integer as input parameters
and returns a string and an error. If the count integer is zerothe function will return a nil and an error, otherwise it returns
the greeting and nil as error.

97

func h e l l o ( name s t r i n g , count i n t ) ( g r e e t i n gstring , e r r e r r o r ) {i f count = 0 {r e t u r n n i l , e r r o r s . New( " Cannot say
h e l l o zero t i m e s " )}g r e e t i n g = " H e l l o " + name , n i lreturn}ing example, in function main, a cat object gets created,
it talks and then gets cast (type changed) to an animal
object:type animal i n t e r f a c e {Talk ( )}type Catfunc ( c Cat ) T a l k ( ) {f m t . P r i n t l n ( "Meow" )}This hello function can be be called in the following
manner:g r e e t i n g , e r r : = h e l l o ( " paard " , 0 )i f err != n i l {println ( " error ! " )} else {println ( greeting )}Or if we are not interested in one of the return values, ablank identifier _ can be used to discard the value:g r e e t i n g , _ : = h e l l o ( " paard " , 1 )3) Object and methods: In Go data structures (objects) aredefined as follows:
type Person s t r u c t {name s t r i n g
age i n t}Functionality can be added to an object by defining methods
associated with it. A difference between Go and other objectoriented languages like Java is that in Go this functionality isdefined outside of the object, for example:
func ( p Person ) SayHello ( name S t r i n g ) {r e t u r n " H e l l o " + name " , my name i s " + p . name}In the above example the SayHello method has a string as
input and is associated with a Person object p.
Methods can be associated with any type, not just objects.
In the following example the Add() method is associated withan Array of strings:
type NameArray [ ] s t r i n gfunc ( na NameArray ) Add ( name s t r i n g ) [ ] s t r i n g {...
}It’s worth noting that Go has objects but not inheritance.
4) Interfaces : As with other object oriented languages,
you can specify behavior of an object by using interfaces
and also implement multiple interfaces per object. The interfaces does not have to be explicitly named: as soon as
the type implements the methods of the interface the compiler knows the relation between the two. In the follow-

98

func main ( ) {var c Catc . Talk ( )a : = animal ( c )a . Talk ( )}/ / Cast from c a t t o animal5) Pointers: Although Go has pointers (references to memory locations), they are implemented differently than in alanguage like C. Pointer arithmetic is not possible so Go
pointers can only be used to pass values by reference. At alower level Go pointers can be converted to C pointers.
6) Concurrency: Go has a basic primitive for concurrency called a goroutine. The name is not only a play on
a programming component called coroutine but is also its
implementation of it in the language. Coroutines are methods
which call on each other, data comes in, gets processed andgets passed to a the next coroutine. One of the advantages ofcoroutines is they are generally easier to create and understand[Knuth V1 p193]. But the main advantage is that it lends
itself very well for distributed computing where data gets
passed around from one processor to another, maybe even ona different computer.
In Go every function can become a goroutine by simple
putting go in front of it. A gorouting can than communicate
its input and output via channels. This concept is called
Communicating sequential processes (CSP) and is surprisingly
versatile in its use. (author?) [3] Here an example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

package main
func receiveChan ( c i chan i n t ) {for {i : = <− c iprintln ( i )}}func main ( ) {c i : = make ( chan i n t )go receiveChan ( c i )}f o r i : = 0 ; i < 1 0 ; i ++ {c i <− i}

The receiveChan() function has as input a channel ofintegers. On line 4 an endless for loop starts where line 5
waits for an integer to come in on the channel. The mainfunctions first creates a channel of integers. Line 12 starts thefunction receiveChan as a Go routine in the background. Thisis followed by a loop sending 10 integers over the channel tothe receiveChan function.
7) Much more: There is more to the language like garbage
collection, first class functions, arrays, slices, however the
explanation of this falls outside the scope of this paper. Moreinformation can be found on the Go website 1 .
III. G O NETWORKINGThe following section contains the findings of my researchon how Go combines the system level TCP socket API into
an easy-to-use network library and how that works internally.
Much of the TCP functionality is very similar to the SCTP
stack and this will serve as an example of how to implement
SCTP in Go.
A. The network library
Go provides a portable interface for network I/O. Basicinteraction is provided by the Dial, Listen, ListenPacket andAccept functions which return implementations of the Conn,
PacketConn and Listener interfaces. The Listen function isfor byte stream data connections and the ListenPacket is fordata transfer which includes messages boundaries, like UDPor Unix domain sockets. These functions simplify the accessto the socket API, but if needed the application developer canstill access the socket API in more detail.
Here is an example of a typical TCP client and server
application. The client sends a single message and the server
waits to receive a message, prints it out after receiving andstarts listening again. First a simple client:
1
2
3
4
5
6
7
8
9
10
11

package main
import " n e t "func main ( ) {conn , e r r : = n e t . D i a l ( " t c p " , " l o c a l h o s t :1234 " )i f err != n i l {return}defer conn . Close ( )conn . W r i t e ( [ ] byte ( " H e l l o w o r l d ! " ) )}The function main() is the entry point of the program.
The first step the client performs is ’dialing’ a server with
the TCP protocol (line 5). The Dial() function returns a
connection which is an implementation of the Conn interface.
After checking for errors (6-8) the defer keyword before theconnection close command indicates the connection can befinished as soon as it is no longer needed. In this case it
happens immediately after the write so it does not make muchsense to defer it, but in larger programs with multiple exit
points you only need a single (deferred) close statement, whichmakes it easier to understand and maintain the program.
Next the server:
1 http://golang.org/doc/effective_go.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

package main
import " n e t "func main ( ) {l i s t e n , e r r : = n e t . L i s t e n ( " t c p " , " l o c a l h o s t :1234 ")i f err != n i l {return}b u f f e r : = make ( [ ] byte , 1024)for {conn , e r r : = l i s t e n . Accept ( )i f err != n i l {continue}
conn . Read ( b u f f e r )println ( string ( buffer ) )}}The server gets created with the Listen() method and returns
an object which implements the Listener interface. On line 9
a byte array buffer gets created for the received data. The
following for loop (10 - 17) will continuously wait to accept
an incoming connection (11), check for errors after connect,
read from it (15) and convert the byte array to a string before
printing it (16).
B. Under the hood
Go’s network communication library uses the same socket
API as any C program. In this section I will examine what
happens when a network connection is set up and which socket
API calls are made at what point. The example uses TCP. To
illustrate how Go accesses the socket API I will take the TCP
client described in the previous section as an example andshow how it interacts with the kernel by opening a connection.
Socket and Connect: For a TCP client to create a connection
and send some data the following system calls need to be madein this order:
1) resolve IP address2) socket()3) setsockopt() (optional)4) connect()
In Go all this is wrapped in the net.Dial() call.
Figure 8 shows a sequence diagram of method calls after aclient calls Dial(). First the hostname:port gets parsed and resolved to an IP address (1.1)2 . Net.dialAddr() (1.3) determines
the transport protocol type and calls the relevant method,net.DialTCP() in this case (1.3.1). Next net.internetSocket()gets called which internally calls socket() in the syscall package. Syscall.socket() is an auto-generated method based on C
header files which describe the socket API.
Every network protocol in Go has its own connection type.
As you can see in figure 8 the generic Dial() method eventuallyreaches the specific DialTCP() method which returns a TCPspecific connection type. This type gets cast to the moregeneric Conn type which can be used in the client application.
If TCP-specific functionality is needed the Conn type can be
2 There are more method calls behind this but they are not relevant for thisexample99

recast to a TCPConn which then makes it possible to access
TCP-specific functionality.

Figure 7: Go SCTP network API
ServerClientnet.ListenPacket()socket()C. Auto-generationbind()

net.Dail()

Native Go functions to access kernel system calls and data
structures can be auto-generated via scripts. In FreeBSD, if thedescription of the system call is present in the syscalls.master
file 3 , the function will be available through the syscall
package. Most system calls which are used in Go are wrapped
in methods to make them fit better the language. The structures
which are passed to the system calls are created in the sameway. The source code directory of the syscall package contains
a file with a link pointing to a header file which describes the
structures.

D. Go non-blocking networking
All networking in Go is non blocking which is not thedefault in the TCP/IP model. As soon as a application tries
to retrieve data from a socket, e.g. via readmsg(), it will notblock until some data comes in, instead it will immediately
move on in the program. Reading data from the socket isnormally done in an endless loop. To make Go actually wait
for sending data back to the application Go implements thereactor design pattern. The implementation of this software
pattern makes use of a mechanism in the kernel where you
can ask the kernel to send a signal back to the application
if certain events occur whilst you keep doing other things in
the program. For example data being written to the socket
descriptor. On BSD the system call kqeueu() and kevent() areused to register and queue events. The functionality of this ishandled by Go’s runtime.

IV. D ESIGNIn the following section I will describe how the different
Go network methods will map to the SCTP socket API.

3 Systemcall
name/number
http://fxr.watson.org/fxr/source/kern/syscalls.master100

masterfile:

listen()socket()PacketConn.ReadFrom()

Conn.WriteTo()recvmsg()

sendmsg()

PacketConn.WriteTo()Conn.WriteTo()

sendmsg()

recvmsg()

PacketConn.Close()

Conn.Close()close()

close()

A. Mapping APIs
The SCTP socket API will follow closely the wrapping of
the TCP socket API in the Go network library as describedin section III-B. Figure 7 show the mapping of the socket
API to the different functions and methods. At the server side
the socket(), bind() and listen() functions are bundled into the
ListenPacket() function which resides in the network package(net). The ListenPacket() function returns an implementationof the PacketConn interface (See appendix B). The client
wraps the socket() function into the Dail() function. Thisfunctions returns a Conn (connection) interface which canused for writing messages (Conn.WriteTo()) and these user
messages can be received vie the ReadFrom() method on the
PacketConn interface.
B. SCTP specific1) Receive SCTP specific information : To access SCTP
specific functionality, such as which stream the message has
been sent on, or the association id, net.ListenSCTP() can beused. This method returns a SCTP specific type (SCTPConn)which has the method ReadFromSCTP() and WriteToSCTP()
added to it. These methods return and set the information
contained by the SCTP receive information structure, added
as ancillary data when the system call recvmsg() returns.
2) Send SCTP specific information: To be able to set SCTP
specific send information such as stream id or association id
via the SCTP Send Information Structure, the several methods
on the SCTPConn object can be used (See table II):
Table II: Initialization parameters
Number of output streams
Max number of input streams
Max number of attempts to connect
Timeout(*SCTPConn) InitNumStreams(n int) error(*SCTPConn) InitMaxInStream(n int) error(*SCTPConn) InitMaxAttempts(n int) error(*SCTPConn) InitMaxInitTimeout(n int) error

A typical server which has access to SCTP specific functionality would look like this:package main
import (" net "
" strconv ")func main ( ) {addr , _ : = n e t . ResolveSCTPAddr ( " s c t p " , " l o c a l h o s t :4242 " )conn , _ : = n e t . ListenSCTP ( " s c t p " , addr )defer conn . Close ( )for {message : = make ( [ ] byte , 1024)_ , _ , stream , _ : = conn . ReadFromSCTP ( message )p r i n t l n ( " stream " + s t r c o n v . I t o a ( i n t ( stream ) ) + " : "+ s t r i n g ( message ) )}}In this program ListenSCTP returns a SCTP connection
type. This type implements Conn and PacketConn interface
and has the ReadFromSCTP method added to it. The println()functions prints the stream id and the user message.
V. I MPLEMENTATIONIn this section I will describe how the SCTP network
functionality can fit into the existing Go network framework.
The main goal of the SCTP application programming interface(API) design is to combine lower-level system calls in aneasy-to-use framework. This framework hides the underlying
complexity of the socket API but if needed gives access to
all the functionality provided by the protocol. To make sure
SCTP fits in the Go design philosophy, less is more, I will
make use as much as possible of the existing components andinterfaces in the Go network package. In the following section
I’ll eA. Server
For a server to be able to set up a SCTP association it
needs to create a socket, bind to it, optionally set some socket
options and start listening to it. A typical server will accessthe socket API in the following sequence:
1) socket()2) bind()3) listen()4) recvmsg()
The socket(), bind() and listen() functions will be wrapped
into a Listen() method which returns a connection type.
There are three variations: net.Listen(), net.ListenPacket()and net.ListenSCTP(). The Go network library provides thenet.ListenPacket() method for packet-oriented networking like
UDP, and net.Listen() for stream-oriented networking like
TCP. SCTP which is packet-oriented, can also make useof the net.ListenPacket() method. ListenPacket() returns animplementation of the PacketConn interface which can be used
to read and write messages (recvmsg()). A simple SCTP echo
server using the PacketConn interface might look like this:package main
import " n e t "func main ( ) {conn , _ : = n e t . L i s t e n P a c k e t ( " s c t p " , "l o c a l h o s t :4242 " )defer conn . Close ( )message : = make ( [ ] byte , 1024)
conn . ReadFrom ( message )p r i n t ( s t r i n g ( message ) )}After the the main entry point a connection object is created
via the ListenPacket() method. The parameters of this method
indicate that the connection should use the SCTP protocol
and listen on localhost port 4242. The next line defers theclosing of the connection when it is not needed anymore. After
creating a byte array buffer to store incoming data a message isread from the connection. The ReadFrom() method will block
until a message is received. Finally the message is printed andthe program ends.
Receive SCTP-specific information: To access SCTPspecific functionality, such as which stream the message has
been sent on, or the association id, net.ListenSCTP() can beused. This method returns a SCTP-specific type (SCTPConn)which has the method ReadFromSCTP() added to it:( ∗SCTPConn ) . ReadFromSCTP ( message ∗ s t r i n g ) ( s i d
i n t , ssn i n t , p p i d i n t , a i d i n t , addr
SCTPAddr , e r r e r r o r )The ReadFromSCTP() method returns the information contained by the SCTP receive information structure, added asancillary data when the system call recvmsg() returns. A
typical server which has access to SCTP-specific functionality
would look like this:package main
import (" net "
" strconv ")func main ( ) {addr , _ : = n e t . ResolveSCTPAddr ( " s c t p " , " l o c a l h o s t:4242 " )conn , _ : = n e t . ListenSCTP ( " s c t p " , addr )defer conn . Close ( )for {message : = make ( [ ] byte , 1024)_ , _ , stream , _ : = conn . ReadFromSCTP ( message )p r i n t l n ( " stream " + s t r c o n v . I t o a ( i n t ( stream ) )+ " : " + s t r i n g ( message ) )}}In this program ListenSCTP() returns a SCTP connection
type. This type implements the Conn and PacketConn interfaces and adds the ReadFromSCTP() method.
B. Client
In Go a client connection sets itself up with a call to theDial() method. The Dial() method returns the generic Conn101

interface. Every network protocol in Go has its own Dial()
method which returns a protocol-specific connection type. In
the case of SCTP this is the PacketConn type which has
underneath it a specific SCTP connection type (SCTPConn).
A simple SCTP client sending a single message would look
like this:package main
import " n e t "func main ( ) {addr , _ : = n e t . ResolveSCTPAddr ( " s c t p " , " l o c a l h o s t:4242 " )conn , _ : = n e t . DialSCTP ( " s c t p " , n i l , addr )defer conn . Close ( )message : = [ ] byte ( " paard " )conn . WriteTo ( message , addr )}B. Fitting like a glove
Since Go already provides methods and interfaces formessage-based data transmission that could be reused, andbecause of the SCTP socket API’s similarity to the TCP socket
API, making SCTP available in the Go network library was a
relatively straightforward task. I was able to reuse the ancillarydata structure from the Unix socket API and had only to add
the SCTP-specific ancillary data to the structure. It was easy
to follow the design philosophy ’less is exponentially more’:
the SCTP socket API could be wrapped in an easier-to-use
API, just as it is done with TCP. This resulted in a Go SCTP
API which can be used in the most simple way, hiding allcomplexity of the protocol or, if needed, it is possible to dive
deeper and make use of more specific SCTP functionality.
C. Issues during implementation

The DialSCTP() method creates the socket and sets default
socket options. Sending the message via WriteTo() will implicitly set up the connection.
Send SCTP-specific information: To be able to set SCTPspecific send information such as stream id or association id
via the SCTP Send Information Structure, the WriteToSCTP()
method can be used:(∗SCTPConn ) . WriteToSCTP ( message ∗ s t r i n g , addr
SCTPAddr , s i d i n t , ssn i n t , p p i d i n t , a i d i n t ,err error )Creating and binding of the socket : The sequence diagramin figure 9 gives an overview of how a socket is created andbind to. At point 1.1.3 in this figure net.internetSocket() returns
a socket descriptor which is used to create the actual SCTP
connection type. At this point the SCTP initialization structure
is set to its default values together with the NODELAY socket
option. The ’no delay’ socket option disables buffering ofbytes sent over the connection. This is also the default setting
for the TCP implementation in Go.
VI. A NALYSIS
A. Performance
For performance testing a client-server application was
designed, with the client sending messages and the server
receiving them. Both a C and a Go version of this application
were created and compared and run against each other. The
data throughput of an SCTP client-server application written in
Go is approximately twice as high as the same program written
in C. Most of the delay happens in the Go client. Unlike the C
implementation, the Go application needs to go through some
additional method calls before it reaches the system call which
sends the data. Go is also garbage-collected, which causes anextra delay because several data structures are redeclared eachtime a message is sent. Another factor to consider is that theimplementation of SCTP in Go is against version 1.0.2 of
Go. This version does not have a compiler which is good at
optimizing. Newer versions of Go address this issue.

102

During implementation there were two major changes thatcaused unexpected setbacks. The first, as previously mentioned, was the changing SCTP socket API, which made large
parts of the implementation already in place obsolete, forcing
me to rewrite the majority of the implementation. The second
issue was the first official release (1.0) of Go. Until that release
I had sporadically synchronized my version of Go with thelatest changes of the main development tree of the canonical
Go source code repository. Building up to the official release
the Go development team did a considerable amount of work.
With the 1.0 release a large number of changes had to beincorporated into my own branch. As there were many changes
to the internals of Go, this resulted in many merge conflicts
in certain areas, specifically around the implementation of thegeneric Dial and Listen interfaces. Most of the work in thisarea had to be redone.
D. Extensions
There are many extensions to SCTP described in multiple
RFCs. A complete SCTP implementation should include (author?) [9]:1) RFC4960 (basic SCTP)
2) RFC3758 (partial reliability)
3) RFC4895 (authentication)4) RFC5061 (dynamic addresses)
The last three in this list are not included in this implementation.
VII. C ONCLUSION
Because of its similarity to existing protocols available
in the Go networking library, SCTP fits easily into it. The
biggest challenges of this project were the ongoing work on
the SCTP specification and Go itself which made successful
implementation a moving target. More recently (mid-way2012) the APIs of Go and SCTP have been stabilized. It
should be noted however that there are many extensions to
SCTP described in multiple RFCs. The work in this paper
only looks at the bare minimum needed to make SCTP workin Go.

A PPENDIX

A. Future work
A. Conn interface
User land implementation of SCTP in Go: Not all operating
systems support the SCTP protocol natively. It is however
possible to have SCTP running on top of the UDP protocol,
outside the kernel (user land). To make this work a user land
implementation of SCTP on top of UDP needs to be added
to Go. Once this is done SCTP could become available on all
different platforms supported by the Go language.

type Conn i n t e r f a c e {Read ( b [ ] byte ) ( n i n t , e r r e r r o r )W r i t e ( b [ ] byte ) ( n i n t , e r r e r r o r )Close ( ) e r r o rLocalAddr ( ) Addr
RemoteAddr ( ) Addr
SetDeadline ( t t i m e . Time ) e r r o r
SetReadDeadline ( t t i m e . Time ) e r r o r}

R EFERENCES

S e t W r i t e D e a d l i n e ( t t i m e . Time ) e r r o r

B. PacketConn interface
type PacketConn i n t e r f a c e {ReadFrom ( b [ ] byte ) ( n i n t , addr Addr , e r r e r r o r )[1] WhyweneedgoOReilly
radar.
http://radar.oreilly.com/2012/09/golang.html.
[2] R. Braden. Requirements for internet hosts - communication layers. http://tools.ietf.org/html/rfc1122.
[3] C. A. R. Hoare. Communicating sequential processes.
Communications of the ACM, 21(8):666–677, August
1978.
[4] Janardhan R. Iyengar, Paul D. Amer, and Randall Stewart. Concurrent multipath transfer using SCTP multihoming over independent end-to-end paths. IEEE/ACM
Trans. Netw., 14(5):951–964, October 2006.
[5] B. Penoff, A. Wagner, M. Tuxen, and I. Rungeler.
Portable and performant userspace SCTP stack. In 2012
21st International Conference on Computer Communications and Networks (ICCCN), pages 1 –9, August 2012.
[6] Rob Pike. command center: Less is exponentially more.
http://commandcenter.blogspot.co.uk/2012/06/less-isexponentially-more.html, June 2012.
[7] W. Richard Stevens, Bill Fenner, and Andrew M. Rudoff.
Unix Network Programming: Sockets Networking API v.
1. Addison Wesley, 3 edition, November 2003.
[8] R. Stewart.
RFC 4960 - stream control
transmission
protocol,motivation.
http://tools.ietf.org/html/rfc4960#section-1.1.
[9] Randall Stewart, Michael Tuexen, and Peter Lei. SCTP:
what is it, and how to use it? BSDCan 2008, 2008.
[10] Randall R. Stewart and Qiaobing Xie. Stream Control
Transmission Protocol (SCTP): A Reference Guide. Addison Wesley, 1 edition, October 2001.
[11] Michael Tuexen, Salvatore Loreto, and Randell
Jesup.
RTCWebdatagramconnection.
http://tools.ietf.org/html/draft-ietf-rtcweb-data-channel00.

WriteTo ( b [ ] byte , addr Addr ) ( n i n t , e r r e r r o r )Close ( ) e r r o rLocalAddr ( ) Addr
SetDeadline ( t t i m e . Time ) e r r o r
SetReadDeadline ( t t i m e . Time ) e r r o r}

S e t W r i t e D e a d l i n e ( t t i m e . Time ) e r r o r

C. Listener interface
type L i s t e n e r i n t e r f a c e {Accept ( ) ( c Conn , e r r e r r o r )Close ( ) e r r o r}Addr ( ) Addr

D. Socket IO function definitions s i z e _ t sendmsg ( i n t s , const s t r u c t msghdr ∗msg , i n t f l a g s )s s i z e _ t recvmsg ( i n t s , s t r u c t msghdr ∗msg , i n t f l a g s )E. Message header structure and ancillary datas t r u c t msghdr {void∗msg_name ;/∗socklen_t
msg_namelen ;/∗s t r u c t i o v e c ∗msg_iov ;/∗int
msg_iovlen ;/∗void∗ msg_control ;/∗socklen_t
msg_controllen ; /∗int
msg_flags ;/∗};The msg_control argument,
msg_controllen,
pointstoao p t i o n a l address ∗ /s i z e o f address ∗ /s c a t t e r / gather array ∗/# elements i n msg_iov ∗ /a n c i l l a r y data ∗ /a n c i l l a r y data b u f f e r l e n ∗ /f l a g s on message ∗ /whichbufferhasforlengthother103

Figure 8: TCP Client setting up connection

net.Dial()

1:

net.resolveNetAddr()

net.ResolveTCPAddr()

net.dialAddr()

net.DialTCP()

net.internetSockets()syscall.socket()

1.1:
1.1.1:

1.1.2: TCPAddr
1.2: Addr

1.3:
1.3.1:
1.3.1.1:
1.3.1.1.1:

1.3.1.1.2: int

1.3.1.2: netFD
1.3.2: TCPConn

1.4: Conn

104

Figure 9: Creating and bind

net.ListenPacket()1:

net.ListenSCTP()

net.internetSocket()net.socket()syscall.Socket()syscall.socket()syscall.Bind()1.1:
1.1.1: resolve address
1.1.2:

1.1.2.1:
1.1.2.1.1:

1.1.2.1.1.1:
1.1.2.1.1.2:

1.1.2.1.2:
1.1.2.1.3:

1.1.2.1.4:

1.1.3:

1.1.2.2:

1.1.4: listen
1.1.5:

105

protocol control related messages or other miscellaneous ancillary data. The messages are of theform:s t r u c t cmsghdr {s o c k l e n _ t cmsg_len ;/ ∗ data b y t e count , i n c l u d i n g hdr ∗ /int
cmsg_level ; / ∗ o r i g i n a t i n g p r o t o c o l ∗ /int
cmsg_type ;/ ∗ p r o t o c o l −s p e c i f i c t y p e ∗ // ∗ f o l l o w e d by u_char cmsg_data [ ] ; ∗ /};106

The surprising complexity of TCP/IP checksums in the network
stack
Henning Brauer
BS Web Services

Abstract
TCP and IP have well known and well understood checksum mechanisms. The actual
checksum math is easy and, from a performance standpoint, so cheap that it can be considered free. In the process of improving theuse of hardware checksum offloading engines,
recalculating the IP checksum has been foundto be essentialy free. However, that is not thecase for the TCP and UDP checksums, which
was partially expected. On further inspection asurprising complexity in dealing with the protocol checksums has been found.
We’ll look at how these checksums are calculated, where the complexity comes from, how
an ancient BSD performance hack made it into
hardware offloading engines, the stack interaction and issues with hardware offloading engines.

1

Introduction

For a long time I had been annoyed by thechecksum handling in pf. pf used to fix up
checksums on the fly, as in, whenever it modified a packet - which it would do for all formsof NAT, for example - it adjusted the original checksum for the applied word delta. This
is not only annoying and error prone in many
places, it also lead to deeply nested calls to
pf cksum fixup. When Theo de Raadt some-when in 2009 or 2010 pointed me to one ofthese super ugly and not exactly efficient nested
pf cksum fixup calls, i knew it was time to lookdeeper into the issue.
On top of this, there is a long standing bugwith said checksum fixup and packets pf redirected to localhost and checksum offloading,a bug that Christian Weisgerber (naddy@) has
explained to us pf people repeatedly over theyears, but it was neither easy to follow nor to
fix.
Eventually, at the k2k10 hackathon in Iceland, I started looking into our checksum handling in general, and the findings were quite interesting.

2

Checksum Calculation

The actual calculation of the checksum is quite
simple. The checksum is the lowest word of
the one-complement sum of all the words thechecksum covers, basically.

3

General Performance Considerations

After years of profiling our network stack it isclear that the actual math here is so cheap that it
can be considered free on every halfway modern system. The actual integer units are neverour bottleneck, the limiting factors are latency

107

and bandwidth to caches, memory and devices.
Thus, a checksum covering a few fields thathave been touched very recently and thus are incache is almost free. A checksum covering awhole bunch of data that hasn’t been accessed
yet at all is expensive, since the data has to beread from RAM, which is relatively slow.
The actual checksum algorithm has optimized assembler implementations on many
platforms we support. Wether these handoptimizied versions are actually faster than thegeneric C version is an interesting question thathas not been evaluated here.

4

The IP Checksum

The checksum in the IP header (referred to as
the IP checksum) covers the IP header. It has
to be updated by each router forwarding thepacket as it updates the ttl field. IPv6 does nothave this checksum.
Since this checksum only covers the relatively small IP header and several fields of thatheader have just been accessed before, recalculating it is pretty much free. The performanceadvantage of offloading it to a capable NIC is sosmall that it gets lost in the noise when trying
to measure it.

5

IP Checksum Implementation in
OpenBSDIn our network stack - and similiar in the other
BSD-derived stacks - an incoming IP packet ishandled in ip input(). Besides a lot of validity
checks, ip input() decides wether that packet
is to be delivered locally, in which case it ishanded off to upper layers, to be forwarded or
to be dropped as undeliverable, e. g. when
forwarding is off. The inbound pf test() call,which makes pf examine the packet, is alsohere.
In the forwarding case, the packet is handed
off to ip forward, which deals with routing and108

ttl decrementation. The actual route lookup andsome other related tasks are already done in
ip input(), as an implementation side-effect. If
the packet is to be forwarded it gets handed off
to ip output().
ip output() checks and, for locally generated
packets, fills in a lot of the IP header fields. The
outbound pf test() call is here as well. Rightafter the pf test call the ip checksum is recalculated unconditionally, last not least to cover the
ttl decrement for forwarded packets, possible
changes done by pf. Locally generated packets do not even have a checksum at this pointand get it filled in.
At this point it seems obvious that the ip
checksum fixup done all over the place in pf
is useless work, since the ip checksum is recalculated just after pf in ip output anyway, andinbound the check happens before pf. However, pf is not only called from ip input() and
ip ouput(). There also is the bridge case - thebridge calls pf test() too, and the bridge does ofcourse not decrement the ttl, nor does it makeother changes to the IP header, thus it does notrecalculate the ip checksum after pf. This isalso the reason why the bridge is special-cased
all over the stack.
The solution to this problem is to make thebridge behave like a regular output path. To
complicate matters, checksum offloading enters the picture.

6

IP checksum offloading

Pretty much every network interface chip/cardmade in the last decade is capable of performing the ip checksum calculation in hardware.
To make use of that, our stack has been modified a long time ago to delay the actual checksum calculation up until we definately know onwhich interface the packet is going to be sent
out. We can then check wether the interface inquestion has matching offload capabilities, indicated via interface flags. If so we don’t needto do much more but to mark the packet for
hardware checksumming. If not, we calculate
the ip checksum in software.
To know wether a packet needs checksumming at all we use a flag in the mbuf packet
header, a structure attached to the packet datafor bookkeeping in throughout the stack. Everywhere we know the packet needs checksumming we plain set this flag.
This works fine for all the regular output
pathes. It doesn’t for the bridge, due to its lackof checksum handling alltogether.
The bridge code is quite old and not exactly
an example for good programming. It is hard tofollow. Adding the missing checksum handlingin its output pathes - there is unfortunately evenmore than one - turned out to be not so easy.
Once this was done and the bridge special casing all over the stack removed, things mostly
worked. Some weird behaviour was eventually
tracked down to problems with broadcase packets, and upon closer inspection the bridge uses
a gross hack to shortcut broadcast processing,so that a packet that supposedly goes out to achecksum offloading capable interface can getcopied and sent out on another interface, potentially without matching offloading capabilities.
This resulted in packets being sent out unchecksummed in that case.
Fixing the broadcast hacked was not straightfoward, this needs to be adressed at a latertime. The special casing in the stack had tostay. However, with that basic checksum handling and the special casing in place, we wereable to stop doing any ip checksum handling in
pf, since now all output pathes recalculate thechecksum if necessary.
Since recalculating the ip checksum is socheap even in software on any halfway modern
system performance improvements from thischange were to small to be really measurable.

7

The TCP and UDP checksums

The tcp and udp, often referred to as protocol
checksums, are quite a different beast from theip checksum. They only cover a few ip header
fields, that part is called pseudo header checksum, the tcp/udp header and the entire payload. Due to the full payload coverage recalculating the protocol checksum is not as cheap.
While chances are good that the payload is stillin cache for locally generated packets, the forwarding case almost certainly means fetching
the payload from RAM, since we don’t touch itfor pure forwarding otherwise.
As with the ip checksum, pf used to update
the protocol checksum on the fly, with the sameproblems as with the ip checksum, just in moreplaces.

8

protocol checksums in
OpenBSD network stackthe

The procotol checksum handling is much more
complex than the ip checksum. As all BSDderived network stacks OpenBSD used protocol control blocks, in short pcbs, to track connections. Even for udp, which is a connectionless protocol - connectionless on the wire
doesn’t mean that the stacks don’t have somekind of state. The pcbs are looked up usinghash tables, or, in OpenBSD, by following thelink to them from the pf state.
When a socket is opened, a template pcb
for connections from or to this socket is created. The known parts are already filled inand checksummed. Once a connection is madeusing that socket, the template pcb is copied,the other side’s information is added, and thechecksum updated for that. This only covers
the ip header parts, not the protocol header, andforms the pseudo header checksum. The packet
is marked for needing checksumming at thispoint and then passes on to get protocol header
and payload.

109

Eventually, late in the outbound path, theflag indicating a checksumming need is evaluated. If the interface that this packet should goout on has matching offloading capabilities, wedon’t need to do anything, otherwise we do thechecksumming in software. That’s the theory,at least.
The early calculated pseudo header checksum is a hack that might have made sense on
a hp300 or a vax, but is counterproductive on
any halfway modern system and foremost complicated things considerably. This is where thepf redirect to localhost problem comes from.
Some network interface cards - last not least intel and broadcom - implemented their offloading engines so that they rely on this hack, by
relying on the pseudo header checksum being
there.
However, when such a packet passes throughpf, we don’t know that it just has a partial
checksum, and happily update it for fields it
doesn’t cover. On a packet that originated fromlocalhost and gets rewritten by pf - prime example being replies to packets that have beenredirected to localhost - we have exactly thatand end up with a broken pseudo header checksum. For cards that rely on and just update it
we end up with broken checksums on the wire.
Both the software engine as many other interface hardware recalculate the entire checksumand don’t care about the existing pseudo-header
checksum.
As with the ip checksum the bridge code had
to be updated for this output path to behave.

9

protocol checksum offloading

As with the ip checksum, almost all halfway
recent network interface chips and cards support tcp and udp checksum offloading, at least
for IPv4. Things are considerably more complicated here tho, since we have to deal with 3
offloading cases: no offloading, pseudo header
checksum required, and full offloading. Since110

the pseudo header case was broken due to the pf
handling, protocol checksum offloading is disabled in the drivers in this case.
Unfortunately we have seen many silicone
bugs with offloading. While that mostly affects
early implementations and is long history, we
have recently seen a case with an Intel 10GE
chip that corrupted ospf packets - ospf is neither udp nor tcp! - when the tcp/udp offloading
engines were turned on.

10changing the stack to make better use of offloading engines

The basic principle is easy: work under the assumption that we have always have offloading
engines. If we hit a path that doesn’t, provide a
software fallback.
To accomodate for this, the actual checksumming has been moved far down in the stack andis done pretty much as late as possible now,
when we know for sure wether we have an outgoing path with offloading capabilities. That allows for removal of pretty much all checksum
handling everywhere else in the stack, we justhave to set the flag now to ask for checksumming.
Subsequently, all ip and protocol checksum
adjustments have been removed from pf, withjust the flag modifications remaining. This has
interesting consequences. Since we are not updating but recalculating the checksum for forwarded packets that are modified by pf now,that case suffers if there is no checksum offloading available, since we have to access theentire payload. With pretty much any system made in the last 10 years supporting offloading, only the case where pf modifies forwarded packets (that means NAT mostly) being affected, and preventing this - by calculating the pseudo header checksum before and after pf making changes and applying the delta
to the existing checksum - hurts machines withoffloading capabilities, this seems acceptable.

Since we are not updating the checksum any
more but recalculating, we have to consider thecase of broken checksums. Adjusting a broken checksum leads to a broken checksum, so
all’s good - but if we’re recalculating, we haveti verify the old checksum first. Again, in manycases we already have that check performed by
the hardware offloading engines already, if not,we have to fall back to software. This again
punishes hardware without offloading capabilities, but is not fixable without punishing the offloading case substantially. On a halfway modern i386 or amd64 system with disabled offloading capabilities the total hit is in the 5 to
10traffic mix - exact numbers vary a lot withspecific hardware implementations. And thesesystems have offloading capable interfaces.
Last not least this finally allows us to enable
the protocol checksum offloading on the interfaces requiring the pseudo header checksum,
since pf won’t munge the checksum any more.

truncated packets are tiny, so the cost is minor.
In my current implementation this is not done,
since nothing in the real world cares about the
inner checksum. The only case I am aware of isscapy, a program generate and verify packets.

11

13

ICMP

ICMP has a checksum too. The icmp checksum handling has been remodeled after the tcp
and udp case, instead of calculating the checksum early on and every time changes are being
made, we just set the flag. Late and way downin the stack we check the flag and calculate thechecksum. Should there ever be hardware thatcan offload the icmp checksum calculation it istrivial to hook in now.
ICMP shows another interesting case. ICMP
errors quote the packet they refer to, usuallythat is tcp or udp. And this quoted packet ofcourse has a checksum as well. In most cases
the quoted packet is truncated and the checksum can’t be verified anyway, so there is noreal need to adjust it. pf used to do it nontheless. In the cases where the quoted packet
is not truncated, we can recalculate the innerchecksum as usual, just without being able touse any offloading. In return the quoted, not12

performance considerations

On a modern amd64 system we could not see
any performance benefit from these changes,
not even from offloading in general. On older
systems (Pentium M) I have seen around 7indicates that the modern Xeon has so much raw
computing power and large caches that otherfactors, like latency to the devices, hides the
saved work completely when just doing packet
forwarding.
However, these changes simplify the checksum handling a lot, shortening the code considerably and allow for even more simplifications
by followup cleanups.

future work

The gross bridge broadcast hack mentioned
earlier needs to be fixed so that the special casing all over the stack can go away.
There is no point in the partial early checksum calculations in the pcb templates and uponestablishment of a new connection any more,
we can simplify things by just calculating thepseudo header checksum in the output routines
where we figure out wether we have offloadingor use the software engine.

14

Acknowledgments

A lot of help and support, last not least
with testing, came from Christian Weisgerber(naddy@) and Mike Belopuhov (mikeb@).
The IPv6 protocol checksum software engine
was written by Kenneth R Westerback (krw@).
My trip to AsiaBSDcon has been funded by
the conference.

111

15

Availability

The ip checksum handling changes are part of
OpenBSD since 5.1. The protocol checksum
parts should be committed soon.
This paper and the slides from my presentation will be availabe from the papers section on
http://www.bulabula.org
and be linked from OpenBSD’s paper sectionon
http://www.openbsd.org/papers

112