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 := &currentPath{
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