src/index.c

   1 /*
   2  * This file is free software; you can redistribute it and/or modify
   3  * it under the terms of the GNU General Public License, version 2,
   4  * as published by the Free Software Foundation.
   5  *
   6  * In addition to the permissions in the GNU General Public License,
   7  * the authors give you unlimited permission to link the compiled
   8  * version of this file into combinations with other programs,
   9  * and to distribute those combinations without any restriction
  10  * coming from the use of this file.  (The General Public License
  11  * restrictions do apply in other respects; for example, they cover
  12  * modification of the file, and distribution when not linked into
  13  * a combined executable.)
  14  *
  15  * This file is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; see the file COPYING.  If not, write to
  22  * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  23  * Boston, MA 02110-1301, USA.
  24  */
  25
  26 #include <stddef.h>
  27
  28 #include "common.h"
  29 #include "index.h"
  30 #include "hash.h"
  31 #include "git/odb.h"
  32
  33 #define entry_padding(type, len) (8 - ((offsetof(type, path) + (len)) & 0x7))
  34 #define short_entry_padding(len) entry_padding(struct entry_short, len)
  35 #define long_entry_padding(len) entry_padding(struct entry_long, len)
  36
  37 #define entry_size(type,len) ((offsetof(type, path) + (len) + 8) & ~7)
  38 #define short_entry_size(len) entry_size(struct entry_short, len)
  39 #define long_entry_size(len) entry_size(struct entry_long, len)
  40
  41 #define minimal_entry_size (offsetof(struct entry_short, path))
  42
  43 static const char INDEX_HEADER_SIG[] = {'D', 'I', 'R', 'C'};
  44 static const char INDEX_EXT_TREECACHE_SIG[] = {'T', 'R', 'E', 'E'};
  45
  46 static const size_t INDEX_FOOTER_SIZE = GIT_OID_RAWSZ;
  47 static const size_t INDEX_HEADER_SIZE = 12;
  48
  49 static const unsigned int INDEX_VERSION_NUMBER = 2;
  50
  51 struct index_header {
  52         uint32_t signature;
  53         uint32_t version;
  54         uint32_t entry_count;
  55 };
  56
  57 struct index_extension {
  58         char signature[4];
  59         uint32_t extension_size;
  60 };
  61
  62 struct entry_short {
  63         git_index_time ctime;
  64         git_index_time mtime;
  65         uint32_t dev;
  66         uint32_t ino;
  67         uint32_t mode;
  68         uint32_t uid;
  69         uint32_t gid;
  70         uint32_t file_size;
  71         git_oid oid;
  72         uint16_t flags;
  73         char path[1]; /* arbritrary length */
  74 };
  75
  76 struct entry_long {
  77         git_index_time ctime;
  78         git_index_time mtime;
  79         uint32_t dev;
  80         uint32_t ino;
  81         uint32_t mode;
  82         uint32_t uid;
  83         uint32_t gid;
  84         uint32_t file_size;
  85         git_oid oid;
  86         uint16_t flags;
  87         uint16_t flags_extended;
  88         char path[1]; /* arbritrary length */
  89 };
  90
  91 /* local declarations */
  92 size_t git_index__parse_extension(git_index *index, const char *buffer, size_t buffer_size);
  93 size_t git_index__parse_entry(git_index_entry *dest, const void *buffer, size_t buffer_size);
  94 int git_index__parse_treecache(git_index *index, const char *buffer, size_t buffer_size);
  95 int git_index__parse_header(struct index_header *dest, const void *buffer);
  96 int git_index__parse(git_index *index, const char *buffer, size_t buffer_size);
  97
  98 int git_index__remove_pos(git_index *index, unsigned int position);
  99 int git_index__append(git_index *index, const git_index_entry *entry);
 100
 101 void git_index_tree__free(git_index_tree *tree);
 102 git_index_tree *git_index_tree__parse(const char **, const char *, git_index_tree *);
 103
 104
 105 git_index *git_index_alloc(const char *index_path)
 106 {
 107         git_index *index;
 108
 109         if (index_path == NULL)
 110                 return NULL;
 111
 112         index = git__malloc(sizeof(git_index));
 113         if (index == NULL)
 114                 return NULL;
 115
 116         memset(index, 0x0, sizeof(git_index));
 117
 118         index->index_file_path = git__strdup(index_path);
 119         if (index->index_file_path == NULL) {
 120                 free(index);
 121                 return NULL;
 122         }
 123
 124         /* Check if index file is stored on disk already */
 125         if (gitfo_exists(index->index_file_path) == 0)
 126                 index->on_disk = 1;
 127
 128         return index;
 129 }
 130
 131 void git_index_clear(git_index *index)
 132 {
 133         unsigned int i;
 134         for (i = 0; i < index->entry_count; ++i)
 135                 free(index->entries[i].path);
 136
 137         index->entry_count = 0;
 138         index->last_modified = 0;
 139         index->sorted = 1;
 140
 141         git_index_tree__free(index->tree);
 142         index->tree = NULL;
 143 }
 144
 145 void git_index_free(git_index *index)
 146 {
 147         free(index->entries);
 148         index->entries = NULL;
 149         free(index->index_file_path);
 150         free(index);
 151 }
 152
 153
 154 int git_index_read(git_index *index)
 155 {
 156         struct stat indexst;
 157         int error = 0;
 158
 159         if (index->index_file_path == NULL)
 160                 return GIT_ERROR;
 161
 162         if (!index->on_disk || gitfo_exists(index->index_file_path) < 0) {
 163                 git_index_clear(index);
 164                 index->on_disk = 0;
 165                 return 0;
 166         }
 167
 168         if (gitfo_stat(index->index_file_path, &indexst) < 0)
 169                 return GIT_EOSERR;
 170
 171         if (indexst.st_mtime != index->last_modified) {
 172
 173                 gitfo_buf buffer;
 174
 175                 if (gitfo_read_file(&buffer, index->index_file_path) < 0)
 176                         return GIT_EOSERR;
 177
 178                 git_index_clear(index);
 179                 error = git_index__parse(index, buffer.data, buffer.len);
 180
 181                 if (error == 0)
 182                         index->last_modified = indexst.st_mtime;
 183
 184                 gitfo_free_buf(&buffer);
 185         }
 186
 187         return error;
 188 }
 189
 190 int git_index_write(git_index *index)
 191 {
 192         git_filelock file;
 193         struct stat indexst;
 194
 195         if (!index->sorted)
 196                 git_index__sort(index);
 197
 198         if (git_filelock_init(&file, index->index_file_path) < 0)
 199                 return GIT_EOSERR;
 200
 201         if (git_filelock_lock(&file, 0) < 0)
 202                 return GIT_EOSERR;
 203
 204         if (git_index__write(index, &file) < 0) {
 205                 git_filelock_unlock(&file);
 206                 return GIT_EOSERR;
 207         }
 208
 209         if (git_filelock_commit(&file) < 0)
 210                 return GIT_EOSERR;
 211
 212         if (gitfo_stat(index->index_file_path, &indexst) == 0) {
 213                 index->last_modified = indexst.st_mtime;
 214                 index->on_disk = 1;
 215         }
 216
 217         return 0;
 218 }
 219
 220 int git_index_add(git_index *index, const char *filename, int stage)
 221 {
 222         git_index_entry entry;
 223         size_t path_length;
 224
 225         memset(&entry, 0x0, sizeof(git_index_entry));
 226
 227         path_length = strlen(filename);
 228
 229         if (path_length < GIT_IDXENTRY_NAMEMASK)
 230                 entry.flags |= path_length;
 231         else
 232                 entry.flags |= path_length;
 233
 234         if (stage < 0 || stage > 3)
 235                 return GIT_ERROR;
 236
 237         entry.flags |= (stage << GIT_IDXENTRY_STAGESHIFT);
 238
 239         entry.path = git__strdup(filename);
 240
 241         return git_index__append(index, &entry);
 242 }
 243
 244 void git_index__sort(git_index *index)
 245 {
 246         git_index_entry pivot;
 247         int i, j;
 248
 249         if (index->sorted)
 250                 return;
 251
 252         for (i = 1; i < (int)index->entry_count; ++i) {
 253
 254                 memcpy(&pivot, &index->entries[i], sizeof(git_index_entry));
 255                 j = i - 1;
 256
 257                 while (j >= 0 && strcmp(pivot.path, index->entries[j].path) < 0) {
 258                         memcpy(&index->entries[j + 1], &index->entries[j], sizeof(git_index_entry));
 259                         j = j - 1;
 260                 }
 261
 262                 memcpy(&index->entries[j + 1], &pivot, sizeof(git_index_entry));
 263         }
 264
 265         index->sorted = 1;
 266 }
 267
 268 int git_index__append(git_index *index, const git_index_entry *source_entry)
 269 {
 270         git_index_entry *offset;
 271
 272         /* Resize the entries array */
 273         if (index->entry_count + 1 > index->entries_size) {
 274                 git_index_entry *new_entries;
 275                 size_t new_size;
 276
 277                 new_size = (unsigned int)(index->entries_size * 1.5f);
 278                 if ((new_entries = git__malloc(new_size * sizeof(git_index_entry))) == NULL)
 279                         return GIT_ENOMEM;
 280
 281                 memcpy(new_entries, index->entries, index->entry_count * sizeof(git_index_entry));
 282                 free(index->entries);
 283
 284                 index->entries_size = new_size;
 285                 index->entries = new_entries;
 286         }
 287
 288         offset = &index->entries[index->entry_count];
 289         index->entry_count++;
 290
 291         memcpy(offset, source_entry, sizeof(git_index_entry));
 292         index->sorted = 0;
 293
 294         return 0;
 295 }
 296
 297 int git_index__remove_pos(git_index *index, unsigned int position)
 298 {
 299         git_index_entry *offset;
 300         size_t copy_size;
 301
 302         offset = &index->entries[position];
 303         index->entry_count--;
 304         copy_size = (index->entry_count - position) * sizeof(git_index_entry);
 305
 306         memcpy(offset, offset + sizeof(git_index_entry), copy_size);
 307
 308         return 0;
 309 }
 310
 311 int git_index_find(git_index *index, const char *path)
 312 {
 313         int low = 0, high = index->entry_count;
 314
 315         if (!index->sorted)
 316                 git_index__sort(index);
 317
 318         while (low < high) {
 319                 int mid = (low + high) >> 1;
 320                 int cmp = strcmp(path, index->entries[mid].path);
 321
 322                 if (cmp < 0)
 323                         high = mid;
 324
 325                 else if (cmp == 0) {
 326
 327                         while (mid > 0 && strcmp(path, index->entries[mid - 1].path) == 0)
 328                                 mid--;
 329
 330                         return mid;
 331
 332                 } else
 333                         low = mid + 1;
 334         }
 335
 336         return GIT_ENOTFOUND; /* NOT FOUND */
 337 }
 338
 339 void git_index_tree__free(git_index_tree *tree)
 340 {
 341         unsigned int i;
 342
 343         if (tree == NULL)
 344                 return;
 345
 346         for (i = 0; i < tree->children_count; ++i)
 347                 git_index_tree__free(tree->children[i]);
 348
 349         free(tree->name);
 350         free(tree->children);
 351         free(tree);
 352 }
 353
 354 git_index_tree *git_index_tree__parse(
 355                 const char **buffer_in, const char *buffer_end, git_index_tree *parent)
 356 {
 357         git_index_tree *tree;
 358         const char *name_start, *buffer;
 359
 360         if ((tree = git__malloc(sizeof(git_index_tree))) == NULL)
 361                 return NULL;
 362
 363         memset(tree, 0x0, sizeof(git_index_tree));
 364         tree->parent = parent;
 365
 366         buffer = name_start = *buffer_in;
 367
 368         if ((buffer = memchr(buffer, '\0', buffer_end - buffer)) == NULL)
 369                 goto error_cleanup;
 370
 371         /* NUL-terminated tree name */
 372         tree->name = git__strdup(name_start);
 373         if (++buffer >= buffer_end)
 374                 goto error_cleanup;
 375
 376         /* Blank-terminated ASCII decimal number of entries in this tree */
 377         tree->entries = strtol(buffer, (char **)&buffer, 10);
 378         if (*buffer != ' ' || ++buffer >= buffer_end)
 379                 goto error_cleanup;
 380
 381          /* Number of children of the tree, newline-terminated */
 382         tree->children_count = strtol(buffer, (char **)&buffer, 10);
 383         if (*buffer != '\n' || ++buffer >= buffer_end)
 384                 goto error_cleanup;
 385
 386         /* 160-bit SHA-1 for this tree and it's children */
 387         if (buffer + GIT_OID_RAWSZ > buffer_end)
 388                 goto error_cleanup;
 389
 390         git_oid_mkraw(&tree->oid, (const unsigned char *)buffer);
 391         buffer += GIT_OID_RAWSZ;
 392
 393         /* Parse children: */
 394         if (tree->children_count > 0) {
 395                 unsigned int i;
 396
 397                 tree->children = git__malloc(tree->children_count * sizeof(git_index_tree *));
 398                 if (tree->children == NULL)
 399                         goto error_cleanup;
 400
 401                 for (i = 0; i < tree->children_count; ++i) {
 402                         tree->children[i] = git_index_tree__parse(&buffer, buffer_end, tree);
 403
 404                         if (tree->children[i] == NULL)
 405                                 goto error_cleanup;
 406                 }
 407         }
 408
 409         *buffer_in = buffer;
 410         return tree;
 411
 412 error_cleanup:
 413         git_index_tree__free(tree);
 414         return NULL;
 415 }
 416
 417 int git_index__parse_tree(git_index *index, const char *buffer, size_t buffer_size)
 418 {
 419         const char *buffer_end = buffer + buffer_size;
 420
 421         index->tree = git_index_tree__parse(&buffer, buffer_end, NULL);
 422         return (index->tree != NULL && buffer == buffer_end) ? 0 : GIT_EOBJCORRUPTED;
 423 }
 424
 425 size_t git_index__parse_entry(git_index_entry *dest, const void *buffer, size_t buffer_size)
 426 {
 427         size_t path_length, entry_size;
 428         uint16_t flags_raw;
 429         const char *path_ptr;
 430         const struct entry_short *source;
 431
 432         if (INDEX_FOOTER_SIZE + minimal_entry_size > buffer_size)
 433                 return 0;
 434
 435         source = (const struct entry_short *)(buffer);
 436
 437         dest->ctime.seconds = ntohl(source->ctime.seconds);
 438         dest->ctime.nanoseconds = ntohl(source->ctime.nanoseconds);
 439         dest->mtime.seconds = ntohl(source->mtime.seconds);
 440         dest->mtime.nanoseconds = ntohl(source->mtime.nanoseconds);
 441         dest->dev = ntohl(source->dev);
 442         dest->ino = ntohl(source->ino);
 443         dest->mode = ntohl(source->mode);
 444         dest->uid = ntohl(source->uid);
 445         dest->gid = ntohl(source->gid);
 446         dest->file_size = ntohl(source->file_size);
 447         git_oid_cpy(&dest->oid, &source->oid);
 448         dest->flags = ntohs(source->flags);
 449
 450         if (dest->flags & GIT_IDXENTRY_EXTENDED) {
 451                 struct entry_long *source_l = (struct entry_long *)source;
 452                 path_ptr = source_l->path;
 453
 454                 flags_raw = ntohs(source_l->flags_extended);
 455                 memcpy(&dest->flags_extended, &flags_raw, 2);
 456         } else
 457                 path_ptr = source->path;
 458
 459         path_length = dest->flags & GIT_IDXENTRY_NAMEMASK;
 460
 461         /* if this is a very long string, we must find its
 462          * real length without overflowing */
 463         if (path_length == 0xFFF) {
 464                 const char *path_end;
 465
 466                 path_end = memchr(path_ptr, '\0', buffer_size);
 467                 if (path_end == NULL)
 468                         return 0;
 469
 470                 path_length = path_end - path_ptr;
 471         }
 472
 473         if (dest->flags & GIT_IDXENTRY_EXTENDED)
 474                 entry_size = long_entry_size(path_length);
 475         else
 476                 entry_size = short_entry_size(path_length);
 477
 478         if (INDEX_FOOTER_SIZE + entry_size > buffer_size)
 479                 return 0;
 480
 481         dest->path = git__strdup(path_ptr);
 482
 483         return entry_size;
 484 }
 485
 486 int git_index__parse_header(struct index_header *dest, const void *buffer)
 487 {
 488         const struct index_header *source;
 489         source = (const struct index_header *)(buffer);
 490
 491         dest->signature = source->signature;
 492         if (memcmp(&dest->signature, INDEX_HEADER_SIG, 4) != 0)
 493                 return GIT_EOBJCORRUPTED;
 494
 495         dest->version = ntohl(source->version);
 496         if (dest->version != INDEX_VERSION_NUMBER)
 497                 return GIT_EOBJCORRUPTED;
 498
 499         dest->entry_count = ntohl(source->entry_count);
 500         return 0;
 501 }
 502
 503 size_t git_index__parse_extension(git_index *index, const char *buffer, size_t buffer_size)
 504 {
 505         const struct index_extension *source;
 506         struct index_extension dest;
 507         size_t total_size;
 508
 509         source = (const struct index_extension *)(buffer);
 510
 511         memcpy(dest.signature, source->signature, 4);
 512         dest.extension_size = ntohl(source->extension_size);
 513
 514         total_size = dest.extension_size + sizeof(struct index_extension);
 515
 516         if (buffer_size - total_size < INDEX_FOOTER_SIZE)
 517                 return 0;
 518
 519         /* optional extension */
 520         if (dest.signature[0] >= 'A' && dest.signature[0] <= 'Z') {
 521                 /* tree cache */
 522                 if (memcmp(dest.signature, INDEX_EXT_TREECACHE_SIG, 4) == 0) {
 523
 524                         if (git_index__parse_tree(index, buffer + 8, dest.extension_size) < 0)
 525                                 return 0;
 526                 }
 527         } else {
 528                 /* we cannot handle non-ignorable extensions;
 529                  * in fact they aren't even defined in the standard */
 530                 return 0;
 531         }
 532
 533         return total_size;
 534 }
 535
 536 int git_index__parse(git_index *index, const char *buffer, size_t buffer_size)
 537 {
 538         unsigned int i;
 539         struct index_header header;
 540         git_oid checksum_calculated, checksum_expected;
 541
 542 #define seek_forward(_increase) { \
 543         if (_increase >= buffer_size) \
 544                 return GIT_EOBJCORRUPTED; \
 545         buffer += _increase; \
 546         buffer_size -= _increase;\
 547 }
 548
 549         if (buffer_size < INDEX_HEADER_SIZE + INDEX_FOOTER_SIZE)
 550                 return GIT_EOBJCORRUPTED;
 551
 552         /* Precalculate the SHA1 of the files's contents -- we'll match it to
 553          * the provided SHA1 in the footer */
 554         git_hash_buf(&checksum_calculated, (const void *)buffer, buffer_size - INDEX_FOOTER_SIZE);
 555
 556         /* Parse header */
 557         if (git_index__parse_header(&header, buffer) < 0)
 558                 return GIT_EOBJCORRUPTED;
 559
 560         seek_forward(INDEX_HEADER_SIZE);
 561
 562         index->entry_count = header.entry_count;
 563
 564         /* If there is already a entires array, reuse it if it can hold all the
 565          * entries. If not, free and reallocate */
 566         if (index->entry_count > index->entries_size) {
 567                 free(index->entries);
 568                 index->entries_size = (uint32_t)(index->entry_count * 1.3f);
 569                 index->entries = git__malloc(index->entries_size * sizeof(git_index_entry));
 570         }
 571
 572         /* Parse all the entries */
 573         for (i = 0; i < index->entry_count && buffer_size > INDEX_FOOTER_SIZE; ++i) {
 574                 size_t entry_size;
 575                 entry_size = git_index__parse_entry(&index->entries[i], buffer, buffer_size);
 576
 577                 /* 0 bytes read means an object corruption */
 578                 if (entry_size == 0)
 579                         return GIT_EOBJCORRUPTED;
 580
 581                 seek_forward(entry_size);
 582         }
 583
 584         /* There's still space for some extensions! */
 585         while (buffer_size > INDEX_FOOTER_SIZE) {
 586                 size_t extension_size;
 587
 588                 extension_size = git_index__parse_extension(index, buffer, buffer_size);
 589
 590                 /* see if we have read any bytes from the extension */
 591                 if (extension_size == 0)
 592                         return GIT_EOBJCORRUPTED;
 593
 594                 seek_forward(extension_size);
 595         }
 596
 597         if (buffer_size != INDEX_FOOTER_SIZE)
 598                 return GIT_EOBJCORRUPTED;
 599
 600         /* 160-bit SHA-1 over the content of the index file before this checksum. */
 601         git_oid_mkraw(&checksum_expected, (const unsigned char *)buffer);
 602
 603         if (git_oid_cmp(&checksum_calculated, &checksum_expected) != 0)
 604                 return GIT_EOBJCORRUPTED;
 605
 606 #undef seek_forward
 607
 608         return 0;
 609 }
 610
 611 int git_index__write(git_index *index, git_filelock *file)
 612 {
 613         static const char NULL_BYTES[] = {0, 0, 0, 0, 0, 0, 0, 0};
 614
 615         int error = 0;
 616         unsigned int i;
 617
 618         git_hash_ctx *digest;
 619         git_oid hash_final;
 620
 621         if (index == NULL || file == NULL || !file->is_locked)
 622                 return GIT_ERROR;
 623
 624         if ((digest = git_hash_new_ctx()) == NULL)
 625                 return GIT_ERROR;
 626
 627 #define WRITE_WORD(_word) {\
 628         uint32_t network_word = htonl((_word));\
 629         git_filelock_write(file, &network_word, 4);\
 630         git_hash_update(digest, &network_word, 4);\
 631 }
 632
 633 #define WRITE_SHORT(_shrt) {\
 634         uint16_t network_shrt = htons((_shrt));\
 635         git_filelock_write(file, &network_shrt, 2);\
 636         git_hash_update(digest, &network_shrt, 2);\
 637 }
 638
 639 #define WRITE_BYTES(_bytes, _n) {\
 640         git_filelock_write(file, _bytes, _n);\
 641         git_hash_update(digest, _bytes, _n);\
 642 }
 643
 644         WRITE_BYTES(INDEX_HEADER_SIG, 4);
 645
 646         WRITE_WORD(INDEX_VERSION_NUMBER);
 647         WRITE_WORD(index->entry_count);
 648
 649         for (i = 0; i < index->entry_count; ++i) {
 650                 git_index_entry *entry;
 651                 size_t path_length, padding;
 652
 653                 entry = &index->entries[i];
 654                 path_length = strlen(entry->path);
 655
 656                 WRITE_WORD(entry->ctime.seconds);
 657                 WRITE_WORD(entry->ctime.nanoseconds);
 658                 WRITE_WORD(entry->mtime.seconds);
 659                 WRITE_WORD(entry->mtime.nanoseconds);
 660                 WRITE_WORD(entry->dev);
 661                 WRITE_WORD(entry->ino);
 662                 WRITE_WORD(entry->mode);
 663                 WRITE_WORD(entry->uid);
 664                 WRITE_WORD(entry->gid);
 665                 WRITE_WORD(entry->file_size);
 666                 WRITE_BYTES(entry->oid.id, GIT_OID_RAWSZ);
 667                 WRITE_SHORT(entry->flags);
 668
 669                 if (entry->flags & GIT_IDXENTRY_EXTENDED) {
 670                         WRITE_SHORT(entry->flags_extended);
 671                         padding = long_entry_padding(path_length);
 672                 } else
 673                         padding = short_entry_padding(path_length);
 674
 675                 WRITE_BYTES(entry->path, path_length);
 676                 WRITE_BYTES(NULL_BYTES, padding);
 677         }
 678
 679 #undef WRITE_WORD
 680 #undef WRITE_BYTES
 681 #undef WRITE_SHORT
 682 #undef WRITE_FLAGS
 683
 684         /* TODO: write extensions (tree cache) */
 685
 686         git_hash_final(&hash_final, digest);
 687         git_filelock_write(file, hash_final.id, GIT_OID_RAWSZ);
 688
 689         return error;
 690 }