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"
11static int is_shallow = -1;
13static struct stat shallow_stat;
14static char *alternate_shallow_file;
15void 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}
25int 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 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}
38int is_repository_shallow(void)
40{
41 FILE *fp;
42 char buf[1024];
43 const char *path = alternate_shallow_file;
44 if (is_shallow >= 0)
46 return is_shallow;
47 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 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}
72struct 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 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 parse_commit_or_die(commit);
103 cur_depth++;
104 if ((depth != INFINITE_DEPTH && cur_depth >= depth) ||
105 (is_repository_shallow() && !commit->parents &&
106 (graft = lookup_commit_graft(commit->object.sha1)) != NULL &&
107 graft->nr_parent < 0)) {
108 commit_list_insert(commit, &result);
109 commit->object.flags |= shallow_flag;
110 commit = NULL;
111 continue;
112 }
113 commit->object.flags |= not_shallow_flag;
114 for (p = commit->parents, commit = NULL; p; p = p->next) {
115 if (!p->item->util) {
116 int *pointer = xmalloc(sizeof(int));
117 p->item->util = pointer;
118 *pointer = cur_depth;
119 } else {
120 int *pointer = p->item->util;
121 if (cur_depth >= *pointer)
122 continue;
123 *pointer = cur_depth;
124 }
125 if (p->next)
126 add_object_array(&p->item->object,
127 NULL, &stack);
128 else {
129 commit = p->item;
130 cur_depth = *(int *)commit->util;
131 }
132 }
133 }
134 return result;
136}
137void check_shallow_file_for_update(void)
139{
140 struct stat st;
141 if (!is_shallow)
143 return;
144 else if (is_shallow == -1)
145 die("BUG: shallow must be initialized by now");
146 if (stat(git_path("shallow"), &st))
148 die("shallow file was removed during fetch");
149 else if (st.st_mtime != shallow_stat.st_mtime
150#ifdef USE_NSEC
151 || ST_MTIME_NSEC(st) != ST_MTIME_NSEC(shallow_stat)
152#endif
153 )
154 die("shallow file was changed during fetch");
155}
156#define SEEN_ONLY 1
158#define VERBOSE 2
159struct write_shallow_data {
161 struct strbuf *out;
162 int use_pack_protocol;
163 int count;
164 unsigned flags;
165};
166static int write_one_shallow(const struct commit_graft *graft, void *cb_data)
168{
169 struct write_shallow_data *data = cb_data;
170 const char *hex = sha1_to_hex(graft->sha1);
171 if (graft->nr_parent != -1)
172 return 0;
173 if (data->flags & SEEN_ONLY) {
174 struct commit *c = lookup_commit(graft->sha1);
175 if (!c || !(c->object.flags & SEEN)) {
176 if (data->flags & VERBOSE)
177 printf("Removing %s from .git/shallow\n",
178 sha1_to_hex(c->object.sha1));
179 return 0;
180 }
181 }
182 data->count++;
183 if (data->use_pack_protocol)
184 packet_buf_write(data->out, "shallow %s", hex);
185 else {
186 strbuf_addstr(data->out, hex);
187 strbuf_addch(data->out, '\n');
188 }
189 return 0;
190}
191static int write_shallow_commits_1(struct strbuf *out, int use_pack_protocol,
193 const struct sha1_array *extra,
194 unsigned flags)
195{
196 struct write_shallow_data data;
197 int i;
198 data.out = out;
199 data.use_pack_protocol = use_pack_protocol;
200 data.count = 0;
201 data.flags = flags;
202 for_each_commit_graft(write_one_shallow, &data);
203 if (!extra)
204 return data.count;
205 for (i = 0; i < extra->nr; i++) {
206 strbuf_addstr(out, sha1_to_hex(extra->sha1[i]));
207 strbuf_addch(out, '\n');
208 data.count++;
209 }
210 return data.count;
211}
212int write_shallow_commits(struct strbuf *out, int use_pack_protocol,
214 const struct sha1_array *extra)
215{
216 return write_shallow_commits_1(out, use_pack_protocol, extra, 0);
217}
218char *setup_temporary_shallow(const struct sha1_array *extra)
220{
221 struct strbuf sb = STRBUF_INIT;
222 int fd;
223 if (write_shallow_commits(&sb, 0, extra)) {
225 struct strbuf path = STRBUF_INIT;
226 strbuf_addstr(&path, git_path("shallow_XXXXXX"));
227 fd = xmkstemp(path.buf);
228 if (write_in_full(fd, sb.buf, sb.len) != sb.len)
229 die_errno("failed to write to %s",
230 path.buf);
231 close(fd);
232 strbuf_release(&sb);
233 return strbuf_detach(&path, NULL);
234 }
235 /*
236 * is_repository_shallow() sees empty string as "no shallow
237 * file".
238 */
239 return xstrdup("");
240}
241void setup_alternate_shallow(struct lock_file *shallow_lock,
243 const char **alternate_shallow_file,
244 const struct sha1_array *extra)
245{
246 struct strbuf sb = STRBUF_INIT;
247 int fd;
248 check_shallow_file_for_update();
250 fd = hold_lock_file_for_update(shallow_lock, git_path("shallow"),
251 LOCK_DIE_ON_ERROR);
252 if (write_shallow_commits(&sb, 0, extra)) {
253 if (write_in_full(fd, sb.buf, sb.len) != sb.len)
254 die_errno("failed to write to %s",
255 shallow_lock->filename);
256 *alternate_shallow_file = shallow_lock->filename;
257 } else
258 /*
259 * is_repository_shallow() sees empty string as "no
260 * shallow file".
261 */
262 *alternate_shallow_file = "";
263 strbuf_release(&sb);
264}
265static int advertise_shallow_grafts_cb(const struct commit_graft *graft, void *cb)
267{
268 int fd = *(int *)cb;
269 if (graft->nr_parent == -1)
270 packet_write(fd, "shallow %s\n", sha1_to_hex(graft->sha1));
271 return 0;
272}
273void advertise_shallow_grafts(int fd)
275{
276 if (!is_repository_shallow())
277 return;
278 for_each_commit_graft(advertise_shallow_grafts_cb, &fd);
279}
280/*
282 * mark_reachable_objects() should have been run prior to this and all
283 * reachable commits marked as "SEEN".
284 */
285void prune_shallow(int show_only)
286{
287 static struct lock_file shallow_lock;
288 struct strbuf sb = STRBUF_INIT;
289 int fd;
290 if (show_only) {
292 write_shallow_commits_1(&sb, 0, NULL, SEEN_ONLY | VERBOSE);
293 strbuf_release(&sb);
294 return;
295 }
296 check_shallow_file_for_update();
297 fd = hold_lock_file_for_update(&shallow_lock, git_path("shallow"),
298 LOCK_DIE_ON_ERROR);
299 if (write_shallow_commits_1(&sb, 0, NULL, SEEN_ONLY)) {
300 if (write_in_full(fd, sb.buf, sb.len) != sb.len)
301 die_errno("failed to write to %s",
302 shallow_lock.filename);
303 commit_lock_file(&shallow_lock);
304 } else {
305 unlink(git_path("shallow"));
306 rollback_lock_file(&shallow_lock);
307 }
308 strbuf_release(&sb);
309}
310#define TRACE_KEY "GIT_TRACE_SHALLOW"
312/*
314 * Step 1, split sender shallow commits into "ours" and "theirs"
315 * Step 2, clean "ours" based on .git/shallow
316 */
317void prepare_shallow_info(struct shallow_info *info, struct sha1_array *sa)
318{
319 int i;
320 trace_printf_key(TRACE_KEY, "shallow: prepare_shallow_info\n");
321 memset(info, 0, sizeof(*info));
322 info->shallow = sa;
323 if (!sa)
324 return;
325 info->ours = xmalloc(sizeof(*info->ours) * sa->nr);
326 info->theirs = xmalloc(sizeof(*info->theirs) * sa->nr);
327 for (i = 0; i < sa->nr; i++) {
328 if (has_sha1_file(sa->sha1[i])) {
329 struct commit_graft *graft;
330 graft = lookup_commit_graft(sa->sha1[i]);
331 if (graft && graft->nr_parent < 0)
332 continue;
333 info->ours[info->nr_ours++] = i;
334 } else
335 info->theirs[info->nr_theirs++] = i;
336 }
337}
338void clear_shallow_info(struct shallow_info *info)
340{
341 free(info->ours);
342 free(info->theirs);
343}
344/* Step 4, remove non-existent ones in "theirs" after getting the pack */
346void remove_nonexistent_theirs_shallow(struct shallow_info *info)
348{
349 unsigned char (*sha1)[20] = info->shallow->sha1;
350 int i, dst;
351 trace_printf_key(TRACE_KEY, "shallow: remove_nonexistent_theirs_shallow\n");
352 for (i = dst = 0; i < info->nr_theirs; i++) {
353 if (i != dst)
354 info->theirs[dst] = info->theirs[i];
355 if (has_sha1_file(sha1[info->theirs[i]]))
356 dst++;
357 }
358 info->nr_theirs = dst;
359}
360define_commit_slab(ref_bitmap, uint32_t *);
362struct paint_info {
364 struct ref_bitmap ref_bitmap;
365 unsigned nr_bits;
366 char **slab;
367 char *free, *end;
368 unsigned slab_count;
369};
370static uint32_t *paint_alloc(struct paint_info *info)
372{
373 unsigned nr = (info->nr_bits + 31) / 32;
374 unsigned size = nr * sizeof(uint32_t);
375 void *p;
376 if (!info->slab_count || info->free + size > info->end) {
377 info->slab_count++;
378 info->slab = xrealloc(info->slab,
379 info->slab_count * sizeof(*info->slab));
380 info->free = xmalloc(COMMIT_SLAB_SIZE);
381 info->slab[info->slab_count - 1] = info->free;
382 info->end = info->free + COMMIT_SLAB_SIZE;
383 }
384 p = info->free;
385 info->free += size;
386 return p;
387}
388/*
390 * Given a commit SHA-1, walk down to parents until either SEEN,
391 * UNINTERESTING or BOTTOM is hit. Set the id-th bit in ref_bitmap for
392 * all walked commits.
393 */
394static void paint_down(struct paint_info *info, const unsigned char *sha1,
395 int id)
396{
397 unsigned int i, nr;
398 struct commit_list *head = NULL;
399 int bitmap_nr = (info->nr_bits + 31) / 32;
400 int bitmap_size = bitmap_nr * sizeof(uint32_t);
401 uint32_t *tmp = xmalloc(bitmap_size); /* to be freed before return */
402 uint32_t *bitmap = paint_alloc(info);
403 struct commit *c = lookup_commit_reference_gently(sha1, 1);
404 if (!c)
405 return;
406 memset(bitmap, 0, bitmap_size);
407 bitmap[id / 32] |= (1 << (id % 32));
408 commit_list_insert(c, &head);
409 while (head) {
410 struct commit_list *p;
411 struct commit *c = head->item;
412 uint32_t **refs = ref_bitmap_at(&info->ref_bitmap, c);
413 p = head;
415 head = head->next;
416 free(p);
417 /* XXX check "UNINTERESTING" from pack bitmaps if available */
419 if (c->object.flags & (SEEN | UNINTERESTING))
420 continue;
421 else
422 c->object.flags |= SEEN;
423 if (*refs == NULL)
425 *refs = bitmap;
426 else {
427 memcpy(tmp, *refs, bitmap_size);
428 for (i = 0; i < bitmap_nr; i++)
429 tmp[i] |= bitmap[i];
430 if (memcmp(tmp, *refs, bitmap_size)) {
431 *refs = paint_alloc(info);
432 memcpy(*refs, tmp, bitmap_size);
433 }
434 }
435 if (c->object.flags & BOTTOM)
437 continue;
438 if (parse_commit(c))
440 die("unable to parse commit %s",
441 sha1_to_hex(c->object.sha1));
442 for (p = c->parents; p; p = p->next) {
444 uint32_t **p_refs = ref_bitmap_at(&info->ref_bitmap,
445 p->item);
446 if (p->item->object.flags & SEEN)
447 continue;
448 if (*p_refs == NULL || *p_refs == *refs)
449 *p_refs = *refs;
450 commit_list_insert(p->item, &head);
451 }
452 }
453 nr = get_max_object_index();
455 for (i = 0; i < nr; i++) {
456 struct object *o = get_indexed_object(i);
457 if (o && o->type == OBJ_COMMIT)
458 o->flags &= ~SEEN;
459 }
460 free(tmp);
462}
463static int mark_uninteresting(const char *refname,
465 const unsigned char *sha1,
466 int flags, void *cb_data)
467{
468 struct commit *commit = lookup_commit_reference_gently(sha1, 1);
469 if (!commit)
470 return 0;
471 commit->object.flags |= UNINTERESTING;
472 mark_parents_uninteresting(commit);
473 return 0;
474}
475static void post_assign_shallow(struct shallow_info *info,
477 struct ref_bitmap *ref_bitmap,
478 int *ref_status);
479/*
480 * Step 6(+7), associate shallow commits with new refs
481 *
482 * info->ref must be initialized before calling this function.
483 *
484 * If used is not NULL, it's an array of info->shallow->nr
485 * bitmaps. The n-th bit set in the m-th bitmap if ref[n] needs the
486 * m-th shallow commit from info->shallow.
487 *
488 * If used is NULL, "ours" and "theirs" are updated. And if ref_status
489 * is not NULL it's an array of ref->nr ints. ref_status[i] is true if
490 * the ref needs some shallow commits from either info->ours or
491 * info->theirs.
492 */
493void assign_shallow_commits_to_refs(struct shallow_info *info,
494 uint32_t **used, int *ref_status)
495{
496 unsigned char (*sha1)[20] = info->shallow->sha1;
497 struct sha1_array *ref = info->ref;
498 unsigned int i, nr;
499 int *shallow, nr_shallow = 0;
500 struct paint_info pi;
501 trace_printf_key(TRACE_KEY, "shallow: assign_shallow_commits_to_refs\n");
503 shallow = xmalloc(sizeof(*shallow) * (info->nr_ours + info->nr_theirs));
504 for (i = 0; i < info->nr_ours; i++)
505 shallow[nr_shallow++] = info->ours[i];
506 for (i = 0; i < info->nr_theirs; i++)
507 shallow[nr_shallow++] = info->theirs[i];
508 /*
510 * Prepare the commit graph to track what refs can reach what
511 * (new) shallow commits.
512 */
513 nr = get_max_object_index();
514 for (i = 0; i < nr; i++) {
515 struct object *o = get_indexed_object(i);
516 if (!o || o->type != OBJ_COMMIT)
517 continue;
518 o->flags &= ~(UNINTERESTING | BOTTOM | SEEN);
520 }
521 memset(&pi, 0, sizeof(pi));
523 init_ref_bitmap(&pi.ref_bitmap);
524 pi.nr_bits = ref->nr;
525 /*
527 * "--not --all" to cut short the traversal if new refs
528 * connect to old refs. If not (e.g. force ref updates) it'll
529 * have to go down to the current shallow commits.
530 */
531 head_ref(mark_uninteresting, NULL);
532 for_each_ref(mark_uninteresting, NULL);
533 /* Mark potential bottoms so we won't go out of bound */
535 for (i = 0; i < nr_shallow; i++) {
536 struct commit *c = lookup_commit(sha1[shallow[i]]);
537 c->object.flags |= BOTTOM;
538 }
539 for (i = 0; i < ref->nr; i++)
541 paint_down(&pi, ref->sha1[i], i);
542 if (used) {
544 int bitmap_size = ((pi.nr_bits + 31) / 32) * sizeof(uint32_t);
545 memset(used, 0, sizeof(*used) * info->shallow->nr);
546 for (i = 0; i < nr_shallow; i++) {
547 const struct commit *c = lookup_commit(sha1[shallow[i]]);
548 uint32_t **map = ref_bitmap_at(&pi.ref_bitmap, c);
549 if (*map)
550 used[shallow[i]] = xmemdupz(*map, bitmap_size);
551 }
552 /*
553 * unreachable shallow commits are not removed from
554 * "ours" and "theirs". The user is supposed to run
555 * step 7 on every ref separately and not trust "ours"
556 * and "theirs" any more.
557 */
558 } else
559 post_assign_shallow(info, &pi.ref_bitmap, ref_status);
560 clear_ref_bitmap(&pi.ref_bitmap);
562 for (i = 0; i < pi.slab_count; i++)
563 free(pi.slab[i]);
564 free(pi.slab);
565 free(shallow);
566}
567struct commit_array {
569 struct commit **commits;
570 int nr, alloc;
571};
572static int add_ref(const char *refname,
574 const unsigned char *sha1, int flags, void *cb_data)
575{
576 struct commit_array *ca = cb_data;
577 ALLOC_GROW(ca->commits, ca->nr + 1, ca->alloc);
578 ca->commits[ca->nr] = lookup_commit_reference_gently(sha1, 1);
579 if (ca->commits[ca->nr])
580 ca->nr++;
581 return 0;
582}
583static void update_refstatus(int *ref_status, int nr, uint32_t *bitmap)
585{
586 int i;
587 if (!ref_status)
588 return;
589 for (i = 0; i < nr; i++)
590 if (bitmap[i / 32] & (1 << (i % 32)))
591 ref_status[i]++;
592}
593/*
595 * Step 7, reachability test on "ours" at commit level
596 */
597static void post_assign_shallow(struct shallow_info *info,
598 struct ref_bitmap *ref_bitmap,
599 int *ref_status)
600{
601 unsigned char (*sha1)[20] = info->shallow->sha1;
602 struct commit *c;
603 uint32_t **bitmap;
604 int dst, i, j;
605 int bitmap_nr = (info->ref->nr + 31) / 32;
606 struct commit_array ca;
607 trace_printf_key(TRACE_KEY, "shallow: post_assign_shallow\n");
609 if (ref_status)
610 memset(ref_status, 0, sizeof(*ref_status) * info->ref->nr);
611 /* Remove unreachable shallow commits from "theirs" */
613 for (i = dst = 0; i < info->nr_theirs; i++) {
614 if (i != dst)
615 info->theirs[dst] = info->theirs[i];
616 c = lookup_commit(sha1[info->theirs[i]]);
617 bitmap = ref_bitmap_at(ref_bitmap, c);
618 if (!*bitmap)
619 continue;
620 for (j = 0; j < bitmap_nr; j++)
621 if (bitmap[0][j]) {
622 update_refstatus(ref_status, info->ref->nr, *bitmap);
623 dst++;
624 break;
625 }
626 }
627 info->nr_theirs = dst;
628 memset(&ca, 0, sizeof(ca));
630 head_ref(add_ref, &ca);
631 for_each_ref(add_ref, &ca);
632 /* Remove unreachable shallow commits from "ours" */
634 for (i = dst = 0; i < info->nr_ours; i++) {
635 if (i != dst)
636 info->ours[dst] = info->ours[i];
637 c = lookup_commit(sha1[info->ours[i]]);
638 bitmap = ref_bitmap_at(ref_bitmap, c);
639 if (!*bitmap)
640 continue;
641 for (j = 0; j < bitmap_nr; j++)
642 if (bitmap[0][j] &&
643 /* Step 7, reachability test at commit level */
644 !in_merge_bases_many(c, ca.nr, ca.commits)) {
645 update_refstatus(ref_status, info->ref->nr, *bitmap);
646 dst++;
647 break;
648 }
649 }
650 info->nr_ours = dst;
651 free(ca.commits);
653}
654/* (Delayed) step 7, reachability test at commit level */
656int delayed_reachability_test(struct shallow_info *si, int c)
657{
658 if (si->need_reachability_test[c]) {
659 struct commit *commit = lookup_commit(si->shallow->sha1[c]);
660 if (!si->commits) {
662 struct commit_array ca;
663 memset(&ca, 0, sizeof(ca));
664 head_ref(add_ref, &ca);
665 for_each_ref(add_ref, &ca);
666 si->commits = ca.commits;
667 si->nr_commits = ca.nr;
668 }
669 si->reachable[c] = in_merge_bases_many(commit,
671 si->nr_commits,
672 si->commits);
673 si->need_reachability_test[c] = 0;
674 }
675 return si->reachable[c];
676}