func logMemFSNodeInfo(node *memFSNode) {
	hdr := node.hdr
	log.Infof("%s %s %d %d %d", hdr.Name, hdr.FileInfo().Mode(), hdr.Uid, hdr.Gid, hdr.Size)
	for _, nxtNode := range node.children {
		logMemFSNodeInfo(nxtNode)
	}
}
logMemFSNodeInfo logs the info of a memFSNode.
package snapshot
import (
	"archive/tar"
	"fmt"
	"io"
	"os"
	"path/filepath"
	"strings"
	"syscall"
	"time"
	"github.com/andres-erbsen/clock"
	"github.com/uber/makisu/lib/docker/image"
	"github.com/uber/makisu/lib/fileio"
	"github.com/uber/makisu/lib/log"
	"github.com/uber/makisu/lib/mountutils"
	"github.com/uber/makisu/lib/pathutils"
	"github.com/uber/makisu/lib/tario"
	"github.com/uber/makisu/lib/utils"
)
type memFSNode struct {
	*contentMemFile                        
	children        map[string]*memFSNode  
}
func newMemFSNode(mf *contentMemFile) *memFSNode {
	return &memFSNode{mf, make(map[string]*memFSNode)}
}
func (n *memFSNode) isOnDisk() (bool, error) {
	if _, err := os.Lstat(n.src); err == nil {
		return true, nil
	} else if os.IsNotExist(err) {
		return false, nil
	} else {
		return false, err
	}
}
type MemFS struct {
	clk  clock.Clock
	tree *memFSNode
	blacklist []string
	layers    []*memLayer
}
func NewMemFS(clk clock.Clock, root string, blacklist []string) (*MemFS, error) {
	fi, err := os.Lstat(root)
	if err != nil {
		return nil, fmt.Errorf("unable to stat root dir: %s", root)
	}
	hdr, err := newMemLayer().createHeader(root, root, "/", fi)
	if err != nil {
		return nil, fmt.Errorf("unable to create root header")
	}
	return &MemFS{
		clk:       clk,
		tree:      newMemFSNode(newContentMemFile(root, "/", hdr)),
		blacklist: blacklist,
	}, nil
}
func (fs *MemFS) Reset() {
	fs.tree.children = make(map[string]*memFSNode)
}
func (fs *MemFS) Checkpoint(newRoot string, sources []string) error {
	if len(sources) == 0 {
		return nil
	}
	resolvedSources := []string{}
	for _, src := range sources {
		if matches, err := filepath.Glob(src); err != nil || len(matches) == 0 {
			resolvedSources = append(resolvedSources, src)
		} else {
			resolvedSources = append(resolvedSources, matches...)
		}
	}
	log.Infof("* Moving directories %v to %s", sources, newRoot)
	for _, src := range resolvedSources {
		if !filepath.IsAbs(src) {
			src = filepath.Join(fs.tree.src, src)
		}
		trimmedSrc, err := pathutils.TrimRoot(src, fs.tree.src)
		if err != nil {
			return fmt.Errorf("trim src %s: %s", src, err)
		}
		dst := filepath.Join(newRoot, trimmedSrc)
		sourceInfo, err := os.Stat(src)
		if err != nil {
			return fmt.Errorf("stat %s: %s", src, err)
		}
		fi, err := os.Lstat(src)
		if err != nil {
			return fmt.Errorf("lstat %s: %s", src, err)
		}
		stat := utils.FileInfoStat(fi)
		copier := fileio.NewCopier(fs.blacklist,
			fileio.WithDstDirOwner(int(stat.Uid), int(stat.Gid), false))
		if sourceInfo.IsDir() {
			if err := copier.CopyDir(src, dst); err != nil {
				return fmt.Errorf("copy dir %s: %s", src, err)
			}
		} else {
			if err := copier.CopyFile(src, dst); err != nil {
				return fmt.Errorf("copy file %s: %s", src, err)
			}
		}
	}
	return nil
}
func (fs *MemFS) Remove() error {
	return removeAllChildren(fs.tree.src, fs.blacklist)
}
func (fs *MemFS) UpdateFromTarPath(source string, untar bool) error {
	reader, err := os.Open(source)
	if err != nil {
		return fmt.Errorf("open tar file: %s", err)
	}
	defer reader.Close()
	gzipReader, err := tario.NewGzipReader(reader)
	if err != nil {
		return fmt.Errorf("new gzip reader: %s", err)
	}
	return fs.UpdateFromTarReader(tar.NewReader(gzipReader), untar)
}
func (fs *MemFS) UpdateFromTarReader(r *tar.Reader, untar bool) error {
	start := time.Now()
	hardlinks := make(map[string]*tar.Header)
	modtimes := make(map[string]time.Time)
	var count int
	l := newMemLayer()
	for {
		hdr, err := r.Next()
		if err == io.EOF {
			duration := time.Since(start).Round(time.Millisecond)
			if untar {
				log.Infow(fmt.Sprintf("* Untarred %d files to %s", count, fs.tree.src), "duration", duration)
			}
			break
		} else if err != nil {
			return fmt.Errorf("read header: %s", err)
		}
		path := filepath.Join(fs.tree.src, hdr.Name)
		if skip, err := shouldSkip(path, hdr.FileInfo(), fs.blacklist); err != nil {
			return fmt.Errorf("check if should skip %s: %s", path, err)
		} else if skip {
			continue
		} else if isMounted, err := mountutils.IsMounted(path); err != nil {
			return fmt.Errorf("check if mounted %s: %s", path, err)
		} else if isMounted {
			continue
		}
		if untar {
			parentDir := filepath.Dir(path)
			if _, found := modtimes[parentDir]; !found {
				parentFi, err := os.Lstat(parentDir)
				if err != nil {
					return fmt.Errorf("stat parent dir of %s: %s", path, err)
				}
				modtimes[parentDir] = parentFi.ModTime()
			}
		}
		hdr.Name = pathutils.RelPath(hdr.Name)
		if hdr.Typeflag == tar.TypeLink {
			hdr.Linkname = pathutils.AbsPath(hdr.Linkname)
			hardlinks[path] = hdr
		} else {
			if untar {
				if err := fs.untarOneItem(path, hdr, r); err != nil {
					return fmt.Errorf("untar one item %s: %s", path, err)
				}
			}
			if err := fs.maybeAddToLayer(l, pathutils.AbsPath(hdr.Name), pathutils.AbsPath(hdr.Name), hdr, false); err != nil {
				return fmt.Errorf("add hdr from tar to layer: %s", err)
			}
		}
		count++
	}
	for path, hdr := range hardlinks {
		if untar {
			if err := fs.untarOneItem(path, hdr, nil); err != nil {
				return fmt.Errorf("untar one item %s: %s", path, err)
			}
		}
		if err := fs.maybeAddToLayer(l, pathutils.AbsPath(hdr.Name), pathutils.AbsPath(hdr.Name), hdr, false); err != nil {
			return fmt.Errorf("add hdr from tar to layer: %s", err)
		}
	}
	for path, modtime := range modtimes {
		if err := os.Chtimes(path, modtime, modtime); err != nil {
			return fmt.Errorf("chtimes on parent directory %s: %s", path, err)
		}
	}
	fs.layers = append(fs.layers, l)
	log.Infof("* Merged %d headers from tar to memfs", l.count())
	return nil
}
func (fs *MemFS) AddLayerByScan(w *tar.Writer) error {
	fs.sync()
	if l, err := fs.createLayerByScan(); err != nil {
		return fmt.Errorf("create layer by scan: %s", err)
	} else if err := fs.commitLayer(l, w); err != nil {
		return fmt.Errorf("commit layer by scan: %s", err)
	} else {
		log.Infof("* Created layer by scanning filesystem; %d files found", l.count())
	}
	return nil
}
func (fs *MemFS) AddLayerByCopyOps(cs []*CopyOperation, w *tar.Writer) error {
	fs.sync()
	l := newMemLayer()
	for _, c := range cs {
		if err := fs.addToLayer(l, c); err != nil {
			return fmt.Errorf("create layer by copy ops: %s", err)
		}
	}
	if err := fs.commitLayer(l, w); err != nil {
		return fmt.Errorf("commit layer by copy ops: %s", err)
	}
	log.Infof("* Created copy layer with %d files", l.count())
	return nil
}
func (fs *MemFS) sync() {
	start := time.Now()
	block := make(chan interface{}, 1)
	go func() {
		<-time.After(1 * time.Second)
		close(block)
	}()
	syscall.Sync()
	<-block
	duration := time.Since(start).Round(time.Millisecond)
	log.Infow("* Synchronized file system", "duration", duration)
}
func (fs *MemFS) createLayerByScan() (*memLayer, error) {
	start := time.Now()
	log.Info("* Collecting filesystem diff")
	l := newMemLayer()
	root := fs.tree.src
	if err := walk(
		root, fs.blacklist, func(src string, fi os.FileInfo) error {
			dst, err := pathutils.TrimRoot(src, root)
			if err != nil {
				return err
			}
			hdr, err := l.createHeader(fs.tree.src, src, dst, fi)
			if err != nil {
				return fmt.Errorf("create header %s: %s", dst, err)
			}
			if err := fs.maybeAddToLayer(l, src, dst, hdr, true); err != nil {
				return fmt.Errorf("add to layer: %s", err)
			}
			return nil
		}); err != nil {
		return nil, fmt.Errorf("walk %s: %s", root, err)
	}
	log.Infow(fmt.Sprintf("* Collected diff: %d files found", l.count()), "duration", time.Since(start).Round(time.Millisecond))
	return l, nil
}
func (fs *MemFS) addToLayer(l *memLayer, c *CopyOperation) error {
	var err error
	createDst := true
	if len(c.srcs) == 1 {
		src := filepath.Join(c.srcRoot, c.srcs[0])
		if fi, err := os.Stat(src); err != nil {
			return fmt.Errorf("stat src %s: %s", src, err)
		} else if !fi.IsDir() {
			createDst = false
		}
	}
	if createDst {
		resolved, err := fs.addAncestors(l, pathutils.AbsPath(c.dst), true, 0, c.uid, c.gid)
		if err != nil {
			return fmt.Errorf("add ancestors of %s: %s", c.dst, err)
		}
		if !strings.HasSuffix(resolved, "/") {
			resolved += "/"
		}
		c.dst = resolved
	}
	for _, src := range c.srcs {
		src, err = evalSymlinks(src, c.srcRoot)
		if err != nil {
			return fmt.Errorf("eval symlinks for %s: %s", src, err)
		}
		src = filepath.Join(c.srcRoot, src)
		if err := walk(src, nil, func(currSrc string, fi os.FileInfo) error {
			var currDst string
			if currSrc == src {
				if fi.IsDir() {
					return nil
				} else if !strings.HasSuffix(c.dst, "/") {
					currDst = c.dst
				} else {
					currDst = filepath.Join(c.dst, filepath.Base(src))
				}
			} else {
				currDst = filepath.Join(c.dst, currSrc[len(src):])
			}
			hdr, err := l.createHeader(fs.tree.src, currSrc, currDst, fi)
			if err != nil {
				return fmt.Errorf("create header %s: %s", currDst, err)
			}
			hdr.Uid = c.uid
			hdr.Gid = c.gid
			return fs.maybeAddToLayer(l, currSrc, currDst, hdr, false)
		}); err != nil {
			return fmt.Errorf("copy src %s to dst %s: %s", src, c.dst, err)
		}
	}
	return nil
}
func (fs *MemFS) commitLayer(l *memLayer, w *tar.Writer) error {
	if err := l.rangeFiles(func(f memFile) error {
		return f.commit(w)
	}); err != nil {
		return fmt.Errorf("commit layer: %s", err)
	}
	fs.layers = append(fs.layers, l)
	return nil
}
func (fs *MemFS) maybeAddToLayer(
	l *memLayer, src, dst string, hdr *tar.Header, createWhiteout bool) error {
	updated, n, err := fs.isUpdated(dst, hdr)
	if err != nil {
		return fmt.Errorf("check header %s: %s", dst, err)
	} else if updated {
		if dst != "/" {  
			if _, err := fs.addAncestors(l, pathutils.AbsPath(dst), false, 0, 0, 0); err != nil {
				return fmt.Errorf("add ancestors of %s: %s", dst, err)
			}
			if err := l.addHeader(src, dst, hdr).updateMemFS(fs.tree); err != nil {
				return fmt.Errorf("update memfs with file %s: %s", dst, err)
			}
		}
	}
	if createWhiteout {
		if hdr.Typeflag == tar.TypeDir && n != nil {
			for _, child := range n.children {
				if ok, err := child.isOnDisk(); err != nil {
					return fmt.Errorf("check on disk %s: %s", child.dst, err)
				} else if !ok {
					if mf, err := l.addWhiteout(child.dst); err != nil {
						return fmt.Errorf(
							"add whiteout to layer %s: %s", child.dst, err)
					} else if err := mf.updateMemFS(fs.tree); err != nil {
						return fmt.Errorf(
							"update memfs with whiteout %s: %s", child.dst, err)
					} else if _, err := fs.addAncestors(l, child.dst, false, 0, 0, 0); err != nil {
						return fmt.Errorf("add ancestors of %s: %s", child.dst, err)
					}
				}
			}
		}
	}
	return nil
}
func (fs *MemFS) isUpdated(p string, hdr *tar.Header) (bool, *memFSNode, error) {
	curr := fs.tree
	parts := pathutils.SplitPath(p)
	for _, part := range parts {
		if n, ok := curr.children[part]; ok {
			curr = n
		} else {
			return true, nil, nil
		}
	}
	similar, err := tario.IsSimilarHeader(curr.hdr, hdr, false)
	if err != nil {
		return false, nil, fmt.Errorf("compare header %s: %s", p, err)
	}
	return !similar, curr, nil
}
func (fs *MemFS) addAncestors(l *memLayer, dst string, inclusive bool, depth, uid, gid int) (string, error) {
	if depth >= 1024 {
		return "", fmt.Errorf("symlink loop at %s", dst)
	}
	lastAncestor := fs.tree
	var i int
	var part string
	curr := fs.tree
	parts := pathutils.SplitPath(dst)
	end := len(parts) - 1
	if inclusive {
		end = len(parts)
	}
	for ; i < end; i++ {
		part = parts[i]
		if n, ok := curr.children[part]; ok {
			if err := l.addHeader(n.src, n.dst, n.hdr).updateMemFS(fs.tree); err != nil {
				return "", fmt.Errorf("update memfs with ancestor %s: %s", n.dst, err)
			}
			switch n.hdr.Typeflag {
			case tar.TypeDir:
				lastAncestor = n
				curr = n
			case tar.TypeSymlink:
				remaining := filepath.Join(parts[i+1:]...)
				target := filepath.Join(n.hdr.Linkname, remaining)
				resolved, err := fs.addAncestors(l, target, inclusive, depth+1, uid, gid)
				if err != nil {
					return "", fmt.Errorf(
						"get symlink target ancestors %s: %s", target, err)
				}
				return resolved, nil
			}
		} else {
			break
		}
	}
	for j := i; j < end; j++ {
		curr := pathutils.AbsPath(filepath.Join(parts[:j+1]...))
		hdr, err := l.createHeader(fs.tree.src, "", curr, lastAncestor.hdr.FileInfo())
		if err != nil {
			return "", fmt.Errorf("create header %s: %s", curr, err)
		}
		hdr.ModTime = fs.clk.Now()
		hdr.Uid = uid
		hdr.Gid = gid
		if err := l.addHeader("", curr, hdr).updateMemFS(fs.tree); err != nil {
			return "", fmt.Errorf("update memfs with ancestor %s: %s", curr, err)
		}
	}
	return dst, nil
}
func (fs *MemFS) untarOneItem(path string, header *tar.Header, r *tar.Reader) error {
	if strings.HasPrefix(filepath.Base(path), _whiteoutPrefix) {
		if err := fs.untarWhiteout(path); err != nil {
			return fmt.Errorf("untar dir: %s", err)
		}
		return nil
	}
	headerInfo := header.FileInfo()
	localInfo, err := os.Lstat(path)
	if err != nil && !os.IsNotExist(err) {
		return fmt.Errorf("lstat %s: %s", path, err)
	} else if err == nil {
		var linkTarget string
		if localInfo.Mode()&os.ModeSymlink != 0 {
			linkTarget, err = os.Readlink(path)
			if err != nil {
				return fmt.Errorf("read link %s: %s", linkTarget, err)
			}
			if filepath.IsAbs(linkTarget) {
				linkTarget, err = pathutils.TrimRoot(linkTarget, fs.tree.src)
				if err != nil {
					return fmt.Errorf("trim link %s: %s", linkTarget, err)
				}
			}
		}
		localHeader, err := tar.FileInfoHeader(localInfo, linkTarget)
		if err != nil {
			return fmt.Errorf("create header %s: %s", path, err)
		}
		if similar, err := tario.IsSimilarHeader(localHeader, header, false); err != nil {
			return fmt.Errorf("compare headers %s: %s", path, err)
		} else if similar {
			return nil
		}
		if headerInfo.IsDir() && localInfo.IsDir() {
			if err := tario.ApplyHeader(path, header); err != nil {
				return fmt.Errorf("update fi %s: %s", path, err)
			}
			return nil
		}
		if err := os.RemoveAll(path); err != nil {
			return fmt.Errorf("clear existing file %s: %s", path, err)
		}
	}
	switch header.Typeflag {
	case tar.TypeDir:
		if err := fs.untarDirectory(path, header); err != nil {
			return fmt.Errorf("untar dir: %s", err)
		}
	case tar.TypeSymlink:
		if err := fs.untarSymlink(path, header); err != nil {
			return fmt.Errorf("untar symlink: %s", err)
		}
	case tar.TypeLink:
		if err := fs.untarHardlink(path, header); err != nil {
			return fmt.Errorf("untar hard link: %s", err)
		}
	default:
		if err := fs.untarFile(path, header, r); err != nil {
			return fmt.Errorf("untar file: %s", err)
		}
	}
	return nil
}
func (fs *MemFS) untarWhiteout(path string) error {
	oldBase := strings.TrimPrefix(filepath.Base(path), _whiteoutPrefix)
	err := os.RemoveAll(filepath.Join(filepath.Dir(path), oldBase))
	if err != nil && !os.IsNotExist(err) {
		return fmt.Errorf("untar whiteout: %s", err)
	}
	return nil
}
func (fs *MemFS) untarDirectory(path string, header *tar.Header) error {
	if err := os.Mkdir(path, header.FileInfo().Mode()); err != nil {
		return fmt.Errorf("create dir %s: %s", path, err)
	}
	if err := tario.ApplyHeader(path, header); err != nil {
		return fmt.Errorf("update fi %s: %s", path, err)
	}
	return nil
}
func (fs *MemFS) untarSymlink(path string, header *tar.Header) error {
	target := header.Linkname
	if filepath.IsAbs(header.Linkname) {
		target = filepath.Join(fs.tree.src, target)
	}
	if err := os.Symlink(target, path); err != nil {
		return fmt.Errorf("create symlink %s => %s: %s", path, target, err)
	}
	if err := os.Lchown(path, header.Uid, header.Gid); err != nil {
		return fmt.Errorf("lchown symlink: %s", path)
	}
	return nil
}
func (fs *MemFS) untarHardlink(path string, header *tar.Header) error {
	target := filepath.Join(fs.tree.src, header.Linkname)
	if err := os.Link(target, path); err != nil {
		return fmt.Errorf(
			"create link %s => %s: %s", path, target, err)
	}
	if err := tario.ApplyHeader(path, header); err != nil {
		return fmt.Errorf("update hard link %s: %s", path, err)
	}
	return nil
}
func (fs *MemFS) untarFile(path string, header *tar.Header, r *tar.Reader) error {
	fi := header.FileInfo()
	file, err := os.OpenFile(path, os.O_CREATE|os.O_TRUNC|os.O_WRONLY, fi.Mode())
	if err != nil {
		return fmt.Errorf("open file %s: %s", path, err)
	}
	defer file.Close()
	if _, err := io.Copy(file, r); err != nil {
		return fmt.Errorf("read from file %s: %s", path, err)
	}
	if err := tario.ApplyHeader(path, header); err != nil {
		return fmt.Errorf("update fi %s: %s", path, err)
	}
	return nil
}
func CompareFS(fs1, fs2 *MemFS, image1Name, image2Name image.Name, ignoreModTime bool) {
	missing1 := make(map[string]*memFSNode)
	missing2 := make(map[string]*memFSNode)
	diff1 := make(map[string]*memFSNode)
	diff2 := make(map[string]*memFSNode)
	compareNode(fs1.tree, fs2.tree, missing1, missing2, diff1, diff2, "/", ignoreModTime)
	image1Format := image1Name.GetRepository() + ":" + image1Name.GetTag()
	image2Format := image2Name.GetRepository() + ":" + image2Name.GetTag()
	log.Infof("===== file missing in first image %s =====", image1Format)
	for _, node := range missing1 {
		logMemFSNodeInfo(node)
	}
	log.Infof("===== file missing in second image %s =====", image2Format)
	for _, node := range missing2 {
		logMemFSNodeInfo(node)
	}
	log.Infof("===== difference between two images %s and %s =====", image1Format, image2Format)
	for path := range diff1 {
		hdr1, hdr2 := diff1[path].hdr, diff2[path].hdr
		log.Infof("%s %s %d %d %d", path, hdr1.FileInfo().Mode(), hdr1.Uid, hdr1.Gid, hdr1.Size)
		log.Infof("%s %s %d %d %d", path, hdr2.FileInfo().Mode(), hdr2.Uid, hdr2.Gid, hdr2.Size)
		log.Infof("xxxxxxxxxxxxxxxxxxxxxxxxxxx")
	}
}
func compareNode(node1, node2 *memFSNode, missing1, missing2, diff1, diff2 map[string]*memFSNode, path string, ignoreModTime bool) {
	if isSimilar, _ := tario.IsSimilarHeader(node1.hdr, node2.hdr, ignoreModTime); !isSimilar {
		diff1[path] = node1
		diff2[path] = node2
	}
	allChildren := make(map[string]bool)
	for child := range node1.children {
		allChildren[child] = true
	}
	for child := range node2.children {
		allChildren[child] = true
	}
	for child := range allChildren {
		nextNode1, ok1 := node1.children[child]
		nextNode2, ok2 := node2.children[child]
		updatedPath := filepath.Join(path, child)
		if ok1 && ok2 {
			compareNode(nextNode1, nextNode2, missing1, missing2, diff1, diff2, updatedPath, ignoreModTime)
			continue
		} else if ok1 {
			missing2[updatedPath] = node1.children[child]
		} else if ok2 {
			missing1[updatedPath] = node2.children[child]
		}
	}
}