[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 1
#define MIDX_CHUNK_ALIGNMENT 4
#define MIDX_CHUNKID_PACKNAMES 0x504e414d /* "PNAM" */
#define MIDX_CHUNKLOOKUP_WIDTH (sizeof(uint32_t) + sizeof(uint64_t))

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

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

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 = 1;

	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] = 0;
	chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + packs.pack_name_concat_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;

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