delta-islands.c

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