read-cache.c

   1 /*
   2  * GIT - The information manager from hell
   3  *
   4  * Copyright (C) Linus Torvalds, 2005
   5  */
   6 #include "cache.h"
   7
   8 int trust_executable_bit = 1;
   9 struct cache_entry **active_cache = NULL;
  10 unsigned int active_nr = 0, active_alloc = 0, active_cache_changed = 0;
  11
  12 /*
  13  * This only updates the "non-critical" parts of the directory
  14  * cache, ie the parts that aren't tracked by GIT, and only used
  15  * to validate the cache.
  16  */
  17 void fill_stat_cache_info(struct cache_entry *ce, struct stat *st)
  18 {
  19         ce->ce_ctime.sec = htonl(st->st_ctime);
  20         ce->ce_mtime.sec = htonl(st->st_mtime);
  21 #ifdef USE_NSEC
  22         ce->ce_ctime.nsec = htonl(st->st_ctim.tv_nsec);
  23         ce->ce_mtime.nsec = htonl(st->st_mtim.tv_nsec);
  24 #endif
  25         ce->ce_dev = htonl(st->st_dev);
  26         ce->ce_ino = htonl(st->st_ino);
  27         ce->ce_uid = htonl(st->st_uid);
  28         ce->ce_gid = htonl(st->st_gid);
  29         ce->ce_size = htonl(st->st_size);
  30 }
  31
  32 int ce_match_stat(struct cache_entry *ce, struct stat *st)
  33 {
  34         unsigned int changed = 0;
  35
  36         switch (ntohl(ce->ce_mode) & S_IFMT) {
  37         case S_IFREG:
  38                 changed |= !S_ISREG(st->st_mode) ? TYPE_CHANGED : 0;
  39                 /* We consider only the owner x bit to be relevant for "mode changes" */
  40                 if (0100 & (ntohl(ce->ce_mode) ^ st->st_mode))
  41                         changed |= MODE_CHANGED;
  42                 break;
  43         case S_IFLNK:
  44                 changed |= !S_ISLNK(st->st_mode) ? TYPE_CHANGED : 0;
  45                 break;
  46         default:
  47                 die("internal error: ce_mode is %o", ntohl(ce->ce_mode));
  48         }
  49         if (ce->ce_mtime.sec != htonl(st->st_mtime))
  50                 changed |= MTIME_CHANGED;
  51         if (ce->ce_ctime.sec != htonl(st->st_ctime))
  52                 changed |= CTIME_CHANGED;
  53
  54 #ifdef USE_NSEC
  55         /*
  56          * nsec seems unreliable - not all filesystems support it, so
  57          * as long as it is in the inode cache you get right nsec
  58          * but after it gets flushed, you get zero nsec.
  59          */
  60         if (ce->ce_mtime.nsec != htonl(st->st_mtim.tv_nsec))
  61                 changed |= MTIME_CHANGED;
  62         if (ce->ce_ctime.nsec != htonl(st->st_ctim.tv_nsec))
  63                 changed |= CTIME_CHANGED;
  64 #endif
  65
  66         if (ce->ce_uid != htonl(st->st_uid) ||
  67             ce->ce_gid != htonl(st->st_gid))
  68                 changed |= OWNER_CHANGED;
  69         if (ce->ce_ino != htonl(st->st_ino))
  70                 changed |= INODE_CHANGED;
  71
  72 #ifdef USE_STDEV
  73         /*
  74          * st_dev breaks on network filesystems where different
  75          * clients will have different views of what "device"
  76          * the filesystem is on
  77          */
  78         if (ce->ce_dev != htonl(st->st_dev))
  79                 changed |= INODE_CHANGED;
  80 #endif
  81
  82         if (ce->ce_size != htonl(st->st_size))
  83                 changed |= DATA_CHANGED;
  84         return changed;
  85 }
  86
  87 static int ce_compare_data(struct cache_entry *ce, struct stat *st)
  88 {
  89         int match = -1;
  90         int fd = open(ce->name, O_RDONLY);
  91
  92         if (fd >= 0) {
  93                 unsigned char sha1[20];
  94                 if (!index_fd(sha1, fd, st, 0, NULL))
  95                         match = memcmp(sha1, ce->sha1, 20);
  96                 close(fd);
  97         }
  98         return match;
  99 }
 100
 101 static int ce_compare_link(struct cache_entry *ce, unsigned long expected_size)
 102 {
 103         int match = -1;
 104         char *target;
 105         void *buffer;
 106         unsigned long size;
 107         char type[10];
 108         int len;
 109
 110         target = xmalloc(expected_size);
 111         len = readlink(ce->name, target, expected_size);
 112         if (len != expected_size) {
 113                 free(target);
 114                 return -1;
 115         }
 116         buffer = read_sha1_file(ce->sha1, type, &size);
 117         if (!buffer) {
 118                 free(target);
 119                 return -1;
 120         }
 121         if (size == expected_size)
 122                 match = memcmp(buffer, target, size);
 123         free(buffer);
 124         free(target);
 125         return match;
 126 }
 127
 128 int ce_modified(struct cache_entry *ce, struct stat *st)
 129 {
 130         int changed;
 131         changed = ce_match_stat(ce, st);
 132         if (!changed)
 133                 return 0;
 134
 135         /*
 136          * If the mode or type has changed, there's no point in trying
 137          * to refresh the entry - it's not going to match
 138          */
 139         if (changed & (MODE_CHANGED | TYPE_CHANGED))
 140                 return changed;
 141
 142         /* Immediately after read-tree or update-index --cacheinfo,
 143          * the length field is zero.  For other cases the ce_size
 144          * should match the SHA1 recorded in the index entry.
 145          */
 146         if ((changed & DATA_CHANGED) && ce->ce_size != htonl(0))
 147                 return changed;
 148
 149         switch (st->st_mode & S_IFMT) {
 150         case S_IFREG:
 151                 if (ce_compare_data(ce, st))
 152                         return changed | DATA_CHANGED;
 153                 break;
 154         case S_IFLNK:
 155                 if (ce_compare_link(ce, st->st_size))
 156                         return changed | DATA_CHANGED;
 157                 break;
 158         default:
 159                 return changed | TYPE_CHANGED;
 160         }
 161         return 0;
 162 }
 163
 164 int base_name_compare(const char *name1, int len1, int mode1,
 165                       const char *name2, int len2, int mode2)
 166 {
 167         unsigned char c1, c2;
 168         int len = len1 < len2 ? len1 : len2;
 169         int cmp;
 170
 171         cmp = memcmp(name1, name2, len);
 172         if (cmp)
 173                 return cmp;
 174         c1 = name1[len];
 175         c2 = name2[len];
 176         if (!c1 && S_ISDIR(mode1))
 177                 c1 = '/';
 178         if (!c2 && S_ISDIR(mode2))
 179                 c2 = '/';
 180         return (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0;
 181 }
 182
 183 int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)
 184 {
 185         int len1 = flags1 & CE_NAMEMASK;
 186         int len2 = flags2 & CE_NAMEMASK;
 187         int len = len1 < len2 ? len1 : len2;
 188         int cmp;
 189
 190         cmp = memcmp(name1, name2, len);
 191         if (cmp)
 192                 return cmp;
 193         if (len1 < len2)
 194                 return -1;
 195         if (len1 > len2)
 196                 return 1;
 197         if (flags1 < flags2)
 198                 return -1;
 199         if (flags1 > flags2)
 200                 return 1;
 201         return 0;
 202 }
 203
 204 int cache_name_pos(const char *name, int namelen)
 205 {
 206         int first, last;
 207
 208         first = 0;
 209         last = active_nr;
 210         while (last > first) {
 211                 int next = (last + first) >> 1;
 212                 struct cache_entry *ce = active_cache[next];
 213                 int cmp = cache_name_compare(name, namelen, ce->name, ntohs(ce->ce_flags));
 214                 if (!cmp)
 215                         return next;
 216                 if (cmp < 0) {
 217                         last = next;
 218                         continue;
 219                 }
 220                 first = next+1;
 221         }
 222         return -first-1;
 223 }
 224
 225 /* Remove entry, return true if there are more entries to go.. */
 226 int remove_cache_entry_at(int pos)
 227 {
 228         active_cache_changed = 1;
 229         active_nr--;
 230         if (pos >= active_nr)
 231                 return 0;
 232         memmove(active_cache + pos, active_cache + pos + 1, (active_nr - pos) * sizeof(struct cache_entry *));
 233         return 1;
 234 }
 235
 236 int remove_file_from_cache(const char *path)
 237 {
 238         int pos = cache_name_pos(path, strlen(path));
 239         if (pos < 0)
 240                 pos = -pos-1;
 241         while (pos < active_nr && !strcmp(active_cache[pos]->name, path))
 242                 remove_cache_entry_at(pos);
 243         return 0;
 244 }
 245
 246 int ce_same_name(struct cache_entry *a, struct cache_entry *b)
 247 {
 248         int len = ce_namelen(a);
 249         return ce_namelen(b) == len && !memcmp(a->name, b->name, len);
 250 }
 251
 252 int ce_path_match(const struct cache_entry *ce, const char **pathspec)
 253 {
 254         const char *match, *name;
 255         int len;
 256
 257         if (!pathspec)
 258                 return 1;
 259
 260         len = ce_namelen(ce);
 261         name = ce->name;
 262         while ((match = *pathspec++) != NULL) {
 263                 int matchlen = strlen(match);
 264                 if (matchlen > len)
 265                         continue;
 266                 if (memcmp(name, match, matchlen))
 267                         continue;
 268                 if (matchlen && name[matchlen-1] == '/')
 269                         return 1;
 270                 if (name[matchlen] == '/' || !name[matchlen])
 271                         return 1;
 272                 if (!matchlen)
 273                         return 1;
 274         }
 275         return 0;
 276 }
 277
 278 /*
 279  * Do we have another file that has the beginning components being a
 280  * proper superset of the name we're trying to add?
 281  */
 282 static int has_file_name(const struct cache_entry *ce, int pos, int ok_to_replace)
 283 {
 284         int retval = 0;
 285         int len = ce_namelen(ce);
 286         int stage = ce_stage(ce);
 287         const char *name = ce->name;
 288
 289         while (pos < active_nr) {
 290                 struct cache_entry *p = active_cache[pos++];
 291
 292                 if (len >= ce_namelen(p))
 293                         break;
 294                 if (memcmp(name, p->name, len))
 295                         break;
 296                 if (ce_stage(p) != stage)
 297                         continue;
 298                 if (p->name[len] != '/')
 299                         continue;
 300                 retval = -1;
 301                 if (!ok_to_replace)
 302                         break;
 303                 remove_cache_entry_at(--pos);
 304         }
 305         return retval;
 306 }
 307
 308 /*
 309  * Do we have another file with a pathname that is a proper
 310  * subset of the name we're trying to add?
 311  */
 312 static int has_dir_name(const struct cache_entry *ce, int pos, int ok_to_replace)
 313 {
 314         int retval = 0;
 315         int stage = ce_stage(ce);
 316         const char *name = ce->name;
 317         const char *slash = name + ce_namelen(ce);
 318
 319         for (;;) {
 320                 int len;
 321
 322                 for (;;) {
 323                         if (*--slash == '/')
 324                                 break;
 325                         if (slash <= ce->name)
 326                                 return retval;
 327                 }
 328                 len = slash - name;
 329
 330                 pos = cache_name_pos(name, ntohs(create_ce_flags(len, stage)));
 331                 if (pos >= 0) {
 332                         retval = -1;
 333                         if (ok_to_replace)
 334                                 break;
 335                         remove_cache_entry_at(pos);
 336                         continue;
 337                 }
 338
 339                 /*
 340                  * Trivial optimization: if we find an entry that
 341                  * already matches the sub-directory, then we know
 342                  * we're ok, and we can exit.
 343                  */
 344                 pos = -pos-1;
 345                 while (pos < active_nr) {
 346                         struct cache_entry *p = active_cache[pos];
 347                         if ((ce_namelen(p) <= len) ||
 348                             (p->name[len] != '/') ||
 349                             memcmp(p->name, name, len))
 350                                 break; /* not our subdirectory */
 351                         if (ce_stage(p) == stage)
 352                                 /* p is at the same stage as our entry, and
 353                                  * is a subdirectory of what we are looking
 354                                  * at, so we cannot have conflicts at our
 355                                  * level or anything shorter.
 356                                  */
 357                                 return retval;
 358                         pos++;
 359                 }
 360         }
 361         return retval;
 362 }
 363
 364 /* We may be in a situation where we already have path/file and path
 365  * is being added, or we already have path and path/file is being
 366  * added.  Either one would result in a nonsense tree that has path
 367  * twice when git-write-tree tries to write it out.  Prevent it.
 368  *
 369  * If ok-to-replace is specified, we remove the conflicting entries
 370  * from the cache so the caller should recompute the insert position.
 371  * When this happens, we return non-zero.
 372  */
 373 static int check_file_directory_conflict(const struct cache_entry *ce, int pos, int ok_to_replace)
 374 {
 375         /*
 376          * We check if the path is a sub-path of a subsequent pathname
 377          * first, since removing those will not change the position
 378          * in the array
 379          */
 380         int retval = has_file_name(ce, pos, ok_to_replace);
 381         /*
 382          * Then check if the path might have a clashing sub-directory
 383          * before it.
 384          */
 385         return retval + has_dir_name(ce, pos, ok_to_replace);
 386 }
 387
 388 int add_cache_entry(struct cache_entry *ce, int option)
 389 {
 390         int pos;
 391         int ok_to_add = option & ADD_CACHE_OK_TO_ADD;
 392         int ok_to_replace = option & ADD_CACHE_OK_TO_REPLACE;
 393         int skip_df_check = option & ADD_CACHE_SKIP_DFCHECK;
 394         pos = cache_name_pos(ce->name, ntohs(ce->ce_flags));
 395
 396         /* existing match? Just replace it */
 397         if (pos >= 0) {
 398                 active_cache_changed = 1;
 399                 active_cache[pos] = ce;
 400                 return 0;
 401         }
 402         pos = -pos-1;
 403
 404         /*
 405          * Inserting a merged entry ("stage 0") into the index
 406          * will always replace all non-merged entries..
 407          */
 408         if (pos < active_nr && ce_stage(ce) == 0) {
 409                 while (ce_same_name(active_cache[pos], ce)) {
 410                         ok_to_add = 1;
 411                         if (!remove_cache_entry_at(pos))
 412                                 break;
 413                 }
 414         }
 415
 416         if (!ok_to_add)
 417                 return -1;
 418
 419         if (!skip_df_check && check_file_directory_conflict(ce, pos, ok_to_replace)) {
 420                 if (!ok_to_replace)
 421                         return -1;
 422                 pos = cache_name_pos(ce->name, ntohs(ce->ce_flags));
 423                 pos = -pos-1;
 424         }
 425
 426         /* Make sure the array is big enough .. */
 427         if (active_nr == active_alloc) {
 428                 active_alloc = alloc_nr(active_alloc);
 429                 active_cache = xrealloc(active_cache, active_alloc * sizeof(struct cache_entry *));
 430         }
 431
 432         /* Add it in.. */
 433         active_nr++;
 434         if (active_nr > pos)
 435                 memmove(active_cache + pos + 1, active_cache + pos, (active_nr - pos - 1) * sizeof(ce));
 436         active_cache[pos] = ce;
 437         active_cache_changed = 1;
 438         return 0;
 439 }
 440
 441 static int verify_hdr(struct cache_header *hdr, unsigned long size)
 442 {
 443         SHA_CTX c;
 444         unsigned char sha1[20];
 445
 446         if (hdr->hdr_signature != htonl(CACHE_SIGNATURE))
 447                 return error("bad signature");
 448         if (hdr->hdr_version != htonl(2))
 449                 return error("bad index version");
 450         SHA1_Init(&c);
 451         SHA1_Update(&c, hdr, size - 20);
 452         SHA1_Final(sha1, &c);
 453         if (memcmp(sha1, (void *)hdr + size - 20, 20))
 454                 return error("bad index file sha1 signature");
 455         return 0;
 456 }
 457
 458 int read_cache(void)
 459 {
 460         int fd, i;
 461         struct stat st;
 462         unsigned long size, offset;
 463         void *map;
 464         struct cache_header *hdr;
 465
 466         errno = EBUSY;
 467         if (active_cache)
 468                 return active_nr;
 469
 470         errno = ENOENT;
 471         fd = open(get_index_file(), O_RDONLY);
 472         if (fd < 0) {
 473                 if (errno == ENOENT)
 474                         return 0;
 475                 die("index file open failed (%s)", strerror(errno));
 476         }
 477
 478         size = 0; // avoid gcc warning
 479         map = MAP_FAILED;
 480         if (!fstat(fd, &st)) {
 481                 size = st.st_size;
 482                 errno = EINVAL;
 483                 if (size >= sizeof(struct cache_header) + 20)
 484                         map = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
 485         }
 486         close(fd);
 487         if (map == MAP_FAILED)
 488                 die("index file mmap failed (%s)", strerror(errno));
 489
 490         hdr = map;
 491         if (verify_hdr(hdr, size) < 0)
 492                 goto unmap;
 493
 494         active_nr = ntohl(hdr->hdr_entries);
 495         active_alloc = alloc_nr(active_nr);
 496         active_cache = calloc(active_alloc, sizeof(struct cache_entry *));
 497
 498         offset = sizeof(*hdr);
 499         for (i = 0; i < active_nr; i++) {
 500                 struct cache_entry *ce = map + offset;
 501                 offset = offset + ce_size(ce);
 502                 active_cache[i] = ce;
 503         }
 504         return active_nr;
 505
 506 unmap:
 507         munmap(map, size);
 508         errno = EINVAL;
 509         die("index file corrupt");
 510 }
 511
 512 #define WRITE_BUFFER_SIZE 8192
 513 static unsigned char write_buffer[WRITE_BUFFER_SIZE];
 514 static unsigned long write_buffer_len;
 515
 516 static int ce_write(SHA_CTX *context, int fd, void *data, unsigned int len)
 517 {
 518         while (len) {
 519                 unsigned int buffered = write_buffer_len;
 520                 unsigned int partial = WRITE_BUFFER_SIZE - buffered;
 521                 if (partial > len)
 522                         partial = len;
 523                 memcpy(write_buffer + buffered, data, partial);
 524                 buffered += partial;
 525                 if (buffered == WRITE_BUFFER_SIZE) {
 526                         SHA1_Update(context, write_buffer, WRITE_BUFFER_SIZE);
 527                         if (write(fd, write_buffer, WRITE_BUFFER_SIZE) != WRITE_BUFFER_SIZE)
 528                                 return -1;
 529                         buffered = 0;
 530                 }
 531                 write_buffer_len = buffered;
 532                 len -= partial;
 533                 data += partial;
 534         }
 535         return 0;
 536 }
 537
 538 static int ce_flush(SHA_CTX *context, int fd)
 539 {
 540         unsigned int left = write_buffer_len;
 541
 542         if (left) {
 543                 write_buffer_len = 0;
 544                 SHA1_Update(context, write_buffer, left);
 545         }
 546
 547         /* Flush first if not enough space for SHA1 signature */
 548         if (left + 20 > WRITE_BUFFER_SIZE) {
 549                 if (write(fd, write_buffer, left) != left)
 550                         return -1;
 551                 left = 0;
 552         }
 553
 554         /* Append the SHA1 signature at the end */
 555         SHA1_Final(write_buffer + left, context);
 556         left += 20;
 557         if (write(fd, write_buffer, left) != left)
 558                 return -1;
 559         return 0;
 560 }
 561
 562 int write_cache(int newfd, struct cache_entry **cache, int entries)
 563 {
 564         SHA_CTX c;
 565         struct cache_header hdr;
 566         int i, removed;
 567
 568         for (i = removed = 0; i < entries; i++)
 569                 if (!cache[i]->ce_mode)
 570                         removed++;
 571
 572         hdr.hdr_signature = htonl(CACHE_SIGNATURE);
 573         hdr.hdr_version = htonl(2);
 574         hdr.hdr_entries = htonl(entries - removed);
 575
 576         SHA1_Init(&c);
 577         if (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0)
 578                 return -1;
 579
 580         for (i = 0; i < entries; i++) {
 581                 struct cache_entry *ce = cache[i];
 582                 if (!ce->ce_mode)
 583                         continue;
 584                 if (ce_write(&c, newfd, ce, ce_size(ce)) < 0)
 585                         return -1;
 586         }
 587         return ce_flush(&c, newfd);
 588 }