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