| 1 | #define DISABLE_SIGN_COMPARE_WARNINGS |
| 2 | |
| 3 | #include "git-compat-util.h" |
| 4 | #include "config.h" |
| 5 | #include "dir.h" |
| 6 | #include "hex.h" |
| 7 | #include "packfile.h" |
| 8 | #include "hash-lookup.h" |
| 9 | #include "midx.h" |
| 10 | #include "progress.h" |
| 11 | #include "trace2.h" |
| 12 | #include "chunk-format.h" |
| 13 | #include "pack-bitmap.h" |
| 14 | #include "pack-revindex.h" |
| 15 | #include "strvec.h" |
| 16 | |
| 17 | #define MIDX_PACK_ERROR ((void *)(intptr_t)-1) |
| 18 | |
| 19 | int midx_checksum_valid(struct multi_pack_index *m); |
| 20 | void clear_midx_files_ext(struct odb_source_packed *source, const char *ext, |
| 21 | const char *keep_hash); |
| 22 | void clear_incremental_midx_files_ext(struct odb_source_packed *source, const char *ext, |
| 23 | const struct strvec *keep_hashes); |
| 24 | int cmp_idx_or_pack_name(const char *idx_or_pack_name, |
| 25 | const char *idx_name); |
| 26 | |
| 27 | const char *midx_get_checksum_hex(const struct multi_pack_index *m) |
| 28 | { |
| 29 | return hash_to_hex_algop(midx_get_checksum_hash(m), |
| 30 | m->source->base.odb->repo->hash_algo); |
| 31 | } |
| 32 | |
| 33 | const unsigned char *midx_get_checksum_hash(const struct multi_pack_index *m) |
| 34 | { |
| 35 | return m->data + m->data_len - m->source->base.odb->repo->hash_algo->rawsz; |
| 36 | } |
| 37 | |
| 38 | void get_midx_filename(struct odb_source_packed *source, struct strbuf *out) |
| 39 | { |
| 40 | get_midx_filename_ext(source, out, NULL, NULL); |
| 41 | } |
| 42 | |
| 43 | void get_midx_filename_ext(struct odb_source_packed *source, struct strbuf *out, |
| 44 | const unsigned char *hash, const char *ext) |
| 45 | { |
| 46 | strbuf_addf(out, "%s/pack/multi-pack-index", source->base.path); |
| 47 | if (ext) |
| 48 | strbuf_addf(out, "-%s.%s", hash_to_hex_algop(hash, source->base.odb->repo->hash_algo), ext); |
| 49 | } |
| 50 | |
| 51 | static int midx_read_oid_fanout(const unsigned char *chunk_start, |
| 52 | size_t chunk_size, void *data) |
| 53 | { |
| 54 | int i; |
| 55 | struct multi_pack_index *m = data; |
| 56 | m->chunk_oid_fanout = (uint32_t *)chunk_start; |
| 57 | |
| 58 | if (chunk_size != 4 * 256) { |
| 59 | error(_("multi-pack-index OID fanout is of the wrong size")); |
| 60 | return 1; |
| 61 | } |
| 62 | for (i = 0; i < 255; i++) { |
| 63 | uint32_t oid_fanout1 = ntohl(m->chunk_oid_fanout[i]); |
| 64 | uint32_t oid_fanout2 = ntohl(m->chunk_oid_fanout[i+1]); |
| 65 | |
| 66 | if (oid_fanout1 > oid_fanout2) { |
| 67 | error(_("oid fanout out of order: fanout[%d] = %"PRIx32" > %"PRIx32" = fanout[%d]"), |
| 68 | i, oid_fanout1, oid_fanout2, i + 1); |
| 69 | return 1; |
| 70 | } |
| 71 | } |
| 72 | m->num_objects = ntohl(m->chunk_oid_fanout[255]); |
| 73 | return 0; |
| 74 | } |
| 75 | |
| 76 | static int midx_read_oid_lookup(const unsigned char *chunk_start, |
| 77 | size_t chunk_size, void *data) |
| 78 | { |
| 79 | struct multi_pack_index *m = data; |
| 80 | m->chunk_oid_lookup = chunk_start; |
| 81 | |
| 82 | if (chunk_size != st_mult(m->hash_len, m->num_objects)) { |
| 83 | error(_("multi-pack-index OID lookup chunk is the wrong size")); |
| 84 | return 1; |
| 85 | } |
| 86 | return 0; |
| 87 | } |
| 88 | |
| 89 | static int midx_read_object_offsets(const unsigned char *chunk_start, |
| 90 | size_t chunk_size, void *data) |
| 91 | { |
| 92 | struct multi_pack_index *m = data; |
| 93 | m->chunk_object_offsets = chunk_start; |
| 94 | |
| 95 | if (chunk_size != st_mult(m->num_objects, MIDX_CHUNK_OFFSET_WIDTH)) { |
| 96 | error(_("multi-pack-index object offset chunk is the wrong size")); |
| 97 | return 1; |
| 98 | } |
| 99 | return 0; |
| 100 | } |
| 101 | |
| 102 | struct multi_pack_index *get_multi_pack_index(struct odb_source_packed *source) |
| 103 | { |
| 104 | odb_source_prepare(&source->base, 0); |
| 105 | return source->midx; |
| 106 | } |
| 107 | |
| 108 | static struct multi_pack_index *load_multi_pack_index_one(struct odb_source_packed *source, |
| 109 | const char *midx_name) |
| 110 | { |
| 111 | struct repository *r = source->base.odb->repo; |
| 112 | struct multi_pack_index *m = NULL; |
| 113 | int fd; |
| 114 | struct stat st; |
| 115 | size_t midx_size; |
| 116 | void *midx_map = NULL; |
| 117 | uint32_t hash_version; |
| 118 | uint32_t i; |
| 119 | const char *cur_pack_name; |
| 120 | struct chunkfile *cf = NULL; |
| 121 | |
| 122 | fd = git_open(midx_name); |
| 123 | |
| 124 | if (fd < 0) |
| 125 | goto cleanup_fail; |
| 126 | if (fstat(fd, &st)) { |
| 127 | error_errno(_("failed to read %s"), midx_name); |
| 128 | goto cleanup_fail; |
| 129 | } |
| 130 | |
| 131 | midx_size = xsize_t(st.st_size); |
| 132 | |
| 133 | if (midx_size < (MIDX_HEADER_SIZE + r->hash_algo->rawsz)) { |
| 134 | error(_("multi-pack-index file %s is too small"), midx_name); |
| 135 | goto cleanup_fail; |
| 136 | } |
| 137 | |
| 138 | midx_map = xmmap(NULL, midx_size, PROT_READ, MAP_PRIVATE, fd, 0); |
| 139 | close(fd); |
| 140 | |
| 141 | CALLOC_ARRAY(m, 1); |
| 142 | m->data = midx_map; |
| 143 | m->data_len = midx_size; |
| 144 | m->source = source; |
| 145 | |
| 146 | m->signature = get_be32(m->data); |
| 147 | if (m->signature != MIDX_SIGNATURE) |
| 148 | die(_("multi-pack-index signature 0x%08x does not match signature 0x%08x"), |
| 149 | m->signature, MIDX_SIGNATURE); |
| 150 | |
| 151 | m->version = m->data[MIDX_BYTE_FILE_VERSION]; |
| 152 | if (m->version != MIDX_VERSION_V1 && m->version != MIDX_VERSION_V2) |
| 153 | die(_("multi-pack-index version %d not recognized"), |
| 154 | m->version); |
| 155 | |
| 156 | hash_version = m->data[MIDX_BYTE_HASH_VERSION]; |
| 157 | if (hash_version != oid_version(r->hash_algo)) { |
| 158 | error(_("multi-pack-index hash version %u does not match version %u"), |
| 159 | hash_version, oid_version(r->hash_algo)); |
| 160 | goto cleanup_fail; |
| 161 | } |
| 162 | m->hash_len = r->hash_algo->rawsz; |
| 163 | |
| 164 | m->num_chunks = m->data[MIDX_BYTE_NUM_CHUNKS]; |
| 165 | |
| 166 | m->num_packs = get_be32(m->data + MIDX_BYTE_NUM_PACKS); |
| 167 | |
| 168 | m->preferred_pack_idx = -1; |
| 169 | |
| 170 | cf = init_chunkfile(NULL); |
| 171 | |
| 172 | if (read_table_of_contents(cf, m->data, midx_size, |
| 173 | MIDX_HEADER_SIZE, m->num_chunks, |
| 174 | MIDX_CHUNK_ALIGNMENT)) |
| 175 | goto cleanup_fail; |
| 176 | |
| 177 | if (pair_chunk(cf, MIDX_CHUNKID_PACKNAMES, &m->chunk_pack_names, &m->chunk_pack_names_len)) |
| 178 | die(_("multi-pack-index required pack-name chunk missing or corrupted")); |
| 179 | if (read_chunk(cf, MIDX_CHUNKID_OIDFANOUT, midx_read_oid_fanout, m)) |
| 180 | die(_("multi-pack-index required OID fanout chunk missing or corrupted")); |
| 181 | if (read_chunk(cf, MIDX_CHUNKID_OIDLOOKUP, midx_read_oid_lookup, m)) |
| 182 | die(_("multi-pack-index required OID lookup chunk missing or corrupted")); |
| 183 | if (read_chunk(cf, MIDX_CHUNKID_OBJECTOFFSETS, midx_read_object_offsets, m)) |
| 184 | die(_("multi-pack-index required object offsets chunk missing or corrupted")); |
| 185 | |
| 186 | pair_chunk(cf, MIDX_CHUNKID_LARGEOFFSETS, &m->chunk_large_offsets, |
| 187 | &m->chunk_large_offsets_len); |
| 188 | if (git_env_bool("GIT_TEST_MIDX_READ_BTMP", 1)) |
| 189 | pair_chunk(cf, MIDX_CHUNKID_BITMAPPEDPACKS, |
| 190 | (const unsigned char **)&m->chunk_bitmapped_packs, |
| 191 | &m->chunk_bitmapped_packs_len); |
| 192 | |
| 193 | if (git_env_bool("GIT_TEST_MIDX_READ_RIDX", 1)) |
| 194 | pair_chunk(cf, MIDX_CHUNKID_REVINDEX, &m->chunk_revindex, |
| 195 | &m->chunk_revindex_len); |
| 196 | |
| 197 | CALLOC_ARRAY(m->pack_names, m->num_packs); |
| 198 | CALLOC_ARRAY(m->packs, m->num_packs); |
| 199 | |
| 200 | cur_pack_name = (const char *)m->chunk_pack_names; |
| 201 | for (i = 0; i < m->num_packs; i++) { |
| 202 | const char *end; |
| 203 | size_t avail = m->chunk_pack_names_len - |
| 204 | (cur_pack_name - (const char *)m->chunk_pack_names); |
| 205 | |
| 206 | m->pack_names[i] = cur_pack_name; |
| 207 | |
| 208 | end = memchr(cur_pack_name, '\0', avail); |
| 209 | if (!end) |
| 210 | die(_("multi-pack-index pack-name chunk is too short")); |
| 211 | cur_pack_name = end + 1; |
| 212 | |
| 213 | if (m->version == MIDX_VERSION_V1 && |
| 214 | i && strcmp(m->pack_names[i], m->pack_names[i - 1]) <= 0) |
| 215 | die(_("multi-pack-index pack names out of order: '%s' before '%s'"), |
| 216 | m->pack_names[i - 1], |
| 217 | m->pack_names[i]); |
| 218 | } |
| 219 | |
| 220 | trace2_data_intmax("midx", r, "load/num_packs", m->num_packs); |
| 221 | trace2_data_intmax("midx", r, "load/num_objects", m->num_objects); |
| 222 | |
| 223 | free_chunkfile(cf); |
| 224 | return m; |
| 225 | |
| 226 | cleanup_fail: |
| 227 | free(m); |
| 228 | free_chunkfile(cf); |
| 229 | if (midx_map) |
| 230 | munmap(midx_map, midx_size); |
| 231 | if (0 <= fd) |
| 232 | close(fd); |
| 233 | return NULL; |
| 234 | } |
| 235 | |
| 236 | void get_midx_chain_dirname(struct odb_source_packed *source, struct strbuf *buf) |
| 237 | { |
| 238 | strbuf_addf(buf, "%s/pack/multi-pack-index.d", source->base.path); |
| 239 | } |
| 240 | |
| 241 | void get_midx_chain_filename(struct odb_source_packed *source, struct strbuf *buf) |
| 242 | { |
| 243 | get_midx_chain_dirname(source, buf); |
| 244 | strbuf_addstr(buf, "/multi-pack-index-chain"); |
| 245 | } |
| 246 | |
| 247 | void get_split_midx_filename_ext(struct odb_source_packed *source, struct strbuf *buf, |
| 248 | const unsigned char *hash, const char *ext) |
| 249 | { |
| 250 | get_midx_chain_dirname(source, buf); |
| 251 | strbuf_addf(buf, "/multi-pack-index-%s.%s", |
| 252 | hash_to_hex_algop(hash, source->base.odb->repo->hash_algo), ext); |
| 253 | } |
| 254 | |
| 255 | static int open_multi_pack_index_chain(const struct git_hash_algo *hash_algo, |
| 256 | const char *chain_file, int *fd, |
| 257 | struct stat *st) |
| 258 | { |
| 259 | *fd = git_open(chain_file); |
| 260 | if (*fd < 0) |
| 261 | return 0; |
| 262 | if (fstat(*fd, st)) { |
| 263 | close(*fd); |
| 264 | return 0; |
| 265 | } |
| 266 | if (st->st_size < hash_algo->hexsz) { |
| 267 | close(*fd); |
| 268 | if (!st->st_size) { |
| 269 | /* treat empty files the same as missing */ |
| 270 | errno = ENOENT; |
| 271 | } else { |
| 272 | warning(_("multi-pack-index chain file too small")); |
| 273 | errno = EINVAL; |
| 274 | } |
| 275 | return 0; |
| 276 | } |
| 277 | return 1; |
| 278 | } |
| 279 | |
| 280 | static int add_midx_to_chain(struct multi_pack_index *midx, |
| 281 | struct multi_pack_index *midx_chain) |
| 282 | { |
| 283 | if (midx_chain) { |
| 284 | if (unsigned_add_overflows(midx_chain->num_packs, |
| 285 | midx_chain->num_packs_in_base)) { |
| 286 | warning(_("pack count in base MIDX too high: %"PRIuMAX), |
| 287 | (uintmax_t)midx_chain->num_packs_in_base); |
| 288 | return 0; |
| 289 | } |
| 290 | if (unsigned_add_overflows(midx_chain->num_objects, |
| 291 | midx_chain->num_objects_in_base)) { |
| 292 | warning(_("object count in base MIDX too high: %"PRIuMAX), |
| 293 | (uintmax_t)midx_chain->num_objects_in_base); |
| 294 | return 0; |
| 295 | } |
| 296 | midx->num_packs_in_base = midx_chain->num_packs + |
| 297 | midx_chain->num_packs_in_base; |
| 298 | midx->num_objects_in_base = midx_chain->num_objects + |
| 299 | midx_chain->num_objects_in_base; |
| 300 | } |
| 301 | |
| 302 | midx->base_midx = midx_chain; |
| 303 | midx->has_chain = 1; |
| 304 | |
| 305 | return 1; |
| 306 | } |
| 307 | |
| 308 | static struct multi_pack_index *load_midx_chain_fd_st(struct odb_source_packed *source, |
| 309 | int fd, struct stat *st, |
| 310 | int *incomplete_chain) |
| 311 | { |
| 312 | const struct git_hash_algo *hash_algo = source->base.odb->repo->hash_algo; |
| 313 | struct multi_pack_index *midx_chain = NULL; |
| 314 | struct strbuf buf = STRBUF_INIT; |
| 315 | int valid = 1; |
| 316 | uint32_t i, count; |
| 317 | FILE *fp = xfdopen(fd, "r"); |
| 318 | |
| 319 | count = st->st_size / (hash_algo->hexsz + 1); |
| 320 | |
| 321 | for (i = 0; i < count; i++) { |
| 322 | struct multi_pack_index *m; |
| 323 | struct object_id layer; |
| 324 | |
| 325 | if (strbuf_getline_lf(&buf, fp) == EOF) |
| 326 | break; |
| 327 | |
| 328 | if (get_oid_hex_algop(buf.buf, &layer, hash_algo)) { |
| 329 | warning(_("invalid multi-pack-index chain: line '%s' " |
| 330 | "not a hash"), |
| 331 | buf.buf); |
| 332 | valid = 0; |
| 333 | break; |
| 334 | } |
| 335 | |
| 336 | valid = 0; |
| 337 | |
| 338 | strbuf_reset(&buf); |
| 339 | get_split_midx_filename_ext(source, &buf, |
| 340 | layer.hash, MIDX_EXT_MIDX); |
| 341 | m = load_multi_pack_index_one(source, buf.buf); |
| 342 | |
| 343 | if (m) { |
| 344 | if (add_midx_to_chain(m, midx_chain)) { |
| 345 | midx_chain = m; |
| 346 | valid = 1; |
| 347 | } else { |
| 348 | close_midx(m); |
| 349 | } |
| 350 | } |
| 351 | if (!valid) { |
| 352 | warning(_("unable to find all multi-pack index files")); |
| 353 | break; |
| 354 | } |
| 355 | } |
| 356 | |
| 357 | fclose(fp); |
| 358 | strbuf_release(&buf); |
| 359 | |
| 360 | *incomplete_chain = !valid; |
| 361 | return midx_chain; |
| 362 | } |
| 363 | |
| 364 | static struct multi_pack_index *load_multi_pack_index_chain(struct odb_source_packed *source) |
| 365 | { |
| 366 | struct strbuf chain_file = STRBUF_INIT; |
| 367 | struct stat st; |
| 368 | int fd; |
| 369 | struct multi_pack_index *m = NULL; |
| 370 | |
| 371 | get_midx_chain_filename(source, &chain_file); |
| 372 | if (open_multi_pack_index_chain(source->base.odb->repo->hash_algo, |
| 373 | chain_file.buf, &fd, &st)) { |
| 374 | int incomplete; |
| 375 | /* ownership of fd is taken over by load function */ |
| 376 | m = load_midx_chain_fd_st(source, fd, &st, &incomplete); |
| 377 | } |
| 378 | |
| 379 | strbuf_release(&chain_file); |
| 380 | return m; |
| 381 | } |
| 382 | |
| 383 | struct multi_pack_index *load_multi_pack_index(struct odb_source_packed *source) |
| 384 | { |
| 385 | struct strbuf midx_name = STRBUF_INIT; |
| 386 | struct multi_pack_index *m; |
| 387 | |
| 388 | get_midx_filename(source, &midx_name); |
| 389 | |
| 390 | m = load_multi_pack_index_one(source, midx_name.buf); |
| 391 | if (!m) |
| 392 | m = load_multi_pack_index_chain(source); |
| 393 | |
| 394 | strbuf_release(&midx_name); |
| 395 | |
| 396 | return m; |
| 397 | } |
| 398 | |
| 399 | void close_midx(struct multi_pack_index *m) |
| 400 | { |
| 401 | uint32_t i; |
| 402 | |
| 403 | if (!m) |
| 404 | return; |
| 405 | |
| 406 | close_midx(m->base_midx); |
| 407 | |
| 408 | munmap((unsigned char *)m->data, m->data_len); |
| 409 | |
| 410 | for (i = 0; i < m->num_packs; i++) { |
| 411 | if (m->packs[i] && m->packs[i] != MIDX_PACK_ERROR) |
| 412 | m->packs[i]->multi_pack_index = 0; |
| 413 | } |
| 414 | FREE_AND_NULL(m->packs); |
| 415 | FREE_AND_NULL(m->pack_names); |
| 416 | FREE_AND_NULL(m->pack_names_sorted); |
| 417 | free(m); |
| 418 | } |
| 419 | |
| 420 | static uint32_t midx_for_object(struct multi_pack_index **_m, uint32_t pos) |
| 421 | { |
| 422 | struct multi_pack_index *m = *_m; |
| 423 | while (m && pos < m->num_objects_in_base) |
| 424 | m = m->base_midx; |
| 425 | |
| 426 | if (!m) |
| 427 | BUG("NULL multi-pack-index for object position: %"PRIu32, pos); |
| 428 | |
| 429 | if (pos >= m->num_objects + m->num_objects_in_base) |
| 430 | die(_("invalid MIDX object position, MIDX is likely corrupt")); |
| 431 | |
| 432 | *_m = m; |
| 433 | |
| 434 | return pos - m->num_objects_in_base; |
| 435 | } |
| 436 | |
| 437 | static uint32_t midx_for_pack(struct multi_pack_index **_m, |
| 438 | uint32_t pack_int_id) |
| 439 | { |
| 440 | struct multi_pack_index *m = *_m; |
| 441 | while (m && pack_int_id < m->num_packs_in_base) |
| 442 | m = m->base_midx; |
| 443 | |
| 444 | if (!m) |
| 445 | BUG("NULL multi-pack-index for pack ID: %"PRIu32, pack_int_id); |
| 446 | |
| 447 | if (pack_int_id >= m->num_packs + m->num_packs_in_base) |
| 448 | die(_("bad pack-int-id: %u (%u total packs)"), |
| 449 | pack_int_id, m->num_packs + m->num_packs_in_base); |
| 450 | |
| 451 | *_m = m; |
| 452 | |
| 453 | return pack_int_id - m->num_packs_in_base; |
| 454 | } |
| 455 | |
| 456 | int prepare_midx_pack(struct multi_pack_index *m, |
| 457 | uint32_t pack_int_id) |
| 458 | { |
| 459 | struct odb_source_packed *packed = m->source; |
| 460 | struct strbuf pack_name = STRBUF_INIT; |
| 461 | struct packed_git *p; |
| 462 | |
| 463 | pack_int_id = midx_for_pack(&m, pack_int_id); |
| 464 | |
| 465 | if (m->packs[pack_int_id] == MIDX_PACK_ERROR) |
| 466 | return 1; |
| 467 | if (m->packs[pack_int_id]) |
| 468 | return 0; |
| 469 | |
| 470 | strbuf_addf(&pack_name, "%s/pack/%s", packed->base.path, |
| 471 | m->pack_names[pack_int_id]); |
| 472 | p = packfile_store_load_pack(packed, |
| 473 | pack_name.buf, packed->base.local); |
| 474 | strbuf_release(&pack_name); |
| 475 | |
| 476 | if (!p) { |
| 477 | m->packs[pack_int_id] = MIDX_PACK_ERROR; |
| 478 | return 1; |
| 479 | } |
| 480 | |
| 481 | p->multi_pack_index = 1; |
| 482 | m->packs[pack_int_id] = p; |
| 483 | |
| 484 | return 0; |
| 485 | } |
| 486 | |
| 487 | struct packed_git *nth_midxed_pack(struct multi_pack_index *m, |
| 488 | uint32_t pack_int_id) |
| 489 | { |
| 490 | uint32_t local_pack_int_id = midx_for_pack(&m, pack_int_id); |
| 491 | if (m->packs[local_pack_int_id] == MIDX_PACK_ERROR) |
| 492 | return NULL; |
| 493 | return m->packs[local_pack_int_id]; |
| 494 | } |
| 495 | |
| 496 | #define MIDX_CHUNK_BITMAPPED_PACKS_WIDTH (2 * sizeof(uint32_t)) |
| 497 | |
| 498 | int nth_bitmapped_pack(struct multi_pack_index *m, |
| 499 | struct bitmapped_pack *bp, uint32_t pack_int_id) |
| 500 | { |
| 501 | uint32_t local_pack_int_id = midx_for_pack(&m, pack_int_id); |
| 502 | |
| 503 | if (!m->chunk_bitmapped_packs) |
| 504 | return error(_("MIDX does not contain the BTMP chunk")); |
| 505 | |
| 506 | if (prepare_midx_pack(m, pack_int_id)) |
| 507 | return error(_("could not load bitmapped pack %"PRIu32), pack_int_id); |
| 508 | |
| 509 | bp->p = m->packs[local_pack_int_id]; |
| 510 | bp->bitmap_pos = get_be32((char *)m->chunk_bitmapped_packs + |
| 511 | MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * local_pack_int_id); |
| 512 | bp->bitmap_nr = get_be32((char *)m->chunk_bitmapped_packs + |
| 513 | MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * local_pack_int_id + |
| 514 | sizeof(uint32_t)); |
| 515 | bp->pack_int_id = pack_int_id; |
| 516 | bp->from_midx = m; |
| 517 | |
| 518 | return 0; |
| 519 | } |
| 520 | |
| 521 | int bsearch_one_midx(const struct object_id *oid, struct multi_pack_index *m, |
| 522 | uint32_t *result) |
| 523 | { |
| 524 | int ret = bsearch_hash(oid->hash, m->chunk_oid_fanout, |
| 525 | m->chunk_oid_lookup, |
| 526 | m->source->base.odb->repo->hash_algo->rawsz, |
| 527 | result); |
| 528 | if (result) |
| 529 | *result += m->num_objects_in_base; |
| 530 | return ret; |
| 531 | } |
| 532 | |
| 533 | int bsearch_midx(const struct object_id *oid, struct multi_pack_index *m, |
| 534 | uint32_t *result) |
| 535 | { |
| 536 | for (; m; m = m->base_midx) |
| 537 | if (bsearch_one_midx(oid, m, result)) |
| 538 | return 1; |
| 539 | return 0; |
| 540 | } |
| 541 | |
| 542 | int midx_has_oid(struct multi_pack_index *m, const struct object_id *oid) |
| 543 | { |
| 544 | return bsearch_midx(oid, m, NULL); |
| 545 | } |
| 546 | |
| 547 | struct object_id *nth_midxed_object_oid(struct object_id *oid, |
| 548 | struct multi_pack_index *m, |
| 549 | uint32_t n) |
| 550 | { |
| 551 | if (n >= m->num_objects + m->num_objects_in_base) |
| 552 | return NULL; |
| 553 | |
| 554 | n = midx_for_object(&m, n); |
| 555 | |
| 556 | oidread(oid, m->chunk_oid_lookup + st_mult(m->hash_len, n), |
| 557 | m->source->base.odb->repo->hash_algo); |
| 558 | return oid; |
| 559 | } |
| 560 | |
| 561 | off_t nth_midxed_offset(struct multi_pack_index *m, uint32_t pos) |
| 562 | { |
| 563 | const unsigned char *offset_data; |
| 564 | uint32_t offset32; |
| 565 | |
| 566 | pos = midx_for_object(&m, pos); |
| 567 | |
| 568 | offset_data = m->chunk_object_offsets + (off_t)pos * MIDX_CHUNK_OFFSET_WIDTH; |
| 569 | offset32 = get_be32(offset_data + sizeof(uint32_t)); |
| 570 | |
| 571 | if (m->chunk_large_offsets && offset32 & MIDX_LARGE_OFFSET_NEEDED) { |
| 572 | if (sizeof(off_t) < sizeof(uint64_t)) |
| 573 | die(_("multi-pack-index stores a 64-bit offset, but off_t is too small")); |
| 574 | |
| 575 | offset32 ^= MIDX_LARGE_OFFSET_NEEDED; |
| 576 | if (offset32 >= m->chunk_large_offsets_len / sizeof(uint64_t)) |
| 577 | die(_("multi-pack-index large offset out of bounds")); |
| 578 | return get_be64(m->chunk_large_offsets + sizeof(uint64_t) * offset32); |
| 579 | } |
| 580 | |
| 581 | return offset32; |
| 582 | } |
| 583 | |
| 584 | uint32_t nth_midxed_pack_int_id(struct multi_pack_index *m, uint32_t pos) |
| 585 | { |
| 586 | pos = midx_for_object(&m, pos); |
| 587 | |
| 588 | return m->num_packs_in_base + get_be32(m->chunk_object_offsets + |
| 589 | (off_t)pos * MIDX_CHUNK_OFFSET_WIDTH); |
| 590 | } |
| 591 | |
| 592 | int fill_midx_entry(struct multi_pack_index *m, |
| 593 | const struct object_id *oid, |
| 594 | struct pack_entry *e) |
| 595 | { |
| 596 | uint32_t pos; |
| 597 | uint32_t pack_int_id; |
| 598 | struct packed_git *p; |
| 599 | |
| 600 | if (!bsearch_midx(oid, m, &pos)) |
| 601 | return 0; |
| 602 | |
| 603 | midx_for_object(&m, pos); |
| 604 | pack_int_id = nth_midxed_pack_int_id(m, pos); |
| 605 | |
| 606 | if (prepare_midx_pack(m, pack_int_id)) |
| 607 | return 0; |
| 608 | p = m->packs[pack_int_id - m->num_packs_in_base]; |
| 609 | |
| 610 | /* |
| 611 | * We are about to tell the caller where they can locate the |
| 612 | * requested object. We better make sure the packfile is |
| 613 | * still here and can be accessed before supplying that |
| 614 | * answer, as it may have been deleted since the MIDX was |
| 615 | * loaded! |
| 616 | */ |
| 617 | if (!is_pack_valid(p)) |
| 618 | return 0; |
| 619 | |
| 620 | if (oidset_size(&p->bad_objects) && |
| 621 | oidset_contains(&p->bad_objects, oid)) |
| 622 | return 0; |
| 623 | |
| 624 | e->offset = nth_midxed_offset(m, pos); |
| 625 | e->p = p; |
| 626 | |
| 627 | return 1; |
| 628 | } |
| 629 | |
| 630 | /* Match "foo.idx" against either "foo.pack" _or_ "foo.idx". */ |
| 631 | int cmp_idx_or_pack_name(const char *idx_or_pack_name, |
| 632 | const char *idx_name) |
| 633 | { |
| 634 | /* Skip past any initial matching prefix. */ |
| 635 | while (*idx_name && *idx_name == *idx_or_pack_name) { |
| 636 | idx_name++; |
| 637 | idx_or_pack_name++; |
| 638 | } |
| 639 | |
| 640 | /* |
| 641 | * If we didn't match completely, we may have matched "pack-1234." and |
| 642 | * be left with "idx" and "pack" respectively, which is also OK. We do |
| 643 | * not have to check for "idx" and "idx", because that would have been |
| 644 | * a complete match (and in that case these strcmps will be false, but |
| 645 | * we'll correctly return 0 from the final strcmp() below. |
| 646 | * |
| 647 | * Technically this matches "fooidx" and "foopack", but we'd never have |
| 648 | * such names in the first place. |
| 649 | */ |
| 650 | if (!strcmp(idx_name, "idx") && !strcmp(idx_or_pack_name, "pack")) |
| 651 | return 0; |
| 652 | |
| 653 | /* |
| 654 | * This not only checks for a complete match, but also orders based on |
| 655 | * the first non-identical character, which means our ordering will |
| 656 | * match a raw strcmp(). That makes it OK to use this to binary search |
| 657 | * a naively-sorted list. |
| 658 | */ |
| 659 | return strcmp(idx_or_pack_name, idx_name); |
| 660 | } |
| 661 | |
| 662 | |
| 663 | static int midx_pack_names_cmp(const void *a, const void *b, void *m_) |
| 664 | { |
| 665 | struct multi_pack_index *m = m_; |
| 666 | return strcmp(m->pack_names[*(const size_t *)a], |
| 667 | m->pack_names[*(const size_t *)b]); |
| 668 | } |
| 669 | |
| 670 | int midx_layer_contains_pack(struct multi_pack_index *m, |
| 671 | const char *idx_or_pack_name) |
| 672 | { |
| 673 | uint32_t first = 0, last = m->num_packs; |
| 674 | |
| 675 | if (m->version == MIDX_VERSION_V2 && !m->pack_names_sorted) { |
| 676 | uint32_t i; |
| 677 | |
| 678 | ALLOC_ARRAY(m->pack_names_sorted, m->num_packs); |
| 679 | |
| 680 | for (i = 0; i < m->num_packs; i++) |
| 681 | m->pack_names_sorted[i] = i; |
| 682 | |
| 683 | QSORT_S(m->pack_names_sorted, m->num_packs, midx_pack_names_cmp, |
| 684 | m); |
| 685 | } |
| 686 | |
| 687 | while (first < last) { |
| 688 | uint32_t mid = first + (last - first) / 2; |
| 689 | const char *current; |
| 690 | int cmp; |
| 691 | |
| 692 | if (m->pack_names_sorted) |
| 693 | current = m->pack_names[m->pack_names_sorted[mid]]; |
| 694 | else |
| 695 | current = m->pack_names[mid]; |
| 696 | cmp = cmp_idx_or_pack_name(idx_or_pack_name, current); |
| 697 | if (!cmp) |
| 698 | return 1; |
| 699 | if (cmp > 0) { |
| 700 | first = mid + 1; |
| 701 | continue; |
| 702 | } |
| 703 | last = mid; |
| 704 | } |
| 705 | |
| 706 | return 0; |
| 707 | } |
| 708 | |
| 709 | int midx_contains_pack(struct multi_pack_index *m, const char *idx_or_pack_name) |
| 710 | { |
| 711 | for (; m; m = m->base_midx) |
| 712 | if (midx_layer_contains_pack(m, idx_or_pack_name)) |
| 713 | return 1; |
| 714 | return 0; |
| 715 | } |
| 716 | |
| 717 | int midx_preferred_pack(struct multi_pack_index *m, uint32_t *pack_int_id) |
| 718 | { |
| 719 | if (m->preferred_pack_idx == -1) { |
| 720 | uint32_t midx_pos; |
| 721 | if (load_midx_revindex(m)) { |
| 722 | m->preferred_pack_idx = -2; |
| 723 | return -1; |
| 724 | } |
| 725 | |
| 726 | midx_pos = pack_pos_to_midx(m, m->num_objects_in_base); |
| 727 | |
| 728 | m->preferred_pack_idx = nth_midxed_pack_int_id(m, midx_pos); |
| 729 | |
| 730 | } else if (m->preferred_pack_idx == -2) |
| 731 | return -1; /* no revindex */ |
| 732 | |
| 733 | *pack_int_id = m->preferred_pack_idx; |
| 734 | return 0; |
| 735 | } |
| 736 | |
| 737 | int prepare_multi_pack_index_one(struct odb_source_packed *source) |
| 738 | { |
| 739 | struct repository *r = source->base.odb->repo; |
| 740 | |
| 741 | prepare_repo_settings(r); |
| 742 | if (!r->settings.core_multi_pack_index) |
| 743 | return 0; |
| 744 | |
| 745 | if (source->midx) |
| 746 | return 1; |
| 747 | |
| 748 | source->midx = load_multi_pack_index(source); |
| 749 | |
| 750 | return !!source->midx; |
| 751 | } |
| 752 | |
| 753 | int midx_checksum_valid(struct multi_pack_index *m) |
| 754 | { |
| 755 | return hashfile_checksum_valid(m->source->base.odb->repo->hash_algo, |
| 756 | m->data, m->data_len); |
| 757 | } |
| 758 | |
| 759 | struct clear_midx_data { |
| 760 | struct strset keep; |
| 761 | const char *ext; |
| 762 | }; |
| 763 | |
| 764 | static void clear_midx_file_ext(const char *full_path, size_t full_path_len UNUSED, |
| 765 | const char *file_name, void *_data) |
| 766 | { |
| 767 | struct clear_midx_data *data = _data; |
| 768 | |
| 769 | if (!(starts_with(file_name, "multi-pack-index-") && |
| 770 | ends_with(file_name, data->ext))) |
| 771 | return; |
| 772 | if (strset_contains(&data->keep, file_name)) |
| 773 | return; |
| 774 | if (unlink(full_path)) |
| 775 | die_errno(_("failed to remove %s"), full_path); |
| 776 | } |
| 777 | |
| 778 | void clear_midx_files_ext(struct odb_source_packed *source, const char *ext, |
| 779 | const char *keep_hash) |
| 780 | { |
| 781 | struct clear_midx_data data = { |
| 782 | .keep = STRSET_INIT, |
| 783 | .ext = ext, |
| 784 | }; |
| 785 | |
| 786 | if (keep_hash) { |
| 787 | struct strbuf buf = STRBUF_INIT; |
| 788 | strbuf_addf(&buf, "multi-pack-index-%s.%s", keep_hash, ext); |
| 789 | |
| 790 | strset_add(&data.keep, buf.buf); |
| 791 | |
| 792 | strbuf_release(&buf); |
| 793 | } |
| 794 | |
| 795 | for_each_file_in_pack_dir(source->base.path, clear_midx_file_ext, &data); |
| 796 | |
| 797 | strset_clear(&data.keep); |
| 798 | } |
| 799 | |
| 800 | void clear_incremental_midx_files_ext(struct odb_source_packed *source, const char *ext, |
| 801 | const struct strvec *keep_hashes) |
| 802 | { |
| 803 | struct clear_midx_data data = { |
| 804 | .keep = STRSET_INIT, |
| 805 | .ext = ext, |
| 806 | }; |
| 807 | struct strbuf buf = STRBUF_INIT; |
| 808 | |
| 809 | if (keep_hashes) { |
| 810 | for (size_t i = 0; i < keep_hashes->nr; i++) { |
| 811 | strbuf_reset(&buf); |
| 812 | strbuf_addf(&buf, "multi-pack-index-%s.%s", |
| 813 | keep_hashes->v[i], ext); |
| 814 | |
| 815 | strset_add(&data.keep, buf.buf); |
| 816 | } |
| 817 | } |
| 818 | |
| 819 | for_each_file_in_pack_subdir(source->base.path, "multi-pack-index.d", |
| 820 | clear_midx_file_ext, &data); |
| 821 | |
| 822 | strbuf_release(&buf); |
| 823 | strset_clear(&data.keep); |
| 824 | } |
| 825 | |
| 826 | void clear_midx_file(struct repository *r) |
| 827 | { |
| 828 | struct odb_source_files *files; |
| 829 | struct strbuf midx = STRBUF_INIT; |
| 830 | |
| 831 | if (r->objects) { |
| 832 | struct odb_source *source; |
| 833 | |
| 834 | for (source = r->objects->sources; source; source = source->next) { |
| 835 | files = odb_source_files_downcast(source); |
| 836 | if (files->packed->midx) |
| 837 | close_midx(files->packed->midx); |
| 838 | files->packed->midx = NULL; |
| 839 | } |
| 840 | } |
| 841 | |
| 842 | files = odb_source_files_downcast(r->objects->sources); |
| 843 | get_midx_filename(files->packed, &midx); |
| 844 | |
| 845 | if (remove_path(midx.buf)) |
| 846 | die(_("failed to clear multi-pack-index at %s"), midx.buf); |
| 847 | |
| 848 | clear_midx_files_ext(files->packed, MIDX_EXT_BITMAP, NULL); |
| 849 | clear_midx_files_ext(files->packed, MIDX_EXT_REV, NULL); |
| 850 | |
| 851 | strbuf_release(&midx); |
| 852 | } |
| 853 | |
| 854 | void clear_incremental_midx_files(struct repository *r, |
| 855 | const struct strvec *keep_hashes) |
| 856 | { |
| 857 | struct odb_source_files *files; |
| 858 | struct odb_source *source; |
| 859 | struct strbuf chain = STRBUF_INIT; |
| 860 | |
| 861 | for (source = r->objects->sources; source; source = source->next) { |
| 862 | files = odb_source_files_downcast(source); |
| 863 | if (files->packed->midx) |
| 864 | close_midx(files->packed->midx); |
| 865 | files->packed->midx = NULL; |
| 866 | } |
| 867 | |
| 868 | files = odb_source_files_downcast(r->objects->sources); |
| 869 | get_midx_chain_filename(files->packed, &chain); |
| 870 | |
| 871 | if (!keep_hashes && remove_path(chain.buf)) |
| 872 | die(_("failed to clear multi-pack-index chain at %s"), |
| 873 | chain.buf); |
| 874 | |
| 875 | clear_incremental_midx_files_ext(files->packed, MIDX_EXT_BITMAP, keep_hashes); |
| 876 | clear_incremental_midx_files_ext(files->packed, MIDX_EXT_REV, keep_hashes); |
| 877 | clear_incremental_midx_files_ext(files->packed, MIDX_EXT_MIDX, keep_hashes); |
| 878 | |
| 879 | strbuf_release(&chain); |
| 880 | } |
| 881 | |
| 882 | static int verify_midx_error; |
| 883 | |
| 884 | __attribute__((format (printf, 1, 2))) |
| 885 | static void midx_report(const char *fmt, ...) |
| 886 | { |
| 887 | va_list ap; |
| 888 | verify_midx_error = 1; |
| 889 | va_start(ap, fmt); |
| 890 | vfprintf(stderr, fmt, ap); |
| 891 | fprintf(stderr, "\n"); |
| 892 | va_end(ap); |
| 893 | } |
| 894 | |
| 895 | struct pair_pos_vs_id |
| 896 | { |
| 897 | uint32_t pos; |
| 898 | uint32_t pack_int_id; |
| 899 | }; |
| 900 | |
| 901 | static int compare_pair_pos_vs_id(const void *_a, const void *_b) |
| 902 | { |
| 903 | struct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a; |
| 904 | struct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b; |
| 905 | |
| 906 | return b->pack_int_id - a->pack_int_id; |
| 907 | } |
| 908 | |
| 909 | /* |
| 910 | * Limit calls to display_progress() for performance reasons. |
| 911 | * The interval here was arbitrarily chosen. |
| 912 | */ |
| 913 | #define SPARSE_PROGRESS_INTERVAL (1 << 12) |
| 914 | #define midx_display_sparse_progress(progress, n) \ |
| 915 | do { \ |
| 916 | uint64_t _n = (n); \ |
| 917 | if ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0) \ |
| 918 | display_progress(progress, _n); \ |
| 919 | } while (0) |
| 920 | |
| 921 | int verify_midx_file(struct odb_source_packed *source, unsigned flags) |
| 922 | { |
| 923 | struct repository *r = source->base.odb->repo; |
| 924 | struct pair_pos_vs_id *pairs = NULL; |
| 925 | uint32_t i; |
| 926 | struct progress *progress = NULL; |
| 927 | struct multi_pack_index *m = load_multi_pack_index(source); |
| 928 | struct multi_pack_index *curr; |
| 929 | verify_midx_error = 0; |
| 930 | |
| 931 | if (!m) { |
| 932 | int result = 0; |
| 933 | struct stat sb; |
| 934 | struct strbuf filename = STRBUF_INIT; |
| 935 | |
| 936 | get_midx_filename(source, &filename); |
| 937 | |
| 938 | if (!stat(filename.buf, &sb)) { |
| 939 | error(_("multi-pack-index file exists, but failed to parse")); |
| 940 | result = 1; |
| 941 | } |
| 942 | strbuf_release(&filename); |
| 943 | return result; |
| 944 | } |
| 945 | |
| 946 | if (!midx_checksum_valid(m)) |
| 947 | midx_report(_("incorrect checksum")); |
| 948 | |
| 949 | if (flags & MIDX_PROGRESS) |
| 950 | progress = start_delayed_progress(r, |
| 951 | _("Looking for referenced packfiles"), |
| 952 | m->num_packs + m->num_packs_in_base); |
| 953 | for (i = 0; i < m->num_packs + m->num_packs_in_base; i++) { |
| 954 | if (prepare_midx_pack(m, i)) |
| 955 | midx_report("failed to load pack in position %d", i); |
| 956 | |
| 957 | display_progress(progress, i + 1); |
| 958 | } |
| 959 | stop_progress(&progress); |
| 960 | |
| 961 | if (m->num_objects == 0) { |
| 962 | midx_report(_("the midx contains no oid")); |
| 963 | /* |
| 964 | * Remaining tests assume that we have objects, so we can |
| 965 | * return here. |
| 966 | */ |
| 967 | goto cleanup; |
| 968 | } |
| 969 | |
| 970 | if (flags & MIDX_PROGRESS) |
| 971 | progress = start_sparse_progress(r, |
| 972 | _("Verifying OID order in multi-pack-index"), |
| 973 | m->num_objects - 1); |
| 974 | |
| 975 | for (curr = m; curr; curr = curr->base_midx) { |
| 976 | for (i = 0; i < m->num_objects - 1; i++) { |
| 977 | struct object_id oid1, oid2; |
| 978 | |
| 979 | nth_midxed_object_oid(&oid1, m, m->num_objects_in_base + i); |
| 980 | nth_midxed_object_oid(&oid2, m, m->num_objects_in_base + i + 1); |
| 981 | |
| 982 | if (oidcmp(&oid1, &oid2) >= 0) |
| 983 | midx_report(_("oid lookup out of order: oid[%d] = %s >= %s = oid[%d]"), |
| 984 | i, oid_to_hex(&oid1), oid_to_hex(&oid2), i + 1); |
| 985 | |
| 986 | midx_display_sparse_progress(progress, i + 1); |
| 987 | } |
| 988 | } |
| 989 | stop_progress(&progress); |
| 990 | |
| 991 | /* |
| 992 | * Create an array mapping each object to its packfile id. Sort it |
| 993 | * to group the objects by packfile. Use this permutation to visit |
| 994 | * each of the objects and only require 1 packfile to be open at a |
| 995 | * time. |
| 996 | */ |
| 997 | ALLOC_ARRAY(pairs, m->num_objects + m->num_objects_in_base); |
| 998 | for (i = 0; i < m->num_objects + m->num_objects_in_base; i++) { |
| 999 | pairs[i].pos = i; |
| 1000 | pairs[i].pack_int_id = nth_midxed_pack_int_id(m, i); |
| 1001 | } |
| 1002 | |
| 1003 | if (flags & MIDX_PROGRESS) |
| 1004 | progress = start_sparse_progress(r, |
| 1005 | _("Sorting objects by packfile"), |
| 1006 | m->num_objects); |
| 1007 | display_progress(progress, 0); /* TODO: Measure QSORT() progress */ |
| 1008 | QSORT(pairs, m->num_objects, compare_pair_pos_vs_id); |
| 1009 | stop_progress(&progress); |
| 1010 | |
| 1011 | if (flags & MIDX_PROGRESS) |
| 1012 | progress = start_sparse_progress(r, |
| 1013 | _("Verifying object offsets"), |
| 1014 | m->num_objects); |
| 1015 | for (i = 0; i < m->num_objects + m->num_objects_in_base; i++) { |
| 1016 | struct object_id oid; |
| 1017 | struct pack_entry e; |
| 1018 | off_t m_offset, p_offset; |
| 1019 | |
| 1020 | if (i > 0 && pairs[i-1].pack_int_id != pairs[i].pack_int_id && |
| 1021 | nth_midxed_pack(m, pairs[i-1].pack_int_id)) { |
| 1022 | uint32_t pack_int_id = pairs[i-1].pack_int_id; |
| 1023 | struct packed_git *p = nth_midxed_pack(m, pack_int_id); |
| 1024 | |
| 1025 | close_pack_fd(p); |
| 1026 | close_pack_index(p); |
| 1027 | } |
| 1028 | |
| 1029 | nth_midxed_object_oid(&oid, m, pairs[i].pos); |
| 1030 | |
| 1031 | if (!fill_midx_entry(m, &oid, &e)) { |
| 1032 | midx_report(_("failed to load pack entry for oid[%d] = %s"), |
| 1033 | pairs[i].pos, oid_to_hex(&oid)); |
| 1034 | continue; |
| 1035 | } |
| 1036 | |
| 1037 | if (open_pack_index(e.p)) { |
| 1038 | midx_report(_("failed to load pack-index for packfile %s"), |
| 1039 | e.p->pack_name); |
| 1040 | break; |
| 1041 | } |
| 1042 | |
| 1043 | m_offset = e.offset; |
| 1044 | p_offset = find_pack_entry_one(&oid, e.p); |
| 1045 | |
| 1046 | if (m_offset != p_offset) |
| 1047 | midx_report(_("incorrect object offset for oid[%d] = %s: %"PRIx64" != %"PRIx64), |
| 1048 | pairs[i].pos, oid_to_hex(&oid), m_offset, p_offset); |
| 1049 | |
| 1050 | midx_display_sparse_progress(progress, i + 1); |
| 1051 | } |
| 1052 | stop_progress(&progress); |
| 1053 | |
| 1054 | cleanup: |
| 1055 | free(pairs); |
| 1056 | close_midx(m); |
| 1057 | |
| 1058 | return verify_midx_error; |
| 1059 | } |