Merge branch 'rs/archive-excluded-directory'
[alt-git.git] / packfile.c
blobf69a5c8d607af191fa8ba04e84da8f02c40823ef
1 #include "cache.h"
2 #include "mru.h"
3 #include "pack.h"
4 #include "dir.h"
5 #include "mergesort.h"
6 #include "packfile.h"
7 #include "delta.h"
8 #include "list.h"
9 #include "streaming.h"
10 #include "sha1-lookup.h"
12 char *odb_pack_name(struct strbuf *buf,
13 const unsigned char *sha1,
14 const char *ext)
16 strbuf_reset(buf);
17 strbuf_addf(buf, "%s/pack/pack-%s.%s", get_object_directory(),
18 sha1_to_hex(sha1), ext);
19 return buf->buf;
22 char *sha1_pack_name(const unsigned char *sha1)
24 static struct strbuf buf = STRBUF_INIT;
25 return odb_pack_name(&buf, sha1, "pack");
28 char *sha1_pack_index_name(const unsigned char *sha1)
30 static struct strbuf buf = STRBUF_INIT;
31 return odb_pack_name(&buf, sha1, "idx");
34 static unsigned int pack_used_ctr;
35 static unsigned int pack_mmap_calls;
36 static unsigned int peak_pack_open_windows;
37 static unsigned int pack_open_windows;
38 static unsigned int pack_open_fds;
39 static unsigned int pack_max_fds;
40 static size_t peak_pack_mapped;
41 static size_t pack_mapped;
42 struct packed_git *packed_git;
43 struct mru packed_git_mru;
45 #define SZ_FMT PRIuMAX
46 static inline uintmax_t sz_fmt(size_t s) { return s; }
48 void pack_report(void)
50 fprintf(stderr,
51 "pack_report: getpagesize() = %10" SZ_FMT "\n"
52 "pack_report: core.packedGitWindowSize = %10" SZ_FMT "\n"
53 "pack_report: core.packedGitLimit = %10" SZ_FMT "\n",
54 sz_fmt(getpagesize()),
55 sz_fmt(packed_git_window_size),
56 sz_fmt(packed_git_limit));
57 fprintf(stderr,
58 "pack_report: pack_used_ctr = %10u\n"
59 "pack_report: pack_mmap_calls = %10u\n"
60 "pack_report: pack_open_windows = %10u / %10u\n"
61 "pack_report: pack_mapped = "
62 "%10" SZ_FMT " / %10" SZ_FMT "\n",
63 pack_used_ctr,
64 pack_mmap_calls,
65 pack_open_windows, peak_pack_open_windows,
66 sz_fmt(pack_mapped), sz_fmt(peak_pack_mapped));
70 * Open and mmap the index file at path, perform a couple of
71 * consistency checks, then record its information to p. Return 0 on
72 * success.
74 static int check_packed_git_idx(const char *path, struct packed_git *p)
76 void *idx_map;
77 struct pack_idx_header *hdr;
78 size_t idx_size;
79 uint32_t version, nr, i, *index;
80 int fd = git_open(path);
81 struct stat st;
83 if (fd < 0)
84 return -1;
85 if (fstat(fd, &st)) {
86 close(fd);
87 return -1;
89 idx_size = xsize_t(st.st_size);
90 if (idx_size < 4 * 256 + 20 + 20) {
91 close(fd);
92 return error("index file %s is too small", path);
94 idx_map = xmmap(NULL, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);
95 close(fd);
97 hdr = idx_map;
98 if (hdr->idx_signature == htonl(PACK_IDX_SIGNATURE)) {
99 version = ntohl(hdr->idx_version);
100 if (version < 2 || version > 2) {
101 munmap(idx_map, idx_size);
102 return error("index file %s is version %"PRIu32
103 " and is not supported by this binary"
104 " (try upgrading GIT to a newer version)",
105 path, version);
107 } else
108 version = 1;
110 nr = 0;
111 index = idx_map;
112 if (version > 1)
113 index += 2; /* skip index header */
114 for (i = 0; i < 256; i++) {
115 uint32_t n = ntohl(index[i]);
116 if (n < nr) {
117 munmap(idx_map, idx_size);
118 return error("non-monotonic index %s", path);
120 nr = n;
123 if (version == 1) {
125 * Total size:
126 * - 256 index entries 4 bytes each
127 * - 24-byte entries * nr (20-byte sha1 + 4-byte offset)
128 * - 20-byte SHA1 of the packfile
129 * - 20-byte SHA1 file checksum
131 if (idx_size != 4*256 + nr * 24 + 20 + 20) {
132 munmap(idx_map, idx_size);
133 return error("wrong index v1 file size in %s", path);
135 } else if (version == 2) {
137 * Minimum size:
138 * - 8 bytes of header
139 * - 256 index entries 4 bytes each
140 * - 20-byte sha1 entry * nr
141 * - 4-byte crc entry * nr
142 * - 4-byte offset entry * nr
143 * - 20-byte SHA1 of the packfile
144 * - 20-byte SHA1 file checksum
145 * And after the 4-byte offset table might be a
146 * variable sized table containing 8-byte entries
147 * for offsets larger than 2^31.
149 unsigned long min_size = 8 + 4*256 + nr*(20 + 4 + 4) + 20 + 20;
150 unsigned long max_size = min_size;
151 if (nr)
152 max_size += (nr - 1)*8;
153 if (idx_size < min_size || idx_size > max_size) {
154 munmap(idx_map, idx_size);
155 return error("wrong index v2 file size in %s", path);
157 if (idx_size != min_size &&
159 * make sure we can deal with large pack offsets.
160 * 31-bit signed offset won't be enough, neither
161 * 32-bit unsigned one will be.
163 (sizeof(off_t) <= 4)) {
164 munmap(idx_map, idx_size);
165 return error("pack too large for current definition of off_t in %s", path);
169 p->index_version = version;
170 p->index_data = idx_map;
171 p->index_size = idx_size;
172 p->num_objects = nr;
173 return 0;
176 int open_pack_index(struct packed_git *p)
178 char *idx_name;
179 size_t len;
180 int ret;
182 if (p->index_data)
183 return 0;
185 if (!strip_suffix(p->pack_name, ".pack", &len))
186 die("BUG: pack_name does not end in .pack");
187 idx_name = xstrfmt("%.*s.idx", (int)len, p->pack_name);
188 ret = check_packed_git_idx(idx_name, p);
189 free(idx_name);
190 return ret;
193 static struct packed_git *alloc_packed_git(int extra)
195 struct packed_git *p = xmalloc(st_add(sizeof(*p), extra));
196 memset(p, 0, sizeof(*p));
197 p->pack_fd = -1;
198 return p;
201 struct packed_git *parse_pack_index(unsigned char *sha1, const char *idx_path)
203 const char *path = sha1_pack_name(sha1);
204 size_t alloc = st_add(strlen(path), 1);
205 struct packed_git *p = alloc_packed_git(alloc);
207 memcpy(p->pack_name, path, alloc); /* includes NUL */
208 hashcpy(p->sha1, sha1);
209 if (check_packed_git_idx(idx_path, p)) {
210 free(p);
211 return NULL;
214 return p;
217 static void scan_windows(struct packed_git *p,
218 struct packed_git **lru_p,
219 struct pack_window **lru_w,
220 struct pack_window **lru_l)
222 struct pack_window *w, *w_l;
224 for (w_l = NULL, w = p->windows; w; w = w->next) {
225 if (!w->inuse_cnt) {
226 if (!*lru_w || w->last_used < (*lru_w)->last_used) {
227 *lru_p = p;
228 *lru_w = w;
229 *lru_l = w_l;
232 w_l = w;
236 static int unuse_one_window(struct packed_git *current)
238 struct packed_git *p, *lru_p = NULL;
239 struct pack_window *lru_w = NULL, *lru_l = NULL;
241 if (current)
242 scan_windows(current, &lru_p, &lru_w, &lru_l);
243 for (p = packed_git; p; p = p->next)
244 scan_windows(p, &lru_p, &lru_w, &lru_l);
245 if (lru_p) {
246 munmap(lru_w->base, lru_w->len);
247 pack_mapped -= lru_w->len;
248 if (lru_l)
249 lru_l->next = lru_w->next;
250 else
251 lru_p->windows = lru_w->next;
252 free(lru_w);
253 pack_open_windows--;
254 return 1;
256 return 0;
259 void release_pack_memory(size_t need)
261 size_t cur = pack_mapped;
262 while (need >= (cur - pack_mapped) && unuse_one_window(NULL))
263 ; /* nothing */
266 void close_pack_windows(struct packed_git *p)
268 while (p->windows) {
269 struct pack_window *w = p->windows;
271 if (w->inuse_cnt)
272 die("pack '%s' still has open windows to it",
273 p->pack_name);
274 munmap(w->base, w->len);
275 pack_mapped -= w->len;
276 pack_open_windows--;
277 p->windows = w->next;
278 free(w);
282 static int close_pack_fd(struct packed_git *p)
284 if (p->pack_fd < 0)
285 return 0;
287 close(p->pack_fd);
288 pack_open_fds--;
289 p->pack_fd = -1;
291 return 1;
294 void close_pack_index(struct packed_git *p)
296 if (p->index_data) {
297 munmap((void *)p->index_data, p->index_size);
298 p->index_data = NULL;
302 static void close_pack(struct packed_git *p)
304 close_pack_windows(p);
305 close_pack_fd(p);
306 close_pack_index(p);
309 void close_all_packs(void)
311 struct packed_git *p;
313 for (p = packed_git; p; p = p->next)
314 if (p->do_not_close)
315 die("BUG: want to close pack marked 'do-not-close'");
316 else
317 close_pack(p);
321 * The LRU pack is the one with the oldest MRU window, preferring packs
322 * with no used windows, or the oldest mtime if it has no windows allocated.
324 static void find_lru_pack(struct packed_git *p, struct packed_git **lru_p, struct pack_window **mru_w, int *accept_windows_inuse)
326 struct pack_window *w, *this_mru_w;
327 int has_windows_inuse = 0;
330 * Reject this pack if it has windows and the previously selected
331 * one does not. If this pack does not have windows, reject
332 * it if the pack file is newer than the previously selected one.
334 if (*lru_p && !*mru_w && (p->windows || p->mtime > (*lru_p)->mtime))
335 return;
337 for (w = this_mru_w = p->windows; w; w = w->next) {
339 * Reject this pack if any of its windows are in use,
340 * but the previously selected pack did not have any
341 * inuse windows. Otherwise, record that this pack
342 * has windows in use.
344 if (w->inuse_cnt) {
345 if (*accept_windows_inuse)
346 has_windows_inuse = 1;
347 else
348 return;
351 if (w->last_used > this_mru_w->last_used)
352 this_mru_w = w;
355 * Reject this pack if it has windows that have been
356 * used more recently than the previously selected pack.
357 * If the previously selected pack had windows inuse and
358 * we have not encountered a window in this pack that is
359 * inuse, skip this check since we prefer a pack with no
360 * inuse windows to one that has inuse windows.
362 if (*mru_w && *accept_windows_inuse == has_windows_inuse &&
363 this_mru_w->last_used > (*mru_w)->last_used)
364 return;
368 * Select this pack.
370 *mru_w = this_mru_w;
371 *lru_p = p;
372 *accept_windows_inuse = has_windows_inuse;
375 static int close_one_pack(void)
377 struct packed_git *p, *lru_p = NULL;
378 struct pack_window *mru_w = NULL;
379 int accept_windows_inuse = 1;
381 for (p = packed_git; p; p = p->next) {
382 if (p->pack_fd == -1)
383 continue;
384 find_lru_pack(p, &lru_p, &mru_w, &accept_windows_inuse);
387 if (lru_p)
388 return close_pack_fd(lru_p);
390 return 0;
393 static unsigned int get_max_fd_limit(void)
395 #ifdef RLIMIT_NOFILE
397 struct rlimit lim;
399 if (!getrlimit(RLIMIT_NOFILE, &lim))
400 return lim.rlim_cur;
402 #endif
404 #ifdef _SC_OPEN_MAX
406 long open_max = sysconf(_SC_OPEN_MAX);
407 if (0 < open_max)
408 return open_max;
410 * Otherwise, we got -1 for one of the two
411 * reasons:
413 * (1) sysconf() did not understand _SC_OPEN_MAX
414 * and signaled an error with -1; or
415 * (2) sysconf() said there is no limit.
417 * We _could_ clear errno before calling sysconf() to
418 * tell these two cases apart and return a huge number
419 * in the latter case to let the caller cap it to a
420 * value that is not so selfish, but letting the
421 * fallback OPEN_MAX codepath take care of these cases
422 * is a lot simpler.
425 #endif
427 #ifdef OPEN_MAX
428 return OPEN_MAX;
429 #else
430 return 1; /* see the caller ;-) */
431 #endif
435 * Do not call this directly as this leaks p->pack_fd on error return;
436 * call open_packed_git() instead.
438 static int open_packed_git_1(struct packed_git *p)
440 struct stat st;
441 struct pack_header hdr;
442 unsigned char sha1[20];
443 unsigned char *idx_sha1;
444 long fd_flag;
446 if (!p->index_data && open_pack_index(p))
447 return error("packfile %s index unavailable", p->pack_name);
449 if (!pack_max_fds) {
450 unsigned int max_fds = get_max_fd_limit();
452 /* Save 3 for stdin/stdout/stderr, 22 for work */
453 if (25 < max_fds)
454 pack_max_fds = max_fds - 25;
455 else
456 pack_max_fds = 1;
459 while (pack_max_fds <= pack_open_fds && close_one_pack())
460 ; /* nothing */
462 p->pack_fd = git_open(p->pack_name);
463 if (p->pack_fd < 0 || fstat(p->pack_fd, &st))
464 return -1;
465 pack_open_fds++;
467 /* If we created the struct before we had the pack we lack size. */
468 if (!p->pack_size) {
469 if (!S_ISREG(st.st_mode))
470 return error("packfile %s not a regular file", p->pack_name);
471 p->pack_size = st.st_size;
472 } else if (p->pack_size != st.st_size)
473 return error("packfile %s size changed", p->pack_name);
475 /* We leave these file descriptors open with sliding mmap;
476 * there is no point keeping them open across exec(), though.
478 fd_flag = fcntl(p->pack_fd, F_GETFD, 0);
479 if (fd_flag < 0)
480 return error("cannot determine file descriptor flags");
481 fd_flag |= FD_CLOEXEC;
482 if (fcntl(p->pack_fd, F_SETFD, fd_flag) == -1)
483 return error("cannot set FD_CLOEXEC");
485 /* Verify we recognize this pack file format. */
486 if (read_in_full(p->pack_fd, &hdr, sizeof(hdr)) != sizeof(hdr))
487 return error("file %s is far too short to be a packfile", p->pack_name);
488 if (hdr.hdr_signature != htonl(PACK_SIGNATURE))
489 return error("file %s is not a GIT packfile", p->pack_name);
490 if (!pack_version_ok(hdr.hdr_version))
491 return error("packfile %s is version %"PRIu32" and not"
492 " supported (try upgrading GIT to a newer version)",
493 p->pack_name, ntohl(hdr.hdr_version));
495 /* Verify the pack matches its index. */
496 if (p->num_objects != ntohl(hdr.hdr_entries))
497 return error("packfile %s claims to have %"PRIu32" objects"
498 " while index indicates %"PRIu32" objects",
499 p->pack_name, ntohl(hdr.hdr_entries),
500 p->num_objects);
501 if (lseek(p->pack_fd, p->pack_size - sizeof(sha1), SEEK_SET) == -1)
502 return error("end of packfile %s is unavailable", p->pack_name);
503 if (read_in_full(p->pack_fd, sha1, sizeof(sha1)) != sizeof(sha1))
504 return error("packfile %s signature is unavailable", p->pack_name);
505 idx_sha1 = ((unsigned char *)p->index_data) + p->index_size - 40;
506 if (hashcmp(sha1, idx_sha1))
507 return error("packfile %s does not match index", p->pack_name);
508 return 0;
511 static int open_packed_git(struct packed_git *p)
513 if (!open_packed_git_1(p))
514 return 0;
515 close_pack_fd(p);
516 return -1;
519 static int in_window(struct pack_window *win, off_t offset)
521 /* We must promise at least 20 bytes (one hash) after the
522 * offset is available from this window, otherwise the offset
523 * is not actually in this window and a different window (which
524 * has that one hash excess) must be used. This is to support
525 * the object header and delta base parsing routines below.
527 off_t win_off = win->offset;
528 return win_off <= offset
529 && (offset + 20) <= (win_off + win->len);
532 unsigned char *use_pack(struct packed_git *p,
533 struct pack_window **w_cursor,
534 off_t offset,
535 unsigned long *left)
537 struct pack_window *win = *w_cursor;
539 /* Since packfiles end in a hash of their content and it's
540 * pointless to ask for an offset into the middle of that
541 * hash, and the in_window function above wouldn't match
542 * don't allow an offset too close to the end of the file.
544 if (!p->pack_size && p->pack_fd == -1 && open_packed_git(p))
545 die("packfile %s cannot be accessed", p->pack_name);
546 if (offset > (p->pack_size - 20))
547 die("offset beyond end of packfile (truncated pack?)");
548 if (offset < 0)
549 die(_("offset before end of packfile (broken .idx?)"));
551 if (!win || !in_window(win, offset)) {
552 if (win)
553 win->inuse_cnt--;
554 for (win = p->windows; win; win = win->next) {
555 if (in_window(win, offset))
556 break;
558 if (!win) {
559 size_t window_align = packed_git_window_size / 2;
560 off_t len;
562 if (p->pack_fd == -1 && open_packed_git(p))
563 die("packfile %s cannot be accessed", p->pack_name);
565 win = xcalloc(1, sizeof(*win));
566 win->offset = (offset / window_align) * window_align;
567 len = p->pack_size - win->offset;
568 if (len > packed_git_window_size)
569 len = packed_git_window_size;
570 win->len = (size_t)len;
571 pack_mapped += win->len;
572 while (packed_git_limit < pack_mapped
573 && unuse_one_window(p))
574 ; /* nothing */
575 win->base = xmmap(NULL, win->len,
576 PROT_READ, MAP_PRIVATE,
577 p->pack_fd, win->offset);
578 if (win->base == MAP_FAILED)
579 die_errno("packfile %s cannot be mapped",
580 p->pack_name);
581 if (!win->offset && win->len == p->pack_size
582 && !p->do_not_close)
583 close_pack_fd(p);
584 pack_mmap_calls++;
585 pack_open_windows++;
586 if (pack_mapped > peak_pack_mapped)
587 peak_pack_mapped = pack_mapped;
588 if (pack_open_windows > peak_pack_open_windows)
589 peak_pack_open_windows = pack_open_windows;
590 win->next = p->windows;
591 p->windows = win;
594 if (win != *w_cursor) {
595 win->last_used = pack_used_ctr++;
596 win->inuse_cnt++;
597 *w_cursor = win;
599 offset -= win->offset;
600 if (left)
601 *left = win->len - xsize_t(offset);
602 return win->base + offset;
605 void unuse_pack(struct pack_window **w_cursor)
607 struct pack_window *w = *w_cursor;
608 if (w) {
609 w->inuse_cnt--;
610 *w_cursor = NULL;
614 static void try_to_free_pack_memory(size_t size)
616 release_pack_memory(size);
619 struct packed_git *add_packed_git(const char *path, size_t path_len, int local)
621 static int have_set_try_to_free_routine;
622 struct stat st;
623 size_t alloc;
624 struct packed_git *p;
626 if (!have_set_try_to_free_routine) {
627 have_set_try_to_free_routine = 1;
628 set_try_to_free_routine(try_to_free_pack_memory);
632 * Make sure a corresponding .pack file exists and that
633 * the index looks sane.
635 if (!strip_suffix_mem(path, &path_len, ".idx"))
636 return NULL;
639 * ".pack" is long enough to hold any suffix we're adding (and
640 * the use xsnprintf double-checks that)
642 alloc = st_add3(path_len, strlen(".pack"), 1);
643 p = alloc_packed_git(alloc);
644 memcpy(p->pack_name, path, path_len);
646 xsnprintf(p->pack_name + path_len, alloc - path_len, ".keep");
647 if (!access(p->pack_name, F_OK))
648 p->pack_keep = 1;
650 xsnprintf(p->pack_name + path_len, alloc - path_len, ".pack");
651 if (stat(p->pack_name, &st) || !S_ISREG(st.st_mode)) {
652 free(p);
653 return NULL;
656 /* ok, it looks sane as far as we can check without
657 * actually mapping the pack file.
659 p->pack_size = st.st_size;
660 p->pack_local = local;
661 p->mtime = st.st_mtime;
662 if (path_len < 40 || get_sha1_hex(path + path_len - 40, p->sha1))
663 hashclr(p->sha1);
664 return p;
667 void install_packed_git(struct packed_git *pack)
669 if (pack->pack_fd != -1)
670 pack_open_fds++;
672 pack->next = packed_git;
673 packed_git = pack;
676 void (*report_garbage)(unsigned seen_bits, const char *path);
678 static void report_helper(const struct string_list *list,
679 int seen_bits, int first, int last)
681 if (seen_bits == (PACKDIR_FILE_PACK|PACKDIR_FILE_IDX))
682 return;
684 for (; first < last; first++)
685 report_garbage(seen_bits, list->items[first].string);
688 static void report_pack_garbage(struct string_list *list)
690 int i, baselen = -1, first = 0, seen_bits = 0;
692 if (!report_garbage)
693 return;
695 string_list_sort(list);
697 for (i = 0; i < list->nr; i++) {
698 const char *path = list->items[i].string;
699 if (baselen != -1 &&
700 strncmp(path, list->items[first].string, baselen)) {
701 report_helper(list, seen_bits, first, i);
702 baselen = -1;
703 seen_bits = 0;
705 if (baselen == -1) {
706 const char *dot = strrchr(path, '.');
707 if (!dot) {
708 report_garbage(PACKDIR_FILE_GARBAGE, path);
709 continue;
711 baselen = dot - path + 1;
712 first = i;
714 if (!strcmp(path + baselen, "pack"))
715 seen_bits |= 1;
716 else if (!strcmp(path + baselen, "idx"))
717 seen_bits |= 2;
719 report_helper(list, seen_bits, first, list->nr);
722 static void prepare_packed_git_one(char *objdir, int local)
724 struct strbuf path = STRBUF_INIT;
725 size_t dirnamelen;
726 DIR *dir;
727 struct dirent *de;
728 struct string_list garbage = STRING_LIST_INIT_DUP;
730 strbuf_addstr(&path, objdir);
731 strbuf_addstr(&path, "/pack");
732 dir = opendir(path.buf);
733 if (!dir) {
734 if (errno != ENOENT)
735 error_errno("unable to open object pack directory: %s",
736 path.buf);
737 strbuf_release(&path);
738 return;
740 strbuf_addch(&path, '/');
741 dirnamelen = path.len;
742 while ((de = readdir(dir)) != NULL) {
743 struct packed_git *p;
744 size_t base_len;
746 if (is_dot_or_dotdot(de->d_name))
747 continue;
749 strbuf_setlen(&path, dirnamelen);
750 strbuf_addstr(&path, de->d_name);
752 base_len = path.len;
753 if (strip_suffix_mem(path.buf, &base_len, ".idx")) {
754 /* Don't reopen a pack we already have. */
755 for (p = packed_git; p; p = p->next) {
756 size_t len;
757 if (strip_suffix(p->pack_name, ".pack", &len) &&
758 len == base_len &&
759 !memcmp(p->pack_name, path.buf, len))
760 break;
762 if (p == NULL &&
764 * See if it really is a valid .idx file with
765 * corresponding .pack file that we can map.
767 (p = add_packed_git(path.buf, path.len, local)) != NULL)
768 install_packed_git(p);
771 if (!report_garbage)
772 continue;
774 if (ends_with(de->d_name, ".idx") ||
775 ends_with(de->d_name, ".pack") ||
776 ends_with(de->d_name, ".bitmap") ||
777 ends_with(de->d_name, ".keep"))
778 string_list_append(&garbage, path.buf);
779 else
780 report_garbage(PACKDIR_FILE_GARBAGE, path.buf);
782 closedir(dir);
783 report_pack_garbage(&garbage);
784 string_list_clear(&garbage, 0);
785 strbuf_release(&path);
788 static int approximate_object_count_valid;
791 * Give a fast, rough count of the number of objects in the repository. This
792 * ignores loose objects completely. If you have a lot of them, then either
793 * you should repack because your performance will be awful, or they are
794 * all unreachable objects about to be pruned, in which case they're not really
795 * interesting as a measure of repo size in the first place.
797 unsigned long approximate_object_count(void)
799 static unsigned long count;
800 if (!approximate_object_count_valid) {
801 struct packed_git *p;
803 prepare_packed_git();
804 count = 0;
805 for (p = packed_git; p; p = p->next) {
806 if (open_pack_index(p))
807 continue;
808 count += p->num_objects;
811 return count;
814 static void *get_next_packed_git(const void *p)
816 return ((const struct packed_git *)p)->next;
819 static void set_next_packed_git(void *p, void *next)
821 ((struct packed_git *)p)->next = next;
824 static int sort_pack(const void *a_, const void *b_)
826 const struct packed_git *a = a_;
827 const struct packed_git *b = b_;
828 int st;
831 * Local packs tend to contain objects specific to our
832 * variant of the project than remote ones. In addition,
833 * remote ones could be on a network mounted filesystem.
834 * Favor local ones for these reasons.
836 st = a->pack_local - b->pack_local;
837 if (st)
838 return -st;
841 * Younger packs tend to contain more recent objects,
842 * and more recent objects tend to get accessed more
843 * often.
845 if (a->mtime < b->mtime)
846 return 1;
847 else if (a->mtime == b->mtime)
848 return 0;
849 return -1;
852 static void rearrange_packed_git(void)
854 packed_git = llist_mergesort(packed_git, get_next_packed_git,
855 set_next_packed_git, sort_pack);
858 static void prepare_packed_git_mru(void)
860 struct packed_git *p;
862 mru_clear(&packed_git_mru);
863 for (p = packed_git; p; p = p->next)
864 mru_append(&packed_git_mru, p);
867 static int prepare_packed_git_run_once = 0;
868 void prepare_packed_git(void)
870 struct alternate_object_database *alt;
872 if (prepare_packed_git_run_once)
873 return;
874 prepare_packed_git_one(get_object_directory(), 1);
875 prepare_alt_odb();
876 for (alt = alt_odb_list; alt; alt = alt->next)
877 prepare_packed_git_one(alt->path, 0);
878 rearrange_packed_git();
879 prepare_packed_git_mru();
880 prepare_packed_git_run_once = 1;
883 void reprepare_packed_git(void)
885 approximate_object_count_valid = 0;
886 prepare_packed_git_run_once = 0;
887 prepare_packed_git();
890 unsigned long unpack_object_header_buffer(const unsigned char *buf,
891 unsigned long len, enum object_type *type, unsigned long *sizep)
893 unsigned shift;
894 unsigned long size, c;
895 unsigned long used = 0;
897 c = buf[used++];
898 *type = (c >> 4) & 7;
899 size = c & 15;
900 shift = 4;
901 while (c & 0x80) {
902 if (len <= used || bitsizeof(long) <= shift) {
903 error("bad object header");
904 size = used = 0;
905 break;
907 c = buf[used++];
908 size += (c & 0x7f) << shift;
909 shift += 7;
911 *sizep = size;
912 return used;
915 unsigned long get_size_from_delta(struct packed_git *p,
916 struct pack_window **w_curs,
917 off_t curpos)
919 const unsigned char *data;
920 unsigned char delta_head[20], *in;
921 git_zstream stream;
922 int st;
924 memset(&stream, 0, sizeof(stream));
925 stream.next_out = delta_head;
926 stream.avail_out = sizeof(delta_head);
928 git_inflate_init(&stream);
929 do {
930 in = use_pack(p, w_curs, curpos, &stream.avail_in);
931 stream.next_in = in;
932 st = git_inflate(&stream, Z_FINISH);
933 curpos += stream.next_in - in;
934 } while ((st == Z_OK || st == Z_BUF_ERROR) &&
935 stream.total_out < sizeof(delta_head));
936 git_inflate_end(&stream);
937 if ((st != Z_STREAM_END) && stream.total_out != sizeof(delta_head)) {
938 error("delta data unpack-initial failed");
939 return 0;
942 /* Examine the initial part of the delta to figure out
943 * the result size.
945 data = delta_head;
947 /* ignore base size */
948 get_delta_hdr_size(&data, delta_head+sizeof(delta_head));
950 /* Read the result size */
951 return get_delta_hdr_size(&data, delta_head+sizeof(delta_head));
954 int unpack_object_header(struct packed_git *p,
955 struct pack_window **w_curs,
956 off_t *curpos,
957 unsigned long *sizep)
959 unsigned char *base;
960 unsigned long left;
961 unsigned long used;
962 enum object_type type;
964 /* use_pack() assures us we have [base, base + 20) available
965 * as a range that we can look at. (Its actually the hash
966 * size that is assured.) With our object header encoding
967 * the maximum deflated object size is 2^137, which is just
968 * insane, so we know won't exceed what we have been given.
970 base = use_pack(p, w_curs, *curpos, &left);
971 used = unpack_object_header_buffer(base, left, &type, sizep);
972 if (!used) {
973 type = OBJ_BAD;
974 } else
975 *curpos += used;
977 return type;
980 void mark_bad_packed_object(struct packed_git *p, const unsigned char *sha1)
982 unsigned i;
983 for (i = 0; i < p->num_bad_objects; i++)
984 if (!hashcmp(sha1, p->bad_object_sha1 + GIT_SHA1_RAWSZ * i))
985 return;
986 p->bad_object_sha1 = xrealloc(p->bad_object_sha1,
987 st_mult(GIT_MAX_RAWSZ,
988 st_add(p->num_bad_objects, 1)));
989 hashcpy(p->bad_object_sha1 + GIT_SHA1_RAWSZ * p->num_bad_objects, sha1);
990 p->num_bad_objects++;
993 const struct packed_git *has_packed_and_bad(const unsigned char *sha1)
995 struct packed_git *p;
996 unsigned i;
998 for (p = packed_git; p; p = p->next)
999 for (i = 0; i < p->num_bad_objects; i++)
1000 if (!hashcmp(sha1, p->bad_object_sha1 + 20 * i))
1001 return p;
1002 return NULL;
1005 static off_t get_delta_base(struct packed_git *p,
1006 struct pack_window **w_curs,
1007 off_t *curpos,
1008 enum object_type type,
1009 off_t delta_obj_offset)
1011 unsigned char *base_info = use_pack(p, w_curs, *curpos, NULL);
1012 off_t base_offset;
1014 /* use_pack() assured us we have [base_info, base_info + 20)
1015 * as a range that we can look at without walking off the
1016 * end of the mapped window. Its actually the hash size
1017 * that is assured. An OFS_DELTA longer than the hash size
1018 * is stupid, as then a REF_DELTA would be smaller to store.
1020 if (type == OBJ_OFS_DELTA) {
1021 unsigned used = 0;
1022 unsigned char c = base_info[used++];
1023 base_offset = c & 127;
1024 while (c & 128) {
1025 base_offset += 1;
1026 if (!base_offset || MSB(base_offset, 7))
1027 return 0; /* overflow */
1028 c = base_info[used++];
1029 base_offset = (base_offset << 7) + (c & 127);
1031 base_offset = delta_obj_offset - base_offset;
1032 if (base_offset <= 0 || base_offset >= delta_obj_offset)
1033 return 0; /* out of bound */
1034 *curpos += used;
1035 } else if (type == OBJ_REF_DELTA) {
1036 /* The base entry _must_ be in the same pack */
1037 base_offset = find_pack_entry_one(base_info, p);
1038 *curpos += 20;
1039 } else
1040 die("I am totally screwed");
1041 return base_offset;
1045 * Like get_delta_base above, but we return the sha1 instead of the pack
1046 * offset. This means it is cheaper for REF deltas (we do not have to do
1047 * the final object lookup), but more expensive for OFS deltas (we
1048 * have to load the revidx to convert the offset back into a sha1).
1050 static const unsigned char *get_delta_base_sha1(struct packed_git *p,
1051 struct pack_window **w_curs,
1052 off_t curpos,
1053 enum object_type type,
1054 off_t delta_obj_offset)
1056 if (type == OBJ_REF_DELTA) {
1057 unsigned char *base = use_pack(p, w_curs, curpos, NULL);
1058 return base;
1059 } else if (type == OBJ_OFS_DELTA) {
1060 struct revindex_entry *revidx;
1061 off_t base_offset = get_delta_base(p, w_curs, &curpos,
1062 type, delta_obj_offset);
1064 if (!base_offset)
1065 return NULL;
1067 revidx = find_pack_revindex(p, base_offset);
1068 if (!revidx)
1069 return NULL;
1071 return nth_packed_object_sha1(p, revidx->nr);
1072 } else
1073 return NULL;
1076 static int retry_bad_packed_offset(struct packed_git *p, off_t obj_offset)
1078 int type;
1079 struct revindex_entry *revidx;
1080 const unsigned char *sha1;
1081 revidx = find_pack_revindex(p, obj_offset);
1082 if (!revidx)
1083 return OBJ_BAD;
1084 sha1 = nth_packed_object_sha1(p, revidx->nr);
1085 mark_bad_packed_object(p, sha1);
1086 type = sha1_object_info(sha1, NULL);
1087 if (type <= OBJ_NONE)
1088 return OBJ_BAD;
1089 return type;
1092 #define POI_STACK_PREALLOC 64
1094 static enum object_type packed_to_object_type(struct packed_git *p,
1095 off_t obj_offset,
1096 enum object_type type,
1097 struct pack_window **w_curs,
1098 off_t curpos)
1100 off_t small_poi_stack[POI_STACK_PREALLOC];
1101 off_t *poi_stack = small_poi_stack;
1102 int poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;
1104 while (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
1105 off_t base_offset;
1106 unsigned long size;
1107 /* Push the object we're going to leave behind */
1108 if (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {
1109 poi_stack_alloc = alloc_nr(poi_stack_nr);
1110 ALLOC_ARRAY(poi_stack, poi_stack_alloc);
1111 memcpy(poi_stack, small_poi_stack, sizeof(off_t)*poi_stack_nr);
1112 } else {
1113 ALLOC_GROW(poi_stack, poi_stack_nr+1, poi_stack_alloc);
1115 poi_stack[poi_stack_nr++] = obj_offset;
1116 /* If parsing the base offset fails, just unwind */
1117 base_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);
1118 if (!base_offset)
1119 goto unwind;
1120 curpos = obj_offset = base_offset;
1121 type = unpack_object_header(p, w_curs, &curpos, &size);
1122 if (type <= OBJ_NONE) {
1123 /* If getting the base itself fails, we first
1124 * retry the base, otherwise unwind */
1125 type = retry_bad_packed_offset(p, base_offset);
1126 if (type > OBJ_NONE)
1127 goto out;
1128 goto unwind;
1132 switch (type) {
1133 case OBJ_BAD:
1134 case OBJ_COMMIT:
1135 case OBJ_TREE:
1136 case OBJ_BLOB:
1137 case OBJ_TAG:
1138 break;
1139 default:
1140 error("unknown object type %i at offset %"PRIuMAX" in %s",
1141 type, (uintmax_t)obj_offset, p->pack_name);
1142 type = OBJ_BAD;
1145 out:
1146 if (poi_stack != small_poi_stack)
1147 free(poi_stack);
1148 return type;
1150 unwind:
1151 while (poi_stack_nr) {
1152 obj_offset = poi_stack[--poi_stack_nr];
1153 type = retry_bad_packed_offset(p, obj_offset);
1154 if (type > OBJ_NONE)
1155 goto out;
1157 type = OBJ_BAD;
1158 goto out;
1161 static struct hashmap delta_base_cache;
1162 static size_t delta_base_cached;
1164 static LIST_HEAD(delta_base_cache_lru);
1166 struct delta_base_cache_key {
1167 struct packed_git *p;
1168 off_t base_offset;
1171 struct delta_base_cache_entry {
1172 struct hashmap hash;
1173 struct delta_base_cache_key key;
1174 struct list_head lru;
1175 void *data;
1176 unsigned long size;
1177 enum object_type type;
1180 static unsigned int pack_entry_hash(struct packed_git *p, off_t base_offset)
1182 unsigned int hash;
1184 hash = (unsigned int)(intptr_t)p + (unsigned int)base_offset;
1185 hash += (hash >> 8) + (hash >> 16);
1186 return hash;
1189 static struct delta_base_cache_entry *
1190 get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)
1192 struct hashmap_entry entry;
1193 struct delta_base_cache_key key;
1195 if (!delta_base_cache.cmpfn)
1196 return NULL;
1198 hashmap_entry_init(&entry, pack_entry_hash(p, base_offset));
1199 key.p = p;
1200 key.base_offset = base_offset;
1201 return hashmap_get(&delta_base_cache, &entry, &key);
1204 static int delta_base_cache_key_eq(const struct delta_base_cache_key *a,
1205 const struct delta_base_cache_key *b)
1207 return a->p == b->p && a->base_offset == b->base_offset;
1210 static int delta_base_cache_hash_cmp(const void *unused_cmp_data,
1211 const void *va, const void *vb,
1212 const void *vkey)
1214 const struct delta_base_cache_entry *a = va, *b = vb;
1215 const struct delta_base_cache_key *key = vkey;
1216 if (key)
1217 return !delta_base_cache_key_eq(&a->key, key);
1218 else
1219 return !delta_base_cache_key_eq(&a->key, &b->key);
1222 static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
1224 return !!get_delta_base_cache_entry(p, base_offset);
1228 * Remove the entry from the cache, but do _not_ free the associated
1229 * entry data. The caller takes ownership of the "data" buffer, and
1230 * should copy out any fields it wants before detaching.
1232 static void detach_delta_base_cache_entry(struct delta_base_cache_entry *ent)
1234 hashmap_remove(&delta_base_cache, ent, &ent->key);
1235 list_del(&ent->lru);
1236 delta_base_cached -= ent->size;
1237 free(ent);
1240 static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
1241 unsigned long *base_size, enum object_type *type)
1243 struct delta_base_cache_entry *ent;
1245 ent = get_delta_base_cache_entry(p, base_offset);
1246 if (!ent)
1247 return unpack_entry(p, base_offset, type, base_size);
1249 if (type)
1250 *type = ent->type;
1251 if (base_size)
1252 *base_size = ent->size;
1253 return xmemdupz(ent->data, ent->size);
1256 static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)
1258 free(ent->data);
1259 detach_delta_base_cache_entry(ent);
1262 void clear_delta_base_cache(void)
1264 struct list_head *lru, *tmp;
1265 list_for_each_safe(lru, tmp, &delta_base_cache_lru) {
1266 struct delta_base_cache_entry *entry =
1267 list_entry(lru, struct delta_base_cache_entry, lru);
1268 release_delta_base_cache(entry);
1272 static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
1273 void *base, unsigned long base_size, enum object_type type)
1275 struct delta_base_cache_entry *ent = xmalloc(sizeof(*ent));
1276 struct list_head *lru, *tmp;
1278 delta_base_cached += base_size;
1280 list_for_each_safe(lru, tmp, &delta_base_cache_lru) {
1281 struct delta_base_cache_entry *f =
1282 list_entry(lru, struct delta_base_cache_entry, lru);
1283 if (delta_base_cached <= delta_base_cache_limit)
1284 break;
1285 release_delta_base_cache(f);
1288 ent->key.p = p;
1289 ent->key.base_offset = base_offset;
1290 ent->type = type;
1291 ent->data = base;
1292 ent->size = base_size;
1293 list_add_tail(&ent->lru, &delta_base_cache_lru);
1295 if (!delta_base_cache.cmpfn)
1296 hashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, NULL, 0);
1297 hashmap_entry_init(ent, pack_entry_hash(p, base_offset));
1298 hashmap_add(&delta_base_cache, ent);
1301 int packed_object_info(struct packed_git *p, off_t obj_offset,
1302 struct object_info *oi)
1304 struct pack_window *w_curs = NULL;
1305 unsigned long size;
1306 off_t curpos = obj_offset;
1307 enum object_type type;
1310 * We always get the representation type, but only convert it to
1311 * a "real" type later if the caller is interested.
1313 if (oi->contentp) {
1314 *oi->contentp = cache_or_unpack_entry(p, obj_offset, oi->sizep,
1315 &type);
1316 if (!*oi->contentp)
1317 type = OBJ_BAD;
1318 } else {
1319 type = unpack_object_header(p, &w_curs, &curpos, &size);
1322 if (!oi->contentp && oi->sizep) {
1323 if (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
1324 off_t tmp_pos = curpos;
1325 off_t base_offset = get_delta_base(p, &w_curs, &tmp_pos,
1326 type, obj_offset);
1327 if (!base_offset) {
1328 type = OBJ_BAD;
1329 goto out;
1331 *oi->sizep = get_size_from_delta(p, &w_curs, tmp_pos);
1332 if (*oi->sizep == 0) {
1333 type = OBJ_BAD;
1334 goto out;
1336 } else {
1337 *oi->sizep = size;
1341 if (oi->disk_sizep) {
1342 struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
1343 *oi->disk_sizep = revidx[1].offset - obj_offset;
1346 if (oi->typep || oi->typename) {
1347 enum object_type ptot;
1348 ptot = packed_to_object_type(p, obj_offset, type, &w_curs,
1349 curpos);
1350 if (oi->typep)
1351 *oi->typep = ptot;
1352 if (oi->typename) {
1353 const char *tn = typename(ptot);
1354 if (tn)
1355 strbuf_addstr(oi->typename, tn);
1357 if (ptot < 0) {
1358 type = OBJ_BAD;
1359 goto out;
1363 if (oi->delta_base_sha1) {
1364 if (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
1365 const unsigned char *base;
1367 base = get_delta_base_sha1(p, &w_curs, curpos,
1368 type, obj_offset);
1369 if (!base) {
1370 type = OBJ_BAD;
1371 goto out;
1374 hashcpy(oi->delta_base_sha1, base);
1375 } else
1376 hashclr(oi->delta_base_sha1);
1379 oi->whence = in_delta_base_cache(p, obj_offset) ? OI_DBCACHED :
1380 OI_PACKED;
1382 out:
1383 unuse_pack(&w_curs);
1384 return type;
1387 static void *unpack_compressed_entry(struct packed_git *p,
1388 struct pack_window **w_curs,
1389 off_t curpos,
1390 unsigned long size)
1392 int st;
1393 git_zstream stream;
1394 unsigned char *buffer, *in;
1396 buffer = xmallocz_gently(size);
1397 if (!buffer)
1398 return NULL;
1399 memset(&stream, 0, sizeof(stream));
1400 stream.next_out = buffer;
1401 stream.avail_out = size + 1;
1403 git_inflate_init(&stream);
1404 do {
1405 in = use_pack(p, w_curs, curpos, &stream.avail_in);
1406 stream.next_in = in;
1407 st = git_inflate(&stream, Z_FINISH);
1408 if (!stream.avail_out)
1409 break; /* the payload is larger than it should be */
1410 curpos += stream.next_in - in;
1411 } while (st == Z_OK || st == Z_BUF_ERROR);
1412 git_inflate_end(&stream);
1413 if ((st != Z_STREAM_END) || stream.total_out != size) {
1414 free(buffer);
1415 return NULL;
1418 return buffer;
1421 static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
1423 static struct trace_key pack_access = TRACE_KEY_INIT(PACK_ACCESS);
1424 trace_printf_key(&pack_access, "%s %"PRIuMAX"\n",
1425 p->pack_name, (uintmax_t)obj_offset);
1428 int do_check_packed_object_crc;
1430 #define UNPACK_ENTRY_STACK_PREALLOC 64
1431 struct unpack_entry_stack_ent {
1432 off_t obj_offset;
1433 off_t curpos;
1434 unsigned long size;
1437 static void *read_object(const unsigned char *sha1, enum object_type *type,
1438 unsigned long *size)
1440 struct object_info oi = OBJECT_INFO_INIT;
1441 void *content;
1442 oi.typep = type;
1443 oi.sizep = size;
1444 oi.contentp = &content;
1446 if (sha1_object_info_extended(sha1, &oi, 0) < 0)
1447 return NULL;
1448 return content;
1451 void *unpack_entry(struct packed_git *p, off_t obj_offset,
1452 enum object_type *final_type, unsigned long *final_size)
1454 struct pack_window *w_curs = NULL;
1455 off_t curpos = obj_offset;
1456 void *data = NULL;
1457 unsigned long size;
1458 enum object_type type;
1459 struct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];
1460 struct unpack_entry_stack_ent *delta_stack = small_delta_stack;
1461 int delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;
1462 int base_from_cache = 0;
1464 write_pack_access_log(p, obj_offset);
1466 /* PHASE 1: drill down to the innermost base object */
1467 for (;;) {
1468 off_t base_offset;
1469 int i;
1470 struct delta_base_cache_entry *ent;
1472 ent = get_delta_base_cache_entry(p, curpos);
1473 if (ent) {
1474 type = ent->type;
1475 data = ent->data;
1476 size = ent->size;
1477 detach_delta_base_cache_entry(ent);
1478 base_from_cache = 1;
1479 break;
1482 if (do_check_packed_object_crc && p->index_version > 1) {
1483 struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
1484 off_t len = revidx[1].offset - obj_offset;
1485 if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
1486 const unsigned char *sha1 =
1487 nth_packed_object_sha1(p, revidx->nr);
1488 error("bad packed object CRC for %s",
1489 sha1_to_hex(sha1));
1490 mark_bad_packed_object(p, sha1);
1491 data = NULL;
1492 goto out;
1496 type = unpack_object_header(p, &w_curs, &curpos, &size);
1497 if (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)
1498 break;
1500 base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
1501 if (!base_offset) {
1502 error("failed to validate delta base reference "
1503 "at offset %"PRIuMAX" from %s",
1504 (uintmax_t)curpos, p->pack_name);
1505 /* bail to phase 2, in hopes of recovery */
1506 data = NULL;
1507 break;
1510 /* push object, proceed to base */
1511 if (delta_stack_nr >= delta_stack_alloc
1512 && delta_stack == small_delta_stack) {
1513 delta_stack_alloc = alloc_nr(delta_stack_nr);
1514 ALLOC_ARRAY(delta_stack, delta_stack_alloc);
1515 memcpy(delta_stack, small_delta_stack,
1516 sizeof(*delta_stack)*delta_stack_nr);
1517 } else {
1518 ALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);
1520 i = delta_stack_nr++;
1521 delta_stack[i].obj_offset = obj_offset;
1522 delta_stack[i].curpos = curpos;
1523 delta_stack[i].size = size;
1525 curpos = obj_offset = base_offset;
1528 /* PHASE 2: handle the base */
1529 switch (type) {
1530 case OBJ_OFS_DELTA:
1531 case OBJ_REF_DELTA:
1532 if (data)
1533 die("BUG: unpack_entry: left loop at a valid delta");
1534 break;
1535 case OBJ_COMMIT:
1536 case OBJ_TREE:
1537 case OBJ_BLOB:
1538 case OBJ_TAG:
1539 if (!base_from_cache)
1540 data = unpack_compressed_entry(p, &w_curs, curpos, size);
1541 break;
1542 default:
1543 data = NULL;
1544 error("unknown object type %i at offset %"PRIuMAX" in %s",
1545 type, (uintmax_t)obj_offset, p->pack_name);
1548 /* PHASE 3: apply deltas in order */
1550 /* invariants:
1551 * 'data' holds the base data, or NULL if there was corruption
1553 while (delta_stack_nr) {
1554 void *delta_data;
1555 void *base = data;
1556 void *external_base = NULL;
1557 unsigned long delta_size, base_size = size;
1558 int i;
1560 data = NULL;
1562 if (base)
1563 add_delta_base_cache(p, obj_offset, base, base_size, type);
1565 if (!base) {
1567 * We're probably in deep shit, but let's try to fetch
1568 * the required base anyway from another pack or loose.
1569 * This is costly but should happen only in the presence
1570 * of a corrupted pack, and is better than failing outright.
1572 struct revindex_entry *revidx;
1573 const unsigned char *base_sha1;
1574 revidx = find_pack_revindex(p, obj_offset);
1575 if (revidx) {
1576 base_sha1 = nth_packed_object_sha1(p, revidx->nr);
1577 error("failed to read delta base object %s"
1578 " at offset %"PRIuMAX" from %s",
1579 sha1_to_hex(base_sha1), (uintmax_t)obj_offset,
1580 p->pack_name);
1581 mark_bad_packed_object(p, base_sha1);
1582 base = read_object(base_sha1, &type, &base_size);
1583 external_base = base;
1587 i = --delta_stack_nr;
1588 obj_offset = delta_stack[i].obj_offset;
1589 curpos = delta_stack[i].curpos;
1590 delta_size = delta_stack[i].size;
1592 if (!base)
1593 continue;
1595 delta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);
1597 if (!delta_data) {
1598 error("failed to unpack compressed delta "
1599 "at offset %"PRIuMAX" from %s",
1600 (uintmax_t)curpos, p->pack_name);
1601 data = NULL;
1602 free(external_base);
1603 continue;
1606 data = patch_delta(base, base_size,
1607 delta_data, delta_size,
1608 &size);
1611 * We could not apply the delta; warn the user, but keep going.
1612 * Our failure will be noticed either in the next iteration of
1613 * the loop, or if this is the final delta, in the caller when
1614 * we return NULL. Those code paths will take care of making
1615 * a more explicit warning and retrying with another copy of
1616 * the object.
1618 if (!data)
1619 error("failed to apply delta");
1621 free(delta_data);
1622 free(external_base);
1625 if (final_type)
1626 *final_type = type;
1627 if (final_size)
1628 *final_size = size;
1630 out:
1631 unuse_pack(&w_curs);
1633 if (delta_stack != small_delta_stack)
1634 free(delta_stack);
1636 return data;
1639 const unsigned char *nth_packed_object_sha1(struct packed_git *p,
1640 uint32_t n)
1642 const unsigned char *index = p->index_data;
1643 if (!index) {
1644 if (open_pack_index(p))
1645 return NULL;
1646 index = p->index_data;
1648 if (n >= p->num_objects)
1649 return NULL;
1650 index += 4 * 256;
1651 if (p->index_version == 1) {
1652 return index + 24 * n + 4;
1653 } else {
1654 index += 8;
1655 return index + 20 * n;
1659 const struct object_id *nth_packed_object_oid(struct object_id *oid,
1660 struct packed_git *p,
1661 uint32_t n)
1663 const unsigned char *hash = nth_packed_object_sha1(p, n);
1664 if (!hash)
1665 return NULL;
1666 hashcpy(oid->hash, hash);
1667 return oid;
1670 void check_pack_index_ptr(const struct packed_git *p, const void *vptr)
1672 const unsigned char *ptr = vptr;
1673 const unsigned char *start = p->index_data;
1674 const unsigned char *end = start + p->index_size;
1675 if (ptr < start)
1676 die(_("offset before start of pack index for %s (corrupt index?)"),
1677 p->pack_name);
1678 /* No need to check for underflow; .idx files must be at least 8 bytes */
1679 if (ptr >= end - 8)
1680 die(_("offset beyond end of pack index for %s (truncated index?)"),
1681 p->pack_name);
1684 off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)
1686 const unsigned char *index = p->index_data;
1687 index += 4 * 256;
1688 if (p->index_version == 1) {
1689 return ntohl(*((uint32_t *)(index + 24 * n)));
1690 } else {
1691 uint32_t off;
1692 index += 8 + p->num_objects * (20 + 4);
1693 off = ntohl(*((uint32_t *)(index + 4 * n)));
1694 if (!(off & 0x80000000))
1695 return off;
1696 index += p->num_objects * 4 + (off & 0x7fffffff) * 8;
1697 check_pack_index_ptr(p, index);
1698 return (((uint64_t)ntohl(*((uint32_t *)(index + 0)))) << 32) |
1699 ntohl(*((uint32_t *)(index + 4)));
1703 off_t find_pack_entry_one(const unsigned char *sha1,
1704 struct packed_git *p)
1706 const uint32_t *level1_ofs = p->index_data;
1707 const unsigned char *index = p->index_data;
1708 unsigned hi, lo, stride;
1709 static int debug_lookup = -1;
1711 if (debug_lookup < 0)
1712 debug_lookup = !!getenv("GIT_DEBUG_LOOKUP");
1714 if (!index) {
1715 if (open_pack_index(p))
1716 return 0;
1717 level1_ofs = p->index_data;
1718 index = p->index_data;
1720 if (p->index_version > 1) {
1721 level1_ofs += 2;
1722 index += 8;
1724 index += 4 * 256;
1725 hi = ntohl(level1_ofs[*sha1]);
1726 lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));
1727 if (p->index_version > 1) {
1728 stride = 20;
1729 } else {
1730 stride = 24;
1731 index += 4;
1734 if (debug_lookup)
1735 printf("%02x%02x%02x... lo %u hi %u nr %"PRIu32"\n",
1736 sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);
1738 while (lo < hi) {
1739 unsigned mi = (lo + hi) / 2;
1740 int cmp = hashcmp(index + mi * stride, sha1);
1742 if (debug_lookup)
1743 printf("lo %u hi %u rg %u mi %u\n",
1744 lo, hi, hi - lo, mi);
1745 if (!cmp)
1746 return nth_packed_object_offset(p, mi);
1747 if (cmp > 0)
1748 hi = mi;
1749 else
1750 lo = mi+1;
1752 return 0;
1755 int is_pack_valid(struct packed_git *p)
1757 /* An already open pack is known to be valid. */
1758 if (p->pack_fd != -1)
1759 return 1;
1761 /* If the pack has one window completely covering the
1762 * file size, the pack is known to be valid even if
1763 * the descriptor is not currently open.
1765 if (p->windows) {
1766 struct pack_window *w = p->windows;
1768 if (!w->offset && w->len == p->pack_size)
1769 return 1;
1772 /* Force the pack to open to prove its valid. */
1773 return !open_packed_git(p);
1776 struct packed_git *find_sha1_pack(const unsigned char *sha1,
1777 struct packed_git *packs)
1779 struct packed_git *p;
1781 for (p = packs; p; p = p->next) {
1782 if (find_pack_entry_one(sha1, p))
1783 return p;
1785 return NULL;
1789 static int fill_pack_entry(const unsigned char *sha1,
1790 struct pack_entry *e,
1791 struct packed_git *p)
1793 off_t offset;
1795 if (p->num_bad_objects) {
1796 unsigned i;
1797 for (i = 0; i < p->num_bad_objects; i++)
1798 if (!hashcmp(sha1, p->bad_object_sha1 + 20 * i))
1799 return 0;
1802 offset = find_pack_entry_one(sha1, p);
1803 if (!offset)
1804 return 0;
1807 * We are about to tell the caller where they can locate the
1808 * requested object. We better make sure the packfile is
1809 * still here and can be accessed before supplying that
1810 * answer, as it may have been deleted since the index was
1811 * loaded!
1813 if (!is_pack_valid(p))
1814 return 0;
1815 e->offset = offset;
1816 e->p = p;
1817 hashcpy(e->sha1, sha1);
1818 return 1;
1822 * Iff a pack file contains the object named by sha1, return true and
1823 * store its location to e.
1825 int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
1827 struct mru_entry *p;
1829 prepare_packed_git();
1830 if (!packed_git)
1831 return 0;
1833 for (p = packed_git_mru.head; p; p = p->next) {
1834 if (fill_pack_entry(sha1, e, p->item)) {
1835 mru_mark(&packed_git_mru, p);
1836 return 1;
1839 return 0;
1842 int has_sha1_pack(const unsigned char *sha1)
1844 struct pack_entry e;
1845 return find_pack_entry(sha1, &e);
1848 int has_pack_index(const unsigned char *sha1)
1850 struct stat st;
1851 if (stat(sha1_pack_index_name(sha1), &st))
1852 return 0;
1853 return 1;
1856 static int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn cb, void *data)
1858 uint32_t i;
1859 int r = 0;
1861 for (i = 0; i < p->num_objects; i++) {
1862 struct object_id oid;
1864 if (!nth_packed_object_oid(&oid, p, i))
1865 return error("unable to get sha1 of object %u in %s",
1866 i, p->pack_name);
1868 r = cb(&oid, p, i, data);
1869 if (r)
1870 break;
1872 return r;
1875 int for_each_packed_object(each_packed_object_fn cb, void *data, unsigned flags)
1877 struct packed_git *p;
1878 int r = 0;
1879 int pack_errors = 0;
1881 prepare_packed_git();
1882 for (p = packed_git; p; p = p->next) {
1883 if ((flags & FOR_EACH_OBJECT_LOCAL_ONLY) && !p->pack_local)
1884 continue;
1885 if (open_pack_index(p)) {
1886 pack_errors = 1;
1887 continue;
1889 r = for_each_object_in_pack(p, cb, data);
1890 if (r)
1891 break;
1893 return r ? r : pack_errors;