odb_pack.c 17.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
#include <zlib.h>
10
#include "git2/repository.h"
11 12
#include "git2/indexer.h"
#include "git2/sys/odb_backend.h"
13 14 15 16
#include "fileops.h"
#include "hash.h"
#include "odb.h"
#include "delta-apply.h"
17
#include "sha1_lookup.h"
18
#include "mwindow.h"
19
#include "pack.h"
20

21
#include "git2/odb_backend.h"
22

Vicent Marti committed
23 24 25
struct pack_backend {
	git_odb_backend parent;
	git_vector packs;
26
	struct git_pack_file *last_found;
27
	char *pack_folder;
Vicent Marti committed
28 29
};

30 31
struct pack_writepack {
	struct git_odb_writepack parent;
32
	git_indexer *indexer;
33 34
};

Vicent Marti committed
35 36 37
/**
 * The wonderful tale of a Packed Object lookup query
 * ===================================================
Vicent Marti committed
38 39 40
 *	A riveting and epic story of epicness and ASCII
 *			art, presented by yours truly,
 *				Sir Vicent of Marti
Vicent Marti committed
41 42 43 44 45 46 47 48 49 50
 *
 *
 *	Chapter 1: Once upon a time...
 *	Initialization of the Pack Backend
 *	--------------------------------------------------
 *
 *	# git_odb_backend_pack
 *	| Creates the pack backend structure, initializes the
 *	| callback pointers to our default read() and exist() methods,
 *	| and tries to preload all the known packfiles in the ODB.
Vicent Marti committed
51
 * |
Vicent Marti committed
52
 *	|-# packfile_load_all
Vicent Marti committed
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
 *	 | Tries to find the `pack` folder, if it exists. ODBs without
 *	 | a pack folder are ignored altogether. If there's a `pack` folder
 *	 | we run a `dirent` callback through every file in the pack folder
 *	 | to find our packfiles. The packfiles are then sorted according
 *	 | to a sorting callback.
 * 	 |
 *	 |-# packfile_load__cb
 *	 | | This callback is called from `dirent` with every single file
 *	 | | inside the pack folder. We find the packs by actually locating
 *	 | | their index (ends in ".idx"). From that index, we verify that
 *	 | | the corresponding packfile exists and is valid, and if so, we
 *	| | add it to the pack list.
 *	 | |
 *	 | |-# packfile_check
 *	 |		Make sure that there's a packfile to back this index, and store
 *	 |		some very basic information regarding the packfile itself,
 *	 |		such as the full path, the size, and the modification time.
 *	 |		We don't actually open the packfile to check for internal consistency.
 *	|
 *	|-# packfile_sort__cb
 *		Sort all the preloaded packs according to some specific criteria:
 *		we prioritize the "newer" packs because it's more likely they
 *		contain the objects we are looking for, and we prioritize local
 *		packs over remote ones.
Vicent Marti committed
77 78 79 80 81 82 83
 *
 *
 *
 *	Chapter 2: To be, or not to be...
 *	A standard packed `exist` query for an OID
 *	--------------------------------------------------
 *
Vicent Marti committed
84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
 * # pack_backend__exists
 * | Check if the given SHA1 oid exists in any of the packs
 * | that have been loaded for our ODB.
 * |
 * |-# pack_entry_find
 *	| Iterate through all the packs that have been preloaded
 *	| (starting by the pack where the latest object was found)
 *	| to try to find the OID in one of them.
 *	|
 *	|-# pack_entry_find1
 *		| Check the index of an individual pack to see if the SHA1
 *		| OID can be found. If we can find the offset to that SHA1
 *		| inside of the index, that means the object is contained
 *		| inside of the packfile and we can stop searching.
 *		| Before returning, we verify that the packfile behing the
 *		| index we are searching still exists on disk.
 *		|
 *		|-# pack_entry_find_offset
 *		| | Mmap the actual index file to disk if it hasn't been opened
 *		| | yet, and run a binary search through it to find the OID.
 *		| | See <http://book.git-scm.com/7_the_packfile.html> for specifics
 *		| | on the Packfile Index format and how do we find entries in it.
 *		| |
 *		| |-# pack_index_open
 *		|	| Guess the name of the index based on the full path to the
 *		|	| packfile, open it and verify its contents. Only if the index
 *		|	| has not been opened already.
 *		|	|
 *		|	|-# pack_index_check
 *		|		Mmap the index file and do a quick run through the header
 *		|		to guess the index version (right now we support v1 and v2),
 *		|		and to verify that the size of the index makes sense.
 *		|
 *		|-# packfile_open
 *			See `packfile_open` in Chapter 3
Vicent Marti committed
119 120 121 122 123 124 125 126 127
 *
 *
 *
 *	Chapter 3: The neverending story...
 *	A standard packed `lookup` query for an OID
 *	--------------------------------------------------
 *	TODO
 *
 */
128 129 130 131


/***********************************************************
 *
Vicent Marti committed
132
 * FORWARD DECLARATIONS
133 134 135
 *
 ***********************************************************/

Vicent Marti committed
136
static int packfile_sort__cb(const void *a_, const void *b_);
137

138
static int packfile_load__cb(void *_data, git_buf *path);
139

140
static int pack_entry_find(struct git_pack_entry *e,
141
	struct pack_backend *backend, const git_oid *oid);
142

143 144
/* Can find the offset of an object given
 * a prefix of an identifier.
145
 * Sets GIT_EAMBIGUOUS if short oid is ambiguous.
146 147
 * This method assumes that len is between
 * GIT_OID_MINPREFIXLEN and GIT_OID_HEXSZ.
148
 */
149 150 151 152
static int pack_entry_find_prefix(
	struct git_pack_entry *e,
	struct pack_backend *backend,
	const git_oid *short_oid,
153
	size_t len);
154

Vicent Marti committed
155 156 157 158 159 160 161


/***********************************************************
 *
 * PACK WINDOW MANAGEMENT
 *
 ***********************************************************/
162

Vicent Marti committed
163
static int packfile_sort__cb(const void *a_, const void *b_)
164
{
165 166
	const struct git_pack_file *a = a_;
	const struct git_pack_file *b = b_;
Vicent Marti committed
167
	int st;
168

Vicent Marti committed
169 170
	/*
	 * Local packs tend to contain objects specific to our
Vicent Marti committed
171
	 * variant of the project than remote ones. In addition,
Vicent Marti committed
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
	 * 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;
190 191
}

Vicent Marti committed
192

193
static int packfile_load__cb(void *data, git_buf *path)
194
{
195
	struct pack_backend *backend = data;
196
	struct git_pack_file *pack;
197 198
	const char *path_str = git_buf_cstr(path);
	size_t i, cmp_len = git_buf_len(path);
Vicent Marti committed
199
	int error;
200

201
	if (cmp_len <= strlen(".idx") || git__suffixcmp(path_str, ".idx") != 0)
202
		return 0; /* not an index */
203

204 205
	cmp_len -= strlen(".idx");

206
	for (i = 0; i < backend->packs.length; ++i) {
207
		struct git_pack_file *p = git_vector_get(&backend->packs, i);
208 209

		if (memcmp(p->pack_name, path_str, cmp_len) == 0)
210
			return 0;
211
	}
212

213
	error = git_mwindow_get_pack(&pack, path->ptr);
214 215 216 217

	/* ignore missing .pack file as git does */
	if (error == GIT_ENOTFOUND) {
		giterr_clear();
218
		return 0;
219 220 221 222 223
	}

	if (!error)
		error = git_vector_insert(&backend->packs, pack);

224
	return error;
Vicent Marti committed
225

226 227
}

228 229 230 231 232
static int pack_entry_find_inner(
	struct git_pack_entry *e,
	struct pack_backend *backend,
	const git_oid *oid,
	struct git_pack_file *last_found)
Vicent Marti committed
233
{
234
	size_t i;
235

236 237
	if (last_found &&
		git_pack_entry_find(e, last_found, oid, GIT_OID_HEXSZ) == 0)
238
		return 0;
239

Vicent Marti committed
240
	for (i = 0; i < backend->packs.length; ++i) {
241
		struct git_pack_file *p;
242

Vicent Marti committed
243
		p = git_vector_get(&backend->packs, i);
244
		if (p == last_found)
Vicent Marti committed
245
			continue;
246

247
		if (git_pack_entry_find(e, p, oid, GIT_OID_HEXSZ) == 0) {
Vicent Marti committed
248
			backend->last_found = p;
249
			return 0;
250
		}
Vicent Marti committed
251 252
	}

253 254 255 256 257
	return -1;
}

static int pack_entry_find(struct git_pack_entry *e, struct pack_backend *backend, const git_oid *oid)
{
258
	struct git_pack_file *last_found = backend->last_found;
259 260 261 262 263

	if (backend->last_found &&
		git_pack_entry_find(e, backend->last_found, oid, GIT_OID_HEXSZ) == 0)
		return 0;

264
	if (!pack_entry_find_inner(e, backend, oid, last_found))
265 266
		return 0;

Russell Belfer committed
267
	return git_odb__error_notfound("failed to find pack entry", oid);
Vicent Marti committed
268 269
}

270 271 272 273 274
static int pack_entry_find_prefix(
	struct git_pack_entry *e,
	struct pack_backend *backend,
	const git_oid *short_oid,
	size_t len)
275 276
{
	int error;
277
	size_t i;
278 279 280
	git_oid found_full_oid = {{0}};
	bool found = false;
	struct git_pack_file *last_found = backend->last_found;
281

282 283
	if (last_found) {
		error = git_pack_entry_find(e, last_found, short_oid, len);
284 285
		if (error == GIT_EAMBIGUOUS)
			return error;
286 287 288 289
		if (!error) {
			git_oid_cpy(&found_full_oid, &e->sha1);
			found = true;
		}
290 291 292
	}

	for (i = 0; i < backend->packs.length; ++i) {
293
		struct git_pack_file *p;
294 295

		p = git_vector_get(&backend->packs, i);
296
		if (p == last_found)
297 298
			continue;

299
		error = git_pack_entry_find(e, p, short_oid, len);
300 301 302
		if (error == GIT_EAMBIGUOUS)
			return error;
		if (!error) {
303 304 305 306
			if (found && git_oid_cmp(&e->sha1, &found_full_oid))
				return git_odb__error_ambiguous("found multiple pack entries");
			git_oid_cpy(&found_full_oid, &e->sha1);
			found = true;
307 308 309 310
			backend->last_found = p;
		}
	}

311
	if (!found)
Russell Belfer committed
312
		return git_odb__error_notfound("no matching pack entry for prefix", short_oid);
313 314
	else
		return 0;
315 316
}

Vicent Marti committed
317

318 319 320 321 322 323 324
/***********************************************************
 *
 * PACKED BACKEND PUBLIC API
 *
 * Implement the git_odb_backend API calls
 *
 ***********************************************************/
325
static int pack_backend__refresh(git_odb_backend *backend_)
Vicent Marti committed
326 327 328 329
{
	int error;
	struct stat st;
	git_buf path = GIT_BUF_INIT;
330
	struct pack_backend *backend = (struct pack_backend *)backend_;
Vicent Marti committed
331

332
	if (backend->pack_folder == NULL)
Vicent Marti committed
333 334
		return 0;

335
	if (p_stat(backend->pack_folder, &st) < 0 || !S_ISDIR(st.st_mode))
Vicent Marti committed
336 337
		return git_odb__error_notfound("failed to refresh packfiles", NULL);

338
	git_buf_sets(&path, backend->pack_folder);
Vicent Marti committed
339 340

	/* reload all packs */
341
	error = git_path_direach(&path, 0, packfile_load__cb, backend);
Vicent Marti committed
342

343
	git_buf_free(&path);
344
	git_vector_sort(&backend->packs);
Vicent Marti committed
345

346
	return error;
Vicent Marti committed
347 348
}

349
static int pack_backend__read_header_internal(
nulltoken committed
350 351
	size_t *len_p, git_otype *type_p,
	struct git_odb_backend *backend, const git_oid *oid)
352
{
353 354
	struct git_pack_entry e;
	int error;
355

356
	assert(len_p && type_p && backend && oid);
357

358 359
	if ((error = pack_entry_find(&e, (struct pack_backend *)backend, oid)) < 0)
		return error;
360

361
	return git_packfile_resolve_header(len_p, type_p, e.p, e.offset);
362 363
}

364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381
static int pack_backend__read_header(
	size_t *len_p, git_otype *type_p,
	struct git_odb_backend *backend, const git_oid *oid)
{
	int error;

	error = pack_backend__read_header_internal(len_p, type_p, backend, oid);

	if (error != GIT_ENOTFOUND)
		return error;

	if ((error = pack_backend__refresh(backend)) < 0)
		return error;

	return pack_backend__read_header_internal(len_p, type_p, backend, oid);
}

static int pack_backend__read_internal(
nulltoken committed
382 383
	void **buffer_p, size_t *len_p, git_otype *type_p,
	git_odb_backend *backend, const git_oid *oid)
384
{
385
	struct git_pack_entry e;
386
	git_rawobj raw = {NULL};
Vicent Marti committed
387
	int error;
388

389 390 391
	if ((error = pack_entry_find(&e, (struct pack_backend *)backend, oid)) < 0 ||
		(error = git_packfile_unpack(&raw, e.p, &e.offset)) < 0)
		return error;
Vicent Marti committed
392 393 394 395 396

	*buffer_p = raw.data;
	*len_p = raw.len;
	*type_p = raw.type;

397
	return 0;
398 399
}

400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417
static int pack_backend__read(
	void **buffer_p, size_t *len_p, git_otype *type_p,
	git_odb_backend *backend, const git_oid *oid)
{
	int error;

	error = pack_backend__read_internal(buffer_p, len_p, type_p, backend, oid);

	if (error != GIT_ENOTFOUND)
		return error;

	if ((error = pack_backend__refresh(backend)) < 0)
		return error;

	return pack_backend__read_internal(buffer_p, len_p, type_p, backend, oid);
}

static int pack_backend__read_prefix_internal(
Vicent Marti committed
418 419 420 421 422 423
	git_oid *out_oid,
	void **buffer_p,
	size_t *len_p,
	git_otype *type_p,
	git_odb_backend *backend,
	const git_oid *short_oid,
424
	size_t len)
425
{
426 427
	int error = 0;

428
	if (len < GIT_OID_MINPREFIXLEN)
429
		error = git_odb__error_ambiguous("prefix length too short");
430

431
	else if (len >= GIT_OID_HEXSZ) {
432
		/* We can fall back to regular read method */
433 434
		error = pack_backend__read(buffer_p, len_p, type_p, backend, short_oid);
		if (!error)
435 436
			git_oid_cpy(out_oid, short_oid);
	} else {
437
		struct git_pack_entry e;
438 439
		git_rawobj raw;

440 441 442 443 444 445 446 447 448
		if ((error = pack_entry_find_prefix(
				&e, (struct pack_backend *)backend, short_oid, len)) == 0 &&
			(error = git_packfile_unpack(&raw, e.p, &e.offset)) == 0)
		{
			*buffer_p = raw.data;
			*len_p = raw.len;
			*type_p = raw.type;
			git_oid_cpy(out_oid, &e.sha1);
		}
449
	}
450

451
	return error;
452 453
}

454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477
static int pack_backend__read_prefix(
	git_oid *out_oid,
	void **buffer_p,
	size_t *len_p,
	git_otype *type_p,
	git_odb_backend *backend,
	const git_oid *short_oid,
	size_t len)
{
	int error;

	error = pack_backend__read_prefix_internal(
		out_oid, buffer_p, len_p, type_p, backend, short_oid, len);

	if (error != GIT_ENOTFOUND)
		return error;

	if ((error = pack_backend__refresh(backend)) < 0)
		return error;

	return pack_backend__read_prefix_internal(
		out_oid, buffer_p, len_p, type_p, backend, short_oid, len);
}

478
static int pack_backend__exists(git_odb_backend *backend, const git_oid *oid)
479
{
480
	struct git_pack_entry e;
481 482 483 484 485 486 487 488 489 490 491 492
	int error;

	error = pack_entry_find(&e, (struct pack_backend *)backend, oid);

	if (error != GIT_ENOTFOUND)
		return error == 0;

	if ((error = pack_backend__refresh(backend)) < 0) {
		giterr_clear();
		return (int)false;
	}

493
	return pack_entry_find(&e, (struct pack_backend *)backend, oid) == 0;
494 495
}

496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512
static int pack_backend__exists_prefix(
	git_oid *out, git_odb_backend *backend, const git_oid *short_id, size_t len)
{
	int error;
	struct pack_backend *pb = (struct pack_backend *)backend;
	struct git_pack_entry e = {0};

	error = pack_entry_find_prefix(&e, pb, short_id, len);

	if (error == GIT_ENOTFOUND && !(error = pack_backend__refresh(backend)))
		error = pack_entry_find_prefix(&e, pb, short_id, len);

	git_oid_cpy(out, &e.sha1);

	return error;
}

513
static int pack_backend__foreach(git_odb_backend *_backend, git_odb_foreach_cb cb, void *data)
514
{
515
	int error;
516 517 518 519 520 521 522 523
	struct git_pack_file *p;
	struct pack_backend *backend;
	unsigned int i;

	assert(_backend && cb);
	backend = (struct pack_backend *)_backend;

	/* Make sure we know about the packfiles */
Vicent Marti committed
524
	if ((error = pack_backend__refresh(_backend)) < 0)
525
		return error;
526 527

	git_vector_foreach(&backend->packs, i, p) {
528
		if ((error = git_pack_foreach_entry(p, cb, data)) < 0)
529
			return error;
530
	}
531

532 533 534
	return 0;
}

535
static int pack_backend__writepack_append(struct git_odb_writepack *_writepack, const void *data, size_t size, git_transfer_progress *stats)
536 537 538 539 540
{
	struct pack_writepack *writepack = (struct pack_writepack *)_writepack;

	assert(writepack);

541
	return git_indexer_append(writepack->indexer, data, size, stats);
542 543 544 545 546 547 548 549
}

static int pack_backend__writepack_commit(struct git_odb_writepack *_writepack, git_transfer_progress *stats)
{
	struct pack_writepack *writepack = (struct pack_writepack *)_writepack;

	assert(writepack);

550
	return git_indexer_commit(writepack->indexer, stats);
551 552 553 554 555 556 557 558
}

static void pack_backend__writepack_free(struct git_odb_writepack *_writepack)
{
	struct pack_writepack *writepack = (struct pack_writepack *)_writepack;

	assert(writepack);

559
	git_indexer_free(writepack->indexer);
560 561 562 563 564
	git__free(writepack);
}

static int pack_backend__writepack(struct git_odb_writepack **out,
	git_odb_backend *_backend,
565
        git_odb *odb,
566
	git_transfer_progress_cb progress_cb,
567 568 569 570 571 572 573 574 575 576 577 578 579 580
	void *progress_payload)
{
	struct pack_backend *backend;
	struct pack_writepack *writepack;

	assert(out && _backend);

	*out = NULL;

	backend = (struct pack_backend *)_backend;

	writepack = git__calloc(1, sizeof(struct pack_writepack));
	GITERR_CHECK_ALLOC(writepack);

581
	if (git_indexer_new(&writepack->indexer,
582
		backend->pack_folder, 0, odb, progress_cb, progress_payload) < 0) {
583 584 585 586 587
		git__free(writepack);
		return -1;
	}

	writepack->parent.backend = _backend;
588
	writepack->parent.append = pack_backend__writepack_append;
589 590 591 592 593 594 595 596
	writepack->parent.commit = pack_backend__writepack_commit;
	writepack->parent.free = pack_backend__writepack_free;

	*out = (git_odb_writepack *)writepack;

	return 0;
}

597
static void pack_backend__free(git_odb_backend *_backend)
598
{
Vicent Marti committed
599
	struct pack_backend *backend;
600
	size_t i;
601 602 603

	assert(_backend);

Vicent Marti committed
604
	backend = (struct pack_backend *)_backend;
605

Vicent Marti committed
606
	for (i = 0; i < backend->packs.length; ++i) {
607
		struct git_pack_file *p = git_vector_get(&backend->packs, i);
608
		git_mwindow_put_pack(p);
Vicent Marti committed
609
	}
610

Vicent Marti committed
611
	git_vector_free(&backend->packs);
612 613
	git__free(backend->pack_folder);
	git__free(backend);
614 615
}

616
static int pack_backend__alloc(struct pack_backend **out, size_t initial_size)
617
{
618 619
	struct pack_backend *backend = git__calloc(1, sizeof(struct pack_backend));
	GITERR_CHECK_ALLOC(backend);
620

621 622
	if (git_vector_init(&backend->packs, initial_size, packfile_sort__cb) < 0) {
		git__free(backend);
623
		return -1;
624
	}
625

626
	backend->parent.version = GIT_ODB_BACKEND_VERSION;
627 628 629

	backend->parent.read = &pack_backend__read;
	backend->parent.read_prefix = &pack_backend__read_prefix;
630
	backend->parent.read_header = &pack_backend__read_header;
631
	backend->parent.exists = &pack_backend__exists;
632
	backend->parent.exists_prefix = &pack_backend__exists_prefix;
Vicent Marti committed
633
	backend->parent.refresh = &pack_backend__refresh;
634
	backend->parent.foreach = &pack_backend__foreach;
635
	backend->parent.writepack = &pack_backend__writepack;
636 637
	backend->parent.free = &pack_backend__free;

638
	*out = backend;
639 640 641
	return 0;
}

642
int git_odb_backend_one_pack(git_odb_backend **backend_out, const char *idx)
643
{
644
	struct pack_backend *backend = NULL;
645
	struct git_pack_file *packfile = NULL;
646

647 648
	if (pack_backend__alloc(&backend, 1) < 0)
		return -1;
649

650
	if (git_mwindow_get_pack(&packfile, idx) < 0 ||
651
		git_vector_insert(&backend->packs, packfile) < 0)
652
	{
653
		pack_backend__free((git_odb_backend *)backend);
654 655
		return -1;
	}
656

657 658 659 660 661 662 663 664 665 666
	*backend_out = (git_odb_backend *)backend;
	return 0;
}

int git_odb_backend_pack(git_odb_backend **backend_out, const char *objects_dir)
{
	int error = 0;
	struct pack_backend *backend = NULL;
	git_buf path = GIT_BUF_INIT;

667 668 669
	if (git_mwindow_files_init() < 0)
		return -1;

670 671
	if (pack_backend__alloc(&backend, 8) < 0)
		return -1;
Vicent Marti committed
672

673 674 675
	if (!(error = git_buf_joinpath(&path, objects_dir, "pack")) &&
		git_path_isdir(git_buf_cstr(&path)))
	{
676
		backend->pack_folder = git_buf_detach(&path);
677

Vicent Marti committed
678
		error = pack_backend__refresh((git_odb_backend *)backend);
Vicent Marti committed
679
	}
680

681 682 683 684
	if (error < 0) {
		pack_backend__free((git_odb_backend *)backend);
		backend = NULL;
	}
685 686

	*backend_out = (git_odb_backend *)backend;
687 688 689

	git_buf_free(&path);

690
	return error;
691
}