op public repos

Blob

Date:: Sun Mar 10 14:55:28 2019 UTC
Message:: read UUID back from work tree meta data
Actions:: History | Blame | Raw File
1 /*
2  * Copyright (c) 2018, 2019 Stefan Sperling <stsp@openbsd.org>
3  *
4  * Permission to use, copy, modify, and distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16 
17 #include <sys/queue.h>
18 #include <sys/tree.h>
19 #include <sys/stat.h>
20 
21 #include <dirent.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <sha1.h>
26 #include <endian.h>
27 #include <limits.h>
28 #include <uuid.h>
29 
30 #include "got_error.h"
31 #include "got_object.h"
32 
33 #include "got_lib_path.h"
34 #include "got_lib_fileindex.h"
35 #include "got_lib_worktree.h"
36 
37 struct got_fileindex {
38 	struct got_fileindex_tree entries;
39 	int nentries;
40 #define GOT_FILEIDX_MAX_ENTRIES INT_MAX
41 };
42 
43 const struct got_error *
44 got_fileindex_entry_update(struct got_fileindex_entry *entry,
45     const char *ondisk_path, uint8_t *blob_sha1, uint8_t *commit_sha1,
46     int update_timestamps)
47 {
48 	struct stat sb;
49 
50 	if (lstat(ondisk_path, &sb) != 0)
51 		return got_error_from_errno();
52 
53 	if (update_timestamps) {
54 		entry->ctime_sec = sb.st_ctime;
55 		entry->ctime_nsec = sb.st_ctimensec;
56 		entry->mtime_sec = sb.st_mtime;
57 		entry->mtime_nsec = sb.st_mtimensec;
58 	}
59 	entry->uid = sb.st_uid;
60 	entry->gid = sb.st_gid;
61 	entry->size = (sb.st_size & 0xffffffff);
62 	if (sb.st_mode & S_IFLNK)
63 		entry->mode = GOT_FILEIDX_MODE_SYMLINK;
64 	else
65 		entry->mode = GOT_FILEIDX_MODE_REGULAR_FILE;
66 	entry->mode |= ((sb.st_mode & (S_IRWXU | S_IRWXG | S_IRWXO)) <<
67 	    GOT_FILEIDX_MODE_PERMS_SHIFT);
68 	memcpy(entry->blob_sha1, blob_sha1, SHA1_DIGEST_LENGTH);
69 	memcpy(entry->commit_sha1, commit_sha1, SHA1_DIGEST_LENGTH);
70 
71 	return NULL;
72 }
73 
74 const struct got_error *
75 got_fileindex_entry_alloc(struct got_fileindex_entry **entry,
76     const char *ondisk_path, const char *relpath, uint8_t *blob_sha1,
77     uint8_t *commit_sha1)
78 {
79 	size_t len;
80 
81 	*entry = calloc(1, sizeof(**entry));
82 	if (*entry == NULL)
83 		return got_error_from_errno();
84 
85 	(*entry)->path = strdup(relpath);
86 	if ((*entry)->path == NULL) {
87 		const struct got_error *err = got_error_from_errno();
88 		free(*entry);
89 		*entry = NULL;
90 		return err;
91 	}
92 
93 	len = strlen(relpath);
94 	if (len > GOT_FILEIDX_F_PATH_LEN)
95 		len = GOT_FILEIDX_F_PATH_LEN;
96 	(*entry)->flags |= len;
97 
98 	return got_fileindex_entry_update(*entry, ondisk_path, blob_sha1,
99 	    commit_sha1, 1);
100 }
101 
102 void
103 got_fileindex_entry_free(struct got_fileindex_entry *entry)
104 {
105 	free(entry->path);
106 	free(entry);
107 }
108 
109 static const struct got_error *
110 add_entry(struct got_fileindex *fileindex, struct got_fileindex_entry *entry)
111 {
112 	if (fileindex->nentries >= GOT_FILEIDX_MAX_ENTRIES)
113 		return got_error(GOT_ERR_NO_SPACE);
114 
115 	RB_INSERT(got_fileindex_tree, &fileindex->entries, entry);
116 	fileindex->nentries++;
117 	return NULL;
118 }
119 
120 const struct got_error *
121 got_fileindex_entry_add(struct got_fileindex *fileindex,
122     struct got_fileindex_entry *entry)
123 {
124 	/* Flag this entry until it gets written out to disk. */
125 	entry->flags |= GOT_FILEIDX_F_INTENT_TO_ADD;
126 
127 	return add_entry(fileindex, entry);
128 }
129 
130 void
131 got_fileindex_entry_remove(struct got_fileindex *fileindex,
132     struct got_fileindex_entry *entry)
133 {
134 	RB_REMOVE(got_fileindex_tree, &fileindex->entries, entry);
135 	fileindex->nentries--;
136 }
137 
138 struct got_fileindex_entry *
139 got_fileindex_entry_get(struct got_fileindex *fileindex, const char *path)
140 {
141 	struct got_fileindex_entry key;
142 	memset(&key, 0, sizeof(key));
143 	key.path = (char *)path;
144 	return RB_FIND(got_fileindex_tree, &fileindex->entries, &key);
145 }
146 
147 const struct got_error *
148 got_fileindex_for_each_entry_safe(struct got_fileindex *fileindex,
149     got_fileindex_cb cb, void *cb_arg)
150 {
151 	const struct got_error *err;
152 	struct got_fileindex_entry *entry, *tmp;
153 
154 	RB_FOREACH_SAFE(entry, got_fileindex_tree, &fileindex->entries, tmp) {
155 		err = (*cb)(cb_arg, entry);
156 		if (err)
157 			return err;
158 	}
159 	return NULL;
160 }
161 
162 struct got_fileindex *
163 got_fileindex_alloc(void)
164 {
165 	struct got_fileindex *fileindex;
166 
167 	fileindex = calloc(1, sizeof(*fileindex));
168 	if (fileindex == NULL)
169 		return NULL;
170 
171 	RB_INIT(&fileindex->entries);
172 	return fileindex;
173 }
174 
175 void
176 got_fileindex_free(struct got_fileindex *fileindex)
177 {
178 	struct got_fileindex_entry *entry;
179 
180 	while ((entry = RB_MIN(got_fileindex_tree, &fileindex->entries))) {
181 		RB_REMOVE(got_fileindex_tree, &fileindex->entries, entry);
182 		got_fileindex_entry_free(entry);
183 	}
184 	free(fileindex);
185 }
186 
187 static const struct got_error *
188 write_fileindex_val64(SHA1_CTX *ctx, uint64_t val, FILE *outfile)
189 {
190 	size_t n;
191 
192 	val = htobe64(val);
193 	SHA1Update(ctx, (uint8_t *)&val, sizeof(val));
194 	n = fwrite(&val, 1, sizeof(val), outfile);
195 	if (n != sizeof(val))
196 		return got_ferror(outfile, GOT_ERR_IO);
197 	return NULL;
198 }
199 
200 static const struct got_error *
201 write_fileindex_val32(SHA1_CTX *ctx, uint32_t val, FILE *outfile)
202 {
203 	size_t n;
204 
205 	val = htobe32(val);
206 	SHA1Update(ctx, (uint8_t *)&val, sizeof(val));
207 	n = fwrite(&val, 1, sizeof(val), outfile);
208 	if (n != sizeof(val))
209 		return got_ferror(outfile, GOT_ERR_IO);
210 	return NULL;
211 }
212 
213 static const struct got_error *
214 write_fileindex_val16(SHA1_CTX *ctx, uint16_t val, FILE *outfile)
215 {
216 	size_t n;
217 
218 	val = htobe16(val);
219 	SHA1Update(ctx, (uint8_t *)&val, sizeof(val));
220 	n = fwrite(&val, 1, sizeof(val), outfile);
221 	if (n != sizeof(val))
222 		return got_ferror(outfile, GOT_ERR_IO);
223 	return NULL;
224 }
225 
226 static const struct got_error *
227 write_fileindex_path(SHA1_CTX *ctx, const char *path, FILE *outfile)
228 {
229 	size_t n, len, pad = 0;
230 	static const uint8_t zero[8] = { 0 };
231 
232 	len = strlen(path);
233 	while ((len + pad) % 8 != 0)
234 		pad++;
235 	if (pad == 0)
236 		pad = 8; /* NUL-terminate */
237 
238 	SHA1Update(ctx, path, len);
239 	n = fwrite(path, 1, len, outfile);
240 	if (n != len)
241 		return got_ferror(outfile, GOT_ERR_IO);
242 	SHA1Update(ctx, zero, pad);
243 	n = fwrite(zero, 1, pad, outfile);
244 	if (n != pad)
245 		return got_ferror(outfile, GOT_ERR_IO);
246 	return NULL;
247 }
248 
249 static const struct got_error *
250 write_fileindex_entry(SHA1_CTX *ctx, struct got_fileindex_entry *entry,
251     FILE *outfile)
252 {
253 	const struct got_error *err;
254 	size_t n;
255 
256 	err = write_fileindex_val64(ctx, entry->ctime_sec, outfile);
257 	if (err)
258 		return err;
259 	err = write_fileindex_val64(ctx, entry->ctime_nsec, outfile);
260 	if (err)
261 		return err;
262 	err = write_fileindex_val64(ctx, entry->mtime_sec, outfile);
263 	if (err)
264 		return err;
265 	err = write_fileindex_val64(ctx, entry->mtime_nsec, outfile);
266 	if (err)
267 		return err;
268 
269 	err = write_fileindex_val32(ctx, entry->uid, outfile);
270 	if (err)
271 		return err;
272 	err = write_fileindex_val32(ctx, entry->gid, outfile);
273 	if (err)
274 		return err;
275 	err = write_fileindex_val32(ctx, entry->size, outfile);
276 	if (err)
277 		return err;
278 
279 	err = write_fileindex_val16(ctx, entry->mode, outfile);
280 	if (err)
281 		return err;
282 
283 	SHA1Update(ctx, entry->blob_sha1, SHA1_DIGEST_LENGTH);
284 	n = fwrite(entry->blob_sha1, 1, SHA1_DIGEST_LENGTH, outfile);
285 	if (n != SHA1_DIGEST_LENGTH)
286 		return got_ferror(outfile, GOT_ERR_IO);
287 
288 	SHA1Update(ctx, entry->commit_sha1, SHA1_DIGEST_LENGTH);
289 	n = fwrite(entry->commit_sha1, 1, SHA1_DIGEST_LENGTH, outfile);
290 	if (n != SHA1_DIGEST_LENGTH)
291 		return got_ferror(outfile, GOT_ERR_IO);
292 
293 	err = write_fileindex_val32(ctx, entry->flags, outfile);
294 	if (err)
295 		return err;
296 
297 	err = write_fileindex_path(ctx, entry->path, outfile);
298 	return err;
299 }
300 
301 const struct got_error *
302 got_fileindex_write(struct got_fileindex *fileindex, FILE *outfile)
303 {
304 	const struct got_error *err = NULL;
305 	struct got_fileindex_hdr hdr;
306 	SHA1_CTX ctx;
307 	uint8_t sha1[SHA1_DIGEST_LENGTH];
308 	size_t n;
309 	struct got_fileindex_entry *entry;
310 
311 	SHA1Init(&ctx);
312 
313 	hdr.signature = htobe32(GOT_FILE_INDEX_SIGNATURE);
314 	hdr.version = htobe32(GOT_FILE_INDEX_VERSION);
315 	hdr.nentries = htobe32(fileindex->nentries);
316 
317 	SHA1Update(&ctx, (uint8_t *)&hdr.signature, sizeof(hdr.signature));
318 	SHA1Update(&ctx, (uint8_t *)&hdr.version, sizeof(hdr.version));
319 	SHA1Update(&ctx, (uint8_t *)&hdr.nentries, sizeof(hdr.nentries));
320 	n = fwrite(&hdr.signature, 1, sizeof(hdr.signature), outfile);
321 	if (n != sizeof(hdr.signature))
322 		return got_ferror(outfile, GOT_ERR_IO);
323 	n = fwrite(&hdr.version, 1, sizeof(hdr.version), outfile);
324 	if (n != sizeof(hdr.version))
325 		return got_ferror(outfile, GOT_ERR_IO);
326 	n = fwrite(&hdr.nentries, 1, sizeof(hdr.nentries), outfile);
327 	if (n != sizeof(hdr.nentries))
328 		return got_ferror(outfile, GOT_ERR_IO);
329 
330 	RB_FOREACH(entry, got_fileindex_tree, &fileindex->entries) {
331 		entry->flags &= ~GOT_FILEIDX_F_INTENT_TO_ADD;
332 		err = write_fileindex_entry(&ctx, entry, outfile);
333 		if (err)
334 			return err;
335 	}
336 
337 	SHA1Final(sha1, &ctx);
338 	n = fwrite(sha1, 1, sizeof(sha1), outfile);
339 	if (n != sizeof(sha1))
340 		return got_ferror(outfile, GOT_ERR_IO);
341 
342 	if (fflush(outfile) != 0)
343 		return got_error_from_errno();
344 
345 	return NULL;
346 }
347 
348 static const struct got_error *
349 read_fileindex_val64(uint64_t *val, SHA1_CTX *ctx, FILE *infile)
350 {
351 	size_t n;
352 
353 	n = fread(val, 1, sizeof(*val), infile);
354 	if (n != sizeof(*val))
355 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
356 	SHA1Update(ctx, (uint8_t *)val, sizeof(*val));
357 	*val = be64toh(*val);
358 	return NULL;
359 }
360 
361 static const struct got_error *
362 read_fileindex_val32(uint32_t *val, SHA1_CTX *ctx, FILE *infile)
363 {
364 	size_t n;
365 
366 	n = fread(val, 1, sizeof(*val), infile);
367 	if (n != sizeof(*val))
368 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
369 	SHA1Update(ctx, (uint8_t *)val, sizeof(*val));
370 	*val = be32toh(*val);
371 	return NULL;
372 }
373 
374 static const struct got_error *
375 read_fileindex_val16(uint16_t *val, SHA1_CTX *ctx, FILE *infile)
376 {
377 	size_t n;
378 
379 	n = fread(val, 1, sizeof(*val), infile);
380 	if (n != sizeof(*val))
381 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
382 	SHA1Update(ctx, (uint8_t *)val, sizeof(*val));
383 	*val = be16toh(*val);
384 	return NULL;
385 }
386 
387 static const struct got_error *
388 read_fileindex_path(char **path, SHA1_CTX *ctx, FILE *infile)
389 {
390 	const struct got_error *err = NULL;
391 	uint8_t buf[8];
392 	size_t n, len = 0, totlen = sizeof(buf);
393 
394 	*path = malloc(totlen);
395 	if (*path == NULL)
396 		return got_error_from_errno();
397 
398 	do {
399 		n = fread(buf, 1, sizeof(buf), infile);
400 		if (n != sizeof(buf))
401 			return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
402 		if (len + sizeof(buf) > totlen) {
403 			char *p = reallocarray(*path, totlen + sizeof(buf), 1);
404 			if (p == NULL) {
405 				err = got_error_from_errno();
406 				break;
407 			}
408 			totlen += sizeof(buf);
409 			*path = p;
410 		}
411 		SHA1Update(ctx, buf, sizeof(buf));
412 		memcpy(*path + len, buf, sizeof(buf));
413 		len += sizeof(buf);
414 	} while (memchr(buf, '\0', sizeof(buf)) == NULL);
415 
416 	if (err) {
417 		free(*path);
418 		*path = NULL;
419 	}
420 	return err;
421 }
422 
423 static const struct got_error *
424 read_fileindex_entry(struct got_fileindex_entry **entryp, SHA1_CTX *ctx,
425     FILE *infile)
426 {
427 	const struct got_error *err;
428 	struct got_fileindex_entry *entry;
429 	size_t n;
430 
431 	*entryp = NULL;
432 
433 	entry = calloc(1, sizeof(*entry));
434 	if (entry == NULL)
435 		return got_error_from_errno();
436 
437 	err = read_fileindex_val64(&entry->ctime_sec, ctx, infile);
438 	if (err)
439 		goto done;
440 	err = read_fileindex_val64(&entry->ctime_nsec, ctx, infile);
441 	if (err)
442 		goto done;
443 	err = read_fileindex_val64(&entry->mtime_sec, ctx, infile);
444 	if (err)
445 		goto done;
446 	err = read_fileindex_val64(&entry->mtime_nsec, ctx, infile);
447 	if (err)
448 		goto done;
449 
450 	err = read_fileindex_val32(&entry->uid, ctx, infile);
451 	if (err)
452 		goto done;
453 	err = read_fileindex_val32(&entry->gid, ctx, infile);
454 	if (err)
455 		goto done;
456 	err = read_fileindex_val32(&entry->size, ctx, infile);
457 	if (err)
458 		goto done;
459 
460 	err = read_fileindex_val16(&entry->mode, ctx, infile);
461 	if (err)
462 		goto done;
463 
464 	n = fread(entry->blob_sha1, 1, SHA1_DIGEST_LENGTH, infile);
465 	if (n != SHA1_DIGEST_LENGTH) {
466 		err = got_ferror(infile, GOT_ERR_FILEIDX_BAD);
467 		goto done;
468 	}
469 	SHA1Update(ctx, entry->blob_sha1, SHA1_DIGEST_LENGTH);
470 
471 	n = fread(entry->commit_sha1, 1, SHA1_DIGEST_LENGTH, infile);
472 	if (n != SHA1_DIGEST_LENGTH) {
473 		err = got_ferror(infile, GOT_ERR_FILEIDX_BAD);
474 		goto done;
475 	}
476 	SHA1Update(ctx, entry->commit_sha1, SHA1_DIGEST_LENGTH);
477 
478 	err = read_fileindex_val32(&entry->flags, ctx, infile);
479 	if (err)
480 		goto done;
481 
482 	err = read_fileindex_path(&entry->path, ctx, infile);
483 done:
484 	if (err)
485 		free(entry);
486 	else
487 		*entryp = entry;
488 	return err;
489 }
490 
491 const struct got_error *
492 got_fileindex_read(struct got_fileindex *fileindex, FILE *infile)
493 {
494 	const struct got_error *err = NULL;
495 	struct got_fileindex_hdr hdr;
496 	SHA1_CTX ctx;
497 	struct got_fileindex_entry *entry;
498 	uint8_t sha1_expected[SHA1_DIGEST_LENGTH];
499 	uint8_t sha1[SHA1_DIGEST_LENGTH];
500 	size_t n;
501 	int i;
502 
503 	SHA1Init(&ctx);
504 
505 	n = fread(&hdr.signature, 1, sizeof(hdr.signature), infile);
506 	if (n != sizeof(hdr.signature)) {
507 		if (n == 0) /* EOF */
508 			return NULL;
509 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
510 	}
511 	n = fread(&hdr.version, 1, sizeof(hdr.version), infile);
512 	if (n != sizeof(hdr.version)) {
513 		if (n == 0) /* EOF */
514 			return NULL;
515 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
516 	}
517 	n = fread(&hdr.nentries, 1, sizeof(hdr.nentries), infile);
518 	if (n != sizeof(hdr.nentries)) {
519 		if (n == 0) /* EOF */
520 			return NULL;
521 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
522 	}
523 
524 	SHA1Update(&ctx, (uint8_t *)&hdr.signature, sizeof(hdr.signature));
525 	SHA1Update(&ctx, (uint8_t *)&hdr.version, sizeof(hdr.version));
526 	SHA1Update(&ctx, (uint8_t *)&hdr.nentries, sizeof(hdr.nentries));
527 
528 	hdr.signature = be32toh(hdr.signature);
529 	hdr.version = be32toh(hdr.version);
530 	hdr.nentries = be32toh(hdr.nentries);
531 
532 	if (hdr.signature != GOT_FILE_INDEX_SIGNATURE)
533 		return got_error(GOT_ERR_FILEIDX_SIG);
534 	if (hdr.version != GOT_FILE_INDEX_VERSION)
535 		return got_error(GOT_ERR_FILEIDX_VER);
536 
537 	for (i = 0; i < hdr.nentries; i++) {
538 		err = read_fileindex_entry(&entry, &ctx, infile);
539 		if (err)
540 			return err;
541 		err = add_entry(fileindex, entry);
542 		if (err)
543 			return err;
544 	}
545 
546 	n = fread(sha1_expected, 1, sizeof(sha1_expected), infile);
547 	if (n != sizeof(sha1_expected))
548 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
549 	SHA1Final(sha1, &ctx);
550 	if (memcmp(sha1, sha1_expected, SHA1_DIGEST_LENGTH) != 0)
551 		return got_error(GOT_ERR_FILEIDX_CSUM);
552 
553 	return NULL;
554 }
555 
556 struct got_fileindex_entry *
557 walk_fileindex(struct got_fileindex *fileindex, struct got_fileindex_entry *ie)
558 {
559 	struct got_fileindex_entry *next;
560 
561 	next = RB_NEXT(got_fileindex_tree, &fileindex->entries, ie);
562 
563 	/* Skip entries which were newly added by diff callbacks. */
564 	while (next && (next->flags & GOT_FILEIDX_F_INTENT_TO_ADD))
565 		next = RB_NEXT(got_fileindex_tree, &fileindex->entries, next);
566 
567 	return next;
568 }
569 
570 static const struct got_error *
571 diff_fileindex_tree(struct got_fileindex *, struct got_fileindex_entry **,
572     struct got_tree_object *, const char *, struct got_repository *,
573     struct got_fileindex_diff_tree_cb *, void *);
574 
575 static const struct got_error *
576 walk_tree(struct got_tree_entry **next, struct got_fileindex *fileindex,
577     struct got_fileindex_entry **ie, struct got_tree_entry *te,
578     const char *path, struct got_repository *repo,
579     struct got_fileindex_diff_tree_cb *cb, void *cb_arg)
580 {
581 	const struct got_error *err = NULL;
582 
583 	if (S_ISDIR(te->mode)) {
584 		char *subpath;
585 		struct got_tree_object *subtree;
586 
587 		if (asprintf(&subpath, "%s%s%s", path,
588 		    path[0] == '\0' ? "" : "/", te->name) == -1)
589 			return got_error_from_errno();
590 
591 		err = got_object_open_as_tree(&subtree, repo, te->id);
592 		if (err) {
593 			free(subpath);
594 			return err;
595 		}
596 
597 		err = diff_fileindex_tree(fileindex, ie, subtree,
598 		    subpath, repo, cb, cb_arg);
599 		free(subpath);
600 		got_object_tree_close(subtree);
601 		if (err)
602 			return err;
603 	}
604 
605 	*next = SIMPLEQ_NEXT(te, entry);
606 	return NULL;
607 }
608 
609 static const struct got_error *
610 diff_fileindex_tree(struct got_fileindex *fileindex,
611     struct got_fileindex_entry **ie, struct got_tree_object *tree,
612     const char *path, struct got_repository *repo,
613     struct got_fileindex_diff_tree_cb *cb, void *cb_arg)
614 {
615 	const struct got_error *err = NULL;
616 	struct got_tree_entry *te = NULL;
617 	size_t path_len = strlen(path);
618 	const struct got_tree_entries *entries;
619 	struct got_fileindex_entry *next;
620 
621 	entries = got_object_tree_get_entries(tree);
622 	te = SIMPLEQ_FIRST(&entries->head);
623 	while ((*ie && got_path_is_child((*ie)->path, path, path_len)) || te) {
624 		if (te && *ie) {
625 			char *te_path;
626 			int cmp;
627 			if (asprintf(&te_path, "%s/%s", path, te->name) == -1) {
628 				err = got_error_from_errno();
629 				break;
630 			}
631 			cmp = got_path_cmp((*ie)->path, te_path);
632 			free(te_path);
633 			if (cmp == 0) {
634 				err = cb->diff_old_new(cb_arg, *ie, te,
635 				    path);
636 				if (err)
637 					break;
638 				*ie = walk_fileindex(fileindex, *ie);
639 				err = walk_tree(&te, fileindex, ie, te,
640 				    path, repo, cb, cb_arg);
641 			} else if (cmp < 0 ) {
642 				next = walk_fileindex(fileindex, *ie);
643 				err = cb->diff_old(cb_arg, *ie, path);
644 				if (err)
645 					break;
646 				*ie = next;
647 			} else {
648 				err = cb->diff_new(cb_arg, te, path);
649 				if (err)
650 					break;
651 				err = walk_tree(&te, fileindex, ie, te,
652 				    path, repo, cb, cb_arg);
653 			}
654 			if (err)
655 				break;
656 		} else if (*ie) {
657 			next = walk_fileindex(fileindex, *ie);
658 			err = cb->diff_old(cb_arg, *ie, path);
659 			if (err)
660 				break;
661 			*ie = next;
662 		} else if (te) {
663 			err = cb->diff_new(cb_arg, te, path);
664 			if (err)
665 				break;
666 			err = walk_tree(&te, fileindex, ie, te, path, repo, cb,
667 			    cb_arg);
668 			if (err)
669 				break;
670 		}
671 	}
672 
673 	return err;
674 }
675 
676 const struct got_error *
677 got_fileindex_diff_tree(struct got_fileindex *fileindex,
678     struct got_tree_object *tree, struct got_repository *repo,
679     struct got_fileindex_diff_tree_cb *cb, void *cb_arg)
680 {
681 	struct got_fileindex_entry *min;
682 	min = RB_MIN(got_fileindex_tree, &fileindex->entries);
683 	return diff_fileindex_tree(fileindex, &min, tree, "", repo, cb, cb_arg);
684 }
685 
686 static const struct got_error *
687 diff_fileindex_dir(struct got_fileindex *, struct got_fileindex_entry **, DIR *,
688     const char *, const char *, struct got_repository *,
689     struct got_fileindex_diff_dir_cb *, void *);
690 
691 static const struct got_error *
692 walk_dir(struct got_pathlist_entry **next, struct got_fileindex *fileindex,
693     struct got_fileindex_entry **ie, struct got_pathlist_entry *dle,
694     const char *path, DIR *dir, const char *rootpath,
695     struct got_repository *repo, struct got_fileindex_diff_dir_cb *cb,
696     void *cb_arg)
697 {
698 	const struct got_error *err = NULL;
699 	struct dirent *de = dle->data;
700 
701 	if (de->d_type == DT_DIR) {
702 		char *subpath;
703 		char *subdirpath;
704 		DIR *subdir;
705 
706 		if (asprintf(&subpath, "%s%s%s", path,
707 		    path[0] == '\0' ? "" : "/", de->d_name) == -1)
708 			return got_error_from_errno();
709 
710 		if (asprintf(&subdirpath, "%s/%s", rootpath, subpath) == -1) {
711 			free(subpath);
712 			return got_error_from_errno();
713 		}
714 
715 		subdir = opendir(subdirpath);
716 		if (subdir == NULL) {
717 			free(subpath);
718 			free(subdirpath);
719 			return got_error_from_errno();
720 		}
721 
722 		err = diff_fileindex_dir(fileindex, ie, subdir, rootpath,
723 		    subpath, repo, cb, cb_arg);
724 		free(subpath);
725 		free(subdirpath);
726 		closedir(subdir);
727 		if (err)
728 			return err;
729 	}
730 
731 	*next = TAILQ_NEXT(dle, entry);
732 	return NULL;
733 }
734 
735 static const struct got_error *
736 diff_fileindex_dir(struct got_fileindex *fileindex,
737     struct got_fileindex_entry **ie, DIR *dir, const char *rootpath,
738     const char *path, struct got_repository *repo,
739     struct got_fileindex_diff_dir_cb *cb, void *cb_arg)
740 {
741 	const struct got_error *err = NULL;
742 	struct dirent *de = NULL;
743 	size_t path_len = strlen(path);
744 	struct got_fileindex_entry *next;
745 	struct got_pathlist_head dirlist;
746 	struct got_pathlist_entry *dle;
747 
748 	TAILQ_INIT(&dirlist);
749 
750 	while (1) {
751 		struct got_pathlist_entry *new = NULL;
752 		struct dirent *dep = NULL;
753 
754 		de = malloc(sizeof(struct dirent) + NAME_MAX + 1);
755 		if (de == NULL) {
756 			err = got_error_from_errno();
757 			goto done;
758 		}
759 
760 		if (readdir_r(dir, de, &dep) != 0) {
761 			err = got_error_from_errno();
762 			free(de);
763 			goto done;
764 		}
765 		if (dep == NULL) {
766 			free(de);
767 			break;
768 		}
769 
770 		if (strcmp(de->d_name, ".") == 0 ||
771 		    strcmp(de->d_name, "..") == 0 ||
772 		    (path[0] == '\0' &&
773 		    strcmp(de->d_name, GOT_WORKTREE_GOT_DIR) == 0)) {
774 			free(de);
775 			continue;
776 		}
777 
778 		err = got_pathlist_insert(&new, &dirlist, de->d_name, de);
779 		if (err)
780 			goto done;
781 		if (new == NULL) {
782 			err = got_error(GOT_ERR_DIR_DUP_ENTRY);
783 			goto done;
784 		}
785 	}
786 
787 	dle = TAILQ_FIRST(&dirlist);
788 	while ((*ie && got_path_is_child((*ie)->path, path, path_len)) || dle) {
789 		if (dle && *ie) {
790 			char *de_path;
791 			int cmp;
792 			de = dle->data;
793 			if (asprintf(&de_path, "%s/%s", path,
794 			    de->d_name) == -1) {
795 				err = got_error_from_errno();
796 				break;
797 			}
798 			cmp = got_path_cmp((*ie)->path, de_path);
799 			free(de_path);
800 			if (cmp == 0) {
801 				err = cb->diff_old_new(cb_arg, *ie, de, path);
802 				if (err)
803 					break;
804 				*ie = walk_fileindex(fileindex, *ie);
805 				err = walk_dir(&dle, fileindex, ie, dle, path,
806 				    dir, rootpath, repo, cb, cb_arg);
807 			} else if (cmp < 0 ) {
808 				next = walk_fileindex(fileindex, *ie);
809 				err = cb->diff_old(cb_arg, *ie, path);
810 				if (err)
811 					break;
812 				*ie = next;
813 			} else {
814 				err = cb->diff_new(cb_arg, de, path);
815 				if (err)
816 					break;
817 				err = walk_dir(&dle, fileindex, ie, dle, path,
818 				    dir, rootpath, repo, cb, cb_arg);
819 			}
820 			if (err)
821 				break;
822 		} else if (*ie) {
823 			next = walk_fileindex(fileindex, *ie);
824 			err = cb->diff_old(cb_arg, *ie, path);
825 			if (err)
826 				break;
827 			*ie = next;
828 		} else if (dle) {
829 			de = dle->data;
830 			err = cb->diff_new(cb_arg, de, path);
831 			if (err)
832 				break;
833 			err = walk_dir(&dle, fileindex, ie, dle, path, dir,
834 			    rootpath, repo, cb, cb_arg);
835 			if (err)
836 				break;
837 		}
838 	}
839 done:
840 	TAILQ_FOREACH(dle, &dirlist, entry)
841 		free(dle->data);
842 	got_pathlist_free(&dirlist);
843 	return err;
844 }
845 
846 const struct got_error *
847 got_fileindex_diff_dir(struct got_fileindex *fileindex, DIR *rootdir,
848     const char *rootpath, const char *path, struct got_repository *repo,
849     struct got_fileindex_diff_dir_cb *cb, void *cb_arg)
850 {
851 	struct got_fileindex_entry *min;
852 	min = RB_MIN(got_fileindex_tree, &fileindex->entries);
853 	return diff_fileindex_dir(fileindex, &min, rootdir, rootpath, path,
854 	    repo, cb, cb_arg);
855 }
856 
857 RB_GENERATE(got_fileindex_tree, got_fileindex_entry, entry, got_fileindex_cmp);