op public repos

Blob

Date:: Thu Aug 8 14:38:43 2019 UTC
Message:: ensure that file index entry perms map to regular files
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 <errno.h>
22 #include <dirent.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <sha1.h>
27 #include <endian.h>
28 #include <limits.h>
29 #include <uuid.h>
30 
31 #include "got_error.h"
32 #include "got_object.h"
33 #include "got_path.h"
34 
35 #include "got_lib_fileindex.h"
36 #include "got_lib_worktree.h"
37 
38 /* got_fileindex_entry flags */
39 #define GOT_FILEIDX_F_PATH_LEN		0x00000fff
40 #define GOT_FILEIDX_F_STAGE		0x0000f000
41 #define GOT_FILEIDX_F_STAGE_SHIFT	12
42 #define GOT_FILEIDX_F_NOT_FLUSHED	0x00010000
43 #define GOT_FILEIDX_F_NO_BLOB		0x00020000
44 #define GOT_FILEIDX_F_NO_COMMIT		0x00040000
45 #define GOT_FILEIDX_F_NO_FILE_ON_DISK	0x00080000
46 
47 struct got_fileindex {
48 	struct got_fileindex_tree entries;
49 	int nentries;
50 #define GOT_FILEIDX_MAX_ENTRIES INT_MAX
51 };
52 
53 uint16_t
54 got_fileindex_perms_from_st(struct stat *sb)
55 {
56 	uint16_t perms = (sb->st_mode & (S_IRWXU | S_IRWXG | S_IRWXO));
57 	return (perms << GOT_FILEIDX_MODE_PERMS_SHIFT);
58 }
59 
60 mode_t
61 got_fileindex_perms_to_st(struct got_fileindex_entry *ie)
62 {
63 	mode_t perms = (ie->mode >> GOT_FILEIDX_MODE_PERMS_SHIFT);
64 	return (S_IFREG | (perms & (S_IRWXU | S_IRWXG | S_IRWXO)));
65 }
66 
67 const struct got_error *
68 got_fileindex_entry_update(struct got_fileindex_entry *ie,
69     const char *ondisk_path, uint8_t *blob_sha1, uint8_t *commit_sha1,
70     int update_timestamps)
71 {
72 	struct stat sb;
73 
74 	if (lstat(ondisk_path, &sb) != 0) {
75 		if ((ie->flags & GOT_FILEIDX_F_NO_FILE_ON_DISK) == 0)
76 			return got_error_from_errno2("lstat", ondisk_path);
77 	} else {
78 		if (sb.st_mode & S_IFDIR)
79 			return got_error_set_errno(EISDIR, ondisk_path);
80 		ie->flags &= ~GOT_FILEIDX_F_NO_FILE_ON_DISK;
81 	}
82 
83 
84 	if ((ie->flags & GOT_FILEIDX_F_NO_FILE_ON_DISK) == 0) {
85 		if (update_timestamps) {
86 			ie->ctime_sec = sb.st_ctime;
87 			ie->ctime_nsec = sb.st_ctimensec;
88 			ie->mtime_sec = sb.st_mtime;
89 			ie->mtime_nsec = sb.st_mtimensec;
90 		}
91 		ie->uid = sb.st_uid;
92 		ie->gid = sb.st_gid;
93 		ie->size = (sb.st_size & 0xffffffff);
94 		if (sb.st_mode & S_IFLNK)
95 			ie->mode = GOT_FILEIDX_MODE_SYMLINK;
96 		else
97 			ie->mode = GOT_FILEIDX_MODE_REGULAR_FILE;
98 		ie->mode |= got_fileindex_perms_from_st(&sb);
99 	}
100 
101 	if (blob_sha1) {
102 		memcpy(ie->blob_sha1, blob_sha1, SHA1_DIGEST_LENGTH);
103 		ie->flags &= ~GOT_FILEIDX_F_NO_BLOB;
104 	} else
105 		ie->flags |= GOT_FILEIDX_F_NO_BLOB;
106 
107 	if (commit_sha1) {
108 		memcpy(ie->commit_sha1, commit_sha1, SHA1_DIGEST_LENGTH);
109 		ie->flags &= ~GOT_FILEIDX_F_NO_COMMIT;
110 	} else
111 		ie->flags |= GOT_FILEIDX_F_NO_COMMIT;
112 
113 	return NULL;
114 }
115 
116 void
117 got_fileindex_entry_mark_deleted_from_disk(struct got_fileindex_entry *ie)
118 {
119 	ie->flags |= GOT_FILEIDX_F_NO_FILE_ON_DISK;
120 }
121 
122 const struct got_error *
123 got_fileindex_entry_alloc(struct got_fileindex_entry **ie,
124     const char *ondisk_path, const char *relpath, uint8_t *blob_sha1,
125     uint8_t *commit_sha1)
126 {
127 	size_t len;
128 
129 	*ie = calloc(1, sizeof(**ie));
130 	if (*ie == NULL)
131 		return got_error_from_errno("calloc");
132 
133 	(*ie)->path = strdup(relpath);
134 	if ((*ie)->path == NULL) {
135 		const struct got_error *err = got_error_from_errno("strdup");
136 		free(*ie);
137 		*ie = NULL;
138 		return err;
139 	}
140 
141 	len = strlen(relpath);
142 	if (len > GOT_FILEIDX_F_PATH_LEN)
143 		len = GOT_FILEIDX_F_PATH_LEN;
144 	(*ie)->flags |= len;
145 
146 	return got_fileindex_entry_update(*ie, ondisk_path, blob_sha1,
147 	    commit_sha1, 1);
148 }
149 
150 void
151 got_fileindex_entry_free(struct got_fileindex_entry *ie)
152 {
153 	free(ie->path);
154 	free(ie);
155 }
156 
157 size_t
158 got_fileindex_entry_path_len(const struct got_fileindex_entry *ie)
159 {
160 	return (size_t)(ie->flags & GOT_FILEIDX_F_PATH_LEN);
161 }
162 
163 uint32_t
164 got_fileindex_entry_stage_get(const struct got_fileindex_entry *ie)
165 {
166 	return ((ie->flags & GOT_FILEIDX_F_STAGE) >> GOT_FILEIDX_F_STAGE_SHIFT);
167 }
168 
169 void
170 got_fileindex_entry_stage_set(struct got_fileindex_entry *ie, uint32_t stage)
171 {
172 	ie->flags &= ~GOT_FILEIDX_F_STAGE;
173 	ie->flags |= ((stage << GOT_FILEIDX_F_STAGE_SHIFT) &
174 	    GOT_FILEIDX_F_STAGE);
175 }
176 
177 int
178 got_fileindex_entry_has_blob(struct got_fileindex_entry *ie)
179 {
180 	return (ie->flags & GOT_FILEIDX_F_NO_BLOB) == 0;
181 }
182 
183 int
184 got_fileindex_entry_has_commit(struct got_fileindex_entry *ie)
185 {
186 	return (ie->flags & GOT_FILEIDX_F_NO_COMMIT) == 0;
187 }
188 
189 int
190 got_fileindex_entry_has_file_on_disk(struct got_fileindex_entry *ie)
191 {
192 	return (ie->flags & GOT_FILEIDX_F_NO_FILE_ON_DISK) == 0;
193 }
194 
195 static const struct got_error *
196 add_entry(struct got_fileindex *fileindex, struct got_fileindex_entry *ie)
197 {
198 	if (fileindex->nentries >= GOT_FILEIDX_MAX_ENTRIES)
199 		return got_error(GOT_ERR_NO_SPACE);
200 
201 	RB_INSERT(got_fileindex_tree, &fileindex->entries, ie);
202 	fileindex->nentries++;
203 	return NULL;
204 }
205 
206 const struct got_error *
207 got_fileindex_entry_add(struct got_fileindex *fileindex,
208     struct got_fileindex_entry *ie)
209 {
210 	/* Flag this entry until it gets written out to disk. */
211 	ie->flags |= GOT_FILEIDX_F_NOT_FLUSHED;
212 
213 	return add_entry(fileindex, ie);
214 }
215 
216 void
217 got_fileindex_entry_remove(struct got_fileindex *fileindex,
218     struct got_fileindex_entry *ie)
219 {
220 	RB_REMOVE(got_fileindex_tree, &fileindex->entries, ie);
221 	fileindex->nentries--;
222 }
223 
224 struct got_fileindex_entry *
225 got_fileindex_entry_get(struct got_fileindex *fileindex, const char *path,
226     size_t path_len)
227 {
228 	struct got_fileindex_entry key;
229 	memset(&key, 0, sizeof(key));
230 	key.path = (char *)path;
231 	key.flags = (path_len & GOT_FILEIDX_F_PATH_LEN);
232 	return RB_FIND(got_fileindex_tree, &fileindex->entries, &key);
233 }
234 
235 const struct got_error *
236 got_fileindex_for_each_entry_safe(struct got_fileindex *fileindex,
237     got_fileindex_cb cb, void *cb_arg)
238 {
239 	const struct got_error *err;
240 	struct got_fileindex_entry *ie, *tmp;
241 
242 	RB_FOREACH_SAFE(ie, got_fileindex_tree, &fileindex->entries, tmp) {
243 		err = (*cb)(cb_arg, ie);
244 		if (err)
245 			return err;
246 	}
247 	return NULL;
248 }
249 
250 struct got_fileindex *
251 got_fileindex_alloc(void)
252 {
253 	struct got_fileindex *fileindex;
254 
255 	fileindex = calloc(1, sizeof(*fileindex));
256 	if (fileindex == NULL)
257 		return NULL;
258 
259 	RB_INIT(&fileindex->entries);
260 	return fileindex;
261 }
262 
263 void
264 got_fileindex_free(struct got_fileindex *fileindex)
265 {
266 	struct got_fileindex_entry *ie;
267 
268 	while ((ie = RB_MIN(got_fileindex_tree, &fileindex->entries))) {
269 		RB_REMOVE(got_fileindex_tree, &fileindex->entries, ie);
270 		got_fileindex_entry_free(ie);
271 	}
272 	free(fileindex);
273 }
274 
275 static const struct got_error *
276 write_fileindex_val64(SHA1_CTX *ctx, uint64_t val, FILE *outfile)
277 {
278 	size_t n;
279 
280 	val = htobe64(val);
281 	SHA1Update(ctx, (uint8_t *)&val, sizeof(val));
282 	n = fwrite(&val, 1, sizeof(val), outfile);
283 	if (n != sizeof(val))
284 		return got_ferror(outfile, GOT_ERR_IO);
285 	return NULL;
286 }
287 
288 static const struct got_error *
289 write_fileindex_val32(SHA1_CTX *ctx, uint32_t val, FILE *outfile)
290 {
291 	size_t n;
292 
293 	val = htobe32(val);
294 	SHA1Update(ctx, (uint8_t *)&val, sizeof(val));
295 	n = fwrite(&val, 1, sizeof(val), outfile);
296 	if (n != sizeof(val))
297 		return got_ferror(outfile, GOT_ERR_IO);
298 	return NULL;
299 }
300 
301 static const struct got_error *
302 write_fileindex_val16(SHA1_CTX *ctx, uint16_t val, FILE *outfile)
303 {
304 	size_t n;
305 
306 	val = htobe16(val);
307 	SHA1Update(ctx, (uint8_t *)&val, sizeof(val));
308 	n = fwrite(&val, 1, sizeof(val), outfile);
309 	if (n != sizeof(val))
310 		return got_ferror(outfile, GOT_ERR_IO);
311 	return NULL;
312 }
313 
314 static const struct got_error *
315 write_fileindex_path(SHA1_CTX *ctx, const char *path, FILE *outfile)
316 {
317 	size_t n, len, pad = 0;
318 	static const uint8_t zero[8] = { 0 };
319 
320 	len = strlen(path);
321 	while ((len + pad) % 8 != 0)
322 		pad++;
323 	if (pad == 0)
324 		pad = 8; /* NUL-terminate */
325 
326 	SHA1Update(ctx, path, len);
327 	n = fwrite(path, 1, len, outfile);
328 	if (n != len)
329 		return got_ferror(outfile, GOT_ERR_IO);
330 	SHA1Update(ctx, zero, pad);
331 	n = fwrite(zero, 1, pad, outfile);
332 	if (n != pad)
333 		return got_ferror(outfile, GOT_ERR_IO);
334 	return NULL;
335 }
336 
337 static const struct got_error *
338 write_fileindex_entry(SHA1_CTX *ctx, struct got_fileindex_entry *ie,
339     FILE *outfile)
340 {
341 	const struct got_error *err;
342 	size_t n;
343 	uint32_t stage;
344 
345 	err = write_fileindex_val64(ctx, ie->ctime_sec, outfile);
346 	if (err)
347 		return err;
348 	err = write_fileindex_val64(ctx, ie->ctime_nsec, outfile);
349 	if (err)
350 		return err;
351 	err = write_fileindex_val64(ctx, ie->mtime_sec, outfile);
352 	if (err)
353 		return err;
354 	err = write_fileindex_val64(ctx, ie->mtime_nsec, outfile);
355 	if (err)
356 		return err;
357 
358 	err = write_fileindex_val32(ctx, ie->uid, outfile);
359 	if (err)
360 		return err;
361 	err = write_fileindex_val32(ctx, ie->gid, outfile);
362 	if (err)
363 		return err;
364 	err = write_fileindex_val32(ctx, ie->size, outfile);
365 	if (err)
366 		return err;
367 
368 	err = write_fileindex_val16(ctx, ie->mode, outfile);
369 	if (err)
370 		return err;
371 
372 	SHA1Update(ctx, ie->blob_sha1, SHA1_DIGEST_LENGTH);
373 	n = fwrite(ie->blob_sha1, 1, SHA1_DIGEST_LENGTH, outfile);
374 	if (n != SHA1_DIGEST_LENGTH)
375 		return got_ferror(outfile, GOT_ERR_IO);
376 
377 	SHA1Update(ctx, ie->commit_sha1, SHA1_DIGEST_LENGTH);
378 	n = fwrite(ie->commit_sha1, 1, SHA1_DIGEST_LENGTH, outfile);
379 	if (n != SHA1_DIGEST_LENGTH)
380 		return got_ferror(outfile, GOT_ERR_IO);
381 
382 	err = write_fileindex_val32(ctx, ie->flags, outfile);
383 	if (err)
384 		return err;
385 
386 	err = write_fileindex_path(ctx, ie->path, outfile);
387 	if (err)
388 		return err;
389 
390 	stage = got_fileindex_entry_stage_get(ie);
391 	if (stage == GOT_FILEIDX_STAGE_MODIFY ||
392 	    stage == GOT_FILEIDX_STAGE_ADD) {
393 		SHA1Update(ctx, ie->staged_blob_sha1, SHA1_DIGEST_LENGTH);
394 		n = fwrite(ie->staged_blob_sha1, 1, SHA1_DIGEST_LENGTH,
395 		    outfile);
396 		if (n != SHA1_DIGEST_LENGTH)
397 			return got_ferror(outfile, GOT_ERR_IO);
398 	}
399 
400 	return NULL;
401 }
402 
403 const struct got_error *
404 got_fileindex_write(struct got_fileindex *fileindex, FILE *outfile)
405 {
406 	const struct got_error *err = NULL;
407 	struct got_fileindex_hdr hdr;
408 	SHA1_CTX ctx;
409 	uint8_t sha1[SHA1_DIGEST_LENGTH];
410 	size_t n;
411 	struct got_fileindex_entry *ie;
412 
413 	SHA1Init(&ctx);
414 
415 	hdr.signature = htobe32(GOT_FILE_INDEX_SIGNATURE);
416 	hdr.version = htobe32(GOT_FILE_INDEX_VERSION);
417 	hdr.nentries = htobe32(fileindex->nentries);
418 
419 	SHA1Update(&ctx, (uint8_t *)&hdr.signature, sizeof(hdr.signature));
420 	SHA1Update(&ctx, (uint8_t *)&hdr.version, sizeof(hdr.version));
421 	SHA1Update(&ctx, (uint8_t *)&hdr.nentries, sizeof(hdr.nentries));
422 	n = fwrite(&hdr.signature, 1, sizeof(hdr.signature), outfile);
423 	if (n != sizeof(hdr.signature))
424 		return got_ferror(outfile, GOT_ERR_IO);
425 	n = fwrite(&hdr.version, 1, sizeof(hdr.version), outfile);
426 	if (n != sizeof(hdr.version))
427 		return got_ferror(outfile, GOT_ERR_IO);
428 	n = fwrite(&hdr.nentries, 1, sizeof(hdr.nentries), outfile);
429 	if (n != sizeof(hdr.nentries))
430 		return got_ferror(outfile, GOT_ERR_IO);
431 
432 	RB_FOREACH(ie, got_fileindex_tree, &fileindex->entries) {
433 		ie->flags &= ~GOT_FILEIDX_F_NOT_FLUSHED;
434 		err = write_fileindex_entry(&ctx, ie, outfile);
435 		if (err)
436 			return err;
437 	}
438 
439 	SHA1Final(sha1, &ctx);
440 	n = fwrite(sha1, 1, sizeof(sha1), outfile);
441 	if (n != sizeof(sha1))
442 		return got_ferror(outfile, GOT_ERR_IO);
443 
444 	if (fflush(outfile) != 0)
445 		return got_error_from_errno("fflush");
446 
447 	return NULL;
448 }
449 
450 static const struct got_error *
451 read_fileindex_val64(uint64_t *val, SHA1_CTX *ctx, FILE *infile)
452 {
453 	size_t n;
454 
455 	n = fread(val, 1, sizeof(*val), infile);
456 	if (n != sizeof(*val))
457 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
458 	SHA1Update(ctx, (uint8_t *)val, sizeof(*val));
459 	*val = be64toh(*val);
460 	return NULL;
461 }
462 
463 static const struct got_error *
464 read_fileindex_val32(uint32_t *val, SHA1_CTX *ctx, FILE *infile)
465 {
466 	size_t n;
467 
468 	n = fread(val, 1, sizeof(*val), infile);
469 	if (n != sizeof(*val))
470 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
471 	SHA1Update(ctx, (uint8_t *)val, sizeof(*val));
472 	*val = be32toh(*val);
473 	return NULL;
474 }
475 
476 static const struct got_error *
477 read_fileindex_val16(uint16_t *val, SHA1_CTX *ctx, FILE *infile)
478 {
479 	size_t n;
480 
481 	n = fread(val, 1, sizeof(*val), infile);
482 	if (n != sizeof(*val))
483 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
484 	SHA1Update(ctx, (uint8_t *)val, sizeof(*val));
485 	*val = be16toh(*val);
486 	return NULL;
487 }
488 
489 static const struct got_error *
490 read_fileindex_path(char **path, SHA1_CTX *ctx, FILE *infile)
491 {
492 	const struct got_error *err = NULL;
493 	const size_t chunk_size = 8;
494 	size_t n, len = 0, totlen = chunk_size;
495 
496 	*path = malloc(totlen);
497 	if (*path == NULL)
498 		return got_error_from_errno("malloc");
499 
500 	do {
501 		if (len + chunk_size > totlen) {
502 			char *p = reallocarray(*path, totlen + chunk_size, 1);
503 			if (p == NULL) {
504 				err = got_error_from_errno("reallocarray");
505 				break;
506 			}
507 			totlen += chunk_size;
508 			*path = p;
509 		}
510 		n = fread(*path + len, 1, chunk_size, infile);
511 		if (n != chunk_size) {
512 			err = got_ferror(infile, GOT_ERR_FILEIDX_BAD);
513 			break;
514 		}
515 		SHA1Update(ctx, *path + len, chunk_size);
516 		len += chunk_size;
517 	} while (memchr(*path + len - chunk_size, '\0', chunk_size) == NULL);
518 
519 	if (err) {
520 		free(*path);
521 		*path = NULL;
522 	}
523 	return err;
524 }
525 
526 static const struct got_error *
527 read_fileindex_entry(struct got_fileindex_entry **iep, SHA1_CTX *ctx,
528     FILE *infile, uint32_t version)
529 {
530 	const struct got_error *err;
531 	struct got_fileindex_entry *ie;
532 	size_t n;
533 
534 	*iep = NULL;
535 
536 	ie = calloc(1, sizeof(*ie));
537 	if (ie == NULL)
538 		return got_error_from_errno("calloc");
539 
540 	err = read_fileindex_val64(&ie->ctime_sec, ctx, infile);
541 	if (err)
542 		goto done;
543 	err = read_fileindex_val64(&ie->ctime_nsec, ctx, infile);
544 	if (err)
545 		goto done;
546 	err = read_fileindex_val64(&ie->mtime_sec, ctx, infile);
547 	if (err)
548 		goto done;
549 	err = read_fileindex_val64(&ie->mtime_nsec, ctx, infile);
550 	if (err)
551 		goto done;
552 
553 	err = read_fileindex_val32(&ie->uid, ctx, infile);
554 	if (err)
555 		goto done;
556 	err = read_fileindex_val32(&ie->gid, ctx, infile);
557 	if (err)
558 		goto done;
559 	err = read_fileindex_val32(&ie->size, ctx, infile);
560 	if (err)
561 		goto done;
562 
563 	err = read_fileindex_val16(&ie->mode, ctx, infile);
564 	if (err)
565 		goto done;
566 
567 	n = fread(ie->blob_sha1, 1, SHA1_DIGEST_LENGTH, infile);
568 	if (n != SHA1_DIGEST_LENGTH) {
569 		err = got_ferror(infile, GOT_ERR_FILEIDX_BAD);
570 		goto done;
571 	}
572 	SHA1Update(ctx, ie->blob_sha1, SHA1_DIGEST_LENGTH);
573 
574 	n = fread(ie->commit_sha1, 1, SHA1_DIGEST_LENGTH, infile);
575 	if (n != SHA1_DIGEST_LENGTH) {
576 		err = got_ferror(infile, GOT_ERR_FILEIDX_BAD);
577 		goto done;
578 	}
579 	SHA1Update(ctx, ie->commit_sha1, SHA1_DIGEST_LENGTH);
580 
581 	err = read_fileindex_val32(&ie->flags, ctx, infile);
582 	if (err)
583 		goto done;
584 
585 	err = read_fileindex_path(&ie->path, ctx, infile);
586 	if (err)
587 		goto done;
588 
589 	if (version >= 2) {
590 		uint32_t stage = got_fileindex_entry_stage_get(ie);
591 		if (stage == GOT_FILEIDX_STAGE_MODIFY ||
592 		    stage == GOT_FILEIDX_STAGE_ADD) {
593 			n = fread(ie->staged_blob_sha1, 1, SHA1_DIGEST_LENGTH,
594 			    infile);
595 			if (n != SHA1_DIGEST_LENGTH) {
596 				err = got_ferror(infile, GOT_ERR_FILEIDX_BAD);
597 				goto done;
598 			}
599 			SHA1Update(ctx, ie->staged_blob_sha1, SHA1_DIGEST_LENGTH);
600 		}
601 	} else {
602 		/* GOT_FILE_INDEX_VERSION 1 does not support staging. */
603 		ie->flags &= ~GOT_FILEIDX_F_STAGE;
604 	}
605 
606 done:
607 	if (err)
608 		got_fileindex_entry_free(ie);
609 	else
610 		*iep = ie;
611 	return err;
612 }
613 
614 const struct got_error *
615 got_fileindex_read(struct got_fileindex *fileindex, FILE *infile)
616 {
617 	const struct got_error *err = NULL;
618 	struct got_fileindex_hdr hdr;
619 	SHA1_CTX ctx;
620 	struct got_fileindex_entry *ie;
621 	uint8_t sha1_expected[SHA1_DIGEST_LENGTH];
622 	uint8_t sha1[SHA1_DIGEST_LENGTH];
623 	size_t n;
624 	int i;
625 
626 	SHA1Init(&ctx);
627 
628 	n = fread(&hdr.signature, 1, sizeof(hdr.signature), infile);
629 	if (n != sizeof(hdr.signature)) {
630 		if (n == 0) /* EOF */
631 			return NULL;
632 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
633 	}
634 	n = fread(&hdr.version, 1, sizeof(hdr.version), infile);
635 	if (n != sizeof(hdr.version)) {
636 		if (n == 0) /* EOF */
637 			return NULL;
638 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
639 	}
640 	n = fread(&hdr.nentries, 1, sizeof(hdr.nentries), infile);
641 	if (n != sizeof(hdr.nentries)) {
642 		if (n == 0) /* EOF */
643 			return NULL;
644 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
645 	}
646 
647 	SHA1Update(&ctx, (uint8_t *)&hdr.signature, sizeof(hdr.signature));
648 	SHA1Update(&ctx, (uint8_t *)&hdr.version, sizeof(hdr.version));
649 	SHA1Update(&ctx, (uint8_t *)&hdr.nentries, sizeof(hdr.nentries));
650 
651 	hdr.signature = be32toh(hdr.signature);
652 	hdr.version = be32toh(hdr.version);
653 	hdr.nentries = be32toh(hdr.nentries);
654 
655 	if (hdr.signature != GOT_FILE_INDEX_SIGNATURE)
656 		return got_error(GOT_ERR_FILEIDX_SIG);
657 	if (hdr.version > GOT_FILE_INDEX_VERSION)
658 		return got_error(GOT_ERR_FILEIDX_VER);
659 
660 	for (i = 0; i < hdr.nentries; i++) {
661 		err = read_fileindex_entry(&ie, &ctx, infile, hdr.version);
662 		if (err)
663 			return err;
664 		err = add_entry(fileindex, ie);
665 		if (err)
666 			return err;
667 	}
668 
669 	n = fread(sha1_expected, 1, sizeof(sha1_expected), infile);
670 	if (n != sizeof(sha1_expected))
671 		return got_ferror(infile, GOT_ERR_FILEIDX_BAD);
672 	SHA1Final(sha1, &ctx);
673 	if (memcmp(sha1, sha1_expected, SHA1_DIGEST_LENGTH) != 0)
674 		return got_error(GOT_ERR_FILEIDX_CSUM);
675 
676 	return NULL;
677 }
678 
679 static struct got_fileindex_entry *
680 walk_fileindex(struct got_fileindex *fileindex, struct got_fileindex_entry *ie)
681 {
682 	struct got_fileindex_entry *next;
683 
684 	next = RB_NEXT(got_fileindex_tree, &fileindex->entries, ie);
685 
686 	/* Skip entries which were newly added by diff callbacks. */
687 	while (next && (next->flags & GOT_FILEIDX_F_NOT_FLUSHED))
688 		next = RB_NEXT(got_fileindex_tree, &fileindex->entries, next);
689 
690 	return next;
691 }
692 
693 static const struct got_error *
694 diff_fileindex_tree(struct got_fileindex *, struct got_fileindex_entry **,
695     const struct got_tree_entries *, const char *, const char *,
696     struct got_repository *, struct got_fileindex_diff_tree_cb *, void *);
697 
698 static const struct got_error *
699 walk_tree(struct got_tree_entry **next, struct got_fileindex *fileindex,
700     struct got_fileindex_entry **ie, struct got_tree_entry *te,
701     const char *path, const char *entry_name, struct got_repository *repo,
702     struct got_fileindex_diff_tree_cb *cb, void *cb_arg)
703 {
704 	const struct got_error *err = NULL;
705 
706 	if (S_ISDIR(te->mode)) {
707 		char *subpath;
708 		struct got_tree_object *subtree;
709 
710 		if (asprintf(&subpath, "%s%s%s", path,
711 		    path[0] == '\0' ? "" : "/", te->name) == -1)
712 			return got_error_from_errno("asprintf");
713 
714 		err = got_object_open_as_tree(&subtree, repo, te->id);
715 		if (err) {
716 			free(subpath);
717 			return err;
718 		}
719 
720 		err = diff_fileindex_tree(fileindex, ie,
721 		    got_object_tree_get_entries(subtree), subpath, entry_name,
722 		    repo, cb, cb_arg);
723 		free(subpath);
724 		got_object_tree_close(subtree);
725 		if (err)
726 			return err;
727 	}
728 
729 	*next = SIMPLEQ_NEXT(te, entry);
730 	return NULL;
731 }
732 
733 static const struct got_error *
734 diff_fileindex_tree(struct got_fileindex *fileindex,
735     struct got_fileindex_entry **ie, const struct got_tree_entries *entries,
736     const char *path, const char *entry_name, struct got_repository *repo,
737     struct got_fileindex_diff_tree_cb *cb, void *cb_arg)
738 {
739 	const struct got_error *err = NULL;
740 	struct got_tree_entry *te = NULL;
741 	size_t path_len = strlen(path);
742 	struct got_fileindex_entry *next;
743 
744 	te = SIMPLEQ_FIRST(&entries->head);
745 	while ((*ie && got_path_is_child((*ie)->path, path, path_len)) || te) {
746 		if (te && *ie) {
747 			char *te_path;
748 			int cmp;
749 			if (asprintf(&te_path, "%s/%s", path, te->name) == -1) {
750 				err = got_error_from_errno("asprintf");
751 				break;
752 			}
753 			cmp = got_path_cmp((*ie)->path, te_path,
754 			    got_fileindex_entry_path_len(*ie), strlen(te_path));
755 			free(te_path);
756 			if (cmp == 0) {
757 				if (got_path_is_child((*ie)->path, path,
758 				    path_len) && (entry_name == NULL ||
759 				    strcmp(te->name, entry_name) == 0)) {
760 					err = cb->diff_old_new(cb_arg, *ie, te,
761 					    path);
762 					if (err || entry_name)
763 						break;
764 				}
765 				*ie = walk_fileindex(fileindex, *ie);
766 				err = walk_tree(&te, fileindex, ie, te,
767 				    path, entry_name, repo, cb, cb_arg);
768 			} else if (cmp < 0) {
769 				next = walk_fileindex(fileindex, *ie);
770 				if (got_path_is_child((*ie)->path, path,
771 				    path_len) && (entry_name == NULL ||
772 				    strcmp(te->name, entry_name) == 0)) {
773 					err = cb->diff_old(cb_arg, *ie, path);
774 					if (err || entry_name)
775 						break;
776 				}
777 				*ie = next;
778 			} else {
779 				if ((entry_name == NULL ||
780 				    strcmp(te->name, entry_name) == 0)) {
781 					err = cb->diff_new(cb_arg, te, path);
782 					if (err || entry_name)
783 						break;
784 				}
785 				err = walk_tree(&te, fileindex, ie, te,
786 				    path, entry_name, repo, cb, cb_arg);
787 			}
788 			if (err)
789 				break;
790 		} else if (*ie) {
791 			next = walk_fileindex(fileindex, *ie);
792 			if (got_path_is_child((*ie)->path, path, path_len) &&
793 			    (entry_name == NULL ||
794 			    strcmp(te->name, entry_name) == 0)) {
795 				err = cb->diff_old(cb_arg, *ie, path);
796 				if (err || entry_name)
797 					break;
798 			}
799 			*ie = next;
800 		} else if (te) {
801 			if (entry_name == NULL ||
802 			    strcmp(te->name, entry_name) == 0) {
803 				err = cb->diff_new(cb_arg, te, path);
804 				if (err || entry_name)
805 					break;
806 			}
807 			err = walk_tree(&te, fileindex, ie, te, path,
808 			    entry_name, repo, cb, cb_arg);
809 			if (err)
810 				break;
811 		}
812 	}
813 
814 	return err;
815 }
816 
817 const struct got_error *
818 got_fileindex_diff_tree(struct got_fileindex *fileindex,
819     struct got_tree_object *tree, const char *path, const char *entry_name,
820     struct got_repository *repo,
821     struct got_fileindex_diff_tree_cb *cb, void *cb_arg)
822 {
823 	struct got_fileindex_entry *ie;
824 	ie = RB_MIN(got_fileindex_tree, &fileindex->entries);
825 	while (ie && !got_path_is_child(ie->path, path, strlen(path)))
826 		ie = walk_fileindex(fileindex, ie);
827 	return diff_fileindex_tree(fileindex, &ie,
828 	    got_object_tree_get_entries(tree), path, entry_name, repo,
829 	    cb, cb_arg);
830 }
831 
832 static const struct got_error *
833 diff_fileindex_dir(struct got_fileindex *, struct got_fileindex_entry **,
834     struct got_pathlist_head *, const char *, const char *,
835     struct got_repository *, struct got_fileindex_diff_dir_cb *, void *);
836 
837 static const struct got_error *
838 read_dirlist(struct got_pathlist_head *dirlist, DIR *dir, const char *path)
839 {
840 	const struct got_error *err = NULL;
841 	struct got_pathlist_entry *new = NULL;
842 	struct dirent *dep = NULL;
843 	struct dirent *de = NULL;
844 
845 	for (;;) {
846 		de = malloc(sizeof(struct dirent) + NAME_MAX + 1);
847 		if (de == NULL) {
848 			err = got_error_from_errno("malloc");
849 			break;
850 		}
851 
852 		if (readdir_r(dir, de, &dep) != 0) {
853 			err = got_error_from_errno("readdir_r");
854 			free(de);
855 			break;
856 		}
857 		if (dep == NULL) {
858 			free(de);
859 			break;
860 		}
861 
862 		if (strcmp(de->d_name, ".") == 0 ||
863 		    strcmp(de->d_name, "..") == 0 ||
864 		    (path[0] == '\0' &&
865 		    strcmp(de->d_name, GOT_WORKTREE_GOT_DIR) == 0)) {
866 			free(de);
867 			continue;
868 		}
869 
870 		err = got_pathlist_insert(&new, dirlist, de->d_name, de);
871 		if (err) {
872 			free(de);
873 			break;
874 		}
875 		if (new == NULL) {
876 			err = got_error(GOT_ERR_DIR_DUP_ENTRY);
877 			free(de);
878 			break;
879 		}
880 	}
881 
882 	return err;
883 }
884 
885 void
886 free_dirlist(struct got_pathlist_head *dirlist)
887 {
888 	struct got_pathlist_entry *dle;
889 
890 	TAILQ_FOREACH(dle, dirlist, entry)
891 		free(dle->data);
892 	got_pathlist_free(dirlist);
893 }
894 
895 static const struct got_error *
896 walk_dir(struct got_pathlist_entry **next, struct got_fileindex *fileindex,
897     struct got_fileindex_entry **ie, struct got_pathlist_entry *dle,
898     const char *path, const char *rootpath, struct got_repository *repo,
899     struct got_fileindex_diff_dir_cb *cb, void *cb_arg)
900 {
901 	const struct got_error *err = NULL;
902 	struct dirent *de = dle->data;
903 
904 	*next = NULL;
905 
906 	if (de->d_type == DT_DIR) {
907 		char *subpath;
908 		char *subdirpath;
909 		DIR *subdir;
910 		struct got_pathlist_head subdirlist;
911 
912 		TAILQ_INIT(&subdirlist);
913 
914 		if (asprintf(&subpath, "%s%s%s", path,
915 		    path[0] == '\0' ? "" : "/", de->d_name) == -1)
916 			return got_error_from_errno("asprintf");
917 
918 		if (asprintf(&subdirpath, "%s/%s", rootpath, subpath) == -1) {
919 			free(subpath);
920 			return got_error_from_errno("asprintf");
921 		}
922 
923 		subdir = opendir(subdirpath);
924 		if (subdir == NULL) {
925 			free(subpath);
926 			free(subdirpath);
927 			return got_error_from_errno2("opendir", subdirpath);
928 		}
929 
930 		err = read_dirlist(&subdirlist, subdir, subdirpath);
931 		if (err) {
932 			free(subpath);
933 			free(subdirpath);
934 			closedir(subdir);
935 			return err;
936 		}
937 		err = diff_fileindex_dir(fileindex, ie, &subdirlist, rootpath,
938 		    subpath, repo, cb, cb_arg);
939 		free(subpath);
940 		free(subdirpath);
941 		closedir(subdir);
942 		free_dirlist(&subdirlist);
943 		if (err)
944 			return err;
945 	}
946 
947 	*next = TAILQ_NEXT(dle, entry);
948 	return NULL;
949 }
950 
951 static const struct got_error *
952 diff_fileindex_dir(struct got_fileindex *fileindex,
953     struct got_fileindex_entry **ie, struct got_pathlist_head *dirlist,
954     const char *rootpath, const char *path, struct got_repository *repo,
955     struct got_fileindex_diff_dir_cb *cb, void *cb_arg)
956 {
957 	const struct got_error *err = NULL;
958 	struct dirent *de = NULL;
959 	size_t path_len = strlen(path);
960 	struct got_pathlist_entry *dle;
961 
962 	dle = TAILQ_FIRST(dirlist);
963 	while ((*ie && got_path_is_child((*ie)->path, path, path_len)) || dle) {
964 		if (dle && *ie) {
965 			char *de_path;
966 			int cmp;
967 			de = dle->data;
968 			if (asprintf(&de_path, "%s/%s", path,
969 			    de->d_name) == -1) {
970 				err = got_error_from_errno("asprintf");
971 				break;
972 			}
973 			cmp = got_path_cmp((*ie)->path, de_path,
974 			    got_fileindex_entry_path_len(*ie),
975 			    strlen(path) + 1 + de->d_namlen);
976 			free(de_path);
977 			if (cmp == 0) {
978 				err = cb->diff_old_new(cb_arg, *ie, de, path);
979 				if (err)
980 					break;
981 				*ie = walk_fileindex(fileindex, *ie);
982 				err = walk_dir(&dle, fileindex, ie, dle, path,
983 				    rootpath, repo, cb, cb_arg);
984 			} else if (cmp < 0 ) {
985 				err = cb->diff_old(cb_arg, *ie, path);
986 				if (err)
987 					break;
988 				*ie = walk_fileindex(fileindex, *ie);
989 			} else {
990 				err = cb->diff_new(cb_arg, de, path);
991 				if (err)
992 					break;
993 				err = walk_dir(&dle, fileindex, ie, dle, path,
994 				    rootpath, repo, cb, cb_arg);
995 			}
996 			if (err)
997 				break;
998 		} else if (*ie) {
999 			err = cb->diff_old(cb_arg, *ie, path);
1000 			if (err)
1001 				break;
1002 			*ie = walk_fileindex(fileindex, *ie);
1003 		} else if (dle) {
1004 			de = dle->data;
1005 			err = cb->diff_new(cb_arg, de, path);
1006 			if (err)
1007 				break;
1008 			err = walk_dir(&dle, fileindex, ie, dle, path,
1009 			    rootpath, repo, cb, cb_arg);
1010 			if (err)
1011 				break;
1012 		}
1013 	}
1014 
1015 	return err;
1016 }
1017 
1018 const struct got_error *
1019 got_fileindex_diff_dir(struct got_fileindex *fileindex, DIR *rootdir,
1020     const char *rootpath, const char *path, struct got_repository *repo,
1021     struct got_fileindex_diff_dir_cb *cb, void *cb_arg)
1022 {
1023 	const struct got_error *err;
1024 	struct got_fileindex_entry *ie;
1025 	struct got_pathlist_head dirlist;
1026 
1027 	TAILQ_INIT(&dirlist);
1028 	err = read_dirlist(&dirlist, rootdir, path);
1029 	if (err)
1030 		return err;
1031 	ie = RB_MIN(got_fileindex_tree, &fileindex->entries);
1032 	while (ie && !got_path_is_child(ie->path, path, strlen(path)))
1033 		ie = walk_fileindex(fileindex, ie);
1034 	err = diff_fileindex_dir(fileindex, &ie, &dirlist, rootpath, path,
1035 	    repo, cb, cb_arg);
1036 	free_dirlist(&dirlist);
1037 	return err;
1038 }
1039 
1040 RB_GENERATE(got_fileindex_tree, got_fileindex_entry, entry, got_fileindex_cmp);