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