vendor/github.com/fsouza/go-dockerclient/external/github.com/docker/docker/pkg/archive/changes_linux.go

   1 package archive
   2
   3 import (
   4         "bytes"
   5         "fmt"
   6         "os"
   7         "path/filepath"
   8         "sort"
   9         "syscall"
  10         "unsafe"
  11
  12         "github.com/fsouza/go-dockerclient/external/github.com/docker/docker/pkg/system"
  13 )
  14
  15 // walker is used to implement collectFileInfoForChanges on linux. Where this
  16 // method in general returns the entire contents of two directory trees, we
  17 // optimize some FS calls out on linux. In particular, we take advantage of the
  18 // fact that getdents(2) returns the inode of each file in the directory being
  19 // walked, which, when walking two trees in parallel to generate a list of
  20 // changes, can be used to prune subtrees without ever having to lstat(2) them
  21 // directly. Eliminating stat calls in this way can save up to seconds on large
  22 // images.
  23 type walker struct {
  24         dir1  string
  25         dir2  string
  26         root1 *FileInfo
  27         root2 *FileInfo
  28 }
  29
  30 // collectFileInfoForChanges returns a complete representation of the trees
  31 // rooted at dir1 and dir2, with one important exception: any subtree or
  32 // leaf where the inode and device numbers are an exact match between dir1
  33 // and dir2 will be pruned from the results. This method is *only* to be used
  34 // to generating a list of changes between the two directories, as it does not
  35 // reflect the full contents.
  36 func collectFileInfoForChanges(dir1, dir2 string) (*FileInfo, *FileInfo, error) {
  37         w := &walker{
  38                 dir1:  dir1,
  39                 dir2:  dir2,
  40                 root1: newRootFileInfo(),
  41                 root2: newRootFileInfo(),
  42         }
  43
  44         i1, err := os.Lstat(w.dir1)
  45         if err != nil {
  46                 return nil, nil, err
  47         }
  48         i2, err := os.Lstat(w.dir2)
  49         if err != nil {
  50                 return nil, nil, err
  51         }
  52
  53         if err := w.walk("/", i1, i2); err != nil {
  54                 return nil, nil, err
  55         }
  56
  57         return w.root1, w.root2, nil
  58 }
  59
  60 // Given a FileInfo, its path info, and a reference to the root of the tree
  61 // being constructed, register this file with the tree.
  62 func walkchunk(path string, fi os.FileInfo, dir string, root *FileInfo) error {
  63         if fi == nil {
  64                 return nil
  65         }
  66         parent := root.LookUp(filepath.Dir(path))
  67         if parent == nil {
  68                 return fmt.Errorf("collectFileInfoForChanges: Unexpectedly no parent for %s", path)
  69         }
  70         info := &FileInfo{
  71                 name:     filepath.Base(path),
  72                 children: make(map[string]*FileInfo),
  73                 parent:   parent,
  74         }
  75         cpath := filepath.Join(dir, path)
  76         stat, err := system.FromStatT(fi.Sys().(*syscall.Stat_t))
  77         if err != nil {
  78                 return err
  79         }
  80         info.stat = stat
  81         info.capability, _ = system.Lgetxattr(cpath, "security.capability") // lgetxattr(2): fs access
  82         parent.children[info.name] = info
  83         return nil
  84 }
  85
  86 // Walk a subtree rooted at the same path in both trees being iterated. For
  87 // example, /docker/overlay/1234/a/b/c/d and /docker/overlay/8888/a/b/c/d
  88 func (w *walker) walk(path string, i1, i2 os.FileInfo) (err error) {
  89         // Register these nodes with the return trees, unless we're still at the
  90         // (already-created) roots:
  91         if path != "/" {
  92                 if err := walkchunk(path, i1, w.dir1, w.root1); err != nil {
  93                         return err
  94                 }
  95                 if err := walkchunk(path, i2, w.dir2, w.root2); err != nil {
  96                         return err
  97                 }
  98         }
  99
 100         is1Dir := i1 != nil && i1.IsDir()
 101         is2Dir := i2 != nil && i2.IsDir()
 102
 103         sameDevice := false
 104         if i1 != nil && i2 != nil {
 105                 si1 := i1.Sys().(*syscall.Stat_t)
 106                 si2 := i2.Sys().(*syscall.Stat_t)
 107                 if si1.Dev == si2.Dev {
 108                         sameDevice = true
 109                 }
 110         }
 111
 112         // If these files are both non-existent, or leaves (non-dirs), we are done.
 113         if !is1Dir && !is2Dir {
 114                 return nil
 115         }
 116
 117         // Fetch the names of all the files contained in both directories being walked:
 118         var names1, names2 []nameIno
 119         if is1Dir {
 120                 names1, err = readdirnames(filepath.Join(w.dir1, path)) // getdents(2): fs access
 121                 if err != nil {
 122                         return err
 123                 }
 124         }
 125         if is2Dir {
 126                 names2, err = readdirnames(filepath.Join(w.dir2, path)) // getdents(2): fs access
 127                 if err != nil {
 128                         return err
 129                 }
 130         }
 131
 132         // We have lists of the files contained in both parallel directories, sorted
 133         // in the same order. Walk them in parallel, generating a unique merged list
 134         // of all items present in either or both directories.
 135         var names []string
 136         ix1 := 0
 137         ix2 := 0
 138
 139         for {
 140                 if ix1 >= len(names1) {
 141                         break
 142                 }
 143                 if ix2 >= len(names2) {
 144                         break
 145                 }
 146
 147                 ni1 := names1[ix1]
 148                 ni2 := names2[ix2]
 149
 150                 switch bytes.Compare([]byte(ni1.name), []byte(ni2.name)) {
 151                 case -1: // ni1 < ni2 -- advance ni1
 152                         // we will not encounter ni1 in names2
 153                         names = append(names, ni1.name)
 154                         ix1++
 155                 case 0: // ni1 == ni2
 156                         if ni1.ino != ni2.ino || !sameDevice {
 157                                 names = append(names, ni1.name)
 158                         }
 159                         ix1++
 160                         ix2++
 161                 case 1: // ni1 > ni2 -- advance ni2
 162                         // we will not encounter ni2 in names1
 163                         names = append(names, ni2.name)
 164                         ix2++
 165                 }
 166         }
 167         for ix1 < len(names1) {
 168                 names = append(names, names1[ix1].name)
 169                 ix1++
 170         }
 171         for ix2 < len(names2) {
 172                 names = append(names, names2[ix2].name)
 173                 ix2++
 174         }
 175
 176         // For each of the names present in either or both of the directories being
 177         // iterated, stat the name under each root, and recurse the pair of them:
 178         for _, name := range names {
 179                 fname := filepath.Join(path, name)
 180                 var cInfo1, cInfo2 os.FileInfo
 181                 if is1Dir {
 182                         cInfo1, err = os.Lstat(filepath.Join(w.dir1, fname)) // lstat(2): fs access
 183                         if err != nil && !os.IsNotExist(err) {
 184                                 return err
 185                         }
 186                 }
 187                 if is2Dir {
 188                         cInfo2, err = os.Lstat(filepath.Join(w.dir2, fname)) // lstat(2): fs access
 189                         if err != nil && !os.IsNotExist(err) {
 190                                 return err
 191                         }
 192                 }
 193                 if err = w.walk(fname, cInfo1, cInfo2); err != nil {
 194                         return err
 195                 }
 196         }
 197         return nil
 198 }
 199
 200 // {name,inode} pairs used to support the early-pruning logic of the walker type
 201 type nameIno struct {
 202         name string
 203         ino  uint64
 204 }
 205
 206 type nameInoSlice []nameIno
 207
 208 func (s nameInoSlice) Len() int           { return len(s) }
 209 func (s nameInoSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
 210 func (s nameInoSlice) Less(i, j int) bool { return s[i].name < s[j].name }
 211
 212 // readdirnames is a hacked-apart version of the Go stdlib code, exposing inode
 213 // numbers further up the stack when reading directory contents. Unlike
 214 // os.Readdirnames, which returns a list of filenames, this function returns a
 215 // list of {filename,inode} pairs.
 216 func readdirnames(dirname string) (names []nameIno, err error) {
 217         var (
 218                 size = 100
 219                 buf  = make([]byte, 4096)
 220                 nbuf int
 221                 bufp int
 222                 nb   int
 223         )
 224
 225         f, err := os.Open(dirname)
 226         if err != nil {
 227                 return nil, err
 228         }
 229         defer f.Close()
 230
 231         names = make([]nameIno, 0, size) // Empty with room to grow.
 232         for {
 233                 // Refill the buffer if necessary
 234                 if bufp >= nbuf {
 235                         bufp = 0
 236                         nbuf, err = syscall.ReadDirent(int(f.Fd()), buf) // getdents on linux
 237                         if nbuf < 0 {
 238                                 nbuf = 0
 239                         }
 240                         if err != nil {
 241                                 return nil, os.NewSyscallError("readdirent", err)
 242                         }
 243                         if nbuf <= 0 {
 244                                 break // EOF
 245                         }
 246                 }
 247
 248                 // Drain the buffer
 249                 nb, names = parseDirent(buf[bufp:nbuf], names)
 250                 bufp += nb
 251         }
 252
 253         sl := nameInoSlice(names)
 254         sort.Sort(sl)
 255         return sl, nil
 256 }
 257
 258 // parseDirent is a minor modification of syscall.ParseDirent (linux version)
 259 // which returns {name,inode} pairs instead of just names.
 260 func parseDirent(buf []byte, names []nameIno) (consumed int, newnames []nameIno) {
 261         origlen := len(buf)
 262         for len(buf) > 0 {
 263                 dirent := (*syscall.Dirent)(unsafe.Pointer(&buf[0]))
 264                 buf = buf[dirent.Reclen:]
 265                 if dirent.Ino == 0 { // File absent in directory.
 266                         continue
 267                 }
 268                 bytes := (*[10000]byte)(unsafe.Pointer(&dirent.Name[0]))
 269                 var name = string(bytes[0:clen(bytes[:])])
 270                 if name == "." || name == ".." { // Useless names
 271                         continue
 272                 }
 273                 names = append(names, nameIno{name, dirent.Ino})
 274         }
 275         return origlen - len(buf), names
 276 }
 277
 278 func clen(n []byte) int {
 279         for i := 0; i < len(n); i++ {
 280                 if n[i] == 0 {
 281                         return i
 282                 }
 283         }
 284         return len(n)
 285 }