sha1_file.c 61.9 KB
Newer Older
1 2 3 4 5 6 7 8 9
/*
 * GIT - The information manager from hell
 *
 * Copyright (C) Linus Torvalds, 2005
 *
 * This handles basic git sha1 object files - packing, unpacking,
 * creation etc.
 */
#include "cache.h"
10
#include "delta.h"
11
#include "pack.h"
12 13 14 15
#include "blob.h"
#include "commit.h"
#include "tag.h"
#include "tree.h"
16
#include "refs.h"
17
#include "pack-revindex.h"
18
#include "sha1-lookup.h"
19

20 21 22 23 24 25 26 27
#ifndef O_NOATIME
#if defined(__linux__) && (defined(__i386__) || defined(__PPC__))
#define O_NOATIME 01000000
#else
#define O_NOATIME 0
#endif
#endif

28 29
#ifdef NO_C99_FORMAT
#define SZ_FMT "lu"
30
static unsigned long sz_fmt(size_t s) { return (unsigned long)s; }
31 32
#else
#define SZ_FMT "zu"
33
static size_t sz_fmt(size_t s) { return s; }
34 35
#endif

36
const unsigned char null_sha1[20];
J
Junio C Hamano 已提交
37

38 39
static unsigned int sha1_file_open_flag = O_NOATIME;

40
const signed char hexval_table[256] = {
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
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 00-07 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 08-0f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 10-17 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 18-1f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 20-27 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 28-2f */
	  0,  1,  2,  3,  4,  5,  6,  7,		/* 30-37 */
	  8,  9, -1, -1, -1, -1, -1, -1,		/* 38-3f */
	 -1, 10, 11, 12, 13, 14, 15, -1,		/* 40-47 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 48-4f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 50-57 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 58-5f */
	 -1, 10, 11, 12, 13, 14, 15, -1,		/* 60-67 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 68-67 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 70-77 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 78-7f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 80-87 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 88-8f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 90-97 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 98-9f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* a0-a7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* a8-af */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* b0-b7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* b8-bf */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* c0-c7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* c8-cf */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* d0-d7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* d8-df */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* e0-e7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* e8-ef */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* f0-f7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* f8-ff */
};
74 75 76 77 78 79 80 81 82 83 84 85 86 87

int get_sha1_hex(const char *hex, unsigned char *sha1)
{
	int i;
	for (i = 0; i < 20; i++) {
		unsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);
		if (val & ~0xff)
			return -1;
		*sha1++ = val;
		hex += 2;
	}
	return 0;
}

88 89 90
int safe_create_leading_directories(char *path)
{
	char *pos = path;
91 92
	struct stat st;

93
	if (is_absolute_path(path))
94
		pos++;
95 96 97 98 99 100

	while (pos) {
		pos = strchr(pos, '/');
		if (!pos)
			break;
		*pos = 0;
101 102 103
		if (!stat(path, &st)) {
			/* path exists */
			if (!S_ISDIR(st.st_mode)) {
104
				*pos = '/';
105
				return -3;
106
			}
107
		}
108 109 110 111
		else if (mkdir(path, 0777)) {
			*pos = '/';
			return -1;
		}
112 113 114 115
		else if (adjust_shared_perm(path)) {
			*pos = '/';
			return -2;
		}
116 117 118 119
		*pos++ = '/';
	}
	return 0;
}
120

121 122
char * sha1_to_hex(const unsigned char *sha1)
{
L
Linus Torvalds 已提交
123 124
	static int bufno;
	static char hexbuffer[4][50];
125
	static const char hex[] = "0123456789abcdef";
L
Linus Torvalds 已提交
126
	char *buffer = hexbuffer[3 & ++bufno], *buf = buffer;
127 128 129 130 131 132 133
	int i;

	for (i = 0; i < 20; i++) {
		unsigned int val = *sha1++;
		*buf++ = hex[val >> 4];
		*buf++ = hex[val & 0xf];
	}
134 135
	*buf = '\0';

136 137 138
	return buffer;
}

139 140 141 142 143 144 145 146 147 148 149 150
static void fill_sha1_path(char *pathbuf, const unsigned char *sha1)
{
	int i;
	for (i = 0; i < 20; i++) {
		static char hex[] = "0123456789abcdef";
		unsigned int val = sha1[i];
		char *pos = pathbuf + i*2 + (i > 0);
		*pos++ = hex[val >> 4];
		*pos = hex[val & 0xf];
	}
}

151 152
/*
 * NOTE! This returns a statically allocated buffer, so you have to be
153
 * careful about using it. Do an "xstrdup()" if you need to save the
154
 * filename.
155 156 157
 *
 * Also note that this returns the location for creating.  Reading
 * SHA1 file can happen from any alternate directory listed in the
J
Junio C Hamano 已提交
158
 * DB_ENVIRONMENT environment variable if it is not found in
159
 * the primary object database.
160 161 162 163 164 165
 */
char *sha1_file_name(const unsigned char *sha1)
{
	static char *name, *base;

	if (!base) {
J
Junio C Hamano 已提交
166
		const char *sha1_file_directory = get_object_directory();
167
		int len = strlen(sha1_file_directory);
168
		base = xmalloc(len + 60);
169 170 171 172 173 174
		memcpy(base, sha1_file_directory, len);
		memset(base+len, 0, 60);
		base[len] = '/';
		base[len+3] = '/';
		name = base + len + 1;
	}
175
	fill_sha1_path(name, sha1);
176 177 178
	return base;
}

179 180
static char *sha1_get_pack_name(const unsigned char *sha1,
				char **name, char **base)
181 182
{
	static const char hex[] = "0123456789abcdef";
183
	char *buf;
184 185
	int i;

186
	if (!*base) {
187 188
		const char *sha1_file_directory = get_object_directory();
		int len = strlen(sha1_file_directory);
189 190 191
		*base = xmalloc(len + 60);
		sprintf(*base, "%s/pack/pack-1234567890123456789012345678901234567890.pack", sha1_file_directory);
		*name = *base + len + 11;
192 193
	}

194
	buf = *name;
195 196 197 198 199 200

	for (i = 0; i < 20; i++) {
		unsigned int val = *sha1++;
		*buf++ = hex[val >> 4];
		*buf++ = hex[val & 0xf];
	}
J
Junio C Hamano 已提交
201

202
	return *base;
203 204
}

205
char *sha1_pack_name(const unsigned char *sha1)
206
{
207
	static char *name, *base;
208

209 210
	return sha1_get_pack_name(sha1, &name, &base);
}
211

212 213 214
char *sha1_pack_index_name(const unsigned char *sha1)
{
	static char *name, *base;
J
Junio C Hamano 已提交
215

216
	return sha1_get_pack_name(sha1, &name, &base);
217 218
}

219 220
struct alternate_object_database *alt_odb_list;
static struct alternate_object_database **alt_odb_tail;
221

M
Martin Waitz 已提交
222 223
static void read_info_alternates(const char * alternates, int depth);

J
Junio C Hamano 已提交
224 225
/*
 * Prepare alternate object database registry.
226 227 228 229 230
 *
 * The variable alt_odb_list points at the list of struct
 * alternate_object_database.  The elements on this list come from
 * non-empty elements from colon separated ALTERNATE_DB_ENVIRONMENT
 * environment variable, and $GIT_OBJECT_DIRECTORY/info/alternates,
231 232
 * whose contents is similar to that environment variable but can be
 * LF separated.  Its base points at a statically allocated buffer that
233 234 235 236 237
 * contains "/the/directory/corresponding/to/.git/objects/...", while
 * its name points just after the slash at the end of ".git/objects/"
 * in the example above, and has enough space to hold 40-byte hex
 * SHA1, an extra slash for the first level indirection, and the
 * terminating NUL.
J
Junio C Hamano 已提交
238
 */
M
Martin Waitz 已提交
239
static int link_alt_odb_entry(const char * entry, int len, const char * relative_base, int depth)
240
{
M
Martin Waitz 已提交
241
	struct stat st;
242
	const char *objdir = get_object_directory();
M
Martin Waitz 已提交
243 244 245 246 247
	struct alternate_object_database *ent;
	struct alternate_object_database *alt;
	/* 43 = 40-byte + 2 '/' + terminating NUL */
	int pfxlen = len;
	int entlen = pfxlen + 43;
248
	int base_len = -1;
249

250
	if (!is_absolute_path(entry) && relative_base) {
M
Martin Waitz 已提交
251 252 253 254 255 256 257 258
		/* Relative alt-odb */
		if (base_len < 0)
			base_len = strlen(relative_base) + 1;
		entlen += base_len;
		pfxlen += base_len;
	}
	ent = xmalloc(sizeof(*ent) + entlen);

259
	if (!is_absolute_path(entry) && relative_base) {
M
Martin Waitz 已提交
260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317
		memcpy(ent->base, relative_base, base_len - 1);
		ent->base[base_len - 1] = '/';
		memcpy(ent->base + base_len, entry, len);
	}
	else
		memcpy(ent->base, entry, pfxlen);

	ent->name = ent->base + pfxlen + 1;
	ent->base[pfxlen + 3] = '/';
	ent->base[pfxlen] = ent->base[entlen-1] = 0;

	/* Detect cases where alternate disappeared */
	if (stat(ent->base, &st) || !S_ISDIR(st.st_mode)) {
		error("object directory %s does not exist; "
		      "check .git/objects/info/alternates.",
		      ent->base);
		free(ent);
		return -1;
	}

	/* Prevent the common mistake of listing the same
	 * thing twice, or object directory itself.
	 */
	for (alt = alt_odb_list; alt; alt = alt->next) {
		if (!memcmp(ent->base, alt->base, pfxlen)) {
			free(ent);
			return -1;
		}
	}
	if (!memcmp(ent->base, objdir, pfxlen)) {
		free(ent);
		return -1;
	}

	/* add the alternate entry */
	*alt_odb_tail = ent;
	alt_odb_tail = &(ent->next);
	ent->next = NULL;

	/* recursively add alternates */
	read_info_alternates(ent->base, depth + 1);

	ent->base[pfxlen] = '/';

	return 0;
}

static void link_alt_odb_entries(const char *alt, const char *ep, int sep,
				 const char *relative_base, int depth)
{
	const char *cp, *last;

	if (depth > 5) {
		error("%s: ignoring alternate object stores, nesting too deep.",
				relative_base);
		return;
	}

318
	last = alt;
319 320 321 322 323 324 325 326
	while (last < ep) {
		cp = last;
		if (cp < ep && *cp == '#') {
			while (cp < ep && *cp != sep)
				cp++;
			last = cp + 1;
			continue;
		}
M
Martin Waitz 已提交
327 328
		while (cp < ep && *cp != sep)
			cp++;
329
		if (last != cp) {
330
			if (!is_absolute_path(last) && depth) {
M
Martin Waitz 已提交
331 332 333 334 335
				error("%s: ignoring relative alternate object store %s",
						relative_base, last);
			} else {
				link_alt_odb_entry(last, cp - last,
						relative_base, depth);
336
			}
337
		}
338
		while (cp < ep && *cp == sep)
339 340
			cp++;
		last = cp;
341
	}
342 343
}

M
Martin Waitz 已提交
344
static void read_info_alternates(const char * relative_base, int depth)
345
{
346
	char *map;
347
	size_t mapsz;
348
	struct stat st;
349 350 351 352 353
	const char alt_file_name[] = "info/alternates";
	/* Given that relative_base is no longer than PATH_MAX,
	   ensure that "path" has enough space to append "/", the
	   file name, "info/alternates", and a trailing NUL.  */
	char path[PATH_MAX + 1 + sizeof alt_file_name];
M
Martin Waitz 已提交
354
	int fd;
355

356
	sprintf(path, "%s/%s", relative_base, alt_file_name);
357 358 359 360 361
	fd = open(path, O_RDONLY);
	if (fd < 0)
		return;
	if (fstat(fd, &st) || (st.st_size == 0)) {
		close(fd);
362
		return;
363
	}
364 365
	mapsz = xsize_t(st.st_size);
	map = xmmap(NULL, mapsz, PROT_READ, MAP_PRIVATE, fd, 0);
366 367
	close(fd);

368
	link_alt_odb_entries(map, map + mapsz, '\n', relative_base, depth);
M
Martin Waitz 已提交
369

370
	munmap(map, mapsz);
371 372
}

373 374 375 376 377 378 379 380 381 382 383 384
void add_to_alternates_file(const char *reference)
{
	struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
	int fd = hold_lock_file_for_append(lock, git_path("objects/info/alternates"), 1);
	char *alt = mkpath("%s/objects\n", reference);
	write_or_die(fd, alt, strlen(alt));
	if (commit_lock_file(lock))
		die("could not close alternates file");
	if (alt_odb_tail)
		link_alt_odb_entries(alt, alt + strlen(alt), '\n', NULL, 0);
}

M
Martin Waitz 已提交
385 386
void prepare_alt_odb(void)
{
T
Timo Hirvonen 已提交
387
	const char *alt;
M
Martin Waitz 已提交
388

S
Shawn O. Pearce 已提交
389 390 391
	if (alt_odb_tail)
		return;

M
Martin Waitz 已提交
392 393 394 395 396 397 398 399 400
	alt = getenv(ALTERNATE_DB_ENVIRONMENT);
	if (!alt) alt = "";

	alt_odb_tail = &alt_odb_list;
	link_alt_odb_entries(alt, alt + strlen(alt), ':', NULL, 0);

	read_info_alternates(get_object_directory(), 0);
}

401 402 403
static char *find_sha1_file(const unsigned char *sha1, struct stat *st)
{
	char *name = sha1_file_name(sha1);
404
	struct alternate_object_database *alt;
405 406 407

	if (!stat(name, st))
		return name;
408
	prepare_alt_odb();
409 410
	for (alt = alt_odb_list; alt; alt = alt->next) {
		name = alt->name;
411
		fill_sha1_path(name, sha1);
412 413
		if (!stat(alt->base, st))
			return alt->base;
414 415 416 417
	}
	return NULL;
}

418
static unsigned int pack_used_ctr;
419 420 421 422
static unsigned int pack_mmap_calls;
static unsigned int peak_pack_open_windows;
static unsigned int pack_open_windows;
static size_t peak_pack_mapped;
423
static size_t pack_mapped;
424
struct packed_git *packed_git;
425

J
Junio C Hamano 已提交
426
void pack_report(void)
427 428
{
	fprintf(stderr,
429 430 431
		"pack_report: getpagesize()            = %10" SZ_FMT "\n"
		"pack_report: core.packedGitWindowSize = %10" SZ_FMT "\n"
		"pack_report: core.packedGitLimit      = %10" SZ_FMT "\n",
432 433 434
		sz_fmt(getpagesize()),
		sz_fmt(packed_git_window_size),
		sz_fmt(packed_git_limit));
435 436 437 438
	fprintf(stderr,
		"pack_report: pack_used_ctr            = %10u\n"
		"pack_report: pack_mmap_calls          = %10u\n"
		"pack_report: pack_open_windows        = %10u / %10u\n"
439 440
		"pack_report: pack_mapped              = "
			"%10" SZ_FMT " / %10" SZ_FMT "\n",
441 442 443
		pack_used_ctr,
		pack_mmap_calls,
		pack_open_windows, peak_pack_open_windows,
444
		sz_fmt(pack_mapped), sz_fmt(peak_pack_mapped));
445 446
}

447
static int check_packed_git_idx(const char *path,  struct packed_git *p)
448 449
{
	void *idx_map;
450
	struct pack_idx_header *hdr;
451
	size_t idx_size;
452
	uint32_t version, nr, i, *index;
453
	int fd = open(path, O_RDONLY);
454
	struct stat st;
455

456 457 458 459 460 461
	if (fd < 0)
		return -1;
	if (fstat(fd, &st)) {
		close(fd);
		return -1;
	}
462
	idx_size = xsize_t(st.st_size);
463 464 465 466
	if (idx_size < 4 * 256 + 20 + 20) {
		close(fd);
		return error("index file %s is too small", path);
	}
467
	idx_map = xmmap(NULL, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);
468 469
	close(fd);

470 471
	hdr = idx_map;
	if (hdr->idx_signature == htonl(PACK_IDX_SIGNATURE)) {
472 473 474 475 476 477 478 479 480 481
		version = ntohl(hdr->idx_version);
		if (version < 2 || version > 2) {
			munmap(idx_map, idx_size);
			return error("index file %s is version %d"
				     " and is not supported by this binary"
				     " (try upgrading GIT to a newer version)",
				     path, version);
		}
	} else
		version = 1;
482

483
	nr = 0;
484
	index = idx_map;
485 486
	if (version > 1)
		index += 2;  /* skip index header */
487
	for (i = 0; i < 256; i++) {
488
		uint32_t n = ntohl(index[i]);
489 490
		if (n < nr) {
			munmap(idx_map, idx_size);
491
			return error("non-monotonic index %s", path);
492
		}
493 494 495
		nr = n;
	}

496 497 498 499 500 501 502 503 504 505
	if (version == 1) {
		/*
		 * Total size:
		 *  - 256 index entries 4 bytes each
		 *  - 24-byte entries * nr (20-byte sha1 + 4-byte offset)
		 *  - 20-byte SHA1 of the packfile
		 *  - 20-byte SHA1 file checksum
		 */
		if (idx_size != 4*256 + nr * 24 + 20 + 20) {
			munmap(idx_map, idx_size);
506
			return error("wrong index v1 file size in %s", path);
507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522
		}
	} else if (version == 2) {
		/*
		 * Minimum size:
		 *  - 8 bytes of header
		 *  - 256 index entries 4 bytes each
		 *  - 20-byte sha1 entry * nr
		 *  - 4-byte crc entry * nr
		 *  - 4-byte offset entry * nr
		 *  - 20-byte SHA1 of the packfile
		 *  - 20-byte SHA1 file checksum
		 * And after the 4-byte offset table might be a
		 * variable sized table containing 8-byte entries
		 * for offsets larger than 2^31.
		 */
		unsigned long min_size = 8 + 4*256 + nr*(20 + 4 + 4) + 20 + 20;
L
Linus Torvalds 已提交
523 524 525 526
		unsigned long max_size = min_size;
		if (nr)
			max_size += (nr - 1)*8;
		if (idx_size < min_size || idx_size > max_size) {
527
			munmap(idx_map, idx_size);
528
			return error("wrong index v2 file size in %s", path);
529
		}
530 531 532 533 534 535 536 537 538
		if (idx_size != min_size &&
		    /*
		     * make sure we can deal with large pack offsets.
		     * 31-bit signed offset won't be enough, neither
		     * 32-bit unsigned one will be.
		     */
		    (sizeof(off_t) <= 4)) {
			munmap(idx_map, idx_size);
			return error("pack too large for current definition of off_t in %s", path);
539
		}
540
	}
541

542
	p->index_version = version;
543 544
	p->index_data = idx_map;
	p->index_size = idx_size;
N
Nicolas Pitre 已提交
545
	p->num_objects = nr;
546 547 548
	return 0;
}

549
int open_pack_index(struct packed_git *p)
550 551 552 553 554 555 556 557 558 559 560 561 562 563
{
	char *idx_name;
	int ret;

	if (p->index_data)
		return 0;

	idx_name = xstrdup(p->pack_name);
	strcpy(idx_name + strlen(idx_name) - strlen(".pack"), ".idx");
	ret = check_packed_git_idx(idx_name, p);
	free(idx_name);
	return ret;
}

564 565 566 567
static void scan_windows(struct packed_git *p,
	struct packed_git **lru_p,
	struct pack_window **lru_w,
	struct pack_window **lru_l)
568
{
569 570 571 572 573 574 575 576
	struct pack_window *w, *w_l;

	for (w_l = NULL, w = p->windows; w; w = w->next) {
		if (!w->inuse_cnt) {
			if (!*lru_w || w->last_used < (*lru_w)->last_used) {
				*lru_p = p;
				*lru_w = w;
				*lru_l = w_l;
577 578
			}
		}
579
		w_l = w;
580
	}
581 582
}

583
static int unuse_one_window(struct packed_git *current, int keep_fd)
584 585 586 587 588 589 590 591
{
	struct packed_git *p, *lru_p = NULL;
	struct pack_window *lru_w = NULL, *lru_l = NULL;

	if (current)
		scan_windows(current, &lru_p, &lru_w, &lru_l);
	for (p = packed_git; p; p = p->next)
		scan_windows(p, &lru_p, &lru_w, &lru_l);
592 593 594 595 596 597 598
	if (lru_p) {
		munmap(lru_w->base, lru_w->len);
		pack_mapped -= lru_w->len;
		if (lru_l)
			lru_l->next = lru_w->next;
		else {
			lru_p->windows = lru_w->next;
599
			if (!lru_p->windows && lru_p->pack_fd != keep_fd) {
600 601 602 603 604
				close(lru_p->pack_fd);
				lru_p->pack_fd = -1;
			}
		}
		free(lru_w);
605
		pack_open_windows--;
606 607 608
		return 1;
	}
	return 0;
609 610
}

611
void release_pack_memory(size_t need, int fd)
612 613
{
	size_t cur = pack_mapped;
614
	while (need >= (cur - pack_mapped) && unuse_one_window(NULL, fd))
615 616 617
		; /* nothing */
}

618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633
void close_pack_windows(struct packed_git *p)
{
	while (p->windows) {
		struct pack_window *w = p->windows;

		if (w->inuse_cnt)
			die("pack '%s' still has open windows to it",
			    p->pack_name);
		munmap(w->base, w->len);
		pack_mapped -= w->len;
		pack_open_windows--;
		p->windows = w->next;
		free(w);
	}
}

634
void unuse_pack(struct pack_window **w_cursor)
635
{
636 637 638 639 640
	struct pack_window *w = *w_cursor;
	if (w) {
		w->inuse_cnt--;
		*w_cursor = NULL;
	}
641 642
}

643 644 645 646 647
/*
 * Do not call this directly as this leaks p->pack_fd on error return;
 * call open_packed_git() instead.
 */
static int open_packed_git_1(struct packed_git *p)
648
{
649 650 651 652
	struct stat st;
	struct pack_header hdr;
	unsigned char sha1[20];
	unsigned char *idx_sha1;
653
	long fd_flag;
654

655 656 657
	if (!p->index_data && open_pack_index(p))
		return error("packfile %s index unavailable", p->pack_name);

658 659
	p->pack_fd = open(p->pack_name, O_RDONLY);
	if (p->pack_fd < 0 || fstat(p->pack_fd, &st))
660
		return -1;
661 662

	/* If we created the struct before we had the pack we lack size. */
663 664
	if (!p->pack_size) {
		if (!S_ISREG(st.st_mode))
665
			return error("packfile %s not a regular file", p->pack_name);
666
		p->pack_size = st.st_size;
667
	} else if (p->pack_size != st.st_size)
668
		return error("packfile %s size changed", p->pack_name);
669

670 671 672 673 674
	/* We leave these file descriptors open with sliding mmap;
	 * there is no point keeping them open across exec(), though.
	 */
	fd_flag = fcntl(p->pack_fd, F_GETFD, 0);
	if (fd_flag < 0)
675
		return error("cannot determine file descriptor flags");
676 677
	fd_flag |= FD_CLOEXEC;
	if (fcntl(p->pack_fd, F_SETFD, fd_flag) == -1)
678
		return error("cannot set FD_CLOEXEC");
679

680
	/* Verify we recognize this pack file format. */
681
	if (read_in_full(p->pack_fd, &hdr, sizeof(hdr)) != sizeof(hdr))
682
		return error("file %s is far too short to be a packfile", p->pack_name);
683
	if (hdr.hdr_signature != htonl(PACK_SIGNATURE))
684
		return error("file %s is not a GIT packfile", p->pack_name);
685
	if (!pack_version_ok(hdr.hdr_version))
686
		return error("packfile %s is version %u and not supported"
687 688 689 690
			" (try upgrading GIT to a newer version)",
			p->pack_name, ntohl(hdr.hdr_version));

	/* Verify the pack matches its index. */
N
Nicolas Pitre 已提交
691
	if (p->num_objects != ntohl(hdr.hdr_entries))
692
		return error("packfile %s claims to have %u objects"
N
Nicolas Pitre 已提交
693 694 695
			     " while index indicates %u objects",
			     p->pack_name, ntohl(hdr.hdr_entries),
			     p->num_objects);
696
	if (lseek(p->pack_fd, p->pack_size - sizeof(sha1), SEEK_SET) == -1)
697
		return error("end of packfile %s is unavailable", p->pack_name);
698
	if (read_in_full(p->pack_fd, sha1, sizeof(sha1)) != sizeof(sha1))
699
		return error("packfile %s signature is unavailable", p->pack_name);
700
	idx_sha1 = ((unsigned char *)p->index_data) + p->index_size - 40;
701
	if (hashcmp(sha1, idx_sha1))
702 703
		return error("packfile %s does not match index", p->pack_name);
	return 0;
704 705
}

706 707 708 709 710 711 712 713 714 715 716
static int open_packed_git(struct packed_git *p)
{
	if (!open_packed_git_1(p))
		return 0;
	if (p->pack_fd != -1) {
		close(p->pack_fd);
		p->pack_fd = -1;
	}
	return -1;
}

717
static int in_window(struct pack_window *win, off_t offset)
718 719 720 721 722 723 724 725 726 727 728 729
{
	/* We must promise at least 20 bytes (one hash) after the
	 * offset is available from this window, otherwise the offset
	 * is not actually in this window and a different window (which
	 * has that one hash excess) must be used.  This is to support
	 * the object header and delta base parsing routines below.
	 */
	off_t win_off = win->offset;
	return win_off <= offset
		&& (offset + 20) <= (win_off + win->len);
}

730 731
unsigned char* use_pack(struct packed_git *p,
		struct pack_window **w_cursor,
732
		off_t offset,
733
		unsigned int *left)
734
{
735
	struct pack_window *win = *w_cursor;
736

737 738
	if (p->pack_fd == -1 && open_packed_git(p))
		die("packfile %s cannot be accessed", p->pack_name);
739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755

	/* Since packfiles end in a hash of their content and its
	 * pointless to ask for an offset into the middle of that
	 * hash, and the in_window function above wouldn't match
	 * don't allow an offset too close to the end of the file.
	 */
	if (offset > (p->pack_size - 20))
		die("offset beyond end of packfile (truncated pack?)");

	if (!win || !in_window(win, offset)) {
		if (win)
			win->inuse_cnt--;
		for (win = p->windows; win; win = win->next) {
			if (in_window(win, offset))
				break;
		}
		if (!win) {
756
			size_t window_align = packed_git_window_size / 2;
757
			off_t len;
758
			win = xcalloc(1, sizeof(*win));
759
			win->offset = (offset / window_align) * window_align;
760 761 762 763
			len = p->pack_size - win->offset;
			if (len > packed_git_window_size)
				len = packed_git_window_size;
			win->len = (size_t)len;
764
			pack_mapped += win->len;
765
			while (packed_git_limit < pack_mapped
766
				&& unuse_one_window(p, p->pack_fd))
767
				; /* nothing */
768
			win->base = xmmap(NULL, win->len,
769 770 771
				PROT_READ, MAP_PRIVATE,
				p->pack_fd, win->offset);
			if (win->base == MAP_FAILED)
772 773 774
				die("packfile %s cannot be mapped: %s",
					p->pack_name,
					strerror(errno));
775 776 777 778 779 780
			pack_mmap_calls++;
			pack_open_windows++;
			if (pack_mapped > peak_pack_mapped)
				peak_pack_mapped = pack_mapped;
			if (pack_open_windows > peak_pack_open_windows)
				peak_pack_open_windows = pack_open_windows;
781 782 783
			win->next = p->windows;
			p->windows = win;
		}
784
	}
785 786 787 788 789
	if (win != *w_cursor) {
		win->last_used = pack_used_ctr++;
		win->inuse_cnt++;
		*w_cursor = win;
	}
790
	offset -= win->offset;
791
	if (left)
792
		*left = win->len - xsize_t(offset);
793
	return win->base + offset;
794 795
}

796
struct packed_git *add_packed_git(const char *path, int path_len, int local)
797 798
{
	struct stat st;
799
	struct packed_git *p = xmalloc(sizeof(*p) + path_len + 2);
800

801 802 803 804 805 806
	/*
	 * Make sure a corresponding .pack file exists and that
	 * the index looks sane.
	 */
	path_len -= strlen(".idx");
	if (path_len < 1)
807
		return NULL;
808 809
	memcpy(p->pack_name, path, path_len);
	strcpy(p->pack_name + path_len, ".pack");
810
	if (stat(p->pack_name, &st) || !S_ISREG(st.st_mode)) {
811
		free(p);
812 813
		return NULL;
	}
814

815 816 817
	/* ok, it looks sane as far as we can check without
	 * actually mapping the pack file.
	 */
818 819 820 821
	p->index_version = 0;
	p->index_data = NULL;
	p->index_size = 0;
	p->num_objects = 0;
822 823
	p->pack_size = st.st_size;
	p->next = NULL;
824
	p->windows = NULL;
825
	p->pack_fd = -1;
826
	p->pack_local = local;
827
	p->mtime = st.st_mtime;
828 829
	if (path_len < 40 || get_sha1_hex(path + path_len - 40, p->sha1))
		hashclr(p->sha1);
830 831 832
	return p;
}

833
struct packed_git *parse_pack_index(unsigned char *sha1)
834 835 836 837 838
{
	char *path = sha1_pack_index_name(sha1);
	return parse_pack_index_file(sha1, path);
}

839 840
struct packed_git *parse_pack_index_file(const unsigned char *sha1,
					 const char *idx_path)
841
{
842 843
	const char *path = sha1_pack_name(sha1);
	struct packed_git *p = xmalloc(sizeof(*p) + strlen(path) + 2);
844

845 846
	if (check_packed_git_idx(idx_path, p)) {
		free(p);
847
		return NULL;
848
	}
849 850 851 852

	strcpy(p->pack_name, path);
	p->pack_size = 0;
	p->next = NULL;
853
	p->windows = NULL;
854
	p->pack_fd = -1;
855
	hashcpy(p->sha1, sha1);
856 857 858 859 860 861 862 863 864
	return p;
}

void install_packed_git(struct packed_git *pack)
{
	pack->next = packed_git;
	packed_git = pack;
}

865
static void prepare_packed_git_one(char *objdir, int local)
866
{
867 868 869 870
	/* Ensure that this buffer is large enough so that we can
	   append "/pack/" without clobbering the stack even if
	   strlen(objdir) were PATH_MAX.  */
	char path[PATH_MAX + 1 + 4 + 1 + 1];
871 872 873 874 875 876 877
	int len;
	DIR *dir;
	struct dirent *de;

	sprintf(path, "%s/pack", objdir);
	len = strlen(path);
	dir = opendir(path);
878
	if (!dir) {
J
Junio C Hamano 已提交
879
		if (errno != ENOENT)
880
			error("unable to open object pack directory: %s: %s",
J
Junio C Hamano 已提交
881
			      path, strerror(errno));
882
		return;
883
	}
884 885 886 887 888
	path[len++] = '/';
	while ((de = readdir(dir)) != NULL) {
		int namelen = strlen(de->d_name);
		struct packed_git *p;

889
		if (!has_extension(de->d_name, ".idx"))
890 891
			continue;

892 893 894
		if (len + namelen + 1 > sizeof(path))
			continue;

895
		/* Don't reopen a pack we already have. */
896
		strcpy(path + len, de->d_name);
897 898 899 900 901 902
		for (p = packed_git; p; p = p->next) {
			if (!memcmp(path, p->pack_name, len + namelen - 4))
				break;
		}
		if (p)
			continue;
903 904 905
		/* See if it really is a valid .idx file with corresponding
		 * .pack file that we can map.
		 */
906
		p = add_packed_git(path, len + namelen, local);
907 908
		if (!p)
			continue;
909
		install_packed_git(p);
910
	}
911
	closedir(dir);
912 913
}

914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967
static int sort_pack(const void *a_, const void *b_)
{
	struct packed_git *a = *((struct packed_git **)a_);
	struct packed_git *b = *((struct packed_git **)b_);
	int st;

	/*
	 * Local packs tend to contain objects specific to our
	 * variant of the project than remote ones.  In addition,
	 * remote ones could be on a network mounted filesystem.
	 * Favor local ones for these reasons.
	 */
	st = a->pack_local - b->pack_local;
	if (st)
		return -st;

	/*
	 * Younger packs tend to contain more recent objects,
	 * and more recent objects tend to get accessed more
	 * often.
	 */
	if (a->mtime < b->mtime)
		return 1;
	else if (a->mtime == b->mtime)
		return 0;
	return -1;
}

static void rearrange_packed_git(void)
{
	struct packed_git **ary, *p;
	int i, n;

	for (n = 0, p = packed_git; p; p = p->next)
		n++;
	if (n < 2)
		return;

	/* prepare an array of packed_git for easier sorting */
	ary = xcalloc(n, sizeof(struct packed_git *));
	for (n = 0, p = packed_git; p; p = p->next)
		ary[n++] = p;

	qsort(ary, n, sizeof(struct packed_git *), sort_pack);

	/* link them back again */
	for (i = 0; i < n - 1; i++)
		ary[i]->next = ary[i + 1];
	ary[n - 1]->next = NULL;
	packed_git = ary[0];

	free(ary);
}

968
static int prepare_packed_git_run_once = 0;
969
void prepare_packed_git(void)
970
{
971
	struct alternate_object_database *alt;
972

973
	if (prepare_packed_git_run_once)
974
		return;
975
	prepare_packed_git_one(get_object_directory(), 1);
976
	prepare_alt_odb();
977
	for (alt = alt_odb_list; alt; alt = alt->next) {
978
		alt->name[-1] = 0;
979
		prepare_packed_git_one(alt->base, 0);
980
		alt->name[-1] = '/';
981
	}
982
	rearrange_packed_git();
983 984 985
	prepare_packed_git_run_once = 1;
}

986
void reprepare_packed_git(void)
987 988 989
{
	prepare_packed_git_run_once = 0;
	prepare_packed_git();
990 991
}

992
int check_sha1_signature(const unsigned char *sha1, void *map, unsigned long size, const char *type)
993 994
{
	unsigned char real_sha1[20];
995
	hash_sha1_file(map, size, type, real_sha1);
996
	return hashcmp(sha1, real_sha1) ? -1 : 0;
997 998
}

J
Junio C Hamano 已提交
999
static void *map_sha1_file(const unsigned char *sha1, unsigned long *size)
1000 1001 1002
{
	struct stat st;
	void *map;
1003
	int fd;
1004 1005 1006 1007 1008
	char *filename = find_sha1_file(sha1, &st);

	if (!filename) {
		return NULL;
	}
1009

1010
	fd = open(filename, O_RDONLY | sha1_file_open_flag);
1011
	if (fd < 0) {
1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022
		/* See if it works without O_NOATIME */
		switch (sha1_file_open_flag) {
		default:
			fd = open(filename, O_RDONLY);
			if (fd >= 0)
				break;
		/* Fallthrough */
		case 0:
			return NULL;
		}

1023 1024 1025
		/* If it failed once, it will probably fail again.
		 * Stop using O_NOATIME
		 */
1026
		sha1_file_open_flag = 0;
1027
	}
1028 1029
	*size = xsize_t(st.st_size);
	map = xmmap(NULL, *size, PROT_READ, MAP_PRIVATE, fd, 0);
1030 1031 1032 1033
	close(fd);
	return map;
}

1034
static int legacy_loose_object(unsigned char *map)
1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049
{
	unsigned int word;

	/*
	 * Is it a zlib-compressed buffer? If so, the first byte
	 * must be 0x78 (15-bit window size, deflated), and the
	 * first 16-bit word is evenly divisible by 31
	 */
	word = (map[0] << 8) + map[1];
	if (map[0] == 0x78 && !(word % 31))
		return 1;
	else
		return 0;
}

1050
unsigned long unpack_object_header_gently(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep)
1051
{
1052
	unsigned shift;
1053 1054
	unsigned char c;
	unsigned long size;
1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080
	unsigned long used = 0;

	c = buf[used++];
	*type = (c >> 4) & 7;
	size = c & 15;
	shift = 4;
	while (c & 0x80) {
		if (len <= used)
			return 0;
		if (sizeof(long) * 8 <= shift)
			return 0;
		c = buf[used++];
		size += (c & 0x7f) << shift;
		shift += 7;
	}
	*sizep = size;
	return used;
}

static int unpack_sha1_header(z_stream *stream, unsigned char *map, unsigned long mapsize, void *buffer, unsigned long bufsiz)
{
	unsigned long size, used;
	static const char valid_loose_object_type[8] = {
		0, /* OBJ_EXT */
		1, 1, 1, 1, /* "commit", "tree", "blob", "tag" */
		0, /* "delta" and others are invalid in a loose object */
1081
	};
1082
	enum object_type type;
1083

1084 1085 1086 1087 1088
	/* Get the data stream */
	memset(stream, 0, sizeof(*stream));
	stream->next_in = map;
	stream->avail_in = mapsize;
	stream->next_out = buffer;
1089 1090
	stream->avail_out = bufsiz;

1091
	if (legacy_loose_object(map)) {
1092 1093 1094 1095
		inflateInit(stream);
		return inflate(stream, 0);
	}

1096 1097 1098 1099 1100 1101 1102 1103

	/*
	 * There used to be a second loose object header format which
	 * was meant to mimic the in-pack format, allowing for direct
	 * copy of the object data.  This format turned up not to be
	 * really worth it and we don't write it any longer.  But we
	 * can still read it.
	 */
1104 1105
	used = unpack_object_header_gently(map, mapsize, &type, &size);
	if (!used || !valid_loose_object_type[type])
1106
		return -1;
1107 1108
	map += used;
	mapsize -= used;
1109 1110 1111 1112

	/* Set up the stream for the rest.. */
	stream->next_in = map;
	stream->avail_in = mapsize;
1113
	inflateInit(stream);
1114 1115

	/* And generate the fake traditional header */
1116
	stream->total_out = 1 + snprintf(buffer, bufsiz, "%s %lu",
1117
					 typename(type), size);
1118
	return 0;
1119 1120
}

1121
static void *unpack_sha1_rest(z_stream *stream, void *buffer, unsigned long size, const unsigned char *sha1)
1122 1123
{
	int bytes = strlen(buffer) + 1;
1124
	unsigned char *buf = xmalloc(1+size);
1125
	unsigned long n;
1126
	int status = Z_OK;
1127

1128 1129 1130 1131 1132
	n = stream->total_out - bytes;
	if (n > size)
		n = size;
	memcpy(buf, (char *) buffer + bytes, n);
	bytes = n;
1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146
	if (bytes <= size) {
		/*
		 * The above condition must be (bytes <= size), not
		 * (bytes < size).  In other words, even though we
		 * expect no more output and set avail_out to zer0,
		 * the input zlib stream may have bytes that express
		 * "this concludes the stream", and we *do* want to
		 * eat that input.
		 *
		 * Otherwise we would not be able to test that we
		 * consumed all the input to reach the expected size;
		 * we also want to check that zlib tells us that all
		 * went well with status == Z_STREAM_END at the end.
		 */
1147 1148
		stream->next_out = buf + bytes;
		stream->avail_out = size - bytes;
1149 1150
		while (status == Z_OK)
			status = inflate(stream, Z_FINISH);
1151 1152
	}
	buf[size] = 0;
1153
	if (status == Z_STREAM_END && !stream->avail_in) {
1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164
		inflateEnd(stream);
		return buf;
	}

	if (status < 0)
		error("corrupt loose object '%s'", sha1_to_hex(sha1));
	else if (stream->avail_in)
		error("garbage at end of loose object '%s'",
		      sha1_to_hex(sha1));
	free(buf);
	return NULL;
1165 1166 1167 1168 1169 1170 1171
}

/*
 * We used to just use "sscanf()", but that's actually way
 * too permissive for what we want to check. So do an anal
 * object header parse by hand.
 */
1172
static int parse_sha1_header(const char *hdr, unsigned long *sizep)
1173
{
1174
	char type[10];
1175 1176 1177 1178
	int i;
	unsigned long size;

	/*
J
Junio C Hamano 已提交
1179
	 * The type can be at most ten bytes (including the
1180
	 * terminating '\0' that we add), and is followed by
1181
	 * a space.
1182
	 */
1183
	i = 0;
1184 1185 1186 1187
	for (;;) {
		char c = *hdr++;
		if (c == ' ')
			break;
1188 1189
		type[i++] = c;
		if (i >= sizeof(type))
1190 1191
			return -1;
	}
1192
	type[i] = 0;
1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214

	/*
	 * The length must follow immediately, and be in canonical
	 * decimal format (ie "010" is not valid).
	 */
	size = *hdr++ - '0';
	if (size > 9)
		return -1;
	if (size) {
		for (;;) {
			unsigned long c = *hdr - '0';
			if (c > 9)
				break;
			hdr++;
			size = size * 10 + c;
		}
	}
	*sizep = size;

	/*
	 * The length must be followed by a zero byte
	 */
1215
	return *hdr ? -1 : type_from_string(type);
1216 1217
}

1218
static void *unpack_sha1_file(void *map, unsigned long mapsize, enum object_type *type, unsigned long *size, const unsigned char *sha1)
1219
{
1220
	int ret;
1221
	z_stream stream;
1222
	char hdr[8192];
1223

1224
	ret = unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr));
1225
	if (ret < Z_OK || (*type = parse_sha1_header(hdr, size)) < 0)
1226 1227
		return NULL;

1228
	return unpack_sha1_rest(&stream, hdr, *size, sha1);
1229 1230
}

N
Nicolas Pitre 已提交
1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267
unsigned long get_size_from_delta(struct packed_git *p,
				  struct pack_window **w_curs,
			          off_t curpos)
{
	const unsigned char *data;
	unsigned char delta_head[20], *in;
	z_stream stream;
	int st;

	memset(&stream, 0, sizeof(stream));
	stream.next_out = delta_head;
	stream.avail_out = sizeof(delta_head);

	inflateInit(&stream);
	do {
		in = use_pack(p, w_curs, curpos, &stream.avail_in);
		stream.next_in = in;
		st = inflate(&stream, Z_FINISH);
		curpos += stream.next_in - in;
	} while ((st == Z_OK || st == Z_BUF_ERROR) &&
		 stream.total_out < sizeof(delta_head));
	inflateEnd(&stream);
	if ((st != Z_STREAM_END) && stream.total_out != sizeof(delta_head))
		die("delta data unpack-initial failed");

	/* Examine the initial part of the delta to figure out
	 * the result size.
	 */
	data = delta_head;

	/* ignore base size */
	get_delta_hdr_size(&data, delta_head+sizeof(delta_head));

	/* Read the result size */
	return get_delta_hdr_size(&data, delta_head+sizeof(delta_head));
}

1268
static off_t get_delta_base(struct packed_git *p,
1269
				    struct pack_window **w_curs,
1270
				    off_t *curpos,
1271
				    enum object_type type,
1272
				    off_t delta_obj_offset)
1273
{
1274
	unsigned char *base_info = use_pack(p, w_curs, *curpos, NULL);
1275
	off_t base_offset;
1276

1277 1278 1279 1280 1281 1282
	/* use_pack() assured us we have [base_info, base_info + 20)
	 * as a range that we can look at without walking off the
	 * end of the mapped window.  Its actually the hash size
	 * that is assured.  An OFS_DELTA longer than the hash size
	 * is stupid, as then a REF_DELTA would be smaller to store.
	 */
1283
	if (type == OBJ_OFS_DELTA) {
1284 1285 1286 1287 1288
		unsigned used = 0;
		unsigned char c = base_info[used++];
		base_offset = c & 127;
		while (c & 128) {
			base_offset += 1;
1289
			if (!base_offset || MSB(base_offset, 7))
1290 1291 1292 1293 1294 1295 1296
				die("offset value overflow for delta base object");
			c = base_info[used++];
			base_offset = (base_offset << 7) + (c & 127);
		}
		base_offset = delta_obj_offset - base_offset;
		if (base_offset >= delta_obj_offset)
			die("delta base offset out of bound");
1297
		*curpos += used;
1298
	} else if (type == OBJ_REF_DELTA) {
1299 1300 1301 1302 1303
		/* The base entry _must_ be in the same pack */
		base_offset = find_pack_entry_one(base_info, p);
		if (!base_offset)
			die("failed to find delta-pack base object %s",
				sha1_to_hex(base_info));
1304
		*curpos += 20;
1305 1306
	} else
		die("I am totally screwed");
1307
	return base_offset;
1308 1309
}

J
Junio C Hamano 已提交
1310
/* forward declaration for a mutually recursive function */
1311
static int packed_object_info(struct packed_git *p, off_t offset,
1312
			      unsigned long *sizep);
J
Junio C Hamano 已提交
1313

N
Nicolas Pitre 已提交
1314
static int packed_delta_info(struct packed_git *p,
1315
			     struct pack_window **w_curs,
1316
			     off_t curpos,
1317
			     enum object_type type,
1318
			     off_t obj_offset,
N
Nicolas Pitre 已提交
1319
			     unsigned long *sizep)
1320
{
1321
	off_t base_offset;
J
Junio C Hamano 已提交
1322

1323 1324
	base_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);
	type = packed_object_info(p, base_offset, NULL);
J
Junio C Hamano 已提交
1325

1326 1327 1328 1329 1330
	/* We choose to only get the type of the base object and
	 * ignore potentially corrupt pack file that expects the delta
	 * based on a base with a wrong size.  This saves tons of
	 * inflate() calls.
	 */
N
Nicolas Pitre 已提交
1331 1332
	if (sizep)
		*sizep = get_size_from_delta(p, w_curs, curpos);
1333 1334

	return type;
1335 1336
}

1337 1338
static int unpack_object_header(struct packed_git *p,
				struct pack_window **w_curs,
1339
				off_t *curpos,
1340
				unsigned long *sizep)
1341
{
1342 1343
	unsigned char *base;
	unsigned int left;
1344
	unsigned long used;
1345
	enum object_type type;
1346

1347 1348
	/* use_pack() assures us we have [base, base + 20) available
	 * as a range that we can look at at.  (Its actually the hash
P
Pavel Roskin 已提交
1349
	 * size that is assured.)  With our object header encoding
1350 1351 1352
	 * the maximum deflated object size is 2^137, which is just
	 * insane, so we know won't exceed what we have been given.
	 */
1353 1354
	base = use_pack(p, w_curs, *curpos, &left);
	used = unpack_object_header_gently(base, left, &type, sizep);
1355 1356
	if (!used)
		die("object offset outside of pack file");
1357
	*curpos += used;
1358

1359
	return type;
1360 1361
}

1362
const char *packed_object_info_detail(struct packed_git *p,
1363
				      off_t obj_offset,
1364 1365 1366 1367
				      unsigned long *size,
				      unsigned long *store_size,
				      unsigned int *delta_chain_length,
				      unsigned char *base_sha1)
1368
{
1369
	struct pack_window *w_curs = NULL;
1370 1371
	off_t curpos;
	unsigned long dummy;
N
Nicolas Pitre 已提交
1372
	unsigned char *next_sha1;
1373
	enum object_type type;
1374
	struct revindex_entry *revidx;
1375

N
Nicolas Pitre 已提交
1376
	*delta_chain_length = 0;
1377
	curpos = obj_offset;
1378
	type = unpack_object_header(p, &w_curs, &curpos, size);
N
Nicolas Pitre 已提交
1379

1380 1381 1382
	revidx = find_pack_revindex(p, obj_offset);
	*store_size = revidx[1].offset - obj_offset;

N
Nicolas Pitre 已提交
1383
	for (;;) {
1384
		switch (type) {
N
Nicolas Pitre 已提交
1385
		default:
1386
			die("pack %s contains unknown object type %d",
1387
			    p->pack_name, type);
N
Nicolas Pitre 已提交
1388 1389 1390 1391
		case OBJ_COMMIT:
		case OBJ_TREE:
		case OBJ_BLOB:
		case OBJ_TAG:
1392
			unuse_pack(&w_curs);
1393
			return typename(type);
1394
		case OBJ_OFS_DELTA:
1395
			obj_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
1396
			if (*delta_chain_length == 0) {
1397 1398
				revidx = find_pack_revindex(p, obj_offset);
				hashcpy(base_sha1, nth_packed_object_sha1(p, revidx->nr));
1399 1400 1401
			}
			break;
		case OBJ_REF_DELTA:
1402
			next_sha1 = use_pack(p, &w_curs, curpos, NULL);
N
Nicolas Pitre 已提交
1403 1404
			if (*delta_chain_length == 0)
				hashcpy(base_sha1, next_sha1);
1405
			obj_offset = find_pack_entry_one(next_sha1, p);
N
Nicolas Pitre 已提交
1406 1407 1408
			break;
		}
		(*delta_chain_length)++;
1409
		curpos = obj_offset;
1410
		type = unpack_object_header(p, &w_curs, &curpos, &dummy);
1411 1412 1413
	}
}

1414
static int packed_object_info(struct packed_git *p, off_t obj_offset,
1415
			      unsigned long *sizep)
1416
{
1417
	struct pack_window *w_curs = NULL;
1418 1419
	unsigned long size;
	off_t curpos = obj_offset;
1420
	enum object_type type;
1421

1422
	type = unpack_object_header(p, &w_curs, &curpos, &size);
1423

1424
	switch (type) {
1425 1426
	case OBJ_OFS_DELTA:
	case OBJ_REF_DELTA:
1427 1428
		type = packed_delta_info(p, &w_curs, curpos,
					 type, obj_offset, sizep);
1429
		break;
1430 1431 1432 1433
	case OBJ_COMMIT:
	case OBJ_TREE:
	case OBJ_BLOB:
	case OBJ_TAG:
1434 1435
		if (sizep)
			*sizep = size;
1436
		break;
1437
	default:
1438
		die("pack %s contains unknown object type %d",
1439
		    p->pack_name, type);
1440
	}
1441
	unuse_pack(&w_curs);
1442
	return type;
1443 1444
}

1445
static void *unpack_compressed_entry(struct packed_git *p,
1446
				    struct pack_window **w_curs,
1447
				    off_t curpos,
1448
				    unsigned long size)
1449 1450 1451
{
	int st;
	z_stream stream;
1452
	unsigned char *buffer, *in;
1453 1454 1455 1456 1457 1458 1459 1460

	buffer = xmalloc(size + 1);
	buffer[size] = 0;
	memset(&stream, 0, sizeof(stream));
	stream.next_out = buffer;
	stream.avail_out = size;

	inflateInit(&stream);
1461
	do {
1462
		in = use_pack(p, w_curs, curpos, &stream.avail_in);
1463 1464
		stream.next_in = in;
		st = inflate(&stream, Z_FINISH);
1465
		curpos += stream.next_in - in;
1466
	} while (st == Z_OK || st == Z_BUF_ERROR);
1467 1468 1469 1470 1471 1472 1473 1474 1475
	inflateEnd(&stream);
	if ((st != Z_STREAM_END) || stream.total_out != size) {
		free(buffer);
		return NULL;
	}

	return buffer;
}

1476 1477
#define MAX_DELTA_CACHE (256)

1478
static size_t delta_base_cached;
1479 1480 1481 1482 1483 1484

static struct delta_base_cache_lru_list {
	struct delta_base_cache_lru_list *prev;
	struct delta_base_cache_lru_list *next;
} delta_base_cache_lru = { &delta_base_cache_lru, &delta_base_cache_lru };

1485
static struct delta_base_cache_entry {
1486 1487
	struct delta_base_cache_lru_list lru;
	void *data;
1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499
	struct packed_git *p;
	off_t base_offset;
	unsigned long size;
	enum object_type type;
} delta_base_cache[MAX_DELTA_CACHE];

static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)
{
	unsigned long hash;

	hash = (unsigned long)p + (unsigned long)base_offset;
	hash += (hash >> 8) + (hash >> 16);
1500
	return hash % MAX_DELTA_CACHE;
1501 1502
}

1503
static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
1504
	unsigned long *base_size, enum object_type *type, int keep_cache)
1505
{
1506 1507 1508 1509 1510 1511 1512
	void *ret;
	unsigned long hash = pack_entry_hash(p, base_offset);
	struct delta_base_cache_entry *ent = delta_base_cache + hash;

	ret = ent->data;
	if (ret && ent->p == p && ent->base_offset == base_offset)
		goto found_cache_entry;
1513
	return unpack_entry(p, base_offset, type, base_size);
1514 1515

found_cache_entry:
1516
	if (!keep_cache) {
1517
		ent->data = NULL;
1518 1519
		ent->lru.next->prev = ent->lru.prev;
		ent->lru.prev->next = ent->lru.next;
1520
		delta_base_cached -= ent->size;
P
Pierre Habouzit 已提交
1521 1522
	} else {
		ret = xmemdupz(ent->data, ent->size);
1523
	}
1524 1525 1526
	*type = ent->type;
	*base_size = ent->size;
	return ret;
1527 1528
}

1529 1530 1531 1532 1533
static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)
{
	if (ent->data) {
		free(ent->data);
		ent->data = NULL;
1534 1535
		ent->lru.next->prev = ent->lru.prev;
		ent->lru.prev->next = ent->lru.next;
1536 1537 1538 1539
		delta_base_cached -= ent->size;
	}
}

1540 1541 1542
static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
	void *base, unsigned long base_size, enum object_type type)
{
1543
	unsigned long hash = pack_entry_hash(p, base_offset);
1544
	struct delta_base_cache_entry *ent = delta_base_cache + hash;
1545
	struct delta_base_cache_lru_list *lru;
1546

1547 1548
	release_delta_base_cache(ent);
	delta_base_cached += base_size;
1549 1550 1551 1552 1553 1554

	for (lru = delta_base_cache_lru.next;
	     delta_base_cached > delta_base_cache_limit
	     && lru != &delta_base_cache_lru;
	     lru = lru->next) {
		struct delta_base_cache_entry *f = (void *)lru;
1555 1556 1557
		if (f->type == OBJ_BLOB)
			release_delta_base_cache(f);
	}
1558 1559 1560 1561 1562 1563 1564
	for (lru = delta_base_cache_lru.next;
	     delta_base_cached > delta_base_cache_limit
	     && lru != &delta_base_cache_lru;
	     lru = lru->next) {
		struct delta_base_cache_entry *f = (void *)lru;
		release_delta_base_cache(f);
	}
1565

1566 1567 1568 1569 1570
	ent->p = p;
	ent->base_offset = base_offset;
	ent->type = type;
	ent->data = base;
	ent->size = base_size;
1571 1572 1573 1574
	ent->lru.next = &delta_base_cache_lru;
	ent->lru.prev = delta_base_cache_lru.prev;
	delta_base_cache_lru.prev->next = &ent->lru;
	delta_base_cache_lru.prev = &ent->lru;
1575 1576
}

1577
static void *unpack_delta_entry(struct packed_git *p,
1578
				struct pack_window **w_curs,
1579
				off_t curpos,
1580
				unsigned long delta_size,
1581
				off_t obj_offset,
1582
				enum object_type *type,
1583
				unsigned long *sizep)
1584
{
1585
	void *delta_data, *result, *base;
1586 1587
	unsigned long base_size;
	off_t base_offset;
N
Nicolas Pitre 已提交
1588

1589
	base_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);
1590
	base = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);
1591
	if (!base)
1592 1593 1594
		die("failed to read delta base object"
		    " at %"PRIuMAX" from %s",
		    (uintmax_t)base_offset, p->pack_name);
1595

1596
	delta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);
1597 1598 1599 1600
	if (!delta_data)
		die("failed to unpack compressed delta"
		    " at %"PRIuMAX" from %s",
		    (uintmax_t)curpos, p->pack_name);
1601 1602
	result = patch_delta(base, base_size,
			     delta_data, delta_size,
1603
			     sizep);
1604 1605 1606
	if (!result)
		die("failed to apply delta");
	free(delta_data);
1607
	add_delta_base_cache(p, base_offset, base, base_size, *type);
1608 1609 1610
	return result;
}

1611
void *unpack_entry(struct packed_git *p, off_t obj_offset,
1612
		   enum object_type *type, unsigned long *sizep)
1613
{
1614
	struct pack_window *w_curs = NULL;
1615
	off_t curpos = obj_offset;
1616
	void *data;
1617

1618 1619
	*type = unpack_object_header(p, &w_curs, &curpos, sizep);
	switch (*type) {
1620 1621
	case OBJ_OFS_DELTA:
	case OBJ_REF_DELTA:
1622 1623
		data = unpack_delta_entry(p, &w_curs, curpos, *sizep,
					  obj_offset, type, sizep);
1624
		break;
1625 1626 1627 1628
	case OBJ_COMMIT:
	case OBJ_TREE:
	case OBJ_BLOB:
	case OBJ_TAG:
1629
		data = unpack_compressed_entry(p, &w_curs, curpos, *sizep);
1630
		break;
1631
	default:
1632
		die("unknown object type %i in %s", *type, p->pack_name);
1633
	}
1634
	unuse_pack(&w_curs);
1635
	return data;
1636 1637
}

1638
const unsigned char *nth_packed_object_sha1(struct packed_git *p,
1639
					    uint32_t n)
1640
{
1641
	const unsigned char *index = p->index_data;
1642 1643 1644 1645 1646
	if (!index) {
		if (open_pack_index(p))
			return NULL;
		index = p->index_data;
	}
N
Nicolas Pitre 已提交
1647
	if (n >= p->num_objects)
1648
		return NULL;
1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673
	index += 4 * 256;
	if (p->index_version == 1) {
		return index + 24 * n + 4;
	} else {
		index += 8;
		return index + 20 * n;
	}
}

static off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)
{
	const unsigned char *index = p->index_data;
	index += 4 * 256;
	if (p->index_version == 1) {
		return ntohl(*((uint32_t *)(index + 24 * n)));
	} else {
		uint32_t off;
		index += 8 + p->num_objects * (20 + 4);
		off = ntohl(*((uint32_t *)(index + 4 * n)));
		if (!(off & 0x80000000))
			return off;
		index += p->num_objects * 4 + (off & 0x7fffffff) * 8;
		return (((uint64_t)ntohl(*((uint32_t *)(index + 0)))) << 32) |
				   ntohl(*((uint32_t *)(index + 4)));
	}
1674 1675
}

1676
off_t find_pack_entry_one(const unsigned char *sha1,
N
Nicolas Pitre 已提交
1677
				  struct packed_git *p)
1678
{
1679 1680
	const uint32_t *level1_ofs = p->index_data;
	const unsigned char *index = p->index_data;
1681 1682 1683 1684 1685 1686
	unsigned hi, lo, stride;
	static int use_lookup = -1;
	static int debug_lookup = -1;

	if (debug_lookup < 0)
		debug_lookup = !!getenv("GIT_DEBUG_LOOKUP");
1687

1688 1689 1690 1691 1692 1693
	if (!index) {
		if (open_pack_index(p))
			return 0;
		level1_ofs = p->index_data;
		index = p->index_data;
	}
1694 1695 1696 1697
	if (p->index_version > 1) {
		level1_ofs += 2;
		index += 8;
	}
1698
	index += 4 * 256;
1699 1700
	hi = ntohl(level1_ofs[*sha1]);
	lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));
1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720
	if (p->index_version > 1) {
		stride = 20;
	} else {
		stride = 24;
		index += 4;
	}

	if (debug_lookup)
		printf("%02x%02x%02x... lo %u hi %u nr %u\n",
		       sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);

	if (use_lookup < 0)
		use_lookup = !!getenv("GIT_USE_LOOKUP");
	if (use_lookup) {
		int pos = sha1_entry_pos(index, stride, 0,
					 lo, hi, p->num_objects, sha1);
		if (pos < 0)
			return 0;
		return nth_packed_object_offset(p, pos);
	}
1721 1722

	do {
1723
		unsigned mi = (lo + hi) / 2;
1724 1725 1726 1727 1728
		int cmp = hashcmp(index + mi * stride, sha1);

		if (debug_lookup)
			printf("lo %u hi %u rg %u mi %u\n",
			       lo, hi, hi - lo, mi);
N
Nicolas Pitre 已提交
1729
		if (!cmp)
1730
			return nth_packed_object_offset(p, mi);
1731 1732 1733 1734 1735 1736 1737 1738
		if (cmp > 0)
			hi = mi;
		else
			lo = mi+1;
	} while (lo < hi);
	return 0;
}

1739
int matches_pack_name(struct packed_git *p, const char *name)
1740 1741 1742
{
	const char *last_c, *c;

1743 1744
	if (!strcmp(p->pack_name, name))
		return 1;
1745 1746 1747 1748 1749 1750

	for (c = p->pack_name, last_c = c; *c;)
		if (*c == '/')
			last_c = ++c;
		else
			++c;
1751 1752
	if (!strcmp(last_c, name))
		return 1;
1753

1754
	return 0;
1755 1756
}

1757
static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, const char **ignore_packed)
1758
{
1759
	static struct packed_git *last_found = (void *)1;
1760
	struct packed_git *p;
1761
	off_t offset;
N
Nicolas Pitre 已提交
1762

1763
	prepare_packed_git();
1764 1765 1766
	if (!packed_git)
		return 0;
	p = (last_found == (void *)1) ? packed_git : last_found;
1767

1768
	do {
1769 1770 1771
		if (ignore_packed) {
			const char **ig;
			for (ig = ignore_packed; *ig; ig++)
1772
				if (matches_pack_name(p, *ig))
1773 1774
					break;
			if (*ig)
1775
				goto next;
1776
		}
1777

N
Nicolas Pitre 已提交
1778 1779
		offset = find_pack_entry_one(sha1, p);
		if (offset) {
1780 1781 1782 1783 1784 1785 1786 1787 1788 1789
			/*
			 * We are about to tell the caller where they can
			 * locate the requested object.  We better make
			 * sure the packfile is still here and can be
			 * accessed before supplying that answer, as
			 * it may have been deleted since the index
			 * was loaded!
			 */
			if (p->pack_fd == -1 && open_packed_git(p)) {
				error("packfile %s cannot be accessed", p->pack_name);
1790
				goto next;
1791
			}
N
Nicolas Pitre 已提交
1792 1793 1794
			e->offset = offset;
			e->p = p;
			hashcpy(e->sha1, sha1);
1795
			last_found = p;
1796
			return 1;
N
Nicolas Pitre 已提交
1797
		}
1798 1799 1800 1801 1802 1803 1804 1805 1806

		next:
		if (p == last_found)
			p = packed_git;
		else
			p = p->next;
		if (p == last_found)
			p = p->next;
	} while (p);
1807 1808 1809
	return 0;
}

J
Junio C Hamano 已提交
1810
struct packed_git *find_sha1_pack(const unsigned char *sha1,
1811 1812 1813 1814 1815
				  struct packed_git *packs)
{
	struct packed_git *p;

	for (p = packs; p; p = p->next) {
N
Nicolas Pitre 已提交
1816
		if (find_pack_entry_one(sha1, p))
1817 1818 1819
			return p;
	}
	return NULL;
1820

1821 1822
}

1823
static int sha1_loose_object_info(const unsigned char *sha1, unsigned long *sizep)
1824
{
1825
	int status;
1826 1827 1828
	unsigned long mapsize, size;
	void *map;
	z_stream stream;
N
Nicolas Pitre 已提交
1829
	char hdr[32];
1830

1831
	map = map_sha1_file(sha1, &mapsize);
1832 1833
	if (!map)
		return error("unable to find %s", sha1_to_hex(sha1));
1834 1835 1836
	if (unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr)) < 0)
		status = error("unable to unpack %s header",
			       sha1_to_hex(sha1));
1837
	else if ((status = parse_sha1_header(hdr, &size)) < 0)
1838
		status = error("unable to parse %s header", sha1_to_hex(sha1));
1839 1840
	else if (sizep)
		*sizep = size;
1841 1842 1843 1844 1845
	inflateEnd(&stream);
	munmap(map, mapsize);
	return status;
}

1846
int sha1_object_info(const unsigned char *sha1, unsigned long *sizep)
1847 1848 1849 1850 1851 1852
{
	struct pack_entry e;

	if (!find_pack_entry(sha1, &e, NULL)) {
		reprepare_packed_git();
		if (!find_pack_entry(sha1, &e, NULL))
1853
			return sha1_loose_object_info(sha1, sizep);
1854
	}
1855
	return packed_object_info(e.p, e.offset, sizep);
1856 1857
}

1858 1859
static void *read_packed_sha1(const unsigned char *sha1,
			      enum object_type *type, unsigned long *size)
1860 1861 1862
{
	struct pack_entry e;

1863
	if (!find_pack_entry(sha1, &e, NULL))
1864
		return NULL;
1865
	else
1866
		return cache_or_unpack_entry(e.p, e.offset, size, type, 1);
1867 1868
}

1869 1870 1871 1872 1873 1874 1875 1876
/*
 * This is meant to hold a *small* number of objects that you would
 * want read_sha1_file() to be able to return, but yet you do not want
 * to write them into the object store (e.g. a browse-only
 * application).
 */
static struct cached_object {
	unsigned char sha1[20];
1877
	enum object_type type;
1878 1879 1880 1881 1882
	void *buf;
	unsigned long size;
} *cached_objects;
static int cached_object_nr, cached_object_alloc;

J
Jeff King 已提交
1883 1884 1885 1886 1887 1888 1889 1890 1891
static struct cached_object empty_tree = {
	/* empty tree sha1: 4b825dc642cb6eb9a060e54bf8d69288fbee4904 */
	"\x4b\x82\x5d\xc6\x42\xcb\x6e\xb9\xa0\x60"
	"\xe5\x4b\xf8\xd6\x92\x88\xfb\xee\x49\x04",
	OBJ_TREE,
	"",
	0
};

1892 1893 1894 1895 1896 1897 1898 1899 1900
static struct cached_object *find_cached_object(const unsigned char *sha1)
{
	int i;
	struct cached_object *co = cached_objects;

	for (i = 0; i < cached_object_nr; i++, co++) {
		if (!hashcmp(co->sha1, sha1))
			return co;
	}
J
Jeff King 已提交
1901 1902
	if (!hashcmp(sha1, empty_tree.sha1))
		return &empty_tree;
1903 1904 1905
	return NULL;
}

1906 1907
int pretend_sha1_file(void *buf, unsigned long len, enum object_type type,
		      unsigned char *sha1)
1908 1909 1910
{
	struct cached_object *co;

1911
	hash_sha1_file(buf, len, typename(type), sha1);
1912 1913 1914 1915 1916 1917 1918 1919 1920 1921
	if (has_sha1_file(sha1) || find_cached_object(sha1))
		return 0;
	if (cached_object_alloc <= cached_object_nr) {
		cached_object_alloc = alloc_nr(cached_object_alloc);
		cached_objects = xrealloc(cached_objects,
					  sizeof(*cached_objects) *
					  cached_object_alloc);
	}
	co = &cached_objects[cached_object_nr++];
	co->size = len;
1922
	co->type = type;
J
Junio C Hamano 已提交
1923 1924
	co->buf = xmalloc(len);
	memcpy(co->buf, buf, len);
1925 1926 1927 1928
	hashcpy(co->sha1, sha1);
	return 0;
}

1929 1930
void *read_sha1_file(const unsigned char *sha1, enum object_type *type,
		     unsigned long *size)
1931 1932 1933
{
	unsigned long mapsize;
	void *map, *buf;
1934 1935 1936 1937
	struct cached_object *co;

	co = find_cached_object(sha1);
	if (co) {
1938
		*type = co->type;
1939
		*size = co->size;
P
Pierre Habouzit 已提交
1940
		return xmemdupz(co->buf, co->size);
1941
	}
1942

1943 1944 1945
	buf = read_packed_sha1(sha1, type, size);
	if (buf)
		return buf;
1946
	map = map_sha1_file(sha1, &mapsize);
1947
	if (map) {
1948
		buf = unpack_sha1_file(map, mapsize, type, size, sha1);
1949 1950 1951
		munmap(map, mapsize);
		return buf;
	}
1952
	reprepare_packed_git();
1953
	return read_packed_sha1(sha1, type, size);
1954 1955
}

1956
void *read_object_with_reference(const unsigned char *sha1,
1957
				 const char *required_type_name,
1958 1959
				 unsigned long *size,
				 unsigned char *actual_sha1_return)
1960
{
1961
	enum object_type type, required_type;
1962 1963
	void *buffer;
	unsigned long isize;
1964
	unsigned char actual_sha1[20];
1965

1966
	required_type = type_from_string(required_type_name);
1967
	hashcpy(actual_sha1, sha1);
1968 1969 1970
	while (1) {
		int ref_length = -1;
		const char *ref_type = NULL;
1971

1972
		buffer = read_sha1_file(actual_sha1, &type, &isize);
1973 1974
		if (!buffer)
			return NULL;
1975
		if (type == required_type) {
1976 1977
			*size = isize;
			if (actual_sha1_return)
1978
				hashcpy(actual_sha1_return, actual_sha1);
1979 1980 1981
			return buffer;
		}
		/* Handle references */
1982
		else if (type == OBJ_COMMIT)
1983
			ref_type = "tree ";
1984
		else if (type == OBJ_TAG)
1985 1986 1987 1988 1989 1990
			ref_type = "object ";
		else {
			free(buffer);
			return NULL;
		}
		ref_length = strlen(ref_type);
1991

1992 1993
		if (ref_length + 40 > isize ||
		    memcmp(buffer, ref_type, ref_length) ||
1994
		    get_sha1_hex((char *) buffer + ref_length, actual_sha1)) {
1995 1996 1997
			free(buffer);
			return NULL;
		}
1998
		free(buffer);
1999 2000
		/* Now we have the ID of the referred-to object in
		 * actual_sha1.  Check again. */
2001 2002 2003
	}
}

N
Nicolas Pitre 已提交
2004
static void write_sha1_file_prepare(const void *buf, unsigned long len,
R
Rene Scharfe 已提交
2005
                                    const char *type, unsigned char *sha1,
N
Nicolas Pitre 已提交
2006
                                    char *hdr, int *hdrlen)
2007 2008 2009 2010
{
	SHA_CTX c;

	/* Generate the header */
N
Nicolas Pitre 已提交
2011
	*hdrlen = sprintf(hdr, "%s %lu", type, len)+1;
2012 2013 2014 2015 2016 2017 2018 2019

	/* Sha1.. */
	SHA1_Init(&c);
	SHA1_Update(&c, hdr, *hdrlen);
	SHA1_Update(&c, buf, len);
	SHA1_Final(sha1, &c);
}

2020 2021 2022 2023 2024 2025
/*
 * Link the tempfile to the final place, possibly creating the
 * last directory level as you do so.
 *
 * Returns the errno on failure, 0 on success.
 */
2026
static int link_temp_to_file(const char *tmpfile, const char *filename)
2027 2028
{
	int ret;
S
Shawn Pearce 已提交
2029
	char *dir;
2030 2031 2032 2033 2034

	if (!link(tmpfile, filename))
		return 0;

	/*
S
Shawn Pearce 已提交
2035
	 * Try to mkdir the last path component if that failed.
2036 2037 2038 2039 2040 2041
	 *
	 * Re-try the "link()" regardless of whether the mkdir
	 * succeeds, since a race might mean that somebody
	 * else succeeded.
	 */
	ret = errno;
S
Shawn Pearce 已提交
2042 2043 2044
	dir = strrchr(filename, '/');
	if (dir) {
		*dir = 0;
2045
		if (!mkdir(filename, 0777) && adjust_shared_perm(filename)) {
2046
			*dir = '/';
S
Shawn Pearce 已提交
2047
			return -2;
2048
		}
S
Shawn Pearce 已提交
2049 2050 2051 2052
		*dir = '/';
		if (!link(tmpfile, filename))
			return 0;
		ret = errno;
2053 2054 2055 2056 2057 2058 2059
	}
	return ret;
}

/*
 * Move the just written object into its final resting place
 */
2060
int move_temp_to_file(const char *tmpfile, const char *filename)
2061 2062
{
	int ret = link_temp_to_file(tmpfile, filename);
2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076

	/*
	 * Coda hack - coda doesn't like cross-directory links,
	 * so we fall back to a rename, which will mean that it
	 * won't be able to check collisions, but that's not a
	 * big deal.
	 *
	 * The same holds for FAT formatted media.
	 *
	 * When this succeeds, we just return 0. We have nothing
	 * left to unlink.
	 */
	if (ret && ret != EEXIST) {
		if (!rename(tmpfile, filename))
2077
			return 0;
2078
		ret = errno;
2079 2080 2081 2082
	}
	unlink(tmpfile);
	if (ret) {
		if (ret != EEXIST) {
2083
			return error("unable to write sha1 filename %s: %s\n", filename, strerror(ret));
2084 2085 2086 2087 2088 2089 2090
		}
		/* FIXME!!! Collision check here ? */
	}

	return 0;
}

L
Linus Torvalds 已提交
2091 2092
static int write_buffer(int fd, const void *buf, size_t len)
{
L
Linus Torvalds 已提交
2093
	if (write_in_full(fd, buf, len) < 0)
2094
		return error("file write error (%s)", strerror(errno));
L
Linus Torvalds 已提交
2095 2096 2097
	return 0;
}

N
Nicolas Pitre 已提交
2098
int hash_sha1_file(const void *buf, unsigned long len, const char *type,
R
Rene Scharfe 已提交
2099 2100
                   unsigned char *sha1)
{
N
Nicolas Pitre 已提交
2101
	char hdr[32];
R
Rene Scharfe 已提交
2102 2103 2104 2105 2106
	int hdrlen;
	write_sha1_file_prepare(buf, len, type, sha1, hdr, &hdrlen);
	return 0;
}

2107 2108
static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,
			      void *buf, unsigned long len, time_t mtime)
2109
{
2110
	int fd, size, ret;
2111
	unsigned char *compressed;
2112
	z_stream stream;
2113
	char *filename;
2114
	static char tmpfile[PATH_MAX];
2115

R
Rene Scharfe 已提交
2116
	filename = sha1_file_name(sha1);
2117 2118
	fd = open(filename, O_RDONLY);
	if (fd >= 0) {
2119
		/*
2120 2121
		 * FIXME!!! We might do collision checking here, but we'd
		 * need to uncompress the old file and check it. Later.
2122
		 */
2123
		close(fd);
2124 2125 2126
		return 0;
	}

2127
	if (errno != ENOENT) {
2128
		return error("sha1 file %s: %s\n", filename, strerror(errno));
2129 2130
	}

2131
	snprintf(tmpfile, sizeof(tmpfile), "%s/tmp_obj_XXXXXX", get_object_directory());
2132

2133 2134
	fd = mkstemp(tmpfile);
	if (fd < 0) {
2135 2136 2137 2138
		if (errno == EPERM)
			return error("insufficient permission for adding an object to repository database %s\n", get_object_directory());
		else
			return error("unable to create temporary sha1 filename %s: %s\n", tmpfile, strerror(errno));
2139 2140
	}

2141 2142
	/* Set it up */
	memset(&stream, 0, sizeof(stream));
2143
	deflateInit(&stream, zlib_compression_level);
2144
	size = 8 + deflateBound(&stream, len+hdrlen);
2145
	compressed = xmalloc(size);
2146 2147 2148 2149

	/* Compress it */
	stream.next_out = compressed;
	stream.avail_out = size;
2150 2151

	/* First header.. */
N
Nicolas Pitre 已提交
2152
	stream.next_in = (unsigned char *)hdr;
2153
	stream.avail_in = hdrlen;
2154 2155
	while (deflate(&stream, 0) == Z_OK)
		/* nothing */;
2156 2157 2158 2159

	/* Then the data itself.. */
	stream.next_in = buf;
	stream.avail_in = len;
2160 2161 2162 2163 2164 2165 2166 2167
	ret = deflate(&stream, Z_FINISH);
	if (ret != Z_STREAM_END)
		die("unable to deflate new object %s (%d)", sha1_to_hex(sha1), ret);

	ret = deflateEnd(&stream);
	if (ret != Z_OK)
		die("deflateEnd on object %s failed (%d)", sha1_to_hex(sha1), ret);

2168 2169
	size = stream.total_out;

L
Linus Torvalds 已提交
2170 2171
	if (write_buffer(fd, compressed, size) < 0)
		die("unable to write sha1 file");
2172
	fchmod(fd, 0444);
2173 2174
	if (close(fd))
		die("unable to write sha1 file");
2175
	free(compressed);
2176

2177 2178 2179 2180 2181 2182 2183 2184 2185
	if (mtime) {
		struct utimbuf utb;
		utb.actime = mtime;
		utb.modtime = mtime;
		if (utime(tmpfile, &utb) < 0)
			warning("failed utime() on %s: %s",
				tmpfile, strerror(errno));
	}

2186
	return move_temp_to_file(tmpfile, filename);
2187
}
2188

2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223
int write_sha1_file(void *buf, unsigned long len, const char *type, unsigned char *returnsha1)
{
	unsigned char sha1[20];
	char hdr[32];
	int hdrlen;

	/* Normally if we have it in the pack then we do not bother writing
	 * it out into .git/objects/??/?{38} file.
	 */
	write_sha1_file_prepare(buf, len, type, sha1, hdr, &hdrlen);
	if (returnsha1)
		hashcpy(returnsha1, sha1);
	if (has_sha1_file(sha1))
		return 0;
	return write_loose_object(sha1, hdr, hdrlen, buf, len, 0);
}

int force_object_loose(const unsigned char *sha1, time_t mtime)
{
	struct stat st;
	void *buf;
	unsigned long len;
	enum object_type type;
	char hdr[32];
	int hdrlen;

	if (find_sha1_file(sha1, &st))
		return 0;
	buf = read_packed_sha1(sha1, &type, &len);
	if (!buf)
		return error("cannot read sha1_file for %s", sha1_to_hex(sha1));
	hdrlen = sprintf(hdr, "%s %lu", typename(type), len) + 1;
	return write_loose_object(sha1, hdr, hdrlen, buf, len, mtime);
}

L
Linus Torvalds 已提交
2224 2225 2226 2227 2228
/*
 * We need to unpack and recompress the object for writing
 * it out to a different file.
 */
static void *repack_object(const unsigned char *sha1, unsigned long *objsize)
D
Daniel Barkalow 已提交
2229
{
L
Linus Torvalds 已提交
2230
	size_t size;
D
Daniel Barkalow 已提交
2231
	z_stream stream;
L
Linus Torvalds 已提交
2232 2233
	unsigned char *unpacked;
	unsigned long len;
2234
	enum object_type type;
N
Nicolas Pitre 已提交
2235
	char hdr[32];
L
Linus Torvalds 已提交
2236 2237
	int hdrlen;
	void *buf;
2238

2239
	/* need to unpack and recompress it by itself */
2240
	unpacked = read_packed_sha1(sha1, &type, &len);
2241 2242
	if (!unpacked)
		error("cannot read sha1_file for %s", sha1_to_hex(sha1));
D
Daniel Barkalow 已提交
2243

2244
	hdrlen = sprintf(hdr, "%s %lu", typename(type), len) + 1;
D
Daniel Barkalow 已提交
2245

L
Linus Torvalds 已提交
2246 2247
	/* Set it up */
	memset(&stream, 0, sizeof(stream));
2248
	deflateInit(&stream, zlib_compression_level);
L
Linus Torvalds 已提交
2249 2250
	size = deflateBound(&stream, len + hdrlen);
	buf = xmalloc(size);
D
Daniel Barkalow 已提交
2251

L
Linus Torvalds 已提交
2252 2253 2254
	/* Compress it */
	stream.next_out = buf;
	stream.avail_out = size;
D
Daniel Barkalow 已提交
2255

L
Linus Torvalds 已提交
2256 2257 2258 2259 2260
	/* First header.. */
	stream.next_in = (void *)hdr;
	stream.avail_in = hdrlen;
	while (deflate(&stream, 0) == Z_OK)
		/* nothing */;
2261

L
Linus Torvalds 已提交
2262 2263 2264 2265 2266 2267 2268
	/* Then the data itself.. */
	stream.next_in = unpacked;
	stream.avail_in = len;
	while (deflate(&stream, Z_FINISH) == Z_OK)
		/* nothing */;
	deflateEnd(&stream);
	free(unpacked);
2269

L
Linus Torvalds 已提交
2270 2271 2272 2273 2274 2275 2276 2277
	*objsize = stream.total_out;
	return buf;
}

int write_sha1_to_fd(int fd, const unsigned char *sha1)
{
	int retval;
	unsigned long objsize;
2278
	void *buf = map_sha1_file(sha1, &objsize);
L
Linus Torvalds 已提交
2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289

	if (buf) {
		retval = write_buffer(fd, buf, objsize);
		munmap(buf, objsize);
		return retval;
	}

	buf = repack_object(sha1, &objsize);
	retval = write_buffer(fd, buf, objsize);
	free(buf);
	return retval;
D
Daniel Barkalow 已提交
2290 2291
}

2292 2293
int write_sha1_from_fd(const unsigned char *sha1, int fd, char *buffer,
		       size_t bufsize, size_t *bufposn)
2294
{
2295
	char tmpfile[PATH_MAX];
2296 2297 2298
	int local;
	z_stream stream;
	unsigned char real_sha1[20];
2299
	unsigned char discard[4096];
2300 2301 2302
	int ret;
	SHA_CTX c;

2303
	snprintf(tmpfile, sizeof(tmpfile), "%s/tmp_obj_XXXXXX", get_object_directory());
2304

2305
	local = mkstemp(tmpfile);
2306 2307 2308 2309 2310 2311
	if (local < 0) {
		if (errno == EPERM)
			return error("insufficient permission for adding an object to repository database %s\n", get_object_directory());
		else
			return error("unable to create temporary sha1 filename %s: %s\n", tmpfile, strerror(errno));
	}
2312 2313 2314 2315 2316 2317 2318 2319 2320

	memset(&stream, 0, sizeof(stream));

	inflateInit(&stream);

	SHA1_Init(&c);

	do {
		ssize_t size;
2321 2322
		if (*bufposn) {
			stream.avail_in = *bufposn;
P
Pavel Roskin 已提交
2323
			stream.next_in = (unsigned char *) buffer;
2324 2325 2326 2327 2328 2329 2330
			do {
				stream.next_out = discard;
				stream.avail_out = sizeof(discard);
				ret = inflate(&stream, Z_SYNC_FLUSH);
				SHA1_Update(&c, discard, sizeof(discard) -
					    stream.avail_out);
			} while (stream.avail_in && ret == Z_OK);
L
Linus Torvalds 已提交
2331 2332
			if (write_buffer(local, buffer, *bufposn - stream.avail_in) < 0)
				die("unable to write sha1 file");
2333 2334 2335 2336 2337 2338
			memmove(buffer, buffer + *bufposn - stream.avail_in,
				stream.avail_in);
			*bufposn = stream.avail_in;
			if (ret != Z_OK)
				break;
		}
2339
		size = xread(fd, buffer + *bufposn, bufsize - *bufposn);
2340 2341
		if (size <= 0) {
			close(local);
2342
			unlink(tmpfile);
2343 2344 2345 2346 2347
			if (!size)
				return error("Connection closed?");
			perror("Reading from connection");
			return -1;
		}
2348 2349
		*bufposn += size;
	} while (1);
2350 2351
	inflateEnd(&stream);

2352
	fchmod(local, 0444);
2353 2354
	if (close(local) != 0)
		die("unable to write sha1 file");
2355 2356
	SHA1_Final(real_sha1, &c);
	if (ret != Z_STREAM_END) {
2357
		unlink(tmpfile);
2358 2359
		return error("File %s corrupted", sha1_to_hex(sha1));
	}
2360
	if (hashcmp(sha1, real_sha1)) {
2361
		unlink(tmpfile);
2362
		return error("File %s has bad hash", sha1_to_hex(sha1));
2363
	}
2364 2365

	return move_temp_to_file(tmpfile, sha1_file_name(sha1));
2366 2367
}

2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383
int has_pack_index(const unsigned char *sha1)
{
	struct stat st;
	if (stat(sha1_pack_index_name(sha1), &st))
		return 0;
	return 1;
}

int has_pack_file(const unsigned char *sha1)
{
	struct stat st;
	if (stat(sha1_pack_name(sha1), &st))
		return 0;
	return 1;
}

2384
int has_sha1_pack(const unsigned char *sha1, const char **ignore_packed)
2385 2386
{
	struct pack_entry e;
2387
	return find_pack_entry(sha1, &e, ignore_packed);
2388 2389
}

2390 2391 2392
int has_sha1_file(const unsigned char *sha1)
{
	struct stat st;
2393 2394
	struct pack_entry e;

2395
	if (find_pack_entry(sha1, &e, NULL))
2396
		return 1;
2397
	return find_sha1_file(sha1, &st) ? 1 : 0;
2398
}
J
Junio C Hamano 已提交
2399

2400 2401
int index_pipe(unsigned char *sha1, int fd, const char *type, int write_object)
{
2402
	struct strbuf buf;
2403 2404
	int ret;

2405 2406 2407
	strbuf_init(&buf, 0);
	if (strbuf_read(&buf, fd, 4096) < 0) {
		strbuf_release(&buf);
2408 2409
		return -1;
	}
2410

2411
	if (!type)
2412
		type = blob_type;
2413
	if (write_object)
2414
		ret = write_sha1_file(buf.buf, buf.len, type, sha1);
R
Rene Scharfe 已提交
2415
	else
2416 2417 2418
		ret = hash_sha1_file(buf.buf, buf.len, type, sha1);
	strbuf_release(&buf);

2419 2420 2421
	return ret;
}

2422
int index_fd(unsigned char *sha1, int fd, struct stat *st, int write_object,
2423
	     enum object_type type, const char *path)
J
Junio C Hamano 已提交
2424
{
2425
	size_t size = xsize_t(st->st_size);
2426
	void *buf = NULL;
L
Linus Torvalds 已提交
2427
	int ret, re_allocated = 0;
J
Junio C Hamano 已提交
2428 2429

	if (size)
2430
		buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
J
Junio C Hamano 已提交
2431 2432
	close(fd);

2433
	if (!type)
2434
		type = OBJ_BLOB;
L
Linus Torvalds 已提交
2435 2436 2437 2438

	/*
	 * Convert blobs to git internal format
	 */
2439
	if ((type == OBJ_BLOB) && S_ISREG(st->st_mode)) {
2440 2441
		struct strbuf nbuf;
		strbuf_init(&nbuf, 0);
2442 2443
		if (convert_to_git(path, buf, size, &nbuf,
		                   write_object ? safe_crlf : 0)) {
2444
			munmap(buf, size);
2445
			buf = strbuf_detach(&nbuf, &size);
L
Linus Torvalds 已提交
2446 2447 2448 2449
			re_allocated = 1;
		}
	}

2450
	if (write_object)
2451
		ret = write_sha1_file(buf, size, typename(type), sha1);
R
Rene Scharfe 已提交
2452
	else
2453
		ret = hash_sha1_file(buf, size, typename(type), sha1);
L
Linus Torvalds 已提交
2454 2455 2456 2457
	if (re_allocated) {
		free(buf);
		return ret;
	}
2458 2459 2460
	if (size)
		munmap(buf, size);
	return ret;
J
Junio C Hamano 已提交
2461
}
2462 2463 2464 2465 2466

int index_path(unsigned char *sha1, const char *path, struct stat *st, int write_object)
{
	int fd;
	char *target;
2467
	size_t len;
2468 2469 2470 2471 2472 2473 2474

	switch (st->st_mode & S_IFMT) {
	case S_IFREG:
		fd = open(path, O_RDONLY);
		if (fd < 0)
			return error("open(\"%s\"): %s", path,
				     strerror(errno));
2475
		if (index_fd(sha1, fd, st, write_object, OBJ_BLOB, path) < 0)
2476 2477 2478 2479
			return error("%s: failed to insert into database",
				     path);
		break;
	case S_IFLNK:
2480 2481 2482
		len = xsize_t(st->st_size);
		target = xmalloc(len + 1);
		if (readlink(path, target, len + 1) != st->st_size) {
2483 2484 2485 2486 2487
			char *errstr = strerror(errno);
			free(target);
			return error("readlink(\"%s\"): %s", path,
			             errstr);
		}
R
Rene Scharfe 已提交
2488
		if (!write_object)
2489 2490
			hash_sha1_file(target, len, blob_type, sha1);
		else if (write_sha1_file(target, len, blob_type, sha1))
2491 2492 2493 2494
			return error("%s: failed to insert into database",
				     path);
		free(target);
		break;
2495 2496
	case S_IFDIR:
		return resolve_gitlink_ref(path, "HEAD", sha1);
2497 2498 2499 2500 2501
	default:
		return error("%s: unsupported file type", path);
	}
	return 0;
}
2502 2503 2504

int read_pack_header(int fd, struct pack_header *header)
{
2505 2506 2507 2508
	if (read_in_full(fd, header, sizeof(*header)) < sizeof(*header))
		/* "eof before pack header was fully read" */
		return PH_ERROR_EOF;

2509 2510 2511 2512 2513 2514 2515 2516
	if (header->hdr_signature != htonl(PACK_SIGNATURE))
		/* "protocol error (pack signature mismatch detected)" */
		return PH_ERROR_PACK_SIGNATURE;
	if (!pack_version_ok(header->hdr_version))
		/* "protocol error (pack version unsupported)" */
		return PH_ERROR_PROTOCOL;
	return 0;
}