read-cache.c 13.7 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
#include "cache.h"

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 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);
}

32
int ce_match_stat(struct cache_entry *ce, struct stat *st)
33 34 35
{
	unsigned int changed = 0;

36 37 38
	switch (ntohl(ce->ce_mode) & S_IFMT) {
	case S_IFREG:
		changed |= !S_ISREG(st->st_mode) ? TYPE_CHANGED : 0;
39 40 41
		/* We consider only the owner x bit to be relevant for "mode changes" */
		if (0100 & (ntohl(ce->ce_mode) ^ st->st_mode))
			changed |= MODE_CHANGED;
42 43 44 45 46 47 48
		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));
	}
49
	if (ce->ce_mtime.sec != htonl(st->st_mtime))
50
		changed |= MTIME_CHANGED;
51 52 53
	if (ce->ce_ctime.sec != htonl(st->st_ctime))
		changed |= CTIME_CHANGED;

54
#ifdef USE_NSEC
55 56 57 58 59
	/*
	 * 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.
	 */
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 65 66 67
#endif	

	if (ce->ce_uid != htonl(st->st_uid) ||
	    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 73 74 75 76 77 78 79 80 81

#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

82
	if (ce->ce_size != htonl(st->st_size))
83 84 85 86
		changed |= DATA_CHANGED;
	return changed;
}

87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
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;
}

int ce_modified(struct cache_entry *ce, struct stat *st)
{
	int changed;
	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;

	switch (st->st_mode & S_IFMT) {
	case S_IFREG:
		if (ce_compare_data(ce, st))
			return changed | DATA_CHANGED;
		break;
	case S_IFLNK:
		if (ce_compare_link(ce, st->st_size))
			return changed | DATA_CHANGED;
		break;
	default:
		return changed | TYPE_CHANGED;
	}
	return 0;
}

164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182
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;
}

183
int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)
184
{
185 186
	int len1 = flags1 & CE_NAMEMASK;
	int len2 = flags2 & CE_NAMEMASK;
187 188 189 190 191 192 193 194 195 196
	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;
197 198 199 200
	if (flags1 < flags2)
		return -1;
	if (flags1 > flags2)
		return 1;
201 202 203 204 205 206 207 208 209 210 211 212
	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];
213
		int cmp = cache_name_compare(name, namelen, ce->name, ntohs(ce->ce_flags));
214
		if (!cmp)
215
			return next;
216 217 218 219 220 221
		if (cmp < 0) {
			last = next;
			continue;
		}
		first = next+1;
	}
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 230 231 232 233 234 235
	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
236
int remove_file_from_cache(const char *path)
237 238
{
	int pos = cache_name_pos(path, strlen(path));
239 240 241
	if (pos < 0)
		pos = -pos-1;
	while (pos < active_nr && !strcmp(active_cache[pos]->name, path))
242
		remove_cache_entry_at(pos);
243 244 245
	return 0;
}

246
int ce_same_name(struct cache_entry *a, struct cache_entry *b)
247 248 249 250 251
{
	int len = ce_namelen(a);
	return ce_namelen(b) == len && !memcmp(a->name, b->name, len);
}

252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271
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;
272 273
		if (!matchlen)
			return 1;
274 275 276 277
	}
	return 0;
}

278 279 280
/*
 * Do we have another file that has the beginning components being a
 * 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 285
	int retval = 0;
	int len = ce_namelen(ce);
286
	int stage = ce_stage(ce);
287
	const char *name = ce->name;
288

289 290
	while (pos < active_nr) {
		struct cache_entry *p = active_cache[pos++];
291

292
		if (len >= ce_namelen(p))
293
			break;
294 295
		if (memcmp(name, p->name, len))
			break;
296 297
		if (ce_stage(p) != stage)
			continue;
298 299 300 301 302 303
		if (p->name[len] != '/')
			continue;
		retval = -1;
		if (!ok_to_replace)
			break;
		remove_cache_entry_at(--pos);
304
	}
305 306
	return retval;
}
307

308 309 310 311 312 313 314
/*
 * 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;
315
	int stage = ce_stage(ce);
316 317
	const char *name = ce->name;
	const char *slash = name + ce_namelen(ce);
318

319 320
	for (;;) {
		int len;
321

322 323 324 325 326 327 328
		for (;;) {
			if (*--slash == '/')
				break;
			if (slash <= ce->name)
				return retval;
		}
		len = slash - name;
329

330
		pos = cache_name_pos(name, ntohs(create_ce_flags(len, stage)));
331 332 333 334
		if (pos >= 0) {
			retval = -1;
			if (ok_to_replace)
				break;
335
			remove_cache_entry_at(pos);
336 337 338 339 340 341
			continue;
		}

		/*
		 * Trivial optimization: if we find an entry that
		 * 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 348 349 350 351 352 353 354 355 356 357 358
			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++;
359
		}
360
	}
361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385
	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);
386 387
}

388
int add_cache_entry(struct cache_entry *ce, int option)
389 390
{
	int pos;
391 392
	int ok_to_add = option & ADD_CACHE_OK_TO_ADD;
	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 401
		return 0;
	}
402
	pos = -pos-1;
403

404 405 406 407 408
	/*
	 * Inserting a merged entry ("stage 0") into the index
	 * will always replace all non-merged entries..
	 */
	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 413 414 415
				break;
		}
	}

416 417 418
	if (!ok_to_add)
		return -1;

419
	if (!skip_df_check && check_file_directory_conflict(ce, pos, ok_to_replace)) {
420 421
		if (!ok_to_replace)
			return -1;
422
		pos = cache_name_pos(ce->name, ntohs(ce->ce_flags));
423 424
		pos = -pos-1;
	}
425

426 427 428
	/* Make sure the array is big enough .. */
	if (active_nr == active_alloc) {
		active_alloc = alloc_nr(active_alloc);
429
		active_cache = xrealloc(active_cache, active_alloc * sizeof(struct cache_entry *));
430 431 432 433 434 435 436
	}

	/* 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;
437
	active_cache_changed = 1;
438 439 440
	return 0;
}

441 442 443 444 445
static int verify_hdr(struct cache_header *hdr, unsigned long size)
{
	SHA_CTX c;
	unsigned char sha1[20];

446
	if (hdr->hdr_signature != htonl(CACHE_SIGNATURE))
447
		return error("bad signature");
448 449
	if (hdr->hdr_version != htonl(2))
		return error("bad index version");
450
	SHA1_Init(&c);
451
	SHA1_Update(&c, hdr, size - 20);
452
	SHA1_Final(sha1, &c);
453 454
	if (memcmp(sha1, (void *)hdr + size - 20, 20))
		return error("bad index file sha1 signature");
455 456 457 458 459 460 461 462 463 464 465 466 467
	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)
468 469
		return active_nr;

470
	errno = ENOENT;
471
	fd = open(get_index_file(), O_RDONLY);
472 473 474 475 476
	if (fd < 0) {
		if (errno == ENOENT)
			return 0;
		die("index file open failed (%s)", strerror(errno));
	}
477

478
	size = 0; // avoid gcc warning
Pavel Roskin's avatar
Pavel Roskin committed
479
	map = MAP_FAILED;
480 481 482
	if (!fstat(fd, &st)) {
		size = st.st_size;
		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);
Pavel Roskin's avatar
Pavel Roskin committed
487
	if (map == MAP_FAILED)
488
		die("index file mmap failed (%s)", strerror(errno));
489 490 491 492 493

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

494
	active_nr = ntohl(hdr->hdr_entries);
495 496 497 498
	active_alloc = alloc_nr(active_nr);
	active_cache = calloc(active_alloc, sizeof(struct cache_entry *));

	offset = sizeof(*hdr);
499
	for (i = 0; i < active_nr; i++) {
500 501 502 503 504 505 506 507 508
		struct cache_entry *ce = map + offset;
		offset = offset + ce_size(ce);
		active_cache[i] = ce;
	}
	return active_nr;

unmap:
	munmap(map, size);
	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 515
static unsigned long write_buffer_len;

516
static int ce_write(SHA_CTX *context, int fd, void *data, unsigned int len)
517 518 519 520 521 522 523 524 525
{
	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) {
526
			SHA1_Update(context, write_buffer, WRITE_BUFFER_SIZE);
527 528 529 530 531 532 533 534 535 536 537
			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;
}

538
static int ce_flush(SHA_CTX *context, int fd)
539 540
{
	unsigned int left = write_buffer_len;
541

542 543
	if (left) {
		write_buffer_len = 0;
544
		SHA1_Update(context, write_buffer, left);
545
	}
546

547 548 549 550 551 552 553
	/* 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;
	}

554 555 556 557 558
	/* Append the SHA1 signature at the end */
	SHA1_Final(write_buffer + left, context);
	left += 20;
	if (write(fd, write_buffer, left) != left)
		return -1;
559 560 561
	return 0;
}

562 563 564 565
int write_cache(int newfd, struct cache_entry **cache, int entries)
{
	SHA_CTX c;
	struct cache_header hdr;
566 567 568 569 570
	int i, removed;

	for (i = removed = 0; i < entries; i++)
		if (!cache[i]->ce_mode)
			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 579 580 581
		return -1;

	for (i = 0; i < entries; i++) {
		struct cache_entry *ce = cache[i];
582 583
		if (!ce->ce_mode)
			continue;
584
		if (ce_write(&c, newfd, ce, ce_size(ce)) < 0)
585 586
			return -1;
	}
587
	return ce_flush(&c, newfd);
588
}