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