sandbox: Improve MountMap to always return entries sorted by path depth and lexicographical order. This prevents certain edge cases in the sandbox, where a mounted child directory could be hidden by a later mount of a parent directory over its parent.

--
MOS_MIGRATED_REVID=104749937

4 files changed, 143 insertions, 96 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java b/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java
index 945f267f03..a7657ad6af 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java
@@ -193,7 +193,7 @@ public class LinuxSandboxedStrategy implements SpawnActionContext {
 
   private ImmutableMap<Path, Path> getMounts(
       Spawn spawn, ActionExecutionContext executionContext) throws IOException {
-    MountMap<Path, Path> mounts = new MountMap<>();
+    MountMap mounts = new MountMap();
     mounts.putAll(mountUsualUnixDirs());
     mounts.putAll(withRecursedDirs(setupBlazeUtils()));
     mounts.putAll(withRecursedDirs(mountRunfilesFromManifests(spawn)));
@@ -230,9 +230,8 @@ public class LinuxSandboxedStrategy implements SpawnActionContext {
    * @return a new mounts multimap with the added mounts.
    */
   @VisibleForTesting
-  static MountMap<Path, Path> withResolvedSymlinks(Map<Path, Path> mounts)
-      throws IOException {
-    MountMap<Path, Path> fixedMounts = new MountMap<>();
+  static MountMap withResolvedSymlinks(Map<Path, Path> mounts) throws IOException {
+    MountMap fixedMounts = new MountMap();
     for (Entry<Path, Path> mount : mounts.entrySet()) {
       Path target = mount.getKey();
       Path source = mount.getValue();
@@ -253,8 +252,8 @@ public class LinuxSandboxedStrategy implements SpawnActionContext {
    * @return a new mounts multimap with the added mounts.
    */
   @VisibleForTesting
-  static MountMap<Path, Path> withRecursedDirs(Map<Path, Path> mounts) throws IOException {
-    MountMap<Path, Path> fixedMounts = new MountMap<>();
+  static MountMap withRecursedDirs(Map<Path, Path> mounts) throws IOException {
+    MountMap fixedMounts = new MountMap();
     for (Entry<Path, Path> mount : mounts.entrySet()) {
       Path target = mount.getKey();
       Path source = mount.getValue();
@@ -275,8 +274,8 @@ public class LinuxSandboxedStrategy implements SpawnActionContext {
    * Mount a certain set of unix directories to make the usual tools and libraries available to the
    * spawn that runs.
    */
-  private MountMap<Path, Path> mountUsualUnixDirs() throws IOException {
-    MountMap<Path, Path> mounts = new MountMap<>();
+  private MountMap mountUsualUnixDirs() throws IOException {
+    MountMap mounts = new MountMap();
     FileSystem fs = blazeDirs.getFileSystem();
     mounts.put(fs.getPath("/bin"), fs.getPath("/bin"));
     mounts.put(fs.getPath("/etc"), fs.getPath("/etc"));
@@ -298,8 +297,8 @@ public class LinuxSandboxedStrategy implements SpawnActionContext {
   /**
    * Mount the embedded tools.
    */
-  private MountMap<Path, Path> setupBlazeUtils() throws IOException {
-    MountMap<Path, Path> mounts = new MountMap<>();
+  private MountMap setupBlazeUtils() throws IOException {
+    MountMap mounts = new MountMap();
     Path mount = blazeDirs.getEmbeddedBinariesRoot().getRelative("build-runfiles");
     mounts.put(mount, mount);
     return mounts;
@@ -308,9 +307,8 @@ public class LinuxSandboxedStrategy implements SpawnActionContext {
   /**
    * Mount all runfiles that the spawn needs as specified in its runfiles manifests.
    */
-  private MountMap<Path, Path> mountRunfilesFromManifests(Spawn spawn)
-      throws IOException {
-    MountMap<Path, Path> mounts = new MountMap<>();
+  private MountMap mountRunfilesFromManifests(Spawn spawn) throws IOException {
+    MountMap mounts = new MountMap();
     for (Entry<PathFragment, Artifact> manifest : spawn.getRunfilesManifests().entrySet()) {
       String manifestFilePath = manifest.getValue().getPath().getPathString();
       Preconditions.checkState(!manifest.getKey().isAbsolute());
@@ -321,9 +319,8 @@ public class LinuxSandboxedStrategy implements SpawnActionContext {
     return mounts;
   }
 
-  static MountMap<Path, Path> parseManifestFile(
-      Path targetDirectory, File manifestFile) throws IOException {
-    MountMap<Path, Path> mounts = new MountMap<>();
+  static MountMap parseManifestFile(Path targetDirectory, File manifestFile) throws IOException {
+    MountMap mounts = new MountMap();
     for (String line : Files.readLines(manifestFile, Charset.defaultCharset())) {
       String[] fields = line.trim().split(" ");
       Path source;
@@ -346,9 +343,8 @@ public class LinuxSandboxedStrategy implements SpawnActionContext {
   /**
    * Mount all runfiles that the spawn needs as specified via its runfiles suppliers.
    */
-  private MountMap<Path, Path> mountRunfilesFromSuppliers(Spawn spawn)
-      throws IOException {
-    MountMap<Path, Path> mounts = new MountMap<>();
+  private MountMap mountRunfilesFromSuppliers(Spawn spawn) throws IOException {
+    MountMap mounts = new MountMap();
     FileSystem fs = blazeDirs.getFileSystem();
     Map<PathFragment, Map<PathFragment, Artifact>> rootsAndMappings =
         spawn.getRunfilesSupplier().getMappings();
@@ -370,10 +366,9 @@ public class LinuxSandboxedStrategy implements SpawnActionContext {
   /**
    * Mount all inputs of the spawn.
    */
-  private MountMap<Path, Path> mountInputs(
-      Spawn spawn, ActionExecutionContext actionExecutionContext)
+  private MountMap mountInputs(Spawn spawn, ActionExecutionContext actionExecutionContext)
       throws IOException {
-    MountMap<Path, Path> mounts = new MountMap<>();
+    MountMap mounts = new MountMap();
 
     List<ActionInput> inputs =
         ActionInputHelper.expandMiddlemen(
@@ -404,8 +399,8 @@ public class LinuxSandboxedStrategy implements SpawnActionContext {
    * <p>If --run_under= refers to a label, it is automatically provided in the spawn's input files,
    * so mountInputs() will catch that case.
    */
-  private MountMap<Path, Path> mountRunUnderCommand(Spawn spawn) {
-    MountMap<Path, Path> mounts = new MountMap<>();
+  private MountMap mountRunUnderCommand(Spawn spawn) {
+    MountMap mounts = new MountMap();
 
     if (spawn.getResourceOwner() instanceof TestRunnerAction) {
       TestRunnerAction testRunnerAction = ((TestRunnerAction) spawn.getResourceOwner());
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/MountMap.java b/src/main/java/com/google/devtools/build/lib/sandbox/MountMap.java
index 4e0ae07e41..5051d27df3 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/MountMap.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/MountMap.java
@@ -13,26 +13,30 @@
 // limitations under the License.
 package com.google.devtools.build.lib.sandbox;
 
-import com.google.common.collect.ForwardingMap;
+import com.google.common.collect.ForwardingSortedMap;
+import com.google.devtools.build.lib.vfs.Path;
 
-import java.util.LinkedHashMap;
 import java.util.Map;
+import java.util.SortedMap;
+import java.util.TreeMap;
 
 /**
  * A map that throws an exception when trying to replace a key (i.e. once a key gets a value,
  * any additional attempt of putting a value on the same key will throw an exception).
+ *
+ * <p>Returns entries sorted by path depth (shorter paths first) and in lexicographical order.
  */
-final class MountMap<K, V> extends ForwardingMap<K, V> {
-  final LinkedHashMap<K, V> delegate = new LinkedHashMap<>();
+final class MountMap extends ForwardingSortedMap<Path, Path> {
+  final TreeMap<Path, Path> delegate = new TreeMap<>();
 
   @Override
-  protected Map<K, V> delegate() {
+  protected SortedMap<Path, Path> delegate() {
     return delegate;
   }
 
   @Override
-  public V put(K key, V value) {
-    V previousValue = get(key);
+  public Path put(Path key, Path value) {
+    Path previousValue = get(key);
     if (previousValue == null) {
       return super.put(key, value);
     } else if (previousValue.equals(value)) {
@@ -44,8 +48,8 @@ final class MountMap<K, V> extends ForwardingMap<K, V> {
   }
 
   @Override
-  public void putAll(Map<? extends K, ? extends V> map) {
-    for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
+  public void putAll(Map<? extends Path, ? extends Path> map) {
+    for (Entry<? extends Path, ? extends Path> entry : map.entrySet()) {
       put(entry.getKey(), entry.getValue());
     }
   }
diff --git a/src/test/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategyTest.java b/src/test/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategyTest.java
index b5bcace951..74016762f4 100644
--- a/src/test/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategyTest.java
@@ -240,9 +240,7 @@ public class LinuxSandboxedStrategyTest extends LinuxSandboxedStrategyTestCase {
         Charset.defaultCharset(),
         String.format("x/testfile %s\nx/emptyfile \n", testFile.getPathString()));
 
-    MountMap<Path, Path> mounts =
-        LinuxSandboxedStrategy.parseManifestFile(
-            targetDir, manifestFile.getPathFile());
+    Map mounts = LinuxSandboxedStrategy.parseManifestFile(targetDir, manifestFile.getPathFile());
 
     assertThat(userFriendlyMap(mounts))
         .isEqualTo(
@@ -253,64 +251,4 @@ public class LinuxSandboxedStrategyTest extends LinuxSandboxedStrategyTestCase {
                     fileSystem.getPath("/runfiles/x/emptyfile"),
                     fileSystem.getPath("/dev/null"))));
   }
-
-  @Test
-  public void testMountMapWithNormalMounts() throws IOException {
-    // Allowed: Just two normal mounts (a -> sandbox/a, b -> sandbox/b)
-    MountMap<Path, Path> mounts = new MountMap<>();
-    mounts.put(fileSystem.getPath("/a"), workspaceDir.getRelative("a"));
-    mounts.put(fileSystem.getPath("/b"), workspaceDir.getRelative("b"));
-    assertThat(mounts)
-        .isEqualTo(
-            ImmutableMap.of(
-                fileSystem.getPath("/a"), workspaceDir.getRelative("a"),
-                fileSystem.getPath("/b"), workspaceDir.getRelative("b")));
-  }
-
-  @Test
-  public void testMountMapWithSameMountTwice() throws IOException {
-    // Allowed: Mount same thing twice (a -> sandbox/a, a -> sandbox/a, b -> sandbox/b)
-    MountMap<Path, Path> mounts = new MountMap<>();
-    mounts.put(fileSystem.getPath("/a"), workspaceDir.getRelative("a"));
-    mounts.put(fileSystem.getPath("/a"), workspaceDir.getRelative("a"));
-    mounts.put(fileSystem.getPath("/b"), workspaceDir.getRelative("b"));
-    assertThat(mounts)
-        .isEqualTo(
-            ImmutableMap.of(
-                fileSystem.getPath("/a"), workspaceDir.getRelative("a"),
-                fileSystem.getPath("/b"), workspaceDir.getRelative("b")));
-  }
-
-  @Test
-  public void testMountMapWithOneThingTwoTargets() throws IOException {
-    // Allowed: Mount one thing in two targets (x -> sandbox/a, x -> sandbox/b)
-    MountMap<Path, Path> mounts = new MountMap<>();
-    mounts.put(fileSystem.getPath("/a"), workspaceDir.getRelative("x"));
-    mounts.put(fileSystem.getPath("/b"), workspaceDir.getRelative("x"));
-    assertThat(mounts)
-        .isEqualTo(
-            ImmutableMap.of(
-                fileSystem.getPath("/a"), workspaceDir.getRelative("x"),
-                fileSystem.getPath("/b"), workspaceDir.getRelative("x")));
-  }
-
-  @Test
-  public void testMountMapWithTwoThingsOneTarget() throws IOException {
-    // Forbidden: Mount two things onto the same target (x -> sandbox/a, y -> sandbox/a)
-    try {
-      MountMap<Path, Path> mounts = new MountMap<>();
-      mounts.put(fileSystem.getPath("/x"), workspaceDir.getRelative("a"));
-      mounts.put(fileSystem.getPath("/x"), workspaceDir.getRelative("b"));
-      fail();
-    } catch (IllegalArgumentException e) {
-      assertThat(e)
-          .hasMessage(
-              String.format(
-                  "Cannot mount both '%s' and '%s' onto '%s'",
-                  workspaceDir.getRelative("a"),
-                  workspaceDir.getRelative("b"),
-                  fileSystem.getPath("/x")));
-    }
-  }
-
 }
diff --git a/src/test/java/com/google/devtools/build/lib/sandbox/MountMapTest.java b/src/test/java/com/google/devtools/build/lib/sandbox/MountMapTest.java
new file mode 100644
index 0000000000..060eb6f264
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/sandbox/MountMapTest.java
@@ -0,0 +1,110 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.sandbox;
+
+import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.fail;
+
+import com.google.common.collect.ImmutableMap;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.io.IOException;
+
+/**
+ * Tests for {@code MountMap}.
+ */
+@RunWith(JUnit4.class)
+public class MountMapTest extends LinuxSandboxedStrategyTestCase {
+  @Test
+  public void testMountMapWithNormalMounts() throws IOException {
+    // Allowed: Just two normal mounts (a -> sandbox/a, b -> sandbox/b)
+    MountMap mounts = new MountMap();
+    mounts.put(fileSystem.getPath("/a"), workspaceDir.getRelative("a"));
+    mounts.put(fileSystem.getPath("/b"), workspaceDir.getRelative("b"));
+    assertThat(mounts)
+        .isEqualTo(
+            ImmutableMap.of(
+                fileSystem.getPath("/a"), workspaceDir.getRelative("a"),
+                fileSystem.getPath("/b"), workspaceDir.getRelative("b")));
+  }
+
+  @Test
+  public void testMountMapWithSameMountTwice() throws IOException {
+    // Allowed: Mount same thing twice (a -> sandbox/a, a -> sandbox/a, b -> sandbox/b)
+    MountMap mounts = new MountMap();
+    mounts.put(fileSystem.getPath("/a"), workspaceDir.getRelative("a"));
+    mounts.put(fileSystem.getPath("/a"), workspaceDir.getRelative("a"));
+    mounts.put(fileSystem.getPath("/b"), workspaceDir.getRelative("b"));
+    assertThat(mounts)
+        .isEqualTo(
+            ImmutableMap.of(
+                fileSystem.getPath("/a"), workspaceDir.getRelative("a"),
+                fileSystem.getPath("/b"), workspaceDir.getRelative("b")));
+  }
+
+  @Test
+  public void testMountMapWithOneThingTwoTargets() throws IOException {
+    // Allowed: Mount one thing in two targets (x -> sandbox/a, x -> sandbox/b)
+    MountMap mounts = new MountMap();
+    mounts.put(fileSystem.getPath("/a"), workspaceDir.getRelative("x"));
+    mounts.put(fileSystem.getPath("/b"), workspaceDir.getRelative("x"));
+    assertThat(mounts)
+        .isEqualTo(
+            ImmutableMap.of(
+                fileSystem.getPath("/a"), workspaceDir.getRelative("x"),
+                fileSystem.getPath("/b"), workspaceDir.getRelative("x")));
+  }
+
+  @Test
+  public void testMountMapWithTwoThingsOneTarget() throws IOException {
+    // Forbidden: Mount two things onto the same target (x -> sandbox/a, y -> sandbox/a)
+    try {
+      MountMap mounts = new MountMap();
+      mounts.put(fileSystem.getPath("/x"), workspaceDir.getRelative("a"));
+      mounts.put(fileSystem.getPath("/x"), workspaceDir.getRelative("b"));
+      fail();
+    } catch (IllegalArgumentException e) {
+      assertThat(e)
+          .hasMessage(
+              String.format(
+                  "Cannot mount both '%s' and '%s' onto '%s'",
+                  workspaceDir.getRelative("a"),
+                  workspaceDir.getRelative("b"),
+                  fileSystem.getPath("/x")));
+    }
+  }
+
+  @Test
+  public void testMountMapGuaranteesOrdering() {
+    MountMap mounts = new MountMap();
+    mounts.put(fileSystem.getPath("/a/c"), workspaceDir.getRelative("x"));
+    mounts.put(fileSystem.getPath("/b"), workspaceDir.getRelative("x"));
+    mounts.put(fileSystem.getPath("/a/b"), workspaceDir.getRelative("x"));
+    mounts.put(fileSystem.getPath("/a"), workspaceDir.getRelative("x"));
+
+    assertThat(mounts.entrySet())
+        .containsExactlyElementsIn(
+            ImmutableMap.builder()
+                .put(fileSystem.getPath("/a"), workspaceDir.getRelative("x"))
+                .put(fileSystem.getPath("/a/b"), workspaceDir.getRelative("x"))
+                .put(fileSystem.getPath("/a/c"), workspaceDir.getRelative("x"))
+                .put(fileSystem.getPath("/b"), workspaceDir.getRelative("x"))
+                .build()
+                .entrySet())
+        .inOrder();
+  }
+}