op public repos

Blob

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