[thirdparty/git.git] / commit-graph.c

#include "cache.h"
#include "config.h"
#include "git-compat-util.h"
#include "lockfile.h"
#include "pack.h"
#include "packfile.h"
#include "commit.h"
#include "object.h"
#include "revision.h"
#include "sha1-lookup.h"
#include "commit-graph.h"

#define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
#define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
#define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
#define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
#define GRAPH_CHUNKID_LARGEEDGES 0x45444745 /* "EDGE" */

#define GRAPH_DATA_WIDTH 36

#define GRAPH_VERSION_1 0x1
#define GRAPH_VERSION GRAPH_VERSION_1

#define GRAPH_OID_VERSION_SHA1 1
#define GRAPH_OID_LEN_SHA1 GIT_SHA1_RAWSZ
#define GRAPH_OID_VERSION GRAPH_OID_VERSION_SHA1
#define GRAPH_OID_LEN GRAPH_OID_LEN_SHA1

#define GRAPH_OCTOPUS_EDGES_NEEDED 0x80000000
#define GRAPH_PARENT_MISSING 0x7fffffff
#define GRAPH_EDGE_LAST_MASK 0x7fffffff
#define GRAPH_PARENT_NONE 0x70000000

#define GRAPH_LAST_EDGE 0x80000000

#define GRAPH_FANOUT_SIZE (4 * 256)
#define GRAPH_CHUNKLOOKUP_WIDTH 12
#define GRAPH_MIN_SIZE (5 * GRAPH_CHUNKLOOKUP_WIDTH + GRAPH_FANOUT_SIZE + \
			GRAPH_OID_LEN + 8)


static char *get_commit_graph_filename(const char *obj_dir)
{
	return xstrfmt("%s/info/commit-graph", obj_dir);
}

static void write_graph_chunk_fanout(struct hashfile *f,
				     struct commit **commits,
				     int nr_commits)
{
	int i, count = 0;
	struct commit **list = commits;

	/*
	 * 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++) {
		while (count < nr_commits) {
			if ((*list)->object.oid.hash[0] != i)
				break;
			count++;
			list++;
		}

		hashwrite_be32(f, count);
	}
}

static void write_graph_chunk_oids(struct hashfile *f, int hash_len,
				   struct commit **commits, int nr_commits)
{
	struct commit **list = commits;
	int count;
	for (count = 0; count < nr_commits; count++, list++)
		hashwrite(f, (*list)->object.oid.hash, (int)hash_len);
}

static const unsigned char *commit_to_sha1(size_t index, void *table)
{
	struct commit **commits = table;
	return commits[index]->object.oid.hash;
}

static void write_graph_chunk_data(struct hashfile *f, int hash_len,
				   struct commit **commits, int nr_commits)
{
	struct commit **list = commits;
	struct commit **last = commits + nr_commits;
	uint32_t num_extra_edges = 0;

	while (list < last) {
		struct commit_list *parent;
		int edge_value;
		uint32_t packedDate[2];

		parse_commit(*list);
		hashwrite(f, (*list)->tree->object.oid.hash, hash_len);

		parent = (*list)->parents;

		if (!parent)
			edge_value = GRAPH_PARENT_NONE;
		else {
			edge_value = sha1_pos(parent->item->object.oid.hash,
					      commits,
					      nr_commits,
					      commit_to_sha1);

			if (edge_value < 0)
				edge_value = GRAPH_PARENT_MISSING;
		}

		hashwrite_be32(f, edge_value);

		if (parent)
			parent = parent->next;

		if (!parent)
			edge_value = GRAPH_PARENT_NONE;
		else if (parent->next)
			edge_value = GRAPH_OCTOPUS_EDGES_NEEDED | num_extra_edges;
		else {
			edge_value = sha1_pos(parent->item->object.oid.hash,
					      commits,
					      nr_commits,
					      commit_to_sha1);
			if (edge_value < 0)
				edge_value = GRAPH_PARENT_MISSING;
		}

		hashwrite_be32(f, edge_value);

		if (edge_value & GRAPH_OCTOPUS_EDGES_NEEDED) {
			do {
				num_extra_edges++;
				parent = parent->next;
			} while (parent);
		}

		if (sizeof((*list)->date) > 4)
			packedDate[0] = htonl(((*list)->date >> 32) & 0x3);
		else
			packedDate[0] = 0;

		packedDate[1] = htonl((*list)->date);
		hashwrite(f, packedDate, 8);

		list++;
	}
}

static void write_graph_chunk_large_edges(struct hashfile *f,
					  struct commit **commits,
					  int nr_commits)
{
	struct commit **list = commits;
	struct commit **last = commits + nr_commits;
	struct commit_list *parent;

	while (list < last) {
		int num_parents = 0;
		for (parent = (*list)->parents; num_parents < 3 && parent;
		     parent = parent->next)
			num_parents++;

		if (num_parents <= 2) {
			list++;
			continue;
		}

		/* Since num_parents > 2, this initializer is safe. */
		for (parent = (*list)->parents->next; parent; parent = parent->next) {
			int edge_value = sha1_pos(parent->item->object.oid.hash,
						  commits,
						  nr_commits,
						  commit_to_sha1);

			if (edge_value < 0)
				edge_value = GRAPH_PARENT_MISSING;
			else if (!parent->next)
				edge_value |= GRAPH_LAST_EDGE;

			hashwrite_be32(f, edge_value);
		}

		list++;
	}
}

static int commit_compare(const void *_a, const void *_b)
{
	const struct object_id *a = (const struct object_id *)_a;
	const struct object_id *b = (const struct object_id *)_b;
	return oidcmp(a, b);
}

struct packed_commit_list {
	struct commit **list;
	int nr;
	int alloc;
};

struct packed_oid_list {
	struct object_id *list;
	int nr;
	int alloc;
};

static int add_packed_commits(const struct object_id *oid,
			      struct packed_git *pack,
			      uint32_t pos,
			      void *data)
{
	struct packed_oid_list *list = (struct packed_oid_list*)data;
	enum object_type type;
	off_t offset = nth_packed_object_offset(pack, pos);
	struct object_info oi = OBJECT_INFO_INIT;

	oi.typep = &type;
	if (packed_object_info(pack, offset, &oi) < 0)
		die("unable to get type of object %s", oid_to_hex(oid));

	if (type != OBJ_COMMIT)
		return 0;

	ALLOC_GROW(list->list, list->nr + 1, list->alloc);
	oidcpy(&(list->list[list->nr]), oid);
	list->nr++;

	return 0;
}

void write_commit_graph(const char *obj_dir)
{
	struct packed_oid_list oids;
	struct packed_commit_list commits;
	struct hashfile *f;
	uint32_t i, count_distinct = 0;
	char *graph_name;
	int fd;
	struct lock_file lk = LOCK_INIT;
	uint32_t chunk_ids[5];
	uint64_t chunk_offsets[5];
	int num_chunks;
	int num_extra_edges;
	struct commit_list *parent;

	oids.nr = 0;
	oids.alloc = approximate_object_count() / 4;

	if (oids.alloc < 1024)
		oids.alloc = 1024;
	ALLOC_ARRAY(oids.list, oids.alloc);

	for_each_packed_object(add_packed_commits, &oids, 0);

	QSORT(oids.list, oids.nr, commit_compare);

	count_distinct = 1;
	for (i = 1; i < oids.nr; i++) {
		if (oidcmp(&oids.list[i-1], &oids.list[i]))
			count_distinct++;
	}

	if (count_distinct >= GRAPH_PARENT_MISSING)
		die(_("the commit graph format cannot write %d commits"), count_distinct);

	commits.nr = 0;
	commits.alloc = count_distinct;
	ALLOC_ARRAY(commits.list, commits.alloc);

	num_extra_edges = 0;
	for (i = 0; i < oids.nr; i++) {
		int num_parents = 0;
		if (i > 0 && !oidcmp(&oids.list[i-1], &oids.list[i]))
			continue;

		commits.list[commits.nr] = lookup_commit(&oids.list[i]);
		parse_commit(commits.list[commits.nr]);

		for (parent = commits.list[commits.nr]->parents;
		     parent; parent = parent->next)
			num_parents++;

		if (num_parents > 2)
			num_extra_edges += num_parents - 1;

		commits.nr++;
	}
	num_chunks = num_extra_edges ? 4 : 3;

	if (commits.nr >= GRAPH_PARENT_MISSING)
		die(_("too many commits to write graph"));

	graph_name = get_commit_graph_filename(obj_dir);
	fd = hold_lock_file_for_update(&lk, graph_name, 0);

	if (fd < 0) {
		struct strbuf folder = STRBUF_INIT;
		strbuf_addstr(&folder, graph_name);
		strbuf_setlen(&folder, strrchr(folder.buf, '/') - folder.buf);

		if (mkdir(folder.buf, 0777) < 0)
			die_errno(_("cannot mkdir %s"), folder.buf);
		strbuf_release(&folder);

		fd = hold_lock_file_for_update(&lk, graph_name, LOCK_DIE_ON_ERROR);

		if (fd < 0)
			die_errno("unable to create '%s'", graph_name);
	}

	f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);

	hashwrite_be32(f, GRAPH_SIGNATURE);

	hashwrite_u8(f, GRAPH_VERSION);
	hashwrite_u8(f, GRAPH_OID_VERSION);
	hashwrite_u8(f, num_chunks);
	hashwrite_u8(f, 0); /* unused padding byte */

	chunk_ids[0] = GRAPH_CHUNKID_OIDFANOUT;
	chunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP;
	chunk_ids[2] = GRAPH_CHUNKID_DATA;
	if (num_extra_edges)
		chunk_ids[3] = GRAPH_CHUNKID_LARGEEDGES;
	else
		chunk_ids[3] = 0;
	chunk_ids[4] = 0;

	chunk_offsets[0] = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH;
	chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE;
	chunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.nr;
	chunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.nr;
	chunk_offsets[4] = chunk_offsets[3] + 4 * num_extra_edges;

	for (i = 0; i <= num_chunks; i++) {
		uint32_t chunk_write[3];

		chunk_write[0] = htonl(chunk_ids[i]);
		chunk_write[1] = htonl(chunk_offsets[i] >> 32);
		chunk_write[2] = htonl(chunk_offsets[i] & 0xffffffff);
		hashwrite(f, chunk_write, 12);
	}

	write_graph_chunk_fanout(f, commits.list, commits.nr);
	write_graph_chunk_oids(f, GRAPH_OID_LEN, commits.list, commits.nr);
	write_graph_chunk_data(f, GRAPH_OID_LEN, commits.list, commits.nr);
	write_graph_chunk_large_edges(f, commits.list, commits.nr);

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

	free(oids.list);
	oids.alloc = 0;
	oids.nr = 0;
}
Commit	Line	Data
08fd81c9 DS	1	#include "cache.h"
	2	#include "config.h"
	3	#include "git-compat-util.h"
	4	#include "lockfile.h"
	5	#include "pack.h"
	6	#include "packfile.h"
	7	#include "commit.h"
	8	#include "object.h"
	9	#include "revision.h"
	10	#include "sha1-lookup.h"
	11	#include "commit-graph.h"
	12
	13	#define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
	14	#define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
	15	#define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
	16	#define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
	17	#define GRAPH_CHUNKID_LARGEEDGES 0x45444745 /* "EDGE" */
	18
	19	#define GRAPH_DATA_WIDTH 36
	20
	21	#define GRAPH_VERSION_1 0x1
	22	#define GRAPH_VERSION GRAPH_VERSION_1
	23
	24	#define GRAPH_OID_VERSION_SHA1 1
	25	#define GRAPH_OID_LEN_SHA1 GIT_SHA1_RAWSZ
	26	#define GRAPH_OID_VERSION GRAPH_OID_VERSION_SHA1
	27	#define GRAPH_OID_LEN GRAPH_OID_LEN_SHA1
	28
	29	#define GRAPH_OCTOPUS_EDGES_NEEDED 0x80000000
	30	#define GRAPH_PARENT_MISSING 0x7fffffff
	31	#define GRAPH_EDGE_LAST_MASK 0x7fffffff
	32	#define GRAPH_PARENT_NONE 0x70000000
	33
	34	#define GRAPH_LAST_EDGE 0x80000000
	35
	36	#define GRAPH_FANOUT_SIZE (4 * 256)
	37	#define GRAPH_CHUNKLOOKUP_WIDTH 12
	38	#define GRAPH_MIN_SIZE (5 * GRAPH_CHUNKLOOKUP_WIDTH + GRAPH_FANOUT_SIZE + \
	39	GRAPH_OID_LEN + 8)
	40
	41
	42	static char get_commit_graph_filename(const char obj_dir)
	43	{
	44	return xstrfmt("%s/info/commit-graph", obj_dir);
	45	}
	46
	47	static void write_graph_chunk_fanout(struct hashfile *f,
	48	struct commit **commits,
	49	int nr_commits)
	50	{
	51	int i, count = 0;
	52	struct commit **list = commits;
	53
	54	/*
	55	* Write the first-level table (the list is sorted,
	56	* but we use a 256-entry lookup to be able to avoid
	57	* having to do eight extra binary search iterations).
	58	*/
	59	for (i = 0; i < 256; i++) {
	60	while (count < nr_commits) {
	61	if ((*list)->object.oid.hash[0] != i)
	62	break;
	63	count++;
	64	list++;
65	}
66
67	hashwrite_be32(f, count);
68	}
69	}
70
71	static void write_graph_chunk_oids(struct hashfile *f, int hash_len,
72	struct commit **commits, int nr_commits)
73	{
74	struct commit **list = commits;
75	int count;
76	for (count = 0; count < nr_commits; count++, list++)
77	hashwrite(f, (*list)->object.oid.hash, (int)hash_len);
78	}
79
80	static const unsigned char commit_to_sha1(size_t index, void table)
81	{
82	struct commit **commits = table;
83	return commits[index]->object.oid.hash;
84	}
85
86	static void write_graph_chunk_data(struct hashfile *f, int hash_len,
87	struct commit **commits, int nr_commits)
88	{
89	struct commit **list = commits;
90	struct commit **last = commits + nr_commits;
91	uint32_t num_extra_edges = 0;
92
93	while (list < last) {
94	struct commit_list *parent;
95	int edge_value;
96	uint32_t packedDate[2];
97
98	parse_commit(*list);
99	hashwrite(f, (*list)->tree->object.oid.hash, hash_len);
100
101	parent = (*list)->parents;
102
103	if (!parent)
104	edge_value = GRAPH_PARENT_NONE;
105	else {
106	edge_value = sha1_pos(parent->item->object.oid.hash,
107	commits,
108	nr_commits,
109	commit_to_sha1);
110
111	if (edge_value < 0)
112	edge_value = GRAPH_PARENT_MISSING;
113	}
114
115	hashwrite_be32(f, edge_value);
116
117	if (parent)
118	parent = parent->next;
119
120	if (!parent)
121	edge_value = GRAPH_PARENT_NONE;
122	else if (parent->next)
123	edge_value = GRAPH_OCTOPUS_EDGES_NEEDED \| num_extra_edges;
124	else {
125	edge_value = sha1_pos(parent->item->object.oid.hash,
126	commits,
127	nr_commits,
128	commit_to_sha1);
129	if (edge_value < 0)
130	edge_value = GRAPH_PARENT_MISSING;
131	}
132
133	hashwrite_be32(f, edge_value);
134
135	if (edge_value & GRAPH_OCTOPUS_EDGES_NEEDED) {
136	do {
137	num_extra_edges++;
138	parent = parent->next;
139	} while (parent);
140	}
141
142	if (sizeof((*list)->date) > 4)
143	packedDate[0] = htonl(((*list)->date >> 32) & 0x3);
144	else
145	packedDate[0] = 0;
146
147	packedDate[1] = htonl((*list)->date);
148	hashwrite(f, packedDate, 8);
149
150	list++;
151	}
152	}
153
154	static void write_graph_chunk_large_edges(struct hashfile *f,
155	struct commit **commits,
156	int nr_commits)
157	{
158	struct commit **list = commits;
159	struct commit **last = commits + nr_commits;
160	struct commit_list *parent;
161
162	while (list < last) {
163	int num_parents = 0;
164	for (parent = (*list)->parents; num_parents < 3 && parent;
165	parent = parent->next)
166	num_parents++;
167
168	if (num_parents <= 2) {
169	list++;
170	continue;
171	}
172
173	/* Since num_parents > 2, this initializer is safe. */
174	for (parent = (*list)->parents->next; parent; parent = parent->next) {
175	int edge_value = sha1_pos(parent->item->object.oid.hash,
176	commits,
177	nr_commits,
178	commit_to_sha1);
179
180	if (edge_value < 0)
181	edge_value = GRAPH_PARENT_MISSING;
182	else if (!parent->next)
183	edge_value \|= GRAPH_LAST_EDGE;
184
185	hashwrite_be32(f, edge_value);
186	}
187
188	list++;
189	}
190	}
191
192	static int commit_compare(const void _a, const void _b)
193	{
194	const struct object_id a = (const struct object_id )_a;
195	const struct object_id b = (const struct object_id )_b;
196	return oidcmp(a, b);
197	}
198
199	struct packed_commit_list {
200	struct commit **list;
201	int nr;
202	int alloc;
203	};
204
205	struct packed_oid_list {
206	struct object_id *list;
207	int nr;
208	int alloc;
209	};
210
211	static int add_packed_commits(const struct object_id *oid,
212	struct packed_git *pack,
213	uint32_t pos,
214	void *data)
215	{
216	struct packed_oid_list list = (struct packed_oid_list)data;
217	enum object_type type;
218	off_t offset = nth_packed_object_offset(pack, pos);
219	struct object_info oi = OBJECT_INFO_INIT;
220
221	oi.typep = &type;
222	if (packed_object_info(pack, offset, &oi) < 0)
223	die("unable to get type of object %s", oid_to_hex(oid));
224
225	if (type != OBJ_COMMIT)
226	return 0;
227
228	ALLOC_GROW(list->list, list->nr + 1, list->alloc);
229	oidcpy(&(list->list[list->nr]), oid);
230	list->nr++;
231
232	return 0;
233	}
234
235	void write_commit_graph(const char *obj_dir)
236	{
237	struct packed_oid_list oids;
238	struct packed_commit_list commits;
239	struct hashfile *f;
240	uint32_t i, count_distinct = 0;
241	char *graph_name;
242	int fd;
243	struct lock_file lk = LOCK_INIT;
244	uint32_t chunk_ids[5];
245	uint64_t chunk_offsets[5];
246	int num_chunks;
247	int num_extra_edges;
248	struct commit_list *parent;
249
250	oids.nr = 0;
251	oids.alloc = approximate_object_count() / 4;
252
253	if (oids.alloc < 1024)
254	oids.alloc = 1024;
255	ALLOC_ARRAY(oids.list, oids.alloc);
256
257	for_each_packed_object(add_packed_commits, &oids, 0);
258
259	QSORT(oids.list, oids.nr, commit_compare);
260
261	count_distinct = 1;
262	for (i = 1; i < oids.nr; i++) {
263	if (oidcmp(&oids.list[i-1], &oids.list[i]))
264	count_distinct++;
265	}
266
267	if (count_distinct >= GRAPH_PARENT_MISSING)
268	die(_("the commit graph format cannot write %d commits"), count_distinct);
269
270	commits.nr = 0;
271	commits.alloc = count_distinct;
272	ALLOC_ARRAY(commits.list, commits.alloc);
273
274	num_extra_edges = 0;
275	for (i = 0; i < oids.nr; i++) {
276	int num_parents = 0;
277	if (i > 0 && !oidcmp(&oids.list[i-1], &oids.list[i]))
278	continue;
279
280	commits.list[commits.nr] = lookup_commit(&oids.list[i]);
281	parse_commit(commits.list[commits.nr]);
282
283	for (parent = commits.list[commits.nr]->parents;
284	parent; parent = parent->next)
285	num_parents++;
286
287	if (num_parents > 2)
288	num_extra_edges += num_parents - 1;
289
290	commits.nr++;
291	}
292	num_chunks = num_extra_edges ? 4 : 3;
293
294	if (commits.nr >= GRAPH_PARENT_MISSING)
295	die(_("too many commits to write graph"));
296
297	graph_name = get_commit_graph_filename(obj_dir);
298	fd = hold_lock_file_for_update(&lk, graph_name, 0);
299
300	if (fd < 0) {
301	struct strbuf folder = STRBUF_INIT;
302	strbuf_addstr(&folder, graph_name);
303	strbuf_setlen(&folder, strrchr(folder.buf, '/') - folder.buf);
304
305	if (mkdir(folder.buf, 0777) < 0)
306	die_errno(_("cannot mkdir %s"), folder.buf);
307	strbuf_release(&folder);
308
309	fd = hold_lock_file_for_update(&lk, graph_name, LOCK_DIE_ON_ERROR);
310
311	if (fd < 0)
312	die_errno("unable to create '%s'", graph_name);
313	}
314
315	f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
316
317	hashwrite_be32(f, GRAPH_SIGNATURE);
318
319	hashwrite_u8(f, GRAPH_VERSION);
320	hashwrite_u8(f, GRAPH_OID_VERSION);
321	hashwrite_u8(f, num_chunks);
322	hashwrite_u8(f, 0); /* unused padding byte */
323
324	chunk_ids[0] = GRAPH_CHUNKID_OIDFANOUT;
325	chunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP;
326	chunk_ids[2] = GRAPH_CHUNKID_DATA;
327	if (num_extra_edges)
328	chunk_ids[3] = GRAPH_CHUNKID_LARGEEDGES;
329	else
330	chunk_ids[3] = 0;
331	chunk_ids[4] = 0;
332
333	chunk_offsets[0] = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH;
334	chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE;
335	chunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.nr;
336	chunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.nr;
337	chunk_offsets[4] = chunk_offsets[3] + 4 * num_extra_edges;
338
339	for (i = 0; i <= num_chunks; i++) {
340	uint32_t chunk_write[3];
341
342	chunk_write[0] = htonl(chunk_ids[i]);
343	chunk_write[1] = htonl(chunk_offsets[i] >> 32);
344	chunk_write[2] = htonl(chunk_offsets[i] & 0xffffffff);
345	hashwrite(f, chunk_write, 12);
346	}
347
348	write_graph_chunk_fanout(f, commits.list, commits.nr);
349	write_graph_chunk_oids(f, GRAPH_OID_LEN, commits.list, commits.nr);
350	write_graph_chunk_data(f, GRAPH_OID_LEN, commits.list, commits.nr);
351	write_graph_chunk_large_edges(f, commits.list, commits.nr);
352
353	finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM \| CSUM_FSYNC);
354	commit_lock_file(&lk);
355
356	free(oids.list);
357	oids.alloc = 0;
358	oids.nr = 0;
359	}