src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java - bazel - Git at Google

 // 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.actions.cache;

 import static java.nio.charset.StandardCharsets.ISO_8859_1;

 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.cache.Protos.ActionCacheStatistics;
 import com.google.devtools.build.lib.actions.cache.Protos.ActionCacheStatistics.MissReason;
 import com.google.devtools.build.lib.clock.Clock;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ConditionallyThreadSafe;
 import com.google.devtools.build.lib.profiler.AutoProfiler;
 import com.google.devtools.build.lib.util.PersistentMap;
 import com.google.devtools.build.lib.util.StringIndexer;
 import com.google.devtools.build.lib.util.VarInt;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.UnixGlob;
 import java.io.ByteArrayOutputStream;
 import java.io.DataInputStream;
 import java.io.DataOutputStream;
 import java.io.IOException;
 import java.io.PrintStream;
 import java.nio.BufferUnderflowException;
 import java.nio.ByteBuffer;
 import java.util.Collection;
 import java.util.EnumMap;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.logging.Logger;

 /**
  * An implementation of the ActionCache interface that uses a {@link StringIndexer} to reduce memory
  * footprint and saves cached actions using the {@link PersistentMap}.
  */
 @ConditionallyThreadSafe // condition: each instance must instantiated with
 // different cache root
 public class CompactPersistentActionCache implements ActionCache {
   private static final int SAVE_INTERVAL_SECONDS = 3;
   // Log if periodically saving the action cache incurs more than 5% overhead.
   private static final int MIN_TIME_FOR_LOGGING_MILLIS =
       (int) (TimeUnit.SECONDS.toMillis(SAVE_INTERVAL_SECONDS) * 0.05);

   // Key of the action cache record that holds information used to verify referential integrity
   // between action cache and string indexer. Must be < 0 to avoid conflict with real action
   // cache records.
   private static final int VALIDATION_KEY = -10;

   private static final int NO_INPUT_DISCOVERY_COUNT = -1;

   private static final int VERSION = 12;

   private static final Logger logger =
       Logger.getLogger(CompactPersistentActionCache.class.getName());

   private final class ActionMap extends PersistentMap<Integer, byte[]> {
     private final Clock clock;
     private long nextUpdateSecs;

     public ActionMap(Map<Integer, byte[]> map, Clock clock, Path mapFile, Path journalFile)
         throws IOException {
       super(VERSION, map, mapFile, journalFile);
       this.clock = clock;
       // Using nanoTime. currentTimeMillis may not provide enough granularity.
       nextUpdateSecs = TimeUnit.NANOSECONDS.toSeconds(clock.nanoTime()) + SAVE_INTERVAL_SECONDS;
       load();
     }

     @Override
     protected boolean updateJournal() {
       // Using nanoTime. currentTimeMillis may not provide enough granularity.
       long timeSecs = TimeUnit.NANOSECONDS.toSeconds(clock.nanoTime());
       if (SAVE_INTERVAL_SECONDS == 0 || timeSecs > nextUpdateSecs) {
         nextUpdateSecs = timeSecs + SAVE_INTERVAL_SECONDS;
         // Force flushing of the PersistentStringIndexer instance. This is needed to ensure
         // that filename index data on disk is always up-to-date when we save action cache
         // data.
         indexer.flush();
         return true;
       }
       return false;
     }

     @Override
     protected void markAsDirty() {
       try (AutoProfiler p =
           AutoProfiler.logged("slow write to journal", logger, MIN_TIME_FOR_LOGGING_MILLIS)) {
         super.markAsDirty();
       }
     }

     @Override
     protected boolean keepJournal() {
       // We must first flush the journal to get an accurate measure of its size.
       forceFlush();
       try {
         return journalSize() * 100 < cacheSize();
       } catch (IOException e) {
         return false;
       }
     }

     @Override
     protected Integer readKey(DataInputStream in) throws IOException {
       return in.readInt();
     }

     @Override
     protected byte[] readValue(DataInputStream in)
         throws IOException {
       int size = in.readInt();
       if (size < 0) {
         throw new IOException("found negative array size: " + size);
       }
       byte[] data = new byte[size];
       in.readFully(data);
       return data;
     }

     @Override
     protected void writeKey(Integer key, DataOutputStream out)
         throws IOException {
       out.writeInt(key);
     }

     @Override
     // TODO(bazel-team): (2010) This method, writeKey() and related Metadata methods
     // should really use protocol messages. Doing so would allow easy inspection
     // of the action cache content and, more importantly, would cut down on the
     // need to change VERSION to different number every time we touch those
     // methods. Especially when we'll start to add stuff like statistics for
     // each action.
     protected void writeValue(byte[] value, DataOutputStream out)
         throws IOException {
       out.writeInt(value.length);
       out.write(value);
     }
   }

   private final PersistentMap<Integer, byte[]> map;
   private final PersistentStringIndexer indexer;

   private final AtomicInteger hits = new AtomicInteger();
   private final Map<MissReason, AtomicInteger> misses = new EnumMap<>(MissReason.class);

   public CompactPersistentActionCache(Path cacheRoot, Clock clock) throws IOException {
     Path cacheFile = cacheFile(cacheRoot);
     Path journalFile = journalFile(cacheRoot);
     Path indexFile = cacheRoot.getChild("filename_index_v" + VERSION + ".blaze");
     // we can now use normal hash map as backing map, since dependency checker
     // will manually purge records from the action cache.
     Map<Integer, byte[]> backingMap = new HashMap<>();

     try {
       indexer = PersistentStringIndexer.newPersistentStringIndexer(indexFile, clock);
     } catch (IOException e) {
       renameCorruptedFiles(cacheRoot);
       throw new IOException("Failed to load filename index data", e);
     }

     try {
       map = new ActionMap(backingMap, clock, cacheFile, journalFile);
     } catch (IOException e) {
       renameCorruptedFiles(cacheRoot);
       throw new IOException("Failed to load action cache data", e);
     }

     // Validate referential integrity between two collections.
     if (!map.isEmpty()) {
       String integrityError = validateIntegrity(indexer.size(), map.get(VALIDATION_KEY));
       if (integrityError != null) {
         renameCorruptedFiles(cacheRoot);
         throw new IOException("Failed action cache referential integrity check: " + integrityError);
       }
     }

     for (MissReason reason : MissReason.values()) {
       if (reason == MissReason.UNRECOGNIZED) {
         // The presence of this enum value is a protobuf artifact and confuses our metrics
         // externalization code below. Just skip it.
         continue;
       }
       misses.put(reason, new AtomicInteger(0));
     }
   }

   /**
    * Rename corrupted files so they could be analyzed later. This would also ensure
    * that next initialization attempt will create empty cache.
    */
   private static void renameCorruptedFiles(Path cacheRoot) {
     try {
       for (Path path : UnixGlob.forPath(cacheRoot).addPattern("action_*_v" + VERSION + ".*")
           .glob()) {
         path.renameTo(path.getParentDirectory().getChild(path.getBaseName() + ".bad"));
       }
       for (Path path : UnixGlob.forPath(cacheRoot).addPattern("filename_*_v" + VERSION + ".*")
           .glob()) {
         path.renameTo(path.getParentDirectory().getChild(path.getBaseName() + ".bad"));
       }
     } catch (UnixGlob.BadPattern ex) {
       throw new IllegalStateException(ex); // can't happen
     } catch (IOException e) {
       // do nothing
     }
   }

   /**
    * @return non-null error description if indexer contains no data or integrity check has failed,
    *     and null otherwise
    */
   private static String validateIntegrity(int indexerSize, byte[] validationRecord) {
     if (indexerSize == 0) {
       return "empty index";
     }
     if (validationRecord == null) {
       return "no validation record";
     }
     try {
       int validationSize = ByteBuffer.wrap(validationRecord).asIntBuffer().get();
       if (validationSize <= indexerSize) {
         return null;
       } else {
         return String.format("Validation mismatch: validation entry %d is too large " +
                              "compared to index size %d", validationSize, indexerSize);
       }
     } catch (BufferUnderflowException e) {
       return e.getMessage();
     }
   }

   public static Path cacheFile(Path cacheRoot) {
     return cacheRoot.getChild("action_cache_v" + VERSION + ".blaze");
   }

   public static Path journalFile(Path cacheRoot) {
     return cacheRoot.getChild("action_journal_v" + VERSION + ".blaze");
   }

   @Override
   public ActionCache.Entry get(String key) {
     int index = indexer.getIndex(key);
     if (index < 0) {
       return null;
     }
     byte[] data;
     synchronized (this) {
       data = map.get(index);
     }
     try {
       return data != null ? CompactPersistentActionCache.decode(indexer, data) : null;
     } catch (IOException e) {
       // return entry marked as corrupted.
       return ActionCache.Entry.CORRUPTED;
     }
   }

   @Override
   public void put(String key, ActionCache.Entry entry) {
     // Encode record. Note that both methods may create new mappings in the indexer.
     int index = indexer.getOrCreateIndex(key);
     byte[] content = encode(indexer, entry);

     // Update validation record.
     ByteBuffer buffer = ByteBuffer.allocate(4); // size of int in bytes
     int indexSize = indexer.size();
     buffer.asIntBuffer().put(indexSize);

     // Note the benign race condition here in which two threads might race on
     // updating the VALIDATION_KEY. If the most recent update loses the race,
     // a value lower than the indexer size will remain in the validation record.
     // This will still pass the integrity check.
     synchronized (this) {
       map.put(VALIDATION_KEY, buffer.array());
       // Now update record itself.
       map.put(index, content);
     }
   }

   @Override
   public synchronized void remove(String key) {
     map.remove(indexer.getIndex(key));
   }

   @Override
   public synchronized long save() throws IOException {
     long indexSize = indexer.save();
     long mapSize = map.save();
     return indexSize + mapSize;
   }

   @Override
   public void clear() {
     indexer.clear();
     map.clear();
   }

   @Override
   public synchronized String toString() {
     StringBuilder builder = new StringBuilder();
     // map.size() - 1 to avoid counting the validation key.
     builder.append("Action cache (" + (map.size() - 1) + " records):\n");
     int size = map.size() > 1000 ? 10 : map.size();
     int ct = 0;
     for (Map.Entry<Integer, byte[]> entry: map.entrySet()) {
       if (entry.getKey() == VALIDATION_KEY) { continue; }
       String content;
       try {
         content = decode(indexer, entry.getValue()).toString();
       } catch (IOException e) {
         content = e + "\n";
       }
       builder.append("-> ").append(indexer.getStringForIndex(entry.getKey())).append("\n")
           .append(content).append("  packed_len = ").append(entry.getValue().length).append("\n");
       if (++ct > size) {
         builder.append("...");
         break;
       }
     }
     return builder.toString();
   }

   /**
    * Dumps action cache content.
    */
   @Override
   public synchronized void dump(PrintStream out) {
     out.println("String indexer content:\n");
     out.println(indexer);
     out.println("Action cache (" + map.size() + " records):\n");
     for (Map.Entry<Integer, byte[]> entry: map.entrySet()) {
       if (entry.getKey() == VALIDATION_KEY) { continue; }
       String content;
       try {
         content = CompactPersistentActionCache.decode(indexer, entry.getValue()).toString();
       } catch (IOException e) {
         content = e + "\n";
       }
       out.println(entry.getKey() + ", " + indexer.getStringForIndex(entry.getKey()) + ":\n"
           +  content + "\n      packed_len = " + entry.getValue().length + "\n");
     }
   }

   /**
    * @return action data encoded as a byte[] array.
    */
   private static byte[] encode(StringIndexer indexer, ActionCache.Entry entry) {
     Preconditions.checkState(!entry.isCorrupted());

     try {
       byte[] actionKeyBytes = entry.getActionKey().getBytes(ISO_8859_1);
       Collection<String> files = entry.getPaths();

       // Estimate the size of the buffer:
       //   5 bytes max for the actionKey length
       // + the actionKey itself
       // + 32 bytes for the digest
       // + 5 bytes max for the file list length
       // + 5 bytes max for each file id
       // + 32 bytes for the environment digest
       int maxSize =
           VarInt.MAX_VARINT_SIZE
               + actionKeyBytes.length
               + DigestUtils.ESTIMATED_SIZE
               + VarInt.MAX_VARINT_SIZE
               + files.size() * VarInt.MAX_VARINT_SIZE
               + DigestUtils.ESTIMATED_SIZE;
       ByteArrayOutputStream sink = new ByteArrayOutputStream(maxSize);

       VarInt.putVarInt(actionKeyBytes.length, sink);
       sink.write(actionKeyBytes);

       DigestUtils.write(entry.getFileDigest(), sink);

       VarInt.putVarInt(entry.discoversInputs() ? files.size() : NO_INPUT_DISCOVERY_COUNT, sink);
       for (String file : files) {
         VarInt.putVarInt(indexer.getOrCreateIndex(file), sink);
       }

       DigestUtils.write(entry.getUsedClientEnvDigest(), sink);

       return sink.toByteArray();
     } catch (IOException e) {
       // This Exception can never be thrown by ByteArrayOutputStream.
       throw new AssertionError(e);
     }
   }

   /**
    * Creates new action cache entry using given compressed entry data. Data
    * will stay in the compressed format until entry is actually used by the
    * dependency checker.
    */
   private static ActionCache.Entry decode(StringIndexer indexer, byte[] data) throws IOException {
     try {
       ByteBuffer source = ByteBuffer.wrap(data);

       byte[] actionKeyBytes = new byte[VarInt.getVarInt(source)];
       source.get(actionKeyBytes);
       String actionKey = new String(actionKeyBytes, ISO_8859_1);

       byte[] digest = DigestUtils.read(source);

       int count = VarInt.getVarInt(source);
       ImmutableList<String> files = null;
       if (count != NO_INPUT_DISCOVERY_COUNT) {
         ImmutableList.Builder<String> builder = ImmutableList.builderWithExpectedSize(count);
         for (int i = 0; i < count; i++) {
           int id = VarInt.getVarInt(source);
           String filename = (id >= 0 ? indexer.getStringForIndex(id) : null);
           if (filename == null) {
             throw new IOException("Corrupted file index");
           }
           builder.add(filename);
         }
         files = builder.build();
       }

       byte[] usedClientEnvDigest = DigestUtils.read(source);

       if (source.remaining() > 0) {
         throw new IOException("serialized entry data has not been fully decoded");
       }
       return new ActionCache.Entry(actionKey, usedClientEnvDigest, files, digest);
     } catch (BufferUnderflowException e) {
       throw new IOException("encoded entry data is incomplete", e);
     }
   }

   @Override
   public void accountHit() {
     hits.incrementAndGet();
   }

   @Override
   public void accountMiss(MissReason reason) {
     AtomicInteger counter = misses.get(reason);
     Preconditions.checkNotNull(counter, "Miss reason %s was not registered in the misses map "
         + "during cache construction", reason);
     counter.incrementAndGet();
   }

   @Override
   public void mergeIntoActionCacheStatistics(ActionCacheStatistics.Builder builder) {
     builder.setHits(hits.get());

     int totalMisses = 0;
     for (Map.Entry<MissReason, AtomicInteger> entry : misses.entrySet()) {
       int count = entry.getValue().get();
       builder.addMissDetailsBuilder().setReason(entry.getKey()).setCount(count);
       totalMisses += count;
     }
     builder.setMisses(totalMisses);
   }

   @Override
   public void resetStatistics() {
     hits.set(0);
     for (Map.Entry<MissReason, AtomicInteger> entry : misses.entrySet()) {
       entry.getValue().set(0);
     }
   }
 }
	// 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.actions.cache;

	import static java.nio.charset.StandardCharsets.ISO_8859_1;

	import com.google.common.base.Preconditions;
	import com.google.common.collect.ImmutableList;
	import com.google.devtools.build.lib.actions.cache.Protos.ActionCacheStatistics;
	import com.google.devtools.build.lib.actions.cache.Protos.ActionCacheStatistics.MissReason;
	import com.google.devtools.build.lib.clock.Clock;
	import com.google.devtools.build.lib.concurrent.ThreadSafety.ConditionallyThreadSafe;
	import com.google.devtools.build.lib.profiler.AutoProfiler;
	import com.google.devtools.build.lib.util.PersistentMap;
	import com.google.devtools.build.lib.util.StringIndexer;
	import com.google.devtools.build.lib.util.VarInt;
	import com.google.devtools.build.lib.vfs.Path;
	import com.google.devtools.build.lib.vfs.UnixGlob;
	import java.io.ByteArrayOutputStream;
	import java.io.DataInputStream;
	import java.io.DataOutputStream;
	import java.io.IOException;
	import java.io.PrintStream;
	import java.nio.BufferUnderflowException;
	import java.nio.ByteBuffer;
	import java.util.Collection;
	import java.util.EnumMap;
	import java.util.HashMap;
	import java.util.Map;
	import java.util.concurrent.TimeUnit;
	import java.util.concurrent.atomic.AtomicInteger;
	import java.util.logging.Logger;

	/**
	* An implementation of the ActionCache interface that uses a {@link StringIndexer} to reduce memory
	* footprint and saves cached actions using the {@link PersistentMap}.
	*/
	@ConditionallyThreadSafe // condition: each instance must instantiated with
	// different cache root
	public class CompactPersistentActionCache implements ActionCache {
	private static final int SAVE_INTERVAL_SECONDS = 3;
	// Log if periodically saving the action cache incurs more than 5% overhead.
	private static final int MIN_TIME_FOR_LOGGING_MILLIS =
	(int) (TimeUnit.SECONDS.toMillis(SAVE_INTERVAL_SECONDS) * 0.05);

	// Key of the action cache record that holds information used to verify referential integrity
	// between action cache and string indexer. Must be < 0 to avoid conflict with real action
	// cache records.
	private static final int VALIDATION_KEY = -10;

	private static final int NO_INPUT_DISCOVERY_COUNT = -1;

	private static final int VERSION = 12;

	private static final Logger logger =
	Logger.getLogger(CompactPersistentActionCache.class.getName());

	private final class ActionMap extends PersistentMap<Integer, byte[]> {
	private final Clock clock;
	private long nextUpdateSecs;

	public ActionMap(Map<Integer, byte[]> map, Clock clock, Path mapFile, Path journalFile)
	throws IOException {
	super(VERSION, map, mapFile, journalFile);
	this.clock = clock;
	// Using nanoTime. currentTimeMillis may not provide enough granularity.
	nextUpdateSecs = TimeUnit.NANOSECONDS.toSeconds(clock.nanoTime()) + SAVE_INTERVAL_SECONDS;
	load();
	}

	@Override
	protected boolean updateJournal() {
	// Using nanoTime. currentTimeMillis may not provide enough granularity.
	long timeSecs = TimeUnit.NANOSECONDS.toSeconds(clock.nanoTime());
	if (SAVE_INTERVAL_SECONDS == 0 \|\| timeSecs > nextUpdateSecs) {
	nextUpdateSecs = timeSecs + SAVE_INTERVAL_SECONDS;
	// Force flushing of the PersistentStringIndexer instance. This is needed to ensure
	// that filename index data on disk is always up-to-date when we save action cache
	// data.
	indexer.flush();
	return true;
	}
	return false;
	}

	@Override
	protected void markAsDirty() {
	try (AutoProfiler p =
	AutoProfiler.logged("slow write to journal", logger, MIN_TIME_FOR_LOGGING_MILLIS)) {
	super.markAsDirty();
	}
	}

	@Override
	protected boolean keepJournal() {
	// We must first flush the journal to get an accurate measure of its size.
	forceFlush();
	try {
	return journalSize() * 100 < cacheSize();
	} catch (IOException e) {
	return false;
	}
	}

	@Override
	protected Integer readKey(DataInputStream in) throws IOException {
	return in.readInt();
	}

	@Override
	protected byte[] readValue(DataInputStream in)
	throws IOException {
	int size = in.readInt();
	if (size < 0) {
	throw new IOException("found negative array size: " + size);
	}
	byte[] data = new byte[size];
	in.readFully(data);
	return data;
	}

	@Override
	protected void writeKey(Integer key, DataOutputStream out)
	throws IOException {
	out.writeInt(key);
	}

	@Override
	// TODO(bazel-team): (2010) This method, writeKey() and related Metadata methods
	// should really use protocol messages. Doing so would allow easy inspection
	// of the action cache content and, more importantly, would cut down on the
	// need to change VERSION to different number every time we touch those
	// methods. Especially when we'll start to add stuff like statistics for
	// each action.
	protected void writeValue(byte[] value, DataOutputStream out)
	throws IOException {
	out.writeInt(value.length);
	out.write(value);
	}
	}

	private final PersistentMap<Integer, byte[]> map;
	private final PersistentStringIndexer indexer;

	private final AtomicInteger hits = new AtomicInteger();
	private final Map<MissReason, AtomicInteger> misses = new EnumMap<>(MissReason.class);

	public CompactPersistentActionCache(Path cacheRoot, Clock clock) throws IOException {
	Path cacheFile = cacheFile(cacheRoot);
	Path journalFile = journalFile(cacheRoot);
	Path indexFile = cacheRoot.getChild("filename_index_v" + VERSION + ".blaze");
	// we can now use normal hash map as backing map, since dependency checker
	// will manually purge records from the action cache.
	Map<Integer, byte[]> backingMap = new HashMap<>();

	try {
	indexer = PersistentStringIndexer.newPersistentStringIndexer(indexFile, clock);
	} catch (IOException e) {
	renameCorruptedFiles(cacheRoot);
	throw new IOException("Failed to load filename index data", e);
	}

	try {
	map = new ActionMap(backingMap, clock, cacheFile, journalFile);
	} catch (IOException e) {
	renameCorruptedFiles(cacheRoot);
	throw new IOException("Failed to load action cache data", e);
	}

	// Validate referential integrity between two collections.
	if (!map.isEmpty()) {
	String integrityError = validateIntegrity(indexer.size(), map.get(VALIDATION_KEY));
	if (integrityError != null) {
	renameCorruptedFiles(cacheRoot);
	throw new IOException("Failed action cache referential integrity check: " + integrityError);
	}
	}

	for (MissReason reason : MissReason.values()) {
	if (reason == MissReason.UNRECOGNIZED) {
	// The presence of this enum value is a protobuf artifact and confuses our metrics
	// externalization code below. Just skip it.
	continue;
	}
	misses.put(reason, new AtomicInteger(0));
	}
	}

	/**
	* Rename corrupted files so they could be analyzed later. This would also ensure
	* that next initialization attempt will create empty cache.
	*/
	private static void renameCorruptedFiles(Path cacheRoot) {
	try {
	for (Path path : UnixGlob.forPath(cacheRoot).addPattern("action__v" + VERSION + ".")
	.glob()) {
	path.renameTo(path.getParentDirectory().getChild(path.getBaseName() + ".bad"));
	}
	for (Path path : UnixGlob.forPath(cacheRoot).addPattern("filename__v" + VERSION + ".")
	.glob()) {
	path.renameTo(path.getParentDirectory().getChild(path.getBaseName() + ".bad"));
	}
	} catch (UnixGlob.BadPattern ex) {
	throw new IllegalStateException(ex); // can't happen
	} catch (IOException e) {
	// do nothing
	}
	}

	/**
	* @return non-null error description if indexer contains no data or integrity check has failed,
	* and null otherwise
	*/
	private static String validateIntegrity(int indexerSize, byte[] validationRecord) {
	if (indexerSize == 0) {
	return "empty index";
	}
	if (validationRecord == null) {
	return "no validation record";
	}
	try {
	int validationSize = ByteBuffer.wrap(validationRecord).asIntBuffer().get();
	if (validationSize <= indexerSize) {
	return null;
	} else {
	return String.format("Validation mismatch: validation entry %d is too large " +
	"compared to index size %d", validationSize, indexerSize);
	}
	} catch (BufferUnderflowException e) {
	return e.getMessage();
	}
	}

	public static Path cacheFile(Path cacheRoot) {
	return cacheRoot.getChild("action_cache_v" + VERSION + ".blaze");
	}

	public static Path journalFile(Path cacheRoot) {
	return cacheRoot.getChild("action_journal_v" + VERSION + ".blaze");
	}

	@Override
	public ActionCache.Entry get(String key) {
	int index = indexer.getIndex(key);
	if (index < 0) {
	return null;
	}
	byte[] data;
	synchronized (this) {
	data = map.get(index);
	}
	try {
	return data != null ? CompactPersistentActionCache.decode(indexer, data) : null;
	} catch (IOException e) {
	// return entry marked as corrupted.
	return ActionCache.Entry.CORRUPTED;
	}
	}

	@Override
	public void put(String key, ActionCache.Entry entry) {
	// Encode record. Note that both methods may create new mappings in the indexer.
	int index = indexer.getOrCreateIndex(key);
	byte[] content = encode(indexer, entry);

	// Update validation record.
	ByteBuffer buffer = ByteBuffer.allocate(4); // size of int in bytes
	int indexSize = indexer.size();
	buffer.asIntBuffer().put(indexSize);

	// Note the benign race condition here in which two threads might race on
	// updating the VALIDATION_KEY. If the most recent update loses the race,
	// a value lower than the indexer size will remain in the validation record.
	// This will still pass the integrity check.
	synchronized (this) {
	map.put(VALIDATION_KEY, buffer.array());
	// Now update record itself.
	map.put(index, content);
	}
	}

	@Override
	public synchronized void remove(String key) {
	map.remove(indexer.getIndex(key));
	}

	@Override
	public synchronized long save() throws IOException {
	long indexSize = indexer.save();
	long mapSize = map.save();
	return indexSize + mapSize;
	}

	@Override
	public void clear() {
	indexer.clear();
	map.clear();
	}

	@Override
	public synchronized String toString() {
	StringBuilder builder = new StringBuilder();
	// map.size() - 1 to avoid counting the validation key.
	builder.append("Action cache (" + (map.size() - 1) + " records):\n");
	int size = map.size() > 1000 ? 10 : map.size();
	int ct = 0;
	for (Map.Entry<Integer, byte[]> entry: map.entrySet()) {
	if (entry.getKey() == VALIDATION_KEY) { continue; }
	String content;
	try {
	content = decode(indexer, entry.getValue()).toString();
	} catch (IOException e) {
	content = e + "\n";
	}
	builder.append("-> ").append(indexer.getStringForIndex(entry.getKey())).append("\n")
	.append(content).append(" packed_len = ").append(entry.getValue().length).append("\n");
	if (++ct > size) {
	builder.append("...");
	break;
	}
	}
	return builder.toString();
	}

	/**
	* Dumps action cache content.
	*/
	@Override
	public synchronized void dump(PrintStream out) {
	out.println("String indexer content:\n");
	out.println(indexer);
	out.println("Action cache (" + map.size() + " records):\n");
	for (Map.Entry<Integer, byte[]> entry: map.entrySet()) {
	if (entry.getKey() == VALIDATION_KEY) { continue; }
	String content;
	try {
	content = CompactPersistentActionCache.decode(indexer, entry.getValue()).toString();
	} catch (IOException e) {
	content = e + "\n";
	}
	out.println(entry.getKey() + ", " + indexer.getStringForIndex(entry.getKey()) + ":\n"
	+ content + "\n packed_len = " + entry.getValue().length + "\n");
	}
	}

	/**
	* @return action data encoded as a byte[] array.
	*/
	private static byte[] encode(StringIndexer indexer, ActionCache.Entry entry) {
	Preconditions.checkState(!entry.isCorrupted());

	try {
	byte[] actionKeyBytes = entry.getActionKey().getBytes(ISO_8859_1);
	Collection<String> files = entry.getPaths();

	// Estimate the size of the buffer:
	// 5 bytes max for the actionKey length
	// + the actionKey itself
	// + 32 bytes for the digest
	// + 5 bytes max for the file list length
	// + 5 bytes max for each file id
	// + 32 bytes for the environment digest
	int maxSize =
	VarInt.MAX_VARINT_SIZE
	+ actionKeyBytes.length
	+ DigestUtils.ESTIMATED_SIZE
	+ VarInt.MAX_VARINT_SIZE
	+ files.size() * VarInt.MAX_VARINT_SIZE
	+ DigestUtils.ESTIMATED_SIZE;
	ByteArrayOutputStream sink = new ByteArrayOutputStream(maxSize);

	VarInt.putVarInt(actionKeyBytes.length, sink);
	sink.write(actionKeyBytes);

	DigestUtils.write(entry.getFileDigest(), sink);

	VarInt.putVarInt(entry.discoversInputs() ? files.size() : NO_INPUT_DISCOVERY_COUNT, sink);
	for (String file : files) {
	VarInt.putVarInt(indexer.getOrCreateIndex(file), sink);
	}

	DigestUtils.write(entry.getUsedClientEnvDigest(), sink);

	return sink.toByteArray();
	} catch (IOException e) {
	// This Exception can never be thrown by ByteArrayOutputStream.
	throw new AssertionError(e);
	}
	}

	/**
	* Creates new action cache entry using given compressed entry data. Data
	* will stay in the compressed format until entry is actually used by the
	* dependency checker.
	*/
	private static ActionCache.Entry decode(StringIndexer indexer, byte[] data) throws IOException {
	try {
	ByteBuffer source = ByteBuffer.wrap(data);

	byte[] actionKeyBytes = new byte[VarInt.getVarInt(source)];
	source.get(actionKeyBytes);
	String actionKey = new String(actionKeyBytes, ISO_8859_1);

	byte[] digest = DigestUtils.read(source);

	int count = VarInt.getVarInt(source);
	ImmutableList<String> files = null;
	if (count != NO_INPUT_DISCOVERY_COUNT) {
	ImmutableList.Builder<String> builder = ImmutableList.builderWithExpectedSize(count);
	for (int i = 0; i < count; i++) {
	int id = VarInt.getVarInt(source);
	String filename = (id >= 0 ? indexer.getStringForIndex(id) : null);
	if (filename == null) {
	throw new IOException("Corrupted file index");
	}
	builder.add(filename);
	}
	files = builder.build();
	}

	byte[] usedClientEnvDigest = DigestUtils.read(source);

	if (source.remaining() > 0) {
	throw new IOException("serialized entry data has not been fully decoded");
	}
	return new ActionCache.Entry(actionKey, usedClientEnvDigest, files, digest);
	} catch (BufferUnderflowException e) {
	throw new IOException("encoded entry data is incomplete", e);
	}
	}

	@Override
	public void accountHit() {
	hits.incrementAndGet();
	}

	@Override
	public void accountMiss(MissReason reason) {
	AtomicInteger counter = misses.get(reason);
	Preconditions.checkNotNull(counter, "Miss reason %s was not registered in the misses map "
	+ "during cache construction", reason);
	counter.incrementAndGet();
	}

	@Override
	public void mergeIntoActionCacheStatistics(ActionCacheStatistics.Builder builder) {
	builder.setHits(hits.get());

	int totalMisses = 0;
	for (Map.Entry<MissReason, AtomicInteger> entry : misses.entrySet()) {
	int count = entry.getValue().get();
	builder.addMissDetailsBuilder().setReason(entry.getKey()).setCount(count);
	totalMisses += count;
	}
	builder.setMisses(totalMisses);
	}

	@Override
	public void resetStatistics() {
	hits.set(0);
	for (Map.Entry<MissReason, AtomicInteger> entry : misses.entrySet()) {
	entry.getValue().set(0);
	}
	}
	}