sha1_file.c

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