read-cache.c 13.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;
9
unsigned int active_nr = 0, active_alloc = 0, active_cache_changed = 0;
10

11 12 13 14 15 16 17 18 19
/*
 * 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);
20
#ifdef USE_NSEC
21 22 23 24 25 26 27 28 29 30
	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);
}

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

35 36 37
	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
38 39 40 41 42
		/* 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)))
43
			changed |= MODE_CHANGED;
44 45 46 47 48 49 50
		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));
	}
51
	if (ce->ce_mtime.sec != htonl(st->st_mtime))
52
		changed |= MTIME_CHANGED;
53 54 55
	if (ce->ce_ctime.sec != htonl(st->st_ctime))
		changed |= CTIME_CHANGED;

56
#ifdef USE_NSEC
57 58 59 60 61
	/*
	 * 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.
	 */
62
	if (ce->ce_mtime.nsec != htonl(st->st_mtim.tv_nsec))
63
		changed |= MTIME_CHANGED;
64
	if (ce->ce_ctime.nsec != htonl(st->st_ctim.tv_nsec))
65
		changed |= CTIME_CHANGED;
66 67 68 69
#endif	

	if (ce->ce_uid != htonl(st->st_uid) ||
	    ce->ce_gid != htonl(st->st_gid))
70
		changed |= OWNER_CHANGED;
71
	if (ce->ce_ino != htonl(st->st_ino))
72
		changed |= INODE_CHANGED;
73 74 75 76 77 78 79 80 81 82 83

#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

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

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 164 165
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;
}

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

185
int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)
186
{
187 188
	int len1 = flags1 & CE_NAMEMASK;
	int len2 = flags2 & CE_NAMEMASK;
189 190 191 192 193 194 195 196 197 198
	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;
199 200 201 202
	if (flags1 < flags2)
		return -1;
	if (flags1 > flags2)
		return 1;
203 204 205 206 207 208 209 210 211 212 213 214
	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];
215
		int cmp = cache_name_compare(name, namelen, ce->name, ntohs(ce->ce_flags));
216
		if (!cmp)
217
			return next;
218 219 220 221 222 223
		if (cmp < 0) {
			last = next;
			continue;
		}
		first = next+1;
	}
224
	return -first-1;
225 226
}

227
/* Remove entry, return true if there are more entries to go.. */
228
int remove_cache_entry_at(int pos)
229
{
230
	active_cache_changed = 1;
231 232 233 234 235 236 237
	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
238
int remove_file_from_cache(const char *path)
239 240
{
	int pos = cache_name_pos(path, strlen(path));
241 242 243
	if (pos < 0)
		pos = -pos-1;
	while (pos < active_nr && !strcmp(active_cache[pos]->name, path))
244
		remove_cache_entry_at(pos);
245 246 247
	return 0;
}

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

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

280 281 282
/*
 * Do we have another file that has the beginning components being a
 * proper superset of the name we're trying to add?
283
 */
284
static int has_file_name(const struct cache_entry *ce, int pos, int ok_to_replace)
285
{
286 287
	int retval = 0;
	int len = ce_namelen(ce);
288
	int stage = ce_stage(ce);
289
	const char *name = ce->name;
290

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

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

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

321 322
	for (;;) {
		int len;
323

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

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

		/*
		 * Trivial optimization: if we find an entry that
		 * already matches the sub-directory, then we know
344
		 * we're ok, and we can exit.
345 346
		 */
		pos = -pos-1;
347
		while (pos < active_nr) {
348
			struct cache_entry *p = active_cache[pos];
349 350 351 352 353 354 355 356 357 358 359 360
			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++;
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 386 387
	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);
388 389
}

390
int add_cache_entry(struct cache_entry *ce, int option)
391 392
{
	int pos;
393 394
	int ok_to_add = option & ADD_CACHE_OK_TO_ADD;
	int ok_to_replace = option & ADD_CACHE_OK_TO_REPLACE;
395
	int skip_df_check = option & ADD_CACHE_SKIP_DFCHECK;
396
	pos = cache_name_pos(ce->name, ntohs(ce->ce_flags));
397

Junio C Hamano's avatar
Junio C Hamano committed
398
	/* existing match? Just replace it. */
399
	if (pos >= 0) {
400
		active_cache_changed = 1;
401
		active_cache[pos] = ce;
402 403
		return 0;
	}
404
	pos = -pos-1;
405

406 407 408 409 410
	/*
	 * Inserting a merged entry ("stage 0") into the index
	 * will always replace all non-merged entries..
	 */
	if (pos < active_nr && ce_stage(ce) == 0) {
411
		while (ce_same_name(active_cache[pos], ce)) {
412
			ok_to_add = 1;
413
			if (!remove_cache_entry_at(pos))
414 415 416 417
				break;
		}
	}

418 419 420
	if (!ok_to_add)
		return -1;

Junio C Hamano's avatar
Junio C Hamano committed
421 422
	if (!skip_df_check &&
	    check_file_directory_conflict(ce, pos, ok_to_replace)) {
423 424
		if (!ok_to_replace)
			return -1;
425
		pos = cache_name_pos(ce->name, ntohs(ce->ce_flags));
426 427
		pos = -pos-1;
	}
428

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

	/* 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;
440
	active_cache_changed = 1;
441 442 443
	return 0;
}

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

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

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

481
	size = 0; // avoid gcc warning
Pavel Roskin's avatar
Pavel Roskin committed
482
	map = MAP_FAILED;
483 484 485
	if (!fstat(fd, &st)) {
		size = st.st_size;
		errno = EINVAL;
486
		if (size >= sizeof(struct cache_header) + 20)
487
			map = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
488 489
	}
	close(fd);
Pavel Roskin's avatar
Pavel Roskin committed
490
	if (map == MAP_FAILED)
491
		die("index file mmap failed (%s)", strerror(errno));
492 493 494 495 496

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

497
	active_nr = ntohl(hdr->hdr_entries);
498 499 500 501
	active_alloc = alloc_nr(active_nr);
	active_cache = calloc(active_alloc, sizeof(struct cache_entry *));

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

unmap:
	munmap(map, size);
	errno = EINVAL;
512
	die("index file corrupt");
513 514
}

515
#define WRITE_BUFFER_SIZE 8192
516
static unsigned char write_buffer[WRITE_BUFFER_SIZE];
517 518
static unsigned long write_buffer_len;

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

541
static int ce_flush(SHA_CTX *context, int fd)
542 543
{
	unsigned int left = write_buffer_len;
544

545 546
	if (left) {
		write_buffer_len = 0;
547
		SHA1_Update(context, write_buffer, left);
548
	}
549

550 551 552 553 554 555 556
	/* 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;
	}

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

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

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

575
	hdr.hdr_signature = htonl(CACHE_SIGNATURE);
576
	hdr.hdr_version = htonl(2);
577
	hdr.hdr_entries = htonl(entries - removed);
578 579

	SHA1_Init(&c);
580
	if (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0)
581 582 583 584
		return -1;

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