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