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