index-pack.c

   1 #include "cache.h"
   2 #include "delta.h"
   3 #include "pack.h"
   4 #include "csum-file.h"
   5 #include "blob.h"
   6 #include "commit.h"
   7 #include "tag.h"
   8 #include "tree.h"
   9
  10 static const char index_pack_usage[] =
  11 "git-index-pack [-o index-file] pack-file";
  12
  13 struct object_entry
  14 {
  15         unsigned long offset;
  16         unsigned long size;
  17         unsigned int hdr_size;
  18         enum object_type type;
  19         enum object_type real_type;
  20         unsigned char sha1[20];
  21 };
  22
  23 union delta_base {
  24         unsigned char sha1[20];
  25         unsigned long offset;
  26 };
  27
  28 /*
  29  * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want
  30  * to memcmp() only the first 20 bytes.
  31  */
  32 #define UNION_BASE_SZ   20
  33
  34 struct delta_entry
  35 {
  36         struct object_entry *obj;
  37         union delta_base base;
  38 };
  39
  40 static const char *pack_name;
  41 static struct object_entry *objects;
  42 static struct delta_entry *deltas;
  43 static int nr_objects;
  44 static int nr_deltas;
  45
  46 /* We always read in 4kB chunks. */
  47 static unsigned char input_buffer[4096];
  48 static unsigned long input_offset, input_len, consumed_bytes;
  49 static SHA_CTX input_ctx;
  50 static int input_fd;
  51
  52 /*
  53  * Make sure at least "min" bytes are available in the buffer, and
  54  * return the pointer to the buffer.
  55  */
  56 static void *fill(int min)
  57 {
  58         if (min <= input_len)
  59                 return input_buffer + input_offset;
  60         if (min > sizeof(input_buffer))
  61                 die("cannot fill %d bytes", min);
  62         if (input_offset) {
  63                 SHA1_Update(&input_ctx, input_buffer, input_offset);
  64                 memmove(input_buffer, input_buffer + input_offset, input_len);
  65                 input_offset = 0;
  66         }
  67         do {
  68                 int ret = xread(input_fd, input_buffer + input_len,
  69                                 sizeof(input_buffer) - input_len);
  70                 if (ret <= 0) {
  71                         if (!ret)
  72                                 die("early EOF");
  73                         die("read error on input: %s", strerror(errno));
  74                 }
  75                 input_len += ret;
  76         } while (input_len < min);
  77         return input_buffer;
  78 }
  79
  80 static void use(int bytes)
  81 {
  82         if (bytes > input_len)
  83                 die("used more bytes than were available");
  84         input_len -= bytes;
  85         input_offset += bytes;
  86         consumed_bytes += bytes;
  87 }
  88
  89 static void open_pack_file(void)
  90 {
  91         input_fd = open(pack_name, O_RDONLY);
  92         if (input_fd < 0)
  93                 die("cannot open packfile '%s': %s", pack_name,
  94                     strerror(errno));
  95         SHA1_Init(&input_ctx);
  96 }
  97
  98 static void parse_pack_header(void)
  99 {
 100         struct pack_header *hdr = fill(sizeof(struct pack_header));
 101
 102         /* Header consistency check */
 103         if (hdr->hdr_signature != htonl(PACK_SIGNATURE))
 104                 die("packfile '%s' signature mismatch", pack_name);
 105         if (!pack_version_ok(hdr->hdr_version))
 106                 die("packfile '%s' version %d unsupported",
 107                     pack_name, ntohl(hdr->hdr_version));
 108
 109         nr_objects = ntohl(hdr->hdr_entries);
 110         use(sizeof(struct pack_header));
 111         /*fprintf(stderr, "Indexing %d objects\n", nr_objects);*/
 112 }
 113
 114 static void bad_object(unsigned long offset, const char *format,
 115                        ...) NORETURN __attribute__((format (printf, 2, 3)));
 116
 117 static void bad_object(unsigned long offset, const char *format, ...)
 118 {
 119         va_list params;
 120         char buf[1024];
 121
 122         va_start(params, format);
 123         vsnprintf(buf, sizeof(buf), format, params);
 124         va_end(params);
 125         die("packfile '%s': bad object at offset %lu: %s",
 126             pack_name, offset, buf);
 127 }
 128
 129 static void *unpack_entry_data(unsigned long offset, unsigned long size)
 130 {
 131         z_stream stream;
 132         void *buf = xmalloc(size);
 133
 134         memset(&stream, 0, sizeof(stream));
 135         stream.next_out = buf;
 136         stream.avail_out = size;
 137         stream.next_in = fill(1);
 138         stream.avail_in = input_len;
 139         inflateInit(&stream);
 140
 141         for (;;) {
 142                 int ret = inflate(&stream, 0);
 143                 use(input_len - stream.avail_in);
 144                 if (stream.total_out == size && ret == Z_STREAM_END)
 145                         break;
 146                 if (ret != Z_OK)
 147                         bad_object(offset, "inflate returned %d", ret);
 148                 stream.next_in = fill(1);
 149                 stream.avail_in = input_len;
 150         }
 151         inflateEnd(&stream);
 152         return buf;
 153 }
 154
 155 static void *unpack_raw_entry(struct object_entry *obj, union delta_base *delta_base)
 156 {
 157         unsigned char *p, c;
 158         unsigned long size, base_offset;
 159         unsigned shift;
 160
 161         obj->offset = consumed_bytes;
 162
 163         p = fill(1);
 164         c = *p;
 165         use(1);
 166         obj->type = (c >> 4) & 7;
 167         size = (c & 15);
 168         shift = 4;
 169         while (c & 0x80) {
 170                 p = fill(1);
 171                 c = *p;
 172                 use(1);
 173                 size += (c & 0x7fUL) << shift;
 174                 shift += 7;
 175         }
 176         obj->size = size;
 177
 178         switch (obj->type) {
 179         case OBJ_REF_DELTA:
 180                 hashcpy(delta_base->sha1, fill(20));
 181                 use(20);
 182                 break;
 183         case OBJ_OFS_DELTA:
 184                 memset(delta_base, 0, sizeof(*delta_base));
 185                 p = fill(1);
 186                 c = *p;
 187                 use(1);
 188                 base_offset = c & 127;
 189                 while (c & 128) {
 190                         base_offset += 1;
 191                         if (!base_offset || base_offset & ~(~0UL >> 7))
 192                                 bad_object(obj->offset, "offset value overflow for delta base object");
 193                         p = fill(1);
 194                         c = *p;
 195                         use(1);
 196                         base_offset = (base_offset << 7) + (c & 127);
 197                 }
 198                 delta_base->offset = obj->offset - base_offset;
 199                 if (delta_base->offset >= obj->offset)
 200                         bad_object(obj->offset, "delta base offset is out of bound");
 201                 break;
 202         case OBJ_COMMIT:
 203         case OBJ_TREE:
 204         case OBJ_BLOB:
 205         case OBJ_TAG:
 206                 break;
 207         default:
 208                 bad_object(obj->offset, "bad object type %d", obj->type);
 209         }
 210         obj->hdr_size = consumed_bytes - obj->offset;
 211
 212         return unpack_entry_data(obj->offset, obj->size);
 213 }
 214
 215 static void * get_data_from_pack(struct object_entry *obj)
 216 {
 217         unsigned long from = obj[0].offset + obj[0].hdr_size;
 218         unsigned long len = obj[1].offset - from;
 219         unsigned pg_offset = from % getpagesize();
 220         unsigned char *map, *data;
 221         z_stream stream;
 222         int st;
 223
 224         map = mmap(NULL, len + pg_offset, PROT_READ, MAP_PRIVATE,
 225                    input_fd, from - pg_offset);
 226         if (map == MAP_FAILED)
 227                 die("cannot mmap packfile '%s': %s", pack_name, strerror(errno));
 228         data = xmalloc(obj->size);
 229         memset(&stream, 0, sizeof(stream));
 230         stream.next_out = data;
 231         stream.avail_out = obj->size;
 232         stream.next_in = map + pg_offset;
 233         stream.avail_in = len;
 234         inflateInit(&stream);
 235         while ((st = inflate(&stream, Z_FINISH)) == Z_OK);
 236         inflateEnd(&stream);
 237         if (st != Z_STREAM_END || stream.total_out != obj->size)
 238                 die("serious inflate inconsistency");
 239         munmap(map, len + pg_offset);
 240         return data;
 241 }
 242
 243 static int find_delta(const union delta_base *base)
 244 {
 245         int first = 0, last = nr_deltas;
 246
 247         while (first < last) {
 248                 int next = (first + last) / 2;
 249                 struct delta_entry *delta = &deltas[next];
 250                 int cmp;
 251
 252                 cmp = memcmp(base, &delta->base, UNION_BASE_SZ);
 253                 if (!cmp)
 254                         return next;
 255                 if (cmp < 0) {
 256                         last = next;
 257                         continue;
 258                 }
 259                 first = next+1;
 260         }
 261         return -first-1;
 262 }
 263
 264 static int find_delta_childs(const union delta_base *base,
 265                              int *first_index, int *last_index)
 266 {
 267         int first = find_delta(base);
 268         int last = first;
 269         int end = nr_deltas - 1;
 270
 271         if (first < 0)
 272                 return -1;
 273         while (first > 0 && !memcmp(&deltas[first - 1].base, base, UNION_BASE_SZ))
 274                 --first;
 275         while (last < end && !memcmp(&deltas[last + 1].base, base, UNION_BASE_SZ))
 276                 ++last;
 277         *first_index = first;
 278         *last_index = last;
 279         return 0;
 280 }
 281
 282 static void sha1_object(const void *data, unsigned long size,
 283                         enum object_type type, unsigned char *sha1)
 284 {
 285         SHA_CTX ctx;
 286         char header[50];
 287         int header_size;
 288         const char *type_str;
 289
 290         switch (type) {
 291         case OBJ_COMMIT: type_str = commit_type; break;
 292         case OBJ_TREE:   type_str = tree_type; break;
 293         case OBJ_BLOB:   type_str = blob_type; break;
 294         case OBJ_TAG:    type_str = tag_type; break;
 295         default:
 296                 die("bad type %d", type);
 297         }
 298
 299         header_size = sprintf(header, "%s %lu", type_str, size) + 1;
 300
 301         SHA1_Init(&ctx);
 302         SHA1_Update(&ctx, header, header_size);
 303         SHA1_Update(&ctx, data, size);
 304         SHA1_Final(sha1, &ctx);
 305 }
 306
 307 static void resolve_delta(struct delta_entry *delta, void *base_data,
 308                           unsigned long base_size, enum object_type type)
 309 {
 310         struct object_entry *obj = delta->obj;
 311         void *delta_data;
 312         unsigned long delta_size;
 313         void *result;
 314         unsigned long result_size;
 315         union delta_base delta_base;
 316         int j, first, last;
 317
 318         obj->real_type = type;
 319         delta_data = get_data_from_pack(obj);
 320         delta_size = obj->size;
 321         result = patch_delta(base_data, base_size, delta_data, delta_size,
 322                              &result_size);
 323         free(delta_data);
 324         if (!result)
 325                 bad_object(obj->offset, "failed to apply delta");
 326         sha1_object(result, result_size, type, obj->sha1);
 327
 328         hashcpy(delta_base.sha1, obj->sha1);
 329         if (!find_delta_childs(&delta_base, &first, &last)) {
 330                 for (j = first; j <= last; j++)
 331                         if (deltas[j].obj->type == OBJ_REF_DELTA)
 332                                 resolve_delta(&deltas[j], result, result_size, type);
 333         }
 334
 335         memset(&delta_base, 0, sizeof(delta_base));
 336         delta_base.offset = obj->offset;
 337         if (!find_delta_childs(&delta_base, &first, &last)) {
 338                 for (j = first; j <= last; j++)
 339                         if (deltas[j].obj->type == OBJ_OFS_DELTA)
 340                                 resolve_delta(&deltas[j], result, result_size, type);
 341         }
 342
 343         free(result);
 344 }
 345
 346 static int compare_delta_entry(const void *a, const void *b)
 347 {
 348         const struct delta_entry *delta_a = a;
 349         const struct delta_entry *delta_b = b;
 350         return memcmp(&delta_a->base, &delta_b->base, UNION_BASE_SZ);
 351 }
 352
 353 /* Parse all objects and return the pack content SHA1 hash */
 354 static void parse_pack_objects(unsigned char *sha1)
 355 {
 356         int i;
 357         struct delta_entry *delta = deltas;
 358         void *data;
 359         struct stat st;
 360
 361         /*
 362          * First pass:
 363          * - find locations of all objects;
 364          * - calculate SHA1 of all non-delta objects;
 365          * - remember base SHA1 for all deltas.
 366          */
 367         for (i = 0; i < nr_objects; i++) {
 368                 struct object_entry *obj = &objects[i];
 369                 data = unpack_raw_entry(obj, &delta->base);
 370                 obj->real_type = obj->type;
 371                 if (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {
 372                         nr_deltas++;
 373                         delta->obj = obj;
 374                         delta++;
 375                 } else
 376                         sha1_object(data, obj->size, obj->type, obj->sha1);
 377                 free(data);
 378         }
 379         objects[i].offset = consumed_bytes;
 380
 381         /* Check pack integrity */
 382         SHA1_Update(&input_ctx, input_buffer, input_offset);
 383         SHA1_Final(sha1, &input_ctx);
 384         if (hashcmp(fill(20), sha1))
 385                 die("packfile '%s' SHA1 mismatch", pack_name);
 386         use(20);
 387
 388         /* If input_fd is a file, we should have reached its end now. */
 389         if (fstat(input_fd, &st))
 390                 die("cannot fstat packfile '%s': %s", pack_name, strerror(errno));
 391         if (S_ISREG(st.st_mode) && st.st_size != consumed_bytes)
 392                 die("packfile '%s' has junk at the end", pack_name);
 393
 394         /* Sort deltas by base SHA1/offset for fast searching */
 395         qsort(deltas, nr_deltas, sizeof(struct delta_entry),
 396               compare_delta_entry);
 397
 398         /*
 399          * Second pass:
 400          * - for all non-delta objects, look if it is used as a base for
 401          *   deltas;
 402          * - if used as a base, uncompress the object and apply all deltas,
 403          *   recursively checking if the resulting object is used as a base
 404          *   for some more deltas.
 405          */
 406         for (i = 0; i < nr_objects; i++) {
 407                 struct object_entry *obj = &objects[i];
 408                 union delta_base base;
 409                 int j, ref, ref_first, ref_last, ofs, ofs_first, ofs_last;
 410
 411                 if (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA)
 412                         continue;
 413                 hashcpy(base.sha1, obj->sha1);
 414                 ref = !find_delta_childs(&base, &ref_first, &ref_last);
 415                 memset(&base, 0, sizeof(base));
 416                 base.offset = obj->offset;
 417                 ofs = !find_delta_childs(&base, &ofs_first, &ofs_last);
 418                 if (!ref && !ofs)
 419                         continue;
 420                 data = get_data_from_pack(obj);
 421                 if (ref)
 422                         for (j = ref_first; j <= ref_last; j++)
 423                                 if (deltas[j].obj->type == OBJ_REF_DELTA)
 424                                         resolve_delta(&deltas[j], data,
 425                                                       obj->size, obj->type);
 426                 if (ofs)
 427                         for (j = ofs_first; j <= ofs_last; j++)
 428                                 if (deltas[j].obj->type == OBJ_OFS_DELTA)
 429                                         resolve_delta(&deltas[j], data,
 430                                                       obj->size, obj->type);
 431                 free(data);
 432         }
 433
 434         /* Check for unresolved deltas */
 435         for (i = 0; i < nr_deltas; i++) {
 436                 if (deltas[i].obj->real_type == OBJ_REF_DELTA ||
 437                     deltas[i].obj->real_type == OBJ_OFS_DELTA)
 438                         die("packfile '%s' has unresolved deltas",  pack_name);
 439         }
 440 }
 441
 442 static int sha1_compare(const void *_a, const void *_b)
 443 {
 444         struct object_entry *a = *(struct object_entry **)_a;
 445         struct object_entry *b = *(struct object_entry **)_b;
 446         return hashcmp(a->sha1, b->sha1);
 447 }
 448
 449 /*
 450  * On entry *sha1 contains the pack content SHA1 hash, on exit it is
 451  * the SHA1 hash of sorted object names.
 452  */
 453 static void write_index_file(const char *index_name, unsigned char *sha1)
 454 {
 455         struct sha1file *f;
 456         struct object_entry **sorted_by_sha, **list, **last;
 457         unsigned int array[256];
 458         int i;
 459         SHA_CTX ctx;
 460
 461         if (nr_objects) {
 462                 sorted_by_sha =
 463                         xcalloc(nr_objects, sizeof(struct object_entry *));
 464                 list = sorted_by_sha;
 465                 last = sorted_by_sha + nr_objects;
 466                 for (i = 0; i < nr_objects; ++i)
 467                         sorted_by_sha[i] = &objects[i];
 468                 qsort(sorted_by_sha, nr_objects, sizeof(sorted_by_sha[0]),
 469                       sha1_compare);
 470
 471         }
 472         else
 473                 sorted_by_sha = list = last = NULL;
 474
 475         unlink(index_name);
 476         f = sha1create("%s", index_name);
 477
 478         /*
 479          * Write the first-level table (the list is sorted,
 480          * but we use a 256-entry lookup to be able to avoid
 481          * having to do eight extra binary search iterations).
 482          */
 483         for (i = 0; i < 256; i++) {
 484                 struct object_entry **next = list;
 485                 while (next < last) {
 486                         struct object_entry *obj = *next;
 487                         if (obj->sha1[0] != i)
 488                                 break;
 489                         next++;
 490                 }
 491                 array[i] = htonl(next - sorted_by_sha);
 492                 list = next;
 493         }
 494         sha1write(f, array, 256 * sizeof(int));
 495
 496         /* recompute the SHA1 hash of sorted object names.
 497          * currently pack-objects does not do this, but that
 498          * can be fixed.
 499          */
 500         SHA1_Init(&ctx);
 501         /*
 502          * Write the actual SHA1 entries..
 503          */
 504         list = sorted_by_sha;
 505         for (i = 0; i < nr_objects; i++) {
 506                 struct object_entry *obj = *list++;
 507                 unsigned int offset = htonl(obj->offset);
 508                 sha1write(f, &offset, 4);
 509                 sha1write(f, obj->sha1, 20);
 510                 SHA1_Update(&ctx, obj->sha1, 20);
 511         }
 512         sha1write(f, sha1, 20);
 513         sha1close(f, NULL, 1);
 514         free(sorted_by_sha);
 515         SHA1_Final(sha1, &ctx);
 516 }
 517
 518 int main(int argc, char **argv)
 519 {
 520         int i;
 521         char *index_name = NULL;
 522         char *index_name_buf = NULL;
 523         unsigned char sha1[20];
 524
 525         for (i = 1; i < argc; i++) {
 526                 const char *arg = argv[i];
 527
 528                 if (*arg == '-') {
 529                         if (!strcmp(arg, "-o")) {
 530                                 if (index_name || (i+1) >= argc)
 531                                         usage(index_pack_usage);
 532                                 index_name = argv[++i];
 533                         } else
 534                                 usage(index_pack_usage);
 535                         continue;
 536                 }
 537
 538                 if (pack_name)
 539                         usage(index_pack_usage);
 540                 pack_name = arg;
 541         }
 542
 543         if (!pack_name)
 544                 usage(index_pack_usage);
 545         if (!index_name) {
 546                 int len = strlen(pack_name);
 547                 if (!has_extension(pack_name, ".pack"))
 548                         die("packfile name '%s' does not end with '.pack'",
 549                             pack_name);
 550                 index_name_buf = xmalloc(len);
 551                 memcpy(index_name_buf, pack_name, len - 5);
 552                 strcpy(index_name_buf + len - 5, ".idx");
 553                 index_name = index_name_buf;
 554         }
 555
 556         open_pack_file();
 557         parse_pack_header();
 558         objects = xcalloc(nr_objects + 1, sizeof(struct object_entry));
 559         deltas = xcalloc(nr_objects, sizeof(struct delta_entry));
 560         parse_pack_objects(sha1);
 561         free(deltas);
 562         write_index_file(index_name, sha1);
 563         free(objects);
 564         free(index_name_buf);
 565
 566         printf("%s\n", sha1_to_hex(sha1));
 567
 568         return 0;
 569 }