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