document the basic algorithms used by pkg*.

Actually a must-read for any porter who plays with non-trivial updates.

1 files changed, 115 insertions, 2 deletions

diff --git a/usr.sbin/pkg_add/pod/OpenBSD::Intro.pod b/usr.sbin/pkg_add/pod/OpenBSD::Intro.pod
index fd30e94a851..9e4649825c3 100644
--- a/usr.sbin/pkg_add/pod/OpenBSD::Intro.pod
+++ b/usr.sbin/pkg_add/pod/OpenBSD::Intro.pod
@@ -1,4 +1,4 @@
-$OpenBSD: OpenBSD::Intro.pod,v 1.4 2008/02/04 13:53:40 espie Exp $
+$OpenBSD: OpenBSD::Intro.pod,v 1.5 2008/02/25 16:58:46 espie Exp $
 
 =head1 NAME
 
@@ -205,7 +205,120 @@ virtually before doing them for real.
 
 =head1 BASIC ALGORITHMS
 
-To be done.
+There are three basic operations: package addition (installation),
+package removal (deinstallation), and package replacement (update).
+
+These operations are achieved through repeating the correct
+operations on all elements of a packing-list.
+
+=head2 PACKAGE ADDITION
+
+For package addition, L<pkg_add(1)> first checks that everything is correct, 
+then runs through the packing-list, and extracts element from the archive.
+
+=head2 PACKAGE DELETION
+
+For package deletion, L<pkg_delete(1)> removes elements from the packing-list,
+and marks `common' stuff that may need to be unregistered, then walks quickly
+through all installed packages and removes stuff that's no longer used
+(directories, users, groups...)
+
+=head2 PACKAGE REPLACEMENT
+
+Package replacement is more complicated. It relies on package names 
+and conflict markers.  
+
+In normal usage, pkg_add installs only new stuff, and checks that all files 
+in the new package don't already exist in the file system.
+By convention, packages with the same stem are assumed to be different
+versions of the same package, e.g., screen-1.0 and screen-1.1 correspond
+to the same software, and users are not expected to be able to install
+both at the same time. 
+
+This is a conflict. 
+
+One can also mark extra conflicts (if two software distributions install 
+the same file, generally a bad idea), or remove default conflict markers 
+(for instance, so that the user can install several versions of autoconf at 
+the same time).
+
+If pkg_add is invoked in replacement mode (-r), it will use conflict 
+information to figure out which package(s) it should replace. It will then
+operate in a specific mode, where it replaces old package(s) with a new one.
+
+=over
+
+=item *
+
+determine which package to replace through conflict information
+
+=item *
+
+extract the new package 'alongside' the existing package(s) using
+temporary filenames.
+
+=item *
+
+remove the old package
+
+=item *
+
+finish installing the new package by renaming the temporary files.
+
+=back
+
+Thus replacements will work without needing any extra information besides
+conflict markers. pkg_add -r will happily replace any package with a
+conflicting package.  Due to missing information (one can't predict the
+future), conflict markers work both way: packages a and b conflict as
+soon as a conflicts with b, or b conflicts with a.
+
+=head2 PACKAGE UPDATES
+
+Package replacement is the basic operation behind package updates.
+In your average update, each individual package will be replaced
+by a more recent one, starting with dependencies, so that the installation
+stays functional the whole time.  Shared libraries enjoy a special status: 
+old shared libraries are kept around in a stub .lib-* package, so that 
+software that depends on them keeps running. (Thus, it is vital that porters
+pay attention to shared library version numbers during an update.)
+
+An update operation starts by figuring out which packages to update (walking
+the selected packages dependency trees). 
+
+Then it looks for new packages to replace the old ones.
+This search relies on stem names first (e.g., to update package
+foo-1.0, pkg_add -u will look for foo-* in the PKG_PATH), then it trims
+the search results by looking more closely inside the package candidates. 
+More specifically, their pkgpath (the directory in the ports tree from which 
+they were compiled). Thus, a package
+that comes from category/someport/snapshot will never replace a package
+that comes from category/someport/stable. Likewise for flavors.
+
+Finally, pkg_add -u decides whether the update is needed by comparing
+the package signatures: a package signature is information is composed of
+the name of a package, together with relevant dependency information: 
+all wantlib versions, and all run dependencies versions. 
+If anything is different, it means the new package must replace the old one.
+
+Currently, pkg_add -u stops at the first entry in the PKG_PATH from which
+suitable candidates are found.
+
+=head1 BUGS AND LIMITATIONS
+
+There are a few desireable changes that will happen in the future:
+* pkg_add -u should be able to find updates with a stem change.
+This requires an extra mechanism that would say `oh, this package changed
+name', as we cannot afford to look into every single package.
+* more complicated update scenarios could happen, once UpdateSets are fully
+functional.
+* pkg_add has no real notion of version number. Thus, updates work only
+in so far as you direct your PKG_PATH to a more recent repository.
+* there should be some carefully designed mechanisms to register more
+`global' processing, to avoid exec/unexec.
+* some packages should be able to refuse automatic update, and to interact
+with the user. Again, to be carefully designed, so that one can still
+understand what's going on.
 
 =head1 LIST OF MODULES