delta-islands.c

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