shallow.c

   1 #include "cache.h"
   2 #include "commit.h"
   3 #include "tag.h"
   4 #include "pkt-line.h"
   5 #include "remote.h"
   6 #include "refs.h"
   7 #include "sha1-array.h"
   8 #include "diff.h"
   9 #include "revision.h"
  10 #include "commit-slab.h"
  11
  12 static int is_shallow = -1;
  13 static struct stat shallow_stat;
  14 static char *alternate_shallow_file;
  15
  16 void set_alternate_shallow_file(const char *path, int override)
  17 {
  18         if (is_shallow != -1)
  19                 die("BUG: is_repository_shallow must not be called before set_alternate_shallow_file");
  20         if (alternate_shallow_file && !override)
  21                 return;
  22         free(alternate_shallow_file);
  23         alternate_shallow_file = path ? xstrdup(path) : NULL;
  24 }
  25
  26 int register_shallow(const unsigned char *sha1)
  27 {
  28         struct commit_graft *graft =
  29                 xmalloc(sizeof(struct commit_graft));
  30         struct commit *commit = lookup_commit(sha1);
  31
  32         hashcpy(graft->sha1, sha1);
  33         graft->nr_parent = -1;
  34         if (commit && commit->object.parsed)
  35                 commit->parents = NULL;
  36         return register_commit_graft(graft, 0);
  37 }
  38
  39 int is_repository_shallow(void)
  40 {
  41         FILE *fp;
  42         char buf[1024];
  43         const char *path = alternate_shallow_file;
  44
  45         if (is_shallow >= 0)
  46                 return is_shallow;
  47
  48         if (!path)
  49                 path = git_path("shallow");
  50         /*
  51          * fetch-pack sets '--shallow-file ""' as an indicator that no
  52          * shallow file should be used. We could just open it and it
  53          * will likely fail. But let's do an explicit check instead.
  54          */
  55         if (!*path ||
  56             stat(path, &shallow_stat) ||
  57             (fp = fopen(path, "r")) == NULL) {
  58                 is_shallow = 0;
  59                 return is_shallow;
  60         }
  61         is_shallow = 1;
  62
  63         while (fgets(buf, sizeof(buf), fp)) {
  64                 unsigned char sha1[20];
  65                 if (get_sha1_hex(buf, sha1))
  66                         die("bad shallow line: %s", buf);
  67                 register_shallow(sha1);
  68         }
  69         fclose(fp);
  70         return is_shallow;
  71 }
  72
  73 struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
  74                 int shallow_flag, int not_shallow_flag)
  75 {
  76         int i = 0, cur_depth = 0;
  77         struct commit_list *result = NULL;
  78         struct object_array stack = OBJECT_ARRAY_INIT;
  79         struct commit *commit = NULL;
  80         struct commit_graft *graft;
  81
  82         while (commit || i < heads->nr || stack.nr) {
  83                 struct commit_list *p;
  84                 if (!commit) {
  85                         if (i < heads->nr) {
  86                                 commit = (struct commit *)
  87                                         deref_tag(heads->objects[i++].item, NULL, 0);
  88                                 if (!commit || commit->object.type != OBJ_COMMIT) {
  89                                         commit = NULL;
  90                                         continue;
  91                                 }
  92                                 if (!commit->util)
  93                                         commit->util = xmalloc(sizeof(int));
  94                                 *(int *)commit->util = 0;
  95                                 cur_depth = 0;
  96                         } else {
  97                                 commit = (struct commit *)
  98                                         stack.objects[--stack.nr].item;
  99                                 cur_depth = *(int *)commit->util;
 100                         }
 101                 }
 102                 if (parse_commit(commit))
 103                         die("invalid commit");
 104                 cur_depth++;
 105                 if ((depth != INFINITE_DEPTH && cur_depth >= depth) ||
 106                     (is_repository_shallow() && !commit->parents &&
 107                      (graft = lookup_commit_graft(commit->object.sha1)) != NULL &&
 108                      graft->nr_parent < 0)) {
 109                         commit_list_insert(commit, &result);
 110                         commit->object.flags |= shallow_flag;
 111                         commit = NULL;
 112                         continue;
 113                 }
 114                 commit->object.flags |= not_shallow_flag;
 115                 for (p = commit->parents, commit = NULL; p; p = p->next) {
 116                         if (!p->item->util) {
 117                                 int *pointer = xmalloc(sizeof(int));
 118                                 p->item->util = pointer;
 119                                 *pointer =  cur_depth;
 120                         } else {
 121                                 int *pointer = p->item->util;
 122                                 if (cur_depth >= *pointer)
 123                                         continue;
 124                                 *pointer = cur_depth;
 125                         }
 126                         if (p->next)
 127                                 add_object_array(&p->item->object,
 128                                                 NULL, &stack);
 129                         else {
 130                                 commit = p->item;
 131                                 cur_depth = *(int *)commit->util;
 132                         }
 133                 }
 134         }
 135
 136         return result;
 137 }
 138
 139 void check_shallow_file_for_update(void)
 140 {
 141         struct stat st;
 142
 143         if (!is_shallow)
 144                 return;
 145         else if (is_shallow == -1)
 146                 die("BUG: shallow must be initialized by now");
 147
 148         if (stat(git_path("shallow"), &st))
 149                 die("shallow file was removed during fetch");
 150         else if (st.st_mtime != shallow_stat.st_mtime
 151 #ifdef USE_NSEC
 152                  || ST_MTIME_NSEC(st) != ST_MTIME_NSEC(shallow_stat)
 153 #endif
 154                    )
 155                 die("shallow file was changed during fetch");
 156 }
 157
 158 struct write_shallow_data {
 159         struct strbuf *out;
 160         int use_pack_protocol;
 161         int count;
 162 };
 163
 164 static int write_one_shallow(const struct commit_graft *graft, void *cb_data)
 165 {
 166         struct write_shallow_data *data = cb_data;
 167         const char *hex = sha1_to_hex(graft->sha1);
 168         if (graft->nr_parent != -1)
 169                 return 0;
 170         data->count++;
 171         if (data->use_pack_protocol)
 172                 packet_buf_write(data->out, "shallow %s", hex);
 173         else {
 174                 strbuf_addstr(data->out, hex);
 175                 strbuf_addch(data->out, '\n');
 176         }
 177         return 0;
 178 }
 179
 180 int write_shallow_commits(struct strbuf *out, int use_pack_protocol,
 181                           const struct sha1_array *extra)
 182 {
 183         struct write_shallow_data data;
 184         int i;
 185         data.out = out;
 186         data.use_pack_protocol = use_pack_protocol;
 187         data.count = 0;
 188         for_each_commit_graft(write_one_shallow, &data);
 189         if (!extra)
 190                 return data.count;
 191         for (i = 0; i < extra->nr; i++) {
 192                 strbuf_addstr(out, sha1_to_hex(extra->sha1[i]));
 193                 strbuf_addch(out, '\n');
 194                 data.count++;
 195         }
 196         return data.count;
 197 }
 198
 199 char *setup_temporary_shallow(const struct sha1_array *extra)
 200 {
 201         struct strbuf sb = STRBUF_INIT;
 202         int fd;
 203
 204         if (write_shallow_commits(&sb, 0, extra)) {
 205                 struct strbuf path = STRBUF_INIT;
 206                 strbuf_addstr(&path, git_path("shallow_XXXXXX"));
 207                 fd = xmkstemp(path.buf);
 208                 if (write_in_full(fd, sb.buf, sb.len) != sb.len)
 209                         die_errno("failed to write to %s",
 210                                   path.buf);
 211                 close(fd);
 212                 strbuf_release(&sb);
 213                 return strbuf_detach(&path, NULL);
 214         }
 215         /*
 216          * is_repository_shallow() sees empty string as "no shallow
 217          * file".
 218          */
 219         return xstrdup("");
 220 }
 221
 222 void setup_alternate_shallow(struct lock_file *shallow_lock,
 223                              const char **alternate_shallow_file,
 224                              const struct sha1_array *extra)
 225 {
 226         struct strbuf sb = STRBUF_INIT;
 227         int fd;
 228
 229         check_shallow_file_for_update();
 230         fd = hold_lock_file_for_update(shallow_lock, git_path("shallow"),
 231                                        LOCK_DIE_ON_ERROR);
 232         if (write_shallow_commits(&sb, 0, extra)) {
 233                 if (write_in_full(fd, sb.buf, sb.len) != sb.len)
 234                         die_errno("failed to write to %s",
 235                                   shallow_lock->filename);
 236                 *alternate_shallow_file = shallow_lock->filename;
 237         } else
 238                 /*
 239                  * is_repository_shallow() sees empty string as "no
 240                  * shallow file".
 241                  */
 242                 *alternate_shallow_file = "";
 243         strbuf_release(&sb);
 244 }
 245
 246 static int advertise_shallow_grafts_cb(const struct commit_graft *graft, void *cb)
 247 {
 248         int fd = *(int *)cb;
 249         if (graft->nr_parent == -1)
 250                 packet_write(fd, "shallow %s\n", sha1_to_hex(graft->sha1));
 251         return 0;
 252 }
 253
 254 void advertise_shallow_grafts(int fd)
 255 {
 256         if (!is_repository_shallow())
 257                 return;
 258         for_each_commit_graft(advertise_shallow_grafts_cb, &fd);
 259 }
 260
 261 #define TRACE_KEY "GIT_TRACE_SHALLOW"
 262
 263 /*
 264  * Step 1, split sender shallow commits into "ours" and "theirs"
 265  * Step 2, clean "ours" based on .git/shallow
 266  */
 267 void prepare_shallow_info(struct shallow_info *info, struct sha1_array *sa)
 268 {
 269         int i;
 270         trace_printf_key(TRACE_KEY, "shallow: prepare_shallow_info\n");
 271         memset(info, 0, sizeof(*info));
 272         info->shallow = sa;
 273         if (!sa)
 274                 return;
 275         info->ours = xmalloc(sizeof(*info->ours) * sa->nr);
 276         info->theirs = xmalloc(sizeof(*info->theirs) * sa->nr);
 277         for (i = 0; i < sa->nr; i++) {
 278                 if (has_sha1_file(sa->sha1[i])) {
 279                         struct commit_graft *graft;
 280                         graft = lookup_commit_graft(sa->sha1[i]);
 281                         if (graft && graft->nr_parent < 0)
 282                                 continue;
 283                         info->ours[info->nr_ours++] = i;
 284                 } else
 285                         info->theirs[info->nr_theirs++] = i;
 286         }
 287 }
 288
 289 void clear_shallow_info(struct shallow_info *info)
 290 {
 291         free(info->ours);
 292         free(info->theirs);
 293 }
 294
 295 /* Step 4, remove non-existent ones in "theirs" after getting the pack */
 296
 297 void remove_nonexistent_theirs_shallow(struct shallow_info *info)
 298 {
 299         unsigned char (*sha1)[20] = info->shallow->sha1;
 300         int i, dst;
 301         trace_printf_key(TRACE_KEY, "shallow: remove_nonexistent_theirs_shallow\n");
 302         for (i = dst = 0; i < info->nr_theirs; i++) {
 303                 if (i != dst)
 304                         info->theirs[dst] = info->theirs[i];
 305                 if (has_sha1_file(sha1[info->theirs[i]]))
 306                         dst++;
 307         }
 308         info->nr_theirs = dst;
 309 }
 310
 311 /* Step 5, remove non-existent ones in "ours" in the pack */
 312 void remove_nonexistent_ours_in_pack(struct shallow_info *info,
 313                                      struct packed_git *p)
 314 {
 315         unsigned char (*sha1)[20] = info->shallow->sha1;
 316         int i, dst;
 317         trace_printf_key(TRACE_KEY, "shallow: remove_nonexistent_ours_in_pack\n");
 318         for (i = dst = 0; i < info->nr_ours; i++) {
 319                 if (i != dst)
 320                         info->ours[dst] = info->ours[i];
 321                 if (find_pack_entry_one(sha1[info->ours[i]], p))
 322                         dst++;
 323         }
 324         info->nr_ours = dst;
 325 }
 326
 327 define_commit_slab(ref_bitmap, uint32_t *);
 328
 329 struct paint_info {
 330         struct ref_bitmap ref_bitmap;
 331         unsigned nr_bits;
 332         char **slab;
 333         char *free, *end;
 334         unsigned slab_count;
 335 };
 336
 337 static uint32_t *paint_alloc(struct paint_info *info)
 338 {
 339         unsigned nr = (info->nr_bits + 31) / 32;
 340         unsigned size = nr * sizeof(uint32_t);
 341         void *p;
 342         if (!info->slab_count || info->free + size > info->end) {
 343                 info->slab_count++;
 344                 info->slab = xrealloc(info->slab,
 345                                       info->slab_count * sizeof(*info->slab));
 346                 info->free = xmalloc(COMMIT_SLAB_SIZE);
 347                 info->slab[info->slab_count - 1] = info->free;
 348                 info->end = info->free + COMMIT_SLAB_SIZE;
 349         }
 350         p = info->free;
 351         info->free += size;
 352         return p;
 353 }
 354
 355 /*
 356  * Given a commit SHA-1, walk down to parents until either SEEN,
 357  * UNINTERESTING or BOTTOM is hit. Set the id-th bit in ref_bitmap for
 358  * all walked commits.
 359  */
 360 static void paint_down(struct paint_info *info, const unsigned char *sha1,
 361                        int id)
 362 {
 363         unsigned int i, nr;
 364         struct commit_list *head = NULL;
 365         int bitmap_nr = (info->nr_bits + 31) / 32;
 366         int bitmap_size = bitmap_nr * sizeof(uint32_t);
 367         uint32_t *tmp = xmalloc(bitmap_size); /* to be freed before return */
 368         uint32_t *bitmap = paint_alloc(info);
 369         struct commit *c = lookup_commit_reference_gently(sha1, 1);
 370         if (!c)
 371                 return;
 372         memset(bitmap, 0, bitmap_size);
 373         bitmap[id / 32] |= (1 << (id % 32));
 374         commit_list_insert(c, &head);
 375         while (head) {
 376                 struct commit_list *p;
 377                 struct commit *c = head->item;
 378                 uint32_t **refs = ref_bitmap_at(&info->ref_bitmap, c);
 379
 380                 p = head;
 381                 head = head->next;
 382                 free(p);
 383
 384                 /* XXX check "UNINTERESTING" from pack bitmaps if available */
 385                 if (c->object.flags & (SEEN | UNINTERESTING))
 386                         continue;
 387                 else
 388                         c->object.flags |= SEEN;
 389
 390                 if (*refs == NULL)
 391                         *refs = bitmap;
 392                 else {
 393                         memcpy(tmp, *refs, bitmap_size);
 394                         for (i = 0; i < bitmap_nr; i++)
 395                                 tmp[i] |= bitmap[i];
 396                         if (memcmp(tmp, *refs, bitmap_size)) {
 397                                 *refs = paint_alloc(info);
 398                                 memcpy(*refs, tmp, bitmap_size);
 399                         }
 400                 }
 401
 402                 if (c->object.flags & BOTTOM)
 403                         continue;
 404
 405                 if (parse_commit(c))
 406                         die("unable to parse commit %s",
 407                             sha1_to_hex(c->object.sha1));
 408
 409                 for (p = c->parents; p; p = p->next) {
 410                         uint32_t **p_refs = ref_bitmap_at(&info->ref_bitmap,
 411                                                           p->item);
 412                         if (p->item->object.flags & SEEN)
 413                                 continue;
 414                         if (*p_refs == NULL || *p_refs == *refs)
 415                                 *p_refs = *refs;
 416                         commit_list_insert(p->item, &head);
 417                 }
 418         }
 419
 420         nr = get_max_object_index();
 421         for (i = 0; i < nr; i++) {
 422                 struct object *o = get_indexed_object(i);
 423                 if (o && o->type == OBJ_COMMIT)
 424                         o->flags &= ~SEEN;
 425         }
 426
 427         free(tmp);
 428 }
 429
 430 static int mark_uninteresting(const char *refname,
 431                               const unsigned char *sha1,
 432                               int flags, void *cb_data)
 433 {
 434         struct commit *commit = lookup_commit_reference_gently(sha1, 1);
 435         if (!commit)
 436                 return 0;
 437         commit->object.flags |= UNINTERESTING;
 438         mark_parents_uninteresting(commit);
 439         return 0;
 440 }
 441
 442 static void post_assign_shallow(struct shallow_info *info,
 443                                 struct ref_bitmap *ref_bitmap,
 444                                 int *ref_status);
 445 /*
 446  * Step 6(+7), associate shallow commits with new refs
 447  *
 448  * info->ref must be initialized before calling this function.
 449  *
 450  * If used is not NULL, it's an array of info->shallow->nr
 451  * bitmaps. The n-th bit set in the m-th bitmap if ref[n] needs the
 452  * m-th shallow commit from info->shallow.
 453  *
 454  * If used is NULL, "ours" and "theirs" are updated. And if ref_status
 455  * is not NULL it's an array of ref->nr ints. ref_status[i] is true if
 456  * the ref needs some shallow commits from either info->ours or
 457  * info->theirs.
 458  */
 459 void assign_shallow_commits_to_refs(struct shallow_info *info,
 460                                     uint32_t **used, int *ref_status)
 461 {
 462         unsigned char (*sha1)[20] = info->shallow->sha1;
 463         struct sha1_array *ref = info->ref;
 464         unsigned int i, nr;
 465         int *shallow, nr_shallow = 0;
 466         struct paint_info pi;
 467
 468         trace_printf_key(TRACE_KEY, "shallow: assign_shallow_commits_to_refs\n");
 469         shallow = xmalloc(sizeof(*shallow) * (info->nr_ours + info->nr_theirs));
 470         for (i = 0; i < info->nr_ours; i++)
 471                 shallow[nr_shallow++] = info->ours[i];
 472         for (i = 0; i < info->nr_theirs; i++)
 473                 shallow[nr_shallow++] = info->theirs[i];
 474
 475         /*
 476          * Prepare the commit graph to track what refs can reach what
 477          * (new) shallow commits.
 478          */
 479         nr = get_max_object_index();
 480         for (i = 0; i < nr; i++) {
 481                 struct object *o = get_indexed_object(i);
 482                 if (!o || o->type != OBJ_COMMIT)
 483                         continue;
 484
 485                 o->flags &= ~(UNINTERESTING | BOTTOM | SEEN);
 486         }
 487
 488         memset(&pi, 0, sizeof(pi));
 489         init_ref_bitmap(&pi.ref_bitmap);
 490         pi.nr_bits = ref->nr;
 491
 492         /*
 493          * "--not --all" to cut short the traversal if new refs
 494          * connect to old refs. If not (e.g. force ref updates) it'll
 495          * have to go down to the current shallow commits.
 496          */
 497         head_ref(mark_uninteresting, NULL);
 498         for_each_ref(mark_uninteresting, NULL);
 499
 500         /* Mark potential bottoms so we won't go out of bound */
 501         for (i = 0; i < nr_shallow; i++) {
 502                 struct commit *c = lookup_commit(sha1[shallow[i]]);
 503                 c->object.flags |= BOTTOM;
 504         }
 505
 506         for (i = 0; i < ref->nr; i++)
 507                 paint_down(&pi, ref->sha1[i], i);
 508
 509         if (used) {
 510                 int bitmap_size = ((pi.nr_bits + 31) / 32) * sizeof(uint32_t);
 511                 memset(used, 0, sizeof(*used) * info->shallow->nr);
 512                 for (i = 0; i < nr_shallow; i++) {
 513                         const struct commit *c = lookup_commit(sha1[shallow[i]]);
 514                         uint32_t **map = ref_bitmap_at(&pi.ref_bitmap, c);
 515                         if (*map)
 516                                 used[shallow[i]] = xmemdupz(*map, bitmap_size);
 517                 }
 518                 /*
 519                  * unreachable shallow commits are not removed from
 520                  * "ours" and "theirs". The user is supposed to run
 521                  * step 7 on every ref separately and not trust "ours"
 522                  * and "theirs" any more.
 523                  */
 524         } else
 525                 post_assign_shallow(info, &pi.ref_bitmap, ref_status);
 526
 527         clear_ref_bitmap(&pi.ref_bitmap);
 528         for (i = 0; i < pi.slab_count; i++)
 529                 free(pi.slab[i]);
 530         free(pi.slab);
 531         free(shallow);
 532 }
 533
 534 struct commit_array {
 535         struct commit **commits;
 536         int nr, alloc;
 537 };
 538
 539 static int add_ref(const char *refname,
 540                    const unsigned char *sha1, int flags, void *cb_data)
 541 {
 542         struct commit_array *ca = cb_data;
 543         ALLOC_GROW(ca->commits, ca->nr + 1, ca->alloc);
 544         ca->commits[ca->nr] = lookup_commit_reference_gently(sha1, 1);
 545         if (ca->commits[ca->nr])
 546                 ca->nr++;
 547         return 0;
 548 }
 549
 550 static void update_refstatus(int *ref_status, int nr, uint32_t *bitmap)
 551 {
 552         int i;
 553         if (!ref_status)
 554                 return;
 555         for (i = 0; i < nr; i++)
 556                 if (bitmap[i / 32] & (1 << (i % 32)))
 557                         ref_status[i]++;
 558 }
 559
 560 /*
 561  * Step 7, reachability test on "ours" at commit level
 562  */
 563 static void post_assign_shallow(struct shallow_info *info,
 564                                 struct ref_bitmap *ref_bitmap,
 565                                 int *ref_status)
 566 {
 567         unsigned char (*sha1)[20] = info->shallow->sha1;
 568         struct commit *c;
 569         uint32_t **bitmap;
 570         int dst, i, j;
 571         int bitmap_nr = (info->ref->nr + 31) / 32;
 572         struct commit_array ca;
 573
 574         trace_printf_key(TRACE_KEY, "shallow: post_assign_shallow\n");
 575         if (ref_status)
 576                 memset(ref_status, 0, sizeof(*ref_status) * info->ref->nr);
 577
 578         /* Remove unreachable shallow commits from "theirs" */
 579         for (i = dst = 0; i < info->nr_theirs; i++) {
 580                 if (i != dst)
 581                         info->theirs[dst] = info->theirs[i];
 582                 c = lookup_commit(sha1[info->theirs[i]]);
 583                 bitmap = ref_bitmap_at(ref_bitmap, c);
 584                 if (!*bitmap)
 585                         continue;
 586                 for (j = 0; j < bitmap_nr; j++)
 587                         if (bitmap[0][j]) {
 588                                 update_refstatus(ref_status, info->ref->nr, *bitmap);
 589                                 dst++;
 590                                 break;
 591                         }
 592         }
 593         info->nr_theirs = dst;
 594
 595         memset(&ca, 0, sizeof(ca));
 596         head_ref(add_ref, &ca);
 597         for_each_ref(add_ref, &ca);
 598
 599         /* Remove unreachable shallow commits from "ours" */
 600         for (i = dst = 0; i < info->nr_ours; i++) {
 601                 if (i != dst)
 602                         info->ours[dst] = info->ours[i];
 603                 c = lookup_commit(sha1[info->ours[i]]);
 604                 bitmap = ref_bitmap_at(ref_bitmap, c);
 605                 if (!*bitmap)
 606                         continue;
 607                 for (j = 0; j < bitmap_nr; j++)
 608                         if (bitmap[0][j] &&
 609                             /* Step 7, reachability test at commit level */
 610                             !in_merge_bases_many(c, ca.nr, ca.commits)) {
 611                                 update_refstatus(ref_status, info->ref->nr, *bitmap);
 612                                 dst++;
 613                                 break;
 614                         }
 615         }
 616         info->nr_ours = dst;
 617
 618         free(ca.commits);
 619 }
 620
 621 /* (Delayed) step 7, reachability test at commit level */
 622 int delayed_reachability_test(struct shallow_info *si, int c)
 623 {
 624         if (si->need_reachability_test[c]) {
 625                 struct commit *commit = lookup_commit(si->shallow->sha1[c]);
 626
 627                 if (!si->commits) {
 628                         struct commit_array ca;
 629                         memset(&ca, 0, sizeof(ca));
 630                         head_ref(add_ref, &ca);
 631                         for_each_ref(add_ref, &ca);
 632                         si->commits = ca.commits;
 633                         si->nr_commits = ca.nr;
 634                 }
 635
 636                 si->reachable[c] = in_merge_bases_many(commit,
 637                                                        si->nr_commits,
 638                                                        si->commits);
 639                 si->need_reachability_test[c] = 0;
 640         }
 641         return si->reachable[c];
 642 }