pack.c 32.6 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
3
 *
Vicent Marti committed
4 5
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
6 7
 */

8
#include "common.h"
9 10
#include "odb.h"
#include "pack.h"
11
#include "delta.h"
12
#include "sha1_lookup.h"
13 14
#include "mwindow.h"
#include "fileops.h"
15
#include "oid.h"
16

17
#include <zlib.h>
18

19
static int packfile_open(struct git_pack_file *p);
20
static git_off_t nth_packed_object_offset(const struct git_pack_file *p, uint32_t n);
21
static int packfile_unpack_compressed(
22 23 24
		git_rawobj *obj,
		struct git_pack_file *p,
		git_mwindow **w_curs,
25
		git_off_t *curpos,
26 27 28 29 30
		size_t size,
		git_otype type);

/* Can find the offset of an object given
 * a prefix of an identifier.
31
 * Throws GIT_EAMBIGUOUSOIDPREFIX if short oid
32 33 34 35 36
 * is ambiguous within the pack.
 * This method assumes that len is between
 * GIT_OID_MINPREFIXLEN and GIT_OID_HEXSZ.
 */
static int pack_entry_find_offset(
37
		git_off_t *offset_out,
38 39 40
		git_oid *found_oid,
		struct git_pack_file *p,
		const git_oid *short_oid,
41
		size_t len);
42

43 44
static int packfile_error(const char *message)
{
45
	giterr_set(GITERR_ODB, "invalid pack file - %s", message);
46 47 48
	return -1;
}

49 50 51
/********************
 * Delta base cache
 ********************/
52

53
static git_pack_cache_entry *new_cache_object(git_rawobj *source)
54
{
55
	git_pack_cache_entry *e = git__calloc(1, sizeof(git_pack_cache_entry));
56 57 58
	if (!e)
		return NULL;

59
	git_atomic_inc(&e->refcount);
60 61 62 63 64 65 66 67 68 69
	memcpy(&e->raw, source, sizeof(git_rawobj));

	return e;
}

static void free_cache_object(void *o)
{
	git_pack_cache_entry *e = (git_pack_cache_entry *)o;

	if (e != NULL) {
70
		assert(e->refcount.val == 0);
71 72 73 74 75
		git__free(e->raw.data);
		git__free(e);
	}
}

76 77
static void cache_free(git_pack_cache *cache)
{
78
	git_pack_cache_entry *entry;
79 80

	if (cache->entries) {
81 82 83
		git_offmap_foreach_value(cache->entries, entry, {
			free_cache_object(entry);
		});
84 85

		git_offmap_free(cache->entries);
86
		cache->entries = NULL;
87 88 89 90 91 92 93
	}
}

static int cache_init(git_pack_cache *cache)
{
	cache->entries = git_offmap_alloc();
	GITERR_CHECK_ALLOC(cache->entries);
94

95
	cache->memory_limit = GIT_PACK_CACHE_MEMORY_LIMIT;
Russell Belfer committed
96 97

	if (git_mutex_init(&cache->lock)) {
98
		giterr_set(GITERR_OS, "failed to initialize pack cache mutex");
Russell Belfer committed
99 100 101 102 103 104

		git__free(cache->entries);
		cache->entries = NULL;

		return -1;
	}
105 106 107 108

	return 0;
}

109
static git_pack_cache_entry *cache_get(git_pack_cache *cache, git_off_t offset)
110 111 112 113
{
	khiter_t k;
	git_pack_cache_entry *entry = NULL;

114 115 116
	if (git_mutex_lock(&cache->lock) < 0)
		return NULL;

117
	k = git_offmap_lookup_index(cache->entries, offset);
118
	if (git_offmap_valid_index(cache->entries, k)) { /* found it */
119
		entry = git_offmap_value_at(cache->entries, k);
120
		git_atomic_inc(&entry->refcount);
121
		entry->last_usage = cache->use_ctr++;
122 123 124 125 126 127
	}
	git_mutex_unlock(&cache->lock);

	return entry;
}

128 129 130
/* Run with the cache lock held */
static void free_lowest_entry(git_pack_cache *cache)
{
131
	git_off_t offset;
132 133
	git_pack_cache_entry *entry;

134
	git_offmap_foreach(cache->entries, offset, entry, {
135 136
		if (entry && entry->refcount.val == 0) {
			cache->memory_used -= entry->raw.len;
137
			git_offmap_delete(cache->entries, offset);
138
			free_cache_object(entry);
139
		}
140
	});
141 142
}

143 144 145 146 147
static int cache_add(
		git_pack_cache_entry **cached_out,
		git_pack_cache *cache,
		git_rawobj *base,
		git_off_t offset)
148 149 150 151 152
{
	git_pack_cache_entry *entry;
	int error, exists = 0;
	khiter_t k;

153 154 155
	if (base->len > GIT_PACK_CACHE_SIZE_LIMIT)
		return -1;

156 157
	entry = new_cache_object(base);
	if (entry) {
158 159
		if (git_mutex_lock(&cache->lock) < 0) {
			giterr_set(GITERR_OS, "failed to lock cache");
Jacques Germishuys committed
160
			git__free(entry);
161 162
			return -1;
		}
163
		/* Add it to the cache if nobody else has */
164
		exists = git_offmap_exists(cache->entries, offset);
165
		if (!exists) {
166 167 168
			while (cache->memory_used + base->len > cache->memory_limit)
				free_lowest_entry(cache);

169
			k = git_offmap_put(cache->entries, offset, &error);
170
			assert(error != 0);
171
			git_offmap_set_value_at(cache->entries, k, entry);
172
			cache->memory_used += entry->raw.len;
173 174

			*cached_out = entry;
175 176 177 178 179 180 181 182 183 184 185 186
		}
		git_mutex_unlock(&cache->lock);
		/* Somebody beat us to adding it into the cache */
		if (exists) {
			git__free(entry);
			return -1;
		}
	}

	return 0;
}

187 188 189 190 191 192 193 194
/***********************************************************
 *
 * PACK INDEX METHODS
 *
 ***********************************************************/

static void pack_index_free(struct git_pack_file *p)
{
195 196 197 198
	if (p->oids) {
		git__free(p->oids);
		p->oids = NULL;
	}
199 200 201 202 203 204
	if (p->index_map.data) {
		git_futils_mmap_free(&p->index_map);
		p->index_map.data = NULL;
	}
}

Vicent Marti committed
205
static int pack_index_check(const char *path, struct git_pack_file *p)
206 207 208 209 210 211 212
{
	struct git_pack_idx_header *hdr;
	uint32_t version, nr, i, *index;
	void *idx_map;
	size_t idx_size;
	struct stat st;
	int error;
213 214
	/* TODO: properly open the file without access time using O_NOATIME */
	git_file fd = git_futils_open_ro(path);
215
	if (fd < 0)
216
		return fd;
217

218 219
	if (p_fstat(fd, &st) < 0) {
		p_close(fd);
220
		giterr_set(GITERR_OS, "unable to stat pack index '%s'", path);
221 222 223 224
		return -1;
	}

	if (!S_ISREG(st.st_mode) ||
225 226 227
		!git__is_sizet(st.st_size) ||
		(idx_size = (size_t)st.st_size) < 4 * 256 + 20 + 20)
	{
228
		p_close(fd);
229
		giterr_set(GITERR_ODB, "invalid pack index '%s'", path);
230
		return -1;
231 232 233
	}

	error = git_futils_mmap_ro(&p->index_map, fd, 0, idx_size);
234

235 236
	p_close(fd);

237 238
	if (error < 0)
		return error;
239 240 241 242 243 244 245 246

	hdr = idx_map = p->index_map.data;

	if (hdr->idx_signature == htonl(PACK_IDX_SIGNATURE)) {
		version = ntohl(hdr->idx_version);

		if (version < 2 || version > 2) {
			git_futils_mmap_free(&p->index_map);
247
			return packfile_error("unsupported index version");
248 249 250 251 252 253 254 255 256
		}

	} else
		version = 1;

	nr = 0;
	index = idx_map;

	if (version > 1)
Vicent Marti committed
257
		index += 2; /* skip index header */
258 259 260 261 262

	for (i = 0; i < 256; i++) {
		uint32_t n = ntohl(index[i]);
		if (n < nr) {
			git_futils_mmap_free(&p->index_map);
263
			return packfile_error("index is non-monotonic");
264 265 266 267 268 269 270
		}
		nr = n;
	}

	if (version == 1) {
		/*
		 * Total size:
Vicent Marti committed
271 272 273 274
		 * - 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
275 276 277
		 */
		if (idx_size != 4*256 + nr * 24 + 20 + 20) {
			git_futils_mmap_free(&p->index_map);
278
			return packfile_error("index is corrupted");
279 280 281 282
		}
	} else if (version == 2) {
		/*
		 * Minimum size:
Vicent Marti committed
283 284 285 286 287 288 289
		 * - 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
290 291 292 293 294 295 296 297 298 299 300 301
		 * 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;
		unsigned long max_size = min_size;

		if (nr)
			max_size += (nr - 1)*8;

		if (idx_size < min_size || idx_size > max_size) {
			git_futils_mmap_free(&p->index_map);
302
			return packfile_error("wrong index size");
303 304 305 306
		}
	}

	p->num_objects = nr;
307
	p->index_version = version;
308
	return 0;
309 310 311 312
}

static int pack_index_open(struct git_pack_file *p)
{
313
	int error = 0;
314
	size_t name_len;
315
	git_buf idx_name;
316

317
	if (p->index_version > -1)
Russell Belfer committed
318
		return 0;
319

320 321
	name_len = strlen(p->pack_name);
	assert(name_len > strlen(".pack")); /* checked by git_pack_file alloc */
322

323 324 325
	if (git_buf_init(&idx_name, name_len) < 0)
		return -1;

326 327 328
	git_buf_put(&idx_name, p->pack_name, name_len - strlen(".pack"));
	git_buf_puts(&idx_name, ".idx");
	if (git_buf_oom(&idx_name)) {
329
		git_buf_free(&idx_name);
Russell Belfer committed
330
		return -1;
331
	}
332

333
	if ((error = git_mutex_lock(&p->lock)) < 0) {
334
		git_buf_free(&idx_name);
Russell Belfer committed
335
		return error;
336
	}
Russell Belfer committed
337

338
	if (p->index_version == -1)
339
		error = pack_index_check(idx_name.ptr, p);
340

341
	git_buf_free(&idx_name);
342

343 344
	git_mutex_unlock(&p->lock);

345
	return error;
346 347 348 349
}

static unsigned char *pack_window_open(
		struct git_pack_file *p,
350
		git_mwindow **w_cursor,
351
		git_off_t offset,
352 353
		unsigned int *left)
{
354
	if (p->mwf.fd == -1 && packfile_open(p) < 0)
355 356 357 358 359 360
		return NULL;

	/* Since packfiles end in a hash of their content and it's
	 * pointless to ask for an offset into the middle of that
	 * hash, and the pack_window_contains function above wouldn't match
	 * don't allow an offset too close to the end of the file.
361 362 363
	 *
	 * Don't allow a negative offset, as that means we've wrapped
	 * around.
364 365 366
	 */
	if (offset > (p->mwf.size - 20))
		return NULL;
367 368
	if (offset < 0)
		return NULL;
369 370 371 372

	return git_mwindow_open(&p->mwf, w_cursor, offset, 20, left);
 }

373 374 375 376 377 378 379 380
/*
 * The per-object header is a pretty dense thing, which is
 *  - first byte: low four bits are "size",
 *    then three bits of "type",
 *    with the high bit being "size continues".
 *  - each byte afterwards: low seven bits are size continuation,
 *    with the high bit being "size continues"
 */
381
size_t git_packfile__object_header(unsigned char *hdr, size_t size, git_otype type)
382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400
{
	unsigned char *hdr_base;
	unsigned char c;

	assert(type >= GIT_OBJ_COMMIT && type <= GIT_OBJ_REF_DELTA);

	/* TODO: add support for chunked objects; see git.git 6c0d19b1 */

	c = (unsigned char)((type << 4) | (size & 15));
	size >>= 4;
	hdr_base = hdr;

	while (size) {
		*hdr++ = c | 0x80;
		c = size & 0x7f;
		size >>= 7;
	}
	*hdr++ = c;

401
	return (hdr - hdr_base);
402 403 404
}


405 406
static int packfile_unpack_header1(
		unsigned long *usedp,
407 408 409 410 411 412 413 414
		size_t *sizep,
		git_otype *type,
		const unsigned char *buf,
		unsigned long len)
{
	unsigned shift;
	unsigned long size, c;
	unsigned long used = 0;
415

416 417 418 419 420
	c = buf[used++];
	*type = (c >> 4) & 7;
	size = c & 15;
	shift = 4;
	while (c & 0x80) {
421 422
		if (len <= used) {
			giterr_set(GITERR_ODB, "buffer too small");
423
			return GIT_EBUFS;
424
		}
425 426 427

		if (bitsizeof(long) <= shift) {
			*usedp = 0;
428
			giterr_set(GITERR_ODB, "packfile corrupted");
429 430
			return -1;
		}
431 432 433 434 435 436 437

		c = buf[used++];
		size += (c & 0x7f) << shift;
		shift += 7;
	}

	*sizep = (size_t)size;
438 439
	*usedp = used;
	return 0;
440 441 442 443 444 445 446
}

int git_packfile_unpack_header(
		size_t *size_p,
		git_otype *type_p,
		git_mwindow_file *mwf,
		git_mwindow **w_curs,
447
		git_off_t *curpos)
448 449 450 451
{
	unsigned char *base;
	unsigned int left;
	unsigned long used;
452
	int ret;
453 454

	/* pack_window_open() assures us we have [base, base + 20) available
Vicent Marti committed
455 456
	 * as a range that we can look at at. (Its actually the hash
	 * size that is assured.) With our object header encoding
457 458 459
	 * the maximum deflated object size is 2^137, which is just
	 * insane, so we know won't exceed what we have been given.
	 */
460
/*	base = pack_window_open(p, w_curs, *curpos, &left); */
461 462
	base = git_mwindow_open(mwf, w_curs, *curpos, 20, &left);
	if (base == NULL)
463
		return GIT_EBUFS;
464

465
	ret = packfile_unpack_header1(&used, size_p, type_p, base, left);
466
	git_mwindow_close(w_curs);
467
	if (ret == GIT_EBUFS)
468 469
		return ret;
	else if (ret < 0)
470
		return packfile_error("header length is zero");
471 472

	*curpos += used;
473
	return 0;
474 475
}

476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494
int git_packfile_resolve_header(
		size_t *size_p,
		git_otype *type_p,
		struct git_pack_file *p,
		git_off_t offset)
{
	git_mwindow *w_curs = NULL;
	git_off_t curpos = offset;
	size_t size;
	git_otype type;
	git_off_t base_offset;
	int error;

	error = git_packfile_unpack_header(&size, &type, &p->mwf, &w_curs, &curpos);
	if (error < 0)
		return error;

	if (type == GIT_OBJ_OFS_DELTA || type == GIT_OBJ_REF_DELTA) {
		size_t base_size;
495 496
		git_packfile_stream stream;

497 498
		base_offset = get_delta_base(p, &w_curs, &curpos, type, offset);
		git_mwindow_close(&w_curs);
499
		if ((error = git_packfile_stream_open(&stream, p, curpos)) < 0)
500
			return error;
501
		error = git_delta_read_header_fromstream(&base_size, size_p, &stream);
502
		git_packfile_stream_free(&stream);
503 504
		if (error < 0)
			return error;
505
	} else {
506
		*size_p = size;
507 508
		base_offset = 0;
	}
509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524

	while (type == GIT_OBJ_OFS_DELTA || type == GIT_OBJ_REF_DELTA) {
		curpos = base_offset;
		error = git_packfile_unpack_header(&size, &type, &p->mwf, &w_curs, &curpos);
		if (error < 0)
			return error;
		if (type != GIT_OBJ_OFS_DELTA && type != GIT_OBJ_REF_DELTA)
			break;
		base_offset = get_delta_base(p, &w_curs, &curpos, type, base_offset);
		git_mwindow_close(&w_curs);
	}
	*type_p = type;

	return error;
}

525 526
#define SMALL_STACK_SIZE 64

527 528 529 530 531 532
/**
 * Generate the chain of dependencies which we need to get to the
 * object at `off`. `chain` is used a stack, popping gives the right
 * order to apply deltas on. If an object is found in the pack's base
 * cache, we stop calculating there.
 */
533 534 535 536
static int pack_dependency_chain(git_dependency_chain *chain_out,
				 git_pack_cache_entry **cached_out, git_off_t *cached_off,
				 struct pack_chain_elem *small_stack, size_t *stack_sz,
				 struct git_pack_file *p, git_off_t obj_offset)
537 538 539 540
{
	git_dependency_chain chain = GIT_ARRAY_INIT;
	git_mwindow *w_curs = NULL;
	git_off_t curpos = obj_offset, base_offset;
541 542
	int error = 0, use_heap = 0;
	size_t size, elem_pos;
543 544
	git_otype type;

545
	elem_pos = 0;
546 547 548 549 550 551 552 553 554 555 556
	while (true) {
		struct pack_chain_elem *elem;
		git_pack_cache_entry *cached = NULL;

		/* if we have a base cached, we can stop here instead */
		if ((cached = cache_get(&p->bases, obj_offset)) != NULL) {
			*cached_out = cached;
			*cached_off = obj_offset;
			break;
		}

557 558 559 560 561 562 563 564 565
		/* if we run out of space on the small stack, use the array */
		if (elem_pos == SMALL_STACK_SIZE) {
			git_array_init_to_size(chain, elem_pos);
			GITERR_CHECK_ARRAY(chain);
			memcpy(chain.ptr, small_stack, elem_pos * sizeof(struct pack_chain_elem));
			chain.size = elem_pos;
			use_heap = 1;
		}

566
		curpos = obj_offset;
567 568 569 570 571 572 573 574
		if (!use_heap) {
			elem = &small_stack[elem_pos];
		} else {
			elem = git_array_alloc(chain);
			if (!elem) {
				error = -1;
				goto on_error;
			}
575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608
		}

		elem->base_key = obj_offset;

		error = git_packfile_unpack_header(&size, &type, &p->mwf, &w_curs, &curpos);

		if (error < 0)
			goto on_error;

		elem->offset = curpos;
		elem->size = size;
		elem->type = type;
		elem->base_key = obj_offset;

		if (type != GIT_OBJ_OFS_DELTA && type != GIT_OBJ_REF_DELTA)
			break;

		base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
		git_mwindow_close(&w_curs);

		if (base_offset == 0) {
			error = packfile_error("delta offset is zero");
			goto on_error;
		}
		if (base_offset < 0) { /* must actually be an error code */
			error = (int)base_offset;
			goto on_error;
		}

		/* we need to pass the pos *after* the delta-base bit */
		elem->offset = curpos;

		/* go through the loop again, but with the new object */
		obj_offset = base_offset;
609
		elem_pos++;
610 611
	}

612 613
	
	*stack_sz = elem_pos + 1;
614 615 616 617 618 619 620 621
	*chain_out = chain;
	return error;

on_error:
	git_array_clear(chain);
	return error;
}

622
int git_packfile_unpack(
623 624 625
	git_rawobj *obj,
	struct git_pack_file *p,
	git_off_t *obj_offset)
626 627
{
	git_mwindow *w_curs = NULL;
628
	git_off_t curpos = *obj_offset;
629 630
	int error, free_base = 0;
	git_dependency_chain chain = GIT_ARRAY_INIT;
631
	struct pack_chain_elem *elem = NULL, *stack;
632
	git_pack_cache_entry *cached = NULL;
633
	struct pack_chain_elem small_stack[SMALL_STACK_SIZE];
634
	size_t stack_size = 0, elem_pos, alloclen;
635
	git_otype base_type;
636 637 638 639 640

	/*
	 * TODO: optionally check the CRC on the packfile
	 */

641
	error = pack_dependency_chain(&chain, &cached, obj_offset, small_stack, &stack_size, p, *obj_offset);
642 643 644
	if (error < 0)
		return error;

645 646 647 648
	obj->data = NULL;
	obj->len = 0;
	obj->type = GIT_OBJ_BAD;

649 650 651 652
	/* let's point to the right stack */
	stack = chain.ptr ? chain.ptr : small_stack;

	elem_pos = stack_size;
653
	if (cached) {
654
		memcpy(obj, &cached->raw, sizeof(git_rawobj));
655
		base_type = obj->type;
656
		elem_pos--;	/* stack_size includes the base, which isn't actually there */
657
	} else {
658
		elem = &stack[--elem_pos];
659
		base_type = elem->type;
660
	}
661

662 663 664 665 666
	switch (base_type) {
	case GIT_OBJ_COMMIT:
	case GIT_OBJ_TREE:
	case GIT_OBJ_BLOB:
	case GIT_OBJ_TAG:
667
		if (!cached) {
668 669 670
			curpos = elem->offset;
			error = packfile_unpack_compressed(obj, p, &w_curs, &curpos, elem->size, elem->type);
			git_mwindow_close(&w_curs);
671
			base_type = elem->type;
672 673 674 675 676 677 678 679 680 681 682 683 684
		}
		if (error < 0)
			goto cleanup;
		break;
	case GIT_OBJ_OFS_DELTA:
	case GIT_OBJ_REF_DELTA:
		error = packfile_error("dependency chain ends in a delta");
		goto cleanup;
	default:
		error = packfile_error("invalid packfile type in header");
		goto cleanup;
	}

685
	/*
686
	 * Finding the object we want a cached base element is
687 688 689 690
	 * problematic, as we need to make sure we don't accidentally
	 * give the caller the cached object, which it would then feel
	 * free to free, so we need to copy the data.
	 */
691
	if (cached && stack_size == 1) {
692
		void *data = obj->data;
693

694 695
		GITERR_CHECK_ALLOC_ADD(&alloclen, obj->len, 1);
		obj->data = git__malloc(alloclen);
696
		GITERR_CHECK_ALLOC(obj->data);
697

698 699 700 701 702
		memcpy(obj->data, data, obj->len + 1);
		git_atomic_dec(&cached->refcount);
		goto cleanup;
	}

703
	/* we now apply each consecutive delta until we run out */
704
	while (elem_pos > 0 && !error) {
705 706
		git_rawobj base, delta;

707 708 709 710 711
		/*
		 * We can now try to add the base to the cache, as
		 * long as it's not already the cached one.
		 */
		if (!cached)
712
			free_base = !!cache_add(&cached, &p->bases, obj, elem->base_key);
713

714
		elem = &stack[elem_pos - 1];
715 716 717 718 719 720 721 722 723 724 725 726 727
		curpos = elem->offset;
		error = packfile_unpack_compressed(&delta, p, &w_curs, &curpos, elem->size, elem->type);
		git_mwindow_close(&w_curs);

		if (error < 0)
			break;

		/* the current object becomes the new base, on which we apply the delta */
		base = *obj;
		obj->data = NULL;
		obj->len = 0;
		obj->type = GIT_OBJ_BAD;

728
		error = git_delta_apply(&obj->data, &obj->len, base.data, base.len, delta.data, delta.len);
729
		obj->type = base_type;
730

731 732 733 734 735 736
		/*
		 * We usually don't want to free the base at this
		 * point, as we put it into the cache in the previous
		 * iteration. free_base lets us know that we got the
		 * base object directly from the packfile, so we can free it.
		 */
737
		git__free(delta.data);
738 739 740 741 742 743 744 745 746
		if (free_base) {
			free_base = 0;
			git__free(base.data);
		}

		if (cached) {
			git_atomic_dec(&cached->refcount);
			cached = NULL;
		}
747 748 749

		if (error < 0)
			break;
750

751
		elem_pos--;
752 753
	}

754
cleanup:
755
	if (error < 0) {
756
		git__free(obj->data);
757 758 759
		if (cached)
			git_atomic_dec(&cached->refcount);
	}
760

761
	if (elem)
762
		*obj_offset = curpos;
763

764
	git_array_clear(chain);
765
	return error;
766 767
}

Russell Belfer committed
768 769 770 771 772 773 774 775 776 777 778 779
static void *use_git_alloc(void *opaq, unsigned int count, unsigned int size)
{
	GIT_UNUSED(opaq);
	return git__calloc(count, size);
}

static void use_git_free(void *opaq, void *ptr)
{
	GIT_UNUSED(opaq);
	git__free(ptr);
}

780 781 782 783 784 785 786 787 788 789 790 791 792
int git_packfile_stream_open(git_packfile_stream *obj, struct git_pack_file *p, git_off_t curpos)
{
	int st;

	memset(obj, 0, sizeof(git_packfile_stream));
	obj->curpos = curpos;
	obj->p = p;
	obj->zstream.zalloc = use_git_alloc;
	obj->zstream.zfree = use_git_free;
	obj->zstream.next_in = Z_NULL;
	obj->zstream.next_out = Z_NULL;
	st = inflateInit(&obj->zstream);
	if (st != Z_OK) {
793
		giterr_set(GITERR_ZLIB, "failed to init packfile stream");
794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813
		return -1;
	}

	return 0;
}

ssize_t git_packfile_stream_read(git_packfile_stream *obj, void *buffer, size_t len)
{
	unsigned char *in;
	size_t written;
	int st;

	if (obj->done)
		return 0;

	in = pack_window_open(obj->p, &obj->mw, obj->curpos, &obj->zstream.avail_in);
	if (in == NULL)
		return GIT_EBUFS;

	obj->zstream.next_out = buffer;
814
	obj->zstream.avail_out = (unsigned int)len;
815 816 817 818 819 820 821 822 823
	obj->zstream.next_in = in;

	st = inflate(&obj->zstream, Z_SYNC_FLUSH);
	git_mwindow_close(&obj->mw);

	obj->curpos += obj->zstream.next_in - in;
	written = len - obj->zstream.avail_out;

	if (st != Z_OK && st != Z_STREAM_END) {
824
		giterr_set(GITERR_ZLIB, "error reading from the zlib stream");
825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844
		return -1;
	}

	if (st == Z_STREAM_END)
		obj->done = 1;


	/* If we didn't write anything out but we're not done, we need more data */
	if (!written && st != Z_STREAM_END)
		return GIT_EBUFS;

	return written;

}

void git_packfile_stream_free(git_packfile_stream *obj)
{
	inflateEnd(&obj->zstream);
}

845
static int packfile_unpack_compressed(
846 847 848 849 850 851
	git_rawobj *obj,
	struct git_pack_file *p,
	git_mwindow **w_curs,
	git_off_t *curpos,
	size_t size,
	git_otype type)
852
{
853
	size_t buf_size;
854 855 856 857
	int st;
	z_stream stream;
	unsigned char *buffer, *in;

858 859
	GITERR_CHECK_ALLOC_ADD(&buf_size, size, 1);
	buffer = git__calloc(1, buf_size);
860
	GITERR_CHECK_ALLOC(buffer);
861 862 863

	memset(&stream, 0, sizeof(stream));
	stream.next_out = buffer;
864
	stream.avail_out = (uInt)buf_size;
Russell Belfer committed
865 866
	stream.zalloc = use_git_alloc;
	stream.zfree = use_git_free;
867 868 869

	st = inflateInit(&stream);
	if (st != Z_OK) {
870
		git__free(buffer);
871
		giterr_set(GITERR_ZLIB, "failed to init zlib stream on unpack");
872

873
		return -1;
874 875 876
	}

	do {
877
		in = pack_window_open(p, w_curs, *curpos, &stream.avail_in);
878 879
		stream.next_in = in;
		st = inflate(&stream, Z_FINISH);
880
		git_mwindow_close(w_curs);
881 882 883 884

		if (!stream.avail_out)
			break; /* the payload is larger than it should be */

885 886 887
		if (st == Z_BUF_ERROR && in == NULL) {
			inflateEnd(&stream);
			git__free(buffer);
888
			return GIT_EBUFS;
889 890
		}

891
		*curpos += stream.next_in - in;
892 893 894 895 896
	} while (st == Z_OK || st == Z_BUF_ERROR);

	inflateEnd(&stream);

	if ((st != Z_STREAM_END) || stream.total_out != size) {
897
		git__free(buffer);
898
		giterr_set(GITERR_ZLIB, "error inflating zlib stream");
899
		return -1;
900 901 902 903 904
	}

	obj->type = type;
	obj->len = size;
	obj->data = buffer;
905
	return 0;
906 907
}

908 909 910 911
/*
 * curpos is where the data starts, delta_obj_offset is the where the
 * header starts
 */
912 913 914 915 916 917
git_off_t get_delta_base(
	struct git_pack_file *p,
	git_mwindow **w_curs,
	git_off_t *curpos,
	git_otype type,
	git_off_t delta_obj_offset)
918
{
919 920
	unsigned int left = 0;
	unsigned char *base_info;
921
	git_off_t base_offset;
922 923
	git_oid unused;

924 925 926
	base_info = pack_window_open(p, w_curs, *curpos, &left);
	/* Assumption: the only reason this would fail is because the file is too small */
	if (base_info == NULL)
927
		return GIT_EBUFS;
928 929
	/* pack_window_open() assured us we have [base_info, base_info + 20)
	 * as a range that we can look at without walking off the
Vicent Marti committed
930 931
	 * end of the mapped window. Its actually the hash size
	 * that is assured. An OFS_DELTA longer than the hash size
932 933 934 935 936 937 938
	 * is stupid, as then a REF_DELTA would be smaller to store.
	 */
	if (type == GIT_OBJ_OFS_DELTA) {
		unsigned used = 0;
		unsigned char c = base_info[used++];
		base_offset = c & 127;
		while (c & 128) {
939
			if (left <= used)
940
				return GIT_EBUFS;
941 942
			base_offset += 1;
			if (!base_offset || MSB(base_offset, 7))
Vicent Marti committed
943
				return 0; /* overflow */
944 945 946 947 948
			c = base_info[used++];
			base_offset = (base_offset << 7) + (c & 127);
		}
		base_offset = delta_obj_offset - base_offset;
		if (base_offset <= 0 || base_offset >= delta_obj_offset)
Vicent Marti committed
949
			return 0; /* out of bound */
950 951
		*curpos += used;
	} else if (type == GIT_OBJ_REF_DELTA) {
952 953
		/* If we have the cooperative cache, search in it first */
		if (p->has_cache) {
954 955
			khiter_t k;
			git_oid oid;
956

957
			git_oid_fromraw(&oid, base_info);
958
			k = git_oidmap_lookup_index(p->idx_cache, &oid);
959
			if (git_oidmap_valid_index(p->idx_cache, k)) {
960
				*curpos += 20;
961
				return ((struct git_pack_entry *)git_oidmap_value_at(p->idx_cache, k))->offset;
962 963 964 965 966 967
			} else {
				/* If we're building an index, don't try to find the pack
				 * entry; we just haven't seen it yet.  We'll make
				 * progress again in the next loop.
				 */
				return GIT_PASSTHROUGH;
968 969
			}
		}
970

971
		/* The base entry _must_ be in the same pack */
972 973
		if (pack_entry_find_offset(&base_offset, &unused, p, (git_oid *)base_info, GIT_OID_HEXSZ) < 0)
			return packfile_error("base entry delta is not in the same pack");
974 975 976 977 978 979
		*curpos += 20;
	} else
		return 0;

	return base_offset;
}
980 981 982 983 984 985 986

/***********************************************************
 *
 * PACKFILE METHODS
 *
 ***********************************************************/

987 988 989 990 991 992 993 994 995 996 997 998
void git_packfile_close(struct git_pack_file *p, bool unlink_packfile)
{
	if (p->mwf.fd >= 0) {
		git_mwindow_free_all_locked(&p->mwf);
		p_close(p->mwf.fd);
		p->mwf.fd = -1;
	}

	if (unlink_packfile)
		p_unlink(p->pack_name);
}

999
void git_packfile_free(struct git_pack_file *p)
1000
{
1001 1002 1003
	if (!p)
		return;

1004
	cache_free(&p->bases);
1005

1006
	git_packfile_close(p, false);
1007 1008 1009

	pack_index_free(p);

1010
	git__free(p->bad_object_sha1);
1011 1012

	git_mutex_free(&p->lock);
1013
	git_mutex_free(&p->bases.lock);
1014
	git__free(p);
1015 1016 1017 1018 1019 1020 1021 1022 1023
}

static int packfile_open(struct git_pack_file *p)
{
	struct stat st;
	struct git_pack_header hdr;
	git_oid sha1;
	unsigned char *idx_sha1;

1024
	if (p->index_version == -1 && pack_index_open(p) < 0)
1025
		return git_odb__error_notfound("failed to open packfile", NULL, 0);
1026

1027 1028 1029 1030 1031 1032 1033 1034 1035
	/* if mwf opened by another thread, return now */
	if (git_mutex_lock(&p->lock) < 0)
		return packfile_error("failed to get lock for open");

	if (p->mwf.fd >= 0) {
		git_mutex_unlock(&p->lock);
		return 0;
	}

1036
	/* TODO: open with noatime */
1037
	p->mwf.fd = git_futils_open_ro(p->pack_name);
1038 1039
	if (p->mwf.fd < 0)
		goto cleanup;
1040

1041 1042 1043
	if (p_fstat(p->mwf.fd, &st) < 0 ||
		git_mwindow_file_register(&p->mwf) < 0)
		goto cleanup;
1044 1045 1046 1047 1048

	/* If we created the struct before we had the pack we lack size. */
	if (!p->mwf.size) {
		if (!S_ISREG(st.st_mode))
			goto cleanup;
1049
		p->mwf.size = (git_off_t)st.st_size;
1050 1051 1052 1053 1054 1055 1056 1057 1058
	} else if (p->mwf.size != st.st_size)
		goto cleanup;

#if 0
	/* We leave these file descriptors open with sliding mmap;
	 * there is no point keeping them open across exec(), though.
	 */
	fd_flag = fcntl(p->mwf.fd, F_GETFD, 0);
	if (fd_flag < 0)
1059
		goto cleanup;
1060 1061 1062

	fd_flag |= FD_CLOEXEC;
	if (fcntl(p->pack_fd, F_SETFD, fd_flag) == -1)
1063
		goto cleanup;
1064 1065 1066
#endif

	/* Verify we recognize this pack file format. */
1067 1068 1069
	if (p_read(p->mwf.fd, &hdr, sizeof(hdr)) < 0 ||
		hdr.hdr_signature != htonl(PACK_SIGNATURE) ||
		!pack_version_ok(hdr.hdr_version))
1070 1071 1072
		goto cleanup;

	/* Verify the pack matches its index. */
1073 1074 1075
	if (p->num_objects != ntohl(hdr.hdr_entries) ||
		p_lseek(p->mwf.fd, p->mwf.size - GIT_OID_RAWSZ, SEEK_SET) == -1 ||
		p_read(p->mwf.fd, sha1.id, GIT_OID_RAWSZ) < 0)
1076 1077 1078 1079
		goto cleanup;

	idx_sha1 = ((unsigned char *)p->index_map.data) + p->index_map.len - 40;

1080 1081 1082 1083 1084
	if (git_oid__cmp(&sha1, (git_oid *)idx_sha1) != 0)
		goto cleanup;

	git_mutex_unlock(&p->lock);
	return 0;
1085 1086

cleanup:
1087
	giterr_set(GITERR_OS, "invalid packfile '%s'", p->pack_name);
1088

1089 1090
	if (p->mwf.fd >= 0)
		p_close(p->mwf.fd);
1091
	p->mwf.fd = -1;
1092 1093 1094

	git_mutex_unlock(&p->lock);

1095
	return -1;
1096 1097
}

1098 1099 1100 1101 1102 1103 1104 1105
int git_packfile__name(char **out, const char *path)
{
	size_t path_len;
	git_buf buf = GIT_BUF_INIT;

	path_len = strlen(path);

	if (path_len < strlen(".idx"))
1106
		return git_odb__error_notfound("invalid packfile path", NULL, 0);
1107 1108 1109 1110 1111 1112 1113 1114

	if (git_buf_printf(&buf, "%.*s.pack", (int)(path_len - strlen(".idx")), path) < 0)
		return -1;

	*out = git_buf_detach(&buf);
	return 0;
}

1115
int git_packfile_alloc(struct git_pack_file **pack_out, const char *path)
1116 1117 1118
{
	struct stat st;
	struct git_pack_file *p;
1119
	size_t path_len = path ? strlen(path) : 0, alloc_len;
1120 1121

	*pack_out = NULL;
1122

1123
	if (path_len < strlen(".idx"))
1124
		return git_odb__error_notfound("invalid packfile path", NULL, 0);
1125

1126 1127
	GITERR_CHECK_ALLOC_ADD(&alloc_len, sizeof(*p), path_len);
	GITERR_CHECK_ALLOC_ADD(&alloc_len, alloc_len, 2);
1128

1129
	p = git__calloc(1, alloc_len);
1130
	GITERR_CHECK_ALLOC(p);
1131

1132 1133
	memcpy(p->pack_name, path, path_len + 1);

1134 1135 1136 1137
	/*
	 * Make sure a corresponding .pack file exists and that
	 * the index looks sane.
	 */
1138 1139 1140 1141 1142 1143
	if (git__suffixcmp(path, ".idx") == 0) {
		size_t root_len = path_len - strlen(".idx");

		memcpy(p->pack_name + root_len, ".keep", sizeof(".keep"));
		if (git_path_exists(p->pack_name) == true)
			p->pack_keep = 1;
1144

1145 1146
		memcpy(p->pack_name + root_len, ".pack", sizeof(".pack"));
	}
1147

1148
	if (p_stat(p->pack_name, &st) < 0 || !S_ISREG(st.st_mode)) {
1149
		git__free(p);
1150
		return git_odb__error_notfound("packfile not found", NULL, 0);
1151 1152 1153 1154 1155
	}

	/* ok, it looks sane as far as we can check without
	 * actually mapping the pack file.
	 */
1156
	p->mwf.fd = -1;
1157
	p->mwf.size = st.st_size;
1158 1159
	p->pack_local = 1;
	p->mtime = (git_time_t)st.st_mtime;
1160
	p->index_version = -1;
1161

Russell Belfer committed
1162
	if (git_mutex_init(&p->lock)) {
1163
		giterr_set(GITERR_OS, "failed to initialize packfile mutex");
Russell Belfer committed
1164 1165 1166
		git__free(p);
		return -1;
	}
1167

1168 1169 1170 1171 1172
	if (cache_init(&p->bases) < 0) {
		git__free(p);
		return -1;
	}

1173
	*pack_out = p;
1174 1175

	return 0;
1176 1177 1178 1179 1180 1181 1182 1183
}

/***********************************************************
 *
 * PACKFILE ENTRY SEARCH INTERNALS
 *
 ***********************************************************/

1184
static git_off_t nth_packed_object_offset(const struct git_pack_file *p, uint32_t n)
1185 1186
{
	const unsigned char *index = p->index_map.data;
1187
	const unsigned char *end = index + p->index_map.len;
1188 1189 1190 1191 1192 1193 1194 1195 1196 1197
	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;
1198 1199 1200 1201 1202

		/* Make sure we're not being sent out of bounds */
		if (index >= end - 8)
			return -1;

1203
		return (((uint64_t)ntohl(*((uint32_t *)(index + 0)))) << 32) |
Vicent Marti committed
1204
					ntohl(*((uint32_t *)(index + 4)));
1205 1206 1207
	}
}

1208 1209 1210 1211
static int git__memcmp4(const void *a, const void *b) {
	return memcmp(a, b, 4);
}

1212
int git_pack_foreach_entry(
1213
	struct git_pack_file *p,
1214
	git_odb_foreach_cb cb,
1215
	void *data)
1216 1217 1218
{
	const unsigned char *index = p->index_map.data, *current;
	uint32_t i;
1219
	int error = 0;
1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235

	if (index == NULL) {
		if ((error = pack_index_open(p)) < 0)
			return error;

		assert(p->index_map.data);

		index = p->index_map.data;
	}

	if (p->index_version > 1) {
		index += 8;
	}

	index += 4 * 256;

1236 1237
	if (p->oids == NULL) {
		git_vector offsets, oids;
1238

1239 1240 1241 1242 1243
		if ((error = git_vector_init(&oids, p->num_objects, NULL)))
			return error;

		if ((error = git_vector_init(&offsets, p->num_objects, git__memcmp4)))
			return error;
1244

1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258
		if (p->index_version > 1) {
			const unsigned char *off = index + 24 * p->num_objects;
			for (i = 0; i < p->num_objects; i++)
				git_vector_insert(&offsets, (void*)&off[4 * i]);
			git_vector_sort(&offsets);
			git_vector_foreach(&offsets, i, current)
				git_vector_insert(&oids, (void*)&index[5 * (current - off)]);
		} else {
			for (i = 0; i < p->num_objects; i++)
				git_vector_insert(&offsets, (void*)&index[24 * i]);
			git_vector_sort(&offsets);
			git_vector_foreach(&offsets, i, current)
				git_vector_insert(&oids, (void*)&current[4]);
		}
1259

1260
		git_vector_free(&offsets);
1261
		p->oids = (git_oid **)git_vector_detach(NULL, NULL, &oids);
1262 1263
	}

1264
	for (i = 0; i < p->num_objects; i++)
1265 1266
		if ((error = cb(p->oids[i], data)) != 0)
			return giterr_set_after_callback(error);
1267

1268
	return error;
1269 1270
}

1271
static int pack_entry_find_offset(
1272 1273 1274 1275
	git_off_t *offset_out,
	git_oid *found_oid,
	struct git_pack_file *p,
	const git_oid *short_oid,
1276
	size_t len)
1277
{
1278 1279
	const uint32_t *level1_ofs;
	const unsigned char *index;
1280 1281
	unsigned hi, lo, stride;
	int pos, found = 0;
1282
	git_off_t offset;
1283 1284 1285 1286
	const unsigned char *current = 0;

	*offset_out = 0;

1287
	if (p->index_version == -1) {
1288
		int error;
1289

1290 1291 1292 1293
		if ((error = pack_index_open(p)) < 0)
			return error;
		assert(p->index_map.data);
	}
1294

1295 1296 1297
	index = p->index_map.data;
	level1_ofs = p->index_map.data;

1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318
	if (p->index_version > 1) {
		level1_ofs += 2;
		index += 8;
	}

	index += 4 * 256;
	hi = ntohl(level1_ofs[(int)short_oid->id[0]]);
	lo = ((short_oid->id[0] == 0x0) ? 0 : ntohl(level1_ofs[(int)short_oid->id[0] - 1]));

	if (p->index_version > 1) {
		stride = 20;
	} else {
		stride = 24;
		index += 4;
	}

#ifdef INDEX_DEBUG_LOOKUP
	printf("%02x%02x%02x... lo %u hi %u nr %d\n",
		short_oid->id[0], short_oid->id[1], short_oid->id[2], lo, hi, p->num_objects);
#endif

1319
#ifdef GIT_USE_LOOKUP
Vicent Marti committed
1320
	pos = sha1_entry_pos(index, stride, 0, lo, hi, p->num_objects, short_oid->id);
1321 1322 1323
#else
	pos = sha1_position(index, stride, lo, hi, short_oid->id);
#endif
1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335

	if (pos >= 0) {
		/* An object matching exactly the oid was found */
		found = 1;
		current = index + pos * stride;
	} else {
		/* No object was found */
		/* pos refers to the object with the "closest" oid to short_oid */
		pos = - 1 - pos;
		if (pos < (int)p->num_objects) {
			current = index + pos * stride;

Russell Belfer committed
1336
			if (!git_oid_ncmp(short_oid, (const git_oid *)current, len))
1337 1338 1339 1340
				found = 1;
		}
	}

1341
	if (found && len != GIT_OID_HEXSZ && pos + 1 < (int)p->num_objects) {
1342 1343 1344 1345 1346 1347 1348 1349
		/* Check for ambiguousity */
		const unsigned char *next = current + stride;

		if (!git_oid_ncmp(short_oid, (const git_oid *)next, len)) {
			found = 2;
		}
	}

1350
	if (!found)
1351
		return git_odb__error_notfound("failed to find offset for pack entry", short_oid, len);
1352 1353
	if (found > 1)
		return git_odb__error_ambiguous("found multiple offsets for pack entry");
1354

1355 1356 1357 1358 1359 1360
	if ((offset = nth_packed_object_offset(p, pos)) < 0) {
		giterr_set(GITERR_ODB, "packfile index is corrupt");
		return -1;
	}

	*offset_out = offset;
1361
	git_oid_fromraw(found_oid, current);
1362 1363

#ifdef INDEX_DEBUG_LOOKUP
1364
	{
1365 1366 1367 1368 1369
		unsigned char hex_sha1[GIT_OID_HEXSZ + 1];
		git_oid_fmt(hex_sha1, found_oid);
		hex_sha1[GIT_OID_HEXSZ] = '\0';
		printf("found lo=%d %s\n", lo, hex_sha1);
	}
1370
#endif
1371

1372
	return 0;
1373 1374 1375 1376 1377 1378
}

int git_pack_entry_find(
		struct git_pack_entry *e,
		struct git_pack_file *p,
		const git_oid *short_oid,
1379
		size_t len)
1380
{
1381
	git_off_t offset;
1382 1383 1384 1385 1386 1387 1388 1389
	git_oid found_oid;
	int error;

	assert(p);

	if (len == GIT_OID_HEXSZ && p->num_bad_objects) {
		unsigned i;
		for (i = 0; i < p->num_bad_objects; i++)
1390
			if (git_oid__cmp(short_oid, &p->bad_object_sha1[i]) == 0)
1391
				return packfile_error("bad object found in packfile");
1392 1393 1394
	}

	error = pack_entry_find_offset(&offset, &found_oid, p, short_oid, len);
1395 1396
	if (error < 0)
		return error;
1397 1398 1399 1400

	/* we found a unique entry in the index;
	 * make sure the packfile backing the index
	 * still exists on disk */
1401 1402
	if (p->mwf.fd == -1 && (error = packfile_open(p)) < 0)
		return error;
1403 1404 1405 1406 1407

	e->offset = offset;
	e->p = p;

	git_oid_cpy(&e->sha1, &found_oid);
1408
	return 0;
1409
}