delta-islands.c

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