cache.go

Documentation: github.com/rogpeppe/go-internal/cache

     1  // Copyright 2017 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package cache implements a build artifact cache.
     6  package cache
     7  
     8  import (
     9  	"bytes"
    10  	"crypto/sha256"
    11  	"encoding/hex"
    12  	"errors"
    13  	"fmt"
    14  	"io"
    15  	"io/fs"
    16  	"os"
    17  	"path/filepath"
    18  	"strconv"
    19  	"strings"
    20  	"time"
    21  
    22  	"github.com/rogpeppe/go-internal/lockedfile"
    23  )
    24  
    25  // An ActionID is a cache action key, the hash of a complete description of a
    26  // repeatable computation (command line, environment variables,
    27  // input file contents, executable contents).
    28  type ActionID [HashSize]byte
    29  
    30  // An OutputID is a cache output key, the hash of an output of a computation.
    31  type OutputID [HashSize]byte
    32  
    33  // A Cache is a package cache, backed by a file system directory tree.
    34  type Cache struct {
    35  	dir string
    36  	now func() time.Time
    37  }
    38  
    39  // Open opens and returns the cache in the given directory.
    40  //
    41  // It is safe for multiple processes on a single machine to use the
    42  // same cache directory in a local file system simultaneously.
    43  // They will coordinate using operating system file locks and may
    44  // duplicate effort but will not corrupt the cache.
    45  //
    46  // However, it is NOT safe for multiple processes on different machines
    47  // to share a cache directory (for example, if the directory were stored
    48  // in a network file system). File locking is notoriously unreliable in
    49  // network file systems and may not suffice to protect the cache.
    50  func Open(dir string) (*Cache, error) {
    51  	info, err := os.Stat(dir)
    52  	if err != nil {
    53  		return nil, err
    54  	}
    55  	if !info.IsDir() {
    56  		return nil, &fs.PathError{Op: "open", Path: dir, Err: fmt.Errorf("not a directory")}
    57  	}
    58  	for i := 0; i < 256; i++ {
    59  		name := filepath.Join(dir, fmt.Sprintf("%02x", i))
    60  		if err := os.MkdirAll(name, 0777); err != nil {
    61  			return nil, err
    62  		}
    63  	}
    64  	c := &Cache{
    65  		dir: dir,
    66  		now: time.Now,
    67  	}
    68  	return c, nil
    69  }
    70  
    71  // fileName returns the name of the file corresponding to the given id.
    72  func (c *Cache) fileName(id [HashSize]byte, key string) string {
    73  	return filepath.Join(c.dir, fmt.Sprintf("%02x", id[0]), fmt.Sprintf("%x", id)+"-"+key)
    74  }
    75  
    76  // An entryNotFoundError indicates that a cache entry was not found, with an
    77  // optional underlying reason.
    78  type entryNotFoundError struct {
    79  	Err error
    80  }
    81  
    82  func (e *entryNotFoundError) Error() string {
    83  	if e.Err == nil {
    84  		return "cache entry not found"
    85  	}
    86  	return fmt.Sprintf("cache entry not found: %v", e.Err)
    87  }
    88  
    89  func (e *entryNotFoundError) Unwrap() error {
    90  	return e.Err
    91  }
    92  
    93  const (
    94  	// action entry file is "v1 <hex id> <hex out> <decimal size space-padded to 20 bytes> <unixnano space-padded to 20 bytes>\n"
    95  	hexSize   = HashSize * 2
    96  	entrySize = 2 + 1 + hexSize + 1 + hexSize + 1 + 20 + 1 + 20 + 1
    97  )
    98  
    99  // verify controls whether to run the cache in verify mode.
   100  // In verify mode, the cache always returns errMissing from Get
   101  // but then double-checks in Put that the data being written
   102  // exactly matches any existing entry. This provides an easy
   103  // way to detect program behavior that would have been different
   104  // had the cache entry been returned from Get.
   105  //
   106  // verify is enabled by setting the environment variable
   107  // GODEBUG=gocacheverify=1.
   108  var verify = false
   109  
   110  var errVerifyMode = errors.New("gocacheverify=1")
   111  
   112  // DebugTest is set when GODEBUG=gocachetest=1 is in the environment.
   113  var DebugTest = false
   114  
   115  func init() { initEnv() }
   116  
   117  func initEnv() {
   118  	verify = false
   119  	debugHash = false
   120  	debug := strings.Split(os.Getenv("GODEBUG"), ",")
   121  	for _, f := range debug {
   122  		if f == "gocacheverify=1" {
   123  			verify = true
   124  		}
   125  		if f == "gocachehash=1" {
   126  			debugHash = true
   127  		}
   128  		if f == "gocachetest=1" {
   129  			DebugTest = true
   130  		}
   131  	}
   132  }
   133  
   134  // Get looks up the action ID in the cache,
   135  // returning the corresponding output ID and file size, if any.
   136  // Note that finding an output ID does not guarantee that the
   137  // saved file for that output ID is still available.
   138  func (c *Cache) Get(id ActionID) (Entry, error) {
   139  	if verify {
   140  		return Entry{}, &entryNotFoundError{Err: errVerifyMode}
   141  	}
   142  	return c.get(id)
   143  }
   144  
   145  type Entry struct {
   146  	OutputID OutputID
   147  	Size     int64
   148  	Time     time.Time
   149  }
   150  
   151  // get is Get but does not respect verify mode, so that Put can use it.
   152  func (c *Cache) get(id ActionID) (Entry, error) {
   153  	missing := func(reason error) (Entry, error) {
   154  		return Entry{}, &entryNotFoundError{Err: reason}
   155  	}
   156  	f, err := os.Open(c.fileName(id, "a"))
   157  	if err != nil {
   158  		return missing(err)
   159  	}
   160  	defer f.Close()
   161  	entry := make([]byte, entrySize+1) // +1 to detect whether f is too long
   162  	if n, err := io.ReadFull(f, entry); n > entrySize {
   163  		return missing(errors.New("too long"))
   164  	} else if err != io.ErrUnexpectedEOF {
   165  		if err == io.EOF {
   166  			return missing(errors.New("file is empty"))
   167  		}
   168  		return missing(err)
   169  	} else if n < entrySize {
   170  		return missing(errors.New("entry file incomplete"))
   171  	}
   172  	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' {
   173  		return missing(errors.New("invalid header"))
   174  	}
   175  	eid, entry := entry[3:3+hexSize], entry[3+hexSize:]
   176  	eout, entry := entry[1:1+hexSize], entry[1+hexSize:]
   177  	esize, entry := entry[1:1+20], entry[1+20:]
   178  	etime, entry := entry[1:1+20], entry[1+20:]
   179  	var buf [HashSize]byte
   180  	if _, err := hex.Decode(buf[:], eid); err != nil {
   181  		return missing(fmt.Errorf("decoding ID: %v", err))
   182  	} else if buf != id {
   183  		return missing(errors.New("mismatched ID"))
   184  	}
   185  	if _, err := hex.Decode(buf[:], eout); err != nil {
   186  		return missing(fmt.Errorf("decoding output ID: %v", err))
   187  	}
   188  	i := 0
   189  	for i < len(esize) && esize[i] == ' ' {
   190  		i++
   191  	}
   192  	size, err := strconv.ParseInt(string(esize[i:]), 10, 64)
   193  	if err != nil {
   194  		return missing(fmt.Errorf("parsing size: %v", err))
   195  	} else if size < 0 {
   196  		return missing(errors.New("negative size"))
   197  	}
   198  	i = 0
   199  	for i < len(etime) && etime[i] == ' ' {
   200  		i++
   201  	}
   202  	tm, err := strconv.ParseInt(string(etime[i:]), 10, 64)
   203  	if err != nil {
   204  		return missing(fmt.Errorf("parsing timestamp: %v", err))
   205  	} else if tm < 0 {
   206  		return missing(errors.New("negative timestamp"))
   207  	}
   208  
   209  	c.used(c.fileName(id, "a"))
   210  
   211  	return Entry{buf, size, time.Unix(0, tm)}, nil
   212  }
   213  
   214  // GetFile looks up the action ID in the cache and returns
   215  // the name of the corresponding data file.
   216  func (c *Cache) GetFile(id ActionID) (file string, entry Entry, err error) {
   217  	entry, err = c.Get(id)
   218  	if err != nil {
   219  		return "", Entry{}, err
   220  	}
   221  	file = c.OutputFile(entry.OutputID)
   222  	info, err := os.Stat(file)
   223  	if err != nil {
   224  		return "", Entry{}, &entryNotFoundError{Err: err}
   225  	}
   226  	if info.Size() != entry.Size {
   227  		return "", Entry{}, &entryNotFoundError{Err: errors.New("file incomplete")}
   228  	}
   229  	return file, entry, nil
   230  }
   231  
   232  // GetBytes looks up the action ID in the cache and returns
   233  // the corresponding output bytes.
   234  // GetBytes should only be used for data that can be expected to fit in memory.
   235  func (c *Cache) GetBytes(id ActionID) ([]byte, Entry, error) {
   236  	entry, err := c.Get(id)
   237  	if err != nil {
   238  		return nil, entry, err
   239  	}
   240  	data, _ := os.ReadFile(c.OutputFile(entry.OutputID))
   241  	if sha256.Sum256(data) != entry.OutputID {
   242  		return nil, entry, &entryNotFoundError{Err: errors.New("bad checksum")}
   243  	}
   244  	return data, entry, nil
   245  }
   246  
   247  /*
   248  TODO: consider copying cmd/go/internal/mmap over for this method
   249  
   250  // GetMmap looks up the action ID in the cache and returns
   251  // the corresponding output bytes.
   252  // GetMmap should only be used for data that can be expected to fit in memory.
   253  func (c *Cache) GetMmap(id ActionID) ([]byte, Entry, error) {
   254  	entry, err := c.Get(id)
   255  	if err != nil {
   256  		return nil, entry, err
   257  	}
   258  	md, err := mmap.Mmap(c.OutputFile(entry.OutputID))
   259  	if err != nil {
   260  		return nil, Entry{}, err
   261  	}
   262  	if int64(len(md.Data)) != entry.Size {
   263  		return nil, Entry{}, &entryNotFoundError{Err: errors.New("file incomplete")}
   264  	}
   265  	return md.Data, entry, nil
   266  }
   267  */
   268  
   269  // OutputFile returns the name of the cache file storing output with the given OutputID.
   270  func (c *Cache) OutputFile(out OutputID) string {
   271  	file := c.fileName(out, "d")
   272  	c.used(file)
   273  	return file
   274  }
   275  
   276  // Time constants for cache expiration.
   277  //
   278  // We set the mtime on a cache file on each use, but at most one per mtimeInterval (1 hour),
   279  // to avoid causing many unnecessary inode updates. The mtimes therefore
   280  // roughly reflect "time of last use" but may in fact be older by at most an hour.
   281  //
   282  // We scan the cache for entries to delete at most once per trimInterval (1 day).
   283  //
   284  // When we do scan the cache, we delete entries that have not been used for
   285  // at least trimLimit (5 days). Statistics gathered from a month of usage by
   286  // Go developers found that essentially all reuse of cached entries happened
   287  // within 5 days of the previous reuse. See golang.org/issue/22990.
   288  const (
   289  	mtimeInterval = 1 * time.Hour
   290  	trimInterval  = 24 * time.Hour
   291  	trimLimit     = 5 * 24 * time.Hour
   292  )
   293  
   294  // used makes a best-effort attempt to update mtime on file,
   295  // so that mtime reflects cache access time.
   296  //
   297  // Because the reflection only needs to be approximate,
   298  // and to reduce the amount of disk activity caused by using
   299  // cache entries, used only updates the mtime if the current
   300  // mtime is more than an hour old. This heuristic eliminates
   301  // nearly all of the mtime updates that would otherwise happen,
   302  // while still keeping the mtimes useful for cache trimming.
   303  func (c *Cache) used(file string) {
   304  	info, err := os.Stat(file)
   305  	if err == nil && c.now().Sub(info.ModTime()) < mtimeInterval {
   306  		return
   307  	}
   308  	os.Chtimes(file, c.now(), c.now())
   309  }
   310  
   311  // Trim removes old cache entries that are likely not to be reused.
   312  func (c *Cache) Trim() error {
   313  	now := c.now()
   314  
   315  	// We maintain in dir/trim.txt the time of the last completed cache trim.
   316  	// If the cache has been trimmed recently enough, do nothing.
   317  	// This is the common case.
   318  	// If the trim file is corrupt, detected if the file can't be parsed, or the
   319  	// trim time is too far in the future, attempt the trim anyway. It's possible that
   320  	// the cache was full when the corruption happened. Attempting a trim on
   321  	// an empty cache is cheap, so there wouldn't be a big performance hit in that case.
   322  	if data, err := lockedfile.Read(filepath.Join(c.dir, "trim.txt")); err == nil {
   323  		if t, err := strconv.ParseInt(strings.TrimSpace(string(data)), 10, 64); err == nil {
   324  			lastTrim := time.Unix(t, 0)
   325  			if d := now.Sub(lastTrim); d < trimInterval && d > -mtimeInterval {
   326  				return nil
   327  			}
   328  		}
   329  	}
   330  
   331  	// Trim each of the 256 subdirectories.
   332  	// We subtract an additional mtimeInterval
   333  	// to account for the imprecision of our "last used" mtimes.
   334  	cutoff := now.Add(-trimLimit - mtimeInterval)
   335  	for i := 0; i < 256; i++ {
   336  		subdir := filepath.Join(c.dir, fmt.Sprintf("%02x", i))
   337  		c.trimSubdir(subdir, cutoff)
   338  	}
   339  
   340  	// Ignore errors from here: if we don't write the complete timestamp, the
   341  	// cache will appear older than it is, and we'll trim it again next time.
   342  	var b bytes.Buffer
   343  	fmt.Fprintf(&b, "%d", now.Unix())
   344  	if err := lockedfile.Write(filepath.Join(c.dir, "trim.txt"), &b, 0666); err != nil {
   345  		return err
   346  	}
   347  
   348  	return nil
   349  }
   350  
   351  // trimSubdir trims a single cache subdirectory.
   352  func (c *Cache) trimSubdir(subdir string, cutoff time.Time) {
   353  	// Read all directory entries from subdir before removing
   354  	// any files, in case removing files invalidates the file offset
   355  	// in the directory scan. Also, ignore error from f.Readdirnames,
   356  	// because we don't care about reporting the error and we still
   357  	// want to process any entries found before the error.
   358  	f, err := os.Open(subdir)
   359  	if err != nil {
   360  		return
   361  	}
   362  	names, _ := f.Readdirnames(-1)
   363  	f.Close()
   364  
   365  	for _, name := range names {
   366  		// Remove only cache entries (xxxx-a and xxxx-d).
   367  		if !strings.HasSuffix(name, "-a") && !strings.HasSuffix(name, "-d") {
   368  			continue
   369  		}
   370  		entry := filepath.Join(subdir, name)
   371  		info, err := os.Stat(entry)
   372  		if err == nil && info.ModTime().Before(cutoff) {
   373  			os.Remove(entry)
   374  		}
   375  	}
   376  }
   377  
   378  // putIndexEntry adds an entry to the cache recording that executing the action
   379  // with the given id produces an output with the given output id (hash) and size.
   380  func (c *Cache) putIndexEntry(id ActionID, out OutputID, size int64, allowVerify bool) error {
   381  	// Note: We expect that for one reason or another it may happen
   382  	// that repeating an action produces a different output hash
   383  	// (for example, if the output contains a time stamp or temp dir name).
   384  	// While not ideal, this is also not a correctness problem, so we
   385  	// don't make a big deal about it. In particular, we leave the action
   386  	// cache entries writable specifically so that they can be overwritten.
   387  	//
   388  	// Setting GODEBUG=gocacheverify=1 does make a big deal:
   389  	// in verify mode we are double-checking that the cache entries
   390  	// are entirely reproducible. As just noted, this may be unrealistic
   391  	// in some cases but the check is also useful for shaking out real bugs.
   392  	entry := fmt.Sprintf("v1 %x %x %20d %20d\n", id, out, size, time.Now().UnixNano())
   393  	if verify && allowVerify {
   394  		old, err := c.get(id)
   395  		if err == nil && (old.OutputID != out || old.Size != size) {
   396  			// panic to show stack trace, so we can see what code is generating this cache entry.
   397  			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)
   398  			panic(msg)
   399  		}
   400  	}
   401  	file := c.fileName(id, "a")
   402  
   403  	// Copy file to cache directory.
   404  	mode := os.O_WRONLY | os.O_CREATE
   405  	f, err := os.OpenFile(file, mode, 0666)
   406  	if err != nil {
   407  		return err
   408  	}
   409  	_, err = f.WriteString(entry)
   410  	if err == nil {
   411  		// Truncate the file only *after* writing it.
   412  		// (This should be a no-op, but truncate just in case of previous corruption.)
   413  		//
   414  		// This differs from os.WriteFile, which truncates to 0 *before* writing
   415  		// via os.O_TRUNC. Truncating only after writing ensures that a second write
   416  		// of the same content to the same file is idempotent, and does not — even
   417  		// temporarily! — undo the effect of the first write.
   418  		err = f.Truncate(int64(len(entry)))
   419  	}
   420  	if closeErr := f.Close(); err == nil {
   421  		err = closeErr
   422  	}
   423  	if err != nil {
   424  		// TODO(bcmills): This Remove potentially races with another go command writing to file.
   425  		// Can we eliminate it?
   426  		os.Remove(file)
   427  		return err
   428  	}
   429  	os.Chtimes(file, c.now(), c.now()) // mainly for tests
   430  
   431  	return nil
   432  }
   433  
   434  // Put stores the given output in the cache as the output for the action ID.
   435  // It may read file twice. The content of file must not change between the two passes.
   436  func (c *Cache) Put(id ActionID, file io.ReadSeeker) (OutputID, int64, error) {
   437  	return c.put(id, file, true)
   438  }
   439  
   440  // PutNoVerify is like Put but disables the verify check
   441  // when GODEBUG=goverifycache=1 is set.
   442  // It is meant for data that is OK to cache but that we expect to vary slightly from run to run,
   443  // like test output containing times and the like.
   444  func (c *Cache) PutNoVerify(id ActionID, file io.ReadSeeker) (OutputID, int64, error) {
   445  	return c.put(id, file, false)
   446  }
   447  
   448  func (c *Cache) put(id ActionID, file io.ReadSeeker, allowVerify bool) (OutputID, int64, error) {
   449  	// Compute output ID.
   450  	h := sha256.New()
   451  	if _, err := file.Seek(0, 0); err != nil {
   452  		return OutputID{}, 0, err
   453  	}
   454  	size, err := io.Copy(h, file)
   455  	if err != nil {
   456  		return OutputID{}, 0, err
   457  	}
   458  	var out OutputID
   459  	h.Sum(out[:0])
   460  
   461  	// Copy to cached output file (if not already present).
   462  	if err := c.copyFile(file, out, size); err != nil {
   463  		return out, size, err
   464  	}
   465  
   466  	// Add to cache index.
   467  	return out, size, c.putIndexEntry(id, out, size, allowVerify)
   468  }
   469  
   470  // PutBytes stores the given bytes in the cache as the output for the action ID.
   471  func (c *Cache) PutBytes(id ActionID, data []byte) error {
   472  	_, _, err := c.Put(id, bytes.NewReader(data))
   473  	return err
   474  }
   475  
   476  // copyFile copies file into the cache, expecting it to have the given
   477  // output ID and size, if that file is not present already.
   478  func (c *Cache) copyFile(file io.ReadSeeker, out OutputID, size int64) error {
   479  	name := c.fileName(out, "d")
   480  	info, err := os.Stat(name)
   481  	if err == nil && info.Size() == size {
   482  		// Check hash.
   483  		if f, err := os.Open(name); err == nil {
   484  			h := sha256.New()
   485  			io.Copy(h, f)
   486  			f.Close()
   487  			var out2 OutputID
   488  			h.Sum(out2[:0])
   489  			if out == out2 {
   490  				return nil
   491  			}
   492  		}
   493  		// Hash did not match. Fall through and rewrite file.
   494  	}
   495  
   496  	// Copy file to cache directory.
   497  	mode := os.O_RDWR | os.O_CREATE
   498  	if err == nil && info.Size() > size { // shouldn't happen but fix in case
   499  		mode |= os.O_TRUNC
   500  	}
   501  	f, err := os.OpenFile(name, mode, 0666)
   502  	if err != nil {
   503  		return err
   504  	}
   505  	defer f.Close()
   506  	if size == 0 {
   507  		// File now exists with correct size.
   508  		// Only one possible zero-length file, so contents are OK too.
   509  		// Early return here makes sure there's a "last byte" for code below.
   510  		return nil
   511  	}
   512  
   513  	// From here on, if any of the I/O writing the file fails,
   514  	// we make a best-effort attempt to truncate the file f
   515  	// before returning, to avoid leaving bad bytes in the file.
   516  
   517  	// Copy file to f, but also into h to double-check hash.
   518  	if _, err := file.Seek(0, 0); err != nil {
   519  		f.Truncate(0)
   520  		return err
   521  	}
   522  	h := sha256.New()
   523  	w := io.MultiWriter(f, h)
   524  	if _, err := io.CopyN(w, file, size-1); err != nil {
   525  		f.Truncate(0)
   526  		return err
   527  	}
   528  	// Check last byte before writing it; writing it will make the size match
   529  	// what other processes expect to find and might cause them to start
   530  	// using the file.
   531  	buf := make([]byte, 1)
   532  	if _, err := file.Read(buf); err != nil {
   533  		f.Truncate(0)
   534  		return err
   535  	}
   536  	h.Write(buf)
   537  	sum := h.Sum(nil)
   538  	if !bytes.Equal(sum, out[:]) {
   539  		f.Truncate(0)
   540  		return fmt.Errorf("file content changed underfoot")
   541  	}
   542  
   543  	// Commit cache file entry.
   544  	if _, err := f.Write(buf); err != nil {
   545  		f.Truncate(0)
   546  		return err
   547  	}
   548  	if err := f.Close(); err != nil {
   549  		// Data might not have been written,
   550  		// but file may look like it is the right size.
   551  		// To be extra careful, remove cached file.
   552  		os.Remove(name)
   553  		return err
   554  	}
   555  	os.Chtimes(name, c.now(), c.now()) // mainly for tests
   556  
   557  	return nil
   558  }
   559  
   560  // FuzzDir returns a subdirectory within the cache for storing fuzzing data.
   561  // The subdirectory may not exist.
   562  //
   563  // This directory is managed by the internal/fuzz package. Files in this
   564  // directory aren't removed by the 'go clean -cache' command or by Trim.
   565  // They may be removed with 'go clean -fuzzcache'.
   566  //
   567  // TODO(#48526): make Trim remove unused files from this directory.
   568  func (c *Cache) FuzzDir() string {
   569  	return filepath.Join(c.dir, "fuzz")
   570  }
   571
View as plain text