\chapter{Existing solutions}

\section{Introduction}

Most tools available today fall into one of two classes,
distribution-oriented or host/customisation-oriented. Examples of the
former are \rpm and dpkg, of the latter, cfengine and rdist.  Most
distribution-oriented tools work with some sort of a database (binary
or text-based) where they record all the software they have installed.
They have no concept of software outside what they have installed
themselves, which means locally compiled software can never satisfy
needed dependencies for distribution-distributed software.  The
distribution-oriented tools are usually close-ended.  Close-ended
implies the list of operations which can be formed is closed.

Host/customisation-oriented tools, on the other hand, usually work
with what's on the file system.  Most of them are file-oriented and
many have no concept of a ``package''. If they do, it's mostly as
a collection of files, not as a full-blown package with dependencies,
pre- and post-installation and -removal scripts.  In contrast to
distribution-oriented tools, those tools are usually open-ended.  Even
though pre- and post-installation scripts may not be in the list of
features supported by the tool they can be provided by the packager.

\section{Processes versus tools}

This chapter is about existing tools, but even though good tools are
needed, they are not enough.  In order to have a good, well-scaling
system a lot of processes are needed.  As shown in Figure
\ref{fig:package_lifecycle} one needs to gather the software to be
distributed, it needs to be customised, coherently packaged according
to a policy and put in a repository.  A subdistributor can then pick
packages from different repositories, customise them and put them in
their own repository.  The structure created by repositories
inheriting from other repositories is a tree.  At any point in the
tree, end-users can use the repository there as their repository.  An
infrastructure and processes for automatic building of packages are
needed if one has more than a very small number of architectures.  It
is therefore important not to focus too much on tools alone, but also
make sure one has the needed infrastructure to fully utilise the
tools.

\section{Existing tools}

There are a lot of existing tools; I will describe some of the most
used ones.

\subsection{dpkg}

Dpkg is Debian's package manager. It is fairly low-level and is
therefore normally used together with at least
\abbrev{apt\footnotemark}\footnotetext {advanced packaging tool,
  developed for Debian/dpkg and later ported to \rpm} and a frontend,
like Synaptic, dselect, aptitude or apt-get.  There doesn't exist any
formal design documents for dpkg, but some starting points are listed
in the references.  \nocite{dpkg-site} \nocite{dpkg-reference}

\begin{figure}[h]
  \centering
  \includegraphics[height=8em]{debian_usertools}
  \caption{Debian's stack of user tools and how they work together}
\end{figure}


Debian packages are .ar archives (as usually used by static libraries
(.a files)) with three components inside: a file containing the
version number, a gzipped tarball with the control information
(package name, dependencies, pre/post install/removal scripts) and
finally a gzipped tarball with the files contained in the package.
This makes sure the package can be handled using standard tools in
case dpkg is unavailable or doesn't work (due to internal errors or
missing libraries).

Dpkg consists of a lot of small programs.  The end-user will usually
just use ``dpkg'', which will then call out to dpkg-deb, dpkg-query
and so on.  Some of those, like dpkg-query are useful to have
available for the advanced user, but won't be needed in most cases.

\begin{figure}[h]
  \centering
  \includegraphics[height=8em]{debian_developertools}
  \caption{Debian's developer tools and how the work together}
\end{figure}


For developers dpkg has a large selection of specialised utilities to
help when building packages. Most of them concentrate around building
the package correctly and generating metadata used by the rest of the
Debian infrastructure, but not by dpkg itself.

As the dpkg utilities are fairly low-level, there are a number of
helper utilities to help abstract away the details and help manage
patches to the source code.  Those are especially useful for larger
packages, and they facilitates adherence to Debian's policy.

\subsubsection{Characteristics}
\begin{itemize}
\item {\em \unix philosophy}.  As shown in the diagrams, dpkg consists
  of multiple smaller programs.  The programs are cooperating through
  standard mechanisms such as pipes.
\item {\em Standard file formats (.ar, .gz, .tar)}.  This expands on
  the previous point.  Rather than reinventing the wheel and making a
  new file format, standard, well-known file formats are used.  This
  makes it possible to use standard tools as well, if that is wanted
  or needed.
\item {\em Text/RFC822-based control files}.  Meta-information, such
  as package name, version, maintainer is stored in the format
  specified by RFC822~\cite{RFC822}
\item {\em Flexible with regards to source package layout}  The only
  requirement is that the file \verb|debian/rules| is a makefile.
  Many different tools are available to help build the package in a
  smooth fashion.
\item {\em Binary package distribution}  The packages distributed are
  binary, but a source package is usually also generated.  The source
  package is used by autobuilders for other architectures.
\item {\em Modular base-line design}. Functionality considered standard in other packages are add-ons
  in dpkg, or handled at other levels, like fetching and signing of
  packages.
\end{itemize}

\subsection{RPM}

\rpm originally meant ``Red Hat Package Manager'', but was renamed to
``\rpm Package Manager'' in the tradition of recursive
acronyms~\footnote{Recursive acronyms are quite common in the free
  software world, with examples such as \abbrev{gnu} (\abbrev{gnu}'s
  not \abbrev{unix}), \abbrev{php} (\abbrev{php}: Hypertext
  Preprocessor) and there's even an example of two mutually recursive
  acronyms: the \abbrev{hurd}, which stands for ``\abbrev{hird} of
  \abbrev{unix}-replacing Daemons'', with \abbrev{hird} standing for
  ``\abbrev{hurd} of Interfaces Representing Depth''}.  It is used by
a large number of Linux distributions: Red Hat/Fedora, SuSE, Mandrake,
Trustix and more.  \rpm by itself is a low-level tool, somewhat like
dpkg.  Like dpkg, there doesn't exist any formal design documents on
\rpm, but a few starting points are listed in the
references.\nocite{maximumrpm} \nocite{rpmguide}

It does not have a concept of a repository where to get dependencies
from, even though it has built-in support for fetching packages via
\abbrev{ftp} and \abbrev{http}.  Combined with the fact that there
wasn't any frontends with a repository concept, this made the built-in
support for dependencies much less useful. The user had to fetch the
dependencies himself as \rpm told him about them.  This hand-tracking
of dependencies was coined ``\rpm hell''.  Later, it has gotten
frontends like urpmi, \apt, yum and up2date which handles the
downloading and installation for the user.

\rpm archives are segmented into two parts: one is a binary
object with the control information.  The second part is a cpio
archive with the package's files.  The file format means \rpm
and other rpmlib-using tools are the only tools able to handle
\rpm files well, though one can extract the files using cpio.

The rpm command line tool is just one big program with its behaviour
adjusted by command line flags.  It is also used for building
packages, specified by a ``spec file''.  The spec file describes how
the package should be unpacked, patched, built and installed.  It also
specifies version numbers, where to get the upstream source and any
patches to apply.  In addition it includes any scripts related to the
installation and removal of the package.  The spec file can also
include macros, and a set of standard macros comes with \rpm.

\subsubsection{Characteristics}
\begin{itemize}
\item {\em \vms-alike philosophy}.  See Tool size under section
  \ref{ph_operational_paradigms}.  rpm is one command line binary with
  its behaviour dependent on switches.
\item {\em Efficient, non-standard file formats}.  The format of the
  binary control information field is not in any standard format.  The
  data section is in cpio format.  The choice of non-standard formats
  gives possibilities for optimisations and relaxes requirements on
  not breaking compatibility with standard tools.
\item {\em Pristine source with stringent source layout}.  The source
  package has a very well-specified layout.  Spec files have a
  well-defined syntax, which makes it easy for people who know
  \rpm, but not the specific package to make changes.
\item {\em Binary package distribution}.  While \rpm has support for
  source packages (called \abbrev{srpm}s), packages distributed to end
  computers contain the binaries to install.
\item {\em Built-in auxiliary utilities}. \rpm has many utilities
  built-in, which are external in other package managers.  Support for
  \abbrev{ftp} and \abbrev{http} downloads, signed packages and
  verification of installed packages are examples.
\item {\em Good querying support}.  \rpm stores a fair amount of
  meta-data about the installed packages, like installation time and
  on what host the package was built.  All this information is
  available for querying, with a user-specified format.
\item {\em Librarified}.  rpmlib is a library that other application
  than the rpm command line tool can link to in order to provide
  package management services, including query support.  This makes it
  relatively easy to build front\-ends with a richer set of semantics
  than what pipes and return codes make possible.
\end{itemize}

\subsection{FreeBSD Ports}

\freebsd, when installed, provides a small, generic ``base system''.
It does not include much more than what's needed for bootstrapping
applications.  If you want to run a web server, have another shell and
so on, you have to install a port, from ``the ports collection''.  A
similar system is used by Net\bsd (pkgsrc) and Open\bsd.  The gentoo
Portage system is also inspired by ports.  BSD Ports are not formally
described, but some starting points are listed in the references.
\nocite{ports-site} \nocite{ports-basics-site}

Ports is a tree of (as of Noember 2004) almost 12000 applications.
The on-disk format is a tree, organised first by section (``cad'',
``graphics'', ``web'' and so on) then by application name.

The application directory contains a makefile, some meta-data and zero
or more patches.  Each makefile is really a small application which
creates packages that are handled by the pkg\_add, pkg\_info, pkg\_sign
and pkg\_check commands. Using a configuration file the user building
the package can decide whether to use or disable certain features,
like IPv6 support.

As the packages are tarballs with meta-data files, they are very
easily manipulated using standard \unix tools.  The meta-data files are
all text files and even though they aren't according to RFC822 or
other standard format, they are easy to read and understand.

For development Ports provide a framework which all ports use.  They
don't necessarily have to, but in practice everybody does.
Development is mostly of writing a makefile to download and build the
sources.  In many cases, some patches are needed as well, so
development consists of writing those as well.

\subsubsection{Characteristics}
\begin{itemize}
\item {\em \unix philosophy}. Ports leverage existing tools heavily.
  Some tools used are make, sed, wget, md5sum and gcc.
\item {\em Standard file formats}.  As standard tools are used for
  building packages, using non-standard file formats would be
  unnecessary work.
\item {\em Text based control files}. \unix has a tradition of
  having files as text files, unless it is absolutely necessary to
  have them as binaries.  With the chosen tools, text-based control
  files comes naturally.
\item {\em Pristine source with fairly stringent source layout.}  Like
  \rpm, Ports has a pristine source-policy, with external patch
  files.  This helps not losing patches when updating to a newer
  upstream version.
\item {\em Source based packages}. Most ports are distributed as source
  packages and built on the machine where they are to be installed,
  but there exists binary port repositories as well, and apart from
  customs, there's nothing stopping one from installing binary ports
  on machines.
\end{itemize}

\section{Other tools}

We have a plethora of other important tools, some of which could have
been examined as the ones above have been.  They will only be briefly
described with an overview and an explanation of why they are not
being examined further.

\subsection{cfengine}

From the cfengine website\cite{cfengine-site}:

\begin{quote}
  Cfengine, or the configuration engine is an autonomous agent and a
  middle to high level policy language for building expert systems
  which administrate and configure large computer networks. Cfengine
  uses the idea of classes and a primitive intelligence to define and
  automate the configuration and maintenance of system state, for
  small to huge configurations. Cfengine is designed to be a part of a
  computer immune system, and can be thought of as a gaming agent. It
  is ideal for cluster management and has been adopted for use all
  over the world in small and huge organisations alike.
\end{quote}

Cfengine is not being examined further because it is not a
closed-ended system.  It is more of a language and an open-ended
system for building a software distribution system, so comparing
cfengine doesn't make much sense.  Cfengine would be a strong
candidate for making a new software distribution system in order not
to start completely from scratch.

\subsection{rdist}

rdist\cite{rdist-site} is a program which uses push file distribution
and with rudimentary support for post-installation scripts.  It is an
open-ended system without a package concept, though one can be
emulated.  One way is grouping files per-package in different
distfiles\footnote{The files that describes what files are to be
  distributed and where to.} and distributing a different set depending
on what packages are to be installed on a host.

\subsection{stash}

stash\cite{stash-site} is mainly used for managing a small number of
packages in a person's home directory rather than a full system
installation.  It tries to autodetect the type of package (autoconf
configure script, IMakefile, perl's Makefile.PL, python's setup.py and
so on) but doesn't seem to have any support for automatic building of
packages through some ``recipe''.

It is not being examined further because it is geared towards managing
programs in a user's home directory rather than system-wide software
management.

\subsection{Depot}

Depot\cite{depot-site} organises related but different software
packages into categories known as ``collections''.  It doesn't have a
dependency concept, so a collection has to be self-sustained, or the
user will have to track dependencies himself.  Depot is more of a
method to organise software into manageable groups and doesn't have a
mechanism to distribute packages.  This makes it out-of-scope for the
purposes of this paper.

\subsection{Store}

Store was developed at what is now the Norwegian University of Science
and Technology.  It is inspired by depot, but the code base is fully
separate.  It it mostly in maintenance mode and the community using it
is small.  Among its interesting features is a master/slave concept
where one can have hierarchical repository structures.

\subsection{pkgadd (Solaris) / SAM (HP-UX) / SMIT (AIX)}

Those are all tools for commercial \abbrev{unix}es and are generally not too
well documented in what kind of package formats they use and how to
build packages for them.  They do not come with source, which means
examining them with the intent of extending them would be hard.  They
are also tied to their ``native'' \unix and therefore has limited
interest given that we want to scale across platforms. 


\subsection{Variations and forks of other tools}

Those tools listed here are either plain forks of software listed
above, or they are variations on the theme, and are therefore not
examined in further detail.

\subsubsection{OpenPKG}

OpenPKG uses a forked \rpm, and concentrates a lot more on the
distribution side and is more of a source distribution tree with
source {\rpm}s than a package tool.

\subsubsection{Fink}

Fink is a patched dpkg and \apt for Mac OS X, with a separate package
repository from Debian.

\subsubsection{Portage}

Portage is the \bsd ports taken to a full system level.  It is used by
the Gentoo Linux distribution.

\subsubsection{GNU Stow}
Stow is a scaled-down version of depot, not requiring a database and
not having a collection concept.  There are a bunch of
forks/reimplementations of it: StowES and XStow are two.


\section{Summary}

The following is a summary of key points on the three package systems
examined in detail. 

\begin{longtable}[h]{|p{3.1cm}| p{2.6cm} |p{2.6cm} |p{2.6cm}|}
\hline
  Requirement & dpkg & \rpm & \abbrev{bsd} Ports \\
\hline \endhead
File formats & simple, standard  & custom, binary & \raggedright
text-based, standard \tabularnewline
\hline
Philosophy & & &\\
- push/pull & pull & pull & pull\\ 
- operations/state & both\footnote{Files are state, pre- and
  postinstallation/removal scripts are operations} & both\footnotemark[\value{footnote}] & both\footnotemark[\value{footnote}]\\
- tool structure & small tools & \raggedright large, do-it-all tool & small tools \\
\hline
Operations support & & & \\
- pristine source & \raggedright supported, but not compulsory 
                  & compulsory 
                  & compulsory \\
- patch system & \raggedright none native, but externally supported & native & native \\
- recursive repository support & no\footnote{repositories supported
  with \apt, externally} & \raggedright no native repository support& no\\
- upgrade support\footnote{support for upgrading packages, separate
  from removal and reinstalling} & yes & yes & yes\footnote{upgrading
  ports can easily break package dependencies, especially for library packages} \\
\raggedright - configuration file handling & \raggedright postinst or asking administrator &
\raggedright rename new or old file & none\footnote{due to policy choices; the
  administrator is told what to do and has to do the changes himself} \\
- installation & yes & yes & yes\\
- acquisition & not natively\footnote{\apt or dselect acquires packages} & yes & yes \\
- querying & yes & yes & yes\\
- verification & not natively & yes & no\\
- signed packages & not natively & yes & no\\
\raggedright - multiple architecture support & no & yes & N/A \\
\hline
\raggedright Programming interfaces & & &\\
- plugins & no & no & no \\
- hooks & no & yes\footnote{called triggers} & no\\
- APIs & \raggedright yes, command line & yes, library & \raggedright
yes, command line \tabularnewline
\hline
\end{longtable}

\rpm has good native support for a lot of extensions such as good
querying support and support for signed packages.  Dpkg does not have
native support, but it's supported through external tools.  \rpm is
librarified, which is a huge advantage if one wants to use it as a
part of a bigger system.  There has been some discussion about
librarifying dpkg, but work has not started on it.

Scalability can be supported through recursive or hierarchical
repositories where the computers do not have a custom configuration
themselves, but get their configuration from the repository.  Given a
low enough cost for branching off a repository, having one repository
per configuration is doable and efficient.  Some repositories might be
used by as little as a single host (an example being a single computer
with a scanner or DVD writer in a computer lab), but most repositories
will be used by a larger number of hosts, such as a complete lab.

A design like this blurs the difference between multiple different
configurations inside an organisation and branching off another
organisation's repository for one's own internal one.  Handling
different release levels can be done with different repositories which
can be partially overlapping (where the version in multiple
repositories is the same) where only the file describing the
repository shows a different subset.  The design is inspired by Tom
Lord's Arch\cite{gnuarch-site}.

None of the tools has native support for recursive repositories of any
kind, but both dpkg and \rpm can be wrapped by \apt.
With external tools, emulating recursive mirrors is possible to do.

%\section{Techniques used by existing tools}

%  - incompatible (to a certain degree)
%  - different goals


%- requirement specification for tools
%- categorization according to requirement specification
