src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java

// Copyright 2014 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.skyframe;

import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;

import com.google.common.collect.ForwardingConcurrentMap;
import com.google.common.collect.ImmutableSortedMap;
import com.google.common.collect.Maps;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.cmdline.Label.LabelInterner;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.concurrent.PooledInterner;
import com.google.devtools.build.lib.packages.Target;
import com.google.devtools.build.lib.profiler.AutoProfiler;
import com.google.devtools.build.lib.profiler.GoogleAutoProfilerUtils;
import com.google.devtools.build.lib.skyframe.PackageValue;
import com.google.devtools.build.lib.skyframe.SkyFunctions;
import com.google.devtools.build.lib.supplier.InterruptibleSupplier;
import com.google.devtools.build.skyframe.SkyKey.SkyKeyInterner;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.errorprone.annotations.ForOverride;
import java.time.Duration;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.locks.Lock;
import java.util.function.Consumer;
import javax.annotation.Nullable;

/**
 * An in-memory graph implementation. All operations are thread-safe with ConcurrentMap semantics.
 * Also see {@link NodeEntry}.
 *
 * <p>This class is public only for use in alternative graph implementations.
 */
public class InMemoryGraphImpl implements InMemoryGraph {

  private static final int PARALLELISM_THRESHOLD = 1024;

  // Use ForwardingConcurrentMap as a live reference to nodeMap so that it's safe to mutate
  // nodeMap and not have callers see the stale map. See getValues, getDoneValues,
  // getAllNodeEntries.
  private final ConcurrentMap<SkyKey, InMemoryNodeEntry> liveView =
      new ForwardingConcurrentMap<>() {
        @Override
        protected ConcurrentMap<SkyKey, InMemoryNodeEntry> delegate() {
          return nodeMap;
        }
      };

  protected ConcurrentHashMap<SkyKey, InMemoryNodeEntry> nodeMap;
  private final NodeBatch getBatch;
  private final NodeBatch createIfAbsentBatch;
  private final boolean usePooledInterning;

  InMemoryGraphImpl() {
    this(/* initialCapacity= */ 1 << 10);
  }

  /**
   * For some shell integration tests, we don't want to apply {@link SkyKeyInterner} created and
   * bind {@code SkyKeyInterner#globalPool} to the second {@link InMemoryGraph}.
   */
  InMemoryGraphImpl(boolean usePooledInterning) {
    this(/* initialCapacity= */ 1 << 10, usePooledInterning);
  }

  protected InMemoryGraphImpl(int initialCapacity) {
    this(initialCapacity, /* usePooledInterning= */ true);
  }

  private InMemoryGraphImpl(int initialCapacity, boolean usePooledInterning) {
    this.nodeMap = new ConcurrentHashMap<>(initialCapacity);
    this.getBatch = this::getIfPresent;
    this.createIfAbsentBatch = this::createIfAbsent;
    this.usePooledInterning = usePooledInterning;
    if (usePooledInterning) {
      SkyKeyInterner.setGlobalPool(new SkyKeyPool());
      LabelInterner.setGlobalPool(new LabelPool());
    }
  }

  @Override
  public void remove(SkyKey skyKey) {
    weakInternSkyKey(skyKey);
    InMemoryNodeEntry nodeEntry = nodeMap.remove(skyKey);
    if (skyKey instanceof PackageIdentifier && nodeEntry != null) {
      weakInternPackageTargetsLabels(
          (PackageValue) nodeEntry.toValue()); // Dirty or changed value are needed.
    }
  }

  @Override
  public void removeIfDone(SkyKey key) {
    nodeMap.computeIfPresent(
        key,
        (k, e) -> {
          if (e.isDone()) {
            weakInternSkyKey(k);
            if (k instanceof PackageIdentifier) {
              weakInternPackageTargetsLabels((PackageValue) e.toValue());
            }
            return null;
          }
          return e;
        });
  }

  private void weakInternSkyKey(SkyKey skyKey) {
    if (!usePooledInterning) {
      return;
    }
    SkyKeyInterner<?> interner = skyKey.getSkyKeyInterner();
    if (interner != null) {
      interner.weakInternUnchecked(skyKey);
    }
  }

  private void weakInternPackageTargetsLabels(@Nullable PackageValue packageValue) {
    if (!usePooledInterning || packageValue == null) {
      return;
    }
    LabelInterner interner = Label.getLabelInterner();

    ImmutableSortedMap<String, Target> targets = packageValue.getPackage().getTargets();
    targets.values().forEach(t -> interner.weakIntern(t.getLabel()));
  }

  @Override
  public NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey skyKey) {
    return nodeMap.get(skyKey);
  }

  @Override
  public NodeBatch getBatch(
      @Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys) {
    return getBatch;
  }

  @Override
  public InterruptibleSupplier<NodeBatch> getBatchAsync(
      @Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys) {
    return () -> getBatch;
  }

  @Override
  public Map<SkyKey, NodeEntry> getBatchMap(
      SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys) {
    // Use a HashMap, not an ImmutableMap.Builder, because we have not yet deduplicated these keys
    // and ImmutableMap.Builder does not tolerate duplicates. The map will be thrown away shortly.
    HashMap<SkyKey, NodeEntry> result = new HashMap<>();
    for (SkyKey key : keys) {
      NodeEntry entry = get(null, Reason.OTHER, key);
      if (entry != null) {
        result.put(key, entry);
      }
    }
    return result;
  }

  @ForOverride
  protected InMemoryNodeEntry newNodeEntry(SkyKey key) {
    return new IncrementalInMemoryNodeEntry(key);
  }

  @Override
  @CanIgnoreReturnValue
  public NodeBatch createIfAbsentBatch(
      @Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys) {
    for (SkyKey key : keys) {
      createIfAbsent(key);
    }
    return createIfAbsentBatch;
  }

  @CanIgnoreReturnValue
  private InMemoryNodeEntry createIfAbsent(SkyKey skyKey) {
    SkyKeyInterner<?> interner = skyKey.getSkyKeyInterner();
    if (!usePooledInterning || interner == null) {
      return nodeMap.computeIfAbsent(skyKey, this::newNodeEntry);
    }

    // The key is typically already present. Record whether this thread newly created a node so that
    // we can skip calling removeWeak if it was already present.
    boolean[] newlyCreated = new boolean[1];
    InMemoryNodeEntry nodeEntry =
        nodeMap.computeIfAbsent(
            skyKey,
            k -> {
              newlyCreated[0] = true;
              return newNodeEntry(k);
            });
    if (newlyCreated[0]) {
      interner.removeWeak(skyKey);
    }
    return nodeEntry;
  }

  @Override
  public DepsReport analyzeDepsDoneness(SkyKey parent, List<SkyKey> deps) {
    return DepsReport.NO_INFORMATION;
  }

  @Override
  public int valuesSize() {
    return nodeMap.size();
  }

  @Override
  public Map<SkyKey, SkyValue> getValues() {
    return Collections.unmodifiableMap(Maps.transformValues(liveView, InMemoryNodeEntry::toValue));
  }

  @Override
  public Map<SkyKey, SkyValue> getDoneValues() {
    return Collections.unmodifiableMap(
        Maps.filterValues(
            Maps.transformValues(liveView, entry -> entry.isDone() ? entry.getValue() : null),
            Objects::nonNull));
  }

  @Override
  public Collection<InMemoryNodeEntry> getAllNodeEntries() {
    return Collections.unmodifiableCollection(nodeMap.values());
  }

  @Override
  public void parallelForEach(Consumer<InMemoryNodeEntry> consumer) {
    nodeMap.forEachValue(PARALLELISM_THRESHOLD, consumer);
  }

  @Override
  public void cleanupInterningPools() {
    if (!usePooledInterning) {
      return;
    }
    try (AutoProfiler ignored =
        GoogleAutoProfilerUtils.logged("Cleaning up interning pools", Duration.ofMillis(2L))) {
      parallelForEach(
          e -> {
            weakInternSkyKey(e.getKey());

            if (e.isDone() && e.getKey().functionName().equals(SkyFunctions.PACKAGE)) {
              weakInternPackageTargetsLabels((PackageValue) e.toValue());
            }

            // The graph is about to be thrown away. Remove as we go to avoid temporarily storing
            // everything in both the weak interner and the graph.
            nodeMap.remove(e.getKey());
          });
    }

    SkyKeyInterner.setGlobalPool(null);
    LabelInterner.setGlobalPool(null);
  }

  @Override
  @Nullable
  public InMemoryNodeEntry getIfPresent(SkyKey key) {
    return nodeMap.get(key);
  }

  /** Minimizes the size of the ConcurrentHashMap backing the graph. May be costly to run (O(n)). */
  @Override
  public void shrinkNodeMap() {
    nodeMap = new ConcurrentHashMap<>(nodeMap);
  }

  static final class EdgelessInMemoryGraphImpl extends InMemoryGraphImpl {

    public EdgelessInMemoryGraphImpl(boolean usePooledInterning) {
      super(usePooledInterning);
    }

    @Override
    protected InMemoryNodeEntry newNodeEntry(SkyKey key) {
      return new NonIncrementalInMemoryNodeEntry(key);
    }
  }

  /** {@link PooledInterner.Pool} for {@link SkyKey}s. */
  final class SkyKeyPool implements PooledInterner.Pool<SkyKey> {

    @Override
    public SkyKey getOrWeakIntern(SkyKey sample) {
      // Use computeIfAbsent not to mutate the map, but to call weakIntern under synchronization.
      // This ensures that the canonical instance isn't being transferred to the node map
      // concurrently in createIfAbsent. In the common case that the key is already present in the
      // node map, this is a lock-free lookup.
      SkyKey[] weakInterned = new SkyKey[1];
      InMemoryNodeEntry nodeEntry =
          nodeMap.computeIfAbsent(
              sample,
              k -> {
                weakInterned[0] = k.getSkyKeyInterner().weakInternUnchecked(k);
                return null; // Don't actually store a mapping.
              });
      return nodeEntry != null ? nodeEntry.getKey() : weakInterned[0];
    }
  }

  /** {@link PooledInterner.Pool} for {@link Label}s. */
  final class LabelPool implements PooledInterner.Pool<Label> {
    @Override
    public Label getOrWeakIntern(Label sample) {
      LabelInterner interner = checkNotNull(Label.getLabelInterner());

      PackageIdentifier packageIdentifier = sample.getPackageIdentifier();

      // Return pooled instance if sample is present in the pool.
      InMemoryNodeEntry inMemoryNodeEntry = nodeMap.get(packageIdentifier);
      if (inMemoryNodeEntry != null) {
        Label pooledInstance = getLabelFromInMemoryNodeEntry(inMemoryNodeEntry, sample);
        if (pooledInstance != null) {
          return pooledInstance;
        }
      }

      Lock readLock = interner.getLockForLabelLookup(sample);
      readLock.lock();

      try {
        // Check again whether sample is already present in the pool inside critical section.
        if (inMemoryNodeEntry == null) {
          inMemoryNodeEntry = nodeMap.get(packageIdentifier);
        }

        if (inMemoryNodeEntry != null) {
          Label pooledInstance = getLabelFromInMemoryNodeEntry(inMemoryNodeEntry, sample);
          if (pooledInstance != null) {
            return pooledInstance;
          }
        }
        return interner.weakIntern(sample);
      } finally {
        readLock.unlock();
      }
    }
  }

  @Nullable
  private static Label getLabelFromInMemoryNodeEntry(
      InMemoryNodeEntry inMemoryNodeEntry, Label sample) {
    checkNotNull(inMemoryNodeEntry);
    SkyValue value = inMemoryNodeEntry.toValue();
    if (value == null) {
      return null;
    }
    checkState(value instanceof PackageValue, value);
    ImmutableSortedMap<String, Target> targets = ((PackageValue) value).getPackage().getTargets();
    Target target = targets.get(sample.getName());
    return target != null ? target.getLabel() : null;
  }
}