diff.go 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326
  1. /*
  2. Copyright The containerd Authors.
  3. Licensed under the Apache License, Version 2.0 (the "License");
  4. you may not use this file except in compliance with the License.
  5. You may obtain a copy of the License at
  6. http://www.apache.org/licenses/LICENSE-2.0
  7. Unless required by applicable law or agreed to in writing, software
  8. distributed under the License is distributed on an "AS IS" BASIS,
  9. WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  10. See the License for the specific language governing permissions and
  11. limitations under the License.
  12. */
  13. package fs
  14. import (
  15. "context"
  16. "os"
  17. "path/filepath"
  18. "strings"
  19. "github.com/sirupsen/logrus"
  20. "golang.org/x/sync/errgroup"
  21. )
  22. // ChangeKind is the type of modification that
  23. // a change is making.
  24. type ChangeKind int
  25. const (
  26. // ChangeKindUnmodified represents an unmodified
  27. // file
  28. ChangeKindUnmodified = iota
  29. // ChangeKindAdd represents an addition of
  30. // a file
  31. ChangeKindAdd
  32. // ChangeKindModify represents a change to
  33. // an existing file
  34. ChangeKindModify
  35. // ChangeKindDelete represents a delete of
  36. // a file
  37. ChangeKindDelete
  38. )
  39. func (k ChangeKind) String() string {
  40. switch k {
  41. case ChangeKindUnmodified:
  42. return "unmodified"
  43. case ChangeKindAdd:
  44. return "add"
  45. case ChangeKindModify:
  46. return "modify"
  47. case ChangeKindDelete:
  48. return "delete"
  49. default:
  50. return ""
  51. }
  52. }
  53. // Change represents single change between a diff and its parent.
  54. type Change struct {
  55. Kind ChangeKind
  56. Path string
  57. }
  58. // ChangeFunc is the type of function called for each change
  59. // computed during a directory changes calculation.
  60. type ChangeFunc func(ChangeKind, string, os.FileInfo, error) error
  61. // Changes computes changes between two directories calling the
  62. // given change function for each computed change. The first
  63. // directory is intended to the base directory and second
  64. // directory the changed directory.
  65. //
  66. // The change callback is called by the order of path names and
  67. // should be appliable in that order.
  68. //
  69. // Due to this apply ordering, the following is true
  70. // - Removed directory trees only create a single change for the root
  71. // directory removed. Remaining changes are implied.
  72. // - A directory which is modified to become a file will not have
  73. // delete entries for sub-path items, their removal is implied
  74. // by the removal of the parent directory.
  75. //
  76. // Opaque directories will not be treated specially and each file
  77. // removed from the base directory will show up as a removal.
  78. //
  79. // File content comparisons will be done on files which have timestamps
  80. // which may have been truncated. If either of the files being compared
  81. // has a zero value nanosecond value, each byte will be compared for
  82. // differences. If 2 files have the same seconds value but different
  83. // nanosecond values where one of those values is zero, the files will
  84. // be considered unchanged if the content is the same. This behavior
  85. // is to account for timestamp truncation during archiving.
  86. func Changes(ctx context.Context, a, b string, changeFn ChangeFunc) error {
  87. if a == "" {
  88. logrus.Debugf("Using single walk diff for %s", b)
  89. return addDirChanges(ctx, changeFn, b)
  90. } else if diffOptions := detectDirDiff(b, a); diffOptions != nil {
  91. logrus.Debugf("Using single walk diff for %s from %s", diffOptions.diffDir, a)
  92. return diffDirChanges(ctx, changeFn, a, diffOptions)
  93. }
  94. logrus.Debugf("Using double walk diff for %s from %s", b, a)
  95. return doubleWalkDiff(ctx, changeFn, a, b)
  96. }
  97. func addDirChanges(ctx context.Context, changeFn ChangeFunc, root string) error {
  98. return filepath.Walk(root, func(path string, f os.FileInfo, err error) error {
  99. if err != nil {
  100. return err
  101. }
  102. // Rebase path
  103. path, err = filepath.Rel(root, path)
  104. if err != nil {
  105. return err
  106. }
  107. path = filepath.Join(string(os.PathSeparator), path)
  108. // Skip root
  109. if path == string(os.PathSeparator) {
  110. return nil
  111. }
  112. return changeFn(ChangeKindAdd, path, f, nil)
  113. })
  114. }
  115. // diffDirOptions is used when the diff can be directly calculated from
  116. // a diff directory to its base, without walking both trees.
  117. type diffDirOptions struct {
  118. diffDir string
  119. skipChange func(string) (bool, error)
  120. deleteChange func(string, string, os.FileInfo) (string, error)
  121. }
  122. // diffDirChanges walks the diff directory and compares changes against the base.
  123. func diffDirChanges(ctx context.Context, changeFn ChangeFunc, base string, o *diffDirOptions) error {
  124. changedDirs := make(map[string]struct{})
  125. return filepath.Walk(o.diffDir, func(path string, f os.FileInfo, err error) error {
  126. if err != nil {
  127. return err
  128. }
  129. // Rebase path
  130. path, err = filepath.Rel(o.diffDir, path)
  131. if err != nil {
  132. return err
  133. }
  134. path = filepath.Join(string(os.PathSeparator), path)
  135. // Skip root
  136. if path == string(os.PathSeparator) {
  137. return nil
  138. }
  139. // TODO: handle opaqueness, start new double walker at this
  140. // location to get deletes, and skip tree in single walker
  141. if o.skipChange != nil {
  142. if skip, err := o.skipChange(path); skip {
  143. return err
  144. }
  145. }
  146. var kind ChangeKind
  147. deletedFile, err := o.deleteChange(o.diffDir, path, f)
  148. if err != nil {
  149. return err
  150. }
  151. // Find out what kind of modification happened
  152. if deletedFile != "" {
  153. path = deletedFile
  154. kind = ChangeKindDelete
  155. f = nil
  156. } else {
  157. // Otherwise, the file was added
  158. kind = ChangeKindAdd
  159. // ...Unless it already existed in a base, in which case, it's a modification
  160. stat, err := os.Stat(filepath.Join(base, path))
  161. if err != nil && !os.IsNotExist(err) {
  162. return err
  163. }
  164. if err == nil {
  165. // The file existed in the base, so that's a modification
  166. // However, if it's a directory, maybe it wasn't actually modified.
  167. // If you modify /foo/bar/baz, then /foo will be part of the changed files only because it's the parent of bar
  168. if stat.IsDir() && f.IsDir() {
  169. if f.Size() == stat.Size() && f.Mode() == stat.Mode() && sameFsTime(f.ModTime(), stat.ModTime()) {
  170. // Both directories are the same, don't record the change
  171. return nil
  172. }
  173. }
  174. kind = ChangeKindModify
  175. }
  176. }
  177. // If /foo/bar/file.txt is modified, then /foo/bar must be part of the changed files.
  178. // This block is here to ensure the change is recorded even if the
  179. // modify time, mode and size of the parent directory in the rw and ro layers are all equal.
  180. // Check https://github.com/docker/docker/pull/13590 for details.
  181. if f.IsDir() {
  182. changedDirs[path] = struct{}{}
  183. }
  184. if kind == ChangeKindAdd || kind == ChangeKindDelete {
  185. parent := filepath.Dir(path)
  186. if _, ok := changedDirs[parent]; !ok && parent != "/" {
  187. pi, err := os.Stat(filepath.Join(o.diffDir, parent))
  188. if err := changeFn(ChangeKindModify, parent, pi, err); err != nil {
  189. return err
  190. }
  191. changedDirs[parent] = struct{}{}
  192. }
  193. }
  194. return changeFn(kind, path, f, nil)
  195. })
  196. }
  197. // doubleWalkDiff walks both directories to create a diff
  198. func doubleWalkDiff(ctx context.Context, changeFn ChangeFunc, a, b string) (err error) {
  199. g, ctx := errgroup.WithContext(ctx)
  200. var (
  201. c1 = make(chan *currentPath)
  202. c2 = make(chan *currentPath)
  203. f1, f2 *currentPath
  204. rmdir string
  205. )
  206. g.Go(func() error {
  207. defer close(c1)
  208. return pathWalk(ctx, a, c1)
  209. })
  210. g.Go(func() error {
  211. defer close(c2)
  212. return pathWalk(ctx, b, c2)
  213. })
  214. g.Go(func() error {
  215. for c1 != nil || c2 != nil {
  216. if f1 == nil && c1 != nil {
  217. f1, err = nextPath(ctx, c1)
  218. if err != nil {
  219. return err
  220. }
  221. if f1 == nil {
  222. c1 = nil
  223. }
  224. }
  225. if f2 == nil && c2 != nil {
  226. f2, err = nextPath(ctx, c2)
  227. if err != nil {
  228. return err
  229. }
  230. if f2 == nil {
  231. c2 = nil
  232. }
  233. }
  234. if f1 == nil && f2 == nil {
  235. continue
  236. }
  237. var f os.FileInfo
  238. k, p := pathChange(f1, f2)
  239. switch k {
  240. case ChangeKindAdd:
  241. if rmdir != "" {
  242. rmdir = ""
  243. }
  244. f = f2.f
  245. f2 = nil
  246. case ChangeKindDelete:
  247. // Check if this file is already removed by being
  248. // under of a removed directory
  249. if rmdir != "" && strings.HasPrefix(f1.path, rmdir) {
  250. f1 = nil
  251. continue
  252. } else if f1.f.IsDir() {
  253. rmdir = f1.path + string(os.PathSeparator)
  254. } else if rmdir != "" {
  255. rmdir = ""
  256. }
  257. f1 = nil
  258. case ChangeKindModify:
  259. same, err := sameFile(f1, f2)
  260. if err != nil {
  261. return err
  262. }
  263. if f1.f.IsDir() && !f2.f.IsDir() {
  264. rmdir = f1.path + string(os.PathSeparator)
  265. } else if rmdir != "" {
  266. rmdir = ""
  267. }
  268. f = f2.f
  269. f1 = nil
  270. f2 = nil
  271. if same {
  272. if !isLinked(f) {
  273. continue
  274. }
  275. k = ChangeKindUnmodified
  276. }
  277. }
  278. if err := changeFn(k, p, f, nil); err != nil {
  279. return err
  280. }
  281. }
  282. return nil
  283. })
  284. return g.Wait()
  285. }