delta-islands.c

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