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 <sys/types.h>
  10 #include <dirent.h>
  11 #include "cache.h"
  12 #include "delta.h"
  13
  14 #ifndef O_NOATIME
  15 #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))
  16 #define O_NOATIME 01000000
  17 #else
  18 #define O_NOATIME 0
  19 #endif
  20 #endif
  21
  22 static unsigned int sha1_file_open_flag = O_NOATIME;
  23
  24 static unsigned hexval(char c)
  25 {
  26         if (c >= '0' && c <= '9')
  27                 return c - '0';
  28         if (c >= 'a' && c <= 'f')
  29                 return c - 'a' + 10;
  30         if (c >= 'A' && c <= 'F')
  31                 return c - 'A' + 10;
  32         return ~0;
  33 }
  34
  35 int get_sha1_hex(const char *hex, unsigned char *sha1)
  36 {
  37         int i;
  38         for (i = 0; i < 20; i++) {
  39                 unsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);
  40                 if (val & ~0xff)
  41                         return -1;
  42                 *sha1++ = val;
  43                 hex += 2;
  44         }
  45         return 0;
  46 }
  47
  48 static int get_sha1_file(const char *path, unsigned char *result)
  49 {
  50         char buffer[60];
  51         int fd = open(path, O_RDONLY);
  52         int len;
  53
  54         if (fd < 0)
  55                 return -1;
  56         len = read(fd, buffer, sizeof(buffer));
  57         close(fd);
  58         if (len < 40)
  59                 return -1;
  60         return get_sha1_hex(buffer, result);
  61 }
  62
  63 static char *git_dir, *git_object_dir, *git_index_file, *git_refs_dir;
  64 static void setup_git_env(void)
  65 {
  66         git_dir = gitenv(GIT_DIR_ENVIRONMENT);
  67         if (!git_dir)
  68                 git_dir = DEFAULT_GIT_DIR_ENVIRONMENT;
  69         git_object_dir = gitenv(DB_ENVIRONMENT);
  70         if (!git_object_dir) {
  71                 git_object_dir = xmalloc(strlen(git_dir) + 9);
  72                 sprintf(git_object_dir, "%s/objects", git_dir);
  73         }
  74         git_refs_dir = xmalloc(strlen(git_dir) + 6);
  75         sprintf(git_refs_dir, "%s/refs", git_dir);
  76         git_index_file = gitenv(INDEX_ENVIRONMENT);
  77         if (!git_index_file) {
  78                 git_index_file = xmalloc(strlen(git_dir) + 7);
  79                 sprintf(git_index_file, "%s/index", git_dir);
  80         }
  81 }
  82
  83 char *get_object_directory(void)
  84 {
  85         if (!git_object_dir)
  86                 setup_git_env();
  87         return git_object_dir;
  88 }
  89
  90 char *get_refs_directory(void)
  91 {
  92         if (!git_refs_dir)
  93                 setup_git_env();
  94         return git_refs_dir;
  95 }
  96
  97 char *get_index_file(void)
  98 {
  99         if (!git_index_file)
 100                 setup_git_env();
 101         return git_index_file;
 102 }
 103
 104 int get_sha1(const char *str, unsigned char *sha1)
 105 {
 106         static char pathname[PATH_MAX];
 107         static const char *prefix[] = {
 108                 "",
 109                 "refs",
 110                 "refs/tags",
 111                 "refs/heads",
 112                 "refs/snap",
 113                 NULL
 114         };
 115         const char **p;
 116
 117         if (!get_sha1_hex(str, sha1))
 118                 return 0;
 119
 120         if (!git_dir)
 121                 setup_git_env();
 122         for (p = prefix; *p; p++) {
 123                 snprintf(pathname, sizeof(pathname), "%s/%s/%s",
 124                          git_dir, *p, str);
 125                 if (!get_sha1_file(pathname, sha1))
 126                         return 0;
 127         }
 128
 129         return -1;
 130 }
 131
 132 char * sha1_to_hex(const unsigned char *sha1)
 133 {
 134         static char buffer[50];
 135         static const char hex[] = "0123456789abcdef";
 136         char *buf = buffer;
 137         int i;
 138
 139         for (i = 0; i < 20; i++) {
 140                 unsigned int val = *sha1++;
 141                 *buf++ = hex[val >> 4];
 142                 *buf++ = hex[val & 0xf];
 143         }
 144         return buffer;
 145 }
 146
 147 static void fill_sha1_path(char *pathbuf, const unsigned char *sha1)
 148 {
 149         int i;
 150         for (i = 0; i < 20; i++) {
 151                 static char hex[] = "0123456789abcdef";
 152                 unsigned int val = sha1[i];
 153                 char *pos = pathbuf + i*2 + (i > 0);
 154                 *pos++ = hex[val >> 4];
 155                 *pos = hex[val & 0xf];
 156         }
 157 }
 158
 159 /*
 160  * NOTE! This returns a statically allocated buffer, so you have to be
 161  * careful about using it. Do a "strdup()" if you need to save the
 162  * filename.
 163  *
 164  * Also note that this returns the location for creating.  Reading
 165  * SHA1 file can happen from any alternate directory listed in the
 166  * DB_ENVIRONMENT environment variable if it is not found in
 167  * the primary object database.
 168  */
 169 char *sha1_file_name(const unsigned char *sha1)
 170 {
 171         static char *name, *base;
 172
 173         if (!base) {
 174                 const char *sha1_file_directory = get_object_directory();
 175                 int len = strlen(sha1_file_directory);
 176                 base = xmalloc(len + 60);
 177                 memcpy(base, sha1_file_directory, len);
 178                 memset(base+len, 0, 60);
 179                 base[len] = '/';
 180                 base[len+3] = '/';
 181                 name = base + len + 1;
 182         }
 183         fill_sha1_path(name, sha1);
 184         return base;
 185 }
 186
 187 struct alternate_object_database *alt_odb;
 188
 189 /*
 190  * Prepare alternate object database registry.
 191  * alt_odb points at an array of struct alternate_object_database.
 192  * This array is terminated with an element that has both its base
 193  * and name set to NULL.  alt_odb[n] comes from n'th non-empty
 194  * element from colon separated ALTERNATE_DB_ENVIRONMENT environment
 195  * variable, and its base points at a statically allocated buffer
 196  * that contains "/the/directory/corresponding/to/.git/objects/...",
 197  * while its name points just after the slash at the end of
 198  * ".git/objects/" in the example above, and has enough space to hold
 199  * 40-byte hex SHA1, an extra slash for the first level indirection,
 200  * and the terminating NUL.
 201  * This function allocates the alt_odb array and all the strings
 202  * pointed by base fields of the array elements with one xmalloc();
 203  * the string pool immediately follows the array.
 204  */
 205 void prepare_alt_odb(void)
 206 {
 207         int pass, totlen, i;
 208         const char *cp, *last;
 209         char *op = NULL;
 210         const char *alt = gitenv(ALTERNATE_DB_ENVIRONMENT) ? : "";
 211
 212         if (alt_odb)
 213                 return;
 214         /* The first pass counts how large an area to allocate to
 215          * hold the entire alt_odb structure, including array of
 216          * structs and path buffers for them.  The second pass fills
 217          * the structure and prepares the path buffers for use by
 218          * fill_sha1_path().
 219          */
 220         for (totlen = pass = 0; pass < 2; pass++) {
 221                 last = alt;
 222                 i = 0;
 223                 do {
 224                         cp = strchr(last, ':') ? : last + strlen(last);
 225                         if (last != cp) {
 226                                 /* 43 = 40-byte + 2 '/' + terminating NUL */
 227                                 int pfxlen = cp - last;
 228                                 int entlen = pfxlen + 43;
 229                                 if (pass == 0)
 230                                         totlen += entlen;
 231                                 else {
 232                                         alt_odb[i].base = op;
 233                                         alt_odb[i].name = op + pfxlen + 1;
 234                                         memcpy(op, last, pfxlen);
 235                                         op[pfxlen] = op[pfxlen + 3] = '/';
 236                                         op[entlen-1] = 0;
 237                                         op += entlen;
 238                                 }
 239                                 i++;
 240                         }
 241                         while (*cp && *cp == ':')
 242                                 cp++;
 243                         last = cp;
 244                 } while (*cp);
 245                 if (pass)
 246                         break;
 247                 alt_odb = xmalloc(sizeof(*alt_odb) * (i + 1) + totlen);
 248                 alt_odb[i].base = alt_odb[i].name = NULL;
 249                 op = (char*)(&alt_odb[i+1]);
 250         }
 251 }
 252
 253 static char *find_sha1_file(const unsigned char *sha1, struct stat *st)
 254 {
 255         int i;
 256         char *name = sha1_file_name(sha1);
 257
 258         if (!stat(name, st))
 259                 return name;
 260         prepare_alt_odb();
 261         for (i = 0; (name = alt_odb[i].name) != NULL; i++) {
 262                 fill_sha1_path(name, sha1);
 263                 if (!stat(alt_odb[i].base, st))
 264                         return alt_odb[i].base;
 265         }
 266         return NULL;
 267 }
 268
 269 #define PACK_MAX_SZ (1<<26)
 270 static int pack_used_ctr;
 271 static unsigned long pack_mapped;
 272 struct packed_git *packed_git;
 273
 274 struct pack_entry {
 275         unsigned int offset;
 276         unsigned char sha1[20];
 277         struct packed_git *p;
 278 };
 279
 280 static int check_packed_git_idx(const char *path, unsigned long *idx_size_,
 281                                 void **idx_map_)
 282 {
 283         void *idx_map;
 284         unsigned int *index;
 285         unsigned long idx_size;
 286         int nr, i;
 287         int fd = open(path, O_RDONLY);
 288         struct stat st;
 289         if (fd < 0)
 290                 return -1;
 291         if (fstat(fd, &st)) {
 292                 close(fd);
 293                 return -1;
 294         }
 295         idx_size = st.st_size;
 296         idx_map = mmap(NULL, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);
 297         close(fd);
 298         if (idx_map == MAP_FAILED)
 299                 return -1;
 300
 301         index = idx_map;
 302
 303         /* check index map */
 304         if (idx_size < 4*256 + 20)
 305                 return error("index file too small");
 306         nr = 0;
 307         for (i = 0; i < 256; i++) {
 308                 unsigned int n = ntohl(index[i]);
 309                 if (n < nr)
 310                         return error("non-monotonic index");
 311                 nr = n;
 312         }
 313
 314         /*
 315          * Total size:
 316          *  - 256 index entries 4 bytes each
 317          *  - 24-byte entries * nr (20-byte sha1 + 4-byte offset)
 318          *  - 20-byte SHA1 of the packfile
 319          *  - 20-byte SHA1 file checksum
 320          */
 321         if (idx_size != 4*256 + nr * 24 + 20 + 20)
 322                 return error("wrong index file size");
 323
 324         *idx_map_ = idx_map;
 325         *idx_size_ = idx_size;
 326         return 0;
 327 }
 328
 329 static void unuse_one_packed_git(void)
 330 {
 331         /* NOTYET */
 332 }
 333
 334 static int use_packed_git(struct packed_git *p)
 335 {
 336         if (!p->pack_base) {
 337                 int fd;
 338                 struct stat st;
 339                 void *map;
 340
 341                 pack_mapped += p->pack_size;
 342                 while (PACK_MAX_SZ < pack_mapped)
 343                         unuse_one_packed_git();
 344                 fd = open(p->pack_name, O_RDONLY);
 345                 if (fd < 0)
 346                         return -1;
 347                 if (fstat(fd, &st)) {
 348                         close(fd);
 349                         return -1;
 350                 }
 351                 if (st.st_size != p->pack_size)
 352                         return -1;
 353                 map = mmap(NULL, p->pack_size, PROT_READ, MAP_PRIVATE, fd, 0);
 354                 close(fd);
 355                 if (map == MAP_FAILED)
 356                         return -1;
 357                 p->pack_base = map;
 358         }
 359         p->pack_last_used = pack_used_ctr++;
 360         return 0;
 361 }
 362
 363 static struct packed_git *add_packed_git(char *path, int path_len)
 364 {
 365         struct stat st;
 366         struct packed_git *p;
 367         unsigned long idx_size;
 368         void *idx_map;
 369
 370         if (check_packed_git_idx(path, &idx_size, &idx_map))
 371                 return NULL;
 372
 373         /* do we have a corresponding .pack file? */
 374         strcpy(path + path_len - 4, ".pack");
 375         if (stat(path, &st) || !S_ISREG(st.st_mode)) {
 376                 munmap(idx_map, idx_size);
 377                 return NULL;
 378         }
 379         /* ok, it looks sane as far as we can check without
 380          * actually mapping the pack file.
 381          */
 382         p = xmalloc(sizeof(*p) + path_len + 2);
 383         strcpy(p->pack_name, path);
 384         p->index_size = idx_size;
 385         p->pack_size = st.st_size;
 386         p->index_base = idx_map;
 387         p->next = NULL;
 388         p->pack_last_used = 0;
 389         return p;
 390 }
 391
 392 static void prepare_packed_git_one(char *objdir)
 393 {
 394         char path[PATH_MAX];
 395         int len;
 396         DIR *dir;
 397         struct dirent *de;
 398
 399         sprintf(path, "%s/pack", objdir);
 400         len = strlen(path);
 401         dir = opendir(path);
 402         if (!dir)
 403                 return;
 404         path[len++] = '/';
 405         while ((de = readdir(dir)) != NULL) {
 406                 int namelen = strlen(de->d_name);
 407                 struct packed_git *p;
 408
 409                 if (strcmp(de->d_name + namelen - 4, ".idx"))
 410                         continue;
 411
 412                 /* we have .idx.  Is it a file we can map? */
 413                 strcpy(path + len, de->d_name);
 414                 p = add_packed_git(path, len + namelen);
 415                 if (!p)
 416                         continue;
 417                 p->next = packed_git;
 418                 packed_git = p;
 419         }
 420 }
 421
 422 void prepare_packed_git(void)
 423 {
 424         int i;
 425         static int run_once = 0;
 426
 427         if (run_once++)
 428                 return;
 429
 430         prepare_packed_git_one(get_object_directory());
 431         prepare_alt_odb();
 432         for (i = 0; alt_odb[i].base != NULL; i++) {
 433                 alt_odb[i].name[0] = 0;
 434                 prepare_packed_git_one(alt_odb[i].base);
 435         }
 436 }
 437
 438 int check_sha1_signature(const unsigned char *sha1, void *map, unsigned long size, const char *type)
 439 {
 440         char header[100];
 441         unsigned char real_sha1[20];
 442         SHA_CTX c;
 443
 444         SHA1_Init(&c);
 445         SHA1_Update(&c, header, 1+sprintf(header, "%s %lu", type, size));
 446         SHA1_Update(&c, map, size);
 447         SHA1_Final(real_sha1, &c);
 448         return memcmp(sha1, real_sha1, 20) ? -1 : 0;
 449 }
 450
 451 static void *map_sha1_file_internal(const unsigned char *sha1,
 452                                     unsigned long *size,
 453                                     int say_error)
 454 {
 455         struct stat st;
 456         void *map;
 457         int fd;
 458         char *filename = find_sha1_file(sha1, &st);
 459
 460         if (!filename) {
 461                 if (say_error)
 462                         error("cannot map sha1 file %s", sha1_to_hex(sha1));
 463                 return NULL;
 464         }
 465
 466         fd = open(filename, O_RDONLY | sha1_file_open_flag);
 467         if (fd < 0) {
 468                 /* See if it works without O_NOATIME */
 469                 switch (sha1_file_open_flag) {
 470                 default:
 471                         fd = open(filename, O_RDONLY);
 472                         if (fd >= 0)
 473                                 break;
 474                 /* Fallthrough */
 475                 case 0:
 476                         if (say_error)
 477                                 perror(filename);
 478                         return NULL;
 479                 }
 480
 481                 /* If it failed once, it will probably fail again.
 482                  * Stop using O_NOATIME
 483                  */
 484                 sha1_file_open_flag = 0;
 485         }
 486         map = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
 487         close(fd);
 488         if (-1 == (int)(long)map)
 489                 return NULL;
 490         *size = st.st_size;
 491         return map;
 492 }
 493
 494 void *map_sha1_file(const unsigned char *sha1, unsigned long *size)
 495 {
 496         return map_sha1_file_internal(sha1, size, 1);
 497 }
 498
 499 int unpack_sha1_header(z_stream *stream, void *map, unsigned long mapsize, void *buffer, unsigned long size)
 500 {
 501         /* Get the data stream */
 502         memset(stream, 0, sizeof(*stream));
 503         stream->next_in = map;
 504         stream->avail_in = mapsize;
 505         stream->next_out = buffer;
 506         stream->avail_out = size;
 507
 508         inflateInit(stream);
 509         return inflate(stream, 0);
 510 }
 511
 512 void *unpack_sha1_rest(z_stream *stream, void *buffer, unsigned long size)
 513 {
 514         int bytes = strlen(buffer) + 1;
 515         unsigned char *buf = xmalloc(1+size);
 516
 517         memcpy(buf, buffer + bytes, stream->total_out - bytes);
 518         bytes = stream->total_out - bytes;
 519         if (bytes < size) {
 520                 stream->next_out = buf + bytes;
 521                 stream->avail_out = size - bytes;
 522                 while (inflate(stream, Z_FINISH) == Z_OK)
 523                         /* nothing */;
 524         }
 525         buf[size] = 0;
 526         inflateEnd(stream);
 527         return buf;
 528 }
 529
 530 /*
 531  * We used to just use "sscanf()", but that's actually way
 532  * too permissive for what we want to check. So do an anal
 533  * object header parse by hand.
 534  */
 535 int parse_sha1_header(char *hdr, char *type, unsigned long *sizep)
 536 {
 537         int i;
 538         unsigned long size;
 539
 540         /*
 541          * The type can be at most ten bytes (including the
 542          * terminating '\0' that we add), and is followed by
 543          * a space.
 544          */
 545         i = 10;
 546         for (;;) {
 547                 char c = *hdr++;
 548                 if (c == ' ')
 549                         break;
 550                 if (!--i)
 551                         return -1;
 552                 *type++ = c;
 553         }
 554         *type = 0;
 555
 556         /*
 557          * The length must follow immediately, and be in canonical
 558          * decimal format (ie "010" is not valid).
 559          */
 560         size = *hdr++ - '0';
 561         if (size > 9)
 562                 return -1;
 563         if (size) {
 564                 for (;;) {
 565                         unsigned long c = *hdr - '0';
 566                         if (c > 9)
 567                                 break;
 568                         hdr++;
 569                         size = size * 10 + c;
 570                 }
 571         }
 572         *sizep = size;
 573
 574         /*
 575          * The length must be followed by a zero byte
 576          */
 577         return *hdr ? -1 : 0;
 578 }
 579
 580 void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size)
 581 {
 582         int ret;
 583         z_stream stream;
 584         char hdr[8192];
 585
 586         ret = unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr));
 587         if (ret < Z_OK || parse_sha1_header(hdr, type, size) < 0)
 588                 return NULL;
 589
 590         return unpack_sha1_rest(&stream, hdr, *size);
 591 }
 592
 593 static int packed_delta_info(unsigned char *base_sha1,
 594                              unsigned long delta_size,
 595                              unsigned long left,
 596                              char *type,
 597                              unsigned long *sizep)
 598 {
 599         unsigned char *data;
 600         unsigned char delta_head[64];
 601         int i;
 602         unsigned char cmd;
 603         unsigned long data_size, result_size, base_size, verify_base_size;
 604         z_stream stream;
 605         int st;
 606
 607         if (left < 20)
 608                 die("truncated pack file");
 609         if (sha1_object_info(base_sha1, type, &base_size))
 610                 die("cannot get info for delta-pack base");
 611
 612         data = base_sha1 + 20;
 613         data_size = left - 20;
 614
 615         memset(&stream, 0, sizeof(stream));
 616
 617         stream.next_in = data;
 618         stream.avail_in = data_size;
 619         stream.next_out = delta_head;
 620         stream.avail_out = sizeof(delta_head);
 621
 622         inflateInit(&stream);
 623         st = inflate(&stream, Z_FINISH);
 624         inflateEnd(&stream);
 625         if ((st != Z_STREAM_END) && stream.total_out != sizeof(delta_head))
 626                 die("delta data unpack-initial failed");
 627
 628         /* Examine the initial part of the delta to figure out
 629          * the result size.  Verify the base size while we are at it.
 630          */
 631         data = delta_head;
 632         verify_base_size = i = 0;
 633         cmd = *data++;
 634         while (cmd) {
 635                 if (cmd & 1)
 636                         verify_base_size |= *data++ << i;
 637                 i += 8;
 638                 cmd >>= 1;
 639         }
 640
 641         /* Read the result size */
 642         result_size = i = 0;
 643         cmd = *data++;
 644         while (cmd) {
 645                 if (cmd & 1)
 646                         result_size |= *data++ << i;
 647                 i += 8;
 648                 cmd >>= 1;
 649         }
 650         if (verify_base_size != base_size)
 651                 die("delta base size mismatch");
 652
 653         *sizep = result_size;
 654         return 0;
 655 }
 656
 657 static int packed_object_info(struct pack_entry *entry,
 658                               char *type, unsigned long *sizep)
 659 {
 660         struct packed_git *p = entry->p;
 661         unsigned long offset, size, left;
 662         unsigned char *pack;
 663
 664         offset = entry->offset;
 665         if (p->pack_size - 5 < offset)
 666                 die("object offset outside of pack file");
 667
 668         if (use_packed_git(p))
 669                 die("cannot map packed file");
 670
 671         pack = p->pack_base + offset;
 672         size = (pack[1] << 24) + (pack[2] << 16) + (pack[3] << 8) + pack[4];
 673         left = p->pack_size - offset - 5;
 674         switch (*pack) {
 675         case 'D':
 676                 return packed_delta_info(pack+5, size, left, type, sizep);
 677                 break;
 678         case 'C':
 679                 strcpy(type, "commit");
 680                 break;
 681         case 'T':
 682                 strcpy(type, "tree");
 683                 break;
 684         case 'B':
 685                 strcpy(type, "blob");
 686                 break;
 687         case 'G':
 688                 strcpy(type, "tag");
 689                 break;
 690         default:
 691                 die("corrupted pack file");
 692         }
 693         *sizep = size;
 694         return 0;
 695 }
 696
 697 /* forward declaration for a mutually recursive function */
 698 static void *unpack_entry(struct pack_entry *, char *, unsigned long *);
 699
 700 static void *unpack_delta_entry(unsigned char *base_sha1,
 701                                 unsigned long delta_size,
 702                                 unsigned long left,
 703                                 char *type,
 704                                 unsigned long *sizep)
 705 {
 706         void *data, *delta_data, *result, *base;
 707         unsigned long data_size, result_size, base_size;
 708         z_stream stream;
 709         int st;
 710
 711         if (left < 20)
 712                 die("truncated pack file");
 713         data = base_sha1 + 20;
 714         data_size = left - 20;
 715         delta_data = xmalloc(delta_size);
 716
 717         memset(&stream, 0, sizeof(stream));
 718
 719         stream.next_in = data;
 720         stream.avail_in = data_size;
 721         stream.next_out = delta_data;
 722         stream.avail_out = delta_size;
 723
 724         inflateInit(&stream);
 725         st = inflate(&stream, Z_FINISH);
 726         inflateEnd(&stream);
 727         if ((st != Z_STREAM_END) || stream.total_out != delta_size)
 728                 die("delta data unpack failed");
 729
 730         /* This may recursively unpack the base, which is what we want */
 731         base = read_sha1_file(base_sha1, type, &base_size);
 732         if (!base)
 733                 die("failed to read delta-pack base object %s",
 734                     sha1_to_hex(base_sha1));
 735         result = patch_delta(base, base_size,
 736                              delta_data, delta_size,
 737                              &result_size);
 738         if (!result)
 739                 die("failed to apply delta");
 740         free(delta_data);
 741         free(base);
 742         *sizep = result_size;
 743         return result;
 744 }
 745
 746 static void *unpack_non_delta_entry(unsigned char *data,
 747                                     unsigned long size,
 748                                     unsigned long left)
 749 {
 750         int st;
 751         z_stream stream;
 752         char *buffer;
 753
 754         buffer = xmalloc(size + 1);
 755         buffer[size] = 0;
 756         memset(&stream, 0, sizeof(stream));
 757         stream.next_in = data;
 758         stream.avail_in = left;
 759         stream.next_out = buffer;
 760         stream.avail_out = size;
 761
 762         inflateInit(&stream);
 763         st = inflate(&stream, Z_FINISH);
 764         inflateEnd(&stream);
 765         if ((st != Z_STREAM_END) || stream.total_out != size) {
 766                 free(buffer);
 767                 return NULL;
 768         }
 769
 770         return buffer;
 771 }
 772
 773 static void *unpack_entry(struct pack_entry *entry,
 774                           char *type, unsigned long *sizep)
 775 {
 776         struct packed_git *p = entry->p;
 777         unsigned long offset, size, left;
 778         unsigned char *pack;
 779
 780         offset = entry->offset;
 781         if (p->pack_size - 5 < offset)
 782                 die("object offset outside of pack file");
 783
 784         if (use_packed_git(p))
 785                 die("cannot map packed file");
 786
 787         pack = p->pack_base + offset;
 788         size = (pack[1] << 24) + (pack[2] << 16) + (pack[3] << 8) + pack[4];
 789         left = p->pack_size - offset - 5;
 790         switch (*pack) {
 791         case 'D':
 792                 return unpack_delta_entry(pack+5, size, left, type, sizep);
 793         case 'C':
 794                 strcpy(type, "commit");
 795                 break;
 796         case 'T':
 797                 strcpy(type, "tree");
 798                 break;
 799         case 'B':
 800                 strcpy(type, "blob");
 801                 break;
 802         case 'G':
 803                 strcpy(type, "tag");
 804                 break;
 805         default:
 806                 die("corrupted pack file");
 807         }
 808         *sizep = size;
 809         return unpack_non_delta_entry(pack+5, size, left);
 810 }
 811
 812 int num_packed_objects(const struct packed_git *p)
 813 {
 814         /* See check_packed_git_idx and pack-objects.c */
 815         return (p->index_size - 20 - 20 - 4*256) / 24;
 816 }
 817
 818 int nth_packed_object_sha1(const struct packed_git *p, int n,
 819                            unsigned char* sha1)
 820 {
 821         void *index = p->index_base + 256;
 822         if (n < 0 || num_packed_objects(p) <= n)
 823                 return -1;
 824         memcpy(sha1, (index + 24 * n + 4), 20);
 825         return 0;
 826 }
 827
 828 static int find_pack_entry_1(const unsigned char *sha1,
 829                              struct pack_entry *e, struct packed_git *p)
 830 {
 831         int *level1_ofs = p->index_base;
 832         int hi = ntohl(level1_ofs[*sha1]);
 833         int lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));
 834         void *index = p->index_base + 256;
 835
 836         do {
 837                 int mi = (lo + hi) / 2;
 838                 int cmp = memcmp(index + 24 * mi + 4, sha1, 20);
 839                 if (!cmp) {
 840                         e->offset = ntohl(*((int*)(index + 24 * mi)));
 841                         memcpy(e->sha1, sha1, 20);
 842                         e->p = p;
 843                         return 1;
 844                 }
 845                 if (cmp > 0)
 846                         hi = mi;
 847                 else
 848                         lo = mi+1;
 849         } while (lo < hi);
 850         return 0;
 851 }
 852
 853 static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
 854 {
 855         struct packed_git *p;
 856         prepare_packed_git();
 857
 858         for (p = packed_git; p; p = p->next) {
 859                 if (find_pack_entry_1(sha1, e, p))
 860                         return 1;
 861         }
 862         return 0;
 863 }
 864
 865 int sha1_object_info(const unsigned char *sha1, char *type, unsigned long *sizep)
 866 {
 867         int status;
 868         unsigned long mapsize, size;
 869         void *map;
 870         z_stream stream;
 871         char hdr[128];
 872
 873         map = map_sha1_file_internal(sha1, &mapsize, 0);
 874         if (!map) {
 875                 struct pack_entry e;
 876
 877                 if (!find_pack_entry(sha1, &e))
 878                         return error("unable to find %s", sha1_to_hex(sha1));
 879                 if (!packed_object_info(&e, type, sizep))
 880                         return 0;
 881                 /* sheesh */
 882                 map = unpack_entry(&e, type, sizep);
 883                 free(map);
 884                 return (map == NULL) ? 0 : -1;
 885         }
 886         if (unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr)) < 0)
 887                 status = error("unable to unpack %s header",
 888                                sha1_to_hex(sha1));
 889         if (parse_sha1_header(hdr, type, &size) < 0)
 890                 status = error("unable to parse %s header", sha1_to_hex(sha1));
 891         else {
 892                 status = 0;
 893                 *sizep = size;
 894         }
 895         inflateEnd(&stream);
 896         munmap(map, mapsize);
 897         return status;
 898 }
 899
 900 static void *read_packed_sha1(const unsigned char *sha1, char *type, unsigned long *size)
 901 {
 902         struct pack_entry e;
 903
 904         if (!find_pack_entry(sha1, &e)) {
 905                 error("cannot read sha1_file for %s", sha1_to_hex(sha1));
 906                 return NULL;
 907         }
 908         return unpack_entry(&e, type, size);
 909 }
 910
 911 void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size)
 912 {
 913         unsigned long mapsize;
 914         void *map, *buf;
 915
 916         map = map_sha1_file_internal(sha1, &mapsize, 0);
 917         if (map) {
 918                 buf = unpack_sha1_file(map, mapsize, type, size);
 919                 munmap(map, mapsize);
 920                 return buf;
 921         }
 922         return read_packed_sha1(sha1, type, size);
 923 }
 924
 925 void *read_object_with_reference(const unsigned char *sha1,
 926                                  const char *required_type,
 927                                  unsigned long *size,
 928                                  unsigned char *actual_sha1_return)
 929 {
 930         char type[20];
 931         void *buffer;
 932         unsigned long isize;
 933         unsigned char actual_sha1[20];
 934
 935         memcpy(actual_sha1, sha1, 20);
 936         while (1) {
 937                 int ref_length = -1;
 938                 const char *ref_type = NULL;
 939
 940                 buffer = read_sha1_file(actual_sha1, type, &isize);
 941                 if (!buffer)
 942                         return NULL;
 943                 if (!strcmp(type, required_type)) {
 944                         *size = isize;
 945                         if (actual_sha1_return)
 946                                 memcpy(actual_sha1_return, actual_sha1, 20);
 947                         return buffer;
 948                 }
 949                 /* Handle references */
 950                 else if (!strcmp(type, "commit"))
 951                         ref_type = "tree ";
 952                 else if (!strcmp(type, "tag"))
 953                         ref_type = "object ";
 954                 else {
 955                         free(buffer);
 956                         return NULL;
 957                 }
 958                 ref_length = strlen(ref_type);
 959
 960                 if (memcmp(buffer, ref_type, ref_length) ||
 961                     get_sha1_hex(buffer + ref_length, actual_sha1)) {
 962                         free(buffer);
 963                         return NULL;
 964                 }
 965                 /* Now we have the ID of the referred-to object in
 966                  * actual_sha1.  Check again. */
 967         }
 968 }
 969
 970 static char *write_sha1_file_prepare(void *buf,
 971                                      unsigned long len,
 972                                      const char *type,
 973                                      unsigned char *sha1,
 974                                      unsigned char *hdr,
 975                                      int *hdrlen)
 976 {
 977         SHA_CTX c;
 978
 979         /* Generate the header */
 980         *hdrlen = sprintf((char *)hdr, "%s %lu", type, len)+1;
 981
 982         /* Sha1.. */
 983         SHA1_Init(&c);
 984         SHA1_Update(&c, hdr, *hdrlen);
 985         SHA1_Update(&c, buf, len);
 986         SHA1_Final(sha1, &c);
 987
 988         return sha1_file_name(sha1);
 989 }
 990
 991 int write_sha1_file(void *buf, unsigned long len, const char *type, unsigned char *returnsha1)
 992 {
 993         int size;
 994         unsigned char *compressed;
 995         z_stream stream;
 996         unsigned char sha1[20];
 997         char *filename;
 998         static char tmpfile[PATH_MAX];
 999         unsigned char hdr[50];
1000         int fd, hdrlen, ret;
1001
1002         /* Normally if we have it in the pack then we do not bother writing
1003          * it out into .git/objects/??/?{38} file.
1004          */
1005         filename = write_sha1_file_prepare(buf, len, type, sha1, hdr, &hdrlen);
1006         if (returnsha1)
1007                 memcpy(returnsha1, sha1, 20);
1008         if (has_sha1_file(sha1))
1009                 return 0;
1010         fd = open(filename, O_RDONLY);
1011         if (fd >= 0) {
1012                 /*
1013                  * FIXME!!! We might do collision checking here, but we'd
1014                  * need to uncompress the old file and check it. Later.
1015                  */
1016                 close(fd);
1017                 return 0;
1018         }
1019
1020         if (errno != ENOENT) {
1021                 fprintf(stderr, "sha1 file %s: %s", filename, strerror(errno));
1022                 return -1;
1023         }
1024
1025         snprintf(tmpfile, sizeof(tmpfile), "%s/obj_XXXXXX", get_object_directory());
1026
1027         fd = mkstemp(tmpfile);
1028         if (fd < 0) {
1029                 fprintf(stderr, "unable to create temporary sha1 filename %s: %s", tmpfile, strerror(errno));
1030                 return -1;
1031         }
1032
1033         /* Set it up */
1034         memset(&stream, 0, sizeof(stream));
1035         deflateInit(&stream, Z_BEST_COMPRESSION);
1036         size = deflateBound(&stream, len+hdrlen);
1037         compressed = xmalloc(size);
1038
1039         /* Compress it */
1040         stream.next_out = compressed;
1041         stream.avail_out = size;
1042
1043         /* First header.. */
1044         stream.next_in = hdr;
1045         stream.avail_in = hdrlen;
1046         while (deflate(&stream, 0) == Z_OK)
1047                 /* nothing */;
1048
1049         /* Then the data itself.. */
1050         stream.next_in = buf;
1051         stream.avail_in = len;
1052         while (deflate(&stream, Z_FINISH) == Z_OK)
1053                 /* nothing */;
1054         deflateEnd(&stream);
1055         size = stream.total_out;
1056
1057         if (write(fd, compressed, size) != size)
1058                 die("unable to write file");
1059         fchmod(fd, 0444);
1060         close(fd);
1061         free(compressed);
1062
1063         ret = link(tmpfile, filename);
1064         if (ret < 0) {
1065                 ret = errno;
1066
1067                 /*
1068                  * Coda hack - coda doesn't like cross-directory links,
1069                  * so we fall back to a rename, which will mean that it
1070                  * won't be able to check collisions, but that's not a
1071                  * big deal.
1072                  *
1073                  * When this succeeds, we just return 0. We have nothing
1074                  * left to unlink.
1075                  */
1076                 if (ret == EXDEV && !rename(tmpfile, filename))
1077                         return 0;
1078         }
1079         unlink(tmpfile);
1080         if (ret) {
1081                 if (ret != EEXIST) {
1082                         fprintf(stderr, "unable to write sha1 filename %s: %s", filename, strerror(ret));
1083                         return -1;
1084                 }
1085                 /* FIXME!!! Collision check here ? */
1086         }
1087
1088         return 0;
1089 }
1090
1091 int write_sha1_from_fd(const unsigned char *sha1, int fd)
1092 {
1093         char *filename = sha1_file_name(sha1);
1094
1095         int local;
1096         z_stream stream;
1097         unsigned char real_sha1[20];
1098         unsigned char buf[4096];
1099         unsigned char discard[4096];
1100         int ret;
1101         SHA_CTX c;
1102
1103         local = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);
1104
1105         if (local < 0)
1106                 return error("Couldn't open %s\n", filename);
1107
1108         memset(&stream, 0, sizeof(stream));
1109
1110         inflateInit(&stream);
1111
1112         SHA1_Init(&c);
1113
1114         do {
1115                 ssize_t size;
1116                 size = read(fd, buf, 4096);
1117                 if (size <= 0) {
1118                         close(local);
1119                         unlink(filename);
1120                         if (!size)
1121                                 return error("Connection closed?");
1122                         perror("Reading from connection");
1123                         return -1;
1124                 }
1125                 write(local, buf, size);
1126                 stream.avail_in = size;
1127                 stream.next_in = buf;
1128                 do {
1129                         stream.next_out = discard;
1130                         stream.avail_out = sizeof(discard);
1131                         ret = inflate(&stream, Z_SYNC_FLUSH);
1132                         SHA1_Update(&c, discard, sizeof(discard) -
1133                                     stream.avail_out);
1134                 } while (stream.avail_in && ret == Z_OK);
1135
1136         } while (ret == Z_OK);
1137         inflateEnd(&stream);
1138
1139         close(local);
1140         SHA1_Final(real_sha1, &c);
1141         if (ret != Z_STREAM_END) {
1142                 unlink(filename);
1143                 return error("File %s corrupted", sha1_to_hex(sha1));
1144         }
1145         if (memcmp(sha1, real_sha1, 20)) {
1146                 unlink(filename);
1147                 return error("File %s has bad hash\n", sha1_to_hex(sha1));
1148         }
1149
1150         return 0;
1151 }
1152
1153 int has_sha1_file(const unsigned char *sha1)
1154 {
1155         struct stat st;
1156         struct pack_entry e;
1157
1158         if (find_sha1_file(sha1, &st))
1159                 return 1;
1160         return find_pack_entry(sha1, &e);
1161 }
1162
1163 int index_fd(unsigned char *sha1, int fd, struct stat *st)
1164 {
1165         unsigned long size = st->st_size;
1166         void *buf;
1167         int ret;
1168
1169         buf = "";
1170         if (size)
1171                 buf = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
1172         close(fd);
1173         if ((int)(long)buf == -1)
1174                 return -1;
1175
1176         ret = write_sha1_file(buf, size, "blob", sha1);
1177         if (size)
1178                 munmap(buf, size);
1179         return ret;
1180 }