[thirdparty/git.git] / midx.c

#include "cache.h"
#include "csum-file.h"
#include "dir.h"
#include "lockfile.h"
#include "packfile.h"
#include "object-store.h"
#include "packfile.h"
#include "midx.h"

#define MIDX_SIGNATURE 0x4d494458 /* "MIDX" */
#define MIDX_VERSION 1
#define MIDX_BYTE_FILE_VERSION 4
#define MIDX_BYTE_HASH_VERSION 5
#define MIDX_BYTE_NUM_CHUNKS 6
#define MIDX_BYTE_NUM_PACKS 8
#define MIDX_HASH_VERSION 1
#define MIDX_HEADER_SIZE 12
#define MIDX_HASH_LEN 20
#define MIDX_MIN_SIZE (MIDX_HEADER_SIZE + MIDX_HASH_LEN)

#define MIDX_MAX_CHUNKS 3
#define MIDX_CHUNK_ALIGNMENT 4
#define MIDX_CHUNKID_PACKNAMES 0x504e414d /* "PNAM" */
#define MIDX_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
#define MIDX_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
#define MIDX_CHUNKLOOKUP_WIDTH (sizeof(uint32_t) + sizeof(uint64_t))
#define MIDX_CHUNK_FANOUT_SIZE (sizeof(uint32_t) * 256)

static char *get_midx_filename(const char *object_dir)
{
	return xstrfmt("%s/pack/multi-pack-index", object_dir);
}

struct multi_pack_index *load_multi_pack_index(const char *object_dir)
{
	struct multi_pack_index *m = NULL;
	int fd;
	struct stat st;
	size_t midx_size;
	void *midx_map = NULL;
	uint32_t hash_version;
	char *midx_name = get_midx_filename(object_dir);
	uint32_t i;
	const char *cur_pack_name;

	fd = git_open(midx_name);

	if (fd < 0)
		goto cleanup_fail;
	if (fstat(fd, &st)) {
		error_errno(_("failed to read %s"), midx_name);
		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);
		goto cleanup_fail;
	}

	FREE_AND_NULL(midx_name);

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

	FLEX_ALLOC_MEM(m, object_dir, object_dir, strlen(object_dir));
	m->fd = fd;
	m->data = midx_map;
	m->data_len = midx_size;

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

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

	hash_version = m->data[MIDX_BYTE_HASH_VERSION];
	if (hash_version != MIDX_HASH_VERSION) {
		error(_("hash version %u does not match"), hash_version);
		goto cleanup_fail;
	}
	m->hash_len = MIDX_HASH_LEN;

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

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

	for (i = 0; i < m->num_chunks; i++) {
		uint32_t chunk_id = get_be32(m->data + MIDX_HEADER_SIZE +
					     MIDX_CHUNKLOOKUP_WIDTH * i);
		uint64_t chunk_offset = get_be64(m->data + MIDX_HEADER_SIZE + 4 +
						 MIDX_CHUNKLOOKUP_WIDTH * i);

		switch (chunk_id) {
			case MIDX_CHUNKID_PACKNAMES:
				m->chunk_pack_names = m->data + chunk_offset;
				break;

			case MIDX_CHUNKID_OIDFANOUT:
				m->chunk_oid_fanout = (uint32_t *)(m->data + chunk_offset);
				break;

			case MIDX_CHUNKID_OIDLOOKUP:
				m->chunk_oid_lookup = m->data + chunk_offset;
				break;

			case 0:
				die(_("terminating multi-pack-index chunk id appears earlier than expected"));
				break;

			default:
				/*
				 * Do nothing on unrecognized chunks, allowing future
				 * extensions to add optional chunks.
				 */
				break;
		}
	}

	if (!m->chunk_pack_names)
		die(_("multi-pack-index missing required pack-name chunk"));
	if (!m->chunk_oid_fanout)
		die(_("multi-pack-index missing required OID fanout chunk"));
	if (!m->chunk_oid_lookup)
		die(_("multi-pack-index missing required OID lookup chunk"));

	m->num_objects = ntohl(m->chunk_oid_fanout[255]);

	m->pack_names = xcalloc(m->num_packs, sizeof(*m->pack_names));

	cur_pack_name = (const char *)m->chunk_pack_names;
	for (i = 0; i < m->num_packs; i++) {
		m->pack_names[i] = cur_pack_name;

		cur_pack_name += strlen(cur_pack_name) + 1;

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

	return m;

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

static size_t write_midx_header(struct hashfile *f,
				unsigned char num_chunks,
				uint32_t num_packs)
{
	unsigned char byte_values[4];

	hashwrite_be32(f, MIDX_SIGNATURE);
	byte_values[0] = MIDX_VERSION;
	byte_values[1] = MIDX_HASH_VERSION;
	byte_values[2] = num_chunks;
	byte_values[3] = 0; /* unused */
	hashwrite(f, byte_values, sizeof(byte_values));
	hashwrite_be32(f, num_packs);

	return MIDX_HEADER_SIZE;
}

struct pack_list {
	struct packed_git **list;
	char **names;
	uint32_t nr;
	uint32_t alloc_list;
	uint32_t alloc_names;
	size_t pack_name_concat_len;
};

static void add_pack_to_midx(const char *full_path, size_t full_path_len,
			     const char *file_name, void *data)
{
	struct pack_list *packs = (struct pack_list *)data;

	if (ends_with(file_name, ".idx")) {
		ALLOC_GROW(packs->list, packs->nr + 1, packs->alloc_list);
		ALLOC_GROW(packs->names, packs->nr + 1, packs->alloc_names);

		packs->list[packs->nr] = add_packed_git(full_path,
							full_path_len,
							0);

		if (!packs->list[packs->nr]) {
			warning(_("failed to add packfile '%s'"),
				full_path);
			return;
		}

		if (open_pack_index(packs->list[packs->nr])) {
			warning(_("failed to open pack-index '%s'"),
				full_path);
			close_pack(packs->list[packs->nr]);
			FREE_AND_NULL(packs->list[packs->nr]);
			return;
		}

		packs->names[packs->nr] = xstrdup(file_name);
		packs->pack_name_concat_len += strlen(file_name) + 1;
		packs->nr++;
	}
}

struct pack_pair {
	uint32_t pack_int_id;
	char *pack_name;
};

static int pack_pair_compare(const void *_a, const void *_b)
{
	struct pack_pair *a = (struct pack_pair *)_a;
	struct pack_pair *b = (struct pack_pair *)_b;
	return strcmp(a->pack_name, b->pack_name);
}

static void sort_packs_by_name(char **pack_names, uint32_t nr_packs, uint32_t *perm)
{
	uint32_t i;
	struct pack_pair *pairs;

	ALLOC_ARRAY(pairs, nr_packs);

	for (i = 0; i < nr_packs; i++) {
		pairs[i].pack_int_id = i;
		pairs[i].pack_name = pack_names[i];
	}

	QSORT(pairs, nr_packs, pack_pair_compare);

	for (i = 0; i < nr_packs; i++) {
		pack_names[i] = pairs[i].pack_name;
		perm[pairs[i].pack_int_id] = i;
	}

	free(pairs);
}

struct pack_midx_entry {
	struct object_id oid;
	uint32_t pack_int_id;
	time_t pack_mtime;
	uint64_t offset;
};

static int midx_oid_compare(const void *_a, const void *_b)
{
	const struct pack_midx_entry *a = (const struct pack_midx_entry *)_a;
	const struct pack_midx_entry *b = (const struct pack_midx_entry *)_b;
	int cmp = oidcmp(&a->oid, &b->oid);

	if (cmp)
		return cmp;

	if (a->pack_mtime > b->pack_mtime)
		return -1;
	else if (a->pack_mtime < b->pack_mtime)
		return 1;

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

static void fill_pack_entry(uint32_t pack_int_id,
			    struct packed_git *p,
			    uint32_t cur_object,
			    struct pack_midx_entry *entry)
{
	if (!nth_packed_object_oid(&entry->oid, p, cur_object))
		die(_("failed to locate object %d in packfile"), cur_object);

	entry->pack_int_id = pack_int_id;
	entry->pack_mtime = p->mtime;

	entry->offset = nth_packed_object_offset(p, cur_object);
}

/*
 * It is possible to artificially get into a state where there are many
 * duplicate copies of objects. That can create high memory pressure if
 * we are to create a list of all objects before de-duplication. To reduce
 * this memory pressure without a significant performance drop, automatically
 * group objects by the first byte of their object id. Use the IDX fanout
 * tables to group the data, copy to a local array, then sort.
 *
 * Copy only the de-duplicated entries (selected by most-recent modified time
 * of a packfile containing the object).
 */
static struct pack_midx_entry *get_sorted_entries(struct packed_git **p,
						  uint32_t *perm,
						  uint32_t nr_packs,
						  uint32_t *nr_objects)
{
	uint32_t cur_fanout, cur_pack, cur_object;
	uint32_t alloc_fanout, alloc_objects, total_objects = 0;
	struct pack_midx_entry *entries_by_fanout = NULL;
	struct pack_midx_entry *deduplicated_entries = NULL;

	for (cur_pack = 0; cur_pack < nr_packs; cur_pack++)
		total_objects += p[cur_pack]->num_objects;

	/*
	 * As we de-duplicate by fanout value, we expect the fanout
	 * slices to be evenly distributed, with some noise. Hence,
	 * allocate slightly more than one 256th.
	 */
	alloc_objects = alloc_fanout = total_objects > 3200 ? total_objects / 200 : 16;

	ALLOC_ARRAY(entries_by_fanout, alloc_fanout);
	ALLOC_ARRAY(deduplicated_entries, alloc_objects);
	*nr_objects = 0;

	for (cur_fanout = 0; cur_fanout < 256; cur_fanout++) {
		uint32_t nr_fanout = 0;

		for (cur_pack = 0; cur_pack < nr_packs; cur_pack++) {
			uint32_t start = 0, end;

			if (cur_fanout)
				start = get_pack_fanout(p[cur_pack], cur_fanout - 1);
			end = get_pack_fanout(p[cur_pack], cur_fanout);

			for (cur_object = start; cur_object < end; cur_object++) {
				ALLOC_GROW(entries_by_fanout, nr_fanout + 1, alloc_fanout);
				fill_pack_entry(perm[cur_pack], p[cur_pack], cur_object, &entries_by_fanout[nr_fanout]);
				nr_fanout++;
			}
		}

		QSORT(entries_by_fanout, nr_fanout, midx_oid_compare);

		/*
		 * The batch is now sorted by OID and then mtime (descending).
		 * Take only the first duplicate.
		 */
		for (cur_object = 0; cur_object < nr_fanout; cur_object++) {
			if (cur_object && !oidcmp(&entries_by_fanout[cur_object - 1].oid,
						  &entries_by_fanout[cur_object].oid))
				continue;

			ALLOC_GROW(deduplicated_entries, *nr_objects + 1, alloc_objects);
			memcpy(&deduplicated_entries[*nr_objects],
			       &entries_by_fanout[cur_object],
			       sizeof(struct pack_midx_entry));
			(*nr_objects)++;
		}
	}

	free(entries_by_fanout);
	return deduplicated_entries;
}

static size_t write_midx_pack_names(struct hashfile *f,
				    char **pack_names,
				    uint32_t num_packs)
{
	uint32_t i;
	unsigned char padding[MIDX_CHUNK_ALIGNMENT];
	size_t written = 0;

	for (i = 0; i < num_packs; i++) {
		size_t writelen = strlen(pack_names[i]) + 1;

		if (i && strcmp(pack_names[i], pack_names[i - 1]) <= 0)
			BUG("incorrect pack-file order: %s before %s",
			    pack_names[i - 1],
			    pack_names[i]);

		hashwrite(f, pack_names[i], writelen);
		written += writelen;
	}

	/* add padding to be aligned */
	i = MIDX_CHUNK_ALIGNMENT - (written % MIDX_CHUNK_ALIGNMENT);
	if (i < MIDX_CHUNK_ALIGNMENT) {
		memset(padding, 0, sizeof(padding));
		hashwrite(f, padding, i);
		written += i;
	}

	return written;
}

static size_t write_midx_oid_fanout(struct hashfile *f,
				    struct pack_midx_entry *objects,
				    uint32_t nr_objects)
{
	struct pack_midx_entry *list = objects;
	struct pack_midx_entry *last = objects + nr_objects;
	uint32_t count = 0;
	uint32_t i;

	/*
	* Write the first-level table (the list is sorted,
	* but we use a 256-entry lookup to be able to avoid
	* having to do eight extra binary search iterations).
	*/
	for (i = 0; i < 256; i++) {
		struct pack_midx_entry *next = list;

		while (next < last && next->oid.hash[0] == i) {
			count++;
			next++;
		}

		hashwrite_be32(f, count);
		list = next;
	}

	return MIDX_CHUNK_FANOUT_SIZE;
}

static size_t write_midx_oid_lookup(struct hashfile *f, unsigned char hash_len,
				    struct pack_midx_entry *objects,
				    uint32_t nr_objects)
{
	struct pack_midx_entry *list = objects;
	uint32_t i;
	size_t written = 0;

	for (i = 0; i < nr_objects; i++) {
		struct pack_midx_entry *obj = list++;

		if (i < nr_objects - 1) {
			struct pack_midx_entry *next = list;
			if (oidcmp(&obj->oid, &next->oid) >= 0)
				BUG("OIDs not in order: %s >= %s",
				    oid_to_hex(&obj->oid),
				    oid_to_hex(&next->oid));
		}

		hashwrite(f, obj->oid.hash, (int)hash_len);
		written += hash_len;
	}

	return written;
}

int write_midx_file(const char *object_dir)
{
	unsigned char cur_chunk, num_chunks = 0;
	char *midx_name;
	uint32_t i;
	struct hashfile *f = NULL;
	struct lock_file lk;
	struct pack_list packs;
	uint32_t *pack_perm = NULL;
	uint64_t written = 0;
	uint32_t chunk_ids[MIDX_MAX_CHUNKS + 1];
	uint64_t chunk_offsets[MIDX_MAX_CHUNKS + 1];
	uint32_t nr_entries;
	struct pack_midx_entry *entries = NULL;

	midx_name = get_midx_filename(object_dir);
	if (safe_create_leading_directories(midx_name)) {
		UNLEAK(midx_name);
		die_errno(_("unable to create leading directories of %s"),
			  midx_name);
	}

	packs.nr = 0;
	packs.alloc_list = 16;
	packs.alloc_names = 16;
	packs.list = NULL;
	packs.pack_name_concat_len = 0;
	ALLOC_ARRAY(packs.list, packs.alloc_list);
	ALLOC_ARRAY(packs.names, packs.alloc_names);

	for_each_file_in_pack_dir(object_dir, add_pack_to_midx, &packs);

	if (packs.pack_name_concat_len % MIDX_CHUNK_ALIGNMENT)
		packs.pack_name_concat_len += MIDX_CHUNK_ALIGNMENT -
					      (packs.pack_name_concat_len % MIDX_CHUNK_ALIGNMENT);

	ALLOC_ARRAY(pack_perm, packs.nr);
	sort_packs_by_name(packs.names, packs.nr, pack_perm);

	entries = get_sorted_entries(packs.list, pack_perm, packs.nr, &nr_entries);

	hold_lock_file_for_update(&lk, midx_name, LOCK_DIE_ON_ERROR);
	f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
	FREE_AND_NULL(midx_name);

	cur_chunk = 0;
	num_chunks = 3;

	written = write_midx_header(f, num_chunks, packs.nr);

	chunk_ids[cur_chunk] = MIDX_CHUNKID_PACKNAMES;
	chunk_offsets[cur_chunk] = written + (num_chunks + 1) * MIDX_CHUNKLOOKUP_WIDTH;

	cur_chunk++;
	chunk_ids[cur_chunk] = MIDX_CHUNKID_OIDFANOUT;
	chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + packs.pack_name_concat_len;

	cur_chunk++;
	chunk_ids[cur_chunk] = MIDX_CHUNKID_OIDLOOKUP;
	chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + MIDX_CHUNK_FANOUT_SIZE;

	cur_chunk++;
	chunk_ids[cur_chunk] = 0;
	chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + nr_entries * MIDX_HASH_LEN;

	for (i = 0; i <= num_chunks; i++) {
		if (i && chunk_offsets[i] < chunk_offsets[i - 1])
			BUG("incorrect chunk offsets: %"PRIu64" before %"PRIu64,
			    chunk_offsets[i - 1],
			    chunk_offsets[i]);

		if (chunk_offsets[i] % MIDX_CHUNK_ALIGNMENT)
			BUG("chunk offset %"PRIu64" is not properly aligned",
			    chunk_offsets[i]);

		hashwrite_be32(f, chunk_ids[i]);
		hashwrite_be32(f, chunk_offsets[i] >> 32);
		hashwrite_be32(f, chunk_offsets[i]);

		written += MIDX_CHUNKLOOKUP_WIDTH;
	}

	for (i = 0; i < num_chunks; i++) {
		if (written != chunk_offsets[i])
			BUG("incorrect chunk offset (%"PRIu64" != %"PRIu64") for chunk id %"PRIx32,
			    chunk_offsets[i],
			    written,
			    chunk_ids[i]);

		switch (chunk_ids[i]) {
			case MIDX_CHUNKID_PACKNAMES:
				written += write_midx_pack_names(f, packs.names, packs.nr);
				break;

			case MIDX_CHUNKID_OIDFANOUT:
				written += write_midx_oid_fanout(f, entries, nr_entries);
				break;

			case MIDX_CHUNKID_OIDLOOKUP:
				written += write_midx_oid_lookup(f, MIDX_HASH_LEN, entries, nr_entries);
				break;

			default:
				BUG("trying to write unknown chunk id %"PRIx32,
				    chunk_ids[i]);
		}
	}

	if (written != chunk_offsets[num_chunks])
		BUG("incorrect final offset %"PRIu64" != %"PRIu64,
		    written,
		    chunk_offsets[num_chunks]);

	finalize_hashfile(f, NULL, CSUM_FSYNC | CSUM_HASH_IN_STREAM);
	commit_lock_file(&lk);

	for (i = 0; i < packs.nr; i++) {
		if (packs.list[i]) {
			close_pack(packs.list[i]);
			free(packs.list[i]);
		}
		free(packs.names[i]);
	}

	free(packs.list);
	free(packs.names);
	free(entries);
	return 0;
}
Commit	Line	Data
a3407730	1	#include "cache.h"
fc59e748	2	#include "csum-file.h"
396f2570	3	#include "dir.h"
fc59e748	4	#include "lockfile.h"
396f2570	5	#include "packfile.h"
4d80560c	6	#include "object-store.h"
fe1ed56f	7	#include "packfile.h"
a3407730 DS	8	#include "midx.h"
a3407730 DS	9
fc59e748 DS	10	#define MIDX_SIGNATURE 0x4d494458 /* "MIDX" */
fc59e748 DS	11	#define MIDX_VERSION 1
4d80560c DS	12	#define MIDX_BYTE_FILE_VERSION 4
	13	#define MIDX_BYTE_HASH_VERSION 5
	14	#define MIDX_BYTE_NUM_CHUNKS 6
	15	#define MIDX_BYTE_NUM_PACKS 8
fc59e748 DS	16	#define MIDX_HASH_VERSION 1
fc59e748 DS	17	#define MIDX_HEADER_SIZE 12
4d80560c DS	18	#define MIDX_HASH_LEN 20
4d80560c DS	19	#define MIDX_MIN_SIZE (MIDX_HEADER_SIZE + MIDX_HASH_LEN)
fc59e748	20
d7cacf29	21	#define MIDX_MAX_CHUNKS 3
32f3c541 DS	22	#define MIDX_CHUNK_ALIGNMENT 4
32f3c541 DS	23	#define MIDX_CHUNKID_PACKNAMES 0x504e414d /* "PNAM" */
d7cacf29	24	#define MIDX_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
0d5b3a5e	25	#define MIDX_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
32f3c541	26	#define MIDX_CHUNKLOOKUP_WIDTH (sizeof(uint32_t) + sizeof(uint64_t))
d7cacf29	27	#define MIDX_CHUNK_FANOUT_SIZE (sizeof(uint32_t) * 256)
32f3c541	28
fc59e748 DS	29	static char get_midx_filename(const char object_dir)
	30	{
	31	return xstrfmt("%s/pack/multi-pack-index", object_dir);
	32	}
	33
4d80560c DS	34	struct multi_pack_index load_multi_pack_index(const char object_dir)
	35	{
	36	struct multi_pack_index *m = NULL;
	37	int fd;
	38	struct stat st;
	39	size_t midx_size;
	40	void *midx_map = NULL;
	41	uint32_t hash_version;
	42	char *midx_name = get_midx_filename(object_dir);
32f3c541	43	uint32_t i;
3227565c	44	const char *cur_pack_name;
4d80560c DS	45
	46	fd = git_open(midx_name);
	47
	48	if (fd < 0)
	49	goto cleanup_fail;
	50	if (fstat(fd, &st)) {
	51	error_errno(_("failed to read %s"), midx_name);
	52	goto cleanup_fail;
	53	}
	54
	55	midx_size = xsize_t(st.st_size);
	56
	57	if (midx_size < MIDX_MIN_SIZE) {
	58	error(_("multi-pack-index file %s is too small"), midx_name);
	59	goto cleanup_fail;
	60	}
	61
	62	FREE_AND_NULL(midx_name);
	63
	64	midx_map = xmmap(NULL, midx_size, PROT_READ, MAP_PRIVATE, fd, 0);
	65
	66	FLEX_ALLOC_MEM(m, object_dir, object_dir, strlen(object_dir));
	67	m->fd = fd;
	68	m->data = midx_map;
	69	m->data_len = midx_size;
	70
	71	m->signature = get_be32(m->data);
	72	if (m->signature != MIDX_SIGNATURE) {
	73	error(_("multi-pack-index signature 0x%08x does not match signature 0x%08x"),
	74	m->signature, MIDX_SIGNATURE);
	75	goto cleanup_fail;
	76	}
	77
	78	m->version = m->data[MIDX_BYTE_FILE_VERSION];
	79	if (m->version != MIDX_VERSION) {
	80	error(_("multi-pack-index version %d not recognized"),
	81	m->version);
	82	goto cleanup_fail;
	83	}
	84
	85	hash_version = m->data[MIDX_BYTE_HASH_VERSION];
	86	if (hash_version != MIDX_HASH_VERSION) {
	87	error(_("hash version %u does not match"), hash_version);
	88	goto cleanup_fail;
	89	}
	90	m->hash_len = MIDX_HASH_LEN;
	91
	92	m->num_chunks = m->data[MIDX_BYTE_NUM_CHUNKS];
	93
	94	m->num_packs = get_be32(m->data + MIDX_BYTE_NUM_PACKS);
	95
32f3c541 DS	96	for (i = 0; i < m->num_chunks; i++) {
	97	uint32_t chunk_id = get_be32(m->data + MIDX_HEADER_SIZE +
	98	MIDX_CHUNKLOOKUP_WIDTH * i);
	99	uint64_t chunk_offset = get_be64(m->data + MIDX_HEADER_SIZE + 4 +
	100	MIDX_CHUNKLOOKUP_WIDTH * i);
	101
	102	switch (chunk_id) {
	103	case MIDX_CHUNKID_PACKNAMES:
	104	m->chunk_pack_names = m->data + chunk_offset;
	105	break;
	106
d7cacf29 DS	107	case MIDX_CHUNKID_OIDFANOUT:
	108	m->chunk_oid_fanout = (uint32_t *)(m->data + chunk_offset);
	109	break;
	110
0d5b3a5e DS	111	case MIDX_CHUNKID_OIDLOOKUP:
	112	m->chunk_oid_lookup = m->data + chunk_offset;
	113	break;
	114
32f3c541 DS	115	case 0:
	116	die(_("terminating multi-pack-index chunk id appears earlier than expected"));
	117	break;
	118
	119	default:
	120	/*
	121	* Do nothing on unrecognized chunks, allowing future
	122	* extensions to add optional chunks.
	123	*/
	124	break;
	125	}
	126	}
	127
	128	if (!m->chunk_pack_names)
	129	die(_("multi-pack-index missing required pack-name chunk"));
d7cacf29 DS	130	if (!m->chunk_oid_fanout)
d7cacf29 DS	131	die(_("multi-pack-index missing required OID fanout chunk"));
0d5b3a5e DS	132	if (!m->chunk_oid_lookup)
0d5b3a5e DS	133	die(_("multi-pack-index missing required OID lookup chunk"));
32f3c541	134
d7cacf29 DS	135	m->num_objects = ntohl(m->chunk_oid_fanout[255]);
d7cacf29 DS	136
3227565c DS	137	m->pack_names = xcalloc(m->num_packs, sizeof(*m->pack_names));
	138
	139	cur_pack_name = (const char *)m->chunk_pack_names;
	140	for (i = 0; i < m->num_packs; i++) {
	141	m->pack_names[i] = cur_pack_name;
	142
	143	cur_pack_name += strlen(cur_pack_name) + 1;
	144
	145	if (i && strcmp(m->pack_names[i], m->pack_names[i - 1]) <= 0) {
	146	error(_("multi-pack-index pack names out of order: '%s' before '%s'"),
	147	m->pack_names[i - 1],
	148	m->pack_names[i]);
	149	goto cleanup_fail;
	150	}
	151	}
	152
4d80560c DS	153	return m;
	154
	155	cleanup_fail:
	156	free(m);
	157	free(midx_name);
	158	if (midx_map)
	159	munmap(midx_map, midx_size);
	160	if (0 <= fd)
	161	close(fd);
	162	return NULL;
	163	}
	164
fc59e748 DS	165	static size_t write_midx_header(struct hashfile *f,
	166	unsigned char num_chunks,
	167	uint32_t num_packs)
	168	{
	169	unsigned char byte_values[4];
	170
	171	hashwrite_be32(f, MIDX_SIGNATURE);
	172	byte_values[0] = MIDX_VERSION;
	173	byte_values[1] = MIDX_HASH_VERSION;
	174	byte_values[2] = num_chunks;
	175	byte_values[3] = 0; /* unused */
	176	hashwrite(f, byte_values, sizeof(byte_values));
	177	hashwrite_be32(f, num_packs);
	178
	179	return MIDX_HEADER_SIZE;
	180	}
	181
396f2570 DS	182	struct pack_list {
396f2570 DS	183	struct packed_git **list;
32f3c541	184	char **names;
396f2570 DS	185	uint32_t nr;
396f2570 DS	186	uint32_t alloc_list;
32f3c541 DS	187	uint32_t alloc_names;
32f3c541 DS	188	size_t pack_name_concat_len;
396f2570 DS	189	};
	190
	191	static void add_pack_to_midx(const char *full_path, size_t full_path_len,
	192	const char file_name, void data)
	193	{
	194	struct pack_list packs = (struct pack_list )data;
	195
	196	if (ends_with(file_name, ".idx")) {
	197	ALLOC_GROW(packs->list, packs->nr + 1, packs->alloc_list);
32f3c541	198	ALLOC_GROW(packs->names, packs->nr + 1, packs->alloc_names);
396f2570 DS	199
	200	packs->list[packs->nr] = add_packed_git(full_path,
	201	full_path_len,
	202	0);
fe1ed56f	203
396f2570 DS	204	if (!packs->list[packs->nr]) {
	205	warning(_("failed to add packfile '%s'"),
	206	full_path);
	207	return;
	208	}
	209
fe1ed56f DS	210	if (open_pack_index(packs->list[packs->nr])) {
	211	warning(_("failed to open pack-index '%s'"),
	212	full_path);
	213	close_pack(packs->list[packs->nr]);
	214	FREE_AND_NULL(packs->list[packs->nr]);
	215	return;
	216	}
	217
32f3c541 DS	218	packs->names[packs->nr] = xstrdup(file_name);
32f3c541 DS	219	packs->pack_name_concat_len += strlen(file_name) + 1;
396f2570 DS	220	packs->nr++;
	221	}
	222	}
	223
32f3c541 DS	224	struct pack_pair {
	225	uint32_t pack_int_id;
	226	char *pack_name;
	227	};
	228
	229	static int pack_pair_compare(const void _a, const void _b)
	230	{
	231	struct pack_pair a = (struct pack_pair )_a;
	232	struct pack_pair b = (struct pack_pair )_b;
	233	return strcmp(a->pack_name, b->pack_name);
	234	}
	235
	236	static void sort_packs_by_name(char *pack_names, uint32_t nr_packs, uint32_t perm)
	237	{
	238	uint32_t i;
	239	struct pack_pair *pairs;
	240
	241	ALLOC_ARRAY(pairs, nr_packs);
	242
	243	for (i = 0; i < nr_packs; i++) {
	244	pairs[i].pack_int_id = i;
	245	pairs[i].pack_name = pack_names[i];
	246	}
	247
	248	QSORT(pairs, nr_packs, pack_pair_compare);
	249
	250	for (i = 0; i < nr_packs; i++) {
	251	pack_names[i] = pairs[i].pack_name;
	252	perm[pairs[i].pack_int_id] = i;
	253	}
	254
	255	free(pairs);
	256	}
	257
fe1ed56f DS	258	struct pack_midx_entry {
	259	struct object_id oid;
	260	uint32_t pack_int_id;
	261	time_t pack_mtime;
	262	uint64_t offset;
	263	};
	264
	265	static int midx_oid_compare(const void _a, const void _b)
	266	{
	267	const struct pack_midx_entry a = (const struct pack_midx_entry )_a;
	268	const struct pack_midx_entry b = (const struct pack_midx_entry )_b;
	269	int cmp = oidcmp(&a->oid, &b->oid);
	270
	271	if (cmp)
	272	return cmp;
	273
	274	if (a->pack_mtime > b->pack_mtime)
	275	return -1;
	276	else if (a->pack_mtime < b->pack_mtime)
	277	return 1;
	278
	279	return a->pack_int_id - b->pack_int_id;
	280	}
	281
	282	static void fill_pack_entry(uint32_t pack_int_id,
	283	struct packed_git *p,
	284	uint32_t cur_object,
	285	struct pack_midx_entry *entry)
	286	{
	287	if (!nth_packed_object_oid(&entry->oid, p, cur_object))
	288	die(_("failed to locate object %d in packfile"), cur_object);
	289
	290	entry->pack_int_id = pack_int_id;
	291	entry->pack_mtime = p->mtime;
	292
	293	entry->offset = nth_packed_object_offset(p, cur_object);
	294	}
	295
	296	/*
	297	* It is possible to artificially get into a state where there are many
	298	* duplicate copies of objects. That can create high memory pressure if
	299	* we are to create a list of all objects before de-duplication. To reduce
	300	* this memory pressure without a significant performance drop, automatically
	301	* group objects by the first byte of their object id. Use the IDX fanout
	302	* tables to group the data, copy to a local array, then sort.
	303	*
	304	* Copy only the de-duplicated entries (selected by most-recent modified time
	305	* of a packfile containing the object).
	306	*/
	307	static struct pack_midx_entry get_sorted_entries(struct packed_git *p,
	308	uint32_t *perm,
	309	uint32_t nr_packs,
	310	uint32_t *nr_objects)
	311	{
	312	uint32_t cur_fanout, cur_pack, cur_object;
	313	uint32_t alloc_fanout, alloc_objects, total_objects = 0;
	314	struct pack_midx_entry *entries_by_fanout = NULL;
	315	struct pack_midx_entry *deduplicated_entries = NULL;
	316
	317	for (cur_pack = 0; cur_pack < nr_packs; cur_pack++)
	318	total_objects += p[cur_pack]->num_objects;
	319
	320	/*
	321	* As we de-duplicate by fanout value, we expect the fanout
322	* slices to be evenly distributed, with some noise. Hence,
323	* allocate slightly more than one 256th.
324	*/
325	alloc_objects = alloc_fanout = total_objects > 3200 ? total_objects / 200 : 16;
326
327	ALLOC_ARRAY(entries_by_fanout, alloc_fanout);
328	ALLOC_ARRAY(deduplicated_entries, alloc_objects);
329	*nr_objects = 0;
330
331	for (cur_fanout = 0; cur_fanout < 256; cur_fanout++) {
332	uint32_t nr_fanout = 0;
333
334	for (cur_pack = 0; cur_pack < nr_packs; cur_pack++) {
335	uint32_t start = 0, end;
336
337	if (cur_fanout)
338	start = get_pack_fanout(p[cur_pack], cur_fanout - 1);
339	end = get_pack_fanout(p[cur_pack], cur_fanout);
340
341	for (cur_object = start; cur_object < end; cur_object++) {
342	ALLOC_GROW(entries_by_fanout, nr_fanout + 1, alloc_fanout);
343	fill_pack_entry(perm[cur_pack], p[cur_pack], cur_object, &entries_by_fanout[nr_fanout]);
344	nr_fanout++;
345	}
346	}
347
348	QSORT(entries_by_fanout, nr_fanout, midx_oid_compare);
349
350	/*
351	* The batch is now sorted by OID and then mtime (descending).
352	* Take only the first duplicate.
353	*/
354	for (cur_object = 0; cur_object < nr_fanout; cur_object++) {
355	if (cur_object && !oidcmp(&entries_by_fanout[cur_object - 1].oid,
356	&entries_by_fanout[cur_object].oid))
357	continue;
358
359	ALLOC_GROW(deduplicated_entries, *nr_objects + 1, alloc_objects);
360	memcpy(&deduplicated_entries[*nr_objects],
361	&entries_by_fanout[cur_object],
362	sizeof(struct pack_midx_entry));
363	(*nr_objects)++;
364	}
365	}
366
367	free(entries_by_fanout);
368	return deduplicated_entries;
369	}
370
32f3c541 DS	371	static size_t write_midx_pack_names(struct hashfile *f,
	372	char **pack_names,
	373	uint32_t num_packs)
	374	{
	375	uint32_t i;
	376	unsigned char padding[MIDX_CHUNK_ALIGNMENT];
	377	size_t written = 0;
	378
	379	for (i = 0; i < num_packs; i++) {
	380	size_t writelen = strlen(pack_names[i]) + 1;
	381
	382	if (i && strcmp(pack_names[i], pack_names[i - 1]) <= 0)
	383	BUG("incorrect pack-file order: %s before %s",
	384	pack_names[i - 1],
	385	pack_names[i]);
	386
	387	hashwrite(f, pack_names[i], writelen);
	388	written += writelen;
	389	}
	390
	391	/* add padding to be aligned */
	392	i = MIDX_CHUNK_ALIGNMENT - (written % MIDX_CHUNK_ALIGNMENT);
	393	if (i < MIDX_CHUNK_ALIGNMENT) {
	394	memset(padding, 0, sizeof(padding));
	395	hashwrite(f, padding, i);
	396	written += i;
	397	}
	398
	399	return written;
	400	}
	401
d7cacf29 DS	402	static size_t write_midx_oid_fanout(struct hashfile *f,
	403	struct pack_midx_entry *objects,
	404	uint32_t nr_objects)
	405	{
	406	struct pack_midx_entry *list = objects;
	407	struct pack_midx_entry *last = objects + nr_objects;
	408	uint32_t count = 0;
	409	uint32_t i;
	410
	411	/*
	412	* Write the first-level table (the list is sorted,
	413	* but we use a 256-entry lookup to be able to avoid
	414	* having to do eight extra binary search iterations).
	415	*/
	416	for (i = 0; i < 256; i++) {
	417	struct pack_midx_entry *next = list;
	418
	419	while (next < last && next->oid.hash[0] == i) {
	420	count++;
	421	next++;
	422	}
	423
	424	hashwrite_be32(f, count);
	425	list = next;
	426	}
	427
	428	return MIDX_CHUNK_FANOUT_SIZE;
	429	}
	430
0d5b3a5e DS	431	static size_t write_midx_oid_lookup(struct hashfile *f, unsigned char hash_len,
	432	struct pack_midx_entry *objects,
	433	uint32_t nr_objects)
	434	{
	435	struct pack_midx_entry *list = objects;
	436	uint32_t i;
	437	size_t written = 0;
	438
	439	for (i = 0; i < nr_objects; i++) {
	440	struct pack_midx_entry *obj = list++;
	441
	442	if (i < nr_objects - 1) {
	443	struct pack_midx_entry *next = list;
	444	if (oidcmp(&obj->oid, &next->oid) >= 0)
	445	BUG("OIDs not in order: %s >= %s",
	446	oid_to_hex(&obj->oid),
	447	oid_to_hex(&next->oid));
	448	}
	449
	450	hashwrite(f, obj->oid.hash, (int)hash_len);
	451	written += hash_len;
	452	}
	453
	454	return written;
	455	}
	456
a3407730 DS	457	int write_midx_file(const char *object_dir)
a3407730 DS	458	{
32f3c541	459	unsigned char cur_chunk, num_chunks = 0;
fc59e748	460	char *midx_name;
396f2570	461	uint32_t i;
fc59e748 DS	462	struct hashfile *f = NULL;
fc59e748 DS	463	struct lock_file lk;
396f2570	464	struct pack_list packs;
32f3c541 DS	465	uint32_t *pack_perm = NULL;
	466	uint64_t written = 0;
	467	uint32_t chunk_ids[MIDX_MAX_CHUNKS + 1];
	468	uint64_t chunk_offsets[MIDX_MAX_CHUNKS + 1];
fe1ed56f DS	469	uint32_t nr_entries;
fe1ed56f DS	470	struct pack_midx_entry *entries = NULL;
fc59e748 DS	471
	472	midx_name = get_midx_filename(object_dir);
	473	if (safe_create_leading_directories(midx_name)) {
	474	UNLEAK(midx_name);
	475	die_errno(_("unable to create leading directories of %s"),
	476	midx_name);
	477	}
	478
396f2570 DS	479	packs.nr = 0;
396f2570 DS	480	packs.alloc_list = 16;
32f3c541	481	packs.alloc_names = 16;
396f2570	482	packs.list = NULL;
32f3c541	483	packs.pack_name_concat_len = 0;
396f2570	484	ALLOC_ARRAY(packs.list, packs.alloc_list);
32f3c541	485	ALLOC_ARRAY(packs.names, packs.alloc_names);
396f2570 DS	486
	487	for_each_file_in_pack_dir(object_dir, add_pack_to_midx, &packs);
	488
32f3c541 DS	489	if (packs.pack_name_concat_len % MIDX_CHUNK_ALIGNMENT)
	490	packs.pack_name_concat_len += MIDX_CHUNK_ALIGNMENT -
	491	(packs.pack_name_concat_len % MIDX_CHUNK_ALIGNMENT);
	492
	493	ALLOC_ARRAY(pack_perm, packs.nr);
	494	sort_packs_by_name(packs.names, packs.nr, pack_perm);
	495
fe1ed56f DS	496	entries = get_sorted_entries(packs.list, pack_perm, packs.nr, &nr_entries);
fe1ed56f DS	497
fc59e748 DS	498	hold_lock_file_for_update(&lk, midx_name, LOCK_DIE_ON_ERROR);
	499	f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
	500	FREE_AND_NULL(midx_name);
	501
32f3c541	502	cur_chunk = 0;
d7cacf29	503	num_chunks = 3;
32f3c541 DS	504
	505	written = write_midx_header(f, num_chunks, packs.nr);
	506
	507	chunk_ids[cur_chunk] = MIDX_CHUNKID_PACKNAMES;
	508	chunk_offsets[cur_chunk] = written + (num_chunks + 1) * MIDX_CHUNKLOOKUP_WIDTH;
	509
	510	cur_chunk++;
d7cacf29	511	chunk_ids[cur_chunk] = MIDX_CHUNKID_OIDFANOUT;
32f3c541 DS	512	chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + packs.pack_name_concat_len;
32f3c541 DS	513
d7cacf29 DS	514	cur_chunk++;
	515	chunk_ids[cur_chunk] = MIDX_CHUNKID_OIDLOOKUP;
	516	chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + MIDX_CHUNK_FANOUT_SIZE;
	517
0d5b3a5e DS	518	cur_chunk++;
	519	chunk_ids[cur_chunk] = 0;
	520	chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + nr_entries * MIDX_HASH_LEN;
	521
32f3c541 DS	522	for (i = 0; i <= num_chunks; i++) {
	523	if (i && chunk_offsets[i] < chunk_offsets[i - 1])
	524	BUG("incorrect chunk offsets: %"PRIu64" before %"PRIu64,
	525	chunk_offsets[i - 1],
	526	chunk_offsets[i]);
	527
	528	if (chunk_offsets[i] % MIDX_CHUNK_ALIGNMENT)
	529	BUG("chunk offset %"PRIu64" is not properly aligned",
	530	chunk_offsets[i]);
	531
	532	hashwrite_be32(f, chunk_ids[i]);
	533	hashwrite_be32(f, chunk_offsets[i] >> 32);
	534	hashwrite_be32(f, chunk_offsets[i]);
	535
	536	written += MIDX_CHUNKLOOKUP_WIDTH;
	537	}
	538
	539	for (i = 0; i < num_chunks; i++) {
	540	if (written != chunk_offsets[i])
	541	BUG("incorrect chunk offset (%"PRIu64" != %"PRIu64") for chunk id %"PRIx32,
	542	chunk_offsets[i],
	543	written,
	544	chunk_ids[i]);
	545
	546	switch (chunk_ids[i]) {
	547	case MIDX_CHUNKID_PACKNAMES:
	548	written += write_midx_pack_names(f, packs.names, packs.nr);
	549	break;
	550
d7cacf29 DS	551	case MIDX_CHUNKID_OIDFANOUT:
	552	written += write_midx_oid_fanout(f, entries, nr_entries);
	553	break;
	554
0d5b3a5e DS	555	case MIDX_CHUNKID_OIDLOOKUP:
	556	written += write_midx_oid_lookup(f, MIDX_HASH_LEN, entries, nr_entries);
	557	break;
	558
32f3c541 DS	559	default:
	560	BUG("trying to write unknown chunk id %"PRIx32,
	561	chunk_ids[i]);
	562	}
	563	}
	564
	565	if (written != chunk_offsets[num_chunks])
	566	BUG("incorrect final offset %"PRIu64" != %"PRIu64,
	567	written,
	568	chunk_offsets[num_chunks]);
fc59e748 DS	569
	570	finalize_hashfile(f, NULL, CSUM_FSYNC \| CSUM_HASH_IN_STREAM);
	571	commit_lock_file(&lk);
	572
396f2570 DS	573	for (i = 0; i < packs.nr; i++) {
	574	if (packs.list[i]) {
	575	close_pack(packs.list[i]);
	576	free(packs.list[i]);
	577	}
32f3c541	578	free(packs.names[i]);
396f2570 DS	579	}
	580
	581	free(packs.list);
32f3c541	582	free(packs.names);
fe1ed56f	583	free(entries);
a3407730 DS	584	return 0;
a3407730 DS	585	}