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,
1889                             each_packed_object_fn cb, void *data,
1890                             enum for_each_object_flags flags)
1891 {
1892         uint32_t i;
1893         int r = 0;
1894
1895         if (flags & FOR_EACH_OBJECT_PACK_ORDER)
1896                 load_pack_revindex(p);
1897
1898         for (i = 0; i < p->num_objects; i++) {
1899                 uint32_t pos;
1900                 struct object_id oid;
1901
1902                 if (flags & FOR_EACH_OBJECT_PACK_ORDER)
1903                         pos = p->revindex[i].nr;
1904                 else
1905                         pos = i;
1906
1907                 if (!nth_packed_object_oid(&oid, p, pos))
1908                         return error("unable to get sha1 of object %u in %s",
1909                                      pos, p->pack_name);
1910
1911                 r = cb(&oid, p, pos, data);
1912                 if (r)
1913                         break;
1914         }
1915         return r;
1916 }
1917
1918 int for_each_packed_object(each_packed_object_fn cb, void *data,
1919                            enum for_each_object_flags flags)
1920 {
1921         struct packed_git *p;
1922         int r = 0;
1923         int pack_errors = 0;
1924
1925         prepare_packed_git(the_repository);
1926         for (p = the_repository->objects->packed_git; p; p = p->next) {
1927                 if ((flags & FOR_EACH_OBJECT_LOCAL_ONLY) && !p->pack_local)
1928                         continue;
1929                 if ((flags & FOR_EACH_OBJECT_PROMISOR_ONLY) &&
1930                     !p->pack_promisor)
1931                         continue;
1932                 if (open_pack_index(p)) {
1933                         pack_errors = 1;
1934                         continue;
1935                 }
1936                 r = for_each_object_in_pack(p, cb, data, flags);
1937                 if (r)
1938                         break;
1939         }
1940         return r ? r : pack_errors;
1941 }
1942
1943 static int add_promisor_object(const struct object_id *oid,
1944                                struct packed_git *pack,
1945                                uint32_t pos,
1946                                void *set_)
1947 {
1948         struct oidset *set = set_;
1949         struct object *obj = parse_object(the_repository, oid);
1950         if (!obj)
1951                 return 1;
1952
1953         oidset_insert(set, oid);
1954
1955         /*
1956          * If this is a tree, commit, or tag, the objects it refers
1957          * to are also promisor objects. (Blobs refer to no objects->)
1958          */
1959         if (obj->type == OBJ_TREE) {
1960                 struct tree *tree = (struct tree *)obj;
1961                 struct tree_desc desc;
1962                 struct name_entry entry;
1963                 if (init_tree_desc_gently(&desc, tree->buffer, tree->size))
1964                         /*
1965                          * Error messages are given when packs are
1966                          * verified, so do not print any here.
1967                          */
1968                         return 0;
1969                 while (tree_entry_gently(&desc, &entry))
1970                         oidset_insert(set, entry.oid);
1971         } else if (obj->type == OBJ_COMMIT) {
1972                 struct commit *commit = (struct commit *) obj;
1973                 struct commit_list *parents = commit->parents;
1974
1975                 oidset_insert(set, get_commit_tree_oid(commit));
1976                 for (; parents; parents = parents->next)
1977                         oidset_insert(set, &parents->item->object.oid);
1978         } else if (obj->type == OBJ_TAG) {
1979                 struct tag *tag = (struct tag *) obj;
1980                 oidset_insert(set, &tag->tagged->oid);
1981         }
1982         return 0;
1983 }
1984
1985 int is_promisor_object(const struct object_id *oid)
1986 {
1987         static struct oidset promisor_objects;
1988         static int promisor_objects_prepared;
1989
1990         if (!promisor_objects_prepared) {
1991                 if (repository_format_partial_clone) {
1992                         for_each_packed_object(add_promisor_object,
1993                                                &promisor_objects,
1994                                                FOR_EACH_OBJECT_PROMISOR_ONLY);
1995                 }
1996                 promisor_objects_prepared = 1;
1997         }
1998         return oidset_contains(&promisor_objects, oid);
1999 }