Make roots a map of store paths to pinning links

This new structure makes more sense as there may be many sources rooting
the same store path. Many profiles can reference the same path but this
is even more true with /proc/<pid>/maps where distinct pids can and
often do map the same store path.
This implementation is also more efficient as the `Roots` map contains
only one entry per rooted store path.

5 files changed, 39 insertions, 35 deletions

diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
index 73630f36d..da6799f6f 100644
--- a/src/libstore/gc.cc
+++ b/src/libstore/gc.cc
@@ -130,7 +130,7 @@ Path LocalFSStore::addPermRoot(const Path & _storePath,
        gcroots directory. */
     if (settings.checkRootReachability) {
         Roots roots = findRoots();
-        if (roots.find(gcRoot) == roots.end())
+        if (roots[storePath].count(gcRoot) == 0)
             printError(
                 format(
                     "warning: '%1%' is not in a directory where the garbage collector looks for roots; "
@@ -266,7 +266,7 @@ void LocalStore::findRoots(const Path & path, unsigned char type, Roots & roots)
     auto foundRoot = [&](const Path & path, const Path & target) {
         Path storePath = toStorePath(target);
         if (isStorePath(storePath) && isValidPath(storePath))
-            roots[path] = storePath;
+            roots[storePath].emplace(path);
         else
             printInfo(format("skipping invalid root from '%1%' to '%2%'") % path % storePath);
     };
@@ -306,7 +306,7 @@ void LocalStore::findRoots(const Path & path, unsigned char type, Roots & roots)
         else if (type == DT_REG) {
             Path storePath = storeDir + "/" + baseNameOf(path);
             if (isStorePath(storePath) && isValidPath(storePath))
-                roots[path] = storePath;
+                roots[storePath].emplace(path);
         }
 
     }
@@ -346,10 +346,10 @@ Roots LocalStore::findRoots()
     FDs fds;
     pid_t prev = -1;
     size_t n = 0;
-    for (auto & root : readTempRoots(fds)) {
-        if (prev != root.first) n = 0;
-        prev = root.first;
-        roots[fmt("{temp:%d:%d}", root.first, n++)] = root.second;
+    for (auto & [pid, root] : readTempRoots(fds)) {
+        if (prev != pid) n = 0;
+        prev = pid;
+        roots[root].emplace(fmt("{temp:%d:%d}", pid, n++));
     }
 
     return roots;
@@ -374,8 +374,8 @@ try_again:
         goto try_again;
     }
     if (res > 0 && buf[0] == '/')
-        roots.emplace((format("{memory:%1%") % file).str(),
-                std::string(static_cast<char *>(buf), res));
+        roots[std::string(static_cast<char *>(buf), res)]
+            .emplace((format("{memory:%1%") % file).str());
     return;
 }
 
@@ -388,7 +388,7 @@ static string quoteRegexChars(const string & raw)
 static void readFileRoots(const char * path, Roots & roots)
 {
     try {
-        roots.emplace(path, readFile(path));
+        roots[readFile(path)].emplace(path);
     } catch (SysError & e) {
         if (e.errNo != ENOENT && e.errNo != EACCES)
             throw;
@@ -434,19 +434,17 @@ void LocalStore::findRuntimeRoots(Roots & roots)
                 try {
                     auto mapFile = (format("/proc/%1%/maps") % ent->d_name).str();
                     auto mapLines = tokenizeString<std::vector<string>>(readFile(mapFile, true), "\n");
-                    int n = 0;
                     for (const auto& line : mapLines) {
                         auto match = std::smatch{};
                         if (std::regex_match(line, match, mapRegex))
-                            unchecked.emplace((format("{memory:%1%:%2%}") % mapFile % n++).str(), match[1]);
+                            unchecked[match[1]].emplace((format("{memory:%1%}") % mapFile).str());
                     }
 
                     auto envFile = (format("/proc/%1%/environ") % ent->d_name).str();
                     auto envString = readFile(envFile, true);
                     auto env_end = std::sregex_iterator{};
-                    n = 0;
                     for (auto i = std::sregex_iterator{envString.begin(), envString.end(), storePathRegex}; i != env_end; ++i)
-                        unchecked.emplace((format("{memory:%1%:%2%}") % envFile % n++).str(), i->str());
+                        unchecked[i->str()].emplace((format("{memory:%1%}") % envFile).str());
                 } catch (SysError & e) {
                     if (errno == ENOENT || errno == EACCES || errno == ESRCH)
                         continue;
@@ -463,11 +461,10 @@ void LocalStore::findRuntimeRoots(Roots & roots)
         std::regex lsofRegex(R"(^n(/.*)$)");
         auto lsofLines =
             tokenizeString<std::vector<string>>(runProgram(LSOF, true, { "-n", "-w", "-F", "n" }), "\n");
-        int n = 0;
         for (const auto & line : lsofLines) {
             std::smatch match;
             if (std::regex_match(line, match, lsofRegex))
-                unchecked.emplace((format("{memory:%1%:%2%}" % LSOF % n++).str(), match[1]);
+                unchecked[match[1]].emplace((format("{memory:%1%}" % LSOF).str());
         }
     } catch (ExecError & e) {
         /* lsof not installed, lsof failed */
@@ -480,12 +477,12 @@ void LocalStore::findRuntimeRoots(Roots & roots)
     readFileRoots("/proc/sys/kernel/poweroff_cmd", unchecked);
 #endif
 
-    for (auto & root : unchecked) {
-        if (isInStore(root.second)) {
-            Path path = toStorePath(root.second);
+    for (auto & [target, links] : unchecked) {
+        if (isInStore(target)) {
+            Path path = toStorePath(target);
             if (isStorePath(path) && isValidPath(path)) {
                 debug(format("got additional root '%1%'") % path);
-                roots.emplace(root.first, path);
+                roots[path].insert(links.begin(), links.end());
             }
         }
     }
@@ -757,7 +754,7 @@ void LocalStore::collectGarbage(const GCOptions & options, GCResults & results)
     printError(format("finding garbage collector roots..."));
     Roots rootMap = options.ignoreLiveness ? Roots() : findRootsNoTemp();
 
-    for (auto & i : rootMap) state.roots.insert(i.second);
+    for (auto & i : rootMap) state.roots.insert(i.first);
 
     /* Read the temporary roots.  This acquires read locks on all
        per-process temporary root files.  So after this point no paths
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index def140cfb..a4dd28af0 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -606,7 +606,7 @@ Roots RemoteStore::findRoots()
     while (count--) {
         Path link = readString(conn->from);
         Path target = readStorePath(*this, conn->from);
-        result[link] = target;
+        result[target].emplace(link);
     }
     return result;
 }
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index ad0f8df11..b4e5f5511 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -47,7 +47,7 @@ const size_t storePathHashLen = 32; // i.e. 160 bits
 const uint32_t exportMagic = 0x4558494e;
 
 
-typedef std::map<Path, Path> Roots;
+typedef std::map<Path, std::set<std::string>> Roots;
 
 
 struct GCOptions
diff --git a/src/nix-daemon/nix-daemon.cc b/src/nix-daemon/nix-daemon.cc
index faa23b268..014378d27 100644
--- a/src/nix-daemon/nix-daemon.cc
+++ b/src/nix-daemon/nix-daemon.cc
@@ -477,14 +477,19 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
         logger->startWork();
         Roots roots = store->findRoots();
         logger->stopWork();
-        to << roots.size();
+        size_t total_length = 0;
+        for (auto & root : roots)
+            total_length += root.second.size();
+        to << total_length;
         int n = 0;
-        for (auto & i : roots) {
-            // Obfuscate 'memory' roots as they exposes information about other users,
-            if (i.first.rfind("{memory:", 0) == 0) {
-               to << fmt("{memory:%d}", n++) << i.second;
-            } else {
-               to << i.first << i.second;
+        for (auto & [target, links] : roots) {
+            for (auto & link : links) {
+                // Obfuscate 'memory' roots as they expose information about other users,
+                if (link.rfind("{memory:", 0) == 0) {
+                    to << fmt("{memory:%d}", n++) << target;
+                } else {
+                    to << link << target;
+                }
             }
         }
         break;
diff --git a/src/nix-store/nix-store.cc b/src/nix-store/nix-store.cc
index 33138baff..b281ea2dd 100644
--- a/src/nix-store/nix-store.cc
+++ b/src/nix-store/nix-store.cc
@@ -428,9 +428,10 @@ static void opQuery(Strings opFlags, Strings opArgs)
                     referrers, true, settings.gcKeepOutputs, settings.gcKeepDerivations);
             }
             Roots roots = store->findRoots();
-            for (auto & i : roots)
-                if (referrers.find(i.second) != referrers.end())
-                    cout << format("%1%\n") % i.first;
+            for (auto & [path, roots] : roots)
+                if (referrers.find(path) != referrers.end())
+                    for (auto & root : roots)
+                        cout << format("%1% -> %2%\n") % root % path;
             break;
         }
 
@@ -591,8 +592,9 @@ static void opGC(Strings opFlags, Strings opArgs)
 
     if (printRoots) {
         Roots roots = store->findRoots();
-        for (auto & i : roots)
-            cout << i.first << " -> " << i.second << std::endl;
+        for (auto & [path, roots] : roots)
+            for (auto & root : roots)
+                cout << root << " -> " << path << std::endl;
     }
 
     else {