about summary refs log tree commit diff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/libexpr/eval.cc2
-rw-r--r--src/libexpr/get-drvs.cc5
-rw-r--r--src/libexpr/parser.y13
-rw-r--r--src/libexpr/primops.cc8
-rw-r--r--src/libexpr/primops/fetchgit.cc82
-rw-r--r--src/libexpr/primops/fetchgit.hh14
-rw-r--r--src/libmain/common-args.cc9
-rw-r--r--src/libmain/shared.cc8
-rw-r--r--src/libstore/binary-cache-store.cc180
-rw-r--r--src/libstore/binary-cache-store.hh50
-rw-r--r--src/libstore/build.cc429
-rw-r--r--src/libstore/builtins.cc2
-rw-r--r--src/libstore/derivations.cc2
-rw-r--r--src/libstore/download.cc4
-rw-r--r--src/libstore/gc.cc10
-rw-r--r--src/libstore/globals.cc15
-rw-r--r--src/libstore/globals.hh30
-rw-r--r--src/libstore/http-binary-cache-store.cc27
-rw-r--r--src/libstore/local-binary-cache-store.cc49
-rw-r--r--src/libstore/local-store.cc330
-rw-r--r--src/libstore/local-store.hh39
-rw-r--r--src/libstore/local.mk2
-rw-r--r--src/libstore/misc.cc17
-rw-r--r--src/libstore/nar-info-disk-cache.cc224
-rw-r--r--src/libstore/nar-info-disk-cache.hh29
-rw-r--r--src/libstore/nar-info.cc20
-rw-r--r--src/libstore/nar-info.hh4
-rw-r--r--src/libstore/optimise-store.cc2
-rw-r--r--src/libstore/remote-store.cc92
-rw-r--r--src/libstore/remote-store.hh12
-rw-r--r--src/libstore/s3-binary-cache-store.cc253
-rw-r--r--src/libstore/s3-binary-cache-store.hh34
-rw-r--r--src/libstore/sqlite.cc5
-rw-r--r--src/libstore/sqlite.hh1
-rw-r--r--src/libstore/store-api.cc181
-rw-r--r--src/libstore/store-api.hh89
-rw-r--r--src/libstore/worker-protocol.hh8
-rw-r--r--src/libutil/args.cc7
-rw-r--r--src/libutil/args.hh3
-rw-r--r--src/libutil/compression.cc178
-rw-r--r--src/libutil/compression.hh7
-rw-r--r--src/libutil/finally.hh12
-rw-r--r--src/libutil/hash.cc32
-rw-r--r--src/libutil/hash.hh12
-rw-r--r--src/libutil/local.mk2
-rw-r--r--src/libutil/logging.cc79
-rw-r--r--src/libutil/logging.hh82
-rw-r--r--src/libutil/lru-cache.hh6
-rw-r--r--src/libutil/ref.hh6
-rw-r--r--src/libutil/thread-pool.cc130
-rw-r--r--src/libutil/thread-pool.hh73
-rw-r--r--src/libutil/types.hh10
-rw-r--r--src/libutil/util.cc131
-rw-r--r--src/libutil/util.hh56
-rw-r--r--src/nix-daemon/nix-daemon.cc91
-rw-r--r--src/nix-env/nix-env.cc2
-rw-r--r--src/nix-instantiate/nix-instantiate.cc2
-rw-r--r--src/nix-log2xml/local.mk5
-rw-r--r--src/nix-log2xml/log2xml.cc201
-rw-r--r--src/nix-log2xml/logfile.css86
-rw-r--r--src/nix-store/dotgraph.cc14
-rw-r--r--src/nix-store/nix-store.cc60
-rw-r--r--src/nix-store/xmlgraph.cc13
-rw-r--r--src/nix/command.cc15
-rw-r--r--src/nix/command.hh12
-rw-r--r--src/nix/copy.cc83
-rw-r--r--src/nix/main.cc5
-rw-r--r--src/nix/path-info.cc85
-rw-r--r--src/nix/progress-bar.cc185
-rw-r--r--src/nix/progress-bar.hh44
-rw-r--r--src/nix/sigs.cc84
-rw-r--r--src/nix/verify.cc77
72 files changed, 2381 insertions, 1790 deletions
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 7ad9a4e46d83..5a6428ca6b6f 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -641,7 +641,7 @@ void EvalState::evalFile(const Path & path, Value & v)
         return;
     }
 
-    startNest(nest, lvlTalkative, format("evaluating file ‘%1%’") % path2);
+    Activity act(*logger, lvlTalkative, format("evaluating file ‘%1%’") % path2);
     Expr * e = parseExprFromFile(checkSourcePath(path2));
     try {
         eval(e, v);
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index 4889fe206a31..b06c539de0fb 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -290,7 +290,7 @@ static void getDerivations(EvalState & state, Value & vIn,
             attrs.insert(std::pair<string, Symbol>(i.name, i.name));
 
         for (auto & i : attrs) {
-            startNest(nest, lvlDebug, format("evaluating attribute ‘%1%’") % i.first);
+            Activity act(*logger, lvlDebug, format("evaluating attribute ‘%1%’") % i.first);
             string pathPrefix2 = addToPath(pathPrefix, i.first);
             Value & v2(*v.attrs->find(i.second)->value);
             if (combineChannels)
@@ -310,8 +310,7 @@ static void getDerivations(EvalState & state, Value & vIn,
 
     else if (v.isList()) {
         for (unsigned int n = 0; n < v.listSize(); ++n) {
-            startNest(nest, lvlDebug,
-                format("evaluating list element"));
+            Activity act(*logger, lvlDebug, "evaluating list element");
             string pathPrefix2 = addToPath(pathPrefix, (format("%1%") % n).str());
             if (getDerivation(state, *v.listElems()[n], pathPrefix2, drvs, done, ignoreAssertionFailures))
                 getDerivations(state, *v.listElems()[n], pathPrefix2, autoArgs, drvs, done, ignoreAssertionFailures);
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index 20ae1a696097..776e5cb39b81 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -520,9 +520,10 @@ formal
 #include <fcntl.h>
 #include <unistd.h>
 
-#include <eval.hh>
-#include <download.hh>
-#include <store-api.hh>
+#include "eval.hh"
+#include "download.hh"
+#include "store-api.hh"
+#include "primops/fetchgit.hh"
 
 
 namespace nix {
@@ -657,7 +658,11 @@ std::pair<bool, std::string> EvalState::resolveSearchPathElem(const SearchPathEl
 
     if (isUri(elem.second)) {
         try {
-            res = { true, makeDownloader()->downloadCached(store, elem.second, true) };
+            if (hasPrefix(elem.second, "git://") || hasSuffix(elem.second, ".git"))
+                // FIXME: support specifying revision/branch
+                res = { true, exportGit(store, elem.second, "master") };
+            else
+                res = { true, makeDownloader()->downloadCached(store, elem.second, true) };
         } catch (DownloadError & e) {
             printMsg(lvlError, format("warning: Nix search path entry ‘%1%’ cannot be downloaded, ignoring") % elem.second);
             res = { false, "" };
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 51680ad62ee2..c2852629a015 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -124,7 +124,7 @@ static void prim_scopedImport(EvalState & state, const Pos & pos, Value * * args
                 env->values[displ++] = attr.value;
             }
 
-            startNest(nest, lvlTalkative, format("evaluating file ‘%1%’") % path);
+            Activity act(*logger, lvlTalkative, format("evaluating file ‘%1%’") % path);
             Expr * e = state.parseExprFromFile(resolveExprPath(path), staticEnv);
 
             e->eval(state, *env, v);
@@ -284,7 +284,7 @@ typedef list<Value *> ValueList;
 
 static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    startNest(nest, lvlDebug, "finding dependencies");
+    Activity act(*logger, lvlDebug, "finding dependencies");
 
     state.forceAttrs(*args[0], pos);
 
@@ -457,7 +457,7 @@ void prim_valueSize(EvalState & state, const Pos & pos, Value * * args, Value &
    derivation. */
 static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    startNest(nest, lvlVomit, "evaluating derivation");
+    Activity act(*logger, lvlVomit, "evaluating derivation");
 
     state.forceAttrs(*args[0], pos);
 
@@ -494,7 +494,7 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
     for (auto & i : *args[0]->attrs) {
         if (i.name == state.sIgnoreNulls) continue;
         string key = i.name;
-        startNest(nest, lvlVomit, format("processing attribute ‘%1%’") % key);
+        Activity act(*logger, lvlVomit, format("processing attribute ‘%1%’") % key);
 
         try {
 
diff --git a/src/libexpr/primops/fetchgit.cc b/src/libexpr/primops/fetchgit.cc
new file mode 100644
index 000000000000..bd440c8c62ad
--- /dev/null
+++ b/src/libexpr/primops/fetchgit.cc
@@ -0,0 +1,82 @@
+#include "primops.hh"
+#include "eval-inline.hh"
+#include "download.hh"
+#include "store-api.hh"
+
+namespace nix {
+
+Path exportGit(ref<Store> store, const std::string & uri, const std::string & rev)
+{
+    if (!isUri(uri))
+        throw EvalError(format("‘%s’ is not a valid URI") % uri);
+
+    Path cacheDir = getCacheDir() + "/nix/git";
+
+    if (!pathExists(cacheDir)) {
+        createDirs(cacheDir);
+        runProgram("git", true, { "init", "--bare", cacheDir });
+    }
+
+    Activity act(*logger, lvlInfo, format("fetching Git repository ‘%s’") % uri);
+
+    std::string localRef = "pid-" + std::to_string(getpid());
+    Path localRefFile = cacheDir + "/refs/heads/" + localRef;
+
+    runProgram("git", true, { "-C", cacheDir, "fetch", uri, rev + ":" + localRef });
+
+    std::string commitHash = chomp(readFile(localRefFile));
+
+    unlink(localRefFile.c_str());
+
+    debug(format("got revision ‘%s’") % commitHash);
+
+    // FIXME: should pipe this, or find some better way to extract a
+    // revision.
+    auto tar = runProgram("git", true, { "-C", cacheDir, "archive", commitHash });
+
+    Path tmpDir = createTempDir();
+    AutoDelete delTmpDir(tmpDir, true);
+
+    runProgram("tar", true, { "x", "-C", tmpDir }, tar);
+
+    return store->addToStore("git-export", tmpDir);
+}
+
+static void prim_fetchgit(EvalState & state, const Pos & pos, Value * * args, Value & v)
+{
+    // FIXME: cut&paste from fetch().
+    if (state.restricted) throw Error("‘fetchgit’ is not allowed in restricted mode");
+
+    std::string url;
+    std::string rev = "master";
+
+    state.forceValue(*args[0]);
+
+    if (args[0]->type == tAttrs) {
+
+        state.forceAttrs(*args[0], pos);
+
+        for (auto & attr : *args[0]->attrs) {
+            string name(attr.name);
+            if (name == "url")
+                url = state.forceStringNoCtx(*attr.value, *attr.pos);
+            else if (name == "rev")
+                rev = state.forceStringNoCtx(*attr.value, *attr.pos);
+            else
+                throw EvalError(format("unsupported argument ‘%1%’ to ‘fetchgit’, at %3%") % attr.name % attr.pos);
+        }
+
+        if (url.empty())
+            throw EvalError(format("‘url’ argument required, at %1%") % pos);
+
+    } else
+        url = state.forceStringNoCtx(*args[0], pos);
+
+    Path storePath = exportGit(state.store, url, rev);
+
+    mkString(v, storePath, PathSet({storePath}));
+}
+
+static RegisterPrimOp r("__fetchgit", 1, prim_fetchgit);
+
+}
diff --git a/src/libexpr/primops/fetchgit.hh b/src/libexpr/primops/fetchgit.hh
new file mode 100644
index 000000000000..6ffb21a96daa
--- /dev/null
+++ b/src/libexpr/primops/fetchgit.hh
@@ -0,0 +1,14 @@
+#pragma once
+
+#include <string>
+
+#include "ref.hh"
+
+namespace nix {
+
+class Store;
+
+Path exportGit(ref<Store> store,
+    const std::string & uri, const std::string & rev);
+
+}
diff --git a/src/libmain/common-args.cc b/src/libmain/common-args.cc
index 9219f380c74f..98693d78a7f4 100644
--- a/src/libmain/common-args.cc
+++ b/src/libmain/common-args.cc
@@ -18,15 +18,6 @@ MixCommonArgs::MixCommonArgs(const string & programName)
         verbosity = lvlDebug;
     });
 
-    mkFlag1(0, "log-type", "type", "set logging format ('pretty', 'flat', 'systemd')",
-        [](std::string s) {
-            if (s == "pretty") logType = ltPretty;
-            else if (s == "escapes") logType = ltEscapes;
-            else if (s == "flat") logType = ltFlat;
-            else if (s == "systemd") logType = ltSystemd;
-            else throw UsageError("unknown log type");
-        });
-
     mkFlag(0, "option", {"name", "value"}, "set a Nix configuration option (overriding nix.conf)", 2,
         [](Strings ss) {
             auto name = ss.front(); ss.pop_front();
diff --git a/src/libmain/shared.cc b/src/libmain/shared.cc
index ed997052be20..0b6311516ad4 100644
--- a/src/libmain/shared.cc
+++ b/src/libmain/shared.cc
@@ -111,8 +111,7 @@ void initNix()
     std::cerr.rdbuf()->pubsetbuf(buf, sizeof(buf));
 #endif
 
-    if (getEnv("IN_SYSTEMD") == "1")
-        logType = ltSystemd;
+    logger = makeDefaultLogger();
 
     /* Initialise OpenSSL locking. */
     opensslLocks = std::vector<std::mutex>(CRYPTO_num_locks());
@@ -172,10 +171,7 @@ struct LegacyArgs : public MixCommonArgs
         : MixCommonArgs(programName), parseArg(parseArg)
     {
         mkFlag('Q', "no-build-output", "do not show build output",
-            &settings.buildVerbosity, lvlVomit);
-
-        mkFlag(0, "print-build-trace", "emit special build trace message",
-            &settings.printBuildTrace);
+            &settings.verboseBuild, false);
 
         mkFlag('K', "keep-failed", "keep temporary directories of failed builds",
             &settings.keepFailed);
diff --git a/src/libstore/binary-cache-store.cc b/src/libstore/binary-cache-store.cc
index 7016eedfa701..411d10130a31 100644
--- a/src/libstore/binary-cache-store.cc
+++ b/src/libstore/binary-cache-store.cc
@@ -8,20 +8,20 @@
 #include "sync.hh"
 #include "worker-protocol.hh"
 #include "nar-accessor.hh"
+#include "nar-info-disk-cache.hh"
 
 #include <chrono>
 
 namespace nix {
 
 BinaryCacheStore::BinaryCacheStore(std::shared_ptr<Store> localStore,
-    const Path & secretKeyFile)
+    const StoreParams & params)
     : localStore(localStore)
+    , compression(get(params, "compression", "xz"))
 {
-    if (secretKeyFile != "") {
+    auto secretKeyFile = get(params, "secret-key", "");
+    if (secretKeyFile != "")
         secretKey = std::unique_ptr<SecretKey>(new SecretKey(readFile(secretKeyFile)));
-        publicKeys = std::unique_ptr<PublicKeys>(new PublicKeys);
-        publicKeys->emplace(secretKey->name, secretKey->toPublicKey());
-    }
 
     StringSink sink;
     sink << narVersionMagic1;
@@ -40,57 +40,65 @@ void BinaryCacheStore::notImpl()
     throw Error("operation not implemented for binary cache stores");
 }
 
-const BinaryCacheStore::Stats & BinaryCacheStore::getStats()
-{
-    return stats;
-}
-
 Path BinaryCacheStore::narInfoFileFor(const Path & storePath)
 {
     assertStorePath(storePath);
     return storePathToHash(storePath) + ".narinfo";
 }
 
-void BinaryCacheStore::addToCache(const ValidPathInfo & info,
-    const string & nar)
+void BinaryCacheStore::addToCache(const ValidPathInfo & info, ref<std::string> nar)
 {
+    /* Verify that all references are valid. This may do some .narinfo
+       reads, but typically they'll already be cached. */
+    for (auto & ref : info.references)
+        try {
+            if (ref != info.path)
+                queryPathInfo(ref);
+        } catch (InvalidPath &) {
+            throw Error(format("cannot add ‘%s’ to the binary cache because the reference ‘%s’ is not valid")
+                % info.path % ref);
+        }
+
     auto narInfoFile = narInfoFileFor(info.path);
     if (fileExists(narInfoFile)) return;
 
-    assert(nar.compare(0, narMagic.size(), narMagic) == 0);
+    assert(nar->compare(0, narMagic.size(), narMagic) == 0);
 
     auto narInfo = make_ref<NarInfo>(info);
 
-    narInfo->narSize = nar.size();
-    narInfo->narHash = hashString(htSHA256, nar);
+    narInfo->narSize = nar->size();
+    narInfo->narHash = hashString(htSHA256, *nar);
 
-    if (info.narHash.type != htUnknown && info.narHash != narInfo->narHash)
+    if (info.narHash && info.narHash != narInfo->narHash)
         throw Error(format("refusing to copy corrupted path ‘%1%’ to binary cache") % info.path);
 
     /* Compress the NAR. */
-    narInfo->compression = "xz";
+    narInfo->compression = compression;
     auto now1 = std::chrono::steady_clock::now();
-    string narXz = compressXZ(nar);
+    auto narCompressed = compress(compression, nar);
     auto now2 = std::chrono::steady_clock::now();
-    narInfo->fileHash = hashString(htSHA256, narXz);
-    narInfo->fileSize = narXz.size();
+    narInfo->fileHash = hashString(htSHA256, *narCompressed);
+    narInfo->fileSize = narCompressed->size();
 
     auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now2 - now1).count();
     printMsg(lvlTalkative, format("copying path ‘%1%’ (%2% bytes, compressed %3$.1f%% in %4% ms) to binary cache")
         % narInfo->path % narInfo->narSize
-        % ((1.0 - (double) narXz.size() / nar.size()) * 100.0)
+        % ((1.0 - (double) narCompressed->size() / nar->size()) * 100.0)
         % duration);
 
     /* Atomically write the NAR file. */
-    narInfo->url = "nar/" + printHash32(narInfo->fileHash) + ".nar.xz";
+    narInfo->url = "nar/" + printHash32(narInfo->fileHash) + ".nar"
+        + (compression == "xz" ? ".xz" :
+           compression == "bzip2" ? ".bz2" :
+           "");
     if (!fileExists(narInfo->url)) {
         stats.narWrite++;
-        upsertFile(narInfo->url, narXz);
+        upsertFile(narInfo->url, *narCompressed);
     } else
         stats.narWriteAverted++;
 
-    stats.narWriteBytes += nar.size();
-    stats.narWriteCompressedBytes += narXz.size();
+    stats.narWriteBytes += nar->size();
+    stats.narWriteCompressedBytes += narCompressed->size();
     stats.narWriteCompressionTimeMs += duration;
 
     /* Atomically write the NAR info file.*/
@@ -98,69 +106,21 @@ void BinaryCacheStore::addToCache(const ValidPathInfo & info,
 
     upsertFile(narInfoFile, narInfo->to_string());
 
-    {
-        auto state_(state.lock());
-        state_->narInfoCache.upsert(narInfo->path, narInfo);
-        stats.narInfoCacheSize = state_->narInfoCache.size();
-    }
+    auto hashPart = storePathToHash(narInfo->path);
 
-    stats.narInfoWrite++;
-}
-
-NarInfo BinaryCacheStore::readNarInfo(const Path & storePath)
-{
     {
         auto state_(state.lock());
-        auto res = state_->narInfoCache.get(storePath);
-        if (res) {
-            stats.narInfoReadAverted++;
-            if (!*res)
-                throw InvalidPath(format("path ‘%s’ is not valid") % storePath);
-            return **res;
-        }
-    }
-
-    auto narInfoFile = narInfoFileFor(storePath);
-    auto data = getFile(narInfoFile);
-    if (!data) {
-        stats.narInfoMissing++;
-        auto state_(state.lock());
-        state_->narInfoCache.upsert(storePath, 0);
-        stats.narInfoCacheSize = state_->narInfoCache.size();
-        throw InvalidPath(format("path ‘%s’ is not valid") % storePath);
-    }
-
-    auto narInfo = make_ref<NarInfo>(*data, narInfoFile);
-    if (narInfo->path != storePath)
-        throw Error(format("NAR info file for store path ‘%1%’ does not match ‘%2%’") % narInfo->path % storePath);
-
-    stats.narInfoRead++;
-
-    if (publicKeys) {
-        if (!narInfo->checkSignatures(*publicKeys))
-            throw Error(format("no good signature on NAR info file ‘%1%’") % narInfoFile);
+        state_->pathInfoCache.upsert(hashPart, std::shared_ptr<NarInfo>(narInfo));
     }
 
-    {
-        auto state_(state.lock());
-        state_->narInfoCache.upsert(storePath, narInfo);
-        stats.narInfoCacheSize = state_->narInfoCache.size();
-    }
+    if (diskCache)
+        diskCache->upsertNarInfo(getUri(), hashPart, std::shared_ptr<NarInfo>(narInfo));
 
-    return *narInfo;
+    stats.narInfoWrite++;
 }
 
-bool BinaryCacheStore::isValidPath(const Path & storePath)
+bool BinaryCacheStore::isValidPathUncached(const Path & storePath)
 {
-    {
-        auto state_(state.lock());
-        auto res = state_->narInfoCache.get(storePath);
-        if (res) {
-            stats.narInfoReadAverted++;
-            return *res != 0;
-        }
-    }
-
     // FIXME: this only checks whether a .narinfo with a matching hash
     // part exists. So ‘f4kb...-foo’ matches ‘f4kb...-bar’, even
     // though they shouldn't. Not easily fixed.
@@ -169,23 +129,23 @@ bool BinaryCacheStore::isValidPath(const Path & storePath)
 
 void BinaryCacheStore::narFromPath(const Path & storePath, Sink & sink)
 {
-    auto res = readNarInfo(storePath);
+    auto info = queryPathInfo(storePath).cast<const NarInfo>();
 
-    auto nar = getFile(res.url);
+    auto nar = getFile(info->url);
 
-    if (!nar) throw Error(format("file ‘%s’ missing from binary cache") % res.url);
+    if (!nar) throw Error(format("file ‘%s’ missing from binary cache") % info->url);
 
     stats.narRead++;
     stats.narReadCompressedBytes += nar->size();
 
     /* Decompress the NAR. FIXME: would be nice to have the remote
        side do this. */
-    if (res.compression == "none")
-        ;
-    else if (res.compression == "xz")
-        nar = decompressXZ(*nar);
-    else
-        throw Error(format("unknown NAR compression type ‘%1%’") % nar);
+    try {
+        nar = decompress(info->compression, ref<std::string>(nar));
+    } catch (UnknownCompressionMethod &) {
+        throw Error(format("binary cache path ‘%s’ uses unknown compression method ‘%s’")
+            % storePath % info->compression);
+    }
 
     stats.narReadBytes += nar->size();
 
@@ -200,13 +160,13 @@ void BinaryCacheStore::exportPath(const Path & storePath, bool sign, Sink & sink
 {
     assert(!sign);
 
-    auto res = readNarInfo(storePath);
+    auto res = queryPathInfo(storePath);
 
     narFromPath(storePath, sink);
 
     // FIXME: check integrity of NAR.
 
-    sink << exportMagic << storePath << res.references << res.deriver << 0;
+    sink << exportMagic << storePath << res->references << res->deriver << 0;
 }
 
 Paths BinaryCacheStore::importPaths(bool requireSignature, Source & source,
@@ -244,9 +204,17 @@ struct NopSink : ParseSink
 {
 };
 
-ValidPathInfo BinaryCacheStore::queryPathInfo(const Path & storePath)
+std::shared_ptr<ValidPathInfo> BinaryCacheStore::queryPathInfoUncached(const Path & storePath)
 {
-    return ValidPathInfo(readNarInfo(storePath));
+    auto narInfoFile = narInfoFileFor(storePath);
+    auto data = getFile(narInfoFile);
+    if (!data) return 0;
+
+    auto narInfo = make_ref<NarInfo>(*data, narInfoFile);
+
+    stats.narInfoRead++;
+
+    return std::shared_ptr<NarInfo>(narInfo);
 }
 
 void BinaryCacheStore::querySubstitutablePathInfos(const PathSet & paths,
@@ -257,16 +225,16 @@ void BinaryCacheStore::querySubstitutablePathInfos(const PathSet & paths,
     if (!localStore) return;
 
     for (auto & storePath : paths) {
-        if (!localStore->isValidPath(storePath)) {
+        try {
+            auto info = localStore->queryPathInfo(storePath);
+            SubstitutablePathInfo sub;
+            sub.references = info->references;
+            sub.downloadSize = 0;
+            sub.narSize = info->narSize;
+            infos.emplace(storePath, sub);
+        } catch (InvalidPath &) {
             left.insert(storePath);
-            continue;
         }
-        ValidPathInfo info = localStore->queryPathInfo(storePath);
-        SubstitutablePathInfo sub;
-        sub.references = info.references;
-        sub.downloadSize = 0;
-        sub.narSize = info.narSize;
-        infos.emplace(storePath, sub);
     }
 
     if (settings.useSubstitutes)
@@ -296,7 +264,7 @@ Path BinaryCacheStore::addToStore(const string & name, const Path & srcPath,
     info.path = makeFixedOutputPath(recursive, hashAlgo, h, name);
 
     if (repair || !isValidPath(info.path))
-        addToCache(info, *sink.s);
+        addToCache(info, sink.s);
 
     return info.path;
 }
@@ -311,7 +279,7 @@ Path BinaryCacheStore::addTextToStore(const string & name, const string & s,
     if (repair || !isValidPath(info.path)) {
         StringSink sink;
         dumpString(s, sink);
-        addToCache(info, *sink.s);
+        addToCache(info, sink.s);
     }
 
     return info.path;
@@ -332,16 +300,16 @@ void BinaryCacheStore::buildPaths(const PathSet & paths, BuildMode buildMode)
         if (!localStore->isValidPath(storePath))
             localStore->ensurePath(storePath);
 
-        ValidPathInfo info = localStore->queryPathInfo(storePath);
+        auto info = localStore->queryPathInfo(storePath);
 
-        for (auto & ref : info.references)
+        for (auto & ref : info->references)
             if (ref != storePath)
                 ensurePath(ref);
 
         StringSink sink;
         dumpPath(storePath, sink);
 
-        addToCache(info, *sink.s);
+        addToCache(*info, sink.s);
     }
 }
 
@@ -439,7 +407,7 @@ Path BinaryCacheStore::importPath(Source & source, std::shared_ptr<FSAccessor> a
     bool haveSignature = readInt(source) == 1;
     assert(!haveSignature);
 
-    addToCache(info, *tee.data);
+    addToCache(info, tee.data);
 
     auto accessor_ = std::dynamic_pointer_cast<BinaryCacheStoreAccessor>(accessor);
     if (accessor_)
diff --git a/src/libstore/binary-cache-store.hh b/src/libstore/binary-cache-store.hh
index 95e5d68b70ae..46a38a1e0fc3 100644
--- a/src/libstore/binary-cache-store.hh
+++ b/src/libstore/binary-cache-store.hh
@@ -3,8 +3,6 @@
 #include "crypto.hh"
 #include "store-api.hh"
 
-#include "lru-cache.hh"
-#include "sync.hh"
 #include "pool.hh"
 
 #include <atomic>
@@ -18,20 +16,15 @@ class BinaryCacheStore : public Store
 private:
 
     std::unique_ptr<SecretKey> secretKey;
-    std::unique_ptr<PublicKeys> publicKeys;
 
     std::shared_ptr<Store> localStore;
 
-    struct State
-    {
-        LRUCache<Path, std::shared_ptr<NarInfo>> narInfoCache{64 * 1024};
-    };
-
-    Sync<State> state;
+    std::string compression;
 
 protected:
 
-    BinaryCacheStore(std::shared_ptr<Store> localStore, const Path & secretKeyFile);
+    BinaryCacheStore(std::shared_ptr<Store> localStore,
+        const StoreParams & params);
 
     [[noreturn]] void notImpl();
 
@@ -47,42 +40,17 @@ public:
 
     virtual void init();
 
-    struct Stats
-    {
-        std::atomic<uint64_t> narInfoRead{0};
-        std::atomic<uint64_t> narInfoReadAverted{0};
-        std::atomic<uint64_t> narInfoMissing{0};
-        std::atomic<uint64_t> narInfoWrite{0};
-        std::atomic<uint64_t> narInfoCacheSize{0};
-        std::atomic<uint64_t> narRead{0};
-        std::atomic<uint64_t> narReadBytes{0};
-        std::atomic<uint64_t> narReadCompressedBytes{0};
-        std::atomic<uint64_t> narWrite{0};
-        std::atomic<uint64_t> narWriteAverted{0};
-        std::atomic<uint64_t> narWriteBytes{0};
-        std::atomic<uint64_t> narWriteCompressedBytes{0};
-        std::atomic<uint64_t> narWriteCompressionTimeMs{0};
-    };
-
-    const Stats & getStats();
-
 private:
 
-    Stats stats;
-
     std::string narMagic;
 
     std::string narInfoFileFor(const Path & storePath);
 
-    void addToCache(const ValidPathInfo & info, const string & nar);
-
-protected:
-
-    NarInfo readNarInfo(const Path & storePath);
+    void addToCache(const ValidPathInfo & info, ref<std::string> nar);
 
 public:
 
-    bool isValidPath(const Path & path) override;
+    bool isValidPathUncached(const Path & path) override;
 
     PathSet queryValidPaths(const PathSet & paths) override
     { notImpl(); }
@@ -90,18 +58,12 @@ public:
     PathSet queryAllValidPaths() override
     { notImpl(); }
 
-    ValidPathInfo queryPathInfo(const Path & path) override;
-
-    Hash queryPathHash(const Path & path) override
-    { notImpl(); }
+    std::shared_ptr<ValidPathInfo> queryPathInfoUncached(const Path & path) override;
 
     void queryReferrers(const Path & path,
         PathSet & referrers) override
     { notImpl(); }
 
-    Path queryDeriver(const Path & path) override
-    { return ""; }
-
     PathSet queryValidDerivers(const Path & path) override
     { return {}; }
 
diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index ba3f3a371d8c..65df2eea59a0 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -8,11 +8,14 @@
 #include "archive.hh"
 #include "affinity.hh"
 #include "builtins.hh"
+#include "finally.hh"
 
 #include <algorithm>
 #include <iostream>
 #include <map>
 #include <sstream>
+#include <thread>
+#include <future>
 
 #include <limits.h>
 #include <time.h>
@@ -199,8 +202,6 @@ struct Child
     time_t timeStarted;
 };
 
-typedef map<pid_t, Child> Children;
-
 
 /* The worker class. */
 class Worker
@@ -220,7 +221,7 @@ private:
     WeakGoals wantingToBuild;
 
     /* Child processes currently running. */
-    Children children;
+    std::list<Child> children;
 
     /* Number of build slots occupied.  This includes local builds and
        substitutions but not remote builds via the build hook. */
@@ -278,14 +279,14 @@ public:
 
     /* Registers a running child process.  `inBuildSlot' means that
        the process counts towards the jobs limit. */
-    void childStarted(GoalPtr goal, pid_t pid,
-        const set<int> & fds, bool inBuildSlot, bool respectTimeouts);
+    void childStarted(GoalPtr goal, const set<int> & fds,
+        bool inBuildSlot, bool respectTimeouts);
 
     /* Unregisters a running child process.  `wakeSleepers' should be
        false if there is no sense in waking up goals that are sleeping
        because they can't run yet (e.g., there is no free build slot,
        or the hook would still say `postpone'). */
-    void childTerminated(pid_t pid, bool wakeSleepers = true);
+    void childTerminated(GoalPtr goal, bool wakeSleepers = true);
 
     /* Put `goal' to sleep until a build slot becomes available (which
        might be right away). */
@@ -633,7 +634,6 @@ HookInstance::HookInstance()
             baseNameOf(buildHook),
             settings.thisSystem,
             (format("%1%") % settings.maxSilentTime).str(),
-            (format("%1%") % settings.printBuildTrace).str(),
             (format("%1%") % settings.buildTimeout).str()
         };
 
@@ -748,6 +748,12 @@ private:
     /* Number of bytes received from the builder's stdout/stderr. */
     unsigned long logSize;
 
+    /* The most recent log lines. */
+    std::list<std::string> logTail;
+
+    std::string currentLogLine;
+    size_t currentLogLinePos = 0; // to handle carriage return
+
     /* Pipe for the builder's standard output/error. */
     Pipe builderOut;
 
@@ -873,6 +879,7 @@ private:
     /* Callback used by the worker to write to the log. */
     void handleChildOutput(int fd, const string & data) override;
     void handleEOF(int fd) override;
+    void flushLine();
 
     /* Return the set of (in)valid paths. */
     PathSet checkPathValidity(bool returnValid, bool checkHash);
@@ -936,7 +943,7 @@ DerivationGoal::~DerivationGoal()
 void DerivationGoal::killChild()
 {
     if (pid != -1) {
-        worker.childTerminated(pid);
+        worker.childTerminated(shared_from_this());
 
         if (buildUser.enabled()) {
             /* If we're using a build user, then there is a tricky
@@ -960,8 +967,6 @@ void DerivationGoal::killChild()
 
 void DerivationGoal::timedOut()
 {
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ build-failed %1% - timeout") % drvPath);
     killChild();
     done(BuildResult::TimedOut);
 }
@@ -1362,9 +1367,6 @@ void DerivationGoal::tryToBuild()
         printMsg(lvlError, e.msg());
         outputLocks.unlock();
         buildUser.release();
-        if (settings.printBuildTrace)
-            printMsg(lvlError, format("@ build-failed %1% - %2% %3%")
-                % drvPath % 0 % e.msg());
         worker.permanentFailure = true;
         done(BuildResult::InputRejected, e.msg());
         return;
@@ -1402,22 +1404,14 @@ void DerivationGoal::buildDone()
        to have terminated.  In fact, the builder could also have
        simply have closed its end of the pipe --- just don't do that
        :-) */
-    int status;
-    pid_t savedPid;
-    if (hook) {
-        savedPid = hook->pid;
-        status = hook->pid.wait(true);
-    } else {
-        /* !!! this could block! security problem! solution: kill the
-           child */
-        savedPid = pid;
-        status = pid.wait(true);
-    }
+    /* !!! this could block! security problem! solution: kill the
+       child */
+    int status = hook ? hook->pid.wait(true) : pid.wait(true);
 
     debug(format("builder process for ‘%1%’ finished") % drvPath);
 
     /* So the child is gone now. */
-    worker.childTerminated(savedPid);
+    worker.childTerminated(shared_from_this());
 
     /* Close the read side of the logger pipe. */
     if (hook) {
@@ -1468,11 +1462,19 @@ void DerivationGoal::buildDone()
                     if (pathExists(chrootRootDir + i))
                         rename((chrootRootDir + i).c_str(), i.c_str());
 
+            std::string msg = (format("builder for ‘%1%’ %2%")
+                % drvPath % statusToString(status)).str();
+
+            if (!settings.verboseBuild && !logTail.empty()) {
+                msg += (format("; last %d log lines:") % logTail.size()).str();
+                for (auto & line : logTail)
+                    msg += "\n  " + line;
+            }
+
             if (diskFull)
-                printMsg(lvlError, "note: build failure may have been caused by lack of free disk space");
+                msg += "\nnote: build failure may have been caused by lack of free disk space";
 
-            throw BuildError(format("builder for ‘%1%’ %2%")
-                % drvPath % statusToString(status));
+            throw BuildError(msg);
         }
 
         /* Compute the FS closure of the outputs and register them as
@@ -1517,23 +1519,13 @@ void DerivationGoal::buildDone()
 
         BuildResult::Status st = BuildResult::MiscFailure;
 
-        if (hook && WIFEXITED(status) && WEXITSTATUS(status) == 101) {
-            if (settings.printBuildTrace)
-                printMsg(lvlError, format("@ build-failed %1% - timeout") % drvPath);
+        if (hook && WIFEXITED(status) && WEXITSTATUS(status) == 101)
             st = BuildResult::TimedOut;
-        }
 
         else if (hook && (!WIFEXITED(status) || WEXITSTATUS(status) != 100)) {
-            if (settings.printBuildTrace)
-                printMsg(lvlError, format("@ hook-failed %1% - %2% %3%")
-                    % drvPath % status % e.msg());
         }
 
         else {
-            if (settings.printBuildTrace)
-                printMsg(lvlError, format("@ build-failed %1% - %2% %3%")
-                    % drvPath % 1 % e.msg());
-
             st =
                 dynamic_cast<NotDeterministic*>(&e) ? BuildResult::NotDeterministic :
                 statusOk(status) ? BuildResult::OutputRejected :
@@ -1548,9 +1540,6 @@ void DerivationGoal::buildDone()
     /* Release the build user, if applicable. */
     buildUser.release();
 
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ build-succeeded %1% -") % drvPath);
-
     done(BuildResult::Built);
 }
 
@@ -1625,11 +1614,7 @@ HookReply DerivationGoal::tryBuildHook()
     set<int> fds;
     fds.insert(hook->fromHook.readSide);
     fds.insert(hook->builderOut.readSide);
-    worker.childStarted(shared_from_this(), hook->pid, fds, false, false);
-
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ build-started %1% - %2% %3%")
-            % drvPath % drv->platform % logFile);
+    worker.childStarted(shared_from_this(), fds, false, false);
 
     return rpAccept;
 }
@@ -1657,12 +1642,10 @@ void DerivationGoal::startBuilder()
         nrRounds > 1 ? "building path(s) %1% (round %2%/%3%)" :
         "building path(s) %1%");
     f.exceptions(boost::io::all_error_bits ^ boost::io::too_many_args_bit);
-    startNest(nest, lvlInfo, f % showPaths(missingPaths) % curRound % nrRounds);
+    printMsg(lvlInfo, f % showPaths(missingPaths) % curRound % nrRounds);
 
     /* Right platform? */
     if (!drv->canBuildLocally()) {
-        if (settings.printBuildTrace)
-            printMsg(lvlError, format("@ unsupported-platform %1% %2%") % drvPath % drv->platform);
         throw Error(
             format("a ‘%1%’ is required to build ‘%3%’, but I am a ‘%2%’")
             % drv->platform % settings.thisSystem % drvPath);
@@ -2165,7 +2148,7 @@ void DerivationGoal::startBuilder()
     /* parent */
     pid.setSeparatePG(true);
     builderOut.writeSide.close();
-    worker.childStarted(shared_from_this(), pid,
+    worker.childStarted(shared_from_this(),
         singleton<set<int> >(builderOut.readSide), true, true);
 
     /* Check if setting up the build environment failed. */
@@ -2177,11 +2160,6 @@ void DerivationGoal::startBuilder()
         }
         printMsg(lvlDebug, msg);
     }
-
-    if (settings.printBuildTrace) {
-        printMsg(lvlError, format("@ build-started %1% - %2% %3%")
-            % drvPath % drv->platform % logFile);
-    }
 }
 
 
@@ -2192,8 +2170,6 @@ void DerivationGoal::runChild()
 
     try { /* child */
 
-        logType = ltFlat;
-
         commonChildInit(builderOut);
 
 #if __linux__
@@ -2535,7 +2511,6 @@ void DerivationGoal::runChild()
         /* Execute the program.  This should not return. */
         if (drv->isBuiltin()) {
             try {
-                logType = ltFlat;
                 if (drv->builder == "builtin:fetchurl")
                     builtinFetchurl(*drv);
                 else
@@ -2667,8 +2642,7 @@ void DerivationGoal::registerOutputs()
             rewritten = true;
         }
 
-        startNest(nest, lvlTalkative,
-            format("scanning for references inside ‘%1%’") % path);
+        Activity act(*logger, lvlTalkative, format("scanning for references inside ‘%1%’") % path);
 
         /* Check that fixed-output derivations produced the right
            outputs (i.e., the content hash should match the specified
@@ -2724,7 +2698,7 @@ void DerivationGoal::registerOutputs()
 
         if (buildMode == bmCheck) {
             if (!worker.store.isValidPath(path)) continue;
-            ValidPathInfo info = worker.store.queryPathInfo(path);
+            auto info = *worker.store.queryPathInfo(path);
             if (hash.first != info.narHash) {
                 if (settings.keepFailed) {
                     Path dst = path + checkSuffix;
@@ -2775,14 +2749,25 @@ void DerivationGoal::registerOutputs()
             } else
                 used = references;
 
+            PathSet badPaths;
+
             for (auto & i : used)
                 if (allowed) {
                     if (spec.find(i) == spec.end())
-                        throw BuildError(format("output ‘%1%’ is not allowed to refer to path ‘%2%’") % actualPath % i);
+                        badPaths.insert(i);
                 } else {
                     if (spec.find(i) != spec.end())
-                        throw BuildError(format("output ‘%1%’ is not allowed to refer to path ‘%2%’") % actualPath % i);
+                        badPaths.insert(i);
                 }
+
+            if (!badPaths.empty()) {
+                string badPathsStr;
+                for (auto & i : badPaths) {
+                    badPathsStr += "\n\t";
+                    badPathsStr += i;
+                }
+                throw BuildError(format("output ‘%1%’ is not allowed to refer to the following paths:%2%") % actualPath % badPathsStr);
+            }
         };
 
         checkRefs("allowedReferences", true, false);
@@ -2943,8 +2928,18 @@ void DerivationGoal::handleChildOutput(int fd, const string & data)
             done(BuildResult::LogLimitExceeded);
             return;
         }
-        if (verbosity >= settings.buildVerbosity)
-            writeToStderr(filterANSIEscapes(data, true));
+
+        for (auto c : data)
+            if (c == '\r')
+                currentLogLinePos = 0;
+            else if (c == '\n')
+                flushLine();
+            else {
+                if (currentLogLinePos >= currentLogLine.size())
+                    currentLogLine.resize(currentLogLinePos + 1);
+                currentLogLine[currentLogLinePos++] = c;
+            }
+
         if (bzLogFile) {
             int err;
             BZ2_bzWrite(&err, bzLogFile, (unsigned char *) data.data(), data.size());
@@ -2954,16 +2949,30 @@ void DerivationGoal::handleChildOutput(int fd, const string & data)
     }
 
     if (hook && fd == hook->fromHook.readSide)
-        writeToStderr(data);
+        printMsg(lvlError, data); // FIXME?
 }
 
 
 void DerivationGoal::handleEOF(int fd)
 {
+    if (!currentLogLine.empty()) flushLine();
     worker.wakeUp(shared_from_this());
 }
 
 
+void DerivationGoal::flushLine()
+{
+    if (settings.verboseBuild)
+        printMsg(lvlInfo, filterANSIEscapes(currentLogLine, true));
+    else {
+        logTail.push_back(currentLogLine);
+        if (logTail.size() > settings.logLines) logTail.pop_front();
+    }
+    currentLogLine = "";
+    currentLogLinePos = 0;
+}
+
+
 PathSet DerivationGoal::checkPathValidity(bool returnValid, bool checkHash)
 {
     PathSet result;
@@ -3016,28 +3025,24 @@ private:
     Path storePath;
 
     /* The remaining substituters. */
-    Paths subs;
+    std::list<ref<Store>> subs;
 
     /* The current substituter. */
-    Path sub;
+    std::shared_ptr<Store> sub;
 
-    /* Whether any substituter can realise this path */
+    /* Whether any substituter can realise this path. */
     bool hasSubstitute;
 
     /* Path info returned by the substituter's query info operation. */
-    SubstitutablePathInfo info;
+    std::shared_ptr<const ValidPathInfo> info;
 
     /* Pipe for the substituter's standard output. */
     Pipe outPipe;
 
-    /* Pipe for the substituter's standard error. */
-    Pipe logPipe;
-
-    /* The process ID of the builder. */
-    Pid pid;
+    /* The substituter thread. */
+    std::thread thr;
 
-    /* Lock on the store path. */
-    std::shared_ptr<PathLocks> outputLock;
+    std::promise<void> promise;
 
     /* Whether to try to repair a valid path. */
     bool repair;
@@ -3053,7 +3058,7 @@ public:
     SubstitutionGoal(const Path & storePath, Worker & worker, bool repair = false);
     ~SubstitutionGoal();
 
-    void timedOut();
+    void timedOut() { abort(); };
 
     string key()
     {
@@ -3094,20 +3099,14 @@ SubstitutionGoal::SubstitutionGoal(const Path & storePath, Worker & worker, bool
 
 SubstitutionGoal::~SubstitutionGoal()
 {
-    if (pid != -1) worker.childTerminated(pid);
-}
-
-
-void SubstitutionGoal::timedOut()
-{
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ substituter-failed %1% timeout") % storePath);
-    if (pid != -1) {
-        pid_t savedPid = pid;
-        pid.kill();
-        worker.childTerminated(savedPid);
+    try {
+        if (thr.joinable()) {
+            thr.join();
+            worker.childTerminated(shared_from_this());
+        }
+    } catch (...) {
+        ignoreException();
     }
-    amDone(ecFailed);
 }
 
 
@@ -3132,7 +3131,7 @@ void SubstitutionGoal::init()
     if (settings.readOnlyMode)
         throw Error(format("cannot substitute path ‘%1%’ - no write access to the Nix store") % storePath);
 
-    subs = settings.substituters;
+    subs = getDefaultSubstituters();
 
     tryNext();
 }
@@ -3157,17 +3156,19 @@ void SubstitutionGoal::tryNext()
     sub = subs.front();
     subs.pop_front();
 
-    SubstitutablePathInfos infos;
-    PathSet dummy(singleton<PathSet>(storePath));
-    worker.store.querySubstitutablePathInfos(sub, dummy, infos);
-    SubstitutablePathInfos::iterator k = infos.find(storePath);
-    if (k == infos.end()) { tryNext(); return; }
-    info = k->second;
+    try {
+        // FIXME: make async
+        info = sub->queryPathInfo(storePath);
+    } catch (InvalidPath &) {
+        tryNext();
+        return;
+    }
+
     hasSubstitute = true;
 
     /* To maintain the closure invariant, we first have to realise the
        paths referenced by this one. */
-    for (auto & i : info.references)
+    for (auto & i : info->references)
         if (i != storePath) /* ignore self-references */
             addWaitee(worker.makeSubstitutionGoal(i));
 
@@ -3188,7 +3189,7 @@ void SubstitutionGoal::referencesValid()
         return;
     }
 
-    for (auto & i : info.references)
+    for (auto & i : info->references)
         if (i != storePath) /* ignore self-references */
             assert(worker.store.isValidPath(i));
 
@@ -3210,75 +3211,32 @@ void SubstitutionGoal::tryToRun()
         return;
     }
 
-    /* Maybe a derivation goal has already locked this path
-       (exceedingly unlikely, since it should have used a substitute
-       first, but let's be defensive). */
-    outputLock.reset(); // make sure this goal's lock is gone
-    if (pathIsLockedByMe(storePath)) {
-        debug(format("restarting substitution of ‘%1%’ because it's locked by another goal")
-            % storePath);
-        worker.waitForAnyGoal(shared_from_this());
-        return; /* restart in the tryToRun() state when another goal finishes */
-    }
-
-    /* Acquire a lock on the output path. */
-    outputLock = std::make_shared<PathLocks>();
-    if (!outputLock->lockPaths(singleton<PathSet>(storePath), "", false)) {
-        worker.waitForAWhile(shared_from_this());
-        return;
-    }
-
-    /* Check again whether the path is invalid. */
-    if (!repair && worker.store.isValidPath(storePath)) {
-        debug(format("store path ‘%1%’ has become valid") % storePath);
-        outputLock->setDeletion(true);
-        amDone(ecSuccess);
-        return;
-    }
-
     printMsg(lvlInfo, format("fetching path ‘%1%’...") % storePath);
 
     outPipe.create();
-    logPipe.create();
-
-    destPath = repair ? storePath + ".tmp" : storePath;
 
-    /* Remove the (stale) output path if it exists. */
-    deletePath(destPath);
+    promise = std::promise<void>();
 
-    worker.store.setSubstituterEnv();
+    thr = std::thread([this]() {
+        try {
+            /* Wake up the worker loop when we're done. */
+            Finally updateStats([this]() { outPipe.writeSide.close(); });
 
-    /* Fill in the arguments. */
-    Strings args;
-    args.push_back(baseNameOf(sub));
-    args.push_back("--substitute");
-    args.push_back(storePath);
-    args.push_back(destPath);
-
-    /* Fork the substitute program. */
-    pid = startProcess([&]() {
-
-        commonChildInit(logPipe);
-
-        if (dup2(outPipe.writeSide, STDOUT_FILENO) == -1)
-            throw SysError("cannot dup output pipe into stdout");
+            StringSink sink;
+            sub->exportPaths({storePath}, false, sink);
 
-        execv(sub.c_str(), stringsToCharPtrs(args).data());
+            StringSource source(*sink.s);
+            worker.store.importPaths(false, source, 0);
 
-        throw SysError(format("executing ‘%1%’") % sub);
+            promise.set_value();
+        } catch (...) {
+            promise.set_exception(std::current_exception());
+        }
     });
 
-    pid.setSeparatePG(true);
-    pid.setKillSignal(SIGTERM);
-    outPipe.writeSide.close();
-    logPipe.writeSide.close();
-    worker.childStarted(shared_from_this(),
-        pid, singleton<set<int> >(logPipe.readSide), true, true);
+    worker.childStarted(shared_from_this(), {outPipe.readSide}, true, false);
 
     state = &SubstitutionGoal::finished;
-
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ substituter-started %1% %2%") % storePath % sub);
 }
 
 
@@ -3286,110 +3244,40 @@ void SubstitutionGoal::finished()
 {
     trace("substitute finished");
 
-    /* Since we got an EOF on the logger pipe, the substitute is
-       presumed to have terminated.  */
-    pid_t savedPid = pid;
-    int status = pid.wait(true);
-
-    /* So the child is gone now. */
-    worker.childTerminated(savedPid);
+    thr.join();
+    worker.childTerminated(shared_from_this());
 
-    /* Close the read side of the logger pipe. */
-    logPipe.readSide.close();
-
-    /* Get the hash info from stdout. */
-    string dummy = readLine(outPipe.readSide);
-    string expectedHashStr = statusOk(status) ? readLine(outPipe.readSide) : "";
-    outPipe.readSide.close();
-
-    /* Check the exit status and the build result. */
-    HashResult hash;
     try {
-
-        if (!statusOk(status))
-            throw SubstError(format("fetching path ‘%1%’ %2%")
-                % storePath % statusToString(status));
-
-        if (!pathExists(destPath))
-            throw SubstError(format("substitute did not produce path ‘%1%’") % destPath);
-
-        hash = hashPath(htSHA256, destPath);
-
-        /* Verify the expected hash we got from the substituer. */
-        if (expectedHashStr != "") {
-            size_t n = expectedHashStr.find(':');
-            if (n == string::npos)
-                throw Error(format("bad hash from substituter: %1%") % expectedHashStr);
-            HashType hashType = parseHashType(string(expectedHashStr, 0, n));
-            if (hashType == htUnknown)
-                throw Error(format("unknown hash algorithm in ‘%1%’") % expectedHashStr);
-            Hash expectedHash = parseHash16or32(hashType, string(expectedHashStr, n + 1));
-            Hash actualHash = hashType == htSHA256 ? hash.first : hashPath(hashType, destPath).first;
-            if (expectedHash != actualHash)
-                throw SubstError(format("hash mismatch in downloaded path ‘%1%’: expected %2%, got %3%")
-                    % storePath % printHash(expectedHash) % printHash(actualHash));
-        }
-
-    } catch (SubstError & e) {
-
+        promise.get_future().get();
+    } catch (Error & e) {
         printMsg(lvlInfo, e.msg());
 
-        if (settings.printBuildTrace) {
-            printMsg(lvlError, format("@ substituter-failed %1% %2% %3%")
-                % storePath % status % e.msg());
-        }
-
         /* Try the next substitute. */
         state = &SubstitutionGoal::tryNext;
         worker.wakeUp(shared_from_this());
         return;
     }
 
-    if (repair) replaceValidPath(storePath, destPath);
-
-    canonicalisePathMetaData(storePath, -1);
-
-    worker.store.optimisePath(storePath); // FIXME: combine with hashPath()
-
-    ValidPathInfo info2;
-    info2.path = storePath;
-    info2.narHash = hash.first;
-    info2.narSize = hash.second;
-    info2.references = info.references;
-    info2.deriver = info.deriver;
-    worker.store.registerValidPath(info2);
-
-    outputLock->setDeletion(true);
-    outputLock.reset();
-
     worker.markContentsGood(storePath);
 
     printMsg(lvlChatty,
         format("substitution of path ‘%1%’ succeeded") % storePath);
 
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ substituter-succeeded %1%") % storePath);
-
     amDone(ecSuccess);
 }
 
 
 void SubstitutionGoal::handleChildOutput(int fd, const string & data)
 {
-    assert(fd == logPipe.readSide);
-    if (verbosity >= settings.buildVerbosity) writeToStderr(data);
-    /* Don't write substitution output to a log file for now.  We
-       probably should, though. */
 }
 
 
 void SubstitutionGoal::handleEOF(int fd)
 {
-    if (fd == logPipe.readSide) worker.wakeUp(shared_from_this());
+    if (fd == outPipe.readSide) worker.wakeUp(shared_from_this());
 }
 
 
-
 //////////////////////////////////////////////////////////////////////
 
 
@@ -3505,9 +3393,8 @@ unsigned Worker::getNrLocalBuilds()
 }
 
 
-void Worker::childStarted(GoalPtr goal,
-    pid_t pid, const set<int> & fds, bool inBuildSlot,
-    bool respectTimeouts)
+void Worker::childStarted(GoalPtr goal, const set<int> & fds,
+    bool inBuildSlot, bool respectTimeouts)
 {
     Child child;
     child.goal = goal;
@@ -3515,30 +3402,29 @@ void Worker::childStarted(GoalPtr goal,
     child.timeStarted = child.lastOutput = time(0);
     child.inBuildSlot = inBuildSlot;
     child.respectTimeouts = respectTimeouts;
-    children[pid] = child;
+    children.emplace_back(child);
     if (inBuildSlot) nrLocalBuilds++;
 }
 
 
-void Worker::childTerminated(pid_t pid, bool wakeSleepers)
+void Worker::childTerminated(GoalPtr goal, bool wakeSleepers)
 {
-    assert(pid != -1); /* common mistake */
-
-    Children::iterator i = children.find(pid);
+    auto i = std::find_if(children.begin(), children.end(),
+        [&](const Child & child) { return child.goal.lock() == goal; });
     assert(i != children.end());
 
-    if (i->second.inBuildSlot) {
+    if (i->inBuildSlot) {
         assert(nrLocalBuilds > 0);
         nrLocalBuilds--;
     }
 
-    children.erase(pid);
+    children.erase(i);
 
     if (wakeSleepers) {
 
         /* Wake up goals waiting for a build slot. */
-        for (auto & i : wantingToBuild) {
-            GoalPtr goal = i.lock();
+        for (auto & j : wantingToBuild) {
+            GoalPtr goal = j.lock();
             if (goal) wakeUp(goal);
         }
 
@@ -3575,7 +3461,7 @@ void Worker::run(const Goals & _topGoals)
 {
     for (auto & i : _topGoals) topGoals.insert(i);
 
-    startNest(nest, lvlDebug, format("entered goal loop"));
+    Activity act(*logger, lvlDebug, "entered goal loop");
 
     while (1) {
 
@@ -3640,11 +3526,11 @@ void Worker::waitForInput()
     assert(sizeof(time_t) >= sizeof(long));
     time_t nearest = LONG_MAX; // nearest deadline
     for (auto & i : children) {
-        if (!i.second.respectTimeouts) continue;
+        if (!i.respectTimeouts) continue;
         if (settings.maxSilentTime != 0)
-            nearest = std::min(nearest, i.second.lastOutput + settings.maxSilentTime);
+            nearest = std::min(nearest, i.lastOutput + settings.maxSilentTime);
         if (settings.buildTimeout != 0)
-            nearest = std::min(nearest, i.second.timeStarted + settings.buildTimeout);
+            nearest = std::min(nearest, i.timeStarted + settings.buildTimeout);
     }
     if (nearest != LONG_MAX) {
         timeout.tv_sec = std::max((time_t) 1, nearest - before);
@@ -3662,7 +3548,6 @@ void Worker::waitForInput()
         timeout.tv_sec = std::max((time_t) 1, (time_t) (lastWokenUp + settings.pollInterval - before));
     } else lastWokenUp = 0;
 
-    using namespace std;
     /* Use select() to wait for the input side of any logger pipe to
        become `available'.  Note that `available' (i.e., non-blocking)
        includes EOF. */
@@ -3670,7 +3555,7 @@ void Worker::waitForInput()
     FD_ZERO(&fds);
     int fdMax = 0;
     for (auto & i : children) {
-        for (auto & j : i.second.fds) {
+        for (auto & j : i.fds) {
             FD_SET(j, &fds);
             if (j >= fdMax) fdMax = j + 1;
         }
@@ -3684,22 +3569,16 @@ void Worker::waitForInput()
     time_t after = time(0);
 
     /* Process all available file descriptors. */
+    decltype(children)::iterator i;
+    for (auto j = children.begin(); j != children.end(); j = i) {
+        i = std::next(j);
 
-    /* Since goals may be canceled from inside the loop below (causing
-       them go be erased from the `children' map), we have to be
-       careful that we don't keep iterators alive across calls to
-       timedOut(). */
-    set<pid_t> pids;
-    for (auto & i : children) pids.insert(i.first);
-
-    for (auto & i : pids) {
         checkInterrupt();
-        Children::iterator j = children.find(i);
-        if (j == children.end()) continue; // child destroyed
-        GoalPtr goal = j->second.goal.lock();
+
+        GoalPtr goal = j->goal.lock();
         assert(goal);
 
-        set<int> fds2(j->second.fds);
+        set<int> fds2(j->fds);
         for (auto & k : fds2) {
             if (FD_ISSET(k, &fds)) {
                 unsigned char buffer[4096];
@@ -3711,12 +3590,12 @@ void Worker::waitForInput()
                 } else if (rd == 0) {
                     debug(format("%1%: got EOF") % goal->getName());
                     goal->handleEOF(k);
-                    j->second.fds.erase(k);
+                    j->fds.erase(k);
                 } else {
                     printMsg(lvlVomit, format("%1%: read %2% bytes")
                         % goal->getName() % rd);
                     string data((char *) buffer, rd);
-                    j->second.lastOutput = after;
+                    j->lastOutput = after;
                     goal->handleChildOutput(k, data);
                 }
             }
@@ -3724,8 +3603,8 @@ void Worker::waitForInput()
 
         if (goal->getExitCode() == Goal::ecBusy &&
             settings.maxSilentTime != 0 &&
-            j->second.respectTimeouts &&
-            after - j->second.lastOutput >= (time_t) settings.maxSilentTime)
+            j->respectTimeouts &&
+            after - j->lastOutput >= (time_t) settings.maxSilentTime)
         {
             printMsg(lvlError,
                 format("%1% timed out after %2% seconds of silence")
@@ -3735,8 +3614,8 @@ void Worker::waitForInput()
 
         else if (goal->getExitCode() == Goal::ecBusy &&
             settings.buildTimeout != 0 &&
-            j->second.respectTimeouts &&
-            after - j->second.timeStarted >= (time_t) settings.buildTimeout)
+            j->respectTimeouts &&
+            after - j->timeStarted >= (time_t) settings.buildTimeout)
         {
             printMsg(lvlError,
                 format("%1% timed out after %2% seconds")
@@ -3767,14 +3646,14 @@ bool Worker::pathContentsGood(const Path & path)
     std::map<Path, bool>::iterator i = pathContentsGoodCache.find(path);
     if (i != pathContentsGoodCache.end()) return i->second;
     printMsg(lvlInfo, format("checking path ‘%1%’...") % path);
-    ValidPathInfo info = store.queryPathInfo(path);
+    auto info = store.queryPathInfo(path);
     bool res;
     if (!pathExists(path))
         res = false;
     else {
-        HashResult current = hashPath(info.narHash.type, path);
+        HashResult current = hashPath(info->narHash.type, path);
         Hash nullHash(htSHA256);
-        res = info.narHash == nullHash || info.narHash == current.first;
+        res = info->narHash == nullHash || info->narHash == current.first;
     }
     pathContentsGoodCache[path] = res;
     if (!res) printMsg(lvlError, format("path ‘%1%’ is corrupted or missing!") % path);
@@ -3793,8 +3672,6 @@ void Worker::markContentsGood(const Path & path)
 
 void LocalStore::buildPaths(const PathSet & drvPaths, BuildMode buildMode)
 {
-    startNest(nest, lvlDebug, format("building %1%") % showPaths(drvPaths));
-
     Worker worker(*this);
 
     Goals goals;
@@ -3824,8 +3701,6 @@ void LocalStore::buildPaths(const PathSet & drvPaths, BuildMode buildMode)
 BuildResult LocalStore::buildDerivation(const Path & drvPath, const BasicDerivation & drv,
     BuildMode buildMode)
 {
-    startNest(nest, lvlDebug, format("building %1%") % showPaths({drvPath}));
-
     Worker worker(*this);
     auto goal = worker.makeBasicDerivationGoal(drvPath, drv, buildMode);
 
@@ -3870,7 +3745,7 @@ void LocalStore::repairPath(const Path & path)
     if (goal->getExitCode() != Goal::ecSuccess) {
         /* Since substituting the path didn't work, if we have a valid
            deriver, then rebuild the deriver. */
-        Path deriver = queryDeriver(path);
+        auto deriver = queryPathInfo(path)->deriver;
         if (deriver != "" && isValidPath(deriver)) {
             goals.clear();
             goals.insert(worker.makeDerivationGoal(deriver, StringSet(), bmRepair));
diff --git a/src/libstore/builtins.cc b/src/libstore/builtins.cc
index 50417b644a02..a4785d6905bb 100644
--- a/src/libstore/builtins.cc
+++ b/src/libstore/builtins.cc
@@ -31,7 +31,7 @@ void builtinFetchurl(const BasicDerivation & drv)
     auto unpack = drv.env.find("unpack");
     if (unpack != drv.env.end() && unpack->second == "1") {
         if (string(*data.data, 0, 6) == string("\xfd" "7zXZ\0", 6))
-            data.data = decompressXZ(*data.data);
+            data.data = decompress("xz", ref<std::string>(data.data));
         StringSource source(*data.data);
         restorePath(storePath, source);
     } else
diff --git a/src/libstore/derivations.cc b/src/libstore/derivations.cc
index d9b009d40322..becf8524546c 100644
--- a/src/libstore/derivations.cc
+++ b/src/libstore/derivations.cc
@@ -290,7 +290,7 @@ Hash hashDerivationModulo(Store & store, Derivation drv)
     DerivationInputs inputs2;
     for (auto & i : drv.inputDrvs) {
         Hash h = drvHashes[i.first];
-        if (h.type == htUnknown) {
+        if (!h) {
             assert(store.isValidPath(i.first));
             Derivation drv2 = readDerivation(i.first);
             h = hashDerivationModulo(store, drv2);
diff --git a/src/libstore/download.cc b/src/libstore/download.cc
index 8cd3ad741e10..6e39330e40d9 100644
--- a/src/libstore/download.cc
+++ b/src/libstore/download.cc
@@ -225,7 +225,7 @@ Path Downloader::downloadCached(ref<Store> store, const string & url_, bool unpa
 {
     auto url = resolveUri(url_);
 
-    Path cacheDir = getEnv("XDG_CACHE_HOME", getEnv("HOME", "") + "/.cache") + "/nix/tarballs";
+    Path cacheDir = getCacheDir() + "/nix/tarballs";
     createDirs(cacheDir);
 
     string urlHash = printHash32(hashString(htSHA256, url));
@@ -313,7 +313,7 @@ bool isUri(const string & s)
     size_t pos = s.find("://");
     if (pos == string::npos) return false;
     string scheme(s, 0, pos);
-    return scheme == "http" || scheme == "https" || scheme == "file" || scheme == "channel";
+    return scheme == "http" || scheme == "https" || scheme == "file" || scheme == "channel" || scheme == "git";
 }
 
 
diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
index 52afa1b14e03..8fc582f4c20d 100644
--- a/src/libstore/gc.cc
+++ b/src/libstore/gc.cc
@@ -305,7 +305,7 @@ void LocalStore::findRoots(const Path & path, unsigned char type, Roots & roots)
 
         else if (type == DT_REG) {
             Path storePath = settings.nixStore + "/" + baseNameOf(path);
-            if (isValidPath(storePath))
+            if (isStorePath(storePath) && isValidPath(storePath))
                 roots[path] = storePath;
         }
 
@@ -407,7 +407,7 @@ void LocalStore::deletePathRecursive(GCState & state, const Path & path)
         queryReferrers(path, referrers);
         for (auto & i : referrers)
             if (i != path) deletePathRecursive(state, i);
-        size = queryPathInfo(path).narSize;
+        size = queryPathInfo(path)->narSize;
         invalidatePathChecked(path);
     }
 
@@ -485,7 +485,7 @@ bool LocalStore::canReachRoot(GCState & state, PathSet & visited, const Path & p
     if (state.gcKeepDerivations && isDerivation(path)) {
         PathSet outputs = queryDerivationOutputs(path);
         for (auto & i : outputs)
-            if (isValidPath(i) && queryDeriver(i) == path)
+            if (isValidPath(i) && queryPathInfo(i)->deriver == path)
                 incoming.insert(i);
     }
 
@@ -514,7 +514,7 @@ void LocalStore::tryToDelete(GCState & state, const Path & path)
 
     if (path == linksDir || path == state.trashDir) return;
 
-    startNest(nest, lvlDebug, format("considering whether to delete ‘%1%’") % path);
+    Activity act(*logger, lvlDebug, format("considering whether to delete ‘%1%’") % path);
 
     if (!isValidPath(path)) {
         /* A lock file belonging to a path that we're building right
@@ -691,7 +691,7 @@ void LocalStore::collectGarbage(const GCOptions & options, GCResults & results)
                 string name = dirent->d_name;
                 if (name == "." || name == "..") continue;
                 Path path = settings.nixStore + "/" + name;
-                if (isValidPath(path))
+                if (isStorePath(path) && isValidPath(path))
                     entries.push_back(path);
                 else
                     tryToDelete(state, path);
diff --git a/src/libstore/globals.cc b/src/libstore/globals.cc
index b6078253319f..c12178e4028a 100644
--- a/src/libstore/globals.cc
+++ b/src/libstore/globals.cc
@@ -28,7 +28,6 @@ Settings::Settings()
     keepFailed = false;
     keepGoing = false;
     tryFallback = false;
-    buildVerbosity = lvlError;
     maxBuildJobs = 1;
     buildCores = 1;
 #ifdef _SC_NPROCESSORS_ONLN
@@ -40,7 +39,6 @@ Settings::Settings()
     maxSilentTime = 0;
     buildTimeout = 0;
     useBuildHook = true;
-    printBuildTrace = false;
     reservedSize = 8 * 1024 * 1024;
     fsyncMetadata = true;
     useSQLiteWAL = true;
@@ -186,19 +184,6 @@ void Settings::update()
     _get(enableImportNative, "allow-unsafe-native-code-during-evaluation");
     _get(useCaseHack, "use-case-hack");
     _get(preBuildHook, "pre-build-hook");
-
-    string subs = getEnv("NIX_SUBSTITUTERS", "default");
-    if (subs == "default") {
-        substituters.clear();
-#if 0
-        if (getEnv("NIX_OTHER_STORES") != "")
-            substituters.push_back(nixLibexecDir + "/nix/substituters/copy-from-other-stores.pl");
-#endif
-        substituters.push_back(nixLibexecDir + "/nix/substituters/download-from-binary-cache.pl");
-        if (useSshSubstituter && !sshSubstituterHosts.empty())
-            substituters.push_back(nixLibexecDir + "/nix/substituters/download-via-ssh");
-    } else
-        substituters = tokenizeString<Strings>(subs, ":");
 }
 
 
diff --git a/src/libstore/globals.hh b/src/libstore/globals.hh
index 572fa7188c14..65f763ace3c7 100644
--- a/src/libstore/globals.hh
+++ b/src/libstore/globals.hh
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "types.hh"
+#include "logging.hh"
 
 #include <map>
 #include <sys/types.h>
@@ -77,8 +78,12 @@ struct Settings {
        instead. */
     bool tryFallback;
 
-    /* Verbosity level for build output. */
-    Verbosity buildVerbosity;
+    /* Whether to show build log output in real time. */
+    bool verboseBuild = true;
+
+    /* If verboseBuild is false, the number of lines of the tail of
+       the log to show if a build fails. */
+    size_t logLines = 10;
 
     /* Maximum number of parallel build jobs.  0 means unlimited. */
     unsigned int maxBuildJobs;
@@ -105,31 +110,10 @@ struct Settings {
        means infinity.  */
     time_t buildTimeout;
 
-    /* The substituters.  There are programs that can somehow realise
-       a store path without building, e.g., by downloading it or
-       copying it from a CD. */
-    Paths substituters;
-
     /* Whether to use build hooks (for distributed builds).  Sometimes
        users want to disable this from the command-line. */
     bool useBuildHook;
 
-    /* Whether buildDerivations() should print out lines on stderr in
-       a fixed format to allow its progress to be monitored.  Each
-       line starts with a "@".  The following are defined:
-
-       @ build-started <drvpath> <outpath> <system> <logfile>
-       @ build-failed <drvpath> <outpath> <exitcode> <error text>
-       @ build-succeeded <drvpath> <outpath>
-       @ substituter-started <outpath> <substituter>
-       @ substituter-failed <outpath> <exitcode> <error text>
-       @ substituter-succeeded <outpath>
-
-       Best combined with --no-build-output, otherwise stderr might
-       conceivably contain lines in this format printed by the
-       builders. */
-    bool printBuildTrace;
-
     /* Amount of reserved space for the garbage collector
        (/nix/var/nix/db/reserved). */
     off_t reservedSize;
diff --git a/src/libstore/http-binary-cache-store.cc b/src/libstore/http-binary-cache-store.cc
index 6dcea1cbf090..92d94aeeacd5 100644
--- a/src/libstore/http-binary-cache-store.cc
+++ b/src/libstore/http-binary-cache-store.cc
@@ -1,6 +1,7 @@
 #include "binary-cache-store.hh"
 #include "download.hh"
 #include "globals.hh"
+#include "nar-info-disk-cache.hh"
 
 namespace nix {
 
@@ -15,8 +16,8 @@ private:
 public:
 
     HttpBinaryCacheStore(std::shared_ptr<Store> localStore,
-        const Path & secretKeyFile, const Path & _cacheUri)
-        : BinaryCacheStore(localStore, secretKeyFile)
+        const StoreParams & params, const Path & _cacheUri)
+        : BinaryCacheStore(localStore, params)
         , cacheUri(_cacheUri)
         , downloaders(
             std::numeric_limits<size_t>::max(),
@@ -24,13 +25,23 @@ public:
     {
         if (cacheUri.back() == '/')
             cacheUri.pop_back();
+
+        diskCache = getNarInfoDiskCache();
+    }
+
+    std::string getUri() override
+    {
+        return cacheUri;
     }
 
     void init() override
     {
         // FIXME: do this lazily?
-        if (!fileExists("nix-cache-info"))
-            throw Error(format("‘%s’ does not appear to be a binary cache") % cacheUri);
+        if (!diskCache->cacheExists(cacheUri)) {
+            if (!fileExists("nix-cache-info"))
+                throw Error(format("‘%s’ does not appear to be a binary cache") % cacheUri);
+            diskCache->createCache(cacheUri);
+        }
     }
 
 protected:
@@ -74,12 +85,14 @@ protected:
 
 };
 
-static RegisterStoreImplementation regStore([](const std::string & uri) -> std::shared_ptr<Store> {
+static RegisterStoreImplementation regStore([](
+    const std::string & uri, const StoreParams & params)
+    -> std::shared_ptr<Store>
+{
     if (std::string(uri, 0, 7) != "http://" &&
         std::string(uri, 0, 8) != "https://") return 0;
     auto store = std::make_shared<HttpBinaryCacheStore>(std::shared_ptr<Store>(0),
-        settings.get("binary-cache-secret-key-file", string("")),
-        uri);
+        params, uri);
     store->init();
     return store;
 });
diff --git a/src/libstore/local-binary-cache-store.cc b/src/libstore/local-binary-cache-store.cc
index 7968c98b9558..2c2944938761 100644
--- a/src/libstore/local-binary-cache-store.cc
+++ b/src/libstore/local-binary-cache-store.cc
@@ -12,10 +12,19 @@ private:
 public:
 
     LocalBinaryCacheStore(std::shared_ptr<Store> localStore,
-        const Path & secretKeyFile, const Path & binaryCacheDir);
+        const StoreParams & params, const Path & binaryCacheDir)
+        : BinaryCacheStore(localStore, params)
+        , binaryCacheDir(binaryCacheDir)
+    {
+    }
 
     void init() override;
 
+    std::string getUri() override
+    {
+        return "file://" + binaryCacheDir;
+    }
+
 protected:
 
     bool fileExists(const std::string & path) override;
@@ -24,14 +33,21 @@ protected:
 
     std::shared_ptr<std::string> getFile(const std::string & path) override;
 
-};
+    PathSet queryAllValidPaths() override
+    {
+        PathSet paths;
 
-LocalBinaryCacheStore::LocalBinaryCacheStore(std::shared_ptr<Store> localStore,
-    const Path & secretKeyFile, const Path & binaryCacheDir)
-    : BinaryCacheStore(localStore, secretKeyFile)
-    , binaryCacheDir(binaryCacheDir)
-{
-}
+        for (auto & entry : readDirectory(binaryCacheDir)) {
+            if (entry.name.size() != 40 ||
+                !hasSuffix(entry.name, ".narinfo"))
+                continue;
+            paths.insert(settings.nixStore + "/" + entry.name.substr(0, entry.name.size() - 8));
+        }
+
+        return paths;
+    }
+
+};
 
 void LocalBinaryCacheStore::init()
 {
@@ -69,20 +85,15 @@ std::shared_ptr<std::string> LocalBinaryCacheStore::getFile(const std::string &
     }
 }
 
-ref<Store> openLocalBinaryCacheStore(std::shared_ptr<Store> localStore,
-    const Path & secretKeyFile, const Path & binaryCacheDir)
+static RegisterStoreImplementation regStore([](
+    const std::string & uri, const StoreParams & params)
+    -> std::shared_ptr<Store>
 {
-    auto store = make_ref<LocalBinaryCacheStore>(
-        localStore, secretKeyFile, binaryCacheDir);
+    if (std::string(uri, 0, 7) != "file://") return 0;
+    auto store = std::make_shared<LocalBinaryCacheStore>(
+        std::shared_ptr<Store>(0), params, std::string(uri, 7));
     store->init();
     return store;
-}
-
-static RegisterStoreImplementation regStore([](const std::string & uri) -> std::shared_ptr<Store> {
-    if (std::string(uri, 0, 7) != "file://") return 0;
-    return openLocalBinaryCacheStore(std::shared_ptr<Store>(0),
-        settings.get("binary-cache-secret-key-file", string("")),
-        std::string(uri, 7));
 });
 
 }
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index d6e1e4d7e0d4..01a11f11f65d 100644
--- a/src/libstore/local-store.cc
+++ b/src/libstore/local-store.cc
@@ -5,12 +5,11 @@
 #include "pathlocks.hh"
 #include "worker-protocol.hh"
 #include "derivations.hh"
-#include "affinity.hh"
+#include "nar-info.hh"
 
 #include <iostream>
 #include <algorithm>
 #include <cstring>
-#include <atomic>
 
 #include <sys/types.h>
 #include <sys/stat.h>
@@ -220,19 +219,6 @@ LocalStore::~LocalStore()
     auto state(_state.lock());
 
     try {
-        for (auto & i : state->runningSubstituters) {
-            if (i.second.disabled) continue;
-            i.second.to.close();
-            i.second.from.close();
-            i.second.error.close();
-            if (i.second.pid != -1)
-                i.second.pid.wait(true);
-        }
-    } catch (...) {
-        ignoreException();
-    }
-
-    try {
         if (state->fdTempRoots != -1) {
             state->fdTempRoots.close();
             unlink(state->fnTempRoots.c_str());
@@ -243,6 +229,12 @@ LocalStore::~LocalStore()
 }
 
 
+std::string LocalStore::getUri()
+{
+    return "local";
+}
+
+
 int LocalStore::getSchema()
 {
     int curSchema = 0;
@@ -577,6 +569,11 @@ uint64_t LocalStore::addValidPath(State & state,
         }
     }
 
+    {
+        auto state_(Store::state.lock());
+        state_->pathInfoCache.upsert(storePathToHash(info.path), std::make_shared<ValidPathInfo>(info));
+    }
+
     return id;
 }
 
@@ -595,44 +592,44 @@ Hash parseHashField(const Path & path, const string & s)
 }
 
 
-ValidPathInfo LocalStore::queryPathInfo(const Path & path)
+std::shared_ptr<ValidPathInfo> LocalStore::queryPathInfoUncached(const Path & path)
 {
-    ValidPathInfo info;
-    info.path = path;
+    auto info = std::make_shared<ValidPathInfo>();
+    info->path = path;
 
     assertStorePath(path);
 
-    return retrySQLite<ValidPathInfo>([&]() {
+    return retrySQLite<std::shared_ptr<ValidPathInfo>>([&]() {
         auto state(_state.lock());
 
         /* Get the path info. */
         auto useQueryPathInfo(state->stmtQueryPathInfo.use()(path));
 
         if (!useQueryPathInfo.next())
-            throw Error(format("path ‘%1%’ is not valid") % path);
+            return std::shared_ptr<ValidPathInfo>();
 
-        info.id = useQueryPathInfo.getInt(0);
+        info->id = useQueryPathInfo.getInt(0);
 
-        info.narHash = parseHashField(path, useQueryPathInfo.getStr(1));
+        info->narHash = parseHashField(path, useQueryPathInfo.getStr(1));
 
-        info.registrationTime = useQueryPathInfo.getInt(2);
+        info->registrationTime = useQueryPathInfo.getInt(2);
 
         auto s = (const char *) sqlite3_column_text(state->stmtQueryPathInfo, 3);
-        if (s) info.deriver = s;
+        if (s) info->deriver = s;
 
         /* Note that narSize = NULL yields 0. */
-        info.narSize = useQueryPathInfo.getInt(4);
+        info->narSize = useQueryPathInfo.getInt(4);
 
-        info.ultimate = useQueryPathInfo.getInt(5) == 1;
+        info->ultimate = useQueryPathInfo.getInt(5) == 1;
 
         s = (const char *) sqlite3_column_text(state->stmtQueryPathInfo, 6);
-        if (s) info.sigs = tokenizeString<StringSet>(s, " ");
+        if (s) info->sigs = tokenizeString<StringSet>(s, " ");
 
         /* Get the references. */
-        auto useQueryReferences(state->stmtQueryReferences.use()(info.id));
+        auto useQueryReferences(state->stmtQueryReferences.use()(info->id));
 
         while (useQueryReferences.next())
-            info.references.insert(useQueryReferences.getStr(0));
+            info->references.insert(useQueryReferences.getStr(0));
 
         return info;
     });
@@ -661,17 +658,17 @@ uint64_t LocalStore::queryValidPathId(State & state, const Path & path)
 }
 
 
-bool LocalStore::isValidPath(State & state, const Path & path)
+bool LocalStore::isValidPath_(State & state, const Path & path)
 {
     return state.stmtQueryPathInfo.use()(path).next();
 }
 
 
-bool LocalStore::isValidPath(const Path & path)
+bool LocalStore::isValidPathUncached(const Path & path)
 {
     return retrySQLite<bool>([&]() {
         auto state(_state.lock());
-        return isValidPath(*state, path);
+        return isValidPath_(*state, path);
     });
 }
 
@@ -716,12 +713,6 @@ void LocalStore::queryReferrers(const Path & path, PathSet & referrers)
 }
 
 
-Path LocalStore::queryDeriver(const Path & path)
-{
-    return queryPathInfo(path).deriver;
-}
-
-
 PathSet LocalStore::queryValidDerivers(const Path & path)
 {
     assertStorePath(path);
@@ -793,215 +784,46 @@ Path LocalStore::queryPathFromHashPart(const string & hashPart)
 }
 
 
-void LocalStore::setSubstituterEnv()
-{
-    static std::atomic_flag done;
-
-    if (done.test_and_set()) return;
-
-    /* Pass configuration options (including those overridden with
-       --option) to substituters. */
-    setenv("_NIX_OPTIONS", settings.pack().c_str(), 1);
-}
-
-
-void LocalStore::startSubstituter(const Path & substituter, RunningSubstituter & run)
-{
-    if (run.disabled || run.pid != -1) return;
-
-    debug(format("starting substituter program ‘%1%’") % substituter);
-
-    Pipe toPipe, fromPipe, errorPipe;
-
-    toPipe.create();
-    fromPipe.create();
-    errorPipe.create();
-
-    setSubstituterEnv();
-
-    run.pid = startProcess([&]() {
-        if (dup2(toPipe.readSide, STDIN_FILENO) == -1)
-            throw SysError("dupping stdin");
-        if (dup2(fromPipe.writeSide, STDOUT_FILENO) == -1)
-            throw SysError("dupping stdout");
-        if (dup2(errorPipe.writeSide, STDERR_FILENO) == -1)
-            throw SysError("dupping stderr");
-        execl(substituter.c_str(), substituter.c_str(), "--query", NULL);
-        throw SysError(format("executing ‘%1%’") % substituter);
-    });
-
-    run.program = baseNameOf(substituter);
-    run.to = toPipe.writeSide.borrow();
-    run.from = run.fromBuf.fd = fromPipe.readSide.borrow();
-    run.error = errorPipe.readSide.borrow();
-
-    toPipe.readSide.close();
-    fromPipe.writeSide.close();
-    errorPipe.writeSide.close();
-
-    /* The substituter may exit right away if it's disabled in any way
-       (e.g. copy-from-other-stores.pl will exit if no other stores
-       are configured). */
-    try {
-        getLineFromSubstituter(run);
-    } catch (EndOfFile & e) {
-        run.to.close();
-        run.from.close();
-        run.error.close();
-        run.disabled = true;
-        if (run.pid.wait(true) != 0) throw;
-    }
-}
-
-
-/* Read a line from the substituter's stdout, while also processing
-   its stderr. */
-string LocalStore::getLineFromSubstituter(RunningSubstituter & run)
-{
-    string res, err;
-
-    /* We might have stdout data left over from the last time. */
-    if (run.fromBuf.hasData()) goto haveData;
-
-    while (1) {
-        checkInterrupt();
-
-        fd_set fds;
-        FD_ZERO(&fds);
-        FD_SET(run.from, &fds);
-        FD_SET(run.error, &fds);
-
-        /* Wait for data to appear on the substituter's stdout or
-           stderr. */
-        if (select(run.from > run.error ? run.from + 1 : run.error + 1, &fds, 0, 0, 0) == -1) {
-            if (errno == EINTR) continue;
-            throw SysError("waiting for input from the substituter");
-        }
-
-        /* Completely drain stderr before dealing with stdout. */
-        if (FD_ISSET(run.error, &fds)) {
-            char buf[4096];
-            ssize_t n = read(run.error, (unsigned char *) buf, sizeof(buf));
-            if (n == -1) {
-                if (errno == EINTR) continue;
-                throw SysError("reading from substituter's stderr");
-            }
-            if (n == 0) throw EndOfFile(format("substituter ‘%1%’ died unexpectedly") % run.program);
-            err.append(buf, n);
-            string::size_type p;
-            while ((p = err.find('\n')) != string::npos) {
-                printMsg(lvlError, run.program + ": " + string(err, 0, p));
-                err = string(err, p + 1);
-            }
-        }
-
-        /* Read from stdout until we get a newline or the buffer is empty. */
-        else if (run.fromBuf.hasData() || FD_ISSET(run.from, &fds)) {
-        haveData:
-            do {
-                unsigned char c;
-                run.fromBuf(&c, 1);
-                if (c == '\n') {
-                    if (!err.empty()) printMsg(lvlError, run.program + ": " + err);
-                    return res;
-                }
-                res += c;
-            } while (run.fromBuf.hasData());
-        }
-    }
-}
-
-
-template<class T> T LocalStore::getIntLineFromSubstituter(RunningSubstituter & run)
-{
-    string s = getLineFromSubstituter(run);
-    T res;
-    if (!string2Int(s, res)) throw Error("integer expected from stream");
-    return res;
-}
-
-
 PathSet LocalStore::querySubstitutablePaths(const PathSet & paths)
 {
-    auto state(_state.lock());
-
     PathSet res;
-    for (auto & i : settings.substituters) {
-        if (res.size() == paths.size()) break;
-        RunningSubstituter & run(state->runningSubstituters[i]);
-        startSubstituter(i, run);
-        if (run.disabled) continue;
-        string s = "have ";
-        for (auto & j : paths)
-            if (res.find(j) == res.end()) { s += j; s += " "; }
-        writeLine(run.to, s);
-        while (true) {
-            /* FIXME: we only read stderr when an error occurs, so
-               substituters should only write (short) messages to
-               stderr when they fail.  I.e. they shouldn't write debug
-               output. */
-            Path path = getLineFromSubstituter(run);
-            if (path == "") break;
-            res.insert(path);
+    for (auto & sub : getDefaultSubstituters()) {
+        for (auto & path : paths) {
+            if (res.count(path)) continue;
+            debug(format("checking substituter ‘%s’ for path ‘%s’")
+                % sub->getUri() % path);
+            if (sub->isValidPath(path))
+                res.insert(path);
         }
     }
-
     return res;
 }
 
 
-void LocalStore::querySubstitutablePathInfos(const Path & substituter,
-    PathSet & paths, SubstitutablePathInfos & infos)
-{
-    auto state(_state.lock());
-
-    RunningSubstituter & run(state->runningSubstituters[substituter]);
-    startSubstituter(substituter, run);
-    if (run.disabled) return;
-
-    string s = "info ";
-    for (auto & i : paths)
-        if (infos.find(i) == infos.end()) { s += i; s += " "; }
-    writeLine(run.to, s);
-
-    while (true) {
-        Path path = getLineFromSubstituter(run);
-        if (path == "") break;
-        if (paths.find(path) == paths.end())
-            throw Error(format("got unexpected path ‘%1%’ from substituter") % path);
-        paths.erase(path);
-        SubstitutablePathInfo & info(infos[path]);
-        info.deriver = getLineFromSubstituter(run);
-        if (info.deriver != "") assertStorePath(info.deriver);
-        int nrRefs = getIntLineFromSubstituter<int>(run);
-        while (nrRefs--) {
-            Path p = getLineFromSubstituter(run);
-            assertStorePath(p);
-            info.references.insert(p);
-        }
-        info.downloadSize = getIntLineFromSubstituter<long long>(run);
-        info.narSize = getIntLineFromSubstituter<long long>(run);
-    }
-}
-
-
 void LocalStore::querySubstitutablePathInfos(const PathSet & paths,
     SubstitutablePathInfos & infos)
 {
-    PathSet todo = paths;
-    for (auto & i : settings.substituters) {
-        if (todo.empty()) break;
-        querySubstitutablePathInfos(i, todo, infos);
+    for (auto & sub : getDefaultSubstituters()) {
+        for (auto & path : paths) {
+            if (infos.count(path)) continue;
+            debug(format("checking substituter ‘%s’ for path ‘%s’")
+                % sub->getUri() % path);
+            try {
+                auto info = sub->queryPathInfo(path);
+                auto narInfo = std::dynamic_pointer_cast<const NarInfo>(
+                    std::shared_ptr<const ValidPathInfo>(info));
+                infos[path] = SubstitutablePathInfo{
+                    info->deriver,
+                    info->references,
+                    narInfo ? narInfo->fileSize : 0,
+                    info->narSize};
+            } catch (InvalidPath) {
+            }
+        }
     }
 }
 
 
-Hash LocalStore::queryPathHash(const Path & path)
-{
-    return queryPathInfo(path).narHash;
-}
-
-
 void LocalStore::registerValidPath(const ValidPathInfo & info)
 {
     ValidPathInfos infos;
@@ -1026,7 +848,7 @@ void LocalStore::registerValidPaths(const ValidPathInfos & infos)
 
         for (auto & i : infos) {
             assert(i.narHash.type == htSHA256);
-            if (isValidPath(*state, i.path))
+            if (isValidPath_(*state, i.path))
                 updatePathInfo(*state, i);
             else
                 addValidPath(*state, i, false);
@@ -1071,6 +893,11 @@ void LocalStore::invalidatePath(State & state, const Path & path)
 
     /* Note that the foreign key constraints on the Refs table take
        care of deleting the references entries for `path'. */
+
+    {
+        auto state_(Store::state.lock());
+        state_->pathInfoCache.erase(storePathToHash(path));
+    }
 }
 
 
@@ -1225,8 +1052,7 @@ void LocalStore::exportPath(const Path & path, bool sign,
 
     printMsg(lvlTalkative, format("exporting path ‘%1%’") % path);
 
-    if (!isValidPath(path))
-        throw Error(format("path ‘%1%’ is not valid") % path);
+    auto info = queryPathInfo(path);
 
     HashAndWriteSink hashAndWriteSink(sink);
 
@@ -1236,15 +1062,11 @@ void LocalStore::exportPath(const Path & path, bool sign,
        filesystem corruption from spreading to other machines.
        Don't complain if the stored hash is zero (unknown). */
     Hash hash = hashAndWriteSink.currentHash();
-    Hash storedHash = queryPathHash(path);
-    if (hash != storedHash && storedHash != Hash(storedHash.type))
+    if (hash != info->narHash && info->narHash != Hash(info->narHash.type))
         throw Error(format("hash of path ‘%1%’ has changed from ‘%2%’ to ‘%3%’!") % path
-            % printHash(storedHash) % printHash(hash));
-
-    PathSet references;
-    queryReferences(path, references);
+            % printHash(info->narHash) % printHash(hash));
 
-    hashAndWriteSink << exportMagic << path << references << queryDeriver(path);
+    hashAndWriteSink << exportMagic << path << info->references << info->deriver;
 
     if (sign) {
         Hash hash = hashAndWriteSink.currentHash();
@@ -1440,7 +1262,7 @@ void LocalStore::invalidatePathChecked(const Path & path)
 
         SQLiteTxn txn(state->db);
 
-        if (isValidPath(*state, path)) {
+        if (isValidPath_(*state, path)) {
             PathSet referrers; queryReferrers(*state, path, referrers);
             referrers.erase(path); /* ignore self-references */
             if (!referrers.empty())
@@ -1486,38 +1308,38 @@ bool LocalStore::verifyStore(bool checkContents, bool repair)
 
         for (auto & i : validPaths) {
             try {
-                ValidPathInfo info = queryPathInfo(i);
+                auto info = std::const_pointer_cast<ValidPathInfo>(std::shared_ptr<const ValidPathInfo>(queryPathInfo(i)));
 
                 /* Check the content hash (optionally - slow). */
                 printMsg(lvlTalkative, format("checking contents of ‘%1%’") % i);
-                HashResult current = hashPath(info.narHash.type, i);
+                HashResult current = hashPath(info->narHash.type, i);
 
-                if (info.narHash != nullHash && info.narHash != current.first) {
+                if (info->narHash != nullHash && info->narHash != current.first) {
                     printMsg(lvlError, format("path ‘%1%’ was modified! "
                             "expected hash ‘%2%’, got ‘%3%’")
-                        % i % printHash(info.narHash) % printHash(current.first));
+                        % i % printHash(info->narHash) % printHash(current.first));
                     if (repair) repairPath(i); else errors = true;
                 } else {
 
                     bool update = false;
 
                     /* Fill in missing hashes. */
-                    if (info.narHash == nullHash) {
+                    if (info->narHash == nullHash) {
                         printMsg(lvlError, format("fixing missing hash on ‘%1%’") % i);
-                        info.narHash = current.first;
+                        info->narHash = current.first;
                         update = true;
                     }
 
                     /* Fill in missing narSize fields (from old stores). */
-                    if (info.narSize == 0) {
+                    if (info->narSize == 0) {
                         printMsg(lvlError, format("updating size field on ‘%1%’ to %2%") % i % current.second);
-                        info.narSize = current.second;
+                        info->narSize = current.second;
                         update = true;
                     }
 
                     if (update) {
                         auto state(_state.lock());
-                        updatePathInfo(*state, info);
+                        updatePathInfo(*state, *info);
                     }
 
                 }
@@ -1656,11 +1478,11 @@ void LocalStore::addSignatures(const Path & storePath, const StringSet & sigs)
 
         SQLiteTxn txn(state->db);
 
-        auto info = queryPathInfo(storePath);
+        auto info = std::const_pointer_cast<ValidPathInfo>(std::shared_ptr<const ValidPathInfo>(queryPathInfo(storePath)));
 
-        info.sigs.insert(sigs.begin(), sigs.end());
+        info->sigs.insert(sigs.begin(), sigs.end());
 
-        updatePathInfo(*state, info);
+        updatePathInfo(*state, *info);
 
         txn.commit();
     });
diff --git a/src/libstore/local-store.hh b/src/libstore/local-store.hh
index 14ff92c35cc5..6f2341decfbd 100644
--- a/src/libstore/local-store.hh
+++ b/src/libstore/local-store.hh
@@ -40,17 +40,6 @@ struct OptimiseStats
 };
 
 
-struct RunningSubstituter
-{
-    Path program;
-    Pid pid;
-    AutoCloseFD to, from, error;
-    FdSource fromBuf;
-    bool disabled;
-    RunningSubstituter() : disabled(false) { };
-};
-
-
 class LocalStore : public LocalFSStore
 {
 private:
@@ -80,10 +69,6 @@ private:
         /* The file to which we write our temporary roots. */
         Path fnTempRoots;
         AutoCloseFD fdTempRoots;
-
-        typedef std::map<Path, RunningSubstituter> RunningSubstituters;
-        RunningSubstituters runningSubstituters;
-
     };
 
     Sync<State, std::recursive_mutex> _state;
@@ -102,20 +87,18 @@ public:
 
     /* Implementations of abstract store API methods. */
 
-    bool isValidPath(const Path & path) override;
+    std::string getUri() override;
+
+    bool isValidPathUncached(const Path & path) override;
 
     PathSet queryValidPaths(const PathSet & paths) override;
 
     PathSet queryAllValidPaths() override;
 
-    ValidPathInfo queryPathInfo(const Path & path) override;
-
-    Hash queryPathHash(const Path & path) override;
+    std::shared_ptr<ValidPathInfo> queryPathInfoUncached(const Path & path) override;
 
     void queryReferrers(const Path & path, PathSet & referrers) override;
 
-    Path queryDeriver(const Path & path) override;
-
     PathSet queryValidDerivers(const Path & path) override;
 
     PathSet queryDerivationOutputs(const Path & path) override;
@@ -126,9 +109,6 @@ public:
 
     PathSet querySubstitutablePaths(const PathSet & paths) override;
 
-    void querySubstitutablePathInfos(const Path & substituter,
-        PathSet & paths, SubstitutablePathInfos & infos);
-
     void querySubstitutablePathInfos(const PathSet & paths,
         SubstitutablePathInfos & infos) override;
 
@@ -196,8 +176,6 @@ public:
        a substituter (if available). */
     void repairPath(const Path & path);
 
-    void setSubstituterEnv();
-
     void addSignatures(const Path & storePath, const StringSet & sigs) override;
 
     static bool haveWriteAccess();
@@ -250,13 +228,6 @@ private:
 
     void removeUnusedLinks(const GCState & state);
 
-    void startSubstituter(const Path & substituter,
-        RunningSubstituter & runningSubstituter);
-
-    string getLineFromSubstituter(RunningSubstituter & run);
-
-    template<class T> T getIntLineFromSubstituter(RunningSubstituter & run);
-
     Path createTempDirInStore();
 
     Path importPath(bool requireSignature, Source & source);
@@ -270,7 +241,7 @@ private:
     void optimisePath_(OptimiseStats & stats, const Path & path, InodeHash & inodeHash);
 
     // Internal versions that are not wrapped in retry_sqlite.
-    bool isValidPath(State & state, const Path & path);
+    bool isValidPath_(State & state, const Path & path);
     void queryReferrers(State & state, const Path & path, PathSet & referrers);
 
     /* Add signatures to a ValidPathInfo using the secret keys
diff --git a/src/libstore/local.mk b/src/libstore/local.mk
index 9a01596c36be..22b0f235e0b2 100644
--- a/src/libstore/local.mk
+++ b/src/libstore/local.mk
@@ -8,7 +8,7 @@ libstore_SOURCES := $(wildcard $(d)/*.cc)
 
 libstore_LIBS = libutil libformat
 
-libstore_LDFLAGS = $(SQLITE3_LIBS) -lbz2 $(LIBCURL_LIBS) $(SODIUM_LIBS)
+libstore_LDFLAGS = $(SQLITE3_LIBS) -lbz2 $(LIBCURL_LIBS) $(SODIUM_LIBS) -laws-cpp-sdk-s3 -laws-cpp-sdk-core -pthread
 
 ifeq ($(OS), SunOS)
 	libstore_LDFLAGS += -lsocket
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index 12472f017ce4..5c284d1b9ab2 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -35,12 +35,13 @@ void Store::computeFSClosure(const Path & path,
         if (includeDerivers && isDerivation(path)) {
             PathSet outputs = queryDerivationOutputs(path);
             for (auto & i : outputs)
-                if (isValidPath(i) && queryDeriver(i) == path)
+                if (isValidPath(i) && queryPathInfo(i)->deriver == path)
                     edges.insert(i);
         }
 
     } else {
-        queryReferences(path, edges);
+        auto info = queryPathInfo(path);
+        edges = info->references;
 
         if (includeOutputs && isDerivation(path)) {
             PathSet outputs = queryDerivationOutputs(path);
@@ -48,10 +49,8 @@ void Store::computeFSClosure(const Path & path,
                 if (isValidPath(i)) edges.insert(i);
         }
 
-        if (includeDerivers) {
-            Path deriver = queryDeriver(path);
-            if (isValidPath(deriver)) edges.insert(deriver);
-        }
+        if (includeDerivers && isValidPath(info->deriver))
+            edges.insert(info->deriver);
     }
 
     for (auto & i : edges)
@@ -189,8 +188,10 @@ Paths Store::topoSortPaths(const PathSet & paths)
         parents.insert(path);
 
         PathSet references;
-        if (isValidPath(path))
-            queryReferences(path, references);
+        try {
+            references = queryPathInfo(path)->references;
+        } catch (InvalidPath &) {
+        }
 
         for (auto & i : references)
             /* Don't traverse into paths that don't exist.  That can
diff --git a/src/libstore/nar-info-disk-cache.cc b/src/libstore/nar-info-disk-cache.cc
new file mode 100644
index 000000000000..d8b0815bf757
--- /dev/null
+++ b/src/libstore/nar-info-disk-cache.cc
@@ -0,0 +1,224 @@
+#include "nar-info-disk-cache.hh"
+#include "sync.hh"
+#include "sqlite.hh"
+#include "globals.hh"
+
+#include <sqlite3.h>
+
+namespace nix {
+
+static const char * schema = R"sql(
+
+create table if not exists BinaryCaches (
+    id        integer primary key autoincrement not null,
+    url       text unique not null,
+    timestamp integer not null,
+    storeDir  text not null,
+    wantMassQuery integer not null,
+    priority  integer not null
+);
+
+create table if not exists NARs (
+    cache            integer not null,
+    hashPart         text not null,
+    namePart         text not null,
+    url              text,
+    compression      text,
+    fileHash         text,
+    fileSize         integer,
+    narHash          text,
+    narSize          integer,
+    refs             text,
+    deriver          text,
+    sigs             text,
+    timestamp        integer not null,
+    primary key (cache, hashPart),
+    foreign key (cache) references BinaryCaches(id) on delete cascade
+);
+
+create table if not exists NARExistence (
+    cache            integer not null,
+    storePath        text not null,
+    exist            integer not null,
+    timestamp        integer not null,
+    primary key (cache, storePath),
+    foreign key (cache) references BinaryCaches(id) on delete cascade
+);
+
+)sql";
+
+class NarInfoDiskCacheImpl : public NarInfoDiskCache
+{
+public:
+
+    /* How long negative lookups are valid. */
+    const int ttlNegative = 3600;
+
+    struct State
+    {
+        SQLite db;
+        SQLiteStmt insertCache, queryCache, insertNAR, queryNAR, insertNARExistence, queryNARExistence;
+        std::map<std::string, int> caches;
+    };
+
+    Sync<State> _state;
+
+    NarInfoDiskCacheImpl()
+    {
+        auto state(_state.lock());
+
+        Path dbPath = getCacheDir() + "/nix/binary-cache-v4.sqlite";
+        createDirs(dirOf(dbPath));
+
+        if (sqlite3_open_v2(dbPath.c_str(), &state->db.db,
+                SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE, 0) != SQLITE_OK)
+            throw Error(format("cannot open store cache ‘%s’") % dbPath);
+
+        if (sqlite3_busy_timeout(state->db, 60 * 60 * 1000) != SQLITE_OK)
+            throwSQLiteError(state->db, "setting timeout");
+
+        // We can always reproduce the cache.
+        if (sqlite3_exec(state->db, "pragma synchronous = off", 0, 0, 0) != SQLITE_OK)
+            throwSQLiteError(state->db, "making database asynchronous");
+        if (sqlite3_exec(state->db, "pragma main.journal_mode = truncate", 0, 0, 0) != SQLITE_OK)
+            throwSQLiteError(state->db, "setting journal mode");
+
+        if (sqlite3_exec(state->db, schema, 0, 0, 0) != SQLITE_OK)
+            throwSQLiteError(state->db, "initialising database schema");
+
+        state->insertCache.create(state->db,
+            "insert or replace into BinaryCaches(url, timestamp, storeDir, wantMassQuery, priority) values (?, ?, ?, ?, ?)");
+
+        state->queryCache.create(state->db,
+            "select id, storeDir, wantMassQuery, priority from BinaryCaches where url = ?");
+
+        state->insertNAR.create(state->db,
+            "insert or replace into NARs(cache, hashPart, namePart, url, compression, fileHash, fileSize, narHash, "
+            "narSize, refs, deriver, sigs, timestamp) values (?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?)");
+
+        state->queryNAR.create(state->db,
+            "select * from NARs where cache = ? and hashPart = ?");
+
+        state->insertNARExistence.create(state->db,
+            "insert or replace into NARExistence(cache, storePath, exist, timestamp) values (?, ?, ?, ?)");
+
+        state->queryNARExistence.create(state->db,
+            "select exist, timestamp from NARExistence where cache = ? and storePath = ?");
+    }
+
+    int uriToInt(State & state, const std::string & uri)
+    {
+        auto i = state.caches.find(uri);
+        if (i == state.caches.end()) abort();
+        return i->second;
+    }
+
+    void createCache(const std::string & uri) override
+    {
+        auto state(_state.lock());
+
+        // FIXME: race
+
+        state->insertCache.use()(uri)(time(0))(settings.nixStore)(1)(0).exec();
+        assert(sqlite3_changes(state->db) == 1);
+        state->caches[uri] = sqlite3_last_insert_rowid(state->db);
+    }
+
+    bool cacheExists(const std::string & uri) override
+    {
+        auto state(_state.lock());
+
+        auto i = state->caches.find(uri);
+        if (i != state->caches.end()) return true;
+
+        auto queryCache(state->queryCache.use()(uri));
+
+        if (queryCache.next()) {
+            state->caches[uri] = queryCache.getInt(0);
+            return true;
+        }
+
+        return false;
+    }
+
+    std::pair<Outcome, std::shared_ptr<NarInfo>> lookupNarInfo(
+        const std::string & uri, const std::string & hashPart) override
+    {
+        auto state(_state.lock());
+
+        auto queryNAR(state->queryNAR.use()
+            (uriToInt(*state, uri))
+            (hashPart));
+
+        if (!queryNAR.next())
+            // FIXME: check NARExistence
+            return {oUnknown, 0};
+
+        auto narInfo = make_ref<NarInfo>();
+
+        // FIXME: implement TTL.
+
+        auto namePart = queryNAR.getStr(2);
+        narInfo->path = settings.nixStore + "/" +
+            hashPart + (namePart.empty() ? "" : "-" + namePart);
+        narInfo->url = queryNAR.getStr(3);
+        narInfo->compression = queryNAR.getStr(4);
+        if (!queryNAR.isNull(5))
+            narInfo->fileHash = parseHash(queryNAR.getStr(5));
+        narInfo->fileSize = queryNAR.getInt(6);
+        narInfo->narHash = parseHash(queryNAR.getStr(7));
+        narInfo->narSize = queryNAR.getInt(8);
+        for (auto & r : tokenizeString<Strings>(queryNAR.getStr(9), " "))
+            narInfo->references.insert(settings.nixStore + "/" + r);
+        if (!queryNAR.isNull(10))
+            narInfo->deriver = settings.nixStore + "/" + queryNAR.getStr(10);
+        for (auto & sig : tokenizeString<Strings>(queryNAR.getStr(11), " "))
+            narInfo->sigs.insert(sig);
+
+        return {oValid, narInfo};
+    }
+
+    void upsertNarInfo(
+        const std::string & uri, const std::string & hashPart,
+        std::shared_ptr<ValidPathInfo> info) override
+    {
+        auto state(_state.lock());
+
+        if (info) {
+
+            auto narInfo = std::dynamic_pointer_cast<NarInfo>(info);
+
+            assert(hashPart == storePathToHash(info->path));
+
+            state->insertNAR.use()
+                (uriToInt(*state, uri))
+                (hashPart)
+                (storePathToName(info->path))
+                (narInfo ? narInfo->url : "", narInfo != 0)
+                (narInfo ? narInfo->compression : "", narInfo != 0)
+                (narInfo && narInfo->fileHash ? narInfo->fileHash.to_string() : "", narInfo && narInfo->fileHash)
+                (narInfo ? narInfo->fileSize : 0, narInfo != 0 && narInfo->fileSize)
+                (info->narHash.to_string())
+                (info->narSize)
+                (concatStringsSep(" ", info->shortRefs()))
+                (info->deriver != "" ? baseNameOf(info->deriver) : "", info->deriver != "")
+                (concatStringsSep(" ", info->sigs))
+                (time(0)).exec();
+
+        } else {
+            // not implemented
+            abort();
+        }
+    }
+};
+
+ref<NarInfoDiskCache> getNarInfoDiskCache()
+{
+    static Sync<std::shared_ptr<NarInfoDiskCache>> cache;
+
+    auto cache_(cache.lock());
+    if (!*cache_) *cache_ = std::make_shared<NarInfoDiskCacheImpl>();
+    return ref<NarInfoDiskCache>(*cache_);
+}
+
+}
diff --git a/src/libstore/nar-info-disk-cache.hh b/src/libstore/nar-info-disk-cache.hh
new file mode 100644
index 000000000000..f4e3fbbdcbdc
--- /dev/null
+++ b/src/libstore/nar-info-disk-cache.hh
@@ -0,0 +1,29 @@
+#pragma once
+
+#include "ref.hh"
+#include "nar-info.hh"
+
+namespace nix {
+
+class NarInfoDiskCache
+{
+public:
+    typedef enum { oValid, oInvalid, oUnknown } Outcome;
+
+    virtual void createCache(const std::string & uri) = 0;
+
+    virtual bool cacheExists(const std::string & uri) = 0;
+
+    virtual std::pair<Outcome, std::shared_ptr<NarInfo>> lookupNarInfo(
+        const std::string & uri, const std::string & hashPart) = 0;
+
+    virtual void upsertNarInfo(
+        const std::string & uri, const std::string & hashPart,
+        std::shared_ptr<ValidPathInfo> info) = 0;
+};
+
+/* Return a singleton cache object that can be used concurrently by
+   multiple threads. */
+ref<NarInfoDiskCache> getNarInfoDiskCache();
+
+}
diff --git a/src/libstore/nar-info.cc b/src/libstore/nar-info.cc
index 680facdcfeb8..c0c5cecd1730 100644
--- a/src/libstore/nar-info.cc
+++ b/src/libstore/nar-info.cc
@@ -5,16 +5,16 @@ namespace nix {
 
 NarInfo::NarInfo(const std::string & s, const std::string & whence)
 {
-    auto corrupt = [&]() {
+    auto corrupt = [&]() [[noreturn]] {
         throw Error("NAR info file ‘%1%’ is corrupt");
     };
 
     auto parseHashField = [&](const string & s) {
-        string::size_type colon = s.find(':');
-        if (colon == string::npos) corrupt();
-        HashType ht = parseHashType(string(s, 0, colon));
-        if (ht == htUnknown) corrupt();
-        return parseHash16or32(ht, string(s, colon + 1));
+        try {
+            return parseHash(s);
+        } catch (BadHash &) {
+            corrupt();
+        }
     };
 
     size_t pos = 0;
@@ -103,12 +103,4 @@ std::string NarInfo::to_string() const
     return res;
 }
 
-Strings NarInfo::shortRefs() const
-{
-    Strings refs;
-    for (auto & r : references)
-        refs.push_back(baseNameOf(r));
-    return refs;
-}
-
 }
diff --git a/src/libstore/nar-info.hh b/src/libstore/nar-info.hh
index 3c783cf83fef..6bc2f03b139b 100644
--- a/src/libstore/nar-info.hh
+++ b/src/libstore/nar-info.hh
@@ -19,10 +19,6 @@ struct NarInfo : ValidPathInfo
     NarInfo(const std::string & s, const std::string & whence);
 
     std::string to_string() const;
-
-private:
-
-    Strings shortRefs() const;
 };
 
 }
diff --git a/src/libstore/optimise-store.cc b/src/libstore/optimise-store.cc
index 23cbe7e26b47..ad7fe0e8bebf 100644
--- a/src/libstore/optimise-store.cc
+++ b/src/libstore/optimise-store.cc
@@ -228,7 +228,7 @@ void LocalStore::optimiseStore(OptimiseStats & stats)
     for (auto & i : paths) {
         addTempRoot(i);
         if (!isValidPath(i)) continue; /* path was GC'ed, probably */
-        startNest(nest, lvlChatty, format("hashing files in ‘%1%’") % i);
+        Activity act(*logger, lvlChatty, format("hashing files in ‘%1%’") % i);
         optimisePath_(stats, i, inodeHash);
     }
 }
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index 761e835481a8..5a254a6104f4 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -49,6 +49,12 @@ RemoteStore::RemoteStore(size_t maxConnections)
 }
 
 
+std::string RemoteStore::getUri()
+{
+    return "daemon";
+}
+
+
 ref<RemoteStore::Connection> RemoteStore::openConnection()
 {
     auto conn = make_ref<Connection>();
@@ -120,9 +126,9 @@ void RemoteStore::setOptions(ref<Connection> conn)
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 2)
         conn->to << settings.useBuildHook;
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 4)
-        conn->to << settings.buildVerbosity
-           << logType
-           << settings.printBuildTrace;
+        conn->to << (settings.verboseBuild ? lvlError : lvlVomit)
+                 << 0 // obsolete log type
+                 << 0 /* obsolete print build trace */;
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 6)
         conn->to << settings.buildCores;
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 10)
@@ -141,7 +147,7 @@ void RemoteStore::setOptions(ref<Connection> conn)
 }
 
 
-bool RemoteStore::isValidPath(const Path & path)
+bool RemoteStore::isValidPathUncached(const Path & path)
 {
     auto conn(connections->get());
     conn->to << wopIsValidPath << path;
@@ -239,48 +245,38 @@ void RemoteStore::querySubstitutablePathInfos(const PathSet & paths,
 }
 
 
-ValidPathInfo RemoteStore::queryPathInfo(const Path & path)
+std::shared_ptr<ValidPathInfo> RemoteStore::queryPathInfoUncached(const Path & path)
 {
     auto conn(connections->get());
     conn->to << wopQueryPathInfo << path;
-    conn->processStderr();
-    ValidPathInfo info;
-    info.path = path;
-    info.deriver = readString(conn->from);
-    if (info.deriver != "") assertStorePath(info.deriver);
-    info.narHash = parseHash(htSHA256, readString(conn->from));
-    info.references = readStorePaths<PathSet>(conn->from);
-    info.registrationTime = readInt(conn->from);
-    info.narSize = readLongLong(conn->from);
+    try {
+        conn->processStderr();
+    } catch (Error & e) {
+        // Ugly backwards compatibility hack.
+        if (e.msg().find("is not valid") != std::string::npos)
+            throw InvalidPath(e.what());
+        throw;
+    }
+    if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 17) {
+        bool valid = readInt(conn->from) != 0;
+        if (!valid) throw InvalidPath(format("path ‘%s’ is not valid") % path);
+    }
+    auto info = std::make_shared<ValidPathInfo>();
+    info->path = path;
+    info->deriver = readString(conn->from);
+    if (info->deriver != "") assertStorePath(info->deriver);
+    info->narHash = parseHash(htSHA256, readString(conn->from));
+    info->references = readStorePaths<PathSet>(conn->from);
+    info->registrationTime = readInt(conn->from);
+    info->narSize = readLongLong(conn->from);
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 16) {
-        info.ultimate = readInt(conn->from) != 0;
-        info.sigs = readStrings<StringSet>(conn->from);
+        info->ultimate = readInt(conn->from) != 0;
+        info->sigs = readStrings<StringSet>(conn->from);
     }
     return info;
 }
 
 
-Hash RemoteStore::queryPathHash(const Path & path)
-{
-    auto conn(connections->get());
-    conn->to << wopQueryPathHash << path;
-    conn->processStderr();
-    string hash = readString(conn->from);
-    return parseHash(htSHA256, hash);
-}
-
-
-void RemoteStore::queryReferences(const Path & path,
-    PathSet & references)
-{
-    auto conn(connections->get());
-    conn->to << wopQueryReferences << path;
-    conn->processStderr();
-    PathSet references2 = readStorePaths<PathSet>(conn->from);
-    references.insert(references2.begin(), references2.end());
-}
-
-
 void RemoteStore::queryReferrers(const Path & path,
     PathSet & referrers)
 {
@@ -292,17 +288,6 @@ void RemoteStore::queryReferrers(const Path & path,
 }
 
 
-Path RemoteStore::queryDeriver(const Path & path)
-{
-    auto conn(connections->get());
-    conn->to << wopQueryDeriver << path;
-    conn->processStderr();
-    Path drvPath = readString(conn->from);
-    if (drvPath != "") assertStorePath(drvPath);
-    return drvPath;
-}
-
-
 PathSet RemoteStore::queryValidDerivers(const Path & path)
 {
     auto conn(connections->get());
@@ -517,6 +502,11 @@ void RemoteStore::collectGarbage(const GCOptions & options, GCResults & results)
     results.paths = readStrings<PathSet>(conn->from);
     results.bytesFreed = readLongLong(conn->from);
     readLongLong(conn->from); // obsolete
+
+    {
+        auto state_(Store::state.lock());
+        state_->pathInfoCache.clear();
+    }
 }
 
 
@@ -577,10 +567,8 @@ void RemoteStore::Connection::processStderr(Sink * sink, Source * source)
             writeString(buf, source->read(buf, len), to);
             to.flush();
         }
-        else {
-            string s = readString(from);
-            writeToStderr(s);
-        }
+        else
+            printMsg(lvlError, chomp(readString(from)));
     }
     if (msg == STDERR_ERROR) {
         string error = readString(from);
diff --git a/src/libstore/remote-store.hh b/src/libstore/remote-store.hh
index 45bc41804ccf..8e45a7449e2e 100644
--- a/src/libstore/remote-store.hh
+++ b/src/libstore/remote-store.hh
@@ -26,22 +26,18 @@ public:
 
     /* Implementations of abstract store API methods. */
 
-    bool isValidPath(const Path & path) override;
+    std::string getUri() override;
+
+    bool isValidPathUncached(const Path & path) override;
 
     PathSet queryValidPaths(const PathSet & paths) override;
 
     PathSet queryAllValidPaths() override;
 
-    ValidPathInfo queryPathInfo(const Path & path) override;
-
-    Hash queryPathHash(const Path & path) override;
-
-    void queryReferences(const Path & path, PathSet & references) override;
+    std::shared_ptr<ValidPathInfo> queryPathInfoUncached(const Path & path) override;
 
     void queryReferrers(const Path & path, PathSet & referrers) override;
 
-    Path queryDeriver(const Path & path) override;
-
     PathSet queryValidDerivers(const Path & path) override;
 
     PathSet queryDerivationOutputs(const Path & path) override;
diff --git a/src/libstore/s3-binary-cache-store.cc b/src/libstore/s3-binary-cache-store.cc
new file mode 100644
index 000000000000..cffcb1bf214f
--- /dev/null
+++ b/src/libstore/s3-binary-cache-store.cc
@@ -0,0 +1,253 @@
+#include "s3-binary-cache-store.hh"
+#include "nar-info.hh"
+#include "nar-info-disk-cache.hh"
+#include "globals.hh"
+
+#include <aws/core/client/ClientConfiguration.h>
+#include <aws/s3/S3Client.h>
+#include <aws/s3/model/CreateBucketRequest.h>
+#include <aws/s3/model/GetBucketLocationRequest.h>
+#include <aws/s3/model/GetObjectRequest.h>
+#include <aws/s3/model/HeadObjectRequest.h>
+#include <aws/s3/model/PutObjectRequest.h>
+#include <aws/s3/model/ListObjectsRequest.h>
+
+namespace nix {
+
+struct S3Error : public Error
+{
+    Aws::S3::S3Errors err;
+    S3Error(Aws::S3::S3Errors err, const FormatOrString & fs)
+        : Error(fs), err(err) { };
+};
+
+/* Helper: given an Outcome<R, E>, return R in case of success, or
+   throw an exception in case of an error. */
+template<typename R, typename E>
+R && checkAws(const FormatOrString & fs, Aws::Utils::Outcome<R, E> && outcome)
+{
+    if (!outcome.IsSuccess())
+        throw S3Error(
+            outcome.GetError().GetErrorType(),
+            fs.s + ": " + outcome.GetError().GetMessage());
+    return outcome.GetResultWithOwnership();
+}
+
+struct S3BinaryCacheStoreImpl : public S3BinaryCacheStore
+{
+    std::string bucketName;
+
+    ref<Aws::Client::ClientConfiguration> config;
+    ref<Aws::S3::S3Client> client;
+
+    Stats stats;
+
+    S3BinaryCacheStoreImpl(std::shared_ptr<Store> localStore,
+        const StoreParams & params, const std::string & bucketName)
+        : S3BinaryCacheStore(localStore, params)
+        , bucketName(bucketName)
+        , config(makeConfig())
+        , client(make_ref<Aws::S3::S3Client>(*config))
+    {
+        diskCache = getNarInfoDiskCache();
+    }
+
+    std::string getUri()
+    {
+        return "s3://" + bucketName;
+    }
+
+    ref<Aws::Client::ClientConfiguration> makeConfig()
+    {
+        auto res = make_ref<Aws::Client::ClientConfiguration>();
+        res->region = Aws::Region::US_EAST_1; // FIXME: make configurable
+        res->requestTimeoutMs = 600 * 1000;
+        return res;
+    }
+
+    void init()
+    {
+        if (!diskCache->cacheExists(getUri())) {
+
+            /* Create the bucket if it doesn't already exists. */
+            // FIXME: HeadBucket would be more appropriate, but doesn't return
+            // an easily parsed 404 message.
+            auto res = client->GetBucketLocation(
+                Aws::S3::Model::GetBucketLocationRequest().WithBucket(bucketName));
+
+            if (!res.IsSuccess()) {
+                if (res.GetError().GetErrorType() != Aws::S3::S3Errors::NO_SUCH_BUCKET)
+                    throw Error(format("AWS error checking bucket ‘%s’: %s") % bucketName % res.GetError().GetMessage());
+
+                checkAws(format("AWS error creating bucket ‘%s’") % bucketName,
+                    client->CreateBucket(
+                        Aws::S3::Model::CreateBucketRequest()
+                        .WithBucket(bucketName)
+                        .WithCreateBucketConfiguration(
+                            Aws::S3::Model::CreateBucketConfiguration()
+                            /* .WithLocationConstraint(
+                               Aws::S3::Model::BucketLocationConstraint::US) */ )));
+            }
+
+            BinaryCacheStore::init();
+
+            diskCache->createCache(getUri());
+        }
+    }
+
+    const Stats & getS3Stats()
+    {
+        return stats;
+    }
+
+    /* This is a specialisation of isValidPath() that optimistically
+       fetches the .narinfo file, rather than first checking for its
+       existence via a HEAD request. Since .narinfos are small, doing
+       a GET is unlikely to be slower than HEAD. */
+    bool isValidPathUncached(const Path & storePath)
+    {
+        try {
+            queryPathInfo(storePath);
+            return true;
+        } catch (InvalidPath & e) {
+            return false;
+        }
+    }
+
+    bool fileExists(const std::string & path)
+    {
+        stats.head++;
+
+        auto res = client->HeadObject(
+            Aws::S3::Model::HeadObjectRequest()
+            .WithBucket(bucketName)
+            .WithKey(path));
+
+        if (!res.IsSuccess()) {
+            auto & error = res.GetError();
+            if (error.GetErrorType() == Aws::S3::S3Errors::UNKNOWN // FIXME
+                && error.GetMessage().find("404") != std::string::npos)
+                return false;
+            throw Error(format("AWS error fetching ‘%s’: %s") % path % error.GetMessage());
+        }
+
+        return true;
+    }
+
+    void upsertFile(const std::string & path, const std::string & data)
+    {
+        auto request =
+            Aws::S3::Model::PutObjectRequest()
+            .WithBucket(bucketName)
+            .WithKey(path);
+
+        auto stream = std::make_shared<std::stringstream>(data);
+
+        request.SetBody(stream);
+
+        stats.put++;
+        stats.putBytes += data.size();
+
+        auto now1 = std::chrono::steady_clock::now();
+
+        auto result = checkAws(format("AWS error uploading ‘%s’") % path,
+            client->PutObject(request));
+
+        auto now2 = std::chrono::steady_clock::now();
+
+        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now2 - now1).count();
+
+        printMsg(lvlInfo, format("uploaded ‘s3://%1%/%2%’ (%3% bytes) in %4% ms")
+            % bucketName % path % data.size() % duration);
+
+        stats.putTimeMs += duration;
+    }
+
+    std::shared_ptr<std::string> getFile(const std::string & path)
+    {
+        debug(format("fetching ‘s3://%1%/%2%’...") % bucketName % path);
+
+        auto request =
+            Aws::S3::Model::GetObjectRequest()
+            .WithBucket(bucketName)
+            .WithKey(path);
+
+        request.SetResponseStreamFactory([&]() {
+            return Aws::New<std::stringstream>("STRINGSTREAM");
+        });
+
+        stats.get++;
+
+        try {
+
+            auto now1 = std::chrono::steady_clock::now();
+
+            auto result = checkAws(format("AWS error fetching ‘%s’") % path,
+                client->GetObject(request));
+
+            auto now2 = std::chrono::steady_clock::now();
+
+            auto res = dynamic_cast<std::stringstream &>(result.GetBody()).str();
+
+            auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now2 - now1).count();
+
+            printMsg(lvlTalkative, format("downloaded ‘s3://%1%/%2%’ (%3% bytes) in %4% ms")
+                % bucketName % path % res.size() % duration);
+
+            stats.getBytes += res.size();
+            stats.getTimeMs += duration;
+
+            return std::make_shared<std::string>(res);
+
+        } catch (S3Error & e) {
+            if (e.err == Aws::S3::S3Errors::NO_SUCH_KEY) return 0;
+            throw;
+        }
+    }
+
+    PathSet queryAllValidPaths() override
+    {
+        PathSet paths;
+        std::string marker;
+
+        do {
+            debug(format("listing bucket ‘s3://%s’ from key ‘%s’...") % bucketName % marker);
+
+            auto res = checkAws(format("AWS error listing bucket ‘%s’") % bucketName,
+                client->ListObjects(
+                    Aws::S3::Model::ListObjectsRequest()
+                    .WithBucket(bucketName)
+                    .WithDelimiter("/")
+                    .WithMarker(marker)));
+
+            auto & contents = res.GetContents();
+
+            debug(format("got %d keys, next marker ‘%s’")
+                % contents.size() % res.GetNextMarker());
+
+            for (auto object : contents) {
+                auto & key = object.GetKey();
+                if (key.size() != 40 || !hasSuffix(key, ".narinfo")) continue;
+                paths.insert(settings.nixStore + "/" + key.substr(0, key.size() - 8));
+            }
+
+            marker = res.GetNextMarker();
+        } while (!marker.empty());
+
+        return paths;
+    }
+
+};
+
+static RegisterStoreImplementation regStore([](
+    const std::string & uri, const StoreParams & params)
+    -> std::shared_ptr<Store>
+{
+    if (std::string(uri, 0, 5) != "s3://") return 0;
+    auto store = std::make_shared<S3BinaryCacheStoreImpl>(std::shared_ptr<Store>(0),
+        params, std::string(uri, 5));
+    store->init();
+    return store;
+});
+
+}
diff --git a/src/libstore/s3-binary-cache-store.hh b/src/libstore/s3-binary-cache-store.hh
new file mode 100644
index 000000000000..2751a9d01cdb
--- /dev/null
+++ b/src/libstore/s3-binary-cache-store.hh
@@ -0,0 +1,34 @@
+#pragma once
+
+#include "binary-cache-store.hh"
+
+#include <atomic>
+
+namespace nix {
+
+class S3BinaryCacheStore : public BinaryCacheStore
+{
+protected:
+
+    S3BinaryCacheStore(std::shared_ptr<Store> localStore,
+        const StoreParams & params)
+        : BinaryCacheStore(localStore, params)
+    { }
+
+public:
+
+    struct Stats
+    {
+        std::atomic<uint64_t> put{0};
+        std::atomic<uint64_t> putBytes{0};
+        std::atomic<uint64_t> putTimeMs{0};
+        std::atomic<uint64_t> get{0};
+        std::atomic<uint64_t> getBytes{0};
+        std::atomic<uint64_t> getTimeMs{0};
+        std::atomic<uint64_t> head{0};
+    };
+
+    const Stats & getS3Stats();
+};
+
+}
diff --git a/src/libstore/sqlite.cc b/src/libstore/sqlite.cc
index f93fa0857588..816f9984d6eb 100644
--- a/src/libstore/sqlite.cc
+++ b/src/libstore/sqlite.cc
@@ -139,6 +139,11 @@ int64_t SQLiteStmt::Use::getInt(int col)
     return sqlite3_column_int64(stmt, col);
 }
 
+bool SQLiteStmt::Use::isNull(int col)
+{
+    return sqlite3_column_type(stmt, col) == SQLITE_NULL;
+}
+
 SQLiteTxn::SQLiteTxn(sqlite3 * db)
 {
     this->db = db;
diff --git a/src/libstore/sqlite.hh b/src/libstore/sqlite.hh
index 326e4a4855b7..d6b4a8d9117b 100644
--- a/src/libstore/sqlite.hh
+++ b/src/libstore/sqlite.hh
@@ -58,6 +58,7 @@ struct SQLiteStmt
 
         std::string getStr(int col);
         int64_t getInt(int col);
+        bool isNull(int col);
     };
 
     Use use()
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index cc91ed287768..463e132e0299 100644
--- a/src/libstore/store-api.cc
+++ b/src/libstore/store-api.cc
@@ -2,6 +2,7 @@
 #include "globals.hh"
 #include "store-api.hh"
 #include "util.hh"
+#include "nar-info-disk-cache.hh"
 
 
 namespace nix {
@@ -16,6 +17,7 @@ bool isInStore(const Path & path)
 bool isStorePath(const Path & path)
 {
     return isInStore(path)
+        && path.size() >= settings.nixStore.size() + 1 + storePathHashLen
         && path.find('/', settings.nixStore.size() + 1) == Path::npos;
 }
 
@@ -62,13 +64,16 @@ Path followLinksToStorePath(const Path & path)
 string storePathToName(const Path & path)
 {
     assertStorePath(path);
-    return string(path, settings.nixStore.size() + storePathHashLen + 2);
+    auto l = settings.nixStore.size() + 1 + storePathHashLen;
+    assert(path.size() >= l);
+    return path.size() == l ? "" : string(path, l + 1);
 }
 
 
 string storePathToHash(const Path & path)
 {
     assertStorePath(path);
+    assert(path.size() >= settings.nixStore.size() + 1 + storePathHashLen);
     return string(path, settings.nixStore.size() + 1, storePathHashLen);
 }
 
@@ -225,10 +230,89 @@ Path computeStorePathForText(const string & name, const string & s,
 }
 
 
-void Store::queryReferences(const Path & path, PathSet & references)
+std::string Store::getUri()
 {
-    ValidPathInfo info = queryPathInfo(path);
-    references.insert(info.references.begin(), info.references.end());
+    return "";
+}
+
+
+bool Store::isValidPath(const Path & storePath)
+{
+    auto hashPart = storePathToHash(storePath);
+
+    {
+        auto state_(state.lock());
+        auto res = state_->pathInfoCache.get(hashPart);
+        if (res) {
+            stats.narInfoReadAverted++;
+            return *res != 0;
+        }
+    }
+
+    if (diskCache) {
+        auto res = diskCache->lookupNarInfo(getUri(), hashPart);
+        if (res.first != NarInfoDiskCache::oUnknown) {
+            stats.narInfoReadAverted++;
+            auto state_(state.lock());
+            state_->pathInfoCache.upsert(hashPart,
+                res.first == NarInfoDiskCache::oInvalid ? 0 : res.second);
+            return res.first == NarInfoDiskCache::oValid;
+        }
+    }
+
+    return isValidPathUncached(storePath);
+
+    // FIXME: insert result into NARExistence table of diskCache.
+}
+
+
+ref<const ValidPathInfo> Store::queryPathInfo(const Path & storePath)
+{
+    auto hashPart = storePathToHash(storePath);
+
+    {
+        auto state_(state.lock());
+        auto res = state_->pathInfoCache.get(hashPart);
+        if (res) {
+            stats.narInfoReadAverted++;
+            if (!*res)
+                throw InvalidPath(format("path ‘%s’ is not valid") % storePath);
+            return ref<ValidPathInfo>(*res);
+        }
+    }
+
+    if (diskCache) {
+        auto res = diskCache->lookupNarInfo(getUri(), hashPart);
+        if (res.first != NarInfoDiskCache::oUnknown) {
+            stats.narInfoReadAverted++;
+            auto state_(state.lock());
+            state_->pathInfoCache.upsert(hashPart,
+                res.first == NarInfoDiskCache::oInvalid ? 0 : res.second);
+            if (res.first == NarInfoDiskCache::oInvalid ||
+                (res.second->path != storePath && storePathToName(storePath) != ""))
+                throw InvalidPath(format("path ‘%s’ is not valid") % storePath);
+            return ref<ValidPathInfo>(res.second);
+        }
+    }
+
+    auto info = queryPathInfoUncached(storePath);
+
+    if (diskCache && info)
+        diskCache->upsertNarInfo(getUri(), hashPart, info);
+
+    {
+        auto state_(state.lock());
+        state_->pathInfoCache.upsert(hashPart, info);
+    }
+
+    if (!info
+        || (info->path != storePath && storePathToName(storePath) != ""))
+    {
+        stats.narInfoMissing++;
+        throw InvalidPath(format("path ‘%s’ is not valid") % storePath);
+    }
+
+    return ref<ValidPathInfo>(info);
 }
 
 
@@ -243,19 +327,19 @@ string Store::makeValidityRegistration(const PathSet & paths,
     for (auto & i : paths) {
         s += i + "\n";
 
-        ValidPathInfo info = queryPathInfo(i);
+        auto info = queryPathInfo(i);
 
         if (showHash) {
-            s += printHash(info.narHash) + "\n";
-            s += (format("%1%\n") % info.narSize).str();
+            s += printHash(info->narHash) + "\n";
+            s += (format("%1%\n") % info->narSize).str();
         }
 
-        Path deriver = showDerivers ? info.deriver : "";
+        Path deriver = showDerivers ? info->deriver : "";
         s += deriver + "\n";
 
-        s += (format("%1%\n") % info.references.size()).str();
+        s += (format("%1%\n") % info->references.size()).str();
 
-        for (auto & j : info.references)
+        for (auto & j : info->references)
             s += j + "\n";
     }
 
@@ -263,6 +347,16 @@ string Store::makeValidityRegistration(const PathSet & paths,
 }
 
 
+const Store::Stats & Store::getStats()
+{
+    {
+        auto state_(state.lock());
+        stats.pathInfoCacheSize = state_->pathInfoCache.size();
+    }
+    return stats;
+}
+
+
 ValidPathInfo decodeValidPathInfo(std::istream & str, bool hashGiven)
 {
     ValidPathInfo info;
@@ -312,7 +406,7 @@ void Store::exportPaths(const Paths & paths,
 
 std::string ValidPathInfo::fingerprint() const
 {
-    if (narSize == 0 || narHash.type == htUnknown)
+    if (narSize == 0 || !narHash)
         throw Error(format("cannot calculate fingerprint of path ‘%s’ because its size/hash is not known")
             % path);
     return
@@ -345,6 +439,15 @@ bool ValidPathInfo::checkSignature(const PublicKeys & publicKeys, const std::str
 }
 
 
+Strings ValidPathInfo::shortRefs() const
+{
+    Strings refs;
+    for (auto & r : references)
+        refs.push_back(baseNameOf(r));
+    return refs;
+}
+
+
 }
 
 
@@ -358,10 +461,22 @@ namespace nix {
 RegisterStoreImplementation::Implementations * RegisterStoreImplementation::implementations = 0;
 
 
-ref<Store> openStoreAt(const std::string & uri)
+ref<Store> openStoreAt(const std::string & uri_)
 {
+    auto uri(uri_);
+    StoreParams params;
+    auto q = uri.find('?');
+    if (q != std::string::npos) {
+        for (auto s : tokenizeString<Strings>(uri.substr(q + 1), "&")) {
+            auto e = s.find('=');
+            if (e != std::string::npos)
+                params[s.substr(0, e)] = s.substr(e + 1);
+        }
+        uri = uri_.substr(0, q);
+    }
+
     for (auto fun : *RegisterStoreImplementation::implementations) {
-        auto store = fun(uri);
+        auto store = fun(uri, params);
         if (store) return ref<Store>(store);
     }
 
@@ -375,7 +490,10 @@ ref<Store> openStore()
 }
 
 
-static RegisterStoreImplementation regStore([](const std::string & uri) -> std::shared_ptr<Store> {
+static RegisterStoreImplementation regStore([](
+    const std::string & uri, const StoreParams & params)
+    -> std::shared_ptr<Store>
+{
     enum { mDaemon, mLocal, mAuto } mode;
 
     if (uri == "daemon") mode = mDaemon;
@@ -398,4 +516,39 @@ static RegisterStoreImplementation regStore([](const std::string & uri) -> std::
 });
 
 
+std::list<ref<Store>> getDefaultSubstituters()
+{
+    struct State {
+        bool done = false;
+        std::list<ref<Store>> stores;
+    };
+    static Sync<State> state_;
+
+    auto state(state_.lock());
+
+    if (state->done) return state->stores;
+
+    StringSet done;
+
+    auto addStore = [&](const std::string & uri) {
+        if (done.count(uri)) return;
+        done.insert(uri);
+        state->stores.push_back(openStoreAt(uri));
+    };
+
+    for (auto uri : settings.get("substituters", Strings()))
+        addStore(uri);
+
+    for (auto uri : settings.get("binary-caches", Strings()))
+        addStore(uri);
+
+    for (auto uri : settings.get("extra-binary-caches", Strings()))
+        addStore(uri);
+
+    state->done = true;
+
+    return state->stores;
+}
+
+
 }
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index 8827654fafdd..29685c9d1676 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -3,11 +3,14 @@
 #include "hash.hh"
 #include "serialise.hh"
 #include "crypto.hh"
+#include "lru-cache.hh"
+#include "sync.hh"
 
-#include <string>
+#include <atomic>
 #include <limits>
 #include <map>
 #include <memory>
+#include <string>
 
 
 namespace nix {
@@ -130,6 +133,10 @@ struct ValidPathInfo
 
     /* Verify a single signature. */
     bool checkSignature(const PublicKeys & publicKeys, const std::string & sig) const;
+
+    Strings shortRefs() const;
+
+    virtual ~ValidPathInfo() { }
 };
 
 typedef list<ValidPathInfo> ValidPathInfos;
@@ -165,42 +172,62 @@ struct BuildResult
 struct BasicDerivation;
 struct Derivation;
 class FSAccessor;
+class NarInfoDiskCache;
 
 
 class Store : public std::enable_shared_from_this<Store>
 {
+protected:
+
+    struct State
+    {
+        LRUCache<std::string, std::shared_ptr<ValidPathInfo>> pathInfoCache{64 * 1024};
+    };
+
+    Sync<State> state;
+
+    std::shared_ptr<NarInfoDiskCache> diskCache;
+
 public:
 
     virtual ~Store() { }
 
+    virtual std::string getUri() = 0;
+
     /* Check whether a path is valid. */
-    virtual bool isValidPath(const Path & path) = 0;
+    bool isValidPath(const Path & path);
+
+protected:
+
+    virtual bool isValidPathUncached(const Path & path) = 0;
+
+public:
 
     /* Query which of the given paths is valid. */
     virtual PathSet queryValidPaths(const PathSet & paths) = 0;
 
-    /* Query the set of all valid paths. */
+    /* Query the set of all valid paths. Note that for some store
+       backends, the name part of store paths may be omitted
+       (i.e. you'll get /nix/store/<hash> rather than
+       /nix/store/<hash>-<name>). Use queryPathInfo() to obtain the
+       full store path. */
     virtual PathSet queryAllValidPaths() = 0;
 
-    /* Query information about a valid path. */
-    virtual ValidPathInfo queryPathInfo(const Path & path) = 0;
+    /* Query information about a valid path. It is permitted to omit
+       the name part of the store path. */
+    ref<const ValidPathInfo> queryPathInfo(const Path & path);
+
+protected:
 
-    /* Query the hash of a valid path. */
-    virtual Hash queryPathHash(const Path & path) = 0;
+    virtual std::shared_ptr<ValidPathInfo> queryPathInfoUncached(const Path & path) = 0;
 
-    /* Query the set of outgoing FS references for a store path. The
-       result is not cleared. */
-    virtual void queryReferences(const Path & path, PathSet & references);
+public:
 
     /* 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;
 
-    /* Query the deriver of a store path.  Return the empty string if
-       no deriver has been set. */
-    virtual Path queryDeriver(const Path & path) = 0;
-
     /* 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
@@ -373,6 +400,29 @@ public:
        relation.  If p refers to q, then p preceeds q in this list. */
     Paths topoSortPaths(const PathSet & paths);
 
+    struct Stats
+    {
+        std::atomic<uint64_t> narInfoRead{0};
+        std::atomic<uint64_t> narInfoReadAverted{0};
+        std::atomic<uint64_t> narInfoMissing{0};
+        std::atomic<uint64_t> narInfoWrite{0};
+        std::atomic<uint64_t> pathInfoCacheSize{0};
+        std::atomic<uint64_t> narRead{0};
+        std::atomic<uint64_t> narReadBytes{0};
+        std::atomic<uint64_t> narReadCompressedBytes{0};
+        std::atomic<uint64_t> narWrite{0};
+        std::atomic<uint64_t> narWriteAverted{0};
+        std::atomic<uint64_t> narWriteBytes{0};
+        std::atomic<uint64_t> narWriteCompressedBytes{0};
+        std::atomic<uint64_t> narWriteCompressionTimeMs{0};
+    };
+
+    const Stats & getStats();
+
+protected:
+
+    Stats stats;
+
 };
 
 
@@ -479,12 +529,17 @@ ref<Store> openStoreAt(const std::string & uri);
 ref<Store> openStore();
 
 
-ref<Store> openLocalBinaryCacheStore(std::shared_ptr<Store> localStore,
-    const Path & secretKeyFile, const Path & binaryCacheDir);
+/* Return the default substituter stores, defined by the
+   ‘substituters’ option and various legacy options like
+   ‘binary-caches’. */
+std::list<ref<Store>> getDefaultSubstituters();
 
 
 /* Store implementation registration. */
-typedef std::function<std::shared_ptr<Store>(const std::string & uri)> OpenStore;
+typedef std::map<std::string, std::string> StoreParams;
+
+typedef std::function<std::shared_ptr<Store>(
+    const std::string & uri, const StoreParams & params)> OpenStore;
 
 struct RegisterStoreImplementation
 {
diff --git a/src/libstore/worker-protocol.hh b/src/libstore/worker-protocol.hh
index c10598d5d301..d133328d1e76 100644
--- a/src/libstore/worker-protocol.hh
+++ b/src/libstore/worker-protocol.hh
@@ -6,7 +6,7 @@ namespace nix {
 #define WORKER_MAGIC_1 0x6e697863
 #define WORKER_MAGIC_2 0x6478696f
 
-#define PROTOCOL_VERSION 0x110
+#define PROTOCOL_VERSION 0x111
 #define GET_PROTOCOL_MAJOR(x) ((x) & 0xff00)
 #define GET_PROTOCOL_MINOR(x) ((x) & 0x00ff)
 
@@ -14,8 +14,8 @@ namespace nix {
 typedef enum {
     wopIsValidPath = 1,
     wopHasSubstitutes = 3,
-    wopQueryPathHash = 4,
-    wopQueryReferences = 5,
+    wopQueryPathHash = 4, // obsolete
+    wopQueryReferences = 5, // obsolete
     wopQueryReferrers = 6,
     wopAddToStore = 7,
     wopAddTextToStore = 8,
@@ -26,7 +26,7 @@ typedef enum {
     wopSyncWithGC = 13,
     wopFindRoots = 14,
     wopExportPath = 16,
-    wopQueryDeriver = 18,
+    wopQueryDeriver = 18, // obsolete
     wopSetOptions = 19,
     wopCollectGarbage = 20,
     wopQuerySubstitutablePathInfo = 21,
diff --git a/src/libutil/args.cc b/src/libutil/args.cc
index 6e4b82a279ce..115484f9e6c7 100644
--- a/src/libutil/args.cc
+++ b/src/libutil/args.cc
@@ -71,10 +71,11 @@ void Args::printHelp(const string & programName, std::ostream & out)
 void Args::printFlags(std::ostream & out)
 {
     Table2 table;
-    for (auto & flags : longFlags)
+    for (auto & flag : longFlags)
         table.push_back(std::make_pair(
-                "--" + flags.first + renderLabels(flags.second.labels),
-                flags.second.description));
+                (flag.second.shortName ? std::string("-") + flag.second.shortName + ", " : "    ")
+                + "--" + flag.first + renderLabels(flag.second.labels),
+                flag.second.description));
     printTable(out, table);
 }
 
diff --git a/src/libutil/args.hh b/src/libutil/args.hh
index 4469a046d28a..6aa08aacac9e 100644
--- a/src/libutil/args.hh
+++ b/src/libutil/args.hh
@@ -29,6 +29,7 @@ protected:
     /* Flags. */
     struct Flag
     {
+        char shortName;
         std::string description;
         Strings labels;
         size_t arity;
@@ -63,7 +64,7 @@ public:
         const Strings & labels, const std::string & description,
         size_t arity, std::function<void(Strings)> handler)
     {
-        auto flag = Flag{description, labels, arity, handler};
+        auto flag = Flag{shortName, description, labels, arity, handler};
         if (shortName) shortFlags[shortName] = flag;
         longFlags[longName] = flag;
     }
diff --git a/src/libutil/compression.cc b/src/libutil/compression.cc
index b047d305cfa6..4d15d2acdd4e 100644
--- a/src/libutil/compression.cc
+++ b/src/libutil/compression.cc
@@ -1,88 +1,88 @@
 #include "compression.hh"
-#include "types.hh"
+#include "util.hh"
+#include "finally.hh"
 
 #include <lzma.h>
+#include <bzlib.h>
 #include <cstdio>
+#include <cstring>
 
 namespace nix {
 
-/* RAII wrapper around lzma_stream. */
-struct LzmaStream
+static ref<std::string> compressXZ(const std::string & in)
 {
     lzma_stream strm;
-    LzmaStream() : strm(LZMA_STREAM_INIT) { };
-    ~LzmaStream() { lzma_end(&strm); };
-    lzma_stream & operator()() { return strm; }
-};
-
-std::string compressXZ(const std::string & in)
-{
-    LzmaStream strm;
 
     // FIXME: apply the x86 BCJ filter?
 
     lzma_ret ret = lzma_easy_encoder(
-        &strm(), 6, LZMA_CHECK_CRC64);
+        &strm, 6, LZMA_CHECK_CRC64);
     if (ret != LZMA_OK)
         throw Error("unable to initialise lzma encoder");
 
+    Finally free([&]() { lzma_end(&strm); });
+
     lzma_action action = LZMA_RUN;
     uint8_t outbuf[BUFSIZ];
-    string res;
-    strm().next_in = (uint8_t *) in.c_str();
-    strm().avail_in = in.size();
-    strm().next_out = outbuf;
-    strm().avail_out = sizeof(outbuf);
+    ref<std::string> res = make_ref<std::string>();
+    strm.next_in = (uint8_t *) in.c_str();
+    strm.avail_in = in.size();
+    strm.next_out = outbuf;
+    strm.avail_out = sizeof(outbuf);
 
     while (true) {
+        checkInterrupt();
 
-        if (strm().avail_in == 0)
+        if (strm.avail_in == 0)
             action = LZMA_FINISH;
 
-        lzma_ret ret = lzma_code(&strm(), action);
+        lzma_ret ret = lzma_code(&strm, action);
 
-        if (strm().avail_out == 0 || ret == LZMA_STREAM_END) {
-            res.append((char *) outbuf, sizeof(outbuf) - strm().avail_out);
-            strm().next_out = outbuf;
-            strm().avail_out = sizeof(outbuf);
+        if (strm.avail_out == 0 || ret == LZMA_STREAM_END) {
+            res->append((char *) outbuf, sizeof(outbuf) - strm.avail_out);
+            strm.next_out = outbuf;
+            strm.avail_out = sizeof(outbuf);
         }
 
         if (ret == LZMA_STREAM_END)
             return res;
 
         if (ret != LZMA_OK)
-            throw Error("error while decompressing xz file");
+            throw Error("error while compressing xz file");
     }
 }
 
-ref<std::string> decompressXZ(const std::string & in)
+static ref<std::string> decompressXZ(const std::string & in)
 {
-    LzmaStream strm;
+    lzma_stream strm;
 
     lzma_ret ret = lzma_stream_decoder(
-        &strm(), UINT64_MAX, LZMA_CONCATENATED);
+        &strm, UINT64_MAX, LZMA_CONCATENATED);
     if (ret != LZMA_OK)
         throw Error("unable to initialise lzma decoder");
 
+    Finally free([&]() { lzma_end(&strm); });
+
     lzma_action action = LZMA_RUN;
     uint8_t outbuf[BUFSIZ];
     ref<std::string> res = make_ref<std::string>();
-    strm().next_in = (uint8_t *) in.c_str();
-    strm().avail_in = in.size();
-    strm().next_out = outbuf;
-    strm().avail_out = sizeof(outbuf);
+    strm.next_in = (uint8_t *) in.c_str();
+    strm.avail_in = in.size();
+    strm.next_out = outbuf;
+    strm.avail_out = sizeof(outbuf);
 
     while (true) {
+        checkInterrupt();
 
-        if (strm().avail_in == 0)
+        if (strm.avail_in == 0)
             action = LZMA_FINISH;
 
-        lzma_ret ret = lzma_code(&strm(), action);
+        lzma_ret ret = lzma_code(&strm, action);
 
-        if (strm().avail_out == 0 || ret == LZMA_STREAM_END) {
-            res->append((char *) outbuf, sizeof(outbuf) - strm().avail_out);
-            strm().next_out = outbuf;
-            strm().avail_out = sizeof(outbuf);
+        if (strm.avail_out == 0 || ret == LZMA_STREAM_END) {
+            res->append((char *) outbuf, sizeof(outbuf) - strm.avail_out);
+            strm.next_out = outbuf;
+            strm.avail_out = sizeof(outbuf);
         }
 
         if (ret == LZMA_STREAM_END)
@@ -93,4 +93,108 @@ ref<std::string> decompressXZ(const std::string & in)
     }
 }
 
+static ref<std::string> compressBzip2(const std::string & in)
+{
+    bz_stream strm;
+    memset(&strm, 0, sizeof(strm));
+
+    int ret = BZ2_bzCompressInit(&strm, 9, 0, 30);
+    if (ret != BZ_OK)
+        throw Error("unable to initialise bzip2 encoder");
+
+    Finally free([&]() { BZ2_bzCompressEnd(&strm); });
+
+    int action = BZ_RUN;
+    char outbuf[BUFSIZ];
+    ref<std::string> res = make_ref<std::string>();
+    strm.next_in = (char *) in.c_str();
+    strm.avail_in = in.size();
+    strm.next_out = outbuf;
+    strm.avail_out = sizeof(outbuf);
+
+    while (true) {
+        checkInterrupt();
+
+        if (strm.avail_in == 0)
+            action = BZ_FINISH;
+
+        int ret = BZ2_bzCompress(&strm, action);
+
+        if (strm.avail_out == 0 || ret == BZ_STREAM_END) {
+            res->append(outbuf, sizeof(outbuf) - strm.avail_out);
+            strm.next_out = outbuf;
+            strm.avail_out = sizeof(outbuf);
+        }
+
+        if (ret == BZ_STREAM_END)
+            return res;
+
+        if (ret != BZ_OK && ret != BZ_FINISH_OK)
+             Error("error while compressing bzip2 file");
+    }
+
+    return res;
+}
+
+static ref<std::string> decompressBzip2(const std::string & in)
+{
+    bz_stream strm;
+    memset(&strm, 0, sizeof(strm));
+
+    int ret = BZ2_bzDecompressInit(&strm, 0, 0);
+    if (ret != BZ_OK)
+        throw Error("unable to initialise bzip2 decoder");
+
+    Finally free([&]() { BZ2_bzDecompressEnd(&strm); });
+
+    char outbuf[BUFSIZ];
+    ref<std::string> res = make_ref<std::string>();
+    strm.next_in = (char *) in.c_str();
+    strm.avail_in = in.size();
+    strm.next_out = outbuf;
+    strm.avail_out = sizeof(outbuf);
+
+    while (true) {
+        checkInterrupt();
+
+        int ret = BZ2_bzDecompress(&strm);
+
+        if (strm.avail_out == 0 || ret == BZ_STREAM_END) {
+            res->append(outbuf, sizeof(outbuf) - strm.avail_out);
+            strm.next_out = outbuf;
+            strm.avail_out = sizeof(outbuf);
+        }
+
+        if (ret == BZ_STREAM_END)
+            return res;
+
+        if (ret != BZ_OK)
+            throw Error("error while decompressing bzip2 file");
+    }
+}
+
+ref<std::string> compress(const std::string & method, ref<std::string> in)
+{
+    if (method == "none")
+        return in;
+    else if (method == "xz")
+        return compressXZ(*in);
+    else if (method == "bzip2")
+        return compressBzip2(*in);
+    else
+        throw UnknownCompressionMethod(format("unknown compression method ‘%s’") % method);
+}
+
+ref<std::string> decompress(const std::string & method, ref<std::string> in)
+{
+    if (method == "none")
+        return in;
+    else if (method == "xz")
+        return decompressXZ(*in);
+    else if (method == "bzip2")
+        return decompressBzip2(*in);
+    else
+        throw UnknownCompressionMethod(format("unknown compression method ‘%s’") % method);
+}
+
 }
diff --git a/src/libutil/compression.hh b/src/libutil/compression.hh
index 79a796db7756..33c465df8455 100644
--- a/src/libutil/compression.hh
+++ b/src/libutil/compression.hh
@@ -1,13 +1,16 @@
 #pragma once
 
 #include "ref.hh"
+#include "types.hh"
 
 #include <string>
 
 namespace nix {
 
-std::string compressXZ(const std::string & in);
+ref<std::string> compress(const std::string & method, ref<std::string> in);
 
-ref<std::string> decompressXZ(const std::string & in);
+ref<std::string> decompress(const std::string & method, ref<std::string> in);
+
+MakeError(UnknownCompressionMethod, Error);
 
 }
diff --git a/src/libutil/finally.hh b/src/libutil/finally.hh
new file mode 100644
index 000000000000..47c64deaecea
--- /dev/null
+++ b/src/libutil/finally.hh
@@ -0,0 +1,12 @@
+#pragma once
+
+/* A trivial class to run a function at the end of a scope. */
+class Finally
+{
+private:
+    std::function<void()> fun;
+
+public:
+    Finally(std::function<void()> fun) : fun(fun) { }
+    ~Finally() { fun(); }
+};
diff --git a/src/libutil/hash.cc b/src/libutil/hash.cc
index 64739300302b..c17f1c4d5150 100644
--- a/src/libutil/hash.cc
+++ b/src/libutil/hash.cc
@@ -33,7 +33,7 @@ Hash::Hash(HashType type)
     else if (type == htSHA1) hashSize = sha1HashSize;
     else if (type == htSHA256) hashSize = sha256HashSize;
     else if (type == htSHA512) hashSize = sha512HashSize;
-    else throw Error("unknown hash type");
+    else abort();
     assert(hashSize <= maxHashSize);
     memset(hash, 0, maxHashSize);
 }
@@ -64,6 +64,12 @@ bool Hash::operator < (const Hash & h) const
 }
 
 
+std::string Hash::to_string(bool base32) const
+{
+    return printHashType(type) + ":" + (base32 ? printHash32(*this) : printHash(*this));
+}
+
+
 const string base16Chars = "0123456789abcdef";
 
 
@@ -78,15 +84,28 @@ string printHash(const Hash & hash)
 }
 
 
+Hash parseHash(const string & s)
+{
+    string::size_type colon = s.find(':');
+    if (colon == string::npos)
+        throw BadHash(format("invalid hash ‘%s’") % s);
+    string hts = string(s, 0, colon);
+    HashType ht = parseHashType(hts);
+    if (ht == htUnknown)
+        throw BadHash(format("unknown hash type ‘%s’") % hts);
+    return parseHash16or32(ht, string(s, colon + 1));
+}
+
+
 Hash parseHash(HashType ht, const string & s)
 {
     Hash hash(ht);
     if (s.length() != hash.hashSize * 2)
-        throw Error(format("invalid hash ‘%1%’") % s);
+        throw BadHash(format("invalid hash ‘%1%’") % s);
     for (unsigned int i = 0; i < hash.hashSize; i++) {
         string s2(s, i * 2, 2);
         if (!isxdigit(s2[0]) || !isxdigit(s2[1]))
-            throw Error(format("invalid hash ‘%1%’") % s);
+            throw BadHash(format("invalid hash ‘%1%’") % s);
         std::istringstream str(s2);
         int n;
         str >> std::hex >> n;
@@ -103,6 +122,7 @@ const string base32Chars = "0123456789abcdfghijklmnpqrsvwxyz";
 string printHash32(const Hash & hash)
 {
     size_t len = hash.base32Len();
+    assert(len);
 
     string s;
     s.reserve(len);
@@ -139,7 +159,7 @@ Hash parseHash32(HashType ht, const string & s)
         for (digit = 0; digit < base32Chars.size(); ++digit) /* !!! slow */
             if (base32Chars[digit] == c) break;
         if (digit >= 32)
-            throw Error(format("invalid base-32 hash ‘%1%’") % s);
+            throw BadHash(format("invalid base-32 hash ‘%1%’") % s);
         unsigned int b = n * 5;
         unsigned int i = b / 8;
         unsigned int j = b % 8;
@@ -161,7 +181,7 @@ Hash parseHash16or32(HashType ht, const string & s)
         /* base-32 representation */
         hash = parseHash32(ht, s);
     else
-        throw Error(format("hash ‘%1%’ has wrong length for hash type ‘%2%’")
+        throw BadHash(format("hash ‘%1%’ has wrong length for hash type ‘%2%’")
             % s % printHashType(ht));
     return hash;
 }
@@ -322,7 +342,7 @@ string printHashType(HashType ht)
     else if (ht == htSHA1) return "sha1";
     else if (ht == htSHA256) return "sha256";
     else if (ht == htSHA512) return "sha512";
-    else throw Error("cannot print unknown hash type");
+    else abort();
 }
 
 
diff --git a/src/libutil/hash.hh b/src/libutil/hash.hh
index bac2ebf2dcfa..02e213fc7b35 100644
--- a/src/libutil/hash.hh
+++ b/src/libutil/hash.hh
@@ -7,6 +7,9 @@
 namespace nix {
 
 
+MakeError(BadHash, Error);
+
+
 enum HashType : char { htUnknown, htMD5, htSHA1, htSHA256, htSHA512 };
 
 
@@ -26,12 +29,15 @@ struct Hash
 
     HashType type;
 
-    /* Create an unusable hash object. */
+    /* Create an unset hash object. */
     Hash();
 
     /* Create a zero-filled hash object. */
     Hash(HashType type);
 
+    /* Check whether a hash is set. */
+    operator bool () const { return type != htUnknown; }
+
     /* Check whether two hash are equal. */
     bool operator == (const Hash & h2) const;
 
@@ -52,12 +58,16 @@ struct Hash
     {
         return (hashSize * 8 - 1) / 5 + 1;
     }
+
+    std::string to_string(bool base32 = true) const;
 };
 
 
 /* Convert a hash to a hexadecimal representation. */
 string printHash(const Hash & hash);
 
+Hash parseHash(const string & s);
+
 /* Parse a hexadecimal representation of a hash code. */
 Hash parseHash(HashType ht, const string & s);
 
diff --git a/src/libutil/local.mk b/src/libutil/local.mk
index 2e5d2672e5f0..98cad00d6d95 100644
--- a/src/libutil/local.mk
+++ b/src/libutil/local.mk
@@ -6,6 +6,6 @@ libutil_DIR := $(d)
 
 libutil_SOURCES := $(wildcard $(d)/*.cc)
 
-libutil_LDFLAGS = -llzma -pthread $(OPENSSL_LIBS)
+libutil_LDFLAGS = -llzma -lbz2 -pthread $(OPENSSL_LIBS)
 
 libutil_LIBS = libformat
diff --git a/src/libutil/logging.cc b/src/libutil/logging.cc
new file mode 100644
index 000000000000..15bb1e175da6
--- /dev/null
+++ b/src/libutil/logging.cc
@@ -0,0 +1,79 @@
+#include "logging.hh"
+#include "util.hh"
+
+namespace nix {
+
+Logger * logger = 0;
+
+class SimpleLogger : public Logger
+{
+public:
+
+    bool systemd, tty;
+
+    SimpleLogger()
+    {
+        systemd = getEnv("IN_SYSTEMD") == "1";
+        tty = isatty(STDERR_FILENO);
+    }
+
+    void log(Verbosity lvl, const FormatOrString & fs) override
+    {
+        if (lvl > verbosity) return;
+
+        std::string prefix;
+
+        if (systemd) {
+            char c;
+            switch (lvl) {
+            case lvlError: c = '3'; break;
+            case lvlInfo: c = '5'; break;
+            case lvlTalkative: case lvlChatty: c = '6'; break;
+            default: c = '7';
+            }
+            prefix = std::string("<") + c + ">";
+        }
+
+        writeToStderr(prefix + (tty ? fs.s : filterANSIEscapes(fs.s)) + "\n");
+    }
+
+    void startActivity(Activity & activity, Verbosity lvl, const FormatOrString & fs) override
+    {
+        log(lvl, fs);
+    }
+
+    void stopActivity(Activity & activity) override
+    {
+    }
+};
+
+Verbosity verbosity = lvlInfo;
+
+void warnOnce(bool & haveWarned, const FormatOrString & fs)
+{
+    if (!haveWarned) {
+        printMsg(lvlError, format("warning: %1%") % fs.s);
+        haveWarned = true;
+    }
+}
+
+void writeToStderr(const string & s)
+{
+    try {
+        writeFull(STDERR_FILENO, s);
+    } catch (SysError & e) {
+        /* Ignore failing writes to stderr if we're in an exception
+           handler, otherwise throw an exception.  We need to ignore
+           write errors in exception handlers to ensure that cleanup
+           code runs to completion if the other side of stderr has
+           been closed unexpectedly. */
+        if (!std::uncaught_exception()) throw;
+    }
+}
+
+Logger * makeDefaultLogger()
+{
+    return new SimpleLogger();
+}
+
+}
diff --git a/src/libutil/logging.hh b/src/libutil/logging.hh
new file mode 100644
index 000000000000..277dff280053
--- /dev/null
+++ b/src/libutil/logging.hh
@@ -0,0 +1,82 @@
+#pragma once
+
+#include "types.hh"
+
+namespace nix {
+
+typedef enum {
+    lvlError = 0,
+    lvlInfo,
+    lvlTalkative,
+    lvlChatty,
+    lvlDebug,
+    lvlVomit
+} Verbosity;
+
+class Activity;
+
+class Logger
+{
+    friend class Activity;
+
+public:
+
+    virtual ~Logger() { }
+
+    virtual void log(Verbosity lvl, const FormatOrString & fs) = 0;
+
+    void log(const FormatOrString & fs)
+    {
+        log(lvlInfo, fs);
+    }
+
+    virtual void setExpected(const std::string & label, uint64_t value = 1) { }
+    virtual void setProgress(const std::string & label, uint64_t value = 1) { }
+    virtual void incExpected(const std::string & label, uint64_t value = 1) { }
+    virtual void incProgress(const std::string & label, uint64_t value = 1) { }
+
+private:
+
+    virtual void startActivity(Activity & activity, Verbosity lvl, const FormatOrString & fs) = 0;
+
+    virtual void stopActivity(Activity & activity) = 0;
+
+};
+
+class Activity
+{
+public:
+    Logger & logger;
+
+    Activity(Logger & logger, Verbosity lvl, const FormatOrString & fs)
+        : logger(logger)
+    {
+        logger.startActivity(*this, lvl, fs);
+    }
+
+    ~Activity()
+    {
+        logger.stopActivity(*this);
+    }
+};
+
+extern Logger * logger;
+
+Logger * makeDefaultLogger();
+
+extern Verbosity verbosity; /* suppress msgs > this */
+
+#define printMsg(level, f) \
+    do { \
+        if (level <= nix::verbosity) { \
+            logger->log(level, (f)); \
+        } \
+    } while (0)
+
+#define debug(f) printMsg(lvlDebug, f)
+
+void warnOnce(bool & haveWarned, const FormatOrString & fs);
+
+void writeToStderr(const string & s);
+
+}
diff --git a/src/libutil/lru-cache.hh b/src/libutil/lru-cache.hh
index 4344d6601bc8..35983aa2c918 100644
--- a/src/libutil/lru-cache.hh
+++ b/src/libutil/lru-cache.hh
@@ -79,6 +79,12 @@ public:
     {
         return data.size();
     }
+
+    void clear()
+    {
+        data.clear();
+        lru.clear();
+    }
 };
 
 }
diff --git a/src/libutil/ref.hh b/src/libutil/ref.hh
index 349f24f7c488..9f5da09152c9 100644
--- a/src/libutil/ref.hh
+++ b/src/libutil/ref.hh
@@ -44,6 +44,12 @@ public:
     }
 
     template<typename T2>
+    ref<T2> cast()
+    {
+        return ref<T2>(std::dynamic_pointer_cast<T2>(p));
+    }
+
+    template<typename T2>
     operator ref<T2> ()
     {
         return ref<T2>((std::shared_ptr<T2>) p);
diff --git a/src/libutil/thread-pool.cc b/src/libutil/thread-pool.cc
index 743038b588a7..32363ecf0098 100644
--- a/src/libutil/thread-pool.cc
+++ b/src/libutil/thread-pool.cc
@@ -1,79 +1,99 @@
 #include "thread-pool.hh"
+#include "affinity.hh"
 
 namespace nix {
 
-ThreadPool::ThreadPool(size_t _nrThreads)
-    : nrThreads(_nrThreads)
+ThreadPool::ThreadPool(size_t _maxThreads)
+    : maxThreads(_maxThreads)
 {
-    if (!nrThreads) {
-        nrThreads = std::thread::hardware_concurrency();
-        if (!nrThreads) nrThreads = 1;
+    restoreAffinity(); // FIXME
+
+    if (!maxThreads) {
+        maxThreads = std::thread::hardware_concurrency();
+        if (!maxThreads) maxThreads = 1;
     }
+
+    debug(format("starting pool of %d threads") % maxThreads);
+}
+
+ThreadPool::~ThreadPool()
+{
+    std::vector<std::thread> workers;
+    {
+        auto state(state_.lock());
+        state->quit = true;
+        std::swap(workers, state->workers);
+    }
+
+    debug(format("reaping %d worker threads") % workers.size());
+
+    work.notify_all();
+
+    for (auto & thr : workers)
+        thr.join();
 }
 
 void ThreadPool::enqueue(const work_t & t)
 {
-    auto state_(state.lock());
-    state_->left.push(t);
-    wakeup.notify_one();
+    auto state(state_.lock());
+    assert(!state->quit);
+    state->left.push(t);
+    if (state->left.size() > state->workers.size() && state->workers.size() < maxThreads)
+        state->workers.emplace_back(&ThreadPool::workerEntry, this);
+    work.notify_one();
 }
 
 void ThreadPool::process()
 {
-    printMsg(lvlDebug, format("starting pool of %d threads") % nrThreads);
-
-    std::vector<std::thread> workers;
+    while (true) {
+        auto state(state_.lock());
+        if (state->exception)
+            std::rethrow_exception(state->exception);
+        if (state->left.empty() && !state->pending) break;
+        state.wait(done);
+    }
+}
 
-    for (size_t n = 0; n < nrThreads; n++)
-        workers.push_back(std::thread([&]() {
-            bool first = true;
+void ThreadPool::workerEntry()
+{
+    bool didWork = false;
 
+    while (true) {
+        work_t w;
+        {
+            auto state(state_.lock());
             while (true) {
-                work_t work;
-                {
-                    auto state_(state.lock());
-                    if (state_->exception) return;
-                    if (!first) {
-                        assert(state_->pending);
-                        state_->pending--;
-                    }
-                    first = false;
-                    while (state_->left.empty()) {
-                        if (!state_->pending) {
-                            wakeup.notify_all();
-                            return;
-                        }
-                        if (state_->exception) return;
-                        state_.wait(wakeup);
-                    }
-                    work = state_->left.front();
-                    state_->left.pop();
-                    state_->pending++;
-                }
-
-                try {
-                    work();
-                } catch (std::exception & e) {
-                    auto state_(state.lock());
-                    if (state_->exception) {
-                        if (!dynamic_cast<Interrupted*>(&e))
-                            printMsg(lvlError, format("error: %s") % e.what());
-                    } else {
-                        state_->exception = std::current_exception();
-                        wakeup.notify_all();
-                    }
+                if (state->quit || state->exception) return;
+                if (didWork) {
+                    assert(state->pending);
+                    state->pending--;
+                    didWork = false;
                 }
+                if (!state->left.empty()) break;
+                if (!state->pending)
+                    done.notify_all();
+                state.wait(work);
             }
+            w = state->left.front();
+            state->left.pop();
+            state->pending++;
+        }
 
-        }));
-
-    for (auto & thr : workers)
-        thr.join();
+        try {
+            w();
+        } catch (std::exception & e) {
+            auto state(state_.lock());
+            if (state->exception) {
+                if (!dynamic_cast<Interrupted*>(&e))
+                    printMsg(lvlError, format("error: %s") % e.what());
+            } else {
+                state->exception = std::current_exception();
+                work.notify_all();
+                done.notify_all();
+            }
+        }
 
-    {
-        auto state_(state.lock());
-        if (state_->exception)
-            std::rethrow_exception(state_->exception);
+        didWork = true;
     }
 }
 
diff --git a/src/libutil/thread-pool.hh b/src/libutil/thread-pool.hh
index 77641d88ba4e..78b63467d62e 100644
--- a/src/libutil/thread-pool.hh
+++ b/src/libutil/thread-pool.hh
@@ -6,6 +6,7 @@
 #include <queue>
 #include <functional>
 #include <thread>
+#include <map>
 
 namespace nix {
 
@@ -15,7 +16,9 @@ class ThreadPool
 {
 public:
 
-    ThreadPool(size_t nrThreads = 0);
+    ThreadPool(size_t maxThreads = 0);
+
+    ~ThreadPool();
 
     // FIXME: use std::packaged_task?
     typedef std::function<void()> work_t;
@@ -34,19 +37,81 @@ public:
 
 private:
 
-    size_t nrThreads;
+    size_t maxThreads;
 
     struct State
     {
         std::queue<work_t> left;
         size_t pending = 0;
         std::exception_ptr exception;
+        std::vector<std::thread> workers;
+        bool quit = false;
     };
 
-    Sync<State> state;
+    Sync<State> state_;
 
-    std::condition_variable wakeup;
+    std::condition_variable work, done;
 
+    void workerEntry();
 };
 
+/* Process in parallel a set of items of type T that have a partial
+   ordering between them. Thus, any item is only processed after all
+   its dependencies have been processed. */
+template<typename T>
+void processGraph(
+    ThreadPool & pool,
+    const std::set<T> & nodes,
+    std::function<std::set<T>(const T &)> getEdges,
+    std::function<void(const T &)> processNode)
+{
+    struct Graph {
+        std::set<T> left;
+        std::map<T, std::set<T>> refs, rrefs;
+        std::function<void(T)> wrap;
+    };
+
+    ref<Sync<Graph>> graph_ = make_ref<Sync<Graph>>();
+
+    auto wrapWork = [&pool, graph_, processNode](const T & node) {
+        processNode(node);
+
+        /* Enqueue work for all nodes that were waiting on this one. */
+        {
+            auto graph(graph_->lock());
+            graph->left.erase(node);
+            for (auto & rref : graph->rrefs[node]) {
+                auto & refs(graph->refs[rref]);
+                auto i = refs.find(node);
+                assert(i != refs.end());
+                refs.erase(i);
+                if (refs.empty())
+                    pool.enqueue(std::bind(graph->wrap, rref));
+            }
+        }
+    };
+
+    {
+        auto graph(graph_->lock());
+        graph->left = nodes;
+        graph->wrap = wrapWork;
+    }
+
+    /* Build the dependency graph; enqueue all nodes with no
+       dependencies. */
+    for (auto & node : nodes) {
+        auto refs = getEdges(node);
+        {
+            auto graph(graph_->lock());
+            for (auto & ref : refs)
+                if (ref != node && graph->left.count(ref)) {
+                    graph->refs[node].insert(ref);
+                    graph->rrefs[ref].insert(node);
+                }
+            if (graph->refs[node].empty())
+                pool.enqueue(std::bind(graph->wrap, node));
+        }
+    }
+}
+
 }
diff --git a/src/libutil/types.hh b/src/libutil/types.hh
index 33aaf5fc9c4d..bd192b8506b2 100644
--- a/src/libutil/types.hh
+++ b/src/libutil/types.hh
@@ -89,14 +89,4 @@ typedef list<Path> Paths;
 typedef set<Path> PathSet;
 
 
-typedef enum {
-    lvlError = 0,
-    lvlInfo,
-    lvlTalkative,
-    lvlChatty,
-    lvlDebug,
-    lvlVomit
-} Verbosity;
-
-
 }
diff --git a/src/libutil/util.cc b/src/libutil/util.cc
index 55d490992108..67558cc0b33c 100644
--- a/src/libutil/util.cc
+++ b/src/libutil/util.cc
@@ -356,8 +356,7 @@ void deletePath(const Path & path)
 
 void deletePath(const Path & path, unsigned long long & bytesFreed)
 {
-    startNest(nest, lvlDebug,
-        format("recursively deleting path ‘%1%’") % path);
+    Activity act(*logger, lvlDebug, format("recursively deleting path ‘%1%’") % path);
     bytesFreed = 0;
     _deletePath(path, bytesFreed);
 }
@@ -403,6 +402,18 @@ Path createTempDir(const Path & tmpRoot, const Path & prefix,
 }
 
 
+Path getCacheDir()
+{
+    Path cacheDir = getEnv("XDG_CACHE_HOME");
+    if (cacheDir.empty()) {
+        Path homeDir = getEnv("HOME");
+        if (homeDir.empty()) throw Error("$XDG_CACHE_HOME and $HOME are not set");
+        cacheDir = homeDir + "/.cache";
+    }
+    return cacheDir;
+}
+
+
 Paths createDirs(const Path & path)
 {
     Paths created;
@@ -444,113 +455,6 @@ void replaceSymlink(const Path & target, const Path & link)
 }
 
 
-LogType logType = ltPretty;
-Verbosity verbosity = lvlInfo;
-
-static int nestingLevel = 0;
-
-
-Nest::Nest()
-{
-    nest = false;
-}
-
-
-Nest::~Nest()
-{
-    close();
-}
-
-
-static string escVerbosity(Verbosity level)
-{
-    return std::to_string((int) level);
-}
-
-
-void Nest::open(Verbosity level, const FormatOrString & fs)
-{
-    if (level <= verbosity) {
-        if (logType == ltEscapes)
-            std::cerr << "\033[" << escVerbosity(level) << "p"
-                      << fs.s << "\n";
-        else
-            printMsg_(level, fs);
-        nest = true;
-        nestingLevel++;
-    }
-}
-
-
-void Nest::close()
-{
-    if (nest) {
-        nestingLevel--;
-        if (logType == ltEscapes)
-            std::cerr << "\033[q";
-        nest = false;
-    }
-}
-
-
-void printMsg_(Verbosity level, const FormatOrString & fs)
-{
-    checkInterrupt();
-    if (level > verbosity) return;
-
-    string prefix;
-    if (logType == ltPretty)
-        for (int i = 0; i < nestingLevel; i++)
-            prefix += "|   ";
-    else if (logType == ltEscapes && level != lvlInfo)
-        prefix = "\033[" + escVerbosity(level) + "s";
-    else if (logType == ltSystemd) {
-        char c;
-        switch (level) {
-            case lvlError: c = '3'; break;
-            case lvlInfo: c = '5'; break;
-            case lvlTalkative: case lvlChatty: c = '6'; break;
-            default: c = '7';
-        }
-        prefix = string("<") + c + ">";
-    }
-
-    string s = (format("%1%%2%\n") % prefix % fs.s).str();
-    if (!isatty(STDERR_FILENO)) s = filterANSIEscapes(s);
-    writeToStderr(s);
-}
-
-
-void warnOnce(bool & haveWarned, const FormatOrString & fs)
-{
-    if (!haveWarned) {
-        printMsg(lvlError, format("warning: %1%") % fs.s);
-        haveWarned = true;
-    }
-}
-
-
-void writeToStderr(const string & s)
-{
-    try {
-        if (_writeToStderr)
-            _writeToStderr((const unsigned char *) s.data(), s.size());
-        else
-            writeFull(STDERR_FILENO, s);
-    } catch (SysError & e) {
-        /* Ignore failing writes to stderr if we're in an exception
-           handler, otherwise throw an exception.  We need to ignore
-           write errors in exception handlers to ensure that cleanup
-           code runs to completion if the other side of stderr has
-           been closed unexpectedly. */
-        if (!std::uncaught_exception()) throw;
-    }
-}
-
-
-std::function<void(const unsigned char * buf, size_t count)> _writeToStderr;
-
-
 void readFull(int fd, unsigned char * buf, size_t count)
 {
     while (count) {
@@ -941,7 +845,8 @@ static pid_t doFork(bool allowVfork, std::function<void()> fun)
 pid_t startProcess(std::function<void()> fun, const ProcessOptions & options)
 {
     auto wrapper = [&]() {
-        if (!options.allowVfork) _writeToStderr = 0;
+        if (!options.allowVfork)
+            logger = makeDefaultLogger();
         try {
 #if __linux__
             if (options.dieWithParent && prctl(PR_SET_PDEATHSIG, SIGKILL) == -1)
@@ -1177,6 +1082,12 @@ bool statusOk(int status)
 }
 
 
+bool hasPrefix(const string & s, const string & suffix)
+{
+    return s.compare(0, suffix.size(), suffix) == 0;
+}
+
+
 bool hasSuffix(const string & s, const string & suffix)
 {
     return s.size() >= suffix.size() && string(s, s.size() - suffix.size()) == suffix;
diff --git a/src/libutil/util.hh b/src/libutil/util.hh
index 20bd62a0e752..f3f0f92a0aaa 100644
--- a/src/libutil/util.hh
+++ b/src/libutil/util.hh
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "types.hh"
+#include "logging.hh"
 
 #include <sys/types.h>
 #include <sys/stat.h>
@@ -102,6 +103,9 @@ void deletePath(const Path & path, unsigned long long & bytesFreed);
 Path createTempDir(const Path & tmpRoot = "", const Path & prefix = "nix",
     bool includePid = true, bool useGlobalCounter = true, mode_t mode = 0755);
 
+/* Return the path to $XDG_CACHE_HOME/.cache. */
+Path getCacheDir();
+
 /* Create a directory and all its parents, if necessary.  Returns the
    list of created directories, in order of creation. */
 Paths createDirs(const Path & path);
@@ -122,54 +126,6 @@ T singleton(const A & a)
 }
 
 
-/* Messages. */
-
-
-typedef enum {
-    ltPretty,   /* nice, nested output */
-    ltEscapes,  /* nesting indicated using escape codes (for log2xml) */
-    ltFlat,     /* no nesting */
-    ltSystemd,  /* use systemd severity prefixes */
-} LogType;
-
-extern LogType logType;
-extern Verbosity verbosity; /* suppress msgs > this */
-
-class Nest
-{
-private:
-    bool nest;
-public:
-    Nest();
-    ~Nest();
-    void open(Verbosity level, const FormatOrString & fs);
-    void close();
-};
-
-void printMsg_(Verbosity level, const FormatOrString & fs);
-
-#define startNest(varName, level, f) \
-    Nest varName; \
-    if (level <= verbosity) { \
-      varName.open(level, (f)); \
-    }
-
-#define printMsg(level, f) \
-    do { \
-        if (level <= nix::verbosity) { \
-            nix::printMsg_(level, (f)); \
-        } \
-    } while (0)
-
-#define debug(f) printMsg(lvlDebug, f)
-
-void warnOnce(bool & haveWarned, const FormatOrString & fs);
-
-void writeToStderr(const string & s);
-
-extern std::function<void(const unsigned char * buf, size_t count)> _writeToStderr;
-
-
 /* Wrappers arount read()/write() that read/write exactly the
    requested number of bytes. */
 void readFull(int fd, unsigned char * buf, size_t count);
@@ -377,6 +333,10 @@ template<class N> bool string2Float(const string & s, N & n)
 }
 
 
+/* Return true iff `s' starts with `prefix'. */
+bool hasPrefix(const string & s, const string & prefix);
+
+
 /* Return true iff `s' ends in `suffix'. */
 bool hasSuffix(const string & s, const string & suffix);
 
diff --git a/src/nix-daemon/nix-daemon.cc b/src/nix-daemon/nix-daemon.cc
index c3cdb8395093..3c2e0521028c 100644
--- a/src/nix-daemon/nix-daemon.cc
+++ b/src/nix-daemon/nix-daemon.cc
@@ -33,29 +33,43 @@ using namespace nix;
 static FdSource from(STDIN_FILENO);
 static FdSink to(STDOUT_FILENO);
 
-bool canSendStderr;
+static bool canSendStderr;
 
+static Logger * defaultLogger;
 
-/* This function is called anytime we want to write something to
-   stderr.  If we're in a state where the protocol allows it (i.e.,
-   when canSendStderr), send the message to the client over the
-   socket. */
-static void tunnelStderr(const unsigned char * buf, size_t count)
+
+/* Logger that forwards log messages to the client, *if* we're in a
+   state where the protocol allows it (i.e., when canSendStderr is
+   true). */
+class TunnelLogger : public Logger
 {
-    if (canSendStderr) {
-        try {
-            to << STDERR_NEXT;
-            writeString(buf, count, to);
-            to.flush();
-        } catch (...) {
-            /* Write failed; that means that the other side is
-               gone. */
-            canSendStderr = false;
-            throw;
-        }
-    } else
-        writeFull(STDERR_FILENO, buf, count);
-}
+    void log(Verbosity lvl, const FormatOrString & fs) override
+    {
+        if (lvl > verbosity) return;
+
+        if (canSendStderr) {
+            try {
+                to << STDERR_NEXT << (fs.s + "\n");
+                to.flush();
+            } catch (...) {
+                /* Write failed; that means that the other side is
+                   gone. */
+                canSendStderr = false;
+                throw;
+            }
+        } else
+            defaultLogger->log(lvl, fs);
+    }
+
+    void startActivity(Activity & activity, Verbosity lvl, const FormatOrString & fs) override
+    {
+        log(lvl, fs);
+    }
+
+    void stopActivity(Activity & activity) override
+    {
+    }
+};
 
 
 /* startWork() means that we're starting an operation for which we
@@ -199,7 +213,7 @@ static void performOp(ref<LocalStore> store, bool trusted, unsigned int clientVe
     case wopQueryPathHash: {
         Path path = readStorePath(from);
         startWork();
-        Hash hash = store->queryPathHash(path);
+        auto hash = store->queryPathInfo(path)->narHash;
         stopWork();
         to << printHash(hash);
         break;
@@ -213,7 +227,7 @@ static void performOp(ref<LocalStore> store, bool trusted, unsigned int clientVe
         startWork();
         PathSet paths;
         if (op == wopQueryReferences)
-            store->queryReferences(path, paths);
+            paths = store->queryPathInfo(path)->references;
         else if (op == wopQueryReferrers)
             store->queryReferrers(path, paths);
         else if (op == wopQueryValidDerivers)
@@ -237,7 +251,7 @@ static void performOp(ref<LocalStore> store, bool trusted, unsigned int clientVe
     case wopQueryDeriver: {
         Path path = readStorePath(from);
         startWork();
-        Path deriver = store->queryDeriver(path);
+        auto deriver = store->queryPathInfo(path)->deriver;
         stopWork();
         to << deriver;
         break;
@@ -429,9 +443,9 @@ static void performOp(ref<LocalStore> store, bool trusted, unsigned int clientVe
         if (GET_PROTOCOL_MINOR(clientVersion) >= 2)
             settings.useBuildHook = readInt(from) != 0;
         if (GET_PROTOCOL_MINOR(clientVersion) >= 4) {
-            settings.buildVerbosity = (Verbosity) readInt(from);
-            logType = (LogType) readInt(from);
-            settings.printBuildTrace = readInt(from) != 0;
+            settings.verboseBuild = lvlError == (Verbosity) readInt(from);
+            readInt(from); // obsolete logType
+            readInt(from); // obsolete printBuildTrace
         }
         if (GET_PROTOCOL_MINOR(clientVersion) >= 6)
             settings.set("build-cores", std::to_string(readInt(from)));
@@ -495,15 +509,23 @@ static void performOp(ref<LocalStore> store, bool trusted, unsigned int clientVe
 
     case wopQueryPathInfo: {
         Path path = readStorePath(from);
+        std::shared_ptr<const ValidPathInfo> info;
         startWork();
-        ValidPathInfo info = store->queryPathInfo(path);
-        stopWork();
-        to << info.deriver << printHash(info.narHash) << info.references
-           << info.registrationTime << info.narSize;
-        if (GET_PROTOCOL_MINOR(clientVersion) >= 16) {
-            to << info.ultimate
-               << info.sigs;
+        try {
+            info = store->queryPathInfo(path);
+        } catch (InvalidPath &) {
+            if (GET_PROTOCOL_MINOR(clientVersion) < 17) throw;
         }
+        stopWork();
+        if (info) {
+            to << 1 << info->deriver << printHash(info->narHash) << info->references
+               << info->registrationTime << info->narSize;
+            if (GET_PROTOCOL_MINOR(clientVersion) >= 16) {
+                to << info->ultimate
+                   << info->sigs;
+            }
+        } else
+            to << 0;
         break;
     }
 
@@ -549,7 +571,8 @@ static void processConnection(bool trusted)
     MonitorFdHup monitor(from.fd);
 
     canSendStderr = false;
-    _writeToStderr = tunnelStderr;
+    defaultLogger = logger;
+    logger = new TunnelLogger();
 
     /* Exchange the greeting. */
     unsigned int magic = readInt(from);
diff --git a/src/nix-env/nix-env.cc b/src/nix-env/nix-env.cc
index a9d1ed024dd3..6bc8d79bc1bb 100644
--- a/src/nix-env/nix-env.cc
+++ b/src/nix-env/nix-env.cc
@@ -996,7 +996,7 @@ static void opQuery(Globals & globals, Strings opFlags, Strings opArgs)
         try {
             if (i.hasFailed()) continue;
 
-            startNest(nest, lvlDebug, format("outputting query result ‘%1%’") % i.attrPath);
+            Activity act(*logger, lvlDebug, format("outputting query result ‘%1%’") % i.attrPath);
 
             if (globals.prebuiltOnly &&
                 validPaths.find(i.queryOutPath()) == validPaths.end() &&
diff --git a/src/nix-instantiate/nix-instantiate.cc b/src/nix-instantiate/nix-instantiate.cc
index 81c1c8d5637c..7dce08400e82 100644
--- a/src/nix-instantiate/nix-instantiate.cc
+++ b/src/nix-instantiate/nix-instantiate.cc
@@ -19,7 +19,7 @@ using namespace nix;
 
 static Expr * parseStdin(EvalState & state)
 {
-    startNest(nest, lvlTalkative, format("parsing standard input"));
+    Activity act(*logger, lvlTalkative, format("parsing standard input"));
     return state.parseExprFromString(drainFD(0), absPath("."));
 }
 
diff --git a/src/nix-log2xml/local.mk b/src/nix-log2xml/local.mk
deleted file mode 100644
index 09c848c17f40..000000000000
--- a/src/nix-log2xml/local.mk
+++ /dev/null
@@ -1,5 +0,0 @@
-programs += nix-log2xml
-
-nix-log2xml_DIR := $(d)
-
-nix-log2xml_SOURCES := $(d)/log2xml.cc
diff --git a/src/nix-log2xml/log2xml.cc b/src/nix-log2xml/log2xml.cc
deleted file mode 100644
index 31cea60c3809..000000000000
--- a/src/nix-log2xml/log2xml.cc
+++ /dev/null
@@ -1,201 +0,0 @@
-#include <vector>
-#include <iostream>
-#include <cstdio>
-#include <string>
-#include <cstring>
-
-using namespace std;
-
-
-struct Decoder
-{
-    enum { stTop, stEscape, stCSI } state;
-    string line;
-    bool inHeader;
-    int level;
-    vector<int> args;
-    bool newNumber;
-    int priority;
-    bool ignoreLF;
-    int lineNo, charNo;
-    bool warning;
-    bool error;
-
-    Decoder()
-    {
-        state = stTop;
-        line = "";
-        inHeader = false;
-        level = 0;
-        priority = 1;
-        ignoreLF = false;
-        lineNo = 1;
-        charNo = 0;
-        warning = false;
-        error = false;
-    }
-
-    void pushChar(char c);
-
-    void finishLine();
-
-    void decodeFile(istream & st);
-};
-
-
-void Decoder::pushChar(char c)
-{
-    if (c == '\n') {
-        lineNo++;
-        charNo = 0;
-    } else charNo++;
-    
-    switch (state) {
-        
-        case stTop:
-            if (c == '\e') {
-                state = stEscape;
-            } else if (c == '\n' && !ignoreLF) {
-                finishLine();
-            } else line += c;
-            break;
-
-        case stEscape:
-            if (c == '[') {
-                state = stCSI;
-                args.clear();
-                newNumber = true;
-            } else
-                state = stTop; /* !!! wrong */
-            break;
-
-        case stCSI:
-            if (c >= 0x40 && c != 0x7e) {
-                state = stTop;
-                switch (c) {
-                    case 'p':
-                        if (line.size()) finishLine();
-                        level++;
-                        inHeader = true;
-                        cout << "<nest>" << endl;
-                        priority = args.size() >= 1 ? args[0] : 1;
-                        break;
-                    case 'q':
-                        if (line.size()) finishLine();
-                        if (level > 0) {
-                            level--;
-                            cout << "</nest>" << endl;
-                        } else
-                            cerr << "not enough nesting levels at line "
-                                 << lineNo << ", character " << charNo  << endl;
-                        break;
-                    case 's':
-                        if (line.size()) finishLine();
-                        priority = args.size() >= 1 ? args[0] : 1;
-                        break;
-                    case 'a':
-                        ignoreLF = true;
-                        break;
-                    case 'b':
-                        ignoreLF = false;
-                        break;
-                    case 'e':
-                        error = true;
-                        break;
-                    case 'w':
-                        warning = true;
-                        break;
-                }
-            } else if (c >= '0' && c <= '9') {
-                int n = 0;
-                if (!newNumber) {
-                    n = args.back() * 10;
-                    args.pop_back();
-                }
-                n += c - '0';
-                args.push_back(n);
-            }
-            break;
-            
-    }
-}
-
-
-void Decoder::finishLine()
-{
-    string storeDir = "/nix/store/";
-    int sz = storeDir.size();
-    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++) {
-
-        if (line[i] == '<') cout << "&lt;";
-        else if (line[i] == '&') cout << "&amp;";
-        else if (line[i] == '\r') ; /* ignore carriage return */
-        else if (line[i] == '\n') cout << "\n";
-        else if (line[i] >= 0 && line[i] < 32 && line[i] != 9) cout << "&#xfffd;";
-        else if (i + sz + 33 < line.size() &&
-            string(line, i, sz) == storeDir &&
-            line[i + sz + 32] == '-')
-        {
-            int j = i + sz + 32;
-            /* skip name */
-            while (!strchr("/\n\r\t ()[]:;?<>", line[j])) j++;
-            int k = j;
-            while (!strchr("\n\r\t ()[]:;?<>", line[k])) k++;
-            // !!! escaping
-            cout << "<storeref>"
-                 << "<storedir>"
-                 << string(line, i, sz)
-                 << "</storedir>"
-                 << "<hash>"
-                 << string(line, i + sz, 32)
-                 << "</hash>"
-                 << "<name>"
-                 << string(line, i + sz + 32, j - (i + sz + 32))
-                 << "</name>"
-                 << "<path>"
-                 << string(line, j, k - j)
-                 << "</path>"
-                 << "</storeref>";
-            i = k - 1;
-        } else cout << line[i];
-    }
-    
-    cout << "</" << tag << ">" << endl;
-    line = "";
-    inHeader = false;
-    priority = 1;
-    warning = false;
-    error = false;
-}
-
-
-void Decoder::decodeFile(istream & st)
-{
-    int c;
-    
-    cout << "<logfile>" << endl;
-    
-    while ((c = st.get()) != EOF) {
-        pushChar(c);
-    }
-
-    if (line.size()) finishLine();
-
-    while (level--) cout << "</nest>" << endl;
-    
-    cout << "</logfile>" << endl;
-}
-
-
-int main(int argc, char * * argv)
-{
-    Decoder dec;
-    dec.decodeFile(cin);
-}
diff --git a/src/nix-log2xml/logfile.css b/src/nix-log2xml/logfile.css
deleted file mode 100644
index ed390d64a9ef..000000000000
--- a/src/nix-log2xml/logfile.css
+++ /dev/null
@@ -1,86 +0,0 @@
-body {
-    font-family: sans-serif;
-    background: white;
-}
-
-
-ul.nesting, ul.toplevel {
-    padding: 0;
-    margin: 0;
-}
-
-ul.toplevel {
-    list-style-type: none;
-}
-
-ul.nesting li.line, ul.nesting li.lastline {
-    position: relative;
-    list-style-type: none;
-}
-
-ul.nesting li.line {
-    padding-left: 1.1em;
-}
-
-ul.nesting li.lastline {
-    padding-left: 1.2em; // for the 0.1em border-left in .lastline > .lineconn
-}
-
-li.line {
-    border-left: 0.1em solid #6185a0;
-}
-
-li.line > span.lineconn, li.lastline > span.lineconn {
-    position: absolute;
-    height: 0.65em;
-    left: 0em;
-    width: 1em;
-    border-bottom: 0.1em solid #6185a0;
-}
-
-li.lastline > span.lineconn {
-    border-left: 0.1em solid #6185a0;
-}
-
-
-em.storeref {
-    color: #500000;
-    position: relative; 
-    width: 100%;
-}
-
-em.storeref:hover {
-    background-color: #eeeeee;
-}
-
-*.popup {
-    display: none;
-/*    background: url('http://losser.st-lab.cs.uu.nl/~mbravenb/menuback.png') repeat; */
-    background: #ffffcd;
-    border: solid #555555 1px;
-    position: absolute;
-    top: 0em;
-    left: 0em;
-    margin: 0;
-    padding: 0;
-    z-index: 100;
-}
-
-em.storeref:hover span.popup {
-    display: inline;
-}
-
-
-.toggle {
-    text-decoration: none;
-}
-
-.showTree, .hideTree {
-    font-family: monospace;
-    font-size: larger;
-}
-
-.error {
-    color: #ff0000;
-    font-weight: bold;
-}
\ No newline at end of file
diff --git a/src/nix-store/dotgraph.cc b/src/nix-store/dotgraph.cc
index 8735cf9b667b..356a82510124 100644
--- a/src/nix-store/dotgraph.cc
+++ b/src/nix-store/dotgraph.cc
@@ -110,19 +110,13 @@ void printDotGraph(ref<Store> store, const PathSet & roots)
 
         cout << makeNode(path, symbolicName(path), "#ff0000");
 
-        PathSet references;
-        store->queryReferences(path, references);
-
-        for (PathSet::iterator i = references.begin();
-             i != references.end(); ++i)
-        {
-            if (*i != path) {
-                workList.insert(*i);
-                cout << makeEdge(*i, path);
+        for (auto & p : store->queryPathInfo(path)->references) {
+            if (p != path) {
+                workList.insert(p);
+                cout << makeEdge(p, path);
             }
         }
 
-
 #if 0
         StoreExpr ne = storeExprFromPath(path);
 
diff --git a/src/nix-store/nix-store.cc b/src/nix-store/nix-store.cc
index 179015b52bfe..653a95f21679 100644
--- a/src/nix-store/nix-store.cc
+++ b/src/nix-store/nix-store.cc
@@ -9,6 +9,7 @@
 #include "util.hh"
 #include "worker-protocol.hh"
 #include "xmlgraph.hh"
+#include "compression.hh"
 
 #include <iostream>
 #include <algorithm>
@@ -51,7 +52,7 @@ ref<LocalStore> ensureLocalStore()
 static Path useDeriver(Path path)
 {
     if (isDerivation(path)) return path;
-    Path drvPath = store->queryDeriver(path);
+    Path drvPath = store->queryPathInfo(path)->deriver;
     if (drvPath == "")
         throw Error(format("deriver of path ‘%1%’ is not known") % path);
     return drvPath;
@@ -247,8 +248,7 @@ static void printTree(const Path & path,
 
     cout << format("%1%%2%\n") % firstPad % path;
 
-    PathSet references;
-    store->queryReferences(path, references);
+    auto references = store->queryPathInfo(path)->references;
 
     /* Topologically sort under the relation A < B iff A \in
        closure(B).  That is, if derivation A is an (possibly indirect)
@@ -335,7 +335,10 @@ static void opQuery(Strings opFlags, Strings opArgs)
                 PathSet ps = maybeUseOutputs(followLinksToStorePath(i), useOutput, forceRealise);
                 for (auto & j : ps) {
                     if (query == qRequisites) store->computeFSClosure(j, paths, false, includeOutputs);
-                    else if (query == qReferences) store->queryReferences(j, paths);
+                    else if (query == qReferences) {
+                        for (auto & p : store->queryPathInfo(j)->references)
+                            paths.insert(p);
+                    }
                     else if (query == qReferrers) store->queryReferrers(j, paths);
                     else if (query == qReferrersClosure) store->computeFSClosure(j, paths, true);
                 }
@@ -349,7 +352,7 @@ static void opQuery(Strings opFlags, Strings opArgs)
 
         case qDeriver:
             for (auto & i : opArgs) {
-                Path deriver = store->queryDeriver(followLinksToStorePath(i));
+                Path deriver = store->queryPathInfo(followLinksToStorePath(i))->deriver;
                 cout << format("%1%\n") %
                     (deriver == "" ? "unknown-deriver" : deriver);
             }
@@ -372,12 +375,12 @@ static void opQuery(Strings opFlags, Strings opArgs)
             for (auto & i : opArgs) {
                 PathSet paths = maybeUseOutputs(followLinksToStorePath(i), useOutput, forceRealise);
                 for (auto & j : paths) {
-                    ValidPathInfo info = store->queryPathInfo(j);
+                    auto info = store->queryPathInfo(j);
                     if (query == qHash) {
-                        assert(info.narHash.type == htSHA256);
-                        cout << format("sha256:%1%\n") % printHash32(info.narHash);
+                        assert(info->narHash.type == htSHA256);
+                        cout << format("sha256:%1%\n") % printHash32(info->narHash);
                     } else if (query == qSize)
-                        cout << format("%1%\n") % info.narSize;
+                        cout << format("%1%\n") % info->narSize;
                 }
             }
             break;
@@ -500,21 +503,7 @@ static void opReadLog(Strings opFlags, Strings opArgs)
             }
 
             else if (pathExists(logBz2Path)) {
-                AutoCloseFD fd = open(logBz2Path.c_str(), O_RDONLY);
-                FILE * f = 0;
-                if (fd == -1 || (f = fdopen(fd.borrow(), "r")) == 0)
-                    throw SysError(format("opening file ‘%1%’") % logBz2Path);
-                int err;
-                BZFILE * bz = BZ2_bzReadOpen(&err, f, 0, 0, 0, 0);
-                if (!bz) throw Error(format("cannot open bzip2 file ‘%1%’") % logBz2Path);
-                unsigned char buf[128 * 1024];
-                do {
-                    int n = BZ2_bzRead(&err, bz, buf, sizeof(buf));
-                    if (err != BZ_OK && err != BZ_STREAM_END)
-                        throw Error(format("error reading bzip2 file ‘%1%’") % logBz2Path);
-                    writeFull(STDOUT_FILENO, buf, n);
-                } while (err != BZ_STREAM_END);
-                BZ2_bzReadClose(&err, bz);
+                std::cout << *decompress("bzip2", make_ref<std::string>(readFile(logBz2Path)));
                 found = true;
                 break;
             }
@@ -782,14 +771,14 @@ static void opVerifyPath(Strings opFlags, Strings opArgs)
     for (auto & i : opArgs) {
         Path path = followLinksToStorePath(i);
         printMsg(lvlTalkative, format("checking path ‘%1%’...") % path);
-        ValidPathInfo info = store->queryPathInfo(path);
-        HashSink sink(info.narHash.type);
+        auto info = store->queryPathInfo(path);
+        HashSink sink(info->narHash.type);
         store->narFromPath(path, sink);
         auto current = sink.finish();
-        if (current.first != info.narHash) {
+        if (current.first != info->narHash) {
             printMsg(lvlError,
                 format("path ‘%1%’ was modified! expected hash ‘%2%’, got ‘%3%’")
-                % path % printHash(info.narHash) % printHash(current.first));
+                % path % printHash(info->narHash) % printHash(current.first));
             status = 1;
         }
     }
@@ -901,13 +890,14 @@ static void opServe(Strings opFlags, Strings opArgs)
                 PathSet paths = readStorePaths<PathSet>(in);
                 // !!! Maybe we want a queryPathInfos?
                 for (auto & i : paths) {
-                    if (!store->isValidPath(i))
-                        continue;
-                    ValidPathInfo info = store->queryPathInfo(i);
-                    out << info.path << info.deriver << info.references;
-                    // !!! Maybe we want compression?
-                    out << info.narSize // downloadSize
-                        << info.narSize;
+                    try {
+                        auto info = store->queryPathInfo(i);
+                        out << info->path << info->deriver << info->references;
+                        // !!! Maybe we want compression?
+                        out << info->narSize // downloadSize
+                            << info->narSize;
+                    } catch (InvalidPath &) {
+                    }
                 }
                 out << "";
                 break;
diff --git a/src/nix-store/xmlgraph.cc b/src/nix-store/xmlgraph.cc
index b6e1c1c4b873..0f7be7f7a02d 100644
--- a/src/nix-store/xmlgraph.cc
+++ b/src/nix-store/xmlgraph.cc
@@ -50,15 +50,10 @@ void printXmlGraph(ref<Store> store, const PathSet & roots)
 
         cout << makeNode(path);
 
-        PathSet references;
-        store->queryReferences(path, references);
-
-        for (PathSet::iterator i = references.begin();
-             i != references.end(); ++i)
-        {
-            if (*i != path) {
-                workList.insert(*i);
-                cout << makeEdge(*i, path);
+        for (auto & p : store->queryPathInfo(path)->references) {
+            if (p != path) {
+                workList.insert(p);
+                cout << makeEdge(p, path);
             }
         }
 
diff --git a/src/nix/command.cc b/src/nix/command.cc
index 986953fd845d..c8d91737d8be 100644
--- a/src/nix/command.cc
+++ b/src/nix/command.cc
@@ -5,6 +5,21 @@ namespace nix {
 
 Commands * RegisterCommand::commands = 0;
 
+void Command::printHelp(const string & programName, std::ostream & out)
+{
+    Args::printHelp(programName, out);
+
+    auto exs = examples();
+    if (!exs.empty()) {
+        out << "\n";
+        out << "Examples:\n";
+        for (auto & ex : exs)
+            out << "\n"
+                << "  " << ex.description << "\n" // FIXME: wrap
+                << "  $ " << ex.command << "\n";
+    }
+}
+
 MultiCommand::MultiCommand(const Commands & _commands)
     : commands(_commands)
 {
diff --git a/src/nix/command.hh b/src/nix/command.hh
index a6adb5f65491..34affc43d96e 100644
--- a/src/nix/command.hh
+++ b/src/nix/command.hh
@@ -11,6 +11,18 @@ struct Command : virtual Args
     virtual std::string name() = 0;
     virtual void prepare() { };
     virtual void run() = 0;
+
+    struct Example
+    {
+        std::string description;
+        std::string command;
+    };
+
+    typedef std::list<Example> Examples;
+
+    virtual Examples examples() { return Examples(); }
+
+    void printHelp(const string & programName, std::ostream & out) override;
 };
 
 class Store;
diff --git a/src/nix/copy.cc b/src/nix/copy.cc
new file mode 100644
index 000000000000..be51fee62712
--- /dev/null
+++ b/src/nix/copy.cc
@@ -0,0 +1,83 @@
+#include "command.hh"
+#include "shared.hh"
+#include "store-api.hh"
+#include "sync.hh"
+#include "thread-pool.hh"
+
+#include <atomic>
+
+using namespace nix;
+
+struct CmdCopy : StorePathsCommand
+{
+    std::string srcUri, dstUri;
+
+    CmdCopy()
+    {
+        mkFlag(0, "from", "store-uri", "URI of the source Nix store", &srcUri);
+        mkFlag(0, "to", "store-uri", "URI of the destination Nix store", &dstUri);
+    }
+
+    std::string name() override
+    {
+        return "copy";
+    }
+
+    std::string description() override
+    {
+        return "copy paths between Nix stores";
+    }
+
+    Examples examples() override
+    {
+        return {
+            Example{
+                "To copy Firefox to the local store to a binary cache in file:///tmp/cache:",
+                "nix copy --to file:///tmp/cache -r $(type -p firefox)"
+            },
+        };
+    }
+
+    void run(ref<Store> store, Paths storePaths) override
+    {
+        if (srcUri.empty() && dstUri.empty())
+            throw UsageError("you must pass ‘--from’ and/or ‘--to’");
+
+        ref<Store> srcStore = srcUri.empty() ? store : openStoreAt(srcUri);
+        ref<Store> dstStore = dstUri.empty() ? store : openStoreAt(dstUri);
+
+        std::string copiedLabel = "copied";
+
+        logger->setExpected(copiedLabel, storePaths.size());
+
+        ThreadPool pool;
+
+        processGraph<Path>(pool,
+            PathSet(storePaths.begin(), storePaths.end()),
+
+            [&](const Path & storePath) {
+                return srcStore->queryPathInfo(storePath)->references;
+            },
+
+            [&](const Path & storePath) {
+                checkInterrupt();
+
+                if (!dstStore->isValidPath(storePath)) {
+                    Activity act(*logger, lvlInfo, format("copying ‘%s’...") % storePath);
+
+                    StringSink sink;
+                    srcStore->exportPaths({storePath}, false, sink);
+
+                    StringSource source(*sink.s);
+                    dstStore->importPaths(false, source, 0);
+
+                    logger->incProgress(copiedLabel);
+                } else
+                    logger->incExpected(copiedLabel, -1);
+            });
+
+        pool.process();
+    }
+};
+
+static RegisterCommand r1(make_ref<CmdCopy>());
diff --git a/src/nix/main.cc b/src/nix/main.cc
index 2005ec5f9a6d..440ced97dfcc 100644
--- a/src/nix/main.cc
+++ b/src/nix/main.cc
@@ -7,6 +7,7 @@
 #include "legacy.hh"
 #include "shared.hh"
 #include "store-api.hh"
+#include "progress-bar.hh"
 
 namespace nix {
 
@@ -26,6 +27,8 @@ struct NixArgs : virtual MultiCommand, virtual MixCommonArgs
 
 void mainWrapped(int argc, char * * argv)
 {
+    settings.verboseBuild = false;
+
     initNix();
     initGC();
 
@@ -42,6 +45,8 @@ void mainWrapped(int argc, char * * argv)
 
     assert(args.command);
 
+    StartProgressBar bar;
+
     args.command->prepare();
     args.command->run();
 }
diff --git a/src/nix/path-info.cc b/src/nix/path-info.cc
new file mode 100644
index 000000000000..c61fe7ff1e00
--- /dev/null
+++ b/src/nix/path-info.cc
@@ -0,0 +1,85 @@
+#include "command.hh"
+#include "shared.hh"
+#include "store-api.hh"
+
+#include <iomanip>
+#include <algorithm>
+
+using namespace nix;
+
+struct CmdPathInfo : StorePathsCommand
+{
+    bool showSize = false;
+    bool showClosureSize = false;
+    bool showSigs = false;
+
+    CmdPathInfo()
+    {
+        mkFlag('s', "size", "print size of the NAR dump of each path", &showSize);
+        mkFlag('S', "closure-size", "print sum size of the NAR dumps of the closure of each path", &showClosureSize);
+        mkFlag(0, "sigs", "show signatures", &showSigs);
+    }
+
+    std::string name() override
+    {
+        return "path-info";
+    }
+
+    std::string description() override
+    {
+        return "query information about store paths";
+    }
+
+    Examples examples() override
+    {
+        return {
+            Example{
+                "To show the closure sizes of every path in the current NixOS system closure, sorted by size:",
+                "nix path-info -rS /run/current-system | sort -nk2"
+            },
+            Example{
+                "To check the existence of a path in a binary cache:",
+                "nix path-info -r /nix/store/7qvk5c91...-geeqie-1.1 --store https://cache.nixos.org/"
+            },
+        };
+    }
+
+    void run(ref<Store> store, Paths storePaths) override
+    {
+        size_t pathLen = 0;
+        for (auto & storePath : storePaths)
+            pathLen = std::max(pathLen, storePath.size());
+
+        for (auto storePath : storePaths) {
+            auto info = store->queryPathInfo(storePath);
+            storePath = info->path; // FIXME: screws up padding
+
+            std::cout << storePath << std::string(std::max(0, (int) pathLen - (int) storePath.size()), ' ');
+
+            if (showSize) {
+                std::cout << '\t' << std::setw(11) << info->narSize;
+            }
+
+            if (showClosureSize) {
+                size_t totalSize = 0;
+                PathSet closure;
+                store->computeFSClosure(storePath, closure, false, false);
+                for (auto & p : closure)
+                    totalSize += store->queryPathInfo(p)->narSize;
+                std::cout << '\t' << std::setw(11) << totalSize;
+            }
+
+            if (showSigs) {
+                std::cout << '\t';
+                Strings ss;
+                if (info->ultimate) ss.push_back("ultimate");
+                for (auto & sig : info->sigs) ss.push_back(sig);
+                std::cout << concatStringsSep(" ", ss);
+            }
+
+            std::cout << std::endl;
+        }
+    }
+};
+
+static RegisterCommand r1(make_ref<CmdPathInfo>());
diff --git a/src/nix/progress-bar.cc b/src/nix/progress-bar.cc
index ed7b578e2f49..659d6572ad93 100644
--- a/src/nix/progress-bar.cc
+++ b/src/nix/progress-bar.cc
@@ -1,72 +1,157 @@
 #include "progress-bar.hh"
+#include "util.hh"
+#include "sync.hh"
 
-#include <iostream>
+#include <map>
 
 namespace nix {
 
-ProgressBar::ProgressBar()
+class ProgressBar : public Logger
 {
-    _writeToStderr = [&](const unsigned char * buf, size_t count) {
-        auto state_(state.lock());
-        assert(!state_->done);
-        std::cerr << "\r\e[K" << std::string((const char *) buf, count);
-        render(*state_);
+private:
+
+    struct ActInfo
+    {
+        Activity * activity;
+        Verbosity lvl;
+        std::string s;
     };
-}
 
-ProgressBar::~ProgressBar()
-{
-    done();
-}
+    struct Progress
+    {
+        uint64_t expected = 0, progress = 0;
+    };
 
-void ProgressBar::updateStatus(const std::string & s)
-{
-    auto state_(state.lock());
-    assert(!state_->done);
-    state_->status = s;
-    render(*state_);
-}
+    struct State
+    {
+        std::list<ActInfo> activities;
+        std::map<Activity *, std::list<ActInfo>::iterator> its;
+        std::map<std::string, Progress> progress;
+    };
 
-void ProgressBar::done()
-{
-    auto state_(state.lock());
-    assert(state_->activities.empty());
-    state_->done = true;
-    std::cerr << "\r\e[K";
-    std::cerr.flush();
-    _writeToStderr = decltype(_writeToStderr)();
-}
+    Sync<State> state_;
 
-void ProgressBar::render(State & state_)
-{
-    std::cerr << '\r' << state_.status;
-    if (!state_.activities.empty()) {
-        if (!state_.status.empty()) std::cerr << ' ';
-        std::cerr << *state_.activities.rbegin();
+public:
+
+    ~ProgressBar()
+    {
+        auto state(state_.lock());
+        assert(state->activities.empty());
+        writeToStderr("\r\e[K");
     }
-    std::cerr << "\e[K";
-    std::cerr.flush();
-}
 
+    void log(Verbosity lvl, const FormatOrString & fs) override
+    {
+        auto state(state_.lock());
+        log(*state, lvl, fs.s);
+    }
 
-ProgressBar::Activity ProgressBar::startActivity(const FormatOrString & fs)
-{
-    return Activity(*this, fs);
-}
+    void log(State & state, Verbosity lvl, const std::string & s)
+    {
+        writeToStderr("\r\e[K" + s + "\n");
+        update(state);
+    }
+
+    void startActivity(Activity & activity, Verbosity lvl, const FormatOrString & fs) override
+    {
+        if (lvl > verbosity) return;
+        auto state(state_.lock());
+        state->activities.emplace_back(ActInfo{&activity, lvl, fs.s});
+        state->its.emplace(&activity, std::prev(state->activities.end()));
+        update(*state);
+    }
+
+    void stopActivity(Activity & activity) override
+    {
+        auto state(state_.lock());
+        auto i = state->its.find(&activity);
+        if (i == state->its.end()) return;
+        state->activities.erase(i->second);
+        state->its.erase(i);
+        update(*state);
+    }
+
+    void setExpected(const std::string & label, uint64_t value) override
+    {
+        auto state(state_.lock());
+        state->progress[label].expected = value;
+    }
+
+    void setProgress(const std::string & label, uint64_t value) override
+    {
+        auto state(state_.lock());
+        state->progress[label].progress = value;
+    }
+
+    void incExpected(const std::string & label, uint64_t value) override
+    {
+        auto state(state_.lock());
+        state->progress[label].expected += value;
+    }
+
+    void incProgress(const std::string & label, uint64_t value)
+    {
+        auto state(state_.lock());
+        state->progress[label].progress += value;
+    }
+
+    void update()
+    {
+        auto state(state_.lock());
+    }
+
+    void update(State & state)
+    {
+        std::string line = "\r";
+
+        std::string status = getStatus(state);
+        if (!status.empty()) {
+            line += '[';
+            line += status;
+            line += "]";
+        }
+
+        if (!state.activities.empty()) {
+            if (!status.empty()) line += " ";
+            line += state.activities.rbegin()->s;
+        }
+
+        line += "\e[K";
+        writeToStderr(line);
+    }
+
+    std::string getStatus(State & state)
+    {
+        std::string res;
+        for (auto & p : state.progress)
+            if (p.second.expected || p.second.progress) {
+                if (!res.empty()) res += ", ";
+                res += std::to_string(p.second.progress);
+                if (p.second.expected) {
+                    res += "/";
+                    res += std::to_string(p.second.expected);
+                }
+                res += " "; res += p.first;
+            }
+        return res;
+    }
+};
 
-ProgressBar::Activity::Activity(ProgressBar & pb, const FormatOrString & fs)
-    : pb(pb)
+StartProgressBar::StartProgressBar()
 {
-    auto state_(pb.state.lock());
-    state_->activities.push_back(fs.s);
-    it = state_->activities.end(); --it;
-    pb.render(*state_);
+    if (isatty(STDERR_FILENO)) {
+        prev = logger;
+        logger = new ProgressBar();
+    }
 }
 
-ProgressBar::Activity::~Activity()
+StartProgressBar::~StartProgressBar()
 {
-    auto state_(pb.state.lock());
-    state_->activities.erase(it);
+    if (prev) {
+        auto bar = logger;
+        logger = prev;
+        delete bar;
+    }
 }
 
 }
diff --git a/src/nix/progress-bar.hh b/src/nix/progress-bar.hh
index 2dda24346c90..d2e44f7c4fd9 100644
--- a/src/nix/progress-bar.hh
+++ b/src/nix/progress-bar.hh
@@ -1,49 +1,15 @@
 #pragma once
 
-#include "sync.hh"
-#include "util.hh"
+#include "logging.hh"
 
 namespace nix {
 
-class ProgressBar
+class StartProgressBar
 {
-private:
-    struct State
-    {
-        std::string status;
-        bool done = false;
-        std::list<std::string> activities;
-    };
-
-    Sync<State> state;
-
+    Logger * prev = 0;
 public:
-
-    ProgressBar();
-
-    ~ProgressBar();
-
-    void updateStatus(const std::string & s);
-
-    void done();
-
-    class Activity
-    {
-        friend class ProgressBar;
-    private:
-        ProgressBar & pb;
-        std::list<std::string>::iterator it;
-        Activity(ProgressBar & pb, const FormatOrString & fs);
-    public:
-        ~Activity();
-    };
-
-    Activity startActivity(const FormatOrString & fs);
-
-private:
-
-    void render(State & state_);
-
+    StartProgressBar();
+    ~StartProgressBar();
 };
 
 }
diff --git a/src/nix/sigs.cc b/src/nix/sigs.cc
index bcc46c3e7d4f..9932aa4a9eb0 100644
--- a/src/nix/sigs.cc
+++ b/src/nix/sigs.cc
@@ -1,6 +1,4 @@
-#include "affinity.hh" // FIXME
 #include "command.hh"
-#include "progress-bar.hh"
 #include "shared.hh"
 #include "store-api.hh"
 #include "thread-pool.hh"
@@ -31,8 +29,6 @@ struct CmdCopySigs : StorePathsCommand
 
     void run(ref<Store> store, Paths storePaths) override
     {
-        restoreAffinity(); // FIXME
-
         if (substituterUris.empty())
             throw UsageError("you must specify at least one substituter using ‘-s’");
 
@@ -41,21 +37,15 @@ struct CmdCopySigs : StorePathsCommand
         for (auto & s : substituterUris)
             substituters.push_back(openStoreAt(s));
 
-        ProgressBar progressBar;
-
         ThreadPool pool;
 
-        std::atomic<size_t> done{0};
+        std::string doneLabel = "done";
         std::atomic<size_t> added{0};
 
-        auto showProgress = [&]() {
-            return (format("[%d/%d done]") % done % storePaths.size()).str();
-        };
-
-        progressBar.updateStatus(showProgress());
+        logger->setExpected(doneLabel, storePaths.size());
 
         auto doPath = [&](const Path & storePath) {
-            auto activity(progressBar.startActivity(format("getting signatures for ‘%s’") % storePath));
+            Activity act(*logger, lvlInfo, format("getting signatures for ‘%s’") % storePath);
 
             checkInterrupt();
 
@@ -64,19 +54,21 @@ struct CmdCopySigs : StorePathsCommand
             StringSet newSigs;
 
             for (auto & store2 : substituters) {
-                if (!store2->isValidPath(storePath)) continue;
-                auto info2 = store2->queryPathInfo(storePath);
-
-                /* Don't import signatures that don't match this
-                   binary. */
-                if (info.narHash != info2.narHash ||
-                    info.narSize != info2.narSize ||
-                    info.references != info2.references)
-                    continue;
-
-                for (auto & sig : info2.sigs)
-                    if (!info.sigs.count(sig))
-                        newSigs.insert(sig);
+                try {
+                    auto info2 = store2->queryPathInfo(storePath);
+
+                    /* Don't import signatures that don't match this
+                       binary. */
+                    if (info->narHash != info2->narHash ||
+                        info->narSize != info2->narSize ||
+                        info->references != info2->references)
+                        continue;
+
+                    for (auto & sig : info2->sigs)
+                        if (!info->sigs.count(sig))
+                            newSigs.insert(sig);
+                } catch (InvalidPath &) {
+                }
             }
 
             if (!newSigs.empty()) {
@@ -84,8 +76,7 @@ struct CmdCopySigs : StorePathsCommand
                 added += newSigs.size();
             }
 
-            done++;
-            progressBar.updateStatus(showProgress());
+            logger->incProgress(doneLabel);
         };
 
         for (auto & storePath : storePaths)
@@ -93,45 +84,12 @@ struct CmdCopySigs : StorePathsCommand
 
         pool.process();
 
-        progressBar.done();
-
         printMsg(lvlInfo, format("imported %d signatures") % added);
     }
 };
 
 static RegisterCommand r1(make_ref<CmdCopySigs>());
 
-struct CmdQueryPathSigs : StorePathsCommand
-{
-    CmdQueryPathSigs()
-    {
-    }
-
-    std::string name() override
-    {
-        return "query-path-sigs";
-    }
-
-    std::string description() override
-    {
-        return "print store path signatures";
-    }
-
-    void run(ref<Store> store, Paths storePaths) override
-    {
-        for (auto & storePath : storePaths) {
-            auto info = store->queryPathInfo(storePath);
-            std::cout << storePath << " ";
-            if (info.ultimate) std::cout << "ultimate ";
-            for (auto & sig : info.sigs)
-                std::cout << sig << " ";
-            std::cout << "\n";
-        }
-    }
-};
-
-static RegisterCommand r2(make_ref<CmdQueryPathSigs>());
-
 struct CmdSignPaths : StorePathsCommand
 {
     Path secretKeyFile;
@@ -163,12 +121,12 @@ struct CmdSignPaths : StorePathsCommand
         for (auto & storePath : storePaths) {
             auto info = store->queryPathInfo(storePath);
 
-            auto info2(info);
+            auto info2(*info);
             info2.sigs.clear();
             info2.sign(secretKey);
             assert(!info2.sigs.empty());
 
-            if (!info.sigs.count(*info2.sigs.begin())) {
+            if (!info->sigs.count(*info2.sigs.begin())) {
                 store->addSignatures(storePath, info2.sigs);
                 added++;
             }
diff --git a/src/nix/verify.cc b/src/nix/verify.cc
index 39a4395cfe5b..fd904f465687 100644
--- a/src/nix/verify.cc
+++ b/src/nix/verify.cc
@@ -1,6 +1,4 @@
-#include "affinity.hh" // FIXME
 #include "command.hh"
-#include "progress-bar.hh"
 #include "shared.hh"
 #include "store-api.hh"
 #include "sync.hh"
@@ -36,40 +34,38 @@ struct CmdVerify : StorePathsCommand
         return "verify the integrity of store paths";
     }
 
-    void run(ref<Store> store, Paths storePaths) override
+    Examples examples() override
     {
-        restoreAffinity(); // FIXME
+        return {
+            Example{
+                "To verify the entire Nix store:",
+                "nix verify --all"
+            },
+            Example{
+                "To check whether each path in the closure of Firefox has at least 2 signatures:",
+                "nix verify -r -n2 --no-contents $(type -p firefox)"
+            },
+        };
+    }
 
+    void run(ref<Store> store, Paths storePaths) override
+    {
         std::vector<ref<Store>> substituters;
         for (auto & s : substituterUris)
             substituters.push_back(openStoreAt(s));
 
         auto publicKeys = getDefaultPublicKeys();
 
+        std::atomic<size_t> done{0};
         std::atomic<size_t> untrusted{0};
         std::atomic<size_t> corrupted{0};
-        std::atomic<size_t> done{0};
         std::atomic<size_t> failed{0};
 
-        ProgressBar progressBar;
-
-        auto showProgress = [&](bool final) {
-            std::string s;
-            if (final)
-                s = (format("checked %d paths") % storePaths.size()).str();
-            else
-                s = (format("[%d/%d checked") % done % storePaths.size()).str();
-            if (corrupted > 0)
-                s += (format(", %d corrupted") % corrupted).str();
-            if (untrusted > 0)
-                s += (format(", %d untrusted") % untrusted).str();
-            if (failed > 0)
-                s += (format(", %d failed") % failed).str();
-            if (!final) s += "]";
-            return s;
-        };
-
-        progressBar.updateStatus(showProgress(false));
+        std::string doneLabel("paths checked");
+        std::string untrustedLabel("untrusted");
+        std::string corruptedLabel("corrupted");
+        std::string failedLabel("failed");
+        logger->setExpected(doneLabel, storePaths.size());
 
         ThreadPool pool;
 
@@ -77,22 +73,23 @@ struct CmdVerify : StorePathsCommand
             try {
                 checkInterrupt();
 
-                auto activity(progressBar.startActivity(format("checking ‘%s’") % storePath));
+                Activity act(*logger, lvlInfo, format("checking ‘%s’") % storePath);
 
                 auto info = store->queryPathInfo(storePath);
 
                 if (!noContents) {
 
-                    HashSink sink(info.narHash.type);
-                    store->narFromPath(storePath, sink);
+                    HashSink sink(info->narHash.type);
+                    store->narFromPath(info->path, sink);
 
                     auto hash = sink.finish();
 
-                    if (hash.first != info.narHash) {
+                    if (hash.first != info->narHash) {
+                        logger->incProgress(corruptedLabel);
                         corrupted = 1;
                         printMsg(lvlError,
                             format("path ‘%s’ was modified! expected hash ‘%s’, got ‘%s’")
-                            % storePath % printHash(info.narHash) % printHash(hash.first));
+                            % info->path % printHash(info->narHash) % printHash(hash.first));
                     }
 
                 }
@@ -101,7 +98,7 @@ struct CmdVerify : StorePathsCommand
 
                     bool good = false;
 
-                    if (info.ultimate && !sigsNeeded)
+                    if (info->ultimate && !sigsNeeded)
                         good = true;
 
                     else {
@@ -114,18 +111,18 @@ struct CmdVerify : StorePathsCommand
                             for (auto sig : sigs) {
                                 if (sigsSeen.count(sig)) continue;
                                 sigsSeen.insert(sig);
-                                if (info.checkSignature(publicKeys, sig))
+                                if (info->checkSignature(publicKeys, sig))
                                     validSigs++;
                             }
                         };
 
-                        doSigs(info.sigs);
+                        doSigs(info->sigs);
 
                         for (auto & store2 : substituters) {
                             if (validSigs >= actualSigsNeeded) break;
                             try {
-                                if (!store2->isValidPath(storePath)) continue;
-                                doSigs(store2->queryPathInfo(storePath).sigs);
+                                doSigs(store2->queryPathInfo(info->path)->sigs);
+                            } catch (InvalidPath &) {
                             } catch (Error & e) {
                                 printMsg(lvlError, format(ANSI_RED "error:" ANSI_NORMAL " %s") % e.what());
                             }
@@ -136,18 +133,19 @@ struct CmdVerify : StorePathsCommand
                     }
 
                     if (!good) {
+                        logger->incProgress(untrustedLabel);
                         untrusted++;
-                        printMsg(lvlError, format("path ‘%s’ is untrusted") % storePath);
+                        printMsg(lvlError, format("path ‘%s’ is untrusted") % info->path);
                     }
 
                 }
 
+                logger->incProgress(doneLabel);
                 done++;
 
-                progressBar.updateStatus(showProgress(false));
-
             } catch (Error & e) {
                 printMsg(lvlError, format(ANSI_RED "error:" ANSI_NORMAL " %s") % e.what());
+                logger->incProgress(failedLabel);
                 failed++;
             }
         };
@@ -157,9 +155,8 @@ struct CmdVerify : StorePathsCommand
 
         pool.process();
 
-        progressBar.done();
-
-        printMsg(lvlInfo, showProgress(true));
+        printMsg(lvlInfo, format("%d paths checked, %d untrusted, %d corrupted, %d failed")
+            % done % untrusted % corrupted % failed);
 
         throw Exit(
             (corrupted ? 1 : 0) |