MetadataProvider now provides ActionInput lookup by exec path.

Adds a helper class, ActionInputMap to do this with minimal wrapping overhead.

PiperOrigin-RevId: 199391251

7 files changed, 446 insertions, 36 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionInputMap.java b/src/main/java/com/google/devtools/build/lib/actions/ActionInputMap.java
new file mode 100644
index 0000000000..c938b07419
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionInputMap.java
@@ -0,0 +1,164 @@
+// Copyright 2018 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.actions;
+
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.actions.cache.Metadata;
+import java.util.Arrays;
+import javax.annotation.Nullable;
+
+/**
+ * Helper for {@link MetadataProvider} implementations.
+ *
+ * <p>Allows {@link Metadata} lookups by exec path or {@link ActionInput}. <i>Also</i> allows {@link
+ * ActionInput} to be looked up by exec path.
+ *
+ * <p>This class is thread-compatible.
+ */
+public final class ActionInputMap implements MetadataProvider {
+  /**
+   * {@link ActionInput} keys stored in even indices
+   *
+   * <p>{@link Metadata} values stored in odd indices
+   */
+  private Object[] data;
+
+  /** Number of contained elements. */
+  private int size;
+
+  /** Length of data = 2^(numBits+1) */
+  private int numBits;
+
+  /** Mask to use to perform the modulo operation since the table size is a power of 2. */
+  private int mask;
+
+  public ActionInputMap(int sizeHint) {
+    this.numBits = 1;
+    while ((1 << numBits) <= sizeHint) {
+      ++numBits;
+    }
+    this.mask = (1 << numBits) - 1;
+    this.data = new Object[1 << (numBits + 1)];
+    this.size = 0;
+  }
+
+  @Nullable
+  @Override
+  public Metadata getMetadata(ActionInput input) {
+    return getMetadata(input.getExecPathString());
+  }
+
+  @Nullable
+  public Metadata getMetadata(String execPathString) {
+    int hashCode = execPathString.hashCode();
+    int probe = getProbe(hashCode);
+    ActionInput nextKey;
+    while ((nextKey = (ActionInput) data[probe]) != null) {
+      if (hashCode == nextKey.getExecPathString().hashCode()
+          && nextKey.getExecPathString().equals(execPathString)) {
+        return (Metadata) data[probe + 1];
+      }
+      probe = incProbe(probe);
+    }
+    return null;
+  }
+
+  @Nullable
+  @Override
+  public ActionInput getInput(String execPathString) {
+    int hashCode = execPathString.hashCode();
+    int probe = getProbe(hashCode);
+    ActionInput nextKey;
+    while ((nextKey = (ActionInput) data[probe]) != null) {
+      if (hashCode == nextKey.getExecPathString().hashCode()
+          && nextKey.getExecPathString().equals(execPathString)) {
+        return nextKey;
+      }
+      probe = incProbe(probe);
+    }
+    return null;
+  }
+
+  /** Count of contained entries. */
+  public int size() {
+    return size;
+  }
+
+  /** @return true if an entry was added, false if the map already contains {@code input} */
+  public boolean put(ActionInput input, Metadata metadata) {
+    Preconditions.checkNotNull(input);
+    if (size * 4 >= data.length) {
+      resize();
+    }
+    return putImpl(input, metadata);
+  }
+
+  public void clear() {
+    Arrays.fill(data, null);
+    size = 0;
+  }
+
+  private void resize() {
+    Object[] oldData = data;
+    int oldSize = size;
+    data = new Object[data.length * 2];
+    size = 0;
+    ++numBits;
+    mask = (1 << numBits) - 1;
+    for (int i = 0; i < oldData.length; i += 2) {
+      ActionInput key = (ActionInput) oldData[i];
+      if (key != null) {
+        Metadata value = (Metadata) oldData[i + 1];
+        putImpl(key, value);
+      }
+    }
+    Preconditions.checkState(size == oldSize, "size = %s, oldSize = %s", size, oldSize);
+  }
+
+  /**
+   * Unlike the public version, this doesn't resize.
+   *
+   * <p>REQUIRES: there are free positions in {@link data}.
+   */
+  private boolean putImpl(ActionInput key, Metadata value) {
+    int hashCode = key.getExecPathString().hashCode();
+    int probe = getProbe(hashCode);
+    while (true) {
+      ActionInput next = (ActionInput) data[probe];
+      if (next == null) {
+        data[probe] = key;
+        data[probe + 1] = value;
+        ++size;
+        return true;
+      }
+      if (hashCode == next.getExecPathString().hashCode()
+          && next.getExecPathString().equals(key.getExecPathString())) {
+        return false; // already present
+      }
+      probe = incProbe(probe);
+    }
+  }
+
+  private int getProbe(int hashCode) {
+    return (hashCode & mask) << 1;
+  }
+
+  private int incProbe(int probe) {
+    probe += 2;
+    if (probe >= data.length) {
+      probe -= data.length;
+    }
+    return probe;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/actions/MetadataProvider.java b/src/main/java/com/google/devtools/build/lib/actions/MetadataProvider.java
index 1538286ff9..80d4104686 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/MetadataProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/MetadataProvider.java
@@ -45,4 +45,11 @@ public interface MetadataProvider {
    */
   @Nullable
   Metadata getMetadata(ActionInput input) throws IOException;
-}
\ No newline at end of file
+
+  /** Looks up an input from its exec path. */
+  @Nullable
+  default ActionInput getInput(String execPath) {
+    // TODO(shahan): make sure all instances have an implementation and delete the default here.
+    return null;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/exec/SingleBuildFileCache.java b/src/main/java/com/google/devtools/build/lib/exec/SingleBuildFileCache.java
index 7eace2295a..073e3d989c 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/SingleBuildFileCache.java
+++ b/src/main/java/com/google/devtools/build/lib/exec/SingleBuildFileCache.java
@@ -13,10 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.lib.exec;
 
-
+import com.google.common.cache.Cache;
 import com.google.common.cache.CacheBuilder;
-import com.google.common.cache.CacheLoader;
-import com.google.common.cache.LoadingCache;
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputFileCache;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -26,6 +24,8 @@ import com.google.devtools.build.lib.skyframe.FileArtifactValue;
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.Path;
 import java.io.IOException;
+import java.util.concurrent.ExecutionException;
+import javax.annotation.Nullable;
 import javax.annotation.concurrent.ThreadSafe;
 
 /**
@@ -44,7 +44,7 @@ public class SingleBuildFileCache implements ActionInputFileCache {
   // If we can't get the digest, we store the exception. This avoids extra file IO for files
   // that are allowed to be missing, as we first check a likely non-existent content file
   // first.  Further we won't need to unwrap the exception in getDigest().
-  private final LoadingCache<ActionInput, ActionInputMetadata> pathToMetadata =
+  private final Cache<String, ActionInputMetadata> pathToMetadata =
       CacheBuilder.newBuilder()
           // We default to 10 disk read threads, but we don't expect them all to edit the map
           // simultaneously.
@@ -52,45 +52,62 @@ public class SingleBuildFileCache implements ActionInputFileCache {
           // Even small-ish builds, as of 11/21/2011 typically have over 10k artifacts, so it's
           // unlikely that this default will adversely affect memory in most cases.
           .initialCapacity(10000)
-          .build(
-              new CacheLoader<ActionInput, ActionInputMetadata>() {
-                @Override
-                public ActionInputMetadata load(ActionInput input) {
-                  Path path =
-                      (input instanceof Artifact)
-                          ? ((Artifact) input).getPath()
-                          : execRoot.getRelative(input.getExecPath());
-                  try {
-                    FileArtifactValue metadata = FileArtifactValue.create(path);
-                    if (metadata.getType().isDirectory()) {
-                      throw new DigestOfDirectoryException(
-                          "Input is a directory: " + input.getExecPathString());
-                    }
-                    return new ActionInputMetadata(metadata);
-                  } catch (IOException e) {
-                    return new ActionInputMetadata(e);
+          .build();
+
+  @Override
+  public Metadata getMetadata(ActionInput input) throws IOException {
+    try {
+      return pathToMetadata
+          .get(
+              input.getExecPathString(),
+              () -> {
+                Path path =
+                    (input instanceof Artifact)
+                        ? ((Artifact) input).getPath()
+                        : execRoot.getRelative(input.getExecPath());
+                try {
+                  FileArtifactValue metadata = FileArtifactValue.create(path);
+                  if (metadata.getType().isDirectory()) {
+                    throw new DigestOfDirectoryException(
+                        "Input is a directory: " + input.getExecPathString());
                   }
+                  return new ActionInputMetadata(input, metadata);
+                } catch (IOException e) {
+                  return new ActionInputMetadata(input, e);
                 }
-              });
+              })
+          .getMetadata();
+    } catch (ExecutionException e) {
+      throw new IllegalStateException("Unexpected cache loading error", e); // Should never happen.
+    }
+  }
 
   @Override
-  public Metadata getMetadata(ActionInput input) throws IOException {
-    return pathToMetadata.getUnchecked(input).getMetadata();
+  @Nullable
+  public ActionInput getInput(String execPath) {
+    ActionInputMetadata metadata = pathToMetadata.getIfPresent(execPath);
+    if (metadata == null) {
+      return null;
+    }
+    return metadata.getInput();
   }
 
   /** Container class for caching I/O around ActionInputs. */
   private static class ActionInputMetadata {
+    private final ActionInput input;
     private final Metadata metadata;
     private final IOException exceptionOnAccess;
 
     /** Constructor for a successful lookup. */
-    ActionInputMetadata(Metadata metadata) {
+    ActionInputMetadata(ActionInput input, Metadata metadata) {
+      this.input = input;
       this.metadata = metadata;
       this.exceptionOnAccess = null;
     }
 
     /** Constructor for a failed lookup, size will be 0. */
-    ActionInputMetadata(IOException exceptionOnAccess) {
+    ActionInputMetadata(ActionInput input, IOException exceptionOnAccess) {
+      this.input = input;
       this.exceptionOnAccess = exceptionOnAccess;
       this.metadata = null;
     }
@@ -100,6 +117,10 @@ public class SingleBuildFileCache implements ActionInputFileCache {
       return metadata;
     }
 
+    ActionInput getInput() {
+      return input;
+    }
+
     private void maybeRaiseException() throws IOException {
       if (exceptionOnAccess != null) {
         throw exceptionOnAccess;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/InputArtifactData.java b/src/main/java/com/google/devtools/build/lib/skyframe/InputArtifactData.java
index e65c6171ba..65b16d7462 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/InputArtifactData.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/InputArtifactData.java
@@ -17,10 +17,10 @@ import static java.nio.charset.StandardCharsets.US_ASCII;
 
 import com.google.common.io.BaseEncoding;
 import com.google.devtools.build.lib.actions.ActionInput;
+import com.google.devtools.build.lib.actions.ActionInputMap;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.protobuf.ByteString;
-import java.util.HashMap;
 import javax.annotation.Nullable;
 
 /** A mapping from artifacts to metadata. */
@@ -32,7 +32,10 @@ interface InputArtifactData {
   FileArtifactValue get(ActionInput input);
 
   @Nullable
-  FileArtifactValue get(PathFragment fragment);
+  FileArtifactValue get(PathFragment execPath);
+
+  @Nullable
+  ActionInput getInput(String execpath);
 
   /**
    * This implementation has a privileged {@link put} method supporting mutations.
@@ -41,31 +44,36 @@ interface InputArtifactData {
    * important that the underlying data is not modified during those phases.
    */
   final class MutableInputArtifactData implements InputArtifactData {
-    private final HashMap<PathFragment, FileArtifactValue> inputs;
+    private final ActionInputMap inputs;
 
     public MutableInputArtifactData(int sizeHint) {
-      this.inputs = new HashMap<>(sizeHint);
+      this.inputs = new ActionInputMap(sizeHint);
     }
 
     @Override
     public boolean contains(ActionInput input) {
-      return inputs.containsKey(input.getExecPath());
+      return inputs.getMetadata(input) != null;
     }
 
     @Override
     @Nullable
     public FileArtifactValue get(ActionInput input) {
-      return inputs.get(input.getExecPath());
+      return (FileArtifactValue) inputs.getMetadata(input);
     }
 
     @Override
     @Nullable
-    public FileArtifactValue get(PathFragment fragment) {
-      return inputs.get(fragment);
+    public FileArtifactValue get(PathFragment execPath) {
+      return (FileArtifactValue) inputs.getMetadata(execPath.getPathString());
+    }
+
+    @Override
+    public ActionInput getInput(String execPath) {
+      return inputs.getInput(execPath);
     }
 
     public void put(Artifact artifact, FileArtifactValue value) {
-      inputs.put(artifact.getExecPath(), value);
+      inputs.put(artifact, value);
     }
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java b/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java
index b455a8e7fa..54dc3a1835 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java
@@ -51,4 +51,9 @@ class PerActionFileCache implements ActionInputFileCache {
     Preconditions.checkState(missingArtifactsAllowed || result != null, "null for %s", input);
     return result;
   }
+
+  @Override
+  public ActionInput getInput(String execPath) {
+    return inputArtifactData.getInput(execPath);
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
index b87e00c78f..5efc8cdddb 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
@@ -1272,5 +1272,11 @@ public final class SkyframeActionExecutor {
           ? metadata
           : perBuildFileCache.getMetadata(input);
     }
+
+    @Override
+    public ActionInput getInput(String execPath) {
+      ActionInput input = perActionCache.getInput(execPath);
+      return input != null ? input : perBuildFileCache.getInput(execPath);
+    }
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ActionInputMapTest.java b/src/test/java/com/google/devtools/build/lib/actions/ActionInputMapTest.java
new file mode 100644
index 0000000000..5690fecaf5
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/actions/ActionInputMapTest.java
@@ -0,0 +1,199 @@
+// Copyright 2018 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.actions;
+
+import static com.google.common.truth.Truth.assertThat;
+import static java.nio.charset.StandardCharsets.US_ASCII;
+
+import com.google.devtools.build.lib.actions.cache.Metadata;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Random;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Unit test for {@link ActionInputMap}. */
+@RunWith(JUnit4.class)
+public final class ActionInputMapTest {
+
+  private ActionInputMap map;
+
+  @Before
+  public void init() {
+    map = new ActionInputMap(1); // small hint to stress the map
+  }
+
+  @Test
+  public void basicPutAndLookup() {
+    assertThat(put("/abc/def", 5)).isTrue();
+    assertThat(map.size()).isEqualTo(1);
+    assertContains("/abc/def", 5);
+    assertThat(map.getMetadata("blah")).isNull();
+    assertThat(map.getInput("blah")).isNull();
+  }
+
+  @Test
+  public void ignoresSubsequent() {
+    assertThat(put("/abc/def", 5)).isTrue();
+    assertThat(map.size()).isEqualTo(1);
+    assertThat(put("/abc/def", 6)).isFalse();
+    assertThat(map.size()).isEqualTo(1);
+    assertThat(put("/ghi/jkl", 7)).isTrue();
+    assertThat(map.size()).isEqualTo(2);
+    assertThat(put("/ghi/jkl", 8)).isFalse();
+    assertThat(map.size()).isEqualTo(2);
+    assertContains("/abc/def", 5);
+    assertContains("/ghi/jkl", 7);
+  }
+
+  @Test
+  public void clear() {
+    assertThat(put("/abc/def", 5)).isTrue();
+    assertThat(map.size()).isEqualTo(1);
+    assertThat(put("/ghi/jkl", 7)).isTrue();
+    assertThat(map.size()).isEqualTo(2);
+    map.clear();
+    assertThat(map.size()).isEqualTo(0);
+    assertThat(map.getMetadata("/abc/def")).isNull();
+    assertThat(map.getMetadata("/ghi/jkl")).isNull();
+  }
+
+  @Test
+  public void stress() {
+    ArrayList<TestEntry> data = new ArrayList<>();
+    {
+      Random rng = new Random();
+      HashSet<TestInput> deduper = new HashSet<>();
+      for (int i = 0; i < 100000; ++i) {
+        byte[] bytes = new byte[80];
+        rng.nextBytes(bytes);
+        for (int j = 0; j < bytes.length; ++j) {
+          bytes[j] &= ((byte) 0x7f);
+        }
+        TestInput nextInput = new TestInput(new String(bytes, US_ASCII));
+        if (deduper.add(nextInput)) {
+          data.add(new TestEntry(nextInput, new TestMetadata(i)));
+        }
+      }
+    }
+    for (int iteration = 0; iteration < 20; ++iteration) {
+      map.clear();
+      Collections.shuffle(data);
+      for (int i = 0; i < data.size(); ++i) {
+        TestEntry entry = data.get(i);
+        assertThat(map.put(entry.input, entry.metadata)).isTrue();
+      }
+      assertThat(map.size()).isEqualTo(data.size());
+      for (int i = 0; i < data.size(); ++i) {
+        TestEntry entry = data.get(i);
+        assertThat(map.getMetadata(entry.input)).isEqualTo(entry.metadata);
+      }
+    }
+  }
+
+  private boolean put(String execPath, int value) {
+    return map.put(new TestInput(execPath), new TestMetadata(value));
+  }
+
+  private void assertContains(String execPath, int value) {
+    assertThat(map.getMetadata(new TestInput(execPath))).isEqualTo(new TestMetadata(value));
+    assertThat(map.getMetadata(execPath)).isEqualTo(new TestMetadata(value));
+    assertThat(map.getInput(execPath)).isEqualTo(new TestInput(execPath));
+  }
+
+  private static class TestEntry {
+    public final TestInput input;
+    public final TestMetadata metadata;
+
+    public TestEntry(TestInput input, TestMetadata metadata) {
+      this.input = input;
+      this.metadata = metadata;
+    }
+  }
+
+  private static class TestInput implements ActionInput {
+    private final PathFragment fragment;
+
+    public TestInput(String fragment) {
+      this.fragment = PathFragment.create(fragment);
+    }
+
+    @Override
+    public PathFragment getExecPath() {
+      return fragment;
+    }
+
+    @Override
+    public String getExecPathString() {
+      return fragment.toString();
+    }
+
+    @Override
+    public boolean equals(Object other) {
+      if (!(other instanceof TestInput)) {
+        return false;
+      }
+      if (this == other) {
+        return true;
+      }
+      return fragment.equals(((TestInput) other).fragment);
+    }
+
+    @Override
+    public int hashCode() {
+      return fragment.hashCode();
+    }
+  }
+
+  private static class TestMetadata implements Metadata {
+    private final int id;
+
+    public TestMetadata(int id) {
+      this.id = id;
+    }
+
+    @Override
+    public FileStateType getType() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public byte[] getDigest() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public long getSize() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public long getModifiedTime() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    @SuppressWarnings("EqualsHashCode")
+    public boolean equals(Object o) {
+      if (!(o instanceof TestMetadata)) {
+        return false;
+      }
+      return id == ((TestMetadata) o).id;
+    }
+  }
+}