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