\chapter{Motivation and problem definition}
\label{problem_definition}

The motivation for multiarch might not seem obvious, but on closer
inspection it supports some very interesting use-cases:

\begin{itemize}
\item A user is on a 64 bit platform but needs a proprietary 32 bit
  plugin in his web browser to access sites using that plugin.  An
  example is the flash plugin from Macromedia.
\item A new architecture is introduced.  This has a different ABI than
  the most prevalent architecture.  However, the new architecture has
  the ability to run older binaries at acceptable speed.
\item New features in binary formats or changed ABIs leave old
  libraries incompatible.
\end{itemize}

The first use-case is fairly common for AMD64 users today if they are
using the platform in 64 bit mode rather than as in i386 legacy mode.
Besides proprietary plugins, we have other proprietary applications
such as a lot of games.  Even in the cases where the source code is
available the porting job might be big.  Examples are OpenOffice.org
and partimage.

We see the second case on both AMD64 and newer PowerPCs today.  Those
are able to run 64 bit code and older code at an acceptable speed.
For the PowerPC a full migration does not make sense since it is
usually a bit slower in 64 bit mode than in 32 bit mode.  AMD64 is
usually faster due to the greater number of registers compared to i386
and this offsets the speed penalty from increased pointer size.
Multiarch allows the user to run his legacy applications until they
are available for the new ABI.  Developers are also able to test their
applications on the new platform without worrying about breakage in
the base system and only have to worry about the libraries they
use directly.

The third use case is much more common than one would expect.  For
more or less each new release of the C++ compiler, the ABI is
changed.  This means all C++ libraries and any depending applications
have to be recompiled.  This is obviously a big pain and something to
avoid whenever possible.  Multiarch will make it a lot less painful
and make it possible to transition gracefully without breaking
user-compiled programs.

The problem is ``how do we make this work''?  This consists of
multiple sub-problems:

\begin{itemize}
\item Where should the support for running the binaries be?  In
  kernel- or user-space?
\item File systems are hierarchical which means two files cannot exist
  in the same place.  A policy on how to name files to avoid overlaps
  is needed.
\item The packaging system will refuse to install packages for a
  foreign architecture today.  This needs to be changed, but in such a
  way that only packages which will work are possible to install.
  This relationship is not bidirectional, since i386 packages are
  useful on amd64 but not vice versa.
\end{itemize}

As the target of our studies is dpkg which usually runs on Linux
systems which use ELF\cite{tis.elf} as the native object file format,
ELF and Linux is what will be discussed further.

\section{Starting an ELF object}

A small introduction on how executing an ELF object (program) helps
explain how it is possible to run binaries of different architectures,
even without any kernel support.  When the kernel is asked to execute
an ELF object, it locates and loads the interpreter noted in the ELF
header of said object.  The interpreter then loads the program and any
objects marked as NEEDED in the ELF header.  Such external objects are
typically libraries, but could be more or less anything the program
needed.  Then \function{_init} for each of the loaded objects (if
available) is run and any constructor functions (prime examples are
C++ global objects which are constructed automatically when the
library is loaded).  Finally, \function{main} itself is called and the
program runs.

\section{Kernel- or user-space support}

The use cases which are interesting in this context already has
support for emulation either in the kernel (as is the case for running
i386 Linux binaries on a Linux/x86\_64 kernel) or in user-space (as is
the case for running i386 Linux binaries on a Linux/PowerPC system
with qemu\cite{qemu-site}).

The kernel support is implemented in a variety of different ways.  An
example is the support in Linux/x86\_64 where the kernel only switches
the CPU into 32 bit mode and executes the binary.  Some other
emulations use a \function{set_fs_altroot} kernel function which
changes the visible root for the file system.
\directory{/emul/i386-linux} is the usual place for the alternate
root.

There are multiple ways to implement multiarch in user-space.  One way
is to emulate a full system with no or very limited integration
between the host and the guest system.  This is a virtual machine
approach where one usually sees the virtual machine in a terminal or
similar on the host system.  This approach is taken by
VMware\cite{vmware-site} and qemu for i386.  The exact emulation can
be done through emulation or virtualisation.  As long as you are
working on the same binary formats, a pure syscall interception route
is also possible.  In that case, a wrapper catches all the
instructions and system calls and rewrites those to the native
architecture.

\section{File hierarchy policy}

Once support to execute binaries is in place, a policy for where to
place ``foreign'' binaries is needed.  This is mostly an aesthetical
issue, but important to ensure acceptance.  Ugly solutions have a
history of not gaining wide acceptance even though they solve the
technical problem at hand.  There are two dinstinct ways to organise
the tree with small variations on exactly how to do it.

\begin{itemize}
\item Separate trees/chroot
\item Merge the trees
\end{itemize}

\subsection{Separated trees or chroot}

Pros:
\begin{itemize}
\item Simpler, both in terms of layout and to construct.
\item Easy handling of multiarch binaries
\item ``Pure'' trees available to chroot into
\end{itemize}

\noindent Cons:
\begin{itemize}
\item Duplication of files
\item Administrative overhead
\end{itemize}

Using a total segregation of the trees is a fairly simplistic
approach.  It shows clearly which files belong to which architecture.
It also makes it easy to change into a tree which is pure to that
architecture rather than a mix of binaries for different
architectures.

On the downside, having fully separate trees means more overhead as
architecture-independent data is duplicated between the trees.
Depending on how the packaging system is set up and works, it might be
necessary to maintain two wholly separate systems with the
administrative overhead that it causes.

\begin{example}
An example of what fully separated trees could look like:

\lstset{language=Directory}
\begin{lstlisting}[columns=fullflexible]
/
/lib
/usr
/usr/lib
/usr/share
/emul
/emul/i386-linux/lib
/emul/i386-linux/usr
/emul/i386-linux/usr/share
/emul/i386-linux/usr/lib
\end{lstlisting}
\end{example}

\subsection{Merged trees}

Pros:
\begin{itemize}
\item Integrated feeling
\item Files are only stored once
\end{itemize}

\noindent Cons:
\begin{itemize}
\item More complex, needs policies which resolve file
  conflicts/overlaps
\item No handling of multiarch binaries
\end{itemize}


Merging the trees and thereby making one multiarch installation rather
than two (or more) installations side-by-side is a much cleaner
approach.  It makes the whole file system layout look better and more
integrated.  Architecture independent files can be placed in only one
place rather than being duplicated in different parts of the tree.  A
single packaging system can handle all the installed packages.  This
all sums up to a much better look and feel of the system where
multiarch support is actually integrated rather than ``bolted on''
afterwards.

A merged tree approach gives a few more possible issues than the
separated trees approach.  A clear policy on how to name
architecture-dependent parts of the tree is needed to avoid file name
overlaps between packages.  The ability to change into a separate tree
or chroot and use that as an independent system goes away.  Some
tools, such as compilers, need to be available for multiple
architectures.  Any such tools need to have their name include an
architecture-specific part, or be placed in a directory whose name
includes an architecture-specific part.

As most binaries aren't that interesting to be provided in multiarch
versions, the first approach will be chosen.  Programs such as
compilers are often installed multiple times on systems today and
already provide good internal support for transforming the program
name.  Other programs which are part of the toolchain usually also has
this support.

A solution where a merged tree with only the libraries (and any
binaries which supports being installed with an architecture-specific
pre/suffix) being multiarch is the solution which will be examined
further.  This approach gives us the biggest gain for the least
effort.  It gives us the ability to select applications of different
architectures without imposing the overhead of providing all
applications in co-installable versions.

An alternative would be to put all the binaries in paths with an
architecture component and manage preferred versions of binaries with
symlink farms.  This would give the advantage of being able to run
binaries for multiple architectures just by changing symlinks or
calling the wanted version explicitly.  It would also make exporting
the tree of binaries to machines of other architectures a lot
simpler.  An example of a system which does this is
Store\cite{DBLP:conf/scm/ChristensenE95}.

\begin{example}
An example of what a merged tree could look like is:

\lstset{language=Directory}
\begin{lstlisting}[columns=fullflexible]
/
/lib
/lib/i386-linux
/lib/x86_64-linux
/usr
/usr/lib
/usr/lib/i386-linux
/usr/lib/x86_64-linux
/usr/share
\end{lstlisting}
\end{example}

\section{Packaging system support}

The packaging system needs to know about the file system policy so it
can implement it correctly.  The level of support will vary, depending
on the abstraction level of the packaging system as well as the amount
of semantics attached to the files. \cite{tfheen-scalable} Most have a
dependency concept where one can say something like

\lstset{language=DebControl}
\begin{lstlisting}[frame=tRBl,columns=fullflexible]
Package: bazaar
Depends: libc6, diff, patch
\end{lstlisting}

This means that the \pkg{bazaar} package needs to have the packages
\pkg{libc6}, \pkg{diff} and \pkg{patch} installed but does not say
anything about which architectures those packages need to be.  Since
\pkg{libc6} is a library, it needs to be of the same architecture as
the binaries in the \pkg{bazaar} package.  Unless it uses diff and
patch in a very peculiar way (by using dlopen and calling functions in
them, effectively treating them as shared libraries), \pkg{bazaar} can
use \pkg{diff} and \pkg{patch} packages of any architecture.  They
are text-processing tools which have text-based interfaces.

Our implementation needs to be able to express the architecture of
dependent packages while preserving the current set of semantics.  The
last part is important so the current set of packages will continue to
work correctly and not give an administrator any unpleasant
surprises.  If a dependency from one package to another suddenly meant
a package of any architecture could fulfill it one would end up with a
large amount of broken systems.

\section{Related problems}

Clashes in library and regular program names are not the only
problems.  Many libraries and binaries have embedded search paths.
They have search paths for plugins and for data files.  They have
search paths for caches, for icons and so on.  Making sure that any
paths which contain architecture dependent files point to the right
places and the same for architecture independent files is important
and probably something which will cause some extra work and disruption
when implementing multiarch.  A number of tools will certainly need
some changes.

Some examples of tools which need to be changed are:

\begin{itemize}
\item binutils\cite{binutils-site} and gcc\cite{gcc-site} as they have
  a default search path which needs to be updated.
\item pkg-config\cite{pkgconfig-site}, to look in multiple directories
  for definitions on the architecture-specific data files it uses.
\item libtool\cite{libtool-site}, autoconf\cite{autoconf-site},
  automake\cite{automake-site} and other tools which know the default
  search path of the compiler and looks for installed libraries.
\end{itemize}
