MetadataProvider now provides ActionInput lookup by exec path. Adds a helper class, ActionInputMap to do this with minimal wrapping overhead. PiperOrigin-RevId: 199391251
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 0000000..c938b07 --- /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 1538286..80d4104 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 @@ */ @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 7eace22..073e3d9 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.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 @@ // 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 @@ // 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 { - return pathToMetadata.getUnchecked(input).getMetadata(); + 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 + @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 @@ 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 e65c617..65b16d7 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 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 @@ 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 @@ * 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 b455a8e..54dc3a1 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 @@ 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 b87e00c..5efc8cd 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 @@ ? 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 0000000..5690fec --- /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; + } + } +}