[thirdparty/git.git] / midx.c

#include "git-compat-util.h"
#include "config.h"
#include "dir.h"
#include "hex.h"
#include "packfile.h"
#include "object-file.h"
#include "hash-lookup.h"
#include "midx.h"
#include "progress.h"
#include "trace2.h"
#include "chunk-format.h"
#include "pack-bitmap.h"
#include "pack-revindex.h"

int midx_checksum_valid(struct multi_pack_index *m);
void clear_midx_files_ext(const char *object_dir, const char *ext,
			  unsigned char *keep_hash);
int cmp_idx_or_pack_name(const char *idx_or_pack_name,
			 const char *idx_name);

const unsigned char *get_midx_checksum(struct multi_pack_index *m)
{
	return m->data + m->data_len - the_hash_algo->rawsz;
}

void get_midx_filename(struct strbuf *out, const char *object_dir)
{
	strbuf_addf(out, "%s/pack/multi-pack-index", object_dir);
}

void get_midx_rev_filename(struct strbuf *out, struct multi_pack_index *m)
{
	get_midx_filename(out, m->object_dir);
	strbuf_addf(out, "-%s.rev", hash_to_hex(get_midx_checksum(m)));
}

static int midx_read_oid_fanout(const unsigned char *chunk_start,
				size_t chunk_size, void *data)
{
	int i;
	struct multi_pack_index *m = data;
	m->chunk_oid_fanout = (uint32_t *)chunk_start;

	if (chunk_size != 4 * 256) {
		error(_("multi-pack-index OID fanout is of the wrong size"));
		return 1;
	}
	for (i = 0; i < 255; i++) {
		uint32_t oid_fanout1 = ntohl(m->chunk_oid_fanout[i]);
		uint32_t oid_fanout2 = ntohl(m->chunk_oid_fanout[i+1]);

		if (oid_fanout1 > oid_fanout2) {
			error(_("oid fanout out of order: fanout[%d] = %"PRIx32" > %"PRIx32" = fanout[%d]"),
			      i, oid_fanout1, oid_fanout2, i + 1);
			return 1;
		}
	}
	m->num_objects = ntohl(m->chunk_oid_fanout[255]);
	return 0;
}

static int midx_read_oid_lookup(const unsigned char *chunk_start,
				size_t chunk_size, void *data)
{
	struct multi_pack_index *m = data;
	m->chunk_oid_lookup = chunk_start;

	if (chunk_size != st_mult(m->hash_len, m->num_objects)) {
		error(_("multi-pack-index OID lookup chunk is the wrong size"));
		return 1;
	}
	return 0;
}

static int midx_read_object_offsets(const unsigned char *chunk_start,
				    size_t chunk_size, void *data)
{
	struct multi_pack_index *m = data;
	m->chunk_object_offsets = chunk_start;

	if (chunk_size != st_mult(m->num_objects, MIDX_CHUNK_OFFSET_WIDTH)) {
		error(_("multi-pack-index object offset chunk is the wrong size"));
		return 1;
	}
	return 0;
}

#define MIDX_MIN_SIZE (MIDX_HEADER_SIZE + the_hash_algo->rawsz)

struct multi_pack_index *load_multi_pack_index(const char *object_dir, int local)
{
	struct multi_pack_index *m = NULL;
	int fd;
	struct stat st;
	size_t midx_size;
	void *midx_map = NULL;
	uint32_t hash_version;
	struct strbuf midx_name = STRBUF_INIT;
	uint32_t i;
	const char *cur_pack_name;
	struct chunkfile *cf = NULL;

	get_midx_filename(&midx_name, object_dir);

	fd = git_open(midx_name.buf);

	if (fd < 0)
		goto cleanup_fail;
	if (fstat(fd, &st)) {
		error_errno(_("failed to read %s"), midx_name.buf);
		goto cleanup_fail;
	}

	midx_size = xsize_t(st.st_size);

	if (midx_size < MIDX_MIN_SIZE) {
		error(_("multi-pack-index file %s is too small"), midx_name.buf);
		goto cleanup_fail;
	}

	strbuf_release(&midx_name);

	midx_map = xmmap(NULL, midx_size, PROT_READ, MAP_PRIVATE, fd, 0);
	close(fd);

	FLEX_ALLOC_STR(m, object_dir, object_dir);
	m->data = midx_map;
	m->data_len = midx_size;
	m->local = local;

	m->signature = get_be32(m->data);
	if (m->signature != MIDX_SIGNATURE)
		die(_("multi-pack-index signature 0x%08x does not match signature 0x%08x"),
		      m->signature, MIDX_SIGNATURE);

	m->version = m->data[MIDX_BYTE_FILE_VERSION];
	if (m->version != MIDX_VERSION)
		die(_("multi-pack-index version %d not recognized"),
		      m->version);

	hash_version = m->data[MIDX_BYTE_HASH_VERSION];
	if (hash_version != oid_version(the_hash_algo)) {
		error(_("multi-pack-index hash version %u does not match version %u"),
		      hash_version, oid_version(the_hash_algo));
		goto cleanup_fail;
	}
	m->hash_len = the_hash_algo->rawsz;

	m->num_chunks = m->data[MIDX_BYTE_NUM_CHUNKS];

	m->num_packs = get_be32(m->data + MIDX_BYTE_NUM_PACKS);

	m->preferred_pack_idx = -1;

	cf = init_chunkfile(NULL);

	if (read_table_of_contents(cf, m->data, midx_size,
				   MIDX_HEADER_SIZE, m->num_chunks,
				   MIDX_CHUNK_ALIGNMENT))
		goto cleanup_fail;

	if (pair_chunk(cf, MIDX_CHUNKID_PACKNAMES, &m->chunk_pack_names, &m->chunk_pack_names_len))
		die(_("multi-pack-index required pack-name chunk missing or corrupted"));
	if (read_chunk(cf, MIDX_CHUNKID_OIDFANOUT, midx_read_oid_fanout, m))
		die(_("multi-pack-index required OID fanout chunk missing or corrupted"));
	if (read_chunk(cf, MIDX_CHUNKID_OIDLOOKUP, midx_read_oid_lookup, m))
		die(_("multi-pack-index required OID lookup chunk missing or corrupted"));
	if (read_chunk(cf, MIDX_CHUNKID_OBJECTOFFSETS, midx_read_object_offsets, m))
		die(_("multi-pack-index required object offsets chunk missing or corrupted"));

	pair_chunk(cf, MIDX_CHUNKID_LARGEOFFSETS, &m->chunk_large_offsets,
		   &m->chunk_large_offsets_len);
	if (git_env_bool("GIT_TEST_MIDX_READ_BTMP", 1))
		pair_chunk(cf, MIDX_CHUNKID_BITMAPPEDPACKS,
			   (const unsigned char **)&m->chunk_bitmapped_packs,
			   &m->chunk_bitmapped_packs_len);

	if (git_env_bool("GIT_TEST_MIDX_READ_RIDX", 1))
		pair_chunk(cf, MIDX_CHUNKID_REVINDEX, &m->chunk_revindex,
			   &m->chunk_revindex_len);

	CALLOC_ARRAY(m->pack_names, m->num_packs);
	CALLOC_ARRAY(m->packs, m->num_packs);

	cur_pack_name = (const char *)m->chunk_pack_names;
	for (i = 0; i < m->num_packs; i++) {
		const char *end;
		size_t avail = m->chunk_pack_names_len -
				(cur_pack_name - (const char *)m->chunk_pack_names);

		m->pack_names[i] = cur_pack_name;

		end = memchr(cur_pack_name, '\0', avail);
		if (!end)
			die(_("multi-pack-index pack-name chunk is too short"));
		cur_pack_name = end + 1;

		if (i && strcmp(m->pack_names[i], m->pack_names[i - 1]) <= 0)
			die(_("multi-pack-index pack names out of order: '%s' before '%s'"),
			      m->pack_names[i - 1],
			      m->pack_names[i]);
	}

	trace2_data_intmax("midx", the_repository, "load/num_packs", m->num_packs);
	trace2_data_intmax("midx", the_repository, "load/num_objects", m->num_objects);

	free_chunkfile(cf);
	return m;

cleanup_fail:
	free(m);
	strbuf_release(&midx_name);
	free_chunkfile(cf);
	if (midx_map)
		munmap(midx_map, midx_size);
	if (0 <= fd)
		close(fd);
	return NULL;
}

void close_midx(struct multi_pack_index *m)
{
	uint32_t i;

	if (!m)
		return;

	close_midx(m->next);

	munmap((unsigned char *)m->data, m->data_len);

	for (i = 0; i < m->num_packs; i++) {
		if (m->packs[i])
			m->packs[i]->multi_pack_index = 0;
	}
	FREE_AND_NULL(m->packs);
	FREE_AND_NULL(m->pack_names);
	free(m);
}

int prepare_midx_pack(struct repository *r, struct multi_pack_index *m, uint32_t pack_int_id)
{
	struct strbuf pack_name = STRBUF_INIT;
	struct packed_git *p;

	if (pack_int_id >= m->num_packs)
		die(_("bad pack-int-id: %u (%u total packs)"),
		    pack_int_id, m->num_packs);

	if (m->packs[pack_int_id])
		return 0;

	strbuf_addf(&pack_name, "%s/pack/%s", m->object_dir,
		    m->pack_names[pack_int_id]);

	p = add_packed_git(pack_name.buf, pack_name.len, m->local);
	strbuf_release(&pack_name);

	if (!p)
		return 1;

	p->multi_pack_index = 1;
	m->packs[pack_int_id] = p;
	install_packed_git(r, p);
	list_add_tail(&p->mru, &r->objects->packed_git_mru);

	return 0;
}

#define MIDX_CHUNK_BITMAPPED_PACKS_WIDTH (2 * sizeof(uint32_t))

int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m,
		       struct bitmapped_pack *bp, uint32_t pack_int_id)
{
	if (!m->chunk_bitmapped_packs)
		return error(_("MIDX does not contain the BTMP chunk"));

	if (prepare_midx_pack(r, m, pack_int_id))
		return error(_("could not load bitmapped pack %"PRIu32), pack_int_id);

	bp->p = m->packs[pack_int_id];
	bp->bitmap_pos = get_be32((char *)m->chunk_bitmapped_packs +
				  MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * pack_int_id);
	bp->bitmap_nr = get_be32((char *)m->chunk_bitmapped_packs +
				 MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * pack_int_id +
				 sizeof(uint32_t));
	bp->pack_int_id = pack_int_id;

	return 0;
}

int bsearch_midx(const struct object_id *oid, struct multi_pack_index *m, uint32_t *result)
{
	return bsearch_hash(oid->hash, m->chunk_oid_fanout, m->chunk_oid_lookup,
			    the_hash_algo->rawsz, result);
}

struct object_id *nth_midxed_object_oid(struct object_id *oid,
					struct multi_pack_index *m,
					uint32_t n)
{
	if (n >= m->num_objects)
		return NULL;

	oidread(oid, m->chunk_oid_lookup + st_mult(m->hash_len, n));
	return oid;
}

off_t nth_midxed_offset(struct multi_pack_index *m, uint32_t pos)
{
	const unsigned char *offset_data;
	uint32_t offset32;

	offset_data = m->chunk_object_offsets + (off_t)pos * MIDX_CHUNK_OFFSET_WIDTH;
	offset32 = get_be32(offset_data + sizeof(uint32_t));

	if (m->chunk_large_offsets && offset32 & MIDX_LARGE_OFFSET_NEEDED) {
		if (sizeof(off_t) < sizeof(uint64_t))
			die(_("multi-pack-index stores a 64-bit offset, but off_t is too small"));

		offset32 ^= MIDX_LARGE_OFFSET_NEEDED;
		if (offset32 >= m->chunk_large_offsets_len / sizeof(uint64_t))
			die(_("multi-pack-index large offset out of bounds"));
		return get_be64(m->chunk_large_offsets + sizeof(uint64_t) * offset32);
	}

	return offset32;
}

uint32_t nth_midxed_pack_int_id(struct multi_pack_index *m, uint32_t pos)
{
	return get_be32(m->chunk_object_offsets +
			(off_t)pos * MIDX_CHUNK_OFFSET_WIDTH);
}

int fill_midx_entry(struct repository *r,
		    const struct object_id *oid,
		    struct pack_entry *e,
		    struct multi_pack_index *m)
{
	uint32_t pos;
	uint32_t pack_int_id;
	struct packed_git *p;

	if (!bsearch_midx(oid, m, &pos))
		return 0;

	if (pos >= m->num_objects)
		return 0;

	pack_int_id = nth_midxed_pack_int_id(m, pos);

	if (prepare_midx_pack(r, m, pack_int_id))
		return 0;
	p = m->packs[pack_int_id];

	/*
	* 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 MIDX was
	* loaded!
	*/
	if (!is_pack_valid(p))
		return 0;

	if (oidset_size(&p->bad_objects) &&
	    oidset_contains(&p->bad_objects, oid))
		return 0;

	e->offset = nth_midxed_offset(m, pos);
	e->p = p;

	return 1;
}

/* Match "foo.idx" against either "foo.pack" _or_ "foo.idx". */
int cmp_idx_or_pack_name(const char *idx_or_pack_name,
			 const char *idx_name)
{
	/* Skip past any initial matching prefix. */
	while (*idx_name && *idx_name == *idx_or_pack_name) {
		idx_name++;
		idx_or_pack_name++;
	}

	/*
	 * If we didn't match completely, we may have matched "pack-1234." and
	 * be left with "idx" and "pack" respectively, which is also OK. We do
	 * not have to check for "idx" and "idx", because that would have been
	 * a complete match (and in that case these strcmps will be false, but
	 * we'll correctly return 0 from the final strcmp() below.
	 *
	 * Technically this matches "fooidx" and "foopack", but we'd never have
	 * such names in the first place.
	 */
	if (!strcmp(idx_name, "idx") && !strcmp(idx_or_pack_name, "pack"))
		return 0;

	/*
	 * This not only checks for a complete match, but also orders based on
	 * the first non-identical character, which means our ordering will
	 * match a raw strcmp(). That makes it OK to use this to binary search
	 * a naively-sorted list.
	 */
	return strcmp(idx_or_pack_name, idx_name);
}

int midx_locate_pack(struct multi_pack_index *m, const char *idx_or_pack_name,
		     uint32_t *pos)
{
	uint32_t first = 0, last = m->num_packs;

	while (first < last) {
		uint32_t mid = first + (last - first) / 2;
		const char *current;
		int cmp;

		current = m->pack_names[mid];
		cmp = cmp_idx_or_pack_name(idx_or_pack_name, current);
		if (!cmp) {
			if (pos)
				*pos = mid;
			return 1;
		}
		if (cmp > 0) {
			first = mid + 1;
			continue;
		}
		last = mid;
	}

	return 0;
}

int midx_contains_pack(struct multi_pack_index *m, const char *idx_or_pack_name)
{
	return midx_locate_pack(m, idx_or_pack_name, NULL);
}

int midx_preferred_pack(struct multi_pack_index *m, uint32_t *pack_int_id)
{
	if (m->preferred_pack_idx == -1) {
		if (load_midx_revindex(m) < 0) {
			m->preferred_pack_idx = -2;
			return -1;
		}

		m->preferred_pack_idx =
			nth_midxed_pack_int_id(m, pack_pos_to_midx(m, 0));
	} else if (m->preferred_pack_idx == -2)
		return -1; /* no revindex */

	*pack_int_id = m->preferred_pack_idx;
	return 0;
}

int prepare_multi_pack_index_one(struct repository *r, const char *object_dir, int local)
{
	struct multi_pack_index *m;
	struct multi_pack_index *m_search;

	prepare_repo_settings(r);
	if (!r->settings.core_multi_pack_index)
		return 0;

	for (m_search = r->objects->multi_pack_index; m_search; m_search = m_search->next)
		if (!strcmp(object_dir, m_search->object_dir))
			return 1;

	m = load_multi_pack_index(object_dir, local);

	if (m) {
		struct multi_pack_index *mp = r->objects->multi_pack_index;
		if (mp) {
			m->next = mp->next;
			mp->next = m;
		} else
			r->objects->multi_pack_index = m;
		return 1;
	}

	return 0;
}

int midx_checksum_valid(struct multi_pack_index *m)
{
	return hashfile_checksum_valid(m->data, m->data_len);
}

struct clear_midx_data {
	char *keep;
	const char *ext;
};

static void clear_midx_file_ext(const char *full_path, size_t full_path_len UNUSED,
				const char *file_name, void *_data)
{
	struct clear_midx_data *data = _data;

	if (!(starts_with(file_name, "multi-pack-index-") &&
	      ends_with(file_name, data->ext)))
		return;
	if (data->keep && !strcmp(data->keep, file_name))
		return;

	if (unlink(full_path))
		die_errno(_("failed to remove %s"), full_path);
}

void clear_midx_files_ext(const char *object_dir, const char *ext,
			  unsigned char *keep_hash)
{
	struct clear_midx_data data;
	memset(&data, 0, sizeof(struct clear_midx_data));

	if (keep_hash)
		data.keep = xstrfmt("multi-pack-index-%s%s",
				    hash_to_hex(keep_hash), ext);
	data.ext = ext;

	for_each_file_in_pack_dir(object_dir,
				  clear_midx_file_ext,
				  &data);

	free(data.keep);
}

void clear_midx_file(struct repository *r)
{
	struct strbuf midx = STRBUF_INIT;

	get_midx_filename(&midx, r->objects->odb->path);

	if (r->objects && r->objects->multi_pack_index) {
		close_midx(r->objects->multi_pack_index);
		r->objects->multi_pack_index = NULL;
	}

	if (remove_path(midx.buf))
		die(_("failed to clear multi-pack-index at %s"), midx.buf);

	clear_midx_files_ext(r->objects->odb->path, ".bitmap", NULL);
	clear_midx_files_ext(r->objects->odb->path, ".rev", NULL);

	strbuf_release(&midx);
}

static int verify_midx_error;

__attribute__((format (printf, 1, 2)))
static void midx_report(const char *fmt, ...)
{
	va_list ap;
	verify_midx_error = 1;
	va_start(ap, fmt);
	vfprintf(stderr, fmt, ap);
	fprintf(stderr, "\n");
	va_end(ap);
}

struct pair_pos_vs_id
{
	uint32_t pos;
	uint32_t pack_int_id;
};

static int compare_pair_pos_vs_id(const void *_a, const void *_b)
{
	struct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;
	struct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;

	return b->pack_int_id - a->pack_int_id;
}

/*
 * Limit calls to display_progress() for performance reasons.
 * The interval here was arbitrarily chosen.
 */
#define SPARSE_PROGRESS_INTERVAL (1 << 12)
#define midx_display_sparse_progress(progress, n) \
	do { \
		uint64_t _n = (n); \
		if ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0) \
			display_progress(progress, _n); \
	} while (0)

int verify_midx_file(struct repository *r, const char *object_dir, unsigned flags)
{
	struct pair_pos_vs_id *pairs = NULL;
	uint32_t i;
	struct progress *progress = NULL;
	struct multi_pack_index *m = load_multi_pack_index(object_dir, 1);
	verify_midx_error = 0;

	if (!m) {
		int result = 0;
		struct stat sb;
		struct strbuf filename = STRBUF_INIT;

		get_midx_filename(&filename, object_dir);

		if (!stat(filename.buf, &sb)) {
			error(_("multi-pack-index file exists, but failed to parse"));
			result = 1;
		}
		strbuf_release(&filename);
		return result;
	}

	if (!midx_checksum_valid(m))
		midx_report(_("incorrect checksum"));

	if (flags & MIDX_PROGRESS)
		progress = start_delayed_progress(_("Looking for referenced packfiles"),
					  m->num_packs);
	for (i = 0; i < m->num_packs; i++) {
		if (prepare_midx_pack(r, m, i))
			midx_report("failed to load pack in position %d", i);

		display_progress(progress, i + 1);
	}
	stop_progress(&progress);

	if (m->num_objects == 0) {
		midx_report(_("the midx contains no oid"));
		/*
		 * Remaining tests assume that we have objects, so we can
		 * return here.
		 */
		goto cleanup;
	}

	if (flags & MIDX_PROGRESS)
		progress = start_sparse_progress(_("Verifying OID order in multi-pack-index"),
						 m->num_objects - 1);
	for (i = 0; i < m->num_objects - 1; i++) {
		struct object_id oid1, oid2;

		nth_midxed_object_oid(&oid1, m, i);
		nth_midxed_object_oid(&oid2, m, i + 1);

		if (oidcmp(&oid1, &oid2) >= 0)
			midx_report(_("oid lookup out of order: oid[%d] = %s >= %s = oid[%d]"),
				    i, oid_to_hex(&oid1), oid_to_hex(&oid2), i + 1);

		midx_display_sparse_progress(progress, i + 1);
	}
	stop_progress(&progress);

	/*
	 * Create an array mapping each object to its packfile id.  Sort it
	 * to group the objects by packfile.  Use this permutation to visit
	 * each of the objects and only require 1 packfile to be open at a
	 * time.
	 */
	ALLOC_ARRAY(pairs, m->num_objects);
	for (i = 0; i < m->num_objects; i++) {
		pairs[i].pos = i;
		pairs[i].pack_int_id = nth_midxed_pack_int_id(m, i);
	}

	if (flags & MIDX_PROGRESS)
		progress = start_sparse_progress(_("Sorting objects by packfile"),
						 m->num_objects);
	display_progress(progress, 0); /* TODO: Measure QSORT() progress */
	QSORT(pairs, m->num_objects, compare_pair_pos_vs_id);
	stop_progress(&progress);

	if (flags & MIDX_PROGRESS)
		progress = start_sparse_progress(_("Verifying object offsets"), m->num_objects);
	for (i = 0; i < m->num_objects; i++) {
		struct object_id oid;
		struct pack_entry e;
		off_t m_offset, p_offset;

		if (i > 0 && pairs[i-1].pack_int_id != pairs[i].pack_int_id &&
		    m->packs[pairs[i-1].pack_int_id])
		{
			close_pack_fd(m->packs[pairs[i-1].pack_int_id]);
			close_pack_index(m->packs[pairs[i-1].pack_int_id]);
		}

		nth_midxed_object_oid(&oid, m, pairs[i].pos);

		if (!fill_midx_entry(r, &oid, &e, m)) {
			midx_report(_("failed to load pack entry for oid[%d] = %s"),
				    pairs[i].pos, oid_to_hex(&oid));
			continue;
		}

		if (open_pack_index(e.p)) {
			midx_report(_("failed to load pack-index for packfile %s"),
				    e.p->pack_name);
			break;
		}

		m_offset = e.offset;
		p_offset = find_pack_entry_one(oid.hash, e.p);

		if (m_offset != p_offset)
			midx_report(_("incorrect object offset for oid[%d] = %s: %"PRIx64" != %"PRIx64),
				    pairs[i].pos, oid_to_hex(&oid), m_offset, p_offset);

		midx_display_sparse_progress(progress, i + 1);
	}
	stop_progress(&progress);

cleanup:
	free(pairs);
	close_midx(m);

	return verify_midx_error;
}