read-cache.c 14.8 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5
/*
 * GIT - The information manager from hell
 *
 * Copyright (C) Linus Torvalds, 2005
 */
6 7 8
#include "cache.h"

struct cache_entry **active_cache = NULL;
Junio C Hamano's avatar
Junio C Hamano committed
9
static time_t index_file_timestamp;
10
unsigned int active_nr = 0, active_alloc = 0, active_cache_changed = 0;
11

12 13 14 15 16 17 18 19 20
/*
 * This only updates the "non-critical" parts of the directory
 * cache, ie the parts that aren't tracked by GIT, and only used
 * to validate the cache.
 */
void fill_stat_cache_info(struct cache_entry *ce, struct stat *st)
{
	ce->ce_ctime.sec = htonl(st->st_ctime);
	ce->ce_mtime.sec = htonl(st->st_mtime);
21
#ifdef USE_NSEC
22 23 24 25 26 27 28 29 30 31
	ce->ce_ctime.nsec = htonl(st->st_ctim.tv_nsec);
	ce->ce_mtime.nsec = htonl(st->st_mtim.tv_nsec);
#endif
	ce->ce_dev = htonl(st->st_dev);
	ce->ce_ino = htonl(st->st_ino);
	ce->ce_uid = htonl(st->st_uid);
	ce->ce_gid = htonl(st->st_gid);
	ce->ce_size = htonl(st->st_size);
}

Junio C Hamano's avatar
Junio C Hamano committed
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
static int ce_compare_data(struct cache_entry *ce, struct stat *st)
{
	int match = -1;
	int fd = open(ce->name, O_RDONLY);

	if (fd >= 0) {
		unsigned char sha1[20];
		if (!index_fd(sha1, fd, st, 0, NULL))
			match = memcmp(sha1, ce->sha1, 20);
		close(fd);
	}
	return match;
}

static int ce_compare_link(struct cache_entry *ce, unsigned long expected_size)
{
	int match = -1;
	char *target;
	void *buffer;
	unsigned long size;
	char type[10];
	int len;

	target = xmalloc(expected_size);
	len = readlink(ce->name, target, expected_size);
	if (len != expected_size) {
		free(target);
		return -1;
	}
	buffer = read_sha1_file(ce->sha1, type, &size);
	if (!buffer) {
		free(target);
		return -1;
	}
	if (size == expected_size)
		match = memcmp(buffer, target, size);
	free(buffer);
	free(target);
	return match;
}

static int ce_modified_check_fs(struct cache_entry *ce, struct stat *st)
{
	switch (st->st_mode & S_IFMT) {
	case S_IFREG:
		if (ce_compare_data(ce, st))
			return DATA_CHANGED;
		break;
	case S_IFLNK:
		if (ce_compare_link(ce, st->st_size))
			return DATA_CHANGED;
		break;
	default:
		return TYPE_CHANGED;
	}
	return 0;
}

90
int ce_match_stat(struct cache_entry *ce, struct stat *st)
91 92 93
{
	unsigned int changed = 0;

94 95 96
	switch (ntohl(ce->ce_mode) & S_IFMT) {
	case S_IFREG:
		changed |= !S_ISREG(st->st_mode) ? TYPE_CHANGED : 0;
Junio C Hamano's avatar
Junio C Hamano committed
97 98 99 100 101
		/* We consider only the owner x bit to be relevant for
		 * "mode changes"
		 */
		if (trust_executable_bit &&
		    (0100 & (ntohl(ce->ce_mode) ^ st->st_mode)))
102
			changed |= MODE_CHANGED;
103 104 105 106 107 108 109
		break;
	case S_IFLNK:
		changed |= !S_ISLNK(st->st_mode) ? TYPE_CHANGED : 0;
		break;
	default:
		die("internal error: ce_mode is %o", ntohl(ce->ce_mode));
	}
110
	if (ce->ce_mtime.sec != htonl(st->st_mtime))
111
		changed |= MTIME_CHANGED;
112 113 114
	if (ce->ce_ctime.sec != htonl(st->st_ctime))
		changed |= CTIME_CHANGED;

115
#ifdef USE_NSEC
116 117 118 119 120
	/*
	 * nsec seems unreliable - not all filesystems support it, so
	 * as long as it is in the inode cache you get right nsec
	 * but after it gets flushed, you get zero nsec.
	 */
121
	if (ce->ce_mtime.nsec != htonl(st->st_mtim.tv_nsec))
122
		changed |= MTIME_CHANGED;
123
	if (ce->ce_ctime.nsec != htonl(st->st_ctim.tv_nsec))
124
		changed |= CTIME_CHANGED;
125 126 127 128
#endif	

	if (ce->ce_uid != htonl(st->st_uid) ||
	    ce->ce_gid != htonl(st->st_gid))
129
		changed |= OWNER_CHANGED;
130
	if (ce->ce_ino != htonl(st->st_ino))
131
		changed |= INODE_CHANGED;
132 133 134 135 136 137 138 139 140 141 142

#ifdef USE_STDEV
	/*
	 * st_dev breaks on network filesystems where different
	 * clients will have different views of what "device"
	 * the filesystem is on
	 */
	if (ce->ce_dev != htonl(st->st_dev))
		changed |= INODE_CHANGED;
#endif

143
	if (ce->ce_size != htonl(st->st_size))
144
		changed |= DATA_CHANGED;
145

Junio C Hamano's avatar
Junio C Hamano committed
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
	/*
	 * Within 1 second of this sequence:
	 * 	echo xyzzy >file && git-update-index --add file
	 * running this command:
	 * 	echo frotz >file
	 * would give a falsely clean cache entry.  The mtime and
	 * length match the cache, and other stat fields do not change.
	 *
	 * We could detect this at update-index time (the cache entry
	 * being registered/updated records the same time as "now")
	 * and delay the return from git-update-index, but that would
	 * effectively mean we can make at most one commit per second,
	 * which is not acceptable.  Instead, we check cache entries
	 * whose mtime are the same as the index file timestamp more
	 * careful than others.
	 */
	if (!changed &&
	    index_file_timestamp &&
	    index_file_timestamp <= ntohl(ce->ce_mtime.sec))
		changed |= ce_modified_check_fs(ce, st);
166

Junio C Hamano's avatar
Junio C Hamano committed
167
	return changed;
168 169 170 171
}

int ce_modified(struct cache_entry *ce, struct stat *st)
{
Junio C Hamano's avatar
Junio C Hamano committed
172
	int changed, changed_fs;
173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
	changed = ce_match_stat(ce, st);
	if (!changed)
		return 0;
	/*
	 * If the mode or type has changed, there's no point in trying
	 * to refresh the entry - it's not going to match
	 */
	if (changed & (MODE_CHANGED | TYPE_CHANGED))
		return changed;

	/* Immediately after read-tree or update-index --cacheinfo,
	 * the length field is zero.  For other cases the ce_size
	 * should match the SHA1 recorded in the index entry.
	 */
	if ((changed & DATA_CHANGED) && ce->ce_size != htonl(0))
		return changed;

Junio C Hamano's avatar
Junio C Hamano committed
190 191 192
	changed_fs = ce_modified_check_fs(ce, st);
	if (changed_fs)
		return changed | changed_fs;
193 194 195
	return 0;
}

196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214
int base_name_compare(const char *name1, int len1, int mode1,
		      const char *name2, int len2, int mode2)
{
	unsigned char c1, c2;
	int len = len1 < len2 ? len1 : len2;
	int cmp;

	cmp = memcmp(name1, name2, len);
	if (cmp)
		return cmp;
	c1 = name1[len];
	c2 = name2[len];
	if (!c1 && S_ISDIR(mode1))
		c1 = '/';
	if (!c2 && S_ISDIR(mode2))
		c2 = '/';
	return (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0;
}

215
int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)
216
{
217 218
	int len1 = flags1 & CE_NAMEMASK;
	int len2 = flags2 & CE_NAMEMASK;
219 220 221 222 223 224 225 226 227 228
	int len = len1 < len2 ? len1 : len2;
	int cmp;

	cmp = memcmp(name1, name2, len);
	if (cmp)
		return cmp;
	if (len1 < len2)
		return -1;
	if (len1 > len2)
		return 1;
229 230 231 232
	if (flags1 < flags2)
		return -1;
	if (flags1 > flags2)
		return 1;
233 234 235 236 237 238 239 240 241 242 243 244
	return 0;
}

int cache_name_pos(const char *name, int namelen)
{
	int first, last;

	first = 0;
	last = active_nr;
	while (last > first) {
		int next = (last + first) >> 1;
		struct cache_entry *ce = active_cache[next];
245
		int cmp = cache_name_compare(name, namelen, ce->name, ntohs(ce->ce_flags));
246
		if (!cmp)
247
			return next;
248 249 250 251 252 253
		if (cmp < 0) {
			last = next;
			continue;
		}
		first = next+1;
	}
254
	return -first-1;
255 256
}

257
/* Remove entry, return true if there are more entries to go.. */
258
int remove_cache_entry_at(int pos)
259
{
260
	active_cache_changed = 1;
261 262 263 264 265 266 267
	active_nr--;
	if (pos >= active_nr)
		return 0;
	memmove(active_cache + pos, active_cache + pos + 1, (active_nr - pos) * sizeof(struct cache_entry *));
	return 1;
}

Junio C Hamano's avatar
Junio C Hamano committed
268
int remove_file_from_cache(const char *path)
269 270
{
	int pos = cache_name_pos(path, strlen(path));
271 272 273
	if (pos < 0)
		pos = -pos-1;
	while (pos < active_nr && !strcmp(active_cache[pos]->name, path))
274
		remove_cache_entry_at(pos);
275 276 277
	return 0;
}

278
int ce_same_name(struct cache_entry *a, struct cache_entry *b)
279 280 281 282 283
{
	int len = ce_namelen(a);
	return ce_namelen(b) == len && !memcmp(a->name, b->name, len);
}

284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303
int ce_path_match(const struct cache_entry *ce, const char **pathspec)
{
	const char *match, *name;
	int len;

	if (!pathspec)
		return 1;

	len = ce_namelen(ce);
	name = ce->name;
	while ((match = *pathspec++) != NULL) {
		int matchlen = strlen(match);
		if (matchlen > len)
			continue;
		if (memcmp(name, match, matchlen))
			continue;
		if (matchlen && name[matchlen-1] == '/')
			return 1;
		if (name[matchlen] == '/' || !name[matchlen])
			return 1;
304 305
		if (!matchlen)
			return 1;
306 307 308 309
	}
	return 0;
}

310 311 312
/*
 * Do we have another file that has the beginning components being a
 * proper superset of the name we're trying to add?
313
 */
314
static int has_file_name(const struct cache_entry *ce, int pos, int ok_to_replace)
315
{
316 317
	int retval = 0;
	int len = ce_namelen(ce);
318
	int stage = ce_stage(ce);
319
	const char *name = ce->name;
320

321 322
	while (pos < active_nr) {
		struct cache_entry *p = active_cache[pos++];
323

324
		if (len >= ce_namelen(p))
325
			break;
326 327
		if (memcmp(name, p->name, len))
			break;
328 329
		if (ce_stage(p) != stage)
			continue;
330 331 332 333 334 335
		if (p->name[len] != '/')
			continue;
		retval = -1;
		if (!ok_to_replace)
			break;
		remove_cache_entry_at(--pos);
336
	}
337 338
	return retval;
}
339

340 341 342 343 344 345 346
/*
 * Do we have another file with a pathname that is a proper
 * subset of the name we're trying to add?
 */
static int has_dir_name(const struct cache_entry *ce, int pos, int ok_to_replace)
{
	int retval = 0;
347
	int stage = ce_stage(ce);
348 349
	const char *name = ce->name;
	const char *slash = name + ce_namelen(ce);
350

351 352
	for (;;) {
		int len;
353

354 355 356 357 358 359 360
		for (;;) {
			if (*--slash == '/')
				break;
			if (slash <= ce->name)
				return retval;
		}
		len = slash - name;
361

362
		pos = cache_name_pos(name, ntohs(create_ce_flags(len, stage)));
363 364 365 366
		if (pos >= 0) {
			retval = -1;
			if (ok_to_replace)
				break;
367
			remove_cache_entry_at(pos);
368 369 370 371 372 373
			continue;
		}

		/*
		 * Trivial optimization: if we find an entry that
		 * already matches the sub-directory, then we know
374
		 * we're ok, and we can exit.
375 376
		 */
		pos = -pos-1;
377
		while (pos < active_nr) {
378
			struct cache_entry *p = active_cache[pos];
379 380 381 382 383 384 385 386 387 388 389 390
			if ((ce_namelen(p) <= len) ||
			    (p->name[len] != '/') ||
			    memcmp(p->name, name, len))
				break; /* not our subdirectory */
			if (ce_stage(p) == stage)
				/* p is at the same stage as our entry, and
				 * is a subdirectory of what we are looking
				 * at, so we cannot have conflicts at our
				 * level or anything shorter.
				 */
				return retval;
			pos++;
391
		}
392
	}
393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417
	return retval;
}

/* We may be in a situation where we already have path/file and path
 * is being added, or we already have path and path/file is being
 * added.  Either one would result in a nonsense tree that has path
 * twice when git-write-tree tries to write it out.  Prevent it.
 * 
 * If ok-to-replace is specified, we remove the conflicting entries
 * from the cache so the caller should recompute the insert position.
 * When this happens, we return non-zero.
 */
static int check_file_directory_conflict(const struct cache_entry *ce, int pos, int ok_to_replace)
{
	/*
	 * We check if the path is a sub-path of a subsequent pathname
	 * first, since removing those will not change the position
	 * in the array
	 */
	int retval = has_file_name(ce, pos, ok_to_replace);
	/*
	 * Then check if the path might have a clashing sub-directory
	 * before it.
	 */
	return retval + has_dir_name(ce, pos, ok_to_replace);
418 419
}

420
int add_cache_entry(struct cache_entry *ce, int option)
421 422
{
	int pos;
423 424
	int ok_to_add = option & ADD_CACHE_OK_TO_ADD;
	int ok_to_replace = option & ADD_CACHE_OK_TO_REPLACE;
425
	int skip_df_check = option & ADD_CACHE_SKIP_DFCHECK;
426
	pos = cache_name_pos(ce->name, ntohs(ce->ce_flags));
427

Junio C Hamano's avatar
Junio C Hamano committed
428
	/* existing match? Just replace it. */
429
	if (pos >= 0) {
430
		active_cache_changed = 1;
431
		active_cache[pos] = ce;
432 433
		return 0;
	}
434
	pos = -pos-1;
435

436 437 438 439 440
	/*
	 * Inserting a merged entry ("stage 0") into the index
	 * will always replace all non-merged entries..
	 */
	if (pos < active_nr && ce_stage(ce) == 0) {
441
		while (ce_same_name(active_cache[pos], ce)) {
442
			ok_to_add = 1;
443
			if (!remove_cache_entry_at(pos))
444 445 446 447
				break;
		}
	}

448 449 450
	if (!ok_to_add)
		return -1;

Junio C Hamano's avatar
Junio C Hamano committed
451 452
	if (!skip_df_check &&
	    check_file_directory_conflict(ce, pos, ok_to_replace)) {
453 454
		if (!ok_to_replace)
			return -1;
455
		pos = cache_name_pos(ce->name, ntohs(ce->ce_flags));
456 457
		pos = -pos-1;
	}
458

459 460 461
	/* Make sure the array is big enough .. */
	if (active_nr == active_alloc) {
		active_alloc = alloc_nr(active_alloc);
462
		active_cache = xrealloc(active_cache, active_alloc * sizeof(struct cache_entry *));
463 464 465 466 467 468 469
	}

	/* Add it in.. */
	active_nr++;
	if (active_nr > pos)
		memmove(active_cache + pos + 1, active_cache + pos, (active_nr - pos - 1) * sizeof(ce));
	active_cache[pos] = ce;
470
	active_cache_changed = 1;
471 472 473
	return 0;
}

474 475 476 477 478
static int verify_hdr(struct cache_header *hdr, unsigned long size)
{
	SHA_CTX c;
	unsigned char sha1[20];

479
	if (hdr->hdr_signature != htonl(CACHE_SIGNATURE))
480
		return error("bad signature");
481 482
	if (hdr->hdr_version != htonl(2))
		return error("bad index version");
483
	SHA1_Init(&c);
484
	SHA1_Update(&c, hdr, size - 20);
485
	SHA1_Final(sha1, &c);
486 487
	if (memcmp(sha1, (void *)hdr + size - 20, 20))
		return error("bad index file sha1 signature");
488 489 490 491 492 493 494 495 496 497 498 499 500
	return 0;
}

int read_cache(void)
{
	int fd, i;
	struct stat st;
	unsigned long size, offset;
	void *map;
	struct cache_header *hdr;

	errno = EBUSY;
	if (active_cache)
501 502
		return active_nr;

503
	errno = ENOENT;
Junio C Hamano's avatar
Junio C Hamano committed
504
	index_file_timestamp = 0;
505
	fd = open(get_index_file(), O_RDONLY);
506 507 508 509 510
	if (fd < 0) {
		if (errno == ENOENT)
			return 0;
		die("index file open failed (%s)", strerror(errno));
	}
511

512
	size = 0; // avoid gcc warning
Pavel Roskin's avatar
Pavel Roskin committed
513
	map = MAP_FAILED;
514 515 516
	if (!fstat(fd, &st)) {
		size = st.st_size;
		errno = EINVAL;
517
		if (size >= sizeof(struct cache_header) + 20)
518
			map = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
519 520
	}
	close(fd);
Pavel Roskin's avatar
Pavel Roskin committed
521
	if (map == MAP_FAILED)
522
		die("index file mmap failed (%s)", strerror(errno));
523 524 525 526 527

	hdr = map;
	if (verify_hdr(hdr, size) < 0)
		goto unmap;

528
	active_nr = ntohl(hdr->hdr_entries);
529 530 531 532
	active_alloc = alloc_nr(active_nr);
	active_cache = calloc(active_alloc, sizeof(struct cache_entry *));

	offset = sizeof(*hdr);
533
	for (i = 0; i < active_nr; i++) {
534 535 536 537
		struct cache_entry *ce = map + offset;
		offset = offset + ce_size(ce);
		active_cache[i] = ce;
	}
Junio C Hamano's avatar
Junio C Hamano committed
538
	index_file_timestamp = st.st_mtime;
539 540 541 542 543
	return active_nr;

unmap:
	munmap(map, size);
	errno = EINVAL;
544
	die("index file corrupt");
545 546
}

547
#define WRITE_BUFFER_SIZE 8192
548
static unsigned char write_buffer[WRITE_BUFFER_SIZE];
549 550
static unsigned long write_buffer_len;

551
static int ce_write(SHA_CTX *context, int fd, void *data, unsigned int len)
552 553 554 555 556 557 558 559 560
{
	while (len) {
		unsigned int buffered = write_buffer_len;
		unsigned int partial = WRITE_BUFFER_SIZE - buffered;
		if (partial > len)
			partial = len;
		memcpy(write_buffer + buffered, data, partial);
		buffered += partial;
		if (buffered == WRITE_BUFFER_SIZE) {
561
			SHA1_Update(context, write_buffer, WRITE_BUFFER_SIZE);
562 563 564 565 566 567 568 569 570 571 572
			if (write(fd, write_buffer, WRITE_BUFFER_SIZE) != WRITE_BUFFER_SIZE)
				return -1;
			buffered = 0;
		}
		write_buffer_len = buffered;
		len -= partial;
		data += partial;
 	}
 	return 0;
}

573
static int ce_flush(SHA_CTX *context, int fd)
574 575
{
	unsigned int left = write_buffer_len;
576

577 578
	if (left) {
		write_buffer_len = 0;
579
		SHA1_Update(context, write_buffer, left);
580
	}
581

582 583 584 585 586 587 588
	/* Flush first if not enough space for SHA1 signature */
	if (left + 20 > WRITE_BUFFER_SIZE) {
		if (write(fd, write_buffer, left) != left)
			return -1;
		left = 0;
	}

589 590 591 592 593
	/* Append the SHA1 signature at the end */
	SHA1_Final(write_buffer + left, context);
	left += 20;
	if (write(fd, write_buffer, left) != left)
		return -1;
594 595 596
	return 0;
}

597 598 599 600
int write_cache(int newfd, struct cache_entry **cache, int entries)
{
	SHA_CTX c;
	struct cache_header hdr;
601 602 603 604 605
	int i, removed;

	for (i = removed = 0; i < entries; i++)
		if (!cache[i]->ce_mode)
			removed++;
606

607
	hdr.hdr_signature = htonl(CACHE_SIGNATURE);
608
	hdr.hdr_version = htonl(2);
609
	hdr.hdr_entries = htonl(entries - removed);
610 611

	SHA1_Init(&c);
612
	if (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0)
613 614 615 616
		return -1;

	for (i = 0; i < entries; i++) {
		struct cache_entry *ce = cache[i];
617 618
		if (!ce->ce_mode)
			continue;
619
		if (ce_write(&c, newfd, ce, ce_size(ce)) < 0)
620 621
			return -1;
	}
622
	return ce_flush(&c, newfd);
623
}