1#include "cache.h"
2#include "list.h"
3#include "pack.h"
4#include "repository.h"
5#include "dir.h"
6#include "mergesort.h"
7#include "packfile.h"
8#include "delta.h"
9#include "list.h"
10#include "streaming.h"
11#include "sha1-lookup.h"
12#include "commit.h"
13#include "object.h"
14#include "tag.h"
15#include "tree-walk.h"
16#include "tree.h"
17#include "object-store.h"
18#include "midx.h"
19#include "commit-graph.h"
20char *odb_pack_name(struct strbuf *buf,
22 const unsigned char *sha1,
23 const char *ext)
24{
25 strbuf_reset(buf);
26 strbuf_addf(buf, "%s/pack/pack-%s.%s", get_object_directory(),
27 sha1_to_hex(sha1), ext);
28 return buf->buf;
29}
30char *sha1_pack_name(const unsigned char *sha1)
32{
33 static struct strbuf buf = STRBUF_INIT;
34 return odb_pack_name(&buf, sha1, "pack");
35}
36char *sha1_pack_index_name(const unsigned char *sha1)
38{
39 static struct strbuf buf = STRBUF_INIT;
40 return odb_pack_name(&buf, sha1, "idx");
41}
42static unsigned int pack_used_ctr;
44static unsigned int pack_mmap_calls;
45static unsigned int peak_pack_open_windows;
46static unsigned int pack_open_windows;
47static unsigned int pack_open_fds;
48static unsigned int pack_max_fds;
49static size_t peak_pack_mapped;
50static size_t pack_mapped;
51#define SZ_FMT PRIuMAX
53static inline uintmax_t sz_fmt(size_t s) { return s; }
54void pack_report(void)
56{
57 fprintf(stderr,
58 "pack_report: getpagesize() = %10" SZ_FMT "\n"
59 "pack_report: core.packedGitWindowSize = %10" SZ_FMT "\n"
60 "pack_report: core.packedGitLimit = %10" SZ_FMT "\n",
61 sz_fmt(getpagesize()),
62 sz_fmt(packed_git_window_size),
63 sz_fmt(packed_git_limit));
64 fprintf(stderr,
65 "pack_report: pack_used_ctr = %10u\n"
66 "pack_report: pack_mmap_calls = %10u\n"
67 "pack_report: pack_open_windows = %10u / %10u\n"
68 "pack_report: pack_mapped = "
69 "%10" SZ_FMT " / %10" SZ_FMT "\n",
70 pack_used_ctr,
71 pack_mmap_calls,
72 pack_open_windows, peak_pack_open_windows,
73 sz_fmt(pack_mapped), sz_fmt(peak_pack_mapped));
74}
75/*
77 * Open and mmap the index file at path, perform a couple of
78 * consistency checks, then record its information to p. Return 0 on
79 * success.
80 */
81static int check_packed_git_idx(const char *path, struct packed_git *p)
82{
83 void *idx_map;
84 size_t idx_size;
85 int fd = git_open(path), ret;
86 struct stat st;
87 const unsigned int hashsz = the_hash_algo->rawsz;
88 if (fd < 0)
90 return -1;
91 if (fstat(fd, &st)) {
92 close(fd);
93 return -1;
94 }
95 idx_size = xsize_t(st.st_size);
96 if (idx_size < 4 * 256 + hashsz + hashsz) {
97 close(fd);
98 return error("index file %s is too small", path);
99 }
100 idx_map = xmmap(NULL, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);
101 close(fd);
102 ret = load_idx(path, hashsz, idx_map, idx_size, p);
104 if (ret)
106 munmap(idx_map, idx_size);
107 return ret;
109}
110int load_idx(const char *path, const unsigned int hashsz, void *idx_map,
112 size_t idx_size, struct packed_git *p)
113{
114 struct pack_idx_header *hdr = idx_map;
115 uint32_t version, nr, i, *index;
116 if (idx_size < 4 * 256 + hashsz + hashsz)
118 return error("index file %s is too small", path);
119 if (idx_map == NULL)
120 return error("empty data");
121 if (hdr->idx_signature == htonl(PACK_IDX_SIGNATURE)) {
123 version = ntohl(hdr->idx_version);
124 if (version < 2 || version > 2)
125 return error("index file %s is version %"PRIu32
126 " and is not supported by this binary"
127 " (try upgrading GIT to a newer version)",
128 path, version);
129 } else
130 version = 1;
131 nr = 0;
133 index = idx_map;
134 if (version > 1)
135 index += 2; /* skip index header */
136 for (i = 0; i < 256; i++) {
137 uint32_t n = ntohl(index[i]);
138 if (n < nr)
139 return error("non-monotonic index %s", path);
140 nr = n;
141 }
142 if (version == 1) {
144 /*
145 * Total size:
146 * - 256 index entries 4 bytes each
147 * - 24-byte entries * nr (object ID + 4-byte offset)
148 * - hash of the packfile
149 * - file checksum
150 */
151 if (idx_size != 4 * 256 + nr * (hashsz + 4) + hashsz + hashsz)
152 return error("wrong index v1 file size in %s", path);
153 } else if (version == 2) {
154 /*
155 * Minimum size:
156 * - 8 bytes of header
157 * - 256 index entries 4 bytes each
158 * - object ID entry * nr
159 * - 4-byte crc entry * nr
160 * - 4-byte offset entry * nr
161 * - hash of the packfile
162 * - file checksum
163 * And after the 4-byte offset table might be a
164 * variable sized table containing 8-byte entries
165 * for offsets larger than 2^31.
166 */
167 unsigned long min_size = 8 + 4*256 + nr*(hashsz + 4 + 4) + hashsz + hashsz;
168 unsigned long max_size = min_size;
169 if (nr)
170 max_size += (nr - 1)*8;
171 if (idx_size < min_size || idx_size > max_size)
172 return error("wrong index v2 file size in %s", path);
173 if (idx_size != min_size &&
174 /*
175 * make sure we can deal with large pack offsets.
176 * 31-bit signed offset won't be enough, neither
177 * 32-bit unsigned one will be.
178 */
179 (sizeof(off_t) <= 4))
180 return error("pack too large for current definition of off_t in %s", path);
181 }
182 p->index_version = version;
184 p->index_data = idx_map;
185 p->index_size = idx_size;
186 p->num_objects = nr;
187 return 0;
188}
189int open_pack_index(struct packed_git *p)
191{
192 char *idx_name;
193 size_t len;
194 int ret;
195 if (p->index_data)
197 return 0;
198 if (!strip_suffix(p->pack_name, ".pack", &len))
200 BUG("pack_name does not end in .pack");
201 idx_name = xstrfmt("%.*s.idx", (int)len, p->pack_name);
202 ret = check_packed_git_idx(idx_name, p);
203 free(idx_name);
204 return ret;
205}
206uint32_t get_pack_fanout(struct packed_git *p, uint32_t value)
208{
209 const uint32_t *level1_ofs = p->index_data;
210 if (!level1_ofs) {
212 if (open_pack_index(p))
213 return 0;
214 level1_ofs = p->index_data;
215 }
216 if (p->index_version > 1) {
218 level1_ofs += 2;
219 }
220 return ntohl(level1_ofs[value]);
222}
223static struct packed_git *alloc_packed_git(int extra)
225{
226 struct packed_git *p = xmalloc(st_add(sizeof(*p), extra));
227 memset(p, 0, sizeof(*p));
228 p->pack_fd = -1;
229 return p;
230}
231struct packed_git *parse_pack_index(unsigned char *sha1, const char *idx_path)
233{
234 const char *path = sha1_pack_name(sha1);
235 size_t alloc = st_add(strlen(path), 1);
236 struct packed_git *p = alloc_packed_git(alloc);
237 memcpy(p->pack_name, path, alloc); /* includes NUL */
239 hashcpy(p->hash, sha1);
240 if (check_packed_git_idx(idx_path, p)) {
241 free(p);
242 return NULL;
243 }
244 return p;
246}
247static void scan_windows(struct packed_git *p,
249 struct packed_git **lru_p,
250 struct pack_window **lru_w,
251 struct pack_window **lru_l)
252{
253 struct pack_window *w, *w_l;
254 for (w_l = NULL, w = p->windows; w; w = w->next) {
256 if (!w->inuse_cnt) {
257 if (!*lru_w || w->last_used < (*lru_w)->last_used) {
258 *lru_p = p;
259 *lru_w = w;
260 *lru_l = w_l;
261 }
262 }
263 w_l = w;
264 }
265}
266static int unuse_one_window(struct packed_git *current)
268{
269 struct packed_git *p, *lru_p = NULL;
270 struct pack_window *lru_w = NULL, *lru_l = NULL;
271 if (current)
273 scan_windows(current, &lru_p, &lru_w, &lru_l);
274 for (p = the_repository->objects->packed_git; p; p = p->next)
275 scan_windows(p, &lru_p, &lru_w, &lru_l);
276 if (lru_p) {
277 munmap(lru_w->base, lru_w->len);
278 pack_mapped -= lru_w->len;
279 if (lru_l)
280 lru_l->next = lru_w->next;
281 else
282 lru_p->windows = lru_w->next;
283 free(lru_w);
284 pack_open_windows--;
285 return 1;
286 }
287 return 0;
288}
289void close_pack_windows(struct packed_git *p)
291{
292 while (p->windows) {
293 struct pack_window *w = p->windows;
294 if (w->inuse_cnt)
296 die("pack '%s' still has open windows to it",
297 p->pack_name);
298 munmap(w->base, w->len);
299 pack_mapped -= w->len;
300 pack_open_windows--;
301 p->windows = w->next;
302 free(w);
303 }
304}
305int close_pack_fd(struct packed_git *p)
307{
308 if (p->pack_fd < 0)
309 return 0;
310 close(p->pack_fd);
312 pack_open_fds--;
313 p->pack_fd = -1;
314 return 1;
316}
317void close_pack_index(struct packed_git *p)
319{
320 if (p->index_data) {
321 munmap((void *)p->index_data, p->index_size);
322 p->index_data = NULL;
323 }
324}
325void close_pack(struct packed_git *p)
327{
328 close_pack_windows(p);
329 close_pack_fd(p);
330 close_pack_index(p);
331}
332void close_object_store(struct raw_object_store *o)
334{
335 struct packed_git *p;
336 for (p = o->packed_git; p; p = p->next)
338 if (p->do_not_close)
339 BUG("want to close pack marked 'do-not-close'");
340 else
341 close_pack(p);
342 if (o->multi_pack_index) {
344 close_midx(o->multi_pack_index);
345 o->multi_pack_index = NULL;
346 }
347 close_commit_graph(o);
349}
350void unlink_pack_path(const char *pack_name, int force_delete)
352{
353 static const char *exts[] = {".pack", ".idx", ".keep", ".bitmap", ".promisor"};
354 int i;
355 struct strbuf buf = STRBUF_INIT;
356 size_t plen;
357 strbuf_addstr(&buf, pack_name);
359 strip_suffix_mem(buf.buf, &buf.len, ".pack");
360 plen = buf.len;
361 if (!force_delete) {
363 strbuf_addstr(&buf, ".keep");
364 if (!access(buf.buf, F_OK)) {
365 strbuf_release(&buf);
366 return;
367 }
368 }
369 for (i = 0; i < ARRAY_SIZE(exts); i++) {
371 strbuf_setlen(&buf, plen);
372 strbuf_addstr(&buf, exts[i]);
373 unlink(buf.buf);
374 }
375 strbuf_release(&buf);
377}
378/*
380 * The LRU pack is the one with the oldest MRU window, preferring packs
381 * with no used windows, or the oldest mtime if it has no windows allocated.
382 */
383static void find_lru_pack(struct packed_git *p, struct packed_git **lru_p, struct pack_window **mru_w, int *accept_windows_inuse)
384{
385 struct pack_window *w, *this_mru_w;
386 int has_windows_inuse = 0;
387 /*
389 * Reject this pack if it has windows and the previously selected
390 * one does not. If this pack does not have windows, reject
391 * it if the pack file is newer than the previously selected one.
392 */
393 if (*lru_p && !*mru_w && (p->windows || p->mtime > (*lru_p)->mtime))
394 return;
395 for (w = this_mru_w = p->windows; w; w = w->next) {
397 /*
398 * Reject this pack if any of its windows are in use,
399 * but the previously selected pack did not have any
400 * inuse windows. Otherwise, record that this pack
401 * has windows in use.
402 */
403 if (w->inuse_cnt) {
404 if (*accept_windows_inuse)
405 has_windows_inuse = 1;
406 else
407 return;
408 }
409 if (w->last_used > this_mru_w->last_used)
411 this_mru_w = w;
412 /*
414 * Reject this pack if it has windows that have been
415 * used more recently than the previously selected pack.
416 * If the previously selected pack had windows inuse and
417 * we have not encountered a window in this pack that is
418 * inuse, skip this check since we prefer a pack with no
419 * inuse windows to one that has inuse windows.
420 */
421 if (*mru_w && *accept_windows_inuse == has_windows_inuse &&
422 this_mru_w->last_used > (*mru_w)->last_used)
423 return;
424 }
425 /*
427 * Select this pack.
428 */
429 *mru_w = this_mru_w;
430 *lru_p = p;
431 *accept_windows_inuse = has_windows_inuse;
432}
433static int close_one_pack(void)
435{
436 struct packed_git *p, *lru_p = NULL;
437 struct pack_window *mru_w = NULL;
438 int accept_windows_inuse = 1;
439 for (p = the_repository->objects->packed_git; p; p = p->next) {
441 if (p->pack_fd == -1)
442 continue;
443 find_lru_pack(p, &lru_p, &mru_w, &accept_windows_inuse);
444 }
445 if (lru_p)
447 return close_pack_fd(lru_p);
448 return 0;
450}
451static unsigned int get_max_fd_limit(void)
453{
454#ifdef RLIMIT_NOFILE
455 {
456 struct rlimit lim;
457 if (!getrlimit(RLIMIT_NOFILE, &lim))
459 return lim.rlim_cur;
460 }
461#endif
462#ifdef _SC_OPEN_MAX
464 {
465 long open_max = sysconf(_SC_OPEN_MAX);
466 if (0 < open_max)
467 return open_max;
468 /*
469 * Otherwise, we got -1 for one of the two
470 * reasons:
471 *
472 * (1) sysconf() did not understand _SC_OPEN_MAX
473 * and signaled an error with -1; or
474 * (2) sysconf() said there is no limit.
475 *
476 * We _could_ clear errno before calling sysconf() to
477 * tell these two cases apart and return a huge number
478 * in the latter case to let the caller cap it to a
479 * value that is not so selfish, but letting the
480 * fallback OPEN_MAX codepath take care of these cases
481 * is a lot simpler.
482 */
483 }
484#endif
485#ifdef OPEN_MAX
487 return OPEN_MAX;
488#else
489 return 1; /* see the caller ;-) */
490#endif
491}
492const char *pack_basename(struct packed_git *p)
494{
495 const char *ret = strrchr(p->pack_name, '/');
496 if (ret)
497 ret = ret + 1; /* skip past slash */
498 else
499 ret = p->pack_name; /* we only have a base */
500 return ret;
501}
502/*
504 * Do not call this directly as this leaks p->pack_fd on error return;
505 * call open_packed_git() instead.
506 */
507static int open_packed_git_1(struct packed_git *p)
508{
509 struct stat st;
510 struct pack_header hdr;
511 unsigned char hash[GIT_MAX_RAWSZ];
512 unsigned char *idx_hash;
513 long fd_flag;
514 ssize_t read_result;
515 const unsigned hashsz = the_hash_algo->rawsz;
516 if (!p->index_data) {
518 struct multi_pack_index *m;
519 const char *pack_name = pack_basename(p);
520 for (m = the_repository->objects->multi_pack_index;
522 m; m = m->next) {
523 if (midx_contains_pack(m, pack_name))
524 break;
525 }
526 if (!m && open_pack_index(p))
528 return error("packfile %s index unavailable", p->pack_name);
529 }
530 if (!pack_max_fds) {
532 unsigned int max_fds = get_max_fd_limit();
533 /* Save 3 for stdin/stdout/stderr, 22 for work */
535 if (25 < max_fds)
536 pack_max_fds = max_fds - 25;
537 else
538 pack_max_fds = 1;
539 }
540 while (pack_max_fds <= pack_open_fds && close_one_pack())
542 ; /* nothing */
543 p->pack_fd = git_open(p->pack_name);
545 if (p->pack_fd < 0 || fstat(p->pack_fd, &st))
546 return -1;
547 pack_open_fds++;
548 /* If we created the struct before we had the pack we lack size. */
550 if (!p->pack_size) {
551 if (!S_ISREG(st.st_mode))
552 return error("packfile %s not a regular file", p->pack_name);
553 p->pack_size = st.st_size;
554 } else if (p->pack_size != st.st_size)
555 return error("packfile %s size changed", p->pack_name);
556 /* We leave these file descriptors open with sliding mmap;
558 * there is no point keeping them open across exec(), though.
559 */
560 fd_flag = fcntl(p->pack_fd, F_GETFD, 0);
561 if (fd_flag < 0)
562 return error("cannot determine file descriptor flags");
563 fd_flag |= FD_CLOEXEC;
564 if (fcntl(p->pack_fd, F_SETFD, fd_flag) == -1)
565 return error("cannot set FD_CLOEXEC");
566 /* Verify we recognize this pack file format. */
568 read_result = read_in_full(p->pack_fd, &hdr, sizeof(hdr));
569 if (read_result < 0)
570 return error_errno("error reading from %s", p->pack_name);
571 if (read_result != sizeof(hdr))
572 return error("file %s is far too short to be a packfile", p->pack_name);
573 if (hdr.hdr_signature != htonl(PACK_SIGNATURE))
574 return error("file %s is not a GIT packfile", p->pack_name);
575 if (!pack_version_ok(hdr.hdr_version))
576 return error("packfile %s is version %"PRIu32" and not"
577 " supported (try upgrading GIT to a newer version)",
578 p->pack_name, ntohl(hdr.hdr_version));
579 /* Skip index checking if in multi-pack-index */
581 if (!p->index_data)
582 return 0;
583 /* Verify the pack matches its index. */
585 if (p->num_objects != ntohl(hdr.hdr_entries))
586 return error("packfile %s claims to have %"PRIu32" objects"
587 " while index indicates %"PRIu32" objects",
588 p->pack_name, ntohl(hdr.hdr_entries),
589 p->num_objects);
590 if (lseek(p->pack_fd, p->pack_size - hashsz, SEEK_SET) == -1)
591 return error("end of packfile %s is unavailable", p->pack_name);
592 read_result = read_in_full(p->pack_fd, hash, hashsz);
593 if (read_result < 0)
594 return error_errno("error reading from %s", p->pack_name);
595 if (read_result != hashsz)
596 return error("packfile %s signature is unavailable", p->pack_name);
597 idx_hash = ((unsigned char *)p->index_data) + p->index_size - hashsz * 2;
598 if (!hasheq(hash, idx_hash))
599 return error("packfile %s does not match index", p->pack_name);
600 return 0;
601}
602static int open_packed_git(struct packed_git *p)
604{
605 if (!open_packed_git_1(p))
606 return 0;
607 close_pack_fd(p);
608 return -1;
609}
610static int in_window(struct pack_window *win, off_t offset)
612{
613 /* We must promise at least one full hash after the
614 * offset is available from this window, otherwise the offset
615 * is not actually in this window and a different window (which
616 * has that one hash excess) must be used. This is to support
617 * the object header and delta base parsing routines below.
618 */
619 off_t win_off = win->offset;
620 return win_off <= offset
621 && (offset + the_hash_algo->rawsz) <= (win_off + win->len);
622}
623unsigned char *use_pack(struct packed_git *p,
625 struct pack_window **w_cursor,
626 off_t offset,
627 unsigned long *left)
628{
629 struct pack_window *win = *w_cursor;
630 /* Since packfiles end in a hash of their content and it's
632 * pointless to ask for an offset into the middle of that
633 * hash, and the in_window function above wouldn't match
634 * don't allow an offset too close to the end of the file.
635 */
636 if (!p->pack_size && p->pack_fd == -1 && open_packed_git(p))
637 die("packfile %s cannot be accessed", p->pack_name);
638 if (offset > (p->pack_size - the_hash_algo->rawsz))
639 die("offset beyond end of packfile (truncated pack?)");
640 if (offset < 0)
641 die(_("offset before end of packfile (broken .idx?)"));
642 if (!win || !in_window(win, offset)) {
644 if (win)
645 win->inuse_cnt--;
646 for (win = p->windows; win; win = win->next) {
647 if (in_window(win, offset))
648 break;
649 }
650 if (!win) {
651 size_t window_align = packed_git_window_size / 2;
652 off_t len;
653 if (p->pack_fd == -1 && open_packed_git(p))
655 die("packfile %s cannot be accessed", p->pack_name);
656 win = xcalloc(1, sizeof(*win));
658 win->offset = (offset / window_align) * window_align;
659 len = p->pack_size - win->offset;
660 if (len > packed_git_window_size)
661 len = packed_git_window_size;
662 win->len = (size_t)len;
663 pack_mapped += win->len;
664 while (packed_git_limit < pack_mapped
665 && unuse_one_window(p))
666 ; /* nothing */
667 win->base = xmmap_gently(NULL, win->len,
668 PROT_READ, MAP_PRIVATE,
669 p->pack_fd, win->offset);
670 if (win->base == MAP_FAILED)
671 die_errno("packfile %s cannot be mapped",
672 p->pack_name);
673 if (!win->offset && win->len == p->pack_size
674 && !p->do_not_close)
675 close_pack_fd(p);
676 pack_mmap_calls++;
677 pack_open_windows++;
678 if (pack_mapped > peak_pack_mapped)
679 peak_pack_mapped = pack_mapped;
680 if (pack_open_windows > peak_pack_open_windows)
681 peak_pack_open_windows = pack_open_windows;
682 win->next = p->windows;
683 p->windows = win;
684 }
685 }
686 if (win != *w_cursor) {
687 win->last_used = pack_used_ctr++;
688 win->inuse_cnt++;
689 *w_cursor = win;
690 }
691 offset -= win->offset;
692 if (left)
693 *left = win->len - xsize_t(offset);
694 return win->base + offset;
695}
696void unuse_pack(struct pack_window **w_cursor)
698{
699 struct pack_window *w = *w_cursor;
700 if (w) {
701 w->inuse_cnt--;
702 *w_cursor = NULL;
703 }
704}
705struct packed_git *add_packed_git(const char *path, size_t path_len, int local)
707{
708 struct stat st;
709 size_t alloc;
710 struct packed_git *p;
711 /*
713 * Make sure a corresponding .pack file exists and that
714 * the index looks sane.
715 */
716 if (!strip_suffix_mem(path, &path_len, ".idx"))
717 return NULL;
718 /*
720 * ".promisor" is long enough to hold any suffix we're adding (and
721 * the use xsnprintf double-checks that)
722 */
723 alloc = st_add3(path_len, strlen(".promisor"), 1);
724 p = alloc_packed_git(alloc);
725 memcpy(p->pack_name, path, path_len);
726 xsnprintf(p->pack_name + path_len, alloc - path_len, ".keep");
728 if (!access(p->pack_name, F_OK))
729 p->pack_keep = 1;
730 xsnprintf(p->pack_name + path_len, alloc - path_len, ".promisor");
732 if (!access(p->pack_name, F_OK))
733 p->pack_promisor = 1;
734 xsnprintf(p->pack_name + path_len, alloc - path_len, ".pack");
736 if (stat(p->pack_name, &st) || !S_ISREG(st.st_mode)) {
737 free(p);
738 return NULL;
739 }
740 /* ok, it looks sane as far as we can check without
742 * actually mapping the pack file.
743 */
744 p->pack_size = st.st_size;
745 p->pack_local = local;
746 p->mtime = st.st_mtime;
747 if (path_len < the_hash_algo->hexsz ||
748 get_sha1_hex(path + path_len - the_hash_algo->hexsz, p->hash))
749 hashclr(p->hash);
750 return p;
751}
752void install_packed_git(struct repository *r, struct packed_git *pack)
754{
755 if (pack->pack_fd != -1)
756 pack_open_fds++;
757 pack->next = r->objects->packed_git;
759 r->objects->packed_git = pack;
760}
761void (*report_garbage)(unsigned seen_bits, const char *path);
763static void report_helper(const struct string_list *list,
765 int seen_bits, int first, int last)
766{
767 if (seen_bits == (PACKDIR_FILE_PACK|PACKDIR_FILE_IDX))
768 return;
769 for (; first < last; first++)
771 report_garbage(seen_bits, list->items[first].string);
772}
773static void report_pack_garbage(struct string_list *list)
775{
776 int i, baselen = -1, first = 0, seen_bits = 0;
777 if (!report_garbage)
779 return;
780 string_list_sort(list);
782 for (i = 0; i < list->nr; i++) {
784 const char *path = list->items[i].string;
785 if (baselen != -1 &&
786 strncmp(path, list->items[first].string, baselen)) {
787 report_helper(list, seen_bits, first, i);
788 baselen = -1;
789 seen_bits = 0;
790 }
791 if (baselen == -1) {
792 const char *dot = strrchr(path, '.');
793 if (!dot) {
794 report_garbage(PACKDIR_FILE_GARBAGE, path);
795 continue;
796 }
797 baselen = dot - path + 1;
798 first = i;
799 }
800 if (!strcmp(path + baselen, "pack"))
801 seen_bits |= 1;
802 else if (!strcmp(path + baselen, "idx"))
803 seen_bits |= 2;
804 }
805 report_helper(list, seen_bits, first, list->nr);
806}
807void for_each_file_in_pack_dir(const char *objdir,
809 each_file_in_pack_dir_fn fn,
810 void *data)
811{
812 struct strbuf path = STRBUF_INIT;
813 size_t dirnamelen;
814 DIR *dir;
815 struct dirent *de;
816 strbuf_addstr(&path, objdir);
818 strbuf_addstr(&path, "/pack");
819 dir = opendir(path.buf);
820 if (!dir) {
821 if (errno != ENOENT)
822 error_errno("unable to open object pack directory: %s",
823 path.buf);
824 strbuf_release(&path);
825 return;
826 }
827 strbuf_addch(&path, '/');
828 dirnamelen = path.len;
829 while ((de = readdir(dir)) != NULL) {
830 if (is_dot_or_dotdot(de->d_name))
831 continue;
832 strbuf_setlen(&path, dirnamelen);
834 strbuf_addstr(&path, de->d_name);
835 fn(path.buf, path.len, de->d_name, data);
837 }
838 closedir(dir);
840 strbuf_release(&path);
841}
842struct prepare_pack_data {
844 struct repository *r;
845 struct string_list *garbage;
846 int local;
847 struct multi_pack_index *m;
848};
849static void prepare_pack(const char *full_name, size_t full_name_len,
851 const char *file_name, void *_data)
852{
853 struct prepare_pack_data *data = (struct prepare_pack_data *)_data;
854 struct packed_git *p;
855 size_t base_len = full_name_len;
856 if (strip_suffix_mem(full_name, &base_len, ".idx") &&
858 !(data->m && midx_contains_pack(data->m, file_name))) {
859 /* Don't reopen a pack we already have. */
860 for (p = data->r->objects->packed_git; p; p = p->next) {
861 size_t len;
862 if (strip_suffix(p->pack_name, ".pack", &len) &&
863 len == base_len &&
864 !memcmp(p->pack_name, full_name, len))
865 break;
866 }
867 if (!p) {
869 p = add_packed_git(full_name, full_name_len, data->local);
870 if (p)
871 install_packed_git(data->r, p);
872 }
873 }
874 if (!report_garbage)
876 return;
877 if (!strcmp(file_name, "multi-pack-index"))
879 return;
880 if (ends_with(file_name, ".idx") ||
881 ends_with(file_name, ".pack") ||
882 ends_with(file_name, ".bitmap") ||
883 ends_with(file_name, ".keep") ||
884 ends_with(file_name, ".promisor"))
885 string_list_append(data->garbage, full_name);
886 else
887 report_garbage(PACKDIR_FILE_GARBAGE, full_name);
888}
889static void prepare_packed_git_one(struct repository *r, char *objdir, int local)
891{
892 struct prepare_pack_data data;
893 struct string_list garbage = STRING_LIST_INIT_DUP;
894 data.m = r->objects->multi_pack_index;
896 /* look for the multi-pack-index for this object directory */
898 while (data.m && strcmp(data.m->object_dir, objdir))
899 data.m = data.m->next;
900 data.r = r;
902 data.garbage = &garbage;
903 data.local = local;
904 for_each_file_in_pack_dir(objdir, prepare_pack, &data);
906 report_pack_garbage(data.garbage);
908 string_list_clear(data.garbage, 0);
909}
910static void prepare_packed_git(struct repository *r);
912/*
913 * Give a fast, rough count of the number of objects in the repository. This
914 * ignores loose objects completely. If you have a lot of them, then either
915 * you should repack because your performance will be awful, or they are
916 * all unreachable objects about to be pruned, in which case they're not really
917 * interesting as a measure of repo size in the first place.
918 */
919unsigned long repo_approximate_object_count(struct repository *r)
920{
921 if (!r->objects->approximate_object_count_valid) {
922 unsigned long count;
923 struct multi_pack_index *m;
924 struct packed_git *p;
925 prepare_packed_git(r);
927 count = 0;
928 for (m = get_multi_pack_index(r); m; m = m->next)
929 count += m->num_objects;
930 for (p = r->objects->packed_git; p; p = p->next) {
931 if (open_pack_index(p))
932 continue;
933 count += p->num_objects;
934 }
935 r->objects->approximate_object_count = count;
936 }
937 return r->objects->approximate_object_count;
938}
939static void *get_next_packed_git(const void *p)
941{
942 return ((const struct packed_git *)p)->next;
943}
944static void set_next_packed_git(void *p, void *next)
946{
947 ((struct packed_git *)p)->next = next;
948}
949static int sort_pack(const void *a_, const void *b_)
951{
952 const struct packed_git *a = a_;
953 const struct packed_git *b = b_;
954 int st;
955 /*
957 * Local packs tend to contain objects specific to our
958 * variant of the project than remote ones. In addition,
959 * remote ones could be on a network mounted filesystem.
960 * Favor local ones for these reasons.
961 */
962 st = a->pack_local - b->pack_local;
963 if (st)
964 return -st;
965 /*
967 * Younger packs tend to contain more recent objects,
968 * and more recent objects tend to get accessed more
969 * often.
970 */
971 if (a->mtime < b->mtime)
972 return 1;
973 else if (a->mtime == b->mtime)
974 return 0;
975 return -1;
976}
977static void rearrange_packed_git(struct repository *r)
979{
980 r->objects->packed_git = llist_mergesort(
981 r->objects->packed_git, get_next_packed_git,
982 set_next_packed_git, sort_pack);
983}
984static void prepare_packed_git_mru(struct repository *r)
986{
987 struct packed_git *p;
988 INIT_LIST_HEAD(&r->objects->packed_git_mru);
990 for (p = r->objects->packed_git; p; p = p->next)
992 list_add_tail(&p->mru, &r->objects->packed_git_mru);
993}
994static void prepare_packed_git(struct repository *r)
996{
997 struct object_directory *odb;
998 if (r->objects->packed_git_initialized)
1000 return;
1001 prepare_alt_odb(r);
1003 for (odb = r->objects->odb; odb; odb = odb->next) {
1004 int local = (odb == r->objects->odb);
1005 prepare_multi_pack_index_one(r, odb->path, local);
1006 prepare_packed_git_one(r, odb->path, local);
1007 }
1008 rearrange_packed_git(r);
1009 prepare_packed_git_mru(r);
1011 r->objects->packed_git_initialized = 1;
1012}
1013void reprepare_packed_git(struct repository *r)
1015{
1016 struct object_directory *odb;
1017 for (odb = r->objects->odb; odb; odb = odb->next)
1019 odb_clear_loose_cache(odb);
1020 r->objects->approximate_object_count_valid = 0;
1022 r->objects->packed_git_initialized = 0;
1023 prepare_packed_git(r);
1024}
1025struct packed_git *get_packed_git(struct repository *r)
1027{
1028 prepare_packed_git(r);
1029 return r->objects->packed_git;
1030}
1031struct multi_pack_index *get_multi_pack_index(struct repository *r)
1033{
1034 prepare_packed_git(r);
1035 return r->objects->multi_pack_index;
1036}
1037struct packed_git *get_all_packs(struct repository *r)
1039{
1040 struct multi_pack_index *m;
1041 prepare_packed_git(r);
1043 for (m = r->objects->multi_pack_index; m; m = m->next) {
1044 uint32_t i;
1045 for (i = 0; i < m->num_packs; i++)
1046 prepare_midx_pack(r, m, i);
1047 }
1048 return r->objects->packed_git;
1050}
1051struct list_head *get_packed_git_mru(struct repository *r)
1053{
1054 prepare_packed_git(r);
1055 return &r->objects->packed_git_mru;
1056}
1057unsigned long unpack_object_header_buffer(const unsigned char *buf,
1059 unsigned long len, enum object_type *type, unsigned long *sizep)
1060{
1061 unsigned shift;
1062 unsigned long size, c;
1063 unsigned long used = 0;
1064 c = buf[used++];
1066 *type = (c >> 4) & 7;
1067 size = c & 15;
1068 shift = 4;
1069 while (c & 0x80) {
1070 if (len <= used || bitsizeof(long) <= shift) {
1071 error("bad object header");
1072 size = used = 0;
1073 break;
1074 }
1075 c = buf[used++];
1076 size += (c & 0x7f) << shift;
1077 shift += 7;
1078 }
1079 *sizep = size;
1080 return used;
1081}
1082unsigned long get_size_from_delta(struct packed_git *p,
1084 struct pack_window **w_curs,
1085 off_t curpos)
1086{
1087 const unsigned char *data;
1088 unsigned char delta_head[20], *in;
1089 git_zstream stream;
1090 int st;
1091 memset(&stream, 0, sizeof(stream));
1093 stream.next_out = delta_head;
1094 stream.avail_out = sizeof(delta_head);
1095 git_inflate_init(&stream);
1097 do {
1098 in = use_pack(p, w_curs, curpos, &stream.avail_in);
1099 stream.next_in = in;
1100 st = git_inflate(&stream, Z_FINISH);
1101 curpos += stream.next_in - in;
1102 } while ((st == Z_OK || st == Z_BUF_ERROR) &&
1103 stream.total_out < sizeof(delta_head));
1104 git_inflate_end(&stream);
1105 if ((st != Z_STREAM_END) && stream.total_out != sizeof(delta_head)) {
1106 error("delta data unpack-initial failed");
1107 return 0;
1108 }
1109 /* Examine the initial part of the delta to figure out
1111 * the result size.
1112 */
1113 data = delta_head;
1114 /* ignore base size */
1116 get_delta_hdr_size(&data, delta_head+sizeof(delta_head));
1117 /* Read the result size */
1119 return get_delta_hdr_size(&data, delta_head+sizeof(delta_head));
1120}
1121int unpack_object_header(struct packed_git *p,
1123 struct pack_window **w_curs,
1124 off_t *curpos,
1125 unsigned long *sizep)
1126{
1127 unsigned char *base;
1128 unsigned long left;
1129 unsigned long used;
1130 enum object_type type;
1131 /* use_pack() assures us we have [base, base + 20) available
1133 * as a range that we can look at. (Its actually the hash
1134 * size that is assured.) With our object header encoding
1135 * the maximum deflated object size is 2^137, which is just
1136 * insane, so we know won't exceed what we have been given.
1137 */
1138 base = use_pack(p, w_curs, *curpos, &left);
1139 used = unpack_object_header_buffer(base, left, &type, sizep);
1140 if (!used) {
1141 type = OBJ_BAD;
1142 } else
1143 *curpos += used;
1144 return type;
1146}
1147void mark_bad_packed_object(struct packed_git *p, const unsigned char *sha1)
1149{
1150 unsigned i;
1151 const unsigned hashsz = the_hash_algo->rawsz;
1152 for (i = 0; i < p->num_bad_objects; i++)
1153 if (hasheq(sha1, p->bad_object_sha1 + hashsz * i))
1154 return;
1155 p->bad_object_sha1 = xrealloc(p->bad_object_sha1,
1156 st_mult(GIT_MAX_RAWSZ,
1157 st_add(p->num_bad_objects, 1)));
1158 hashcpy(p->bad_object_sha1 + hashsz * p->num_bad_objects, sha1);
1159 p->num_bad_objects++;
1160}
1161const struct packed_git *has_packed_and_bad(struct repository *r,
1163 const unsigned char *sha1)
1164{
1165 struct packed_git *p;
1166 unsigned i;
1167 for (p = r->objects->packed_git; p; p = p->next)
1169 for (i = 0; i < p->num_bad_objects; i++)
1170 if (hasheq(sha1,
1171 p->bad_object_sha1 + the_hash_algo->rawsz * i))
1172 return p;
1173 return NULL;
1174}
1175static off_t get_delta_base(struct packed_git *p,
1177 struct pack_window **w_curs,
1178 off_t *curpos,
1179 enum object_type type,
1180 off_t delta_obj_offset)
1181{
1182 unsigned char *base_info = use_pack(p, w_curs, *curpos, NULL);
1183 off_t base_offset;
1184 /* use_pack() assured us we have [base_info, base_info + 20)
1186 * as a range that we can look at without walking off the
1187 * end of the mapped window. Its actually the hash size
1188 * that is assured. An OFS_DELTA longer than the hash size
1189 * is stupid, as then a REF_DELTA would be smaller to store.
1190 */
1191 if (type == OBJ_OFS_DELTA) {
1192 unsigned used = 0;
1193 unsigned char c = base_info[used++];
1194 base_offset = c & 127;
1195 while (c & 128) {
1196 base_offset += 1;
1197 if (!base_offset || MSB(base_offset, 7))
1198 return 0; /* overflow */
1199 c = base_info[used++];
1200 base_offset = (base_offset << 7) + (c & 127);
1201 }
1202 base_offset = delta_obj_offset - base_offset;
1203 if (base_offset <= 0 || base_offset >= delta_obj_offset)
1204 return 0; /* out of bound */
1205 *curpos += used;
1206 } else if (type == OBJ_REF_DELTA) {
1207 /* The base entry _must_ be in the same pack */
1208 base_offset = find_pack_entry_one(base_info, p);
1209 *curpos += the_hash_algo->rawsz;
1210 } else
1211 die("I am totally screwed");
1212 return base_offset;
1213}
1214/*
1216 * Like get_delta_base above, but we return the sha1 instead of the pack
1217 * offset. This means it is cheaper for REF deltas (we do not have to do
1218 * the final object lookup), but more expensive for OFS deltas (we
1219 * have to load the revidx to convert the offset back into a sha1).
1220 */
1221static const unsigned char *get_delta_base_sha1(struct packed_git *p,
1222 struct pack_window **w_curs,
1223 off_t curpos,
1224 enum object_type type,
1225 off_t delta_obj_offset)
1226{
1227 if (type == OBJ_REF_DELTA) {
1228 unsigned char *base = use_pack(p, w_curs, curpos, NULL);
1229 return base;
1230 } else if (type == OBJ_OFS_DELTA) {
1231 struct revindex_entry *revidx;
1232 off_t base_offset = get_delta_base(p, w_curs, &curpos,
1233 type, delta_obj_offset);
1234 if (!base_offset)
1236 return NULL;
1237 revidx = find_pack_revindex(p, base_offset);
1239 if (!revidx)
1240 return NULL;
1241 return nth_packed_object_sha1(p, revidx->nr);
1243 } else
1244 return NULL;
1245}
1246static int retry_bad_packed_offset(struct repository *r,
1248 struct packed_git *p,
1249 off_t obj_offset)
1250{
1251 int type;
1252 struct revindex_entry *revidx;
1253 struct object_id oid;
1254 revidx = find_pack_revindex(p, obj_offset);
1255 if (!revidx)
1256 return OBJ_BAD;
1257 nth_packed_object_oid(&oid, p, revidx->nr);
1258 mark_bad_packed_object(p, oid.hash);
1259 type = oid_object_info(r, &oid, NULL);
1260 if (type <= OBJ_NONE)
1261 return OBJ_BAD;
1262 return type;
1263}
1264#define POI_STACK_PREALLOC 64
1266static enum object_type packed_to_object_type(struct repository *r,
1268 struct packed_git *p,
1269 off_t obj_offset,
1270 enum object_type type,
1271 struct pack_window **w_curs,
1272 off_t curpos)
1273{
1274 off_t small_poi_stack[POI_STACK_PREALLOC];
1275 off_t *poi_stack = small_poi_stack;
1276 int poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;
1277 while (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
1279 off_t base_offset;
1280 unsigned long size;
1281 /* Push the object we're going to leave behind */
1282 if (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {
1283 poi_stack_alloc = alloc_nr(poi_stack_nr);
1284 ALLOC_ARRAY(poi_stack, poi_stack_alloc);
1285 COPY_ARRAY(poi_stack, small_poi_stack, poi_stack_nr);
1286 } else {
1287 ALLOC_GROW(poi_stack, poi_stack_nr+1, poi_stack_alloc);
1288 }
1289 poi_stack[poi_stack_nr++] = obj_offset;
1290 /* If parsing the base offset fails, just unwind */
1291 base_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);
1292 if (!base_offset)
1293 goto unwind;
1294 curpos = obj_offset = base_offset;
1295 type = unpack_object_header(p, w_curs, &curpos, &size);
1296 if (type <= OBJ_NONE) {
1297 /* If getting the base itself fails, we first
1298 * retry the base, otherwise unwind */
1299 type = retry_bad_packed_offset(r, p, base_offset);
1300 if (type > OBJ_NONE)
1301 goto out;
1302 goto unwind;
1303 }
1304 }
1305 switch (type) {
1307 case OBJ_BAD:
1308 case OBJ_COMMIT:
1309 case OBJ_TREE:
1310 case OBJ_BLOB:
1311 case OBJ_TAG:
1312 break;
1313 default:
1314 error("unknown object type %i at offset %"PRIuMAX" in %s",
1315 type, (uintmax_t)obj_offset, p->pack_name);
1316 type = OBJ_BAD;
1317 }
1318out:
1320 if (poi_stack != small_poi_stack)
1321 free(poi_stack);
1322 return type;
1323unwind:
1325 while (poi_stack_nr) {
1326 obj_offset = poi_stack[--poi_stack_nr];
1327 type = retry_bad_packed_offset(r, p, obj_offset);
1328 if (type > OBJ_NONE)
1329 goto out;
1330 }
1331 type = OBJ_BAD;
1332 goto out;
1333}
1334static struct hashmap delta_base_cache;
1336static size_t delta_base_cached;
1337static LIST_HEAD(delta_base_cache_lru);
1339struct delta_base_cache_key {
1341 struct packed_git *p;
1342 off_t base_offset;
1343};
1344struct delta_base_cache_entry {
1346 struct hashmap hash;
1347 struct delta_base_cache_key key;
1348 struct list_head lru;
1349 void *data;
1350 unsigned long size;
1351 enum object_type type;
1352};
1353static unsigned int pack_entry_hash(struct packed_git *p, off_t base_offset)
1355{
1356 unsigned int hash;
1357 hash = (unsigned int)(intptr_t)p + (unsigned int)base_offset;
1359 hash += (hash >> 8) + (hash >> 16);
1360 return hash;
1361}
1362static struct delta_base_cache_entry *
1364get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)
1365{
1366 struct hashmap_entry entry;
1367 struct delta_base_cache_key key;
1368 if (!delta_base_cache.cmpfn)
1370 return NULL;
1371 hashmap_entry_init(&entry, pack_entry_hash(p, base_offset));
1373 key.p = p;
1374 key.base_offset = base_offset;
1375 return hashmap_get(&delta_base_cache, &entry, &key);
1376}
1377static int delta_base_cache_key_eq(const struct delta_base_cache_key *a,
1379 const struct delta_base_cache_key *b)
1380{
1381 return a->p == b->p && a->base_offset == b->base_offset;
1382}
1383static int delta_base_cache_hash_cmp(const void *unused_cmp_data,
1385 const void *va, const void *vb,
1386 const void *vkey)
1387{
1388 const struct delta_base_cache_entry *a = va, *b = vb;
1389 const struct delta_base_cache_key *key = vkey;
1390 if (key)
1391 return !delta_base_cache_key_eq(&a->key, key);
1392 else
1393 return !delta_base_cache_key_eq(&a->key, &b->key);
1394}
1395static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
1397{
1398 return !!get_delta_base_cache_entry(p, base_offset);
1399}
1400/*
1402 * Remove the entry from the cache, but do _not_ free the associated
1403 * entry data. The caller takes ownership of the "data" buffer, and
1404 * should copy out any fields it wants before detaching.
1405 */
1406static void detach_delta_base_cache_entry(struct delta_base_cache_entry *ent)
1407{
1408 hashmap_remove(&delta_base_cache, ent, &ent->key);
1409 list_del(&ent->lru);
1410 delta_base_cached -= ent->size;
1411 free(ent);
1412}
1413static void *cache_or_unpack_entry(struct repository *r, struct packed_git *p,
1415 off_t base_offset, unsigned long *base_size,
1416 enum object_type *type)
1417{
1418 struct delta_base_cache_entry *ent;
1419 ent = get_delta_base_cache_entry(p, base_offset);
1421 if (!ent)
1422 return unpack_entry(r, p, base_offset, type, base_size);
1423 if (type)
1425 *type = ent->type;
1426 if (base_size)
1427 *base_size = ent->size;
1428 return xmemdupz(ent->data, ent->size);
1429}
1430static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)
1432{
1433 free(ent->data);
1434 detach_delta_base_cache_entry(ent);
1435}
1436void clear_delta_base_cache(void)
1438{
1439 struct list_head *lru, *tmp;
1440 list_for_each_safe(lru, tmp, &delta_base_cache_lru) {
1441 struct delta_base_cache_entry *entry =
1442 list_entry(lru, struct delta_base_cache_entry, lru);
1443 release_delta_base_cache(entry);
1444 }
1445}
1446static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
1448 void *base, unsigned long base_size, enum object_type type)
1449{
1450 struct delta_base_cache_entry *ent = xmalloc(sizeof(*ent));
1451 struct list_head *lru, *tmp;
1452 delta_base_cached += base_size;
1454 list_for_each_safe(lru, tmp, &delta_base_cache_lru) {
1456 struct delta_base_cache_entry *f =
1457 list_entry(lru, struct delta_base_cache_entry, lru);
1458 if (delta_base_cached <= delta_base_cache_limit)
1459 break;
1460 release_delta_base_cache(f);
1461 }
1462 ent->key.p = p;
1464 ent->key.base_offset = base_offset;
1465 ent->type = type;
1466 ent->data = base;
1467 ent->size = base_size;
1468 list_add_tail(&ent->lru, &delta_base_cache_lru);
1469 if (!delta_base_cache.cmpfn)
1471 hashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, NULL, 0);
1472 hashmap_entry_init(ent, pack_entry_hash(p, base_offset));
1473 hashmap_add(&delta_base_cache, ent);
1474}
1475int packed_object_info(struct repository *r, struct packed_git *p,
1477 off_t obj_offset, struct object_info *oi)
1478{
1479 struct pack_window *w_curs = NULL;
1480 unsigned long size;
1481 off_t curpos = obj_offset;
1482 enum object_type type;
1483 /*
1485 * We always get the representation type, but only convert it to
1486 * a "real" type later if the caller is interested.
1487 */
1488 if (oi->contentp) {
1489 *oi->contentp = cache_or_unpack_entry(r, p, obj_offset, oi->sizep,
1490 &type);
1491 if (!*oi->contentp)
1492 type = OBJ_BAD;
1493 } else {
1494 type = unpack_object_header(p, &w_curs, &curpos, &size);
1495 }
1496 if (!oi->contentp && oi->sizep) {
1498 if (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
1499 off_t tmp_pos = curpos;
1500 off_t base_offset = get_delta_base(p, &w_curs, &tmp_pos,
1501 type, obj_offset);
1502 if (!base_offset) {
1503 type = OBJ_BAD;
1504 goto out;
1505 }
1506 *oi->sizep = get_size_from_delta(p, &w_curs, tmp_pos);
1507 if (*oi->sizep == 0) {
1508 type = OBJ_BAD;
1509 goto out;
1510 }
1511 } else {
1512 *oi->sizep = size;
1513 }
1514 }
1515 if (oi->disk_sizep) {
1517 struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
1518 *oi->disk_sizep = revidx[1].offset - obj_offset;
1519 }
1520 if (oi->typep || oi->type_name) {
1522 enum object_type ptot;
1523 ptot = packed_to_object_type(r, p, obj_offset,
1524 type, &w_curs, curpos);
1525 if (oi->typep)
1526 *oi->typep = ptot;
1527 if (oi->type_name) {
1528 const char *tn = type_name(ptot);
1529 if (tn)
1530 strbuf_addstr(oi->type_name, tn);
1531 }
1532 if (ptot < 0) {
1533 type = OBJ_BAD;
1534 goto out;
1535 }
1536 }
1537 if (oi->delta_base_sha1) {
1539 if (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
1540 const unsigned char *base;
1541 base = get_delta_base_sha1(p, &w_curs, curpos,
1543 type, obj_offset);
1544 if (!base) {
1545 type = OBJ_BAD;
1546 goto out;
1547 }
1548 hashcpy(oi->delta_base_sha1, base);
1550 } else
1551 hashclr(oi->delta_base_sha1);
1552 }
1553 oi->whence = in_delta_base_cache(p, obj_offset) ? OI_DBCACHED :
1555 OI_PACKED;
1556out:
1558 unuse_pack(&w_curs);
1559 return type;
1560}
1561static void *unpack_compressed_entry(struct packed_git *p,
1563 struct pack_window **w_curs,
1564 off_t curpos,
1565 unsigned long size)
1566{
1567 int st;
1568 git_zstream stream;
1569 unsigned char *buffer, *in;
1570 buffer = xmallocz_gently(size);
1572 if (!buffer)
1573 return NULL;
1574 memset(&stream, 0, sizeof(stream));
1575 stream.next_out = buffer;
1576 stream.avail_out = size + 1;
1577 git_inflate_init(&stream);
1579 do {
1580 in = use_pack(p, w_curs, curpos, &stream.avail_in);
1581 stream.next_in = in;
1582 st = git_inflate(&stream, Z_FINISH);
1583 if (!stream.avail_out)
1584 break; /* the payload is larger than it should be */
1585 curpos += stream.next_in - in;
1586 } while (st == Z_OK || st == Z_BUF_ERROR);
1587 git_inflate_end(&stream);
1588 if ((st != Z_STREAM_END) || stream.total_out != size) {
1589 free(buffer);
1590 return NULL;
1591 }
1592 /* versions of zlib can clobber unconsumed portion of outbuf */
1594 buffer[size] = '\0';
1595 return buffer;
1597}
1598static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
1600{
1601 static struct trace_key pack_access = TRACE_KEY_INIT(PACK_ACCESS);
1602 trace_printf_key(&pack_access, "%s %"PRIuMAX"\n",
1603 p->pack_name, (uintmax_t)obj_offset);
1604}
1605int do_check_packed_object_crc;
1607#define UNPACK_ENTRY_STACK_PREALLOC 64
1609struct unpack_entry_stack_ent {
1610 off_t obj_offset;
1611 off_t curpos;
1612 unsigned long size;
1613};
1614static void *read_object(struct repository *r,
1616 const struct object_id *oid,
1617 enum object_type *type,
1618 unsigned long *size)
1619{
1620 struct object_info oi = OBJECT_INFO_INIT;
1621 void *content;
1622 oi.typep = type;
1623 oi.sizep = size;
1624 oi.contentp = &content;
1625 if (oid_object_info_extended(r, oid, &oi, 0) < 0)
1627 return NULL;
1628 return content;
1629}
1630void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
1632 enum object_type *final_type, unsigned long *final_size)
1633{
1634 struct pack_window *w_curs = NULL;
1635 off_t curpos = obj_offset;
1636 void *data = NULL;
1637 unsigned long size;
1638 enum object_type type;
1639 struct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];
1640 struct unpack_entry_stack_ent *delta_stack = small_delta_stack;
1641 int delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;
1642 int base_from_cache = 0;
1643 write_pack_access_log(p, obj_offset);
1645 /* PHASE 1: drill down to the innermost base object */
1647 for (;;) {
1648 off_t base_offset;
1649 int i;
1650 struct delta_base_cache_entry *ent;
1651 ent = get_delta_base_cache_entry(p, curpos);
1653 if (ent) {
1654 type = ent->type;
1655 data = ent->data;
1656 size = ent->size;
1657 detach_delta_base_cache_entry(ent);
1658 base_from_cache = 1;
1659 break;
1660 }
1661 if (do_check_packed_object_crc && p->index_version > 1) {
1663 struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
1664 off_t len = revidx[1].offset - obj_offset;
1665 if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
1666 struct object_id oid;
1667 nth_packed_object_oid(&oid, p, revidx->nr);
1668 error("bad packed object CRC for %s",
1669 oid_to_hex(&oid));
1670 mark_bad_packed_object(p, oid.hash);
1671 data = NULL;
1672 goto out;
1673 }
1674 }
1675 type = unpack_object_header(p, &w_curs, &curpos, &size);
1677 if (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)
1678 break;
1679 base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
1681 if (!base_offset) {
1682 error("failed to validate delta base reference "
1683 "at offset %"PRIuMAX" from %s",
1684 (uintmax_t)curpos, p->pack_name);
1685 /* bail to phase 2, in hopes of recovery */
1686 data = NULL;
1687 break;
1688 }
1689 /* push object, proceed to base */
1691 if (delta_stack_nr >= delta_stack_alloc
1692 && delta_stack == small_delta_stack) {
1693 delta_stack_alloc = alloc_nr(delta_stack_nr);
1694 ALLOC_ARRAY(delta_stack, delta_stack_alloc);
1695 COPY_ARRAY(delta_stack, small_delta_stack,
1696 delta_stack_nr);
1697 } else {
1698 ALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);
1699 }
1700 i = delta_stack_nr++;
1701 delta_stack[i].obj_offset = obj_offset;
1702 delta_stack[i].curpos = curpos;
1703 delta_stack[i].size = size;
1704 curpos = obj_offset = base_offset;
1706 }
1707 /* PHASE 2: handle the base */
1709 switch (type) {
1710 case OBJ_OFS_DELTA:
1711 case OBJ_REF_DELTA:
1712 if (data)
1713 BUG("unpack_entry: left loop at a valid delta");
1714 break;
1715 case OBJ_COMMIT:
1716 case OBJ_TREE:
1717 case OBJ_BLOB:
1718 case OBJ_TAG:
1719 if (!base_from_cache)
1720 data = unpack_compressed_entry(p, &w_curs, curpos, size);
1721 break;
1722 default:
1723 data = NULL;
1724 error("unknown object type %i at offset %"PRIuMAX" in %s",
1725 type, (uintmax_t)obj_offset, p->pack_name);
1726 }
1727 /* PHASE 3: apply deltas in order */
1729 /* invariants:
1731 * 'data' holds the base data, or NULL if there was corruption
1732 */
1733 while (delta_stack_nr) {
1734 void *delta_data;
1735 void *base = data;
1736 void *external_base = NULL;
1737 unsigned long delta_size, base_size = size;
1738 int i;
1739 data = NULL;
1741 if (base)
1743 add_delta_base_cache(p, obj_offset, base, base_size, type);
1744 if (!base) {
1746 /*
1747 * We're probably in deep shit, but let's try to fetch
1748 * the required base anyway from another pack or loose.
1749 * This is costly but should happen only in the presence
1750 * of a corrupted pack, and is better than failing outright.
1751 */
1752 struct revindex_entry *revidx;
1753 struct object_id base_oid;
1754 revidx = find_pack_revindex(p, obj_offset);
1755 if (revidx) {
1756 nth_packed_object_oid(&base_oid, p, revidx->nr);
1757 error("failed to read delta base object %s"
1758 " at offset %"PRIuMAX" from %s",
1759 oid_to_hex(&base_oid), (uintmax_t)obj_offset,
1760 p->pack_name);
1761 mark_bad_packed_object(p, base_oid.hash);
1762 base = read_object(r, &base_oid, &type, &base_size);
1763 external_base = base;
1764 }
1765 }
1766 i = --delta_stack_nr;
1768 obj_offset = delta_stack[i].obj_offset;
1769 curpos = delta_stack[i].curpos;
1770 delta_size = delta_stack[i].size;
1771 if (!base)
1773 continue;
1774 delta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);
1776 if (!delta_data) {
1778 error("failed to unpack compressed delta "
1779 "at offset %"PRIuMAX" from %s",
1780 (uintmax_t)curpos, p->pack_name);
1781 data = NULL;
1782 free(external_base);
1783 continue;
1784 }
1785 data = patch_delta(base, base_size,
1787 delta_data, delta_size,
1788 &size);
1789 /*
1791 * We could not apply the delta; warn the user, but keep going.
1792 * Our failure will be noticed either in the next iteration of
1793 * the loop, or if this is the final delta, in the caller when
1794 * we return NULL. Those code paths will take care of making
1795 * a more explicit warning and retrying with another copy of
1796 * the object.
1797 */
1798 if (!data)
1799 error("failed to apply delta");
1800 free(delta_data);
1802 free(external_base);
1803 }
1804 if (final_type)
1806 *final_type = type;
1807 if (final_size)
1808 *final_size = size;
1809out:
1811 unuse_pack(&w_curs);
1812 if (delta_stack != small_delta_stack)
1814 free(delta_stack);
1815 return data;
1817}
1818int bsearch_pack(const struct object_id *oid, const struct packed_git *p, uint32_t *result)
1820{
1821 const unsigned char *index_fanout = p->index_data;
1822 const unsigned char *index_lookup;
1823 const unsigned int hashsz = the_hash_algo->rawsz;
1824 int index_lookup_width;
1825 if (!index_fanout)
1827 BUG("bsearch_pack called without a valid pack-index");
1828 index_lookup = index_fanout + 4 * 256;
1830 if (p->index_version == 1) {
1831 index_lookup_width = hashsz + 4;
1832 index_lookup += 4;
1833 } else {
1834 index_lookup_width = hashsz;
1835 index_fanout += 8;
1836 index_lookup += 8;
1837 }
1838 return bsearch_hash(oid->hash, (const uint32_t*)index_fanout,
1840 index_lookup, index_lookup_width, result);
1841}
1842const unsigned char *nth_packed_object_sha1(struct packed_git *p,
1844 uint32_t n)
1845{
1846 const unsigned char *index = p->index_data;
1847 const unsigned int hashsz = the_hash_algo->rawsz;
1848 if (!index) {
1849 if (open_pack_index(p))
1850 return NULL;
1851 index = p->index_data;
1852 }
1853 if (n >= p->num_objects)
1854 return NULL;
1855 index += 4 * 256;
1856 if (p->index_version == 1) {
1857 return index + (hashsz + 4) * n + 4;
1858 } else {
1859 index += 8;
1860 return index + hashsz * n;
1861 }
1862}
1863const struct object_id *nth_packed_object_oid(struct object_id *oid,
1865 struct packed_git *p,
1866 uint32_t n)
1867{
1868 const unsigned char *hash = nth_packed_object_sha1(p, n);
1869 if (!hash)
1870 return NULL;
1871 hashcpy(oid->hash, hash);
1872 return oid;
1873}
1874void check_pack_index_ptr(const struct packed_git *p, const void *vptr)
1876{
1877 const unsigned char *ptr = vptr;
1878 const unsigned char *start = p->index_data;
1879 const unsigned char *end = start + p->index_size;
1880 if (ptr < start)
1881 die(_("offset before start of pack index for %s (corrupt index?)"),
1882 p->pack_name);
1883 /* No need to check for underflow; .idx files must be at least 8 bytes */
1884 if (ptr >= end - 8)
1885 die(_("offset beyond end of pack index for %s (truncated index?)"),
1886 p->pack_name);
1887}
1888off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)
1890{
1891 const unsigned char *index = p->index_data;
1892 const unsigned int hashsz = the_hash_algo->rawsz;
1893 index += 4 * 256;
1894 if (p->index_version == 1) {
1895 return ntohl(*((uint32_t *)(index + (hashsz + 4) * n)));
1896 } else {
1897 uint32_t off;
1898 index += 8 + p->num_objects * (hashsz + 4);
1899 off = ntohl(*((uint32_t *)(index + 4 * n)));
1900 if (!(off & 0x80000000))
1901 return off;
1902 index += p->num_objects * 4 + (off & 0x7fffffff) * 8;
1903 check_pack_index_ptr(p, index);
1904 return get_be64(index);
1905 }
1906}
1907off_t find_pack_entry_one(const unsigned char *sha1,
1909 struct packed_git *p)
1910{
1911 const unsigned char *index = p->index_data;
1912 struct object_id oid;
1913 uint32_t result;
1914 if (!index) {
1916 if (open_pack_index(p))
1917 return 0;
1918 }
1919 hashcpy(oid.hash, sha1);
1921 if (bsearch_pack(&oid, p, &result))
1922 return nth_packed_object_offset(p, result);
1923 return 0;
1924}
1925int is_pack_valid(struct packed_git *p)
1927{
1928 /* An already open pack is known to be valid. */
1929 if (p->pack_fd != -1)
1930 return 1;
1931 /* If the pack has one window completely covering the
1933 * file size, the pack is known to be valid even if
1934 * the descriptor is not currently open.
1935 */
1936 if (p->windows) {
1937 struct pack_window *w = p->windows;
1938 if (!w->offset && w->len == p->pack_size)
1940 return 1;
1941 }
1942 /* Force the pack to open to prove its valid. */
1944 return !open_packed_git(p);
1945}
1946struct packed_git *find_sha1_pack(const unsigned char *sha1,
1948 struct packed_git *packs)
1949{
1950 struct packed_git *p;
1951 for (p = packs; p; p = p->next) {
1953 if (find_pack_entry_one(sha1, p))
1954 return p;
1955 }
1956 return NULL;
1957}
1959static int fill_pack_entry(const struct object_id *oid,
1961 struct pack_entry *e,
1962 struct packed_git *p)
1963{
1964 off_t offset;
1965 if (p->num_bad_objects) {
1967 unsigned i;
1968 for (i = 0; i < p->num_bad_objects; i++)
1969 if (hasheq(oid->hash,
1970 p->bad_object_sha1 + the_hash_algo->rawsz * i))
1971 return 0;
1972 }
1973 offset = find_pack_entry_one(oid->hash, p);
1975 if (!offset)
1976 return 0;
1977 /*
1979 * We are about to tell the caller where they can locate the
1980 * requested object. We better make sure the packfile is
1981 * still here and can be accessed before supplying that
1982 * answer, as it may have been deleted since the index was
1983 * loaded!
1984 */
1985 if (!is_pack_valid(p))
1986 return 0;
1987 e->offset = offset;
1988 e->p = p;
1989 return 1;
1990}
1991int find_pack_entry(struct repository *r, const struct object_id *oid, struct pack_entry *e)
1993{
1994 struct list_head *pos;
1995 struct multi_pack_index *m;
1996 prepare_packed_git(r);
1998 if (!r->objects->packed_git && !r->objects->multi_pack_index)
1999 return 0;
2000 for (m = r->objects->multi_pack_index; m; m = m->next) {
2002 if (fill_midx_entry(r, oid, e, m))
2003 return 1;
2004 }
2005 list_for_each(pos, &r->objects->packed_git_mru) {
2007 struct packed_git *p = list_entry(pos, struct packed_git, mru);
2008 if (!p->multi_pack_index && fill_pack_entry(oid, e, p)) {
2009 list_move(&p->mru, &r->objects->packed_git_mru);
2010 return 1;
2011 }
2012 }
2013 return 0;
2014}
2015int has_object_pack(const struct object_id *oid)
2017{
2018 struct pack_entry e;
2019 return find_pack_entry(the_repository, oid, &e);
2020}
2021int has_pack_index(const unsigned char *sha1)
2023{
2024 struct stat st;
2025 if (stat(sha1_pack_index_name(sha1), &st))
2026 return 0;
2027 return 1;
2028}
2029int for_each_object_in_pack(struct packed_git *p,
2031 each_packed_object_fn cb, void *data,
2032 enum for_each_object_flags flags)
2033{
2034 uint32_t i;
2035 int r = 0;
2036 if (flags & FOR_EACH_OBJECT_PACK_ORDER) {
2038 if (load_pack_revindex(p))
2039 return -1;
2040 }
2041 for (i = 0; i < p->num_objects; i++) {
2043 uint32_t pos;
2044 struct object_id oid;
2045 if (flags & FOR_EACH_OBJECT_PACK_ORDER)
2047 pos = p->revindex[i].nr;
2048 else
2049 pos = i;
2050 if (!nth_packed_object_oid(&oid, p, pos))
2052 return error("unable to get sha1 of object %u in %s",
2053 pos, p->pack_name);
2054 r = cb(&oid, p, pos, data);
2056 if (r)
2057 break;
2058 }
2059 return r;
2060}
2061int for_each_packed_object(each_packed_object_fn cb, void *data,
2063 enum for_each_object_flags flags)
2064{
2065 struct packed_git *p;
2066 int r = 0;
2067 int pack_errors = 0;
2068 prepare_packed_git(the_repository);
2070 for (p = get_all_packs(the_repository); p; p = p->next) {
2071 if ((flags & FOR_EACH_OBJECT_LOCAL_ONLY) && !p->pack_local)
2072 continue;
2073 if ((flags & FOR_EACH_OBJECT_PROMISOR_ONLY) &&
2074 !p->pack_promisor)
2075 continue;
2076 if (open_pack_index(p)) {
2077 pack_errors = 1;
2078 continue;
2079 }
2080 r = for_each_object_in_pack(p, cb, data, flags);
2081 if (r)
2082 break;
2083 }
2084 return r ? r : pack_errors;
2085}
2086static int add_promisor_object(const struct object_id *oid,
2088 struct packed_git *pack,
2089 uint32_t pos,
2090 void *set_)
2091{
2092 struct oidset *set = set_;
2093 struct object *obj = parse_object(the_repository, oid);
2094 if (!obj)
2095 return 1;
2096 oidset_insert(set, oid);
2098 /*
2100 * If this is a tree, commit, or tag, the objects it refers
2101 * to are also promisor objects. (Blobs refer to no objects->)
2102 */
2103 if (obj->type == OBJ_TREE) {
2104 struct tree *tree = (struct tree *)obj;
2105 struct tree_desc desc;
2106 struct name_entry entry;
2107 if (init_tree_desc_gently(&desc, tree->buffer, tree->size))
2108 /*
2109 * Error messages are given when packs are
2110 * verified, so do not print any here.
2111 */
2112 return 0;
2113 while (tree_entry_gently(&desc, &entry))
2114 oidset_insert(set, &entry.oid);
2115 } else if (obj->type == OBJ_COMMIT) {
2116 struct commit *commit = (struct commit *) obj;
2117 struct commit_list *parents = commit->parents;
2118 oidset_insert(set, get_commit_tree_oid(commit));
2120 for (; parents; parents = parents->next)
2121 oidset_insert(set, &parents->item->object.oid);
2122 } else if (obj->type == OBJ_TAG) {
2123 struct tag *tag = (struct tag *) obj;
2124 oidset_insert(set, &tag->tagged->oid);
2125 }
2126 return 0;
2127}
2128int is_promisor_object(const struct object_id *oid)
2130{
2131 static struct oidset promisor_objects;
2132 static int promisor_objects_prepared;
2133 if (!promisor_objects_prepared) {
2135 if (repository_format_partial_clone) {
2136 for_each_packed_object(add_promisor_object,
2137 &promisor_objects,
2138 FOR_EACH_OBJECT_PROMISOR_ONLY);
2139 }
2140 promisor_objects_prepared = 1;
2141 }
2142 return oidset_contains(&promisor_objects, oid);
2143}