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