\documentclass[12pt,a4paper]{article}
\usepackage[utf8x]{inputenc}
\usepackage{parskip}
\usepackage{hyperref}
\usepackage{xcolor}
\hypersetup{
    colorlinks,
    linkcolor={red!50!black},
    citecolor={blue!50!black},
    urlcolor={blue!80!black}
}
\usepackage{abstract}
\usepackage{graphicx}
\DeclareGraphicsExtensions{.pdf,.png,.jpg}
\usepackage{float}
\floatstyle{boxed}
\restylefloat{figure}
\usepackage{fancyhdr}
  \pagestyle{fancy}
  %\fancyhead{}
  %\fancyfoot{}

\title{Optimizing QEMU boot time}
\author{
\large
Richard W.M. Jones
\normalsize Red Hat Inc.
\normalsize \href{mailto:rjones@redhat.com}{rjones@redhat.com}
}
\date{}

\begin{document}
\maketitle

\begin{abstract}
Everyone knows that containers are really fast and lightweight, and
full virtualization is slow and heavyweight ... Or that's what we
thought, until Intel demonstrated full Linux virtual machines booting
as fast as containers and using as little memory.  Intel's work used
kvmtool and a customized, cut down guest kernel.  Can we do the same
using libvirt, QEMU, SeaBIOS, and an off the shelf Linux distro
kernel?  The short answer is \textit{no}, but we can get pretty close,
and it was an exciting journey learning about unexpected performance
roadblocks, developing tools to measure the boot process, and shaving
off milliseconds all over the place.  The work has practical
significance because it will allow us to deploy secure containers,
protected by hardware virtualization.  Even if you never plan to use
containers, you're still benefiting from a faster QEMU experience.
\end{abstract}

\section{Intel Clear Linux}

Intel's Clear Linux means a lot of different things to different
people.  I'm only going to talk about a narrow aspect of it, usually
known as ``Clear Containers'', but if other people talk about Intel
Clear Linux they might be talking about a Linux distribution,
OpenStack or graphics technologies.

LWN has a useful and relatively recent introduction to Clear
Containers \url{https://lwn.net/Articles/644675/}.

Until recently Intel hosted a Clear Containers demo.  If you
downloaded it and ran \texttt{bash~./boot.sh} then it booted into a
full Linux VM in about 150ms, and using 20~MB of RAM.

Intel are using this technology along with a customized Docker driver
to run Docker containers safely inside a VM.  The overhead (150ms /
20~MB) is very attractive since it doesn't impact on the density that
containers give you.  It's also aligned with Intel's interests, since
they are selling chips with VT, VT-d, EPT, VPID and so on and they
need people to use those features.

The Clear Containers demo uses \texttt{kvmtool} with several
non-upstream patches such as for DAX and 64 bit guests.  Since first
demonstrating Clear Containers, Intel has worked on getting vNVDIMM
(needed for DAX) into QEMU.

The Clear Containers demo from last year uses a patched Linux kernel.
There are many non-upstream patches.  More importantly they use a
custom, cut down configuration where many subsystems not used by VMs
are cut out entirely.

\section{Real Linux distros use QEMU}

Can we do the same sort of thing in our Linux distros?  Let's talk
about some things that constrain us in Fedora.

We'd prefer to use QEMU over kvmtool.  QEMU isn't really ``bloated''.
It's featureful, but (generally) if you're not using those features
they don't slow things down.

We \textit{can't} use the heavily patched and customized kernel.
Fedora is strictly ``upstream first''.  Fedora also ships a single
kernel image for baremetal, virtual machines and all other uses, since
building and maintaining multiple kernels is a huge pain.

\section{Stating the problem}

What we want to do is to boot up and shut down a modern Linux kernel
in a KVM virtual machine on a modern Linux host.  Inside the virtual
machine we will eventually want to run our Docker container.  However
I am just concentrating on the overhead of the boot and shutdown.

\begin{samepage}
Conveniently -- and also the reason I'm interested in this problem --
libguestfs does almost the same thing.  It starts up and shuts down a
small Linux-based appliance.  If you have \texttt{guestfish}
installed, then you can try running the command below (several times
so you have a warm cache).  Add \texttt{-v~-x} to the command line to
see what's really going on.

\begin{verbatim}
$ guestfish -a /dev/null run
\end{verbatim}
\end{samepage}

\section{Measurements}

The first step to improving the situation is to build tools that can
accurately measure the time taken for each step in the boot process.

Booting a Linux kernel under QEMU using the \texttt{-kernel} option
looks like table~\ref{tab:kernel-steps}.

\begin{table}[h]
\caption{Steps run when you use QEMU \texttt{-kernel}}
\centering
\begin{tabular}{l}
  query QEMU's capabilities \\
  \hline
  run QEMU \\
  \hline
  run SeaBIOS \\
  \hline
  run the kernel \\
  \hline
  run the initramfs \\
  \hline
  load kernel modules \\
  \hline
  mount and pivot to the root filesystem \\
  \hline
  run \texttt{/init}, \texttt{udevd} etc \\
  \hline
  perform the desired task \\
  \hline
  shutdown \\
  \hline
  exit QEMU
\end{tabular}
\label{tab:kernel-steps}
\end{table}

How do you know when SeaBIOS starts or various kernel events happen?

I started out looking at various QEMU tracing options, but ended up
using a very simple technique: Attach a serial console to QEMU,
timestamp the messages as they arrive, and use regular expression
string matches to find significant events.

The three programs I wrote (two in C and one in Perl) use libguestfs
as a convenient framework, since libguestfs has the machinery already
for creating VMs, initramfses, capturing serial console output etc.
They are:

\begin{itemize}
\item \texttt{boot-benchmark}

\texttt{boot-benchmark} runs the boot up sequence repeatedly, throwing
away the first few runs (to warm the cache) and collecting the mean
test time and standard deviation.

\begin{verbatim}
$ ./boot-benchmark
Warming up the libguestfs cache ...
Running the tests ...

test version: libguestfs 1.33.29
 test passes: 10
host version: Linux moo.home.annexia.org 4.4.4-301.fc23.x86_64 #1 SMP
    host CPU: Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz
     backend: direct               [to change set $LIBGUESTFS_BACKEND]
        qemu: /home/rjones/d/qemu/x86_64-softmmu/qemu-system-x86_64
qemu version: QEMU emulator version 2.6.50, Copyright (c) 2003-2008
         smp: 1                    [to change use --smp option]
     memsize: 500                  [to change use --memsize option]
      append:                      [to change use --append option]

Result: 568.2ms ±8.7ms
\end{verbatim}

\item \texttt{boot-benchmark-range.pl}

\texttt{boot-benchmark-range.pl} is a wrapper script around
\texttt{boot-benchmark} which lets you benchmark across a range of
commits from some other project (eg. QEMU or the kernel).  You can
easily see which commits are causing or solving performance problems
as in the example below:

\begin{verbatim}
$ ./boot-benchmark-range.pl ~/d/qemu 3123bd8^..8e86aa8
da34fed hw/ppc/spapr: Fix crash when specifying bad[...]
	1666.8ms ±2.5ms

3123bd8 Merge remote-tracking branch 'remotes/dgibson/[...]
	1658.8ms ±4.2ms

f419a62 (origin/master, origin/HEAD, master) usb/uhci: move[...]
	1671.3ms ±17.0ms

8e86aa8 Add optionrom compatible with fw_cfg DMA version
	1013.7ms ±3.0ms ↑ improves performance by 64.9%
\end{verbatim}

\item \texttt{boot-analysis}

\begin{figure}[h]
\caption{boot-analysis timeline}
\includegraphics[width=0.9\textwidth]{boot-analysis-screenshot}
\label{fig:ba-timeline}
\end{figure}

\texttt{boot-analysis} performs multiple runs of the boot sequence.
It enables the QEMU serial console (and other events from libguestfs),
timestamps the events, and then presents the sequence graphically as
shown in figure~\ref{fig:ba-timeline}.  Also shown are mean times and standard
deviations and percentage of the total run time.

\begin{figure}[h]
\caption{boot-analysis longest activities}
\includegraphics[width=0.9\textwidth]{boot-analysis-screenshot-2}
\label{fig:ba-longest}
\end{figure}

This test also prints which activities took the longest time, see
figure~\ref{fig:ba-longest}.

\end{itemize}

The source for these tools is here:
\url{https://github.com/libguestfs/libguestfs/tree/master/utils}.

Only now that we have the right tools to hand can we work out what
activities take time.

For consistency, all times displayed by the tool are in milliseconds
(ms), and I try to use the same convention in this paper.

In this paper I'm using times based on my laptop, an
Intel\textregistered Core\texttrademark i7-5600U CPU @ 2.60GHz
(Broadwell~U).  This does of course mean that these results won't be
exactly reproducible, but it is hoped that with similar hardware you
will get times that differ only by a scale factor.

\section{glibc}

Surprisingly the first problem is glibc.  QEMU links to over 170
libraries, and that number keeps growing.  A simple
\texttt{qemu~-version} takes up to 60ms, and examining this with
\texttt{perf} showed two things:

\begin{itemize}
\item Ceph had a bug where it ran some \texttt{rdtsc} benchmarks in a
  constructor function.  This is now fixed.
\item The glibc link loader is really slow when presented with lots of
  libraries and lots of symbols.
\end{itemize}

The second problem is intractable.  We can't link to fewer libraries,
because each of those libraries represents some feature that someone
wants, like Ceph, or Gtk support (though if you remove the Gtk
dependency the link time reduces substantially).  And the link loader
is bound by all sorts of obscure ELF rules (eg. symbol interposition)
which we don't need but cannot avoid and make things slow.

When I said earlier that QEMU features don't slow things down, this is
an exception.

We can run QEMU fewer times.  There are several places where we need
to run QEMU.  Obviously one place is where we start the virtual
machine, and the overhead there cannot be avoided.  But also we
perform QEMU feature detection by running commands like
\texttt{qemu~-help} and \texttt{qemu~-devices~\textbackslash?} and
libguestfs now caches that output.

\section{QEMU}

Libguestfs, Intel Clear Containers, and any future Docker container
support we build will use \texttt{-kernel} and \texttt{-initrd} or
their equivalent.  In QEMU up to 2.6 on x86-64 this was implemented
using an interface called \texttt{fw\_cfg} and a PIO loop, and that is
very slow.  To load the kernel and very small initrd used by
libguestfs takes around 700ms.  In QEMU 2.7 we have added a pseudo-DMA
mode which makes this step almost instant.

To see debugging messages from the kernel and to collect our benchmark
results, we have to use an emulated 16550A UART (serial port).
Virtio-console exists but isn't a good replacement because it can't be
used to get BIOS and very early kernel messages.  The UART is slow.
It takes about 4µs per character, or approximately 1ms for 3 lines of
text.  Enabling debugging changes the results subtly.

To get serial console output from the BIOS, we use a
Google-contributed option ROM called SGABIOS.  It quickly became clear
that SGABIOS introduced a 260ms boot delay.  This happened because it
expects to be talking to a real serial terminal, so it sends control
sequences to query the width and height of this ``terminal''.  These
weren't being answered by the actual reader (libguestfs simply reads).
The solution was to modify libguestfs to respond to the control
sequence with a dummy reply, which reduced the delay to almost
nothing.

\section{libvirt}

Libguestfs can optionally use libvirt to manage the QEMU process.
When I did this it was obvious that libvirt was adding a (precisely)
200ms delay.  I tracked this down to a poorly implemented polling loop
in libvirt, waiting for the QEMU monitor socket to be created by QEMU.
I fixed it by changing the loop to use exponential backoff.  A better
fix would involve passing pre-created file descriptors to QEMU.

\section{SeaBIOS}

SeaBIOS wastes time probing for boot devices even though we will use
the \texttt{linuxboot} option ROM to boot (via \texttt{-kernel}).  By
building a \texttt{bios-fast.bin} variant of SeaBIOS with many unused
features disabled we can reduce the time spent inside the BIOS from
about 63ms to about 19ms.

\section{kernel}

PCI probing is slow, taking around 95ms for a guest with just two
virtio-scsi drives.  It turns out that it's not the scanning of the
PCI device space which is slow, but the initialization of each device
as it is found.  QEMU's i440fx machine model exports some legacy
devices which cannot be switched off, and that is unhelpful.

I implemented experimental support for parallel PCI probing using the
kernel ``async'' feature.  With 1~vCPU this slows things down very
slightly as expected.  With 4~vCPUs performance improved by about
30\%.  Unfortunately we can't use it because of the next point.

You would think multiple vCPUs would be better and faster than 1~vCPU,
but that is not the case.  It actually has a large negative impact on
performance.  Switching from 1 to 4~vCPUs increases the boot time by
over 200ms.  About 25ms is spent starting each secondary CPU (in
\texttt{check\_tsc\_sync\_target}).  This can be avoided by setting
\texttt{tsc.reliable=1} but no one can tell me if this is safe.  But
most of the extra time just disappears between the cracks -- for
example, PCI probing just slows down, but for no readily apparent
reason.  It seems as if the overhead of spinlocks or RCU or whatever
hurts general performance.  Or perhaps there is some scheduling
problem on the host since it only has 4 physical CPUs.

When the kernel runs, it does some BIOS stuff, and there's a long
delay (about 80ms) before \texttt{start\_kernel} is entered.

Another unavoidable overhead is \texttt{ftrace} which must modify
every function in the kernel.  This takes 20ms.  You can't disable
ftrace at run time, the only option is to compile it out, but that
breaks so many useful features that we'd never persuade a distro
kernel to do that.

If your kernel has crypto functions, then it will spend 18ms testing
them at boot.  Herbert Xu accepted my patch to add a
\texttt{cryptomgr.notests} flag which bypasses this.

As we are presenting an emulated 16550A UART,
\texttt{serial\_8250\_init} runs, and this spends 25ms checking that
the UART is really a 16650A (does it work, does it have a FIFO?), and
(unsurprisingly) yes it is.  This is a totally useless waste of time,
but I have not managed to come up with a patch or even with an
approach for how to avoid this that is acceptable upstream.

But the main problem is none of the above.  It's simply the small
amount of time taken to run many many initcalls.  For a distro kernel
this can be around 690ms (with serial debugging enabled which
exaggerates the effect somewhat).  One way to avoid that would be to
compile some sort of custom kernel, and even though this approach is
not acceptable for Fedora I did explore this, trying both a cut down
distro kernel, and also a super-minimal kernel.

\begin{itemize}
\item The cut down distro kernel works by removing any subsystem that
  has a $>$~1ms initcall overhead.  These include:
  \begin{itemize}
  \item auditing
  \item big\_key
  \item ftrace
  \item hugetlbfs
  \item input\_leds
  \item joydev
  \item joysticks
  \item keyboards
  \item kprobes
  \item libata
  \item mice
  \item microcode
  \item netlabel
  \item profiling support
  \item quota
  \item rtc\_drv\_cmos
  \item sound card support
  \item tablets
  \item touchscreens
  \item USB
  \item zbud
  \item zswap
  \end{itemize}
  That reduces the time taken running initcalls before userspace by
  about 20\%.  There is some scope for reducing this a bit more by
  going even further down the ``long tail'' of subsystems.
\item For my second test I started with an absolutely minimal kernel
  config (\texttt{allnoconfig}), and built up the configuration until
  I got something that booted.  That reduces the time taken running
  initcalls before userspace by about 60\% (down to 288ms).
\end{itemize}

With a minimal kernel, we can get total boot times down to the
500-600ms range, but not any lower.

\section{udev}

udevd takes about 130ms to populate \texttt{/dev}.

The rules are monolithic, entwined together and resist modification,
and starting a new set of rules from scratch looks like it would be a
constant game of catch up.

\section{initrd}

We use a program called supermin
(\url{http://libguestfs.org/supermin.1.html}) to construct the initrd
which is responsible for loading enough kmods to mount the real root
filesystem and pivoting into it.

Because of PIO loading of the initrd in earlier versions of QEMU, it
was very important to construct as small an initrd as possible, and
supermin was not doing a very good job of that.  However once I
started to analyze the situation there were some easy wins (now all
upstream):

\begin{itemize}
\item We were adding all virtio kmods to the appliance plus any
  dependencies, with the starting set being constructed using the
  wildcard ``\texttt{virtio*.ko}''.  The wildcard pulls in
  \texttt{virtio-gpu.ko} which depends on \texttt{drm.ko} and both are
  quite large.  Since we are only interested in non-graphical VMs, I
  was able to blacklist \texttt{virtio-gpu.ko} and that reduced the
  total size of the initrd.
\item We use a small C init program to load the kmods and mount
  the root filesystem, and this must be statically linked so we
  don't have to include a separate libc in the initrd.  However
  glibc produces enormous static binaries (800KB+).  Switching to using
  dietlibc allows us to build the same program to a
  22KB binary, about $\frac{1}{40}$th of the size.
\item We initially used xz-compressed kmods.  These are smaller,
  reducing PIO loading time (but making not a lot of difference to
  DMA) but they are very slow to decompress.  Switching to using
  uncompressed kmods produced a small reduction in boot time, and
  simplified the init code.
\item Stripping kmods (with \texttt{strip~-g}) is very important for
  reducing the size of the initrd.
\end{itemize}

The resulting initrd is about 126KB for the minimal kernel, or 347K
for the standard Fedora kernel.

\section{libguestfs}

Finally there is libguestfs itself which glues everything together and
provides the initial \texttt{/init} script.  There were several
savings to be made:

\begin{itemize}
\item When we are not debugging, we were still reading the verbose
  kernel output over the slow UART, and then throwing it away.  The
  solution was to add the \texttt{quiet} option.  That reduced boot
  time by about 1,000ms, the single largest saving.
\item We used to run the \texttt{hwclock} command.  With kvmclock it
  turns out this is not necessary, and removing it saved 300ms.
\item We used to run \texttt{qemu~-help} and \texttt{qemu~-version}.
  Drew Jones pointed out the obvious: the help output contains the
  version number, so that reduces the number of times we need to run
  QEMU and suffer the glibc slow link loader overhead (and in the
  final version of libguestfs we also memoize QEMU output, reducing it
  further).
\item We used to run SGABIOS unconditionally, but it is only necessary
  to use it when debugging.  When we're not debugging we can omit it
  and save loading it at all.
\item Running \texttt{ldconfig} in the appliance to update the link
  loader cache took 100ms, but we found a way that we don't need to
  run it at all.
\end{itemize}

\section{Memory usage and DAX}

I was pleasantly surprised that Intel had implemented a virtual
NVDIMM, and ext4 + DAX is also working in modern kernels, and it was a
relatively trivial job to implement DAX.

However I'm not certain that the benefits are clear, nor that I'm
measuring things correctly.

Inside the guest you can run \texttt{free~-m} with and without DAX:

\begin{verbatim}
              total    used    free  shared buff/cache available
Without DAX:    485       3     451       1         30       465
With DAX:       485       3     469       1         12       467
\end{verbatim}

The MaxRSS of QEMU reduces by about 5~MB when DAX is enabled.

\section{Conclusions}

\begin{minipage}{\textwidth}
This graph is just for a bit of fun:

\includegraphics[width=0.8\textwidth]{progress}
\end{minipage}

There were a few false starts at the beginning of March (2016) where I
was exploring how we might benchmark QEMU.  But once I had written the
right tools to analyze the boot process, two quick wins brought the
time down from 3.5~seconds to 1.2~seconds in the space of a few days.
It's worth noting that the libguestfs appliance had been booting in
approx.~3-4~seconds for literally half a decade.

Getting the time under 600ms took a few weeks longer, and without some
breakthrough in the kernel or udev, I cannot see us getting the time
under 500ms.

Performance is everyone's job, but it sometimes feels like few people
care about a use case which is considered esoteric.  Yet this does
affect everyone:

\begin{itemize}
\item If we can use virtualization as an extra layer of security
  around operations, whether that is Docker, or Qubes, or
  libvirt-sandbox, or libguestfs, that benefits everyone.
\item The same concerns about boot speed are raised over and over
  again by the embedded community.  If your digital camera is slow to
  switch on, it might be running initcalls for subsystems that it will
  never use.  (Many references here:
  \url{http://elinux.org/Boot_Time})
\end{itemize}

Hopefully this paper will persuade developers to think twice before
adding an unnecessary delay loop, inserting a useless boot splash
screen, or creating another initcall.

\end{document}
