odb_pack.c 15.9 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(
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
static int pack_backend__read(
nulltoken committed
365 366
	void **buffer_p, size_t *len_p, git_otype *type_p,
	git_odb_backend *backend, const git_oid *oid)
367
{
368
	struct git_pack_entry e;
369
	git_rawobj raw = {NULL};
Vicent Marti committed
370
	int error;
371

372 373 374
	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
375 376 377 378 379

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

380
	return 0;
381 382
}

383
static int pack_backend__read_prefix(
Vicent Marti committed
384 385 386 387 388 389
	git_oid *out_oid,
	void **buffer_p,
	size_t *len_p,
	git_otype *type_p,
	git_odb_backend *backend,
	const git_oid *short_oid,
390
	size_t len)
391
{
392 393
	int error = 0;

394
	if (len < GIT_OID_MINPREFIXLEN)
395
		error = git_odb__error_ambiguous("prefix length too short");
396

397
	else if (len >= GIT_OID_HEXSZ) {
398
		/* We can fall back to regular read method */
399 400
		error = pack_backend__read(buffer_p, len_p, type_p, backend, short_oid);
		if (!error)
401 402
			git_oid_cpy(out_oid, short_oid);
	} else {
403
		struct git_pack_entry e;
404 405
		git_rawobj raw;

406 407 408 409 410 411 412 413 414
		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);
		}
415
	}
416

417
	return error;
418 419
}

420
static int pack_backend__exists(git_odb_backend *backend, const git_oid *oid)
421
{
422
	struct git_pack_entry e;
423
	return pack_entry_find(&e, (struct pack_backend *)backend, oid) == 0;
424 425
}

426 427 428 429 430 431 432 433 434 435 436 437
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);
	git_oid_cpy(out, &e.sha1);
	return error;
}

438
static int pack_backend__foreach(git_odb_backend *_backend, git_odb_foreach_cb cb, void *data)
439
{
440
	int error;
441 442 443 444 445 446 447 448
	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
449
	if ((error = pack_backend__refresh(_backend)) < 0)
450
		return error;
451 452

	git_vector_foreach(&backend->packs, i, p) {
453
		if ((error = git_pack_foreach_entry(p, cb, data)) < 0)
454
			return error;
455
	}
456

457 458 459
	return 0;
}

460
static int pack_backend__writepack_append(struct git_odb_writepack *_writepack, const void *data, size_t size, git_transfer_progress *stats)
461 462 463 464 465
{
	struct pack_writepack *writepack = (struct pack_writepack *)_writepack;

	assert(writepack);

466
	return git_indexer_append(writepack->indexer, data, size, stats);
467 468 469 470 471 472 473 474
}

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

475
	return git_indexer_commit(writepack->indexer, stats);
476 477 478 479 480 481 482 483
}

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

	assert(writepack);

484
	git_indexer_free(writepack->indexer);
485 486 487 488 489
	git__free(writepack);
}

static int pack_backend__writepack(struct git_odb_writepack **out,
	git_odb_backend *_backend,
490
        git_odb *odb,
491
	git_transfer_progress_cb progress_cb,
492 493 494 495 496 497 498 499 500 501 502 503 504 505
	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);

506
	if (git_indexer_new(&writepack->indexer,
507
		backend->pack_folder, 0, odb, progress_cb, progress_payload) < 0) {
508 509 510 511 512
		git__free(writepack);
		return -1;
	}

	writepack->parent.backend = _backend;
513
	writepack->parent.append = pack_backend__writepack_append;
514 515 516 517 518 519 520 521
	writepack->parent.commit = pack_backend__writepack_commit;
	writepack->parent.free = pack_backend__writepack_free;

	*out = (git_odb_writepack *)writepack;

	return 0;
}

522
static void pack_backend__free(git_odb_backend *_backend)
523
{
Vicent Marti committed
524
	struct pack_backend *backend;
525
	size_t i;
526 527 528

	assert(_backend);

Vicent Marti committed
529
	backend = (struct pack_backend *)_backend;
530

Vicent Marti committed
531
	for (i = 0; i < backend->packs.length; ++i) {
532
		struct git_pack_file *p = git_vector_get(&backend->packs, i);
533
		git_mwindow_put_pack(p);
Vicent Marti committed
534
	}
535

Vicent Marti committed
536
	git_vector_free(&backend->packs);
537 538
	git__free(backend->pack_folder);
	git__free(backend);
539 540
}

541
static int pack_backend__alloc(struct pack_backend **out, size_t initial_size)
542
{
543 544
	struct pack_backend *backend = git__calloc(1, sizeof(struct pack_backend));
	GITERR_CHECK_ALLOC(backend);
545

546 547
	if (git_vector_init(&backend->packs, initial_size, packfile_sort__cb) < 0) {
		git__free(backend);
548
		return -1;
549
	}
550

551
	backend->parent.version = GIT_ODB_BACKEND_VERSION;
552 553 554

	backend->parent.read = &pack_backend__read;
	backend->parent.read_prefix = &pack_backend__read_prefix;
555
	backend->parent.read_header = &pack_backend__read_header;
556
	backend->parent.exists = &pack_backend__exists;
557
	backend->parent.exists_prefix = &pack_backend__exists_prefix;
Vicent Marti committed
558
	backend->parent.refresh = &pack_backend__refresh;
559
	backend->parent.foreach = &pack_backend__foreach;
560
	backend->parent.writepack = &pack_backend__writepack;
561 562
	backend->parent.free = &pack_backend__free;

563
	*out = backend;
564 565 566
	return 0;
}

567
int git_odb_backend_one_pack(git_odb_backend **backend_out, const char *idx)
568
{
569
	struct pack_backend *backend = NULL;
570
	struct git_pack_file *packfile = NULL;
571

572 573
	if (pack_backend__alloc(&backend, 1) < 0)
		return -1;
574

575
	if (git_mwindow_get_pack(&packfile, idx) < 0 ||
576
		git_vector_insert(&backend->packs, packfile) < 0)
577
	{
578
		pack_backend__free((git_odb_backend *)backend);
579 580
		return -1;
	}
581

582 583 584 585 586 587 588 589 590 591
	*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;

592 593 594
	if (git_mwindow_files_init() < 0)
		return -1;

595 596
	if (pack_backend__alloc(&backend, 8) < 0)
		return -1;
Vicent Marti committed
597

598 599 600
	if (!(error = git_buf_joinpath(&path, objects_dir, "pack")) &&
		git_path_isdir(git_buf_cstr(&path)))
	{
601
		backend->pack_folder = git_buf_detach(&path);
Vicent Marti committed
602
		error = pack_backend__refresh((git_odb_backend *)backend);
Vicent Marti committed
603
	}
604

605 606 607 608
	if (error < 0) {
		pack_backend__free((git_odb_backend *)backend);
		backend = NULL;
	}
609 610

	*backend_out = (git_odb_backend *)backend;
611 612 613

	git_buf_free(&path);

614
	return error;
615
}