delta-islands.c

   1 #define USE_THE_REPOSITORY_VARIABLE
   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(_("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 || parse_tree(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 char *refname, const struct object_id *oid,
 394                                int flags UNUSED, void *cb)
 395 {
 396         struct island_load_data *ild = cb;
 397
 398         /*
 399          * We should advertise 'ARRAY_SIZE(matches) - 2' as the max,
 400          * so we can diagnose below a config with more capture groups
 401          * than we support.
 402          */
 403         regmatch_t matches[16];
 404         int i, m;
 405         struct strbuf island_name = STRBUF_INIT;
 406
 407         /* walk backwards to get last-one-wins ordering */
 408         for (i = ild->nr - 1; i >= 0; i--) {
 409                 if (!regexec(&ild->rx[i], refname,
 410                              ARRAY_SIZE(matches), matches, 0))
 411                         break;
 412         }
 413
 414         if (i < 0)
 415                 return 0;
 416
 417         if (matches[ARRAY_SIZE(matches) - 1].rm_so != -1)
 418                 warning(_("island regex from config has "
 419                           "too many capture groups (max=%d)"),
 420                         (int)ARRAY_SIZE(matches) - 2);
 421
 422         for (m = 1; m < ARRAY_SIZE(matches); m++) {
 423                 regmatch_t *match = &matches[m];
 424
 425                 if (match->rm_so == -1)
 426                         continue;
 427
 428                 if (island_name.len)
 429                         strbuf_addch(&island_name, '-');
 430
 431                 strbuf_add(&island_name, refname + match->rm_so, match->rm_eo - match->rm_so);
 432         }
 433
 434         add_ref_to_island(ild->remote_islands, island_name.buf, oid);
 435         strbuf_release(&island_name);
 436         return 0;
 437 }
 438
 439 static struct remote_island *get_core_island(kh_str_t *remote_islands)
 440 {
 441         if (core_island_name) {
 442                 khiter_t pos = kh_get_str(remote_islands, core_island_name);
 443                 if (pos < kh_end(remote_islands))
 444                         return kh_value(remote_islands, pos);
 445         }
 446
 447         return NULL;
 448 }
 449
 450 static void deduplicate_islands(kh_str_t *remote_islands, struct repository *r)
 451 {
 452         struct remote_island *island, *core = NULL, **list;
 453         unsigned int island_count, dst, src, ref, i = 0;
 454
 455         island_count = kh_size(remote_islands);
 456         ALLOC_ARRAY(list, island_count);
 457
 458         kh_foreach_value(remote_islands, island, {
 459                 list[i++] = island;
 460         });
 461
 462         for (ref = 0; ref + 1 < island_count; ref++) {
 463                 for (src = ref + 1, dst = src; src < island_count; src++) {
 464                         if (list[ref]->hash == list[src]->hash)
 465                                 continue;
 466
 467                         if (src != dst)
 468                                 list[dst] = list[src];
 469
 470                         dst++;
 471                 }
 472                 island_count = dst;
 473         }
 474
 475         island_bitmap_size = (island_count / 32) + 1;
 476         core = get_core_island(remote_islands);
 477
 478         for (i = 0; i < island_count; ++i) {
 479                 mark_remote_island_1(r, list[i], core && list[i]->hash == core->hash);
 480         }
 481
 482         free(list);
 483 }
 484
 485 void load_delta_islands(struct repository *r, int progress)
 486 {
 487         struct island_load_data ild = { 0 };
 488
 489         island_marks = kh_init_oid_map();
 490
 491         git_config(island_config_callback, &ild);
 492         ild.remote_islands = kh_init_str();
 493         refs_for_each_ref(get_main_ref_store(the_repository),
 494                           find_island_for_ref, &ild);
 495         free_config_regexes(&ild);
 496         deduplicate_islands(ild.remote_islands, r);
 497         free_remote_islands(ild.remote_islands);
 498
 499         if (progress)
 500                 fprintf(stderr, _("Marked %d islands, done.\n"), island_counter);
 501 }
 502
 503 void propagate_island_marks(struct commit *commit)
 504 {
 505         khiter_t pos = kh_get_oid_map(island_marks, commit->object.oid);
 506
 507         if (pos < kh_end(island_marks)) {
 508                 struct commit_list *p;
 509                 struct island_bitmap *root_marks = kh_value(island_marks, pos);
 510
 511                 repo_parse_commit(the_repository, commit);
 512                 set_island_marks(&repo_get_commit_tree(the_repository, commit)->object,
 513                                  root_marks);
 514                 for (p = commit->parents; p; p = p->next)
 515                         set_island_marks(&p->item->object, root_marks);
 516         }
 517 }
 518
 519 void free_island_marks(void)
 520 {
 521         struct island_bitmap *bitmap;
 522
 523         if (island_marks) {
 524                 kh_foreach_value(island_marks, bitmap, {
 525                         if (!--bitmap->refcount)
 526                                 free(bitmap);
 527                 });
 528                 kh_destroy_oid_map(island_marks);
 529         }
 530
 531         /* detect use-after-free with a an address which is never valid: */
 532         island_marks = (void *)-1;
 533 }
 534
 535 int compute_pack_layers(struct packing_data *to_pack)
 536 {
 537         uint32_t i;
 538
 539         if (!core_island_name || !island_marks)
 540                 return 1;
 541
 542         for (i = 0; i < to_pack->nr_objects; ++i) {
 543                 struct object_entry *entry = &to_pack->objects[i];
 544                 khiter_t pos = kh_get_oid_map(island_marks, entry->idx.oid);
 545
 546                 oe_set_layer(to_pack, entry, 1);
 547
 548                 if (pos < kh_end(island_marks)) {
 549                         struct island_bitmap *bitmap = kh_value(island_marks, pos);
 550
 551                         if (island_bitmap_get(bitmap, island_counter_core))
 552                                 oe_set_layer(to_pack, entry, 0);
 553                 }
 554         }
 555
 556         return 2;
 557 }