sha1_file.con commit Merge branch 'jh/memihash-opt' (c05e123)
   1/*
   2 * GIT - The information manager from hell
   3 *
   4 * Copyright (C) Linus Torvalds, 2005
   5 *
   6 * This handles basic git sha1 object files - packing, unpacking,
   7 * creation etc.
   8 */
   9#include "cache.h"
  10#include "string-list.h"
  11#include "lockfile.h"
  12#include "delta.h"
  13#include "pack.h"
  14#include "blob.h"
  15#include "commit.h"
  16#include "run-command.h"
  17#include "tag.h"
  18#include "tree.h"
  19#include "tree-walk.h"
  20#include "refs.h"
  21#include "pack-revindex.h"
  22#include "sha1-lookup.h"
  23#include "bulk-checkin.h"
  24#include "streaming.h"
  25#include "dir.h"
  26#include "mru.h"
  27#include "list.h"
  28#include "mergesort.h"
  29#include "quote.h"
  30
  31#define SZ_FMT PRIuMAX
  32static inline uintmax_t sz_fmt(size_t s) { return s; }
  33
  34const unsigned char null_sha1[20];
  35const struct object_id null_oid;
  36const struct object_id empty_tree_oid = {
  37        EMPTY_TREE_SHA1_BIN_LITERAL
  38};
  39const struct object_id empty_blob_oid = {
  40        EMPTY_BLOB_SHA1_BIN_LITERAL
  41};
  42
  43/*
  44 * This is meant to hold a *small* number of objects that you would
  45 * want read_sha1_file() to be able to return, but yet you do not want
  46 * to write them into the object store (e.g. a browse-only
  47 * application).
  48 */
  49static struct cached_object {
  50        unsigned char sha1[20];
  51        enum object_type type;
  52        void *buf;
  53        unsigned long size;
  54} *cached_objects;
  55static int cached_object_nr, cached_object_alloc;
  56
  57static struct cached_object empty_tree = {
  58        EMPTY_TREE_SHA1_BIN_LITERAL,
  59        OBJ_TREE,
  60        "",
  61        0
  62};
  63
  64static struct cached_object *find_cached_object(const unsigned char *sha1)
  65{
  66        int i;
  67        struct cached_object *co = cached_objects;
  68
  69        for (i = 0; i < cached_object_nr; i++, co++) {
  70                if (!hashcmp(co->sha1, sha1))
  71                        return co;
  72        }
  73        if (!hashcmp(sha1, empty_tree.sha1))
  74                return &empty_tree;
  75        return NULL;
  76}
  77
  78int mkdir_in_gitdir(const char *path)
  79{
  80        if (mkdir(path, 0777)) {
  81                int saved_errno = errno;
  82                struct stat st;
  83                struct strbuf sb = STRBUF_INIT;
  84
  85                if (errno != EEXIST)
  86                        return -1;
  87                /*
  88                 * Are we looking at a path in a symlinked worktree
  89                 * whose original repository does not yet have it?
  90                 * e.g. .git/rr-cache pointing at its original
  91                 * repository in which the user hasn't performed any
  92                 * conflict resolution yet?
  93                 */
  94                if (lstat(path, &st) || !S_ISLNK(st.st_mode) ||
  95                    strbuf_readlink(&sb, path, st.st_size) ||
  96                    !is_absolute_path(sb.buf) ||
  97                    mkdir(sb.buf, 0777)) {
  98                        strbuf_release(&sb);
  99                        errno = saved_errno;
 100                        return -1;
 101                }
 102                strbuf_release(&sb);
 103        }
 104        return adjust_shared_perm(path);
 105}
 106
 107enum scld_error safe_create_leading_directories(char *path)
 108{
 109        char *next_component = path + offset_1st_component(path);
 110        enum scld_error ret = SCLD_OK;
 111
 112        while (ret == SCLD_OK && next_component) {
 113                struct stat st;
 114                char *slash = next_component, slash_character;
 115
 116                while (*slash && !is_dir_sep(*slash))
 117                        slash++;
 118
 119                if (!*slash)
 120                        break;
 121
 122                next_component = slash + 1;
 123                while (is_dir_sep(*next_component))
 124                        next_component++;
 125                if (!*next_component)
 126                        break;
 127
 128                slash_character = *slash;
 129                *slash = '\0';
 130                if (!stat(path, &st)) {
 131                        /* path exists */
 132                        if (!S_ISDIR(st.st_mode)) {
 133                                errno = ENOTDIR;
 134                                ret = SCLD_EXISTS;
 135                        }
 136                } else if (mkdir(path, 0777)) {
 137                        if (errno == EEXIST &&
 138                            !stat(path, &st) && S_ISDIR(st.st_mode))
 139                                ; /* somebody created it since we checked */
 140                        else if (errno == ENOENT)
 141                                /*
 142                                 * Either mkdir() failed because
 143                                 * somebody just pruned the containing
 144                                 * directory, or stat() failed because
 145                                 * the file that was in our way was
 146                                 * just removed.  Either way, inform
 147                                 * the caller that it might be worth
 148                                 * trying again:
 149                                 */
 150                                ret = SCLD_VANISHED;
 151                        else
 152                                ret = SCLD_FAILED;
 153                } else if (adjust_shared_perm(path)) {
 154                        ret = SCLD_PERMS;
 155                }
 156                *slash = slash_character;
 157        }
 158        return ret;
 159}
 160
 161enum scld_error safe_create_leading_directories_const(const char *path)
 162{
 163        int save_errno;
 164        /* path points to cache entries, so xstrdup before messing with it */
 165        char *buf = xstrdup(path);
 166        enum scld_error result = safe_create_leading_directories(buf);
 167
 168        save_errno = errno;
 169        free(buf);
 170        errno = save_errno;
 171        return result;
 172}
 173
 174int raceproof_create_file(const char *path, create_file_fn fn, void *cb)
 175{
 176        /*
 177         * The number of times we will try to remove empty directories
 178         * in the way of path. This is only 1 because if another
 179         * process is racily creating directories that conflict with
 180         * us, we don't want to fight against them.
 181         */
 182        int remove_directories_remaining = 1;
 183
 184        /*
 185         * The number of times that we will try to create the
 186         * directories containing path. We are willing to attempt this
 187         * more than once, because another process could be trying to
 188         * clean up empty directories at the same time as we are
 189         * trying to create them.
 190         */
 191        int create_directories_remaining = 3;
 192
 193        /* A scratch copy of path, filled lazily if we need it: */
 194        struct strbuf path_copy = STRBUF_INIT;
 195
 196        int ret, save_errno;
 197
 198        /* Sanity check: */
 199        assert(*path);
 200
 201retry_fn:
 202        ret = fn(path, cb);
 203        save_errno = errno;
 204        if (!ret)
 205                goto out;
 206
 207        if (errno == EISDIR && remove_directories_remaining-- > 0) {
 208                /*
 209                 * A directory is in the way. Maybe it is empty; try
 210                 * to remove it:
 211                 */
 212                if (!path_copy.len)
 213                        strbuf_addstr(&path_copy, path);
 214
 215                if (!remove_dir_recursively(&path_copy, REMOVE_DIR_EMPTY_ONLY))
 216                        goto retry_fn;
 217        } else if (errno == ENOENT && create_directories_remaining-- > 0) {
 218                /*
 219                 * Maybe the containing directory didn't exist, or
 220                 * maybe it was just deleted by a process that is
 221                 * racing with us to clean up empty directories. Try
 222                 * to create it:
 223                 */
 224                enum scld_error scld_result;
 225
 226                if (!path_copy.len)
 227                        strbuf_addstr(&path_copy, path);
 228
 229                do {
 230                        scld_result = safe_create_leading_directories(path_copy.buf);
 231                        if (scld_result == SCLD_OK)
 232                                goto retry_fn;
 233                } while (scld_result == SCLD_VANISHED && create_directories_remaining-- > 0);
 234        }
 235
 236out:
 237        strbuf_release(&path_copy);
 238        errno = save_errno;
 239        return ret;
 240}
 241
 242static void fill_sha1_path(struct strbuf *buf, const unsigned char *sha1)
 243{
 244        int i;
 245        for (i = 0; i < 20; i++) {
 246                static char hex[] = "0123456789abcdef";
 247                unsigned int val = sha1[i];
 248                strbuf_addch(buf, hex[val >> 4]);
 249                strbuf_addch(buf, hex[val & 0xf]);
 250                if (!i)
 251                        strbuf_addch(buf, '/');
 252        }
 253}
 254
 255const char *sha1_file_name(const unsigned char *sha1)
 256{
 257        static struct strbuf buf = STRBUF_INIT;
 258
 259        strbuf_reset(&buf);
 260        strbuf_addf(&buf, "%s/", get_object_directory());
 261
 262        fill_sha1_path(&buf, sha1);
 263        return buf.buf;
 264}
 265
 266struct strbuf *alt_scratch_buf(struct alternate_object_database *alt)
 267{
 268        strbuf_setlen(&alt->scratch, alt->base_len);
 269        return &alt->scratch;
 270}
 271
 272static const char *alt_sha1_path(struct alternate_object_database *alt,
 273                                 const unsigned char *sha1)
 274{
 275        struct strbuf *buf = alt_scratch_buf(alt);
 276        fill_sha1_path(buf, sha1);
 277        return buf->buf;
 278}
 279
 280 char *odb_pack_name(struct strbuf *buf,
 281                     const unsigned char *sha1,
 282                     const char *ext)
 283{
 284        strbuf_reset(buf);
 285        strbuf_addf(buf, "%s/pack/pack-%s.%s", get_object_directory(),
 286                    sha1_to_hex(sha1), ext);
 287        return buf->buf;
 288}
 289
 290char *sha1_pack_name(const unsigned char *sha1)
 291{
 292        static struct strbuf buf = STRBUF_INIT;
 293        return odb_pack_name(&buf, sha1, "pack");
 294}
 295
 296char *sha1_pack_index_name(const unsigned char *sha1)
 297{
 298        static struct strbuf buf = STRBUF_INIT;
 299        return odb_pack_name(&buf, sha1, "idx");
 300}
 301
 302struct alternate_object_database *alt_odb_list;
 303static struct alternate_object_database **alt_odb_tail;
 304
 305/*
 306 * Return non-zero iff the path is usable as an alternate object database.
 307 */
 308static int alt_odb_usable(struct strbuf *path, const char *normalized_objdir)
 309{
 310        struct alternate_object_database *alt;
 311
 312        /* Detect cases where alternate disappeared */
 313        if (!is_directory(path->buf)) {
 314                error("object directory %s does not exist; "
 315                      "check .git/objects/info/alternates.",
 316                      path->buf);
 317                return 0;
 318        }
 319
 320        /*
 321         * Prevent the common mistake of listing the same
 322         * thing twice, or object directory itself.
 323         */
 324        for (alt = alt_odb_list; alt; alt = alt->next) {
 325                if (!fspathcmp(path->buf, alt->path))
 326                        return 0;
 327        }
 328        if (!fspathcmp(path->buf, normalized_objdir))
 329                return 0;
 330
 331        return 1;
 332}
 333
 334/*
 335 * Prepare alternate object database registry.
 336 *
 337 * The variable alt_odb_list points at the list of struct
 338 * alternate_object_database.  The elements on this list come from
 339 * non-empty elements from colon separated ALTERNATE_DB_ENVIRONMENT
 340 * environment variable, and $GIT_OBJECT_DIRECTORY/info/alternates,
 341 * whose contents is similar to that environment variable but can be
 342 * LF separated.  Its base points at a statically allocated buffer that
 343 * contains "/the/directory/corresponding/to/.git/objects/...", while
 344 * its name points just after the slash at the end of ".git/objects/"
 345 * in the example above, and has enough space to hold 40-byte hex
 346 * SHA1, an extra slash for the first level indirection, and the
 347 * terminating NUL.
 348 */
 349static int link_alt_odb_entry(const char *entry, const char *relative_base,
 350        int depth, const char *normalized_objdir)
 351{
 352        struct alternate_object_database *ent;
 353        struct strbuf pathbuf = STRBUF_INIT;
 354
 355        if (!is_absolute_path(entry) && relative_base) {
 356                strbuf_realpath(&pathbuf, relative_base, 1);
 357                strbuf_addch(&pathbuf, '/');
 358        }
 359        strbuf_addstr(&pathbuf, entry);
 360
 361        if (strbuf_normalize_path(&pathbuf) < 0 && relative_base) {
 362                error("unable to normalize alternate object path: %s",
 363                      pathbuf.buf);
 364                strbuf_release(&pathbuf);
 365                return -1;
 366        }
 367
 368        /*
 369         * The trailing slash after the directory name is given by
 370         * this function at the end. Remove duplicates.
 371         */
 372        while (pathbuf.len && pathbuf.buf[pathbuf.len - 1] == '/')
 373                strbuf_setlen(&pathbuf, pathbuf.len - 1);
 374
 375        if (!alt_odb_usable(&pathbuf, normalized_objdir)) {
 376                strbuf_release(&pathbuf);
 377                return -1;
 378        }
 379
 380        ent = alloc_alt_odb(pathbuf.buf);
 381
 382        /* add the alternate entry */
 383        *alt_odb_tail = ent;
 384        alt_odb_tail = &(ent->next);
 385        ent->next = NULL;
 386
 387        /* recursively add alternates */
 388        read_info_alternates(pathbuf.buf, depth + 1);
 389
 390        strbuf_release(&pathbuf);
 391        return 0;
 392}
 393
 394static const char *parse_alt_odb_entry(const char *string,
 395                                       int sep,
 396                                       struct strbuf *out)
 397{
 398        const char *end;
 399
 400        strbuf_reset(out);
 401
 402        if (*string == '#') {
 403                /* comment; consume up to next separator */
 404                end = strchrnul(string, sep);
 405        } else if (*string == '"' && !unquote_c_style(out, string, &end)) {
 406                /*
 407                 * quoted path; unquote_c_style has copied the
 408                 * data for us and set "end". Broken quoting (e.g.,
 409                 * an entry that doesn't end with a quote) falls
 410                 * back to the unquoted case below.
 411                 */
 412        } else {
 413                /* normal, unquoted path */
 414                end = strchrnul(string, sep);
 415                strbuf_add(out, string, end - string);
 416        }
 417
 418        if (*end)
 419                end++;
 420        return end;
 421}
 422
 423static void link_alt_odb_entries(const char *alt, int len, int sep,
 424                                 const char *relative_base, int depth)
 425{
 426        struct strbuf objdirbuf = STRBUF_INIT;
 427        struct strbuf entry = STRBUF_INIT;
 428
 429        if (depth > 5) {
 430                error("%s: ignoring alternate object stores, nesting too deep.",
 431                                relative_base);
 432                return;
 433        }
 434
 435        strbuf_add_absolute_path(&objdirbuf, get_object_directory());
 436        if (strbuf_normalize_path(&objdirbuf) < 0)
 437                die("unable to normalize object directory: %s",
 438                    objdirbuf.buf);
 439
 440        while (*alt) {
 441                alt = parse_alt_odb_entry(alt, sep, &entry);
 442                if (!entry.len)
 443                        continue;
 444                link_alt_odb_entry(entry.buf, relative_base, depth, objdirbuf.buf);
 445        }
 446        strbuf_release(&entry);
 447        strbuf_release(&objdirbuf);
 448}
 449
 450void read_info_alternates(const char * relative_base, int depth)
 451{
 452        char *map;
 453        size_t mapsz;
 454        struct stat st;
 455        char *path;
 456        int fd;
 457
 458        path = xstrfmt("%s/info/alternates", relative_base);
 459        fd = git_open(path);
 460        free(path);
 461        if (fd < 0)
 462                return;
 463        if (fstat(fd, &st) || (st.st_size == 0)) {
 464                close(fd);
 465                return;
 466        }
 467        mapsz = xsize_t(st.st_size);
 468        map = xmmap(NULL, mapsz, PROT_READ, MAP_PRIVATE, fd, 0);
 469        close(fd);
 470
 471        link_alt_odb_entries(map, mapsz, '\n', relative_base, depth);
 472
 473        munmap(map, mapsz);
 474}
 475
 476struct alternate_object_database *alloc_alt_odb(const char *dir)
 477{
 478        struct alternate_object_database *ent;
 479
 480        FLEX_ALLOC_STR(ent, path, dir);
 481        strbuf_init(&ent->scratch, 0);
 482        strbuf_addf(&ent->scratch, "%s/", dir);
 483        ent->base_len = ent->scratch.len;
 484
 485        return ent;
 486}
 487
 488void add_to_alternates_file(const char *reference)
 489{
 490        struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
 491        char *alts = git_pathdup("objects/info/alternates");
 492        FILE *in, *out;
 493
 494        hold_lock_file_for_update(lock, alts, LOCK_DIE_ON_ERROR);
 495        out = fdopen_lock_file(lock, "w");
 496        if (!out)
 497                die_errno("unable to fdopen alternates lockfile");
 498
 499        in = fopen(alts, "r");
 500        if (in) {
 501                struct strbuf line = STRBUF_INIT;
 502                int found = 0;
 503
 504                while (strbuf_getline(&line, in) != EOF) {
 505                        if (!strcmp(reference, line.buf)) {
 506                                found = 1;
 507                                break;
 508                        }
 509                        fprintf_or_die(out, "%s\n", line.buf);
 510                }
 511
 512                strbuf_release(&line);
 513                fclose(in);
 514
 515                if (found) {
 516                        rollback_lock_file(lock);
 517                        lock = NULL;
 518                }
 519        }
 520        else if (errno != ENOENT)
 521                die_errno("unable to read alternates file");
 522
 523        if (lock) {
 524                fprintf_or_die(out, "%s\n", reference);
 525                if (commit_lock_file(lock))
 526                        die_errno("unable to move new alternates file into place");
 527                if (alt_odb_tail)
 528                        link_alt_odb_entries(reference, strlen(reference), '\n', NULL, 0);
 529        }
 530        free(alts);
 531}
 532
 533void add_to_alternates_memory(const char *reference)
 534{
 535        /*
 536         * Make sure alternates are initialized, or else our entry may be
 537         * overwritten when they are.
 538         */
 539        prepare_alt_odb();
 540
 541        link_alt_odb_entries(reference, strlen(reference), '\n', NULL, 0);
 542}
 543
 544/*
 545 * Compute the exact path an alternate is at and returns it. In case of
 546 * error NULL is returned and the human readable error is added to `err`
 547 * `path` may be relative and should point to $GITDIR.
 548 * `err` must not be null.
 549 */
 550char *compute_alternate_path(const char *path, struct strbuf *err)
 551{
 552        char *ref_git = NULL;
 553        const char *repo, *ref_git_s;
 554        int seen_error = 0;
 555
 556        ref_git_s = real_path_if_valid(path);
 557        if (!ref_git_s) {
 558                seen_error = 1;
 559                strbuf_addf(err, _("path '%s' does not exist"), path);
 560                goto out;
 561        } else
 562                /*
 563                 * Beware: read_gitfile(), real_path() and mkpath()
 564                 * return static buffer
 565                 */
 566                ref_git = xstrdup(ref_git_s);
 567
 568        repo = read_gitfile(ref_git);
 569        if (!repo)
 570                repo = read_gitfile(mkpath("%s/.git", ref_git));
 571        if (repo) {
 572                free(ref_git);
 573                ref_git = xstrdup(repo);
 574        }
 575
 576        if (!repo && is_directory(mkpath("%s/.git/objects", ref_git))) {
 577                char *ref_git_git = mkpathdup("%s/.git", ref_git);
 578                free(ref_git);
 579                ref_git = ref_git_git;
 580        } else if (!is_directory(mkpath("%s/objects", ref_git))) {
 581                struct strbuf sb = STRBUF_INIT;
 582                seen_error = 1;
 583                if (get_common_dir(&sb, ref_git)) {
 584                        strbuf_addf(err,
 585                                    _("reference repository '%s' as a linked "
 586                                      "checkout is not supported yet."),
 587                                    path);
 588                        goto out;
 589                }
 590
 591                strbuf_addf(err, _("reference repository '%s' is not a "
 592                                        "local repository."), path);
 593                goto out;
 594        }
 595
 596        if (!access(mkpath("%s/shallow", ref_git), F_OK)) {
 597                strbuf_addf(err, _("reference repository '%s' is shallow"),
 598                            path);
 599                seen_error = 1;
 600                goto out;
 601        }
 602
 603        if (!access(mkpath("%s/info/grafts", ref_git), F_OK)) {
 604                strbuf_addf(err,
 605                            _("reference repository '%s' is grafted"),
 606                            path);
 607                seen_error = 1;
 608                goto out;
 609        }
 610
 611out:
 612        if (seen_error) {
 613                free(ref_git);
 614                ref_git = NULL;
 615        }
 616
 617        return ref_git;
 618}
 619
 620int foreach_alt_odb(alt_odb_fn fn, void *cb)
 621{
 622        struct alternate_object_database *ent;
 623        int r = 0;
 624
 625        prepare_alt_odb();
 626        for (ent = alt_odb_list; ent; ent = ent->next) {
 627                r = fn(ent, cb);
 628                if (r)
 629                        break;
 630        }
 631        return r;
 632}
 633
 634void prepare_alt_odb(void)
 635{
 636        const char *alt;
 637
 638        if (alt_odb_tail)
 639                return;
 640
 641        alt = getenv(ALTERNATE_DB_ENVIRONMENT);
 642        if (!alt) alt = "";
 643
 644        alt_odb_tail = &alt_odb_list;
 645        link_alt_odb_entries(alt, strlen(alt), PATH_SEP, NULL, 0);
 646
 647        read_info_alternates(get_object_directory(), 0);
 648}
 649
 650/* Returns 1 if we have successfully freshened the file, 0 otherwise. */
 651static int freshen_file(const char *fn)
 652{
 653        struct utimbuf t;
 654        t.actime = t.modtime = time(NULL);
 655        return !utime(fn, &t);
 656}
 657
 658/*
 659 * All of the check_and_freshen functions return 1 if the file exists and was
 660 * freshened (if freshening was requested), 0 otherwise. If they return
 661 * 0, you should not assume that it is safe to skip a write of the object (it
 662 * either does not exist on disk, or has a stale mtime and may be subject to
 663 * pruning).
 664 */
 665int check_and_freshen_file(const char *fn, int freshen)
 666{
 667        if (access(fn, F_OK))
 668                return 0;
 669        if (freshen && !freshen_file(fn))
 670                return 0;
 671        return 1;
 672}
 673
 674static int check_and_freshen_local(const unsigned char *sha1, int freshen)
 675{
 676        return check_and_freshen_file(sha1_file_name(sha1), freshen);
 677}
 678
 679static int check_and_freshen_nonlocal(const unsigned char *sha1, int freshen)
 680{
 681        struct alternate_object_database *alt;
 682        prepare_alt_odb();
 683        for (alt = alt_odb_list; alt; alt = alt->next) {
 684                const char *path = alt_sha1_path(alt, sha1);
 685                if (check_and_freshen_file(path, freshen))
 686                        return 1;
 687        }
 688        return 0;
 689}
 690
 691static int check_and_freshen(const unsigned char *sha1, int freshen)
 692{
 693        return check_and_freshen_local(sha1, freshen) ||
 694               check_and_freshen_nonlocal(sha1, freshen);
 695}
 696
 697int has_loose_object_nonlocal(const unsigned char *sha1)
 698{
 699        return check_and_freshen_nonlocal(sha1, 0);
 700}
 701
 702static int has_loose_object(const unsigned char *sha1)
 703{
 704        return check_and_freshen(sha1, 0);
 705}
 706
 707static unsigned int pack_used_ctr;
 708static unsigned int pack_mmap_calls;
 709static unsigned int peak_pack_open_windows;
 710static unsigned int pack_open_windows;
 711static unsigned int pack_open_fds;
 712static unsigned int pack_max_fds;
 713static size_t peak_pack_mapped;
 714static size_t pack_mapped;
 715struct packed_git *packed_git;
 716
 717static struct mru packed_git_mru_storage;
 718struct mru *packed_git_mru = &packed_git_mru_storage;
 719
 720void pack_report(void)
 721{
 722        fprintf(stderr,
 723                "pack_report: getpagesize()            = %10" SZ_FMT "\n"
 724                "pack_report: core.packedGitWindowSize = %10" SZ_FMT "\n"
 725                "pack_report: core.packedGitLimit      = %10" SZ_FMT "\n",
 726                sz_fmt(getpagesize()),
 727                sz_fmt(packed_git_window_size),
 728                sz_fmt(packed_git_limit));
 729        fprintf(stderr,
 730                "pack_report: pack_used_ctr            = %10u\n"
 731                "pack_report: pack_mmap_calls          = %10u\n"
 732                "pack_report: pack_open_windows        = %10u / %10u\n"
 733                "pack_report: pack_mapped              = "
 734                        "%10" SZ_FMT " / %10" SZ_FMT "\n",
 735                pack_used_ctr,
 736                pack_mmap_calls,
 737                pack_open_windows, peak_pack_open_windows,
 738                sz_fmt(pack_mapped), sz_fmt(peak_pack_mapped));
 739}
 740
 741/*
 742 * Open and mmap the index file at path, perform a couple of
 743 * consistency checks, then record its information to p.  Return 0 on
 744 * success.
 745 */
 746static int check_packed_git_idx(const char *path, struct packed_git *p)
 747{
 748        void *idx_map;
 749        struct pack_idx_header *hdr;
 750        size_t idx_size;
 751        uint32_t version, nr, i, *index;
 752        int fd = git_open(path);
 753        struct stat st;
 754
 755        if (fd < 0)
 756                return -1;
 757        if (fstat(fd, &st)) {
 758                close(fd);
 759                return -1;
 760        }
 761        idx_size = xsize_t(st.st_size);
 762        if (idx_size < 4 * 256 + 20 + 20) {
 763                close(fd);
 764                return error("index file %s is too small", path);
 765        }
 766        idx_map = xmmap(NULL, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);
 767        close(fd);
 768
 769        hdr = idx_map;
 770        if (hdr->idx_signature == htonl(PACK_IDX_SIGNATURE)) {
 771                version = ntohl(hdr->idx_version);
 772                if (version < 2 || version > 2) {
 773                        munmap(idx_map, idx_size);
 774                        return error("index file %s is version %"PRIu32
 775                                     " and is not supported by this binary"
 776                                     " (try upgrading GIT to a newer version)",
 777                                     path, version);
 778                }
 779        } else
 780                version = 1;
 781
 782        nr = 0;
 783        index = idx_map;
 784        if (version > 1)
 785                index += 2;  /* skip index header */
 786        for (i = 0; i < 256; i++) {
 787                uint32_t n = ntohl(index[i]);
 788                if (n < nr) {
 789                        munmap(idx_map, idx_size);
 790                        return error("non-monotonic index %s", path);
 791                }
 792                nr = n;
 793        }
 794
 795        if (version == 1) {
 796                /*
 797                 * Total size:
 798                 *  - 256 index entries 4 bytes each
 799                 *  - 24-byte entries * nr (20-byte sha1 + 4-byte offset)
 800                 *  - 20-byte SHA1 of the packfile
 801                 *  - 20-byte SHA1 file checksum
 802                 */
 803                if (idx_size != 4*256 + nr * 24 + 20 + 20) {
 804                        munmap(idx_map, idx_size);
 805                        return error("wrong index v1 file size in %s", path);
 806                }
 807        } else if (version == 2) {
 808                /*
 809                 * Minimum size:
 810                 *  - 8 bytes of header
 811                 *  - 256 index entries 4 bytes each
 812                 *  - 20-byte sha1 entry * nr
 813                 *  - 4-byte crc entry * nr
 814                 *  - 4-byte offset entry * nr
 815                 *  - 20-byte SHA1 of the packfile
 816                 *  - 20-byte SHA1 file checksum
 817                 * And after the 4-byte offset table might be a
 818                 * variable sized table containing 8-byte entries
 819                 * for offsets larger than 2^31.
 820                 */
 821                unsigned long min_size = 8 + 4*256 + nr*(20 + 4 + 4) + 20 + 20;
 822                unsigned long max_size = min_size;
 823                if (nr)
 824                        max_size += (nr - 1)*8;
 825                if (idx_size < min_size || idx_size > max_size) {
 826                        munmap(idx_map, idx_size);
 827                        return error("wrong index v2 file size in %s", path);
 828                }
 829                if (idx_size != min_size &&
 830                    /*
 831                     * make sure we can deal with large pack offsets.
 832                     * 31-bit signed offset won't be enough, neither
 833                     * 32-bit unsigned one will be.
 834                     */
 835                    (sizeof(off_t) <= 4)) {
 836                        munmap(idx_map, idx_size);
 837                        return error("pack too large for current definition of off_t in %s", path);
 838                }
 839        }
 840
 841        p->index_version = version;
 842        p->index_data = idx_map;
 843        p->index_size = idx_size;
 844        p->num_objects = nr;
 845        return 0;
 846}
 847
 848int open_pack_index(struct packed_git *p)
 849{
 850        char *idx_name;
 851        size_t len;
 852        int ret;
 853
 854        if (p->index_data)
 855                return 0;
 856
 857        if (!strip_suffix(p->pack_name, ".pack", &len))
 858                die("BUG: pack_name does not end in .pack");
 859        idx_name = xstrfmt("%.*s.idx", (int)len, p->pack_name);
 860        ret = check_packed_git_idx(idx_name, p);
 861        free(idx_name);
 862        return ret;
 863}
 864
 865static void scan_windows(struct packed_git *p,
 866        struct packed_git **lru_p,
 867        struct pack_window **lru_w,
 868        struct pack_window **lru_l)
 869{
 870        struct pack_window *w, *w_l;
 871
 872        for (w_l = NULL, w = p->windows; w; w = w->next) {
 873                if (!w->inuse_cnt) {
 874                        if (!*lru_w || w->last_used < (*lru_w)->last_used) {
 875                                *lru_p = p;
 876                                *lru_w = w;
 877                                *lru_l = w_l;
 878                        }
 879                }
 880                w_l = w;
 881        }
 882}
 883
 884static int unuse_one_window(struct packed_git *current)
 885{
 886        struct packed_git *p, *lru_p = NULL;
 887        struct pack_window *lru_w = NULL, *lru_l = NULL;
 888
 889        if (current)
 890                scan_windows(current, &lru_p, &lru_w, &lru_l);
 891        for (p = packed_git; p; p = p->next)
 892                scan_windows(p, &lru_p, &lru_w, &lru_l);
 893        if (lru_p) {
 894                munmap(lru_w->base, lru_w->len);
 895                pack_mapped -= lru_w->len;
 896                if (lru_l)
 897                        lru_l->next = lru_w->next;
 898                else
 899                        lru_p->windows = lru_w->next;
 900                free(lru_w);
 901                pack_open_windows--;
 902                return 1;
 903        }
 904        return 0;
 905}
 906
 907void release_pack_memory(size_t need)
 908{
 909        size_t cur = pack_mapped;
 910        while (need >= (cur - pack_mapped) && unuse_one_window(NULL))
 911                ; /* nothing */
 912}
 913
 914static void mmap_limit_check(size_t length)
 915{
 916        static size_t limit = 0;
 917        if (!limit) {
 918                limit = git_env_ulong("GIT_MMAP_LIMIT", 0);
 919                if (!limit)
 920                        limit = SIZE_MAX;
 921        }
 922        if (length > limit)
 923                die("attempting to mmap %"PRIuMAX" over limit %"PRIuMAX,
 924                    (uintmax_t)length, (uintmax_t)limit);
 925}
 926
 927void *xmmap_gently(void *start, size_t length,
 928                  int prot, int flags, int fd, off_t offset)
 929{
 930        void *ret;
 931
 932        mmap_limit_check(length);
 933        ret = mmap(start, length, prot, flags, fd, offset);
 934        if (ret == MAP_FAILED) {
 935                if (!length)
 936                        return NULL;
 937                release_pack_memory(length);
 938                ret = mmap(start, length, prot, flags, fd, offset);
 939        }
 940        return ret;
 941}
 942
 943void *xmmap(void *start, size_t length,
 944        int prot, int flags, int fd, off_t offset)
 945{
 946        void *ret = xmmap_gently(start, length, prot, flags, fd, offset);
 947        if (ret == MAP_FAILED)
 948                die_errno("mmap failed");
 949        return ret;
 950}
 951
 952void close_pack_windows(struct packed_git *p)
 953{
 954        while (p->windows) {
 955                struct pack_window *w = p->windows;
 956
 957                if (w->inuse_cnt)
 958                        die("pack '%s' still has open windows to it",
 959                            p->pack_name);
 960                munmap(w->base, w->len);
 961                pack_mapped -= w->len;
 962                pack_open_windows--;
 963                p->windows = w->next;
 964                free(w);
 965        }
 966}
 967
 968static int close_pack_fd(struct packed_git *p)
 969{
 970        if (p->pack_fd < 0)
 971                return 0;
 972
 973        close(p->pack_fd);
 974        pack_open_fds--;
 975        p->pack_fd = -1;
 976
 977        return 1;
 978}
 979
 980static void close_pack(struct packed_git *p)
 981{
 982        close_pack_windows(p);
 983        close_pack_fd(p);
 984        close_pack_index(p);
 985}
 986
 987void close_all_packs(void)
 988{
 989        struct packed_git *p;
 990
 991        for (p = packed_git; p; p = p->next)
 992                if (p->do_not_close)
 993                        die("BUG: want to close pack marked 'do-not-close'");
 994                else
 995                        close_pack(p);
 996}
 997
 998
 999/*
1000 * The LRU pack is the one with the oldest MRU window, preferring packs
1001 * with no used windows, or the oldest mtime if it has no windows allocated.
1002 */
1003static void find_lru_pack(struct packed_git *p, struct packed_git **lru_p, struct pack_window **mru_w, int *accept_windows_inuse)
1004{
1005        struct pack_window *w, *this_mru_w;
1006        int has_windows_inuse = 0;
1007
1008        /*
1009         * Reject this pack if it has windows and the previously selected
1010         * one does not.  If this pack does not have windows, reject
1011         * it if the pack file is newer than the previously selected one.
1012         */
1013        if (*lru_p && !*mru_w && (p->windows || p->mtime > (*lru_p)->mtime))
1014                return;
1015
1016        for (w = this_mru_w = p->windows; w; w = w->next) {
1017                /*
1018                 * Reject this pack if any of its windows are in use,
1019                 * but the previously selected pack did not have any
1020                 * inuse windows.  Otherwise, record that this pack
1021                 * has windows in use.
1022                 */
1023                if (w->inuse_cnt) {
1024                        if (*accept_windows_inuse)
1025                                has_windows_inuse = 1;
1026                        else
1027                                return;
1028                }
1029
1030                if (w->last_used > this_mru_w->last_used)
1031                        this_mru_w = w;
1032
1033                /*
1034                 * Reject this pack if it has windows that have been
1035                 * used more recently than the previously selected pack.
1036                 * If the previously selected pack had windows inuse and
1037                 * we have not encountered a window in this pack that is
1038                 * inuse, skip this check since we prefer a pack with no
1039                 * inuse windows to one that has inuse windows.
1040                 */
1041                if (*mru_w && *accept_windows_inuse == has_windows_inuse &&
1042                    this_mru_w->last_used > (*mru_w)->last_used)
1043                        return;
1044        }
1045
1046        /*
1047         * Select this pack.
1048         */
1049        *mru_w = this_mru_w;
1050        *lru_p = p;
1051        *accept_windows_inuse = has_windows_inuse;
1052}
1053
1054static int close_one_pack(void)
1055{
1056        struct packed_git *p, *lru_p = NULL;
1057        struct pack_window *mru_w = NULL;
1058        int accept_windows_inuse = 1;
1059
1060        for (p = packed_git; p; p = p->next) {
1061                if (p->pack_fd == -1)
1062                        continue;
1063                find_lru_pack(p, &lru_p, &mru_w, &accept_windows_inuse);
1064        }
1065
1066        if (lru_p)
1067                return close_pack_fd(lru_p);
1068
1069        return 0;
1070}
1071
1072void unuse_pack(struct pack_window **w_cursor)
1073{
1074        struct pack_window *w = *w_cursor;
1075        if (w) {
1076                w->inuse_cnt--;
1077                *w_cursor = NULL;
1078        }
1079}
1080
1081void close_pack_index(struct packed_git *p)
1082{
1083        if (p->index_data) {
1084                munmap((void *)p->index_data, p->index_size);
1085                p->index_data = NULL;
1086        }
1087}
1088
1089static unsigned int get_max_fd_limit(void)
1090{
1091#ifdef RLIMIT_NOFILE
1092        {
1093                struct rlimit lim;
1094
1095                if (!getrlimit(RLIMIT_NOFILE, &lim))
1096                        return lim.rlim_cur;
1097        }
1098#endif
1099
1100#ifdef _SC_OPEN_MAX
1101        {
1102                long open_max = sysconf(_SC_OPEN_MAX);
1103                if (0 < open_max)
1104                        return open_max;
1105                /*
1106                 * Otherwise, we got -1 for one of the two
1107                 * reasons:
1108                 *
1109                 * (1) sysconf() did not understand _SC_OPEN_MAX
1110                 *     and signaled an error with -1; or
1111                 * (2) sysconf() said there is no limit.
1112                 *
1113                 * We _could_ clear errno before calling sysconf() to
1114                 * tell these two cases apart and return a huge number
1115                 * in the latter case to let the caller cap it to a
1116                 * value that is not so selfish, but letting the
1117                 * fallback OPEN_MAX codepath take care of these cases
1118                 * is a lot simpler.
1119                 */
1120        }
1121#endif
1122
1123#ifdef OPEN_MAX
1124        return OPEN_MAX;
1125#else
1126        return 1; /* see the caller ;-) */
1127#endif
1128}
1129
1130/*
1131 * Do not call this directly as this leaks p->pack_fd on error return;
1132 * call open_packed_git() instead.
1133 */
1134static int open_packed_git_1(struct packed_git *p)
1135{
1136        struct stat st;
1137        struct pack_header hdr;
1138        unsigned char sha1[20];
1139        unsigned char *idx_sha1;
1140        long fd_flag;
1141
1142        if (!p->index_data && open_pack_index(p))
1143                return error("packfile %s index unavailable", p->pack_name);
1144
1145        if (!pack_max_fds) {
1146                unsigned int max_fds = get_max_fd_limit();
1147
1148                /* Save 3 for stdin/stdout/stderr, 22 for work */
1149                if (25 < max_fds)
1150                        pack_max_fds = max_fds - 25;
1151                else
1152                        pack_max_fds = 1;
1153        }
1154
1155        while (pack_max_fds <= pack_open_fds && close_one_pack())
1156                ; /* nothing */
1157
1158        p->pack_fd = git_open(p->pack_name);
1159        if (p->pack_fd < 0 || fstat(p->pack_fd, &st))
1160                return -1;
1161        pack_open_fds++;
1162
1163        /* If we created the struct before we had the pack we lack size. */
1164        if (!p->pack_size) {
1165                if (!S_ISREG(st.st_mode))
1166                        return error("packfile %s not a regular file", p->pack_name);
1167                p->pack_size = st.st_size;
1168        } else if (p->pack_size != st.st_size)
1169                return error("packfile %s size changed", p->pack_name);
1170
1171        /* We leave these file descriptors open with sliding mmap;
1172         * there is no point keeping them open across exec(), though.
1173         */
1174        fd_flag = fcntl(p->pack_fd, F_GETFD, 0);
1175        if (fd_flag < 0)
1176                return error("cannot determine file descriptor flags");
1177        fd_flag |= FD_CLOEXEC;
1178        if (fcntl(p->pack_fd, F_SETFD, fd_flag) == -1)
1179                return error("cannot set FD_CLOEXEC");
1180
1181        /* Verify we recognize this pack file format. */
1182        if (read_in_full(p->pack_fd, &hdr, sizeof(hdr)) != sizeof(hdr))
1183                return error("file %s is far too short to be a packfile", p->pack_name);
1184        if (hdr.hdr_signature != htonl(PACK_SIGNATURE))
1185                return error("file %s is not a GIT packfile", p->pack_name);
1186        if (!pack_version_ok(hdr.hdr_version))
1187                return error("packfile %s is version %"PRIu32" and not"
1188                        " supported (try upgrading GIT to a newer version)",
1189                        p->pack_name, ntohl(hdr.hdr_version));
1190
1191        /* Verify the pack matches its index. */
1192        if (p->num_objects != ntohl(hdr.hdr_entries))
1193                return error("packfile %s claims to have %"PRIu32" objects"
1194                             " while index indicates %"PRIu32" objects",
1195                             p->pack_name, ntohl(hdr.hdr_entries),
1196                             p->num_objects);
1197        if (lseek(p->pack_fd, p->pack_size - sizeof(sha1), SEEK_SET) == -1)
1198                return error("end of packfile %s is unavailable", p->pack_name);
1199        if (read_in_full(p->pack_fd, sha1, sizeof(sha1)) != sizeof(sha1))
1200                return error("packfile %s signature is unavailable", p->pack_name);
1201        idx_sha1 = ((unsigned char *)p->index_data) + p->index_size - 40;
1202        if (hashcmp(sha1, idx_sha1))
1203                return error("packfile %s does not match index", p->pack_name);
1204        return 0;
1205}
1206
1207static int open_packed_git(struct packed_git *p)
1208{
1209        if (!open_packed_git_1(p))
1210                return 0;
1211        close_pack_fd(p);
1212        return -1;
1213}
1214
1215static int in_window(struct pack_window *win, off_t offset)
1216{
1217        /* We must promise at least 20 bytes (one hash) after the
1218         * offset is available from this window, otherwise the offset
1219         * is not actually in this window and a different window (which
1220         * has that one hash excess) must be used.  This is to support
1221         * the object header and delta base parsing routines below.
1222         */
1223        off_t win_off = win->offset;
1224        return win_off <= offset
1225                && (offset + 20) <= (win_off + win->len);
1226}
1227
1228unsigned char *use_pack(struct packed_git *p,
1229                struct pack_window **w_cursor,
1230                off_t offset,
1231                unsigned long *left)
1232{
1233        struct pack_window *win = *w_cursor;
1234
1235        /* Since packfiles end in a hash of their content and it's
1236         * pointless to ask for an offset into the middle of that
1237         * hash, and the in_window function above wouldn't match
1238         * don't allow an offset too close to the end of the file.
1239         */
1240        if (!p->pack_size && p->pack_fd == -1 && open_packed_git(p))
1241                die("packfile %s cannot be accessed", p->pack_name);
1242        if (offset > (p->pack_size - 20))
1243                die("offset beyond end of packfile (truncated pack?)");
1244        if (offset < 0)
1245                die(_("offset before end of packfile (broken .idx?)"));
1246
1247        if (!win || !in_window(win, offset)) {
1248                if (win)
1249                        win->inuse_cnt--;
1250                for (win = p->windows; win; win = win->next) {
1251                        if (in_window(win, offset))
1252                                break;
1253                }
1254                if (!win) {
1255                        size_t window_align = packed_git_window_size / 2;
1256                        off_t len;
1257
1258                        if (p->pack_fd == -1 && open_packed_git(p))
1259                                die("packfile %s cannot be accessed", p->pack_name);
1260
1261                        win = xcalloc(1, sizeof(*win));
1262                        win->offset = (offset / window_align) * window_align;
1263                        len = p->pack_size - win->offset;
1264                        if (len > packed_git_window_size)
1265                                len = packed_git_window_size;
1266                        win->len = (size_t)len;
1267                        pack_mapped += win->len;
1268                        while (packed_git_limit < pack_mapped
1269                                && unuse_one_window(p))
1270                                ; /* nothing */
1271                        win->base = xmmap(NULL, win->len,
1272                                PROT_READ, MAP_PRIVATE,
1273                                p->pack_fd, win->offset);
1274                        if (win->base == MAP_FAILED)
1275                                die_errno("packfile %s cannot be mapped",
1276                                          p->pack_name);
1277                        if (!win->offset && win->len == p->pack_size
1278                                && !p->do_not_close)
1279                                close_pack_fd(p);
1280                        pack_mmap_calls++;
1281                        pack_open_windows++;
1282                        if (pack_mapped > peak_pack_mapped)
1283                                peak_pack_mapped = pack_mapped;
1284                        if (pack_open_windows > peak_pack_open_windows)
1285                                peak_pack_open_windows = pack_open_windows;
1286                        win->next = p->windows;
1287                        p->windows = win;
1288                }
1289        }
1290        if (win != *w_cursor) {
1291                win->last_used = pack_used_ctr++;
1292                win->inuse_cnt++;
1293                *w_cursor = win;
1294        }
1295        offset -= win->offset;
1296        if (left)
1297                *left = win->len - xsize_t(offset);
1298        return win->base + offset;
1299}
1300
1301static struct packed_git *alloc_packed_git(int extra)
1302{
1303        struct packed_git *p = xmalloc(st_add(sizeof(*p), extra));
1304        memset(p, 0, sizeof(*p));
1305        p->pack_fd = -1;
1306        return p;
1307}
1308
1309static void try_to_free_pack_memory(size_t size)
1310{
1311        release_pack_memory(size);
1312}
1313
1314struct packed_git *add_packed_git(const char *path, size_t path_len, int local)
1315{
1316        static int have_set_try_to_free_routine;
1317        struct stat st;
1318        size_t alloc;
1319        struct packed_git *p;
1320
1321        if (!have_set_try_to_free_routine) {
1322                have_set_try_to_free_routine = 1;
1323                set_try_to_free_routine(try_to_free_pack_memory);
1324        }
1325
1326        /*
1327         * Make sure a corresponding .pack file exists and that
1328         * the index looks sane.
1329         */
1330        if (!strip_suffix_mem(path, &path_len, ".idx"))
1331                return NULL;
1332
1333        /*
1334         * ".pack" is long enough to hold any suffix we're adding (and
1335         * the use xsnprintf double-checks that)
1336         */
1337        alloc = st_add3(path_len, strlen(".pack"), 1);
1338        p = alloc_packed_git(alloc);
1339        memcpy(p->pack_name, path, path_len);
1340
1341        xsnprintf(p->pack_name + path_len, alloc - path_len, ".keep");
1342        if (!access(p->pack_name, F_OK))
1343                p->pack_keep = 1;
1344
1345        xsnprintf(p->pack_name + path_len, alloc - path_len, ".pack");
1346        if (stat(p->pack_name, &st) || !S_ISREG(st.st_mode)) {
1347                free(p);
1348                return NULL;
1349        }
1350
1351        /* ok, it looks sane as far as we can check without
1352         * actually mapping the pack file.
1353         */
1354        p->pack_size = st.st_size;
1355        p->pack_local = local;
1356        p->mtime = st.st_mtime;
1357        if (path_len < 40 || get_sha1_hex(path + path_len - 40, p->sha1))
1358                hashclr(p->sha1);
1359        return p;
1360}
1361
1362struct packed_git *parse_pack_index(unsigned char *sha1, const char *idx_path)
1363{
1364        const char *path = sha1_pack_name(sha1);
1365        size_t alloc = st_add(strlen(path), 1);
1366        struct packed_git *p = alloc_packed_git(alloc);
1367
1368        memcpy(p->pack_name, path, alloc); /* includes NUL */
1369        hashcpy(p->sha1, sha1);
1370        if (check_packed_git_idx(idx_path, p)) {
1371                free(p);
1372                return NULL;
1373        }
1374
1375        return p;
1376}
1377
1378void install_packed_git(struct packed_git *pack)
1379{
1380        if (pack->pack_fd != -1)
1381                pack_open_fds++;
1382
1383        pack->next = packed_git;
1384        packed_git = pack;
1385}
1386
1387void (*report_garbage)(unsigned seen_bits, const char *path);
1388
1389static void report_helper(const struct string_list *list,
1390                          int seen_bits, int first, int last)
1391{
1392        if (seen_bits == (PACKDIR_FILE_PACK|PACKDIR_FILE_IDX))
1393                return;
1394
1395        for (; first < last; first++)
1396                report_garbage(seen_bits, list->items[first].string);
1397}
1398
1399static void report_pack_garbage(struct string_list *list)
1400{
1401        int i, baselen = -1, first = 0, seen_bits = 0;
1402
1403        if (!report_garbage)
1404                return;
1405
1406        string_list_sort(list);
1407
1408        for (i = 0; i < list->nr; i++) {
1409                const char *path = list->items[i].string;
1410                if (baselen != -1 &&
1411                    strncmp(path, list->items[first].string, baselen)) {
1412                        report_helper(list, seen_bits, first, i);
1413                        baselen = -1;
1414                        seen_bits = 0;
1415                }
1416                if (baselen == -1) {
1417                        const char *dot = strrchr(path, '.');
1418                        if (!dot) {
1419                                report_garbage(PACKDIR_FILE_GARBAGE, path);
1420                                continue;
1421                        }
1422                        baselen = dot - path + 1;
1423                        first = i;
1424                }
1425                if (!strcmp(path + baselen, "pack"))
1426                        seen_bits |= 1;
1427                else if (!strcmp(path + baselen, "idx"))
1428                        seen_bits |= 2;
1429        }
1430        report_helper(list, seen_bits, first, list->nr);
1431}
1432
1433static void prepare_packed_git_one(char *objdir, int local)
1434{
1435        struct strbuf path = STRBUF_INIT;
1436        size_t dirnamelen;
1437        DIR *dir;
1438        struct dirent *de;
1439        struct string_list garbage = STRING_LIST_INIT_DUP;
1440
1441        strbuf_addstr(&path, objdir);
1442        strbuf_addstr(&path, "/pack");
1443        dir = opendir(path.buf);
1444        if (!dir) {
1445                if (errno != ENOENT)
1446                        error_errno("unable to open object pack directory: %s",
1447                                    path.buf);
1448                strbuf_release(&path);
1449                return;
1450        }
1451        strbuf_addch(&path, '/');
1452        dirnamelen = path.len;
1453        while ((de = readdir(dir)) != NULL) {
1454                struct packed_git *p;
1455                size_t base_len;
1456
1457                if (is_dot_or_dotdot(de->d_name))
1458                        continue;
1459
1460                strbuf_setlen(&path, dirnamelen);
1461                strbuf_addstr(&path, de->d_name);
1462
1463                base_len = path.len;
1464                if (strip_suffix_mem(path.buf, &base_len, ".idx")) {
1465                        /* Don't reopen a pack we already have. */
1466                        for (p = packed_git; p; p = p->next) {
1467                                size_t len;
1468                                if (strip_suffix(p->pack_name, ".pack", &len) &&
1469                                    len == base_len &&
1470                                    !memcmp(p->pack_name, path.buf, len))
1471                                        break;
1472                        }
1473                        if (p == NULL &&
1474                            /*
1475                             * See if it really is a valid .idx file with
1476                             * corresponding .pack file that we can map.
1477                             */
1478                            (p = add_packed_git(path.buf, path.len, local)) != NULL)
1479                                install_packed_git(p);
1480                }
1481
1482                if (!report_garbage)
1483                        continue;
1484
1485                if (ends_with(de->d_name, ".idx") ||
1486                    ends_with(de->d_name, ".pack") ||
1487                    ends_with(de->d_name, ".bitmap") ||
1488                    ends_with(de->d_name, ".keep"))
1489                        string_list_append(&garbage, path.buf);
1490                else
1491                        report_garbage(PACKDIR_FILE_GARBAGE, path.buf);
1492        }
1493        closedir(dir);
1494        report_pack_garbage(&garbage);
1495        string_list_clear(&garbage, 0);
1496        strbuf_release(&path);
1497}
1498
1499static int approximate_object_count_valid;
1500
1501/*
1502 * Give a fast, rough count of the number of objects in the repository. This
1503 * ignores loose objects completely. If you have a lot of them, then either
1504 * you should repack because your performance will be awful, or they are
1505 * all unreachable objects about to be pruned, in which case they're not really
1506 * interesting as a measure of repo size in the first place.
1507 */
1508unsigned long approximate_object_count(void)
1509{
1510        static unsigned long count;
1511        if (!approximate_object_count_valid) {
1512                struct packed_git *p;
1513
1514                prepare_packed_git();
1515                count = 0;
1516                for (p = packed_git; p; p = p->next) {
1517                        if (open_pack_index(p))
1518                                continue;
1519                        count += p->num_objects;
1520                }
1521        }
1522        return count;
1523}
1524
1525static void *get_next_packed_git(const void *p)
1526{
1527        return ((const struct packed_git *)p)->next;
1528}
1529
1530static void set_next_packed_git(void *p, void *next)
1531{
1532        ((struct packed_git *)p)->next = next;
1533}
1534
1535static int sort_pack(const void *a_, const void *b_)
1536{
1537        const struct packed_git *a = a_;
1538        const struct packed_git *b = b_;
1539        int st;
1540
1541        /*
1542         * Local packs tend to contain objects specific to our
1543         * variant of the project than remote ones.  In addition,
1544         * remote ones could be on a network mounted filesystem.
1545         * Favor local ones for these reasons.
1546         */
1547        st = a->pack_local - b->pack_local;
1548        if (st)
1549                return -st;
1550
1551        /*
1552         * Younger packs tend to contain more recent objects,
1553         * and more recent objects tend to get accessed more
1554         * often.
1555         */
1556        if (a->mtime < b->mtime)
1557                return 1;
1558        else if (a->mtime == b->mtime)
1559                return 0;
1560        return -1;
1561}
1562
1563static void rearrange_packed_git(void)
1564{
1565        packed_git = llist_mergesort(packed_git, get_next_packed_git,
1566                                     set_next_packed_git, sort_pack);
1567}
1568
1569static void prepare_packed_git_mru(void)
1570{
1571        struct packed_git *p;
1572
1573        mru_clear(packed_git_mru);
1574        for (p = packed_git; p; p = p->next)
1575                mru_append(packed_git_mru, p);
1576}
1577
1578static int prepare_packed_git_run_once = 0;
1579void prepare_packed_git(void)
1580{
1581        struct alternate_object_database *alt;
1582
1583        if (prepare_packed_git_run_once)
1584                return;
1585        prepare_packed_git_one(get_object_directory(), 1);
1586        prepare_alt_odb();
1587        for (alt = alt_odb_list; alt; alt = alt->next)
1588                prepare_packed_git_one(alt->path, 0);
1589        rearrange_packed_git();
1590        prepare_packed_git_mru();
1591        prepare_packed_git_run_once = 1;
1592}
1593
1594void reprepare_packed_git(void)
1595{
1596        approximate_object_count_valid = 0;
1597        prepare_packed_git_run_once = 0;
1598        prepare_packed_git();
1599}
1600
1601static void mark_bad_packed_object(struct packed_git *p,
1602                                   const unsigned char *sha1)
1603{
1604        unsigned i;
1605        for (i = 0; i < p->num_bad_objects; i++)
1606                if (!hashcmp(sha1, p->bad_object_sha1 + GIT_SHA1_RAWSZ * i))
1607                        return;
1608        p->bad_object_sha1 = xrealloc(p->bad_object_sha1,
1609                                      st_mult(GIT_MAX_RAWSZ,
1610                                              st_add(p->num_bad_objects, 1)));
1611        hashcpy(p->bad_object_sha1 + GIT_SHA1_RAWSZ * p->num_bad_objects, sha1);
1612        p->num_bad_objects++;
1613}
1614
1615static const struct packed_git *has_packed_and_bad(const unsigned char *sha1)
1616{
1617        struct packed_git *p;
1618        unsigned i;
1619
1620        for (p = packed_git; p; p = p->next)
1621                for (i = 0; i < p->num_bad_objects; i++)
1622                        if (!hashcmp(sha1, p->bad_object_sha1 + 20 * i))
1623                                return p;
1624        return NULL;
1625}
1626
1627/*
1628 * With an in-core object data in "map", rehash it to make sure the
1629 * object name actually matches "sha1" to detect object corruption.
1630 * With "map" == NULL, try reading the object named with "sha1" using
1631 * the streaming interface and rehash it to do the same.
1632 */
1633int check_sha1_signature(const unsigned char *sha1, void *map,
1634                         unsigned long size, const char *type)
1635{
1636        unsigned char real_sha1[20];
1637        enum object_type obj_type;
1638        struct git_istream *st;
1639        git_SHA_CTX c;
1640        char hdr[32];
1641        int hdrlen;
1642
1643        if (map) {
1644                hash_sha1_file(map, size, type, real_sha1);
1645                return hashcmp(sha1, real_sha1) ? -1 : 0;
1646        }
1647
1648        st = open_istream(sha1, &obj_type, &size, NULL);
1649        if (!st)
1650                return -1;
1651
1652        /* Generate the header */
1653        hdrlen = xsnprintf(hdr, sizeof(hdr), "%s %lu", typename(obj_type), size) + 1;
1654
1655        /* Sha1.. */
1656        git_SHA1_Init(&c);
1657        git_SHA1_Update(&c, hdr, hdrlen);
1658        for (;;) {
1659                char buf[1024 * 16];
1660                ssize_t readlen = read_istream(st, buf, sizeof(buf));
1661
1662                if (readlen < 0) {
1663                        close_istream(st);
1664                        return -1;
1665                }
1666                if (!readlen)
1667                        break;
1668                git_SHA1_Update(&c, buf, readlen);
1669        }
1670        git_SHA1_Final(real_sha1, &c);
1671        close_istream(st);
1672        return hashcmp(sha1, real_sha1) ? -1 : 0;
1673}
1674
1675int git_open_cloexec(const char *name, int flags)
1676{
1677        int fd;
1678        static int o_cloexec = O_CLOEXEC;
1679
1680        fd = open(name, flags | o_cloexec);
1681        if ((o_cloexec & O_CLOEXEC) && fd < 0 && errno == EINVAL) {
1682                /* Try again w/o O_CLOEXEC: the kernel might not support it */
1683                o_cloexec &= ~O_CLOEXEC;
1684                fd = open(name, flags | o_cloexec);
1685        }
1686
1687#if defined(F_GETFL) && defined(F_SETFL) && defined(FD_CLOEXEC)
1688        {
1689                static int fd_cloexec = FD_CLOEXEC;
1690
1691                if (!o_cloexec && 0 <= fd && fd_cloexec) {
1692                        /* Opened w/o O_CLOEXEC?  try with fcntl(2) to add it */
1693                        int flags = fcntl(fd, F_GETFL);
1694                        if (fcntl(fd, F_SETFL, flags | fd_cloexec))
1695                                fd_cloexec = 0;
1696                }
1697        }
1698#endif
1699        return fd;
1700}
1701
1702/*
1703 * Find "sha1" as a loose object in the local repository or in an alternate.
1704 * Returns 0 on success, negative on failure.
1705 *
1706 * The "path" out-parameter will give the path of the object we found (if any).
1707 * Note that it may point to static storage and is only valid until another
1708 * call to sha1_file_name(), etc.
1709 */
1710static int stat_sha1_file(const unsigned char *sha1, struct stat *st,
1711                          const char **path)
1712{
1713        struct alternate_object_database *alt;
1714
1715        *path = sha1_file_name(sha1);
1716        if (!lstat(*path, st))
1717                return 0;
1718
1719        prepare_alt_odb();
1720        errno = ENOENT;
1721        for (alt = alt_odb_list; alt; alt = alt->next) {
1722                *path = alt_sha1_path(alt, sha1);
1723                if (!lstat(*path, st))
1724                        return 0;
1725        }
1726
1727        return -1;
1728}
1729
1730/*
1731 * Like stat_sha1_file(), but actually open the object and return the
1732 * descriptor. See the caveats on the "path" parameter above.
1733 */
1734static int open_sha1_file(const unsigned char *sha1, const char **path)
1735{
1736        int fd;
1737        struct alternate_object_database *alt;
1738        int most_interesting_errno;
1739
1740        *path = sha1_file_name(sha1);
1741        fd = git_open(*path);
1742        if (fd >= 0)
1743                return fd;
1744        most_interesting_errno = errno;
1745
1746        prepare_alt_odb();
1747        for (alt = alt_odb_list; alt; alt = alt->next) {
1748                *path = alt_sha1_path(alt, sha1);
1749                fd = git_open(*path);
1750                if (fd >= 0)
1751                        return fd;
1752                if (most_interesting_errno == ENOENT)
1753                        most_interesting_errno = errno;
1754        }
1755        errno = most_interesting_errno;
1756        return -1;
1757}
1758
1759/*
1760 * Map the loose object at "path" if it is not NULL, or the path found by
1761 * searching for a loose object named "sha1".
1762 */
1763static void *map_sha1_file_1(const char *path,
1764                             const unsigned char *sha1,
1765                             unsigned long *size)
1766{
1767        void *map;
1768        int fd;
1769
1770        if (path)
1771                fd = git_open(path);
1772        else
1773                fd = open_sha1_file(sha1, &path);
1774        map = NULL;
1775        if (fd >= 0) {
1776                struct stat st;
1777
1778                if (!fstat(fd, &st)) {
1779                        *size = xsize_t(st.st_size);
1780                        if (!*size) {
1781                                /* mmap() is forbidden on empty files */
1782                                error("object file %s is empty", path);
1783                                return NULL;
1784                        }
1785                        map = xmmap(NULL, *size, PROT_READ, MAP_PRIVATE, fd, 0);
1786                }
1787                close(fd);
1788        }
1789        return map;
1790}
1791
1792void *map_sha1_file(const unsigned char *sha1, unsigned long *size)
1793{
1794        return map_sha1_file_1(NULL, sha1, size);
1795}
1796
1797unsigned long unpack_object_header_buffer(const unsigned char *buf,
1798                unsigned long len, enum object_type *type, unsigned long *sizep)
1799{
1800        unsigned shift;
1801        unsigned long size, c;
1802        unsigned long used = 0;
1803
1804        c = buf[used++];
1805        *type = (c >> 4) & 7;
1806        size = c & 15;
1807        shift = 4;
1808        while (c & 0x80) {
1809                if (len <= used || bitsizeof(long) <= shift) {
1810                        error("bad object header");
1811                        size = used = 0;
1812                        break;
1813                }
1814                c = buf[used++];
1815                size += (c & 0x7f) << shift;
1816                shift += 7;
1817        }
1818        *sizep = size;
1819        return used;
1820}
1821
1822static int unpack_sha1_short_header(git_zstream *stream,
1823                                    unsigned char *map, unsigned long mapsize,
1824                                    void *buffer, unsigned long bufsiz)
1825{
1826        /* Get the data stream */
1827        memset(stream, 0, sizeof(*stream));
1828        stream->next_in = map;
1829        stream->avail_in = mapsize;
1830        stream->next_out = buffer;
1831        stream->avail_out = bufsiz;
1832
1833        git_inflate_init(stream);
1834        return git_inflate(stream, 0);
1835}
1836
1837int unpack_sha1_header(git_zstream *stream,
1838                       unsigned char *map, unsigned long mapsize,
1839                       void *buffer, unsigned long bufsiz)
1840{
1841        int status = unpack_sha1_short_header(stream, map, mapsize,
1842                                              buffer, bufsiz);
1843
1844        if (status < Z_OK)
1845                return status;
1846
1847        /* Make sure we have the terminating NUL */
1848        if (!memchr(buffer, '\0', stream->next_out - (unsigned char *)buffer))
1849                return -1;
1850        return 0;
1851}
1852
1853static int unpack_sha1_header_to_strbuf(git_zstream *stream, unsigned char *map,
1854                                        unsigned long mapsize, void *buffer,
1855                                        unsigned long bufsiz, struct strbuf *header)
1856{
1857        int status;
1858
1859        status = unpack_sha1_short_header(stream, map, mapsize, buffer, bufsiz);
1860        if (status < Z_OK)
1861                return -1;
1862
1863        /*
1864         * Check if entire header is unpacked in the first iteration.
1865         */
1866        if (memchr(buffer, '\0', stream->next_out - (unsigned char *)buffer))
1867                return 0;
1868
1869        /*
1870         * buffer[0..bufsiz] was not large enough.  Copy the partial
1871         * result out to header, and then append the result of further
1872         * reading the stream.
1873         */
1874        strbuf_add(header, buffer, stream->next_out - (unsigned char *)buffer);
1875        stream->next_out = buffer;
1876        stream->avail_out = bufsiz;
1877
1878        do {
1879                status = git_inflate(stream, 0);
1880                strbuf_add(header, buffer, stream->next_out - (unsigned char *)buffer);
1881                if (memchr(buffer, '\0', stream->next_out - (unsigned char *)buffer))
1882                        return 0;
1883                stream->next_out = buffer;
1884                stream->avail_out = bufsiz;
1885        } while (status != Z_STREAM_END);
1886        return -1;
1887}
1888
1889static void *unpack_sha1_rest(git_zstream *stream, void *buffer, unsigned long size, const unsigned char *sha1)
1890{
1891        int bytes = strlen(buffer) + 1;
1892        unsigned char *buf = xmallocz(size);
1893        unsigned long n;
1894        int status = Z_OK;
1895
1896        n = stream->total_out - bytes;
1897        if (n > size)
1898                n = size;
1899        memcpy(buf, (char *) buffer + bytes, n);
1900        bytes = n;
1901        if (bytes <= size) {
1902                /*
1903                 * The above condition must be (bytes <= size), not
1904                 * (bytes < size).  In other words, even though we
1905                 * expect no more output and set avail_out to zero,
1906                 * the input zlib stream may have bytes that express
1907                 * "this concludes the stream", and we *do* want to
1908                 * eat that input.
1909                 *
1910                 * Otherwise we would not be able to test that we
1911                 * consumed all the input to reach the expected size;
1912                 * we also want to check that zlib tells us that all
1913                 * went well with status == Z_STREAM_END at the end.
1914                 */
1915                stream->next_out = buf + bytes;
1916                stream->avail_out = size - bytes;
1917                while (status == Z_OK)
1918                        status = git_inflate(stream, Z_FINISH);
1919        }
1920        if (status == Z_STREAM_END && !stream->avail_in) {
1921                git_inflate_end(stream);
1922                return buf;
1923        }
1924
1925        if (status < 0)
1926                error("corrupt loose object '%s'", sha1_to_hex(sha1));
1927        else if (stream->avail_in)
1928                error("garbage at end of loose object '%s'",
1929                      sha1_to_hex(sha1));
1930        free(buf);
1931        return NULL;
1932}
1933
1934/*
1935 * We used to just use "sscanf()", but that's actually way
1936 * too permissive for what we want to check. So do an anal
1937 * object header parse by hand.
1938 */
1939static int parse_sha1_header_extended(const char *hdr, struct object_info *oi,
1940                               unsigned int flags)
1941{
1942        const char *type_buf = hdr;
1943        unsigned long size;
1944        int type, type_len = 0;
1945
1946        /*
1947         * The type can be of any size but is followed by
1948         * a space.
1949         */
1950        for (;;) {
1951                char c = *hdr++;
1952                if (!c)
1953                        return -1;
1954                if (c == ' ')
1955                        break;
1956                type_len++;
1957        }
1958
1959        type = type_from_string_gently(type_buf, type_len, 1);
1960        if (oi->typename)
1961                strbuf_add(oi->typename, type_buf, type_len);
1962        /*
1963         * Set type to 0 if its an unknown object and
1964         * we're obtaining the type using '--allow-unknown-type'
1965         * option.
1966         */
1967        if ((flags & LOOKUP_UNKNOWN_OBJECT) && (type < 0))
1968                type = 0;
1969        else if (type < 0)
1970                die("invalid object type");
1971        if (oi->typep)
1972                *oi->typep = type;
1973
1974        /*
1975         * The length must follow immediately, and be in canonical
1976         * decimal format (ie "010" is not valid).
1977         */
1978        size = *hdr++ - '0';
1979        if (size > 9)
1980                return -1;
1981        if (size) {
1982                for (;;) {
1983                        unsigned long c = *hdr - '0';
1984                        if (c > 9)
1985                                break;
1986                        hdr++;
1987                        size = size * 10 + c;
1988                }
1989        }
1990
1991        if (oi->sizep)
1992                *oi->sizep = size;
1993
1994        /*
1995         * The length must be followed by a zero byte
1996         */
1997        return *hdr ? -1 : type;
1998}
1999
2000int parse_sha1_header(const char *hdr, unsigned long *sizep)
2001{
2002        struct object_info oi = OBJECT_INFO_INIT;
2003
2004        oi.sizep = sizep;
2005        return parse_sha1_header_extended(hdr, &oi, LOOKUP_REPLACE_OBJECT);
2006}
2007
2008static void *unpack_sha1_file(void *map, unsigned long mapsize, enum object_type *type, unsigned long *size, const unsigned char *sha1)
2009{
2010        int ret;
2011        git_zstream stream;
2012        char hdr[8192];
2013
2014        ret = unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr));
2015        if (ret < Z_OK || (*type = parse_sha1_header(hdr, size)) < 0)
2016                return NULL;
2017
2018        return unpack_sha1_rest(&stream, hdr, *size, sha1);
2019}
2020
2021unsigned long get_size_from_delta(struct packed_git *p,
2022                                  struct pack_window **w_curs,
2023                                  off_t curpos)
2024{
2025        const unsigned char *data;
2026        unsigned char delta_head[20], *in;
2027        git_zstream stream;
2028        int st;
2029
2030        memset(&stream, 0, sizeof(stream));
2031        stream.next_out = delta_head;
2032        stream.avail_out = sizeof(delta_head);
2033
2034        git_inflate_init(&stream);
2035        do {
2036                in = use_pack(p, w_curs, curpos, &stream.avail_in);
2037                stream.next_in = in;
2038                st = git_inflate(&stream, Z_FINISH);
2039                curpos += stream.next_in - in;
2040        } while ((st == Z_OK || st == Z_BUF_ERROR) &&
2041                 stream.total_out < sizeof(delta_head));
2042        git_inflate_end(&stream);
2043        if ((st != Z_STREAM_END) && stream.total_out != sizeof(delta_head)) {
2044                error("delta data unpack-initial failed");
2045                return 0;
2046        }
2047
2048        /* Examine the initial part of the delta to figure out
2049         * the result size.
2050         */
2051        data = delta_head;
2052
2053        /* ignore base size */
2054        get_delta_hdr_size(&data, delta_head+sizeof(delta_head));
2055
2056        /* Read the result size */
2057        return get_delta_hdr_size(&data, delta_head+sizeof(delta_head));
2058}
2059
2060static off_t get_delta_base(struct packed_git *p,
2061                                    struct pack_window **w_curs,
2062                                    off_t *curpos,
2063                                    enum object_type type,
2064                                    off_t delta_obj_offset)
2065{
2066        unsigned char *base_info = use_pack(p, w_curs, *curpos, NULL);
2067        off_t base_offset;
2068
2069        /* use_pack() assured us we have [base_info, base_info + 20)
2070         * as a range that we can look at without walking off the
2071         * end of the mapped window.  Its actually the hash size
2072         * that is assured.  An OFS_DELTA longer than the hash size
2073         * is stupid, as then a REF_DELTA would be smaller to store.
2074         */
2075        if (type == OBJ_OFS_DELTA) {
2076                unsigned used = 0;
2077                unsigned char c = base_info[used++];
2078                base_offset = c & 127;
2079                while (c & 128) {
2080                        base_offset += 1;
2081                        if (!base_offset || MSB(base_offset, 7))
2082                                return 0;  /* overflow */
2083                        c = base_info[used++];
2084                        base_offset = (base_offset << 7) + (c & 127);
2085                }
2086                base_offset = delta_obj_offset - base_offset;
2087                if (base_offset <= 0 || base_offset >= delta_obj_offset)
2088                        return 0;  /* out of bound */
2089                *curpos += used;
2090        } else if (type == OBJ_REF_DELTA) {
2091                /* The base entry _must_ be in the same pack */
2092                base_offset = find_pack_entry_one(base_info, p);
2093                *curpos += 20;
2094        } else
2095                die("I am totally screwed");
2096        return base_offset;
2097}
2098
2099/*
2100 * Like get_delta_base above, but we return the sha1 instead of the pack
2101 * offset. This means it is cheaper for REF deltas (we do not have to do
2102 * the final object lookup), but more expensive for OFS deltas (we
2103 * have to load the revidx to convert the offset back into a sha1).
2104 */
2105static const unsigned char *get_delta_base_sha1(struct packed_git *p,
2106                                                struct pack_window **w_curs,
2107                                                off_t curpos,
2108                                                enum object_type type,
2109                                                off_t delta_obj_offset)
2110{
2111        if (type == OBJ_REF_DELTA) {
2112                unsigned char *base = use_pack(p, w_curs, curpos, NULL);
2113                return base;
2114        } else if (type == OBJ_OFS_DELTA) {
2115                struct revindex_entry *revidx;
2116                off_t base_offset = get_delta_base(p, w_curs, &curpos,
2117                                                   type, delta_obj_offset);
2118
2119                if (!base_offset)
2120                        return NULL;
2121
2122                revidx = find_pack_revindex(p, base_offset);
2123                if (!revidx)
2124                        return NULL;
2125
2126                return nth_packed_object_sha1(p, revidx->nr);
2127        } else
2128                return NULL;
2129}
2130
2131int unpack_object_header(struct packed_git *p,
2132                         struct pack_window **w_curs,
2133                         off_t *curpos,
2134                         unsigned long *sizep)
2135{
2136        unsigned char *base;
2137        unsigned long left;
2138        unsigned long used;
2139        enum object_type type;
2140
2141        /* use_pack() assures us we have [base, base + 20) available
2142         * as a range that we can look at.  (Its actually the hash
2143         * size that is assured.)  With our object header encoding
2144         * the maximum deflated object size is 2^137, which is just
2145         * insane, so we know won't exceed what we have been given.
2146         */
2147        base = use_pack(p, w_curs, *curpos, &left);
2148        used = unpack_object_header_buffer(base, left, &type, sizep);
2149        if (!used) {
2150                type = OBJ_BAD;
2151        } else
2152                *curpos += used;
2153
2154        return type;
2155}
2156
2157static int retry_bad_packed_offset(struct packed_git *p, off_t obj_offset)
2158{
2159        int type;
2160        struct revindex_entry *revidx;
2161        const unsigned char *sha1;
2162        revidx = find_pack_revindex(p, obj_offset);
2163        if (!revidx)
2164                return OBJ_BAD;
2165        sha1 = nth_packed_object_sha1(p, revidx->nr);
2166        mark_bad_packed_object(p, sha1);
2167        type = sha1_object_info(sha1, NULL);
2168        if (type <= OBJ_NONE)
2169                return OBJ_BAD;
2170        return type;
2171}
2172
2173#define POI_STACK_PREALLOC 64
2174
2175static enum object_type packed_to_object_type(struct packed_git *p,
2176                                              off_t obj_offset,
2177                                              enum object_type type,
2178                                              struct pack_window **w_curs,
2179                                              off_t curpos)
2180{
2181        off_t small_poi_stack[POI_STACK_PREALLOC];
2182        off_t *poi_stack = small_poi_stack;
2183        int poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;
2184
2185        while (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
2186                off_t base_offset;
2187                unsigned long size;
2188                /* Push the object we're going to leave behind */
2189                if (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {
2190                        poi_stack_alloc = alloc_nr(poi_stack_nr);
2191                        ALLOC_ARRAY(poi_stack, poi_stack_alloc);
2192                        memcpy(poi_stack, small_poi_stack, sizeof(off_t)*poi_stack_nr);
2193                } else {
2194                        ALLOC_GROW(poi_stack, poi_stack_nr+1, poi_stack_alloc);
2195                }
2196                poi_stack[poi_stack_nr++] = obj_offset;
2197                /* If parsing the base offset fails, just unwind */
2198                base_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);
2199                if (!base_offset)
2200                        goto unwind;
2201                curpos = obj_offset = base_offset;
2202                type = unpack_object_header(p, w_curs, &curpos, &size);
2203                if (type <= OBJ_NONE) {
2204                        /* If getting the base itself fails, we first
2205                         * retry the base, otherwise unwind */
2206                        type = retry_bad_packed_offset(p, base_offset);
2207                        if (type > OBJ_NONE)
2208                                goto out;
2209                        goto unwind;
2210                }
2211        }
2212
2213        switch (type) {
2214        case OBJ_BAD:
2215        case OBJ_COMMIT:
2216        case OBJ_TREE:
2217        case OBJ_BLOB:
2218        case OBJ_TAG:
2219                break;
2220        default:
2221                error("unknown object type %i at offset %"PRIuMAX" in %s",
2222                      type, (uintmax_t)obj_offset, p->pack_name);
2223                type = OBJ_BAD;
2224        }
2225
2226out:
2227        if (poi_stack != small_poi_stack)
2228                free(poi_stack);
2229        return type;
2230
2231unwind:
2232        while (poi_stack_nr) {
2233                obj_offset = poi_stack[--poi_stack_nr];
2234                type = retry_bad_packed_offset(p, obj_offset);
2235                if (type > OBJ_NONE)
2236                        goto out;
2237        }
2238        type = OBJ_BAD;
2239        goto out;
2240}
2241
2242int packed_object_info(struct packed_git *p, off_t obj_offset,
2243                       struct object_info *oi)
2244{
2245        struct pack_window *w_curs = NULL;
2246        unsigned long size;
2247        off_t curpos = obj_offset;
2248        enum object_type type;
2249
2250        /*
2251         * We always get the representation type, but only convert it to
2252         * a "real" type later if the caller is interested.
2253         */
2254        type = unpack_object_header(p, &w_curs, &curpos, &size);
2255
2256        if (oi->sizep) {
2257                if (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
2258                        off_t tmp_pos = curpos;
2259                        off_t base_offset = get_delta_base(p, &w_curs, &tmp_pos,
2260                                                           type, obj_offset);
2261                        if (!base_offset) {
2262                                type = OBJ_BAD;
2263                                goto out;
2264                        }
2265                        *oi->sizep = get_size_from_delta(p, &w_curs, tmp_pos);
2266                        if (*oi->sizep == 0) {
2267                                type = OBJ_BAD;
2268                                goto out;
2269                        }
2270                } else {
2271                        *oi->sizep = size;
2272                }
2273        }
2274
2275        if (oi->disk_sizep) {
2276                struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
2277                *oi->disk_sizep = revidx[1].offset - obj_offset;
2278        }
2279
2280        if (oi->typep) {
2281                *oi->typep = packed_to_object_type(p, obj_offset, type, &w_curs, curpos);
2282                if (*oi->typep < 0) {
2283                        type = OBJ_BAD;
2284                        goto out;
2285                }
2286        }
2287
2288        if (oi->delta_base_sha1) {
2289                if (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
2290                        const unsigned char *base;
2291
2292                        base = get_delta_base_sha1(p, &w_curs, curpos,
2293                                                   type, obj_offset);
2294                        if (!base) {
2295                                type = OBJ_BAD;
2296                                goto out;
2297                        }
2298
2299                        hashcpy(oi->delta_base_sha1, base);
2300                } else
2301                        hashclr(oi->delta_base_sha1);
2302        }
2303
2304out:
2305        unuse_pack(&w_curs);
2306        return type;
2307}
2308
2309static void *unpack_compressed_entry(struct packed_git *p,
2310                                    struct pack_window **w_curs,
2311                                    off_t curpos,
2312                                    unsigned long size)
2313{
2314        int st;
2315        git_zstream stream;
2316        unsigned char *buffer, *in;
2317
2318        buffer = xmallocz_gently(size);
2319        if (!buffer)
2320                return NULL;
2321        memset(&stream, 0, sizeof(stream));
2322        stream.next_out = buffer;
2323        stream.avail_out = size + 1;
2324
2325        git_inflate_init(&stream);
2326        do {
2327                in = use_pack(p, w_curs, curpos, &stream.avail_in);
2328                stream.next_in = in;
2329                st = git_inflate(&stream, Z_FINISH);
2330                if (!stream.avail_out)
2331                        break; /* the payload is larger than it should be */
2332                curpos += stream.next_in - in;
2333        } while (st == Z_OK || st == Z_BUF_ERROR);
2334        git_inflate_end(&stream);
2335        if ((st != Z_STREAM_END) || stream.total_out != size) {
2336                free(buffer);
2337                return NULL;
2338        }
2339
2340        return buffer;
2341}
2342
2343static struct hashmap delta_base_cache;
2344static size_t delta_base_cached;
2345
2346static LIST_HEAD(delta_base_cache_lru);
2347
2348struct delta_base_cache_key {
2349        struct packed_git *p;
2350        off_t base_offset;
2351};
2352
2353struct delta_base_cache_entry {
2354        struct hashmap hash;
2355        struct delta_base_cache_key key;
2356        struct list_head lru;
2357        void *data;
2358        unsigned long size;
2359        enum object_type type;
2360};
2361
2362static unsigned int pack_entry_hash(struct packed_git *p, off_t base_offset)
2363{
2364        unsigned int hash;
2365
2366        hash = (unsigned int)(intptr_t)p + (unsigned int)base_offset;
2367        hash += (hash >> 8) + (hash >> 16);
2368        return hash;
2369}
2370
2371static struct delta_base_cache_entry *
2372get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)
2373{
2374        struct hashmap_entry entry;
2375        struct delta_base_cache_key key;
2376
2377        if (!delta_base_cache.cmpfn)
2378                return NULL;
2379
2380        hashmap_entry_init(&entry, pack_entry_hash(p, base_offset));
2381        key.p = p;
2382        key.base_offset = base_offset;
2383        return hashmap_get(&delta_base_cache, &entry, &key);
2384}
2385
2386static int delta_base_cache_key_eq(const struct delta_base_cache_key *a,
2387                                   const struct delta_base_cache_key *b)
2388{
2389        return a->p == b->p && a->base_offset == b->base_offset;
2390}
2391
2392static int delta_base_cache_hash_cmp(const void *va, const void *vb,
2393                                     const void *vkey)
2394{
2395        const struct delta_base_cache_entry *a = va, *b = vb;
2396        const struct delta_base_cache_key *key = vkey;
2397        if (key)
2398                return !delta_base_cache_key_eq(&a->key, key);
2399        else
2400                return !delta_base_cache_key_eq(&a->key, &b->key);
2401}
2402
2403static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
2404{
2405        return !!get_delta_base_cache_entry(p, base_offset);
2406}
2407
2408/*
2409 * Remove the entry from the cache, but do _not_ free the associated
2410 * entry data. The caller takes ownership of the "data" buffer, and
2411 * should copy out any fields it wants before detaching.
2412 */
2413static void detach_delta_base_cache_entry(struct delta_base_cache_entry *ent)
2414{
2415        hashmap_remove(&delta_base_cache, ent, &ent->key);
2416        list_del(&ent->lru);
2417        delta_base_cached -= ent->size;
2418        free(ent);
2419}
2420
2421static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
2422        unsigned long *base_size, enum object_type *type)
2423{
2424        struct delta_base_cache_entry *ent;
2425
2426        ent = get_delta_base_cache_entry(p, base_offset);
2427        if (!ent)
2428                return unpack_entry(p, base_offset, type, base_size);
2429
2430        *type = ent->type;
2431        *base_size = ent->size;
2432        return xmemdupz(ent->data, ent->size);
2433}
2434
2435static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)
2436{
2437        free(ent->data);
2438        detach_delta_base_cache_entry(ent);
2439}
2440
2441void clear_delta_base_cache(void)
2442{
2443        struct list_head *lru, *tmp;
2444        list_for_each_safe(lru, tmp, &delta_base_cache_lru) {
2445                struct delta_base_cache_entry *entry =
2446                        list_entry(lru, struct delta_base_cache_entry, lru);
2447                release_delta_base_cache(entry);
2448        }
2449}
2450
2451static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
2452        void *base, unsigned long base_size, enum object_type type)
2453{
2454        struct delta_base_cache_entry *ent = xmalloc(sizeof(*ent));
2455        struct list_head *lru, *tmp;
2456
2457        delta_base_cached += base_size;
2458
2459        list_for_each_safe(lru, tmp, &delta_base_cache_lru) {
2460                struct delta_base_cache_entry *f =
2461                        list_entry(lru, struct delta_base_cache_entry, lru);
2462                if (delta_base_cached <= delta_base_cache_limit)
2463                        break;
2464                release_delta_base_cache(f);
2465        }
2466
2467        ent->key.p = p;
2468        ent->key.base_offset = base_offset;
2469        ent->type = type;
2470        ent->data = base;
2471        ent->size = base_size;
2472        list_add_tail(&ent->lru, &delta_base_cache_lru);
2473
2474        if (!delta_base_cache.cmpfn)
2475                hashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, 0);
2476        hashmap_entry_init(ent, pack_entry_hash(p, base_offset));
2477        hashmap_add(&delta_base_cache, ent);
2478}
2479
2480static void *read_object(const unsigned char *sha1, enum object_type *type,
2481                         unsigned long *size);
2482
2483static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
2484{
2485        static struct trace_key pack_access = TRACE_KEY_INIT(PACK_ACCESS);
2486        trace_printf_key(&pack_access, "%s %"PRIuMAX"\n",
2487                         p->pack_name, (uintmax_t)obj_offset);
2488}
2489
2490int do_check_packed_object_crc;
2491
2492#define UNPACK_ENTRY_STACK_PREALLOC 64
2493struct unpack_entry_stack_ent {
2494        off_t obj_offset;
2495        off_t curpos;
2496        unsigned long size;
2497};
2498
2499void *unpack_entry(struct packed_git *p, off_t obj_offset,
2500                   enum object_type *final_type, unsigned long *final_size)
2501{
2502        struct pack_window *w_curs = NULL;
2503        off_t curpos = obj_offset;
2504        void *data = NULL;
2505        unsigned long size;
2506        enum object_type type;
2507        struct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];
2508        struct unpack_entry_stack_ent *delta_stack = small_delta_stack;
2509        int delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;
2510        int base_from_cache = 0;
2511
2512        write_pack_access_log(p, obj_offset);
2513
2514        /* PHASE 1: drill down to the innermost base object */
2515        for (;;) {
2516                off_t base_offset;
2517                int i;
2518                struct delta_base_cache_entry *ent;
2519
2520                ent = get_delta_base_cache_entry(p, curpos);
2521                if (ent) {
2522                        type = ent->type;
2523                        data = ent->data;
2524                        size = ent->size;
2525                        detach_delta_base_cache_entry(ent);
2526                        base_from_cache = 1;
2527                        break;
2528                }
2529
2530                if (do_check_packed_object_crc && p->index_version > 1) {
2531                        struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
2532                        off_t len = revidx[1].offset - obj_offset;
2533                        if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
2534                                const unsigned char *sha1 =
2535                                        nth_packed_object_sha1(p, revidx->nr);
2536                                error("bad packed object CRC for %s",
2537                                      sha1_to_hex(sha1));
2538                                mark_bad_packed_object(p, sha1);
2539                                unuse_pack(&w_curs);
2540                                return NULL;
2541                        }
2542                }
2543
2544                type = unpack_object_header(p, &w_curs, &curpos, &size);
2545                if (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)
2546                        break;
2547
2548                base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
2549                if (!base_offset) {
2550                        error("failed to validate delta base reference "
2551                              "at offset %"PRIuMAX" from %s",
2552                              (uintmax_t)curpos, p->pack_name);
2553                        /* bail to phase 2, in hopes of recovery */
2554                        data = NULL;
2555                        break;
2556                }
2557
2558                /* push object, proceed to base */
2559                if (delta_stack_nr >= delta_stack_alloc
2560                    && delta_stack == small_delta_stack) {
2561                        delta_stack_alloc = alloc_nr(delta_stack_nr);
2562                        ALLOC_ARRAY(delta_stack, delta_stack_alloc);
2563                        memcpy(delta_stack, small_delta_stack,
2564                               sizeof(*delta_stack)*delta_stack_nr);
2565                } else {
2566                        ALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);
2567                }
2568                i = delta_stack_nr++;
2569                delta_stack[i].obj_offset = obj_offset;
2570                delta_stack[i].curpos = curpos;
2571                delta_stack[i].size = size;
2572
2573                curpos = obj_offset = base_offset;
2574        }
2575
2576        /* PHASE 2: handle the base */
2577        switch (type) {
2578        case OBJ_OFS_DELTA:
2579        case OBJ_REF_DELTA:
2580                if (data)
2581                        die("BUG: unpack_entry: left loop at a valid delta");
2582                break;
2583        case OBJ_COMMIT:
2584        case OBJ_TREE:
2585        case OBJ_BLOB:
2586        case OBJ_TAG:
2587                if (!base_from_cache)
2588                        data = unpack_compressed_entry(p, &w_curs, curpos, size);
2589                break;
2590        default:
2591                data = NULL;
2592                error("unknown object type %i at offset %"PRIuMAX" in %s",
2593                      type, (uintmax_t)obj_offset, p->pack_name);
2594        }
2595
2596        /* PHASE 3: apply deltas in order */
2597
2598        /* invariants:
2599         *   'data' holds the base data, or NULL if there was corruption
2600         */
2601        while (delta_stack_nr) {
2602                void *delta_data;
2603                void *base = data;
2604                void *external_base = NULL;
2605                unsigned long delta_size, base_size = size;
2606                int i;
2607
2608                data = NULL;
2609
2610                if (base)
2611                        add_delta_base_cache(p, obj_offset, base, base_size, type);
2612
2613                if (!base) {
2614                        /*
2615                         * We're probably in deep shit, but let's try to fetch
2616                         * the required base anyway from another pack or loose.
2617                         * This is costly but should happen only in the presence
2618                         * of a corrupted pack, and is better than failing outright.
2619                         */
2620                        struct revindex_entry *revidx;
2621                        const unsigned char *base_sha1;
2622                        revidx = find_pack_revindex(p, obj_offset);
2623                        if (revidx) {
2624                                base_sha1 = nth_packed_object_sha1(p, revidx->nr);
2625                                error("failed to read delta base object %s"
2626                                      " at offset %"PRIuMAX" from %s",
2627                                      sha1_to_hex(base_sha1), (uintmax_t)obj_offset,
2628                                      p->pack_name);
2629                                mark_bad_packed_object(p, base_sha1);
2630                                base = read_object(base_sha1, &type, &base_size);
2631                                external_base = base;
2632                        }
2633                }
2634
2635                i = --delta_stack_nr;
2636                obj_offset = delta_stack[i].obj_offset;
2637                curpos = delta_stack[i].curpos;
2638                delta_size = delta_stack[i].size;
2639
2640                if (!base)
2641                        continue;
2642
2643                delta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);
2644
2645                if (!delta_data) {
2646                        error("failed to unpack compressed delta "
2647                              "at offset %"PRIuMAX" from %s",
2648                              (uintmax_t)curpos, p->pack_name);
2649                        data = NULL;
2650                        free(external_base);
2651                        continue;
2652                }
2653
2654                data = patch_delta(base, base_size,
2655                                   delta_data, delta_size,
2656                                   &size);
2657
2658                /*
2659                 * We could not apply the delta; warn the user, but keep going.
2660                 * Our failure will be noticed either in the next iteration of
2661                 * the loop, or if this is the final delta, in the caller when
2662                 * we return NULL. Those code paths will take care of making
2663                 * a more explicit warning and retrying with another copy of
2664                 * the object.
2665                 */
2666                if (!data)
2667                        error("failed to apply delta");
2668
2669                free(delta_data);
2670                free(external_base);
2671        }
2672
2673        *final_type = type;
2674        *final_size = size;
2675
2676        unuse_pack(&w_curs);
2677
2678        if (delta_stack != small_delta_stack)
2679                free(delta_stack);
2680
2681        return data;
2682}
2683
2684const unsigned char *nth_packed_object_sha1(struct packed_git *p,
2685                                            uint32_t n)
2686{
2687        const unsigned char *index = p->index_data;
2688        if (!index) {
2689                if (open_pack_index(p))
2690                        return NULL;
2691                index = p->index_data;
2692        }
2693        if (n >= p->num_objects)
2694                return NULL;
2695        index += 4 * 256;
2696        if (p->index_version == 1) {
2697                return index + 24 * n + 4;
2698        } else {
2699                index += 8;
2700                return index + 20 * n;
2701        }
2702}
2703
2704const struct object_id *nth_packed_object_oid(struct object_id *oid,
2705                                              struct packed_git *p,
2706                                              uint32_t n)
2707{
2708        const unsigned char *hash = nth_packed_object_sha1(p, n);
2709        if (!hash)
2710                return NULL;
2711        hashcpy(oid->hash, hash);
2712        return oid;
2713}
2714
2715void check_pack_index_ptr(const struct packed_git *p, const void *vptr)
2716{
2717        const unsigned char *ptr = vptr;
2718        const unsigned char *start = p->index_data;
2719        const unsigned char *end = start + p->index_size;
2720        if (ptr < start)
2721                die(_("offset before start of pack index for %s (corrupt index?)"),
2722                    p->pack_name);
2723        /* No need to check for underflow; .idx files must be at least 8 bytes */
2724        if (ptr >= end - 8)
2725                die(_("offset beyond end of pack index for %s (truncated index?)"),
2726                    p->pack_name);
2727}
2728
2729off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)
2730{
2731        const unsigned char *index = p->index_data;
2732        index += 4 * 256;
2733        if (p->index_version == 1) {
2734                return ntohl(*((uint32_t *)(index + 24 * n)));
2735        } else {
2736                uint32_t off;
2737                index += 8 + p->num_objects * (20 + 4);
2738                off = ntohl(*((uint32_t *)(index + 4 * n)));
2739                if (!(off & 0x80000000))
2740                        return off;
2741                index += p->num_objects * 4 + (off & 0x7fffffff) * 8;
2742                check_pack_index_ptr(p, index);
2743                return (((uint64_t)ntohl(*((uint32_t *)(index + 0)))) << 32) |
2744                                   ntohl(*((uint32_t *)(index + 4)));
2745        }
2746}
2747
2748off_t find_pack_entry_one(const unsigned char *sha1,
2749                                  struct packed_git *p)
2750{
2751        const uint32_t *level1_ofs = p->index_data;
2752        const unsigned char *index = p->index_data;
2753        unsigned hi, lo, stride;
2754        static int use_lookup = -1;
2755        static int debug_lookup = -1;
2756
2757        if (debug_lookup < 0)
2758                debug_lookup = !!getenv("GIT_DEBUG_LOOKUP");
2759
2760        if (!index) {
2761                if (open_pack_index(p))
2762                        return 0;
2763                level1_ofs = p->index_data;
2764                index = p->index_data;
2765        }
2766        if (p->index_version > 1) {
2767                level1_ofs += 2;
2768                index += 8;
2769        }
2770        index += 4 * 256;
2771        hi = ntohl(level1_ofs[*sha1]);
2772        lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));
2773        if (p->index_version > 1) {
2774                stride = 20;
2775        } else {
2776                stride = 24;
2777                index += 4;
2778        }
2779
2780        if (debug_lookup)
2781                printf("%02x%02x%02x... lo %u hi %u nr %"PRIu32"\n",
2782                       sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);
2783
2784        if (use_lookup < 0)
2785                use_lookup = !!getenv("GIT_USE_LOOKUP");
2786        if (use_lookup) {
2787                int pos = sha1_entry_pos(index, stride, 0,
2788                                         lo, hi, p->num_objects, sha1);
2789                if (pos < 0)
2790                        return 0;
2791                return nth_packed_object_offset(p, pos);
2792        }
2793
2794        do {
2795                unsigned mi = (lo + hi) / 2;
2796                int cmp = hashcmp(index + mi * stride, sha1);
2797
2798                if (debug_lookup)
2799                        printf("lo %u hi %u rg %u mi %u\n",
2800                               lo, hi, hi - lo, mi);
2801                if (!cmp)
2802                        return nth_packed_object_offset(p, mi);
2803                if (cmp > 0)
2804                        hi = mi;
2805                else
2806                        lo = mi+1;
2807        } while (lo < hi);
2808        return 0;
2809}
2810
2811int is_pack_valid(struct packed_git *p)
2812{
2813        /* An already open pack is known to be valid. */
2814        if (p->pack_fd != -1)
2815                return 1;
2816
2817        /* If the pack has one window completely covering the
2818         * file size, the pack is known to be valid even if
2819         * the descriptor is not currently open.
2820         */
2821        if (p->windows) {
2822                struct pack_window *w = p->windows;
2823
2824                if (!w->offset && w->len == p->pack_size)
2825                        return 1;
2826        }
2827
2828        /* Force the pack to open to prove its valid. */
2829        return !open_packed_git(p);
2830}
2831
2832static int fill_pack_entry(const unsigned char *sha1,
2833                           struct pack_entry *e,
2834                           struct packed_git *p)
2835{
2836        off_t offset;
2837
2838        if (p->num_bad_objects) {
2839                unsigned i;
2840                for (i = 0; i < p->num_bad_objects; i++)
2841                        if (!hashcmp(sha1, p->bad_object_sha1 + 20 * i))
2842                                return 0;
2843        }
2844
2845        offset = find_pack_entry_one(sha1, p);
2846        if (!offset)
2847                return 0;
2848
2849        /*
2850         * We are about to tell the caller where they can locate the
2851         * requested object.  We better make sure the packfile is
2852         * still here and can be accessed before supplying that
2853         * answer, as it may have been deleted since the index was
2854         * loaded!
2855         */
2856        if (!is_pack_valid(p))
2857                return 0;
2858        e->offset = offset;
2859        e->p = p;
2860        hashcpy(e->sha1, sha1);
2861        return 1;
2862}
2863
2864/*
2865 * Iff a pack file contains the object named by sha1, return true and
2866 * store its location to e.
2867 */
2868static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
2869{
2870        struct mru_entry *p;
2871
2872        prepare_packed_git();
2873        if (!packed_git)
2874                return 0;
2875
2876        for (p = packed_git_mru->head; p; p = p->next) {
2877                if (fill_pack_entry(sha1, e, p->item)) {
2878                        mru_mark(packed_git_mru, p);
2879                        return 1;
2880                }
2881        }
2882        return 0;
2883}
2884
2885struct packed_git *find_sha1_pack(const unsigned char *sha1,
2886                                  struct packed_git *packs)
2887{
2888        struct packed_git *p;
2889
2890        for (p = packs; p; p = p->next) {
2891                if (find_pack_entry_one(sha1, p))
2892                        return p;
2893        }
2894        return NULL;
2895
2896}
2897
2898static int sha1_loose_object_info(const unsigned char *sha1,
2899                                  struct object_info *oi,
2900                                  int flags)
2901{
2902        int status = 0;
2903        unsigned long mapsize;
2904        void *map;
2905        git_zstream stream;
2906        char hdr[32];
2907        struct strbuf hdrbuf = STRBUF_INIT;
2908
2909        if (oi->delta_base_sha1)
2910                hashclr(oi->delta_base_sha1);
2911
2912        /*
2913         * If we don't care about type or size, then we don't
2914         * need to look inside the object at all. Note that we
2915         * do not optimize out the stat call, even if the
2916         * caller doesn't care about the disk-size, since our
2917         * return value implicitly indicates whether the
2918         * object even exists.
2919         */
2920        if (!oi->typep && !oi->typename && !oi->sizep) {
2921                const char *path;
2922                struct stat st;
2923                if (stat_sha1_file(sha1, &st, &path) < 0)
2924                        return -1;
2925                if (oi->disk_sizep)
2926                        *oi->disk_sizep = st.st_size;
2927                return 0;
2928        }
2929
2930        map = map_sha1_file(sha1, &mapsize);
2931        if (!map)
2932                return -1;
2933        if (oi->disk_sizep)
2934                *oi->disk_sizep = mapsize;
2935        if ((flags & LOOKUP_UNKNOWN_OBJECT)) {
2936                if (unpack_sha1_header_to_strbuf(&stream, map, mapsize, hdr, sizeof(hdr), &hdrbuf) < 0)
2937                        status = error("unable to unpack %s header with --allow-unknown-type",
2938                                       sha1_to_hex(sha1));
2939        } else if (unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr)) < 0)
2940                status = error("unable to unpack %s header",
2941                               sha1_to_hex(sha1));
2942        if (status < 0)
2943                ; /* Do nothing */
2944        else if (hdrbuf.len) {
2945                if ((status = parse_sha1_header_extended(hdrbuf.buf, oi, flags)) < 0)
2946                        status = error("unable to parse %s header with --allow-unknown-type",
2947                                       sha1_to_hex(sha1));
2948        } else if ((status = parse_sha1_header_extended(hdr, oi, flags)) < 0)
2949                status = error("unable to parse %s header", sha1_to_hex(sha1));
2950        git_inflate_end(&stream);
2951        munmap(map, mapsize);
2952        if (status && oi->typep)
2953                *oi->typep = status;
2954        strbuf_release(&hdrbuf);
2955        return (status < 0) ? status : 0;
2956}
2957
2958int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi, unsigned flags)
2959{
2960        struct cached_object *co;
2961        struct pack_entry e;
2962        int rtype;
2963        enum object_type real_type;
2964        const unsigned char *real = lookup_replace_object_extended(sha1, flags);
2965
2966        co = find_cached_object(real);
2967        if (co) {
2968                if (oi->typep)
2969                        *(oi->typep) = co->type;
2970                if (oi->sizep)
2971                        *(oi->sizep) = co->size;
2972                if (oi->disk_sizep)
2973                        *(oi->disk_sizep) = 0;
2974                if (oi->delta_base_sha1)
2975                        hashclr(oi->delta_base_sha1);
2976                if (oi->typename)
2977                        strbuf_addstr(oi->typename, typename(co->type));
2978                oi->whence = OI_CACHED;
2979                return 0;
2980        }
2981
2982        if (!find_pack_entry(real, &e)) {
2983                /* Most likely it's a loose object. */
2984                if (!sha1_loose_object_info(real, oi, flags)) {
2985                        oi->whence = OI_LOOSE;
2986                        return 0;
2987                }
2988
2989                /* Not a loose object; someone else may have just packed it. */
2990                reprepare_packed_git();
2991                if (!find_pack_entry(real, &e))
2992                        return -1;
2993        }
2994
2995        /*
2996         * packed_object_info() does not follow the delta chain to
2997         * find out the real type, unless it is given oi->typep.
2998         */
2999        if (oi->typename && !oi->typep)
3000                oi->typep = &real_type;
3001
3002        rtype = packed_object_info(e.p, e.offset, oi);
3003        if (rtype < 0) {
3004                mark_bad_packed_object(e.p, real);
3005                if (oi->typep == &real_type)
3006                        oi->typep = NULL;
3007                return sha1_object_info_extended(real, oi, 0);
3008        } else if (in_delta_base_cache(e.p, e.offset)) {
3009                oi->whence = OI_DBCACHED;
3010        } else {
3011                oi->whence = OI_PACKED;
3012                oi->u.packed.offset = e.offset;
3013                oi->u.packed.pack = e.p;
3014                oi->u.packed.is_delta = (rtype == OBJ_REF_DELTA ||
3015                                         rtype == OBJ_OFS_DELTA);
3016        }
3017        if (oi->typename)
3018                strbuf_addstr(oi->typename, typename(*oi->typep));
3019        if (oi->typep == &real_type)
3020                oi->typep = NULL;
3021
3022        return 0;
3023}
3024
3025/* returns enum object_type or negative */
3026int sha1_object_info(const unsigned char *sha1, unsigned long *sizep)
3027{
3028        enum object_type type;
3029        struct object_info oi = OBJECT_INFO_INIT;
3030
3031        oi.typep = &type;
3032        oi.sizep = sizep;
3033        if (sha1_object_info_extended(sha1, &oi, LOOKUP_REPLACE_OBJECT) < 0)
3034                return -1;
3035        return type;
3036}
3037
3038static void *read_packed_sha1(const unsigned char *sha1,
3039                              enum object_type *type, unsigned long *size)
3040{
3041        struct pack_entry e;
3042        void *data;
3043
3044        if (!find_pack_entry(sha1, &e))
3045                return NULL;
3046        data = cache_or_unpack_entry(e.p, e.offset, size, type);
3047        if (!data) {
3048                /*
3049                 * We're probably in deep shit, but let's try to fetch
3050                 * the required object anyway from another pack or loose.
3051                 * This should happen only in the presence of a corrupted
3052                 * pack, and is better than failing outright.
3053                 */
3054                error("failed to read object %s at offset %"PRIuMAX" from %s",
3055                      sha1_to_hex(sha1), (uintmax_t)e.offset, e.p->pack_name);
3056                mark_bad_packed_object(e.p, sha1);
3057                data = read_object(sha1, type, size);
3058        }
3059        return data;
3060}
3061
3062int pretend_sha1_file(void *buf, unsigned long len, enum object_type type,
3063                      unsigned char *sha1)
3064{
3065        struct cached_object *co;
3066
3067        hash_sha1_file(buf, len, typename(type), sha1);
3068        if (has_sha1_file(sha1) || find_cached_object(sha1))
3069                return 0;
3070        ALLOC_GROW(cached_objects, cached_object_nr + 1, cached_object_alloc);
3071        co = &cached_objects[cached_object_nr++];
3072        co->size = len;
3073        co->type = type;
3074        co->buf = xmalloc(len);
3075        memcpy(co->buf, buf, len);
3076        hashcpy(co->sha1, sha1);
3077        return 0;
3078}
3079
3080static void *read_object(const unsigned char *sha1, enum object_type *type,
3081                         unsigned long *size)
3082{
3083        unsigned long mapsize;
3084        void *map, *buf;
3085        struct cached_object *co;
3086
3087        co = find_cached_object(sha1);
3088        if (co) {
3089                *type = co->type;
3090                *size = co->size;
3091                return xmemdupz(co->buf, co->size);
3092        }
3093
3094        buf = read_packed_sha1(sha1, type, size);
3095        if (buf)
3096                return buf;
3097        map = map_sha1_file(sha1, &mapsize);
3098        if (map) {
3099                buf = unpack_sha1_file(map, mapsize, type, size, sha1);
3100                munmap(map, mapsize);
3101                return buf;
3102        }
3103        reprepare_packed_git();
3104        return read_packed_sha1(sha1, type, size);
3105}
3106
3107/*
3108 * This function dies on corrupt objects; the callers who want to
3109 * deal with them should arrange to call read_object() and give error
3110 * messages themselves.
3111 */
3112void *read_sha1_file_extended(const unsigned char *sha1,
3113                              enum object_type *type,
3114                              unsigned long *size,
3115                              unsigned flag)
3116{
3117        void *data;
3118        const struct packed_git *p;
3119        const char *path;
3120        struct stat st;
3121        const unsigned char *repl = lookup_replace_object_extended(sha1, flag);
3122
3123        errno = 0;
3124        data = read_object(repl, type, size);
3125        if (data)
3126                return data;
3127
3128        if (errno && errno != ENOENT)
3129                die_errno("failed to read object %s", sha1_to_hex(sha1));
3130
3131        /* die if we replaced an object with one that does not exist */
3132        if (repl != sha1)
3133                die("replacement %s not found for %s",
3134                    sha1_to_hex(repl), sha1_to_hex(sha1));
3135
3136        if (!stat_sha1_file(repl, &st, &path))
3137                die("loose object %s (stored in %s) is corrupt",
3138                    sha1_to_hex(repl), path);
3139
3140        if ((p = has_packed_and_bad(repl)) != NULL)
3141                die("packed object %s (stored in %s) is corrupt",
3142                    sha1_to_hex(repl), p->pack_name);
3143
3144        return NULL;
3145}
3146
3147void *read_object_with_reference(const unsigned char *sha1,
3148                                 const char *required_type_name,
3149                                 unsigned long *size,
3150                                 unsigned char *actual_sha1_return)
3151{
3152        enum object_type type, required_type;
3153        void *buffer;
3154        unsigned long isize;
3155        unsigned char actual_sha1[20];
3156
3157        required_type = type_from_string(required_type_name);
3158        hashcpy(actual_sha1, sha1);
3159        while (1) {
3160                int ref_length = -1;
3161                const char *ref_type = NULL;
3162
3163                buffer = read_sha1_file(actual_sha1, &type, &isize);
3164                if (!buffer)
3165                        return NULL;
3166                if (type == required_type) {
3167                        *size = isize;
3168                        if (actual_sha1_return)
3169                                hashcpy(actual_sha1_return, actual_sha1);
3170                        return buffer;
3171                }
3172                /* Handle references */
3173                else if (type == OBJ_COMMIT)
3174                        ref_type = "tree ";
3175                else if (type == OBJ_TAG)
3176                        ref_type = "object ";
3177                else {
3178                        free(buffer);
3179                        return NULL;
3180                }
3181                ref_length = strlen(ref_type);
3182
3183                if (ref_length + 40 > isize ||
3184                    memcmp(buffer, ref_type, ref_length) ||
3185                    get_sha1_hex((char *) buffer + ref_length, actual_sha1)) {
3186                        free(buffer);
3187                        return NULL;
3188                }
3189                free(buffer);
3190                /* Now we have the ID of the referred-to object in
3191                 * actual_sha1.  Check again. */
3192        }
3193}
3194
3195static void write_sha1_file_prepare(const void *buf, unsigned long len,
3196                                    const char *type, unsigned char *sha1,
3197                                    char *hdr, int *hdrlen)
3198{
3199        git_SHA_CTX c;
3200
3201        /* Generate the header */
3202        *hdrlen = xsnprintf(hdr, *hdrlen, "%s %lu", type, len)+1;
3203
3204        /* Sha1.. */
3205        git_SHA1_Init(&c);
3206        git_SHA1_Update(&c, hdr, *hdrlen);
3207        git_SHA1_Update(&c, buf, len);
3208        git_SHA1_Final(sha1, &c);
3209}
3210
3211/*
3212 * Move the just written object into its final resting place.
3213 */
3214int finalize_object_file(const char *tmpfile, const char *filename)
3215{
3216        int ret = 0;
3217
3218        if (object_creation_mode == OBJECT_CREATION_USES_RENAMES)
3219                goto try_rename;
3220        else if (link(tmpfile, filename))
3221                ret = errno;
3222
3223        /*
3224         * Coda hack - coda doesn't like cross-directory links,
3225         * so we fall back to a rename, which will mean that it
3226         * won't be able to check collisions, but that's not a
3227         * big deal.
3228         *
3229         * The same holds for FAT formatted media.
3230         *
3231         * When this succeeds, we just return.  We have nothing
3232         * left to unlink.
3233         */
3234        if (ret && ret != EEXIST) {
3235        try_rename:
3236                if (!rename(tmpfile, filename))
3237                        goto out;
3238                ret = errno;
3239        }
3240        unlink_or_warn(tmpfile);
3241        if (ret) {
3242                if (ret != EEXIST) {
3243                        return error_errno("unable to write sha1 filename %s", filename);
3244                }
3245                /* FIXME!!! Collision check here ? */
3246        }
3247
3248out:
3249        if (adjust_shared_perm(filename))
3250                return error("unable to set permission to '%s'", filename);
3251        return 0;
3252}
3253
3254static int write_buffer(int fd, const void *buf, size_t len)
3255{
3256        if (write_in_full(fd, buf, len) < 0)
3257                return error_errno("file write error");
3258        return 0;
3259}
3260
3261int hash_sha1_file(const void *buf, unsigned long len, const char *type,
3262                   unsigned char *sha1)
3263{
3264        char hdr[32];
3265        int hdrlen = sizeof(hdr);
3266        write_sha1_file_prepare(buf, len, type, sha1, hdr, &hdrlen);
3267        return 0;
3268}
3269
3270/* Finalize a file on disk, and close it. */
3271static void close_sha1_file(int fd)
3272{
3273        if (fsync_object_files)
3274                fsync_or_die(fd, "sha1 file");
3275        if (close(fd) != 0)
3276                die_errno("error when closing sha1 file");
3277}
3278
3279/* Size of directory component, including the ending '/' */
3280static inline int directory_size(const char *filename)
3281{
3282        const char *s = strrchr(filename, '/');
3283        if (!s)
3284                return 0;
3285        return s - filename + 1;
3286}
3287
3288/*
3289 * This creates a temporary file in the same directory as the final
3290 * 'filename'
3291 *
3292 * We want to avoid cross-directory filename renames, because those
3293 * can have problems on various filesystems (FAT, NFS, Coda).
3294 */
3295static int create_tmpfile(struct strbuf *tmp, const char *filename)
3296{
3297        int fd, dirlen = directory_size(filename);
3298
3299        strbuf_reset(tmp);
3300        strbuf_add(tmp, filename, dirlen);
3301        strbuf_addstr(tmp, "tmp_obj_XXXXXX");
3302        fd = git_mkstemp_mode(tmp->buf, 0444);
3303        if (fd < 0 && dirlen && errno == ENOENT) {
3304                /*
3305                 * Make sure the directory exists; note that the contents
3306                 * of the buffer are undefined after mkstemp returns an
3307                 * error, so we have to rewrite the whole buffer from
3308                 * scratch.
3309                 */
3310                strbuf_reset(tmp);
3311                strbuf_add(tmp, filename, dirlen - 1);
3312                if (mkdir(tmp->buf, 0777) && errno != EEXIST)
3313                        return -1;
3314                if (adjust_shared_perm(tmp->buf))
3315                        return -1;
3316
3317                /* Try again */
3318                strbuf_addstr(tmp, "/tmp_obj_XXXXXX");
3319                fd = git_mkstemp_mode(tmp->buf, 0444);
3320        }
3321        return fd;
3322}
3323
3324static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,
3325                              const void *buf, unsigned long len, time_t mtime)
3326{
3327        int fd, ret;
3328        unsigned char compressed[4096];
3329        git_zstream stream;
3330        git_SHA_CTX c;
3331        unsigned char parano_sha1[20];
3332        static struct strbuf tmp_file = STRBUF_INIT;
3333        const char *filename = sha1_file_name(sha1);
3334
3335        fd = create_tmpfile(&tmp_file, filename);
3336        if (fd < 0) {
3337                if (errno == EACCES)
3338                        return error("insufficient permission for adding an object to repository database %s", get_object_directory());
3339                else
3340                        return error_errno("unable to create temporary file");
3341        }
3342
3343        /* Set it up */
3344        git_deflate_init(&stream, zlib_compression_level);
3345        stream.next_out = compressed;
3346        stream.avail_out = sizeof(compressed);
3347        git_SHA1_Init(&c);
3348
3349        /* First header.. */
3350        stream.next_in = (unsigned char *)hdr;
3351        stream.avail_in = hdrlen;
3352        while (git_deflate(&stream, 0) == Z_OK)
3353                ; /* nothing */
3354        git_SHA1_Update(&c, hdr, hdrlen);
3355
3356        /* Then the data itself.. */
3357        stream.next_in = (void *)buf;
3358        stream.avail_in = len;
3359        do {
3360                unsigned char *in0 = stream.next_in;
3361                ret = git_deflate(&stream, Z_FINISH);
3362                git_SHA1_Update(&c, in0, stream.next_in - in0);
3363                if (write_buffer(fd, compressed, stream.next_out - compressed) < 0)
3364                        die("unable to write sha1 file");
3365                stream.next_out = compressed;
3366                stream.avail_out = sizeof(compressed);
3367        } while (ret == Z_OK);
3368
3369        if (ret != Z_STREAM_END)
3370                die("unable to deflate new object %s (%d)", sha1_to_hex(sha1), ret);
3371        ret = git_deflate_end_gently(&stream);
3372        if (ret != Z_OK)
3373                die("deflateEnd on object %s failed (%d)", sha1_to_hex(sha1), ret);
3374        git_SHA1_Final(parano_sha1, &c);
3375        if (hashcmp(sha1, parano_sha1) != 0)
3376                die("confused by unstable object source data for %s", sha1_to_hex(sha1));
3377
3378        close_sha1_file(fd);
3379
3380        if (mtime) {
3381                struct utimbuf utb;
3382                utb.actime = mtime;
3383                utb.modtime = mtime;
3384                if (utime(tmp_file.buf, &utb) < 0)
3385                        warning_errno("failed utime() on %s", tmp_file.buf);
3386        }
3387
3388        return finalize_object_file(tmp_file.buf, filename);
3389}
3390
3391static int freshen_loose_object(const unsigned char *sha1)
3392{
3393        return check_and_freshen(sha1, 1);
3394}
3395
3396static int freshen_packed_object(const unsigned char *sha1)
3397{
3398        struct pack_entry e;
3399        if (!find_pack_entry(sha1, &e))
3400                return 0;
3401        if (e.p->freshened)
3402                return 1;
3403        if (!freshen_file(e.p->pack_name))
3404                return 0;
3405        e.p->freshened = 1;
3406        return 1;
3407}
3408
3409int write_sha1_file(const void *buf, unsigned long len, const char *type, unsigned char *sha1)
3410{
3411        char hdr[32];
3412        int hdrlen = sizeof(hdr);
3413
3414        /* Normally if we have it in the pack then we do not bother writing
3415         * it out into .git/objects/??/?{38} file.
3416         */
3417        write_sha1_file_prepare(buf, len, type, sha1, hdr, &hdrlen);
3418        if (freshen_packed_object(sha1) || freshen_loose_object(sha1))
3419                return 0;
3420        return write_loose_object(sha1, hdr, hdrlen, buf, len, 0);
3421}
3422
3423int hash_sha1_file_literally(const void *buf, unsigned long len, const char *type,
3424                             unsigned char *sha1, unsigned flags)
3425{
3426        char *header;
3427        int hdrlen, status = 0;
3428
3429        /* type string, SP, %lu of the length plus NUL must fit this */
3430        hdrlen = strlen(type) + 32;
3431        header = xmalloc(hdrlen);
3432        write_sha1_file_prepare(buf, len, type, sha1, header, &hdrlen);
3433
3434        if (!(flags & HASH_WRITE_OBJECT))
3435                goto cleanup;
3436        if (freshen_packed_object(sha1) || freshen_loose_object(sha1))
3437                goto cleanup;
3438        status = write_loose_object(sha1, header, hdrlen, buf, len, 0);
3439
3440cleanup:
3441        free(header);
3442        return status;
3443}
3444
3445int force_object_loose(const unsigned char *sha1, time_t mtime)
3446{
3447        void *buf;
3448        unsigned long len;
3449        enum object_type type;
3450        char hdr[32];
3451        int hdrlen;
3452        int ret;
3453
3454        if (has_loose_object(sha1))
3455                return 0;
3456        buf = read_packed_sha1(sha1, &type, &len);
3457        if (!buf)
3458                return error("cannot read sha1_file for %s", sha1_to_hex(sha1));
3459        hdrlen = xsnprintf(hdr, sizeof(hdr), "%s %lu", typename(type), len) + 1;
3460        ret = write_loose_object(sha1, hdr, hdrlen, buf, len, mtime);
3461        free(buf);
3462
3463        return ret;
3464}
3465
3466int has_pack_index(const unsigned char *sha1)
3467{
3468        struct stat st;
3469        if (stat(sha1_pack_index_name(sha1), &st))
3470                return 0;
3471        return 1;
3472}
3473
3474int has_sha1_pack(const unsigned char *sha1)
3475{
3476        struct pack_entry e;
3477        return find_pack_entry(sha1, &e);
3478}
3479
3480int has_sha1_file_with_flags(const unsigned char *sha1, int flags)
3481{
3482        struct pack_entry e;
3483
3484        if (!startup_info->have_repository)
3485                return 0;
3486        if (find_pack_entry(sha1, &e))
3487                return 1;
3488        if (has_loose_object(sha1))
3489                return 1;
3490        if (flags & HAS_SHA1_QUICK)
3491                return 0;
3492        reprepare_packed_git();
3493        return find_pack_entry(sha1, &e);
3494}
3495
3496int has_object_file(const struct object_id *oid)
3497{
3498        return has_sha1_file(oid->hash);
3499}
3500
3501int has_object_file_with_flags(const struct object_id *oid, int flags)
3502{
3503        return has_sha1_file_with_flags(oid->hash, flags);
3504}
3505
3506static void check_tree(const void *buf, size_t size)
3507{
3508        struct tree_desc desc;
3509        struct name_entry entry;
3510
3511        init_tree_desc(&desc, buf, size);
3512        while (tree_entry(&desc, &entry))
3513                /* do nothing
3514                 * tree_entry() will die() on malformed entries */
3515                ;
3516}
3517
3518static void check_commit(const void *buf, size_t size)
3519{
3520        struct commit c;
3521        memset(&c, 0, sizeof(c));
3522        if (parse_commit_buffer(&c, buf, size))
3523                die("corrupt commit");
3524}
3525
3526static void check_tag(const void *buf, size_t size)
3527{
3528        struct tag t;
3529        memset(&t, 0, sizeof(t));
3530        if (parse_tag_buffer(&t, buf, size))
3531                die("corrupt tag");
3532}
3533
3534static int index_mem(unsigned char *sha1, void *buf, size_t size,
3535                     enum object_type type,
3536                     const char *path, unsigned flags)
3537{
3538        int ret, re_allocated = 0;
3539        int write_object = flags & HASH_WRITE_OBJECT;
3540
3541        if (!type)
3542                type = OBJ_BLOB;
3543
3544        /*
3545         * Convert blobs to git internal format
3546         */
3547        if ((type == OBJ_BLOB) && path) {
3548                struct strbuf nbuf = STRBUF_INIT;
3549                if (convert_to_git(path, buf, size, &nbuf,
3550                                   write_object ? safe_crlf : SAFE_CRLF_FALSE)) {
3551                        buf = strbuf_detach(&nbuf, &size);
3552                        re_allocated = 1;
3553                }
3554        }
3555        if (flags & HASH_FORMAT_CHECK) {
3556                if (type == OBJ_TREE)
3557                        check_tree(buf, size);
3558                if (type == OBJ_COMMIT)
3559                        check_commit(buf, size);
3560                if (type == OBJ_TAG)
3561                        check_tag(buf, size);
3562        }
3563
3564        if (write_object)
3565                ret = write_sha1_file(buf, size, typename(type), sha1);
3566        else
3567                ret = hash_sha1_file(buf, size, typename(type), sha1);
3568        if (re_allocated)
3569                free(buf);
3570        return ret;
3571}
3572
3573static int index_stream_convert_blob(unsigned char *sha1, int fd,
3574                                     const char *path, unsigned flags)
3575{
3576        int ret;
3577        const int write_object = flags & HASH_WRITE_OBJECT;
3578        struct strbuf sbuf = STRBUF_INIT;
3579
3580        assert(path);
3581        assert(would_convert_to_git_filter_fd(path));
3582
3583        convert_to_git_filter_fd(path, fd, &sbuf,
3584                                 write_object ? safe_crlf : SAFE_CRLF_FALSE);
3585
3586        if (write_object)
3587                ret = write_sha1_file(sbuf.buf, sbuf.len, typename(OBJ_BLOB),
3588                                      sha1);
3589        else
3590                ret = hash_sha1_file(sbuf.buf, sbuf.len, typename(OBJ_BLOB),
3591                                     sha1);
3592        strbuf_release(&sbuf);
3593        return ret;
3594}
3595
3596static int index_pipe(unsigned char *sha1, int fd, enum object_type type,
3597                      const char *path, unsigned flags)
3598{
3599        struct strbuf sbuf = STRBUF_INIT;
3600        int ret;
3601
3602        if (strbuf_read(&sbuf, fd, 4096) >= 0)
3603                ret = index_mem(sha1, sbuf.buf, sbuf.len, type, path, flags);
3604        else
3605                ret = -1;
3606        strbuf_release(&sbuf);
3607        return ret;
3608}
3609
3610#define SMALL_FILE_SIZE (32*1024)
3611
3612static int index_core(unsigned char *sha1, int fd, size_t size,
3613                      enum object_type type, const char *path,
3614                      unsigned flags)
3615{
3616        int ret;
3617
3618        if (!size) {
3619                ret = index_mem(sha1, "", size, type, path, flags);
3620        } else if (size <= SMALL_FILE_SIZE) {
3621                char *buf = xmalloc(size);
3622                if (size == read_in_full(fd, buf, size))
3623                        ret = index_mem(sha1, buf, size, type, path, flags);
3624                else
3625                        ret = error_errno("short read");
3626                free(buf);
3627        } else {
3628                void *buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
3629                ret = index_mem(sha1, buf, size, type, path, flags);
3630                munmap(buf, size);
3631        }
3632        return ret;
3633}
3634
3635/*
3636 * This creates one packfile per large blob unless bulk-checkin
3637 * machinery is "plugged".
3638 *
3639 * This also bypasses the usual "convert-to-git" dance, and that is on
3640 * purpose. We could write a streaming version of the converting
3641 * functions and insert that before feeding the data to fast-import
3642 * (or equivalent in-core API described above). However, that is
3643 * somewhat complicated, as we do not know the size of the filter
3644 * result, which we need to know beforehand when writing a git object.
3645 * Since the primary motivation for trying to stream from the working
3646 * tree file and to avoid mmaping it in core is to deal with large
3647 * binary blobs, they generally do not want to get any conversion, and
3648 * callers should avoid this code path when filters are requested.
3649 */
3650static int index_stream(unsigned char *sha1, int fd, size_t size,
3651                        enum object_type type, const char *path,
3652                        unsigned flags)
3653{
3654        return index_bulk_checkin(sha1, fd, size, type, path, flags);
3655}
3656
3657int index_fd(unsigned char *sha1, int fd, struct stat *st,
3658             enum object_type type, const char *path, unsigned flags)
3659{
3660        int ret;
3661
3662        /*
3663         * Call xsize_t() only when needed to avoid potentially unnecessary
3664         * die() for large files.
3665         */
3666        if (type == OBJ_BLOB && path && would_convert_to_git_filter_fd(path))
3667                ret = index_stream_convert_blob(sha1, fd, path, flags);
3668        else if (!S_ISREG(st->st_mode))
3669                ret = index_pipe(sha1, fd, type, path, flags);
3670        else if (st->st_size <= big_file_threshold || type != OBJ_BLOB ||
3671                 (path && would_convert_to_git(path)))
3672                ret = index_core(sha1, fd, xsize_t(st->st_size), type, path,
3673                                 flags);
3674        else
3675                ret = index_stream(sha1, fd, xsize_t(st->st_size), type, path,
3676                                   flags);
3677        close(fd);
3678        return ret;
3679}
3680
3681int index_path(unsigned char *sha1, const char *path, struct stat *st, unsigned flags)
3682{
3683        int fd;
3684        struct strbuf sb = STRBUF_INIT;
3685
3686        switch (st->st_mode & S_IFMT) {
3687        case S_IFREG:
3688                fd = open(path, O_RDONLY);
3689                if (fd < 0)
3690                        return error_errno("open(\"%s\")", path);
3691                if (index_fd(sha1, fd, st, OBJ_BLOB, path, flags) < 0)
3692                        return error("%s: failed to insert into database",
3693                                     path);
3694                break;
3695        case S_IFLNK:
3696                if (strbuf_readlink(&sb, path, st->st_size))
3697                        return error_errno("readlink(\"%s\")", path);
3698                if (!(flags & HASH_WRITE_OBJECT))
3699                        hash_sha1_file(sb.buf, sb.len, blob_type, sha1);
3700                else if (write_sha1_file(sb.buf, sb.len, blob_type, sha1))
3701                        return error("%s: failed to insert into database",
3702                                     path);
3703                strbuf_release(&sb);
3704                break;
3705        case S_IFDIR:
3706                return resolve_gitlink_ref(path, "HEAD", sha1);
3707        default:
3708                return error("%s: unsupported file type", path);
3709        }
3710        return 0;
3711}
3712
3713int read_pack_header(int fd, struct pack_header *header)
3714{
3715        if (read_in_full(fd, header, sizeof(*header)) < sizeof(*header))
3716                /* "eof before pack header was fully read" */
3717                return PH_ERROR_EOF;
3718
3719        if (header->hdr_signature != htonl(PACK_SIGNATURE))
3720                /* "protocol error (pack signature mismatch detected)" */
3721                return PH_ERROR_PACK_SIGNATURE;
3722        if (!pack_version_ok(header->hdr_version))
3723                /* "protocol error (pack version unsupported)" */
3724                return PH_ERROR_PROTOCOL;
3725        return 0;
3726}
3727
3728void assert_sha1_type(const unsigned char *sha1, enum object_type expect)
3729{
3730        enum object_type type = sha1_object_info(sha1, NULL);
3731        if (type < 0)
3732                die("%s is not a valid object", sha1_to_hex(sha1));
3733        if (type != expect)
3734                die("%s is not a valid '%s' object", sha1_to_hex(sha1),
3735                    typename(expect));
3736}
3737
3738static int for_each_file_in_obj_subdir(int subdir_nr,
3739                                       struct strbuf *path,
3740                                       each_loose_object_fn obj_cb,
3741                                       each_loose_cruft_fn cruft_cb,
3742                                       each_loose_subdir_fn subdir_cb,
3743                                       void *data)
3744{
3745        size_t baselen = path->len;
3746        DIR *dir = opendir(path->buf);
3747        struct dirent *de;
3748        int r = 0;
3749
3750        if (!dir) {
3751                if (errno == ENOENT)
3752                        return 0;
3753                return error_errno("unable to open %s", path->buf);
3754        }
3755
3756        while ((de = readdir(dir))) {
3757                if (is_dot_or_dotdot(de->d_name))
3758                        continue;
3759
3760                strbuf_setlen(path, baselen);
3761                strbuf_addf(path, "/%s", de->d_name);
3762
3763                if (strlen(de->d_name) == GIT_SHA1_HEXSZ - 2)  {
3764                        char hex[GIT_MAX_HEXSZ+1];
3765                        struct object_id oid;
3766
3767                        xsnprintf(hex, sizeof(hex), "%02x%s",
3768                                  subdir_nr, de->d_name);
3769                        if (!get_oid_hex(hex, &oid)) {
3770                                if (obj_cb) {
3771                                        r = obj_cb(&oid, path->buf, data);
3772                                        if (r)
3773                                                break;
3774                                }
3775                                continue;
3776                        }
3777                }
3778
3779                if (cruft_cb) {
3780                        r = cruft_cb(de->d_name, path->buf, data);
3781                        if (r)
3782                                break;
3783                }
3784        }
3785        closedir(dir);
3786
3787        strbuf_setlen(path, baselen);
3788        if (!r && subdir_cb)
3789                r = subdir_cb(subdir_nr, path->buf, data);
3790
3791        return r;
3792}
3793
3794int for_each_loose_file_in_objdir_buf(struct strbuf *path,
3795                            each_loose_object_fn obj_cb,
3796                            each_loose_cruft_fn cruft_cb,
3797                            each_loose_subdir_fn subdir_cb,
3798                            void *data)
3799{
3800        size_t baselen = path->len;
3801        int r = 0;
3802        int i;
3803
3804        for (i = 0; i < 256; i++) {
3805                strbuf_addf(path, "/%02x", i);
3806                r = for_each_file_in_obj_subdir(i, path, obj_cb, cruft_cb,
3807                                                subdir_cb, data);
3808                strbuf_setlen(path, baselen);
3809                if (r)
3810                        break;
3811        }
3812
3813        return r;
3814}
3815
3816int for_each_loose_file_in_objdir(const char *path,
3817                                  each_loose_object_fn obj_cb,
3818                                  each_loose_cruft_fn cruft_cb,
3819                                  each_loose_subdir_fn subdir_cb,
3820                                  void *data)
3821{
3822        struct strbuf buf = STRBUF_INIT;
3823        int r;
3824
3825        strbuf_addstr(&buf, path);
3826        r = for_each_loose_file_in_objdir_buf(&buf, obj_cb, cruft_cb,
3827                                              subdir_cb, data);
3828        strbuf_release(&buf);
3829
3830        return r;
3831}
3832
3833struct loose_alt_odb_data {
3834        each_loose_object_fn *cb;
3835        void *data;
3836};
3837
3838static int loose_from_alt_odb(struct alternate_object_database *alt,
3839                              void *vdata)
3840{
3841        struct loose_alt_odb_data *data = vdata;
3842        struct strbuf buf = STRBUF_INIT;
3843        int r;
3844
3845        strbuf_addstr(&buf, alt->path);
3846        r = for_each_loose_file_in_objdir_buf(&buf,
3847                                              data->cb, NULL, NULL,
3848                                              data->data);
3849        strbuf_release(&buf);
3850        return r;
3851}
3852
3853int for_each_loose_object(each_loose_object_fn cb, void *data, unsigned flags)
3854{
3855        struct loose_alt_odb_data alt;
3856        int r;
3857
3858        r = for_each_loose_file_in_objdir(get_object_directory(),
3859                                          cb, NULL, NULL, data);
3860        if (r)
3861                return r;
3862
3863        if (flags & FOR_EACH_OBJECT_LOCAL_ONLY)
3864                return 0;
3865
3866        alt.cb = cb;
3867        alt.data = data;
3868        return foreach_alt_odb(loose_from_alt_odb, &alt);
3869}
3870
3871static int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn cb, void *data)
3872{
3873        uint32_t i;
3874        int r = 0;
3875
3876        for (i = 0; i < p->num_objects; i++) {
3877                struct object_id oid;
3878
3879                if (!nth_packed_object_oid(&oid, p, i))
3880                        return error("unable to get sha1 of object %u in %s",
3881                                     i, p->pack_name);
3882
3883                r = cb(&oid, p, i, data);
3884                if (r)
3885                        break;
3886        }
3887        return r;
3888}
3889
3890int for_each_packed_object(each_packed_object_fn cb, void *data, unsigned flags)
3891{
3892        struct packed_git *p;
3893        int r = 0;
3894        int pack_errors = 0;
3895
3896        prepare_packed_git();
3897        for (p = packed_git; p; p = p->next) {
3898                if ((flags & FOR_EACH_OBJECT_LOCAL_ONLY) && !p->pack_local)
3899                        continue;
3900                if (open_pack_index(p)) {
3901                        pack_errors = 1;
3902                        continue;
3903                }
3904                r = for_each_object_in_pack(p, cb, data);
3905                if (r)
3906                        break;
3907        }
3908        return r ? r : pack_errors;
3909}
3910
3911static int check_stream_sha1(git_zstream *stream,
3912                             const char *hdr,
3913                             unsigned long size,
3914                             const char *path,
3915                             const unsigned char *expected_sha1)
3916{
3917        git_SHA_CTX c;
3918        unsigned char real_sha1[GIT_MAX_RAWSZ];
3919        unsigned char buf[4096];
3920        unsigned long total_read;
3921        int status = Z_OK;
3922
3923        git_SHA1_Init(&c);
3924        git_SHA1_Update(&c, hdr, stream->total_out);
3925
3926        /*
3927         * We already read some bytes into hdr, but the ones up to the NUL
3928         * do not count against the object's content size.
3929         */
3930        total_read = stream->total_out - strlen(hdr) - 1;
3931
3932        /*
3933         * This size comparison must be "<=" to read the final zlib packets;
3934         * see the comment in unpack_sha1_rest for details.
3935         */
3936        while (total_read <= size &&
3937               (status == Z_OK || status == Z_BUF_ERROR)) {
3938                stream->next_out = buf;
3939                stream->avail_out = sizeof(buf);
3940                if (size - total_read < stream->avail_out)
3941                        stream->avail_out = size - total_read;
3942                status = git_inflate(stream, Z_FINISH);
3943                git_SHA1_Update(&c, buf, stream->next_out - buf);
3944                total_read += stream->next_out - buf;
3945        }
3946        git_inflate_end(stream);
3947
3948        if (status != Z_STREAM_END) {
3949                error("corrupt loose object '%s'", sha1_to_hex(expected_sha1));
3950                return -1;
3951        }
3952        if (stream->avail_in) {
3953                error("garbage at end of loose object '%s'",
3954                      sha1_to_hex(expected_sha1));
3955                return -1;
3956        }
3957
3958        git_SHA1_Final(real_sha1, &c);
3959        if (hashcmp(expected_sha1, real_sha1)) {
3960                error("sha1 mismatch for %s (expected %s)", path,
3961                      sha1_to_hex(expected_sha1));
3962                return -1;
3963        }
3964
3965        return 0;
3966}
3967
3968int read_loose_object(const char *path,
3969                      const unsigned char *expected_sha1,
3970                      enum object_type *type,
3971                      unsigned long *size,
3972                      void **contents)
3973{
3974        int ret = -1;
3975        void *map = NULL;
3976        unsigned long mapsize;
3977        git_zstream stream;
3978        char hdr[32];
3979
3980        *contents = NULL;
3981
3982        map = map_sha1_file_1(path, NULL, &mapsize);
3983        if (!map) {
3984                error_errno("unable to mmap %s", path);
3985                goto out;
3986        }
3987
3988        if (unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr)) < 0) {
3989                error("unable to unpack header of %s", path);
3990                goto out;
3991        }
3992
3993        *type = parse_sha1_header(hdr, size);
3994        if (*type < 0) {
3995                error("unable to parse header of %s", path);
3996                git_inflate_end(&stream);
3997                goto out;
3998        }
3999
4000        if (*type == OBJ_BLOB) {
4001                if (check_stream_sha1(&stream, hdr, *size, path, expected_sha1) < 0)
4002                        goto out;
4003        } else {
4004                *contents = unpack_sha1_rest(&stream, hdr, *size, expected_sha1);
4005                if (!*contents) {
4006                        error("unable to unpack contents of %s", path);
4007                        git_inflate_end(&stream);
4008                        goto out;
4009                }
4010                if (check_sha1_signature(expected_sha1, *contents,
4011                                         *size, typename(*type))) {
4012                        error("sha1 mismatch for %s (expected %s)", path,
4013                              sha1_to_hex(expected_sha1));
4014                        free(*contents);
4015                        goto out;
4016                }
4017        }
4018
4019        ret = 0; /* everything checks out */
4020
4021out:
4022        if (map)
4023                munmap(map, mapsize);
4024        return ret;
4025}