* Start of concurrent garbage collection. Processes write temporary

  roots to a per-process temporary file in /nix/var/nix/temproots
  while holding a write lock on that file.  The garbage collector
  acquires read locks on all those files, thus blocking further
  progress in other Nix processes, and reads the sets of temporary
  roots.

4 files changed, 166 insertions, 98 deletions

diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index 52bd08bb1..dbfde447e 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -13,6 +13,7 @@
 #include "references.hh"
 #include "pathlocks.hh"
 #include "globals.hh"
+#include "gc.hh"
 
 
 /* !!! TODO derivationFromPath shouldn't be used here */
@@ -59,7 +60,6 @@ protected:
     /* Whether amDone() has been called. */
     bool done;
 
-    
     Goal(Worker & worker) : worker(worker)
     {
         done = false;
@@ -442,6 +442,10 @@ void DerivationGoal::haveStoreExpr()
     /* Get the derivation. */
     drv = derivationFromPath(drvPath);
 
+    for (DerivationOutputs::iterator i = drv.outputs.begin();
+         i != drv.outputs.end(); ++i)
+        addTempRoot(i->second.path);
+
     /* Check what outputs paths are not already valid. */
     PathSet invalidOutputs = checkPathValidity(false);
 
@@ -1308,6 +1312,8 @@ void SubstitutionGoal::init()
 {
     trace("init");
 
+    addTempRoot(storePath);
+    
     /* If the path already exists we're done. */
     if (isValidPath(storePath)) {
         amDone();
diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
index ba6e6bb9d..4c6a944b8 100644
--- a/src/libstore/gc.cc
+++ b/src/libstore/gc.cc
@@ -1,20 +1,146 @@
 #include "globals.hh"
 #include "gc.hh"
 #include "build.hh"
+#include "pathlocks.hh"
+
+#include <boost/shared_ptr.hpp>
 
 #include <sys/types.h>
 #include <sys/stat.h>
+#include <errno.h>
+#include <fcntl.h>
 #include <unistd.h>
 
 
+static string tempRootsDir = "temproots";
+
+/* The file to which we write our temporary roots. */
+Path fnTempRoots;
+static AutoCloseFD fdTempRoots;
+
+
+void addTempRoot(const Path & path)
+{
+    /* Create the temporary roots file for this process. */
+    if (fdTempRoots == -1) {
+
+        while (1) {
+            fnTempRoots = (format("%1%/%2%/%3%")
+                % nixStateDir % tempRootsDir % getpid()).str();
+        
+            fdTempRoots = open(fnTempRoots.c_str(), O_RDWR | O_CREAT | O_TRUNC, 0600);
+            if (fdTempRoots == -1)
+                throw SysError(format("opening temporary roots file `%1%'") % fnTempRoots);
+
+            debug(format("acquiring read lock on `%1%'") % fnTempRoots);
+            lockFile(fdTempRoots, ltRead, true);
+
+            /* Check whether the garbage collector didn't get in our
+               way. */
+            struct stat st;
+            if (fstat(fdTempRoots, &st) == -1)
+                throw SysError(format("statting `%1%'") % fnTempRoots);
+            if (st.st_size == 0) break;
+            
+            /* The garbage collector deleted this file before we could
+               get a lock.  (It won't delete the file after we get a
+               lock.)  Try again. */
+        }
+
+    }
+
+    /* Upgrade the lock to a write lock.  This will cause us to block
+       if the garbage collector is holding our lock. */
+    debug(format("acquiring write lock on `%1%'") % fnTempRoots);
+    lockFile(fdTempRoots, ltWrite, true);
+
+    string s = path + '\0';
+    writeFull(fdTempRoots, (const unsigned char *) s.c_str(), s.size());
+
+    /* Downgrade to a read lock. */
+    debug(format("downgrading to read lock on `%1%'") % fnTempRoots);
+    lockFile(fdTempRoots, ltRead, true);
+}
+
+
+typedef shared_ptr<AutoCloseFD> FDPtr;
+typedef list<FDPtr> FDs;
+
+
+static void readTempRoots(PathSet & tempRoots, FDs & fds)
+{
+    /* Read the `temproots' directory for per-process temporary root
+       files. */
+    Strings tempRootFiles = readDirectory(
+        (format("%1%/%2%") % nixStateDir % tempRootsDir).str());
+
+    for (Strings::iterator i = tempRootFiles.begin();
+         i != tempRootFiles.end(); ++i)
+    {
+        Path path = (format("%1%/%2%/%3%") % nixStateDir % tempRootsDir % *i).str();
+
+        debug(format("reading temporary root file `%1%'") % path);
+            
+        FDPtr fd(new AutoCloseFD(open(path.c_str(), O_RDWR, 0666)));
+        if (*fd == -1) {
+            /* It's okay if the file has disappeared. */
+            if (errno == ENOENT) continue;
+            throw SysError(format("opening temporary roots file `%1%'") % path);
+        }
+
+        /* Try to acquire a write lock without blocking.  This can
+           only succeed if the owning process has died.  In that case
+           we don't care about its temporary roots. */
+        if (lockFile(*fd, ltWrite, false)) {
+            printMsg(lvlError, format("removing stale temporary roots file `%1%'")
+                % path);
+            /* !!! write token, unlink */
+            continue;
+        }
+
+        /* Acquire a read lock.  This will prevent the owning process
+           from upgrading to a write lock, therefore it will block in
+           addTempRoot(). */
+        debug(format("waiting for read lock on `%1%'") % path);
+        lockFile(*fd, ltRead, true);
+
+        /* Read the entire file. */
+        struct stat st;
+        if (fstat(*fd, &st) == -1)
+            throw SysError(format("statting `%1%'") % path);
+        unsigned char buf[st.st_size]; /* !!! stack space */
+        readFull(*fd, buf, st.st_size);
+        debug(format("FILE SIZE %1%") % st.st_size);
+
+        /* Extract the roots. */
+        string contents((char *) buf, st.st_size);
+        unsigned int pos = 0, end;
+
+        while ((end = contents.find((char) 0, pos)) != string::npos) {
+            Path root(contents, pos, end - pos);
+            debug(format("got temporary root `%1%'") % root);
+            assertStorePath(root);
+            tempRoots.insert(root);
+            pos = end + 1;
+        }
+
+        fds.push_back(fd); /* keep open */
+    }
+}
+
+
 void collectGarbage(const PathSet & roots, GCAction action,
     PathSet & result)
 {
     result.clear();
     
-    /* !!! TODO: Acquire an exclusive lock on the gcroots directory.
-       This prevents the set of live paths from increasing after this
-       point. */
+    /* !!! TODO: Acquire the global GC root.  This prevents
+       a) New roots from being added.
+       b) Processes from creating new temporary root files. */
+
+    /* !!! Restrict read permission on the GC root.  Otherwise any
+       process that can open the file for reading can DoS the
+       collector. */
     
     /* Determine the live paths which is just the closure of the
        roots under the `references' relation. */
@@ -27,6 +153,16 @@ void collectGarbage(const PathSet & roots, GCAction action,
         return;
     }
 
+    /* Read the temporary roots.  This acquires read locks on all
+       per-process temporary root files.  So after this point no paths
+       can be added to the set of temporary roots. */
+    PathSet tempRoots;
+    FDs fds;
+    readTempRoots(tempRoots, fds);
+
+    for (FDs::iterator i = fds.begin(); i != fds.end(); ++i)
+        debug(format("FD %1%") % (int) **i);
+    
     /* !!! TODO: Try to acquire (without blocking) exclusive locks on
        the files in the `pending' directory.  Delete all files for
        which we managed to acquire such a lock (since if we could get
@@ -50,6 +186,11 @@ void collectGarbage(const PathSet & roots, GCAction action,
             continue;
         }
 
+        if (tempRoots.find(path) != tempRoots.end()) {
+            debug(format("temporary root `%1%'") % path);
+            continue;
+        }
+
         debug(format("dead path `%1%'") % path);
         result.insert(path);
 
@@ -57,100 +198,10 @@ void collectGarbage(const PathSet & roots, GCAction action,
             printMsg(lvlInfo, format("deleting `%1%'") % path);
             deleteFromStore(path);
         }
-        
-    }
-}
-
-
-
-#if 0
-void followLivePaths(Path nePath, PathSet & live)
-{
-    /* Just to be sure, canonicalise the path.  It is important to do
-       this here and in findDeadPath() to ensure that a live path is
-       not mistaken for a dead path due to some non-canonical
-       representation. */
-    nePath = canonPath(nePath);
-    
-    if (live.find(nePath) != live.end()) return;
-    live.insert(nePath);
-
-    startNest(nest, lvlDebug, format("following `%1%'") % nePath);
-    assertStorePath(nePath);
-
-    if (isValidPath(nePath)) {
-
-        /* !!! should make sure that no substitutes are used */
-        StoreExpr ne = storeExprFromPath(nePath);
-
-        /* !!! painfully similar to requisitesWorker() */
-        if (ne.type == StoreExpr::neClosure)
-            for (ClosureElems::iterator i = ne.closure.elems.begin();
-                 i != ne.closure.elems.end(); ++i)
-            {
-                Path p = canonPath(i->first);
-                if (live.find(p) == live.end()) {
-                    debug(format("found live `%1%'") % p);
-                    assertStorePath(p);
-                    live.insert(p);
-                }
-            }
-    
-        else if (ne.type == StoreExpr::neDerivation)
-            for (PathSet::iterator i = ne.derivation.inputs.begin();
-                 i != ne.derivation.inputs.end(); ++i)
-                followLivePaths(*i, live);
-
-        else abort();
-        
-    }
-
-    Path nfPath;
-    if (querySuccessor(nePath, nfPath))
-        followLivePaths(nfPath, live);
-}
-
-
-PathSet findLivePaths(const Paths & roots)
-{
-    PathSet live;
-
-    startNest(nest, lvlDebug, "finding live paths");
-
-    for (Paths::const_iterator i = roots.begin(); i != roots.end(); ++i)
-        followLivePaths(*i, live);
-
-    return live;
-}
-
-
-PathSet findDeadPaths(const PathSet & live, time_t minAge)
-{
-    PathSet dead;
-
-    startNest(nest, lvlDebug, "finding dead paths");
 
-    time_t now = time(0);
-
-    Strings storeNames = readDirectory(nixStore);
-
-    for (Strings::iterator i = storeNames.begin(); i != storeNames.end(); ++i) {
-        Path p = canonPath(nixStore + "/" + *i);
-
-        if (minAge > 0) {
-            struct stat st;
-            if (lstat(p.c_str(), &st) != 0)
-                throw SysError(format("obtaining information about `%1%'") % p);
-            if (st.st_atime + minAge >= now) continue;
-        }
-        
-        if (live.find(p) == live.end()) {
-            debug(format("dead path `%1%'") % p);
-            dead.insert(p);
-        } else
-            debug(format("live path `%1%'") % p);
+        /* Only delete lock files if the path is belongs to doesn't
+           exist and isn't a temporary root and we can acquire an
+           exclusive lock on it. */
+        /* !!! */
     }
-    
-    return dead;
 }
-#endif
diff --git a/src/libstore/gc.hh b/src/libstore/gc.hh
index 2ea851abc..838188ade 100644
--- a/src/libstore/gc.hh
+++ b/src/libstore/gc.hh
@@ -3,6 +3,7 @@
 
 #include "util.hh"
 
+
 /* Garbage collector operation. */
 typedef enum { gcReturnLive, gcReturnDead, gcDeleteDead } GCAction;
 
@@ -14,4 +15,9 @@ typedef enum { gcReturnLive, gcReturnDead, gcDeleteDead } GCAction;
 void collectGarbage(const PathSet & roots, GCAction action,
     PathSet & result);
 
+/* Register a temporary GC root.  This root will automatically
+   disappear when this process exits. */
+void addTempRoot(const Path & path);
+
+
 #endif /* !__GC_H */
diff --git a/src/libstore/store.cc b/src/libstore/store.cc
index e676216c9..7c0faaf6c 100644
--- a/src/libstore/store.cc
+++ b/src/libstore/store.cc
@@ -12,6 +12,7 @@
 #include "db.hh"
 #include "archive.hh"
 #include "pathlocks.hh"
+#include "gc.hh"
 
 
 /* Nix database. */
@@ -468,6 +469,8 @@ Path addToStore(const Path & _srcPath)
     string baseName = baseNameOf(srcPath);
     Path dstPath = makeStorePath("source", h, baseName);
 
+    addTempRoot(dstPath);
+
     if (!readOnlyMode && !isValidPath(dstPath)) { 
 
         /* The first check above is an optimisation to prevent
@@ -512,6 +515,8 @@ Path addTextToStore(const string & suffix, const string & s,
 
     Path dstPath = makeStorePath("text", hash, suffix);
     
+    addTempRoot(dstPath);
+
     if (!readOnlyMode && !isValidPath(dstPath)) {
 
         PathSet lockPaths;