commit-graph: implement git-commit-graph write
[git/git.git] / commit-graph.c
CommitLineData
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
42static char *get_commit_graph_filename(const char *obj_dir)
43{
44 return xstrfmt("%s/info/commit-graph", obj_dir);
45}
46
47static 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
71static 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
80static 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
86static 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
154static 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
192static 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
199struct packed_commit_list {
200 struct commit **list;
201 int nr;
202 int alloc;
203};
204
205struct packed_oid_list {
206 struct object_id *list;
207 int nr;
208 int alloc;
209};
210
211static 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
235void 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}