about summary refs log tree commit diff
diff options
context:
space:
mode:
-rw-r--r--aterm-gc.supp32
-rw-r--r--configure.ac67
-rw-r--r--doc/manual/conf-file.xml2
-rw-r--r--doc/manual/quick-start.xml2
-rw-r--r--externals/Makefile.am54
-rw-r--r--release.nix72
-rw-r--r--scripts/copy-from-other-stores.pl.in58
-rw-r--r--src/bin2c/bin2c.c4
-rw-r--r--src/libexpr/eval.hh2
-rw-r--r--src/libstore/Makefile.am11
-rw-r--r--src/libstore/build.cc15
-rw-r--r--src/libstore/derivations.hh4
-rw-r--r--src/libstore/gc.cc73
-rw-r--r--src/libstore/local-store.cc987
-rw-r--r--src/libstore/local-store.hh98
-rw-r--r--src/libstore/misc.cc8
-rw-r--r--src/libstore/remote-store.cc33
-rw-r--r--src/libstore/remote-store.hh6
-rw-r--r--src/libstore/schema.sql43
-rw-r--r--src/libstore/store-api.cc13
-rw-r--r--src/libstore/store-api.hh35
-rw-r--r--src/libstore/worker-protocol.hh4
-rw-r--r--src/libutil/Makefile.am2
-rw-r--r--src/libutil/archive.cc8
-rw-r--r--src/libutil/archive.hh1
-rw-r--r--src/libutil/hash.cc7
-rw-r--r--src/libutil/hash.hh3
-rw-r--r--src/libutil/util.cc3
-rw-r--r--src/libutil/util.hh2
-rw-r--r--src/nix-env/Makefile.am2
-rw-r--r--src/nix-env/nix-env.cc2
-rw-r--r--src/nix-hash/Makefile.am2
-rw-r--r--src/nix-hash/nix-hash.cc2
-rw-r--r--src/nix-instantiate/Makefile.am2
-rw-r--r--src/nix-instantiate/nix-instantiate.cc2
-rw-r--r--src/nix-log2xml/log2xml.cc14
-rw-r--r--src/nix-setuid-helper/Makefile.am3
-rw-r--r--src/nix-store/Makefile.am2
-rw-r--r--src/nix-store/help.txt3
-rw-r--r--src/nix-store/nix-store.cc29
-rw-r--r--src/nix-worker/Makefile.am2
-rw-r--r--src/nix-worker/nix-worker.cc33
-rw-r--r--substitute.mk1
-rw-r--r--tests/common.sh.in1
-rw-r--r--tests/init.sh4
-rw-r--r--tests/referrers.sh38
46 files changed, 1046 insertions, 745 deletions
diff --git a/aterm-gc.supp b/aterm-gc.supp
index dcd6371fe5aa..21b9a2372856 100644
--- a/aterm-gc.supp
+++ b/aterm-gc.supp
@@ -115,3 +115,35 @@
    fun:*
    fun:AT_collect
 }
+
+{
+   ATerm library conservatively scans for GC roots
+   Memcheck:Value4
+   fun:*
+   fun:*
+   fun:mark_phase
+}
+
+{
+   ATerm library conservatively scans for GC roots
+   Memcheck:Cond
+   fun:*
+   fun:*
+   fun:mark_phase
+}
+
+{
+   ATerm library conservatively scans for GC roots
+   Memcheck:Value4
+   fun:*
+   fun:*
+   fun:mark_phase_young
+}
+
+{
+   ATerm library conservatively scans for GC roots
+   Memcheck:Cond
+   fun:*
+   fun:*
+   fun:mark_phase_young
+}
diff --git a/configure.ac b/configure.ac
index 8d3f308d7142..662a65c82279 100644
--- a/configure.ac
+++ b/configure.ac
@@ -50,39 +50,24 @@ AC_DEFINE_UNQUOTED(SYSTEM, ["$system"], [platform identifier (`cpu-os')])
 test "$localstatedir" = '${prefix}/var' && localstatedir=/nix/var
 
 
-# Whether to produce a statically linked binary.  On Cygwin, this is
-# the default: dynamically linking against the ATerm DLL does work,
-# except that it requires the ATerm "lib" directory to be in $PATH, as
-# Windows doesn't have anything like an RPATH embedded in executable.
-# Since this is kind of annoying, we use static libraries for now.
-
-AC_ARG_ENABLE(static-nix, AC_HELP_STRING([--enable-static-nix],
-  [produce statically linked binaries]),
-  static_nix=$enableval, static_nix=no)
-
-if test "$sys_name" = cygwin; then
-   static_nix=yes
-fi
-
-if test "$static_nix" = yes; then
+# Windows-specific stuff.  On Cygwin, dynamically linking against the
+# ATerm DLL works, except that it requires the ATerm "lib" directory
+# to be in $PATH, as Windows doesn't have anything like an RPATH
+# embedded in executable.  Since this is kind of annoying, we use
+# static libraries for now.
+if test "$sys_name" = "cygwin"; then
     AC_DISABLE_SHARED
     AC_ENABLE_STATIC
 fi
 
 
-# Windows-specific stuff.
-if test "$sys_name" = "cygwin"; then
-    # We cannot delete open files.
-    AC_DEFINE(CANNOT_DELETE_OPEN_FILES, 1, [Whether it is impossible to delete open files.])
-fi
-
 # Solaris-specific stuff.
 if test "$sys_name" = "sunos"; then
     # Solaris requires -lsocket -lnsl for network functions
-    ADDITIONAL_NETWORK_LIBS="-lsocket -lnsl"
-    AC_SUBST(ADDITIONAL_NETWORK_LIBS)
+    LIBS="-lsocket -lnsl $LIBS"
 fi
 
+
 AC_PROG_CC
 AC_PROG_CXX
 
@@ -101,6 +86,13 @@ AC_DISABLE_STATIC
 AC_ENABLE_SHARED
 AC_PROG_LIBTOOL
 
+if test "$enable_shared" = yes; then
+   SUB_CONFIGURE_FLAGS="--enable-shared --disable-static"
+else
+   SUB_CONFIGURE_FLAGS="--enable-static --disable-shared"
+fi
+AC_SUBST(SUB_CONFIGURE_FLAGS)
+
 
 # Use 64-bit file system calls so that we can support files > 2 GiB.
 AC_SYS_LARGEFILE
@@ -218,6 +210,8 @@ AC_ARG_WITH(bzip2, AC_HELP_STRING([--with-bzip2=PATH],
   [prefix of bzip2]),
   bzip2=$withval, bzip2=)
 AM_CONDITIONAL(HAVE_BZIP2, test -n "$bzip2")
+ATERM_VERSION=2.5
+AC_SUBST(ATERM_VERSION)
 if test -z "$bzip2"; then
   # Headers and libraries will be used from the temporary installation
   # in externals/inst-bzip2.
@@ -238,6 +232,25 @@ AC_SUBST(bzip2_include)
 AC_SUBST(bzip2_bin)
 AC_SUBST(bzip2_bin_test)
 
+AC_ARG_WITH(sqlite, AC_HELP_STRING([--with-sqlite=PATH],
+  [prefix of SQLite]),
+  sqlite=$withval, sqlite=)
+AM_CONDITIONAL(HAVE_SQLITE, test -n "$sqlite")
+SQLITE_VERSION=3.6.23
+AC_SUBST(SQLITE_VERSION)
+if test -z "$sqlite"; then
+  sqlite_lib='${top_builddir}/externals/sqlite-$(SQLITE_VERSION)/libsqlite3.la'
+  sqlite_include='-I${top_builddir}/externals/sqlite-$(SQLITE_VERSION)'
+  sqlite_bin='${top_builddir}/externals/sqlite-$(SQLITE_VERSION)'
+else
+  sqlite_lib="-L$sqlite/lib -lsqlite3"
+  sqlite_include="-I$sqlite/include"
+  sqlite_bin="$sqlite/bin"
+fi
+AC_SUBST(sqlite_lib)
+AC_SUBST(sqlite_include)
+AC_SUBST(sqlite_bin)
+
 
 AC_CHECK_LIB(pthread, pthread_mutex_init)
 
@@ -264,14 +277,6 @@ if test "$(uname)" = "Darwin"; then
 fi
 
 
-if test "$static_nix" = yes; then
-    # `-all-static' has to be added at the end of configure, because
-    # the C compiler doesn't know about -all-static (it's filtered out
-    # by libtool, but configure doesn't use libtool).
-    LDFLAGS="-all-static $LDFLAGS"
-fi
-
-
 AM_CONFIG_HEADER([config.h])
 AC_CONFIG_FILES([Makefile
    externals/Makefile
diff --git a/doc/manual/conf-file.xml b/doc/manual/conf-file.xml
index 2ee268097066..19e86808ec3a 100644
--- a/doc/manual/conf-file.xml
+++ b/doc/manual/conf-file.xml
@@ -241,7 +241,7 @@ build-use-chroot = /dev /proc /bin</programlisting>
     Nix store metadata (in <filename>/nix/var/nix/db</filename>) are
     synchronously flushed to disk.  This improves robustness in case
     of system crashes, but reduces performance.  The default is
-    <literal>false</literal>.</para></listitem>
+    <literal>true</literal>.</para></listitem>
 
   </varlistentry>
     
diff --git a/doc/manual/quick-start.xml b/doc/manual/quick-start.xml
index 6d96cb5ac0bc..d2431151f360 100644
--- a/doc/manual/quick-start.xml
+++ b/doc/manual/quick-start.xml
@@ -60,7 +60,7 @@ available remotely.</para></listitem>
 in the channel:
 
 <screen>
-$ nix-env -qa ’*’ <lineannotation>(mind the quotes!)</lineannotation>
+$ nix-env -qa \*
 docbook-xml-4.2
 firefox-1.0pre-PR-0.10.1
 hello-2.1.1
diff --git a/externals/Makefile.am b/externals/Makefile.am
index 63150b1f5e71..060ae2c52fd4 100644
--- a/externals/Makefile.am
+++ b/externals/Makefile.am
@@ -12,30 +12,56 @@ $(BZIP2).tar.gz:
 $(BZIP2): $(BZIP2).tar.gz
 	gunzip < $(srcdir)/$(BZIP2).tar.gz | tar xvf -
 
-have-bzip2:
-	$(MAKE) $(BZIP2)
-	touch have-bzip2
-
 if HAVE_BZIP2
 build-bzip2:
 else
-build-bzip2: have-bzip2
-	(pfx=`pwd` && \
-	cd $(BZIP2) && \
+build-bzip2: $(BZIP2)
+	(cd $(BZIP2) && \
 	$(MAKE) && \
-	$(MAKE) install PREFIX=$$pfx/inst-bzip2)
+	$(MAKE) install PREFIX=$(abs_builddir)/inst-bzip2)
 	touch build-bzip2
 
-install:
+install-exec-local:: build-bzip2
 	mkdir -p $(DESTDIR)${bzip2_bin}
 	$(INSTALL_PROGRAM) $(bzip2_bin_test)/bzip2 $(bzip2_bin_test)/bunzip2 $(DESTDIR)${bzip2_bin}
 endif
 
 
-all: build-bzip2
+# SQLite
+
+SQLITE = sqlite-$(SQLITE_VERSION)
+SQLITE_TAR = sqlite-amalgamation-$(SQLITE_VERSION).tar.gz
+
+$(SQLITE_TAR):
+	@echo "Nix requires the SQLite library to build."
+	@echo "Please download version $(SQLITE_VERSION) from"
+	@echo "  http://www.sqlite.org/$(SQLITE_TAR)"
+	@echo "and place it in the externals/ directory."
+	false
+
+$(SQLITE): $(SQLITE_TAR)
+	gzip -d < $(srcdir)/$(SQLITE_TAR) | tar xvf -
+
+if HAVE_SQLITE
+build-sqlite:
+else
+build-sqlite: $(SQLITE)
+	(cd $(SQLITE) && \
+	CC="$(CC)" ./configure --disable-static --prefix=$(pkglibdir)/dummy --libdir=${pkglibdir} $(SUB_CONFIGURE_FLAGS) && \
+	$(MAKE) )
+	touch build-sqlite
+
+install-exec-local:: build-sqlite
+	cd $(SQLITE) && make install
+	rm -rf "$(DESTDIR)/$(pkglibdir)/dummy"
+endif
+
+
+all: build-bzip2 build-sqlite
 
-EXTRA_DIST = $(BZIP2).tar.gz
+EXTRA_DIST = $(BZIP2).tar.gz $(SQLITE_TAR)
 
-ext-clean:
-	$(RM) -f have-bzip2 build-bzip2
-	$(RM) -rf $(BZIP2)
+clean:
+	$(RM) -f build-bzip2 build-sqlite
+	$(RM) -rf $(BZIP2) $(SQLITE)
+	$(RM) -rf inst-bzip2
diff --git a/release.nix b/release.nix
index 3343f8658091..62ac87da73b6 100644
--- a/release.nix
+++ b/release.nix
@@ -1,4 +1,7 @@
-{ nixpkgs ? ../nixpkgs }:
+{ nix ? {outPath = ./.; rev = 1234;}
+, nixpkgs ? ../nixpkgs
+, officialRelease ? false
+}:
 
 let
 
@@ -6,10 +9,6 @@ let
 
 
     tarball =
-      { nix ? {outPath = ./.; rev = 1234;}
-      , officialRelease ? false
-      }:
-
       with import nixpkgs {};
 
       releaseTools.sourceTarball {
@@ -34,6 +33,9 @@ let
           stripHash ${bzip2.src}
           cp -pv ${bzip2.src} externals/$strippedName
 
+          stripHash ${sqlite.src}
+          cp -pv ${sqlite.src} externals/$strippedName
+
           # TeX needs a writable font cache.
           export VARTEXFONTS=$TMPDIR/texfonts
         '';
@@ -60,9 +62,7 @@ let
 
 
     build =
-      { tarball ? jobs.tarball {}
-      , system ? "i686-linux"
-      }:
+      { system ? "i686-linux" }:
 
       with import nixpkgs {inherit system;};
 
@@ -70,60 +70,34 @@ let
         name = "nix";
         src = tarball;
 
-        buildInputs = [curl perl bzip2 openssl];
+        buildInputs = [ curl perl bzip2 openssl ];
 
         configureFlags = ''
           --disable-init-state
-          --with-bzip2=${bzip2}
+          --with-bzip2=${bzip2} --with-sqlite=${sqlite}
         '';
       };
 
 
-    /*
-    static =
-      { tarball ? jobs.tarball {}
-      , system ? "i686-linux"
-      }:
-
-      with import nixpkgs {inherit system;};
-
-      releaseTools.binaryTarball {
-        name = "nix-static-tarball";
-        src = tarball;
-
-        buildInputs = [curl perl bzip2];
-
-        configureFlags = ''
-          --disable-init-state
-          --with-bzip2=${bzip2}
-          --enable-static-nix
-        '';
-      };
-    */
-
-      
     coverage =
-      { tarball ? jobs.tarball {}
-      }:
-
       with import nixpkgs {};
 
       releaseTools.coverageAnalysis {
         name = "nix-build";
         src = tarball;
 
-        buildInputs = [
-          curl perl bzip2 openssl
-          # These are for "make check" only:
-          graphviz libxml2 libxslt
-        ];
+        buildInputs =
+          [ curl perl bzip2 openssl
+            # These are for "make check" only:
+            graphviz libxml2 libxslt
+          ];
 
         configureFlags = ''
           --disable-init-state --disable-shared
-          --with-bzip2=${bzip2}
+          --with-bzip2=${bzip2} --with-sqlite=${sqlite}
         '';
 
-        lcovFilter = ["*/boost/*" "*-tab.*"];
+        lcovFilter = [ "*/boost/*" "*-tab.*" ];
 
         # We call `dot', and even though we just use it to
         # syntax-check generated dot files, it still requires some
@@ -168,17 +142,15 @@ let
 
   makeRPM = 
     system: diskImageFun: prio:
-    { tarball ? jobs.tarball {}
-    }:
 
     with import nixpkgs {inherit system;};
 
     releaseTools.rpmBuild rec {
       name = "nix-rpm-${diskImage.name}";
-      src = tarball;
+      src = jobs.tarball;
       diskImage = diskImageFun vmTools.diskImages;
       memSize = 1024;
-      meta = { schedulingPriority = toString prio; };
+      meta.schedulingPriority = prio;
     };
 
 
@@ -187,17 +159,15 @@ let
   
   makeDeb =
     system: diskImageFun: prio:
-    { tarball ? jobs.tarball {}
-    }:
 
     with import nixpkgs {inherit system;};
 
     releaseTools.debBuild {
       name = "nix-deb";
-      src = tarball;
+      src = jobs.tarball;
       diskImage = diskImageFun vmTools.diskImages;
       memSize = 1024;
-      meta = { schedulingPriority = toString prio; };
+      meta.schedulingPriority = prio;
       configureFlags = "--sysconfdir=/etc";
       debRequires = ["curl"];
     };
diff --git a/scripts/copy-from-other-stores.pl.in b/scripts/copy-from-other-stores.pl.in
index 8f0ff4ca8df8..a6a14c3dc228 100644
--- a/scripts/copy-from-other-stores.pl.in
+++ b/scripts/copy-from-other-stores.pl.in
@@ -17,25 +17,19 @@ foreach my $dir (@remoteStoresAll) {
 }
 
 
+$ENV{"NIX_REMOTE"} = "";
+
+
 sub findStorePath {
     my $storePath = shift;
-    
-    my $storePathName = basename $storePath;
-    
     foreach my $store (@remoteStores) {
-        # Determine whether $storePath exists by looking for the
-        # existence of the info file, and if so, get store path info
-        # from that file.  This rather breaks abstraction: we should
-        # be using `nix-store' for that.  But right now there is no
-        # good way to tell nix-store to access a store mounted under a
-        # different location (there's $NIX_STORE, but that only works
-        # if the remote store is mounted under its "real" location).
-        my $infoFile = "$store/var/nix/db/info/$storePathName";
-        my $storePath2 = "$store/store/$storePathName";
-        if (-f $infoFile && -e $storePath2) {
-            return ($infoFile, $storePath2);
-        }
+        my $sourcePath = "$store/store/" . basename $storePath;
+        next unless -e $sourcePath || -l $sourcePath;
+        $ENV{"NIX_DB_DIR"} = "$store/var/nix/db";
+        return ($store, $sourcePath) if
+            system("@bindir@/nix-store --check-validity $storePath") == 0;
     }
+    return undef;
 }
 
 
@@ -46,32 +40,28 @@ if ($ARGV[0] eq "--query") {
 
         if ($cmd eq "have") {
             my $storePath = <STDIN>; chomp $storePath;
-            (my $infoFile) = findStorePath $storePath;
-            print STDOUT ($infoFile ? "1\n" : "0\n");
+            print STDOUT (defined findStorePath($storePath) ? "1\n" : "0\n");
         }
 
         elsif ($cmd eq "info") {
             my $storePath = <STDIN>; chomp $storePath;
-            (my $infoFile) = findStorePath $storePath;
-            if (!$infoFile) {
+            my ($store, $sourcePath) = findStorePath($storePath);
+            if (!defined $store) {
                 print "0\n";
                 next; # not an error
             }
             print "1\n";
 
-            my $deriver = "";
-            my @references = ();
-
-            open INFO, "<$infoFile" or die "cannot read info file $infoFile\n";
-            while (<INFO>) {
-                chomp;
-                /^([\w-]+): (.*)$/ or die "bad info file";
-                my $key = $1;
-                my $value = $2;
-                if ($key eq "Deriver") { $deriver = $value; }
-                elsif ($key eq "References") { @references = split ' ', $value; }
-            }
-            close INFO;
+            $ENV{"NIX_DB_DIR"} = "$store/var/nix/db";
+            
+            my $deriver = `@bindir@/nix-store --query --deriver $storePath`;
+            die "cannot query deriver of `$storePath'" if $? != 0;
+            chomp $deriver;
+            $deriver = "" if $deriver eq "unknown-deriver";
+
+            my @references = split "\n",
+                `@bindir@/nix-store --query --references $storePath`;
+            die "cannot query references of `$storePath'" if $? != 0;
 
             print "$deriver\n";
             print scalar @references, "\n";
@@ -87,8 +77,8 @@ if ($ARGV[0] eq "--query") {
 elsif ($ARGV[0] eq "--substitute") {
     die unless scalar @ARGV == 2;
     my $storePath = $ARGV[1];
-    (my $infoFile, my $sourcePath) = findStorePath $storePath;
-    die unless $infoFile;
+    my ($store, $sourcePath) = findStorePath $storePath;
+    die unless $store;
     print "\n*** Copying `$storePath' from `$sourcePath'\n\n";
     system("$binDir/nix-store --dump $sourcePath | $binDir/nix-store --restore $storePath") == 0
         or die "cannot copy `$sourcePath' to `$storePath'";
diff --git a/src/bin2c/bin2c.c b/src/bin2c/bin2c.c
index 18bf81d69e25..5ed8a57082fd 100644
--- a/src/bin2c/bin2c.c
+++ b/src/bin2c/bin2c.c
@@ -14,10 +14,10 @@ int main(int argc, char * * argv)
 {
     int c;
     if (argc != 2) abort();
-    print("static unsigned char %s[] = {", argv[1]);
+    print("static unsigned char %s[] = { ", argv[1]);
     while ((c = getchar()) != EOF) {
         print("0x%02x, ", (unsigned char) c);
     }
-    print("};\n");
+    print("0 };\n");
     return 0;
 }
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 0cdf0b28300f..03bf43a3b9a4 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -6,6 +6,8 @@
 #include "nixexpr.hh"
 #include "symbol-table.hh"
 
+typedef union _ATermList * ATermList;
+
 
 namespace nix {
 
diff --git a/src/libstore/Makefile.am b/src/libstore/Makefile.am
index 9accc3005fc3..e19256b925ea 100644
--- a/src/libstore/Makefile.am
+++ b/src/libstore/Makefile.am
@@ -10,7 +10,14 @@ pkginclude_HEADERS = \
   globals.hh references.hh pathlocks.hh \
   worker-protocol.hh
 
-libstore_la_LIBADD = ../libutil/libutil.la ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@
+libstore_la_LIBADD = ../libutil/libutil.la ../boost/format/libformat.la ${aterm_lib} ${sqlite_lib}
+
+EXTRA_DIST = schema.sql
 
 AM_CXXFLAGS = -Wall \
- -I$(srcdir)/.. -I$(srcdir)/../libutil
+ ${sqlite_include} -I$(srcdir)/.. -I$(srcdir)/../libutil
+
+local-store.lo: schema.sql.hh
+
+%.sql.hh: %.sql
+	../bin2c/bin2c schema < $< > $@ || (rm $@ && exit 1)
diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index f901c1f7d99e..8ce8c873d6a3 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -1545,6 +1545,9 @@ void DerivationGoal::startBuilder()
 
     if (fixedOutput) useChroot = false;
 
+    /* Hack to allow derivations to disable chroot builds. */
+    if (drv.env["__noChroot"] == "1") useChroot = false;
+
     if (useChroot) {
 #if CHROOT_ENABLED
         /* Create a temporary directory in which we set up the chroot
@@ -1568,7 +1571,7 @@ void DerivationGoal::startBuilder()
 
         /* Create a /etc/passwd with entries for the build user and the
            nobody account.  The latter is kind of a hack to support
-           Samba-in-QEMU.  */
+           Samba-in-QEMU. */
         createDirs(chrootRootDir + "/etc");
 
         writeFile(chrootRootDir + "/etc/passwd",
@@ -1576,13 +1579,13 @@ void DerivationGoal::startBuilder()
                 "nixbld:x:%1%:%2%:Nix build user:/:/noshell\n"
                 "nobody:x:65534:65534:Nobody:/:/noshell\n")
                 % (buildUser.enabled() ? buildUser.getUID() : getuid())
-	        % (buildUser.enabled() ? buildUser.getGID() : getgid())).str());
+                % (buildUser.enabled() ? buildUser.getGID() : getgid())).str());
 
 	/* Declare the build user's group so that programs get a consistent
-	   view of the system (e.g., "id -gn").  */
-	writeFile(chrootRootDir + "/etc/group",
-		  (format("nixbld:!:%1%:\n")
-		   % (buildUser.enabled() ? buildUser.getGID() : getgid())).str());
+	   view of the system (e.g., "id -gn"). */
+        writeFile(chrootRootDir + "/etc/group",
+            (format("nixbld:!:%1%:\n")
+                % (buildUser.enabled() ? buildUser.getGID() : getgid())).str());
 
         /* Bind-mount a user-configurable set of directories from the
            host file system.  The `/dev/pts' directory must be mounted
diff --git a/src/libstore/derivations.hh b/src/libstore/derivations.hh
index 95e49d42c9ea..c14be48afb8e 100644
--- a/src/libstore/derivations.hh
+++ b/src/libstore/derivations.hh
@@ -1,10 +1,10 @@
 #ifndef __DERIVATIONS_H
 #define __DERIVATIONS_H
 
-#include "hash.hh"
-
 #include <map>
 
+#include "types.hh"
+
 
 namespace nix {
 
diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
index f58f691c99dd..87e0a05bc9ec 100644
--- a/src/libstore/gc.cc
+++ b/src/libstore/gc.cc
@@ -416,12 +416,7 @@ struct LocalStore::GCState
     PathSet busy;
     bool gcKeepOutputs;
     bool gcKeepDerivations;
-
-    bool drvsIndexed;
-    typedef std::multimap<string, Path> DrvsByName;
-    DrvsByName drvsByName; // derivation paths hashed by name attribute
-
-    GCState(GCResults & results_) : results(results_), drvsIndexed(false)
+    GCState(GCResults & results_) : results(results_)
     {
     }
 };
@@ -441,42 +436,6 @@ bool LocalStore::isActiveTempFile(const GCState & state,
         && state.tempRoots.find(string(path, 0, path.size() - suffix.size())) != state.tempRoots.end();
 }
 
-
-/* Return all the derivations in the Nix store that have `path' as an
-   output.  This function assumes that derivations have the same name
-   as their outputs. */
-PathSet LocalStore::findDerivers(GCState & state, const Path & path)
-{
-    PathSet derivers;
-
-    Path deriver = queryDeriver(path);
-    if (deriver != "") derivers.insert(deriver);
-
-    if (!state.drvsIndexed) {
-        Paths entries = readDirectory(nixStore);
-        foreach (Paths::iterator, i, entries)
-            if (isDerivation(*i))
-                state.drvsByName.insert(std::pair<string, Path>(
-                        getNameOfStorePath(*i), nixStore + "/" + *i));
-        state.drvsIndexed = true;
-    }
-    
-    string name = getNameOfStorePath(path);
-
-    // Urgh, I should have used Haskell...
-    std::pair<GCState::DrvsByName::iterator, GCState::DrvsByName::iterator> range =
-        state.drvsByName.equal_range(name);
-
-    for (GCState::DrvsByName::iterator i = range.first; i != range.second; ++i)
-        if (isValidPath(i->second)) {
-            Derivation drv = derivationFromPath(i->second);
-            foreach (DerivationOutputs::iterator, j, drv.outputs)
-                if (j->second.path == path) derivers.insert(i->second);
-        }
-
-    return derivers;
-}
-
     
 bool LocalStore::tryToDelete(GCState & state, const Path & path)
 {
@@ -508,10 +467,10 @@ bool LocalStore::tryToDelete(GCState & state, const Path & path)
            then don't delete the derivation if any of the outputs are
            live. */
         if (state.gcKeepDerivations && isDerivation(path)) {
-            Derivation drv = derivationFromPath(path);
-            foreach (DerivationOutputs::iterator, i, drv.outputs)
-                if (!tryToDelete(state, i->second.path)) {
-                    printMsg(lvlDebug, format("cannot delete derivation `%1%' because its output is alive") % path);
+            PathSet outputs = queryDerivationOutputs(path);
+            foreach (PathSet::iterator, i, outputs)
+                if (!tryToDelete(state, *i)) {
+                    printMsg(lvlDebug, format("cannot delete derivation `%1%' because its output `%2%' is alive") % path % *i);
                     goto isLive;
                 }
         }
@@ -522,18 +481,9 @@ bool LocalStore::tryToDelete(GCState & state, const Path & path)
         if (!pathExists(path)) return true;
 
         /* If gc-keep-outputs is set, then don't delete this path if
-           its deriver is not garbage.  !!! Nix does not reliably
-           store derivers, so we have to look at all derivations to
-           determine which of them derive `path'.  Since this makes
-           the garbage collector very slow to start on large Nix
-           stores, here we just look for all derivations that have the
-           same name as `path' (where the name is the part of the
-           filename after the hash, i.e. the `name' attribute of the
-           derivation).  This is somewhat hacky: currently, the
-           deriver of a path always has the same name as the output,
-           but this might change in the future. */
+           there are derivers of this path that are not garbage. */
         if (state.gcKeepOutputs) {
-            PathSet derivers = findDerivers(state, path);
+            PathSet derivers = queryValidDerivers(path);
             foreach (PathSet::iterator, deriver, derivers) {
                 /* Break an infinite recursion if gc-keep-derivations
                    and gc-keep-outputs are both set by tentatively
@@ -613,6 +563,15 @@ void LocalStore::collectGarbage(const GCOptions & options, GCResults & results)
     
     state.gcKeepOutputs = queryBoolSetting("gc-keep-outputs", false);
     state.gcKeepDerivations = queryBoolSetting("gc-keep-derivations", true);
+
+    /* Using `--ignore-liveness' with `--delete' can have unintended
+       consequences if `gc-keep-outputs' or `gc-keep-derivations' are
+       true (the garbage collector will recurse into deleting the
+       outputs or derivers, respectively).  So disable them. */
+    if (options.action == GCOptions::gcDeleteSpecific && options.ignoreLiveness) {
+        state.gcKeepOutputs = false;
+        state.gcKeepDerivations = false;
+    }
     
     /* Acquire the global GC root.  This prevents
        a) New roots from being added.
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index f430492fd407..6f3d9efa8625 100644
--- a/src/libstore/local-store.cc
+++ b/src/libstore/local-store.cc
@@ -4,6 +4,7 @@
 #include "archive.hh"
 #include "pathlocks.hh"
 #include "worker-protocol.hh"
+#include "derivations.hh"
     
 #include <iostream>
 #include <algorithm>
@@ -16,10 +17,137 @@
 #include <errno.h>
 #include <stdio.h>
 
+#include <sqlite3.h>
+
 
 namespace nix {
 
     
+class SQLiteError : public Error
+{
+public:
+    SQLiteError(sqlite3 * db, const format & f)
+        : Error(format("%1%: %2%") % f.str() % sqlite3_errmsg(db))
+    {
+    }
+};
+
+
+SQLite::~SQLite()
+{
+    try {
+        if (db && sqlite3_close(db) != SQLITE_OK)
+            throw SQLiteError(db, "closing database");
+    } catch (...) {
+        ignoreException();
+    }
+}
+
+
+void SQLiteStmt::create(sqlite3 * db, const string & s)
+{
+    checkInterrupt();
+    assert(!stmt);
+    if (sqlite3_prepare_v2(db, s.c_str(), -1, &stmt, 0) != SQLITE_OK)
+        throw SQLiteError(db, "creating statement");
+    this->db = db;
+}
+
+
+void SQLiteStmt::reset()
+{
+    assert(stmt);
+    if (sqlite3_reset(stmt) != SQLITE_OK)
+        throw SQLiteError(db, "resetting statement");
+    curArg = 1;
+}
+
+
+SQLiteStmt::~SQLiteStmt()
+{
+    try {
+        if (stmt && sqlite3_finalize(stmt) != SQLITE_OK)
+            throw SQLiteError(db, "finalizing statement");
+    } catch (...) {
+        ignoreException();
+    }
+}
+
+
+void SQLiteStmt::bind(const string & value)
+{
+    if (sqlite3_bind_text(stmt, curArg++, value.c_str(), -1, SQLITE_TRANSIENT) != SQLITE_OK)
+        throw SQLiteError(db, "binding argument");
+}
+
+
+void SQLiteStmt::bind(int value)
+{
+    if (sqlite3_bind_int(stmt, curArg++, value) != SQLITE_OK)
+        throw SQLiteError(db, "binding argument");
+}
+
+
+void SQLiteStmt::bind()
+{
+    if (sqlite3_bind_null(stmt, curArg++) != SQLITE_OK)
+        throw SQLiteError(db, "binding argument");
+}
+
+
+/* Helper class to ensure that prepared statements are reset when
+   leaving the scope that uses them.  Unfinished prepared statements
+   prevent transactions from being aborted, and can cause locks to be
+   kept when they should be released. */
+struct SQLiteStmtUse
+{
+    SQLiteStmt & stmt;
+    SQLiteStmtUse(SQLiteStmt & stmt) : stmt(stmt)
+    {
+        stmt.reset();
+    }
+    ~SQLiteStmtUse()
+    {
+        try {
+            stmt.reset();
+        } catch (...) {
+            ignoreException();
+        }
+    }
+};
+
+
+struct SQLiteTxn 
+{
+    bool active;
+    sqlite3 * db;
+    
+    SQLiteTxn(sqlite3 * db) : active(false) {
+        this->db = db;
+        if (sqlite3_exec(db, "begin;", 0, 0, 0) != SQLITE_OK)
+            throw SQLiteError(db, "starting transaction");
+        active = true;
+    }
+
+    void commit() 
+    {
+        if (sqlite3_exec(db, "commit;", 0, 0, 0) != SQLITE_OK)
+            throw SQLiteError(db, "committing transaction");
+        active = false;
+    }
+    
+    ~SQLiteTxn() 
+    {
+        try {
+            if (active && sqlite3_exec(db, "rollback;", 0, 0, 0) != SQLITE_OK)
+                throw SQLiteError(db, "aborting transaction");
+        } catch (...) {
+            ignoreException();
+        }
+    }
+};
+
+
 void checkStoreNotSymlink()
 {
     if (getEnv("NIX_IGNORE_SYMLINK_STORE") == "1") return;
@@ -44,13 +172,13 @@ LocalStore::LocalStore()
     
     schemaPath = nixDBPath + "/schema";
     
-    if (readOnlyMode) return;
+    if (readOnlyMode) {
+        openDB(false);
+        return;
+    }
 
     /* Create missing state directories if they don't already exist. */
     createDirs(nixStore);
-    createDirs(nixDBPath + "/info");
-    createDirs(nixDBPath + "/referrer");
-    createDirs(nixDBPath + "/failed");
     Path profilesDir = nixStateDir + "/profiles";
     createDirs(nixStateDir + "/profiles");
     createDirs(nixStateDir + "/temproots");
@@ -63,12 +191,15 @@ LocalStore::LocalStore()
   
     checkStoreNotSymlink();
 
+    /* Acquire the big fat lock in shared mode to make sure that no
+       schema upgrade is in progress. */
     try {
         Path globalLockPath = nixDBPath + "/big-lock";
         globalLock = openLockFile(globalLockPath.c_str(), true);
     } catch (SysError & e) {
         if (e.errNo != EACCES) throw;
         readOnlyMode = true;
+        openDB(false);
         return;
     }
     
@@ -76,33 +207,55 @@ LocalStore::LocalStore()
         printMsg(lvlError, "waiting for the big Nix store lock...");
         lockFile(globalLock, ltRead, true);
     }
-    
+
+    /* Check the current database schema and if necessary do an
+       upgrade.  */
     int curSchema = getSchema();
     if (curSchema > nixSchemaVersion)
         throw Error(format("current Nix store schema is version %1%, but I only support %2%")
             % curSchema % nixSchemaVersion);
-    if (curSchema == 0) { /* new store */
-        curSchema = nixSchemaVersion; 
+    
+    else if (curSchema == 0) { /* new store */
+        curSchema = nixSchemaVersion;
+        openDB(true);
         writeFile(schemaPath, (format("%1%") % nixSchemaVersion).str());
     }
-    if (curSchema == 1) throw Error("your Nix store is no longer supported");
-    if (curSchema < nixSchemaVersion) upgradeStore12();
+    
+    else if (curSchema < nixSchemaVersion) {
+        if (curSchema < 5)
+            throw Error(
+                "Your Nix store has a database in Berkeley DB format,\n"
+                "which is no longer supported. To convert to the new format,\n"
+                "please upgrade Nix to version 0.12 first.");
+        
+        if (!lockFile(globalLock, ltWrite, false)) {
+            printMsg(lvlError, "waiting for exclusive access to the Nix store...");
+            lockFile(globalLock, ltWrite, true);
+        }
+
+        /* Get the schema version again, because another process may
+           have performed the upgrade already. */
+        curSchema = getSchema();
+
+        if (curSchema < 6) upgradeStore6();
+
+        writeFile(schemaPath, (format("%1%") % nixSchemaVersion).str());
 
-    doFsync = queryBoolSetting("fsync-metadata", false);
+        lockFile(globalLock, ltRead, true);
+    }
+    
+    else openDB(false);
 }
 
 
 LocalStore::~LocalStore()
 {
     try {
-        flushDelayedUpdates();
-
         foreach (RunningSubstituters::iterator, i, runningSubstituters) {
             i->second.to.close();
             i->second.from.close();
             i->second.pid.wait(true);
         }
-                
     } catch (...) {
         ignoreException();
     }
@@ -121,6 +274,71 @@ int LocalStore::getSchema()
 }
 
 
+void LocalStore::openDB(bool create)
+{
+    /* Open the Nix database. */
+    if (sqlite3_open_v2((nixDBPath + "/db.sqlite").c_str(), &db.db,
+            SQLITE_OPEN_READWRITE | (create ? SQLITE_OPEN_CREATE : 0), 0) != SQLITE_OK)
+        throw Error("cannot open SQLite database");
+
+    if (sqlite3_busy_timeout(db, 60 * 60 * 1000) != SQLITE_OK)
+        throw SQLiteError(db, "setting timeout");
+
+    if (sqlite3_exec(db, "pragma foreign_keys = 1;", 0, 0, 0) != SQLITE_OK)
+        throw SQLiteError(db, "enabling foreign keys");
+
+    /* !!! check whether sqlite has been built with foreign key
+       support */
+    
+    /* Whether SQLite should fsync().  "Normal" synchronous mode
+       should be safe enough.  If the user asks for it, don't sync at
+       all.  This can cause database corruption if the system
+       crashes. */
+    string syncMode = queryBoolSetting("fsync-metadata", true) ? "normal" : "off";
+    if (sqlite3_exec(db, ("pragma synchronous = " + syncMode + ";").c_str(), 0, 0, 0) != SQLITE_OK)
+        throw SQLiteError(db, "setting synchronous mode");
+
+    /* Use `truncate' journal mode, which should be a bit faster. */
+    if (sqlite3_exec(db, "pragma main.journal_mode = truncate;", 0, 0, 0) != SQLITE_OK)
+        throw SQLiteError(db, "setting journal mode");
+
+    /* Initialise the database schema, if necessary. */
+    if (create) {
+#include "schema.sql.hh"
+        if (sqlite3_exec(db, (const char *) schema, 0, 0, 0) != SQLITE_OK)
+            throw SQLiteError(db, "initialising database schema");
+    }
+
+    /* Prepare SQL statements. */
+    stmtRegisterValidPath.create(db,
+        "insert into ValidPaths (path, hash, registrationTime, deriver) values (?, ?, ?, ?);");
+    stmtAddReference.create(db,
+        "insert or replace into Refs (referrer, reference) values (?, ?);");
+    stmtQueryPathInfo.create(db,
+        "select id, hash, registrationTime, deriver from ValidPaths where path = ?;");
+    stmtQueryReferences.create(db,
+        "select path from Refs join ValidPaths on reference = id where referrer = ?;");
+    stmtQueryReferrers.create(db,
+        "select path from Refs join ValidPaths on referrer = id where reference = (select id from ValidPaths where path = ?);");
+    stmtInvalidatePath.create(db,
+        "delete from ValidPaths where path = ?;");
+    stmtRegisterFailedPath.create(db,
+        "insert into FailedPaths (path, time) values (?, ?);");
+    stmtHasPathFailed.create(db,
+        "select time from FailedPaths where path = ?;");
+    stmtQueryFailedPaths.create(db,
+        "select path from FailedPaths;");
+    stmtClearFailedPath.create(db,
+        "delete from FailedPaths where ?1 = '*' or path = ?1;");
+    stmtAddDerivationOutput.create(db,
+        "insert or replace into DerivationOutputs (drv, id, path) values (?, ?, ?);");
+    stmtQueryValidDerivers.create(db,
+        "select v.id, v.path from DerivationOutputs d join ValidPaths v on d.drv = v.id where d.path = ?;");
+    stmtQueryDerivationOutputs.create(db,
+        "select id, path from DerivationOutputs where drv = ?;");
+}
+
+
 void canonicalisePathMetaData(const Path & path, bool recurse)
 {
     checkInterrupt();
@@ -195,181 +413,133 @@ void canonicalisePathMetaData(const Path & path)
 }
 
 
-static Path infoFileFor(const Path & path)
+void LocalStore::registerValidPath(const Path & path,
+    const Hash & hash, const PathSet & references,
+    const Path & deriver)
 {
-    string baseName = baseNameOf(path);
-    return (format("%1%/info/%2%") % nixDBPath % baseName).str();
+    ValidPathInfo info;
+    info.path = path;
+    info.hash = hash;
+    info.references = references;
+    info.deriver = deriver;
+    registerValidPath(info);
 }
 
 
-static Path referrersFileFor(const Path & path)
+unsigned long long LocalStore::addValidPath(const ValidPathInfo & info)
 {
-    string baseName = baseNameOf(path);
-    return (format("%1%/referrer/%2%") % nixDBPath % baseName).str();
-}
-
+    SQLiteStmtUse use(stmtRegisterValidPath);
+    stmtRegisterValidPath.bind(info.path);
+    stmtRegisterValidPath.bind("sha256:" + printHash(info.hash));
+    stmtRegisterValidPath.bind(info.registrationTime);
+    if (info.deriver != "")
+        stmtRegisterValidPath.bind(info.deriver);
+    else
+        stmtRegisterValidPath.bind(); // null
+    if (sqlite3_step(stmtRegisterValidPath) != SQLITE_DONE)
+        throw SQLiteError(db, format("registering valid path `%1%' in database") % info.path);
+    unsigned long long id = sqlite3_last_insert_rowid(db);
+
+    /* If this is a derivation, then store the derivation outputs in
+       the database.  This is useful for the garbage collector: it can
+       efficiently query whether a path is an output of some
+       derivation. */
+    if (isDerivation(info.path)) {
+        Derivation drv = parseDerivation(readFile(info.path));
+        foreach (DerivationOutputs::iterator, i, drv.outputs) {
+            SQLiteStmtUse use(stmtAddDerivationOutput);
+            stmtAddDerivationOutput.bind(id);
+            stmtAddDerivationOutput.bind(i->first);
+            stmtAddDerivationOutput.bind(i->second.path);
+            if (sqlite3_step(stmtAddDerivationOutput) != SQLITE_DONE)
+                throw SQLiteError(db, format("adding derivation output for `%1%' in database") % info.path);
+        }
+    }
 
-static Path failedFileFor(const Path & path)
-{
-    string baseName = baseNameOf(path);
-    return (format("%1%/failed/%2%") % nixDBPath % baseName).str();
+    return id;
 }
 
 
-static Path tmpFileForAtomicUpdate(const Path & path)
+void LocalStore::addReference(unsigned long long referrer, unsigned long long reference)
 {
-    return (format("%1%/.%2%.%3%") % dirOf(path) % getpid() % baseNameOf(path)).str();
+    SQLiteStmtUse use(stmtAddReference);
+    stmtAddReference.bind(referrer);
+    stmtAddReference.bind(reference);
+    if (sqlite3_step(stmtAddReference) != SQLITE_DONE)
+        throw SQLiteError(db, "adding reference to database");
 }
 
 
-void LocalStore::appendReferrer(const Path & from, const Path & to, bool lock)
+void LocalStore::registerValidPath(const ValidPathInfo & info)
 {
-    Path referrersFile = referrersFileFor(from);
-    
-    PathLocks referrersLock;
-    if (lock) {
-        referrersLock.lockPaths(singleton<PathSet, Path>(referrersFile));
-        referrersLock.setDeletion(true);
-    }
-
-    AutoCloseFD fd = open(referrersFile.c_str(), O_WRONLY | O_APPEND | O_CREAT, 0666);
-    if (fd == -1) throw SysError(format("opening file `%1%'") % referrersFile);
-    
-    string s = " " + to;
-    writeFull(fd, (const unsigned char *) s.c_str(), s.size());
-
-    if (doFsync) fsync(fd);
-}
-
-
-/* Atomically update the referrers file.  If `purge' is true, the set
-   of referrers is set to `referrers'.  Otherwise, the current set of
-   referrers is purged of invalid paths. */
-void LocalStore::rewriteReferrers(const Path & path, bool purge, PathSet referrers)
-{
-    Path referrersFile = referrersFileFor(path);
-    
-    PathLocks referrersLock(singleton<PathSet, Path>(referrersFile));
-    referrersLock.setDeletion(true);
-
-    if (purge)
-        /* queryReferrers() purges invalid paths, so that's all we
-           need. */
-        queryReferrers(path, referrers);
-
-    Path tmpFile = tmpFileForAtomicUpdate(referrersFile);
-    
-    AutoCloseFD fd = open(tmpFile.c_str(), O_WRONLY | O_TRUNC | O_CREAT, 0666);
-    if (fd == -1) throw SysError(format("opening file `%1%'") % referrersFile);
+    assert(info.hash.type == htSHA256);
+    ValidPathInfo info2(info);
+    if (info2.registrationTime == 0) info2.registrationTime = time(0);
     
-    string s;
-    foreach (PathSet::const_iterator, i, referrers) {
-        s += " "; s += *i;
-    }
+    SQLiteTxn txn(db);
     
-    writeFull(fd, (const unsigned char *) s.c_str(), s.size());
+    unsigned long long id = addValidPath(info2);
 
-    if (doFsync) fsync(fd);
-    
-    fd.close(); /* for Windows; can't rename open file */
-
-    if (rename(tmpFile.c_str(), referrersFile.c_str()) == -1)
-        throw SysError(format("cannot rename `%1%' to `%2%'") % tmpFile % referrersFile);
+    foreach (PathSet::const_iterator, i, info2.references)
+        addReference(id, queryValidPathId(*i));
+        
+    txn.commit();
 }
 
 
-void LocalStore::flushDelayedUpdates()
+void LocalStore::registerFailedPath(const Path & path)
 {
-    foreach (PathSet::iterator, i, delayedUpdates) {
-        rewriteReferrers(*i, true, PathSet());
-    }
-    delayedUpdates.clear();
+    if (hasPathFailed(path)) return;
+    SQLiteStmtUse use(stmtRegisterFailedPath);
+    stmtRegisterFailedPath.bind(path);
+    stmtRegisterFailedPath.bind(time(0));
+    if (sqlite3_step(stmtRegisterFailedPath) != SQLITE_DONE)
+        throw SQLiteError(db, format("registering failed path `%1%'") % path);
 }
 
 
-void LocalStore::registerValidPath(const Path & path,
-    const Hash & hash, const PathSet & references,
-    const Path & deriver)
+bool LocalStore::hasPathFailed(const Path & path)
 {
-    ValidPathInfo info;
-    info.path = path;
-    info.hash = hash;
-    info.references = references;
-    info.deriver = deriver;
-    registerValidPath(info);
+    SQLiteStmtUse use(stmtHasPathFailed);
+    stmtHasPathFailed.bind(path);
+    int res = sqlite3_step(stmtHasPathFailed);
+    if (res != SQLITE_DONE && res != SQLITE_ROW)
+        throw SQLiteError(db, "querying whether path failed");
+    return res == SQLITE_ROW;
 }
 
 
-void LocalStore::registerValidPath(const ValidPathInfo & info, bool ignoreValidity)
+PathSet LocalStore::queryFailedPaths()
 {
-    Path infoFile = infoFileFor(info.path);
-
-    ValidPathInfo oldInfo;
-    if (pathExists(infoFile)) oldInfo = queryPathInfo(info.path);
-
-    /* Note that it's possible for infoFile to already exist. */
-
-    /* Acquire a lock on each referrer file.  This prevents those
-       paths from being invalidated.  (It would be a violation of the
-       store invariants if we registered info.path as valid while some
-       of its references are invalid.)  NB: there can be no deadlock
-       here since we're acquiring the locks in sorted order. */
-    PathSet lockNames;
-    foreach (PathSet::const_iterator, i, info.references)
-        if (*i != info.path) lockNames.insert(referrersFileFor(*i));
-    PathLocks referrerLocks(lockNames);
-    referrerLocks.setDeletion(true);
-        
-    string refs;
-    foreach (PathSet::const_iterator, i, info.references) {
-        if (!refs.empty()) refs += " ";
-        refs += *i;
-
-        if (!ignoreValidity && *i != info.path && !isValidPath(*i))
-            throw Error(format("cannot register `%1%' as valid, because its reference `%2%' isn't valid")
-                % info.path % *i);
-
-        /* Update the referrer mapping for *i.  This must be done
-           before the info file is written to maintain the invariant
-           that if `path' is a valid path, then all its references
-           have referrer mappings back to `path'.  A " " is prefixed
-           to separate it from the previous entry.  It's not suffixed
-           to deal with interrupted partial writes to this file. */
-        if (oldInfo.references.find(*i) == oldInfo.references.end())
-            appendReferrer(*i, info.path, false);
+    SQLiteStmtUse use(stmtQueryFailedPaths);
+
+    PathSet res;
+    int r;
+    while ((r = sqlite3_step(stmtQueryFailedPaths)) == SQLITE_ROW) {
+        const char * s = (const char *) sqlite3_column_text(stmtQueryFailedPaths, 0);
+        assert(s);
+        res.insert(s);
     }
 
-    assert(info.hash.type == htSHA256);
+    if (r != SQLITE_DONE)
+        throw SQLiteError(db, "error querying failed paths");
 
-    string s = (format(
-        "Hash: sha256:%1%\n"
-        "References: %2%\n"
-        "Deriver: %3%\n"
-        "Registered-At: %4%\n")
-        % printHash(info.hash) % refs % info.deriver %
-        (oldInfo.registrationTime ? oldInfo.registrationTime : time(0))).str();
-
-    /* Atomically rewrite the info file. */
-    Path tmpFile = tmpFileForAtomicUpdate(infoFile);
-    writeFile(tmpFile, s, doFsync);
-    if (rename(tmpFile.c_str(), infoFile.c_str()) == -1)
-        throw SysError(format("cannot rename `%1%' to `%2%'") % tmpFile % infoFile);
-
-    pathInfoCache[info.path] = info;
+    return res;
 }
 
 
-void LocalStore::registerFailedPath(const Path & path)
+void LocalStore::clearFailedPaths(const PathSet & paths)
 {
-    /* Write an empty file in the .../failed directory to denote the
-       failure of the builder for `path'. */
-    writeFile(failedFileFor(path), "");
-}
+    SQLiteTxn txn(db);
 
+    foreach (PathSet::const_iterator, i, paths) {
+        SQLiteStmtUse use(stmtClearFailedPath);
+        stmtClearFailedPath.bind(*i);
+        if (sqlite3_step(stmtClearFailedPath) != SQLITE_DONE)
+            throw SQLiteError(db, format("clearing failed path `%1%' in database") % *i);
+    }
 
-bool LocalStore::hasPathFailed(const Path & path)
-{
-    return pathExists(failedFileFor(path));
+    txn.commit();
 }
 
 
@@ -387,91 +557,91 @@ Hash parseHashField(const Path & path, const string & s)
 }
 
 
-ValidPathInfo LocalStore::queryPathInfo(const Path & path, bool ignoreErrors)
+ValidPathInfo LocalStore::queryPathInfo(const Path & path)
 {
-    ValidPathInfo res;
-    res.path = path;
+    ValidPathInfo info;
+    info.path = path;
 
     assertStorePath(path);
 
-    if (!isValidPath(path))
-        throw Error(format("path `%1%' is not valid") % path);
+    /* Get the path info. */
+    SQLiteStmtUse use1(stmtQueryPathInfo);
 
-    std::map<Path, ValidPathInfo>::iterator lookup = pathInfoCache.find(path);
-    if (lookup != pathInfoCache.end()) return lookup->second;
+    stmtQueryPathInfo.bind(path);
     
-    /* Read the info file. */
-    Path infoFile = infoFileFor(path);
-    if (!pathExists(infoFile))
-        throw Error(format("path `%1%' is not valid") % path);
-    string info = readFile(infoFile);
+    int r = sqlite3_step(stmtQueryPathInfo);
+    if (r == SQLITE_DONE) throw Error(format("path `%1%' is not valid") % path);
+    if (r != SQLITE_ROW) throw SQLiteError(db, "querying path in database");
 
-    /* Parse it. */
-    Strings lines = tokenizeString(info, "\n");
+    info.id = sqlite3_column_int(stmtQueryPathInfo, 0);
 
-    foreach (Strings::iterator, i, lines) {
-        string::size_type p = i->find(':');
-        if (p == string::npos) {
-            if (!ignoreErrors)
-                throw Error(format("corrupt line in `%1%': %2%") % infoFile % *i);
-            continue; /* bad line */
-        }
-        string name(*i, 0, p);
-        string value(*i, p + 2);
-        if (name == "References") {
-            Strings refs = tokenizeString(value, " ");
-            res.references = PathSet(refs.begin(), refs.end());
-        } else if (name == "Deriver") {
-            res.deriver = value;
-        } else if (name == "Hash") {
-            try {
-                res.hash = parseHashField(path, value);
-            } catch (Error & e) {
-                if (!ignoreErrors) throw;
-                printMsg(lvlError, format("cannot parse hash field in `%1%': %2%") % infoFile % e.msg());
-            }
-        } else if (name == "Registered-At") {
-            int n = 0;
-            string2Int(value, n);
-            res.registrationTime = n;
-        }
+    const char * s = (const char *) sqlite3_column_text(stmtQueryPathInfo, 1);
+    assert(s);
+    info.hash = parseHashField(path, s);
+    
+    info.registrationTime = sqlite3_column_int(stmtQueryPathInfo, 2);
+
+    s = (const char *) sqlite3_column_text(stmtQueryPathInfo, 3);
+    if (s) info.deriver = s;
+
+    /* Get the references. */
+    SQLiteStmtUse use2(stmtQueryReferences);
+
+    stmtQueryReferences.bind(info.id);
+
+    while ((r = sqlite3_step(stmtQueryReferences)) == SQLITE_ROW) {
+        s = (const char *) sqlite3_column_text(stmtQueryReferences, 0);
+        assert(s);
+        info.references.insert(s);
     }
 
-    return pathInfoCache[path] = res;
+    if (r != SQLITE_DONE)
+        throw SQLiteError(db, format("error getting references of `%1%'") % path);
+
+    return info;
 }
 
 
-bool LocalStore::isValidPath(const Path & path)
+unsigned long long LocalStore::queryValidPathId(const Path & path)
 {
-    /* Files in the info directory starting with a `.' are temporary
-       files. */
-    if (baseNameOf(path).at(0) == '.') return false;
-
-    /* A path is valid if its info file exists and has a non-zero
-       size.  (The non-zero size restriction is to be robust to
-       certain kinds of filesystem corruption, particularly with
-       ext4.) */
-    Path infoFile = infoFileFor(path);
+    SQLiteStmtUse use(stmtQueryPathInfo);
+    stmtQueryPathInfo.bind(path);
+    int res = sqlite3_step(stmtQueryPathInfo);
+    if (res == SQLITE_ROW) return sqlite3_column_int(stmtQueryPathInfo, 0);
+    if (res == SQLITE_DONE) throw Error(format("path `%1%' is not valid") % path);
+    throw SQLiteError(db, "querying path in database");
+}
 
-    struct stat st;
-    if (lstat(infoFile.c_str(), &st)) {
-        if (errno == ENOENT) return false;
-        throw SysError(format("getting status of `%1%'") % infoFile);
-    }
 
-    if (st.st_size == 0) return false;
-    
-    return true;
+bool LocalStore::isValidPath(const Path & path)
+{
+    SQLiteStmtUse use(stmtQueryPathInfo);
+    stmtQueryPathInfo.bind(path);
+    int res = sqlite3_step(stmtQueryPathInfo);
+    if (res != SQLITE_DONE && res != SQLITE_ROW)
+        throw SQLiteError(db, "querying path in database");
+    return res == SQLITE_ROW;
 }
 
 
 PathSet LocalStore::queryValidPaths()
 {
-    PathSet paths;
-    Strings entries = readDirectory(nixDBPath + "/info");
-    foreach (Strings::iterator, i, entries)
-        if (i->at(0) != '.') paths.insert(nixStore + "/" + *i);
-    return paths;
+    SQLiteStmt stmt;
+    stmt.create(db, "select path from ValidPaths");
+    
+    PathSet res;
+    
+    int r;
+    while ((r = sqlite3_step(stmt)) == SQLITE_ROW) {
+        const char * s = (const char *) sqlite3_column_text(stmt, 0);
+        assert(s);
+        res.insert(s);
+    }
+
+    if (r != SQLITE_DONE)
+        throw SQLiteError(db, "error getting valid paths");
+
+    return res;
 }
 
 
@@ -483,45 +653,73 @@ void LocalStore::queryReferences(const Path & path,
 }
 
 
-bool LocalStore::queryReferrersInternal(const Path & path, PathSet & referrers)
+void LocalStore::queryReferrers(const Path & path, PathSet & referrers)
 {
-    bool allValid = true;
-    
-    if (!isValidPath(path))
-        throw Error(format("path `%1%' is not valid") % path);
+    assertStorePath(path);
 
-    /* No locking is necessary here: updates are only done by
-       appending or by atomically replacing the file.  When appending,
-       there is a possibility that we see a partial entry, but it will
-       just be filtered out below (the partially written path will not
-       be valid, so it will be ignored). */
+    SQLiteStmtUse use(stmtQueryReferrers);
 
-    Path referrersFile = referrersFileFor(path);
-    if (!pathExists(referrersFile)) return true;
-    
-    AutoCloseFD fd = open(referrersFile.c_str(), O_RDONLY);
-    if (fd == -1) throw SysError(format("opening file `%1%'") % referrersFile);
+    stmtQueryReferrers.bind(path);
 
-    Paths refs = tokenizeString(readFile(fd), " ");
+    int r;
+    while ((r = sqlite3_step(stmtQueryReferrers)) == SQLITE_ROW) {
+        const char * s = (const char *) sqlite3_column_text(stmtQueryReferrers, 0);
+        assert(s);
+        referrers.insert(s);
+    }
+
+    if (r != SQLITE_DONE)
+        throw SQLiteError(db, format("error getting references of `%1%'") % path);
+}
 
-    foreach (Paths::iterator, i, refs)
-        /* Referrers can be invalid (see registerValidPath() for the
-           invariant), so we only return one if it is valid. */
-        if (isStorePath(*i) && isValidPath(*i)) referrers.insert(*i); else allValid = false;
 
-    return allValid;
+Path LocalStore::queryDeriver(const Path & path)
+{
+    return queryPathInfo(path).deriver;
 }
 
 
-void LocalStore::queryReferrers(const Path & path, PathSet & referrers)
+PathSet LocalStore::queryValidDerivers(const Path & path)
 {
-    queryReferrersInternal(path, referrers);
+    assertStorePath(path);
+
+    SQLiteStmtUse use(stmtQueryValidDerivers);
+    stmtQueryValidDerivers.bind(path);
+
+    PathSet derivers;
+    int r;
+    while ((r = sqlite3_step(stmtQueryValidDerivers)) == SQLITE_ROW) {
+        const char * s = (const char *) sqlite3_column_text(stmtQueryValidDerivers, 1);
+        assert(s);
+        derivers.insert(s);
+    }
+    
+    if (r != SQLITE_DONE)
+        throw SQLiteError(db, format("error getting valid derivers of `%1%'") % path);
+    
+    return derivers;
 }
 
 
-Path LocalStore::queryDeriver(const Path & path)
+PathSet LocalStore::queryDerivationOutputs(const Path & path)
 {
-    return queryPathInfo(path).deriver;
+    SQLiteTxn txn(db);
+    
+    SQLiteStmtUse use(stmtQueryDerivationOutputs);
+    stmtQueryDerivationOutputs.bind(queryValidPathId(path));
+    
+    PathSet outputs;
+    int r;
+    while ((r = sqlite3_step(stmtQueryDerivationOutputs)) == SQLITE_ROW) {
+        const char * s = (const char *) sqlite3_column_text(stmtQueryDerivationOutputs, 1);
+        assert(s);
+        outputs.insert(s);
+    }
+    
+    if (r != SQLITE_DONE)
+        throw SQLiteError(db, format("error getting outputs of `%1%'") % path);
+
+    return outputs;
 }
 
 
@@ -635,39 +833,22 @@ Hash LocalStore::queryPathHash(const Path & path)
 }
 
 
-static void dfsVisit(std::map<Path, ValidPathInfo> & infos,
-    const Path & path, PathSet & visited, Paths & sorted)
-{
-    if (visited.find(path) != visited.end()) return;
-    visited.insert(path);
-
-    ValidPathInfo & info(infos[path]);
-    
-    foreach (PathSet::iterator, i, info.references)
-        if (infos.find(*i) != infos.end())
-            dfsVisit(infos, *i, visited, sorted);
-
-    sorted.push_back(path);
-}
-
-
 void LocalStore::registerValidPaths(const ValidPathInfos & infos)
 {
-    std::map<Path, ValidPathInfo> infosMap;
+    SQLiteTxn txn(db);
     
-    /* Sort the paths topologically under the references relation, so
-       that if path A is referenced by B, then A is registered before
-       B. */
     foreach (ValidPathInfos::const_iterator, i, infos)
-        infosMap[i->path] = *i;
-
-    PathSet visited;
-    Paths sorted;
-    foreach (ValidPathInfos::const_iterator, i, infos)
-        dfsVisit(infosMap, i->path, visited, sorted);
+        /* !!! Maybe the registration info should be updated if the
+           path is already valid. */
+        if (!isValidPath(i->path)) addValidPath(*i);
+
+    foreach (ValidPathInfos::const_iterator, i, infos) {
+        unsigned long long referrer = queryValidPathId(i->path);
+        foreach (PathSet::iterator, j, i->references)
+            addReference(referrer, queryValidPathId(*j));
+    }
 
-    foreach (Paths::iterator, i, sorted)
-        registerValidPath(infosMap[*i]);
+    txn.commit();
 }
 
 
@@ -677,43 +858,15 @@ void LocalStore::invalidatePath(const Path & path)
 {
     debug(format("invalidating path `%1%'") % path);
 
-    ValidPathInfo info;
+    SQLiteStmtUse use(stmtInvalidatePath);
 
-    if (pathExists(infoFileFor(path))) {
-        info = queryPathInfo(path);
+    stmtInvalidatePath.bind(path);
 
-        /* Remove the info file. */
-        Path p = infoFileFor(path);
-        if (unlink(p.c_str()) == -1)
-            throw SysError(format("unlinking `%1%'") % p);
-    }
+    if (sqlite3_step(stmtInvalidatePath) != SQLITE_DONE)
+        throw SQLiteError(db, format("invalidating path `%1%' in database") % path);
 
-    /* Remove the referrers file for `path'. */
-    Path p = referrersFileFor(path);
-    if (pathExists(p) && unlink(p.c_str()) == -1)
-        throw SysError(format("unlinking `%1%'") % p);
-
-    /* Clear `path' from the info cache. */
-    pathInfoCache.erase(path);
-    delayedUpdates.erase(path);
-
-    /* Cause the referrer files for each path referenced by this one
-       to be updated.  This has to happen after removing the info file
-       to preserve the invariant (see registerValidPath()).
-
-       The referrer files are updated lazily in flushDelayedUpdates()
-       to prevent quadratic performance in the garbage collector
-       (i.e., when N referrers to some path X are deleted, we have to
-       rewrite the referrers file for X N times, causing O(N^2) I/O).
-
-       What happens if we die before the referrer file can be updated?
-       That's not a problem, because stale (invalid) entries in the
-       referrer file are ignored by queryReferrers().  Thus a referrer
-       file is allowed to have stale entries; removing them is just an
-       optimisation.  verifyStore() gets rid of them eventually.
-    */
-    foreach (PathSet::iterator, i, info.references)
-        if (*i != path) delayedUpdates.insert(*i);
+    /* Note that the foreign key constraints on the Refs table take
+       care of deleting the references entries for `path'. */
 }
 
 
@@ -815,16 +968,19 @@ struct HashAndWriteSink : Sink
 {
     Sink & writeSink;
     HashSink hashSink;
-    bool hashing;
     HashAndWriteSink(Sink & writeSink) : writeSink(writeSink), hashSink(htSHA256)
     {
-        hashing = true;
     }
     virtual void operator ()
         (const unsigned char * data, unsigned int len)
     {
         writeSink(data, len);
-        if (hashing) hashSink(data, len);
+        hashSink(data, len);
+    }
+    Hash currentHash()
+    {
+        HashSink hashSinkClone(hashSink);
+        return hashSinkClone.finish();
     }
 };
 
@@ -855,6 +1011,14 @@ void LocalStore::exportPath(const Path & path, bool sign,
     
     dumpPath(path, hashAndWriteSink);
 
+    /* Refuse to export paths that have changed.  This prevents
+       filesystem corruption from spreading to other machines. */
+    Hash hash = hashAndWriteSink.currentHash();
+    Hash storedHash = queryPathHash(path);
+    if (hash != storedHash)
+        throw Error(format("hash of path `%1%' has changed from `%2%' to `%3%'!") % path
+            % printHash(storedHash) % printHash(hash));
+
     writeInt(EXPORT_MAGIC, hashAndWriteSink);
 
     writeString(path, hashAndWriteSink);
@@ -867,14 +1031,11 @@ void LocalStore::exportPath(const Path & path, bool sign,
     writeString(deriver, hashAndWriteSink);
 
     if (sign) {
-        Hash hash = hashAndWriteSink.hashSink.finish();
-        hashAndWriteSink.hashing = false;
-
+        Hash hash = hashAndWriteSink.currentHash();
+ 
         writeInt(1, hashAndWriteSink);
         
         Path tmpDir = createTempDir();
-        PathLocks tmpDirLock(singleton<PathSet, Path>(tmpDir));
-        tmpDirLock.setDeletion(true);
         AutoDelete delTmp(tmpDir);
         Path hashFile = tmpDir + "/hash";
         writeFile(hashFile, printHash(hash));
@@ -916,6 +1077,22 @@ struct HashAndReadSource : Source
 };
 
 
+/* Create a temporary directory in the store that won't be
+   garbage-collected. */
+Path LocalStore::createTempDirInStore()
+{
+    Path tmpDir;
+    do {
+        /* There is a slight possibility that `tmpDir' gets deleted by
+           the GC between createTempDir() and addTempRoot(), so repeat
+           until `tmpDir' exists. */
+        tmpDir = createTempDir(nixStore);
+        addTempRoot(tmpDir);
+    } while (!pathExists(tmpDir));
+    return tmpDir;
+}
+
+
 Path LocalStore::importPath(bool requireSignature, Source & source)
 {
     HashAndReadSource hashAndReadSource(source);
@@ -923,10 +1100,8 @@ Path LocalStore::importPath(bool requireSignature, Source & source)
     /* We don't yet know what store path this archive contains (the
        store path follows the archive data proper), and besides, we
        don't know yet whether the signature is valid. */
-    Path tmpDir = createTempDir(nixStore);
-    PathLocks tmpDirLock(singleton<PathSet, Path>(tmpDir));
-    tmpDirLock.setDeletion(true);
-    AutoDelete delTmp(tmpDir); /* !!! could be GC'ed! */
+    Path tmpDir = createTempDirInStore();
+    AutoDelete delTmp(tmpDir);
     Path unpacked = tmpDir + "/unpacked";
 
     restorePath(unpacked, hashAndReadSource);
@@ -1026,11 +1201,6 @@ void LocalStore::deleteFromStore(const Path & path, unsigned long long & bytesFr
     assertStorePath(path);
 
     if (isValidPath(path)) {
-        /* Acquire a lock on the referrers file to prevent new
-           referrers to this path from appearing while we're deleting
-           it. */
-        PathLocks referrersLock(singleton<PathSet, Path>(referrersFileFor(path)));
-        referrersLock.setDeletion(true);
         PathSet referrers; queryReferrers(path, referrers);
         referrers.erase(path); /* ignore self-references */
         if (!referrers.empty())
@@ -1052,68 +1222,26 @@ void LocalStore::verifyStore(bool checkContents)
     
     foreach (PathSet::iterator, i, validPaths2) {
         checkInterrupt();
+        /* !!! invalidatePath() will probably fail due to the foreign
+           key constraints on the Ref table. */
         if (!isStorePath(*i)) {
             printMsg(lvlError, format("path `%1%' is not in the Nix store") % *i);
             invalidatePath(*i);
         } else if (!pathExists(*i)) {
             printMsg(lvlError, format("path `%1%' disappeared") % *i);
             invalidatePath(*i);
-        } else {
-            Path infoFile = infoFileFor(*i);
-            struct stat st;
-            if (lstat(infoFile.c_str(), &st))
-                throw SysError(format("getting status of `%1%'") % infoFile);
-            if (st.st_size == 0) {
-                printMsg(lvlError, format("removing corrupt info file `%1%'") % infoFile);
-                if (unlink(infoFile.c_str()) == -1)
-                    throw SysError(format("unlinking `%1%'") % infoFile);
-            }
-            else validPaths.insert(*i);
-        }
+        } else validPaths.insert(*i);
     }
 
+    /* Optionally, check the content hashes (slow). */
+    if (checkContents) {
+        printMsg(lvlInfo, "checking hashes");
 
-    /* Check the store path meta-information. */
-    printMsg(lvlInfo, "checking path meta-information");
-
-    std::map<Path, PathSet> referrersCache;
-    
-    foreach (PathSet::iterator, i, validPaths) {
-        bool update = false;
-        ValidPathInfo info = queryPathInfo(*i, true);
-
-        /* Check the references: each reference should be valid, and
-           it should have a matching referrer. */
-        foreach (PathSet::iterator, j, info.references) {
-            if (validPaths.find(*j) == validPaths.end()) {
-                printMsg(lvlError, format("incomplete closure: `%1%' needs missing `%2%'")
-                    % *i % *j);
-                /* nothing we can do about it... */
-            } else {
-                if (referrersCache.find(*j) == referrersCache.end())
-                    queryReferrers(*j, referrersCache[*j]);
-                if (referrersCache[*j].find(*i) == referrersCache[*j].end()) {
-                    printMsg(lvlError, format("adding missing referrer mapping from `%1%' to `%2%'")
-                        % *j % *i);
-                    appendReferrer(*j, *i, true);
-                }
-            }
-        }
-
-        /* Check the deriver.  (Note that the deriver doesn't have to
-           be a valid path.) */
-        if (!info.deriver.empty() && !isStorePath(info.deriver)) {
-            info.deriver = "";
-            update = true;
-        }
+        foreach (PathSet::iterator, i, validPaths) {
+            ValidPathInfo info = queryPathInfo(*i);
 
-        /* Check the content hash (optionally - slow). */
-        if (info.hash.hashSize == 0) {
-            printMsg(lvlError, format("re-hashing `%1%'") % *i);
-            info.hash = hashPath(htSHA256, *i);
-            update = true;
-        } else if (checkContents) {
-            debug(format("checking contents of `%1%'") % *i);
+            /* Check the content hash (optionally - slow). */
+            printMsg(lvlTalkative, format("checking contents of `%1%'") % *i);
             Hash current = hashPath(info.hash.type, *i);
             if (current != info.hash) {
                 printMsg(lvlError, format("path `%1%' was modified! "
@@ -1121,67 +1249,90 @@ void LocalStore::verifyStore(bool checkContents)
                     % *i % printHash(info.hash) % printHash(current));
             }
         }
-
-        if (update) registerValidPath(info);
     }
+}
 
-    referrersCache.clear();
-    
 
-    /* Check the referrers. */
-    printMsg(lvlInfo, "checking referrers");
+/* Functions for upgrading from the pre-SQLite database. */
 
-    std::map<Path, PathSet> referencesCache;
-    
-    Strings entries = readDirectory(nixDBPath + "/referrer");
-    foreach (Strings::iterator, i, entries) {
-        Path from = nixStore + "/" + *i;
-        
-        if (validPaths.find(from) == validPaths.end()) {
-            /* !!! This removes lock files as well.  Need to check
-               whether that's okay. */
-            printMsg(lvlError, format("removing referrers file for invalid `%1%'") % from);
-            Path p = referrersFileFor(from);
-            if (unlink(p.c_str()) == -1)
-                throw SysError(format("unlinking `%1%'") % p);
-            continue;
-        }
+PathSet LocalStore::queryValidPathsOld()
+{
+    PathSet paths;
+    Strings entries = readDirectory(nixDBPath + "/info");
+    foreach (Strings::iterator, i, entries)
+        if (i->at(0) != '.') paths.insert(nixStore + "/" + *i);
+    return paths;
+}
 
-        PathSet referrers;
-        bool allValid = queryReferrersInternal(from, referrers);
-        bool update = false;
 
-        if (!allValid) {
-            printMsg(lvlError, format("removing some stale referrers for `%1%'") % from);
-            update = true;
-        }
+ValidPathInfo LocalStore::queryPathInfoOld(const Path & path)
+{
+    ValidPathInfo res;
+    res.path = path;
 
-        /* Each referrer should have a matching reference. */
-        PathSet referrersNew;
-        foreach (PathSet::iterator, j, referrers) {
-            if (referencesCache.find(*j) == referencesCache.end())
-                queryReferences(*j, referencesCache[*j]);
-            if (referencesCache[*j].find(from) == referencesCache[*j].end()) {
-                printMsg(lvlError, format("removing unexpected referrer mapping from `%1%' to `%2%'")
-                    % from % *j);
-                update = true;
-            } else referrersNew.insert(*j);
-        }
+    /* Read the info file. */
+    string baseName = baseNameOf(path);
+    Path infoFile = (format("%1%/info/%2%") % nixDBPath % baseName).str();
+    if (!pathExists(infoFile))
+        throw Error(format("path `%1%' is not valid") % path);
+    string info = readFile(infoFile);
+
+    /* Parse it. */
+    Strings lines = tokenizeString(info, "\n");
 
-        if (update) rewriteReferrers(from, false, referrersNew);
+    foreach (Strings::iterator, i, lines) {
+        string::size_type p = i->find(':');
+        if (p == string::npos)
+            throw Error(format("corrupt line in `%1%': %2%") % infoFile % *i);
+        string name(*i, 0, p);
+        string value(*i, p + 2);
+        if (name == "References") {
+            Strings refs = tokenizeString(value, " ");
+            res.references = PathSet(refs.begin(), refs.end());
+        } else if (name == "Deriver") {
+            res.deriver = value;
+        } else if (name == "Hash") {
+            res.hash = parseHashField(path, value);
+        } else if (name == "Registered-At") {
+            int n = 0;
+            string2Int(value, n);
+            res.registrationTime = n;
+        }
     }
+
+    return res;
 }
 
 
-/* Upgrade from schema 4 (Nix 0.11) to schema 5 (Nix >= 0.12).  The
-   old schema uses Berkeley DB, the new one stores store path
-   meta-information in files. */
-void LocalStore::upgradeStore12()
+/* Upgrade from schema 5 (Nix 0.12) to schema 6 (Nix >= 0.15). */
+void LocalStore::upgradeStore6()
 {
-    throw Error(
-        "Your Nix store has a database in Berkeley DB format,\n"
-        "which is no longer supported. To convert to the new format,\n"
-        "please upgrade Nix to version 0.12 first.");
+    printMsg(lvlError, "upgrading Nix store to new schema (this may take a while)...");
+
+    openDB(true);
+
+    PathSet validPaths = queryValidPathsOld();
+
+    SQLiteTxn txn(db);
+    
+    foreach (PathSet::iterator, i, validPaths) {
+        addValidPath(queryPathInfoOld(*i));
+        std::cerr << ".";
+    }
+
+    std::cerr << "|";
+    
+    foreach (PathSet::iterator, i, validPaths) {
+        ValidPathInfo info = queryPathInfoOld(*i);
+        unsigned long long referrer = queryValidPathId(*i);
+        foreach (PathSet::iterator, j, info.references)
+            addReference(referrer, queryValidPathId(*j));
+        std::cerr << ".";
+    }
+
+    std::cerr << "\n";
+
+    txn.commit();
 }
 
 
diff --git a/src/libstore/local-store.hh b/src/libstore/local-store.hh
index 31f8d91096a3..3ae964f0544d 100644
--- a/src/libstore/local-store.hh
+++ b/src/libstore/local-store.hh
@@ -7,13 +7,18 @@
 #include "util.hh"
 
 
+class sqlite3;
+class sqlite3_stmt;
+
+
 namespace nix {
 
 
 /* Nix store and database schema version.  Version 1 (or 0) was Nix <=
    0.7.  Version 2 was Nix 0.8 and 0.9.  Version 3 is Nix 0.10.
-   Version 4 is Nix 0.11.  Version 5 is Nix 0.12*/
-const int nixSchemaVersion = 5;
+   Version 4 is Nix 0.11.  Version 5 is Nix 0.12-0.14.  Version 6 is
+   Nix 0.15. */
+const int nixSchemaVersion = 6;
 
 
 extern string drvsLogDir;
@@ -41,6 +46,33 @@ struct RunningSubstituter
 };
 
 
+/* Wrapper object to close the SQLite database automatically. */
+struct SQLite
+{
+    sqlite3 * db;
+    SQLite() { db = 0; }
+    ~SQLite();
+    operator sqlite3 * () { return db; }
+};
+
+
+/* Wrapper object to create and destroy SQLite prepared statements. */
+struct SQLiteStmt
+{
+    sqlite3 * db;
+    sqlite3_stmt * stmt;
+    unsigned int curArg;
+    SQLiteStmt() { stmt = 0; }
+    void create(sqlite3 * db, const string & s);
+    void reset();
+    ~SQLiteStmt();
+    operator sqlite3_stmt * () { return stmt; }
+    void bind(const string & value);
+    void bind(int value);
+    void bind();
+};
+    
+
 class LocalStore : public StoreAPI
 {
 private:
@@ -71,6 +103,14 @@ public:
     void queryReferrers(const Path & path, PathSet & referrers);
 
     Path queryDeriver(const Path & path);
+
+    /* Return all currently valid derivations that have `path' as an
+       output.  (Note that the result of `queryDeriver()' is the
+       derivation that was actually used to produce `path', which may
+       not exist anymore.) */
+    PathSet queryValidDerivers(const Path & path);
+
+    PathSet queryDerivationOutputs(const Path & path);
     
     PathSet querySubstitutablePaths();
     
@@ -144,6 +184,10 @@ public:
     /* Query whether `path' previously failed to build. */
     bool hasPathFailed(const Path & path);
 
+    PathSet queryFailedPaths();
+
+    void clearFailedPaths(const PathSet & paths);
+
 private:
 
     Path schemaPath;
@@ -151,45 +195,59 @@ private:
     /* Lock file used for upgrading. */
     AutoCloseFD globalLock;
 
-    /* !!! The cache can grow very big.  Maybe it should be pruned
-       every once in a while. */
-    std::map<Path, ValidPathInfo> pathInfoCache;
+    /* The SQLite database object. */
+    SQLite db;
+
+    /* Some precompiled SQLite statements. */
+    SQLiteStmt stmtRegisterValidPath;
+    SQLiteStmt stmtAddReference;
+    SQLiteStmt stmtQueryPathInfo;
+    SQLiteStmt stmtQueryReferences;
+    SQLiteStmt stmtQueryReferrers;
+    SQLiteStmt stmtInvalidatePath;
+    SQLiteStmt stmtRegisterFailedPath;
+    SQLiteStmt stmtHasPathFailed;
+    SQLiteStmt stmtQueryFailedPaths;
+    SQLiteStmt stmtClearFailedPath;
+    SQLiteStmt stmtAddDerivationOutput;
+    SQLiteStmt stmtQueryValidDerivers;
+    SQLiteStmt stmtQueryDerivationOutputs;
 
-    /* Store paths for which the referrers file must be purged. */
-    PathSet delayedUpdates;
+    int getSchema();
 
-    /* Whether to do an fsync() after writing Nix metadata. */
-    bool doFsync;
+    void openDB(bool create);
 
-    int getSchema();
+    unsigned long long queryValidPathId(const Path & path);
 
-    void registerValidPath(const ValidPathInfo & info, bool ignoreValidity = false);
+    unsigned long long addValidPath(const ValidPathInfo & info);
+        
+    void addReference(unsigned long long referrer, unsigned long long reference);
+    
+    void registerValidPath(const ValidPathInfo & info);
 
-    ValidPathInfo queryPathInfo(const Path & path, bool ignoreErrors = false);
+    ValidPathInfo queryPathInfo(const Path & path);
 
     void appendReferrer(const Path & from, const Path & to, bool lock);
     
     void rewriteReferrers(const Path & path, bool purge, PathSet referrers);
 
-    void flushDelayedUpdates();
-    
-    bool queryReferrersInternal(const Path & path, PathSet & referrers);
-    
     void invalidatePath(const Path & path);
-    
-    void upgradeStore12();
+
+    void upgradeStore6();
+    PathSet queryValidPathsOld();
+    ValidPathInfo queryPathInfoOld(const Path & path);
 
     struct GCState;
 
     bool tryToDelete(GCState & state, const Path & path);
     
-    PathSet findDerivers(GCState & state, const Path & path);
-    
     bool isActiveTempFile(const GCState & state,
         const Path & path, const string & suffix);
         
     void startSubstituter(const Path & substituter,
         RunningSubstituter & runningSubstituter);
+
+    Path createTempDirInStore();
 };
 
 
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index f2cc20626915..d52dd6346c7a 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -27,10 +27,10 @@ void computeFSClosure(const Path & storePath,
         store->queryReferences(storePath, references);
 
     if (includeOutputs && isDerivation(storePath)) {
-        Derivation drv = derivationFromPath(storePath);
-        foreach (DerivationOutputs::iterator, i, drv.outputs)
-            if (store->isValidPath(i->second.path))
-                computeFSClosure(i->second.path, paths, flipDirection, true);
+        PathSet outputs = store->queryDerivationOutputs(storePath);
+        foreach (PathSet::iterator, i, outputs)
+            if (store->isValidPath(*i))
+                computeFSClosure(*i, paths, flipDirection, true);
     }
 
     foreach (PathSet::iterator, i, references)
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index 5143143f57c3..334ad95cf9df 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -214,7 +214,9 @@ bool RemoteStore::isValidPath(const Path & path)
 PathSet RemoteStore::queryValidPaths()
 {
     openConnection();
-    throw Error("not implemented");
+    writeInt(wopQueryValidPaths, to);
+    processStderr();
+    return readStorePaths(from);
 }
 
 
@@ -294,6 +296,16 @@ Path RemoteStore::queryDeriver(const Path & path)
 }
 
 
+PathSet RemoteStore::queryDerivationOutputs(const Path & path)
+{
+    openConnection();
+    writeInt(wopQueryDerivationOutputs, to);
+    writeString(path, to);
+    processStderr();
+    return readStorePaths(from);
+}
+
+
 Path RemoteStore::addToStore(const Path & _srcPath,
     bool recursive, HashType hashAlgo, PathFilter & filter)
 {
@@ -439,6 +451,25 @@ void RemoteStore::collectGarbage(const GCOptions & options, GCResults & results)
 }
 
 
+PathSet RemoteStore::queryFailedPaths()
+{
+    openConnection();
+    writeInt(wopQueryFailedPaths, to);
+    processStderr();
+    return readStorePaths(from);
+}
+
+
+void RemoteStore::clearFailedPaths(const PathSet & paths)
+{
+    openConnection();
+    writeInt(wopClearFailedPaths, to);
+    writeStringSet(paths, to);
+    processStderr();
+    readInt(from);
+}
+
+
 void RemoteStore::processStderr(Sink * sink, Source * source)
 {
     unsigned int msg;
diff --git a/src/libstore/remote-store.hh b/src/libstore/remote-store.hh
index 3d55d23d958e..02a1c475252d 100644
--- a/src/libstore/remote-store.hh
+++ b/src/libstore/remote-store.hh
@@ -37,6 +37,8 @@ public:
 
     Path queryDeriver(const Path & path);
     
+    PathSet queryDerivationOutputs(const Path & path);
+    
     bool hasSubstitutes(const Path & path);
     
     bool querySubstitutablePathInfo(const Path & path,
@@ -68,6 +70,10 @@ public:
 
     void collectGarbage(const GCOptions & options, GCResults & results);
     
+    PathSet queryFailedPaths();
+
+    void clearFailedPaths(const PathSet & paths);
+    
 private:
     AutoCloseFD fdSocket;
     FdSink to;
diff --git a/src/libstore/schema.sql b/src/libstore/schema.sql
new file mode 100644
index 000000000000..7438632edbd9
--- /dev/null
+++ b/src/libstore/schema.sql
@@ -0,0 +1,43 @@
+create table if not exists ValidPaths (
+    id               integer primary key autoincrement not null,
+    path             text unique not null,
+    hash             text not null,
+    registrationTime integer not null,
+    deriver          text
+);
+
+create table if not exists Refs (
+    referrer  integer not null,
+    reference integer not null,
+    primary key (referrer, reference),
+    foreign key (referrer) references ValidPaths(id) on delete cascade,
+    foreign key (reference) references ValidPaths(id) on delete restrict
+);
+
+create index if not exists IndexReferrer on Refs(referrer);
+create index if not exists IndexReference on Refs(reference);
+
+-- Paths can refer to themselves, causing a tuple (N, N) in the Refs
+-- table.  This causes a deletion of the corresponding row in
+-- ValidPaths to cause a foreign key constraint violation (due to `on
+-- delete restrict' on the `reference' column).  Therefore, explicitly
+-- get rid of self-references.
+create trigger if not exists DeleteSelfRefs before delete on ValidPaths
+  begin
+    delete from Refs where referrer = old.id and reference = old.id;
+  end;
+
+create table if not exists DerivationOutputs (
+    drv  integer not null,
+    id   text not null, -- symbolic output id, usually "out"
+    path text not null,
+    primary key (drv, id),
+    foreign key (drv) references ValidPaths(id) on delete cascade
+);
+
+create index if not exists IndexDerivationOutputs on DerivationOutputs(path);
+
+create table if not exists FailedPaths (
+    path text primary key not null,
+    time integer not null
+);
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index f0abe61ad1e1..01dd51621625 100644
--- a/src/libstore/store-api.cc
+++ b/src/libstore/store-api.cc
@@ -1,7 +1,6 @@
 #include "store-api.hh"
 #include "globals.hh"
 #include "util.hh"
-#include "derivations.hh"
 
 #include <limits.h>
 
@@ -53,18 +52,6 @@ Path toStorePath(const Path & path)
 }
 
 
-string getNameOfStorePath(const Path & path)
-{
-    Path::size_type slash = path.rfind('/');
-    string p = slash == Path::npos ? path : string(path, slash + 1);
-    Path::size_type dash = p.find('-');
-    assert(dash != Path::npos);
-    string p2 = string(p, dash + 1);
-    if (isDerivation(p2)) p2 = string(p2, 0, p2.size() - 4);
-    return p2;
-}
-
-
 Path followLinksToStore(const Path & _path)
 {
     Path path = absPath(_path);
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index 0590f448c0e2..3b81bfa39438 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -110,33 +110,18 @@ public:
     virtual void queryReferences(const Path & path,
         PathSet & references) = 0;
 
-    /* Like queryReferences, but with self-references filtered out. */
-    PathSet queryReferencesNoSelf(const Path & path)
-    {
-        PathSet res;
-        queryReferences(path, res);
-        res.erase(path);
-        return res;
-    }
-
     /* Queries the set of incoming FS references for a store path.
        The result is not cleared. */
     virtual void queryReferrers(const Path & path,
         PathSet & referrers) = 0;
 
-    /* Like queryReferrers, but with self-references filtered out. */
-    PathSet queryReferrersNoSelf(const Path & path)
-    {
-        PathSet res;
-        queryReferrers(path, res);
-        res.erase(path);
-        return res;
-    }
-
     /* Query the deriver of a store path.  Return the empty string if
        no deriver has been set. */
     virtual Path queryDeriver(const Path & path) = 0;
 
+    /* Query the outputs of the derivation denoted by `path'. */
+    virtual PathSet queryDerivationOutputs(const Path & path) = 0;
+    
     /* Query whether a path has substitutes. */
     virtual bool hasSubstitutes(const Path & path) = 0;
 
@@ -222,6 +207,13 @@ public:
 
     /* Perform a garbage collection. */
     virtual void collectGarbage(const GCOptions & options, GCResults & results) = 0;
+
+    /* Return the set of paths that have failed to build.*/
+    virtual PathSet queryFailedPaths() = 0;
+
+    /* Clear the "failed" status of the given paths.  The special
+       value `*' causes all failed paths to be cleared. */
+    virtual void clearFailedPaths(const PathSet & paths) = 0;
 };
 
 
@@ -241,12 +233,6 @@ void checkStoreName(const string & name);
 Path toStorePath(const Path & path);
 
 
-/* Get the "name" part of a store path, that is, the part after the
-   hash and the dash, and with any ".drv" suffix removed
-   (e.g. /nix/store/<hash>-foo-1.2.3.drv => foo-1.2.3). */
-string getNameOfStorePath(const Path & path);
-
-
 /* Follow symlinks until we end up with a path in the Nix store. */
 Path followLinksToStore(const Path & path);
 
@@ -331,6 +317,7 @@ struct ValidPathInfo
     Hash hash;
     PathSet references;
     time_t registrationTime;
+    unsigned long long id; // internal use only
     ValidPathInfo() : registrationTime(0) { }
 };
 
diff --git a/src/libstore/worker-protocol.hh b/src/libstore/worker-protocol.hh
index e44c1e36b56f..392a69acf654 100644
--- a/src/libstore/worker-protocol.hh
+++ b/src/libstore/worker-protocol.hh
@@ -34,6 +34,10 @@ typedef enum {
     wopSetOptions = 19,
     wopCollectGarbage = 20,
     wopQuerySubstitutablePathInfo = 21,
+    wopQueryDerivationOutputs = 22,
+    wopQueryValidPaths = 23,
+    wopQueryFailedPaths = 24,
+    wopClearFailedPaths = 25,
 } WorkerOp;
 
 
diff --git a/src/libutil/Makefile.am b/src/libutil/Makefile.am
index aa862208c6f9..98f32633b894 100644
--- a/src/libutil/Makefile.am
+++ b/src/libutil/Makefile.am
@@ -3,7 +3,7 @@ pkglib_LTLIBRARIES = libutil.la
 libutil_la_SOURCES = util.cc hash.cc serialise.cc \
   archive.cc xml-writer.cc
 
-libutil_la_LIBADD = ../boost/format/libformat.la
+libutil_la_LIBADD = ../boost/format/libformat.la ${aterm_lib} ${sqlite_lib}
 
 pkginclude_HEADERS = util.hh hash.hh serialise.hh \
   archive.hh xml-writer.hh types.hh
diff --git a/src/libutil/archive.cc b/src/libutil/archive.cc
index 8fde4328c47e..999b17cd2f19 100644
--- a/src/libutil/archive.cc
+++ b/src/libutil/archive.cc
@@ -181,8 +181,6 @@ static void parseContents(ParseSink & sink, Source & source, const Path & path)
         left -= n;
     }
 
-    sink.finalizeContents(size);
-
     readPadding(size, source);
 }
 
@@ -317,12 +315,6 @@ struct RestoreSink : ParseSink
         writeFull(fd, data, len);
     }
 
-    void finalizeContents(unsigned long long size)
-    {
-        errno = ftruncate(fd, size);
-        if (errno) throw SysError(format("truncating file to its allocated length of %1% bytes") % size);
-    }
-
     void createSymlink(const Path & path, const string & target)
     {
         Path p = dstPath + path;
diff --git a/src/libutil/archive.hh b/src/libutil/archive.hh
index f358a2a6be17..fff62031397c 100644
--- a/src/libutil/archive.hh
+++ b/src/libutil/archive.hh
@@ -64,7 +64,6 @@ struct ParseSink
     virtual void isExecutable() { };
     virtual void preallocateContents(unsigned long long size) { };
     virtual void receiveContents(unsigned char * data, unsigned int len) { };
-    virtual void finalizeContents(unsigned long long size) { };
 
     virtual void createSymlink(const Path & path, const string & target) { };
 };
diff --git a/src/libutil/hash.cc b/src/libutil/hash.cc
index eef01fe4d609..bd7e33a48e70 100644
--- a/src/libutil/hash.cc
+++ b/src/libutil/hash.cc
@@ -289,6 +289,13 @@ HashSink::HashSink(HashType ht) : ht(ht)
     start(ht, *ctx);
 }
     
+HashSink::HashSink(const HashSink & h)
+{
+    ht = h.ht;
+    ctx = new Ctx;
+    *ctx = *h.ctx;
+}
+    
 HashSink::~HashSink()
 {
     delete ctx;
diff --git a/src/libutil/hash.hh b/src/libutil/hash.hh
index 062d97254bfc..81425b23494c 100644
--- a/src/libutil/hash.hh
+++ b/src/libutil/hash.hh
@@ -96,6 +96,7 @@ private:
 
 public:
     HashSink(HashType ht);
+    HashSink(const HashSink & h);
     ~HashSink();
     virtual void operator () (const unsigned char * data, unsigned int len);
     Hash finish();
@@ -104,5 +105,5 @@ public:
 
 }
 
-    
+
 #endif /* !__HASH_H */
diff --git a/src/libutil/util.cc b/src/libutil/util.cc
index 98912e7a002c..e0c41a58d8ee 100644
--- a/src/libutil/util.cc
+++ b/src/libutil/util.cc
@@ -227,13 +227,12 @@ string readFile(const Path & path)
 }
 
 
-void writeFile(const Path & path, const string & s, bool doFsync)
+void writeFile(const Path & path, const string & s)
 {
     AutoCloseFD fd = open(path.c_str(), O_WRONLY | O_TRUNC | O_CREAT, 0666);
     if (fd == -1)
         throw SysError(format("opening file `%1%'") % path);
     writeFull(fd, (unsigned char *) s.c_str(), s.size());
-    if (doFsync) fsync(fd);
 }
 
 
diff --git a/src/libutil/util.hh b/src/libutil/util.hh
index ff710077ceaa..c45ebc062ffa 100644
--- a/src/libutil/util.hh
+++ b/src/libutil/util.hh
@@ -60,7 +60,7 @@ string readFile(int fd);
 string readFile(const Path & path);
 
 /* Write a string to a file. */
-void writeFile(const Path & path, const string & s, bool doFsync = false);
+void writeFile(const Path & path, const string & s);
 
 /* Read a line from a file descriptor. */
 string readLine(int fd);
diff --git a/src/nix-env/Makefile.am b/src/nix-env/Makefile.am
index 7dfa7425a062..113baabc41cd 100644
--- a/src/nix-env/Makefile.am
+++ b/src/nix-env/Makefile.am
@@ -4,7 +4,7 @@ nix_env_SOURCES = nix-env.cc profiles.cc profiles.hh user-env.cc user-env.hh hel
 
 nix_env_LDADD = ../libmain/libmain.la ../libexpr/libexpr.la \
  ../libstore/libstore.la ../libutil/libutil.la \
- ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@
+ ../boost/format/libformat.la
 
 nix-env.o: help.txt.hh
 
diff --git a/src/nix-env/nix-env.cc b/src/nix-env/nix-env.cc
index 12a256a091f9..ca67119e9b2b 100644
--- a/src/nix-env/nix-env.cc
+++ b/src/nix-env/nix-env.cc
@@ -69,7 +69,7 @@ typedef void (* Operation) (Globals & globals,
 
 void printHelp()
 {
-    cout << string((char *) helpText, sizeof helpText);
+    cout << string((char *) helpText);
 }
 
 
diff --git a/src/nix-hash/Makefile.am b/src/nix-hash/Makefile.am
index 5f84eb34d6da..a4fdb324629d 100644
--- a/src/nix-hash/Makefile.am
+++ b/src/nix-hash/Makefile.am
@@ -2,7 +2,7 @@ bin_PROGRAMS = nix-hash
 
 nix_hash_SOURCES = nix-hash.cc help.txt
 nix_hash_LDADD = ../libmain/libmain.la ../libstore/libstore.la ../libutil/libutil.la \
- ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@
+ ../boost/format/libformat.la
 
 nix-hash.o: help.txt.hh
 
diff --git a/src/nix-hash/nix-hash.cc b/src/nix-hash/nix-hash.cc
index 1282af070e62..a70f59e0c2d0 100644
--- a/src/nix-hash/nix-hash.cc
+++ b/src/nix-hash/nix-hash.cc
@@ -10,7 +10,7 @@ using namespace nix;
 
 void printHelp()
 {
-    std::cout << string((char *) helpText, sizeof helpText);
+    std::cout << string((char *) helpText);
 }
 
 
diff --git a/src/nix-instantiate/Makefile.am b/src/nix-instantiate/Makefile.am
index a65907a8d40a..b48dbd9d410f 100644
--- a/src/nix-instantiate/Makefile.am
+++ b/src/nix-instantiate/Makefile.am
@@ -3,7 +3,7 @@ bin_PROGRAMS = nix-instantiate
 nix_instantiate_SOURCES = nix-instantiate.cc help.txt
 nix_instantiate_LDADD = ../libmain/libmain.la ../libexpr/libexpr.la \
  ../libstore/libstore.la ../libutil/libutil.la \
- ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@
+ ../boost/format/libformat.la
 
 nix-instantiate.o: help.txt.hh
 
diff --git a/src/nix-instantiate/nix-instantiate.cc b/src/nix-instantiate/nix-instantiate.cc
index 4d629ea1b333..38c62880b88f 100644
--- a/src/nix-instantiate/nix-instantiate.cc
+++ b/src/nix-instantiate/nix-instantiate.cc
@@ -19,7 +19,7 @@ using namespace nix;
 
 void printHelp()
 {
-    std::cout << string((char *) helpText, sizeof helpText);
+    std::cout << string((char *) helpText);
 }
 
 
diff --git a/src/nix-log2xml/log2xml.cc b/src/nix-log2xml/log2xml.cc
index b2a25eefa269..6645dc500fed 100644
--- a/src/nix-log2xml/log2xml.cc
+++ b/src/nix-log2xml/log2xml.cc
@@ -18,6 +18,8 @@ struct Decoder
     int priority;
     bool ignoreLF;
     int lineNo, charNo;
+    bool warning;
+    bool error;
 
     Decoder()
     {
@@ -29,6 +31,8 @@ struct Decoder
         ignoreLF = false;
         lineNo = 1;
         charNo = 0;
+        warning = false;
+        error = false;
     }
 
     void pushChar(char c);
@@ -95,6 +99,12 @@ void Decoder::pushChar(char c)
                     case 'b':
                         ignoreLF = false;
                         break;
+                    case 'e':
+                        error = true;
+                        break;
+                    case 'w':
+                        warning = true;
+                        break;
                 }
             } else if (c >= '0' && c <= '9') {
                 int n = 0;
@@ -118,6 +128,8 @@ void Decoder::finishLine()
     string tag = inHeader ? "head" : "line";
     cout << "<" << tag;
     if (priority != 1) cout << " priority='" << priority << "'";
+    if (warning) cout << " warning='1'";
+    if (error) cout << " error='1'";
     cout << ">";
 
     for (unsigned int i = 0; i < line.size(); i++) {
@@ -158,6 +170,8 @@ void Decoder::finishLine()
     line = "";
     inHeader = false;
     priority = 1;
+    warning = false;
+    error = false;
 }
 
 
diff --git a/src/nix-setuid-helper/Makefile.am b/src/nix-setuid-helper/Makefile.am
index 35528458c5f6..a04701636d84 100644
--- a/src/nix-setuid-helper/Makefile.am
+++ b/src/nix-setuid-helper/Makefile.am
@@ -4,5 +4,4 @@ nix_setuid_helper_SOURCES = nix-setuid-helper.cc
 nix_setuid_helper_LDADD = ../libutil/libutil.la \
  ../boost/format/libformat.la
 
-AM_CXXFLAGS = \
- -I$(srcdir)/.. -I$(srcdir)/../libutil
+AM_CXXFLAGS = -I$(srcdir)/.. -I$(srcdir)/../libutil
diff --git a/src/nix-store/Makefile.am b/src/nix-store/Makefile.am
index b6dd37a6114a..44ff54674ade 100644
--- a/src/nix-store/Makefile.am
+++ b/src/nix-store/Makefile.am
@@ -5,7 +5,7 @@ nix_store_SOURCES =				\
   xmlgraph.cc xmlgraph.hh
 
 nix_store_LDADD = ../libmain/libmain.la ../libstore/libstore.la ../libutil/libutil.la \
- ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@
+ ../boost/format/libformat.la
 
 nix-store.o: help.txt.hh
 
diff --git a/src/nix-store/help.txt b/src/nix-store/help.txt
index 071934b2000f..342281b338c4 100644
--- a/src/nix-store/help.txt
+++ b/src/nix-store/help.txt
@@ -27,6 +27,9 @@ Operations:
   --verify: verify Nix structures
   --optimise: optimise the Nix store by hard-linking identical files
 
+  --query-failed-paths: list paths that failed to build (if enabled)
+  --clear-failed-paths: clear the failed status of the given paths
+
   --version: output version information
   --help: display help
 
diff --git a/src/nix-store/nix-store.cc b/src/nix-store/nix-store.cc
index e22ef7efcefb..b6ece30ce0b8 100644
--- a/src/nix-store/nix-store.cc
+++ b/src/nix-store/nix-store.cc
@@ -22,7 +22,7 @@ typedef void (* Operation) (Strings opFlags, Strings opArgs);
 
 void printHelp()
 {
-    cout << string((char *) helpText, sizeof helpText);
+    cout << string((char *) helpText);
 }
 
 
@@ -34,7 +34,7 @@ static bool indirectRoot = false;
 LocalStore & ensureLocalStore()
 {
     LocalStore * store2(dynamic_cast<LocalStore *>(store.get()));
-    if (!store2) throw Error("you don't have sufficient rights to use --verify");
+    if (!store2) throw Error("you don't have sufficient rights to use this command");
     return *store2;
 }
 
@@ -661,8 +661,7 @@ static void opOptimise(Strings opFlags, Strings opArgs)
 
     bool dryRun = false;
 
-    for (Strings::iterator i = opFlags.begin();
-         i != opFlags.end(); ++i)
+    foreach (Strings::iterator, i, opFlags)
         if (*i == "--dry-run") dryRun = true;
         else throw UsageError(format("unknown flag `%1%'") % *i);
 
@@ -677,6 +676,24 @@ static void opOptimise(Strings opFlags, Strings opArgs)
 }
 
 
+static void opQueryFailedPaths(Strings opFlags, Strings opArgs)
+{
+    if (!opArgs.empty() || !opFlags.empty())
+        throw UsageError("no arguments expected");
+    PathSet failed = store->queryFailedPaths();
+    foreach (PathSet::iterator, i, failed)
+        cout << format("%1%\n") % *i;
+}
+
+
+static void opClearFailedPaths(Strings opFlags, Strings opArgs)
+{
+    if (!opFlags.empty())
+        throw UsageError("no flags expected");
+    store->clearFailedPaths(PathSet(opArgs.begin(), opArgs.end()));
+}
+
+
 /* Scan the arguments; find the operation, set global flags, put all
    other flags in a list, and put all other arguments in another
    list. */
@@ -728,6 +745,10 @@ void run(Strings args)
             op = opVerify;
         else if (arg == "--optimise")
             op = opOptimise;
+        else if (arg == "--query-failed-paths")
+            op = opQueryFailedPaths;
+        else if (arg == "--clear-failed-paths")
+            op = opClearFailedPaths;
         else if (arg == "--add-root") {
             if (i == args.end())
                 throw UsageError("`--add-root requires an argument");
diff --git a/src/nix-worker/Makefile.am b/src/nix-worker/Makefile.am
index 50c8ae36d2e8..b6094a2a038c 100644
--- a/src/nix-worker/Makefile.am
+++ b/src/nix-worker/Makefile.am
@@ -2,7 +2,7 @@ bin_PROGRAMS = nix-worker
 
 nix_worker_SOURCES = nix-worker.cc help.txt
 nix_worker_LDADD = ../libmain/libmain.la ../libstore/libstore.la ../libutil/libutil.la \
- ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@
+ ../boost/format/libformat.la
 
 nix-worker.o: help.txt.hh
 
diff --git a/src/nix-worker/nix-worker.cc b/src/nix-worker/nix-worker.cc
index bd2209c6d756..d41877e881a0 100644
--- a/src/nix-worker/nix-worker.cc
+++ b/src/nix-worker/nix-worker.cc
@@ -313,14 +313,16 @@ static void performOp(unsigned int clientVersion,
     }
 
     case wopQueryReferences:
-    case wopQueryReferrers: {
+    case wopQueryReferrers:
+    case wopQueryDerivationOutputs: {
         Path path = readStorePath(from);
         startWork();
         PathSet paths;
         if (op == wopQueryReferences)
             store->queryReferences(path, paths);
-        else
+        else if (op == wopQueryReferrers)
             store->queryReferrers(path, paths);
+        else paths = store->queryDerivationOutputs(path);
         stopWork();
         writeStringSet(paths, to);
         break;
@@ -518,6 +520,31 @@ static void performOp(unsigned int clientVersion,
         break;
     }
             
+    case wopQueryValidPaths: {
+        startWork();
+        PathSet paths = store->queryValidPaths();
+        stopWork();
+        writeStringSet(paths, to);
+        break;
+    }
+
+    case wopQueryFailedPaths: {
+        startWork();
+        PathSet paths = store->queryFailedPaths();
+        stopWork();
+        writeStringSet(paths, to);
+        break;
+    }
+
+    case wopClearFailedPaths: {
+        PathSet paths = readStringSet(from);
+        startWork();
+        store->clearFailedPaths(paths);
+        stopWork();
+        writeInt(1, to);
+        break;
+    }
+
     default:
         throw Error(format("invalid operation %1%") % op);
     }
@@ -765,7 +792,7 @@ void run(Strings args)
 
 void printHelp()
 {
-    std::cout << string((char *) helpText, sizeof helpText);
+    std::cout << string((char *) helpText);
 }
 
 
diff --git a/substitute.mk b/substitute.mk
index 50d63ef5c73b..e99b1c615cf9 100644
--- a/substitute.mk
+++ b/substitute.mk
@@ -24,6 +24,7 @@
 	 -e "s^@xmllint\@^$(xmllint)^g" \
 	 -e "s^@xmlflags\@^$(xmlflags)^g" \
 	 -e "s^@xsltproc\@^$(xsltproc)^g" \
+	 -e "s^@sqlite_bin\@^$(sqlite_bin)^g" \
 	 -e "s^@version\@^$(VERSION)^g" \
 	 -e "s^@testPath\@^$(coreutils):$$(dirname $$(type -P expr))^g" \
 	 < $< > $@ || rm $@
diff --git a/tests/common.sh.in b/tests/common.sh.in
index b30bc44b5cc0..2c47d75eea23 100644
--- a/tests/common.sh.in
+++ b/tests/common.sh.in
@@ -38,6 +38,7 @@ export dot=@dot@
 export xmllint="@xmllint@"
 export xmlflags="@xmlflags@"
 export xsltproc="@xsltproc@"
+export sqlite3="@sqlite_bin@/bin/sqlite3"
 export SHELL="@shell@"
 
 export version=@version@
diff --git a/tests/init.sh b/tests/init.sh
index 0639a70662cd..64947031bfe7 100644
--- a/tests/init.sh
+++ b/tests/init.sh
@@ -40,6 +40,7 @@ cat > "$NIX_CONF_DIR"/nix.conf <<EOF
 gc-keep-outputs = false
 gc-keep-derivations = false
 env-keep-derivations = false
+fsync-metadata = false
 EOF
 
 mkdir $NIX_DATA_DIR/nix
@@ -96,7 +97,6 @@ mv $NIX_BIN_DIR/nix/download-using-manifests.pl $NIX_BIN_DIR/nix/substituters/do
 $nixstore --init
 
 # Did anything happen?
-test -e "$NIX_DB_DIR"/info
-test -e "$NIX_DB_DIR"/referrer
+test -e "$NIX_DB_DIR"/db.sqlite
 
 echo 'Hello World' > ./dummy
diff --git a/tests/referrers.sh b/tests/referrers.sh
index e3f8e07bc1bb..a0c195d5ab6c 100644
--- a/tests/referrers.sh
+++ b/tests/referrers.sh
@@ -1,9 +1,8 @@
 source common.sh
 
-# This takes way to long on Cygwin (because process creation is so slow...).
-if test "$system" = i686-cygwin; then exit 0; fi
+clearStore
 
-max=2500
+max=500
 
 reference=$NIX_STORE_DIR/abcdef
 touch $reference
@@ -13,46 +12,23 @@ echo "making registration..."
 
 for ((n = 0; n < $max; n++)); do
     storePath=$NIX_STORE_DIR/$n
-    touch $storePath
+    echo -n > $storePath
     ref2=$NIX_STORE_DIR/$((n+1))
     if test $((n+1)) = $max; then
         ref2=$reference
     fi
-    (echo $storePath && echo && echo 2 && echo $reference && echo $ref2)
+    echo $storePath; echo; echo 2; echo $reference; echo $ref2
 done > $TEST_ROOT/reg_info
 
 echo "registering..."
 
-time $nixstore --register-validity < $TEST_ROOT/reg_info
-
-oldTime=$(cat test-tmp/db/info/1 | grep Registered-At)
-
-echo "sleeping..."
-
-sleep 2
-
-echo "reregistering..."
-
-time $nixstore --register-validity --reregister < $TEST_ROOT/reg_info
-
-newTime=$(cat test-tmp/db/info/1 | grep Registered-At)
-
-if test "$newTime" != "$oldTime"; then
-    echo "reregistration changed original registration time"
-    exit 1
-fi
-
-if test "$(cat test-tmp/db/referrer/1 | wc -w)" -ne 1; then
-    echo "reregistration duplicated referrers"
-    exit 1
-fi
+$nixstore --register-validity < $TEST_ROOT/reg_info
 
 echo "collecting garbage..."
 ln -sfn $reference "$NIX_STATE_DIR"/gcroots/ref
-time $nixstore --gc
+$nixstore --gc
 
-if test "$(cat test-tmp/db/referrer/abcdef | wc -w)" -ne 0; then
+if test "$(sqlite3 ./test-tmp/db/db.sqlite 'select count(*) from Refs')" -ne 0; then
     echo "referrers not cleaned up"
     exit 1
 fi
-