]>
Commit | Line | Data |
---|---|---|
9b12e4fe JC |
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 | } |