| 1 | #define DISABLE_SIGN_COMPARE_WARNINGS |
| 2 | |
| 3 | #include "git-compat-util.h" |
| 4 | #include "object.h" |
| 5 | #include "commit.h" |
| 6 | #include "gettext.h" |
| 7 | #include "hex.h" |
| 8 | #include "tag.h" |
| 9 | #include "tree.h" |
| 10 | #include "pack.h" |
| 11 | #include "tree-walk.h" |
| 12 | #include "diff.h" |
| 13 | #include "progress.h" |
| 14 | #include "refs.h" |
| 15 | #include "khash.h" |
| 16 | #include "pack-bitmap.h" |
| 17 | #include "pack-objects.h" |
| 18 | #include "delta-islands.h" |
| 19 | #include "oid-array.h" |
| 20 | #include "config.h" |
| 21 | |
| 22 | KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal) |
| 23 | |
| 24 | static kh_oid_map_t *island_marks; |
| 25 | static unsigned island_counter; |
| 26 | static unsigned island_counter_core; |
| 27 | |
| 28 | struct remote_island { |
| 29 | uint64_t hash; |
| 30 | struct oid_array oids; |
| 31 | }; |
| 32 | |
| 33 | struct island_bitmap { |
| 34 | uint32_t refcount; |
| 35 | uint32_t bits[FLEX_ARRAY]; |
| 36 | }; |
| 37 | |
| 38 | static uint32_t island_bitmap_size; |
| 39 | |
| 40 | /* |
| 41 | * Allocate a new bitmap; if "old" is not NULL, the new bitmap will be a copy |
| 42 | * of "old". Otherwise, the new bitmap is empty. |
| 43 | */ |
| 44 | static struct island_bitmap *island_bitmap_new(const struct island_bitmap *old) |
| 45 | { |
| 46 | size_t size = sizeof(struct island_bitmap) + (island_bitmap_size * 4); |
| 47 | struct island_bitmap *b = xcalloc(1, size); |
| 48 | |
| 49 | if (old) |
| 50 | memcpy(b, old, size); |
| 51 | |
| 52 | b->refcount = 1; |
| 53 | return b; |
| 54 | } |
| 55 | |
| 56 | static void island_bitmap_or(struct island_bitmap *a, const struct island_bitmap *b) |
| 57 | { |
| 58 | uint32_t i; |
| 59 | |
| 60 | for (i = 0; i < island_bitmap_size; ++i) |
| 61 | a->bits[i] |= b->bits[i]; |
| 62 | } |
| 63 | |
| 64 | static int island_bitmap_is_subset(struct island_bitmap *self, |
| 65 | struct island_bitmap *super) |
| 66 | { |
| 67 | uint32_t i; |
| 68 | |
| 69 | if (self == super) |
| 70 | return 1; |
| 71 | |
| 72 | for (i = 0; i < island_bitmap_size; ++i) { |
| 73 | if ((self->bits[i] & super->bits[i]) != self->bits[i]) |
| 74 | return 0; |
| 75 | } |
| 76 | |
| 77 | return 1; |
| 78 | } |
| 79 | |
| 80 | #define ISLAND_BITMAP_BLOCK(x) (x / 32) |
| 81 | #define ISLAND_BITMAP_MASK(x) (1 << (x % 32)) |
| 82 | |
| 83 | static void island_bitmap_set(struct island_bitmap *self, uint32_t i) |
| 84 | { |
| 85 | self->bits[ISLAND_BITMAP_BLOCK(i)] |= ISLAND_BITMAP_MASK(i); |
| 86 | } |
| 87 | |
| 88 | static int island_bitmap_get(struct island_bitmap *self, uint32_t i) |
| 89 | { |
| 90 | return (self->bits[ISLAND_BITMAP_BLOCK(i)] & ISLAND_BITMAP_MASK(i)) != 0; |
| 91 | } |
| 92 | |
| 93 | int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid) |
| 94 | { |
| 95 | khiter_t trg_pos, src_pos; |
| 96 | |
| 97 | /* If we aren't using islands, assume everything goes together. */ |
| 98 | if (!island_marks) |
| 99 | return 1; |
| 100 | |
| 101 | /* |
| 102 | * If we don't have a bitmap for the target, we can delta it |
| 103 | * against anything -- it's not an important object |
| 104 | */ |
| 105 | trg_pos = kh_get_oid_map(island_marks, *trg_oid); |
| 106 | if (trg_pos >= kh_end(island_marks)) |
| 107 | return 1; |
| 108 | |
| 109 | /* |
| 110 | * if the source (our delta base) doesn't have a bitmap, |
| 111 | * we don't want to base any deltas on it! |
| 112 | */ |
| 113 | src_pos = kh_get_oid_map(island_marks, *src_oid); |
| 114 | if (src_pos >= kh_end(island_marks)) |
| 115 | return 0; |
| 116 | |
| 117 | return island_bitmap_is_subset(kh_value(island_marks, trg_pos), |
| 118 | kh_value(island_marks, src_pos)); |
| 119 | } |
| 120 | |
| 121 | int island_delta_cmp(const struct object_id *a, const struct object_id *b) |
| 122 | { |
| 123 | khiter_t a_pos, b_pos; |
| 124 | struct island_bitmap *a_bitmap = NULL, *b_bitmap = NULL; |
| 125 | |
| 126 | if (!island_marks) |
| 127 | return 0; |
| 128 | |
| 129 | a_pos = kh_get_oid_map(island_marks, *a); |
| 130 | if (a_pos < kh_end(island_marks)) |
| 131 | a_bitmap = kh_value(island_marks, a_pos); |
| 132 | |
| 133 | b_pos = kh_get_oid_map(island_marks, *b); |
| 134 | if (b_pos < kh_end(island_marks)) |
| 135 | b_bitmap = kh_value(island_marks, b_pos); |
| 136 | |
| 137 | if (a_bitmap) { |
| 138 | if (!b_bitmap || !island_bitmap_is_subset(a_bitmap, b_bitmap)) |
| 139 | return -1; |
| 140 | } |
| 141 | if (b_bitmap) { |
| 142 | if (!a_bitmap || !island_bitmap_is_subset(b_bitmap, a_bitmap)) |
| 143 | return 1; |
| 144 | } |
| 145 | |
| 146 | return 0; |
| 147 | } |
| 148 | |
| 149 | static struct island_bitmap *create_or_get_island_marks(struct object *obj) |
| 150 | { |
| 151 | khiter_t pos; |
| 152 | int hash_ret; |
| 153 | |
| 154 | pos = kh_put_oid_map(island_marks, obj->oid, &hash_ret); |
| 155 | if (hash_ret) |
| 156 | kh_value(island_marks, pos) = island_bitmap_new(NULL); |
| 157 | |
| 158 | return kh_value(island_marks, pos); |
| 159 | } |
| 160 | |
| 161 | static void set_island_marks(struct object *obj, struct island_bitmap *marks) |
| 162 | { |
| 163 | struct island_bitmap *b; |
| 164 | khiter_t pos; |
| 165 | int hash_ret; |
| 166 | |
| 167 | pos = kh_put_oid_map(island_marks, obj->oid, &hash_ret); |
| 168 | if (hash_ret) { |
| 169 | /* |
| 170 | * We don't have one yet; make a copy-on-write of the |
| 171 | * parent. |
| 172 | */ |
| 173 | marks->refcount++; |
| 174 | kh_value(island_marks, pos) = marks; |
| 175 | return; |
| 176 | } |
| 177 | |
| 178 | /* |
| 179 | * We do have it. Make sure we split any copy-on-write before |
| 180 | * updating. |
| 181 | */ |
| 182 | b = kh_value(island_marks, pos); |
| 183 | if (b->refcount > 1) { |
| 184 | b->refcount--; |
| 185 | b = kh_value(island_marks, pos) = island_bitmap_new(b); |
| 186 | } |
| 187 | island_bitmap_or(b, marks); |
| 188 | } |
| 189 | |
| 190 | static void mark_remote_island_1(struct repository *r, |
| 191 | struct remote_island *rl, |
| 192 | int is_core_island) |
| 193 | { |
| 194 | uint32_t i; |
| 195 | |
| 196 | for (i = 0; i < rl->oids.nr; ++i) { |
| 197 | struct island_bitmap *marks; |
| 198 | struct object *obj = parse_object(r, &rl->oids.oid[i]); |
| 199 | |
| 200 | if (!obj) |
| 201 | continue; |
| 202 | |
| 203 | marks = create_or_get_island_marks(obj); |
| 204 | island_bitmap_set(marks, island_counter); |
| 205 | |
| 206 | if (is_core_island && obj->type == OBJ_COMMIT) |
| 207 | obj->flags |= NEEDS_BITMAP; |
| 208 | |
| 209 | /* If it was a tag, also make sure we hit the underlying object. */ |
| 210 | while (obj && obj->type == OBJ_TAG) { |
| 211 | obj = ((struct tag *)obj)->tagged; |
| 212 | if (obj) { |
| 213 | parse_object(r, &obj->oid); |
| 214 | marks = create_or_get_island_marks(obj); |
| 215 | island_bitmap_set(marks, island_counter); |
| 216 | } |
| 217 | } |
| 218 | } |
| 219 | |
| 220 | if (is_core_island) |
| 221 | island_counter_core = island_counter; |
| 222 | |
| 223 | island_counter++; |
| 224 | } |
| 225 | |
| 226 | struct tree_islands_todo { |
| 227 | struct object_entry *entry; |
| 228 | unsigned int depth; |
| 229 | }; |
| 230 | |
| 231 | static int tree_depth_compare(const void *a, const void *b) |
| 232 | { |
| 233 | const struct tree_islands_todo *todo_a = a; |
| 234 | const struct tree_islands_todo *todo_b = b; |
| 235 | |
| 236 | return todo_a->depth - todo_b->depth; |
| 237 | } |
| 238 | |
| 239 | void resolve_tree_islands(struct repository *r, |
| 240 | int progress, |
| 241 | struct packing_data *to_pack) |
| 242 | { |
| 243 | struct progress *progress_state = NULL; |
| 244 | struct tree_islands_todo *todo; |
| 245 | int nr = 0; |
| 246 | int i; |
| 247 | |
| 248 | if (!island_marks) |
| 249 | return; |
| 250 | |
| 251 | /* |
| 252 | * We process only trees, as commits and tags have already been handled |
| 253 | * (and passed their marks on to root trees, as well. We must make sure |
| 254 | * to process them in descending tree-depth order so that marks |
| 255 | * propagate down the tree properly, even if a sub-tree is found in |
| 256 | * multiple parent trees. |
| 257 | */ |
| 258 | ALLOC_ARRAY(todo, to_pack->nr_objects); |
| 259 | for (i = 0; i < to_pack->nr_objects; i++) { |
| 260 | if (oe_type(&to_pack->objects[i]) == OBJ_TREE) { |
| 261 | todo[nr].entry = &to_pack->objects[i]; |
| 262 | todo[nr].depth = oe_tree_depth(to_pack, &to_pack->objects[i]); |
| 263 | nr++; |
| 264 | } |
| 265 | } |
| 266 | QSORT(todo, nr, tree_depth_compare); |
| 267 | |
| 268 | if (progress) |
| 269 | progress_state = start_progress(r, _("Propagating island marks"), nr); |
| 270 | |
| 271 | for (i = 0; i < nr; i++) { |
| 272 | struct object_entry *ent = todo[i].entry; |
| 273 | struct island_bitmap *root_marks; |
| 274 | struct tree *tree; |
| 275 | struct tree_desc desc; |
| 276 | struct name_entry entry; |
| 277 | khiter_t pos; |
| 278 | |
| 279 | pos = kh_get_oid_map(island_marks, ent->idx.oid); |
| 280 | if (pos >= kh_end(island_marks)) |
| 281 | continue; |
| 282 | |
| 283 | root_marks = kh_value(island_marks, pos); |
| 284 | |
| 285 | tree = lookup_tree(r, &ent->idx.oid); |
| 286 | if (!tree || repo_parse_tree(r, tree) < 0) |
| 287 | die(_("bad tree object %s"), oid_to_hex(&ent->idx.oid)); |
| 288 | |
| 289 | init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size); |
| 290 | while (tree_entry(&desc, &entry)) { |
| 291 | struct object *obj; |
| 292 | |
| 293 | if (S_ISGITLINK(entry.mode)) |
| 294 | continue; |
| 295 | |
| 296 | obj = lookup_object(r, &entry.oid); |
| 297 | if (!obj) |
| 298 | continue; |
| 299 | |
| 300 | set_island_marks(obj, root_marks); |
| 301 | } |
| 302 | |
| 303 | free_tree_buffer(tree); |
| 304 | |
| 305 | display_progress(progress_state, i+1); |
| 306 | } |
| 307 | |
| 308 | stop_progress(&progress_state); |
| 309 | free(todo); |
| 310 | } |
| 311 | |
| 312 | struct island_load_data { |
| 313 | kh_str_t *remote_islands; |
| 314 | regex_t *rx; |
| 315 | size_t nr; |
| 316 | size_t alloc; |
| 317 | }; |
| 318 | static char *core_island_name; |
| 319 | |
| 320 | static void free_config_regexes(struct island_load_data *ild) |
| 321 | { |
| 322 | for (size_t i = 0; i < ild->nr; i++) |
| 323 | regfree(&ild->rx[i]); |
| 324 | free(ild->rx); |
| 325 | } |
| 326 | |
| 327 | static void free_remote_islands(kh_str_t *remote_islands) |
| 328 | { |
| 329 | const char *island_name; |
| 330 | struct remote_island *rl; |
| 331 | |
| 332 | kh_foreach(remote_islands, island_name, rl, { |
| 333 | free((void *)island_name); |
| 334 | oid_array_clear(&rl->oids); |
| 335 | free(rl); |
| 336 | }); |
| 337 | kh_destroy_str(remote_islands); |
| 338 | } |
| 339 | |
| 340 | static int island_config_callback(const char *k, const char *v, |
| 341 | const struct config_context *ctx UNUSED, |
| 342 | void *cb) |
| 343 | { |
| 344 | struct island_load_data *ild = cb; |
| 345 | |
| 346 | if (!strcmp(k, "pack.island")) { |
| 347 | struct strbuf re = STRBUF_INIT; |
| 348 | |
| 349 | if (!v) |
| 350 | return config_error_nonbool(k); |
| 351 | |
| 352 | ALLOC_GROW(ild->rx, ild->nr + 1, ild->alloc); |
| 353 | |
| 354 | if (*v != '^') |
| 355 | strbuf_addch(&re, '^'); |
| 356 | strbuf_addstr(&re, v); |
| 357 | |
| 358 | if (regcomp(&ild->rx[ild->nr], re.buf, REG_EXTENDED)) |
| 359 | die(_("failed to load island regex for '%s': %s"), k, re.buf); |
| 360 | |
| 361 | strbuf_release(&re); |
| 362 | ild->nr++; |
| 363 | return 0; |
| 364 | } |
| 365 | |
| 366 | if (!strcmp(k, "pack.islandcore")) |
| 367 | return git_config_string(&core_island_name, k, v); |
| 368 | |
| 369 | return 0; |
| 370 | } |
| 371 | |
| 372 | static void add_ref_to_island(kh_str_t *remote_islands, const char *island_name, |
| 373 | const struct object_id *oid) |
| 374 | { |
| 375 | uint64_t sha_core; |
| 376 | struct remote_island *rl = NULL; |
| 377 | |
| 378 | int hash_ret; |
| 379 | khiter_t pos = kh_put_str(remote_islands, island_name, &hash_ret); |
| 380 | |
| 381 | if (hash_ret) { |
| 382 | kh_key(remote_islands, pos) = xstrdup(island_name); |
| 383 | kh_value(remote_islands, pos) = xcalloc(1, sizeof(struct remote_island)); |
| 384 | } |
| 385 | |
| 386 | rl = kh_value(remote_islands, pos); |
| 387 | oid_array_append(&rl->oids, oid); |
| 388 | |
| 389 | memcpy(&sha_core, oid->hash, sizeof(uint64_t)); |
| 390 | rl->hash += sha_core; |
| 391 | } |
| 392 | |
| 393 | static int find_island_for_ref(const struct reference *ref, void *cb) |
| 394 | { |
| 395 | struct island_load_data *ild = cb; |
| 396 | |
| 397 | /* |
| 398 | * We should advertise 'ARRAY_SIZE(matches) - 2' as the max, |
| 399 | * so we can diagnose below a config with more capture groups |
| 400 | * than we support. |
| 401 | */ |
| 402 | regmatch_t matches[16]; |
| 403 | int i, m; |
| 404 | struct strbuf island_name = STRBUF_INIT; |
| 405 | |
| 406 | /* walk backwards to get last-one-wins ordering */ |
| 407 | for (i = ild->nr - 1; i >= 0; i--) { |
| 408 | if (!regexec(&ild->rx[i], ref->name, |
| 409 | ARRAY_SIZE(matches), matches, 0)) |
| 410 | break; |
| 411 | } |
| 412 | |
| 413 | if (i < 0) |
| 414 | return 0; |
| 415 | |
| 416 | if (matches[ARRAY_SIZE(matches) - 1].rm_so != -1) |
| 417 | warning(_("island regex from config has " |
| 418 | "too many capture groups (max=%d)"), |
| 419 | (int)ARRAY_SIZE(matches) - 2); |
| 420 | |
| 421 | for (m = 1; m < ARRAY_SIZE(matches); m++) { |
| 422 | regmatch_t *match = &matches[m]; |
| 423 | |
| 424 | if (match->rm_so == -1) |
| 425 | continue; |
| 426 | |
| 427 | if (island_name.len) |
| 428 | strbuf_addch(&island_name, '-'); |
| 429 | |
| 430 | strbuf_add(&island_name, ref->name + match->rm_so, match->rm_eo - match->rm_so); |
| 431 | } |
| 432 | |
| 433 | add_ref_to_island(ild->remote_islands, island_name.buf, ref->oid); |
| 434 | strbuf_release(&island_name); |
| 435 | return 0; |
| 436 | } |
| 437 | |
| 438 | static struct remote_island *get_core_island(kh_str_t *remote_islands) |
| 439 | { |
| 440 | if (core_island_name) { |
| 441 | khiter_t pos = kh_get_str(remote_islands, core_island_name); |
| 442 | if (pos < kh_end(remote_islands)) |
| 443 | return kh_value(remote_islands, pos); |
| 444 | } |
| 445 | |
| 446 | return NULL; |
| 447 | } |
| 448 | |
| 449 | static void deduplicate_islands(kh_str_t *remote_islands, struct repository *r) |
| 450 | { |
| 451 | struct remote_island *island, *core = NULL, **list; |
| 452 | unsigned int island_count, dst, src, ref, i = 0; |
| 453 | |
| 454 | island_count = kh_size(remote_islands); |
| 455 | ALLOC_ARRAY(list, island_count); |
| 456 | |
| 457 | kh_foreach_value(remote_islands, island, { |
| 458 | list[i++] = island; |
| 459 | }); |
| 460 | |
| 461 | for (ref = 0; ref + 1 < island_count; ref++) { |
| 462 | for (src = ref + 1, dst = src; src < island_count; src++) { |
| 463 | if (list[ref]->hash == list[src]->hash) |
| 464 | continue; |
| 465 | |
| 466 | if (src != dst) |
| 467 | list[dst] = list[src]; |
| 468 | |
| 469 | dst++; |
| 470 | } |
| 471 | island_count = dst; |
| 472 | } |
| 473 | |
| 474 | island_bitmap_size = (island_count / 32) + 1; |
| 475 | core = get_core_island(remote_islands); |
| 476 | |
| 477 | for (i = 0; i < island_count; ++i) { |
| 478 | mark_remote_island_1(r, list[i], core && list[i]->hash == core->hash); |
| 479 | } |
| 480 | |
| 481 | free(list); |
| 482 | } |
| 483 | |
| 484 | void load_delta_islands(struct repository *r, int progress) |
| 485 | { |
| 486 | struct island_load_data ild = { 0 }; |
| 487 | |
| 488 | island_marks = kh_init_oid_map(); |
| 489 | |
| 490 | repo_config(r, island_config_callback, &ild); |
| 491 | ild.remote_islands = kh_init_str(); |
| 492 | refs_for_each_ref(get_main_ref_store(r), |
| 493 | find_island_for_ref, &ild); |
| 494 | free_config_regexes(&ild); |
| 495 | deduplicate_islands(ild.remote_islands, r); |
| 496 | free_remote_islands(ild.remote_islands); |
| 497 | |
| 498 | if (progress) |
| 499 | fprintf(stderr, _("Marked %d islands, done.\n"), island_counter); |
| 500 | } |
| 501 | |
| 502 | void propagate_island_marks(struct repository *r, struct commit *commit) |
| 503 | { |
| 504 | khiter_t pos = kh_get_oid_map(island_marks, commit->object.oid); |
| 505 | |
| 506 | if (pos < kh_end(island_marks)) { |
| 507 | struct commit_list *p; |
| 508 | struct island_bitmap *root_marks = kh_value(island_marks, pos); |
| 509 | |
| 510 | repo_parse_commit(r, commit); |
| 511 | set_island_marks(&repo_get_commit_tree(r, commit)->object, |
| 512 | root_marks); |
| 513 | for (p = commit->parents; p; p = p->next) |
| 514 | set_island_marks(&p->item->object, root_marks); |
| 515 | } |
| 516 | } |
| 517 | |
| 518 | void free_island_marks(void) |
| 519 | { |
| 520 | struct island_bitmap *bitmap; |
| 521 | |
| 522 | if (island_marks) { |
| 523 | kh_foreach_value(island_marks, bitmap, { |
| 524 | if (!--bitmap->refcount) |
| 525 | free(bitmap); |
| 526 | }); |
| 527 | kh_destroy_oid_map(island_marks); |
| 528 | } |
| 529 | |
| 530 | /* detect use-after-free with an address which is never valid: */ |
| 531 | island_marks = (void *)-1; |
| 532 | } |
| 533 | |
| 534 | int compute_pack_layers(struct packing_data *to_pack) |
| 535 | { |
| 536 | uint32_t i; |
| 537 | |
| 538 | if (!core_island_name || !island_marks) |
| 539 | return 1; |
| 540 | |
| 541 | for (i = 0; i < to_pack->nr_objects; ++i) { |
| 542 | struct object_entry *entry = &to_pack->objects[i]; |
| 543 | khiter_t pos = kh_get_oid_map(island_marks, entry->idx.oid); |
| 544 | |
| 545 | oe_set_layer(to_pack, entry, 1); |
| 546 | |
| 547 | if (pos < kh_end(island_marks)) { |
| 548 | struct island_bitmap *bitmap = kh_value(island_marks, pos); |
| 549 | |
| 550 | if (island_bitmap_get(bitmap, island_counter_core)) |
| 551 | oe_set_layer(to_pack, entry, 0); |
| 552 | } |
| 553 | } |
| 554 | |
| 555 | return 2; |
| 556 | } |