src/cmd/go/internal/cache/cache.go - go - Git at Google

 // Copyright 2017 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 // Package cache implements a build artifact cache.
 package cache

 import (
 	"bytes"
 	"crypto/sha256"
 	"encoding/hex"
 	"errors"
 	"fmt"
 	"io"
 	"io/ioutil"
 	"os"
 	"path/filepath"
 	"strconv"
 	"strings"
 	"time"

 	"cmd/go/internal/renameio"
 )

 // An ActionID is a cache action key, the hash of a complete description of a
 // repeatable computation (command line, environment variables,
 // input file contents, executable contents).
 type ActionID [HashSize]byte

 // An OutputID is a cache output key, the hash of an output of a computation.
 type OutputID [HashSize]byte

 // A Cache is a package cache, backed by a file system directory tree.
 type Cache struct {
 	dir string
 	now func() time.Time
 }

 // Open opens and returns the cache in the given directory.
 //
 // It is safe for multiple processes on a single machine to use the
 // same cache directory in a local file system simultaneously.
 // They will coordinate using operating system file locks and may
 // duplicate effort but will not corrupt the cache.
 //
 // However, it is NOT safe for multiple processes on different machines
 // to share a cache directory (for example, if the directory were stored
 // in a network file system). File locking is notoriously unreliable in
 // network file systems and may not suffice to protect the cache.
 //
 func Open(dir string) (*Cache, error) {
 	info, err := os.Stat(dir)
 	if err != nil {
 		return nil, err
 	}
 	if !info.IsDir() {
 		return nil, &os.PathError{Op: "open", Path: dir, Err: fmt.Errorf("not a directory")}
 	}
 	for i := 0; i < 256; i++ {
 		name := filepath.Join(dir, fmt.Sprintf("%02x", i))
 		if err := os.MkdirAll(name, 0777); err != nil {
 			return nil, err
 		}
 	}
 	c := &Cache{
 		dir: dir,
 		now: time.Now,
 	}
 	return c, nil
 }

 // fileName returns the name of the file corresponding to the given id.
 func (c *Cache) fileName(id [HashSize]byte, key string) string {
 	return filepath.Join(c.dir, fmt.Sprintf("%02x", id[0]), fmt.Sprintf("%x", id)+"-"+key)
 }

 // An entryNotFoundError indicates that a cache entry was not found, with an
 // optional underlying reason.
 type entryNotFoundError struct {
 	Err error
 }

 func (e *entryNotFoundError) Error() string {
 	if e.Err == nil {
 		return "cache entry not found"
 	}
 	return fmt.Sprintf("cache entry not found: %v", e.Err)
 }

 func (e *entryNotFoundError) Unwrap() error {
 	return e.Err
 }

 const (
 	// action entry file is "v1 <hex id> <hex out> <decimal size space-padded to 20 bytes> <unixnano space-padded to 20 bytes>\n"
 	hexSize   = HashSize * 2
 	entrySize = 2 + 1 + hexSize + 1 + hexSize + 1 + 20 + 1 + 20 + 1
 )

 // verify controls whether to run the cache in verify mode.
 // In verify mode, the cache always returns errMissing from Get
 // but then double-checks in Put that the data being written
 // exactly matches any existing entry. This provides an easy
 // way to detect program behavior that would have been different
 // had the cache entry been returned from Get.
 //
 // verify is enabled by setting the environment variable
 // GODEBUG=gocacheverify=1.
 var verify = false

 var errVerifyMode = errors.New("gocachverify=1")

 // DebugTest is set when GODEBUG=gocachetest=1 is in the environment.
 var DebugTest = false

 func init() { initEnv() }

 func initEnv() {
 	verify = false
 	debugHash = false
 	debug := strings.Split(os.Getenv("GODEBUG"), ",")
 	for _, f := range debug {
 		if f == "gocacheverify=1" {
 			verify = true
 		}
 		if f == "gocachehash=1" {
 			debugHash = true
 		}
 		if f == "gocachetest=1" {
 			DebugTest = true
 		}
 	}
 }

 // Get looks up the action ID in the cache,
 // returning the corresponding output ID and file size, if any.
 // Note that finding an output ID does not guarantee that the
 // saved file for that output ID is still available.
 func (c *Cache) Get(id ActionID) (Entry, error) {
 	if verify {
 		return Entry{}, &entryNotFoundError{Err: errVerifyMode}
 	}
 	return c.get(id)
 }

 type Entry struct {
 	OutputID OutputID
 	Size     int64
 	Time     time.Time
 }

 // get is Get but does not respect verify mode, so that Put can use it.
 func (c *Cache) get(id ActionID) (Entry, error) {
 	missing := func(reason error) (Entry, error) {
 		return Entry{}, &entryNotFoundError{Err: reason}
 	}
 	f, err := os.Open(c.fileName(id, "a"))
 	if err != nil {
 		return missing(err)
 	}
 	defer f.Close()
 	entry := make([]byte, entrySize+1) // +1 to detect whether f is too long
 	if n, err := io.ReadFull(f, entry); n > entrySize {
 		return missing(errors.New("too long"))
 	} else if err != io.ErrUnexpectedEOF {
 		if err == io.EOF {
 			return missing(errors.New("file is empty"))
 		}
 		return missing(err)
 	} else if n < entrySize {
 		return missing(errors.New("entry file incomplete"))
 	}
 	if entry[0] != 'v' || entry[1] != '1' || entry[2] != ' ' || entry[3+hexSize] != ' ' || entry[3+hexSize+1+hexSize] != ' ' || entry[3+hexSize+1+hexSize+1+20] != ' ' || entry[entrySize-1] != '\n' {
 		return missing(errors.New("invalid header"))
 	}
 	eid, entry := entry[3:3+hexSize], entry[3+hexSize:]
 	eout, entry := entry[1:1+hexSize], entry[1+hexSize:]
 	esize, entry := entry[1:1+20], entry[1+20:]
 	etime, entry := entry[1:1+20], entry[1+20:]
 	var buf [HashSize]byte
 	if _, err := hex.Decode(buf[:], eid); err != nil {
 		return missing(fmt.Errorf("decoding ID: %v", err))
 	} else if buf != id {
 		return missing(errors.New("mismatched ID"))
 	}
 	if _, err := hex.Decode(buf[:], eout); err != nil {
 		return missing(fmt.Errorf("decoding output ID: %v", err))
 	}
 	i := 0
 	for i < len(esize) && esize[i] == ' ' {
 		i++
 	}
 	size, err := strconv.ParseInt(string(esize[i:]), 10, 64)
 	if err != nil {
 		return missing(fmt.Errorf("parsing size: %v", err))
 	} else if size < 0 {
 		return missing(errors.New("negative size"))
 	}
 	i = 0
 	for i < len(etime) && etime[i] == ' ' {
 		i++
 	}
 	tm, err := strconv.ParseInt(string(etime[i:]), 10, 64)
 	if err != nil {
 		return missing(fmt.Errorf("parsing timestamp: %v", err))
 	} else if tm < 0 {
 		return missing(errors.New("negative timestamp"))
 	}

 	c.used(c.fileName(id, "a"))

 	return Entry{buf, size, time.Unix(0, tm)}, nil
 }

 // GetFile looks up the action ID in the cache and returns
 // the name of the corresponding data file.
 func (c *Cache) GetFile(id ActionID) (file string, entry Entry, err error) {
 	entry, err = c.Get(id)
 	if err != nil {
 		return "", Entry{}, err
 	}
 	file = c.OutputFile(entry.OutputID)
 	info, err := os.Stat(file)
 	if err != nil {
 		return "", Entry{}, &entryNotFoundError{Err: err}
 	}
 	if info.Size() != entry.Size {
 		return "", Entry{}, &entryNotFoundError{Err: errors.New("file incomplete")}
 	}
 	return file, entry, nil
 }

 // GetBytes looks up the action ID in the cache and returns
 // the corresponding output bytes.
 // GetBytes should only be used for data that can be expected to fit in memory.
 func (c *Cache) GetBytes(id ActionID) ([]byte, Entry, error) {
 	entry, err := c.Get(id)
 	if err != nil {
 		return nil, entry, err
 	}
 	data, _ := ioutil.ReadFile(c.OutputFile(entry.OutputID))
 	if sha256.Sum256(data) != entry.OutputID {
 		return nil, entry, &entryNotFoundError{Err: errors.New("bad checksum")}
 	}
 	return data, entry, nil
 }

 // OutputFile returns the name of the cache file storing output with the given OutputID.
 func (c *Cache) OutputFile(out OutputID) string {
 	file := c.fileName(out, "d")
 	c.used(file)
 	return file
 }

 // Time constants for cache expiration.
 //
 // We set the mtime on a cache file on each use, but at most one per mtimeInterval (1 hour),
 // to avoid causing many unnecessary inode updates. The mtimes therefore
 // roughly reflect "time of last use" but may in fact be older by at most an hour.
 //
 // We scan the cache for entries to delete at most once per trimInterval (1 day).
 //
 // When we do scan the cache, we delete entries that have not been used for
 // at least trimLimit (5 days). Statistics gathered from a month of usage by
 // Go developers found that essentially all reuse of cached entries happened
 // within 5 days of the previous reuse. See golang.org/issue/22990.
 const (
 	mtimeInterval = 1 * time.Hour
 	trimInterval  = 24 * time.Hour
 	trimLimit     = 5 * 24 * time.Hour
 )

 // used makes a best-effort attempt to update mtime on file,
 // so that mtime reflects cache access time.
 //
 // Because the reflection only needs to be approximate,
 // and to reduce the amount of disk activity caused by using
 // cache entries, used only updates the mtime if the current
 // mtime is more than an hour old. This heuristic eliminates
 // nearly all of the mtime updates that would otherwise happen,
 // while still keeping the mtimes useful for cache trimming.
 func (c *Cache) used(file string) {
 	info, err := os.Stat(file)
 	if err == nil && c.now().Sub(info.ModTime()) < mtimeInterval {
 		return
 	}
 	os.Chtimes(file, c.now(), c.now())
 }

 // Trim removes old cache entries that are likely not to be reused.
 func (c *Cache) Trim() {
 	now := c.now()

 	// We maintain in dir/trim.txt the time of the last completed cache trim.
 	// If the cache has been trimmed recently enough, do nothing.
 	// This is the common case.
 	data, _ := renameio.ReadFile(filepath.Join(c.dir, "trim.txt"))
 	t, err := strconv.ParseInt(strings.TrimSpace(string(data)), 10, 64)
 	if err == nil && now.Sub(time.Unix(t, 0)) < trimInterval {
 		return
 	}

 	// Trim each of the 256 subdirectories.
 	// We subtract an additional mtimeInterval
 	// to account for the imprecision of our "last used" mtimes.
 	cutoff := now.Add(-trimLimit - mtimeInterval)
 	for i := 0; i < 256; i++ {
 		subdir := filepath.Join(c.dir, fmt.Sprintf("%02x", i))
 		c.trimSubdir(subdir, cutoff)
 	}

 	// Ignore errors from here: if we don't write the complete timestamp, the
 	// cache will appear older than it is, and we'll trim it again next time.
 	renameio.WriteFile(filepath.Join(c.dir, "trim.txt"), []byte(fmt.Sprintf("%d", now.Unix())), 0666)
 }

 // trimSubdir trims a single cache subdirectory.
 func (c *Cache) trimSubdir(subdir string, cutoff time.Time) {
 	// Read all directory entries from subdir before removing
 	// any files, in case removing files invalidates the file offset
 	// in the directory scan. Also, ignore error from f.Readdirnames,
 	// because we don't care about reporting the error and we still
 	// want to process any entries found before the error.
 	f, err := os.Open(subdir)
 	if err != nil {
 		return
 	}
 	names, _ := f.Readdirnames(-1)
 	f.Close()

 	for _, name := range names {
 		// Remove only cache entries (xxxx-a and xxxx-d).
 		if !strings.HasSuffix(name, "-a") && !strings.HasSuffix(name, "-d") {
 			continue
 		}
 		entry := filepath.Join(subdir, name)
 		info, err := os.Stat(entry)
 		if err == nil && info.ModTime().Before(cutoff) {
 			os.Remove(entry)
 		}
 	}
 }

 // putIndexEntry adds an entry to the cache recording that executing the action
 // with the given id produces an output with the given output id (hash) and size.
 func (c *Cache) putIndexEntry(id ActionID, out OutputID, size int64, allowVerify bool) error {
 	// Note: We expect that for one reason or another it may happen
 	// that repeating an action produces a different output hash
 	// (for example, if the output contains a time stamp or temp dir name).
 	// While not ideal, this is also not a correctness problem, so we
 	// don't make a big deal about it. In particular, we leave the action
 	// cache entries writable specifically so that they can be overwritten.
 	//
 	// Setting GODEBUG=gocacheverify=1 does make a big deal:
 	// in verify mode we are double-checking that the cache entries
 	// are entirely reproducible. As just noted, this may be unrealistic
 	// in some cases but the check is also useful for shaking out real bugs.
 	entry := fmt.Sprintf("v1 %x %x %20d %20d\n", id, out, size, time.Now().UnixNano())
 	if verify && allowVerify {
 		old, err := c.get(id)
 		if err == nil && (old.OutputID != out || old.Size != size) {
 			// panic to show stack trace, so we can see what code is generating this cache entry.
 			msg := fmt.Sprintf("go: internal cache error: cache verify failed: id=%x changed:<<<\n%s\n>>>\nold: %x %d\nnew: %x %d", id, reverseHash(id), out, size, old.OutputID, old.Size)
 			panic(msg)
 		}
 	}
 	file := c.fileName(id, "a")

 	// Copy file to cache directory.
 	mode := os.O_WRONLY | os.O_CREATE
 	f, err := os.OpenFile(file, mode, 0666)
 	if err != nil {
 		return err
 	}
 	_, err = f.WriteString(entry)
 	if err == nil {
 		// Truncate the file only *after* writing it.
 		// (This should be a no-op, but truncate just in case of previous corruption.)
 		//
 		// This differs from ioutil.WriteFile, which truncates to 0 *before* writing
 		// via os.O_TRUNC. Truncating only after writing ensures that a second write
 		// of the same content to the same file is idempotent, and does not — even
 		// temporarily! — undo the effect of the first write.
 		err = f.Truncate(int64(len(entry)))
 	}
 	if closeErr := f.Close(); err == nil {
 		err = closeErr
 	}
 	if err != nil {
 		// TODO(bcmills): This Remove potentially races with another go command writing to file.
 		// Can we eliminate it?
 		os.Remove(file)
 		return err
 	}
 	os.Chtimes(file, c.now(), c.now()) // mainly for tests

 	return nil
 }

 // Put stores the given output in the cache as the output for the action ID.
 // It may read file twice. The content of file must not change between the two passes.
 func (c *Cache) Put(id ActionID, file io.ReadSeeker) (OutputID, int64, error) {
 	return c.put(id, file, true)
 }

 // PutNoVerify is like Put but disables the verify check
 // when GODEBUG=goverifycache=1 is set.
 // It is meant for data that is OK to cache but that we expect to vary slightly from run to run,
 // like test output containing times and the like.
 func (c *Cache) PutNoVerify(id ActionID, file io.ReadSeeker) (OutputID, int64, error) {
 	return c.put(id, file, false)
 }

 func (c *Cache) put(id ActionID, file io.ReadSeeker, allowVerify bool) (OutputID, int64, error) {
 	// Compute output ID.
 	h := sha256.New()
 	if _, err := file.Seek(0, 0); err != nil {
 		return OutputID{}, 0, err
 	}
 	size, err := io.Copy(h, file)
 	if err != nil {
 		return OutputID{}, 0, err
 	}
 	var out OutputID
 	h.Sum(out[:0])

 	// Copy to cached output file (if not already present).
 	if err := c.copyFile(file, out, size); err != nil {
 		return out, size, err
 	}

 	// Add to cache index.
 	return out, size, c.putIndexEntry(id, out, size, allowVerify)
 }

 // PutBytes stores the given bytes in the cache as the output for the action ID.
 func (c *Cache) PutBytes(id ActionID, data []byte) error {
 	_, _, err := c.Put(id, bytes.NewReader(data))
 	return err
 }

 // copyFile copies file into the cache, expecting it to have the given
 // output ID and size, if that file is not present already.
 func (c *Cache) copyFile(file io.ReadSeeker, out OutputID, size int64) error {
 	name := c.fileName(out, "d")
 	info, err := os.Stat(name)
 	if err == nil && info.Size() == size {
 		// Check hash.
 		if f, err := os.Open(name); err == nil {
 			h := sha256.New()
 			io.Copy(h, f)
 			f.Close()
 			var out2 OutputID
 			h.Sum(out2[:0])
 			if out == out2 {
 				return nil
 			}
 		}
 		// Hash did not match. Fall through and rewrite file.
 	}

 	// Copy file to cache directory.
 	mode := os.O_RDWR | os.O_CREATE
 	if err == nil && info.Size() > size { // shouldn't happen but fix in case
 		mode |= os.O_TRUNC
 	}
 	f, err := os.OpenFile(name, mode, 0666)
 	if err != nil {
 		return err
 	}
 	defer f.Close()
 	if size == 0 {
 		// File now exists with correct size.
 		// Only one possible zero-length file, so contents are OK too.
 		// Early return here makes sure there's a "last byte" for code below.
 		return nil
 	}

 	// From here on, if any of the I/O writing the file fails,
 	// we make a best-effort attempt to truncate the file f
 	// before returning, to avoid leaving bad bytes in the file.

 	// Copy file to f, but also into h to double-check hash.
 	if _, err := file.Seek(0, 0); err != nil {
 		f.Truncate(0)
 		return err
 	}
 	h := sha256.New()
 	w := io.MultiWriter(f, h)
 	if _, err := io.CopyN(w, file, size-1); err != nil {
 		f.Truncate(0)
 		return err
 	}
 	// Check last byte before writing it; writing it will make the size match
 	// what other processes expect to find and might cause them to start
 	// using the file.
 	buf := make([]byte, 1)
 	if _, err := file.Read(buf); err != nil {
 		f.Truncate(0)
 		return err
 	}
 	h.Write(buf)
 	sum := h.Sum(nil)
 	if !bytes.Equal(sum, out[:]) {
 		f.Truncate(0)
 		return fmt.Errorf("file content changed underfoot")
 	}

 	// Commit cache file entry.
 	if _, err := f.Write(buf); err != nil {
 		f.Truncate(0)
 		return err
 	}
 	if err := f.Close(); err != nil {
 		// Data might not have been written,
 		// but file may look like it is the right size.
 		// To be extra careful, remove cached file.
 		os.Remove(name)
 		return err
 	}
 	os.Chtimes(name, c.now(), c.now()) // mainly for tests

 	return nil
 }
	// Copyright 2017 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	// Package cache implements a build artifact cache.
	package cache

	import (
	"bytes"
	"crypto/sha256"
	"encoding/hex"
	"errors"
	"fmt"
	"io"
	"io/ioutil"
	"os"
	"path/filepath"
	"strconv"
	"strings"
	"time"

	"cmd/go/internal/renameio"
	)

	// An ActionID is a cache action key, the hash of a complete description of a
	// repeatable computation (command line, environment variables,
	// input file contents, executable contents).
	type ActionID [HashSize]byte

	// An OutputID is a cache output key, the hash of an output of a computation.
	type OutputID [HashSize]byte

	// A Cache is a package cache, backed by a file system directory tree.
	type Cache struct {
	dir string
	now func() time.Time
	}

	// Open opens and returns the cache in the given directory.
	//
	// It is safe for multiple processes on a single machine to use the
	// same cache directory in a local file system simultaneously.
	// They will coordinate using operating system file locks and may
	// duplicate effort but will not corrupt the cache.
	//
	// However, it is NOT safe for multiple processes on different machines
	// to share a cache directory (for example, if the directory were stored
	// in a network file system). File locking is notoriously unreliable in
	// network file systems and may not suffice to protect the cache.
	//
	func Open(dir string) (*Cache, error) {
	info, err := os.Stat(dir)
	if err != nil {
	return nil, err
	}
	if !info.IsDir() {
	return nil, &os.PathError{Op: "open", Path: dir, Err: fmt.Errorf("not a directory")}
	}
	for i := 0; i < 256; i++ {
	name := filepath.Join(dir, fmt.Sprintf("%02x", i))
	if err := os.MkdirAll(name, 0777); err != nil {
	return nil, err
	}
	}
	c := &Cache{
	dir: dir,
	now: time.Now,
	}
	return c, nil
	}

	// fileName returns the name of the file corresponding to the given id.
	func (c *Cache) fileName(id [HashSize]byte, key string) string {
	return filepath.Join(c.dir, fmt.Sprintf("%02x", id[0]), fmt.Sprintf("%x", id)+"-"+key)
	}

	// An entryNotFoundError indicates that a cache entry was not found, with an
	// optional underlying reason.
	type entryNotFoundError struct {
	Err error
	}

	func (e *entryNotFoundError) Error() string {
	if e.Err == nil {
	return "cache entry not found"
	}
	return fmt.Sprintf("cache entry not found: %v", e.Err)
	}

	func (e *entryNotFoundError) Unwrap() error {
	return e.Err
	}

	const (
	// action entry file is "v1 <hex id> <hex out> <decimal size space-padded to 20 bytes> <unixnano space-padded to 20 bytes>\n"
	hexSize = HashSize * 2
	entrySize = 2 + 1 + hexSize + 1 + hexSize + 1 + 20 + 1 + 20 + 1
	)

	// verify controls whether to run the cache in verify mode.
	// In verify mode, the cache always returns errMissing from Get
	// but then double-checks in Put that the data being written
	// exactly matches any existing entry. This provides an easy
	// way to detect program behavior that would have been different
	// had the cache entry been returned from Get.
	//
	// verify is enabled by setting the environment variable
	// GODEBUG=gocacheverify=1.
	var verify = false

	var errVerifyMode = errors.New("gocachverify=1")

	// DebugTest is set when GODEBUG=gocachetest=1 is in the environment.
	var DebugTest = false

	func init() { initEnv() }

	func initEnv() {
	verify = false
	debugHash = false
	debug := strings.Split(os.Getenv("GODEBUG"), ",")
	for _, f := range debug {
	if f == "gocacheverify=1" {
	verify = true
	}
	if f == "gocachehash=1" {
	debugHash = true
	}
	if f == "gocachetest=1" {
	DebugTest = true
	}
	}
	}

	// Get looks up the action ID in the cache,
	// returning the corresponding output ID and file size, if any.
	// Note that finding an output ID does not guarantee that the
	// saved file for that output ID is still available.
	func (c *Cache) Get(id ActionID) (Entry, error) {
	if verify {
	return Entry{}, &entryNotFoundError{Err: errVerifyMode}
	}
	return c.get(id)
	}

	type Entry struct {
	OutputID OutputID
	Size int64
	Time time.Time
	}

	// get is Get but does not respect verify mode, so that Put can use it.
	func (c *Cache) get(id ActionID) (Entry, error) {
	missing := func(reason error) (Entry, error) {
	return Entry{}, &entryNotFoundError{Err: reason}
	}
	f, err := os.Open(c.fileName(id, "a"))
	if err != nil {
	return missing(err)
	}
	defer f.Close()
	entry := make([]byte, entrySize+1) // +1 to detect whether f is too long
	if n, err := io.ReadFull(f, entry); n > entrySize {
	return missing(errors.New("too long"))
	} else if err != io.ErrUnexpectedEOF {
	if err == io.EOF {
	return missing(errors.New("file is empty"))
	}
	return missing(err)
	} else if n < entrySize {
	return missing(errors.New("entry file incomplete"))
	}
	if entry[0] != 'v' \|\| entry[1] != '1' \|\| entry[2] != ' ' \|\| entry[3+hexSize] != ' ' \|\| entry[3+hexSize+1+hexSize] != ' ' \|\| entry[3+hexSize+1+hexSize+1+20] != ' ' \|\| entry[entrySize-1] != '\n' {
	return missing(errors.New("invalid header"))
	}
	eid, entry := entry[3:3+hexSize], entry[3+hexSize:]
	eout, entry := entry[1:1+hexSize], entry[1+hexSize:]
	esize, entry := entry[1:1+20], entry[1+20:]
	etime, entry := entry[1:1+20], entry[1+20:]
	var buf [HashSize]byte
	if _, err := hex.Decode(buf[:], eid); err != nil {
	return missing(fmt.Errorf("decoding ID: %v", err))
	} else if buf != id {
	return missing(errors.New("mismatched ID"))
	}
	if _, err := hex.Decode(buf[:], eout); err != nil {
	return missing(fmt.Errorf("decoding output ID: %v", err))
	}
	i := 0
	for i < len(esize) && esize[i] == ' ' {
	i++
	}
	size, err := strconv.ParseInt(string(esize[i:]), 10, 64)
	if err != nil {
	return missing(fmt.Errorf("parsing size: %v", err))
	} else if size < 0 {
	return missing(errors.New("negative size"))
	}
	i = 0
	for i < len(etime) && etime[i] == ' ' {
	i++
	}
	tm, err := strconv.ParseInt(string(etime[i:]), 10, 64)
	if err != nil {
	return missing(fmt.Errorf("parsing timestamp: %v", err))
	} else if tm < 0 {
	return missing(errors.New("negative timestamp"))
	}

	c.used(c.fileName(id, "a"))

	return Entry{buf, size, time.Unix(0, tm)}, nil
	}

	// GetFile looks up the action ID in the cache and returns
	// the name of the corresponding data file.
	func (c *Cache) GetFile(id ActionID) (file string, entry Entry, err error) {
	entry, err = c.Get(id)
	if err != nil {
	return "", Entry{}, err
	}
	file = c.OutputFile(entry.OutputID)
	info, err := os.Stat(file)
	if err != nil {
	return "", Entry{}, &entryNotFoundError{Err: err}
	}
	if info.Size() != entry.Size {
	return "", Entry{}, &entryNotFoundError{Err: errors.New("file incomplete")}
	}
	return file, entry, nil
	}

	// GetBytes looks up the action ID in the cache and returns
	// the corresponding output bytes.
	// GetBytes should only be used for data that can be expected to fit in memory.
	func (c *Cache) GetBytes(id ActionID) ([]byte, Entry, error) {
	entry, err := c.Get(id)
	if err != nil {
	return nil, entry, err
	}
	data, _ := ioutil.ReadFile(c.OutputFile(entry.OutputID))
	if sha256.Sum256(data) != entry.OutputID {
	return nil, entry, &entryNotFoundError{Err: errors.New("bad checksum")}
	}
	return data, entry, nil
	}

	// OutputFile returns the name of the cache file storing output with the given OutputID.
	func (c *Cache) OutputFile(out OutputID) string {
	file := c.fileName(out, "d")
	c.used(file)
	return file
	}

	// Time constants for cache expiration.
	//
	// We set the mtime on a cache file on each use, but at most one per mtimeInterval (1 hour),
	// to avoid causing many unnecessary inode updates. The mtimes therefore
	// roughly reflect "time of last use" but may in fact be older by at most an hour.
	//
	// We scan the cache for entries to delete at most once per trimInterval (1 day).
	//
	// When we do scan the cache, we delete entries that have not been used for
	// at least trimLimit (5 days). Statistics gathered from a month of usage by
	// Go developers found that essentially all reuse of cached entries happened
	// within 5 days of the previous reuse. See golang.org/issue/22990.
	const (
	mtimeInterval = 1 * time.Hour
	trimInterval = 24 * time.Hour
	trimLimit = 5 * 24 * time.Hour
	)

	// used makes a best-effort attempt to update mtime on file,
	// so that mtime reflects cache access time.
	//
	// Because the reflection only needs to be approximate,
	// and to reduce the amount of disk activity caused by using
	// cache entries, used only updates the mtime if the current
	// mtime is more than an hour old. This heuristic eliminates
	// nearly all of the mtime updates that would otherwise happen,
	// while still keeping the mtimes useful for cache trimming.
	func (c *Cache) used(file string) {
	info, err := os.Stat(file)
	if err == nil && c.now().Sub(info.ModTime()) < mtimeInterval {
	return
	}
	os.Chtimes(file, c.now(), c.now())
	}

	// Trim removes old cache entries that are likely not to be reused.
	func (c *Cache) Trim() {
	now := c.now()

	// We maintain in dir/trim.txt the time of the last completed cache trim.
	// If the cache has been trimmed recently enough, do nothing.
	// This is the common case.
	data, _ := renameio.ReadFile(filepath.Join(c.dir, "trim.txt"))
	t, err := strconv.ParseInt(strings.TrimSpace(string(data)), 10, 64)
	if err == nil && now.Sub(time.Unix(t, 0)) < trimInterval {
	return
	}

	// Trim each of the 256 subdirectories.
	// We subtract an additional mtimeInterval
	// to account for the imprecision of our "last used" mtimes.
	cutoff := now.Add(-trimLimit - mtimeInterval)
	for i := 0; i < 256; i++ {
	subdir := filepath.Join(c.dir, fmt.Sprintf("%02x", i))
	c.trimSubdir(subdir, cutoff)
	}

	// Ignore errors from here: if we don't write the complete timestamp, the
	// cache will appear older than it is, and we'll trim it again next time.
	renameio.WriteFile(filepath.Join(c.dir, "trim.txt"), []byte(fmt.Sprintf("%d", now.Unix())), 0666)
	}

	// trimSubdir trims a single cache subdirectory.
	func (c *Cache) trimSubdir(subdir string, cutoff time.Time) {
	// Read all directory entries from subdir before removing
	// any files, in case removing files invalidates the file offset
	// in the directory scan. Also, ignore error from f.Readdirnames,
	// because we don't care about reporting the error and we still
	// want to process any entries found before the error.
	f, err := os.Open(subdir)
	if err != nil {
	return
	}
	names, _ := f.Readdirnames(-1)
	f.Close()

	for _, name := range names {
	// Remove only cache entries (xxxx-a and xxxx-d).
	if !strings.HasSuffix(name, "-a") && !strings.HasSuffix(name, "-d") {
	continue
	}
	entry := filepath.Join(subdir, name)
	info, err := os.Stat(entry)
	if err == nil && info.ModTime().Before(cutoff) {
	os.Remove(entry)
	}
	}
	}

	// putIndexEntry adds an entry to the cache recording that executing the action
	// with the given id produces an output with the given output id (hash) and size.
	func (c *Cache) putIndexEntry(id ActionID, out OutputID, size int64, allowVerify bool) error {
	// Note: We expect that for one reason or another it may happen
	// that repeating an action produces a different output hash
	// (for example, if the output contains a time stamp or temp dir name).
	// While not ideal, this is also not a correctness problem, so we
	// don't make a big deal about it. In particular, we leave the action
	// cache entries writable specifically so that they can be overwritten.
	//
	// Setting GODEBUG=gocacheverify=1 does make a big deal:
	// in verify mode we are double-checking that the cache entries
	// are entirely reproducible. As just noted, this may be unrealistic
	// in some cases but the check is also useful for shaking out real bugs.
	entry := fmt.Sprintf("v1 %x %x %20d %20d\n", id, out, size, time.Now().UnixNano())
	if verify && allowVerify {
	old, err := c.get(id)
	if err == nil && (old.OutputID != out \|\| old.Size != size) {
	// panic to show stack trace, so we can see what code is generating this cache entry.
	msg := fmt.Sprintf("go: internal cache error: cache verify failed: id=%x changed:<<<\n%s\n>>>\nold: %x %d\nnew: %x %d", id, reverseHash(id), out, size, old.OutputID, old.Size)
	panic(msg)
	}
	}
	file := c.fileName(id, "a")

	// Copy file to cache directory.
	mode := os.O_WRONLY \| os.O_CREATE
	f, err := os.OpenFile(file, mode, 0666)
	if err != nil {
	return err
	}
	_, err = f.WriteString(entry)
	if err == nil {
	// Truncate the file only after writing it.
	// (This should be a no-op, but truncate just in case of previous corruption.)
	//
	// This differs from ioutil.WriteFile, which truncates to 0 before writing
	// via os.O_TRUNC. Truncating only after writing ensures that a second write
	// of the same content to the same file is idempotent, and does not — even
	// temporarily! — undo the effect of the first write.
	err = f.Truncate(int64(len(entry)))
	}
	if closeErr := f.Close(); err == nil {
	err = closeErr
	}
	if err != nil {
	// TODO(bcmills): This Remove potentially races with another go command writing to file.
	// Can we eliminate it?
	os.Remove(file)
	return err
	}
	os.Chtimes(file, c.now(), c.now()) // mainly for tests

	return nil
	}

	// Put stores the given output in the cache as the output for the action ID.
	// It may read file twice. The content of file must not change between the two passes.
	func (c *Cache) Put(id ActionID, file io.ReadSeeker) (OutputID, int64, error) {
	return c.put(id, file, true)
	}

	// PutNoVerify is like Put but disables the verify check
	// when GODEBUG=goverifycache=1 is set.
	// It is meant for data that is OK to cache but that we expect to vary slightly from run to run,
	// like test output containing times and the like.
	func (c *Cache) PutNoVerify(id ActionID, file io.ReadSeeker) (OutputID, int64, error) {
	return c.put(id, file, false)
	}

	func (c *Cache) put(id ActionID, file io.ReadSeeker, allowVerify bool) (OutputID, int64, error) {
	// Compute output ID.
	h := sha256.New()
	if _, err := file.Seek(0, 0); err != nil {
	return OutputID{}, 0, err
	}
	size, err := io.Copy(h, file)
	if err != nil {
	return OutputID{}, 0, err
	}
	var out OutputID
	h.Sum(out[:0])

	// Copy to cached output file (if not already present).
	if err := c.copyFile(file, out, size); err != nil {
	return out, size, err
	}

	// Add to cache index.
	return out, size, c.putIndexEntry(id, out, size, allowVerify)
	}

	// PutBytes stores the given bytes in the cache as the output for the action ID.
	func (c *Cache) PutBytes(id ActionID, data []byte) error {
	_, _, err := c.Put(id, bytes.NewReader(data))
	return err
	}

	// copyFile copies file into the cache, expecting it to have the given
	// output ID and size, if that file is not present already.
	func (c *Cache) copyFile(file io.ReadSeeker, out OutputID, size int64) error {
	name := c.fileName(out, "d")
	info, err := os.Stat(name)
	if err == nil && info.Size() == size {
	// Check hash.
	if f, err := os.Open(name); err == nil {
	h := sha256.New()
	io.Copy(h, f)
	f.Close()
	var out2 OutputID
	h.Sum(out2[:0])
	if out == out2 {
	return nil
	}
	}
	// Hash did not match. Fall through and rewrite file.
	}

	// Copy file to cache directory.
	mode := os.O_RDWR \| os.O_CREATE
	if err == nil && info.Size() > size { // shouldn't happen but fix in case
	mode \|= os.O_TRUNC
	}
	f, err := os.OpenFile(name, mode, 0666)
	if err != nil {
	return err
	}
	defer f.Close()
	if size == 0 {
	// File now exists with correct size.
	// Only one possible zero-length file, so contents are OK too.
	// Early return here makes sure there's a "last byte" for code below.
	return nil
	}

	// From here on, if any of the I/O writing the file fails,
	// we make a best-effort attempt to truncate the file f
	// before returning, to avoid leaving bad bytes in the file.

	// Copy file to f, but also into h to double-check hash.
	if _, err := file.Seek(0, 0); err != nil {
	f.Truncate(0)
	return err
	}
	h := sha256.New()
	w := io.MultiWriter(f, h)
	if _, err := io.CopyN(w, file, size-1); err != nil {
	f.Truncate(0)
	return err
	}
	// Check last byte before writing it; writing it will make the size match
	// what other processes expect to find and might cause them to start
	// using the file.
	buf := make([]byte, 1)
	if _, err := file.Read(buf); err != nil {
	f.Truncate(0)
	return err
	}
	h.Write(buf)
	sum := h.Sum(nil)
	if !bytes.Equal(sum, out[:]) {
	f.Truncate(0)
	return fmt.Errorf("file content changed underfoot")
	}

	// Commit cache file entry.
	if _, err := f.Write(buf); err != nil {
	f.Truncate(0)
	return err
	}
	if err := f.Close(); err != nil {
	// Data might not have been written,
	// but file may look like it is the right size.
	// To be extra careful, remove cached file.
	os.Remove(name)
	return err
	}
	os.Chtimes(name, c.now(), c.now()) // mainly for tests

	return nil
	}