packfile.con commit Merge branch 'ls/complete-remote-update-names' (f0209e8)
   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
  19char *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
  29char *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
  35char *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
  41static unsigned int pack_used_ctr;
  42static unsigned int pack_mmap_calls;
  43static unsigned int peak_pack_open_windows;
  44static unsigned int pack_open_windows;
  45static unsigned int pack_open_fds;
  46static unsigned int pack_max_fds;
  47static size_t peak_pack_mapped;
  48static size_t pack_mapped;
  49
  50#define SZ_FMT PRIuMAX
  51static inline uintmax_t sz_fmt(size_t s) { return s; }
  52
  53void 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 */
  79static 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
 182int 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
 199static 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
 207struct 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
 223static 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
 242static 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
 265void 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
 272void 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
 288static 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
 300void 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
 308void close_pack(struct packed_git *p)
 309{
 310        close_pack_windows(p);
 311        close_pack_fd(p);
 312        close_pack_index(p);
 313}
 314
 315void 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 */
 330static 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
 381static 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
 399static 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 */
 444static 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
 525static 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
 533static 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
 546unsigned 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
 619void 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
 628static void try_to_free_pack_memory(size_t size)
 629{
 630        release_pack_memory(size);
 631}
 632
 633struct 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
 686void 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
 695void (*report_garbage)(unsigned seen_bits, const char *path);
 696
 697static 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
 707static 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
 741static 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
 809static 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 */
 817unsigned 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
 835static void *get_next_packed_git(const void *p)
 836{
 837        return ((const struct packed_git *)p)->next;
 838}
 839
 840static void set_next_packed_git(void *p, void *next)
 841{
 842        ((struct packed_git *)p)->next = next;
 843}
 844
 845static 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
 873static 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
 880static 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
 890static 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
 905void 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
 912struct packed_git *get_packed_git(struct repository *r)
 913{
 914        prepare_packed_git(r);
 915        return r->objects->packed_git;
 916}
 917
 918struct list_head *get_packed_git_mru(struct repository *r)
 919{
 920        prepare_packed_git(r);
 921        return &r->objects->packed_git_mru;
 922}
 923
 924unsigned 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
 949unsigned 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
 988int 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
1014void 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
1027const 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
1040static 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 */
1085static 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
1111static 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
1131static 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
1183out:
1184        if (poi_stack != small_poi_stack)
1185                free(poi_stack);
1186        return type;
1187
1188unwind:
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
1199static struct hashmap delta_base_cache;
1200static size_t delta_base_cached;
1201
1202static LIST_HEAD(delta_base_cache_lru);
1203
1204struct delta_base_cache_key {
1205        struct packed_git *p;
1206        off_t base_offset;
1207};
1208
1209struct 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
1218static 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
1227static struct delta_base_cache_entry *
1228get_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
1242static 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
1248static 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
1260static 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 */
1270static 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
1278static 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
1295static 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
1301void 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
1311static 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
1340int 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
1421out:
1422        unuse_pack(&w_curs);
1423        return type;
1424}
1425
1426static 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
1463static 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
1470int do_check_packed_object_crc;
1471
1472#define UNPACK_ENTRY_STACK_PREALLOC 64
1473struct unpack_entry_stack_ent {
1474        off_t obj_offset;
1475        off_t curpos;
1476        unsigned long size;
1477};
1478
1479static 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
1495void *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
1674out:
1675        unuse_pack(&w_curs);
1676
1677        if (delta_stack != small_delta_stack)
1678                free(delta_stack);
1679
1680        return data;
1681}
1682
1683int 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
1707const 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
1728const 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
1739void 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
1753off_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
1772off_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
1790int 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
1811struct 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
1824static 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
1856int 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
1874int 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
1880int 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
1888int 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
1907int 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
1931static 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
1973int 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}