1/* 2 Copyright The containerd Authors. 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15*/ 16 17package fs 18 19import ( 20 "bytes" 21 "context" 22 "io" 23 "os" 24 "path/filepath" 25 26 "github.com/pkg/errors" 27) 28 29var ( 30 errTooManyLinks = errors.New("too many links") 31) 32 33type currentPath struct { 34 path string 35 f os.FileInfo 36 fullPath string 37} 38 39func pathChange(lower, upper *currentPath) (ChangeKind, string) { 40 if lower == nil { 41 if upper == nil { 42 panic("cannot compare nil paths") 43 } 44 return ChangeKindAdd, upper.path 45 } 46 if upper == nil { 47 return ChangeKindDelete, lower.path 48 } 49 50 switch i := directoryCompare(lower.path, upper.path); { 51 case i < 0: 52 // File in lower that is not in upper 53 return ChangeKindDelete, lower.path 54 case i > 0: 55 // File in upper that is not in lower 56 return ChangeKindAdd, upper.path 57 default: 58 return ChangeKindModify, upper.path 59 } 60} 61 62func directoryCompare(a, b string) int { 63 l := len(a) 64 if len(b) < l { 65 l = len(b) 66 } 67 for i := 0; i < l; i++ { 68 c1, c2 := a[i], b[i] 69 if c1 == filepath.Separator { 70 c1 = byte(0) 71 } 72 if c2 == filepath.Separator { 73 c2 = byte(0) 74 } 75 if c1 < c2 { 76 return -1 77 } 78 if c1 > c2 { 79 return +1 80 } 81 } 82 if len(a) < len(b) { 83 return -1 84 } 85 if len(a) > len(b) { 86 return +1 87 } 88 return 0 89} 90 91func sameFile(f1, f2 *currentPath) (bool, error) { 92 if os.SameFile(f1.f, f2.f) { 93 return true, nil 94 } 95 96 equalStat, err := compareSysStat(f1.f.Sys(), f2.f.Sys()) 97 if err != nil || !equalStat { 98 return equalStat, err 99 } 100 101 if eq, err := compareCapabilities(f1.fullPath, f2.fullPath); err != nil || !eq { 102 return eq, err 103 } 104 105 // If not a directory also check size, modtime, and content 106 if !f1.f.IsDir() { 107 if f1.f.Size() != f2.f.Size() { 108 return false, nil 109 } 110 t1 := f1.f.ModTime() 111 t2 := f2.f.ModTime() 112 113 if t1.Unix() != t2.Unix() { 114 return false, nil 115 } 116 117 // If the timestamp may have been truncated in both of the 118 // files, check content of file to determine difference 119 if t1.Nanosecond() == 0 && t2.Nanosecond() == 0 { 120 var eq bool 121 if (f1.f.Mode() & os.ModeSymlink) == os.ModeSymlink { 122 eq, err = compareSymlinkTarget(f1.fullPath, f2.fullPath) 123 } else if f1.f.Size() > 0 { 124 eq, err = compareFileContent(f1.fullPath, f2.fullPath) 125 } 126 if err != nil || !eq { 127 return eq, err 128 } 129 } else if t1.Nanosecond() != t2.Nanosecond() { 130 return false, nil 131 } 132 } 133 134 return true, nil 135} 136 137func compareSymlinkTarget(p1, p2 string) (bool, error) { 138 t1, err := os.Readlink(p1) 139 if err != nil { 140 return false, err 141 } 142 t2, err := os.Readlink(p2) 143 if err != nil { 144 return false, err 145 } 146 return t1 == t2, nil 147} 148 149const compareChuckSize = 32 * 1024 150 151// compareFileContent compares the content of 2 same sized files 152// by comparing each byte. 153func compareFileContent(p1, p2 string) (bool, error) { 154 f1, err := os.Open(p1) 155 if err != nil { 156 return false, err 157 } 158 defer f1.Close() 159 f2, err := os.Open(p2) 160 if err != nil { 161 return false, err 162 } 163 defer f2.Close() 164 165 b1 := make([]byte, compareChuckSize) 166 b2 := make([]byte, compareChuckSize) 167 for { 168 n1, err1 := f1.Read(b1) 169 if err1 != nil && err1 != io.EOF { 170 return false, err1 171 } 172 n2, err2 := f2.Read(b2) 173 if err2 != nil && err2 != io.EOF { 174 return false, err2 175 } 176 if n1 != n2 || !bytes.Equal(b1[:n1], b2[:n2]) { 177 return false, nil 178 } 179 if err1 == io.EOF && err2 == io.EOF { 180 return true, nil 181 } 182 } 183} 184 185func pathWalk(ctx context.Context, root string, pathC chan<- *currentPath) error { 186 return filepath.Walk(root, func(path string, f os.FileInfo, err error) error { 187 if err != nil { 188 return err 189 } 190 191 // Rebase path 192 path, err = filepath.Rel(root, path) 193 if err != nil { 194 return err 195 } 196 197 path = filepath.Join(string(os.PathSeparator), path) 198 199 // Skip root 200 if path == string(os.PathSeparator) { 201 return nil 202 } 203 204 p := ¤tPath{ 205 path: path, 206 f: f, 207 fullPath: filepath.Join(root, path), 208 } 209 210 select { 211 case <-ctx.Done(): 212 return ctx.Err() 213 case pathC <- p: 214 return nil 215 } 216 }) 217} 218 219func nextPath(ctx context.Context, pathC <-chan *currentPath) (*currentPath, error) { 220 select { 221 case <-ctx.Done(): 222 return nil, ctx.Err() 223 case p := <-pathC: 224 return p, nil 225 } 226} 227 228// RootPath joins a path with a root, evaluating and bounding any 229// symlink to the root directory. 230func RootPath(root, path string) (string, error) { 231 if path == "" { 232 return root, nil 233 } 234 var linksWalked int // to protect against cycles 235 for { 236 i := linksWalked 237 newpath, err := walkLinks(root, path, &linksWalked) 238 if err != nil { 239 return "", err 240 } 241 path = newpath 242 if i == linksWalked { 243 newpath = filepath.Join("/", newpath) 244 if path == newpath { 245 return filepath.Join(root, newpath), nil 246 } 247 path = newpath 248 } 249 } 250} 251 252func walkLink(root, path string, linksWalked *int) (newpath string, islink bool, err error) { 253 if *linksWalked > 255 { 254 return "", false, errTooManyLinks 255 } 256 257 path = filepath.Join("/", path) 258 if path == "/" { 259 return path, false, nil 260 } 261 realPath := filepath.Join(root, path) 262 263 fi, err := os.Lstat(realPath) 264 if err != nil { 265 // If path does not yet exist, treat as non-symlink 266 if os.IsNotExist(err) { 267 return path, false, nil 268 } 269 return "", false, err 270 } 271 if fi.Mode()&os.ModeSymlink == 0 { 272 return path, false, nil 273 } 274 newpath, err = os.Readlink(realPath) 275 if err != nil { 276 return "", false, err 277 } 278 *linksWalked++ 279 return newpath, true, nil 280} 281 282func walkLinks(root, path string, linksWalked *int) (string, error) { 283 switch dir, file := filepath.Split(path); { 284 case dir == "": 285 newpath, _, err := walkLink(root, file, linksWalked) 286 return newpath, err 287 case file == "": 288 if os.IsPathSeparator(dir[len(dir)-1]) { 289 if dir == "/" { 290 return dir, nil 291 } 292 return walkLinks(root, dir[:len(dir)-1], linksWalked) 293 } 294 newpath, _, err := walkLink(root, dir, linksWalked) 295 return newpath, err 296 default: 297 newdir, err := walkLinks(root, dir, linksWalked) 298 if err != nil { 299 return "", err 300 } 301 newpath, islink, err := walkLink(root, filepath.Join(newdir, file), linksWalked) 302 if err != nil { 303 return "", err 304 } 305 if !islink { 306 return newpath, nil 307 } 308 if filepath.IsAbs(newpath) { 309 return newpath, nil 310 } 311 return filepath.Join(newdir, newpath), nil 312 } 313} 314