src/main/java/com/google/devtools/build/lib/skyframe/DefaultSyscallCache.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.lib.skyframe;

import static com.google.common.base.MoreObjects.firstNonNull;

import com.github.benmanes.caffeine.cache.Caffeine;
import com.github.benmanes.caffeine.cache.LoadingCache;
import com.google.common.base.Ascii;
import com.google.devtools.build.lib.unsafe.StringUnsafe;
import com.google.devtools.build.lib.vfs.Dirent;
import com.google.devtools.build.lib.vfs.FileStatus;
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.Symlinks;
import com.google.devtools.build.lib.vfs.SyscallCache;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import java.io.IOException;
import java.util.Collection;
import java.util.function.Supplier;
import javax.annotation.Nullable;

/**
 * A basic implementation of {@link SyscallCache} that caches stat and readdir operations, used if
 * no custom cache is set in {@link
 * com.google.devtools.build.lib.runtime.WorkspaceBuilder#setSyscallCache}.
 *
 * <p>Allows non-Skyframe operations (like non-Skyframe globbing) to share a filesystem cache with
 * Skyframe operations, and may be able to answer questions (like the type of a file) based on
 * existing data (like the directory listing of a parent) without filesystem access.
 */
public final class DefaultSyscallCache implements SyscallCache {

  private final Supplier<LoadingCache<Path, Object>> statCacheSupplier;
  private final Supplier<LoadingCache<Path, Object>> readdirCacheSupplier;

  private LoadingCache<Path, Object> statCache;

  /* Caches the result of readdir(<path>, Symlinks.NOFOLLOW) calls. */
  private LoadingCache<Path, Object> readdirCache;

  private static final FileStatus NO_STATUS = new FakeFileStatus();

  private static final class SymlinkEntry {
    private final FileStatus nofollowStatus;
    @Nullable private volatile Object followStatus;

    SymlinkEntry(FileStatus nofollowStatus) {
      this.nofollowStatus = nofollowStatus;
    }

    FileStatus getNofollowStatus() {
      return nofollowStatus;
    }

    @Nullable
    FileStatus getFollowStatus(Path path) throws IOException {
      Object result = followStatus;
      if (result == null) {
        synchronized (this) {
          result = followStatus;
          if (result == null) {
            try {
              FileStatus stat = path.statIfFound(Symlinks.FOLLOW);
              result = firstNonNull(stat, NO_STATUS);
            } catch (IOException e) {
              result = e;
            }
            followStatus = result;
          }
        }
      }
      if (result instanceof IOException ioException) {
        throw ioException;
      }
      return (result == NO_STATUS) ? null : (FileStatus) result;
    }

    @Nullable
    FileStatus getFollowStatusIfPresent() {
      Object result = followStatus;
      if (result instanceof FileStatus fileStatus && fileStatus != NO_STATUS) {
        return fileStatus;
      }
      return null;
    }
  }

  private DefaultSyscallCache(
      Supplier<LoadingCache<Path, Object>> statCacheSupplier,
      Supplier<LoadingCache<Path, Object>> readdirCacheSupplier) {
    this.statCacheSupplier = statCacheSupplier;
    this.readdirCacheSupplier = readdirCacheSupplier;
    clear();
  }

  public static Builder newBuilder() {
    return new Builder();
  }

  /** Builder for a per-build filesystem cache. */
  public static final class Builder {
    private static final int UNSET = -1;
    private int maxStats = UNSET;
    private int maxReaddirs = UNSET;
    private int initialCapacity = UNSET;

    private Builder() {}

    /** Sets the upper bound of the 'stat' cache. This cache is unbounded by default. */
    @CanIgnoreReturnValue
    public Builder setMaxStats(int maxStats) {
      this.maxStats = maxStats;
      return this;
    }

    /** Sets the upper bound of the 'readdir' cache. This cache is unbounded by default. */
    @CanIgnoreReturnValue
    public Builder setMaxReaddirs(int maxReaddirs) {
      this.maxReaddirs = maxReaddirs;
      return this;
    }

    /** Sets the concurrency level of the caches. */
    @CanIgnoreReturnValue
    public Builder setInitialCapacity(int initialCapacity) {
      this.initialCapacity = initialCapacity;
      return this;
    }

    public DefaultSyscallCache build() {
      Caffeine<Object, Object> statCacheBuilder = Caffeine.newBuilder();
      if (maxStats != UNSET) {
        statCacheBuilder.maximumSize(maxStats);
      }
      Caffeine<Object, Object> readdirCacheBuilder = Caffeine.newBuilder();
      if (maxReaddirs != UNSET) {
        readdirCacheBuilder.maximumSize(maxReaddirs);
      }
      if (initialCapacity != UNSET) {
        statCacheBuilder.initialCapacity(initialCapacity);
        readdirCacheBuilder.initialCapacity(initialCapacity);
      }
      return new DefaultSyscallCache(
          () -> statCacheBuilder.build(DefaultSyscallCache::statImpl),
          () -> readdirCacheBuilder.build(DefaultSyscallCache::readdirImpl));
    }
  }

  @Override
  @SuppressWarnings("unchecked") // readdirImpl only returns Collection<Dirent> or IOException
  public Collection<Dirent> readdir(Path path) throws IOException {
    Object result = readdirCache.get(path);
    if (result instanceof IOException ioException) {
      throw ioException;
    }
    return (Collection<Dirent>) result; // unchecked cast
  }

  @Nullable
  @Override
  public FileStatus statIfFound(Path path, Symlinks symlinks) throws IOException {
    Object result = statCache.get(path);
    if (result instanceof IOException ioException) {
      throw ioException;
    }
    if (result == NO_STATUS) {
      return null;
    }
    if (result instanceof SymlinkEntry symlinkEntry) {
      if (symlinks == Symlinks.FOLLOW) {
        return symlinkEntry.getFollowStatus(path);
      }
      return symlinkEntry.getNofollowStatus();
    }
    return (FileStatus) result;
  }

  @Nullable
  @Override
  public DirentTypeWithSkip getType(Path path, Symlinks symlinks) throws IOException {
    // Use a cached stat call if we have one. This is done first so that we don't need to iterate
    // over a list of directory entries as we do for cached readdir() entries. We don't ever expect
    // to get a cache hit if symlinks == Symlinks.NOFOLLOW and so we don't bother to check.
    if (symlinks == Symlinks.FOLLOW) {
      Object result = statCache.getIfPresent(path);
      if (result != null && !(result instanceof IOException)) {
        if (result == NO_STATUS) {
          return null;
        }
        if (result instanceof SymlinkEntry symlinkEntry) {
          FileStatus followStatus = symlinkEntry.getFollowStatusIfPresent();
          if (followStatus != null) {
            return ofStat(followStatus);
          }
        } else {
          return ofStat((FileStatus) result);
        }
      }
    }

    // If this is a root directory, we must stat, there is no parent.
    Path parent = path.getParentDirectory();
    if (parent == null) {
      return ofStat(statIfFound(path, symlinks));
    }

    // Answer based on a cached readdir() call if possible. The cache might already be populated
    // from Skyframe directory lising (DirectoryListingFunction) or by globbing via
    // {@link UnixGlob}. We generally try to avoid following symlinks in readdir() calls as in a
    // directory with many symlinks, these would be resolved basically using a stat anyway and they
    // would be resolved sequentially which can be slow on high-latency file systems. If we request
    // the type of a file with FOLLOW, and find a symlink in the directory, we fall back to doing a
    // stat.
    if (readdirCache.getIfPresent(parent) instanceof Dirents dirents) {
      String baseName = path.getBaseName();
      Dirent.Type direntType = dirents.maybeGetDirentType(baseName);
      if (direntType != null) {
        if (direntType == Dirent.Type.SYMLINK && symlinks == Symlinks.FOLLOW) {
          // See above: We don't want to follow symlinks with readdir(). Do a stat() instead.
          return ofStat(statIfFound(path, Symlinks.FOLLOW));
        }
        return DirentTypeWithSkip.of(direntType);
      }
      if (!path.getFileSystem().mayBeCaseOrNormalizationInsensitive()) {
        return null;
      }
      // The filesystem may be case-insensitive or normalization-insensitive, but it doesn't have
      // to be and even if it is, we don't know which normalization algorithm it uses. We assume
      // that every reasonable filesystem doesn't normalize pure ASCII path components in any
      // way other than ASCII case insensitivity.
      if (StringUnsafe.isAscii(baseName)) {
        boolean mayHaveFoundMatch = false;
        for (Dirent d : dirents) {
          if (!StringUnsafe.isAscii(d.getName()) || Ascii.equalsIgnoreCase(baseName, d.getName())) {
            mayHaveFoundMatch = true;
            break;
          }
        }
        if (!mayHaveFoundMatch) {
          return null;
        }
      }
      // Fall back to stat() if we might have found a match.
    }

    return ofStat(statIfFound(path, symlinks));
  }

  @Nullable
  private static DirentTypeWithSkip ofStat(@Nullable FileStatus status) {
    return DirentTypeWithSkip.of(SyscallCache.statusToDirentType(status));
  }

  @Override
  public void clear() {
    // Drop not just the memory of the FileStatus objects but the maps themselves.
    statCache = statCacheSupplier.get();
    readdirCache = readdirCacheSupplier.get();
  }

  // This is used because the cache implementations don't allow null.
  private static final class FakeFileStatus implements FileStatus {
    @Override
    public long getLastChangeTime() {
      throw new UnsupportedOperationException();
    }

    @Override
    public long getNodeId() {
      throw new UnsupportedOperationException();
    }

    @Override
    public long getLastModifiedTime() {
      throw new UnsupportedOperationException();
    }

    @Override
    public long getSize() {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean isDirectory() {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean isFile() {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean isSpecialFile() {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean isSymbolicLink() {
      throw new UnsupportedOperationException();
    }
  }

  /** Returns {@link FileStatus}, {@link SymlinkEntry}, or {@link IOException}. */
  private static Object statImpl(Path path) {
    try {
      FileStatus stat = path.statIfFound(Symlinks.NOFOLLOW);
      if (stat == null) {
        return NO_STATUS;
      }
      if (stat.isSymbolicLink()) {
        return new SymlinkEntry(stat);
      }
      return stat;
    } catch (IOException e) {
      return e;
    }
  }

  /** Returns a collection of {@link Dirent} or {@link IOException}. */
  private static Object readdirImpl(Path p) {
    try {
      return CompactSortedDirents.create(p.readdir(Symlinks.NOFOLLOW));
    } catch (IOException e) {
      return e;
    }
  }
}