1 #include "git-compat-util.h"
10 #include "object-file.h"
11 #include "object-store-ll.h"
12 #include "hash-lookup.h"
16 #include "run-command.h"
17 #include "repository.h"
18 #include "chunk-format.h"
20 #include "pack-bitmap.h"
23 #include "list-objects.h"
24 #include "pack-revindex.h"
26 #define MIDX_SIGNATURE 0x4d494458 /* "MIDX" */
27 #define MIDX_VERSION 1
28 #define MIDX_BYTE_FILE_VERSION 4
29 #define MIDX_BYTE_HASH_VERSION 5
30 #define MIDX_BYTE_NUM_CHUNKS 6
31 #define MIDX_BYTE_NUM_PACKS 8
32 #define MIDX_HEADER_SIZE 12
33 #define MIDX_MIN_SIZE (MIDX_HEADER_SIZE + the_hash_algo->rawsz)
35 #define MIDX_CHUNK_ALIGNMENT 4
36 #define MIDX_CHUNKID_PACKNAMES 0x504e414d /* "PNAM" */
37 #define MIDX_CHUNKID_BITMAPPEDPACKS 0x42544d50 /* "BTMP" */
38 #define MIDX_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
39 #define MIDX_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
40 #define MIDX_CHUNKID_OBJECTOFFSETS 0x4f4f4646 /* "OOFF" */
41 #define MIDX_CHUNKID_LARGEOFFSETS 0x4c4f4646 /* "LOFF" */
42 #define MIDX_CHUNKID_REVINDEX 0x52494458 /* "RIDX" */
43 #define MIDX_CHUNK_FANOUT_SIZE (sizeof(uint32_t) * 256)
44 #define MIDX_CHUNK_OFFSET_WIDTH (2 * sizeof(uint32_t))
45 #define MIDX_CHUNK_LARGE_OFFSET_WIDTH (sizeof(uint64_t))
46 #define MIDX_CHUNK_BITMAPPED_PACKS_WIDTH (2 * sizeof(uint32_t))
47 #define MIDX_LARGE_OFFSET_NEEDED 0x80000000
49 #define PACK_EXPIRED UINT_MAX
51 const unsigned char *get_midx_checksum(struct multi_pack_index
*m
)
53 return m
->data
+ m
->data_len
- the_hash_algo
->rawsz
;
56 void get_midx_filename(struct strbuf
*out
, const char *object_dir
)
58 strbuf_addf(out
, "%s/pack/multi-pack-index", object_dir
);
61 void get_midx_rev_filename(struct strbuf
*out
, struct multi_pack_index
*m
)
63 get_midx_filename(out
, m
->object_dir
);
64 strbuf_addf(out
, "-%s.rev", hash_to_hex(get_midx_checksum(m
)));
67 static int midx_read_oid_fanout(const unsigned char *chunk_start
,
68 size_t chunk_size
, void *data
)
71 struct multi_pack_index
*m
= data
;
72 m
->chunk_oid_fanout
= (uint32_t *)chunk_start
;
74 if (chunk_size
!= 4 * 256) {
75 error(_("multi-pack-index OID fanout is of the wrong size"));
78 for (i
= 0; i
< 255; i
++) {
79 uint32_t oid_fanout1
= ntohl(m
->chunk_oid_fanout
[i
]);
80 uint32_t oid_fanout2
= ntohl(m
->chunk_oid_fanout
[i
+1]);
82 if (oid_fanout1
> oid_fanout2
) {
83 error(_("oid fanout out of order: fanout[%d] = %"PRIx32
" > %"PRIx32
" = fanout[%d]"),
84 i
, oid_fanout1
, oid_fanout2
, i
+ 1);
88 m
->num_objects
= ntohl(m
->chunk_oid_fanout
[255]);
92 static int midx_read_oid_lookup(const unsigned char *chunk_start
,
93 size_t chunk_size
, void *data
)
95 struct multi_pack_index
*m
= data
;
96 m
->chunk_oid_lookup
= chunk_start
;
98 if (chunk_size
!= st_mult(m
->hash_len
, m
->num_objects
)) {
99 error(_("multi-pack-index OID lookup chunk is the wrong size"));
105 static int midx_read_object_offsets(const unsigned char *chunk_start
,
106 size_t chunk_size
, void *data
)
108 struct multi_pack_index
*m
= data
;
109 m
->chunk_object_offsets
= chunk_start
;
111 if (chunk_size
!= st_mult(m
->num_objects
, MIDX_CHUNK_OFFSET_WIDTH
)) {
112 error(_("multi-pack-index object offset chunk is the wrong size"));
118 struct multi_pack_index
*load_multi_pack_index(const char *object_dir
, int local
)
120 struct multi_pack_index
*m
= NULL
;
124 void *midx_map
= NULL
;
125 uint32_t hash_version
;
126 struct strbuf midx_name
= STRBUF_INIT
;
128 const char *cur_pack_name
;
129 struct chunkfile
*cf
= NULL
;
131 get_midx_filename(&midx_name
, object_dir
);
133 fd
= git_open(midx_name
.buf
);
137 if (fstat(fd
, &st
)) {
138 error_errno(_("failed to read %s"), midx_name
.buf
);
142 midx_size
= xsize_t(st
.st_size
);
144 if (midx_size
< MIDX_MIN_SIZE
) {
145 error(_("multi-pack-index file %s is too small"), midx_name
.buf
);
149 strbuf_release(&midx_name
);
151 midx_map
= xmmap(NULL
, midx_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
154 FLEX_ALLOC_STR(m
, object_dir
, object_dir
);
156 m
->data_len
= midx_size
;
159 m
->signature
= get_be32(m
->data
);
160 if (m
->signature
!= MIDX_SIGNATURE
)
161 die(_("multi-pack-index signature 0x%08x does not match signature 0x%08x"),
162 m
->signature
, MIDX_SIGNATURE
);
164 m
->version
= m
->data
[MIDX_BYTE_FILE_VERSION
];
165 if (m
->version
!= MIDX_VERSION
)
166 die(_("multi-pack-index version %d not recognized"),
169 hash_version
= m
->data
[MIDX_BYTE_HASH_VERSION
];
170 if (hash_version
!= oid_version(the_hash_algo
)) {
171 error(_("multi-pack-index hash version %u does not match version %u"),
172 hash_version
, oid_version(the_hash_algo
));
175 m
->hash_len
= the_hash_algo
->rawsz
;
177 m
->num_chunks
= m
->data
[MIDX_BYTE_NUM_CHUNKS
];
179 m
->num_packs
= get_be32(m
->data
+ MIDX_BYTE_NUM_PACKS
);
181 m
->preferred_pack_idx
= -1;
183 cf
= init_chunkfile(NULL
);
185 if (read_table_of_contents(cf
, m
->data
, midx_size
,
186 MIDX_HEADER_SIZE
, m
->num_chunks
,
187 MIDX_CHUNK_ALIGNMENT
))
190 if (pair_chunk(cf
, MIDX_CHUNKID_PACKNAMES
, &m
->chunk_pack_names
, &m
->chunk_pack_names_len
))
191 die(_("multi-pack-index required pack-name chunk missing or corrupted"));
192 if (read_chunk(cf
, MIDX_CHUNKID_OIDFANOUT
, midx_read_oid_fanout
, m
))
193 die(_("multi-pack-index required OID fanout chunk missing or corrupted"));
194 if (read_chunk(cf
, MIDX_CHUNKID_OIDLOOKUP
, midx_read_oid_lookup
, m
))
195 die(_("multi-pack-index required OID lookup chunk missing or corrupted"));
196 if (read_chunk(cf
, MIDX_CHUNKID_OBJECTOFFSETS
, midx_read_object_offsets
, m
))
197 die(_("multi-pack-index required object offsets chunk missing or corrupted"));
199 pair_chunk(cf
, MIDX_CHUNKID_LARGEOFFSETS
, &m
->chunk_large_offsets
,
200 &m
->chunk_large_offsets_len
);
201 if (git_env_bool("GIT_TEST_MIDX_READ_BTMP", 1))
202 pair_chunk(cf
, MIDX_CHUNKID_BITMAPPEDPACKS
,
203 (const unsigned char **)&m
->chunk_bitmapped_packs
,
204 &m
->chunk_bitmapped_packs_len
);
206 if (git_env_bool("GIT_TEST_MIDX_READ_RIDX", 1))
207 pair_chunk(cf
, MIDX_CHUNKID_REVINDEX
, &m
->chunk_revindex
,
208 &m
->chunk_revindex_len
);
210 CALLOC_ARRAY(m
->pack_names
, m
->num_packs
);
211 CALLOC_ARRAY(m
->packs
, m
->num_packs
);
213 cur_pack_name
= (const char *)m
->chunk_pack_names
;
214 for (i
= 0; i
< m
->num_packs
; i
++) {
216 size_t avail
= m
->chunk_pack_names_len
-
217 (cur_pack_name
- (const char *)m
->chunk_pack_names
);
219 m
->pack_names
[i
] = cur_pack_name
;
221 end
= memchr(cur_pack_name
, '\0', avail
);
223 die(_("multi-pack-index pack-name chunk is too short"));
224 cur_pack_name
= end
+ 1;
226 if (i
&& strcmp(m
->pack_names
[i
], m
->pack_names
[i
- 1]) <= 0)
227 die(_("multi-pack-index pack names out of order: '%s' before '%s'"),
228 m
->pack_names
[i
- 1],
232 trace2_data_intmax("midx", the_repository
, "load/num_packs", m
->num_packs
);
233 trace2_data_intmax("midx", the_repository
, "load/num_objects", m
->num_objects
);
240 strbuf_release(&midx_name
);
243 munmap(midx_map
, midx_size
);
249 void close_midx(struct multi_pack_index
*m
)
258 munmap((unsigned char *)m
->data
, m
->data_len
);
260 for (i
= 0; i
< m
->num_packs
; i
++) {
262 m
->packs
[i
]->multi_pack_index
= 0;
264 FREE_AND_NULL(m
->packs
);
265 FREE_AND_NULL(m
->pack_names
);
269 int prepare_midx_pack(struct repository
*r
, struct multi_pack_index
*m
, uint32_t pack_int_id
)
271 struct strbuf pack_name
= STRBUF_INIT
;
272 struct packed_git
*p
;
274 if (pack_int_id
>= m
->num_packs
)
275 die(_("bad pack-int-id: %u (%u total packs)"),
276 pack_int_id
, m
->num_packs
);
278 if (m
->packs
[pack_int_id
])
281 strbuf_addf(&pack_name
, "%s/pack/%s", m
->object_dir
,
282 m
->pack_names
[pack_int_id
]);
284 p
= add_packed_git(pack_name
.buf
, pack_name
.len
, m
->local
);
285 strbuf_release(&pack_name
);
290 p
->multi_pack_index
= 1;
291 m
->packs
[pack_int_id
] = p
;
292 install_packed_git(r
, p
);
293 list_add_tail(&p
->mru
, &r
->objects
->packed_git_mru
);
298 int nth_bitmapped_pack(struct repository
*r
, struct multi_pack_index
*m
,
299 struct bitmapped_pack
*bp
, uint32_t pack_int_id
)
301 if (!m
->chunk_bitmapped_packs
)
302 return error(_("MIDX does not contain the BTMP chunk"));
304 if (prepare_midx_pack(r
, m
, pack_int_id
))
305 return error(_("could not load bitmapped pack %"PRIu32
), pack_int_id
);
307 bp
->p
= m
->packs
[pack_int_id
];
308 bp
->bitmap_pos
= get_be32((char *)m
->chunk_bitmapped_packs
+
309 MIDX_CHUNK_BITMAPPED_PACKS_WIDTH
* pack_int_id
);
310 bp
->bitmap_nr
= get_be32((char *)m
->chunk_bitmapped_packs
+
311 MIDX_CHUNK_BITMAPPED_PACKS_WIDTH
* pack_int_id
+
313 bp
->pack_int_id
= pack_int_id
;
318 int bsearch_midx(const struct object_id
*oid
, struct multi_pack_index
*m
, uint32_t *result
)
320 return bsearch_hash(oid
->hash
, m
->chunk_oid_fanout
, m
->chunk_oid_lookup
,
321 the_hash_algo
->rawsz
, result
);
324 struct object_id
*nth_midxed_object_oid(struct object_id
*oid
,
325 struct multi_pack_index
*m
,
328 if (n
>= m
->num_objects
)
331 oidread(oid
, m
->chunk_oid_lookup
+ st_mult(m
->hash_len
, n
));
335 off_t
nth_midxed_offset(struct multi_pack_index
*m
, uint32_t pos
)
337 const unsigned char *offset_data
;
340 offset_data
= m
->chunk_object_offsets
+ (off_t
)pos
* MIDX_CHUNK_OFFSET_WIDTH
;
341 offset32
= get_be32(offset_data
+ sizeof(uint32_t));
343 if (m
->chunk_large_offsets
&& offset32
& MIDX_LARGE_OFFSET_NEEDED
) {
344 if (sizeof(off_t
) < sizeof(uint64_t))
345 die(_("multi-pack-index stores a 64-bit offset, but off_t is too small"));
347 offset32
^= MIDX_LARGE_OFFSET_NEEDED
;
348 if (offset32
>= m
->chunk_large_offsets_len
/ sizeof(uint64_t))
349 die(_("multi-pack-index large offset out of bounds"));
350 return get_be64(m
->chunk_large_offsets
+ sizeof(uint64_t) * offset32
);
356 uint32_t nth_midxed_pack_int_id(struct multi_pack_index
*m
, uint32_t pos
)
358 return get_be32(m
->chunk_object_offsets
+
359 (off_t
)pos
* MIDX_CHUNK_OFFSET_WIDTH
);
362 int fill_midx_entry(struct repository
*r
,
363 const struct object_id
*oid
,
364 struct pack_entry
*e
,
365 struct multi_pack_index
*m
)
368 uint32_t pack_int_id
;
369 struct packed_git
*p
;
371 if (!bsearch_midx(oid
, m
, &pos
))
374 if (pos
>= m
->num_objects
)
377 pack_int_id
= nth_midxed_pack_int_id(m
, pos
);
379 if (prepare_midx_pack(r
, m
, pack_int_id
))
381 p
= m
->packs
[pack_int_id
];
384 * We are about to tell the caller where they can locate the
385 * requested object. We better make sure the packfile is
386 * still here and can be accessed before supplying that
387 * answer, as it may have been deleted since the MIDX was
390 if (!is_pack_valid(p
))
393 if (oidset_size(&p
->bad_objects
) &&
394 oidset_contains(&p
->bad_objects
, oid
))
397 e
->offset
= nth_midxed_offset(m
, pos
);
403 /* Match "foo.idx" against either "foo.pack" _or_ "foo.idx". */
404 static int cmp_idx_or_pack_name(const char *idx_or_pack_name
,
405 const char *idx_name
)
407 /* Skip past any initial matching prefix. */
408 while (*idx_name
&& *idx_name
== *idx_or_pack_name
) {
414 * If we didn't match completely, we may have matched "pack-1234." and
415 * be left with "idx" and "pack" respectively, which is also OK. We do
416 * not have to check for "idx" and "idx", because that would have been
417 * a complete match (and in that case these strcmps will be false, but
418 * we'll correctly return 0 from the final strcmp() below.
420 * Technically this matches "fooidx" and "foopack", but we'd never have
421 * such names in the first place.
423 if (!strcmp(idx_name
, "idx") && !strcmp(idx_or_pack_name
, "pack"))
427 * This not only checks for a complete match, but also orders based on
428 * the first non-identical character, which means our ordering will
429 * match a raw strcmp(). That makes it OK to use this to binary search
430 * a naively-sorted list.
432 return strcmp(idx_or_pack_name
, idx_name
);
435 int midx_locate_pack(struct multi_pack_index
*m
, const char *idx_or_pack_name
,
438 uint32_t first
= 0, last
= m
->num_packs
;
440 while (first
< last
) {
441 uint32_t mid
= first
+ (last
- first
) / 2;
445 current
= m
->pack_names
[mid
];
446 cmp
= cmp_idx_or_pack_name(idx_or_pack_name
, current
);
462 int midx_contains_pack(struct multi_pack_index
*m
, const char *idx_or_pack_name
)
464 return midx_locate_pack(m
, idx_or_pack_name
, NULL
);
467 int midx_preferred_pack(struct multi_pack_index
*m
, uint32_t *pack_int_id
)
469 if (m
->preferred_pack_idx
== -1) {
470 if (load_midx_revindex(m
) < 0) {
471 m
->preferred_pack_idx
= -2;
475 m
->preferred_pack_idx
=
476 nth_midxed_pack_int_id(m
, pack_pos_to_midx(m
, 0));
477 } else if (m
->preferred_pack_idx
== -2)
478 return -1; /* no revindex */
480 *pack_int_id
= m
->preferred_pack_idx
;
484 int prepare_multi_pack_index_one(struct repository
*r
, const char *object_dir
, int local
)
486 struct multi_pack_index
*m
;
487 struct multi_pack_index
*m_search
;
489 prepare_repo_settings(r
);
490 if (!r
->settings
.core_multi_pack_index
)
493 for (m_search
= r
->objects
->multi_pack_index
; m_search
; m_search
= m_search
->next
)
494 if (!strcmp(object_dir
, m_search
->object_dir
))
497 m
= load_multi_pack_index(object_dir
, local
);
500 struct multi_pack_index
*mp
= r
->objects
->multi_pack_index
;
505 r
->objects
->multi_pack_index
= m
;
512 static size_t write_midx_header(struct hashfile
*f
,
513 unsigned char num_chunks
,
516 hashwrite_be32(f
, MIDX_SIGNATURE
);
517 hashwrite_u8(f
, MIDX_VERSION
);
518 hashwrite_u8(f
, oid_version(the_hash_algo
));
519 hashwrite_u8(f
, num_chunks
);
520 hashwrite_u8(f
, 0); /* unused */
521 hashwrite_be32(f
, num_packs
);
523 return MIDX_HEADER_SIZE
;
526 #define BITMAP_POS_UNKNOWN (~((uint32_t)0))
529 uint32_t orig_pack_int_id
;
531 struct packed_git
*p
;
536 unsigned expired
: 1;
539 static void fill_pack_info(struct pack_info
*info
,
540 struct packed_git
*p
, const char *pack_name
,
541 uint32_t orig_pack_int_id
)
543 memset(info
, 0, sizeof(struct pack_info
));
545 info
->orig_pack_int_id
= orig_pack_int_id
;
546 info
->pack_name
= xstrdup(pack_name
);
548 info
->bitmap_pos
= BITMAP_POS_UNKNOWN
;
551 static int pack_info_compare(const void *_a
, const void *_b
)
553 struct pack_info
*a
= (struct pack_info
*)_a
;
554 struct pack_info
*b
= (struct pack_info
*)_b
;
555 return strcmp(a
->pack_name
, b
->pack_name
);
558 static int idx_or_pack_name_cmp(const void *_va
, const void *_vb
)
560 const char *pack_name
= _va
;
561 const struct pack_info
*compar
= _vb
;
563 return cmp_idx_or_pack_name(pack_name
, compar
->pack_name
);
566 struct write_midx_context
{
567 struct pack_info
*info
;
570 struct multi_pack_index
*m
;
571 struct progress
*progress
;
572 unsigned pack_paths_checked
;
574 struct pack_midx_entry
*entries
;
578 uint32_t *pack_order
;
579 unsigned large_offsets_needed
:1;
580 uint32_t num_large_offsets
;
582 int preferred_pack_idx
;
584 struct string_list
*to_include
;
587 static void add_pack_to_midx(const char *full_path
, size_t full_path_len
,
588 const char *file_name
, void *data
)
590 struct write_midx_context
*ctx
= data
;
591 struct packed_git
*p
;
593 if (ends_with(file_name
, ".idx")) {
594 display_progress(ctx
->progress
, ++ctx
->pack_paths_checked
);
596 * Note that at most one of ctx->m and ctx->to_include are set,
597 * so we are testing midx_contains_pack() and
598 * string_list_has_string() independently (guarded by the
599 * appropriate NULL checks).
601 * We could support passing to_include while reusing an existing
602 * MIDX, but don't currently since the reuse process drags
603 * forward all packs from an existing MIDX (without checking
604 * whether or not they appear in the to_include list).
606 * If we added support for that, these next two conditional
607 * should be performed independently (likely checking
608 * to_include before the existing MIDX).
610 if (ctx
->m
&& midx_contains_pack(ctx
->m
, file_name
))
612 else if (ctx
->to_include
&&
613 !string_list_has_string(ctx
->to_include
, file_name
))
616 ALLOC_GROW(ctx
->info
, ctx
->nr
+ 1, ctx
->alloc
);
618 p
= add_packed_git(full_path
, full_path_len
, 0);
620 warning(_("failed to add packfile '%s'"),
625 if (open_pack_index(p
)) {
626 warning(_("failed to open pack-index '%s'"),
633 fill_pack_info(&ctx
->info
[ctx
->nr
], p
, file_name
, ctx
->nr
);
638 struct pack_midx_entry
{
639 struct object_id oid
;
640 uint32_t pack_int_id
;
643 unsigned preferred
: 1;
646 static int midx_oid_compare(const void *_a
, const void *_b
)
648 const struct pack_midx_entry
*a
= (const struct pack_midx_entry
*)_a
;
649 const struct pack_midx_entry
*b
= (const struct pack_midx_entry
*)_b
;
650 int cmp
= oidcmp(&a
->oid
, &b
->oid
);
655 /* Sort objects in a preferred pack first when multiple copies exist. */
656 if (a
->preferred
> b
->preferred
)
658 if (a
->preferred
< b
->preferred
)
661 if (a
->pack_mtime
> b
->pack_mtime
)
663 else if (a
->pack_mtime
< b
->pack_mtime
)
666 return a
->pack_int_id
- b
->pack_int_id
;
669 static int nth_midxed_pack_midx_entry(struct multi_pack_index
*m
,
670 struct pack_midx_entry
*e
,
673 if (pos
>= m
->num_objects
)
676 nth_midxed_object_oid(&e
->oid
, m
, pos
);
677 e
->pack_int_id
= nth_midxed_pack_int_id(m
, pos
);
678 e
->offset
= nth_midxed_offset(m
, pos
);
680 /* consider objects in midx to be from "old" packs */
685 static void fill_pack_entry(uint32_t pack_int_id
,
686 struct packed_git
*p
,
688 struct pack_midx_entry
*entry
,
691 if (nth_packed_object_id(&entry
->oid
, p
, cur_object
) < 0)
692 die(_("failed to locate object %d in packfile"), cur_object
);
694 entry
->pack_int_id
= pack_int_id
;
695 entry
->pack_mtime
= p
->mtime
;
697 entry
->offset
= nth_packed_object_offset(p
, cur_object
);
698 entry
->preferred
= !!preferred
;
702 struct pack_midx_entry
*entries
;
706 static void midx_fanout_grow(struct midx_fanout
*fanout
, size_t nr
)
709 BUG("negative growth in midx_fanout_grow() (%"PRIuMAX
" < %"PRIuMAX
")",
710 (uintmax_t)nr
, (uintmax_t)fanout
->nr
);
711 ALLOC_GROW(fanout
->entries
, nr
, fanout
->alloc
);
714 static void midx_fanout_sort(struct midx_fanout
*fanout
)
716 QSORT(fanout
->entries
, fanout
->nr
, midx_oid_compare
);
719 static void midx_fanout_add_midx_fanout(struct midx_fanout
*fanout
,
720 struct multi_pack_index
*m
,
724 uint32_t start
= 0, end
;
728 start
= ntohl(m
->chunk_oid_fanout
[cur_fanout
- 1]);
729 end
= ntohl(m
->chunk_oid_fanout
[cur_fanout
]);
731 for (cur_object
= start
; cur_object
< end
; cur_object
++) {
732 if ((preferred_pack
> -1) &&
733 (preferred_pack
== nth_midxed_pack_int_id(m
, cur_object
))) {
735 * Objects from preferred packs are added
741 midx_fanout_grow(fanout
, fanout
->nr
+ 1);
742 nth_midxed_pack_midx_entry(m
,
743 &fanout
->entries
[fanout
->nr
],
745 fanout
->entries
[fanout
->nr
].preferred
= 0;
750 static void midx_fanout_add_pack_fanout(struct midx_fanout
*fanout
,
751 struct pack_info
*info
,
756 struct packed_git
*pack
= info
[cur_pack
].p
;
757 uint32_t start
= 0, end
;
761 start
= get_pack_fanout(pack
, cur_fanout
- 1);
762 end
= get_pack_fanout(pack
, cur_fanout
);
764 for (cur_object
= start
; cur_object
< end
; cur_object
++) {
765 midx_fanout_grow(fanout
, fanout
->nr
+ 1);
766 fill_pack_entry(cur_pack
,
769 &fanout
->entries
[fanout
->nr
],
776 * It is possible to artificially get into a state where there are many
777 * duplicate copies of objects. That can create high memory pressure if
778 * we are to create a list of all objects before de-duplication. To reduce
779 * this memory pressure without a significant performance drop, automatically
780 * group objects by the first byte of their object id. Use the IDX fanout
781 * tables to group the data, copy to a local array, then sort.
783 * Copy only the de-duplicated entries (selected by most-recent modified time
784 * of a packfile containing the object).
786 static struct pack_midx_entry
*get_sorted_entries(struct multi_pack_index
*m
,
787 struct pack_info
*info
,
792 uint32_t cur_fanout
, cur_pack
, cur_object
;
793 size_t alloc_objects
, total_objects
= 0;
794 struct midx_fanout fanout
= { 0 };
795 struct pack_midx_entry
*deduplicated_entries
= NULL
;
796 uint32_t start_pack
= m
? m
->num_packs
: 0;
798 for (cur_pack
= start_pack
; cur_pack
< nr_packs
; cur_pack
++)
799 total_objects
= st_add(total_objects
,
800 info
[cur_pack
].p
->num_objects
);
803 * As we de-duplicate by fanout value, we expect the fanout
804 * slices to be evenly distributed, with some noise. Hence,
805 * allocate slightly more than one 256th.
807 alloc_objects
= fanout
.alloc
= total_objects
> 3200 ? total_objects
/ 200 : 16;
809 ALLOC_ARRAY(fanout
.entries
, fanout
.alloc
);
810 ALLOC_ARRAY(deduplicated_entries
, alloc_objects
);
813 for (cur_fanout
= 0; cur_fanout
< 256; cur_fanout
++) {
817 midx_fanout_add_midx_fanout(&fanout
, m
, cur_fanout
,
820 for (cur_pack
= start_pack
; cur_pack
< nr_packs
; cur_pack
++) {
821 int preferred
= cur_pack
== preferred_pack
;
822 midx_fanout_add_pack_fanout(&fanout
,
824 preferred
, cur_fanout
);
827 if (-1 < preferred_pack
&& preferred_pack
< start_pack
)
828 midx_fanout_add_pack_fanout(&fanout
, info
,
832 midx_fanout_sort(&fanout
);
835 * The batch is now sorted by OID and then mtime (descending).
836 * Take only the first duplicate.
838 for (cur_object
= 0; cur_object
< fanout
.nr
; cur_object
++) {
839 if (cur_object
&& oideq(&fanout
.entries
[cur_object
- 1].oid
,
840 &fanout
.entries
[cur_object
].oid
))
843 ALLOC_GROW(deduplicated_entries
, st_add(*nr_objects
, 1),
845 memcpy(&deduplicated_entries
[*nr_objects
],
846 &fanout
.entries
[cur_object
],
847 sizeof(struct pack_midx_entry
));
852 free(fanout
.entries
);
853 return deduplicated_entries
;
856 static int write_midx_pack_names(struct hashfile
*f
, void *data
)
858 struct write_midx_context
*ctx
= data
;
860 unsigned char padding
[MIDX_CHUNK_ALIGNMENT
];
863 for (i
= 0; i
< ctx
->nr
; i
++) {
866 if (ctx
->info
[i
].expired
)
869 if (i
&& strcmp(ctx
->info
[i
].pack_name
, ctx
->info
[i
- 1].pack_name
) <= 0)
870 BUG("incorrect pack-file order: %s before %s",
871 ctx
->info
[i
- 1].pack_name
,
872 ctx
->info
[i
].pack_name
);
874 writelen
= strlen(ctx
->info
[i
].pack_name
) + 1;
875 hashwrite(f
, ctx
->info
[i
].pack_name
, writelen
);
879 /* add padding to be aligned */
880 i
= MIDX_CHUNK_ALIGNMENT
- (written
% MIDX_CHUNK_ALIGNMENT
);
881 if (i
< MIDX_CHUNK_ALIGNMENT
) {
882 memset(padding
, 0, sizeof(padding
));
883 hashwrite(f
, padding
, i
);
889 static int write_midx_bitmapped_packs(struct hashfile
*f
, void *data
)
891 struct write_midx_context
*ctx
= data
;
894 for (i
= 0; i
< ctx
->nr
; i
++) {
895 struct pack_info
*pack
= &ctx
->info
[i
];
899 if (pack
->bitmap_pos
== BITMAP_POS_UNKNOWN
&& pack
->bitmap_nr
)
900 BUG("pack '%s' has no bitmap position, but has %d bitmapped object(s)",
901 pack
->pack_name
, pack
->bitmap_nr
);
903 hashwrite_be32(f
, pack
->bitmap_pos
);
904 hashwrite_be32(f
, pack
->bitmap_nr
);
909 static int write_midx_oid_fanout(struct hashfile
*f
,
912 struct write_midx_context
*ctx
= data
;
913 struct pack_midx_entry
*list
= ctx
->entries
;
914 struct pack_midx_entry
*last
= ctx
->entries
+ ctx
->entries_nr
;
919 * Write the first-level table (the list is sorted,
920 * but we use a 256-entry lookup to be able to avoid
921 * having to do eight extra binary search iterations).
923 for (i
= 0; i
< 256; i
++) {
924 struct pack_midx_entry
*next
= list
;
926 while (next
< last
&& next
->oid
.hash
[0] == i
) {
931 hashwrite_be32(f
, count
);
938 static int write_midx_oid_lookup(struct hashfile
*f
,
941 struct write_midx_context
*ctx
= data
;
942 unsigned char hash_len
= the_hash_algo
->rawsz
;
943 struct pack_midx_entry
*list
= ctx
->entries
;
946 for (i
= 0; i
< ctx
->entries_nr
; i
++) {
947 struct pack_midx_entry
*obj
= list
++;
949 if (i
< ctx
->entries_nr
- 1) {
950 struct pack_midx_entry
*next
= list
;
951 if (oidcmp(&obj
->oid
, &next
->oid
) >= 0)
952 BUG("OIDs not in order: %s >= %s",
953 oid_to_hex(&obj
->oid
),
954 oid_to_hex(&next
->oid
));
957 hashwrite(f
, obj
->oid
.hash
, (int)hash_len
);
963 static int write_midx_object_offsets(struct hashfile
*f
,
966 struct write_midx_context
*ctx
= data
;
967 struct pack_midx_entry
*list
= ctx
->entries
;
968 uint32_t i
, nr_large_offset
= 0;
970 for (i
= 0; i
< ctx
->entries_nr
; i
++) {
971 struct pack_midx_entry
*obj
= list
++;
973 if (ctx
->pack_perm
[obj
->pack_int_id
] == PACK_EXPIRED
)
974 BUG("object %s is in an expired pack with int-id %d",
975 oid_to_hex(&obj
->oid
),
978 hashwrite_be32(f
, ctx
->pack_perm
[obj
->pack_int_id
]);
980 if (ctx
->large_offsets_needed
&& obj
->offset
>> 31)
981 hashwrite_be32(f
, MIDX_LARGE_OFFSET_NEEDED
| nr_large_offset
++);
982 else if (!ctx
->large_offsets_needed
&& obj
->offset
>> 32)
983 BUG("object %s requires a large offset (%"PRIx64
") but the MIDX is not writing large offsets!",
984 oid_to_hex(&obj
->oid
),
987 hashwrite_be32(f
, (uint32_t)obj
->offset
);
993 static int write_midx_large_offsets(struct hashfile
*f
,
996 struct write_midx_context
*ctx
= data
;
997 struct pack_midx_entry
*list
= ctx
->entries
;
998 struct pack_midx_entry
*end
= ctx
->entries
+ ctx
->entries_nr
;
999 uint32_t nr_large_offset
= ctx
->num_large_offsets
;
1001 while (nr_large_offset
) {
1002 struct pack_midx_entry
*obj
;
1006 BUG("too many large-offset objects");
1009 offset
= obj
->offset
;
1011 if (!(offset
>> 31))
1014 hashwrite_be64(f
, offset
);
1022 static int write_midx_revindex(struct hashfile
*f
,
1025 struct write_midx_context
*ctx
= data
;
1028 for (i
= 0; i
< ctx
->entries_nr
; i
++)
1029 hashwrite_be32(f
, ctx
->pack_order
[i
]);
1034 struct midx_pack_order_data
{
1040 static int midx_pack_order_cmp(const void *va
, const void *vb
)
1042 const struct midx_pack_order_data
*a
= va
, *b
= vb
;
1043 if (a
->pack
< b
->pack
)
1045 else if (a
->pack
> b
->pack
)
1047 else if (a
->offset
< b
->offset
)
1049 else if (a
->offset
> b
->offset
)
1055 static uint32_t *midx_pack_order(struct write_midx_context
*ctx
)
1057 struct midx_pack_order_data
*data
;
1058 uint32_t *pack_order
;
1061 trace2_region_enter("midx", "midx_pack_order", the_repository
);
1063 ALLOC_ARRAY(data
, ctx
->entries_nr
);
1064 for (i
= 0; i
< ctx
->entries_nr
; i
++) {
1065 struct pack_midx_entry
*e
= &ctx
->entries
[i
];
1067 data
[i
].pack
= ctx
->pack_perm
[e
->pack_int_id
];
1069 data
[i
].pack
|= (1U << 31);
1070 data
[i
].offset
= e
->offset
;
1073 QSORT(data
, ctx
->entries_nr
, midx_pack_order_cmp
);
1075 ALLOC_ARRAY(pack_order
, ctx
->entries_nr
);
1076 for (i
= 0; i
< ctx
->entries_nr
; i
++) {
1077 struct pack_midx_entry
*e
= &ctx
->entries
[data
[i
].nr
];
1078 struct pack_info
*pack
= &ctx
->info
[ctx
->pack_perm
[e
->pack_int_id
]];
1079 if (pack
->bitmap_pos
== BITMAP_POS_UNKNOWN
)
1080 pack
->bitmap_pos
= i
;
1082 pack_order
[i
] = data
[i
].nr
;
1084 for (i
= 0; i
< ctx
->nr
; i
++) {
1085 struct pack_info
*pack
= &ctx
->info
[ctx
->pack_perm
[i
]];
1086 if (pack
->bitmap_pos
== BITMAP_POS_UNKNOWN
)
1087 pack
->bitmap_pos
= 0;
1091 trace2_region_leave("midx", "midx_pack_order", the_repository
);
1096 static void write_midx_reverse_index(char *midx_name
, unsigned char *midx_hash
,
1097 struct write_midx_context
*ctx
)
1099 struct strbuf buf
= STRBUF_INIT
;
1100 const char *tmp_file
;
1102 trace2_region_enter("midx", "write_midx_reverse_index", the_repository
);
1104 strbuf_addf(&buf
, "%s-%s.rev", midx_name
, hash_to_hex(midx_hash
));
1106 tmp_file
= write_rev_file_order(NULL
, ctx
->pack_order
, ctx
->entries_nr
,
1107 midx_hash
, WRITE_REV
);
1109 if (finalize_object_file(tmp_file
, buf
.buf
))
1110 die(_("cannot store reverse index file"));
1112 strbuf_release(&buf
);
1114 trace2_region_leave("midx", "write_midx_reverse_index", the_repository
);
1117 static void clear_midx_files_ext(const char *object_dir
, const char *ext
,
1118 unsigned char *keep_hash
);
1120 static int midx_checksum_valid(struct multi_pack_index
*m
)
1122 return hashfile_checksum_valid(m
->data
, m
->data_len
);
1125 static void prepare_midx_packing_data(struct packing_data
*pdata
,
1126 struct write_midx_context
*ctx
)
1130 trace2_region_enter("midx", "prepare_midx_packing_data", the_repository
);
1132 memset(pdata
, 0, sizeof(struct packing_data
));
1133 prepare_packing_data(the_repository
, pdata
);
1135 for (i
= 0; i
< ctx
->entries_nr
; i
++) {
1136 struct pack_midx_entry
*from
= &ctx
->entries
[ctx
->pack_order
[i
]];
1137 struct object_entry
*to
= packlist_alloc(pdata
, &from
->oid
);
1139 oe_set_in_pack(pdata
, to
,
1140 ctx
->info
[ctx
->pack_perm
[from
->pack_int_id
]].p
);
1143 trace2_region_leave("midx", "prepare_midx_packing_data", the_repository
);
1146 static int add_ref_to_pending(const char *refname
,
1147 const struct object_id
*oid
,
1148 int flag
, void *cb_data
)
1150 struct rev_info
*revs
= (struct rev_info
*)cb_data
;
1151 struct object_id peeled
;
1152 struct object
*object
;
1154 if ((flag
& REF_ISSYMREF
) && (flag
& REF_ISBROKEN
)) {
1155 warning("symbolic ref is dangling: %s", refname
);
1159 if (!peel_iterated_oid(oid
, &peeled
))
1162 object
= parse_object_or_die(oid
, refname
);
1163 if (object
->type
!= OBJ_COMMIT
)
1166 add_pending_object(revs
, object
, "");
1167 if (bitmap_is_preferred_refname(revs
->repo
, refname
))
1168 object
->flags
|= NEEDS_BITMAP
;
1172 struct bitmap_commit_cb
{
1173 struct commit
**commits
;
1174 size_t commits_nr
, commits_alloc
;
1176 struct write_midx_context
*ctx
;
1179 static const struct object_id
*bitmap_oid_access(size_t index
,
1180 const void *_entries
)
1182 const struct pack_midx_entry
*entries
= _entries
;
1183 return &entries
[index
].oid
;
1186 static void bitmap_show_commit(struct commit
*commit
, void *_data
)
1188 struct bitmap_commit_cb
*data
= _data
;
1189 int pos
= oid_pos(&commit
->object
.oid
, data
->ctx
->entries
,
1190 data
->ctx
->entries_nr
,
1195 ALLOC_GROW(data
->commits
, data
->commits_nr
+ 1, data
->commits_alloc
);
1196 data
->commits
[data
->commits_nr
++] = commit
;
1199 static int read_refs_snapshot(const char *refs_snapshot
,
1200 struct rev_info
*revs
)
1202 struct strbuf buf
= STRBUF_INIT
;
1203 struct object_id oid
;
1204 FILE *f
= xfopen(refs_snapshot
, "r");
1206 while (strbuf_getline(&buf
, f
) != EOF
) {
1207 struct object
*object
;
1209 char *hex
= buf
.buf
;
1210 const char *end
= NULL
;
1212 if (buf
.len
&& *buf
.buf
== '+') {
1217 if (parse_oid_hex(hex
, &oid
, &end
) < 0)
1218 die(_("could not parse line: %s"), buf
.buf
);
1220 die(_("malformed line: %s"), buf
.buf
);
1222 object
= parse_object_or_die(&oid
, NULL
);
1224 object
->flags
|= NEEDS_BITMAP
;
1226 add_pending_object(revs
, object
, "");
1230 strbuf_release(&buf
);
1234 static struct commit
**find_commits_for_midx_bitmap(uint32_t *indexed_commits_nr_p
,
1235 const char *refs_snapshot
,
1236 struct write_midx_context
*ctx
)
1238 struct rev_info revs
;
1239 struct bitmap_commit_cb cb
= {0};
1241 trace2_region_enter("midx", "find_commits_for_midx_bitmap",
1246 repo_init_revisions(the_repository
, &revs
, NULL
);
1247 if (refs_snapshot
) {
1248 read_refs_snapshot(refs_snapshot
, &revs
);
1250 setup_revisions(0, NULL
, &revs
, NULL
);
1251 for_each_ref(add_ref_to_pending
, &revs
);
1255 * Skipping promisor objects here is intentional, since it only excludes
1256 * them from the list of reachable commits that we want to select from
1257 * when computing the selection of MIDX'd commits to receive bitmaps.
1259 * Reachability bitmaps do require that their objects be closed under
1260 * reachability, but fetching any objects missing from promisors at this
1261 * point is too late. But, if one of those objects can be reached from
1262 * an another object that is included in the bitmap, then we will
1263 * complain later that we don't have reachability closure (and fail
1266 fetch_if_missing
= 0;
1267 revs
.exclude_promisor_objects
= 1;
1269 if (prepare_revision_walk(&revs
))
1270 die(_("revision walk setup failed"));
1272 traverse_commit_list(&revs
, bitmap_show_commit
, NULL
, &cb
);
1273 if (indexed_commits_nr_p
)
1274 *indexed_commits_nr_p
= cb
.commits_nr
;
1276 release_revisions(&revs
);
1278 trace2_region_leave("midx", "find_commits_for_midx_bitmap",
1284 static int write_midx_bitmap(const char *midx_name
,
1285 const unsigned char *midx_hash
,
1286 struct packing_data
*pdata
,
1287 struct commit
**commits
,
1288 uint32_t commits_nr
,
1289 uint32_t *pack_order
,
1293 uint16_t options
= 0;
1294 struct pack_idx_entry
**index
;
1295 char *bitmap_name
= xstrfmt("%s-%s.bitmap", midx_name
,
1296 hash_to_hex(midx_hash
));
1298 trace2_region_enter("midx", "write_midx_bitmap", the_repository
);
1300 if (flags
& MIDX_WRITE_BITMAP_HASH_CACHE
)
1301 options
|= BITMAP_OPT_HASH_CACHE
;
1303 if (flags
& MIDX_WRITE_BITMAP_LOOKUP_TABLE
)
1304 options
|= BITMAP_OPT_LOOKUP_TABLE
;
1307 * Build the MIDX-order index based on pdata.objects (which is already
1308 * in MIDX order; c.f., 'midx_pack_order_cmp()' for the definition of
1311 ALLOC_ARRAY(index
, pdata
->nr_objects
);
1312 for (i
= 0; i
< pdata
->nr_objects
; i
++)
1313 index
[i
] = &pdata
->objects
[i
].idx
;
1315 bitmap_writer_show_progress(flags
& MIDX_PROGRESS
);
1316 bitmap_writer_build_type_index(pdata
, index
, pdata
->nr_objects
);
1319 * bitmap_writer_finish expects objects in lex order, but pack_order
1320 * gives us exactly that. use it directly instead of re-sorting the
1323 * This changes the order of objects in 'index' between
1324 * bitmap_writer_build_type_index and bitmap_writer_finish.
1326 * The same re-ordering takes place in the single-pack bitmap code via
1327 * write_idx_file(), which is called by finish_tmp_packfile(), which
1328 * happens between bitmap_writer_build_type_index() and
1329 * bitmap_writer_finish().
1331 for (i
= 0; i
< pdata
->nr_objects
; i
++)
1332 index
[pack_order
[i
]] = &pdata
->objects
[i
].idx
;
1334 bitmap_writer_select_commits(commits
, commits_nr
, -1);
1335 ret
= bitmap_writer_build(pdata
);
1339 bitmap_writer_set_checksum(midx_hash
);
1340 bitmap_writer_finish(index
, pdata
->nr_objects
, bitmap_name
, options
);
1346 trace2_region_leave("midx", "write_midx_bitmap", the_repository
);
1351 static struct multi_pack_index
*lookup_multi_pack_index(struct repository
*r
,
1352 const char *object_dir
)
1354 struct multi_pack_index
*result
= NULL
;
1355 struct multi_pack_index
*cur
;
1356 char *obj_dir_real
= real_pathdup(object_dir
, 1);
1357 struct strbuf cur_path_real
= STRBUF_INIT
;
1359 /* Ensure the given object_dir is local, or a known alternate. */
1360 find_odb(r
, obj_dir_real
);
1362 for (cur
= get_multi_pack_index(r
); cur
; cur
= cur
->next
) {
1363 strbuf_realpath(&cur_path_real
, cur
->object_dir
, 1);
1364 if (!strcmp(obj_dir_real
, cur_path_real
.buf
)) {
1372 strbuf_release(&cur_path_real
);
1376 static int write_midx_internal(const char *object_dir
,
1377 struct string_list
*packs_to_include
,
1378 struct string_list
*packs_to_drop
,
1379 const char *preferred_pack_name
,
1380 const char *refs_snapshot
,
1383 struct strbuf midx_name
= STRBUF_INIT
;
1384 unsigned char midx_hash
[GIT_MAX_RAWSZ
];
1386 struct hashfile
*f
= NULL
;
1387 struct lock_file lk
;
1388 struct write_midx_context ctx
= { 0 };
1389 int bitmapped_packs_concat_len
= 0;
1390 int pack_name_concat_len
= 0;
1391 int dropped_packs
= 0;
1393 struct chunkfile
*cf
;
1395 trace2_region_enter("midx", "write_midx_internal", the_repository
);
1397 get_midx_filename(&midx_name
, object_dir
);
1398 if (safe_create_leading_directories(midx_name
.buf
))
1399 die_errno(_("unable to create leading directories of %s"),
1402 if (!packs_to_include
) {
1404 * Only reference an existing MIDX when not filtering which
1405 * packs to include, since all packs and objects are copied
1406 * blindly from an existing MIDX if one is present.
1408 ctx
.m
= lookup_multi_pack_index(the_repository
, object_dir
);
1411 if (ctx
.m
&& !midx_checksum_valid(ctx
.m
)) {
1412 warning(_("ignoring existing multi-pack-index; checksum mismatch"));
1417 ctx
.alloc
= ctx
.m
? ctx
.m
->num_packs
: 16;
1419 ALLOC_ARRAY(ctx
.info
, ctx
.alloc
);
1422 for (i
= 0; i
< ctx
.m
->num_packs
; i
++) {
1423 ALLOC_GROW(ctx
.info
, ctx
.nr
+ 1, ctx
.alloc
);
1425 if (flags
& MIDX_WRITE_REV_INDEX
) {
1427 * If generating a reverse index, need to have
1428 * packed_git's loaded to compare their
1429 * mtimes and object count.
1431 if (prepare_midx_pack(the_repository
, ctx
.m
, i
)) {
1432 error(_("could not load pack"));
1437 if (open_pack_index(ctx
.m
->packs
[i
]))
1438 die(_("could not open index for %s"),
1439 ctx
.m
->packs
[i
]->pack_name
);
1442 fill_pack_info(&ctx
.info
[ctx
.nr
++], ctx
.m
->packs
[i
],
1443 ctx
.m
->pack_names
[i
], i
);
1447 ctx
.pack_paths_checked
= 0;
1448 if (flags
& MIDX_PROGRESS
)
1449 ctx
.progress
= start_delayed_progress(_("Adding packfiles to multi-pack-index"), 0);
1451 ctx
.progress
= NULL
;
1453 ctx
.to_include
= packs_to_include
;
1455 for_each_file_in_pack_dir(object_dir
, add_pack_to_midx
, &ctx
);
1456 stop_progress(&ctx
.progress
);
1458 if ((ctx
.m
&& ctx
.nr
== ctx
.m
->num_packs
) &&
1459 !(packs_to_include
|| packs_to_drop
)) {
1460 struct bitmap_index
*bitmap_git
;
1462 int want_bitmap
= flags
& MIDX_WRITE_BITMAP
;
1464 bitmap_git
= prepare_midx_bitmap_git(ctx
.m
);
1465 bitmap_exists
= bitmap_git
&& bitmap_is_midx(bitmap_git
);
1466 free_bitmap_index(bitmap_git
);
1468 if (bitmap_exists
|| !want_bitmap
) {
1470 * The correct MIDX already exists, and so does a
1471 * corresponding bitmap (or one wasn't requested).
1474 clear_midx_files_ext(object_dir
, ".bitmap",
1480 if (preferred_pack_name
) {
1481 ctx
.preferred_pack_idx
= -1;
1483 for (i
= 0; i
< ctx
.nr
; i
++) {
1484 if (!cmp_idx_or_pack_name(preferred_pack_name
,
1485 ctx
.info
[i
].pack_name
)) {
1486 ctx
.preferred_pack_idx
= i
;
1491 if (ctx
.preferred_pack_idx
== -1)
1492 warning(_("unknown preferred pack: '%s'"),
1493 preferred_pack_name
);
1494 } else if (ctx
.nr
&&
1495 (flags
& (MIDX_WRITE_REV_INDEX
| MIDX_WRITE_BITMAP
))) {
1496 struct packed_git
*oldest
= ctx
.info
[ctx
.preferred_pack_idx
].p
;
1497 ctx
.preferred_pack_idx
= 0;
1499 if (packs_to_drop
&& packs_to_drop
->nr
)
1500 BUG("cannot write a MIDX bitmap during expiration");
1503 * set a preferred pack when writing a bitmap to ensure that
1504 * the pack from which the first object is selected in pseudo
1505 * pack-order has all of its objects selected from that pack
1506 * (and not another pack containing a duplicate)
1508 for (i
= 1; i
< ctx
.nr
; i
++) {
1509 struct packed_git
*p
= ctx
.info
[i
].p
;
1511 if (!oldest
->num_objects
|| p
->mtime
< oldest
->mtime
) {
1513 ctx
.preferred_pack_idx
= i
;
1517 if (!oldest
->num_objects
) {
1519 * If all packs are empty; unset the preferred index.
1520 * This is acceptable since there will be no duplicate
1521 * objects to resolve, so the preferred value doesn't
1524 ctx
.preferred_pack_idx
= -1;
1528 * otherwise don't mark any pack as preferred to avoid
1529 * interfering with expiration logic below
1531 ctx
.preferred_pack_idx
= -1;
1534 if (ctx
.preferred_pack_idx
> -1) {
1535 struct packed_git
*preferred
= ctx
.info
[ctx
.preferred_pack_idx
].p
;
1536 if (!preferred
->num_objects
) {
1537 error(_("cannot select preferred pack %s with no objects"),
1538 preferred
->pack_name
);
1544 ctx
.entries
= get_sorted_entries(ctx
.m
, ctx
.info
, ctx
.nr
, &ctx
.entries_nr
,
1545 ctx
.preferred_pack_idx
);
1547 ctx
.large_offsets_needed
= 0;
1548 for (i
= 0; i
< ctx
.entries_nr
; i
++) {
1549 if (ctx
.entries
[i
].offset
> 0x7fffffff)
1550 ctx
.num_large_offsets
++;
1551 if (ctx
.entries
[i
].offset
> 0xffffffff)
1552 ctx
.large_offsets_needed
= 1;
1555 QSORT(ctx
.info
, ctx
.nr
, pack_info_compare
);
1557 if (packs_to_drop
&& packs_to_drop
->nr
) {
1559 int missing_drops
= 0;
1561 for (i
= 0; i
< ctx
.nr
&& drop_index
< packs_to_drop
->nr
; i
++) {
1562 int cmp
= strcmp(ctx
.info
[i
].pack_name
,
1563 packs_to_drop
->items
[drop_index
].string
);
1567 ctx
.info
[i
].expired
= 1;
1568 } else if (cmp
> 0) {
1569 error(_("did not see pack-file %s to drop"),
1570 packs_to_drop
->items
[drop_index
].string
);
1575 ctx
.info
[i
].expired
= 0;
1579 if (missing_drops
) {
1586 * pack_perm stores a permutation between pack-int-ids from the
1587 * previous multi-pack-index to the new one we are writing:
1589 * pack_perm[old_id] = new_id
1591 ALLOC_ARRAY(ctx
.pack_perm
, ctx
.nr
);
1592 for (i
= 0; i
< ctx
.nr
; i
++) {
1593 if (ctx
.info
[i
].expired
) {
1595 ctx
.pack_perm
[ctx
.info
[i
].orig_pack_int_id
] = PACK_EXPIRED
;
1597 ctx
.pack_perm
[ctx
.info
[i
].orig_pack_int_id
] = i
- dropped_packs
;
1601 for (i
= 0; i
< ctx
.nr
; i
++) {
1602 if (ctx
.info
[i
].expired
)
1604 pack_name_concat_len
+= strlen(ctx
.info
[i
].pack_name
) + 1;
1605 bitmapped_packs_concat_len
+= 2 * sizeof(uint32_t);
1608 /* Check that the preferred pack wasn't expired (if given). */
1609 if (preferred_pack_name
) {
1610 struct pack_info
*preferred
= bsearch(preferred_pack_name
,
1613 idx_or_pack_name_cmp
);
1615 uint32_t perm
= ctx
.pack_perm
[preferred
->orig_pack_int_id
];
1616 if (perm
== PACK_EXPIRED
)
1617 warning(_("preferred pack '%s' is expired"),
1618 preferred_pack_name
);
1622 if (pack_name_concat_len
% MIDX_CHUNK_ALIGNMENT
)
1623 pack_name_concat_len
+= MIDX_CHUNK_ALIGNMENT
-
1624 (pack_name_concat_len
% MIDX_CHUNK_ALIGNMENT
);
1626 hold_lock_file_for_update(&lk
, midx_name
.buf
, LOCK_DIE_ON_ERROR
);
1627 f
= hashfd(get_lock_file_fd(&lk
), get_lock_file_path(&lk
));
1629 if (ctx
.nr
- dropped_packs
== 0) {
1630 error(_("no pack files to index."));
1635 if (!ctx
.entries_nr
) {
1636 if (flags
& MIDX_WRITE_BITMAP
)
1637 warning(_("refusing to write multi-pack .bitmap without any objects"));
1638 flags
&= ~(MIDX_WRITE_REV_INDEX
| MIDX_WRITE_BITMAP
);
1641 cf
= init_chunkfile(f
);
1643 add_chunk(cf
, MIDX_CHUNKID_PACKNAMES
, pack_name_concat_len
,
1644 write_midx_pack_names
);
1645 add_chunk(cf
, MIDX_CHUNKID_OIDFANOUT
, MIDX_CHUNK_FANOUT_SIZE
,
1646 write_midx_oid_fanout
);
1647 add_chunk(cf
, MIDX_CHUNKID_OIDLOOKUP
,
1648 st_mult(ctx
.entries_nr
, the_hash_algo
->rawsz
),
1649 write_midx_oid_lookup
);
1650 add_chunk(cf
, MIDX_CHUNKID_OBJECTOFFSETS
,
1651 st_mult(ctx
.entries_nr
, MIDX_CHUNK_OFFSET_WIDTH
),
1652 write_midx_object_offsets
);
1654 if (ctx
.large_offsets_needed
)
1655 add_chunk(cf
, MIDX_CHUNKID_LARGEOFFSETS
,
1656 st_mult(ctx
.num_large_offsets
,
1657 MIDX_CHUNK_LARGE_OFFSET_WIDTH
),
1658 write_midx_large_offsets
);
1660 if (flags
& (MIDX_WRITE_REV_INDEX
| MIDX_WRITE_BITMAP
)) {
1661 ctx
.pack_order
= midx_pack_order(&ctx
);
1662 add_chunk(cf
, MIDX_CHUNKID_REVINDEX
,
1663 st_mult(ctx
.entries_nr
, sizeof(uint32_t)),
1664 write_midx_revindex
);
1665 add_chunk(cf
, MIDX_CHUNKID_BITMAPPEDPACKS
,
1666 bitmapped_packs_concat_len
,
1667 write_midx_bitmapped_packs
);
1670 write_midx_header(f
, get_num_chunks(cf
), ctx
.nr
- dropped_packs
);
1671 write_chunkfile(cf
, &ctx
);
1673 finalize_hashfile(f
, midx_hash
, FSYNC_COMPONENT_PACK_METADATA
,
1674 CSUM_FSYNC
| CSUM_HASH_IN_STREAM
);
1677 if (flags
& MIDX_WRITE_REV_INDEX
&&
1678 git_env_bool("GIT_TEST_MIDX_WRITE_REV", 0))
1679 write_midx_reverse_index(midx_name
.buf
, midx_hash
, &ctx
);
1681 if (flags
& MIDX_WRITE_BITMAP
) {
1682 struct packing_data pdata
;
1683 struct commit
**commits
;
1684 uint32_t commits_nr
;
1686 if (!ctx
.entries_nr
)
1687 BUG("cannot write a bitmap without any objects");
1689 prepare_midx_packing_data(&pdata
, &ctx
);
1691 commits
= find_commits_for_midx_bitmap(&commits_nr
, refs_snapshot
, &ctx
);
1694 * The previous steps translated the information from
1695 * 'entries' into information suitable for constructing
1696 * bitmaps. We no longer need that array, so clear it to
1697 * reduce memory pressure.
1699 FREE_AND_NULL(ctx
.entries
);
1702 if (write_midx_bitmap(midx_name
.buf
, midx_hash
, &pdata
,
1703 commits
, commits_nr
, ctx
.pack_order
,
1705 error(_("could not write multi-pack bitmap"));
1707 clear_packing_data(&pdata
);
1712 clear_packing_data(&pdata
);
1716 * NOTE: Do not use ctx.entries beyond this point, since it might
1717 * have been freed in the previous if block.
1721 close_object_store(the_repository
->objects
);
1723 if (commit_lock_file(&lk
) < 0)
1724 die_errno(_("could not write multi-pack-index"));
1726 clear_midx_files_ext(object_dir
, ".bitmap", midx_hash
);
1727 clear_midx_files_ext(object_dir
, ".rev", midx_hash
);
1730 for (i
= 0; i
< ctx
.nr
; i
++) {
1731 if (ctx
.info
[i
].p
) {
1732 close_pack(ctx
.info
[i
].p
);
1733 free(ctx
.info
[i
].p
);
1735 free(ctx
.info
[i
].pack_name
);
1740 free(ctx
.pack_perm
);
1741 free(ctx
.pack_order
);
1742 strbuf_release(&midx_name
);
1744 trace2_region_leave("midx", "write_midx_internal", the_repository
);
1749 int write_midx_file(const char *object_dir
,
1750 const char *preferred_pack_name
,
1751 const char *refs_snapshot
,
1754 return write_midx_internal(object_dir
, NULL
, NULL
, preferred_pack_name
,
1755 refs_snapshot
, flags
);
1758 int write_midx_file_only(const char *object_dir
,
1759 struct string_list
*packs_to_include
,
1760 const char *preferred_pack_name
,
1761 const char *refs_snapshot
,
1764 return write_midx_internal(object_dir
, packs_to_include
, NULL
,
1765 preferred_pack_name
, refs_snapshot
, flags
);
1768 struct clear_midx_data
{
1773 static void clear_midx_file_ext(const char *full_path
, size_t full_path_len UNUSED
,
1774 const char *file_name
, void *_data
)
1776 struct clear_midx_data
*data
= _data
;
1778 if (!(starts_with(file_name
, "multi-pack-index-") &&
1779 ends_with(file_name
, data
->ext
)))
1781 if (data
->keep
&& !strcmp(data
->keep
, file_name
))
1784 if (unlink(full_path
))
1785 die_errno(_("failed to remove %s"), full_path
);
1788 static void clear_midx_files_ext(const char *object_dir
, const char *ext
,
1789 unsigned char *keep_hash
)
1791 struct clear_midx_data data
;
1792 memset(&data
, 0, sizeof(struct clear_midx_data
));
1795 data
.keep
= xstrfmt("multi-pack-index-%s%s",
1796 hash_to_hex(keep_hash
), ext
);
1799 for_each_file_in_pack_dir(object_dir
,
1800 clear_midx_file_ext
,
1806 void clear_midx_file(struct repository
*r
)
1808 struct strbuf midx
= STRBUF_INIT
;
1810 get_midx_filename(&midx
, r
->objects
->odb
->path
);
1812 if (r
->objects
&& r
->objects
->multi_pack_index
) {
1813 close_midx(r
->objects
->multi_pack_index
);
1814 r
->objects
->multi_pack_index
= NULL
;
1817 if (remove_path(midx
.buf
))
1818 die(_("failed to clear multi-pack-index at %s"), midx
.buf
);
1820 clear_midx_files_ext(r
->objects
->odb
->path
, ".bitmap", NULL
);
1821 clear_midx_files_ext(r
->objects
->odb
->path
, ".rev", NULL
);
1823 strbuf_release(&midx
);
1826 static int verify_midx_error
;
1828 __attribute__((format (printf
, 1, 2)))
1829 static void midx_report(const char *fmt
, ...)
1832 verify_midx_error
= 1;
1834 vfprintf(stderr
, fmt
, ap
);
1835 fprintf(stderr
, "\n");
1839 struct pair_pos_vs_id
1842 uint32_t pack_int_id
;
1845 static int compare_pair_pos_vs_id(const void *_a
, const void *_b
)
1847 struct pair_pos_vs_id
*a
= (struct pair_pos_vs_id
*)_a
;
1848 struct pair_pos_vs_id
*b
= (struct pair_pos_vs_id
*)_b
;
1850 return b
->pack_int_id
- a
->pack_int_id
;
1854 * Limit calls to display_progress() for performance reasons.
1855 * The interval here was arbitrarily chosen.
1857 #define SPARSE_PROGRESS_INTERVAL (1 << 12)
1858 #define midx_display_sparse_progress(progress, n) \
1860 uint64_t _n = (n); \
1861 if ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0) \
1862 display_progress(progress, _n); \
1865 int verify_midx_file(struct repository
*r
, const char *object_dir
, unsigned flags
)
1867 struct pair_pos_vs_id
*pairs
= NULL
;
1869 struct progress
*progress
= NULL
;
1870 struct multi_pack_index
*m
= load_multi_pack_index(object_dir
, 1);
1871 verify_midx_error
= 0;
1876 struct strbuf filename
= STRBUF_INIT
;
1878 get_midx_filename(&filename
, object_dir
);
1880 if (!stat(filename
.buf
, &sb
)) {
1881 error(_("multi-pack-index file exists, but failed to parse"));
1884 strbuf_release(&filename
);
1888 if (!midx_checksum_valid(m
))
1889 midx_report(_("incorrect checksum"));
1891 if (flags
& MIDX_PROGRESS
)
1892 progress
= start_delayed_progress(_("Looking for referenced packfiles"),
1894 for (i
= 0; i
< m
->num_packs
; i
++) {
1895 if (prepare_midx_pack(r
, m
, i
))
1896 midx_report("failed to load pack in position %d", i
);
1898 display_progress(progress
, i
+ 1);
1900 stop_progress(&progress
);
1902 if (m
->num_objects
== 0) {
1903 midx_report(_("the midx contains no oid"));
1905 * Remaining tests assume that we have objects, so we can
1911 if (flags
& MIDX_PROGRESS
)
1912 progress
= start_sparse_progress(_("Verifying OID order in multi-pack-index"),
1913 m
->num_objects
- 1);
1914 for (i
= 0; i
< m
->num_objects
- 1; i
++) {
1915 struct object_id oid1
, oid2
;
1917 nth_midxed_object_oid(&oid1
, m
, i
);
1918 nth_midxed_object_oid(&oid2
, m
, i
+ 1);
1920 if (oidcmp(&oid1
, &oid2
) >= 0)
1921 midx_report(_("oid lookup out of order: oid[%d] = %s >= %s = oid[%d]"),
1922 i
, oid_to_hex(&oid1
), oid_to_hex(&oid2
), i
+ 1);
1924 midx_display_sparse_progress(progress
, i
+ 1);
1926 stop_progress(&progress
);
1929 * Create an array mapping each object to its packfile id. Sort it
1930 * to group the objects by packfile. Use this permutation to visit
1931 * each of the objects and only require 1 packfile to be open at a
1934 ALLOC_ARRAY(pairs
, m
->num_objects
);
1935 for (i
= 0; i
< m
->num_objects
; i
++) {
1937 pairs
[i
].pack_int_id
= nth_midxed_pack_int_id(m
, i
);
1940 if (flags
& MIDX_PROGRESS
)
1941 progress
= start_sparse_progress(_("Sorting objects by packfile"),
1943 display_progress(progress
, 0); /* TODO: Measure QSORT() progress */
1944 QSORT(pairs
, m
->num_objects
, compare_pair_pos_vs_id
);
1945 stop_progress(&progress
);
1947 if (flags
& MIDX_PROGRESS
)
1948 progress
= start_sparse_progress(_("Verifying object offsets"), m
->num_objects
);
1949 for (i
= 0; i
< m
->num_objects
; i
++) {
1950 struct object_id oid
;
1951 struct pack_entry e
;
1952 off_t m_offset
, p_offset
;
1954 if (i
> 0 && pairs
[i
-1].pack_int_id
!= pairs
[i
].pack_int_id
&&
1955 m
->packs
[pairs
[i
-1].pack_int_id
])
1957 close_pack_fd(m
->packs
[pairs
[i
-1].pack_int_id
]);
1958 close_pack_index(m
->packs
[pairs
[i
-1].pack_int_id
]);
1961 nth_midxed_object_oid(&oid
, m
, pairs
[i
].pos
);
1963 if (!fill_midx_entry(r
, &oid
, &e
, m
)) {
1964 midx_report(_("failed to load pack entry for oid[%d] = %s"),
1965 pairs
[i
].pos
, oid_to_hex(&oid
));
1969 if (open_pack_index(e
.p
)) {
1970 midx_report(_("failed to load pack-index for packfile %s"),
1975 m_offset
= e
.offset
;
1976 p_offset
= find_pack_entry_one(oid
.hash
, e
.p
);
1978 if (m_offset
!= p_offset
)
1979 midx_report(_("incorrect object offset for oid[%d] = %s: %"PRIx64
" != %"PRIx64
),
1980 pairs
[i
].pos
, oid_to_hex(&oid
), m_offset
, p_offset
);
1982 midx_display_sparse_progress(progress
, i
+ 1);
1984 stop_progress(&progress
);
1990 return verify_midx_error
;
1993 int expire_midx_packs(struct repository
*r
, const char *object_dir
, unsigned flags
)
1995 uint32_t i
, *count
, result
= 0;
1996 struct string_list packs_to_drop
= STRING_LIST_INIT_DUP
;
1997 struct multi_pack_index
*m
= lookup_multi_pack_index(r
, object_dir
);
1998 struct progress
*progress
= NULL
;
2003 CALLOC_ARRAY(count
, m
->num_packs
);
2005 if (flags
& MIDX_PROGRESS
)
2006 progress
= start_delayed_progress(_("Counting referenced objects"),
2008 for (i
= 0; i
< m
->num_objects
; i
++) {
2009 int pack_int_id
= nth_midxed_pack_int_id(m
, i
);
2010 count
[pack_int_id
]++;
2011 display_progress(progress
, i
+ 1);
2013 stop_progress(&progress
);
2015 if (flags
& MIDX_PROGRESS
)
2016 progress
= start_delayed_progress(_("Finding and deleting unreferenced packfiles"),
2018 for (i
= 0; i
< m
->num_packs
; i
++) {
2020 display_progress(progress
, i
+ 1);
2025 if (prepare_midx_pack(r
, m
, i
))
2028 if (m
->packs
[i
]->pack_keep
|| m
->packs
[i
]->is_cruft
)
2031 pack_name
= xstrdup(m
->packs
[i
]->pack_name
);
2032 close_pack(m
->packs
[i
]);
2034 string_list_insert(&packs_to_drop
, m
->pack_names
[i
]);
2035 unlink_pack_path(pack_name
, 0);
2038 stop_progress(&progress
);
2042 if (packs_to_drop
.nr
)
2043 result
= write_midx_internal(object_dir
, NULL
, &packs_to_drop
, NULL
, NULL
, flags
);
2045 string_list_clear(&packs_to_drop
, 0);
2050 struct repack_info
{
2052 uint32_t referenced_objects
;
2053 uint32_t pack_int_id
;
2056 static int compare_by_mtime(const void *a_
, const void *b_
)
2058 const struct repack_info
*a
, *b
;
2060 a
= (const struct repack_info
*)a_
;
2061 b
= (const struct repack_info
*)b_
;
2063 if (a
->mtime
< b
->mtime
)
2065 if (a
->mtime
> b
->mtime
)
2070 static int fill_included_packs_all(struct repository
*r
,
2071 struct multi_pack_index
*m
,
2072 unsigned char *include_pack
)
2074 uint32_t i
, count
= 0;
2075 int pack_kept_objects
= 0;
2077 repo_config_get_bool(r
, "repack.packkeptobjects", &pack_kept_objects
);
2079 for (i
= 0; i
< m
->num_packs
; i
++) {
2080 if (prepare_midx_pack(r
, m
, i
))
2082 if (!pack_kept_objects
&& m
->packs
[i
]->pack_keep
)
2084 if (m
->packs
[i
]->is_cruft
)
2087 include_pack
[i
] = 1;
2094 static int fill_included_packs_batch(struct repository
*r
,
2095 struct multi_pack_index
*m
,
2096 unsigned char *include_pack
,
2099 uint32_t i
, packs_to_repack
;
2101 struct repack_info
*pack_info
;
2102 int pack_kept_objects
= 0;
2104 CALLOC_ARRAY(pack_info
, m
->num_packs
);
2106 repo_config_get_bool(r
, "repack.packkeptobjects", &pack_kept_objects
);
2108 for (i
= 0; i
< m
->num_packs
; i
++) {
2109 pack_info
[i
].pack_int_id
= i
;
2111 if (prepare_midx_pack(r
, m
, i
))
2114 pack_info
[i
].mtime
= m
->packs
[i
]->mtime
;
2117 for (i
= 0; i
< m
->num_objects
; i
++) {
2118 uint32_t pack_int_id
= nth_midxed_pack_int_id(m
, i
);
2119 pack_info
[pack_int_id
].referenced_objects
++;
2122 QSORT(pack_info
, m
->num_packs
, compare_by_mtime
);
2125 packs_to_repack
= 0;
2126 for (i
= 0; total_size
< batch_size
&& i
< m
->num_packs
; i
++) {
2127 int pack_int_id
= pack_info
[i
].pack_int_id
;
2128 struct packed_git
*p
= m
->packs
[pack_int_id
];
2129 size_t expected_size
;
2133 if (!pack_kept_objects
&& p
->pack_keep
)
2137 if (open_pack_index(p
) || !p
->num_objects
)
2140 expected_size
= st_mult(p
->pack_size
,
2141 pack_info
[i
].referenced_objects
);
2142 expected_size
/= p
->num_objects
;
2144 if (expected_size
>= batch_size
)
2148 total_size
+= expected_size
;
2149 include_pack
[pack_int_id
] = 1;
2154 if (packs_to_repack
< 2)
2160 int midx_repack(struct repository
*r
, const char *object_dir
, size_t batch_size
, unsigned flags
)
2164 unsigned char *include_pack
;
2165 struct child_process cmd
= CHILD_PROCESS_INIT
;
2167 struct strbuf base_name
= STRBUF_INIT
;
2168 struct multi_pack_index
*m
= lookup_multi_pack_index(r
, object_dir
);
2171 * When updating the default for these configuration
2172 * variables in builtin/repack.c, these must be adjusted
2175 int delta_base_offset
= 1;
2176 int use_delta_islands
= 0;
2181 CALLOC_ARRAY(include_pack
, m
->num_packs
);
2184 if (fill_included_packs_batch(r
, m
, include_pack
, batch_size
))
2186 } else if (fill_included_packs_all(r
, m
, include_pack
))
2189 repo_config_get_bool(r
, "repack.usedeltabaseoffset", &delta_base_offset
);
2190 repo_config_get_bool(r
, "repack.usedeltaislands", &use_delta_islands
);
2192 strvec_push(&cmd
.args
, "pack-objects");
2194 strbuf_addstr(&base_name
, object_dir
);
2195 strbuf_addstr(&base_name
, "/pack/pack");
2196 strvec_push(&cmd
.args
, base_name
.buf
);
2198 if (delta_base_offset
)
2199 strvec_push(&cmd
.args
, "--delta-base-offset");
2200 if (use_delta_islands
)
2201 strvec_push(&cmd
.args
, "--delta-islands");
2203 if (flags
& MIDX_PROGRESS
)
2204 strvec_push(&cmd
.args
, "--progress");
2206 strvec_push(&cmd
.args
, "-q");
2208 strbuf_release(&base_name
);
2211 cmd
.in
= cmd
.out
= -1;
2213 if (start_command(&cmd
)) {
2214 error(_("could not start pack-objects"));
2219 cmd_in
= xfdopen(cmd
.in
, "w");
2221 for (i
= 0; i
< m
->num_objects
; i
++) {
2222 struct object_id oid
;
2223 uint32_t pack_int_id
= nth_midxed_pack_int_id(m
, i
);
2225 if (!include_pack
[pack_int_id
])
2228 nth_midxed_object_oid(&oid
, m
, i
);
2229 fprintf(cmd_in
, "%s\n", oid_to_hex(&oid
));
2233 if (finish_command(&cmd
)) {
2234 error(_("could not finish pack-objects"));
2239 result
= write_midx_internal(object_dir
, NULL
, NULL
, NULL
, NULL
, flags
);