7 #include "sha1-array.h"
10 #include "commit-slab.h"
12 static int is_shallow
= -1;
13 static struct stat shallow_stat
;
14 static char *alternate_shallow_file
;
16 void set_alternate_shallow_file(const char *path
)
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
;
24 int register_shallow(const unsigned char *sha1
)
26 struct commit_graft
*graft
=
27 xmalloc(sizeof(struct commit_graft
));
28 struct commit
*commit
= lookup_commit(sha1
);
30 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);
37 int is_repository_shallow(void)
41 const char *path
= alternate_shallow_file
;
47 path
= git_path("shallow");
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.
54 stat(path
, &shallow_stat
) ||
55 (fp
= fopen(path
, "r")) == NULL
) {
61 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
);
71 struct commit_list
*get_shallow_commits(struct object_array
*heads
, int depth
,
72 int shallow_flag
, int not_shallow_flag
)
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
;
79 while (commit
|| i
< heads
->nr
|| stack
.nr
) {
80 struct commit_list
*p
;
83 commit
= (struct commit
*)
84 deref_tag(heads
->objects
[i
++].item
, NULL
, 0);
85 if (!commit
|| commit
->object
.type
!= OBJ_COMMIT
) {
90 commit
->util
= xmalloc(sizeof(int));
91 *(int *)commit
->util
= 0;
94 commit
= (struct commit
*)
95 stack
.objects
[--stack
.nr
].item
;
96 cur_depth
= *(int *)commit
->util
;
99 if (parse_commit(commit
))
100 die("invalid commit");
102 if (cur_depth
>= depth
) {
103 commit_list_insert(commit
, &result
);
104 commit
->object
.flags
|= shallow_flag
;
108 commit
->object
.flags
|= not_shallow_flag
;
109 for (p
= commit
->parents
, commit
= NULL
; p
; p
= p
->next
) {
110 if (!p
->item
->util
) {
111 int *pointer
= xmalloc(sizeof(int));
112 p
->item
->util
= pointer
;
113 *pointer
= cur_depth
;
115 int *pointer
= p
->item
->util
;
116 if (cur_depth
>= *pointer
)
118 *pointer
= cur_depth
;
121 add_object_array(&p
->item
->object
,
125 cur_depth
= *(int *)commit
->util
;
133 void check_shallow_file_for_update(void)
139 else if (is_shallow
== -1)
140 die("BUG: shallow must be initialized by now");
142 if (stat(git_path("shallow"), &st
))
143 die("shallow file was removed during fetch");
144 else if (st
.st_mtime
!= shallow_stat
.st_mtime
146 || ST_MTIME_NSEC(st
) != ST_MTIME_NSEC(shallow_stat
)
149 die("shallow file was changed during fetch");
152 struct write_shallow_data
{
154 int use_pack_protocol
;
158 static int write_one_shallow(const struct commit_graft
*graft
, void *cb_data
)
160 struct write_shallow_data
*data
= cb_data
;
161 const char *hex
= sha1_to_hex(graft
->sha1
);
162 if (graft
->nr_parent
!= -1)
165 if (data
->use_pack_protocol
)
166 packet_buf_write(data
->out
, "shallow %s", hex
);
168 strbuf_addstr(data
->out
, hex
);
169 strbuf_addch(data
->out
, '\n');
174 int write_shallow_commits(struct strbuf
*out
, int use_pack_protocol
,
175 const struct sha1_array
*extra
)
177 struct write_shallow_data data
;
180 data
.use_pack_protocol
= use_pack_protocol
;
182 for_each_commit_graft(write_one_shallow
, &data
);
185 for (i
= 0; i
< extra
->nr
; i
++) {
186 strbuf_addstr(out
, sha1_to_hex(extra
->sha1
[i
]));
187 strbuf_addch(out
, '\n');
193 char *setup_temporary_shallow(const struct sha1_array
*extra
)
195 struct strbuf sb
= STRBUF_INIT
;
198 if (write_shallow_commits(&sb
, 0, extra
)) {
199 struct strbuf path
= STRBUF_INIT
;
200 strbuf_addstr(&path
, git_path("shallow_XXXXXX"));
201 fd
= xmkstemp(path
.buf
);
202 if (write_in_full(fd
, sb
.buf
, sb
.len
) != sb
.len
)
203 die_errno("failed to write to %s",
207 return strbuf_detach(&path
, NULL
);
210 * is_repository_shallow() sees empty string as "no shallow
216 void setup_alternate_shallow(struct lock_file
*shallow_lock
,
217 const char **alternate_shallow_file
,
218 const struct sha1_array
*extra
)
220 struct strbuf sb
= STRBUF_INIT
;
223 check_shallow_file_for_update();
224 fd
= hold_lock_file_for_update(shallow_lock
, git_path("shallow"),
226 if (write_shallow_commits(&sb
, 0, extra
)) {
227 if (write_in_full(fd
, sb
.buf
, sb
.len
) != sb
.len
)
228 die_errno("failed to write to %s",
229 shallow_lock
->filename
);
230 *alternate_shallow_file
= shallow_lock
->filename
;
233 * is_repository_shallow() sees empty string as "no
236 *alternate_shallow_file
= "";
240 static int advertise_shallow_grafts_cb(const struct commit_graft
*graft
, void *cb
)
243 if (graft
->nr_parent
== -1)
244 packet_write(fd
, "shallow %s\n", sha1_to_hex(graft
->sha1
));
248 void advertise_shallow_grafts(int fd
)
250 if (!is_repository_shallow())
252 for_each_commit_graft(advertise_shallow_grafts_cb
, &fd
);
255 #define TRACE_KEY "GIT_TRACE_SHALLOW"
258 * Step 1, split sender shallow commits into "ours" and "theirs"
259 * Step 2, clean "ours" based on .git/shallow
261 void prepare_shallow_info(struct shallow_info
*info
, struct sha1_array
*sa
)
264 trace_printf_key(TRACE_KEY
, "shallow: prepare_shallow_info\n");
265 memset(info
, 0, sizeof(*info
));
269 info
->ours
= xmalloc(sizeof(*info
->ours
) * sa
->nr
);
270 info
->theirs
= xmalloc(sizeof(*info
->theirs
) * sa
->nr
);
271 for (i
= 0; i
< sa
->nr
; i
++) {
272 if (has_sha1_file(sa
->sha1
[i
])) {
273 struct commit_graft
*graft
;
274 graft
= lookup_commit_graft(sa
->sha1
[i
]);
275 if (graft
&& graft
->nr_parent
< 0)
277 info
->ours
[info
->nr_ours
++] = i
;
279 info
->theirs
[info
->nr_theirs
++] = i
;
283 void clear_shallow_info(struct shallow_info
*info
)
289 /* Step 4, remove non-existent ones in "theirs" after getting the pack */
291 void remove_nonexistent_theirs_shallow(struct shallow_info
*info
)
293 unsigned char (*sha1
)[20] = info
->shallow
->sha1
;
295 trace_printf_key(TRACE_KEY
, "shallow: remove_nonexistent_theirs_shallow\n");
296 for (i
= dst
= 0; i
< info
->nr_theirs
; i
++) {
298 info
->theirs
[dst
] = info
->theirs
[i
];
299 if (has_sha1_file(sha1
[info
->theirs
[i
]]))
302 info
->nr_theirs
= dst
;
305 /* Step 5, remove non-existent ones in "ours" in the pack */
306 void remove_nonexistent_ours_in_pack(struct shallow_info
*info
,
307 struct packed_git
*p
)
309 unsigned char (*sha1
)[20] = info
->shallow
->sha1
;
311 trace_printf_key(TRACE_KEY
, "shallow: remove_nonexistent_ours_in_pack\n");
312 for (i
= dst
= 0; i
< info
->nr_ours
; i
++) {
314 info
->ours
[dst
] = info
->ours
[i
];
315 if (find_pack_entry_one(sha1
[info
->ours
[i
]], p
))
321 define_commit_slab(ref_bitmap
, uint32_t *);
324 struct ref_bitmap ref_bitmap
;
331 static uint32_t *paint_alloc(struct paint_info
*info
)
333 unsigned nr
= (info
->nr_bits
+ 31) / 32;
334 unsigned size
= nr
* sizeof(uint32_t);
336 if (!info
->slab_count
|| info
->free
+ size
> info
->end
) {
338 info
->slab
= xrealloc(info
->slab
,
339 info
->slab_count
* sizeof(*info
->slab
));
340 info
->free
= xmalloc(COMMIT_SLAB_SIZE
);
341 info
->slab
[info
->slab_count
- 1] = info
->free
;
342 info
->end
= info
->free
+ COMMIT_SLAB_SIZE
;
350 * Given a commit SHA-1, walk down to parents until either SEEN,
351 * UNINTERESTING or BOTTOM is hit. Set the id-th bit in ref_bitmap for
352 * all walked commits.
354 static void paint_down(struct paint_info
*info
, const unsigned char *sha1
,
358 struct commit_list
*head
= NULL
;
359 int bitmap_nr
= (info
->nr_bits
+ 31) / 32;
360 int bitmap_size
= bitmap_nr
* sizeof(uint32_t);
361 uint32_t *tmp
= xmalloc(bitmap_size
); /* to be freed before return */
362 uint32_t *bitmap
= paint_alloc(info
);
363 struct commit
*c
= lookup_commit_reference_gently(sha1
, 1);
366 memset(bitmap
, 0, bitmap_size
);
367 bitmap
[id
/ 32] |= (1 << (id
% 32));
368 commit_list_insert(c
, &head
);
370 struct commit_list
*p
;
371 struct commit
*c
= head
->item
;
372 uint32_t **refs
= ref_bitmap_at(&info
->ref_bitmap
, c
);
378 /* XXX check "UNINTERESTING" from pack bitmaps if available */
379 if (c
->object
.flags
& (SEEN
| UNINTERESTING
))
382 c
->object
.flags
|= SEEN
;
387 memcpy(tmp
, *refs
, bitmap_size
);
388 for (i
= 0; i
< bitmap_nr
; i
++)
390 if (memcmp(tmp
, *refs
, bitmap_size
)) {
391 *refs
= paint_alloc(info
);
392 memcpy(*refs
, tmp
, bitmap_size
);
396 if (c
->object
.flags
& BOTTOM
)
400 die("unable to parse commit %s",
401 sha1_to_hex(c
->object
.sha1
));
403 for (p
= c
->parents
; p
; p
= p
->next
) {
404 uint32_t **p_refs
= ref_bitmap_at(&info
->ref_bitmap
,
406 if (p
->item
->object
.flags
& SEEN
)
408 if (*p_refs
== NULL
|| *p_refs
== *refs
)
410 commit_list_insert(p
->item
, &head
);
414 nr
= get_max_object_index();
415 for (i
= 0; i
< nr
; i
++) {
416 struct object
*o
= get_indexed_object(i
);
417 if (o
&& o
->type
== OBJ_COMMIT
)
424 static int mark_uninteresting(const char *refname
,
425 const unsigned char *sha1
,
426 int flags
, void *cb_data
)
428 struct commit
*commit
= lookup_commit_reference_gently(sha1
, 1);
431 commit
->object
.flags
|= UNINTERESTING
;
432 mark_parents_uninteresting(commit
);
436 static void post_assign_shallow(struct shallow_info
*info
,
437 struct ref_bitmap
*ref_bitmap
,
440 * Step 6(+7), associate shallow commits with new refs
442 * info->ref must be initialized before calling this function.
444 * If used is not NULL, it's an array of info->shallow->nr
445 * bitmaps. The n-th bit set in the m-th bitmap if ref[n] needs the
446 * m-th shallow commit from info->shallow.
448 * If used is NULL, "ours" and "theirs" are updated. And if ref_status
449 * is not NULL it's an array of ref->nr ints. ref_status[i] is true if
450 * the ref needs some shallow commits from either info->ours or
453 void assign_shallow_commits_to_refs(struct shallow_info
*info
,
454 uint32_t **used
, int *ref_status
)
456 unsigned char (*sha1
)[20] = info
->shallow
->sha1
;
457 struct sha1_array
*ref
= info
->ref
;
459 int *shallow
, nr_shallow
= 0;
460 struct paint_info pi
;
462 trace_printf_key(TRACE_KEY
, "shallow: assign_shallow_commits_to_refs\n");
463 shallow
= xmalloc(sizeof(*shallow
) * (info
->nr_ours
+ info
->nr_theirs
));
464 for (i
= 0; i
< info
->nr_ours
; i
++)
465 shallow
[nr_shallow
++] = info
->ours
[i
];
466 for (i
= 0; i
< info
->nr_theirs
; i
++)
467 shallow
[nr_shallow
++] = info
->theirs
[i
];
470 * Prepare the commit graph to track what refs can reach what
471 * (new) shallow commits.
473 nr
= get_max_object_index();
474 for (i
= 0; i
< nr
; i
++) {
475 struct object
*o
= get_indexed_object(i
);
476 if (!o
|| o
->type
!= OBJ_COMMIT
)
479 o
->flags
&= ~(UNINTERESTING
| BOTTOM
| SEEN
);
482 memset(&pi
, 0, sizeof(pi
));
483 init_ref_bitmap(&pi
.ref_bitmap
);
484 pi
.nr_bits
= ref
->nr
;
487 * "--not --all" to cut short the traversal if new refs
488 * connect to old refs. If not (e.g. force ref updates) it'll
489 * have to go down to the current shallow commits.
491 head_ref(mark_uninteresting
, NULL
);
492 for_each_ref(mark_uninteresting
, NULL
);
494 /* Mark potential bottoms so we won't go out of bound */
495 for (i
= 0; i
< nr_shallow
; i
++) {
496 struct commit
*c
= lookup_commit(sha1
[shallow
[i
]]);
497 c
->object
.flags
|= BOTTOM
;
500 for (i
= 0; i
< ref
->nr
; i
++)
501 paint_down(&pi
, ref
->sha1
[i
], i
);
504 int bitmap_size
= ((pi
.nr_bits
+ 31) / 32) * sizeof(uint32_t);
505 memset(used
, 0, sizeof(*used
) * info
->shallow
->nr
);
506 for (i
= 0; i
< nr_shallow
; i
++) {
507 const struct commit
*c
= lookup_commit(sha1
[shallow
[i
]]);
508 uint32_t **map
= ref_bitmap_at(&pi
.ref_bitmap
, c
);
510 used
[shallow
[i
]] = xmemdupz(*map
, bitmap_size
);
513 * unreachable shallow commits are not removed from
514 * "ours" and "theirs". The user is supposed to run
515 * step 7 on every ref separately and not trust "ours"
516 * and "theirs" any more.
519 post_assign_shallow(info
, &pi
.ref_bitmap
, ref_status
);
521 clear_ref_bitmap(&pi
.ref_bitmap
);
522 for (i
= 0; i
< pi
.slab_count
; i
++)
528 struct commit_array
{
529 struct commit
**commits
;
533 static int add_ref(const char *refname
,
534 const unsigned char *sha1
, int flags
, void *cb_data
)
536 struct commit_array
*ca
= cb_data
;
537 ALLOC_GROW(ca
->commits
, ca
->nr
+ 1, ca
->alloc
);
538 ca
->commits
[ca
->nr
] = lookup_commit_reference_gently(sha1
, 1);
539 if (ca
->commits
[ca
->nr
])
544 static void update_refstatus(int *ref_status
, int nr
, uint32_t *bitmap
)
549 for (i
= 0; i
< nr
; i
++)
550 if (bitmap
[i
/ 32] & (1 << (i
% 32)))
555 * Step 7, reachability test on "ours" at commit level
557 static void post_assign_shallow(struct shallow_info
*info
,
558 struct ref_bitmap
*ref_bitmap
,
561 unsigned char (*sha1
)[20] = info
->shallow
->sha1
;
565 int bitmap_nr
= (info
->ref
->nr
+ 31) / 32;
566 struct commit_array ca
;
568 trace_printf_key(TRACE_KEY
, "shallow: post_assign_shallow\n");
570 memset(ref_status
, 0, sizeof(*ref_status
) * info
->ref
->nr
);
572 /* Remove unreachable shallow commits from "theirs" */
573 for (i
= dst
= 0; i
< info
->nr_theirs
; i
++) {
575 info
->theirs
[dst
] = info
->theirs
[i
];
576 c
= lookup_commit(sha1
[info
->theirs
[i
]]);
577 bitmap
= ref_bitmap_at(ref_bitmap
, c
);
580 for (j
= 0; j
< bitmap_nr
; j
++)
582 update_refstatus(ref_status
, info
->ref
->nr
, *bitmap
);
587 info
->nr_theirs
= dst
;
589 memset(&ca
, 0, sizeof(ca
));
590 head_ref(add_ref
, &ca
);
591 for_each_ref(add_ref
, &ca
);
593 /* Remove unreachable shallow commits from "ours" */
594 for (i
= dst
= 0; i
< info
->nr_ours
; i
++) {
596 info
->ours
[dst
] = info
->ours
[i
];
597 c
= lookup_commit(sha1
[info
->ours
[i
]]);
598 bitmap
= ref_bitmap_at(ref_bitmap
, c
);
601 for (j
= 0; j
< bitmap_nr
; j
++)
603 /* Step 7, reachability test at commit level */
604 !in_merge_bases_many(c
, ca
.nr
, ca
.commits
)) {
605 update_refstatus(ref_status
, info
->ref
->nr
, *bitmap
);