[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 5
#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_CHUNKID_OBJECTOFFSETS 0x4f4f4646 /* "OOFF" */
#define MIDX_CHUNKID_LARGEOFFSETS 0x4c4f4646 /* "LOFF" */
#define MIDX_CHUNKLOOKUP_WIDTH (sizeof(uint32_t) + sizeof(uint64_t))
#define MIDX_CHUNK_FANOUT_SIZE (sizeof(uint32_t) * 256)
#define MIDX_CHUNK_OFFSET_WIDTH (2 * sizeof(uint32_t))
#define MIDX_CHUNK_LARGE_OFFSET_WIDTH (sizeof(uint64_t))
#define MIDX_LARGE_OFFSET_NEEDED 0x80000000

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 MIDX_CHUNKID_OBJECTOFFSETS:
				m->chunk_object_offsets = m->data + chunk_offset;
				break;

			case MIDX_CHUNKID_LARGEOFFSETS:
				m->chunk_large_offsets = 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"));
	if (!m->chunk_object_offsets)
		die(_("multi-pack-index missing required object offsets 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;
}

static size_t write_midx_object_offsets(struct hashfile *f, int large_offset_needed,
					struct pack_midx_entry *objects, uint32_t nr_objects)
{
	struct pack_midx_entry *list = objects;
	uint32_t i, nr_large_offset = 0;
	size_t written = 0;

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

		hashwrite_be32(f, obj->pack_int_id);

		if (large_offset_needed && obj->offset >> 31)
			hashwrite_be32(f, MIDX_LARGE_OFFSET_NEEDED | nr_large_offset++);
		else if (!large_offset_needed && obj->offset >> 32)
			BUG("object %s requires a large offset (%"PRIx64") but the MIDX is not writing large offsets!",
			    oid_to_hex(&obj->oid),
			    obj->offset);
		else
			hashwrite_be32(f, (uint32_t)obj->offset);

		written += MIDX_CHUNK_OFFSET_WIDTH;
	}

	return written;
}

static size_t write_midx_large_offsets(struct hashfile *f, uint32_t nr_large_offset,
				       struct pack_midx_entry *objects, uint32_t nr_objects)
{
	struct pack_midx_entry *list = objects;
	size_t written = 0;

	while (nr_large_offset) {
		struct pack_midx_entry *obj = list++;
		uint64_t offset = obj->offset;

		if (!(offset >> 31))
			continue;

		hashwrite_be32(f, offset >> 32);
		hashwrite_be32(f, offset & 0xffffffffUL);
		written += 2 * sizeof(uint32_t);

		nr_large_offset--;
	}

	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, num_large_offsets = 0;
	struct pack_midx_entry *entries = NULL;
	int large_offsets_needed = 0;

	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);
	for (i = 0; i < nr_entries; i++) {
		if (entries[i].offset > 0x7fffffff)
			num_large_offsets++;
		if (entries[i].offset > 0xffffffff)
			large_offsets_needed = 1;
	}

	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 = large_offsets_needed ? 5 : 4;

	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] = MIDX_CHUNKID_OBJECTOFFSETS;
	chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + nr_entries * MIDX_HASH_LEN;

	cur_chunk++;
	chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + nr_entries * MIDX_CHUNK_OFFSET_WIDTH;
	if (large_offsets_needed) {
		chunk_ids[cur_chunk] = MIDX_CHUNKID_LARGEOFFSETS;

		cur_chunk++;
		chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] +
					   num_large_offsets * MIDX_CHUNK_LARGE_OFFSET_WIDTH;
	}

	chunk_ids[cur_chunk] = 0;

	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;

			case MIDX_CHUNKID_OBJECTOFFSETS:
				written += write_midx_object_offsets(f, large_offsets_needed, entries, nr_entries);
				break;

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