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